Index: src/where.c ================================================================== --- src/where.c +++ src/where.c @@ -3708,10 +3708,128 @@ whereLoopDelete(db, p); } sqlite3DbFree(db, pWInfo); } } + +/* +** Return TRUE if the set of WHERE clause terms used by pA is a proper +** subset of the WHERE clause terms used by pB. +*/ +static int whereLoopProperSubset(const WhereLoop *pA, const WhereLoop *pB){ + int i, j; + assert( pA->nLTermnLTerm ); /* Checked by calling function */ + for(j=0, i=pA->nLTerm-1; i>=0 && j>=0; i--){ + for(j=pB->nLTerm-1; j>=0; j--){ + if( pB->aLTerm[j]==pA->aLTerm[i] ) break; + } + } + return j>=0; +} + +/* +** Try to adjust the cost of WhereLoop pTemplate upwards or downwards so +** that: +** +** (1) pTemplate costs less than any other WhereLoops that are a proper +** subset of pTemplate +** +** (2) pTemplate costs more than any other WhereLoops for which pTemplate +** is a proper subset. +** +** To say "WhereLoop X is a proper subset of Y" means that X uses fewer +** WHERE clause terms than Y and that every WHERE clause term used by X is +** also used by Y. +*/ +static void whereLoopAdjustCost(const WhereLoop *p, WhereLoop *pTemplate){ + if( (pTemplate->wsFlags & WHERE_INDEXED)==0 ) return; + for(; p; p=p->pNextLoop){ + if( p->iTab!=pTemplate->iTab ) continue; + if( (p->wsFlags & WHERE_INDEXED)==0 ) continue; + if( p->nLTermnLTerm + && (p->rRunrRun || (p->rRun==pTemplate->rRun && + p->nOut<=pTemplate->nOut)) + && whereLoopProperSubset(p, pTemplate) + ){ + pTemplate->rRun = p->rRun; + pTemplate->nOut = p->nOut - 1; + }else + if( p->nLTerm>pTemplate->nLTerm + && (p->rRun>pTemplate->rRun || (p->rRun==pTemplate->rRun && + p->nOut>=pTemplate->nOut)) + && whereLoopProperSubset(pTemplate, p) + ){ + pTemplate->rRun = p->rRun; + pTemplate->nOut = p->nOut + 1; + } + } +} + +/* +** Search the list of WhereLoops in *ppPrev looking for one that can be +** supplanted by pTemplate. +** +** Return NULL if the WhereLoop list contains an entry that can supplant +** pTemplate, in other words if pTemplate does not belong on the list. +** +** If pX is a WhereLoop that pTemplate can supplant, then return the +** link that points to pX. +** +** If pTemplate cannot supplant any existing element of the list but needs +** to be added to the list, then return a pointer to the tail of the list. +*/ +static WhereLoop **whereLoopFindLesser( + WhereLoop **ppPrev, + const WhereLoop *pTemplate +){ + WhereLoop *p; + for(p=(*ppPrev); p; ppPrev=&p->pNextLoop, p=*ppPrev){ + if( p->iTab!=pTemplate->iTab || p->iSortIdx!=pTemplate->iSortIdx ){ + /* If either the iTab or iSortIdx values for two WhereLoop are different + ** then those WhereLoops need to be considered separately. Neither is + ** a candidate to replace the other. */ + continue; + } + /* In the current implementation, the rSetup value is either zero + ** or the cost of building an automatic index (NlogN) and the NlogN + ** is the same for compatible WhereLoops. */ + assert( p->rSetup==0 || pTemplate->rSetup==0 + || p->rSetup==pTemplate->rSetup ); + + /* whereLoopAddBtree() always generates and inserts the automatic index + ** case first. Hence compatible candidate WhereLoops never have a larger + ** rSetup. Call this SETUP-INVARIANT */ + assert( p->rSetup>=pTemplate->rSetup ); + + /* If existing WhereLoop p is better than pTemplate, pTemplate can be + ** discarded. WhereLoop p is better if: + ** (1) p has no more dependencies than pTemplate, and + ** (2) p has an equal or lower cost than pTemplate + */ + if( (p->prereq & pTemplate->prereq)==p->prereq /* (1) */ + && p->rSetup<=pTemplate->rSetup /* (2a) */ + && p->rRun<=pTemplate->rRun /* (2b) */ + && p->nOut<=pTemplate->nOut /* (2c) */ + ){ + return 0; /* Discard pTemplate */ + } + + /* If pTemplate is always better than p, then cause p to be overwritten + ** with pTemplate. pTemplate is better than p if: + ** (1) pTemplate has no more dependences than p, and + ** (2) pTemplate has an equal or lower cost than p. + */ + if( (p->prereq & pTemplate->prereq)==pTemplate->prereq /* (1) */ + && p->rRun>=pTemplate->rRun /* (2a) */ + && p->nOut>=pTemplate->nOut /* (2b) */ + ){ + assert( p->rSetup>=pTemplate->rSetup ); /* SETUP-INVARIANT above */ + break; /* Cause p to be overwritten by pTemplate */ + } + } + return ppPrev; +} /* ** Insert or replace a WhereLoop entry using the template supplied. ** ** An existing WhereLoop entry might be overwritten if the new template @@ -3718,29 +3836,27 @@ ** is better and has fewer dependencies. Or the template will be ignored ** and no insert will occur if an existing WhereLoop is faster and has ** fewer dependencies than the template. Otherwise a new WhereLoop is ** added based on the template. ** -** If pBuilder->pOrSet is not NULL then we only care about only the +** If pBuilder->pOrSet is not NULL then we care about only the ** prerequisites and rRun and nOut costs of the N best loops. That ** information is gathered in the pBuilder->pOrSet object. This special ** processing mode is used only for OR clause processing. ** ** When accumulating multiple loops (when pBuilder->pOrSet is NULL) we ** still might overwrite similar loops with the new template if the -** template is better. Loops may be overwritten if the following +** new template is better. Loops may be overwritten if the following ** conditions are met: ** ** (1) They have the same iTab. ** (2) They have the same iSortIdx. ** (3) The template has same or fewer dependencies than the current loop ** (4) The template has the same or lower cost than the current loop -** (5) The template uses more terms of the same index but has no additional -** dependencies */ static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){ - WhereLoop **ppPrev, *p, *pNext = 0; + WhereLoop **ppPrev, *p; WhereInfo *pWInfo = pBuilder->pWInfo; sqlite3 *db = pWInfo->pParse->db; /* If pBuilder->pOrSet is defined, then only keep track of the costs ** and prereqs. @@ -3759,68 +3875,27 @@ } #endif return SQLITE_OK; } - /* Search for an existing WhereLoop to overwrite, or which takes - ** priority over pTemplate. - */ - for(ppPrev=&pWInfo->pLoops, p=*ppPrev; p; ppPrev=&p->pNextLoop, p=*ppPrev){ - if( p->iTab!=pTemplate->iTab || p->iSortIdx!=pTemplate->iSortIdx ){ - /* If either the iTab or iSortIdx values for two WhereLoop are different - ** then those WhereLoops need to be considered separately. Neither is - ** a candidate to replace the other. */ - continue; - } - /* In the current implementation, the rSetup value is either zero - ** or the cost of building an automatic index (NlogN) and the NlogN - ** is the same for compatible WhereLoops. */ - assert( p->rSetup==0 || pTemplate->rSetup==0 - || p->rSetup==pTemplate->rSetup ); - - /* whereLoopAddBtree() always generates and inserts the automatic index - ** case first. Hence compatible candidate WhereLoops never have a larger - ** rSetup. Call this SETUP-INVARIANT */ - assert( p->rSetup>=pTemplate->rSetup ); - - if( (p->prereq & pTemplate->prereq)==p->prereq - && p->rSetup<=pTemplate->rSetup - && p->rRun<=pTemplate->rRun - && p->nOut<=pTemplate->nOut - ){ - /* This branch taken when p is equal or better than pTemplate in - ** all of (1) dependencies (2) setup-cost, (3) run-cost, and - ** (4) number of output rows. */ - assert( p->rSetup==pTemplate->rSetup ); - if( p->prereq==pTemplate->prereq - && p->nLTermnLTerm - && (p->wsFlags & pTemplate->wsFlags & WHERE_INDEXED)!=0 - && (p->u.btree.pIndex==pTemplate->u.btree.pIndex - || pTemplate->rRun+p->nLTerm<=p->rRun+pTemplate->nLTerm) - ){ - /* 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 - && p->rRun>=pTemplate->rRun - && p->nOut>=pTemplate->nOut - ){ - /* Overwrite an existing WhereLoop with a better one: one that is - ** better at one of (1) dependencies, (2) setup-cost, (3) run-cost - ** or (4) number of output rows, and is no worse in any of those - ** categories. */ - assert( p->rSetup>=pTemplate->rSetup ); /* SETUP-INVARIANT above */ - pNext = p->pNextLoop; - break; - } + /* Look for an existing WhereLoop to replace with pTemplate + */ + whereLoopAdjustCost(pWInfo->pLoops, pTemplate); + ppPrev = whereLoopFindLesser(&pWInfo->pLoops, pTemplate); + + if( ppPrev==0 ){ + /* There already exists a WhereLoop on the list that is better + ** than pTemplate, so just ignore pTemplate */ +#if WHERETRACE_ENABLED /* 0x8 */ + if( sqlite3WhereTrace & 0x8 ){ + sqlite3DebugPrintf("ins-noop: "); + whereLoopPrint(pTemplate, pBuilder->pWC); + } +#endif + return SQLITE_OK; + }else{ + p = *ppPrev; } /* If we reach this point it means that either p[] should be overwritten ** with pTemplate[] if p[] exists, or if p==NULL then allocate a new ** WhereLoop and insert it. @@ -3834,34 +3909,44 @@ sqlite3DebugPrintf("ins-new: "); whereLoopPrint(pTemplate, pBuilder->pWC); } #endif if( p==0 ){ - p = sqlite3DbMallocRaw(db, sizeof(WhereLoop)); + /* Allocate a new WhereLoop to add to the end of the list */ + *ppPrev = p = sqlite3DbMallocRaw(db, sizeof(WhereLoop)); if( p==0 ) return SQLITE_NOMEM; whereLoopInit(p); + p->pNextLoop = 0; + }else{ + /* We will be overwriting WhereLoop p[]. But before we do, first + ** go through the rest of the list and delete any other entries besides + ** p[] that are also supplated by pTemplate */ + WhereLoop **ppTail = &p->pNextLoop; + WhereLoop *pToDel; + while( *ppTail ){ + ppTail = whereLoopFindLesser(ppTail, pTemplate); + if( NEVER(ppTail==0) ) break; + pToDel = *ppTail; + if( pToDel==0 ) break; + *ppTail = pToDel->pNextLoop; +#if WHERETRACE_ENABLED /* 0x8 */ + if( sqlite3WhereTrace & 0x8 ){ + sqlite3DebugPrintf("ins-del: "); + whereLoopPrint(pToDel, pBuilder->pWC); + } +#endif + whereLoopDelete(db, pToDel); + } } whereLoopXfer(db, p, pTemplate); - p->pNextLoop = pNext; - *ppPrev = p; if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){ Index *pIndex = p->u.btree.pIndex; if( pIndex && pIndex->tnum==0 ){ p->u.btree.pIndex = 0; } } return SQLITE_OK; - - /* Jump here if the insert is a no-op */ -whereLoopInsert_noop: -#if WHERETRACE_ENABLED /* 0x8 */ - if( sqlite3WhereTrace & 0x8 ){ - sqlite3DebugPrintf("ins-noop: "); - whereLoopPrint(pTemplate, pBuilder->pWC); - } -#endif - return SQLITE_OK; } /* ** Adjust the WhereLoop.nOut value downward to account for terms of the ** WHERE clause that reference the loop but which are not used by an ADDED test/whereH.test Index: test/whereH.test ================================================================== --- /dev/null +++ test/whereH.test @@ -0,0 +1,139 @@ +# 2014-03-31 +# +# 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 query planning decisions where one candidate index +# covers a proper superset of the WHERE clause terms of another +# candidate index. +# + +set testdir [file dirname $argv0] +source $testdir/tester.tcl + +do_execsql_test whereH-1.1 { + CREATE TABLE t1(a,b,c,d); + CREATE INDEX t1abc ON t1(a,b,c); + CREATE INDEX t1bc ON t1(b,c); + + EXPLAIN QUERY PLAN + SELECT d FROM t1 WHERE a=? AND b=? AND c>=? ORDER BY c; +} {/INDEX t1abc /} +do_execsql_test whereH-1.2 { + EXPLAIN QUERY PLAN + SELECT d FROM t1 WHERE a=? AND b=? AND c>=? ORDER BY c; +} {~/TEMP B-TREE FOR ORDER BY/} + +do_execsql_test whereH-2.1 { + DROP TABLE t1; + CREATE TABLE t1(a,b,c,d); + CREATE INDEX t1bc ON t1(b,c); + CREATE INDEX t1abc ON t1(a,b,c); + + EXPLAIN QUERY PLAN + SELECT d FROM t1 WHERE a=? AND b=? AND c>=? ORDER BY c; +} {/INDEX t1abc /} +do_execsql_test whereH-2.2 { + EXPLAIN QUERY PLAN + SELECT d FROM t1 WHERE a=? AND b=? AND c>=? ORDER BY c; +} {~/TEMP B-TREE FOR ORDER BY/} + +do_execsql_test whereH-3.1 { + DROP TABLE t1; + CREATE TABLE t1(a,b,c,d,e); + CREATE INDEX t1cd ON t1(c,d); + CREATE INDEX t1bcd ON t1(b,c,d); + CREATE INDEX t1abcd ON t1(a,b,c,d); + + EXPLAIN QUERY PLAN + SELECT d FROM t1 WHERE a=? AND b=? AND c=? AND d>=? ORDER BY d; +} {/INDEX t1abcd /} +do_execsql_test whereH-3.2 { + EXPLAIN QUERY PLAN + SELECT d FROM t1 WHERE a=? AND b=? AND c=? AND d>=? ORDER BY d; +} {~/TEMP B-TREE FOR ORDER BY/} + +do_execsql_test whereH-4.1 { + DROP TABLE t1; + CREATE TABLE t1(a,b,c,d,e); + CREATE INDEX t1cd ON t1(c,d); + CREATE INDEX t1abcd ON t1(a,b,c,d); + CREATE INDEX t1bcd ON t1(b,c,d); + + EXPLAIN QUERY PLAN + SELECT d FROM t1 WHERE a=? AND b=? AND c=? AND d>=? ORDER BY d; +} {/INDEX t1abcd /} +do_execsql_test whereH-4.2 { + EXPLAIN QUERY PLAN + SELECT d FROM t1 WHERE a=? AND b=? AND c=? AND d>=? ORDER BY d; +} {~/TEMP B-TREE FOR ORDER BY/} + +do_execsql_test whereH-5.1 { + DROP TABLE t1; + CREATE TABLE t1(a,b,c,d,e); + CREATE INDEX t1bcd ON t1(b,c,d); + CREATE INDEX t1cd ON t1(c,d); + CREATE INDEX t1abcd ON t1(a,b,c,d); + + EXPLAIN QUERY PLAN + SELECT d FROM t1 WHERE a=? AND b=? AND c=? AND d>=? ORDER BY d; +} {/INDEX t1abcd /} +do_execsql_test whereH-5.2 { + EXPLAIN QUERY PLAN + SELECT d FROM t1 WHERE a=? AND b=? AND c=? AND d>=? ORDER BY d; +} {~/TEMP B-TREE FOR ORDER BY/} + +do_execsql_test whereH-6.1 { + DROP TABLE t1; + CREATE TABLE t1(a,b,c,d,e); + CREATE INDEX t1bcd ON t1(b,c,d); + CREATE INDEX t1abcd ON t1(a,b,c,d); + CREATE INDEX t1cd ON t1(c,d); + + EXPLAIN QUERY PLAN + SELECT d FROM t1 WHERE a=? AND b=? AND c=? AND d>=? ORDER BY d; +} {/INDEX t1abcd /} +do_execsql_test whereH-6.2 { + EXPLAIN QUERY PLAN + SELECT d FROM t1 WHERE a=? AND b=? AND c=? AND d>=? ORDER BY d; +} {~/TEMP B-TREE FOR ORDER BY/} + +do_execsql_test whereH-7.1 { + DROP TABLE t1; + CREATE TABLE t1(a,b,c,d,e); + CREATE INDEX t1abcd ON t1(a,b,c,d); + CREATE INDEX t1bcd ON t1(b,c,d); + CREATE INDEX t1cd ON t1(c,d); + + EXPLAIN QUERY PLAN + SELECT d FROM t1 WHERE a=? AND b=? AND c=? AND d>=? ORDER BY d; +} {/INDEX t1abcd /} +do_execsql_test whereH-7.2 { + EXPLAIN QUERY PLAN + SELECT d FROM t1 WHERE a=? AND b=? AND c=? AND d>=? ORDER BY d; +} {~/TEMP B-TREE FOR ORDER BY/} + +do_execsql_test whereH-8.1 { + DROP TABLE t1; + CREATE TABLE t1(a,b,c,d,e); + CREATE INDEX t1abcd ON t1(a,b,c,d); + CREATE INDEX t1cd ON t1(c,d); + CREATE INDEX t1bcd ON t1(b,c,d); + + EXPLAIN QUERY PLAN + SELECT d FROM t1 WHERE a=? AND b=? AND c=? AND d>=? ORDER BY d; +} {/INDEX t1abcd /} +do_execsql_test whereH-8.2 { + EXPLAIN QUERY PLAN + SELECT d FROM t1 WHERE a=? AND b=? AND c=? AND d>=? ORDER BY d; +} {~/TEMP B-TREE FOR ORDER BY/} + + + +finish_test