Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Update where.c with patches from sqlite3. src4 where.c is now based on sqlite3 artifact 1a26c37b7b. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
3f4a1c7648f1240f611e4b3b084a8f39 |
User & Date: | dan 2013-07-26 20:04:29.826 |
References
2013-07-29
| ||
12:31 | Fix an typo affecting virtual WHERE clause terms made in [3f4a1c7648]. check-in: 736b5e6a1a user: dan tags: trunk | |
Context
2013-07-26
| ||
21:13 | Remove unused fields from KeyInfo. Enhancement the EXPLAIN output for KeyInfo P4 columns. check-in: 9eb585660b user: drh tags: trunk | |
20:04 | Update where.c with patches from sqlite3. src4 where.c is now based on sqlite3 artifact 1a26c37b7b. check-in: 3f4a1c7648 user: dan tags: trunk | |
19:13 | Fix some issues with assigning costs to loops in where.c. check-in: faac50a266 user: dan tags: trunk | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
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; /* ** 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. | > > | 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | 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. |
︙ | ︙ | |||
149 150 151 152 153 154 155 156 157 158 159 160 161 162 | /**** 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(sqlite4*, WhereLoop*, int); /* ** Each instance of this object holds a sequence of WhereLoop objects ** that implement some or all of a query plan. | > > > > > > > > > > > > > > > > > > > > > | 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 184 185 | /**** 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(sqlite4*, WhereLoop*, int); /* ** Each instance of this object holds a sequence of WhereLoop objects ** that implement some or all of a query plan. |
︙ | ︙ | |||
364 365 366 367 368 369 370 | ** 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 */ | | | 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 | ** 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 |
︙ | ︙ | |||
507 508 509 510 511 512 513 514 515 516 517 518 519 520 | ** the rowids returned by a WHERE clause. Return FALSE if doing an ** UPDATE or DELETE might change subsequent WHERE clause results. */ int sqlite4WhereOkOnePass(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 */ ){ | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 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 589 590 591 592 | ** the rowids returned by a WHERE clause. Return FALSE if doing an ** UPDATE or DELETE might change subsequent WHERE clause results. */ int sqlite4WhereOkOnePass(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 */ ){ |
︙ | ︙ | |||
3865 3866 3867 3868 3869 3870 3871 3872 3873 3874 3875 3876 3877 3878 | ** 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; if( pWC->a[iTerm].wtFlags & (TERM_VIRTUAL|TERM_ORINFO) ) continue; if( (pWC->a[iTerm].eOperator & WO_ALL)==0 ) continue; pExpr = sqlite4ExprDup(pParse->db, pExpr, 0); pAndExpr = sqlite4ExprAnd(pParse->db, pAndExpr, pExpr); } if( pAndExpr ){ | > | 3937 3938 3939 3940 3941 3942 3943 3944 3945 3946 3947 3948 3949 3950 3951 | ** 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_VIRTUAL|TERM_ORINFO) ) continue; if( (pWC->a[iTerm].eOperator & WO_ALL)==0 ) continue; pExpr = sqlite4ExprDup(pParse->db, pExpr, 0); pAndExpr = sqlite4ExprAnd(pParse->db, pAndExpr, pExpr); } if( pAndExpr ){ |
︙ | ︙ | |||
4198 4199 4200 4201 4202 4203 4204 | ** ** 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. ** | | | | | | | < | < > > | > | < | | < < < < < < < | > < | 4271 4272 4273 4274 4275 4276 4277 4278 4279 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 4312 4313 4314 4315 4316 4317 4318 4319 4320 4321 4322 4323 4324 4325 | ** ** 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; sqlite4 *db = pWInfo->pParse->db; assert( pTemplate->u.btree.pIndex || !(pTemplate->wsFlags & WHERE_INDEXED) ); /* 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( sqlite4WhereTrace & 0x8 ){ sqlite4DebugPrintf(x?" or-%d: ":" or-X: ", n); whereLoopPrint(pTemplate, pWInfo->pTabList); } #endif return SQLITE4_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){ |
︙ | ︙ | |||
4339 4340 4341 4342 4343 4344 4345 | } return SQLITE4_OK; /* Jump here if the insert is a no-op */ whereLoopInsert_noop: #if WHERETRACE_ENABLED if( sqlite4WhereTrace & 0x8 ){ | | | 4405 4406 4407 4408 4409 4410 4411 4412 4413 4414 4415 4416 4417 4418 4419 | } return SQLITE4_OK; /* Jump here if the insert is a no-op */ whereLoopInsert_noop: #if WHERETRACE_ENABLED if( sqlite4WhereTrace & 0x8 ){ sqlite4DebugPrintf("ins-noop: "); whereLoopPrint(pTemplate, pWInfo->pTabList); } #endif return SQLITE4_OK; } |
︙ | ︙ | |||
4616 4617 4618 4619 4620 4621 4622 | } rSize = whereCost(pSrc->pTab->nRowEst); rLogSize = estLog(rSize); #ifndef SQLITE4_OMIT_AUTOMATIC_INDEX /* Automatic indexes */ | | | 4682 4683 4684 4685 4686 4687 4688 4689 4690 4691 4692 4693 4694 4695 4696 | } rSize = whereCost(pSrc->pTab->nRowEst); rLogSize = estLog(rSize); #ifndef SQLITE4_OMIT_AUTOMATIC_INDEX /* Automatic indexes */ if( !pBuilder->pOrSet && (pWInfo->pParse->db->flags & SQLITE4_AutoIndex)!=0 && pSrc->pIndex==0 #if 0 && !pSrc->viaCoroutine #endif && !pSrc->notIndexed && !pSrc->isCorrelated |
︙ | ︙ | |||
4696 4697 4698 4699 4700 4701 4702 | assert( (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || b==0 ); pNew->iSortIdx = b ? iSortIdx : 0; if( pProbe==pPk || b || (bCover && pProbe->bUnordered==0 && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 #if 0 | | | 4762 4763 4764 4765 4766 4767 4768 4769 4770 4771 4772 4773 4774 4775 4776 | assert( (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || b==0 ); pNew->iSortIdx = b ? iSortIdx : 0; if( pProbe==pPk || b || (bCover && pProbe->bUnordered==0 && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 #if 0 && sqlite4GlobalConfig.bUseCis && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan) #endif )){ if( pProbe==pPk ){ /* TUNING: Cost of full table scan is 3*(N + log2(N)). ** + The extra 3 factor is to encourage the use of indexed lookups ** over full scans. A smaller constant 2 is used for covering |
︙ | ︙ | |||
4917 4918 4919 4920 4921 4922 4923 | WhereClause *pWC; WhereLoop *pNew; WhereTerm *pTerm, *pWCEnd; int rc = SQLITE4_OK; int iCur; WhereClause tempWC; WhereLoopBuilder sSubBuild; | | | | < | < | | < | > | | > > | > > > | > > > > > | | < | < < > > > | | | | > > > | | | < < > | 4983 4984 4985 4986 4987 4988 4989 4990 4991 4992 4993 4994 4995 4996 4997 4998 4999 5000 5001 5002 5003 5004 5005 5006 5007 5008 5009 5010 5011 5012 5013 5014 5015 5016 5017 5018 5019 5020 5021 5022 5023 5024 5025 5026 5027 5028 5029 5030 5031 5032 5033 5034 5035 5036 5037 5038 5039 5040 5041 5042 5043 5044 5045 5046 5047 5048 5049 5050 5051 5052 5053 5054 5055 5056 5057 5058 5059 5060 5061 5062 5063 5064 5065 5066 5067 5068 5069 5070 5071 5072 5073 5074 5075 5076 5077 5078 5079 5080 5081 5082 | WhereClause *pWC; WhereLoop *pNew; WhereTerm *pTerm, *pWCEnd; int rc = SQLITE4_OK; int iCur; WhereClause tempWC; WhereLoopBuilder sSubBuild; WhereOrSet sSum, sCur, sPrev; struct SrcListItem *pItem; pWC = pBuilder->pWC; if( pWInfo->wctrlFlags & WHERE_AND_ONLY ) return SQLITE4_OK; pWCEnd = pWC->a + pWC->nTerm; pNew = pBuilder->pNew; for(pTerm=pWC->a; pTerm<pWCEnd && rc==SQLITE4_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 SQLITE4_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==SQLITE4_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==SQLITE4_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 */ static int whereLoopAddAll(WhereLoopBuilder *pBuilder){ WhereInfo *pWInfo = pBuilder->pWInfo; Bitmask mExtra = 0; |
︙ | ︙ | |||
5797 5798 5799 5800 5801 5802 5803 | pWInfo->pResultSet = pResultSet; pWInfo->iBreak = sqlite4VdbeMakeLabel(v); pWInfo->wctrlFlags = wctrlFlags; pWInfo->savedNQueryLoop = pParse->nQueryLoop; pMaskSet = &pWInfo->sMaskSet; sWLB.pWInfo = pWInfo; sWLB.pWC = &pWInfo->sWC; | | > | 5873 5874 5875 5876 5877 5878 5879 5880 5881 5882 5883 5884 5885 5886 5887 5888 | pWInfo->pResultSet = pResultSet; pWInfo->iBreak = sqlite4VdbeMakeLabel(v); pWInfo->wctrlFlags = wctrlFlags; pWInfo->savedNQueryLoop = pParse->nQueryLoop; pMaskSet = &pWInfo->sMaskSet; sWLB.pWInfo = pWInfo; sWLB.pWC = &pWInfo->sWC; sWLB.pNew = (WhereLoop*)(((char*)pWInfo)+nByteWInfo); assert( EIGHT_BYTE_ALIGNMENT(sWLB.pNew) ); whereLoopInit(sWLB.pNew); #ifdef SQLITE4_DEBUG sWLB.pNew->cId = '*'; #endif /* Split the WHERE clause into separate subexpressions where each ** subexpression is separated by an AND operator. |
︙ | ︙ |