Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Enhance the query planner so that it looks at multiple solutions to OR expressions in the WHERE clause. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
5e19d054105fb16ff52d265d48cc87a4 |
User & Date: | drh 2013-07-16 21:31:23.453 |
Context
2013-07-16
| ||
23:26 | Make sure the sqlite3_prepare16 and sqlite3_prepare16_v2 interfaces do not read past a zero-terminator if the nBytes parameter is too large. (check-in: 20dba3a7fb user: drh tags: trunk) | |
21:31 | Enhance the query planner so that it looks at multiple solutions to OR expressions in the WHERE clause. (check-in: 5e19d05410 user: drh tags: trunk) | |
2013-07-15
| ||
17:02 | Add the sqlite3_cancel_auto_extension(X) interface which will undo a prior call to sqlite3_auto_extension(X). (check-in: cdce87eb88 user: drh tags: trunk) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
41 42 43 44 45 46 47 48 49 50 51 52 53 54 | typedef struct WhereAndInfo WhereAndInfo; typedef struct WhereLevel WhereLevel; typedef struct WhereLoop WhereLoop; typedef struct WherePath WherePath; typedef struct WhereTerm WhereTerm; typedef struct WhereLoopBuilder WhereLoopBuilder; typedef struct WhereScan WhereScan; /* ** Cost X is tracked as 10*log2(X) stored in a 16-bit integer. The ** maximum cost for ordinary tables is 64*(2**63) which becomes 6900. ** (Virtual tables can return a larger cost, but let's assume they do not.) ** So all costs can be stored in a 16-bit unsigned integer without risk ** of overflow. | > > | 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | typedef struct WhereAndInfo WhereAndInfo; typedef struct WhereLevel WhereLevel; typedef struct WhereLoop WhereLoop; typedef struct WherePath WherePath; typedef struct WhereTerm WhereTerm; typedef struct WhereLoopBuilder WhereLoopBuilder; typedef struct WhereScan WhereScan; typedef struct WhereOrCost WhereOrCost; typedef struct WhereOrSet WhereOrSet; /* ** Cost X is tracked as 10*log2(X) stored in a 16-bit integer. The ** maximum cost for ordinary tables is 64*(2**63) which becomes 6900. ** (Virtual tables can return a larger cost, but let's assume they do not.) ** So all costs can be stored in a 16-bit unsigned integer without risk ** of overflow. |
︙ | ︙ | |||
147 148 149 150 151 152 153 154 155 156 157 158 159 160 | /**** whereLoopXfer() copies fields above ***********************/ # define WHERE_LOOP_XFER_SZ offsetof(WhereLoop,nLSlot) u16 nLSlot; /* Number of slots allocated for aLTerm[] */ WhereTerm **aLTerm; /* WhereTerms used */ WhereLoop *pNextLoop; /* Next WhereLoop object in the WhereClause */ WhereTerm *aLTermSpace[4]; /* Initial aLTerm[] space */ }; /* Forward declaration of methods */ static int whereLoopResize(sqlite3*, WhereLoop*, int); /* ** Each instance of this object holds a sequence of WhereLoop objects ** that implement some or all of a query plan. | > > > > > > > > > > > > > > > > > > > > > | 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 | /**** whereLoopXfer() copies fields above ***********************/ # define WHERE_LOOP_XFER_SZ offsetof(WhereLoop,nLSlot) u16 nLSlot; /* Number of slots allocated for aLTerm[] */ WhereTerm **aLTerm; /* WhereTerms used */ WhereLoop *pNextLoop; /* Next WhereLoop object in the WhereClause */ WhereTerm *aLTermSpace[4]; /* Initial aLTerm[] space */ }; /* This object holds the prerequisites and the cost of running a ** subquery on one operand of an OR operator in the WHERE clause. ** See WhereOrSet for additional information */ struct WhereOrCost { Bitmask prereq; /* Prerequisites */ WhereCost rRun; /* Cost of running this subquery */ WhereCost nOut; /* Number of outputs for this subquery */ }; /* The WhereOrSet object holds a set of possible WhereOrCosts that ** correspond to the subquery(s) of OR-clause processing. At most ** favorable N_OR_COST elements are retained. */ #define N_OR_COST 3 struct WhereOrSet { u16 n; /* Number of valid a[] entries */ WhereOrCost a[N_OR_COST]; /* Set of best costs */ }; /* Forward declaration of methods */ static int whereLoopResize(sqlite3*, WhereLoop*, int); /* ** Each instance of this object holds a sequence of WhereLoop objects ** that implement some or all of a query plan. |
︙ | ︙ | |||
362 363 364 365 366 367 368 | ** to construct WhereLoop objects for a particular query. */ struct WhereLoopBuilder { WhereInfo *pWInfo; /* Information about this WHERE */ WhereClause *pWC; /* WHERE clause terms */ ExprList *pOrderBy; /* ORDER BY clause */ WhereLoop *pNew; /* Template WhereLoop */ | | | 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 | ** to construct WhereLoop objects for a particular query. */ struct WhereLoopBuilder { WhereInfo *pWInfo; /* Information about this WHERE */ WhereClause *pWC; /* WHERE clause terms */ ExprList *pOrderBy; /* ORDER BY clause */ WhereLoop *pNew; /* Template WhereLoop */ WhereOrSet *pOrSet; /* Record best loops here, if not NULL */ }; /* ** The WHERE clause processing routine has two halves. The ** first part does the start of the WHERE loop and the second ** half does the tail of the WHERE loop. An instance of ** this structure is returned by the first half and passed |
︙ | ︙ | |||
504 505 506 507 508 509 510 511 512 513 514 515 516 517 | ** Return TRUE if an UPDATE or DELETE statement can operate directly on ** the rowids returned by a WHERE clause. Return FALSE if doing an ** UPDATE or DELETE might change subsequent WHERE clause results. */ int sqlite3WhereOkOnePass(WhereInfo *pWInfo){ return pWInfo->okOnePass; } /* ** Initialize a preallocated WhereClause structure. */ static void whereClauseInit( WhereClause *pWC, /* The WhereClause to be initialized */ WhereInfo *pWInfo /* The WHERE processing context */ | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 | ** Return TRUE if an UPDATE or DELETE statement can operate directly on ** the rowids returned by a WHERE clause. Return FALSE if doing an ** UPDATE or DELETE might change subsequent WHERE clause results. */ int sqlite3WhereOkOnePass(WhereInfo *pWInfo){ return pWInfo->okOnePass; } /* ** Move the content of pSrc into pDest */ static void whereOrMove(WhereOrSet *pDest, WhereOrSet *pSrc){ pDest->n = pSrc->n; memcpy(pDest->a, pSrc->a, pDest->n*sizeof(pDest->a[0])); } /* ** Try to insert a new prerequisite/cost entry into the WhereOrSet pSet. ** ** The new entry might overwrite an existing entry, or it might be ** appended, or it might be discarded. Do whatever is the right thing ** so that pSet keeps the N_OR_COST best entries seen so far. */ static int whereOrInsert( WhereOrSet *pSet, /* The WhereOrSet to be updated */ Bitmask prereq, /* Prerequisites of the new entry */ WhereCost rRun, /* Run-cost of the new entry */ WhereCost nOut /* Number of outputs for the new entry */ ){ u16 i; WhereOrCost *p; for(i=pSet->n, p=pSet->a; i>0; i--, p++){ if( rRun<=p->rRun && (prereq & p->prereq)==prereq ){ goto whereOrInsert_done; } if( p->rRun<=rRun && (p->prereq & prereq)==p->prereq ){ return 0; } } if( pSet->n<N_OR_COST ){ p = &pSet->a[pSet->n++]; p->nOut = nOut; }else{ p = pSet->a; for(i=1; i<pSet->n; i++){ if( p->rRun>pSet->a[i].rRun ) p = pSet->a + i; } if( p->rRun<=rRun ) return 0; } whereOrInsert_done: p->prereq = prereq; p->rRun = rRun; if( p->nOut>nOut ) p->nOut = nOut; return 1; } /* ** Initialize a preallocated WhereClause structure. */ static void whereClauseInit( WhereClause *pWC, /* The WhereClause to be initialized */ WhereInfo *pWInfo /* The WHERE processing context */ |
︙ | ︙ | |||
3739 3740 3741 3742 3743 3744 3745 3746 | ** is not contained in the ON clause of a LEFT JOIN. ** See ticket http://www.sqlite.org/src/info/f2369304e4 */ if( pWC->nTerm>1 ){ int iTerm; for(iTerm=0; iTerm<pWC->nTerm; iTerm++){ Expr *pExpr = pWC->a[iTerm].pExpr; if( ExprHasProperty(pExpr, EP_FromJoin) ) continue; | > | | 3810 3811 3812 3813 3814 3815 3816 3817 3818 3819 3820 3821 3822 3823 3824 3825 3826 | ** is not contained in the ON clause of a LEFT JOIN. ** See ticket http://www.sqlite.org/src/info/f2369304e4 */ if( pWC->nTerm>1 ){ int iTerm; for(iTerm=0; iTerm<pWC->nTerm; iTerm++){ Expr *pExpr = pWC->a[iTerm].pExpr; if( &pWC->a[iTerm] == pTerm ) continue; if( ExprHasProperty(pExpr, EP_FromJoin) ) continue; if( pWC->a[iTerm].wtFlags & (TERM_ORINFO) ) continue; if( (pWC->a[iTerm].eOperator & WO_ALL)==0 ) continue; pExpr = sqlite3ExprDup(pParse->db, pExpr, 0); pAndExpr = sqlite3ExprAnd(pParse->db, pAndExpr, pExpr); } if( pAndExpr ){ pAndExpr = sqlite3PExpr(pParse, TK_AND, 0, pAndExpr, 0); } |
︙ | ︙ | |||
4068 4069 4070 4071 4072 4073 4074 | ** ** An existing WhereLoop entry might be overwritten if the new template ** 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. ** | | | | | | | < | < > > | > | < | | < < < < < < < | < | 4140 4141 4142 4143 4144 4145 4146 4147 4148 4149 4150 4151 4152 4153 4154 4155 4156 4157 4158 4159 4160 4161 4162 4163 4164 4165 4166 4167 4168 4169 4170 4171 4172 4173 4174 4175 4176 4177 4178 4179 4180 4181 4182 4183 4184 4185 4186 4187 4188 4189 4190 4191 | ** ** An existing WhereLoop entry might be overwritten if the new template ** 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 ** 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 ** 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; WhereInfo *pWInfo = pBuilder->pWInfo; sqlite3 *db = pWInfo->pParse->db; /* If pBuilder->pOrSet is defined, then only keep track of the costs ** and prereqs. */ if( pBuilder->pOrSet!=0 ){ #if WHERETRACE_ENABLED u16 n = pBuilder->pOrSet->n; int x = #endif whereOrInsert(pBuilder->pOrSet, pTemplate->prereq, pTemplate->rRun, pTemplate->nOut); #if WHERETRACE_ENABLED if( sqlite3WhereTrace & 0x8 ){ sqlite3DebugPrintf(x?" or-%d: ":" or-X: ", n); whereLoopPrint(pTemplate, pWInfo->pTabList); } #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){ |
︙ | ︙ | |||
4207 4208 4209 4210 4211 4212 4213 | } return SQLITE_OK; /* Jump here if the insert is a no-op */ whereLoopInsert_noop: #if WHERETRACE_ENABLED if( sqlite3WhereTrace & 0x8 ){ | | | 4271 4272 4273 4274 4275 4276 4277 4278 4279 4280 4281 4282 4283 4284 4285 | } return SQLITE_OK; /* Jump here if the insert is a no-op */ whereLoopInsert_noop: #if WHERETRACE_ENABLED if( sqlite3WhereTrace & 0x8 ){ sqlite3DebugPrintf("ins-noop: "); whereLoopPrint(pTemplate, pWInfo->pTabList); } #endif return SQLITE_OK; } /* |
︙ | ︙ | |||
4489 4490 4491 4492 4493 4494 4495 | } pProbe = &sPk; } rSize = whereCost(pSrc->pTab->nRowEst); rLogSize = estLog(rSize); /* Automatic indexes */ | | | 4553 4554 4555 4556 4557 4558 4559 4560 4561 4562 4563 4564 4565 4566 4567 | } pProbe = &sPk; } rSize = whereCost(pSrc->pTab->nRowEst); rLogSize = estLog(rSize); /* Automatic indexes */ if( !pBuilder->pOrSet && (pWInfo->pParse->db->flags & SQLITE_AutoIndex)!=0 && pSrc->pIndex==0 && !pSrc->viaCoroutine && !pSrc->notIndexed && !pSrc->isCorrelated ){ /* Generate auto-index WhereLoops */ |
︙ | ︙ | |||
4775 4776 4777 4778 4779 4780 4781 | WhereClause *pWC; WhereLoop *pNew; WhereTerm *pTerm, *pWCEnd; int rc = SQLITE_OK; int iCur; WhereClause tempWC; WhereLoopBuilder sSubBuild; | | | | < < | < < | > < | > > | > > > | > > > > > | | < | < < > > > | | | | > > > | | | < < | 4839 4840 4841 4842 4843 4844 4845 4846 4847 4848 4849 4850 4851 4852 4853 4854 4855 4856 4857 4858 4859 4860 4861 4862 4863 4864 4865 4866 4867 4868 4869 4870 4871 4872 4873 4874 4875 4876 4877 4878 4879 4880 4881 4882 4883 4884 4885 4886 4887 4888 4889 4890 4891 4892 4893 4894 4895 4896 4897 4898 4899 4900 4901 4902 4903 4904 4905 4906 4907 4908 4909 4910 4911 4912 4913 4914 4915 4916 4917 4918 4919 4920 4921 4922 4923 4924 4925 4926 4927 4928 4929 4930 4931 | WhereClause *pWC; WhereLoop *pNew; WhereTerm *pTerm, *pWCEnd; int rc = SQLITE_OK; int iCur; WhereClause tempWC; WhereLoopBuilder sSubBuild; WhereOrSet sSum, sCur, sPrev; struct SrcList_item *pItem; pWC = pBuilder->pWC; if( pWInfo->wctrlFlags & WHERE_AND_ONLY ) return SQLITE_OK; pWCEnd = pWC->a + pWC->nTerm; pNew = pBuilder->pNew; for(pTerm=pWC->a; pTerm<pWCEnd && rc==SQLITE_OK; pTerm++){ if( (pTerm->eOperator & WO_OR)!=0 && (pTerm->u.pOrInfo->indexable & pNew->maskSelf)!=0 ){ WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc; WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm]; WhereTerm *pOrTerm; int once = 1; int i, j; pItem = pWInfo->pTabList->a + pNew->iTab; iCur = pItem->iCursor; sSubBuild = *pBuilder; sSubBuild.pOrderBy = 0; sSubBuild.pOrSet = &sCur; for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){ if( (pOrTerm->eOperator & WO_AND)!=0 ){ sSubBuild.pWC = &pOrTerm->u.pAndInfo->wc; }else if( pOrTerm->leftCursor==iCur ){ tempWC.pWInfo = pWC->pWInfo; tempWC.pOuter = pWC; tempWC.op = TK_AND; tempWC.nTerm = 1; tempWC.a = pOrTerm; sSubBuild.pWC = &tempWC; }else{ continue; } sCur.n = 0; #ifndef SQLITE_OMIT_VIRTUALTABLE if( IsVirtual(pItem->pTab) ){ rc = whereLoopAddVirtual(&sSubBuild); for(i=0; i<sCur.n; i++) sCur.a[i].prereq |= mExtra; }else #endif { rc = whereLoopAddBtree(&sSubBuild, mExtra); } assert( rc==SQLITE_OK || sCur.n==0 ); if( sCur.n==0 ){ sSum.n = 0; break; }else if( once ){ whereOrMove(&sSum, &sCur); once = 0; }else{ whereOrMove(&sPrev, &sSum); sSum.n = 0; for(i=0; i<sPrev.n; i++){ for(j=0; j<sCur.n; j++){ whereOrInsert(&sSum, sPrev.a[i].prereq | sCur.a[j].prereq, whereCostAdd(sPrev.a[i].rRun, sCur.a[j].rRun), whereCostAdd(sPrev.a[i].nOut, sCur.a[j].nOut)); } } } } pNew->nLTerm = 1; pNew->aLTerm[0] = pTerm; pNew->wsFlags = WHERE_MULTI_OR; pNew->rSetup = 0; pNew->iSortIdx = 0; memset(&pNew->u, 0, sizeof(pNew->u)); for(i=0; rc==SQLITE_OK && i<sSum.n; i++){ /* TUNING: Multiple by 3.5 for the secondary table lookup */ pNew->rRun = sSum.a[i].rRun + 18; pNew->nOut = sSum.a[i].nOut; pNew->prereq = sSum.a[i].prereq; rc = whereLoopInsert(pBuilder, pNew); } } } return rc; } /* ** Add all WhereLoop objects for all tables |
︙ | ︙ |
Changes to test/where2.test.
︙ | ︙ | |||
694 695 696 697 698 699 700 701 702 703 | } } {4} do_test where2-11.4 { execsql { SELECT d FROM t11 WHERE c=7 OR (a=1 AND b=2) ORDER BY d; } } {4 8 10} finish_test | > > > > > > > > > > > | 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 | } } {4} do_test where2-11.4 { execsql { SELECT d FROM t11 WHERE c=7 OR (a=1 AND b=2) ORDER BY d; } } {4 8 10} # Verify that the OR clause is used in an outer loop even when # the OR clause scores slightly better on an inner loop. do_execsql_test where2-12.1 { CREATE TABLE t12(x INTEGER PRIMARY KEY, y); CREATE INDEX t12y ON t12(y); EXPLAIN QUERY PLAN SELECT a.x, b.x FROM t12 AS a JOIN t12 AS b ON a.y=b.x WHERE (b.x=$abc OR b.y=$abc); } {/.*SEARCH TABLE t12 AS b .*SEARCH TABLE t12 AS b .*/} finish_test |
Changes to test/where8.test.
︙ | ︙ | |||
208 209 210 211 212 213 214 215 | SELECT a, d FROM t1, t2 WHERE (a = 2 OR a = 3) AND d = a } } {2 2 3 3 0 0} do_test where8-3.5 { execsql_status { SELECT a, d FROM t1, t2 WHERE (a = 2 OR a = 3) AND (d = a OR e = 'sixteen') } | > | | | 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 | SELECT a, d FROM t1, t2 WHERE (a = 2 OR a = 3) AND d = a } } {2 2 3 3 0 0} do_test where8-3.5 { execsql_status { SELECT a, d FROM t1, t2 WHERE (a = 2 OR a = 3) AND (d = a OR e = 'sixteen') ORDER BY +a, +d; } } {2 2 2 4 3 3 3 4 0 1} do_test where8-3.6 { # The first part of the WHERE clause in this query, (a=2 OR a=3) is # transformed into "a IN (2, 3)". This is why the sort is required. # execsql_status { SELECT a, d FROM t1, t2 WHERE (a = 2 OR a = 3) AND (d = a OR e = 'sixteen') ORDER BY t1.rowid } } {2 2 2 4 3 3 3 4 0 1} do_test where8-3.7 { execsql_status { SELECT a, d FROM t1, t2 WHERE a = 2 AND (d = a OR e = 'sixteen') ORDER BY t1.rowid } } {/2 2 2 4 0 [01]/} do_test where8-3.8 { execsql_status { SELECT a, d FROM t1, t2 WHERE (a = 2 OR b = 'three') AND (d = a OR e = 'sixteen') ORDER BY t1.rowid } |
︙ | ︙ |