Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Further optimizations for sorting records that begin with integer or text values. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | sorter-opt |
Files: | files | file ages | folders |
SHA1: |
24fe9f25d64ee516633fed1ae7ebc215 |
User & Date: | dan 2015-03-28 19:56:41.373 |
Context
2015-03-30
| ||
09:58 | Remove some unnecessary code from vdbesort.c. (check-in: b58191e917 user: dan tags: sorter-opt) | |
2015-03-28
| ||
19:56 | Further optimizations for sorting records that begin with integer or text values. (check-in: 24fe9f25d6 user: dan tags: sorter-opt) | |
2015-03-26
| ||
11:55 | Optimize cases where all the sorter is sorting a set of records that all begin with integer values, or that all begin with text values to be compared using BINARY. (check-in: ce5ad17c25 user: dan tags: sorter-opt) | |
Changes
Changes to src/vdbesort.c.
︙ | ︙ | |||
287 288 289 290 291 292 293 294 295 296 297 298 299 300 | ** to sqlite3ThreadJoin() is likely to block. Cases that are likely to ** block provoke debugging output. ** ** In both cases, the effects of the main thread seeing (bDone==0) even ** after the thread has finished are not dire. So we don't worry about ** memory barriers and such here. */ struct SortSubtask { SQLiteThread *pThread; /* Background thread, if any */ int bDone; /* Set if thread is finished but not joined */ VdbeSorter *pSorter; /* Sorter that owns this sub-task */ UnpackedRecord *pUnpacked; /* Space to unpack a record */ SorterList list; /* List for thread to write to a PMA */ int nPMA; /* Number of PMAs currently in file */ | > | > | 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 | ** to sqlite3ThreadJoin() is likely to block. Cases that are likely to ** block provoke debugging output. ** ** In both cases, the effects of the main thread seeing (bDone==0) even ** after the thread has finished are not dire. So we don't worry about ** memory barriers and such here. */ typedef int (*SorterCompare)(SortSubtask*,int*,const void*,int,const void*,int); struct SortSubtask { SQLiteThread *pThread; /* Background thread, if any */ int bDone; /* Set if thread is finished but not joined */ VdbeSorter *pSorter; /* Sorter that owns this sub-task */ UnpackedRecord *pUnpacked; /* Space to unpack a record */ SorterList list; /* List for thread to write to a PMA */ int nPMA; /* Number of PMAs currently in file */ SorterCompare xCompare; /* Compare function to use */ SorterFile file; /* Temp file for level-0 PMAs */ SorterFile file2; /* Space for other PMAs */ }; /* ** Main sorter structure. A single instance of this is allocated for each ** sorter cursor created by the VDBE. ** ** mxKeysize: ** As records are added to the sorter by calls to sqlite3VdbeSorterWrite(), |
︙ | ︙ | |||
743 744 745 746 747 748 749 | if( rc==SQLITE_OK ){ rc = vdbePmaReaderNext(pReadr); } return rc; } | < > > | | < < > | > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 | if( rc==SQLITE_OK ){ rc = vdbePmaReaderNext(pReadr); } return rc; } /* ** Compare key1 (buffer pKey1, size nKey1 bytes) with key2 (buffer pKey2, ** size nKey2 bytes). Use (pTask->pKeyInfo) for the collation sequences ** used by the comparison. Return the result of the comparison. ** ** If IN/OUT parameter *pbKey2Cached is true when this function is called, ** it is assumed that (pTask->pUnpacked) contains the unpacked version ** of key2. If it is false, (pTask->pUnpacked) is populated with the unpacked ** version of key2 and *pbKey2Cached set to true before returning. ** ** If an OOM error is encountered, (pTask->pUnpacked->error_rc) is set ** to SQLITE_NOMEM. */ static int vdbeSorterCompare( SortSubtask *pTask, /* Subtask context (for pKeyInfo) */ int *pbKey2Cached, /* True if pTask->pUnpacked is pKey2 */ const void *pKey1, int nKey1, /* Left side of comparison */ const void *pKey2, int nKey2 /* Right side of comparison */ ){ UnpackedRecord *r2 = pTask->pUnpacked; if( !*pbKey2Cached ){ sqlite3VdbeRecordUnpack(pTask->pSorter->pKeyInfo, nKey2, pKey2, r2); *pbKey2Cached = 1; } return sqlite3VdbeRecordCompare(nKey1, pKey1, r2); } /* ** A specially optimized version of vdbeSorterCompare() that assumes that ** the first field of each key is a TEXT value and that the collation ** sequence to compare them with is BINARY. */ static int vdbeSorterCompareText( SortSubtask *pTask, /* Subtask context (for pKeyInfo) */ int *pbKey2Cached, /* True if pTask->pUnpacked is pKey2 */ const void *pKey1, int nKey1, /* Left side of comparison */ const void *pKey2, int nKey2 /* Right side of comparison */ ){ const u8 * const p1 = (const u8 * const)pKey1; const u8 * const p2 = (const u8 * const)pKey2; const u8 * const v1 = &p1[ p1[0] ]; /* Pointer to value 1 */ const u8 * const v2 = &p2[ p2[0] ]; /* Pointer to value 2 */ int n1; int n2; int res; getVarint32(&p1[1], n1); n1 = (n1 - 13) / 2; getVarint32(&p2[1], n2); n2 = (n2 - 13) / 2; res = memcmp(v1, v2, MIN(n1, n2)); if( res==0 ){ res = n1 - n2; } if( res==0 ){ if( pTask->pSorter->pKeyInfo->nField>1 ){ res = vdbeSorterCompare(pTask, pbKey2Cached, pKey1, nKey1, pKey2, nKey2); } }else{ if( pTask->pSorter->pKeyInfo->aSortOrder[0] ){ res = res * -1; } } return res; } /* ** A specially optimized version of vdbeSorterCompare() that assumes that ** the first field of each key is an INTEGER value. */ static int vdbeSorterCompareInt( SortSubtask *pTask, /* Subtask context (for pKeyInfo) */ int *pbKey2Cached, /* True if pTask->pUnpacked is pKey2 */ const void *pKey1, int nKey1, /* Left side of comparison */ const void *pKey2, int nKey2 /* Right side of comparison */ ){ const u8 * const p1 = (const u8 * const)pKey1; const u8 * const p2 = (const u8 * const)pKey2; const int s1 = p1[1]; /* Left hand serial type */ const int s2 = p2[1]; /* Right hand serial type */ const u8 * const v1 = &p1[ p1[0] ]; /* Pointer to value 1 */ const u8 * const v2 = &p2[ p2[0] ]; /* Pointer to value 2 */ int res; /* Return value */ assert( (s1>0 && s1<7) || s1==8 || s1==9 ); assert( (s2>0 && s2<7) || s2==8 || s2==9 ); if( s1>7 && s2>7 ){ res = s1 - s2; }else{ if( s1==s2 ){ if( (*v1 ^ *v2) & 0x80 ){ /* The two values have different signs */ res = (*v1 & 0x80) ? -1 : +1; }else{ /* The two values have the same sign. Compare using memcmp(). */ static const u8 aLen[] = {0, 1, 2, 3, 4, 6, 8 }; int i; res = 0; for(i=0; i<aLen[s1]; i++){ if( (res = v1[i] - v2[i]) ) break; } } }else{ if( s2>7 ){ res = +1; }else if( s1>7 ){ res = -1; }else{ res = s1 - s2; } if( res>0 ){ if( *v1 & 0x80 ) res = -1; }else if( res<0 ){ if( *v2 & 0x80 ) res = +1; } } } if( res==0 ){ if( pTask->pSorter->pKeyInfo->nField>1 ){ res = vdbeSorterCompare(pTask, pbKey2Cached, pKey1, nKey1, pKey2, nKey2); } }else if( pTask->pSorter->pKeyInfo->aSortOrder[0] ){ res = res * -1; } return res; } /* ** Initialize the temporary index cursor just opened as a sorter cursor. ** ** Usually, the sorter module uses the value of (pCsr->pKeyInfo->nField) ** to determine the number of fields that should be compared from the |
︙ | ︙ | |||
869 870 871 872 873 874 875 | assert( pSorter->iMemory==0 ); pSorter->nMemory = pgsz; pSorter->list.aMemory = (u8*)sqlite3Malloc(pgsz); if( !pSorter->list.aMemory ) rc = SQLITE_NOMEM; } } | | > > | 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 | assert( pSorter->iMemory==0 ); pSorter->nMemory = pgsz; pSorter->list.aMemory = (u8*)sqlite3Malloc(pgsz); if( !pSorter->list.aMemory ) rc = SQLITE_NOMEM; } } if( (pKeyInfo->nField+pKeyInfo->nXField)<13 && (pKeyInfo->aColl[0]==0 || pKeyInfo->aColl[0]==db->pDfltColl) ){ pSorter->typeMask = SORTER_TYPE_INTEGER | SORTER_TYPE_TEXT; } } return rc; } #undef nWorker /* Defined at the top of this function */ |
︙ | ︙ | |||
1215 1216 1217 1218 1219 1220 1221 | SortSubtask *pTask, /* Calling thread context */ SorterRecord *p1, /* First list to merge */ SorterRecord *p2, /* Second list to merge */ SorterRecord **ppOut /* OUT: Head of merged list */ ){ SorterRecord *pFinal = 0; SorterRecord **pp = &pFinal; | | > | > > < | < | > > > > > > > > > > > > > < | < < < < < | 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 | SortSubtask *pTask, /* Calling thread context */ SorterRecord *p1, /* First list to merge */ SorterRecord *p2, /* Second list to merge */ SorterRecord **ppOut /* OUT: Head of merged list */ ){ SorterRecord *pFinal = 0; SorterRecord **pp = &pFinal; int bCached = 0; while( p1 && p2 ){ int res; res = pTask->xCompare( pTask, &bCached, SRVAL(p1), p1->nVal, SRVAL(p2), p2->nVal ); if( res<=0 ){ *pp = p1; pp = &p1->u.pNext; p1 = p1->u.pNext; }else{ *pp = p2; pp = &p2->u.pNext; p2 = p2->u.pNext; bCached = 0; } } *pp = p1 ? p1 : p2; *ppOut = pFinal; } /* ** Return the SorterCompare function to compare values collected by the ** sorter object passed as the only argument. */ static SorterCompare vdbeSorterGetCompare(VdbeSorter *p){ if( p->typeMask==SORTER_TYPE_INTEGER ){ return vdbeSorterCompareInt; }else if( p->typeMask==SORTER_TYPE_TEXT ){ return vdbeSorterCompareText; } return vdbeSorterCompare; } /* ** Sort the linked list of records headed at pTask->pList. Return ** SQLITE_OK if successful, or an SQLite error code (i.e. SQLITE_NOMEM) if ** an error occurs. */ static int vdbeSorterSort(SortSubtask *pTask, SorterList *pList){ int i; SorterRecord **aSlot; SorterRecord *p; int rc; rc = vdbeSortAllocUnpacked(pTask); if( rc!=SQLITE_OK ) return rc; p = pList->pList; pTask->xCompare = vdbeSorterGetCompare(pTask->pSorter); aSlot = (SorterRecord **)sqlite3MallocZero(64 * sizeof(SorterRecord *)); if( !aSlot ){ return SQLITE_NOMEM; } while( p ){ |
︙ | ︙ | |||
1478 1479 1480 1481 1482 1483 1484 | 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 */ | | < | | | 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 | 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 */ int bCached = 0; /* 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)]; 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->pFd==0 ){ iRes = +1; }else if( pReadr2->pFd==0 ){ iRes = -1; }else{ iRes = pTask->xCompare(pTask, &bCached, pReadr1->aKey, pReadr1->nKey, pReadr2->aKey, 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. |
︙ | ︙ | |||
1517 1518 1519 1520 1521 1522 1523 | ** 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] ]; | | | | 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 | ** 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] ]; bCached = 0; }else{ bCached = (pReadr1->pFd!=0); pMerger->aTree[i] = (int)(pReadr2 - pMerger->aReadr); pReadr1 = &pMerger->aReadr[ pMerger->aTree[i ^ 0x0001] ]; } } *pbEof = (pMerger->aReadr[pMerger->aTree[1]].pFd==0); } |
︙ | ︙ | |||
1631 1632 1633 1634 1635 1636 1637 | int nReq; /* Bytes of memory required */ int nPMA; /* Bytes of PMA space required */ int t; /* serial type of first record field */ getVarint32((const u8*)&pVal->z[1], t); if( t>0 && t<10 && t!=7 ){ pSorter->typeMask &= SORTER_TYPE_INTEGER; | | | 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 | int nReq; /* Bytes of memory required */ int nPMA; /* Bytes of PMA space required */ int t; /* serial type of first record field */ getVarint32((const u8*)&pVal->z[1], t); if( t>0 && t<10 && t!=7 ){ pSorter->typeMask &= SORTER_TYPE_INTEGER; }else if( t>10 && (t & 0x01) ){ pSorter->typeMask &= SORTER_TYPE_TEXT; }else{ pSorter->typeMask = 0; } assert( pSorter ); |
︙ | ︙ | |||
1901 1902 1903 1904 1905 1906 1907 1908 | p2 = &pMerger->aReadr[i2]; if( p1->pFd==0 ){ iRes = i2; }else if( p2->pFd==0 ){ iRes = i1; }else{ int res; | > > | | | | 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 | p2 = &pMerger->aReadr[i2]; if( p1->pFd==0 ){ iRes = i2; }else if( p2->pFd==0 ){ iRes = i1; }else{ SortSubtask *pTask = pMerger->pTask; int bCached = 0; int res; assert( pTask->pUnpacked!=0 ); /* from vdbeSortSubtaskMain() */ res = pTask->xCompare( pTask, &bCached, p1->aKey, p1->nKey, p2->aKey, p2->nKey ); if( res<=0 ){ iRes = i1; }else{ iRes = i2; } } |
︙ | ︙ | |||
2322 2323 2324 2325 2326 2327 2328 | */ static int vdbeSorterSetupMerge(VdbeSorter *pSorter){ int rc; /* Return code */ SortSubtask *pTask0 = &pSorter->aTask[0]; MergeEngine *pMain = 0; #if SQLITE_MAX_WORKER_THREADS sqlite3 *db = pTask0->pSorter->db; | < < < > | 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 | */ static int vdbeSorterSetupMerge(VdbeSorter *pSorter){ int rc; /* Return code */ SortSubtask *pTask0 = &pSorter->aTask[0]; MergeEngine *pMain = 0; #if SQLITE_MAX_WORKER_THREADS sqlite3 *db = pTask0->pSorter->db; int i; SorterCompare xCompare = vdbeSorterGetCompare(pSorter); for(i=0; i<pSorter->nTask; i++){ pSorter->aTask[i].xCompare = xCompare; } #endif rc = vdbeSorterMergeTreeBuild(pSorter, &pMain); if( rc==SQLITE_OK ){ |
︙ | ︙ |