Annotation of embedaddon/sqlite3/src/vdbesort.c, revision 1.1
1.1 ! misho 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: #ifndef SQLITE_OMIT_MERGE_SORT
! 22:
! 23: typedef struct VdbeSorterIter VdbeSorterIter;
! 24: typedef struct SorterRecord SorterRecord;
! 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 preceed 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: int nInMemory; /* Current size of pRecord list as PMA */
! 97: int nTree; /* Used size of aTree/aIter (power of 2) */
! 98: VdbeSorterIter *aIter; /* Array of iterators to merge */
! 99: int *aTree; /* Current state of incremental merge */
! 100: i64 iWriteOff; /* Current write offset within file pTemp1 */
! 101: i64 iReadOff; /* Current read offset within file pTemp1 */
! 102: sqlite3_file *pTemp1; /* PMA file 1 */
! 103: int nPMA; /* Number of PMAs stored in pTemp1 */
! 104: SorterRecord *pRecord; /* Head of in-memory record list */
! 105: int mnPmaSize; /* Minimum PMA size, in bytes */
! 106: int mxPmaSize; /* Maximum PMA size, in bytes. 0==no limit */
! 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: sqlite3_file *pFile; /* File iterator is reading from */
! 118: int nAlloc; /* Bytes of space at aAlloc */
! 119: u8 *aAlloc; /* Allocated space */
! 120: int nKey; /* Number of bytes in key */
! 121: u8 *aKey; /* Pointer to current key */
! 122: };
! 123:
! 124: /*
! 125: ** A structure to store a single record. All in-memory records are connected
! 126: ** together into a linked list headed at VdbeSorter.pRecord using the
! 127: ** SorterRecord.pNext pointer.
! 128: */
! 129: struct SorterRecord {
! 130: void *pVal;
! 131: int nVal;
! 132: SorterRecord *pNext;
! 133: };
! 134:
! 135: /* Minimum allowable value for the VdbeSorter.nWorking variable */
! 136: #define SORTER_MIN_WORKING 10
! 137:
! 138: /* Maximum number of segments to merge in a single pass. */
! 139: #define SORTER_MAX_MERGE_COUNT 16
! 140:
! 141: /*
! 142: ** Free all memory belonging to the VdbeSorterIter object passed as the second
! 143: ** argument. All structure fields are set to zero before returning.
! 144: */
! 145: static void vdbeSorterIterZero(sqlite3 *db, VdbeSorterIter *pIter){
! 146: sqlite3DbFree(db, pIter->aAlloc);
! 147: memset(pIter, 0, sizeof(VdbeSorterIter));
! 148: }
! 149:
! 150: /*
! 151: ** Advance iterator pIter to the next key in its PMA. Return SQLITE_OK if
! 152: ** no error occurs, or an SQLite error code if one does.
! 153: */
! 154: static int vdbeSorterIterNext(
! 155: sqlite3 *db, /* Database handle (for sqlite3DbMalloc() ) */
! 156: VdbeSorterIter *pIter /* Iterator to advance */
! 157: ){
! 158: int rc; /* Return Code */
! 159: int nRead; /* Number of bytes read */
! 160: int nRec = 0; /* Size of record in bytes */
! 161: int iOff = 0; /* Size of serialized size varint in bytes */
! 162:
! 163: assert( pIter->iEof>=pIter->iReadOff );
! 164: if( pIter->iEof-pIter->iReadOff>5 ){
! 165: nRead = 5;
! 166: }else{
! 167: nRead = (int)(pIter->iEof - pIter->iReadOff);
! 168: }
! 169: if( nRead<=0 ){
! 170: /* This is an EOF condition */
! 171: vdbeSorterIterZero(db, pIter);
! 172: return SQLITE_OK;
! 173: }
! 174:
! 175: rc = sqlite3OsRead(pIter->pFile, pIter->aAlloc, nRead, pIter->iReadOff);
! 176: if( rc==SQLITE_OK ){
! 177: iOff = getVarint32(pIter->aAlloc, nRec);
! 178: if( (iOff+nRec)>nRead ){
! 179: int nRead2; /* Number of extra bytes to read */
! 180: if( (iOff+nRec)>pIter->nAlloc ){
! 181: int nNew = pIter->nAlloc*2;
! 182: while( (iOff+nRec)>nNew ) nNew = nNew*2;
! 183: pIter->aAlloc = sqlite3DbReallocOrFree(db, pIter->aAlloc, nNew);
! 184: if( !pIter->aAlloc ) return SQLITE_NOMEM;
! 185: pIter->nAlloc = nNew;
! 186: }
! 187:
! 188: nRead2 = iOff + nRec - nRead;
! 189: rc = sqlite3OsRead(
! 190: pIter->pFile, &pIter->aAlloc[nRead], nRead2, pIter->iReadOff+nRead
! 191: );
! 192: }
! 193: }
! 194:
! 195: assert( rc!=SQLITE_OK || nRec>0 );
! 196: pIter->iReadOff += iOff+nRec;
! 197: pIter->nKey = nRec;
! 198: pIter->aKey = &pIter->aAlloc[iOff];
! 199: return rc;
! 200: }
! 201:
! 202: /*
! 203: ** Write a single varint, value iVal, to file-descriptor pFile. Return
! 204: ** SQLITE_OK if successful, or an SQLite error code if some error occurs.
! 205: **
! 206: ** The value of *piOffset when this function is called is used as the byte
! 207: ** offset in file pFile to write to. Before returning, *piOffset is
! 208: ** incremented by the number of bytes written.
! 209: */
! 210: static int vdbeSorterWriteVarint(
! 211: sqlite3_file *pFile, /* File to write to */
! 212: i64 iVal, /* Value to write as a varint */
! 213: i64 *piOffset /* IN/OUT: Write offset in file pFile */
! 214: ){
! 215: u8 aVarint[9]; /* Buffer large enough for a varint */
! 216: int nVarint; /* Number of used bytes in varint */
! 217: int rc; /* Result of write() call */
! 218:
! 219: nVarint = sqlite3PutVarint(aVarint, iVal);
! 220: rc = sqlite3OsWrite(pFile, aVarint, nVarint, *piOffset);
! 221: *piOffset += nVarint;
! 222:
! 223: return rc;
! 224: }
! 225:
! 226: /*
! 227: ** Read a single varint from file-descriptor pFile. Return SQLITE_OK if
! 228: ** successful, or an SQLite error code if some error occurs.
! 229: **
! 230: ** The value of *piOffset when this function is called is used as the
! 231: ** byte offset in file pFile from whence to read the varint. If successful
! 232: ** (i.e. if no IO error occurs), then *piOffset is set to the offset of
! 233: ** the first byte past the end of the varint before returning. *piVal is
! 234: ** set to the integer value read. If an error occurs, the final values of
! 235: ** both *piOffset and *piVal are undefined.
! 236: */
! 237: static int vdbeSorterReadVarint(
! 238: sqlite3_file *pFile, /* File to read from */
! 239: i64 *piOffset, /* IN/OUT: Read offset in pFile */
! 240: i64 *piVal /* OUT: Value read from file */
! 241: ){
! 242: u8 aVarint[9]; /* Buffer large enough for a varint */
! 243: i64 iOff = *piOffset; /* Offset in file to read from */
! 244: int rc; /* Return code */
! 245:
! 246: rc = sqlite3OsRead(pFile, aVarint, 9, iOff);
! 247: if( rc==SQLITE_OK ){
! 248: *piOffset += getVarint(aVarint, (u64 *)piVal);
! 249: }
! 250:
! 251: return rc;
! 252: }
! 253:
! 254: /*
! 255: ** Initialize iterator pIter to scan through the PMA stored in file pFile
! 256: ** starting at offset iStart and ending at offset iEof-1. This function
! 257: ** leaves the iterator pointing to the first key in the PMA (or EOF if the
! 258: ** PMA is empty).
! 259: */
! 260: static int vdbeSorterIterInit(
! 261: sqlite3 *db, /* Database handle */
! 262: VdbeSorter *pSorter, /* Sorter object */
! 263: i64 iStart, /* Start offset in pFile */
! 264: VdbeSorterIter *pIter, /* Iterator to populate */
! 265: i64 *pnByte /* IN/OUT: Increment this value by PMA size */
! 266: ){
! 267: int rc;
! 268:
! 269: assert( pSorter->iWriteOff>iStart );
! 270: assert( pIter->aAlloc==0 );
! 271: pIter->pFile = pSorter->pTemp1;
! 272: pIter->iReadOff = iStart;
! 273: pIter->nAlloc = 128;
! 274: pIter->aAlloc = (u8 *)sqlite3DbMallocRaw(db, pIter->nAlloc);
! 275: if( !pIter->aAlloc ){
! 276: rc = SQLITE_NOMEM;
! 277: }else{
! 278: i64 nByte; /* Total size of PMA in bytes */
! 279: rc = vdbeSorterReadVarint(pSorter->pTemp1, &pIter->iReadOff, &nByte);
! 280: *pnByte += nByte;
! 281: pIter->iEof = pIter->iReadOff + nByte;
! 282: }
! 283: if( rc==SQLITE_OK ){
! 284: rc = vdbeSorterIterNext(db, pIter);
! 285: }
! 286: return rc;
! 287: }
! 288:
! 289:
! 290: /*
! 291: ** Compare key1 (buffer pKey1, size nKey1 bytes) with key2 (buffer pKey2,
! 292: ** size nKey2 bytes). Argument pKeyInfo supplies the collation functions
! 293: ** used by the comparison. If an error occurs, return an SQLite error code.
! 294: ** Otherwise, return SQLITE_OK and set *pRes to a negative, zero or positive
! 295: ** value, depending on whether key1 is smaller, equal to or larger than key2.
! 296: **
! 297: ** If the bOmitRowid argument is non-zero, assume both keys end in a rowid
! 298: ** field. For the purposes of the comparison, ignore it. Also, if bOmitRowid
! 299: ** is true and key1 contains even a single NULL value, it is considered to
! 300: ** be less than key2. Even if key2 also contains NULL values.
! 301: **
! 302: ** If pKey2 is passed a NULL pointer, then it is assumed that the pCsr->aSpace
! 303: ** has been allocated and contains an unpacked record that is used as key2.
! 304: */
! 305: static void vdbeSorterCompare(
! 306: VdbeCursor *pCsr, /* Cursor object (for pKeyInfo) */
! 307: int bOmitRowid, /* Ignore rowid field at end of keys */
! 308: void *pKey1, int nKey1, /* Left side of comparison */
! 309: void *pKey2, int nKey2, /* Right side of comparison */
! 310: int *pRes /* OUT: Result of comparison */
! 311: ){
! 312: KeyInfo *pKeyInfo = pCsr->pKeyInfo;
! 313: VdbeSorter *pSorter = pCsr->pSorter;
! 314: UnpackedRecord *r2 = pSorter->pUnpacked;
! 315: int i;
! 316:
! 317: if( pKey2 ){
! 318: sqlite3VdbeRecordUnpack(pKeyInfo, nKey2, pKey2, r2);
! 319: }
! 320:
! 321: if( bOmitRowid ){
! 322: r2->nField = pKeyInfo->nField;
! 323: assert( r2->nField>0 );
! 324: for(i=0; i<r2->nField; i++){
! 325: if( r2->aMem[i].flags & MEM_Null ){
! 326: *pRes = -1;
! 327: return;
! 328: }
! 329: }
! 330: r2->flags |= UNPACKED_PREFIX_MATCH;
! 331: }
! 332:
! 333: *pRes = sqlite3VdbeRecordCompare(nKey1, pKey1, r2);
! 334: }
! 335:
! 336: /*
! 337: ** This function is called to compare two iterator keys when merging
! 338: ** multiple b-tree segments. Parameter iOut is the index of the aTree[]
! 339: ** value to recalculate.
! 340: */
! 341: static int vdbeSorterDoCompare(VdbeCursor *pCsr, int iOut){
! 342: VdbeSorter *pSorter = pCsr->pSorter;
! 343: int i1;
! 344: int i2;
! 345: int iRes;
! 346: VdbeSorterIter *p1;
! 347: VdbeSorterIter *p2;
! 348:
! 349: assert( iOut<pSorter->nTree && iOut>0 );
! 350:
! 351: if( iOut>=(pSorter->nTree/2) ){
! 352: i1 = (iOut - pSorter->nTree/2) * 2;
! 353: i2 = i1 + 1;
! 354: }else{
! 355: i1 = pSorter->aTree[iOut*2];
! 356: i2 = pSorter->aTree[iOut*2+1];
! 357: }
! 358:
! 359: p1 = &pSorter->aIter[i1];
! 360: p2 = &pSorter->aIter[i2];
! 361:
! 362: if( p1->pFile==0 ){
! 363: iRes = i2;
! 364: }else if( p2->pFile==0 ){
! 365: iRes = i1;
! 366: }else{
! 367: int res;
! 368: assert( pCsr->pSorter->pUnpacked!=0 ); /* allocated in vdbeSorterMerge() */
! 369: vdbeSorterCompare(
! 370: pCsr, 0, p1->aKey, p1->nKey, p2->aKey, p2->nKey, &res
! 371: );
! 372: if( res<=0 ){
! 373: iRes = i1;
! 374: }else{
! 375: iRes = i2;
! 376: }
! 377: }
! 378:
! 379: pSorter->aTree[iOut] = iRes;
! 380: return SQLITE_OK;
! 381: }
! 382:
! 383: /*
! 384: ** Initialize the temporary index cursor just opened as a sorter cursor.
! 385: */
! 386: int sqlite3VdbeSorterInit(sqlite3 *db, VdbeCursor *pCsr){
! 387: int pgsz; /* Page size of main database */
! 388: int mxCache; /* Cache size */
! 389: VdbeSorter *pSorter; /* The new sorter */
! 390: char *d; /* Dummy */
! 391:
! 392: assert( pCsr->pKeyInfo && pCsr->pBt==0 );
! 393: pCsr->pSorter = pSorter = sqlite3DbMallocZero(db, sizeof(VdbeSorter));
! 394: if( pSorter==0 ){
! 395: return SQLITE_NOMEM;
! 396: }
! 397:
! 398: pSorter->pUnpacked = sqlite3VdbeAllocUnpackedRecord(pCsr->pKeyInfo, 0, 0, &d);
! 399: if( pSorter->pUnpacked==0 ) return SQLITE_NOMEM;
! 400: assert( pSorter->pUnpacked==(UnpackedRecord *)d );
! 401:
! 402: if( !sqlite3TempInMemory(db) ){
! 403: pgsz = sqlite3BtreeGetPageSize(db->aDb[0].pBt);
! 404: pSorter->mnPmaSize = SORTER_MIN_WORKING * pgsz;
! 405: mxCache = db->aDb[0].pSchema->cache_size;
! 406: if( mxCache<SORTER_MIN_WORKING ) mxCache = SORTER_MIN_WORKING;
! 407: pSorter->mxPmaSize = mxCache * pgsz;
! 408: }
! 409:
! 410: return SQLITE_OK;
! 411: }
! 412:
! 413: /*
! 414: ** Free the list of sorted records starting at pRecord.
! 415: */
! 416: static void vdbeSorterRecordFree(sqlite3 *db, SorterRecord *pRecord){
! 417: SorterRecord *p;
! 418: SorterRecord *pNext;
! 419: for(p=pRecord; p; p=pNext){
! 420: pNext = p->pNext;
! 421: sqlite3DbFree(db, p);
! 422: }
! 423: }
! 424:
! 425: /*
! 426: ** Free any cursor components allocated by sqlite3VdbeSorterXXX routines.
! 427: */
! 428: void sqlite3VdbeSorterClose(sqlite3 *db, VdbeCursor *pCsr){
! 429: VdbeSorter *pSorter = pCsr->pSorter;
! 430: if( pSorter ){
! 431: if( pSorter->aIter ){
! 432: int i;
! 433: for(i=0; i<pSorter->nTree; i++){
! 434: vdbeSorterIterZero(db, &pSorter->aIter[i]);
! 435: }
! 436: sqlite3DbFree(db, pSorter->aIter);
! 437: }
! 438: if( pSorter->pTemp1 ){
! 439: sqlite3OsCloseFree(pSorter->pTemp1);
! 440: }
! 441: vdbeSorterRecordFree(db, pSorter->pRecord);
! 442: sqlite3DbFree(db, pSorter->pUnpacked);
! 443: sqlite3DbFree(db, pSorter);
! 444: pCsr->pSorter = 0;
! 445: }
! 446: }
! 447:
! 448: /*
! 449: ** Allocate space for a file-handle and open a temporary file. If successful,
! 450: ** set *ppFile to point to the malloc'd file-handle and return SQLITE_OK.
! 451: ** Otherwise, set *ppFile to 0 and return an SQLite error code.
! 452: */
! 453: static int vdbeSorterOpenTempFile(sqlite3 *db, sqlite3_file **ppFile){
! 454: int dummy;
! 455: return sqlite3OsOpenMalloc(db->pVfs, 0, ppFile,
! 456: SQLITE_OPEN_TEMP_JOURNAL |
! 457: SQLITE_OPEN_READWRITE | SQLITE_OPEN_CREATE |
! 458: SQLITE_OPEN_EXCLUSIVE | SQLITE_OPEN_DELETEONCLOSE, &dummy
! 459: );
! 460: }
! 461:
! 462: /*
! 463: ** Merge the two sorted lists p1 and p2 into a single list.
! 464: ** Set *ppOut to the head of the new list.
! 465: */
! 466: static void vdbeSorterMerge(
! 467: VdbeCursor *pCsr, /* For pKeyInfo */
! 468: SorterRecord *p1, /* First list to merge */
! 469: SorterRecord *p2, /* Second list to merge */
! 470: SorterRecord **ppOut /* OUT: Head of merged list */
! 471: ){
! 472: SorterRecord *pFinal = 0;
! 473: SorterRecord **pp = &pFinal;
! 474: void *pVal2 = p2 ? p2->pVal : 0;
! 475:
! 476: while( p1 && p2 ){
! 477: int res;
! 478: vdbeSorterCompare(pCsr, 0, p1->pVal, p1->nVal, pVal2, p2->nVal, &res);
! 479: if( res<=0 ){
! 480: *pp = p1;
! 481: pp = &p1->pNext;
! 482: p1 = p1->pNext;
! 483: pVal2 = 0;
! 484: }else{
! 485: *pp = p2;
! 486: pp = &p2->pNext;
! 487: p2 = p2->pNext;
! 488: if( p2==0 ) break;
! 489: pVal2 = p2->pVal;
! 490: }
! 491: }
! 492: *pp = p1 ? p1 : p2;
! 493: *ppOut = pFinal;
! 494: }
! 495:
! 496: /*
! 497: ** Sort the linked list of records headed at pCsr->pRecord. Return SQLITE_OK
! 498: ** if successful, or an SQLite error code (i.e. SQLITE_NOMEM) if an error
! 499: ** occurs.
! 500: */
! 501: static int vdbeSorterSort(VdbeCursor *pCsr){
! 502: int i;
! 503: SorterRecord **aSlot;
! 504: SorterRecord *p;
! 505: VdbeSorter *pSorter = pCsr->pSorter;
! 506:
! 507: aSlot = (SorterRecord **)sqlite3MallocZero(64 * sizeof(SorterRecord *));
! 508: if( !aSlot ){
! 509: return SQLITE_NOMEM;
! 510: }
! 511:
! 512: p = pSorter->pRecord;
! 513: while( p ){
! 514: SorterRecord *pNext = p->pNext;
! 515: p->pNext = 0;
! 516: for(i=0; aSlot[i]; i++){
! 517: vdbeSorterMerge(pCsr, p, aSlot[i], &p);
! 518: aSlot[i] = 0;
! 519: }
! 520: aSlot[i] = p;
! 521: p = pNext;
! 522: }
! 523:
! 524: p = 0;
! 525: for(i=0; i<64; i++){
! 526: vdbeSorterMerge(pCsr, p, aSlot[i], &p);
! 527: }
! 528: pSorter->pRecord = p;
! 529:
! 530: sqlite3_free(aSlot);
! 531: return SQLITE_OK;
! 532: }
! 533:
! 534:
! 535: /*
! 536: ** Write the current contents of the in-memory linked-list to a PMA. Return
! 537: ** SQLITE_OK if successful, or an SQLite error code otherwise.
! 538: **
! 539: ** The format of a PMA is:
! 540: **
! 541: ** * A varint. This varint contains the total number of bytes of content
! 542: ** in the PMA (not including the varint itself).
! 543: **
! 544: ** * One or more records packed end-to-end in order of ascending keys.
! 545: ** Each record consists of a varint followed by a blob of data (the
! 546: ** key). The varint is the number of bytes in the blob of data.
! 547: */
! 548: static int vdbeSorterListToPMA(sqlite3 *db, VdbeCursor *pCsr){
! 549: int rc = SQLITE_OK; /* Return code */
! 550: VdbeSorter *pSorter = pCsr->pSorter;
! 551:
! 552: if( pSorter->nInMemory==0 ){
! 553: assert( pSorter->pRecord==0 );
! 554: return rc;
! 555: }
! 556:
! 557: rc = vdbeSorterSort(pCsr);
! 558:
! 559: /* If the first temporary PMA file has not been opened, open it now. */
! 560: if( rc==SQLITE_OK && pSorter->pTemp1==0 ){
! 561: rc = vdbeSorterOpenTempFile(db, &pSorter->pTemp1);
! 562: assert( rc!=SQLITE_OK || pSorter->pTemp1 );
! 563: assert( pSorter->iWriteOff==0 );
! 564: assert( pSorter->nPMA==0 );
! 565: }
! 566:
! 567: if( rc==SQLITE_OK ){
! 568: i64 iOff = pSorter->iWriteOff;
! 569: SorterRecord *p;
! 570: SorterRecord *pNext = 0;
! 571: static const char eightZeros[8] = { 0, 0, 0, 0, 0, 0, 0, 0 };
! 572:
! 573: pSorter->nPMA++;
! 574: rc = vdbeSorterWriteVarint(pSorter->pTemp1, pSorter->nInMemory, &iOff);
! 575: for(p=pSorter->pRecord; rc==SQLITE_OK && p; p=pNext){
! 576: pNext = p->pNext;
! 577: rc = vdbeSorterWriteVarint(pSorter->pTemp1, p->nVal, &iOff);
! 578:
! 579: if( rc==SQLITE_OK ){
! 580: rc = sqlite3OsWrite(pSorter->pTemp1, p->pVal, p->nVal, iOff);
! 581: iOff += p->nVal;
! 582: }
! 583:
! 584: sqlite3DbFree(db, p);
! 585: }
! 586:
! 587: /* This assert verifies that unless an error has occurred, the size of
! 588: ** the PMA on disk is the same as the expected size stored in
! 589: ** pSorter->nInMemory. */
! 590: assert( rc!=SQLITE_OK || pSorter->nInMemory==(
! 591: iOff-pSorter->iWriteOff-sqlite3VarintLen(pSorter->nInMemory)
! 592: ));
! 593:
! 594: pSorter->iWriteOff = iOff;
! 595: if( rc==SQLITE_OK ){
! 596: /* Terminate each file with 8 extra bytes so that from any offset
! 597: ** in the file we can always read 9 bytes without a SHORT_READ error */
! 598: rc = sqlite3OsWrite(pSorter->pTemp1, eightZeros, 8, iOff);
! 599: }
! 600: pSorter->pRecord = p;
! 601: }
! 602:
! 603: return rc;
! 604: }
! 605:
! 606: /*
! 607: ** Add a record to the sorter.
! 608: */
! 609: int sqlite3VdbeSorterWrite(
! 610: sqlite3 *db, /* Database handle */
! 611: VdbeCursor *pCsr, /* Sorter cursor */
! 612: Mem *pVal /* Memory cell containing record */
! 613: ){
! 614: VdbeSorter *pSorter = pCsr->pSorter;
! 615: int rc = SQLITE_OK; /* Return Code */
! 616: SorterRecord *pNew; /* New list element */
! 617:
! 618: assert( pSorter );
! 619: pSorter->nInMemory += sqlite3VarintLen(pVal->n) + pVal->n;
! 620:
! 621: pNew = (SorterRecord *)sqlite3DbMallocRaw(db, pVal->n + sizeof(SorterRecord));
! 622: if( pNew==0 ){
! 623: rc = SQLITE_NOMEM;
! 624: }else{
! 625: pNew->pVal = (void *)&pNew[1];
! 626: memcpy(pNew->pVal, pVal->z, pVal->n);
! 627: pNew->nVal = pVal->n;
! 628: pNew->pNext = pSorter->pRecord;
! 629: pSorter->pRecord = pNew;
! 630: }
! 631:
! 632: /* See if the contents of the sorter should now be written out. They
! 633: ** are written out when either of the following are true:
! 634: **
! 635: ** * The total memory allocated for the in-memory list is greater
! 636: ** than (page-size * cache-size), or
! 637: **
! 638: ** * The total memory allocated for the in-memory list is greater
! 639: ** than (page-size * 10) and sqlite3HeapNearlyFull() returns true.
! 640: */
! 641: if( rc==SQLITE_OK && pSorter->mxPmaSize>0 && (
! 642: (pSorter->nInMemory>pSorter->mxPmaSize)
! 643: || (pSorter->nInMemory>pSorter->mnPmaSize && sqlite3HeapNearlyFull())
! 644: )){
! 645: rc = vdbeSorterListToPMA(db, pCsr);
! 646: pSorter->nInMemory = 0;
! 647: }
! 648:
! 649: return rc;
! 650: }
! 651:
! 652: /*
! 653: ** Helper function for sqlite3VdbeSorterRewind().
! 654: */
! 655: static int vdbeSorterInitMerge(
! 656: sqlite3 *db, /* Database handle */
! 657: VdbeCursor *pCsr, /* Cursor handle for this sorter */
! 658: i64 *pnByte /* Sum of bytes in all opened PMAs */
! 659: ){
! 660: VdbeSorter *pSorter = pCsr->pSorter;
! 661: int rc = SQLITE_OK; /* Return code */
! 662: int i; /* Used to iterator through aIter[] */
! 663: i64 nByte = 0; /* Total bytes in all opened PMAs */
! 664:
! 665: /* Initialize the iterators. */
! 666: for(i=0; i<SORTER_MAX_MERGE_COUNT; i++){
! 667: VdbeSorterIter *pIter = &pSorter->aIter[i];
! 668: rc = vdbeSorterIterInit(db, pSorter, pSorter->iReadOff, pIter, &nByte);
! 669: pSorter->iReadOff = pIter->iEof;
! 670: assert( rc!=SQLITE_OK || pSorter->iReadOff<=pSorter->iWriteOff );
! 671: if( rc!=SQLITE_OK || pSorter->iReadOff>=pSorter->iWriteOff ) break;
! 672: }
! 673:
! 674: /* Initialize the aTree[] array. */
! 675: for(i=pSorter->nTree-1; rc==SQLITE_OK && i>0; i--){
! 676: rc = vdbeSorterDoCompare(pCsr, i);
! 677: }
! 678:
! 679: *pnByte = nByte;
! 680: return rc;
! 681: }
! 682:
! 683: /*
! 684: ** Once the sorter has been populated, this function is called to prepare
! 685: ** for iterating through its contents in sorted order.
! 686: */
! 687: int sqlite3VdbeSorterRewind(sqlite3 *db, VdbeCursor *pCsr, int *pbEof){
! 688: VdbeSorter *pSorter = pCsr->pSorter;
! 689: int rc; /* Return code */
! 690: sqlite3_file *pTemp2 = 0; /* Second temp file to use */
! 691: i64 iWrite2 = 0; /* Write offset for pTemp2 */
! 692: int nIter; /* Number of iterators used */
! 693: int nByte; /* Bytes of space required for aIter/aTree */
! 694: int N = 2; /* Power of 2 >= nIter */
! 695:
! 696: assert( pSorter );
! 697:
! 698: /* If no data has been written to disk, then do not do so now. Instead,
! 699: ** sort the VdbeSorter.pRecord list. The vdbe layer will read data directly
! 700: ** from the in-memory list. */
! 701: if( pSorter->nPMA==0 ){
! 702: *pbEof = !pSorter->pRecord;
! 703: assert( pSorter->aTree==0 );
! 704: return vdbeSorterSort(pCsr);
! 705: }
! 706:
! 707: /* Write the current b-tree to a PMA. Close the b-tree cursor. */
! 708: rc = vdbeSorterListToPMA(db, pCsr);
! 709: if( rc!=SQLITE_OK ) return rc;
! 710:
! 711: /* Allocate space for aIter[] and aTree[]. */
! 712: nIter = pSorter->nPMA;
! 713: if( nIter>SORTER_MAX_MERGE_COUNT ) nIter = SORTER_MAX_MERGE_COUNT;
! 714: assert( nIter>0 );
! 715: while( N<nIter ) N += N;
! 716: nByte = N * (sizeof(int) + sizeof(VdbeSorterIter));
! 717: pSorter->aIter = (VdbeSorterIter *)sqlite3DbMallocZero(db, nByte);
! 718: if( !pSorter->aIter ) return SQLITE_NOMEM;
! 719: pSorter->aTree = (int *)&pSorter->aIter[N];
! 720: pSorter->nTree = N;
! 721:
! 722: do {
! 723: int iNew; /* Index of new, merged, PMA */
! 724:
! 725: for(iNew=0;
! 726: rc==SQLITE_OK && iNew*SORTER_MAX_MERGE_COUNT<pSorter->nPMA;
! 727: iNew++
! 728: ){
! 729: i64 nWrite; /* Number of bytes in new PMA */
! 730:
! 731: /* If there are SORTER_MAX_MERGE_COUNT or less PMAs in file pTemp1,
! 732: ** initialize an iterator for each of them and break out of the loop.
! 733: ** These iterators will be incrementally merged as the VDBE layer calls
! 734: ** sqlite3VdbeSorterNext().
! 735: **
! 736: ** Otherwise, if pTemp1 contains more than SORTER_MAX_MERGE_COUNT PMAs,
! 737: ** initialize interators for SORTER_MAX_MERGE_COUNT of them. These PMAs
! 738: ** are merged into a single PMA that is written to file pTemp2.
! 739: */
! 740: rc = vdbeSorterInitMerge(db, pCsr, &nWrite);
! 741: assert( rc!=SQLITE_OK || pSorter->aIter[ pSorter->aTree[1] ].pFile );
! 742: if( rc!=SQLITE_OK || pSorter->nPMA<=SORTER_MAX_MERGE_COUNT ){
! 743: break;
! 744: }
! 745:
! 746: /* Open the second temp file, if it is not already open. */
! 747: if( pTemp2==0 ){
! 748: assert( iWrite2==0 );
! 749: rc = vdbeSorterOpenTempFile(db, &pTemp2);
! 750: }
! 751:
! 752: if( rc==SQLITE_OK ){
! 753: rc = vdbeSorterWriteVarint(pTemp2, nWrite, &iWrite2);
! 754: }
! 755:
! 756: if( rc==SQLITE_OK ){
! 757: int bEof = 0;
! 758: while( rc==SQLITE_OK && bEof==0 ){
! 759: int nToWrite;
! 760: VdbeSorterIter *pIter = &pSorter->aIter[ pSorter->aTree[1] ];
! 761: assert( pIter->pFile );
! 762: nToWrite = pIter->nKey + sqlite3VarintLen(pIter->nKey);
! 763: rc = sqlite3OsWrite(pTemp2, pIter->aAlloc, nToWrite, iWrite2);
! 764: iWrite2 += nToWrite;
! 765: if( rc==SQLITE_OK ){
! 766: rc = sqlite3VdbeSorterNext(db, pCsr, &bEof);
! 767: }
! 768: }
! 769: }
! 770: }
! 771:
! 772: if( pSorter->nPMA<=SORTER_MAX_MERGE_COUNT ){
! 773: break;
! 774: }else{
! 775: sqlite3_file *pTmp = pSorter->pTemp1;
! 776: pSorter->nPMA = iNew;
! 777: pSorter->pTemp1 = pTemp2;
! 778: pTemp2 = pTmp;
! 779: pSorter->iWriteOff = iWrite2;
! 780: pSorter->iReadOff = 0;
! 781: iWrite2 = 0;
! 782: }
! 783: }while( rc==SQLITE_OK );
! 784:
! 785: if( pTemp2 ){
! 786: sqlite3OsCloseFree(pTemp2);
! 787: }
! 788: *pbEof = (pSorter->aIter[pSorter->aTree[1]].pFile==0);
! 789: return rc;
! 790: }
! 791:
! 792: /*
! 793: ** Advance to the next element in the sorter.
! 794: */
! 795: int sqlite3VdbeSorterNext(sqlite3 *db, VdbeCursor *pCsr, int *pbEof){
! 796: VdbeSorter *pSorter = pCsr->pSorter;
! 797: int rc; /* Return code */
! 798:
! 799: if( pSorter->aTree ){
! 800: int iPrev = pSorter->aTree[1];/* Index of iterator to advance */
! 801: int i; /* Index of aTree[] to recalculate */
! 802:
! 803: rc = vdbeSorterIterNext(db, &pSorter->aIter[iPrev]);
! 804: for(i=(pSorter->nTree+iPrev)/2; rc==SQLITE_OK && i>0; i=i/2){
! 805: rc = vdbeSorterDoCompare(pCsr, i);
! 806: }
! 807:
! 808: *pbEof = (pSorter->aIter[pSorter->aTree[1]].pFile==0);
! 809: }else{
! 810: SorterRecord *pFree = pSorter->pRecord;
! 811: pSorter->pRecord = pFree->pNext;
! 812: pFree->pNext = 0;
! 813: vdbeSorterRecordFree(db, pFree);
! 814: *pbEof = !pSorter->pRecord;
! 815: rc = SQLITE_OK;
! 816: }
! 817: return rc;
! 818: }
! 819:
! 820: /*
! 821: ** Return a pointer to a buffer owned by the sorter that contains the
! 822: ** current key.
! 823: */
! 824: static void *vdbeSorterRowkey(
! 825: VdbeSorter *pSorter, /* Sorter object */
! 826: int *pnKey /* OUT: Size of current key in bytes */
! 827: ){
! 828: void *pKey;
! 829: if( pSorter->aTree ){
! 830: VdbeSorterIter *pIter;
! 831: pIter = &pSorter->aIter[ pSorter->aTree[1] ];
! 832: *pnKey = pIter->nKey;
! 833: pKey = pIter->aKey;
! 834: }else{
! 835: *pnKey = pSorter->pRecord->nVal;
! 836: pKey = pSorter->pRecord->pVal;
! 837: }
! 838: return pKey;
! 839: }
! 840:
! 841: /*
! 842: ** Copy the current sorter key into the memory cell pOut.
! 843: */
! 844: int sqlite3VdbeSorterRowkey(VdbeCursor *pCsr, Mem *pOut){
! 845: VdbeSorter *pSorter = pCsr->pSorter;
! 846: void *pKey; int nKey; /* Sorter key to copy into pOut */
! 847:
! 848: pKey = vdbeSorterRowkey(pSorter, &nKey);
! 849: if( sqlite3VdbeMemGrow(pOut, nKey, 0) ){
! 850: return SQLITE_NOMEM;
! 851: }
! 852: pOut->n = nKey;
! 853: MemSetTypeFlag(pOut, MEM_Blob);
! 854: memcpy(pOut->z, pKey, nKey);
! 855:
! 856: return SQLITE_OK;
! 857: }
! 858:
! 859: /*
! 860: ** Compare the key in memory cell pVal with the key that the sorter cursor
! 861: ** passed as the first argument currently points to. For the purposes of
! 862: ** the comparison, ignore the rowid field at the end of each record.
! 863: **
! 864: ** If an error occurs, return an SQLite error code (i.e. SQLITE_NOMEM).
! 865: ** Otherwise, set *pRes to a negative, zero or positive value if the
! 866: ** key in pVal is smaller than, equal to or larger than the current sorter
! 867: ** key.
! 868: */
! 869: int sqlite3VdbeSorterCompare(
! 870: VdbeCursor *pCsr, /* Sorter cursor */
! 871: Mem *pVal, /* Value to compare to current sorter key */
! 872: int *pRes /* OUT: Result of comparison */
! 873: ){
! 874: VdbeSorter *pSorter = pCsr->pSorter;
! 875: void *pKey; int nKey; /* Sorter key to compare pVal with */
! 876:
! 877: pKey = vdbeSorterRowkey(pSorter, &nKey);
! 878: vdbeSorterCompare(pCsr, 1, pVal->z, pVal->n, pKey, nKey, pRes);
! 879: return SQLITE_OK;
! 880: }
! 881:
! 882: #endif /* #ifndef SQLITE_OMIT_MERGE_SORT */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to vdbesort.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / sqlite3 / src