/ 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 Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/vdbeInt.h.

   391    391   void sqlite3VdbeFrameDelete(VdbeFrame*);
   392    392   int sqlite3VdbeFrameRestore(VdbeFrame *);
   393    393   void sqlite3VdbeMemStoreType(Mem *pMem);
   394    394   
   395    395   int sqlite3VdbeSorterInit(sqlite3 *, VdbeCursor *);
   396    396   int sqlite3VdbeSorterWrite(sqlite3 *, VdbeCursor *);
   397    397   void sqlite3VdbeSorterClose(sqlite3 *, VdbeCursor *);
          398  +
          399  +int sqlite3VdbeSorterRowkey(sqlite3 *, VdbeCursor *, Mem *);
          400  +int sqlite3VdbeSorterRewind(sqlite3 *, VdbeCursor *, int *);
          401  +int sqlite3VdbeSorterNext(sqlite3 *, VdbeCursor *, int *);
   398    402   
   399    403   #if !defined(SQLITE_OMIT_SHARED_CACHE) && SQLITE_THREADSAFE>0
   400    404     void sqlite3VdbeEnter(Vdbe*);
   401    405     void sqlite3VdbeLeave(Vdbe*);
   402    406   #else
   403    407   # define sqlite3VdbeEnter(X)
   404    408   # define sqlite3VdbeLeave(X)

Changes to src/vdbesort.c.

   107    107     int nKey;                       /* Number of bytes in key */
   108    108     u8 *aKey;                       /* Pointer to current key */
   109    109   };
   110    110   
   111    111   /* Minimum allowable value for the VdbeSorter.nWorking variable */
   112    112   #define SORTER_MIN_SEGMENT_SIZE 10
   113    113   
          114  +/* Maximum number of segments to merge in a single go */
          115  +#define SORTER_MAX_MERGE_COUNT 256
          116  +
   114    117   /*
   115    118   ** Append integer iRoot to the VdbeSorter.aRoot[] array of the sorter object
   116    119   ** passed as the second argument. SQLITE_NOMEM is returned if an OOM error
   117    120   ** is encountered, or SQLITE_OK if no error occurs.
   118    121   **
   119    122   ** TODO: The aRoot[] array may grow indefinitely. Fix this.
   120    123   */
................................................................................
   184    187   */
   185    188   static int vdbeSorterIterInit(
   186    189     sqlite3 *db,                    /* Database handle */
   187    190     VdbeCursor *pCsr,               /* Vdbe cursor handle */
   188    191     int iRoot,                      /* Root page of b-tree to iterate */
   189    192     VdbeSorterIter *pIter           /* Pointer to iterator to initialize */
   190    193   ){
   191         -  VdbeSorter *pSorter = pCsr->pSorter;
   192    194     int rc;
   193    195   
   194    196     pIter->pCsr = (BtCursor *)sqlite3DbMallocZero(db, sqlite3BtreeCursorSize());
   195    197     if( !pIter->pCsr ){
   196    198       rc = SQLITE_NOMEM;
   197    199     }else{
   198    200       rc = sqlite3BtreeCursor(pCsr->pBt, iRoot, 1, pCsr->pKeyInfo, pIter->pCsr);
................................................................................
   214    216   static int vdbeSorterIterNext(
   215    217     sqlite3 *db, 
   216    218     VdbeCursor *pCsr, 
   217    219     VdbeSorterIter *pIter
   218    220   ){
   219    221     int rc;
   220    222     int bDummy;
   221         -  VdbeSorter *pSorter = pCsr->pSorter;
   222    223   
   223    224     rc = sqlite3BtreeNext(pIter->pCsr, &bDummy);
   224    225     if( rc==SQLITE_OK ){
   225    226       rc = vdbeSorterIterLoadkey(db, pIter);
   226    227     }
   227    228   
   228    229     return rc;
................................................................................
   407    408     VdbeSorter *pSorter = pCsr->pSorter;
   408    409     int rc = SQLITE_OK;
   409    410     int i;
   410    411     int nMaxRef = (pSorter->nWorking * 9/10);
   411    412     int N = 2;
   412    413   
   413    414     /* Initialize as many iterators as possible. */
   414         -  for(i=iFirst; rc==SQLITE_OK && i<pSorter->nRoot; i++){
          415  +  for(i=iFirst; 
          416  +      rc==SQLITE_OK && i<pSorter->nRoot && (i-iFirst)<SORTER_MAX_MERGE_COUNT; 
          417  +      i++
          418  +  ){
   415    419       int iIter = i - iFirst;
   416    420   
   417    421       assert( iIter<=pSorter->nAlloc );
   418    422       if( iIter==pSorter->nAlloc ){
   419    423         rc = vdbeSorterGrowArrays(db, pSorter);
   420    424       }
   421    425   
................................................................................
   446    450   
   447    451   /*
   448    452   ** Once the sorter has been populated, this function is called to prepare
   449    453   ** for iterating through its contents in sorted order.
   450    454   */
   451    455   int sqlite3VdbeSorterRewind(sqlite3 *db, VdbeCursor *pCsr, int *pbEof){
   452    456     int rc = SQLITE_OK;             /* Return code */
   453         -  int N;
   454         -  int i;
   455    457   
   456    458     VdbeSorter *pSorter = pCsr->pSorter;
   457    459     BtCursor *p = pCsr->pCursor;    /* Cursor structure */
   458    460   
   459    461     assert( pSorter );
   460    462     sqlite3BtreeCloseCursor(p);
   461    463   
................................................................................
   481    483             if( rc==SQLITE_OK ){
   482    484               rc = sqlite3VdbeSorterNext(db, pCsr, &bEof);
   483    485             }
   484    486           }
   485    487           sqlite3BtreeCloseCursor(p);
   486    488           iRoot++;
   487    489         }
   488         -    } while( rc==SQLITE_OK && iNext<pSorter->nRoot );
          490  +    }while( rc==SQLITE_OK && iNext<pSorter->nRoot );
   489    491   
   490    492       if( iRoot==0 ) break;
   491    493       pSorter->nRoot = iRoot;
   492    494     }
   493    495   
   494    496     *pbEof = (pSorter->aIter[pSorter->aTree[1]].pCsr==0);
   495    497     return rc;

Changes to tool/mksqlite3c.tcl.

   255    255   
   256    256      vdbemem.c
   257    257      vdbeaux.c
   258    258      vdbeapi.c
   259    259      vdbetrace.c
   260    260      vdbe.c
   261    261      vdbeblob.c
          262  +   vdbesort.c
   262    263      journal.c
   263    264      memjournal.c
   264    265   
   265    266      walker.c
   266    267      resolve.c
   267    268      expr.c
   268    269      alter.c