From 9da8bf9ae7143bb4dec6e473ac4dd6fac6384d65 Mon Sep 17 00:00:00 2001 From: drh Date: Mon, 17 Jul 2017 19:07:14 +0000 Subject: [PATCH] For FROM-clause subqueries that cannot be flattened, try to push relevant WHERE clause terms of the outer query down into the subquery in order to help the subquery run faster and/or use less memory. Cherry-pick from [6df18e949d36]. Still need to backport bug fixes associated with that check-in. FossilOrigin-Name: 043d6ce8ad85f8044735747b8938ea5ce9a08e71b860c2b7179b824021bb7a62 --- manifest | 16 +++-- manifest.uuid | 2 +- src/select.c | 177 ++++++++++++++++++++++++++++++++++++-------------- 3 files changed, 139 insertions(+), 56 deletions(-) diff --git a/manifest b/manifest index 8d0e566596..3e0b7688a8 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Fix\sthe\scovering\sindex\sOR\soptimization\s(check-in\s[fcbd6abd])\sso\sthat\nit\sworks\swith\sSQLITE_MAX_ATTACHED>30.\s\sBroken\sby\sa\sbad\scherry-pick\smerge. -D 2017-07-08T01:01:08.062 +C For\sFROM-clause\ssubqueries\sthat\scannot\sbe\sflattened,\stry\sto\spush\srelevant\nWHERE\sclause\sterms\sof\sthe\souter\squery\sdown\sinto\sthe\ssubquery\sin\sorder\sto\shelp\nthe\ssubquery\srun\sfaster\sand/or\suse\sless\smemory.\nCherry-pick\sfrom\s[6df18e949d36].\s\sStill\sneed\sto\sbackport\sbug\sfixes\sassociated\nwith\sthat\scheck-in. +D 2017-07-17T19:07:14.155 F Makefile.arm-wince-mingw32ce-gcc d6df77f1f48d690bd73162294bbba7f59507c72f F Makefile.in 00d12636df7a5b08af09116bcd6c7bfd49b8b3b4 F Makefile.linux-gcc 91d710bdc4998cb015f39edf3cb314ec4f4d7e23 @@ -230,7 +230,7 @@ F src/printf.c 8ae1fa9d30c1200a9268a390ba9e9cea9197b27a F src/random.c ba2679f80ec82c4190062d756f22d0c358180696 F src/resolve.c 41aa91af56d960e9414ce1d7c17cfb68e0d1c6cb F src/rowset.c eccf6af6d620aaa4579bd3b72c1b6395d9e9fa1e -F src/select.c 12b01d61078da5aeaa6bae2bcb1bd5550c86a761dea52b4ce833d4e273e44e96 +F src/select.c 22db63945060c317d48efb0e98ccc8d4cd0c3f2e48123b3ff5de8ce3f4a8a30b F src/shell.c 84a1593bd86aaa14f4da8a8f9b16fbc239d262aa F src/sqlite.h.in 278602140d49575e8708e643161f4263e428a02a F src/sqlite3.rc 992c9f5fb8285ae285d6be28240a7e8d3a7f2bad @@ -1250,7 +1250,11 @@ F tool/vdbe_profile.tcl 67746953071a9f8f2f668b73fe899074e2c6d8c1 F tool/warnings-clang.sh f6aa929dc20ef1f856af04a730772f59283631d4 F tool/warnings.sh 0abfd78ceb09b7f7c27c688c8e3fe93268a13b32 F tool/win/sqlite.vsix deb315d026cc8400325c5863eef847784a219a2f -P fcbd6abdb1a4cf622ff7e85625b9c2a9bbae92410359872924b7fc1e35046a75 -R e16d14bd52b65abae70b31af2e996886 +P d227de8ad9cf757f30f5415ca8fccff3b5959621d09244bd1f444d3282c5b2ef +Q +6df18e949d3676290785143993513ea1b917d729 +R e3d665c8862aa342ba39861cd8f4b980 +T *branch * push-down-backport +T *sym-push-down-backport * +T -sym-branch-3.8.9 * U drh -Z 1ba13c74fc4ad36a0d13cfbf7520225c +Z 47d048d729d8d3e7689e51a3a0eb2508 diff --git a/manifest.uuid b/manifest.uuid index 2f2d4b0dd3..113dddaa29 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -d227de8ad9cf757f30f5415ca8fccff3b5959621d09244bd1f444d3282c5b2ef \ No newline at end of file +043d6ce8ad85f8044735747b8938ea5ce9a08e71b860c2b7179b824021bb7a62 \ No newline at end of file diff --git a/src/select.c b/src/select.c index 58d21758a4..1b623202ee 100644 --- a/src/select.c +++ b/src/select.c @@ -3749,6 +3749,73 @@ static int flattenSubquery( } #endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */ + + +#if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) +/* +** Make copies of relevant WHERE clause terms of the outer query into +** the WHERE clause of subquery. Example: +** +** SELECT * FROM (SELECT a AS x, c-d AS y FROM t1) WHERE x=5 AND y=10; +** +** Transformed into: +** +** SELECT * FROM (SELECT a AS x, c-d AS y FROM t1 WHERE a=5 AND c-d=10) +** WHERE x=5 AND y=10; +** +** The hope is that the terms added to the inner query will make it more +** efficient. +** +** Do not attempt this optimization if: +** +** (1) The inner query is an aggregate. (In that case, we'd really want +** to copy the outer WHERE-clause terms onto the HAVING clause of the +** inner query. But they probably won't help there so do not bother.) +** +** (2) The inner query is the recursive part of a common table expression. +** +** (3) The inner query has a LIMIT clause (since the changes to the WHERE +** close would change the meaning of the LIMIT). +** +** (4) The inner query is the right operand of a LEFT JOIN. (The caller +** enforces this restriction since this routine does not have enough +** information to know.) +** +** Return 0 if no changes are made and non-zero if one or more WHERE clause +** terms are duplicated into the subquery. +*/ +static int pushDownWhereTerms( + sqlite3 *db, /* The database connection (for malloc()) */ + Select *pSubq, /* The subquery whose WHERE clause is to be augmented */ + Expr *pWhere, /* The WHERE clause of the outer query */ + int iCursor /* Cursor number of the subquery */ +){ + Expr *pNew; + int nChng = 0; + if( pWhere==0 ) return 0; + if( (pSubq->selFlags & (SF_Aggregate|SF_Recursive))!=0 ){ + return 0; /* restrictions (1) and (2) */ + } + if( pSubq->pLimit!=0 ){ + return 0; /* restriction (3) */ + } + while( pWhere->op==TK_AND ){ + nChng += pushDownWhereTerms(db, pSubq, pWhere->pRight, iCursor); + pWhere = pWhere->pLeft; + } + if( sqlite3ExprIsTableConstant(pWhere, iCursor) ){ + nChng++; + while( pSubq ){ + pNew = sqlite3ExprDup(db, pWhere, 0); + pNew = substExpr(db, pNew, iCursor, pSubq->pEList); + pSubq->pWhere = sqlite3ExprAnd(db, pSubq->pWhere, pNew); + pSubq = pSubq->pPrior; + } + } + return nChng; +} +#endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */ + /* ** Based on the contents of the AggInfo structure indicated by the first ** argument, this function checks if the following are true: @@ -4940,59 +5007,71 @@ int sqlite3Select( p->selFlags |= SF_Aggregate; } i = -1; - }else if( pTabList->nSrc==1 - && OptimizationEnabled(db, SQLITE_SubqCoroutine) - ){ - /* Implement a co-routine that will return a single row of the result - ** set on each invocation. - */ - int addrTop = sqlite3VdbeCurrentAddr(v)+1; - pItem->regReturn = ++pParse->nMem; - sqlite3VdbeAddOp3(v, OP_InitCoroutine, pItem->regReturn, 0, addrTop); - VdbeComment((v, "%s", pItem->pTab->zName)); - pItem->addrFillSub = addrTop; - sqlite3SelectDestInit(&dest, SRT_Coroutine, pItem->regReturn); - explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId); - sqlite3Select(pParse, pSub, &dest); - pItem->pTab->nRowLogEst = sqlite3LogEst(pSub->nSelectRow); - pItem->viaCoroutine = 1; - pItem->regResult = dest.iSdst; - sqlite3VdbeAddOp1(v, OP_EndCoroutine, pItem->regReturn); - sqlite3VdbeJumpHere(v, addrTop-1); - sqlite3ClearTempRegCache(pParse); }else{ - /* Generate a subroutine that will fill an ephemeral table with - ** the content of this subquery. pItem->addrFillSub will point - ** to the address of the generated subroutine. pItem->regReturn - ** is a register allocated to hold the subroutine return address - */ - int topAddr; - int onceAddr = 0; - int retAddr; - assert( pItem->addrFillSub==0 ); - pItem->regReturn = ++pParse->nMem; - topAddr = sqlite3VdbeAddOp2(v, OP_Integer, 0, pItem->regReturn); - pItem->addrFillSub = topAddr+1; - if( pItem->isCorrelated==0 ){ - /* If the subquery is not correlated and if we are not inside of - ** a trigger, then we only need to compute the value of the subquery - ** once. */ - onceAddr = sqlite3CodeOnce(pParse); VdbeCoverage(v); - VdbeComment((v, "materialize \"%s\"", pItem->pTab->zName)); + if( (pItem->jointype & JT_OUTER)==0 + && pushDownWhereTerms(db, pSub, p->pWhere, pItem->iCursor) + ){ +#if SELECTTRACE_ENABLED + if( sqlite3SelectTrace & 0x100 ){ + sqlite3DebugPrintf("After WHERE-clause push-down:\n"); + sqlite3TreeViewSelect(0, p, 0); + } +#endif + } + if( pTabList->nSrc==1 + && OptimizationEnabled(db, SQLITE_SubqCoroutine) + ){ + /* Implement a co-routine that will return a single row of the result + ** set on each invocation. + */ + int addrTop = sqlite3VdbeCurrentAddr(v)+1; + pItem->regReturn = ++pParse->nMem; + sqlite3VdbeAddOp3(v, OP_InitCoroutine, pItem->regReturn, 0, addrTop); + VdbeComment((v, "%s", pItem->pTab->zName)); + pItem->addrFillSub = addrTop; + sqlite3SelectDestInit(&dest, SRT_Coroutine, pItem->regReturn); + explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId); + sqlite3Select(pParse, pSub, &dest); + pItem->pTab->nRowLogEst = sqlite3LogEst(pSub->nSelectRow); + pItem->viaCoroutine = 1; + pItem->regResult = dest.iSdst; + sqlite3VdbeAddOp1(v, OP_EndCoroutine, pItem->regReturn); + sqlite3VdbeJumpHere(v, addrTop-1); + sqlite3ClearTempRegCache(pParse); }else{ - VdbeNoopComment((v, "materialize \"%s\"", pItem->pTab->zName)); + /* Generate a subroutine that will fill an ephemeral table with + ** the content of this subquery. pItem->addrFillSub will point + ** to the address of the generated subroutine. pItem->regReturn + ** is a register allocated to hold the subroutine return address + */ + int topAddr; + int onceAddr = 0; + int retAddr; + assert( pItem->addrFillSub==0 ); + pItem->regReturn = ++pParse->nMem; + topAddr = sqlite3VdbeAddOp2(v, OP_Integer, 0, pItem->regReturn); + pItem->addrFillSub = topAddr+1; + if( pItem->isCorrelated==0 ){ + /* If the subquery is not correlated and if we are not inside of + ** a trigger, then we only need to compute the value of the subquery + ** once. */ + onceAddr = sqlite3CodeOnce(pParse); VdbeCoverage(v); + VdbeComment((v, "materialize \"%s\"", pItem->pTab->zName)); + }else{ + VdbeNoopComment((v, "materialize \"%s\"", pItem->pTab->zName)); + } + sqlite3SelectDestInit(&dest, SRT_EphemTab, pItem->iCursor); + explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId); + sqlite3Select(pParse, pSub, &dest); + pItem->pTab->nRowLogEst = sqlite3LogEst(pSub->nSelectRow); + if( onceAddr ) sqlite3VdbeJumpHere(v, onceAddr); + retAddr = sqlite3VdbeAddOp1(v, OP_Return, pItem->regReturn); + VdbeComment((v, "end %s", pItem->pTab->zName)); + sqlite3VdbeChangeP1(v, topAddr, retAddr); + sqlite3ClearTempRegCache(pParse); } - sqlite3SelectDestInit(&dest, SRT_EphemTab, pItem->iCursor); - explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId); - sqlite3Select(pParse, pSub, &dest); - pItem->pTab->nRowLogEst = sqlite3LogEst(pSub->nSelectRow); - if( onceAddr ) sqlite3VdbeJumpHere(v, onceAddr); - retAddr = sqlite3VdbeAddOp1(v, OP_Return, pItem->regReturn); - VdbeComment((v, "end %s", pItem->pTab->zName)); - sqlite3VdbeChangeP1(v, topAddr, retAddr); - sqlite3ClearTempRegCache(pParse); } - if( /*pParse->nErr ||*/ db->mallocFailed ){ + if( db->mallocFailed ){ goto select_end; } pParse->nHeight -= sqlite3SelectExprHeight(p); -- 2.47.2