/ Check-in [b6cea420]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Change the WITH RECURSIVE implementation to use a queue instead of a pair of tables. Add support for ORDER BY, LIMIT, and OFFSET on recursive queries.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: b6cea42006910d590373e8f9e296d7672edb114b
User & Date: drh 2014-01-22 18:16:27
Context
2014-01-22
18:31
Fix harmless compiler warnings. check-in: dea2ca6a user: drh tags: trunk
18:16
Change the WITH RECURSIVE implementation to use a queue instead of a pair of tables. Add support for ORDER BY, LIMIT, and OFFSET on recursive queries. check-in: b6cea420 user: drh tags: trunk
18:07
Add support for LIMIT and OFFSET in a recursive query. Closed-Leaf check-in: 1945484e user: drh tags: cte-via-queue
17:43
Update the spellfix virtual table to optimize queries of the form "SELECT ... FROM tbl WHERE rowid=?". check-in: a0ba55ff user: dan tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/select.c.

   458    458   }
   459    459   
   460    460   /*
   461    461   ** Add code to implement the OFFSET
   462    462   */
   463    463   static void codeOffset(
   464    464     Vdbe *v,          /* Generate code into this VM */
   465         -  Select *p,        /* The SELECT statement being coded */
          465  +  int iOffset,      /* Register holding the offset counter */
   466    466     int iContinue     /* Jump here to skip the current record */
   467    467   ){
   468         -  if( p->iOffset && iContinue!=0 ){
          468  +  if( iOffset>0 && iContinue!=0 ){
   469    469       int addr;
   470         -    sqlite3VdbeAddOp2(v, OP_AddImm, p->iOffset, -1);
   471         -    addr = sqlite3VdbeAddOp1(v, OP_IfNeg, p->iOffset);
          470  +    sqlite3VdbeAddOp2(v, OP_AddImm, iOffset, -1);
          471  +    addr = sqlite3VdbeAddOp1(v, OP_IfNeg, iOffset);
   472    472       sqlite3VdbeAddOp2(v, OP_Goto, 0, iContinue);
   473    473       VdbeComment((v, "skip OFFSET records"));
   474    474       sqlite3VdbeJumpHere(v, addr);
   475    475     }
   476    476   }
   477    477   
   478    478   /*
................................................................................
   539    539     int addrTnct;   /* Address of OP_OpenEphemeral opcode for tabTnct */
   540    540   };
   541    541   
   542    542   /*
   543    543   ** This routine generates the code for the inside of the inner loop
   544    544   ** of a SELECT.
   545    545   **
   546         -** If srcTab and nColumn are both zero, then the pEList expressions
   547         -** are evaluated in order to get the data for this row.  If nColumn>0
   548         -** then data is pulled from srcTab and pEList is used only to get the
   549         -** datatypes for each column.
          546  +** If srcTab is negative, then the pEList expressions
          547  +** are evaluated in order to get the data for this row.  If srcTab is
          548  +** zero or more, then data is pulled from srcTab and pEList is used only 
          549  +** to get number columns and the datatype for each column.
   550    550   */
   551    551   static void selectInnerLoop(
   552    552     Parse *pParse,          /* The parser context */
   553    553     Select *p,              /* The complete select statement being coded */
   554    554     ExprList *pEList,       /* List of values being extracted */
   555    555     int srcTab,             /* Pull data from this table */
   556         -  int nColumn,            /* Number of columns in the source table */
   557    556     ExprList *pOrderBy,     /* If not NULL, sort results using this key */
   558    557     DistinctCtx *pDistinct, /* If not NULL, info on how to process DISTINCT */
   559    558     SelectDest *pDest,      /* How to dispose of the results */
   560    559     int iContinue,          /* Jump here to continue with next row */
   561    560     int iBreak              /* Jump here to break out of the inner loop */
   562    561   ){
   563    562     Vdbe *v = pParse->pVdbe;
................................................................................
   565    564     int hasDistinct;        /* True if the DISTINCT keyword is present */
   566    565     int regResult;              /* Start of memory holding result set */
   567    566     int eDest = pDest->eDest;   /* How to dispose of results */
   568    567     int iParm = pDest->iSDParm; /* First argument to disposal method */
   569    568     int nResultCol;             /* Number of result columns */
   570    569   
   571    570     assert( v );
   572         -  if( NEVER(v==0) ) return;
   573    571     assert( pEList!=0 );
   574    572     hasDistinct = pDistinct ? pDistinct->eTnctType : WHERE_DISTINCT_NOOP;
   575    573     if( pOrderBy==0 && !hasDistinct ){
   576         -    codeOffset(v, p, iContinue);
          574  +    codeOffset(v, p->iOffset, iContinue);
   577    575     }
   578    576   
   579    577     /* Pull the requested columns.
   580    578     */
   581         -  if( nColumn>0 ){
   582         -    nResultCol = nColumn;
   583         -  }else{
   584         -    nResultCol = pEList->nExpr;
   585         -  }
          579  +  nResultCol = pEList->nExpr;
   586    580     if( pDest->iSdst==0 ){
   587    581       pDest->iSdst = pParse->nMem+1;
   588    582       pDest->nSdst = nResultCol;
   589    583       pParse->nMem += nResultCol;
   590    584     }else{ 
   591    585       assert( pDest->nSdst==nResultCol );
   592    586     }
   593    587     regResult = pDest->iSdst;
   594         -  if( nColumn>0 ){
   595         -    for(i=0; i<nColumn; i++){
          588  +  if( srcTab>=0 ){
          589  +    for(i=0; i<nResultCol; i++){
   596    590         sqlite3VdbeAddOp3(v, OP_Column, srcTab, i, regResult+i);
          591  +      VdbeComment((v, "%s", pEList->a[i].zName));
   597    592       }
   598    593     }else if( eDest!=SRT_Exists ){
   599    594       /* If the destination is an EXISTS(...) expression, the actual
   600    595       ** values returned by the SELECT are not required.
   601    596       */
   602    597       sqlite3ExprCodeExprList(pParse, pEList, regResult,
   603    598                               (eDest==SRT_Output)?SQLITE_ECEL_DUP:0);
   604    599     }
   605         -  nColumn = nResultCol;
   606    600   
   607    601     /* If the DISTINCT keyword was present on the SELECT statement
   608    602     ** and this row has been seen before, then do not make this row
   609    603     ** part of the result.
   610    604     */
   611    605     if( hasDistinct ){
   612         -    assert( pEList!=0 );
   613         -    assert( pEList->nExpr==nColumn );
   614    606       switch( pDistinct->eTnctType ){
   615    607         case WHERE_DISTINCT_ORDERED: {
   616    608           VdbeOp *pOp;            /* No longer required OpenEphemeral instr. */
   617    609           int iJump;              /* Jump destination */
   618    610           int regPrev;            /* Previous row content */
   619    611   
   620    612           /* Allocate space for the previous row */
   621    613           regPrev = pParse->nMem+1;
   622         -        pParse->nMem += nColumn;
          614  +        pParse->nMem += nResultCol;
   623    615   
   624    616           /* Change the OP_OpenEphemeral coded earlier to an OP_Null
   625    617           ** sets the MEM_Cleared bit on the first register of the
   626    618           ** previous value.  This will cause the OP_Ne below to always
   627    619           ** fail on the first iteration of the loop even if the first
   628    620           ** row is all NULLs.
   629    621           */
   630    622           sqlite3VdbeChangeToNoop(v, pDistinct->addrTnct);
   631    623           pOp = sqlite3VdbeGetOp(v, pDistinct->addrTnct);
   632    624           pOp->opcode = OP_Null;
   633    625           pOp->p1 = 1;
   634    626           pOp->p2 = regPrev;
   635    627   
   636         -        iJump = sqlite3VdbeCurrentAddr(v) + nColumn;
   637         -        for(i=0; i<nColumn; i++){
          628  +        iJump = sqlite3VdbeCurrentAddr(v) + nResultCol;
          629  +        for(i=0; i<nResultCol; i++){
   638    630             CollSeq *pColl = sqlite3ExprCollSeq(pParse, pEList->a[i].pExpr);
   639         -          if( i<nColumn-1 ){
          631  +          if( i<nResultCol-1 ){
   640    632               sqlite3VdbeAddOp3(v, OP_Ne, regResult+i, iJump, regPrev+i);
   641    633             }else{
   642    634               sqlite3VdbeAddOp3(v, OP_Eq, regResult+i, iContinue, regPrev+i);
   643    635             }
   644    636             sqlite3VdbeChangeP4(v, -1, (const char *)pColl, P4_COLLSEQ);
   645    637             sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);
   646    638           }
   647    639           assert( sqlite3VdbeCurrentAddr(v)==iJump );
   648         -        sqlite3VdbeAddOp3(v, OP_Copy, regResult, regPrev, nColumn-1);
          640  +        sqlite3VdbeAddOp3(v, OP_Copy, regResult, regPrev, nResultCol-1);
   649    641           break;
   650    642         }
   651    643   
   652    644         case WHERE_DISTINCT_UNIQUE: {
   653    645           sqlite3VdbeChangeToNoop(v, pDistinct->addrTnct);
   654    646           break;
   655    647         }
   656    648   
   657    649         default: {
   658    650           assert( pDistinct->eTnctType==WHERE_DISTINCT_UNORDERED );
   659         -        codeDistinct(pParse, pDistinct->tabTnct, iContinue, nColumn, regResult);
          651  +        codeDistinct(pParse, pDistinct->tabTnct, iContinue, nResultCol, regResult);
   660    652           break;
   661    653         }
   662    654       }
   663    655       if( pOrderBy==0 ){
   664         -      codeOffset(v, p, iContinue);
          656  +      codeOffset(v, p->iOffset, iContinue);
   665    657       }
   666    658     }
   667    659   
   668    660     switch( eDest ){
   669    661       /* In this mode, write each query result to the key of the temporary
   670    662       ** table iParm.
   671    663       */
   672    664   #ifndef SQLITE_OMIT_COMPOUND_SELECT
   673    665       case SRT_Union: {
   674    666         int r1;
   675    667         r1 = sqlite3GetTempReg(pParse);
   676         -      sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nColumn, r1);
          668  +      sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nResultCol, r1);
   677    669         sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm, r1);
   678    670         sqlite3ReleaseTempReg(pParse, r1);
   679    671         break;
   680    672       }
   681    673   
   682    674       /* Construct a record from the query result, but instead of
   683    675       ** saving that record, use it as a key to delete elements from
   684    676       ** the temporary table iParm.
   685    677       */
   686    678       case SRT_Except: {
   687         -      sqlite3VdbeAddOp3(v, OP_IdxDelete, iParm, regResult, nColumn);
          679  +      sqlite3VdbeAddOp3(v, OP_IdxDelete, iParm, regResult, nResultCol);
   688    680         break;
   689    681       }
   690         -#endif
          682  +#endif /* SQLITE_OMIT_COMPOUND_SELECT */
   691    683   
   692    684       /* Store the result as data using a unique key.
   693    685       */
   694    686       case SRT_DistTable:
   695    687       case SRT_Table:
   696    688       case SRT_EphemTab: {
   697    689         int r1 = sqlite3GetTempReg(pParse);
   698    690         testcase( eDest==SRT_Table );
   699    691         testcase( eDest==SRT_EphemTab );
   700         -      sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nColumn, r1);
          692  +      sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nResultCol, r1);
   701    693   #ifndef SQLITE_OMIT_CTE
   702    694         if( eDest==SRT_DistTable ){
   703    695           /* If the destination is DistTable, then cursor (iParm+1) is open
   704    696           ** on an ephemeral index. If the current row is already present
   705    697           ** in the index, do not write it to the output. If not, add the
   706    698           ** current row to the index and proceed with writing it to the
   707    699           ** output table as well.  */
................................................................................
   726    718   
   727    719   #ifndef SQLITE_OMIT_SUBQUERY
   728    720       /* If we are creating a set for an "expr IN (SELECT ...)" construct,
   729    721       ** then there should be a single item on the stack.  Write this
   730    722       ** item into the set table with bogus data.
   731    723       */
   732    724       case SRT_Set: {
   733         -      assert( nColumn==1 );
          725  +      assert( nResultCol==1 );
   734    726         pDest->affSdst =
   735    727                     sqlite3CompareAffinity(pEList->a[0].pExpr, pDest->affSdst);
   736    728         if( pOrderBy ){
   737    729           /* At first glance you would think we could optimize out the
   738    730           ** ORDER BY in this case since the order of entries in the set
   739    731           ** does not matter.  But there might be a LIMIT clause, in which
   740    732           ** case the order does matter */
................................................................................
   758    750       }
   759    751   
   760    752       /* If this is a scalar select that is part of an expression, then
   761    753       ** store the results in the appropriate memory cell and break out
   762    754       ** of the scan loop.
   763    755       */
   764    756       case SRT_Mem: {
   765         -      assert( nColumn==1 );
          757  +      assert( nResultCol==1 );
   766    758         if( pOrderBy ){
   767    759           pushOntoSorter(pParse, pOrderBy, p, regResult);
   768    760         }else{
   769    761           sqlite3ExprCodeMove(pParse, regResult, iParm, 1);
   770    762           /* The LIMIT clause will jump out of the loop for us */
   771    763         }
   772    764         break;
................................................................................
   779    771       */
   780    772       case SRT_Coroutine:
   781    773       case SRT_Output: {
   782    774         testcase( eDest==SRT_Coroutine );
   783    775         testcase( eDest==SRT_Output );
   784    776         if( pOrderBy ){
   785    777           int r1 = sqlite3GetTempReg(pParse);
   786         -        sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nColumn, r1);
          778  +        sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nResultCol, r1);
   787    779           pushOntoSorter(pParse, pOrderBy, p, r1);
   788    780           sqlite3ReleaseTempReg(pParse, r1);
   789    781         }else if( eDest==SRT_Coroutine ){
   790    782           sqlite3VdbeAddOp1(v, OP_Yield, pDest->iSDParm);
   791    783         }else{
   792         -        sqlite3VdbeAddOp2(v, OP_ResultRow, regResult, nColumn);
   793         -        sqlite3ExprCacheAffinityChange(pParse, regResult, nColumn);
          784  +        sqlite3VdbeAddOp2(v, OP_ResultRow, regResult, nResultCol);
          785  +        sqlite3ExprCacheAffinityChange(pParse, regResult, nResultCol);
   794    786         }
   795    787         break;
   796    788       }
          789  +
          790  +#ifndef SQLITE_OMIT_CTE
          791  +    /* Write the results into a priority queue that is order according to
          792  +    ** pDest->pOrderBy (in pSO).  pDest->iSDParm (in iParm) is the cursor for an
          793  +    ** index with pSO->nExpr+2 columns.  Build a key using pSO for the first
          794  +    ** pSO->nExpr columns, then make sure all keys are unique by adding a
          795  +    ** final OP_Sequence column.  The last column is the record as a blob.
          796  +    */
          797  +    case SRT_DistQueue:
          798  +    case SRT_Queue: {
          799  +      int nKey;
          800  +      int r1, r2, r3;
          801  +      int addrTest = 0;
          802  +      ExprList *pSO;
          803  +      pSO = pDest->pOrderBy;
          804  +      assert( pSO );
          805  +      nKey = pSO->nExpr;
          806  +      r1 = sqlite3GetTempReg(pParse);
          807  +      r2 = sqlite3GetTempRange(pParse, nKey+2);
          808  +      r3 = r2+nKey+1;
          809  +      sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nResultCol, r3);
          810  +      if( eDest==SRT_DistQueue ){
          811  +        /* If the destination is DistQueue, then cursor (iParm+1) is open
          812  +        ** on a second ephemeral index that holds all values every previously
          813  +        ** added to the queue.  Only add this new value if it has never before
          814  +        ** been added */
          815  +        addrTest = sqlite3VdbeAddOp4Int(v, OP_Found, iParm+1, 0, r3, 0);
          816  +        sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm+1, r3);
          817  +      }
          818  +      for(i=0; i<nKey; i++){
          819  +        sqlite3VdbeAddOp2(v, OP_SCopy,
          820  +                          regResult + pSO->a[i].u.x.iOrderByCol - 1,
          821  +                          r2+i);
          822  +      }
          823  +      sqlite3VdbeAddOp2(v, OP_Sequence, iParm, r2+nKey);
          824  +      sqlite3VdbeAddOp3(v, OP_MakeRecord, r2, nKey+2, r1);
          825  +      sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm, r1);
          826  +      if( addrTest ) sqlite3VdbeJumpHere(v, addrTest);
          827  +      sqlite3ReleaseTempReg(pParse, r1);
          828  +      sqlite3ReleaseTempRange(pParse, r2, nKey+2);
          829  +      break;
          830  +    }
          831  +#endif /* SQLITE_OMIT_CTE */
          832  +
          833  +
   797    834   
   798    835   #if !defined(SQLITE_OMIT_TRIGGER)
   799    836       /* Discard the results.  This is used for SELECT statements inside
   800    837       ** the body of a TRIGGER.  The purpose of such selects is to call
   801    838       ** user-defined functions that have side effects.  We do not care
   802    839       ** about the actual results of the select.
   803    840       */
