Add code to handle recursive CTEs.
FossilOrigin-Name: a5c2a54a07d35166911abc792008c05dea897742
diff --git a/src/btree.c b/src/btree.c
index 20bed05..e28a97c 100644
--- a/src/btree.c
+++ b/src/btree.c
@@ -7350,6 +7350,7 @@
int rc;
unsigned char *pCell;
int i;
+ int hdr;
assert( sqlite3_mutex_held(pBt->mutex) );
if( pgno>btreePagecount(pBt) ){
@@ -7358,6 +7359,7 @@
rc = getAndInitPage(pBt, pgno, &pPage, 0);
if( rc ) return rc;
+ hdr = pPage->hdrOffset;
for(i=0; i<pPage->nCell; i++){
pCell = findCell(pPage, i);
if( !pPage->leaf ){
@@ -7368,7 +7370,7 @@
if( rc ) goto cleardatabasepage_out;
}
if( !pPage->leaf ){
- rc = clearDatabasePage(pBt, get4byte(&pPage->aData[8]), 1, pnChange);
+ rc = clearDatabasePage(pBt, get4byte(&pPage->aData[hdr+8]), 1, pnChange);
if( rc ) goto cleardatabasepage_out;
}else if( pnChange ){
assert( pPage->intKey );
@@ -7377,7 +7379,7 @@
if( freePageFlag ){
freePage(pPage, &rc);
}else if( (rc = sqlite3PagerWrite(pPage->pDbPage))==0 ){
- zeroPage(pPage, pPage->aData[0] | PTF_LEAF);
+ zeroPage(pPage, pPage->aData[hdr] | PTF_LEAF);
}
cleardatabasepage_out:
diff --git a/src/expr.c b/src/expr.c
index d0ea280..e271e46 100644
--- a/src/expr.c
+++ b/src/expr.c
@@ -1055,6 +1055,7 @@
pNew->addrOpenEphm[1] = -1;
pNew->addrOpenEphm[2] = -1;
pNew->pWith = withDup(db, p->pWith);
+ pNew->pRecurse = p->pRecurse;
return pNew;
}
#else
diff --git a/src/select.c b/src/select.c
index b054489..0db4b01 100644
--- a/src/select.c
+++ b/src/select.c
@@ -691,12 +691,26 @@
/* Store the result as data using a unique key.
*/
+ case SRT_DistTable:
case SRT_Table:
case SRT_EphemTab: {
int r1 = sqlite3GetTempReg(pParse);
testcase( eDest==SRT_Table );
testcase( eDest==SRT_EphemTab );
sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nColumn, r1);
+#ifndef SQLITE_OMIT_CTE
+ if( eDest==SRT_DistTable ){
+ /* If the destination is DistTable, then cursor (iParm+1) is open
+ ** on an ephemeral index. If the current row is already present
+ ** in the index, do not write it to the output. If not, add the
+ ** current row to the index and proceed with writing it to the
+ ** output table as well. */
+ int addr = sqlite3VdbeCurrentAddr(v) + 4;
+ sqlite3VdbeAddOp4Int(v, OP_Found, iParm+1, addr, r1, 0);
+ sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm+1, r1);
+ assert( pOrderBy==0 );
+ }
+#endif
if( pOrderBy ){
pushOntoSorter(pParse, pOrderBy, p, r1);
}else{
@@ -1729,6 +1743,7 @@
** the last (right-most) SELECT in the series may have an ORDER BY or LIMIT.
*/
assert( p && p->pPrior ); /* Calling function guarantees this much */
+ assert( p->pRecurse==0 || p->op==TK_ALL || p->op==TK_UNION );
db = pParse->db;
pPrior = p->pPrior;
assert( pPrior->pRightmost!=pPrior );
@@ -1774,12 +1789,82 @@
goto multi_select_end;
}
+ /* If this is a recursive query, check that there is no ORDER BY or
+ ** LIMIT clause. Neither of these are supported. */
+ assert( p->pOffset==0 || p->pLimit );
+ if( p->pRecurse && (p->pOrderBy || p->pLimit) ){
+ sqlite3ErrorMsg(pParse, "%s in a recursive query is not allowed",
+ p->pOrderBy ? "ORDER BY" : "LIMIT"
+ );
+ goto multi_select_end;
+ }
+
/* Compound SELECTs that have an ORDER BY clause are handled separately.
*/
if( p->pOrderBy ){
return multiSelectOrderBy(pParse, p, pDest);
}
+#ifndef SQLITE_OMIT_CTE
+ if( p->pRecurse ){
+ int nCol = p->pEList->nExpr;
+ int addrNext;
+ int addrSwap;
+ int iCont, iBreak;
+ int tmp1, tmp2; /* Cursors used to access temporary tables */
+ int tmp3 = 0; /* To ensure unique results if UNION */
+ int eDest = SRT_Table;
+ SelectDest tmp2dest;
+
+ iBreak = sqlite3VdbeMakeLabel(v);
+ iCont = sqlite3VdbeMakeLabel(v);
+
+ tmp1 = pParse->nTab++;
+ tmp2 = pParse->nTab++;
+ if( p->op==TK_UNION ){
+ eDest = SRT_DistTable;
+ tmp3 = pParse->nTab++;
+ }
+ sqlite3SelectDestInit(&tmp2dest, eDest, tmp2);
+
+ sqlite3VdbeAddOp2(v, OP_OpenEphemeral, tmp1, nCol);
+ sqlite3VdbeAddOp2(v, OP_OpenEphemeral, tmp2, nCol);
+ if( tmp3 ){
+ p->addrOpenEphm[0] = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, tmp3, 0);
+ p->selFlags |= SF_UsesEphemeral;
+ }
+
+ /* Store the results of the initial SELECT in tmp2. */
+ rc = sqlite3Select(pParse, pPrior, &tmp2dest);
+ if( rc ) goto multi_select_end;
+
+ /* Clear tmp1. Then switch the contents of tmp1 and tmp2. Then teturn
+ ** the contents of tmp1 to the caller. Or, if tmp1 is empty at this
+ ** point, the recursive query has finished - jump to address iBreak. */
+ addrSwap = sqlite3VdbeAddOp2(v, OP_SwapCursors, tmp1, tmp2);
+ sqlite3VdbeAddOp2(v, OP_Rewind, tmp1, iBreak);
+ addrNext = sqlite3VdbeCurrentAddr(v);
+ selectInnerLoop(pParse, p, p->pEList, tmp1, p->pEList->nExpr,
+ 0, 0, &dest, iCont, iBreak);
+ sqlite3VdbeResolveLabel(v, iCont);
+ sqlite3VdbeAddOp2(v, OP_Next, tmp1, addrNext);
+
+ /* Execute the recursive SELECT. Store the results in tmp2. While this
+ ** SELECT is running, the contents of tmp1 are read by recursive
+ ** references to the current CTE. */
+ p->pPrior = 0;
+ p->pRecurse->tnum = tmp1;
+ p->pRecurse->tabFlags |= TF_Recursive;
+ rc = sqlite3Select(pParse, p, &tmp2dest);
+ p->pRecurse->tabFlags &= ~TF_Recursive;
+ p->pPrior = pPrior;
+ if( rc ) goto multi_select_end;
+
+ sqlite3VdbeAddOp2(v, OP_Goto, 0, addrSwap);
+ sqlite3VdbeResolveLabel(v, iBreak);
+ }else
+#endif
+
/* Generate code for the left and right SELECT statements.
*/
switch( p->op ){
@@ -3449,6 +3534,73 @@
}
}
+static int withExpand(
+ Walker *pWalker,
+ struct SrcList_item *pFrom,
+ struct Cte *pCte
+){
+ Table *pTab;
+ Parse *pParse = pWalker->pParse;
+ sqlite3 *db = pParse->db;
+
+ assert( pFrom->pSelect==0 );
+ assert( pFrom->pTab==0 );
+
+ if( pCte==pParse->pCte && (pTab = pCte->pTab) ){
+ /* This is the recursive part of a recursive CTE */
+ pFrom->pTab = pTab;
+ pTab->nRef++;
+ }else{
+ ExprList *pEList;
+ Select *pSel;
+ int bRecursive;
+
+ pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table));
+ if( pTab==0 ) return WRC_Abort;
+ pTab->nRef = 1;
+ pTab->zName = sqlite3MPrintf(db, "sqlite_sq_%p", (void*)pTab);
+ pTab->iPKey = -1;
+ pTab->nRowEst = 1048576;
+ pTab->tabFlags |= TF_Ephemeral;
+ pFrom->pSelect = sqlite3SelectDup(db, pCte->pSelect, 0);
+ if( db->mallocFailed ) return SQLITE_NOMEM;
+ assert( pFrom->pSelect );
+
+ if( ctePush(pParse, pCte) ) return WRC_Abort;
+ pSel = pFrom->pSelect;
+ bRecursive = (pSel->op==TK_ALL || pSel->op==TK_UNION);
+ if( bRecursive ){
+ assert( pSel->pPrior );
+ sqlite3WalkSelect(pWalker, pSel->pPrior);
+ }else{
+ sqlite3WalkSelect(pWalker, pSel);
+ }
+
+ if( pCte->pCols ){
+ pEList = pCte->pCols;
+ }else{
+ Select *pLeft;
+ for(pLeft=pSel; pLeft->pPrior; pLeft=pLeft->pPrior);
+ pEList = pLeft->pEList;
+ }
+ selectColumnsFromExprList(pParse, pEList, &pTab->nCol, &pTab->aCol);
+
+ if( bRecursive ){
+ int nRef = pTab->nRef;
+ pCte->pTab = pTab;
+ sqlite3WalkSelect(pWalker, pSel);
+ pCte->pTab = 0;
+ if( pTab->nRef > nRef){
+ pSel->pRecurse = pTab;
+ assert( pTab->tnum==0 );
+ }
+ }
+
+ ctePop(pParse, pCte);
+ }
+
+ return SQLITE_OK;
+}
/*
** This routine is a Walker callback for "expanding" a SELECT statement.
@@ -3515,31 +3667,22 @@
#ifndef SQLITE_OMIT_CTE
pCte = searchWith(pParse, pFrom);
if( pCte ){
- pFrom->pSelect = sqlite3SelectDup(db, pCte->pSelect, 0);
- if( pFrom->pSelect==0 ) return WRC_Abort;
- }
+ if( withExpand(pWalker, pFrom, pCte) ) return WRC_Abort;
+ }else
#endif
- if( pFrom->zName==0 || pCte ){
+ if( pFrom->zName==0 ){
#ifndef SQLITE_OMIT_SUBQUERY
- ExprList *pEList;
Select *pSel = pFrom->pSelect;
/* A sub-query in the FROM clause of a SELECT */
assert( pSel!=0 );
assert( pFrom->pTab==0 );
- if( ctePush(pParse, pCte) ) return WRC_Abort;
sqlite3WalkSelect(pWalker, pSel);
- ctePop(pParse, pCte);
pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table));
if( pTab==0 ) return WRC_Abort;
pTab->nRef = 1;
pTab->zName = sqlite3MPrintf(db, "sqlite_sq_%p", (void*)pTab);
while( pSel->pPrior ){ pSel = pSel->pPrior; }
- if( pCte && pCte->pCols ){
- pEList = pCte->pCols;
- }else{
- pEList = pSel->pEList;
- }
- selectColumnsFromExprList(pParse, pEList, &pTab->nCol, &pTab->aCol);
+ selectColumnsFromExprList(pParse, pSel->pEList, &pTab->nCol, &pTab->aCol);
pTab->iPKey = -1;
pTab->nRowEst = 1048576;
pTab->tabFlags |= TF_Ephemeral;
@@ -3831,9 +3974,10 @@
if( ALWAYS(pTab!=0) && (pTab->tabFlags & TF_Ephemeral)!=0 ){
/* A sub-query in the FROM clause of a SELECT */
Select *pSel = pFrom->pSelect;
- assert( pSel );
- while( pSel->pPrior ) pSel = pSel->pPrior;
- selectAddColumnTypeAndCollation(pParse, pTab, pSel);
+ if( pSel ){
+ while( pSel->pPrior ) pSel = pSel->pPrior;
+ selectAddColumnTypeAndCollation(pParse, pTab, pSel);
+ }
}
}
}
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index 6bd6559..c7f0609 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -1429,7 +1429,7 @@
};
/*
-** Allowed values for Tabe.tabFlags.
+** Allowed values for Table.tabFlags.
*/
#define TF_Readonly 0x01 /* Read-only system table */
#define TF_Ephemeral 0x02 /* An ephemeral table */
@@ -1437,6 +1437,7 @@
#define TF_Autoincrement 0x08 /* Integer primary key is autoincrement */
#define TF_Virtual 0x10 /* Is a virtual table */
#define TF_WithoutRowid 0x20 /* No rowid used. PRIMARY KEY is the key */
+#define TF_Recursive 0x40 /* Recursive reference within CTE */
/*
@@ -2129,6 +2130,7 @@
*/
struct Select {
ExprList *pEList; /* The fields of the result */
+ Table *pRecurse; /* Non-NULL for the recursive part of recursive CTE */
u8 op; /* One of: TK_UNION TK_ALL TK_INTERSECT TK_EXCEPT */
u16 selFlags; /* Various SF_* values */
int iLimit, iOffset; /* Memory registers holding LIMIT & OFFSET counters */
@@ -2182,6 +2184,7 @@
#define SRT_Table 8 /* Store result as data with an automatic rowid */
#define SRT_EphemTab 9 /* Create transient tab and store like SRT_Table */
#define SRT_Coroutine 10 /* Generate a single row of result */
+#define SRT_DistTable 11 /* Like SRT_TABLE, but unique results only */
/*
** An instance of this object describes where to put of the results of
@@ -2647,6 +2650,7 @@
ExprList *pCols; /* List of explicit column names, or NULL */
Select *pSelect; /* The contents of the CTE */
struct Cte *pOuterCte;
+ Table *pTab;
} a[1];
};
diff --git a/src/vdbe.c b/src/vdbe.c
index 286bc45..ffb4dd1 100644
--- a/src/vdbe.c
+++ b/src/vdbe.c
@@ -3369,6 +3369,53 @@
break;
}
+/* Opcode: OpenEphreader P1 P2 * * *
+**
+** P2 is a cursor opened by the OpenEphemeral opcode. This opcode opens
+** a new read-only cursor named P1 that accesses the same epheremal table
+** as P2.
+*/
+case OP_OpenEphreader: {
+ VdbeCursor *pEph;
+ VdbeCursor *pCx;
+ Pgno pgno;
+
+ pEph = p->apCsr[pOp->p2];
+ pCx = allocateCursor(p, pOp->p1, pEph->nField, -1, 1);
+ if( pCx==0 ) goto no_mem;
+ pCx->nullRow = 1;
+ pCx->pKeyInfo = pEph->pKeyInfo;
+ pCx->isTable = pEph->isTable;
+ pCx->isOrdered = pEph->isOrdered;
+ pgno = MASTER_ROOT + !pCx->isTable;
+ rc = sqlite3BtreeCursor(pEph->pBt, pgno, 0, pCx->pKeyInfo, pCx->pCursor);
+ break;
+}
+
+/* Opcode: SwapCursors P1 P2 * * *
+**
+** Parameters P1 and P2 are both cursors opened by the OpenEphemeral
+** opcode. This opcode deletes the contents of epheremal table P1,
+** then renames P2 to P1 and P1 to P2. In other words, following this
+** opcode cursor P2 is open on an empty table and P1 is open on the
+** table that was initially accessed by P2.
+*/
+case OP_SwapCursors: {
+ Mem tmp;
+ VdbeCursor *pTmp;
+
+ tmp = p->aMem[p->nMem - pOp->p1];
+ p->aMem[p->nMem - pOp->p1] = p->aMem[p->nMem - pOp->p2];
+ p->aMem[p->nMem - pOp->p2] = tmp;
+
+ pTmp = p->apCsr[pOp->p1];
+ p->apCsr[pOp->p1] = p->apCsr[pOp->p2];
+ p->apCsr[pOp->p2] = pTmp;
+
+ rc = sqlite3BtreeClearTable(pTmp->pBt, MASTER_ROOT + !pTmp->isTable, 0);
+ break;
+}
+
/* Opcode: SorterOpen P1 * * P4 *
**
** This opcode works like OP_OpenEphemeral except that it opens
diff --git a/src/where.c b/src/where.c
index d5444a6..8827faa 100644
--- a/src/where.c
+++ b/src/where.c
@@ -5653,7 +5653,11 @@
iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
pLoop = pLevel->pWLoop;
if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ){
- /* Do nothing */
+ if( pTab->tabFlags & TF_Recursive ){
+ int iCur = pTabItem->iCursor;
+ sqlite3VdbeAddOp2(v, OP_OpenEphreader, iCur, pTab->tnum);
+ }
+ /* Otherwise do nothing */
}else
#ifndef SQLITE_OMIT_VIRTUALTABLE
if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)!=0 ){