Index: src/btree.c ================================================================== --- src/btree.c +++ src/btree.c @@ -7348,18 +7348,20 @@ ){ MemPage *pPage; int rc; unsigned char *pCell; int i; + int hdr; assert( sqlite3_mutex_held(pBt->mutex) ); if( pgno>btreePagecount(pBt) ){ return SQLITE_CORRUPT_BKPT; } rc = getAndInitPage(pBt, pgno, &pPage, 0); if( rc ) return rc; + hdr = pPage->hdrOffset; for(i=0; inCell; i++){ pCell = findCell(pPage, i); if( !pPage->leaf ){ rc = clearDatabasePage(pBt, get4byte(pCell), 1, pnChange); if( rc ) goto cleardatabasepage_out; @@ -7366,20 +7368,20 @@ } rc = clearCell(pPage, pCell); 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 ); *pnChange += pPage->nCell; } 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: releasePage(pPage); return rc; Index: src/expr.c ================================================================== --- src/expr.c +++ src/expr.c @@ -1053,10 +1053,11 @@ pNew->pRightmost = 0; pNew->addrOpenEphm[0] = -1; pNew->addrOpenEphm[1] = -1; pNew->addrOpenEphm[2] = -1; pNew->pWith = withDup(db, p->pWith); + pNew->pRecurse = p->pRecurse; return pNew; } #else Select *sqlite3SelectDup(sqlite3 *db, Select *p, int flags){ assert( p==0 ); Index: src/select.c ================================================================== --- src/select.c +++ src/select.c @@ -689,16 +689,30 @@ } #endif /* 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{ int r2 = sqlite3GetTempReg(pParse); sqlite3VdbeAddOp2(v, OP_NewRowid, iParm, r2); @@ -1727,10 +1741,11 @@ /* Make sure there is no ORDER BY or LIMIT clause on prior SELECTs. Only ** 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 ); assert( pPrior->pRightmost==p->pRightmost ); dest = *pDest; @@ -1771,16 +1786,86 @@ " do not have the same number of result columns", selectOpName(p->op)); } rc = 1; 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 ){ case TK_ALL: { @@ -3447,10 +3532,77 @@ assert( pParse->pCte==pCte ); pParse->pCte = pCte->pOuterCte; } } +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. ** "Expanding" means to do the following: ** @@ -3513,35 +3665,26 @@ return WRC_Prune; } #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; #endif }else{ @@ -3829,13 +3972,14 @@ for(i=0, pFrom=pTabList->a; inSrc; i++, pFrom++){ Table *pTab = pFrom->pTab; 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); + } } } } return WRC_Continue; } Index: src/sqliteInt.h ================================================================== --- src/sqliteInt.h +++ src/sqliteInt.h @@ -1427,18 +1427,19 @@ Schema *pSchema; /* Schema that contains this table */ Table *pNextZombie; /* Next on the Parse.pZombieTab list */ }; /* -** 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 */ #define TF_HasPrimaryKey 0x04 /* Table has a primary key */ #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 */ /* ** Test to see whether or not a table is a virtual table. This is ** done as a macro so that it will be optimized out when virtual @@ -2127,10 +2128,11 @@ ** for the result set. The KeyInfo for addrOpenEphm[2] contains collating ** sequences for the ORDER BY clause. */ 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 */ int addrOpenEphm[3]; /* OP_OpenEphem opcodes related to this select */ u64 nSelectRow; /* Estimated number of result rows */ @@ -2180,10 +2182,11 @@ #define SRT_Mem 6 /* Store result in a memory cell */ #define SRT_Set 7 /* Store results as keys in an index */ #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 ** a SELECT statement. */ @@ -2645,10 +2648,11 @@ struct Cte { char *zName; /* Name of this CTE */ ExprList *pCols; /* List of explicit column names, or NULL */ Select *pSelect; /* The contents of the CTE */ struct Cte *pOuterCte; + Table *pTab; } a[1]; }; /* ** Assuming zIn points to the first byte of a UTF-8 character, Index: src/vdbe.c ================================================================== --- src/vdbe.c +++ src/vdbe.c @@ -3366,10 +3366,57 @@ } } pCx->isOrdered = (pOp->p5!=BTREE_UNORDERED); 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 ** a transient index that is specifically designed to sort large Index: src/where.c ================================================================== --- src/where.c +++ src/where.c @@ -5651,11 +5651,15 @@ pTabItem = &pTabList->a[pLevel->iFrom]; pTab = pTabItem->pTab; 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 ){ const char *pVTab = (const char *)sqlite3GetVTable(db, pTab); int iCur = pTabItem->iCursor; Index: test/with1.test ================================================================== --- test/with1.test +++ test/with1.test @@ -134,10 +134,37 @@ do_execsql_test 4.3 { WITH uset(a, b) AS ( SELECT 2, 8 UNION ALL SELECT 4, 9 ) UPDATE t1 SET x = COALESCE( (SELECT b FROM uset WHERE a=x), x ); SELECT * FROM t1; } {1 3 8 9} + +#------------------------------------------------------------------------- +# +do_execsql_test 5.1 { + WITH i(x) AS ( VALUES(1) UNION ALL SELECT x+1 FROM i) + SELECT x FROM i LIMIT 10; +} {1 2 3 4 5 6 7 8 9 10} + +do_catchsql_test 5.2 { + WITH i(x) AS ( VALUES(1) UNION ALL SELECT x+1 FROM i ORDER BY 1) + SELECT x FROM i LIMIT 10; +} {1 {ORDER BY in a recursive query is not allowed}} + +do_catchsql_test 5.3 { + WITH i(x) AS ( VALUES(1) UNION ALL SELECT x+1 FROM i LIMIT 10 ) + SELECT x FROM i LIMIT 10; +} {1 {LIMIT in a recursive query is not allowed}} + +do_execsql_test 5.4 { + WITH i(x) AS ( VALUES(1) UNION ALL SELECT (x+1)%10 FROM i) + SELECT x FROM i LIMIT 20; +} {1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0} + +do_execsql_test 5.5 { + WITH i(x) AS ( VALUES(1) UNION SELECT (x+1)%10 FROM i) + SELECT x FROM i LIMIT 20; +} {1 2 3 4 5 6 7 8 9 0} finish_test