/ Check-in [2cd374cd]
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:The first of a planned series of enhancements to the query planner that enable it to make better use of sqlite_stat2 histograms when the table has many repeated values.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | stat2-enhancement
Files: files | file ages | folders
SHA1: 2cd374cd23fa2fd38f49090d6eeb9b1e521d51d5
User & Date: drh 2011-01-20 02:56:37
Context
2011-01-20
16:52
Use histogram data to improve the row-count estimates on equality constraints. check-in: 6bfc5c69 user: drh tags: stat2-enhancement
02:56
The first of a planned series of enhancements to the query planner that enable it to make better use of sqlite_stat2 histograms when the table has many repeated values. check-in: 2cd374cd user: drh tags: stat2-enhancement
2011-01-19
21:58
Comment improvements in pcache1.c. No changes to code. check-in: 9660a0a2 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

  2197   2197     bestOrClauseIndex(pParse, pWC, pSrc, notReady, notValid, pOrderBy, pCost);
  2198   2198   }
  2199   2199   #endif /* SQLITE_OMIT_VIRTUALTABLE */
  2200   2200   
  2201   2201   /*
  2202   2202   ** Argument pIdx is a pointer to an index structure that has an array of
  2203   2203   ** SQLITE_INDEX_SAMPLES evenly spaced samples of the first indexed column
  2204         -** stored in Index.aSample. The domain of values stored in said column
  2205         -** may be thought of as divided into (SQLITE_INDEX_SAMPLES+1) regions.
  2206         -** Region 0 contains all values smaller than the first sample value. Region
  2207         -** 1 contains values larger than or equal to the value of the first sample,
  2208         -** but smaller than the value of the second. And so on.
         2204  +** stored in Index.aSample. These samples divide the domain of values stored
         2205  +** the index into (SQLITE_INDEX_SAMPLES+1) regions.
         2206  +** Region 0 contains all values less than the first sample value. Region
         2207  +** 1 contains values between the first and second samples.  Region 2 contains
         2208  +** values between samples 2 and 3.  And so on.  Region SQLITE_INDEX_SAMPLES
         2209  +** contains values larger than the last sample.
         2210  +**
         2211  +** If the index contains many duplicates of a single value, then it is
         2212  +** possible that two or more adjacent samples can hold the same value.
         2213  +** When that is the case, the smallest possible region code is returned
         2214  +** when roundUp is false and the largest possible region code is returned
         2215  +** when roundUp is true.
  2209   2216   **
  2210   2217   ** If successful, this function determines which of the regions value 
  2211   2218   ** pVal lies in, sets *piRegion to the region index (a value between 0
  2212   2219   ** and SQLITE_INDEX_SAMPLES+1, inclusive) and returns SQLITE_OK.
  2213   2220   ** Or, if an OOM occurs while converting text values between encodings,
  2214   2221   ** SQLITE_NOMEM is returned and *piRegion is undefined.
  2215   2222   */
  2216   2223   #ifdef SQLITE_ENABLE_STAT2
  2217   2224   static int whereRangeRegion(
  2218   2225     Parse *pParse,              /* Database connection */
  2219   2226     Index *pIdx,                /* Index to consider domain of */
  2220   2227     sqlite3_value *pVal,        /* Value to consider */
         2228  +  int roundUp,                /* Return largest valid region if true */
  2221   2229     int *piRegion               /* OUT: Region of domain in which value lies */
  2222   2230   ){
         2231  +  assert( roundUp==0 || roundUp==1 );
  2223   2232     if( ALWAYS(pVal) ){
  2224   2233       IndexSample *aSample = pIdx->aSample;
  2225   2234       int i = 0;
  2226   2235       int eType = sqlite3_value_type(pVal);
  2227   2236   
  2228   2237       if( eType==SQLITE_INTEGER || eType==SQLITE_FLOAT ){
  2229   2238         double r = sqlite3_value_double(pVal);
  2230   2239         for(i=0; i<SQLITE_INDEX_SAMPLES; i++){
  2231   2240           if( aSample[i].eType==SQLITE_NULL ) continue;
  2232         -        if( aSample[i].eType>=SQLITE_TEXT || aSample[i].u.r>r ) break;
         2241  +        if( aSample[i].eType>=SQLITE_TEXT ) break;
         2242  +        if( roundUp ){
         2243  +          if( aSample[i].u.r>r ) break;
         2244  +        }else{
         2245  +          if( aSample[i].u.r>=r ) break;
         2246  +        }
  2233   2247         }
  2234   2248       }else{ 
  2235   2249         sqlite3 *db = pParse->db;
  2236   2250         CollSeq *pColl;
  2237   2251         const u8 *z;
  2238   2252         int n;
  2239   2253   
................................................................................
  2256   2270             return SQLITE_NOMEM;
  2257   2271           }
  2258   2272           assert( z && pColl && pColl->xCmp );
  2259   2273         }
  2260   2274         n = sqlite3ValueBytes(pVal, pColl->enc);
  2261   2275   
  2262   2276         for(i=0; i<SQLITE_INDEX_SAMPLES; i++){
  2263         -        int r;
         2277  +        int c;
  2264   2278           int eSampletype = aSample[i].eType;
  2265   2279           if( eSampletype==SQLITE_NULL || eSampletype<eType ) continue;
  2266   2280           if( (eSampletype!=eType) ) break;
  2267   2281   #ifndef SQLITE_OMIT_UTF16
  2268   2282           if( pColl->enc!=SQLITE_UTF8 ){
  2269   2283             int nSample;
  2270   2284             char *zSample = sqlite3Utf8to16(
  2271   2285                 db, pColl->enc, aSample[i].u.z, aSample[i].nByte, &nSample
  2272   2286             );
  2273   2287             if( !zSample ){
  2274   2288               assert( db->mallocFailed );
  2275   2289               return SQLITE_NOMEM;
  2276   2290             }
  2277         -          r = pColl->xCmp(pColl->pUser, nSample, zSample, n, z);
         2291  +          c = pColl->xCmp(pColl->pUser, nSample, zSample, n, z);
  2278   2292             sqlite3DbFree(db, zSample);
  2279   2293           }else
  2280   2294   #endif
  2281   2295           {
  2282         -          r = pColl->xCmp(pColl->pUser, aSample[i].nByte, aSample[i].u.z, n, z);
         2296  +          c = pColl->xCmp(pColl->pUser, aSample[i].nByte, aSample[i].u.z, n, z);
  2283   2297           }
  2284         -        if( r>0 ) break;
         2298  +        if( c-roundUp>=0 ) break;
  2285   2299         }
  2286   2300       }
  2287   2301   
  2288   2302       assert( i>=0 && i<=SQLITE_INDEX_SAMPLES );
  2289   2303       *piRegion = i;
  2290   2304     }
  2291   2305     return SQLITE_OK;
