/ Check-in [59742dd4]
Login

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

Overview
Comment:First attempt at getting block-sort to work. This is an incremental check-in. There are many problems still to be worked out.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | orderby-planning
Files: files | file ages | folders
SHA1: 59742dd4c5259883850044d0938248b009ebd045
User & Date: drh 2014-03-19 14:10:55
Context
2014-03-19
14:30
Make sure the where.c query planner never reports that the number of ORDER BY terms that are satisfied by indices is negative. check-in: b186d8d1 user: drh tags: orderby-planning
14:10
First attempt at getting block-sort to work. This is an incremental check-in. There are many problems still to be worked out. check-in: 59742dd4 user: drh tags: orderby-planning
2014-03-18
20:33
Make the partial-ORDER-BY information in the query planner available to the SELECT code generator. Still doesn't make a difference in the generated code. check-in: e258df23 user: drh tags: orderby-planning
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/btree.c.

  7420   7420       ** a no-op).  */
  7421   7421       invalidateIncrblobCursors(p, 0, 1);
  7422   7422       rc = clearDatabasePage(pBt, (Pgno)iTable, 0, pnChange);
  7423   7423     }
  7424   7424     sqlite3BtreeLeave(p);
  7425   7425     return rc;
  7426   7426   }
         7427  +
         7428  +/*
         7429  +** Delete all information from the single table that pCur is open on.
         7430  +**
         7431  +** This routine only work for pCur on an ephemeral table.
         7432  +*/
         7433  +int sqlite3BtreeClearTableOfCursor(BtCursor *pCur){
         7434  +  return sqlite3BtreeClearTable(pCur->pBtree, pCur->pgnoRoot, 0);
         7435  +}
  7427   7436   
  7428   7437   /*
  7429   7438   ** Erase all information in a table and add the root of the table to
  7430   7439   ** the freelist.  Except, the root of the principle table (the one on
  7431   7440   ** page 1) is never added to the freelist.
  7432   7441   **
  7433   7442   ** This routine will fail with SQLITE_LOCKED if there are any open

Changes to src/btree.h.

   111    111   ** indices.)
   112    112   */
   113    113   #define BTREE_INTKEY     1    /* Table has only 64-bit signed integer keys */
   114    114   #define BTREE_BLOBKEY    2    /* Table has keys only - no data */
   115    115   
   116    116   int sqlite3BtreeDropTable(Btree*, int, int*);
   117    117   int sqlite3BtreeClearTable(Btree*, int, int*);
          118  +int sqlite3BtreeClearTableOfCursor(BtCursor*);
   118    119   void sqlite3BtreeTripAllCursors(Btree*, int);
   119    120   
   120    121   void sqlite3BtreeGetMeta(Btree *pBtree, int idx, u32 *pValue);
   121    122   int sqlite3BtreeUpdateMeta(Btree*, int idx, u32 value);
   122    123   
   123    124   int sqlite3BtreeNewDb(Btree *p);
   124    125   

