Index: src/main.c ================================================================== --- src/main.c +++ src/main.c @@ -4246,10 +4246,11 @@ ** The seek-count is only available if compiled with SQLITE_DEBUG. */ case SQLITE_TESTCTRL_SEEK_COUNT: { sqlite3 *db = va_arg(ap, sqlite3*); u64 *pn = va_arg(ap, sqlite3_uint64*); + (void)db; /* Silence a harmless warning */ *pn = sqlite3BtreeSeekCount(db->aDb->pBt); break; } Index: src/vdbe.c ================================================================== --- src/vdbe.c +++ src/vdbe.c @@ -135,10 +135,58 @@ static int n = 0; n++; } #endif + +#ifdef SQLITE_DEBUG +/* This is a validation routine that occurs only inside of assert() +** statements. Its purpose is to verify that the generated bytecode +** is correct. It only runs on debugging builds. +** +** Verify that the pOp opcode is an OP_SeekGE or OP_SeekLE that is +** followed by a corresponding OP_IdxGT or OP_IdxLT, possibly with +** an intervening OP_SeekHit. Return 1 if the constraint is true. +** Return 0 if something unexpected is seen. +*/ +static int seekFollowedByPairedIdxCompare(VdbeOp *pOp){ + VdbeOp *pNext; + + /* Find the subsequent opcode. We are allowed to skip over a single + ** OP_SeekHit against the same cursor with a P2 value of 1. + */ + pNext = pOp + 1; + if( pNext->opcode==OP_SeekHit ){ + if( pNext->p2!=1 ) return 0; + if( pNext->p1!=pOp->p1 ) return 0; + pNext++; + } + + /* This routine verifies that the opcodes are correct for a + ** BTREE_SEEK_EQ lookup. So the two opcodes involved must be either: + ** + ** * OP_SeekGE followed by OP_IdxGT + ** * OP_SeekLE followed by OP_IdxLT + */ + if( pOp->opcode==OP_SeekGE ){ + if( pNext->opcode!=OP_IdxGT ) return 0; + }else if( pOp->opcode==OP_SeekLE ){ + if( pNext->opcode!=OP_IdxLT ) return 0; + }else{ + return 0; + } + + /* The OP_SeekXX and OP_IdxXX must have the same arguments. + */ + if( pOp->p1!=pNext->p1 ) return 0; + if( pOp->p2!=pNext->p2 ) return 0; + if( pOp->p3!=pNext->p3 ) return 0; + if( pOp->p4.i!=pNext->p4.i ) return 0; + return 1; +} +#endif /* SQLITE_DEBUG */ + /* ** Invoke the VDBE coverage callback, if that callback is defined. This ** feature is used for test suite validation only and does not appear an ** production builds. ** @@ -4284,22 +4332,16 @@ } }else{ /* For a cursor with the OPFLAG_SEEKEQ/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. + ** with the same key. There might be a single OP_SeekHit opcode in + ** between the OP_SeekXX and OP_IdxXX. */ if( sqlite3BtreeCursorHasHint(pC->uc.pCursor, BTREE_SEEK_EQ) ){ - eqOnly = 1; - assert( pOp->opcode==OP_SeekGE || pOp->opcode==OP_SeekLE ); - assert( pOp[1].opcode==OP_IdxLT || pOp[1].opcode==OP_IdxGT ); - assert( pOp->opcode==OP_SeekGE || pOp[1].opcode==OP_IdxLT ); - assert( pOp->opcode==OP_SeekLE || 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 ); + eqOnly = 1 + (pOp[1].opcode==OP_SeekHit); + assert( seekFollowedByPairedIdxCompare(pOp) ); } nField = pOp->p4.i; assert( pOp->p4type==P4_INT32 ); assert( nField>0 ); @@ -4375,12 +4417,12 @@ assert( pOp->p2>0 ); VdbeBranchTaken(res!=0,2); if( res ){ 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 */ + assert( pOp[eqOnly].opcode==OP_IdxLT || pOp[eqOnly].opcode==OP_IdxGT ); + pOp += eqOnly; /* Skip the OP_IdxLt or OP_IdxGT that follows */ } break; } /* Opcode: SeekHit P1 P2 * * * @@ -4387,20 +4429,20 @@ ** 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. +** P1 must be a valid b-tree cursor. P2 must be an integer +** between 0 and 3. */ case OP_SeekHit: { VdbeCursor *pC; assert( pOp->p1>=0 && pOp->p1nCursor ); pC = p->apCsr[pOp->p1]; assert( pC!=0 ); - assert( pOp->p2==0 || pOp->p2==1 ); - pC->seekHit = pOp->p2 & 1; + assert( pOp->p2>=0 && pOp->p2<=3 ); + pC->seekHit = pOp->p2 & 3; break; } /* Opcode: IfNotOpen P1 P2 * * * ** Synopsis: if( !csr[P1] ) goto P2 @@ -4450,37 +4492,10 @@ ** 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 @@ -4500,19 +4515,10 @@ ** 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->p1nCursor ); - pC = p->apCsr[pOp->p1]; - assert( pC!=0 ); - if( pC->seekHit ) break; - /* Fall through into OP_NotFound */ - /* no break */ deliberate_fall_through -} case OP_NoConflict: /* jump, in3 */ case OP_NotFound: /* jump, in3 */ case OP_Found: { /* jump, in3 */ int alreadyExists; int takeJump; @@ -4525,10 +4531,11 @@ #ifdef SQLITE_TEST if( pOp->opcode!=OP_NoConflict ) sqlite3_found_count++; #endif +vdbe_op_notfound: /* OP_IfNoHope jumps here, sometimes */ assert( pOp->p1>=0 && pOp->p1nCursor ); assert( pOp->p4type==P4_INT32 ); pC = p->apCsr[pOp->p1]; assert( pC!=0 ); #ifdef SQLITE_DEBUG @@ -5863,18 +5870,19 @@ ** ROWID on the P1 index. ** ** If the P1 index entry is less than or equal to the key value then jump ** to P2. Otherwise fall through to the next instruction. */ -case OP_IdxLE: /* jump */ -case OP_IdxGT: /* jump */ -case OP_IdxLT: /* jump */ -case OP_IdxGE: { /* jump */ +case OP_IdxLE: /* jump, group */ +case OP_IdxGT: /* jump, group */ +case OP_IdxLT: /* jump, group */ +case OP_IdxGE: { /* jump, group */ VdbeCursor *pC; int res; UnpackedRecord r; +vdbe_op_idxne: /* Virtual OP_IdxNE opcode. See OP_IfNoHope */ assert( pOp->p1>=0 && pOp->p1nCursor ); pC = p->apCsr[pOp->p1]; assert( pC!=0 ); assert( pC->isOrdered ); assert( pC->eCurType==CURTYPE_BTREE ); @@ -5885,11 +5893,12 @@ r.nField = (u16)pOp->p4.i; if( pOp->opcodeopcode==OP_IdxLE || pOp->opcode==OP_IdxGT ); r.default_rc = -1; }else{ - assert( pOp->opcode==OP_IdxGE || pOp->opcode==OP_IdxLT ); + assert( pOp->opcode==OP_IdxGE || pOp->opcode==OP_IdxLT + || pOp->opcode==OP_IfNoHope ); r.default_rc = 0; } r.aMem = &aMem[pOp->p3]; #ifdef SQLITE_DEBUG { @@ -5902,11 +5911,12 @@ #endif res = 0; /* Not needed. Only used to silence a warning. */ rc = sqlite3VdbeIdxKeyCompare(db, pC, &r, &res); assert( (OP_IdxLE&1)==(OP_IdxLT&1) && (OP_IdxGE&1)==(OP_IdxGT&1) ); if( (pOp->opcode&1)==(OP_IdxLT&1) ){ - assert( pOp->opcode==OP_IdxLE || pOp->opcode==OP_IdxLT ); + assert( pOp->opcode==OP_IdxLE || pOp->opcode==OP_IdxLT + || pOp->opcode==OP_IfNoHope ); res = -res; }else{ assert( pOp->opcode==OP_IdxGE || pOp->opcode==OP_IdxGT ); res++; } @@ -5913,10 +5923,76 @@ VdbeBranchTaken(res>0,2); if( rc ) goto abort_due_to_error; if( res>0 ) goto jump_to_p2; break; } + +/* Opcode: IfNoHope P1 P2 P3 P4 * +** Synopsis: key=r[P3@P4] +** +** Register P3 is the first of P4 registers that form an unpacked +** record. P1 is number of an index-btree cursor. P2 is a jump +** destination. So, in other words, the operands to this opcode +** are the same as the operands to OP_NotFound and OP_IdxGT. +** +** The behavior of this opcode depends on the current seekFlag setting. +** (See the OP_SeekHit.) +** +**
    +**
  • seekHit==0 → OP_NotFound +**
  • seekHit==1 → OP_IdxGT or OP_IdxLT +**
  • seekHit==2 → OP_Noop +**
