From e604ec0be02b4e550883c0998c5872a2ba2459ce Mon Sep 17 00:00:00 2001 From: drh Date: Wed, 27 Jul 2016 19:20:58 +0000 Subject: [PATCH] Add test cases and fix a comment. FossilOrigin-Name: 50f8ea37fb9647c4a9da2c269a4d6f54b10ce96b --- manifest | 20 +++++++-------- manifest.uuid | 2 +- src/expr.c | 8 +++--- src/where.c | 4 +-- test/index8.test | 60 ++++++++++++++++++++++++++++++++++++++++++++ test/scanstatus.test | 4 +-- 6 files changed, 78 insertions(+), 20 deletions(-) create mode 100644 test/index8.test diff --git a/manifest b/manifest index 0e15122481..b810c2000b 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C When\sestimating\sthe\scost\sof\san\sindex\sscan,\sfactor\sin\sthe\scost\ssavings\sof\nbeing\sable\sto\suse\sthe\sindex\sto\sevaluate\ssome\sWHERE\sclause\sterms\swithout\nhaving\sto\sdo\sa\stable\slookup. -D 2016-07-27T18:27:02.556 +C Add\stest\scases\sand\sfix\sa\scomment. +D 2016-07-27T19:20:58.611 F Makefile.in 6c20d44f72d4564f11652b26291a214c8367e5db F Makefile.linux-gcc 7bc79876b875010e8c8f9502eb935ca92aa3c434 F Makefile.msc d66d0395c38571aab3804f8db0fa20707ae4609a @@ -337,7 +337,7 @@ F src/ctime.c 61949e83c4c36e37195a8398ebc752780b534d95 F src/date.c 1cc9fb516ec9932c6fd4d2a0d2f8bc4480145c39 F src/dbstat.c 4f6f7f52b49beb9636ffbd517cfe44a402ba4ad0 F src/delete.c 4aba4214a377ce8ddde2d2e609777bcc8235200f -F src/expr.c 3347e66d4e27ec5f3ec7573b9a5f899bbd7d1df8 +F src/expr.c fbc17c717a80b5b61158ea8f25b5af6f8cad66f8 F src/fault.c 160a0c015b6c2629d3899ed2daf63d75754a32bb F src/fkey.c bc4145347595b7770f9a598cff1c848302cf5413 F src/func.c 61a4114cf7004f10c542cfabbab9f2bcb9033045 @@ -463,7 +463,7 @@ F src/vxworks.h d2988f4e5a61a4dfe82c6524dd3d6e4f2ce3cdb9 F src/wal.c 02eeecc265f6ffd0597378f5d8ae9070b62a406a F src/wal.h 6dd221ed384afdc204bc61e25c23ef7fd5a511f2 F src/walker.c 0f142b5bd3ed2041fc52d773880748b212e63354 -F src/where.c 7e4d676b5ac4434e5f93606a744d396dc40d9977 +F src/where.c 66a290310e71491ffc9c74108413176438aa8718 F src/whereInt.h e5b939701a7ceffc5a3a8188a37f9746416ebcd0 F src/wherecode.c 99707d11907c71d289ee9553d2d1a22f1fd8ba41 F src/whereexpr.c d7dcbf14ce1b5876c1f76496162c30fcba669563 @@ -845,6 +845,7 @@ F test/index4.test ab92e736d5946840236cd61ac3191f91a7856bf6 F test/index5.test 8621491915800ec274609e42e02a97d67e9b13e7 F test/index6.test 43b4e29258b978fcdab84fc61df4f5212119dd09 F test/index7.test 9c6765a74fc3fcde7aebc5b3bd40d98df14a527c +F test/index8.test bc2e3db70e8e62459aaa1bd7e4a9b39664f8f9d7 F test/indexedby.test 9c4cd331224e57f79fbf411ae245e6272d415985 F test/indexexpr1.test cb71b6586177b840e28110dd952178bb2bdfedc2 F test/indexfault.test 31d4ab9a7d2f6e9616933eb079722362a883eb1d @@ -1026,7 +1027,7 @@ F test/savepoint5.test 0735db177e0ebbaedc39812c8d065075d563c4fd F test/savepoint6.test f41279c5e137139fa5c21485773332c7adb98cd7 F test/savepoint7.test cde525ea3075283eb950cdcdefe23ead4f700daa F test/savepointfault.test f044eac64b59f09746c7020ee261734de82bf9b2 -F test/scanstatus.test 5253c219e331318a437f436268e0e82345700285 +F test/scanstatus.test 030acbbdcea6a3fc676fee99edc84f6f16c0cf92 F test/schema.test 8f7999be894260f151adf15c2c7540f1c6d6a481 F test/schema2.test 906408621ea881fdb496d878b1822572a34e32c5 F test/schema3.test 1bc1008e1f8cb5654b248c55f27249366eb7ed38 @@ -1507,10 +1508,7 @@ F vsixtest/vsixtest.tcl 6a9a6ab600c25a91a7acc6293828957a386a8a93 F vsixtest/vsixtest.vcxproj.data 2ed517e100c66dc455b492e1a33350c1b20fbcdc F vsixtest/vsixtest.vcxproj.filters 37e51ffedcdb064aad6ff33b6148725226cd608e F vsixtest/vsixtest_TemporaryKey.pfx e5b1b036facdb453873e7084e1cae9102ccc67a0 -P 483994a54dee3c7a3801e0e9d3c96fa9dbd8d2fd -R 9e4bd013f5c2cf2171d472668aed0d1c -T *branch * improved-index-scan -T *sym-improved-index-scan * -T -sym-trunk * +P a59b5622f7cc6e502d71aabc12c053582cd03609 +R f515f9eadedb75a99af064851213e82e U drh -Z 8f3398744130761f466da0e8b7212fe4 +Z 99f5c72d7c6c2cd0c635c52258200786 diff --git a/manifest.uuid b/manifest.uuid index 6da37e4d78..213abdc7d3 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -a59b5622f7cc6e502d71aabc12c053582cd03609 \ No newline at end of file +50f8ea37fb9647c4a9da2c269a4d6f54b10ce96b \ No newline at end of file diff --git a/src/expr.c b/src/expr.c index c027cf02a4..c6d74cfd32 100644 --- a/src/expr.c +++ b/src/expr.c @@ -3994,10 +3994,10 @@ static int exprIdxCover(Walker *pWalker, Expr *pExpr){ } /* -** Determine if an index on table iCur that contains the columns in -** Bitmask m will cover the expression pExpr. Return true if the index -** does cover the expression and false if the expression references -** table columns that are not found in the index. +** Determine if an index pIdx on table with cursor iCur contains will +** the expression pExpr. Return true if the index does cover the +** expression and false if the pExpr expression references table columns +** that are not found in the index pIdx. ** ** An index covering an expression means that the expression can be ** evaluated using only the index and without having to lookup the diff --git a/src/where.c b/src/where.c index 6a02574921..699dc2a614 100644 --- a/src/where.c +++ b/src/where.c @@ -2478,11 +2478,11 @@ static int whereLoopAddBtreeIndex( pNew->nSkip++; pNew->aLTerm[pNew->nLTerm++] = 0; pNew->wsFlags |= WHERE_SKIPSCAN; - nIter = pProbe->aiRowLogEst[saved_nEq] - pProbe->aiRowLogEst[saved_nEq+1]; + nIter = pProbe->aiRowLogEst[saved_nEq]+1 - pProbe->aiRowLogEst[saved_nEq+1]; pNew->nOut -= nIter; /* TUNING: Because uncertainties in the estimates for skip-scan queries, ** add a 1.375 fudge factor to make skip-scan slightly less likely. */ - nIter += 5; + nIter += 4; whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nIter + nInMul); pNew->nOut = saved_nOut; pNew->u.btree.nEq = saved_nEq; diff --git a/test/index8.test b/test/index8.test new file mode 100644 index 0000000000..bb58228527 --- /dev/null +++ b/test/index8.test @@ -0,0 +1,60 @@ +# 2016-07-27 +# +# 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. +# +#*********************************************************************** +# +# Test cases for ORDER BY and LIMIT on an index scan. +# + + +set testdir [file dirname $argv0] +source $testdir/tester.tcl + +# Performance regression reported at +# http://www.mail-archive.com/sqlite-users@mailinglists.sqlite.org/msg98615.html +# +# Caused by the ORDER BY LIMIT optionation for check-in +# https://sqlite.org/src/info/bf46179d44843769 +# +# Fixed on approximately 2016-07-27 by changes that compute a better score +# for index scans by taking into account WHERE clause constraints that can +# be handled by the index and do not require a table lookup. +# +do_execsql_test 1.0 { + CREATE TABLE t1(a,b,c,d); + WITH RECURSIVE c(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM c WHERE x<100) + INSERT INTO t1(a,b,c,d) + SELECT x/10, x%10, x%19, x FROM c; + CREATE INDEX t1abc ON t1(a,b,c); + SELECT * FROM t1 WHERE c=4 ORDER BY a, b LIMIT 2; +} {0 4 4 4 2 3 4 23} + +# Prior to the fix, the following EQP would show a table scan and a sort +# rather than an index scan. +# +do_execsql_test 1.0eqp { + EXPLAIN QUERY PLAN + SELECT * FROM t1 WHERE c=4 ORDER BY a, b LIMIT 2; +} {/SCAN TABLE t1 USING INDEX t1abc/} + +# If we change the index so that it no longer covers the WHERE clause, +# then we should (correctly) revert to using a table scan. +# +do_execsql_test 1.1 { + DROP INDEX t1abc; + CREATE INDEX t1abd ON t1(a,b,d); + SELECT * FROM t1 WHERE c=4 ORDER BY a, b LIMIT 2; +} {0 4 4 4 2 3 4 23} +do_execsql_test 1.1eqp { + EXPLAIN QUERY PLAN + SELECT * FROM t1 WHERE c=4 ORDER BY a, b LIMIT 2; +} {~/USING INDEX/} + + +finish_test diff --git a/test/scanstatus.test b/test/scanstatus.test index ed24d97437..48365a8794 100644 --- a/test/scanstatus.test +++ b/test/scanstatus.test @@ -333,7 +333,7 @@ do_execsql_test 5.3.2 { SELECT count(*) FROM t2 WHERE y = 'j'; } {19} do_scanstatus_test 5.3.3 { - nLoop 1 nVisit 19 nEst 56.0 zName t2xy zExplain + nLoop 1 nVisit 19 nEst 52.0 zName t2xy zExplain {SEARCH TABLE t2 USING COVERING INDEX t2xy (ANY(x) AND y=?)} } @@ -349,7 +349,7 @@ do_execsql_test 5.4.2 { do_scanstatus_test 5.4.3 { nLoop 1 nVisit 10 nEst 10.0 zName t1bc zExplain {SCAN TABLE t1 USING COVERING INDEX t1bc} - nLoop 10 nVisit 200 nEst 56.0 zName t2xy + nLoop 10 nVisit 200 nEst 52.0 zName t2xy zExplain {SEARCH TABLE t2 USING COVERING INDEX t2xy (ANY(x) AND y=?)} } -- 2.39.5