Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Improve performance of multi-field sorts where the first field has a low cardinality. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | sorter-opt |
Files: | files | file ages | folders |
SHA1: |
601e7b6b8e6bfabda03b70f75094c901 |
User & Date: | dan 2015-03-30 12:06:26.995 |
Context
2015-04-01
| ||
16:18 | Reduce the CPU used by CREATE INDEX statements by taking better advantage of the fact that keys are inserted in sorted order. (check-in: 592cdc5d72 user: dan tags: sorter-opt) | |
2015-03-30
| ||
19:56 | Optimize CREATE INDEX, REINDEX and VACUUM statements by taking better advantage of the fact that index keys are being inserted into b-trees in sorted order. (Leaf check-in: 763d2bc74b user: dan tags: mistake) | |
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) | |
09:58 | Remove some unnecessary code from vdbesort.c. (check-in: b58191e917 user: dan tags: sorter-opt) | |
Changes
Changes to src/vdbe.h.
︙ | ︙ | |||
209 210 211 212 213 214 215 216 217 218 219 220 221 222 | #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*); UnpackedRecord *sqlite3VdbeAllocUnpackedRecord(KeyInfo *, char *, int, char **); typedef int (*RecordCompare)(int,const void*,UnpackedRecord*); RecordCompare sqlite3VdbeFindCompare(UnpackedRecord*); #ifndef SQLITE_OMIT_TRIGGER void sqlite3VdbeLinkSubProgram(Vdbe *, SubProgram *); | > | 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 | ** 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). */ | | | 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). */ int sqlite3VdbeRecordCompareWithSkip( int nKey1, const void *pKey1, /* Left key */ UnpackedRecord *pPKey2, /* Right key */ int bSkip /* If true, skip the first field */ ){ u32 d1; /* Offset into aKey[] of next data element */ int i; /* Index of next field to compare */ u32 szHdr1; /* Size of record header in bytes */ |
︙ | ︙ | |||
3767 3768 3769 3770 3771 3772 3773 | ); return pPKey2->default_rc; } int sqlite3VdbeRecordCompare( int nKey1, const void *pKey1, /* Left key */ UnpackedRecord *pPKey2 /* Right key */ ){ | | | 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 */ ){ return sqlite3VdbeRecordCompareWithSkip(nKey1, pKey1, pPKey2, 0); } /* ** This function is an optimized version of sqlite3VdbeRecordCompare() ** that (a) the first field of pPKey2 is an integer, and (b) the ** size-of-header varint at the start of (pKey1/nKey1) fits in a single |
︙ | ︙ | |||
3855 3856 3857 3858 3859 3860 3861 | 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. */ | | | 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. */ res = sqlite3VdbeRecordCompareWithSkip(nKey1, pKey1, pPKey2, 1); }else{ /* The first fields of the two keys are equal and there are no trailing ** fields. Return pPKey2->default_rc in this case. */ res = pPKey2->default_rc; } assert( vdbeRecordCompareDebug(nKey1, pKey1, pPKey2, res) ); |
︙ | ︙ | |||
3903 3904 3905 3906 3907 3908 3909 | 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 ){ | | | 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 ){ res = sqlite3VdbeRecordCompareWithSkip(nKey1, pKey1, pPKey2, 1); }else{ res = pPKey2->default_rc; } }else if( res>0 ){ res = pPKey2->r2; }else{ res = pPKey2->r1; |
︙ | ︙ |
Changes to src/vdbesort.c.
︙ | ︙ | |||
744 745 746 747 748 749 750 751 752 753 754 755 756 757 | } 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, | > > > > > > > > > > > > > > > > > > > | 744 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 | } 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, |
︙ | ︙ | |||
801 802 803 804 805 806 807 | res = memcmp(v1, v2, MIN(n1, n2)); if( res==0 ){ res = n1 - n2; } if( res==0 ){ if( pTask->pSorter->pKeyInfo->nField>1 ){ | > | > | 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 | res = memcmp(v1, v2, MIN(n1, n2)); if( res==0 ){ res = n1 - n2; } if( res==0 ){ if( pTask->pSorter->pKeyInfo->nField>1 ){ res = vdbeSorterCompareTail( pTask, pbKey2Cached, pKey1, nKey1, pKey2, nKey2 ); } }else{ if( pTask->pSorter->pKeyInfo->aSortOrder[0] ){ res = res * -1; } } |
︙ | ︙ | |||
868 869 870 871 872 873 874 | if( *v2 & 0x80 ) res = +1; } } } if( res==0 ){ if( pTask->pSorter->pKeyInfo->nField>1 ){ | > | > | 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 | if( *v2 & 0x80 ) res = +1; } } } if( res==0 ){ if( pTask->pSorter->pKeyInfo->nField>1 ){ res = vdbeSorterCompareTail( pTask, pbKey2Cached, pKey1, nKey1, pKey2, nKey2 ); } }else if( pTask->pSorter->pKeyInfo->aSortOrder[0] ){ res = res * -1; } return res; } |
︙ | ︙ |