Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | In vdbesort.c, change the names of PmaReader variables "pIter" to "pReadr". Other related comment changes. The generated object code should be the same. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | threads |
Files: | files | file ages | folders |
SHA1: |
99efb235a08784020535a770d7e7d96d |
User & Date: | drh 2014-05-20 11:03:53.818 |
Context
2014-05-20
| ||
19:11 | Improvements to the testability of the threads.c module. (check-in: 386e088868 user: drh tags: threads) | |
11:03 | In vdbesort.c, change the names of PmaReader variables "pIter" to "pReadr". Other related comment changes. The generated object code should be the same. (check-in: 99efb235a0 user: drh tags: threads) | |
2014-05-19
| ||
23:17 | Merge recent changes from trunk. (check-in: 6eefdad946 user: drh tags: threads) | |
Changes
Changes to src/vdbesort.c.
︙ | ︙ | |||
184 185 186 187 188 189 190 | /* ** The MergeEngine object is used to combine two or more smaller PMAs into ** one big PMA using a merge operation. Separate PMAs all need to be ** combined into one big PMA in order to be able to step through the sorted ** records in order. ** | | | | | | | | | | | | | | | | | | | | | | | 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 | /* ** The MergeEngine object is used to combine two or more smaller PMAs into ** one big PMA using a merge operation. Separate PMAs all need to be ** combined into one big PMA in order to be able to step through the sorted ** records in order. ** ** The aReadr[] array contains a PmaReader object for each of the PMAs being ** merged. An aReadr[] object either points to a valid key or else is at EOF. ** For the purposes of the paragraphs below, we assume that the array is ** actually N elements in size, where N is the smallest power of 2 greater ** to or equal to the number of PMAs being merged. The extra aReadr[] elements ** are treated as if they are empty (always at EOF). ** ** The aTree[] array is also N elements in size. The value of N is stored in ** the MergeEngine.nTree variable. ** ** The final (N/2) elements of aTree[] contain the results of comparing ** pairs of PMA keys together. Element i contains the result of ** comparing aReadr[2*i-N] and aReadr[2*i-N+1]. Whichever key is smaller, the ** aTree element is set to the index of it. ** ** For the purposes of this comparison, EOF is considered greater than any ** other key value. If the keys are equal (only possible with two EOF ** values), it doesn't matter which index is stored. ** ** The (N/4) elements of aTree[] that precede the final (N/2) described ** above contains the index of the smallest of each block of 4 PmaReaders ** And so on. So that aTree[1] contains the index of the PmaReader that ** currently points to the smallest key value. aTree[0] is unused. ** ** Example: ** ** aReadr[0] -> Banana ** aReadr[1] -> Feijoa ** aReadr[2] -> Elderberry ** aReadr[3] -> Currant ** aReadr[4] -> Grapefruit ** aReadr[5] -> Apple ** aReadr[6] -> Durian ** aReadr[7] -> EOF ** ** aTree[] = { X, 5 0, 5 0, 3, 5, 6 } ** ** The current element is "Apple" (the value of the key indicated by ** PmaReader 5). When the Next() operation is invoked, PmaReader 5 will ** be advanced to the next key in its segment. Say the next key is ** "Eggplant": ** ** aReadr[5] -> Eggplant ** ** The contents of aTree[] are updated first by comparing the new PmaReader ** 5 key to the current key of PmaReader 4 (still "Grapefruit"). The PmaReader ** 5 value is still smaller, so aTree[6] is set to 5. And so on up the tree. ** The value of PmaReader 6 - "Durian" - is now smaller than that of PmaReader ** 5, so aTree[3] is set to 6. Key 0 is smaller than key 6 (Banana<Durian), ** so the value written into element 1 of the array is 0. As follows: ** ** aTree[] = { X, 0 0, 6 0, 3, 5, 6 } ** ** In other words, each time we advance to the next sorter element, log2(N) ** key comparison operations are required, where N is the number of segments ** being merged (rounded up to the next power of 2). */ struct MergeEngine { int nTree; /* Used size of aTree/aReadr (power of 2) */ int *aTree; /* Current state of incremental merge */ PmaReader *aReadr; /* Array of PmaReaders to merge data from */ }; /* ** Exactly VdbeSorter.nTask instances of this object are allocated ** as part of each VdbeSorter object. Instances are never allocated any ** other way. VdbeSorter.nTask is set to the number of worker threads allowed ** (see SQLITE_CONFIG_WORKER_THREADS) plus one (the main thread). |
︙ | ︙ | |||
300 301 302 303 304 305 306 | ** largest record in the sorter. */ struct VdbeSorter { int mnPmaSize; /* Minimum PMA size, in bytes */ int mxPmaSize; /* Maximum PMA size, in bytes. 0==no limit */ int mxKeysize; /* Largest serialized key seen so far */ int pgsz; /* Main database page size */ | | | 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 | ** largest record in the sorter. */ struct VdbeSorter { int mnPmaSize; /* Minimum PMA size, in bytes */ int mxPmaSize; /* Maximum PMA size, in bytes. 0==no limit */ int mxKeysize; /* Largest serialized key seen so far */ int pgsz; /* Main database page size */ PmaReader *pReader; /* Readr data from here after Rewind() */ MergeEngine *pMerger; /* Or here, if bUseThreads==0 */ sqlite3 *db; /* Database connection */ KeyInfo *pKeyInfo; /* How to compare records */ UnpackedRecord *pUnpacked; /* Used by VdbeSorterCompare() */ SorterList list; /* List of in-memory records */ int iMemory; /* Offset of free space in list.aMemory */ int nMemory; /* Size of list.aMemory allocation in bytes */ |
︙ | ︙ | |||
322 323 324 325 326 327 328 | /* ** An instance of the following object is used to read records out of a ** PMA, in sorted order. The next key to be read is cached in nKey/aKey. ** pFile==0 at EOF. */ struct PmaReader { i64 iReadOff; /* Current read offset */ | | | | 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 | /* ** An instance of the following object is used to read records out of a ** PMA, in sorted order. The next key to be read is cached in nKey/aKey. ** pFile==0 at EOF. */ struct PmaReader { i64 iReadOff; /* Current read offset */ i64 iEof; /* 1 byte past EOF for this PmaReader */ int nAlloc; /* Bytes of space at aAlloc */ int nKey; /* Number of bytes in key */ sqlite3_file *pFile; /* File we are reading from */ u8 *aAlloc; /* Allocated space */ u8 *aKey; /* Pointer to current key */ u8 *aBuffer; /* Current read buffer */ int nBuffer; /* Size of read buffer in bytes */ u8 *aMap; /* Pointer to mapping of entire file */ IncrMerger *pIncr; /* Incremental merger */ }; |
︙ | ︙ | |||
442 443 444 445 446 447 448 | static int vdbeIncrSwap(IncrMerger*); static void vdbeIncrFree(IncrMerger *); /* ** Free all memory belonging to the PmaReader object passed as the second ** argument. All structure fields are set to zero before returning. */ | | | | | | | | | 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 | static int vdbeIncrSwap(IncrMerger*); static void vdbeIncrFree(IncrMerger *); /* ** Free all memory belonging to the PmaReader object passed as the second ** argument. All structure fields are set to zero before returning. */ static void vdbePmaReaderClear(PmaReader *pReadr){ sqlite3_free(pReadr->aAlloc); sqlite3_free(pReadr->aBuffer); if( pReadr->aMap ) sqlite3OsUnfetch(pReadr->pFile, 0, pReadr->aMap); vdbeIncrFree(pReadr->pIncr); memset(pReadr, 0, sizeof(PmaReader)); } /* ** Read nByte bytes of data from the stream of data iterated by object p. ** If successful, set *ppOut to point to a buffer containing the data ** and return SQLITE_OK. Otherwise, if an error occurs, return an SQLite ** error code. ** ** The buffer indicated by *ppOut may only be considered valid until the ** next call to this function. */ static int vdbePmaReadBlob( PmaReader *p, /* PmaReader from which to take the blob */ int nByte, /* Bytes of data to read */ u8 **ppOut /* OUT: Pointer to buffer containing data */ ){ int iBuf; /* Offset within buffer to read from */ int nAvail; /* Bytes of data available in buffer */ if( p->aMap ){ |
︙ | ︙ | |||
491 492 493 494 495 496 497 | if( (p->iEof - p->iReadOff) > (i64)p->nBuffer ){ nRead = p->nBuffer; }else{ nRead = (int)(p->iEof - p->iReadOff); } assert( nRead>0 ); | | | 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 | if( (p->iEof - p->iReadOff) > (i64)p->nBuffer ){ nRead = p->nBuffer; }else{ nRead = (int)(p->iEof - p->iReadOff); } assert( nRead>0 ); /* Readr data from the file. Return early if an error occurs. */ rc = sqlite3OsRead(p->pFile, p->aBuffer, nRead, p->iReadOff); assert( rc!=SQLITE_IOERR_SHORT_READ ); if( rc!=SQLITE_OK ) return rc; } nAvail = p->nBuffer - iBuf; if( nByte<=nAvail ){ |
︙ | ︙ | |||
595 596 597 598 599 600 601 | if( pFile->iEof<=(i64)(pTask->pSorter->db->nMaxSorterMmap) ){ rc = sqlite3OsFetch(pFile->pFd, 0, (int)pFile->iEof, (void**)pp); } return rc; } /* | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 | if( pFile->iEof<=(i64)(pTask->pSorter->db->nMaxSorterMmap) ){ rc = sqlite3OsFetch(pFile->pFd, 0, (int)pFile->iEof, (void**)pp); } return rc; } /* ** Seek PmaReader pReadr to offset iOff within file pFile. Return SQLITE_OK ** if successful, or an SQLite error code if an error occurs. */ static int vdbePmaReaderSeek( SortSubtask *pTask, /* Task context */ PmaReader *pReadr, /* Iterate to populate */ SorterFile *pFile, /* Sorter file to read from */ i64 iOff /* Offset in pFile */ ){ int rc = SQLITE_OK; assert( pReadr->pIncr==0 || pReadr->pIncr->bEof==0 ); if( pReadr->aMap ){ sqlite3OsUnfetch(pReadr->pFile, 0, pReadr->aMap); pReadr->aMap = 0; } pReadr->iReadOff = iOff; pReadr->iEof = pFile->iEof; pReadr->pFile = pFile->pFd; rc = vdbeSorterMapFile(pTask, pFile, &pReadr->aMap); if( rc==SQLITE_OK && pReadr->aMap==0 ){ int pgsz = pTask->pSorter->pgsz; int iBuf = pReadr->iReadOff % pgsz; if( pReadr->aBuffer==0 ){ pReadr->aBuffer = (u8*)sqlite3Malloc(pgsz); if( pReadr->aBuffer==0 ) rc = SQLITE_NOMEM; pReadr->nBuffer = pgsz; } if( rc==SQLITE_OK && iBuf ){ int nRead = pgsz - iBuf; if( (pReadr->iReadOff + nRead) > pReadr->iEof ){ nRead = (int)(pReadr->iEof - pReadr->iReadOff); } rc = sqlite3OsRead( pReadr->pFile, &pReadr->aBuffer[iBuf], nRead, pReadr->iReadOff ); assert( rc!=SQLITE_IOERR_SHORT_READ ); } } return rc; } /* ** Advance PmaReader pReadr to the next key in its PMA. Return SQLITE_OK if ** no error occurs, or an SQLite error code if one does. */ static int vdbePmaReaderNext(PmaReader *pReadr){ int rc = SQLITE_OK; /* Return Code */ u64 nRec = 0; /* Size of record in bytes */ if( pReadr->iReadOff>=pReadr->iEof ){ IncrMerger *pIncr = pReadr->pIncr; int bEof = 1; if( pIncr ){ rc = vdbeIncrSwap(pIncr); if( rc==SQLITE_OK && pIncr->bEof==0 ){ rc = vdbePmaReaderSeek( pIncr->pTask, pReadr, &pIncr->aFile[0], pIncr->iStartOff ); bEof = 0; } } if( bEof ){ /* This is an EOF condition */ vdbePmaReaderClear(pReadr); return rc; } } if( rc==SQLITE_OK ){ rc = vdbePmaReadVarint(pReadr, &nRec); } if( rc==SQLITE_OK ){ pReadr->nKey = (int)nRec; rc = vdbePmaReadBlob(pReadr, (int)nRec, &pReadr->aKey); } return rc; } /* ** Initialize PmaReader pReadr to scan through the PMA stored in file pFile ** starting at offset iStart and ending at offset iEof-1. This function ** leaves the PmaReader pointing to the first key in the PMA (or EOF if the ** PMA is empty). ** ** If the pnByte parameter is NULL, then it is assumed that the file ** contains a single PMA, and that that PMA omits the initial length varint. */ static int vdbePmaReaderInit( SortSubtask *pTask, /* Task context */ SorterFile *pFile, /* Sorter file to read from */ i64 iStart, /* Start offset in pFile */ PmaReader *pReadr, /* PmaReader to populate */ i64 *pnByte /* IN/OUT: Increment this value by PMA size */ ){ int rc; assert( pFile->iEof>iStart ); assert( pReadr->aAlloc==0 && pReadr->nAlloc==0 ); assert( pReadr->aBuffer==0 ); assert( pReadr->aMap==0 ); rc = vdbePmaReaderSeek(pTask, pReadr, pFile, iStart); if( rc==SQLITE_OK ){ u64 nByte; /* Size of PMA in bytes */ rc = vdbePmaReadVarint(pReadr, &nByte); pReadr->iEof = pReadr->iReadOff + nByte; *pnByte += nByte; } if( rc==SQLITE_OK ){ rc = vdbePmaReaderNext(pReadr); } return rc; } /* ** Compare key1 (buffer pKey1, size nKey1 bytes) with key2 (buffer pKey2, |
︙ | ︙ | |||
744 745 746 747 748 749 750 | if( pKey2 ){ sqlite3VdbeRecordUnpack(pTask->pSorter->pKeyInfo, nKey2, pKey2, r2); } return sqlite3VdbeRecordCompare(nKey1, pKey1, r2, 0); } /* | | | 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 | if( pKey2 ){ sqlite3VdbeRecordUnpack(pTask->pSorter->pKeyInfo, nKey2, pKey2, r2); } return sqlite3VdbeRecordCompare(nKey1, pKey1, r2, 0); } /* ** This function is called to compare two PmaReader keys when merging ** multiple b-tree segments. Parameter iOut is the index of the aTree[] ** value to recalculate. */ static int vdbeSorterDoCompare( SortSubtask *pTask, MergeEngine *pMerger, int iOut |
︙ | ︙ | |||
769 770 771 772 773 774 775 | i1 = (iOut - pMerger->nTree/2) * 2; i2 = i1 + 1; }else{ i1 = pMerger->aTree[iOut*2]; i2 = pMerger->aTree[iOut*2+1]; } | | | | 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 | i1 = (iOut - pMerger->nTree/2) * 2; i2 = i1 + 1; }else{ i1 = pMerger->aTree[iOut*2]; i2 = pMerger->aTree[iOut*2+1]; } p1 = &pMerger->aReadr[i1]; p2 = &pMerger->aReadr[i2]; if( p1->pFile==0 ){ iRes = i2; }else if( p2->pFile==0 ){ iRes = i1; }else{ int res; |
︙ | ︙ | |||
1023 1024 1025 1026 1027 1028 1029 | } #else # define vdbeSorterJoinAll(x,rcin) (rcin) # define vdbeSorterJoinThread(pTask) SQLITE_OK #endif /* | | | | | | | | | | 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 | } #else # define vdbeSorterJoinAll(x,rcin) (rcin) # define vdbeSorterJoinThread(pTask) SQLITE_OK #endif /* ** Allocate a new MergeEngine object with space for nReader PmaReaders. */ static MergeEngine *vdbeMergeEngineNew(int nReader){ int N = 2; /* Smallest power of two >= nReader */ int nByte; /* Total bytes of space to allocate */ MergeEngine *pNew; /* Pointer to allocated object to return */ assert( nReader<=SORTER_MAX_MERGE_COUNT ); while( N<nReader ) N += N; nByte = sizeof(MergeEngine) + N * (sizeof(int) + sizeof(PmaReader)); pNew = sqlite3FaultSim(100) ? 0 : (MergeEngine*)sqlite3MallocZero(nByte); if( pNew ){ pNew->nTree = N; pNew->aReadr = (PmaReader*)&pNew[1]; pNew->aTree = (int*)&pNew->aReadr[N]; } return pNew; } /* ** Free the MergeEngine object passed as the only argument. */ static void vdbeMergeEngineFree(MergeEngine *pMerger){ int i; if( pMerger ){ for(i=0; i<pMerger->nTree; i++){ vdbePmaReaderClear(&pMerger->aReadr[i]); } } sqlite3_free(pMerger); } /* ** Free all resources associated with the IncrMerger object indicated by |
︙ | ︙ | |||
1435 1436 1437 1438 1439 1440 1441 | vdbeSorterWorkDebug(pTask, "exit"); assert( rc!=SQLITE_OK || pList->pList==0 ); assert( rc!=SQLITE_OK || pTask->file.iEof==iSz ); return rc; } /* | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 | vdbeSorterWorkDebug(pTask, "exit"); assert( rc!=SQLITE_OK || pList->pList==0 ); assert( rc!=SQLITE_OK || pTask->file.iEof==iSz ); return rc; } /* ** Advance the MergeEngine PmaReader passed as the second argument to ** the next entry. Set *pbEof to true if this means the PmaReader has ** reached EOF. ** ** Return SQLITE_OK if successful or an error code if an error occurs. */ static int vdbeSorterNext( SortSubtask *pTask, MergeEngine *pMerger, int *pbEof ){ int rc; int iPrev = pMerger->aTree[1];/* Index of PmaReader to advance */ /* Advance the current PmaReader */ rc = vdbePmaReaderNext(&pMerger->aReadr[iPrev]); /* Update contents of aTree[] */ if( rc==SQLITE_OK ){ int i; /* Index of aTree[] to recalculate */ PmaReader *pReadr1; /* First PmaReader to compare */ PmaReader *pReadr2; /* Second PmaReader to compare */ u8 *pKey2; /* To pReadr2->aKey, or 0 if record cached */ /* Find the first two PmaReaders to compare. The one that was just ** advanced (iPrev) and the one next to it in the array. */ pReadr1 = &pMerger->aReadr[(iPrev & 0xFFFE)]; pReadr2 = &pMerger->aReadr[(iPrev | 0x0001)]; pKey2 = pReadr2->aKey; for(i=(pMerger->nTree+iPrev)/2; i>0; i=i/2){ /* Compare pReadr1 and pReadr2. Store the result in variable iRes. */ int iRes; if( pReadr1->pFile==0 ){ iRes = +1; }else if( pReadr2->pFile==0 ){ iRes = -1; }else{ iRes = vdbeSorterCompare(pTask, pReadr1->aKey, pReadr1->nKey, pKey2, pReadr2->nKey ); } /* If pReadr1 contained the smaller value, set aTree[i] to its index. ** Then set pReadr2 to the next PmaReader to compare to pReadr1. In this ** case there is no cache of pReadr2 in pTask->pUnpacked, so set ** pKey2 to point to the record belonging to pReadr2. ** ** Alternatively, if pReadr2 contains the smaller of the two values, ** set aTree[i] to its index and update pReadr1. If vdbeSorterCompare() ** was actually called above, then pTask->pUnpacked now contains ** a value equivalent to pReadr2. So set pKey2 to NULL to prevent ** vdbeSorterCompare() from decoding pReadr2 again. ** ** If the two values were equal, then the value from the oldest ** PMA should be considered smaller. The VdbeSorter.aReadr[] array ** is sorted from oldest to newest, so pReadr1 contains older values ** than pReadr2 iff (pReadr1<pReadr2). */ if( iRes<0 || (iRes==0 && pReadr1<pReadr2) ){ pMerger->aTree[i] = (int)(pReadr1 - pMerger->aReadr); pReadr2 = &pMerger->aReadr[ pMerger->aTree[i ^ 0x0001] ]; pKey2 = pReadr2->aKey; }else{ if( pReadr1->pFile ) pKey2 = 0; pMerger->aTree[i] = (int)(pReadr2 - pMerger->aReadr); pReadr1 = &pMerger->aReadr[ pMerger->aTree[i ^ 0x0001] ]; } } *pbEof = (pMerger->aReadr[pMerger->aTree[1]].pFile==0); } return (rc==SQLITE_OK ? pTask->pUnpacked->errCode : rc); } #if SQLITE_MAX_WORKER_THREADS>0 /* |
︙ | ︙ | |||
1705 1706 1707 1708 1709 1710 1711 | assert( pIncr->bEof==0 ); vdbeSorterPopulateDebug(pTask, "enter"); vdbePmaWriterInit(pOut->pFd, &writer, pTask->pSorter->pgsz, iStart); while( rc==SQLITE_OK ){ int dummy; | | | 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 | assert( pIncr->bEof==0 ); vdbeSorterPopulateDebug(pTask, "enter"); vdbePmaWriterInit(pOut->pFd, &writer, pTask->pSorter->pgsz, iStart); while( rc==SQLITE_OK ){ int dummy; PmaReader *pReader = &pMerger->aReadr[ pMerger->aTree[1] ]; int nKey = pReader->nKey; i64 iEof = writer.iWriteOff + writer.iBufEnd; /* Check if the output file is full or if the input has been exhausted. ** In either case exit the loop. */ if( pReader->pFile==0 ) break; if( (iEof + nKey + sqlite3VarintLen(nKey))>(iStart + pIncr->mxSz) ) break; |
︙ | ︙ | |||
1751 1752 1753 1754 1755 1756 1757 | return vdbeSorterCreateThread(pIncr->pTask, vdbeIncrPopulateThread, p); } #endif /* ** This function is called when the PmaReader corresponding to pIncr has ** finished reading the contents of aFile[0]. Its purpose is to "refill" | | | 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 | return vdbeSorterCreateThread(pIncr->pTask, vdbeIncrPopulateThread, p); } #endif /* ** This function is called when the PmaReader corresponding to pIncr has ** finished reading the contents of aFile[0]. Its purpose is to "refill" ** aFile[0] such that the PmaReader should start rereading it from the ** beginning. ** ** For single-threaded objects, this is accomplished by literally reading ** keys from pIncr->pMerger and repopulating aFile[0]. ** ** For multi-threaded objects, all that is required is to wait until the ** background thread is finished (if it is not already) and then swap |
︙ | ︙ | |||
1837 1838 1839 1840 1841 1842 1843 | pIncr->pTask->file2.iEof -= pIncr->mxSz; } #endif /* SQLITE_MAX_WORKER_THREADS>0 */ #define INCRINIT_NORMAL 0 #define INCRINIT_TASK 1 #define INCRINIT_ROOT 2 | | | | | | | | | | | | | | | | | | | | | | | 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 | pIncr->pTask->file2.iEof -= pIncr->mxSz; } #endif /* SQLITE_MAX_WORKER_THREADS>0 */ #define INCRINIT_NORMAL 0 #define INCRINIT_TASK 1 #define INCRINIT_ROOT 2 static int vdbePmaReaderIncrInit(PmaReader *pReadr, int eMode); /* ** Initialize the merger argument passed as the second argument. Once this ** function returns, the first key of merged data may be read from the merger ** object in the usual fashion. ** ** If argument eMode is INCRINIT_ROOT, then it is assumed that any IncrMerge ** objects attached to the PmaReader objects that the merger reads from have ** already been populated, but that they have not yet populated aFile[0] and ** set the PmaReader objects up to read from it. In this case all that is ** required is to call vdbePmaReaderNext() on each PmaReader to point it at ** its first key. ** ** Otherwise, if eMode is any value other than INCRINIT_ROOT, then use ** vdbePmaReaderIncrInit() to initialize each PmaReader that feeds data ** to pMerger. ** ** SQLITE_OK is returned if successful, or an SQLite error code otherwise. */ static int vdbeIncrInitMerger( SortSubtask *pTask, MergeEngine *pMerger, int eMode /* One of the INCRINIT_XXX constants */ ){ int rc = SQLITE_OK; /* Return code */ int i; /* For looping over PmaReader objects */ int nTree = pMerger->nTree; for(i=0; rc==SQLITE_OK && i<nTree; i++){ if( eMode==INCRINIT_ROOT ){ /* PmaReaders should be normally initialized in order, as if they are ** reading from the same temp file this makes for more linear file IO. ** However, in the INCRINIT_ROOT case, if PmaReader aReadr[nTask-1] is ** in use it will block the vdbePmaReaderNext() call while it uses ** the main thread to fill its buffer. So calling PmaReaderNext() ** on this PmaReader before any of the multi-threaded PmaReaders takes ** better advantage of multi-processor hardware. */ rc = vdbePmaReaderNext(&pMerger->aReadr[nTree-i-1]); }else{ rc = vdbePmaReaderIncrInit(&pMerger->aReadr[i], INCRINIT_NORMAL); } } for(i=pMerger->nTree-1; rc==SQLITE_OK && i>0; i--){ rc = vdbeSorterDoCompare(pTask, pMerger, i); } return (rc==SQLITE_OK ? pTask->pUnpacked->errCode : rc); } /* ** If the PmaReader passed as the first argument is not an incremental-reader ** (if pReadr->pIncr==0), then this function is a no-op. Otherwise, it serves ** to open and/or initialize the temp file related fields of the IncrMerge ** object at (pReadr->pIncr). ** ** If argument eMode is set to INCRINIT_NORMAL, then PmaReader PmaReaders ** in the sub-tree headed by pReadr are also initialized. Data is then loaded ** into the buffers belonging to this PmaReader, pReadr, and it is set to ** point to the first key in its range. ** ** If argument eMode is set to INCRINIT_TASK, then PmaReader is guaranteed ** to be a multi-threaded PmaReader and this function is being called in a ** background thread. In this case all PmaReaders in the sub-tree are ** initialized as for INCRINIT_NORMAL and the aFile[1] buffer belonging to ** pReadr is populated. However, the PmaReader itself is not set up to point ** to its first key. A call to vdbePmaReaderNext() is still required to do ** that. ** ** The reason this function does not call vdbePmaReaderNext() immediately ** in the INCRINIT_TASK case is that vdbePmaReaderNext() assumes that has ** to block on thread (pTask->thread) before accessing aFile[1]. But, since ** this entire function is being run by thread (pTask->thread), that will ** lead to the current background thread attempting to join itself. ** ** Finally, if argument eMode is set to INCRINIT_ROOT, it may be assumed ** that pReadr->pIncr is a multi-threaded IncrMerge objects, and that all ** child-trees have already been initialized using IncrInit(INCRINIT_TASK). ** In this case vdbePmaReaderNext() is called on all child PmaReaders and ** the current PmaReader set to point to the first key in its range. ** ** SQLITE_OK is returned if successful, or an SQLite error code otherwise. */ static int vdbePmaReaderIncrInit(PmaReader *pReadr, int eMode){ int rc = SQLITE_OK; IncrMerger *pIncr = pReadr->pIncr; if( pIncr ){ SortSubtask *pTask = pIncr->pTask; sqlite3 *db = pTask->pSorter->db; rc = vdbeIncrInitMerger(pTask, pIncr->pMerger, eMode); /* Set up the required files for pIncr. A multi-theaded IncrMerge object |
︙ | ︙ | |||
1960 1961 1962 1963 1964 1965 1966 | } } } #if SQLITE_MAX_WORKER_THREADS>0 if( rc==SQLITE_OK && pIncr->bUseThread ){ /* Use the current thread to populate aFile[1], even though this | | | | 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 | } } } #if SQLITE_MAX_WORKER_THREADS>0 if( rc==SQLITE_OK && pIncr->bUseThread ){ /* Use the current thread to populate aFile[1], even though this ** PmaReader is multi-threaded. The reason being that this function ** is already running in background thread pIncr->pTask->thread. */ assert( eMode==INCRINIT_ROOT || eMode==INCRINIT_TASK ); rc = vdbeIncrPopulate(pIncr); } #endif if( rc==SQLITE_OK && eMode!=INCRINIT_TASK ){ rc = vdbePmaReaderNext(pReadr); } } return rc; } #if SQLITE_MAX_WORKER_THREADS>0 /* |
︙ | ︙ | |||
1990 1991 1992 1993 1994 1995 1996 | return pRet; } /* ** Use a background thread to invoke vdbePmaReaderIncrInit(INCRINIT_TASK) ** on the the PmaReader object passed as the first argument. ** | | | | | | | | | | 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 | return pRet; } /* ** Use a background thread to invoke vdbePmaReaderIncrInit(INCRINIT_TASK) ** on the the PmaReader object passed as the first argument. ** ** This call will initialize the various fields of the pReadr->pIncr ** structure and, if it is a multi-threaded IncrMerger, launch a ** background thread to populate aFile[1]. */ static int vdbePmaReaderBgIncrInit(PmaReader *pReadr){ void *pCtx = (void*)pReadr; return vdbeSorterCreateThread(pReadr->pIncr->pTask, vdbePmaReaderBgInit, pCtx); } #endif /* ** Allocate a new MergeEngine object to merge the contents of nPMA level-0 ** PMAs from pTask->file. If no error occurs, set *ppOut to point to ** the new object and return SQLITE_OK. Or, if an error does occur, set *ppOut ** to NULL and return an SQLite error code. ** ** When this function is called, *piOffset is set to the offset of the ** first PMA to read from pTask->file. Assuming no error occurs, it is ** set to the offset immediately following the last byte of the last ** PMA before returning. If an error does occur, then the final value of ** *piOffset is undefined. */ static int vdbeMergeEngineLevel0( SortSubtask *pTask, /* Sorter task to read from */ int nPMA, /* Number of PMAs to read */ i64 *piOffset, /* IN/OUT: Readr offset in pTask->file */ MergeEngine **ppOut /* OUT: New merge-engine */ ){ MergeEngine *pNew; /* Merge engine to return */ i64 iOff = *piOffset; int i; int rc = SQLITE_OK; *ppOut = pNew = vdbeMergeEngineNew(nPMA); if( pNew==0 ) rc = SQLITE_NOMEM; for(i=0; i<nPMA && rc==SQLITE_OK; i++){ i64 nDummy; PmaReader *pReadr = &pNew->aReadr[i]; rc = vdbePmaReaderInit(pTask, &pTask->file, iOff, pReadr, &nDummy); iOff = pReadr->iEof; } if( rc!=SQLITE_OK ){ vdbeMergeEngineFree(pNew); *ppOut = 0; } *piOffset = iOff; |
︙ | ︙ | |||
2090 2091 2092 2093 2094 2095 2096 | for(i=1; i<nDepth; i++){ nDiv = nDiv * SORTER_MAX_MERGE_COUNT; } for(i=1; i<nDepth && rc==SQLITE_OK; i++){ int iIter = (iSeq / nDiv) % SORTER_MAX_MERGE_COUNT; | | | | | | | 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 | for(i=1; i<nDepth; i++){ nDiv = nDiv * SORTER_MAX_MERGE_COUNT; } for(i=1; i<nDepth && rc==SQLITE_OK; i++){ int iIter = (iSeq / nDiv) % SORTER_MAX_MERGE_COUNT; PmaReader *pReadr = &p->aReadr[iIter]; if( pReadr->pIncr==0 ){ MergeEngine *pNew = vdbeMergeEngineNew(SORTER_MAX_MERGE_COUNT); if( pNew==0 ){ rc = SQLITE_NOMEM; }else{ rc = vdbeIncrNew(pTask, pNew, &pReadr->pIncr); } } if( rc==SQLITE_OK ){ p = pReadr->pIncr->pMerger; nDiv = nDiv / SORTER_MAX_MERGE_COUNT; } } if( rc==SQLITE_OK ){ p->aReadr[iSeq % SORTER_MAX_MERGE_COUNT].pIncr = pIncr; }else{ vdbeIncrFree(pIncr); } return rc; } /* |
︙ | ︙ | |||
2170 2171 2172 2173 2174 2175 2176 | } } } if( rc==SQLITE_OK ){ #if SQLITE_MAX_WORKER_THREADS>0 if( pMain!=0 ){ | | | 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 | } } } if( rc==SQLITE_OK ){ #if SQLITE_MAX_WORKER_THREADS>0 if( pMain!=0 ){ rc = vdbeIncrNew(pTask, pRoot, &pMain->aReadr[iTask].pIncr); }else #endif { assert( pMain==0 ); pMain = pRoot; } }else{ |
︙ | ︙ | |||
2214 2215 2216 2217 2218 2219 2220 | rc = vdbeSorterMergeTreeBuild(pSorter, &pMain); if( rc==SQLITE_OK ){ #if SQLITE_MAX_WORKER_THREADS assert( pSorter->bUseThreads==0 || pSorter->nTask>1 ); if( pSorter->bUseThreads ){ int iTask; | | | | | | | | | | | 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 | rc = vdbeSorterMergeTreeBuild(pSorter, &pMain); if( rc==SQLITE_OK ){ #if SQLITE_MAX_WORKER_THREADS assert( pSorter->bUseThreads==0 || pSorter->nTask>1 ); if( pSorter->bUseThreads ){ int iTask; PmaReader *pReadr; SortSubtask *pLast = &pSorter->aTask[pSorter->nTask-1]; rc = vdbeSortAllocUnpacked(pLast); if( rc==SQLITE_OK ){ pReadr = (PmaReader*)sqlite3DbMallocZero(db, sizeof(PmaReader)); pSorter->pReader = pReadr; if( pReadr==0 ) rc = SQLITE_NOMEM; } if( rc==SQLITE_OK ){ rc = vdbeIncrNew(pLast, pMain, &pReadr->pIncr); if( rc==SQLITE_OK ){ vdbeIncrSetThreads(pReadr->pIncr); for(iTask=0; iTask<(pSorter->nTask-1); iTask++){ IncrMerger *pIncr; if( (pIncr = pMain->aReadr[iTask].pIncr) ){ vdbeIncrSetThreads(pIncr); assert( pIncr->pTask!=pLast ); } } for(iTask=0; rc==SQLITE_OK && iTask<pSorter->nTask; iTask++){ PmaReader *p = &pMain->aReadr[iTask]; assert( p->pIncr==0 || p->pIncr->pTask==&pSorter->aTask[iTask] ); if( p->pIncr ){ if( iTask==pSorter->nTask-1 ){ rc = vdbePmaReaderIncrInit(p, INCRINIT_TASK); }else{ rc = vdbePmaReaderBgIncrInit(p); } } } } pMain = 0; } if( rc==SQLITE_OK ){ rc = vdbePmaReaderIncrInit(pReadr, INCRINIT_ROOT); } }else #endif { rc = vdbeIncrInitMerger(pTask0, pMain, INCRINIT_NORMAL); pSorter->pMerger = pMain; pMain = 0; |
︙ | ︙ | |||
2363 2364 2365 2366 2367 2368 2369 | PmaReader *pReader; #if SQLITE_MAX_WORKER_THREADS>0 if( pSorter->bUseThreads ){ pReader = pSorter->pReader; }else #endif /*if( !pSorter->bUseThreads )*/{ | | | 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 | PmaReader *pReader; #if SQLITE_MAX_WORKER_THREADS>0 if( pSorter->bUseThreads ){ pReader = pSorter->pReader; }else #endif /*if( !pSorter->bUseThreads )*/{ pReader = &pSorter->pMerger->aReadr[pSorter->pMerger->aTree[1]]; } *pnKey = pReader->nKey; pKey = pReader->aKey; }else{ *pnKey = pSorter->list.pList->nVal; pKey = SRVAL(pSorter->list.pList); } |
︙ | ︙ |