diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/expr.c | 53 | ||||
| -rw-r--r-- | src/func.c | 20 | ||||
| -rw-r--r-- | src/resolve.c | 27 | ||||
| -rw-r--r-- | src/sqliteInt.h | 7 | ||||
| -rw-r--r-- | src/where.c | 133 |
5 files changed, 176 insertions, 64 deletions
diff --git a/src/expr.c b/src/expr.c index 82623b14b..e5d8a6129 100644 --- a/src/expr.c +++ b/src/expr.c @@ -70,7 +70,7 @@ Expr *sqlite3ExprAddCollateToken(Parse *pParse, Expr *pExpr, Token *pCollName){ Expr *pNew = sqlite3ExprAlloc(pParse->db, TK_COLLATE, pCollName, 1); if( pNew ){ pNew->pLeft = pExpr; - pNew->flags |= EP_Collate; + pNew->flags |= EP_Collate|EP_Skip; pExpr = pNew; } } @@ -85,13 +85,21 @@ Expr *sqlite3ExprAddCollateString(Parse *pParse, Expr *pExpr, const char *zC){ } /* -** Skip over any TK_COLLATE and/or TK_AS operators at the root of -** an expression. +** Skip over any TK_COLLATE or TK_AS operators and any unlikely() +** or likelihood() function at the root of an expression. */ Expr *sqlite3ExprSkipCollate(Expr *pExpr){ - while( pExpr && (pExpr->op==TK_COLLATE || pExpr->op==TK_AS) ){ - pExpr = pExpr->pLeft; - } + while( pExpr && ExprHasProperty(pExpr, EP_Skip) ){ + if( ExprHasProperty(pExpr, EP_Unlikely) ){ + assert( !ExprHasProperty(pExpr, EP_xIsSelect) ); + assert( pExpr->x.pList->nExpr>0 ); + assert( pExpr->op==TK_FUNCTION ); + pExpr = pExpr->x.pList->a[0].pExpr; + }else{ + assert( pExpr->op==TK_COLLATE || pExpr->op==TK_AS ); + pExpr = pExpr->pLeft; + } + } return pExpr; } @@ -2316,6 +2324,16 @@ static int usedAsColumnCache(Parse *pParse, int iFrom, int iTo){ #endif /* SQLITE_DEBUG || SQLITE_COVERAGE_TEST */ /* +** Convert an expression node to a TK_REGISTER +*/ +static void exprToRegister(Expr *p, int iReg){ + p->op2 = p->op; + p->op = TK_REGISTER; + p->iTable = iReg; + ExprClearProperty(p, EP_Skip); +} + +/* ** Generate code into the current Vdbe to evaluate the given ** expression. Attempt to store the results in register "target". ** Return the register where results are stored. @@ -2648,6 +2666,14 @@ int sqlite3ExprCodeTarget(Parse *pParse, Expr *pExpr, int target){ break; } + /* The UNLIKELY() function is a no-op. The result is the value + ** of the first argument. + */ + if( pDef->funcFlags & SQLITE_FUNC_UNLIKELY ){ + assert( nFarg>=1 ); + sqlite3ExprCode(pParse, pFarg->a[0].pExpr, target); + break; + } if( pFarg ){ r1 = sqlite3GetTempRange(pParse, nFarg); @@ -2877,9 +2903,8 @@ int sqlite3ExprCodeTarget(Parse *pParse, Expr *pExpr, int target){ cacheX = *pX; testcase( pX->op==TK_COLUMN ); testcase( pX->op==TK_REGISTER ); - cacheX.iTable = sqlite3ExprCodeTemp(pParse, pX, ®Free1); + exprToRegister(&cacheX, sqlite3ExprCodeTemp(pParse, pX, ®Free1)); testcase( regFree1==0 ); - cacheX.op = TK_REGISTER; opCompare.op = TK_EQ; opCompare.pLeft = &cacheX; pTest = &opCompare; @@ -3021,9 +3046,7 @@ int sqlite3ExprCodeAndCache(Parse *pParse, Expr *pExpr, int target){ int iMem; iMem = ++pParse->nMem; sqlite3VdbeAddOp2(v, OP_Copy, inReg, iMem); - pExpr->iTable = iMem; - pExpr->op2 = pExpr->op; - pExpr->op = TK_REGISTER; + exprToRegister(pExpr, iMem); } return inReg; } @@ -3402,9 +3425,7 @@ static int evalConstExpr(Walker *pWalker, Expr *pExpr){ ** but suboptimal, so we want to know about the situation to fix it. ** Hence the following assert: */ assert( r2==r1 ); - pExpr->op2 = pExpr->op; - pExpr->op = TK_REGISTER; - pExpr->iTable = r2; + exprToRegister(pExpr, r2); return WRC_Prune; } return WRC_Continue; @@ -3502,9 +3523,7 @@ static void exprCodeBetween( compRight.op = TK_LE; compRight.pLeft = &exprX; compRight.pRight = pExpr->x.pList->a[1].pExpr; - exprX.iTable = sqlite3ExprCodeTemp(pParse, &exprX, ®Free1); - exprX.op2 = exprX.op; - exprX.op = TK_REGISTER; + exprToRegister(&exprX, sqlite3ExprCodeTemp(pParse, &exprX, ®Free1)); if( jumpIfTrue ){ sqlite3ExprIfTrue(pParse, &exprAnd, dest, jumpIfNull); }else{ diff --git a/src/func.c b/src/func.c index 64e33640b..ae7945111 100644 --- a/src/func.c +++ b/src/func.c @@ -418,14 +418,14 @@ static void lowerFunc(sqlite3_context *context, int argc, sqlite3_value **argv){ } /* -** The COALESCE() and IFNULL() functions are implemented as VDBE code so -** that unused argument values do not have to be computed. However, we -** still need some kind of function implementation for this routines in -** the function table. That function implementation will never be called -** so it doesn't matter what the implementation is. We might as well use -** the "version()" function as a substitute. +** Some functions like COALESCE() and IFNULL() and UNLIKELY() are implemented +** as VDBE code so that unused argument values do not have to be computed. +** However, we still need some kind of function implementation for this +** routines in the function table. The noopFunc macro provides this. +** noopFunc will never be called so it doesn't matter what the implementation +** is. We might as well use the "version()" function as a substitute. */ -#define ifnullFunc versionFunc /* Substitute function - never called */ +#define noopFunc versionFunc /* Substitute function - never called */ /* ** Implementation of random(). Return a random integer. @@ -1659,9 +1659,11 @@ void sqlite3RegisterGlobalFunctions(void){ FUNCTION(lower, 1, 0, 0, lowerFunc ), FUNCTION(coalesce, 1, 0, 0, 0 ), FUNCTION(coalesce, 0, 0, 0, 0 ), - FUNCTION2(coalesce, -1, 0, 0, ifnullFunc, SQLITE_FUNC_COALESCE), + FUNCTION2(coalesce, -1, 0, 0, noopFunc, SQLITE_FUNC_COALESCE), FUNCTION(hex, 1, 0, 0, hexFunc ), - FUNCTION2(ifnull, 2, 0, 0, ifnullFunc, SQLITE_FUNC_COALESCE), + FUNCTION2(ifnull, 2, 0, 0, noopFunc, SQLITE_FUNC_COALESCE), + FUNCTION2(unlikely, 1, 0, 0, noopFunc, SQLITE_FUNC_UNLIKELY), + FUNCTION2(likelihood, 2, 0, 0, noopFunc, SQLITE_FUNC_UNLIKELY), FUNCTION(random, 0, 0, 0, randomFunc ), FUNCTION(randomblob, 1, 0, 0, randomBlob ), FUNCTION(nullif, 2, 0, 1, nullifFunc ), diff --git a/src/resolve.c b/src/resolve.c index 54ce3adf5..c1e8cb798 100644 --- a/src/resolve.c +++ b/src/resolve.c @@ -107,6 +107,7 @@ static void resolveAlias( incrAggFunctionDepth(pDup, nSubquery); pDup = sqlite3PExpr(pParse, TK_AS, pDup, 0, 0); if( pDup==0 ) return; + ExprSetProperty(pDup, EP_Skip); if( pEList->a[iCol].iAlias==0 ){ pEList->a[iCol].iAlias = (u16)(++pParse->nAlias); } @@ -570,6 +571,19 @@ static void notValidCheckConstraint( # define notValidCheckConstraint(P,N,M) #endif +/* +** Expression p should encode a floating point value between 1.0 and 0.0. +** Return 1024 times this value. Or return -1 if p is not a floating point +** value between 1.0 and 0.0. +*/ +static int exprProbability(Expr *p){ + double r = -1.0; + if( p->op!=TK_FLOAT ) return -1; + sqlite3AtoF(p->u.zToken, &r, sqlite3Strlen30(p->u.zToken), SQLITE_UTF8); + assert( r>=0.0 ); + if( r>1.0 ) return -1; + return (int)(r*1000.0); +} /* ** This routine is callback for sqlite3WalkExpr(). @@ -683,6 +697,19 @@ static int resolveExprStep(Walker *pWalker, Expr *pExpr){ } }else{ is_agg = pDef->xFunc==0; + if( pDef->funcFlags & SQLITE_FUNC_UNLIKELY ){ + ExprSetProperty(pExpr, EP_Unlikely|EP_Skip); + if( n==2 ){ + pExpr->iTable = exprProbability(pList->a[1].pExpr); + if( pExpr->iTable<0 ){ + sqlite3ErrorMsg(pParse, "second argument to likelihood() must be a " + "constant between 0.0 and 1.0"); + pNC->nErr++; + } + }else{ + pExpr->iTable = 62; /* TUNING: Default 2nd arg to unlikely() is 0.0625 */ + } + } } #ifndef SQLITE_OMIT_AUTHORIZATION if( pDef ){ diff --git a/src/sqliteInt.h b/src/sqliteInt.h index 758561362..361224084 100644 --- a/src/sqliteInt.h +++ b/src/sqliteInt.h @@ -1030,6 +1030,7 @@ struct sqlite3 { #define SQLITE_Transitive 0x0200 /* Transitive constraints */ #define SQLITE_OmitNoopJoin 0x0400 /* Omit unused tables in joins */ #define SQLITE_Stat3 0x0800 /* Use the SQLITE_STAT3 table */ +#define SQLITE_AdjustOutEst 0x1000 /* Adjust output estimates using WHERE */ #define SQLITE_AllOpts 0xffff /* All optimizations */ /* @@ -1750,7 +1751,8 @@ struct Expr { #endif int iTable; /* TK_COLUMN: cursor number of table holding column ** TK_REGISTER: register number - ** TK_TRIGGER: 1 -> new, 0 -> old */ + ** TK_TRIGGER: 1 -> new, 0 -> old + ** EP_Unlikely: 1000 times likelihood */ ynVar iColumn; /* TK_COLUMN: column index. -1 for rowid. ** TK_VARIABLE: variable number (always >= 1). */ i16 iAgg; /* Which entry in pAggInfo->aCol[] or ->aFunc[] */ @@ -1777,12 +1779,13 @@ struct Expr { #define EP_FixedDest 0x000200 /* Result needed in a specific register */ #define EP_IntValue 0x000400 /* Integer value contained in u.iValue */ #define EP_xIsSelect 0x000800 /* x.pSelect is valid (otherwise x.pList is) */ -#define EP_Hint 0x001000 /* Not used */ +#define EP_Skip 0x001000 /* COLLATE, AS, or UNLIKELY */ #define EP_Reduced 0x002000 /* Expr struct EXPR_REDUCEDSIZE bytes only */ #define EP_TokenOnly 0x004000 /* Expr struct EXPR_TOKENONLYSIZE bytes only */ #define EP_Static 0x008000 /* Held in memory not obtained from malloc() */ #define EP_MemToken 0x010000 /* Need to sqlite3DbFree() Expr.zToken */ #define EP_Irreduce 0x020000 /* Cannot EXPRDUP_REDUCE this Expr */ +#define EP_Unlikely 0x040000 /* unlikely() or likelihood() function */ /* ** The pseudo-routine sqlite3ExprSetIrreducible sets the EP2_Irreducible diff --git a/src/where.c b/src/where.c index fb097d2af..b8ec788bc 100644 --- a/src/where.c +++ b/src/where.c @@ -52,12 +52,13 @@ typedef struct WhereOrSet WhereOrSet; ** Cost X is tracked as 10*log2(X) stored in a 16-bit integer. The ** maximum cost for ordinary tables is 64*(2**63) which becomes 6900. ** (Virtual tables can return a larger cost, but let's assume they do not.) -** So all costs can be stored in a 16-bit unsigned integer without risk +** So all costs can be stored in a 16-bit integer without risk ** of overflow. ** ** Costs are estimates, so no effort is made to compute 10*log2(X) exactly. -** Instead, a close estimate is used. Any value of X<=1 is stored as 0. -** X=2 is 10. X=3 is 16. X=1000 is 99. etc. +** Instead, a close estimate is used. Any value of X=1 is stored as 0. +** X=2 is 10. X=3 is 16. X=1000 is 99. etc. Negative values are allowed. +** A WhereCost of -10 means 0.5. WhereCost of -20 means 0.25. And so forth. ** ** The tool/wherecosttest.c source file implements a command-line program ** that will convert WhereCosts to integers, convert integers to WhereCosts @@ -65,7 +66,7 @@ typedef struct WhereOrSet WhereOrSet; ** command-line program is a useful utility to have around when working with ** this module. */ -typedef unsigned short int WhereCost; +typedef short int WhereCost; /* ** This object contains information needed to implement a single nested @@ -269,6 +270,7 @@ struct WhereTerm { WhereOrInfo *pOrInfo; /* Extra information if (eOperator & WO_OR)!=0 */ WhereAndInfo *pAndInfo; /* Extra information if (eOperator& WO_AND)!=0 */ } u; + WhereCost truthProb; /* Probability of truth for this expression */ u16 eOperator; /* A WO_xx value describing <op> */ u8 wtFlags; /* TERM_xxx bit flags. See below */ u8 nChild; /* Number of children that must disable us */ @@ -643,6 +645,9 @@ static void whereClauseClear(WhereClause *pWC){ } } +/* Forward declaration */ +static WhereCost whereCost(tRowcnt x); + /* ** Add a single new WhereTerm entry to the WhereClause object pWC. ** The new WhereTerm object is constructed from Expr p and with wtFlags. @@ -684,6 +689,11 @@ static int whereClauseInsert(WhereClause *pWC, Expr *p, u8 wtFlags){ pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]); } pTerm = &pWC->a[idx = pWC->nTerm++]; + if( p && ExprHasProperty(p, EP_Unlikely) ){ + pTerm->truthProb = whereCost(p->iTable) - 99; + }else{ + pTerm->truthProb = -1; + } pTerm->pExpr = sqlite3ExprSkipCollate(p); pTerm->wtFlags = wtFlags; pTerm->pWC = pWC; @@ -2545,6 +2555,7 @@ static int whereRangeScanEst( ){ int rc = SQLITE_OK; int nOut = (int)*pnOut; + WhereCost nNew; #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 Index *p = pBuilder->pNew->u.btree.pIndex; @@ -2607,6 +2618,7 @@ static int whereRangeScanEst( whereKeyStats(pParse, p, pRec, 0, a); iNew = a[0] + ((pLower->eOperator & WO_GT) ? a[1] : 0); if( iNew>iLower ) iLower = iNew; + nOut--; } } @@ -2621,12 +2633,12 @@ static int whereRangeScanEst( whereKeyStats(pParse, p, pRec, 1, a); iNew = a[0] + ((pUpper->eOperator & WO_LE) ? a[1] : 0); if( iNew<iUpper ) iUpper = iNew; + nOut--; } } pBuilder->pRec = pRec; if( rc==SQLITE_OK ){ - WhereCost nNew; if( iUpper>iLower ){ nNew = whereCost(iUpper - iLower); }else{ @@ -2648,13 +2660,17 @@ static int whereRangeScanEst( assert( pLower || pUpper ); /* TUNING: Each inequality constraint reduces the search space 4-fold. ** A BETWEEN operator, therefore, reduces the search space 16-fold */ + nNew = nOut; if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ){ - nOut -= 20; assert( 20==whereCost(4) ); + nNew -= 20; assert( 20==whereCost(4) ); + nOut--; } if( pUpper ){ - nOut -= 20; assert( 20==whereCost(4) ); + nNew -= 20; assert( 20==whereCost(4) ); + nOut--; } - if( nOut<10 ) nOut = 10; + if( nNew<10 ) nNew = 10; + if( nNew<nOut ) nOut = nNew; *pnOut = (WhereCost)nOut; return rc; } @@ -4189,9 +4205,9 @@ static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){ assert( p->rSetup==pTemplate->rSetup ); if( p->prereq==pTemplate->prereq && p->nLTerm<pTemplate->nLTerm - && (p->wsFlags & WHERE_INDEXED)!=0 - && (pTemplate->wsFlags & WHERE_INDEXED)!=0 - && p->u.btree.pIndex==pTemplate->u.btree.pIndex + && (p->wsFlags & pTemplate->wsFlags & WHERE_INDEXED)!=0 + && (p->u.btree.pIndex==pTemplate->u.btree.pIndex + || pTemplate->rRun+p->nLTerm<=p->rRun+pTemplate->nLTerm) ){ /* Overwrite an existing WhereLoop with an similar one that uses ** more terms of the index */ @@ -4206,12 +4222,12 @@ static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){ if( (p->prereq & pTemplate->prereq)==pTemplate->prereq && p->rRun>=pTemplate->rRun && p->nOut>=pTemplate->nOut - && ALWAYS(p->rSetup>=pTemplate->rSetup) /* See SETUP-INVARIANT above */ ){ /* Overwrite an existing WhereLoop with a better one: one that is ** better at one of (1) dependencies, (2) setup-cost, (3) run-cost ** or (4) number of output rows, and is no worse in any of those ** categories. */ + assert( p->rSetup>=pTemplate->rSetup ); /* SETUP-INVARIANT above */ pNext = p->pNextLoop; break; } @@ -4259,6 +4275,36 @@ whereLoopInsert_noop: } /* +** Adjust the WhereLoop.nOut value downward to account for terms of the +** WHERE clause that reference the loop but which are not used by an +** index. +** +** In the current implementation, the first extra WHERE clause term reduces +** the number of output rows by a factor of 10 and each additional term +** reduces the number of output rows by sqrt(2). +*/ +static void whereLoopOutputAdjust(WhereClause *pWC, WhereLoop *pLoop, int iCur){ + WhereTerm *pTerm, *pX; + Bitmask notAllowed = ~(pLoop->prereq|pLoop->maskSelf); + int i, j; + + if( !OptimizationEnabled(pWC->pWInfo->pParse->db, SQLITE_AdjustOutEst) ){ + return; + } + for(i=pWC->nTerm, pTerm=pWC->a; i>0; i--, pTerm++){ + if( (pTerm->wtFlags & TERM_VIRTUAL)!=0 ) break; + if( (pTerm->prereqAll & pLoop->maskSelf)==0 ) continue; + if( (pTerm->prereqAll & notAllowed)!=0 ) continue; + for(j=pLoop->nLTerm-1; j>=0; j--){ + pX = pLoop->aLTerm[j]; + if( pX==pTerm ) break; + if( pX->iParent>=0 && (&pWC->a[pX->iParent])==pTerm ) break; + } + if( j<0 ) pLoop->nOut += pTerm->truthProb; + } +} + +/* ** We have so far matched pBuilder->pNew->u.btree.nEq terms of the index pIndex. ** Try to match one more. ** @@ -4424,7 +4470,7 @@ static int whereLoopAddBtreeIndex( } /* Step cost for each output row */ pNew->rRun = whereCostAdd(pNew->rRun, pNew->nOut); - /* TBD: Adjust nOut for additional constraints */ + whereLoopOutputAdjust(pBuilder->pWC, pNew, pSrc->iCursor); rc = whereLoopInsert(pBuilder, pNew); if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0 && pNew->u.btree.nEq<(pProbe->nColumn + (pProbe->zName!=0)) @@ -4628,7 +4674,9 @@ static int whereLoopAddBtree( ** index scans so that a covering index scan will be favored over ** a table scan. */ pNew->rRun = whereCostAdd(rSize,rLogSize) + 16; + whereLoopOutputAdjust(pWC, pNew, pSrc->iCursor); rc = whereLoopInsert(pBuilder, pNew); + pNew->nOut = rSize; if( rc ) break; }else{ Bitmask m = pSrc->colUsed & ~columnsInIndex(pProbe); @@ -4660,7 +4708,9 @@ static int whereLoopAddBtree( ** which we will simplify to just N*log2(N) */ pNew->rRun = rSize + rLogSize; } + whereLoopOutputAdjust(pWC, pNew, pSrc->iCursor); rc = whereLoopInsert(pBuilder, pNew); + pNew->nOut = rSize; if( rc ) break; } } @@ -5267,9 +5317,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 */ @@ -5338,6 +5391,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, @@ -5360,7 +5414,11 @@ 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; jj<nTo; jj++, pTo++){ - if( pTo->maskLoop==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; } @@ -5369,8 +5427,8 @@ static int wherePathSolver(WhereInfo *pWInfo, WhereCost nRowEst){ if( nTo>=mxChoice && rCost>=mxCost ){ #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 @@ -5382,26 +5440,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].rCost<mxCost; jj--){ assert(jj>0); } + 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 @@ -5413,11 +5471,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 @@ -5425,16 +5483,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]; jj<mxChoice; jj++, pTo++){ - if( pTo->rCost>mxCost ) mxCost = pTo->rCost; + if( pTo->rCost>mxCost || (pTo->rCost==mxCost && pTo->nRow>mxOut) ){ + mxCost = pTo->rCost; + mxOut = pTo->nRow; + mxI = jj; + } } } } @@ -5471,12 +5535,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; 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++){ |