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