/ Check-in [7f339c0e]
Login

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

Overview
Comment:Minor fixes to vdbesort.c code in preparation for a major rework.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | experimental
Files: files | file ages | folders
SHA1:7f339c0e2655310d7530041c379b082d49ce8c7f
User & Date: dan 2011-08-02 10:56:22
Context
2011-08-04
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
2011-08-02
10:56
Minor fixes to vdbesort.c code in preparation for a major rework. check-in: 7f339c0e user: dan tags: experimental
2011-07-12
14:28
Experimental support for speeding up CREATE INDEX commands using an offline merge sort. check-in: 30dbf0fe user: dan tags: experimental
Changes
Hide Diffs Unified Diffs Show Whitespace Changes Patch

Changes to src/vdbeInt.h.

391
392
393
394
395
396
397




398
399
400
401
402
403
404
void sqlite3VdbeFrameDelete(VdbeFrame*);
int sqlite3VdbeFrameRestore(VdbeFrame *);
void sqlite3VdbeMemStoreType(Mem *pMem);

int sqlite3VdbeSorterInit(sqlite3 *, VdbeCursor *);
int sqlite3VdbeSorterWrite(sqlite3 *, VdbeCursor *);
void sqlite3VdbeSorterClose(sqlite3 *, VdbeCursor *);





#if !defined(SQLITE_OMIT_SHARED_CACHE) && SQLITE_THREADSAFE>0
  void sqlite3VdbeEnter(Vdbe*);
  void sqlite3VdbeLeave(Vdbe*);
#else
# define sqlite3VdbeEnter(X)
# define sqlite3VdbeLeave(X)







>
>
>
>







391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
void sqlite3VdbeFrameDelete(VdbeFrame*);
int sqlite3VdbeFrameRestore(VdbeFrame *);
void sqlite3VdbeMemStoreType(Mem *pMem);

int sqlite3VdbeSorterInit(sqlite3 *, VdbeCursor *);
int sqlite3VdbeSorterWrite(sqlite3 *, VdbeCursor *);
void sqlite3VdbeSorterClose(sqlite3 *, VdbeCursor *);

int sqlite3VdbeSorterRowkey(sqlite3 *, VdbeCursor *, Mem *);
int sqlite3VdbeSorterRewind(sqlite3 *, VdbeCursor *, int *);
int sqlite3VdbeSorterNext(sqlite3 *, VdbeCursor *, int *);

#if !defined(SQLITE_OMIT_SHARED_CACHE) && SQLITE_THREADSAFE>0
  void sqlite3VdbeEnter(Vdbe*);
  void sqlite3VdbeLeave(Vdbe*);
#else
# define sqlite3VdbeEnter(X)
# define sqlite3VdbeLeave(X)

Changes to src/vdbesort.c.

107
108
109
110
111
112
113



114
115
116
117
118
119
120
...
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
...
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
...
407
408
409
410
411
412
413

414


415
416
417
418
419
420
421
...
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
  int nKey;                       /* Number of bytes in key */
  u8 *aKey;                       /* Pointer to current key */
};

/* Minimum allowable value for the VdbeSorter.nWorking variable */
#define SORTER_MIN_SEGMENT_SIZE 10




