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

Changes to src/vdbesort.c.

    85     85   **
    86     86   ** In other words, each time we advance to the next sorter element, log2(N)
    87     87   ** key comparison operations are required, where N is the number of segments
    88     88   ** being merged (rounded up to the next power of 2).
    89     89   */
    90     90   struct VdbeSorter {
    91     91     int nWorking;                   /* Start a new b-tree after this many pages */
    92         -  int nAlloc;                     /* Allocated size of aIter[] and aTree[] */
    93     92     int nTree;                      /* Used size of aTree/aIter (power of 2) */
    94     93     VdbeSorterIter *aIter;          /* Array of iterators to merge */
    95     94     int *aTree;                     /* Current state of incremental merge */
    96     95   
    97     96     i64 iWriteOff;                  /* Current write offset within file pTemp1 */
    98     97     sqlite3_file *pTemp1;           /* PMA file 1 */
    99     98     i64 *aOffset;                   /* Array of PMA offsets for file 1 */
................................................................................
   114    113     u8 *aKey;                       /* Pointer to current key */
   115    114   };
   116    115   
   117    116   /* Minimum allowable value for the VdbeSorter.nWorking variable */
   118    117   #define SORTER_MIN_SEGMENT_SIZE 10
   119    118   
   120    119   /* Maximum number of segments to merge in a single go */
   121         -#define SORTER_MAX_MERGE_COUNT 2
          120  +#define SORTER_MAX_MERGE_COUNT 16
   122    121   
   123    122   /*
   124    123   ** Append integer iOff to the VdbeSorter.aOffset[] array of the sorter object
   125    124   ** passed as the second argument. SQLITE_NOMEM is returned if an OOM error
   126    125   ** is encountered, or SQLITE_OK if no error occurs.
   127    126   **
   128    127   ** TODO: The aOffset[] array may grow indefinitely. Fix this.
   129    128   */
   130    129   static int vdbeSorterAppendOffset(sqlite3 *db, VdbeSorter *p, i64 iOff){
   131         -  int *aNew;                      /* New VdbeSorter.aRoot[] array */
   132    130     p->aOffset = sqlite3DbReallocOrFree(
   133    131         db, p->aOffset, (p->nOffset+1)*sizeof(i64)
   134    132     );
   135    133     if( !p->aOffset ) return SQLITE_NOMEM;
   136    134     p->aOffset[p->nOffset++] = iOff;
   137    135     return SQLITE_OK;
   138    136   }
