From b80ffe626ceb3aa0d40773713e9b2c17227d687f Mon Sep 17 00:00:00 2001 From: drh Date: Mon, 29 Feb 2016 23:02:50 +0000 Subject: [PATCH] Improvements to the logic for adding the "noskipscan" flag to stat1 entries. FossilOrigin-Name: 421b5b544af734b97e3da47699fa0f82b21617d3 --- manifest | 14 ++++---- manifest.uuid | 2 +- src/analyze.c | 24 +++++++------ test/skipscan2.test | 86 ++++++++++++++++----------------------------- 4 files changed, 52 insertions(+), 74 deletions(-) diff --git a/manifest b/manifest index 32bc41890c..e22606ca78 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C The\sANALYZE\scommand\sautomatically\sappends\s"noskipscan"\sto\ssqlite_stat1\sentries\nthat\shave\slarge\sworst-case\srepeat\sestimates\sbut\ssmall\saverage\srepeat\sestimates. -D 2016-02-29T21:27:16.923 +C Improvements\sto\sthe\slogic\sfor\sadding\sthe\s"noskipscan"\sflag\sto\sstat1\sentries. +D 2016-02-29T23:02:50.488 F Makefile.in 4e90dc1521879022aa9479268a4cd141d1771142 F Makefile.linux-gcc 7bc79876b875010e8c8f9502eb935ca92aa3c434 F Makefile.msc 4f319afb7c049d40aff7af6e8c4e7cc2ba18e079 @@ -286,7 +286,7 @@ F sqlite.pc.in 42b7bf0d02e08b9e77734a47798d1a55a9e0716b F sqlite3.1 fc7ad8990fc8409983309bb80de8c811a7506786 F sqlite3.pc.in 48fed132e7cb71ab676105d2a4dc77127d8c1f3a F src/alter.c 44e18dfd78e8942d65d3cdaec4de972b5cd9f1f2 -F src/analyze.c 95b2e37e92cbeb9093700b8248e1ec73b3da417b +F src/analyze.c 997b0ce0f4efd68b0499f941ebebdd1ec0c71549 F src/attach.c a3724c64de1099d85e30751213d285752aed9505 F src/auth.c b56c78ebe40a2110fd361379f7e8162d23f92240 F src/backup.c f60f0aa55d25d853ffde53d0b0370a7bb7ee41ce @@ -1030,7 +1030,7 @@ F test/show_speedtest1_rtree.tcl 32e6c5f073d7426148a6936a0408f4b5b169aba5 F test/shrink.test 1b4330b1fd9e818c04726d45cb28db73087535ce F test/sidedelete.test f0ad71abe6233e3b153100f3b8d679b19a488329 F test/skipscan1.test d37a75b4be4eb9dedeb69b4f38b1d0a74b5021d7 -F test/skipscan2.test d1d1450952b7275f0b0a3a981f0230532743951a +F test/skipscan2.test 9fb533b9b66d33d5036fa86bbad1c1ae20861a3f F test/skipscan3.test ec5bab3f81c7038b43450e7b3062e04a198bdbb5 F test/skipscan5.test 67817a4b6857c47e0e33ba3e506da6f23ef68de2 F test/skipscan6.test 5866039d03a56f5bd0b3d172a012074a1d90a15b @@ -1451,7 +1451,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 5a0143c94ec0682798f3c09fba63593e695d2e2d -R 177b6cf14f8f11e0a114dc66d2d822d0 +P 6326ba5891fae9c6be0c0c51cebcbe44c9f3f057 +R d11c7934d7e6b9fd5164f25abb15ccbc U drh -Z ca3d3ef3ca17a24048e080e522e9cbee +Z e3fa57a0ace16605a0bcfe31fb8b1cb6 diff --git a/manifest.uuid b/manifest.uuid index f8a9fd14ea..c321bd6bb3 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -6326ba5891fae9c6be0c0c51cebcbe44c9f3f057 \ No newline at end of file +421b5b544af734b97e3da47699fa0f82b21617d3 \ No newline at end of file diff --git a/src/analyze.c b/src/analyze.c index 776d9c44c5..9c3c37b05b 100644 --- a/src/analyze.c +++ b/src/analyze.c @@ -844,13 +844,15 @@ static void statGet( ** * "WHERE a=?" matches 10 rows, and ** * "WHERE a=? AND b=?" matches 2 rows. ** - ** Use the worst-case estimate: the maximum number of repeated entries - ** in the index. The worst-case estimate is best for picking indexes. - ** But for skip-scan, we want an average case estimate. The worst-case - ** estimate might be too high. To avoid undesirable skip-scans, if the - ** worst-case estimate is above the WHERE_SKIPSCAN_ONSET but the average - ** estimate is below, simply disable skipscans on this index by adding - ** the "noskipscan" modifier onto the end of the stat line. + ** A worst-case estimate is used: the maximum number of rows that + ** could be select for any set of query parameters. The worst case + ** is the estimate we want for choosing indexes. + ** + ** For deciding whether or not to do a skip-scan, we want to know the + ** average number of rows with the same key. We can approximate this + ** using the (worst case) most number of rows with the same key. But + ** sometimes that approximation can be badly off. In those cases, + ** mark the index as "noskipscan" to avoid suboptimal skip-scan plans. */ char *z; int i; @@ -869,10 +871,10 @@ static void statGet( sqlite3_snprintf(24, z, " %llu", iVal); z += sqlite3Strlen30(z); assert( p->current.anEq[i] ); - if( i>0 && iVal>=WHERE_SKIPSCAN_ONSET+5 ){ - iVal = p->current.anDLt[i]; - iVal = (p->nRow + iVal)/(iVal + 1); - if( iVal=WHERE_SKIPSCAN_ONSET + && p->current.anDLt[i] > p->nRow/(WHERE_SKIPSCAN_ONSET*2/3) + ){ + noSkipScan = 1; } } if( noSkipScan ) sqlite3_snprintf(14, z, " noskipscan"); diff --git a/test/skipscan2.test b/test/skipscan2.test index a42ff2d057..35ca8269ab 100644 --- a/test/skipscan2.test +++ b/test/skipscan2.test @@ -48,22 +48,24 @@ do_execsql_test skipscan2-1.2 { INSERT INTO people VALUES('Robert','student',159); INSERT INTO people VALUES('Sally','student',166); INSERT INTO people VALUES('Tom','student',171); +/* INSERT INTO people VALUES('Ursula','student',170); INSERT INTO people VALUES('Vance','student',179); INSERT INTO people VALUES('Willma','student',175); INSERT INTO people VALUES('Xavier','teacher',185); INSERT INTO people VALUES('Yvonne','student',149); INSERT INTO people VALUES('Zach','student',170); +*/ } # Without ANALYZE, a skip-scan is not used # do_execsql_test skipscan2-1.3 { - SELECT name FROM people WHERE height>=180 ORDER BY +name; -} {David Jack Patrick Quiana Xavier} + SELECT name FROM people WHERE height<=161 ORDER BY +name; +} {Alice Bob Cindy Emily Megan Olivia Robert} do_execsql_test skipscan2-1.3eqp { EXPLAIN QUERY PLAN - SELECT name FROM people WHERE height>=180 ORDER BY +name; + SELECT name FROM people WHERE height<=161 ORDER BY +name; } {~/*INDEX people_idx1 */} # Now do an ANALYZE. A skip-scan can be used after ANALYZE. @@ -79,11 +81,11 @@ do_execsql_test skipscan2-1.4 { } db cache flush do_execsql_test skipscan2-1.5 { - SELECT name FROM people WHERE height>=180 ORDER BY +name; -} {David Jack Patrick Quiana Xavier} + SELECT name FROM people WHERE height<=161 ORDER BY +name; +} {Alice Bob Cindy Emily Megan Olivia Robert} do_execsql_test skipscan2-1.5eqp { EXPLAIN QUERY PLAN - SELECT name FROM people WHERE height>=180 ORDER BY +name; + SELECT name FROM people WHERE height<=161 ORDER BY +name; } {/*INDEX people_idx1 */} # Same answer with other formulations of the same query @@ -91,59 +93,33 @@ do_execsql_test skipscan2-1.5eqp { do_execsql_test skipscan2-1.6 { SELECT name FROM people WHERE role IN (SELECT DISTINCT role FROM people) - AND height>=180 ORDER BY +name; -} {David Jack Patrick Quiana Xavier} + AND height<=161 ORDER BY +name; +} {Alice Bob Cindy Emily Megan Olivia Robert} do_execsql_test skipscan2-1.7 { - SELECT name FROM people WHERE role='teacher' AND height>=180 + SELECT name FROM people WHERE role='teacher' AND height<=161 UNION ALL - SELECT name FROM people WHERE role='student' AND height>=180 + SELECT name FROM people WHERE role='student' AND height<=161 ORDER BY 1; -} {David Jack Patrick Quiana Xavier} +} {Alice Bob Cindy Emily Megan Olivia Robert} -# Add 8 more people, bringing the total to 34. Then the number of -# duplicates in the left-column of the index will be 17 and -# skip-scan should not be used after an (unfudged) ANALYZE. +# Add more people so that the estimated number of rows per key is +# equal to the skip-scan threshold of 18. Then run an (unfudged) +# ANALYZE. skip-scan should work. # do_execsql_test skipscan2-1.8 { - INSERT INTO people VALUES('Angie','student',166); - INSERT INTO people VALUES('Brad','student',176); - INSERT INTO people VALUES('Claire','student',168); - INSERT INTO people VALUES('Donald','student',162); - INSERT INTO people VALUES('Elaine','student',177); - INSERT INTO people VALUES('Frazier','student',159); - INSERT INTO people VALUES('Grace','student',179); - INSERT INTO people VALUES('Horace','student',166); + INSERT INTO people VALUES('Ursula','student',170); ANALYZE; SELECT stat FROM sqlite_stat1 WHERE idx='people_idx1'; -} {{34 17 2}} +} {{21 18 3}} db cache flush do_execsql_test skipscan2-1.9 { - SELECT name FROM people WHERE height>=180 ORDER BY +name; -} {David Jack Patrick Quiana Xavier} + SELECT name FROM people WHERE height<=161 ORDER BY +name; +} {Alice Bob Cindy Emily Megan Olivia Robert} do_execsql_test skipscan2-1.9eqp { EXPLAIN QUERY PLAN - SELECT name FROM people WHERE height>=180 ORDER BY +name; + SELECT name FROM people WHERE height<=161 ORDER BY +name; } {~/*INDEX people_idx1 */} -# Add 2 more people, bringing the total to 36. Then the number of -# duplicates in the left-column of the index will be 18 and -# skip-scan will be used after an (unfudged) ANALYZE. -# -do_execsql_test skipscan2-1.10 { - INSERT INTO people VALUES('Ingrad','student',155); - INSERT INTO people VALUES('Jacob','student',179); - ANALYZE; - SELECT stat FROM sqlite_stat1 WHERE idx='people_idx1'; -} {{36 18 2}} -db cache flush -do_execsql_test skipscan2-1.11 { - SELECT name FROM people WHERE height>=180 ORDER BY +name; -} {David Jack Patrick Quiana Xavier} -do_execsql_test skipscan2-1.11eqp { - EXPLAIN QUERY PLAN - SELECT name FROM people WHERE height>=180 ORDER BY +name; -} {/*INDEX people_idx1 */} - # Repeat using a WITHOUT ROWID table. # @@ -158,19 +134,19 @@ do_execsql_test skipscan2-2.1 { INSERT INTO peoplew(name,role,height) SELECT name, role, height FROM people; ALTER TABLE people RENAME TO old_people; - SELECT name FROM peoplew WHERE height>=180 ORDER BY +name; -} {David Jack Patrick Quiana Xavier} + SELECT name FROM peoplew WHERE height<=161 ORDER BY +name; +} {Alice Bob Cindy Emily Megan Olivia Robert} do_execsql_test skipscan2-2.2 { SELECT name FROM peoplew WHERE role IN (SELECT DISTINCT role FROM peoplew) - AND height>=180 ORDER BY +name; -} {David Jack Patrick Quiana Xavier} + AND height<=161 ORDER BY +name; +} {Alice Bob Cindy Emily Megan Olivia Robert} do_execsql_test skipscan2-2.2 { - SELECT name FROM peoplew WHERE role='teacher' AND height>=180 + SELECT name FROM peoplew WHERE role='teacher' AND height<=161 UNION ALL - SELECT name FROM peoplew WHERE role='student' AND height>=180 + SELECT name FROM peoplew WHERE role='student' AND height<=161 ORDER BY 1; -} {David Jack Patrick Quiana Xavier} +} {Alice Bob Cindy Emily Megan Olivia Robert} # Now do an ANALYZE. A skip-scan can be used after ANALYZE. # @@ -179,11 +155,11 @@ do_execsql_test skipscan2-2.4 { } db cache flush do_execsql_test skipscan2-2.5 { - SELECT name FROM peoplew WHERE height>=180 ORDER BY +name; -} {David Jack Patrick Quiana Xavier} + SELECT name FROM peoplew WHERE height<=161 ORDER BY +name; +} {Alice Bob Cindy Emily Megan Olivia Robert} do_execsql_test skipscan2-2.5eqp { EXPLAIN QUERY PLAN - SELECT name FROM peoplew WHERE height>=180 ORDER BY +name; + SELECT name FROM peoplew WHERE height<=161 ORDER BY +name; } {/*INDEX peoplew_idx1 */} # A skip-scan on a PK index of a WITHOUT ROWID table. -- 2.47.2