Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Add the OP_IfNoHope and OP_SeekHit opcodes used to reduce the number of unnecessary sqlite3BtreeMovetoUnpacked() calls when checking for an early exit on IN-operator loops. Futher optimizations are likely possible here. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | multikey-opt-idea |
| Files: | files | file ages | folders |
| SHA3-256: |
6bf251af4347165a470d39457d61ab6d |
| User & Date: | drh 2018-06-05 20:45:20 |
Context
|
2018-06-07
| ||
| 14:32 | Merge recent trunk enhancements. check-in: e9d7bf4f7b user: drh tags: multikey-opt-idea | |
|
2018-06-05
| ||
| 20:45 | Add the OP_IfNoHope and OP_SeekHit opcodes used to reduce the number of unnecessary sqlite3BtreeMovetoUnpacked() calls when checking for an early exit on IN-operator loops. Futher optimizations are likely possible here. check-in: 6bf251af43 user: drh tags: multikey-opt-idea | |
| 15:16 | Use an OP_NotFound opcode to cancel futile IN operators early. The current implementation is suboptimal because it always runs teh OP_NotFound. This still needs to be enhanced to only do the OP_NotFound if no results have been seen on the current loop. check-in: 87a9fc504f user: drh tags: multikey-opt-idea | |
Changes
Changes to src/vdbe.c.
4029 4030 4031 4032 4033 4034 4035 4036 4037 4038 4039 4040 4041 4042 .... 4064 4065 4066 4067 4068 4069 4070 4071 4072 4073 4074 4075 4076 4077 4078 .... 4089 4090 4091 4092 4093 4094 4095 4096 4097 4098 4099 4100 4101 4102 |
goto jump_to_p2;
}else if( eqOnly ){
assert( pOp[1].opcode==OP_IdxLT || pOp[1].opcode==OP_IdxGT );
pOp++; /* Skip the OP_IdxLt or OP_IdxGT that follows */
}
break;
}
/* Opcode: Found P1 P2 P3 P4 *
** Synopsis: key=r[P3@P4]
**
** If P4==0 then register P3 holds a blob constructed by MakeRecord. If
** P4>0 then register P3 is the first of P4 registers that form an unpacked
** record.
................................................................................
** falls through to the next instruction and P1 is left pointing at the
** matching entry.
**
** This operation leaves the cursor in a state where it cannot be
** advanced in either direction. In other words, the Next and Prev
** opcodes do not work after this operation.
**
** See also: Found, NotExists, NoConflict
*/
/* Opcode: NoConflict P1 P2 P3 P4 *
** Synopsis: key=r[P3@P4]
**
** If P4==0 then register P3 holds a blob constructed by MakeRecord. If
** P4>0 then register P3 is the first of P4 registers that form an unpacked
** record.
................................................................................
**
** This operation leaves the cursor in a state where it cannot be
** advanced in either direction. In other words, the Next and Prev
** opcodes do not work after this operation.
**
** See also: NotFound, Found, NotExists
*/
case OP_NoConflict: /* jump, in3 */
case OP_NotFound: /* jump, in3 */
case OP_Found: { /* jump, in3 */
int alreadyExists;
int takeJump;
int ii;
VdbeCursor *pC;
|
> > > > > > > > > > > > > > > > > > > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > |
4029 4030 4031 4032 4033 4034 4035 4036 4037 4038 4039 4040 4041 4042 4043 4044 4045 4046 4047 4048 4049 4050 4051 4052 4053 4054 4055 4056 4057 4058 4059 4060 4061 .... 4083 4084 4085 4086 4087 4088 4089 4090 4091 4092 4093 4094 4095 4096 4097 4098 4099 4100 4101 4102 4103 4104 4105 4106 4107 4108 4109 4110 4111 4112 4113 4114 4115 4116 4117 4118 4119 4120 4121 4122 4123 4124 .... 4135 4136 4137 4138 4139 4140 4141 4142 4143 4144 4145 4146 4147 4148 4149 4150 4151 4152 4153 4154 4155 4156 |
goto jump_to_p2;
}else if( eqOnly ){
assert( pOp[1].opcode==OP_IdxLT || pOp[1].opcode==OP_IdxGT );
pOp++; /* Skip the OP_IdxLt or OP_IdxGT that follows */
}
break;
}
/* Opcode: SeekHit P1 P2 * * *
** Synopsis: seekHit=P2
**
** Set the seekHit flag on cursor P1 to the value in P2.
** The seekHit flag is used by the IfNoHope opcode.
**
** P1 must be a valid b-tree cursor. P2 must be a boolean value,
** either 0 or 1.
*/
case OP_SeekHit: {
VdbeCursor *pC;
assert( pOp->p1>=0 && pOp->p1<p->nCursor );
pC = p->apCsr[pOp->p1];
assert( pC!=0 );
assert( pOp->p2==0 || pOp->p2==1 );
pC->seekHit = pOp->p2 & 1;
break;
}
/* Opcode: Found P1 P2 P3 P4 *
** Synopsis: key=r[P3@P4]
**
** If P4==0 then register P3 holds a blob constructed by MakeRecord. If
** P4>0 then register P3 is the first of P4 registers that form an unpacked
** record.
................................................................................
** falls through to the next instruction and P1 is left pointing at the
** matching entry.
**
** This operation leaves the cursor in a state where it cannot be
** advanced in either direction. In other words, the Next and Prev
** opcodes do not work after this operation.
**
** See also: Found, NotExists, NoConflict, IfNoHope
*/
/* Opcode: IfNoHope P1 P2 P3 P4 *
** Synopsis: key=r[P3@P4]
**
** Register P3 is the first of P4 registers that form an unpacked
** record.
**
** Cursor P1 is on an index btree. If the seekHit flag is set on P1, then
** this opcode is a no-op. But if the seekHit flag of P1 is clear, then
** check to see if there is any entry in P1 that matches the
** prefix identified by P3 and P4. If no entry matches the prefix,
** jump to P2. Otherwise fall through.
**
** This opcode behaves like OP_NotFound if the seekHit
** flag is clear and it behaves like OP_Noop if the seekHit flag is set.
**
** This opcode is used in IN clause processing for a multi-column key.
** If an IN clause is attached to an element of the key other than the
** left-most element, and if there are no matches on the most recent
** seek over the whole key, then it might be that one of the key element
** to the left is prohibiting a match, and hence there is "no hope" of
** any match regardless of how many IN clause elements are checked.
** In such a case, we abandon the IN clause search early, using this
** opcode. The opcode name comes from the fact that the
** jump is taken if there is "no hope" of achieving a match.
**
** See also: NotFound, SeekHit
*/
/* Opcode: NoConflict P1 P2 P3 P4 *
** Synopsis: key=r[P3@P4]
**
** If P4==0 then register P3 holds a blob constructed by MakeRecord. If
** P4>0 then register P3 is the first of P4 registers that form an unpacked
** record.
................................................................................
**
** This operation leaves the cursor in a state where it cannot be
** advanced in either direction. In other words, the Next and Prev
** opcodes do not work after this operation.
**
** See also: NotFound, Found, NotExists
*/
case OP_IfNoHope: { /* jump, in3 */
VdbeCursor *pC;
assert( pOp->p1>=0 && pOp->p1<p->nCursor );
pC = p->apCsr[pOp->p1];
assert( pC!=0 );
if( pC->seekHit ) break;
/* Fall through into OP_NotFound */
}
case OP_NoConflict: /* jump, in3 */
case OP_NotFound: /* jump, in3 */
case OP_Found: { /* jump, in3 */
int alreadyExists;
int takeJump;
int ii;
VdbeCursor *pC;
|
Changes to src/vdbeInt.h.
81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
#ifdef SQLITE_DEBUG u8 seekOp; /* Most recent seek operation on this cursor */ u8 wrFlag; /* The wrFlag argument to sqlite3BtreeCursor() */ #endif Bool isEphemeral:1; /* True for an ephemeral table */ Bool useRandomRowid:1; /* Generate new record numbers semi-randomly */ Bool isOrdered:1; /* True if the table is not BTREE_UNORDERED */ Btree *pBtx; /* Separate file holding temporary table */ i64 seqCount; /* Sequence counter */ int *aAltMap; /* Mapping from table to index column numbers */ /* Cached OP_Column parse information is only valid if cacheStatus matches ** Vdbe.cacheCtr. Vdbe.cacheCtr will never take on the value of ** CACHE_STALE (0) and so setting cacheStatus=CACHE_STALE guarantees that |
> |
81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
#ifdef SQLITE_DEBUG
u8 seekOp; /* Most recent seek operation on this cursor */
u8 wrFlag; /* The wrFlag argument to sqlite3BtreeCursor() */
#endif
Bool isEphemeral:1; /* True for an ephemeral table */
Bool useRandomRowid:1; /* Generate new record numbers semi-randomly */
Bool isOrdered:1; /* True if the table is not BTREE_UNORDERED */
Bool seekHit:1; /* See the OP_SeekHit and OP_IfNoHope opcodes */
Btree *pBtx; /* Separate file holding temporary table */
i64 seqCount; /* Sequence counter */
int *aAltMap; /* Mapping from table to index column numbers */
/* Cached OP_Column parse information is only valid if cacheStatus matches
** Vdbe.cacheCtr. Vdbe.cacheCtr will never take on the value of
** CACHE_STALE (0) and so setting cacheStatus=CACHE_STALE guarantees that
|
Changes to src/where.c.
5080 5081 5082 5083 5084 5085 5086 5087 5088 5089 5090 5091 5092 5093 5094 |
struct InLoop *pIn;
int j;
sqlite3VdbeResolveLabel(v, pLevel->addrNxt);
for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){
sqlite3VdbeJumpHere(v, pIn->addrInTop+1);
if( pIn->eEndLoopOp!=OP_Noop ){
if( pIn->nPrefix ){
sqlite3VdbeAddOp4Int(v, OP_NotFound, pLevel->iIdxCur,
sqlite3VdbeCurrentAddr(v)+2,
pIn->iBase, pIn->nPrefix);
VdbeCoverage(v);
}
sqlite3VdbeAddOp2(v, pIn->eEndLoopOp, pIn->iCur, pIn->addrInTop);
VdbeCoverage(v);
VdbeCoverageIf(v, pIn->eEndLoopOp==OP_PrevIfOpen);
|
| |
5080 5081 5082 5083 5084 5085 5086 5087 5088 5089 5090 5091 5092 5093 5094 |
struct InLoop *pIn;
int j;
sqlite3VdbeResolveLabel(v, pLevel->addrNxt);
for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){
sqlite3VdbeJumpHere(v, pIn->addrInTop+1);
if( pIn->eEndLoopOp!=OP_Noop ){
if( pIn->nPrefix ){
sqlite3VdbeAddOp4Int(v, OP_IfNoHope, pLevel->iIdxCur,
sqlite3VdbeCurrentAddr(v)+2,
pIn->iBase, pIn->nPrefix);
VdbeCoverage(v);
}
sqlite3VdbeAddOp2(v, pIn->eEndLoopOp, pIn->iCur, pIn->addrInTop);
VdbeCoverage(v);
VdbeCoverageIf(v, pIn->eEndLoopOp==OP_PrevIfOpen);
|
Changes to src/wherecode.c.
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
....
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
|
}
codeApplyAffinity(pParse, regBase, nConstraint - bSeekPastNull, zStartAff);
if( pLoop->nSkip>0 && nConstraint==pLoop->nSkip ){
/* The skip-scan logic inside the call to codeAllEqualityConstraints()
** above has already left the cursor sitting on the correct row,
** so no further seeking is needed */
}else{
op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev];
assert( op!=0 );
sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
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 );
................................................................................
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 );
}
/* Seek the table cursor, if required */
if( omitTable ){
/* pIdx is a covering index. No need to access the main table. */
}else if( HasRowid(pIdx->pTable) ){
if( (pWInfo->wctrlFlags & WHERE_SEEK_TABLE) || (
(pWInfo->wctrlFlags & WHERE_SEEK_UNIQ_TABLE)
|
>
>
>
>
>
>
>
|
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
....
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
|
}
codeApplyAffinity(pParse, regBase, nConstraint - bSeekPastNull, zStartAff);
if( pLoop->nSkip>0 && nConstraint==pLoop->nSkip ){
/* The skip-scan logic inside the call to codeAllEqualityConstraints()
** above has already left the cursor sitting on the correct row,
** so no further seeking is needed */
}else{
if( pLoop->wsFlags & WHERE_IN_ABLE ){
sqlite3VdbeAddOp1(v, OP_SeekHit, iIdxCur);
}
op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev];
assert( op!=0 );
sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
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 );
................................................................................
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 );
}
if( pLoop->wsFlags & WHERE_IN_ABLE ){
sqlite3VdbeAddOp2(v, OP_SeekHit, iIdxCur, 1);
}
/* Seek the table cursor, if required */
if( omitTable ){
/* pIdx is a covering index. No need to access the main table. */
}else if( HasRowid(pIdx->pTable) ){
if( (pWInfo->wctrlFlags & WHERE_SEEK_TABLE) || (
(pWInfo->wctrlFlags & WHERE_SEEK_UNIQ_TABLE)
|