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 | SQL 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 |
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: 36373b85 user: drh tags: nextgen-query-plan-logcost | |
| 01:50 | Handle virtual tables correctly when using logarithmic costs. Fixes to test cases. check-in: e612664a 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: aa580e36 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 .... 4084 4085 4086 4087 4088 4089 4090 4091 4092 4093 4094 4095 4096 4097 .... 4259 4260 4261 4262 4263 4264 4265 4266 4267 4268 4269 4270 4271 4272 4273 .... 4478 4479 4480 4481 4482 4483 4484 4485 4486 4487 4488 4489 4490 4491 .... 4565 4566 4567 4568 4569 4570 4571 4572 4573 4574 4575 4576 4577 4578 4579 4580 .... 4620 4621 4622 4623 4624 4625 4626 4627 4628 4629 4630 4631 4632 4633 4634 .... 4635 4636 4637 4638 4639 4640 4641 4642 4643 4644 4645 4646 4647 4648 .... 4691 4692 4693 4694 4695 4696 4697 4698 4699 4700 4701 4702 4703 4704 4705 4706 4707 |
}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.
*/
................................................................................
&& 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
................................................................................
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;
}
#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)
................................................................................
/* 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 */
................................................................................
}
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;
/* ((WhereCost)2) In case of SQLITE_OMIT_FLOATING_POINT... */
pIdxInfo->estimatedCost = SQLITE_BIG_DBL / ((WhereCost)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;
................................................................................
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 = whereCostFromInt((tRowcnt)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;
}
/*
** 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;
................................................................................
sSubBuild.pWC = &tempWC;
}else{
continue;
}
sBest.maskSelf = 0;
sBest.rSetup = 0;
sBest.rRun = 0;
if( IsVirtual(pItem->pTab) ){
rc = whereLoopAddVirtual(&sSubBuild, mExtra);
}else{
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;
|
> > > > > > > > > > > > > > > > > > > > > > > > > | > < | | > > | > > |
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 .... 4101 4102 4103 4104 4105 4106 4107 4108 4109 4110 4111 4112 4113 4114 4115 4116 4117 4118 4119 4120 4121 4122 .... 4284 4285 4286 4287 4288 4289 4290 4291 4292 4293 4294 4295 4296 4297 4298 .... 4503 4504 4505 4506 4507 4508 4509 4510 4511 4512 4513 4514 4515 4516 4517 .... 4591 4592 4593 4594 4595 4596 4597 4598 4599 4600 4601 4602 4603 4604 4605 .... 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 .... 4717 4718 4719 4720 4721 4722 4723 4724 4725 4726 4727 4728 4729 4730 4731 4732 4733 4734 4735 4736 |
}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.
*/
................................................................................
&& 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
................................................................................
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)
................................................................................
/* 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 */
................................................................................
}
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;
................................................................................
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;
................................................................................
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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
...
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
|
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
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"]
................................................................................
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
if {$testid==50299} {breakpoint; set sqlite_where_trace 1}
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]
if {$testid==50299} exit
# 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"]
|
>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
<
|
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
...
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
|
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"]
................................................................................
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 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+)\W} \
$x all as tab idx]} {
lappend data $tab $idx
} elseif {[regexp { TABLE (\w+ AS )?(\w+)\W} $x all as tab]} {
lappend data $tab *
}
}
return $data
}
do_test between-1.1.1 {
|
| | |
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
557
558
559
560
561
562
563
564
...
572
573
574
575
576
577
578
579
580
581
582
583
|
}
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(~1000000 rows)}
}
do_execsql_test 7.3 {
INSERT INTO t1 VALUES(1, 2);
INSERT INTO t1 VALUES(3, 4);
INSERT INTO t2 VALUES(1, 2);
................................................................................
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(~3 rows)}
}
finish_test
|
|
|
|
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
...
572
573
574
575
576
577
578
579
580
581
582
583
|
}
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);
................................................................................
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
|