Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Update the NGQP so that it can produce plans that include automatic indices. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | nextgen-query-plan-exp |
Files: | files | file ages | folders |
SHA1: |
586b55d8d7722de1c0530b3b832bae05 |
User & Date: | drh 2013-05-10 15:16:30.669 |
Context
2013-05-10
| ||
20:26 | Now generating OR-clause plans. (check-in: e17003fcfe user: drh tags: nextgen-query-plan-exp) | |
15:16 | Update the NGQP so that it can produce plans that include automatic indices. (check-in: 586b55d8d7 user: drh tags: nextgen-query-plan-exp) | |
03:30 | Factor out common operations into whereLoopAddAll(). Add stubs for missing features. (check-in: 0278e42061 user: drh tags: nextgen-query-plan-exp) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
285 286 287 288 289 290 291 292 293 294 295 296 297 298 | 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. */ | > | 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 | 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 */ int mxTerm; /* Maximum number of aTerm[] entries on pNew */ }; /* ** 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. */ |
︙ | ︙ | |||
5237 5238 5239 5240 5241 5242 5243 5244 5245 5246 5247 5248 5249 5250 | 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[] */ int iCol; /* Index of the column in the table */ int rc = SQLITE_OK; /* Return code */ db = pBuilder->db; pNew = pBuilder->pNew; if( db->mallocFailed ) return SQLITE_NOMEM; assert( (pNew->wsFlags & WHERE_VIRTUALTABLE)==0 ); assert( pNew->u.btree.nEq<pProbe->nColumn ); | > | 5238 5239 5240 5241 5242 5243 5244 5245 5246 5247 5248 5249 5250 5251 5252 | 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[] */ int iCol; /* Index of the column in the table */ int rc = SQLITE_OK; /* Return code */ double rLogSize; /* Logarithm of table size */ db = pBuilder->db; pNew = pBuilder->pNew; if( db->mallocFailed ) return SQLITE_NOMEM; assert( (pNew->wsFlags & WHERE_VIRTUALTABLE)==0 ); assert( pNew->u.btree.nEq<pProbe->nColumn ); |
︙ | ︙ | |||
5258 5259 5260 5261 5262 5263 5264 5265 5266 5267 5268 5269 5270 5271 5272 5273 5274 5275 | } iCol = pProbe->aiColumn[pNew->u.btree.nEq]; pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol, opMask, iCol>=0 ? pProbe : 0); savedLoop = *pNew; pNew->rSetup = (double)0; for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){ int nIn = 1; pNew->u.btree.nEq = savedLoop.u.btree.nEq; pNew->nTerm = savedLoop.nTerm; pNew->aTerm[pNew->nTerm++] = pTerm; pNew->prereq = (savedLoop.prereq | pTerm->prereqRight) & ~pNew->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 */ | > > | 5260 5261 5262 5263 5264 5265 5266 5267 5268 5269 5270 5271 5272 5273 5274 5275 5276 5277 5278 5279 | } iCol = pProbe->aiColumn[pNew->u.btree.nEq]; pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol, opMask, iCol>=0 ? pProbe : 0); savedLoop = *pNew; pNew->rSetup = (double)0; rLogSize = estLog(pProbe->aiRowEst[0]); for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){ int nIn = 1; pNew->u.btree.nEq = savedLoop.u.btree.nEq; pNew->nTerm = savedLoop.nTerm; if( pNew->nTerm>=pBuilder->mxTerm ) break; /* Repeated column in index */ pNew->aTerm[pNew->nTerm++] = pTerm; pNew->prereq = (savedLoop.prereq | pTerm->prereqRight) & ~pNew->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 */ |
︙ | ︙ | |||
5287 5288 5289 5290 5291 5292 5293 | }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; } | > > > > > > | > > > | 5291 5292 5293 5294 5295 5296 5297 5298 5299 5300 5301 5302 5303 5304 5305 5306 5307 5308 5309 5310 5311 5312 5313 5314 | }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 = rLogSize*nIn; /* Cost for nIn binary searches */ if( pNew->wsFlags & (WHERE_IDX_ONLY|WHERE_IPK) ){ pNew->rRun += pNew->nOut; /* Unit step cost to reach each row */ }else{ /* Each row involves a step of the index, then a binary search of ** the main table */ pNew->rRun += pNew->nOut*(1 + rLogSize); } /* TBD: Adjust nOut and rRun for STAT3 range values */ /* TBD: Adjust nOut for additional constraints */ rc = whereLoopInsert(pBuilder->pWInfo, pNew); if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0 && pNew->u.btree.nEq<pProbe->nColumn ){ whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul*nIn); } } |
︙ | ︙ | |||
5314 5315 5316 5317 5318 5319 5320 5321 5322 5323 5324 5325 5326 5327 | 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 */ WhereLoop *pNew; /* Template WhereLoop object */ int rc = SQLITE_OK; /* Return code */ pNew = pBuilder->pNew; pSrc = pBuilder->pTabList->a + pNew->iTab; if( pSrc->pIndex ){ /* An INDEXED BY clause specifies a particular index to use */ pProbe = pSrc->pIndex; | > > | 5327 5328 5329 5330 5331 5332 5333 5334 5335 5336 5337 5338 5339 5340 5341 5342 | 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 */ WhereLoop *pNew; /* Template WhereLoop object */ int rc = SQLITE_OK; /* Return code */ double rSize; /* number of rows in the table */ double rLogSize; /* Logarithm of the number of rows in the table */ pNew = pBuilder->pNew; pSrc = pBuilder->pTabList->a + pNew->iTab; if( pSrc->pIndex ){ /* An INDEXED BY clause specifies a particular index to use */ pProbe = pSrc->pIndex; |
︙ | ︙ | |||
5343 5344 5345 5346 5347 5348 5349 5350 5351 5352 5353 5354 5355 5356 5357 | if( pSrc->notIndexed==0 ){ /* 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->u.btree.nEq = 0; pNew->nTerm = 0; pNew->rSetup = (double)0; pNew->prereq = mExtra; pNew->u.btree.pIndex = 0; pNew->wsFlags = 0; | > > > > > > > > > > > > > > > > > > > > > > > > > > > < | > > < < | 5358 5359 5360 5361 5362 5363 5364 5365 5366 5367 5368 5369 5370 5371 5372 5373 5374 5375 5376 5377 5378 5379 5380 5381 5382 5383 5384 5385 5386 5387 5388 5389 5390 5391 5392 5393 5394 5395 5396 5397 5398 5399 5400 5401 5402 5403 5404 5405 5406 5407 5408 5409 5410 5411 | if( pSrc->notIndexed==0 ){ /* 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; } rSize = (double)pSrc->pTab->nRowEst; rLogSize = estLog(rSize); /* Automatic indexes */ if( (pBuilder->pParse->db->flags & SQLITE_AutoIndex)!=0 && !pSrc->viaCoroutine && !pSrc->notIndexed && !pSrc->isCorrelated ){ /* Generate auto-index WhereLoops */ WhereClause *pWC = pBuilder->pWC; WhereTerm *pTerm; WhereTerm *pWCEnd = pWC->a + pWC->nTerm; for(pTerm=pWC->a; rc==SQLITE_OK && pTerm<pWCEnd; pTerm++){ if( termCanDriveIndex(pTerm, pSrc, 0) ){ pNew->u.btree.nEq = 1; pNew->nTerm = 1; pNew->aTerm[0] = pTerm; pNew->rSetup = 2*rLogSize*pSrc->pTab->nRowEst; pNew->nOut = (double)10; pNew->rRun = rLogSize + pNew->nOut; pNew->wsFlags = WHERE_TEMP_INDEX; pNew->prereq = mExtra | pTerm->prereqRight; rc = whereLoopInsert(pBuilder->pWInfo, pNew); } } } /* Insert a full table scan */ pNew->u.btree.nEq = 0; pNew->nTerm = 0; pNew->rSetup = (double)0; pNew->prereq = mExtra; pNew->u.btree.pIndex = 0; pNew->wsFlags = 0; pNew->nOut = rSize; pNew->rRun = rSize + rLogSize; /* TBD: Reduce nOut using constraints */ rc = whereLoopInsert(pBuilder->pWInfo, pNew); /* Loop over all indices */ for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext){ pNew->u.btree.nEq = 0; pNew->nTerm = 0; if( pProbe->tnum<=0 ){ /* Integer primary key index */ |
︙ | ︙ | |||
5474 5475 5476 5477 5478 5479 5480 5481 5482 5483 5484 5485 5486 5487 | pIdxInfo->orderByConsumed = 0; /* ((double)2) In case of SQLITE_OMIT_FLOATING_POINT... */ pIdxInfo->estimatedCost = SQLITE_BIG_DBL / ((double)2); rc = vtabBestIndex(pParse, pTab, pIdxInfo); if( rc ) goto whereLoopAddVtab_exit; pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint; pNew->prereq = 0; for(i=0; i<pIdxInfo->nConstraint; i++) pNew->aTerm[i] = 0; mxTerm = -1; for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){ if( (iTerm = pUsage[i].argvIndex - 1)>=0 ){ j = pIdxCons->iTermOffset; if( iTerm>=pIdxInfo->nConstraint || j<0 | > | 5515 5516 5517 5518 5519 5520 5521 5522 5523 5524 5525 5526 5527 5528 5529 | pIdxInfo->orderByConsumed = 0; /* ((double)2) In case of SQLITE_OMIT_FLOATING_POINT... */ pIdxInfo->estimatedCost = SQLITE_BIG_DBL / ((double)2); rc = vtabBestIndex(pParse, pTab, pIdxInfo); if( rc ) goto whereLoopAddVtab_exit; pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint; pNew->prereq = 0; assert( pIdxInfo->nConstraint<=pBuilder->mxTerm ); for(i=0; i<pIdxInfo->nConstraint; i++) pNew->aTerm[i] = 0; mxTerm = -1; for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){ if( (iTerm = pUsage[i].argvIndex - 1)>=0 ){ j = pIdxCons->iTermOffset; if( iTerm>=pIdxInfo->nConstraint || j<0 |
︙ | ︙ | |||
5551 5552 5553 5554 5555 5556 5557 | int nTabList = pBuilder->pWInfo->nLevel; int rc = SQLITE_OK; WhereLoop *pNew; /* Loop over the tables in the join, from left to right */ pBuilder->pNew = pNew = sqlite3DbMallocZero(db, sizeof(WhereLoop)); if( pNew==0 ) return SQLITE_NOMEM; | > > > > > > | | 5593 5594 5595 5596 5597 5598 5599 5600 5601 5602 5603 5604 5605 5606 5607 5608 5609 5610 5611 5612 5613 | int nTabList = pBuilder->pWInfo->nLevel; int rc = SQLITE_OK; WhereLoop *pNew; /* Loop over the tables in the join, from left to right */ pBuilder->pNew = pNew = sqlite3DbMallocZero(db, sizeof(WhereLoop)); if( pNew==0 ) return SQLITE_NOMEM; pBuilder->mxTerm = pWC->nTerm+1; while( pWC->pOuter ){ pWC = pWC->pOuter; pBuilder->mxTerm += pWC->nTerm; } pWC = pBuilder->pWC; pNew->aTerm = sqlite3DbMallocZero(db,pBuilder->mxTerm*sizeof(pNew->aTerm[0])); if( pNew->aTerm==0 ){ rc = SQLITE_NOMEM; goto whereLoopAddAll_end; } for(iTab=0, pItem=pTabList->a; iTab<nTabList; iTab++, pItem++){ pNew->iTab = iTab; pNew->maskSelf = getMask(pWC->pMaskSet, pItem->iCursor); |
︙ | ︙ | |||
6327 6328 6329 6330 6331 6332 6333 6334 6335 6336 6337 6338 6339 6340 | */ assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 ); if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 && (andFlags & WHERE_UNIQUE)!=0 ){ pWInfo->okOnePass = 1; pWInfo->a[0].plan.wsFlags &= ~WHERE_IDX_ONLY; } /* Open all tables in the pTabList and any indices selected for ** searching those tables. */ sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */ notReady = ~(Bitmask)0; pWInfo->nRowOut = (double)1; for(ii=0, pLevel=pWInfo->a; ii<nTabList; ii++, pLevel++){ | > > > > > > > > > > > | 6375 6376 6377 6378 6379 6380 6381 6382 6383 6384 6385 6386 6387 6388 6389 6390 6391 6392 6393 6394 6395 6396 6397 6398 6399 | */ assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 ); if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 && (andFlags & WHERE_UNIQUE)!=0 ){ pWInfo->okOnePass = 1; pWInfo->a[0].plan.wsFlags &= ~WHERE_IDX_ONLY; } #if 0 /* Scaffolding: Check the new query plan against the old. Report any ** discrepencies */ for(ii=0; ii<nTabList; ii++){ if( pWInfo->a[ii].iFrom!=pWInfo->a[ii].pWLoop->iTab ){ sqlite3DebugPrintf("(QP-Mismatch)"); break; } } #endif /* Open all tables in the pTabList and any indices selected for ** searching those tables. */ sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */ notReady = ~(Bitmask)0; pWInfo->nRowOut = (double)1; for(ii=0, pLevel=pWInfo->a; ii<nTabList; ii++, pLevel++){ |
︙ | ︙ |