Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Work toward improving the NGQP's ability to optimize out ORDER BY clauses. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | nextgen-query-plan-exp |
Files: | files | file ages | folders |
SHA1: |
67367f1e1f0c3eb6be65eea9873910aa |
User & Date: | drh 2013-05-21 15:52:07.219 |
Context
2013-05-21
| ||
19:23 | Enhanced "wheretrace" output in the NGQP solver routine. (check-in: 04dfb85a2a user: drh tags: nextgen-query-plan-exp) | |
15:52 | Work toward improving the NGQP's ability to optimize out ORDER BY clauses. (check-in: 67367f1e1f user: drh tags: nextgen-query-plan-exp) | |
2013-05-20
| ||
15:14 | Merge in all trunk changes up through the 3.7.17 release. (check-in: 14ab6675e5 user: drh tags: nextgen-query-plan-exp) | |
Changes
Changes to src/sqliteInt.h.
︙ | ︙ | |||
1915 1916 1917 1918 1919 1920 1921 | ** But sqlite3SrcListShiftJoinType() later shifts the jointypes so that each ** jointype expresses the join between the table and the previous table. ** ** In the colUsed field, the high-order bit (bit 63) is set if the table ** contains more than 63 columns and the 64-th or later column is used. */ struct SrcList { | | | | 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 | ** But sqlite3SrcListShiftJoinType() later shifts the jointypes so that each ** jointype expresses the join between the table and the previous table. ** ** In the colUsed field, the high-order bit (bit 63) is set if the table ** contains more than 63 columns and the 64-th or later column is used. */ struct SrcList { u8 nSrc; /* Number of tables or subqueries in the FROM clause */ u8 nAlloc; /* Number of entries allocated in a[] below */ struct SrcList_item { Schema *pSchema; /* Schema to which this item is fixed */ char *zDatabase; /* Name of database holding this table */ char *zName; /* Name of the table */ char *zAlias; /* The "B" part of a "A AS B" phrase. zName is the "A" */ Table *pTab; /* An SQL table corresponding to zName */ Select *pSelect; /* A SELECT statement used in place of a table name */ |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
52 53 54 55 56 57 58 | ** term of a join. The WhereClause object holds a table of these ** objects using (maskSelf,prereq,) 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 */ Bitmask maskSelf; /* Bitmask identifying table iTab */ | | > | 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | ** term of a join. The WhereClause object holds a table of these ** objects using (maskSelf,prereq,) 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 */ Bitmask maskSelf; /* Bitmask identifying table iTab */ u8 iTab; /* Position in FROM clause of table coded by this loop */ u8 iSortIdx; /* Sorting index number. 0==None */ u16 nTerm; /* Number of entries in aTerm[] */ u32 wsFlags; /* WHERE_* flags describing the plan */ double rSetup; /* One-time setup cost (ex: create transient index) */ double rRun; /* Cost of running each loop */ double nOut; /* Estimated number of output rows */ union { struct { /* Information for internal btree tables */ |
︙ | ︙ | |||
1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 | struct SrcList_item *pSrc, /* Table we are trying to access */ Bitmask notReady /* Tables in outer loops of the join */ ){ char aff; if( pTerm->leftCursor!=pSrc->iCursor ) return 0; if( (pTerm->eOperator & WO_EQ)==0 ) return 0; if( (pTerm->prereqRight & notReady)!=0 ) return 0; aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity; if( !sqlite3IndexAffinityOk(pTerm->pExpr, aff) ) return 0; return 1; } #endif #ifndef SQLITE_OMIT_AUTOMATIC_INDEX | > | 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 | struct SrcList_item *pSrc, /* Table we are trying to access */ Bitmask notReady /* Tables in outer loops of the join */ ){ char aff; if( pTerm->leftCursor!=pSrc->iCursor ) return 0; if( (pTerm->eOperator & WO_EQ)==0 ) return 0; if( (pTerm->prereqRight & notReady)!=0 ) return 0; if( pTerm->u.leftColumn<0 ) return 0; aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity; if( !sqlite3IndexAffinityOk(pTerm->pExpr, aff) ) return 0; return 1; } #endif #ifndef SQLITE_OMIT_AUTOMATIC_INDEX |
︙ | ︙ | |||
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 | ** Insert or replace a WhereLoop entry using the template supplied. ** ** 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(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){ WhereLoop **ppPrev, *p, *pNext = 0, *pToFree = 0; WhereTerm **paTerm = 0; sqlite3 *db = pBuilder->db; WhereInfo *pWInfo = pBuilder->pWInfo; if( (p = pBuilder->pBest)!=0 ){ if( p->maskSelf!=0 ){ if( p->rRun+p->rSetup < pTemplate->rRun+pTemplate->rSetup ){ return SQLITE_OK; } if( p->rRun+p->rSetup == pTemplate->rRun+pTemplate->rSetup && p->prereq <= pTemplate->prereq ){ return SQLITE_OK; } } *p = *pTemplate; p->aTerm = 0; p->u.vtab.needFree = 0; 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){ | > > > > > > > > > > > > > > > > > > > > | | 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 | ** Insert or replace a WhereLoop entry using the template supplied. ** ** 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. ** ** If pBuilder->pBest is not NULL then we only care about the very ** best template and that template should be stored in pBuilder->pBest. ** If pBuilder->pBest is NULL then a list of the best templates are stored ** in pBuilder->pWInfo->pLoops. ** ** When accumulating multiple loops (when pBuilder->pBest 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 */ static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){ WhereLoop **ppPrev, *p, *pNext = 0, *pToFree = 0; WhereTerm **paTerm = 0; sqlite3 *db = pBuilder->db; WhereInfo *pWInfo = pBuilder->pWInfo; /* If pBuilder->pBest is defined, then only keep track of the single ** best WhereLoop. pBuilder->pBest->maskSelf==0 indicates that no ** prior WhereLoops have been evaluated and that the current pTemplate ** is therefore the first and hence the best and should be retained. */ if( (p = pBuilder->pBest)!=0 ){ if( p->maskSelf!=0 ){ if( p->rRun+p->rSetup < pTemplate->rRun+pTemplate->rSetup ){ return SQLITE_OK; } if( p->rRun+p->rSetup == pTemplate->rRun+pTemplate->rSetup && p->prereq <= pTemplate->prereq ){ return SQLITE_OK; } } *p = *pTemplate; p->aTerm = 0; p->u.vtab.needFree = 0; 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){ if( p->iTab!=pTemplate->iTab || p->iSortIdx!=pTemplate->iSortIdx ) continue; if( (p->prereq & pTemplate->prereq)==p->prereq && p->rSetup<=pTemplate->rSetup && p->rRun<=pTemplate->rRun ){ /* Already holding an equal or better WhereLoop. ** Return without changing or adding anything */ return SQLITE_OK; |
︙ | ︙ | |||
5234 5235 5236 5237 5238 5239 5240 | p->pNextLoop = pNext; *ppPrev = p; p->aTerm = paTerm; if( p->nTerm ){ memcpy(p->aTerm, pTemplate->aTerm, p->nTerm*sizeof(p->aTerm[0])); } if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){ | | | 5256 5257 5258 5259 5260 5261 5262 5263 5264 5265 5266 5267 5268 5269 5270 | p->pNextLoop = pNext; *ppPrev = p; p->aTerm = paTerm; if( p->nTerm ){ memcpy(p->aTerm, pTemplate->aTerm, p->nTerm*sizeof(p->aTerm[0])); } if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){ if( p->u.btree.pIndex && p->u.btree.pIndex && p->u.btree.pIndex->tnum==0 ){ p->u.btree.pIndex = 0; } }else{ pTemplate->u.vtab.needFree = 0; } return SQLITE_OK; } |
︙ | ︙ | |||
5337 5338 5339 5340 5341 5342 5343 5344 5345 5346 5347 5348 5349 5350 5351 5352 5353 5354 5355 5356 5357 5358 5359 5360 5361 5362 | ){ whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul*nIn); } } *pNew = savedLoop; return rc; } /* ** Add all WhereLoop objects a single table of the join were the table ** is idenfied by pBuilder->pNew->iTab. That table is guaranteed to be ** a b-tree table, not a virtual table. */ static int whereLoopAddBtree( WhereLoopBuilder *pBuilder, /* WHERE clause information */ Bitmask mExtra /* Extra prerequesites for using this table */ ){ 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 */ | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | | 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 5412 5413 5414 5415 5416 5417 5418 5419 5420 5421 5422 5423 5424 | ){ whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul*nIn); } } *pNew = savedLoop; return rc; } /* ** Return True if it is possible that pIndex might be useful in ** implementing the ORDER BY clause in pBuilder. ** ** Return False if pBuilder does not contain an ORDER BY clause or ** if there is no way for pIndex to be useful in implementing that ** ORDER BY clause. */ static int indexMightHelpWithOrderBy( WhereLoopBuilder *pBuilder, Index *pIndex, int iCursor ){ ExprList *pOB; int iCol; int ii; if( (pOB = pBuilder->pOrderBy)==0 ) return 0; iCol = pIndex->aiColumn[0]; for(ii=0; ii<pOB->nExpr; ii++){ Expr *pExpr = pOB->a[ii].pExpr; if( pExpr->op!=TK_COLUMN ) return 0; if( pExpr->iTable==iCursor ){ if( pExpr->iColumn==iCol ) return 1; return 0; } } return 0; } /* ** Add all WhereLoop objects a single table of the join were the table ** is idenfied by pBuilder->pNew->iTab. That table is guaranteed to be ** a b-tree table, not a virtual table. */ static int whereLoopAddBtree( WhereLoopBuilder *pBuilder, /* WHERE clause information */ Bitmask mExtra /* Extra prerequesites for using this table */ ){ 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 */ int iSortIdx = 0; /* Index number */ int b; /* A boolean value */ 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; assert( !IsVirtual(pSrc->pTab) ); if( pSrc->pIndex ){ /* An INDEXED BY clause specifies a particular index to use */ pProbe = pSrc->pIndex; |
︙ | ︙ | |||
5415 5416 5417 5418 5419 5420 5421 | pNew->wsFlags = WHERE_TEMP_INDEX; pNew->prereq = mExtra | pTerm->prereqRight; rc = whereLoopInsert(pBuilder, pNew); } } } | | > > | | > | | | < < < < < | < < < < < > > > > > > | | > > > | > > > | > | 5469 5470 5471 5472 5473 5474 5475 5476 5477 5478 5479 5480 5481 5482 5483 5484 5485 5486 5487 5488 5489 5490 5491 5492 5493 5494 5495 5496 5497 5498 5499 5500 5501 5502 5503 5504 5505 5506 5507 5508 5509 5510 5511 5512 5513 5514 5515 5516 5517 5518 5519 5520 5521 | pNew->wsFlags = WHERE_TEMP_INDEX; pNew->prereq = mExtra | pTerm->prereqRight; rc = whereLoopInsert(pBuilder, pNew); } } } /* Loop over all indices */ for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext, iSortIdx++){ pNew->u.btree.nEq = 0; pNew->nTerm = 0; pNew->iSortIdx = 0; pNew->rSetup = (double)0; pNew->prereq = mExtra; pNew->u.btree.pIndex = pProbe; b = indexMightHelpWithOrderBy(pBuilder, pProbe, pSrc->iCursor); if( pProbe->tnum<=0 ){ /* Integer primary key index */ pNew->wsFlags = WHERE_IPK; /* Full table scan */ pNew->nOut = rSize; pNew->rRun = (rSize + rLogSize)*(3+b); /* 4x penalty for a full-scan */ rc = whereLoopInsert(pBuilder, pNew); if( rc ) break; }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; /* Full scan via index */ if( m==0 || b ){ pNew->iSortIdx = b ? iSortIdx : 0; pNew->nOut = rSize; pNew->rRun = (m==0) ? (rSize + rLogSize)*(1+b) : (rSize*rLogSize); rc = whereLoopInsert(pBuilder, pNew); if( rc ) break; } } rc = whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, 1); /* If there was an INDEXED BY clause, then only that one index is ** considered. */ if( pSrc->pIndex ) break; } return rc; |
︙ | ︙ | |||
5677 5678 5679 5680 5681 5682 5683 5684 5685 5686 5687 5688 5689 5690 | pNew->nTerm = 1; pNew->aTerm[0] = pTerm; pNew->wsFlags = WHERE_MULTI_OR; pNew->rSetup = (double)0; pNew->rRun = rTotal; pNew->nOut = nRow; pNew->prereq = prereq; rc = whereLoopInsert(pBuilder, pNew); } } return rc; } /* | > | 5737 5738 5739 5740 5741 5742 5743 5744 5745 5746 5747 5748 5749 5750 5751 | pNew->nTerm = 1; pNew->aTerm[0] = pTerm; pNew->wsFlags = WHERE_MULTI_OR; pNew->rSetup = (double)0; pNew->rRun = rTotal; pNew->nOut = nRow; pNew->prereq = prereq; memset(&pNew->u, 0, sizeof(pNew->u)); rc = whereLoopInsert(pBuilder, pNew); } } return rc; } /* |
︙ | ︙ |