Index: src/where.c ================================================================== --- src/where.c +++ src/where.c @@ -287,10 +287,11 @@ Parse *pParse; /* Parsing context */ WhereClause *pWC; /* WHERE clause terms */ SrcList *pTabList; /* FROM clause */ ExprList *pOrderBy; /* ORDER BY clause */ WhereLoop *pNew; /* Template WhereLoop */ + WhereLoop *pBest; /* If non-NULL, store single best loop here */ int mxTerm; /* Maximum number of aTerm[] entries on pNew */ }; /* ** Bitmasks for the operators that indices are able to exploit. An @@ -5160,14 +5161,31 @@ ** is better and has fewer dependencies. Or the template will be ignored ** and no insert will occur if an existing WhereLoop is faster and has ** fewer dependencies than the template. Otherwise a new WhereLoop is ** added based no the template. */ -static int whereLoopInsert(WhereInfo *pWInfo, WhereLoop *pTemplate){ +static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){ WhereLoop **ppPrev, *p, *pNext = 0, *pToFree = 0; WhereTerm **paTerm = 0; - sqlite3 *db = pWInfo->pParse->db; + sqlite3 *db = pBuilder->db; + WhereInfo *pWInfo = pBuilder->pWInfo; + + if( (p = pBuilder->pBest)!=0 ){ + if( p->maskSelf!=0 ){ + if( p->rRun+p->rSetup < pTemplate->rRun+pTemplate->rSetup ){ + return SQLITE_OK; + } + if( p->rRun+p->rSetup == pTemplate->rRun+pTemplate->rSetup + && p->prereq <= pTemplate->prereq ){ + return SQLITE_OK; + } + } + *p = *pTemplate; + p->aTerm = 0; + p->u.vtab.needFree = 0; + return SQLITE_OK; + } /* Search for an existing WhereLoop to overwrite, or which takes ** priority over pTemplate. */ for(ppPrev=&pWInfo->pLoops, p=*ppPrev; p; ppPrev=&p->pNextLoop, p=*ppPrev){ @@ -5208,15 +5226,17 @@ } *p = *pTemplate; p->pNextLoop = pNext; *ppPrev = p; p->aTerm = paTerm; - if( pTemplate->nTerm ){ - memcpy(p->aTerm, pTemplate->aTerm, pTemplate->nTerm*sizeof(p->aTerm[0])); + if( p->nTerm ){ + memcpy(p->aTerm, pTemplate->aTerm, p->nTerm*sizeof(p->aTerm[0])); } if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){ - if( p->u.btree.pIndex && p->u.btree.pIndex->tnum==0 ) p->u.btree.pIndex = 0; + if( p->u.btree.pIndex && p->u.btree.pIndex->tnum==0 ){ + p->u.btree.pIndex = 0; + } }else{ pTemplate->u.vtab.needFree = 0; } return SQLITE_OK; } @@ -5303,11 +5323,11 @@ ** the main table */ pNew->rRun += pNew->nOut*(1 + rLogSize); } /* TBD: Adjust nOut and rRun for STAT3 range values */ /* TBD: Adjust nOut for additional constraints */ - rc = whereLoopInsert(pBuilder->pWInfo, pNew); + rc = whereLoopInsert(pBuilder, pNew); if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0 && pNew->u.btree.nEqnColumn ){ whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul*nIn); } @@ -5364,11 +5384,12 @@ } rSize = (double)pSrc->pTab->nRowEst; rLogSize = estLog(rSize); /* Automatic indexes */ - if( (pBuilder->pParse->db->flags & SQLITE_AutoIndex)!=0 + if( !pBuilder->pBest + && (pBuilder->pParse->db->flags & SQLITE_AutoIndex)!=0 && !pSrc->viaCoroutine && !pSrc->notIndexed && !pSrc->isCorrelated ){ /* Generate auto-index WhereLoops */ @@ -5383,11 +5404,11 @@ pNew->rSetup = 2*rLogSize*pSrc->pTab->nRowEst; pNew->nOut = (double)10; pNew->rRun = rLogSize + pNew->nOut; pNew->wsFlags = WHERE_TEMP_INDEX; pNew->prereq = mExtra | pTerm->prereqRight; - rc = whereLoopInsert(pBuilder->pWInfo, pNew); + rc = whereLoopInsert(pBuilder, pNew); } } } /* Insert a full table scan */ @@ -5398,11 +5419,11 @@ pNew->u.btree.pIndex = 0; pNew->wsFlags = 0; pNew->nOut = rSize; pNew->rRun = rSize + rLogSize; /* TBD: Reduce nOut using constraints */ - rc = whereLoopInsert(pBuilder->pWInfo, pNew); + rc = whereLoopInsert(pBuilder, pNew); /* Loop over all indices */ for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext){ pNew->u.btree.nEq = 0; @@ -5563,11 +5584,11 @@ pNew->u.vtab.idxStr = pIdxInfo->idxStr; pNew->u.vtab.isOrdered = (u8)(pIdxInfo->nOrderBy!=0); pNew->rSetup = (double)0; pNew->rRun = pIdxInfo->estimatedCost; pNew->nOut = (double)25; - whereLoopInsert(pBuilder->pWInfo, pNew); + whereLoopInsert(pBuilder, pNew); if( pNew->u.vtab.needFree ){ sqlite3_free(pNew->u.vtab.idxStr); pNew->u.vtab.needFree = 0; } } @@ -5576,10 +5597,88 @@ whereLoopAddVtab_exit: if( pIdxInfo->needToFreeIdxStr ) sqlite3_free(pIdxInfo->idxStr); sqlite3DbFree(db, pIdxInfo); return rc; } + +/* +** Add WhereLoop entries to handle OR terms. This works for either +** btrees or virtual tables. +*/ +static int whereLoopAddOr(WhereLoopBuilder *pBuilder, Bitmask mExtra){ + WhereClause *pWC; + WhereLoop *pNew; + WhereTerm *pTerm, *pWCEnd; + int rc = SQLITE_OK; + int iCur; + WhereClause tempWC; + WhereLoopBuilder sSubBuild; + WhereLoop sBest; + struct SrcList_item *pItem; + + + pWC = pBuilder->pWC; + if( pWC->wctrlFlags & WHERE_AND_ONLY ) return SQLITE_OK; + pWCEnd = pWC->a + pWC->nTerm; + pNew = pBuilder->pNew; + pItem = pBuilder->pTabList->a + pNew->iTab; + iCur = pItem->iCursor; + sSubBuild = *pBuilder; + sSubBuild.pOrderBy = 0; + sSubBuild.pBest = &sBest; + tempWC.pParse = pWC->pParse; + tempWC.pMaskSet = pWC->pMaskSet; + tempWC.pOuter = pWC; + tempWC.op = TK_AND; + tempWC.wctrlFlags = 0; + tempWC.nTerm = 1; + + for(pTerm=pWC->a; pTermeOperator & WO_OR)!=0 + && (pTerm->u.pOrInfo->indexable & pNew->maskSelf)!=0 + ){ + WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc; + WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm]; + WhereTerm *pOrTerm; + double rTotal = 0; + double nRow = 0; + Bitmask prereq = mExtra; + + + for(pOrTerm=pOrWC->a; pOrTermeOperator& WO_AND)!=0 ){ + sSubBuild.pWC = &pOrTerm->u.pAndInfo->wc; + }else if( pOrTerm->leftCursor==iCur ){ + tempWC.a = pOrTerm; + sSubBuild.pWC = &tempWC; + }else{ + continue; + } + sBest.maskSelf = 0; + if( IsVirtual(pItem->pTab) ){ + rc = whereLoopAddVirtual(&sSubBuild, mExtra); + }else{ + rc = whereLoopAddBtree(&sSubBuild, mExtra); + } + if( sBest.maskSelf==0 ) break; + assert( sBest.rSetup==(double)0 ); + rTotal += sBest.rRun; + nRow += sBest.nOut; + prereq |= sBest.prereq; + } + pNew->nTerm = 1; + pNew->aTerm[0] = pTerm; + pNew->wsFlags = WHERE_MULTI_OR; + pNew->rSetup = (double)0; + pNew->rRun = rTotal; + pNew->nOut = nRow; + pNew->prereq = prereq; + rc = whereLoopInsert(pBuilder, pNew); + } + } + return rc; +} /* ** Add all WhereLoop objects for all tables */ static int whereLoopAddAll(WhereLoopBuilder *pBuilder){ @@ -5617,15 +5716,13 @@ if( IsVirtual(pItem->pTab) ){ rc = whereLoopAddVirtual(pBuilder, mExtra); }else{ rc = whereLoopAddBtree(pBuilder, mExtra); } -#if 0 if( rc==SQLITE_OK ){ rc = whereLoopAddOr(pBuilder, mExtra); } -#endif mPrior |= pNew->maskSelf; if( rc || db->mallocFailed ) break; } whereLoopAddAll_end: whereLoopDelete(db, pBuilder->pNew);