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

Changes to src/vdbe.c.

  4089   4089     assert( pC->isIndex || pOp->opcode==OP_RowData );
  4090   4090     assert( pC!=0 );
  4091   4091     assert( pC->nullRow==0 );
  4092   4092     assert( pC->pseudoTableReg==0 );
  4093   4093   
  4094   4094     if( isSorter(pC) ){
  4095   4095       assert( pOp->opcode==OP_RowKey );
  4096         -    rc = sqlite3VdbeSorterRowkey(db, pC, pOut);
         4096  +    rc = sqlite3VdbeSorterRowkey(pC, pOut);
  4097   4097       break;
  4098   4098     }
  4099   4099   
  4100   4100     assert( pC->pCursor!=0 );
  4101   4101     pCrsr = pC->pCursor;
  4102   4102     assert( sqlite3BtreeCursorIsValid(pCrsr) );
  4103   4103   

Changes to src/vdbeInt.h.

   392    392   int sqlite3VdbeFrameRestore(VdbeFrame *);
   393    393   void sqlite3VdbeMemStoreType(Mem *pMem);
   394    394   
   395    395   #ifdef SQLITE_OMIT_MERGE_SORT
   396    396   # define sqlite3VdbeSorterInit(Y,Z)      SQLITE_OK
   397    397   # define sqlite3VdbeSorterWrite(X,Y,Z)   SQLITE_OK
   398    398   # define sqlite3VdbeSorterClose(Y,Z)
   399         -# define sqlite3VdbeSorterRowkey(X,Y,Z)  SQLITE_OK
          399  +# define sqlite3VdbeSorterRowkey(Y,Z)    SQLITE_OK
   400    400   # define sqlite3VdbeSorterRewind(X,Y,Z)  SQLITE_OK
   401    401   # define sqlite3VdbeSorterNext(X,Y,Z)    SQLITE_OK
   402    402   #else
   403    403   int sqlite3VdbeSorterInit(sqlite3 *, VdbeCursor *);
   404    404   int sqlite3VdbeSorterWrite(sqlite3 *, VdbeCursor *, int);
   405    405   void sqlite3VdbeSorterClose(sqlite3 *, VdbeCursor *);
   406         -int sqlite3VdbeSorterRowkey(sqlite3 *, VdbeCursor *, Mem *);
          406  +int sqlite3VdbeSorterRowkey(VdbeCursor *, Mem *);
   407    407   int sqlite3VdbeSorterRewind(sqlite3 *, VdbeCursor *, int *);
   408    408   int sqlite3VdbeSorterNext(sqlite3 *, VdbeCursor *, int *);
   409    409   #endif
   410    410   
   411    411   #if !defined(SQLITE_OMIT_SHARED_CACHE) && SQLITE_THREADSAFE>0
   412    412     void sqlite3VdbeEnter(Vdbe*);
   413    413     void sqlite3VdbeLeave(Vdbe*);

