/ Check-in [4847c6cb]
Login

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

Overview
Comment:Change the weighting of binary searches on tables to 1/10th the cost of a search on an index. Change the assumed reduction in search space from a indexed range constraint from 1/3rd to 1/4th. Do not let the estimated number of rows drop below 1.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | stat2-enhancement
Files: files | file ages | folders
SHA1: 4847c6cb71423248b186ab7842b97c83e2f5fefd
User & Date: drh 2011-01-28 01:57:41
Context
2011-01-28
03:13
Reactivate the analyze5.test script. Closed-Leaf check-in: a2a9f640 user: drh tags: stat2-enhancement
01:57
Change the weighting of binary searches on tables to 1/10th the cost of a search on an index. Change the assumed reduction in search space from a indexed range constraint from 1/3rd to 1/4th. Do not let the estimated number of rows drop below 1. check-in: 4847c6cb user: drh tags: stat2-enhancement
2011-01-24
17:46
Restructuring and generalizing analyze5.test. The whole script is currently disabled and will need to be reenabled prior to merging with trunk. check-in: 31fcc706 user: drh tags: stat2-enhancement
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

  2417   2417   ** value of 1 indicates that the proposed range scan is expected to visit
  2418   2418   ** approximately 1/100th (1%) of the rows selected by the nEq equality
  2419   2419   ** constraints (if any). A return value of 100 indicates that it is expected
  2420   2420   ** that the range scan will visit every row (100%) selected by the equality
  2421   2421   ** constraints.
  2422   2422   **
  2423   2423   ** In the absence of sqlite_stat2 ANALYZE data, each range inequality
  2424         -** reduces the search space by 2/3rds.  Hence a single constraint (x>?)
  2425         -** results in a return of 33 and a range constraint (x>? AND x<?) results
  2426         -** in a return of 11.
         2424  +** reduces the search space by 3/4ths.  Hence a single constraint (x>?)
         2425  +** results in a return of 25 and a range constraint (x>? AND x<?) results
         2426  +** in a return of 6.
  2427   2427   */
  2428   2428   static int whereRangeScanEst(
  2429   2429     Parse *pParse,       /* Parsing & code generating context */
  2430   2430     Index *p,            /* The index containing the range-compared column; "x" */
  2431   2431     int nEq,             /* index into p->aCol[] of the range-compared column */
  2432   2432     WhereTerm *pLower,   /* Lower bound on the range. ex: "x>123" Might be NULL */
  2433   2433     WhereTerm *pUpper,   /* Upper bound on the range. ex: "x<455" Might be NULL */
................................................................................
  2494   2494   #else
  2495   2495     UNUSED_PARAMETER(pParse);
  2496   2496     UNUSED_PARAMETER(p);
  2497   2497     UNUSED_PARAMETER(nEq);
  2498   2498   #endif
  2499   2499     assert( pLower || pUpper );
  2500   2500     *piEst = 100;
  2501         -  if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ) *piEst /= 3;
  2502         -  if( pUpper ) *piEst /= 3;
         2501  +  if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ) *piEst /= 4;
         2502  +  if( pUpper ) *piEst /= 4;
  2503   2503     return rc;
  2504   2504   }
  2505   2505   
  2506   2506   #ifdef SQLITE_ENABLE_STAT2
  2507   2507   /*
  2508   2508   ** Estimate the number of rows that will be returned based on
  2509   2509   ** an equality constraint x=VALUE and where that VALUE occurs in
................................................................................
  2632   2632     sqlite3ValueFree(pVal);
  2633   2633     return rc;
  2634   2634   }
  2635   2635   #endif /* defined(SQLITE_ENABLE_STAT2) */
  2636   2636   
  2637   2637   
  2638   2638   /*
  2639         -** Find the query plan for accessing a particular table.  Write the
         2639  +** Find the best query plan for accessing a particular table.  Write the
  2640   2640   ** best query plan and its cost into the WhereCost object supplied as the
  2641   2641   ** last parameter.
  2642   2642   **
  2643   2643   ** The lowest cost plan wins.  The cost is an estimate of the amount of
  2644         -** CPU and disk I/O need to process the request using the selected plan.
         2644  +** CPU and disk I/O needed to process the requested result.
  2645   2645   ** Factors that influence cost include:
  2646   2646   **
  2647   2647   **    *  The estimated number of rows that will be retrieved.  (The
  2648   2648   **       fewer the better.)
  2649   2649   **
  2650   2650   **    *  Whether or not sorting must occur.
  2651   2651   **
................................................................................
  2656   2656   ** the SQL statement, then this function only considers plans using the 
  2657   2657   ** named index. If no such plan is found, then the returned cost is
  2658   2658   ** SQLITE_BIG_DBL. If a plan is found that uses the named index, 
  2659   2659   ** then the cost is calculated in the usual way.
  2660   2660   **
  2661   2661   ** If a NOT INDEXED clause (pSrc->notIndexed!=0) was attached to the table 
  2662   2662   ** in the SELECT statement, then no indexes are considered. However, the 
  2663         -** selected plan may still take advantage of the tables built-in rowid
         2663  +** selected plan may still take advantage of the built-in rowid primary key
  2664   2664   ** index.
  2665   2665   */
  2666   2666   static void bestBtreeIndex(
  2667   2667     Parse *pParse,              /* The parsing context */
  2668   2668     WhereClause *pWC,           /* The WHERE clause */
  2669   2669     struct SrcList_item *pSrc,  /* The FROM clause term to search */
  2670   2670     Bitmask notReady,           /* Mask of cursors not available for indexing */
................................................................................
  2699   2699   
  2700   2700     if( pSrc->pIndex ){
  2701   2701       /* An INDEXED BY clause specifies a particular index to use */
  2702   2702       pIdx = pProbe = pSrc->pIndex;
  2703   2703       wsFlagMask = ~(WHERE_ROWID_EQ|WHERE_ROWID_RANGE);
  2704   2704       eqTermMask = idxEqTermMask;
  2705   2705     }else{
  2706         -    /* There is no INDEXED BY clause.  Create a fake Index object to
  2707         -    ** represent the primary key */
  2708         -    Index *pFirst;                /* Any other index on the table */
         2706  +    /* There is no INDEXED BY clause.  Create a fake Index object in local
         2707  +    ** variable sPk to represent the rowid primary key index.  Make this
         2708  +    ** fake index the first in a chain of Index objects with all of the real
         2709  +    ** indices to follow */
         2710  +    Index *pFirst;                  /* First of real indices on the table */
  2709   2711       memset(&sPk, 0, sizeof(Index));
  2710   2712       sPk.nColumn = 1;
  2711   2713       sPk.aiColumn = &aiColumnPk;
  2712   2714       sPk.aiRowEst = aiRowEstPk;
  2713   2715       sPk.onError = OE_Replace;
  2714   2716       sPk.pTable = pSrc->pTab;
  2715   2717       aiRowEstPk[0] = pSrc->pTab->nRowEst;
  2716   2718       aiRowEstPk[1] = 1;
  2717   2719       pFirst = pSrc->pTab->pIndex;
  2718   2720       if( pSrc->notIndexed==0 ){
         2721  +      /* The real indices of the table are only considered if the
         2722  +      ** NOT INDEXED qualifier is omitted from the FROM clause */
  2719   2723         sPk.pNext = pFirst;
  2720   2724       }
  2721   2725       pProbe = &sPk;
  2722   2726       wsFlagMask = ~(
  2723   2727           WHERE_COLUMN_IN|WHERE_COLUMN_EQ|WHERE_COLUMN_NULL|WHERE_COLUMN_RANGE
  2724   2728       );
  2725   2729       eqTermMask = WO_EQ|WO_IN;
................................................................................
  2729   2733     /* Loop over all indices looking for the best one to use
  2730   2734     */
  2731   2735     for(; pProbe; pIdx=pProbe=pProbe->pNext){
  2732   2736       const unsigned int * const aiRowEst = pProbe->aiRowEst;
  2733   2737       double cost;                /* Cost of using pProbe */
  2734   2738       double nRow;                /* Estimated number of rows in result set */
  2735   2739       int rev;                    /* True to scan in reverse order */
         2740  +    double nSearch;             /* Estimated number of binary searches */
  2736   2741       int wsFlags = 0;
  2737   2742       Bitmask used = 0;
  2738   2743   
  2739   2744       /* The following variables are populated based on the properties of
  2740         -    ** scan being evaluated. They are then used to determine the expected
         2745  +    ** index being evaluated. They are then used to determine the expected
  2741   2746       ** cost and number of rows returned.
  2742   2747       **
  2743   2748       **  nEq: 
  2744   2749       **    Number of equality terms that can be implemented using the index.
         2750  +    **    In other words, the number of initial fields in the index that
         2751  +    **    are used in == or IN or NOT NULL constraints of the WHERE clause.
  2745   2752       **
  2746   2753       **  nInMul:  
  2747   2754       **    The "in-multiplier". This is an estimate of how many seek operations 
  2748   2755       **    SQLite must perform on the index in question. For example, if the 
  2749   2756       **    WHERE clause is:
  2750   2757       **
  2751   2758       **      WHERE a IN (1, 2, 3) AND b IN (4, 5, 6)
................................................................................
  2761   2768       **
  2762   2769       **    If there exists a WHERE term of the form "x IN (SELECT ...)", then 
  2763   2770       **    the sub-select is assumed to return 25 rows for the purposes of 
  2764   2771       **    determining nInMul.
  2765   2772       **
  2766   2773       **  bInEst:  
  2767   2774       **    Set to true if there was at least one "x IN (SELECT ...)" term used 
  2768         -    **    in determining the value of nInMul.
         2775  +    **    in determining the value of nInMul.  Note that the RHS of the
         2776  +    **    IN operator must be a SELECT, not a value list, for this variable
         2777  +    **    to be true.
  2769   2778       **
  2770   2779       **  estBound:
  2771   2780       **    An estimate on the amount of the table that must be searched.  A
  2772   2781       **    value of 100 means the entire table is searched.  Range constraints
  2773   2782       **    might reduce this to a value less than 100 to indicate that only
  2774   2783       **    a fraction of the table needs searching.  In the absence of
  2775   2784       **    sqlite_stat2 ANALYZE data, a single inequality reduces the search
  2776         -    **    space to 1/3rd its original size.  So an x>? constraint reduces
  2777         -    **    estBound to 33.  Two constraints (x>? AND x<?) reduce estBound to 11.
         2785  +    **    space to 1/4rd its original size.  So an x>? constraint reduces
         2786  +    **    estBound to 25.  Two constraints (x>? AND x<?) reduce estBound to 6.
  2778   2787       **
  2779   2788       **  bSort:   
  2780   2789       **    Boolean. True if there is an ORDER BY clause that will require an 
  2781   2790       **    external sort (i.e. scanning the index being evaluated will not 
  2782   2791       **    correctly order records).
  2783   2792       **
  2784   2793       **  bLookup: 
  2785         -    **    Boolean. True if for each index entry visited a lookup on the 
  2786         -    **    corresponding table b-tree is required. This is always false 
  2787         -    **    for the rowid index. For other indexes, it is true unless all the 
  2788         -    **    columns of the table used by the SELECT statement are present in 
  2789         -    **    the index (such an index is sometimes described as a covering index).
         2794  +    **    Boolean. True if a table lookup is required for each index entry
         2795  +    **    visited.  In other words, true if this is not a covering index.
         2796  +    **    This is always false for the rowid primary key index of a table.
         2797  +    **    For other indexes, it is true unless all the columns of the table
         2798  +    **    used by the SELECT statement are present in the index (such an
         2799  +    **    index is sometimes described as a covering index).
  2790   2800       **    For example, given the index on (a, b), the second of the following 
  2791         -    **    two queries requires table b-tree lookups, but the first does not.
         2801  +    **    two queries requires table b-tree lookups in order to find the value
         2802  +    **    of column c, but the first does not because columns a and b are
         2803  +    **    both available in the index.
  2792   2804       **
  2793   2805       **             SELECT a, b    FROM tbl WHERE a = 1;
  2794   2806       **             SELECT a, b, c FROM tbl WHERE a = 1;
  2795   2807       */
  2796         -    int nEq;
  2797         -    int bInEst = 0;
  2798         -    int nInMul = 1;
  2799         -    int estBound = 100;
         2808  +    int nEq;                      /* Number of == or IN terms matching index */
         2809  +    int bInEst = 0;               /* True if "x IN (SELECT...)" seen */
         2810  +    int nInMul = 1;               /* Number of distinct equalities to lookup */
         2811  +    int estBound = 100;           /* Estimated reduction in search space */
  2800   2812       int nBound = 0;               /* Number of range constraints seen */
  2801         -    int bSort = 0;
  2802         -    int bLookup = 0;
         2813  +    int bSort = 0;                /* True if external sort required */
         2814  +    int bLookup = 0;              /* True if not a covering index */
  2803   2815       WhereTerm *pTerm;             /* A single term of the WHERE clause */
  2804   2816   #ifdef SQLITE_ENABLE_STAT2
  2805   2817       WhereTerm *pFirstTerm = 0;    /* First term matching the index */
  2806   2818   #endif
  2807   2819   
  2808   2820       /* Determine the values of nEq and nInMul */
  2809   2821       for(nEq=0; nEq<pProbe->nColumn; nEq++){
................................................................................
  2814   2826         if( pTerm->eOperator & WO_IN ){
  2815   2827           Expr *pExpr = pTerm->pExpr;
  2816   2828           wsFlags |= WHERE_COLUMN_IN;
  2817   2829           if( ExprHasProperty(pExpr, EP_xIsSelect) ){
  2818   2830             /* "x IN (SELECT ...)":  Assume the SELECT returns 25 rows */
  2819   2831             nInMul *= 25;
  2820   2832             bInEst = 1;
  2821         -        }else if( ALWAYS(pExpr->x.pList) ){
         2833  +        }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){
  2822   2834             /* "x IN (value, value, ...)" */
  2823         -          nInMul *= pExpr->x.pList->nExpr + 1;
         2835  +          nInMul *= pExpr->x.pList->nExpr;
  2824   2836           }
  2825   2837         }else if( pTerm->eOperator & WO_ISNULL ){
  2826   2838           wsFlags |= WHERE_COLUMN_NULL;
  2827   2839         }
  2828   2840   #ifdef SQLITE_ENABLE_STAT2
  2829   2841         if( nEq==0 && pProbe->aSample ) pFirstTerm = pTerm;
  2830   2842   #endif
................................................................................
  2919   2931       }
  2920   2932   #endif /* SQLITE_ENABLE_STAT2 */
  2921   2933   
  2922   2934       /* Adjust the number of rows and the cost downward to reflect rows
  2923   2935       ** that are excluded by range constraints.
  2924   2936       */
  2925   2937       nRow = (nRow * (double)estBound) / (double)100;
         2938  +    if( nRow<1 ) nRow = 1;
  2926   2939   
  2927         -    /* Assume constant cost to access a row and logarithmic cost to
  2928         -    ** do a binary search.  Hence, the initial cost is the number of output
  2929         -    ** rows plus log2(table-size) times the number of binary searches.
         2940  +    /* Assume constant cost to advance from one row to the next and
         2941  +    ** logarithmic cost to do a binary search.  Hence, the initial cost
         2942  +    ** is the number of output rows plus log2(table-size) times the
         2943  +    ** number of binary searches.
         2944  +    **
         2945  +    ** Because fan-out on tables is so much higher than the fan-out on
         2946  +    ** indices (because table btrees contain only integer keys in non-leaf
         2947  +    ** nodes) we weight the cost of a table binary search as 1/10th the
         2948  +    ** cost of an index binary search.
  2930   2949       */
  2931         -    if( pIdx && bLookup ){
  2932         -      cost = nRow + (nInMul+nRow)*estLog(aiRowEst[0]);
         2950  +    if( pIdx ){
         2951  +      if( bLookup ){
         2952  +        /* For an index lookup followed by a table lookup:
         2953  +        **    nInMul index searches to find the start of each index range
         2954  +        **  + nRow steps through the index
         2955  +        **  + nRow table searches to lookup the table entry using the rowid
         2956  +        */
         2957  +        nSearch = nInMul + nRow/10;
         2958  +      }else{
         2959  +        /* For a covering index:
         2960  +        **     nInMul binary searches to find the initial entry 
         2961  +        **   + nRow steps through the index
         2962  +        */
         2963  +        nSearch = nInMul;
         2964  +      }
  2933   2965       }else{
  2934         -      cost = nRow + nInMul*estLog(aiRowEst[0]);
         2966  +      /* For a rowid primary key lookup:
         2967  +      **    nInMult binary searches to find the initial entry scaled by 1/10th
         2968  +      **  + nRow steps through the table
         2969  +      */
         2970  +      nSearch = nInMul/10;
  2935   2971       }
         2972  +    cost = nRow + nSearch*estLog(aiRowEst[0]);
  2936   2973   
  2937   2974       /* Add in the estimated cost of sorting the result.  This cost is expanded
  2938   2975       ** by a fudge factor of 3.0 to account for the fact that a sorting step 
  2939   2976       ** involves a write and is thus more expensive than a lookup step.
  2940   2977       */
  2941   2978       if( bSort ){
  2942   2979         cost += nRow*estLog(nRow)*(double)3;
................................................................................
  2983   3020           }else if( pTerm->eOperator & (WO_LT|WO_LE|WO_GT|WO_GE) ){
  2984   3021             if( nSkipRange ){
  2985   3022               /* Ignore the first nSkipRange range constraints since the index
  2986   3023               ** has already accounted for these */
  2987   3024               nSkipRange--;
  2988   3025             }else{
  2989   3026               /* Assume each additional range constraint reduces the result
  2990         -            ** set size by a factor of 3 */
         3027  +            ** set size by a factor of 3.  Indexed range constraints reduce
         3028  +            ** the search space by a larger factor: 4.  We make indexed range
         3029  +            ** more selective intentionally because of the subjective 
         3030  +            ** observation that indexed range constraints really are more
         3031  +            ** selective in practice, on average. */
  2991   3032               nRow /= 3;
  2992   3033             }
  2993   3034           }else if( pTerm->eOperator!=WO_NOOP ){
  2994   3035             /* Any other expression lowers the output row count by half */
  2995   3036             nRow /= 2;
  2996   3037           }
  2997   3038         }

Changes to test/analyze2.test.

   238    238       execsql { INSERT INTO t3 VALUES($str, $str) }
   239    239     }
   240    240     execsql COMMIT
   241    241     execsql ANALYZE
   242    242   } {}
   243    243   do_test analyze2-4.2 {
   244    244     execsql { 
          245  +    PRAGMA automatic_index=OFF;
   245    246       SELECT tbl,idx,group_concat(sample,' ') 
   246    247       FROM sqlite_stat2 
   247    248       WHERE idx = 't3a' 
   248         -    GROUP BY tbl,idx
          249  +    GROUP BY tbl,idx;
          250  +    PRAGMA automatic_index=ON;
   249    251     }
   250    252   } {t3 t3a {AfA bEj CEj dEj EEj fEj GEj hEj IEj jEj}}
   251    253   do_test analyze2-4.3 {
   252    254     execsql { 
   253    255       SELECT tbl,idx,group_concat(sample,' ') 
   254    256       FROM sqlite_stat2 
   255    257       WHERE idx = 't3b' 
................................................................................
   404    406       DELETE FROM sqlite_stat2;
   405    407     }
   406    408     sqlite3 db test.db
   407    409     eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
   408    410           t5.a>1 AND t5.a<15 AND
   409    411           t6.a>1
   410    412     }
   411         -} {0 0 0 {SEARCH TABLE t5 USING COVERING INDEX t5i (a>? AND a<?) (~110000 rows)} 0 1 1 {SEARCH TABLE t6 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
          413  +} {0 0 0 {SEARCH TABLE t5 USING COVERING INDEX t5i (a>? AND a<?) (~60000 rows)} 0 1 1 {SEARCH TABLE t6 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
   412    414   do_test analyze2-6.2.2 {
   413    415     db cache flush
   414    416     execsql ANALYZE
   415    417     eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
   416    418           t5.a>1 AND t5.a<15 AND
   417    419           t6.a>1
   418    420     }
................................................................................
   430    432       DELETE FROM sqlite_master WHERE tbl_name = 'sqlite_stat1';
   431    433     }
   432    434     sqlite3 db test.db
   433    435     eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
   434    436           t5.a>1 AND t5.a<15 AND
   435    437           t6.a>1
   436    438     }
   437         -} {0 0 0 {SEARCH TABLE t5 USING COVERING INDEX t5i (a>? AND a<?) (~110000 rows)} 0 1 1 {SEARCH TABLE t6 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
          439  +} {0 0 0 {SEARCH TABLE t5 USING COVERING INDEX t5i (a>? AND a<?) (~60000 rows)} 0 1 1 {SEARCH TABLE t6 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
   438    440   do_test analyze2-6.2.5 {
   439    441     execsql { 
   440    442       PRAGMA writable_schema = 1;
   441    443       DELETE FROM sqlite_master WHERE tbl_name = 'sqlite_stat2';
   442    444     }
   443    445     sqlite3 db test.db
   444    446     eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
   445    447           t5.a>1 AND t5.a<15 AND
   446    448           t6.a>1
   447    449     }
   448         -} {0 0 0 {SEARCH TABLE t5 USING COVERING INDEX t5i (a>? AND a<?) (~110000 rows)} 0 1 1 {SEARCH TABLE t6 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
          450  +} {0 0 0 {SEARCH TABLE t5 USING COVERING INDEX t5i (a>? AND a<?) (~60000 rows)} 0 1 1 {SEARCH TABLE t6 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
   449    451   do_test analyze2-6.2.6 {
   450    452     execsql { 
   451    453       PRAGMA writable_schema = 1;
   452    454       INSERT INTO sqlite_master SELECT * FROM master;
   453    455     }
   454    456     sqlite3 db test.db
   455    457     execsql ANALYZE
................................................................................
   538    540     do_test analyze2-7.10 {
   539    541       incr_schema_cookie test.db
   540    542       execsql { SELECT * FROM sqlite_master } db1
   541    543       eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
   542    544             t5.a>1 AND t5.a<15 AND
   543    545             t6.a>1
   544    546       } db1
   545         -  } {0 0 0 {SEARCH TABLE t5 USING COVERING INDEX t5i (a>? AND a<?) (~2 rows)} 0 1 1 {SEARCH TABLE t6 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
          547  +  } {0 0 0 {SEARCH TABLE t5 USING COVERING INDEX t5i (a>? AND a<?) (~1 rows)} 0 1 1 {SEARCH TABLE t6 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
   546    548   
   547    549     db1 close
   548    550     db2 close
   549    551     sqlite3_enable_shared_cache $::enable_shared_cache
   550    552   }
   551    553   
   552    554   finish_test

Changes to test/analyze3.test.

   244    244       append t [lindex {a b c d e f g h i j} [expr ($i%10)]]
   245    245       execsql { INSERT INTO t1 VALUES($i, $t) }
   246    246     }
   247    247     execsql COMMIT
   248    248   } {}
   249    249   do_eqp_test analyze3-2.2 {
   250    250     SELECT count(a) FROM t1 WHERE b LIKE 'a%'
   251         -} {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (b>? AND b<?) (~55000 rows)}}
          251  +} {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (b>? AND b<?) (~30000 rows)}}
   252    252   do_eqp_test analyze3-2.3 {
   253    253     SELECT count(a) FROM t1 WHERE b LIKE '%a'
   254    254   } {0 0 0 {SCAN TABLE t1 (~500000 rows)}}
   255    255   
   256    256   do_test analyze3-2.4 {
   257    257     sf_execsql { SELECT count(*) FROM t1 WHERE b LIKE 'a%' }
   258    258   } {101 0 100}

Changes to test/e_createtable.test.

  1375   1375     1    "EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE b = 5" 
  1376   1376          {0 0 0 {SEARCH TABLE t1 USING INDEX sqlite_autoindex_t1_1 (b=?) (~1 rows)}}
  1377   1377   
  1378   1378     2    "EXPLAIN QUERY PLAN SELECT * FROM t2 ORDER BY b, c"
  1379   1379          {0 0 0 {SCAN TABLE t2 USING INDEX sqlite_autoindex_t2_1 (~1000000 rows)}}
  1380   1380   
  1381   1381     3    "EXPLAIN QUERY PLAN SELECT * FROM t2 WHERE b=10 AND c>10"
  1382         -       {0 0 0 {SEARCH TABLE t2 USING INDEX sqlite_autoindex_t2_1 (b=? AND c>?) (~3 rows)}}
         1382  +       {0 0 0 {SEARCH TABLE t2 USING INDEX sqlite_autoindex_t2_1 (b=? AND c>?) (~2 rows)}}
  1383   1383   }
  1384   1384   
  1385   1385   # EVIDENCE-OF: R-45493-35653 A CHECK constraint may be attached to a
  1386   1386   # column definition or specified as a table constraint. In practice it
  1387   1387   # makes no difference.
  1388   1388   #
  1389   1389   #   All the tests that deal with CHECK constraints below (4.11.* and 

Changes to test/eqp.test.

   388    388   
   389    389   # EVIDENCE-OF: R-22253-05302 sqlite> EXPLAIN QUERY PLAN SELECT t1.*,
   390    390   # t2.* FROM t1, t2 WHERE t1.a=1 AND t1.b>2; 0|0|0|SEARCH TABLE t1
   391    391   # USING COVERING INDEX i2 (a=? AND b>?) (~3 rows) 0|1|1|SCAN TABLE t2
   392    392   # (~1000000 rows)
   393    393   do_execsql_test 5.4.0 {CREATE TABLE t2(c, d)}
   394    394   det 5.4.1 "SELECT t1.*, t2.* FROM t1, t2 WHERE t1.a=1 AND t1.b>2" {
   395         -  0 0 0 {SEARCH TABLE t1 USING COVERING INDEX i2 (a=? AND b>?) (~3 rows)}
          395  +  0 0 0 {SEARCH TABLE t1 USING COVERING INDEX i2 (a=? AND b>?) (~2 rows)}
   396    396     0 1 1 {SCAN TABLE t2 (~1000000 rows)}
   397    397   }
   398    398   
   399    399   # EVIDENCE-OF: R-21040-07025 sqlite> EXPLAIN QUERY PLAN SELECT t1.*,
   400    400   # t2.* FROM t2, t1 WHERE t1.a=1 AND t1.b>2; 0|0|1|SEARCH TABLE t1
   401    401   # USING COVERING INDEX i2 (a=? AND b>?) (~3 rows) 0|1|0|SCAN TABLE t2
   402    402   # (~1000000 rows)
   403    403   det 5.5 "SELECT t1.*, t2.* FROM t2, t1 WHERE t1.a=1 AND t1.b>2" {
   404         -  0 0 1 {SEARCH TABLE t1 USING COVERING INDEX i2 (a=? AND b>?) (~3 rows)}
          404  +  0 0 1 {SEARCH TABLE t1 USING COVERING INDEX i2 (a=? AND b>?) (~2 rows)}
   405    405     0 1 0 {SCAN TABLE t2 (~1000000 rows)}
   406    406   }
   407    407   
   408    408   # EVIDENCE-OF: R-39007-61103 sqlite> CREATE INDEX i3 ON t1(b);
   409    409   # sqlite> EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE a=1 OR b=2;
   410    410   # 0|0|0|SEARCH TABLE t1 USING COVERING INDEX i2 (a=?) (~10 rows)
   411    411   # 0|0|0|SEARCH TABLE t1 USING INDEX i3 (b=?) (~10 rows)

Changes to test/indexedby.test.

   150    150   # Test embedding an INDEXED BY in a CREATE VIEW statement. This block
   151    151   # also tests that nothing bad happens if an index refered to by
   152    152   # a CREATE VIEW statement is dropped and recreated.
   153    153   #
   154    154   do_execsql_test indexedby-5.1 {
   155    155     CREATE VIEW v2 AS SELECT * FROM t1 INDEXED BY i1 WHERE a > 5;
   156    156     EXPLAIN QUERY PLAN SELECT * FROM v2 
   157         -} {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a>?) (~330000 rows)}}
          157  +} {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a>?) (~250000 rows)}}
   158    158   do_execsql_test indexedby-5.2 {
   159    159     EXPLAIN QUERY PLAN SELECT * FROM v2 WHERE b = 10 
   160         -} {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a>?) (~33000 rows)}}
          160  +} {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a>?) (~25000 rows)}}
   161    161   do_test indexedby-5.3 {
   162    162     execsql { DROP INDEX i1 }
   163    163     catchsql { SELECT * FROM v2 }
   164    164   } {1 {no such index: i1}}
   165    165   do_test indexedby-5.4 {
   166    166     # Recreate index i1 in such a way as it cannot be used by the view query.
   167    167     execsql { CREATE INDEX i1 ON t1(b) }

Changes to test/like.test.

   703    703         INSERT INTO t10 VALUES(12,12,12,12,12,12);
   704    704         INSERT INTO t10 VALUES(123,123,123,123,123,123);
   705    705         INSERT INTO t10 VALUES(234,234,234,234,234,234);
   706    706         INSERT INTO t10 VALUES(345,345,345,345,345,345);
   707    707         INSERT INTO t10 VALUES(45,45,45,45,45,45);
   708    708       }
   709    709       count {
   710         -      SELECT a FROM t10 WHERE b LIKE '12%' ORDER BY a;
          710  +      SELECT a FROM t10 WHERE b LIKE '12%' ORDER BY +a;
   711    711       }
   712    712     } {12 123 scan 5 like 6}
   713    713     do_test like-10.2 {
   714    714       count {
   715         -      SELECT a FROM t10 WHERE c LIKE '12%' ORDER BY a;
          715  +      SELECT a FROM t10 WHERE c LIKE '12%' ORDER BY +a;
   716    716       }
   717    717     } {12 123 scan 5 like 6}
   718    718     do_test like-10.3 {
   719    719       count {
   720         -      SELECT a FROM t10 WHERE d LIKE '12%' ORDER BY a;
          720  +      SELECT a FROM t10 WHERE d LIKE '12%' ORDER BY +a;
   721    721       }
   722    722     } {12 123 scan 5 like 6}
   723    723     do_test like-10.4 {
   724    724       count {
   725         -      SELECT a FROM t10 WHERE e LIKE '12%' ORDER BY a;
          725  +      SELECT a FROM t10 WHERE e LIKE '12%' ORDER BY +a;
   726    726       }
   727    727     } {12 123 scan 5 like 6}
   728    728     do_test like-10.5 {
   729    729       count {
   730         -      SELECT a FROM t10 WHERE f LIKE '12%' ORDER BY a;
          730  +      SELECT a FROM t10 WHERE f LIKE '12%' ORDER BY +a;
   731    731       }
   732    732     } {12 123 scan 3 like 0}
   733    733     do_test like-10.6 {
   734    734       count {
   735         -      SELECT a FROM t10 WHERE a LIKE '12%' ORDER BY a;
          735  +      SELECT a FROM t10 WHERE a LIKE '12%' ORDER BY +a;
   736    736       }
   737    737     } {12 123 scan 5 like 6}
   738    738     do_test like-10.10 {
   739    739       execsql {
   740    740         CREATE TABLE t10b(
   741    741           a INTEGER PRIMARY KEY,
   742    742           b INTEGER UNIQUE,
................................................................................
   744    744           d BLOB UNIQUE,
   745    745           e UNIQUE,
   746    746           f TEXT UNIQUE
   747    747         );
   748    748         INSERT INTO t10b SELECT * FROM t10;
   749    749       }
   750    750       count {
   751         -      SELECT a FROM t10b WHERE b GLOB '12*' ORDER BY a;
          751  +      SELECT a FROM t10b WHERE b GLOB '12*' ORDER BY +a;
   752    752       }
   753    753     } {12 123 scan 5 like 6}
   754    754     do_test like-10.11 {
   755    755       count {
   756         -      SELECT a FROM t10b WHERE c GLOB '12*' ORDER BY a;
          756  +      SELECT a FROM t10b WHERE c GLOB '12*' ORDER BY +a;
   757    757       }
   758    758     } {12 123 scan 5 like 6}
   759    759     do_test like-10.12 {
   760    760       count {
   761         -      SELECT a FROM t10b WHERE d GLOB '12*' ORDER BY a;
          761  +      SELECT a FROM t10b WHERE d GLOB '12*' ORDER BY +a;
   762    762       }
   763    763     } {12 123 scan 5 like 6}
   764    764     do_test like-10.13 {
   765    765       count {
   766         -      SELECT a FROM t10b WHERE e GLOB '12*' ORDER BY a;
          766  +      SELECT a FROM t10b WHERE e GLOB '12*' ORDER BY +a;
   767    767       }
   768    768     } {12 123 scan 5 like 6}
   769    769     do_test like-10.14 {
   770    770       count {
   771         -      SELECT a FROM t10b WHERE f GLOB '12*' ORDER BY a;
          771  +      SELECT a FROM t10b WHERE f GLOB '12*' ORDER BY +a;
   772    772       }
   773    773     } {12 123 scan 3 like 0}
   774    774     do_test like-10.15 {
   775    775       count {
   776         -      SELECT a FROM t10b WHERE a GLOB '12*' ORDER BY a;
          776  +      SELECT a FROM t10b WHERE a GLOB '12*' ORDER BY +a;
   777    777       }
   778    778     } {12 123 scan 5 like 6}
   779    779   }
   780    780   
   781    781   # LIKE and GLOB where the default collating sequence is not appropriate
   782    782   # but an index with the appropriate collating sequence exists.
   783    783   #