Changes to src/expr.c.

   945    945   ExprList *sqlite3ExprListDup(sqlite3 *db, ExprList *p, int flags){
   946    946     ExprList *pNew;
   947    947     struct ExprList_item *pItem, *pOldItem;
   948    948     int i;
   949    949     if( p==0 ) return 0;
   950    950     pNew = sqlite3DbMallocRaw(db, sizeof(*pNew) );
   951    951     if( pNew==0 ) return 0;
   952         -  pNew->iECursor = 0;
   953    952     pNew->nExpr = i = p->nExpr;
   954    953     if( (flags & EXPRDUP_REDUCE)==0 ) for(i=1; i<p->nExpr; i+=i){}
   955    954     pNew->a = pItem = sqlite3DbMallocRaw(db,  i*sizeof(p->a[0]) );
   956    955     if( pItem==0 ){
   957    956       sqlite3DbFree(db, pNew);
   958    957       return 0;
   959    958     } 
................................................................................
  1058   1057     pNew->pLimit = sqlite3ExprDup(db, p->pLimit, flags);
  1059   1058     pNew->pOffset = sqlite3ExprDup(db, p->pOffset, flags);
  1060   1059     pNew->iLimit = 0;
  1061   1060     pNew->iOffset = 0;
  1062   1061     pNew->selFlags = p->selFlags & ~SF_UsesEphemeral;
  1063   1062     pNew->addrOpenEphm[0] = -1;
  1064   1063     pNew->addrOpenEphm[1] = -1;
  1065         -  pNew->addrOpenEphm[2] = -1;
  1066   1064     pNew->nSelectRow = p->nSelectRow;
  1067   1065     pNew->pWith = withDup(db, p->pWith);
  1068   1066     return pNew;
  1069   1067   }
  1070   1068   #else
  1071   1069   Select *sqlite3SelectDup(sqlite3 *db, Select *p, int flags){
  1072   1070     assert( p==0 );
................................................................................
  2331   2329   ** Generate code to move content from registers iFrom...iFrom+nReg-1
  2332   2330   ** over to iTo..iTo+nReg-1. Keep the column cache up-to-date.
  2333   2331   */
  2334   2332   void sqlite3ExprCodeMove(Parse *pParse, int iFrom, int iTo, int nReg){
  2335   2333     int i;
  2336   2334     struct yColCache *p;
  2337   2335     assert( iFrom>=iTo+nReg || iFrom+nReg<=iTo );
  2338         -  sqlite3VdbeAddOp3(pParse->pVdbe, OP_Move, iFrom, iTo, nReg-1);
         2336  +  sqlite3VdbeAddOp3(pParse->pVdbe, OP_Move, iFrom, iTo, nReg);
  2339   2337     for(i=0, p=pParse->aColCache; i<SQLITE_N_COLCACHE; i++, p++){
  2340   2338       int x = p->iReg;
  2341   2339       if( x>=iFrom && x<iFrom+nReg ){
  2342   2340         p->iReg += iTo-iFrom;
  2343   2341       }
  2344   2342     }
  2345   2343   }
................................................................................
  2732   2730               testcase( pDef->funcFlags & OPFLAG_LENGTHARG );
  2733   2731               pFarg->a[0].pExpr->op2 = 
  2734   2732                     pDef->funcFlags & (OPFLAG_LENGTHARG|OPFLAG_TYPEOFARG);
  2735   2733             }
  2736   2734           }
  2737   2735   
  2738   2736           sqlite3ExprCachePush(pParse);     /* Ticket 2ea2425d34be */
  2739         -        sqlite3ExprCodeExprList(pParse, pFarg, r1, 
         2737  +        sqlite3ExprCodeExprList(pParse, pFarg, r1,
  2740   2738                                   SQLITE_ECEL_DUP|SQLITE_ECEL_FACTOR);
  2741   2739           sqlite3ExprCachePop(pParse, 1);   /* Ticket 2ea2425d34be */
  2742   2740         }else{
  2743   2741           r1 = 0;
  2744   2742         }
  2745   2743   #ifndef SQLITE_OMIT_VIRTUALTABLE
  2746   2744         /* Possibly overload the function if the first argument is

Changes to src/pragma.c.

  1871   1871         /* Do the b-tree integrity checks */
  1872   1872         sqlite3VdbeAddOp3(v, OP_IntegrityCk, 2, cnt, 1);
  1873   1873         sqlite3VdbeChangeP5(v, (u8)i);
  1874   1874         addr = sqlite3VdbeAddOp1(v, OP_IsNull, 2); VdbeCoverage(v);
  1875   1875         sqlite3VdbeAddOp4(v, OP_String8, 0, 3, 0,
  1876   1876            sqlite3MPrintf(db, "*** in database %s ***\n", db->aDb[i].zName),
  1877   1877            P4_DYNAMIC);
  1878         -      sqlite3VdbeAddOp2(v, OP_Move, 2, 4);
         1878  +      sqlite3VdbeAddOp3(v, OP_Move, 2, 4, 1);
  1879   1879         sqlite3VdbeAddOp3(v, OP_Concat, 4, 3, 2);
  1880   1880         sqlite3VdbeAddOp2(v, OP_ResultRow, 2, 1);
  1881   1881         sqlite3VdbeJumpHere(v, addr);
  1882   1882   
  1883   1883         /* Make sure all the indices are constructed correctly.
  1884   1884         */
  1885   1885         for(x=sqliteHashFirst(pTbls); x && !isQuick; x=sqliteHashNext(x)){

Changes to src/select.c.

    10     10   **
    11     11   *************************************************************************
    12     12   ** This file contains C code routines that are called by the parser
    13     13   ** to handle SELECT statements in SQLite.
    14     14   */
    15     15   #include "sqliteInt.h"
    16     16   
           17  +/*
           18  +** An instance of the following object is used to record information about
           19  +** how to process the DISTINCT keyword, to simplify passing that information
           20  +** into the selectInnerLoop() routine.
           21  +*/
           22  +typedef struct DistinctCtx DistinctCtx;
           23  +struct DistinctCtx {
           24  +  u8 isTnct;      /* True if the DISTINCT keyword is present */
           25  +  u8 eTnctType;   /* One of the WHERE_DISTINCT_* operators */
           26  +  int tabTnct;    /* Ephemeral table used for DISTINCT processing */
           27  +  int addrTnct;   /* Address of OP_OpenEphemeral opcode for tabTnct */
           28  +};
           29  +
           30  +/*
           31  +** An instance of the following object is used to record information about
           32  +** the ORDER BY (or GROUP BY) clause of query is being coded.
           33  +*/
           34  +typedef struct SortCtx SortCtx;
           35  +struct SortCtx {
           36  +  ExprList *pOrderBy;   /* The ORDER BY (or GROUP BY clause) */
           37  +  int nOBSat;           /* Number of ORDER BY terms satisfied by indices */
           38  +  int iECursor;         /* Cursor number for the sorter */
           39  +  int regReturn;        /* Register holding block-output return address */
           40  +  int labelBkOut;       /* Start label for the block-output subroutine */
           41  +  int addrSortIndex;    /* Address of the OP_SorterOpen or OP_OpenEphemeral */
           42  +  u8 sortFlags;         /* Zero or more SORTFLAG_* bits */
           43  +};
           44  +#define SORTFLAG_UseSorter  0x01   /* Use SorterOpen instead of OpenEphemeral */
    17     45   
    18     46   /*
    19     47   ** Delete all the content of a Select structure but do not deallocate
    20     48   ** the select structure itself.
    21     49   */
    22     50   static void clearSelect(sqlite3 *db, Select *p){
    23     51     sqlite3ExprListDelete(db, p->pEList);
................................................................................
    83    111     pNew->selFlags = selFlags;
    84    112     pNew->op = TK_SELECT;
    85    113     pNew->pLimit = pLimit;
    86    114     pNew->pOffset = pOffset;
    87    115     assert( pOffset==0 || pLimit!=0 );
    88    116     pNew->addrOpenEphm[0] = -1;
    89    117     pNew->addrOpenEphm[1] = -1;
    90         -  pNew->addrOpenEphm[2] = -1;
    91    118     if( db->mallocFailed ) {
    92    119       clearSelect(db, pNew);
    93    120       if( pNew!=&standin ) sqlite3DbFree(db, pNew);
    94    121       pNew = 0;
    95    122     }else{
    96    123       assert( pNew->pSrc!=0 || pParse->nErr>0 );
    97    124     }
................................................................................
   415    442                        isOuter, &p->pWhere);
   416    443         }
   417    444       }
   418    445     }
   419    446     return 0;
   420    447   }
   421    448   
          449  +/* Forward reference */
          450  +static KeyInfo *keyInfoFromExprList(
          451  +  Parse *pParse,       /* Parsing context */
          452  +  ExprList *pList,     /* Form the KeyInfo object from this ExprList */
          453  +  int iStart,          /* Begin with this column of pList */
          454  +  int nExtra           /* Add this many extra columns to the end */
          455  +);
          456  +
   422    457   /*
   423         -** Insert code into "v" that will push the record on the top of the
   424         -** stack into the sorter.
          458  +** Insert code into "v" that will push the record in register regData
          459  +** into the sorter.
   425    460   */
   426    461   static void pushOntoSorter(
   427    462     Parse *pParse,         /* Parser context */
   428         -  ExprList *pOrderBy,    /* The ORDER BY clause */
          463  +  SortCtx *pSort,        /* Information about the ORDER BY clause */
   429    464     Select *pSelect,       /* The whole SELECT statement */
   430    465     int regData            /* Register holding data to be sorted */
   431    466   ){
   432    467     Vdbe *v = pParse->pVdbe;
   433         -  int nExpr = pOrderBy->nExpr;
          468  +  int nExpr = pSort->pOrderBy->nExpr;
   434    469     int regBase = sqlite3GetTempRange(pParse, nExpr+2);
   435    470     int regRecord = sqlite3GetTempReg(pParse);
          471  +  int nOBSat = pSort->nOBSat;
   436    472     int op;
   437    473     sqlite3ExprCacheClear(pParse);
   438         -  sqlite3ExprCodeExprList(pParse, pOrderBy, regBase, 0);
   439         -  sqlite3VdbeAddOp2(v, OP_Sequence, pOrderBy->iECursor, regBase+nExpr);
          474  +  sqlite3ExprCodeExprList(pParse, pSort->pOrderBy, regBase, 0);
          475  +  sqlite3VdbeAddOp2(v, OP_Sequence, pSort->iECursor, regBase+nExpr);
   440    476     sqlite3ExprCodeMove(pParse, regData, regBase+nExpr+1, 1);
   441         -  sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase, nExpr + 2, regRecord);
   442         -  if( pSelect->selFlags & SF_UseSorter ){
          477  +  sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase+nOBSat, nExpr+2-nOBSat, regRecord);
          478  +  if( nOBSat>0 ){
          479  +    int regPrevKey;   /* The first nOBSat columns of the previous row */
          480  +    int addrFirst;    /* Address of the OP_IfNot opcode */
          481  +    int addrJmp;      /* Address of the OP_Jump opcode */
          482  +    VdbeOp *pOp;      /* Opcode that opens the sorter */
          483  +    int nKey;         /* Number of sorting key columns, including OP_Sequence */
          484  +
          485  +    addrFirst = sqlite3VdbeAddOp1(v, OP_IfNot, regBase+nExpr); VdbeCoverage(v);
          486  +    pOp = sqlite3VdbeGetOp(v, pSort->addrSortIndex);
          487  +    pOp->opcode = OP_OpenEphemeral;
          488  +    pSort->sortFlags &= ~SORTFLAG_UseSorter;
          489  +    nKey = nExpr - pSort->nOBSat + 1;
          490  +    pOp->p2 = nKey + 1;
          491  +    regPrevKey = pParse->nMem+1;
          492  +    pParse->nMem += pSort->nOBSat;
          493  +    sqlite3VdbeAddOp4(v, OP_Compare, regPrevKey, regBase, pSort->nOBSat,
          494  +                      (char*)pOp->p4.pKeyInfo, P4_KEYINFO);
          495  +    pOp->p4.pKeyInfo = keyInfoFromExprList(pParse, pSort->pOrderBy, nOBSat, 1);
          496  +    addrJmp = sqlite3VdbeCurrentAddr(v);
          497  +    sqlite3VdbeAddOp3(v, OP_Jump, addrJmp+1, 0, addrJmp+1); VdbeCoverage(v);
          498  +    pSort->labelBkOut = sqlite3VdbeMakeLabel(v);
          499  +    pSort->regReturn = ++pParse->nMem;
          500  +    sqlite3VdbeAddOp2(v, OP_Gosub, pSort->regReturn, pSort->labelBkOut);
          501  +    sqlite3VdbeAddOp1(v, OP_ClearEphem, pSort->iECursor);
          502  +    sqlite3VdbeJumpHere(v, addrFirst);
          503  +    sqlite3VdbeAddOp3(v, OP_Move, regBase, regPrevKey, pSort->nOBSat);
          504  +    sqlite3VdbeJumpHere(v, addrJmp);
          505  +  }
          506  +  if( pSort->sortFlags & SORTFLAG_UseSorter ){
   443    507       op = OP_SorterInsert;
   444    508     }else{
   445    509       op = OP_IdxInsert;
   446    510     }
   447         -  sqlite3VdbeAddOp2(v, op, pOrderBy->iECursor, regRecord);
          511  +  sqlite3VdbeAddOp2(v, op, pSort->iECursor, regRecord);
   448    512     sqlite3ReleaseTempReg(pParse, regRecord);
   449    513     sqlite3ReleaseTempRange(pParse, regBase, nExpr+2);
   450    514     if( pSelect->iLimit ){
   451    515       int addr1, addr2;
   452    516       int iLimit;
   453    517       if( pSelect->iOffset ){
   454    518         iLimit = pSelect->iOffset+1;
................................................................................
   455    519       }else{
   456    520         iLimit = pSelect->iLimit;
   457    521       }
   458    522       addr1 = sqlite3VdbeAddOp1(v, OP_IfZero, iLimit); VdbeCoverage(v);
   459    523       sqlite3VdbeAddOp2(v, OP_AddImm, iLimit, -1);
   460    524       addr2 = sqlite3VdbeAddOp0(v, OP_Goto);
   461    525       sqlite3VdbeJumpHere(v, addr1);
   462         -    sqlite3VdbeAddOp1(v, OP_Last, pOrderBy->iECursor);
   463         -    sqlite3VdbeAddOp1(v, OP_Delete, pOrderBy->iECursor);
          526  +    sqlite3VdbeAddOp1(v, OP_Last, pSort->iECursor);
          527  +    sqlite3VdbeAddOp1(v, OP_Delete, pSort->iECursor);
   464    528       sqlite3VdbeJumpHere(v, addr2);
   465    529     }
   466    530   }
   467    531   
   468    532   /*
   469    533   ** Add code to implement the OFFSET
   470    534   */
