/ Check-in [09fffbdf]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:The IN-early-out optimization: When doing a look-up on a multi-column index and an IN operator is used on a column other than the left-most column, then if no rows match against the first IN value, check to make sure there exist rows that match the columns to the right before continuing with the next IN value.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256:09fffbdf9f2f6ce31a22d5a6df7a45f19a16628da622f12d6e33171cce09fb21
User & Date: drh 2018-06-07 18:13:49
Context
2018-06-08
19:13
Fix an assert() that can be false for a corrupt database and a strange query that uses a recursive SQL function to delete content from a corrupt database file while it is being queried. check-in: 99057383 user: drh tags: trunk
18:22
Consider doing a partial table scan to fulfill an IN operator rather than using an index. Try to pick the plan with the lowest cost. check-in: 1fa40a78 user: drh tags: in-scan-vs-index
2018-06-07
20:35
Merge latest trunk changes with this branch. check-in: 25102203 user: dan tags: exp-window-functions
18:13
The IN-early-out optimization: When doing a look-up on a multi-column index and an IN operator is used on a column other than the left-most column, then if no rows match against the first IN value, check to make sure there exist rows that match the columns to the right before continuing with the next IN value. check-in: 09fffbdf user: drh tags: trunk
18:01
Fix the assert()s in the byte-code engine that prove that cursors are unidirectional. Closed-Leaf check-in: 4b0b4e14 user: drh tags: multikey-opt-idea
15:23
Avoid using a prepared statement for ".stats on" after it has been closed by the ".eqp full" logic. Fix for ticket [7be932dfa60a8a6b3b26bcf76]. check-in: bb87c054 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/shell.c.in.

  2563   2563   static void explain_data_prepare(ShellState *p, sqlite3_stmt *pSql){
  2564   2564     const char *zSql;               /* The text of the SQL statement */
  2565   2565     const char *z;                  /* Used to check if this is an EXPLAIN */
  2566   2566     int *abYield = 0;               /* True if op is an OP_Yield */
  2567   2567     int nAlloc = 0;                 /* Allocated size of p->aiIndent[], abYield */
  2568   2568     int iOp;                        /* Index of operation in p->aiIndent[] */
  2569   2569   
  2570         -  const char *azNext[] = { "Next", "Prev", "VPrev", "VNext", "SorterNext",
  2571         -                           "NextIfOpen", "PrevIfOpen", 0 };
         2570  +  const char *azNext[] = { "Next", "Prev", "VPrev", "VNext", "SorterNext", 0 };
  2572   2571     const char *azYield[] = { "Yield", "SeekLT", "SeekGT", "RowSetRead",
  2573   2572                               "Rewind", 0 };
  2574   2573     const char *azGoto[] = { "Goto", 0 };
  2575   2574   
  2576   2575     /* Try to figure out if this is really an EXPLAIN statement. If this
  2577   2576     ** cannot be verified, return early.  */
  2578   2577     if( sqlite3_column_count(pSql)!=8 ){

Changes to src/vdbe.c.

  4026   4026       goto jump_to_p2;
  4027   4027     }else if( eqOnly ){
  4028   4028       assert( pOp[1].opcode==OP_IdxLT || pOp[1].opcode==OP_IdxGT );
  4029   4029       pOp++; /* Skip the OP_IdxLt or OP_IdxGT that follows */
  4030   4030     }
  4031   4031     break;
  4032   4032   }
         4033  +
         4034  +/* Opcode: SeekHit P1 P2 * * *
         4035  +** Synopsis: seekHit=P2
         4036  +**
         4037  +** Set the seekHit flag on cursor P1 to the value in P2.
         4038  +** The seekHit flag is used by the IfNoHope opcode.
         4039  +**
         4040  +** P1 must be a valid b-tree cursor.  P2 must be a boolean value,
         4041  +** either 0 or 1.
         4042  +*/
         4043  +case OP_SeekHit: {
         4044  +  VdbeCursor *pC;
         4045  +  assert( pOp->p1>=0 && pOp->p1<p->nCursor );
         4046  +  pC = p->apCsr[pOp->p1];
         4047  +  assert( pC!=0 );
         4048  +  assert( pOp->p2==0 || pOp->p2==1 );
         4049  +  pC->seekHit = pOp->p2 & 1;
         4050  +  break;
         4051  +}
  4033   4052   
  4034   4053   /* Opcode: Found P1 P2 P3 P4 *
  4035   4054   ** Synopsis: key=r[P3@P4]
  4036   4055   **
  4037   4056   ** If P4==0 then register P3 holds a blob constructed by MakeRecord.  If
  4038   4057   ** P4>0 then register P3 is the first of P4 registers that form an unpacked
  4039   4058   ** record.
................................................................................
  4061   4080   ** falls through to the next instruction and P1 is left pointing at the
  4062   4081   ** matching entry.
  4063   4082   **
  4064   4083   ** This operation leaves the cursor in a state where it cannot be
  4065   4084   ** advanced in either direction.  In other words, the Next and Prev
  4066   4085   ** opcodes do not work after this operation.
  4067   4086   **
  4068         -** See also: Found, NotExists, NoConflict
         4087  +** See also: Found, NotExists, NoConflict, IfNoHope
         4088  +*/
         4089  +/* Opcode: IfNoHope P1 P2 P3 P4 *
         4090  +** Synopsis: key=r[P3@P4]
         4091  +**
         4092  +** Register P3 is the first of P4 registers that form an unpacked
         4093  +** record.
         4094  +**
         4095  +** Cursor P1 is on an index btree.  If the seekHit flag is set on P1, then
         4096  +** this opcode is a no-op.  But if the seekHit flag of P1 is clear, then
         4097  +** check to see if there is any entry in P1 that matches the
         4098  +** prefix identified by P3 and P4.  If no entry matches the prefix,
         4099  +** jump to P2.  Otherwise fall through.
         4100  +**
         4101  +** This opcode behaves like OP_NotFound if the seekHit
         4102  +** flag is clear and it behaves like OP_Noop if the seekHit flag is set.
         4103  +**
         4104  +** This opcode is used in IN clause processing for a multi-column key.
         4105  +** If an IN clause is attached to an element of the key other than the
         4106  +** left-most element, and if there are no matches on the most recent
         4107  +** seek over the whole key, then it might be that one of the key element
         4108  +** to the left is prohibiting a match, and hence there is "no hope" of
         4109  +** any match regardless of how many IN clause elements are checked.
         4110  +** In such a case, we abandon the IN clause search early, using this
         4111  +** opcode.  The opcode name comes from the fact that the
         4112  +** jump is taken if there is "no hope" of achieving a match.
         4113  +**
         4114  +** See also: NotFound, SeekHit
  4069   4115   */
  4070   4116   /* Opcode: NoConflict P1 P2 P3 P4 *
  4071   4117   ** Synopsis: key=r[P3@P4]
  4072   4118   **
  4073   4119   ** If P4==0 then register P3 holds a blob constructed by MakeRecord.  If
  4074   4120   ** P4>0 then register P3 is the first of P4 registers that form an unpacked
  4075   4121   ** record.
................................................................................
  4086   4132   **
  4087   4133   ** This operation leaves the cursor in a state where it cannot be
  4088   4134   ** advanced in either direction.  In other words, the Next and Prev
  4089   4135   ** opcodes do not work after this operation.
  4090   4136   **
  4091   4137   ** See also: NotFound, Found, NotExists
  4092   4138   */
         4139  +case OP_IfNoHope: {     /* jump, in3 */
         4140  +  VdbeCursor *pC;
         4141  +  assert( pOp->p1>=0 && pOp->p1<p->nCursor );
         4142  +  pC = p->apCsr[pOp->p1];
         4143  +  assert( pC!=0 );
         4144  +  if( pC->seekHit ) break;
         4145  +  /* Fall through into OP_NotFound */
         4146  +}
  4093   4147   case OP_NoConflict:     /* jump, in3 */
  4094   4148   case OP_NotFound:       /* jump, in3 */
  4095   4149   case OP_Found: {        /* jump, in3 */
  4096   4150     int alreadyExists;
  4097   4151     int takeJump;
  4098   4152     int ii;
  4099   4153     VdbeCursor *pC;
................................................................................
  4234   4288   case OP_NotExists:          /* jump, in3 */
  4235   4289     pIn3 = &aMem[pOp->p3];
  4236   4290     assert( pIn3->flags & MEM_Int );
  4237   4291     assert( pOp->p1>=0 && pOp->p1<p->nCursor );
  4238   4292     pC = p->apCsr[pOp->p1];
  4239   4293     assert( pC!=0 );
  4240   4294   #ifdef SQLITE_DEBUG
  4241         -  pC->seekOp = 0;
         4295  +  pC->seekOp = OP_SeekRowid;
  4242   4296   #endif
  4243   4297     assert( pC->isTable );
  4244   4298     assert( pC->eCurType==CURTYPE_BTREE );
  4245   4299     pCrsr = pC->uc.pCursor;
  4246   4300     assert( pCrsr!=0 );
  4247   4301     res = 0;
  4248   4302     iKey = pIn3->u.i;
................................................................................
  4888   4942     assert( pC!=0 );
  4889   4943     pC->nullRow = 1;
  4890   4944     pC->cacheStatus = CACHE_STALE;
  4891   4945     if( pC->eCurType==CURTYPE_BTREE ){
  4892   4946       assert( pC->uc.pCursor!=0 );
  4893   4947       sqlite3BtreeClearCursor(pC->uc.pCursor);
  4894   4948     }
         4949  +#ifdef SQLITE_DEBUG
         4950  +  if( pC->seekOp==0 ) pC->seekOp = OP_NullRow;
         4951  +#endif
  4895   4952     break;
  4896   4953   }
  4897   4954   
  4898   4955   /* Opcode: SeekEnd P1 * * * *
  4899   4956   **
  4900   4957   ** Position cursor P1 at the end of the btree for the purpose of
  4901   4958   ** appending a new entry onto the btree.
................................................................................
  5074   5131   **
  5075   5132   ** P4 is always of type P4_ADVANCE. The function pointer points to
  5076   5133   ** sqlite3BtreeNext().
  5077   5134   **
  5078   5135   ** If P5 is positive and the jump is taken, then event counter
  5079   5136   ** number P5-1 in the prepared statement is incremented.
  5080   5137   **
  5081         -** See also: Prev, NextIfOpen
  5082         -*/
  5083         -/* Opcode: NextIfOpen P1 P2 P3 P4 P5
  5084         -**
  5085         -** This opcode works just like Next except that if cursor P1 is not
  5086         -** open it behaves a no-op.
         5138  +** See also: Prev
  5087   5139   */
  5088   5140   /* Opcode: Prev P1 P2 P3 P4 P5
  5089   5141   **
  5090   5142   ** Back up cursor P1 so that it points to the previous key/data pair in its
  5091   5143   ** table or index.  If there is no previous key/value pairs then fall through
  5092   5144   ** to the following instruction.  But if the cursor backup was successful,
  5093   5145   ** jump immediately to P2.
................................................................................
  5107   5159   **
  5108   5160   ** P4 is always of type P4_ADVANCE. The function pointer points to
  5109   5161   ** sqlite3BtreePrevious().
  5110   5162   **
  5111   5163   ** If P5 is positive and the jump is taken, then event counter
  5112   5164   ** number P5-1 in the prepared statement is incremented.
  5113   5165   */
  5114         -/* Opcode: PrevIfOpen P1 P2 P3 P4 P5
  5115         -**
  5116         -** This opcode works just like Prev except that if cursor P1 is not
  5117         -** open it behaves a no-op.
  5118         -*/
  5119   5166   /* Opcode: SorterNext P1 P2 * * P5
  5120   5167   **
  5121   5168   ** This opcode works just like OP_Next except that P1 must be a
  5122   5169   ** sorter object for which the OP_SorterSort opcode has been
  5123   5170   ** invoked.  This opcode advances the cursor to the next sorted
  5124   5171   ** record, or jumps to P2 if there are no more sorted records.
  5125   5172   */