/*
** Append integer iRoot to the VdbeSorter.aRoot[] array of the sorter object
** passed as the second argument. SQLITE_NOMEM is returned if an OOM error
** is encountered, or SQLITE_OK if no error occurs.
**
** TODO: The aRoot[] array may grow indefinitely. Fix this.
*/
................................................................................
*/
static int vdbeSorterIterInit(
  sqlite3 *db,                    /* Database handle */
  VdbeCursor *pCsr,               /* Vdbe cursor handle */
  int iRoot,                      /* Root page of b-tree to iterate */
  VdbeSorterIter *pIter           /* Pointer to iterator to initialize */
){
  VdbeSorter *pSorter = pCsr->pSorter;
  int rc;

  pIter->pCsr = (BtCursor *)sqlite3DbMallocZero(db, sqlite3BtreeCursorSize());
  if( !pIter->pCsr ){
    rc = SQLITE_NOMEM;
  }else{
    rc = sqlite3BtreeCursor(pCsr->pBt, iRoot, 1, pCsr->pKeyInfo, pIter->pCsr);
................................................................................
static int vdbeSorterIterNext(
  sqlite3 *db, 
  VdbeCursor *pCsr, 
  VdbeSorterIter *pIter
){
  int rc;
  int bDummy;
  VdbeSorter *pSorter = pCsr->pSorter;

  rc = sqlite3BtreeNext(pIter->pCsr, &bDummy);
  if( rc==SQLITE_OK ){
    rc = vdbeSorterIterLoadkey(db, pIter);
  }

  return rc;
................................................................................
  VdbeSorter *pSorter = pCsr->pSorter;
  int rc = SQLITE_OK;
  int i;
  int nMaxRef = (pSorter->nWorking * 9/10);
  int N = 2;

  /* Initialize as many iterators as possible. */

  for(i=iFirst; rc==SQLITE_OK && i<pSorter->nRoot; i++){


    int iIter = i - iFirst;

    assert( iIter<=pSorter->nAlloc );
    if( iIter==pSorter->nAlloc ){
      rc = vdbeSorterGrowArrays(db, pSorter);
    }

................................................................................

/*
** Once the sorter has been populated, this function is called to prepare
** for iterating through its contents in sorted order.
*/
int sqlite3VdbeSorterRewind(sqlite3 *db, VdbeCursor *pCsr, int *pbEof){
  int rc = SQLITE_OK;             /* Return code */
  int N;
  int i;

  VdbeSorter *pSorter = pCsr->pSorter;
  BtCursor *p = pCsr->pCursor;    /* Cursor structure */

  assert( pSorter );
  sqlite3BtreeCloseCursor(p);








>
>
>







 







<







 







<







 







>
|
>
>







 







<
<







107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
...
187
188
189
190
191
192
193

194
195
196
197
198
199
200
...
216
217
218
219
220
221
222

223
224
225
226
227
228
229
...
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
...
450
451
452
453
454
455
456


457
458
459
460
461
462
463
  int nKey;                       /* Number of bytes in key */
  u8 *aKey;                       /* Pointer to current key */
};

/* Minimum allowable value for the VdbeSorter.nWorking variable */
#define SORTER_MIN_SEGMENT_SIZE 10

/* Maximum number of segments to merge in a single go */
#define SORTER_MAX_MERGE_COUNT 256

/*
** Append integer iRoot to the VdbeSorter.aRoot[] array of the sorter object
** passed as the second argument. SQLITE_NOMEM is returned if an OOM error
** is encountered, or SQLITE_OK if no error occurs.
**
** TODO: The aRoot[] array may grow indefinitely. Fix this.
*/
................................................................................
*/
static int vdbeSorterIterInit(
  sqlite3 *db,                    /* Database handle */
  VdbeCursor *pCsr,               /* Vdbe cursor handle */
  int iRoot,                      /* Root page of b-tree to iterate */
  VdbeSorterIter *pIter           /* Pointer to iterator to initialize */
){

  int rc;

  pIter->pCsr = (BtCursor *)sqlite3DbMallocZero(db, sqlite3BtreeCursorSize());
  if( !pIter->pCsr ){
    rc = SQLITE_NOMEM;
  }else{
    rc = sqlite3BtreeCursor(pCsr->pBt, iRoot, 1, pCsr->pKeyInfo, pIter->pCsr);
................................................................................
static int vdbeSorterIterNext(
  sqlite3 *db, 
  VdbeCursor *pCsr, 
  VdbeSorterIter *pIter
){
  int rc;
  int bDummy;


  rc = sqlite3BtreeNext(pIter->pCsr, &bDummy);
  if( rc==SQLITE_OK ){
    rc = vdbeSorterIterLoadkey(db, pIter);
  }

  return rc;
................................................................................
  VdbeSorter *pSorter = pCsr->pSorter;
  int rc = SQLITE_OK;
  int i;
  int nMaxRef = (pSorter->nWorking * 9/10);
  int N = 2;

  /* Initialize as many iterators as possible. */
  for(i=iFirst; 
      rc==SQLITE_OK && i<pSorter->nRoot && (i-iFirst)<SORTER_MAX_MERGE_COUNT; 
      i++
  ){
    int iIter = i - iFirst;

    assert( iIter<=pSorter->nAlloc );
    if( iIter==pSorter->nAlloc ){
      rc = vdbeSorterGrowArrays(db, pSorter);
    }

................................................................................

/*
** Once the sorter has been populated, this function is called to prepare
** for iterating through its contents in sorted order.
*/
int sqlite3VdbeSorterRewind(sqlite3 *db, VdbeCursor *pCsr, int *pbEof){
  int rc = SQLITE_OK;             /* Return code */



  VdbeSorter *pSorter = pCsr->pSorter;
  BtCursor *p = pCsr->pCursor;    /* Cursor structure */

  assert( pSorter );
  sqlite3BtreeCloseCursor(p);

Changes to tool/mksqlite3c.tcl.

255
256
257
258
259
260
261

262
263
264
265
266
267
268

   vdbemem.c
   vdbeaux.c
   vdbeapi.c
   vdbetrace.c
   vdbe.c
   vdbeblob.c

   journal.c
   memjournal.c

   walker.c
   resolve.c
   expr.c
   alter.c







>







255
256
257
258
259
260
261
262
263
264
265
266
267
268
269

   vdbemem.c
   vdbeaux.c
   vdbeapi.c
   vdbetrace.c
   vdbe.c
   vdbeblob.c
   vdbesort.c
   journal.c
   memjournal.c

   walker.c
   resolve.c
   expr.c
   alter.c