From e054f82d2d834faef16994815d9557c668da6aa3 Mon Sep 17 00:00:00 2001 From: drh <> Date: Fri, 7 Oct 2022 19:11:22 +0000 Subject: [PATCH] Fix a problem causing the seek-scan optimization to skip over valid rows that could occur when it is used with expressions of the form (a IN (?,?..) AND b >= ?). dbsqlfuzz ab1db6dc0efb04cba1cd3431ee6da4894fdc4520. FossilOrigin-Name: b6be4ce6db3a891029a56a34edf61283b442fa67b4f1982e880be5cc69bd8058 --- manifest | 17 +++++---- manifest.uuid | 2 +- src/vdbe.c | 93 +++++++++++++++++++++++++++++++-------------- src/wherecode.c | 5 +++ test/seekscan1.test | 63 ++++++++++++++++++++++++++++++ 5 files changed, 142 insertions(+), 38 deletions(-) create mode 100644 test/seekscan1.test diff --git a/manifest b/manifest index e662921547..bc56d490f6 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Fix\sa\sproblem\sthat\soccurred\swhen\susing\sa\sbloom\sfilter\sto\soptimize\san\s(ipk\s=\s?)\slookup\sin\sthe\scase\swhere\sthe\sRHS\sof\sthe\sexpression\sis\sa\sTEXT\svalue.\sFirst\sreported\sby\s[forum:/forumpost/f61a8b7053|forum\spost\sf61a8b7053]. -D 2022-10-07T18:06:51.355 +C Fix\sa\sproblem\scausing\sthe\sseek-scan\soptimization\sto\sskip\sover\svalid\srows\sthat\scould\soccur\swhen\sit\sis\sused\swith\sexpressions\sof\sthe\sform\s(a\sIN\s(?,?..)\sAND\sb\s>=\s?).\sdbsqlfuzz\sab1db6dc0efb04cba1cd3431ee6da4894fdc4520. +D 2022-10-07T19:11:22.290 F .fossil-settings/empty-dirs dbb81e8fc0401ac46a1491ab34a7f2c7c0452f2f06b54ebb845d024ca8283ef1 F .fossil-settings/ignore-glob 35175cdfcf539b2318cb04a9901442804be81cd677d8b889fcc9149c21f239ea F LICENSE.md df5091916dbb40e6e9686186587125e1b2ff51f022cc334e886c19a0e9982724 @@ -642,7 +642,7 @@ F src/upsert.c 8789047a8f0a601ea42fa0256d1ba3190c13746b6ba940fe2d25643a7e991937 F src/utf.c ee39565f0843775cc2c81135751ddd93eceb91a673ea2c57f61c76f288b041a0 F src/util.c 0be191521ff6d2805995f4910f0b6231b42843678b2efdc1abecaf39929a673f F src/vacuum.c bb346170b0b54c6683bba4a5983aea40485597fdf605c87ec8bc2e199fe88cd8 -F src/vdbe.c 3df15f0f2cd9d8faeeea18398a62f16c07fda2bfd8d726186f07508ad69b40e2 +F src/vdbe.c 08494341a3d67af1c83517cfb3ff3a493720974efbdd4cecd6966314ff26725b F src/vdbe.h 07641758ca8b4f4c6d81ea667ea167c541e6ece21f5574da11e3d21ec37e2662 F src/vdbeInt.h 2cad0aeeb106371ed0e0946bab89f60627087068847afc2451c05056961c18da F src/vdbeapi.c 602610f1252d59cd69742f78a1e2f6fbae40a4b407f5506a6a7b869b0df08ff2 @@ -659,7 +659,7 @@ F src/wal.h c3aa7825bfa2fe0d85bef2db94655f99870a285778baa36307c0a16da32b226a F src/walker.c f890a3298418d7cba3b69b8803594fdc484ea241206a8dfa99db6dd36f8cbb3b F src/where.c e7b7c9d37f4f8d14d4d05b20e57ae43712a51ffed7d45f547a23f9c42ee483dd F src/whereInt.h b48ca529ffe293c18cbfa8326af18a09e39910de66fb3e96ef788c7cbf8ef3a7 -F src/wherecode.c 4f05c8af3fb1312807654e517de08203c40479b48614fccaedcdf44c628209d7 +F src/wherecode.c 3851a23caf13b9f4cda390525fad14f57a74cf6fe7bdac4f56b0754564079bdc F src/whereexpr.c 55a39f42aaf982574fbf52906371a84cceed98a994422198dfd03db4fce4cc46 F src/window.c fff1b51757438c664e471d5184634e48dcdf8ea34b640f3b1b0810b1e06de18c F test/8_3_names.test ebbb5cd36741350040fd28b432ceadf495be25b2 @@ -1389,6 +1389,7 @@ F test/schema6.test e4bd1f23d368695eb9e7b51ef6e02ca0642ea2ab4a52579959826b5e7dce F test/schemafault.test 1936bceca55ac82c5efbcc9fc91a1933e45c8d1e1d106b9a7e56c972a5a2a51e F test/securedel.test 2f70b2449186a1921bd01ec9da407fbfa98c3a7a5521854c300c194b2ff09384 F test/securedel2.test 2d54c28e46eb1fd6902089958b20b1b056c6f1c5 +F test/seekscan1.test d79c97de5bb1dd1fd466687f3014add514fddf8248c57baf51d749c7dfd573d8 F test/select1.test 692e84cfa29c405854c69e8a4027183d64c22952866a123fabbce741a379e889 F test/select2.test 352480e0e9c66eda9c3044e412abdf5be0215b56 F test/select3.test ce4f78bbc809b0513f960f1ee84cdbc5af50ba112c343d5266558a8b2468f656 @@ -1979,9 +1980,9 @@ F vsixtest/vsixtest.tcl 6a9a6ab600c25a91a7acc6293828957a386a8a93 F vsixtest/vsixtest.vcxproj.data 2ed517e100c66dc455b492e1a33350c1b20fbcdc F vsixtest/vsixtest.vcxproj.filters 37e51ffedcdb064aad6ff33b6148725226cd608e F vsixtest/vsixtest_TemporaryKey.pfx e5b1b036facdb453873e7084e1cae9102ccc67a0 -P 8eb0048ece0259e4bfef5de1bfee0b860839ae97756020b40e1d6a8e3a2ea119 -Q +8e14c351b29bb434ac4e2510681e95716424a73e340d39feff4919f0431c2e00 -R 42894e9b44d60bc4074dcd1d624092ac +P dc01d9d8d898ac864811d39e7f3a47be2f179bbda137500da6874f461315d4b3 +Q +63d9efe277759d4daa29794846b60c6f55491496618f423f61468df72d0a4633 +R 55384e6cde5f657b1f4f77e3ca0dab48 U drh -Z 939678c5b31e195a348345a08acb669c +Z 52a758abbd21692f0699035570eb82b6 # Remove this line to create a well-formed Fossil manifest. diff --git a/manifest.uuid b/manifest.uuid index ef539c13a4..c9f97a7d27 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -dc01d9d8d898ac864811d39e7f3a47be2f179bbda137500da6874f461315d4b3 \ No newline at end of file +b6be4ce6db3a891029a56a34edf61283b442fa67b4f1982e880be5cc69bd8058 \ No newline at end of file diff --git a/src/vdbe.c b/src/vdbe.c index ef9a23f64e..de2a108bba 100644 --- a/src/vdbe.c +++ b/src/vdbe.c @@ -4708,7 +4708,7 @@ seek_not_found: } -/* Opcode: SeekScan P1 P2 * * * +/* Opcode: SeekScan P1 P2 * * P5 ** Synopsis: Scan-ahead up to P1 rows ** ** This opcode is a prefix opcode to OP_SeekGE. In other words, this @@ -4718,8 +4718,8 @@ seek_not_found: ** This opcode uses the P1 through P4 operands of the subsequent ** OP_SeekGE. In the text that follows, the operands of the subsequent ** OP_SeekGE opcode are denoted as SeekOP.P1 through SeekOP.P4. Only -** the P1 and P2 operands of this opcode are also used, and are called -** This.P1 and This.P2. +** the P1, P2 and P5 operands of this opcode are also used, and are called +** This.P1, This.P2 and This.P5. ** ** This opcode helps to optimize IN operators on a multi-column index ** where the IN operator is on the later terms of the index by avoiding @@ -4729,29 +4729,51 @@ seek_not_found: ** ** The SeekGE.P3 and SeekGE.P4 operands identify an unpacked key which ** is the desired entry that we want the cursor SeekGE.P1 to be pointing -** to. Call this SeekGE.P4/P5 row the "target". +** to. Call this SeekGE.P3/P4 row the "target". ** ** If the SeekGE.P1 cursor is not currently pointing to a valid row, ** then this opcode is a no-op and control passes through into the OP_SeekGE. ** ** If the SeekGE.P1 cursor is pointing to a valid row, then that row ** might be the target row, or it might be near and slightly before the -** target row. This opcode attempts to position the cursor on the target -** row by, perhaps by invoking sqlite3BtreeStep() on the cursor -** between 0 and This.P1 times. -** -** There are three possible outcomes from this opcode:
    -** -**
  1. If after This.P1 steps, the cursor is still pointing to a place that -** is earlier in the btree than the target row, then fall through -** into the subsquence OP_SeekGE opcode. -** -**
  2. If the cursor is successfully moved to the target row by 0 or more -** sqlite3BtreeNext() calls, then jump to This.P2, which will land just -** past the OP_IdxGT or OP_IdxGE opcode that follows the OP_SeekGE. -** -**
  3. If the cursor ends up past the target row (indicating the the target -** row does not exist in the btree) then jump to SeekOP.P2. +** target row, or it might be after the target row. If the cursor is +** currently before the target row, then this opcode attempts to position +** the cursor on or after the target row by invoking sqlite3BtreeStep() +** on the cursor between 1 and This.P1 times. +** +** The This.P5 parameter is a flag that indicates what to do if the +** cursor ends up pointing at a valid row that is past the target +** row. If This.P5 is false (0) then a jump is made to SeekGE.P2. If +** This.P5 is true (non-zero) then a jump is made to This.P2. The P5==0 +** case occurs when there are no inequality constraints to the right of +** the IN constraing. The jump to SeekGE.P2 ends the loop. The P5!=0 case +** occurs when there are inequality constraints to the right of the IN +** operator. In that case, the This.P2 will point either directly to or +** to setup code prior to the OP_IdxGT or OP_IdxGE opcode that checks for +** loop terminate. +** +** Possible outcomes from this opcode:
      +** +**
    1. If the cursor is initally not pointed to any valid row, then +** fall through into the subsequent OP_SeekGE opcode. +** +**
    2. If the cursor is left pointing to a row that is before the target +** row, even after making as many as This.P1 calls to +** sqlite3BtreeNext(), then also fall through into OP_SeekGE. +** +**
    3. If the cursor is left pointing at the target row, either because it +** was at the target row to begin with or because one or more +** sqlite3BtreeNext() calls moved the cursor to the target row, +** then jump to This.P2.., +** +**
    4. If the cursor started out before the target row and a call to +** to sqlite3BtreeNext() moved the cursor off the end of the index +** (indicating that the target row definitely does not exist in the +** btree) then jump to SeekGE.P2, ending the loop. +** +**
    5. If the cursor ends up on a valid row that is past the target row +** (indicating that the target row does not exist in the btree) then +** jump to SeekOP.P2 if This.P5==0 or to This.P2 if This.P5>0. **
    */ case OP_SeekScan: { @@ -4762,14 +4784,25 @@ case OP_SeekScan: { assert( pOp[1].opcode==OP_SeekGE ); - /* pOp->p2 points to the first instruction past the OP_IdxGT that - ** follows the OP_SeekGE. */ + /* If pOp->p5 is clear, then pOp->p2 points to the first instruction past the + ** OP_IdxGT that follows the OP_SeekGE. Otherwise, it points to the first + ** opcode past the OP_SeekGE itself. */ assert( pOp->p2>=(int)(pOp-aOp)+2 ); - assert( aOp[pOp->p2-1].opcode==OP_IdxGT || aOp[pOp->p2-1].opcode==OP_IdxGE ); - testcase( aOp[pOp->p2-1].opcode==OP_IdxGE ); - assert( pOp[1].p1==aOp[pOp->p2-1].p1 ); - assert( pOp[1].p2==aOp[pOp->p2-1].p2 ); - assert( pOp[1].p3==aOp[pOp->p2-1].p3 ); +#ifdef SQLITE_DEBUG + if( pOp->p5==0 ){ + /* There are no inequality constraints following the IN constraint. */ + assert( pOp[1].p1==aOp[pOp->p2-1].p1 ); + assert( pOp[1].p2==aOp[pOp->p2-1].p2 ); + assert( pOp[1].p3==aOp[pOp->p2-1].p3 ); + assert( aOp[pOp->p2-1].opcode==OP_IdxGT + || aOp[pOp->p2-1].opcode==OP_IdxGE ); + testcase( aOp[pOp->p2-1].opcode==OP_IdxGE ); + }else{ + /* There are inequality constraints. */ + assert( pOp->p2==(int)(pOp-aOp)+2 ); + assert( aOp[pOp->p2-1].opcode==OP_SeekGE ); + } +#endif assert( pOp->p1>0 ); pC = p->apCsr[pOp[1].p1]; @@ -4803,8 +4836,9 @@ case OP_SeekScan: { while(1){ rc = sqlite3VdbeIdxKeyCompare(db, pC, &r, &res); if( rc ) goto abort_due_to_error; - if( res>0 ){ + if( res>0 && pOp->p5==0 ){ seekscan_search_fail: + /* Jump to SeekGE.P2, ending the loop */ #ifdef SQLITE_DEBUG if( db->flags&SQLITE_VdbeTrace ){ printf("... %d steps and then skip\n", pOp->p1 - nStep); @@ -4814,7 +4848,8 @@ case OP_SeekScan: { pOp++; goto jump_to_p2; } - if( res==0 ){ + if( res>=0 ){ + /* Jump to This.P2, bypassing the OP_SeekGE opcode */ #ifdef SQLITE_DEBUG if( db->flags&SQLITE_VdbeTrace ){ printf("... %d steps and then success\n", pOp->p1 - nStep); diff --git a/src/wherecode.c b/src/wherecode.c index e26504aace..1fc6f88399 100644 --- a/src/wherecode.c +++ b/src/wherecode.c @@ -2038,6 +2038,11 @@ Bitmask sqlite3WhereCodeOneLoopStart( ** guess. */ addrSeekScan = sqlite3VdbeAddOp1(v, OP_SeekScan, (pIdx->aiRowLogEst[0]+9)/10); + if( pRangeStart ){ + sqlite3VdbeChangeP5(v, 1); + sqlite3VdbeChangeP2(v, addrSeekScan, sqlite3VdbeCurrentAddr(v)+1); + addrSeekScan = 0; + } VdbeCoverage(v); } sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint); diff --git a/test/seekscan1.test b/test/seekscan1.test new file mode 100644 index 0000000000..e68d71449d --- /dev/null +++ b/test/seekscan1.test @@ -0,0 +1,63 @@ +# 2022 October 7 +# +# 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. +# +#*********************************************************************** +# This file implements regression tests for SQLite library. +# + +set testdir [file dirname $argv0] +source $testdir/tester.tcl +set testprefix seekscan1 + +do_execsql_test 1.0 { + CREATE TABLE t1(a TEXT, b INT, c INT NOT NULL, PRIMARY KEY(a,b,c)); + WITH RECURSIVE c(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM c WHERE x<1997) + INSERT INTO t1(a,b,c) SELECT printf('xyz%d',x/10),x/6,x FROM c; + INSERT INTO t1 VALUES('abc',234,6); + INSERT INTO t1 VALUES('abc',345,7); + ANALYZE; +} + +do_execsql_test 1.1 { + SELECT a,b,c FROM t1 + WHERE b IN (234, 345) AND c BETWEEN 6 AND 6.5 AND a='abc' + ORDER BY a, b; +} { + abc 234 6 +} + +do_execsql_test 1.2 { + SELECT a,b,c FROM t1 + WHERE b IN (234, 345) AND c BETWEEN 6 AND 7 AND a='abc' + ORDER BY a, b; +} { + abc 234 6 + abc 345 7 +} + +do_execsql_test 1.3 { + SELECT a,b,c FROM t1 + WHERE b IN (234, 345) AND c >=6 AND a='abc' + ORDER BY a, b; +} { + abc 234 6 + abc 345 7 +} + +do_execsql_test 1.4 { + SELECT a,b,c FROM t1 + WHERE b IN (234, 345) AND c<=7 AND a='abc' + ORDER BY a, b; +} { + abc 234 6 + abc 345 7 +} + + +finish_test -- 2.47.2