Add test cases and fix a comment.
FossilOrigin-Name: 50f8ea37fb9647c4a9da2c269a4d6f54b10ce96b
diff --git a/manifest b/manifest
index 0e15122..b810c20 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/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/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/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/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.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 6da37e4..213abdc 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 c027cf0..c6d74cf 100644
--- a/src/expr.c
+++ b/src/expr.c
@@ -3994,10 +3994,10 @@
}
/*
-** 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 6a02574..699dc2a 100644
--- a/src/where.c
+++ b/src/where.c
@@ -2478,11 +2478,11 @@
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 0000000..bb58228
--- /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 ed24d97..48365a8 100644
--- a/test/scanstatus.test
+++ b/test/scanstatus.test
@@ -333,7 +333,7 @@
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_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=?)}
}