Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Fix handling of COLLATE. Add test cases for the same. Code cleanup for improved understandability and maintainability. |
---|---|
Downloads: | Tarball | ZIP archive | SQL archive |
Timelines: | family | ancestors | descendants | both | order-by-subquery |
Files: | files | file ages | folders |
SHA3-256: |
41a41c173a9d15d94f23d73a5c04bfb1 |
User & Date: | drh 2024-08-16 11:26:21 |
Context
2024-08-16
| ||
18:58 | Merge the latest trunk enhancements into the wal2 branch. (check-in: a78208b5 user: drh tags: wal2) | |
18:51 | If a subquery has an ORDER BY clause and that ordering is helpfile in satisfying the ORDER BY or GROUP BY of the outer query without doing an extra sort, then omit or reduce the sort in the outer query. Call this the "order-by-subquery optimization". (check-in: 7a0cdc7e user: drh tags: trunk) | |
11:26 | Fix handling of COLLATE. Add test cases for the same. Code cleanup for improved understandability and maintainability. (Closed-Leaf check-in: 41a41c17 user: drh tags: order-by-subquery) | |
02:19 | Bug fix in the subquery ORDER BY propagator. (check-in: 5a9a3b8a user: drh tags: order-by-subquery) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
4843 4844 4845 4846 4847 4848 4849 | } } whereLoopClear(db, pNew); return rc; } | > | | > > > > > > > > > > > > > > > > > > > > > < | > | | | > > | | | | | | | | > | | | | | | | | 4843 4844 4845 4846 4847 4848 4849 4850 4851 4852 4853 4854 4855 4856 4857 4858 4859 4860 4861 4862 4863 4864 4865 4866 4867 4868 4869 4870 4871 4872 4873 4874 4875 4876 4877 4878 4879 4880 4881 4882 4883 4884 4885 4886 4887 4888 4889 4890 4891 4892 4893 4894 4895 4896 4897 4898 4899 4900 4901 4902 4903 4904 4905 4906 4907 4908 4909 4910 4911 4912 4913 4914 4915 4916 4917 4918 4919 4920 4921 4922 4923 4924 4925 4926 4927 4928 4929 4930 4931 4932 4933 4934 4935 4936 4937 4938 4939 4940 4941 4942 4943 4944 4945 | } } whereLoopClear(db, pNew); return rc; } /* Implementation of the order-by-subquery optimization: ** ** WhereLoop pLoop, which the iLoop-th term of the nested loop, is really ** a subquery or CTE that has an ORDER BY clause. See if any of the terms ** in the subquery ORDER BY clause will satisfy pOrderBy from the outer ** query. Mark off all satisfied terms (by setting bits in *pOBSat) and ** return TRUE if they do. If not, return false. ** ** Example: ** ** CREATE TABLE t1(a,b,c, PRIMARY KEY(a,b)); ** CREATE TABLE t2(x,y); ** WITH t3(p,q) AS MATERIALIZED (SELECT x+y, x-y FROM t2 ORDER BY x+y) ** SELECT * FROM t3 JOIN t1 ON a=q ORDER BY p, b; ** ** The CTE named "t3" comes out in the natural order of "p", so the first ** first them of "ORDER BY p,b" is satisfied by a sequential scan of "t3" ** and sorting only needs to occur on the second term "b". ** ** Limitations: ** ** (1) The optimization is not applied if the outer ORDER BY contains ** a COLLATE clause. The optimization might be applied if the ** outer ORDER BY uses NULLS FIRST, NULLS LAST, ASC, and/or DESC as ** long as the subquery ORDER BY does the same. But if the ** outer ORDER BY uses COLLATE, even a redundant COLLATE, the ** optimization is bypassed. ** ** (2) The subquery ORDER BY terms must exactly match subquery result ** columns, including any COLLATE annotations. This routine relies ** on iOrderByCol to do matching between order by terms and result ** columns, and iOrderByCol will not be set if the result column ** and ORDER BY collations differ. ** ** (3) The subquery and outer ORDER BY can be in opposite directions as ** long as the subquery is materialized. If the subquery is ** implemented as a co-routine, the sort orders must be in the same ** direction because there is no way to run a co-routine backwards. */ static SQLITE_NOINLINE int wherePathMatchSubqueryOB( WhereInfo *pWInfo, /* The WHERE clause */ WhereLoop *pLoop, /* The nested loop term that is a subquery */ int iLoop, /* Which level of the nested loop. 0==outermost */ int iCur, /* Cursor used by the this loop */ ExprList *pOrderBy, /* The ORDER BY clause on the whole query */ Bitmask *pRevMask, /* When loops need to go in reverse order */ Bitmask *pOBSat /* Which terms of pOrderBy are satisfied so far */ ){ int iOB; /* Index into pOrderBy->a[] */ int jSub; /* Index into pSubOB->a[] */ u8 rev = 0; /* True if iOB and jSub sort in opposite directions */ u8 revIdx = 0; /* Sort direction for jSub */ Expr *pOBExpr; /* Current term of outer ORDER BY */ ExprList *pSubOB; /* Complete ORDER BY on the subquery */ pSubOB = pLoop->u.btree.pOrderBy; assert( pSubOB!=0 ); for(iOB=0; (MASKBIT(iOB) & *pOBSat)!=0; iOB++){} for(jSub=0; jSub<pSubOB->nExpr && iOB<pOrderBy->nExpr; jSub++, iOB++){ if( pSubOB->a[jSub].u.x.iOrderByCol==0 ) break; pOBExpr = pOrderBy->a[iOB].pExpr; if( pOBExpr->op!=TK_COLUMN && pOBExpr->op!=TK_AGG_COLUMN ) break; if( pOBExpr->iTable!=iCur ) break; if( pOBExpr->iColumn!=pSubOB->a[jSub].u.x.iOrderByCol-1 ) break; if( (pWInfo->wctrlFlags & WHERE_GROUPBY)==0 ){ u8 sfOB = pOrderBy->a[iOB].fg.sortFlags; /* sortFlags for iOB */ u8 sfSub = pSubOB->a[jSub].fg.sortFlags; /* sortFlags for jSub */ if( (sfSub & KEYINFO_ORDER_BIGNULL) != (sfOB & KEYINFO_ORDER_BIGNULL) ){ break; } revIdx = sfSub & KEYINFO_ORDER_DESC; if( jSub>0 ){ if( (rev^revIdx)!=(sfOB & KEYINFO_ORDER_DESC) ){ break; } }else{ rev = revIdx ^ (sfOB & KEYINFO_ORDER_DESC); if( rev ){ if( (pLoop->wsFlags & WHERE_COROUTINE)!=0 ){ /* Cannot run a co-routine in reverse order */ break; } *pRevMask |= MASKBIT(iLoop); } } } *pOBSat |= MASKBIT(iOB); } return jSub>0; } /* ** Examine a WherePath (with the addition of the extra WhereLoop of the 6th ** parameters) to see if it outputs rows in the requested ORDER BY ** (or GROUP BY) without requiring a separate sort operation. Return N: ** |
︙ | ︙ | |||
5056 5057 5058 5059 5060 5061 5062 | obSat |= MASKBIT(i); } if( (pLoop->wsFlags & WHERE_ONEROW)==0 ){ if( pLoop->wsFlags & WHERE_IPK ){ if( pLoop->u.btree.pOrderBy && OptimizationEnabled(db, SQLITE_OrderBySubq) | | | 5081 5082 5083 5084 5085 5086 5087 5088 5089 5090 5091 5092 5093 5094 5095 | obSat |= MASKBIT(i); } if( (pLoop->wsFlags & WHERE_ONEROW)==0 ){ if( pLoop->wsFlags & WHERE_IPK ){ if( pLoop->u.btree.pOrderBy && OptimizationEnabled(db, SQLITE_OrderBySubq) && wherePathMatchSubqueryOB(pWInfo,pLoop,iLoop,iCur, pOrderBy,pRevMask, &obSat) ){ nColumn = 0; isOrderDistinct = 0; }else{ nColumn = 1; } |
︙ | ︙ |
Added test/orderbyB.test.
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 | # 2024-08-15 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #*********************************************************************** # This file implements regression tests for SQLite library. # # Specifically, it tests cases with order-by-subquery optimization in which # an ORDER BY in a subquery is used to help resolve an ORDER BY in the # outer query without having to do an extra sort. # set testdir [file dirname $argv0] source $testdir/tester.tcl set ::testprefix orderbyb db null NULL do_execsql_test 1.0 { CREATE TABLE t1(a TEXT, b TEXT, c INT); INSERT INTO t1 VALUES(NULL,NULL,NULL); WITH RECURSIVE c(n) AS (VALUES(1) UNION ALL SELECT n+1 FROM c WHERE n<7) INSERT INTO t1(a,b,c) SELECT char(p,p), char(q,q), n FROM (SELECT ((n-1)%4)+0x61 AS p, abs(n*2-9+(n>=5))+0x60 AS q, n FROM c); UPDATE t1 SET b=upper(b) WHERE c=1; CREATE TABLE t2(k TEXT PRIMARY KEY, v INT) WITHOUT ROWID; WITH RECURSIVE c(n) AS (VALUES(1) UNION ALL SELECT n+1 FROM c WHERE n<7) INSERT INTO t2(k,v) SELECT char(0x60+n,0x60+n), n FROM c; WITH RECURSIVE c(n) AS (VALUES(1) UNION ALL SELECT n+1 FROM c WHERE n<7) INSERT INTO t2(k,v) SELECT char(0x40+n,0x40+n), n FROM c; SELECT a,b,c,tx.v AS 'v-a', ty.v AS 'v-b' FROM t1 LEFT JOIN t2 AS tx ON tx.k=a LEFT JOIN t2 AS ty ON ty.k=b ORDER BY c; } { NULL NULL NULL NULL NULL aa GG 1 1 7 bb ee 2 2 5 cc cc 3 3 3 dd aa 4 4 1 aa bb 5 1 2 bb dd 6 2 4 cc ff 7 3 6 } do_eqp_execsql_test 1.1 { WITH t3(x,y) AS (SELECT a, b FROM t1 ORDER BY a, b LIMIT 8) SELECT x, y, v FROM t3 LEFT JOIN t2 ON k=t3.y ORDER BY x, y COLLATE nocase; } { QUERY PLAN |--CO-ROUTINE t3 | |--SCAN t1 | `--USE TEMP B-TREE FOR ORDER BY |--SCAN t3 |--SEARCH t2 USING PRIMARY KEY (k=?) LEFT-JOIN `--USE TEMP B-TREE FOR LAST TERM OF ORDER BY } { NULL NULL NULL aa bb 2 aa GG 7 bb dd 4 bb ee 5 cc cc 3 cc ff 6 dd aa 1 } do_eqp_execsql_test 1.2 { WITH t3(x,y) AS MATERIALIZED (SELECT a, b COLLATE nocase FROM t1 ORDER BY 1,2) SELECT x, y, v FROM t3 LEFT JOIN t2 ON k=t3.y ORDER BY x,y; } { QUERY PLAN |--MATERIALIZE t3 | |--SCAN t1 | `--USE TEMP B-TREE FOR ORDER BY |--SCAN t3 `--SEARCH t2 USING PRIMARY KEY (k=?) LEFT-JOIN } { NULL NULL NULL aa bb 2 aa GG 7 bb dd 4 bb ee 5 cc cc 3 cc ff 6 dd aa 1 } finish_test |
Changes to test/tester.tcl.
︙ | ︙ | |||
1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 | } else { if {[string index $res 0]!="/"} { set res "/*$res*/" } uplevel do_execsql_test $name [list "EXPLAIN QUERY PLAN $sql"] [list $res] } } #------------------------------------------------------------------------- # Usage: do_select_tests PREFIX ?SWITCHES? TESTLIST # # Where switches are: # | > > > > > > > > > > > > > > > > > > > > > > > | 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 | } else { if {[string index $res 0]!="/"} { set res "/*$res*/" } uplevel do_execsql_test $name [list "EXPLAIN QUERY PLAN $sql"] [list $res] } } # Do both an eqp_test and an execsql_test on the same SQL. # proc do_eqp_execsql_test {name sql res1 res2} { if {[regexp {^\s+QUERY PLAN\n} $res1]} { set query_plan [query_plan_graph $sql] if {[list {*}$query_plan]==[list {*}$res1]} { uplevel [list do_test ${name}a [list set {} ok] ok] } else { uplevel [list \ do_test ${name}a [list query_plan_graph $sql] $res1 ] } } else { if {[string index $res 0]!="/"} { set res1 "/*$res1*/" } uplevel do_execsql_test ${name}a [list "EXPLAIN QUERY PLAN $sql"] [list $res1] } uplevel do_execsql_test ${name}b [list $sql] [list $res2] } #------------------------------------------------------------------------- # Usage: do_select_tests PREFIX ?SWITCHES? TESTLIST # # Where switches are: # |
︙ | ︙ |