Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | The top of an index equality loop normally starts with OP_SeekGE and OP_IdxGT. This check-in adds a flag to OP_SeekGE such that it fails immediately if the key is not equal, then jumps over the OP_IdxGT, saving a call to the key comparison functions. Consider this check-in a proof-of-concept. It needs improvement before going on trunk. Some tests fail, but only because they new use fewer key comparisons than expected (which is a good thing!). |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | seekeq-experiment |
Files: | files | file ages | folders |
SHA1: |
32e31b9bc8664afcd326a1ff3892d86d |
User & Date: | drh 2015-11-05 20:25:09.480 |
Context
2015-11-05
| ||
22:30 | Improvements and simplifications to the equality seek logic. Tests are adjusted so that they all pass now. (Closed-Leaf check-in: 997ce6c90b user: drh tags: seekeq-experiment) | |
20:25 | The top of an index equality loop normally starts with OP_SeekGE and OP_IdxGT. This check-in adds a flag to OP_SeekGE such that it fails immediately if the key is not equal, then jumps over the OP_IdxGT, saving a call to the key comparison functions. Consider this check-in a proof-of-concept. It needs improvement before going on trunk. Some tests fail, but only because they new use fewer key comparisons than expected (which is a good thing!). (check-in: 32e31b9bc8 user: drh tags: seekeq-experiment) | |
18:09 | Add the 'hashsize' configuration option to fts5, for configuring the amount of memory allocated to the in-memory hash table while writing. (check-in: 445480095e user: dan tags: trunk) | |
Changes
Changes to main.mk.
︙ | ︙ | |||
578 579 580 581 582 583 584 | # Rules to build opcodes.c and opcodes.h # opcodes.c: opcodes.h $(TOP)/tool/mkopcodec.tcl tclsh $(TOP)/tool/mkopcodec.tcl opcodes.h >opcodes.c | | | 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 | # Rules to build opcodes.c and opcodes.h # opcodes.c: opcodes.h $(TOP)/tool/mkopcodec.tcl tclsh $(TOP)/tool/mkopcodec.tcl opcodes.h >opcodes.c opcodes.h: parse.h $(TOP)/tool/mkopcodeh.tcl cat parse.h $(TOP)/src/vdbe.c | \ tclsh $(TOP)/tool/mkopcodeh.tcl >opcodes.h # Rules to build parse.c and parse.h - the outputs of lemon. # parse.h: parse.c |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 | ** into its constituent fields. ** ** The r1 and r2 member variables are only used by the optimized comparison ** functions vdbeRecordCompareInt() and vdbeRecordCompareString(). */ struct UnpackedRecord { KeyInfo *pKeyInfo; /* Collation and sort-order information */ u16 nField; /* Number of entries in apMem[] */ i8 default_rc; /* Comparison result if keys are equal */ u8 errCode; /* Error detected by xRecordCompare (CORRUPT or NOMEM) */ | > < | | > | 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 | ** into its constituent fields. ** ** The r1 and r2 member variables are only used by the optimized comparison ** functions vdbeRecordCompareInt() and vdbeRecordCompareString(). */ struct UnpackedRecord { KeyInfo *pKeyInfo; /* Collation and sort-order information */ Mem *aMem; /* Values */ u16 nField; /* Number of entries in apMem[] */ i8 default_rc; /* Comparison result if keys are equal */ u8 errCode; /* Error detected by xRecordCompare (CORRUPT or NOMEM) */ i8 r1; /* Value to return if (lhs > rhs) */ i8 r2; /* Value to return if (rhs < lhs) */ u8 eqSeen; /* True if an equality comparison has been seen */ }; /* ** Each SQL index is represented in memory by an ** instance of the following structure. ** |
︙ | ︙ |
Changes to src/vdbe.c.
︙ | ︙ | |||
3687 3688 3689 3690 3691 3692 3693 3694 3695 3696 3697 3698 3699 3700 3701 3702 3703 3704 3705 | /* For a cursor with the BTREE_SEEK_EQ hint, only the OP_SeekGE and ** OP_SeekLE opcodes are allowed, and these must be immediately followed ** by an OP_IdxGT or OP_IdxLT opcode, respectively, with the same key. */ #ifdef SQLITE_DEBUG if( sqlite3BtreeCursorHasHint(pC->pCursor, BTREE_SEEK_EQ) ){ assert( pOp->opcode==OP_SeekGE || pOp->opcode==OP_SeekLE ); assert( pOp[1].opcode==OP_IdxLT || pOp[1].opcode==OP_IdxGT ); assert( pOp[1].p1==pOp[0].p1 ); assert( pOp[1].p2==pOp[0].p2 ); assert( pOp[1].p3==pOp[0].p3 ); assert( pOp[1].p4.i==pOp[0].p4.i ); } #endif if( pC->isTable ){ /* The input value in P3 might be of any type: integer, real, string, ** blob, or NULL. But it needs to be an integer before we can do ** the seek, so convert it. */ | > > | 3687 3688 3689 3690 3691 3692 3693 3694 3695 3696 3697 3698 3699 3700 3701 3702 3703 3704 3705 3706 3707 | /* For a cursor with the BTREE_SEEK_EQ hint, only the OP_SeekGE and ** OP_SeekLE opcodes are allowed, and these must be immediately followed ** by an OP_IdxGT or OP_IdxLT opcode, respectively, with the same key. */ #ifdef SQLITE_DEBUG if( sqlite3BtreeCursorHasHint(pC->pCursor, BTREE_SEEK_EQ) ){ assert( pOp->opcode==OP_SeekGE || pOp->opcode==OP_SeekLE ); #if 0 assert( pOp[1].opcode==OP_IdxLT || pOp[1].opcode==OP_IdxGT ); assert( pOp[1].p1==pOp[0].p1 ); assert( pOp[1].p2==pOp[0].p2 ); assert( pOp[1].p3==pOp[0].p3 ); assert( pOp[1].p4.i==pOp[0].p4.i ); #endif } #endif if( pC->isTable ){ /* The input value in P3 might be of any type: integer, real, string, ** blob, or NULL. But it needs to be an integer before we can do ** the seek, so convert it. */ |
︙ | ︙ | |||
3768 3769 3770 3771 3772 3773 3774 3775 3776 3777 3778 3779 3780 3781 3782 3783 3784 | assert( oc!=OP_SeekLT || r.default_rc==+1 ); r.aMem = &aMem[pOp->p3]; #ifdef SQLITE_DEBUG { int i; for(i=0; i<r.nField; i++) assert( memIsValid(&r.aMem[i]) ); } #endif ExpandBlob(r.aMem); rc = sqlite3BtreeMovetoUnpacked(pC->pCursor, &r, 0, 0, &res); if( rc!=SQLITE_OK ){ goto abort_due_to_error; } } pC->deferredMoveto = 0; pC->cacheStatus = CACHE_STALE; #ifdef SQLITE_TEST sqlite3_search_count++; #endif | > > > > | 3770 3771 3772 3773 3774 3775 3776 3777 3778 3779 3780 3781 3782 3783 3784 3785 3786 3787 3788 3789 3790 | assert( oc!=OP_SeekLT || r.default_rc==+1 ); r.aMem = &aMem[pOp->p3]; #ifdef SQLITE_DEBUG { int i; for(i=0; i<r.nField; i++) assert( memIsValid(&r.aMem[i]) ); } #endif ExpandBlob(r.aMem); r.eqSeen = 0; rc = sqlite3BtreeMovetoUnpacked(pC->pCursor, &r, 0, 0, &res); if( rc!=SQLITE_OK ){ goto abort_due_to_error; } if( (pOp->p5 & OPFLAG_SEEKEQ)!=0 && r.eqSeen==0 ){ goto take_the_jump; } } pC->deferredMoveto = 0; pC->cacheStatus = CACHE_STALE; #ifdef SQLITE_TEST sqlite3_search_count++; #endif |
︙ | ︙ | |||
3799 3800 3801 3802 3803 3804 3805 3806 3807 3808 3809 3810 3811 3812 | }else{ /* res might be negative because the table is empty. Check to ** see if this is the case. */ res = sqlite3BtreeEof(pC->pCursor); } } assert( pOp->p2>0 ); VdbeBranchTaken(res!=0,2); if( res ){ goto jump_to_p2; } break; } | > | 3805 3806 3807 3808 3809 3810 3811 3812 3813 3814 3815 3816 3817 3818 3819 | }else{ /* res might be negative because the table is empty. Check to ** see if this is the case. */ res = sqlite3BtreeEof(pC->pCursor); } } take_the_jump: assert( pOp->p2>0 ); VdbeBranchTaken(res!=0,2); if( res ){ goto jump_to_p2; } break; } |
︙ | ︙ |
Changes to src/vdbeaux.c.
︙ | ︙ | |||
3965 3966 3967 3968 3969 3970 3971 3972 3973 3974 3975 3976 3977 3978 | /* rc==0 here means that one or both of the keys ran out of fields and ** all the fields up to that point were equal. Return the default_rc ** value. */ assert( CORRUPT_DB || vdbeRecordCompareDebug(nKey1, pKey1, pPKey2, pPKey2->default_rc) || pKeyInfo->db->mallocFailed ); return pPKey2->default_rc; } int sqlite3VdbeRecordCompare( int nKey1, const void *pKey1, /* Left key */ UnpackedRecord *pPKey2 /* Right key */ ){ return sqlite3VdbeRecordCompareWithSkip(nKey1, pKey1, pPKey2, 0); | > | 3965 3966 3967 3968 3969 3970 3971 3972 3973 3974 3975 3976 3977 3978 3979 | /* rc==0 here means that one or both of the keys ran out of fields and ** all the fields up to that point were equal. Return the default_rc ** value. */ assert( CORRUPT_DB || vdbeRecordCompareDebug(nKey1, pKey1, pPKey2, pPKey2->default_rc) || pKeyInfo->db->mallocFailed ); pPKey2->eqSeen = 1; return pPKey2->default_rc; } int sqlite3VdbeRecordCompare( int nKey1, const void *pKey1, /* Left key */ UnpackedRecord *pPKey2 /* Right key */ ){ return sqlite3VdbeRecordCompareWithSkip(nKey1, pKey1, pPKey2, 0); |
︙ | ︙ | |||
4064 4065 4066 4067 4068 4069 4070 4071 4072 4073 4074 4075 4076 4077 | /* 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) ); return res; } /* | > | 4065 4066 4067 4068 4069 4070 4071 4072 4073 4074 4075 4076 4077 4078 4079 | /* 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; pPKey2->eqSeen = 1; } assert( vdbeRecordCompareDebug(nKey1, pKey1, pPKey2, res) ); return res; } /* |
︙ | ︙ | |||
4110 4111 4112 4113 4114 4115 4116 4117 4118 4119 4120 4121 4122 4123 | 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; } }else if( res>0 ){ | > | 4112 4113 4114 4115 4116 4117 4118 4119 4120 4121 4122 4123 4124 4125 4126 | 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; pPKey2->eqSeen = 1; } }else if( res>0 ){ res = pPKey2->r2; }else{ res = pPKey2->r1; } }else if( res>0 ){ |
︙ | ︙ |
Changes to src/wherecode.c.
︙ | ︙ | |||
1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 | }; u16 nEq = pLoop->u.btree.nEq; /* Number of == or IN terms */ int regBase; /* Base register holding constraint values */ WhereTerm *pRangeStart = 0; /* Inequality constraint at range start */ WhereTerm *pRangeEnd = 0; /* Inequality constraint at range end */ int startEq; /* True if range start uses ==, >= or <= */ int endEq; /* True if range end uses ==, >= or <= */ int start_constraints; /* Start of range is constrained */ int nConstraint; /* Number of constraint terms */ Index *pIdx; /* The index we will be using */ int iIdxCur; /* The VDBE cursor for the index */ int nExtraReg = 0; /* Number of extra registers needed */ int op; /* Instruction opcode */ char *zStartAff; /* Affinity for start of range constraint */ | > | 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 | }; u16 nEq = pLoop->u.btree.nEq; /* Number of == or IN terms */ int regBase; /* Base register holding constraint values */ WhereTerm *pRangeStart = 0; /* Inequality constraint at range start */ WhereTerm *pRangeEnd = 0; /* Inequality constraint at range end */ int startEq; /* True if range start uses ==, >= or <= */ int endEq; /* True if range end uses ==, >= or <= */ int eqOnly; /* True if uses only == */ int start_constraints; /* Start of range is constrained */ int nConstraint; /* Number of constraint terms */ Index *pIdx; /* The index we will be using */ int iIdxCur; /* The VDBE cursor for the index */ int nExtraReg = 0; /* Number of extra registers needed */ int op; /* Instruction opcode */ char *zStartAff; /* Affinity for start of range constraint */ |
︙ | ︙ | |||
1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 | && (j = pIdx->aiColumn[nEq])>=0 && pIdx->pTable->aCol[j].notNull==0 ){ bSeekPastNull = 1; } } assert( pRangeEnd==0 || (pRangeEnd->wtFlags & TERM_VNULL)==0 ); /* If we are doing a reverse order scan on an ascending index, or ** a forward order scan on a descending index, interchange the ** start and end terms (pRangeStart and pRangeEnd). */ if( (nEq<pIdx->nKeyCol && bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC)) || (bRev && pIdx->nKeyCol==nEq) | > > | 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 | && (j = pIdx->aiColumn[nEq])>=0 && pIdx->pTable->aCol[j].notNull==0 ){ bSeekPastNull = 1; } } assert( pRangeEnd==0 || (pRangeEnd->wtFlags & TERM_VNULL)==0 ); eqOnly = nEq>0 && (pLoop->wsFlags & WHERE_COLUMN_RANGE)==0 && (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)==0; /* If we are doing a reverse order scan on an ascending index, or ** a forward order scan on a descending index, interchange the ** start and end terms (pRangeStart and pRangeEnd). */ if( (nEq<pIdx->nKeyCol && bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC)) || (bRev && pIdx->nKeyCol==nEq) |
︙ | ︙ | |||
1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 | VdbeCoverage(v); VdbeCoverageIf(v, op==OP_Rewind); testcase( op==OP_Rewind ); VdbeCoverageIf(v, op==OP_Last); testcase( op==OP_Last ); VdbeCoverageIf(v, op==OP_SeekGT); testcase( op==OP_SeekGT ); VdbeCoverageIf(v, op==OP_SeekGE); testcase( op==OP_SeekGE ); VdbeCoverageIf(v, op==OP_SeekLE); testcase( op==OP_SeekLE ); VdbeCoverageIf(v, op==OP_SeekLT); testcase( op==OP_SeekLT ); /* Load the value for the inequality constraint at the end of the ** range (if any). */ nConstraint = nEq; if( pRangeEnd ){ Expr *pRight = pRangeEnd->pExpr->pRight; | > | 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 | VdbeCoverage(v); VdbeCoverageIf(v, op==OP_Rewind); testcase( op==OP_Rewind ); VdbeCoverageIf(v, op==OP_Last); testcase( op==OP_Last ); VdbeCoverageIf(v, op==OP_SeekGT); testcase( op==OP_SeekGT ); VdbeCoverageIf(v, op==OP_SeekGE); testcase( op==OP_SeekGE ); VdbeCoverageIf(v, op==OP_SeekLE); testcase( op==OP_SeekLE ); VdbeCoverageIf(v, op==OP_SeekLT); testcase( op==OP_SeekLT ); if( eqOnly ) sqlite3VdbeChangeP5(v, OPFLAG_SEEKEQ); /* Load the value for the inequality constraint at the end of the ** range (if any). */ nConstraint = nEq; if( pRangeEnd ){ Expr *pRight = pRangeEnd->pExpr->pRight; |
︙ | ︙ | |||
1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 | sqlite3DbFree(db, zStartAff); /* Top of the loop body */ pLevel->p2 = sqlite3VdbeCurrentAddr(v); /* Check if the index cursor is past the end of the range. */ if( nConstraint ){ op = aEndOp[bRev*2 + endEq]; sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint); testcase( op==OP_IdxGT ); VdbeCoverageIf(v, op==OP_IdxGT ); testcase( op==OP_IdxGE ); VdbeCoverageIf(v, op==OP_IdxGE ); testcase( op==OP_IdxLT ); VdbeCoverageIf(v, op==OP_IdxLT ); testcase( op==OP_IdxLE ); VdbeCoverageIf(v, op==OP_IdxLE ); } | > > > > > | 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 | sqlite3DbFree(db, zStartAff); /* Top of the loop body */ pLevel->p2 = sqlite3VdbeCurrentAddr(v); /* Check if the index cursor is past the end of the range. */ if( nConstraint ){ if( eqOnly ){ int bx = sqlite3VdbeCurrentAddr(v); sqlite3VdbeAddOp2(v, OP_Goto, 0, bx+2); pLevel->p2 = bx+1; } op = aEndOp[bRev*2 + endEq]; sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint); testcase( op==OP_IdxGT ); VdbeCoverageIf(v, op==OP_IdxGT ); testcase( op==OP_IdxGE ); VdbeCoverageIf(v, op==OP_IdxGE ); testcase( op==OP_IdxLT ); VdbeCoverageIf(v, op==OP_IdxLT ); testcase( op==OP_IdxLE ); VdbeCoverageIf(v, op==OP_IdxLE ); } |
︙ | ︙ |