+** +** Actually, when seekHit==1, this routine behaves as if it were an +** OP_IdxNE opcode. It has all the same parameters as OP_IdxGT and +** OP_IdxLT, but the jump is taken if the key is not equal to the index +** record, rather than if the key is greater than or less than the +** index record, respectively. +** +** 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. +** +** This opcode is an optimization. It can always behave as OP_Noop +** and the correct result will still be obtained, though perhaps not +** quite as quickly. +** +** See also: NotFound, SeekHit, IdxGT +*/ +case OP_IfNoHope: { /* jump, in3, group */ + VdbeCursor *pC; + assert( pOp->p1>=0 && pOp->p1nCursor ); + pC = p->apCsr[pOp->p1]; + assert( pC!=0 ); + assert( pC->eCurType==CURTYPE_BTREE ); + if( pC->seekHit>=2 ){ + /* There has been one or more successful OP_IdxXX opcodes ("successful" + ** in the sense that the jump was not taken because the key and index + ** matched). So a match is possible. We do not want to abort. Fall + ** through to the next opcode without doing anything. */ + break; + }else if( pC->seekHit==1 ){ + /* The initial OP_SeekXX opcode was successful (in that it found a + ** candidate row) but all subsequent OP_IdxXX opcodes failed. The + ** index should have been left pointing at the candidate row. In this + ** case, this opcode works like a "OP_IdxNE" opcode - similar to + ** OP_IdxGT but instead of jumping if the index entry is greater than + ** the key, it jumps if the index entry is not equal to the key. + */ + goto vdbe_op_idxne; + } + /* The initial OP_SeekXX opcode took its jump, meaning that it found + ** no candidate rows. Treat this opcode as if it were an OP_NotFound */ + goto vdbe_op_notfound; +} /* Opcode: Destroy P1 P2 P3 * * ** ** Delete an entire database table or index whose root page in the database ** file is given by P1. Index: src/vdbeInt.h ================================================================== --- src/vdbeInt.h +++ src/vdbeInt.h @@ -84,11 +84,11 @@ 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 */ + unsigned seekHit:2; /* See the OP_SeekHit and OP_IfNoHope opcodes */ Btree *pBtx; /* Separate file holding temporary table */ i64 seqCount; /* Sequence counter */ u32 *aAltMap; /* Mapping from table to index column numbers */ /* Cached OP_Column parse information is only valid if cacheStatus matches Index: src/wherecode.c ================================================================== --- src/wherecode.c +++ src/wherecode.c @@ -1868,10 +1868,13 @@ /* Top of the loop body */ pLevel->p2 = sqlite3VdbeCurrentAddr(v); /* Check if the index cursor is past the end of the range. */ if( nConstraint ){ + if( pLoop->wsFlags & WHERE_IN_EARLYOUT ){ + sqlite3VdbeAddOp2(v, OP_SeekHit, iIdxCur, 1); + } if( regBignull ){ /* Except, skip the end-of-range check while doing the NULL-scan */ sqlite3VdbeAddOp2(v, OP_IfNot, regBignull, sqlite3VdbeCurrentAddr(v)+3); VdbeComment((v, "If NULL-scan 2nd pass")); VdbeCoverage(v); @@ -1900,11 +1903,11 @@ 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); + sqlite3VdbeAddOp2(v, OP_SeekHit, iIdxCur, 2); } /* Seek the table cursor, if required */ omitTable = (pLoop->wsFlags & WHERE_IDX_ONLY)!=0 && (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)==0;