Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Improved detection of unnecessary ORDER BY clauses. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | nextgen-query-plan-exp |
Files: | files | file ages | folders |
SHA1: |
58805eb36b9975706e2c4e3826895194 |
User & Date: | drh 2013-05-31 12:43:55.143 |
Context
2013-05-31
| ||
13:36 | Futher enhancements to the ORDER BY optimizer. (check-in: d8efa5f8b6 user: drh tags: nextgen-query-plan-exp) | |
12:43 | Improved detection of unnecessary ORDER BY clauses. (check-in: 58805eb36b user: drh tags: nextgen-query-plan-exp) | |
11:57 | Fix the constructAutomaticIndex() routine so that it works with NGQP. (check-in: 5e1e613995 user: drh tags: nextgen-query-plan-exp) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
3828 3829 3830 3831 3832 3833 3834 | /* ** 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 | | > > | 3828 3829 3830 3831 3832 3833 3834 3835 3836 3837 3838 3839 3840 3841 3842 3843 3844 3845 3846 3847 3848 3849 3850 3851 3852 3853 3854 3855 3856 3857 3858 3859 | /* ** 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 on 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 ** (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, *pToFree = 0; WhereTerm **paTerm = 0; sqlite3 *db = pBuilder->db; WhereInfo *pWInfo = pBuilder->pWInfo; |
︙ | ︙ | |||
4096 4097 4098 4099 4100 4101 4102 | 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 */ | | | 4098 4099 4100 4101 4102 4103 4104 4105 4106 4107 4108 4109 4110 4111 4112 | 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 = 1; /* 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) ); |
︙ | ︙ | |||
4175 4176 4177 4178 4179 4180 4181 4182 4183 4184 4185 4186 4187 4188 | 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; | > | 4177 4178 4179 4180 4181 4182 4183 4184 4185 4186 4187 4188 4189 4190 4191 | 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->iSortIdx = b ? iSortIdx : 0; 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; |
︙ | ︙ | |||
4509 4510 4511 4512 4513 4514 4515 | int nLoop, /* Number of entries in pPath->aLoop[] */ WhereLoop *pLast, /* Add this WhereLoop to the end of pPath->aLoop[] */ Bitmask *pRevMask /* Mask of WhereLoops to run in reverse order */ ){ u8 revSet; /* True if rev is known */ u8 rev; /* Composite sort order */ u8 revIdx; /* Index sort order */ | > > | < | 4512 4513 4514 4515 4516 4517 4518 4519 4520 4521 4522 4523 4524 4525 4526 4527 4528 | int nLoop, /* Number of entries in pPath->aLoop[] */ WhereLoop *pLast, /* Add this WhereLoop to the end of pPath->aLoop[] */ Bitmask *pRevMask /* Mask of WhereLoops to run in reverse order */ ){ u8 revSet; /* True if rev is known */ u8 rev; /* Composite sort order */ u8 revIdx; /* Index sort order */ u8 isOneRow; /* Current WhereLoop is a one-row loop */ u8 requireOneRow = 0; /* All subsequent loops must be one-row */ u8 isUniqueIdx; /* Current WhereLoop uses a unique index */ u16 nColumn; u16 nOrderBy; int i, j; int nUsed = 0; int iCur; int iColumn; WhereLoop *pLoop; |
︙ | ︙ | |||
4543 4544 4545 4546 4547 4548 4549 4550 4551 4552 4553 4554 4555 4556 | ** (2) If the current WhereLoop is not one-row, then all subsequent ** WhereLoops must be one-row. ** ** (3) Optionally match any ORDER BY terms against the first nEq columns ** of the index. ** ** (4) Index columns past nEq must match ORDER BY terms one-for-one. */ assert( pOrderBy!=0 ); /* Sortability of virtual tables is determined by the xBestIndex method ** of the virtual table itself */ if( pLast->wsFlags & WHERE_VIRTUALTABLE ){ | > > > > | 4547 4548 4549 4550 4551 4552 4553 4554 4555 4556 4557 4558 4559 4560 4561 4562 4563 4564 | ** (2) If the current WhereLoop is not one-row, then all subsequent ** WhereLoops must be one-row. ** ** (3) Optionally match any ORDER BY terms against the first nEq columns ** of the index. ** ** (4) Index columns past nEq must match ORDER BY terms one-for-one. ** ** (5) If all columns of a UNIQUE index have been matched against ORDER BY ** terms, then any subsequent entries in the ORDER BY clause against the ** same table can be skipped. */ assert( pOrderBy!=0 ); /* Sortability of virtual tables is determined by the xBestIndex method ** of the virtual table itself */ if( pLast->wsFlags & WHERE_VIRTUALTABLE ){ |
︙ | ︙ | |||
4565 4566 4567 4568 4569 4570 4571 | pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr); if( pOBExpr->op!=TK_COLUMN ) return 0; } for(i=0; i<=nLoop && nUsed<nOrderBy; i++){ pLoop = i<nLoop ? pPath->aLoop[i] : pLast; assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 ); | | | | | | | | | | | 4573 4574 4575 4576 4577 4578 4579 4580 4581 4582 4583 4584 4585 4586 4587 4588 4589 4590 4591 4592 4593 4594 4595 4596 4597 4598 4599 4600 4601 4602 4603 4604 4605 4606 4607 4608 4609 4610 4611 4612 4613 4614 4615 4616 | pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr); if( pOBExpr->op!=TK_COLUMN ) return 0; } for(i=0; i<=nLoop && nUsed<nOrderBy; i++){ pLoop = i<nLoop ? pPath->aLoop[i] : pLast; assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 ); isOneRow = isUniqueIdx = 1; if( pLoop->wsFlags & WHERE_IPK ){ if( (pLoop->wsFlags & WHERE_COLUMN_IN)!=0 ) isOneRow = 0; if( pLoop->u.btree.nEq!=1 ) isOneRow = 0; pIndex = 0; nColumn = 0; }else if( (pIndex = pLoop->u.btree.pIndex)==0 || pIndex->bUnordered ){ return 0; }else{ nColumn = pIndex->nColumn; if( pIndex->onError==OE_None ){ isOneRow = isUniqueIdx = 0; }else if( (pLoop->wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_RANGE |WHERE_COLUMN_NULL))!=0 ){ isOneRow = 0; }else if( pLoop->u.btree.nEq < pIndex->nColumn ){ isOneRow = 0; } } if( !isOneRow && requireOneRow ) return 0; requireOneRow = !isOneRow; iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor; j = 0; revSet = rev = 0; for(j=0; j<=nColumn && nUsed<nOrderBy; j++, nUsed++){ int skipable; pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[nUsed].pExpr); assert( pOBExpr->op==TK_COLUMN ); if( pOBExpr->iTable!=iCur ) break; if( isOneRow ){ j--; continue; } if( j<nColumn ){ /* Normal index columns */ iColumn = pIndex->aiColumn[j]; revIdx = pIndex->aSortOrder[j]; if( iColumn==pIndex->pTable->iPKey ) iColumn = -1; }else{ /* The ROWID column at the end */ |
︙ | ︙ | |||
4625 4626 4627 4628 4629 4630 4631 4632 4633 4634 4635 4636 4637 4638 | if( revSet ){ if( (rev ^ revIdx)!=pOrderBy->a[nUsed].sortOrder ) return 0; }else{ rev = revIdx ^ pOrderBy->a[nUsed].sortOrder; revSet = 1; } } } if( rev ) revMask |= ((Bitmask)1)<<i; } if( nUsed==nOrderBy ){ *pRevMask = revMask; return 1; } | > | 4633 4634 4635 4636 4637 4638 4639 4640 4641 4642 4643 4644 4645 4646 4647 | if( revSet ){ if( (rev ^ revIdx)!=pOrderBy->a[nUsed].sortOrder ) return 0; }else{ rev = revIdx ^ pOrderBy->a[nUsed].sortOrder; revSet = 1; } } if( j>=nColumn-1 && isUniqueIdx ){ j--; isOneRow = 1; } } if( rev ) revMask |= ((Bitmask)1)<<i; } if( nUsed==nOrderBy ){ *pRevMask = revMask; return 1; } |
︙ | ︙ |