................................................................................
  2382   2396   
  2383   2397     if( nEq==0 && p->aSample ){
  2384   2398       sqlite3_value *pLowerVal = 0;
  2385   2399       sqlite3_value *pUpperVal = 0;
  2386   2400       int iEst;
  2387   2401       int iLower = 0;
  2388   2402       int iUpper = SQLITE_INDEX_SAMPLES;
         2403  +    int roundUpUpper;
         2404  +    int roundUpLower;
  2389   2405       u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity;
  2390   2406   
  2391   2407       if( pLower ){
  2392   2408         Expr *pExpr = pLower->pExpr->pRight;
  2393   2409         rc = valueFromExpr(pParse, pExpr, aff, &pLowerVal);
         2410  +      assert( pLower->eOperator==WO_GT || pLower->eOperator==WO_GE );
         2411  +      roundUpLower = (pLower->eOperator==WO_GT) ?1:0;
  2394   2412       }
  2395   2413       if( rc==SQLITE_OK && pUpper ){
  2396   2414         Expr *pExpr = pUpper->pExpr->pRight;
  2397   2415         rc = valueFromExpr(pParse, pExpr, aff, &pUpperVal);
         2416  +      assert( pUpper->eOperator==WO_LT || pUpper->eOperator==WO_LE );
         2417  +      roundUpUpper = (pUpper->eOperator==WO_LE) ?1:0;
  2398   2418       }
  2399   2419   
  2400   2420       if( rc!=SQLITE_OK || (pLowerVal==0 && pUpperVal==0) ){
  2401   2421         sqlite3ValueFree(pLowerVal);
  2402   2422         sqlite3ValueFree(pUpperVal);
  2403   2423         goto range_est_fallback;
  2404   2424       }else if( pLowerVal==0 ){
  2405         -      rc = whereRangeRegion(pParse, p, pUpperVal, &iUpper);
         2425  +      rc = whereRangeRegion(pParse, p, pUpperVal, roundUpUpper, &iUpper);
  2406   2426         if( pLower ) iLower = iUpper/2;
  2407   2427       }else if( pUpperVal==0 ){
  2408         -      rc = whereRangeRegion(pParse, p, pLowerVal, &iLower);
         2428  +      rc = whereRangeRegion(pParse, p, pLowerVal, roundUpLower, &iLower);
  2409   2429         if( pUpper ) iUpper = (iLower + SQLITE_INDEX_SAMPLES + 1)/2;
  2410   2430       }else{
  2411         -      rc = whereRangeRegion(pParse, p, pUpperVal, &iUpper);
         2431  +      rc = whereRangeRegion(pParse, p, pUpperVal, roundUpUpper, &iUpper);
  2412   2432         if( rc==SQLITE_OK ){
  2413         -        rc = whereRangeRegion(pParse, p, pLowerVal, &iLower);
         2433  +        rc = whereRangeRegion(pParse, p, pLowerVal, roundUpLower, &iLower);
  2414   2434         }
  2415   2435       }
  2416   2436   
  2417   2437       iEst = iUpper - iLower;
  2418   2438       testcase( iEst==SQLITE_INDEX_SAMPLES );
  2419   2439       assert( iEst<=SQLITE_INDEX_SAMPLES );
  2420   2440       if( iEst<1 ){
  2421         -      iEst = 1;
         2441  +      *piEst = 50/SQLITE_INDEX_SAMPLES;
         2442  +    }else{
         2443  +      *piEst = (iEst*100)/SQLITE_INDEX_SAMPLES;
  2422   2444       }
  2423         -
  2424   2445       sqlite3ValueFree(pLowerVal);
  2425   2446       sqlite3ValueFree(pUpperVal);
  2426         -    *piEst = (iEst * 100)/SQLITE_INDEX_SAMPLES;
  2427   2447       return rc;
  2428   2448     }
  2429   2449   range_est_fallback:
  2430   2450   #else
  2431   2451     UNUSED_PARAMETER(pParse);
  2432   2452     UNUSED_PARAMETER(p);
  2433   2453     UNUSED_PARAMETER(nEq);

