diff options
Diffstat (limited to 'chromium/third_party/sqlite/src/src/where.c')
| -rw-r--r-- | chromium/third_party/sqlite/src/src/where.c | 781 |
1 files changed, 585 insertions, 196 deletions
diff --git a/chromium/third_party/sqlite/src/src/where.c b/chromium/third_party/sqlite/src/src/where.c index 6c2c64d18ec..448c9557637 100644 --- a/chromium/third_party/sqlite/src/src/where.c +++ b/chromium/third_party/sqlite/src/src/where.c @@ -67,7 +67,7 @@ int sqlite3WhereIsDistinct(WhereInfo *pWInfo){ ** block sorting is required. */ int sqlite3WhereIsOrdered(WhereInfo *pWInfo){ - return pWInfo->nOBSat; + return pWInfo->nOBSat<0 ? 0 : pWInfo->nOBSat; } /* @@ -705,7 +705,7 @@ static void translateColumnToCopy( #if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(WHERETRACE_ENABLED) static void whereTraceIndexInfoInputs(sqlite3_index_info *p){ int i; - if( !sqlite3WhereTrace ) return; + if( (sqlite3WhereTrace & 0x10)==0 ) return; for(i=0; i<p->nConstraint; i++){ sqlite3DebugPrintf( " constraint[%d]: col=%d termid=%d op=%d usabled=%d collseq=%s\n", @@ -725,7 +725,7 @@ static void whereTraceIndexInfoInputs(sqlite3_index_info *p){ } static void whereTraceIndexInfoOutputs(sqlite3_index_info *p){ int i; - if( !sqlite3WhereTrace ) return; + if( (sqlite3WhereTrace & 0x10)==0 ) return; for(i=0; i<p->nConstraint; i++){ sqlite3DebugPrintf(" usage[%d]: argvIdx=%d omit=%d\n", i, @@ -743,6 +743,43 @@ static void whereTraceIndexInfoOutputs(sqlite3_index_info *p){ #define whereTraceIndexInfoOutputs(A) #endif +/* +** We know that pSrc is an operand of an outer join. Return true if +** pTerm is a constraint that is compatible with that join. +** +** pTerm must be EP_OuterON if pSrc is the right operand of an +** outer join. pTerm can be either EP_OuterON or EP_InnerON if pSrc +** is the left operand of a RIGHT join. +** +** See https://sqlite.org/forum/forumpost/206d99a16dd9212f +** for an example of a WHERE clause constraints that may not be used on +** the right table of a RIGHT JOIN because the constraint implies a +** not-NULL condition on the left table of the RIGHT JOIN. +*/ +static int constraintCompatibleWithOuterJoin( + const WhereTerm *pTerm, /* WHERE clause term to check */ + const SrcItem *pSrc /* Table we are trying to access */ +){ + assert( (pSrc->fg.jointype&(JT_LEFT|JT_LTORJ|JT_RIGHT))!=0 ); /* By caller */ + testcase( (pSrc->fg.jointype & (JT_LEFT|JT_LTORJ|JT_RIGHT))==JT_LEFT ); + testcase( (pSrc->fg.jointype & (JT_LEFT|JT_LTORJ|JT_RIGHT))==JT_LTORJ ); + testcase( ExprHasProperty(pTerm->pExpr, EP_OuterON) ) + testcase( ExprHasProperty(pTerm->pExpr, EP_InnerON) ); + if( !ExprHasProperty(pTerm->pExpr, EP_OuterON|EP_InnerON) + || pTerm->pExpr->w.iJoin != pSrc->iCursor + ){ + return 0; + } + if( (pSrc->fg.jointype & (JT_LEFT|JT_RIGHT))!=0 + && ExprHasProperty(pTerm->pExpr, EP_InnerON) + ){ + return 0; + } + return 1; +} + + + #ifndef SQLITE_OMIT_AUTOMATIC_INDEX /* ** Return TRUE if the WHERE clause term pTerm is of a form where it @@ -758,16 +795,10 @@ static int termCanDriveIndex( if( pTerm->leftCursor!=pSrc->iCursor ) return 0; if( (pTerm->eOperator & (WO_EQ|WO_IS))==0 ) return 0; assert( (pSrc->fg.jointype & JT_RIGHT)==0 ); - if( (pSrc->fg.jointype & (JT_LEFT|JT_LTORJ|JT_RIGHT))!=0 ){ - testcase( (pSrc->fg.jointype & (JT_LEFT|JT_LTORJ|JT_RIGHT))==JT_LEFT ); - testcase( (pSrc->fg.jointype & (JT_LEFT|JT_LTORJ|JT_RIGHT))==JT_LTORJ ); - testcase( ExprHasProperty(pTerm->pExpr, EP_OuterON) ) - testcase( ExprHasProperty(pTerm->pExpr, EP_InnerON) ); - if( !ExprHasProperty(pTerm->pExpr, EP_OuterON|EP_InnerON) - || pTerm->pExpr->w.iJoin != pSrc->iCursor - ){ - return 0; /* See tag-20191211-001 */ - } + if( (pSrc->fg.jointype & (JT_LEFT|JT_LTORJ|JT_RIGHT))!=0 + && !constraintCompatibleWithOuterJoin(pTerm,pSrc) + ){ + return 0; /* See https://sqlite.org/forum/forumpost/51e6959f61 */ } if( (pTerm->prereqRight & notReady)!=0 ) return 0; assert( (pTerm->eOperator & (WO_OR|WO_AND))==0 ); @@ -781,6 +812,57 @@ static int termCanDriveIndex( #ifndef SQLITE_OMIT_AUTOMATIC_INDEX + +#ifdef SQLITE_ENABLE_STMT_SCANSTATUS +/* +** Argument pIdx represents an automatic index that the current statement +** will create and populate. Add an OP_Explain with text of the form: +** +** CREATE AUTOMATIC INDEX ON <table>(<cols>) [WHERE <expr>] +** +** This is only required if sqlite3_stmt_scanstatus() is enabled, to +** associate an SQLITE_SCANSTAT_NCYCLE and SQLITE_SCANSTAT_NLOOP +** values with. In order to avoid breaking legacy code and test cases, +** the OP_Explain is not added if this is an EXPLAIN QUERY PLAN command. +*/ +static void explainAutomaticIndex( + Parse *pParse, + Index *pIdx, /* Automatic index to explain */ + int bPartial, /* True if pIdx is a partial index */ + int *pAddrExplain /* OUT: Address of OP_Explain */ +){ + if( pParse->explain!=2 ){ + Table *pTab = pIdx->pTable; + const char *zSep = ""; + char *zText = 0; + int ii = 0; + sqlite3_str *pStr = sqlite3_str_new(pParse->db); + sqlite3_str_appendf(pStr,"CREATE AUTOMATIC INDEX ON %s(", pTab->zName); + assert( pIdx->nColumn>1 ); + assert( pIdx->aiColumn[pIdx->nColumn-1]==XN_ROWID ); + for(ii=0; ii<(pIdx->nColumn-1); ii++){ + const char *zName = 0; + int iCol = pIdx->aiColumn[ii]; + + zName = pTab->aCol[iCol].zCnName; + sqlite3_str_appendf(pStr, "%s%s", zSep, zName); + zSep = ", "; + } + zText = sqlite3_str_finish(pStr); + if( zText==0 ){ + sqlite3OomFault(pParse->db); + }else{ + *pAddrExplain = sqlite3VdbeExplain( + pParse, 0, "%s)%s", zText, (bPartial ? " WHERE <expr>" : "") + ); + sqlite3_free(zText); + } + } +} +#else +# define explainAutomaticIndex(a,b,c,d) +#endif + /* ** Generate code to construct the Index object for an automatic index ** and to set up the WhereLevel object pLevel so that the code generator @@ -816,6 +898,9 @@ static SQLITE_NOINLINE void constructAutomaticIndex( SrcItem *pTabItem; /* FROM clause term being indexed */ int addrCounter = 0; /* Address where integer counter is initialized */ int regBase; /* Array of registers where record is assembled */ +#ifdef SQLITE_ENABLE_STMT_SCANSTATUS + int addrExp = 0; /* Address of OP_Explain */ +#endif /* Generate code to skip over the creation and initialization of the ** transient index on 2nd and subsequent iterations of the loop. */ @@ -939,6 +1024,7 @@ static SQLITE_NOINLINE void constructAutomaticIndex( pIdx->azColl[n] = sqlite3StrBINARY; /* Create the automatic index */ + explainAutomaticIndex(pParse, pIdx, pPartial!=0, &addrExp); assert( pLevel->iIdxCur>=0 ); pLevel->iIdxCur = pParse->nTab++; sqlite3VdbeAddOp2(v, OP_OpenAutoindex, pLevel->iIdxCur, nKeyCol+1); @@ -974,6 +1060,7 @@ static SQLITE_NOINLINE void constructAutomaticIndex( sqlite3VdbeAddOp4Int(v, OP_FilterAdd, pLevel->regFilter, 0, regBase, pLoop->u.btree.nEq); } + sqlite3VdbeScanStatusCounters(v, addrExp, addrExp, sqlite3VdbeCurrentAddr(v)); sqlite3VdbeAddOp2(v, OP_IdxInsert, pLevel->iIdxCur, regRecord); sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT); if( pPartial ) sqlite3VdbeResolveLabel(v, iContinue); @@ -994,6 +1081,7 @@ static SQLITE_NOINLINE void constructAutomaticIndex( /* Jump here when skipping the initialization */ sqlite3VdbeJumpHere(v, addrInit); + sqlite3VdbeScanStatusRange(v, addrExp, addrExp, -1); end_auto_index_create: sqlite3ExprDelete(pParse->db, pPartial); @@ -1035,6 +1123,10 @@ static SQLITE_NOINLINE void sqlite3ConstructBloomFilter( Vdbe *v = pParse->pVdbe; /* VDBE under construction */ WhereLoop *pLoop = pLevel->pWLoop; /* The loop being coded */ int iCur; /* Cursor for table getting the filter */ + IndexedExpr *saved_pIdxEpr; /* saved copy of Parse.pIdxEpr */ + + saved_pIdxEpr = pParse->pIdxEpr; + pParse->pIdxEpr = 0; assert( pLoop!=0 ); assert( v!=0 ); @@ -1091,9 +1183,8 @@ static SQLITE_NOINLINE void sqlite3ConstructBloomFilter( int r1 = sqlite3GetTempRange(pParse, n); int jj; for(jj=0; jj<n; jj++){ - int iCol = pIdx->aiColumn[jj]; assert( pIdx->pTable==pItem->pTab ); - sqlite3ExprCodeGetColumnOfTable(v, pIdx->pTable, iCur, iCol,r1+jj); + sqlite3ExprCodeLoadIndexColumn(pParse, pIdx, iCur, jj, r1+jj); } sqlite3VdbeAddOp4Int(v, OP_FilterAdd, pLevel->regFilter, 0, r1, n); sqlite3ReleaseTempRange(pParse, r1, n); @@ -1124,6 +1215,7 @@ static SQLITE_NOINLINE void sqlite3ConstructBloomFilter( } }while( iLevel < pWInfo->nLevel ); sqlite3VdbeJumpHere(v, addrOnce); + pParse->pIdxEpr = saved_pIdxEpr; } @@ -1179,22 +1271,10 @@ static sqlite3_index_info *allocateIndexInfo( assert( (pTerm->eOperator & (WO_OR|WO_AND))==0 ); assert( pTerm->u.x.leftColumn>=XN_ROWID ); assert( pTerm->u.x.leftColumn<pTab->nCol ); - - /* tag-20191211-002: WHERE-clause constraints are not useful to the - ** right-hand table of a LEFT JOIN nor to the either table of a - ** RIGHT JOIN. See tag-20191211-001 for the - ** equivalent restriction for ordinary tables. */ - if( (pSrc->fg.jointype & (JT_LEFT|JT_LTORJ|JT_RIGHT))!=0 ){ - testcase( (pSrc->fg.jointype & (JT_LEFT|JT_LTORJ|JT_RIGHT))==JT_LEFT ); - testcase( (pSrc->fg.jointype & (JT_LEFT|JT_LTORJ|JT_RIGHT))==JT_RIGHT ); - testcase( (pSrc->fg.jointype & (JT_LEFT|JT_LTORJ|JT_RIGHT))==JT_LTORJ ); - testcase( ExprHasProperty(pTerm->pExpr, EP_OuterON) ); - testcase( ExprHasProperty(pTerm->pExpr, EP_InnerON) ); - if( !ExprHasProperty(pTerm->pExpr, EP_OuterON|EP_InnerON) - || pTerm->pExpr->w.iJoin != pSrc->iCursor - ){ - continue; - } + if( (pSrc->fg.jointype & (JT_LEFT|JT_LTORJ|JT_RIGHT))!=0 + && !constraintCompatibleWithOuterJoin(pTerm,pSrc) + ){ + continue; } nTerm++; pTerm->wtFlags |= TERM_OK; @@ -1434,6 +1514,7 @@ static int whereKeyStats( assert( pRec!=0 ); assert( pIdx->nSample>0 ); assert( pRec->nField>0 ); + /* Do a binary search to find the first sample greater than or equal ** to pRec. If pRec contains a single field, the set of samples to search @@ -1479,7 +1560,12 @@ static int whereKeyStats( ** it is extended to two fields. The duplicates that this creates do not ** cause any problems. */ - nField = MIN(pRec->nField, pIdx->nSample); + if( !HasRowid(pIdx->pTable) && IsPrimaryKeyIndex(pIdx) ){ + nField = pIdx->nKeyCol; + }else{ + nField = pIdx->nColumn; + } + nField = MIN(pRec->nField, nField); iCol = 0; iSample = pIdx->nSample * nField; do{ @@ -1545,12 +1631,12 @@ static int whereKeyStats( if( iCol>0 ){ pRec->nField = iCol; assert( sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, pRec)<=0 - || pParse->db->mallocFailed ); + || pParse->db->mallocFailed || CORRUPT_DB ); } if( i>0 ){ pRec->nField = nField; assert( sqlite3VdbeRecordCompare(aSample[i-1].n, aSample[i-1].p, pRec)<0 - || pParse->db->mallocFailed ); + || pParse->db->mallocFailed || CORRUPT_DB ); } } } @@ -1567,7 +1653,7 @@ static int whereKeyStats( ** is larger than all samples in the array. */ tRowcnt iUpper, iGap; if( i>=pIdx->nSample ){ - iUpper = sqlite3LogEstToInt(pIdx->aiRowLogEst[0]); + iUpper = pIdx->nRowEst0; }else{ iUpper = aSample[i].anLt[iCol]; } @@ -1723,7 +1809,7 @@ static int whereRangeSkipScanEst( int nAdjust = (sqlite3LogEst(p->nSample) - sqlite3LogEst(nDiff)); pLoop->nOut -= nAdjust; *pbDone = 1; - WHERETRACE(0x10, ("range skip-scan regions: %u..%u adjust=%d est=%d\n", + WHERETRACE(0x20, ("range skip-scan regions: %u..%u adjust=%d est=%d\n", nLower, nUpper, nAdjust*-1, pLoop->nOut)); } @@ -1901,7 +1987,7 @@ static int whereRangeScanEst( if( nNew<nOut ){ nOut = nNew; } - WHERETRACE(0x10, ("STAT4 range scan: %u..%u est=%d\n", + WHERETRACE(0x20, ("STAT4 range scan: %u..%u est=%d\n", (u32)iLower, (u32)iUpper, nOut)); } }else{ @@ -1934,7 +2020,7 @@ static int whereRangeScanEst( if( nNew<nOut ) nOut = nNew; #if defined(WHERETRACE_ENABLED) if( pLoop->nOut>nOut ){ - WHERETRACE(0x10,("Range scan lowers nOut from %d to %d\n", + WHERETRACE(0x20,("Range scan lowers nOut from %d to %d\n", pLoop->nOut, nOut)); } #endif @@ -1999,7 +2085,7 @@ static int whereEqualScanEst( pBuilder->nRecValid = nEq; whereKeyStats(pParse, p, pRec, 0, a); - WHERETRACE(0x10,("equality scan regions %s(%d): %d\n", + WHERETRACE(0x20,("equality scan regions %s(%d): %d\n", p->zName, nEq-1, (int)a[1])); *pnRow = a[1]; @@ -2047,9 +2133,9 @@ static int whereInScanEst( } if( rc==SQLITE_OK ){ - if( nRowEst > nRow0 ) nRowEst = nRow0; + if( nRowEst > (tRowcnt)nRow0 ) nRowEst = nRow0; *pnRow = nRowEst; - WHERETRACE(0x10,("IN row estimate: est=%d\n", nRowEst)); + WHERETRACE(0x20,("IN row estimate: est=%d\n", nRowEst)); } assert( pBuilder->nRecValid==nRecValid ); return rc; @@ -2158,7 +2244,7 @@ void sqlite3WhereLoopPrint(WhereLoop *p, WhereClause *pWC){ sqlite3DebugPrintf(" f %06x N %d", p->wsFlags, p->nLTerm); } sqlite3DebugPrintf(" cost %d,%d,%d\n", p->rSetup, p->rRun, p->nOut); - if( p->nLTerm && (sqlite3WhereTrace & 0x100)!=0 ){ + if( p->nLTerm && (sqlite3WhereTrace & 0x4000)!=0 ){ int i; for(i=0; i<p->nLTerm; i++){ sqlite3WhereTermPrint(p->aLTerm[i], i); @@ -2196,12 +2282,18 @@ static void whereLoopClearUnion(sqlite3 *db, WhereLoop *p){ } /* -** Deallocate internal memory used by a WhereLoop object +** Deallocate internal memory used by a WhereLoop object. Leave the +** object in an initialized state, as if it had been newly allocated. */ static void whereLoopClear(sqlite3 *db, WhereLoop *p){ - if( p->aLTerm!=p->aLTermSpace ) sqlite3DbFreeNN(db, p->aLTerm); + if( p->aLTerm!=p->aLTermSpace ){ + sqlite3DbFreeNN(db, p->aLTerm); + p->aLTerm = p->aLTermSpace; + p->nLSlot = ArraySize(p->aLTermSpace); + } whereLoopClearUnion(db, p); - whereLoopInit(p); + p->nLTerm = 0; + p->wsFlags = 0; } /* @@ -2225,7 +2317,9 @@ static int whereLoopResize(sqlite3 *db, WhereLoop *p, int n){ */ static int whereLoopXfer(sqlite3 *db, WhereLoop *pTo, WhereLoop *pFrom){ whereLoopClearUnion(db, pTo); - if( whereLoopResize(db, pTo, pFrom->nLTerm) ){ + if( pFrom->nLTerm > pTo->nLSlot + && whereLoopResize(db, pTo, pFrom->nLTerm) + ){ memset(pTo, 0, WHERE_LOOP_XFER_SZ); return SQLITE_NOMEM_BKPT; } @@ -2243,8 +2337,9 @@ static int whereLoopXfer(sqlite3 *db, WhereLoop *pTo, WhereLoop *pFrom){ ** Delete a WhereLoop object */ static void whereLoopDelete(sqlite3 *db, WhereLoop *p){ + assert( db!=0 ); whereLoopClear(db, p); - sqlite3DbFreeNN(db, p); + sqlite3DbNNFreeNN(db, p); } /* @@ -2252,30 +2347,19 @@ static void whereLoopDelete(sqlite3 *db, WhereLoop *p){ */ static void whereInfoFree(sqlite3 *db, WhereInfo *pWInfo){ assert( pWInfo!=0 ); + assert( db!=0 ); sqlite3WhereClauseClear(&pWInfo->sWC); while( pWInfo->pLoops ){ WhereLoop *p = pWInfo->pLoops; pWInfo->pLoops = p->pNextLoop; whereLoopDelete(db, p); } - assert( pWInfo->pExprMods==0 ); while( pWInfo->pMemToFree ){ WhereMemBlock *pNext = pWInfo->pMemToFree->pNext; - sqlite3DbFreeNN(db, pWInfo->pMemToFree); + sqlite3DbNNFreeNN(db, pWInfo->pMemToFree); pWInfo->pMemToFree = pNext; } - sqlite3DbFreeNN(db, pWInfo); -} - -/* Undo all Expr node modifications -*/ -static void whereUndoExprMods(WhereInfo *pWInfo){ - while( pWInfo->pExprMods ){ - WhereExprMod *p = pWInfo->pExprMods; - pWInfo->pExprMods = p->pNext; - memcpy(p->pExpr, &p->orig, sizeof(p->orig)); - sqlite3DbFree(pWInfo->pParse->db, p); - } + sqlite3DbNNFreeNN(db, pWInfo); } /* @@ -2624,6 +2708,7 @@ static void whereLoopOutputAdjust( if( pX->iParent>=0 && (&pWC->a[pX->iParent])==pTerm ) break; } if( j<0 ){ + sqlite3ProgressCheck(pWC->pWInfo->pParse); if( pLoop->maskSelf==pTerm->prereqAll ){ /* If there are extra terms in the WHERE clause not used by an index ** that depend only on the table being scanned, and that will tend to @@ -2791,7 +2876,10 @@ static int whereLoopAddBtreeIndex( WhereTerm *pTop = 0, *pBtm = 0; /* Top and bottom range constraints */ pNew = pBuilder->pNew; - if( db->mallocFailed ) return SQLITE_NOMEM_BKPT; + assert( db->mallocFailed==0 || pParse->nErr>0 ); + if( pParse->nErr ){ + return pParse->rc; + } WHERETRACE(0x800, ("BEGIN %s.addBtreeIdx(%s), nEq=%d, nSkip=%d, rRun=%d\n", pProbe->pTable->zName,pProbe->zName, pNew->u.btree.nEq, pNew->nSkip, pNew->rRun)); @@ -2842,32 +2930,11 @@ static int whereLoopAddBtreeIndex( ** to mix with a lower range bound from some other source */ if( pTerm->wtFlags & TERM_LIKEOPT && pTerm->eOperator==WO_LT ) continue; - /* tag-20191211-001: Do not allow constraints from the WHERE clause to - ** be used by the right table of a LEFT JOIN nor by the left table of a - ** RIGHT JOIN. Only constraints in the ON clause are allowed. - ** See tag-20191211-002 for the vtab equivalent. - ** - ** 2022-06-06: See https://sqlite.org/forum/forumpost/206d99a16dd9212f - ** for an example of a WHERE clause constraints that may not be used on - ** the right table of a RIGHT JOIN because the constraint implies a - ** not-NULL condition on the left table of the RIGHT JOIN. - ** - ** 2022-06-10: The same condition applies to termCanDriveIndex() above. - ** https://sqlite.org/forum/forumpost/51e6959f61 - */ - if( (pSrc->fg.jointype & (JT_LEFT|JT_LTORJ|JT_RIGHT))!=0 ){ - testcase( (pSrc->fg.jointype & (JT_LEFT|JT_LTORJ|JT_RIGHT))==JT_LEFT ); - testcase( (pSrc->fg.jointype & (JT_LEFT|JT_LTORJ|JT_RIGHT))==JT_RIGHT ); - testcase( (pSrc->fg.jointype & (JT_LEFT|JT_LTORJ|JT_RIGHT))==JT_LTORJ ); - testcase( ExprHasProperty(pTerm->pExpr, EP_OuterON) ) - testcase( ExprHasProperty(pTerm->pExpr, EP_InnerON) ); - if( !ExprHasProperty(pTerm->pExpr, EP_OuterON|EP_InnerON) - || pTerm->pExpr->w.iJoin != pSrc->iCursor - ){ - continue; - } + if( (pSrc->fg.jointype & (JT_LEFT|JT_LTORJ|JT_RIGHT))!=0 + && !constraintCompatibleWithOuterJoin(pTerm,pSrc) + ){ + continue; } - if( IsUniqueIndex(pProbe) && saved_nEq==pProbe->nKeyCol-1 ){ pBuilder->bldFlags1 |= SQLITE_BLDF1_UNIQUE; }else{ @@ -2878,7 +2945,11 @@ static int whereLoopAddBtreeIndex( pNew->u.btree.nBtm = saved_nBtm; pNew->u.btree.nTop = saved_nTop; pNew->nLTerm = saved_nLTerm; - if( whereLoopResize(db, pNew, pNew->nLTerm+1) ) break; /* OOM */ + if( pNew->nLTerm>=pNew->nLSlot + && whereLoopResize(db, pNew, pNew->nLTerm+1) + ){ + break; /* OOM while trying to enlarge the pNew->aLTerm array */ + } pNew->aLTerm[pNew->nLTerm++] = pTerm; pNew->prereq = (saved_prereq | pTerm->prereqRight) & ~pNew->maskSelf; @@ -2971,38 +3042,39 @@ static int whereLoopAddBtreeIndex( if( scan.iEquiv>1 ) pNew->wsFlags |= WHERE_TRANSCONS; }else if( eOp & WO_ISNULL ){ pNew->wsFlags |= WHERE_COLUMN_NULL; - }else if( eOp & (WO_GT|WO_GE) ){ - testcase( eOp & WO_GT ); - testcase( eOp & WO_GE ); - pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_BTM_LIMIT; - pNew->u.btree.nBtm = whereRangeVectorLen( - pParse, pSrc->iCursor, pProbe, saved_nEq, pTerm - ); - pBtm = pTerm; - pTop = 0; - if( pTerm->wtFlags & TERM_LIKEOPT ){ - /* Range constraints that come from the LIKE optimization are - ** always used in pairs. */ - pTop = &pTerm[1]; - assert( (pTop-(pTerm->pWC->a))<pTerm->pWC->nTerm ); - assert( pTop->wtFlags & TERM_LIKEOPT ); - assert( pTop->eOperator==WO_LT ); - if( whereLoopResize(db, pNew, pNew->nLTerm+1) ) break; /* OOM */ - pNew->aLTerm[pNew->nLTerm++] = pTop; - pNew->wsFlags |= WHERE_TOP_LIMIT; - pNew->u.btree.nTop = 1; - } }else{ - assert( eOp & (WO_LT|WO_LE) ); - testcase( eOp & WO_LT ); - testcase( eOp & WO_LE ); - pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_TOP_LIMIT; - pNew->u.btree.nTop = whereRangeVectorLen( + int nVecLen = whereRangeVectorLen( pParse, pSrc->iCursor, pProbe, saved_nEq, pTerm ); - pTop = pTerm; - pBtm = (pNew->wsFlags & WHERE_BTM_LIMIT)!=0 ? - pNew->aLTerm[pNew->nLTerm-2] : 0; + if( eOp & (WO_GT|WO_GE) ){ + testcase( eOp & WO_GT ); + testcase( eOp & WO_GE ); + pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_BTM_LIMIT; + pNew->u.btree.nBtm = nVecLen; + pBtm = pTerm; + pTop = 0; + if( pTerm->wtFlags & TERM_LIKEOPT ){ + /* Range constraints that come from the LIKE optimization are + ** always used in pairs. */ + pTop = &pTerm[1]; + assert( (pTop-(pTerm->pWC->a))<pTerm->pWC->nTerm ); + assert( pTop->wtFlags & TERM_LIKEOPT ); + assert( pTop->eOperator==WO_LT ); + if( whereLoopResize(db, pNew, pNew->nLTerm+1) ) break; /* OOM */ + pNew->aLTerm[pNew->nLTerm++] = pTop; + pNew->wsFlags |= WHERE_TOP_LIMIT; + pNew->u.btree.nTop = 1; + } + }else{ + assert( eOp & (WO_LT|WO_LE) ); + testcase( eOp & WO_LT ); + testcase( eOp & WO_LE ); + pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_TOP_LIMIT; + pNew->u.btree.nTop = nVecLen; + pTop = pTerm; + pBtm = (pNew->wsFlags & WHERE_BTM_LIMIT)!=0 ? + pNew->aLTerm[pNew->nLTerm-2] : 0; + } } /* At this point pNew->nOut is set to the number of rows expected to @@ -3054,7 +3126,7 @@ static int whereLoopAddBtreeIndex( && pNew->nOut+10 > pProbe->aiRowLogEst[0] ){ #if WHERETRACE_ENABLED /* 0x01 */ - if( sqlite3WhereTrace & 0x01 ){ + if( sqlite3WhereTrace & 0x20 ){ sqlite3DebugPrintf( "STAT4 determines term has low selectivity:\n"); sqlite3WhereTermPrint(pTerm, 999); @@ -3091,9 +3163,17 @@ static int whereLoopAddBtreeIndex( ** seek only. Then, if this is a non-covering index, add the cost of ** visiting the rows in the main table. */ assert( pSrc->pTab->szTabRow>0 ); - rCostIdx = pNew->nOut + 1 + (15*pProbe->szIdxRow)/pSrc->pTab->szTabRow; + if( pProbe->idxType==SQLITE_IDXTYPE_IPK ){ + /* The pProbe->szIdxRow is low for an IPK table since the interior + ** pages are small. Thuse szIdxRow gives a good estimate of seek cost. + ** But the leaf pages are full-size, so pProbe->szIdxRow would badly + ** under-estimate the scanning cost. */ + rCostIdx = pNew->nOut + 16; + }else{ + rCostIdx = pNew->nOut + 1 + (15*pProbe->szIdxRow)/pSrc->pTab->szTabRow; + } pNew->rRun = sqlite3LogEstAdd(rLogSize, rCostIdx); - if( (pNew->wsFlags & (WHERE_IDX_ONLY|WHERE_IPK))==0 ){ + if( (pNew->wsFlags & (WHERE_IDX_ONLY|WHERE_IPK|WHERE_EXPRIDX))==0 ){ pNew->rRun = sqlite3LogEstAdd(pNew->rRun, pNew->nOut + 16); } ApplyCostMultiplier(pNew->rRun, pProbe->pTable->costMult); @@ -3115,6 +3195,9 @@ static int whereLoopAddBtreeIndex( && (pNew->u.btree.nEq<pProbe->nKeyCol || pProbe->idxType!=SQLITE_IDXTYPE_PRIMARYKEY) ){ + if( pNew->u.btree.nEq>3 ){ + sqlite3ProgressCheck(pParse); + } whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul+nIn); } pNew->nOut = saved_nOut; @@ -3247,6 +3330,149 @@ static int whereUsablePartialIndex( } /* +** pIdx is an index containing expressions. Check it see if any of the +** expressions in the index match the pExpr expression. +*/ +static int exprIsCoveredByIndex( + const Expr *pExpr, + const Index *pIdx, + int iTabCur +){ + int i; + for(i=0; i<pIdx->nColumn; i++){ + if( pIdx->aiColumn[i]==XN_EXPR + && sqlite3ExprCompare(0, pExpr, pIdx->aColExpr->a[i].pExpr, iTabCur)==0 + ){ + return 1; + } + } + return 0; +} + +/* +** Structure passed to the whereIsCoveringIndex Walker callback. +*/ +typedef struct CoveringIndexCheck CoveringIndexCheck; +struct CoveringIndexCheck { + Index *pIdx; /* The index */ + int iTabCur; /* Cursor number for the corresponding table */ + u8 bExpr; /* Uses an indexed expression */ + u8 bUnidx; /* Uses an unindexed column not within an indexed expr */ +}; + +/* +** Information passed in is pWalk->u.pCovIdxCk. Call it pCk. +** +** If the Expr node references the table with cursor pCk->iTabCur, then +** make sure that column is covered by the index pCk->pIdx. We know that +** all columns less than 63 (really BMS-1) are covered, so we don't need +** to check them. But we do need to check any column at 63 or greater. +** +** If the index does not cover the column, then set pWalk->eCode to +** non-zero and return WRC_Abort to stop the search. +** +** If this node does not disprove that the index can be a covering index, +** then just return WRC_Continue, to continue the search. +** +** If pCk->pIdx contains indexed expressions and one of those expressions +** matches pExpr, then prune the search. +*/ +static int whereIsCoveringIndexWalkCallback(Walker *pWalk, Expr *pExpr){ + int i; /* Loop counter */ + const Index *pIdx; /* The index of interest */ + const i16 *aiColumn; /* Columns contained in the index */ + u16 nColumn; /* Number of columns in the index */ + CoveringIndexCheck *pCk; /* Info about this search */ + + pCk = pWalk->u.pCovIdxCk; + pIdx = pCk->pIdx; + if( (pExpr->op==TK_COLUMN || pExpr->op==TK_AGG_COLUMN) ){ + /* if( pExpr->iColumn<(BMS-1) && pIdx->bHasExpr==0 ) return WRC_Continue;*/ + if( pExpr->iTable!=pCk->iTabCur ) return WRC_Continue; + pIdx = pWalk->u.pCovIdxCk->pIdx; + aiColumn = pIdx->aiColumn; + nColumn = pIdx->nColumn; + for(i=0; i<nColumn; i++){ + if( aiColumn[i]==pExpr->iColumn ) return WRC_Continue; + } + pCk->bUnidx = 1; + return WRC_Abort; + }else if( pIdx->bHasExpr + && exprIsCoveredByIndex(pExpr, pIdx, pWalk->u.pCovIdxCk->iTabCur) ){ + pCk->bExpr = 1; + return WRC_Prune; + } + return WRC_Continue; +} + + +/* +** pIdx is an index that covers all of the low-number columns used by +** pWInfo->pSelect (columns from 0 through 62) or an index that has +** expressions terms. Hence, we cannot determine whether or not it is +** a covering index by using the colUsed bitmasks. We have to do a search +** to see if the index is covering. This routine does that search. +** +** The return value is one of these: +** +** 0 The index is definitely not a covering index +** +** WHERE_IDX_ONLY The index is definitely a covering index +** +** WHERE_EXPRIDX The index is likely a covering index, but it is +** difficult to determine precisely because of the +** expressions that are indexed. Score it as a +** covering index, but still keep the main table open +** just in case we need it. +** +** This routine is an optimization. It is always safe to return zero. +** But returning one of the other two values when zero should have been +** returned can lead to incorrect bytecode and assertion faults. +*/ +static SQLITE_NOINLINE u32 whereIsCoveringIndex( + WhereInfo *pWInfo, /* The WHERE clause context */ + Index *pIdx, /* Index that is being tested */ + int iTabCur /* Cursor for the table being indexed */ +){ + int i, rc; + struct CoveringIndexCheck ck; + Walker w; + if( pWInfo->pSelect==0 ){ + /* We don't have access to the full query, so we cannot check to see + ** if pIdx is covering. Assume it is not. */ + return 0; + } + if( pIdx->bHasExpr==0 ){ + for(i=0; i<pIdx->nColumn; i++){ + if( pIdx->aiColumn[i]>=BMS-1 ) break; + } + if( i>=pIdx->nColumn ){ + /* pIdx does not index any columns greater than 62, but we know from + ** colMask that columns greater than 62 are used, so this is not a + ** covering index */ + return 0; + } + } + ck.pIdx = pIdx; + ck.iTabCur = iTabCur; + ck.bExpr = 0; + ck.bUnidx = 0; + memset(&w, 0, sizeof(w)); + w.xExprCallback = whereIsCoveringIndexWalkCallback; + w.xSelectCallback = sqlite3SelectWalkNoop; + w.u.pCovIdxCk = &ck; + sqlite3WalkSelect(&w, pWInfo->pSelect); + if( ck.bUnidx ){ + rc = 0; + }else if( ck.bExpr ){ + rc = WHERE_EXPRIDX; + }else{ + rc = WHERE_IDX_ONLY; + } + return rc; +} + +/* ** Add all WhereLoop objects for a single table of the join where the table ** is identified by pBuilder->pNew->iTab. That table is guaranteed to be ** a b-tree table, not a virtual table. @@ -3328,7 +3554,7 @@ static int whereLoopAddBtree( sPk.aiRowLogEst = aiRowEstPk; sPk.onError = OE_Replace; sPk.pTable = pTab; - sPk.szIdxRow = pTab->szTabRow; + sPk.szIdxRow = 3; /* TUNING: Interior rows of IPK table are very small */ sPk.idxType = SQLITE_IDXTYPE_IPK; aiRowEstPk[0] = pTab->nRowLogEst; aiRowEstPk[1] = 0; @@ -3379,7 +3605,8 @@ static int whereLoopAddBtree( if( !IsView(pTab) && (pTab->tabFlags & TF_Ephemeral)==0 ){ pNew->rSetup += 28; }else{ - pNew->rSetup -= 10; + pNew->rSetup -= 25; /* Greatly reduced setup cost for auto indexes + ** on ephemeral materializations of views */ } ApplyCostMultiplier(pNew->rSetup, pTab->costMult); if( pNew->rSetup<0 ) pNew->rSetup = 0; @@ -3448,6 +3675,9 @@ static int whereLoopAddBtree( #else pNew->rRun = rSize + 16; #endif + if( IsView(pTab) || (pTab->tabFlags & TF_Ephemeral)!=0 ){ + pNew->wsFlags |= WHERE_VIEWSCAN; + } ApplyCostMultiplier(pNew->rRun, pTab->costMult); whereLoopOutputAdjust(pWC, pNew, rSize); rc = whereLoopInsert(pBuilder, pNew); @@ -3456,11 +3686,38 @@ static int whereLoopAddBtree( }else{ Bitmask m; if( pProbe->isCovering ){ - pNew->wsFlags = WHERE_IDX_ONLY | WHERE_INDEXED; m = 0; + pNew->wsFlags = WHERE_IDX_ONLY | WHERE_INDEXED; }else{ m = pSrc->colUsed & pProbe->colNotIdxed; - pNew->wsFlags = (m==0) ? (WHERE_IDX_ONLY|WHERE_INDEXED) : WHERE_INDEXED; + pNew->wsFlags = WHERE_INDEXED; + if( m==TOPBIT || (pProbe->bHasExpr && !pProbe->bHasVCol && m!=0) ){ + u32 isCov = whereIsCoveringIndex(pWInfo, pProbe, pSrc->iCursor); + if( isCov==0 ){ + WHERETRACE(0x200, + ("-> %s is not a covering index" + " according to whereIsCoveringIndex()\n", pProbe->zName)); + assert( m!=0 ); + }else{ + m = 0; + pNew->wsFlags |= isCov; + if( isCov & WHERE_IDX_ONLY ){ + WHERETRACE(0x200, + ("-> %s is a covering expression index" + " according to whereIsCoveringIndex()\n", pProbe->zName)); + }else{ + assert( isCov==WHERE_EXPRIDX ); + WHERETRACE(0x200, + ("-> %s might be a covering expression index" + " according to whereIsCoveringIndex()\n", pProbe->zName)); + } + } + }else if( m==0 ){ + WHERETRACE(0x200, + ("-> %s a covering index according to bitmasks\n", + pProbe->zName, m==0 ? "is" : "is not")); + pNew->wsFlags = WHERE_IDX_ONLY | WHERE_INDEXED; + } } /* Full scan via index */ @@ -3633,7 +3890,7 @@ static int whereLoopAddVirtualOne( ** that the particular combination of parameters provided is unusable. ** Make no entries in the loop table. */ - WHERETRACE(0xffff, (" ^^^^--- non-viable plan rejected!\n")); + WHERETRACE(0xffffffff, (" ^^^^--- non-viable plan rejected!\n")); return SQLITE_OK; } return rc; @@ -3744,7 +4001,7 @@ static int whereLoopAddVirtualOne( sqlite3_free(pNew->u.vtab.idxStr); pNew->u.vtab.needFree = 0; } - WHERETRACE(0xffff, (" bIn=%d prereqIn=%04llx prereqOut=%04llx\n", + WHERETRACE(0xffffffff, (" bIn=%d prereqIn=%04llx prereqOut=%04llx\n", *pbIn, (sqlite3_uint64)mPrereq, (sqlite3_uint64)(pNew->prereq & ~mPrereq))); @@ -3849,7 +4106,7 @@ int sqlite3_vtab_distinct(sqlite3_index_info *pIdxInfo){ && !defined(SQLITE_OMIT_VIRTUALTABLE) /* ** Cause the prepared statement that is associated with a call to -** xBestIndex to potentiall use all schemas. If the statement being +** xBestIndex to potentially use all schemas. If the statement being ** prepared is read-only, then just start read transactions on all ** schemas. But if this is a write operation, start writes on all ** schemas. @@ -3864,7 +4121,7 @@ void sqlite3VtabUsesAllSchemas(sqlite3_index_info *pIdxInfo){ for(i=0; i<nDb; i++){ sqlite3CodeVerifySchema(pParse, i); } - if( pParse->writeMask ){ + if( DbMaskNonZero(pParse->writeMask) ){ for(i=0; i<nDb; i++){ sqlite3BeginWriteOperation(pParse, 0, i); } @@ -3936,7 +4193,7 @@ static int whereLoopAddVirtual( /* First call xBestIndex() with all constraints usable. */ WHERETRACE(0x800, ("BEGIN %s.addVirtual()\n", pSrc->pTab->zName)); - WHERETRACE(0x40, (" VirtualOne: all usable\n")); + WHERETRACE(0x800, (" VirtualOne: all usable\n")); rc = whereLoopAddVirtualOne( pBuilder, mPrereq, ALLBITS, 0, p, mNoOmit, &bIn, &bRetry ); @@ -3961,7 +4218,7 @@ static int whereLoopAddVirtual( /* If the plan produced by the earlier call uses an IN(...) term, call ** xBestIndex again, this time with IN(...) terms disabled. */ if( bIn ){ - WHERETRACE(0x40, (" VirtualOne: all usable w/o IN\n")); + WHERETRACE(0x800, (" VirtualOne: all usable w/o IN\n")); rc = whereLoopAddVirtualOne( pBuilder, mPrereq, ALLBITS, WO_IN, p, mNoOmit, &bIn, 0); assert( bIn==0 ); @@ -3987,7 +4244,7 @@ static int whereLoopAddVirtual( mPrev = mNext; if( mNext==ALLBITS ) break; if( mNext==mBest || mNext==mBestNoIn ) continue; - WHERETRACE(0x40, (" VirtualOne: mPrev=%04llx mNext=%04llx\n", + WHERETRACE(0x800, (" VirtualOne: mPrev=%04llx mNext=%04llx\n", (sqlite3_uint64)mPrev, (sqlite3_uint64)mNext)); rc = whereLoopAddVirtualOne( pBuilder, mPrereq, mNext|mPrereq, 0, p, mNoOmit, &bIn, 0); @@ -4001,7 +4258,7 @@ static int whereLoopAddVirtual( ** that requires no source tables at all (i.e. one guaranteed to be ** usable), make a call here with all source tables disabled */ if( rc==SQLITE_OK && seenZero==0 ){ - WHERETRACE(0x40, (" VirtualOne: all disabled\n")); + WHERETRACE(0x800, (" VirtualOne: all disabled\n")); rc = whereLoopAddVirtualOne( pBuilder, mPrereq, mPrereq, 0, p, mNoOmit, &bIn, 0); if( bIn==0 ) seenZeroNoIN = 1; @@ -4011,7 +4268,7 @@ static int whereLoopAddVirtual( ** that requires no source tables at all and does not use an IN(...) ** operator, make a final call to obtain one here. */ if( rc==SQLITE_OK && seenZeroNoIN==0 ){ - WHERETRACE(0x40, (" VirtualOne: all disabled and w/o IN\n")); + WHERETRACE(0x800, (" VirtualOne: all disabled and w/o IN\n")); rc = whereLoopAddVirtualOne( pBuilder, mPrereq, mPrereq, WO_IN, p, mNoOmit, &bIn, 0); } @@ -4067,7 +4324,7 @@ static int whereLoopAddOr( sSubBuild = *pBuilder; sSubBuild.pOrSet = &sCur; - WHERETRACE(0x200, ("Begin processing OR-clause %p\n", pTerm)); + WHERETRACE(0x400, ("Begin processing OR-clause %p\n", pTerm)); for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){ if( (pOrTerm->eOperator & WO_AND)!=0 ){ sSubBuild.pWC = &pOrTerm->u.pAndInfo->wc; @@ -4084,9 +4341,9 @@ static int whereLoopAddOr( } sCur.n = 0; #ifdef WHERETRACE_ENABLED - WHERETRACE(0x200, ("OR-term %d of %p has %d subterms:\n", + WHERETRACE(0x400, ("OR-term %d of %p has %d subterms:\n", (int)(pOrTerm-pOrWC->a), pTerm, sSubBuild.pWC->nTerm)); - if( sqlite3WhereTrace & 0x400 ){ + if( sqlite3WhereTrace & 0x20000 ){ sqlite3WhereClausePrint(sSubBuild.pWC); } #endif @@ -4101,8 +4358,6 @@ static int whereLoopAddOr( if( rc==SQLITE_OK ){ rc = whereLoopAddOr(&sSubBuild, mPrereq, mUnusable); } - assert( rc==SQLITE_OK || rc==SQLITE_DONE || sCur.n==0 - || rc==SQLITE_NOMEM ); testcase( rc==SQLITE_NOMEM && sCur.n>0 ); testcase( rc==SQLITE_DONE ); if( sCur.n==0 ){ @@ -4148,7 +4403,7 @@ static int whereLoopAddOr( pNew->prereq = sSum.a[i].prereq; rc = whereLoopInsert(pBuilder, pNew); } - WHERETRACE(0x200, ("End processing OR-clause %p\n", pTerm)); + WHERETRACE(0x400, ("End processing OR-clause %p\n", pTerm)); } } return rc; @@ -4174,7 +4429,13 @@ static int whereLoopAddAll(WhereLoopBuilder *pBuilder){ /* Loop over the tables in the join, from left to right */ pNew = pBuilder->pNew; - whereLoopInit(pNew); + + /* Verify that pNew has already been initialized */ + assert( pNew->nLTerm==0 ); + assert( pNew->wsFlags==0 ); + assert( pNew->nLSlot>=ArraySize(pNew->aLTermSpace) ); + assert( pNew->aLTerm!=0 ); + pBuilder->iPlanLimit = SQLITE_QUERY_PLANNER_LIMIT; for(iTab=0, pItem=pTabList->a; pItem<pEnd; iTab++, pItem++){ Bitmask mUnusable = 0; @@ -4490,8 +4751,8 @@ static i8 wherePathSatisfiesOrderBy( if( pOBExpr->iTable!=iCur ) continue; if( pOBExpr->iColumn!=iColumn ) continue; }else{ - Expr *pIdxExpr = pIndex->aColExpr->a[j].pExpr; - if( sqlite3ExprCompareSkip(pOBExpr, pIdxExpr, iCur) ){ + Expr *pIxExpr = pIndex->aColExpr->a[j].pExpr; + if( sqlite3ExprCompareSkip(pOBExpr, pIxExpr, iCur) ){ continue; } } @@ -4623,37 +4884,56 @@ static const char *wherePathName(WherePath *pPath, int nLoop, WhereLoop *pLast){ ** order. */ static LogEst whereSortingCost( - WhereInfo *pWInfo, - LogEst nRow, - int nOrderBy, - int nSorted + WhereInfo *pWInfo, /* Query planning context */ + LogEst nRow, /* Estimated number of rows to sort */ + int nOrderBy, /* Number of ORDER BY clause terms */ + int nSorted /* Number of initial ORDER BY terms naturally in order */ ){ - /* TUNING: Estimated cost of a full external sort, where N is + /* Estimated cost of a full external sort, where N is ** the number of rows to sort is: ** - ** cost = (3.0 * N * log(N)). + ** cost = (K * N * log(N)). ** ** Or, if the order-by clause has X terms but only the last Y ** terms are out of order, then block-sorting will reduce the ** sorting cost to: ** - ** cost = (3.0 * N * log(N)) * (Y/X) + ** cost = (K * N * log(N)) * (Y/X) + ** + ** The constant K is at least 2.0 but will be larger if there are a + ** large number of columns to be sorted, as the sorting time is + ** proportional to the amount of content to be sorted. The algorithm + ** does not currently distinguish between fat columns (BLOBs and TEXTs) + ** and skinny columns (INTs). It just uses the number of columns as + ** an approximation for the row width. ** - ** The (Y/X) term is implemented using stack variable rScale - ** below. + ** And extra factor of 2.0 or 3.0 is added to the sorting cost if the sort + ** is built using OP_IdxInsert and OP_Sort rather than with OP_SorterInsert. */ - LogEst rScale, rSortCost; - assert( nOrderBy>0 && 66==sqlite3LogEst(100) ); - rScale = sqlite3LogEst((nOrderBy-nSorted)*100/nOrderBy) - 66; - rSortCost = nRow + rScale + 16; + LogEst rSortCost, nCol; + assert( pWInfo->pSelect!=0 ); + assert( pWInfo->pSelect->pEList!=0 ); + /* TUNING: sorting cost proportional to the number of output columns: */ + nCol = sqlite3LogEst((pWInfo->pSelect->pEList->nExpr+59)/30); + rSortCost = nRow + nCol; + if( nSorted>0 ){ + /* Scale the result by (Y/X) */ + rSortCost += sqlite3LogEst((nOrderBy-nSorted)*100/nOrderBy) - 66; + } /* Multiple by log(M) where M is the number of output rows. ** Use the LIMIT for M if it is smaller. Or if this sort is for ** a DISTINCT operator, M will be the number of distinct output ** rows, so fudge it downwards a bit. */ - if( (pWInfo->wctrlFlags & WHERE_USE_LIMIT)!=0 && pWInfo->iLimit<nRow ){ - nRow = pWInfo->iLimit; + if( (pWInfo->wctrlFlags & WHERE_USE_LIMIT)!=0 ){ + rSortCost += 10; /* TUNING: Extra 2.0x if using LIMIT */ + if( nSorted!=0 ){ + rSortCost += 6; /* TUNING: Extra 1.5x if also using partial sort */ + } + if( pWInfo->iLimit<nRow ){ + nRow = pWInfo->iLimit; + } }else if( (pWInfo->wctrlFlags & WHERE_WANT_DISTINCT) ){ /* TUNING: In the sort for a DISTINCT operator, assume that the DISTINCT ** reduces the number of output rows by a factor of 2 */ @@ -4679,7 +4959,6 @@ static int wherePathSolver(WhereInfo *pWInfo, LogEst nRowEst){ int mxChoice; /* Maximum number of simultaneous paths tracked */ int nLoop; /* Number of terms in the join */ Parse *pParse; /* Parsing context */ - sqlite3 *db; /* The database connection */ int iLoop; /* Loop counter over the terms of the join */ int ii, jj; /* Loop counters */ int mxI = 0; /* Index of next entry to replace */ @@ -4698,7 +4977,6 @@ static int wherePathSolver(WhereInfo *pWInfo, LogEst nRowEst){ int nSpace; /* Bytes of space allocated at pSpace */ pParse = pWInfo->pParse; - db = pParse->db; nLoop = pWInfo->nLevel; /* TUNING: For simple queries, only the best path is tracked. ** For 2-way joins, the 5 best paths are followed. @@ -4721,7 +4999,7 @@ static int wherePathSolver(WhereInfo *pWInfo, LogEst nRowEst){ /* Allocate and initialize space for aTo, aFrom and aSortCost[] */ nSpace = (sizeof(WherePath)+sizeof(WhereLoop*)*nLoop)*mxChoice*2; nSpace += sizeof(LogEst) * nOrderBy; - pSpace = sqlite3DbMallocRawNN(db, nSpace); + pSpace = sqlite3StackAllocRawNN(pParse->db, nSpace); if( pSpace==0 ) return SQLITE_NOMEM_BKPT; aTo = (WherePath*)pSpace; aFrom = aTo+mxChoice; @@ -4771,9 +5049,9 @@ static int wherePathSolver(WhereInfo *pWInfo, LogEst nRowEst){ LogEst nOut; /* Rows visited by (pFrom+pWLoop) */ LogEst rCost; /* Cost of path (pFrom+pWLoop) */ LogEst rUnsorted; /* Unsorted cost of (pFrom+pWLoop) */ - i8 isOrdered = pFrom->isOrdered; /* isOrdered for (pFrom+pWLoop) */ + i8 isOrdered; /* isOrdered for (pFrom+pWLoop) */ Bitmask maskNew; /* Mask of src visited by (..) */ - Bitmask revMask = 0; /* Mask of rev-order loops for (..) */ + Bitmask revMask; /* Mask of rev-order loops for (..) */ if( (pWLoop->prereq & ~pFrom->maskLoop)!=0 ) continue; if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue; @@ -4792,7 +5070,9 @@ static int wherePathSolver(WhereInfo *pWInfo, LogEst nRowEst){ rUnsorted = sqlite3LogEstAdd(rUnsorted, pFrom->rUnsorted); nOut = pFrom->nRow + pWLoop->nOut; maskNew = pFrom->maskLoop | pWLoop->maskSelf; + isOrdered = pFrom->isOrdered; if( isOrdered<0 ){ + revMask = 0; isOrdered = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags, iLoop, pWLoop, &revMask); @@ -4805,11 +5085,11 @@ static int wherePathSolver(WhereInfo *pWInfo, LogEst nRowEst){ pWInfo, nRowEst, nOrderBy, isOrdered ); } - /* TUNING: Add a small extra penalty (5) to sorting as an + /* TUNING: Add a small extra penalty (3) to sorting as an ** extra encouragment to the query planner to select a plan ** where the rows emerge in the correct order without any sorting ** required. */ - rCost = sqlite3LogEstAdd(rUnsorted, aSortCost[isOrdered]) + 5; + rCost = sqlite3LogEstAdd(rUnsorted, aSortCost[isOrdered]) + 3; WHERETRACE(0x002, ("---- sort cost=%-3d (%d/%d) increases cost %3d to %-3d\n", @@ -4820,6 +5100,13 @@ static int wherePathSolver(WhereInfo *pWInfo, LogEst nRowEst){ rUnsorted -= 2; /* TUNING: Slight bias in favor of no-sort plans */ } + /* TUNING: A full-scan of a VIEW or subquery in the outer loop + ** is not so bad. */ + if( iLoop==0 && (pWLoop->wsFlags & WHERE_VIEWSCAN)!=0 ){ + rCost += -10; + nOut += -30; + } + /* Check to see if pWLoop should be added to the set of ** mxChoice best-so-far paths. ** @@ -4970,7 +5257,7 @@ static int wherePathSolver(WhereInfo *pWInfo, LogEst nRowEst){ if( nFrom==0 ){ sqlite3ErrorMsg(pParse, "no query solution"); - sqlite3DbFreeNN(db, pSpace); + sqlite3StackFreeNN(pParse->db, pSpace); return SQLITE_ERROR; } @@ -5006,6 +5293,10 @@ static int wherePathSolver(WhereInfo *pWInfo, LogEst nRowEst){ if( pFrom->isOrdered==pWInfo->pOrderBy->nExpr ){ pWInfo->eDistinct = WHERE_DISTINCT_ORDERED; } + if( pWInfo->pSelect->pOrderBy + && pWInfo->nOBSat > pWInfo->pSelect->pOrderBy->nExpr ){ + pWInfo->nOBSat = pWInfo->pSelect->pOrderBy->nExpr; + } }else{ pWInfo->revMask = pFrom->revLoop; if( pWInfo->nOBSat<=0 ){ @@ -5052,7 +5343,7 @@ static int wherePathSolver(WhereInfo *pWInfo, LogEst nRowEst){ pWInfo->nRowOut = pFrom->nRow; /* Free temporary memory and return success */ - sqlite3DbFreeNN(db, pSpace); + sqlite3StackFreeNN(pParse->db, pSpace); return SQLITE_OK; } @@ -5150,7 +5441,7 @@ static int whereShortCut(WhereLoopBuilder *pBuilder){ pLoop->cId = '0'; #endif #ifdef WHERETRACE_ENABLED - if( sqlite3WhereTrace ){ + if( sqlite3WhereTrace & 0x02 ){ sqlite3DebugPrintf("whereShortCut() used to compute solution\n"); } #endif @@ -5280,7 +5571,7 @@ static SQLITE_NOINLINE Bitmask whereOmitNoopJoin( } } if( pTerm<pEnd ) continue; - WHERETRACE(0xffff, ("-> drop loop %c not used\n", pLoop->cId)); + WHERETRACE(0xffffffff, ("-> drop loop %c not used\n", pLoop->cId)); notReady &= ~pLoop->maskSelf; for(pTerm=pWInfo->sWC.a; pTerm<pEnd; pTerm++){ if( (pTerm->prereqAll & pLoop->maskSelf)!=0 ){ @@ -5319,28 +5610,27 @@ static SQLITE_NOINLINE void whereCheckIfBloomFilterIsUseful( const WhereInfo *pWInfo ){ int i; - LogEst nSearch; + LogEst nSearch = 0; assert( pWInfo->nLevel>=2 ); assert( OptimizationEnabled(pWInfo->pParse->db, SQLITE_BloomFilter) ); - nSearch = pWInfo->a[0].pWLoop->nOut; - for(i=1; i<pWInfo->nLevel; i++){ + for(i=0; i<pWInfo->nLevel; i++){ WhereLoop *pLoop = pWInfo->a[i].pWLoop; const unsigned int reqFlags = (WHERE_SELFCULL|WHERE_COLUMN_EQ); - if( (pLoop->wsFlags & reqFlags)==reqFlags + SrcItem *pItem = &pWInfo->pTabList->a[pLoop->iTab]; + Table *pTab = pItem->pTab; + if( (pTab->tabFlags & TF_HasStat1)==0 ) break; + pTab->tabFlags |= TF_StatsUsed; + if( i>=1 + && (pLoop->wsFlags & reqFlags)==reqFlags /* vvvvvv--- Always the case if WHERE_COLUMN_EQ is defined */ && ALWAYS((pLoop->wsFlags & (WHERE_IPK|WHERE_INDEXED))!=0) ){ - SrcItem *pItem = &pWInfo->pTabList->a[pLoop->iTab]; - Table *pTab = pItem->pTab; - pTab->tabFlags |= TF_StatsUsed; - if( nSearch > pTab->nRowLogEst - && (pTab->tabFlags & TF_HasStat1)!=0 - ){ + if( nSearch > pTab->nRowLogEst ){ testcase( pItem->fg.jointype & JT_LEFT ); pLoop->wsFlags |= WHERE_BLOOMFILTER; pLoop->wsFlags &= ~WHERE_IDX_ONLY; - WHERETRACE(0xffff, ( + WHERETRACE(0xffffffff, ( "-> use Bloom-filter on loop %c because there are ~%.1e " "lookups into %s which has only ~%.1e rows\n", pLoop->cId, (double)sqlite3LogEstToInt(nSearch), pTab->zName, @@ -5352,6 +5642,86 @@ static SQLITE_NOINLINE void whereCheckIfBloomFilterIsUseful( } /* +** This is an sqlite3ParserAddCleanup() callback that is invoked to +** free the Parse->pIdxEpr list when the Parse object is destroyed. +*/ +static void whereIndexedExprCleanup(sqlite3 *db, void *pObject){ + Parse *pParse = (Parse*)pObject; + while( pParse->pIdxEpr!=0 ){ + IndexedExpr *p = pParse->pIdxEpr; + pParse->pIdxEpr = p->pIENext; + sqlite3ExprDelete(db, p->pExpr); + sqlite3DbFreeNN(db, p); + } +} + +/* +** The index pIdx is used by a query and contains one or more expressions. +** In other words pIdx is an index on an expression. iIdxCur is the cursor +** number for the index and iDataCur is the cursor number for the corresponding +** table. +** +** This routine adds IndexedExpr entries to the Parse->pIdxEpr field for +** each of the expressions in the index so that the expression code generator +** will know to replace occurrences of the indexed expression with +** references to the corresponding column of the index. +*/ +static SQLITE_NOINLINE void whereAddIndexedExpr( + Parse *pParse, /* Add IndexedExpr entries to pParse->pIdxEpr */ + Index *pIdx, /* The index-on-expression that contains the expressions */ + int iIdxCur, /* Cursor number for pIdx */ + SrcItem *pTabItem /* The FROM clause entry for the table */ +){ + int i; + IndexedExpr *p; + Table *pTab; + assert( pIdx->bHasExpr ); + pTab = pIdx->pTable; + for(i=0; i<pIdx->nColumn; i++){ + Expr *pExpr; + int j = pIdx->aiColumn[i]; + int bMaybeNullRow; + if( j==XN_EXPR ){ + pExpr = pIdx->aColExpr->a[i].pExpr; + testcase( pTabItem->fg.jointype & JT_LEFT ); + testcase( pTabItem->fg.jointype & JT_RIGHT ); + testcase( pTabItem->fg.jointype & JT_LTORJ ); + bMaybeNullRow = (pTabItem->fg.jointype & (JT_LEFT|JT_LTORJ|JT_RIGHT))!=0; + }else if( j>=0 && (pTab->aCol[j].colFlags & COLFLAG_VIRTUAL)!=0 ){ + pExpr = sqlite3ColumnExpr(pTab, &pTab->aCol[j]); + bMaybeNullRow = 0; + }else{ + continue; + } + if( sqlite3ExprIsConstant(pExpr) ) continue; + p = sqlite3DbMallocRaw(pParse->db, sizeof(IndexedExpr)); + if( p==0 ) break; + p->pIENext = pParse->pIdxEpr; +#ifdef WHERETRACE_ENABLED + if( sqlite3WhereTrace & 0x200 ){ + sqlite3DebugPrintf("New pParse->pIdxEpr term {%d,%d}\n", iIdxCur, i); + if( sqlite3WhereTrace & 0x5000 ) sqlite3ShowExpr(pExpr); + } +#endif + p->pExpr = sqlite3ExprDup(pParse->db, pExpr, 0); + p->iDataCur = pTabItem->iCursor; + p->iIdxCur = iIdxCur; + p->iIdxCol = i; + p->bMaybeNullRow = bMaybeNullRow; + if( sqlite3IndexAffinityStr(pParse->db, pIdx) ){ + p->aff = pIdx->zColAff[i]; + } +#ifdef SQLITE_ENABLE_EXPLAIN_COMMENTS + p->zIdxName = pIdx->zName; +#endif + pParse->pIdxEpr = p; + if( p->pIENext==0 ){ + sqlite3ParserAddCleanup(pParse, whereIndexedExprCleanup, pParse); + } + } +} + +/* ** Generate the beginning of the loop used for WHERE clause processing. ** The return value is a pointer to an opaque structure that contains ** information needed to terminate the loop. Later, the calling routine @@ -5445,7 +5815,7 @@ WhereInfo *sqlite3WhereBegin( Expr *pWhere, /* The WHERE clause */ ExprList *pOrderBy, /* An ORDER BY (or GROUP BY) clause, or NULL */ ExprList *pResultSet, /* Query result set. Req'd for DISTINCT */ - Select *pLimit, /* Use this LIMIT/OFFSET clause, if any */ + Select *pSelect, /* The entire SELECT statement */ u16 wctrlFlags, /* The WHERE_* flags defined in sqliteInt.h */ int iAuxArg /* If WHERE_OR_SUBCLAUSE is set, index cursor number ** If WHERE_USE_LIMIT, then the limit amount */ @@ -5514,7 +5884,9 @@ WhereInfo *sqlite3WhereBegin( pWInfo->pParse = pParse; pWInfo->pTabList = pTabList; pWInfo->pOrderBy = pOrderBy; +#if WHERETRACE_ENABLED pWInfo->pWhere = pWhere; +#endif pWInfo->pResultSet = pResultSet; pWInfo->aiCurOnePass[0] = pWInfo->aiCurOnePass[1] = -1; pWInfo->nLevel = nTabList; @@ -5522,9 +5894,7 @@ WhereInfo *sqlite3WhereBegin( pWInfo->wctrlFlags = wctrlFlags; pWInfo->iLimit = iAuxArg; pWInfo->savedNQueryLoop = pParse->nQueryLoop; -#ifndef SQLITE_OMIT_VIRTUALTABLE - pWInfo->pLimit = pLimit; -#endif + pWInfo->pSelect = pSelect; memset(&pWInfo->nOBSat, 0, offsetof(WhereInfo,sWC) - offsetof(WhereInfo,nOBSat)); memset(&pWInfo->a[0], 0, sizeof(WhereLoop)+nTabList*sizeof(WhereLevel)); @@ -5593,7 +5963,9 @@ WhereInfo *sqlite3WhereBegin( /* Analyze all of the subexpressions. */ sqlite3WhereExprAnalyze(pTabList, &pWInfo->sWC); - sqlite3WhereAddLimit(&pWInfo->sWC, pLimit); + if( pSelect && pSelect->pLimit ){ + sqlite3WhereAddLimit(&pWInfo->sWC, pSelect); + } if( pParse->nErr ) goto whereBeginError; /* Special case: WHERE terms that do not refer to any tables in the join @@ -5634,13 +6006,13 @@ WhereInfo *sqlite3WhereBegin( /* Construct the WhereLoop objects */ #if defined(WHERETRACE_ENABLED) - if( sqlite3WhereTrace & 0xffff ){ + if( sqlite3WhereTrace & 0xffffffff ){ sqlite3DebugPrintf("*** Optimizer Start *** (wctrlFlags: 0x%x",wctrlFlags); if( wctrlFlags & WHERE_USE_LIMIT ){ sqlite3DebugPrintf(", limit: %d", iAuxArg); } sqlite3DebugPrintf(")\n"); - if( sqlite3WhereTrace & 0x100 ){ + if( sqlite3WhereTrace & 0x8000 ){ Select sSelect; memset(&sSelect, 0, sizeof(sSelect)); sSelect.selFlags = SF_WhereBegin; @@ -5650,10 +6022,10 @@ WhereInfo *sqlite3WhereBegin( sSelect.pEList = pResultSet; sqlite3TreeViewSelect(0, &sSelect, 0); } - } - if( sqlite3WhereTrace & 0x100 ){ /* Display all terms of the WHERE clause */ - sqlite3DebugPrintf("---- WHERE clause at start of analysis:\n"); - sqlite3WhereClausePrint(sWLB.pWC); + if( sqlite3WhereTrace & 0x4000 ){ /* Display all WHERE clause terms */ + sqlite3DebugPrintf("---- WHERE clause at start of analysis:\n"); + sqlite3WhereClausePrint(sWLB.pWC); + } } #endif @@ -5669,7 +6041,7 @@ WhereInfo *sqlite3WhereBegin( ** loops will be built using the revised truthProb values. */ if( sWLB.bldFlags2 & SQLITE_BLDF2_2NDPASS ){ WHERETRACE_ALL_LOOPS(pWInfo, sWLB.pWC); - WHERETRACE(0xffff, + WHERETRACE(0xffffffff, ("**** Redo all loop computations due to" " TERM_HIGHTRUTH changes ****\n")); while( pWInfo->pLoops ){ @@ -5755,11 +6127,11 @@ WhereInfo *sqlite3WhereBegin( } #if defined(WHERETRACE_ENABLED) - if( sqlite3WhereTrace & 0x100 ){ /* Display all terms of the WHERE clause */ + if( sqlite3WhereTrace & 0x4000 ){ /* Display all terms of the WHERE clause */ sqlite3DebugPrintf("---- WHERE clause at end of analysis:\n"); sqlite3WhereClausePrint(sWLB.pWC); } - WHERETRACE(0xffff,("*** Optimizer Finished ***\n")); + WHERETRACE(0xffffffff,("*** Optimizer Finished ***\n")); #endif pWInfo->pParse->nQueryLoop += pWInfo->nRowOut; @@ -5896,6 +6268,9 @@ WhereInfo *sqlite3WhereBegin( op = OP_ReopenIdx; }else{ iIndexCur = pParse->nTab++; + if( pIx->bHasExpr && OptimizationEnabled(db, SQLITE_IndexedExpr) ){ + whereAddIndexedExpr(pParse, pIx, iIndexCur, pTabItem); + } } pLevel->iIdxCur = iIndexCur; assert( pIx!=0 ); @@ -6018,8 +6393,6 @@ WhereInfo *sqlite3WhereBegin( /* Jump here if malloc fails */ whereBeginError: if( pWInfo ){ - testcase( pWInfo->pExprMods!=0 ); - whereUndoExprMods(pWInfo); pParse->nQueryLoop = pWInfo->savedNQueryLoop; whereInfoFree(db, pWInfo); } @@ -6238,7 +6611,6 @@ void sqlite3WhereEnd(WhereInfo *pWInfo){ } assert( pWInfo->nLevel<=pTabList->nSrc ); - if( pWInfo->pExprMods ) whereUndoExprMods(pWInfo); for(i=0, pLevel=pWInfo->a; i<pWInfo->nLevel; i++, pLevel++){ int k, last; VdbeOp *pOp, *pLastOp; @@ -6292,6 +6664,23 @@ void sqlite3WhereEnd(WhereInfo *pWInfo){ }else{ last = pWInfo->iEndWhere; } + if( pIdx->bHasExpr ){ + IndexedExpr *p = pParse->pIdxEpr; + while( p ){ + if( p->iIdxCur==pLevel->iIdxCur ){ +#ifdef WHERETRACE_ENABLED + if( sqlite3WhereTrace & 0x200 ){ + sqlite3DebugPrintf("Disable pParse->pIdxEpr term {%d,%d}\n", + p->iIdxCur, p->iIdxCol); + if( sqlite3WhereTrace & 0x5000 ) sqlite3ShowExpr(p->pExpr); + } +#endif + p->iDataCur = -1; + p->iIdxCur = -1; + } + p = p->pIENext; + } + } k = pLevel->addrBody + 1; #ifdef SQLITE_DEBUG if( db->flags & SQLITE_VdbeAddopTrace ){ |