................................................................................
   288    286   ** Free any cursor components allocated by sqlite3VdbeSorterXXX routines.
   289    287   */
   290    288   void sqlite3VdbeSorterClose(sqlite3 *db, VdbeCursor *pCsr){
   291    289     VdbeSorter *pSorter = pCsr->pSorter;
   292    290     if( pSorter ){
   293    291       if( pSorter->aIter ){
   294    292         int i;
   295         -      for(i=0; i<pSorter->nAlloc; i++){
          293  +      for(i=0; i<pSorter->nTree; i++){
   296    294           vdbeSorterIterZero(db, &pSorter->aIter[i]);
   297    295         }
   298    296         sqlite3DbFree(db, pSorter->aIter);
   299         -      sqlite3DbFree(db, pSorter->aTree);
   300    297       }
   301    298       if( pSorter->pTemp1 ){
   302    299         sqlite3OsCloseFree(pSorter->pTemp1);
   303    300       }
   304    301       sqlite3DbFree(db, pSorter->aOffset);
   305    302       sqlite3DbFree(db, pSorter);
   306    303       pCsr->pSorter = 0;
................................................................................
   444    441           rc = sqlite3BtreeCursor(pCsr->pBt, iRoot, 1, pCsr->pKeyInfo, p);
   445    442         }
   446    443       }
   447    444     }
   448    445     return rc;
   449    446   }
   450    447   
   451         -/*
   452         -** Extend the pSorter->aIter[] and pSorter->aTree[] arrays using DbRealloc().
   453         -** Return SQLITE_OK if successful, or SQLITE_NOMEM otherwise.
   454         -*/
   455         -static int vdbeSorterGrowArrays(sqlite3* db, VdbeSorter *pSorter){
   456         -  int *aTree;                     /* New aTree[] allocation */
   457         -  VdbeSorterIter *aIter;          /* New aIter[] allocation */
   458         -  int nOld = pSorter->nAlloc;     /* Current size of arrays */
   459         -  int nNew = (nOld?nOld*2:4);     /* Size of arrays after reallocation */
   460         -
   461         -  /* Realloc aTree[]. */
   462         -  aTree = sqlite3DbRealloc(db, pSorter->aTree, sizeof(int)*nNew);
   463         -  if( !aTree ) return SQLITE_NOMEM;
   464         -  memset(&aTree[nOld], 0, (nNew-nOld) * sizeof(int));
   465         -  pSorter->aTree = aTree;
   466         -
   467         -  /* Realloc aIter[]. */
   468         -  aIter = sqlite3DbRealloc(db, pSorter->aIter, sizeof(VdbeSorterIter)*nNew);
   469         -  if( !aIter ) return SQLITE_NOMEM;
   470         -  memset(&aIter[nOld], 0, (nNew-nOld) * sizeof(VdbeSorterIter));
   471         -  pSorter->aIter = aIter;
   472         -
   473         -  /* Set VdbeSorter.nAlloc to the new size of the arrays and return OK. */
   474         -  pSorter->nAlloc = nNew;
   475         -  return SQLITE_OK;
   476         -}
   477         -
   478    448   /*
   479    449   ** Helper function for sqlite3VdbeSorterRewind().
   480    450   */
   481    451   static int vdbeSorterInitMerge(
   482    452     sqlite3 *db,
   483    453     VdbeCursor *pCsr,
   484    454     int iFirst,
   485    455     int *piNext
   486    456   ){
   487         -  Pager *pPager = sqlite3BtreePager(pCsr->pBt);
   488    457     VdbeSorter *pSorter = pCsr->pSorter;
   489    458     int rc = SQLITE_OK;
   490    459     int i;
   491         -  int nMaxRef = (pSorter->nWorking * 9/10);
   492    460     int N = 2;
          461  +  int nIter;                      /* Number of iterators to initialize. */
   493    462   
   494         -  assert( iFirst<pSorter->nOffset );
          463  +  nIter = pSorter->nOffset - iFirst;
          464  +  if( nIter>SORTER_MAX_MERGE_COUNT ){
          465  +    nIter = SORTER_MAX_MERGE_COUNT;
          466  +  }
          467  +  assert( nIter>0 );
          468  +  while( N<nIter ) N += N;
          469  +
          470  +  /* Allocate aIter[] and aTree[], if required. */
          471  +  if( pSorter->aIter==0 ){
          472  +    int nByte = N * (sizeof(int) + sizeof(VdbeSorterIter));
          473  +    pSorter->aIter = (VdbeSorterIter *)sqlite3DbMallocZero(db, nByte);
          474  +    if( !pSorter->aIter ) return SQLITE_NOMEM;
          475  +    pSorter->aTree = (int *)&pSorter->aIter[N];
          476  +  }
   495    477   
   496    478     /* Initialize as many iterators as possible. */
   497    479     for(i=iFirst; 
   498    480         rc==SQLITE_OK && i<pSorter->nOffset && (i-iFirst)<SORTER_MAX_MERGE_COUNT; 
   499    481         i++
   500    482     ){
   501    483       int iIter = i - iFirst;
   502    484   
   503         -    assert( iIter<=pSorter->nAlloc );
   504         -    if( iIter==pSorter->nAlloc ){
   505         -      rc = vdbeSorterGrowArrays(db, pSorter);
   506         -    }
   507         -
   508    485       if( rc==SQLITE_OK ){
   509    486         VdbeSorterIter *pIter = &pSorter->aIter[iIter];
   510    487         i64 iStart = pSorter->aOffset[i];
   511    488         i64 iEof;
   512    489         if( i==(pSorter->nOffset-1) ){
   513    490           iEof = pSorter->iWriteOff;
   514    491         }else{
   515    492           iEof = pSorter->aOffset[i+1];
   516    493         }
   517    494         rc = vdbeSorterIterInit(db, pSorter->pTemp1, iStart, iEof, pIter);
   518         -      if( i>iFirst+1 ){
   519         -        int nRef = (i-iFirst)*10;
   520         -        if( nRef>=nMaxRef ){
   521         -          i++;
   522         -          break;
   523         -        }
   524         -      }
   525    495       }
   526    496     }
   527    497     *piNext = i;
   528    498   
   529    499     assert( i>iFirst );
   530         -  while( (i-iFirst)>N ) N += N;
   531    500     pSorter->nTree = N;
   532    501   
   533    502     /* Populate the aTree[] array. */
   534    503     for(i=N-1; rc==SQLITE_OK && i>0; i--){
   535    504       rc = vdbeSorterDoCompare(pCsr, i);
   536    505     }
   537    506   
................................................................................
   556    525     if( rc!=SQLITE_OK ) return rc;
   557    526     if( pSorter->nOffset==0 ){
   558    527       *pbEof = 1;
   559    528       return SQLITE_OK;
   560    529     }
   561    530   
   562    531     while( rc==SQLITE_OK ){
   563         -    int iRoot = 0;
   564    532       int iNext = 0;                /* Index of next segment to open */
   565    533       int iNew = 0;                 /* Index of new, merged, PMA */
   566    534   
   567    535       do {
   568    536   
   569    537         /* This call configures iterators for merging. */
   570    538         rc = vdbeSorterInitMerge(db, pCsr, iNext, &iNext);
   571    539         assert( iNext>0 );
   572    540         assert( rc!=SQLITE_OK || pSorter->aIter[ pSorter->aTree[1] ].pFile );
   573    541   
   574         -      if( rc==SQLITE_OK && (iRoot>0 || iNext<pSorter->nOffset) ){
   575         -        int pgno;
          542  +      if( rc==SQLITE_OK && (iNew>0 || iNext<pSorter->nOffset) ){
   576    543           int bEof = 0;
   577    544   
   578    545           if( pTemp2==0 ){
   579    546             rc = vdbeSorterOpenTempFile(db, &pTemp2);
   580    547           }
   581    548           if( rc==SQLITE_OK ){
   582         -          pSorter->aOffset[iRoot] = iWrite2;
          549  +          pSorter->aOffset[iNew] = iWrite2;
   583    550           }
   584    551   
   585    552           while( rc==SQLITE_OK && bEof==0 ){
   586    553             int nByte;
   587    554             VdbeSorterIter *pIter = &pSorter->aIter[ pSorter->aTree[1] ];
   588    555             assert( pIter->pFile );
   589    556             nByte = pIter->nKey + sqlite3VarintLen(pIter->nKey);
   590    557             rc = sqlite3OsWrite(pTemp2, pIter->aAlloc, nByte, iWrite2);
   591    558             iWrite2 += nByte;
   592    559             if( rc==SQLITE_OK ){
   593    560               rc = sqlite3VdbeSorterNext(db, pCsr, &bEof);
   594    561             }
   595    562           }
   596         -        iRoot++;
          563  +        iNew++;
   597    564         }
   598    565       }while( rc==SQLITE_OK && iNext<pSorter->nOffset );
   599    566   
   600         -    if( iRoot==0 ){
          567  +    if( iNew==0 ){
   601    568         break;
   602    569       }else{
   603    570         sqlite3_file *pTmp = pSorter->pTemp1;
   604         -      pSorter->nOffset = iRoot;
          571  +      pSorter->nOffset = iNew;
   605    572         pSorter->pTemp1 = pTemp2;
   606    573         pTemp2 = pTmp;
   607    574         pSorter->iWriteOff = iWrite2;
   608    575         iWrite2 = 0;
   609    576       }
   610    577     }
   611    578