SQLite

Check-in [50f8ea37fb]
Login

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

Overview
Comment:Add test cases and fix a comment.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | improved-index-scan
Files: files | file ages | folders
SHA1: 50f8ea37fb9647c4a9da2c269a4d6f54b10ce96b
User & Date: drh 2016-07-27 19:20:58.611
Context
2016-07-27
19:30
Enhance the query planner cost estimation for index scans to take into account WHERE clause terms that can be computed using only the index and that do not require looking up rows in the original table. This fixes an obscure performance regression that arose when the ORDER BY LIMIT optimization was added by check-in [bf46179d44843]. (check-in: 9e2b268114 user: drh tags: trunk)
19:20
Add test cases and fix a comment. (Closed-Leaf check-in: 50f8ea37fb user: drh tags: improved-index-scan)
18:27
When estimating the cost of an index scan, factor in the cost savings of being able to use the index to evaluate some WHERE clause terms without having to do a table lookup. (check-in: a59b5622f7 user: drh tags: improved-index-scan)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/expr.c.
3990
3991
3992
3993
3994
3995
3996
3997
3998
3999
4000
4001
4002
4003
4004
4005
4006
4007
    pWalker->eCode = 1;
    return WRC_Abort;
  }
  return WRC_Continue;
}

/*
** Determine if an index on table iCur that contains the columns in
** Bitmask m will cover the expression pExpr.  Return true if the index
** does cover the expression and false if the expression references
** table columns that are not found in the index.
**
** An index covering an expression means that the expression can be
** evaluated using only the index and without having to lookup the
** corresponding table entry.
*/
int sqlite3ExprCoveredByIndex(
  Expr *pExpr,        /* The index to be tested */







|
|
|
|







3990
3991
3992
3993
3994
3995
3996
3997
3998
3999
4000
4001
4002
4003
4004
4005
4006
4007
    pWalker->eCode = 1;
    return WRC_Abort;
  }
  return WRC_Continue;
}

/*
** Determine if an index pIdx on table with cursor iCur contains will
** the expression pExpr.  Return true if the index does cover the
** expression and false if the pExpr expression references table columns
** that are not found in the index pIdx.
**
** An index covering an expression means that the expression can be
** evaluated using only the index and without having to lookup the
** corresponding table entry.
*/
int sqlite3ExprCoveredByIndex(
  Expr *pExpr,        /* The index to be tested */
Changes to src/where.c.
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
   && (rc = whereLoopResize(db, pNew, pNew->nLTerm+1))==SQLITE_OK
  ){
    LogEst nIter;
    pNew->u.btree.nEq++;
    pNew->nSkip++;
    pNew->aLTerm[pNew->nLTerm++] = 0;
    pNew->wsFlags |= WHERE_SKIPSCAN;
    nIter = pProbe->aiRowLogEst[saved_nEq] - pProbe->aiRowLogEst[saved_nEq+1];
    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->nSkip = saved_nSkip;
    pNew->wsFlags = saved_wsFlags;
  }








|



|







2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
   && (rc = whereLoopResize(db, pNew, pNew->nLTerm+1))==SQLITE_OK
  ){
    LogEst nIter;
    pNew->u.btree.nEq++;
    pNew->nSkip++;
    pNew->aLTerm[pNew->nLTerm++] = 0;
    pNew->wsFlags |= WHERE_SKIPSCAN;
    nIter = pProbe->aiRowLogEst[saved_nEq]+1 - pProbe->aiRowLogEst[saved_nEq+1];
    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 += 4;
    whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nIter + nInMul);
    pNew->nOut = saved_nOut;
    pNew->u.btree.nEq = saved_nEq;
    pNew->nSkip = saved_nSkip;
    pNew->wsFlags = saved_wsFlags;
  }

Added test/index8.test.
























































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
# 2016-07-27
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# Test cases for ORDER BY and LIMIT on an index scan.
#


set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Performance regression reported at
# http://www.mail-archive.com/sqlite-users@mailinglists.sqlite.org/msg98615.html
#
# Caused by the ORDER BY LIMIT optionation for check-in
# https://sqlite.org/src/info/bf46179d44843769
#
# Fixed on approximately 2016-07-27 by changes that compute a better score
# for index scans by taking into account WHERE clause constraints that can
# be handled by the index and do not require a table lookup.
#
do_execsql_test 1.0 {
  CREATE TABLE t1(a,b,c,d);
  WITH RECURSIVE c(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM c WHERE x<100)
  INSERT INTO t1(a,b,c,d)
     SELECT x/10, x%10, x%19, x FROM c;
  CREATE INDEX t1abc ON t1(a,b,c);
  SELECT * FROM t1 WHERE c=4 ORDER BY a, b LIMIT 2;
} {0 4 4 4 2 3 4 23}