................................................................................
   879    916   ** then the KeyInfo structure is appropriate for initializing a virtual
   880    917   ** index to implement a DISTINCT test.
   881    918   **
   882    919   ** Space to hold the KeyInfo structure is obtain from malloc.  The calling
   883    920   ** function is responsible for seeing that this structure is eventually
   884    921   ** freed.
   885    922   */
   886         -static KeyInfo *keyInfoFromExprList(Parse *pParse, ExprList *pList){
          923  +static KeyInfo *keyInfoFromExprList(Parse *pParse, ExprList *pList, int nExtra){
   887    924     int nExpr;
   888    925     KeyInfo *pInfo;
   889    926     struct ExprList_item *pItem;
   890    927     sqlite3 *db = pParse->db;
   891    928     int i;
   892    929   
   893    930     nExpr = pList->nExpr;
   894         -  pInfo = sqlite3KeyInfoAlloc(db, nExpr, 1);
          931  +  pInfo = sqlite3KeyInfoAlloc(db, nExpr+nExtra, 1);
   895    932     if( pInfo ){
   896    933       assert( sqlite3KeyInfoIsWriteable(pInfo) );
   897    934       for(i=0, pItem=pList->a; i<nExpr; i++, pItem++){
   898    935         CollSeq *pColl;
   899    936         pColl = sqlite3ExprCollSeq(pParse, pItem->pExpr);
   900    937         if( !pColl ) pColl = db->pDfltColl;
   901    938         pInfo->aColl[i] = pColl;
................................................................................
  1028   1065       regRowid = sqlite3GetTempReg(pParse);
  1029   1066     }
  1030   1067     if( p->selFlags & SF_UseSorter ){
  1031   1068       int regSortOut = ++pParse->nMem;
  1032   1069       int ptab2 = pParse->nTab++;
  1033   1070       sqlite3VdbeAddOp3(v, OP_OpenPseudo, ptab2, regSortOut, pOrderBy->nExpr+2);
  1034   1071       addr = 1 + sqlite3VdbeAddOp2(v, OP_SorterSort, iTab, addrBreak);
  1035         -    codeOffset(v, p, addrContinue);
         1072  +    codeOffset(v, p->iOffset, addrContinue);
  1036   1073       sqlite3VdbeAddOp2(v, OP_SorterData, iTab, regSortOut);
  1037   1074       sqlite3VdbeAddOp3(v, OP_Column, ptab2, pOrderBy->nExpr+1, regRow);
  1038   1075       sqlite3VdbeChangeP5(v, OPFLAG_CLEARCACHE);
  1039   1076     }else{
  1040   1077       addr = 1 + sqlite3VdbeAddOp2(v, OP_Sort, iTab, addrBreak);
  1041         -    codeOffset(v, p, addrContinue);
         1078  +    codeOffset(v, p->iOffset, addrContinue);
  1042   1079       sqlite3VdbeAddOp3(v, OP_Column, iTab, pOrderBy->nExpr+1, regRow);
  1043   1080     }
  1044   1081     switch( eDest ){
  1045   1082       case SRT_Table:
  1046   1083       case SRT_EphemTab: {
  1047   1084         testcase( eDest==SRT_Table );
  1048   1085         testcase( eDest==SRT_EphemTab );
................................................................................
  1598   1635   ** keywords.  Or NULL if those keywords are omitted. iLimit and iOffset 
  1599   1636   ** are the integer memory register numbers for counters used to compute 
  1600   1637   ** the limit and offset.  If there is no limit and/or offset, then 
  1601   1638   ** iLimit and iOffset are negative.
  1602   1639   **
  1603   1640   ** This routine changes the values of iLimit and iOffset only if
  1604   1641   ** a limit or offset is defined by pLimit and pOffset.  iLimit and
  1605         -** iOffset should have been preset to appropriate default values
  1606         -** (usually but not always -1) prior to calling this routine.
         1642  +** iOffset should have been preset to appropriate default values (zero)
         1643  +** prior to calling this routine.
         1644  +**
         1645  +** The iOffset register (if it exists) is initialized to the value
         1646  +** of the OFFSET.  The iLimit register is initialized to LIMIT.  Register
         1647  +** iOffset+1 is initialized to LIMIT+OFFSET.
         1648  +**
  1607   1649   ** Only if pLimit!=0 or pOffset!=0 do the limit registers get
  1608   1650   ** redefined.  The UNION ALL operator uses this property to force
  1609   1651   ** the reuse of the same limit and offset registers across multiple
  1610   1652   ** SELECT statements.
  1611   1653   */
  1612   1654   static void computeLimitRegisters(Parse *pParse, Select *p, int iBreak){
  1613   1655     Vdbe *v = 0;
................................................................................
  1623   1665     ** no rows.
  1624   1666     */
  1625   1667     sqlite3ExprCacheClear(pParse);
  1626   1668     assert( p->pOffset==0 || p->pLimit!=0 );
  1627   1669     if( p->pLimit ){
  1628   1670       p->iLimit = iLimit = ++pParse->nMem;
  1629   1671       v = sqlite3GetVdbe(pParse);
  1630         -    if( NEVER(v==0) ) return;  /* VDBE should have already been allocated */
         1672  +    assert( v!=0 );
  1631   1673       if( sqlite3ExprIsInteger(p->pLimit, &n) ){
  1632   1674         sqlite3VdbeAddOp2(v, OP_Integer, n, iLimit);
  1633   1675         VdbeComment((v, "LIMIT counter"));
  1634   1676         if( n==0 ){
  1635   1677           sqlite3VdbeAddOp2(v, OP_Goto, 0, iBreak);
  1636   1678         }else if( n>=0 && p->nSelectRow>(u64)n ){
  1637   1679           p->nSelectRow = n;
................................................................................
  1680   1722     if( pRet==0 && iCol<p->pEList->nExpr ){
  1681   1723       pRet = sqlite3ExprCollSeq(pParse, p->pEList->a[iCol].pExpr);
  1682   1724     }
  1683   1725     return pRet;
  1684   1726   }
  1685   1727   #endif /* SQLITE_OMIT_COMPOUND_SELECT */
  1686   1728   
  1687         -/* Forward reference */
         1729  +#ifndef SQLITE_OMIT_CTE
         1730  +/*
         1731  +** This routine generates VDBE code to compute the content of a WITH RECURSIVE
         1732  +** query of the form:
         1733  +**
         1734  +**   <recursive-table> AS (<setup-query> UNION [ALL] <recursive-query>)
         1735  +**                         \___________/             \_______________/
         1736  +**                           p->pPrior                      p
         1737  +**
         1738  +**
         1739  +** There is exactly one reference to the recursive-table in the FROM clause
         1740  +** of recursive-query, marked with the SrcList->a[].isRecursive flag.
         1741  +**
         1742  +** The setup-query runs once to generate an initial set of rows that go
         1743  +** into a Queue table.  Rows are extracted from the Queue table one by
         1744  +** one.  Each row extracted from Queue is output to pDest.  Then the single
         1745  +** extracted row (now in the iCurrent table) becomes the content of the
         1746  +** recursive-table for a recursive-query run.  The output of the recursive-query
         1747  +** is added back into the Queue table.  Then another row is extracted from Queue
         1748  +** and the iteration continues until the Queue table is empty.
         1749  +**
         1750  +** If the compound query operator is UNION then no duplicate rows are ever
         1751  +** inserted into the Queue table.  The iDistinct table keeps a copy of all rows
         1752  +** that have ever been inserted into Queue and causes duplicates to be
         1753  +** discarded.  If the operator is UNION ALL, then duplicates are allowed.
         1754  +** 
         1755  +** If the query has an ORDER BY, then entries in the Queue table are kept in
         1756  +** ORDER BY order and the first entry is extracted for each cycle.  Without
         1757  +** an ORDER BY, the Queue table is just a FIFO.
         1758  +**
         1759  +** If a LIMIT clause is provided, then the iteration stops after LIMIT rows
         1760  +** have been output to pDest.  A LIMIT of zero means to output no rows and a
         1761  +** negative LIMIT means to output all rows.  If there is also an OFFSET clause
         1762  +** with a positive value, then the first OFFSET outputs are discarded rather
         1763  +** than being sent to pDest.  The LIMIT count does not begin until after OFFSET
         1764  +** rows have been skipped.
         1765  +*/
         1766  +static void generateWithRecursiveQuery(
         1767  +  Parse *pParse,        /* Parsing context */
         1768  +  Select *p,            /* The recursive SELECT to be coded */
         1769  +  SelectDest *pDest     /* What to do with query results */
         1770  +){
         1771  +  SrcList *pSrc = p->pSrc;      /* The FROM clause of the recursive query */
         1772  +  int nCol = p->pEList->nExpr;  /* Number of columns in the recursive table */
         1773  +  Vdbe *v = pParse->pVdbe;      /* The prepared statement under construction */
         1774  +  Select *pSetup = p->pPrior;   /* The setup query */
         1775  +  int addrTop;                  /* Top of the loop */
         1776  +  int addrCont, addrBreak;      /* CONTINUE and BREAK addresses */
         1777  +  int iCurrent;                 /* The Current table */
         1778  +  int regCurrent;               /* Register holding Current table */
         1779  +  int iQueue;                   /* The Queue table */
         1780  +  int iDistinct = 0;            /* To ensure unique results if UNION */
         1781  +  int eDest = SRT_Table;        /* How to write to Queue */
         1782  +  SelectDest destQueue;         /* SelectDest targetting the Queue table */
         1783  +  int i;                        /* Loop counter */
         1784  +  int rc;                       /* Result code */
         1785  +  ExprList *pOrderBy;           /* The ORDER BY clause */
         1786  +  Expr *pLimit, *pOffset;       /* Saved LIMIT and OFFSET */
         1787  +  int regLimit, regOffset;      /* Registers used by LIMIT and OFFSET */
         1788  +
         1789  +  /* Obtain authorization to do a recursive query */
         1790  +  if( sqlite3AuthCheck(pParse, SQLITE_RECURSIVE, 0, 0, 0) ) return;
         1791  +
         1792  +  /* Process the LIMIT and OFFSET clauses, if they exist */
         1793  +  addrBreak = sqlite3VdbeMakeLabel(v);
         1794  +  computeLimitRegisters(pParse, p, addrBreak);
         1795  +  pLimit = p->pLimit;
         1796  +  pOffset = p->pOffset;
         1797  +  regLimit = p->iLimit;
         1798  +  regOffset = p->iOffset;
         1799  +  p->pLimit = p->pOffset = 0;
         1800  +  p->iLimit = p->iOffset = 0;
         1801  +
         1802  +  /* Locate the cursor number of the Current table */
         1803  +  for(i=0; ALWAYS(i<pSrc->nSrc); i++){
         1804  +    if( pSrc->a[i].isRecursive ){
         1805  +      iCurrent = pSrc->a[i].iCursor;
         1806  +      break;
         1807  +    }
         1808  +  }
         1809  +
         1810  +  /* Detach the ORDER BY clause from the compound SELECT */
         1811  +  pOrderBy = p->pOrderBy;
         1812  +  p->pOrderBy = 0;
         1813  +
         1814  +  /* Allocate cursors numbers for Queue and Distinct.  The cursor number for
         1815  +  ** the Distinct table must be exactly one greater than Queue in order
         1816  +  ** for the SRT_DistTable and SRT_DistQueue destinations to work. */
         1817  +  iQueue = pParse->nTab++;
         1818  +  if( p->op==TK_UNION ){
         1819  +    eDest = pOrderBy ? SRT_DistQueue : SRT_DistTable;
         1820  +    iDistinct = pParse->nTab++;
         1821  +  }else{
         1822  +    eDest = pOrderBy ? SRT_Queue : SRT_Table;
         1823  +  }
         1824  +  sqlite3SelectDestInit(&destQueue, eDest, iQueue);
         1825  +
         1826  +  /* Allocate cursors for Current, Queue, and Distinct. */
         1827  +  regCurrent = ++pParse->nMem;
         1828  +  sqlite3VdbeAddOp3(v, OP_OpenPseudo, iCurrent, regCurrent, nCol);
         1829  +  if( pOrderBy ){
         1830  +    KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pOrderBy, 1);
         1831  +    sqlite3VdbeAddOp4(v, OP_OpenEphemeral, iQueue, pOrderBy->nExpr+2, 0,
         1832  +                      (char*)pKeyInfo, P4_KEYINFO);
         1833  +    destQueue.pOrderBy = pOrderBy;
         1834  +  }else{
         1835  +    sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iQueue, nCol);
         1836  +  }
         1837  +  VdbeComment((v, "Queue table"));
         1838  +  if( iDistinct ){
         1839  +    p->addrOpenEphm[0] = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iDistinct, 0);
         1840  +    p->selFlags |= SF_UsesEphemeral;
         1841  +  }
         1842  +
         1843  +  /* Store the results of the setup-query in Queue. */
         1844  +  rc = sqlite3Select(pParse, pSetup, &destQueue);
         1845  +  if( rc ) goto end_of_recursive_query;
         1846  +
         1847  +  /* Find the next row in the Queue and output that row */
         1848  +  addrTop = sqlite3VdbeAddOp2(v, OP_Rewind, iQueue, addrBreak);
         1849  +
         1850  +  /* Transfer the next row in Queue over to Current */
         1851  +  sqlite3VdbeAddOp1(v, OP_NullRow, iCurrent); /* To reset column cache */
         1852  +  if( pOrderBy ){
         1853  +    sqlite3VdbeAddOp3(v, OP_Column, iQueue, pOrderBy->nExpr+1, regCurrent);
         1854  +  }else{
         1855  +    sqlite3VdbeAddOp2(v, OP_RowData, iQueue, regCurrent);
         1856  +  }
         1857  +  sqlite3VdbeAddOp1(v, OP_Delete, iQueue);
         1858  +
         1859  +  /* Output the single row in Current */
         1860  +  addrCont = sqlite3VdbeMakeLabel(v);
         1861  +  codeOffset(v, regOffset, addrCont);
         1862  +  selectInnerLoop(pParse, p, p->pEList, iCurrent,
         1863  +      0, 0, pDest, addrCont, addrBreak);
         1864  +  if( regLimit ) sqlite3VdbeAddOp3(v, OP_IfZero, regLimit, addrBreak, -1);
         1865  +  sqlite3VdbeResolveLabel(v, addrCont);
         1866  +
         1867  +  /* Execute the recursive SELECT taking the single row in Current as
         1868  +  ** the value for the recursive-table. Store the results in the Queue.
         1869  +  */
         1870  +  p->pPrior = 0;
         1871  +  sqlite3Select(pParse, p, &destQueue);
         1872  +  assert( p->pPrior==0 );
         1873  +  p->pPrior = pSetup;
         1874  +
         1875  +  /* Keep running the loop until the Queue is empty */
         1876  +  sqlite3VdbeAddOp2(v, OP_Goto, 0, addrTop);
         1877  +  sqlite3VdbeResolveLabel(v, addrBreak);
         1878  +
         1879  +end_of_recursive_query:
         1880  +  p->pOrderBy = pOrderBy;
         1881  +  p->pLimit = pLimit;
         1882  +  p->pOffset = pOffset;
         1883  +  return;
         1884  +}
         1885  +#endif
         1886  +
         1887  +/* Forward references */
  1688   1888   static int multiSelectOrderBy(
  1689   1889     Parse *pParse,        /* Parsing context */
  1690   1890     Select *p,            /* The right-most of SELECTs to be coded */
  1691   1891     SelectDest *pDest     /* What to do with query results */
  1692   1892   );
  1693   1893   
  1694   1894   
................................................................................
  1788   1988       }
  1789   1989       rc = 1;
  1790   1990       goto multi_select_end;
  1791   1991     }
  1792   1992   
  1793   1993   #ifndef SQLITE_OMIT_CTE
  1794   1994     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;
  1806         -
  1807         -    /* Check that there is no ORDER BY or LIMIT clause. Neither of these 
  1808         -    ** are supported on recursive queries.  */
  1809         -    assert( p->pOffset==0 || p->pLimit );
  1810         -    if( p->pOrderBy || p->pLimit ){
  1811         -      sqlite3ErrorMsg(pParse, "%s in a recursive query",
  1812         -          p->pOrderBy ? "ORDER BY" : "LIMIT"
  1813         -      );
  1814         -      goto multi_select_end;
  1815         -    }
  1816         -
  1817         -    if( sqlite3AuthCheck(pParse, SQLITE_RECURSIVE, 0, 0, 0) ){
  1818         -      goto multi_select_end;
  1819         -    }
  1820         -    iBreak = sqlite3VdbeMakeLabel(v);
  1821         -    iCont = sqlite3VdbeMakeLabel(v);
  1822         -
  1823         -    for(i=0; ALWAYS(i<pSrc->nSrc); i++){
  1824         -      if( pSrc->a[i].isRecursive ){
  1825         -        tmp1 = pSrc->a[i].iCursor;
  1826         -        break;
  1827         -      }
  1828         -    }
  1829         -
  1830         -    tmp2 = pParse->nTab++;
  1831         -    if( p->op==TK_UNION ){
  1832         -      eDest = SRT_DistTable;
  1833         -      tmp3 = pParse->nTab++;
  1834         -    }
  1835         -    sqlite3SelectDestInit(&tmp2dest, eDest, tmp2);
  1836         -
  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);
  1841         -      p->selFlags |= SF_UsesEphemeral;
  1842         -    }
  1843         -
  1844         -    /* Store the results of the initial SELECT in tmp2. */
  1845         -    rc = sqlite3Select(pParse, pPrior, &tmp2dest);
  1846         -    if( rc ) goto multi_select_end;
  1847         -
  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         -
  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.  */
  1862         -    p->pPrior = 0;
  1863         -    rc = sqlite3Select(pParse, p, &tmp2dest);
  1864         -    assert( p->pPrior==0 );
  1865         -    p->pPrior = pPrior;
  1866         -    if( rc ) goto multi_select_end;
  1867         -
  1868         -    sqlite3VdbeAddOp2(v, OP_Goto, 0, addrSwap);
  1869         -    sqlite3VdbeResolveLabel(v, iBreak);
         1995  +    generateWithRecursiveQuery(pParse, p, &dest);
  1870   1996     }else
  1871   1997   #endif
  1872   1998   
  1873   1999     /* Compound SELECTs that have an ORDER BY clause are handled separately.
  1874   2000     */
  1875   2001     if( p->pOrderBy ){
  1876   2002       return multiSelectOrderBy(pParse, p, pDest);
................................................................................
  2005   2131             generateColumnNames(pParse, 0, pFirst->pEList);
  2006   2132           }
  2007   2133           iBreak = sqlite3VdbeMakeLabel(v);
  2008   2134           iCont = sqlite3VdbeMakeLabel(v);
  2009   2135           computeLimitRegisters(pParse, p, iBreak);
  2010   2136           sqlite3VdbeAddOp2(v, OP_Rewind, unionTab, iBreak);
  2011   2137           iStart = sqlite3VdbeCurrentAddr(v);
  2012         -        selectInnerLoop(pParse, p, p->pEList, unionTab, p->pEList->nExpr,
         2138  +        selectInnerLoop(pParse, p, p->pEList, unionTab,
  2013   2139                           0, 0, &dest, iCont, iBreak);
  2014   2140           sqlite3VdbeResolveLabel(v, iCont);
  2015   2141           sqlite3VdbeAddOp2(v, OP_Next, unionTab, iStart);
  2016   2142           sqlite3VdbeResolveLabel(v, iBreak);
  2017   2143           sqlite3VdbeAddOp2(v, OP_Close, unionTab, 0);
  2018   2144         }
  2019   2145         break;
