/ Check-in [6744d9a3]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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

Overview
Comment:Further attempts to optimize out unnecessary ORDER BY clauses.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | qp-enhancements
Files: files | file ages | folders
SHA1: 6744d9a37faffed59b4d5cb96c8671ec46a87ea7
User & Date: drh 2012-10-03 00:25:54
Context
2012-10-03
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
00:25
Further attempts to optimize out unnecessary ORDER BY clauses. check-in: 6744d9a3 user: drh tags: qp-enhancements
2012-10-02
22:54
Work around an optimization issue with the MSVC compiler for ARM. check-in: 7d301fdf user: mistachkin tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

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;
  3336   3369       }else{
  3337   3370         log10N = estLog(aiRowEst[0]);
  3338         -      cost = nRow;
         3371  +      pc.rCost = pc.plan.nRow;
  3339   3372         if( pIdx ){
  3340   3373           if( bLookup ){
  3341   3374             /* For an index lookup followed by a table lookup:
  3342   3375             **    nInMul index searches to find the start of each index range
  3343   3376             **  + nRow steps through the index
  3344   3377             **  + nRow table searches to lookup the table entry using the rowid
  3345   3378             */
  3346         -          cost += (nInMul + nRow)*log10N;
         3379  +          pc.rCost += (nInMul + pc.plan.nRow)*log10N;
  3347   3380           }else{
  3348   3381             /* For a covering index:
  3349   3382             **     nInMul index searches to find the initial entry 
  3350   3383             **   + nRow steps through the index
  3351   3384             */
  3352         -          cost += nInMul*log10N;
         3385  +          pc.rCost += nInMul*log10N;
  3353   3386           }
  3354   3387         }else{
  3355   3388           /* For a rowid primary key lookup:
  3356   3389           **    nInMult table searches to find the initial entry for each range
  3357   3390           **  + nRow steps through the table
  3358   3391           */
  3359         -        cost += nInMul*log10N;
         3392  +        pc.rCost += nInMul*log10N;
  3360   3393         }
  3361   3394       }
  3362   3395   
  3363   3396       /* Add in the estimated cost of sorting the result.  Actual experimental
  3364   3397       ** measurements of sorting performance in SQLite show that sorting time
  3365   3398       ** adds C*N*log10(N) to the cost, where N is the number of rows to be 
  3366   3399       ** sorted and C is a factor between 1.95 and 4.3.  We will split the
  3367   3400       ** difference and select C of 3.0.
  3368   3401       */
  3369   3402       if( bSort ){
  3370         -      cost += nRow*estLog(nRow*(nOrderBy - nOBSat)/nOrderBy)*3;
         3403  +      double m = estLog(pc.plan.nRow*(nOrderBy - pc.plan.nOBSat)/nOrderBy);
         3404  +      m *= (double)(pc.plan.nOBSat ? 2 : 3);
         3405  +      pc.rCost += pc.plan.nRow*m;
  3371   3406       }
  3372   3407       if( bDist ){
  3373         -      cost += nRow*estLog(nRow)*3;
         3408  +      pc.rCost += pc.plan.nRow*estLog(pc.plan.nRow)*3;
  3374   3409       }
  3375   3410   
  3376   3411       /**** Cost of using this index has now been computed ****/
  3377   3412   
  3378   3413       /* If there are additional constraints on this table that cannot
  3379   3414       ** be used with the current index, but which might lower the number
  3380   3415       ** of output rows, adjust the nRow value accordingly.  This only 
................................................................................
  3387   3422       ** mask will only have one bit set - the bit for the current table.
  3388   3423       ** The notValid mask, on the other hand, always has all bits set for
  3389   3424       ** tables that are not in outer loops.  If notReady is used here instead
  3390   3425       ** of notValid, then a optimal index that depends on inner joins loops
  3391   3426       ** might be selected even when there exists an optimal index that has
  3392   3427       ** no such dependency.
  3393   3428       */
  3394         -    if( nRow>2 && cost<=p->cost.rCost ){
         3429  +    if( pc.plan.nRow>2 && pc.rCost<=p->cost.rCost ){
  3395   3430         int k;                       /* Loop counter */
  3396         -      int nSkipEq = nEq;           /* Number of == constraints to skip */
         3431  +      int nSkipEq = pc.plan.nEq;   /* Number of == constraints to skip */
  3397   3432         int nSkipRange = nBound;     /* Number of < constraints to skip */
  3398   3433         Bitmask thisTab;             /* Bitmap for pSrc */
  3399   3434   
  3400   3435         thisTab = getMask(pWC->pMaskSet, iCur);
  3401         -      for(pTerm=pWC->a, k=pWC->nTerm; nRow>2 && k; k--, pTerm++){
         3436  +      for(pTerm=pWC->a, k=pWC->nTerm; pc.plan.nRow>2 && k; k--, pTerm++){
  3402   3437           if( pTerm->wtFlags & TERM_VIRTUAL ) continue;
  3403   3438           if( (pTerm->prereqAll & p->notValid)!=thisTab ) continue;
  3404   3439           if( pTerm->eOperator & (WO_EQ|WO_IN|WO_ISNULL) ){
  3405   3440             if( nSkipEq ){
  3406         -            /* Ignore the first nEq equality matches since the index
         3441  +            /* Ignore the first pc.plan.nEq equality matches since the index
  3407   3442               ** has already accounted for these */
  3408   3443               nSkipEq--;
  3409   3444             }else{
  3410   3445               /* Assume each additional equality match reduces the result
  3411   3446               ** set size by a factor of 10 */
  3412         -            nRow /= 10;
         3447  +            pc.plan.nRow /= 10;
  3413   3448             }
  3414   3449           }else if( pTerm->eOperator & (WO_LT|WO_LE|WO_GT|WO_GE) ){
  3415   3450             if( nSkipRange ){
  3416   3451               /* Ignore the first nSkipRange range constraints since the index
  3417   3452               ** has already accounted for these */
  3418   3453               nSkipRange--;
  3419   3454             }else{
  3420   3455               /* Assume each additional range constraint reduces the result
  3421   3456               ** set size by a factor of 3.  Indexed range constraints reduce
  3422   3457               ** the search space by a larger factor: 4.  We make indexed range
  3423   3458               ** more selective intentionally because of the subjective 
  3424   3459               ** observation that indexed range constraints really are more
  3425   3460               ** selective in practice, on average. */
  3426         -            nRow /= 3;
         3461  +            pc.plan.nRow /= 3;
  3427   3462             }
  3428   3463           }else if( pTerm->eOperator!=WO_NOOP ){
  3429   3464             /* Any other expression lowers the output row count by half */
  3430         -          nRow /= 2;
         3465  +          pc.plan.nRow /= 2;
  3431   3466           }
  3432   3467         }
  3433         -      if( nRow<2 ) nRow = 2;
         3468  +      if( pc.plan.nRow<2 ) pc.plan.nRow = 2;
  3434   3469       }
  3435   3470   
  3436   3471   
  3437   3472       WHERETRACE((
  3438   3473         "%s(%s):\n"
  3439   3474         "    nEq=%d nInMul=%d rangeDiv=%d bSort=%d bLookup=%d wsFlags=0x%08x\n"
  3440   3475         "    notReady=0x%llx log10N=%.1f nRow=%.1f cost=%.1f\n"
  3441   3476         "    used=0x%llx nOrdered=%d nOBSat=%d\n",
  3442   3477         pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk"), 
  3443         -      nEq, nInMul, (int)rangeDiv, bSort, bLookup, wsFlags,
  3444         -      p->notReady, log10N, nRow, cost, used, nOrdered, nOBSat
         3478  +      pc.plan.nEq, nInMul, (int)rangeDiv, bSort, bLookup, pc.plan.wsFlags,
         3479  +      p->notReady, log10N, pc.plan.nRow, pc.rCost, pc.used, nOrdered,
         3480  +      pc.plan.nOBSat
  3445   3481       ));
  3446   3482   
  3447   3483       /* If this index is the best we have seen so far, then record this
  3448         -    ** index and its cost in the pCost structure.
         3484  +    ** index and its cost in the p->cost structure.
  3449   3485       */
  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;
         3486  +    if( (!pIdx || pc.plan.wsFlags) && compareCost(&pc, &p->cost) ){
         3487  +      p->cost = pc;
         3488  +      p->cost.plan.wsFlags &= wsFlagMask;
  3459   3489         p->cost.plan.u.pIdx = pIdx;
  3460   3490       }
  3461   3491   
  3462   3492       /* If there was an INDEXED BY clause, then only that one index is
  3463   3493       ** considered. */
  3464   3494       if( pSrc->pIndex ) break;
  3465   3495   
................................................................................
  3473   3503     ** in. This is used for application testing, to help find cases
  3474   3504     ** where application behaviour depends on the (undefined) order that
  3475   3505     ** SQLite outputs rows in in the absence of an ORDER BY clause.  */
  3476   3506     if( !p->pOrderBy && pParse->db->flags & SQLITE_ReverseOrder ){
  3477   3507       p->cost.plan.wsFlags |= WHERE_REVERSE;
  3478   3508     }
  3479   3509   
  3480         -  assert( p->pOrderBy || (p->cost.plan.wsFlags&WHERE_ORDERBY)==0 );
         3510  +  assert( p->pOrderBy || (p->cost.plan.wsFlags&WHERE_ORDERED)==0 );
  3481   3511     assert( p->cost.plan.u.pIdx==0 || (p->cost.plan.wsFlags&WHERE_ROWID_EQ)==0 );
  3482   3512     assert( pSrc->pIndex==0 
  3483   3513          || p->cost.plan.u.pIdx==0 
  3484   3514          || p->cost.plan.u.pIdx==pSrc->pIndex 
  3485   3515     );
  3486   3516   
  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         -  ));
         3517  +  WHERETRACE(("best index is: %s\n",
         3518  +         p->cost.plan.u.pIdx ? p->cost.plan.u.pIdx->zName : "ipk"));
  3491   3519     
  3492   3520     bestOrClauseIndex(p);
  3493   3521     bestAutomaticIndex(p);
  3494   3522     p->cost.plan.wsFlags |= eqTermMask;
  3495   3523   }
  3496   3524   
  3497   3525   /*
................................................................................
  4211   4239       ** query, then the caller will only allow the loop to run for
  4212   4240       ** a single iteration. This means that the first row returned
  4213   4241       ** should not have a NULL value stored in 'x'. If column 'x' is
  4214   4242       ** the first one after the nEq equality constraints in the index,
  4215   4243       ** this requires some special handling.
  4216   4244       */
  4217   4245       if( (wctrlFlags&WHERE_ORDERBY_MIN)!=0
  4218         -     && (pLevel->plan.wsFlags&WHERE_ORDERBY)
         4246  +     && (pLevel->plan.wsFlags&WHERE_ORDERED)
  4219   4247        && (pIdx->nColumn>nEq)
  4220   4248       ){
  4221   4249         /* assert( pOrderBy->nExpr==1 ); */
  4222   4250         /* assert( pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq] ); */
  4223   4251         isMinQuery = 1;
  4224   4252         nExtraReg = 1;
  4225   4253       }
