Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Allow SQLite to omit redundant ORDER BY sorts in the case where a SELECT statement has GROUP BY and ORDER BY clauses that use the same expressions, even when the ORDER BY expressions are marked "DESC". |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA3-256: |
20f7951bb238ddc0b8932a55145df426 |
| User & Date: | dan 2019-09-21 15:44:12 |
Context
|
2019-09-21
| ||
| 17:31 | Fix harmless compiler warnings. check-in: 8ea1dc72 user: drh tags: trunk | |
| 15:44 | Allow SQLite to omit redundant ORDER BY sorts in the case where a SELECT statement has GROUP BY and ORDER BY clauses that use the same expressions, even when the ORDER BY expressions are marked "DESC". check-in: 20f7951b user: dan tags: trunk | |
| 13:34 | Add --multithread, --serialized, and --singlethread options to the speed-check.sh test script. check-in: c17078af user: drh tags: trunk | |
Changes
Changes to src/select.c.
6219 6219 pItem->u.x.iAlias = 0; 6220 6220 } 6221 6221 for(k=pGroupBy->nExpr, pItem=pGroupBy->a; k>0; k--, pItem++){ 6222 6222 pItem->u.x.iAlias = 0; 6223 6223 } 6224 6224 assert( 66==sqlite3LogEst(100) ); 6225 6225 if( p->nSelectRow>66 ) p->nSelectRow = 66; 6226 + 6227 + /* If there is both a GROUP BY and an ORDER BY clause and they are 6228 + ** identical, then it may be possible to disable the ORDER BY clause 6229 + ** on the grounds that the GROUP BY will cause elements to come out 6230 + ** in the correct order. It also may not - the GROUP BY might use a 6231 + ** database index that causes rows to be grouped together as required 6232 + ** but not actually sorted. Either way, record the fact that the 6233 + ** ORDER BY and GROUP BY clauses are the same by setting the orderByGrp 6234 + ** variable. */ 6235 + if( sSort.pOrderBy && pGroupBy->nExpr==sSort.pOrderBy->nExpr ){ 6236 + int i; 6237 + /* The GROUP BY processing doesn't care whether rows are delivered in 6238 + ** ASC or DESC order - only that each group is returned contiguously. 6239 + ** So set the ASC/DESC flags in the GROUP BY to match those in the 6240 + ** ORDER BY to maximize the chances of rows being delivered in an 6241 + ** order that makes the ORDER BY redundant. */ 6242 + for(i=0; i<pGroupBy->nExpr; i++){ 6243 + u8 sortFlags = sSort.pOrderBy->a[i].sortFlags & KEYINFO_ORDER_DESC; 6244 + pGroupBy->a[i].sortFlags = sortFlags; 6245 + } 6246 + if( sqlite3ExprListCompare(pGroupBy, sSort.pOrderBy, -1)==0 ){ 6247 + orderByGrp = 1; 6248 + } 6249 + } 6226 6250 }else{ 6227 6251 assert( 0==sqlite3LogEst(1) ); 6228 6252 p->nSelectRow = 0; 6229 6253 } 6230 6254 6231 - /* If there is both a GROUP BY and an ORDER BY clause and they are 6232 - ** identical, then it may be possible to disable the ORDER BY clause 6233 - ** on the grounds that the GROUP BY will cause elements to come out 6234 - ** in the correct order. It also may not - the GROUP BY might use a 6235 - ** database index that causes rows to be grouped together as required 6236 - ** but not actually sorted. Either way, record the fact that the 6237 - ** ORDER BY and GROUP BY clauses are the same by setting the orderByGrp 6238 - ** variable. */ 6239 - if( sqlite3ExprListCompare(pGroupBy, sSort.pOrderBy, -1)==0 ){ 6240 - orderByGrp = 1; 6241 - } 6242 - 6243 6255 /* Create a label to jump to when we want to abort the query */ 6244 6256 addrEnd = sqlite3VdbeMakeLabel(pParse); 6245 6257 6246 6258 /* Convert TK_COLUMN nodes into TK_AGG_COLUMN and make entries in 6247 6259 ** sAggInfo for all TK_AGG_FUNCTION nodes in expressions of the 6248 6260 ** SELECT statement. 6249 6261 */
Added test/orderbyA.test.
1 +# 2019-09-21 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. 12 +# 13 +# Specifically, it tests cases where the expressions in a GROUP BY 14 +# clause are the same as those in the ORDER BY clause. 15 +# 16 + 17 +set testdir [file dirname $argv0] 18 +source $testdir/tester.tcl 19 +set ::testprefix orderbyA 20 + 21 +proc do_sortcount_test {tn sql cnt res} { 22 + set eqp [execsql "EXPLAIN QUERY PLAN $sql"] 23 + set rcnt [regexp -all {USE TEMP} $eqp] 24 + uplevel [list do_test $tn.1 [list set {} $rcnt] $cnt] 25 + uplevel [list do_execsql_test $tn.2 $sql $res] 26 +} 27 + 28 +do_execsql_test 1.0 { 29 + CREATE TABLE t1(a, b, c); 30 + INSERT INTO t1 VALUES('one', 1, 11); 31 + INSERT INTO t1 VALUES('three', 7, 11); 32 + INSERT INTO t1 VALUES('one', 2, 11); 33 + INSERT INTO t1 VALUES('one', 3, 11); 34 + INSERT INTO t1 VALUES('two', 4, 11); 35 + INSERT INTO t1 VALUES('two', 6, 11); 36 + INSERT INTO t1 VALUES('three', 8, 11); 37 + INSERT INTO t1 VALUES('two', 5, 11); 38 + INSERT INTO t1 VALUES('three', 9, 11); 39 +} 40 + 41 +foreach {tn idx} { 42 + 1 {} 43 + 2 {CREATE INDEX i1 ON t1(a)} 44 + 3 {CREATE INDEX i1 ON t1(a DESC)} 45 +} { 46 + execsql { DROP INDEX IF EXISTS i1 } 47 + execsql $idx 48 + 49 + # $match is the number of temp-table sorts we expect if the GROUP BY 50 + # can use the same sort order as the ORDER BY. $nomatch is the number 51 + # of expected sorts if the GROUP BY and ORDER BY are not compatible. 52 + set match 1 53 + set nomatch 2 54 + if {$tn>=2} { 55 + set match 0 56 + set nomatch 1 57 + } 58 + 59 + do_sortcount_test 1.$tn.1.1 { 60 + SELECT a, sum(b) FROM t1 GROUP BY a ORDER BY a 61 + } $match {one 6 three 24 two 15} 62 + do_sortcount_test 1.$tn.1.2 { 63 + SELECT a, sum(b) FROM t1 GROUP BY a ORDER BY a DESC 64 + } $match {two 15 three 24 one 6} 65 + 66 + do_sortcount_test 1.$tn.2.1 { 67 + SELECT a, sum(b) FROM t1 GROUP BY a ORDER BY a||'' 68 + } $nomatch {one 6 three 24 two 15} 69 + do_sortcount_test 1.$tn.2.2 { 70 + SELECT a, sum(b) FROM t1 GROUP BY a ORDER BY a||'' DESC 71 + } $nomatch {two 15 three 24 one 6} 72 + 73 + do_sortcount_test 1.$tn.3.1 { 74 + SELECT a, sum(b) FROM t1 GROUP BY a ORDER BY a NULLS LAST 75 + } $nomatch {one 6 three 24 two 15} 76 + do_sortcount_test 1.$tn.3.2 { 77 + SELECT a, sum(b) FROM t1 GROUP BY a ORDER BY a DESC NULLS FIRST 78 + } $nomatch {two 15 three 24 one 6} 79 +} 80 + 81 +#------------------------------------------------------------------------- 82 +do_execsql_test 2.0 { 83 + CREATE TABLE t2(a, b, c); 84 + INSERT INTO t2 VALUES(1, 'one', 1); 85 + INSERT INTO t2 VALUES(1, 'two', 2); 86 + INSERT INTO t2 VALUES(1, 'one', 3); 87 + INSERT INTO t2 VALUES(1, 'two', 4); 88 + INSERT INTO t2 VALUES(1, 'one', 5); 89 + INSERT INTO t2 VALUES(1, 'two', 6); 90 + 91 + INSERT INTO t2 VALUES(2, 'one', 7); 92 + INSERT INTO t2 VALUES(2, 'two', 8); 93 + INSERT INTO t2 VALUES(2, 'one', 9); 94 + INSERT INTO t2 VALUES(2, 'two', 10); 95 + INSERT INTO t2 VALUES(2, 'one', 11); 96 + INSERT INTO t2 VALUES(2, 'two', 12); 97 + 98 + INSERT INTO t2 VALUES(NULL, 'one', 13); 99 + INSERT INTO t2 VALUES(NULL, 'two', 14); 100 + INSERT INTO t2 VALUES(NULL, 'one', 15); 101 + INSERT INTO t2 VALUES(NULL, 'two', 16); 102 + INSERT INTO t2 VALUES(NULL, 'one', 17); 103 + INSERT INTO t2 VALUES(NULL, 'two', 18); 104 +} 105 + 106 +foreach {tn idx} { 107 + 1 {} 108 + 109 + 2 { CREATE INDEX i2 ON t2(a, b) } 110 + 3 { CREATE INDEX i2 ON t2(a DESC, b DESC) } 111 + 112 + 4 { CREATE INDEX i2 ON t2(a, b DESC) } 113 + 5 { CREATE INDEX i2 ON t2(a DESC, b) } 114 +} { 115 + execsql { DROP INDEX IF EXISTS i2 } 116 + execsql $idx 117 + 118 + 119 + set nSort [expr ($tn==2 || $tn==3) ? 0 : 1] 120 + do_sortcount_test 2.$tn.1.1 { 121 + SELECT a, b, sum(c) FROM t2 GROUP BY a, b ORDER BY a, b; 122 + } $nSort {{} one 45 {} two 48 1 one 9 1 two 12 2 one 27 2 two 30} 123 + do_sortcount_test 2.$tn.1.2 { 124 + SELECT a, b, sum(c) FROM t2 GROUP BY a, b ORDER BY a DESC, b DESC; 125 + } $nSort {2 two 30 2 one 27 1 two 12 1 one 9 {} two 48 {} one 45} 126 + 127 + set nSort [expr ($tn==4 || $tn==5) ? 0 : 1] 128 + do_sortcount_test 2.$tn.2.1 { 129 + SELECT a, b, sum(c) FROM t2 GROUP BY a, b ORDER BY a, b DESC; 130 + } $nSort { {} two 48 {} one 45 1 two 12 1 one 9 2 two 30 2 one 27 } 131 + do_sortcount_test 2.$tn.2.2 { 132 + SELECT a, b, sum(c) FROM t2 GROUP BY a, b ORDER BY a DESC, b; 133 + } $nSort { 2 one 27 2 two 30 1 one 9 1 two 12 {} one 45 {} two 48 } 134 + 135 + # ORDER BY can never piggyback on the GROUP BY sort if it uses 136 + # non-standard NULLS behaviour. 137 + set nSort [expr $tn==1 ? 2 : 1] 138 + do_sortcount_test 2.$tn.3.1 { 139 + SELECT a, b, sum(c) FROM t2 GROUP BY a, b ORDER BY a, b DESC NULLS FIRST; 140 + } $nSort { {} two 48 {} one 45 1 two 12 1 one 9 2 two 30 2 one 27 } 141 + do_sortcount_test 2.$tn.3.2 { 142 + SELECT a, b, sum(c) FROM t2 GROUP BY a, b ORDER BY a DESC, b NULLS LAST; 143 + } $nSort { 2 one 27 2 two 30 1 one 9 1 two 12 {} one 45 {} two 48 } 144 +} 145 + 146 + 147 +finish_test
Changes to test/tkt-b75a9ca6b0.test.
56 56 6 "SELECT * FROM t1 GROUP BY y ORDER BY x" 57 57 {1 3 2 2 3 1} {$tblscan*$grpsort*$sort} 58 58 59 59 7 "SELECT * FROM t1 GROUP BY x, y ORDER BY x, y DESC" 60 60 {1 3 2 2 3 1} {$idxscan*$sort} 61 61 62 62 8 "SELECT * FROM t1 GROUP BY x, y ORDER BY x DESC, y DESC" 63 - {3 1 2 2 1 3} {$idxscan*$sort} 63 + {3 1 2 2 1 3} {$idxscan} 64 64 65 65 9 "SELECT * FROM t1 GROUP BY x, y ORDER BY x ASC, y ASC" 66 66 {1 3 2 2 3 1} {$idxscan} 67 67 68 68 10 "SELECT * FROM t1 GROUP BY x, y ORDER BY x COLLATE nocase, y" 69 69 {1 3 2 2 3 1} {$idxscan*$sort} 70 70