................................................................................
   815    815       SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY a;
   816    816     }
   817    817   } {abc abcd nosort t11 *}
   818    818   do_test like-11.3 {
   819    819     queryplan {
   820    820       PRAGMA case_sensitive_like=OFF;
   821    821       CREATE INDEX t11b ON t11(b);
   822         -    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY a;
          822  +    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY +a;
   823    823     }
   824    824   } {abc abcd ABC ABCD sort {} t11b}
   825    825   do_test like-11.4 {
   826    826     queryplan {
   827    827       PRAGMA case_sensitive_like=ON;
   828    828       SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY a;
   829    829     }
   830    830   } {abc abcd nosort t11 *}
   831    831   do_test like-11.5 {
   832    832     queryplan {
   833    833       PRAGMA case_sensitive_like=OFF;
   834    834       DROP INDEX t11b;
   835    835       CREATE INDEX t11bnc ON t11(b COLLATE nocase);
   836         -    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY a;
          836  +    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY +a;
   837    837     }
   838    838   } {abc abcd ABC ABCD sort {} t11bnc}
   839    839   do_test like-11.6 {
   840    840     queryplan {
   841    841       CREATE INDEX t11bb ON t11(b COLLATE binary);
   842         -    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY a;
          842  +    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY +a;
   843    843     }
   844    844   } {abc abcd ABC ABCD sort {} t11bnc}
   845    845   do_test like-11.7 {
   846    846     queryplan {
   847    847       PRAGMA case_sensitive_like=ON;
   848         -    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY a;
          848  +    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY +a;
   849    849     }
   850    850   } {abc abcd sort {} t11bb}
   851    851   do_test like-11.8 {
   852    852     queryplan {
   853    853       PRAGMA case_sensitive_like=OFF;
   854         -    SELECT b FROM t11 WHERE b GLOB 'abc*' ORDER BY a;
          854  +    SELECT b FROM t11 WHERE b GLOB 'abc*' ORDER BY +a;
   855    855     }
   856    856   } {abc abcd sort {} t11bb}
   857    857   do_test like-11.9 {
   858    858     queryplan {
   859    859       CREATE INDEX t11cnc ON t11(c COLLATE nocase);
   860    860       CREATE INDEX t11cb ON t11(c COLLATE binary);
   861         -    SELECT c FROM t11 WHERE c LIKE 'abc%' ORDER BY a;
          861  +    SELECT c FROM t11 WHERE c LIKE 'abc%' ORDER BY +a;
   862    862     }
   863    863   } {abc abcd ABC ABCD sort {} t11cnc}
   864    864   do_test like-11.10 {
   865    865     queryplan {
   866         -    SELECT c FROM t11 WHERE c GLOB 'abc*' ORDER BY a;
          866  +    SELECT c FROM t11 WHERE c GLOB 'abc*' ORDER BY +a;
   867    867     }
   868    868   } {abc abcd sort {} t11cb}
   869    869   
   870    870   
   871    871   finish_test

