| /* |
| ** 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 |
| /* |
| ** 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 */ |
| int iTerm, /* Index of this term. First is zero */ |
| const char *zColumn, /* Name of the column */ |
| const char *zOp /* Name of the operator */ |
| ){ |
| if( iTerm ) sqlite3StrAccumAppend(pStr, " AND ", 5); |
| sqlite3StrAccumAppendAll(pStr, zColumn); |
| sqlite3StrAccumAppend(pStr, zOp, 1); |
| sqlite3StrAccumAppend(pStr, "?", 1); |
| } |
| |
| /* |
| ** 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; |
| } |
| |
| /* |
| ** 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; |
| sqlite3StrAccumAppend(pStr, " (", 2); |
| for(i=0; i<nEq; i++){ |
| const char *z = explainIndexColumnName(pIndex, i); |
| if( i ) sqlite3StrAccumAppend(pStr, " AND ", 5); |
| sqlite3XPrintf(pStr, 0, i>=nSkip ? "%s=?" : "ANY(%s)", z); |
| } |
| |
| j = i; |
| if( pLoop->wsFlags&WHERE_BTM_LIMIT ){ |
| const char *z = explainIndexColumnName(pIndex, i); |
| explainAppendTerm(pStr, i++, z, ">"); |
| } |
| if( pLoop->wsFlags&WHERE_TOP_LIMIT ){ |
| const char *z = explainIndexColumnName(pIndex, j); |
| explainAppendTerm(pStr, i, z, "<"); |
| } |
| sqlite3StrAccumAppend(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 */ |
| int iLevel, /* Value for "level" column of output */ |
| int iFrom, /* Value for "from" column of output */ |
| u16 wctrlFlags /* Flags passed to sqlite3WhereBegin() */ |
| ){ |
| int ret = 0; |
| #if !defined(SQLITE_DEBUG) && !defined(SQLITE_ENABLE_STMT_SCANSTATUS) |
| if( 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 iId = pParse->iSelectId; /* Select id (left-most output column) */ |
| 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_ONETABLE_ONLY) ) 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); |
| sqlite3StrAccumAppendAll(&str, isSearch ? "SEARCH" : "SCAN"); |
| if( pItem->pSelect ){ |
| sqlite3XPrintf(&str, 0, " SUBQUERY %d", pItem->iSelectId); |
| }else{ |
| sqlite3XPrintf(&str, 0, " TABLE %s", pItem->zName); |
| } |
| |
| if( pItem->zAlias ){ |
| sqlite3XPrintf(&str, 0, " 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 ){ |
| sqlite3StrAccumAppend(&str, " USING ", 7); |
| sqlite3XPrintf(&str, 0, 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 = "<"; |
| } |
| sqlite3XPrintf(&str, 0, " USING INTEGER PRIMARY KEY (rowid%s?)",zRangeOp); |
| } |
| #ifndef SQLITE_OMIT_VIRTUALTABLE |
| else if( (flags & WHERE_VIRTUALTABLE)!=0 ){ |
| sqlite3XPrintf(&str, 0, " VIRTUAL TABLE INDEX %d:%s", |
| pLoop->u.vtab.idxNum, pLoop->u.vtab.idxStr); |
| } |
| #endif |
| #ifdef SQLITE_EXPLAIN_ESTIMATED_ROWS |
| if( pLoop->nOut>=10 ){ |
| sqlite3XPrintf(&str, 0, " (~%llu rows)", sqlite3LogEstToInt(pLoop->nOut)); |
| }else{ |
| sqlite3StrAccumAppend(&str, " (~1 row)", 9); |
| } |
| #endif |
| zMsg = sqlite3StrAccumFinish(&str); |
| ret = sqlite3VdbeAddOp4(v, OP_Explain, iId, iLevel, iFrom, 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; |
| while( pTerm |
| && (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]; |
| 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 ){ |
| sqlite3VdbeAddOp2(v, OP_Affinity, base, n); |
| sqlite3VdbeChangeP4(v, -1, zAff, n); |
| sqlite3ExprCacheAffinityChange(pParse, base, n); |
| } |
| } |
| |
| |
| /* |
| ** 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 register iReg. |
| ** |
| ** For a constraint of the form X=expr, the expression is evaluated and its |
| ** result is left on the stack. 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( 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; |
| int iTab; |
| struct InLoop *pIn; |
| WhereLoop *pLoop = pLevel->pWLoop; |
| |
| 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; |
| eType = sqlite3FindInIndex(pParse, pX, IN_INDEX_LOOP, 0); |
| if( eType==IN_INDEX_INDEX_DESC ){ |
| testcase( bRev ); |
| bRev = !bRev; |
| } |
| iTab = pX->iTable; |
| 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(v); |
| } |
| pLevel->u.in.nIn++; |
| 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 ){ |
| pIn += pLevel->u.in.nIn - 1; |
| pIn->iCur = iTab; |
| if( eType==IN_INDEX_ROWID ){ |
| pIn->addrInTop = sqlite3VdbeAddOp2(v, OP_Rowid, iTab, iReg); |
| }else{ |
| pIn->addrInTop = sqlite3VdbeAddOp3(v, OP_Column, iTab, 0, iReg); |
| } |
| pIn->eEndLoopOp = bRev ? OP_PrevIfOpen : OP_NextIfOpen; |
| sqlite3VdbeAddOp1(v, OP_IsNull, iReg); VdbeCoverage(v); |
| }else{ |
| pLevel->u.in.nIn = 0; |
| } |
| #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)); |
| if( !zAff ){ |
| pParse->db->mallocFailed = 1; |
| } |
| |
| 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); |
| } |
| } |
| testcase( pTerm->eOperator & WO_ISNULL ); |
| testcase( pTerm->eOperator & WO_IN ); |
| if( (pTerm->eOperator & (WO_ISNULL|WO_IN))==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 contraint |
| ** that originated from the LIKE optimization, then change the P3 to be |
| ** pLoop->iLikeRepCntr and set P5. |
| ** |
| ** 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 contants 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 = pLevel->iLikeRepCntr; |
| pOp->p5 = 1; |
| } |
| } |
| #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; |
| } |
| |
| |
| /* |
| ** 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 ){ |
| Vdbe *v = pWalker->pParse->pVdbe; |
| int reg = ++pWalker->pParse->nMem; /* Register for column value */ |
| sqlite3ExprCodeGetColumnOfTable( |
| v, pExpr->pTab, pExpr->iTable, pExpr->iColumn, 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( |
| 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; |
| 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) /* No-op */ |
| #endif /* SQLITE_ENABLE_CURSOR_HINTS */ |
| |
| /* |
| ** Generate code for the start of the iLevel-th loop in the WHERE clause |
| ** implementation described by pWInfo. |
| */ |
| Bitmask sqlite3WhereCodeOneLoopStart( |
| WhereInfo *pWInfo, /* Complete information about the WHERE clause */ |
| int iLevel, /* Which level of pWInfo->a[] should be coded */ |
| 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 omitTable; /* True if we use the index only */ |
| int bRev; /* True if we need to scan in reverse order */ |
| WhereLevel *pLevel; /* The where level to be coded */ |
| WhereLoop *pLoop; /* The WhereLoop object being coded */ |
| WhereClause *pWC; /* Decomposition of the entire WHERE clause */ |
| WhereTerm *pTerm; /* A WHERE clause term */ |
| Parse *pParse; /* Parsing context */ |
| sqlite3 *db; /* Database connection */ |
| Vdbe *v; /* The prepared stmt under constructions */ |
| struct SrcList_item *pTabItem; /* FROM clause term being coded */ |
| int addrBrk; /* Jump here to break out of the loop */ |
| 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 */ |
| |
| pParse = pWInfo->pParse; |
| v = pParse->pVdbe; |
| pWC = &pWInfo->sWC; |
| db = pParse->db; |
| pLevel = &pWInfo->a[iLevel]; |
| pLoop = pLevel->pWLoop; |
| pTabItem = &pWInfo->pTabList->a[pLevel->iFrom]; |
| iCur = pTabItem->iCursor; |
| pLevel->notReady = notReady & ~sqlite3WhereGetMask(&pWInfo->sMaskSet, iCur); |
| bRev = (pWInfo->revMask>>iLevel)&1; |
| omitTable = (pLoop->wsFlags & WHERE_IDX_ONLY)!=0 |
| && (pWInfo->wctrlFlags & WHERE_FORCE_TABLE)==0; |
| 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(v); |
| addrCont = pLevel->addrCont = sqlite3VdbeMakeLabel(v); |
| |
| /* 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. |
| */ |
| 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")); |
| } |
| |
| /* 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; |
| |
| sqlite3ExprCachePush(pParse); |
| iReg = sqlite3GetTempRange(pParse, nConstraint+2); |
| addrNotFound = pLevel->addrBrk; |
| for(j=0; j<nConstraint; j++){ |
| int iTarget = iReg+j+2; |
| pTerm = pLoop->aLTerm[j]; |
| if( pTerm==0 ) continue; |
| if( pTerm->eOperator & WO_IN ){ |
| codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, iTarget); |
| addrNotFound = pLevel->addrNxt; |
| }else{ |
| sqlite3ExprCode(pParse, pTerm->pExpr->pRight, iTarget); |
| } |
| } |
| 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_MPRINTF : P4_STATIC); |
| VdbeCoverage(v); |
| pLoop->u.vtab.needFree = 0; |
| for(j=0; j<nConstraint && j<16; j++){ |
| if( (pLoop->u.vtab.omitMask>>j)&1 ){ |
| disableTerm(pLevel, pLoop->aLTerm[j]); |
| } |
| } |
| pLevel->p1 = iCur; |
| pLevel->op = pWInfo->eOnePass ? OP_Noop : OP_VNext; |
| pLevel->p2 = sqlite3VdbeCurrentAddr(v); |
| sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2); |
| sqlite3ExprCachePop(pParse); |
| }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 ); |
| assert( omitTable==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; |
| sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt); VdbeCoverage(v); |
| sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, iRowidReg); |
| VdbeCoverage(v); |
| sqlite3ExprCacheAffinityChange(pParse, iRowidReg, 1); |
| sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg); |
| VdbeComment((v, "pk")); |
| 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; |
| |
| assert( omitTable==0 ); |
| 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(pWInfo, pLevel, pEnd); |
| if( pStart ){ |
| Expr *pX; /* The expression that defines the start bound */ |
| int r1, rTemp; /* Registers for holding the start boundary */ |
| |
| /* 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 */ |
| r1 = sqlite3ExprCodeTemp(pParse, pX->pRight, &rTemp); |
| sqlite3VdbeAddOp3(v, aMoveOp[pX->op-TK_GT], 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); |
| sqlite3ExprCacheAffinityChange(pParse, r1, 1); |
| sqlite3ReleaseTempReg(pParse, rTemp); |
| disableTerm(pLevel, pStart); |
| }else{ |
| sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iCur, addrBrk); |
| 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; |
| sqlite3ExprCode(pParse, pX->pRight, memEndValue); |
| if( pX->op==TK_LT || pX->op==TK_GT ){ |
| testOp = bRev ? OP_Le : OP_Ge; |
| }else{ |
| testOp = bRev ? OP_Lt : OP_Gt; |
| } |
| 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); |
| sqlite3ExprCacheStore(pParse, iCur, -1, 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 */ |
| 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 */ |
| Index *pIdx; /* The index we will be using */ |
| 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 cEndAff = 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 */ |
| |
| 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 = 1; |
| /* 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 = 1; |
| #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 = ++pParse->nMem; |
| testcase( bRev ); |
| testcase( pIdx->aSortOrder[nEq]==SQLITE_SO_DESC ); |
| sqlite3VdbeAddOp2(v, OP_Integer, |
| bRev ^ (pIdx->aSortOrder[nEq]==SQLITE_SO_DESC), |
| pLevel->iLikeRepCntr); |
| VdbeComment((v, "LIKE loop counter")); |
| pLevel->addrLikeRep = sqlite3VdbeCurrentAddr(v); |
| } |
| #endif |
| if( pRangeStart==0 |
| && (j = pIdx->aiColumn[nEq])>=0 |
| && pIdx->pTable->aCol[j].notNull==0 |
| ){ |
| 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); |
| } |
| |
| /* 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(pWInfo, pLevel, pRangeEnd); |
| regBase = codeAllEqualityTerms(pParse,pLevel,bRev,nExtraReg,&zStartAff); |
| assert( zStartAff==0 || sqlite3Strlen30(zStartAff)>=nEq ); |
| if( zStartAff ) cEndAff = 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; |
| sqlite3ExprCode(pParse, pRight, regBase+nEq); |
| whereLikeOptimizationStringFixup(v, pLevel, pRangeStart); |
| if( (pRangeStart->wtFlags & TERM_VNULL)==0 |
| && sqlite3ExprCanBeNull(pRight) |
| ){ |
| sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt); |
| VdbeCoverage(v); |
| } |
| if( zStartAff ){ |
| if( sqlite3CompareAffinity(pRight, zStartAff[nEq])==SQLITE_AFF_BLOB){ |
| /* Since the comparison is to be performed with no conversions |
| ** applied to the operands, set the affinity to apply to pRight to |
| ** SQLITE_AFF_BLOB. */ |
| zStartAff[nEq] = SQLITE_AFF_BLOB; |
| } |
| if( sqlite3ExprNeedsNoAffinityChange(pRight, zStartAff[nEq]) ){ |
| zStartAff[nEq] = SQLITE_AFF_BLOB; |
| } |
| } |
| nConstraint++; |
| testcase( pRangeStart->wtFlags & TERM_VIRTUAL ); |
| }else if( bSeekPastNull ){ |
| sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq); |
| nConstraint++; |
| startEq = 0; |
| start_constraints = 1; |
| } |
| codeApplyAffinity(pParse, regBase, nConstraint - bSeekPastNull, zStartAff); |
| 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; |
| sqlite3ExprCacheRemove(pParse, regBase+nEq, 1); |
| sqlite3ExprCode(pParse, pRight, regBase+nEq); |
| whereLikeOptimizationStringFixup(v, pLevel, pRangeEnd); |
| if( (pRangeEnd->wtFlags & TERM_VNULL)==0 |
| && sqlite3ExprCanBeNull(pRight) |
| ){ |
| sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt); |
| VdbeCoverage(v); |
| } |
| if( sqlite3CompareAffinity(pRight, cEndAff)!=SQLITE_AFF_BLOB |
| && !sqlite3ExprNeedsNoAffinityChange(pRight, cEndAff) |
| ){ |
| codeApplyAffinity(pParse, regBase+nEq, 1, &cEndAff); |
| } |
| nConstraint++; |
| testcase( pRangeEnd->wtFlags & TERM_VIRTUAL ); |
| }else if( bStopAtNull ){ |
| sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq); |
| endEq = 0; |
| nConstraint++; |
| } |
| sqlite3DbFree(db, zStartAff); |
| |
| /* 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 ); |
| } |
| |
| /* Seek the table cursor, if required */ |
| disableTerm(pLevel, pRangeStart); |
| disableTerm(pLevel, pRangeEnd); |
| if( omitTable ){ |
| /* pIdx is a covering index. No need to access the main table. */ |
| }else if( HasRowid(pIdx->pTable) ){ |
| iRowidReg = ++pParse->nMem; |
| sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, iRowidReg); |
| sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg); |
| if( pWInfo->eOnePass!=ONEPASS_OFF ){ |
| sqlite3VdbeAddOp3(v, OP_NotExists, iCur, 0, iRowidReg); |
| VdbeCoverage(v); |
| }else{ |
| sqlite3VdbeAddOp2(v, OP_Seek, iCur, iRowidReg); /* Deferred seek */ |
| } |
| }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); |
| } |
| |
| /* Record the instruction used to terminate the loop. Disable |
| ** WHERE clause terms made redundant by the index range scan. |
| */ |
| 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 ); |
| } |
| }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(v); /* 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; |
| if( ExprHasProperty(pExpr, EP_FromJoin) ) continue; |
| if( (pWC->a[iTerm].wtFlags & TERM_VIRTUAL)!=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, 0); |
| } |
| } |
| |
| /* 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_OMIT_OPEN_CLOSE |
| | WHERE_FORCE_TABLE |
| | WHERE_ONETABLE_ONLY |
| | WHERE_NO_AUTOINDEX; |
| 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 */ |
| if( pAndExpr && !ExprHasProperty(pOrExpr, EP_FromJoin) ){ |
| pAndExpr->pLeft = pOrExpr; |
| pOrExpr = pAndExpr; |
| } |
| /* Loop through table entries that match term pOrTerm. */ |
| 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], iLevel, pLevel->iFrom, 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 r; |
| int iSet = ((ii==pOrWc->nTerm-1)?-1:ii); |
| if( HasRowid(pTab) ){ |
| r = sqlite3ExprCodeGetColumn(pParse, pTab, -1, iCur, regRowid, 0); |
| jmp1 = sqlite3VdbeAddOp4Int(v, OP_RowSetTest, regRowset, 0, |
| r,iSet); |
| VdbeCoverage(v); |
| }else{ |
| Index *pPk = sqlite3PrimaryKeyIndex(pTab); |
| int nPk = pPk->nKeyCol; |
| int iPk; |
| |
| /* Read the PK into an array of temp registers. */ |
| r = sqlite3GetTempRange(pParse, nPk); |
| for(iPk=0; iPk<nPk; iPk++){ |
| int iCol = pPk->aiColumn[iPk]; |
| sqlite3ExprCodeGetColumnToReg(pParse, pTab, iCol, iCur, 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); |
| sqlite3VdbeAddOp3(v, OP_IdxInsert, regRowset, regRowid, 0); |
| 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; |
| wctrlFlags |= WHERE_REOPEN_IDX; |
| }else{ |
| pCov = 0; |
| } |
| |
| /* Finish the loop through table entries that match term pOrTerm. */ |
| sqlite3WhereEnd(pSubWInfo); |
| } |
| } |
| } |
| 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(pWInfo, pLevel, 0); |
| pLevel->op = aStep[bRev]; |
| pLevel->p1 = iCur; |
| pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk); |
| 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. |
| */ |
| 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_ONETABLE_ONLY)!=0 ); |
| pWInfo->untestedTerms = 1; |
| continue; |
| } |
| pE = pTerm->pExpr; |
| assert( pE!=0 ); |
| if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){ |
| continue; |
| } |
| if( pTerm->wtFlags & TERM_LIKECOND ){ |
| #ifdef SQLITE_LIKE_DOESNT_MATCH_BLOBS |
| continue; |
| #else |
| assert( pLevel->iLikeRepCntr>0 ); |
| skipLikeAddr = sqlite3VdbeAddOp1(v, OP_IfNot, pLevel->iLikeRepCntr); |
| VdbeCoverage(v); |
| #endif |
| } |
| sqlite3ExprIfFalse(pParse, pE, addrCont, SQLITE_JUMPIFNULL); |
| if( skipLikeAddr ) sqlite3VdbeJumpHere(v, skipLikeAddr); |
| pTerm->wtFlags |= TERM_CODED; |
| } |
| |
| /* 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, *pEAlt; |
| 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; |
| testcase( pAlt->eOperator & WO_EQ ); |
| testcase( pAlt->eOperator & WO_IS ); |
| testcase( pAlt->eOperator & WO_IN ); |
| VdbeModuleComment((v, "begin transitive constraint")); |
| pEAlt = sqlite3StackAllocRaw(db, sizeof(*pEAlt)); |
| if( pEAlt ){ |
| *pEAlt = *pAlt->pExpr; |
| pEAlt->pLeft = pE->pLeft; |
| sqlite3ExprIfFalse(pParse, pEAlt, addrCont, SQLITE_JUMPIFNULL); |
| sqlite3StackFree(db, pEAlt); |
| } |
| } |
| |
| /* For a LEFT OUTER JOIN, generate code that will record the fact that |
| ** 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")); |
| sqlite3ExprCacheClear(pParse); |
| 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; |
| } |