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 |
Timelines: | family | ancestors | descendants | both | cte-via-queue |
Files: | files | file ages | folders |
SHA1: |
b2671e1133d2f1fbd36e7cd4b86d6cc7 |
User & Date: | drh 2014-01-21 22:25:45.721 |
Context
2014-01-22
| ||
00:23 | Remove an unnecessary parameter from selectInnerLoop(). Clean up comments. (check-in: 5e6c4a55f6 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: b2671e1133 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: 5e43bf0132 user: dan tags: trunk) | |
Changes
Changes to src/select.c.
︙ | ︙ | |||
1788 1789 1790 1791 1792 1793 1794 | } rc = 1; goto multi_select_end; } #ifndef SQLITE_OMIT_CTE if( p->selFlags & SF_Recursive ){ | | | | | | | | | | | | | > | | > | > > > | | > > > | > > | | | | | | | < < < | < | | | > > > | > | | | | > | | | 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 | } rc = 1; goto multi_select_end; } #ifndef SQLITE_OMIT_CTE if( p->selFlags & SF_Recursive ){ 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 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" ); goto multi_select_end; } if( sqlite3AuthCheck(pParse, SQLITE_RECURSIVE, 0, 0, 0) ){ goto multi_select_end; } addrBreak = sqlite3VdbeMakeLabel(v); addrCont = sqlite3VdbeMakeLabel(v); /* Locate the cursor number of the Current table */ for(i=0; ALWAYS(i<pSrc->nSrc); i++){ if( pSrc->a[i].isRecursive ){ iCurrent = pSrc->a[i].iCursor; break; } } /* 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; 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 Queue. */ rc = sqlite3Select(pParse, pPrior, &destQueue); if( rc ) goto multi_select_end; /* 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, &destQueue); assert( p->pPrior==0 ); p->pPrior = pPrior; if( rc ) goto multi_select_end; /* 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. */ if( p->pOrderBy ){ return multiSelectOrderBy(pParse, p, pDest); |
︙ | ︙ |
Changes to src/shell.c.
︙ | ︙ | |||
1173 1174 1175 1176 1177 1178 1179 | ** ** * For each "Next", "Prev", "VNext" or "VPrev" instruction, indent ** 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: | | | | 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 | ** ** * For each "Next", "Prev", "VNext" or "VPrev" instruction, indent ** 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 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 */ const char *z; /* Used to check if this is an EXPLAIN */ 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", "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); if( zSql==0 ) return; for(z=zSql; *z==' ' || *z=='\t' || *z=='\n' || *z=='\f' || *z=='\r'; z++); |
︙ | ︙ | |||
1222 1223 1224 1225 1226 1227 1228 | p->aiIndent[iOp] = 0; p->nIndent = iOp+1; if( str_in_array(zOp, azNext) ){ for(i=p2op; i<iOp; i++) p->aiIndent[i] += 2; } if( str_in_array(zOp, azGoto) && p2op<p->nIndent && abYield[p2op] ){ | | | 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 | p->aiIndent[iOp] = 0; p->nIndent = iOp+1; if( str_in_array(zOp, azNext) ){ for(i=p2op; i<iOp; i++) p->aiIndent[i] += 2; } if( str_in_array(zOp, azGoto) && p2op<p->nIndent && abYield[p2op] ){ for(i=p2op+1; i<iOp; i++) p->aiIndent[i] += 2; } } p->iIndent = 0; sqlite3_free(abYield); sqlite3_reset(pSql); } |
︙ | ︙ |
Changes to src/vdbe.c.
︙ | ︙ | |||
3365 3366 3367 3368 3369 3370 3371 | pCx->isTable = 1; } } pCx->isOrdered = (pOp->p5!=BTREE_UNORDERED); break; } | < < < < < < < < < < < < < < < < < < < < < < < < < < < | 3365 3366 3367 3368 3369 3370 3371 3372 3373 3374 3375 3376 3377 3378 | pCx->isTable = 1; } } pCx->isOrdered = (pOp->p5!=BTREE_UNORDERED); 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 ** tables using an external merge-sort algorithm. */ case OP_SorterOpen: { |
︙ | ︙ | |||
4389 4390 4391 4392 4393 4394 4395 | assert( pOp->p1>=0 && pOp->p1<p->nCursor ); pC = p->apCsr[pOp->p1]; assert( pC!=0 ); pC->nullRow = 1; pC->rowidIsValid = 0; pC->cacheStatus = CACHE_STALE; | < | 4362 4363 4364 4365 4366 4367 4368 4369 4370 4371 4372 4373 4374 4375 | assert( pOp->p1>=0 && pOp->p1<p->nCursor ); pC = p->apCsr[pOp->p1]; assert( pC!=0 ); pC->nullRow = 1; pC->rowidIsValid = 0; pC->cacheStatus = CACHE_STALE; if( pC->pCursor ){ sqlite3BtreeClearCursor(pC->pCursor); } break; } /* Opcode: Last P1 P2 * * * |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
3406 3407 3408 3409 3410 3411 3412 | { /* Case 6: There is no usable index. We must do a complete ** 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 ); | > > > | | | | > | 3406 3407 3408 3409 3410 3411 3412 3413 3414 3415 3416 3417 3418 3419 3420 3421 3422 3423 3424 3425 3426 3427 | { /* Case 6: There is no usable index. We must do a complete ** 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 ); 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. */ for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){ Expr *pE; |
︙ | ︙ |