Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Progress toward using the iScanRatio information on indices. Many tests are still failing. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | index-scan-rate |
Files: | files | file ages | folders |
SHA1: |
6c352edbba85a15ca356b5e131f4b3b2 |
User & Date: | drh 2013-10-04 02:36:19.375 |
Context
2013-10-04
| ||
15:30 | Improved estimates of the relative speed of index scans based on declared datatypes of columns in the table. Add "r" column to PRAGMA index_info, showing the estimated relative scan rate. (check-in: 07462bb605 user: drh tags: index-scan-rate) | |
02:36 | Progress toward using the iScanRatio information on indices. Many tests are still failing. (check-in: 6c352edbba user: drh tags: index-scan-rate) | |
2013-10-03
| ||
19:21 | Experimental branch allowing different postulated scan rates for each index. (check-in: d59d97b0a8 user: drh tags: index-scan-rate) | |
Changes
Changes to src/analyze.c.
︙ | ︙ | |||
1278 1279 1280 1281 1282 1283 1284 | if( pIndex ){ while( z[0] ){ for(i=1; z[i] && z[i]!=' '; i++){} if( i==9 && memcmp(z, "unordered", 9)==0 ){ pIndex->bUnordered = 1; }else if( i>2 && memcmp(z, "r=", 2)==0 && sqlite3GetInt32(z+2, &v32) ){ | | > | > > > > | 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 | if( pIndex ){ while( z[0] ){ for(i=1; z[i] && z[i]!=' '; i++){} if( i==9 && memcmp(z, "unordered", 9)==0 ){ pIndex->bUnordered = 1; }else if( i>2 && memcmp(z, "r=", 2)==0 && sqlite3GetInt32(z+2, &v32) ){ if( v32>=200 ){ v32 = 255; }else if( v32<0 ){ v32 = 0; }else{ v32 = (128*v32)/100; } pIndex->iScanRatio = (u8)v32; } z += i; if( z[0]==' ' ) z++; } } } |
︙ | ︙ |
Changes to src/select.c.
︙ | ︙ | |||
4593 4594 4595 4596 4597 4598 4599 | KeyInfo *pKeyInfo = 0; /* Keyinfo for scanned index */ Index *pBest = 0; /* Best index found so far */ int iRoot = pTab->tnum; /* Root page of scanned b-tree */ sqlite3CodeVerifySchema(pParse, iDb); sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName); | | < < < < < < | > > > | | 4593 4594 4595 4596 4597 4598 4599 4600 4601 4602 4603 4604 4605 4606 4607 4608 4609 4610 4611 4612 4613 4614 4615 4616 4617 4618 4619 4620 4621 4622 | KeyInfo *pKeyInfo = 0; /* Keyinfo for scanned index */ Index *pBest = 0; /* Best index found so far */ int iRoot = pTab->tnum; /* Root page of scanned b-tree */ sqlite3CodeVerifySchema(pParse, iDb); sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName); /* Search for the index that has the lowest scan cost. ** ** (2011-04-15) Do not do a full scan of an unordered index. ** ** In practice the KeyInfo structure will not be used. It is only ** passed to keep OP_OpenRead happy. */ for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){ if( pIdx->bUnordered==0 && pIdx->iScanRatio<128 && (!pBest || pIdx->iScanRatio<pBest->iScanRatio) ){ pBest = pIdx; } } if( pBest ){ iRoot = pBest->tnum; pKeyInfo = sqlite3IndexKeyinfo(pParse, pBest); } /* Open a read-only cursor, execute the OP_Count, close the cursor. */ sqlite3VdbeAddOp3(v, OP_OpenRead, iCsr, iRoot, iDb); if( pKeyInfo ){ |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
4665 4666 4667 4668 4669 4670 4671 | if( pProbe->tnum<=0 ){ /* Integer primary key index */ pNew->wsFlags = WHERE_IPK; /* Full table scan */ pNew->iSortIdx = b ? iSortIdx : 0; /* TUNING: Cost of full table scan is 3*(N + log2(N)). | | | < < > | > | < | | < < < | | 4665 4666 4667 4668 4669 4670 4671 4672 4673 4674 4675 4676 4677 4678 4679 4680 4681 4682 4683 4684 4685 4686 4687 4688 4689 4690 4691 4692 4693 4694 4695 4696 4697 4698 4699 4700 4701 4702 4703 4704 4705 4706 4707 | if( pProbe->tnum<=0 ){ /* Integer primary key index */ pNew->wsFlags = WHERE_IPK; /* Full table scan */ pNew->iSortIdx = b ? iSortIdx : 0; /* TUNING: Cost of full table scan is 3*(N + log2(N)). ** + The extra 4 factor is to encourage the use of indexed lookups ** over full scans. */ pNew->rRun = whereCostAdd(rSize,rLogSize) + 16; whereLoopOutputAdjust(pWC, pNew, pSrc->iCursor); rc = whereLoopInsert(pBuilder, pNew); pNew->nOut = rSize; if( rc ) break; }else{ Bitmask m = pSrc->colUsed & ~columnsInIndex(pProbe); pNew->wsFlags = (m==0) ? (WHERE_IDX_ONLY|WHERE_INDEXED) : WHERE_INDEXED; /* Full scan via index */ if( b || ( m==0 && pProbe->bUnordered==0 && pProbe->iScanRatio<128 && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 && sqlite3GlobalConfig.bUseCis && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan) ) ){ pNew->iSortIdx = b ? iSortIdx : 0; if( m==0 ){ /* TUNING: Cost of a covering index scan is K*(N + log2(N)). ** + The extra factor K of between 1.0 and 3.0 is added to ** encourage the use of indexed lookups. The value of K ** depends on the iScanRatio value for the index. */ pNew->rRun = whereCostAdd(rSize,rLogSize) + pProbe->iScanRatio/9 + 1; }else{ assert( b!=0 ); /* TUNING: Cost of scanning a non-covering index is (N+1)*log2(N) ** which we will simplify to just N*log2(N) */ pNew->rRun = rSize + rLogSize; } whereLoopOutputAdjust(pWC, pNew, pSrc->iCursor); |
︙ | ︙ |
Changes to test/analyze6.test.
︙ | ︙ | |||
26 27 28 29 30 31 32 | proc eqp {sql {db db}} { uplevel execsql [list "EXPLAIN QUERY PLAN $sql"] $db } do_test analyze6-1.0 { db eval { | | | | | | | | 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | proc eqp {sql {db db}} { uplevel execsql [list "EXPLAIN QUERY PLAN $sql"] $db } do_test analyze6-1.0 { db eval { CREATE TABLE cat(x INT, yz TEXT); CREATE UNIQUE INDEX catx ON cat(x); /* Give cat 16 unique integers */ INSERT INTO cat(x) VALUES(1); INSERT INTO cat(x) VALUES(2); INSERT INTO cat(x) SELECT x+2 FROM cat; INSERT INTO cat(x) SELECT x+4 FROM cat; INSERT INTO cat(x) SELECT x+8 FROM cat; CREATE TABLE ev(y INT); CREATE INDEX evy ON ev(y); /* ev will hold 32 copies of 16 integers found in cat */ INSERT INTO ev SELECT x FROM cat; INSERT INTO ev SELECT x FROM cat; INSERT INTO ev SELECT y FROM ev; |
︙ | ︙ |
Changes to test/eqp.test.
︙ | ︙ | |||
29 30 31 32 33 34 35 | # ... # eqp-7.*: "SELECT count(*) FROM tbl" statements (VDBE code OP_Count). # proc det {args} { uplevel do_eqp_test $args } do_execsql_test 1.1 { | | | | | 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | # ... # eqp-7.*: "SELECT count(*) FROM tbl" statements (VDBE code OP_Count). # proc det {args} { uplevel do_eqp_test $args } do_execsql_test 1.1 { CREATE TABLE t1(a INT, b INT, ex TEXT); CREATE INDEX i1 ON t1(a); CREATE INDEX i2 ON t1(b); CREATE TABLE t2(a INT, b INT, ex TEXT); CREATE TABLE t3(a INT, b INT, ex TEXT); } do_eqp_test 1.2 { SELECT * FROM t2, t1 WHERE t1.a=1 OR t1.b=2; } { 0 0 1 {SEARCH TABLE t1 USING INDEX i1 (a=?)} 0 0 1 {SEARCH TABLE t1 USING INDEX i2 (b=?)} |
︙ | ︙ | |||
118 119 120 121 122 123 124 | } #------------------------------------------------------------------------- # Test cases eqp-2.* - tests for single select statements. # drop_all_tables do_execsql_test 2.1 { | | | | 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 | } #------------------------------------------------------------------------- # Test cases eqp-2.* - tests for single select statements. # drop_all_tables do_execsql_test 2.1 { CREATE TABLE t1(x INT, y INT, ex TEXT); CREATE TABLE t2(x INT, y INT, ex TEXT); CREATE INDEX t2i1 ON t2(x); } det 2.2.1 "SELECT DISTINCT min(x), max(x) FROM t1 GROUP BY x ORDER BY 1" { 0 0 0 {SCAN TABLE t1} 0 0 0 {USE TEMP B-TREE FOR GROUP BY} 0 0 0 {USE TEMP B-TREE FOR DISTINCT} |
︙ | ︙ | |||
370 371 372 373 374 375 376 | # drop_all_tables # EVIDENCE-OF: R-47779-47605 sqlite> EXPLAIN QUERY PLAN SELECT a, b # FROM t1 WHERE a=1; # 0|0|0|SCAN TABLE t1 # | | | 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 | # drop_all_tables # EVIDENCE-OF: R-47779-47605 sqlite> EXPLAIN QUERY PLAN SELECT a, b # FROM t1 WHERE a=1; # 0|0|0|SCAN TABLE t1 # do_execsql_test 5.1.0 { CREATE TABLE t1(a INT, b INT, ex TEXT) } det 5.1.1 "SELECT a, b FROM t1 WHERE a=1" { 0 0 0 {SCAN TABLE t1} } # EVIDENCE-OF: R-55852-17599 sqlite> CREATE INDEX i1 ON t1(a); # sqlite> EXPLAIN QUERY PLAN SELECT a, b FROM t1 WHERE a=1; # 0|0|0|SEARCH TABLE t1 USING INDEX i1 |
︙ | ︙ | |||
398 399 400 401 402 403 404 | } # EVIDENCE-OF: R-09991-48941 sqlite> EXPLAIN QUERY PLAN # SELECT t1.*, t2.* FROM t1, t2 WHERE t1.a=1 AND t1.b>2; # 0|0|0|SEARCH TABLE t1 USING COVERING INDEX i2 (a=? AND b>?) # 0|1|1|SCAN TABLE t2 # | | | | | | 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 | } # EVIDENCE-OF: R-09991-48941 sqlite> EXPLAIN QUERY PLAN # SELECT t1.*, t2.* FROM t1, t2 WHERE t1.a=1 AND t1.b>2; # 0|0|0|SEARCH TABLE t1 USING COVERING INDEX i2 (a=? AND b>?) # 0|1|1|SCAN TABLE t2 # do_execsql_test 5.4.0 {CREATE TABLE t2(c INT, d INT, ex TEXT)} det 5.4.1 "SELECT t1.a, t2.c FROM t1, t2 WHERE t1.a=1 AND t1.b>2" { 0 0 0 {SEARCH TABLE t1 USING COVERING INDEX i2 (a=? AND b>?)} 0 1 1 {SCAN TABLE t2} } # EVIDENCE-OF: R-33626-61085 sqlite> EXPLAIN QUERY PLAN # SELECT t1.*, t2.* FROM t2, t1 WHERE t1.a=1 AND t1.b>2; # 0|0|1|SEARCH TABLE t1 USING COVERING INDEX i2 (a=? AND b>?) # 0|1|0|SCAN TABLE t2 # det 5.5 "SELECT t1.a, t2.c FROM t2, t1 WHERE t1.a=1 AND t1.b>2" { 0 0 1 {SEARCH TABLE t1 USING COVERING INDEX i2 (a=? AND b>?)} 0 1 0 {SCAN TABLE t2} } # EVIDENCE-OF: R-04002-25654 sqlite> CREATE INDEX i3 ON t1(b); # sqlite> EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE a=1 OR b=2; # 0|0|0|SEARCH TABLE t1 USING COVERING INDEX i2 (a=?) # 0|0|0|SEARCH TABLE t1 USING INDEX i3 (b=?) # do_execsql_test 5.5.0 {CREATE INDEX i3 ON t1(b)} det 5.6.1 "SELECT a, b FROM t1 WHERE a=1 OR b=2" { 0 0 0 {SEARCH TABLE t1 USING COVERING INDEX i2 (a=?)} 0 0 0 {SEARCH TABLE t1 USING INDEX i3 (b=?)} } # EVIDENCE-OF: R-24577-38891 sqlite> EXPLAIN QUERY PLAN # SELECT c, d FROM t2 ORDER BY c; # 0|0|0|SCAN TABLE t2 |
︙ | ︙ | |||
481 482 483 484 485 486 487 | } # EVIDENCE-OF: R-46219-33846 sqlite> EXPLAIN QUERY PLAN # SELECT * FROM (SELECT * FROM t2 WHERE c=1), t1; # 0|0|0|SEARCH TABLE t2 USING INDEX i4 (c=?) # 0|1|1|SCAN TABLE t1 # | | | 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 | } # EVIDENCE-OF: R-46219-33846 sqlite> EXPLAIN QUERY PLAN # SELECT * FROM (SELECT * FROM t2 WHERE c=1), t1; # 0|0|0|SEARCH TABLE t2 USING INDEX i4 (c=?) # 0|1|1|SCAN TABLE t1 # det 5.11 "SELECT a, b FROM (SELECT * FROM t2 WHERE c=1), t1" { 0 0 0 {SEARCH TABLE t2 USING INDEX i4 (c=?)} 0 1 1 {SCAN TABLE t1 USING COVERING INDEX i2} } # EVIDENCE-OF: R-37879-39987 sqlite> EXPLAIN QUERY PLAN # SELECT a FROM t1 UNION SELECT c FROM t2; # 1|0|0|SCAN TABLE t1 |
︙ | ︙ | |||
559 560 561 562 563 564 565 | #------------------------------------------------------------------------- # The following tests - eqp-7.* - test that queries that use the OP_Count # optimization return something sensible with EQP. # drop_all_tables do_execsql_test 7.0 { | | | | 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 | #------------------------------------------------------------------------- # The following tests - eqp-7.* - test that queries that use the OP_Count # optimization return something sensible with EQP. # drop_all_tables do_execsql_test 7.0 { CREATE TABLE t1(a INT, b INT, ex TEXT); CREATE TABLE t2(a INT, b INT, ex TEXT); CREATE INDEX i1 ON t2(a); } det 7.1 "SELECT count(*) FROM t1" { 0 0 0 {SCAN TABLE t1} } |
︙ | ︙ |