Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Change the recursive common table expression algorithm to use a queue instead of a pair of tables. Runs about 25% faster on the sudoku solver query. The OP_SwapCursors opcode is no longer required. The current implementation uses just a fifo, but the plan is to change it into a queue that will support ORDER BY and LIMIT in a recursive query. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | cte-via-queue |
| Files: | files | file ages | folders |
| SHA1: |
b2671e1133d2f1fbd36e7cd4b86d6cc7 |
| User & Date: | drh 2014-01-21 22:25:45 |
Context
|
2014-01-22
| ||
| 00:23 | Remove an unnecessary parameter from selectInnerLoop(). Clean up comments. (check-in: 5e6c4a55 user: drh tags: cte-via-queue) | |
|
2014-01-21
| ||
| 22:25 | Change the recursive common table expression algorithm to use a queue instead of a pair of tables. Runs about 25% faster on the sudoku solver query. The OP_SwapCursors opcode is no longer required. The current implementation uses just a fifo, but the plan is to change it into a queue that will support ORDER BY and LIMIT in a recursive query. (check-in: b2671e11 user: drh tags: cte-via-queue) | |
| 15:04 | Remove the undocumented requirement for applications that use an SQLITE_ENABLE_SQLLOG build to define a sqlite3_init_sqllog() function. (check-in: 5e43bf01 user: dan tags: trunk) | |
Changes
Changes to src/select.c.
1788 1788 } 1789 1789 rc = 1; 1790 1790 goto multi_select_end; 1791 1791 } 1792 1792 1793 1793 #ifndef SQLITE_OMIT_CTE 1794 1794 if( p->selFlags & SF_Recursive ){ 1795 - SrcList *pSrc = p->pSrc; 1796 - int nCol = p->pEList->nExpr; 1797 - int addrNext; 1798 - int addrSwap; 1799 - int iCont, iBreak; 1800 - int tmp1; /* Intermediate table */ 1801 - int tmp2; /* Next intermediate table */ 1802 - int tmp3 = 0; /* To ensure unique results if UNION */ 1803 - int eDest = SRT_Table; 1804 - SelectDest tmp2dest; 1805 - int i; 1795 + SrcList *pSrc = p->pSrc; /* The FROM clause of the recursive query */ 1796 + int nCol = p->pEList->nExpr; /* Number of columns in the CTE */ 1797 + int addrTop; /* Top of the loop */ 1798 + int addrCont, addrBreak; /* CONTINUE and BREAK addresses */ 1799 + int iCurrent; /* The Current table */ 1800 + int regCurrent; /* Register holding Current table */ 1801 + int iQueue; /* The Queue table */ 1802 + int iDistinct; /* To ensure unique results if UNION */ 1803 + int eDest; /* How to write to Queue */ 1804 + SelectDest destQueue; /* SelectDest targetting the Queue table */ 1805 + int i; /* Loop counter */ 1806 1806 1807 1807 /* Check that there is no ORDER BY or LIMIT clause. Neither of these 1808 - ** are supported on recursive queries. */ 1808 + ** are currently supported on recursive queries. 1809 + */ 1809 1810 assert( p->pOffset==0 || p->pLimit ); 1810 1811 if( p->pOrderBy || p->pLimit ){ 1811 1812 sqlite3ErrorMsg(pParse, "%s in a recursive query", 1812 1813 p->pOrderBy ? "ORDER BY" : "LIMIT" 1813 1814 ); 1814 1815 goto multi_select_end; 1815 1816 } 1816 1817 1817 1818 if( sqlite3AuthCheck(pParse, SQLITE_RECURSIVE, 0, 0, 0) ){ 1818 1819 goto multi_select_end; 1819 1820 } 1820 - iBreak = sqlite3VdbeMakeLabel(v); 1821 - iCont = sqlite3VdbeMakeLabel(v); 1821 + addrBreak = sqlite3VdbeMakeLabel(v); 1822 + addrCont = sqlite3VdbeMakeLabel(v); 1822 1823 1824 + /* Locate the cursor number of the Current table */ 1823 1825 for(i=0; ALWAYS(i<pSrc->nSrc); i++){ 1824 1826 if( pSrc->a[i].isRecursive ){ 1825 - tmp1 = pSrc->a[i].iCursor; 1827 + iCurrent = pSrc->a[i].iCursor; 1826 1828 break; 1827 1829 } 1828 1830 } 1829 1831 1830 - tmp2 = pParse->nTab++; 1832 + /* Allocate cursors for Queue and Distinct. The cursor number for 1833 + ** the Distinct table must be exactly one greater than Queue in order 1834 + ** for the SRT_DistTable destination to work. */ 1835 + iQueue = pParse->nTab++; 1831 1836 if( p->op==TK_UNION ){ 1832 1837 eDest = SRT_DistTable; 1833 - tmp3 = pParse->nTab++; 1838 + iDistinct = pParse->nTab++; 1839 + }else{ 1840 + eDest = SRT_Table; 1841 + iDistinct = 0; 1834 1842 } 1835 - sqlite3SelectDestInit(&tmp2dest, eDest, tmp2); 1843 + sqlite3SelectDestInit(&destQueue, eDest, iQueue); 1836 1844 1837 - sqlite3VdbeAddOp2(v, OP_OpenEphemeral, tmp1, nCol); 1838 - sqlite3VdbeAddOp2(v, OP_OpenEphemeral, tmp2, nCol); 1839 - if( tmp3 ){ 1840 - p->addrOpenEphm[0] = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, tmp3, 0); 1845 + /* Allocate cursors for Current, Queue, and iDistinct. */ 1846 + regCurrent = ++pParse->nMem; 1847 + sqlite3VdbeAddOp3(v, OP_OpenPseudo, iCurrent, regCurrent, nCol); 1848 + sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iQueue, nCol); 1849 + if( iDistinct ){ 1850 + p->addrOpenEphm[0] = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iDistinct, 0); 1841 1851 p->selFlags |= SF_UsesEphemeral; 1842 1852 } 1843 1853 1844 - /* Store the results of the initial SELECT in tmp2. */ 1845 - rc = sqlite3Select(pParse, pPrior, &tmp2dest); 1854 + /* Store the results of the initial SELECT in Queue. */ 1855 + rc = sqlite3Select(pParse, pPrior, &destQueue); 1846 1856 if( rc ) goto multi_select_end; 1847 1857 1848 - /* Clear tmp1. Then switch the contents of tmp1 and tmp2. Then return 1849 - ** the contents of tmp1 to the caller. Or, if tmp1 is empty at this 1850 - ** point, the recursive query has finished - jump to address iBreak. */ 1851 - addrSwap = sqlite3VdbeAddOp2(v, OP_SwapCursors, tmp1, tmp2); 1852 - sqlite3VdbeAddOp2(v, OP_Rewind, tmp1, iBreak); 1853 - addrNext = sqlite3VdbeCurrentAddr(v); 1854 - selectInnerLoop(pParse, p, p->pEList, tmp1, p->pEList->nExpr, 1855 - 0, 0, &dest, iCont, iBreak); 1856 - sqlite3VdbeResolveLabel(v, iCont); 1857 - sqlite3VdbeAddOp2(v, OP_Next, tmp1, addrNext); 1858 + /* Find the next row in the Queue and output that row */ 1859 + addrTop = sqlite3VdbeAddOp2(v, OP_Rewind, iQueue, addrBreak); 1860 + selectInnerLoop(pParse, p, p->pEList, iQueue, p->pEList->nExpr, 1861 + 0, 0, &dest, addrCont, addrBreak); 1862 + sqlite3VdbeResolveLabel(v, addrCont); 1858 1863 1859 - /* Execute the recursive SELECT. Store the results in tmp2. While this 1860 - ** SELECT is running, the contents of tmp1 are read by recursive 1861 - ** references to the current CTE. */ 1864 + /* Transfer the next row in Queue over to Current */ 1865 + sqlite3VdbeAddOp1(v, OP_NullRow, iCurrent); /* To reset column cache */ 1866 + sqlite3VdbeAddOp2(v, OP_RowData, iQueue, regCurrent); 1867 + sqlite3VdbeAddOp1(v, OP_Delete, iQueue); 1868 + 1869 + /* Execute the recursive SELECT taking the single row in Current as 1870 + ** the value for the CTE. Store the results in the Queue. 1871 + */ 1862 1872 p->pPrior = 0; 1863 - rc = sqlite3Select(pParse, p, &tmp2dest); 1873 + rc = sqlite3Select(pParse, p, &destQueue); 1864 1874 assert( p->pPrior==0 ); 1865 1875 p->pPrior = pPrior; 1866 1876 if( rc ) goto multi_select_end; 1867 1877 1868 - sqlite3VdbeAddOp2(v, OP_Goto, 0, addrSwap); 1869 - sqlite3VdbeResolveLabel(v, iBreak); 1878 + /* Keep running the loop until the Queue is empty */ 1879 + sqlite3VdbeAddOp2(v, OP_Goto, 0, addrTop); 1880 + sqlite3VdbeResolveLabel(v, addrBreak); 1870 1881 }else 1871 1882 #endif 1872 1883 1873 1884 /* Compound SELECTs that have an ORDER BY clause are handled separately. 1874 1885 */ 1875 1886 if( p->pOrderBy ){ 1876 1887 return multiSelectOrderBy(pParse, p, pDest);
Changes to src/shell.c.
1173 1173 ** 1174 1174 ** * For each "Next", "Prev", "VNext" or "VPrev" instruction, indent 1175 1175 ** all opcodes that occur between the p2 jump destination and the opcode 1176 1176 ** itself by 2 spaces. 1177 1177 ** 1178 1178 ** * For each "Goto", if the jump destination is earlier in the program 1179 1179 ** and ends on one of: 1180 -** Yield SeekGt SeekLt RowSetRead 1180 +** Yield SeekGt SeekLt RowSetRead Rewind 1181 1181 ** then indent all opcodes between the earlier instruction 1182 1182 ** and "Goto" by 2 spaces. 1183 1183 */ 1184 1184 static void explain_data_prepare(struct callback_data *p, sqlite3_stmt *pSql){ 1185 1185 const char *zSql; /* The text of the SQL statement */ 1186 1186 const char *z; /* Used to check if this is an EXPLAIN */ 1187 1187 int *abYield = 0; /* True if op is an OP_Yield */ 1188 1188 int nAlloc = 0; /* Allocated size of p->aiIndent[], abYield */ 1189 1189 int iOp; /* Index of operation in p->aiIndent[] */ 1190 1190 1191 1191 const char *azNext[] = { "Next", "Prev", "VPrev", "VNext", "SorterNext", 0 }; 1192 - const char *azYield[] = { "Yield", "SeekLt", "SeekGt", "RowSetRead", 0 }; 1192 + const char *azYield[] = { "Yield", "SeekLt", "SeekGt", "RowSetRead", "Rewind", 0 }; 1193 1193 const char *azGoto[] = { "Goto", 0 }; 1194 1194 1195 1195 /* Try to figure out if this is really an EXPLAIN statement. If this 1196 1196 ** cannot be verified, return early. */ 1197 1197 zSql = sqlite3_sql(pSql); 1198 1198 if( zSql==0 ) return; 1199 1199 for(z=zSql; *z==' ' || *z=='\t' || *z=='\n' || *z=='\f' || *z=='\r'; z++); ................................................................................ 1222 1222 p->aiIndent[iOp] = 0; 1223 1223 p->nIndent = iOp+1; 1224 1224 1225 1225 if( str_in_array(zOp, azNext) ){ 1226 1226 for(i=p2op; i<iOp; i++) p->aiIndent[i] += 2; 1227 1227 } 1228 1228 if( str_in_array(zOp, azGoto) && p2op<p->nIndent && abYield[p2op] ){ 1229 - for(i=p2op; i<iOp; i++) p->aiIndent[i] += 2; 1229 + for(i=p2op+1; i<iOp; i++) p->aiIndent[i] += 2; 1230 1230 } 1231 1231 } 1232 1232 1233 1233 p->iIndent = 0; 1234 1234 sqlite3_free(abYield); 1235 1235 sqlite3_reset(pSql); 1236 1236 }
Changes to src/vdbe.c.
3365 3365 pCx->isTable = 1; 3366 3366 } 3367 3367 } 3368 3368 pCx->isOrdered = (pOp->p5!=BTREE_UNORDERED); 3369 3369 break; 3370 3370 } 3371 3371 3372 -#ifndef SQLITE_OMIT_CTE 3373 -/* Opcode: SwapCursors P1 P2 * * * 3374 -** 3375 -** Parameters P1 and P2 are both cursors opened by the OpenEphemeral 3376 -** opcode. This opcode deletes the contents of epheremal table P1, 3377 -** then renames P2 to P1 and P1 to P2. In other words, following this 3378 -** opcode cursor P2 is open on an empty table and P1 is open on the 3379 -** table that was initially accessed by P2. 3380 -*/ 3381 -case OP_SwapCursors: { 3382 - Mem tmp; 3383 - VdbeCursor *pTmp; 3384 - 3385 - tmp = p->aMem[p->nMem - pOp->p1]; 3386 - p->aMem[p->nMem - pOp->p1] = p->aMem[p->nMem - pOp->p2]; 3387 - p->aMem[p->nMem - pOp->p2] = tmp; 3388 - 3389 - pTmp = p->apCsr[pOp->p1]; 3390 - p->apCsr[pOp->p1] = p->apCsr[pOp->p2]; 3391 - p->apCsr[pOp->p2] = pTmp; 3392 - 3393 - assert( pTmp->isTable ); 3394 - rc = sqlite3BtreeClearTable(pTmp->pBt, MASTER_ROOT, 0); 3395 - break; 3396 -} 3397 -#endif /* ifndef SQLITE_OMIT_CTE */ 3398 - 3399 3372 /* Opcode: SorterOpen P1 * * P4 * 3400 3373 ** 3401 3374 ** This opcode works like OP_OpenEphemeral except that it opens 3402 3375 ** a transient index that is specifically designed to sort large 3403 3376 ** tables using an external merge-sort algorithm. 3404 3377 */ 3405 3378 case OP_SorterOpen: { ................................................................................ 4389 4362 4390 4363 assert( pOp->p1>=0 && pOp->p1<p->nCursor ); 4391 4364 pC = p->apCsr[pOp->p1]; 4392 4365 assert( pC!=0 ); 4393 4366 pC->nullRow = 1; 4394 4367 pC->rowidIsValid = 0; 4395 4368 pC->cacheStatus = CACHE_STALE; 4396 - assert( pC->pCursor || pC->pVtabCursor ); 4397 4369 if( pC->pCursor ){ 4398 4370 sqlite3BtreeClearCursor(pC->pCursor); 4399 4371 } 4400 4372 break; 4401 4373 } 4402 4374 4403 4375 /* Opcode: Last P1 P2 * * *
Changes to src/where.c.
3406 3406 { 3407 3407 /* Case 6: There is no usable index. We must do a complete 3408 3408 ** scan of the entire table. 3409 3409 */ 3410 3410 static const u8 aStep[] = { OP_Next, OP_Prev }; 3411 3411 static const u8 aStart[] = { OP_Rewind, OP_Last }; 3412 3412 assert( bRev==0 || bRev==1 ); 3413 + if( pTabItem->isRecursive ){ 3414 + pLevel->op = OP_Noop; 3415 + }else{ 3413 3416 pLevel->op = aStep[bRev]; 3414 3417 pLevel->p1 = iCur; 3415 3418 pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk); 3416 3419 pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP; 3417 3420 } 3421 + } 3418 3422 3419 3423 /* Insert code to test every subexpression that can be completely 3420 3424 ** computed using the current set of tables. 3421 3425 */ 3422 3426 for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){ 3423 3427 Expr *pE; 3424 3428 testcase( pTerm->wtFlags & TERM_VIRTUAL );