Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.
|Comment:||Fix a comment in vdbesort.c.|
|Downloads:||Tarball | ZIP archive | SQL archive|
|Timelines:||family | ancestors | descendants | both | experimental|
|Files:||files | file ages | folders|
|User & Date:||dan 2011-08-04 18:43:37|
|11:49||Minor internal changes to vdbesort.c. Also, default to merging lists together 16 at a time. check-in: 9ddc324a user: dan tags: experimental|
|18:43||Fix a comment in vdbesort.c. check-in: db8518ca user: dan tags: experimental|
|12:14||Change to using packed-memory-arrays instead of b-trees when performing an offline merge-sort for CREATE INDEX. This makes it easier to control the number of disc seeks required when merging. check-in: a4770d07 user: dan tags: experimental|
Changes to src/vdbesort.c.
17 17 18 18 #include "sqliteInt.h" 19 19 #include "vdbeInt.h" 20 20 21 21 typedef struct VdbeSorterIter VdbeSorterIter; 22 22 23 23 /* 24 -** The aIter and aTree arrays are used to iterate through the sorter 25 -** contents after it has been populated. To iterate through the sorter 26 -** contents, the contents of all packed-memory-arrays (PMAs) must be 27 -** merged. This structure supports merging any number of arrays in a 28 -** single pass with no redundant comparison operations. 24 +** As keys are added to the sorter, they are written to disk in a series 25 +** of sorted packed-memory-arrays (PMAs). The size of each PMA is roughly 26 +** the same as the cache-size allowed for temporary databases. In order 27 +** to allow the caller to extract keys from the sorter in sorted order, 28 +** all PMAs currently stored on disk must be merged together. This comment 29 +** describes the data structure used to do so. The structure supports 30 +** merging any number of arrays in a single pass with no redundant comparison 31 +** operations. 29 32 ** 30 -** TODO: It may turn out that the optimum number of PMAs to merge in a 31 -** single pass is 2. If this is the case, this data structure could be 32 -** simplified. 33 +** The aIter array contains an iterator for each of the PMAs being merged. 34 +** An aIter iterator either points to a valid key or else is at EOF. For 35 +** the purposes of the paragraphs below, we assume that the array is actually 36 +** N elements in size, where N is the smallest power of 2 greater to or equal 37 +** to the number of iterators being merged. The extra aIter elements are 38 +** treated as if they are empty (always at EOF). 33 39 ** 34 -** The first few elements of the aIter array contain pointers into 35 -** each of the PMAs being merged. An aIter element either points to a 36 -** valid key or else is at EOF. For the purposes of the paragraphs below, 37 -** we assume that the array is actually N elements in size, where N is the 38 -** smallest power of 2 greater to or equal to nRoot. The extra aIter 39 -** elements are treated as if they are empty PMAs (always at EOF). 40 -** 41 -** The aTree array is N elements in size. The value of N is stored in 40 +** The aTree array is also N elements in size. The value of N is stored in 42 41 ** the VdbeSorter.nTree variable. 43 42 ** 44 43 ** The final (N/2) elements of aTree contain the results of comparing 45 44 ** pairs of iterator keys together. Element i contains the result of 46 45 ** comparing aIter[2*i-N] and aIter[2*i-N+1]. Whichever key is smaller, the 47 46 ** aTree element is set to the index of it. 48 47 **