Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Improvements to likelihood processing so that commuting an unindexed term in the WHERE clause does not change the query plan. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | unlikely-func |
| Files: | files | file ages | folders |
| SHA1: |
6e6bded055cdbc902731687c86d92c39 |
| User & Date: | drh 2013-09-11 17:39:09 |
Context
|
2013-09-12
| ||
| 17:29 | Merge in the Expr.flags expansion to 32-bits. Use an extra bit to help optimize the sqlite3ExprSkipCollate() routine. (check-in: 4c84d1b4 user: drh tags: unlikely-func) | |
|
2013-09-11
| ||
| 17:39 | Improvements to likelihood processing so that commuting an unindexed term in the WHERE clause does not change the query plan. (check-in: 6e6bded0 user: drh tags: unlikely-func) | |
| 14:34 | Additional unlikely() test cases. Logic tweaks to support test coverage. (check-in: 5d00cce7 user: drh tags: unlikely-func) | |
Changes
Changes to src/where.c.
685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 .... 4282 4283 4284 4285 4286 4287 4288 4289 4290 4291 4292 4293 4294 4295 4296 4297 4298 4299 4300 4301 4302 4303 4304 4305 4306 4307 4308 4309 4310 4311 4312 4313 .... 5422 5423 5424 5425 5426 5427 5428 5429 5430 5431 5432 5433 5434 5435 5436 5437 5438 |
memcpy(pWC->a, pOld, sizeof(pWC->a[0])*pWC->nTerm);
if( pOld!=pWC->aStatic ){
sqlite3DbFree(db, pOld);
}
pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]);
}
pTerm = &pWC->a[idx = pWC->nTerm++];
if( wtFlags & TERM_VIRTUAL ){
pTerm->truthProb = 0;
}else if( ALWAYS(p) && ExprHasAnyProperty(p, EP_Hint) ){
pTerm->truthProb = whereCost(p->iTable) - 99;
}else{
pTerm->truthProb = -1;
}
pTerm->pExpr = sqlite3ExprSkipCollate(p);
pTerm->wtFlags = wtFlags;
pTerm->pWC = pWC;
................................................................................
** index.
**
** In the current implementation, the first extra WHERE clause term reduces
** the number of output rows by a factor of 10 and each additional term
** reduces the number of output rows by sqrt(2).
*/
static void whereLoopOutputAdjust(WhereClause *pWC, WhereLoop *pLoop, int iCur){
WhereTerm *pTerm;
Bitmask notAllowed = ~(pLoop->prereq|pLoop->maskSelf);
int x = 0;
int i;
if( !OptimizationEnabled(pWC->pWInfo->pParse->db, SQLITE_AdjustOutEst) ){
return;
}
for(i=pWC->nTerm, pTerm=pWC->a; i>0; i--, pTerm++){
if( (pTerm->wtFlags & TERM_VIRTUAL)!=0 ) continue;
if( (pTerm->prereqAll & pLoop->maskSelf)==0 ) continue;
if( (pTerm->prereqAll & notAllowed)!=0 ) continue;
x += pTerm->truthProb;
}
for(i=pLoop->nLTerm-1; i>=0; i--){
x -= pLoop->aLTerm[i]->truthProb;
}
if( x<0 ) pLoop->nOut += x;
}
/*
** We have so far matched pBuilder->pNew->u.btree.nEq terms of the index pIndex.
** Try to match one more.
**
** If pProbe->tnum==0, that means pIndex is a fake index used for the
................................................................................
(pTo->rCost>=rCost && pTo->nRow>=nOut))
){
testcase( jj==nTo-1 );
break;
}
}
if( jj>=nTo ){
if( nTo>=mxChoice
&& (rCost>mxCost || (rCost==mxCost && nOut>=mxOut))
){
#ifdef WHERETRACE_ENABLED
if( sqlite3WhereTrace&0x4 ){
sqlite3DebugPrintf("Skip %s cost=%-3d,%3d order=%c\n",
wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,
isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?');
}
#endif
|
< < | | < | | < < | | > > | | > | < < |
685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 .... 4280 4281 4282 4283 4284 4285 4286 4287 4288 4289 4290 4291 4292 4293 4294 4295 4296 4297 4298 4299 4300 4301 4302 4303 4304 4305 4306 4307 4308 4309 4310 4311 .... 5420 5421 5422 5423 5424 5425 5426 5427 5428 5429 5430 5431 5432 5433 5434 |
memcpy(pWC->a, pOld, sizeof(pWC->a[0])*pWC->nTerm);
if( pOld!=pWC->aStatic ){
sqlite3DbFree(db, pOld);
}
pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]);
}
pTerm = &pWC->a[idx = pWC->nTerm++];
if( p && ExprHasAnyProperty(p, EP_Hint) ){
pTerm->truthProb = whereCost(p->iTable) - 99;
}else{
pTerm->truthProb = -1;
}
pTerm->pExpr = sqlite3ExprSkipCollate(p);
pTerm->wtFlags = wtFlags;
pTerm->pWC = pWC;
................................................................................
** index.
**
** In the current implementation, the first extra WHERE clause term reduces
** the number of output rows by a factor of 10 and each additional term
** reduces the number of output rows by sqrt(2).
*/
static void whereLoopOutputAdjust(WhereClause *pWC, WhereLoop *pLoop, int iCur){
WhereTerm *pTerm, *pX;
Bitmask notAllowed = ~(pLoop->prereq|pLoop->maskSelf);
int i, j;
if( !OptimizationEnabled(pWC->pWInfo->pParse->db, SQLITE_AdjustOutEst) ){
return;
}
for(i=pWC->nTerm, pTerm=pWC->a; i>0; i--, pTerm++){
if( (pTerm->wtFlags & TERM_VIRTUAL)!=0 ) break;
if( (pTerm->prereqAll & pLoop->maskSelf)==0 ) continue;
if( (pTerm->prereqAll & notAllowed)!=0 ) continue;
for(j=pLoop->nLTerm-1; j>=0; j--){
pX = pLoop->aLTerm[j];
if( pX==pTerm ) break;
if( pX->iParent>=0 && (&pWC->a[pX->iParent])==pTerm ) break;
}
if( j<0 ) pLoop->nOut += pTerm->truthProb;
}
}
/*
** We have so far matched pBuilder->pNew->u.btree.nEq terms of the index pIndex.
** Try to match one more.
**
** If pProbe->tnum==0, that means pIndex is a fake index used for the
................................................................................
(pTo->rCost>=rCost && pTo->nRow>=nOut))
){
testcase( jj==nTo-1 );
break;
}
}
if( jj>=nTo ){
if( nTo>=mxChoice && rCost>=mxCost ){
#ifdef WHERETRACE_ENABLED
if( sqlite3WhereTrace&0x4 ){
sqlite3DebugPrintf("Skip %s cost=%-3d,%3d order=%c\n",
wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,
isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?');
}
#endif
|
Changes to test/whereG.test.
142 143 144 145 146 147 148 149 150 |
SELECT DISTINCT aname
FROM album, composer, track
WHERE likelihood(cname LIKE '%bach%', track.cid)
AND composer.cid=track.cid
AND album.aid=track.aid;
}
} {1 {second argument to likelihood() must be a constant between 0.0 and 1.0}}
finish_test
|
> > > > > > > > > > > > > > > > > > > > |
142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 |
SELECT DISTINCT aname
FROM album, composer, track
WHERE likelihood(cname LIKE '%bach%', track.cid)
AND composer.cid=track.cid
AND album.aid=track.aid;
}
} {1 {second argument to likelihood() must be a constant between 0.0 and 1.0}}
# Commuting a term of the WHERE clause should not change the query plan
#
do_execsql_test whereG-3.0 {
CREATE TABLE a(a1 PRIMARY KEY, a2);
CREATE TABLE b(b1 PRIMARY KEY, b2);
} {}
do_eqp_test whereG-3.1 {
SELECT * FROM a, b WHERE b1=a1 AND a2=5;
} {/.*SCAN TABLE a.*SEARCH TABLE b USING INDEX .*b_1 .b1=..*/}
do_eqp_test whereG-3.2 {
SELECT * FROM a, b WHERE a1=b1 AND a2=5;
} {/.*SCAN TABLE a.*SEARCH TABLE b USING INDEX .*b_1 .b1=..*/}
do_eqp_test whereG-3.3 {
SELECT * FROM a, b WHERE a2=5 AND b1=a1;
} {/.*SCAN TABLE a.*SEARCH TABLE b USING INDEX .*b_1 .b1=..*/}
do_eqp_test whereG-3.4 {
SELECT * FROM a, b WHERE a2=5 AND a1=b1;
} {/.*SCAN TABLE a.*SEARCH TABLE b USING INDEX .*b_1 .b1=..*/}
finish_test
|