................................................................................
  5126   5173   case OP_SorterNext: {  /* jump */
  5127   5174     VdbeCursor *pC;
  5128   5175   
  5129   5176     pC = p->apCsr[pOp->p1];
  5130   5177     assert( isSorter(pC) );
  5131   5178     rc = sqlite3VdbeSorterNext(db, pC);
  5132   5179     goto next_tail;
  5133         -case OP_PrevIfOpen:    /* jump */
  5134         -case OP_NextIfOpen:    /* jump */
  5135         -  if( p->apCsr[pOp->p1]==0 ) break;
  5136         -  /* Fall through */
  5137   5180   case OP_Prev:          /* jump */
  5138   5181   case OP_Next:          /* jump */
  5139   5182     assert( pOp->p1>=0 && pOp->p1<p->nCursor );
  5140   5183     assert( pOp->p5<ArraySize(p->aCounter) );
  5141   5184     pC = p->apCsr[pOp->p1];
  5142   5185     assert( pC!=0 );
  5143   5186     assert( pC->deferredMoveto==0 );
  5144   5187     assert( pC->eCurType==CURTYPE_BTREE );
  5145   5188     assert( pOp->opcode!=OP_Next || pOp->p4.xAdvance==sqlite3BtreeNext );
  5146   5189     assert( pOp->opcode!=OP_Prev || pOp->p4.xAdvance==sqlite3BtreePrevious );
  5147         -  assert( pOp->opcode!=OP_NextIfOpen || pOp->p4.xAdvance==sqlite3BtreeNext );
  5148         -  assert( pOp->opcode!=OP_PrevIfOpen || pOp->p4.xAdvance==sqlite3BtreePrevious);
  5149   5190   
  5150         -  /* The Next opcode is only used after SeekGT, SeekGE, and Rewind.
         5191  +  /* The Next opcode is only used after SeekGT, SeekGE, Rewind, and Found.
  5151   5192     ** The Prev opcode is only used after SeekLT, SeekLE, and Last. */
  5152         -  assert( pOp->opcode!=OP_Next || pOp->opcode!=OP_NextIfOpen
         5193  +  assert( pOp->opcode!=OP_Next
  5153   5194          || pC->seekOp==OP_SeekGT || pC->seekOp==OP_SeekGE
  5154         -       || pC->seekOp==OP_Rewind || pC->seekOp==OP_Found);
  5155         -  assert( pOp->opcode!=OP_Prev || pOp->opcode!=OP_PrevIfOpen
         5195  +       || pC->seekOp==OP_Rewind || pC->seekOp==OP_Found 
         5196  +       || pC->seekOp==OP_NullRow);
         5197  +  assert( pOp->opcode!=OP_Prev
  5156   5198          || pC->seekOp==OP_SeekLT || pC->seekOp==OP_SeekLE
  5157         -       || pC->seekOp==OP_Last );
         5199  +       || pC->seekOp==OP_Last 
         5200  +       || pC->seekOp==OP_NullRow);
  5158   5201   
  5159   5202     rc = pOp->p4.xAdvance(pC->uc.pCursor, pOp->p3);
  5160   5203   next_tail:
  5161   5204     pC->cacheStatus = CACHE_STALE;
  5162   5205     VdbeBranchTaken(rc==SQLITE_OK,2);
  5163   5206     if( rc==SQLITE_OK ){
  5164   5207       pC->nullRow = 0;

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/vdbeaux.c.

   685    685           case OP_Vacuum:
   686    686           case OP_JournalMode: {
   687    687             p->readOnly = 0;
   688    688             p->bIsReader = 1;
   689    689             break;
   690    690           }
   691    691           case OP_Next:
   692         -        case OP_NextIfOpen:
   693    692           case OP_SorterNext: {
   694    693             pOp->p4.xAdvance = sqlite3BtreeNext;
   695    694             pOp->p4type = P4_ADVANCE;
   696    695             /* The code generator never codes any of these opcodes as a jump
   697    696             ** to a label.  They are always coded as a jump backwards to a 
   698    697             ** known address */
   699    698             assert( pOp->p2>=0 );
   700    699             break;
   701    700           }
   702         -        case OP_Prev:
   703         -        case OP_PrevIfOpen: {
          701  +        case OP_Prev: {
   704    702             pOp->p4.xAdvance = sqlite3BtreePrevious;
   705    703             pOp->p4type = P4_ADVANCE;
   706    704             /* The code generator never codes any of these opcodes as a jump
   707    705             ** to a label.  They are always coded as a jump backwards to a 
   708    706             ** known address */
   709    707             assert( pOp->p2>=0 );
   710    708             break;

Changes to src/where.c.

  5079   5079       if( pLoop->wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){
  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  +          if( pIn->nPrefix ){
         5087  +            assert( pLoop->wsFlags & WHERE_IN_EARLYOUT );
         5088  +            sqlite3VdbeAddOp4Int(v, OP_IfNoHope, pLevel->iIdxCur,
         5089  +                              sqlite3VdbeCurrentAddr(v)+2,
         5090  +                              pIn->iBase, pIn->nPrefix);
         5091  +            VdbeCoverage(v);
         5092  +          }
  5086   5093             sqlite3VdbeAddOp2(v, pIn->eEndLoopOp, pIn->iCur, pIn->addrInTop);
  5087   5094             VdbeCoverage(v);
  5088         -          VdbeCoverageIf(v, pIn->eEndLoopOp==OP_PrevIfOpen);
  5089         -          VdbeCoverageIf(v, pIn->eEndLoopOp==OP_NextIfOpen);
         5095  +          VdbeCoverageIf(v, pIn->eEndLoopOp==OP_Prev);
         5096  +          VdbeCoverageIf(v, pIn->eEndLoopOp==OP_Next);
  5090   5097           }
  5091   5098           sqlite3VdbeJumpHere(v, pIn->addrInTop-1);
  5092   5099         }
  5093   5100       }
  5094   5101       sqlite3VdbeResolveLabel(v, pLevel->addrBrk);
  5095   5102       if( pLevel->addrSkip ){
  5096   5103         sqlite3VdbeGoto(v, pLevel->addrSkip);

Changes to src/whereInt.h.

    78     78     int p1, p2;           /* Operands of the opcode used to ends the loop */
    79     79     union {               /* Information that depends on pWLoop->wsFlags */
    80     80       struct {
    81     81         int nIn;              /* Number of entries in aInLoop[] */
    82     82         struct InLoop {
    83     83           int iCur;              /* The VDBE cursor used by this IN operator */
    84     84           int addrInTop;         /* Top of the IN loop */
           85  +        int iBase;             /* Base register of multi-key index record */
           86  +        int nPrefix;           /* Number of prior entires in the key */
    85     87           u8 eEndLoopOp;         /* IN Loop terminator. OP_Next or OP_Prev */
    86     88         } *aInLoop;           /* Information about each nested IN operator */
    87     89       } in;                 /* Used when pWLoop->wsFlags&WHERE_IN_ABLE */
    88     90       Index *pCovidx;       /* Possible covering index for WHERE_MULTI_OR */
    89     91     } u;
    90     92     struct WhereLoop *pWLoop;  /* The selected WhereLoop object */
    91     93     Bitmask notReady;          /* FROM entries not usable at this level */
................................................................................
   551    553   #define WHERE_IN_ABLE      0x00000800  /* Able to support an IN operator */
   552    554   #define WHERE_ONEROW       0x00001000  /* Selects no more than one row */
   553    555   #define WHERE_MULTI_OR     0x00002000  /* OR using multiple indices */
   554    556   #define WHERE_AUTO_INDEX   0x00004000  /* Uses an ephemeral index */
   555    557   #define WHERE_SKIPSCAN     0x00008000  /* Uses the skip-scan algorithm */
   556    558   #define WHERE_UNQ_WANTED   0x00010000  /* WHERE_ONEROW would have been helpful*/
   557    559   #define WHERE_PARTIALIDX   0x00020000  /* The automatic index is partial */
          560  +#define WHERE_IN_EARLYOUT  0x00040000  /* Perhaps quit IN loops early */

Changes to src/wherecode.c.

   587    587             }else{
   588    588               int iCol = aiMap ? aiMap[iMap++] : 0;
   589    589               pIn->addrInTop = sqlite3VdbeAddOp3(v,OP_Column,iTab, iCol, iOut);
   590    590             }
   591    591             sqlite3VdbeAddOp1(v, OP_IsNull, iOut); VdbeCoverage(v);
   592    592             if( i==iEq ){
   593    593               pIn->iCur = iTab;
   594         -            pIn->eEndLoopOp = bRev ? OP_PrevIfOpen : OP_NextIfOpen;
          594  +            pIn->eEndLoopOp = bRev ? OP_Prev : OP_Next;
          595  +            if( iEq>0 && (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 ){
          596  +              pIn->iBase = iReg - i;
          597  +              pIn->nPrefix = i;
          598  +              pLoop->wsFlags |= WHERE_IN_EARLYOUT;
          599  +            }else{
          600  +              pIn->nPrefix = 0;
          601  +            }
   595    602             }else{
   596    603               pIn->eEndLoopOp = OP_Noop;
   597    604             }
   598    605             pIn++;
   599    606           }
   600    607         }
   601    608       }else{
................................................................................
  1654   1661       }
  1655   1662       codeApplyAffinity(pParse, regBase, nConstraint - bSeekPastNull, zStartAff);
  1656   1663       if( pLoop->nSkip>0 && nConstraint==pLoop->nSkip ){
  1657   1664         /* The skip-scan logic inside the call to codeAllEqualityConstraints()
  1658   1665         ** above has already left the cursor sitting on the correct row,
  1659   1666         ** so no further seeking is needed */
  1660   1667       }else{
         1668  +      if( pLoop->wsFlags & WHERE_IN_EARLYOUT ){
         1669  +        sqlite3VdbeAddOp1(v, OP_SeekHit, iIdxCur);
         1670  +      }
  1661   1671         op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev];
  1662   1672         assert( op!=0 );
  1663   1673         sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
  1664   1674         VdbeCoverage(v);
  1665   1675         VdbeCoverageIf(v, op==OP_Rewind);  testcase( op==OP_Rewind );
  1666   1676         VdbeCoverageIf(v, op==OP_Last);    testcase( op==OP_Last );
  1667   1677         VdbeCoverageIf(v, op==OP_SeekGT);  testcase( op==OP_SeekGT );