Changes to src/vdbesort.c.

    19     19   #include "vdbeInt.h"
    20     20   
    21     21   #ifndef SQLITE_OMIT_MERGE_SORT
    22     22   
    23     23   typedef struct VdbeSorterIter VdbeSorterIter;
    24     24   
    25     25   /*
           26  +** NOTES ON DATA STRUCTURE USED FOR N-WAY MERGES:
           27  +**
    26     28   ** As keys are added to the sorter, they are written to disk in a series
    27     29   ** of sorted packed-memory-arrays (PMAs). The size of each PMA is roughly
    28     30   ** the same as the cache-size allowed for temporary databases. In order
    29     31   ** to allow the caller to extract keys from the sorter in sorted order,
    30     32   ** all PMAs currently stored on disk must be merged together. This comment
    31     33   ** describes the data structure used to do so. The structure supports 
    32     34   ** merging any number of arrays in a single pass with no redundant comparison 
................................................................................
   112    114     int nAlloc;                     /* Bytes of space at aAlloc */
   113    115     u8 *aAlloc;                     /* Allocated space */
   114    116     int nKey;                       /* Number of bytes in key */
   115    117     u8 *aKey;                       /* Pointer to current key */
   116    118   };
   117    119   
   118    120   /* Minimum allowable value for the VdbeSorter.nWorking variable */
   119         -#define SORTER_MIN_SEGMENT_SIZE 10
          121  +#define SORTER_MIN_WORKING 10
   120    122   
   121    123   /* Maximum number of segments to merge in a single pass. */
   122    124   #define SORTER_MAX_MERGE_COUNT 16
   123    125   
   124    126   /*
   125    127   ** Free all memory belonging to the VdbeSorterIter object passed as the second
   126    128   ** argument. All structure fields are set to zero before returning.
................................................................................
   127    129   */
   128    130   static void vdbeSorterIterZero(sqlite3 *db, VdbeSorterIter *pIter){
   129    131     sqlite3DbFree(db, pIter->aAlloc);
   130    132     memset(pIter, 0, sizeof(VdbeSorterIter));
   131    133   }
   132    134   
   133    135   /*
   134         -** Advance iterator pIter to the next key in its PMA.
          136  +** Advance iterator pIter to the next key in its PMA. Return SQLITE_OK if
          137  +** no error occurs, or an SQLite error code if one does.
   135    138   */
   136    139   static int vdbeSorterIterNext(
   137    140     sqlite3 *db,                    /* Database handle (for sqlite3DbMalloc() ) */
   138    141     VdbeSorterIter *pIter           /* Iterator to advance */
   139    142   ){
   140         -  int rc;
   141         -  int nRead;
   142         -  int nRec;
   143         -  int iOff;
          143  +  int rc;                         /* Return Code */
          144  +  int nRead;                      /* Number of bytes read */
          145  +  int nRec;                       /* Size of record in bytes */
          146  +  int iOff;                       /* Size of serialized size varint in bytes */
   144    147   
   145    148     nRead = pIter->iEof - pIter->iReadOff;
   146    149     if( nRead>5 ) nRead = 5;
   147    150     if( nRead<=0 ){
          151  +    /* This is an EOF condition */
   148    152       vdbeSorterIterZero(db, pIter);
   149    153       return SQLITE_OK;
   150    154     }
   151    155   
   152    156     rc = sqlite3OsRead(pIter->pFile, pIter->aAlloc, nRead, pIter->iReadOff);
   153    157     iOff = getVarint32(pIter->aAlloc, nRec);
   154    158   
   155    159     if( rc==SQLITE_OK && (iOff+nRec)>nRead ){
   156         -    int nRead2;
          160  +    int nRead2;                   /* Number of extra bytes to read */
   157    161       if( (iOff+nRec)>pIter->nAlloc ){
   158    162         int nNew = pIter->nAlloc*2;
   159    163         while( (iOff+nRec)>nNew ) nNew = nNew*2;
   160    164         pIter->aAlloc = sqlite3DbReallocOrFree(db, pIter->aAlloc, nNew);
   161    165         if( !pIter->aAlloc ) return SQLITE_NOMEM;
   162    166         pIter->nAlloc = nNew;
   163    167       }
................................................................................
   165    169       nRead2 = iOff + nRec - nRead;
   166    170       rc = sqlite3OsRead(
   167    171           pIter->pFile, &pIter->aAlloc[nRead], nRead2, pIter->iReadOff+nRead
   168    172       );
   169    173     }
   170    174   
   171    175     assert( nRec>0 || rc!=SQLITE_OK );
   172         -
   173    176     pIter->iReadOff += iOff+nRec;
   174    177     pIter->nKey = nRec;
   175    178     pIter->aKey = &pIter->aAlloc[iOff];
   176    179     return rc;
   177    180   }
   178    181   
   179    182   /*
................................................................................
   181    184   ** SQLITE_OK if successful, or an SQLite error code if some error occurs.
   182    185   **
   183    186   ** The value of *piOffset when this function is called is used as the byte
   184    187   ** offset in file pFile to write to. Before returning, *piOffset is 
   185    188   ** incremented by the number of bytes written.
   186    189   */
   187    190   static int vdbeSorterWriteVarint(
   188         -  sqlite3_file *pFile, 
   189         -  i64 iVal, 
   190         -  i64 *piOffset
          191  +  sqlite3_file *pFile,            /* File to write to */
          192  +  i64 iVal,                       /* Value to write as a varint */
          193  +  i64 *piOffset                   /* IN/OUT: Write offset in file pFile */
   191    194   ){
   192    195     u8 aVarint[9];                  /* Buffer large enough for a varint */
   193    196     int nVarint;                    /* Number of used bytes in varint */
   194    197     int rc;                         /* Result of write() call */
   195    198   
   196    199     nVarint = sqlite3PutVarint(aVarint, iVal);
   197    200     rc = sqlite3OsWrite(pFile, aVarint, nVarint, *piOffset);
................................................................................
   208    211   ** byte offset in file pFile from whence to read the varint. If successful
   209    212   ** (i.e. if no IO error occurs), then *piOffset is set to the offset of
   210    213   ** the first byte past the end of the varint before returning. *piVal is
   211    214   ** set to the integer value read. If an error occurs, the final values of
   212    215   ** both *piOffset and *piVal are undefined.
   213    216   */
   214    217   static int vdbeSorterReadVarint(
   215         -  sqlite3_file *pFile, 
          218  +  sqlite3_file *pFile,            /* File to read from */
   216    219     i64 iEof,                       /* Total number of bytes in file */
   217         -  i64 *piOffset,                  /* IN/OUT: Read offset */
          220  +  i64 *piOffset,                  /* IN/OUT: Read offset in pFile */
   218    221     i64 *piVal                      /* OUT: Value read from file */
   219    222   ){
   220    223     u8 aVarint[9];                  /* Buffer large enough for a varint */
   221    224     i64 iOff = *piOffset;           /* Offset in file to read from */
   222    225     int nRead = 9;                  /* Number of bytes to read from file */
   223    226     int rc;                         /* Return code */
   224    227   
................................................................................
   245    248     sqlite3 *db,                    /* Database handle */
   246    249     VdbeSorter *pSorter,            /* Sorter object */
   247    250     i64 iStart,                     /* Start offset in pFile */
   248    251     VdbeSorterIter *pIter,          /* Iterator to populate */
   249    252     i64 *pnByte                     /* IN/OUT: Increment this value by PMA size */
   250    253   ){
   251    254     int rc;
   252         -  i64 iEof = pSorter->iWriteOff;
   253    255   
   254         -  assert( iEof>iStart );
          256  +  assert( pSorter->iWriteOff>iStart );
   255    257     assert( pIter->aAlloc==0 );
   256    258     pIter->pFile = pSorter->pTemp1;
   257    259     pIter->iReadOff = iStart;
   258    260     pIter->nAlloc = 128;
   259    261     pIter->aAlloc = (u8 *)sqlite3DbMallocRaw(db, pIter->nAlloc);
   260    262     if( !pIter->aAlloc ){
   261    263       rc = SQLITE_NOMEM;
   262    264     }else{
   263         -    i64 nByte;
          265  +    i64 iEof = pSorter->iWriteOff;     /* EOF of file pSorter->pTemp1 */
          266  +    i64 nByte;                         /* Total size of PMA in bytes */
   264    267       rc = vdbeSorterReadVarint(pSorter->pTemp1, iEof, &pIter->iReadOff, &nByte);
   265    268       *pnByte += nByte;
   266    269       pIter->iEof = pIter->iReadOff + nByte;
   267    270     }
   268    271     if( rc==SQLITE_OK ){
   269    272       rc = vdbeSorterIterNext(db, pIter);
   270    273     }
................................................................................
   322    325     return SQLITE_OK;
   323    326   }
   324    327   
   325    328   /*
   326    329   ** Initialize the temporary index cursor just opened as a sorter cursor.
   327    330   */
   328    331   int sqlite3VdbeSorterInit(sqlite3 *db, VdbeCursor *pCsr){
   329         -  VdbeSorter *pSorter;            /* Allocated sorter object */
   330         -
   331         -  /* Cursor must be a temp cursor and not open on an intkey table */
   332    332     assert( pCsr->pKeyInfo && pCsr->pBt );
   333         -
   334         -  pSorter = sqlite3DbMallocZero(db, sizeof(VdbeSorter));
   335         -  if( !pSorter ) return SQLITE_NOMEM;
   336         -  pCsr->pSorter = pSorter;
   337         -  return SQLITE_OK;
          333  +  pCsr->pSorter = sqlite3DbMallocZero(db, sizeof(VdbeSorter));
          334  +  return (pCsr->pSorter ? SQLITE_NOMEM : SQLITE_OK);
   338    335   }
   339    336   
   340    337   /*
   341    338   ** Free any cursor components allocated by sqlite3VdbeSorterXXX routines.
   342    339   */
   343    340   void sqlite3VdbeSorterClose(sqlite3 *db, VdbeCursor *pCsr){
   344    341     VdbeSorter *pSorter = pCsr->pSorter;
................................................................................
   372    369     );
   373    370   }
   374    371   
   375    372   
   376    373   /*
   377    374   ** Write the current contents of the b-tree to a PMA. Return SQLITE_OK
   378    375   ** if successful, or an SQLite error code otherwise.
          376  +**
          377  +** The format of a PMA is:
          378  +**
          379  +**     * A varint. This varint contains the total number of bytes of content
          380  +**       in the PMA (not including the varint itself).
          381  +**
          382  +**     * One or more records packed end-to-end in order of ascending keys. 
          383  +**       Each record consists of a varint followed by a blob of data (the 
          384  +**       key). The varint is the number of bytes in the blob of data.
   379    385   */
   380    386   static int vdbeSorterBtreeToPMA(sqlite3 *db, VdbeCursor *pCsr){
   381    387     int rc = SQLITE_OK;             /* Return code */
   382    388     VdbeSorter *pSorter = pCsr->pSorter;
   383         -  i64 iWriteOff = pSorter->iWriteOff;
   384    389     int res = 0;
   385         -  void *aMalloc = 0;
   386         -  int nMalloc = 0;
   387    390   
   388    391     rc = sqlite3BtreeFirst(pCsr->pCursor, &res);
   389    392     if( rc!=SQLITE_OK || res ) return rc;
          393  +  assert( pSorter->nBtree>0 );
   390    394   
   391    395     /* If the first temporary PMA file has not been opened, open it now. */
   392    396     if( pSorter->pTemp1==0 ){
   393    397       rc = vdbeSorterOpenTempFile(db, &pSorter->pTemp1);
   394    398       assert( rc!=SQLITE_OK || pSorter->pTemp1 );
   395    399       assert( pSorter->iWriteOff==0 );
   396    400       assert( pSorter->nPMA==0 );
   397    401     }
   398    402   
   399    403     if( rc==SQLITE_OK ){
          404  +    i64 iWriteOff = pSorter->iWriteOff;
          405  +    void *aMalloc = 0;            /* Array used to hold a single record */
          406  +    int nMalloc = 0;              /* Allocated size of aMalloc[] in bytes */
   400    407   
   401    408       pSorter->nPMA++;
   402         -
   403         -    /* Write a varint containg the size of the PMA in bytes into the file. */
   404         -    assert( pSorter->nBtree>0 );
   405         -
   406    409       for(
   407    410         rc = vdbeSorterWriteVarint(pSorter->pTemp1, pSorter->nBtree, &iWriteOff);
   408    411         rc==SQLITE_OK && res==0;
   409    412         rc = sqlite3BtreeNext(pCsr->pCursor, &res)
   410    413       ){
   411    414         i64 nKey;                   /* Size of this key in bytes */
   412    415   
................................................................................
   432    435             iWriteOff += nKey;
   433    436           }
   434    437         }
   435    438   
   436    439         if( rc!=SQLITE_OK ) break;
   437    440       }
   438    441   
          442  +    /* This assert verifies that unless an error has occurred, the size of 
          443  +    ** the PMA on disk is the same as the expected size stored in
          444  +    ** pSorter->nBtree. */ 
   439    445       assert( rc!=SQLITE_OK || pSorter->nBtree==(
   440    446             iWriteOff-pSorter->iWriteOff-sqlite3VarintLen(pSorter->nBtree)
   441    447       ));
          448  +
   442    449       pSorter->iWriteOff = iWriteOff;
   443    450       sqlite3DbFree(db, aMalloc);
   444    451     }
   445    452   
   446    453     pSorter->nBtree = 0;
   447    454     return rc;
   448    455   }
   449    456   
   450    457   /*
   451         -** This function is called on a sorter cursor before each row is inserted.
   452         -** If the current b-tree being constructed is already considered "full",
   453         -** a new tree is started.
          458  +** This function is called on a sorter cursor by the VDBE before each row 
          459  +** is inserted into VdbeCursor.pCsr. Argument nKey is the size of the key, in
          460  +** bytes, about to be inserted.
          461  +**
          462  +** If it is determined that the temporary b-tree accessed via VdbeCursor.pCsr
          463  +** is large enough, its contents are written to a sorted PMA on disk and the
          464  +** tree emptied. This prevents the b-tree (which must be small enough to
          465  +** fit entirely in the cache in order to support efficient inserts) from
          466  +** growing too large.
          467  +**
          468  +** An SQLite error code is returned if an error occurs. Otherwise, SQLITE_OK.
   454    469   */
   455    470   int sqlite3VdbeSorterWrite(sqlite3 *db, VdbeCursor *pCsr, int nKey){
   456    471     int rc = SQLITE_OK;             /* Return code */
   457    472     VdbeSorter *pSorter = pCsr->pSorter;
   458    473     if( pSorter ){
   459    474       Pager *pPager = sqlite3BtreePager(pCsr->pBt);
   460    475       int nPage;                    /* Current size of temporary file in pages */
   461    476   
          477  +    /* Determine how many pages the temporary b-tree has grown to */
   462    478       sqlite3PagerPagecount(pPager, &nPage);
   463    479   
   464    480       /* If pSorter->nWorking is still zero, but the temporary file has been
   465    481       ** created in the file-system, then the most recent insert into the
   466    482       ** current b-tree segment probably caused the cache to overflow (it is
   467    483       ** also possible that sqlite3_release_memory() was called). So set the
   468    484       ** size of the working set to a little less than the current size of the 
   469    485       ** file in pages.  */
   470    486       if( pSorter->nWorking==0 && sqlite3PagerFile(pPager)->pMethods ){
   471    487         pSorter->nWorking = nPage-5;
   472         -      if( pSorter->nWorking<SORTER_MIN_SEGMENT_SIZE ){
   473         -        pSorter->nWorking = SORTER_MIN_SEGMENT_SIZE;
          488  +      if( pSorter->nWorking<SORTER_MIN_WORKING ){
          489  +        pSorter->nWorking = SORTER_MIN_WORKING;
   474    490         }
   475    491       }
   476    492   
   477    493       /* If the number of pages used by the current b-tree segment is greater
   478    494       ** than the size of the working set (VdbeSorter.nWorking), start a new
   479    495       ** segment b-tree.  */
   480    496       if( pSorter->nWorking && nPage>=pSorter->nWorking ){
................................................................................
   660    676     *pbEof = (pSorter->aIter[pSorter->aTree[1]].pFile==0);
   661    677     return rc;
   662    678   }
   663    679   
   664    680   /*
   665    681   ** Copy the current sorter key into the memory cell pOut.
   666    682   */
   667         -int sqlite3VdbeSorterRowkey(sqlite3 *db, VdbeCursor *pCsr, Mem *pOut){
          683  +int sqlite3VdbeSorterRowkey(VdbeCursor *pCsr, Mem *pOut){
   668    684     VdbeSorter *pSorter = pCsr->pSorter;
   669    685     VdbeSorterIter *pIter;
   670    686   
   671    687     pIter = &pSorter->aIter[ pSorter->aTree[1] ];
   672    688   
   673    689     /* Coverage testing note: As things are currently, this call will always
   674    690     ** succeed. This is because the memory cell passed by the VDBE layer