................................................................................
  2083   2209         iCont = sqlite3VdbeMakeLabel(v);
  2084   2210         computeLimitRegisters(pParse, p, iBreak);
  2085   2211         sqlite3VdbeAddOp2(v, OP_Rewind, tab1, iBreak);
  2086   2212         r1 = sqlite3GetTempReg(pParse);
  2087   2213         iStart = sqlite3VdbeAddOp2(v, OP_RowKey, tab1, r1);
  2088   2214         sqlite3VdbeAddOp4Int(v, OP_NotFound, tab2, iCont, r1, 0);
  2089   2215         sqlite3ReleaseTempReg(pParse, r1);
  2090         -      selectInnerLoop(pParse, p, p->pEList, tab1, p->pEList->nExpr,
         2216  +      selectInnerLoop(pParse, p, p->pEList, tab1,
  2091   2217                         0, 0, &dest, iCont, iBreak);
  2092   2218         sqlite3VdbeResolveLabel(v, iCont);
  2093   2219         sqlite3VdbeAddOp2(v, OP_Next, tab1, iStart);
  2094   2220         sqlite3VdbeResolveLabel(v, iBreak);
  2095   2221         sqlite3VdbeAddOp2(v, OP_Close, tab2, 0);
  2096   2222         sqlite3VdbeAddOp2(v, OP_Close, tab1, 0);
  2097   2223         break;
................................................................................
  2205   2331       sqlite3VdbeAddOp3(v, OP_Copy, pIn->iSdst, regPrev+1, pIn->nSdst-1);
  2206   2332       sqlite3VdbeAddOp2(v, OP_Integer, 1, regPrev);
  2207   2333     }
  2208   2334     if( pParse->db->mallocFailed ) return 0;
  2209   2335   
  2210   2336     /* Suppress the first OFFSET entries if there is an OFFSET clause
  2211   2337     */
  2212         -  codeOffset(v, p, iContinue);
         2338  +  codeOffset(v, p->iOffset, iContinue);
  2213   2339   
  2214   2340     switch( pDest->eDest ){
  2215   2341       /* Store the result as data using a unique key.
  2216   2342       */
  2217   2343       case SRT_Table:
  2218   2344       case SRT_EphemTab: {
  2219   2345         int r1 = sqlite3GetTempReg(pParse);
................................................................................
  4151   4277         Expr *pE = pFunc->pExpr;
  4152   4278         assert( !ExprHasProperty(pE, EP_xIsSelect) );
  4153   4279         if( pE->x.pList==0 || pE->x.pList->nExpr!=1 ){
  4154   4280           sqlite3ErrorMsg(pParse, "DISTINCT aggregates must have exactly one "
  4155   4281              "argument");
  4156   4282           pFunc->iDistinct = -1;
  4157   4283         }else{
  4158         -        KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pE->x.pList);
         4284  +        KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pE->x.pList, 0);
  4159   4285           sqlite3VdbeAddOp4(v, OP_OpenEphemeral, pFunc->iDistinct, 0, 0,
  4160   4286                             (char*)pKeyInfo, P4_KEYINFO);
  4161   4287         }
  4162   4288       }
  4163   4289     }
  4164   4290   }
  4165   4291   
