/ Check-in [fa06a6fe]
Login

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

Overview
Comment:Add the ability to use indices for the first few terms of an ORDER BY clause, then sort in batches to handle the later terms.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: fa06a6fed9f48322d9b89721799ba12c46efa898
User & Date: drh 2014-03-21 20:58:42
Context
2014-03-22
00:27
Fix the ORDER BY optimization logic so that it will do a block-sort on a partial DESC ORDER BY. This enhancement uncovered a memory leak in pushUntoSorter() which is also fixed. check-in: c36f7461 user: drh tags: trunk
2014-03-21
20:58
Add the ability to use indices for the first few terms of an ORDER BY clause, then sort in batches to handle the later terms. check-in: fa06a6fe user: drh tags: trunk
19:56
Change the names of SRT_DistTable and SRT_Table used by CTE to more meaningful SRT_DistFifo and SRT_Fifo, respectively. Simplify the IgnorableOrderby() macro in the process. check-in: 45d8cc67 user: drh tags: trunk
18:45
Merge the OFFSET-on-query-without-FROM fix from trunk. check-in: 71e9ae72 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.

   951    951   ExprList *sqlite3ExprListDup(sqlite3 *db, ExprList *p, int flags){
   952    952     ExprList *pNew;
   953    953     struct ExprList_item *pItem, *pOldItem;
   954    954     int i;
   955    955     if( p==0 ) return 0;
   956    956     pNew = sqlite3DbMallocRaw(db, sizeof(*pNew) );
   957    957     if( pNew==0 ) return 0;
   958         -  pNew->iECursor = 0;
   959    958     pNew->nExpr = i = p->nExpr;
   960    959     if( (flags & EXPRDUP_REDUCE)==0 ) for(i=1; i<p->nExpr; i+=i){}
   961    960     pNew->a = pItem = sqlite3DbMallocRaw(db,  i*sizeof(p->a[0]) );
   962    961     if( pItem==0 ){
   963    962       sqlite3DbFree(db, pNew);
   964    963       return 0;
   965    964     } 
................................................................................
  1064   1063     pNew->pLimit = sqlite3ExprDup(db, p->pLimit, flags);
  1065   1064     pNew->pOffset = sqlite3ExprDup(db, p->pOffset, flags);
  1066   1065     pNew->iLimit = 0;
  1067   1066     pNew->iOffset = 0;
  1068   1067     pNew->selFlags = p->selFlags & ~SF_UsesEphemeral;
  1069   1068     pNew->addrOpenEphm[0] = -1;
  1070   1069     pNew->addrOpenEphm[1] = -1;
  1071         -  pNew->addrOpenEphm[2] = -1;
  1072   1070     pNew->nSelectRow = p->nSelectRow;
  1073   1071     pNew->pWith = withDup(db, p->pWith);
  1074   1072     return pNew;
  1075   1073   }
  1076   1074   #else
  1077   1075   Select *sqlite3SelectDup(sqlite3 *db, Select *p, int flags){
  1078   1076     assert( p==0 );
................................................................................
  2336   2334   ** Generate code to move content from registers iFrom...iFrom+nReg-1
  2337   2335   ** over to iTo..iTo+nReg-1. Keep the column cache up-to-date.
  2338   2336   */
  2339   2337   void sqlite3ExprCodeMove(Parse *pParse, int iFrom, int iTo, int nReg){
  2340   2338     int i;
  2341   2339     struct yColCache *p;
  2342   2340     assert( iFrom>=iTo+nReg || iFrom+nReg<=iTo );
  2343         -  sqlite3VdbeAddOp3(pParse->pVdbe, OP_Move, iFrom, iTo, nReg-1);
         2341  +  sqlite3VdbeAddOp3(pParse->pVdbe, OP_Move, iFrom, iTo, nReg);
  2344   2342     for(i=0, p=pParse->aColCache; i<SQLITE_N_COLCACHE; i++, p++){
  2345   2343       int x = p->iReg;
  2346   2344       if( x>=iFrom && x<iFrom+nReg ){
  2347   2345         p->iReg += iTo-iFrom;
  2348   2346       }
  2349   2347     }
  2350   2348   }
................................................................................
  2737   2735               testcase( pDef->funcFlags & OPFLAG_LENGTHARG );
  2738   2736               pFarg->a[0].pExpr->op2 = 
  2739   2737                     pDef->funcFlags & (OPFLAG_LENGTHARG|OPFLAG_TYPEOFARG);
  2740   2738             }
  2741   2739           }
  2742   2740   
  2743   2741           sqlite3ExprCachePush(pParse);     /* Ticket 2ea2425d34be */
  2744         -        sqlite3ExprCodeExprList(pParse, pFarg, r1, 
         2742  +        sqlite3ExprCodeExprList(pParse, pFarg, r1,
  2745   2743                                   SQLITE_ECEL_DUP|SQLITE_ECEL_FACTOR);
  2746   2744           sqlite3ExprCachePop(pParse, 1);   /* Ticket 2ea2425d34be */
  2747   2745         }else{
  2748   2746           r1 = 0;
  2749   2747         }
  2750   2748   #ifndef SQLITE_OMIT_VIRTUALTABLE
  2751   2749         /* 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  +    regPrevKey = pParse->nMem+1;
          486  +    pParse->nMem += pSort->nOBSat;
          487  +    nKey = nExpr - pSort->nOBSat + 1;
          488  +    addrFirst = sqlite3VdbeAddOp1(v, OP_IfNot, regBase+nExpr); VdbeCoverage(v);
          489  +    sqlite3VdbeAddOp3(v, OP_Compare, regPrevKey, regBase, pSort->nOBSat);
          490  +    pOp = sqlite3VdbeGetOp(v, pSort->addrSortIndex);
          491  +    pOp->p2 = nKey + 1;
          492  +    sqlite3VdbeChangeP4(v, -1, (char*)pOp->p4.pKeyInfo, P4_KEYINFO);
          493  +    pOp->p4.pKeyInfo = keyInfoFromExprList(pParse, pSort->pOrderBy, nOBSat, 1);
          494  +    addrJmp = sqlite3VdbeCurrentAddr(v);
          495  +    sqlite3VdbeAddOp3(v, OP_Jump, addrJmp+1, 0, addrJmp+1); VdbeCoverage(v);
          496  +    pSort->labelBkOut = sqlite3VdbeMakeLabel(v);
          497  +    pSort->regReturn = ++pParse->nMem;
          498  +    sqlite3VdbeAddOp2(v, OP_Gosub, pSort->regReturn, pSort->labelBkOut);
          499  +    sqlite3VdbeAddOp1(v, OP_ResetSorter, pSort->iECursor);
          500  +    sqlite3VdbeJumpHere(v, addrFirst);
          501  +    sqlite3VdbeAddOp3(v, OP_Move, regBase, regPrevKey, pSort->nOBSat);
          502  +    sqlite3VdbeJumpHere(v, addrJmp);
          503  +  }
          504  +  if( pSort->sortFlags & SORTFLAG_UseSorter ){
   443    505       op = OP_SorterInsert;
   444    506     }else{
   445    507       op = OP_IdxInsert;
   446    508     }
   447         -  sqlite3VdbeAddOp2(v, op, pOrderBy->iECursor, regRecord);
   448         -  sqlite3ReleaseTempReg(pParse, regRecord);
   449         -  sqlite3ReleaseTempRange(pParse, regBase, nExpr+2);
          509  +  sqlite3VdbeAddOp2(v, op, pSort->iECursor, regRecord);
          510  +  if( nOBSat==0 ){
          511  +    sqlite3ReleaseTempReg(pParse, regRecord);
          512  +    sqlite3ReleaseTempRange(pParse, regBase, nExpr+2);
          513  +  }
   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 */
          615  +  SortCtx *pSort,         /* If not NULL, info on how to process ORDER BY */
   565    616     DistinctCtx *pDistinct, /* If not NULL, info on how to process DISTINCT */
   566    617     SelectDest *pDest,      /* How to dispose of the results */
   567    618     int iContinue,          /* Jump here to continue with next row */
   568    619     int iBreak              /* Jump here to break out of the inner loop */
   569    620   ){
   570    621     Vdbe *v = pParse->pVdbe;
   571    622     int i;
................................................................................
   574    625     int eDest = pDest->eDest;   /* How to dispose of results */
   575    626     int iParm = pDest->iSDParm; /* First argument to disposal method */
   576    627     int nResultCol;             /* Number of result columns */
   577    628   
   578    629     assert( v );
   579    630     assert( pEList!=0 );
   580    631     hasDistinct = pDistinct ? pDistinct->eTnctType : WHERE_DISTINCT_NOOP;
   581         -  if( pOrderBy==0 && !hasDistinct ){
          632  +  if( pSort && pSort->pOrderBy==0 ) pSort = 0;
          633  +  if( pSort==0 && !hasDistinct ){
   582    634       assert( iContinue!=0 );
   583    635       codeOffset(v, p->iOffset, iContinue);
   584    636     }
   585    637   
   586    638     /* Pull the requested columns.
   587    639     */
   588    640     nResultCol = pEList->nExpr;
................................................................................
   665    717   
   666    718         default: {
   667    719           assert( pDistinct->eTnctType==WHERE_DISTINCT_UNORDERED );
   668    720           codeDistinct(pParse, pDistinct->tabTnct, iContinue, nResultCol, regResult);
   669    721           break;
   670    722         }
   671    723       }
   672         -    if( pOrderBy==0 ){
          724  +    if( pSort==0 ){
   673    725         codeOffset(v, p->iOffset, iContinue);
   674    726       }
   675    727     }
   676    728   
   677    729     switch( eDest ){
   678    730       /* In this mode, write each query result to the key of the temporary
   679    731       ** table iParm.
................................................................................
   714    766           ** on an ephemeral index. If the current row is already present
   715    767           ** in the index, do not write it to the output. If not, add the
   716    768           ** current row to the index and proceed with writing it to the
   717    769           ** output table as well.  */
   718    770           int addr = sqlite3VdbeCurrentAddr(v) + 4;
   719    771           sqlite3VdbeAddOp4Int(v, OP_Found, iParm+1, addr, r1, 0); VdbeCoverage(v);
   720    772           sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm+1, r1);
   721         -        assert( pOrderBy==0 );
          773  +        assert( pSort==0 );
   722    774         }
   723    775   #endif
   724         -      if( pOrderBy ){
   725         -        pushOntoSorter(pParse, pOrderBy, p, r1);
          776  +      if( pSort ){
          777  +        pushOntoSorter(pParse, pSort, p, r1);
   726    778         }else{
   727    779           int r2 = sqlite3GetTempReg(pParse);
   728    780           sqlite3VdbeAddOp2(v, OP_NewRowid, iParm, r2);
   729    781           sqlite3VdbeAddOp3(v, OP_Insert, iParm, r1, r2);
   730    782           sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
   731    783           sqlite3ReleaseTempReg(pParse, r2);
   732    784         }
................................................................................
   739    791       ** then there should be a single item on the stack.  Write this
   740    792       ** item into the set table with bogus data.
   741    793       */
   742    794       case SRT_Set: {
   743    795         assert( nResultCol==1 );
   744    796         pDest->affSdst =
   745    797                     sqlite3CompareAffinity(pEList->a[0].pExpr, pDest->affSdst);
   746         -      if( pOrderBy ){
          798  +      if( pSort ){
   747    799           /* At first glance you would think we could optimize out the
   748    800           ** ORDER BY in this case since the order of entries in the set
   749    801           ** does not matter.  But there might be a LIMIT clause, in which
   750    802           ** case the order does matter */
   751         -        pushOntoSorter(pParse, pOrderBy, p, regResult);
          803  +        pushOntoSorter(pParse, pSort, p, regResult);
   752    804         }else{
   753    805           int r1 = sqlite3GetTempReg(pParse);
   754    806           sqlite3VdbeAddOp4(v, OP_MakeRecord, regResult,1,r1, &pDest->affSdst, 1);
   755    807           sqlite3ExprCacheAffinityChange(pParse, regResult, 1);
   756    808           sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm, r1);
   757    809           sqlite3ReleaseTempReg(pParse, r1);
   758    810         }
................................................................................
   769    821   
   770    822       /* If this is a scalar select that is part of an expression, then
   771    823       ** store the results in the appropriate memory cell and break out
   772    824       ** of the scan loop.
   773    825       */
   774    826       case SRT_Mem: {
   775    827         assert( nResultCol==1 );
   776         -      if( pOrderBy ){
   777         -        pushOntoSorter(pParse, pOrderBy, p, regResult);
          828  +      if( pSort ){
          829  +        pushOntoSorter(pParse, pSort, p, regResult);
   778    830         }else{
   779    831           sqlite3ExprCodeMove(pParse, regResult, iParm, 1);
   780    832           /* The LIMIT clause will jump out of the loop for us */
   781    833         }
   782    834         break;
   783    835       }
   784    836   #endif /* #ifndef SQLITE_OMIT_SUBQUERY */
   785    837   
   786    838       case SRT_Coroutine:       /* Send data to a co-routine */
   787    839       case SRT_Output: {        /* Return the results */
   788    840         testcase( eDest==SRT_Coroutine );
   789    841         testcase( eDest==SRT_Output );
   790         -      if( pOrderBy ){
          842  +      if( pSort ){
   791    843           int r1 = sqlite3GetTempReg(pParse);
   792    844           sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nResultCol, r1);
   793         -        pushOntoSorter(pParse, pOrderBy, p, r1);
          845  +        pushOntoSorter(pParse, pSort, p, r1);
   794    846           sqlite3ReleaseTempReg(pParse, r1);
   795    847         }else if( eDest==SRT_Coroutine ){
   796    848           sqlite3VdbeAddOp1(v, OP_Yield, pDest->iSDParm);
   797    849         }else{
   798    850           sqlite3VdbeAddOp2(v, OP_ResultRow, regResult, nResultCol);
   799    851           sqlite3ExprCacheAffinityChange(pParse, regResult, nResultCol);
   800    852         }
................................................................................
   863    915   #endif
   864    916     }
   865    917   
   866    918     /* Jump to the end of the loop if the LIMIT is reached.  Except, if
   867    919     ** there is a sorter, in which case the sorter has already limited
   868    920     ** the output for us.
   869    921     */
   870         -  if( pOrderBy==0 && p->iLimit ){
          922  +  if( pSort==0 && p->iLimit ){
   871    923       sqlite3VdbeAddOp3(v, OP_IfZero, p->iLimit, iBreak, -1); VdbeCoverage(v);
   872    924     }
   873    925   }
   874    926   
   875    927   /*
   876    928   ** Allocate a KeyInfo object sufficient for an index of N key columns and
   877    929   ** X extra columns.
................................................................................
   934    986   ** then the KeyInfo structure is appropriate for initializing a virtual
   935    987   ** index to implement a DISTINCT test.
   936    988   **
   937    989   ** Space to hold the KeyInfo structure is obtain from malloc.  The calling
   938    990   ** function is responsible for seeing that this structure is eventually
   939    991   ** freed.
   940    992   */
   941         -static KeyInfo *keyInfoFromExprList(Parse *pParse, ExprList *pList, int nExtra){
          993  +static KeyInfo *keyInfoFromExprList(
          994  +  Parse *pParse,       /* Parsing context */
          995  +  ExprList *pList,     /* Form the KeyInfo object from this ExprList */
          996  +  int iStart,          /* Begin with this column of pList */
          997  +  int nExtra           /* Add this many extra columns to the end */
          998  +){
   942    999     int nExpr;
   943   1000     KeyInfo *pInfo;
   944   1001     struct ExprList_item *pItem;
   945   1002     sqlite3 *db = pParse->db;
   946   1003     int i;
   947   1004   
   948   1005     nExpr = pList->nExpr;
   949         -  pInfo = sqlite3KeyInfoAlloc(db, nExpr+nExtra, 1);
         1006  +  pInfo = sqlite3KeyInfoAlloc(db, nExpr+nExtra-iStart, 1);
   950   1007     if( pInfo ){
   951   1008       assert( sqlite3KeyInfoIsWriteable(pInfo) );
   952         -    for(i=0, pItem=pList->a; i<nExpr; i++, pItem++){
         1009  +    for(i=iStart, pItem=pList->a+iStart; i<nExpr; i++, pItem++){
   953   1010         CollSeq *pColl;
   954   1011         pColl = sqlite3ExprCollSeq(pParse, pItem->pExpr);
   955   1012         if( !pColl ) pColl = db->pDfltColl;
   956         -      pInfo->aColl[i] = pColl;
   957         -      pInfo->aSortOrder[i] = pItem->sortOrder;
         1013  +      pInfo->aColl[i-iStart] = pColl;
         1014  +      pInfo->aSortOrder[i-iStart] = pItem->sortOrder;
   958   1015       }
   959   1016     }
   960   1017     return pInfo;
   961   1018   }
   962   1019   
   963   1020   #ifndef SQLITE_OMIT_COMPOUND_SELECT
   964   1021   /*
................................................................................
  1052   1109   ** then the results were placed in a sorter.  After the loop is terminated
  1053   1110   ** we need to run the sorter and output the results.  The following
  1054   1111   ** routine generates the code needed to do that.
  1055   1112   */
  1056   1113   static void generateSortTail(
  1057   1114     Parse *pParse,    /* Parsing context */
  1058   1115     Select *p,        /* The SELECT statement */
  1059         -  Vdbe *v,          /* Generate code into this VDBE */
         1116  +  SortCtx *pSort,   /* Information on the ORDER BY clause */
  1060   1117     int nColumn,      /* Number of columns of data */
  1061   1118     SelectDest *pDest /* Write the sorted results here */
  1062   1119   ){
         1120  +  Vdbe *v = pParse->pVdbe;                     /* The prepared statement */
  1063   1121     int addrBreak = sqlite3VdbeMakeLabel(v);     /* Jump here to exit loop */
  1064   1122     int addrContinue = sqlite3VdbeMakeLabel(v);  /* Jump here for next cycle */
  1065   1123     int addr;
         1124  +  int addrOnce = 0;
  1066   1125     int iTab;
  1067   1126     int pseudoTab = 0;
  1068         -  ExprList *pOrderBy = p->pOrderBy;
  1069         -
         1127  +  ExprList *pOrderBy = pSort->pOrderBy;
  1070   1128     int eDest = pDest->eDest;
  1071   1129     int iParm = pDest->iSDParm;
  1072         -
  1073   1130     int regRow;
  1074   1131     int regRowid;
         1132  +  int nKey;
  1075   1133   
  1076         -  iTab = pOrderBy->iECursor;
         1134  +  if( pSort->labelBkOut ){
         1135  +    sqlite3VdbeAddOp2(v, OP_Gosub, pSort->regReturn, pSort->labelBkOut);
         1136  +    sqlite3VdbeAddOp2(v, OP_Goto, 0, addrBreak);
         1137  +    sqlite3VdbeResolveLabel(v, pSort->labelBkOut);
         1138  +    addrOnce = sqlite3CodeOnce(pParse); VdbeCoverage(v);
         1139  +  }
         1140  +  iTab = pSort->iECursor;
  1077   1141     regRow = sqlite3GetTempReg(pParse);
  1078   1142     if( eDest==SRT_Output || eDest==SRT_Coroutine ){
  1079   1143       pseudoTab = pParse->nTab++;
  1080   1144       sqlite3VdbeAddOp3(v, OP_OpenPseudo, pseudoTab, regRow, nColumn);
  1081   1145       regRowid = 0;
  1082   1146     }else{
  1083   1147       regRowid = sqlite3GetTempReg(pParse);
  1084   1148     }
  1085         -  if( p->selFlags & SF_UseSorter ){
         1149  +  nKey = pOrderBy->nExpr - pSort->nOBSat;
         1150  +  if( pSort->sortFlags & SORTFLAG_UseSorter ){
  1086   1151       int regSortOut = ++pParse->nMem;
  1087   1152       int ptab2 = pParse->nTab++;
  1088         -    sqlite3VdbeAddOp3(v, OP_OpenPseudo, ptab2, regSortOut, pOrderBy->nExpr+2);
         1153  +    sqlite3VdbeAddOp3(v, OP_OpenPseudo, ptab2, regSortOut, nKey+2);
         1154  +    if( addrOnce ) sqlite3VdbeJumpHere(v, addrOnce);
  1089   1155       addr = 1 + sqlite3VdbeAddOp2(v, OP_SorterSort, iTab, addrBreak);
  1090   1156       VdbeCoverage(v);
  1091   1157       codeOffset(v, p->iOffset, addrContinue);
  1092   1158       sqlite3VdbeAddOp2(v, OP_SorterData, iTab, regSortOut);
  1093         -    sqlite3VdbeAddOp3(v, OP_Column, ptab2, pOrderBy->nExpr+1, regRow);
         1159  +    sqlite3VdbeAddOp3(v, OP_Column, ptab2, nKey+1, regRow);
  1094   1160       sqlite3VdbeChangeP5(v, OPFLAG_CLEARCACHE);
  1095   1161     }else{
         1162  +    if( addrOnce ) sqlite3VdbeJumpHere(v, addrOnce);
  1096   1163       addr = 1 + sqlite3VdbeAddOp2(v, OP_Sort, iTab, addrBreak); VdbeCoverage(v);
  1097   1164       codeOffset(v, p->iOffset, addrContinue);
  1098         -    sqlite3VdbeAddOp3(v, OP_Column, iTab, pOrderBy->nExpr+1, regRow);
         1165  +    sqlite3VdbeAddOp3(v, OP_Column, iTab, nKey+1, regRow);
  1099   1166     }
  1100   1167     switch( eDest ){
  1101   1168       case SRT_Table:
  1102   1169       case SRT_EphemTab: {
  1103   1170         testcase( eDest==SRT_Table );
  1104   1171         testcase( eDest==SRT_EphemTab );
  1105   1172         sqlite3VdbeAddOp2(v, OP_NewRowid, iParm, regRowid);
................................................................................
  1146   1213     }
  1147   1214     sqlite3ReleaseTempReg(pParse, regRow);
  1148   1215     sqlite3ReleaseTempReg(pParse, regRowid);
  1149   1216   
  1150   1217     /* The bottom of the loop
  1151   1218     */
  1152   1219     sqlite3VdbeResolveLabel(v, addrContinue);
  1153         -  if( p->selFlags & SF_UseSorter ){
         1220  +  if( pSort->sortFlags & SORTFLAG_UseSorter ){
  1154   1221       sqlite3VdbeAddOp2(v, OP_SorterNext, iTab, addr); VdbeCoverage(v);
  1155   1222     }else{
  1156   1223       sqlite3VdbeAddOp2(v, OP_Next, iTab, addr); VdbeCoverage(v);
  1157   1224     }
         1225  +  if( pSort->regReturn ) sqlite3VdbeAddOp1(v, OP_Return, pSort->regReturn);
  1158   1226     sqlite3VdbeResolveLabel(v, addrBreak);
  1159   1227     if( eDest==SRT_Output || eDest==SRT_Coroutine ){
  1160   1228       sqlite3VdbeAddOp2(v, OP_Close, pseudoTab, 0);
  1161   1229     }
  1162   1230   }
  1163   1231   
  1164   1232   /*
................................................................................
  4308   4376         Expr *pE = pFunc->pExpr;
  4309   4377         assert( !ExprHasProperty(pE, EP_xIsSelect) );
  4310   4378         if( pE->x.pList==0 || pE->x.pList->nExpr!=1 ){
  4311   4379           sqlite3ErrorMsg(pParse, "DISTINCT aggregates must have exactly one "
  4312   4380              "argument");
  4313   4381           pFunc->iDistinct = -1;
  4314   4382         }else{
  4315         -        KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pE->x.pList, 0);
         4383  +        KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pE->x.pList, 0, 0);
  4316   4384           sqlite3VdbeAddOp4(v, OP_OpenEphemeral, pFunc->iDistinct, 0, 0,
  4317   4385                             (char*)pKeyInfo, P4_KEYINFO);
  4318   4386         }
  4319   4387       }
  4320   4388     }
  4321   4389   }
  4322   4390   
................................................................................
  4463   4531     int i, j;              /* Loop counters */
  4464   4532     WhereInfo *pWInfo;     /* Return from sqlite3WhereBegin() */
  4465   4533     Vdbe *v;               /* The virtual machine under construction */
  4466   4534     int isAgg;             /* True for select lists like "count(*)" */
  4467   4535     ExprList *pEList;      /* List of columns to extract. */
  4468   4536     SrcList *pTabList;     /* List of tables to select from */
  4469   4537     Expr *pWhere;          /* The WHERE clause.  May be NULL */
  4470         -  ExprList *pOrderBy;    /* The ORDER BY clause.  May be NULL */
  4471   4538     ExprList *pGroupBy;    /* The GROUP BY clause.  May be NULL */
  4472   4539     Expr *pHaving;         /* The HAVING clause.  May be NULL */
  4473   4540     int rc = 1;            /* Value to return from this function */
  4474         -  int addrSortIndex;     /* Address of an OP_OpenEphemeral instruction */
  4475   4541     DistinctCtx sDistinct; /* Info on how to code the DISTINCT keyword */
         4542  +  SortCtx sSort;         /* Info on how to code the ORDER BY clause */
  4476   4543     AggInfo sAggInfo;      /* Information used by aggregate queries */
  4477   4544     int iEnd;              /* Address of the end of the query */
  4478   4545     sqlite3 *db;           /* The database connection */
  4479   4546   
  4480   4547   #ifndef SQLITE_OMIT_EXPLAIN
  4481   4548     int iRestoreSelectId = pParse->iSelectId;
  4482   4549     pParse->iSelectId = pParse->iNextSelectId++;
................................................................................
  4501   4568       /* If ORDER BY makes no difference in the output then neither does
  4502   4569       ** DISTINCT so it can be removed too. */
  4503   4570       sqlite3ExprListDelete(db, p->pOrderBy);
  4504   4571       p->pOrderBy = 0;
  4505   4572       p->selFlags &= ~SF_Distinct;
  4506   4573     }
  4507   4574     sqlite3SelectPrep(pParse, p, 0);
  4508         -  pOrderBy = p->pOrderBy;
         4575  +  memset(&sSort, 0, sizeof(sSort));
         4576  +  sSort.pOrderBy = p->pOrderBy;
  4509   4577     pTabList = p->pSrc;
  4510   4578     pEList = p->pEList;
  4511   4579     if( pParse->nErr || db->mallocFailed ){
  4512   4580       goto select_end;
  4513   4581     }
  4514   4582     isAgg = (p->selFlags & SF_Aggregate)!=0;
  4515   4583     assert( pEList!=0 );
................................................................................
  4623   4691       }
  4624   4692       if( /*pParse->nErr ||*/ db->mallocFailed ){
  4625   4693         goto select_end;
  4626   4694       }
  4627   4695       pParse->nHeight -= sqlite3SelectExprHeight(p);
  4628   4696       pTabList = p->pSrc;
  4629   4697       if( !IgnorableOrderby(pDest) ){
  4630         -      pOrderBy = p->pOrderBy;
         4698  +      sSort.pOrderBy = p->pOrderBy;
  4631   4699       }
  4632   4700     }
  4633   4701     pEList = p->pEList;
  4634   4702   #endif
  4635   4703     pWhere = p->pWhere;
  4636   4704     pGroupBy = p->pGroupBy;
  4637   4705     pHaving = p->pHaving;
................................................................................
  4650   4718     /* If there is both a GROUP BY and an ORDER BY clause and they are
  4651   4719     ** identical, then disable the ORDER BY clause since the GROUP BY
  4652   4720     ** will cause elements to come out in the correct order.  This is
  4653   4721     ** an optimization - the correct answer should result regardless.
  4654   4722     ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER
  4655   4723     ** to disable this optimization for testing purposes.
  4656   4724     */
  4657         -  if( sqlite3ExprListCompare(p->pGroupBy, pOrderBy, -1)==0
         4725  +  if( sqlite3ExprListCompare(p->pGroupBy, sSort.pOrderBy, -1)==0
  4658   4726            && OptimizationEnabled(db, SQLITE_GroupByOrder) ){
  4659         -    pOrderBy = 0;
         4727  +    sSort.pOrderBy = 0;
  4660   4728     }
  4661   4729   
  4662   4730     /* If the query is DISTINCT with an ORDER BY but is not an aggregate, and 
  4663   4731     ** if the select-list is the same as the ORDER BY list, then this query
  4664   4732     ** can be rewritten as a GROUP BY. In other words, this:
  4665   4733     **
  4666   4734     **     SELECT DISTINCT xyz FROM ... ORDER BY xyz
................................................................................
  4671   4739     **
  4672   4740     ** The second form is preferred as a single index (or temp-table) may be 
  4673   4741     ** used for both the ORDER BY and DISTINCT processing. As originally 
  4674   4742     ** written the query must use a temp-table for at least one of the ORDER 
  4675   4743     ** BY and DISTINCT, and an index or separate temp-table for the other.
  4676   4744     */
  4677   4745     if( (p->selFlags & (SF_Distinct|SF_Aggregate))==SF_Distinct 
  4678         -   && sqlite3ExprListCompare(pOrderBy, p->pEList, -1)==0
         4746  +   && sqlite3ExprListCompare(sSort.pOrderBy, p->pEList, -1)==0
  4679   4747     ){
  4680   4748       p->selFlags &= ~SF_Distinct;
  4681   4749       p->pGroupBy = sqlite3ExprListDup(db, p->pEList, 0);
  4682   4750       pGroupBy = p->pGroupBy;
  4683         -    pOrderBy = 0;
         4751  +    sSort.pOrderBy = 0;
  4684   4752       /* Notice that even thought SF_Distinct has been cleared from p->selFlags,
  4685   4753       ** the sDistinct.isTnct is still set.  Hence, isTnct represents the
  4686   4754       ** original setting of the SF_Distinct flag, not the current setting */
  4687   4755       assert( sDistinct.isTnct );
  4688   4756     }
  4689   4757   
  4690   4758     /* If there is an ORDER BY clause, then this sorting
  4691   4759     ** index might end up being unused if the data can be 
  4692   4760     ** extracted in pre-sorted order.  If that is the case, then the
  4693   4761     ** OP_OpenEphemeral instruction will be changed to an OP_Noop once
  4694   4762     ** we figure out that the sorting index is not needed.  The addrSortIndex
  4695   4763     ** variable is used to facilitate that change.
  4696   4764     */
  4697         -  if( pOrderBy ){
         4765  +  if( sSort.pOrderBy ){
  4698   4766       KeyInfo *pKeyInfo;
  4699         -    pKeyInfo = keyInfoFromExprList(pParse, pOrderBy, 0);
  4700         -    pOrderBy->iECursor = pParse->nTab++;
  4701         -    p->addrOpenEphm[2] = addrSortIndex =
         4767  +    pKeyInfo = keyInfoFromExprList(pParse, sSort.pOrderBy, 0, 0);
         4768  +    sSort.iECursor = pParse->nTab++;
         4769  +    sSort.addrSortIndex =
  4702   4770         sqlite3VdbeAddOp4(v, OP_OpenEphemeral,
  4703         -                           pOrderBy->iECursor, pOrderBy->nExpr+2, 0,
         4771  +                           sSort.iECursor, sSort.pOrderBy->nExpr+2, 0,
  4704   4772                              (char*)pKeyInfo, P4_KEYINFO);
  4705   4773     }else{
  4706         -    addrSortIndex = -1;
         4774  +    sSort.addrSortIndex = -1;
  4707   4775     }
  4708   4776   
  4709   4777     /* If the output is destined for a temporary table, open that table.
  4710   4778     */
  4711   4779     if( pDest->eDest==SRT_EphemTab ){
  4712   4780       sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pDest->iSDParm, pEList->nExpr);
  4713   4781     }
  4714   4782   
  4715   4783     /* Set the limiter.
  4716   4784     */
  4717   4785     iEnd = sqlite3VdbeMakeLabel(v);
  4718   4786     p->nSelectRow = LARGEST_INT64;
  4719   4787     computeLimitRegisters(pParse, p, iEnd);
  4720         -  if( p->iLimit==0 && addrSortIndex>=0 ){
  4721         -    sqlite3VdbeGetOp(v, addrSortIndex)->opcode = OP_SorterOpen;
  4722         -    p->selFlags |= SF_UseSorter;
         4788  +  if( p->iLimit==0 && sSort.addrSortIndex>=0 ){
         4789  +    sqlite3VdbeGetOp(v, sSort.addrSortIndex)->opcode = OP_SorterOpen;
         4790  +    sSort.sortFlags |= SORTFLAG_UseSorter;
  4723   4791     }
  4724   4792   
  4725   4793     /* Open a virtual index to use for the distinct set.
  4726   4794     */
  4727   4795     if( p->selFlags & SF_Distinct ){
  4728   4796       sDistinct.tabTnct = pParse->nTab++;
  4729   4797       sDistinct.addrTnct = sqlite3VdbeAddOp4(v, OP_OpenEphemeral,
  4730   4798                                   sDistinct.tabTnct, 0, 0,
  4731         -                                (char*)keyInfoFromExprList(pParse, p->pEList, 0),
         4799  +                                (char*)keyInfoFromExprList(pParse, p->pEList,0,0),
  4732   4800                                   P4_KEYINFO);
  4733   4801       sqlite3VdbeChangeP5(v, BTREE_UNORDERED);
  4734   4802       sDistinct.eTnctType = WHERE_DISTINCT_UNORDERED;
  4735   4803     }else{
  4736   4804       sDistinct.eTnctType = WHERE_DISTINCT_NOOP;
  4737   4805     }
  4738   4806   
  4739   4807     if( !isAgg && pGroupBy==0 ){
  4740   4808       /* No aggregate functions and no GROUP BY clause */
  4741   4809       u16 wctrlFlags = (sDistinct.isTnct ? WHERE_WANT_DISTINCT : 0);
  4742   4810   
  4743   4811       /* Begin the database scan. */
  4744         -    pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pOrderBy, p->pEList,
  4745         -                               wctrlFlags, 0);
         4812  +    pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, sSort.pOrderBy,
         4813  +                               p->pEList, wctrlFlags, 0);
  4746   4814       if( pWInfo==0 ) goto select_end;
  4747   4815       if( sqlite3WhereOutputRowCount(pWInfo) < p->nSelectRow ){
  4748   4816         p->nSelectRow = sqlite3WhereOutputRowCount(pWInfo);
  4749   4817       }
  4750   4818       if( sDistinct.isTnct && sqlite3WhereIsDistinct(pWInfo) ){
  4751   4819         sDistinct.eTnctType = sqlite3WhereIsDistinct(pWInfo);
  4752   4820       }
  4753         -    if( pOrderBy && sqlite3WhereIsOrdered(pWInfo) ) pOrderBy = 0;
         4821  +    if( sSort.pOrderBy ){
         4822  +      sSort.nOBSat = sqlite3WhereIsOrdered(pWInfo);
         4823  +      if( sSort.nOBSat==sSort.pOrderBy->nExpr ){
         4824  +        sSort.pOrderBy = 0;
         4825  +      }
         4826  +    }
  4754   4827   
  4755   4828       /* If sorting index that was created by a prior OP_OpenEphemeral 
  4756   4829       ** instruction ended up not being needed, then change the OP_OpenEphemeral
  4757   4830       ** into an OP_Noop.
  4758   4831       */
  4759         -    if( addrSortIndex>=0 && pOrderBy==0 ){
  4760         -      sqlite3VdbeChangeToNoop(v, addrSortIndex);
  4761         -      p->addrOpenEphm[2] = -1;
         4832  +    if( sSort.addrSortIndex>=0 && sSort.pOrderBy==0 ){
         4833  +      sqlite3VdbeChangeToNoop(v, sSort.addrSortIndex);
  4762   4834       }
  4763   4835   
  4764   4836       /* Use the standard inner loop. */
  4765         -    selectInnerLoop(pParse, p, pEList, -1, pOrderBy, &sDistinct, pDest,
         4837  +    selectInnerLoop(pParse, p, pEList, -1, &sSort, &sDistinct, pDest,
  4766   4838                       sqlite3WhereContinueLabel(pWInfo),
  4767   4839                       sqlite3WhereBreakLabel(pWInfo));
  4768   4840   
  4769   4841       /* End the database scan loop.
  4770   4842       */
  4771   4843       sqlite3WhereEnd(pWInfo);
  4772   4844     }else{
................................................................................
  4814   4886       sNC.pParse = pParse;
  4815   4887       sNC.pSrcList = pTabList;
  4816   4888       sNC.pAggInfo = &sAggInfo;
  4817   4889       sAggInfo.mnReg = pParse->nMem+1;
  4818   4890       sAggInfo.nSortingColumn = pGroupBy ? pGroupBy->nExpr+1 : 0;
  4819   4891       sAggInfo.pGroupBy = pGroupBy;
  4820   4892       sqlite3ExprAnalyzeAggList(&sNC, pEList);
  4821         -    sqlite3ExprAnalyzeAggList(&sNC, pOrderBy);
         4893  +    sqlite3ExprAnalyzeAggList(&sNC, sSort.pOrderBy);
  4822   4894       if( pHaving ){
  4823   4895         sqlite3ExprAnalyzeAggregates(&sNC, pHaving);
  4824   4896       }
  4825   4897       sAggInfo.nAccumulator = sAggInfo.nColumn;
  4826   4898       for(i=0; i<sAggInfo.nFunc; i++){
  4827   4899         assert( !ExprHasProperty(sAggInfo.aFunc[i].pExpr, EP_xIsSelect) );
  4828   4900         sNC.ncFlags |= NC_InAggFunc;
................................................................................
  4848   4920   
  4849   4921         /* If there is a GROUP BY clause we might need a sorting index to
  4850   4922         ** implement it.  Allocate that sorting index now.  If it turns out
  4851   4923         ** that we do not need it after all, the OP_SorterOpen instruction
  4852   4924         ** will be converted into a Noop.  
  4853   4925         */
  4854   4926         sAggInfo.sortingIdx = pParse->nTab++;
  4855         -      pKeyInfo = keyInfoFromExprList(pParse, pGroupBy, 0);
         4927  +      pKeyInfo = keyInfoFromExprList(pParse, pGroupBy, 0, 0);
  4856   4928         addrSortingIdx = sqlite3VdbeAddOp4(v, OP_SorterOpen, 
  4857   4929             sAggInfo.sortingIdx, sAggInfo.nSortingColumn, 
  4858   4930             0, (char*)pKeyInfo, P4_KEYINFO);
  4859   4931   
  4860   4932         /* Initialize memory locations used by GROUP BY aggregate processing
  4861   4933         */
  4862   4934         iUseFlag = ++pParse->nMem;
................................................................................
  4877   4949   
  4878   4950         /* Begin a loop that will extract all source rows in GROUP BY order.
  4879   4951         ** This might involve two separate loops with an OP_Sort in between, or
  4880   4952         ** it might be a single loop that uses an index to extract information
  4881   4953         ** in the right order to begin with.
  4882   4954         */
  4883   4955         sqlite3VdbeAddOp2(v, OP_Gosub, regReset, addrReset);
  4884         -      pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pGroupBy, 0, 
         4956  +      pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pGroupBy, 0,
  4885   4957                                    WHERE_GROUPBY, 0);
  4886   4958         if( pWInfo==0 ) goto select_end;
  4887         -      if( sqlite3WhereIsOrdered(pWInfo) ){
         4959  +      if( sqlite3WhereIsOrdered(pWInfo)==pGroupBy->nExpr ){
  4888   4960           /* The optimizer is able to deliver rows in group by order so
  4889   4961           ** we do not have to sort.  The OP_OpenEphemeral table will be
  4890   4962           ** cancelled later because we still need to use the pKeyInfo
  4891   4963           */
  4892   4964           groupBySort = 0;
  4893   4965         }else{
  4894   4966           /* Rows are coming out in undetermined order.  We have to push
................................................................................
  5031   5103         sqlite3VdbeResolveLabel(v, addrOutputRow);
  5032   5104         addrOutputRow = sqlite3VdbeCurrentAddr(v);
  5033   5105         sqlite3VdbeAddOp2(v, OP_IfPos, iUseFlag, addrOutputRow+2); VdbeCoverage(v);
  5034   5106         VdbeComment((v, "Groupby result generator entry point"));
  5035   5107         sqlite3VdbeAddOp1(v, OP_Return, regOutputRow);
  5036   5108         finalizeAggFunctions(pParse, &sAggInfo);
  5037   5109         sqlite3ExprIfFalse(pParse, pHaving, addrOutputRow+1, SQLITE_JUMPIFNULL);
  5038         -      selectInnerLoop(pParse, p, p->pEList, -1, pOrderBy,
         5110  +      selectInnerLoop(pParse, p, p->pEList, -1, &sSort,
  5039   5111                         &sDistinct, pDest,
  5040   5112                         addrOutputRow+1, addrSetAbort);
  5041   5113         sqlite3VdbeAddOp1(v, OP_Return, regOutputRow);
  5042   5114         VdbeComment((v, "end groupby result generator"));
  5043   5115   
  5044   5116         /* Generate a subroutine that will reset the group-by accumulator
  5045   5117         */
................................................................................
  5163   5235           pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pMinMax,0,flag,0);
  5164   5236           if( pWInfo==0 ){
  5165   5237             sqlite3ExprListDelete(db, pDel);
  5166   5238             goto select_end;
  5167   5239           }
  5168   5240           updateAccumulator(pParse, &sAggInfo);
  5169   5241           assert( pMinMax==0 || pMinMax->nExpr==1 );
  5170         -        if( sqlite3WhereIsOrdered(pWInfo) ){
         5242  +        if( sqlite3WhereIsOrdered(pWInfo)>0 ){
  5171   5243             sqlite3VdbeAddOp2(v, OP_Goto, 0, sqlite3WhereBreakLabel(pWInfo));
  5172   5244             VdbeComment((v, "%s() by index",
  5173   5245                   (flag==WHERE_ORDERBY_MIN?"min":"max")));
  5174   5246           }
  5175   5247           sqlite3WhereEnd(pWInfo);
  5176   5248           finalizeAggFunctions(pParse, &sAggInfo);
  5177   5249         }
  5178   5250   
  5179         -      pOrderBy = 0;
         5251  +      sSort.pOrderBy = 0;
  5180   5252         sqlite3ExprIfFalse(pParse, pHaving, addrEnd, SQLITE_JUMPIFNULL);
  5181   5253         selectInnerLoop(pParse, p, p->pEList, -1, 0, 0, 
  5182   5254                         pDest, addrEnd, addrEnd);
  5183   5255         sqlite3ExprListDelete(db, pDel);
  5184   5256       }
  5185   5257       sqlite3VdbeResolveLabel(v, addrEnd);
  5186   5258       
................................................................................
  5189   5261     if( sDistinct.eTnctType==WHERE_DISTINCT_UNORDERED ){
  5190   5262       explainTempTable(pParse, "DISTINCT");
  5191   5263     }
  5192   5264   
  5193   5265     /* If there is an ORDER BY clause, then we need to sort the results
  5194   5266     ** and send them to the callback one by one.
  5195   5267     */
  5196         -  if( pOrderBy ){
  5197         -    explainTempTable(pParse, "ORDER BY");
  5198         -    generateSortTail(pParse, p, v, pEList->nExpr, pDest);
         5268  +  if( sSort.pOrderBy ){
         5269  +    explainTempTable(pParse, sSort.nOBSat>0 ? "RIGHT PART OF ORDER BY":"ORDER BY");
         5270  +    generateSortTail(pParse, p, &sSort, pEList->nExpr, pDest);
  5199   5271     }
  5200   5272   
  5201   5273     /* Jump here to skip this query
  5202   5274     */
  5203   5275     sqlite3VdbeResolveLabel(v, iEnd);
  5204   5276   
  5205   5277     /* 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: ResetSorter P1 * * * *
         4876  +**
         4877  +** Delete all contents from the ephemeral table or sorter
         4878  +** that is open on cursor P1.
         4879  +**
         4880  +** This opcode only works for cursors used for sorting and
         4881  +** opened with OP_OpenEphemeral or OP_SorterOpen.
         4882  +*/
         4883  +case OP_ResetSorter: {
         4884  +  VdbeCursor *pC;
         4885  + 
         4886  +  assert( pOp->p1>=0 && pOp->p1<p->nCursor );
         4887  +  pC = p->apCsr[pOp->p1];
         4888  +  assert( pC!=0 );
         4889  +  if( pC->pSorter ){
         4890  +    sqlite3VdbeSorterReset(db, pC->pSorter);
         4891  +  }else{
         4892  +    assert( pC->isEphemeral );
         4893  +    rc = sqlite3BtreeClearTableOfCursor(pC->pCursor);
         4894  +  }
         4895  +  break;
         4896  +}
  4871   4897   
  4872   4898   /* Opcode: CreateTable P1 P2 * * *
  4873   4899   ** Synopsis: r[P2]=root iDb=P1
  4874   4900   **
  4875   4901   ** Allocate a new table in the main database file if P1==0 or in the
  4876   4902   ** auxiliary database file if P1==1 or in an attached database if
  4877   4903   ** 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 */
................................................................................
   433    434   int sqlite3VdbeMemGrow(Mem *pMem, int n, int preserve);
   434    435   int sqlite3VdbeCloseStatement(Vdbe *, int);
   435    436   void sqlite3VdbeFrameDelete(VdbeFrame*);
   436    437   int sqlite3VdbeFrameRestore(VdbeFrame *);
   437    438   int sqlite3VdbeTransferError(Vdbe *p);
   438    439   
   439    440   int sqlite3VdbeSorterInit(sqlite3 *, VdbeCursor *);
          441  +void sqlite3VdbeSorterReset(sqlite3 *, VdbeSorter *);
   440    442   void sqlite3VdbeSorterClose(sqlite3 *, VdbeCursor *);
   441    443   int sqlite3VdbeSorterRowkey(const VdbeCursor *, Mem *);
   442    444   int sqlite3VdbeSorterNext(sqlite3 *, const VdbeCursor *, int *);
   443    445   int sqlite3VdbeSorterRewind(sqlite3 *, const VdbeCursor *, int *);
   444    446   int sqlite3VdbeSorterWrite(sqlite3 *, const VdbeCursor *, Mem *);
   445    447   int sqlite3VdbeSorterCompare(const VdbeCursor *, Mem *, int, int *);
   446    448   

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/vdbesort.c.

   499    499     SorterRecord *p;
   500    500     SorterRecord *pNext;
   501    501     for(p=pRecord; p; p=pNext){
   502    502       pNext = p->pNext;
   503    503       sqlite3DbFree(db, p);
   504    504     }
   505    505   }
          506  +
          507  +/*
          508  +** Reset a sorting cursor back to its original empty state.
          509  +*/
          510  +void sqlite3VdbeSorterReset(sqlite3 *db, VdbeSorter *pSorter){
          511  +  if( pSorter->aIter ){
          512  +    int i;
          513  +    for(i=0; i<pSorter->nTree; i++){
          514  +      vdbeSorterIterZero(db, &pSorter->aIter[i]);
          515  +    }
          516  +    sqlite3DbFree(db, pSorter->aIter);
          517  +    pSorter->aIter = 0;
          518  +  }
          519  +  if( pSorter->pTemp1 ){
          520  +    sqlite3OsCloseFree(pSorter->pTemp1);
          521  +    pSorter->pTemp1 = 0;
          522  +  }
          523  +  vdbeSorterRecordFree(db, pSorter->pRecord);
          524  +  pSorter->pRecord = 0;
          525  +  pSorter->iWriteOff = 0;
          526  +  pSorter->iReadOff = 0;
          527  +  pSorter->nInMemory = 0;
          528  +  pSorter->nTree = 0;
          529  +  pSorter->nPMA = 0;
          530  +  pSorter->aTree = 0;
          531  +}
          532  +
   506    533   
   507    534   /*
   508    535   ** Free any cursor components allocated by sqlite3VdbeSorterXXX routines.
   509    536   */
   510    537   void sqlite3VdbeSorterClose(sqlite3 *db, VdbeCursor *pCsr){
   511    538     VdbeSorter *pSorter = pCsr->pSorter;
   512    539     if( pSorter ){
   513         -    if( pSorter->aIter ){
   514         -      int i;
   515         -      for(i=0; i<pSorter->nTree; i++){
   516         -        vdbeSorterIterZero(db, &pSorter->aIter[i]);
   517         -      }
   518         -      sqlite3DbFree(db, pSorter->aIter);
   519         -    }
   520         -    if( pSorter->pTemp1 ){
   521         -      sqlite3OsCloseFree(pSorter->pTemp1);
   522         -    }
   523         -    vdbeSorterRecordFree(db, pSorter->pRecord);
          540  +    sqlite3VdbeSorterReset(db, pSorter);
   524    541       sqlite3DbFree(db, pSorter->pUnpacked);
   525    542       sqlite3DbFree(db, pSorter);
   526    543       pCsr->pSorter = 0;
   527    544     }
   528    545   }
   529    546   
   530    547   /*

Changes to src/where.c.

    35     35   }
    36     36   
    37     37   /*
    38     38   ** Return TRUE if the WHERE clause returns rows in ORDER BY order.
    39     39   ** Return FALSE if the output needs to be sorted.
    40     40   */
    41     41   int sqlite3WhereIsOrdered(WhereInfo *pWInfo){
    42         -  return pWInfo->bOBSat!=0;
           42  +  return pWInfo->nOBSat;
    43     43   }
    44     44   
    45     45   /*
    46     46   ** Return the VDBE address or label to jump to in order to continue
    47     47   ** immediately with the next row of a WHERE clause.
    48     48   */
    49     49   int sqlite3WhereContinueLabel(WhereInfo *pWInfo){
................................................................................
  3033   3033       ** was passed to this function to implement a "SELECT min(x) ..." 
  3034   3034       ** query, then the caller will only allow the loop to run for
  3035   3035       ** a single iteration. This means that the first row returned
  3036   3036       ** should not have a NULL value stored in 'x'. If column 'x' is
  3037   3037       ** the first one after the nEq equality constraints in the index,
  3038   3038       ** this requires some special handling.
  3039   3039       */
         3040  +    assert( pWInfo->pOrderBy==0
         3041  +         || pWInfo->pOrderBy->nExpr==1
         3042  +         || (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)==0 );
  3040   3043       if( (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)!=0
  3041         -     && (pWInfo->bOBSat!=0)
         3044  +     && pWInfo->nOBSat>0
  3042   3045        && (pIdx->nKeyCol>nEq)
  3043   3046       ){
  3044   3047         assert( pLoop->u.btree.nSkip==0 );
  3045   3048         bSeekPastNull = 1;
  3046   3049         nExtraReg = 1;
  3047   3050       }
  3048   3051   
................................................................................
  4504   4507       if( i>=nConstraint ){
  4505   4508         pNew->nLTerm = mxTerm+1;
  4506   4509         assert( pNew->nLTerm<=pNew->nLSlot );
  4507   4510         pNew->u.vtab.idxNum = pIdxInfo->idxNum;
  4508   4511         pNew->u.vtab.needFree = pIdxInfo->needToFreeIdxStr;
  4509   4512         pIdxInfo->needToFreeIdxStr = 0;
  4510   4513         pNew->u.vtab.idxStr = pIdxInfo->idxStr;
  4511         -      pNew->u.vtab.isOrdered = (u8)((pIdxInfo->nOrderBy!=0)
  4512         -                                     && pIdxInfo->orderByConsumed);
         4514  +      pNew->u.vtab.isOrdered = (i8)(pIdxInfo->orderByConsumed ?
         4515  +                                      pIdxInfo->nOrderBy : 0);
  4513   4516         pNew->rSetup = 0;
  4514   4517         pNew->rRun = sqlite3LogEstFromDouble(pIdxInfo->estimatedCost);
  4515   4518         pNew->nOut = sqlite3LogEst(pIdxInfo->estimatedRows);
  4516   4519         whereLoopInsert(pBuilder, pNew);
  4517   4520         if( pNew->u.vtab.needFree ){
  4518   4521           sqlite3_free(pNew->u.vtab.idxStr);
  4519   4522           pNew->u.vtab.needFree = 0;
................................................................................
  4666   4669     whereLoopClear(db, pNew);
  4667   4670     return rc;
  4668   4671   }
  4669   4672   
  4670   4673   /*
  4671   4674   ** Examine a WherePath (with the addition of the extra WhereLoop of the 5th
  4672   4675   ** parameters) to see if it outputs rows in the requested ORDER BY
  4673         -** (or GROUP BY) without requiring a separate sort operation.  Return:
         4676  +** (or GROUP BY) without requiring a separate sort operation.  Return N:
  4674   4677   ** 
  4675         -**    0:  ORDER BY is not satisfied.  Sorting required
  4676         -**    1:  ORDER BY is satisfied.      Omit sorting
  4677         -**   -1:  Unknown at this time
         4678  +**   N>0:   N terms of the ORDER BY clause are satisfied
         4679  +**   N==0:  No terms of the ORDER BY clause are satisfied
         4680  +**   N<0:   Unknown yet how many terms of ORDER BY might be satisfied.   
  4678   4681   **
  4679   4682   ** Note that processing for WHERE_GROUPBY and WHERE_DISTINCTBY is not as
  4680   4683   ** strict.  With GROUP BY and DISTINCT the only requirement is that
  4681   4684   ** equivalent rows appear immediately adjacent to one another.  GROUP BY
  4682   4685   ** and DISTINT do not require rows to appear in any particular order as long
  4683   4686   ** as equivelent rows are grouped together.  Thus for GROUP BY and DISTINCT
  4684   4687   ** the pOrderBy terms can be matched in any order.  With ORDER BY, the 
  4685   4688   ** pOrderBy terms must be matched in strict left-to-right order.
  4686   4689   */
  4687         -static int wherePathSatisfiesOrderBy(
         4690  +static i8 wherePathSatisfiesOrderBy(
  4688   4691     WhereInfo *pWInfo,    /* The WHERE clause */
  4689   4692     ExprList *pOrderBy,   /* ORDER BY or GROUP BY or DISTINCT clause to check */
  4690   4693     WherePath *pPath,     /* The WherePath to check */
  4691   4694     u16 wctrlFlags,       /* Might contain WHERE_GROUPBY or WHERE_DISTINCTBY */
  4692   4695     u16 nLoop,            /* Number of entries in pPath->aLoop[] */
  4693   4696     WhereLoop *pLast,     /* Add this WhereLoop to the end of pPath->aLoop[] */
  4694   4697     Bitmask *pRevMask     /* OUT: Mask of WhereLoops to run in reverse order */
................................................................................
  4913   4916           if( mTerm==0 && !sqlite3ExprIsConstant(p) ) continue;
  4914   4917           if( (mTerm&~orderDistinctMask)==0 ){
  4915   4918             obSat |= MASKBIT(i);
  4916   4919           }
  4917   4920         }
  4918   4921       }
  4919   4922     } /* End the loop over all WhereLoops from outer-most down to inner-most */
  4920         -  if( obSat==obDone ) return 1;
  4921         -  if( !isOrderDistinct ) return 0;
         4923  +  if( obSat==obDone ) return nOrderBy;
         4924  +  if( !isOrderDistinct ){
         4925  +    for(i=nOrderBy-1; i>0; i--){
         4926  +      Bitmask m = MASKBIT(i) - 1;
         4927  +      if( (obSat&m)==m ) return i;
         4928  +    }
         4929  +    return 0;
         4930  +  }
  4922   4931     return -1;
  4923   4932   }
  4924   4933   
  4925   4934   #ifdef WHERETRACE_ENABLED
  4926   4935   /* For debugging use only: */
  4927   4936   static const char *wherePathName(WherePath *pPath, int nLoop, WhereLoop *pLast){
  4928   4937     static char zName[65];
................................................................................
  4951   4960     int mxChoice;             /* Maximum number of simultaneous paths tracked */
  4952   4961     int nLoop;                /* Number of terms in the join */
  4953   4962     Parse *pParse;            /* Parsing context */
  4954   4963     sqlite3 *db;              /* The database connection */
  4955   4964     int iLoop;                /* Loop counter over the terms of the join */
  4956   4965     int ii, jj;               /* Loop counters */
  4957   4966     int mxI = 0;              /* Index of next entry to replace */
         4967  +  int nOrderBy;             /* Number of ORDER BY clause terms */
  4958   4968     LogEst rCost;             /* Cost of a path */
  4959   4969     LogEst nOut;              /* Number of outputs */
  4960   4970     LogEst mxCost = 0;        /* Maximum cost of a set of paths */
  4961   4971     LogEst mxOut = 0;         /* Maximum nOut value on the set of paths */
  4962         -  LogEst rSortCost;         /* Cost to do a sort */
  4963   4972     int nTo, nFrom;           /* Number of valid entries in aTo[] and aFrom[] */
  4964   4973     WherePath *aFrom;         /* All nFrom paths at the previous level */
  4965   4974     WherePath *aTo;           /* The nTo best paths at the current level */
  4966   4975     WherePath *pFrom;         /* An element of aFrom[] that we are working on */
  4967   4976     WherePath *pTo;           /* An element of aTo[] that we are working on */
  4968   4977     WhereLoop *pWLoop;        /* One of the WhereLoop objects */
  4969   4978     WhereLoop **pX;           /* Used to divy up the pSpace memory */
................................................................................
  4997   5006     ** of computing an automatic index is not paid back within the first 25
  4998   5007     ** rows, then do not use the automatic index. */
  4999   5008     aFrom[0].nRow = MIN(pParse->nQueryLoop, 46);  assert( 46==sqlite3LogEst(25) );
  5000   5009     nFrom = 1;
  5001   5010   
  5002   5011     /* Precompute the cost of sorting the final result set, if the caller
  5003   5012     ** to sqlite3WhereBegin() was concerned about sorting */
  5004         -  rSortCost = 0;
  5005   5013     if( pWInfo->pOrderBy==0 || nRowEst==0 ){
  5006         -    aFrom[0].isOrderedValid = 1;
         5014  +    aFrom[0].isOrdered = 0;
         5015  +    nOrderBy = 0;
  5007   5016     }else{
  5008         -    /* TUNING: Estimated cost of sorting is 48*N*log2(N) where N is the
  5009         -    ** number of output rows. The 48 is the expected size of a row to sort. 
  5010         -    ** FIXME:  compute a better estimate of the 48 multiplier based on the
  5011         -    ** result set expressions. */
  5012         -    rSortCost = nRowEst + estLog(nRowEst);
  5013         -    WHERETRACE(0x002,("---- sort cost=%-3d\n", rSortCost));
         5017  +    aFrom[0].isOrdered = -1;
         5018  +    nOrderBy = pWInfo->pOrderBy->nExpr;
  5014   5019     }
  5015   5020   
  5016   5021     /* Compute successively longer WherePaths using the previous generation
  5017   5022     ** of WherePaths as the basis for the next.  Keep track of the mxChoice
  5018   5023     ** best paths at each generation */
  5019   5024     for(iLoop=0; iLoop<nLoop; iLoop++){
  5020   5025       nTo = 0;
  5021   5026       for(ii=0, pFrom=aFrom; ii<nFrom; ii++, pFrom++){
  5022   5027         for(pWLoop=pWInfo->pLoops; pWLoop; pWLoop=pWLoop->pNextLoop){
  5023   5028           Bitmask maskNew;
  5024   5029           Bitmask revMask = 0;
  5025         -        u8 isOrderedValid = pFrom->isOrderedValid;
  5026         -        u8 isOrdered = pFrom->isOrdered;
         5030  +        i8 isOrdered = pFrom->isOrdered;
  5027   5031           if( (pWLoop->prereq & ~pFrom->maskLoop)!=0 ) continue;
  5028   5032           if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue;
  5029   5033           /* At this point, pWLoop is a candidate to be the next loop. 
  5030   5034           ** Compute its cost */
  5031   5035           rCost = sqlite3LogEstAdd(pWLoop->rSetup,pWLoop->rRun + pFrom->nRow);
  5032   5036           rCost = sqlite3LogEstAdd(rCost, pFrom->rCost);
  5033   5037           nOut = pFrom->nRow + pWLoop->nOut;
  5034   5038           maskNew = pFrom->maskLoop | pWLoop->maskSelf;
  5035         -        if( !isOrderedValid ){
  5036         -          switch( wherePathSatisfiesOrderBy(pWInfo,
         5039  +        if( isOrdered<0 ){
         5040  +          isOrdered = wherePathSatisfiesOrderBy(pWInfo,
  5037   5041                          pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags,
  5038         -                       iLoop, pWLoop, &revMask) ){
  5039         -            case 1:  /* Yes.  pFrom+pWLoop does satisfy the ORDER BY clause */
  5040         -              isOrdered = 1;
  5041         -              isOrderedValid = 1;
  5042         -              break;
  5043         -            case 0:  /* No.  pFrom+pWLoop will require a separate sort */
  5044         -              isOrdered = 0;
  5045         -              isOrderedValid = 1;
  5046         -              rCost = sqlite3LogEstAdd(rCost, rSortCost);
  5047         -              break;
  5048         -            default: /* Cannot tell yet.  Try again on the next iteration */
  5049         -              break;
         5042  +                       iLoop, pWLoop, &revMask);
         5043  +          if( isOrdered>=0 && isOrdered<nOrderBy ){
         5044  +            /* TUNING: Estimated cost of sorting cost as roughly N*log(N).
         5045  +            ** If some but not all of the columns are in sorted order, then
         5046  +            ** scale down the log(N) term. */
         5047  +            LogEst rScale = sqlite3LogEst((nOrderBy-isOrdered)*100/nOrderBy);
         5048  +            LogEst rSortCost = nRowEst + estLog(nRowEst) + rScale - 66;
         5049  +            /* TUNING: The cost of implementing DISTINCT using a B-TREE is
         5050  +            ** also N*log(N) but it has a larger constant of proportionality.
         5051  +            ** Multiply by 3.0. */
         5052  +            if( pWInfo->wctrlFlags & WHERE_WANT_DISTINCT ){
         5053  +              rSortCost += 16;
         5054  +            }
         5055  +            WHERETRACE(0x002,
         5056  +               ("---- sort cost=%-3d (%d/%d) increases cost %3d to %-3d\n",
         5057  +                rSortCost, (nOrderBy-isOrdered), nOrderBy, rCost,
         5058  +                sqlite3LogEstAdd(rCost,rSortCost)));
         5059  +            rCost = sqlite3LogEstAdd(rCost, rSortCost);
  5050   5060             }
  5051   5061           }else{
  5052   5062             revMask = pFrom->revLoop;
  5053   5063           }
  5054   5064           /* Check to see if pWLoop should be added to the mxChoice best so far */
  5055   5065           for(jj=0, pTo=aTo; jj<nTo; jj++, pTo++){
  5056   5066             if( pTo->maskLoop==maskNew
  5057         -           && pTo->isOrderedValid==isOrderedValid
         5067  +           && ((pTo->isOrdered^isOrdered)&80)==0
  5058   5068              && ((pTo->rCost<=rCost && pTo->nRow<=nOut) ||
  5059   5069                   (pTo->rCost>=rCost && pTo->nRow>=nOut))
  5060   5070             ){
  5061   5071               testcase( jj==nTo-1 );
  5062   5072               break;
  5063   5073             }
  5064   5074           }
  5065   5075           if( jj>=nTo ){
  5066   5076             if( nTo>=mxChoice && rCost>=mxCost ){
  5067   5077   #ifdef WHERETRACE_ENABLED /* 0x4 */
  5068   5078               if( sqlite3WhereTrace&0x4 ){
  5069   5079                 sqlite3DebugPrintf("Skip   %s cost=%-3d,%3d order=%c\n",
  5070   5080                     wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,
  5071         -                  isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?');
         5081  +                  isOrdered>=0 ? isOrdered+'0' : '?');
  5072   5082               }
  5073   5083   #endif
  5074   5084               continue;
  5075   5085             }
  5076   5086             /* Add a new Path to the aTo[] set */
  5077   5087             if( nTo<mxChoice ){
  5078   5088               /* Increase the size of the aTo set by one */
................................................................................
  5082   5092               jj = mxI;
  5083   5093             }
  5084   5094             pTo = &aTo[jj];
  5085   5095   #ifdef WHERETRACE_ENABLED /* 0x4 */
  5086   5096             if( sqlite3WhereTrace&0x4 ){
  5087   5097               sqlite3DebugPrintf("New    %s cost=%-3d,%3d order=%c\n",
  5088   5098                   wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,
  5089         -                isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?');
         5099  +                isOrdered>=0 ? isOrdered+'0' : '?');
  5090   5100             }
  5091   5101   #endif
  5092   5102           }else{
  5093   5103             if( pTo->rCost<=rCost && pTo->nRow<=nOut ){
  5094   5104   #ifdef WHERETRACE_ENABLED /* 0x4 */
  5095   5105               if( sqlite3WhereTrace&0x4 ){
  5096   5106                 sqlite3DebugPrintf(
  5097   5107                     "Skip   %s cost=%-3d,%3d order=%c",
  5098   5108                     wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,
  5099         -                  isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?');
         5109  +                  isOrdered>=0 ? isOrdered+'0' : '?');
  5100   5110                 sqlite3DebugPrintf("   vs %s cost=%-3d,%d order=%c\n",
  5101   5111                     wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow,
  5102         -                  pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?');
         5112  +                  pTo->isOrdered>=0 ? pTo->isOrdered+'0' : '?');
  5103   5113               }
  5104   5114   #endif
  5105   5115               testcase( pTo->rCost==rCost );
  5106   5116               continue;
  5107   5117             }
  5108   5118             testcase( pTo->rCost==rCost+1 );
  5109   5119             /* A new and better score for a previously created equivalent path */
  5110   5120   #ifdef WHERETRACE_ENABLED /* 0x4 */
  5111   5121             if( sqlite3WhereTrace&0x4 ){
  5112   5122               sqlite3DebugPrintf(
  5113   5123                   "Update %s cost=%-3d,%3d order=%c",
  5114   5124                   wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,
  5115         -                isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?');
         5125  +                isOrdered>=0 ? isOrdered+'0' : '?');
  5116   5126               sqlite3DebugPrintf("  was %s cost=%-3d,%3d order=%c\n",
  5117   5127                   wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow,
  5118         -                pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?');
         5128  +                pTo->isOrdered>=0 ? pTo->isOrdered+'0' : '?');
  5119   5129             }
  5120   5130   #endif
  5121   5131           }
  5122   5132           /* pWLoop is a winner.  Add it to the set of best so far */
  5123   5133           pTo->maskLoop = pFrom->maskLoop | pWLoop->maskSelf;
  5124   5134           pTo->revLoop = revMask;
  5125   5135           pTo->nRow = nOut;
  5126   5136           pTo->rCost = rCost;
  5127         -        pTo->isOrderedValid = isOrderedValid;
  5128   5137           pTo->isOrdered = isOrdered;
  5129   5138           memcpy(pTo->aLoop, pFrom->aLoop, sizeof(WhereLoop*)*iLoop);
  5130   5139           pTo->aLoop[iLoop] = pWLoop;
  5131   5140           if( nTo>=mxChoice ){
  5132   5141             mxI = 0;
  5133   5142             mxCost = aTo[0].rCost;
  5134   5143             mxOut = aTo[0].nRow;
................................................................................
  5145   5154   
  5146   5155   #ifdef WHERETRACE_ENABLED  /* >=2 */
  5147   5156       if( sqlite3WhereTrace>=2 ){
  5148   5157         sqlite3DebugPrintf("---- after round %d ----\n", iLoop);
  5149   5158         for(ii=0, pTo=aTo; ii<nTo; ii++, pTo++){
  5150   5159           sqlite3DebugPrintf(" %s cost=%-3d nrow=%-3d order=%c",
  5151   5160              wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow,
  5152         -           pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?');
  5153         -        if( pTo->isOrderedValid && pTo->isOrdered ){
         5161  +           pTo->isOrdered>=0 ? (pTo->isOrdered+'0') : '?');
         5162  +        if( pTo->isOrdered>0 ){
  5154   5163             sqlite3DebugPrintf(" rev=0x%llx\n", pTo->revLoop);
  5155   5164           }else{
  5156   5165             sqlite3DebugPrintf("\n");
  5157   5166           }
  5158   5167         }
  5159   5168       }
  5160   5169   #endif
................................................................................
  5189   5198      && (pWInfo->wctrlFlags & WHERE_DISTINCTBY)==0
  5190   5199      && pWInfo->eDistinct==WHERE_DISTINCT_NOOP
  5191   5200      && nRowEst
  5192   5201     ){
  5193   5202       Bitmask notUsed;
  5194   5203       int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pResultSet, pFrom,
  5195   5204                    WHERE_DISTINCTBY, nLoop-1, pFrom->aLoop[nLoop-1], &notUsed);
  5196         -    if( rc==1 ) pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
         5205  +    if( rc==pWInfo->pResultSet->nExpr ){
         5206  +      pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
         5207  +    }
  5197   5208     }
  5198         -  if( pFrom->isOrdered ){
         5209  +  if( pWInfo->pOrderBy ){
  5199   5210       if( pWInfo->wctrlFlags & WHERE_DISTINCTBY ){
  5200         -      pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
         5211  +      if( pFrom->isOrdered==pWInfo->pOrderBy->nExpr ){
         5212  +        pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
         5213  +      }
  5201   5214       }else{
  5202         -      pWInfo->bOBSat = 1;
         5215  +      pWInfo->nOBSat = pFrom->isOrdered;
         5216  +      if( pWInfo->nOBSat<0 ) pWInfo->nOBSat = 0;
  5203   5217         pWInfo->revMask = pFrom->revLoop;
  5204   5218       }
  5205   5219     }
  5206   5220     pWInfo->nRowOut = pFrom->nRow;
  5207   5221   
  5208   5222     /* Free temporary memory and return success */
  5209   5223     sqlite3DbFree(db, pSpace);
................................................................................
  5280   5294     }
  5281   5295     if( pLoop->wsFlags ){
  5282   5296       pLoop->nOut = (LogEst)1;
  5283   5297       pWInfo->a[0].pWLoop = pLoop;
  5284   5298       pLoop->maskSelf = getMask(&pWInfo->sMaskSet, iCur);
  5285   5299       pWInfo->a[0].iTabCur = iCur;
  5286   5300       pWInfo->nRowOut = 1;
  5287         -    if( pWInfo->pOrderBy ) pWInfo->bOBSat =  1;
         5301  +    if( pWInfo->pOrderBy ) pWInfo->nOBSat =  pWInfo->pOrderBy->nExpr;
  5288   5302       if( pWInfo->wctrlFlags & WHERE_WANT_DISTINCT ){
  5289   5303         pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
  5290   5304       }
  5291   5305   #ifdef SQLITE_DEBUG
  5292   5306       pLoop->cId = '0';
  5293   5307   #endif
  5294   5308       return 1;
................................................................................
  5384   5398   ** be used to compute the appropriate cursor depending on which index is
  5385   5399   ** used.
  5386   5400   */
  5387   5401   WhereInfo *sqlite3WhereBegin(
  5388   5402     Parse *pParse,        /* The parser context */
  5389   5403     SrcList *pTabList,    /* FROM clause: A list of all tables to be scanned */
  5390   5404     Expr *pWhere,         /* The WHERE clause */
  5391         -  ExprList *pOrderBy,   /* An ORDER BY clause, or NULL */
         5405  +  ExprList *pOrderBy,   /* An ORDER BY (or GROUP BY) clause, or NULL */
  5392   5406     ExprList *pResultSet, /* Result set of the query */
  5393   5407     u16 wctrlFlags,       /* One of the WHERE_* flags defined in sqliteInt.h */
  5394   5408     int iIdxCur           /* If WHERE_ONETABLE_ONLY is set, index cursor number */
  5395   5409   ){
  5396   5410     int nByteWInfo;            /* Num. bytes allocated for WhereInfo struct */
  5397   5411     int nTabList;              /* Number of elements in pTabList */
  5398   5412     WhereInfo *pWInfo;         /* Will become the return value of this function */
................................................................................
  5406   5420     sqlite3 *db;               /* Database connection */
  5407   5421     int rc;                    /* Return code */
  5408   5422   
  5409   5423   
  5410   5424     /* Variable initialization */
  5411   5425     db = pParse->db;
  5412   5426     memset(&sWLB, 0, sizeof(sWLB));
         5427  +
         5428  +  /* An ORDER/GROUP BY clause of more than 63 terms cannot be optimized */
         5429  +  testcase( pOrderBy && pOrderBy->nExpr==BMS-1 );
         5430  +  if( pOrderBy && pOrderBy->nExpr>=BMS ) pOrderBy = 0;
  5413   5431     sWLB.pOrderBy = pOrderBy;
  5414   5432   
  5415   5433     /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via
  5416   5434     ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */
  5417   5435     if( OptimizationDisabled(db, SQLITE_DistinctOpt) ){
  5418   5436       wctrlFlags &= ~WHERE_WANT_DISTINCT;
  5419   5437     }
................................................................................
  5484   5502         sWLB.pWC->a[ii].wtFlags |= TERM_CODED;
  5485   5503       }
  5486   5504     }
  5487   5505   
  5488   5506     /* Special case: No FROM clause
  5489   5507     */
  5490   5508     if( nTabList==0 ){
  5491         -    if( pOrderBy ) pWInfo->bOBSat = 1;
         5509  +    if( pOrderBy ) pWInfo->nOBSat = pOrderBy->nExpr;
  5492   5510       if( wctrlFlags & WHERE_WANT_DISTINCT ){
  5493   5511         pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
  5494   5512       }
  5495   5513     }
  5496   5514   
  5497   5515     /* Assign a bit from the bitmask to every term in the FROM clause.
  5498   5516     **
................................................................................
  5595   5613     if( pParse->nErr || NEVER(db->mallocFailed) ){
  5596   5614       goto whereBeginError;
  5597   5615     }
  5598   5616   #ifdef WHERETRACE_ENABLED /* !=0 */
  5599   5617     if( sqlite3WhereTrace ){
  5600   5618       int ii;
  5601   5619       sqlite3DebugPrintf("---- Solution nRow=%d", pWInfo->nRowOut);
  5602         -    if( pWInfo->bOBSat ){
  5603         -      sqlite3DebugPrintf(" ORDERBY=0x%llx", pWInfo->revMask);
         5620  +    if( pWInfo->nOBSat>0 ){
         5621  +      sqlite3DebugPrintf(" ORDERBY=%d,0x%llx", pWInfo->nOBSat, pWInfo->revMask);
  5604   5622       }
  5605   5623       switch( pWInfo->eDistinct ){
  5606   5624         case WHERE_DISTINCT_UNIQUE: {
  5607   5625           sqlite3DebugPrintf("  DISTINCT=unique");
  5608   5626           break;
  5609   5627         }
  5610   5628         case WHERE_DISTINCT_ORDERED: {

Changes to src/whereInt.h.

   117    117         u16 nEq;               /* Number of equality constraints */
   118    118         u16 nSkip;             /* Number of initial index columns to skip */
   119    119         Index *pIndex;         /* Index used, or NULL */
   120    120       } btree;
   121    121       struct {               /* Information for virtual tables */
   122    122         int idxNum;            /* Index number */
   123    123         u8 needFree;           /* True if sqlite3_free(idxStr) is needed */
   124         -      u8 isOrdered;          /* True if satisfies ORDER BY */
          124  +      i8 isOrdered;          /* True if satisfies ORDER BY */
   125    125         u16 omitMask;          /* Terms that may be omitted */
   126    126         char *idxStr;          /* Index identifier string */
   127    127       } vtab;
   128    128     } u;
   129    129     u32 wsFlags;          /* WHERE_* flags describing the plan */
   130    130     u16 nLTerm;           /* Number of entries in aLTerm[] */
   131    131     /**** whereLoopXfer() copies fields above ***********************/
................................................................................
   179    179   ** at the end is the choosen query plan.
   180    180   */
   181    181   struct WherePath {
   182    182     Bitmask maskLoop;     /* Bitmask of all WhereLoop objects in this path */
   183    183     Bitmask revLoop;      /* aLoop[]s that should be reversed for ORDER BY */
   184    184     LogEst nRow;          /* Estimated number of rows generated by this path */
   185    185     LogEst rCost;         /* Total cost of this path */
   186         -  u8 isOrdered;         /* True if this path satisfies ORDER BY */
   187         -  u8 isOrderedValid;    /* True if the isOrdered field is valid */
          186  +  i8 isOrdered;         /* No. of ORDER BY terms satisfied. -1 for unknown */
   188    187     WhereLoop **aLoop;    /* Array of WhereLoop objects implementing this path */
   189    188   };
   190    189   
   191    190   /*
   192    191   ** The query generator uses an array of instances of this structure to
   193    192   ** help it analyze the subexpressions of the WHERE clause.  Each WHERE
   194    193   ** clause subexpression is separated from the others by AND operators,
................................................................................
   394    393     SrcList *pTabList;        /* List of tables in the join */
   395    394     ExprList *pOrderBy;       /* The ORDER BY clause or NULL */
   396    395     ExprList *pResultSet;     /* Result set. DISTINCT operates on these */
   397    396     WhereLoop *pLoops;        /* List of all WhereLoop objects */
   398    397     Bitmask revMask;          /* Mask of ORDER BY terms that need reversing */
   399    398     LogEst nRowOut;           /* Estimated number of output rows */
   400    399     u16 wctrlFlags;           /* Flags originally passed to sqlite3WhereBegin() */
   401         -  u8 bOBSat;                /* ORDER BY satisfied by indices */
          400  +  i8 nOBSat;                /* Number of ORDER BY terms satisfied by indices */
   402    401     u8 okOnePass;             /* Ok to use one-pass algorithm for UPDATE/DELETE */
   403    402     u8 untestedTerms;         /* Not all WHERE terms resolved by outer loop */
   404    403     u8 eDistinct;             /* One of the WHERE_DISTINCT_* values below */
   405    404     u8 nLevel;                /* Number of nested loop */
   406    405     int iTop;                 /* The very beginning of the WHERE loop */
   407    406     int iContinue;            /* Jump here to continue with next record */
   408    407     int iBreak;               /* Jump here to break out of the loop */

Changes to test/distinct.test.

   158    158     INSERT INTO t1 VALUES('a', 'b', 'c');
   159    159     INSERT INTO t1 VALUES('A', 'B', 'C');
   160    160   }
   161    161   
   162    162   foreach {tn sql temptables res} {
   163    163     1   "a, b FROM t1"                                       {}      {A B a b}
   164    164     2   "b, a FROM t1"                                       {}      {B A b a}
   165         -  3   "a, b, c FROM t1"                                    {hash}  {a b c A B C}
          165  +  3   "a, b, c FROM t1"                                    {hash}  {A B C a b c}
   166    166     4   "a, b, c FROM t1 ORDER BY a, b, c"                   {btree} {A B C a b c}
   167    167     5   "b FROM t1 WHERE a = 'a'"                            {}      {b}
   168    168     6   "b FROM t1 ORDER BY +b COLLATE binary"          {btree hash} {B b}
   169    169     7   "a FROM t1"                                          {}      {A a}
   170    170     8   "b COLLATE nocase FROM t1"                           {}      {b}
   171    171     9   "b COLLATE nocase FROM t1 ORDER BY b COLLATE nocase" {}      {b}
   172    172   } {

Changes to test/orderby5.test.

    60     60     EXPLAIN QUERY PLAN
    61     61     SELECT DISTINCT c, b, a FROM t1 WHERE a=0;
    62     62   } {~/B-TREE/}
    63     63   do_execsql_test 1.7 {
    64     64     EXPLAIN QUERY PLAN
    65     65     SELECT DISTINCT c, b, a FROM t1 WHERE +a=0;
    66     66   } {/B-TREE/}
    67         -do_execsql_test 2.1 {
           67  +
           68  +# In some cases, it is faster to do repeated index lookups than it is to
           69  +# sort.  But in other cases, it is faster to sort than to do repeated index
           70  +# lookups.
           71  +#
           72  +do_execsql_test 2.1a {
           73  +  CREATE TABLE t2(a,b,c);
           74  +  CREATE INDEX t2bc ON t2(b,c);
           75  +  ANALYZE;
           76  +  INSERT INTO sqlite_stat1 VALUES('t1','t1bc','1000000 10 9');
           77  +  INSERT INTO sqlite_stat1 VALUES('t2','t2bc','100 10 5');
           78  +  ANALYZE sqlite_master;
           79  +
           80  +  EXPLAIN QUERY PLAN
           81  +  SELECT * FROM t2 WHERE a=0 ORDER BY a, b, c;
           82  +} {~/B-TREE/}
           83  +do_execsql_test 2.1b {
    68     84     EXPLAIN QUERY PLAN
    69     85     SELECT * FROM t1 WHERE a=0 ORDER BY a, b, c;
    70         -} {~/B-TREE/}
           86  +} {/B-TREE/}
           87  +
           88  +
    71     89   do_execsql_test 2.2 {
    72     90     EXPLAIN QUERY PLAN
    73     91     SELECT * FROM t1 WHERE +a=0 ORDER BY a, b, c;
    74     92   } {/B-TREE/}
    75     93   do_execsql_test 2.3 {
    76     94     EXPLAIN QUERY PLAN
    77     95     SELECT * FROM t1 WHERE a=0 ORDER BY b, a, c;

Added test/orderby6.test.

            1  +# 2014-03-21
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#***********************************************************************
           11  +# This file implements regression tests for SQLite library.  The
           12  +# focus of this file is testing that the block-sort optimization.
           13  +#
           14  +
           15  +
           16  +set testdir [file dirname $argv0]
           17  +source $testdir/tester.tcl
           18  +set ::testprefix orderby6
           19  +
           20  +# Run all tests twice.  Once with a normal table and a second time
           21  +# with a WITHOUT ROWID table
           22  +#
           23  +foreach {tn rowidclause} {1 {} 2 {WITHOUT ROWID}} {
           24  +
           25  +  # Construct a table with 1000 rows and a split primary key
           26  +  #
           27  +  reset_db
           28  +  do_test $tn.1 {
           29  +    db eval "CREATE TABLE t1(a,b,c,PRIMARY KEY(b,c)) $rowidclause;"
           30  +    db eval {
           31  +      WITH RECURSIVE
           32  +       cnt(x) AS (VALUES(1) UNION ALL SELECT x+1 FROM cnt WHERE x<1000)
           33  +     INSERT INTO t1 SELECT x, x%40, x/40 FROM cnt;
           34  +    }
           35  +  } {}
           36  +
           37  +  # Run various ORDER BY queries that can benefit from block-sort.
           38  +  # Compare the output to the same output using a full-sort enforced
           39  +  # by adding + to each term of the ORDER BY clause.
           40  +  #
           41  +  do_execsql_test $tn.2 {
           42  +    SELECT b,a,c FROM t1 ORDER BY b,a,c;
           43  +  } [db eval {SELECT b,a,c FROM t1 ORDER BY +b,+a,+c}]
           44  +  do_execsql_test $tn.3 {
           45  +    SELECT b,a,c FROM t1 ORDER BY b,c DESC,a;
           46  +  } [db eval {SELECT b,a,c FROM t1 ORDER BY +b,+c DESC,+a}]
           47  +  do_execsql_test $tn.4 {
           48  +    SELECT b,a,c FROM t1 ORDER BY b DESC,c,a;
           49  +  } [db eval {SELECT b,a,c FROM t1 ORDER BY +b DESC,+c,+a}]
           50  +  do_execsql_test $tn.5 {
           51  +    SELECT b,a,c FROM t1 ORDER BY b DESC,a,c;
           52  +  } [db eval {SELECT b,a,c FROM t1 ORDER BY +b DESC,+a,+c}]
           53  +
           54  +  # LIMIT and OFFSET clauses on block-sort queries.
           55  +  #
           56  +  do_execsql_test $tn.11 {
           57  +    SELECT a FROM t1 ORDER BY b, a LIMIT 10 OFFSET 20;
           58  +  } {840 880 920 960 1000 1 41 81 121 161}
           59  +  do_execsql_test $tn.11x {
           60  +    SELECT a FROM t1 ORDER BY +b, a LIMIT 10 OFFSET 20;
           61  +  } {840 880 920 960 1000 1 41 81 121 161}
           62  +
           63  +  do_execsql_test $tn.12 {
           64  +    SELECT a FROM t1 ORDER BY b DESC, a LIMIT 10 OFFSET 20;
           65  +  } {839 879 919 959 999 38 78 118 158 198}
           66  +  do_execsql_test $tn.12 {
           67  +    SELECT a FROM t1 ORDER BY +b DESC, a LIMIT 10 OFFSET 20;
           68  +  } {839 879 919 959 999 38 78 118 158 198}
           69  +
           70  +  do_execsql_test $tn.13 {
           71  +    SELECT a FROM t1 ORDER BY b, a DESC LIMIT 10 OFFSET 45;
           72  +  } {161 121 81 41 1 962 922 882 842 802}
           73  +  do_execsql_test $tn.13x {
           74  +    SELECT a FROM t1 ORDER BY +b, a DESC LIMIT 10 OFFSET 45;
           75  +  } {161 121 81 41 1 962 922 882 842 802}
           76  +
           77  +  do_execsql_test $tn.14 {
           78  +    SELECT a FROM t1 ORDER BY b DESC, a LIMIT 10 OFFSET 45;
           79  +  } {838 878 918 958 998 37 77 117 157 197}
           80  +  do_execsql_test $tn.14x {
           81  +    SELECT a FROM t1 ORDER BY +b DESC, a LIMIT 10 OFFSET 45;
           82  +  } {838 878 918 958 998 37 77 117 157 197}
           83  +
           84  +  # Many test cases where the LIMIT+OFFSET window is in various
           85  +  # alignments with block-sort boundaries.
           86  +  #
           87  +  foreach {tx limit offset orderby} {
           88  +     1  10 24 {+b,+a}
           89  +     2  10 25 {+b,+a}
           90  +     3  10 26 {+b,+a}
           91  +     4  10 39 {+b,+a}
           92  +     5  10 40 {+b,+a}
           93  +     6  10 41 {+b,+a}
           94  +     7  27 24 {+b,+a}
           95  +     8  27 49 {+b,+a}
           96  +     11 10 24 {+b DESC,+a}
           97  +     12 10 25 {+b DESC,+a}
           98  +     13 10 26 {+b DESC,+a}
           99  +     14 10 39 {+b DESC,+a}
          100  +     15 10 40 {+b DESC,+a}
          101  +     16 10 41 {+b DESC,+a}
          102  +     17 27 24 {+b DESC,+a}
          103  +     18 27 49 {+b DESC,+a}
          104  +     21 10 24 {+b,+a DESC}
          105  +     22 10 25 {+b,+a DESC}
          106  +     23 10 26 {+b,+a DESC}
          107  +     24 10 39 {+b,+a DESC}
          108  +     25 10 40 {+b,+a DESC}
          109  +     26 10 41 {+b,+a DESC}
          110  +     27 27 24 {+b,+a DESC}
          111  +     28 27 49 {+b,+a DESC}
          112  +     31 10 24 {+b DESC,+a DESC}
          113  +     32 10 25 {+b DESC,+a DESC}
          114  +     33 10 26 {+b DESC,+a DESC}
          115  +     34 10 39 {+b DESC,+a DESC}
          116  +     35 10 40 {+b DESC,+a DESC}
          117  +     36 10 41 {+b DESC,+a DESC}
          118  +     37 27 24 {+b DESC,+a DESC}
          119  +     38 27 49 {+b DESC,+a DESC}
          120  +  } {
          121  +    set sql1 "SELECT a FROM t1 ORDER BY $orderby LIMIT $limit OFFSET $offset;"
          122  +    set sql2 [string map {+ {}} $sql1]
          123  +    # puts $sql2\n$sql1\n[db eval $sql2]
          124  +    do_test $tn.21.$tx {db eval $::sql2} [db eval $sql1]
          125  +  }
          126  +
          127  +  ########################################################################
          128  +  # A second test table, t2, has many columns open to sorting.
          129  +  do_test $tn.31 {
          130  +    db eval "CREATE TABLE t2(a,b,c,d,e,f,PRIMARY KEY(b,c,d,e,f)) $rowidclause;"
          131  +    db eval {
          132  +      WITH RECURSIVE
          133  +       cnt(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM cnt WHERE x<242)
          134  +     INSERT INTO t2 SELECT x,  x%3, (x/3)%3, (x/9)%3, (x/27)%3, (x/81)%3
          135  +                      FROM cnt;
          136  +    }
          137  +  } {}
          138  +
          139  +  do_execsql_test $tn.32 {
          140  +    SELECT a FROM t2 ORDER BY b,c,d,e,f;
          141  +  } [db eval {SELECT a FROM t2 ORDER BY +b,+c,+d,+e,+f;}]
          142  +  do_execsql_test $tn.33 {
          143  +    SELECT a FROM t2 ORDER BY b,c,d,e,+f;
          144  +  } [db eval {SELECT a FROM t2 ORDER BY +b,+c,+d,+e,+f;}]
          145  +  do_execsql_test $tn.34 {
          146  +    SELECT a FROM t2 ORDER BY b,c,d,+e,+f;
          147  +  } [db eval {SELECT a FROM t2 ORDER BY +b,+c,+d,+e,+f;}]
          148  +  do_execsql_test $tn.35 {
          149  +    SELECT a FROM t2 ORDER BY b,c,+d,+e,+f;
          150  +  } [db eval {SELECT a FROM t2 ORDER BY +b,+c,+d,+e,+f;}]
          151  +  do_execsql_test $tn.36 {
          152  +    SELECT a FROM t2 ORDER BY b,+c,+d,+e,+f;
          153  +  } [db eval {SELECT a FROM t2 ORDER BY +b,+c,+d,+e,+f;}]
          154  +
          155  +  do_execsql_test $tn.37 {
          156  +    SELECT a FROM t2 ORDER BY b,c,d,e,f DESC;
          157  +  } [db eval {SELECT a FROM t2 ORDER BY +b,+c,+d,+e,+f DESC;}]
          158  +  do_execsql_test $tn.38 {
          159  +    SELECT a FROM t2 ORDER BY b,c,d,e DESC,f;
          160  +  } [db eval {SELECT a FROM t2 ORDER BY +b,+c,+d,+e DESC,+f;}]
          161  +  do_execsql_test $tn.39 {
          162  +    SELECT a FROM t2 ORDER BY b,c,d DESC,e,f;
          163  +  } [db eval {SELECT a FROM t2 ORDER BY +b,+c,+d DESC,+e,+f;}]
          164  +  do_execsql_test $tn.40 {
          165  +    SELECT a FROM t2 ORDER BY b,c DESC,d,e,f;
          166  +  } [db eval {SELECT a FROM t2 ORDER BY +b,+c DESC,+d,+e,+f;}]
          167  +  do_execsql_test $tn.41 {
          168  +    SELECT a FROM t2 ORDER BY b DESC,c,d,e,f;
          169  +  } [db eval {SELECT a FROM t2 ORDER BY +b DESC,+c,+d,+e,+f;}]
          170  +
          171  +  do_execsql_test $tn.42 {
          172  +    SELECT a FROM t2 ORDER BY b DESC,c DESC,d,e,f LIMIT 31;
          173  +  } [db eval {SELECT a FROM t2 ORDER BY +b DESC,+c DESC,+d,+e,+f LIMIT 31}]
          174  +  do_execsql_test $tn.43 {
          175  +    SELECT a FROM t2 ORDER BY b,c,d,e,f DESC LIMIT 8 OFFSET 7;
          176  +  } [db eval {SELECT a FROM t2 ORDER BY +b,+c,+d,+e,+f DESC LIMIT 8 OFFSET 7}]
          177  +
          178  +
          179  +}
          180  +
          181  +
          182  +
          183  +finish_test

Changes to test/whereG.test.

    91     91   
    92     92   do_eqp_test whereG-1.5 {
    93     93     SELECT DISTINCT aname
    94     94       FROM album, composer, track
    95     95      WHERE cname LIKE '%bach%'
    96     96        AND composer.cid=track.cid
    97     97        AND album.aid=track.aid;
    98         -} {/.*track.*composer.*album.*/}
           98  +} {/.*track.*(composer.*album|album.*composer).*/}
    99     99   do_execsql_test whereG-1.6 {
   100    100     SELECT DISTINCT aname
   101    101       FROM album, composer, track
   102    102      WHERE cname LIKE '%bach%'
   103    103        AND composer.cid=track.cid
   104    104        AND album.aid=track.aid;
   105    105   } {{Mass in B Minor, BWV 232}}
................................................................................
   106    106   
   107    107   do_eqp_test whereG-1.7 {
   108    108     SELECT DISTINCT aname
   109    109       FROM album, composer, track
   110    110      WHERE cname LIKE '%bach%'
   111    111        AND unlikely(composer.cid=track.cid)
   112    112        AND unlikely(album.aid=track.aid);
   113         -} {/.*track.*composer.*album.*/}
          113  +} {/.*track.*(composer.*album|album.*composer).*/}
   114    114   do_execsql_test whereG-1.8 {
   115    115     SELECT DISTINCT aname
   116    116       FROM album, composer, track
   117    117      WHERE cname LIKE '%bach%'
   118    118        AND unlikely(composer.cid=track.cid)
   119    119        AND unlikely(album.aid=track.aid);
   120    120   } {{Mass in B Minor, BWV 232}}