Changes to test/minmax3.test.

    48     48       INSERT INTO t1 VALUES('1', 'I',   'one');
    49     49       INSERT INTO t1 VALUES('2', 'IV',  'four');
    50     50       INSERT INTO t1 VALUES('2', NULL,  'three');
    51     51       INSERT INTO t1 VALUES('2', 'II',  'two');
    52     52       INSERT INTO t1 VALUES('2', 'V',   'five');
    53     53       INSERT INTO t1 VALUES('3', 'VI',  'six');
    54     54       COMMIT;
           55  +    PRAGMA automatic_index=OFF;
    55     56     }
    56     57   } {}
    57     58   do_test minmax3-1.1.1 {
    58     59     # Linear scan.
    59     60     count { SELECT max(y) FROM t1 WHERE x = '2'; }
    60     61   } {V 5}
    61     62   do_test minmax3-1.1.2 {

Changes to test/where3.test.

   221    221     CREATE TABLE t301(a INTEGER PRIMARY KEY,b,c);
   222    222     CREATE INDEX t301c ON t301(c);
   223    223     INSERT INTO t301 VALUES(1,2,3);
   224    224     CREATE TABLE t302(x, y);
   225    225     ANALYZE;
   226    226     explain query plan SELECT * FROM t302, t301 WHERE t302.x=5 AND t301.a=t302.y;
   227    227   } {
   228         -  0 0 0 {SCAN TABLE t302 (~0 rows)} 
          228  +  0 0 0 {SCAN TABLE t302 (~1 rows)} 
   229    229     0 1 1 {SEARCH TABLE t301 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}
   230    230   }
          231  +exit
   231    232   do_execsql_test where3-3.1 {
   232    233     explain query plan
   233    234     SELECT * FROM t301, t302 WHERE t302.x=5 AND t301.a=t302.y;
   234    235   } {
   235         -  0 0 1 {SCAN TABLE t302 (~0 rows)} 
          236  +  0 0 1 {SCAN TABLE t302 (~1 rows)} 
   236    237     0 1 0 {SEARCH TABLE t301 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}
   237    238   }
   238    239   
   239    240   # Verify that when there are multiple tables in a join which must be
   240    241   # full table scans that the query planner attempts put the table with
   241    242   # the fewest number of output rows as the outer loop.
   242    243   #

Changes to test/where9.test.

   468    468   
   469    469     # Likewise, inequalities in an AND are preferred over inequalities in
   470    470     # an OR.
   471    471     #
   472    472     do_execsql_test where9-5.3 {
   473    473       EXPLAIN QUERY PLAN SELECT a FROM t1 WHERE b>1000 AND (c>=31031 OR d IS NULL)
   474    474     } {
   475         -    0 0 0 {SEARCH TABLE t1 USING INDEX t1b (b>?) (~165000 rows)}
          475  +    0 0 0 {SEARCH TABLE t1 USING INDEX t1b (b>?) (~125000 rows)}
   476    476     }
   477    477   }
   478    478   
   479    479   ############################################################################
   480    480   # Make sure OR-clauses work correctly on UPDATE and DELETE statements.
   481    481   
   482    482   do_test where9-6.2.1 {