SQLite

Check-in [db8518cab8]
Login

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

Overview
Comment:Fix a comment in vdbesort.c.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | experimental
Files: files | file ages | folders
SHA1: db8518cab8e329b1dbe4cd6c81b21ef3ea69fcb1
User & Date: dan 2011-08-04 18:43:37.790
Context
2011-08-05
11:49
Minor internal changes to vdbesort.c. Also, default to merging lists together 16 at a time. (check-in: 9ddc324a34 user: dan tags: experimental)
2011-08-04
18:43
Fix a comment in vdbesort.c. (check-in: db8518cab8 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: a4770d079c user: dan tags: experimental)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/vdbesort.c.
︙︙
17
18
19
20
21
22
23
24
25
26


27

28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48


#include "sqliteInt.h"
#include "vdbeInt.h"

typedef struct VdbeSorterIter VdbeSorterIter;

/*
** The aIter[] and aTree[] arrays are used to iterate through the sorter
** contents after it has been populated. To iterate through the sorter
** contents, the contents of all packed-memory-arrays (PMAs) must be 


** merged. This structure supports merging any number of arrays in a 

** single pass with no redundant comparison operations.
**
** TODO: It may turn out that the optimum number of PMAs to merge in a 
** single pass is 2. If this is the case, this data structure could be
** simplified.
**
** The first few elements of the aIter[] array contain pointers into
** each of the PMAs being merged. An aIter[] element either points to a 
** valid key or else is at EOF. For the purposes of the paragraphs below, 
** we assume that the array is actually N elements in size, where N is the
** smallest power of 2 greater to or equal to nRoot. The extra aIter[]
** elements are treated as if they are empty PMAs (always at EOF).
**
** The aTree[] array is N elements in size. The value of N is stored in
** the VdbeSorter.nTree variable.
**
** The final (N/2) elements of aTree[] contain the results of comparing
** pairs of iterator keys together. Element i contains the result of 
** comparing aIter[2*i-N] and aIter[2*i-N+1]. Whichever key is smaller, the
** aTree element is set to the index of it. 
**








<
|
|
>
>
|
>
|
|
<
<
<

|
|
|
|
|
|

|








17
18
19
20
21
22
23

24
25
26
27
28
29
30
31



32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


#include "sqliteInt.h"
#include "vdbeInt.h"

typedef struct VdbeSorterIter VdbeSorterIter;

/*

** As keys are added to the sorter, they are written to disk in a series
** of sorted packed-memory-arrays (PMAs). The size of each PMA is roughly
** the same as the cache-size allowed for temporary databases. In order
** to allow the caller to extract keys from the sorter in sorted order,
** all PMAs currently stored on disk must be merged together. This comment
** describes the data structure used to do so. The structure supports 
** merging any number of arrays in a single pass with no redundant comparison 
** operations.



**
** The aIter[] array contains an iterator for each of the PMAs being merged.
** An aIter[] iterator either points to a valid key or else is at EOF. For 
** the purposes of the paragraphs below, we assume that the array is actually 
** N elements in size, where N is the smallest power of 2 greater to or equal 
** to the number of iterators being merged. The extra aIter[] elements are 
** treated as if they are empty (always at EOF).
**
** The aTree[] array is also N elements in size. The value of N is stored in
** the VdbeSorter.nTree variable.
**
** The final (N/2) elements of aTree[] contain the results of comparing
** pairs of iterator keys together. Element i contains the result of 
** comparing aIter[2*i-N] and aIter[2*i-N+1]. Whichever key is smaller, the
** aTree element is set to the index of it. 
**
︙︙