Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Improvements to ORDER BY handling in the NGQP. Fix an "exit" mistakenly left in a test script during the previous check-in. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | nextgen-query-plan-exp |
| Files: | files | file ages | folders |
| SHA1: |
12c709b4369c7d94d7fb743d0d0da7a9 |
| User & Date: | drh 2013-05-22 02:06:59 |
Context
|
2013-05-22
| ||
| 17:01 | Allow the rowid at the end of an index to be used in a constraint on that index. check-in: 9bf0524d user: drh tags: nextgen-query-plan-exp | |
| 02:06 | Improvements to ORDER BY handling in the NGQP. Fix an "exit" mistakenly left in a test script during the previous check-in. check-in: 12c709b4 user: drh tags: nextgen-query-plan-exp | |
|
2013-05-21
| ||
| 19:23 | Enhanced "wheretrace" output in the NGQP solver routine. check-in: 04dfb85a user: drh tags: nextgen-query-plan-exp | |
Changes
Changes to src/where.c.
5957 5958 5959 5960 5961 5962 5963 5964 5965 5966 5967 5968 5969 5970 5971 .... 5972 5973 5974 5975 5976 5977 5978 5979 5980 5981 5982 5983 5984 5985 5986 .... 5999 6000 6001 6002 6003 6004 6005 6006 6007 6008 6009 6010 6011 6012 6013 6014 6015 6016 6017 6018 6019 6020 6021 6022 6023 6024 6025 6026 6027 .... 6130 6131 6132 6133 6134 6135 6136 6137 6138 6139 6140 6141 6142 6143 6144 6145 6146 6147 .... 6163 6164 6165 6166 6167 6168 6169 6170 6171 6172 6173 6174 6175 6176 .... 6428 6429 6430 6431 6432 6433 6434 6435 6436 6437 6438 6439 6440 6441 6442 6443 |
** Given the list of WhereLoop objects on pWInfo->pLoops, this routine
** attempts to find the lowest cost path that visits each WhereLoop
** once. This path is then loaded into the pWInfo->a[].pWLoop fields.
**
** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation
** error occurs.
*/
static int wherePathSolver(WhereInfo *pWInfo){
const int mxChoice = 10; /* Maximum number of simultaneous paths tracked */
int nLoop; /* Number of terms in the join */
sqlite3 *db; /* The database connection */
int iLoop; /* Loop counter over the terms of the join */
int ii, jj; /* Loop counters */
double rCost; /* Cost of a path */
double mxCost; /* Maximum cost of a set of paths */
................................................................................
double rSortCost; /* Cost to do a sort */
int nTo, nFrom; /* Number of valid entries in aTo[] and aFrom[] */
WherePath *aFrom; /* All nFrom paths at the previous level */
WherePath *aTo; /* The nTo best paths at the current level */
WherePath *pFrom; /* An element of aFrom[] that we are working on */
WherePath *pTo; /* An element of aTo[] that we are working on */
WhereLoop *pWLoop; /* One of the WhereLoop objects */
WhereLoop *pNext; /* Next loop */
WhereLoop **pX; /* Used to divy up the pSpace memory */
char *pSpace; /* Temporary memory used by this routine */
db = pWInfo->pParse->db;
nLoop = pWInfo->nLevel;
assert( nLoop<=pWInfo->pTabList->nSrc );
................................................................................
/* Seed the search with a single WherePath containing zero WhereLoops */
aFrom[0].nRow = (double)1;
nFrom = 1;
/* Precompute the cost of sorting the final result set, if the caller
** to sqlite3WhereBegin() was concerned about sorting */
rSortCost = (double)0;
if( pWInfo->pOrderBy==0 ){
aFrom[0].isOrderedValid = 1;
}else{
/* Compute an estimate on the cost to sort the entire result set */
rSortCost = (double)1;
for(pWLoop=pWInfo->pLoops; pWLoop; pWLoop=pNext){
pNext = pWLoop->pNextLoop;
rCost = pWLoop->nOut;
while( pNext && pNext->iTab==pWLoop->iTab ){
if( pNext->nOut<rCost ) rCost = pNext->nOut;
pNext = pNext->pNextLoop;
}
rSortCost *= rCost;
}
rSortCost *= estLog(rSortCost);
}
/* Compute successively longer WherePaths using the previous generation
** of WherePaths as the basis for the next. Keep track of the mxChoice
** best paths at each generation */
for(iLoop=0; iLoop<nLoop; iLoop++){
nTo = 0;
................................................................................
}
}
}
}
#ifdef WHERETRACE_ENABLED
if( sqlite3WhereTrace>=2 ){
sqlite3DebugPrintf("---- round %d ----\n", iLoop);
for(ii=0, pTo=aTo; ii<nTo; ii++, pTo++){
sqlite3DebugPrintf("%2d: %s cost=%-7.2g nrow=%-7.2g order=%c\n",
ii, wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow,
pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?');
}
}
#endif
/* Swap the roles of aFrom and aTo for the next generation */
pFrom = aTo;
................................................................................
/* Load the lowest cost path into pWInfo */
for(iLoop=0; iLoop<nLoop; iLoop++){
pWInfo->a[iLoop].pWLoop = pFrom->aLoop[iLoop];
}
if( pFrom->isOrdered ){
pWInfo->nOBSat = pWInfo->pOrderBy->nExpr;
}
/* Free temporary memory and return success */
sqlite3DbFree(db, pSpace);
return SQLITE_OK;
}
/*
................................................................................
for(p=pWInfo->pLoops; p; p=p->pNextLoop){
p->cId = zLabel[(i++)%sizeof(zLabel)];
whereLoopPrint(p, pTabList);
}
}
#endif
wherePathSolver(pWInfo);
if( db->mallocFailed ) goto whereBeginError;
#ifdef WHERETRACE_ENABLED
if( sqlite3WhereTrace ){
int ii;
sqlite3DebugPrintf("------------ Solution -------------");
if( pWInfo->nOBSat ){
sqlite3DebugPrintf(" ORDER BY omitted\n");
}else{
|
| < | > > > > > > > > > | | | > | > > > > |
5957 5958 5959 5960 5961 5962 5963 5964 5965 5966 5967 5968 5969 5970 5971 .... 5972 5973 5974 5975 5976 5977 5978 5979 5980 5981 5982 5983 5984 5985 .... 5998 5999 6000 6001 6002 6003 6004 6005 6006 6007 6008 6009 6010 6011 6012 6013 6014 6015 6016 6017 6018 6019 6020 6021 6022 6023 6024 6025 6026 6027 6028 6029 6030 6031 6032 6033 6034 6035 .... 6138 6139 6140 6141 6142 6143 6144 6145 6146 6147 6148 6149 6150 6151 6152 6153 6154 6155 .... 6171 6172 6173 6174 6175 6176 6177 6178 6179 6180 6181 6182 6183 6184 6185 .... 6437 6438 6439 6440 6441 6442 6443 6444 6445 6446 6447 6448 6449 6450 6451 6452 6453 6454 6455 6456 |
** Given the list of WhereLoop objects on pWInfo->pLoops, this routine ** attempts to find the lowest cost path that visits each WhereLoop ** once. This path is then loaded into the pWInfo->a[].pWLoop fields. ** ** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation ** error occurs. */ static int wherePathSolver(WhereInfo *pWInfo, double nRowEst){ const int mxChoice = 10; /* Maximum number of simultaneous paths tracked */ int nLoop; /* Number of terms in the join */ sqlite3 *db; /* The database connection */ int iLoop; /* Loop counter over the terms of the join */ int ii, jj; /* Loop counters */ double rCost; /* Cost of a path */ double mxCost; /* Maximum cost of a set of paths */ ................................................................................ double rSortCost; /* Cost to do a sort */ int nTo, nFrom; /* Number of valid entries in aTo[] and aFrom[] */ WherePath *aFrom; /* All nFrom paths at the previous level */ WherePath *aTo; /* The nTo best paths at the current level */ WherePath *pFrom; /* An element of aFrom[] that we are working on */ WherePath *pTo; /* An element of aTo[] that we are working on */ WhereLoop *pWLoop; /* One of the WhereLoop objects */ WhereLoop **pX; /* Used to divy up the pSpace memory */ char *pSpace; /* Temporary memory used by this routine */ db = pWInfo->pParse->db; nLoop = pWInfo->nLevel; assert( nLoop<=pWInfo->pTabList->nSrc ); ................................................................................ /* Seed the search with a single WherePath containing zero WhereLoops */ aFrom[0].nRow = (double)1; nFrom = 1; /* Precompute the cost of sorting the final result set, if the caller ** to sqlite3WhereBegin() was concerned about sorting */ rSortCost = (double)0; if( pWInfo->pOrderBy==0 || nRowEst<0.0 ){ aFrom[0].isOrderedValid = 1; }else{ /* Compute an estimate on the cost to sort the entire result set */ #if 0 rSortCost = (double)1; for(pWLoop=pWInfo->pLoops; pWLoop; pWLoop=pNext){ pNext = pWLoop->pNextLoop; rCost = pWLoop->nOut; while( pNext && pNext->iTab==pWLoop->iTab ){ if( pNext->nOut<rCost ) rCost = pNext->nOut; pNext = pNext->pNextLoop; } rSortCost *= rCost; } rSortCost *= estLog(rSortCost); #else rSortCost = nRowEst*estLog(nRowEst); #endif #ifdef WHERETRACE_ENABLED if( sqlite3WhereTrace>=2 ){ sqlite3DebugPrintf("--solver sort cost=%-7.2g\n", rSortCost); } #endif } /* Compute successively longer WherePaths using the previous generation ** of WherePaths as the basis for the next. Keep track of the mxChoice ** best paths at each generation */ for(iLoop=0; iLoop<nLoop; iLoop++){ nTo = 0; ................................................................................ } } } } #ifdef WHERETRACE_ENABLED if( sqlite3WhereTrace>=2 ){ sqlite3DebugPrintf("---- after round %d ----\n", iLoop); for(ii=0, pTo=aTo; ii<nTo; ii++, pTo++){ sqlite3DebugPrintf(" %s cost=%-7.2g nrow=%-7.2g order=%c\n", wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow, pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?'); } } #endif /* Swap the roles of aFrom and aTo for the next generation */ pFrom = aTo; ................................................................................ /* Load the lowest cost path into pWInfo */ for(iLoop=0; iLoop<nLoop; iLoop++){ pWInfo->a[iLoop].pWLoop = pFrom->aLoop[iLoop]; } if( pFrom->isOrdered ){ pWInfo->nOBSat = pWInfo->pOrderBy->nExpr; } pWInfo->nRowOut = pFrom->nRow; /* Free temporary memory and return success */ sqlite3DbFree(db, pSpace); return SQLITE_OK; } /* ................................................................................ for(p=pWInfo->pLoops; p; p=p->pNextLoop){ p->cId = zLabel[(i++)%sizeof(zLabel)]; whereLoopPrint(p, pTabList); } } #endif wherePathSolver(pWInfo, -1); if( db->mallocFailed ) goto whereBeginError; if( pWInfo->pOrderBy ){ wherePathSolver(pWInfo, pWInfo->nRowOut); if( db->mallocFailed ) goto whereBeginError; } #ifdef WHERETRACE_ENABLED if( sqlite3WhereTrace ){ int ii; sqlite3DebugPrintf("------------ Solution -------------"); if( pWInfo->nOBSat ){ sqlite3DebugPrintf(" ORDER BY omitted\n"); }else{ |
Changes to test/boundary3.test.
119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
}
} {72057594037927935 17}
do_test boundary3-2.1.3 {
db eval {
SELECT t1.rowid, x FROM t1 JOIN t2 ON t2.r=t1.rowid WHERE t2.a=17
}
} {72057594037927935 00ffffffffffffff}
exit
do_test boundary3-2.1.gt.1 {
db eval {
SELECT t2.a FROM t1 JOIN t2 USING(a)
WHERE t1.rowid > 72057594037927935 ORDER BY t2.a
}
} {3 28}
do_test boundary3-2.1.gt.2 {
|
< |
119 120 121 122 123 124 125 126 127 128 129 130 131 132 |
}
} {72057594037927935 17}
do_test boundary3-2.1.3 {
db eval {
SELECT t1.rowid, x FROM t1 JOIN t2 ON t2.r=t1.rowid WHERE t2.a=17
}
} {72057594037927935 00ffffffffffffff}
do_test boundary3-2.1.gt.1 {
db eval {
SELECT t2.a FROM t1 JOIN t2 USING(a)
WHERE t1.rowid > 72057594037927935 ORDER BY t2.a
}
} {3 28}
do_test boundary3-2.1.gt.2 {
|