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     COMMIT;
  47   }
  48 } {}
  49 do_test 1.1a {
  50   db eval {
  51     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  52   }
  53 } {one-a one-c two-a two-b three-a three-c}
  54
  55 # Verify that the ORDER BY clause is optimized out
  56 #
  57 do_test 1.1b {
  58   db eval {
  59     EXPLAIN QUERY PLAN
  60     SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn
  61   }
  62 } {~/ORDER BY/}  ;# ORDER BY optimized out
  63
  64 # The same query with ORDER BY clause optimization disabled via + operators
  65 # should give exactly the same answer.
  66 #
  67 do_test 1.2a {
  68   db eval {
  69     SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn
  70   }
  71 } {one-a one-c two-a two-b three-a three-c}
  72
  73 # The output is sorted manually in this case.
  74 #
  75 do_test 1.2b {
  76   db eval {
  77     EXPLAIN QUERY PLAN
  78     SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn
  79   }
  80 } {/ORDER BY/}   ;# separate sorting pass due to "+" on ORDER BY terms
  81
  82 # The same query with ORDER BY optimizations turned off via built-in test.
  83 #
  84 do_test 1.3a {
  85   optimization_control db order-by-idx-join 0
  86   db cache flush
  87   db eval {
  88     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  89   }
  90 } {one-a one-c two-a two-b three-a three-c}
  91 do_test 1.3b {
  92   db eval {
  93     EXPLAIN QUERY PLAN
  94     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
  95   }
  96 } {/ORDER BY/}   ;# separate sorting pass due to disabled optimization
  97 optimization_control db all 1
  98 db cache flush
  99
 100 # Reverse order sorts
 101 #
 102 do_test 1.4a {
 103   db eval {
 104     SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
 105   }
 106 } {three-a three-c two-a two-b one-a one-c}
 107 do_test 1.4b {
 108   db eval {
 109     SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn
 110   }
 111 } {three-a three-c two-a two-b one-a one-c}  ;# verify same order after sorting
 112 do_test 1.4c {
 113   db eval {
 114     EXPLAIN QUERY PLAN
 115     SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
 116   }
 117 } {~/ORDER BY/}  ;# ORDER BY suppressed due to uniqueness constraints
 118
 119 do_test 1.5a {
 120   db eval {
 121     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
 122   }
 123 } {one-c one-a two-b two-a three-c three-a}
 124 do_test 1.5b {
 125   db eval {
 126     SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC
 127   }
 128 } {one-c one-a two-b two-a three-c three-a}  ;# verify same order after sorting
 129 do_test 1.5c {
 130   db eval {
 131     EXPLAIN QUERY PLAN
 132     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
 133   }
 134 } {~/ORDER BY/}  ;# ORDER BY suppressed due to uniqueness constraints
 135
 136 do_test 1.6a {
 137   db eval {
 138     SELECT name FROM album CROSS JOIN track USING (aid)
 139      ORDER BY title DESC, tn DESC
 140   }
 141 } {three-c three-a two-b two-a one-c one-a}
 142 do_test 1.6b {
 143   db eval {
 144     SELECT name FROM album CROSS JOIN track USING (aid)
 145      ORDER BY +title DESC, +tn DESC
 146   }
 147 } {three-c three-a two-b two-a one-c one-a}  ;# verify same order after sorting
 148 do_test 1.6c {
 149   db eval {
 150     EXPLAIN QUERY PLAN
 151     SELECT name FROM album CROSS JOIN track USING (aid)
 152      ORDER BY title DESC, tn DESC
 153   }
 154 } {~/ORDER BY/}  ;# ORDER BY
 155
 156
 157 # Reconstruct the test data to use indices rather than integer primary keys.
 158 #
 159 do_test 2.0 {
 160   db eval {
 161     BEGIN;
 162     DROP TABLE album;
 163     DROP TABLE track;
 164     CREATE TABLE album(
 165       aid INT PRIMARY KEY,
 166       title TEXT NOT NULL
 167     );
 168     CREATE INDEX album_i1 ON album(title, aid);
 169     CREATE TABLE track(
 170       aid INTEGER NOT NULL REFERENCES album,
 171       tn INTEGER NOT NULL,
 172       name TEXT,
 173       UNIQUE(aid, tn)
 174     );
 175     INSERT INTO album VALUES(1, '1-one'), (20, '2-two'), (3, '3-three');
 176     INSERT INTO track VALUES
 177         (1,  1, 'one-a'),
 178         (20, 2, 'two-b'),
 179         (3,  3, 'three-c'),
 180         (1,  3, 'one-c'),
 181         (20, 1, 'two-a'),
 182         (3,  1, 'three-a');
 183     COMMIT;
 184   }
 185 } {}
 186 do_test 2.1a {
 187   db eval {
 188     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
 189   }
 190 } {one-a one-c two-a two-b three-a three-c}
 191
 192 # Verify that the ORDER BY clause is optimized out
 193 #
 194 do_test 2.1b {
 195   db eval {
 196     EXPLAIN QUERY PLAN
 197     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
 198   }
 199 } {/ORDER BY/}  ;# ORDER BY required because of missing aid term in ORDER BY
 200
 201 do_test 2.1c {
 202   db eval {
 203     SELECT name FROM album JOIN track USING (aid) ORDER BY title, aid, tn
 204   }
 205 } {one-a one-c two-a two-b three-a three-c}
 206 do_test 2.1d {
 207   db eval {
 208     EXPLAIN QUERY PLAN
 209     SELECT name FROM album JOIN track USING (aid) ORDER BY title, aid, tn
 210   }
 211 } {/ORDER BY/}  ;# ORDER BY required in this case
 212
 213 # The same query with ORDER BY clause optimization disabled via + operators
 214 # should give exactly the same answer.
 215 #
 216 do_test 2.2a {
 217   db eval {
 218     SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn
 219   }
 220 } {one-a one-c two-a two-b three-a three-c}
 221
 222 # The output is sorted manually in this case.
 223 #
 224 do_test 2.2b {
 225   db eval {
 226     EXPLAIN QUERY PLAN
 227     SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn
 228   }
 229 } {/ORDER BY/}   ;# separate sorting pass due to "+" on ORDER BY terms
 230
 231 # The same query with ORDER BY optimizations turned off via built-in test.
 232 #
 233 do_test 2.3a {
 234   optimization_control db order-by-idx-join 0
 235   db cache flush
 236   db eval {
 237     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
 238   }
 239 } {one-a one-c two-a two-b three-a three-c}
 240 do_test 2.3b {
 241   db eval {
 242     EXPLAIN QUERY PLAN
 243     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
 244   }
 245 } {/ORDER BY/}   ;# separate sorting pass due to disabled optimization
 246 optimization_control db all 1
 247 db cache flush
 248
 249 # Reverse order sorts
 250 #
 251 do_test 2.4a {
 252   db eval {
 253     SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
 254   }
 255 } {three-a three-c two-a two-b one-a one-c}
 256 do_test 2.4b {
 257   db eval {
 258     SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn
 259   }
 260 } {three-a three-c two-a two-b one-a one-c}  ;# verify same order after sorting
 261 do_test 2.4c {
 262   db eval {
 263     EXPLAIN QUERY PLAN
 264     SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn
 265   }
 266 } {/ORDER BY/}  ;# separate sorting pass due to mixed DESC/ASC
 267
 268
 269 do_test 2.5a {
 270   db eval {
 271     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
 272   }
 273 } {one-c one-a two-b two-a three-c three-a}
 274 do_test 2.5b {
 275   db eval {
 276     SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC
 277   }
 278 } {one-c one-a two-b two-a three-c three-a}  ;# verify same order after sorting
 279 do_test 2.5c {
 280   db eval {
 281     EXPLAIN QUERY PLAN
 282     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
 283   }
 284 } {/ORDER BY/}  ;# separate sorting pass due to mixed ASC/DESC
 285
 286 do_test 2.6a {
 287   db eval {
 288     SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
 289   }
 290 } {three-c three-a two-b two-a one-c one-a}
 291 do_test 2.6b {
 292   db eval {
 293     SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn DESC
 294   }
 295 } {three-c three-a two-b two-a one-c one-a}  ;# verify same order after sorting
 296 do_test 2.6c {
 297   db eval {
 298     EXPLAIN QUERY PLAN
 299     SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
 300   }
 301 } {/ORDER BY/}  ;# ORDER BY required
 302
 303
 304 # Generate another test dataset, but this time using mixed ASC/DESC indices.
 305 #
 306 do_test 3.0 {
 307   db eval {
 308     BEGIN;
 309     DROP TABLE album;
 310     DROP TABLE track;
 311     CREATE TABLE album(
 312       aid INTEGER PRIMARY KEY,
 313       title TEXT UNIQUE NOT NULL
 314     );
 315     CREATE TABLE track(
 316       tid INTEGER PRIMARY KEY,
 317       aid INTEGER NOT NULL REFERENCES album,
 318       tn INTEGER NOT NULL,
 319       name TEXT,
 320       UNIQUE(aid ASC, tn DESC)
 321     );
 322     INSERT INTO album VALUES(1, '1-one'), (2, '2-two'), (3, '3-three');
 323     INSERT INTO track VALUES
 324         (NULL, 1, 1, 'one-a'),
 325         (NULL, 2, 2, 'two-b'),
 326         (NULL, 3, 3, 'three-c'),
 327         (NULL, 1, 3, 'one-c'),
 328         (NULL, 2, 1, 'two-a'),
 329         (NULL, 3, 1, 'three-a');
 330     COMMIT;
 331   }
 332 } {}
 333 do_test 3.1a {
 334   db eval {
 335     SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn DESC
 336   }
 337 } {one-c one-a two-b two-a three-c three-a}
 338
 339 # Verify that the ORDER BY clause is optimized out
 340 #
 341 do_test 3.1b {
 342   db eval {
 343     EXPLAIN QUERY PLAN
 344     SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title, tn DESC
 345   }
 346 } {~/ORDER BY/}  ;# ORDER BY optimized out
 347
 348 # The same query with ORDER BY clause optimization disabled via + operators
 349 # should give exactly the same answer.
 350 #
 351 do_test 3.2a {
 352   db eval {
 353     SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC
 354   }
 355 } {one-c one-a two-b two-a three-c three-a}
 356
 357 # The output is sorted manually in this case.
 358 #
 359 do_test 3.2b {
 360   db eval {
 361     EXPLAIN QUERY PLAN
 362     SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn DESC
 363   }
 364 } {/ORDER BY/}   ;# separate sorting pass due to "+" on ORDER BY terms
 365
 366 # The same query with ORDER BY optimizations turned off via built-in test.
 367 #
 368 do_test 3.3a {
 369   optimization_control db order-by-idx-join 0
 370   db cache flush
 371   db eval {
 372     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
 373   }
 374 } {one-c one-a two-b two-a three-c three-a}
 375 do_test 3.3b {
 376   db eval {
 377     EXPLAIN QUERY PLAN
 378     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn DESC
 379   }
 380 } {/ORDER BY/}   ;# separate sorting pass due to disabled optimization
 381 optimization_control db all 1
 382 db cache flush
 383
 384 # Without the mixed ASC/DESC on ORDER BY
 385 #
 386 do_test 3.4a {
 387   db eval {
 388     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
 389   }
 390 } {one-a one-c two-a two-b three-a three-c}
 391 do_test 3.4b {
 392   db eval {
 393     SELECT name FROM album JOIN track USING (aid) ORDER BY +title, +tn
 394   }
 395 } {one-a one-c two-a two-b three-a three-c}  ;# verify same order after sorting
 396 do_test 3.4c {
 397   db eval {
 398     EXPLAIN QUERY PLAN
 399     SELECT name FROM album JOIN track USING (aid) ORDER BY title, tn
 400   }
 401 } {~/ORDER BY/}  ;# ORDER BY suppressed by uniqueness constraints
 402
 403 do_test 3.5a {
 404   db eval {
 405     SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
 406   }
 407 } {three-c three-a two-b two-a one-c one-a}
 408 do_test 3.5b {
 409   db eval {
 410     SELECT name FROM album JOIN track USING (aid) ORDER BY +title DESC, +tn DESC
 411   }
 412 } {three-c three-a two-b two-a one-c one-a}  ;# verify same order after sorting
 413 do_test 3.5c {
 414   db eval {
 415     EXPLAIN QUERY PLAN
 416     SELECT name FROM album JOIN track USING (aid) ORDER BY title DESC, tn DESC
 417   }
 418 } {~/ORDER BY/}  ;# ORDER BY suppressed by uniqueness constraints
 419
 420
 421 do_test 3.6a {
 422   db eval {
 423     SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn
 424   }
 425 } {three-a three-c two-a two-b one-a one-c}
 426 do_test 3.6b {
 427   db eval {
 428     SELECT name FROM album CROSS JOIN track USING (aid)
 429      ORDER BY +title DESC, +tn
 430   }
 431 } {three-a three-c two-a two-b one-a one-c}  ;# verify same order after sorting
 432 do_test 3.6c {
 433   db eval {
 434     EXPLAIN QUERY PLAN
 435     SELECT name FROM album CROSS JOIN track USING (aid) ORDER BY title DESC, tn
 436   }
 437 } {~/ORDER BY/}  ;# inverted ASC/DESC is optimized out
 438
 439 # Ticket 5ed1772895bf3deeab78c5e3519b1da9165c541b (2013-06-04)
 440 # Incorrect ORDER BY on an indexed JOIN
 441 #
 442 do_test 4.0 {
 443   db eval {
 444     CREATE TABLE t41(a INT UNIQUE NOT NULL, b INT NOT NULL);
 445     CREATE INDEX t41ba ON t41(b,a);
 446     CREATE TABLE t42(x INT NOT NULL REFERENCES t41(a), y INT NOT NULL);
 447     CREATE UNIQUE INDEX t42xy ON t42(x,y);
 448     INSERT INTO t41 VALUES(1,1),(3,1);
 449     INSERT INTO t42 VALUES(1,13),(1,15),(3,14),(3,16);
 450
 451     SELECT b, y FROM t41 CROSS JOIN t42 ON x=a ORDER BY b, y;
 452   }
 453 } {1 13 1 14 1 15 1 16}
 454
 455 # No sorting of queries that omit the FROM clause.
 456 #
 457 do_eqp_test 5.0 {
 458   SELECT 5 ORDER BY 1
 459 } {
 460   QUERY PLAN
 461   `--SCAN CONSTANT ROW
 462 }
 463 do_execsql_test 5.1 {
 464   EXPLAIN QUERY PLAN SELECT 5 UNION ALL SELECT 3 ORDER BY 1
 465 } {~/B-TREE/}
 466 do_execsql_test 5.2 {
 467   SELECT 5 UNION ALL SELECT 3 ORDER BY 1
 468 } {3 5}
 469 do_execsql_test 5.3 {
 470   SELECT 986 AS x GROUP BY X ORDER BY X
 471 } {986}
 472
 473 # The following test (originally derived from a single test within fuzz.test)
 474 # verifies that a PseudoTable cursor is not closed prematurely in a deeply
 475 # nested query.  This test caused a segfault on 3.8.5 beta.
 476 #
 477 do_execsql_test 6.0 {
 478   CREATE TABLE abc(a, b, c);
 479   INSERT INTO abc VALUES(1, 2, 3);
 480   INSERT INTO abc VALUES(4, 5, 6);
 481   INSERT INTO abc VALUES(7, 8, 9);
 482   SELECT (
 483     SELECT 'hardware' FROM (
 484       SELECT 'software' ORDER BY 'firmware' ASC, 'sportswear' DESC
 485     ) GROUP BY 1 HAVING length(b)
 486   )
 487   FROM abc;
 488 } {hardware hardware hardware}
 489
 490 # Here is a test for a query-planner problem reported on the SQLite
 491 # mailing list on 2014-09-18 by "Merike".  Beginning with version 3.8.0,
 492 # a separate sort was being used rather than using the single-column
 493 # index.  This was due to an oversight in the indexMightHelpWithOrderby()
 494 # routine in where.c.
 495 #
 496 do_execsql_test 7.0 {
 497   CREATE TABLE t7(a,b);
 498   CREATE INDEX t7a ON t7(a);
 499   CREATE INDEX t7ab ON t7(a,b);
 500   EXPLAIN QUERY PLAN
 501   SELECT * FROM t7 WHERE a=?1 ORDER BY rowid;
 502 } {~/ORDER BY/}
 503
 504 #-------------------------------------------------------------------------
 505 # Test a partial sort large enough to cause the sorter to spill data
 506 # to disk.
 507 #
 508 reset_db
 509 do_execsql_test 8.0 {
 510   PRAGMA cache_size = 5;
 511   CREATE TABLE t1(a, b);
 512   CREATE INDEX i1 ON t1(a);
 513 }
 514
 515 do_eqp_test 8.1 {
 516   SELECT * FROM t1 ORDER BY a, b;
 517 } {
 518   QUERY PLAN
 519   |--SCAN TABLE t1 USING INDEX i1
 520   `--USE TEMP B-TREE FOR RIGHT PART OF ORDER BY
 521 }
 522
 523 do_execsql_test 8.2 {
 524   WITH cnt(i) AS (
 525     SELECT 1 UNION ALL SELECT i+1 FROM cnt WHERE i<10000
 526   )
 527   INSERT INTO t1 SELECT i%2, randomblob(500) FROM cnt;
 528 }
 529
 530 do_test 8.3 {
 531   db eval { SELECT * FROM t1 ORDER BY a, b } { incr res $a }
 532   set res
 533 } 5000
 534
 535 #---------------------------------------------------------------------------
 536 # https://www.sqlite.org/src/tktview/cb3aa0641d9a413841c004293a4fc06cdc122029
 537 #
 538 # Adverse interaction between scalar subqueries and the partial-sorting
 539 # logic.
 540 #
 541 do_execsql_test 9.0 {
 542   DROP TABLE IF EXISTS t1;
 543   CREATE TABLE t1(x INTEGER PRIMARY KEY);
 544   INSERT INTO t1 VALUES(1),(2);
 545   DROP TABLE IF EXISTS t2;
 546   CREATE TABLE t2(y);
 547   INSERT INTO t2 VALUES(9),(8),(3),(4);
 548   SELECT (SELECT x||y FROM t2, t1 ORDER BY x, y);
 549 } {13}
 550
 551 # Problem found by OSSFuzz on 2018-05-05.  This was caused by a new
 552 # optimization that had not been previously released.
 553 #
 554 do_execsql_test 10.0 {
 555   CREATE TABLE t10(a,b);
 556   INSERT INTO t10 VALUES(1,2),(8,9),(3,4),(5,4),(0,7);
 557   CREATE INDEX t10b ON t10(b);
 558   SELECT b, rowid, '^' FROM t10 ORDER BY b, a LIMIT 4;
 559 } {2 1 ^ 4 3 ^ 4 4 ^ 7 5 ^}
 560
 561
 562 finish_test