................................................................................
  4284   4410   #else
  4285   4411   # define explainSimpleCount(a,b,c)
  4286   4412   #endif
  4287   4413   
  4288   4414   /*
  4289   4415   ** Generate code for the SELECT statement given in the p argument.  
  4290   4416   **
  4291         -** The results are distributed in various ways depending on the
  4292         -** contents of the SelectDest structure pointed to by argument pDest
  4293         -** as follows:
  4294         -**
  4295         -**     pDest->eDest    Result
  4296         -**     ------------    -------------------------------------------
  4297         -**     SRT_Output      Generate a row of output (using the OP_ResultRow
  4298         -**                     opcode) for each row in the result set.
  4299         -**
  4300         -**     SRT_Mem         Only valid if the result is a single column.
  4301         -**                     Store the first column of the first result row
  4302         -**                     in register pDest->iSDParm then abandon the rest
  4303         -**                     of the query.  This destination implies "LIMIT 1".
  4304         -**
  4305         -**     SRT_Set         The result must be a single column.  Store each
  4306         -**                     row of result as the key in table pDest->iSDParm. 
  4307         -**                     Apply the affinity pDest->affSdst before storing
  4308         -**                     results.  Used to implement "IN (SELECT ...)".
  4309         -**
  4310         -**     SRT_Union       Store results as a key in a temporary table 
  4311         -**                     identified by pDest->iSDParm.
  4312         -**
  4313         -**     SRT_Except      Remove results from the temporary table pDest->iSDParm.
  4314         -**
  4315         -**     SRT_Table       Store results in temporary table pDest->iSDParm.
  4316         -**                     This is like SRT_EphemTab except that the table
  4317         -**                     is assumed to already be open.
  4318         -**
  4319         -**     SRT_EphemTab    Create an temporary table pDest->iSDParm and store
  4320         -**                     the result there. The cursor is left open after
  4321         -**                     returning.  This is like SRT_Table except that
  4322         -**                     this destination uses OP_OpenEphemeral to create
  4323         -**                     the table first.
  4324         -**
  4325         -**     SRT_Coroutine   Generate a co-routine that returns a new row of
  4326         -**                     results each time it is invoked.  The entry point
  4327         -**                     of the co-routine is stored in register pDest->iSDParm.
  4328         -**
  4329         -**     SRT_Exists      Store a 1 in memory cell pDest->iSDParm if the result
  4330         -**                     set is not empty.
  4331         -**
  4332         -**     SRT_Discard     Throw the results away.  This is used by SELECT
  4333         -**                     statements within triggers whose only purpose is
  4334         -**                     the side-effects of functions.
         4417  +** The results are returned according to the SelectDest structure.
         4418  +** See comments in sqliteInt.h for further information.
  4335   4419   **
  4336   4420   ** This routine returns the number of errors.  If any errors are
  4337   4421   ** encountered, then an appropriate error message is left in
  4338   4422   ** pParse->zErrMsg.
  4339   4423   **
  4340   4424   ** This routine does NOT free the Select structure passed in.  The
  4341   4425   ** calling function needs to do that.
................................................................................
  4602   4686     ** extracted in pre-sorted order.  If that is the case, then the
  4603   4687     ** OP_OpenEphemeral instruction will be changed to an OP_Noop once
  4604   4688     ** we figure out that the sorting index is not needed.  The addrSortIndex
  4605   4689     ** variable is used to facilitate that change.
  4606   4690     */
  4607   4691     if( pOrderBy ){
  4608   4692       KeyInfo *pKeyInfo;
  4609         -    pKeyInfo = keyInfoFromExprList(pParse, pOrderBy);
         4693  +    pKeyInfo = keyInfoFromExprList(pParse, pOrderBy, 0);
  4610   4694       pOrderBy->iECursor = pParse->nTab++;
  4611   4695       p->addrOpenEphm[2] = addrSortIndex =
  4612   4696         sqlite3VdbeAddOp4(v, OP_OpenEphemeral,
  4613   4697                              pOrderBy->iECursor, pOrderBy->nExpr+2, 0,
  4614   4698                              (char*)pKeyInfo, P4_KEYINFO);
  4615   4699     }else{
  4616   4700       addrSortIndex = -1;
................................................................................
  4634   4718   
  4635   4719     /* Open a virtual index to use for the distinct set.
  4636   4720     */
  4637   4721     if( p->selFlags & SF_Distinct ){
  4638   4722       sDistinct.tabTnct = pParse->nTab++;
  4639   4723       sDistinct.addrTnct = sqlite3VdbeAddOp4(v, OP_OpenEphemeral,
  4640   4724                                   sDistinct.tabTnct, 0, 0,
  4641         -                                (char*)keyInfoFromExprList(pParse, p->pEList),
         4725  +                                (char*)keyInfoFromExprList(pParse, p->pEList, 0),
  4642   4726                                   P4_KEYINFO);
  4643   4727       sqlite3VdbeChangeP5(v, BTREE_UNORDERED);
  4644   4728       sDistinct.eTnctType = WHERE_DISTINCT_UNORDERED;
  4645   4729     }else{
  4646   4730       sDistinct.eTnctType = WHERE_DISTINCT_NOOP;
  4647   4731     }
  4648   4732   
................................................................................
  4668   4752       */
  4669   4753       if( addrSortIndex>=0 && pOrderBy==0 ){
  4670   4754         sqlite3VdbeChangeToNoop(v, addrSortIndex);
  4671   4755         p->addrOpenEphm[2] = -1;
  4672   4756       }
  4673   4757   
  4674   4758       /* Use the standard inner loop. */
  4675         -    selectInnerLoop(pParse, p, pEList, 0, 0, pOrderBy, &sDistinct, pDest,
         4759  +    selectInnerLoop(pParse, p, pEList, -1, pOrderBy, &sDistinct, pDest,
  4676   4760                       sqlite3WhereContinueLabel(pWInfo),
  4677   4761                       sqlite3WhereBreakLabel(pWInfo));
  4678   4762   
  4679   4763       /* End the database scan loop.
  4680   4764       */
  4681   4765       sqlite3WhereEnd(pWInfo);
  4682   4766     }else{
................................................................................
  4758   4842   
  4759   4843         /* If there is a GROUP BY clause we might need a sorting index to
  4760   4844         ** implement it.  Allocate that sorting index now.  If it turns out
  4761   4845         ** that we do not need it after all, the OP_SorterOpen instruction
  4762   4846         ** will be converted into a Noop.  
  4763   4847         */
  4764   4848         sAggInfo.sortingIdx = pParse->nTab++;
  4765         -      pKeyInfo = keyInfoFromExprList(pParse, pGroupBy);
         4849  +      pKeyInfo = keyInfoFromExprList(pParse, pGroupBy, 0);
  4766   4850         addrSortingIdx = sqlite3VdbeAddOp4(v, OP_SorterOpen, 
  4767   4851             sAggInfo.sortingIdx, sAggInfo.nSortingColumn, 
  4768   4852             0, (char*)pKeyInfo, P4_KEYINFO);
  4769   4853   
  4770   4854         /* Initialize memory locations used by GROUP BY aggregate processing
  4771   4855         */
  4772   4856         iUseFlag = ++pParse->nMem;
................................................................................
  4940   5024         sqlite3VdbeResolveLabel(v, addrOutputRow);
  4941   5025         addrOutputRow = sqlite3VdbeCurrentAddr(v);
  4942   5026         sqlite3VdbeAddOp2(v, OP_IfPos, iUseFlag, addrOutputRow+2);
  4943   5027         VdbeComment((v, "Groupby result generator entry point"));
  4944   5028         sqlite3VdbeAddOp1(v, OP_Return, regOutputRow);
  4945   5029         finalizeAggFunctions(pParse, &sAggInfo);
  4946   5030         sqlite3ExprIfFalse(pParse, pHaving, addrOutputRow+1, SQLITE_JUMPIFNULL);
  4947         -      selectInnerLoop(pParse, p, p->pEList, 0, 0, pOrderBy,
         5031  +      selectInnerLoop(pParse, p, p->pEList, -1, pOrderBy,
  4948   5032                         &sDistinct, pDest,
  4949   5033                         addrOutputRow+1, addrSetAbort);
  4950   5034         sqlite3VdbeAddOp1(v, OP_Return, regOutputRow);
  4951   5035         VdbeComment((v, "end groupby result generator"));
  4952   5036   
  4953   5037         /* Generate a subroutine that will reset the group-by accumulator
  4954   5038         */
................................................................................
  5083   5167           }
  5084   5168           sqlite3WhereEnd(pWInfo);
  5085   5169           finalizeAggFunctions(pParse, &sAggInfo);
  5086   5170         }
  5087   5171   
  5088   5172         pOrderBy = 0;
  5089   5173         sqlite3ExprIfFalse(pParse, pHaving, addrEnd, SQLITE_JUMPIFNULL);
  5090         -      selectInnerLoop(pParse, p, p->pEList, 0, 0, 0, 0, 
         5174  +      selectInnerLoop(pParse, p, p->pEList, -1, 0, 0, 
  5091   5175                         pDest, addrEnd, addrEnd);
  5092   5176         sqlite3ExprListDelete(db, pDel);
  5093   5177       }
  5094   5178       sqlite3VdbeResolveLabel(v, addrEnd);
  5095   5179       
  5096   5180     } /* endif aggregate query */
  5097   5181   

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/sqliteInt.h.

  2163   2163   #define SF_Materialize     0x0100  /* Force materialization of views */
  2164   2164   #define SF_NestedFrom      0x0200  /* Part of a parenthesized FROM clause */
  2165   2165   #define SF_MaybeConvert    0x0400  /* Need convertCompoundSelectToSubquery() */
  2166   2166   #define SF_Recursive       0x0800  /* The recursive part of a recursive CTE */
  2167   2167   
  2168   2168   
  2169   2169   /*
  2170         -** The results of a select can be distributed in several ways.  The
  2171         -** "SRT" prefix means "SELECT Result Type".
         2170  +** The results of a SELECT can be distributed in several ways, as defined
         2171  +** by one of the following macros.  The "SRT" prefix means "SELECT Result
         2172  +** Type".
         2173  +**
         2174  +**     SRT_Union       Store results as a key in a temporary index 
         2175  +**                     identified by pDest->iSDParm.
         2176  +**
         2177  +**     SRT_Except      Remove results from the temporary index pDest->iSDParm.
         2178  +**
         2179  +**     SRT_Exists      Store a 1 in memory cell pDest->iSDParm if the result
         2180  +**                     set is not empty.
         2181  +**
         2182  +**     SRT_Discard     Throw the results away.  This is used by SELECT
         2183  +**                     statements within triggers whose only purpose is
         2184  +**                     the side-effects of functions.
         2185  +**
         2186  +** All of the above are free to ignore their ORDER BY clause. Those that
         2187  +** follow must honor the ORDER BY clause.
         2188  +**
         2189  +**     SRT_Output      Generate a row of output (using the OP_ResultRow
         2190  +**                     opcode) for each row in the result set.
         2191  +**
         2192  +**     SRT_Mem         Only valid if the result is a single column.
         2193  +**                     Store the first column of the first result row
         2194  +**                     in register pDest->iSDParm then abandon the rest
         2195  +**                     of the query.  This destination implies "LIMIT 1".
         2196  +**
         2197  +**     SRT_Set         The result must be a single column.  Store each
         2198  +**                     row of result as the key in table pDest->iSDParm. 
         2199  +**                     Apply the affinity pDest->affSdst before storing
         2200  +**                     results.  Used to implement "IN (SELECT ...)".
         2201  +**
         2202  +**     SRT_EphemTab    Create an temporary table pDest->iSDParm and store
         2203  +**                     the result there. The cursor is left open after
         2204  +**                     returning.  This is like SRT_Table except that
         2205  +**                     this destination uses OP_OpenEphemeral to create
         2206  +**                     the table first.
         2207  +**
         2208  +**     SRT_Coroutine   Generate a co-routine that returns a new row of
         2209  +**                     results each time it is invoked.  The entry point
         2210  +**                     of the co-routine is stored in register pDest->iSDParm
         2211  +**                     and the result row is stored in pDest->nDest registers
         2212  +**                     starting with pDest->iSdst.
         2213  +**
         2214  +**     SRT_Table       Store results in temporary table pDest->iSDParm.
         2215  +**                     This is like SRT_EphemTab except that the table
         2216  +**                     is assumed to already be open.
         2217  +**
         2218  +**     SRT_DistTable   Store results in a temporary table pDest->iSDParm.
         2219  +**                     But also use temporary table pDest->iSDParm+1 as
         2220  +**                     a record of all prior results and ignore any duplicate
         2221  +**                     rows.  Name means:  "Distinct Table".
         2222  +**
         2223  +**     SRT_Queue       Store results in priority queue pDest->iSDParm (really
         2224  +**                     an index).  Append a sequence number so that all entries
         2225  +**                     are distinct.
         2226  +**
         2227  +**     SRT_DistQueue   Store results in priority queue pDest->iSDParm only if
         2228  +**                     the same record has never been stored before.  The
         2229  +**                     index at pDest->iSDParm+1 hold all prior stores.
  2172   2230   */
  2173   2231   #define SRT_Union        1  /* Store result as keys in an index */
  2174   2232   #define SRT_Except       2  /* Remove result from a UNION index */
  2175   2233   #define SRT_Exists       3  /* Store 1 if the result is not empty */
  2176   2234   #define SRT_Discard      4  /* Do not save the results anywhere */
  2177   2235   
  2178   2236   /* The ORDER BY clause is ignored for all of the above */
  2179   2237   #define IgnorableOrderby(X) ((X->eDest)<=SRT_Discard)
  2180   2238   
  2181   2239   #define SRT_Output       5  /* Output each row of result */
  2182   2240   #define SRT_Mem          6  /* Store result in a memory cell */
  2183   2241   #define SRT_Set          7  /* Store results as keys in an index */
  2184         -#define SRT_Table        8  /* Store result as data with an automatic rowid */
  2185         -#define SRT_EphemTab     9  /* Create transient tab and store like SRT_Table */
  2186         -#define SRT_Coroutine   10  /* Generate a single row of result */
  2187         -#define SRT_DistTable   11  /* Like SRT_TABLE, but unique results only */
         2242  +#define SRT_EphemTab     8  /* Create transient tab and store like SRT_Table */
         2243  +#define SRT_Coroutine    9  /* Generate a single row of result */
         2244  +#define SRT_Table       10  /* Store result as data with an automatic rowid */
         2245  +#define SRT_DistTable   11  /* Like SRT_Table, but unique results only */
         2246  +#define SRT_Queue       12  /* Store result in an queue */
         2247  +#define SRT_DistQueue   13  /* Like SRT_Queue, but unique results only */
  2188   2248   
  2189   2249   /*
  2190   2250   ** An instance of this object describes where to put of the results of
  2191   2251   ** a SELECT statement.
  2192   2252   */
  2193   2253   struct SelectDest {
  2194         -  u8 eDest;         /* How to dispose of the results.  On of SRT_* above. */
  2195         -  char affSdst;     /* Affinity used when eDest==SRT_Set */
  2196         -  int iSDParm;      /* A parameter used by the eDest disposal method */
  2197         -  int iSdst;        /* Base register where results are written */
  2198         -  int nSdst;        /* Number of registers allocated */
         2254  +  u8 eDest;            /* How to dispose of the results.  On of SRT_* above. */
         2255  +  char affSdst;        /* Affinity used when eDest==SRT_Set */
         2256  +  int iSDParm;         /* A parameter used by the eDest disposal method */
         2257  +  int iSdst;           /* Base register where results are written */
         2258  +  int nSdst;           /* Number of registers allocated */
         2259  +  ExprList *pOrderBy;  /* Key columns for SRT_Queue and SRT_DistQueue */
  2199   2260   };
  2200   2261   
  2201   2262   /*
  2202   2263   ** During code generation of statements that do inserts into AUTOINCREMENT 
  2203   2264   ** tables, the following information is attached to the Table.u.autoInc.p
  2204   2265   ** pointer of each autoincrement table to record some side information that
  2205   2266   ** the code generator needs.  We have to keep per-table autoincrement

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  +      /* Tables marked isRecursive have only a single row that is stored in
         3415  +      ** a pseudo-cursor.  No need to Rewind or Next such cursors. */
         3416  +      pLevel->op = OP_Noop;
         3417  +    }else{
         3418  +      pLevel->op = aStep[bRev];
         3419  +      pLevel->p1 = iCur;
         3420  +      pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk);
         3421  +      pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
         3422  +    }
  3417   3423     }
  3418   3424   
  3419   3425     /* Insert code to test every subexpression that can be completely
  3420   3426     ** computed using the current set of tables.
  3421   3427     */
  3422   3428     for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){
  3423   3429       Expr *pE;

Changes to test/with1.test.

   148    148     WITH i(x) AS ( VALUES(1) UNION ALL SELECT x+1 FROM i)
   149    149     SELECT x FROM i LIMIT 10;
   150    150   } {1 2 3 4 5 6 7 8 9 10}
   151    151   
   152    152   do_catchsql_test 5.2 {
   153    153     WITH i(x) AS ( VALUES(1) UNION ALL SELECT x+1 FROM i ORDER BY 1)
   154    154     SELECT x FROM i LIMIT 10;
   155         -} {1 {ORDER BY in a recursive query}}
          155  +} {0 {1 2 3 4 5 6 7 8 9 10}}
          156  +
          157  +do_execsql_test 5.2.1 {
          158  +  CREATE TABLE edge(xfrom, xto, seq, PRIMARY KEY(xfrom, xto)) WITHOUT ROWID;
          159  +  INSERT INTO edge VALUES(0, 1, 10);
          160  +  INSERT INTO edge VALUES(1, 2, 20);
          161  +  INSERT INTO edge VALUES(0, 3, 30);
          162  +  INSERT INTO edge VALUES(2, 4, 40);
          163  +  INSERT INTO edge VALUES(3, 4, 40);
          164  +  INSERT INTO edge VALUES(2, 5, 50);
          165  +  INSERT INTO edge VALUES(3, 6, 60);
          166  +  INSERT INTO edge VALUES(5, 7, 70);
          167  +  INSERT INTO edge VALUES(3, 7, 70);
          168  +  INSERT INTO edge VALUES(4, 8, 80);
          169  +  INSERT INTO edge VALUES(7, 8, 80);
          170  +  INSERT INTO edge VALUES(8, 9, 90);
          171  +  
          172  +  WITH RECURSIVE
          173  +    ancest(id, mtime) AS
          174  +      (VALUES(0, 0)
          175  +       UNION
          176  +       SELECT edge.xto, edge.seq FROM edge, ancest
          177  +        WHERE edge.xfrom=ancest.id
          178  +        ORDER BY 2
          179  +      )
          180  +  SELECT * FROM ancest;
          181  +} {0 0 1 10 2 20 3 30 4 40 5 50 6 60 7 70 8 80 9 90}
          182  +do_execsql_test 5.2.2 {
          183  +  WITH RECURSIVE
          184  +    ancest(id, mtime) AS
          185  +      (VALUES(0, 0)
          186  +       UNION ALL
          187  +       SELECT edge.xto, edge.seq FROM edge, ancest
          188  +        WHERE edge.xfrom=ancest.id
          189  +        ORDER BY 2
          190  +      )
          191  +  SELECT * FROM ancest;
          192  +} {0 0 1 10 2 20 3 30 4 40 4 40 5 50 6 60 7 70 7 70 8 80 8 80 8 80 8 80 9 90 9 90 9 90 9 90}
          193  +do_execsql_test 5.2.3 {
          194  +  WITH RECURSIVE
          195  +    ancest(id, mtime) AS
          196  +      (VALUES(0, 0)
          197  +       UNION ALL
          198  +       SELECT edge.xto, edge.seq FROM edge, ancest
          199  +        WHERE edge.xfrom=ancest.id
          200  +        ORDER BY 2 LIMIT 4 OFFSET 2
          201  +      )
          202  +  SELECT * FROM ancest;
          203  +} {2 20 3 30 4 40 4 40}
   156    204   
   157    205   do_catchsql_test 5.3 {
   158         -  WITH i(x) AS ( VALUES(1) UNION ALL SELECT x+1 FROM i LIMIT 10 )
   159         -  SELECT x FROM i LIMIT 10;
   160         -} {1 {LIMIT in a recursive query}}
          206  +  WITH i(x) AS ( VALUES(1) UNION ALL SELECT x+1 FROM i LIMIT 5)
          207  +  SELECT x FROM i;
          208  +} {0 {1 2 3 4 5}}
   161    209   
   162    210   do_execsql_test 5.4 {
   163    211     WITH i(x) AS ( VALUES(1) UNION ALL SELECT (x+1)%10 FROM i)
   164    212     SELECT x FROM i LIMIT 20;
   165    213   } {1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0}
   166    214   
   167    215   do_execsql_test 5.5 {