................................................................................
  5074   5102           **       index specified by its INDEXED BY clause.  This rule ensures
  5075   5103           **       that a best-so-far is always selected even if an impossible
  5076   5104           **       combination of INDEXED BY clauses are given.  The error
  5077   5105           **       will be detected and relayed back to the application later.
  5078   5106           **       The NEVER() comes about because rule (2) above prevents
  5079   5107           **       An indexable full-table-scan from reaching rule (3).
  5080   5108           **
  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.
         5109  +        **   (4) The plan cost must be lower than prior plans, where "cost"
         5110  +        **       is defined by the compareCost() function above. 
  5083   5111           */
  5084   5112           if( (sWBI.cost.used&sWBI.notValid)==0                    /* (1) */
  5085   5113               && (bestJ<0 || (notIndexed&m)!=0                     /* (2) */
  5086   5114                   || (bestPlan.plan.wsFlags & WHERE_NOT_FULLSCAN)==0
  5087   5115                   || (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0)
  5088   5116               && (nUnconstrained==0 || sWBI.pSrc->pIndex==0        /* (3) */
  5089   5117                   || 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))
         5118  +            && (bestJ<0 || compareCost(&sWBI.cost, &bestPlan))   /* (4) */
  5093   5119           ){
  5094         -          WHERETRACE(("=== table %d (%s) is best so far"
  5095         -                      " with cost=%.1f, nRow=%.1f, nOBSat=%d\n",
         5120  +          WHERETRACE(("=== table %d (%s) is best so far\n"
         5121  +                      "    cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=%08x\n",
  5096   5122                         j, sWBI.pSrc->pTab->zName,
  5097   5123                         sWBI.cost.rCost, sWBI.cost.plan.nRow,
  5098         -                      sWBI.cost.plan.nOBSat));
         5124  +                      sWBI.cost.plan.nOBSat, sWBI.cost.plan.wsFlags));
  5099   5125             bestPlan = sWBI.cost;
  5100   5126             bestJ = j;
  5101   5127           }
  5102   5128           if( doNotReorder ) break;
  5103   5129         }
  5104   5130       }
  5105   5131       assert( bestJ>=0 );
  5106   5132       assert( sWBI.notValid & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );
  5107   5133       WHERETRACE(("*** Optimizer selects table %d (%s) for loop %d with:\n"
  5108         -                "    cost=%.1f, nRow=%.1f, nOBSat=%d wsFlags=0x%08x\n",
         5134  +                "    cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=0x%08x\n",
  5109   5135                   bestJ, pTabList->a[bestJ].pTab->zName,
  5110   5136                   pLevel-pWInfo->a, bestPlan.rCost, bestPlan.plan.nRow,
  5111   5137                   bestPlan.plan.nOBSat, bestPlan.plan.wsFlags));
  5112         -    if( (bestPlan.plan.wsFlags & WHERE_ORDERBY)!=0 ){
  5113         -      pWInfo->nOBSat = pOrderBy->nExpr;
  5114         -    }
  5115   5138       if( (bestPlan.plan.wsFlags & WHERE_DISTINCT)!=0 ){
  5116   5139         assert( pWInfo->eDistinct==0 );
  5117   5140         pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
  5118   5141       }
  5119   5142       andFlags &= bestPlan.plan.wsFlags;
  5120   5143       pLevel->plan = bestPlan.plan;
  5121   5144       pLevel->iTabCur = pTabList->a[bestJ].iCursor;
