/ Check-in [20f7951b]
Login

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: 20f7951bb238ddc0b8932a55145df426b6fdf7b8631e069345902c853c90f191
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
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

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