| /* |
| ** 2015-06-06 |
| ** |
| ** 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 file was split off from where.c on 2015-06-06 in order to reduce the |
| ** size of where.c and make it easier to edit. This file contains the routines |
| ** that actually generate the bulk of the WHERE loop code. The original where.c |
| ** file retains the code that does query planning and analysis. |
| */ |
| #include "sqliteInt.h" |
| #include "whereInt.h" |
| |
| #ifndef SQLITE_OMIT_EXPLAIN |
| |
| /* |
| ** Return the name of the i-th column of the pIdx index. |
| */ |
| static const char *explainIndexColumnName(Index *pIdx, int i){ |
| i = pIdx->aiColumn[i]; |
| if( i==XN_EXPR ) return "<expr>"; |
| if( i==XN_ROWID ) return "rowid"; |
| return pIdx->pTable->aCol[i].zName; |
| } |
| |
| /* |
| ** This routine is a helper for explainIndexRange() below |
| ** |
| ** pStr holds the text of an expression that we are building up one term |
| ** at a time. This routine adds a new term to the end of the expression. |
| ** Terms are separated by AND so add the "AND" text for second and subsequent |
| ** terms only. |
| */ |
| static void explainAppendTerm( |
| StrAccum *pStr, /* The text expression being built */ |
| Index *pIdx, /* Index to read column names from */ |
| int nTerm, /* Number of terms */ |
| int iTerm, /* Zero-based index of first term. */ |
| int bAnd, /* Non-zero to append " AND " */ |
| const char *zOp /* Name of the operator */ |
| ){ |
| int i; |
| |
| assert( nTerm>=1 ); |
| if( bAnd ) sqlite3_str_append(pStr, " AND ", 5); |
| |
| if( nTerm>1 ) sqlite3_str_append(pStr, "(", 1); |
| for(i=0; i<nTerm; i++){ |
| if( i ) sqlite3_str_append(pStr, ",", 1); |
| sqlite3_str_appendall(pStr, explainIndexColumnName(pIdx, iTerm+i)); |
| } |
| if( nTerm>1 ) sqlite3_str_append(pStr, ")", 1); |
| |
| sqlite3_str_append(pStr, zOp, 1); |
| |
| if( nTerm>1 ) sqlite3_str_append(pStr, "(", 1); |
| for(i=0; i<nTerm; i++){ |
| if( i ) sqlite3_str_append(pStr, ",", 1); |
| sqlite3_str_append(pStr, "?", 1); |
| } |
| if( nTerm>1 ) sqlite3_str_append(pStr, ")", 1); |
| } |
| |
| /* |
| ** Argument pLevel describes a strategy for scanning table pTab. This |
| ** function appends text to pStr that describes the subset of table |
| ** rows scanned by the strategy in the form of an SQL expression. |
| ** |
| ** For example, if the query: |
| ** |
| ** SELECT * FROM t1 WHERE a=1 AND b>2; |
| ** |
| ** is run and there is an index on (a, b), then this function returns a |
| ** string similar to: |
| ** |
| ** "a=? AND b>?" |
| */ |
| static void explainIndexRange(StrAccum *pStr, WhereLoop *pLoop){ |
| Index *pIndex = pLoop->u.btree.pIndex; |
| u16 nEq = pLoop->u.btree.nEq; |
| u16 nSkip = pLoop->nSkip; |
| int i, j; |
| |
| if( nEq==0 && (pLoop->wsFlags&(WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))==0 ) return; |
| sqlite3_str_append(pStr, " (", 2); |
| for(i=0; i<nEq; i++){ |
| const char *z = explainIndexColumnName(pIndex, i); |
| if( i ) sqlite3_str_append(pStr, " AND ", 5); |
| sqlite3_str_appendf(pStr, i>=nSkip ? "%s=?" : "ANY(%s)", z); |
| } |
| |
| j = i; |
| if( pLoop->wsFlags&WHERE_BTM_LIMIT ){ |
| explainAppendTerm(pStr, pIndex, pLoop->u.btree.nBtm, j, i, ">"); |
| i = 1; |
| } |
| if( pLoop->wsFlags&WHERE_TOP_LIMIT ){ |
| explainAppendTerm(pStr, pIndex, pLoop->u.btree.nTop, j, i, "<"); |
| } |
| sqlite3_str_append(pStr, ")", 1); |
| } |
| |
| /* |
| ** This function is a no-op unless currently processing an EXPLAIN QUERY PLAN |
| ** command, or if either SQLITE_DEBUG or SQLITE_ENABLE_STMT_SCANSTATUS was |
| ** defined at compile-time. If it is not a no-op, a single OP_Explain opcode |
| ** is added to the output to describe the table scan strategy in pLevel. |
| ** |
| ** If an OP_Explain opcode is added to the VM, its address is returned. |
| ** Otherwise, if no OP_Explain is coded, zero is returned. |
| */ |
| int sqlite3WhereExplainOneScan( |
| Parse *pParse, /* Parse context */ |
| SrcList *pTabList, /* Table list this loop refers to */ |
| WhereLevel *pLevel, /* Scan to write OP_Explain opcode for */ |
| u16 wctrlFlags /* Flags passed to sqlite3WhereBegin() */ |
| ){ |
| int ret = 0; |
| #if !defined(SQLITE_DEBUG) && !defined(SQLITE_ENABLE_STMT_SCANSTATUS) |
| if( sqlite3ParseToplevel(pParse)->explain==2 ) |
| #endif |
| { |
| struct SrcList_item *pItem = &pTabList->a[pLevel->iFrom]; |
| Vdbe *v = pParse->pVdbe; /* VM being constructed */ |
| sqlite3 *db = pParse->db; /* Database handle */ |
| int isSearch; /* True for a SEARCH. False for SCAN. */ |
| WhereLoop *pLoop; /* The controlling WhereLoop object */ |
| u32 flags; /* Flags that describe this loop */ |
| char *zMsg; /* Text to add to EQP output */ |
| StrAccum str; /* EQP output string */ |
| char zBuf[100]; /* Initial space for EQP output string */ |
| |
| pLoop = pLevel->pWLoop; |
| flags = pLoop->wsFlags; |
| if( (flags&WHERE_MULTI_OR) || (wctrlFlags&WHERE_OR_SUBCLAUSE) ) return 0; |
| |
| isSearch = (flags&(WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))!=0 |
| || ((flags&WHERE_VIRTUALTABLE)==0 && (pLoop->u.btree.nEq>0)) |
| || (wctrlFlags&(WHERE_ORDERBY_MIN|WHERE_ORDERBY_MAX)); |
| |
| sqlite3StrAccumInit(&str, db, zBuf, sizeof(zBuf), SQLITE_MAX_LENGTH); |
| sqlite3_str_appendall(&str, isSearch ? "SEARCH" : "SCAN"); |
| if( pItem->pSelect ){ |
| sqlite3_str_appendf(&str, " SUBQUERY %u", pItem->pSelect->selId); |
| }else{ |
| sqlite3_str_appendf(&str, " TABLE %s", pItem->zName); |
| } |
| |
| if( pItem->zAlias ){ |
| sqlite3_str_appendf(&str, " AS %s", pItem->zAlias); |
| } |
| if( (flags & (WHERE_IPK|WHERE_VIRTUALTABLE))==0 ){ |
| const char *zFmt = 0; |
| Index *pIdx; |
| |
| assert( pLoop->u.btree.pIndex!=0 ); |
| pIdx = pLoop->u.btree.pIndex; |
| assert( !(flags&WHERE_AUTO_INDEX) || (flags&WHERE_IDX_ONLY) ); |
| if( !HasRowid(pItem->pTab) && IsPrimaryKeyIndex(pIdx) ){ |
| if( isSearch ){ |
| zFmt = "PRIMARY KEY"; |
| } |
| }else if( flags & WHERE_PARTIALIDX ){ |
| zFmt = "AUTOMATIC PARTIAL COVERING INDEX"; |
| }else if( flags & WHERE_AUTO_INDEX ){ |
| zFmt = "AUTOMATIC COVERING INDEX"; |
| }else if( flags & WHERE_IDX_ONLY ){ |
| zFmt = "COVERING INDEX %s"; |
| }else{ |
| zFmt = "INDEX %s"; |
| } |
| if( zFmt ){ |
| sqlite3_str_append(&str, " USING ", 7); |
| sqlite3_str_appendf(&str, zFmt, pIdx->zName); |
| explainIndexRange(&str, pLoop); |
| } |
| }else if( (flags & WHERE_IPK)!=0 && (flags & WHERE_CONSTRAINT)!=0 ){ |
| const char *zRangeOp; |
| if( flags&(WHERE_COLUMN_EQ|WHERE_COLUMN_IN) ){ |
| zRangeOp = "="; |
| }else if( (flags&WHERE_BOTH_LIMIT)==WHERE_BOTH_LIMIT ){ |
| zRangeOp = ">? AND rowid<"; |
| }else if( flags&WHERE_BTM_LIMIT ){ |
| zRangeOp = ">"; |
| }else{ |
| assert( flags&WHERE_TOP_LIMIT); |
| zRangeOp = "<"; |
| } |
| sqlite3_str_appendf(&str, |
| " USING INTEGER PRIMARY KEY (rowid%s?)",zRangeOp); |
| } |
| #ifndef SQLITE_OMIT_VIRTUALTABLE |
| else if( (flags & WHERE_VIRTUALTABLE)!=0 ){ |
| sqlite3_str_appendf(&str, " VIRTUAL TABLE INDEX %d:%s", |
| pLoop->u.vtab.idxNum, pLoop->u.vtab.idxStr); |
| } |
| #endif |
| #ifdef SQLITE_EXPLAIN_ESTIMATED_ROWS |
| if( pLoop->nOut>=10 ){ |
| sqlite3_str_appendf(&str, " (~%llu rows)", |
| sqlite3LogEstToInt(pLoop->nOut)); |
| }else{ |
| sqlite3_str_append(&str, " (~1 row)", 9); |
| } |
| #endif |
| zMsg = sqlite3StrAccumFinish(&str); |
| sqlite3ExplainBreakpoint("",zMsg); |
| ret = sqlite3VdbeAddOp4(v, OP_Explain, sqlite3VdbeCurrentAddr(v), |
| pParse->addrExplain, 0, zMsg,P4_DYNAMIC); |
| } |
| return ret; |
| } |
| #endif /* SQLITE_OMIT_EXPLAIN */ |
| |
| #ifdef SQLITE_ENABLE_STMT_SCANSTATUS |
| /* |
| ** Configure the VM passed as the first argument with an |
| ** sqlite3_stmt_scanstatus() entry corresponding to the scan used to |
| ** implement level pLvl. Argument pSrclist is a pointer to the FROM |
| ** clause that the scan reads data from. |
| ** |
| ** If argument addrExplain is not 0, it must be the address of an |
| ** OP_Explain instruction that describes the same loop. |
| */ |
| void sqlite3WhereAddScanStatus( |
| Vdbe *v, /* Vdbe to add scanstatus entry to */ |
| SrcList *pSrclist, /* FROM clause pLvl reads data from */ |
| WhereLevel *pLvl, /* Level to add scanstatus() entry for */ |
| int addrExplain /* Address of OP_Explain (or 0) */ |
| ){ |
| const char *zObj = 0; |
| WhereLoop *pLoop = pLvl->pWLoop; |
| if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 && pLoop->u.btree.pIndex!=0 ){ |
| zObj = pLoop->u.btree.pIndex->zName; |
| }else{ |
| zObj = pSrclist->a[pLvl->iFrom].zName; |
| } |
| sqlite3VdbeScanStatus( |
| v, addrExplain, pLvl->addrBody, pLvl->addrVisit, pLoop->nOut, zObj |
| ); |
| } |
| #endif |
| |
| |
| /* |
| ** Disable a term in the WHERE clause. Except, do not disable the term |
| ** if it controls a LEFT OUTER JOIN and it did not originate in the ON |
| ** or USING clause of that join. |
| ** |
| ** Consider the term t2.z='ok' in the following queries: |
| ** |
| ** (1) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok' |
| ** (2) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok' |
| ** (3) SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok' |
| ** |
| ** The t2.z='ok' is disabled in the in (2) because it originates |
| ** in the ON clause. The term is disabled in (3) because it is not part |
| ** of a LEFT OUTER JOIN. In (1), the term is not disabled. |
| ** |
| ** Disabling a term causes that term to not be tested in the inner loop |
| ** of the join. Disabling is an optimization. When terms are satisfied |
| ** by indices, we disable them to prevent redundant tests in the inner |
| ** loop. We would get the correct results if nothing were ever disabled, |
| ** but joins might run a little slower. The trick is to disable as much |
| ** as we can without disabling too much. If we disabled in (1), we'd get |
| ** the wrong answer. See ticket #813. |
| ** |
| ** If all the children of a term are disabled, then that term is also |
| ** automatically disabled. In this way, terms get disabled if derived |
| ** virtual terms are tested first. For example: |
| ** |
| ** x GLOB 'abc*' AND x>='abc' AND x<'acd' |
| ** \___________/ \______/ \_____/ |
| ** parent child1 child2 |
| ** |
| ** Only the parent term was in the original WHERE clause. The child1 |
| ** and child2 terms were added by the LIKE optimization. If both of |
| ** the virtual child terms are valid, then testing of the parent can be |
| ** skipped. |
| ** |
| ** Usually the parent term is marked as TERM_CODED. But if the parent |
| ** term was originally TERM_LIKE, then the parent gets TERM_LIKECOND instead. |
| ** The TERM_LIKECOND marking indicates that the term should be coded inside |
| ** a conditional such that is only evaluated on the second pass of a |
| ** LIKE-optimization loop, when scanning BLOBs instead of strings. |
| */ |
| static void disableTerm(WhereLevel *pLevel, WhereTerm *pTerm){ |
| int nLoop = 0; |
| assert( pTerm!=0 ); |
| while( (pTerm->wtFlags & TERM_CODED)==0 |
| && (pLevel->iLeftJoin==0 || ExprHasProperty(pTerm->pExpr, EP_FromJoin)) |
| && (pLevel->notReady & pTerm->prereqAll)==0 |
| ){ |
| if( nLoop && (pTerm->wtFlags & TERM_LIKE)!=0 ){ |
| pTerm->wtFlags |= TERM_LIKECOND; |
| }else{ |
| pTerm->wtFlags |= TERM_CODED; |
| } |
| if( pTerm->iParent<0 ) break; |
| pTerm = &pTerm->pWC->a[pTerm->iParent]; |
| assert( pTerm!=0 ); |
| pTerm->nChild--; |
| if( pTerm->nChild!=0 ) break; |
| nLoop++; |
| } |
| } |
| |
| /* |
| ** Code an OP_Affinity opcode to apply the column affinity string zAff |
| ** to the n registers starting at base. |
| ** |
| ** As an optimization, SQLITE_AFF_BLOB entries (which are no-ops) at the |
| ** beginning and end of zAff are ignored. If all entries in zAff are |
| ** SQLITE_AFF_BLOB, then no code gets generated. |
| ** |
| ** This routine makes its own copy of zAff so that the caller is free |
| ** to modify zAff after this routine returns. |
| */ |
| static void codeApplyAffinity(Parse *pParse, int base, int n, char *zAff){ |
| Vdbe *v = pParse->pVdbe; |
| if( zAff==0 ){ |
| assert( pParse->db->mallocFailed ); |
| return; |
| } |
| assert( v!=0 ); |
| |
| /* Adjust base and n to skip over SQLITE_AFF_BLOB entries at the beginning |
| ** and end of the affinity string. |
| */ |
| while( n>0 && zAff[0]==SQLITE_AFF_BLOB ){ |
| n--; |
| base++; |
| zAff++; |
| } |
| while( n>1 && zAff[n-1]==SQLITE_AFF_BLOB ){ |
| n--; |
| } |
| |
| /* Code the OP_Affinity opcode if there is anything left to do. */ |
| if( n>0 ){ |
| sqlite3VdbeAddOp4(v, OP_Affinity, base, n, 0, zAff, n); |
| } |
| } |
| |
| /* |
| ** Expression pRight, which is the RHS of a comparison operation, is |
| ** either a vector of n elements or, if n==1, a scalar expression. |
| ** Before the comparison operation, affinity zAff is to be applied |
| ** to the pRight values. This function modifies characters within the |
| ** affinity string to SQLITE_AFF_BLOB if either: |
| ** |
| ** * the comparison will be performed with no affinity, or |
| ** * the affinity change in zAff is guaranteed not to change the value. |
| */ |
| static void updateRangeAffinityStr( |
| Expr *pRight, /* RHS of comparison */ |
| int n, /* Number of vector elements in comparison */ |
| char *zAff /* Affinity string to modify */ |
| ){ |
| int i; |
| for(i=0; i<n; i++){ |
| Expr *p = sqlite3VectorFieldSubexpr(pRight, i); |
| if( sqlite3CompareAffinity(p, zAff[i])==SQLITE_AFF_BLOB |
| || sqlite3ExprNeedsNoAffinityChange(p, zAff[i]) |
| ){ |
| zAff[i] = SQLITE_AFF_BLOB; |
| } |
| } |
| } |
| |
| |
| /* |
| ** pX is an expression of the form: (vector) IN (SELECT ...) |
| ** In other words, it is a vector IN operator with a SELECT clause on the |
| ** LHS. But not all terms in the vector are indexable and the terms might |
| ** not be in the correct order for indexing. |
| ** |
| ** This routine makes a copy of the input pX expression and then adjusts |
| ** the vector on the LHS with corresponding changes to the SELECT so that |
| ** the vector contains only index terms and those terms are in the correct |
| ** order. The modified IN expression is returned. The caller is responsible |
| ** for deleting the returned expression. |
| ** |
| ** Example: |
| ** |
| ** CREATE TABLE t1(a,b,c,d,e,f); |
| ** CREATE INDEX t1x1 ON t1(e,c); |
| ** SELECT * FROM t1 WHERE (a,b,c,d,e) IN (SELECT v,w,x,y,z FROM t2) |
| ** \_______________________________________/ |
| ** The pX expression |
| ** |
| ** Since only columns e and c can be used with the index, in that order, |
| ** the modified IN expression that is returned will be: |
| ** |
| ** (e,c) IN (SELECT z,x FROM t2) |
| ** |
| ** The reduced pX is different from the original (obviously) and thus is |
| ** only used for indexing, to improve performance. The original unaltered |
| ** IN expression must also be run on each output row for correctness. |
| */ |
| static Expr *removeUnindexableInClauseTerms( |
| Parse *pParse, /* The parsing context */ |
| int iEq, /* Look at loop terms starting here */ |
| WhereLoop *pLoop, /* The current loop */ |
| Expr *pX /* The IN expression to be reduced */ |
| ){ |
| sqlite3 *db = pParse->db; |
| Expr *pNew = sqlite3ExprDup(db, pX, 0); |
| if( db->mallocFailed==0 ){ |
| ExprList *pOrigRhs = pNew->x.pSelect->pEList; /* Original unmodified RHS */ |
| ExprList *pOrigLhs = pNew->pLeft->x.pList; /* Original unmodified LHS */ |
| ExprList *pRhs = 0; /* New RHS after modifications */ |
| ExprList *pLhs = 0; /* New LHS after mods */ |
| int i; /* Loop counter */ |
| Select *pSelect; /* Pointer to the SELECT on the RHS */ |
| |
| for(i=iEq; i<pLoop->nLTerm; i++){ |
| if( pLoop->aLTerm[i]->pExpr==pX ){ |
| int iField = pLoop->aLTerm[i]->iField - 1; |
| if( pOrigRhs->a[iField].pExpr==0 ) continue; /* Duplicate PK column */ |
| pRhs = sqlite3ExprListAppend(pParse, pRhs, pOrigRhs->a[iField].pExpr); |
| pOrigRhs->a[iField].pExpr = 0; |
| assert( pOrigLhs->a[iField].pExpr!=0 ); |
| pLhs = sqlite3ExprListAppend(pParse, pLhs, pOrigLhs->a[iField].pExpr); |
| pOrigLhs->a[iField].pExpr = 0; |
| } |
| } |
| sqlite3ExprListDelete(db, pOrigRhs); |
| sqlite3ExprListDelete(db, pOrigLhs); |
| pNew->pLeft->x.pList = pLhs; |
| pNew->x.pSelect->pEList = pRhs; |
| if( pLhs && pLhs->nExpr==1 ){ |
| /* Take care here not to generate a TK_VECTOR containing only a |
| ** single value. Since the parser never creates such a vector, some |
| ** of the subroutines do not handle this case. */ |
| Expr *p = pLhs->a[0].pExpr; |
| pLhs->a[0].pExpr = 0; |
| sqlite3ExprDelete(db, pNew->pLeft); |
| pNew->pLeft = p; |
| } |
| pSelect = pNew->x.pSelect; |
| if( pSelect->pOrderBy ){ |
| /* If the SELECT statement has an ORDER BY clause, zero the |
| ** iOrderByCol variables. These are set to non-zero when an |
| ** ORDER BY term exactly matches one of the terms of the |
| ** result-set. Since the result-set of the SELECT statement may |
| ** have been modified or reordered, these variables are no longer |
| ** set correctly. Since setting them is just an optimization, |
| ** it's easiest just to zero them here. */ |
| ExprList *pOrderBy = pSelect->pOrderBy; |
| for(i=0; i<pOrderBy->nExpr; i++){ |
| pOrderBy->a[i].u.x.iOrderByCol = 0; |
| } |
| } |
| |
| #if 0 |
| printf("For indexing, change the IN expr:\n"); |
| sqlite3TreeViewExpr(0, pX, 0); |
| printf("Into:\n"); |
| sqlite3TreeViewExpr(0, pNew, 0); |
| #endif |
| } |
| return pNew; |
| } |
| |
| |
| /* |
| ** Generate code for a single equality term of the WHERE clause. An equality |
| ** term can be either X=expr or X IN (...). pTerm is the term to be |
| ** coded. |
| ** |
| ** The current value for the constraint is left in a register, the index |
| ** of which is returned. An attempt is made store the result in iTarget but |
| ** this is only guaranteed for TK_ISNULL and TK_IN constraints. If the |
| ** constraint is a TK_EQ or TK_IS, then the current value might be left in |
| ** some other register and it is the caller's responsibility to compensate. |
| ** |
| ** For a constraint of the form X=expr, the expression is evaluated in |
| ** straight-line code. For constraints of the form X IN (...) |
| ** this routine sets up a loop that will iterate over all values of X. |
| */ |
| static int codeEqualityTerm( |
| Parse *pParse, /* The parsing context */ |
| WhereTerm *pTerm, /* The term of the WHERE clause to be coded */ |
| WhereLevel *pLevel, /* The level of the FROM clause we are working on */ |
| int iEq, /* Index of the equality term within this level */ |
| int bRev, /* True for reverse-order IN operations */ |
| int iTarget /* Attempt to leave results in this register */ |
| ){ |
| Expr *pX = pTerm->pExpr; |
| Vdbe *v = pParse->pVdbe; |
| int iReg; /* Register holding results */ |
| |
| assert( pLevel->pWLoop->aLTerm[iEq]==pTerm ); |
| assert( iTarget>0 ); |
| if( pX->op==TK_EQ || pX->op==TK_IS ){ |
| iReg = sqlite3ExprCodeTarget(pParse, pX->pRight, iTarget); |
| }else if( pX->op==TK_ISNULL ){ |
| iReg = iTarget; |
| sqlite3VdbeAddOp2(v, OP_Null, 0, iReg); |
| #ifndef SQLITE_OMIT_SUBQUERY |
| }else{ |
| int eType = IN_INDEX_NOOP; |
| int iTab; |
| struct InLoop *pIn; |
| WhereLoop *pLoop = pLevel->pWLoop; |
| int i; |
| int nEq = 0; |
| int *aiMap = 0; |
| |
| if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 |
| && pLoop->u.btree.pIndex!=0 |
| && pLoop->u.btree.pIndex->aSortOrder[iEq] |
| ){ |
| testcase( iEq==0 ); |
| testcase( bRev ); |
| bRev = !bRev; |
| } |
| assert( pX->op==TK_IN ); |
| iReg = iTarget; |
| |
| for(i=0; i<iEq; i++){ |
| if( pLoop->aLTerm[i] && pLoop->aLTerm[i]->pExpr==pX ){ |
| disableTerm(pLevel, pTerm); |
| return iTarget; |
| } |
| } |
| for(i=iEq;i<pLoop->nLTerm; i++){ |
| assert( pLoop->aLTerm[i]!=0 ); |
| if( pLoop->aLTerm[i]->pExpr==pX ) nEq++; |
| } |
| |
| iTab = 0; |
| if( (pX->flags & EP_xIsSelect)==0 || pX->x.pSelect->pEList->nExpr==1 ){ |
| eType = sqlite3FindInIndex(pParse, pX, IN_INDEX_LOOP, 0, 0, &iTab); |
| }else{ |
| sqlite3 *db = pParse->db; |
| pX = removeUnindexableInClauseTerms(pParse, iEq, pLoop, pX); |
| |
| if( !db->mallocFailed ){ |
| aiMap = (int*)sqlite3DbMallocZero(pParse->db, sizeof(int)*nEq); |
| eType = sqlite3FindInIndex(pParse, pX, IN_INDEX_LOOP, 0, aiMap, &iTab); |
| pTerm->pExpr->iTable = iTab; |
| } |
| sqlite3ExprDelete(db, pX); |
| pX = pTerm->pExpr; |
| } |
| |
| if( eType==IN_INDEX_INDEX_DESC ){ |
| testcase( bRev ); |
| bRev = !bRev; |
| } |
| sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iTab, 0); |
| VdbeCoverageIf(v, bRev); |
| VdbeCoverageIf(v, !bRev); |
| assert( (pLoop->wsFlags & WHERE_MULTI_OR)==0 ); |
| |
| pLoop->wsFlags |= WHERE_IN_ABLE; |
| if( pLevel->u.in.nIn==0 ){ |
| pLevel->addrNxt = sqlite3VdbeMakeLabel(pParse); |
| } |
| |
| i = pLevel->u.in.nIn; |
| pLevel->u.in.nIn += nEq; |
| pLevel->u.in.aInLoop = |
| sqlite3DbReallocOrFree(pParse->db, pLevel->u.in.aInLoop, |
| sizeof(pLevel->u.in.aInLoop[0])*pLevel->u.in.nIn); |
| pIn = pLevel->u.in.aInLoop; |
| if( pIn ){ |
| int iMap = 0; /* Index in aiMap[] */ |
| pIn += i; |
| for(i=iEq;i<pLoop->nLTerm; i++){ |
| if( pLoop->aLTerm[i]->pExpr==pX ){ |
| int iOut = iReg + i - iEq; |
| if( eType==IN_INDEX_ROWID ){ |
| testcase( nEq>1 ); /* Happens with a UNIQUE index on ROWID */ |
| pIn->addrInTop = sqlite3VdbeAddOp2(v, OP_Rowid, iTab, iOut); |
| }else{ |
| int iCol = aiMap ? aiMap[iMap++] : 0; |
| pIn->addrInTop = sqlite3VdbeAddOp3(v,OP_Column,iTab, iCol, iOut); |
| } |
| sqlite3VdbeAddOp1(v, OP_IsNull, iOut); VdbeCoverage(v); |
| if( i==iEq ){ |
| pIn->iCur = iTab; |
| pIn->eEndLoopOp = bRev ? OP_Prev : OP_Next; |
| if( iEq>0 && (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 ){ |
| pIn->iBase = iReg - i; |
| pIn->nPrefix = i; |
| pLoop->wsFlags |= WHERE_IN_EARLYOUT; |
| }else{ |
| pIn->nPrefix = 0; |
| } |
| }else{ |
| pIn->eEndLoopOp = OP_Noop; |
| } |
| pIn++; |
| } |
| } |
| }else{ |
| pLevel->u.in.nIn = 0; |
| } |
| sqlite3DbFree(pParse->db, aiMap); |
| #endif |
| } |
| disableTerm(pLevel, pTerm); |
| return iReg; |
| } |
| |
| /* |
| ** Generate code that will evaluate all == and IN constraints for an |
| ** index scan. |
| ** |
| ** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c). |
| ** Suppose the WHERE clause is this: a==5 AND b IN (1,2,3) AND c>5 AND c<10 |
| ** The index has as many as three equality constraints, but in this |
| ** example, the third "c" value is an inequality. So only two |
| ** constraints are coded. This routine will generate code to evaluate |
| ** a==5 and b IN (1,2,3). The current values for a and b will be stored |
| ** in consecutive registers and the index of the first register is returned. |
| ** |
| ** In the example above nEq==2. But this subroutine works for any value |
| ** of nEq including 0. If nEq==0, this routine is nearly a no-op. |
| ** The only thing it does is allocate the pLevel->iMem memory cell and |
| ** compute the affinity string. |
| ** |
| ** The nExtraReg parameter is 0 or 1. It is 0 if all WHERE clause constraints |
| ** are == or IN and are covered by the nEq. nExtraReg is 1 if there is |
| ** an inequality constraint (such as the "c>=5 AND c<10" in the example) that |
| ** occurs after the nEq quality constraints. |
| ** |
| ** This routine allocates a range of nEq+nExtraReg memory cells and returns |
| ** the index of the first memory cell in that range. The code that |
| ** calls this routine will use that memory range to store keys for |
| ** start and termination conditions of the loop. |
| ** key value of the loop. If one or more IN operators appear, then |
| ** this routine allocates an additional nEq memory cells for internal |
| ** use. |
| ** |
| ** Before returning, *pzAff is set to point to a buffer containing a |
| ** copy of the column affinity string of the index allocated using |
| ** sqlite3DbMalloc(). Except, entries in the copy of the string associated |
| ** with equality constraints that use BLOB or NONE affinity are set to |
| ** SQLITE_AFF_BLOB. This is to deal with SQL such as the following: |
| ** |
| ** CREATE TABLE t1(a TEXT PRIMARY KEY, b); |
| ** SELECT ... FROM t1 AS t2, t1 WHERE t1.a = t2.b; |
| ** |
| ** In the example above, the index on t1(a) has TEXT affinity. But since |
| ** the right hand side of the equality constraint (t2.b) has BLOB/NONE affinity, |
| ** no conversion should be attempted before using a t2.b value as part of |
| ** a key to search the index. Hence the first byte in the returned affinity |
| ** string in this example would be set to SQLITE_AFF_BLOB. |
| */ |
| static int codeAllEqualityTerms( |
| Parse *pParse, /* Parsing context */ |
| WhereLevel *pLevel, /* Which nested loop of the FROM we are coding */ |
| int bRev, /* Reverse the order of IN operators */ |
| int nExtraReg, /* Number of extra registers to allocate */ |
| char **pzAff /* OUT: Set to point to affinity string */ |
| ){ |
| u16 nEq; /* The number of == or IN constraints to code */ |
| u16 nSkip; /* Number of left-most columns to skip */ |
| Vdbe *v = pParse->pVdbe; /* The vm under construction */ |
| Index *pIdx; /* The index being used for this loop */ |
| WhereTerm *pTerm; /* A single constraint term */ |
| WhereLoop *pLoop; /* The WhereLoop object */ |
| int j; /* Loop counter */ |
| int regBase; /* Base register */ |
| int nReg; /* Number of registers to allocate */ |
| char *zAff; /* Affinity string to return */ |
| |
| /* This module is only called on query plans that use an index. */ |
| pLoop = pLevel->pWLoop; |
| assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 ); |
| nEq = pLoop->u.btree.nEq; |
| nSkip = pLoop->nSkip; |
| pIdx = pLoop->u.btree.pIndex; |
| assert( pIdx!=0 ); |
| |
| /* Figure out how many memory cells we will need then allocate them. |
| */ |
| regBase = pParse->nMem + 1; |
| nReg = pLoop->u.btree.nEq + nExtraReg; |
| pParse->nMem += nReg; |
| |
| zAff = sqlite3DbStrDup(pParse->db,sqlite3IndexAffinityStr(pParse->db,pIdx)); |
| assert( zAff!=0 || pParse->db->mallocFailed ); |
| |
| if( nSkip ){ |
| int iIdxCur = pLevel->iIdxCur; |
| sqlite3VdbeAddOp1(v, (bRev?OP_Last:OP_Rewind), iIdxCur); |
| VdbeCoverageIf(v, bRev==0); |
| VdbeCoverageIf(v, bRev!=0); |
| VdbeComment((v, "begin skip-scan on %s", pIdx->zName)); |
| j = sqlite3VdbeAddOp0(v, OP_Goto); |
| pLevel->addrSkip = sqlite3VdbeAddOp4Int(v, (bRev?OP_SeekLT:OP_SeekGT), |
| iIdxCur, 0, regBase, nSkip); |
| VdbeCoverageIf(v, bRev==0); |
| VdbeCoverageIf(v, bRev!=0); |
| sqlite3VdbeJumpHere(v, j); |
| for(j=0; j<nSkip; j++){ |
| sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, j, regBase+j); |
| testcase( pIdx->aiColumn[j]==XN_EXPR ); |
| VdbeComment((v, "%s", explainIndexColumnName(pIdx, j))); |
| } |
| } |
| |
| /* Evaluate the equality constraints |
| */ |
| assert( zAff==0 || (int)strlen(zAff)>=nEq ); |
| for(j=nSkip; j<nEq; j++){ |
| int r1; |
| pTerm = pLoop->aLTerm[j]; |
| assert( pTerm!=0 ); |
| /* The following testcase is true for indices with redundant columns. |
| ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */ |
| testcase( (pTerm->wtFlags & TERM_CODED)!=0 ); |
| testcase( pTerm->wtFlags & TERM_VIRTUAL ); |
| r1 = codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, regBase+j); |
| if( r1!=regBase+j ){ |
| if( nReg==1 ){ |
| sqlite3ReleaseTempReg(pParse, regBase); |
| regBase = r1; |
| }else{ |
| sqlite3VdbeAddOp2(v, OP_SCopy, r1, regBase+j); |
| } |
| } |
| if( pTerm->eOperator & WO_IN ){ |
| if( pTerm->pExpr->flags & EP_xIsSelect ){ |
| /* No affinity ever needs to be (or should be) applied to a value |
| ** from the RHS of an "? IN (SELECT ...)" expression. The |
| ** sqlite3FindInIndex() routine has already ensured that the |
| ** affinity of the comparison has been applied to the value. */ |
| if( zAff ) zAff[j] = SQLITE_AFF_BLOB; |
| } |
| }else if( (pTerm->eOperator & WO_ISNULL)==0 ){ |
| Expr *pRight = pTerm->pExpr->pRight; |
| if( (pTerm->wtFlags & TERM_IS)==0 && sqlite3ExprCanBeNull(pRight) ){ |
| sqlite3VdbeAddOp2(v, OP_IsNull, regBase+j, pLevel->addrBrk); |
| VdbeCoverage(v); |
| } |
| if( zAff ){ |
| if( sqlite3CompareAffinity(pRight, zAff[j])==SQLITE_AFF_BLOB ){ |
| zAff[j] = SQLITE_AFF_BLOB; |
| } |
| if( sqlite3ExprNeedsNoAffinityChange(pRight, zAff[j]) ){ |
| zAff[j] = SQLITE_AFF_BLOB; |
| } |
| } |
| } |
| } |
| *pzAff = zAff; |
| return regBase; |
| } |
| |
| #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS |
| /* |
| ** If the most recently coded instruction is a constant range constraint |
| ** (a string literal) that originated from the LIKE optimization, then |
| ** set P3 and P5 on the OP_String opcode so that the string will be cast |
| ** to a BLOB at appropriate times. |
| ** |
| ** The LIKE optimization trys to evaluate "x LIKE 'abc%'" as a range |
| ** expression: "x>='ABC' AND x<'abd'". But this requires that the range |
| ** scan loop run twice, once for strings and a second time for BLOBs. |
| ** The OP_String opcodes on the second pass convert the upper and lower |
| ** bound string constants to blobs. This routine makes the necessary changes |
| ** to the OP_String opcodes for that to happen. |
| ** |
| ** Except, of course, if SQLITE_LIKE_DOESNT_MATCH_BLOBS is defined, then |
| ** only the one pass through the string space is required, so this routine |
| ** becomes a no-op. |
| */ |
| static void whereLikeOptimizationStringFixup( |
| Vdbe *v, /* prepared statement under construction */ |
| WhereLevel *pLevel, /* The loop that contains the LIKE operator */ |
| WhereTerm *pTerm /* The upper or lower bound just coded */ |
| ){ |
| if( pTerm->wtFlags & TERM_LIKEOPT ){ |
| VdbeOp *pOp; |
| assert( pLevel->iLikeRepCntr>0 ); |
| pOp = sqlite3VdbeGetOp(v, -1); |
| assert( pOp!=0 ); |
| assert( pOp->opcode==OP_String8 |
| || pTerm->pWC->pWInfo->pParse->db->mallocFailed ); |
| pOp->p3 = (int)(pLevel->iLikeRepCntr>>1); /* Register holding counter */ |
| pOp->p5 = (u8)(pLevel->iLikeRepCntr&1); /* ASC or DESC */ |
| } |
| } |
| #else |
| # define whereLikeOptimizationStringFixup(A,B,C) |
| #endif |
| |
| #ifdef SQLITE_ENABLE_CURSOR_HINTS |
| /* |
| ** Information is passed from codeCursorHint() down to individual nodes of |
| ** the expression tree (by sqlite3WalkExpr()) using an instance of this |
| ** structure. |
| */ |
| struct CCurHint { |
| int iTabCur; /* Cursor for the main table */ |
| int iIdxCur; /* Cursor for the index, if pIdx!=0. Unused otherwise */ |
| Index *pIdx; /* The index used to access the table */ |
| }; |
| |
| /* |
| ** This function is called for every node of an expression that is a candidate |
| ** for a cursor hint on an index cursor. For TK_COLUMN nodes that reference |
| ** the table CCurHint.iTabCur, verify that the same column can be |
| ** accessed through the index. If it cannot, then set pWalker->eCode to 1. |
| */ |
| static int codeCursorHintCheckExpr(Walker *pWalker, Expr *pExpr){ |
| struct CCurHint *pHint = pWalker->u.pCCurHint; |
| assert( pHint->pIdx!=0 ); |
| if( pExpr->op==TK_COLUMN |
| && pExpr->iTable==pHint->iTabCur |
| && sqlite3ColumnOfIndex(pHint->pIdx, pExpr->iColumn)<0 |
| ){ |
| pWalker->eCode = 1; |
| } |
| return WRC_Continue; |
| } |
| |
| /* |
| ** Test whether or not expression pExpr, which was part of a WHERE clause, |
| ** should be included in the cursor-hint for a table that is on the rhs |
| ** of a LEFT JOIN. Set Walker.eCode to non-zero before returning if the |
| ** expression is not suitable. |
| ** |
| ** An expression is unsuitable if it might evaluate to non NULL even if |
| ** a TK_COLUMN node that does affect the value of the expression is set |
| ** to NULL. For example: |
| ** |
| ** col IS NULL |
| ** col IS NOT NULL |
| ** coalesce(col, 1) |
| ** CASE WHEN col THEN 0 ELSE 1 END |
| */ |
| static int codeCursorHintIsOrFunction(Walker *pWalker, Expr *pExpr){ |
| if( pExpr->op==TK_IS |
| || pExpr->op==TK_ISNULL || pExpr->op==TK_ISNOT |
| || pExpr->op==TK_NOTNULL || pExpr->op==TK_CASE |
| ){ |
| pWalker->eCode = 1; |
| }else if( pExpr->op==TK_FUNCTION ){ |
| int d1; |
| char d2[4]; |
| if( 0==sqlite3IsLikeFunction(pWalker->pParse->db, pExpr, &d1, d2) ){ |
| pWalker->eCode = 1; |
| } |
| } |
| |
| return WRC_Continue; |
| } |
| |
| |
| /* |
| ** This function is called on every node of an expression tree used as an |
| ** argument to the OP_CursorHint instruction. If the node is a TK_COLUMN |
| ** that accesses any table other than the one identified by |
| ** CCurHint.iTabCur, then do the following: |
| ** |
| ** 1) allocate a register and code an OP_Column instruction to read |
| ** the specified column into the new register, and |
| ** |
| ** 2) transform the expression node to a TK_REGISTER node that reads |
| ** from the newly populated register. |
| ** |
| ** Also, if the node is a TK_COLUMN that does access the table idenified |
| ** by pCCurHint.iTabCur, and an index is being used (which we will |
| ** know because CCurHint.pIdx!=0) then transform the TK_COLUMN into |
| ** an access of the index rather than the original table. |
| */ |
| static int codeCursorHintFixExpr(Walker *pWalker, Expr *pExpr){ |
| int rc = WRC_Continue; |
| struct CCurHint *pHint = pWalker->u.pCCurHint; |
| if( pExpr->op==TK_COLUMN ){ |
| if( pExpr->iTable!=pHint->iTabCur ){ |
| int reg = ++pWalker->pParse->nMem; /* Register for column value */ |
| sqlite3ExprCode(pWalker->pParse, pExpr, reg); |
| pExpr->op = TK_REGISTER; |
| pExpr->iTable = reg; |
| }else if( pHint->pIdx!=0 ){ |
| pExpr->iTable = pHint->iIdxCur; |
| pExpr->iColumn = sqlite3ColumnOfIndex(pHint->pIdx, pExpr->iColumn); |
| assert( pExpr->iColumn>=0 ); |
| } |
| }else if( pExpr->op==TK_AGG_FUNCTION ){ |
| /* An aggregate function in the WHERE clause of a query means this must |
| ** be a correlated sub-query, and expression pExpr is an aggregate from |
| ** the parent context. Do not walk the function arguments in this case. |
| ** |
| ** todo: It should be possible to replace this node with a TK_REGISTER |
| ** expression, as the result of the expression must be stored in a |
| ** register at this point. The same holds for TK_AGG_COLUMN nodes. */ |
| rc = WRC_Prune; |
| } |
| return rc; |
| } |
| |
| /* |
| ** Insert an OP_CursorHint instruction if it is appropriate to do so. |
| */ |
| static void codeCursorHint( |
| struct SrcList_item *pTabItem, /* FROM clause item */ |
| WhereInfo *pWInfo, /* The where clause */ |
| WhereLevel *pLevel, /* Which loop to provide hints for */ |
| WhereTerm *pEndRange /* Hint this end-of-scan boundary term if not NULL */ |
| ){ |
| Parse *pParse = pWInfo->pParse; |
| sqlite3 *db = pParse->db; |
| Vdbe *v = pParse->pVdbe; |
| Expr *pExpr = 0; |
| WhereLoop *pLoop = pLevel->pWLoop; |
| int iCur; |
| WhereClause *pWC; |
| WhereTerm *pTerm; |
| int i, j; |
| struct CCurHint sHint; |
| Walker sWalker; |
| |
| if( OptimizationDisabled(db, SQLITE_CursorHints) ) return; |
| iCur = pLevel->iTabCur; |
| assert( iCur==pWInfo->pTabList->a[pLevel->iFrom].iCursor ); |
| sHint.iTabCur = iCur; |
| sHint.iIdxCur = pLevel->iIdxCur; |
| sHint.pIdx = pLoop->u.btree.pIndex; |
| memset(&sWalker, 0, sizeof(sWalker)); |
| sWalker.pParse = pParse; |
| sWalker.u.pCCurHint = &sHint; |
| pWC = &pWInfo->sWC; |
| for(i=0; i<pWC->nTerm; i++){ |
| pTerm = &pWC->a[i]; |
| if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue; |
| if( pTerm->prereqAll & pLevel->notReady ) continue; |
| |
| /* Any terms specified as part of the ON(...) clause for any LEFT |
| ** JOIN for which the current table is not the rhs are omitted |
| ** from the cursor-hint. |
| ** |
| ** If this table is the rhs of a LEFT JOIN, "IS" or "IS NULL" terms |
| ** that were specified as part of the WHERE clause must be excluded. |
| ** This is to address the following: |
| ** |
| ** SELECT ... t1 LEFT JOIN t2 ON (t1.a=t2.b) WHERE t2.c IS NULL; |
| ** |
| ** Say there is a single row in t2 that matches (t1.a=t2.b), but its |
| ** t2.c values is not NULL. If the (t2.c IS NULL) constraint is |
| ** pushed down to the cursor, this row is filtered out, causing |
| ** SQLite to synthesize a row of NULL values. Which does match the |
| ** WHERE clause, and so the query returns a row. Which is incorrect. |
| ** |
| ** For the same reason, WHERE terms such as: |
| ** |
| ** WHERE 1 = (t2.c IS NULL) |
| ** |
| ** are also excluded. See codeCursorHintIsOrFunction() for details. |
| */ |
| if( pTabItem->fg.jointype & JT_LEFT ){ |
| Expr *pExpr = pTerm->pExpr; |
| if( !ExprHasProperty(pExpr, EP_FromJoin) |
| || pExpr->iRightJoinTable!=pTabItem->iCursor |
| ){ |
| sWalker.eCode = 0; |
| sWalker.xExprCallback = codeCursorHintIsOrFunction; |
| sqlite3WalkExpr(&sWalker, pTerm->pExpr); |
| if( sWalker.eCode ) continue; |
| } |
| }else{ |
| if( ExprHasProperty(pTerm->pExpr, EP_FromJoin) ) continue; |
| } |
| |
| /* All terms in pWLoop->aLTerm[] except pEndRange are used to initialize |
| ** the cursor. These terms are not needed as hints for a pure range |
| ** scan (that has no == terms) so omit them. */ |
| if( pLoop->u.btree.nEq==0 && pTerm!=pEndRange ){ |
| for(j=0; j<pLoop->nLTerm && pLoop->aLTerm[j]!=pTerm; j++){} |
| if( j<pLoop->nLTerm ) continue; |
| } |
| |
| /* No subqueries or non-deterministic functions allowed */ |
| if( sqlite3ExprContainsSubquery(pTerm->pExpr) ) continue; |
| |
| /* For an index scan, make sure referenced columns are actually in |
| ** the index. */ |
| if( sHint.pIdx!=0 ){ |
| sWalker.eCode = 0; |
| sWalker.xExprCallback = codeCursorHintCheckExpr; |
| sqlite3WalkExpr(&sWalker, pTerm->pExpr); |
| if( sWalker.eCode ) continue; |
| } |
| |
| /* If we survive all prior tests, that means this term is worth hinting */ |
| pExpr = sqlite3ExprAnd(db, pExpr, sqlite3ExprDup(db, pTerm->pExpr, 0)); |
| } |
| if( pExpr!=0 ){ |
| sWalker.xExprCallback = codeCursorHintFixExpr; |
| sqlite3WalkExpr(&sWalker, pExpr); |
| sqlite3VdbeAddOp4(v, OP_CursorHint, |
| (sHint.pIdx ? sHint.iIdxCur : sHint.iTabCur), 0, 0, |
| (const char*)pExpr, P4_EXPR); |
| } |
| } |
| #else |
| # define codeCursorHint(A,B,C,D) /* No-op */ |
| #endif /* SQLITE_ENABLE_CURSOR_HINTS */ |
| |
| /* |
| ** Cursor iCur is open on an intkey b-tree (a table). Register iRowid contains |
| ** a rowid value just read from cursor iIdxCur, open on index pIdx. This |
| ** function generates code to do a deferred seek of cursor iCur to the |
| ** rowid stored in register iRowid. |
| ** |
| ** Normally, this is just: |
| ** |
| ** OP_DeferredSeek $iCur $iRowid |
| ** |
| ** However, if the scan currently being coded is a branch of an OR-loop and |
| ** the statement currently being coded is a SELECT, then P3 of OP_DeferredSeek |
| ** is set to iIdxCur and P4 is set to point to an array of integers |
| ** containing one entry for each column of the table cursor iCur is open |
| ** on. For each table column, if the column is the i'th column of the |
| ** index, then the corresponding array entry is set to (i+1). If the column |
| ** does not appear in the index at all, the array entry is set to 0. |
| */ |
| static void codeDeferredSeek( |
| WhereInfo *pWInfo, /* Where clause context */ |
| Index *pIdx, /* Index scan is using */ |
| int iCur, /* Cursor for IPK b-tree */ |
| int iIdxCur /* Index cursor */ |
| ){ |
| Parse *pParse = pWInfo->pParse; /* Parse context */ |
| Vdbe *v = pParse->pVdbe; /* Vdbe to generate code within */ |
| |
| assert( iIdxCur>0 ); |
| assert( pIdx->aiColumn[pIdx->nColumn-1]==-1 ); |
| |
| sqlite3VdbeAddOp3(v, OP_DeferredSeek, iIdxCur, 0, iCur); |
| if( (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE) |
| && DbMaskAllZero(sqlite3ParseToplevel(pParse)->writeMask) |
| ){ |
| int i; |
| Table *pTab = pIdx->pTable; |
| int *ai = (int*)sqlite3DbMallocZero(pParse->db, sizeof(int)*(pTab->nCol+1)); |
| if( ai ){ |
| ai[0] = pTab->nCol; |
| for(i=0; i<pIdx->nColumn-1; i++){ |
| assert( pIdx->aiColumn[i]<pTab->nCol ); |
| if( pIdx->aiColumn[i]>=0 ) ai[pIdx->aiColumn[i]+1] = i+1; |
| } |
| sqlite3VdbeChangeP4(v, -1, (char*)ai, P4_INTARRAY); |
| } |
| } |
| } |
| |
| /* |
| ** If the expression passed as the second argument is a vector, generate |
| ** code to write the first nReg elements of the vector into an array |
| ** of registers starting with iReg. |
| ** |
| ** If the expression is not a vector, then nReg must be passed 1. In |
| ** this case, generate code to evaluate the expression and leave the |
| ** result in register iReg. |
| */ |
| static void codeExprOrVector(Parse *pParse, Expr *p, int iReg, int nReg){ |
| assert( nReg>0 ); |
| if( p && sqlite3ExprIsVector(p) ){ |
| #ifndef SQLITE_OMIT_SUBQUERY |
| if( (p->flags & EP_xIsSelect) ){ |
| Vdbe *v = pParse->pVdbe; |
| int iSelect; |
| assert( p->op==TK_SELECT ); |
| iSelect = sqlite3CodeSubselect(pParse, p); |
| sqlite3VdbeAddOp3(v, OP_Copy, iSelect, iReg, nReg-1); |
| }else |
| #endif |
| { |
| int i; |
| ExprList *pList = p->x.pList; |
| assert( nReg<=pList->nExpr ); |
| for(i=0; i<nReg; i++){ |
| sqlite3ExprCode(pParse, pList->a[i].pExpr, iReg+i); |
| } |
| } |
| }else{ |
| assert( nReg==1 ); |
| sqlite3ExprCode(pParse, p, iReg); |
| } |
| } |
| |
| /* An instance of the IdxExprTrans object carries information about a |
| ** mapping from an expression on table columns into a column in an index |
| ** down through the Walker. |
| */ |
| typedef struct IdxExprTrans { |
| Expr *pIdxExpr; /* The index expression */ |
| int iTabCur; /* The cursor of the corresponding table */ |
| int iIdxCur; /* The cursor for the index */ |
| int iIdxCol; /* The column for the index */ |
| } IdxExprTrans; |
| |
| /* The walker node callback used to transform matching expressions into |
| ** a reference to an index column for an index on an expression. |
| ** |
| ** If pExpr matches, then transform it into a reference to the index column |
| ** that contains the value of pExpr. |
| */ |
| static int whereIndexExprTransNode(Walker *p, Expr *pExpr){ |
| IdxExprTrans *pX = p->u.pIdxTrans; |
| if( sqlite3ExprCompare(0, pExpr, pX->pIdxExpr, pX->iTabCur)==0 ){ |
| pExpr->op = TK_COLUMN; |
| pExpr->iTable = pX->iIdxCur; |
| pExpr->iColumn = pX->iIdxCol; |
| pExpr->y.pTab = 0; |
| return WRC_Prune; |
| }else{ |
| return WRC_Continue; |
| } |
| } |
| |
| /* |
| ** For an indexes on expression X, locate every instance of expression X |
| ** in pExpr and change that subexpression into a reference to the appropriate |
| ** column of the index. |
| */ |
| static void whereIndexExprTrans( |
| Index *pIdx, /* The Index */ |
| int iTabCur, /* Cursor of the table that is being indexed */ |
| int iIdxCur, /* Cursor of the index itself */ |
| WhereInfo *pWInfo /* Transform expressions in this WHERE clause */ |
| ){ |
| int iIdxCol; /* Column number of the index */ |
| ExprList *aColExpr; /* Expressions that are indexed */ |
| Walker w; |
| IdxExprTrans x; |
| aColExpr = pIdx->aColExpr; |
| if( aColExpr==0 ) return; /* Not an index on expressions */ |
| memset(&w, 0, sizeof(w)); |
| w.xExprCallback = whereIndexExprTransNode; |
| w.u.pIdxTrans = &x; |
| x.iTabCur = iTabCur; |
| x.iIdxCur = iIdxCur; |
| for(iIdxCol=0; iIdxCol<aColExpr->nExpr; iIdxCol++){ |
| if( pIdx->aiColumn[iIdxCol]!=XN_EXPR ) continue; |
| assert( aColExpr->a[iIdxCol].pExpr!=0 ); |
| x.iIdxCol = iIdxCol; |
| x.pIdxExpr = aColExpr->a[iIdxCol].pExpr; |
| sqlite3WalkExpr(&w, pWInfo->pWhere); |
| sqlite3WalkExprList(&w, pWInfo->pOrderBy); |
| sqlite3WalkExprList(&w, pWInfo->pResultSet); |
| } |
| } |
| |
| /* |
| ** Generate code for the start of the iLevel-th loop in the WHERE clause |
| ** implementation described by pWInfo. |
| */ |
| Bitmask sqlite3WhereCodeOneLoopStart( |
| Parse *pParse, /* Parsing context */ |
| Vdbe *v, /* Prepared statement under construction */ |
| WhereInfo *pWInfo, /* Complete information about the WHERE clause */ |
| int iLevel, /* Which level of pWInfo->a[] should be coded */ |
| WhereLevel *pLevel, /* The current level pointer */ |
| Bitmask notReady /* Which tables are currently available */ |
| ){ |
| int j, k; /* Loop counters */ |
| int iCur; /* The VDBE cursor for the table */ |
| int addrNxt; /* Where to jump to continue with the next IN case */ |
| int bRev; /* True if we need to scan in reverse order */ |
| WhereLoop *pLoop; /* The WhereLoop object being coded */ |
| WhereClause *pWC; /* Decomposition of the entire WHERE clause */ |
| WhereTerm *pTerm; /* A WHERE clause term */ |
| sqlite3 *db; /* Database connection */ |
| struct SrcList_item *pTabItem; /* FROM clause term being coded */ |
| int addrBrk; /* Jump here to break out of the loop */ |
| int addrHalt; /* addrBrk for the outermost loop */ |
| int addrCont; /* Jump here to continue with next cycle */ |
| int iRowidReg = 0; /* Rowid is stored in this register, if not zero */ |
| int iReleaseReg = 0; /* Temp register to free before returning */ |
| Index *pIdx = 0; /* Index used by loop (if any) */ |
| int iLoop; /* Iteration of constraint generator loop */ |
| |
| pWC = &pWInfo->sWC; |
| db = pParse->db; |
| pLoop = pLevel->pWLoop; |
| pTabItem = &pWInfo->pTabList->a[pLevel->iFrom]; |
| iCur = pTabItem->iCursor; |
| pLevel->notReady = notReady & ~sqlite3WhereGetMask(&pWInfo->sMaskSet, iCur); |
| bRev = (pWInfo->revMask>>iLevel)&1; |
| VdbeModuleComment((v, "Begin WHERE-loop%d: %s",iLevel,pTabItem->pTab->zName)); |
| |
| /* Create labels for the "break" and "continue" instructions |
| ** for the current loop. Jump to addrBrk to break out of a loop. |
| ** Jump to cont to go immediately to the next iteration of the |
| ** loop. |
| ** |
| ** When there is an IN operator, we also have a "addrNxt" label that |
| ** means to continue with the next IN value combination. When |
| ** there are no IN operators in the constraints, the "addrNxt" label |
| ** is the same as "addrBrk". |
| */ |
| addrBrk = pLevel->addrBrk = pLevel->addrNxt = sqlite3VdbeMakeLabel(pParse); |
| addrCont = pLevel->addrCont = sqlite3VdbeMakeLabel(pParse); |
| |
| /* If this is the right table of a LEFT OUTER JOIN, allocate and |
| ** initialize a memory cell that records if this table matches any |
| ** row of the left table of the join. |
| */ |
| assert( (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE) |
| || pLevel->iFrom>0 || (pTabItem[0].fg.jointype & JT_LEFT)==0 |
| ); |
| if( pLevel->iFrom>0 && (pTabItem[0].fg.jointype & JT_LEFT)!=0 ){ |
| pLevel->iLeftJoin = ++pParse->nMem; |
| sqlite3VdbeAddOp2(v, OP_Integer, 0, pLevel->iLeftJoin); |
| VdbeComment((v, "init LEFT JOIN no-match flag")); |
| } |
| |
| /* Compute a safe address to jump to if we discover that the table for |
| ** this loop is empty and can never contribute content. */ |
| for(j=iLevel; j>0 && pWInfo->a[j].iLeftJoin==0; j--){} |
| addrHalt = pWInfo->a[j].addrBrk; |
| |
| /* Special case of a FROM clause subquery implemented as a co-routine */ |
| if( pTabItem->fg.viaCoroutine ){ |
| int regYield = pTabItem->regReturn; |
| sqlite3VdbeAddOp3(v, OP_InitCoroutine, regYield, 0, pTabItem->addrFillSub); |
| pLevel->p2 = sqlite3VdbeAddOp2(v, OP_Yield, regYield, addrBrk); |
| VdbeCoverage(v); |
| VdbeComment((v, "next row of %s", pTabItem->pTab->zName)); |
| pLevel->op = OP_Goto; |
| }else |
| |
| #ifndef SQLITE_OMIT_VIRTUALTABLE |
| if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)!=0 ){ |
| /* Case 1: The table is a virtual-table. Use the VFilter and VNext |
| ** to access the data. |
| */ |
| int iReg; /* P3 Value for OP_VFilter */ |
| int addrNotFound; |
| int nConstraint = pLoop->nLTerm; |
| int iIn; /* Counter for IN constraints */ |
| |
| iReg = sqlite3GetTempRange(pParse, nConstraint+2); |
| addrNotFound = pLevel->addrBrk; |
| for(j=0; j<nConstraint; j++){ |
| int iTarget = iReg+j+2; |
| pTerm = pLoop->aLTerm[j]; |
| if( NEVER(pTerm==0) ) continue; |
| if( pTerm->eOperator & WO_IN ){ |
| codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, iTarget); |
| addrNotFound = pLevel->addrNxt; |
| }else{ |
| Expr *pRight = pTerm->pExpr->pRight; |
| codeExprOrVector(pParse, pRight, iTarget, 1); |
| } |
| } |
| sqlite3VdbeAddOp2(v, OP_Integer, pLoop->u.vtab.idxNum, iReg); |
| sqlite3VdbeAddOp2(v, OP_Integer, nConstraint, iReg+1); |
| sqlite3VdbeAddOp4(v, OP_VFilter, iCur, addrNotFound, iReg, |
| pLoop->u.vtab.idxStr, |
| pLoop->u.vtab.needFree ? P4_DYNAMIC : P4_STATIC); |
| VdbeCoverage(v); |
| pLoop->u.vtab.needFree = 0; |
| pLevel->p1 = iCur; |
| pLevel->op = pWInfo->eOnePass ? OP_Noop : OP_VNext; |
| pLevel->p2 = sqlite3VdbeCurrentAddr(v); |
| iIn = pLevel->u.in.nIn; |
| for(j=nConstraint-1; j>=0; j--){ |
| pTerm = pLoop->aLTerm[j]; |
| if( j<16 && (pLoop->u.vtab.omitMask>>j)&1 ){ |
| disableTerm(pLevel, pTerm); |
| }else if( (pTerm->eOperator & WO_IN)!=0 ){ |
| Expr *pCompare; /* The comparison operator */ |
| Expr *pRight; /* RHS of the comparison */ |
| VdbeOp *pOp; /* Opcode to access the value of the IN constraint */ |
| |
| /* Reload the constraint value into reg[iReg+j+2]. The same value |
| ** was loaded into the same register prior to the OP_VFilter, but |
| ** the xFilter implementation might have changed the datatype or |
| ** encoding of the value in the register, so it *must* be reloaded. */ |
| assert( pLevel->u.in.aInLoop!=0 || db->mallocFailed ); |
| if( !db->mallocFailed ){ |
| assert( iIn>0 ); |
| pOp = sqlite3VdbeGetOp(v, pLevel->u.in.aInLoop[--iIn].addrInTop); |
| assert( pOp->opcode==OP_Column || pOp->opcode==OP_Rowid ); |
| assert( pOp->opcode!=OP_Column || pOp->p3==iReg+j+2 ); |
| assert( pOp->opcode!=OP_Rowid || pOp->p2==iReg+j+2 ); |
| testcase( pOp->opcode==OP_Rowid ); |
| sqlite3VdbeAddOp3(v, pOp->opcode, pOp->p1, pOp->p2, pOp->p3); |
| } |
| |
| /* Generate code that will continue to the next row if |
| ** the IN constraint is not satisfied */ |
| pCompare = sqlite3PExpr(pParse, TK_EQ, 0, 0); |
| assert( pCompare!=0 || db->mallocFailed ); |
| if( pCompare ){ |
| pCompare->pLeft = pTerm->pExpr->pLeft; |
| pCompare->pRight = pRight = sqlite3Expr(db, TK_REGISTER, 0); |
| if( pRight ){ |
| pRight->iTable = iReg+j+2; |
| sqlite3ExprIfFalse(pParse, pCompare, pLevel->addrCont, 0); |
| } |
| pCompare->pLeft = 0; |
| sqlite3ExprDelete(db, pCompare); |
| } |
| } |
| } |
| /* These registers need to be preserved in case there is an IN operator |
| ** loop. So we could deallocate the registers here (and potentially |
| ** reuse them later) if (pLoop->wsFlags & WHERE_IN_ABLE)==0. But it seems |
| ** simpler and safer to simply not reuse the registers. |
| ** |
| ** sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2); |
| */ |
| }else |
| #endif /* SQLITE_OMIT_VIRTUALTABLE */ |
| |
| if( (pLoop->wsFlags & WHERE_IPK)!=0 |
| && (pLoop->wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_EQ))!=0 |
| ){ |
| /* Case 2: We can directly reference a single row using an |
| ** equality comparison against the ROWID field. Or |
| ** we reference multiple rows using a "rowid IN (...)" |
| ** construct. |
| */ |
| assert( pLoop->u.btree.nEq==1 ); |
| pTerm = pLoop->aLTerm[0]; |
| assert( pTerm!=0 ); |
| assert( pTerm->pExpr!=0 ); |
| testcase( pTerm->wtFlags & TERM_VIRTUAL ); |
| iReleaseReg = ++pParse->nMem; |
| iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, 0, bRev, iReleaseReg); |
| if( iRowidReg!=iReleaseReg ) sqlite3ReleaseTempReg(pParse, iReleaseReg); |
| addrNxt = pLevel->addrNxt; |
| sqlite3VdbeAddOp3(v, OP_SeekRowid, iCur, addrNxt, iRowidReg); |
| VdbeCoverage(v); |
| pLevel->op = OP_Noop; |
| }else if( (pLoop->wsFlags & WHERE_IPK)!=0 |
| && (pLoop->wsFlags & WHERE_COLUMN_RANGE)!=0 |
| ){ |
| /* Case 3: We have an inequality comparison against the ROWID field. |
| */ |
| int testOp = OP_Noop; |
| int start; |
| int memEndValue = 0; |
| WhereTerm *pStart, *pEnd; |
| |
| j = 0; |
| pStart = pEnd = 0; |
| if( pLoop->wsFlags & WHERE_BTM_LIMIT ) pStart = pLoop->aLTerm[j++]; |
| if( pLoop->wsFlags & WHERE_TOP_LIMIT ) pEnd = pLoop->aLTerm[j++]; |
| assert( pStart!=0 || pEnd!=0 ); |
| if( bRev ){ |
| pTerm = pStart; |
| pStart = pEnd; |
| pEnd = pTerm; |
| } |
| codeCursorHint(pTabItem, pWInfo, pLevel, pEnd); |
| if( pStart ){ |
| Expr *pX; /* The expression that defines the start bound */ |
| int r1, rTemp; /* Registers for holding the start boundary */ |
| int op; /* Cursor seek operation */ |
| |
| /* The following constant maps TK_xx codes into corresponding |
| ** seek opcodes. It depends on a particular ordering of TK_xx |
| */ |
| const u8 aMoveOp[] = { |
| /* TK_GT */ OP_SeekGT, |
| /* TK_LE */ OP_SeekLE, |
| /* TK_LT */ OP_SeekLT, |
| /* TK_GE */ OP_SeekGE |
| }; |
| assert( TK_LE==TK_GT+1 ); /* Make sure the ordering.. */ |
| assert( TK_LT==TK_GT+2 ); /* ... of the TK_xx values... */ |
| assert( TK_GE==TK_GT+3 ); /* ... is correcct. */ |
| |
| assert( (pStart->wtFlags & TERM_VNULL)==0 ); |
| testcase( pStart->wtFlags & TERM_VIRTUAL ); |
| pX = pStart->pExpr; |
| assert( pX!=0 ); |
| testcase( pStart->leftCursor!=iCur ); /* transitive constraints */ |
| if( sqlite3ExprIsVector(pX->pRight) ){ |
| r1 = rTemp = sqlite3GetTempReg(pParse); |
| codeExprOrVector(pParse, pX->pRight, r1, 1); |
| testcase( pX->op==TK_GT ); |
| testcase( pX->op==TK_GE ); |
| testcase( pX->op==TK_LT ); |
| testcase( pX->op==TK_LE ); |
| op = aMoveOp[((pX->op - TK_GT - 1) & 0x3) | 0x1]; |
| assert( pX->op!=TK_GT || op==OP_SeekGE ); |
| assert( pX->op!=TK_GE || op==OP_SeekGE ); |
| assert( pX->op!=TK_LT || op==OP_SeekLE ); |
| assert( pX->op!=TK_LE || op==OP_SeekLE ); |
| }else{ |
| r1 = sqlite3ExprCodeTemp(pParse, pX->pRight, &rTemp); |
| disableTerm(pLevel, pStart); |
| op = aMoveOp[(pX->op - TK_GT)]; |
| } |
| sqlite3VdbeAddOp3(v, op, iCur, addrBrk, r1); |
| VdbeComment((v, "pk")); |
| VdbeCoverageIf(v, pX->op==TK_GT); |
| VdbeCoverageIf(v, pX->op==TK_LE); |
| VdbeCoverageIf(v, pX->op==TK_LT); |
| VdbeCoverageIf(v, pX->op==TK_GE); |
| sqlite3ReleaseTempReg(pParse, rTemp); |
| }else{ |
| sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iCur, addrHalt); |
| VdbeCoverageIf(v, bRev==0); |
| VdbeCoverageIf(v, bRev!=0); |
| } |
| if( pEnd ){ |
| Expr *pX; |
| pX = pEnd->pExpr; |
| assert( pX!=0 ); |
| assert( (pEnd->wtFlags & TERM_VNULL)==0 ); |
| testcase( pEnd->leftCursor!=iCur ); /* Transitive constraints */ |
| testcase( pEnd->wtFlags & TERM_VIRTUAL ); |
| memEndValue = ++pParse->nMem; |
| codeExprOrVector(pParse, pX->pRight, memEndValue, 1); |
| if( 0==sqlite3ExprIsVector(pX->pRight) |
| && (pX->op==TK_LT || pX->op==TK_GT) |
| ){ |
| testOp = bRev ? OP_Le : OP_Ge; |
| }else{ |
| testOp = bRev ? OP_Lt : OP_Gt; |
| } |
| if( 0==sqlite3ExprIsVector(pX->pRight) ){ |
| disableTerm(pLevel, pEnd); |
| } |
| } |
| start = sqlite3VdbeCurrentAddr(v); |
| pLevel->op = bRev ? OP_Prev : OP_Next; |
| pLevel->p1 = iCur; |
| pLevel->p2 = start; |
| assert( pLevel->p5==0 ); |
| if( testOp!=OP_Noop ){ |
| iRowidReg = ++pParse->nMem; |
| sqlite3VdbeAddOp2(v, OP_Rowid, iCur, iRowidReg); |
| sqlite3VdbeAddOp3(v, testOp, memEndValue, addrBrk, iRowidReg); |
| VdbeCoverageIf(v, testOp==OP_Le); |
| VdbeCoverageIf(v, testOp==OP_Lt); |
| VdbeCoverageIf(v, testOp==OP_Ge); |
| VdbeCoverageIf(v, testOp==OP_Gt); |
| sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC | SQLITE_JUMPIFNULL); |
| } |
| }else if( pLoop->wsFlags & WHERE_INDEXED ){ |
| /* Case 4: A scan using an index. |
| ** |
| ** The WHERE clause may contain zero or more equality |
| ** terms ("==" or "IN" operators) that refer to the N |
| ** left-most columns of the index. It may also contain |
| ** inequality constraints (>, <, >= or <=) on the indexed |
| ** column that immediately follows the N equalities. Only |
| ** the right-most column can be an inequality - the rest must |
| ** use the "==" and "IN" operators. For example, if the |
| ** index is on (x,y,z), then the following clauses are all |
| ** optimized: |
| ** |
| ** x=5 |
| ** x=5 AND y=10 |
| ** x=5 AND y<10 |
| ** x=5 AND y>5 AND y<10 |
| ** x=5 AND y=5 AND z<=10 |
| ** |
| ** The z<10 term of the following cannot be used, only |
| ** the x=5 term: |
| ** |
| ** x=5 AND z<10 |
| ** |
| ** N may be zero if there are inequality constraints. |
| ** If there are no inequality constraints, then N is at |
| ** least one. |
| ** |
| ** This case is also used when there are no WHERE clause |
| ** constraints but an index is selected anyway, in order |
| ** to force the output order to conform to an ORDER BY. |
| */ |
| static const u8 aStartOp[] = { |
| 0, |
| 0, |
| OP_Rewind, /* 2: (!start_constraints && startEq && !bRev) */ |
| OP_Last, /* 3: (!start_constraints && startEq && bRev) */ |
| OP_SeekGT, /* 4: (start_constraints && !startEq && !bRev) */ |
| OP_SeekLT, /* 5: (start_constraints && !startEq && bRev) */ |
| OP_SeekGE, /* 6: (start_constraints && startEq && !bRev) */ |
| OP_SeekLE /* 7: (start_constraints && startEq && bRev) */ |
| }; |
| static const u8 aEndOp[] = { |
| OP_IdxGE, /* 0: (end_constraints && !bRev && !endEq) */ |
| OP_IdxGT, /* 1: (end_constraints && !bRev && endEq) */ |
| OP_IdxLE, /* 2: (end_constraints && bRev && !endEq) */ |
| OP_IdxLT, /* 3: (end_constraints && bRev && endEq) */ |
| }; |
| u16 nEq = pLoop->u.btree.nEq; /* Number of == or IN terms */ |
| u16 nBtm = pLoop->u.btree.nBtm; /* Length of BTM vector */ |
| u16 nTop = pLoop->u.btree.nTop; /* Length of TOP vector */ |
| int regBase; /* Base register holding constraint values */ |
| WhereTerm *pRangeStart = 0; /* Inequality constraint at range start */ |
| WhereTerm *pRangeEnd = 0; /* Inequality constraint at range end */ |
| int startEq; /* True if range start uses ==, >= or <= */ |
| int endEq; /* True if range end uses ==, >= or <= */ |
| int start_constraints; /* Start of range is constrained */ |
| int nConstraint; /* Number of constraint terms */ |
| int iIdxCur; /* The VDBE cursor for the index */ |
| int nExtraReg = 0; /* Number of extra registers needed */ |
| int op; /* Instruction opcode */ |
| char *zStartAff; /* Affinity for start of range constraint */ |
| char *zEndAff = 0; /* Affinity for end of range constraint */ |
| u8 bSeekPastNull = 0; /* True to seek past initial nulls */ |
| u8 bStopAtNull = 0; /* Add condition to terminate at NULLs */ |
| int omitTable; /* True if we use the index only */ |
| |
| |
| pIdx = pLoop->u.btree.pIndex; |
| iIdxCur = pLevel->iIdxCur; |
| assert( nEq>=pLoop->nSkip ); |
| |
| /* If this loop satisfies a sort order (pOrderBy) request that |
| ** was passed to this function to implement a "SELECT min(x) ..." |
| ** query, then the caller will only allow the loop to run for |
| ** a single iteration. This means that the first row returned |
| ** should not have a NULL value stored in 'x'. If column 'x' is |
| ** the first one after the nEq equality constraints in the index, |
| ** this requires some special handling. |
| */ |
| assert( pWInfo->pOrderBy==0 |
| || pWInfo->pOrderBy->nExpr==1 |
| || (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)==0 ); |
| if( (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)!=0 |
| && pWInfo->nOBSat>0 |
| && (pIdx->nKeyCol>nEq) |
| ){ |
| assert( pLoop->nSkip==0 ); |
| bSeekPastNull = 1; |
| nExtraReg = 1; |
| } |
| |
| /* Find any inequality constraint terms for the start and end |
| ** of the range. |
| */ |
| j = nEq; |
| if( pLoop->wsFlags & WHERE_BTM_LIMIT ){ |
| pRangeStart = pLoop->aLTerm[j++]; |
| nExtraReg = MAX(nExtraReg, pLoop->u.btree.nBtm); |
| /* Like optimization range constraints always occur in pairs */ |
| assert( (pRangeStart->wtFlags & TERM_LIKEOPT)==0 || |
| (pLoop->wsFlags & WHERE_TOP_LIMIT)!=0 ); |
| } |
| if( pLoop->wsFlags & WHERE_TOP_LIMIT ){ |
| pRangeEnd = pLoop->aLTerm[j++]; |
| nExtraReg = MAX(nExtraReg, pLoop->u.btree.nTop); |
| #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS |
| if( (pRangeEnd->wtFlags & TERM_LIKEOPT)!=0 ){ |
| assert( pRangeStart!=0 ); /* LIKE opt constraints */ |
| assert( pRangeStart->wtFlags & TERM_LIKEOPT ); /* occur in pairs */ |
| pLevel->iLikeRepCntr = (u32)++pParse->nMem; |
| sqlite3VdbeAddOp2(v, OP_Integer, 1, (int)pLevel->iLikeRepCntr); |
| VdbeComment((v, "LIKE loop counter")); |
| pLevel->addrLikeRep = sqlite3VdbeCurrentAddr(v); |
| /* iLikeRepCntr actually stores 2x the counter register number. The |
| ** bottom bit indicates whether the search order is ASC or DESC. */ |
| testcase( bRev ); |
| testcase( pIdx->aSortOrder[nEq]==SQLITE_SO_DESC ); |
| assert( (bRev & ~1)==0 ); |
| pLevel->iLikeRepCntr <<=1; |
| pLevel->iLikeRepCntr |= bRev ^ (pIdx->aSortOrder[nEq]==SQLITE_SO_DESC); |
| } |
| #endif |
| if( pRangeStart==0 ){ |
| j = pIdx->aiColumn[nEq]; |
| if( (j>=0 && pIdx->pTable->aCol[j].notNull==0) || j==XN_EXPR ){ |
| bSeekPastNull = 1; |
| } |
| } |
| } |
| assert( pRangeEnd==0 || (pRangeEnd->wtFlags & TERM_VNULL)==0 ); |
| |
| /* If we are doing a reverse order scan on an ascending index, or |
| ** a forward order scan on a descending index, interchange the |
| ** start and end terms (pRangeStart and pRangeEnd). |
| */ |
| if( (nEq<pIdx->nKeyCol && bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC)) |
| || (bRev && pIdx->nKeyCol==nEq) |
| ){ |
| SWAP(WhereTerm *, pRangeEnd, pRangeStart); |
| SWAP(u8, bSeekPastNull, bStopAtNull); |
| SWAP(u8, nBtm, nTop); |
| } |
| |
| /* Generate code to evaluate all constraint terms using == or IN |
| ** and store the values of those terms in an array of registers |
| ** starting at regBase. |
| */ |
| codeCursorHint(pTabItem, pWInfo, pLevel, pRangeEnd); |
| regBase = codeAllEqualityTerms(pParse,pLevel,bRev,nExtraReg,&zStartAff); |
| assert( zStartAff==0 || sqlite3Strlen30(zStartAff)>=nEq ); |
| if( zStartAff && nTop ){ |
| zEndAff = sqlite3DbStrDup(db, &zStartAff[nEq]); |
| } |
| addrNxt = pLevel->addrNxt; |
| |
| testcase( pRangeStart && (pRangeStart->eOperator & WO_LE)!=0 ); |
| testcase( pRangeStart && (pRangeStart->eOperator & WO_GE)!=0 ); |
| testcase( pRangeEnd && (pRangeEnd->eOperator & WO_LE)!=0 ); |
| testcase( pRangeEnd && (pRangeEnd->eOperator & WO_GE)!=0 ); |
| startEq = !pRangeStart || pRangeStart->eOperator & (WO_LE|WO_GE); |
| endEq = !pRangeEnd || pRangeEnd->eOperator & (WO_LE|WO_GE); |
| start_constraints = pRangeStart || nEq>0; |
| |
| /* Seek the index cursor to the start of the range. */ |
| nConstraint = nEq; |
| if( pRangeStart ){ |
| Expr *pRight = pRangeStart->pExpr->pRight; |
| codeExprOrVector(pParse, pRight, regBase+nEq, nBtm); |
| whereLikeOptimizationStringFixup(v, pLevel, pRangeStart); |
| if( (pRangeStart->wtFlags & TERM_VNULL)==0 |
| && sqlite3ExprCanBeNull(pRight) |
| ){ |
| sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt); |
| VdbeCoverage(v); |
| } |
| if( zStartAff ){ |
| updateRangeAffinityStr(pRight, nBtm, &zStartAff[nEq]); |
| } |
| nConstraint += nBtm; |
| testcase( pRangeStart->wtFlags & TERM_VIRTUAL ); |
| if( sqlite3ExprIsVector(pRight)==0 ){ |
| disableTerm(pLevel, pRangeStart); |
| }else{ |
| startEq = 1; |
| } |
| bSeekPastNull = 0; |
| }else if( bSeekPastNull ){ |
| sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq); |
| nConstraint++; |
| startEq = 0; |
| start_constraints = 1; |
| } |
| codeApplyAffinity(pParse, regBase, nConstraint - bSeekPastNull, zStartAff); |
| if( pLoop->nSkip>0 && nConstraint==pLoop->nSkip ){ |
| /* The skip-scan logic inside the call to codeAllEqualityConstraints() |
| ** above has already left the cursor sitting on the correct row, |
| ** so no further seeking is needed */ |
| }else{ |
| if( pLoop->wsFlags & WHERE_IN_EARLYOUT ){ |
| sqlite3VdbeAddOp1(v, OP_SeekHit, iIdxCur); |
| } |
| op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev]; |
| assert( op!=0 ); |
| sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint); |
| VdbeCoverage(v); |
| VdbeCoverageIf(v, op==OP_Rewind); testcase( op==OP_Rewind ); |
| VdbeCoverageIf(v, op==OP_Last); testcase( op==OP_Last ); |
| VdbeCoverageIf(v, op==OP_SeekGT); testcase( op==OP_SeekGT ); |
| VdbeCoverageIf(v, op==OP_SeekGE); testcase( op==OP_SeekGE ); |
| VdbeCoverageIf(v, op==OP_SeekLE); testcase( op==OP_SeekLE ); |
| VdbeCoverageIf(v, op==OP_SeekLT); testcase( op==OP_SeekLT ); |
| } |
| |
| /* Load the value for the inequality constraint at the end of the |
| ** range (if any). |
| */ |
| nConstraint = nEq; |
| if( pRangeEnd ){ |
| Expr *pRight = pRangeEnd->pExpr->pRight; |
| codeExprOrVector(pParse, pRight, regBase+nEq, nTop); |
| whereLikeOptimizationStringFixup(v, pLevel, pRangeEnd); |
| if( (pRangeEnd->wtFlags & TERM_VNULL)==0 |
| && sqlite3ExprCanBeNull(pRight) |
| ){ |
| sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt); |
| VdbeCoverage(v); |
| } |
| if( zEndAff ){ |
| updateRangeAffinityStr(pRight, nTop, zEndAff); |
| codeApplyAffinity(pParse, regBase+nEq, nTop, zEndAff); |
| }else{ |
| assert( pParse->db->mallocFailed ); |
| } |
| nConstraint += nTop; |
| testcase( pRangeEnd->wtFlags & TERM_VIRTUAL ); |
| |
| if( sqlite3ExprIsVector(pRight)==0 ){ |
| disableTerm(pLevel, pRangeEnd); |
| }else{ |
| endEq = 1; |
| } |
| }else if( bStopAtNull ){ |
| sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq); |
| endEq = 0; |
| nConstraint++; |
| } |
| sqlite3DbFree(db, zStartAff); |
| sqlite3DbFree(db, zEndAff); |
| |
| /* Top of the loop body */ |
| pLevel->p2 = sqlite3VdbeCurrentAddr(v); |
| |
| /* Check if the index cursor is past the end of the range. */ |
| if( nConstraint ){ |
| op = aEndOp[bRev*2 + endEq]; |
| sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint); |
| testcase( op==OP_IdxGT ); VdbeCoverageIf(v, op==OP_IdxGT ); |
| testcase( op==OP_IdxGE ); VdbeCoverageIf(v, op==OP_IdxGE ); |
| testcase( op==OP_IdxLT ); VdbeCoverageIf(v, op==OP_IdxLT ); |
| testcase( op==OP_IdxLE ); VdbeCoverageIf(v, op==OP_IdxLE ); |
| } |
| |
| if( pLoop->wsFlags & WHERE_IN_EARLYOUT ){ |
| sqlite3VdbeAddOp2(v, OP_SeekHit, iIdxCur, 1); |
| } |
| |
| /* Seek the table cursor, if required */ |
| omitTable = (pLoop->wsFlags & WHERE_IDX_ONLY)!=0 |
| && (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)==0; |
| if( omitTable ){ |
| /* pIdx is a covering index. No need to access the main table. */ |
| }else if( HasRowid(pIdx->pTable) ){ |
| if( (pWInfo->wctrlFlags & WHERE_SEEK_TABLE) || ( |
| (pWInfo->wctrlFlags & WHERE_SEEK_UNIQ_TABLE) |
| && (pWInfo->eOnePass==ONEPASS_SINGLE) |
| )){ |
| iRowidReg = ++pParse->nMem; |
| sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, iRowidReg); |
| sqlite3VdbeAddOp3(v, OP_NotExists, iCur, 0, iRowidReg); |
| VdbeCoverage(v); |
| }else{ |
| codeDeferredSeek(pWInfo, pIdx, iCur, iIdxCur); |
| } |
| }else if( iCur!=iIdxCur ){ |
| Index *pPk = sqlite3PrimaryKeyIndex(pIdx->pTable); |
| iRowidReg = sqlite3GetTempRange(pParse, pPk->nKeyCol); |
| for(j=0; j<pPk->nKeyCol; j++){ |
| k = sqlite3ColumnOfIndex(pIdx, pPk->aiColumn[j]); |
| sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, k, iRowidReg+j); |
| } |
| sqlite3VdbeAddOp4Int(v, OP_NotFound, iCur, addrCont, |
| iRowidReg, pPk->nKeyCol); VdbeCoverage(v); |
| } |
| |
| /* If pIdx is an index on one or more expressions, then look through |
| ** all the expressions in pWInfo and try to transform matching expressions |
| ** into reference to index columns. |
| ** |
| ** Do not do this for the RHS of a LEFT JOIN. This is because the |
| ** expression may be evaluated after OP_NullRow has been executed on |
| ** the cursor. In this case it is important to do the full evaluation, |
| ** as the result of the expression may not be NULL, even if all table |
| ** column values are. https://www.sqlite.org/src/info/7fa8049685b50b5a |
| */ |
| if( pLevel->iLeftJoin==0 ){ |
| whereIndexExprTrans(pIdx, iCur, iIdxCur, pWInfo); |
| } |
| |
| /* Record the instruction used to terminate the loop. */ |
| if( pLoop->wsFlags & WHERE_ONEROW ){ |
| pLevel->op = OP_Noop; |
| }else if( bRev ){ |
| pLevel->op = OP_Prev; |
| }else{ |
| pLevel->op = OP_Next; |
| } |
| pLevel->p1 = iIdxCur; |
| pLevel->p3 = (pLoop->wsFlags&WHERE_UNQ_WANTED)!=0 ? 1:0; |
| if( (pLoop->wsFlags & WHERE_CONSTRAINT)==0 ){ |
| pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP; |
| }else{ |
| assert( pLevel->p5==0 ); |
| } |
| if( omitTable ) pIdx = 0; |
| }else |
| |
| #ifndef SQLITE_OMIT_OR_OPTIMIZATION |
| if( pLoop->wsFlags & WHERE_MULTI_OR ){ |
| /* Case 5: Two or more separately indexed terms connected by OR |
| ** |
| ** Example: |
| ** |
| ** CREATE TABLE t1(a,b,c,d); |
| ** CREATE INDEX i1 ON t1(a); |
| ** CREATE INDEX i2 ON t1(b); |
| ** CREATE INDEX i3 ON t1(c); |
| ** |
| ** SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13) |
| ** |
| ** In the example, there are three indexed terms connected by OR. |
| ** The top of the loop looks like this: |
| ** |
| ** Null 1 # Zero the rowset in reg 1 |
| ** |
| ** Then, for each indexed term, the following. The arguments to |
| ** RowSetTest are such that the rowid of the current row is inserted |
| ** into the RowSet. If it is already present, control skips the |
| ** Gosub opcode and jumps straight to the code generated by WhereEnd(). |
| ** |
| ** sqlite3WhereBegin(<term>) |
| ** RowSetTest # Insert rowid into rowset |
| ** Gosub 2 A |
| ** sqlite3WhereEnd() |
| ** |
| ** Following the above, code to terminate the loop. Label A, the target |
| ** of the Gosub above, jumps to the instruction right after the Goto. |
| ** |
| ** Null 1 # Zero the rowset in reg 1 |
| ** Goto B # The loop is finished. |
| ** |
| ** A: <loop body> # Return data, whatever. |
| ** |
| ** Return 2 # Jump back to the Gosub |
| ** |
| ** B: <after the loop> |
| ** |
| ** Added 2014-05-26: If the table is a WITHOUT ROWID table, then |
| ** use an ephemeral index instead of a RowSet to record the primary |
| ** keys of the rows we have already seen. |
| ** |
| */ |
| WhereClause *pOrWc; /* The OR-clause broken out into subterms */ |
| SrcList *pOrTab; /* Shortened table list or OR-clause generation */ |
| Index *pCov = 0; /* Potential covering index (or NULL) */ |
| int iCovCur = pParse->nTab++; /* Cursor used for index scans (if any) */ |
| |
| int regReturn = ++pParse->nMem; /* Register used with OP_Gosub */ |
| int regRowset = 0; /* Register for RowSet object */ |
| int regRowid = 0; /* Register holding rowid */ |
| int iLoopBody = sqlite3VdbeMakeLabel(pParse);/* Start of loop body */ |
| int iRetInit; /* Address of regReturn init */ |
| int untestedTerms = 0; /* Some terms not completely tested */ |
| int ii; /* Loop counter */ |
| u16 wctrlFlags; /* Flags for sub-WHERE clause */ |
| Expr *pAndExpr = 0; /* An ".. AND (...)" expression */ |
| Table *pTab = pTabItem->pTab; |
| |
| pTerm = pLoop->aLTerm[0]; |
| assert( pTerm!=0 ); |
| assert( pTerm->eOperator & WO_OR ); |
| assert( (pTerm->wtFlags & TERM_ORINFO)!=0 ); |
| pOrWc = &pTerm->u.pOrInfo->wc; |
| pLevel->op = OP_Return; |
| pLevel->p1 = regReturn; |
| |
| /* Set up a new SrcList in pOrTab containing the table being scanned |
| ** by this loop in the a[0] slot and all notReady tables in a[1..] slots. |
| ** This becomes the SrcList in the recursive call to sqlite3WhereBegin(). |
| */ |
| if( pWInfo->nLevel>1 ){ |
| int nNotReady; /* The number of notReady tables */ |
| struct SrcList_item *origSrc; /* Original list of tables */ |
| nNotReady = pWInfo->nLevel - iLevel - 1; |
| pOrTab = sqlite3StackAllocRaw(db, |
| sizeof(*pOrTab)+ nNotReady*sizeof(pOrTab->a[0])); |
| if( pOrTab==0 ) return notReady; |
| pOrTab->nAlloc = (u8)(nNotReady + 1); |
| pOrTab->nSrc = pOrTab->nAlloc; |
| memcpy(pOrTab->a, pTabItem, sizeof(*pTabItem)); |
| origSrc = pWInfo->pTabList->a; |
| for(k=1; k<=nNotReady; k++){ |
| memcpy(&pOrTab->a[k], &origSrc[pLevel[k].iFrom], sizeof(pOrTab->a[k])); |
| } |
| }else{ |
| pOrTab = pWInfo->pTabList; |
| } |
| |
| /* Initialize the rowset register to contain NULL. An SQL NULL is |
| ** equivalent to an empty rowset. Or, create an ephemeral index |
| ** capable of holding primary keys in the case of a WITHOUT ROWID. |
| ** |
| ** Also initialize regReturn to contain the address of the instruction |
| ** immediately following the OP_Return at the bottom of the loop. This |
| ** is required in a few obscure LEFT JOIN cases where control jumps |
| ** over the top of the loop into the body of it. In this case the |
| ** correct response for the end-of-loop code (the OP_Return) is to |
| ** fall through to the next instruction, just as an OP_Next does if |
| ** called on an uninitialized cursor. |
| */ |
| if( (pWInfo->wctrlFlags & WHERE_DUPLICATES_OK)==0 ){ |
| if( HasRowid(pTab) ){ |
| regRowset = ++pParse->nMem; |
| sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset); |
| }else{ |
| Index *pPk = sqlite3PrimaryKeyIndex(pTab); |
| regRowset = pParse->nTab++; |
| sqlite3VdbeAddOp2(v, OP_OpenEphemeral, regRowset, pPk->nKeyCol); |
| sqlite3VdbeSetP4KeyInfo(pParse, pPk); |
| } |
| regRowid = ++pParse->nMem; |
| } |
| iRetInit = sqlite3VdbeAddOp2(v, OP_Integer, 0, regReturn); |
| |
| /* If the original WHERE clause is z of the form: (x1 OR x2 OR ...) AND y |
| ** Then for every term xN, evaluate as the subexpression: xN AND z |
| ** That way, terms in y that are factored into the disjunction will |
| ** be picked up by the recursive calls to sqlite3WhereBegin() below. |
| ** |
| ** Actually, each subexpression is converted to "xN AND w" where w is |
| ** the "interesting" terms of z - terms that did not originate in the |
| ** ON or USING clause of a LEFT JOIN, and terms that are usable as |
| ** indices. |
| ** |
| ** This optimization also only applies if the (x1 OR x2 OR ...) term |
| ** is not contained in the ON clause of a LEFT JOIN. |
| ** See ticket http://www.sqlite.org/src/info/f2369304e4 |
| */ |
| if( pWC->nTerm>1 ){ |
| int iTerm; |
| for(iTerm=0; iTerm<pWC->nTerm; iTerm++){ |
| Expr *pExpr = pWC->a[iTerm].pExpr; |
| if( &pWC->a[iTerm] == pTerm ) continue; |
| testcase( pWC->a[iTerm].wtFlags & TERM_VIRTUAL ); |
| testcase( pWC->a[iTerm].wtFlags & TERM_CODED ); |
| if( (pWC->a[iTerm].wtFlags & (TERM_VIRTUAL|TERM_CODED))!=0 ) continue; |
| if( (pWC->a[iTerm].eOperator & WO_ALL)==0 ) continue; |
| testcase( pWC->a[iTerm].wtFlags & TERM_ORINFO ); |
| pExpr = sqlite3ExprDup(db, pExpr, 0); |
| pAndExpr = sqlite3ExprAnd(db, pAndExpr, pExpr); |
| } |
| if( pAndExpr ){ |
| pAndExpr = sqlite3PExpr(pParse, TK_AND|TKFLG_DONTFOLD, 0, pAndExpr); |
| } |
| } |
| |
| /* Run a separate WHERE clause for each term of the OR clause. After |
| ** eliminating duplicates from other WHERE clauses, the action for each |
| ** sub-WHERE clause is to to invoke the main loop body as a subroutine. |
| */ |
| wctrlFlags = WHERE_OR_SUBCLAUSE | (pWInfo->wctrlFlags & WHERE_SEEK_TABLE); |
| ExplainQueryPlan((pParse, 1, "MULTI-INDEX OR")); |
| for(ii=0; ii<pOrWc->nTerm; ii++){ |
| WhereTerm *pOrTerm = &pOrWc->a[ii]; |
| if( pOrTerm->leftCursor==iCur || (pOrTerm->eOperator & WO_AND)!=0 ){ |
| WhereInfo *pSubWInfo; /* Info for single OR-term scan */ |
| Expr *pOrExpr = pOrTerm->pExpr; /* Current OR clause term */ |
| int jmp1 = 0; /* Address of jump operation */ |
| assert( (pTabItem[0].fg.jointype & JT_LEFT)==0 |
| || ExprHasProperty(pOrExpr, EP_FromJoin) |
| ); |
| if( pAndExpr ){ |
| pAndExpr->pLeft = pOrExpr; |
| pOrExpr = pAndExpr; |
| } |
| /* Loop through table entries that match term pOrTerm. */ |
| ExplainQueryPlan((pParse, 1, "INDEX %d", ii+1)); |
| WHERETRACE(0xffff, ("Subplan for OR-clause:\n")); |
| pSubWInfo = sqlite3WhereBegin(pParse, pOrTab, pOrExpr, 0, 0, |
| wctrlFlags, iCovCur); |
| assert( pSubWInfo || pParse->nErr || db->mallocFailed ); |
| if( pSubWInfo ){ |
| WhereLoop *pSubLoop; |
| int addrExplain = sqlite3WhereExplainOneScan( |
| pParse, pOrTab, &pSubWInfo->a[0], 0 |
| ); |
| sqlite3WhereAddScanStatus(v, pOrTab, &pSubWInfo->a[0], addrExplain); |
| |
| /* This is the sub-WHERE clause body. First skip over |
| ** duplicate rows from prior sub-WHERE clauses, and record the |
| ** rowid (or PRIMARY KEY) for the current row so that the same |
| ** row will be skipped in subsequent sub-WHERE clauses. |
| */ |
| if( (pWInfo->wctrlFlags & WHERE_DUPLICATES_OK)==0 ){ |
| int iSet = ((ii==pOrWc->nTerm-1)?-1:ii); |
| if( HasRowid(pTab) ){ |
| sqlite3ExprCodeGetColumnOfTable(v, pTab, iCur, -1, regRowid); |
| jmp1 = sqlite3VdbeAddOp4Int(v, OP_RowSetTest, regRowset, 0, |
| regRowid, iSet); |
| VdbeCoverage(v); |
| }else{ |
| Index *pPk = sqlite3PrimaryKeyIndex(pTab); |
| int nPk = pPk->nKeyCol; |
| int iPk; |
| int r; |
| |
| /* Read the PK into an array of temp registers. */ |
| r = sqlite3GetTempRange(pParse, nPk); |
| for(iPk=0; iPk<nPk; iPk++){ |
| int iCol = pPk->aiColumn[iPk]; |
| sqlite3ExprCodeGetColumnOfTable(v, pTab, iCur, iCol, r+iPk); |
| } |
| |
| /* Check if the temp table already contains this key. If so, |
| ** the row has already been included in the result set and |
| ** can be ignored (by jumping past the Gosub below). Otherwise, |
| ** insert the key into the temp table and proceed with processing |
| ** the row. |
| ** |
| ** Use some of the same optimizations as OP_RowSetTest: If iSet |
| ** is zero, assume that the key cannot already be present in |
| ** the temp table. And if iSet is -1, assume that there is no |
| ** need to insert the key into the temp table, as it will never |
| ** be tested for. */ |
| if( iSet ){ |
| jmp1 = sqlite3VdbeAddOp4Int(v, OP_Found, regRowset, 0, r, nPk); |
| VdbeCoverage(v); |
| } |
| if( iSet>=0 ){ |
| sqlite3VdbeAddOp3(v, OP_MakeRecord, r, nPk, regRowid); |
| sqlite3VdbeAddOp4Int(v, OP_IdxInsert, regRowset, regRowid, |
| r, nPk); |
| if( iSet ) sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT); |
| } |
| |
| /* Release the array of temp registers */ |
| sqlite3ReleaseTempRange(pParse, r, nPk); |
| } |
| } |
| |
| /* Invoke the main loop body as a subroutine */ |
| sqlite3VdbeAddOp2(v, OP_Gosub, regReturn, iLoopBody); |
| |
| /* Jump here (skipping the main loop body subroutine) if the |
| ** current sub-WHERE row is a duplicate from prior sub-WHEREs. */ |
| if( jmp1 ) sqlite3VdbeJumpHere(v, jmp1); |
| |
| /* The pSubWInfo->untestedTerms flag means that this OR term |
| ** contained one or more AND term from a notReady table. The |
| ** terms from the notReady table could not be tested and will |
| ** need to be tested later. |
| */ |
| if( pSubWInfo->untestedTerms ) untestedTerms = 1; |
| |
| /* If all of the OR-connected terms are optimized using the same |
| ** index, and the index is opened using the same cursor number |
| ** by each call to sqlite3WhereBegin() made by this loop, it may |
| ** be possible to use that index as a covering index. |
| ** |
| ** If the call to sqlite3WhereBegin() above resulted in a scan that |
| ** uses an index, and this is either the first OR-connected term |
| ** processed or the index is the same as that used by all previous |
| ** terms, set pCov to the candidate covering index. Otherwise, set |
| ** pCov to NULL to indicate that no candidate covering index will |
| ** be available. |
| */ |
| pSubLoop = pSubWInfo->a[0].pWLoop; |
| assert( (pSubLoop->wsFlags & WHERE_AUTO_INDEX)==0 ); |
| if( (pSubLoop->wsFlags & WHERE_INDEXED)!=0 |
| && (ii==0 || pSubLoop->u.btree.pIndex==pCov) |
| && (HasRowid(pTab) || !IsPrimaryKeyIndex(pSubLoop->u.btree.pIndex)) |
| ){ |
| assert( pSubWInfo->a[0].iIdxCur==iCovCur ); |
| pCov = pSubLoop->u.btree.pIndex; |
| }else{ |
| pCov = 0; |
| } |
| |
| /* Finish the loop through table entries that match term pOrTerm. */ |
| sqlite3WhereEnd(pSubWInfo); |
| ExplainQueryPlanPop(pParse); |
| } |
| } |
| } |
| ExplainQueryPlanPop(pParse); |
| pLevel->u.pCovidx = pCov; |
| if( pCov ) pLevel->iIdxCur = iCovCur; |
| if( pAndExpr ){ |
| pAndExpr->pLeft = 0; |
| sqlite3ExprDelete(db, pAndExpr); |
| } |
| sqlite3VdbeChangeP1(v, iRetInit, sqlite3VdbeCurrentAddr(v)); |
| sqlite3VdbeGoto(v, pLevel->addrBrk); |
| sqlite3VdbeResolveLabel(v, iLoopBody); |
| |
| if( pWInfo->nLevel>1 ) sqlite3StackFree(db, pOrTab); |
| if( !untestedTerms ) disableTerm(pLevel, pTerm); |
| }else |
| #endif /* SQLITE_OMIT_OR_OPTIMIZATION */ |
| |
| { |
| /* Case 6: There is no usable index. We must do a complete |
| ** scan of the entire table. |
| */ |
| static const u8 aStep[] = { OP_Next, OP_Prev }; |
| static const u8 aStart[] = { OP_Rewind, OP_Last }; |
| assert( bRev==0 || bRev==1 ); |
| if( pTabItem->fg.isRecursive ){ |
| /* Tables marked isRecursive have only a single row that is stored in |
| ** a pseudo-cursor. No need to Rewind or Next such cursors. */ |
| pLevel->op = OP_Noop; |
| }else{ |
| codeCursorHint(pTabItem, pWInfo, pLevel, 0); |
| pLevel->op = aStep[bRev]; |
| pLevel->p1 = iCur; |
| pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrHalt); |
| VdbeCoverageIf(v, bRev==0); |
| VdbeCoverageIf(v, bRev!=0); |
| pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP; |
| } |
| } |
| |
| #ifdef SQLITE_ENABLE_STMT_SCANSTATUS |
| pLevel->addrVisit = sqlite3VdbeCurrentAddr(v); |
| #endif |
| |
| /* Insert code to test every subexpression that can be completely |
| ** computed using the current set of tables. |
| ** |
| ** This loop may run between one and three times, depending on the |
| ** constraints to be generated. The value of stack variable iLoop |
| ** determines the constraints coded by each iteration, as follows: |
| ** |
| ** iLoop==1: Code only expressions that are entirely covered by pIdx. |
| ** iLoop==2: Code remaining expressions that do not contain correlated |
| ** sub-queries. |
| ** iLoop==3: Code all remaining expressions. |
| ** |
| ** An effort is made to skip unnecessary iterations of the loop. |
| */ |
| iLoop = (pIdx ? 1 : 2); |
| do{ |
| int iNext = 0; /* Next value for iLoop */ |
| for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){ |
| Expr *pE; |
| int skipLikeAddr = 0; |
| testcase( pTerm->wtFlags & TERM_VIRTUAL ); |
| testcase( pTerm->wtFlags & TERM_CODED ); |
| if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue; |
| if( (pTerm->prereqAll & pLevel->notReady)!=0 ){ |
| testcase( pWInfo->untestedTerms==0 |
| && (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)!=0 ); |
| pWInfo->untestedTerms = 1; |
| continue; |
| } |
| pE = pTerm->pExpr; |
| assert( pE!=0 ); |
| if( (pTabItem->fg.jointype&JT_LEFT) && !ExprHasProperty(pE,EP_FromJoin) ){ |
| continue; |
| } |
| |
| if( iLoop==1 && !sqlite3ExprCoveredByIndex(pE, pLevel->iTabCur, pIdx) ){ |
| iNext = 2; |
| continue; |
| } |
| if( iLoop<3 && (pTerm->wtFlags & TERM_VARSELECT) ){ |
| if( iNext==0 ) iNext = 3; |
| continue; |
| } |
| |
| if( (pTerm->wtFlags & TERM_LIKECOND)!=0 ){ |
| /* If the TERM_LIKECOND flag is set, that means that the range search |
| ** is sufficient to guarantee that the LIKE operator is true, so we |
| ** can skip the call to the like(A,B) function. But this only works |
| ** for strings. So do not skip the call to the function on the pass |
| ** that compares BLOBs. */ |
| #ifdef SQLITE_LIKE_DOESNT_MATCH_BLOBS |
| continue; |
| #else |
| u32 x = pLevel->iLikeRepCntr; |
| if( x>0 ){ |
| skipLikeAddr = sqlite3VdbeAddOp1(v, (x&1)?OP_IfNot:OP_If,(int)(x>>1)); |
| } |
| VdbeCoverage(v); |
| #endif |
| } |
| #ifdef WHERETRACE_ENABLED /* 0xffff */ |
| if( sqlite3WhereTrace ){ |
| VdbeNoopComment((v, "WhereTerm[%d] (%p) priority=%d", |
| pWC->nTerm-j, pTerm, iLoop)); |
| } |
| #endif |
| sqlite3ExprIfFalse(pParse, pE, addrCont, SQLITE_JUMPIFNULL); |
| if( skipLikeAddr ) sqlite3VdbeJumpHere(v, skipLikeAddr); |
| pTerm->wtFlags |= TERM_CODED; |
| } |
| iLoop = iNext; |
| }while( iLoop>0 ); |
| |
| /* Insert code to test for implied constraints based on transitivity |
| ** of the "==" operator. |
| ** |
| ** Example: If the WHERE clause contains "t1.a=t2.b" and "t2.b=123" |
| ** and we are coding the t1 loop and the t2 loop has not yet coded, |
| ** then we cannot use the "t1.a=t2.b" constraint, but we can code |
| ** the implied "t1.a=123" constraint. |
| */ |
| for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){ |
| Expr *pE, sEAlt; |
| WhereTerm *pAlt; |
| if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue; |
| if( (pTerm->eOperator & (WO_EQ|WO_IS))==0 ) continue; |
| if( (pTerm->eOperator & WO_EQUIV)==0 ) continue; |
| if( pTerm->leftCursor!=iCur ) continue; |
| if( pLevel->iLeftJoin ) continue; |
| pE = pTerm->pExpr; |
| assert( !ExprHasProperty(pE, EP_FromJoin) ); |
| assert( (pTerm->prereqRight & pLevel->notReady)!=0 ); |
| pAlt = sqlite3WhereFindTerm(pWC, iCur, pTerm->u.leftColumn, notReady, |
| WO_EQ|WO_IN|WO_IS, 0); |
| if( pAlt==0 ) continue; |
| if( pAlt->wtFlags & (TERM_CODED) ) continue; |
| if( (pAlt->eOperator & WO_IN) |
| && (pAlt->pExpr->flags & EP_xIsSelect) |
| && (pAlt->pExpr->x.pSelect->pEList->nExpr>1) |
| ){ |
| continue; |
| } |
| testcase( pAlt->eOperator & WO_EQ ); |
| testcase( pAlt->eOperator & WO_IS ); |
| testcase( pAlt->eOperator & WO_IN ); |
| VdbeModuleComment((v, "begin transitive constraint")); |
| sEAlt = *pAlt->pExpr; |
| sEAlt.pLeft = pE->pLeft; |
| sqlite3ExprIfFalse(pParse, &sEAlt, addrCont, SQLITE_JUMPIFNULL); |
| } |
| |
| /* For a LEFT OUTER JOIN, generate code that will record the fact that |
| ** at least one row of the right table has matched the left table. |
| */ |
| if( pLevel->iLeftJoin ){ |
| pLevel->addrFirst = sqlite3VdbeCurrentAddr(v); |
| sqlite3VdbeAddOp2(v, OP_Integer, 1, pLevel->iLeftJoin); |
| VdbeComment((v, "record LEFT JOIN hit")); |
| for(pTerm=pWC->a, j=0; j<pWC->nTerm; j++, pTerm++){ |
| testcase( pTerm->wtFlags & TERM_VIRTUAL ); |
| testcase( pTerm->wtFlags & TERM_CODED ); |
| if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue; |
| if( (pTerm->prereqAll & pLevel->notReady)!=0 ){ |
| assert( pWInfo->untestedTerms ); |
| continue; |
| } |
| assert( pTerm->pExpr ); |
| sqlite3ExprIfFalse(pParse, pTerm->pExpr, addrCont, SQLITE_JUMPIFNULL); |
| pTerm->wtFlags |= TERM_CODED; |
| } |
| } |
| |
| return pLevel->notReady; |
| } |