Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Handle virtual tables correctly when using logarithmic costs. Fixes to test cases. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | nextgen-query-plan-logcost |
Files: | files | file ages | folders |
SHA1: |
e612664aa2e24ed5e222be2c7fe16e21 |
User & Date: | drh 2013-06-11 01:50:08.263 |
Context
2013-06-11
| ||
02:32 | Fixes to EXPLAIN QUERY PLAN output. Change weights back to something closer to what they are in legacy. More test case fixes. (Closed-Leaf check-in: 36373b85f9 user: drh tags: nextgen-query-plan-logcost) | |
01:50 | Handle virtual tables correctly when using logarithmic costs. Fixes to test cases. (check-in: e612664aa2 user: drh tags: nextgen-query-plan-logcost) | |
2013-06-10
| ||
23:30 | Fix test cases for the new EXPLAIN QUERY PLAN format. Add the wherecosttest tool. Other fixes to logarithm cost. (check-in: aa580e368e user: drh tags: nextgen-query-plan-logcost) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 | }else{ while( x>255 ){ y += 40; x >>= 4; } while( x>15 ){ y += 10; x >>= 1; } } return a[x&7] + y - 10; } /* ** Prepare a crude estimate of the logarithm of the input value. ** The results need not be exact. This is only used for estimating ** the total cost of performing operations with O(logN) or O(NlogN) ** complexity. Because N is just a guess, it is no great tragedy if ** logN is a little off. */ | > > > > > > > > > > > > > > > > > | 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 | }else{ while( x>255 ){ y += 40; x >>= 4; } while( x>15 ){ y += 10; x >>= 1; } } return a[x&7] + y - 10; } #ifndef SQLITE_OMIT_VIRTUALTABLE /* ** Convert a double (as received from xBestIndex of a virtual table) ** into a WhereCost */ static WhereCost whereCostFromDouble(double x){ u64 a; WhereCost e; assert( sizeof(x)==8 && sizeof(a)==8 ); if( x<=1 ) return 0; if( x<=2000000000 ) return whereCostFromInt((tRowcnt)x); memcpy(&a, &x, 8); e = (a>>52) - 1022; return e*10; } #endif /* SQLITE_OMIT_VIRTUALTABLE */ /* ** Prepare a crude estimate of the logarithm of the input value. ** The results need not be exact. This is only used for estimating ** the total cost of performing operations with O(logN) or O(NlogN) ** complexity. Because N is just a guess, it is no great tragedy if ** logN is a little off. */ |
︙ | ︙ | |||
4084 4085 4086 4087 4088 4089 4090 4091 4092 4093 4094 4095 4096 4097 | && p->u.btree.pIndex==pTemplate->u.btree.pIndex && p->prereq==pTemplate->prereq ){ /* Overwrite an existing WhereLoop with an similar one that uses ** more terms of the index */ pNext = p->pNextLoop; break; }else{ /* pTemplate is not helpful. ** Return without changing or adding anything */ goto whereLoopInsert_noop; } } if( (p->prereq & pTemplate->prereq)==pTemplate->prereq | > > > > > > > > | 4101 4102 4103 4104 4105 4106 4107 4108 4109 4110 4111 4112 4113 4114 4115 4116 4117 4118 4119 4120 4121 4122 | && p->u.btree.pIndex==pTemplate->u.btree.pIndex && p->prereq==pTemplate->prereq ){ /* Overwrite an existing WhereLoop with an similar one that uses ** more terms of the index */ pNext = p->pNextLoop; break; }else if( p->nOut>pTemplate->nOut && p->rSetup==pTemplate->rSetup && p->rRun==pTemplate->rRun ){ /* Overwrite an existing WhereLoop with the same cost but more ** outputs */ pNext = p->pNextLoop; break; }else{ /* pTemplate is not helpful. ** Return without changing or adding anything */ goto whereLoopInsert_noop; } } if( (p->prereq & pTemplate->prereq)==pTemplate->prereq |
︙ | ︙ | |||
4259 4260 4261 4262 4263 4264 4265 | pNew->aLTerm[pNew->nLTerm-2] : 0; } if( pNew->wsFlags & WHERE_COLUMN_RANGE ){ /* Adjust nOut and rRun for STAT3 range values */ WhereCost rDiv; whereRangeScanEst(pParse, pProbe, pNew->u.btree.nEq, pBtm, pTop, &rDiv); | | | 4284 4285 4286 4287 4288 4289 4290 4291 4292 4293 4294 4295 4296 4297 4298 | pNew->aLTerm[pNew->nLTerm-2] : 0; } if( pNew->wsFlags & WHERE_COLUMN_RANGE ){ /* Adjust nOut and rRun for STAT3 range values */ WhereCost rDiv; whereRangeScanEst(pParse, pProbe, pNew->u.btree.nEq, pBtm, pTop, &rDiv); pNew->nOut = saved_nOut>rDiv+10 ? saved_nOut - rDiv : 10; } #ifdef SQLITE_ENABLE_STAT3 if( pNew->u.btree.nEq==1 && pProbe->nSample ){ tRowcnt nOut = 0; if( (pTerm->eOperator & (WO_EQ|WO_ISNULL))!=0 ){ rc = whereEqualScanEst(pParse, pProbe, pTerm->pExpr->pRight, &nOut); }else if( (pTerm->eOperator & WO_IN) |
︙ | ︙ | |||
4478 4479 4480 4481 4482 4483 4484 4485 4486 4487 4488 4489 4490 4491 | /* If there was an INDEXED BY clause, then only that one index is ** considered. */ if( pSrc->pIndex ) break; } return rc; } /* ** Add all WhereLoop objects for a table of the join identified by ** pBuilder->pNew->iTab. That table is guaranteed to be a virtual table. */ static int whereLoopAddVirtual( WhereLoopBuilder *pBuilder, /* WHERE clause information */ Bitmask mExtra /* Extra prerequesites for using this table */ | > | 4503 4504 4505 4506 4507 4508 4509 4510 4511 4512 4513 4514 4515 4516 4517 | /* If there was an INDEXED BY clause, then only that one index is ** considered. */ if( pSrc->pIndex ) break; } return rc; } #ifndef SQLITE_OMIT_VIRTUALTABLE /* ** Add all WhereLoop objects for a table of the join identified by ** pBuilder->pNew->iTab. That table is guaranteed to be a virtual table. */ static int whereLoopAddVirtual( WhereLoopBuilder *pBuilder, /* WHERE clause information */ Bitmask mExtra /* Extra prerequesites for using this table */ |
︙ | ︙ | |||
4565 4566 4567 4568 4569 4570 4571 | } memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint); if( pIdxInfo->needToFreeIdxStr ) sqlite3_free(pIdxInfo->idxStr); pIdxInfo->idxStr = 0; pIdxInfo->idxNum = 0; pIdxInfo->needToFreeIdxStr = 0; pIdxInfo->orderByConsumed = 0; | < | | 4591 4592 4593 4594 4595 4596 4597 4598 4599 4600 4601 4602 4603 4604 4605 | } memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint); if( pIdxInfo->needToFreeIdxStr ) sqlite3_free(pIdxInfo->idxStr); pIdxInfo->idxStr = 0; pIdxInfo->idxNum = 0; pIdxInfo->needToFreeIdxStr = 0; pIdxInfo->orderByConsumed = 0; pIdxInfo->estimatedCost = SQLITE_BIG_DBL / (double)2; rc = vtabBestIndex(pParse, pTab, pIdxInfo); if( rc ) goto whereLoopAddVtab_exit; pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint; pNew->prereq = 0; mxTerm = -1; assert( pNew->nLSlot>=nConstraint ); for(i=0; i<nConstraint; i++) pNew->aLTerm[i] = 0; |
︙ | ︙ | |||
4620 4621 4622 4623 4624 4625 4626 | pNew->u.vtab.idxNum = pIdxInfo->idxNum; pNew->u.vtab.needFree = pIdxInfo->needToFreeIdxStr; pIdxInfo->needToFreeIdxStr = 0; pNew->u.vtab.idxStr = pIdxInfo->idxStr; pNew->u.vtab.isOrdered = (u8)((pIdxInfo->nOrderBy!=0) && pIdxInfo->orderByConsumed); pNew->rSetup = 0; | | > | 4645 4646 4647 4648 4649 4650 4651 4652 4653 4654 4655 4656 4657 4658 4659 4660 4661 4662 4663 4664 4665 4666 4667 4668 4669 4670 4671 4672 4673 4674 | pNew->u.vtab.idxNum = pIdxInfo->idxNum; pNew->u.vtab.needFree = pIdxInfo->needToFreeIdxStr; pIdxInfo->needToFreeIdxStr = 0; pNew->u.vtab.idxStr = pIdxInfo->idxStr; pNew->u.vtab.isOrdered = (u8)((pIdxInfo->nOrderBy!=0) && pIdxInfo->orderByConsumed); pNew->rSetup = 0; pNew->rRun = whereCostFromDouble(pIdxInfo->estimatedCost); pNew->nOut = 46; assert( 46 == whereCostFromInt(25) ); whereLoopInsert(pBuilder, pNew); if( pNew->u.vtab.needFree ){ sqlite3_free(pNew->u.vtab.idxStr); pNew->u.vtab.needFree = 0; } } } whereLoopAddVtab_exit: if( pIdxInfo->needToFreeIdxStr ) sqlite3_free(pIdxInfo->idxStr); sqlite3DbFree(db, pIdxInfo); return rc; } #endif /* SQLITE_OMIT_VIRTUALTABLE */ /* ** Add WhereLoop entries to handle OR terms. This works for either ** btrees or virtual tables. */ static int whereLoopAddOr(WhereLoopBuilder *pBuilder, Bitmask mExtra){ WhereInfo *pWInfo = pBuilder->pWInfo; |
︙ | ︙ | |||
4691 4692 4693 4694 4695 4696 4697 4698 4699 | sSubBuild.pWC = &tempWC; }else{ continue; } sBest.maskSelf = 0; sBest.rSetup = 0; sBest.rRun = 0; if( IsVirtual(pItem->pTab) ){ rc = whereLoopAddVirtual(&sSubBuild, mExtra); | > | > > | 4717 4718 4719 4720 4721 4722 4723 4724 4725 4726 4727 4728 4729 4730 4731 4732 4733 4734 4735 4736 | sSubBuild.pWC = &tempWC; }else{ continue; } sBest.maskSelf = 0; sBest.rSetup = 0; sBest.rRun = 0; #ifndef SQLITE_OMIT_VIRTUALTABLE if( IsVirtual(pItem->pTab) ){ rc = whereLoopAddVirtual(&sSubBuild, mExtra); }else #endif { rc = whereLoopAddBtree(&sSubBuild, mExtra); } if( sBest.maskSelf==0 ) break; assert( sBest.rSetup==0 ); rTotal = whereCostAdd(rTotal, sBest.rRun); nRow = whereCostAdd(nRow, sBest.nOut); prereq |= sBest.prereq; |
︙ | ︙ |
Changes to test/analyze5.test.
︙ | ︙ | |||
152 153 154 155 156 157 158 | 301 {y=1} t1y 26 302 {y=0.1} t1y 1 400 {x IS NULL} t1x 400 } { # Verify that the expected index is used with the expected row count | > | | | | | | | | 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 | 301 {y=1} t1y 26 302 {y=0.1} t1y 1 400 {x IS NULL} t1x 400 } { # Verify that the expected index is used with the expected row count # No longer valid due to an EXPLAIN QUERY PLAN output format change # do_test analyze5-1.${testid}a { # set x [lindex [eqp "SELECT * FROM t1 WHERE $where"] 3] # set idx {} # regexp {INDEX (t1.) } $x all idx # regexp {~([0-9]+) rows} $x all nrow # list $idx $nrow # } [list $index $rows] # Verify that the same result is achieved regardless of whether or not # the index is used do_test analyze5-1.${testid}b { set w2 [string map {y +y z +z} $where] set a1 [db eval "SELECT rowid FROM t1 NOT INDEXED WHERE $w2\ ORDER BY +rowid"] |
︙ | ︙ | |||
198 199 200 201 202 203 204 | 503 {x=1} t1x 1 504 {x IS NOT NULL} t1x 2 505 {+x IS NOT NULL} {} 500 506 {upper(x) IS NOT NULL} {} 500 } { # Verify that the expected index is used with the expected row count | | | | | | | | | < | 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 | 503 {x=1} t1x 1 504 {x IS NOT NULL} t1x 2 505 {+x IS NOT NULL} {} 500 506 {upper(x) IS NOT NULL} {} 500 } { # Verify that the expected index is used with the expected row count # No longer valid due to an EXPLAIN QUERY PLAN format change # do_test analyze5-1.${testid}a { # set x [lindex [eqp "SELECT * FROM t1 WHERE $where"] 3] # set idx {} # regexp {INDEX (t1.) } $x all idx # regexp {~([0-9]+) rows} $x all nrow # list $idx $nrow # } [list $index $rows] # Verify that the same result is achieved regardless of whether or not # the index is used do_test analyze5-1.${testid}b { set w2 [string map {y +y z +z} $where] set a1 [db eval "SELECT rowid FROM t1 NOT INDEXED WHERE $w2\ ORDER BY +rowid"] |
︙ | ︙ |
Changes to test/between.test.
︙ | ︙ | |||
54 55 56 57 58 59 60 | set ::sqlite_sort_count 0 set data [execsql $sql] if {$::sqlite_sort_count} {set x sort} {set x nosort} lappend data $x set eqp [execsql "EXPLAIN QUERY PLAN $sql"] # puts eqp=$eqp foreach {a b c x} $eqp { | | | | 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | set ::sqlite_sort_count 0 set data [execsql $sql] if {$::sqlite_sort_count} {set x sort} {set x nosort} lappend data $x set eqp [execsql "EXPLAIN QUERY PLAN $sql"] # puts eqp=$eqp foreach {a b c x} $eqp { if {[regexp { TABLE (\w+ AS )?(\w+) USING.* INDEX (\w+)\y} \ $x all as tab idx]} { lappend data $tab $idx } elseif {[regexp { TABLE (\w+ AS )?(\w+)\y} $x all as tab]} { lappend data $tab * } } return $data } do_test between-1.1.1 { |
︙ | ︙ |
Changes to test/eqp.test.
︙ | ︙ | |||
550 551 552 553 554 555 556 | } det 7.1 "SELECT count(*) FROM t1" { 0 0 0 {SCAN TABLE t1} } det 7.2 "SELECT count(*) FROM t2" { | | | 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 | } det 7.1 "SELECT count(*) FROM t1" { 0 0 0 {SCAN TABLE t1} } det 7.2 "SELECT count(*) FROM t2" { 0 0 0 {SCAN TABLE t2 USING COVERING INDEX i1} } do_execsql_test 7.3 { INSERT INTO t1 VALUES(1, 2); INSERT INTO t1 VALUES(3, 4); INSERT INTO t2 VALUES(1, 2); |
︙ | ︙ | |||
572 573 574 575 576 577 578 | sqlite3 db test.db det 7.4 "SELECT count(*) FROM t1" { 0 0 0 {SCAN TABLE t1} } det 7.5 "SELECT count(*) FROM t2" { | | | 572 573 574 575 576 577 578 579 580 581 582 583 | sqlite3 db test.db det 7.4 "SELECT count(*) FROM t1" { 0 0 0 {SCAN TABLE t1} } det 7.5 "SELECT count(*) FROM t2" { 0 0 0 {SCAN TABLE t2 USING COVERING INDEX i1} } finish_test |