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: |
50f8ea37fb9647c4a9da2c269a4d6f54 |
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
Changes to src/expr.c.
︙ | ︙ | |||
3990 3991 3992 3993 3994 3995 3996 | pWalker->eCode = 1; return WRC_Abort; } return WRC_Continue; } /* | | | | | | 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 | && (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; | | | | 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 | 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 { | | | | 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} |
︙ | ︙ |