/ Check-in [6bf251af]
Login

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: 6bf251af4347165a470d39457d61ab6d2a06c206db8f30bd8be5dbb388ae8a5b
User & Date: drh 2018-06-05 20:45:20
Context
2018-06-07
14:32
Merge recent trunk enhancements. check-in: e9d7bf4f 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: 6bf251af 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: 87a9fc50 user: drh tags: multikey-opt-idea
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/vdbe.c.

  4029   4029       goto jump_to_p2;
  4030   4030     }else if( eqOnly ){
  4031   4031       assert( pOp[1].opcode==OP_IdxLT || pOp[1].opcode==OP_IdxGT );
  4032   4032       pOp++; /* Skip the OP_IdxLt or OP_IdxGT that follows */
  4033   4033     }
  4034   4034     break;
  4035   4035   }
         4036  +
         4037  +/* Opcode: SeekHit P1 P2 * * *
         4038  +** Synopsis: seekHit=P2
         4039  +**
         4040  +** Set the seekHit flag on cursor P1 to the value in P2.
         4041  +** The seekHit flag is used by the IfNoHope opcode.
         4042  +**
         4043  +** P1 must be a valid b-tree cursor.  P2 must be a boolean value,
         4044  +** either 0 or 1.
         4045  +*/
         4046  +case OP_SeekHit: {
         4047  +  VdbeCursor *pC;
         4048  +  assert( pOp->p1>=0 && pOp->p1<p->nCursor );
         4049  +  pC = p->apCsr[pOp->p1];
         4050  +  assert( pC!=0 );
         4051  +  assert( pOp->p2==0 || pOp->p2==1 );
         4052  +  pC->seekHit = pOp->p2 & 1;
         4053  +  break;
         4054  +}
  4036   4055   
  4037   4056   /* Opcode: Found P1 P2 P3 P4 *
  4038   4057   ** Synopsis: key=r[P3@P4]
  4039   4058   **
  4040   4059   ** If P4==0 then register P3 holds a blob constructed by MakeRecord.  If
  4041   4060   ** P4>0 then register P3 is the first of P4 registers that form an unpacked
  4042   4061   ** record.
................................................................................
  4064   4083   ** falls through to the next instruction and P1 is left pointing at the
  4065   4084   ** matching entry.
  4066   4085   **
  4067   4086   ** This operation leaves the cursor in a state where it cannot be
  4068   4087   ** advanced in either direction.  In other words, the Next and Prev
  4069   4088   ** opcodes do not work after this operation.
  4070   4089   **
  4071         -** See also: Found, NotExists, NoConflict
         4090  +** See also: Found, NotExists, NoConflict, IfNoHope
         4091  +*/
         4092  +/* Opcode: IfNoHope P1 P2 P3 P4 *
         4093  +** Synopsis: key=r[P3@P4]
         4094  +**
         4095  +** Register P3 is the first of P4 registers that form an unpacked
         4096  +** record.
         4097  +**
         4098  +** Cursor P1 is on an index btree.  If the seekHit flag is set on P1, then
         4099  +** this opcode is a no-op.  But if the seekHit flag of P1 is clear, then
         4100  +** check to see if there is any entry in P1 that matches the
         4101  +** prefix identified by P3 and P4.  If no entry matches the prefix,
         4102  +** jump to P2.  Otherwise fall through.
         4103  +**
         4104  +** This opcode behaves like OP_NotFound if the seekHit
         4105  +** flag is clear and it behaves like OP_Noop if the seekHit flag is set.
         4106  +**
         4107  +** This opcode is used in IN clause processing for a multi-column key.
         4108  +** If an IN clause is attached to an element of the key other than the
         4109  +** left-most element, and if there are no matches on the most recent
         4110  +** seek over the whole key, then it might be that one of the key element
         4111  +** to the left is prohibiting a match, and hence there is "no hope" of
         4112  +** any match regardless of how many IN clause elements are checked.
         4113  +** In such a case, we abandon the IN clause search early, using this
         4114  +** opcode.  The opcode name comes from the fact that the
         4115  +** jump is taken if there is "no hope" of achieving a match.
         4116  +**
         4117  +** See also: NotFound, SeekHit
  4072   4118   */
  4073   4119   /* Opcode: NoConflict P1 P2 P3 P4 *
  4074   4120   ** Synopsis: key=r[P3@P4]
  4075   4121   **
  4076   4122   ** If P4==0 then register P3 holds a blob constructed by MakeRecord.  If
  4077   4123   ** P4>0 then register P3 is the first of P4 registers that form an unpacked
  4078   4124   ** record.
................................................................................
  4089   4135   **
  4090   4136   ** This operation leaves the cursor in a state where it cannot be
  4091   4137   ** advanced in either direction.  In other words, the Next and Prev
  4092   4138   ** opcodes do not work after this operation.
  4093   4139   **
  4094   4140   ** See also: NotFound, Found, NotExists
  4095   4141   */
         4142  +case OP_IfNoHope: {     /* jump, in3 */
         4143  +  VdbeCursor *pC;
         4144  +  assert( pOp->p1>=0 && pOp->p1<p->nCursor );
         4145  +  pC = p->apCsr[pOp->p1];
         4146  +  assert( pC!=0 );
         4147  +  if( pC->seekHit ) break;
         4148  +  /* Fall through into OP_NotFound */
         4149  +}
  4096   4150   case OP_NoConflict:     /* jump, in3 */
  4097   4151   case OP_NotFound:       /* jump, in3 */
  4098   4152   case OP_Found: {        /* jump, in3 */
  4099   4153     int alreadyExists;
  4100   4154     int takeJump;
  4101   4155     int ii;
  4102   4156     VdbeCursor *pC;

Changes to src/vdbeInt.h.

    81     81   #ifdef SQLITE_DEBUG
    82     82     u8 seekOp;              /* Most recent seek operation on this cursor */
    83     83     u8 wrFlag;              /* The wrFlag argument to sqlite3BtreeCursor() */
    84     84   #endif
    85     85     Bool isEphemeral:1;     /* True for an ephemeral table */
    86     86     Bool useRandomRowid:1;  /* Generate new record numbers semi-randomly */
    87     87     Bool isOrdered:1;       /* True if the table is not BTREE_UNORDERED */
           88  +  Bool seekHit:1;         /* See the OP_SeekHit and OP_IfNoHope opcodes */
    88     89     Btree *pBtx;            /* Separate file holding temporary table */
    89     90     i64 seqCount;           /* Sequence counter */
    90     91     int *aAltMap;           /* Mapping from table to index column numbers */
    91     92   
    92     93     /* Cached OP_Column parse information is only valid if cacheStatus matches
    93     94     ** Vdbe.cacheCtr.  Vdbe.cacheCtr will never take on the value of
    94     95     ** CACHE_STALE (0) and so setting cacheStatus=CACHE_STALE guarantees that

Changes to src/where.c.

  5080   5080         struct InLoop *pIn;
  5081   5081         int j;
  5082   5082         sqlite3VdbeResolveLabel(v, pLevel->addrNxt);
  5083   5083         for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){
  5084   5084           sqlite3VdbeJumpHere(v, pIn->addrInTop+1);
  5085   5085           if( pIn->eEndLoopOp!=OP_Noop ){
  5086   5086             if( pIn->nPrefix ){
  5087         -            sqlite3VdbeAddOp4Int(v, OP_NotFound, pLevel->iIdxCur,
         5087  +            sqlite3VdbeAddOp4Int(v, OP_IfNoHope, pLevel->iIdxCur,
  5088   5088                                 sqlite3VdbeCurrentAddr(v)+2,
  5089   5089                                 pIn->iBase, pIn->nPrefix);
  5090   5090               VdbeCoverage(v);
  5091   5091             }
  5092   5092             sqlite3VdbeAddOp2(v, pIn->eEndLoopOp, pIn->iCur, pIn->addrInTop);
  5093   5093             VdbeCoverage(v);
  5094   5094             VdbeCoverageIf(v, pIn->eEndLoopOp==OP_PrevIfOpen);

Changes to src/wherecode.c.

  1660   1660       }
  1661   1661       codeApplyAffinity(pParse, regBase, nConstraint - bSeekPastNull, zStartAff);
  1662   1662       if( pLoop->nSkip>0 && nConstraint==pLoop->nSkip ){
  1663   1663         /* The skip-scan logic inside the call to codeAllEqualityConstraints()
  1664   1664         ** above has already left the cursor sitting on the correct row,
  1665   1665         ** so no further seeking is needed */
  1666   1666       }else{
         1667  +      if( pLoop->wsFlags & WHERE_IN_ABLE ){
         1668  +        sqlite3VdbeAddOp1(v, OP_SeekHit, iIdxCur);
         1669  +      }
  1667   1670         op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev];
  1668   1671         assert( op!=0 );
  1669   1672         sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
  1670   1673         VdbeCoverage(v);
  1671   1674         VdbeCoverageIf(v, op==OP_Rewind);  testcase( op==OP_Rewind );
  1672   1675         VdbeCoverageIf(v, op==OP_Last);    testcase( op==OP_Last );
  1673   1676         VdbeCoverageIf(v, op==OP_SeekGT);  testcase( op==OP_SeekGT );
