/ Check-in [db8518ca]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Fix a comment in vdbesort.c.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | experimental
Files: files | file ages | folders
SHA1: db8518cab8e329b1dbe4cd6c81b21ef3ea69fcb1
User & Date: dan 2011-08-04 18:43:37
Context
2011-08-05
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
2011-08-04
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
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

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   **