................................................................................
   530    594       return 1;
   531    595     }else{
   532    596       return 0;
   533    597     }
   534    598   }
   535    599   #endif
   536    600   
   537         -/*
   538         -** An instance of the following object is used to record information about
   539         -** how to process the DISTINCT keyword, to simplify passing that information
   540         -** into the selectInnerLoop() routine.
   541         -*/
   542         -typedef struct DistinctCtx DistinctCtx;
   543         -struct DistinctCtx {
   544         -  u8 isTnct;      /* True if the DISTINCT keyword is present */
   545         -  u8 eTnctType;   /* One of the WHERE_DISTINCT_* operators */
   546         -  int tabTnct;    /* Ephemeral table used for DISTINCT processing */
   547         -  int addrTnct;   /* Address of OP_OpenEphemeral opcode for tabTnct */
   548         -};
   549         -
   550    601   /*
   551    602   ** This routine generates the code for the inside of the inner loop
   552    603   ** of a SELECT.
   553    604   **
   554    605   ** If srcTab is negative, then the pEList expressions
   555    606   ** are evaluated in order to get the data for this row.  If srcTab is
   556    607   ** zero or more, then data is pulled from srcTab and pEList is used only 
................................................................................
   557    608   ** to get number columns and the datatype for each column.
   558    609   */
   559    610   static void selectInnerLoop(
   560    611     Parse *pParse,          /* The parser context */
   561    612     Select *p,              /* The complete select statement being coded */
   562    613     ExprList *pEList,       /* List of values being extracted */
   563    614     int srcTab,             /* Pull data from this table */
   564         -  ExprList *pOrderBy,     /* If not NULL, sort results using this key */
   565         -  int nOBSat,             /* Terms of ORDER BY already satisfied */
          615  +  SortCtx *pSort,         /* If not NULL, info on how to process ORDER BY */
   566    616     DistinctCtx *pDistinct, /* If not NULL, info on how to process DISTINCT */
   567    617     SelectDest *pDest,      /* How to dispose of the results */
   568    618     int iContinue,          /* Jump here to continue with next row */
   569    619     int iBreak              /* Jump here to break out of the inner loop */
   570    620   ){
   571    621     Vdbe *v = pParse->pVdbe;
   572    622     int i;
................................................................................
   575    625     int eDest = pDest->eDest;   /* How to dispose of results */
   576    626     int iParm = pDest->iSDParm; /* First argument to disposal method */
   577    627     int nResultCol;             /* Number of result columns */
   578    628   
   579    629     assert( v );
   580    630     assert( pEList!=0 );
   581    631     hasDistinct = pDistinct ? pDistinct->eTnctType : WHERE_DISTINCT_NOOP;
   582         -  if( pOrderBy==0 && !hasDistinct ){
          632  +  if( pSort && pSort->pOrderBy==0 ) pSort = 0;
          633  +  if( pSort==0 && !hasDistinct ){
   583    634       codeOffset(v, p->iOffset, iContinue);
   584    635     }
   585    636   
   586    637     /* Pull the requested columns.
   587    638     */
   588    639     nResultCol = pEList->nExpr;
   589    640   
................................................................................
   665    716   
   666    717         default: {
   667    718           assert( pDistinct->eTnctType==WHERE_DISTINCT_UNORDERED );
   668    719           codeDistinct(pParse, pDistinct->tabTnct, iContinue, nResultCol, regResult);
   669    720           break;
   670    721         }
   671    722       }
   672         -    if( pOrderBy==0 ){
          723  +    if( pSort==0 ){
   673    724         codeOffset(v, p->iOffset, iContinue);
   674    725       }
   675    726     }
   676    727   
   677    728     switch( eDest ){
   678    729       /* In this mode, write each query result to the key of the temporary
   679    730       ** table iParm.
................................................................................
   713    764           ** on an ephemeral index. If the current row is already present
   714    765           ** in the index, do not write it to the output. If not, add the
   715    766           ** current row to the index and proceed with writing it to the
   716    767           ** output table as well.  */
   717    768           int addr = sqlite3VdbeCurrentAddr(v) + 4;
   718    769           sqlite3VdbeAddOp4Int(v, OP_Found, iParm+1, addr, r1, 0); VdbeCoverage(v);
   719    770           sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm+1, r1);
   720         -        assert( pOrderBy==0 );
          771  +        assert( pSort==0 );
   721    772         }
   722    773   #endif
   723         -      if( pOrderBy ){
   724         -        pushOntoSorter(pParse, pOrderBy, p, r1);
          774  +      if( pSort ){
          775  +        pushOntoSorter(pParse, pSort, p, r1);
   725    776         }else{
   726    777           int r2 = sqlite3GetTempReg(pParse);
   727    778           sqlite3VdbeAddOp2(v, OP_NewRowid, iParm, r2);
   728    779           sqlite3VdbeAddOp3(v, OP_Insert, iParm, r1, r2);
   729    780           sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
   730    781           sqlite3ReleaseTempReg(pParse, r2);
   731    782         }
................................................................................
   738    789       ** then there should be a single item on the stack.  Write this
   739    790       ** item into the set table with bogus data.
   740    791       */
   741    792       case SRT_Set: {
   742    793         assert( nResultCol==1 );
   743    794         pDest->affSdst =
   744    795                     sqlite3CompareAffinity(pEList->a[0].pExpr, pDest->affSdst);
   745         -      if( pOrderBy ){
          796  +      if( pSort ){
   746    797           /* At first glance you would think we could optimize out the
   747    798           ** ORDER BY in this case since the order of entries in the set
   748    799           ** does not matter.  But there might be a LIMIT clause, in which
   749    800           ** case the order does matter */
   750         -        pushOntoSorter(pParse, pOrderBy, p, regResult);
          801  +        pushOntoSorter(pParse, pSort, p, regResult);
   751    802         }else{
   752    803           int r1 = sqlite3GetTempReg(pParse);
   753    804           sqlite3VdbeAddOp4(v, OP_MakeRecord, regResult,1,r1, &pDest->affSdst, 1);
   754    805           sqlite3ExprCacheAffinityChange(pParse, regResult, 1);
   755    806           sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm, r1);
   756    807           sqlite3ReleaseTempReg(pParse, r1);
   757    808         }
................................................................................
   768    819   
   769    820       /* If this is a scalar select that is part of an expression, then
   770    821       ** store the results in the appropriate memory cell and break out
   771    822       ** of the scan loop.
   772    823       */
   773    824       case SRT_Mem: {
   774    825         assert( nResultCol==1 );
   775         -      if( pOrderBy ){
   776         -        pushOntoSorter(pParse, pOrderBy, p, regResult);
          826  +      if( pSort ){
          827  +        pushOntoSorter(pParse, pSort, p, regResult);
   777    828         }else{
   778    829           sqlite3ExprCodeMove(pParse, regResult, iParm, 1);
   779    830           /* The LIMIT clause will jump out of the loop for us */
   780    831         }
   781    832         break;
   782    833       }
   783    834   #endif /* #ifndef SQLITE_OMIT_SUBQUERY */
   784    835   
   785    836       case SRT_Coroutine:       /* Send data to a co-routine */
   786    837       case SRT_Output: {        /* Return the results */
   787    838         testcase( eDest==SRT_Coroutine );
   788    839         testcase( eDest==SRT_Output );
   789         -      if( pOrderBy ){
          840  +      if( pSort ){
   790    841           int r1 = sqlite3GetTempReg(pParse);
   791    842           sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nResultCol, r1);
   792         -        pushOntoSorter(pParse, pOrderBy, p, r1);
          843  +        pushOntoSorter(pParse, pSort, p, r1);
   793    844           sqlite3ReleaseTempReg(pParse, r1);
   794    845         }else if( eDest==SRT_Coroutine ){
   795    846           sqlite3VdbeAddOp1(v, OP_Yield, pDest->iSDParm);
   796    847         }else{
   797    848           sqlite3VdbeAddOp2(v, OP_ResultRow, regResult, nResultCol);
   798    849           sqlite3ExprCacheAffinityChange(pParse, regResult, nResultCol);
   799    850         }
................................................................................
   862    913   #endif
   863    914     }
   864    915   
   865    916     /* Jump to the end of the loop if the LIMIT is reached.  Except, if
   866    917     ** there is a sorter, in which case the sorter has already limited
   867    918     ** the output for us.
   868    919     */
   869         -  if( pOrderBy==0 && p->iLimit ){
          920  +  if( pSort==0 && p->iLimit ){
   870    921       sqlite3VdbeAddOp3(v, OP_IfZero, p->iLimit, iBreak, -1); VdbeCoverage(v);
   871    922     }
   872    923   }
   873    924   
   874    925   /*
   875    926   ** Allocate a KeyInfo object sufficient for an index of N key columns and
   876    927   ** X extra columns.
................................................................................
   933    984   ** then the KeyInfo structure is appropriate for initializing a virtual
   934    985   ** index to implement a DISTINCT test.
   935    986   **
   936    987   ** Space to hold the KeyInfo structure is obtain from malloc.  The calling
   937    988   ** function is responsible for seeing that this structure is eventually
   938    989   ** freed.
   939    990   */
   940         -static KeyInfo *keyInfoFromExprList(Parse *pParse, ExprList *pList, int nExtra){
          991  +static KeyInfo *keyInfoFromExprList(
          992  +  Parse *pParse,       /* Parsing context */
          993  +  ExprList *pList,     /* Form the KeyInfo object from this ExprList */
          994  +  int iStart,          /* Begin with this column of pList */
          995  +  int nExtra           /* Add this many extra columns to the end */
          996  +){
   941    997     int nExpr;
   942    998     KeyInfo *pInfo;
   943    999     struct ExprList_item *pItem;
   944   1000     sqlite3 *db = pParse->db;
   945   1001     int i;
   946   1002   
   947   1003     nExpr = pList->nExpr;
   948         -  pInfo = sqlite3KeyInfoAlloc(db, nExpr+nExtra, 1);
         1004  +  pInfo = sqlite3KeyInfoAlloc(db, nExpr+nExtra-iStart, 1);
   949   1005     if( pInfo ){
   950   1006       assert( sqlite3KeyInfoIsWriteable(pInfo) );
   951         -    for(i=0, pItem=pList->a; i<nExpr; i++, pItem++){
         1007  +    for(i=iStart, pItem=pList->a; i<nExpr; i++, pItem++){
   952   1008         CollSeq *pColl;
   953   1009         pColl = sqlite3ExprCollSeq(pParse, pItem->pExpr);
   954   1010         if( !pColl ) pColl = db->pDfltColl;
   955   1011         pInfo->aColl[i] = pColl;
   956   1012         pInfo->aSortOrder[i] = pItem->sortOrder;
   957   1013       }
   958   1014     }
................................................................................
  1051   1107   ** then the results were placed in a sorter.  After the loop is terminated
  1052   1108   ** we need to run the sorter and output the results.  The following
  1053   1109   ** routine generates the code needed to do that.
  1054   1110   */
  1055   1111   static void generateSortTail(
  1056   1112     Parse *pParse,    /* Parsing context */
  1057   1113     Select *p,        /* The SELECT statement */
         1114  +  SortCtx *pSort,   /* Information on the ORDER BY clause */
  1058   1115     int nColumn,      /* Number of columns of data */
  1059   1116     SelectDest *pDest /* Write the sorted results here */
  1060   1117   ){
  1061   1118     Vdbe *v = pParse->pVdbe;                     /* The prepared statement */
  1062   1119     int addrBreak = sqlite3VdbeMakeLabel(v);     /* Jump here to exit loop */
  1063   1120     int addrContinue = sqlite3VdbeMakeLabel(v);  /* Jump here for next cycle */
  1064   1121     int addr;
         1122  +  int addrOnce = 0;
  1065   1123     int iTab;
  1066   1124     int pseudoTab = 0;
  1067         -  ExprList *pOrderBy = p->pOrderBy;
  1068         -
         1125  +  ExprList *pOrderBy = pSort->pOrderBy;
  1069   1126     int eDest = pDest->eDest;
  1070   1127     int iParm = pDest->iSDParm;
  1071         -
  1072   1128     int regRow;
  1073   1129     int regRowid;
         1130  +  int nKey;
  1074   1131   
  1075         -  iTab = pOrderBy->iECursor;
         1132  +  if( pSort->labelBkOut ){
         1133  +    sqlite3VdbeAddOp2(v, OP_Gosub, pSort->regReturn, pSort->labelBkOut);
         1134  +    sqlite3VdbeAddOp2(v, OP_Goto, 0, addrBreak);
         1135  +    sqlite3VdbeResolveLabel(v, pSort->labelBkOut);
         1136  +    addrOnce = sqlite3CodeOnce(pParse); VdbeCoverage(v);
         1137  +  }
         1138  +  iTab = pSort->iECursor;
  1076   1139     regRow = sqlite3GetTempReg(pParse);
  1077   1140     if( eDest==SRT_Output || eDest==SRT_Coroutine ){
  1078   1141       pseudoTab = pParse->nTab++;
  1079   1142       sqlite3VdbeAddOp3(v, OP_OpenPseudo, pseudoTab, regRow, nColumn);
  1080   1143       regRowid = 0;
  1081   1144     }else{
  1082   1145       regRowid = sqlite3GetTempReg(pParse);
  1083   1146     }
  1084         -  if( p->selFlags & SF_UseSorter ){
         1147  +  nKey = pOrderBy->nExpr - pSort->nOBSat;
         1148  +  if( pSort->sortFlags & SORTFLAG_UseSorter ){
  1085   1149       int regSortOut = ++pParse->nMem;
  1086   1150       int ptab2 = pParse->nTab++;
  1087         -    sqlite3VdbeAddOp3(v, OP_OpenPseudo, ptab2, regSortOut, pOrderBy->nExpr+2);
         1151  +    sqlite3VdbeAddOp3(v, OP_OpenPseudo, ptab2, regSortOut, nKey+2);
         1152  +    if( addrOnce ) sqlite3VdbeJumpHere(v, addrOnce);
  1088   1153       addr = 1 + sqlite3VdbeAddOp2(v, OP_SorterSort, iTab, addrBreak);
  1089   1154       VdbeCoverage(v);
  1090   1155       codeOffset(v, p->iOffset, addrContinue);
  1091   1156       sqlite3VdbeAddOp2(v, OP_SorterData, iTab, regSortOut);
  1092         -    sqlite3VdbeAddOp3(v, OP_Column, ptab2, pOrderBy->nExpr+1, regRow);
         1157  +    sqlite3VdbeAddOp3(v, OP_Column, ptab2, nKey+1, regRow);
  1093   1158       sqlite3VdbeChangeP5(v, OPFLAG_CLEARCACHE);
  1094   1159     }else{
         1160  +    if( addrOnce ) sqlite3VdbeJumpHere(v, addrOnce);
  1095   1161       addr = 1 + sqlite3VdbeAddOp2(v, OP_Sort, iTab, addrBreak); VdbeCoverage(v);
  1096   1162       codeOffset(v, p->iOffset, addrContinue);
  1097         -    sqlite3VdbeAddOp3(v, OP_Column, iTab, pOrderBy->nExpr+1, regRow);
         1163  +    sqlite3VdbeAddOp3(v, OP_Column, iTab, nKey+1, regRow);
  1098   1164     }
  1099   1165     switch( eDest ){
  1100   1166       case SRT_Table:
  1101   1167       case SRT_EphemTab: {
  1102   1168         testcase( eDest==SRT_Table );
  1103   1169         testcase( eDest==SRT_EphemTab );
  1104   1170         sqlite3VdbeAddOp2(v, OP_NewRowid, iParm, regRowid);
................................................................................
  1145   1211     }
  1146   1212     sqlite3ReleaseTempReg(pParse, regRow);
  1147   1213     sqlite3ReleaseTempReg(pParse, regRowid);
  1148   1214   
  1149   1215     /* The bottom of the loop
  1150   1216     */
  1151   1217     sqlite3VdbeResolveLabel(v, addrContinue);
  1152         -  if( p->selFlags & SF_UseSorter ){
         1218  +  if( pSort->sortFlags & SORTFLAG_UseSorter ){
  1153   1219       sqlite3VdbeAddOp2(v, OP_SorterNext, iTab, addr); VdbeCoverage(v);
  1154   1220     }else{
  1155   1221       sqlite3VdbeAddOp2(v, OP_Next, iTab, addr); VdbeCoverage(v);
  1156   1222     }
         1223  +  if( pSort->regReturn ) sqlite3VdbeAddOp1(v, OP_Return, pSort->regReturn);
  1157   1224     sqlite3VdbeResolveLabel(v, addrBreak);
  1158   1225     if( eDest==SRT_Output || eDest==SRT_Coroutine ){
  1159   1226       sqlite3VdbeAddOp2(v, OP_Close, pseudoTab, 0);
  1160   1227     }
  1161   1228   }
  1162   1229   
  1163   1230   /*
................................................................................
  1915   1982     }
  1916   1983     sqlite3VdbeAddOp1(v, OP_Delete, iQueue);
  1917   1984   
  1918   1985     /* Output the single row in Current */
  1919   1986     addrCont = sqlite3VdbeMakeLabel(v);
  1920   1987     codeOffset(v, regOffset, addrCont);
  1921   1988     selectInnerLoop(pParse, p, p->pEList, iCurrent,
  1922         -      0, 0, 0, pDest, addrCont, addrBreak);
         1989  +      0, 0, pDest, addrCont, addrBreak);
  1923   1990     if( regLimit ){
  1924   1991       sqlite3VdbeAddOp3(v, OP_IfZero, regLimit, addrBreak, -1);
  1925   1992       VdbeCoverage(v);
  1926   1993     }
  1927   1994     sqlite3VdbeResolveLabel(v, addrCont);
  1928   1995   
  1929   1996     /* Execute the recursive SELECT taking the single row in Current as
................................................................................
  2189   2256           }
  2190   2257           iBreak = sqlite3VdbeMakeLabel(v);
  2191   2258           iCont = sqlite3VdbeMakeLabel(v);
  2192   2259           computeLimitRegisters(pParse, p, iBreak);
  2193   2260           sqlite3VdbeAddOp2(v, OP_Rewind, unionTab, iBreak); VdbeCoverage(v);
  2194   2261           iStart = sqlite3VdbeCurrentAddr(v);
  2195   2262           selectInnerLoop(pParse, p, p->pEList, unionTab,
  2196         -                        0, 0, 0, &dest, iCont, iBreak);
         2263  +                        0, 0, &dest, iCont, iBreak);
  2197   2264           sqlite3VdbeResolveLabel(v, iCont);
  2198   2265           sqlite3VdbeAddOp2(v, OP_Next, unionTab, iStart); VdbeCoverage(v);
  2199   2266           sqlite3VdbeResolveLabel(v, iBreak);
  2200   2267           sqlite3VdbeAddOp2(v, OP_Close, unionTab, 0);
  2201   2268         }
  2202   2269         break;
  2203   2270       }
................................................................................
  2267   2334         computeLimitRegisters(pParse, p, iBreak);
  2268   2335         sqlite3VdbeAddOp2(v, OP_Rewind, tab1, iBreak); VdbeCoverage(v);
  2269   2336         r1 = sqlite3GetTempReg(pParse);
  2270   2337         iStart = sqlite3VdbeAddOp2(v, OP_RowKey, tab1, r1);
  2271   2338         sqlite3VdbeAddOp4Int(v, OP_NotFound, tab2, iCont, r1, 0); VdbeCoverage(v);
  2272   2339         sqlite3ReleaseTempReg(pParse, r1);
  2273   2340         selectInnerLoop(pParse, p, p->pEList, tab1,
  2274         -                      0, 0, 0, &dest, iCont, iBreak);
         2341  +                      0, 0, &dest, iCont, iBreak);
  2275   2342         sqlite3VdbeResolveLabel(v, iCont);
  2276   2343         sqlite3VdbeAddOp2(v, OP_Next, tab1, iStart); VdbeCoverage(v);
  2277   2344         sqlite3VdbeResolveLabel(v, iBreak);
  2278   2345         sqlite3VdbeAddOp2(v, OP_Close, tab2, 0);
  2279   2346         sqlite3VdbeAddOp2(v, OP_Close, tab1, 0);
  2280   2347         break;
  2281   2348       }
................................................................................
  4306   4373         Expr *pE = pFunc->pExpr;
  4307   4374         assert( !ExprHasProperty(pE, EP_xIsSelect) );
  4308   4375         if( pE->x.pList==0 || pE->x.pList->nExpr!=1 ){
  4309   4376           sqlite3ErrorMsg(pParse, "DISTINCT aggregates must have exactly one "
  4310   4377              "argument");
  4311   4378           pFunc->iDistinct = -1;
  4312   4379         }else{
  4313         -        KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pE->x.pList, 0);
         4380  +        KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pE->x.pList, 0, 0);
  4314   4381           sqlite3VdbeAddOp4(v, OP_OpenEphemeral, pFunc->iDistinct, 0, 0,
  4315   4382                             (char*)pKeyInfo, P4_KEYINFO);
  4316   4383         }
  4317   4384       }
  4318   4385     }
  4319   4386   }
  4320   4387   
................................................................................
  4461   4528     int i, j;              /* Loop counters */
  4462   4529     WhereInfo *pWInfo;     /* Return from sqlite3WhereBegin() */
  4463   4530     Vdbe *v;               /* The virtual machine under construction */
  4464   4531     int isAgg;             /* True for select lists like "count(*)" */
  4465   4532     ExprList *pEList;      /* List of columns to extract. */
  4466   4533     SrcList *pTabList;     /* List of tables to select from */
  4467   4534     Expr *pWhere;          /* The WHERE clause.  May be NULL */
  4468         -  ExprList *pOrderBy;    /* The ORDER BY clause.  May be NULL */
  4469   4535     ExprList *pGroupBy;    /* The GROUP BY clause.  May be NULL */
  4470   4536     Expr *pHaving;         /* The HAVING clause.  May be NULL */
  4471   4537     int rc = 1;            /* Value to return from this function */
  4472         -  int addrSortIndex;     /* Address of an OP_OpenEphemeral instruction */
  4473   4538     DistinctCtx sDistinct; /* Info on how to code the DISTINCT keyword */
         4539  +  SortCtx sSort;         /* Info on how to code the ORDER BY clause */
  4474   4540     AggInfo sAggInfo;      /* Information used by aggregate queries */
  4475   4541     int iEnd;              /* Address of the end of the query */
  4476   4542     sqlite3 *db;           /* The database connection */
  4477   4543   
  4478   4544   #ifndef SQLITE_OMIT_EXPLAIN
  4479   4545     int iRestoreSelectId = pParse->iSelectId;
  4480   4546     pParse->iSelectId = pParse->iNextSelectId++;
................................................................................
  4493   4559       /* If ORDER BY makes no difference in the output then neither does
  4494   4560       ** DISTINCT so it can be removed too. */
  4495   4561       sqlite3ExprListDelete(db, p->pOrderBy);
  4496   4562       p->pOrderBy = 0;
  4497   4563       p->selFlags &= ~SF_Distinct;
  4498   4564     }
  4499   4565     sqlite3SelectPrep(pParse, p, 0);
  4500         -  pOrderBy = p->pOrderBy;
         4566  +  memset(&sSort, 0, sizeof(sSort));
         4567  +  sSort.pOrderBy = p->pOrderBy;
  4501   4568     pTabList = p->pSrc;
  4502   4569     pEList = p->pEList;
  4503   4570     if( pParse->nErr || db->mallocFailed ){
  4504   4571       goto select_end;
  4505   4572     }
  4506   4573     isAgg = (p->selFlags & SF_Aggregate)!=0;
  4507   4574     assert( pEList!=0 );
................................................................................
  4615   4682       }
  4616   4683       if( /*pParse->nErr ||*/ db->mallocFailed ){
  4617   4684         goto select_end;
  4618   4685       }
  4619   4686       pParse->nHeight -= sqlite3SelectExprHeight(p);
  4620   4687       pTabList = p->pSrc;
  4621   4688       if( !IgnorableOrderby(pDest) ){
  4622         -      pOrderBy = p->pOrderBy;
         4689  +      sSort.pOrderBy = p->pOrderBy;
  4623   4690       }
  4624   4691     }
  4625   4692     pEList = p->pEList;
  4626   4693   #endif
  4627   4694     pWhere = p->pWhere;
  4628   4695     pGroupBy = p->pGroupBy;
  4629   4696     pHaving = p->pHaving;
................................................................................
  4642   4709     /* If there is both a GROUP BY and an ORDER BY clause and they are
  4643   4710     ** identical, then disable the ORDER BY clause since the GROUP BY
  4644   4711     ** will cause elements to come out in the correct order.  This is
  4645   4712     ** an optimization - the correct answer should result regardless.
  4646   4713     ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER
  4647   4714     ** to disable this optimization for testing purposes.
  4648   4715     */
  4649         -  if( sqlite3ExprListCompare(p->pGroupBy, pOrderBy, -1)==0
         4716  +  if( sqlite3ExprListCompare(p->pGroupBy, sSort.pOrderBy, -1)==0
  4650   4717            && OptimizationEnabled(db, SQLITE_GroupByOrder) ){
  4651         -    pOrderBy = 0;
         4718  +    sSort.pOrderBy = 0;
  4652   4719     }
  4653   4720   
  4654   4721     /* If the query is DISTINCT with an ORDER BY but is not an aggregate, and 
  4655   4722     ** if the select-list is the same as the ORDER BY list, then this query
  4656   4723     ** can be rewritten as a GROUP BY. In other words, this:
  4657   4724     **
  4658   4725     **     SELECT DISTINCT xyz FROM ... ORDER BY xyz
................................................................................
  4663   4730     **
  4664   4731     ** The second form is preferred as a single index (or temp-table) may be 
  4665   4732     ** used for both the ORDER BY and DISTINCT processing. As originally 
  4666   4733     ** written the query must use a temp-table for at least one of the ORDER 
  4667   4734     ** BY and DISTINCT, and an index or separate temp-table for the other.
  4668   4735     */
  4669   4736     if( (p->selFlags & (SF_Distinct|SF_Aggregate))==SF_Distinct 
  4670         -   && sqlite3ExprListCompare(pOrderBy, p->pEList, -1)==0
         4737  +   && sqlite3ExprListCompare(sSort.pOrderBy, p->pEList, -1)==0
  4671   4738     ){
  4672   4739       p->selFlags &= ~SF_Distinct;
  4673   4740       p->pGroupBy = sqlite3ExprListDup(db, p->pEList, 0);
  4674   4741       pGroupBy = p->pGroupBy;
  4675         -    pOrderBy = 0;
         4742  +    sSort.pOrderBy = 0;
  4676   4743       /* Notice that even thought SF_Distinct has been cleared from p->selFlags,
  4677   4744       ** the sDistinct.isTnct is still set.  Hence, isTnct represents the
  4678   4745       ** original setting of the SF_Distinct flag, not the current setting */
  4679   4746       assert( sDistinct.isTnct );
  4680   4747     }
  4681   4748   
  4682   4749     /* If there is an ORDER BY clause, then this sorting
  4683   4750     ** index might end up being unused if the data can be 
  4684   4751     ** extracted in pre-sorted order.  If that is the case, then the
  4685   4752     ** OP_OpenEphemeral instruction will be changed to an OP_Noop once
  4686   4753     ** we figure out that the sorting index is not needed.  The addrSortIndex
  4687   4754     ** variable is used to facilitate that change.
  4688   4755     */
  4689         -  if( pOrderBy ){
         4756  +  if( sSort.pOrderBy ){
  4690   4757       KeyInfo *pKeyInfo;
  4691         -    pKeyInfo = keyInfoFromExprList(pParse, pOrderBy, 0);
  4692         -    pOrderBy->iECursor = pParse->nTab++;
  4693         -    p->addrOpenEphm[2] = addrSortIndex =
         4758  +    pKeyInfo = keyInfoFromExprList(pParse, sSort.pOrderBy, 0, 0);
         4759  +    sSort.iECursor = pParse->nTab++;
         4760  +    sSort.addrSortIndex =
  4694   4761         sqlite3VdbeAddOp4(v, OP_OpenEphemeral,
  4695         -                           pOrderBy->iECursor, pOrderBy->nExpr+2, 0,
         4762  +                           sSort.iECursor, sSort.pOrderBy->nExpr+2, 0,
  4696   4763                              (char*)pKeyInfo, P4_KEYINFO);
  4697   4764     }else{
  4698         -    addrSortIndex = -1;
         4765  +    sSort.addrSortIndex = -1;
  4699   4766     }
  4700   4767   
  4701   4768     /* If the output is destined for a temporary table, open that table.
  4702   4769     */
  4703   4770     if( pDest->eDest==SRT_EphemTab ){
  4704   4771       sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pDest->iSDParm, pEList->nExpr);
  4705   4772     }
  4706   4773   
  4707   4774     /* Set the limiter.
  4708   4775     */
  4709   4776     iEnd = sqlite3VdbeMakeLabel(v);
  4710   4777     p->nSelectRow = LARGEST_INT64;
  4711   4778     computeLimitRegisters(pParse, p, iEnd);
  4712         -  if( p->iLimit==0 && addrSortIndex>=0 ){
  4713         -    sqlite3VdbeGetOp(v, addrSortIndex)->opcode = OP_SorterOpen;
  4714         -    p->selFlags |= SF_UseSorter;
         4779  +  if( p->iLimit==0 && sSort.addrSortIndex>=0 ){
         4780  +    sqlite3VdbeGetOp(v, sSort.addrSortIndex)->opcode = OP_SorterOpen;
         4781  +    sSort.sortFlags |= SORTFLAG_UseSorter;
  4715   4782     }
  4716   4783   
  4717   4784     /* Open a virtual index to use for the distinct set.
  4718   4785     */
  4719   4786     if( p->selFlags & SF_Distinct ){
  4720   4787       sDistinct.tabTnct = pParse->nTab++;
  4721   4788       sDistinct.addrTnct = sqlite3VdbeAddOp4(v, OP_OpenEphemeral,
  4722   4789                                   sDistinct.tabTnct, 0, 0,
  4723         -                                (char*)keyInfoFromExprList(pParse, p->pEList, 0),
         4790  +                                (char*)keyInfoFromExprList(pParse, p->pEList,0,0),
  4724   4791                                   P4_KEYINFO);
  4725   4792       sqlite3VdbeChangeP5(v, BTREE_UNORDERED);
  4726   4793       sDistinct.eTnctType = WHERE_DISTINCT_UNORDERED;
  4727   4794     }else{
  4728   4795       sDistinct.eTnctType = WHERE_DISTINCT_NOOP;
  4729   4796     }
  4730   4797   
  4731   4798     if( !isAgg && pGroupBy==0 ){
  4732   4799       /* No aggregate functions and no GROUP BY clause */
  4733   4800       u16 wctrlFlags = (sDistinct.isTnct ? WHERE_WANT_DISTINCT : 0);
  4734         -    int nOBSat;
  4735   4801   
  4736   4802       /* Begin the database scan. */
  4737         -    pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pOrderBy, p->pEList,
  4738         -                               wctrlFlags, 0);
         4803  +    pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, sSort.pOrderBy,
         4804  +                               p->pEList, wctrlFlags, 0);
  4739   4805       if( pWInfo==0 ) goto select_end;
  4740   4806       if( sqlite3WhereOutputRowCount(pWInfo) < p->nSelectRow ){
  4741   4807         p->nSelectRow = sqlite3WhereOutputRowCount(pWInfo);
  4742   4808       }
  4743   4809       if( sDistinct.isTnct && sqlite3WhereIsDistinct(pWInfo) ){
  4744   4810         sDistinct.eTnctType = sqlite3WhereIsDistinct(pWInfo);
  4745   4811       }
  4746         -    nOBSat = sqlite3WhereIsOrdered(pWInfo);
  4747         -    if( pOrderBy && nOBSat==pOrderBy->nExpr ){ pOrderBy = 0;  nOBSat = 0; }
         4812  +    if( sSort.pOrderBy ){
         4813  +      sSort.nOBSat = sqlite3WhereIsOrdered(pWInfo);
         4814  +      if( sSort.nOBSat==sSort.pOrderBy->nExpr ){
         4815  +        sSort.pOrderBy = 0;
         4816  +      }
         4817  +    }
  4748   4818   
  4749   4819       /* If sorting index that was created by a prior OP_OpenEphemeral 
  4750   4820       ** instruction ended up not being needed, then change the OP_OpenEphemeral
  4751   4821       ** into an OP_Noop.
  4752   4822       */
  4753         -    if( addrSortIndex>=0 && pOrderBy==0 ){
  4754         -      sqlite3VdbeChangeToNoop(v, addrSortIndex);
  4755         -      p->addrOpenEphm[2] = -1;
         4823  +    if( sSort.addrSortIndex>=0 && sSort.pOrderBy==0 ){
         4824  +      sqlite3VdbeChangeToNoop(v, sSort.addrSortIndex);
  4756   4825       }
  4757   4826   
  4758   4827       /* Use the standard inner loop. */
  4759         -    selectInnerLoop(pParse, p, pEList, -1, pOrderBy, nOBSat, &sDistinct, pDest,
         4828  +    selectInnerLoop(pParse, p, pEList, -1, &sSort, &sDistinct, pDest,
  4760   4829                       sqlite3WhereContinueLabel(pWInfo),
  4761   4830                       sqlite3WhereBreakLabel(pWInfo));
  4762   4831   
  4763   4832       /* End the database scan loop.
  4764   4833       */
  4765   4834       sqlite3WhereEnd(pWInfo);
  4766   4835     }else{
................................................................................
  4808   4877       sNC.pParse = pParse;
  4809   4878       sNC.pSrcList = pTabList;
  4810   4879       sNC.pAggInfo = &sAggInfo;
  4811   4880       sAggInfo.mnReg = pParse->nMem+1;
  4812   4881       sAggInfo.nSortingColumn = pGroupBy ? pGroupBy->nExpr+1 : 0;
  4813   4882       sAggInfo.pGroupBy = pGroupBy;
  4814   4883       sqlite3ExprAnalyzeAggList(&sNC, pEList);
  4815         -    sqlite3ExprAnalyzeAggList(&sNC, pOrderBy);
         4884  +    sqlite3ExprAnalyzeAggList(&sNC, sSort.pOrderBy);
  4816   4885       if( pHaving ){
  4817   4886         sqlite3ExprAnalyzeAggregates(&sNC, pHaving);
  4818   4887       }
  4819   4888       sAggInfo.nAccumulator = sAggInfo.nColumn;
  4820   4889       for(i=0; i<sAggInfo.nFunc; i++){
  4821   4890         assert( !ExprHasProperty(sAggInfo.aFunc[i].pExpr, EP_xIsSelect) );
  4822   4891         sNC.ncFlags |= NC_InAggFunc;
................................................................................
  4842   4911   
  4843   4912         /* If there is a GROUP BY clause we might need a sorting index to
  4844   4913         ** implement it.  Allocate that sorting index now.  If it turns out
  4845   4914         ** that we do not need it after all, the OP_SorterOpen instruction
  4846   4915         ** will be converted into a Noop.  
  4847   4916         */
  4848   4917         sAggInfo.sortingIdx = pParse->nTab++;
  4849         -      pKeyInfo = keyInfoFromExprList(pParse, pGroupBy, 0);
         4918  +      pKeyInfo = keyInfoFromExprList(pParse, pGroupBy, 0, 0);
  4850   4919         addrSortingIdx = sqlite3VdbeAddOp4(v, OP_SorterOpen, 
  4851   4920             sAggInfo.sortingIdx, sAggInfo.nSortingColumn, 
  4852   4921             0, (char*)pKeyInfo, P4_KEYINFO);
  4853   4922   
  4854   4923         /* Initialize memory locations used by GROUP BY aggregate processing
  4855   4924         */
  4856   4925         iUseFlag = ++pParse->nMem;
................................................................................
  4871   4940   
  4872   4941         /* Begin a loop that will extract all source rows in GROUP BY order.
  4873   4942         ** This might involve two separate loops with an OP_Sort in between, or
  4874   4943         ** it might be a single loop that uses an index to extract information
  4875   4944         ** in the right order to begin with.
  4876   4945         */
  4877   4946         sqlite3VdbeAddOp2(v, OP_Gosub, regReset, addrReset);
  4878         -      pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pGroupBy, 0, 
         4947  +      pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pGroupBy, 0,
  4879   4948                                    WHERE_GROUPBY, 0);
  4880   4949         if( pWInfo==0 ) goto select_end;
  4881   4950         if( sqlite3WhereIsOrdered(pWInfo)==pGroupBy->nExpr ){
  4882   4951           /* The optimizer is able to deliver rows in group by order so
  4883   4952           ** we do not have to sort.  The OP_OpenEphemeral table will be
  4884   4953           ** cancelled later because we still need to use the pKeyInfo
  4885   4954           */
................................................................................
  5025   5094         sqlite3VdbeResolveLabel(v, addrOutputRow);
  5026   5095         addrOutputRow = sqlite3VdbeCurrentAddr(v);
  5027   5096         sqlite3VdbeAddOp2(v, OP_IfPos, iUseFlag, addrOutputRow+2); VdbeCoverage(v);
  5028   5097         VdbeComment((v, "Groupby result generator entry point"));
  5029   5098         sqlite3VdbeAddOp1(v, OP_Return, regOutputRow);
  5030   5099         finalizeAggFunctions(pParse, &sAggInfo);
  5031   5100         sqlite3ExprIfFalse(pParse, pHaving, addrOutputRow+1, SQLITE_JUMPIFNULL);
  5032         -      selectInnerLoop(pParse, p, p->pEList, -1, pOrderBy, 0,
         5101  +      selectInnerLoop(pParse, p, p->pEList, -1, &sSort,
  5033   5102                         &sDistinct, pDest,
  5034   5103                         addrOutputRow+1, addrSetAbort);
  5035   5104         sqlite3VdbeAddOp1(v, OP_Return, regOutputRow);
  5036   5105         VdbeComment((v, "end groupby result generator"));
  5037   5106   
  5038   5107         /* Generate a subroutine that will reset the group-by accumulator
  5039   5108         */
................................................................................
  5166   5235             VdbeComment((v, "%s() by index",
  5167   5236                   (flag==WHERE_ORDERBY_MIN?"min":"max")));
  5168   5237           }
  5169   5238           sqlite3WhereEnd(pWInfo);
  5170   5239           finalizeAggFunctions(pParse, &sAggInfo);
  5171   5240         }
  5172   5241   
  5173         -      pOrderBy = 0;
         5242  +      sSort.pOrderBy = 0;
  5174   5243         sqlite3ExprIfFalse(pParse, pHaving, addrEnd, SQLITE_JUMPIFNULL);
  5175         -      selectInnerLoop(pParse, p, p->pEList, -1, 0, 0, 0, 
         5244  +      selectInnerLoop(pParse, p, p->pEList, -1, 0, 0, 
  5176   5245                         pDest, addrEnd, addrEnd);
  5177   5246         sqlite3ExprListDelete(db, pDel);
  5178   5247       }
  5179   5248       sqlite3VdbeResolveLabel(v, addrEnd);
  5180   5249       
  5181   5250     } /* endif aggregate query */
  5182   5251   
................................................................................
  5183   5252     if( sDistinct.eTnctType==WHERE_DISTINCT_UNORDERED ){
  5184   5253       explainTempTable(pParse, "DISTINCT");
  5185   5254     }
  5186   5255   
  5187   5256     /* If there is an ORDER BY clause, then we need to sort the results
  5188   5257     ** and send them to the callback one by one.
  5189   5258     */
  5190         -  if( pOrderBy ){
         5259  +  if( sSort.pOrderBy ){
  5191   5260       explainTempTable(pParse, "ORDER BY");
  5192         -    generateSortTail(pParse, p, pEList->nExpr, pDest);
         5261  +    generateSortTail(pParse, p, &sSort, pEList->nExpr, pDest);
  5193   5262     }
  5194   5263   
  5195   5264     /* Jump here to skip this query
  5196   5265     */
  5197   5266     sqlite3VdbeResolveLabel(v, iEnd);
  5198   5267   
  5199   5268     /* The SELECT was successfully coded.   Set the return code to 0

Changes to src/sqliteInt.h.

  1954   1954   ** column expression as it exists in a SELECT statement.  However, if
  1955   1955   ** the bSpanIsTab flag is set, then zSpan is overloaded to mean the name
  1956   1956   ** of the result column in the form: DATABASE.TABLE.COLUMN.  This later
  1957   1957   ** form is used for name resolution with nested FROM clauses.
  1958   1958   */
  1959   1959   struct ExprList {
  1960   1960     int nExpr;             /* Number of expressions on the list */
  1961         -  int iECursor;          /* VDBE Cursor associated with this ExprList */
  1962   1961     struct ExprList_item { /* For each expression in the list */
  1963   1962       Expr *pExpr;            /* The list of expressions */
  1964   1963       char *zName;            /* Token associated with this expression */
  1965   1964       char *zSpan;            /* Original text of the expression */
  1966   1965       u8 sortOrder;           /* 1 for DESC or 0 for ASC */
  1967   1966       unsigned done :1;       /* A flag to indicate when processing is finished */
  1968   1967       unsigned bSpanIsTab :1; /* zSpan holds DB.TABLE.COLUMN */
................................................................................
  2178   2177   ** sequences for the ORDER BY clause.
  2179   2178   */
  2180   2179   struct Select {
  2181   2180     ExprList *pEList;      /* The fields of the result */
  2182   2181     u8 op;                 /* One of: TK_UNION TK_ALL TK_INTERSECT TK_EXCEPT */
  2183   2182     u16 selFlags;          /* Various SF_* values */
  2184   2183     int iLimit, iOffset;   /* Memory registers holding LIMIT & OFFSET counters */
  2185         -  int addrOpenEphm[3];   /* OP_OpenEphem opcodes related to this select */
         2184  +  int addrOpenEphm[2];   /* OP_OpenEphem opcodes related to this select */
  2186   2185     u64 nSelectRow;        /* Estimated number of result rows */
  2187   2186     SrcList *pSrc;         /* The FROM clause */
  2188   2187     Expr *pWhere;          /* The WHERE clause */
  2189   2188     ExprList *pGroupBy;    /* The GROUP BY clause */
  2190   2189     Expr *pHaving;         /* The HAVING clause */
  2191   2190     ExprList *pOrderBy;    /* The ORDER BY clause */
  2192   2191     Select *pPrior;        /* Prior select in a compound select statement */
................................................................................
  2202   2201   */
  2203   2202   #define SF_Distinct        0x0001  /* Output should be DISTINCT */
  2204   2203   #define SF_Resolved        0x0002  /* Identifiers have been resolved */
  2205   2204   #define SF_Aggregate       0x0004  /* Contains aggregate functions */
  2206   2205   #define SF_UsesEphemeral   0x0008  /* Uses the OpenEphemeral opcode */
  2207   2206   #define SF_Expanded        0x0010  /* sqlite3SelectExpand() called on this */
  2208   2207   #define SF_HasTypeInfo     0x0020  /* FROM subqueries have Table metadata */
  2209         -#define SF_UseSorter       0x0040  /* Sort using a sorter */
         2208  +                    /*     0x0040  NOT USED */
  2210   2209   #define SF_Values          0x0080  /* Synthesized from VALUES clause */
  2211         -#define SF_Materialize     0x0100  /* NOT USED */
         2210  +                    /*     0x0100  NOT USED */
  2212   2211   #define SF_NestedFrom      0x0200  /* Part of a parenthesized FROM clause */
  2213   2212   #define SF_MaybeConvert    0x0400  /* Need convertCompoundSelectToSubquery() */
  2214   2213   #define SF_Recursive       0x0800  /* The recursive part of a recursive CTE */
  2215   2214   #define SF_Compound        0x1000  /* Part of a compound query */
  2216   2215   
  2217   2216   
  2218   2217   /*

Changes to src/vdbe.c.

  1076   1076     UPDATE_MAX_BLOBSIZE(pOut);
  1077   1077     break;
  1078   1078   }
  1079   1079   
  1080   1080   /* Opcode: Move P1 P2 P3 * *
  1081   1081   ** Synopsis:  r[P2@P3]=r[P1@P3]
  1082   1082   **
  1083         -** Move the values in register P1..P1+P3 over into
  1084         -** registers P2..P2+P3.  Registers P1..P1+P3 are
         1083  +** Move the P3 values in register P1..P1+P3-1 over into
         1084  +** registers P2..P2+P3-1.  Registers P1..P1+P3-1 are
  1085   1085   ** left holding a NULL.  It is an error for register ranges
  1086         -** P1..P1+P3 and P2..P2+P3 to overlap.
         1086  +** P1..P1+P3-1 and P2..P2+P3-1 to overlap.  It is an error
         1087  +** for P3 to be less than 1.
  1087   1088   */
  1088   1089   case OP_Move: {
  1089   1090     char *zMalloc;   /* Holding variable for allocated memory */
  1090   1091     int n;           /* Number of registers left to copy */
  1091   1092     int p1;          /* Register to copy from */
  1092   1093     int p2;          /* Register to copy to */
  1093   1094   
  1094   1095     n = pOp->p3;
  1095   1096     p1 = pOp->p1;
  1096   1097     p2 = pOp->p2;
  1097         -  assert( n>=0 && p1>0 && p2>0 );
         1098  +  assert( n>0 && p1>0 && p2>0 );
  1098   1099     assert( p1+n<=p2 || p2+n<=p1 );
  1099   1100   
  1100   1101     pIn1 = &aMem[p1];
  1101   1102     pOut = &aMem[p2];
  1102   1103     do{
  1103   1104       assert( pOut<=&aMem[(p->nMem-p->nCursor)] );
  1104   1105       assert( pIn1<=&aMem[(p->nMem-p->nCursor)] );
................................................................................
  1114   1115   #endif
  1115   1116       pIn1->flags = MEM_Undefined;
  1116   1117       pIn1->xDel = 0;
  1117   1118       pIn1->zMalloc = zMalloc;
  1118   1119       REGISTER_TRACE(p2++, pOut);
  1119   1120       pIn1++;
  1120   1121       pOut++;
  1121         -  }while( n-- );
         1122  +  }while( --n );
  1122   1123     break;
  1123   1124   }
  1124   1125   
  1125   1126   /* Opcode: Copy P1 P2 P3 * *
  1126   1127   ** Synopsis: r[P2@P3+1]=r[P1@P3+1]
  1127   1128   **
  1128   1129   ** Make a copy of registers P1..P1+P3 into registers P2..P2+P3.
................................................................................
  1991   1992     assert( pOp->p4type==P4_INTARRAY );
  1992   1993     assert( pOp->p4.ai );
  1993   1994     aPermute = pOp->p4.ai;
  1994   1995     break;
  1995   1996   }
  1996   1997   
  1997   1998   /* Opcode: Compare P1 P2 P3 P4 P5
         1999  +** Synopsis: r[P1@P3] <-> r[P2@P3]
  1998   2000   **
  1999   2001   ** Compare two vectors of registers in reg(P1)..reg(P1+P3-1) (call this
  2000   2002   ** vector "A") and in reg(P2)..reg(P2+P3-1) ("B").  Save the result of
  2001   2003   ** the comparison for use by the next OP_Jump instruct.
  2002   2004   **
  2003   2005   ** If P5 has the OPFLAG_PERMUTE bit set, then the order of comparison is
  2004   2006   ** determined by the most recent OP_Permutation operator.  If the
................................................................................
  3326   3328         SQLITE_OPEN_DELETEONCLOSE |
  3327   3329         SQLITE_OPEN_TRANSIENT_DB;
  3328   3330     assert( pOp->p1>=0 );
  3329   3331     assert( pOp->p2>=0 );
  3330   3332     pCx = allocateCursor(p, pOp->p1, pOp->p2, -1, 1);
  3331   3333     if( pCx==0 ) goto no_mem;
  3332   3334     pCx->nullRow = 1;
         3335  +  pCx->isEphemeral = 1;
  3333   3336     rc = sqlite3BtreeOpen(db->pVfs, 0, db, &pCx->pBt, 
  3334   3337                           BTREE_OMIT_JOURNAL | BTREE_SINGLE | pOp->p5, vfsFlags);
  3335   3338     if( rc==SQLITE_OK ){
  3336   3339       rc = sqlite3BtreeBeginTrans(pCx->pBt, 1);
  3337   3340     }
  3338   3341     if( rc==SQLITE_OK ){
  3339   3342       /* If a transient index is required, create it by calling
................................................................................
  3816   3819       assert( pC->rowidIsValid==0 );
  3817   3820     }
  3818   3821     pC->seekResult = res;
  3819   3822     break;
  3820   3823   }
  3821   3824   
  3822   3825   /* Opcode: Sequence P1 P2 * * *
  3823         -** Synopsis: r[P2]=rowid
         3826  +** Synopsis: r[P2]=cursor[P1].ctr++
  3824   3827   **
  3825   3828   ** Find the next available sequence number for cursor P1.
  3826   3829   ** Write the sequence number into register P2.
  3827   3830   ** The sequence number on the cursor is incremented after this
  3828   3831   ** instruction.  
  3829   3832   */
  3830   3833   case OP_Sequence: {           /* out2-prerelease */
................................................................................
  4864   4867         assert( memIsValid(&aMem[pOp->p3]) );
  4865   4868         memAboutToChange(p, &aMem[pOp->p3]);
  4866   4869         aMem[pOp->p3].u.i += nChange;
  4867   4870       }
  4868   4871     }
  4869   4872     break;
  4870   4873   }
         4874  +
         4875  +/* Opcode: ClearEphem P1 * * * *
         4876  +**
         4877  +** Delete all contents from the ephemeral table that is open on cursor P1.
         4878  +**
         4879  +** See also: Clear, Destroy
         4880  +*/
         4881  +case OP_ClearEphem: {
         4882  +  VdbeCursor *pC;
         4883  + 
         4884  +  assert( pOp->p1>=0 && pOp->p1<p->nCursor );
         4885  +  pC = p->apCsr[pOp->p1];
         4886  +  assert( pC!=0 );
         4887  +  assert( pC->isEphemeral );
         4888  +  rc = sqlite3BtreeClearTableOfCursor(pC->pCursor);
         4889  +  break;
         4890  +}
  4871   4891   
  4872   4892   /* Opcode: CreateTable P1 P2 * * *
  4873   4893   ** Synopsis: r[P2]=root iDb=P1
  4874   4894   **
  4875   4895   ** Allocate a new table in the main database file if P1==0 or in the
  4876   4896   ** auxiliary database file if P1==1 or in an attached database if
  4877   4897   ** P1>1.  Write the root page number of the new table into

Changes to src/vdbeInt.h.

    68     68     int pseudoTableReg;   /* Register holding pseudotable content. */
    69     69     i16 nField;           /* Number of fields in the header */
    70     70     u16 nHdrParsed;       /* Number of header fields parsed so far */
    71     71     i8 iDb;               /* Index of cursor database in db->aDb[] (or -1) */
    72     72     u8 nullRow;           /* True if pointing to a row with no data */
    73     73     u8 rowidIsValid;      /* True if lastRowid is valid */
    74     74     u8 deferredMoveto;    /* A call to sqlite3BtreeMoveto() is needed */
           75  +  Bool isEphemeral:1;   /* True for an ephemeral table */
    75     76     Bool useRandomRowid:1;/* Generate new record numbers semi-randomly */
    76     77     Bool isTable:1;       /* True if a table requiring integer keys */
    77     78     Bool isOrdered:1;     /* True if the underlying table is BTREE_UNORDERED */
    78     79     sqlite3_vtab_cursor *pVtabCursor;  /* The cursor for a virtual table */
    79     80     i64 seqCount;         /* Sequence counter */
    80     81     i64 movetoTarget;     /* Argument to the deferred sqlite3BtreeMoveto() */
    81     82     i64 lastRowid;        /* Rowid being deleted by OP_Delete */

Changes to src/vdbeaux.c.

   779    779     }
   780    780     assert( p->nOp>0 );
   781    781     assert( addr<p->nOp );
   782    782     if( addr<0 ){
   783    783       addr = p->nOp - 1;
   784    784     }
   785    785     pOp = &p->aOp[addr];
   786         -  assert( pOp->p4type==P4_NOTUSED || pOp->p4type==P4_INT32 );
          786  +  assert( pOp->p4type==P4_NOTUSED
          787  +       || pOp->p4type==P4_INT32
          788  +       || pOp->p4type==P4_KEYINFO );
   787    789     freeP4(db, pOp->p4type, pOp->p4.p);
   788    790     pOp->p4.p = 0;
   789    791     if( n==P4_INT32 ){
   790    792       /* Note: this cast is safe, because the origin data point was an int
   791    793       ** that was cast to a (const char *). */
   792    794       pOp->p4.i = SQLITE_PTR_TO_INT(zP4);
   793    795       pOp->p4type = P4_INT32;

Changes to src/where.c.

  5194   5194       Bitmask notUsed;
  5195   5195       int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pResultSet, pFrom,
  5196   5196                    WHERE_DISTINCTBY, nLoop-1, pFrom->aLoop[nLoop-1], &notUsed);
  5197   5197       if( rc==pWInfo->pResultSet->nExpr ){
  5198   5198         pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
  5199   5199       }
  5200   5200     }
  5201         -  if( pWInfo->pOrderBy && pFrom->isOrdered==pWInfo->pOrderBy->nExpr ){
         5201  +  if( pWInfo->pOrderBy ){
  5202   5202       if( pWInfo->wctrlFlags & WHERE_DISTINCTBY ){
  5203         -      pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
         5203  +      if( pFrom->isOrdered==pWInfo->pOrderBy->nExpr ){
         5204  +        pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
         5205  +      }
  5204   5206       }else{
  5205   5207         pWInfo->nOBSat = pFrom->isOrdered;
  5206   5208         pWInfo->revMask = pFrom->revLoop;
  5207   5209       }
  5208   5210     }
  5209   5211     pWInfo->nRowOut = pFrom->nRow;
  5210   5212