/ Check-in [956e4d7f]
Login

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

Overview
Comment:Update the query planner to recognize more cases where ORDER BY clauses can be optimized out. Add test cases to verify correct behavior of the ORDER BY optimization when the covering-index-scan optimization is disabled. Fix a harmless compiler warning in the TCL interface.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 956e4d7f8958e7065ff2d61cd71519d6f4113d4a
User & Date: drh 2012-10-03 12:56:18
References
2013-03-27
11:39 Ticket [a179fe74] Incorrect output order on a join with an ORDER BY status still Open with 7 other changes artifact: 41623a1a user: drh
2013-01-09
09:39 New ticket [c997b11c] ORDER BY clause ignored in 3-way join query. artifact: 55771e45 user: dan
Context
2012-10-03
18:09
Fix an out-of-order memset() that occurs before all variable declarations are finished. Also fix a line that exceeds the 80-character line length limit. check-in: ba2f492f user: drh tags: trunk
12:56
Update the query planner to recognize more cases where ORDER BY clauses can be optimized out. Add test cases to verify correct behavior of the ORDER BY optimization when the covering-index-scan optimization is disabled. Fix a harmless compiler warning in the TCL interface. check-in: 956e4d7f user: drh tags: trunk
12:38
Fix a query planner problem that only occurs when covering-index-scan is disabled. Fix to tests whose output changed due to the new and more aggressive ORDER BY optimization. Closed-Leaf check-in: 0f9bb901 user: drh tags: qp-enhancements
11:02
Fix the TCL interface so that SQL functions implemented in TCL honor the "nullvalue" setting. Also remove from the TCL interface some unused legacy UTF8 translation code left over from SQLite2. check-in: c1f10a26 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/tclsqlite.c.

  1485   1485         return Tcl_NewDoubleObj(sqlite3_column_double(pStmt, iCol));
  1486   1486       }
  1487   1487       case SQLITE_NULL: {
  1488   1488         return Tcl_NewStringObj(p->pDb->zNull, -1);
  1489   1489       }
  1490   1490     }
  1491   1491   
  1492         -  return Tcl_NewStringObj(sqlite3_column_text(pStmt, iCol), -1);
         1492  +  return Tcl_NewStringObj((char*)sqlite3_column_text(pStmt, iCol), -1);
  1493   1493   }
  1494   1494   
  1495   1495   /*
  1496   1496   ** If using Tcl version 8.6 or greater, use the NR functions to avoid
  1497   1497   ** recursive evalution of scripts by the [db eval] and [db trans]
  1498   1498   ** commands. Even if the headers used while compiling the extension
  1499   1499   ** are 8.6 or newer, the code still tests the Tcl version at runtime.

Changes to src/where.c.

   254    254   #define WHERE_INDEXED      0x000f0000  /* Anything that uses an index */
   255    255   #define WHERE_NOT_FULLSCAN 0x100f3000  /* Does not do a full table scan */
   256    256   #define WHERE_IN_ABLE      0x000f1000  /* Able to support an IN operator */
   257    257   #define WHERE_TOP_LIMIT    0x00100000  /* x<EXPR or x<=EXPR constraint */
   258    258   #define WHERE_BTM_LIMIT    0x00200000  /* x>EXPR or x>=EXPR constraint */
   259    259   #define WHERE_BOTH_LIMIT   0x00300000  /* Both x>EXPR and x<EXPR */
   260    260   #define WHERE_IDX_ONLY     0x00400000  /* Use index only - omit table */
   261         -#define WHERE_ORDERBY      0x00800000  /* Output will appear in correct order */
          261  +#define WHERE_ORDERED      0x00800000  /* Output will appear in correct order */
   262    262   #define WHERE_REVERSE      0x01000000  /* Scan in reverse order */
   263    263   #define WHERE_UNIQUE       0x02000000  /* Selects no more than one row */
   264    264   #define WHERE_ALL_UNIQUE   0x04000000  /* This and all prior have one row */
   265    265   #define WHERE_VIRTUALTABLE 0x08000000  /* Use virtual-table processing */
   266    266   #define WHERE_MULTI_OR     0x10000000  /* OR using multiple indices */
   267    267   #define WHERE_TEMP_INDEX   0x20000000  /* Uses an ephemeral index */
   268    268   #define WHERE_DISTINCT     0x40000000  /* Correct order for DISTINCT */
................................................................................
   285    285     ExprList *pOrderBy;             /* The ORDER BY clause */
   286    286     ExprList *pDistinct;            /* The select-list if query is DISTINCT */
   287    287     sqlite3_index_info **ppIdxInfo; /* Index information passed to xBestIndex */
   288    288     int i, n;                       /* Which loop is being coded; # of loops */
   289    289     WhereLevel *aLevel;             /* Info about outer loops */
   290    290     WhereCost cost;                 /* Lowest cost query plan */
   291    291   };
          292  +
          293  +/*
          294  +** Return TRUE if the probe cost is less than the baseline cost
          295  +*/
          296  +static int compareCost(const WhereCost *pProbe, const WhereCost *pBaseline){
          297  +  if( pProbe->rCost<pBaseline->rCost ) return 1;
          298  +  if( pProbe->rCost>pBaseline->rCost ) return 0;
          299  +  if( pProbe->plan.nOBSat>pBaseline->plan.nOBSat ) return 1;
          300  +  if( pProbe->plan.nRow<pBaseline->plan.nRow ) return 1;
          301  +  return 0;
          302  +}
   292    303   
   293    304   /*
   294    305   ** Initialize a preallocated WhereClause structure.
   295    306   */
   296    307   static void whereClauseInit(
   297    308     WhereClause *pWC,        /* The WhereClause to be initialized */
   298    309     Parse *pParse,           /* The parsing context */
................................................................................
  1758   1769         ** less than the current cost stored in pCost, replace the contents
  1759   1770         ** of pCost. */
  1760   1771         WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n", rTotal, nRow));
  1761   1772         if( rTotal<p->cost.rCost ){
  1762   1773           p->cost.rCost = rTotal;
  1763   1774           p->cost.used = used;
  1764   1775           p->cost.plan.nRow = nRow;
         1776  +        p->cost.plan.nOBSat = p->i ? p->aLevel[p->i-1].plan.nOBSat : 0;
  1765   1777           p->cost.plan.wsFlags = flags;
  1766   1778           p->cost.plan.u.pTerm = pTerm;
  1767   1779         }
  1768   1780       }
  1769   1781     }
  1770   1782   #endif /* SQLITE_OMIT_OR_OPTIMIZATION */
  1771   1783   }
