From a79e2a2d28eab71b7434a77ada3af5c2855d9bef Mon Sep 17 00:00:00 2001 From: drh <> Date: Sun, 21 Feb 2021 23:44:14 +0000 Subject: [PATCH] Materialize any CTE that is used more than once. FossilOrigin-Name: ba59159fbe6b83fb6d79fbfee22d983768b0ebbaac7e99d2ac66c810e5e04100 --- manifest | 27 ++++++++++-------- manifest.uuid | 2 +- src/delete.c | 6 +++- src/expr.c | 5 +++- src/prepare.c | 4 ++- src/select.c | 75 ++++++++++++++++++++++++++++++++++--------------- src/sqliteInt.h | 30 ++++++++++++++++++-- src/treeview.c | 8 +++++- src/where.c | 2 +- 9 files changed, 117 insertions(+), 42 deletions(-) diff --git a/manifest b/manifest index 59fa169b0a..fe6d151c8a 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Rename\sthe\s"struct\sSrcList_item"\sobject\sto\sthe\smore\ssuccinct\s"SrcItem".\nThis\sis\sa\ssymbolic\schange\sonly.\s\sThe\slogic\sis\sunmodified. -D 2021-02-21T21:04:54.414 +C Materialize\sany\sCTE\sthat\sis\sused\smore\sthan\sonce. +D 2021-02-21T23:44:14.598 F .fossil-settings/empty-dirs dbb81e8fc0401ac46a1491ab34a7f2c7c0452f2f06b54ebb845d024ca8283ef1 F .fossil-settings/ignore-glob 35175cdfcf539b2318cb04a9901442804be81cd677d8b889fcc9149c21f239ea F LICENSE.md df5091916dbb40e6e9686186587125e1b2ff51f022cc334e886c19a0e9982724 @@ -493,8 +493,8 @@ F src/ctime.c 2a322b9a3d75771fb4d99e0702851f4f68dda982507a0f798eefb0712969a410 F src/date.c dace306a10d9b02ee553d454c8e1cf8d3c9b932e137738a6b15b90253a9bfc10 F src/dbpage.c 8a01e865bf8bc6d7b1844b4314443a6436c07c3efe1d488ed89e81719047833a F src/dbstat.c 3aa79fc3aed7ce906e4ea6c10e85d657299e304f6049861fe300053ac57de36c -F src/delete.c 8097c2c8feade9c46a1828dbdc98e1f52f4934fbff38233a2e7b98729528d244 -F src/expr.c 3a756aae0435178ddaed3b4e99ed7c6006f94d380881a249b7cf9d3fca8a405e +F src/delete.c 83dbb8d8c136a100b7a15da38c374b88d82460b3b14f036c169c2d5810223112 +F src/expr.c 6793c836aff149b14011ad546ae1648a18573779ee78f5a7d375f2a3047e8c8e F src/fault.c 460f3e55994363812d9d60844b2a6de88826e007 F src/fkey.c e9063648396c58778f77583a678342fe4a9bc82436bf23c5f9f444f2df0fdaa4 F src/func.c 479f6929be027eb0210cbdde9d3529c012facf082d64a6b854a9415940761e5e @@ -537,17 +537,17 @@ F src/pcache.h 4f87acd914cef5016fae3030343540d75f5b85a1877eed1a2a19b9f284248586 F src/pcache1.c 6596e10baf3d8f84cc1585d226cf1ab26564a5f5caf85a15757a281ff977d51a F src/pragma.c 6daaaecc26a4b09481d21722525b079ce756751a43a79cc1d8f122d686806193 F src/pragma.h 8dc78ab7e9ec6ce3ded8332810a2066f1ef6267e2e03cd7356ee00276125c6cf -F src/prepare.c 7a534d100c556f45f10aee131f2e4244cb52547b7cf17e1c393f55d8abb62e97 +F src/prepare.c f634a9e799a6b1c136d8ee12479cffa22862bfb807d307b1db406aa0cdb042a5 F src/printf.c 10e61ec79dd9d41fdc77afee4e0df04fbb427f309c043118fe0b26a7d7db488a F src/random.c 80f5d666f23feb3e6665a6ce04c7197212a88384 F src/resolve.c c263fa5b255a03314c2418f936386e903d01c3e7cbec25a363a586ef3f10b249 F src/rowset.c ba9515a922af32abe1f7d39406b9d35730ed65efab9443dc5702693b60854c92 -F src/select.c b3277dc42ab20367b023c78d998119915403aa98c4e7230567dd9884ca38d7fd +F src/select.c cc8df79d5838f7c1d0bdbcf3e78b3d2efb781a09a39c4e5146fe7a669a621e82 F src/shell.c.in 844417f84df1f6c4fce1c815629a888cfdcf219e86513e9c332bbcc38832f477 F src/sqlite.h.in 8855a19f37ade8dad189a9e48233a2ebe1b46faf469c7eb0906a654e252dcc57 F src/sqlite3.rc 5121c9e10c3964d5755191c80dd1180c122fc3a8 F src/sqlite3ext.h 61b38c073d5e1e96a3d45271b257aef27d0d13da2bea5347692ae579475cd95e -F src/sqliteInt.h dbe0a5541c6eaabd3535ca6fd9838452bef7d25430267ac6701ef4d0c2cce46a +F src/sqliteInt.h 4e6c2c06e0234ef5e3049e1d0fc551c45db202bee9d90e2397862ec1ae9ca2cf F src/sqliteLimit.h d7323ffea5208c6af2734574bae933ca8ed2ab728083caa117c9738581a31657 F src/status.c 4b8bc2a6905163a38b739854a35b826c737333fab5b1f8e03fa7eb9a4799c4c1 F src/table.c 0f141b58a16de7e2fbe81c308379e7279f4c6b50eb08efeec5892794a0ba30d1 @@ -607,7 +607,7 @@ F src/test_window.c cdae419fdcea5bad6dcd9368c685abdad6deb59e9fc8b84b153de513d394 F src/test_wsd.c 41cadfd9d97fe8e3e4e44f61a4a8ccd6f7ca8fe9 F src/threads.c 4ae07fa022a3dc7c5beb373cf744a85d3c5c6c3c F src/tokenize.c c64c49d7c2ec4490c2fef1f24350167ba16b03b0c6cee58ad1a1d70a4325d4e9 -F src/treeview.c 04bf47d19b9f6f0b636cf42fec6e676b140d781bae792f52a8a014867e838e3e +F src/treeview.c c6260e1fa5f41c361b2409edc9b0050bcaef5bc4d6abc467fbc45f0d7ccf3d84 F src/trigger.c 861c3ec2c5b0fc830bdf82470454a9324fad70cbaa96d2e208fb54577c9e8d28 F src/update.c 0f5a61f0787199983530a33f6fffe4f52742f35fcdf6ccfad1078b1a8bc17723 F src/upsert.c df8f1727d62b5987c4fd302cd4d7c0c84ae57cd65683c5a34a740dfe24039235 @@ -629,7 +629,7 @@ F src/vxworks.h d2988f4e5a61a4dfe82c6524dd3d6e4f2ce3cdb9 F src/wal.c 69e770e96fd56cc21608992bf2c6f1f3dc5cf2572d0495c6a643b06c3a679f14 F src/wal.h c3aa7825bfa2fe0d85bef2db94655f99870a285778baa36307c0a16da32b226a F src/walker.c d42d6c80ea363ef689a462e65eefcfe87deab924c50de5baa37ecb6af7d7ddaa -F src/where.c 40735d2b96b9b071a510fd3f090a195f48a09beb0c97ae0a11fd49e7c9396af9 +F src/where.c a02138440d7230493b5e508664d629f3e1e7615737a5d83aac3a2955d3a654ff F src/whereInt.h 446e5e8018f83358ef917cf32d8e6a86dc8430113d0b17e720f1839d3faa44c4 F src/wherecode.c e57a8690311a75d06e723e8d379f9831de04aba300e07174d236e32a7f9c7a13 F src/whereexpr.c 2dc51263e1fb8d8723e97a077a9a137ab0534e59e4cb88b3195f65edbe43cc32 @@ -1905,7 +1905,10 @@ F vsixtest/vsixtest.tcl 6a9a6ab600c25a91a7acc6293828957a386a8a93 F vsixtest/vsixtest.vcxproj.data 2ed517e100c66dc455b492e1a33350c1b20fbcdc F vsixtest/vsixtest.vcxproj.filters 37e51ffedcdb064aad6ff33b6148725226cd608e F vsixtest/vsixtest_TemporaryKey.pfx e5b1b036facdb453873e7084e1cae9102ccc67a0 -P 0d2c992f3622a6272ca4a3caff6b21f619fe976b8df8b34eff066086f8df2202 -R 3144ef024c1b147facc59f065688290b +P bfd5bf2c73110fcb36db9ba2a949ff516131fbd3e89325f88fe9f5c2b4ed87b2 +R aea18ad89757e208224db76c6eac01bc +T *branch * as-materialize-redux +T *sym-as-materialize-redux * +T -sym-trunk * U drh -Z 9a2772a6abeb20b71009a7863f85f821 +Z aa337b23bcebfb9b048b70a9fb74f61a diff --git a/manifest.uuid b/manifest.uuid index 08a79a0dbf..24a494e999 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -bfd5bf2c73110fcb36db9ba2a949ff516131fbd3e89325f88fe9f5c2b4ed87b2 \ No newline at end of file +ba59159fbe6b83fb6d79fbfee22d983768b0ebbaac7e99d2ac66c810e5e04100 \ No newline at end of file diff --git a/src/delete.c b/src/delete.c index 860a2739ad..117347ef96 100644 --- a/src/delete.c +++ b/src/delete.c @@ -209,7 +209,11 @@ Expr *sqlite3LimitWhere( pSrc->a[0].pTab = 0; pSelectSrc = sqlite3SrcListDup(pParse->db, pSrc, 0); pSrc->a[0].pTab = pTab; - pSrc->a[0].pIBIndex = 0; + if( pSrc->a[0].fg.isIndexedBy ){ + pSrc->a[0].u2.pIBIndex = 0; + }else if( pSrc->a[0].fg.isCte ){ + pSrc->a[0].u2.pCteUse->nUse++; + } /* generate the SELECT expression tree. */ pSelect = sqlite3SelectNew(pParse, pEList, pSelectSrc, pWhere, 0 ,0, diff --git a/src/expr.c b/src/expr.c index cf9a213f4e..b66556b039 100644 --- a/src/expr.c +++ b/src/expr.c @@ -1544,7 +1544,10 @@ SrcList *sqlite3SrcListDup(sqlite3 *db, SrcList *p, int flags){ if( pNewItem->fg.isIndexedBy ){ pNewItem->u1.zIndexedBy = sqlite3DbStrDup(db, pOldItem->u1.zIndexedBy); } - pNewItem->pIBIndex = pOldItem->pIBIndex; + pNewItem->u2 = pOldItem->u2; + if( pNewItem->fg.isCte ){ + pNewItem->u2.pCteUse->nUse++; + } if( pNewItem->fg.isTabFunc ){ pNewItem->u1.pFuncArg = sqlite3ExprListDup(db, pOldItem->u1.pFuncArg, flags); diff --git a/src/prepare.c b/src/prepare.c index dfa20e2b5d..d79495d2c6 100644 --- a/src/prepare.c +++ b/src/prepare.c @@ -597,7 +597,7 @@ void sqlite3ParserReset(Parse *pParse){ ** ** testcase( pParse->earlyCleanup ); */ -void sqlite3ParserAddCleanup( +void *sqlite3ParserAddCleanup( Parse *pParse, /* Destroy when this Parser finishes */ void (*xCleanup)(sqlite3*,void*), /* The cleanup routine */ void *pPtr /* Pointer to object to be cleaned up */ @@ -610,10 +610,12 @@ void sqlite3ParserAddCleanup( pCleanup->xCleanup = xCleanup; }else{ xCleanup(pParse->db, pPtr); + pPtr = 0; #if defined(SQLITE_DEBUG) || defined(SQLITE_COVERAGE_TEST) pParse->earlyCleanup = 1; #endif } + return pPtr; } /* diff --git a/src/select.c b/src/select.c index a9d0eb1530..3da69943f7 100644 --- a/src/select.c +++ b/src/select.c @@ -4726,7 +4726,7 @@ int sqlite3IndexedByLookup(Parse *pParse, SrcItem *pFrom){ pParse->checkSchema = 1; return SQLITE_ERROR; } - pFrom->pIBIndex = pIdx; + pFrom->u2.pIBIndex = pIdx; return SQLITE_OK; } @@ -4935,8 +4935,18 @@ static int resolveFromTermToCte( if( cannotBeFunction(pParse, pFrom) ) return 2; assert( pFrom->pTab==0 ); - pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table)); + pTab = sqlite3DbMallocZero(db, sizeof(Table)); if( pTab==0 ) return 2; + if( pCte->pUse==0 ){ + pCte->pUse = sqlite3DbMallocZero(db, sizeof(pCte->pUse[0])); + if( pCte->pUse==0 + || sqlite3ParserAddCleanup(pParse,sqlite3DbFree,pCte->pUse)==0 + ){ + sqlite3DbFree(db, pTab); + return 2; + } + } + pFrom->pTab = pTab; pTab->nTabRef = 1; pTab->zName = sqlite3DbStrDup(db, pCte->zName); pTab->iPKey = -1; @@ -4945,6 +4955,9 @@ static int resolveFromTermToCte( pFrom->pSelect = sqlite3SelectDup(db, pCte->pSelect, 0); if( db->mallocFailed ) return 2; assert( pFrom->pSelect ); + pFrom->fg.isCte = 1; + pFrom->u2.pCteUse = pCte->pUse; + pCte->pUse->nUse++; /* Check if this is a recursive CTE. */ pRecTerm = pSel = pFrom->pSelect; @@ -6153,6 +6166,7 @@ int sqlite3Select( */ for(i=0; inSrc; i++){ SrcItem *pItem = &pTabList->a[i]; + SrcItem *pPrior; SelectDest dest; Select *pSub; #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) @@ -6212,6 +6226,7 @@ int sqlite3Select( ** inside the subquery. This can help the subquery to run more efficiently. */ if( OptimizationEnabled(db, SQLITE_PushDown) + && (pItem->fg.isCte==0 || pItem->u2.pCteUse->nUse<=1) && pushDownWhereTerms(pParse, pSub, p->pWhere, pItem->iCursor, (pItem->fg.jointype & JT_OUTER)!=0) ){ @@ -6232,16 +6247,18 @@ int sqlite3Select( /* Generate code to implement the subquery ** - ** The subquery is implemented as a co-routine if the subquery is - ** guaranteed to be the outer loop (so that it does not need to be - ** computed more than once) + ** The subquery is implemented as a co-routine if: + ** (1) the subquery is guaranteed to be the outer loop (so that + ** it does not need to be computed more than once), and + ** (2) the subquery is not a CTE that is used more then once. ** - ** TODO: Are there other reasons beside (1) to use a co-routine + ** TODO: Are there other reasons beside (1) and (2) to use a co-routine ** implementation? */ if( i==0 && (pTabList->nSrc==1 || (pTabList->a[1].fg.jointype&(JT_LEFT|JT_CROSS))!=0) /* (1) */ + && (pItem->fg.isCte==0 || pItem->u2.pCteUse->nUse<2) /* (2) */ ){ /* Implement a co-routine that will return a single row of the result ** set on each invocation. @@ -6261,16 +6278,30 @@ int sqlite3Select( sqlite3VdbeEndCoroutine(v, pItem->regReturn); sqlite3VdbeJumpHere(v, addrTop-1); sqlite3ClearTempRegCache(pParse); + }else if( pItem->fg.isCte && pItem->u2.pCteUse->addrM9e>0 ){ + /* This is a CTE for which materialization code has already been + ** generated. Invoke the subroutine to compute the materialization, + ** the make the pItem->iCursor be a copy of the ephemerial table that + ** holds the result of the materialization. */ + CteUse *pCteUse = pItem->u2.pCteUse; + sqlite3VdbeAddOp2(v, OP_Gosub, pCteUse->regRtn, pCteUse->addrM9e); + if( pItem->iCursor!=pCteUse->iCur ){ + sqlite3VdbeAddOp2(v, OP_OpenDup, pItem->iCursor, pCteUse->iCur); + } + pSub->nSelectRow = pCteUse->nRowEst; + }else if( (pPrior = isSelfJoinView(pTabList, pItem))!=0 ){ + /* This view has already been materialized by a prior entry in + ** this same FROM clause. Reuse it. */ + if( pPrior->addrFillSub ){ + sqlite3VdbeAddOp2(v, OP_Gosub, pPrior->regReturn, pPrior->addrFillSub); + } + sqlite3VdbeAddOp2(v, OP_OpenDup, pItem->iCursor, pPrior->iCursor); + pSub->nSelectRow = pPrior->pSelect->nSelectRow; }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 - */ + /* Generate a subroutine that will materialize the view. */ int topAddr; int onceAddr = 0; int retAddr; - SrcItem *pPrior; testcase( pItem->addrFillSub==0 ); /* Ticket c52b09c7f38903b1311 */ pItem->regReturn = ++pParse->nMem; @@ -6285,22 +6316,22 @@ int sqlite3Select( }else{ VdbeNoopComment((v, "materialize \"%s\"", pItem->pTab->zName)); } - pPrior = isSelfJoinView(pTabList, pItem); - if( pPrior ){ - sqlite3VdbeAddOp2(v, OP_OpenDup, pItem->iCursor, pPrior->iCursor); - assert( pPrior->pSelect!=0 ); - pSub->nSelectRow = pPrior->pSelect->nSelectRow; - }else{ - sqlite3SelectDestInit(&dest, SRT_EphemTab, pItem->iCursor); - ExplainQueryPlan((pParse, 1, "MATERIALIZE %u", pSub->selId)); - sqlite3Select(pParse, pSub, &dest); - } + sqlite3SelectDestInit(&dest, SRT_EphemTab, pItem->iCursor); + ExplainQueryPlan((pParse, 1, "MATERIALIZE %u", pSub->selId)); + sqlite3Select(pParse, pSub, &dest); pItem->pTab->nRowLogEst = 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( pItem->fg.isCte ){ + CteUse *pCteUse = pItem->u2.pCteUse; + pCteUse->addrM9e = pItem->addrFillSub; + pCteUse->regRtn = pItem->regReturn; + pCteUse->iCur = pItem->iCursor; + pCteUse->nRowEst = pSub->nSelectRow; + } } if( db->mallocFailed ) goto select_end; pParse->nHeight -= sqlite3SelectExprHeight(p); diff --git a/src/sqliteInt.h b/src/sqliteInt.h index 7fd71a86bf..ea6ff13815 100644 --- a/src/sqliteInt.h +++ b/src/sqliteInt.h @@ -1137,6 +1137,7 @@ typedef struct Bitvec Bitvec; typedef struct CollSeq CollSeq; typedef struct Column Column; typedef struct Cte Cte; +typedef struct CteUse CteUse; typedef struct Db Db; typedef struct DbFixer DbFixer; typedef struct Schema Schema; @@ -2941,6 +2942,7 @@ struct SrcItem { unsigned viaCoroutine :1; /* Implemented as a co-routine */ unsigned isRecursive :1; /* True for recursive reference in WITH */ unsigned fromDDL :1; /* Comes from sqlite_schema */ + unsigned isCte :1; /* This is a CTE */ } fg; int iCursor; /* The VDBE cursor number used to access this table */ Expr *pOn; /* The ON clause of a join */ @@ -2950,7 +2952,10 @@ struct SrcItem { char *zIndexedBy; /* Identifier from "INDEXED BY " clause */ ExprList *pFuncArg; /* Arguments to table-valued-function */ } u1; - Index *pIBIndex; /* Index structure corresponding to u1.zIndexedBy */ + union { + Index *pIBIndex; /* Index structure corresponding to u1.zIndexedBy */ + CteUse *pCteUse; /* CTE Usage info info fg.isCte is true */ + } u2; }; /* @@ -3889,6 +3894,7 @@ struct Cte { ExprList *pCols; /* List of explicit column names, or NULL */ Select *pSelect; /* The definition of this CTE */ const char *zCteErr; /* Error message for circular references */ + CteUse *pUse; /* Usage information for this CTE */ }; /* @@ -3901,6 +3907,26 @@ struct With { Cte a[1]; /* For each CTE in the WITH clause.... */ }; +/* +** The Cte object is not guaranteed to persist for the entire duration +** of code generation. (The query flattener or other parser tree +** edits might delete it.) The following object records information +** about each Common Table Expression that must be preserved for the +** duration of the parse. +** +** The CteUse objects are freed using sqlite3ParserAddCleanup() rather +** than sqlite3SelectDelete(), which is what enables them to persist +** until the end of code generation. +*/ +struct CteUse { + int nUse; /* Number of users of this CTE */ + int addrM9e; /* Start of subroutine to compute materialization */ + int regRtn; /* Return address register for addrM9e subroutine */ + int iCur; /* Ephemeral table holding the materialization */ + LogEst nRowEst; /* Estimated number of rows in the table */ +}; + + #ifdef SQLITE_DEBUG /* ** An instance of the TreeView object is used for printing the content of @@ -4889,7 +4915,7 @@ sqlite3_int64 sqlite3StmtCurrentTime(sqlite3_context*); int sqlite3VdbeParameterIndex(Vdbe*, const char*, int); int sqlite3TransferBindings(sqlite3_stmt *, sqlite3_stmt *); void sqlite3ParserReset(Parse*); -void sqlite3ParserAddCleanup(Parse*,void(*)(sqlite3*,void*),void*); +void *sqlite3ParserAddCleanup(Parse*,void(*)(sqlite3*,void*),void*); #ifdef SQLITE_ENABLE_NORMALIZE char *sqlite3Normalize(Vdbe*, const char*); #endif diff --git a/src/treeview.c b/src/treeview.c index e0fa4971e2..b696d764e0 100644 --- a/src/treeview.c +++ b/src/treeview.c @@ -111,7 +111,10 @@ void sqlite3TreeViewWith(TreeView *pView, const With *pWith, u8 moreToFollow){ } sqlite3_str_appendf(&x, ")"); } - sqlite3_str_appendf(&x, " AS"); + if( pCte->pUse ){ + sqlite3_str_appendf(&x, " (pUse=0x%p, nUse=%d)", pCte->pUse, + pCte->pUse->nUse); + } sqlite3StrAccumFinish(&x); sqlite3TreeViewItem(pView, zLine, inCte-1); sqlite3TreeViewSelect(pView, pCte->pSelect, 0); @@ -150,6 +153,9 @@ void sqlite3TreeViewSrcList(TreeView *pView, const SrcList *pSrc){ if( pItem->fg.fromDDL ){ sqlite3_str_appendf(&x, " DDL"); } + if( pItem->fg.isCte ){ + sqlite3_str_appendf(&x, " CteUse=0x%p", pItem->u2.pCteUse); + } sqlite3StrAccumFinish(&x); sqlite3TreeViewItem(pView, zLine, inSrc-1); if( pItem->pSelect ){ diff --git a/src/where.c b/src/where.c index 63aba17c71..d7aa812849 100644 --- a/src/where.c +++ b/src/where.c @@ -2956,7 +2956,7 @@ static int whereLoopAddBtree( if( pSrc->fg.isIndexedBy ){ /* An INDEXED BY clause specifies a particular index to use */ - pProbe = pSrc->pIBIndex; + pProbe = pSrc->u2.pIBIndex; }else if( !HasRowid(pTab) ){ pProbe = pTab->pIndex; }else{ -- 2.47.2