# Prior to the fix, the following EQP would show a table scan and a sort
# rather than an index scan.
#
do_execsql_test 1.0eqp {
  EXPLAIN QUERY PLAN
  SELECT * FROM t1 WHERE c=4 ORDER BY a, b LIMIT 2;
} {/SCAN TABLE t1 USING INDEX t1abc/}

# If we change the index so that it no longer covers the WHERE clause,
# then we should (correctly) revert to using a table scan.
#
do_execsql_test 1.1 {
  DROP INDEX t1abc;
  CREATE INDEX t1abd ON t1(a,b,d);
  SELECT * FROM t1 WHERE c=4 ORDER BY a, b LIMIT 2;
} {0 4 4 4 2 3 4 23}
do_execsql_test 1.1eqp {
  EXPLAIN QUERY PLAN
  SELECT * FROM t1 WHERE c=4 ORDER BY a, b LIMIT 2;
} {~/USING INDEX/}


finish_test
Changes to test/scanstatus.test.
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
do_eqp_test 5.3.1 {
  SELECT count(*) FROM t2 WHERE y = 'j';
} {0 0 0 {SEARCH TABLE t2 USING COVERING INDEX t2xy (ANY(x) AND y=?)}}
do_execsql_test 5.3.2 {
  SELECT count(*) FROM t2 WHERE y = 'j';
} {19}
do_scanstatus_test 5.3.3 { 
  nLoop 1 nVisit 19 nEst 56.0 zName t2xy zExplain
  {SEARCH TABLE t2 USING COVERING INDEX t2xy (ANY(x) AND y=?)}
}

do_eqp_test 5.4.1 {
  SELECT count(*) FROM t1, t2 WHERE y = c;
} {
  0 0 0 {SCAN TABLE t1 USING COVERING INDEX t1bc}
  0 1 1 {SEARCH TABLE t2 USING COVERING INDEX t2xy (ANY(x) AND y=?)}
}
do_execsql_test 5.4.2 {
  SELECT count(*) FROM t1, t2 WHERE y = c;
} {200}
do_scanstatus_test 5.4.3 { 
  nLoop 1 nVisit 10 nEst 10.0 zName t1bc 
  zExplain {SCAN TABLE t1 USING COVERING INDEX t1bc}
  nLoop 10 nVisit 200 nEst 56.0 zName t2xy 
  zExplain {SEARCH TABLE t2 USING COVERING INDEX t2xy (ANY(x) AND y=?)}
}

do_eqp_test 5.5.1 {
  SELECT count(*) FROM t1, t3 WHERE y = c;
} {
  0 0 1 {SCAN TABLE t3} 







|















|







329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
do_eqp_test 5.3.1 {
  SELECT count(*) FROM t2 WHERE y = 'j';
} {0 0 0 {SEARCH TABLE t2 USING COVERING INDEX t2xy (ANY(x) AND y=?)}}
do_execsql_test 5.3.2 {
  SELECT count(*) FROM t2 WHERE y = 'j';
} {19}
do_scanstatus_test 5.3.3 { 
  nLoop 1 nVisit 19 nEst 52.0 zName t2xy zExplain
  {SEARCH TABLE t2 USING COVERING INDEX t2xy (ANY(x) AND y=?)}
}

do_eqp_test 5.4.1 {
  SELECT count(*) FROM t1, t2 WHERE y = c;
} {
  0 0 0 {SCAN TABLE t1 USING COVERING INDEX t1bc}
  0 1 1 {SEARCH TABLE t2 USING COVERING INDEX t2xy (ANY(x) AND y=?)}
}
do_execsql_test 5.4.2 {
  SELECT count(*) FROM t1, t2 WHERE y = c;
} {200}
do_scanstatus_test 5.4.3 { 
  nLoop 1 nVisit 10 nEst 10.0 zName t1bc 
  zExplain {SCAN TABLE t1 USING COVERING INDEX t1bc}
  nLoop 10 nVisit 200 nEst 52.0 zName t2xy 
  zExplain {SEARCH TABLE t2 USING COVERING INDEX t2xy (ANY(x) AND y=?)}
}

do_eqp_test 5.5.1 {
  SELECT count(*) FROM t1, t3 WHERE y = c;
} {
  0 0 1 {SCAN TABLE t3}