/ 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 Unified Diffs Ignore Whitespace Patch

Changes to src/shell.c.in.

2563
2564
2565
2566
2567
2568
2569
2570
2571
2572
2573
2574
2575
2576
2577
2578
static void explain_data_prepare(ShellState *p, sqlite3_stmt *pSql){
  const char *zSql;               /* The text of the SQL statement */
  const char *z;                  /* Used to check if this is an EXPLAIN */
  int *abYield = 0;               /* True if op is an OP_Yield */
  int nAlloc = 0;                 /* Allocated size of p->aiIndent[], abYield */
  int iOp;                        /* Index of operation in p->aiIndent[] */

  const char *azNext[] = { "Next", "Prev", "VPrev", "VNext", "SorterNext",
                           "NextIfOpen", "PrevIfOpen", 0 };
  const char *azYield[] = { "Yield", "SeekLT", "SeekGT", "RowSetRead",
                            "Rewind", 0 };
  const char *azGoto[] = { "Goto", 0 };

  /* Try to figure out if this is really an EXPLAIN statement. If this
  ** cannot be verified, return early.  */
  if( sqlite3_column_count(pSql)!=8 ){







|
<







2563
2564
2565
2566
2567
2568
2569
2570

2571
2572
2573
2574
2575
2576
2577
static void explain_data_prepare(ShellState *p, sqlite3_stmt *pSql){
  const char *zSql;               /* The text of the SQL statement */
  const char *z;                  /* Used to check if this is an EXPLAIN */
  int *abYield = 0;               /* True if op is an OP_Yield */
  int nAlloc = 0;                 /* Allocated size of p->aiIndent[], abYield */
  int iOp;                        /* Index of operation in p->aiIndent[] */

  const char *azNext[] = { "Next", "Prev", "VPrev", "VNext", "SorterNext", 0 };

  const char *azYield[] = { "Yield", "SeekLT", "SeekGT", "RowSetRead",
                            "Rewind", 0 };
  const char *azGoto[] = { "Goto", 0 };

  /* Try to figure out if this is really an EXPLAIN statement. If this
  ** cannot be verified, return early.  */
  if( sqlite3_column_count(pSql)!=8 ){

Changes to src/vdbe.c.

4026
4027
4028
4029
4030
4031
4032



















4033
4034
4035
4036
4037
4038
4039
....
4061
4062
4063
4064
4065
4066
4067
4068



























4069
4070
4071
4072
4073
4074
4075
....
4086
4087
4088
4089
4090
4091
4092








4093
4094
4095
4096
4097
4098
4099
....
4234
4235
4236
4237
4238
4239
4240
4241
4242
4243
4244
4245
4246
4247
4248
....
4888
4889
4890
4891
4892
4893
4894



4895
4896
4897
4898
4899
4900
4901
....
5074
5075
5076
5077
5078
5079
5080
5081
5082
5083
5084
5085
5086
5087
5088
5089
5090
5091
5092
5093
....
5107
5108
5109
5110
5111
5112
5113
5114
5115
5116
5117
5118
5119
5120
5121
5122
5123
5124
5125
....
5126
5127
5128
5129
5130
5131
5132
5133
5134
5135
5136
5137
5138
5139
5140
5141
5142
5143
5144
5145
5146
5147
5148
5149
5150
5151
5152
5153
5154

5155
5156
5157

5158
5159
5160
5161
5162
5163
5164
    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;
................................................................................
case OP_NotExists:          /* jump, in3 */
  pIn3 = &aMem[pOp->p3];
  assert( pIn3->flags & MEM_Int );
  assert( pOp->p1>=0 && pOp->p1<p->nCursor );
  pC = p->apCsr[pOp->p1];
  assert( pC!=0 );
#ifdef SQLITE_DEBUG
  pC->seekOp = 0;
#endif
  assert( pC->isTable );
  assert( pC->eCurType==CURTYPE_BTREE );
  pCrsr = pC->uc.pCursor;
  assert( pCrsr!=0 );
  res = 0;
  iKey = pIn3->u.i;
................................................................................
  assert( pC!=0 );
  pC->nullRow = 1;
  pC->cacheStatus = CACHE_STALE;
  if( pC->eCurType==CURTYPE_BTREE ){
    assert( pC->uc.pCursor!=0 );
    sqlite3BtreeClearCursor(pC->uc.pCursor);
  }



  break;
}

/* Opcode: SeekEnd P1 * * * *
**
** Position cursor P1 at the end of the btree for the purpose of
** appending a new entry onto the btree.
................................................................................
**
** P4 is always of type P4_ADVANCE. The function pointer points to
** sqlite3BtreeNext().
**
** If P5 is positive and the jump is taken, then event counter
** number P5-1 in the prepared statement is incremented.
**
** See also: Prev, NextIfOpen
*/
/* Opcode: NextIfOpen P1 P2 P3 P4 P5
**
** This opcode works just like Next except that if cursor P1 is not
** open it behaves a no-op.
*/
/* Opcode: Prev P1 P2 P3 P4 P5
**
** Back up cursor P1 so that it points to the previous key/data pair in its
** table or index.  If there is no previous key/value pairs then fall through
** to the following instruction.  But if the cursor backup was successful,
** jump immediately to P2.
................................................................................
**
** P4 is always of type P4_ADVANCE. The function pointer points to
** sqlite3BtreePrevious().
**
** If P5 is positive and the jump is taken, then event counter
** number P5-1 in the prepared statement is incremented.
*/
/* Opcode: PrevIfOpen P1 P2 P3 P4 P5
**
** This opcode works just like Prev except that if cursor P1 is not
** open it behaves a no-op.
*/
/* Opcode: SorterNext P1 P2 * * P5
**
** This opcode works just like OP_Next except that P1 must be a
** sorter object for which the OP_SorterSort opcode has been
** invoked.  This opcode advances the cursor to the next sorted
** record, or jumps to P2 if there are no more sorted records.
*/
................................................................................
case OP_SorterNext: {  /* jump */
  VdbeCursor *pC;

  pC = p->apCsr[pOp->p1];
  assert( isSorter(pC) );
  rc = sqlite3VdbeSorterNext(db, pC);
  goto next_tail;
case OP_PrevIfOpen:    /* jump */
case OP_NextIfOpen:    /* jump */
  if( p->apCsr[pOp->p1]==0 ) break;
  /* Fall through */
case OP_Prev:          /* jump */
case OP_Next:          /* jump */
  assert( pOp->p1>=0 && pOp->p1<p->nCursor );
  assert( pOp->p5<ArraySize(p->aCounter) );
  pC = p->apCsr[pOp->p1];
  assert( pC!=0 );
  assert( pC->deferredMoveto==0 );
  assert( pC->eCurType==CURTYPE_BTREE );
  assert( pOp->opcode!=OP_Next || pOp->p4.xAdvance==sqlite3BtreeNext );
  assert( pOp->opcode!=OP_Prev || pOp->p4.xAdvance==sqlite3BtreePrevious );
  assert( pOp->opcode!=OP_NextIfOpen || pOp->p4.xAdvance==sqlite3BtreeNext );
  assert( pOp->opcode!=OP_PrevIfOpen || pOp->p4.xAdvance==sqlite3BtreePrevious);

  /* The Next opcode is only used after SeekGT, SeekGE, and Rewind.
  ** The Prev opcode is only used after SeekLT, SeekLE, and Last. */
  assert( pOp->opcode!=OP_Next || pOp->opcode!=OP_NextIfOpen
       || pC->seekOp==OP_SeekGT || pC->seekOp==OP_SeekGE
       || pC->seekOp==OP_Rewind || pC->seekOp==OP_Found);

  assert( pOp->opcode!=OP_Prev || pOp->opcode!=OP_PrevIfOpen
       || pC->seekOp==OP_SeekLT || pC->seekOp==OP_SeekLE
       || pC->seekOp==OP_Last );


  rc = pOp->p4.xAdvance(pC->uc.pCursor, pOp->p3);
next_tail:
  pC->cacheStatus = CACHE_STALE;
  VdbeBranchTaken(rc==SQLITE_OK,2);
  if( rc==SQLITE_OK ){
    pC->nullRow = 0;







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







>
>
>
>
>
>
>
>







 







|







 







>
>
>







 







|
<
<
<
<
<







 







<
<
<
<
<







 







<
<
<
<










<
<

|

|

|
>
|

|
>







4026
4027
4028
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
....
4080
4081
4082
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
....
4132
4133
4134
4135
4136
4137
4138
4139
4140
4141
4142
4143
4144
4145
4146
4147
4148
4149
4150
4151
4152
4153
....
4288
4289
4290
4291
4292
4293
4294
4295
4296
4297
4298
4299
4300
4301
4302
....
4942
4943
4944
4945
4946
4947
4948
4949
4950
4951
4952
4953
4954
4955
4956
4957
4958
....
5131
5132
5133
5134
5135
5136
5137
5138





5139
5140
5141
5142
5143
5144
5145
....
5159
5160
5161
5162
5163
5164
5165





5166
5167
5168
5169
5170
5171
5172
....
5173
5174
5175
5176
5177
5178
5179




5180
5181
5182
5183
5184
5185
5186
5187
5188
5189


5190
5191
5192
5193
5194
5195
5196
5197
5198
5199
5200
5201
5202
5203
5204
5205
5206
5207
    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;
................................................................................
case OP_NotExists:          /* jump, in3 */
  pIn3 = &aMem[pOp->p3];
  assert( pIn3->flags & MEM_Int );
  assert( pOp->p1>=0 && pOp->p1<p->nCursor );
  pC = p->apCsr[pOp->p1];
  assert( pC!=0 );
#ifdef SQLITE_DEBUG
  pC->seekOp = OP_SeekRowid;
#endif
  assert( pC->isTable );
  assert( pC->eCurType==CURTYPE_BTREE );
  pCrsr = pC->uc.pCursor;
  assert( pCrsr!=0 );
  res = 0;
  iKey = pIn3->u.i;
................................................................................
  assert( pC!=0 );
  pC->nullRow = 1;
  pC->cacheStatus = CACHE_STALE;
  if( pC->eCurType==CURTYPE_BTREE ){
    assert( pC->uc.pCursor!=0 );
    sqlite3BtreeClearCursor(pC->uc.pCursor);
  }
#ifdef SQLITE_DEBUG
  if( pC->seekOp==0 ) pC->seekOp = OP_NullRow;
#endif
  break;
}

/* Opcode: SeekEnd P1 * * * *
**
** Position cursor P1 at the end of the btree for the purpose of
** appending a new entry onto the btree.
................................................................................
**
** P4 is always of type P4_ADVANCE. The function pointer points to
** sqlite3BtreeNext().
**
** If P5 is positive and the jump is taken, then event counter
** number P5-1 in the prepared statement is incremented.
**
** See also: Prev





*/
/* Opcode: Prev P1 P2 P3 P4 P5
**
** Back up cursor P1 so that it points to the previous key/data pair in its
** table or index.  If there is no previous key/value pairs then fall through
** to the following instruction.  But if the cursor backup was successful,
** jump immediately to P2.
................................................................................
**
** P4 is always of type P4_ADVANCE. The function pointer points to
** sqlite3BtreePrevious().
**
** If P5 is positive and the jump is taken, then event counter
** number P5-1 in the prepared statement is incremented.
*/





/* Opcode: SorterNext P1 P2 * * P5
**
** This opcode works just like OP_Next except that P1 must be a
** sorter object for which the OP_SorterSort opcode has been
** invoked.  This opcode advances the cursor to the next sorted
** record, or jumps to P2 if there are no more sorted records.
*/
................................................................................
case OP_SorterNext: {  /* jump */
  VdbeCursor *pC;

  pC = p->apCsr[pOp->p1];
  assert( isSorter(pC) );
  rc = sqlite3VdbeSorterNext(db, pC);
  goto next_tail;




case OP_Prev:          /* jump */
case OP_Next:          /* jump */
  assert( pOp->p1>=0 && pOp->p1<p->nCursor );
  assert( pOp->p5<ArraySize(p->aCounter) );
  pC = p->apCsr[pOp->p1];
  assert( pC!=0 );
  assert( pC->deferredMoveto==0 );
  assert( pC->eCurType==CURTYPE_BTREE );
  assert( pOp->opcode!=OP_Next || pOp->p4.xAdvance==sqlite3BtreeNext );
  assert( pOp->opcode!=OP_Prev || pOp->p4.xAdvance==sqlite3BtreePrevious );



  /* The Next opcode is only used after SeekGT, SeekGE, Rewind, and Found.
  ** The Prev opcode is only used after SeekLT, SeekLE, and Last. */
  assert( pOp->opcode!=OP_Next
       || pC->seekOp==OP_SeekGT || pC->seekOp==OP_SeekGE
       || pC->seekOp==OP_Rewind || pC->seekOp==OP_Found 
       || pC->seekOp==OP_NullRow);
  assert( pOp->opcode!=OP_Prev
       || pC->seekOp==OP_SeekLT || pC->seekOp==OP_SeekLE
       || pC->seekOp==OP_Last 
       || pC->seekOp==OP_NullRow);

  rc = pOp->p4.xAdvance(pC->uc.pCursor, pOp->p3);
next_tail:
  pC->cacheStatus = CACHE_STALE;
  VdbeBranchTaken(rc==SQLITE_OK,2);
  if( rc==SQLITE_OK ){
    pC->nullRow = 0;

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

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







<









|
<







685
686
687
688
689
690
691

692
693
694
695
696
697
698
699
700
701

702
703
704
705
706
707
708
        case OP_Vacuum:
        case OP_JournalMode: {
          p->readOnly = 0;
          p->bIsReader = 1;
          break;
        }
        case OP_Next:

        case OP_SorterNext: {
          pOp->p4.xAdvance = sqlite3BtreeNext;
          pOp->p4type = P4_ADVANCE;
          /* The code generator never codes any of these opcodes as a jump
          ** to a label.  They are always coded as a jump backwards to a 
          ** known address */
          assert( pOp->p2>=0 );
          break;
        }
        case OP_Prev: {

          pOp->p4.xAdvance = sqlite3BtreePrevious;
          pOp->p4type = P4_ADVANCE;
          /* The code generator never codes any of these opcodes as a jump
          ** to a label.  They are always coded as a jump backwards to a 
          ** known address */
          assert( pOp->p2>=0 );
          break;

Changes to src/where.c.

5079
5080
5081
5082
5083
5084
5085







5086
5087
5088
5089
5090
5091
5092
5093
5094
5095
5096
    if( pLoop->wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){
      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 ){







          sqlite3VdbeAddOp2(v, pIn->eEndLoopOp, pIn->iCur, pIn->addrInTop);
          VdbeCoverage(v);
          VdbeCoverageIf(v, pIn->eEndLoopOp==OP_PrevIfOpen);
          VdbeCoverageIf(v, pIn->eEndLoopOp==OP_NextIfOpen);
        }
        sqlite3VdbeJumpHere(v, pIn->addrInTop-1);
      }
    }
    sqlite3VdbeResolveLabel(v, pLevel->addrBrk);
    if( pLevel->addrSkip ){
      sqlite3VdbeGoto(v, pLevel->addrSkip);







>
>
>
>
>
>
>


|
|







5079
5080
5081
5082
5083
5084
5085
5086
5087
5088
5089
5090
5091
5092
5093
5094
5095
5096
5097
5098
5099
5100
5101
5102
5103
    if( pLoop->wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){
      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 ){
            assert( pLoop->wsFlags & WHERE_IN_EARLYOUT );
            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_Prev);
          VdbeCoverageIf(v, pIn->eEndLoopOp==OP_Next);
        }
        sqlite3VdbeJumpHere(v, pIn->addrInTop-1);
      }
    }
    sqlite3VdbeResolveLabel(v, pLevel->addrBrk);
    if( pLevel->addrSkip ){
      sqlite3VdbeGoto(v, pLevel->addrSkip);

Changes to src/whereInt.h.

78
79
80
81
82
83
84


85
86
87
88
89
90
91
...
551
552
553
554
555
556
557

  int p1, p2;           /* Operands of the opcode used to ends the loop */
  union {               /* Information that depends on pWLoop->wsFlags */
    struct {
      int nIn;              /* Number of entries in aInLoop[] */
      struct InLoop {
        int iCur;              /* The VDBE cursor used by this IN operator */
        int addrInTop;         /* Top of the IN loop */


        u8 eEndLoopOp;         /* IN Loop terminator. OP_Next or OP_Prev */
      } *aInLoop;           /* Information about each nested IN operator */
    } in;                 /* Used when pWLoop->wsFlags&WHERE_IN_ABLE */
    Index *pCovidx;       /* Possible covering index for WHERE_MULTI_OR */
  } u;
  struct WhereLoop *pWLoop;  /* The selected WhereLoop object */
  Bitmask notReady;          /* FROM entries not usable at this level */
................................................................................
#define WHERE_IN_ABLE      0x00000800  /* Able to support an IN operator */
#define WHERE_ONEROW       0x00001000  /* Selects no more than one row */
#define WHERE_MULTI_OR     0x00002000  /* OR using multiple indices */
#define WHERE_AUTO_INDEX   0x00004000  /* Uses an ephemeral index */
#define WHERE_SKIPSCAN     0x00008000  /* Uses the skip-scan algorithm */
#define WHERE_UNQ_WANTED   0x00010000  /* WHERE_ONEROW would have been helpful*/
#define WHERE_PARTIALIDX   0x00020000  /* The automatic index is partial */








>
>







 







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

Changes to src/wherecode.c.

587
588
589
590
591
592
593
594







595
596
597
598
599
600
601
....
1654
1655
1656
1657
1658
1659
1660



1661
1662
1663
1664
1665
1666
1667
....
1716
1717
1718
1719
1720
1721
1722




1723
1724
1725
1726
1727
1728
1729
          }else{
            int iCol = aiMap ? aiMap[iMap++] : 0;
            pIn->addrInTop = sqlite3VdbeAddOp3(v,OP_Column,iTab, iCol, iOut);
          }
          sqlite3VdbeAddOp1(v, OP_IsNull, iOut); VdbeCoverage(v);
          if( i==iEq ){
            pIn->iCur = iTab;
            pIn->eEndLoopOp = bRev ? OP_PrevIfOpen : OP_NextIfOpen;







          }else{
            pIn->eEndLoopOp = OP_Noop;
          }
          pIn++;
        }
      }
    }else{
................................................................................
    }
    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) 







