Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Merge sorter optimizations with this branch. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | insert-select-opt |
Files: | files | file ages | folders |
SHA1: |
9bf1cfb4d99328bb95567330fdae7651 |
User & Date: | dan 2015-03-30 15:45:45.183 |
Context
2015-04-10
| ||
08:28 | Update this branch with the latest changes from sorter-opt. (Leaf check-in: 08c0b19b89 user: dan tags: insert-select-opt) | |
2015-03-30
| ||
15:45 | Merge sorter optimizations with this branch. (check-in: 9bf1cfb4d9 user: dan tags: insert-select-opt) | |
12:06 | Improve performance of multi-field sorts where the first field has a low cardinality. (check-in: 601e7b6b8e user: dan tags: sorter-opt) | |
2015-03-26
| ||
12:38 | Merge sorter optimization into this branch. (check-in: aeb8e9a9f2 user: dan tags: insert-select-opt) | |
Changes
Changes to src/vdbe.h.
︙ | |||
209 210 211 212 213 214 215 216 217 218 219 220 221 222 | 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 | + | #ifndef SQLITE_OMIT_TRACE char *sqlite3VdbeExpandSql(Vdbe*, const char*); #endif int sqlite3MemCompare(const Mem*, const Mem*, const CollSeq*); void sqlite3VdbeRecordUnpack(KeyInfo*,int,const void*,UnpackedRecord*); int sqlite3VdbeRecordCompare(int,const void*,UnpackedRecord*); int sqlite3VdbeRecordCompareWithSkip(int, const void *, UnpackedRecord *, int); UnpackedRecord *sqlite3VdbeAllocUnpackedRecord(KeyInfo *, char *, int, char **); typedef int (*RecordCompare)(int,const void*,UnpackedRecord*); RecordCompare sqlite3VdbeFindCompare(UnpackedRecord*); #ifndef SQLITE_OMIT_TRIGGER void sqlite3VdbeLinkSubProgram(Vdbe *, SubProgram *); |
︙ |
Changes to src/vdbeaux.c.
︙ | |||
3581 3582 3583 3584 3585 3586 3587 | 3581 3582 3583 3584 3585 3586 3587 3588 3589 3590 3591 3592 3593 3594 3595 | - + | ** returned. ** ** If database corruption is discovered, set pPKey2->errCode to ** SQLITE_CORRUPT and return 0. If an OOM error is encountered, ** pPKey2->errCode is set to SQLITE_NOMEM and, if it is not NULL, the ** malloc-failed flag set on database handle (pPKey2->pKeyInfo->db). */ |
︙ | |||
3767 3768 3769 3770 3771 3772 3773 | 3767 3768 3769 3770 3771 3772 3773 3774 3775 3776 3777 3778 3779 3780 3781 | - + | ); return pPKey2->default_rc; } int sqlite3VdbeRecordCompare( int nKey1, const void *pKey1, /* Left key */ UnpackedRecord *pPKey2 /* Right key */ ){ |
︙ | |||
3855 3856 3857 3858 3859 3860 3861 | 3855 3856 3857 3858 3859 3860 3861 3862 3863 3864 3865 3866 3867 3868 3869 | - + | if( v>lhs ){ res = pPKey2->r1; }else if( v<lhs ){ res = pPKey2->r2; }else if( pPKey2->nField>1 ){ /* The first fields of the two keys are equal. Compare the trailing ** fields. */ |
︙ | |||
3903 3904 3905 3906 3907 3908 3909 | 3903 3904 3905 3906 3907 3908 3909 3910 3911 3912 3913 3914 3915 3916 3917 | - + | nCmp = MIN( pPKey2->aMem[0].n, nStr ); res = memcmp(&aKey1[szHdr], pPKey2->aMem[0].z, nCmp); if( res==0 ){ res = nStr - pPKey2->aMem[0].n; if( res==0 ){ if( pPKey2->nField>1 ){ |
︙ |
Changes to src/vdbesort.c.
︙ | |||
287 288 289 290 291 292 293 294 295 296 297 298 299 300 | 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 */ |
︙ | |||
743 744 745 746 747 748 749 750 751 752 753 754 755 | 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 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 | + + + + + + + + + + + + + + + + + + + + - - + + - - + - + + - + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + | if( rc==SQLITE_OK ){ rc = vdbePmaReaderNext(pReadr); } return rc; } /* ** A version of vdbeSorterCompare() that assumes that it has already been ** determined that the first field of key1 is equal to the first field of ** key2. */ static int vdbeSorterCompareTail( 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==0 ){ sqlite3VdbeRecordUnpack(pTask->pSorter->pKeyInfo, nKey2, pKey2, r2); *pbKey2Cached = 1; } return sqlite3VdbeRecordCompareWithSkip(nKey1, pKey1, r2, 1); } /* ** 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 |
︙ | |||
869 870 871 872 873 874 875 | 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 | - + + + | assert( pSorter->iMemory==0 ); pSorter->nMemory = pgsz; pSorter->list.aMemory = (u8*)sqlite3Malloc(pgsz); if( !pSorter->list.aMemory ) rc = SQLITE_NOMEM; } } |
︙ | |||
1191 1192 1193 1194 1195 1196 1197 | 1324 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 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 | - - - - - - - - + + - + + + - - + - - + + + + + + + + + + + + + + - - + - - - - - | pTask->pUnpacked = sqlite3VdbeAllocUnpackedRecord( pTask->pSorter->pKeyInfo, 0, 0, &pFree ); assert( pTask->pUnpacked==(UnpackedRecord*)pFree ); if( pFree==0 ) return SQLITE_NOMEM; pTask->pUnpacked->nField = pTask->pSorter->pKeyInfo->nField; pTask->pUnpacked->errCode = 0; |
︙ | |||
1478 1479 1480 1481 1482 1483 1484 | 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 | - + - - - + + | 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 */ |
︙ | |||
1517 1518 1519 1520 1521 1522 1523 | 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 | - + - + | ** 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] ]; |
︙ | |||
1631 1632 1633 1634 1635 1636 1637 | 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 | - + | 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; |
︙ | |||
1901 1902 1903 1904 1905 1906 1907 1908 | 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 | + + - - - + + + | 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; |
︙ | |||
2322 2323 2324 2325 2326 2327 2328 | 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 | - - - + | */ 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; |
︙ |