Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Simplifications to the NGQP. Add the queryplantest makefile target. Add testcase() macros in the NGQP. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | nextgen-query-plan-exp |
| Files: | files | file ages | folders |
| SHA1: | eaf1f1b405ec2c498092527fae00e5db |
| User & Date: | drh 2013-06-17 18:20:48 |
Context
|
2013-06-17
| ||
| 21:37 | Add more testcase() macros. Fix a memory leak following OOM in the virtual table analysis logic. check-in: b61402af user: drh tags: nextgen-query-plan-exp | |
| 18:20 | Simplifications to the NGQP. Add the queryplantest makefile target. Add testcase() macros in the NGQP. check-in: eaf1f1b4 user: drh tags: nextgen-query-plan-exp | |
| 14:18 | Use automatic indices on subqueries of the FROM clause when appropriate. check-in: e8f12428 user: drh tags: nextgen-query-plan-exp | |
Changes
Changes to main.mk.
589 590 591 592 593 594 595 596 597 598 599 600 601 602 |
soaktest: testfixture$(EXE) sqlite3$(EXE) ./testfixture$(EXE) $(TOP)/test/all.test -soak=1 fulltestonly: testfixture$(EXE) sqlite3$(EXE) ./testfixture$(EXE) $(TOP)/test/full.test test: testfixture$(EXE) sqlite3$(EXE) ./testfixture$(EXE) $(TOP)/test/veryquick.test # The next two rules are used to support the "threadtest" target. Building # threadtest runs a few thread-safety tests that are implemented in C. This # target is invoked by the releasetest.tcl script. # |
> > > |
589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 |
soaktest: testfixture$(EXE) sqlite3$(EXE) ./testfixture$(EXE) $(TOP)/test/all.test -soak=1 fulltestonly: testfixture$(EXE) sqlite3$(EXE) ./testfixture$(EXE) $(TOP)/test/full.test queryplantest: testfixture$(EXE) sqlite3$(EXE) ./testfixture$(EXE) $(TOP)/test/permutations.test queryplanner test: testfixture$(EXE) sqlite3$(EXE) ./testfixture$(EXE) $(TOP)/test/veryquick.test # The next two rules are used to support the "threadtest" target. Building # threadtest runs a few thread-safety tests that are implemented in C. This # target is invoked by the releasetest.tcl script. # |
Changes to src/select.c.
4397 4398 4399 4400 4401 4402 4403 4404 4405 4406 4407 4408 4409 4410 4411 |
/* Begin a loop that will extract all source rows in GROUP BY order.
** This might involve two separate loops with an OP_Sort in between, or
** it might be a single loop that uses an index to extract information
** in the right order to begin with.
*/
sqlite3VdbeAddOp2(v, OP_Gosub, regReset, addrReset);
pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pGroupBy, 0, 0, 0);
if( pWInfo==0 ) goto select_end;
if( sqlite3WhereIsOrdered(pWInfo) ){
/* The optimizer is able to deliver rows in group by order so
** we do not have to sort. The OP_OpenEphemeral table will be
** cancelled later because we still need to use the pKeyInfo
*/
groupBySort = 0;
|
| > |
4397 4398 4399 4400 4401 4402 4403 4404 4405 4406 4407 4408 4409 4410 4411 4412 |
/* Begin a loop that will extract all source rows in GROUP BY order.
** This might involve two separate loops with an OP_Sort in between, or
** it might be a single loop that uses an index to extract information
** in the right order to begin with.
*/
sqlite3VdbeAddOp2(v, OP_Gosub, regReset, addrReset);
pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pGroupBy, 0,
WHERE_GROUPBY, 0);
if( pWInfo==0 ) goto select_end;
if( sqlite3WhereIsOrdered(pWInfo) ){
/* The optimizer is able to deliver rows in group by order so
** we do not have to sort. The OP_OpenEphemeral table will be
** cancelled later because we still need to use the pKeyInfo
*/
groupBySort = 0;
|
Changes to src/where.c.
4317 4318 4319 4320 4321 4322 4323 4324 4325 4326 4327 4328 4329 4330 .... 4857 4858 4859 4860 4861 4862 4863 4864 4865 4866 4867 4868 4869 4870 4871 .... 4942 4943 4944 4945 4946 4947 4948 4949 4950 4951 4952 4953 4954 4955 .... 4966 4967 4968 4969 4970 4971 4972 4973 4974 4975 4976 4977 4978 4979 4980 4981 4982 4983 4984 4985 4986 4987 4988 4989 4990 4991 4992 4993 4994 4995 4996 4997 4998 4999 5000 5001 5002 5003 .... 5039 5040 5041 5042 5043 5044 5045 5046 5047 5048 5049 5050 5051 5052 .... 5089 5090 5091 5092 5093 5094 5095 5096 5097 5098 5099 5100 5101 5102 5103 .... 5196 5197 5198 5199 5200 5201 5202 5203 5204 5205 5206 5207 5208 5209 5210 .... 5322 5323 5324 5325 5326 5327 5328 5329 5330 5331 5332 5333 5334 5335 5336 5337 5338 .... 5339 5340 5341 5342 5343 5344 5345 5346 5347 5348 5349 5350 5351 5352 5353 |
pBtm, pTop, &rDiv);
pNew->nOut = saved_nOut>rDiv+10 ? saved_nOut - rDiv : 10;
}
#ifdef SQLITE_ENABLE_STAT3
if( pNew->u.btree.nEq==1 && pProbe->nSample ){
tRowcnt nOut = 0;
if( (pTerm->eOperator & (WO_EQ|WO_ISNULL))!=0 ){
rc = whereEqualScanEst(pParse, pProbe, pTerm->pExpr->pRight, &nOut);
}else if( (pTerm->eOperator & WO_IN)
&& !ExprHasProperty(pTerm->pExpr, EP_xIsSelect) ){
rc = whereInScanEst(pParse, pProbe, pTerm->pExpr->x.pList, &nOut);
}
pNew->nOut = whereCost(nOut);
}
................................................................................
*/
static int wherePathSatisfiesOrderBy(
WhereInfo *pWInfo, /* The WHERE clause */
ExprList *pOrderBy, /* ORDER BY or GROUP BY or DISTINCT clause to check */
WherePath *pPath, /* The WherePath to check */
u16 wctrlFlags, /* Might contain WHERE_GROUPBY or WHERE_DISTINCTBY */
u16 nLoop, /* Number of entries in pPath->aLoop[] */
u8 isLastLoop, /* True if pLast is the inner-most loop */
WhereLoop *pLast, /* Add this WhereLoop to the end of pPath->aLoop[] */
Bitmask *pRevMask /* OUT: 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 isOrderDistinct; /* All prior WhereLoops are order-distinct */
................................................................................
if( MASKBIT(i) & obSat ) continue;
pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);
if( pOBExpr->op!=TK_COLUMN ) continue;
if( pOBExpr->iTable!=iCur ) continue;
pTerm = findTerm(&pWInfo->sWC, iCur, pOBExpr->iColumn,
~ready, WO_EQ|WO_ISNULL, 0);
if( pTerm==0 ) continue;
if( pOBExpr->iColumn>=0 ){
const char *z1, *z2;
pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[i].pExpr);
if( !pColl ) pColl = db->pDfltColl;
z1 = pColl->zName;
pColl = sqlite3ExprCollSeq(pWInfo->pParse, pTerm->pExpr);
if( !pColl ) pColl = db->pDfltColl;
................................................................................
}else if( (pIndex = pLoop->u.btree.pIndex)==0 || pIndex->bUnordered ){
return 0;
}else{
nColumn = pIndex->nColumn;
isOrderDistinct = pIndex->onError!=OE_None;
}
/* For every term of the index that is constrained by == or IS NULL,
** mark off corresponding ORDER BY terms wherever they occur
** in the ORDER BY clause.
*/
for(i=0; i<pLoop->u.btree.nEq; i++){
pTerm = pLoop->aLTerm[i];
if( (pTerm->eOperator & (WO_EQ|WO_ISNULL))==0 ) continue;
iColumn = pTerm->u.leftColumn;
for(j=0; j<nOrderBy; j++){
if( MASKBIT(j) & obSat ) continue;
pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[j].pExpr);
if( pOBExpr->op!=TK_COLUMN ) continue;
if( pOBExpr->iTable!=iCur ) continue;
if( pOBExpr->iColumn!=iColumn ) continue;
if( iColumn>=0 ){
pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[j].pExpr);
if( !pColl ) pColl = db->pDfltColl;
if( sqlite3StrICmp(pColl->zName, pIndex->azColl[i])!=0 ) continue;
}
obSat |= MASKBIT(j);
}
if( obSat==obDone ) return 1;
}
/* Loop through all columns of the index and deal with the ones
** that are not constrained by == or IN.
*/
rev = revSet = 0;
distinctColumns = 0;
for(j=0; j<=nColumn; j++){
u8 bOnce; /* True to run the ORDER BY search loop */
................................................................................
** of the index and and mark that ORDER BY term off
*/
bOnce = 1;
isMatch = 0;
for(i=0; bOnce && i<nOrderBy; i++){
if( MASKBIT(i) & obSat ) continue;
pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);
if( (wctrlFlags & (WHERE_GROUPBY|WHERE_DISTINCTBY))==0 ) bOnce = 0;
if( pOBExpr->op!=TK_COLUMN ) continue;
if( pOBExpr->iTable!=iCur ) continue;
if( pOBExpr->iColumn!=iColumn ) continue;
if( iColumn>=0 ){
pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[i].pExpr);
if( !pColl ) pColl = db->pDfltColl;
................................................................................
obSat |= MASKBIT(i);
}
}
}
} /* End the loop over all WhereLoops from outer-most down to inner-most */
if( obSat==obDone ) return 1;
if( !isOrderDistinct ) return 0;
if( isLastLoop ) return 1;
return -1;
}
#ifdef WHERETRACE_ENABLED
/* For debugging use only: */
static const char *wherePathName(WherePath *pPath, int nLoop, WhereLoop *pLast){
static char zName[65];
................................................................................
** Compute its cost */
rCost = whereCostAdd(pWLoop->rSetup,pWLoop->rRun + pFrom->nRow);
rCost = whereCostAdd(rCost, pFrom->rCost);
maskNew = pFrom->maskLoop | pWLoop->maskSelf;
if( !isOrderedValid ){
switch( wherePathSatisfiesOrderBy(pWInfo,
pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags,
iLoop, iLoop==nLoop-1, pWLoop, &revMask) ){
case 1: /* Yes. pFrom+pWLoop does satisfy the ORDER BY clause */
isOrdered = 1;
isOrderedValid = 1;
break;
case 0: /* No. pFrom+pWLoop will require a separate sort */
isOrdered = 0;
isOrderedValid = 1;
................................................................................
sqlite3ErrorMsg(pParse, "no query solution");
sqlite3DbFree(db, pSpace);
return SQLITE_ERROR;
}
/* Find the lowest cost path. pFrom will be left pointing to that path */
pFrom = aFrom;
for(ii=1; ii<nFrom; ii++){
if( pFrom->rCost>aFrom[ii].rCost ) pFrom = &aFrom[ii];
}
assert( pWInfo->nLevel==nLoop );
/* Load the lowest cost path into pWInfo */
for(iLoop=0; iLoop<nLoop; iLoop++){
WhereLevel *pLevel = pWInfo->a + iLoop;
pLevel->pWLoop = pWLoop = pFrom->aLoop[iLoop];
pLevel->iFrom = pWLoop->iTab;
pLevel->iTabCur = pWInfo->pTabList->a[pLevel->iFrom].iCursor;
................................................................................
}
if( (pWInfo->wctrlFlags & WHERE_DISTINCTBY)==0
&& pWInfo->pDistinct
&& nRowEst
){
Bitmask notUsed;
int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pDistinct, pFrom,
WHERE_DISTINCTBY, nLoop-1, 1, pFrom->aLoop[nLoop-1], ¬Used);
if( rc==1 ) pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
}
if( pFrom->isOrdered ){
if( pWInfo->wctrlFlags & WHERE_DISTINCTBY ){
pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
}else{
pWInfo->bOBSat = 1;
|
> > < > > < < < < < < < < < < < < < < < < < < < < < < < < > > < | > > > | |
4317 4318 4319 4320 4321 4322 4323 4324 4325 4326 4327 4328 4329 4330 4331 4332 .... 4859 4860 4861 4862 4863 4864 4865 4866 4867 4868 4869 4870 4871 4872 .... 4943 4944 4945 4946 4947 4948 4949 4950 4951 4952 4953 4954 4955 4956 4957 4958 .... 4969 4970 4971 4972 4973 4974 4975 4976 4977 4978 4979 4980 4981 4982 .... 5018 5019 5020 5021 5022 5023 5024 5025 5026 5027 5028 5029 5030 5031 5032 5033 .... 5070 5071 5072 5073 5074 5075 5076 5077 5078 5079 5080 5081 5082 5083 .... 5176 5177 5178 5179 5180 5181 5182 5183 5184 5185 5186 5187 5188 5189 5190 .... 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 |
pBtm, pTop, &rDiv);
pNew->nOut = saved_nOut>rDiv+10 ? saved_nOut - rDiv : 10;
}
#ifdef SQLITE_ENABLE_STAT3
if( pNew->u.btree.nEq==1 && pProbe->nSample ){
tRowcnt nOut = 0;
if( (pTerm->eOperator & (WO_EQ|WO_ISNULL))!=0 ){
testcase( pTerm->eOperator & WO_EQ );
testcase( pTerm->eOperator & WO_ISNULL );
rc = whereEqualScanEst(pParse, pProbe, pTerm->pExpr->pRight, &nOut);
}else if( (pTerm->eOperator & WO_IN)
&& !ExprHasProperty(pTerm->pExpr, EP_xIsSelect) ){
rc = whereInScanEst(pParse, pProbe, pTerm->pExpr->x.pList, &nOut);
}
pNew->nOut = whereCost(nOut);
}
................................................................................
*/
static int wherePathSatisfiesOrderBy(
WhereInfo *pWInfo, /* The WHERE clause */
ExprList *pOrderBy, /* ORDER BY or GROUP BY or DISTINCT clause to check */
WherePath *pPath, /* The WherePath to check */
u16 wctrlFlags, /* Might contain WHERE_GROUPBY or WHERE_DISTINCTBY */
u16 nLoop, /* Number of entries in pPath->aLoop[] */
WhereLoop *pLast, /* Add this WhereLoop to the end of pPath->aLoop[] */
Bitmask *pRevMask /* OUT: 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 isOrderDistinct; /* All prior WhereLoops are order-distinct */
................................................................................
if( MASKBIT(i) & obSat ) continue;
pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);
if( pOBExpr->op!=TK_COLUMN ) continue;
if( pOBExpr->iTable!=iCur ) continue;
pTerm = findTerm(&pWInfo->sWC, iCur, pOBExpr->iColumn,
~ready, WO_EQ|WO_ISNULL, 0);
if( pTerm==0 ) continue;
testcase( pTerm->eOperator & WO_EQ );
testcase( pTerm->eOperator & WO_ISNULL );
if( pOBExpr->iColumn>=0 ){
const char *z1, *z2;
pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[i].pExpr);
if( !pColl ) pColl = db->pDfltColl;
z1 = pColl->zName;
pColl = sqlite3ExprCollSeq(pWInfo->pParse, pTerm->pExpr);
if( !pColl ) pColl = db->pDfltColl;
................................................................................
}else if( (pIndex = pLoop->u.btree.pIndex)==0 || pIndex->bUnordered ){
return 0;
}else{
nColumn = pIndex->nColumn;
isOrderDistinct = pIndex->onError!=OE_None;
}
/* Loop through all columns of the index and deal with the ones
** that are not constrained by == or IN.
*/
rev = revSet = 0;
distinctColumns = 0;
for(j=0; j<=nColumn; j++){
u8 bOnce; /* True to run the ORDER BY search loop */
................................................................................
** of the index and and mark that ORDER BY term off
*/
bOnce = 1;
isMatch = 0;
for(i=0; bOnce && i<nOrderBy; i++){
if( MASKBIT(i) & obSat ) continue;
pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);
testcase( wctrlFlags & WHERE_GROUPBY );
testcase( wctrlFlags & WHERE_DISTINCTBY );
if( (wctrlFlags & (WHERE_GROUPBY|WHERE_DISTINCTBY))==0 ) bOnce = 0;
if( pOBExpr->op!=TK_COLUMN ) continue;
if( pOBExpr->iTable!=iCur ) continue;
if( pOBExpr->iColumn!=iColumn ) continue;
if( iColumn>=0 ){
pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[i].pExpr);
if( !pColl ) pColl = db->pDfltColl;
................................................................................
obSat |= MASKBIT(i);
}
}
}
} /* End the loop over all WhereLoops from outer-most down to inner-most */
if( obSat==obDone ) return 1;
if( !isOrderDistinct ) return 0;
return -1;
}
#ifdef WHERETRACE_ENABLED
/* For debugging use only: */
static const char *wherePathName(WherePath *pPath, int nLoop, WhereLoop *pLast){
static char zName[65];
................................................................................
** Compute its cost */
rCost = whereCostAdd(pWLoop->rSetup,pWLoop->rRun + pFrom->nRow);
rCost = whereCostAdd(rCost, pFrom->rCost);
maskNew = pFrom->maskLoop | pWLoop->maskSelf;
if( !isOrderedValid ){
switch( wherePathSatisfiesOrderBy(pWInfo,
pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags,
iLoop, pWLoop, &revMask) ){
case 1: /* Yes. pFrom+pWLoop does satisfy the ORDER BY clause */
isOrdered = 1;
isOrderedValid = 1;
break;
case 0: /* No. pFrom+pWLoop will require a separate sort */
isOrdered = 0;
isOrderedValid = 1;
................................................................................
sqlite3ErrorMsg(pParse, "no query solution");
sqlite3DbFree(db, pSpace);
return SQLITE_ERROR;
}
/* Find the lowest cost path. pFrom will be left pointing to that path */
pFrom = aFrom;
assert( nFrom==1 );
#if 0 /* The following is needed if nFrom is ever more than 1 */
for(ii=1; ii<nFrom; ii++){
if( pFrom->rCost>aFrom[ii].rCost ) pFrom = &aFrom[ii];
}
#endif
assert( pWInfo->nLevel==nLoop );
/* Load the lowest cost path into pWInfo */
for(iLoop=0; iLoop<nLoop; iLoop++){
WhereLevel *pLevel = pWInfo->a + iLoop;
pLevel->pWLoop = pWLoop = pFrom->aLoop[iLoop];
pLevel->iFrom = pWLoop->iTab;
pLevel->iTabCur = pWInfo->pTabList->a[pLevel->iFrom].iCursor;
................................................................................
}
if( (pWInfo->wctrlFlags & WHERE_DISTINCTBY)==0
&& pWInfo->pDistinct
&& nRowEst
){
Bitmask notUsed;
int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pDistinct, pFrom,
WHERE_DISTINCTBY, nLoop-1, pFrom->aLoop[nLoop-1], ¬Used);
if( rc==1 ) pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
}
if( pFrom->isOrdered ){
if( pWInfo->wctrlFlags & WHERE_DISTINCTBY ){
pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
}else{
pWInfo->bOBSat = 1;
|