................................................................................
  5156   5179         }
  5157   5180       }
  5158   5181     }
  5159   5182     WHERETRACE(("*** Optimizer Finished ***\n"));
  5160   5183     if( pParse->nErr || db->mallocFailed ){
  5161   5184       goto whereBeginError;
  5162   5185     }
         5186  +  if( nTabList ){
         5187  +    pLevel--;
         5188  +    pWInfo->nOBSat = pLevel->plan.nOBSat;
         5189  +  }else{
         5190  +    pWInfo->nOBSat = 0;
         5191  +  }
  5163   5192   
  5164   5193     /* If the total query only selects a single row, then the ORDER BY
  5165   5194     ** clause is irrelevant.
  5166   5195     */
  5167   5196     if( (andFlags & WHERE_UNIQUE)!=0 && pOrderBy ){
         5197  +    assert( nTabList==0 || (pLevel->plan.wsFlags & WHERE_ALL_UNIQUE)!=0 );
  5168   5198       pWInfo->nOBSat = pOrderBy->nExpr;
  5169   5199     }
  5170   5200   
  5171   5201     /* If the caller is an UPDATE or DELETE statement that is requesting
  5172   5202     ** to use a one-pass algorithm, determine if this is appropriate.
  5173   5203     ** The one-pass algorithm only works if the WHERE clause constraints
  5174   5204     ** 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.

    88     88   do_test 2.1 {
    89     89     db eval {
    90     90       SELECT a||','||c||','||e||','||g FROM t31, t32, t33, t34
    91     91        WHERE c=b AND e=d AND g=f
    92     92        ORDER BY +a ASC, +c ASC, +e DESC, +g ASC;
    93     93     }
    94     94   } {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         -    
           95  +
    96     96   
    97     97   finish_test