Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Continued progress on generating good WhereLoop objects for the new query planner. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | nextgen-query-plan-exp |
Files: | files | file ages | folders |
SHA1: |
15cc8a16482777d8e138c4d0863faf8d |
User & Date: | drh 2013-05-07 23:06:23.630 |
Context
2013-05-08
| ||
03:05 | Add the NGQP solver. (check-in: 5d37587c50 user: drh tags: nextgen-query-plan-exp) | |
2013-05-07
| ||
23:06 | Continued progress on generating good WhereLoop objects for the new query planner. (check-in: 15cc8a1648 user: drh tags: nextgen-query-plan-exp) | |
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) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
311 312 313 314 315 316 317 318 319 320 321 322 323 324 | ** is set to WO_IN|WO_EQ. The WhereLevel.wsFlags field can then be used as ** the "op" parameter to findTerm when we are resolving equality constraints. ** ISNULL constraints will then not be used on the right table of a left ** join. Tickets #2177 and #2189. */ #define WHERE_ROWID_EQ 0x00001000 /* rowid=EXPR or rowid IN (...) */ #define WHERE_ROWID_RANGE 0x00002000 /* rowid<EXPR and/or rowid>EXPR */ #define WHERE_COLUMN_EQ 0x00010000 /* x=EXPR or x IN (...) or x IS NULL */ #define WHERE_COLUMN_RANGE 0x00020000 /* x<EXPR and/or x>EXPR */ #define WHERE_COLUMN_IN 0x00040000 /* x IN (...) */ #define WHERE_COLUMN_NULL 0x00080000 /* x IS NULL */ #define WHERE_INDEXED 0x000f0000 /* Anything that uses an index */ #define WHERE_NOT_FULLSCAN 0x100f3000 /* Does not do a full table scan */ #define WHERE_IN_ABLE 0x080f1000 /* Able to support an IN operator */ | > | 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 | ** is set to WO_IN|WO_EQ. The WhereLevel.wsFlags field can then be used as ** the "op" parameter to findTerm when we are resolving equality constraints. ** ISNULL constraints will then not be used on the right table of a left ** join. Tickets #2177 and #2189. */ #define WHERE_ROWID_EQ 0x00001000 /* rowid=EXPR or rowid IN (...) */ #define WHERE_ROWID_RANGE 0x00002000 /* rowid<EXPR and/or rowid>EXPR */ #define WHERE_IPK 0x00004000 /* x is the INTEGER PRIMARY KEY */ #define WHERE_COLUMN_EQ 0x00010000 /* x=EXPR or x IN (...) or x IS NULL */ #define WHERE_COLUMN_RANGE 0x00020000 /* x<EXPR and/or x>EXPR */ #define WHERE_COLUMN_IN 0x00040000 /* x IN (...) */ #define WHERE_COLUMN_NULL 0x00080000 /* x IS NULL */ #define WHERE_INDEXED 0x000f0000 /* Anything that uses an index */ #define WHERE_NOT_FULLSCAN 0x100f3000 /* Does not do a full table scan */ #define WHERE_IN_ABLE 0x080f1000 /* Able to support an IN operator */ |
︙ | ︙ | |||
706 707 708 709 710 711 712 713 714 715 716 717 718 719 | 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 ); | > > > > > > > > > | 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 | 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->iParent>=0 ){ WhereTerm *pParent = &pWC->a[pTerm->iParent]; int j; for(j=pScan->iEquiv-4; j>=0; j-=2 ){ if( pParent->leftCursor==pScan->aEquiv[j] && pParent->u.leftColumn==pScan->aEquiv[j+1] ) break; } if( j>=0 ) continue; } 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 ); |
︙ | ︙ | |||
5087 5088 5089 5090 5091 5092 5093 | ** 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 no the template. */ static int whereLoopInsert(WhereInfo *pWInfo, WhereLoop *pTemplate){ | | | 5097 5098 5099 5100 5101 5102 5103 5104 5105 5106 5107 5108 5109 5110 5111 | ** 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 no the template. */ static int whereLoopInsert(WhereInfo *pWInfo, WhereLoop *pTemplate){ WhereLoop **ppPrev, *p, *pNext = 0, *pToFree = 0; sqlite3 *db = pWInfo->pParse->db; /* 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 ) continue; |
︙ | ︙ | |||
5113 5114 5115 5116 5117 5118 5119 | && p->nOb<=pTemplate->nOb && p->iOb==pTemplate->iOb && p->rSetup>=pTemplate->rSetup && p->rRun>=pTemplate->rRun ){ /* Overwrite an existing WhereLoop with a better one */ sqlite3DbFree(db, p->aTerm); | | | | | | > | > | | > > > > | | | | > > > | | < | > > > > > > > > > > > > | > | | | | > | | > | > | | | 5123 5124 5125 5126 5127 5128 5129 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 | && p->nOb<=pTemplate->nOb && p->iOb==pTemplate->iOb && p->rSetup>=pTemplate->rSetup && p->rRun>=pTemplate->rRun ){ /* Overwrite an existing WhereLoop with a better one */ sqlite3DbFree(db, p->aTerm); pNext = p->pNextLoop; break; } } /* 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. */ if( p==0 ){ p = pToFree = sqlite3DbMallocRaw(db, sizeof(WhereLoop)); if( p==0 ) return SQLITE_NOMEM; } *p = *pTemplate; p->pNextLoop = pNext; *ppPrev = p; p->aTerm = 0; if( p->pIndex && p->pIndex->tnum==0 ) p->pIndex = 0; if( pTemplate->nTerm<=0 ) return SQLITE_OK; p->aTerm = sqlite3DbMallocRaw(db, pTemplate->nTerm*sizeof(p->aTerm[0])); if( p->aTerm==0 ){ p->nTerm = 0; sqlite3DbFree(db, pToFree); 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 */ Bitmask maskSelf, /* Bitmask for table being scanned */ 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 opMask; /* Valid operators for constraints */ WhereScan scan; /* Iterator for WHERE terms */ WhereLoop savedLoop; /* Saved original content of pNew[] */ db = pBuilder->db; pNew = pBuilder->pNew; if( db->mallocFailed ) return; assert( pNew->nEq<pProbe->nColumn ); assert( (pNew->wsFlags & WHERE_TOP_LIMIT)==0 ); if( pNew->wsFlags & WHERE_BTM_LIMIT ){ opMask = WO_LT|WO_LE; }else if( pProbe->tnum<=0 || (pSrc->jointype & JT_LEFT)!=0 ){ opMask = WO_EQ|WO_IN|WO_GT|WO_GE|WO_LT|WO_LE; }else{ opMask = WO_EQ|WO_IN|WO_ISNULL|WO_GT|WO_GE|WO_LT|WO_LE; } 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, opMask, iCol>=0 ? pProbe : 0); savedLoop = *pNew; pNew->rSetup = (double)0; for(; pTerm!=0; pTerm = whereScanNext(&scan)){ int nIn = 1; pNew->nEq = savedLoop.nEq; pNew->nTerm = savedLoop.nTerm; pNew->aTerm[pNew->nTerm++] = pTerm; pNew->prereq = (savedLoop.prereq | pTerm->prereqRight) & ~maskSelf; if( pTerm->eOperator & WO_IN ){ Expr *pExpr = pTerm->pExpr; pNew->wsFlags |= WHERE_COLUMN_IN; if( ExprHasProperty(pExpr, EP_xIsSelect) ){ /* "x IN (SELECT ...)": Assume the SELECT returns 25 rows */ nIn = 25; }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){ /* "x IN (value, value, ...)" */ nIn = pExpr->x.pList->nExpr; } pNew->nEq++; pNew->nOut = (double)pProbe->aiRowEst[pNew->nEq] * nInMul * nIn; }else if( pTerm->eOperator & (WO_EQ|WO_ISNULL) ){ pNew->wsFlags |= WHERE_COLUMN_EQ; pNew->nEq++; pNew->nOut = (double)pProbe->aiRowEst[pNew->nEq] * nInMul; }else if( pTerm->eOperator & (WO_GT|WO_GE) ){ pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_BTM_LIMIT; pNew->nOut = savedLoop.nOut/3; }else if( pTerm->eOperator & (WO_LT|WO_LE) ){ pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_TOP_LIMIT; pNew->nOut = savedLoop.nOut/3; } pNew->rRun = pNew->nOut + estLog(pProbe->aiRowEst[0])*nIn; whereLoopInsert(pBuilder->pWInfo, pNew); if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0 && pNew->nEq<pProbe->nColumn ){ whereLoopAddBtreeIndex(pBuilder, maskSelf, pSrc, pProbe, nInMul*nIn); } } *pNew = savedLoop; } } /* |
︙ | ︙ | |||
5218 5219 5220 5221 5222 5223 5224 5225 5226 5227 5228 5229 5230 5231 5232 5233 5234 5235 | Index *pProbe; /* An index we are evaluating */ Index sPk; /* A fake index object for the primary key */ tRowcnt aiRowEstPk[2]; /* The aiRowEst[] value for the sPk index */ int aiColumnPk = -1; /* The aColumn[] value for the sPk index */ struct SrcList_item *pSrc; /* The FROM clause btree term to add */ sqlite3 *db; /* The database connection */ WhereLoop *pNew; /* Template WhereLoop object */ pNew = pBuilder->pNew; db = pBuilder->db; pSrc = pBuilder->pTabList->a + iTab; if( pSrc->pIndex ){ /* An INDEXED BY clause specifies a particular index to use */ pProbe = pSrc->pIndex; }else{ /* There is no INDEXED BY clause. Create a fake Index object in local ** variable sPk to represent the rowid primary key index. Make this | > > | 5252 5253 5254 5255 5256 5257 5258 5259 5260 5261 5262 5263 5264 5265 5266 5267 5268 5269 5270 5271 | Index *pProbe; /* An index we are evaluating */ Index sPk; /* A fake index object for the primary key */ tRowcnt aiRowEstPk[2]; /* The aiRowEst[] value for the sPk index */ int aiColumnPk = -1; /* The aColumn[] value for the sPk index */ struct SrcList_item *pSrc; /* The FROM clause btree term to add */ sqlite3 *db; /* The database connection */ WhereLoop *pNew; /* Template WhereLoop object */ Bitmask maskSelf; /* Mask for iTab */ pNew = pBuilder->pNew; db = pBuilder->db; pSrc = pBuilder->pTabList->a + iTab; maskSelf = getMask(pBuilder->pWC->pMaskSet, iTab); if( pSrc->pIndex ){ /* An INDEXED BY clause specifies a particular index to use */ pProbe = pSrc->pIndex; }else{ /* There is no INDEXED BY clause. Create a fake Index object in local ** variable sPk to represent the rowid primary key index. Make this |
︙ | ︙ | |||
5249 5250 5251 5252 5253 5254 5255 5256 5257 5258 5259 5260 5261 5262 5263 5264 5265 5266 5267 5268 5269 | /* The real indices of the table are only considered if the ** NOT INDEXED qualifier is omitted from the FROM clause */ sPk.pNext = pFirst; } pProbe = &sPk; } /* Loop over all indices */ for(; pProbe; pProbe=pProbe->pNext){ WhereTerm **paTerm; pNew->prereq = mExtra; pNew->iTab = iTab; pNew->nEq = 0; pNew->nTerm = 0; paTerm = sqlite3DbRealloc(db, pNew->aTerm, (pProbe->nColumn+1)*sizeof(pNew->aTerm[0])); if( paTerm==0 ) break; pNew->aTerm = paTerm; pNew->pIndex = pProbe; | > > > > > > > > > > > > > > > > > > > > > > > > > > > | < < < < < < < < < | 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 5319 5320 5321 5322 5323 5324 5325 5326 5327 5328 5329 5330 5331 5332 5333 5334 5335 5336 5337 5338 5339 5340 5341 5342 5343 5344 5345 | /* The real indices of the table are only considered if the ** NOT INDEXED qualifier is omitted from the FROM clause */ sPk.pNext = pFirst; } pProbe = &sPk; } /* Insert a full table scan */ pNew->iTab = iTab; pNew->nEq = 0; pNew->nTerm = 0; pNew->rSetup = (double)0; pNew->prereq = 0; pNew->pIndex = 0; pNew->wsFlags = 0; pNew->iOb = pNew->nOb = 0; pNew->rRun = (double)pSrc->pTab->nRowEst; pNew->nOut = (double)pSrc->pTab->nRowEst; whereLoopInsert(pBuilder->pWInfo, pNew); /* Loop over all indices */ for(; pProbe; pProbe=pProbe->pNext){ WhereTerm **paTerm; pNew->prereq = mExtra; pNew->iTab = iTab; pNew->nEq = 0; pNew->nTerm = 0; if( pProbe->tnum<=0 ){ /* Integer primary key index */ pNew->wsFlags = WHERE_IPK; }else{ Bitmask m = pSrc->colUsed; int j; for(j=pProbe->nColumn-1; j>=0; j--){ int x = pProbe->aiColumn[j]; if( x<BMS-1 ){ m &= ~(((Bitmask)1)<<x); } } pNew->wsFlags = m==0 ? WHERE_IDX_ONLY : 0; } paTerm = sqlite3DbRealloc(db, pNew->aTerm, (pProbe->nColumn+1)*sizeof(pNew->aTerm[0])); if( paTerm==0 ) break; pNew->aTerm = paTerm; pNew->pIndex = pProbe; whereLoopAddBtreeIndex(pBuilder, maskSelf, pSrc, pProbe, 1); /* If there was an INDEXED BY clause, then only that one index is ** considered. */ if( pSrc->pIndex ) break; } } /* ** Add all WhereLoop objects for the iTab-th table of the join. That ** table is guaranteed to be a virtual table. */ static void whereLoopAddVirtual( |
︙ | ︙ | |||
5574 5575 5576 5577 5578 5579 5580 | if( sqlite3WhereTrace ){ WhereLoop *p; int nb = 2*((nTabList+15)/16); for(p=pWInfo->pLoops; p; p=p->pNextLoop){ struct SrcList_item *pItem = pTabList->a + p->iTab; Table *pTab = pItem->pTab; sqlite3DebugPrintf("%02d.%0*llx", p->iTab, nb, p->prereq); | | | | | | 5628 5629 5630 5631 5632 5633 5634 5635 5636 5637 5638 5639 5640 5641 5642 5643 5644 5645 5646 5647 5648 5649 5650 5651 | if( sqlite3WhereTrace ){ WhereLoop *p; int nb = 2*((nTabList+15)/16); for(p=pWInfo->pLoops; p; p=p->pNextLoop){ struct SrcList_item *pItem = pTabList->a + p->iTab; Table *pTab = pItem->pTab; sqlite3DebugPrintf("%02d.%0*llx", p->iTab, nb, p->prereq); sqlite3DebugPrintf(" %6s", pItem->zAlias ? pItem->zAlias : pTab->zName); if( p->pIndex ){ sqlite3DebugPrintf(".%-8s %2d", p->pIndex->zName, p->nEq); }else{ sqlite3DebugPrintf("%12s",""); } sqlite3DebugPrintf(" fg %08x OB %d,%d N %2d", p->wsFlags, p->iOb, p->nOb, p->nTerm); sqlite3DebugPrintf(" cost %.4g,%.4g,%.4g\n", p->prereq, p->rSetup, p->rRun, p->nOut); } } #endif /* Chose the best index to use for each table in the FROM clause. ** |
︙ | ︙ |