Changes to test/analyze2.test.

   150    150     SELECT * FROM t1 WHERE x BETWEEN 100 AND 500 AND y BETWEEN 400 AND 700
   151    151   } {
   152    152     0 0 0 {SEARCH TABLE t1 USING INDEX t1_y (y>? AND y<?) (~75 rows)}
   153    153   }
   154    154   do_eqp_test 2.7 {
   155    155     SELECT * FROM t1 WHERE x BETWEEN -400 AND -300 AND y BETWEEN 100 AND 300
   156    156   } {
   157         -  0 0 0 {SEARCH TABLE t1 USING INDEX t1_x (x>? AND x<?) (~25 rows)}
          157  +  0 0 0 {SEARCH TABLE t1 USING INDEX t1_x (x>? AND x<?) (~12 rows)}
   158    158   }
   159    159   do_eqp_test 2.8 {
   160    160     SELECT * FROM t1 WHERE x BETWEEN 100 AND 300 AND y BETWEEN -400 AND -300
   161    161   } {
   162         -  0 0 0 {SEARCH TABLE t1 USING INDEX t1_y (y>? AND y<?) (~25 rows)}
          162  +  0 0 0 {SEARCH TABLE t1 USING INDEX t1_y (y>? AND y<?) (~12 rows)}
   163    163   }
   164    164   do_eqp_test 2.9 {
   165    165     SELECT * FROM t1 WHERE x BETWEEN 500 AND 100 AND y BETWEEN 100 AND 300
   166    166   } {
   167         -  0 0 0 {SEARCH TABLE t1 USING INDEX t1_x (x>? AND x<?) (~25 rows)}
          167  +  0 0 0 {SEARCH TABLE t1 USING INDEX t1_x (x>? AND x<?) (~12 rows)}
   168    168   }
   169    169   do_eqp_test 2.10 {
   170    170     SELECT * FROM t1 WHERE x BETWEEN 100 AND 300 AND y BETWEEN 500 AND 100
   171    171   } {
   172         -  0 0 0 {SEARCH TABLE t1 USING INDEX t1_y (y>? AND y<?) (~25 rows)}
          172  +  0 0 0 {SEARCH TABLE t1 USING INDEX t1_y (y>? AND y<?) (~12 rows)}
   173    173   }
   174    174   
   175    175   do_test analyze2-3.1 {
   176    176     set alphabet [list a b c d e f g h i j]
   177    177     execsql BEGIN
   178    178     for {set i 0} {$i < 1000} {incr i} {
   179    179       set str    [lindex $alphabet [expr ($i/100)%10]] 
................................................................................
   203    203     SELECT * FROM t1 WHERE x BETWEEN 100 AND 500 AND y BETWEEN 'a' AND 'b'
   204    204   } {
   205    205     0 0 0 {SEARCH TABLE t1 USING INDEX t1_y (y>? AND y<?) (~50 rows)}
   206    206   }
   207    207   do_eqp_test 3.4 {
   208    208     SELECT * FROM t1 WHERE x BETWEEN 100 AND 400 AND y BETWEEN 'a' AND 'h'
   209    209   } {
   210         -  0 0 0 {SEARCH TABLE t1 USING INDEX t1_x (x>? AND x<?) (~50 rows)}
          210  +  0 0 0 {SEARCH TABLE t1 USING INDEX t1_x (x>? AND x<?) (~100 rows)}
   211    211   }
   212    212   do_eqp_test 3.5 {
   213    213     SELECT * FROM t1 WHERE x<'a' AND y>'h'
   214    214   } {
   215    215     0 0 0 {SEARCH TABLE t1 USING INDEX t1_y (y>?) (~66 rows)}
   216    216   }
   217    217   do_eqp_test 3.6 {
................................................................................
   412    412   do_test analyze2-6.2.2 {
   413    413     db cache flush
   414    414     execsql ANALYZE
   415    415     eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
   416    416           t5.a>1 AND t5.a<15 AND
   417    417           t6.a>1
   418    418     }
   419         -} {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~2 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
          419  +} {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~1 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
   420    420   do_test analyze2-6.2.3 {
   421    421     sqlite3 db test.db
   422    422     eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
   423    423           t5.a>1 AND t5.a<15 AND
   424    424           t6.a>1
   425    425     }
   426         -} {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~2 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
          426  +} {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~1 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
   427    427   do_test analyze2-6.2.4 {
   428    428     execsql { 
   429    429       PRAGMA writable_schema = 1;
   430    430       DELETE FROM sqlite_master WHERE tbl_name = 'sqlite_stat1';
   431    431     }
   432    432     sqlite3 db test.db
   433    433     eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
................................................................................
   453    453     }
   454    454     sqlite3 db test.db
   455    455     execsql ANALYZE
   456    456     eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
   457    457           t5.a>1 AND t5.a<15 AND
   458    458           t6.a>1
   459    459     }
   460         -} {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~2 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
          460  +} {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~1 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
   461    461   
   462    462   #--------------------------------------------------------------------
   463    463   # These tests, analyze2-7.*, test that the sqlite_stat2 functionality
   464    464   # works in shared-cache mode. Note that these tests reuse the database
   465    465   # created for the analyze2-6.* tests.
   466    466   #
   467    467   ifcapable shared_cache {
................................................................................
   497    497     } {20}
   498    498   
   499    499     do_test analyze2-7.5 {
   500    500       eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
   501    501             t5.a>1 AND t5.a<15 AND
   502    502             t6.a>1
   503    503       } db1
   504         -  } {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~2 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
          504  +  } {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~1 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
   505    505     do_test analyze2-7.6 {
   506    506       incr_schema_cookie test.db
   507    507       execsql { SELECT * FROM sqlite_master } db2
   508    508       eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
   509    509             t5.a>1 AND t5.a<15 AND
   510    510             t6.a>1
   511    511       } db2
   512         -  } {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~2 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
          512  +  } {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~1 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
   513    513     do_test analyze2-7.7 {
   514    514       incr_schema_cookie test.db
   515    515       execsql { SELECT * FROM sqlite_master } db1
   516    516       eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
   517    517             t5.a>1 AND t5.a<15 AND
   518    518             t6.a>1
   519    519       } db1
   520         -  } {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~2 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
          520  +  } {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~1 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
   521    521   
   522    522     do_test analyze2-7.8 {
   523    523       execsql { DELETE FROM sqlite_stat2 } db2
   524    524       execsql { SELECT * FROM sqlite_master } db1
   525    525       eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
   526    526             t5.a>1 AND t5.a<15 AND
   527    527             t6.a>1
   528    528       } db1
   529         -  } {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~2 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
          529  +  } {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~1 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
   530    530     do_test analyze2-7.9 {
   531    531       execsql { SELECT * FROM sqlite_master } db2
   532    532       eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
   533    533             t5.a>1 AND t5.a<15 AND
   534    534             t6.a>1
   535    535       } db2
   536         -  } {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~2 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
          536  +  } {0 0 1 {SEARCH TABLE t6 USING COVERING INDEX t6i (a>?) (~1 rows)} 0 1 0 {SEARCH TABLE t5 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}}
   537    537   
   538    538     do_test analyze2-7.10 {
   539    539       incr_schema_cookie test.db
   540    540       execsql { SELECT * FROM sqlite_master } db1
   541    541       eqp { SELECT * FROM t5,t6 WHERE t5.rowid=t6.rowid AND 
   542    542             t5.a>1 AND t5.a<15 AND
   543    543             t6.a>1

Added test/analyze5.test.

            1  +# 2011 January 19
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#***********************************************************************
           11  +#
           12  +# This file implements tests for SQLite library.  The focus of the tests
           13  +# in this file is the use of the sqlite_stat2 histogram data on tables
           14  +# with many repeated values and only a few distinct values.
           15  +#
           16  +
           17  +set testdir [file dirname $argv0]
           18  +source $testdir/tester.tcl
           19  +
           20  +ifcapable !stat2 {
           21  +  finish_test
           22  +  return
           23  +}
           24  +
           25  +set testprefix analyze5
           26  +
           27  +proc eqp {sql {db db}} {
           28  +  uplevel execsql [list "EXPLAIN QUERY PLAN $sql"] $db
           29  +}
           30  +
           31  +do_test analyze5-1.0 {
           32  +  execsql { CREATE TABLE t1(x INTEGER PRIMARY KEY, y, z) }
           33  +  for {set i 0} {$i < 1000} {incr i} {
           34  +    set j [expr {$i>=25 && $i<=50}]
           35  +    set k [expr {($i>=400) + ($i>=700) + ($i>=875)}]
           36  +    execsql { INSERT INTO t1 VALUES($i,$j,$k) }
           37  +  }
           38  +  execsql { 
           39  +    CREATE INDEX t1y ON t1(y);
           40  +    CREATE INDEX t1z ON t1(z);
           41  +    ANALYZE;
           42  +    SELECT * FROM sqlite_stat2 ORDER BY 1, 2, 3;
           43  +  }
           44  +} [list t1 t1y 0 0 \
           45  +        t1 t1y 1 0 \
           46  +        t1 t1y 2 0 \
           47  +        t1 t1y 3 0 \
           48  +        t1 t1y 4 0 \
           49  +        t1 t1y 5 0 \
           50  +        t1 t1y 6 0 \
           51  +        t1 t1y 7 0 \
           52  +        t1 t1y 8 0 \
           53  +        t1 t1y 9 0 \
           54  +        t1 t1z 0 0 \
           55  +        t1 t1z 1 0 \
           56  +        t1 t1z 2 0 \
           57  +        t1 t1z 3 0 \
           58  +        t1 t1z 4 1 \
           59  +        t1 t1z 5 1 \
           60  +        t1 t1z 6 1 \
           61  +        t1 t1z 7 2 \
           62  +        t1 t1z 8 2 \
           63  +        t1 t1z 9 3]
           64  +
           65  +# Verify that range queries generate the correct row count estimates
           66  +#
           67  +foreach {testid where rows} {
           68  +  1  {z>=0 AND z<=0}     400
           69  +  2  {z>=1 AND z<=1}     300
           70  +  3  {z>=2 AND z<=2}     200
           71  +  4  {z>=3 AND z<=3}     100
           72  +  5  {z>=4 AND z<=4}      50
           73  +  6  {z>=-1 AND z<=-1}    50
           74  +  7  {z>1 AND z<3}       200
           75  +  8  {z>0 AND z<100}     600
           76  +  9  {z>=1 AND z<100}    600
           77  + 10  {z>1 AND z<100}     300
           78  + 11  {z>=2 AND z<100}    300
           79  + 12  {z>2 AND z<100}     100
           80  + 13  {z>=3 AND z<100}    100
           81  + 14  {z>3 AND z<100}      50
           82  + 15  {z>=4 AND z<100}     50
           83  + 16  {z>=-100 AND z<=-1}  50
           84  + 17  {z>=-100 AND z<=0}  400
           85  + 18  {z>=-100 AND z<0}    50
           86  + 19  {z>=-100 AND z<=1}  700
           87  + 20  {z>=-100 AND z<2}   700
           88  + 21  {z>=-100 AND z<=2}  900
           89  + 22  {z>=-100 AND z<3}   900
           90  +
           91  + 31  {z>=0.0 AND z<=0.0}   400
           92  + 32  {z>=1.0 AND z<=1.0}   300
           93  + 33  {z>=2.0 AND z<=2.0}   200
           94  + 34  {z>=3.0 AND z<=3.0}   100
           95  + 35  {z>=4.0 AND z<=4.0}    50
           96  + 36  {z>=-1.0 AND z<=-1.0}  50
           97  + 37  {z>1.5 AND z<3.0}     200
           98  + 38  {z>0.5 AND z<100}     600
           99  + 39  {z>=1.0 AND z<100}    600
          100  + 40  {z>1.5 AND z<100}     300
          101  + 41  {z>=2.0 AND z<100}    300
          102  + 42  {z>2.1 AND z<100}     100
          103  + 43  {z>=3.0 AND z<100}    100
          104  + 44  {z>3.2 AND z<100}      50
          105  + 45  {z>=4.0 AND z<100}     50
          106  + 46  {z>=-100 AND z<=-1.0}  50
          107  + 47  {z>=-100 AND z<=0.0}  400
          108  + 48  {z>=-100 AND z<0.0}    50
          109  + 49  {z>=-100 AND z<=1.0}  700
          110  + 50  {z>=-100 AND z<2.0}   700
          111  + 51  {z>=-100 AND z<=2.0}  900
          112  + 52  {z>=-100 AND z<3.0}   900
          113  +
          114  +} {
          115  +  do_test analyze5-1.$testid {
          116  +    eqp "SELECT * FROM t1 WHERE $where"
          117  +  } [format {0 0 0 {SEARCH TABLE t1 USING INDEX t1z (z>? AND z<?) (~%d rows)}} \
          118  +       $rows]
          119  +}
          120  +
          121  +# Change the table values from integer to floating point and then
          122  +# repeat the same sequence of tests.  We should get the same results.
          123  +#
          124  +do_test analyze5-2.0 {
          125  +  db eval {
          126  +    UPDATE t1 SET z=z+0.0;
          127  +    ANALYZE;
          128  +    SELECT sample FROM sqlite_stat2 WHERE idx='t1z' ORDER BY sampleno;
          129  +  }
          130  +} {0.0 0.0 0.0 0.0 1.0 1.0 1.0 2.0 2.0 3.0}
          131  +foreach {testid where rows} {
          132  +  1  {z>=0 AND z<=0}     400
          133  +  2  {z>=1 AND z<=1}     300
          134  +  3  {z>=2 AND z<=2}     200
          135  +  4  {z>=3 AND z<=3}     100
          136  +  5  {z>=4 AND z<=4}      50
          137  +  6  {z>=-1 AND z<=-1}    50
          138  +  7  {z>1 AND z<3}       200
          139  +  8  {z>0 AND z<100}     600
          140  +  9  {z>=1 AND z<100}    600
          141  + 10  {z>1 AND z<100}     300
          142  + 11  {z>=2 AND z<100}    300
          143  + 12  {z>2 AND z<100}     100
          144  + 13  {z>=3 AND z<100}    100
          145  + 14  {z>3 AND z<100}      50
          146  + 15  {z>=4 AND z<100}     50
          147  + 16  {z>=-100 AND z<=-1}  50
          148  + 17  {z>=-100 AND z<=0}  400
          149  + 18  {z>=-100 AND z<0}    50
          150  + 19  {z>=-100 AND z<=1}  700
          151  + 20  {z>=-100 AND z<2}   700
          152  + 21  {z>=-100 AND z<=2}  900
          153  + 22  {z>=-100 AND z<3}   900
          154  +
          155  + 31  {z>=0.0 AND z<=0.0}   400
          156  + 32  {z>=1.0 AND z<=1.0}   300
          157  + 33  {z>=2.0 AND z<=2.0}   200
          158  + 34  {z>=3.0 AND z<=3.0}   100
          159  + 35  {z>=4.0 AND z<=4.0}    50
          160  + 36  {z>=-1.0 AND z<=-1.0}  50
          161  + 37  {z>1.5 AND z<3.0}     200
          162  + 38  {z>0.5 AND z<100}     600
          163  + 39  {z>=1.0 AND z<100}    600
          164  + 40  {z>1.5 AND z<100}     300
          165  + 41  {z>=2.0 AND z<100}    300
          166  + 42  {z>2.1 AND z<100}     100
          167  + 43  {z>=3.0 AND z<100}    100
          168  + 44  {z>3.2 AND z<100}      50
          169  + 45  {z>=4.0 AND z<100}     50
          170  + 46  {z>=-100 AND z<=-1.0}  50
          171  + 47  {z>=-100 AND z<=0.0}  400
          172  + 48  {z>=-100 AND z<0.0}    50
          173  + 49  {z>=-100 AND z<=1.0}  700
          174  + 50  {z>=-100 AND z<2.0}   700
          175  + 51  {z>=-100 AND z<=2.0}  900
          176  + 52  {z>=-100 AND z<3.0}   900
          177  +} {
          178  +  do_test analyze5-2.$testid {
          179  +    eqp "SELECT * FROM t1 WHERE $where"
          180  +  } [format {0 0 0 {SEARCH TABLE t1 USING INDEX t1z (z>? AND z<?) (~%d rows)}} \
          181  +       $rows]
          182  +}
          183  +
          184  +# Repeat the same range query tests using TEXT columns.
          185  +#
          186  +do_test analyze5-3.0 {
          187  +  db eval {
          188  +    UPDATE t1 SET y=CASE z WHEN 0 THEN 'alpha' WHEN 1 THEN 'bravo'
          189  +                           WHEN 2 THEN 'charlie' ELSE 'delta' END;
          190  +    ANALYZE;
          191  +    SELECT sample FROM sqlite_stat2 WHERE idx='t1y' ORDER BY sampleno;
          192  +  }
          193  +} {alpha alpha alpha alpha bravo bravo bravo charlie charlie delta}
          194  +foreach {testid where rows} {
          195  +  1  {y>='alpha' AND y<='alpha'}     400
          196  +  2  {y>='bravo' AND y<='bravo'}     300
          197  +  3  {y>='charlie' AND y<='charlie'} 200
          198  +  4  {y>='delta' AND y<='delta'}     100
          199  +  5  {y>='echo' AND y<='echo'}        50
          200  +  6  {y>='' AND y<=''}                50
          201  +  7  {y>'bravo' AND y<'delta'}       200
          202  +  8  {y>'alpha' AND y<'zzz'}         600
          203  +  9  {y>='bravo' AND y<'zzz'}        600
          204  + 10  {y>'bravo' AND y<'zzz'}         300
          205  + 11  {y>='charlie' AND y<'zzz'}      300
          206  + 12  {y>'charlie' AND y<'zzz'}       100
          207  + 13  {y>='delta' AND y<'zzz'}        100
          208  + 14  {y>'delta' AND y<'zzz'}          50
          209  + 15  {y>='echo' AND y<'zzz'}          50
          210  + 16  {y>=0 AND y<=''}                 50
          211  + 17  {y>=0 AND y<='alpha'}           400
          212  + 18  {y>=0 AND y<'alpha'}             50
          213  + 19  {y>=0 AND y<='bravo'}           700
          214  + 20  {y>=0 AND y<'charlie'}          700
          215  + 21  {y>=0 AND y<='charlie'}         900
          216  + 22  {y>=0 AND y<'delta'}            900
          217  +} {
          218  +  do_test analyze5-3.$testid {
          219  +    eqp "SELECT * FROM t1 WHERE $where"
          220  +  } [format {0 0 0 {SEARCH TABLE t1 USING INDEX t1y (y>? AND y<?) (~%d rows)}} \
          221  +       $rows]
          222  +}
          223  +
          224  +
          225  +finish_test