|
>
>
>
>
>
>
>







 







>
>
>







 







>
>
>
>







587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
....
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
....
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
          }else{
            int iCol = aiMap ? aiMap[iMap++] : 0;
            pIn->addrInTop = sqlite3VdbeAddOp3(v,OP_Column,iTab, iCol, iOut);
          }
          sqlite3VdbeAddOp1(v, OP_IsNull, iOut); VdbeCoverage(v);
          if( i==iEq ){
            pIn->iCur = iTab;
            pIn->eEndLoopOp = bRev ? OP_Prev : OP_Next;
            if( iEq>0 && (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 ){
              pIn->iBase = iReg - i;
              pIn->nPrefix = i;
              pLoop->wsFlags |= WHERE_IN_EARLYOUT;
            }else{
              pIn->nPrefix = 0;
            }
          }else{
            pIn->eEndLoopOp = OP_Noop;
          }
          pIn++;
        }
      }
    }else{
................................................................................
    }
    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_EARLYOUT ){
        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_EARLYOUT ){
      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) 

Added test/in6.test.



























































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
# 2018-06-07
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# A multi-key index that uses an IN operator on one of the keys other
# than the left-most key is able to abort the IN-operator loop early
# if key terms further to the left do not match.
#
# Call this the "multikey-IN-operator early-out optimization" or
# just "IN-early-out" optimization for short.
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl
set testprefix in6

