| 1 |
# 2012 November 9 |
| 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 |
# Test cases for query planning decisions. |
| 13 |
|
| 14 |
|
| 15 |
# |
| 16 |
# The tests in this file demonstrate the behaviour of the query planner |
| 17 |
# in determining the order in which joined tables are scanned. |
| 18 |
# |
| 19 |
# Assume there are two tables being joined - t1 and t2. Each has a cost |
| 20 |
# if it is the outer loop, and a cost if it is the inner loop. As follows: |
| 21 |
# |
| 22 |
# t1(outer) - cost of scanning t1 as the outer loop. |
| 23 |
# t1(inner) - cost of scanning t1 as the inner loop. |
| 24 |
# t2(outer) - cost of scanning t2 as the outer loop. |
| 25 |
# t2(inner) - cost of scanning t2 as the inner loop. |
| 26 |
# |
| 27 |
# Depending on the order in which the planner nests the scans, the total |
| 28 |
# cost of the join query is one of: |
| 29 |
# |
| 30 |
# t1(outer) * t2(inner) |
| 31 |
# t2(outer) * t1(inner) |
| 32 |
# |
| 33 |
# The tests in this file attempt to verify that the planner nests joins in |
| 34 |
# the correct order when the following are true: |
| 35 |
# |
| 36 |
# + (t1(outer) * t2(inner)) > (t1(inner) * t2(outer) |
| 37 |
# + t1(outer) < t2(outer) |
| 38 |
# |
| 39 |
# In other words, when the best overall query plan has t2 as the outer loop, |
| 40 |
# but when the outer loop is considered independent of the inner, t1 is the |
| 41 |
# most efficient choice. |
| 42 |
# |
| 43 |
# In order to make them more predictable, automatic indexes are turned off for |
| 44 |
# the tests in this file. |
| 45 |
# |
| 46 |
|
| 47 |
set testdir [file dirname $argv0] |
| 48 |
source $testdir/tester.tcl |
| 49 |
set testprefix whereF |
| 50 |
|
| 51 |
do_execsql_test 1.0 { |
| 52 |
PRAGMA automatic_index = 0; |
| 53 |
CREATE TABLE t1(a, b, c); |
| 54 |
CREATE TABLE t2(d, e, f); |
| 55 |
CREATE UNIQUE INDEX i1 ON t1(a); |
| 56 |
CREATE UNIQUE INDEX i2 ON t2(d); |
| 57 |
} {} |
| 58 |
|
| 59 |
foreach {tn sql} { |
| 60 |
1 "SELECT * FROM t1, t2 WHERE t1.a=t2.e AND t2.d<t1.b AND t1.c!=10" |
| 61 |
2 "SELECT * FROM t2, t1 WHERE t1.a=t2.e AND t2.d<t1.b AND t1.c!=10" |
| 62 |
3 "SELECT * FROM t2 CROSS JOIN t1 WHERE t1.a=t2.e AND t2.d<t1.b AND t1.c!=10" |
| 63 |
} { |
| 64 |
do_test 1.$tn { |
| 65 |
db eval "EXPLAIN QUERY PLAN $sql" |
| 66 |
} {/.*SCAN t2\y.*SEARCH t1\y.*/} |
| 67 |
} |
| 68 |
|
| 69 |
do_execsql_test 2.0 { |
| 70 |
DROP TABLE t1; |
| 71 |
DROP TABLE t2; |
| 72 |
CREATE TABLE t1(a, b, c); |
| 73 |
CREATE TABLE t2(d, e, f); |
| 74 |
|
| 75 |
CREATE UNIQUE INDEX i1 ON t1(a); |
| 76 |
CREATE UNIQUE INDEX i2 ON t1(b); |
| 77 |
CREATE UNIQUE INDEX i3 ON t2(d); |
| 78 |
} {} |
| 79 |
|
| 80 |
foreach {tn sql} { |
| 81 |
1 "SELECT * FROM t1, t2 WHERE t1.a>? AND t2.d>t1.c AND t1.b=t2.e" |
| 82 |
2 "SELECT * FROM t2, t1 WHERE t1.a>? AND t2.d>t1.c AND t1.b=t2.e" |
| 83 |
3 "SELECT * FROM t2 CROSS JOIN t1 WHERE t1.a>? AND t2.d>t1.c AND t1.b=t2.e" |
| 84 |
} { |
| 85 |
do_test 2.$tn { |
| 86 |
db eval "EXPLAIN QUERY PLAN $sql" |
| 87 |
} {/.*SCAN t2\y.*SEARCH t1\y.*/} |
| 88 |
} |
| 89 |
|
| 90 |
do_execsql_test 3.0 { |
| 91 |
DROP TABLE t1; |
| 92 |
DROP TABLE t2; |
| 93 |
CREATE TABLE t1(a, b, c); |
| 94 |
CREATE TABLE t2(d, e, f); |
| 95 |
|
| 96 |
CREATE UNIQUE INDEX i1 ON t1(a, b); |
| 97 |
CREATE INDEX i2 ON t2(d); |
| 98 |
} {} |
| 99 |
|
| 100 |
foreach {tn sql} { |
| 101 |
1 {SELECT t1.a, t1.b, t2.d, t2.e FROM t1, t2 |
| 102 |
WHERE t2.d=t1.b AND t1.a=(t2.d+1) AND t1.b = (t2.e+1)} |
| 103 |
|
| 104 |
2 {SELECT t1.a, t1.b, t2.d, t2.e FROM t2, t1 |
| 105 |
WHERE t2.d=t1.b AND t1.a=(t2.d+1) AND t1.b = (t2.e+1)} |
| 106 |
|
| 107 |
3 {SELECT t1.a, t1.b, t2.d, t2.e FROM t2 CROSS JOIN t1 |
| 108 |
WHERE t2.d=t1.b AND t1.a=(t2.d+1) AND t1.b = (t2.e+1)} |
| 109 |
} { |
| 110 |
do_test 3.$tn { |
| 111 |
db eval "EXPLAIN QUERY PLAN $sql" |
| 112 |
} {/.*SCAN t2\y.*SEARCH t1\y.*/} |
| 113 |
} |
| 114 |
|
| 115 |
do_execsql_test 4.0 { |
| 116 |
CREATE TABLE t4(a,b,c,d,e, PRIMARY KEY(a,b,c)); |
| 117 |
CREATE INDEX t4adc ON t4(a,d,c); |
| 118 |
CREATE UNIQUE INDEX t4aebc ON t4(a,e,b,c); |
| 119 |
EXPLAIN QUERY PLAN SELECT rowid FROM t4 WHERE a=? AND b=?; |
| 120 |
} {/a=. AND b=./} |
| 121 |
|
| 122 |
#------------------------------------------------------------------------- |
| 123 |
# Test the following case: |
| 124 |
# |
| 125 |
# ... FROM t1, t2 WHERE ( |
| 126 |
# t2.rowid = +t1.rowid OR (t2.f2 = t1.f1 AND t1.f1!=-1) |
| 127 |
# ) |
| 128 |
# |
| 129 |
# where there is an index on t2(f2). The planner should use "t1" as the |
| 130 |
# outer loop. The inner loop, on "t2", is an OR optimization. One pass |
| 131 |
# for: |
| 132 |
# |
| 133 |
# t2.rowid = $1 |
| 134 |
# |
| 135 |
# and another for: |
| 136 |
# |
| 137 |
# t2.f2=$1 AND $1!=-1 |
| 138 |
# |
| 139 |
# the test is to ensure that on the second pass, the ($1!=-1) condition |
| 140 |
# is tested before any seek operations are performed - i.e. outside of |
| 141 |
# the loop through the f2=$1 range of the t2(f2) index. |
| 142 |
# |
| 143 |
reset_db |
| 144 |
do_execsql_test 5.0 { |
| 145 |
CREATE TABLE t1(f1); |
| 146 |
CREATE TABLE t2(f2); |
| 147 |
CREATE INDEX t2f ON t2(f2); |
| 148 |
|
| 149 |
INSERT INTO t1 VALUES(-1); |
| 150 |
INSERT INTO t1 VALUES(-1); |
| 151 |
INSERT INTO t1 VALUES(-1); |
| 152 |
INSERT INTO t1 VALUES(-1); |
| 153 |
|
| 154 |
WITH w(i) AS ( |
| 155 |
SELECT 1 UNION ALL SELECT i+1 FROM w WHERE i<1000 |
| 156 |
) |
| 157 |
INSERT INTO t2 SELECT -1 FROM w; |
| 158 |
} |
| 159 |
|
| 160 |
do_execsql_test 5.1 { |
| 161 |
SELECT count(*) FROM t1, t2 WHERE t2.rowid = +t1.rowid |
| 162 |
} {4} |
| 163 |
do_test 5.2 { expr [db status vmstep]<200 } 1 |
| 164 |
|
| 165 |
do_execsql_test 5.3 { |
| 166 |
SELECT count(*) FROM t1, t2 WHERE ( |
| 167 |
t2.rowid = +t1.rowid OR t2.f2 = t1.f1 |
| 168 |
) |
| 169 |
} {4000} |
| 170 |
do_test 5.4 { expr [db status vmstep]>1000 } 1 |
| 171 |
|
| 172 |
do_execsql_test 5.5 { |
| 173 |
SELECT count(*) FROM t1, t2 WHERE ( |
| 174 |
t2.rowid = +t1.rowid OR (t2.f2 = t1.f1 AND t1.f1!=-1) |
| 175 |
) |
| 176 |
} {4} |
| 177 |
do_test 5.6 { expr [db status vmstep]<200 } 1 |
| 178 |
|
| 179 |
# 2017-09-04 ticket b899b6042f97f52d |
| 180 |
# Segfault on correlated subquery... |
| 181 |
# |
| 182 |
ifcapable json1&&vtab { |
| 183 |
do_execsql_test 6.1 { |
| 184 |
CREATE TABLE t6(x); |
| 185 |
SELECT * FROM t6 WHERE 1 IN (SELECT value FROM json_each(x)); |
| 186 |
} {} |
| 187 |
|
| 188 |
do_execsql_test 6.2 { |
| 189 |
DROP TABLE t6; |
| 190 |
CREATE TABLE t6(a,b,c); |
| 191 |
INSERT INTO t6 VALUES |
| 192 |
(0,null,'{"a":0,"b":[3,4,5],"c":{"x":4.5,"y":7.8}}'), |
| 193 |
(1,null,'{"a":1,"b":[3,4,5],"c":{"x":4.5,"y":7.8}}'), |
| 194 |
(2,null,'{"a":9,"b":[3,4,5],"c":{"x":4.5,"y":7.8}}'); |
| 195 |
SELECT * FROM t6 |
| 196 |
WHERE (EXISTS (SELECT 1 FROM json_each(t6.c) AS x WHERE x.value=1)); |
| 197 |
} {1 {} {{"a":1,"b":[3,4,5],"c":{"x":4.5,"y":7.8}}}} |
| 198 |
|
| 199 |
# Another test case derived from a posting by Wout Mertens on the |
| 200 |
# sqlite-users mailing list on 2017-10-04. |
| 201 |
do_execsql_test 6.3 { |
| 202 |
DROP TABLE IF EXISTS t; |
| 203 |
CREATE TABLE t(json JSON); |
| 204 |
SELECT * FROM t |
| 205 |
WHERE(EXISTS(SELECT 1 FROM json_each(t.json,"$.foo") j |
| 206 |
WHERE j.value = 'meep')); |
| 207 |
} {} |
| 208 |
do_execsql_test 6.4 { |
| 209 |
INSERT INTO t VALUES('{"xyzzy":null}'); |
| 210 |
INSERT INTO t VALUES('{"foo":"meep","other":12345}'); |
| 211 |
INSERT INTO t VALUES('{"foo":"bingo","alt":5.25}'); |
| 212 |
SELECT * FROM t |
| 213 |
WHERE(EXISTS(SELECT 1 FROM json_each(t.json,"$.foo") j |
| 214 |
WHERE j.value = 'meep')); |
| 215 |
} {{{"foo":"meep","other":12345}}} |
| 216 |
} |
| 217 |
|
| 218 |
# 2018-01-27 |
| 219 |
# Ticket https://sqlite.org/src/tktview/ec32177c99ccac2b180fd3ea2083 |
| 220 |
# Incorrect result when using the new OR clause factoring optimization |
| 221 |
# |
| 222 |
# This is the original test case as reported on the sqlite-users mailing |
| 223 |
# list |
| 224 |
# |
| 225 |
do_execsql_test 7.1 { |
| 226 |
DROP TABLE IF EXISTS cd; |
| 227 |
CREATE TABLE cd ( cdid INTEGER PRIMARY KEY NOT NULL, genreid integer ); |
| 228 |
CREATE INDEX cd_idx_genreid ON cd (genreid); |
| 229 |
INSERT INTO cd ( cdid, genreid ) VALUES |
| 230 |
( 1, 1 ), |
| 231 |
( 2, NULL ), |
| 232 |
( 3, NULL ), |
| 233 |
( 4, NULL ), |
| 234 |
( 5, NULL ); |
| 235 |
|
| 236 |
SELECT cdid |
| 237 |
FROM cd me |
| 238 |
WHERE 2 > ( |
| 239 |
SELECT COUNT( * ) |
| 240 |
FROM cd rownum__emulation |
| 241 |
WHERE |
| 242 |
( |
| 243 |
me.genreid IS NOT NULL |
| 244 |
AND |
| 245 |
rownum__emulation.genreid IS NULL |
| 246 |
) |
| 247 |
OR |
| 248 |
( |
| 249 |
me.genreid IS NOT NULL |
| 250 |
AND |
| 251 |
rownum__emulation.genreid IS NOT NULL |
| 252 |
AND |
| 253 |
rownum__emulation.genreid < me.genreid |
| 254 |
) |
| 255 |
OR |
| 256 |
( |
| 257 |
( me.genreid = rownum__emulation.genreid OR ( me.genreid IS NULL |
| 258 |
AND rownum__emulation.genreid IS NULL ) ) |
| 259 |
AND |
| 260 |
rownum__emulation.cdid > me.cdid |
| 261 |
) |
| 262 |
); |
| 263 |
} {4 5} |
| 264 |
|
| 265 |
# Simplified test cases from the ticket |
| 266 |
# |
| 267 |
do_execsql_test 7.2 { |
| 268 |
DROP TABLE IF EXISTS t1; |
| 269 |
DROP TABLE IF EXISTS t2; |
| 270 |
CREATE TABLE t1(a INTEGER PRIMARY KEY, b); |
| 271 |
INSERT INTO t1(a,b) VALUES(1,1); |
| 272 |
CREATE TABLE t2(aa INTEGER PRIMARY KEY, bb); |
| 273 |
INSERT INTO t2(aa,bb) VALUES(1,1),(2,NULL),(3,NULL); |
| 274 |
SELECT ( |
| 275 |
SELECT COUNT(*) FROM t2 |
| 276 |
WHERE ( t1.b IS NOT NULL AND t2.bb IS NULL ) |
| 277 |
OR ( t2.bb < t1.b ) |
| 278 |
OR ( t1.b IS t2.bb AND t2.aa > t1.a ) |
| 279 |
) |
| 280 |
FROM t1; |
| 281 |
} {2} |
| 282 |
|
| 283 |
# The fix for ticket ec32177c99ccac2b180fd3ea2083 only makes a difference |
| 284 |
# in the output when there is a TERM_VNULL entry in the WhereClause array. |
| 285 |
# And TERM_VNULL entries are only generated when compiling with |
| 286 |
# SQLITE_ENABLE_STAT4. Nevertheless, it is correct that TERM_VIRTUAL terms |
| 287 |
# should not participate in the factoring optimization. In all cases other |
| 288 |
# than TERM_VNULL, participation is harmless, but it does consume a few |
| 289 |
# extra CPU cycles. |
| 290 |
# |
| 291 |
# The following test verifies that the TERM_VIRTUAL terms resulting from |
| 292 |
# a GLOB operator do not appear anywhere in the generated code. This |
| 293 |
# confirms that the problem is fixed, even on builds that omit STAT4. |
| 294 |
# |
| 295 |
do_execsql_test 7.3 { |
| 296 |
DROP TABLE IF EXISTS t1; |
| 297 |
DROP TABLE IF EXISTS t2; |
| 298 |
CREATE TABLE t1(a INTEGER PRIMARY KEY, b TEXT); |
| 299 |
INSERT INTO t1(a,b) VALUES(1,'abcxyz'); |
| 300 |
CREATE TABLE t2(aa INTEGER PRIMARY KEY, bb TEXT); |
| 301 |
INSERT INTO t2(aa,bb) VALUES(1,'abc'),(2,'wxyz'),(3,'xyz'); |
| 302 |
CREATE INDEX t2bb ON t2(bb); |
| 303 |
EXPLAIN SELECT ( |
| 304 |
SELECT COUNT(*) FROM t2 |
| 305 |
WHERE ( t1.b GLOB 'a*z' AND t2.bb='xyz' ) |
| 306 |
OR ( t2.bb = t1.b ) |
| 307 |
OR ( t2.aa = t1.a ) |
| 308 |
) |
| 309 |
FROM t1; |
| 310 |
} {~/ (Lt|Ge) /} |
| 311 |
|
| 312 |
finish_test |