test/skipscan1.test

   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
  15 set testdir [file dirname $argv0]
  16 source $testdir/tester.tcl
  17
  18 do_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 #
  41 do_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 |}
  44 do_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=?)*/}
  48 do_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
  53 do_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 |}
  56 do_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=?)*/}
  60 do_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
  65 do_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 |}
  68 do_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=?)*/}
  72 do_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
  77 do_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 |}
  80 do_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=?)*/}
  84 do_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
  89 do_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 |}
  92 do_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<?)*/}
  96 do_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
 101 do_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 |}
 105 do_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<?)*/}
 110 do_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 #
 119 do_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 |}
 126 do_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
 131 do_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 {} {} {} {} |}
 134 do_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
 139 do_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
 152 do_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 |}
 155 do_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=?)*/}
 159 do_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
 165 do_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
 178 do_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 |}
 181 do_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=?)*/}
 185 do_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 #
 193 do_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 #
 218 do_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 .*/}
 233 do_execsql_test skipscan1-5.2 {
 234   ANALYZE;
 235   DELETE FROM sqlite_stat1;
 236   DROP TABLE IF EXISTS sqlite_stat4;
 237   INSERT INTO sqlite_stat1 VALUES('t5','t5i1','2702931 3 2 2 2 2');
 238   INSERT INTO sqlite_stat1 VALUES('t5','t5i2','2702931 686 2 2 2');
 239   ANALYZE sqlite_master;
 240 } {}
 241 db cache flush
 242 do_execsql_test skipscan1-5.3 {
 243   EXPLAIN QUERY PLAN
 244     SELECT xh, loc FROM t5 WHERE loc >= 'M' AND loc < 'N';
 245 } {/.*COVERING INDEX t5i1 .*/}
 246
 247 # The column used by the skip-scan needs to be sufficiently selective.
 248 # See the private email from Adi Zaimi to drh@sqlite.org on 2014-09-22.
 249 #
 250 db close
 251 forcedelete test.db
 252 sqlite3 db test.db
 253 do_execsql_test skipscan1-6.1 {
 254   CREATE TABLE t1(a,b,c,d,e,f,g,h varchar(300));
 255   CREATE INDEX t1ab ON t1(a,b);
 256   ANALYZE sqlite_master;
 257   -- Only two distinct values for the skip-scan column.  Skip-scan is not used.
 258   INSERT INTO sqlite_stat1 VALUES('t1','t1ab','500000 250000 125000');
 259   ANALYZE sqlite_master;
 260   EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE b=1;
 261 } {~/ANY/}
 262 do_execsql_test skipscan1-6.2 {
 263   -- Four distinct values for the skip-scan column.  Skip-scan is used.
 264   UPDATE sqlite_stat1 SET stat='500000 250000 62500';
 265   ANALYZE sqlite_master;
 266   EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE b=1;
 267 } {/ANY.a. AND b=/}
 268 do_execsql_test skipscan1-6.3 {
 269   -- Two distinct values for the skip-scan column again.  Skip-scan is not used.
 270   UPDATE sqlite_stat1 SET stat='500000 125000 62500';
 271   ANALYZE sqlite_master;
 272   EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE b=1;
 273 } {~/ANY/}
 274
 275 # If the sqlite_stat1 entry includes the "noskipscan" token, then never use
 276 # skipscan with that index.
 277 #
 278 do_execsql_test skipscan1-7.1 {
 279   UPDATE sqlite_stat1 SET stat='500000 125000 1 sz=100';
 280   ANALYZE sqlite_master;
 281   EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE b=1;
 282 } {/ANY/}
 283 do_execsql_test skipscan1-7.2 {
 284   UPDATE sqlite_stat1 SET stat='500000 125000 1 noskipscan sz=100';
 285   ANALYZE sqlite_master;
 286   EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE b=1;
 287 } {~/ANY/}
 288 do_execsql_test skipscan1-7.3 {
 289   UPDATE sqlite_stat1 SET stat='500000 125000 1 sz=100 noskipscan';
 290   ANALYZE sqlite_master;
 291   EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE b=1;
 292 } {~/ANY/}
 293
 294 # Ticket 8fd39115d8f46ece70e7d4b3c481d1bd86194746  2015-07-23
 295 # Incorrect code generated for a skipscan within an OR optimization
 296 # on a WITHOUT ROWID table.
 297 #
 298 do_execsql_test skipscan1-8.1 {
 299   DROP TABLE IF EXISTS t1;
 300   CREATE TABLE t1(x, y, PRIMARY KEY(x,y)) WITHOUT ROWID;
 301   INSERT INTO t1(x,y) VALUES(1,'AB');
 302   INSERT INTO t1(x,y) VALUES(2,'CD');
 303   ANALYZE;
 304   DROP TABLE IF EXISTS sqlite_stat4;
 305   DELETE FROM sqlite_stat1;
 306   INSERT INTO sqlite_stat1(tbl,idx,stat) VALUES('t1','t1','1000000 100 1');
 307   ANALYZE sqlite_master;
 308   SELECT * FROM t1
 309    WHERE (y = 'AB' AND x <= 4)
 310       OR (y = 'EF' AND x = 5);
 311 } {1 AB}
 312 do_execsql_test skipscan1-8.1eqp {
 313   EXPLAIN QUERY PLAN
 314   SELECT * FROM t1
 315    WHERE (y = 'AB' AND x <= 4)
 316       OR (y = 'EF' AND x = 5);
 317 } {/ANY/}
 318 do_execsql_test skipscan1-8.2 {
 319   SELECT * FROM t1
 320    WHERE y = 'AB' OR (y = 'CD' AND x = 2)
 321   ORDER BY +x;
 322 } {1 AB 2 CD}
 323
 324 # Segfault reported on the mailing list by Keith Medcalf on 2016-09-18.
 325 # A skip-scan with a "column IN (SELECT ...)" on the second term of the
 326 # index.
 327 #
 328 do_execsql_test skipscan1-9.2 {
 329   CREATE TABLE t9a(a,b,c);
 330   CREATE INDEX t9a_ab ON t9a(a,b);
 331   CREATE TABLE t9b(x,y);
 332   ANALYZE sqlite_master;
 333   INSERT INTO sqlite_stat1 VALUES('t9a','t9a_ab','1000000 250000 1');
 334   ANALYZE sqlite_master;
 335   EXPLAIN QUERY PLAN
 336   SELECT * FROM t9a WHERE b IN (SELECT x FROM t9b WHERE y!=5);
 337 } {/USING INDEX t9a_ab .ANY.a. AND b=./}
 338
 339
 340 optimization_control db skip-scan 0
 341 do_execsql_test skipscan1-9.3 {
 342   EXPLAIN QUERY PLAN
 343   SELECT  * FROM t9a WHERE b IN (SELECT x FROM t9b WHERE y!=5);
 344 } {/{SCAN t9a}/}
 345 optimization_control db skip-scan 1
 346
 347 do_execsql_test skipscan1-2.1 {
 348   CREATE TABLE t6(a TEXT, b INT, c INT, d INT);
 349   CREATE INDEX t6abc ON t6(a,b,c);
 350   INSERT INTO t6 VALUES('abc',123,4,5);
 351
 352   ANALYZE;
 353   DELETE FROM sqlite_stat1;
 354   INSERT INTO sqlite_stat1 VALUES('t6','t6abc','10000 5000 2000 10');
 355   ANALYZE sqlite_master;
 356   DELETE FROM t6;
 357 } {}
 358
 359 do_execsql_test skipscan1-2.2eqp {
 360   EXPLAIN QUERY PLAN
 361   SELECT a,b,c,d,'|' FROM t6 WHERE d<>99 AND b=345 ORDER BY a;
 362 } {/* USING INDEX t6abc (ANY(a) AND b=?)*/}
 363 do_execsql_test skipscan1-2.2 {
 364   SELECT a,b,c,d,'|' FROM t6 WHERE d<>99 AND b=345 ORDER BY a;
 365 } {}
 366
 367 do_execsql_test skipscan1-2.3eqp {
 368   EXPLAIN QUERY PLAN
 369   SELECT a,b,c,d,'|' FROM t6 WHERE d<>99 AND b=345 ORDER BY a DESC;
 370 } {/* USING INDEX t6abc (ANY(a) AND b=?)*/}
 371 do_execsql_test skipscan1-2.3 {
 372   SELECT a,b,c,d,'|' FROM t6 WHERE d<>99 AND b=345 ORDER BY a DESC;
 373 } {}
 374
 375 # 2019-07-29 Ticket ced41c7c7d6b4d36
 376 # A skipscan query is not order-distinct
 377 #
 378 db close
 379 sqlite3 db :memory:
 380 do_execsql_test skipscan1-3.1 {
 381   CREATE TABLE t1 (c1, c2, c3, c4, PRIMARY KEY(c4, c3));
 382   INSERT INTO t1 VALUES(3,0,1,NULL);
 383   INSERT INTO t1 VALUES(0,4,1,NULL);
 384   INSERT INTO t1 VALUES(5,6,1,NULL);
 385   INSERT INTO t1 VALUES(0,4,1,NULL);
 386   ANALYZE sqlite_master;
 387   INSERT INTO sqlite_stat1 VALUES('t1','sqlite_autoindex_t1_1','18 18 6');
 388   ANALYZE sqlite_master;
 389   SELECT DISTINCT quote(c1), quote(c2), quote(c3), quote(c4), '|'
 390     FROM t1 WHERE t1.c3 = 1;
 391 } {3 0 1 NULL | 0 4 1 NULL | 5 6 1 NULL |}
 392 do_eqp_test skipscan1-3.2 {
 393   SELECT DISTINCT quote(c1), quote(c2), quote(c3), quote(c4), '|'
 394     FROM t1 WHERE t1.c3 = 1;
 395 } {
 396   QUERY PLAN
 397   |--SEARCH t1 USING INDEX sqlite_autoindex_t1_1 (ANY(c4) AND c3=?)
 398   `--USE TEMP B-TREE FOR DISTINCT
 399 }
 400
 401 # 2020-01-06 ticket 304017f5f04a0035
 402 #
 403 reset_db
 404 do_execsql_test skipscan1-4.10 {
 405   CREATE TABLE t1(a,b INT);
 406   INSERT INTO t1(a,b) VALUES(1,2),(3,3),(4,5);
 407   CREATE UNIQUE INDEX i1 ON t1(b,b,a,a,a,a,a,b,a);
 408   ANALYZE;
 409   DROP TABLE IF EXISTS sqlite_stat4;
 410   INSERT INTO sqlite_stat1 VALUES('t1','i1','30 30 30 2 2 2 2 2 2 2');
 411   ANALYZE sqlite_master;
 412
 413   SELECT DISTINCT a
 414     FROM t1
 415    WHERE a = b
 416      AND a = 3
 417      AND b IN (1,3,2,4)
 418      AND b >= 0
 419      AND a <= 10;
 420 } {3}
 421
 422 # 2023-03-24 https://sqlite.org/forum/forumpost/8cc1dc0fe9
 423 #
 424 reset_db
 425 do_execsql_test skipscan1-5.0 {
 426   CREATE TABLE t1(a TEXT, UNIQUE(a,a,a));
 427   INSERT INTO t1 VALUES (hex(zeroblob(241))),(1),(2),(3);
 428   ANALYZE;
 429   SELECT max(a) FROM t1 WHERE a IN t1;
 430 } {3}
 431
 432 finish_test