Small performance optimization in sqlite3VdbeRecordCompareWithSkip() for
[sqlite.git] / test / sort.test
blobd73ecea4802d9a0dc82184bfa4d135cefa040c63
1 # 2001 September 15.
3 # The author disclaims copyright to this source code.  In place of
4 # a legal notice, here is a blessing:
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.
10 #***********************************************************************
12 # This file implements regression tests for SQLite library.  The
13 # focus of this file is testing the sorter (code in vdbesort.c).
16 set testdir [file dirname $argv0]
17 source $testdir/tester.tcl
18 set testprefix sort
19 db close
20 sqlite3_shutdown
21 sqlite3_config_pmasz 10
22 sqlite3_initialize
23 sqlite3 db test.db
25 # Create a bunch of data to sort against
27 do_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 real
35     );
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}
48 do_test sort-1.1 {
49   execsql {SELECT n FROM t1 ORDER BY n}
50 } {1 2 3 4 5 6 7 8}
51 do_test sort-1.1.1 {
52   execsql {SELECT n FROM t1 ORDER BY n ASC}
53 } {1 2 3 4 5 6 7 8}
54 do_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}
57 do_test sort-1.2 {
58   execsql {SELECT n FROM t1 ORDER BY n DESC}
59 } {8 7 6 5 4 3 2 1}
60 do_test sort-1.3a {
61   execsql {SELECT v FROM t1 ORDER BY v}
62 } {eight five four one seven six three two}
63 do_test sort-1.3b {
64   execsql {SELECT n FROM t1 ORDER BY v}
65 } {8 5 4 1 7 6 3 2}
66 do_test sort-1.4 {
67   execsql {SELECT n FROM t1 ORDER BY v DESC}
68 } {2 3 6 7 1 4 5 8}
69 do_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}
72 do_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}
75 do_test sort-1.7 {
76   execsql {SELECT roman FROM t1 ORDER BY roman}
77 } {I II III IV V VI VII VIII}
78 do_test sort-1.8 {
79   execsql {SELECT n FROM t1 ORDER BY log, flt}
80 } {1 2 3 5 4 6 7 8}
81 do_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}
84 do_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}
87 do_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}
90 do_test sort-1.9 {
91   execsql {SELECT n FROM t1 ORDER BY log, flt DESC}
92 } {1 3 2 7 6 4 5 8}
93 do_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}
96 do_test sort-1.10 {
97   execsql {SELECT n FROM t1 ORDER BY log DESC, flt}
98 } {8 5 4 6 7 2 3 1}
99 do_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}
103 # These tests are designed to reach some hard-to-reach places
104 # inside the string comparison routines.
106 # (Later) The sorting behavior changed in 2.7.0.  But we will
107 # keep these tests.  You can never have too many test cases!
109 do_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}
116 do_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}
121 do_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}
126 do_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}
131 do_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}
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'.
141 do_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}
150 do_test sort-3.2 {
151   execsql {
152     SELECT a, b FROM t2 ORDER BY a DESC;
153   }
154 } {AGNA 3 AGLIE` 2 AGLIENTU 1}
155 do_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}
164 do_test sort-3.4 {
165   execsql {
166     SELECT a, b FROM t2 ORDER BY a DESC;
167   }
168 } {agna 3 aglientu 1 aglie` 2}
170 # Version 2.7.0 testing.
172 do_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}
181 do_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}
186 do_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}
191 do_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}
196 do_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}
201 do_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}
206 do_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}
211 do_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}
222 do_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}
234 do_test sort-5.2 {
235   execsql {
236     select a from t3 order by b, a desc;
237   }
238 } {6 5 3 2 1 4}
239 do_test sort-5.3 {
240   execsql {
241     select a from t3 order by b desc, a;
242   }
243 } {4 1 2 3 5 6}
244 do_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}
250 do_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}
256 do_test sort-6.2 {
257   execsql {
258     select a from t3 order by b, a desc;
259   }
260 } {6 5 3 2 1 4}
261 do_test sort-6.3 {
262   execsql {
263     select a from t3 order by b desc, a;
264   }
265 } {4 1 2 3 5 6}
266 do_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}
272 do_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}
285 do_test sort-7.2 {
286   execsql {
287     SELECT b FROM t4 ORDER BY 1
288   }
289 } {1 11 12 2}
291 # Omit tests sort-7.3 to sort-7.8 if view support was disabled at
292 # compilatation time.
293 ifcapable view {
294 do_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}
300 do_test sort-7.4 {
301   execsql {
302     SELECT b FROM v4 ORDER BY 1;
303   }
304 } {1 11 12 2}
306 ifcapable compound {
307 do_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}
312 do_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.a
317 do_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.b
322 do_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 compound
328 } ;# ifcapable view
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}
362 # Ticket #297
364 do_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}
374 ifcapable {bloblit} {
375 # BLOBs should sort after TEXT
377 do_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}
387 do_test sort-9.2 {
388   execsql {
389     SELECT x FROM t6 ORDER BY y DESC;
390   }
391 } {3 2 1 4}
392 do_test sort-9.3 {
393   execsql {
394     SELECT x FROM t6 WHERE y<1
395   }
396 } {}
397 do_test sort-9.4 {
398   execsql {
399     SELECT x FROM t6 WHERE y<'1'
400   }
401 } {1}
402 do_test sort-9.5 {
403   execsql {
404     SELECT x FROM t6 WHERE y<x'31'
405   }
406 } {1 2}
407 do_test sort-9.6 {
408   execsql {
409     SELECT x FROM t6 WHERE y>1
410   }
411 } {2 3}
412 do_test sort-9.7 {
413   execsql {
414     SELECT x FROM t6 WHERE y>'1'
415   }
416 } {3}
417 } ;# endif bloblit
419 # Ticket #1092 - ORDER BY on rowid fields.
420 do_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 } {}
429 do_test sort-10.2 {
430   execsql {
431     SELECT c FROM t7 WHERE c<=3 ORDER BY c DESC;
432   }
433 } {3 2 1}
434 do_test sort-10.3 {
435   execsql {
436     SELECT c FROM t7 WHERE c<3 ORDER BY c DESC;
437   }
438 } {2 1}
440 # ticket #1358.  Just because one table in a join gives a unique
441 # result does not mean they all do.  We cannot disable sorting unless
442 # all tables in the join give unique results.
444 do_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}
456 # Trouble reported on the mailing list.  Check for overly aggressive
457 # (which is to say, incorrect) optimization of order-by with a rowid
458 # in a join.
460 do_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}
473 #-------------------------------------------------------------------------
474 # Check that the sorter in vdbesort.c sorts in a stable fashion.
476 do_execsql_test sort-13.0 {
477   CREATE TABLE t10(a, b);
479 do_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 } {}
486 do_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}]
489 do_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}]
494 #-------------------------------------------------------------------------
496 foreach {tn mmap_limit nWorker tmpstore coremutex fakeheap softheaplimit} {
497           1          0       3     file      true    false             0
498           2          0       3     file      true     true             0
499           3          0       0     file      true    false             0
500           4    1000000       3     file      true    false             0
501           5          0       0   memory     false     true             0
502           6          0       0     file     false     true       1000000     
503           7          0       0     file     false     true         10000
504 } {
505   db close
506   sqlite3_shutdown
507   if {$coremutex} {
508     sqlite3_config multithread
509   } else {
510     sqlite3_config singlethread
511   }
512   sqlite3_initialize
513   sorter_test_fakeheap $fakeheap
514   sqlite3_soft_heap_limit $softheaplimit
516   reset_db
517   sqlite3_test_control SQLITE_TESTCTRL_SORTER_MMAP db $mmap_limit
518   execsql "PRAGMA temp_store = $tmpstore; PRAGMA threads = $nWorker"
519   
520   
521   set ten [string repeat X 10300]
522   set one [string repeat y   200]
524   if {$softheaplimit} {
525     execsql { PRAGMA cache_size = 20 };
526   } else {
527     execsql { PRAGMA cache_size = 5 };
528   }
530   do_execsql_test 15.$tn.1 {
531     WITH rr AS (
532       SELECT 4, $ten UNION ALL
533       SELECT 2, $one UNION ALL
534       SELECT 1, $ten UNION ALL
535       SELECT 3, $one
536     )
537     SELECT * FROM rr ORDER BY 1;
538   } [list 1 $ten 2 $one 3 $one 4 $ten]
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}
552   do_execsql_test 15.$tn.3 {
553     WITH rr AS (
554       SELECT 4, $ten UNION ALL
555       SELECT 2, $one
556     )
557     SELECT * FROM rr ORDER BY 1;
558   } [list 2 $one 4 $ten]
560   sorter_test_fakeheap 0
563 db close
564 sqlite3_shutdown
565 set t(0) singlethread
566 set t(1) multithread
567 set t(2) serialized
568 sqlite3_config $t($sqlite_options(threadsafe))
569 sqlite3_initialize
570 sqlite3_soft_heap_limit 0
572 reset_db
573 do_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 {}}
582 reset_db
583 do_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}}
593 reset_db
594 do_execsql_test 17.1 {
595   SELECT * FROM sqlite_master ORDER BY sql;
596 } {}
598 finish_test