do_test in6-1.1 {
  db eval {
    CREATE TABLE t1(a,b,c,d);
    WITH RECURSIVE c(x) AS (VALUES(1) UNION ALL SELECT x+1 FROM c WHERE x<100)
      INSERT INTO t1(a,b,c,d)
        SELECT 100, 200+x/2, 300+x/5, x FROM c;
    CREATE INDEX t1abc ON t1(a,b,c);
  }
  set ::sqlite_search_count 0
  db eval {
    SELECT d FROM t1
     WHERE a=99
       AND b IN (200,205,201,204)
       AND c IN (304,302,309,308);
  }
} {}
do_test in6-1.2 {
  set ::sqlite_search_count
} {0}  ;# Without the IN-early-out optimization, this value would be 15

# The multikey-IN-operator early-out optimization does not apply
# when the IN operator is on the left-most column of the index.
#
do_test in6-1.3 {
  db eval {
    EXPLAIN
    SELECT d FROM t1
      WHERE a IN (98,99,100,101)
        AND b=200 AND c=300;
  }
} {~/(IfNoHope|SeekHit)/}

set sqlite_search_count 0
do_execsql_test in6-1.4 {
 SELECT d FROM t1
  WHERE a=100
    AND b IN (200,201,202,204)
    AND c IN (300,302,301,305)
  ORDER BY +d;
} {1 2 3 4 5 8 9}
do_test in6-1.5 {
  set ::sqlite_search_count
} {39}

do_execsql_test in6-2.1 {
  CREATE TABLE t2(e INT UNIQUE, f TEXT);
  SELECT d, f FROM t1 LEFT JOIN t2 ON (e=d)
  WHERE a=100
    AND b IN (200,201,202,204)
    AND c IN (300,302,301,305)
  ORDER BY +d;
} {1 {} 2 {} 3 {} 4 {} 5 {} 8 {} 9 {}}

finish_test

Changes to test/where.test.

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







|




|







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