aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/sqliteInt.h1
-rw-r--r--src/test1.c1
-rw-r--r--src/where.c108
-rw-r--r--src/whereInt.h4
4 files changed, 111 insertions, 3 deletions
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index dca5bb150..ebd0f01b2 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -1927,6 +1927,7 @@ struct sqlite3 {
#define SQLITE_Coroutines 0x02000000 /* Co-routines for subqueries */
#define SQLITE_NullUnusedCols 0x04000000 /* NULL unused columns in subqueries */
#define SQLITE_OnePass 0x08000000 /* Single-pass DELETE and UPDATE */
+#define SQLITE_OrderBySubq 0x10000000 /* ORDER BY in subquery helps outer */
#define SQLITE_AllOpts 0xffffffff /* All optimizations */
/*
diff --git a/src/test1.c b/src/test1.c
index 9def739f4..177091a0e 100644
--- a/src/test1.c
+++ b/src/test1.c
@@ -8100,6 +8100,7 @@ static int SQLITE_TCLAPI optimization_control(
{ "distinct-opt", SQLITE_DistinctOpt },
{ "cover-idx-scan", SQLITE_CoverIdxScan },
{ "order-by-idx-join", SQLITE_OrderByIdxJoin },
+ { "order-by-subquery", SQLITE_OrderBySubq },
{ "transitive", SQLITE_Transitive },
{ "omit-noop-join", SQLITE_OmitNoopJoin },
{ "stat4", SQLITE_Stat4 },
diff --git a/src/where.c b/src/where.c
index 98e9f117f..631b7581f 100644
--- a/src/where.c
+++ b/src/where.c
@@ -4010,6 +4010,10 @@ static int whereLoopAddBtree(
#endif
ApplyCostMultiplier(pNew->rRun, pTab->costMult);
whereLoopOutputAdjust(pWC, pNew, rSize);
+ if( pSrc->pSelect ){
+ if( pSrc->fg.viaCoroutine ) pNew->wsFlags |= WHERE_COROUTINE;
+ pNew->u.btree.pOrderBy = pSrc->pSelect->pOrderBy;
+ }
rc = whereLoopInsert(pBuilder, pNew);
pNew->nOut = rSize;
if( rc ) break;
@@ -4843,6 +4847,97 @@ static int whereLoopAddAll(WhereLoopBuilder *pBuilder){
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
@@ -4988,9 +5083,18 @@ static i8 wherePathSatisfiesOrderBy(
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;
+ }
pIndex = 0;
nKeyCol = 0;
- nColumn = 1;
}else if( (pIndex = pLoop->u.btree.pIndex)==0 || pIndex->bUnordered ){
return 0;
}else{
@@ -5085,7 +5189,7 @@ static i8 wherePathSatisfiesOrderBy(
}
/* Find the ORDER BY term that corresponds to the j-th column
- ** of the index and mark that ORDER BY term off
+ ** of the index and mark that ORDER BY term having been satisfied.
*/
isMatch = 0;
for(i=0; bOnce && i<nOrderBy; i++){
diff --git a/src/whereInt.h b/src/whereInt.h
index d3226e086..c9afed267 100644
--- a/src/whereInt.h
+++ b/src/whereInt.h
@@ -143,6 +143,7 @@ struct WhereLoop {
u16 nTop; /* Size of TOP vector */
u16 nDistinctCol; /* Index columns used to sort for DISTINCT */
Index *pIndex; /* Index used, or NULL */
+ ExprList *pOrderBy; /* ORDER BY clause if this is really a subquery */
} btree;
struct { /* Information for virtual tables */
int idxNum; /* Index number */
@@ -636,7 +637,8 @@ void sqlite3WhereTabFuncArgs(Parse*, SrcItem*, WhereClause*);
#define WHERE_BLOOMFILTER 0x00400000 /* Consider using a Bloom-filter */
#define WHERE_SELFCULL 0x00800000 /* nOut reduced by extra WHERE terms */
#define WHERE_OMIT_OFFSET 0x01000000 /* Set offset counter to zero */
- /* 0x02000000 -- available for reuse */
+#define WHERE_COROUTINE 0x02000000 /* Implemented by co-routine.
+ ** NB: False-negatives are possible */
#define WHERE_EXPRIDX 0x04000000 /* Uses an index-on-expressions */
#endif /* !defined(SQLITE_WHEREINT_H) */