src/vdbesort.c

   1 /*
   2 ** 2011 July 9
   3 **
   4 ** The author disclaims copyright to this source code.  In place of
   5 ** a legal notice, here is a blessing:
   6 **
   7 **    May you do good and not evil.
   8 **    May you find forgiveness for yourself and forgive others.
   9 **    May you share freely, never taking more than you give.
  10 **
  11 *************************************************************************
  12 ** This file contains code for the VdbeSorter object, used in concert with
  13 ** a VdbeCursor to sort large numbers of keys (as may be required, for
  14 ** example, by CREATE INDEX statements on tables too large to fit in main
  15 ** memory).
  16 */
  17
  18 #include "sqliteInt.h"
  19 #include "vdbeInt.h"
  20
  21
  22 typedef struct VdbeSorterIter VdbeSorterIter;
  23 typedef struct SorterRecord SorterRecord;
  24 typedef struct FileWriter FileWriter;
  25
  26 /*
  27 ** NOTES ON DATA STRUCTURE USED FOR N-WAY MERGES:
  28 **
  29 ** As keys are added to the sorter, they are written to disk in a series
  30 ** of sorted packed-memory-arrays (PMAs). The size of each PMA is roughly
  31 ** the same as the cache-size allowed for temporary databases. In order
  32 ** to allow the caller to extract keys from the sorter in sorted order,
  33 ** all PMAs currently stored on disk must be merged together. This comment
  34 ** describes the data structure used to do so. The structure supports
  35 ** merging any number of arrays in a single pass with no redundant comparison
  36 ** operations.
  37 **
  38 ** The aIter[] array contains an iterator for each of the PMAs being merged.
  39 ** An aIter[] iterator either points to a valid key or else is at EOF. For
  40 ** the purposes of the paragraphs below, we assume that the array is actually
  41 ** N elements in size, where N is the smallest power of 2 greater to or equal
  42 ** to the number of iterators being merged. The extra aIter[] elements are
  43 ** treated as if they are empty (always at EOF).
  44 **
  45 ** The aTree[] array is also N elements in size. The value of N is stored in
  46 ** the VdbeSorter.nTree variable.
  47 **
  48 ** The final (N/2) elements of aTree[] contain the results of comparing
  49 ** pairs of iterator keys together. Element i contains the result of
  50 ** comparing aIter[2*i-N] and aIter[2*i-N+1]. Whichever key is smaller, the
  51 ** aTree element is set to the index of it.
  52 **
  53 ** For the purposes of this comparison, EOF is considered greater than any
  54 ** other key value. If the keys are equal (only possible with two EOF
  55 ** values), it doesn't matter which index is stored.
  56 **
  57 ** The (N/4) elements of aTree[] that precede the final (N/2) described
  58 ** above contains the index of the smallest of each block of 4 iterators.
  59 ** And so on. So that aTree[1] contains the index of the iterator that
  60 ** currently points to the smallest key value. aTree[0] is unused.
  61 **
  62 ** Example:
  63 **
  64 **     aIter[0] -> Banana
  65 **     aIter[1] -> Feijoa
  66 **     aIter[2] -> Elderberry
  67 **     aIter[3] -> Currant
  68 **     aIter[4] -> Grapefruit
  69 **     aIter[5] -> Apple
  70 **     aIter[6] -> Durian
  71 **     aIter[7] -> EOF
  72 **
  73 **     aTree[] = { X, 5   0, 5    0, 3, 5, 6 }
  74 **
  75 ** The current element is "Apple" (the value of the key indicated by
  76 ** iterator 5). When the Next() operation is invoked, iterator 5 will
  77 ** be advanced to the next key in its segment. Say the next key is
  78 ** "Eggplant":
  79 **
  80 **     aIter[5] -> Eggplant
  81 **
  82 ** The contents of aTree[] are updated first by comparing the new iterator
  83 ** 5 key to the current key of iterator 4 (still "Grapefruit"). The iterator
  84 ** 5 value is still smaller, so aTree[6] is set to 5. And so on up the tree.
  85 ** The value of iterator 6 - "Durian" - is now smaller than that of iterator
  86 ** 5, so aTree[3] is set to 6. Key 0 is smaller than key 6 (Banana<Durian),
  87 ** so the value written into element 1 of the array is 0. As follows:
  88 **
  89 **     aTree[] = { X, 0   0, 6    0, 3, 5, 6 }
  90 **
  91 ** In other words, each time we advance to the next sorter element, log2(N)
  92 ** key comparison operations are required, where N is the number of segments
  93 ** being merged (rounded up to the next power of 2).
  94 */
  95 struct VdbeSorter {
  96   i64 iWriteOff;                  /* Current write offset within file pTemp1 */
  97   i64 iReadOff;                   /* Current read offset within file pTemp1 */
  98   int nInMemory;                  /* Current size of pRecord list as PMA */
  99   int nTree;                      /* Used size of aTree/aIter (power of 2) */
 100   int nPMA;                       /* Number of PMAs stored in pTemp1 */
 101   int mnPmaSize;                  /* Minimum PMA size, in bytes */
 102   int mxPmaSize;                  /* Maximum PMA size, in bytes.  0==no limit */
 103   VdbeSorterIter *aIter;          /* Array of iterators to merge */
 104   int *aTree;                     /* Current state of incremental merge */
 105   sqlite3_file *pTemp1;           /* PMA file 1 */
 106   SorterRecord *pRecord;          /* Head of in-memory record list */
 107   UnpackedRecord *pUnpacked;      /* Used to unpack keys */
 108 };
 109
 110 /*
 111 ** The following type is an iterator for a PMA. It caches the current key in
 112 ** variables nKey/aKey. If the iterator is at EOF, pFile==0.
 113 */
 114 struct VdbeSorterIter {
 115   i64 iReadOff;                   /* Current read offset */
 116   i64 iEof;                       /* 1 byte past EOF for this iterator */
 117   int nAlloc;                     /* Bytes of space at aAlloc */
 118   int nKey;                       /* Number of bytes in key */
 119   sqlite3_file *pFile;            /* File iterator is reading from */
 120   u8 *aAlloc;                     /* Allocated space */
 121   u8 *aKey;                       /* Pointer to current key */
 122   u8 *aBuffer;                    /* Current read buffer */
 123   int nBuffer;                    /* Size of read buffer in bytes */
 124 };
 125
 126 /*
 127 ** An instance of this structure is used to organize the stream of records
 128 ** being written to files by the merge-sort code into aligned, page-sized
 129 ** blocks.  Doing all I/O in aligned page-sized blocks helps I/O to go
 130 ** faster on many operating systems.
 131 */
 132 struct FileWriter {
 133   int eFWErr;                     /* Non-zero if in an error state */
 134   u8 *aBuffer;                    /* Pointer to write buffer */
 135   int nBuffer;                    /* Size of write buffer in bytes */
 136   int iBufStart;                  /* First byte of buffer to write */
 137   int iBufEnd;                    /* Last byte of buffer to write */
 138   i64 iWriteOff;                  /* Offset of start of buffer in file */
 139   sqlite3_file *pFile;            /* File to write to */
 140 };
 141
 142 /*
 143 ** A structure to store a single record. All in-memory records are connected
 144 ** together into a linked list headed at VdbeSorter.pRecord using the
 145 ** SorterRecord.pNext pointer.
 146 */
 147 struct SorterRecord {
 148   void *pVal;
 149   int nVal;
 150   SorterRecord *pNext;
 151 };
 152
 153 /* Minimum allowable value for the VdbeSorter.nWorking variable */
 154 #define SORTER_MIN_WORKING 10
 155
 156 /* Maximum number of segments to merge in a single pass. */
 157 #define SORTER_MAX_MERGE_COUNT 16
 158
 159 /*
 160 ** Free all memory belonging to the VdbeSorterIter object passed as the second
 161 ** argument. All structure fields are set to zero before returning.
 162 */
 163 static void vdbeSorterIterZero(sqlite3 *db, VdbeSorterIter *pIter){
 164   sqlite3DbFree(db, pIter->aAlloc);
 165   sqlite3DbFree(db, pIter->aBuffer);
 166   memset(pIter, 0, sizeof(VdbeSorterIter));
 167 }
 168
 169 /*
 170 ** Read nByte bytes of data from the stream of data iterated by object p.
 171 ** If successful, set *ppOut to point to a buffer containing the data
 172 ** and return SQLITE_OK. Otherwise, if an error occurs, return an SQLite
 173 ** error code.
 174 **
 175 ** The buffer indicated by *ppOut may only be considered valid until the
 176 ** next call to this function.
 177 */
 178 static int vdbeSorterIterRead(
 179   sqlite3 *db,                    /* Database handle (for malloc) */
 180   VdbeSorterIter *p,              /* Iterator */
 181   int nByte,                      /* Bytes of data to read */
 182   u8 **ppOut                      /* OUT: Pointer to buffer containing data */
 183 ){
 184   int iBuf;                       /* Offset within buffer to read from */
 185   int nAvail;                     /* Bytes of data available in buffer */
 186   assert( p->aBuffer );
 187
 188   /* If there is no more data to be read from the buffer, read the next
 189   ** p->nBuffer bytes of data from the file into it. Or, if there are less
 190   ** than p->nBuffer bytes remaining in the PMA, read all remaining data.  */
 191   iBuf = p->iReadOff % p->nBuffer;
 192   if( iBuf==0 ){
 193     int nRead;                    /* Bytes to read from disk */
 194     int rc;                       /* sqlite3OsRead() return code */
 195
 196     /* Determine how many bytes of data to read. */
 197     if( (p->iEof - p->iReadOff) > (i64)p->nBuffer ){
 198       nRead = p->nBuffer;
 199     }else{
 200       nRead = (int)(p->iEof - p->iReadOff);
 201     }
 202     assert( nRead>0 );
 203
 204     /* Read data from the file. Return early if an error occurs. */
 205     rc = sqlite3OsRead(p->pFile, p->aBuffer, nRead, p->iReadOff);
 206     assert( rc!=SQLITE_IOERR_SHORT_READ );
 207     if( rc!=SQLITE_OK ) return rc;
 208   }
 209   nAvail = p->nBuffer - iBuf;
 210
 211   if( nByte<=nAvail ){
 212     /* The requested data is available in the in-memory buffer. In this
 213     ** case there is no need to make a copy of the data, just return a
 214     ** pointer into the buffer to the caller.  */
 215     *ppOut = &p->aBuffer[iBuf];
 216     p->iReadOff += nByte;
 217   }else{
 218     /* The requested data is not all available in the in-memory buffer.
 219     ** In this case, allocate space at p->aAlloc[] to copy the requested
 220     ** range into. Then return a copy of pointer p->aAlloc to the caller.  */
 221     int nRem;                     /* Bytes remaining to copy */
 222
 223     /* Extend the p->aAlloc[] allocation if required. */
 224     if( p->nAlloc<nByte ){
 225       int nNew = p->nAlloc*2;
 226       while( nByte>nNew ) nNew = nNew*2;
 227       p->aAlloc = sqlite3DbReallocOrFree(db, p->aAlloc, nNew);
 228       if( !p->aAlloc ) return SQLITE_NOMEM;
 229       p->nAlloc = nNew;
 230     }
 231
 232     /* Copy as much data as is available in the buffer into the start of
 233     ** p->aAlloc[].  */
 234     memcpy(p->aAlloc, &p->aBuffer[iBuf], nAvail);
 235     p->iReadOff += nAvail;
 236     nRem = nByte - nAvail;
 237
 238     /* The following loop copies up to p->nBuffer bytes per iteration into
 239     ** the p->aAlloc[] buffer.  */
 240     while( nRem>0 ){
 241       int rc;                     /* vdbeSorterIterRead() return code */
 242       int nCopy;                  /* Number of bytes to copy */
 243       u8 *aNext;                  /* Pointer to buffer to copy data from */
 244
 245       nCopy = nRem;
 246       if( nRem>p->nBuffer ) nCopy = p->nBuffer;
 247       rc = vdbeSorterIterRead(db, p, nCopy, &aNext);
 248       if( rc!=SQLITE_OK ) return rc;
 249       assert( aNext!=p->aAlloc );
 250       memcpy(&p->aAlloc[nByte - nRem], aNext, nCopy);
 251       nRem -= nCopy;
 252     }
 253
 254     *ppOut = p->aAlloc;
 255   }
 256
 257   return SQLITE_OK;
 258 }
 259
 260 /*
 261 ** Read a varint from the stream of data accessed by p. Set *pnOut to
 262 ** the value read.
 263 */
 264 static int vdbeSorterIterVarint(sqlite3 *db, VdbeSorterIter *p, u64 *pnOut){
 265   int iBuf;
 266
 267   iBuf = p->iReadOff % p->nBuffer;
 268   if( iBuf && (p->nBuffer-iBuf)>=9 ){
 269     p->iReadOff += sqlite3GetVarint(&p->aBuffer[iBuf], pnOut);
 270   }else{
 271     u8 aVarint[16], *a;
 272     int i = 0, rc;
 273     do{
 274       rc = vdbeSorterIterRead(db, p, 1, &a);
 275       if( rc ) return rc;
 276       aVarint[(i++)&0xf] = a[0];
 277     }while( (a[0]&0x80)!=0 );
 278     sqlite3GetVarint(aVarint, pnOut);
 279   }
 280
 281   return SQLITE_OK;
 282 }
 283
 284
 285 /*
 286 ** Advance iterator pIter to the next key in its PMA. Return SQLITE_OK if
 287 ** no error occurs, or an SQLite error code if one does.
 288 */
 289 static int vdbeSorterIterNext(
 290   sqlite3 *db,                    /* Database handle (for sqlite3DbMalloc() ) */
 291   VdbeSorterIter *pIter           /* Iterator to advance */
 292 ){
 293   int rc;                         /* Return Code */
 294   u64 nRec = 0;                   /* Size of record in bytes */
 295
 296   if( pIter->iReadOff>=pIter->iEof ){
 297     /* This is an EOF condition */
 298     vdbeSorterIterZero(db, pIter);
 299     return SQLITE_OK;
 300   }
 301
 302   rc = vdbeSorterIterVarint(db, pIter, &nRec);
 303   if( rc==SQLITE_OK ){
 304     pIter->nKey = (int)nRec;
 305     rc = vdbeSorterIterRead(db, pIter, (int)nRec, &pIter->aKey);
 306   }
 307
 308   return rc;
 309 }
 310
 311 /*
 312 ** Initialize iterator pIter to scan through the PMA stored in file pFile
 313 ** starting at offset iStart and ending at offset iEof-1. This function
 314 ** leaves the iterator pointing to the first key in the PMA (or EOF if the
 315 ** PMA is empty).
 316 */
 317 static int vdbeSorterIterInit(
 318   sqlite3 *db,                    /* Database handle */
 319   const VdbeSorter *pSorter,      /* Sorter object */
 320   i64 iStart,                     /* Start offset in pFile */
 321   VdbeSorterIter *pIter,          /* Iterator to populate */
 322   i64 *pnByte                     /* IN/OUT: Increment this value by PMA size */
 323 ){
 324   int rc = SQLITE_OK;
 325   int nBuf;
 326
 327   nBuf = sqlite3BtreeGetPageSize(db->aDb[0].pBt);
 328
 329   assert( pSorter->iWriteOff>iStart );
 330   assert( pIter->aAlloc==0 );
 331   assert( pIter->aBuffer==0 );
 332   pIter->pFile = pSorter->pTemp1;
 333   pIter->iReadOff = iStart;
 334   pIter->nAlloc = 128;
 335   pIter->aAlloc = (u8 *)sqlite3DbMallocRaw(db, pIter->nAlloc);
 336   pIter->nBuffer = nBuf;
 337   pIter->aBuffer = (u8 *)sqlite3DbMallocRaw(db, nBuf);
 338
 339   if( !pIter->aBuffer ){
 340     rc = SQLITE_NOMEM;
 341   }else{
 342     int iBuf;
 343
 344     iBuf = iStart % nBuf;
 345     if( iBuf ){
 346       int nRead = nBuf - iBuf;
 347       if( (iStart + nRead) > pSorter->iWriteOff ){
 348         nRead = (int)(pSorter->iWriteOff - iStart);
 349       }
 350       rc = sqlite3OsRead(
 351           pSorter->pTemp1, &pIter->aBuffer[iBuf], nRead, iStart
 352       );
 353       assert( rc!=SQLITE_IOERR_SHORT_READ );
 354     }
 355
 356     if( rc==SQLITE_OK ){
 357       u64 nByte;                       /* Size of PMA in bytes */
 358       pIter->iEof = pSorter->iWriteOff;
 359       rc = vdbeSorterIterVarint(db, pIter, &nByte);
 360       pIter->iEof = pIter->iReadOff + nByte;
 361       *pnByte += nByte;
 362     }
 363   }
 364
 365   if( rc==SQLITE_OK ){
 366     rc = vdbeSorterIterNext(db, pIter);
 367   }
 368   return rc;
 369 }
 370
 371
 372 /*
 373 ** Compare key1 (buffer pKey1, size nKey1 bytes) with key2 (buffer pKey2,
 374 ** size nKey2 bytes).  Argument pKeyInfo supplies the collation functions
 375 ** used by the comparison. If an error occurs, return an SQLite error code.
 376 ** Otherwise, return SQLITE_OK and set *pRes to a negative, zero or positive
 377 ** value, depending on whether key1 is smaller, equal to or larger than key2.
 378 **
 379 ** If the bOmitRowid argument is non-zero, assume both keys end in a rowid
 380 ** field. For the purposes of the comparison, ignore it. Also, if bOmitRowid
 381 ** is true and key1 contains even a single NULL value, it is considered to
 382 ** be less than key2. Even if key2 also contains NULL values.
 383 **
 384 ** If pKey2 is passed a NULL pointer, then it is assumed that the pCsr->aSpace
 385 ** has been allocated and contains an unpacked record that is used as key2.
 386 */
 387 static void vdbeSorterCompare(
 388   const VdbeCursor *pCsr,         /* Cursor object (for pKeyInfo) */
 389   int bOmitRowid,                 /* Ignore rowid field at end of keys */
 390   const void *pKey1, int nKey1,   /* Left side of comparison */
 391   const void *pKey2, int nKey2,   /* Right side of comparison */
 392   int *pRes                       /* OUT: Result of comparison */
 393 ){
 394   KeyInfo *pKeyInfo = pCsr->pKeyInfo;
 395   VdbeSorter *pSorter = pCsr->pSorter;
 396   UnpackedRecord *r2 = pSorter->pUnpacked;
 397   int i;
 398
 399   if( pKey2 ){
 400     sqlite3VdbeRecordUnpack(pKeyInfo, nKey2, pKey2, r2);
 401   }
 402
 403   if( bOmitRowid ){
 404     r2->nField = pKeyInfo->nField;
 405     assert( r2->nField>0 );
 406     for(i=0; i<r2->nField; i++){
 407       if( r2->aMem[i].flags & MEM_Null ){
 408         *pRes = -1;
 409         return;
 410       }
 411     }
 412     r2->flags |= UNPACKED_PREFIX_MATCH;
 413   }
 414
 415   *pRes = sqlite3VdbeRecordCompare(nKey1, pKey1, r2);
 416 }
 417
 418 /*
 419 ** This function is called to compare two iterator keys when merging
 420 ** multiple b-tree segments. Parameter iOut is the index of the aTree[]
 421 ** value to recalculate.
 422 */
 423 static int vdbeSorterDoCompare(const VdbeCursor *pCsr, int iOut){
 424   VdbeSorter *pSorter = pCsr->pSorter;
 425   int i1;
 426   int i2;
 427   int iRes;
 428   VdbeSorterIter *p1;
 429   VdbeSorterIter *p2;
 430
 431   assert( iOut<pSorter->nTree && iOut>0 );
 432
 433   if( iOut>=(pSorter->nTree/2) ){
 434     i1 = (iOut - pSorter->nTree/2) * 2;
 435     i2 = i1 + 1;
 436   }else{
 437     i1 = pSorter->aTree[iOut*2];
 438     i2 = pSorter->aTree[iOut*2+1];
 439   }
 440
 441   p1 = &pSorter->aIter[i1];
 442   p2 = &pSorter->aIter[i2];
 443
 444   if( p1->pFile==0 ){
 445     iRes = i2;
 446   }else if( p2->pFile==0 ){
 447     iRes = i1;
 448   }else{
 449     int res;
 450     assert( pCsr->pSorter->pUnpacked!=0 );  /* allocated in vdbeSorterMerge() */
 451     vdbeSorterCompare(
 452         pCsr, 0, p1->aKey, p1->nKey, p2->aKey, p2->nKey, &res
 453     );
 454     if( res<=0 ){
 455       iRes = i1;
 456     }else{
 457       iRes = i2;
 458     }
 459   }
 460
 461   pSorter->aTree[iOut] = iRes;
 462   return SQLITE_OK;
 463 }
 464
 465 /*
 466 ** Initialize the temporary index cursor just opened as a sorter cursor.
 467 */
 468 int sqlite3VdbeSorterInit(sqlite3 *db, VdbeCursor *pCsr){
 469   int pgsz;                       /* Page size of main database */
 470   int mxCache;                    /* Cache size */
 471   VdbeSorter *pSorter;            /* The new sorter */
 472   char *d;                        /* Dummy */
 473
 474   assert( pCsr->pKeyInfo && pCsr->pBt==0 );
 475   pCsr->pSorter = pSorter = sqlite3DbMallocZero(db, sizeof(VdbeSorter));
 476   if( pSorter==0 ){
 477     return SQLITE_NOMEM;
 478   }
 479
 480   pSorter->pUnpacked = sqlite3VdbeAllocUnpackedRecord(pCsr->pKeyInfo, 0, 0, &d);
 481   if( pSorter->pUnpacked==0 ) return SQLITE_NOMEM;
 482   assert( pSorter->pUnpacked==(UnpackedRecord *)d );
 483
 484   if( !sqlite3TempInMemory(db) ){
 485     pgsz = sqlite3BtreeGetPageSize(db->aDb[0].pBt);
 486     pSorter->mnPmaSize = SORTER_MIN_WORKING * pgsz;
 487     mxCache = db->aDb[0].pSchema->cache_size;
 488     if( mxCache<SORTER_MIN_WORKING ) mxCache = SORTER_MIN_WORKING;
 489     pSorter->mxPmaSize = mxCache * pgsz;
 490   }
 491
 492   return SQLITE_OK;
 493 }
 494
 495 /*
 496 ** Free the list of sorted records starting at pRecord.
 497 */
 498 static void vdbeSorterRecordFree(sqlite3 *db, SorterRecord *pRecord){
 499   SorterRecord *p;
 500   SorterRecord *pNext;
 501   for(p=pRecord; p; p=pNext){
 502     pNext = p->pNext;
 503     sqlite3DbFree(db, p);
 504   }
 505 }
 506
 507 /*
 508 ** Free any cursor components allocated by sqlite3VdbeSorterXXX routines.
 509 */
 510 void sqlite3VdbeSorterClose(sqlite3 *db, VdbeCursor *pCsr){
 511   VdbeSorter *pSorter = pCsr->pSorter;
 512   if( pSorter ){
 513     if( pSorter->aIter ){
 514       int i;
 515       for(i=0; i<pSorter->nTree; i++){
 516         vdbeSorterIterZero(db, &pSorter->aIter[i]);
 517       }
 518       sqlite3DbFree(db, pSorter->aIter);
 519     }
 520     if( pSorter->pTemp1 ){
 521       sqlite3OsCloseFree(pSorter->pTemp1);
 522     }
 523     vdbeSorterRecordFree(db, pSorter->pRecord);
 524     sqlite3DbFree(db, pSorter->pUnpacked);
 525     sqlite3DbFree(db, pSorter);
 526     pCsr->pSorter = 0;
 527   }
 528 }
 529
 530 /*
 531 ** Allocate space for a file-handle and open a temporary file. If successful,
 532 ** set *ppFile to point to the malloc'd file-handle and return SQLITE_OK.
 533 ** Otherwise, set *ppFile to 0 and return an SQLite error code.
 534 */
 535 static int vdbeSorterOpenTempFile(sqlite3 *db, sqlite3_file **ppFile){
 536   int dummy;
 537   return sqlite3OsOpenMalloc(db->pVfs, 0, ppFile,
 538       SQLITE_OPEN_TEMP_JOURNAL |
 539       SQLITE_OPEN_READWRITE    | SQLITE_OPEN_CREATE |
 540       SQLITE_OPEN_EXCLUSIVE    | SQLITE_OPEN_DELETEONCLOSE, &dummy
 541   );
 542 }
 543
 544 /*
 545 ** Merge the two sorted lists p1 and p2 into a single list.
 546 ** Set *ppOut to the head of the new list.
 547 */
 548 static void vdbeSorterMerge(
 549   const VdbeCursor *pCsr,         /* For pKeyInfo */
 550   SorterRecord *p1,               /* First list to merge */
 551   SorterRecord *p2,               /* Second list to merge */
 552   SorterRecord **ppOut            /* OUT: Head of merged list */
 553 ){
 554   SorterRecord *pFinal = 0;
 555   SorterRecord **pp = &pFinal;
 556   void *pVal2 = p2 ? p2->pVal : 0;
 557
 558   while( p1 && p2 ){
 559     int res;
 560     vdbeSorterCompare(pCsr, 0, p1->pVal, p1->nVal, pVal2, p2->nVal, &res);
 561     if( res<=0 ){
 562       *pp = p1;
 563       pp = &p1->pNext;
 564       p1 = p1->pNext;
 565       pVal2 = 0;
 566     }else{
 567       *pp = p2;
 568        pp = &p2->pNext;
 569       p2 = p2->pNext;
 570       if( p2==0 ) break;
 571       pVal2 = p2->pVal;
 572     }
 573   }
 574   *pp = p1 ? p1 : p2;
 575   *ppOut = pFinal;
 576 }
 577
 578 /*
 579 ** Sort the linked list of records headed at pCsr->pRecord. Return SQLITE_OK
 580 ** if successful, or an SQLite error code (i.e. SQLITE_NOMEM) if an error
 581 ** occurs.
 582 */
 583 static int vdbeSorterSort(const VdbeCursor *pCsr){
 584   int i;
 585   SorterRecord **aSlot;
 586   SorterRecord *p;
 587   VdbeSorter *pSorter = pCsr->pSorter;
 588
 589   aSlot = (SorterRecord **)sqlite3MallocZero(64 * sizeof(SorterRecord *));
 590   if( !aSlot ){
 591     return SQLITE_NOMEM;
 592   }
 593
 594   p = pSorter->pRecord;
 595   while( p ){
 596     SorterRecord *pNext = p->pNext;
 597     p->pNext = 0;
 598     for(i=0; aSlot[i]; i++){
 599       vdbeSorterMerge(pCsr, p, aSlot[i], &p);
 600       aSlot[i] = 0;
 601     }
 602     aSlot[i] = p;
 603     p = pNext;
 604   }
 605
 606   p = 0;
 607   for(i=0; i<64; i++){
 608     vdbeSorterMerge(pCsr, p, aSlot[i], &p);
 609   }
 610   pSorter->pRecord = p;
 611
 612   sqlite3_free(aSlot);
 613   return SQLITE_OK;
 614 }
 615
 616 /*
 617 ** Initialize a file-writer object.
 618 */
 619 static void fileWriterInit(
 620   sqlite3 *db,                    /* Database (for malloc) */
 621   sqlite3_file *pFile,            /* File to write to */
 622   FileWriter *p,                  /* Object to populate */
 623   i64 iStart                      /* Offset of pFile to begin writing at */
 624 ){
 625   int nBuf = sqlite3BtreeGetPageSize(db->aDb[0].pBt);
 626
 627   memset(p, 0, sizeof(FileWriter));
 628   p->aBuffer = (u8 *)sqlite3DbMallocRaw(db, nBuf);
 629   if( !p->aBuffer ){
 630     p->eFWErr = SQLITE_NOMEM;
 631   }else{
 632     p->iBufEnd = p->iBufStart = (iStart % nBuf);
 633     p->iWriteOff = iStart - p->iBufStart;
 634     p->nBuffer = nBuf;
 635     p->pFile = pFile;
 636   }
 637 }
 638
 639 /*
 640 ** Write nData bytes of data to the file-write object. Return SQLITE_OK
 641 ** if successful, or an SQLite error code if an error occurs.
 642 */
 643 static void fileWriterWrite(FileWriter *p, u8 *pData, int nData){
 644   int nRem = nData;
 645   while( nRem>0 && p->eFWErr==0 ){
 646     int nCopy = nRem;
 647     if( nCopy>(p->nBuffer - p->iBufEnd) ){
 648       nCopy = p->nBuffer - p->iBufEnd;
 649     }
 650
 651     memcpy(&p->aBuffer[p->iBufEnd], &pData[nData-nRem], nCopy);
 652     p->iBufEnd += nCopy;
 653     if( p->iBufEnd==p->nBuffer ){
 654       p->eFWErr = sqlite3OsWrite(p->pFile,
 655           &p->aBuffer[p->iBufStart], p->iBufEnd - p->iBufStart,
 656           p->iWriteOff + p->iBufStart
 657       );
 658       p->iBufStart = p->iBufEnd = 0;
 659       p->iWriteOff += p->nBuffer;
 660     }
 661     assert( p->iBufEnd<p->nBuffer );
 662
 663     nRem -= nCopy;
 664   }
 665 }
 666
 667 /*
 668 ** Flush any buffered data to disk and clean up the file-writer object.
 669 ** The results of using the file-writer after this call are undefined.
 670 ** Return SQLITE_OK if flushing the buffered data succeeds or is not
 671 ** required. Otherwise, return an SQLite error code.
 672 **
 673 ** Before returning, set *piEof to the offset immediately following the
 674 ** last byte written to the file.
 675 */
 676 static int fileWriterFinish(sqlite3 *db, FileWriter *p, i64 *piEof){
 677   int rc;
 678   if( p->eFWErr==0 && ALWAYS(p->aBuffer) && p->iBufEnd>p->iBufStart ){
 679     p->eFWErr = sqlite3OsWrite(p->pFile,
 680         &p->aBuffer[p->iBufStart], p->iBufEnd - p->iBufStart,
 681         p->iWriteOff + p->iBufStart
 682     );
 683   }
 684   *piEof = (p->iWriteOff + p->iBufEnd);
 685   sqlite3DbFree(db, p->aBuffer);
 686   rc = p->eFWErr;
 687   memset(p, 0, sizeof(FileWriter));
 688   return rc;
 689 }
 690
 691 /*
 692 ** Write value iVal encoded as a varint to the file-write object. Return
 693 ** SQLITE_OK if successful, or an SQLite error code if an error occurs.
 694 */
 695 static void fileWriterWriteVarint(FileWriter *p, u64 iVal){
 696   int nByte;
 697   u8 aByte[10];
 698   nByte = sqlite3PutVarint(aByte, iVal);
 699   fileWriterWrite(p, aByte, nByte);
 700 }
 701
 702 /*
 703 ** Write the current contents of the in-memory linked-list to a PMA. Return
 704 ** SQLITE_OK if successful, or an SQLite error code otherwise.
 705 **
 706 ** The format of a PMA is:
 707 **
 708 **     * A varint. This varint contains the total number of bytes of content
 709 **       in the PMA (not including the varint itself).
 710 **
 711 **     * One or more records packed end-to-end in order of ascending keys.
 712 **       Each record consists of a varint followed by a blob of data (the
 713 **       key). The varint is the number of bytes in the blob of data.
 714 */
 715 static int vdbeSorterListToPMA(sqlite3 *db, const VdbeCursor *pCsr){
 716   int rc = SQLITE_OK;             /* Return code */
 717   VdbeSorter *pSorter = pCsr->pSorter;
 718   FileWriter writer;
 719
 720   memset(&writer, 0, sizeof(FileWriter));
 721
 722   if( pSorter->nInMemory==0 ){
 723     assert( pSorter->pRecord==0 );
 724     return rc;
 725   }
 726
 727   rc = vdbeSorterSort(pCsr);
 728
 729   /* If the first temporary PMA file has not been opened, open it now. */
 730   if( rc==SQLITE_OK && pSorter->pTemp1==0 ){
 731     rc = vdbeSorterOpenTempFile(db, &pSorter->pTemp1);
 732     assert( rc!=SQLITE_OK || pSorter->pTemp1 );
 733     assert( pSorter->iWriteOff==0 );
 734     assert( pSorter->nPMA==0 );
 735   }
 736
 737   if( rc==SQLITE_OK ){
 738     SorterRecord *p;
 739     SorterRecord *pNext = 0;
 740
 741     fileWriterInit(db, pSorter->pTemp1, &writer, pSorter->iWriteOff);
 742     pSorter->nPMA++;
 743     fileWriterWriteVarint(&writer, pSorter->nInMemory);
 744     for(p=pSorter->pRecord; p; p=pNext){
 745       pNext = p->pNext;
 746       fileWriterWriteVarint(&writer, p->nVal);
 747       fileWriterWrite(&writer, p->pVal, p->nVal);
 748       sqlite3DbFree(db, p);
 749     }
 750     pSorter->pRecord = p;
 751     rc = fileWriterFinish(db, &writer, &pSorter->iWriteOff);
 752   }
 753
 754   return rc;
 755 }
 756
 757 /*
 758 ** Add a record to the sorter.
 759 */
 760 int sqlite3VdbeSorterWrite(
 761   sqlite3 *db,                    /* Database handle */
 762   const VdbeCursor *pCsr,               /* Sorter cursor */
 763   Mem *pVal                       /* Memory cell containing record */
 764 ){
 765   VdbeSorter *pSorter = pCsr->pSorter;
 766   int rc = SQLITE_OK;             /* Return Code */
 767   SorterRecord *pNew;             /* New list element */
 768
 769   assert( pSorter );
 770   pSorter->nInMemory += sqlite3VarintLen(pVal->n) + pVal->n;
 771
 772   pNew = (SorterRecord *)sqlite3DbMallocRaw(db, pVal->n + sizeof(SorterRecord));
 773   if( pNew==0 ){
 774     rc = SQLITE_NOMEM;
 775   }else{
 776     pNew->pVal = (void *)&pNew[1];
 777     memcpy(pNew->pVal, pVal->z, pVal->n);
 778     pNew->nVal = pVal->n;
 779     pNew->pNext = pSorter->pRecord;
 780     pSorter->pRecord = pNew;
 781   }
 782
 783   /* See if the contents of the sorter should now be written out. They
 784   ** are written out when either of the following are true:
 785   **
 786   **   * The total memory allocated for the in-memory list is greater
 787   **     than (page-size * cache-size), or
 788   **
 789   **   * The total memory allocated for the in-memory list is greater
 790   **     than (page-size * 10) and sqlite3HeapNearlyFull() returns true.
 791   */
 792   if( rc==SQLITE_OK && pSorter->mxPmaSize>0 && (
 793         (pSorter->nInMemory>pSorter->mxPmaSize)
 794      || (pSorter->nInMemory>pSorter->mnPmaSize && sqlite3HeapNearlyFull())
 795   )){
 796 #ifdef SQLITE_DEBUG
 797     i64 nExpect = pSorter->iWriteOff
 798                 + sqlite3VarintLen(pSorter->nInMemory)
 799                 + pSorter->nInMemory;
 800 #endif
 801     rc = vdbeSorterListToPMA(db, pCsr);
 802     pSorter->nInMemory = 0;
 803     assert( rc!=SQLITE_OK || (nExpect==pSorter->iWriteOff) );
 804   }
 805
 806   return rc;
 807 }
 808
 809 /*
 810 ** Helper function for sqlite3VdbeSorterRewind().
 811 */
 812 static int vdbeSorterInitMerge(
 813   sqlite3 *db,                    /* Database handle */
 814   const VdbeCursor *pCsr,         /* Cursor handle for this sorter */
 815   i64 *pnByte                     /* Sum of bytes in all opened PMAs */
 816 ){
 817   VdbeSorter *pSorter = pCsr->pSorter;
 818   int rc = SQLITE_OK;             /* Return code */
 819   int i;                          /* Used to iterator through aIter[] */
 820   i64 nByte = 0;                  /* Total bytes in all opened PMAs */
 821
 822   /* Initialize the iterators. */
 823   for(i=0; i<SORTER_MAX_MERGE_COUNT; i++){
 824     VdbeSorterIter *pIter = &pSorter->aIter[i];
 825     rc = vdbeSorterIterInit(db, pSorter, pSorter->iReadOff, pIter, &nByte);
 826     pSorter->iReadOff = pIter->iEof;
 827     assert( rc!=SQLITE_OK || pSorter->iReadOff<=pSorter->iWriteOff );
 828     if( rc!=SQLITE_OK || pSorter->iReadOff>=pSorter->iWriteOff ) break;
 829   }
 830
 831   /* Initialize the aTree[] array. */
 832   for(i=pSorter->nTree-1; rc==SQLITE_OK && i>0; i--){
 833     rc = vdbeSorterDoCompare(pCsr, i);
 834   }
 835
 836   *pnByte = nByte;
 837   return rc;
 838 }
 839
 840 /*
 841 ** Once the sorter has been populated, this function is called to prepare
 842 ** for iterating through its contents in sorted order.
 843 */
 844 int sqlite3VdbeSorterRewind(sqlite3 *db, const VdbeCursor *pCsr, int *pbEof){
 845   VdbeSorter *pSorter = pCsr->pSorter;
 846   int rc;                         /* Return code */
 847   sqlite3_file *pTemp2 = 0;       /* Second temp file to use */
 848   i64 iWrite2 = 0;                /* Write offset for pTemp2 */
 849   int nIter;                      /* Number of iterators used */
 850   int nByte;                      /* Bytes of space required for aIter/aTree */
 851   int N = 2;                      /* Power of 2 >= nIter */
 852
 853   assert( pSorter );
 854
 855   /* If no data has been written to disk, then do not do so now. Instead,
 856   ** sort the VdbeSorter.pRecord list. The vdbe layer will read data directly
 857   ** from the in-memory list.  */
 858   if( pSorter->nPMA==0 ){
 859     *pbEof = !pSorter->pRecord;
 860     assert( pSorter->aTree==0 );
 861     return vdbeSorterSort(pCsr);
 862   }
 863
 864   /* Write the current in-memory list to a PMA. */
 865   rc = vdbeSorterListToPMA(db, pCsr);
 866   if( rc!=SQLITE_OK ) return rc;
 867
 868   /* Allocate space for aIter[] and aTree[]. */
 869   nIter = pSorter->nPMA;
 870   if( nIter>SORTER_MAX_MERGE_COUNT ) nIter = SORTER_MAX_MERGE_COUNT;
 871   assert( nIter>0 );
 872   while( N<nIter ) N += N;
 873   nByte = N * (sizeof(int) + sizeof(VdbeSorterIter));
 874   pSorter->aIter = (VdbeSorterIter *)sqlite3DbMallocZero(db, nByte);
 875   if( !pSorter->aIter ) return SQLITE_NOMEM;
 876   pSorter->aTree = (int *)&pSorter->aIter[N];
 877   pSorter->nTree = N;
 878
 879   do {
 880     int iNew;                     /* Index of new, merged, PMA */
 881
 882     for(iNew=0;
 883         rc==SQLITE_OK && iNew*SORTER_MAX_MERGE_COUNT<pSorter->nPMA;
 884         iNew++
 885     ){
 886       int rc2;                    /* Return code from fileWriterFinish() */
 887       FileWriter writer;          /* Object used to write to disk */
 888       i64 nWrite;                 /* Number of bytes in new PMA */
 889
 890       memset(&writer, 0, sizeof(FileWriter));
 891
 892       /* If there are SORTER_MAX_MERGE_COUNT or less PMAs in file pTemp1,
 893       ** initialize an iterator for each of them and break out of the loop.
 894       ** These iterators will be incrementally merged as the VDBE layer calls
 895       ** sqlite3VdbeSorterNext().
 896       **
 897       ** Otherwise, if pTemp1 contains more than SORTER_MAX_MERGE_COUNT PMAs,
 898       ** initialize interators for SORTER_MAX_MERGE_COUNT of them. These PMAs
 899       ** are merged into a single PMA that is written to file pTemp2.
 900       */
 901       rc = vdbeSorterInitMerge(db, pCsr, &nWrite);
 902       assert( rc!=SQLITE_OK || pSorter->aIter[ pSorter->aTree[1] ].pFile );
 903       if( rc!=SQLITE_OK || pSorter->nPMA<=SORTER_MAX_MERGE_COUNT ){
 904         break;
 905       }
 906
 907       /* Open the second temp file, if it is not already open. */
 908       if( pTemp2==0 ){
 909         assert( iWrite2==0 );
 910         rc = vdbeSorterOpenTempFile(db, &pTemp2);
 911       }
 912
 913       if( rc==SQLITE_OK ){
 914         int bEof = 0;
 915         fileWriterInit(db, pTemp2, &writer, iWrite2);
 916         fileWriterWriteVarint(&writer, nWrite);
 917         while( rc==SQLITE_OK && bEof==0 ){
 918           VdbeSorterIter *pIter = &pSorter->aIter[ pSorter->aTree[1] ];
 919           assert( pIter->pFile );
 920
 921           fileWriterWriteVarint(&writer, pIter->nKey);
 922           fileWriterWrite(&writer, pIter->aKey, pIter->nKey);
 923           rc = sqlite3VdbeSorterNext(db, pCsr, &bEof);
 924         }
 925         rc2 = fileWriterFinish(db, &writer, &iWrite2);
 926         if( rc==SQLITE_OK ) rc = rc2;
 927       }
 928     }
 929
 930     if( pSorter->nPMA<=SORTER_MAX_MERGE_COUNT ){
 931       break;
 932     }else{
 933       sqlite3_file *pTmp = pSorter->pTemp1;
 934       pSorter->nPMA = iNew;
 935       pSorter->pTemp1 = pTemp2;
 936       pTemp2 = pTmp;
 937       pSorter->iWriteOff = iWrite2;
 938       pSorter->iReadOff = 0;
 939       iWrite2 = 0;
 940     }
 941   }while( rc==SQLITE_OK );
 942
 943   if( pTemp2 ){
 944     sqlite3OsCloseFree(pTemp2);
 945   }
 946   *pbEof = (pSorter->aIter[pSorter->aTree[1]].pFile==0);
 947   return rc;
 948 }
 949
 950 /*
 951 ** Advance to the next element in the sorter.
 952 */
 953 int sqlite3VdbeSorterNext(sqlite3 *db, const VdbeCursor *pCsr, int *pbEof){
 954   VdbeSorter *pSorter = pCsr->pSorter;
 955   int rc;                         /* Return code */
 956
 957   if( pSorter->aTree ){
 958     int iPrev = pSorter->aTree[1];/* Index of iterator to advance */
 959     int i;                        /* Index of aTree[] to recalculate */
 960
 961     rc = vdbeSorterIterNext(db, &pSorter->aIter[iPrev]);
 962     for(i=(pSorter->nTree+iPrev)/2; rc==SQLITE_OK && i>0; i=i/2){
 963       rc = vdbeSorterDoCompare(pCsr, i);
 964     }
 965
 966     *pbEof = (pSorter->aIter[pSorter->aTree[1]].pFile==0);
 967   }else{
 968     SorterRecord *pFree = pSorter->pRecord;
 969     pSorter->pRecord = pFree->pNext;
 970     pFree->pNext = 0;
 971     vdbeSorterRecordFree(db, pFree);
 972     *pbEof = !pSorter->pRecord;
 973     rc = SQLITE_OK;
 974   }
 975   return rc;
 976 }
 977
 978 /*
 979 ** Return a pointer to a buffer owned by the sorter that contains the
 980 ** current key.
 981 */
 982 static void *vdbeSorterRowkey(
 983   const VdbeSorter *pSorter,      /* Sorter object */
 984   int *pnKey                      /* OUT: Size of current key in bytes */
 985 ){
 986   void *pKey;
 987   if( pSorter->aTree ){
 988     VdbeSorterIter *pIter;
 989     pIter = &pSorter->aIter[ pSorter->aTree[1] ];
 990     *pnKey = pIter->nKey;
 991     pKey = pIter->aKey;
 992   }else{
 993     *pnKey = pSorter->pRecord->nVal;
 994     pKey = pSorter->pRecord->pVal;
 995   }
 996   return pKey;
 997 }
 998
 999 /*
1000 ** Copy the current sorter key into the memory cell pOut.
1001 */
1002 int sqlite3VdbeSorterRowkey(const VdbeCursor *pCsr, Mem *pOut){
1003   VdbeSorter *pSorter = pCsr->pSorter;
1004   void *pKey; int nKey;           /* Sorter key to copy into pOut */
1005
1006   pKey = vdbeSorterRowkey(pSorter, &nKey);
1007   if( sqlite3VdbeMemGrow(pOut, nKey, 0) ){
1008     return SQLITE_NOMEM;
1009   }
1010   pOut->n = nKey;
1011   MemSetTypeFlag(pOut, MEM_Blob);
1012   memcpy(pOut->z, pKey, nKey);
1013
1014   return SQLITE_OK;
1015 }
1016
1017 /*
1018 ** Compare the key in memory cell pVal with the key that the sorter cursor
1019 ** passed as the first argument currently points to. For the purposes of
1020 ** the comparison, ignore the rowid field at the end of each record.
1021 **
1022 ** If an error occurs, return an SQLite error code (i.e. SQLITE_NOMEM).
1023 ** Otherwise, set *pRes to a negative, zero or positive value if the
1024 ** key in pVal is smaller than, equal to or larger than the current sorter
1025 ** key.
1026 */
1027 int sqlite3VdbeSorterCompare(
1028   const VdbeCursor *pCsr,         /* Sorter cursor */
1029   Mem *pVal,                      /* Value to compare to current sorter key */
1030   int *pRes                       /* OUT: Result of comparison */
1031 ){
1032   VdbeSorter *pSorter = pCsr->pSorter;
1033   void *pKey; int nKey;           /* Sorter key to compare pVal with */
1034
1035   pKey = vdbeSorterRowkey(pSorter, &nKey);
1036   vdbeSorterCompare(pCsr, 1, pVal->z, pVal->n, pKey, nKey, pRes);
1037   return SQLITE_OK;
1038 }