AryaWu/sqlite
0
1# 2012 Sept 272#3# The author disclaims copyright to this source code. In place of4# 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# This file implements regression tests for SQLite library. The12# focus of this file is testing that the optimizations that disable13# ORDER BY clauses when the natural order of a query is correct.14#15 16 17set testdir [file dirname $argv0]18source $testdir/tester.tcl19set ::testprefix orderby120 21# Generate test data for a join. Verify that the join gets the22# correct answer.23#24do_test 1.0 {25 db eval {26 BEGIN;27 CREATE TABLE album(28 aid INTEGER PRIMARY KEY,29 title TEXT UNIQUE NOT NULL30 );31 CREATE TABLE track(32 tid INTEGER PRIMARY KEY,33 aid INTEGER NOT NULL REFERENCES album,34 tn INTEGER NOT NULL,35 name TEXT,36 UNIQUE(aid, tn)37 );38 INSERT INTO album VALUES(1, '1-one'), (2, '2-two'), (3, '3-three');39 INSERT INTO track VALUES40 (NULL, 1, 1, 'one-a'),41 (NULL, 2, 2, 'two-b'),42 (NULL, 3, 3, 'three-c'),43 (NULL, 1, 3, 'one-c'),44 (NULL, 2, 1, 'two-a'),45 (NULL, 3, 1, 'three-a');46 ANALYZE;47 COMMIT;48 }49} {}50do_test 1.1a {51 db eval {52 SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn53 }54} {one-a one-c two-a two-b three-a three-c}55 56# Verify that the ORDER BY clause is optimized out57#58do_test 1.1b {59 db eval {60 EXPLAIN QUERY PLAN61 SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn62 }63} {~/ORDER BY/} ;# ORDER BY optimized out64 65# The same query with ORDER BY clause optimization disabled via + operators66# should give exactly the same answer.67#68do_test 1.2a {69 db eval {70 SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn71 }72} {one-a one-c two-a two-b three-a three-c}73 74# The output is sorted manually in this case.75#76do_test 1.2b {77 db eval {78 EXPLAIN QUERY PLAN79 SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn80 }81} {/ORDER BY/} ;# separate sorting pass due to "+" on ORDER BY terms82 83# The same query with ORDER BY optimizations turned off via built-in test.84#85do_test 1.3a {86 optimization_control db order-by-idx-join 087 db cache flush88 db eval {89 SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn90 }91} {one-a one-c two-a two-b three-a three-c}92do_test 1.3b {93 db eval {94 EXPLAIN QUERY PLAN95 SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn96 }97} {/ORDER BY/} ;# separate sorting pass due to disabled optimization98optimization_control db all 199db cache flush100 101# Reverse order sorts102#103do_test 1.4a {104 db eval {105 SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn106 }107} {three-a three-c two-a two-b one-a one-c}108do_test 1.4b {109 db eval {110 SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn111 }112} {three-a three-c two-a two-b one-a one-c} ;# verify same order after sorting113do_test 1.4c {114 db eval {115 EXPLAIN QUERY PLAN116 SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn117 }118} {~/ORDER BY/} ;# ORDER BY suppressed due to uniqueness constraints119 120do_test 1.5a {121 db eval {122 SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC123 }124} {one-c one-a two-b two-a three-c three-a}125do_test 1.5b {126 db eval {127 SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC128 }129} {one-c one-a two-b two-a three-c three-a} ;# verify same order after sorting130do_test 1.5c {131 db eval {132 EXPLAIN QUERY PLAN133 SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC134 }135} {~/ORDER BY/} ;# ORDER BY suppressed due to uniqueness constraints136 137do_test 1.6a {138 db eval {139 SELECT name FROM album CROSS JOIN track USING (aid)140 ORDER BY title DESC, tn DESC141 }142} {three-c three-a two-b two-a one-c one-a}143do_test 1.6b {144 db eval {145 SELECT name FROM album CROSS JOIN track USING (aid)146 ORDER BY +title DESC, +tn DESC147 }148} {three-c three-a two-b two-a one-c one-a} ;# verify same order after sorting149do_test 1.6c {150 db eval {151 EXPLAIN QUERY PLAN152 SELECT name FROM album CROSS JOIN track USING (aid)153 ORDER BY title DESC, tn DESC154 }155} {~/ORDER BY/} ;# ORDER BY 156 157 158# Reconstruct the test data to use indices rather than integer primary keys.159#160do_test 2.0 {161 db eval {162 BEGIN;163 DROP TABLE album;164 DROP TABLE track;165 CREATE TABLE album(166 aid INT PRIMARY KEY,167 title TEXT NOT NULL168 );169 CREATE INDEX album_i1 ON album(title, aid);170 CREATE TABLE track(171 aid INTEGER NOT NULL REFERENCES album,172 tn INTEGER NOT NULL,173 name TEXT,174 UNIQUE(aid, tn)175 );176 INSERT INTO album VALUES(1, '1-one'), (20, '2-two'), (3, '3-three');177 INSERT INTO track VALUES178 (1, 1, 'one-a'),179 (20, 2, 'two-b'),180 (3, 3, 'three-c'),181 (1, 3, 'one-c'),182 (20, 1, 'two-a'),183 (3, 1, 'three-a');184 ANALYZE;185 COMMIT;186 }187} {}188do_test 2.1a {189 db eval {190 SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn191 }192} {one-a one-c two-a two-b three-a three-c}193 194# Verify that the ORDER BY clause is optimized out195#196do_test 2.1b {197 db eval {198 EXPLAIN QUERY PLAN199 SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn200 }201} {/ORDER BY/} ;# ORDER BY required because of missing aid term in ORDER BY202 203do_test 2.1c {204 db eval {205 SELECT name FROM album JOIN track USING (aid) ORDER BY title, aid, tn206 }207} {one-a one-c two-a two-b three-a three-c}208do_test 2.1d {209 db eval {210 EXPLAIN QUERY PLAN211 SELECT name FROM album JOIN track USING (aid) ORDER BY title, aid, tn212 }213} {/ORDER BY/} ;# ORDER BY required in this case214 215# The same query with ORDER BY clause optimization disabled via + operators216# should give exactly the same answer.217#218do_test 2.2a {219 db eval {220 SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn221 }222} {one-a one-c two-a two-b three-a three-c}223 224# The output is sorted manually in this case.225#226do_test 2.2b {227 db eval {228 EXPLAIN QUERY PLAN229 SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn230 }231} {/ORDER BY/} ;# separate sorting pass due to "+" on ORDER BY terms232 233# The same query with ORDER BY optimizations turned off via built-in test.234#235do_test 2.3a {236 optimization_control db order-by-idx-join 0237 db cache flush238 db eval {239 SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn240 }241} {one-a one-c two-a two-b three-a three-c}242do_test 2.3b {243 db eval {244 EXPLAIN QUERY PLAN245 SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn246 }247} {/ORDER BY/} ;# separate sorting pass due to disabled optimization248optimization_control db all 1249db cache flush250 251# Reverse order sorts252#253do_test 2.4a {254 db eval {255 SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn256 }257} {three-a three-c two-a two-b one-a one-c}258do_test 2.4b {259 db eval {260 SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn261 }262} {three-a three-c two-a two-b one-a one-c} ;# verify same order after sorting263do_test 2.4c {264 db eval {265 EXPLAIN QUERY PLAN266 SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn267 }268} {/ORDER BY/} ;# separate sorting pass due to mixed DESC/ASC269 270 271do_test 2.5a {272 db eval {273 SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC274 }275} {one-c one-a two-b two-a three-c three-a}276do_test 2.5b {277 db eval {278 SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC279 }280} {one-c one-a two-b two-a three-c three-a} ;# verify same order after sorting281do_test 2.5c {282 db eval {283 EXPLAIN QUERY PLAN284 SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC285 }286} {/ORDER BY/} ;# separate sorting pass due to mixed ASC/DESC287 288do_test 2.6a {289 db eval {290 SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC291 }292} {three-c three-a two-b two-a one-c one-a}293do_test 2.6b {294 db eval {295 SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn DESC296 }297} {three-c three-a two-b two-a one-c one-a} ;# verify same order after sorting298do_test 2.6c {299 db eval {300 EXPLAIN QUERY PLAN301 SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC302 }303} {/ORDER BY/} ;# ORDER BY required304 305 306# Generate another test dataset, but this time using mixed ASC/DESC indices.307#308do_test 3.0 {309 db eval {310 BEGIN;311 DROP TABLE album;312 DROP TABLE track;313 CREATE TABLE album(314 aid INTEGER PRIMARY KEY,315 title TEXT UNIQUE NOT NULL316 );317 CREATE TABLE track(318 tid INTEGER PRIMARY KEY,319 aid INTEGER NOT NULL REFERENCES album,320 tn INTEGER NOT NULL,321 name TEXT,322 UNIQUE(aid ASC, tn DESC)323 );324 INSERT INTO album VALUES(1, '1-one'), (2, '2-two'), (3, '3-three');325 INSERT INTO track VALUES326 (NULL, 1, 1, 'one-a'),327 (NULL, 2, 2, 'two-b'),328 (NULL, 3, 3, 'three-c'),329 (NULL, 1, 3, 'one-c'),330 (NULL, 2, 1, 'two-a'),331 (NULL, 3, 1, 'three-a');332 ANALYZE;333 COMMIT;334 }335} {}336do_test 3.1a {337 db eval {338 SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn DESC339 }340} {one-c one-a two-b two-a three-c three-a}341 342# Verify that the ORDER BY clause is optimized out343#344do_test 3.1b {345 db eval {346 EXPLAIN QUERY PLAN347 SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn DESC348 }349} {~/ORDER BY/} ;# ORDER BY optimized out350 351# The same query with ORDER BY clause optimization disabled via + operators352# should give exactly the same answer.353#354do_test 3.2a {355 db eval {356 SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC357 }358} {one-c one-a two-b two-a three-c three-a}359 360# The output is sorted manually in this case.361#362do_test 3.2b {363 db eval {364 EXPLAIN QUERY PLAN365 SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC366 }367} {/ORDER BY/} ;# separate sorting pass due to "+" on ORDER BY terms368 369# The same query with ORDER BY optimizations turned off via built-in test.370#371do_test 3.3a {372 optimization_control db order-by-idx-join 0373 db cache flush374 db eval {375 SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC376 }377} {one-c one-a two-b two-a three-c three-a}378do_test 3.3b {379 db eval {380 EXPLAIN QUERY PLAN381 SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC382 }383} {/ORDER BY/} ;# separate sorting pass due to disabled optimization384optimization_control db all 1385db cache flush386 387# Without the mixed ASC/DESC on ORDER BY388#389do_test 3.4a {390 db eval {391 SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn392 }393} {one-a one-c two-a two-b three-a three-c}394do_test 3.4b {395 db eval {396 SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn397 }398} {one-a one-c two-a two-b three-a three-c} ;# verify same order after sorting399do_test 3.4c {400 db eval {401 EXPLAIN QUERY PLAN402 SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn403 }404} {~/ORDER BY/} ;# ORDER BY suppressed by uniqueness constraints405 406do_test 3.5a {407 db eval {408 SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC409 }410} {three-c three-a two-b two-a one-c one-a}411do_test 3.5b {412 db eval {413 SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn DESC414 }415} {three-c three-a two-b two-a one-c one-a} ;# verify same order after sorting416do_test 3.5c {417 db eval {418 EXPLAIN QUERY PLAN419 SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC420 }421} {~/ORDER BY/} ;# ORDER BY suppressed by uniqueness constraints422 423 424do_test 3.6a {425 db eval {426 SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn427 }428} {three-a three-c two-a two-b one-a one-c}429do_test 3.6b {430 db eval {431 SELECT name FROM album CROSS JOIN track USING (aid)432 ORDER BY +title DESC, +tn433 }434} {three-a three-c two-a two-b one-a one-c} ;# verify same order after sorting435do_test 3.6c {436 db eval {437 EXPLAIN QUERY PLAN438 SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn439 }440} {~/ORDER BY/} ;# inverted ASC/DESC is optimized out441 442# Ticket 5ed1772895bf3deeab78c5e3519b1da9165c541b (2013-06-04)443# Incorrect ORDER BY on an indexed JOIN444#445do_test 4.0 {446 db eval {447 CREATE TABLE t41(a INT UNIQUE NOT NULL, b INT NOT NULL);448 CREATE INDEX t41ba ON t41(b,a);449 CREATE TABLE t42(x INT NOT NULL REFERENCES t41(a), y INT NOT NULL);450 CREATE UNIQUE INDEX t42xy ON t42(x,y);451 INSERT INTO t41 VALUES(1,1),(3,1);452 INSERT INTO t42 VALUES(1,13),(1,15),(3,14),(3,16);453 454 SELECT b, y FROM t41 CROSS JOIN t42 ON x=a ORDER BY b, y;455 }456} {1 13 1 14 1 15 1 16}457 458# No sorting of queries that omit the FROM clause.459#460do_eqp_test 5.0 {461 SELECT 5 ORDER BY 1462} {463 QUERY PLAN464 `--SCAN CONSTANT ROW465}466do_execsql_test 5.1 {467 EXPLAIN QUERY PLAN SELECT 5 UNION ALL SELECT 3 ORDER BY 1468} {~/B-TREE/}469do_execsql_test 5.2 {470 SELECT 5 UNION ALL SELECT 3 ORDER BY 1471} {3 5}472do_execsql_test 5.3 {473 SELECT 986 AS x GROUP BY X ORDER BY X474} {986}475 476# The following test (originally derived from a single test within fuzz.test)477# verifies that a PseudoTable cursor is not closed prematurely in a deeply478# nested query. This test caused a segfault on 3.8.5 beta.479#480do_execsql_test 6.0 {481 CREATE TABLE abc(a, b, c);482 INSERT INTO abc VALUES(1, 2, 3);483 INSERT INTO abc VALUES(4, 5, 6);484 INSERT INTO abc VALUES(7, 8, 9);485 SELECT (486 SELECT 'hardware' FROM ( 487 SELECT 'software' ORDER BY 'firmware' ASC, 'sportswear' DESC 488 ) GROUP BY 1 HAVING length(b)489 )490 FROM abc;491} {hardware hardware hardware}492 493# Here is a test for a query-planner problem reported on the SQLite494# mailing list on 2014-09-18 by "Merike". Beginning with version 3.8.0,495# a separate sort was being used rather than using the single-column496# index. This was due to an oversight in the indexMightHelpWithOrderby()497# routine in where.c.498#499do_execsql_test 7.0 {500 CREATE TABLE t7(a,b);501 CREATE INDEX t7a ON t7(a);502 CREATE INDEX t7ab ON t7(a,b);503 EXPLAIN QUERY PLAN504 SELECT * FROM t7 WHERE a=?1 ORDER BY rowid;505} {~/ORDER BY/}506 507#-------------------------------------------------------------------------508# Test a partial sort large enough to cause the sorter to spill data509# to disk.510#511reset_db512do_execsql_test 8.0 {513 PRAGMA cache_size = 5;514 CREATE TABLE t1(a, b);515 CREATE INDEX i1 ON t1(a);516}517 518do_eqp_test 8.1 {519 SELECT * FROM t1 ORDER BY a, b;520} {521 QUERY PLAN522 |--SCAN t1 USING INDEX i1523 `--USE TEMP B-TREE FOR LAST TERM OF ORDER BY524}525 526do_execsql_test 8.2 {527 WITH cnt(i) AS (528 SELECT 1 UNION ALL SELECT i+1 FROM cnt WHERE i<10000529 )530 INSERT INTO t1 SELECT i%2, randomblob(500) FROM cnt;531}532 533do_test 8.3 {534 db eval { SELECT * FROM t1 ORDER BY a, b } { incr res $a }535 set res536} 5000537 538#---------------------------------------------------------------------------539# https://sqlite.org/src/tktview/cb3aa0641d9a413841c004293a4fc06cdc122029540#541# Adverse interaction between scalar subqueries and the partial-sorting542# logic.543#544do_execsql_test 9.0 {545 DROP TABLE IF EXISTS t1;546 CREATE TABLE t1(x INTEGER PRIMARY KEY);547 INSERT INTO t1 VALUES(1),(2);548 DROP TABLE IF EXISTS t2;549 CREATE TABLE t2(y);550 INSERT INTO t2 VALUES(9),(8),(3),(4);551 SELECT (SELECT x||y FROM t2, t1 ORDER BY x, y);552} {13}553 554# Problem found by OSSFuzz on 2018-05-05. This was caused by a new555# optimization that had not been previously released.556#557do_execsql_test 10.0 {558 CREATE TABLE t10(a,b);559 INSERT INTO t10 VALUES(1,2),(8,9),(3,4),(5,4),(0,7);560 CREATE INDEX t10b ON t10(b);561 SELECT b, rowid, '^' FROM t10 ORDER BY b, a LIMIT 4;562} {2 1 ^ 4 3 ^ 4 4 ^ 7 5 ^}563 564do_catchsql_test 11.0 {565 VALUES(2) EXCEPT SELECT '' ORDER BY abc566} {1 {1st ORDER BY term does not match any column in the result set}}567 568 569finish_test570