................................................................................
  1716   1726         op = aEndOp[bRev*2 + endEq];
  1717   1727         sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
  1718   1728         testcase( op==OP_IdxGT );  VdbeCoverageIf(v, op==OP_IdxGT );
  1719   1729         testcase( op==OP_IdxGE );  VdbeCoverageIf(v, op==OP_IdxGE );
  1720   1730         testcase( op==OP_IdxLT );  VdbeCoverageIf(v, op==OP_IdxLT );
  1721   1731         testcase( op==OP_IdxLE );  VdbeCoverageIf(v, op==OP_IdxLE );
  1722   1732       }
         1733  +
         1734  +    if( pLoop->wsFlags & WHERE_IN_EARLYOUT ){
         1735  +      sqlite3VdbeAddOp2(v, OP_SeekHit, iIdxCur, 1);
         1736  +    }
  1723   1737   
  1724   1738       /* Seek the table cursor, if required */
  1725   1739       if( omitTable ){
  1726   1740         /* pIdx is a covering index.  No need to access the main table. */
  1727   1741       }else if( HasRowid(pIdx->pTable) ){
  1728   1742         if( (pWInfo->wctrlFlags & WHERE_SEEK_TABLE) || (
  1729   1743             (pWInfo->wctrlFlags & WHERE_SEEK_UNIQ_TABLE) 

Added test/in6.test.

            1  +# 2018-06-07
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#***********************************************************************
           11  +#
           12  +# A multi-key index that uses an IN operator on one of the keys other
           13  +# than the left-most key is able to abort the IN-operator loop early
           14  +# if key terms further to the left do not match.
           15  +#
           16  +# Call this the "multikey-IN-operator early-out optimization" or
           17  +# just "IN-early-out" optimization for short.
           18  +#
           19  +
           20  +set testdir [file dirname $argv0]
           21  +source $testdir/tester.tcl
           22  +set testprefix in6
           23  +
           24  +do_test in6-1.1 {
           25  +  db eval {
           26  +    CREATE TABLE t1(a,b,c,d);
           27  +    WITH RECURSIVE c(x) AS (VALUES(1) UNION ALL SELECT x+1 FROM c WHERE x<100)
           28  +      INSERT INTO t1(a,b,c,d)
           29  +        SELECT 100, 200+x/2, 300+x/5, x FROM c;
           30  +    CREATE INDEX t1abc ON t1(a,b,c);
           31  +  }
           32  +  set ::sqlite_search_count 0
           33  +  db eval {
           34  +    SELECT d FROM t1
           35  +     WHERE a=99
           36  +       AND b IN (200,205,201,204)
           37  +       AND c IN (304,302,309,308);
           38  +  }
           39  +} {}
           40  +do_test in6-1.2 {
           41  +  set ::sqlite_search_count
           42  +} {0}  ;# Without the IN-early-out optimization, this value would be 15
           43  +
           44  +# The multikey-IN-operator early-out optimization does not apply
           45  +# when the IN operator is on the left-most column of the index.
           46  +#
           47  +do_test in6-1.3 {
           48  +  db eval {
           49  +    EXPLAIN
           50  +    SELECT d FROM t1
           51  +      WHERE a IN (98,99,100,101)
           52  +        AND b=200 AND c=300;
           53  +  }
           54  +} {~/(IfNoHope|SeekHit)/}
           55  +
           56  +set sqlite_search_count 0
           57  +do_execsql_test in6-1.4 {
           58  + SELECT d FROM t1
           59  +  WHERE a=100
           60  +    AND b IN (200,201,202,204)
           61  +    AND c IN (300,302,301,305)
           62  +  ORDER BY +d;
           63  +} {1 2 3 4 5 8 9}
           64  +do_test in6-1.5 {
           65  +  set ::sqlite_search_count
           66  +} {39}
           67  +
           68  +do_execsql_test in6-2.1 {
           69  +  CREATE TABLE t2(e INT UNIQUE, f TEXT);
           70  +  SELECT d, f FROM t1 LEFT JOIN t2 ON (e=d)
           71  +  WHERE a=100
           72  +    AND b IN (200,201,202,204)
           73  +    AND c IN (300,302,301,305)
           74  +  ORDER BY +d;
           75  +} {1 {} 2 {} 3 {} 4 {} 5 {} 8 {} 9 {}}
           76  +
           77  +finish_test

Changes to test/where.test.

   486    486         SELECT * FROM t1 WHERE x IN (1,7) AND y NOT IN (6400,8100) ORDER BY 1;
   487    487       }
   488    488     } {2 1 9 3 1 16 6}
   489    489     do_test where-5.14 {
   490    490       count {
   491    491         SELECT * FROM t1 WHERE x IN (1,7) AND y IN (9,10) ORDER BY 1;
   492    492       }
   493         -  } {2 1 9 5}
          493  +  } {2 1 9 4}
   494    494     do_test where-5.15 {
   495    495       count {
   496    496         SELECT * FROM t1 WHERE x IN (1,7) AND y IN (9,16) ORDER BY 1;
   497    497       }
   498         -  } {2 1 9 3 1 16 9}
          498  +  } {2 1 9 3 1 16 8}
   499    499     do_test where-5.100 {
   500    500       db eval {
   501    501         SELECT w, x, y FROM t1 WHERE x IN (1,5) AND y IN (9,8,3025,1000,3969)
   502    502          ORDER BY x, y
   503    503       }
   504    504     } {2 1 9 54 5 3025 62 5 3969}
   505    505     do_test where-5.101 {