AryaWu/sqlite
0
1# 2001 September 15.2#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#12# This file implements regression tests for SQLite library. The13# focus of this file is testing the sorter (code in vdbesort.c).14#15 16set testdir [file dirname $argv0]17source $testdir/tester.tcl18set testprefix sort19db close20sqlite3_shutdown21sqlite3_config_pmasz 1022sqlite3_initialize23sqlite3 db test.db24 25# Create a bunch of data to sort against26#27do_test sort-1.0 {28 execsql {29 CREATE TABLE t1(30 n int,31 v varchar(10),32 log int,33 roman varchar(10),34 flt real35 );36 INSERT INTO t1 VALUES(1,'one',0,'I',3.141592653);37 INSERT INTO t1 VALUES(2,'two',1,'II',2.15);38 INSERT INTO t1 VALUES(3,'three',1,'III',4221.0);39 INSERT INTO t1 VALUES(4,'four',2,'IV',-0.0013442);40 INSERT INTO t1 VALUES(5,'five',2,'V',-11);41 INSERT INTO t1 VALUES(6,'six',2,'VI',0.123);42 INSERT INTO t1 VALUES(7,'seven',2,'VII',123.0);43 INSERT INTO t1 VALUES(8,'eight',3,'VIII',-1.6);44 }45 execsql {SELECT count(*) FROM t1}46} {8}47 48do_test sort-1.1 {49 execsql {SELECT n FROM t1 ORDER BY n}50} {1 2 3 4 5 6 7 8}51do_test sort-1.1.1 {52 execsql {SELECT n FROM t1 ORDER BY n ASC}53} {1 2 3 4 5 6 7 8}54do_test sort-1.1.1 {55 execsql {SELECT ALL n FROM t1 ORDER BY n ASC}56} {1 2 3 4 5 6 7 8}57do_test sort-1.2 {58 execsql {SELECT n FROM t1 ORDER BY n DESC}59} {8 7 6 5 4 3 2 1}60do_test sort-1.3a {61 execsql {SELECT v FROM t1 ORDER BY v}62} {eight five four one seven six three two}63do_test sort-1.3b {64 execsql {SELECT n FROM t1 ORDER BY v}65} {8 5 4 1 7 6 3 2}66do_test sort-1.4 {67 execsql {SELECT n FROM t1 ORDER BY v DESC}68} {2 3 6 7 1 4 5 8}69do_test sort-1.5 {70 execsql {SELECT flt FROM t1 ORDER BY flt}71} {-11.0 -1.6 -0.0013442 0.123 2.15 3.141592653 123.0 4221.0}72do_test sort-1.6 {73 execsql {SELECT flt FROM t1 ORDER BY flt DESC}74} {4221.0 123.0 3.141592653 2.15 0.123 -0.0013442 -1.6 -11.0}75do_test sort-1.7 {76 execsql {SELECT roman FROM t1 ORDER BY roman}77} {I II III IV V VI VII VIII}78do_test sort-1.8 {79 execsql {SELECT n FROM t1 ORDER BY log, flt}80} {1 2 3 5 4 6 7 8}81do_test sort-1.8.1 {82 execsql {SELECT n FROM t1 ORDER BY log asc, flt}83} {1 2 3 5 4 6 7 8}84do_test sort-1.8.2 {85 execsql {SELECT n FROM t1 ORDER BY log, flt ASC}86} {1 2 3 5 4 6 7 8}87do_test sort-1.8.3 {88 execsql {SELECT n FROM t1 ORDER BY log ASC, flt asc}89} {1 2 3 5 4 6 7 8}90do_test sort-1.9 {91 execsql {SELECT n FROM t1 ORDER BY log, flt DESC}92} {1 3 2 7 6 4 5 8}93do_test sort-1.9.1 {94 execsql {SELECT n FROM t1 ORDER BY log ASC, flt DESC}95} {1 3 2 7 6 4 5 8}96do_test sort-1.10 {97 execsql {SELECT n FROM t1 ORDER BY log DESC, flt}98} {8 5 4 6 7 2 3 1}99do_test sort-1.11 {100 execsql {SELECT n FROM t1 ORDER BY log DESC, flt DESC}101} {8 7 6 4 5 3 2 1}102 103# These tests are designed to reach some hard-to-reach places104# inside the string comparison routines.105#106# (Later) The sorting behavior changed in 2.7.0. But we will107# keep these tests. You can never have too many test cases!108#109do_test sort-2.1.1 {110 execsql {111 UPDATE t1 SET v='x' || -flt;112 UPDATE t1 SET v='x-2b' where v=='x-0.123';113 SELECT v FROM t1 ORDER BY v;114 }115} {x-123.0 x-2.15 x-2b x-3.141592653 x-4221.0 x0.0013442 x1.6 x11.0}116do_test sort-2.1.2 {117 execsql {118 SELECT v FROM t1 ORDER BY substr(v,2,999);119 }120} {x-123.0 x-2.15 x-2b x-3.141592653 x-4221.0 x0.0013442 x1.6 x11.0}121do_test sort-2.1.3 {122 execsql {123 SELECT v FROM t1 ORDER BY substr(v,2,999)+0.0;124 }125} {x-4221.0 x-123.0 x-3.141592653 x-2.15 x-2b x0.0013442 x1.6 x11.0}126do_test sort-2.1.4 {127 execsql {128 SELECT v FROM t1 ORDER BY substr(v,2,999) DESC;129 }130} {x11.0 x1.6 x0.0013442 x-4221.0 x-3.141592653 x-2b x-2.15 x-123.0}131do_test sort-2.1.5 {132 execsql {133 SELECT v FROM t1 ORDER BY substr(v,2,999)+0.0 DESC;134 }135} {x11.0 x1.6 x0.0013442 x-2b x-2.15 x-3.141592653 x-123.0 x-4221.0}136 137# This is a bug fix for 2.2.4.138# Strings are normally mapped to upper-case for a caseless comparison.139# But this can cause problems for characters in between 'Z' and 'a'.140#141do_test sort-3.1 {142 execsql {143 CREATE TABLE t2(a,b);144 INSERT INTO t2 VALUES('AGLIENTU',1);145 INSERT INTO t2 VALUES('AGLIE`',2);146 INSERT INTO t2 VALUES('AGNA',3);147 SELECT a, b FROM t2 ORDER BY a;148 }149} {AGLIENTU 1 AGLIE` 2 AGNA 3}150do_test sort-3.2 {151 execsql {152 SELECT a, b FROM t2 ORDER BY a DESC;153 }154} {AGNA 3 AGLIE` 2 AGLIENTU 1}155do_test sort-3.3 {156 execsql {157 DELETE FROM t2;158 INSERT INTO t2 VALUES('aglientu',1);159 INSERT INTO t2 VALUES('aglie`',2);160 INSERT INTO t2 VALUES('agna',3);161 SELECT a, b FROM t2 ORDER BY a;162 }163} {aglie` 2 aglientu 1 agna 3}164do_test sort-3.4 {165 execsql {166 SELECT a, b FROM t2 ORDER BY a DESC;167 }168} {agna 3 aglientu 1 aglie` 2}169 170# Version 2.7.0 testing.171#172do_test sort-4.1 {173 execsql {174 INSERT INTO t1 VALUES(9,'x2.7',3,'IX',4.0e5);175 INSERT INTO t1 VALUES(10,'x5.0e10',3,'X',-4.0e5);176 INSERT INTO t1 VALUES(11,'x-4.0e9',3,'XI',4.1e4);177 INSERT INTO t1 VALUES(12,'x01234567890123456789',3,'XII',-4.2e3);178 SELECT n FROM t1 ORDER BY n;179 }180} {1 2 3 4 5 6 7 8 9 10 11 12}181do_test sort-4.2 {182 execsql {183 SELECT n||'' FROM t1 ORDER BY 1;184 }185} {1 10 11 12 2 3 4 5 6 7 8 9}186do_test sort-4.3 {187 execsql {188 SELECT n+0 FROM t1 ORDER BY 1;189 }190} {1 2 3 4 5 6 7 8 9 10 11 12}191do_test sort-4.4 {192 execsql {193 SELECT n||'' FROM t1 ORDER BY 1 DESC;194 }195} {9 8 7 6 5 4 3 2 12 11 10 1}196do_test sort-4.5 {197 execsql {198 SELECT n+0 FROM t1 ORDER BY 1 DESC;199 }200} {12 11 10 9 8 7 6 5 4 3 2 1}201do_test sort-4.6 {202 execsql {203 SELECT v FROM t1 ORDER BY 1;204 }205} {x-123.0 x-2.15 x-2b x-3.141592653 x-4.0e9 x-4221.0 x0.0013442 x01234567890123456789 x1.6 x11.0 x2.7 x5.0e10}206do_test sort-4.7 {207 execsql {208 SELECT v FROM t1 ORDER BY 1 DESC;209 }210} {x5.0e10 x2.7 x11.0 x1.6 x01234567890123456789 x0.0013442 x-4221.0 x-4.0e9 x-3.141592653 x-2b x-2.15 x-123.0}211do_test sort-4.8 {212 execsql {213 SELECT substr(v,2,99) FROM t1 ORDER BY 1;214 }215} {-123.0 -2.15 -2b -3.141592653 -4.0e9 -4221.0 0.0013442 01234567890123456789 1.6 11.0 2.7 5.0e10}216#do_test sort-4.9 {217# execsql {218# SELECT substr(v,2,99)+0.0 FROM t1 ORDER BY 1;219# }220#} {-4000000000 -4221 -123 -3.141592653 -2.15 -2 0.0013442 1.6 2.7 11 50000000000 1.23456789012346e+18}221 222do_test sort-5.1 {223 execsql {224 create table t3(a,b);225 insert into t3 values(5,NULL);226 insert into t3 values(6,NULL);227 insert into t3 values(3,NULL);228 insert into t3 values(4,'cd');229 insert into t3 values(1,'ab');230 insert into t3 values(2,NULL);231 select a from t3 order by b, a;232 }233} {2 3 5 6 1 4}234do_test sort-5.2 {235 execsql {236 select a from t3 order by b, a desc;237 }238} {6 5 3 2 1 4}239do_test sort-5.3 {240 execsql {241 select a from t3 order by b desc, a;242 }243} {4 1 2 3 5 6}244do_test sort-5.4 {245 execsql {246 select a from t3 order by b desc, a desc;247 }248} {4 1 6 5 3 2}249 250do_test sort-6.1 {251 execsql {252 create index i3 on t3(b,a);253 select a from t3 order by b, a;254 }255} {2 3 5 6 1 4}256do_test sort-6.2 {257 execsql {258 select a from t3 order by b, a desc;259 }260} {6 5 3 2 1 4}261do_test sort-6.3 {262 execsql {263 select a from t3 order by b desc, a;264 }265} {4 1 2 3 5 6}266do_test sort-6.4 {267 execsql {268 select a from t3 order by b desc, a desc;269 }270} {4 1 6 5 3 2}271 272do_test sort-7.1 {273 execsql {274 CREATE TABLE t4(275 a INTEGER,276 b VARCHAR(30)277 );278 INSERT INTO t4 VALUES(1,1);279 INSERT INTO t4 VALUES(2,2);280 INSERT INTO t4 VALUES(11,11);281 INSERT INTO t4 VALUES(12,12);282 SELECT a FROM t4 ORDER BY 1;283 }284} {1 2 11 12}285do_test sort-7.2 {286 execsql {287 SELECT b FROM t4 ORDER BY 1288 }289} {1 11 12 2}290 291# Omit tests sort-7.3 to sort-7.8 if view support was disabled at292# compilatation time.293ifcapable view {294do_test sort-7.3 {295 execsql {296 CREATE VIEW v4 AS SELECT * FROM t4;297 SELECT a FROM v4 ORDER BY 1;298 }299} {1 2 11 12}300do_test sort-7.4 {301 execsql {302 SELECT b FROM v4 ORDER BY 1;303 }304} {1 11 12 2}305 306ifcapable compound {307do_test sort-7.5 {308 execsql {309 SELECT a FROM t4 UNION SELECT a FROM v4 ORDER BY 1;310 }311} {1 2 11 12}312do_test sort-7.6 {313 execsql {314 SELECT b FROM t4 UNION SELECT a FROM v4 ORDER BY 1;315 }316} {1 2 11 12 1 11 12 2} ;# text from t4.b and numeric from v4.a317do_test sort-7.7 {318 execsql {319 SELECT a FROM t4 UNION SELECT b FROM v4 ORDER BY 1;320 }321} {1 2 11 12 1 11 12 2} ;# numeric from t4.a and text from v4.b322do_test sort-7.8 {323 execsql {324 SELECT b FROM t4 UNION SELECT b FROM v4 ORDER BY 1;325 }326} {1 11 12 2}327} ;# ifcapable compound328} ;# ifcapable view329 330#### Version 3 works differently here:331#do_test sort-7.9 {332# execsql {333# SELECT b FROM t4 UNION SELECT b FROM v4 ORDER BY 1 COLLATE numeric;334# }335#} {1 2 11 12}336#do_test sort-7.10 {337# execsql {338# SELECT b FROM t4 UNION SELECT b FROM v4 ORDER BY 1 COLLATE integer;339# }340#} {1 2 11 12}341#do_test sort-7.11 {342# execsql {343# SELECT b FROM t4 UNION SELECT b FROM v4 ORDER BY 1 COLLATE text;344# }345#} {1 11 12 2}346#do_test sort-7.12 {347# execsql {348# SELECT b FROM t4 UNION SELECT b FROM v4 ORDER BY 1 COLLATE blob;349# }350#} {1 11 12 2}351#do_test sort-7.13 {352# execsql {353# SELECT b FROM t4 UNION SELECT b FROM v4 ORDER BY 1 COLLATE clob;354# }355#} {1 11 12 2}356#do_test sort-7.14 {357# execsql {358# SELECT b FROM t4 UNION SELECT b FROM v4 ORDER BY 1 COLLATE varchar;359# }360#} {1 11 12 2}361 362# Ticket #297363#364do_test sort-8.1 {365 execsql {366 CREATE TABLE t5(a real, b text);367 INSERT INTO t5 VALUES(100,'A1');368 INSERT INTO t5 VALUES(100.0,'A2');369 SELECT * FROM t5 ORDER BY a, b;370 }371} {100.0 A1 100.0 A2}372 373 374ifcapable {bloblit} {375# BLOBs should sort after TEXT376#377do_test sort-9.1 {378 execsql {379 CREATE TABLE t6(x, y);380 INSERT INTO t6 VALUES(1,1);381 INSERT INTO t6 VALUES(2,'1');382 INSERT INTO t6 VALUES(3,x'31');383 INSERT INTO t6 VALUES(4,NULL);384 SELECT x FROM t6 ORDER BY y;385 }386} {4 1 2 3}387do_test sort-9.2 {388 execsql {389 SELECT x FROM t6 ORDER BY y DESC;390 }391} {3 2 1 4}392do_test sort-9.3 {393 execsql {394 SELECT x FROM t6 WHERE y<1395 }396} {}397do_test sort-9.4 {398 execsql {399 SELECT x FROM t6 WHERE y<'1'400 }401} {1}402do_test sort-9.5 {403 execsql {404 SELECT x FROM t6 WHERE y<x'31'405 }406} {1 2}407do_test sort-9.6 {408 execsql {409 SELECT x FROM t6 WHERE y>1410 }411} {2 3}412do_test sort-9.7 {413 execsql {414 SELECT x FROM t6 WHERE y>'1'415 }416} {3}417} ;# endif bloblit418 419# Ticket #1092 - ORDER BY on rowid fields.420do_test sort-10.1 {421 execsql {422 CREATE TABLE t7(c INTEGER PRIMARY KEY);423 INSERT INTO t7 VALUES(1);424 INSERT INTO t7 VALUES(2);425 INSERT INTO t7 VALUES(3);426 INSERT INTO t7 VALUES(4);427 }428} {}429do_test sort-10.2 {430 execsql {431 SELECT c FROM t7 WHERE c<=3 ORDER BY c DESC;432 }433} {3 2 1}434do_test sort-10.3 {435 execsql {436 SELECT c FROM t7 WHERE c<3 ORDER BY c DESC;437 }438} {2 1}439 440# ticket #1358. Just because one table in a join gives a unique441# result does not mean they all do. We cannot disable sorting unless442# all tables in the join give unique results.443#444do_test sort-11.1 {445 execsql {446 create table t8(a unique, b, c);447 insert into t8 values(1,2,3);448 insert into t8 values(2,3,4);449 create table t9(x,y);450 insert into t9 values(2,4);451 insert into t9 values(2,3);452 select y from t8, t9 where a=1 order by a, y;453 }454} {3 4}455 456# Trouble reported on the mailing list. Check for overly aggressive457# (which is to say, incorrect) optimization of order-by with a rowid458# in a join.459#460do_test sort-12.1 {461 execsql {462 create table a (id integer primary key);463 create table b (id integer primary key, aId integer, text);464 insert into a values (1);465 insert into b values (2, 1, 'xxx');466 insert into b values (1, 1, 'zzz');467 insert into b values (3, 1, 'yyy');468 select a.id, b.id, b.text from a join b on (a.id = b.aId)469 order by a.id, b.text;470 }471} {1 2 xxx 1 3 yyy 1 1 zzz}472 473#-------------------------------------------------------------------------474# Check that the sorter in vdbesort.c sorts in a stable fashion.475#476do_execsql_test sort-13.0 {477 CREATE TABLE t10(a, b);478}479do_test sort-13.1 {480 db transaction {481 for {set i 0} {$i < 100000} {incr i} {482 execsql { INSERT INTO t10 VALUES( $i/10, $i%10 ) }483 }484 }485} {}486do_execsql_test sort-13.2 {487 SELECT a, b FROM t10 ORDER BY a;488} [db eval {SELECT a, b FROM t10 ORDER BY a, b}]489do_execsql_test sort-13.3 {490 PRAGMA cache_size = 5;491 SELECT a, b FROM t10 ORDER BY a;492} [db eval {SELECT a, b FROM t10 ORDER BY a, b}]493 494#-------------------------------------------------------------------------495#496foreach {tn mmap_limit nWorker tmpstore coremutex fakeheap softheaplimit} {497 1 0 3 file true false 0498 2 0 3 file true true 0499 3 0 0 file true false 0500 4 1000000 3 file true false 0501 5 0 0 memory false true 0502 6 0 0 file false true 1000000 503 7 0 0 file false true 10000504} {505 db close506 sqlite3_shutdown507 if {$coremutex} {508 sqlite3_config multithread509 } else {510 sqlite3_config singlethread511 }512 sqlite3_initialize513 sorter_test_fakeheap $fakeheap514 sqlite3_soft_heap_limit $softheaplimit515 516 reset_db517 sqlite3_test_control SQLITE_TESTCTRL_SORTER_MMAP db $mmap_limit518 execsql "PRAGMA temp_store = $tmpstore; PRAGMA threads = $nWorker"519 520 521 set ten [string repeat X 10300]522 set one [string repeat y 200]523 524 if {$softheaplimit} {525 execsql { PRAGMA cache_size = 20 };526 } else {527 execsql { PRAGMA cache_size = 5 };528 }529 530 do_execsql_test 15.$tn.1 {531 WITH rr AS (532 SELECT 4, $ten UNION ALL533 SELECT 2, $one UNION ALL534 SELECT 1, $ten UNION ALL535 SELECT 3, $one536 )537 SELECT * FROM rr ORDER BY 1;538 } [list 1 $ten 2 $one 3 $one 4 $ten]539 540 do_execsql_test 15.$tn.2 {541 CREATE TABLE t1(a);542 INSERT INTO t1 VALUES(4);543 INSERT INTO t1 VALUES(5);544 INSERT INTO t1 VALUES(3);545 INSERT INTO t1 VALUES(2);546 INSERT INTO t1 VALUES(6);547 INSERT INTO t1 VALUES(1);548 CREATE INDEX i1 ON t1(a);549 SELECT * FROM t1 ORDER BY a;550 } {1 2 3 4 5 6}551 552 do_execsql_test 15.$tn.3 {553 WITH rr AS (554 SELECT 4, $ten UNION ALL555 SELECT 2, $one556 )557 SELECT * FROM rr ORDER BY 1;558 } [list 2 $one 4 $ten]559 560 sorter_test_fakeheap 0561}562 563db close564sqlite3_shutdown565set t(0) singlethread566set t(1) multithread567set t(2) serialized568sqlite3_config $t($sqlite_options(threadsafe))569sqlite3_initialize570sqlite3_soft_heap_limit 0571 572reset_db573do_catchsql_test 16.1 {574 CREATE TABLE t1(a, b, c);575 INSERT INTO t1 VALUES(1, 2, 3);576 INSERT INTO t1 VALUES(1, NULL, 3);577 INSERT INTO t1 VALUES(NULL, 2, 3);578 INSERT INTO t1 VALUES(1, 2, NULL);579 INSERT INTO t1 VALUES(4, 5, 6);580 CREATE UNIQUE INDEX i1 ON t1(b, a, c);581} {0 {}}582reset_db583do_catchsql_test 16.2 {584 CREATE TABLE t1(a, b, c);585 INSERT INTO t1 VALUES(1, 2, 3);586 INSERT INTO t1 VALUES(1, NULL, 3);587 INSERT INTO t1 VALUES(1, 2, 3);588 INSERT INTO t1 VALUES(1, 2, NULL);589 INSERT INTO t1 VALUES(4, 5, 6);590 CREATE UNIQUE INDEX i1 ON t1(b, a, c);591} {1 {UNIQUE constraint failed: t1.b, t1.a, t1.c}}592 593reset_db594do_execsql_test 17.1 {595 SELECT * FROM sqlite_master ORDER BY sql;596} {}597 598# 2022-12-03 Ticket e8b674241947eb3b599# Improve estimates for the cost of sorting relative600# to the cost of doing an index lookup, so as to get601# a better query plan. See the ticket for a deetailed602# example.603#604reset_db605do_execsql_test 18.1 {606 CREATE TABLE t1(a INTEGER PRIMARY KEY, b, c);607 WITH RECURSIVE c(x) AS (VALUES(1) UNION ALL SELECT x+1 FROM c WHERE x<50)608 -- increase to 5000 for actual test data ----^^609 INSERT INTO t1(a,b,c) SELECT x, random()%5000, random()%5000 FROM c;610 CREATE TABLE t2(d,e,f);611 WITH RECURSIVE c(x) AS (VALUES(1) UNION ALL SELECT x+1 FROM c WHERE x<500)612 -- increase to 50000 for actual test data -----^^^613 INSERT INTO t2(d,e,f) SELECT614 NULLIF(0, random()%2), random()%5000, random()%5000615 FROM c;616 ANALYZE;617 UPDATE sqlite_stat1 SET stat='50000' WHERE tbl='t2';618 UPDATE sqlite_stat1 SET stat='5000' WHERE tbl='t1';619 ANALYZE sqlite_schema;620} {}621do_execsql_test 18.2 {622 EXPLAIN QUERY PLAN623 SELECT a FROM t1 JOIN t2624 WHERE a IN (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20)625 AND a=CASE WHEN d IS NOT NULL THEN e ELSE f END626 ORDER BY a;627} {/.*SCAN t2.*SEARCH t1.*/}628# ^^^^^^^--^^^^^^^^^--- t2 should be the outer loop.629 630finish_test631