| /* |
| ** 2001 September 15 |
| ** |
| ** The author disclaims copyright to this source code. In place of |
| ** a legal notice, here is a blessing: |
| ** |
| ** May you do good and not evil. |
| ** May you find forgiveness for yourself and forgive others. |
| ** May you share freely, never taking more than you give. |
| ** |
| ************************************************************************* |
| ** This module contains C code that generates VDBE code used to process |
| ** the WHERE clause of SQL statements. This module is responsible for |
| ** generating the code that loops through a table looking for applicable |
| ** rows. Indices are selected and used to speed the search when doing |
| ** so is applicable. Because this module is responsible for selecting |
| ** indices, you might also think of this module as the "query optimizer". |
| */ |
| #include "sqliteInt.h" |
| #include "whereInt.h" |
| |
| /* |
| ** Extra information appended to the end of sqlite3_index_info but not |
| ** visible to the xBestIndex function, at least not directly. The |
| ** sqlite3_vtab_collation() interface knows how to reach it, however. |
| ** |
| ** This object is not an API and can be changed from one release to the |
| ** next. As long as allocateIndexInfo() and sqlite3_vtab_collation() |
| ** agree on the structure, all will be well. |
| */ |
| typedef struct HiddenIndexInfo HiddenIndexInfo; |
| struct HiddenIndexInfo { |
| WhereClause *pWC; /* The Where clause being analyzed */ |
| Parse *pParse; /* The parsing context */ |
| }; |
| |
| /* Forward declaration of methods */ |
| static int whereLoopResize(sqlite3*, WhereLoop*, int); |
| |
| /* Test variable that can be set to enable WHERE tracing */ |
| #if defined(SQLITE_TEST) || defined(SQLITE_DEBUG) |
| /***/ int sqlite3WhereTrace = 0; |
| #endif |
| |
| |
| /* |
| ** Return the estimated number of output rows from a WHERE clause |
| */ |
| LogEst sqlite3WhereOutputRowCount(WhereInfo *pWInfo){ |
| return pWInfo->nRowOut; |
| } |
| |
| /* |
| ** Return one of the WHERE_DISTINCT_xxxxx values to indicate how this |
| ** WHERE clause returns outputs for DISTINCT processing. |
| */ |
| int sqlite3WhereIsDistinct(WhereInfo *pWInfo){ |
| return pWInfo->eDistinct; |
| } |
| |
| /* |
| ** Return TRUE if the WHERE clause returns rows in ORDER BY order. |
| ** Return FALSE if the output needs to be sorted. |
| */ |
| int sqlite3WhereIsOrdered(WhereInfo *pWInfo){ |
| return pWInfo->nOBSat; |
| } |
| |
| /* |
| ** In the ORDER BY LIMIT optimization, if the inner-most loop is known |
| ** to emit rows in increasing order, and if the last row emitted by the |
| ** inner-most loop did not fit within the sorter, then we can skip all |
| ** subsequent rows for the current iteration of the inner loop (because they |
| ** will not fit in the sorter either) and continue with the second inner |
| ** loop - the loop immediately outside the inner-most. |
| ** |
| ** When a row does not fit in the sorter (because the sorter already |
| ** holds LIMIT+OFFSET rows that are smaller), then a jump is made to the |
| ** label returned by this function. |
| ** |
| ** If the ORDER BY LIMIT optimization applies, the jump destination should |
| ** be the continuation for the second-inner-most loop. If the ORDER BY |
| ** LIMIT optimization does not apply, then the jump destination should |
| ** be the continuation for the inner-most loop. |
| ** |
| ** It is always safe for this routine to return the continuation of the |
| ** inner-most loop, in the sense that a correct answer will result. |
| ** Returning the continuation the second inner loop is an optimization |
| ** that might make the code run a little faster, but should not change |
| ** the final answer. |
| */ |
| int sqlite3WhereOrderByLimitOptLabel(WhereInfo *pWInfo){ |
| WhereLevel *pInner; |
| if( !pWInfo->bOrderedInnerLoop ){ |
| /* The ORDER BY LIMIT optimization does not apply. Jump to the |
| ** continuation of the inner-most loop. */ |
| return pWInfo->iContinue; |
| } |
| pInner = &pWInfo->a[pWInfo->nLevel-1]; |
| assert( pInner->addrNxt!=0 ); |
| return pInner->addrNxt; |
| } |
| |
| /* |
| ** Return the VDBE address or label to jump to in order to continue |
| ** immediately with the next row of a WHERE clause. |
| */ |
| int sqlite3WhereContinueLabel(WhereInfo *pWInfo){ |
| assert( pWInfo->iContinue!=0 ); |
| return pWInfo->iContinue; |
| } |
| |
| /* |
| ** Return the VDBE address or label to jump to in order to break |
| ** out of a WHERE loop. |
| */ |
| int sqlite3WhereBreakLabel(WhereInfo *pWInfo){ |
| return pWInfo->iBreak; |
| } |
| |
| /* |
| ** Return ONEPASS_OFF (0) if an UPDATE or DELETE statement is unable to |
| ** operate directly on the rowis returned by a WHERE clause. Return |
| ** ONEPASS_SINGLE (1) if the statement can operation directly because only |
| ** a single row is to be changed. Return ONEPASS_MULTI (2) if the one-pass |
| ** optimization can be used on multiple |
| ** |
| ** If the ONEPASS optimization is used (if this routine returns true) |
| ** then also write the indices of open cursors used by ONEPASS |
| ** into aiCur[0] and aiCur[1]. iaCur[0] gets the cursor of the data |
| ** table and iaCur[1] gets the cursor used by an auxiliary index. |
| ** Either value may be -1, indicating that cursor is not used. |
| ** Any cursors returned will have been opened for writing. |
| ** |
| ** aiCur[0] and aiCur[1] both get -1 if the where-clause logic is |
| ** unable to use the ONEPASS optimization. |
| */ |
| int sqlite3WhereOkOnePass(WhereInfo *pWInfo, int *aiCur){ |
| memcpy(aiCur, pWInfo->aiCurOnePass, sizeof(int)*2); |
| #ifdef WHERETRACE_ENABLED |
| if( sqlite3WhereTrace && pWInfo->eOnePass!=ONEPASS_OFF ){ |
| sqlite3DebugPrintf("%s cursors: %d %d\n", |
| pWInfo->eOnePass==ONEPASS_SINGLE ? "ONEPASS_SINGLE" : "ONEPASS_MULTI", |
| aiCur[0], aiCur[1]); |
| } |
| #endif |
| return pWInfo->eOnePass; |
| } |
| |
| /* |
| ** 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 */ |
| LogEst rRun, /* Run-cost of the new entry */ |
| LogEst 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; |
| } |
| |
| /* |
| ** Return the bitmask for the given cursor number. Return 0 if |
| ** iCursor is not in the set. |
| */ |
| Bitmask sqlite3WhereGetMask(WhereMaskSet *pMaskSet, int iCursor){ |
| int i; |
| assert( pMaskSet->n<=(int)sizeof(Bitmask)*8 ); |
| for(i=0; i<pMaskSet->n; i++){ |
| if( pMaskSet->ix[i]==iCursor ){ |
| return MASKBIT(i); |
| } |
| } |
| return 0; |
| } |
| |
| /* |
| ** Create a new mask for cursor iCursor. |
| ** |
| ** There is one cursor per table in the FROM clause. The number of |
| ** tables in the FROM clause is limited by a test early in the |
| ** sqlite3WhereBegin() routine. So we know that the pMaskSet->ix[] |
| ** array will never overflow. |
| */ |
| static void createMask(WhereMaskSet *pMaskSet, int iCursor){ |
| assert( pMaskSet->n < ArraySize(pMaskSet->ix) ); |
| pMaskSet->ix[pMaskSet->n++] = iCursor; |
| } |
| |
| /* |
| ** Advance to the next WhereTerm that matches according to the criteria |
| ** established when the pScan object was initialized by whereScanInit(). |
| ** Return NULL if there are no more matching WhereTerms. |
| */ |
| static WhereTerm *whereScanNext(WhereScan *pScan){ |
| int iCur; /* The cursor on the LHS of the term */ |
| i16 iColumn; /* The column on the LHS of the term. -1 for IPK */ |
| Expr *pX; /* An expression being tested */ |
| WhereClause *pWC; /* Shorthand for pScan->pWC */ |
| WhereTerm *pTerm; /* The term being tested */ |
| int k = pScan->k; /* Where to start scanning */ |
| |
| assert( pScan->iEquiv<=pScan->nEquiv ); |
| pWC = pScan->pWC; |
| while(1){ |
| iColumn = pScan->aiColumn[pScan->iEquiv-1]; |
| iCur = pScan->aiCur[pScan->iEquiv-1]; |
| assert( pWC!=0 ); |
| do{ |
| for(pTerm=pWC->a+k; k<pWC->nTerm; k++, pTerm++){ |
| if( pTerm->leftCursor==iCur |
| && pTerm->u.leftColumn==iColumn |
| && (iColumn!=XN_EXPR |
| || sqlite3ExprCompareSkip(pTerm->pExpr->pLeft, |
| pScan->pIdxExpr,iCur)==0) |
| && (pScan->iEquiv<=1 || !ExprHasProperty(pTerm->pExpr, EP_FromJoin)) |
| ){ |
| if( (pTerm->eOperator & WO_EQUIV)!=0 |
| && pScan->nEquiv<ArraySize(pScan->aiCur) |
| && (pX = sqlite3ExprSkipCollate(pTerm->pExpr->pRight))->op==TK_COLUMN |
| ){ |
| int j; |
| for(j=0; j<pScan->nEquiv; j++){ |
| if( pScan->aiCur[j]==pX->iTable |
| && pScan->aiColumn[j]==pX->iColumn ){ |
| break; |
| } |
| } |
| if( j==pScan->nEquiv ){ |
| pScan->aiCur[j] = pX->iTable; |
| pScan->aiColumn[j] = pX->iColumn; |
| pScan->nEquiv++; |
| } |
| } |
| if( (pTerm->eOperator & pScan->opMask)!=0 ){ |
| /* Verify the affinity and collating sequence match */ |
| if( pScan->zCollName && (pTerm->eOperator & WO_ISNULL)==0 ){ |
| CollSeq *pColl; |
| Parse *pParse = pWC->pWInfo->pParse; |
| pX = pTerm->pExpr; |
| if( !sqlite3IndexAffinityOk(pX, pScan->idxaff) ){ |
| continue; |
| } |
| assert(pX->pLeft); |
| pColl = sqlite3BinaryCompareCollSeq(pParse, |
| pX->pLeft, pX->pRight); |
| if( pColl==0 ) pColl = pParse->db->pDfltColl; |
| if( sqlite3StrICmp(pColl->zName, pScan->zCollName) ){ |
| continue; |
| } |
| } |
| if( (pTerm->eOperator & (WO_EQ|WO_IS))!=0 |
| && (pX = pTerm->pExpr->pRight)->op==TK_COLUMN |
| && pX->iTable==pScan->aiCur[0] |
| && pX->iColumn==pScan->aiColumn[0] |
| ){ |
| testcase( pTerm->eOperator & WO_IS ); |
| continue; |
| } |
| pScan->pWC = pWC; |
| pScan->k = k+1; |
| return pTerm; |
| } |
| } |
| } |
| pWC = pWC->pOuter; |
| k = 0; |
| }while( pWC!=0 ); |
| if( pScan->iEquiv>=pScan->nEquiv ) break; |
| pWC = pScan->pOrigWC; |
| k = 0; |
| pScan->iEquiv++; |
| } |
| return 0; |
| } |
| |
| /* |
| ** This is whereScanInit() for the case of an index on an expression. |
| ** It is factored out into a separate tail-recursion subroutine so that |
| ** the normal whereScanInit() routine, which is a high-runner, does not |
| ** need to push registers onto the stack as part of its prologue. |
| */ |
| static SQLITE_NOINLINE WhereTerm *whereScanInitIndexExpr(WhereScan *pScan){ |
| pScan->idxaff = sqlite3ExprAffinity(pScan->pIdxExpr); |
| return whereScanNext(pScan); |
| } |
| |
| /* |
| ** Initialize a WHERE clause scanner object. Return a pointer to the |
| ** first match. Return NULL if there are no matches. |
| ** |
| ** The scanner will be searching the WHERE clause pWC. It will look |
| ** for terms of the form "X <op> <expr>" where X is column iColumn of table |
| ** iCur. Or if pIdx!=0 then X is column iColumn of index pIdx. pIdx |
| ** must be one of the indexes of table iCur. |
| ** |
| ** The <op> must be one of the operators described by opMask. |
| ** |
| ** If the search is for X and the WHERE clause contains terms of the |
| ** form X=Y then this routine might also return terms of the form |
| ** "Y <op> <expr>". The number of levels of transitivity is limited, |
| ** but is enough to handle most commonly occurring SQL statements. |
| ** |
| ** If X is not the INTEGER PRIMARY KEY then X must be compatible with |
| ** index pIdx. |
| */ |
| static WhereTerm *whereScanInit( |
| WhereScan *pScan, /* The WhereScan object being initialized */ |
| WhereClause *pWC, /* The WHERE clause to be scanned */ |
| int iCur, /* Cursor to scan for */ |
| int iColumn, /* Column to scan for */ |
| u32 opMask, /* Operator(s) to scan for */ |
| Index *pIdx /* Must be compatible with this index */ |
| ){ |
| pScan->pOrigWC = pWC; |
| pScan->pWC = pWC; |
| pScan->pIdxExpr = 0; |
| pScan->idxaff = 0; |
| pScan->zCollName = 0; |
| pScan->opMask = opMask; |
| pScan->k = 0; |
| pScan->aiCur[0] = iCur; |
| pScan->nEquiv = 1; |
| pScan->iEquiv = 1; |
| if( pIdx ){ |
| int j = iColumn; |
| iColumn = pIdx->aiColumn[j]; |
| if( iColumn==XN_EXPR ){ |
| pScan->pIdxExpr = pIdx->aColExpr->a[j].pExpr; |
| pScan->zCollName = pIdx->azColl[j]; |
| pScan->aiColumn[0] = XN_EXPR; |
| return whereScanInitIndexExpr(pScan); |
| }else if( iColumn==pIdx->pTable->iPKey ){ |
| iColumn = XN_ROWID; |
| }else if( iColumn>=0 ){ |
| pScan->idxaff = pIdx->pTable->aCol[iColumn].affinity; |
| pScan->zCollName = pIdx->azColl[j]; |
| } |
| }else if( iColumn==XN_EXPR ){ |
| return 0; |
| } |
| pScan->aiColumn[0] = iColumn; |
| return whereScanNext(pScan); |
| } |
| |
| /* |
| ** Search for a term in the WHERE clause that is of the form "X <op> <expr>" |
| ** where X is a reference to the iColumn of table iCur or of index pIdx |
| ** if pIdx!=0 and <op> is one of the WO_xx operator codes specified by |
| ** the op parameter. Return a pointer to the term. Return 0 if not found. |
| ** |
| ** If pIdx!=0 then it must be one of the indexes of table iCur. |
| ** Search for terms matching the iColumn-th column of pIdx |
| ** rather than the iColumn-th column of table iCur. |
| ** |
| ** The term returned might by Y=<expr> if there is another constraint in |
| ** the WHERE clause that specifies that X=Y. Any such constraints will be |
| ** identified by the WO_EQUIV bit in the pTerm->eOperator field. The |
| ** aiCur[]/iaColumn[] arrays hold X and all its equivalents. There are 11 |
| ** slots in aiCur[]/aiColumn[] so that means we can look for X plus up to 10 |
| ** other equivalent values. Hence a search for X will return <expr> if X=A1 |
| ** and A1=A2 and A2=A3 and ... and A9=A10 and A10=<expr>. |
| ** |
| ** If there are multiple terms in the WHERE clause of the form "X <op> <expr>" |
| ** then try for the one with no dependencies on <expr> - in other words where |
| ** <expr> is a constant expression of some kind. Only return entries of |
| ** the form "X <op> Y" where Y is a column in another table if no terms of |
| ** the form "X <op> <const-expr>" exist. If no terms with a constant RHS |
| ** exist, try to return a term that does not use WO_EQUIV. |
| */ |
| WhereTerm *sqlite3WhereFindTerm( |
| WhereClause *pWC, /* The WHERE clause to be searched */ |
| int iCur, /* Cursor number of LHS */ |
| int iColumn, /* Column number of LHS */ |
| Bitmask notReady, /* RHS must not overlap with this mask */ |
| u32 op, /* Mask of WO_xx values describing operator */ |
| Index *pIdx /* Must be compatible with this index, if not NULL */ |
| ){ |
| WhereTerm *pResult = 0; |
| WhereTerm *p; |
| WhereScan scan; |
| |
| p = whereScanInit(&scan, pWC, iCur, iColumn, op, pIdx); |
| op &= WO_EQ|WO_IS; |
| while( p ){ |
| if( (p->prereqRight & notReady)==0 ){ |
| if( p->prereqRight==0 && (p->eOperator&op)!=0 ){ |
| testcase( p->eOperator & WO_IS ); |
| return p; |
| } |
| if( pResult==0 ) pResult = p; |
| } |
| p = whereScanNext(&scan); |
| } |
| return pResult; |
| } |
| |
| /* |
| ** This function searches pList for an entry that matches the iCol-th column |
| ** of index pIdx. |
| ** |
| ** If such an expression is found, its index in pList->a[] is returned. If |
| ** no expression is found, -1 is returned. |
| */ |
| static int findIndexCol( |
| Parse *pParse, /* Parse context */ |
| ExprList *pList, /* Expression list to search */ |
| int iBase, /* Cursor for table associated with pIdx */ |
| Index *pIdx, /* Index to match column of */ |
| int iCol /* Column of index to match */ |
| ){ |
| int i; |
| const char *zColl = pIdx->azColl[iCol]; |
| |
| for(i=0; i<pList->nExpr; i++){ |
| Expr *p = sqlite3ExprSkipCollate(pList->a[i].pExpr); |
| if( p->op==TK_COLUMN |
| && p->iColumn==pIdx->aiColumn[iCol] |
| && p->iTable==iBase |
| ){ |
| CollSeq *pColl = sqlite3ExprNNCollSeq(pParse, pList->a[i].pExpr); |
| if( 0==sqlite3StrICmp(pColl->zName, zColl) ){ |
| return i; |
| } |
| } |
| } |
| |
| return -1; |
| } |
| |
| /* |
| ** Return TRUE if the iCol-th column of index pIdx is NOT NULL |
| */ |
| static int indexColumnNotNull(Index *pIdx, int iCol){ |
| int j; |
| assert( pIdx!=0 ); |
| assert( iCol>=0 && iCol<pIdx->nColumn ); |
| j = pIdx->aiColumn[iCol]; |
| if( j>=0 ){ |
| return pIdx->pTable->aCol[j].notNull; |
| }else if( j==(-1) ){ |
| return 1; |
| }else{ |
| assert( j==(-2) ); |
| return 0; /* Assume an indexed expression can always yield a NULL */ |
| |
| } |
| } |
| |
| /* |
| ** Return true if the DISTINCT expression-list passed as the third argument |
| ** is redundant. |
| ** |
| ** A DISTINCT list is redundant if any subset of the columns in the |
| ** DISTINCT list are collectively unique and individually non-null. |
| */ |
| static int isDistinctRedundant( |
| Parse *pParse, /* Parsing context */ |
| SrcList *pTabList, /* The FROM clause */ |
| WhereClause *pWC, /* The WHERE clause */ |
| ExprList *pDistinct /* The result set that needs to be DISTINCT */ |
| ){ |
| Table *pTab; |
| Index *pIdx; |
| int i; |
| int iBase; |
| |
| /* If there is more than one table or sub-select in the FROM clause of |
| ** this query, then it will not be possible to show that the DISTINCT |
| ** clause is redundant. */ |
| if( pTabList->nSrc!=1 ) return 0; |
| iBase = pTabList->a[0].iCursor; |
| pTab = pTabList->a[0].pTab; |
| |
| /* If any of the expressions is an IPK column on table iBase, then return |
| ** true. Note: The (p->iTable==iBase) part of this test may be false if the |
| ** current SELECT is a correlated sub-query. |
| */ |
| for(i=0; i<pDistinct->nExpr; i++){ |
| Expr *p = sqlite3ExprSkipCollate(pDistinct->a[i].pExpr); |
| if( p->op==TK_COLUMN && p->iTable==iBase && p->iColumn<0 ) return 1; |
| } |
| |
| /* Loop through all indices on the table, checking each to see if it makes |
| ** the DISTINCT qualifier redundant. It does so if: |
| ** |
| ** 1. The index is itself UNIQUE, and |
| ** |
| ** 2. All of the columns in the index are either part of the pDistinct |
| ** list, or else the WHERE clause contains a term of the form "col=X", |
| ** where X is a constant value. The collation sequences of the |
| ** comparison and select-list expressions must match those of the index. |
| ** |
| ** 3. All of those index columns for which the WHERE clause does not |
| ** contain a "col=X" term are subject to a NOT NULL constraint. |
| */ |
| for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){ |
| if( !IsUniqueIndex(pIdx) ) continue; |
| for(i=0; i<pIdx->nKeyCol; i++){ |
| if( 0==sqlite3WhereFindTerm(pWC, iBase, i, ~(Bitmask)0, WO_EQ, pIdx) ){ |
| if( findIndexCol(pParse, pDistinct, iBase, pIdx, i)<0 ) break; |
| if( indexColumnNotNull(pIdx, i)==0 ) break; |
| } |
| } |
| if( i==pIdx->nKeyCol ){ |
| /* This index implies that the DISTINCT qualifier is redundant. */ |
| return 1; |
| } |
| } |
| |
| return 0; |
| } |
| |
| |
| /* |
| ** Estimate the logarithm of the input value to base 2. |
| */ |
| static LogEst estLog(LogEst N){ |
| return N<=10 ? 0 : sqlite3LogEst(N) - 33; |
| } |
| |
| /* |
| ** Convert OP_Column opcodes to OP_Copy in previously generated code. |
| ** |
| ** This routine runs over generated VDBE code and translates OP_Column |
| ** opcodes into OP_Copy when the table is being accessed via co-routine |
| ** instead of via table lookup. |
| ** |
| ** If the bIncrRowid parameter is 0, then any OP_Rowid instructions on |
| ** cursor iTabCur are transformed into OP_Null. Or, if bIncrRowid is non-zero, |
| ** then each OP_Rowid is transformed into an instruction to increment the |
| ** value stored in its output register. |
| */ |
| static void translateColumnToCopy( |
| Parse *pParse, /* Parsing context */ |
| int iStart, /* Translate from this opcode to the end */ |
| int iTabCur, /* OP_Column/OP_Rowid references to this table */ |
| int iRegister, /* The first column is in this register */ |
| int bIncrRowid /* If non-zero, transform OP_rowid to OP_AddImm(1) */ |
| ){ |
| Vdbe *v = pParse->pVdbe; |
| VdbeOp *pOp = sqlite3VdbeGetOp(v, iStart); |
| int iEnd = sqlite3VdbeCurrentAddr(v); |
| if( pParse->db->mallocFailed ) return; |
| for(; iStart<iEnd; iStart++, pOp++){ |
| if( pOp->p1!=iTabCur ) continue; |
| if( pOp->opcode==OP_Column ){ |
| pOp->opcode = OP_Copy; |
| pOp->p1 = pOp->p2 + iRegister; |
| pOp->p2 = pOp->p3; |
| pOp->p3 = 0; |
| }else if( pOp->opcode==OP_Rowid ){ |
| if( bIncrRowid ){ |
| /* Increment the value stored in the P2 operand of the OP_Rowid. */ |
| pOp->opcode = OP_AddImm; |
| pOp->p1 = pOp->p2; |
| pOp->p2 = 1; |
| }else{ |
| pOp->opcode = OP_Null; |
| pOp->p1 = 0; |
| pOp->p3 = 0; |
| } |
| } |
| } |
| } |
| |
| /* |
| ** Two routines for printing the content of an sqlite3_index_info |
| ** structure. Used for testing and debugging only. If neither |
| ** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines |
| ** are no-ops. |
| */ |
| #if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(WHERETRACE_ENABLED) |
| static void TRACE_IDX_INPUTS(sqlite3_index_info *p){ |
| int i; |
| if( !sqlite3WhereTrace ) return; |
| for(i=0; i<p->nConstraint; i++){ |
| sqlite3DebugPrintf(" constraint[%d]: col=%d termid=%d op=%d usabled=%d\n", |
| i, |
| p->aConstraint[i].iColumn, |
| p->aConstraint[i].iTermOffset, |
| p->aConstraint[i].op, |
| p->aConstraint[i].usable); |
| } |
| for(i=0; i<p->nOrderBy; i++){ |
| sqlite3DebugPrintf(" orderby[%d]: col=%d desc=%d\n", |
| i, |
| p->aOrderBy[i].iColumn, |
| p->aOrderBy[i].desc); |
| } |
| } |
| static void TRACE_IDX_OUTPUTS(sqlite3_index_info *p){ |
| int i; |
| if( !sqlite3WhereTrace ) return; |
| for(i=0; i<p->nConstraint; i++){ |
| sqlite3DebugPrintf(" usage[%d]: argvIdx=%d omit=%d\n", |
| i, |
| p->aConstraintUsage[i].argvIndex, |
| p->aConstraintUsage[i].omit); |
| } |
| sqlite3DebugPrintf(" idxNum=%d\n", p->idxNum); |
| sqlite3DebugPrintf(" idxStr=%s\n", p->idxStr); |
| sqlite3DebugPrintf(" orderByConsumed=%d\n", p->orderByConsumed); |
| sqlite3DebugPrintf(" estimatedCost=%g\n", p->estimatedCost); |
| sqlite3DebugPrintf(" estimatedRows=%lld\n", p->estimatedRows); |
| } |
| #else |
| #define TRACE_IDX_INPUTS(A) |
| #define TRACE_IDX_OUTPUTS(A) |
| #endif |
| |
| #ifndef SQLITE_OMIT_AUTOMATIC_INDEX |
| /* |
| ** Return TRUE if the WHERE clause term pTerm is of a form where it |
| ** could be used with an index to access pSrc, assuming an appropriate |
| ** index existed. |
| */ |
| static int termCanDriveIndex( |
| WhereTerm *pTerm, /* WHERE clause term to check */ |
| struct SrcList_item *pSrc, /* Table we are trying to access */ |
| Bitmask notReady /* Tables in outer loops of the join */ |
| ){ |
| char aff; |
| if( pTerm->leftCursor!=pSrc->iCursor ) return 0; |
| if( (pTerm->eOperator & (WO_EQ|WO_IS))==0 ) return 0; |
| if( (pSrc->fg.jointype & JT_LEFT) |
| && !ExprHasProperty(pTerm->pExpr, EP_FromJoin) |
| && (pTerm->eOperator & WO_IS) |
| ){ |
| /* Cannot use an IS term from the WHERE clause as an index driver for |
| ** the RHS of a LEFT JOIN. Such a term can only be used if it is from |
| ** the ON clause. */ |
| return 0; |
| } |
| if( (pTerm->prereqRight & notReady)!=0 ) return 0; |
| if( pTerm->u.leftColumn<0 ) return 0; |
| aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity; |
| if( !sqlite3IndexAffinityOk(pTerm->pExpr, aff) ) return 0; |
| testcase( pTerm->pExpr->op==TK_IS ); |
| return 1; |
| } |
| #endif |
| |
| |
| #ifndef SQLITE_OMIT_AUTOMATIC_INDEX |
| /* |
| ** Generate code to construct the Index object for an automatic index |
| ** and to set up the WhereLevel object pLevel so that the code generator |
| ** makes use of the automatic index. |
| */ |
| static void constructAutomaticIndex( |
| Parse *pParse, /* The parsing context */ |
| WhereClause *pWC, /* The WHERE clause */ |
| struct SrcList_item *pSrc, /* The FROM clause term to get the next index */ |
| Bitmask notReady, /* Mask of cursors that are not available */ |
| WhereLevel *pLevel /* Write new index here */ |
| ){ |
| int nKeyCol; /* Number of columns in the constructed index */ |
| WhereTerm *pTerm; /* A single term of the WHERE clause */ |
| WhereTerm *pWCEnd; /* End of pWC->a[] */ |
| Index *pIdx; /* Object describing the transient index */ |
| Vdbe *v; /* Prepared statement under construction */ |
| int addrInit; /* Address of the initialization bypass jump */ |
| Table *pTable; /* The table being indexed */ |
| int addrTop; /* Top of the index fill loop */ |
| int regRecord; /* Register holding an index record */ |
| int n; /* Column counter */ |
| int i; /* Loop counter */ |
| int mxBitCol; /* Maximum column in pSrc->colUsed */ |
| CollSeq *pColl; /* Collating sequence to on a column */ |
| WhereLoop *pLoop; /* The Loop object */ |
| char *zNotUsed; /* Extra space on the end of pIdx */ |
| Bitmask idxCols; /* Bitmap of columns used for indexing */ |
| Bitmask extraCols; /* Bitmap of additional columns */ |
| u8 sentWarning = 0; /* True if a warnning has been issued */ |
| Expr *pPartial = 0; /* Partial Index Expression */ |
| int iContinue = 0; /* Jump here to skip excluded rows */ |
| struct SrcList_item *pTabItem; /* FROM clause term being indexed */ |
| int addrCounter = 0; /* Address where integer counter is initialized */ |
| int regBase; /* Array of registers where record is assembled */ |
| |
| /* Generate code to skip over the creation and initialization of the |
| ** transient index on 2nd and subsequent iterations of the loop. */ |
| v = pParse->pVdbe; |
| assert( v!=0 ); |
| addrInit = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v); |
| |
| /* Count the number of columns that will be added to the index |
| ** and used to match WHERE clause constraints */ |
| nKeyCol = 0; |
| pTable = pSrc->pTab; |
| pWCEnd = &pWC->a[pWC->nTerm]; |
| pLoop = pLevel->pWLoop; |
| idxCols = 0; |
| for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){ |
| Expr *pExpr = pTerm->pExpr; |
| assert( !ExprHasProperty(pExpr, EP_FromJoin) /* prereq always non-zero */ |
| || pExpr->iRightJoinTable!=pSrc->iCursor /* for the right-hand */ |
| || pLoop->prereq!=0 ); /* table of a LEFT JOIN */ |
| if( pLoop->prereq==0 |
| && (pTerm->wtFlags & TERM_VIRTUAL)==0 |
| && !ExprHasProperty(pExpr, EP_FromJoin) |
| && sqlite3ExprIsTableConstant(pExpr, pSrc->iCursor) ){ |
| pPartial = sqlite3ExprAnd(pParse->db, pPartial, |
| sqlite3ExprDup(pParse->db, pExpr, 0)); |
| } |
| if( termCanDriveIndex(pTerm, pSrc, notReady) ){ |
| int iCol = pTerm->u.leftColumn; |
| Bitmask cMask = iCol>=BMS ? MASKBIT(BMS-1) : MASKBIT(iCol); |
| testcase( iCol==BMS ); |
| testcase( iCol==BMS-1 ); |
| if( !sentWarning ){ |
| sqlite3_log(SQLITE_WARNING_AUTOINDEX, |
| "automatic index on %s(%s)", pTable->zName, |
| pTable->aCol[iCol].zName); |
| sentWarning = 1; |
| } |
| if( (idxCols & cMask)==0 ){ |
| if( whereLoopResize(pParse->db, pLoop, nKeyCol+1) ){ |
| goto end_auto_index_create; |
| } |
| pLoop->aLTerm[nKeyCol++] = pTerm; |
| idxCols |= cMask; |
| } |
| } |
| } |
| assert( nKeyCol>0 ); |
| pLoop->u.btree.nEq = pLoop->nLTerm = nKeyCol; |
| pLoop->wsFlags = WHERE_COLUMN_EQ | WHERE_IDX_ONLY | WHERE_INDEXED |
| | WHERE_AUTO_INDEX; |
| |
| /* Count the number of additional columns needed to create a |
| ** covering index. A "covering index" is an index that contains all |
| ** columns that are needed by the query. With a covering index, the |
| ** original table never needs to be accessed. Automatic indices must |
| ** be a covering index because the index will not be updated if the |
| ** original table changes and the index and table cannot both be used |
| ** if they go out of sync. |
| */ |
| extraCols = pSrc->colUsed & (~idxCols | MASKBIT(BMS-1)); |
| mxBitCol = MIN(BMS-1,pTable->nCol); |
| testcase( pTable->nCol==BMS-1 ); |
| testcase( pTable->nCol==BMS-2 ); |
| for(i=0; i<mxBitCol; i++){ |
| if( extraCols & MASKBIT(i) ) nKeyCol++; |
| } |
| if( pSrc->colUsed & MASKBIT(BMS-1) ){ |
| nKeyCol += pTable->nCol - BMS + 1; |
| } |
| |
| /* Construct the Index object to describe this index */ |
| pIdx = sqlite3AllocateIndexObject(pParse->db, nKeyCol+1, 0, &zNotUsed); |
| if( pIdx==0 ) goto end_auto_index_create; |
| pLoop->u.btree.pIndex = pIdx; |
| pIdx->zName = "auto-index"; |
| pIdx->pTable = pTable; |
| n = 0; |
| idxCols = 0; |
| for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){ |
| if( termCanDriveIndex(pTerm, pSrc, notReady) ){ |
| int iCol = pTerm->u.leftColumn; |
| Bitmask cMask = iCol>=BMS ? MASKBIT(BMS-1) : MASKBIT(iCol); |
| testcase( iCol==BMS-1 ); |
| testcase( iCol==BMS ); |
| if( (idxCols & cMask)==0 ){ |
| Expr *pX = pTerm->pExpr; |
| idxCols |= cMask; |
| pIdx->aiColumn[n] = pTerm->u.leftColumn; |
| pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight); |
| pIdx->azColl[n] = pColl ? pColl->zName : sqlite3StrBINARY; |
| n++; |
| } |
| } |
| } |
| assert( (u32)n==pLoop->u.btree.nEq ); |
| |
| /* Add additional columns needed to make the automatic index into |
| ** a covering index */ |
| for(i=0; i<mxBitCol; i++){ |
| if( extraCols & MASKBIT(i) ){ |
| pIdx->aiColumn[n] = i; |
| pIdx->azColl[n] = sqlite3StrBINARY; |
| n++; |
| } |
| } |
| if( pSrc->colUsed & MASKBIT(BMS-1) ){ |
| for(i=BMS-1; i<pTable->nCol; i++){ |
| pIdx->aiColumn[n] = i; |
| pIdx->azColl[n] = sqlite3StrBINARY; |
| n++; |
| } |
| } |
| assert( n==nKeyCol ); |
| pIdx->aiColumn[n] = XN_ROWID; |
| pIdx->azColl[n] = sqlite3StrBINARY; |
| |
| /* Create the automatic index */ |
| assert( pLevel->iIdxCur>=0 ); |
| pLevel->iIdxCur = pParse->nTab++; |
| sqlite3VdbeAddOp2(v, OP_OpenAutoindex, pLevel->iIdxCur, nKeyCol+1); |
| sqlite3VdbeSetP4KeyInfo(pParse, pIdx); |
| VdbeComment((v, "for %s", pTable->zName)); |
| |
| /* Fill the automatic index with content */ |
| pTabItem = &pWC->pWInfo->pTabList->a[pLevel->iFrom]; |
| if( pTabItem->fg.viaCoroutine ){ |
| int regYield = pTabItem->regReturn; |
| addrCounter = sqlite3VdbeAddOp2(v, OP_Integer, 0, 0); |
| sqlite3VdbeAddOp3(v, OP_InitCoroutine, regYield, 0, pTabItem->addrFillSub); |
| addrTop = sqlite3VdbeAddOp1(v, OP_Yield, regYield); |
| VdbeCoverage(v); |
| VdbeComment((v, "next row of %s", pTabItem->pTab->zName)); |
| }else{ |
| addrTop = sqlite3VdbeAddOp1(v, OP_Rewind, pLevel->iTabCur); VdbeCoverage(v); |
| } |
| if( pPartial ){ |
| iContinue = sqlite3VdbeMakeLabel(pParse); |
| sqlite3ExprIfFalse(pParse, pPartial, iContinue, SQLITE_JUMPIFNULL); |
| pLoop->wsFlags |= WHERE_PARTIALIDX; |
| } |
| regRecord = sqlite3GetTempReg(pParse); |
| regBase = sqlite3GenerateIndexKey( |
| pParse, pIdx, pLevel->iTabCur, regRecord, 0, 0, 0, 0 |
| ); |
| sqlite3VdbeAddOp2(v, OP_IdxInsert, pLevel->iIdxCur, regRecord); |
| sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT); |
| if( pPartial ) sqlite3VdbeResolveLabel(v, iContinue); |
| if( pTabItem->fg.viaCoroutine ){ |
| sqlite3VdbeChangeP2(v, addrCounter, regBase+n); |
| testcase( pParse->db->mallocFailed ); |
| translateColumnToCopy(pParse, addrTop, pLevel->iTabCur, |
| pTabItem->regResult, 1); |
| sqlite3VdbeGoto(v, addrTop); |
| pTabItem->fg.viaCoroutine = 0; |
| }else{ |
| sqlite3VdbeAddOp2(v, OP_Next, pLevel->iTabCur, addrTop+1); VdbeCoverage(v); |
| } |
| sqlite3VdbeChangeP5(v, SQLITE_STMTSTATUS_AUTOINDEX); |
| sqlite3VdbeJumpHere(v, addrTop); |
| sqlite3ReleaseTempReg(pParse, regRecord); |
| |
| /* Jump here when skipping the initialization */ |
| sqlite3VdbeJumpHere(v, addrInit); |
| |
| end_auto_index_create: |
| sqlite3ExprDelete(pParse->db, pPartial); |
| } |
| #endif /* SQLITE_OMIT_AUTOMATIC_INDEX */ |
| |
| #ifndef SQLITE_OMIT_VIRTUALTABLE |
| /* |
| ** Allocate and populate an sqlite3_index_info structure. It is the |
| ** responsibility of the caller to eventually release the structure |
| ** by passing the pointer returned by this function to sqlite3_free(). |
| */ |
| static sqlite3_index_info *allocateIndexInfo( |
| Parse *pParse, /* The parsing context */ |
| WhereClause *pWC, /* The WHERE clause being analyzed */ |
| Bitmask mUnusable, /* Ignore terms with these prereqs */ |
| struct SrcList_item *pSrc, /* The FROM clause term that is the vtab */ |
| ExprList *pOrderBy, /* The ORDER BY clause */ |
| u16 *pmNoOmit /* Mask of terms not to omit */ |
| ){ |
| int i, j; |
| int nTerm; |
| struct sqlite3_index_constraint *pIdxCons; |
| struct sqlite3_index_orderby *pIdxOrderBy; |
| struct sqlite3_index_constraint_usage *pUsage; |
| struct HiddenIndexInfo *pHidden; |
| WhereTerm *pTerm; |
| int nOrderBy; |
| sqlite3_index_info *pIdxInfo; |
| u16 mNoOmit = 0; |
| |
| /* Count the number of possible WHERE clause constraints referring |
| ** to this virtual table */ |
| for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){ |
| if( pTerm->leftCursor != pSrc->iCursor ) continue; |
| if( pTerm->prereqRight & mUnusable ) continue; |
| assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) ); |
| testcase( pTerm->eOperator & WO_IN ); |
| testcase( pTerm->eOperator & WO_ISNULL ); |
| testcase( pTerm->eOperator & WO_IS ); |
| testcase( pTerm->eOperator & WO_ALL ); |
| if( (pTerm->eOperator & ~(WO_EQUIV))==0 ) continue; |
| if( pTerm->wtFlags & TERM_VNULL ) continue; |
| assert( pTerm->u.leftColumn>=(-1) ); |
| nTerm++; |
| } |
| |
| /* If the ORDER BY clause contains only columns in the current |
| ** virtual table then allocate space for the aOrderBy part of |
| ** the sqlite3_index_info structure. |
| */ |
| nOrderBy = 0; |
| if( pOrderBy ){ |
| int n = pOrderBy->nExpr; |
| for(i=0; i<n; i++){ |
| Expr *pExpr = pOrderBy->a[i].pExpr; |
| if( pExpr->op!=TK_COLUMN || pExpr->iTable!=pSrc->iCursor ) break; |
| } |
| if( i==n){ |
| nOrderBy = n; |
| } |
| } |
| |
| /* Allocate the sqlite3_index_info structure |
| */ |
| pIdxInfo = sqlite3DbMallocZero(pParse->db, sizeof(*pIdxInfo) |
| + (sizeof(*pIdxCons) + sizeof(*pUsage))*nTerm |
| + sizeof(*pIdxOrderBy)*nOrderBy + sizeof(*pHidden) ); |
| if( pIdxInfo==0 ){ |
| sqlite3ErrorMsg(pParse, "out of memory"); |
| return 0; |
| } |
| |
| /* Initialize the structure. The sqlite3_index_info structure contains |
| ** many fields that are declared "const" to prevent xBestIndex from |
| ** changing them. We have to do some funky casting in order to |
| ** initialize those fields. |
| */ |
| pHidden = (struct HiddenIndexInfo*)&pIdxInfo[1]; |
| pIdxCons = (struct sqlite3_index_constraint*)&pHidden[1]; |
| pIdxOrderBy = (struct sqlite3_index_orderby*)&pIdxCons[nTerm]; |
| pUsage = (struct sqlite3_index_constraint_usage*)&pIdxOrderBy[nOrderBy]; |
| *(int*)&pIdxInfo->nConstraint = nTerm; |
| *(int*)&pIdxInfo->nOrderBy = nOrderBy; |
| *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint = pIdxCons; |
| *(struct sqlite3_index_orderby**)&pIdxInfo->aOrderBy = pIdxOrderBy; |
| *(struct sqlite3_index_constraint_usage**)&pIdxInfo->aConstraintUsage = |
| pUsage; |
| |
| pHidden->pWC = pWC; |
| pHidden->pParse = pParse; |
| for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){ |
| u16 op; |
| if( pTerm->leftCursor != pSrc->iCursor ) continue; |
| if( pTerm->prereqRight & mUnusable ) continue; |
| assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) ); |
| testcase( pTerm->eOperator & WO_IN ); |
| testcase( pTerm->eOperator & WO_IS ); |
| testcase( pTerm->eOperator & WO_ISNULL ); |
| testcase( pTerm->eOperator & WO_ALL ); |
| if( (pTerm->eOperator & ~(WO_EQUIV))==0 ) continue; |
| if( pTerm->wtFlags & TERM_VNULL ) continue; |
| if( (pSrc->fg.jointype & JT_LEFT)!=0 |
| && !ExprHasProperty(pTerm->pExpr, EP_FromJoin) |
| && (pTerm->eOperator & (WO_IS|WO_ISNULL)) |
| ){ |
| /* An "IS" term in the WHERE clause where the virtual table is the rhs |
| ** of a LEFT JOIN. Do not pass this term to the virtual table |
| ** implementation, as this can lead to incorrect results from SQL such |
| ** as: |
| ** |
| ** "LEFT JOIN vtab WHERE vtab.col IS NULL" */ |
| testcase( pTerm->eOperator & WO_ISNULL ); |
| testcase( pTerm->eOperator & WO_IS ); |
| continue; |
| } |
| assert( pTerm->u.leftColumn>=(-1) ); |
| pIdxCons[j].iColumn = pTerm->u.leftColumn; |
| pIdxCons[j].iTermOffset = i; |
| op = pTerm->eOperator & WO_ALL; |
| if( op==WO_IN ) op = WO_EQ; |
| if( op==WO_AUX ){ |
| pIdxCons[j].op = pTerm->eMatchOp; |
| }else if( op & (WO_ISNULL|WO_IS) ){ |
| if( op==WO_ISNULL ){ |
| pIdxCons[j].op = SQLITE_INDEX_CONSTRAINT_ISNULL; |
| }else{ |
| pIdxCons[j].op = SQLITE_INDEX_CONSTRAINT_IS; |
| } |
| }else{ |
| pIdxCons[j].op = (u8)op; |
| /* The direct assignment in the previous line is possible only because |
| ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical. The |
| ** following asserts verify this fact. */ |
| assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ ); |
| assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT ); |
| assert( WO_LE==SQLITE_INDEX_CONSTRAINT_LE ); |
| assert( WO_GT==SQLITE_INDEX_CONSTRAINT_GT ); |
| assert( WO_GE==SQLITE_INDEX_CONSTRAINT_GE ); |
| assert( pTerm->eOperator&(WO_IN|WO_EQ|WO_LT|WO_LE|WO_GT|WO_GE|WO_AUX) ); |
| |
| if( op & (WO_LT|WO_LE|WO_GT|WO_GE) |
| && sqlite3ExprIsVector(pTerm->pExpr->pRight) |
| ){ |
| if( i<16 ) mNoOmit |= (1 << i); |
| if( op==WO_LT ) pIdxCons[j].op = WO_LE; |
| if( op==WO_GT ) pIdxCons[j].op = WO_GE; |
| } |
| } |
| |
| j++; |
| } |
| for(i=0; i<nOrderBy; i++){ |
| Expr *pExpr = pOrderBy->a[i].pExpr; |
| pIdxOrderBy[i].iColumn = pExpr->iColumn; |
| pIdxOrderBy[i].desc = pOrderBy->a[i].sortOrder; |
| } |
| |
| *pmNoOmit = mNoOmit; |
| return pIdxInfo; |
| } |
| |
| /* |
| ** The table object reference passed as the second argument to this function |
| ** must represent a virtual table. This function invokes the xBestIndex() |
| ** method of the virtual table with the sqlite3_index_info object that |
| ** comes in as the 3rd argument to this function. |
| ** |
| ** If an error occurs, pParse is populated with an error message and an |
| ** appropriate error code is returned. A return of SQLITE_CONSTRAINT from |
| ** xBestIndex is not considered an error. SQLITE_CONSTRAINT indicates that |
| ** the current configuration of "unusable" flags in sqlite3_index_info can |
| ** not result in a valid plan. |
| ** |
| ** Whether or not an error is returned, it is the responsibility of the |
| ** caller to eventually free p->idxStr if p->needToFreeIdxStr indicates |
| ** that this is required. |
| */ |
| static int vtabBestIndex(Parse *pParse, Table *pTab, sqlite3_index_info *p){ |
| sqlite3_vtab *pVtab = sqlite3GetVTable(pParse->db, pTab)->pVtab; |
| int rc; |
| |
| TRACE_IDX_INPUTS(p); |
| rc = pVtab->pModule->xBestIndex(pVtab, p); |
| TRACE_IDX_OUTPUTS(p); |
| |
| if( rc!=SQLITE_OK && rc!=SQLITE_CONSTRAINT ){ |
| if( rc==SQLITE_NOMEM ){ |
| sqlite3OomFault(pParse->db); |
| }else if( !pVtab->zErrMsg ){ |
| sqlite3ErrorMsg(pParse, "%s", sqlite3ErrStr(rc)); |
| }else{ |
| sqlite3ErrorMsg(pParse, "%s", pVtab->zErrMsg); |
| } |
| } |
| sqlite3_free(pVtab->zErrMsg); |
| pVtab->zErrMsg = 0; |
| return rc; |
| } |
| #endif /* !defined(SQLITE_OMIT_VIRTUALTABLE) */ |
| |
| #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 |
| /* |
| ** Estimate the location of a particular key among all keys in an |
| ** index. Store the results in aStat as follows: |
| ** |
| ** aStat[0] Est. number of rows less than pRec |
| ** aStat[1] Est. number of rows equal to pRec |
| ** |
| ** Return the index of the sample that is the smallest sample that |
| ** is greater than or equal to pRec. Note that this index is not an index |
| ** into the aSample[] array - it is an index into a virtual set of samples |
| ** based on the contents of aSample[] and the number of fields in record |
| ** pRec. |
| */ |
| static int whereKeyStats( |
| Parse *pParse, /* Database connection */ |
| Index *pIdx, /* Index to consider domain of */ |
| UnpackedRecord *pRec, /* Vector of values to consider */ |
| int roundUp, /* Round up if true. Round down if false */ |
| tRowcnt *aStat /* OUT: stats written here */ |
| ){ |
| IndexSample *aSample = pIdx->aSample; |
| int iCol; /* Index of required stats in anEq[] etc. */ |
| int i; /* Index of first sample >= pRec */ |
| int iSample; /* Smallest sample larger than or equal to pRec */ |
| int iMin = 0; /* Smallest sample not yet tested */ |
| int iTest; /* Next sample to test */ |
| int res; /* Result of comparison operation */ |
| int nField; /* Number of fields in pRec */ |
| tRowcnt iLower = 0; /* anLt[] + anEq[] of largest sample pRec is > */ |
| |
| #ifndef SQLITE_DEBUG |
| UNUSED_PARAMETER( pParse ); |
| #endif |
| assert( pRec!=0 ); |
| assert( pIdx->nSample>0 ); |
| assert( pRec->nField>0 && pRec->nField<=pIdx->nSampleCol ); |
| |
| /* 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 |
| ** is simply the aSample[] array. If the samples in aSample[] contain more |
| ** than one fields, all fields following the first are ignored. |
| ** |
| ** If pRec contains N fields, where N is more than one, then as well as the |
| ** samples in aSample[] (truncated to N fields), the search also has to |
| ** consider prefixes of those samples. For example, if the set of samples |
| ** in aSample is: |
| ** |
| ** aSample[0] = (a, 5) |
| ** aSample[1] = (a, 10) |
| ** aSample[2] = (b, 5) |
| ** aSample[3] = (c, 100) |
| ** aSample[4] = (c, 105) |
| ** |
| ** Then the search space should ideally be the samples above and the |
| ** unique prefixes [a], [b] and [c]. But since that is hard to organize, |
| ** the code actually searches this set: |
| ** |
| ** 0: (a) |
| ** 1: (a, 5) |
| ** 2: (a, 10) |
| ** 3: (a, 10) |
| ** 4: (b) |
| ** 5: (b, 5) |
| ** 6: (c) |
| ** 7: (c, 100) |
| ** 8: (c, 105) |
| ** 9: (c, 105) |
| ** |
| ** For each sample in the aSample[] array, N samples are present in the |
| ** effective sample array. In the above, samples 0 and 1 are based on |
| ** sample aSample[0]. Samples 2 and 3 on aSample[1] etc. |
| ** |
| ** Often, sample i of each block of N effective samples has (i+1) fields. |
| ** Except, each sample may be extended to ensure that it is greater than or |
| ** equal to the previous sample in the array. For example, in the above, |
| ** sample 2 is the first sample of a block of N samples, so at first it |
| ** appears that it should be 1 field in size. However, that would make it |
| ** smaller than sample 1, so the binary search would not work. As a result, |
| ** it is extended to two fields. The duplicates that this creates do not |
| ** cause any problems. |
| */ |
| nField = pRec->nField; |
| iCol = 0; |
| iSample = pIdx->nSample * nField; |
| do{ |
| int iSamp; /* Index in aSample[] of test sample */ |
| int n; /* Number of fields in test sample */ |
| |
| iTest = (iMin+iSample)/2; |
| iSamp = iTest / nField; |
| if( iSamp>0 ){ |
| /* The proposed effective sample is a prefix of sample aSample[iSamp]. |
| ** Specifically, the shortest prefix of at least (1 + iTest%nField) |
| ** fields that is greater than the previous effective sample. */ |
| for(n=(iTest % nField) + 1; n<nField; n++){ |
| if( aSample[iSamp-1].anLt[n-1]!=aSample[iSamp].anLt[n-1] ) break; |
| } |
| }else{ |
| n = iTest + 1; |
| } |
| |
| pRec->nField = n; |
| res = sqlite3VdbeRecordCompare(aSample[iSamp].n, aSample[iSamp].p, pRec); |
| if( res<0 ){ |
| iLower = aSample[iSamp].anLt[n-1] + aSample[iSamp].anEq[n-1]; |
| iMin = iTest+1; |
| }else if( res==0 && n<nField ){ |
| iLower = aSample[iSamp].anLt[n-1]; |
| iMin = iTest+1; |
| res = -1; |
| }else{ |
| iSample = iTest; |
| iCol = n-1; |
| } |
| }while( res && iMin<iSample ); |
| i = iSample / nField; |
| |
| #ifdef SQLITE_DEBUG |
| /* The following assert statements check that the binary search code |
| ** above found the right answer. This block serves no purpose other |
| ** than to invoke the asserts. */ |
| if( pParse->db->mallocFailed==0 ){ |
| if( res==0 ){ |
| /* If (res==0) is true, then pRec must be equal to sample i. */ |
| assert( i<pIdx->nSample ); |
| assert( iCol==nField-1 ); |
| pRec->nField = nField; |
| assert( 0==sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, pRec) |
| || pParse->db->mallocFailed |
| ); |
| }else{ |
| /* Unless i==pIdx->nSample, indicating that pRec is larger than |
| ** all samples in the aSample[] array, pRec must be smaller than the |
| ** (iCol+1) field prefix of sample i. */ |
| assert( i<=pIdx->nSample && i>=0 ); |
| pRec->nField = iCol+1; |
| assert( i==pIdx->nSample |
| || sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, pRec)>0 |
| || pParse->db->mallocFailed ); |
| |
| /* if i==0 and iCol==0, then record pRec is smaller than all samples |
| ** in the aSample[] array. Otherwise, if (iCol>0) then pRec must |
| ** be greater than or equal to the (iCol) field prefix of sample i. |
| ** If (i>0), then pRec must also be greater than sample (i-1). */ |
| if( iCol>0 ){ |
| pRec->nField = iCol; |
| assert( sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, pRec)<=0 |
| || pParse->db->mallocFailed ); |
| } |
| if( i>0 ){ |
| pRec->nField = nField; |
| assert( sqlite3VdbeRecordCompare(aSample[i-1].n, aSample[i-1].p, pRec)<0 |
| || pParse->db->mallocFailed ); |
| } |
| } |
| } |
| #endif /* ifdef SQLITE_DEBUG */ |
| |
| if( res==0 ){ |
| /* Record pRec is equal to sample i */ |
| assert( iCol==nField-1 ); |
| aStat[0] = aSample[i].anLt[iCol]; |
| aStat[1] = aSample[i].anEq[iCol]; |
| }else{ |
| /* At this point, the (iCol+1) field prefix of aSample[i] is the first |
| ** sample that is greater than pRec. Or, if i==pIdx->nSample then pRec |
| ** is larger than all samples in the array. */ |
| tRowcnt iUpper, iGap; |
| if( i>=pIdx->nSample ){ |
| iUpper = sqlite3LogEstToInt(pIdx->aiRowLogEst[0]); |
| }else{ |
| iUpper = aSample[i].anLt[iCol]; |
| } |
| |
| if( iLower>=iUpper ){ |
| iGap = 0; |
| }else{ |
| iGap = iUpper - iLower; |
| } |
| if( roundUp ){ |
| iGap = (iGap*2)/3; |
| }else{ |
| iGap = iGap/3; |
| } |
| aStat[0] = iLower + iGap; |
| aStat[1] = pIdx->aAvgEq[nField-1]; |
| } |
| |
| /* Restore the pRec->nField value before returning. */ |
| pRec->nField = nField; |
| return i; |
| } |
| #endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */ |
| |
| /* |
| ** If it is not NULL, pTerm is a term that provides an upper or lower |
| ** bound on a range scan. Without considering pTerm, it is estimated |
| ** that the scan will visit nNew rows. This function returns the number |
| ** estimated to be visited after taking pTerm into account. |
| ** |
| ** If the user explicitly specified a likelihood() value for this term, |
| ** then the return value is the likelihood multiplied by the number of |
| ** input rows. Otherwise, this function assumes that an "IS NOT NULL" term |
| ** has a likelihood of 0.50, and any other term a likelihood of 0.25. |
| */ |
| static LogEst whereRangeAdjust(WhereTerm *pTerm, LogEst nNew){ |
| LogEst nRet = nNew; |
| if( pTerm ){ |
| if( pTerm->truthProb<=0 ){ |
| nRet += pTerm->truthProb; |
| }else if( (pTerm->wtFlags & TERM_VNULL)==0 ){ |
| nRet -= 20; assert( 20==sqlite3LogEst(4) ); |
| } |
| } |
| return nRet; |
| } |
| |
| |
| #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 |
| /* |
| ** Return the affinity for a single column of an index. |
| */ |
| char sqlite3IndexColumnAffinity(sqlite3 *db, Index *pIdx, int iCol){ |
| assert( iCol>=0 && iCol<pIdx->nColumn ); |
| if( !pIdx->zColAff ){ |
| if( sqlite3IndexAffinityStr(db, pIdx)==0 ) return SQLITE_AFF_BLOB; |
| } |
| return pIdx->zColAff[iCol]; |
| } |
| #endif |
| |
| |
| #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 |
| /* |
| ** This function is called to estimate the number of rows visited by a |
| ** range-scan on a skip-scan index. For example: |
| ** |
| ** CREATE INDEX i1 ON t1(a, b, c); |
| ** SELECT * FROM t1 WHERE a=? AND c BETWEEN ? AND ?; |
| ** |
| ** Value pLoop->nOut is currently set to the estimated number of rows |
| ** visited for scanning (a=? AND b=?). This function reduces that estimate |
| ** by some factor to account for the (c BETWEEN ? AND ?) expression based |
| ** on the stat4 data for the index. this scan will be peformed multiple |
| ** times (once for each (a,b) combination that matches a=?) is dealt with |
| ** by the caller. |
| ** |
| ** It does this by scanning through all stat4 samples, comparing values |
| ** extracted from pLower and pUpper with the corresponding column in each |
| ** sample. If L and U are the number of samples found to be less than or |
| ** equal to the values extracted from pLower and pUpper respectively, and |
| ** N is the total number of samples, the pLoop->nOut value is adjusted |
| ** as follows: |
| ** |
| ** nOut = nOut * ( min(U - L, 1) / N ) |
| ** |
| ** If pLower is NULL, or a value cannot be extracted from the term, L is |
| ** set to zero. If pUpper is NULL, or a value cannot be extracted from it, |
| ** U is set to N. |
| ** |
| ** Normally, this function sets *pbDone to 1 before returning. However, |
| ** if no value can be extracted from either pLower or pUpper (and so the |
| ** estimate of the number of rows delivered remains unchanged), *pbDone |
| ** is left as is. |
| ** |
| ** If an error occurs, an SQLite error code is returned. Otherwise, |
| ** SQLITE_OK. |
| */ |
| static int whereRangeSkipScanEst( |
| Parse *pParse, /* Parsing & code generating context */ |
| WhereTerm *pLower, /* Lower bound on the range. ex: "x>123" Might be NULL */ |
| WhereTerm *pUpper, /* Upper bound on the range. ex: "x<455" Might be NULL */ |
| WhereLoop *pLoop, /* Update the .nOut value of this loop */ |
| int *pbDone /* Set to true if at least one expr. value extracted */ |
| ){ |
| Index *p = pLoop->u.btree.pIndex; |
| int nEq = pLoop->u.btree.nEq; |
| sqlite3 *db = pParse->db; |
| int nLower = -1; |
| int nUpper = p->nSample+1; |
| int rc = SQLITE_OK; |
| u8 aff = sqlite3IndexColumnAffinity(db, p, nEq); |
| CollSeq *pColl; |
| |
| sqlite3_value *p1 = 0; /* Value extracted from pLower */ |
| sqlite3_value *p2 = 0; /* Value extracted from pUpper */ |
| sqlite3_value *pVal = 0; /* Value extracted from record */ |
| |
| pColl = sqlite3LocateCollSeq(pParse, p->azColl[nEq]); |
| if( pLower ){ |
| rc = sqlite3Stat4ValueFromExpr(pParse, pLower->pExpr->pRight, aff, &p1); |
| nLower = 0; |
| } |
| if( pUpper && rc==SQLITE_OK ){ |
| rc = sqlite3Stat4ValueFromExpr(pParse, pUpper->pExpr->pRight, aff, &p2); |
| nUpper = p2 ? 0 : p->nSample; |
| } |
| |
| if( p1 || p2 ){ |
| int i; |
| int nDiff; |
| for(i=0; rc==SQLITE_OK && i<p->nSample; i++){ |
| rc = sqlite3Stat4Column(db, p->aSample[i].p, p->aSample[i].n, nEq, &pVal); |
| if( rc==SQLITE_OK && p1 ){ |
| int res = sqlite3MemCompare(p1, pVal, pColl); |
| if( res>=0 ) nLower++; |
| } |
| if( rc==SQLITE_OK && p2 ){ |
| int res = sqlite3MemCompare(p2, pVal, pColl); |
| if( res>=0 ) nUpper++; |
| } |
| } |
| nDiff = (nUpper - nLower); |
| if( nDiff<=0 ) nDiff = 1; |
| |
| /* If there is both an upper and lower bound specified, and the |
| ** comparisons indicate that they are close together, use the fallback |
| ** method (assume that the scan visits 1/64 of the rows) for estimating |
| ** the number of rows visited. Otherwise, estimate the number of rows |
| ** using the method described in the header comment for this function. */ |
| if( nDiff!=1 || pUpper==0 || pLower==0 ){ |
| 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", |
| nLower, nUpper, nAdjust*-1, pLoop->nOut)); |
| } |
| |
| }else{ |
| assert( *pbDone==0 ); |
| } |
| |
| sqlite3ValueFree(p1); |
| sqlite3ValueFree(p2); |
| sqlite3ValueFree(pVal); |
| |
| return rc; |
| } |
| #endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */ |
| |
| /* |
| ** This function is used to estimate the number of rows that will be visited |
| ** by scanning an index for a range of values. The range may have an upper |
| ** bound, a lower bound, or both. The WHERE clause terms that set the upper |
| ** and lower bounds are represented by pLower and pUpper respectively. For |
| ** example, assuming that index p is on t1(a): |
| ** |
| ** ... FROM t1 WHERE a > ? AND a < ? ... |
| ** |_____| |_____| |
| ** | | |
| ** pLower pUpper |
| ** |
| ** If either of the upper or lower bound is not present, then NULL is passed in |
| ** place of the corresponding WhereTerm. |
| ** |
| ** The value in (pBuilder->pNew->u.btree.nEq) is the number of the index |
| ** column subject to the range constraint. Or, equivalently, the number of |
| ** equality constraints optimized by the proposed index scan. For example, |
| ** assuming index p is on t1(a, b), and the SQL query is: |
| ** |
| ** ... FROM t1 WHERE a = ? AND b > ? AND b < ? ... |
| ** |
| ** then nEq is set to 1 (as the range restricted column, b, is the second |
| ** left-most column of the index). Or, if the query is: |
| ** |
| ** ... FROM t1 WHERE a > ? AND a < ? ... |
| ** |
| ** then nEq is set to 0. |
| ** |
| ** When this function is called, *pnOut is set to the sqlite3LogEst() of the |
| ** number of rows that the index scan is expected to visit without |
| ** considering the range constraints. If nEq is 0, then *pnOut is the number of |
| ** rows in the index. Assuming no error occurs, *pnOut is adjusted (reduced) |
| ** to account for the range constraints pLower and pUpper. |
| ** |
| ** In the absence of sqlite_stat4 ANALYZE data, or if such data cannot be |
| ** used, a single range inequality reduces the search space by a factor of 4. |
| ** and a pair of constraints (x>? AND x<?) reduces the expected number of |
| ** rows visited by a factor of 64. |
| */ |
| static int whereRangeScanEst( |
| Parse *pParse, /* Parsing & code generating context */ |
| WhereLoopBuilder *pBuilder, |
| WhereTerm *pLower, /* Lower bound on the range. ex: "x>123" Might be NULL */ |
| WhereTerm *pUpper, /* Upper bound on the range. ex: "x<455" Might be NULL */ |
| WhereLoop *pLoop /* Modify the .nOut and maybe .rRun fields */ |
| ){ |
| int rc = SQLITE_OK; |
| int nOut = pLoop->nOut; |
| LogEst nNew; |
| |
| #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 |
| Index *p = pLoop->u.btree.pIndex; |
| int nEq = pLoop->u.btree.nEq; |
| |
| if( p->nSample>0 && nEq<p->nSampleCol |
| && OptimizationEnabled(pParse->db, SQLITE_Stat34) |
| ){ |
| if( nEq==pBuilder->nRecValid ){ |
| UnpackedRecord *pRec = pBuilder->pRec; |
| tRowcnt a[2]; |
| int nBtm = pLoop->u.btree.nBtm; |
| int nTop = pLoop->u.btree.nTop; |
| |
| /* Variable iLower will be set to the estimate of the number of rows in |
| ** the index that are less than the lower bound of the range query. The |
| ** lower bound being the concatenation of $P and $L, where $P is the |
| ** key-prefix formed by the nEq values matched against the nEq left-most |
| ** columns of the index, and $L is the value in pLower. |
| ** |
| ** Or, if pLower is NULL or $L cannot be extracted from it (because it |
| ** is not a simple variable or literal value), the lower bound of the |
| ** range is $P. Due to a quirk in the way whereKeyStats() works, even |
| ** if $L is available, whereKeyStats() is called for both ($P) and |
| ** ($P:$L) and the larger of the two returned values is used. |
| ** |
| ** Similarly, iUpper is to be set to the estimate of the number of rows |
| ** less than the upper bound of the range query. Where the upper bound |
| ** is either ($P) or ($P:$U). Again, even if $U is available, both values |
| ** of iUpper are requested of whereKeyStats() and the smaller used. |
| ** |
| ** The number of rows between the two bounds is then just iUpper-iLower. |
| */ |
| tRowcnt iLower; /* Rows less than the lower bound */ |
| tRowcnt iUpper; /* Rows less than the upper bound */ |
| int iLwrIdx = -2; /* aSample[] for the lower bound */ |
| int iUprIdx = -1; /* aSample[] for the upper bound */ |
| |
| if( pRec ){ |
| testcase( pRec->nField!=pBuilder->nRecValid ); |
| pRec->nField = pBuilder->nRecValid; |
| } |
| /* Determine iLower and iUpper using ($P) only. */ |
| if( nEq==0 ){ |
| iLower = 0; |
| iUpper = p->nRowEst0; |
| }else{ |
| /* Note: this call could be optimized away - since the same values must |
| ** have been requested when testing key $P in whereEqualScanEst(). */ |
| whereKeyStats(pParse, p, pRec, 0, a); |
| iLower = a[0]; |
| iUpper = a[0] + a[1]; |
| } |
| |
| assert( pLower==0 || (pLower->eOperator & (WO_GT|WO_GE))!=0 ); |
| assert( pUpper==0 || (pUpper->eOperator & (WO_LT|WO_LE))!=0 ); |
| assert( p->aSortOrder!=0 ); |
| if( p->aSortOrder[nEq] ){ |
| /* The roles of pLower and pUpper are swapped for a DESC index */ |
| SWAP(WhereTerm*, pLower, pUpper); |
| SWAP(int, nBtm, nTop); |
| } |
| |
| /* If possible, improve on the iLower estimate using ($P:$L). */ |
| if( pLower ){ |
| int n; /* Values extracted from pExpr */ |
| Expr *pExpr = pLower->pExpr->pRight; |
| rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, nBtm, nEq, &n); |
| if( rc==SQLITE_OK && n ){ |
| tRowcnt iNew; |
| u16 mask = WO_GT|WO_LE; |
| if( sqlite3ExprVectorSize(pExpr)>n ) mask = (WO_LE|WO_LT); |
| iLwrIdx = whereKeyStats(pParse, p, pRec, 0, a); |
| iNew = a[0] + ((pLower->eOperator & mask) ? a[1] : 0); |
| if( iNew>iLower ) iLower = iNew; |
| nOut--; |
| pLower = 0; |
| } |
| } |
| |
| /* If possible, improve on the iUpper estimate using ($P:$U). */ |
| if( pUpper ){ |
| int n; /* Values extracted from pExpr */ |
| Expr *pExpr = pUpper->pExpr->pRight; |
| rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, nTop, nEq, &n); |
| if( rc==SQLITE_OK && n ){ |
| tRowcnt iNew; |
| u16 mask = WO_GT|WO_LE; |
| if( sqlite3ExprVectorSize(pExpr)>n ) mask = (WO_LE|WO_LT); |
| iUprIdx = whereKeyStats(pParse, p, pRec, 1, a); |
| iNew = a[0] + ((pUpper->eOperator & mask) ? a[1] : 0); |
| if( iNew<iUpper ) iUpper = iNew; |
| nOut--; |
| pUpper = 0; |
| } |
| } |
| |
| pBuilder->pRec = pRec; |
| if( rc==SQLITE_OK ){ |
| if( iUpper>iLower ){ |
| nNew = sqlite3LogEst(iUpper - iLower); |
| /* TUNING: If both iUpper and iLower are derived from the same |
| ** sample, then assume they are 4x more selective. This brings |
| ** the estimated selectivity more in line with what it would be |
| ** if estimated without the use of STAT3/4 tables. */ |
| if( iLwrIdx==iUprIdx ) nNew -= 20; assert( 20==sqlite3LogEst(4) ); |
| }else{ |
| nNew = 10; assert( 10==sqlite3LogEst(2) ); |
| } |
| if( nNew<nOut ){ |
| nOut = nNew; |
| } |
| WHERETRACE(0x10, ("STAT4 range scan: %u..%u est=%d\n", |
| (u32)iLower, (u32)iUpper, nOut)); |
| } |
| }else{ |
| int bDone = 0; |
| rc = whereRangeSkipScanEst(pParse, pLower, pUpper, pLoop, &bDone); |
| if( bDone ) return rc; |
| } |
| } |
| #else |
| UNUSED_PARAMETER(pParse); |
| UNUSED_PARAMETER(pBuilder); |
| assert( pLower || pUpper ); |
| #endif |
| assert( pUpper==0 || (pUpper->wtFlags & TERM_VNULL)==0 ); |
| nNew = whereRangeAdjust(pLower, nOut); |
| nNew = whereRangeAdjust(pUpper, nNew); |
| |
| /* TUNING: If there is both an upper and lower limit and neither limit |
| ** has an application-defined likelihood(), assume the range is |
| ** reduced by an additional 75%. This means that, by default, an open-ended |
| ** range query (e.g. col > ?) is assumed to match 1/4 of the rows in the |
| ** index. While a closed range (e.g. col BETWEEN ? AND ?) is estimated to |
| ** match 1/64 of the index. */ |
| if( pLower && pLower->truthProb>0 && pUpper && pUpper->truthProb>0 ){ |
| nNew -= 20; |
| } |
| |
| nOut -= (pLower!=0) + (pUpper!=0); |
| if( nNew<10 ) nNew = 10; |
| if( nNew<nOut ) nOut = nNew; |
| #if defined(WHERETRACE_ENABLED) |
| if( pLoop->nOut>nOut ){ |
| WHERETRACE(0x10,("Range scan lowers nOut from %d to %d\n", |
| pLoop->nOut, nOut)); |
| } |
| #endif |
| pLoop->nOut = (LogEst)nOut; |
| return rc; |
| } |
| |
| #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 |
| /* |
| ** Estimate the number of rows that will be returned based on |
| ** an equality constraint x=VALUE and where that VALUE occurs in |
| ** the histogram data. This only works when x is the left-most |
| ** column of an index and sqlite_stat3 histogram data is available |
| ** for that index. When pExpr==NULL that means the constraint is |
| ** "x IS NULL" instead of "x=VALUE". |
| ** |
| ** Write the estimated row count into *pnRow and return SQLITE_OK. |
| ** If unable to make an estimate, leave *pnRow unchanged and return |
| ** non-zero. |
| ** |
| ** This routine can fail if it is unable to load a collating sequence |
| ** required for string comparison, or if unable to allocate memory |
| ** for a UTF conversion required for comparison. The error is stored |
| ** in the pParse structure. |
| */ |
| static int whereEqualScanEst( |
| Parse *pParse, /* Parsing & code generating context */ |
| WhereLoopBuilder *pBuilder, |
| Expr *pExpr, /* Expression for VALUE in the x=VALUE constraint */ |
| tRowcnt *pnRow /* Write the revised row estimate here */ |
| ){ |
| Index *p = pBuilder->pNew->u.btree.pIndex; |
| int nEq = pBuilder->pNew->u.btree.nEq; |
| UnpackedRecord *pRec = pBuilder->pRec; |
| int rc; /* Subfunction return code */ |
| tRowcnt a[2]; /* Statistics */ |
| int bOk; |
| |
| assert( nEq>=1 ); |
| assert( nEq<=p->nColumn ); |
| assert( p->aSample!=0 ); |
| assert( p->nSample>0 ); |
| assert( pBuilder->nRecValid<nEq ); |
| |
| /* If values are not available for all fields of the index to the left |
| ** of this one, no estimate can be made. Return SQLITE_NOTFOUND. */ |
| if( pBuilder->nRecValid<(nEq-1) ){ |
| return SQLITE_NOTFOUND; |
| } |
| |
| /* This is an optimization only. The call to sqlite3Stat4ProbeSetValue() |
| ** below would return the same value. */ |
| if( nEq>=p->nColumn ){ |
| *pnRow = 1; |
| return SQLITE_OK; |
| } |
| |
| rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, 1, nEq-1, &bOk); |
| pBuilder->pRec = pRec; |
| if( rc!=SQLITE_OK ) return rc; |
| if( bOk==0 ) return SQLITE_NOTFOUND; |
| pBuilder->nRecValid = nEq; |
| |
| whereKeyStats(pParse, p, pRec, 0, a); |
| WHERETRACE(0x10,("equality scan regions %s(%d): %d\n", |
| p->zName, nEq-1, (int)a[1])); |
| *pnRow = a[1]; |
| |
| return rc; |
| } |
| #endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */ |
| |
| #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 |
| /* |
| ** Estimate the number of rows that will be returned based on |
| ** an IN constraint where the right-hand side of the IN operator |
| ** is a list of values. Example: |
| ** |
| ** WHERE x IN (1,2,3,4) |
| ** |
| ** Write the estimated row count into *pnRow and return SQLITE_OK. |
| ** If unable to make an estimate, leave *pnRow unchanged and return |
| ** non-zero. |
| ** |
| ** This routine can fail if it is unable to load a collating sequence |
| ** required for string comparison, or if unable to allocate memory |
| ** for a UTF conversion required for comparison. The error is stored |
| ** in the pParse structure. |
| */ |
| static int whereInScanEst( |
| Parse *pParse, /* Parsing & code generating context */ |
| WhereLoopBuilder *pBuilder, |
| ExprList *pList, /* The value list on the RHS of "x IN (v1,v2,v3,...)" */ |
| tRowcnt *pnRow /* Write the revised row estimate here */ |
| ){ |
| Index *p = pBuilder->pNew->u.btree.pIndex; |
| i64 nRow0 = sqlite3LogEstToInt(p->aiRowLogEst[0]); |
| int nRecValid = pBuilder->nRecValid; |
| int rc = SQLITE_OK; /* Subfunction return code */ |
| tRowcnt nEst; /* Number of rows for a single term */ |
| tRowcnt nRowEst = 0; /* New estimate of the number of rows */ |
| int i; /* Loop counter */ |
| |
| assert( p->aSample!=0 ); |
| for(i=0; rc==SQLITE_OK && i<pList->nExpr; i++){ |
| nEst = nRow0; |
| rc = whereEqualScanEst(pParse, pBuilder, pList->a[i].pExpr, &nEst); |
| nRowEst += nEst; |
| pBuilder->nRecValid = nRecValid; |
| } |
| |
| if( rc==SQLITE_OK ){ |
| if( nRowEst > nRow0 ) nRowEst = nRow0; |
| *pnRow = nRowEst; |
| WHERETRACE(0x10,("IN row estimate: est=%d\n", nRowEst)); |
| } |
| assert( pBuilder->nRecValid==nRecValid ); |
| return rc; |
| } |
| #endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */ |
| |
| |
| #ifdef WHERETRACE_ENABLED |
| /* |
| ** Print the content of a WhereTerm object |
| */ |
| static void whereTermPrint(WhereTerm *pTerm, int iTerm){ |
| if( pTerm==0 ){ |
| sqlite3DebugPrintf("TERM-%-3d NULL\n", iTerm); |
| }else{ |
| char zType[4]; |
| char zLeft[50]; |
| memcpy(zType, "...", 4); |
| if( pTerm->wtFlags & TERM_VIRTUAL ) zType[0] = 'V'; |
| if( pTerm->eOperator & WO_EQUIV ) zType[1] = 'E'; |
| if( ExprHasProperty(pTerm->pExpr, EP_FromJoin) ) zType[2] = 'L'; |
| if( pTerm->eOperator & WO_SINGLE ){ |
| sqlite3_snprintf(sizeof(zLeft),zLeft,"left={%d:%d}", |
| pTerm->leftCursor, pTerm->u.leftColumn); |
| }else if( (pTerm->eOperator & WO_OR)!=0 && pTerm->u.pOrInfo!=0 ){ |
| sqlite3_snprintf(sizeof(zLeft),zLeft,"indexable=0x%lld", |
| pTerm->u.pOrInfo->indexable); |
| }else{ |
| sqlite3_snprintf(sizeof(zLeft),zLeft,"left=%d", pTerm->leftCursor); |
| } |
| sqlite3DebugPrintf( |
| "TERM-%-3d %p %s %-12s prob=%-3d op=0x%03x wtFlags=0x%04x", |
| iTerm, pTerm, zType, zLeft, pTerm->truthProb, |
| pTerm->eOperator, pTerm->wtFlags); |
| if( pTerm->iField ){ |
| sqlite3DebugPrintf(" iField=%d\n", pTerm->iField); |
| }else{ |
| sqlite3DebugPrintf("\n"); |
| } |
| sqlite3TreeViewExpr(0, pTerm->pExpr, 0); |
| } |
| } |
| #endif |
| |
| #ifdef WHERETRACE_ENABLED |
| /* |
| ** Show the complete content of a WhereClause |
| */ |
| void sqlite3WhereClausePrint(WhereClause *pWC){ |
| int i; |
| for(i=0; i<pWC->nTerm; i++){ |
| whereTermPrint(&pWC->a[i], i); |
| } |
| } |
| #endif |
| |
| #ifdef WHERETRACE_ENABLED |
| /* |
| ** Print a WhereLoop object for debugging purposes |
| */ |
| static void whereLoopPrint(WhereLoop *p, WhereClause *pWC){ |
| WhereInfo *pWInfo = pWC->pWInfo; |
| int nb = 1+(pWInfo->pTabList->nSrc+3)/4; |
| struct SrcList_item *pItem = pWInfo->pTabList->a + p->iTab; |
| Table *pTab = pItem->pTab; |
| Bitmask mAll = (((Bitmask)1)<<(nb*4)) - 1; |
| sqlite3DebugPrintf("%c%2d.%0*llx.%0*llx", p->cId, |
| p->iTab, nb, p->maskSelf, nb, p->prereq & mAll); |
| sqlite3DebugPrintf(" %12s", |
| pItem->zAlias ? pItem->zAlias : pTab->zName); |
| if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){ |
| const char *zName; |
| if( p->u.btree.pIndex && (zName = p->u.btree.pIndex->zName)!=0 ){ |
| if( strncmp(zName, "sqlite_autoindex_", 17)==0 ){ |
| int i = sqlite3Strlen30(zName) - 1; |
| while( zName[i]!='_' ) i--; |
| zName += i; |
| } |
| sqlite3DebugPrintf(".%-16s %2d", zName, p->u.btree.nEq); |
| }else{ |
| sqlite3DebugPrintf("%20s",""); |
| } |
| }else{ |
| char *z; |
| if( p->u.vtab.idxStr ){ |
| z = sqlite3_mprintf("(%d,\"%s\",%x)", |
| p->u.vtab.idxNum, p->u.vtab.idxStr, p->u.vtab.omitMask); |
| }else{ |
| z = sqlite3_mprintf("(%d,%x)", p->u.vtab.idxNum, p->u.vtab.omitMask); |
| } |
| sqlite3DebugPrintf(" %-19s", z); |
| sqlite3_free(z); |
| } |
| if( p->wsFlags & WHERE_SKIPSCAN ){ |
| sqlite3DebugPrintf(" f %05x %d-%d", p->wsFlags, p->nLTerm,p->nSkip); |
| }else{ |
| sqlite3DebugPrintf(" f %05x N %d", p->wsFlags, p->nLTerm); |
| } |
| sqlite3DebugPrintf(" cost %d,%d,%d\n", p->rSetup, p->rRun, p->nOut); |
| if( p->nLTerm && (sqlite3WhereTrace & 0x100)!=0 ){ |
| int i; |
| for(i=0; i<p->nLTerm; i++){ |
| whereTermPrint(p->aLTerm[i], i); |
| } |
| } |
| } |
| #endif |
| |
| /* |
| ** Convert bulk memory into a valid WhereLoop that can be passed |
| ** to whereLoopClear harmlessly. |
| */ |
| static void whereLoopInit(WhereLoop *p){ |
| p->aLTerm = p->aLTermSpace; |
| p->nLTerm = 0; |
| p->nLSlot = ArraySize(p->aLTermSpace); |
| p->wsFlags = 0; |
| } |
| |
| /* |
| ** Clear the WhereLoop.u union. Leave WhereLoop.pLTerm intact. |
| */ |
| static void whereLoopClearUnion(sqlite3 *db, WhereLoop *p){ |
| if( p->wsFlags & (WHERE_VIRTUALTABLE|WHERE_AUTO_INDEX) ){ |
| if( (p->wsFlags & WHERE_VIRTUALTABLE)!=0 && p->u.vtab.needFree ){ |
| sqlite3_free(p->u.vtab.idxStr); |
| p->u.vtab.needFree = 0; |
| p->u.vtab.idxStr = 0; |
| }else if( (p->wsFlags & WHERE_AUTO_INDEX)!=0 && p->u.btree.pIndex!=0 ){ |
| sqlite3DbFree(db, p->u.btree.pIndex->zColAff); |
| sqlite3DbFreeNN(db, p->u.btree.pIndex); |
| p->u.btree.pIndex = 0; |
| } |
| } |
| } |
| |
| /* |
| ** Deallocate internal memory used by a WhereLoop object |
| */ |
| static void whereLoopClear(sqlite3 *db, WhereLoop *p){ |
| if( p->aLTerm!=p->aLTermSpace ) sqlite3DbFreeNN(db, p->aLTerm); |
| whereLoopClearUnion(db, p); |
| whereLoopInit(p); |
| } |
| |
| /* |
| ** Increase the memory allocation for pLoop->aLTerm[] to be at least n. |
| */ |
| static int whereLoopResize(sqlite3 *db, WhereLoop *p, int n){ |
| WhereTerm **paNew; |
| if( p->nLSlot>=n ) return SQLITE_OK; |
| n = (n+7)&~7; |
| paNew = sqlite3DbMallocRawNN(db, sizeof(p->aLTerm[0])*n); |
| if( paNew==0 ) return SQLITE_NOMEM_BKPT; |
| memcpy(paNew, p->aLTerm, sizeof(p->aLTerm[0])*p->nLSlot); |
| if( p->aLTerm!=p->aLTermSpace ) sqlite3DbFreeNN(db, p->aLTerm); |
| p->aLTerm = paNew; |
| p->nLSlot = n; |
| return SQLITE_OK; |
| } |
| |
| /* |
| ** Transfer content from the second pLoop into the first. |
| */ |
| static int whereLoopXfer(sqlite3 *db, WhereLoop *pTo, WhereLoop *pFrom){ |
| whereLoopClearUnion(db, pTo); |
| if( whereLoopResize(db, pTo, pFrom->nLTerm) ){ |
| memset(&pTo->u, 0, sizeof(pTo->u)); |
| return SQLITE_NOMEM_BKPT; |
| } |
| memcpy(pTo, pFrom, WHERE_LOOP_XFER_SZ); |
| memcpy(pTo->aLTerm, pFrom->aLTerm, pTo->nLTerm*sizeof(pTo->aLTerm[0])); |
| if( pFrom->wsFlags & WHERE_VIRTUALTABLE ){ |
| pFrom->u.vtab.needFree = 0; |
| }else if( (pFrom->wsFlags & WHERE_AUTO_INDEX)!=0 ){ |
| pFrom->u.btree.pIndex = 0; |
| } |
| return SQLITE_OK; |
| } |
| |
| /* |
| ** Delete a WhereLoop object |
| */ |
| static void whereLoopDelete(sqlite3 *db, WhereLoop *p){ |
| whereLoopClear(db, p); |
| sqlite3DbFreeNN(db, p); |
| } |
| |
| /* |
| ** Free a WhereInfo structure |
| */ |
| static void whereInfoFree(sqlite3 *db, WhereInfo *pWInfo){ |
| int i; |
| assert( pWInfo!=0 ); |
| for(i=0; i<pWInfo->nLevel; i++){ |
| WhereLevel *pLevel = &pWInfo->a[i]; |
| if( pLevel->pWLoop && (pLevel->pWLoop->wsFlags & WHERE_IN_ABLE) ){ |
| sqlite3DbFree(db, pLevel->u.in.aInLoop); |
| } |
| } |
| sqlite3WhereClauseClear(&pWInfo->sWC); |
| while( pWInfo->pLoops ){ |
| WhereLoop *p = pWInfo->pLoops; |
| pWInfo->pLoops = p->pNextLoop; |
| whereLoopDelete(db, p); |
| } |
| sqlite3DbFreeNN(db, pWInfo); |
| } |
| |
| /* |
| ** Return TRUE if all of the following are true: |
| ** |
| ** (1) X has the same or lower cost that Y |
| ** (2) X uses fewer WHERE clause terms than Y |
| ** (3) Every WHERE clause term used by X is also used by Y |
| ** (4) X skips at least as many columns as Y |
| ** (5) If X is a covering index, than Y is too |
| ** |
| ** Conditions (2) and (3) mean that X is a "proper subset" of Y. |
| ** If X is a proper subset of Y then Y is a better choice and ought |
| ** to have a lower cost. This routine returns TRUE when that cost |
| ** relationship is inverted and needs to be adjusted. Constraint (4) |
| ** was added because if X uses skip-scan less than Y it still might |
| ** deserve a lower cost even if it is a proper subset of Y. Constraint (5) |
| ** was added because a covering index probably deserves to have a lower cost |
| ** than a non-covering index even if it is a proper subset. |
| */ |
| static int whereLoopCheaperProperSubset( |
| const WhereLoop *pX, /* First WhereLoop to compare */ |
| const WhereLoop *pY /* Compare against this WhereLoop */ |
| ){ |
| int i, j; |
| if( pX->nLTerm-pX->nSkip >= pY->nLTerm-pY->nSkip ){ |
| return 0; /* X is not a subset of Y */ |
| } |
| if( pY->nSkip > pX->nSkip ) return 0; |
| if( pX->rRun >= pY->rRun ){ |
| if( pX->rRun > pY->rRun ) return 0; /* X costs more than Y */ |
| if( pX->nOut > pY->nOut ) return 0; /* X costs more than Y */ |
| } |
| for(i=pX->nLTerm-1; i>=0; i--){ |
| if( pX->aLTerm[i]==0 ) continue; |
| for(j=pY->nLTerm-1; j>=0; j--){ |
| if( pY->aLTerm[j]==pX->aLTerm[i] ) break; |
| } |
| if( j<0 ) return 0; /* X not a subset of Y since term X[i] not used by Y */ |
| } |
| if( (pX->wsFlags&WHERE_IDX_ONLY)!=0 |
| && (pY->wsFlags&WHERE_IDX_ONLY)==0 ){ |
| return 0; /* Constraint (5) */ |
| } |
| return 1; /* All conditions meet */ |
| } |
| |
| /* |
| ** Try to adjust the cost of WhereLoop pTemplate upwards or downwards so |
| ** that: |
| ** |
| ** (1) pTemplate costs less than any other WhereLoops that are a proper |
| ** subset of pTemplate |
| ** |
| ** (2) pTemplate costs more than any other WhereLoops for which pTemplate |
| ** is a proper subset. |
| ** |
| ** To say "WhereLoop X is a proper subset of Y" means that X uses fewer |
| ** WHERE clause terms than Y and that every WHERE clause term used by X is |
| ** also used by Y. |
| */ |
| static void whereLoopAdjustCost(const WhereLoop *p, WhereLoop *pTemplate){ |
| if( (pTemplate->wsFlags & WHERE_INDEXED)==0 ) return; |
| for(; p; p=p->pNextLoop){ |
| if( p->iTab!=pTemplate->iTab ) continue; |
| if( (p->wsFlags & WHERE_INDEXED)==0 ) continue; |
| if( whereLoopCheaperProperSubset(p, pTemplate) ){ |
| /* Adjust pTemplate cost downward so that it is cheaper than its |
| ** subset p. */ |
| WHERETRACE(0x80,("subset cost adjustment %d,%d to %d,%d\n", |
| pTemplate->rRun, pTemplate->nOut, p->rRun, p->nOut-1)); |
| pTemplate->rRun = p->rRun; |
| pTemplate->nOut = p->nOut - 1; |
| }else if( whereLoopCheaperProperSubset(pTemplate, p) ){ |
| /* Adjust pTemplate cost upward so that it is costlier than p since |
| ** pTemplate is a proper subset of p */ |
| WHERETRACE(0x80,("subset cost adjustment %d,%d to %d,%d\n", |
| pTemplate->rRun, pTemplate->nOut, p->rRun, p->nOut+1)); |
| pTemplate->rRun = p->rRun; |
| pTemplate->nOut = p->nOut + 1; |
| } |
| } |
| } |
| |
| /* |
| ** Search the list of WhereLoops in *ppPrev looking for one that can be |
| ** replaced by pTemplate. |
| ** |
| ** Return NULL if pTemplate does not belong on the WhereLoop list. |
| ** In other words if pTemplate ought to be dropped from further consideration. |
| ** |
| ** If pX is a WhereLoop that pTemplate can replace, then return the |
| ** link that points to pX. |
| ** |
| ** If pTemplate cannot replace any existing element of the list but needs |
| ** to be added to the list as a new entry, then return a pointer to the |
| ** tail of the list. |
| */ |
| static WhereLoop **whereLoopFindLesser( |
| WhereLoop **ppPrev, |
| const WhereLoop *pTemplate |
| ){ |
| WhereLoop *p; |
| for(p=(*ppPrev); p; ppPrev=&p->pNextLoop, p=*ppPrev){ |
| if( p->iTab!=pTemplate->iTab || p->iSortIdx!=pTemplate->iSortIdx ){ |
| /* If either the iTab or iSortIdx values for two WhereLoop are different |
| ** then those WhereLoops need to be considered separately. Neither is |
| ** a candidate to replace the other. */ |
| continue; |
| } |
| /* In the current implementation, the rSetup value is either zero |
| ** or the cost of building an automatic index (NlogN) and the NlogN |
| ** is the same for compatible WhereLoops. */ |
| assert( p->rSetup==0 || pTemplate->rSetup==0 |
| || p->rSetup==pTemplate->rSetup ); |
| |
| /* whereLoopAddBtree() always generates and inserts the automatic index |
| ** case first. Hence compatible candidate WhereLoops never have a larger |
| ** rSetup. Call this SETUP-INVARIANT */ |
| assert( p->rSetup>=pTemplate->rSetup ); |
| |
| /* Any loop using an appliation-defined index (or PRIMARY KEY or |
| ** UNIQUE constraint) with one or more == constraints is better |
| ** than an automatic index. Unless it is a skip-scan. */ |
| if( (p->wsFlags & WHERE_AUTO_INDEX)!=0 |
| && (pTemplate->nSkip)==0 |
| && (pTemplate->wsFlags & WHERE_INDEXED)!=0 |
| && (pTemplate->wsFlags & WHERE_COLUMN_EQ)!=0 |
| && (p->prereq & pTemplate->prereq)==pTemplate->prereq |
| ){ |
| break; |
| } |
| |
| /* If existing WhereLoop p is better than pTemplate, pTemplate can be |
| ** discarded. WhereLoop p is better if: |
| ** (1) p has no more dependencies than pTemplate, and |
| ** (2) p has an equal or lower cost than pTemplate |
| */ |
| if( (p->prereq & pTemplate->prereq)==p->prereq /* (1) */ |
| && p->rSetup<=pTemplate->rSetup /* (2a) */ |
| && p->rRun<=pTemplate->rRun /* (2b) */ |
| && p->nOut<=pTemplate->nOut /* (2c) */ |
| ){ |
| return 0; /* Discard pTemplate */ |
| } |
| |
| /* If pTemplate is always better than p, then cause p to be overwritten |
| ** with pTemplate. pTemplate is better than p if: |
| ** (1) pTemplate has no more dependences than p, and |
| ** (2) pTemplate has an equal or lower cost than p. |
| */ |
| if( (p->prereq & pTemplate->prereq)==pTemplate->prereq /* (1) */ |
| && p->rRun>=pTemplate->rRun /* (2a) */ |
| && p->nOut>=pTemplate->nOut /* (2b) */ |
| ){ |
| assert( p->rSetup>=pTemplate->rSetup ); /* SETUP-INVARIANT above */ |
| break; /* Cause p to be overwritten by pTemplate */ |
| } |
| } |
| return ppPrev; |
| } |
| |
| /* |
| ** Insert or replace a WhereLoop entry using the template supplied. |
| ** |
| ** An existing WhereLoop entry might be overwritten if the new template |
| ** 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 on the template. |
| ** |
| ** If pBuilder->pOrSet is not NULL then we 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->pOrSet is NULL) we |
| ** still might overwrite similar loops with the new template if the |
| ** new template is better. Loops may be overwritten if the following |
| ** conditions are met: |
| ** |
| ** (1) They have the same iTab. |
| ** (2) They have the same iSortIdx. |
| ** (3) The template has same or fewer dependencies than the current loop |
| ** (4) The template has the same or lower cost than the current loop |
| */ |
| static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){ |
| WhereLoop **ppPrev, *p; |
| WhereInfo *pWInfo = pBuilder->pWInfo; |
| sqlite3 *db = pWInfo->pParse->db; |
| int rc; |
| |
| /* Stop the search once we hit the query planner search limit */ |
| if( pBuilder->iPlanLimit==0 ){ |
| WHERETRACE(0xffffffff,("=== query planner search limit reached ===\n")); |
| if( pBuilder->pOrSet ) pBuilder->pOrSet->n = 0; |
| return SQLITE_DONE; |
| } |
| pBuilder->iPlanLimit--; |
| |
| /* If pBuilder->pOrSet is defined, then only keep track of the costs |
| ** and prereqs. |
| */ |
| if( pBuilder->pOrSet!=0 ){ |
| if( pTemplate->nLTerm ){ |
| #if WHERETRACE_ENABLED |
| u16 n = pBuilder->pOrSet->n; |
| int x = |
| #endif |
| whereOrInsert(pBuilder->pOrSet, pTemplate->prereq, pTemplate->rRun, |
| pTemplate->nOut); |
| #if WHERETRACE_ENABLED /* 0x8 */ |
| if( sqlite3WhereTrace & 0x8 ){ |
| sqlite3DebugPrintf(x?" or-%d: ":" or-X: ", n); |
| whereLoopPrint(pTemplate, pBuilder->pWC); |
| } |
| #endif |
| } |
| return SQLITE_OK; |
| } |
| |
| /* Look for an existing WhereLoop to replace with pTemplate |
| */ |
| whereLoopAdjustCost(pWInfo->pLoops, pTemplate); |
| ppPrev = whereLoopFindLesser(&pWInfo->pLoops, pTemplate); |
| |
| if( ppPrev==0 ){ |
| /* There already exists a WhereLoop on the list that is better |
| ** than pTemplate, so just ignore pTemplate */ |
| #if WHERETRACE_ENABLED /* 0x8 */ |
| if( sqlite3WhereTrace & 0x8 ){ |
| sqlite3DebugPrintf(" skip: "); |
| whereLoopPrint(pTemplate, pBuilder->pWC); |
| } |
| #endif |
| return SQLITE_OK; |
| }else{ |
| p = *ppPrev; |
| } |
| |
| /* If we reach this point it means that either p[] should be overwritten |
| ** with pTemplate[] if p[] exists, or if p==NULL then allocate a new |
| ** WhereLoop and insert it. |
| */ |
| #if WHERETRACE_ENABLED /* 0x8 */ |
| if( sqlite3WhereTrace & 0x8 ){ |
| if( p!=0 ){ |
| sqlite3DebugPrintf("replace: "); |
| whereLoopPrint(p, pBuilder->pWC); |
| sqlite3DebugPrintf(" with: "); |
| }else{ |
| sqlite3DebugPrintf(" add: "); |
| } |
| whereLoopPrint(pTemplate, pBuilder->pWC); |
| } |
| #endif |
| if( p==0 ){ |
| /* Allocate a new WhereLoop to add to the end of the list */ |
| *ppPrev = p = sqlite3DbMallocRawNN(db, sizeof(WhereLoop)); |
| if( p==0 ) return SQLITE_NOMEM_BKPT; |
| whereLoopInit(p); |
| p->pNextLoop = 0; |
| }else{ |
| /* We will be overwriting WhereLoop p[]. But before we do, first |
| ** go through the rest of the list and delete any other entries besides |
| ** p[] that are also supplated by pTemplate */ |
| WhereLoop **ppTail = &p->pNextLoop; |
| WhereLoop *pToDel; |
| while( *ppTail ){ |
| ppTail = whereLoopFindLesser(ppTail, pTemplate); |
| if( ppTail==0 ) break; |
| pToDel = *ppTail; |
| if( pToDel==0 ) break; |
| *ppTail = pToDel->pNextLoop; |
| #if WHERETRACE_ENABLED /* 0x8 */ |
| if( sqlite3WhereTrace & 0x8 ){ |
| sqlite3DebugPrintf(" delete: "); |
| whereLoopPrint(pToDel, pBuilder->pWC); |
| } |
| #endif |
| whereLoopDelete(db, pToDel); |
| } |
| } |
| rc = whereLoopXfer(db, p, pTemplate); |
| if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){ |
| Index *pIndex = p->u.btree.pIndex; |
| if( pIndex && pIndex->idxType==SQLITE_IDXTYPE_IPK ){ |
| p->u.btree.pIndex = 0; |
| } |
| } |
| return rc; |
| } |
| |
| /* |
| ** 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. |
| * |
| ** For every WHERE clause term that is not used by the index |
| ** and which has a truth probability assigned by one of the likelihood(), |
| ** likely(), or unlikely() SQL functions, reduce the estimated number |
| ** of output rows by the probability specified. |
| ** |
| ** TUNING: For every WHERE clause term that is not used by the index |
| ** and which does not have an assigned truth probability, heuristics |
| ** described below are used to try to estimate the truth probability. |
| ** TODO --> Perhaps this is something that could be improved by better |
| ** table statistics. |
| ** |
| ** Heuristic 1: Estimate the truth probability as 93.75%. The 93.75% |
| ** value corresponds to -1 in LogEst notation, so this means decrement |
| ** the WhereLoop.nOut field for every such WHERE clause term. |
| ** |
| ** Heuristic 2: If there exists one or more WHERE clause terms of the |
| ** form "x==EXPR" and EXPR is not a constant 0 or 1, then make sure the |
| ** final output row estimate is no greater than 1/4 of the total number |
| ** of rows in the table. In other words, assume that x==EXPR will filter |
| ** out at least 3 out of 4 rows. If EXPR is -1 or 0 or 1, then maybe the |
| ** "x" column is boolean or else -1 or 0 or 1 is a common default value |
| ** on the "x" column and so in that case only cap the output row estimate |
| ** at 1/2 instead of 1/4. |
| */ |
| static void whereLoopOutputAdjust( |
| WhereClause *pWC, /* The WHERE clause */ |
| WhereLoop *pLoop, /* The loop to adjust downward */ |
| LogEst nRow /* Number of rows in the entire table */ |
| ){ |
| WhereTerm *pTerm, *pX; |
| Bitmask notAllowed = ~(pLoop->prereq|pLoop->maskSelf); |
| int i, j, k; |
| LogEst iReduce = 0; /* pLoop->nOut should not exceed nRow-iReduce */ |
| |
| assert( (pLoop->wsFlags & WHERE_AUTO_INDEX)==0 ); |
| 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==0 ) continue; |
| if( pX==pTerm ) break; |
| if( pX->iParent>=0 && (&pWC->a[pX->iParent])==pTerm ) break; |
| } |
| if( j<0 ){ |
| if( pTerm->truthProb<=0 ){ |
| /* If a truth probability is specified using the likelihood() hints, |
| ** then use the probability provided by the application. */ |
| pLoop->nOut += pTerm->truthProb; |
| }else{ |
| /* In the absence of explicit truth probabilities, use heuristics to |
| ** guess a reasonable truth probability. */ |
| pLoop->nOut--; |
| if( pTerm->eOperator&(WO_EQ|WO_IS) ){ |
| Expr *pRight = pTerm->pExpr->pRight; |
| testcase( pTerm->pExpr->op==TK_IS ); |
| if( sqlite3ExprIsInteger(pRight, &k) && k>=(-1) && k<=1 ){ |
| k = 10; |
| }else{ |
| k = 20; |
| } |
| if( iReduce<k ) iReduce = k; |
| } |
| } |
| } |
| } |
| if( pLoop->nOut > nRow-iReduce ) pLoop->nOut = nRow - iReduce; |
| } |
| |
| /* |
| ** Term pTerm is a vector range comparison operation. The first comparison |
| ** in the vector can be optimized using column nEq of the index. This |
| ** function returns the total number of vector elements that can be used |
| ** as part of the range comparison. |
| ** |
| ** For example, if the query is: |
| ** |
| ** WHERE a = ? AND (b, c, d) > (?, ?, ?) |
| ** |
| ** and the index: |
| ** |
| ** CREATE INDEX ... ON (a, b, c, d, e) |
| ** |
| ** then this function would be invoked with nEq=1. The value returned in |
| ** this case is 3. |
| */ |
| static int whereRangeVectorLen( |
| Parse *pParse, /* Parsing context */ |
| int iCur, /* Cursor open on pIdx */ |
| Index *pIdx, /* The index to be used for a inequality constraint */ |
| int nEq, /* Number of prior equality constraints on same index */ |
| WhereTerm *pTerm /* The vector inequality constraint */ |
| ){ |
| int nCmp = sqlite3ExprVectorSize(pTerm->pExpr->pLeft); |
| int i; |
| |
| nCmp = MIN(nCmp, (pIdx->nColumn - nEq)); |
| for(i=1; i<nCmp; i++){ |
| /* Test if comparison i of pTerm is compatible with column (i+nEq) |
| ** of the index. If not, exit the loop. */ |
| char aff; /* Comparison affinity */ |
| char idxaff = 0; /* Indexed columns affinity */ |
| CollSeq *pColl; /* Comparison collation sequence */ |
| Expr *pLhs = pTerm->pExpr->pLeft->x.pList->a[i].pExpr; |
| Expr *pRhs = pTerm->pExpr->pRight; |
| if( pRhs->flags & EP_xIsSelect ){ |
| pRhs = pRhs->x.pSelect->pEList->a[i].pExpr; |
| }else{ |
| pRhs = pRhs->x.pList->a[i].pExpr; |
| } |
| |
| /* Check that the LHS of the comparison is a column reference to |
| ** the right column of the right source table. And that the sort |
| ** order of the index column is the same as the sort order of the |
| ** leftmost index column. */ |
| if( pLhs->op!=TK_COLUMN |
| || pLhs->iTable!=iCur |
| || pLhs->iColumn!=pIdx->aiColumn[i+nEq] |
| || pIdx->aSortOrder[i+nEq]!=pIdx->aSortOrder[nEq] |
| ){ |
| break; |
| } |
| |
| testcase( pLhs->iColumn==XN_ROWID ); |
| aff = sqlite3CompareAffinity(pRhs, sqlite3ExprAffinity(pLhs)); |
| idxaff = sqlite3TableColumnAffinity(pIdx->pTable, pLhs->iColumn); |
| if( aff!=idxaff ) break; |
| |
| pColl = sqlite3BinaryCompareCollSeq(pParse, pLhs, pRhs); |
| if( pColl==0 ) break; |
| if( sqlite3StrICmp(pColl->zName, pIdx->azColl[i+nEq]) ) break; |
| } |
| return i; |
| } |
| |
| /* |
| ** Adjust the cost C by the costMult facter T. This only occurs if |
| ** compiled with -DSQLITE_ENABLE_COSTMULT |
| */ |
| #ifdef SQLITE_ENABLE_COSTMULT |
| # define ApplyCostMultiplier(C,T) C += T |
| #else |
| # define ApplyCostMultiplier(C,T) |
| #endif |
| |
| /* |
| ** We have so far matched pBuilder->pNew->u.btree.nEq terms of the |
| ** index pIndex. Try to match one more. |
| ** |
| ** When this function is called, pBuilder->pNew->nOut contains the |
| ** number of rows expected to be visited by filtering using the nEq |
| ** terms only. If it is modified, this value is restored before this |
| ** function returns. |
| ** |
| ** If pProbe->idxType==SQLITE_IDXTYPE_IPK, that means pIndex is |
| ** a fake index used for the INTEGER PRIMARY KEY. |
| */ |
| static int whereLoopAddBtreeIndex( |
| WhereLoopBuilder *pBuilder, /* The WhereLoop factory */ |
| struct SrcList_item *pSrc, /* FROM clause term being analyzed */ |
| Index *pProbe, /* An index on pSrc */ |
| LogEst nInMul /* log(Number of iterations due to IN) */ |
| ){ |
| WhereInfo *pWInfo = pBuilder->pWInfo; /* WHERE analyse context */ |
| Parse *pParse = pWInfo->pParse; /* Parsing context */ |
| sqlite3 *db = pParse->db; /* Database connection malloc context */ |
| WhereLoop *pNew; /* Template WhereLoop under construction */ |
| WhereTerm *pTerm; /* A WhereTerm under consideration */ |
| int opMask; /* Valid operators for constraints */ |
| WhereScan scan; /* Iterator for WHERE terms */ |
| Bitmask saved_prereq; /* Original value of pNew->prereq */ |
| u16 saved_nLTerm; /* Original value of pNew->nLTerm */ |
| u16 saved_nEq; /* Original value of pNew->u.btree.nEq */ |
| u16 saved_nBtm; /* Original value of pNew->u.btree.nBtm */ |
| u16 saved_nTop; /* Original value of pNew->u.btree.nTop */ |
| u16 saved_nSkip; /* Original value of pNew->nSkip */ |
| u32 saved_wsFlags; /* Original value of pNew->wsFlags */ |
| LogEst saved_nOut; /* Original value of pNew->nOut */ |
| int rc = SQLITE_OK; /* Return code */ |
| LogEst rSize; /* Number of rows in the table */ |
| LogEst rLogSize; /* Logarithm of table size */ |
| WhereTerm *pTop = 0, *pBtm = 0; /* Top and bottom range constraints */ |
| |
| pNew = pBuilder->pNew; |
| if( db->mallocFailed ) return SQLITE_NOMEM_BKPT; |
| WHERETRACE(0x800, ("BEGIN %s.addBtreeIdx(%s), nEq=%d\n", |
| pProbe->pTable->zName,pProbe->zName, pNew->u.btree.nEq)); |
| |
| assert( (pNew->wsFlags & WHERE_VIRTUALTABLE)==0 ); |
| assert( (pNew->wsFlags & WHERE_TOP_LIMIT)==0 ); |
| if( pNew->wsFlags & WHERE_BTM_LIMIT ){ |
| opMask = WO_LT|WO_LE; |
| }else{ |
| assert( pNew->u.btree.nBtm==0 ); |
| opMask = WO_EQ|WO_IN|WO_GT|WO_GE|WO_LT|WO_LE|WO_ISNULL|WO_IS; |
| } |
| if( pProbe->bUnordered ) opMask &= ~(WO_GT|WO_GE|WO_LT|WO_LE); |
| |
| assert( pNew->u.btree.nEq<pProbe->nColumn ); |
| |
| saved_nEq = pNew->u.btree.nEq; |
| saved_nBtm = pNew->u.btree.nBtm; |
| saved_nTop = pNew->u.btree.nTop; |
| saved_nSkip = pNew->nSkip; |
| saved_nLTerm = pNew->nLTerm; |
| saved_wsFlags = pNew->wsFlags; |
| saved_prereq = pNew->prereq; |
| saved_nOut = pNew->nOut; |
| pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, saved_nEq, |
| opMask, pProbe); |
| pNew->rSetup = 0; |
| rSize = pProbe->aiRowLogEst[0]; |
| rLogSize = estLog(rSize); |
| for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){ |
| u16 eOp = pTerm->eOperator; /* Shorthand for pTerm->eOperator */ |
| LogEst rCostIdx; |
| LogEst nOutUnadjusted; /* nOut before IN() and WHERE adjustments */ |
| int nIn = 0; |
| #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 |
| int nRecValid = pBuilder->nRecValid; |
| #endif |
| if( (eOp==WO_ISNULL || (pTerm->wtFlags&TERM_VNULL)!=0) |
| && indexColumnNotNull(pProbe, saved_nEq) |
| ){ |
| continue; /* ignore IS [NOT] NULL constraints on NOT NULL columns */ |
| } |
| if( pTerm->prereqRight & pNew->maskSelf ) continue; |
| |
| /* Do not allow the upper bound of a LIKE optimization range constraint |
| ** to mix with a lower range bound from some other source */ |
| if( pTerm->wtFlags & TERM_LIKEOPT && pTerm->eOperator==WO_LT ) continue; |
| |
| /* Do not allow constraints from the WHERE clause to be used by the |
| ** right table of a LEFT JOIN. Only constraints in the ON clause are |
| ** allowed */ |
| if( (pSrc->fg.jointype & JT_LEFT)!=0 |
| && !ExprHasProperty(pTerm->pExpr, EP_FromJoin) |
| ){ |
| continue; |
| } |
| |
| if( IsUniqueIndex(pProbe) && saved_nEq==pProbe->nKeyCol-1 ){ |
| pBuilder->bldFlags |= SQLITE_BLDF_UNIQUE; |
| }else{ |
| pBuilder->bldFlags |= SQLITE_BLDF_INDEXED; |
| } |
| pNew->wsFlags = saved_wsFlags; |
| pNew->u.btree.nEq = saved_nEq; |
| 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 */ |
| pNew->aLTerm[pNew->nLTerm++] = pTerm; |
| pNew->prereq = (saved_prereq | pTerm->prereqRight) & ~pNew->maskSelf; |
| |
| assert( nInMul==0 |
| || (pNew->wsFlags & WHERE_COLUMN_NULL)!=0 |
| || (pNew->wsFlags & WHERE_COLUMN_IN)!=0 |
| || (pNew->wsFlags & WHERE_SKIPSCAN)!=0 |
| ); |
| |
| if( eOp & WO_IN ){ |
| Expr *pExpr = pTerm->pExpr; |
| if( ExprHasProperty(pExpr, EP_xIsSelect) ){ |
| /* "x IN (SELECT ...)": TUNING: the SELECT returns 25 rows */ |
| int i; |
| nIn = 46; assert( 46==sqlite3LogEst(25) ); |
| |
| /* The expression may actually be of the form (x, y) IN (SELECT...). |
| ** In this case there is a separate term for each of (x) and (y). |
| ** However, the nIn multiplier should only be applied once, not once |
| ** for each such term. The following loop checks that pTerm is the |
| ** first such term in use, and sets nIn back to 0 if it is not. */ |
| for(i=0; i<pNew->nLTerm-1; i++){ |
| if( pNew->aLTerm[i] && pNew->aLTerm[i]->pExpr==pExpr ) nIn = 0; |
| } |
| }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){ |
| /* "x IN (value, value, ...)" */ |
| nIn = sqlite3LogEst(pExpr->x.pList->nExpr); |
| assert( nIn>0 ); /* RHS always has 2 or more terms... The parser |
| ** changes "x IN (?)" into "x=?". */ |
| } |
| if( pProbe->hasStat1 ){ |
| LogEst M, logK, safetyMargin; |
| /* Let: |
| ** N = the total number of rows in the table |
| ** K = the number of entries on the RHS of the IN operator |
| ** M = the number of rows in the table that match terms to the |
| ** to the left in the same index. If the IN operator is on |
| ** the left-most index column, M==N. |
| ** |
| ** Given the definitions above, it is better to omit the IN operator |
| ** from the index lookup and instead do a scan of the M elements, |
| ** testing each scanned row against the IN operator separately, if: |
| ** |
| ** M*log(K) < K*log(N) |
| ** |
| ** Our estimates for M, K, and N might be inaccurate, so we build in |
| ** a safety margin of 2 (LogEst: 10) that favors using the IN operator |
| ** with the index, as using an index has better worst-case behavior. |
| ** If we do not have real sqlite_stat1 data, always prefer to use |
| ** the index. |
| */ |
| M = pProbe->aiRowLogEst[saved_nEq]; |
| logK = estLog(nIn); |
| safetyMargin = 10; /* TUNING: extra weight for indexed IN */ |
| if( M + logK + safetyMargin < nIn + rLogSize ){ |
| WHERETRACE(0x40, |
| ("Scan preferred over IN operator on column %d of \"%s\" (%d<%d)\n", |
| saved_nEq, pProbe->zName, M+logK+10, nIn+rLogSize)); |
| continue; |
| }else{ |
| WHERETRACE(0x40, |
| ("IN operator preferred on column %d of \"%s\" (%d>=%d)\n", |
| saved_nEq, pProbe->zName, M+logK+10, nIn+rLogSize)); |
| } |
| } |
| pNew->wsFlags |= WHERE_COLUMN_IN; |
| }else if( eOp & (WO_EQ|WO_IS) ){ |
| int iCol = pProbe->aiColumn[saved_nEq]; |
| pNew->wsFlags |= WHERE_COLUMN_EQ; |
| assert( saved_nEq==pNew->u.btree.nEq ); |
| if( iCol==XN_ROWID |
| || (iCol>=0 && nInMul==0 && saved_nEq==pProbe->nKeyCol-1) |
| ){ |
| if( iCol==XN_ROWID || pProbe->uniqNotNull |
| || (pProbe->nKeyCol==1 && pProbe->onError && eOp==WO_EQ) |
| ){ |
| pNew->wsFlags |= WHERE_ONEROW; |
| }else{ |
| pNew->wsFlags |= WHERE_UNQ_WANTED; |
| } |
| } |
| }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 contraints 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( |
| pParse, pSrc->iCursor, pProbe, saved_nEq, pTerm |
| ); |
| 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 |
| ** be visited by the index scan before considering term pTerm, or the |
| ** values of nIn and nInMul. In other words, assuming that all |
| ** "x IN(...)" terms are replaced with "x = ?". This block updates |
| ** the value of pNew->nOut to account for pTerm (but not nIn/nInMul). */ |
| assert( pNew->nOut==saved_nOut ); |
| if( pNew->wsFlags & WHERE_COLUMN_RANGE ){ |
| /* Adjust nOut using stat3/stat4 data. Or, if there is no stat3/stat4 |
| ** data, using some other estimate. */ |
| whereRangeScanEst(pParse, pBuilder, pBtm, pTop, pNew); |
| }else{ |
| int nEq = ++pNew->u.btree.nEq; |
| assert( eOp & (WO_ISNULL|WO_EQ|WO_IN|WO_IS) ); |
| |
| assert( pNew->nOut==saved_nOut ); |
| if( pTerm->truthProb<=0 && pProbe->aiColumn[saved_nEq]>=0 ){ |
| assert( (eOp & WO_IN) || nIn==0 ); |
| testcase( eOp & WO_IN ); |
| pNew->nOut += pTerm->truthProb; |
| pNew->nOut -= nIn; |
| }else{ |
| #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 |
| tRowcnt nOut = 0; |
| if( nInMul==0 |
| && pProbe->nSample |
| && pNew->u.btree.nEq<=pProbe->nSampleCol |
| && ((eOp & WO_IN)==0 || !ExprHasProperty(pTerm->pExpr, EP_xIsSelect)) |
| && OptimizationEnabled(db, SQLITE_Stat34) |
| ){ |
| Expr *pExpr = pTerm->pExpr; |
| if( (eOp & (WO_EQ|WO_ISNULL|WO_IS))!=0 ){ |
| testcase( eOp & WO_EQ ); |
| testcase( eOp & WO_IS ); |
| testcase( eOp & WO_ISNULL ); |
| rc = whereEqualScanEst(pParse, pBuilder, pExpr->pRight, &nOut); |
| }else{ |
| rc = whereInScanEst(pParse, pBuilder, pExpr->x.pList, &nOut); |
| } |
| if( rc==SQLITE_NOTFOUND ) rc = SQLITE_OK; |
| if( rc!=SQLITE_OK ) break; /* Jump out of the pTerm loop */ |
| if( nOut ){ |
| pNew->nOut = sqlite3LogEst(nOut); |
| if( pNew->nOut>saved_nOut ) pNew->nOut = saved_nOut; |
| pNew->nOut -= nIn; |
| } |
| } |
| if( nOut==0 ) |
| #endif |
| { |
| pNew->nOut += (pProbe->aiRowLogEst[nEq] - pProbe->aiRowLogEst[nEq-1]); |
| if( eOp & WO_ISNULL ){ |
| /* TUNING: If there is no likelihood() value, assume that a |
| ** "col IS NULL" expression matches twice as many rows |
| ** as (col=?). */ |
| pNew->nOut += 10; |
| } |
| } |
| } |
| } |
| |
| /* Set rCostIdx to the cost of visiting selected rows in index. Add |
| ** it to pNew->rRun, which is currently set to the cost of the index |
| ** seek only. Then, if this is a non-covering index, add the cost of |
| ** visiting the rows in the main table. */ |
| rCostIdx = pNew->nOut + 1 + (15*pProbe->szIdxRow)/pSrc->pTab->szTabRow; |
| pNew->rRun = sqlite3LogEstAdd(rLogSize, rCostIdx); |
| if( (pNew->wsFlags & (WHERE_IDX_ONLY|WHERE_IPK))==0 ){ |
| pNew->rRun = sqlite3LogEstAdd(pNew->rRun, pNew->nOut + 16); |
| } |
| ApplyCostMultiplier(pNew->rRun, pProbe->pTable->costMult); |
| |
| nOutUnadjusted = pNew->nOut; |
| pNew->rRun += nInMul + nIn; |
| pNew->nOut += nInMul + nIn; |
| whereLoopOutputAdjust(pBuilder->pWC, pNew, rSize); |
| rc = whereLoopInsert(pBuilder, pNew); |
| |
| if( pNew->wsFlags & WHERE_COLUMN_RANGE ){ |
| pNew->nOut = saved_nOut; |
| }else{ |
| pNew->nOut = nOutUnadjusted; |
| } |
| |
| if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0 |
| && pNew->u.btree.nEq<pProbe->nColumn |
| ){ |
| whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul+nIn); |
| } |
| pNew->nOut = saved_nOut; |
| #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 |
| pBuilder->nRecValid = nRecValid; |
| #endif |
| } |
| pNew->prereq = saved_prereq; |
| pNew->u.btree.nEq = saved_nEq; |
| pNew->u.btree.nBtm = saved_nBtm; |
| pNew->u.btree.nTop = saved_nTop; |
| pNew->nSkip = saved_nSkip; |
| pNew->wsFlags = saved_wsFlags; |
| pNew->nOut = saved_nOut; |
| pNew->nLTerm = saved_nLTerm; |
| |
| /* Consider using a skip-scan if there are no WHERE clause constraints |
| ** available for the left-most terms of the index, and if the average |
| ** number of repeats in the left-most terms is at least 18. |
| ** |
| ** The magic number 18 is selected on the basis that scanning 17 rows |
| ** is almost always quicker than an index seek (even though if the index |
| ** contains fewer than 2^17 rows we assume otherwise in other parts of |
| ** the code). And, even if it is not, it should not be too much slower. |
| ** On the other hand, the extra seeks could end up being significantly |
| ** more expensive. */ |
| assert( 42==sqlite3LogEst(18) ); |
| if( saved_nEq==saved_nSkip |
| && saved_nEq+1<pProbe->nKeyCol |
| && pProbe->noSkipScan==0 |
| && OptimizationEnabled(db, SQLITE_SkipScan) |
| && pProbe->aiRowLogEst[saved_nEq+1]>=42 /* TUNING: Minimum for skip-scan */ |
| && (rc = whereLoopResize(db, pNew, pNew->nLTerm+1))==SQLITE_OK |
| ){ |
| LogEst nIter; |
| pNew->u.btree.nEq++; |
| pNew->nSkip++; |
| pNew->aLTerm[pNew->nLTerm++] = 0; |
| pNew->wsFlags |= WHERE_SKIPSCAN; |
| nIter = pProbe->aiRowLogEst[saved_nEq] - pProbe->aiRowLogEst[saved_nEq+1]; |
| pNew->nOut -= nIter; |
| /* TUNING: Because uncertainties in the estimates for skip-scan queries, |
| ** add a 1.375 fudge factor to make skip-scan slightly less likely. */ |
| nIter += 5; |
| whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nIter + nInMul); |
| pNew->nOut = saved_nOut; |
| pNew->u.btree.nEq = saved_nEq; |
| pNew->nSkip = saved_nSkip; |
| pNew->wsFlags = saved_wsFlags; |
| } |
| |
| WHERETRACE(0x800, ("END %s.addBtreeIdx(%s), nEq=%d, rc=%d\n", |
| pProbe->pTable->zName, pProbe->zName, saved_nEq, rc)); |
| return rc; |
| } |
| |
| /* |
| ** Return True if it is possible that pIndex might be useful in |
| ** implementing the ORDER BY clause in pBuilder. |
| ** |
| ** Return False if pBuilder does not contain an ORDER BY clause or |
| ** if there is no way for pIndex to be useful in implementing that |
| ** ORDER BY clause. |
| */ |
| static int indexMightHelpWithOrderBy( |
| WhereLoopBuilder *pBuilder, |
| Index *pIndex, |
| int iCursor |
| ){ |
| ExprList *pOB; |
| ExprList *aColExpr; |
| int ii, jj; |
| |
| if( pIndex->bUnordered ) return 0; |
| if( (pOB = pBuilder->pWInfo->pOrderBy)==0 ) return 0; |
| for(ii=0; ii<pOB->nExpr; ii++){ |
| Expr *pExpr = sqlite3ExprSkipCollate(pOB->a[ii].pExpr); |
| if( pExpr->op==TK_COLUMN && pExpr->iTable==iCursor ){ |
| if( pExpr->iColumn<0 ) return 1; |
| for(jj=0; jj<pIndex->nKeyCol; jj++){ |
| if( pExpr->iColumn==pIndex->aiColumn[jj] ) return 1; |
| } |
| }else if( (aColExpr = pIndex->aColExpr)!=0 ){ |
| for(jj=0; jj<pIndex->nKeyCol; jj++){ |
| if( pIndex->aiColumn[jj]!=XN_EXPR ) continue; |
| if( sqlite3ExprCompareSkip(pExpr,aColExpr->a[jj].pExpr,iCursor)==0 ){ |
| return 1; |
| } |
| } |
| } |
| } |
| return 0; |
| } |
| |
| /* 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; |
| Parse *pParse = pWC->pWInfo->pParse; |
| while( pWhere->op==TK_AND ){ |
| if( !whereUsablePartialIndex(iTab,pWC,pWhere->pLeft) ) return 0; |
| pWhere = pWhere->pRight; |
| } |
| if( pParse->db->flags & SQLITE_EnableQPSG ) pParse = 0; |
| for(i=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){ |
| Expr *pExpr = pTerm->pExpr; |
| if( (!ExprHasProperty(pExpr, EP_FromJoin) || pExpr->iRightJoinTable==iTab) |
| && sqlite3ExprImpliesExpr(pParse, pExpr, pWhere, iTab) |
| ){ |
| return 1; |
| } |
| } |
| return 0; |
| } |
| |
| /* |
| ** 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. |
| ** |
| ** The costs (WhereLoop.rRun) of the b-tree loops added by this function |
| ** are calculated as follows: |
| ** |
| ** For a full scan, assuming the table (or index) contains nRow rows: |
| ** |
| ** cost = nRow * 3.0 // full-table scan |
| ** cost = nRow * K // scan of covering index |
| ** cost = nRow * (K+3.0) // scan of non-covering index |
| ** |
| ** where K is a value between 1.1 and 3.0 set based on the relative |
| ** estimated average size of the index and table records. |
| ** |
| ** For an index scan, where nVisit is the number of index rows visited |
| ** by the scan, and nSeek is the number of seek operations required on |
| ** the index b-tree: |
| ** |
| ** cost = nSeek * (log(nRow) + K * nVisit) // covering index |
| ** cost = nSeek * (log(nRow) + (K+3.0) * nVisit) // non-covering index |
| ** |
| ** Normally, nSeek is 1. nSeek values greater than 1 come about if the |
| ** WHERE clause includes "x IN (....)" terms used in place of "x=?". Or when |
| ** implicit "x IN (SELECT x FROM tbl)" terms are added for skip-scans. |
| ** |
| ** The estimated values (nRow, nVisit, nSeek) often contain a large amount |
| ** of uncertainty. For this reason, scoring is designed to pick plans that |
| ** "do the least harm" if the estimates are inaccurate. For example, a |
| ** log(nRow) factor is omitted from a non-covering index scan in order to |
| ** bias the scoring in favor of using an index, since the worst-case |
| ** performance of using an index is far better than the worst-case performance |
| ** of a full table scan. |
| */ |
| static int whereLoopAddBtree( |
| WhereLoopBuilder *pBuilder, /* WHERE clause information */ |
| Bitmask mPrereq /* Extra prerequesites for using this table */ |
| ){ |
| WhereInfo *pWInfo; /* WHERE analysis context */ |
| Index *pProbe; /* An index we are evaluating */ |
| Index sPk; /* A fake index object for the primary key */ |
| LogEst aiRowEstPk[2]; /* The aiRowLogEst[] value for the sPk index */ |
| i16 aiColumnPk = -1; /* The aColumn[] value for the sPk index */ |
| SrcList *pTabList; /* The FROM clause */ |
| struct SrcList_item *pSrc; /* The FROM clause btree term to add */ |
| WhereLoop *pNew; /* Template WhereLoop object */ |
| int rc = SQLITE_OK; /* Return code */ |
| int iSortIdx = 1; /* Index number */ |
| int b; /* A boolean value */ |
| LogEst rSize; /* number of rows in the table */ |
| LogEst rLogSize; /* Logarithm of the number of rows in the table */ |
| WhereClause *pWC; /* The parsed WHERE clause */ |
| Table *pTab; /* Table being queried */ |
| |
| pNew = pBuilder->pNew; |
| pWInfo = pBuilder->pWInfo; |
| pTabList = pWInfo->pTabList; |
| pSrc = pTabList->a + pNew->iTab; |
| pTab = pSrc->pTab; |
| pWC = pBuilder->pWC; |
| assert( !IsVirtual(pSrc->pTab) ); |
| |
| if( pSrc->pIBIndex ){ |
| /* An INDEXED BY clause specifies a particular index to use */ |
| pProbe = pSrc->pIBIndex; |
| }else if( !HasRowid(pTab) ){ |
| pProbe = pTab->pIndex; |
| }else{ |
| /* There is no INDEXED BY clause. Create a fake Index object in local |
| ** variable sPk to represent the rowid primary key index. Make this |
| ** fake index the first in a chain of Index objects with all of the real |
| ** indices to follow */ |
| Index *pFirst; /* First of real indices on the table */ |
| memset(&sPk, 0, sizeof(Index)); |
| sPk.nKeyCol = 1; |
| sPk.nColumn = 1; |
| sPk.aiColumn = &aiColumnPk; |
| sPk.aiRowLogEst = aiRowEstPk; |
| sPk.onError = OE_Replace; |
| sPk.pTable = pTab; |
| sPk.szIdxRow = pTab->szTabRow; |
| sPk.idxType = SQLITE_IDXTYPE_IPK; |
| aiRowEstPk[0] = pTab->nRowLogEst; |
| aiRowEstPk[1] = 0; |
| pFirst = pSrc->pTab->pIndex; |
| if( pSrc->fg.notIndexed==0 ){ |
| /* The real indices of the table are only considered if the |
| ** NOT INDEXED qualifier is omitted from the FROM clause */ |
| sPk.pNext = pFirst; |
| } |
| pProbe = &sPk; |
| } |
| rSize = pTab->nRowLogEst; |
| rLogSize = estLog(rSize); |
| |
| #ifndef SQLITE_OMIT_AUTOMATIC_INDEX |
| /* Automatic indexes */ |
| if( !pBuilder->pOrSet /* Not part of an OR optimization */ |
| && (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)==0 |
| && (pWInfo->pParse->db->flags & SQLITE_AutoIndex)!=0 |
| && pSrc->pIBIndex==0 /* Has no INDEXED BY clause */ |
| && !pSrc->fg.notIndexed /* Has no NOT INDEXED clause */ |
| && HasRowid(pTab) /* Not WITHOUT ROWID table. (FIXME: Why not?) */ |
| && !pSrc->fg.isCorrelated /* Not a correlated subquery */ |
| && !pSrc->fg.isRecursive /* Not a recursive common table expression. */ |
| ){ |
| /* Generate auto-index WhereLoops */ |
| WhereTerm *pTerm; |
| WhereTerm *pWCEnd = pWC->a + pWC->nTerm; |
| for(pTerm=pWC->a; rc==SQLITE_OK && pTerm<pWCEnd; pTerm++){ |
| if( pTerm->prereqRight & pNew->maskSelf ) continue; |
| if( termCanDriveIndex(pTerm, pSrc, 0) ){ |
| pNew->u.btree.nEq = 1; |
| pNew->nSkip = 0; |
| pNew->u.btree.pIndex = 0; |
| pNew->nLTerm = 1; |
| pNew->aLTerm[0] = pTerm; |
| /* TUNING: One-time cost for computing the automatic index is |
| ** estimated to be X*N*log2(N) where N is the number of rows in |
| ** the table being indexed and where X is 7 (LogEst=28) for normal |
| ** tables or 0.5 (LogEst=-10) for views and subqueries. The value |
| ** of X is smaller for views and subqueries so that the query planner |
| ** will be more aggressive about generating automatic indexes for |
| ** those objects, since there is no opportunity to add schema |
| ** indexes on subqueries and views. */ |
| pNew->rSetup = rLogSize + rSize; |
| if( pTab->pSelect==0 && (pTab->tabFlags & TF_Ephemeral)==0 ){ |
| pNew->rSetup += 28; |
| }else{ |
| pNew->rSetup -= 10; |
| } |
| ApplyCostMultiplier(pNew->rSetup, pTab->costMult); |
| if( pNew->rSetup<0 ) pNew->rSetup = 0; |
| /* TUNING: Each index lookup yields 20 rows in the table. This |
| ** is more than the usual guess of 10 rows, since we have no way |
| ** of knowing how selective the index will ultimately be. It would |
| ** not be unreasonable to make this value much larger. */ |
| pNew->nOut = 43; assert( 43==sqlite3LogEst(20) ); |
| pNew->rRun = sqlite3LogEstAdd(rLogSize,pNew->nOut); |
| pNew->wsFlags = WHERE_AUTO_INDEX; |
| pNew->prereq = mPrereq | pTerm->prereqRight; |
| rc = whereLoopInsert(pBuilder, pNew); |
| } |
| } |
| } |
| #endif /* SQLITE_OMIT_AUTOMATIC_INDEX */ |
| |
| /* Loop over all indices. If there was an INDEXED BY clause, then only |
| ** consider index pProbe. */ |
| for(; rc==SQLITE_OK && pProbe; |
| pProbe=(pSrc->pIBIndex ? 0 : pProbe->pNext), iSortIdx++ |
| ){ |
| if( pProbe->pPartIdxWhere!=0 |
| && !whereUsablePartialIndex(pSrc->iCursor, pWC, pProbe->pPartIdxWhere) ){ |
| testcase( pNew->iTab!=pSrc->iCursor ); /* See ticket [98d973b8f5] */ |
| continue; /* Partial index inappropriate for this query */ |
| } |
| if( pProbe->bNoQuery ) continue; |
| rSize = pProbe->aiRowLogEst[0]; |
| pNew->u.btree.nEq = 0; |
| pNew->u.btree.nBtm = 0; |
| pNew->u.btree.nTop = 0; |
| pNew->nSkip = 0; |
| pNew->nLTerm = 0; |
| pNew->iSortIdx = 0; |
| pNew->rSetup = 0; |
| pNew->prereq = mPrereq; |
| pNew->nOut = rSize; |
| pNew->u.btree.pIndex = pProbe; |
| b = indexMightHelpWithOrderBy(pBuilder, pProbe, pSrc->iCursor); |
| /* The ONEPASS_DESIRED flags never occurs together with ORDER BY */ |
| assert( (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || b==0 ); |
| if( pProbe->idxType==SQLITE_IDXTYPE_IPK ){ |
| /* Integer primary key index */ |
| pNew->wsFlags = WHERE_IPK; |
| |
| /* Full table scan */ |
| pNew->iSortIdx = b ? iSortIdx : 0; |
| /* TUNING: Cost of full table scan is (N*3.0). */ |
| pNew->rRun = rSize + 16; |
| ApplyCostMultiplier(pNew->rRun, pTab->costMult); |
| whereLoopOutputAdjust(pWC, pNew, rSize); |
| rc = whereLoopInsert(pBuilder, pNew); |
| pNew->nOut = rSize; |
| if( rc ) break; |
| }else{ |
| Bitmask m; |
| if( pProbe->isCovering ){ |
| pNew->wsFlags = WHERE_IDX_ONLY | WHERE_INDEXED; |
| m = 0; |
| }else{ |
| m = pSrc->colUsed & pProbe->colNotIdxed; |
| pNew->wsFlags = (m==0) ? (WHERE_IDX_ONLY|WHERE_INDEXED) : WHERE_INDEXED; |
| } |
| |
| /* Full scan via index */ |
| if( b |
| || !HasRowid(pTab) |
| || pProbe->pPartIdxWhere!=0 |
| || ( m==0 |
| && pProbe->bUnordered==0 |
| && (pProbe->szIdxRow<pTab->szTabRow) |
| && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 |
| && sqlite3GlobalConfig.bUseCis |
| && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan) |
| ) |
| ){ |
| pNew->iSortIdx = b ? iSortIdx : 0; |
| |
| /* The cost of visiting the index rows is N*K, where K is |
| ** between 1.1 and 3.0, depending on the relative sizes of the |
| ** index and table rows. */ |
| pNew->rRun = rSize + 1 + (15*pProbe->szIdxRow)/pTab->szTabRow; |
| if( m!=0 ){ |
| /* If this is a non-covering index scan, add in the cost of |
| ** doing table lookups. The cost will be 3x the number of |
| ** lookups. Take into account WHERE clause terms that can be |
| ** satisfied using just the index, and that do not require a |
| ** table lookup. */ |
| LogEst nLookup = rSize + 16; /* Base cost: N*3 */ |
| int ii; |
| int iCur = pSrc->iCursor; |
| WhereClause *pWC2 = &pWInfo->sWC; |
| for(ii=0; ii<pWC2->nTerm; ii++){ |
| WhereTerm *pTerm = &pWC2->a[ii]; |
| if( !sqlite3ExprCoveredByIndex(pTerm->pExpr, iCur, pProbe) ){ |
| break; |
| } |
| /* pTerm can be evaluated using just the index. So reduce |
| ** the expected number of table lookups accordingly */ |
| if( pTerm->truthProb<=0 ){ |
| nLookup += pTerm->truthProb; |
| }else{ |
| nLookup--; |
| if( pTerm->eOperator & (WO_EQ|WO_IS) ) nLookup -= 19; |
| } |
| } |
| |
| pNew->rRun = sqlite3LogEstAdd(pNew->rRun, nLookup); |
| } |
| ApplyCostMultiplier(pNew->rRun, pTab->costMult); |
| whereLoopOutputAdjust(pWC, pNew, rSize); |
| rc = whereLoopInsert(pBuilder, pNew); |
| pNew->nOut = rSize; |
| if( rc ) break; |
| } |
| } |
| |
| pBuilder->bldFlags = 0; |
| rc = whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, 0); |
| if( pBuilder->bldFlags==SQLITE_BLDF_INDEXED ){ |
| /* If a non-unique index is used, or if a prefix of the key for |
| ** unique index is used (making the index functionally non-unique) |
| ** then the sqlite_stat1 data becomes important for scoring the |
| ** plan */ |
| pTab->tabFlags |= TF_StatsUsed; |
| } |
| #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 |
| sqlite3Stat4ProbeFree(pBuilder->pRec); |
| pBuilder->nRecValid = 0; |
| pBuilder->pRec = 0; |
| #endif |
| } |
| return rc; |
| } |
| |
| #ifndef SQLITE_OMIT_VIRTUALTABLE |
| |
| /* |
| ** Argument pIdxInfo is already populated with all constraints that may |
| ** be used by the virtual table identified by pBuilder->pNew->iTab. This |
| ** function marks a subset of those constraints usable, invokes the |
| ** xBestIndex method and adds the returned plan to pBuilder. |
| ** |
| ** A constraint is marked usable if: |
| ** |
| ** * Argument mUsable indicates that its prerequisites are available, and |
| ** |
| ** * It is not one of the operators specified in the mExclude mask passed |
| ** as the fourth argument (which in practice is either WO_IN or 0). |
| ** |
| ** Argument mPrereq is a mask of tables that must be scanned before the |
| ** virtual table in question. These are added to the plans prerequisites |
| ** before it is added to pBuilder. |
| ** |
| ** Output parameter *pbIn is set to true if the plan added to pBuilder |
| ** uses one or more WO_IN terms, or false otherwise. |
| */ |
| static int whereLoopAddVirtualOne( |
| WhereLoopBuilder *pBuilder, |
| Bitmask mPrereq, /* Mask of tables that must be used. */ |
| Bitmask mUsable, /* Mask of usable tables */ |
| u16 mExclude, /* Exclude terms using these operators */ |
| sqlite3_index_info *pIdxInfo, /* Populated object for xBestIndex */ |
| u16 mNoOmit, /* Do not omit these constraints */ |
| int *pbIn /* OUT: True if plan uses an IN(...) op */ |
| ){ |
| WhereClause *pWC = pBuilder->pWC; |
| struct sqlite3_index_constraint *pIdxCons; |
| struct sqlite3_index_constraint_usage *pUsage = pIdxInfo->aConstraintUsage; |
| int i; |
| int mxTerm; |
| int rc = SQLITE_OK; |
| WhereLoop *pNew = pBuilder->pNew; |
| Parse *pParse = pBuilder->pWInfo->pParse; |
| struct SrcList_item *pSrc = &pBuilder->pWInfo->pTabList->a[pNew->iTab]; |
| int nConstraint = pIdxInfo->nConstraint; |
| |
| assert( (mUsable & mPrereq)==mPrereq ); |
| *pbIn = 0; |
| pNew->prereq = mPrereq; |
| |
| /* Set the usable flag on the subset of constraints identified by |
| ** arguments mUsable and mExclude. */ |
| pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint; |
| for(i=0; i<nConstraint; i++, pIdxCons++){ |
| WhereTerm *pTerm = &pWC->a[pIdxCons->iTermOffset]; |
| pIdxCons->usable = 0; |
| if( (pTerm->prereqRight & mUsable)==pTerm->prereqRight |
| && (pTerm->eOperator & mExclude)==0 |
| ){ |
| pIdxCons->usable = 1; |
| } |
| } |
| |
| /* Initialize the output fields of the sqlite3_index_info structure */ |
| memset(pUsage, 0, sizeof(pUsage[0])*nConstraint); |
| assert( pIdxInfo->needToFreeIdxStr==0 ); |
| pIdxInfo->idxStr = 0; |
| pIdxInfo->idxNum = 0; |
| pIdxInfo->orderByConsumed = 0; |
| pIdxInfo->estimatedCost = SQLITE_BIG_DBL / (double)2; |
| pIdxInfo->estimatedRows = 25; |
| pIdxInfo->idxFlags = 0; |
| pIdxInfo->colUsed = (sqlite3_int64)pSrc->colUsed; |
| |
| /* Invoke the virtual table xBestIndex() method */ |
| rc = vtabBestIndex(pParse, pSrc->pTab, pIdxInfo); |
| if( rc ){ |
| if( rc==SQLITE_CONSTRAINT ){ |
| /* If the xBestIndex method returns SQLITE_CONSTRAINT, that means |
| ** that the particular combination of parameters provided is unusable. |
| ** Make no entries in the loop table. |
| */ |
| WHERETRACE(0xffff, (" ^^^^--- non-viable plan rejected!\n")); |
| return SQLITE_OK; |
| } |
| return rc; |
| } |
| |
| mxTerm = -1; |
| assert( pNew->nLSlot>=nConstraint ); |
| for(i=0; i<nConstraint; i++) pNew->aLTerm[i] = 0; |
| pNew->u.vtab.omitMask = 0; |
| pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint; |
| for(i=0; i<nConstraint; i++, pIdxCons++){ |
| int iTerm; |
| if( (iTerm = pUsage[i].argvIndex - 1)>=0 ){ |
| WhereTerm *pTerm; |
| int j = pIdxCons->iTermOffset; |
| if( iTerm>=nConstraint |
| || j<0 |
| || j>=pWC->nTerm |
| || pNew->aLTerm[iTerm]!=0 |
| || pIdxCons->usable==0 |
| ){ |
| sqlite3ErrorMsg(pParse,"%s.xBestIndex malfunction",pSrc->pTab->zName); |
| testcase( pIdxInfo->needToFreeIdxStr ); |
| return SQLITE_ERROR; |
| } |
| testcase( iTerm==nConstraint-1 ); |
| testcase( j==0 ); |
| testcase( j==pWC->nTerm-1 ); |
| pTerm = &pWC->a[j]; |
| pNew->prereq |= pTerm->prereqRight; |
| assert( iTerm<pNew->nLSlot ); |
| pNew->aLTerm[iTerm] = pTerm; |
| if( iTerm>mxTerm ) mxTerm = iTerm; |
| testcase( iTerm==15 ); |
| testcase( iTerm==16 ); |
| if( iTerm<16 && pUsage[i].omit ) pNew->u.vtab.omitMask |= 1<<iTerm; |
| if( (pTerm->eOperator & WO_IN)!=0 ){ |
| /* A virtual table that is constrained by an IN clause may not |
| ** consume the ORDER BY clause because (1) the order of IN terms |
| ** is not necessarily related to the order of output terms and |
| ** (2) Multiple outputs from a single IN value will not merge |
| ** together. */ |
| pIdxInfo->orderByConsumed = 0; |
| pIdxInfo->idxFlags &= ~SQLITE_INDEX_SCAN_UNIQUE; |
| *pbIn = 1; assert( (mExclude & WO_IN)==0 ); |
| } |
| } |
| } |
| pNew->u.vtab.omitMask &= ~mNoOmit; |
| |
| pNew->nLTerm = mxTerm+1; |
| for(i=0; i<=mxTerm; i++){ |
| if( pNew->aLTerm[i]==0 ){ |
| /* The non-zero argvIdx values must be contiguous. Raise an |
| ** error if they are not */ |
| sqlite3ErrorMsg(pParse,"%s.xBestIndex malfunction",pSrc->pTab->zName); |
| testcase( pIdxInfo->needToFreeIdxStr ); |
| return SQLITE_ERROR; |
| } |
| } |
| assert( pNew->nLTerm<=pNew->nLSlot ); |
| pNew->u.vtab.idxNum = pIdxInfo->idxNum; |
| pNew->u.vtab.needFree = pIdxInfo->needToFreeIdxStr; |
| pIdxInfo->needToFreeIdxStr = 0; |
| pNew->u.vtab.idxStr = pIdxInfo->idxStr; |
| pNew->u.vtab.isOrdered = (i8)(pIdxInfo->orderByConsumed ? |
| pIdxInfo->nOrderBy : 0); |
| pNew->rSetup = 0; |
| pNew->rRun = sqlite3LogEstFromDouble(pIdxInfo->estimatedCost); |
| pNew->nOut = sqlite3LogEst(pIdxInfo->estimatedRows); |
| |
| /* Set the WHERE_ONEROW flag if the xBestIndex() method indicated |
| ** that the scan will visit at most one row. Clear it otherwise. */ |
| if( pIdxInfo->idxFlags & SQLITE_INDEX_SCAN_UNIQUE ){ |
| pNew->wsFlags |= WHERE_ONEROW; |
| }else{ |
| pNew->wsFlags &= ~WHERE_ONEROW; |
| } |
| rc = whereLoopInsert(pBuilder, pNew); |
| if( pNew->u.vtab.needFree ){ |
| sqlite3_free(pNew->u.vtab.idxStr); |
| pNew->u.vtab.needFree = 0; |
| } |
| WHERETRACE(0xffff, (" bIn=%d prereqIn=%04llx prereqOut=%04llx\n", |
| *pbIn, (sqlite3_uint64)mPrereq, |
| (sqlite3_uint64)(pNew->prereq & ~mPrereq))); |
| |
| return rc; |
| } |
| |
| /* |
| ** If this function is invoked from within an xBestIndex() callback, it |
| ** returns a pointer to a buffer containing the name of the collation |
| ** sequence associated with element iCons of the sqlite3_index_info.aConstraint |
| ** array. Or, if iCons is out of range or there is no active xBestIndex |
| ** call, return NULL. |
| */ |
| const char *sqlite3_vtab_collation(sqlite3_index_info *pIdxInfo, int iCons){ |
| HiddenIndexInfo *pHidden = (HiddenIndexInfo*)&pIdxInfo[1]; |
| const char *zRet = 0; |
| if( iCons>=0 && iCons<pIdxInfo->nConstraint ){ |
| CollSeq *pC = 0; |
| int iTerm = pIdxInfo->aConstraint[iCons].iTermOffset; |
| Expr *pX = pHidden->pWC->a[iTerm].pExpr; |
| if( pX->pLeft ){ |
| pC = sqlite3BinaryCompareCollSeq(pHidden->pParse, pX->pLeft, pX->pRight); |
| } |
| zRet = (pC ? pC->zName : sqlite3StrBINARY); |
| } |
| return zRet; |
| } |
| |
| /* |
| ** Add all WhereLoop objects for a table of the join identified by |
| ** pBuilder->pNew->iTab. That table is guaranteed to be a virtual table. |
| ** |
| ** If there are no LEFT or CROSS JOIN joins in the query, both mPrereq and |
| ** mUnusable are set to 0. Otherwise, mPrereq is a mask of all FROM clause |
| ** entries that occur before the virtual table in the FROM clause and are |
| ** separated from it by at least one LEFT or CROSS JOIN. Similarly, the |
| ** mUnusable mask contains all FROM clause entries that occur after the |
| ** virtual table and are separated from it by at least one LEFT or |
| ** CROSS JOIN. |
| ** |
| ** For example, if the query were: |
| ** |
| ** ... FROM t1, t2 LEFT JOIN t3, t4, vt CROSS JOIN t5, t6; |
| ** |
| ** then mPrereq corresponds to (t1, t2) and mUnusable to (t5, t6). |
| ** |
| ** All the tables in mPrereq must be scanned before the current virtual |
| ** table. So any terms for which all prerequisites are satisfied by |
| ** mPrereq may be specified as "usable" in all calls to xBestIndex. |
| ** Conversely, all tables in mUnusable must be scanned after the current |
| ** virtual table, so any terms for which the prerequisites overlap with |
| ** mUnusable should always be configured as "not-usable" for xBestIndex. |
| */ |
| static int whereLoopAddVirtual( |
| WhereLoopBuilder *pBuilder, /* WHERE clause information */ |
| Bitmask mPrereq, /* Tables that must be scanned before this one */ |
| Bitmask mUnusable /* Tables that must be scanned after this one */ |
| ){ |
| int rc = SQLITE_OK; /* Return code */ |
| WhereInfo *pWInfo; /* WHERE analysis context */ |
| Parse *pParse; /* The parsing context */ |
| WhereClause *pWC; /* The WHERE clause */ |
| struct SrcList_item *pSrc; /* The FROM clause term to search */ |
| sqlite3_index_info *p; /* Object to pass to xBestIndex() */ |
| int nConstraint; /* Number of constraints in p */ |
| int bIn; /* True if plan uses IN(...) operator */ |
| WhereLoop *pNew; |
| Bitmask mBest; /* Tables used by best possible plan */ |
| u16 mNoOmit; |
| |
| assert( (mPrereq & mUnusable)==0 ); |
| pWInfo = pBuilder->pWInfo; |
| pParse = pWInfo->pParse; |
| pWC = pBuilder->pWC; |
| pNew = pBuilder->pNew; |
| pSrc = &pWInfo->pTabList->a[pNew->iTab]; |
| assert( IsVirtual(pSrc->pTab) ); |
| p = allocateIndexInfo(pParse, pWC, mUnusable, pSrc, pBuilder->pOrderBy, |
| &mNoOmit); |
| if( p==0 ) return SQLITE_NOMEM_BKPT; |
| pNew->rSetup = 0; |
| pNew->wsFlags = WHERE_VIRTUALTABLE; |
| pNew->nLTerm = 0; |
| pNew->u.vtab.needFree = 0; |
| nConstraint = p->nConstraint; |
| if( whereLoopResize(pParse->db, pNew, nConstraint) ){ |
| sqlite3DbFree(pParse->db, p); |
| return SQLITE_NOMEM_BKPT; |
| } |
| |
| /* First call xBestIndex() with all constraints usable. */ |
| WHERETRACE(0x800, ("BEGIN %s.addVirtual()\n", pSrc->pTab->zName)); |
| WHERETRACE(0x40, (" VirtualOne: all usable\n")); |
| rc = whereLoopAddVirtualOne(pBuilder, mPrereq, ALLBITS, 0, p, mNoOmit, &bIn); |
| |
| /* If the call to xBestIndex() with all terms enabled produced a plan |
| ** that does not require any source tables (IOW: a plan with mBest==0), |
| ** then there is no point in making any further calls to xBestIndex() |
| ** since they will all return the same result (if the xBestIndex() |
| ** implementation is sane). */ |
| if( rc==SQLITE_OK && (mBest = (pNew->prereq & ~mPrereq))!=0 ){ |
| int seenZero = 0; /* True if a plan with no prereqs seen */ |
| int seenZeroNoIN = 0; /* Plan with no prereqs and no IN(...) seen */ |
| Bitmask mPrev = 0; |
| Bitmask mBestNoIn = 0; |
| |
| /* 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")); |
| rc = whereLoopAddVirtualOne( |
| pBuilder, mPrereq, ALLBITS, WO_IN, p, mNoOmit, &bIn); |
| assert( bIn==0 ); |
| mBestNoIn = pNew->prereq & ~mPrereq; |
| if( mBestNoIn==0 ){ |
| seenZero = 1; |
| seenZeroNoIN = 1; |
| } |
| } |
| |
| /* Call xBestIndex once for each distinct value of (prereqRight & ~mPrereq) |
| ** in the set of terms that apply to the current virtual table. */ |
| while( rc==SQLITE_OK ){ |
| int i; |
| Bitmask mNext = ALLBITS; |
| assert( mNext>0 ); |
| for(i=0; i<nConstraint; i++){ |
| Bitmask mThis = ( |
| pWC->a[p->aConstraint[i].iTermOffset].prereqRight & ~mPrereq |
| ); |
| if( mThis>mPrev && mThis<mNext ) mNext = mThis; |
| } |
| mPrev = mNext; |
| if( mNext==ALLBITS ) break; |
| if( mNext==mBest || mNext==mBestNoIn ) continue; |
| WHERETRACE(0x40, (" VirtualOne: mPrev=%04llx mNext=%04llx\n", |
| (sqlite3_uint64)mPrev, (sqlite3_uint64)mNext)); |
| rc = whereLoopAddVirtualOne( |
| pBuilder, mPrereq, mNext|mPrereq, 0, p, mNoOmit, &bIn); |
| if( pNew->prereq==mPrereq ){ |
| seenZero = 1; |
| if( bIn==0 ) seenZeroNoIN = 1; |
| } |
| } |
| |
| /* If the calls to xBestIndex() in the above loop did not find a plan |
| ** 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")); |
| rc = whereLoopAddVirtualOne( |
| pBuilder, mPrereq, mPrereq, 0, p, mNoOmit, &bIn); |
| if( bIn==0 ) seenZeroNoIN = 1; |
| } |
| |
| /* If the calls to xBestIndex() have so far failed to find a plan |
| ** 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")); |
| rc = whereLoopAddVirtualOne( |
| pBuilder, mPrereq, mPrereq, WO_IN, p, mNoOmit, &bIn); |
| } |
| } |
| |
| if( p->needToFreeIdxStr ) sqlite3_free(p->idxStr); |
| sqlite3DbFreeNN(pParse->db, p); |
| WHERETRACE(0x800, ("END %s.addVirtual(), rc=%d\n", pSrc->pTab->zName, rc)); |
| return rc; |
| } |
| #endif /* SQLITE_OMIT_VIRTUALTABLE */ |
| |
| /* |
| ** Add WhereLoop entries to handle OR terms. This works for either |
| ** btrees or virtual tables. |
| */ |
| static int whereLoopAddOr( |
| WhereLoopBuilder *pBuilder, |
| Bitmask mPrereq, |
| Bitmask mUnusable |
| ){ |
| WhereInfo *pWInfo = pBuilder->pWInfo; |
| WhereClause *pWC; |
| WhereLoop *pNew; |
| WhereTerm *pTerm, *pWCEnd; |
| int rc = SQLITE_OK; |
| int iCur; |
| WhereClause tempWC; |
| WhereLoopBuilder sSubBuild; |
| WhereOrSet sSum, sCur; |
| struct SrcList_item *pItem; |
| |
| pWC = pBuilder->pWC; |
| pWCEnd = pWC->a + pWC->nTerm; |
| pNew = pBuilder->pNew; |
| memset(&sSum, 0, sizeof(sSum)); |
| pItem = pWInfo->pTabList->a + pNew->iTab; |
| iCur = pItem->iCursor; |
| |
| for(pTerm=pWC->a; pTerm<pWCEnd && rc==SQLITE_OK; pTerm++){ |
| if( (pTerm->eOperator & 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; |
| int once = 1; |
| int i, j; |
| |
| sSubBuild = *pBuilder; |
| sSubBuild.pOrderBy = 0; |
| sSubBuild.pOrSet = &sCur; |
| |
| WHERETRACE(0x200, ("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; |
| }else if( pOrTerm->leftCursor==iCur ){ |
| tempWC.pWInfo = pWC->pWInfo; |
| tempWC.pOuter = pWC; |
| tempWC.op = TK_AND; |
| tempWC.nTerm = 1; |
| tempWC.a = pOrTerm; |
| sSubBuild.pWC = &tempWC; |
| }else{ |
| continue; |
| } |
| sCur.n = 0; |
| #ifdef WHERETRACE_ENABLED |
| WHERETRACE(0x200, ("OR-term %d of %p has %d subterms:\n", |
| (int)(pOrTerm-pOrWC->a), pTerm, sSubBuild.pWC->nTerm)); |
| if( sqlite3WhereTrace & 0x400 ){ |
| sqlite3WhereClausePrint(sSubBuild.pWC); |
| } |
| #endif |
| #ifndef SQLITE_OMIT_VIRTUALTABLE |
| if( IsVirtual(pItem->pTab) ){ |
| rc = whereLoopAddVirtual(&sSubBuild, mPrereq, mUnusable); |
| }else |
| #endif |
| { |
| rc = whereLoopAddBtree(&sSubBuild, mPrereq); |
| } |
| if( rc==SQLITE_OK ){ |
| rc = whereLoopAddOr(&sSubBuild, mPrereq, mUnusable); |
| } |
| assert( rc==SQLITE_OK || sCur.n==0 ); |
| if( sCur.n==0 ){ |
| sSum.n = 0; |
| break; |
| }else if( once ){ |
| whereOrMove(&sSum, &sCur); |
| once = 0; |
| }else{ |
| WhereOrSet sPrev; |
| 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, |
| sqlite3LogEstAdd(sPrev.a[i].rRun, sCur.a[j].rRun), |
| sqlite3LogEstAdd(sPrev.a[i].nOut, sCur.a[j].nOut)); |
| } |
| } |
| } |
| } |
| 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: Currently sSum.a[i].rRun is set to the sum of the costs |
| ** of all sub-scans required by the OR-scan. However, due to rounding |
| ** errors, it may be that the cost of the OR-scan is equal to its |
| ** most expensive sub-scan. Add the smallest possible penalty |
| ** (equivalent to multiplying the cost by 1.07) to ensure that |
| ** this does not happen. Otherwise, for WHERE clauses such as the |
| ** following where there is an index on "y": |
| ** |
| ** WHERE likelihood(x=?, 0.99) OR y=? |
| ** |
| ** the planner may elect to "OR" together a full-table scan and an |
| ** index lookup. And other similarly odd results. */ |
| pNew->rRun = sSum.a[i].rRun + 1; |
| pNew->nOut = sSum.a[i].nOut; |
| pNew->prereq = sSum.a[i].prereq; |
| rc = whereLoopInsert(pBuilder, pNew); |
| } |
| WHERETRACE(0x200, ("End processing OR-clause %p\n", pTerm)); |
| } |
| } |
| return rc; |
| } |
| |
| /* |
| ** Add all WhereLoop objects for all tables |
| */ |
| static int whereLoopAddAll(WhereLoopBuilder *pBuilder){ |
| WhereInfo *pWInfo = pBuilder->pWInfo; |
| Bitmask mPrereq = 0; |
| Bitmask mPrior = 0; |
| int iTab; |
| SrcList *pTabList = pWInfo->pTabList; |
| struct SrcList_item *pItem; |
| struct SrcList_item *pEnd = &pTabList->a[pWInfo->nLevel]; |
| sqlite3 *db = pWInfo->pParse->db; |
| int rc = SQLITE_OK; |
| WhereLoop *pNew; |
| u8 priorJointype = 0; |
| |
| /* Loop over the tables in the join, from left to right */ |
| pNew = pBuilder->pNew; |
| whereLoopInit(pNew); |
| pBuilder->iPlanLimit = SQLITE_QUERY_PLANNER_LIMIT; |
| for(iTab=0, pItem=pTabList->a; pItem<pEnd; iTab++, pItem++){ |
| Bitmask mUnusable = 0; |
| pNew->iTab = iTab; |
| pBuilder->iPlanLimit += SQLITE_QUERY_PLANNER_LIMIT_INCR; |
| pNew->maskSelf = sqlite3WhereGetMask(&pWInfo->sMaskSet, pItem->iCursor); |
| if( ((pItem->fg.jointype|priorJointype) & (JT_LEFT|JT_CROSS))!=0 ){ |
| /* This condition is true when pItem is the FROM clause term on the |
| ** right-hand-side of a LEFT or CROSS JOIN. */ |
| mPrereq = mPrior; |
| } |
| priorJointype = pItem->fg.jointype; |
| #ifndef SQLITE_OMIT_VIRTUALTABLE |
| if( IsVirtual(pItem->pTab) ){ |
| struct SrcList_item *p; |
| for(p=&pItem[1]; p<pEnd; p++){ |
| if( mUnusable || (p->fg.jointype & (JT_LEFT|JT_CROSS)) ){ |
| mUnusable |= sqlite3WhereGetMask(&pWInfo->sMaskSet, p->iCursor); |
| } |
| } |
| rc = whereLoopAddVirtual(pBuilder, mPrereq, mUnusable); |
| }else |
| #endif /* SQLITE_OMIT_VIRTUALTABLE */ |
| { |
| rc = whereLoopAddBtree(pBuilder, mPrereq); |
| } |
| if( rc==SQLITE_OK && pBuilder->pWC->hasOr ){ |
| rc = whereLoopAddOr(pBuilder, mPrereq, mUnusable); |
| } |
| mPrior |= pNew->maskSelf; |
| if( rc || db->mallocFailed ){ |
| if( rc==SQLITE_DONE ){ |
| /* We hit the query planner search limit set by iPlanLimit */ |
| sqlite3_log(SQLITE_WARNING, "abbreviated query algorithm search"); |
| rc = SQLITE_OK; |
| }else{ |
| break; |
| } |
| } |
| } |
| |
| whereLoopClear(db, pNew); |
| return rc; |
| } |
| |
| /* |
| ** Examine a WherePath (with the addition of the extra WhereLoop of the 6th |
| ** parameters) to see if it outputs rows in the requested ORDER BY |
| ** (or GROUP BY) without requiring a separate sort operation. Return N: |
| ** |
| ** N>0: N terms of the ORDER BY clause are satisfied |
| ** N==0: No terms of the ORDER BY clause are satisfied |
| ** N<0: Unknown yet how many terms of ORDER BY might be satisfied. |
| ** |
| ** Note that processing for WHERE_GROUPBY and WHERE_DISTINCTBY is not as |
| ** strict. With GROUP BY and DISTINCT the only requirement is that |
| ** equivalent rows appear immediately adjacent to one another. GROUP BY |
| ** and DISTINCT do not require rows to appear in any particular order as long |
| ** as equivalent rows are grouped together. Thus for GROUP BY and DISTINCT |
| ** the pOrderBy terms can be matched in any order. With ORDER BY, the |
| ** pOrderBy terms must be matched in strict left-to-right order. |
| */ |
| static i8 wherePathSatisfiesOrderBy( |
| WhereInfo *pWInfo, /* The WHERE clause */ |
| ExprList *pOrderBy, /* ORDER BY or GROUP BY or DISTINCT clause to check */ |
| WherePath *pPath, /* The WherePath to check */ |
| u16 wctrlFlags, /* WHERE_GROUPBY or _DISTINCTBY or _ORDERBY_LIMIT */ |
| u16 nLoop, /* Number of entries in pPath->aLoop[] */ |
| WhereLoop *pLast, /* Add this WhereLoop to the end of pPath->aLoop[] */ |
| Bitmask *pRevMask /* OUT: Mask of WhereLoops to run in reverse order */ |
| ){ |
| u8 revSet; /* True if rev is known */ |
| u8 rev; /* Composite sort order */ |
| u8 revIdx; /* Index sort order */ |
| u8 isOrderDistinct; /* All prior WhereLoops are order-distinct */ |
| u8 distinctColumns; /* True if the loop has UNIQUE NOT NULL columns */ |
| u8 isMatch; /* iColumn matches a term of the ORDER BY clause */ |
| u16 eqOpMask; /* Allowed equality operators */ |
| u16 nKeyCol; /* Number of key columns in pIndex */ |
| u16 nColumn; /* Total number of ordered columns in the index */ |
| u16 nOrderBy; /* Number terms in the ORDER BY clause */ |
| int iLoop; /* Index of WhereLoop in pPath being processed */ |
| int i, j; /* Loop counters */ |
| int iCur; /* Cursor number for current WhereLoop */ |
| int iColumn; /* A column number within table iCur */ |
| WhereLoop *pLoop = 0; /* Current WhereLoop being processed. */ |
| WhereTerm *pTerm; /* A single term of the WHERE clause */ |
| Expr *pOBExpr; /* An expression from the ORDER BY clause */ |
| CollSeq *pColl; /* COLLATE function from an ORDER BY clause term */ |
| Index *pIndex; /* The index associated with pLoop */ |
| sqlite3 *db = pWInfo->pParse->db; /* Database connection */ |
| Bitmask obSat = 0; /* Mask of ORDER BY terms satisfied so far */ |
| Bitmask obDone; /* Mask of all ORDER BY terms */ |
| Bitmask orderDistinctMask; /* Mask of all well-ordered loops */ |
| Bitmask ready; /* Mask of inner loops */ |
| |
| /* |
| ** We say the WhereLoop is "one-row" if it generates no more than one |
| ** row of output. A WhereLoop is one-row if all of the following are true: |
| ** (a) All index columns match with WHERE_COLUMN_EQ. |
| ** (b) The index is unique |
| ** Any WhereLoop with an WHERE_COLUMN_EQ constraint on the rowid is one-row. |
| ** Every one-row WhereLoop will have the WHERE_ONEROW bit set in wsFlags. |
| ** |
| ** We say the WhereLoop is "order-distinct" if the set of columns from |
| ** that WhereLoop that are in the ORDER BY clause are different for every |
| ** row of the WhereLoop. Every one-row WhereLoop is automatically |
| ** order-distinct. A WhereLoop that has no columns in the ORDER BY clause |
| ** is not order-distinct. To be order-distinct is not quite the same as being |
| ** UNIQUE since a UNIQUE column or index can have multiple rows that |
| ** are NULL and NULL values are equivalent for the purpose of order-distinct. |
| ** To be order-distinct, the columns must be UNIQUE and NOT NULL. |
| ** |
| ** The rowid for a table is always UNIQUE and NOT NULL so whenever the |
| ** rowid appears in the ORDER BY clause, the corresponding WhereLoop is |
| ** automatically order-distinct. |
| */ |
| |
| assert( pOrderBy!=0 ); |
| if( nLoop && OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ) return 0; |
| |
| nOrderBy = pOrderBy->nExpr; |
| testcase( nOrderBy==BMS-1 ); |
| if( nOrderBy>BMS-1 ) return 0; /* Cannot optimize overly large ORDER BYs */ |
| isOrderDistinct = 1; |
| obDone = MASKBIT(nOrderBy)-1; |
| orderDistinctMask = 0; |
| ready = 0; |
| eqOpMask = WO_EQ | WO_IS | WO_ISNULL; |
| if( wctrlFlags & WHERE_ORDERBY_LIMIT ) eqOpMask |= WO_IN; |
| for(iLoop=0; isOrderDistinct && obSat<obDone && iLoop<=nLoop; iLoop++){ |
| if( iLoop>0 ) ready |= pLoop->maskSelf; |
| if( iLoop<nLoop ){ |
| pLoop = pPath->aLoop[iLoop]; |
| if( wctrlFlags & WHERE_ORDERBY_LIMIT ) continue; |
| }else{ |
| pLoop = pLast; |
| } |
| if( pLoop->wsFlags & WHERE_VIRTUALTABLE ){ |
| if( pLoop->u.vtab.isOrdered ) obSat = obDone; |
| break; |
| }else{ |
| pLoop->u.btree.nIdxCol = 0; |
| } |
| iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor; |
| |
| /* Mark off any ORDER BY term X that is a column in the table of |
| ** the current loop for which there is term in the WHERE |
| ** clause of the form X IS NULL or X=? that reference only outer |
| ** loops. |
| */ |
| for(i=0; i<nOrderBy; i++){ |
| if( MASKBIT(i) & obSat ) continue; |
| pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr); |
| if( pOBExpr->op!=TK_COLUMN ) continue; |
| if( pOBExpr->iTable!=iCur ) continue; |
| pTerm = sqlite3WhereFindTerm(&pWInfo->sWC, iCur, pOBExpr->iColumn, |
| ~ready, eqOpMask, 0); |
| if( pTerm==0 ) continue; |
| if( pTerm->eOperator==WO_IN ){ |
| /* IN terms are only valid for sorting in the ORDER BY LIMIT |
| ** optimization, and then only if they are actually used |
| ** by the query plan */ |
| assert( wctrlFlags & WHERE_ORDERBY_LIMIT ); |
| for(j=0; j<pLoop->nLTerm && pTerm!=pLoop->aLTerm[j]; j++){} |
| if( j>=pLoop->nLTerm ) continue; |
| } |
| if( (pTerm->eOperator&(WO_EQ|WO_IS))!=0 && pOBExpr->iColumn>=0 ){ |
| if( sqlite3ExprCollSeqMatch(pWInfo->pParse, |
| pOrderBy->a[i].pExpr, pTerm->pExpr)==0 ){ |
| continue; |
| } |
| testcase( pTerm->pExpr->op==TK_IS ); |
| } |
| obSat |= MASKBIT(i); |
| } |
| |
| if( (pLoop->wsFlags & WHERE_ONEROW)==0 ){ |
| if( pLoop->wsFlags & WHERE_IPK ){ |
| pIndex = 0; |
| nKeyCol = 0; |
| nColumn = 1; |
| }else if( (pIndex = pLoop->u.btree.pIndex)==0 || pIndex->bUnordered ){ |
| return 0; |
| }else{ |
| nKeyCol = pIndex->nKeyCol; |
| nColumn = pIndex->nColumn; |
| assert( nColumn==nKeyCol+1 || !HasRowid(pIndex->pTable) ); |
| assert( pIndex->aiColumn[nColumn-1]==XN_ROWID |
| || !HasRowid(pIndex->pTable)); |
| isOrderDistinct = IsUniqueIndex(pIndex); |
| } |
| |
| /* Loop through all columns of the index and deal with the ones |
| ** that are not constrained by == or IN. |
| */ |
| rev = revSet = 0; |
| distinctColumns = 0; |
| for(j=0; j<nColumn; j++){ |
| u8 bOnce = 1; /* True to run the ORDER BY search loop */ |
| |
| assert( j>=pLoop->u.btree.nEq |
| || (pLoop->aLTerm[j]==0)==(j<pLoop->nSkip) |
| ); |
| if( j<pLoop->u.btree.nEq && j>=pLoop->nSkip ){ |
| u16 eOp = pLoop->aLTerm[j]->eOperator; |
| |
| /* Skip over == and IS and ISNULL terms. (Also skip IN terms when |
| ** doing WHERE_ORDERBY_LIMIT processing). |
| ** |
| ** If the current term is a column of an ((?,?) IN (SELECT...)) |
| ** expression for which the SELECT returns more than one column, |
| ** check that it is the only column used by this loop. Otherwise, |
| ** if it is one of two or more, none of the columns can be |
| ** considered to match an ORDER BY term. */ |
| if( (eOp & eqOpMask)!=0 ){ |
| if( eOp & WO_ISNULL ){ |
| testcase( isOrderDistinct ); |
| isOrderDistinct = 0; |
| } |
| continue; |
| }else if( ALWAYS(eOp & WO_IN) ){ |
| /* ALWAYS() justification: eOp is an equality operator due to the |
| ** j<pLoop->u.btree.nEq constraint above. Any equality other |
| ** than WO_IN is captured by the previous "if". So this one |
| ** always has to be WO_IN. */ |
| Expr *pX = pLoop->aLTerm[j]->pExpr; |
| for(i=j+1; i<pLoop->u.btree.nEq; i++){ |
| if( pLoop->aLTerm[i]->pExpr==pX ){ |
| assert( (pLoop->aLTerm[i]->eOperator & WO_IN) ); |
| bOnce = 0; |
| break; |
| } |
| } |
| } |
| } |
| |
| /* Get the column number in the table (iColumn) and sort order |
| ** (revIdx) for the j-th column of the index. |
| */ |
| if( pIndex ){ |
| iColumn = pIndex->aiColumn[j]; |
| revIdx = pIndex->aSortOrder[j]; |
| if( iColumn==pIndex->pTable->iPKey ) iColumn = XN_ROWID; |
| }else{ |
| iColumn = XN_ROWID; |
| revIdx = 0; |
| } |
| |
| /* An unconstrained column that might be NULL means that this |
| ** WhereLoop is not well-ordered |
| */ |
| if( isOrderDistinct |
| && iColumn>=0 |
| && j>=pLoop->u.btree.nEq |
| && pIndex->pTable->aCol[iColumn].notNull==0 |
| ){ |
| isOrderDistinct = 0; |
| } |
| |
| /* Find the ORDER BY term that corresponds to the j-th column |
| ** of the index and mark that ORDER BY term off |
| */ |
| isMatch = 0; |
| for(i=0; bOnce && i<nOrderBy; i++){ |
| if( MASKBIT(i) & obSat ) continue; |
| pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr); |
| testcase( wctrlFlags & WHERE_GROUPBY ); |
| testcase( wctrlFlags & WHERE_DISTINCTBY ); |
| if( (wctrlFlags & (WHERE_GROUPBY|WHERE_DISTINCTBY))==0 ) bOnce = 0; |
| if( iColumn>=XN_ROWID ){ |
| if( pOBExpr->op!=TK_COLUMN ) continue; |
| if( pOBExpr->iTable!=iCur ) continue; |
| if( pOBExpr->iColumn!=iColumn ) continue; |
| }else{ |
| Expr *pIdxExpr = pIndex->aColExpr->a[j].pExpr; |
| if( sqlite3ExprCompareSkip(pOBExpr, pIdxExpr, iCur) ){ |
| continue; |
| } |
| } |
| if( iColumn!=XN_ROWID ){ |
| pColl = sqlite3ExprNNCollSeq(pWInfo->pParse, pOrderBy->a[i].pExpr); |
| if( sqlite3StrICmp(pColl->zName, pIndex->azColl[j])!=0 ) continue; |
| } |
| pLoop->u.btree.nIdxCol = j+1; |
| isMatch = 1; |
| break; |
| } |
| if( isMatch && (wctrlFlags & WHERE_GROUPBY)==0 ){ |
| /* Make sure the sort order is compatible in an ORDER BY clause. |
| ** Sort order is irrelevant for a GROUP BY clause. */ |
| if( revSet ){ |
| if( (rev ^ revIdx)!=pOrderBy->a[i].sortOrder ) isMatch = 0; |
| }else{ |
| rev = revIdx ^ pOrderBy->a[i].sortOrder; |
| if( rev ) *pRevMask |= MASKBIT(iLoop); |
| revSet = 1; |
| } |
| } |
| if( isMatch ){ |
| if( iColumn==XN_ROWID ){ |
| testcase( distinctColumns==0 ); |
| distinctColumns = 1; |
| } |
| obSat |= MASKBIT(i); |
| }else{ |
| /* No match found */ |
| if( j==0 || j<nKeyCol ){ |
| testcase( isOrderDistinct!=0 ); |
| isOrderDistinct = 0; |
| } |
| break; |
| } |
| } /* end Loop over all index columns */ |
| if( distinctColumns ){ |
| testcase( isOrderDistinct==0 ); |
| isOrderDistinct = 1; |
| } |
| } /* end-if not one-row */ |
| |
| /* Mark off any other ORDER BY terms that reference pLoop */ |
| if( isOrderDistinct ){ |
| orderDistinctMask |= pLoop->maskSelf; |
| for(i=0; i<nOrderBy; i++){ |
| Expr *p; |
| Bitmask mTerm; |
| if( MASKBIT(i) & obSat ) continue; |
| p = pOrderBy->a[i].pExpr; |
| mTerm = sqlite3WhereExprUsage(&pWInfo->sMaskSet,p); |
| if( mTerm==0 && !sqlite3ExprIsConstant(p) ) continue; |
| if( (mTerm&~orderDistinctMask)==0 ){ |
| obSat |= MASKBIT(i); |
| } |
| } |
| } |
| } /* End the loop over all WhereLoops from outer-most down to inner-most */ |
| if( obSat==obDone ) return (i8)nOrderBy; |
| if( !isOrderDistinct ){ |
| for(i=nOrderBy-1; i>0; i--){ |
| Bitmask m = MASKBIT(i) - 1; |
| if( (obSat&m)==m ) return i; |
| } |
| return 0; |
| } |
| return -1; |
| } |
| |
| |
| /* |
| ** If the WHERE_GROUPBY flag is set in the mask passed to sqlite3WhereBegin(), |
| ** the planner assumes that the specified pOrderBy list is actually a GROUP |
| ** BY clause - and so any order that groups rows as required satisfies the |
| ** request. |
| ** |
| ** Normally, in this case it is not possible for the caller to determine |
| ** whether or not the rows are really being delivered in sorted order, or |
| ** just in some other order that provides the required grouping. However, |
| ** if the WHERE_SORTBYGROUP flag is also passed to sqlite3WhereBegin(), then |
| ** this function may be called on the returned WhereInfo object. It returns |
| ** true if the rows really will be sorted in the specified order, or false |
| ** otherwise. |
| ** |
| ** For example, assuming: |
| ** |
| ** CREATE INDEX i1 ON t1(x, Y); |
| ** |
| ** then |
| ** |
| ** SELECT * FROM t1 GROUP BY x,y ORDER BY x,y; -- IsSorted()==1 |
| ** SELECT * FROM t1 GROUP BY y,x ORDER BY y,x; -- IsSorted()==0 |
| */ |
| int sqlite3WhereIsSorted(WhereInfo *pWInfo){ |
| assert( pWInfo->wctrlFlags & WHERE_GROUPBY ); |
| assert( pWInfo->wctrlFlags & WHERE_SORTBYGROUP ); |
| return pWInfo->sorted; |
| } |
| |
| #ifdef WHERETRACE_ENABLED |
| /* For debugging use only: */ |
| static const char *wherePathName(WherePath *pPath, int nLoop, WhereLoop *pLast){ |
| static char zName[65]; |
| int i; |
| for(i=0; i<nLoop; i++){ zName[i] = pPath->aLoop[i]->cId; } |
| if( pLast ) zName[i++] = pLast->cId; |
| zName[i] = 0; |
| return zName; |
| } |
| #endif |
| |
| /* |
| ** Return the cost of sorting nRow rows, assuming that the keys have |
| ** nOrderby columns and that the first nSorted columns are already in |
| ** order. |
| */ |
| static LogEst whereSortingCost( |
| WhereInfo *pWInfo, |
| LogEst nRow, |
| int nOrderBy, |
| int nSorted |
| ){ |
| /* TUNING: Estimated cost of a full external sort, where N is |
| ** the number of rows to sort is: |
| ** |
| ** cost = (3.0 * 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) |
| ** |
| ** The (Y/X) term is implemented using stack variable rScale |
| ** below. */ |
| LogEst rScale, rSortCost; |
| assert( nOrderBy>0 && 66==sqlite3LogEst(100) ); |
| rScale = sqlite3LogEst((nOrderBy-nSorted)*100/nOrderBy) - 66; |
| rSortCost = nRow + rScale + 16; |
| |
| /* Multiple by log(M) where M is the number of output rows. |
| ** Use the LIMIT for M if it is smaller */ |
| if( (pWInfo->wctrlFlags & WHERE_USE_LIMIT)!=0 && pWInfo->iLimit<nRow ){ |
| nRow = pWInfo->iLimit; |
| } |
| rSortCost += estLog(nRow); |
| return rSortCost; |
| } |
| |
| /* |
| ** Given the list of WhereLoop objects at pWInfo->pLoops, this routine |
| ** attempts to find the lowest cost path that visits each WhereLoop |
| ** once. This path is then loaded into the pWInfo->a[].pWLoop fields. |
| ** |
| ** Assume that the total number of output rows that will need to be sorted |
| ** will be nRowEst (in the 10*log2 representation). Or, ignore sorting |
| ** costs if nRowEst==0. |
| ** |
| ** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation |
| ** error occurs. |
| */ |
| 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 */ |
| int nOrderBy; /* Number of ORDER BY clause terms */ |
| LogEst mxCost = 0; /* Maximum cost of a set of paths */ |
| LogEst mxUnsorted = 0; /* Maximum unsorted cost of a set of path */ |
| 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 */ |
| WherePath *pFrom; /* An element of aFrom[] that we are working on */ |
| WherePath *pTo; /* An element of aTo[] that we are working on */ |
| WhereLoop *pWLoop; /* One of the WhereLoop objects */ |
| WhereLoop **pX; /* Used to divy up the pSpace memory */ |
| LogEst *aSortCost = 0; /* Sorting and partial sorting costs */ |
| char *pSpace; /* Temporary memory used by this routine */ |
| 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. |
| ** For joins of 3 or more tables, track the 10 best paths */ |
| mxChoice = (nLoop<=1) ? 1 : (nLoop==2 ? 5 : 10); |
| assert( nLoop<=pWInfo->pTabList->nSrc ); |
| WHERETRACE(0x002, ("---- begin solver. (nRowEst=%d)\n", nRowEst)); |
| |
| /* If nRowEst is zero and there is an ORDER BY clause, ignore it. In this |
| ** case the purpose of this call is to estimate the number of rows returned |
| ** by the overall query. Once this estimate has been obtained, the caller |
| ** will invoke this function a second time, passing the estimate as the |
| ** nRowEst parameter. */ |
| if( pWInfo->pOrderBy==0 || nRowEst==0 ){ |
| nOrderBy = 0; |
| }else{ |
| nOrderBy = pWInfo->pOrderBy->nExpr; |
| } |
| |
| /* 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); |
| if( pSpace==0 ) return SQLITE_NOMEM_BKPT; |
| aTo = (WherePath*)pSpace; |
| aFrom = aTo+mxChoice; |
| memset(aFrom, 0, sizeof(aFrom[0])); |
| pX = (WhereLoop**)(aFrom+mxChoice); |
| for(ii=mxChoice*2, pFrom=aTo; ii>0; ii--, pFrom++, pX += nLoop){ |
| pFrom->aLoop = pX; |
| } |
| if( nOrderBy ){ |
| /* If there is an ORDER BY clause and it is not being ignored, set up |
| ** space for the aSortCost[] array. Each element of the aSortCost array |
| ** is either zero - meaning it has not yet been initialized - or the |
| ** cost of sorting nRowEst rows of data where the first X terms of |
| ** the ORDER BY clause are already in order, where X is the array |
| ** index. */ |
| aSortCost = (LogEst*)pX; |
| memset(aSortCost, 0, sizeof(LogEst) * nOrderBy); |
| } |
| assert( aSortCost==0 || &pSpace[nSpace]==(char*)&aSortCost[nOrderBy] ); |
| assert( aSortCost!=0 || &pSpace[nSpace]==(char*)pX ); |
| |
| /* Seed the search with a single WherePath containing zero WhereLoops. |
| ** |
| ** TUNING: Do not let the number of iterations go above 28. If the cost |
| ** of computing an automatic index is not paid back within the first 28 |
| ** rows, then do not use the automatic index. */ |
| aFrom[0].nRow = MIN(pParse->nQueryLoop, 48); assert( 48==sqlite3LogEst(28) ); |
| nFrom = 1; |
| assert( aFrom[0].isOrdered==0 ); |
| if( nOrderBy ){ |
| /* If nLoop is zero, then there are no FROM terms in the query. Since |
| ** in this case the query may return a maximum of one row, the results |
| ** are already in the requested order. Set isOrdered to nOrderBy to |
| ** indicate this. Or, if nLoop is greater than zero, set isOrdered to |
| ** -1, indicating that the result set may or may not be ordered, |
| ** depending on the loops added to the current plan. */ |
| aFrom[0].isOrdered = nLoop>0 ? -1 : nOrderBy; |
| } |
| |
| /* Compute successively longer WherePaths using the previous generation |
| ** of WherePaths as the basis for the next. Keep track of the mxChoice |
| ** best paths at each generation */ |
| for(iLoop=0; iLoop<nLoop; iLoop++){ |
| nTo = 0; |
| for(ii=0, pFrom=aFrom; ii<nFrom; ii++, pFrom++){ |
| for(pWLoop=pWInfo->pLoops; pWLoop; pWLoop=pWLoop->pNextLoop){ |
| 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) */ |
| Bitmask maskNew; /* Mask of src visited by (..) */ |
| Bitmask revMask = 0; /* Mask of rev-order loops for (..) */ |
| |
| if( (pWLoop->prereq & ~pFrom->maskLoop)!=0 ) continue; |
| if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue; |
| if( (pWLoop->wsFlags & WHERE_AUTO_INDEX)!=0 && pFrom->nRow<3 ){ |
| /* Do not use an automatic index if the this loop is expected |
| ** to run less than 1.25 times. It is tempting to also exclude |
| ** automatic index usage on an outer loop, but sometimes an automatic |
| ** index is useful in the outer loop of a correlated subquery. */ |
| assert( 10==sqlite3LogEst(2) ); |
| continue; |
| } |
| |
| /* At this point, pWLoop is a candidate to be the next loop. |
| ** Compute its cost */ |
| rUnsorted = sqlite3LogEstAdd(pWLoop->rSetup,pWLoop->rRun + pFrom->nRow); |
| rUnsorted = sqlite3LogEstAdd(rUnsorted, pFrom->rUnsorted); |
| nOut = pFrom->nRow + pWLoop->nOut; |
| maskNew = pFrom->maskLoop | pWLoop->maskSelf; |
| if( isOrdered<0 ){ |
| isOrdered = wherePathSatisfiesOrderBy(pWInfo, |
| pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags, |
| iLoop, pWLoop, &revMask); |
| }else{ |
| revMask = pFrom->revLoop; |
| } |
| if( isOrdered>=0 && isOrdered<nOrderBy ){ |
| if( aSortCost[isOrdered]==0 ){ |
| aSortCost[isOrdered] = whereSortingCost( |
| pWInfo, nRowEst, nOrderBy, isOrdered |
| ); |
| } |
| /* TUNING: Add a small extra penalty (5) 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; |
| |
| WHERETRACE(0x002, |
| ("---- sort cost=%-3d (%d/%d) increases cost %3d to %-3d\n", |
| aSortCost[isOrdered], (nOrderBy-isOrdered), nOrderBy, |
| rUnsorted, rCost)); |
| }else{ |
| rCost = rUnsorted; |
| rUnsorted -= 2; /* TUNING: Slight bias in favor of no-sort plans */ |
| } |
| |
| /* Check to see if pWLoop should be added to the set of |
| ** mxChoice best-so-far paths. |
| ** |
| ** First look for an existing path among best-so-far paths |
| ** that covers the same set of loops and has the same isOrdered |
| ** setting as the current path candidate. |
| ** |
| ** The term "((pTo->isOrdered^isOrdered)&0x80)==0" is equivalent |
| ** to (pTo->isOrdered==(-1))==(isOrdered==(-1))" for the range |
| ** of legal values for isOrdered, -1..64. |
| */ |
| for(jj=0, pTo=aTo; jj<nTo; jj++, pTo++){ |
| if( pTo->maskLoop==maskNew |
| && ((pTo->isOrdered^isOrdered)&0x80)==0 |
| ){ |
| testcase( jj==nTo-1 ); |
| break; |
| } |
| } |
| if( jj>=nTo ){ |
| /* None of the existing best-so-far paths match the candidate. */ |
| if( nTo>=mxChoice |
| && (rCost>mxCost || (rCost==mxCost && rUnsorted>=mxUnsorted)) |
| ){ |
| /* The current candidate is no better than any of the mxChoice |
| ** paths currently in the best-so-far buffer. So discard |
| ** this candidate as not viable. */ |
| #ifdef WHERETRACE_ENABLED /* 0x4 */ |
| if( sqlite3WhereTrace&0x4 ){ |
| sqlite3DebugPrintf("Skip %s cost=%-3d,%3d,%3d order=%c\n", |
| wherePathName(pFrom, iLoop, pWLoop), rCost, nOut, rUnsorted, |
| isOrdered>=0 ? isOrdered+'0' : '?'); |
| } |
| #endif |
| continue; |
| } |
| /* If we reach this points it means that the new candidate path |
| ** needs to be added to the set of best-so-far paths. */ |
| if( nTo<mxChoice ){ |
| /* Increase the size of the aTo set by one */ |
| jj = nTo++; |
| }else{ |
| /* New path replaces the prior worst to keep count below mxChoice */ |
| jj = mxI; |
| } |
| pTo = &aTo[jj]; |
| #ifdef WHERETRACE_ENABLED /* 0x4 */ |
| if( sqlite3WhereTrace&0x4 ){ |
| sqlite3DebugPrintf("New %s cost=%-3d,%3d,%3d order=%c\n", |
| wherePathName(pFrom, iLoop, pWLoop), rCost, nOut, rUnsorted, |
| isOrdered>=0 ? isOrdered+'0' : '?'); |
| } |
| #endif |
| }else{ |
| /* Control reaches here if best-so-far path pTo=aTo[jj] covers the |
| ** same set of loops and has the same isOrdered setting as the |
| ** candidate path. Check to see if the candidate should replace |
| ** pTo or if the candidate should be skipped. |
| ** |
| ** The conditional is an expanded vector comparison equivalent to: |
| ** (pTo->rCost,pTo->nRow,pTo->rUnsorted) <= (rCost,nOut,rUnsorted) |
| */ |
| if( pTo->rCost<rCost |
| || (pTo->rCost==rCost |
| && (pTo->nRow<nOut |
| || (pTo->nRow==nOut && pTo->rUnsorted<=rUnsorted) |
| ) |
| ) |
| ){ |
| #ifdef WHERETRACE_ENABLED /* 0x4 */ |
| if( sqlite3WhereTrace&0x4 ){ |
| sqlite3DebugPrintf( |
| "Skip %s cost=%-3d,%3d,%3d order=%c", |
| wherePathName(pFrom, iLoop, pWLoop), rCost, nOut, rUnsorted, |
| isOrdered>=0 ? isOrdered+'0' : '?'); |
| sqlite3DebugPrintf(" vs %s cost=%-3d,%3d,%3d order=%c\n", |
| wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow, |
| pTo->rUnsorted, pTo->isOrdered>=0 ? pTo->isOrdered+'0' : '?'); |
| } |
| #endif |
| /* Discard the candidate path from further consideration */ |
| testcase( pTo->rCost==rCost ); |
| continue; |
| } |
| testcase( pTo->rCost==rCost+1 ); |
| /* Control reaches here if the candidate path is better than the |
| ** pTo path. Replace pTo with the candidate. */ |
| #ifdef WHERETRACE_ENABLED /* 0x4 */ |
| if( sqlite3WhereTrace&0x4 ){ |
| sqlite3DebugPrintf( |
| "Update %s cost=%-3d,%3d,%3d order=%c", |
| wherePathName(pFrom, iLoop, pWLoop), rCost, nOut, rUnsorted, |
| isOrdered>=0 ? isOrdered+'0' : '?'); |
| sqlite3DebugPrintf(" was %s cost=%-3d,%3d,%3d order=%c\n", |
| wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow, |
| pTo->rUnsorted, pTo->isOrdered>=0 ? pTo->isOrdered+'0' : '?'); |
| } |
| #endif |
| } |
| /* pWLoop is a winner. Add it to the set of best so far */ |
| pTo->maskLoop = pFrom->maskLoop | pWLoop->maskSelf; |
| pTo->revLoop = revMask; |
| pTo->nRow = nOut; |
| pTo->rCost = rCost; |
| pTo->rUnsorted = rUnsorted; |
| pTo->isOrdered = isOrdered; |
| memcpy(pTo->aLoop, pFrom->aLoop, sizeof(WhereLoop*)*iLoop); |
| pTo->aLoop[iLoop] = pWLoop; |
| if( nTo>=mxChoice ){ |
| mxI = 0; |
| mxCost = aTo[0].rCost; |
| mxUnsorted = aTo[0].nRow; |
| for(jj=1, pTo=&aTo[1]; jj<mxChoice; jj++, pTo++){ |
| if( pTo->rCost>mxCost |
| || (pTo->rCost==mxCost && pTo->rUnsorted>mxUnsorted) |
| ){ |
| mxCost = pTo->rCost; |
| mxUnsorted = pTo->rUnsorted; |
| mxI = jj; |
| } |
| } |
| } |
| } |
| } |
| |
| #ifdef WHERETRACE_ENABLED /* >=2 */ |
| if( sqlite3WhereTrace & 0x02 ){ |
| sqlite3DebugPrintf("---- after round %d ----\n", iLoop); |
| for(ii=0, pTo=aTo; ii<nTo; ii++, pTo++){ |
| sqlite3DebugPrintf(" %s cost=%-3d nrow=%-3d order=%c", |
| wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow, |
| pTo->isOrdered>=0 ? (pTo->isOrdered+'0') : '?'); |
| if( pTo->isOrdered>0 ){ |
| sqlite3DebugPrintf(" rev=0x%llx\n", pTo->revLoop); |
| }else{ |
| sqlite3DebugPrintf("\n"); |
| } |
| } |
| } |
| #endif |
| |
| /* Swap the roles of aFrom and aTo for the next generation */ |
| pFrom = aTo; |
| aTo = aFrom; |
| aFrom = pFrom; |
| nFrom = nTo; |
| } |
| |
| if( nFrom==0 ){ |
| sqlite3ErrorMsg(pParse, "no query solution"); |
| sqlite3DbFreeNN(db, pSpace); |
| return SQLITE_ERROR; |
| } |
| |
| /* Find the lowest cost path. pFrom will be left pointing to that path */ |
| pFrom = aFrom; |
| for(ii=1; ii<nFrom; ii++){ |
| if( pFrom->rCost>aFrom[ii].rCost ) pFrom = &aFrom[ii]; |
| } |
| assert( pWInfo->nLevel==nLoop ); |
| /* Load the lowest cost path into pWInfo */ |
| for(iLoop=0; iLoop<nLoop; iLoop++){ |
| WhereLevel *pLevel = pWInfo->a + iLoop; |
| pLevel->pWLoop = pWLoop = pFrom->aLoop[iLoop]; |
| pLevel->iFrom = pWLoop->iTab; |
| pLevel->iTabCur = pWInfo->pTabList->a[pLevel->iFrom].iCursor; |
| } |
| if( (pWInfo->wctrlFlags & WHERE_WANT_DISTINCT)!=0 |
| && (pWInfo->wctrlFlags & WHERE_DISTINCTBY)==0 |
| && pWInfo->eDistinct==WHERE_DISTINCT_NOOP |
| && nRowEst |
| ){ |
| Bitmask notUsed; |
| int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pResultSet, pFrom, |
| WHERE_DISTINCTBY, nLoop-1, pFrom->aLoop[nLoop-1], ¬Used); |
| if( rc==pWInfo->pResultSet->nExpr ){ |
| pWInfo->eDistinct = WHERE_DISTINCT_ORDERED; |
| } |
| } |
| pWInfo->bOrderedInnerLoop = 0; |
| if( pWInfo->pOrderBy ){ |
| if( pWInfo->wctrlFlags & WHERE_DISTINCTBY ){ |
| if( pFrom->isOrdered==pWInfo->pOrderBy->nExpr ){ |
| pWInfo->eDistinct = WHERE_DISTINCT_ORDERED; |
| } |
| }else{ |
| pWInfo->nOBSat = pFrom->isOrdered; |
| pWInfo->revMask = pFrom->revLoop; |
| if( pWInfo->nOBSat<=0 ){ |
| pWInfo->nOBSat = 0; |
| if( nLoop>0 ){ |
| u32 wsFlags = pFrom->aLoop[nLoop-1]->wsFlags; |
| if( (wsFlags & WHERE_ONEROW)==0 |
| && (wsFlags&(WHERE_IPK|WHERE_COLUMN_IN))!=(WHERE_IPK|WHERE_COLUMN_IN) |
| ){ |
| Bitmask m = 0; |
| int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, pFrom, |
| WHERE_ORDERBY_LIMIT, nLoop-1, pFrom->aLoop[nLoop-1], &m); |
| testcase( wsFlags & WHERE_IPK ); |
| testcase( wsFlags & WHERE_COLUMN_IN ); |
| if( rc==pWInfo->pOrderBy->nExpr ){ |
| pWInfo->bOrderedInnerLoop = 1; |
| pWInfo->revMask = m; |
| } |
| } |
| } |
| } |
| } |
| if( (pWInfo->wctrlFlags & WHERE_SORTBYGROUP) |
| && pWInfo->nOBSat==pWInfo->pOrderBy->nExpr && nLoop>0 |
| ){ |
| Bitmask revMask = 0; |
| int nOrder = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, |
| pFrom, 0, nLoop-1, pFrom->aLoop[nLoop-1], &revMask |
| ); |
| assert( pWInfo->sorted==0 ); |
| if( nOrder==pWInfo->pOrderBy->nExpr ){ |
| pWInfo->sorted = 1; |
| pWInfo->revMask = revMask; |
| } |
| } |
| } |
| |
| |
| pWInfo->nRowOut = pFrom->nRow; |
| |
| /* Free temporary memory and return success */ |
| sqlite3DbFreeNN(db, pSpace); |
| return SQLITE_OK; |
| } |
| |
| /* |
| ** Most queries use only a single table (they are not joins) and have |
| ** simple == constraints against indexed fields. This routine attempts |
| ** to plan those simple cases using much less ceremony than the |
| ** general-purpose query planner, and thereby yield faster sqlite3_prepare() |
| ** times for the common case. |
| ** |
| ** Return non-zero on success, if this query can be handled by this |
| ** no-frills query planner. Return zero if this query needs the |
| ** general-purpose query planner. |
| */ |
| static int whereShortCut(WhereLoopBuilder *pBuilder){ |
| WhereInfo *pWInfo; |
| struct SrcList_item *pItem; |
| WhereClause *pWC; |
| WhereTerm *pTerm; |
| WhereLoop *pLoop; |
| int iCur; |
| int j; |
| Table *pTab; |
| Index *pIdx; |
| |
| pWInfo = pBuilder->pWInfo; |
| if( pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE ) return 0; |
| assert( pWInfo->pTabList->nSrc>=1 ); |
| pItem = pWInfo->pTabList->a; |
| pTab = pItem->pTab; |
| if( IsVirtual(pTab) ) return 0; |
| if( pItem->fg.isIndexedBy ) return 0; |
| iCur = pItem->iCursor; |
| pWC = &pWInfo->sWC; |
| pLoop = pBuilder->pNew; |
| pLoop->wsFlags = 0; |
| pLoop->nSkip = 0; |
| pTerm = sqlite3WhereFindTerm(pWC, iCur, -1, 0, WO_EQ|WO_IS, 0); |
| if( pTerm ){ |
| testcase( pTerm->eOperator & WO_IS ); |
| pLoop->wsFlags = WHERE_COLUMN_EQ|WHERE_IPK|WHERE_ONEROW; |
| pLoop->aLTerm[0] = pTerm; |
| pLoop->nLTerm = 1; |
| pLoop->u.btree.nEq = 1; |
| /* TUNING: Cost of a rowid lookup is 10 */ |
| pLoop->rRun = 33; /* 33==sqlite3LogEst(10) */ |
| }else{ |
| for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){ |
| int opMask; |
| assert( pLoop->aLTermSpace==pLoop->aLTerm ); |
| if( !IsUniqueIndex(pIdx) |
| || pIdx->pPartIdxWhere!=0 |
| || pIdx->nKeyCol>ArraySize(pLoop->aLTermSpace) |
| ) continue; |
| opMask = pIdx->uniqNotNull ? (WO_EQ|WO_IS) : WO_EQ; |
| for(j=0; j<pIdx->nKeyCol; j++){ |
| pTerm = sqlite3WhereFindTerm(pWC, iCur, j, 0, opMask, pIdx); |
| if( pTerm==0 ) break; |
| testcase( pTerm->eOperator & WO_IS ); |
| pLoop->aLTerm[j] = pTerm; |
| } |
| if( j!=pIdx->nKeyCol ) continue; |
| pLoop->wsFlags = WHERE_COLUMN_EQ|WHERE_ONEROW|WHERE_INDEXED; |
| if( pIdx->isCovering || (pItem->colUsed & pIdx->colNotIdxed)==0 ){ |
| pLoop->wsFlags |= WHERE_IDX_ONLY; |
| } |
| pLoop->nLTerm = j; |
| pLoop->u.btree.nEq = j; |
| pLoop->u.btree.pIndex = pIdx; |
| /* TUNING: Cost of a unique index lookup is 15 */ |
| pLoop->rRun = 39; /* 39==sqlite3LogEst(15) */ |
| break; |
| } |
| } |
| if( pLoop->wsFlags ){ |
| pLoop->nOut = (LogEst)1; |
| pWInfo->a[0].pWLoop = pLoop; |
| assert( pWInfo->sMaskSet.n==1 && iCur==pWInfo->sMaskSet.ix[0] ); |
| pLoop->maskSelf = 1; /* sqlite3WhereGetMask(&pWInfo->sMaskSet, iCur); */ |
| pWInfo->a[0].iTabCur = iCur; |
| pWInfo->nRowOut = 1; |
| if( pWInfo->pOrderBy ) pWInfo->nOBSat = pWInfo->pOrderBy->nExpr; |
| if( pWInfo->wctrlFlags & WHERE_WANT_DISTINCT ){ |
| pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE; |
| } |
| #ifdef SQLITE_DEBUG |
| pLoop->cId = '0'; |
| #endif |
| return 1; |
| } |
| return 0; |
| } |
| |
| /* |
| ** Helper function for exprIsDeterministic(). |
| */ |
| static int exprNodeIsDeterministic(Walker *pWalker, Expr *pExpr){ |
| if( pExpr->op==TK_FUNCTION && ExprHasProperty(pExpr, EP_ConstFunc)==0 ){ |
| pWalker->eCode = 0; |
| return WRC_Abort; |
| } |
| return WRC_Continue; |
| } |
| |
| /* |
| ** Return true if the expression contains no non-deterministic SQL |
| ** functions. Do not consider non-deterministic SQL functions that are |
| ** part of sub-select statements. |
| */ |
| static int exprIsDeterministic(Expr *p){ |
| Walker w; |
| memset(&w, 0, sizeof(w)); |
| w.eCode = 1; |
| w.xExprCallback = exprNodeIsDeterministic; |
| w.xSelectCallback = sqlite3SelectWalkFail; |
| sqlite3WalkExpr(&w, p); |
| return w.eCode; |
| } |
| |
| /* |
| ** 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 |
| ** should invoke sqlite3WhereEnd() with the return value of this function |
| ** in order to complete the WHERE clause processing. |
| ** |
| ** If an error occurs, this routine returns NULL. |
| ** |
| ** The basic idea is to do a nested loop, one loop for each table in |
| ** the FROM clause of a select. (INSERT and UPDATE statements are the |
| ** same as a SELECT with only a single table in the FROM clause.) For |
| ** example, if the SQL is this: |
| ** |
| ** SELECT * FROM t1, t2, t3 WHERE ...; |
| ** |
| ** Then the code generated is conceptually like the following: |
| ** |
| ** foreach row1 in t1 do \ Code generated |
| ** foreach row2 in t2 do |-- by sqlite3WhereBegin() |
| ** foreach row3 in t3 do / |
| ** ... |
| ** end \ Code generated |
| ** end |-- by sqlite3WhereEnd() |
| ** end / |
| ** |
| ** Note that the loops might not be nested in the order in which they |
| ** appear in the FROM clause if a different order is better able to make |
| ** use of indices. Note also that when the IN operator appears in |
| ** the WHERE clause, it might result in additional nested loops for |
| ** scanning through all values on the right-hand side of the IN. |
| ** |
| ** There are Btree cursors associated with each table. t1 uses cursor |
| ** number pTabList->a[0].iCursor. t2 uses the cursor pTabList->a[1].iCursor. |
| ** And so forth. This routine generates code to open those VDBE cursors |
| ** and sqlite3WhereEnd() generates the code to close them. |
| ** |
| ** The code that sqlite3WhereBegin() generates leaves the cursors named |
| ** in pTabList pointing at their appropriate entries. The [...] code |
| ** can use OP_Column and OP_Rowid opcodes on these cursors to extract |
| ** data from the various tables of the loop. |
| ** |
| ** If the WHERE clause is empty, the foreach loops must each scan their |
| ** entire tables. Thus a three-way join is an O(N^3) operation. But if |
| ** the tables have indices and there are terms in the WHERE clause that |
| ** refer to those indices, a complete table scan can be avoided and the |
| ** code will run much faster. Most of the work of this routine is checking |
| ** to see if there are indices that can be used to speed up the loop. |
| ** |
| ** Terms of the WHERE clause are also used to limit which rows actually |
| ** make it to the "..." in the middle of the loop. After each "foreach", |
| ** terms of the WHERE clause that use only terms in that loop and outer |
| ** loops are evaluated and if false a jump is made around all subsequent |
| ** inner loops (or around the "..." if the test occurs within the inner- |
| ** most loop) |
| ** |
| ** OUTER JOINS |
| ** |
| ** An outer join of tables t1 and t2 is conceptally coded as follows: |
| ** |
| ** foreach row1 in t1 do |
| ** flag = 0 |
| ** foreach row2 in t2 do |
| ** start: |
| ** ... |
| ** flag = 1 |
| ** end |
| ** if flag==0 then |
| ** move the row2 cursor to a null row |
| ** goto start |
| ** fi |
| ** end |
| ** |
| ** ORDER BY CLAUSE PROCESSING |
| ** |
| ** pOrderBy is a pointer to the ORDER BY clause (or the GROUP BY clause |
| ** if the WHERE_GROUPBY flag is set in wctrlFlags) of a SELECT statement |
| ** if there is one. If there is no ORDER BY clause or if this routine |
| ** is called from an UPDATE or DELETE statement, then pOrderBy is NULL. |
| ** |
| ** The iIdxCur parameter is the cursor number of an index. If |
| ** WHERE_OR_SUBCLAUSE is set, iIdxCur is the cursor number of an index |
| ** to use for OR clause processing. The WHERE clause should use this |
| ** specific cursor. If WHERE_ONEPASS_DESIRED is set, then iIdxCur is |
| ** the first cursor in an array of cursors for all indices. iIdxCur should |
| ** be used to compute the appropriate cursor depending on which index is |
| ** used. |
| */ |
| WhereInfo *sqlite3WhereBegin( |
| Parse *pParse, /* The parser context */ |
| SrcList *pTabList, /* FROM clause: A list of all tables to be scanned */ |
| 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 */ |
| 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 */ |
| ){ |
| int nByteWInfo; /* Num. bytes allocated for WhereInfo struct */ |
| int nTabList; /* Number of elements in pTabList */ |
| WhereInfo *pWInfo; /* Will become the return value of this function */ |
| Vdbe *v = pParse->pVdbe; /* The virtual database engine */ |
| Bitmask notReady; /* Cursors that are not yet positioned */ |
| WhereLoopBuilder sWLB; /* The WhereLoop builder */ |
| WhereMaskSet *pMaskSet; /* The expression mask set */ |
| WhereLevel *pLevel; /* A single level in pWInfo->a[] */ |
| WhereLoop *pLoop; /* Pointer to a single WhereLoop object */ |
| int ii; /* Loop counter */ |
| sqlite3 *db; /* Database connection */ |
| int rc; /* Return code */ |
| u8 bFordelete = 0; /* OPFLAG_FORDELETE or zero, as appropriate */ |
| |
| assert( (wctrlFlags & WHERE_ONEPASS_MULTIROW)==0 || ( |
| (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 |
| && (wctrlFlags & WHERE_OR_SUBCLAUSE)==0 |
| )); |
| |
| /* Only one of WHERE_OR_SUBCLAUSE or WHERE_USE_LIMIT */ |
| assert( (wctrlFlags & WHERE_OR_SUBCLAUSE)==0 |
| || (wctrlFlags & WHERE_USE_LIMIT)==0 ); |
| |
| /* Variable initialization */ |
| db = pParse->db; |
| memset(&sWLB, 0, sizeof(sWLB)); |
| |
| /* An ORDER/GROUP BY clause of more than 63 terms cannot be optimized */ |
| testcase( pOrderBy && pOrderBy->nExpr==BMS-1 ); |
| if( pOrderBy && pOrderBy->nExpr>=BMS ) pOrderBy = 0; |
| sWLB.pOrderBy = pOrderBy; |
| |
| /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via |
| ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */ |
| if( OptimizationDisabled(db, SQLITE_DistinctOpt) ){ |
| wctrlFlags &= ~WHERE_WANT_DISTINCT; |
| } |
| |
| /* The number of tables in the FROM clause is limited by the number of |
| ** bits in a Bitmask |
| */ |
| testcase( pTabList->nSrc==BMS ); |
| if( pTabList->nSrc>BMS ){ |
| sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS); |
| return 0; |
| } |
| |
| /* This function normally generates a nested loop for all tables in |
| ** pTabList. But if the WHERE_OR_SUBCLAUSE flag is set, then we should |
| ** only generate code for the first table in pTabList and assume that |
| ** any cursors associated with subsequent tables are uninitialized. |
| */ |
| nTabList = (wctrlFlags & WHERE_OR_SUBCLAUSE) ? 1 : pTabList->nSrc; |
| |
| /* Allocate and initialize the WhereInfo structure that will become the |
| ** return value. A single allocation is used to store the WhereInfo |
| ** struct, the contents of WhereInfo.a[], the WhereClause structure |
| ** and the WhereMaskSet structure. Since WhereClause contains an 8-byte |
| ** field (type Bitmask) it must be aligned on an 8-byte boundary on |
| ** some architectures. Hence the ROUND8() below. |
| */ |
| nByteWInfo = ROUND8(sizeof(WhereInfo)+(nTabList-1)*sizeof(WhereLevel)); |
| pWInfo = sqlite3DbMallocRawNN(db, nByteWInfo + sizeof(WhereLoop)); |
| if( db->mallocFailed ){ |
| sqlite3DbFree(db, pWInfo); |
| pWInfo = 0; |
| goto whereBeginError; |
| } |
| pWInfo->pParse = pParse; |
| pWInfo->pTabList = pTabList; |
| pWInfo->pOrderBy = pOrderBy; |
| pWInfo->pWhere = pWhere; |
| pWInfo->pResultSet = pResultSet; |
| pWInfo->aiCurOnePass[0] = pWInfo->aiCurOnePass[1] = -1; |
| pWInfo->nLevel = nTabList; |
| pWInfo->iBreak = pWInfo->iContinue = sqlite3VdbeMakeLabel(pParse); |
| pWInfo->wctrlFlags = wctrlFlags; |
| pWInfo->iLimit = iAuxArg; |
| pWInfo->savedNQueryLoop = pParse->nQueryLoop; |
| memset(&pWInfo->nOBSat, 0, |
| offsetof(WhereInfo,sWC) - offsetof(WhereInfo,nOBSat)); |
| memset(&pWInfo->a[0], 0, sizeof(WhereLoop)+nTabList*sizeof(WhereLevel)); |
| assert( pWInfo->eOnePass==ONEPASS_OFF ); /* ONEPASS defaults to OFF */ |
| pMaskSet = &pWInfo->sMaskSet; |
| sWLB.pWInfo = pWInfo; |
| sWLB.pWC = &pWInfo->sWC; |
| sWLB.pNew = (WhereLoop*)(((char*)pWInfo)+nByteWInfo); |
| assert( EIGHT_BYTE_ALIGNMENT(sWLB.pNew) ); |
| whereLoopInit(sWLB.pNew); |
| #ifdef SQLITE_DEBUG |
| sWLB.pNew->cId = '*'; |
| #endif |
| |
| /* Split the WHERE clause into separate subexpressions where each |
| ** subexpression is separated by an AND operator. |
| */ |
| initMaskSet(pMaskSet); |
| sqlite3WhereClauseInit(&pWInfo->sWC, pWInfo); |
| sqlite3WhereSplit(&pWInfo->sWC, pWhere, TK_AND); |
| |
| /* Special case: No FROM clause |
| */ |
| if( nTabList==0 ){ |
| if( pOrderBy ) pWInfo->nOBSat = pOrderBy->nExpr; |
| if( wctrlFlags & WHERE_WANT_DISTINCT ){ |
| pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE; |
| } |
| ExplainQueryPlan((pParse, 0, "SCAN CONSTANT ROW")); |
| }else{ |
| /* Assign a bit from the bitmask to every term in the FROM clause. |
| ** |
| ** The N-th term of the FROM clause is assigned a bitmask of 1<<N. |
| ** |
| ** The rule of the previous sentence ensures thta if X is the bitmask for |
| ** a table T, then X-1 is the bitmask for all other tables to the left of T. |
| ** Knowing the bitmask for all tables to the left of a left join is |
| ** important. Ticket #3015. |
| ** |
| ** Note that bitmasks are created for all pTabList->nSrc tables in |
| ** pTabList, not just the first nTabList tables. nTabList is normally |
| ** equal to pTabList->nSrc but might be shortened to 1 if the |
| ** WHERE_OR_SUBCLAUSE flag is set. |
| */ |
| ii = 0; |
| do{ |
| createMask(pMaskSet, pTabList->a[ii].iCursor); |
| sqlite3WhereTabFuncArgs(pParse, &pTabList->a[ii], &pWInfo->sWC); |
| }while( (++ii)<pTabList->nSrc ); |
| #ifdef SQLITE_DEBUG |
| { |
| Bitmask mx = 0; |
| for(ii=0; ii<pTabList->nSrc; ii++){ |
| Bitmask m = sqlite3WhereGetMask(pMaskSet, pTabList->a[ii].iCursor); |
| assert( m>=mx ); |
| mx = m; |
| } |
| } |
| #endif |
| } |
| |
| /* Analyze all of the subexpressions. */ |
| sqlite3WhereExprAnalyze(pTabList, &pWInfo->sWC); |
| if( db->mallocFailed ) goto whereBeginError; |
| |
| /* Special case: WHERE terms that do not refer to any tables in the join |
| ** (constant expressions). Evaluate each such term, and jump over all the |
| ** generated code if the result is not true. |
| ** |
| ** Do not do this if the expression contains non-deterministic functions |
| ** that are not within a sub-select. This is not strictly required, but |
| ** preserves SQLite's legacy behaviour in the following two cases: |
| ** |
| ** FROM ... WHERE random()>0; -- eval random() once per row |
| ** FROM ... WHERE (SELECT random())>0; -- eval random() once overall |
| */ |
| for(ii=0; ii<sWLB.pWC->nTerm; ii++){ |
| WhereTerm *pT = &sWLB.pWC->a[ii]; |
| if( pT->wtFlags & TERM_VIRTUAL ) continue; |
| if( pT->prereqAll==0 && (nTabList==0 || exprIsDeterministic(pT->pExpr)) ){ |
| sqlite3ExprIfFalse(pParse, pT->pExpr, pWInfo->iBreak, SQLITE_JUMPIFNULL); |
| pT->wtFlags |= TERM_CODED; |
| } |
| } |
| |
| if( wctrlFlags & WHERE_WANT_DISTINCT ){ |
| if( isDistinctRedundant(pParse, pTabList, &pWInfo->sWC, pResultSet) ){ |
| /* The DISTINCT marking is pointless. Ignore it. */ |
| pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE; |
| }else if( pOrderBy==0 ){ |
| /* Try to ORDER BY the result set to make distinct processing easier */ |
| pWInfo->wctrlFlags |= WHERE_DISTINCTBY; |
| pWInfo->pOrderBy = pResultSet; |
| } |
| } |
| |
| /* Construct the WhereLoop objects */ |
| #if defined(WHERETRACE_ENABLED) |
| if( sqlite3WhereTrace & 0xffff ){ |
| sqlite3DebugPrintf("*** Optimizer Start *** (wctrlFlags: 0x%x",wctrlFlags); |
| if( wctrlFlags & WHERE_USE_LIMIT ){ |
| sqlite3DebugPrintf(", limit: %d", iAuxArg); |
| } |
| sqlite3DebugPrintf(")\n"); |
| } |
| if( sqlite3WhereTrace & 0x100 ){ /* Display all terms of the WHERE clause */ |
| sqlite3WhereClausePrint(sWLB.pWC); |
| } |
| #endif |
| |
| if( nTabList!=1 || whereShortCut(&sWLB)==0 ){ |
| rc = whereLoopAddAll(&sWLB); |
| if( rc ) goto whereBeginError; |
| |
| #ifdef WHERETRACE_ENABLED |
| if( sqlite3WhereTrace ){ /* Display all of the WhereLoop objects */ |
| WhereLoop *p; |
| int i; |
| static const char zLabel[] = "0123456789abcdefghijklmnopqrstuvwyxz" |
| "ABCDEFGHIJKLMNOPQRSTUVWYXZ"; |
| for(p=pWInfo->pLoops, i=0; p; p=p->pNextLoop, i++){ |
| p->cId = zLabel[i%(sizeof(zLabel)-1)]; |
| whereLoopPrint(p, sWLB.pWC); |
| } |
| } |
| #endif |
| |
| wherePathSolver(pWInfo, 0); |
| if( db->mallocFailed ) goto whereBeginError; |
| if( pWInfo->pOrderBy ){ |
| wherePathSolver(pWInfo, pWInfo->nRowOut+1); |
| if( db->mallocFailed ) goto whereBeginError; |
| } |
| } |
| if( pWInfo->pOrderBy==0 && (db->flags & SQLITE_ReverseOrder)!=0 ){ |
| pWInfo->revMask = ALLBITS; |
| } |
| if( pParse->nErr || NEVER(db->mallocFailed) ){ |
| goto whereBeginError; |
| } |
| #ifdef WHERETRACE_ENABLED |
| if( sqlite3WhereTrace ){ |
| sqlite3DebugPrintf("---- Solution nRow=%d", pWInfo->nRowOut); |
| if( pWInfo->nOBSat>0 ){ |
| sqlite3DebugPrintf(" ORDERBY=%d,0x%llx", pWInfo->nOBSat, pWInfo->revMask); |
| } |
| switch( pWInfo->eDistinct ){ |
| case WHERE_DISTINCT_UNIQUE: { |
| sqlite3DebugPrintf(" DISTINCT=unique"); |
| break; |
| } |
| case WHERE_DISTINCT_ORDERED: { |
| sqlite3DebugPrintf(" DISTINCT=ordered"); |
| break; |
| } |
| case WHERE_DISTINCT_UNORDERED: { |
| sqlite3DebugPrintf(" DISTINCT=unordered"); |
| break; |
| } |
| } |
| sqlite3DebugPrintf("\n"); |
| for(ii=0; ii<pWInfo->nLevel; ii++){ |
| whereLoopPrint(pWInfo->a[ii].pWLoop, sWLB.pWC); |
| } |
| } |
| #endif |
| |
| /* Attempt to omit tables from the join that do not affect the result. |
| ** For a table to not affect the result, the following must be true: |
| ** |
| ** 1) The query must not be an aggregate. |
| ** 2) The table must be the RHS of a LEFT JOIN. |
| ** 3) Either the query must be DISTINCT, or else the ON or USING clause |
| ** must contain a constraint that limits the scan of the table to |
| ** at most a single row. |
| ** 4) The table must not be referenced by any part of the query apart |
| ** from its own USING or ON clause. |
| ** |
| ** For example, given: |
| ** |
| ** CREATE TABLE t1(ipk INTEGER PRIMARY KEY, v1); |
| ** CREATE TABLE t2(ipk INTEGER PRIMARY KEY, v2); |
| ** CREATE TABLE t3(ipk INTEGER PRIMARY KEY, v3); |
| ** |
| ** then table t2 can be omitted from the following: |
| ** |
| ** SELECT v1, v3 FROM t1 |
| ** LEFT JOIN t2 USING (t1.ipk=t2.ipk) |
| ** LEFT JOIN t3 USING (t1.ipk=t3.ipk) |
| ** |
| ** or from: |
| ** |
| ** SELECT DISTINCT v1, v3 FROM t1 |
| ** LEFT JOIN t2 |
| ** LEFT JOIN t3 USING (t1.ipk=t3.ipk) |
| */ |
| notReady = ~(Bitmask)0; |
| if( pWInfo->nLevel>=2 |
| && pResultSet!=0 /* guarantees condition (1) above */ |
| && OptimizationEnabled(db, SQLITE_OmitNoopJoin) |
| ){ |
| int i; |
| Bitmask tabUsed = sqlite3WhereExprListUsage(pMaskSet, pResultSet); |
| if( sWLB.pOrderBy ){ |
| tabUsed |= sqlite3WhereExprListUsage(pMaskSet, sWLB.pOrderBy); |
| } |
| for(i=pWInfo->nLevel-1; i>=1; i--){ |
| WhereTerm *pTerm, *pEnd; |
| struct SrcList_item *pItem; |
| pLoop = pWInfo->a[i].pWLoop; |
| pItem = &pWInfo->pTabList->a[pLoop->iTab]; |
| if( (pItem->fg.jointype & JT_LEFT)==0 ) continue; |
| if( (wctrlFlags & WHERE_WANT_DISTINCT)==0 |
| && (pLoop->wsFlags & WHERE_ONEROW)==0 |
| ){ |
| continue; |
| } |
| if( (tabUsed & pLoop->maskSelf)!=0 ) continue; |
| pEnd = sWLB.pWC->a + sWLB.pWC->nTerm; |
| for(pTerm=sWLB.pWC->a; pTerm<pEnd; pTerm++){ |
| if( (pTerm->prereqAll & pLoop->maskSelf)!=0 ){ |
| if( !ExprHasProperty(pTerm->pExpr, EP_FromJoin) |
| || pTerm->pExpr->iRightJoinTable!=pItem->iCursor |
| ){ |
| break; |
| } |
| } |
| } |
| if( pTerm<pEnd ) continue; |
| WHERETRACE(0xffff, ("-> drop loop %c not used\n", pLoop->cId)); |
| notReady &= ~pLoop->maskSelf; |
| for(pTerm=sWLB.pWC->a; pTerm<pEnd; pTerm++){ |
| if( (pTerm->prereqAll & pLoop->maskSelf)!=0 ){ |
| pTerm->wtFlags |= TERM_CODED; |
| } |
| } |
| if( i!=pWInfo->nLevel-1 ){ |
| int nByte = (pWInfo->nLevel-1-i) * sizeof(WhereLevel); |
| memmove(&pWInfo->a[i], &pWInfo->a[i+1], nByte); |
| } |
| pWInfo->nLevel--; |
| nTabList--; |
| } |
| } |
| WHERETRACE(0xffff,("*** Optimizer Finished ***\n")); |
| pWInfo->pParse->nQueryLoop += pWInfo->nRowOut; |
| |
| /* If the caller is an UPDATE or DELETE statement that is requesting |
| ** to use a one-pass algorithm, determine if this is appropriate. |
| ** |
| ** A one-pass approach can be used if the caller has requested one |
| ** and either (a) the scan visits at most one row or (b) each |
| ** of the following are true: |
| ** |
| ** * the caller has indicated that a one-pass approach can be used |
| ** with multiple rows (by setting WHERE_ONEPASS_MULTIROW), and |
| ** * the table is not a virtual table, and |
| ** * either the scan does not use the OR optimization or the caller |
| ** is a DELETE operation (WHERE_DUPLICATES_OK is only specified |
| ** for DELETE). |
| ** |
| ** The last qualification is because an UPDATE statement uses |
| ** WhereInfo.aiCurOnePass[1] to determine whether or not it really can |
| ** use a one-pass approach, and this is not set accurately for scans |
| ** that use the OR optimization. |
| */ |
| assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 ); |
| if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 ){ |
| int wsFlags = pWInfo->a[0].pWLoop->wsFlags; |
| int bOnerow = (wsFlags & WHERE_ONEROW)!=0; |
| assert( !(wsFlags & WHERE_VIRTUALTABLE) || IsVirtual(pTabList->a[0].pTab) ); |
| if( bOnerow || ( |
| 0!=(wctrlFlags & WHERE_ONEPASS_MULTIROW) |
| && !IsVirtual(pTabList->a[0].pTab) |
| && (0==(wsFlags & WHERE_MULTI_OR) || (wctrlFlags & WHERE_DUPLICATES_OK)) |
| )){ |
| pWInfo->eOnePass = bOnerow ? ONEPASS_SINGLE : ONEPASS_MULTI; |
| if( HasRowid(pTabList->a[0].pTab) && (wsFlags & WHERE_IDX_ONLY) ){ |
| if( wctrlFlags & WHERE_ONEPASS_MULTIROW ){ |
| bFordelete = OPFLAG_FORDELETE; |
| } |
| pWInfo->a[0].pWLoop->wsFlags = (wsFlags & ~WHERE_IDX_ONLY); |
| } |
| } |
| } |
| |
| /* Open all tables in the pTabList and any indices selected for |
| ** searching those tables. |
| */ |
| for(ii=0, pLevel=pWInfo->a; ii<nTabList; ii++, pLevel++){ |
| Table *pTab; /* Table to open */ |
| int iDb; /* Index of database containing table/index */ |
| struct SrcList_item *pTabItem; |
| |
| pTabItem = &pTabList->a[pLevel->iFrom]; |
| pTab = pTabItem->pTab; |
| iDb = sqlite3SchemaToIndex(db, pTab->pSchema); |
| pLoop = pLevel->pWLoop; |
| if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ){ |
| /* Do nothing */ |
| }else |
| #ifndef SQLITE_OMIT_VIRTUALTABLE |
| if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)!=0 ){ |
| const char *pVTab = (const char *)sqlite3GetVTable(db, pTab); |
| int iCur = pTabItem->iCursor; |
| sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0, pVTab, P4_VTAB); |
| }else if( IsVirtual(pTab) ){ |
| /* noop */ |
| }else |
| #endif |
| if( (pLoop->wsFlags & WHERE_IDX_ONLY)==0 |
| && (wctrlFlags & WHERE_OR_SUBCLAUSE)==0 ){ |
| int op = OP_OpenRead; |
| if( pWInfo->eOnePass!=ONEPASS_OFF ){ |
| op = OP_OpenWrite; |
| pWInfo->aiCurOnePass[0] = pTabItem->iCursor; |
| }; |
| sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, op); |
| assert( pTabItem->iCursor==pLevel->iTabCur ); |
| testcase( pWInfo->eOnePass==ONEPASS_OFF && pTab->nCol==BMS-1 ); |
| testcase( pWInfo->eOnePass==ONEPASS_OFF && pTab->nCol==BMS ); |
| if( pWInfo->eOnePass==ONEPASS_OFF && pTab->nCol<BMS && HasRowid(pTab) ){ |
| Bitmask b = pTabItem->colUsed; |
| int n = 0; |
| for(; b; b=b>>1, n++){} |
| sqlite3VdbeChangeP4(v, -1, SQLITE_INT_TO_PTR(n), P4_INT32); |
| assert( n<=pTab->nCol ); |
| } |
| #ifdef SQLITE_ENABLE_CURSOR_HINTS |
| if( pLoop->u.btree.pIndex!=0 ){ |
| sqlite3VdbeChangeP5(v, OPFLAG_SEEKEQ|bFordelete); |
| }else |
| #endif |
| { |
| sqlite3VdbeChangeP5(v, bFordelete); |
| } |
| #ifdef SQLITE_ENABLE_COLUMN_USED_MASK |
| sqlite3VdbeAddOp4Dup8(v, OP_ColumnsUsed, pTabItem->iCursor, 0, 0, |
| (const u8*)&pTabItem->colUsed, P4_INT64); |
| #endif |
| }else{ |
| sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName); |
| } |
| if( pLoop->wsFlags & WHERE_INDEXED ){ |
| Index *pIx = pLoop->u.btree.pIndex; |
| int iIndexCur; |
| int op = OP_OpenRead; |
| /* iAuxArg is always set to a positive value if ONEPASS is possible */ |
| assert( iAuxArg!=0 || (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 ); |
| if( !HasRowid(pTab) && IsPrimaryKeyIndex(pIx) |
| && (wctrlFlags & WHERE_OR_SUBCLAUSE)!=0 |
| ){ |
| /* This is one term of an OR-optimization using the PRIMARY KEY of a |
| ** WITHOUT ROWID table. No need for a separate index */ |
| iIndexCur = pLevel->iTabCur; |
| op = 0; |
| }else if( pWInfo->eOnePass!=ONEPASS_OFF ){ |
| Index *pJ = pTabItem->pTab->pIndex; |
| iIndexCur = iAuxArg; |
| assert( wctrlFlags & WHERE_ONEPASS_DESIRED ); |
| while( ALWAYS(pJ) && pJ!=pIx ){ |
| iIndexCur++; |
| pJ = pJ->pNext; |
| } |
| op = OP_OpenWrite; |
| pWInfo->aiCurOnePass[1] = iIndexCur; |
| }else if( iAuxArg && (wctrlFlags & WHERE_OR_SUBCLAUSE)!=0 ){ |
| iIndexCur = iAuxArg; |
| op = OP_ReopenIdx; |
| }else{ |
| iIndexCur = pParse->nTab++; |
| } |
| pLevel->iIdxCur = iIndexCur; |
| assert( pIx->pSchema==pTab->pSchema ); |
| assert( iIndexCur>=0 ); |
| if( op ){ |
| sqlite3VdbeAddOp3(v, op, iIndexCur, pIx->tnum, iDb); |
| sqlite3VdbeSetP4KeyInfo(pParse, pIx); |
| if( (pLoop->wsFlags & WHERE_CONSTRAINT)!=0 |
| && (pLoop->wsFlags & (WHERE_COLUMN_RANGE|WHERE_SKIPSCAN))==0 |
| && (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)==0 |
| && pWInfo->eDistinct!=WHERE_DISTINCT_ORDERED |
| ){ |
| sqlite3VdbeChangeP5(v, OPFLAG_SEEKEQ); /* Hint to COMDB2 */ |
| } |
| VdbeComment((v, "%s", pIx->zName)); |
| #ifdef SQLITE_ENABLE_COLUMN_USED_MASK |
| { |
| u64 colUsed = 0; |
| int ii, jj; |
| for(ii=0; ii<pIx->nColumn; ii++){ |
| jj = pIx->aiColumn[ii]; |
| if( jj<0 ) continue; |
| if( jj>63 ) jj = 63; |
| if( (pTabItem->colUsed & MASKBIT(jj))==0 ) continue; |
| colUsed |= ((u64)1)<<(ii<63 ? ii : 63); |
| } |
| sqlite3VdbeAddOp4Dup8(v, OP_ColumnsUsed, iIndexCur, 0, 0, |
| (u8*)&colUsed, P4_INT64); |
| } |
| #endif /* SQLITE_ENABLE_COLUMN_USED_MASK */ |
| } |
| } |
| if( iDb>=0 ) sqlite3CodeVerifySchema(pParse, iDb); |
| } |
| pWInfo->iTop = sqlite3VdbeCurrentAddr(v); |
| if( db->mallocFailed ) goto whereBeginError; |
| |
| /* Generate the code to do the search. Each iteration of the for |
| ** loop below generates code for a single nested loop of the VM |
| ** program. |
| */ |
| for(ii=0; ii<nTabList; ii++){ |
| int addrExplain; |
| int wsFlags; |
| pLevel = &pWInfo->a[ii]; |
| wsFlags = pLevel->pWLoop->wsFlags; |
| #ifndef SQLITE_OMIT_AUTOMATIC_INDEX |
| if( (pLevel->pWLoop->wsFlags & WHERE_AUTO_INDEX)!=0 ){ |
| constructAutomaticIndex(pParse, &pWInfo->sWC, |
| &pTabList->a[pLevel->iFrom], notReady, pLevel); |
| if( db->mallocFailed ) goto whereBeginError; |
| } |
| #endif |
| addrExplain = sqlite3WhereExplainOneScan( |
| pParse, pTabList, pLevel, wctrlFlags |
| ); |
| pLevel->addrBody = sqlite3VdbeCurrentAddr(v); |
| notReady = sqlite3WhereCodeOneLoopStart(pParse,v,pWInfo,ii,pLevel,notReady); |
| pWInfo->iContinue = pLevel->addrCont; |
| if( (wsFlags&WHERE_MULTI_OR)==0 && (wctrlFlags&WHERE_OR_SUBCLAUSE)==0 ){ |
| sqlite3WhereAddScanStatus(v, pTabList, pLevel, addrExplain); |
| } |
| } |
| |
| /* Done. */ |
| VdbeModuleComment((v, "Begin WHERE-core")); |
| return pWInfo; |
| |
| /* Jump here if malloc fails */ |
| whereBeginError: |
| if( pWInfo ){ |
| pParse->nQueryLoop = pWInfo->savedNQueryLoop; |
| whereInfoFree(db, pWInfo); |
| } |
| return 0; |
| } |
| |
| /* |
| ** Part of sqlite3WhereEnd() will rewrite opcodes to reference the |
| ** index rather than the main table. In SQLITE_DEBUG mode, we want |
| ** to trace those changes if PRAGMA vdbe_addoptrace=on. This routine |
| ** does that. |
| */ |
| #ifndef SQLITE_DEBUG |
| # define OpcodeRewriteTrace(D,K,P) /* no-op */ |
| #else |
| # define OpcodeRewriteTrace(D,K,P) sqlite3WhereOpcodeRewriteTrace(D,K,P) |
| static void sqlite3WhereOpcodeRewriteTrace( |
| sqlite3 *db, |
| int pc, |
| VdbeOp *pOp |
| ){ |
| if( (db->flags & SQLITE_VdbeAddopTrace)==0 ) return; |
| sqlite3VdbePrintOp(0, pc, pOp); |
| } |
| #endif |
| |
| /* |
| ** Generate the end of the WHERE loop. See comments on |
| ** sqlite3WhereBegin() for additional information. |
| */ |
| void sqlite3WhereEnd(WhereInfo *pWInfo){ |
| Parse *pParse = pWInfo->pParse; |
| Vdbe *v = pParse->pVdbe; |
| int i; |
| WhereLevel *pLevel; |
| WhereLoop *pLoop; |
| SrcList *pTabList = pWInfo->pTabList; |
| sqlite3 *db = pParse->db; |
| |
| /* Generate loop termination code. |
| */ |
| VdbeModuleComment((v, "End WHERE-core")); |
| for(i=pWInfo->nLevel-1; i>=0; i--){ |
| int addr; |
| pLevel = &pWInfo->a[i]; |
| pLoop = pLevel->pWLoop; |
| if( pLevel->op!=OP_Noop ){ |
| #ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT |
| int addrSeek = 0; |
| Index *pIdx; |
| int n; |
| if( pWInfo->eDistinct==WHERE_DISTINCT_ORDERED |
| && i==pWInfo->nLevel-1 /* Ticket [ef9318757b152e3] 2017-10-21 */ |
| && (pLoop->wsFlags & WHERE_INDEXED)!=0 |
| && (pIdx = pLoop->u.btree.pIndex)->hasStat1 |
| && (n = pLoop->u.btree.nIdxCol)>0 |
| && pIdx->aiRowLogEst[n]>=36 |
| ){ |
| int r1 = pParse->nMem+1; |
| int j, op; |
| for(j=0; j<n; j++){ |
| sqlite3VdbeAddOp3(v, OP_Column, pLevel->iIdxCur, j, r1+j); |
| } |
| pParse->nMem += n+1; |
| op = pLevel->op==OP_Prev ? OP_SeekLT : OP_SeekGT; |
| addrSeek = sqlite3VdbeAddOp4Int(v, op, pLevel->iIdxCur, 0, r1, n); |
| VdbeCoverageIf(v, op==OP_SeekLT); |
| VdbeCoverageIf(v, op==OP_SeekGT); |
| sqlite3VdbeAddOp2(v, OP_Goto, 1, pLevel->p2); |
| } |
| #endif /* SQLITE_DISABLE_SKIPAHEAD_DISTINCT */ |
| /* The common case: Advance to the next row */ |
| sqlite3VdbeResolveLabel(v, pLevel->addrCont); |
| sqlite3VdbeAddOp3(v, pLevel->op, pLevel->p1, pLevel->p2, pLevel->p3); |
| sqlite3VdbeChangeP5(v, pLevel->p5); |
| VdbeCoverage(v); |
| VdbeCoverageIf(v, pLevel->op==OP_Next); |
| VdbeCoverageIf(v, pLevel->op==OP_Prev); |
| VdbeCoverageIf(v, pLevel->op==OP_VNext); |
| #ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT |
| if( addrSeek ) sqlite3VdbeJumpHere(v, addrSeek); |
| #endif |
| }else{ |
| sqlite3VdbeResolveLabel(v, pLevel->addrCont); |
| } |
| if( pLoop->wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){ |
| struct InLoop *pIn; |
| int j; |
| sqlite3VdbeResolveLabel(v, pLevel->addrNxt); |
| for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){ |
| sqlite3VdbeJumpHere(v, pIn->addrInTop+1); |
| if( pIn->eEndLoopOp!=OP_Noop ){ |
| if( pIn->nPrefix ){ |
| assert( pLoop->wsFlags & WHERE_IN_EARLYOUT ); |
| sqlite3VdbeAddOp4Int(v, OP_IfNoHope, pLevel->iIdxCur, |
| sqlite3VdbeCurrentAddr(v)+2, |
| pIn->iBase, pIn->nPrefix); |
| VdbeCoverage(v); |
| } |
| sqlite3VdbeAddOp2(v, pIn->eEndLoopOp, pIn->iCur, pIn->addrInTop); |
| VdbeCoverage(v); |
| VdbeCoverageIf(v, pIn->eEndLoopOp==OP_Prev); |
| VdbeCoverageIf(v, pIn->eEndLoopOp==OP_Next); |
| } |
| sqlite3VdbeJumpHere(v, pIn->addrInTop-1); |
| } |
| } |
| sqlite3VdbeResolveLabel(v, pLevel->addrBrk); |
| if( pLevel->addrSkip ){ |
| sqlite3VdbeGoto(v, pLevel->addrSkip); |
| VdbeComment((v, "next skip-scan on %s", pLoop->u.btree.pIndex->zName)); |
| sqlite3VdbeJumpHere(v, pLevel->addrSkip); |
| sqlite3VdbeJumpHere(v, pLevel->addrSkip-2); |
| } |
| #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS |
| if( pLevel->addrLikeRep ){ |
| sqlite3VdbeAddOp2(v, OP_DecrJumpZero, (int)(pLevel->iLikeRepCntr>>1), |
| pLevel->addrLikeRep); |
| VdbeCoverage(v); |
| } |
| #endif |
| if( pLevel->iLeftJoin ){ |
| int ws = pLoop->wsFlags; |
| addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin); VdbeCoverage(v); |
| assert( (ws & WHERE_IDX_ONLY)==0 || (ws & WHERE_INDEXED)!=0 ); |
| if( (ws & WHERE_IDX_ONLY)==0 ){ |
| assert( pLevel->iTabCur==pTabList->a[pLevel->iFrom].iCursor ); |
| sqlite3VdbeAddOp1(v, OP_NullRow, pLevel->iTabCur); |
| } |
| if( (ws & WHERE_INDEXED) |
| || ((ws & WHERE_MULTI_OR) && pLevel->u.pCovidx) |
| ){ |
| sqlite3VdbeAddOp1(v, OP_NullRow, pLevel->iIdxCur); |
| } |
| if( pLevel->op==OP_Return ){ |
| sqlite3VdbeAddOp2(v, OP_Gosub, pLevel->p1, pLevel->addrFirst); |
| }else{ |
| sqlite3VdbeGoto(v, pLevel->addrFirst); |
| } |
| sqlite3VdbeJumpHere(v, addr); |
| } |
| VdbeModuleComment((v, "End WHERE-loop%d: %s", i, |
| pWInfo->pTabList->a[pLevel->iFrom].pTab->zName)); |
| } |
| |
| /* The "break" point is here, just past the end of the outer loop. |
| ** Set it. |
| */ |
| sqlite3VdbeResolveLabel(v, pWInfo->iBreak); |
| |
| assert( pWInfo->nLevel<=pTabList->nSrc ); |
| for(i=0, pLevel=pWInfo->a; i<pWInfo->nLevel; i++, pLevel++){ |
| int k, last; |
| VdbeOp *pOp; |
| Index *pIdx = 0; |
| struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom]; |
| Table *pTab = pTabItem->pTab; |
| assert( pTab!=0 ); |
| pLoop = pLevel->pWLoop; |
| |
| /* For a co-routine, change all OP_Column references to the table of |
| ** the co-routine into OP_Copy of result contained in a register. |
| ** OP_Rowid becomes OP_Null. |
| */ |
| if( pTabItem->fg.viaCoroutine ){ |
| testcase( pParse->db->mallocFailed ); |
| translateColumnToCopy(pParse, pLevel->addrBody, pLevel->iTabCur, |
| pTabItem->regResult, 0); |
| continue; |
| } |
| |
| #ifdef SQLITE_ENABLE_EARLY_CURSOR_CLOSE |
| /* Close all of the cursors that were opened by sqlite3WhereBegin. |
| ** Except, do not close cursors that will be reused by the OR optimization |
| ** (WHERE_OR_SUBCLAUSE). And do not close the OP_OpenWrite cursors |
| ** created for the ONEPASS optimization. |
| */ |
| if( (pTab->tabFlags & TF_Ephemeral)==0 |
| && pTab->pSelect==0 |
| && (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)==0 |
| ){ |
| int ws = pLoop->wsFlags; |
| if( pWInfo->eOnePass==ONEPASS_OFF && (ws & WHERE_IDX_ONLY)==0 ){ |
| sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor); |
| } |
| if( (ws & WHERE_INDEXED)!=0 |
| && (ws & (WHERE_IPK|WHERE_AUTO_INDEX))==0 |
| && pLevel->iIdxCur!=pWInfo->aiCurOnePass[1] |
| ){ |
| sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur); |
| } |
| } |
| #endif |
| |
| /* If this scan uses an index, make VDBE code substitutions to read data |
| ** from the index instead of from the table where possible. In some cases |
| ** this optimization prevents the table from ever being read, which can |
| ** yield a significant performance boost. |
| ** |
| ** Calls to the code generator in between sqlite3WhereBegin and |
| ** sqlite3WhereEnd will have created code that references the table |
| ** directly. This loop scans all that code looking for opcodes |
| ** that reference the table and converts them into opcodes that |
| ** reference the index. |
| */ |
| if( pLoop->wsFlags & (WHERE_INDEXED|WHERE_IDX_ONLY) ){ |
| pIdx = pLoop->u.btree.pIndex; |
| }else if( pLoop->wsFlags & WHERE_MULTI_OR ){ |
| pIdx = pLevel->u.pCovidx; |
| } |
| if( pIdx |
| && (pWInfo->eOnePass==ONEPASS_OFF || !HasRowid(pIdx->pTable)) |
| && !db->mallocFailed |
| ){ |
| last = sqlite3VdbeCurrentAddr(v); |
| k = pLevel->addrBody; |
| #ifdef SQLITE_DEBUG |
| if( db->flags & SQLITE_VdbeAddopTrace ){ |
| printf("TRANSLATE opcodes in range %d..%d\n", k, last-1); |
| } |
| #endif |
| pOp = sqlite3VdbeGetOp(v, k); |
| for(; k<last; k++, pOp++){ |
| if( pOp->p1!=pLevel->iTabCur ) continue; |
| if( pOp->opcode==OP_Column |
| #ifdef SQLITE_ENABLE_OFFSET_SQL_FUNC |
| || pOp->opcode==OP_Offset |
| #endif |
| ){ |
| int x = pOp->p2; |
| assert( pIdx->pTable==pTab ); |
| if( !HasRowid(pTab) ){ |
| Index *pPk = sqlite3PrimaryKeyIndex(pTab); |
| x = pPk->aiColumn[x]; |
| assert( x>=0 ); |
| } |
| x = sqlite3ColumnOfIndex(pIdx, x); |
| if( x>=0 ){ |
| pOp->p2 = x; |
| pOp->p1 = pLevel->iIdxCur; |
| OpcodeRewriteTrace(db, k, pOp); |
| } |
| assert( (pLoop->wsFlags & WHERE_IDX_ONLY)==0 || x>=0 |
| || pWInfo->eOnePass ); |
| }else if( pOp->opcode==OP_Rowid ){ |
| pOp->p1 = pLevel->iIdxCur; |
| pOp->opcode = OP_IdxRowid; |
| OpcodeRewriteTrace(db, k, pOp); |
| }else if( pOp->opcode==OP_IfNullRow ){ |
| pOp->p1 = pLevel->iIdxCur; |
| OpcodeRewriteTrace(db, k, pOp); |
| } |
| } |
| #ifdef SQLITE_DEBUG |
| if( db->flags & SQLITE_VdbeAddopTrace ) printf("TRANSLATE complete\n"); |
| #endif |
| } |
| } |
| |
| /* Final cleanup |
| */ |
| pParse->nQueryLoop = pWInfo->savedNQueryLoop; |
| whereInfoFree(db, pWInfo); |
| return; |
| } |