Index: third_party/sqlite/sqlite-src-3100200/src/wherecode.c |
diff --git a/third_party/sqlite/sqlite-src-3100200/src/wherecode.c b/third_party/sqlite/sqlite-src-3100200/src/wherecode.c |
new file mode 100644 |
index 0000000000000000000000000000000000000000..bc72e0ac7d2819e416d7866fa16b6fa99ce7d802 |
--- /dev/null |
+++ b/third_party/sqlite/sqlite-src-3100200/src/wherecode.c |
@@ -0,0 +1,1675 @@ |
+/* |
+** 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; |
+} |