/ Check-in [ae9a42b2]
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:Adjust skip-scan cost estimates slightly so that a full table scan is preferred over a skip-scan to a column with only two distinct values.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: ae9a42b268ad3f7d21a5813bb931e795c6917014
User & Date: drh 2014-09-23 01:40:59
Context
2014-09-23
18:30
Add the "multiplex_truncate" PRAGMA to the multiplexor extension, for querying and setting the truncate flag on a database connection. check-in: d2962a5f user: drh tags: trunk
01:40
Adjust skip-scan cost estimates slightly so that a full table scan is preferred over a skip-scan to a column with only two distinct values. check-in: ae9a42b2 user: drh tags: trunk
2014-09-22
20:38
Fix to payload size overflow detection in the cellSizePtr() change of the previous check-in. check-in: 76097440 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

4355
4356
4357
4358
4359
4360
4361
4362
4363
4364
4365
4366



4367
4368
4369
4370
4371
4372
4373
    pNew->u.btree.nEq++;
    pNew->u.btree.nSkip++;
    pNew->aLTerm[pNew->nLTerm++] = 0;
    pNew->wsFlags |= WHERE_SKIPSCAN;
    nIter = pProbe->aiRowLogEst[saved_nEq] - pProbe->aiRowLogEst[saved_nEq+1];
    if( pTerm ){
      /* TUNING:  When estimating skip-scan for a term that is also indexable,
      ** increase the cost of the skip-scan by 2x, to make it a little less
      ** desirable than the regular index lookup. */
      nIter += 10;  assert( 10==sqlite3LogEst(2) );
    }
    pNew->nOut -= nIter;



    whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nIter + nInMul);
    pNew->nOut = saved_nOut;
    pNew->u.btree.nEq = saved_nEq;
    pNew->u.btree.nSkip = saved_nSkip;
  }
  for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){
    u16 eOp = pTerm->eOperator;   /* Shorthand for pTerm->eOperator */







|




>
>
>







4355
4356
4357
4358
4359
4360
4361
4362
4363
4364
4365
4366
4367
4368
4369
4370
4371
4372
4373
4374
4375
4376
    pNew->u.btree.nEq++;
    pNew->u.btree.nSkip++;
    pNew->aLTerm[pNew->nLTerm++] = 0;
    pNew->wsFlags |= WHERE_SKIPSCAN;
    nIter = pProbe->aiRowLogEst[saved_nEq] - pProbe->aiRowLogEst[saved_nEq+1];
    if( pTerm ){
      /* TUNING:  When estimating skip-scan for a term that is also indexable,
      ** multiply the cost of the skip-scan by 2.0, to make it a little less
      ** desirable than the regular index lookup. */
      nIter += 10;  assert( 10==sqlite3LogEst(2) );
    }
    pNew->nOut -= nIter;
    /* TUNING:  Because uncertainties in the estimates for skip-scan queries,
    ** add a 1.375 fudge factor to make skip-scan slightly less likely. */
    nIter += 5;
    whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nIter + nInMul);
    pNew->nOut = saved_nOut;
    pNew->u.btree.nEq = saved_nEq;
    pNew->u.btree.nSkip = saved_nSkip;
  }
  for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){
    u16 eOp = pTerm->eOperator;   /* Shorthand for pTerm->eOperator */

Changes to test/skipscan1.test.

241
242
243
244
245
246
247


248
























249
250
} {}
db cache flush
do_execsql_test skipscan1-5.3 {
  EXPLAIN QUERY PLAN
    SELECT xh, loc FROM t5 WHERE loc >= 'M' AND loc < 'N';
} {/.*COVERING INDEX t5i1 .*/}





























finish_test







>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>


241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
} {}
db cache flush
do_execsql_test skipscan1-5.3 {
  EXPLAIN QUERY PLAN
    SELECT xh, loc FROM t5 WHERE loc >= 'M' AND loc < 'N';
} {/.*COVERING INDEX t5i1 .*/}

# The column used by the skip-scan needs to be sufficiently selective.
# See the private email from Adi Zaimi to drh@sqlite.org on 2014-09-22.
#
db close
forcedelete test.db
sqlite3 db test.db
do_execsql_test skipscan1-6.1 {
  CREATE TABLE t1(a,b,c,d,e,f,g,h varchar(300));
  CREATE INDEX t1ab ON t1(a,b);
  ANALYZE sqlite_master;
  -- Only two distinct values for the skip-scan column.  Skip-scan is not used.
  INSERT INTO sqlite_stat1 VALUES('t1','t1ab','500000 250000 125000');
  ANALYZE sqlite_master;
  EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE b=1;
} {~/ANY/}
do_execsql_test skipscan1-6.2 {
  -- Four distinct values for the skip-scan column.  Skip-scan is used.
  UPDATE sqlite_stat1 SET stat='500000 250000 62500';
  ANALYZE sqlite_master;
  EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE b=1;
} {/ANY.a. AND b=/}
do_execsql_test skipscan1-6.3 {
  -- Two distinct values for the skip-scan column again.  Skip-scan is not used.
  UPDATE sqlite_stat1 SET stat='500000 125000 62500';
  ANALYZE sqlite_master;
  EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE b=1;
} {~/ANY/}

finish_test

Changes to test/skipscan5.test.

104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
...
176
177
178
179
180
181
182
183
184
185
186

  foreach {tn2 q res} {
    1 { c BETWEEN 'd' AND 'e' }       {/*ANY(a) AND ANY(b) AND c>? AND c<?*/}
    2 { c BETWEEN 'b' AND 'r' }       {/*SCAN TABLE t2*/}
    3 { c > 'q' }                     {/*ANY(a) AND ANY(b) AND c>?*/}
    4 { c > 'e' }                     {/*SCAN TABLE t2*/}
    5 { c < 'q' }                     {/*SCAN TABLE t2*/}
    4 { c < 'e' }                     {/*ANY(a) AND ANY(b) AND c<?*/}
  } {
    set sql "EXPLAIN QUERY PLAN SELECT * FROM t2 WHERE $q" 
    do_execsql_test 2.$tn.$tn2 $sql $res
  }

}

................................................................................
  6 "b < 'zzz'"                        {/*SCAN TABLE t3*/}
} {
  set sql "EXPLAIN QUERY PLAN SELECT * FROM t3 WHERE $q" 
  do_execsql_test 3.3.$tn $sql $res
}

finish_test











|







 







<
<
<
<
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
...
176
177
178
179
180
181
182





  foreach {tn2 q res} {
    1 { c BETWEEN 'd' AND 'e' }       {/*ANY(a) AND ANY(b) AND c>? AND c<?*/}
    2 { c BETWEEN 'b' AND 'r' }       {/*SCAN TABLE t2*/}
    3 { c > 'q' }                     {/*ANY(a) AND ANY(b) AND c>?*/}
    4 { c > 'e' }                     {/*SCAN TABLE t2*/}
    5 { c < 'q' }                     {/*SCAN TABLE t2*/}
    6 { c < 'c' }                     {/*ANY(a) AND ANY(b) AND c<?*/}
  } {
    set sql "EXPLAIN QUERY PLAN SELECT * FROM t2 WHERE $q" 
    do_execsql_test 2.$tn.$tn2 $sql $res
  }

}

................................................................................
  6 "b < 'zzz'"                        {/*SCAN TABLE t3*/}
} {
  set sql "EXPLAIN QUERY PLAN SELECT * FROM t3 WHERE $q" 
  do_execsql_test 3.3.$tn $sql $res
}

finish_test