1# 2013-11-13 2# 3# The author disclaims copyright to this source code. In place of 4# a legal notice, here is a blessing: 5# 6# May you do good and not evil. 7# May you find forgiveness for yourself and forgive others. 8# May you share freely, never taking more than you give. 9# 10#*********************************************************************** 11# 12# This file implements tests of the "skip-scan" query strategy. 13# 14 15set testdir [file dirname $argv0] 16source $testdir/tester.tcl 17 18do_execsql_test skipscan1-1.1 { 19 CREATE TABLE t1(a TEXT, b INT, c INT, d INT); 20 CREATE INDEX t1abc ON t1(a,b,c); 21 INSERT INTO t1 VALUES('abc',123,4,5); 22 INSERT INTO t1 VALUES('abc',234,5,6); 23 INSERT INTO t1 VALUES('abc',234,6,7); 24 INSERT INTO t1 VALUES('abc',345,7,8); 25 INSERT INTO t1 VALUES('def',567,8,9); 26 INSERT INTO t1 VALUES('def',345,9,10); 27 INSERT INTO t1 VALUES('bcd',100,6,11); 28 29 /* Fake the sqlite_stat1 table so that the query planner believes 30 ** the table contains thousands of rows and that the first few 31 ** columns are not selective. */ 32 ANALYZE; 33 DELETE FROM sqlite_stat1; 34 INSERT INTO sqlite_stat1 VALUES('t1','t1abc','10000 5000 2000 10'); 35 ANALYZE sqlite_master; 36} {} 37 38# Simple queries that leave the first one or two columns of the 39# index unconstrainted. 40# 41do_execsql_test skipscan1-1.2 { 42 SELECT a,b,c,d,'|' FROM t1 WHERE b=345 ORDER BY a; 43} {abc 345 7 8 | def 345 9 10 |} 44do_execsql_test skipscan1-1.2eqp { 45 EXPLAIN QUERY PLAN 46 SELECT a,b,c,d,'|' FROM t1 WHERE d<>99 AND b=345 ORDER BY a; 47} {/* USING INDEX t1abc (ANY(a) AND b=?)*/} 48do_execsql_test skipscan1-1.2sort { 49 EXPLAIN QUERY PLAN 50 SELECT a,b,c,d,'|' FROM t1 WHERE d<>99 AND b=345 ORDER BY a; 51} {~/*ORDER BY*/} 52 53do_execsql_test skipscan1-1.3 { 54 SELECT a,b,c,d,'|' FROM t1 WHERE d<>99 AND b=345 ORDER BY a DESC; 55} {def 345 9 10 | abc 345 7 8 |} 56do_execsql_test skipscan1-1.3eqp { 57 EXPLAIN QUERY PLAN 58 SELECT a,b,c,d,'|' FROM t1 WHERE d<>99 AND b=345 ORDER BY a DESC; 59} {/* USING INDEX t1abc (ANY(a) AND b=?)*/} 60do_execsql_test skipscan1-1.3sort { 61 EXPLAIN QUERY PLAN 62 SELECT a,b,c,d,'|' FROM t1 WHERE d<>99 AND b=345 ORDER BY a DESC; 63} {~/*ORDER BY*/} 64 65do_execsql_test skipscan1-1.4 { 66 SELECT a,b,c,d,'|' FROM t1 WHERE c=6 ORDER BY a, b, c; 67} {abc 234 6 7 | bcd 100 6 11 |} 68do_execsql_test skipscan1-1.4eqp { 69 EXPLAIN QUERY PLAN 70 SELECT a,b,c,d,'|' FROM t1 WHERE c=6 ORDER BY a, b, c; 71} {/* USING INDEX t1abc (ANY(a) AND ANY(b) AND c=?)*/} 72do_execsql_test skipscan1-1.4sort { 73 EXPLAIN QUERY PLAN 74 SELECT a,b,c,d,'|' FROM t1 WHERE c=6 ORDER BY a, b, c; 75} {~/*ORDER BY*/} 76 77do_execsql_test skipscan1-1.5 { 78 SELECT a,b,c,d,'|' FROM t1 WHERE c IN (6,7) ORDER BY a, b, c; 79} {abc 234 6 7 | abc 345 7 8 | bcd 100 6 11 |} 80do_execsql_test skipscan1-1.5eqp { 81 EXPLAIN QUERY PLAN 82 SELECT a,b,c,d,'|' FROM t1 WHERE c IN (6,7) ORDER BY a, b, c; 83} {/* USING INDEX t1abc (ANY(a) AND ANY(b) AND c=?)*/} 84do_execsql_test skipscan1-1.5sort { 85 EXPLAIN QUERY PLAN 86 SELECT a,b,c,d,'|' FROM t1 WHERE c IN (6,7) ORDER BY a, b, c; 87} {~/*ORDER BY*/} 88 89do_execsql_test skipscan1-1.6 { 90 SELECT a,b,c,d,'|' FROM t1 WHERE c BETWEEN 6 AND 7 ORDER BY a, b, c; 91} {abc 234 6 7 | abc 345 7 8 | bcd 100 6 11 |} 92do_execsql_test skipscan1-1.6eqp { 93 EXPLAIN QUERY PLAN 94 SELECT a,b,c,d,'|' FROM t1 WHERE c BETWEEN 6 AND 7 ORDER BY a, b, c; 95} {/* USING INDEX t1abc (ANY(a) AND ANY(b) AND c>? AND c<?)*/} 96do_execsql_test skipscan1-1.6sort { 97 EXPLAIN QUERY PLAN 98 SELECT a,b,c,d,'|' FROM t1 WHERE c BETWEEN 6 AND 7 ORDER BY a, b, c; 99} {~/*ORDER BY*/} 100 101do_execsql_test skipscan1-1.7 { 102 SELECT a,b,c,d,'|' FROM t1 WHERE b IN (234, 345) AND c BETWEEN 6 AND 7 103 ORDER BY a, b; 104} {abc 234 6 7 | abc 345 7 8 |} 105do_execsql_test skipscan1-1.7eqp { 106 EXPLAIN QUERY PLAN 107 SELECT a,b,c,d,'|' FROM t1 WHERE b IN (234, 345) AND c BETWEEN 6 AND 7 108 ORDER BY a, b; 109} {/* USING INDEX t1abc (ANY(a) AND b=? AND c>? AND c<?)*/} 110do_execsql_test skipscan1-1.7sort { 111 EXPLAIN QUERY PLAN 112 SELECT a,b,c,d,'|' FROM t1 WHERE b IN (234, 345) AND c BETWEEN 6 AND 7 113 ORDER BY a, b; 114} {~/*ORDER BY*/} 115 116 117# Joins 118# 119do_execsql_test skipscan1-1.51 { 120 CREATE TABLE t1j(x TEXT, y INTEGER); 121 INSERT INTO t1j VALUES('one',1),('six',6),('ninty-nine',99); 122 INSERT INTO sqlite_stat1 VALUES('t1j',null,'3'); 123 ANALYZE sqlite_master; 124 SELECT x, a, b, c, d, '|' FROM t1j, t1 WHERE c=y ORDER BY +a; 125} {six abc 234 6 7 | six bcd 100 6 11 |} 126do_execsql_test skipscan1-1.51eqp { 127 EXPLAIN QUERY PLAN 128 SELECT x, a, b, c, d, '|' FROM t1j, t1 WHERE c=y ORDER BY +a; 129} {/* INDEX t1abc (ANY(a) AND ANY(b) AND c=?)*/} 130 131do_execsql_test skipscan1-1.52 { 132 SELECT x, a, b, c, d, '|' FROM t1j LEFT JOIN t1 ON c=y ORDER BY +y, +a; 133} {one {} {} {} {} | six abc 234 6 7 | six bcd 100 6 11 | ninty-nine {} {} {} {} |} 134do_execsql_test skipscan1-1.52eqp { 135 EXPLAIN QUERY PLAN 136 SELECT x, a, b, c, d, '|' FROM t1j LEFT JOIN t1 ON c=y ORDER BY +y, +a; 137} {/* INDEX t1abc (ANY(a) AND ANY(b) AND c=?)*/} 138 139do_execsql_test skipscan1-2.1 { 140 CREATE TABLE t2(a TEXT, b INT, c INT, d INT, 141 PRIMARY KEY(a,b,c)); 142 INSERT INTO t2 SELECT * FROM t1; 143 144 /* Fake the sqlite_stat1 table so that the query planner believes 145 ** the table contains thousands of rows and that the first few 146 ** columns are not selective. */ 147 ANALYZE; 148 UPDATE sqlite_stat1 SET stat='10000 5000 2000 10' WHERE idx NOT NULL; 149 ANALYZE sqlite_master; 150} {} 151 152do_execsql_test skipscan1-2.2 { 153 SELECT a,b,c,d,'|' FROM t2 WHERE d<>99 AND b=345 ORDER BY a; 154} {abc 345 7 8 | def 345 9 10 |} 155do_execsql_test skipscan1-2.2eqp { 156 EXPLAIN QUERY PLAN 157 SELECT a,b,c,d,'|' FROM t2 WHERE d<>99 AND b=345 ORDER BY a; 158} {/* USING INDEX sqlite_autoindex_t2_1 (ANY(a) AND b=?)*/} 159do_execsql_test skipscan1-2.2sort { 160 EXPLAIN QUERY PLAN 161 SELECT a,b,c,d,'|' FROM t2 WHERE d<>99 AND b=345 ORDER BY a; 162} {~/*ORDER BY*/} 163 164 165do_execsql_test skipscan1-3.1 { 166 CREATE TABLE t3(a TEXT, b INT, c INT, d INT, 167 PRIMARY KEY(a,b,c)) WITHOUT ROWID; 168 INSERT INTO t3 SELECT * FROM t1; 169 170 /* Fake the sqlite_stat1 table so that the query planner believes 171 ** the table contains thousands of rows and that the first few 172 ** columns are not selective. */ 173 ANALYZE; 174 UPDATE sqlite_stat1 SET stat='10000 5000 2000 10' WHERE idx NOT NULL; 175 ANALYZE sqlite_master; 176} {} 177 178do_execsql_test skipscan1-3.2 { 179 SELECT a,b,c,d,'|' FROM t3 WHERE b=345 ORDER BY a; 180} {abc 345 7 8 | def 345 9 10 |} 181do_execsql_test skipscan1-3.2eqp { 182 EXPLAIN QUERY PLAN 183 SELECT a,b,c,d,'|' FROM t3 WHERE b=345 ORDER BY a; 184} {/* PRIMARY KEY (ANY(a) AND b=?)*/} 185do_execsql_test skipscan1-3.2sort { 186 EXPLAIN QUERY PLAN 187 SELECT a,b,c,d,'|' FROM t3 WHERE b=345 ORDER BY a; 188} {~/*ORDER BY*/} 189 190# Ticket 520070ec7fbaac: Array overrun in the skip-scan optimization 191# 2013-12-22 192# 193do_execsql_test skipscan1-4.1 { 194 CREATE TABLE t4(a,b,c,d,e,f,g,h,i); 195 CREATE INDEX t4all ON t4(a,b,c,d,e,f,g,h); 196 INSERT INTO t4 VALUES(1,2,3,4,5,6,7,8,9); 197 ANALYZE; 198 DELETE FROM sqlite_stat1; 199 INSERT INTO sqlite_stat1 200 VALUES('t4','t4all','655360 163840 40960 10240 2560 640 160 40 10'); 201 ANALYZE sqlite_master; 202 SELECT i FROM t4 WHERE a=1; 203 SELECT i FROM t4 WHERE b=2; 204 SELECT i FROM t4 WHERE c=3; 205 SELECT i FROM t4 WHERE d=4; 206 SELECT i FROM t4 WHERE e=5; 207 SELECT i FROM t4 WHERE f=6; 208 SELECT i FROM t4 WHERE g=7; 209 SELECT i FROM t4 WHERE h=8; 210} {9 9 9 9 9 9 9 9} 211 212# Make sure skip-scan cost computation in the query planner takes into 213# account the fact that the seek must occur multiple times. 214# 215# Prior to 2014-03-10, the costs were computed incorrectly which would 216# cause index t5i2 to be used instead of t5i1 on the skipscan1-5.3. 217# 218do_execsql_test skipscan1-5.1 { 219 CREATE TABLE t5( 220 id INTEGER PRIMARY KEY, 221 loc TEXT, 222 lang INTEGER, 223 utype INTEGER, 224 xa INTEGER, 225 xd INTEGER, 226 xh INTEGER 227 ); 228 CREATE INDEX t5i1 on t5(loc, xh, xa, utype, lang); 229 CREATE INDEX t5i2 ON t5(xd,loc,utype,lang); 230 EXPLAIN QUERY PLAN 231 SELECT xh, loc FROM t5 WHERE loc >= 'M' AND loc < 'N'; 232} {/.*COVERING INDEX t5i1 .*/} 233do_execsql_test skipscan1-5.2 { 234 ANALYZE; 235 DELETE FROM sqlite_stat1; 236 DROP TABLE IF EXISTS sqlite_stat4; 237 DROP TABLE IF EXISTS sqlite_stat3; 238 INSERT INTO sqlite_stat1 VALUES('t5','t5i1','2702931 3 2 2 2 2'); 239 INSERT INTO sqlite_stat1 VALUES('t5','t5i2','2702931 686 2 2 2'); 240 ANALYZE sqlite_master; 241} {} 242db cache flush 243do_execsql_test skipscan1-5.3 { 244 EXPLAIN QUERY PLAN 245 SELECT xh, loc FROM t5 WHERE loc >= 'M' AND loc < 'N'; 246} {/.*COVERING INDEX t5i1 .*/} 247 248# The column used by the skip-scan needs to be sufficiently selective. 249# See the private email from Adi Zaimi to [email protected] on 2014-09-22. 250# 251db close 252forcedelete test.db 253sqlite3 db test.db 254do_execsql_test skipscan1-6.1 { 255 CREATE TABLE t1(a,b,c,d,e,f,g,h varchar(300)); 256 CREATE INDEX t1ab ON t1(a,b); 257 ANALYZE sqlite_master; 258 -- Only two distinct values for the skip-scan column. Skip-scan is not used. 259 INSERT INTO sqlite_stat1 VALUES('t1','t1ab','500000 250000 125000'); 260 ANALYZE sqlite_master; 261 EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE b=1; 262} {~/ANY/} 263do_execsql_test skipscan1-6.2 { 264 -- Four distinct values for the skip-scan column. Skip-scan is used. 265 UPDATE sqlite_stat1 SET stat='500000 250000 62500'; 266 ANALYZE sqlite_master; 267 EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE b=1; 268} {/ANY.a. AND b=/} 269do_execsql_test skipscan1-6.3 { 270 -- Two distinct values for the skip-scan column again. Skip-scan is not used. 271 UPDATE sqlite_stat1 SET stat='500000 125000 62500'; 272 ANALYZE sqlite_master; 273 EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE b=1; 274} {~/ANY/} 275 276# If the sqlite_stat1 entry includes the "noskipscan" token, then never use 277# skipscan with that index. 278# 279do_execsql_test skipscan1-7.1 { 280 UPDATE sqlite_stat1 SET stat='500000 125000 1 sz=100'; 281 ANALYZE sqlite_master; 282 EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE b=1; 283} {/ANY/} 284do_execsql_test skipscan1-7.2 { 285 UPDATE sqlite_stat1 SET stat='500000 125000 1 noskipscan sz=100'; 286 ANALYZE sqlite_master; 287 EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE b=1; 288} {~/ANY/} 289do_execsql_test skipscan1-7.3 { 290 UPDATE sqlite_stat1 SET stat='500000 125000 1 sz=100 noskipscan'; 291 ANALYZE sqlite_master; 292 EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE b=1; 293} {~/ANY/} 294 295# Ticket 8fd39115d8f46ece70e7d4b3c481d1bd86194746 2015-07-23 296# Incorrect code generated for a skipscan within an OR optimization 297# on a WITHOUT ROWID table. 298# 299do_execsql_test skipscan1-8.1 { 300 DROP TABLE IF EXISTS t1; 301 CREATE TABLE t1(x, y, PRIMARY KEY(x,y)) WITHOUT ROWID; 302 INSERT INTO t1(x,y) VALUES(1,'AB'); 303 INSERT INTO t1(x,y) VALUES(2,'CD'); 304 ANALYZE; 305 DROP TABLE IF EXISTS sqlite_stat4; 306 DELETE FROM sqlite_stat1; 307 INSERT INTO sqlite_stat1(tbl,idx,stat) VALUES('t1','t1','1000000 100 1'); 308 ANALYZE sqlite_master; 309 SELECT * FROM t1 310 WHERE (y = 'AB' AND x <= 4) 311 OR (y = 'EF' AND x = 5); 312} {1 AB} 313do_execsql_test skipscan1-8.1eqp { 314 EXPLAIN QUERY PLAN 315 SELECT * FROM t1 316 WHERE (y = 'AB' AND x <= 4) 317 OR (y = 'EF' AND x = 5); 318} {/ANY/} 319do_execsql_test skipscan1-8.2 { 320 SELECT * FROM t1 321 WHERE y = 'AB' OR (y = 'CD' AND x = 2) 322 ORDER BY +x; 323} {1 AB 2 CD} 324 325# Segfault reported on the mailing list by Keith Medcalf on 2016-09-18. 326# A skip-scan with a "column IN (SELECT ...)" on the second term of the 327# index. 328# 329do_execsql_test skipscan1-9.2 { 330 CREATE TABLE t9a(a,b,c); 331 CREATE INDEX t9a_ab ON t9a(a,b); 332 CREATE TABLE t9b(x,y); 333 ANALYZE sqlite_master; 334 INSERT INTO sqlite_stat1 VALUES('t9a','t9a_ab','1000000 250000 1'); 335 ANALYZE sqlite_master; 336 EXPLAIN QUERY PLAN 337 SELECT * FROM t9a WHERE b IN (SELECT x FROM t9b WHERE y!=5); 338} {/USING INDEX t9a_ab .ANY.a. AND b=./} 339 340finish_test 341