................................................................................
  1722   1725         op = aEndOp[bRev*2 + endEq];
  1723   1726         sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
  1724   1727         testcase( op==OP_IdxGT );  VdbeCoverageIf(v, op==OP_IdxGT );
  1725   1728         testcase( op==OP_IdxGE );  VdbeCoverageIf(v, op==OP_IdxGE );
  1726   1729         testcase( op==OP_IdxLT );  VdbeCoverageIf(v, op==OP_IdxLT );
  1727   1730         testcase( op==OP_IdxLE );  VdbeCoverageIf(v, op==OP_IdxLE );
  1728   1731       }
         1732  +
         1733  +    if( pLoop->wsFlags & WHERE_IN_ABLE ){
         1734  +      sqlite3VdbeAddOp2(v, OP_SeekHit, iIdxCur, 1);
         1735  +    }
  1729   1736   
  1730   1737       /* Seek the table cursor, if required */
  1731   1738       if( omitTable ){
  1732   1739         /* pIdx is a covering index.  No need to access the main table. */
  1733   1740       }else if( HasRowid(pIdx->pTable) ){
  1734   1741         if( (pWInfo->wctrlFlags & WHERE_SEEK_TABLE) || (
  1735   1742             (pWInfo->wctrlFlags & WHERE_SEEK_UNIQ_TABLE)