diff options
Diffstat (limited to 'src/where.c')
-rw-r--r-- | src/where.c | 244 |
1 files changed, 169 insertions, 75 deletions
diff --git a/src/where.c b/src/where.c index e18e88623..02193785b 100644 --- a/src/where.c +++ b/src/where.c @@ -45,6 +45,8 @@ typedef struct WherePath WherePath; typedef struct WhereTerm WhereTerm; typedef struct WhereLoopBuilder WhereLoopBuilder; typedef struct WhereScan WhereScan; +typedef struct WhereOrCost WhereOrCost; +typedef struct WhereOrSet WhereOrSet; /* ** Cost X is tracked as 10*log2(X) stored in a 16-bit integer. The @@ -152,6 +154,27 @@ struct WhereLoop { WhereTerm *aLTermSpace[4]; /* Initial aLTerm[] space */ }; +/* This object holds the prerequisites and the cost of running a +** subquery on one operand of an OR operator in the WHERE clause. +** See WhereOrSet for additional information +*/ +struct WhereOrCost { + Bitmask prereq; /* Prerequisites */ + WhereCost rRun; /* Cost of running this subquery */ + WhereCost nOut; /* Number of outputs for this subquery */ +}; + +/* The WhereOrSet object holds a set of possible WhereOrCosts that +** correspond to the subquery(s) of OR-clause processing. At most +** favorable N_OR_COST elements are retained. +*/ +#define N_OR_COST 3 +struct WhereOrSet { + u16 n; /* Number of valid a[] entries */ + WhereOrCost a[N_OR_COST]; /* Set of best costs */ +}; + + /* Forward declaration of methods */ static int whereLoopResize(sqlite3*, WhereLoop*, int); @@ -366,7 +389,7 @@ struct WhereLoopBuilder { WhereClause *pWC; /* WHERE clause terms */ ExprList *pOrderBy; /* ORDER BY clause */ WhereLoop *pNew; /* Template WhereLoop */ - WhereLoop *pBest; /* If non-NULL, store single best loop here */ + WhereOrSet *pOrSet; /* Record best loops here, if not NULL */ }; /* @@ -510,6 +533,54 @@ int sqlite3WhereOkOnePass(WhereInfo *pWInfo){ } /* +** Move the content of pSrc into pDest +*/ +static void whereOrMove(WhereOrSet *pDest, WhereOrSet *pSrc){ + pDest->n = pSrc->n; + memcpy(pDest->a, pSrc->a, pDest->n*sizeof(pDest->a[0])); +} + +/* +** Try to insert a new prerequisite/cost entry into the WhereOrSet pSet. +** +** The new entry might overwrite an existing entry, or it might be +** appended, or it might be discarded. Do whatever is the right thing +** so that pSet keeps the N_OR_COST best entries seen so far. +*/ +static int whereOrInsert( + WhereOrSet *pSet, /* The WhereOrSet to be updated */ + Bitmask prereq, /* Prerequisites of the new entry */ + WhereCost rRun, /* Run-cost of the new entry */ + WhereCost nOut /* Number of outputs for the new entry */ +){ + u16 i; + WhereOrCost *p; + for(i=pSet->n, p=pSet->a; i>0; i--, p++){ + if( rRun<=p->rRun && (prereq & p->prereq)==prereq ){ + goto whereOrInsert_done; + } + if( p->rRun<=rRun && (p->prereq & prereq)==p->prereq ){ + return 0; + } + } + if( pSet->n<N_OR_COST ){ + p = &pSet->a[pSet->n++]; + p->nOut = nOut; + }else{ + p = pSet->a; + for(i=1; i<pSet->n; i++){ + if( p->rRun>pSet->a[i].rRun ) p = pSet->a + i; + } + if( p->rRun<=rRun ) return 0; + } +whereOrInsert_done: + p->prereq = prereq; + p->rRun = rRun; + if( p->nOut>nOut ) p->nOut = nOut; + return 1; +} + +/* ** Initialize a preallocated WhereClause structure. */ static void whereClauseInit( @@ -1057,7 +1128,7 @@ static int isLikeOrGlob( if( op==TK_VARIABLE ){ Vdbe *pReprepare = pParse->pReprepare; int iCol = pRight->iColumn; - pVal = sqlite3VdbeGetValue(pReprepare, iCol, SQLITE_AFF_NONE); + pVal = sqlite3VdbeGetBoundValue(pReprepare, iCol, SQLITE_AFF_NONE); if( pVal && sqlite3_value_type(pVal)==SQLITE_TEXT ){ z = (char *)sqlite3_value_text(pVal); } @@ -2164,7 +2235,7 @@ static void constructAutomaticIndex( /* Fill the automatic index with content */ addrTop = sqlite3VdbeAddOp1(v, OP_Rewind, pLevel->iTabCur); regRecord = sqlite3GetTempReg(pParse); - sqlite3GenerateIndexKey(pParse, pIdx, pLevel->iTabCur, regRecord, 1); + sqlite3GenerateIndexKey(pParse, pIdx, pLevel->iTabCur, regRecord, 1, 0); sqlite3VdbeAddOp2(v, OP_IdxInsert, pLevel->iIdxCur, regRecord); sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT); sqlite3VdbeAddOp2(v, OP_Next, pLevel->iTabCur, addrTop+1); @@ -2521,7 +2592,7 @@ static int valueFromExpr( ){ int iVar = pExpr->iColumn; sqlite3VdbeSetVarmask(pParse->pVdbe, iVar); - *pp = sqlite3VdbeGetValue(pParse->pReprepare, iVar, aff); + *pp = sqlite3VdbeGetBoundValue(pParse->pReprepare, iVar, aff); return SQLITE_OK; } return sqlite3ValueFromExpr(pParse->db, pExpr, SQLITE_UTF8, aff, pp); @@ -3179,6 +3250,7 @@ static Bitmask codeOneLoopStart( WhereClause *pWC; /* Decomposition of the entire WHERE clause */ WhereTerm *pTerm; /* A WHERE clause term */ Parse *pParse; /* Parsing context */ + sqlite3 *db; /* Database connection */ Vdbe *v; /* The prepared stmt under constructions */ struct SrcList_item *pTabItem; /* FROM clause term being coded */ int addrBrk; /* Jump here to break out of the loop */ @@ -3190,6 +3262,7 @@ static Bitmask codeOneLoopStart( pParse = pWInfo->pParse; v = pParse->pVdbe; pWC = &pWInfo->sWC; + db = pParse->db; pLevel = &pWInfo->a[iLevel]; pLoop = pLevel->pWLoop; pTabItem = &pWInfo->pTabList->a[pLevel->iFrom]; @@ -3480,7 +3553,7 @@ static Bitmask codeOneLoopStart( ** starting at regBase. */ regBase = codeAllEqualityTerms(pParse,pLevel,bRev,nExtraReg,&zStartAff); - zEndAff = sqlite3DbStrDup(pParse->db, zStartAff); + zEndAff = sqlite3DbStrDup(db, zStartAff); addrNxt = pLevel->addrNxt; /* If we are doing a reverse order scan on an ascending index, or @@ -3565,8 +3638,8 @@ static Bitmask codeOneLoopStart( nConstraint++; testcase( pRangeEnd->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */ } - sqlite3DbFree(pParse->db, zStartAff); - sqlite3DbFree(pParse->db, zEndAff); + sqlite3DbFree(db, zStartAff); + sqlite3DbFree(db, zEndAff); /* Top of the loop body */ pLevel->p2 = sqlite3VdbeCurrentAddr(v); @@ -3693,7 +3766,7 @@ static Bitmask codeOneLoopStart( int nNotReady; /* The number of notReady tables */ struct SrcList_item *origSrc; /* Original list of tables */ nNotReady = pWInfo->nLevel - iLevel - 1; - pOrTab = sqlite3StackAllocRaw(pParse->db, + pOrTab = sqlite3StackAllocRaw(db, sizeof(*pOrTab)+ nNotReady*sizeof(pOrTab->a[0])); if( pOrTab==0 ) return notReady; pOrTab->nAlloc = (u8)(nNotReady + 1); @@ -3743,11 +3816,12 @@ static Bitmask codeOneLoopStart( int iTerm; for(iTerm=0; iTerm<pWC->nTerm; iTerm++){ Expr *pExpr = pWC->a[iTerm].pExpr; + if( &pWC->a[iTerm] == pTerm ) continue; if( ExprHasProperty(pExpr, EP_FromJoin) ) continue; - if( pWC->a[iTerm].wtFlags & (TERM_VIRTUAL|TERM_ORINFO) ) continue; + if( pWC->a[iTerm].wtFlags & (TERM_ORINFO) ) continue; if( (pWC->a[iTerm].eOperator & WO_ALL)==0 ) continue; - pExpr = sqlite3ExprDup(pParse->db, pExpr, 0); - pAndExpr = sqlite3ExprAnd(pParse->db, pAndExpr, pExpr); + pExpr = sqlite3ExprDup(db, pExpr, 0); + pAndExpr = sqlite3ExprAnd(db, pAndExpr, pExpr); } if( pAndExpr ){ pAndExpr = sqlite3PExpr(pParse, TK_AND, 0, pAndExpr, 0); @@ -3767,7 +3841,7 @@ static Bitmask codeOneLoopStart( pSubWInfo = sqlite3WhereBegin(pParse, pOrTab, pOrExpr, 0, 0, WHERE_OMIT_OPEN_CLOSE | WHERE_AND_ONLY | WHERE_FORCE_TABLE | WHERE_ONETABLE_ONLY, iCovCur); - assert( pSubWInfo || pParse->nErr || pParse->db->mallocFailed ); + assert( pSubWInfo || pParse->nErr || db->mallocFailed ); if( pSubWInfo ){ WhereLoop *pSubLoop; explainOneScan( @@ -3822,13 +3896,13 @@ static Bitmask codeOneLoopStart( if( pCov ) pLevel->iIdxCur = iCovCur; if( pAndExpr ){ pAndExpr->pLeft = 0; - sqlite3ExprDelete(pParse->db, pAndExpr); + sqlite3ExprDelete(db, pAndExpr); } sqlite3VdbeChangeP1(v, iRetInit, sqlite3VdbeCurrentAddr(v)); sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrBrk); sqlite3VdbeResolveLabel(v, iLoopBody); - if( pWInfo->nLevel>1 ) sqlite3StackFree(pParse->db, pOrTab); + if( pWInfo->nLevel>1 ) sqlite3StackFree(db, pOrTab); if( !untestedTerms ) disableTerm(pLevel, pTerm); }else #endif /* SQLITE_OMIT_OR_OPTIMIZATION */ @@ -3883,9 +3957,8 @@ static Bitmask codeOneLoopStart( ** the implied "t1.a=123" constraint. */ for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){ - Expr *pE; + Expr *pE, *pEAlt; WhereTerm *pAlt; - Expr sEq; if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue; if( pTerm->eOperator!=(WO_EQUIV|WO_EQ) ) continue; if( pTerm->leftCursor!=iCur ) continue; @@ -3899,9 +3972,13 @@ static Bitmask codeOneLoopStart( testcase( pAlt->eOperator & WO_EQ ); testcase( pAlt->eOperator & WO_IN ); VdbeNoopComment((v, "begin transitive constraint")); - sEq = *pAlt->pExpr; - sEq.pLeft = pE->pLeft; - sqlite3ExprIfFalse(pParse, &sEq, addrCont, SQLITE_JUMPIFNULL); + pEAlt = sqlite3StackAllocRaw(db, sizeof(*pEAlt)); + if( pEAlt ){ + *pEAlt = *pAlt->pExpr; + pEAlt->pLeft = pE->pLeft; + sqlite3ExprIfFalse(pParse, pEAlt, addrCont, SQLITE_JUMPIFNULL); + sqlite3StackFree(db, pEAlt); + } } /* For a LEFT OUTER JOIN, generate code that will record the fact that @@ -4072,12 +4149,12 @@ static void whereInfoFree(sqlite3 *db, WhereInfo *pWInfo){ ** 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. +** If pBuilder->pOrSet is not NULL then we only care about only the +** prerequisites and rRun and nOut costs of the N best loops. That +** information is gathered in the pBuilder->pOrSet object. This special +** processing mode is used only for OR clause processing. ** -** When accumulating multiple loops (when pBuilder->pBest is NULL) we +** When accumulating multiple loops (when pBuilder->pOrSet 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: @@ -4094,30 +4171,22 @@ static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){ WhereInfo *pWInfo = pBuilder->pWInfo; sqlite3 *db = pWInfo->pParse->db; - /* If pBuilder->pBest is defined, then only keep track of the single - ** best WhereLoop. pBuilder->pBest->maskSelf==0 indicates that no - ** prior WhereLoops have been evaluated and that the current pTemplate - ** is therefore the first and hence the best and should be retained. + /* If pBuilder->pOrSet is defined, then only keep track of the costs + ** and prereqs. */ - if( (p = pBuilder->pBest)!=0 ){ - if( p->maskSelf!=0 ){ - WhereCost rCost = whereCostAdd(p->rRun,p->rSetup); - WhereCost rTemplate = whereCostAdd(pTemplate->rRun,pTemplate->rSetup); - if( rCost < rTemplate ){ - testcase( rCost==rTemplate-1 ); - goto whereLoopInsert_noop; - } - if( rCost==rTemplate && (p->prereq & pTemplate->prereq)==p->prereq ){ - goto whereLoopInsert_noop; - } - } + if( pBuilder->pOrSet!=0 ){ +#if WHERETRACE_ENABLED + u16 n = pBuilder->pOrSet->n; + int x = +#endif + whereOrInsert(pBuilder->pOrSet, pTemplate->prereq, pTemplate->rRun, + pTemplate->nOut); #if WHERETRACE_ENABLED if( sqlite3WhereTrace & 0x8 ){ - sqlite3DebugPrintf(p->maskSelf==0 ? "ins-init: " : "ins-best: "); + sqlite3DebugPrintf(x?" or-%d: ":" or-X: ", n); whereLoopPrint(pTemplate, pWInfo->pTabList); } #endif - whereLoopXfer(db, p, pTemplate); return SQLITE_OK; } @@ -4211,7 +4280,7 @@ static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){ whereLoopInsert_noop: #if WHERETRACE_ENABLED if( sqlite3WhereTrace & 0x8 ){ - sqlite3DebugPrintf(pBuilder->pBest ? "ins-skip: " : "ins-noop: "); + sqlite3DebugPrintf("ins-noop: "); whereLoopPrint(pTemplate, pWInfo->pTabList); } #endif @@ -4362,7 +4431,8 @@ static int whereLoopAddBtreeIndex( && !ExprHasProperty(pTerm->pExpr, EP_xIsSelect) ){ rc = whereInScanEst(pParse, pProbe, pTerm->pExpr->x.pList, &nOut); } - if( rc==SQLITE_OK ) pNew->nOut = whereCost(nOut); + assert( nOut==0 || rc==SQLITE_OK ); + if( nOut ) pNew->nOut = whereCost(nOut); } #endif if( (pNew->wsFlags & (WHERE_IDX_ONLY|WHERE_IPK))==0 ){ @@ -4434,6 +4504,17 @@ static Bitmask columnsInIndex(Index *pIdx){ return m; } +/* Check to see if a partial index with pPartIndexWhere can be used +** in the current query. Return true if it can be and false if not. +*/ +static int whereUsablePartialIndex(int iTab, WhereClause *pWC, Expr *pWhere){ + int i; + WhereTerm *pTerm; + for(i=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){ + if( sqlite3ExprImpliesExpr(pTerm->pExpr, pWhere, iTab) ) return 1; + } + return 0; +} /* ** Add all WhereLoop objects for a single table of the join where the table @@ -4457,11 +4538,13 @@ static int whereLoopAddBtree( int b; /* A boolean value */ WhereCost rSize; /* number of rows in the table */ WhereCost rLogSize; /* Logarithm of the number of rows in the table */ + WhereClause *pWC; /* The parsed WHERE clause */ pNew = pBuilder->pNew; pWInfo = pBuilder->pWInfo; pTabList = pWInfo->pTabList; pSrc = pTabList->a + pNew->iTab; + pWC = pBuilder->pWC; assert( !IsVirtual(pSrc->pTab) ); if( pSrc->pIndex ){ @@ -4493,7 +4576,7 @@ static int whereLoopAddBtree( rLogSize = estLog(rSize); /* Automatic indexes */ - if( !pBuilder->pBest + if( !pBuilder->pOrSet && (pWInfo->pParse->db->flags & SQLITE_AutoIndex)!=0 && pSrc->pIndex==0 && !pSrc->viaCoroutine @@ -4501,7 +4584,6 @@ static int whereLoopAddBtree( && !pSrc->isCorrelated ){ /* Generate auto-index WhereLoops */ - WhereClause *pWC = pBuilder->pWC; WhereTerm *pTerm; WhereTerm *pWCEnd = pWC->a + pWC->nTerm; for(pTerm=pWC->a; rc==SQLITE_OK && pTerm<pWCEnd; pTerm++){ @@ -4531,6 +4613,10 @@ static int whereLoopAddBtree( /* Loop over all indices */ for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext, iSortIdx++){ + if( pProbe->pPartIdxWhere!=0 + && !whereUsablePartialIndex(pNew->iTab, pWC, pProbe->pPartIdxWhere) ){ + continue; /* Partial index inappropriate for this query */ + } pNew->u.btree.nEq = 0; pNew->nLTerm = 0; pNew->iSortIdx = 0; @@ -4779,7 +4865,7 @@ static int whereLoopAddOr(WhereLoopBuilder *pBuilder, Bitmask mExtra){ int iCur; WhereClause tempWC; WhereLoopBuilder sSubBuild; - WhereLoop sBest; + WhereOrSet sSum, sCur, sPrev; struct SrcList_item *pItem; pWC = pBuilder->pWC; @@ -4794,16 +4880,14 @@ static int whereLoopAddOr(WhereLoopBuilder *pBuilder, Bitmask mExtra){ WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc; WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm]; WhereTerm *pOrTerm; - WhereCost rTotal = 0; - WhereCost nRow = 0; - Bitmask prereq = mExtra; + int once = 1; + int i, j; - whereLoopInit(&sBest); pItem = pWInfo->pTabList->a + pNew->iTab; iCur = pItem->iCursor; sSubBuild = *pBuilder; sSubBuild.pOrderBy = 0; - sSubBuild.pBest = &sBest; + sSubBuild.pOrSet = &sCur; for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){ if( (pOrTerm->eOperator & WO_AND)!=0 ){ @@ -4818,39 +4902,48 @@ static int whereLoopAddOr(WhereLoopBuilder *pBuilder, Bitmask mExtra){ }else{ continue; } - sBest.maskSelf = 0; - sBest.rSetup = 0; - sBest.rRun = 0; + sCur.n = 0; #ifndef SQLITE_OMIT_VIRTUALTABLE if( IsVirtual(pItem->pTab) ){ rc = whereLoopAddVirtual(&sSubBuild); + for(i=0; i<sCur.n; i++) sCur.a[i].prereq |= mExtra; }else #endif { rc = whereLoopAddBtree(&sSubBuild, mExtra); } - /* sBest.maskSelf is always zero if an error occurs */ - assert( rc==SQLITE_OK || sBest.maskSelf==0 ); - if( sBest.maskSelf==0 ) break; - assert( sBest.rSetup==0 ); - rTotal = whereCostAdd(rTotal, sBest.rRun); - nRow = whereCostAdd(nRow, sBest.nOut); - prereq |= sBest.prereq; + assert( rc==SQLITE_OK || sCur.n==0 ); + if( sCur.n==0 ){ + sSum.n = 0; + break; + }else if( once ){ + whereOrMove(&sSum, &sCur); + once = 0; + }else{ + whereOrMove(&sPrev, &sSum); + sSum.n = 0; + for(i=0; i<sPrev.n; i++){ + for(j=0; j<sCur.n; j++){ + whereOrInsert(&sSum, sPrev.a[i].prereq | sCur.a[j].prereq, + whereCostAdd(sPrev.a[i].rRun, sCur.a[j].rRun), + whereCostAdd(sPrev.a[i].nOut, sCur.a[j].nOut)); + } + } + } } - assert( pNew->nLSlot>=1 ); - if( sBest.maskSelf ){ - pNew->nLTerm = 1; - pNew->aLTerm[0] = pTerm; - pNew->wsFlags = WHERE_MULTI_OR; - pNew->rSetup = 0; + pNew->nLTerm = 1; + pNew->aLTerm[0] = pTerm; + pNew->wsFlags = WHERE_MULTI_OR; + pNew->rSetup = 0; + pNew->iSortIdx = 0; + memset(&pNew->u, 0, sizeof(pNew->u)); + for(i=0; rc==SQLITE_OK && i<sSum.n; i++){ /* TUNING: Multiple by 3.5 for the secondary table lookup */ - pNew->rRun = rTotal + 18; assert( 18==whereCost(7)-whereCost(2) ); - pNew->nOut = nRow; - pNew->prereq = prereq; - memset(&pNew->u, 0, sizeof(pNew->u)); + pNew->rRun = sSum.a[i].rRun + 18; + pNew->nOut = sSum.a[i].nOut; + pNew->prereq = sSum.a[i].prereq; rc = whereLoopInsert(pBuilder, pNew); } - whereLoopClear(pWInfo->pParse->db, &sBest); } } return rc; @@ -5464,7 +5557,7 @@ static int whereShortCut(WhereLoopBuilder *pBuilder){ pLoop->rRun = 33; /* 33==whereCost(10) */ }else{ for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){ - if( pIdx->onError==OE_None ) continue; + if( pIdx->onError==OE_None || pIdx->pPartIdxWhere!=0 ) continue; for(j=0; j<pIdx->nColumn; j++){ pTerm = findTerm(pWC, iCur, pIdx->aiColumn[j], 0, WO_EQ, pIdx); if( pTerm==0 ) break; @@ -5657,7 +5750,8 @@ WhereInfo *sqlite3WhereBegin( pMaskSet = &pWInfo->sMaskSet; sWLB.pWInfo = pWInfo; sWLB.pWC = &pWInfo->sWC; - sWLB.pNew = (WhereLoop*)&pWInfo->a[nTabList]; + sWLB.pNew = (WhereLoop*)(((char*)pWInfo)+nByteWInfo); + assert( EIGHT_BYTE_ALIGNMENT(sWLB.pNew) ); whereLoopInit(sWLB.pNew); #ifdef SQLITE_DEBUG sWLB.pNew->cId = '*'; |