/ Check-in [a8ae93f0]
Login

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

Overview
Comment:Do not reduce the number of rows scanned at all for "IS NOT NULL" constraints. Fix a bug in calculating the number of rows visited by scans of partial indicies.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | experimental-costs
Files: files | file ages | folders
SHA1: a8ae93f0cffa116df0ba34d46a53f49d42dace41
User & Date: dan 2014-04-28 20:11:20
Context
2014-04-29
12:01
Fix a test case so that it updates sqlite_stat1 consistently. check-in: 2dc5a0b5 user: dan tags: experimental-costs
2014-04-28
20:11
Do not reduce the number of rows scanned at all for "IS NOT NULL" constraints. Fix a bug in calculating the number of rows visited by scans of partial indicies. check-in: a8ae93f0 user: dan tags: experimental-costs
19:34
The trunk assumes that an open range constraint on an indexed term (col>?) term matches 1/4 of the indexed rows, and that a closed constraint (col BETWEEN ? AND ?) matches 1/64. Change this branch to do the same. check-in: 4047ac75 user: dan tags: experimental-costs
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

  1988   1988   ** has a likelihood of 0.50, and any other term a likelihood of 0.25.
  1989   1989   */
  1990   1990   static LogEst whereRangeAdjust(WhereTerm *pTerm, LogEst nNew){
  1991   1991     LogEst nRet = nNew;
  1992   1992     if( pTerm ){
  1993   1993       if( pTerm->truthProb<=0 ){
  1994   1994         nRet += pTerm->truthProb;
  1995         -    }else if( pTerm->wtFlags & TERM_VNULL ){
  1996         -      nRet -= 10;        assert( 10==sqlite3LogEst(2) );
  1997         -    }else{
         1995  +    }else if( (pTerm->wtFlags & TERM_VNULL)==0 ){
  1998   1996         nRet -= 20;        assert( 20==sqlite3LogEst(4) );
  1999   1997       }
  2000   1998     }
  2001   1999     return nRet;
  2002   2000   }
  2003   2001   
  2004   2002   /*
................................................................................
  2149   2147       }
  2150   2148     }
  2151   2149   #else
  2152   2150     UNUSED_PARAMETER(pParse);
  2153   2151     UNUSED_PARAMETER(pBuilder);
  2154   2152   #endif
  2155   2153     assert( pLower || pUpper );
         2154  +  assert( pUpper==0 || (pUpper->wtFlags & TERM_VNULL)==0 );
  2156   2155     nNew = whereRangeAdjust(pLower, nOut);
  2157   2156     nNew = whereRangeAdjust(pUpper, nNew);
         2157  +
  2158   2158     /* TUNING: If there is both an upper and lower limit, assume the range is
  2159   2159     ** reduced by an additional 75%. This means that, by default, an open-ended
  2160   2160     ** range query (e.g. col > ?) is assumed to match 1/4 of the rows in the
  2161   2161     ** index. While a closed range (e.g. col BETWEEN ? AND ?) is estimated to
  2162   2162     ** match 1/64 of the index. */ 
  2163   2163     if( pLower && pUpper ) nNew -= 20;
         2164  +
  2164   2165     nOut -= (pLower!=0) + (pUpper!=0);
  2165   2166     if( nNew<10 ) nNew = 10;
  2166   2167     if( nNew<nOut ) nOut = nNew;
  2167   2168     pLoop->nOut = (LogEst)nOut;
  2168   2169     return rc;
  2169   2170   }
  2170   2171   
