Index: src/select.c ================================================================== --- src/select.c +++ src/select.c @@ -1790,24 +1790,25 @@ goto multi_select_end; } #ifndef SQLITE_OMIT_CTE if( p->selFlags & SF_Recursive ){ - SrcList *pSrc = p->pSrc; - int nCol = p->pEList->nExpr; - int addrNext; - int addrSwap; - int iCont, iBreak; - int tmp1; /* Intermediate table */ - int tmp2; /* Next intermediate table */ - int tmp3 = 0; /* To ensure unique results if UNION */ - int eDest = SRT_Table; - SelectDest tmp2dest; - int i; + SrcList *pSrc = p->pSrc; /* The FROM clause of the recursive query */ + int nCol = p->pEList->nExpr; /* Number of columns in the CTE */ + int addrTop; /* Top of the loop */ + int addrCont, addrBreak; /* CONTINUE and BREAK addresses */ + int iCurrent; /* The Current table */ + int regCurrent; /* Register holding Current table */ + int iQueue; /* The Queue table */ + int iDistinct; /* To ensure unique results if UNION */ + int eDest; /* How to write to Queue */ + SelectDest destQueue; /* SelectDest targetting the Queue table */ + int i; /* Loop counter */ /* Check that there is no ORDER BY or LIMIT clause. Neither of these - ** are supported on recursive queries. */ + ** are currently supported on recursive queries. + */ assert( p->pOffset==0 || p->pLimit ); if( p->pOrderBy || p->pLimit ){ sqlite3ErrorMsg(pParse, "%s in a recursive query", p->pOrderBy ? "ORDER BY" : "LIMIT" ); @@ -1815,60 +1816,70 @@ } if( sqlite3AuthCheck(pParse, SQLITE_RECURSIVE, 0, 0, 0) ){ goto multi_select_end; } - iBreak = sqlite3VdbeMakeLabel(v); - iCont = sqlite3VdbeMakeLabel(v); + addrBreak = sqlite3VdbeMakeLabel(v); + addrCont = sqlite3VdbeMakeLabel(v); + /* Locate the cursor number of the Current table */ for(i=0; ALWAYS(inSrc); i++){ if( pSrc->a[i].isRecursive ){ - tmp1 = pSrc->a[i].iCursor; + iCurrent = pSrc->a[i].iCursor; break; } } - tmp2 = pParse->nTab++; + /* Allocate cursors for Queue and Distinct. The cursor number for + ** the Distinct table must be exactly one greater than Queue in order + ** for the SRT_DistTable destination to work. */ + iQueue = 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); + iDistinct = pParse->nTab++; + }else{ + eDest = SRT_Table; + iDistinct = 0; + } + sqlite3SelectDestInit(&destQueue, eDest, iQueue); + + /* Allocate cursors for Current, Queue, and iDistinct. */ + regCurrent = ++pParse->nMem; + sqlite3VdbeAddOp3(v, OP_OpenPseudo, iCurrent, regCurrent, nCol); + sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iQueue, nCol); + if( iDistinct ){ + p->addrOpenEphm[0] = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iDistinct, 0); p->selFlags |= SF_UsesEphemeral; } - /* Store the results of the initial SELECT in tmp2. */ - rc = sqlite3Select(pParse, pPrior, &tmp2dest); + /* Store the results of the initial SELECT in Queue. */ + rc = sqlite3Select(pParse, pPrior, &destQueue); if( rc ) goto multi_select_end; - /* Clear tmp1. Then switch the contents of tmp1 and tmp2. Then return - ** 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. */ + /* Find the next row in the Queue and output that row */ + addrTop = sqlite3VdbeAddOp2(v, OP_Rewind, iQueue, addrBreak); + selectInnerLoop(pParse, p, p->pEList, iQueue, p->pEList->nExpr, + 0, 0, &dest, addrCont, addrBreak); + sqlite3VdbeResolveLabel(v, addrCont); + + /* Transfer the next row in Queue over to Current */ + sqlite3VdbeAddOp1(v, OP_NullRow, iCurrent); /* To reset column cache */ + sqlite3VdbeAddOp2(v, OP_RowData, iQueue, regCurrent); + sqlite3VdbeAddOp1(v, OP_Delete, iQueue); + + /* Execute the recursive SELECT taking the single row in Current as + ** the value for the CTE. Store the results in the Queue. + */ p->pPrior = 0; - rc = sqlite3Select(pParse, p, &tmp2dest); + rc = sqlite3Select(pParse, p, &destQueue); assert( p->pPrior==0 ); p->pPrior = pPrior; if( rc ) goto multi_select_end; - sqlite3VdbeAddOp2(v, OP_Goto, 0, addrSwap); - sqlite3VdbeResolveLabel(v, iBreak); + /* Keep running the loop until the Queue is empty */ + sqlite3VdbeAddOp2(v, OP_Goto, 0, addrTop); + sqlite3VdbeResolveLabel(v, addrBreak); }else #endif /* Compound SELECTs that have an ORDER BY clause are handled separately. */ Index: src/shell.c ================================================================== --- src/shell.c +++ src/shell.c @@ -1175,11 +1175,11 @@ ** all opcodes that occur between the p2 jump destination and the opcode ** itself by 2 spaces. ** ** * For each "Goto", if the jump destination is earlier in the program ** and ends on one of: -** Yield SeekGt SeekLt RowSetRead +** Yield SeekGt SeekLt RowSetRead Rewind ** then indent all opcodes between the earlier instruction ** and "Goto" by 2 spaces. */ static void explain_data_prepare(struct callback_data *p, sqlite3_stmt *pSql){ const char *zSql; /* The text of the SQL statement */ @@ -1187,11 +1187,11 @@ int *abYield = 0; /* True if op is an OP_Yield */ int nAlloc = 0; /* Allocated size of p->aiIndent[], abYield */ int iOp; /* Index of operation in p->aiIndent[] */ const char *azNext[] = { "Next", "Prev", "VPrev", "VNext", "SorterNext", 0 }; - const char *azYield[] = { "Yield", "SeekLt", "SeekGt", "RowSetRead", 0 }; + const char *azYield[] = { "Yield", "SeekLt", "SeekGt", "RowSetRead", "Rewind", 0 }; const char *azGoto[] = { "Goto", 0 }; /* Try to figure out if this is really an EXPLAIN statement. If this ** cannot be verified, return early. */ zSql = sqlite3_sql(pSql); @@ -1224,11 +1224,11 @@ if( str_in_array(zOp, azNext) ){ for(i=p2op; iaiIndent[i] += 2; } if( str_in_array(zOp, azGoto) && p2opnIndent && abYield[p2op] ){ - for(i=p2op; iaiIndent[i] += 2; + for(i=p2op+1; iaiIndent[i] += 2; } } p->iIndent = 0; sqlite3_free(abYield); Index: src/vdbe.c ================================================================== --- src/vdbe.c +++ src/vdbe.c @@ -3367,37 +3367,10 @@ } pCx->isOrdered = (pOp->p5!=BTREE_UNORDERED); break; } -#ifndef SQLITE_OMIT_CTE -/* 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; - - assert( pTmp->isTable ); - rc = sqlite3BtreeClearTable(pTmp->pBt, MASTER_ROOT, 0); - break; -} -#endif /* ifndef SQLITE_OMIT_CTE */ - /* Opcode: SorterOpen P1 * * P4 * ** ** This opcode works like OP_OpenEphemeral except that it opens ** a transient index that is specifically designed to sort large ** tables using an external merge-sort algorithm. @@ -4391,11 +4364,10 @@ pC = p->apCsr[pOp->p1]; assert( pC!=0 ); pC->nullRow = 1; pC->rowidIsValid = 0; pC->cacheStatus = CACHE_STALE; - assert( pC->pCursor || pC->pVtabCursor ); if( pC->pCursor ){ sqlite3BtreeClearCursor(pC->pCursor); } break; } Index: src/where.c ================================================================== --- src/where.c +++ src/where.c @@ -3408,14 +3408,18 @@ ** scan of the entire table. */ static const u8 aStep[] = { OP_Next, OP_Prev }; static const u8 aStart[] = { OP_Rewind, OP_Last }; assert( bRev==0 || bRev==1 ); - pLevel->op = aStep[bRev]; - pLevel->p1 = iCur; - pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk); - pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP; + if( pTabItem->isRecursive ){ + pLevel->op = OP_Noop; + }else{ + pLevel->op = aStep[bRev]; + pLevel->p1 = iCur; + pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk); + pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP; + } } /* Insert code to test every subexpression that can be completely ** computed using the current set of tables. */