test/orderby1.test

   1 # 2012 Sept 27
   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 # This file implements regression tests for SQLite library.  The
  12 # focus of this file is testing that the optimizations that disable
  13 # ORDER BY clauses when the natural order of a query is correct.
  14 #
  15
  16
  17 set testdir [file dirname $argv0]
  18 source $testdir/tester.tcl
  19 set ::testprefix orderby1
  20
  21 # Generate test data for a join.  Verify that the join gets the
  22 # correct answer.
  23 #
  24 do_test 1.0 {
  25   db eval {
  26     BEGIN;
  27     CREATE TABLE album(
  28       aid INTEGER PRIMARY KEY,
  29       title TEXT UNIQUE NOT NULL
  30     );
  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 VALUES
  40         (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 } {}
  50 do_test 1.1a {
  51   db eval {
  52     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  53   }
  54 } {one-a one-c two-a two-b three-a three-c}
  55
  56 # Verify that the ORDER BY clause is optimized out
  57 #
  58 do_test 1.1b {
  59   db eval {
  60     EXPLAIN QUERY PLAN
  61     SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn
  62   }
  63 } {~/ORDER BY/}  ;# ORDER BY optimized out
  64
  65 # The same query with ORDER BY clause optimization disabled via + operators
  66 # should give exactly the same answer.
  67 #
  68 do_test 1.2a {
  69   db eval {
  70     SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn
  71   }
  72 } {one-a one-c two-a two-b three-a three-c}
  73
  74 # The output is sorted manually in this case.
  75 #
  76 do_test 1.2b {
  77   db eval {
  78     EXPLAIN QUERY PLAN
  79     SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn
  80   }
  81 } {/ORDER BY/}   ;# separate sorting pass due to "+" on ORDER BY terms
  82
  83 # The same query with ORDER BY optimizations turned off via built-in test.
  84 #
  85 do_test 1.3a {
  86   optimization_control db order-by-idx-join 0
  87   db cache flush
  88   db eval {
  89     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  90   }
  91 } {one-a one-c two-a two-b three-a three-c}
  92 do_test 1.3b {
  93   db eval {
  94     EXPLAIN QUERY PLAN
  95     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  96   }
  97 } {/ORDER BY/}   ;# separate sorting pass due to disabled optimization
  98 optimization_control db all 1
  99 db cache flush
 100
 101 # Reverse order sorts
 102 #
 103 do_test 1.4a {
 104   db eval {
 105     SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
 106   }
 107 } {three-a three-c two-a two-b one-a one-c}
 108 do_test 1.4b {
 109   db eval {
 110     SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn
 111   }
 112 } {three-a three-c two-a two-b one-a one-c}  ;# verify same order after sorting
 113 do_test 1.4c {
 114   db eval {
 115     EXPLAIN QUERY PLAN
 116     SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
 117   }
 118 } {~/ORDER BY/}  ;# ORDER BY suppressed due to uniqueness constraints
 119
 120 do_test 1.5a {
 121   db eval {
 122     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
 123   }
 124 } {one-c one-a two-b two-a three-c three-a}
 125 do_test 1.5b {
 126   db eval {
 127     SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC
 128   }
 129 } {one-c one-a two-b two-a three-c three-a}  ;# verify same order after sorting
 130 do_test 1.5c {
 131   db eval {
 132     EXPLAIN QUERY PLAN
 133     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
 134   }
 135 } {~/ORDER BY/}  ;# ORDER BY suppressed due to uniqueness constraints
 136
 137 do_test 1.6a {
 138   db eval {
 139     SELECT name FROM album CROSS JOIN track USING (aid)
 140      ORDER BY title DESC, tn DESC
 141   }
 142 } {three-c three-a two-b two-a one-c one-a}
 143 do_test 1.6b {
 144   db eval {
 145     SELECT name FROM album CROSS JOIN track USING (aid)
 146      ORDER BY +title DESC, +tn DESC
 147   }
 148 } {three-c three-a two-b two-a one-c one-a}  ;# verify same order after sorting
 149 do_test 1.6c {
 150   db eval {
 151     EXPLAIN QUERY PLAN
 152     SELECT name FROM album CROSS JOIN track USING (aid)
 153      ORDER BY title DESC, tn DESC
 154   }
 155 } {~/ORDER BY/}  ;# ORDER BY
 156
 157
 158 # Reconstruct the test data to use indices rather than integer primary keys.
 159 #
 160 do_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 NULL
 168     );
 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 VALUES
 178         (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 } {}
 188 do_test 2.1a {
 189   db eval {
 190     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
 191   }
 192 } {one-a one-c two-a two-b three-a three-c}
 193
 194 # Verify that the ORDER BY clause is optimized out
 195 #
 196 do_test 2.1b {
 197   db eval {
 198     EXPLAIN QUERY PLAN
 199     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
 200   }
 201 } {/ORDER BY/}  ;# ORDER BY required because of missing aid term in ORDER BY
 202
 203 do_test 2.1c {
 204   db eval {
 205     SELECT name FROM album JOIN track USING (aid) ORDER BY title, aid, tn
 206   }
 207 } {one-a one-c two-a two-b three-a three-c}
 208 do_test 2.1d {
 209   db eval {
 210     EXPLAIN QUERY PLAN
 211     SELECT name FROM album JOIN track USING (aid) ORDER BY title, aid, tn
 212   }
 213 } {/ORDER BY/}  ;# ORDER BY required in this case
 214
 215 # The same query with ORDER BY clause optimization disabled via + operators
 216 # should give exactly the same answer.
 217 #
 218 do_test 2.2a {
 219   db eval {
 220     SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn
 221   }
 222 } {one-a one-c two-a two-b three-a three-c}
 223
 224 # The output is sorted manually in this case.
 225 #
 226 do_test 2.2b {
 227   db eval {
 228     EXPLAIN QUERY PLAN
 229     SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn
 230   }
 231 } {/ORDER BY/}   ;# separate sorting pass due to "+" on ORDER BY terms
 232
 233 # The same query with ORDER BY optimizations turned off via built-in test.
 234 #
 235 do_test 2.3a {
 236   optimization_control db order-by-idx-join 0
 237   db cache flush
 238   db eval {
 239     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
 240   }
 241 } {one-a one-c two-a two-b three-a three-c}
 242 do_test 2.3b {
 243   db eval {
 244     EXPLAIN QUERY PLAN
 245     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
 246   }
 247 } {/ORDER BY/}   ;# separate sorting pass due to disabled optimization
 248 optimization_control db all 1
 249 db cache flush
 250
 251 # Reverse order sorts
 252 #
 253 do_test 2.4a {
 254   db eval {
 255     SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
 256   }
 257 } {three-a three-c two-a two-b one-a one-c}
 258 do_test 2.4b {
 259   db eval {
 260     SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn
 261   }
 262 } {three-a three-c two-a two-b one-a one-c}  ;# verify same order after sorting
 263 do_test 2.4c {
 264   db eval {
 265     EXPLAIN QUERY PLAN
 266     SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
 267   }
 268 } {/ORDER BY/}  ;# separate sorting pass due to mixed DESC/ASC
 269
 270
 271 do_test 2.5a {
 272   db eval {
 273     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
 274   }
 275 } {one-c one-a two-b two-a three-c three-a}
 276 do_test 2.5b {
 277   db eval {
 278     SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC
 279   }
 280 } {one-c one-a two-b two-a three-c three-a}  ;# verify same order after sorting
 281 do_test 2.5c {
 282   db eval {
 283     EXPLAIN QUERY PLAN
 284     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
 285   }
 286 } {/ORDER BY/}  ;# separate sorting pass due to mixed ASC/DESC
 287
 288 do_test 2.6a {
 289   db eval {
 290     SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
 291   }
 292 } {three-c three-a two-b two-a one-c one-a}
 293 do_test 2.6b {
 294   db eval {
 295     SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn DESC
 296   }
 297 } {three-c three-a two-b two-a one-c one-a}  ;# verify same order after sorting
 298 do_test 2.6c {
 299   db eval {
 300     EXPLAIN QUERY PLAN
 301     SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
 302   }
 303 } {/ORDER BY/}  ;# ORDER BY required
 304
 305
 306 # Generate another test dataset, but this time using mixed ASC/DESC indices.
 307 #
 308 do_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 NULL
 316     );
 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 VALUES
 326         (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 } {}
 336 do_test 3.1a {
 337   db eval {
 338     SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn DESC
 339   }
 340 } {one-c one-a two-b two-a three-c three-a}
 341
 342 # Verify that the ORDER BY clause is optimized out
 343 #
 344 do_test 3.1b {
 345   db eval {
 346     EXPLAIN QUERY PLAN
 347     SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn DESC
 348   }
 349 } {~/ORDER BY/}  ;# ORDER BY optimized out
 350
 351 # The same query with ORDER BY clause optimization disabled via + operators
 352 # should give exactly the same answer.
 353 #
 354 do_test 3.2a {
 355   db eval {
 356     SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC
 357   }
 358 } {one-c one-a two-b two-a three-c three-a}
 359
 360 # The output is sorted manually in this case.
 361 #
 362 do_test 3.2b {
 363   db eval {
 364     EXPLAIN QUERY PLAN
 365     SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC
 366   }
 367 } {/ORDER BY/}   ;# separate sorting pass due to "+" on ORDER BY terms
 368
 369 # The same query with ORDER BY optimizations turned off via built-in test.
 370 #
 371 do_test 3.3a {
 372   optimization_control db order-by-idx-join 0
 373   db cache flush
 374   db eval {
 375     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
 376   }
 377 } {one-c one-a two-b two-a three-c three-a}
 378 do_test 3.3b {
 379   db eval {
 380     EXPLAIN QUERY PLAN
 381     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
 382   }
 383 } {/ORDER BY/}   ;# separate sorting pass due to disabled optimization
 384 optimization_control db all 1
 385 db cache flush
 386
 387 # Without the mixed ASC/DESC on ORDER BY
 388 #
 389 do_test 3.4a {
 390   db eval {
 391     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
 392   }
 393 } {one-a one-c two-a two-b three-a three-c}
 394 do_test 3.4b {
 395   db eval {
 396     SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn
 397   }
 398 } {one-a one-c two-a two-b three-a three-c}  ;# verify same order after sorting
 399 do_test 3.4c {
 400   db eval {
 401     EXPLAIN QUERY PLAN
 402     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
 403   }
 404 } {~/ORDER BY/}  ;# ORDER BY suppressed by uniqueness constraints
 405
 406 do_test 3.5a {
 407   db eval {
 408     SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
 409   }
 410 } {three-c three-a two-b two-a one-c one-a}
 411 do_test 3.5b {
 412   db eval {
 413     SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn DESC
 414   }
 415 } {three-c three-a two-b two-a one-c one-a}  ;# verify same order after sorting
 416 do_test 3.5c {
 417   db eval {
 418     EXPLAIN QUERY PLAN
 419     SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
 420   }
 421 } {~/ORDER BY/}  ;# ORDER BY suppressed by uniqueness constraints
 422
 423
 424 do_test 3.6a {
 425   db eval {
 426     SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn
 427   }
 428 } {three-a three-c two-a two-b one-a one-c}
 429 do_test 3.6b {
 430   db eval {
 431     SELECT name FROM album CROSS JOIN track USING (aid)
 432      ORDER BY +title DESC, +tn
 433   }
 434 } {three-a three-c two-a two-b one-a one-c}  ;# verify same order after sorting
 435 do_test 3.6c {
 436   db eval {
 437     EXPLAIN QUERY PLAN
 438     SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn
 439   }
 440 } {~/ORDER BY/}  ;# inverted ASC/DESC is optimized out
 441
 442 # Ticket 5ed1772895bf3deeab78c5e3519b1da9165c541b (2013-06-04)
 443 # Incorrect ORDER BY on an indexed JOIN
 444 #
 445 do_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 #
 460 do_eqp_test 5.0 {
 461   SELECT 5 ORDER BY 1
 462 } {
 463   QUERY PLAN
 464   `--SCAN CONSTANT ROW
 465 }
 466 do_execsql_test 5.1 {
 467   EXPLAIN QUERY PLAN SELECT 5 UNION ALL SELECT 3 ORDER BY 1
 468 } {~/B-TREE/}
 469 do_execsql_test 5.2 {
 470   SELECT 5 UNION ALL SELECT 3 ORDER BY 1
 471 } {3 5}
 472 do_execsql_test 5.3 {
 473   SELECT 986 AS x GROUP BY X ORDER BY X
 474 } {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 deeply
 478 # nested query.  This test caused a segfault on 3.8.5 beta.
 479 #
 480 do_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 SQLite
 494 # 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-column
 496 # index.  This was due to an oversight in the indexMightHelpWithOrderby()
 497 # routine in where.c.
 498 #
 499 do_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 PLAN
 504   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 data
 509 # to disk.
 510 #
 511 reset_db
 512 do_execsql_test 8.0 {
 513   PRAGMA cache_size = 5;
 514   CREATE TABLE t1(a, b);
 515   CREATE INDEX i1 ON t1(a);
 516 }
 517
 518 do_eqp_test 8.1 {
 519   SELECT * FROM t1 ORDER BY a, b;
 520 } {
 521   QUERY PLAN
 522   |--SCAN t1 USING INDEX i1
 523   `--USE TEMP B-TREE FOR RIGHT PART OF ORDER BY
 524 }
 525
 526 do_execsql_test 8.2 {
 527   WITH cnt(i) AS (
 528     SELECT 1 UNION ALL SELECT i+1 FROM cnt WHERE i<10000
 529   )
 530   INSERT INTO t1 SELECT i%2, randomblob(500) FROM cnt;
 531 }
 532
 533 do_test 8.3 {
 534   db eval { SELECT * FROM t1 ORDER BY a, b } { incr res $a }
 535   set res
 536 } 5000
 537
 538 #---------------------------------------------------------------------------
 539 # https://www.sqlite.org/src/tktview/cb3aa0641d9a413841c004293a4fc06cdc122029
 540 #
 541 # Adverse interaction between scalar subqueries and the partial-sorting
 542 # logic.
 543 #
 544 do_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 new
 555 # optimization that had not been previously released.
 556 #
 557 do_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
 564 do_catchsql_test 11.0 {
 565   VALUES(2) EXCEPT SELECT '' ORDER BY abc
 566 } {1 {1st ORDER BY term does not match any column in the result set}}
 567
 568
 569 finish_test