................................................................................
  2300   2312     if( (SQLITE_BIG_DBL/((double)2))<rCost ){
  2301   2313       p->cost.rCost = (SQLITE_BIG_DBL/((double)2));
  2302   2314     }else{
  2303   2315       p->cost.rCost = rCost;
  2304   2316     }
  2305   2317     p->cost.plan.u.pVtabIdx = pIdxInfo;
  2306   2318     if( pIdxInfo->orderByConsumed ){
  2307         -    p->cost.plan.wsFlags |= WHERE_ORDERBY;
         2319  +    p->cost.plan.wsFlags |= WHERE_ORDERED;
         2320  +    p->cost.plan.nOBSat = nOrderBy;
         2321  +  }else{
         2322  +    p->cost.plan.nOBSat = p->i ? p->aLevel[p->i-1].plan.nOBSat : 0;
  2308   2323     }
  2309   2324     p->cost.plan.nEq = 0;
  2310   2325     pIdxInfo->nOrderBy = nOrderBy;
  2311   2326   
  2312   2327     /* Try to find a more efficient access pattern by using multiple indexes
  2313   2328     ** to optimize an OR expression within the WHERE clause. 
  2314   2329     */
................................................................................
  2726   2741     Index *pIdx;
  2727   2742     u8 sortOrder;
  2728   2743     for(i=p->i-1; i>=0; i--, pLevel--){
  2729   2744       if( pLevel->iTabCur!=iTab ) continue;
  2730   2745       if( (pLevel->plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){
  2731   2746         return 1;
  2732   2747       }
  2733         -    if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
  2734         -      pIdx = pLevel->plan.u.pIdx;
         2748  +    if( (pLevel->plan.wsFlags & WHERE_ORDERED)==0 ){
         2749  +      return 0;
         2750  +    }
         2751  +    if( (pIdx = pLevel->plan.u.pIdx)!=0 ){
  2735   2752         if( iCol<0 ){
  2736   2753           sortOrder = 0;
  2737   2754           testcase( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 );
  2738   2755         }else{
  2739   2756           int n = pIdx->nColumn;
  2740   2757           for(j=0; j<n; j++){
  2741   2758             if( iCol==pIdx->aiColumn[j] ) break;
................................................................................
  2829   2846   
  2830   2847     if( p->i==0 ){
  2831   2848       nPriorSat = 0;
  2832   2849     }else{
  2833   2850       nPriorSat = p->aLevel[p->i-1].plan.nOBSat;
  2834   2851       if( OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ) return nPriorSat;
  2835   2852     }
  2836         -  if( p->i==0 || (p->aLevel[p->i-1].plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){
         2853  +  if( nEqCol==0 ){
         2854  +    if( p->i && (p->aLevel[p->i-1].plan.wsFlags & WHERE_ORDERED)==0 ){
         2855  +      return nPriorSat;
         2856  +    }
         2857  +    nEqOneRow = 0;
         2858  +  }else if( p->i==0 || (p->aLevel[p->i-1].plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){
  2837   2859       nEqOneRow = nEqCol;
  2838   2860     }else{
  2839         -    if( nEqCol==0 ) return nPriorSat;
  2840   2861       sortOrder = bOuterRev;
  2841   2862       nEqOneRow = -1;
  2842   2863     }
  2843   2864     pOrderBy = p->pOrderBy;
  2844   2865     assert( pOrderBy!=0 );
  2845   2866     if( wsFlags & WHERE_COLUMN_IN ) return nPriorSat;
  2846   2867     if( pIdx->bUnordered ) return nPriorSat;
................................................................................
  3039   3060       pIdx = 0;
  3040   3061     }
  3041   3062   
  3042   3063     /* Loop over all indices looking for the best one to use
  3043   3064     */
  3044   3065     for(; pProbe; pIdx=pProbe=pProbe->pNext){
  3045   3066       const tRowcnt * const aiRowEst = pProbe->aiRowEst;
  3046         -    double cost;                /* Cost of using pProbe */
  3047         -    double nRow;                /* Estimated number of rows in result set */
         3067  +    WhereCost pc;               /* Cost of using pProbe */
  3048   3068       double log10N = (double)1;  /* base-10 logarithm of nRow (inexact) */
  3049   3069       int bRev = 2;               /* 0=forward scan.  1=reverse.  2=undecided */
  3050         -    int wsFlags = 0;
  3051         -    Bitmask used = 0;
         3070  +    memset(&pc, 0, sizeof(pc));
  3052   3071   
  3053   3072       /* The following variables are populated based on the properties of
  3054   3073       ** index being evaluated. They are then used to determine the expected
  3055   3074       ** cost and number of rows returned.
  3056   3075       **
  3057         -    **  nEq: 
         3076  +    **  pc.plan.nEq: 
  3058   3077       **    Number of equality terms that can be implemented using the index.
  3059   3078       **    In other words, the number of initial fields in the index that
  3060   3079       **    are used in == or IN or NOT NULL constraints of the WHERE clause.
  3061   3080       **
  3062   3081       **  nInMul:  
  3063   3082       **    The "in-multiplier". This is an estimate of how many seek operations 
  3064   3083       **    SQLite must perform on the index in question. For example, if the 
................................................................................
  3116   3135       **    two queries requires table b-tree lookups in order to find the value
  3117   3136       **    of column c, but the first does not because columns a and b are
  3118   3137       **    both available in the index.
  3119   3138       **
  3120   3139       **             SELECT a, b    FROM tbl WHERE a = 1;
  3121   3140       **             SELECT a, b, c FROM tbl WHERE a = 1;
  3122   3141       */
  3123         -    int nEq;                      /* Number of == or IN terms matching index */
  3124   3142       int nOrdered;                 /* Number of ordered terms matching index */
  3125   3143       int bInEst = 0;               /* True if "x IN (SELECT...)" seen */
  3126   3144       int nInMul = 1;               /* Number of distinct equalities to lookup */
  3127   3145       double rangeDiv = (double)1;  /* Estimated reduction in search space */
  3128   3146       int nBound = 0;               /* Number of range constraints seen */
  3129   3147       int bSort;                    /* True if external sort required */
  3130   3148       int bDist;                    /* True if index cannot help with DISTINCT */
  3131   3149       int bLookup = 0;              /* True if not a covering index */
  3132         -    int nOBSat = 0;               /* Number of ORDER BY terms satisfied */
         3150  +    int nPriorSat;                /* ORDER BY terms satisfied by outer loops */
  3133   3151       int nOrderBy;                 /* Number of ORDER BY terms */
  3134   3152       WhereTerm *pTerm;             /* A single term of the WHERE clause */
  3135   3153   #ifdef SQLITE_ENABLE_STAT3
  3136   3154       WhereTerm *pFirstTerm = 0;    /* First term matching the index */
  3137   3155   #endif
  3138   3156   
  3139   3157       nOrderBy = p->pOrderBy ? p->pOrderBy->nExpr : 0;
  3140         -    bSort = nOrderBy>0 && (p->i==0 || p->aLevel[p->i-1].plan.nOBSat<nOrderBy);
  3141         -    bDist = p->i==0 && p->pDistinct!=0;
         3158  +    if( p->i ){
         3159  +      nPriorSat = pc.plan.nOBSat = p->aLevel[p->i-1].plan.nOBSat;
         3160  +      bSort = nPriorSat<nOrderBy;
         3161  +      bDist = 0;
         3162  +    }else{
         3163  +      nPriorSat = pc.plan.nOBSat = 0;
         3164  +      bSort = nOrderBy>0;
         3165  +      bDist = p->pDistinct!=0;
         3166  +    }
  3142   3167   
  3143         -    /* Determine the values of nEq and nInMul */
  3144         -    for(nEq=nOrdered=0; nEq<pProbe->nColumn; nEq++){
  3145         -      int j = pProbe->aiColumn[nEq];
         3168  +    /* Determine the values of pc.plan.nEq and nInMul */
         3169  +    for(pc.plan.nEq=nOrdered=0; pc.plan.nEq<pProbe->nColumn; pc.plan.nEq++){
         3170  +      int j = pProbe->aiColumn[pc.plan.nEq];
  3146   3171         pTerm = findTerm(pWC, iCur, j, p->notReady, eqTermMask, pIdx);
  3147   3172         if( pTerm==0 ) break;
  3148         -      wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ);
         3173  +      pc.plan.wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ);
  3149   3174         testcase( pTerm->pWC!=pWC );
  3150   3175         if( pTerm->eOperator & WO_IN ){
  3151   3176           Expr *pExpr = pTerm->pExpr;
  3152         -        wsFlags |= WHERE_COLUMN_IN;
         3177  +        pc.plan.wsFlags |= WHERE_COLUMN_IN;
  3153   3178           if( ExprHasProperty(pExpr, EP_xIsSelect) ){
  3154   3179             /* "x IN (SELECT ...)":  Assume the SELECT returns 25 rows */
  3155   3180             nInMul *= 25;
  3156   3181             bInEst = 1;
  3157   3182           }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){
  3158   3183             /* "x IN (value, value, ...)" */
  3159   3184             nInMul *= pExpr->x.pList->nExpr;
  3160   3185           }
  3161   3186         }else if( pTerm->eOperator & WO_ISNULL ){
  3162         -        wsFlags |= WHERE_COLUMN_NULL;
  3163         -        if( nEq==nOrdered ) nOrdered++;
  3164         -      }else if( bSort && nEq==nOrdered && isOrderedTerm(p, pTerm, &bRev) ){
         3187  +        pc.plan.wsFlags |= WHERE_COLUMN_NULL;
         3188  +        if( pc.plan.nEq==nOrdered ) nOrdered++;
         3189  +      }else if( bSort && pc.plan.nEq==nOrdered && isOrderedTerm(p, pTerm, &bRev) ){
  3165   3190           nOrdered++;
  3166   3191         }
  3167   3192   #ifdef SQLITE_ENABLE_STAT3
  3168         -      if( nEq==0 && pProbe->aSample ) pFirstTerm = pTerm;
         3193  +      if( pc.plan.nEq==0 && pProbe->aSample ) pFirstTerm = pTerm;
  3169   3194   #endif
  3170         -      used |= pTerm->prereqRight;
         3195  +      pc.used |= pTerm->prereqRight;
  3171   3196       }
  3172   3197    
  3173   3198       /* If the index being considered is UNIQUE, and there is an equality 
  3174   3199       ** constraint for all columns in the index, then this search will find
  3175   3200       ** at most a single row. In this case set the WHERE_UNIQUE flag to 
  3176   3201       ** indicate this to the caller.
  3177   3202       **
  3178   3203       ** Otherwise, if the search may find more than one row, test to see if
  3179         -    ** there is a range constraint on indexed column (nEq+1) that can be 
         3204  +    ** there is a range constraint on indexed column (pc.plan.nEq+1) that can be 
  3180   3205       ** optimized using the index. 
  3181   3206       */
  3182         -    if( nEq==pProbe->nColumn && pProbe->onError!=OE_None ){
  3183         -      testcase( wsFlags & WHERE_COLUMN_IN );
  3184         -      testcase( wsFlags & WHERE_COLUMN_NULL );
  3185         -      if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){
  3186         -        wsFlags |= WHERE_UNIQUE;
         3207  +    if( pc.plan.nEq==pProbe->nColumn && pProbe->onError!=OE_None ){
         3208  +      testcase( pc.plan.wsFlags & WHERE_COLUMN_IN );
         3209  +      testcase( pc.plan.wsFlags & WHERE_COLUMN_NULL );
         3210  +      if( (pc.plan.wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){
         3211  +        pc.plan.wsFlags |= WHERE_UNIQUE;
  3187   3212           if( p->i==0 || (p->aLevel[p->i-1].plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){
  3188         -          wsFlags |= WHERE_ALL_UNIQUE;
         3213  +          pc.plan.wsFlags |= WHERE_ALL_UNIQUE;
  3189   3214           }
  3190   3215         }
  3191   3216       }else if( pProbe->bUnordered==0 ){
  3192         -      int j = (nEq==pProbe->nColumn ? -1 : pProbe->aiColumn[nEq]);
         3217  +      int j;
         3218  +      j = (pc.plan.nEq==pProbe->nColumn ? -1 : pProbe->aiColumn[pc.plan.nEq]);
  3193   3219         if( findTerm(pWC, iCur, j, p->notReady, WO_LT|WO_LE|WO_GT|WO_GE, pIdx) ){
  3194   3220           WhereTerm *pTop, *pBtm;
  3195   3221           pTop = findTerm(pWC, iCur, j, p->notReady, WO_LT|WO_LE, pIdx);
  3196   3222           pBtm = findTerm(pWC, iCur, j, p->notReady, WO_GT|WO_GE, pIdx);
  3197         -        whereRangeScanEst(pParse, pProbe, nEq, pBtm, pTop, &rangeDiv);
         3223  +        whereRangeScanEst(pParse, pProbe, pc.plan.nEq, pBtm, pTop, &rangeDiv);
  3198   3224           if( pTop ){
  3199   3225             nBound = 1;
  3200         -          wsFlags |= WHERE_TOP_LIMIT;
  3201         -          used |= pTop->prereqRight;
         3226  +          pc.plan.wsFlags |= WHERE_TOP_LIMIT;
         3227  +          pc.used |= pTop->prereqRight;
  3202   3228             testcase( pTop->pWC!=pWC );
  3203   3229           }
  3204   3230           if( pBtm ){
  3205   3231             nBound++;
  3206         -          wsFlags |= WHERE_BTM_LIMIT;
  3207         -          used |= pBtm->prereqRight;
         3232  +          pc.plan.wsFlags |= WHERE_BTM_LIMIT;
         3233  +          pc.used |= pBtm->prereqRight;
  3208   3234             testcase( pBtm->pWC!=pWC );
  3209   3235           }
  3210         -        wsFlags |= (WHERE_COLUMN_RANGE|WHERE_ROWID_RANGE);
         3236  +        pc.plan.wsFlags |= (WHERE_COLUMN_RANGE|WHERE_ROWID_RANGE);
  3211   3237         }
  3212   3238       }
  3213   3239   
  3214   3240       /* If there is an ORDER BY clause and the index being considered will
  3215   3241       ** naturally scan rows in the required order, set the appropriate flags
  3216         -    ** in wsFlags. Otherwise, if there is an ORDER BY clause but the index
  3217         -    ** will scan rows in a different order, set the bSort variable.  */
         3242  +    ** in pc.plan.wsFlags. Otherwise, if there is an ORDER BY clause but
         3243  +    ** the index will scan rows in a different order, set the bSort
         3244  +    ** variable.  */
  3218   3245       assert( bRev>=0 && bRev<=2 );
  3219   3246       if( bSort ){
  3220   3247         testcase( bRev==0 );
  3221   3248         testcase( bRev==1 );
  3222   3249         testcase( bRev==2 );
  3223         -      nOBSat = isSortingIndex(p, pProbe, iCur, nOrdered,
  3224         -                              wsFlags, bRev&1, &bRev);
  3225         -      if( nOrderBy==nOBSat ){
         3250  +      pc.plan.nOBSat = isSortingIndex(p, pProbe, iCur, nOrdered,
         3251  +                                 pc.plan.wsFlags, bRev&1, &bRev);
         3252  +      if( nPriorSat<pc.plan.nOBSat || (pc.plan.wsFlags & WHERE_UNIQUE)!=0 ){
         3253  +        pc.plan.wsFlags |= WHERE_ORDERED;
         3254  +      }
         3255  +      if( nOrderBy==pc.plan.nOBSat ){
  3226   3256           bSort = 0;
  3227         -        wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE|WHERE_ORDERBY;
         3257  +        pc.plan.wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE;
  3228   3258         }
  3229         -      if( bRev & 1 ) wsFlags |= WHERE_REVERSE;
         3259  +      if( bRev & 1 ) pc.plan.wsFlags |= WHERE_REVERSE;
  3230   3260       }
  3231   3261   
  3232   3262       /* If there is a DISTINCT qualifier and this index will scan rows in
  3233   3263       ** order of the DISTINCT expressions, clear bDist and set the appropriate
  3234         -    ** flags in wsFlags. */
         3264  +    ** flags in pc.plan.wsFlags. */
  3235   3265       if( bDist
  3236         -     && isDistinctIndex(pParse, pWC, pProbe, iCur, p->pDistinct, nEq)
  3237         -     && (wsFlags & WHERE_COLUMN_IN)==0
         3266  +     && isDistinctIndex(pParse, pWC, pProbe, iCur, p->pDistinct, pc.plan.nEq)
         3267  +     && (pc.plan.wsFlags & WHERE_COLUMN_IN)==0
  3238   3268       ){
  3239   3269         bDist = 0;
  3240         -      wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE|WHERE_DISTINCT;
         3270  +      pc.plan.wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE|WHERE_DISTINCT;
  3241   3271       }
  3242   3272   
  3243   3273       /* If currently calculating the cost of using an index (not the IPK
  3244   3274       ** index), determine if all required column data may be obtained without 
  3245   3275       ** using the main table (i.e. if the index is a covering
  3246   3276       ** index for this query). If it is, set the WHERE_IDX_ONLY flag in
  3247         -    ** wsFlags. Otherwise, set the bLookup variable to true.  */
         3277  +    ** pc.plan.wsFlags. Otherwise, set the bLookup variable to true.  */
  3248   3278       if( pIdx ){
  3249   3279         Bitmask m = pSrc->colUsed;
  3250   3280         int j;
  3251   3281         for(j=0; j<pIdx->nColumn; j++){
  3252   3282           int x = pIdx->aiColumn[j];
  3253   3283           if( x<BMS-1 ){
  3254   3284             m &= ~(((Bitmask)1)<<x);
  3255   3285           }
  3256   3286         }
  3257   3287         if( m==0 ){
  3258         -        wsFlags |= WHERE_IDX_ONLY;
         3288  +        pc.plan.wsFlags |= WHERE_IDX_ONLY;
  3259   3289         }else{
  3260   3290           bLookup = 1;
  3261   3291         }
  3262   3292       }
  3263   3293   
  3264   3294       /*
  3265   3295       ** Estimate the number of rows of output.  For an "x IN (SELECT...)"
  3266   3296       ** constraint, do not let the estimate exceed half the rows in the table.
  3267   3297       */
  3268         -    nRow = (double)(aiRowEst[nEq] * nInMul);
  3269         -    if( bInEst && nRow*2>aiRowEst[0] ){
  3270         -      nRow = aiRowEst[0]/2;
  3271         -      nInMul = (int)(nRow / aiRowEst[nEq]);
         3298  +    pc.plan.nRow = (double)(aiRowEst[pc.plan.nEq] * nInMul);
         3299  +    if( bInEst && pc.plan.nRow*2>aiRowEst[0] ){
         3300  +      pc.plan.nRow = aiRowEst[0]/2;
         3301  +      nInMul = (int)(pc.plan.nRow / aiRowEst[pc.plan.nEq]);
  3272   3302       }
  3273   3303   
  3274   3304   #ifdef SQLITE_ENABLE_STAT3
  3275   3305       /* If the constraint is of the form x=VALUE or x IN (E1,E2,...)
  3276   3306       ** and we do not think that values of x are unique and if histogram
  3277   3307       ** data is available for column x, then it might be possible
  3278   3308       ** to get a better estimate on the number of rows based on
  3279   3309       ** VALUE and how common that value is according to the histogram.
  3280   3310       */
  3281         -    if( nRow>(double)1 && nEq==1 && pFirstTerm!=0 && aiRowEst[1]>1 ){
         3311  +    if( pc.plan.nRow>(double)1 && pc.plan.nEq==1
         3312  +     && pFirstTerm!=0 && aiRowEst[1]>1 ){
  3282   3313         assert( (pFirstTerm->eOperator & (WO_EQ|WO_ISNULL|WO_IN))!=0 );
  3283   3314         if( pFirstTerm->eOperator & (WO_EQ|WO_ISNULL) ){
  3284   3315           testcase( pFirstTerm->eOperator==WO_EQ );
  3285   3316           testcase( pFirstTerm->eOperator==WO_ISNULL );
  3286         -        whereEqualScanEst(pParse, pProbe, pFirstTerm->pExpr->pRight, &nRow);
         3317  +        whereEqualScanEst(pParse, pProbe, pFirstTerm->pExpr->pRight,
         3318  +                          &pc.plan.nRow);
  3287   3319         }else if( bInEst==0 ){
  3288   3320           assert( pFirstTerm->eOperator==WO_IN );
  3289         -        whereInScanEst(pParse, pProbe, pFirstTerm->pExpr->x.pList, &nRow);
         3321  +        whereInScanEst(pParse, pProbe, pFirstTerm->pExpr->x.pList,
         3322  +                       &pc.plan.nRow);
  3290   3323         }
  3291   3324       }
  3292   3325   #endif /* SQLITE_ENABLE_STAT3 */
  3293   3326   
  3294   3327       /* Adjust the number of output rows and downward to reflect rows
  3295   3328       ** that are excluded by range constraints.
  3296   3329       */
  3297         -    nRow = nRow/rangeDiv;
  3298         -    if( nRow<1 ) nRow = 1;
         3330  +    pc.plan.nRow = pc.plan.nRow/rangeDiv;
         3331  +    if( pc.plan.nRow<1 ) pc.plan.nRow = 1;
  3299   3332   
  3300   3333       /* Experiments run on real SQLite databases show that the time needed
  3301   3334       ** to do a binary search to locate a row in a table or index is roughly
  3302   3335       ** log10(N) times the time to move from one row to the next row within
  3303   3336       ** a table or index.  The actual times can vary, with the size of
  3304   3337       ** records being an important factor.  Both moves and searches are
  3305   3338       ** slower with larger records, presumably because fewer records fit
................................................................................
  3306   3339       ** on one page and hence more pages have to be fetched.
  3307   3340       **
  3308   3341       ** The ANALYZE command and the sqlite_stat1 and sqlite_stat3 tables do
  3309   3342       ** not give us data on the relative sizes of table and index records.
  3310   3343       ** So this computation assumes table records are about twice as big
  3311   3344       ** as index records
  3312   3345       */
  3313         -    if( (wsFlags&~WHERE_REVERSE)==WHERE_IDX_ONLY
         3346  +    if( (pc.plan.wsFlags&~(WHERE_REVERSE|WHERE_ORDERED))==WHERE_IDX_ONLY
  3314   3347        && (pWC->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
  3315   3348        && sqlite3GlobalConfig.bUseCis
  3316   3349        && OptimizationEnabled(pParse->db, SQLITE_CoverIdxScan)
  3317   3350       ){
  3318   3351         /* This index is not useful for indexing, but it is a covering index.
  3319   3352         ** A full-scan of the index might be a little faster than a full-scan
  3320   3353         ** of the table, so give this case a cost slightly less than a table
  3321   3354         ** scan. */
  3322         -      cost = aiRowEst[0]*3 + pProbe->nColumn;
  3323         -      wsFlags |= WHERE_COVER_SCAN|WHERE_COLUMN_RANGE;
  3324         -    }else if( (wsFlags & WHERE_NOT_FULLSCAN)==0 ){
         3355  +      pc.rCost = aiRowEst[0]*3 + pProbe->nColumn;
         3356  +      pc.plan.wsFlags |= WHERE_COVER_SCAN|WHERE_COLUMN_RANGE;
         3357  +    }else if( (pc.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ){
  3325   3358         /* The cost of a full table scan is a number of move operations equal
  3326   3359         ** to the number of rows in the table.
  3327   3360         **
  3328   3361         ** We add an additional 4x penalty to full table scans.  This causes
  3329   3362         ** the cost function to err on the side of choosing an index over
  3330   3363         ** choosing a full scan.  This 4x full-scan penalty is an arguable
  3331   3364         ** decision and one which we expect to revisit in the future.  But
  3332   3365         ** it seems to be working well enough at the moment.
  3333   3366         */
  3334         -      cost = aiRowEst[0]*4;
  3335         -      wsFlags &= ~WHERE_IDX_ONLY;
         3367  +      pc.rCost = aiRowEst[0]*4;
         3368  +      pc.plan.wsFlags &= ~WHERE_IDX_ONLY;
         3369  +      if( pIdx ) pc.plan.wsFlags &= ~WHERE_ORDERED;
  3336   3370       }else{
  3337   3371         log10N = estLog(aiRowEst[0]);
  3338         -      cost = nRow;
         3372  +      pc.rCost = pc.plan.nRow;
  3339   3373         if( pIdx ){
  3340   3374           if( bLookup ){
  3341   3375             /* For an index lookup followed by a table lookup:
  3342   3376             **    nInMul index searches to find the start of each index range
  3343   3377             **  + nRow steps through the index
  3344   3378             **  + nRow table searches to lookup the table entry using the rowid
  3345   3379             */
  3346         -          cost += (nInMul + nRow)*log10N;
         3380  +          pc.rCost += (nInMul + pc.plan.nRow)*log10N;
  3347   3381           }else{
  3348   3382             /* For a covering index:
  3349   3383             **     nInMul index searches to find the initial entry 
  3350   3384             **   + nRow steps through the index
  3351   3385             */
  3352         -          cost += nInMul*log10N;
         3386  +          pc.rCost += nInMul*log10N;
  3353   3387           }
  3354   3388         }else{
  3355   3389           /* For a rowid primary key lookup:
  3356   3390           **    nInMult table searches to find the initial entry for each range
  3357   3391           **  + nRow steps through the table
  3358   3392           */
  3359         -        cost += nInMul*log10N;
         3393  +        pc.rCost += nInMul*log10N;
  3360   3394         }
  3361   3395       }
  3362   3396   
  3363   3397       /* Add in the estimated cost of sorting the result.  Actual experimental
  3364   3398       ** measurements of sorting performance in SQLite show that sorting time
  3365   3399       ** adds C*N*log10(N) to the cost, where N is the number of rows to be 
  3366   3400       ** sorted and C is a factor between 1.95 and 4.3.  We will split the
  3367   3401       ** difference and select C of 3.0.
  3368   3402       */
  3369   3403       if( bSort ){
  3370         -      cost += nRow*estLog(nRow*(nOrderBy - nOBSat)/nOrderBy)*3;
         3404  +      double m = estLog(pc.plan.nRow*(nOrderBy - pc.plan.nOBSat)/nOrderBy);
         3405  +      m *= (double)(pc.plan.nOBSat ? 2 : 3);
         3406  +      pc.rCost += pc.plan.nRow*m;
  3371   3407       }
  3372   3408       if( bDist ){
  3373         -      cost += nRow*estLog(nRow)*3;
         3409  +      pc.rCost += pc.plan.nRow*estLog(pc.plan.nRow)*3;
  3374   3410       }
  3375   3411   
  3376   3412       /**** Cost of using this index has now been computed ****/
  3377   3413   
  3378   3414       /* If there are additional constraints on this table that cannot
  3379   3415       ** be used with the current index, but which might lower the number
  3380   3416       ** of output rows, adjust the nRow value accordingly.  This only 
................................................................................
  3387   3423       ** mask will only have one bit set - the bit for the current table.
  3388   3424       ** The notValid mask, on the other hand, always has all bits set for
  3389   3425       ** tables that are not in outer loops.  If notReady is used here instead
  3390   3426       ** of notValid, then a optimal index that depends on inner joins loops
  3391   3427       ** might be selected even when there exists an optimal index that has
  3392   3428       ** no such dependency.
  3393   3429       */
  3394         -    if( nRow>2 && cost<=p->cost.rCost ){
         3430  +    if( pc.plan.nRow>2 && pc.rCost<=p->cost.rCost ){
  3395   3431         int k;                       /* Loop counter */
  3396         -      int nSkipEq = nEq;           /* Number of == constraints to skip */
         3432  +      int nSkipEq = pc.plan.nEq;   /* Number of == constraints to skip */
  3397   3433         int nSkipRange = nBound;     /* Number of < constraints to skip */
  3398   3434         Bitmask thisTab;             /* Bitmap for pSrc */
  3399   3435   
  3400   3436         thisTab = getMask(pWC->pMaskSet, iCur);
  3401         -      for(pTerm=pWC->a, k=pWC->nTerm; nRow>2 && k; k--, pTerm++){
         3437  +      for(pTerm=pWC->a, k=pWC->nTerm; pc.plan.nRow>2 && k; k--, pTerm++){
  3402   3438           if( pTerm->wtFlags & TERM_VIRTUAL ) continue;
  3403   3439           if( (pTerm->prereqAll & p->notValid)!=thisTab ) continue;
  3404   3440           if( pTerm->eOperator & (WO_EQ|WO_IN|WO_ISNULL) ){
  3405   3441             if( nSkipEq ){
  3406         -            /* Ignore the first nEq equality matches since the index
         3442  +            /* Ignore the first pc.plan.nEq equality matches since the index
  3407   3443               ** has already accounted for these */
  3408   3444               nSkipEq--;
  3409   3445             }else{
  3410   3446               /* Assume each additional equality match reduces the result
  3411   3447               ** set size by a factor of 10 */
  3412         -            nRow /= 10;
         3448  +            pc.plan.nRow /= 10;
  3413   3449             }
  3414   3450           }else if( pTerm->eOperator & (WO_LT|WO_LE|WO_GT|WO_GE) ){
  3415   3451             if( nSkipRange ){
  3416   3452               /* Ignore the first nSkipRange range constraints since the index
  3417   3453               ** has already accounted for these */
  3418   3454               nSkipRange--;
  3419   3455             }else{
  3420   3456               /* Assume each additional range constraint reduces the result
  3421   3457               ** set size by a factor of 3.  Indexed range constraints reduce
  3422   3458               ** the search space by a larger factor: 4.  We make indexed range
  3423   3459               ** more selective intentionally because of the subjective 
  3424   3460               ** observation that indexed range constraints really are more
  3425   3461               ** selective in practice, on average. */
  3426         -            nRow /= 3;
         3462  +            pc.plan.nRow /= 3;
  3427   3463             }
  3428   3464           }else if( pTerm->eOperator!=WO_NOOP ){
  3429   3465             /* Any other expression lowers the output row count by half */
  3430         -          nRow /= 2;
         3466  +          pc.plan.nRow /= 2;
  3431   3467           }
  3432   3468         }
  3433         -      if( nRow<2 ) nRow = 2;
         3469  +      if( pc.plan.nRow<2 ) pc.plan.nRow = 2;
  3434   3470       }
  3435   3471   
  3436   3472   
  3437   3473       WHERETRACE((
  3438   3474         "%s(%s):\n"
  3439   3475         "    nEq=%d nInMul=%d rangeDiv=%d bSort=%d bLookup=%d wsFlags=0x%08x\n"
  3440   3476         "    notReady=0x%llx log10N=%.1f nRow=%.1f cost=%.1f\n"
  3441   3477         "    used=0x%llx nOrdered=%d nOBSat=%d\n",
  3442   3478         pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk"), 
  3443         -      nEq, nInMul, (int)rangeDiv, bSort, bLookup, wsFlags,
  3444         -      p->notReady, log10N, nRow, cost, used, nOrdered, nOBSat
         3479  +      pc.plan.nEq, nInMul, (int)rangeDiv, bSort, bLookup, pc.plan.wsFlags,
         3480  +      p->notReady, log10N, pc.plan.nRow, pc.rCost, pc.used, nOrdered,
         3481  +      pc.plan.nOBSat
  3445   3482       ));
  3446   3483   
  3447   3484       /* If this index is the best we have seen so far, then record this
  3448         -    ** index and its cost in the pCost structure.
         3485  +    ** index and its cost in the p->cost structure.
  3449   3486       */
  3450         -    if( (!pIdx || wsFlags)
  3451         -     && (cost<p->cost.rCost || (cost<=p->cost.rCost && nRow<p->cost.plan.nRow))
  3452         -    ){
  3453         -      p->cost.rCost = cost;
  3454         -      p->cost.used = used;
  3455         -      p->cost.plan.nRow = nRow;
  3456         -      p->cost.plan.wsFlags = (wsFlags&wsFlagMask);
  3457         -      p->cost.plan.nEq = nEq;
  3458         -      p->cost.plan.nOBSat = nOBSat;
         3487  +    if( (!pIdx || pc.plan.wsFlags) && compareCost(&pc, &p->cost) ){
         3488  +      p->cost = pc;
         3489  +      p->cost.plan.wsFlags &= wsFlagMask;
  3459   3490         p->cost.plan.u.pIdx = pIdx;
  3460   3491       }
  3461   3492   
  3462   3493       /* If there was an INDEXED BY clause, then only that one index is
  3463   3494       ** considered. */
  3464   3495       if( pSrc->pIndex ) break;
  3465   3496   
................................................................................
  3473   3504     ** in. This is used for application testing, to help find cases
  3474   3505     ** where application behaviour depends on the (undefined) order that
  3475   3506     ** SQLite outputs rows in in the absence of an ORDER BY clause.  */
  3476   3507     if( !p->pOrderBy && pParse->db->flags & SQLITE_ReverseOrder ){
  3477   3508       p->cost.plan.wsFlags |= WHERE_REVERSE;
  3478   3509     }
  3479   3510   
  3480         -  assert( p->pOrderBy || (p->cost.plan.wsFlags&WHERE_ORDERBY)==0 );
         3511  +  assert( p->pOrderBy || (p->cost.plan.wsFlags&WHERE_ORDERED)==0 );
  3481   3512     assert( p->cost.plan.u.pIdx==0 || (p->cost.plan.wsFlags&WHERE_ROWID_EQ)==0 );
  3482   3513     assert( pSrc->pIndex==0 
  3483   3514          || p->cost.plan.u.pIdx==0 
  3484   3515          || p->cost.plan.u.pIdx==pSrc->pIndex 
  3485   3516     );
  3486   3517   
  3487         -  WHERETRACE(("best index is: %s\n", 
  3488         -    ((p->cost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ? "none" : 
  3489         -         p->cost.plan.u.pIdx ? p->cost.plan.u.pIdx->zName : "ipk")
  3490         -  ));
         3518  +  WHERETRACE(("best index is: %s\n",
         3519  +         p->cost.plan.u.pIdx ? p->cost.plan.u.pIdx->zName : "ipk"));
  3491   3520     
  3492   3521     bestOrClauseIndex(p);
  3493   3522     bestAutomaticIndex(p);
  3494   3523     p->cost.plan.wsFlags |= eqTermMask;
  3495   3524   }
  3496   3525   
  3497   3526   /*
................................................................................
  4211   4240       ** query, then the caller will only allow the loop to run for
  4212   4241       ** a single iteration. This means that the first row returned
  4213   4242       ** should not have a NULL value stored in 'x'. If column 'x' is
  4214   4243       ** the first one after the nEq equality constraints in the index,
  4215   4244       ** this requires some special handling.
  4216   4245       */
  4217   4246       if( (wctrlFlags&WHERE_ORDERBY_MIN)!=0
  4218         -     && (pLevel->plan.wsFlags&WHERE_ORDERBY)
         4247  +     && (pLevel->plan.wsFlags&WHERE_ORDERED)
  4219   4248        && (pIdx->nColumn>nEq)
  4220   4249       ){
  4221   4250         /* assert( pOrderBy->nExpr==1 ); */
  4222   4251         /* assert( pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq] ); */
  4223   4252         isMinQuery = 1;
  4224   4253         nExtraReg = 1;
  4225   4254       }
................................................................................
  5074   5103           **       index specified by its INDEXED BY clause.  This rule ensures
  5075   5104           **       that a best-so-far is always selected even if an impossible
  5076   5105           **       combination of INDEXED BY clauses are given.  The error
  5077   5106           **       will be detected and relayed back to the application later.
  5078   5107           **       The NEVER() comes about because rule (2) above prevents
  5079   5108           **       An indexable full-table-scan from reaching rule (3).
  5080   5109           **
  5081         -        **   (4) The plan cost must be lower than prior plans or else the
  5082         -        **       cost must be the same and the number of rows must be lower.
         5110  +        **   (4) The plan cost must be lower than prior plans, where "cost"
         5111  +        **       is defined by the compareCost() function above. 
  5083   5112           */
  5084   5113           if( (sWBI.cost.used&sWBI.notValid)==0                    /* (1) */
  5085   5114               && (bestJ<0 || (notIndexed&m)!=0                     /* (2) */
  5086   5115                   || (bestPlan.plan.wsFlags & WHERE_NOT_FULLSCAN)==0
  5087   5116                   || (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0)
  5088   5117               && (nUnconstrained==0 || sWBI.pSrc->pIndex==0        /* (3) */
  5089   5118                   || NEVER((sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0))
  5090         -            && (bestJ<0 || sWBI.cost.rCost<bestPlan.rCost        /* (4) */
  5091         -                || (sWBI.cost.rCost<=bestPlan.rCost 
  5092         -                 && sWBI.cost.plan.nRow<bestPlan.plan.nRow))
         5119  +            && (bestJ<0 || compareCost(&sWBI.cost, &bestPlan))   /* (4) */
  5093   5120           ){
  5094         -          WHERETRACE(("=== table %d (%s) is best so far"
  5095         -                      " with cost=%.1f, nRow=%.1f, nOBSat=%d\n",
         5121  +          WHERETRACE(("=== table %d (%s) is best so far\n"
         5122  +                      "    cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=%08x\n",
  5096   5123                         j, sWBI.pSrc->pTab->zName,
  5097   5124                         sWBI.cost.rCost, sWBI.cost.plan.nRow,
  5098         -                      sWBI.cost.plan.nOBSat));
         5125  +                      sWBI.cost.plan.nOBSat, sWBI.cost.plan.wsFlags));
  5099   5126             bestPlan = sWBI.cost;
  5100   5127             bestJ = j;
  5101   5128           }
  5102   5129           if( doNotReorder ) break;
  5103   5130         }
  5104   5131       }
  5105   5132       assert( bestJ>=0 );
  5106   5133       assert( sWBI.notValid & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );
  5107   5134       WHERETRACE(("*** Optimizer selects table %d (%s) for loop %d with:\n"
  5108         -                "    cost=%.1f, nRow=%.1f, nOBSat=%d wsFlags=0x%08x\n",
         5135  +                "    cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=0x%08x\n",
  5109   5136                   bestJ, pTabList->a[bestJ].pTab->zName,
  5110   5137                   pLevel-pWInfo->a, bestPlan.rCost, bestPlan.plan.nRow,
  5111   5138                   bestPlan.plan.nOBSat, bestPlan.plan.wsFlags));
  5112         -    if( (bestPlan.plan.wsFlags & WHERE_ORDERBY)!=0 ){
  5113         -      pWInfo->nOBSat = pOrderBy->nExpr;
  5114         -    }
  5115   5139       if( (bestPlan.plan.wsFlags & WHERE_DISTINCT)!=0 ){
  5116   5140         assert( pWInfo->eDistinct==0 );
  5117   5141         pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
  5118   5142       }
  5119   5143       andFlags &= bestPlan.plan.wsFlags;
  5120   5144       pLevel->plan = bestPlan.plan;
  5121   5145       pLevel->iTabCur = pTabList->a[bestJ].iCursor;
................................................................................
  5156   5180         }
  5157   5181       }
  5158   5182     }
  5159   5183     WHERETRACE(("*** Optimizer Finished ***\n"));
  5160   5184     if( pParse->nErr || db->mallocFailed ){
  5161   5185       goto whereBeginError;
  5162   5186     }
         5187  +  if( nTabList ){
         5188  +    pLevel--;
         5189  +    pWInfo->nOBSat = pLevel->plan.nOBSat;
         5190  +  }else{
         5191  +    pWInfo->nOBSat = 0;
         5192  +  }
  5163   5193   
  5164   5194     /* If the total query only selects a single row, then the ORDER BY
  5165   5195     ** clause is irrelevant.
  5166   5196     */
  5167   5197     if( (andFlags & WHERE_UNIQUE)!=0 && pOrderBy ){
         5198  +    assert( nTabList==0 || (pLevel->plan.wsFlags & WHERE_ALL_UNIQUE)!=0 );
  5168   5199       pWInfo->nOBSat = pOrderBy->nExpr;
  5169   5200     }
  5170   5201   
  5171   5202     /* If the caller is an UPDATE or DELETE statement that is requesting
  5172   5203     ** to use a one-pass algorithm, determine if this is appropriate.
  5173   5204     ** The one-pass algorithm only works if the WHERE clause constraints
  5174   5205     ** the statement to update a single row.

Changes to test/fuzzer1.test.

  1860   1860     INSERT INTO x5_rules VALUES(0, 'a', '0.1.2.3.4.5.6.7.8.9.a', 1);
  1861   1861     DROP TABLE x5;
  1862   1862     CREATE VIRTUAL TABLE x5 USING fuzzer(x5_rules);
  1863   1863     SELECT length(word) FROM x5 WHERE word MATCH 'a' LIMIT 50;
  1864   1864   } {1 21 41 61 81}
  1865   1865   
  1866   1866   finish_test
  1867         -
  1868         -

Changes to test/orderby2.test.

    63     63   do_test 1.3b {
    64     64     db eval {
    65     65       EXPLAIN QUERY PLAN
    66     66       SELECT e, b FROM t1, t2 WHERE a=1 ORDER BY d, e;
    67     67     }
    68     68   } {~/ORDER BY/}
    69     69   
    70         -# After where34.314 in TH3:
           70  +# The following tests derived from TH3 test module cov1/where34.test
           71  +#
    71     72   do_test 2.0 {
    72     73     db eval {
    73     74       CREATE TABLE t31(a,b); CREATE INDEX t31ab ON t31(a,b);
    74     75       CREATE TABLE t32(c,d); CREATE INDEX t32cd ON t32(c,d);
    75     76       CREATE TABLE t33(e,f); CREATE INDEX t33ef ON t33(e,f);
    76     77       CREATE TABLE t34(g,h); CREATE INDEX t34gh ON t34(g,h);
    77     78       
................................................................................
    88     89   do_test 2.1 {
    89     90     db eval {
    90     91       SELECT a||','||c||','||e||','||g FROM t31, t32, t33, t34
    91     92        WHERE c=b AND e=d AND g=f
    92     93        ORDER BY +a ASC, +c ASC, +e DESC, +g ASC;
    93     94     }
    94     95   } {1,3,7,10 1,3,7,14 1,3,6,11 1,4,8,12 1,4,8,12 1,4,8,13 1,4,5,9 2,3,7,10 2,3,7,14 2,3,6,11}
    95         -    
           96  +do_test 2.2 {
           97  +  db eval {
           98  +    SELECT a||','||c||','||e||','||g FROM t31, t32, t33, t34
           99  +     WHERE c=b AND e=d AND g=f
          100  +     ORDER BY a ASC, c ASC, e ASC, g ASC;
          101  +  }
          102  +} {1,3,6,11 1,3,7,10 1,3,7,14 1,4,5,9 1,4,8,12 1,4,8,12 1,4,8,13 2,3,6,11 2,3,7,10 2,3,7,14}
          103  +do_test 2.3 {
          104  +  optimization_control db cover-idx-scan off
          105  +  db cache flush
          106  +  db eval {
          107  +    SELECT a||','||c||','||e||','||g FROM t31, t32, t33, t34
          108  +     WHERE c=b AND e=d AND g=f
          109  +     ORDER BY a ASC, c ASC, e ASC, g ASC;
          110  +  }
          111  +} {1,3,6,11 1,3,7,10 1,3,7,14 1,4,5,9 1,4,8,12 1,4,8,12 1,4,8,13 2,3,6,11 2,3,7,10 2,3,7,14}  
          112  +optimization_control db all on
          113  +db cache flush
          114  +
          115  +
    96    116   
    97    117   finish_test

Changes to test/where.test.

  1084   1084       CREATE TABLE t8(a INTEGER PRIMARY KEY, b TEXT UNIQUE);
  1085   1085       INSERT INTO t8 VALUES(1,'one');
  1086   1086       INSERT INTO t8 VALUES(4,'four');
  1087   1087     }
  1088   1088     cksort {
  1089   1089       SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.a, y.b
  1090   1090     } 
  1091         -} {1/4 1/1 4/4 4/1 sort}
         1091  +} {1/4 1/1 4/4 4/1 nosort}
  1092   1092   do_test where-14.2 {
  1093   1093     cksort {
  1094   1094       SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.a, y.b DESC
  1095   1095     } 
  1096         -} {1/1 1/4 4/1 4/4 sort}
         1096  +} {1/1 1/4 4/1 4/4 nosort}
  1097   1097   do_test where-14.3 {
  1098   1098     cksort {
  1099   1099       SELECT x.a || '/' || y.a FROM t8 x, t8 y ORDER BY x.a, x.b
  1100   1100     } 
  1101   1101   } {1/4 1/1 4/4 4/1 nosort}
  1102   1102   do_test where-14.4 {
  1103   1103     cksort {