................................................................................
  4442   4443     /* Loop over all indices
  4443   4444     */
  4444   4445     for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext, iSortIdx++){
  4445   4446       if( pProbe->pPartIdxWhere!=0
  4446   4447        && !whereUsablePartialIndex(pNew->iTab, pWC, pProbe->pPartIdxWhere) ){
  4447   4448         continue;  /* Partial index inappropriate for this query */
  4448   4449       }
         4450  +    rSize = pProbe->aiRowLogEst[0];
  4449   4451       pNew->u.btree.nEq = 0;
  4450   4452       pNew->u.btree.nSkip = 0;
  4451   4453       pNew->nLTerm = 0;
  4452   4454       pNew->iSortIdx = 0;
  4453   4455       pNew->rSetup = 0;
  4454   4456       pNew->prereq = mExtra;
  4455   4457       pNew->nOut = rSize;

Changes to test/cost.test.

    84     84   }
    85     85   do_eqp_test 4.3 {
    86     86     SELECT * FROM t1 WHERE likelihood(a=?, 0.067) AND b BETWEEN ? AND ?;
    87     87   } {
    88     88     0 0 0 {SEARCH TABLE t1 USING INDEX i2 (b>? AND b<?)}
    89     89   }
    90     90   
           91  +
           92  +#-------------------------------------------------------------------------
           93  +#
           94  +reset_db
           95  +do_execsql_test 5.1 {
           96  +  CREATE TABLE t2(x, y);
           97  +  CREATE INDEX t2i1 ON t2(x);
           98  +}
           99  +
          100  +do_eqp_test 5.2 {
          101  +  SELECT * FROM t2 ORDER BY x, y;
          102  +} {}
          103  +#exit
          104  +
          105  +# TODO: Check this one out!!
          106  +# set sqlite_where_trace 0xfff
          107  +do_eqp_test 5.3 {
          108  +  SELECT * FROM t2 WHERE x BETWEEN ? AND ? ORDER BY rowid;
          109  +} {}
          110  +#exit
          111  +
          112  +# where7.test, where8.test:
          113  +#
          114  +do_execsql_test 6.1 {
          115  +  CREATE TABLE t3(a INTEGER PRIMARY KEY, b, c);
          116  +  CREATE INDEX t3i1 ON t3(b);
          117  +  CREATE INDEX t3i2 ON t3(c);
          118  +}
          119  +
          120  +#set sqlite_where_trace 0xfff
          121  +# eqp.test
          122  +do_eqp_test 6.2 {
          123  +  SELECT a FROM t3 WHERE (b BETWEEN 2 AND 4) OR c=100 ORDER BY a
          124  +} {
          125  +}
          126  +
          127  +#-------------------------------------------------------------------------
          128  +#
          129  +reset_db
          130  +do_execsql_test 7.1 {
          131  +  CREATE TABLE t1(a INTEGER PRIMARY KEY,b,c,d,e,f,g);
          132  +  CREATE INDEX t1b ON t1(b);
          133  +  CREATE INDEX t1c ON t1(c);
          134  +  CREATE INDEX t1d ON t1(d);
          135  +  CREATE INDEX t1e ON t1(e);
          136  +  CREATE INDEX t1f ON t1(f);
          137  +  CREATE INDEX t1g ON t1(g);
          138  +}
          139  +
          140  +do_eqp_test 7.2 {
          141  +  SELECT a FROM t1
          142  +     WHERE (b>=950 AND b<=1010) OR (b IS NULL AND c NOT NULL)
          143  +  ORDER BY a
          144  +} {
          145  +}
          146  +
          147  +#set sqlite_where_trace 0xfff
          148  +do_eqp_test 7.3 {
          149  +  SELECT rowid FROM t1
          150  +  WHERE (+b IS NULL AND c NOT NULL AND d NOT NULL)
          151  +        OR (b NOT NULL AND c IS NULL AND d NOT NULL)
          152  +        OR (b NOT NULL AND c NOT NULL AND d IS NULL)
          153  +} {}
          154  +#exit
          155  +
          156  +#-------------------------------------------------------------------------
          157  +#
          158  +reset_db
          159  +do_execsql_test 8.1 {
          160  +  CREATE TABLE composer(
          161  +    cid INTEGER PRIMARY KEY,
          162  +    cname TEXT
          163  +  );
          164  +  CREATE TABLE album(
          165  +    aid INTEGER PRIMARY KEY,
          166  +    aname TEXT
          167  +  );
          168  +  CREATE TABLE track(
          169  +    tid INTEGER PRIMARY KEY,
          170  +    cid INTEGER REFERENCES composer,
          171  +    aid INTEGER REFERENCES album,
          172  +    title TEXT
          173  +  );
          174  +  CREATE INDEX track_i1 ON track(cid);
          175  +  CREATE INDEX track_i2 ON track(aid);
          176  +}
          177  +
          178  +do_eqp_test 8.2 {
          179  +  SELECT DISTINCT aname
          180  +    FROM album, composer, track
          181  +   WHERE cname LIKE '%bach%'
          182  +     AND unlikely(composer.cid=track.cid)
          183  +     AND unlikely(album.aid=track.aid);
          184  +} {
          185  +}
    91    186   
    92    187   finish_test
    93    188   
    94    189   
    95    190   

Changes to test/index6.test.

   141    141   
   142    142   # Queries use partial indices as appropriate times.
   143    143   #
   144    144   do_test index6-2.1 {
   145    145     execsql {
   146    146       CREATE TABLE t2(a,b);
   147    147       INSERT INTO t2(a,b) SELECT value, value FROM nums WHERE value<1000;
   148         -    UPDATE t2 SET a=NULL WHERE b%5==0;
          148  +    UPDATE t2 SET a=NULL WHERE b%2==0;
   149    149       CREATE INDEX t2a1 ON t2(a) WHERE a IS NOT NULL;
   150    150       SELECT count(*) FROM t2 WHERE a IS NOT NULL;
   151    151     }
   152         -} {800}
          152  +} {500}
   153    153   do_test index6-2.2 {
   154    154     execsql {
   155    155       EXPLAIN QUERY PLAN
   156    156       SELECT * FROM t2 WHERE a=5;
   157    157     }
   158    158   } {/.* TABLE t2 USING INDEX t2a1 .*/}
   159    159   ifcapable stat4||stat3 {
          160  +  execsql ANALYZE
   160    161     do_test index6-2.3stat4 {
   161    162       execsql {
   162    163         EXPLAIN QUERY PLAN
   163    164         SELECT * FROM t2 WHERE a IS NOT NULL;
   164    165       }
   165    166     } {/.* TABLE t2 USING INDEX t2a1 .*/}
   166    167   } else {