From fde1e6bc376be6b667d7e634f0102dccb0cf3f98 Mon Sep 17 00:00:00 2001 From: drh Date: Fri, 6 Sep 2013 17:45:42 +0000 Subject: [PATCH] Enhance the plan solver to take into account the number of output rows when computing the set of paths to retain for the next cycle. FossilOrigin-Name: 1a46a7242313da96420985fa52e1de3f84533e5b --- manifest | 17 ++++++-------- manifest.uuid | 2 +- src/resolve.c | 2 +- src/where.c | 61 +++++++++++++++++++++++++++++++-------------------- 4 files changed, 46 insertions(+), 36 deletions(-) diff --git a/manifest b/manifest index c355e4ffe5..af8be5bcd5 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Initial\simplementation\sof\sthe\sunlikely()\sSQL\sfunction\sused\sas\sa\shint\sto\nthe\squery\splanner. -D 2013-09-06T15:23:29.191 +C Enhance\sthe\splan\ssolver\sto\stake\sinto\saccount\sthe\snumber\sof\soutput\srows\swhen\ncomputing\sthe\sset\sof\spaths\sto\sretain\sfor\sthe\snext\scycle. +D 2013-09-06T17:45:42.446 F Makefile.arm-wince-mingw32ce-gcc d6df77f1f48d690bd73162294bbba7f59507c72f F Makefile.in 5e41da95d92656a5004b03d3576e8b226858a28e F Makefile.linux-gcc 91d710bdc4998cb015f39edf3cb314ec4f4d7e23 @@ -214,7 +214,7 @@ F src/pragma.c 3aa3d8c8623b7b71c5b1bfb72dcc31fb0c25665f F src/prepare.c fa6988589f39af8504a61731614cd4f6ae71554f F src/printf.c da9119eb31a187a4b99f60aa4a225141c0ebb74b F src/random.c 0b2dbc37fdfbfa6bd455b091dfcef5bdb32dba68 -F src/resolve.c 748618c3df7f37f2cd33c8834770b1e34f9b1185 +F src/resolve.c 8a2b6b9a6487e6e5a23b8de571131ccce62a1ce0 F src/rowset.c 64655f1a627c9c212d9ab497899e7424a34222e0 F src/select.c 9239586282bd146ec5843a2cde7d54cd7816cf78 F src/shell.c d920a891ca09b8bd262cced7fb0ab9d723f7a747 @@ -290,7 +290,7 @@ F src/vtab.c 5a423b042eb1402ef77697d03d6a67378d97bc8d F src/wal.c 7dc3966ef98b74422267e7e6e46e07ff6c6eb1b4 F src/wal.h df01efe09c5cb8c8e391ff1715cca294f89668a4 F src/walker.c 4fa43583d0a84b48f93b1e88f11adf2065be4e73 -F src/where.c c9f8ae51797bebfbfa49b9e5bede6fc142b44262 +F src/where.c ce16c689b9a199ffffd63745405214912e941e6f F test/8_3_names.test ebbb5cd36741350040fd28b432ceadf495be25b2 F test/aggerror.test a867e273ef9e3d7919f03ef4f0e8c0d2767944f2 F test/aggnested.test 45c0201e28045ad38a530b5a144b73cd4aa2cfd6 @@ -1111,10 +1111,7 @@ F tool/warnings-clang.sh f6aa929dc20ef1f856af04a730772f59283631d4 F tool/warnings.sh fbc018d67fd7395f440c28f33ef0f94420226381 F tool/wherecosttest.c f407dc4c79786982a475261866a161cd007947ae F tool/win/sqlite.vsix 97894c2790eda7b5bce3cc79cb2a8ec2fde9b3ac -P 97b10e66e98e84755aa577f8da017bf1aea2056c -R fcd7cd29a90a12a870cace66939b8877 -T *branch * unlikely-func -T *sym-unlikely-func * -T -sym-trunk * +P 036fc37a034093a4c6fc190633bd41c2b7230d77 +R 3890bf7553bc1077426fb2f0e0259279 U drh -Z 2a30cee668099b5c8e0e2b447ac67feb +Z 80a7432df4b498524e527dd8f32c240f diff --git a/manifest.uuid b/manifest.uuid index b43b68fee1..b05ebc1a75 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -036fc37a034093a4c6fc190633bd41c2b7230d77 \ No newline at end of file +1a46a7242313da96420985fa52e1de3f84533e5b \ No newline at end of file diff --git a/src/resolve.c b/src/resolve.c index cb86a83ee0..ec6fe90716 100644 --- a/src/resolve.c +++ b/src/resolve.c @@ -705,7 +705,7 @@ static int resolveExprStep(Walker *pWalker, Expr *pExpr){ pNC->nErr++; } }else{ - pExpr->iTable = 100; + pExpr->iTable = 75; } } } diff --git a/src/where.c b/src/where.c index a9905769a4..e4485ac7d4 100644 --- a/src/where.c +++ b/src/where.c @@ -5306,9 +5306,12 @@ static int wherePathSolver(WhereInfo *pWInfo, WhereCost nRowEst){ sqlite3 *db; /* The database connection */ int iLoop; /* Loop counter over the terms of the join */ int ii, jj; /* Loop counters */ - WhereCost rCost; /* Cost of a path */ - WhereCost mxCost = 0; /* Maximum cost of a set of paths */ - WhereCost rSortCost; /* Cost to do a sort */ + int mxI = 0; /* Index of next entry to replace */ + WhereCost rCost; /* Cost of a path */ + WhereCost nOut; /* Number of outputs */ + WhereCost mxCost = 0; /* Maximum cost of a set of paths */ + WhereCost mxOut = 0; /* Maximum nOut value on the set of paths */ + WhereCost 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 */ @@ -5377,6 +5380,7 @@ static int wherePathSolver(WhereInfo *pWInfo, WhereCost nRowEst){ ** Compute its cost */ rCost = whereCostAdd(pWLoop->rSetup,pWLoop->rRun + pFrom->nRow); rCost = whereCostAdd(rCost, pFrom->rCost); + nOut = pFrom->nRow + pWLoop->nOut; maskNew = pFrom->maskLoop | pWLoop->maskSelf; if( !isOrderedValid ){ switch( wherePathSatisfiesOrderBy(pWInfo, @@ -5399,17 +5403,23 @@ static int wherePathSolver(WhereInfo *pWInfo, WhereCost nRowEst){ } /* Check to see if pWLoop should be added to the mxChoice best so far */ for(jj=0, pTo=aTo; jjmaskLoop==maskNew && pTo->isOrderedValid==isOrderedValid ){ + if( pTo->maskLoop==maskNew + && pTo->isOrderedValid==isOrderedValid + && ((pTo->rCost<=rCost && pTo->nRow<=nOut) || + (pTo->rCost>=rCost && pTo->nRow>=nOut)) + ){ testcase( jj==nTo-1 ); break; } } if( jj>=nTo ){ - if( nTo>=mxChoice && rCost>=mxCost ){ + if( nTo>=mxChoice + && (rCost>mxCost || (rCost==mxCost && nOut>=mxOut)) + ){ #ifdef WHERETRACE_ENABLED if( sqlite3WhereTrace&0x4 ){ - sqlite3DebugPrintf("Skip %s cost=%3d order=%c\n", - wherePathName(pFrom, iLoop, pWLoop), rCost, + sqlite3DebugPrintf("Skip %s cost=%-3d,%3d order=%c\n", + wherePathName(pFrom, iLoop, pWLoop), rCost, nOut, isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?'); } #endif @@ -5421,26 +5431,26 @@ static int wherePathSolver(WhereInfo *pWInfo, WhereCost nRowEst){ jj = nTo++; }else{ /* New path replaces the prior worst to keep count below mxChoice */ - for(jj=nTo-1; aTo[jj].rCost0); } + jj = mxI; } pTo = &aTo[jj]; #ifdef WHERETRACE_ENABLED if( sqlite3WhereTrace&0x4 ){ - sqlite3DebugPrintf("New %s cost=%-3d order=%c\n", - wherePathName(pFrom, iLoop, pWLoop), rCost, + sqlite3DebugPrintf("New %s cost=%-3d,%3d order=%c\n", + wherePathName(pFrom, iLoop, pWLoop), rCost, nOut, isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?'); } #endif }else{ - if( pTo->rCost<=rCost ){ + if( pTo->rCost<=rCost && pTo->nRow<=nOut ){ #ifdef WHERETRACE_ENABLED if( sqlite3WhereTrace&0x4 ){ sqlite3DebugPrintf( - "Skip %s cost=%-3d order=%c", - wherePathName(pFrom, iLoop, pWLoop), rCost, + "Skip %s cost=%-3d,%3d order=%c", + wherePathName(pFrom, iLoop, pWLoop), rCost, nOut, isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?'); - sqlite3DebugPrintf(" vs %s cost=%-3d order=%c\n", - wherePathName(pTo, iLoop+1, 0), pTo->rCost, + sqlite3DebugPrintf(" vs %s cost=%-3d,%d order=%c\n", + wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow, pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?'); } #endif @@ -5452,11 +5462,11 @@ static int wherePathSolver(WhereInfo *pWInfo, WhereCost nRowEst){ #ifdef WHERETRACE_ENABLED if( sqlite3WhereTrace&0x4 ){ sqlite3DebugPrintf( - "Update %s cost=%-3d order=%c", - wherePathName(pFrom, iLoop, pWLoop), rCost, + "Update %s cost=%-3d,%3d order=%c", + wherePathName(pFrom, iLoop, pWLoop), rCost, nOut, isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?'); - sqlite3DebugPrintf(" was %s cost=%-3d order=%c\n", - wherePathName(pTo, iLoop+1, 0), pTo->rCost, + sqlite3DebugPrintf(" was %s cost=%-3d,%3d order=%c\n", + wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow, pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?'); } #endif @@ -5464,16 +5474,22 @@ static int wherePathSolver(WhereInfo *pWInfo, WhereCost nRowEst){ /* pWLoop is a winner. Add it to the set of best so far */ pTo->maskLoop = pFrom->maskLoop | pWLoop->maskSelf; pTo->revLoop = revMask; - pTo->nRow = pFrom->nRow + pWLoop->nOut; + pTo->nRow = nOut; pTo->rCost = rCost; pTo->isOrderedValid = isOrderedValid; pTo->isOrdered = isOrdered; memcpy(pTo->aLoop, pFrom->aLoop, sizeof(WhereLoop*)*iLoop); pTo->aLoop[iLoop] = pWLoop; if( nTo>=mxChoice ){ + mxI = 0; mxCost = aTo[0].rCost; + mxOut = aTo[0].nRow; for(jj=1, pTo=&aTo[1]; jjrCost>mxCost ) mxCost = pTo->rCost; + if( pTo->rCost>mxCost || (pTo->rCost==mxCost && pTo->nRow>mxOut) ){ + mxCost = pTo->rCost; + mxOut = pTo->nRow; + mxI = jj; + } } } } @@ -5510,12 +5526,9 @@ static int wherePathSolver(WhereInfo *pWInfo, WhereCost nRowEst){ /* 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; iirCost>aFrom[ii].rCost ) pFrom = &aFrom[ii]; } -#endif assert( pWInfo->nLevel==nLoop ); /* Load the lowest cost path into pWInfo */ for(iLoop=0; iLoop