/ Check-in [b2671e11]
Login

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: b2671e1133d2f1fbd36e7cd4b86d6cc7b528aa97
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
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

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         -    pLevel->op = aStep[bRev];
  3414         -    pLevel->p1 = iCur;
  3415         -    pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk);
  3416         -    pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
         3413  +    if( pTabItem->isRecursive ){
         3414  +      pLevel->op = OP_Noop;
         3415  +    }else{
         3416  +      pLevel->op = aStep[bRev];
         3417  +      pLevel->p1 = iCur;
         3418  +      pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk);
         3419  +      pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
         3420  +    }
  3417   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;