Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | In where.c, make findTerm() a wrapper around methods to a new WhereScan object which is capable of finding all suitable matching terms, not just the first. This check-in includes some prototype functions for building WhereLoop objects. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | nextgen-query-plan-exp |
Files: | files | file ages | folders |
SHA1: |
dd92b8fa929badaf2f79e8a00c83667a |
User & Date: | drh 2013-05-04 20:25:23.612 |
Context
2013-05-07
| ||
19:44 | Inserting a few WhereLoop objects without leaking memory. Costs are not correct. Inequality and IN constraints are not implemented. (check-in: e8881a8b2f user: drh tags: nextgen-query-plan-exp) | |
2013-05-04
| ||
20:25 | In where.c, make findTerm() a wrapper around methods to a new WhereScan object which is capable of finding all suitable matching terms, not just the first. This check-in includes some prototype functions for building WhereLoop objects. (check-in: dd92b8fa92 user: drh tags: nextgen-query-plan-exp) | |
2013-05-02
| ||
00:15 | Begin inserting some experimental code for the next generation query planner. (check-in: ccaf4c3f7e user: drh tags: nextgen-query-plan-exp) | |
Changes
Changes to src/where.c.
︙ | |||
38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | + + - + | typedef struct WhereMaskSet WhereMaskSet; typedef struct WhereOrInfo WhereOrInfo; typedef struct WhereAndInfo WhereAndInfo; typedef struct WhereCost WhereCost; typedef struct WhereLoop WhereLoop; typedef struct WherePath WherePath; typedef struct WhereTerm WhereTerm; typedef struct WhereLoopBuilder WhereLoopBuilder; typedef struct WhereScan WhereScan; /* ** Each instance of this object represents a way of evaluating one ** term of a join. The WhereClause object holds a table of these ** objects using (iTab,prereq,iOb,nOb) as the primary key. Note that the ** same join term might have multiple associated WhereLoop objects. */ struct WhereLoop { Bitmask prereq; /* Bitmask of other loops that must run first */ int iTab; /* Index of the table coded by this loop */ u16 iOb, nOb; /* ORDER BY terms satisfied by this strategy */ double rSetup; /* One-time setup cost (ex: create transient index) */ double rRun; /* Cost of running each loop */ double nOut; /* Estimated number of output rows */ u32 wsFlags; /* WHERE_* flags describing the plan */ u16 nEq; /* Number of equality constraints */ u16 nTerm; /* Number of entries in aTerm[] */ Index *pIndex; /* Index used */ |
︙ | |||
157 158 159 160 161 162 163 164 165 166 167 168 169 170 | 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 186 187 188 189 | + + + + + + + + + + + + + + + + + | #define TERM_OR_OK 0x40 /* Used during OR-clause processing */ #ifdef SQLITE_ENABLE_STAT3 # define TERM_VNULL 0x80 /* Manufactured x>NULL or x<=NULL term */ #else # define TERM_VNULL 0x00 /* Disabled if not using stat3 */ #endif /* ** An instance of the WhereScan object is used as an iterator for locating ** terms in the WHERE clause that are useful to the query planner. */ struct WhereScan { WhereTerm *pCurrent; /* Most recent match */ WhereClause *pOrigWC; /* Original, innermost WhereClause */ WhereClause *pWC; /* WhereClause currently being scanned */ char *zCollName; /* Must have this collating sequence, if not NULL */ char idxaff; /* Must match this affinity, if zCollName!=NULL */ unsigned char nEquiv; /* Number of entries in aEquiv[] */ unsigned char iEquiv; /* Next unused slot in aEquiv[] */ u32 opMask; /* Acceptable operators */ int k; /* Resume scanning at this->pWC->a[this->k] */ int aEquiv[22]; /* Cursor,Column pairs for equivalence classes */ }; /* ** An instance of the following structure holds all information about a ** WHERE clause. Mostly this is a container for one or more WhereTerms. ** ** Explanation of pOuter: For a WHERE clause of the form ** ** a AND ((b AND c) OR (d AND e)) AND f |
︙ | |||
242 243 244 245 246 247 248 249 250 251 252 253 254 255 | 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 | + + + + + + + + + + + + + | ** cost of pursuing that strategy. */ struct WhereCost { WherePlan plan; /* The lookup strategy */ double rCost; /* Overall cost of pursuing this search strategy */ Bitmask used; /* Bitmask of cursors used by this plan */ }; /* ** This object is a factory for WhereLoop objects for a particular query. */ struct WhereLoopBuilder { WhereInfo *pWInfo; /* Information about this WHERE */ sqlite3 *db; /* Database connection */ Parse *pParse; /* Parsing context */ WhereClause *pWC; /* WHERE clause terms */ SrcList *pTabList; /* FROM clause */ ExprList *pOrderBy; /* ORDER BY clause */ WhereLoop *pNew; /* Template WhereLoop */ }; /* ** Bitmasks for the operators that indices are able to exploit. An ** OR-ed combination of these values can be used when searching for ** terms in the where clause. */ #define WO_IN 0x001 |
︙ | |||
656 657 658 659 660 661 662 663 664 665 666 667 668 669 | 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 | + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + | assert( op!=TK_EQ || c==WO_EQ ); assert( op!=TK_LT || c==WO_LT ); assert( op!=TK_LE || c==WO_LE ); assert( op!=TK_GT || c==WO_GT ); assert( op!=TK_GE || c==WO_GE ); return c; } /* ** Advance to the next WhereTerm that matches according to the criteria ** established when the pScan object was initialized by whereScanInit(). ** Return NULL if there are no more matching WhereTerms. */ WhereTerm *whereScanNext(WhereScan *pScan){ int iCur; /* The cursor on the LHS of the term */ int iColumn; /* The column on the LHS of the term. -1 for IPK */ Expr *pX; /* An expression being tested */ WhereClause *pWC; /* Shorthand for pScan->pWC */ WhereTerm *pTerm; /* The term being tested */ while( pScan->iEquiv<=pScan->nEquiv ){ iCur = pScan->aEquiv[pScan->iEquiv-2]; iColumn = pScan->aEquiv[pScan->iEquiv-1]; while( (pWC = pScan->pWC)!=0 ){ for(pTerm=pWC->a+pScan->k; pScan->k<pWC->nTerm; pScan->k++, pTerm++){ if( pTerm->leftCursor==iCur && pTerm->u.leftColumn==iColumn ){ if( (pTerm->eOperator & WO_EQUIV)!=0 && pScan->nEquiv<ArraySize(pScan->aEquiv) ){ int j; pX = sqlite3ExprSkipCollate(pTerm->pExpr->pRight); assert( pX->op==TK_COLUMN ); for(j=0; j<pScan->nEquiv; j+=2){ if( pScan->aEquiv[j]==pX->iTable && pScan->aEquiv[j+1]==pX->iColumn ){ break; } } if( j==pScan->nEquiv ){ pScan->aEquiv[j] = pX->iTable; pScan->aEquiv[j+1] = pX->iColumn; pScan->nEquiv += 2; } } if( (pTerm->eOperator & pScan->opMask)!=0 ){ /* Verify the affinity and collating sequence match */ if( pScan->zCollName && (pTerm->eOperator & WO_ISNULL)==0 ){ CollSeq *pColl; pX = pTerm->pExpr; if( !sqlite3IndexAffinityOk(pX, pScan->idxaff) ){ continue; } assert(pX->pLeft); pColl = sqlite3BinaryCompareCollSeq(pWC->pParse, pX->pLeft, pX->pRight); if( pColl==0 ) pColl = pWC->pParse->db->pDfltColl; if( sqlite3StrICmp(pColl->zName, pScan->zCollName) ){ continue; } } pScan->pCurrent = pTerm; pScan->k++; return pTerm; } } } pWC = pScan->pWC = pScan->pWC->pOuter; pScan->k = 0; } pScan->pWC = pScan->pOrigWC; pScan->k = 0; pScan->iEquiv += 2; } pScan->pCurrent = 0; return 0; } /* ** Initialize a WHERE clause scanner object. Return a pointer to the ** first match. Return NULL if there are no matches. ** ** The scanner will be searching the WHERE clause pWC. It will look ** for terms of the form "X <op> <expr>" where X is column iColumn of table ** iCur. The <op> must be one of the operators described by opMask. ** ** If X is not the INTEGER PRIMARY KEY then X must be compatible with ** index pIdx. */ WhereTerm *whereScanInit( WhereScan *pScan, /* The WhereScan object being initialized */ WhereClause *pWC, /* The WHERE clause to be scanned */ int iCur, /* Cursor to scan for */ int iColumn, /* Column to scan for */ u32 opMask, /* Operator(s) to scan for */ Index *pIdx /* Must be compatible with this index */ ){ int j; memset(pScan, 0, sizeof(*pScan)); pScan->pOrigWC = pWC; pScan->pWC = pWC; if( pIdx && iColumn>=0 ){ pScan->idxaff = pIdx->pTable->aCol[iColumn].affinity; for(j=0; pIdx->aiColumn[j]!=iColumn; j++){ if( NEVER(j>=pIdx->nColumn) ) return 0; } pScan->zCollName = pIdx->azColl[j]; } pScan->opMask = opMask; pScan->aEquiv[0] = iCur; pScan->aEquiv[1] = iColumn; pScan->nEquiv = 2; pScan->iEquiv = 2; return whereScanNext(pScan); } /* ** Search for a term in the WHERE clause that is of the form "X <op> <expr>" ** where X is a reference to the iColumn of table iCur and <op> is one of ** the WO_xx operator codes specified by the op parameter. ** Return a pointer to the term. Return 0 if not found. ** |
︙ | |||
688 689 690 691 692 693 694 | 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 | - - - + + + - - - - - - - - - - + - - - - - - - + + - - - - - - + - - - - - - - + - - - - - - - - + - - - - - - - - - - - + - - + - - - - - - - - - - - + - - - + - - - - - - - - - | WhereClause *pWC, /* The WHERE clause to be searched */ int iCur, /* Cursor number of LHS */ int iColumn, /* Column number of LHS */ Bitmask notReady, /* RHS must not overlap with this mask */ u32 op, /* Mask of WO_xx values describing operator */ Index *pIdx /* Must be compatible with this index, if not NULL */ ){ |
︙ | |||
5054 5055 5056 5057 5058 5059 5060 5061 5062 5063 5064 5065 5066 5067 5068 5069 5070 5071 5072 5073 5074 | 5130 5131 5132 5133 5134 5135 5136 5137 5138 5139 5140 5141 5142 5143 5144 5145 5146 5147 5148 5149 5150 5151 5152 5153 5154 5155 5156 5157 5158 5159 5160 5161 5162 5163 5164 5165 5166 5167 5168 5169 5170 5171 5172 5173 5174 5175 5176 5177 5178 5179 5180 5181 5182 5183 5184 5185 5186 5187 5188 5189 5190 5191 5192 5193 5194 5195 5196 5197 5198 5199 5200 5201 5202 5203 5204 5205 5206 5207 5208 5209 5210 5211 5212 5213 5214 5215 5216 5217 5218 5219 5220 5221 5222 5223 5224 5225 5226 5227 5228 5229 5230 5231 5232 5233 5234 5235 5236 5237 5238 5239 5240 5241 5242 5243 5244 5245 5246 5247 5248 5249 5250 5251 5252 5253 5254 5255 5256 5257 5258 5259 5260 5261 5262 5263 5264 5265 5266 5267 5268 5269 5270 5271 5272 5273 5274 5275 5276 5277 5278 5279 5280 5281 5282 5283 5284 5285 5286 5287 5288 5289 5290 5291 5292 5293 5294 5295 5296 5297 5298 5299 5300 5301 5302 5303 5304 5305 5306 5307 5308 5309 5310 5311 5312 5313 5314 5315 5316 5317 5318 | + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + - - - + + + + + + + + + + - - + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + - - - + + + + + + + + + + + + + + + + + + + + + - - + + - - - - + + + - + - + - - + + + + - + - + + + | p = sqlite3DbMallocRaw(db, sizeof(WhereLoop)); if( p==0 ) return SQLITE_NOMEM; } *p = *pTemplate; p->pNextLoop = pWInfo->pLoops; pWInfo->pLoops = p; if( pTemplate->nTerm<=0 ) return SQLITE_OK; if( p->pIndex && p->pIndex->tnum==0 ) p->pIndex = 0; p->aTerm = sqlite3DbMallocRaw(db, pTemplate->nTerm*sizeof(p->aTerm[0])); if( p->aTerm==0 ){ p->nTerm = 0; sqlite3DbFree(db, p); return SQLITE_NOMEM; } memcpy(p->aTerm, pTemplate->aTerm, pTemplate->nTerm*sizeof(p->aTerm[0])); return SQLITE_OK; } /* ** We have so far matched pBuilder->pNew->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 ** INTEGER PRIMARY KEY. */ static void whereLoopAddBtreeIndex( WhereLoopBuilder *pBuilder, /* The WhereLoop factory */ struct SrcList_item *pSrc, /* FROM clause term being analyzed */ Index *pProbe, /* An index on pSrc */ int nInMul /* Number of iterations due to IN */ ){ sqlite3 *db; /* Database connection malloc context */ WhereLoop *pNew; /* Template WhereLoop under construction */ WhereTerm *pTerm; /* A WhereTerm under consideration */ int eqTermMask; /* Valid equality operators */ WhereScan scan; /* Iterator for WHERE terms */ db = pBuilder->db; pNew = pBuilder->pNew; if( db->mallocFailed ) return; if( pProbe->tnum<=0 || (pSrc->jointype & JT_LEFT)!=0 ){ eqTermMask = WO_EQ|WO_IN; }else{ eqTermMask = WO_EQ|WO_IN|WO_ISNULL; } if( pNew->nEq<pProbe->nColumn ){ int iCol; /* Index of the column in the table */ iCol = pProbe->aiColumn[pNew->nEq]; pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol, eqTermMask, iCol>=0 ? pProbe : 0); pNew->nEq++; for(; pTerm!=0; pTerm = whereScanNext(&scan)){ pNew->aTerm[pNew->nEq-1] = pTerm; } pNew->nEq--; } } /* ** Add all WhereLoop objects for the iTab-th table of the join. That ** table is guaranteed to be a b-tree table, not a virtual table. */ static void whereLoopAddBtree( |
︙ | |||
5230 5231 5232 5233 5234 5235 5236 5237 5238 5239 5240 5241 5242 5243 5244 5245 5246 5247 5248 5249 5250 5251 5252 5253 5254 | 5411 5412 5413 5414 5415 5416 5417 5418 5419 5420 5421 5422 5423 5424 5425 5426 5427 5428 5429 5430 5431 5432 5433 5434 5435 5436 5437 5438 5439 5440 5441 | + + + + + + | ){ int nByteWInfo; /* Num. bytes allocated for WhereInfo struct */ int nTabList; /* Number of elements in pTabList */ WhereInfo *pWInfo; /* Will become the return value of this function */ Vdbe *v = pParse->pVdbe; /* The virtual database engine */ Bitmask notReady; /* Cursors that are not yet positioned */ WhereBestIdx sWBI; /* Best index search context */ WhereLoopBuilder sWLB; /* The WhereLoop builder */ WhereMaskSet *pMaskSet; /* The expression mask set */ WhereLevel *pLevel; /* A single level in pWInfo->a[] */ int iFrom; /* First unused FROM clause element */ int andFlags; /* AND-ed combination of all pWC->a[].wtFlags */ int ii; /* Loop counter */ sqlite3 *db; /* Database connection */ /* Variable initialization */ memset(&sWBI, 0, sizeof(sWBI)); sWBI.pParse = pParse; memset(&sWLB, 0, sizeof(sWLB)); sWLB.pParse = pParse; sWLB.db = pParse->db; sWLB.pTabList = pTabList; sWLB.pOrderBy = pOrderBy; /* The number of tables in the FROM clause is limited by the number of ** bits in a Bitmask */ testcase( pTabList->nSrc==BMS ); if( pTabList->nSrc>BMS ){ sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS); |
︙ | |||
5286 5287 5288 5289 5290 5291 5292 5293 5294 5295 5296 5297 5298 5299 | 5473 5474 5475 5476 5477 5478 5479 5480 5481 5482 5483 5484 5485 5486 5487 5488 | + + | pWInfo->pTabList = pTabList; pWInfo->iBreak = sqlite3VdbeMakeLabel(v); pWInfo->pWC = sWBI.pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo]; pWInfo->wctrlFlags = wctrlFlags; pWInfo->savedNQueryLoop = pParse->nQueryLoop; pMaskSet = (WhereMaskSet*)&sWBI.pWC[1]; sWBI.aLevel = pWInfo->a; sWLB.pWInfo = pWInfo; sWLB.pWC = pWInfo->pWC; /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */ if( OptimizationDisabled(db, SQLITE_DistinctOpt) ) pDistinct = 0; /* Split the WHERE clause into separate subexpressions where each ** subexpression is separated by an AND operator. |
︙ | |||
5358 5359 5360 5361 5362 5363 5364 | 5547 5548 5549 5550 5551 5552 5553 5554 5555 5556 5557 5558 5559 5560 5561 | - + | if( pDistinct && isDistinctRedundant(pParse, pTabList, sWBI.pWC, pDistinct) ){ pDistinct = 0; pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE; } /* Construct the WhereLoop objects */ WHERETRACE(("*** Optimizer Start ***\n")); |
︙ |