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 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)/src/vdbe.c $(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
|
| |
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 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 |
** 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) */
Mem *aMem; /* Values */
int r1; /* Value to return if (lhs > rhs) */
int r2; /* Value to return if (rhs < lhs) */
};
/*
** Each SQL index is represented in memory by an
** instance of the following structure.
**
|
> | | | |
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 .... 3768 3769 3770 3771 3772 3773 3774 3775 3776 3777 3778 3779 3780 3781 3782 3783 3784 .... 3799 3800 3801 3802 3803 3804 3805 3806 3807 3808 3809 3810 3811 3812 |
/* 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. */
................................................................................
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
................................................................................
}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;
}
|
> > > > > > > |
3687 3688 3689 3690 3691 3692 3693 3694 3695 3696 3697 3698 3699 3700 3701 3702 3703 3704 3705 3706 3707 .... 3770 3771 3772 3773 3774 3775 3776 3777 3778 3779 3780 3781 3782 3783 3784 3785 3786 3787 3788 3789 3790 .... 3805 3806 3807 3808 3809 3810 3811 3812 3813 3814 3815 3816 3817 3818 3819 |
/* 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. */
................................................................................
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
................................................................................
}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 .... 4064 4065 4066 4067 4068 4069 4070 4071 4072 4073 4074 4075 4076 4077 .... 4110 4111 4112 4113 4114 4115 4116 4117 4118 4119 4120 4121 4122 4123 |
/* 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);
................................................................................
/* 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;
}
/*
................................................................................
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 ){
|
> > > |
3965 3966 3967 3968 3969 3970 3971 3972 3973 3974 3975 3976 3977 3978 3979 .... 4065 4066 4067 4068 4069 4070 4071 4072 4073 4074 4075 4076 4077 4078 4079 .... 4112 4113 4114 4115 4116 4117 4118 4119 4120 4121 4122 4123 4124 4125 4126 |
/* 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);
................................................................................
/* 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;
}
/*
................................................................................
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 .... 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 .... 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 .... 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 |
};
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 */
................................................................................
&& (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)
................................................................................
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;
................................................................................
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 );
}
|
> > > > > > > > > |
1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 .... 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 .... 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 .... 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 |
};
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 */
................................................................................
&& (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)
................................................................................
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;
................................................................................
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 );
}
|