4 ** The author disclaims copyright to this source code. In place of
5 ** a legal notice, here is a blessing:
7 ** May you do good and not evil.
8 ** May you find forgiveness for yourself and forgive others.
9 ** May you share freely, never taking more than you give.
11 *************************************************************************
12 ** This module contains C code that generates VDBE code used to process
13 ** the WHERE clause of SQL statements.
15 ** This file was split off from where.c on 2015-06-06 in order to reduce the
16 ** size of where.c and make it easier to edit. This file contains the routines
17 ** that actually generate the bulk of the WHERE loop code. The original where.c
18 ** file retains the code that does query planning and analysis.
20 #include "sqliteInt.h"
23 #ifndef SQLITE_OMIT_EXPLAIN
26 ** Return the name of the i-th column of the pIdx index.
28 static const char *explainIndexColumnName(Index
*pIdx
, int i
){
29 i
= pIdx
->aiColumn
[i
];
30 if( i
==XN_EXPR
) return "<expr>";
31 if( i
==XN_ROWID
) return "rowid";
32 return pIdx
->pTable
->aCol
[i
].zName
;
36 ** This routine is a helper for explainIndexRange() below
38 ** pStr holds the text of an expression that we are building up one term
39 ** at a time. This routine adds a new term to the end of the expression.
40 ** Terms are separated by AND so add the "AND" text for second and subsequent
43 static void explainAppendTerm(
44 StrAccum
*pStr
, /* The text expression being built */
45 Index
*pIdx
, /* Index to read column names from */
46 int nTerm
, /* Number of terms */
47 int iTerm
, /* Zero-based index of first term. */
48 int bAnd
, /* Non-zero to append " AND " */
49 const char *zOp
/* Name of the operator */
54 if( bAnd
) sqlite3_str_append(pStr
, " AND ", 5);
56 if( nTerm
>1 ) sqlite3_str_append(pStr
, "(", 1);
57 for(i
=0; i
<nTerm
; i
++){
58 if( i
) sqlite3_str_append(pStr
, ",", 1);
59 sqlite3_str_appendall(pStr
, explainIndexColumnName(pIdx
, iTerm
+i
));
61 if( nTerm
>1 ) sqlite3_str_append(pStr
, ")", 1);
63 sqlite3_str_append(pStr
, zOp
, 1);
65 if( nTerm
>1 ) sqlite3_str_append(pStr
, "(", 1);
66 for(i
=0; i
<nTerm
; i
++){
67 if( i
) sqlite3_str_append(pStr
, ",", 1);
68 sqlite3_str_append(pStr
, "?", 1);
70 if( nTerm
>1 ) sqlite3_str_append(pStr
, ")", 1);
74 ** Argument pLevel describes a strategy for scanning table pTab. This
75 ** function appends text to pStr that describes the subset of table
76 ** rows scanned by the strategy in the form of an SQL expression.
78 ** For example, if the query:
80 ** SELECT * FROM t1 WHERE a=1 AND b>2;
82 ** is run and there is an index on (a, b), then this function returns a
87 static void explainIndexRange(StrAccum
*pStr
, WhereLoop
*pLoop
){
88 Index
*pIndex
= pLoop
->u
.btree
.pIndex
;
89 u16 nEq
= pLoop
->u
.btree
.nEq
;
90 u16 nSkip
= pLoop
->nSkip
;
93 if( nEq
==0 && (pLoop
->wsFlags
&(WHERE_BTM_LIMIT
|WHERE_TOP_LIMIT
))==0 ) return;
94 sqlite3_str_append(pStr
, " (", 2);
96 const char *z
= explainIndexColumnName(pIndex
, i
);
97 if( i
) sqlite3_str_append(pStr
, " AND ", 5);
98 sqlite3_str_appendf(pStr
, i
>=nSkip
? "%s=?" : "ANY(%s)", z
);
102 if( pLoop
->wsFlags
&WHERE_BTM_LIMIT
){
103 explainAppendTerm(pStr
, pIndex
, pLoop
->u
.btree
.nBtm
, j
, i
, ">");
106 if( pLoop
->wsFlags
&WHERE_TOP_LIMIT
){
107 explainAppendTerm(pStr
, pIndex
, pLoop
->u
.btree
.nTop
, j
, i
, "<");
109 sqlite3_str_append(pStr
, ")", 1);
113 ** This function is a no-op unless currently processing an EXPLAIN QUERY PLAN
114 ** command, or if either SQLITE_DEBUG or SQLITE_ENABLE_STMT_SCANSTATUS was
115 ** defined at compile-time. If it is not a no-op, a single OP_Explain opcode
116 ** is added to the output to describe the table scan strategy in pLevel.
118 ** If an OP_Explain opcode is added to the VM, its address is returned.
119 ** Otherwise, if no OP_Explain is coded, zero is returned.
121 int sqlite3WhereExplainOneScan(
122 Parse
*pParse
, /* Parse context */
123 SrcList
*pTabList
, /* Table list this loop refers to */
124 WhereLevel
*pLevel
, /* Scan to write OP_Explain opcode for */
125 u16 wctrlFlags
/* Flags passed to sqlite3WhereBegin() */
128 #if !defined(SQLITE_DEBUG) && !defined(SQLITE_ENABLE_STMT_SCANSTATUS)
129 if( sqlite3ParseToplevel(pParse
)->explain
==2 )
132 struct SrcList_item
*pItem
= &pTabList
->a
[pLevel
->iFrom
];
133 Vdbe
*v
= pParse
->pVdbe
; /* VM being constructed */
134 sqlite3
*db
= pParse
->db
; /* Database handle */
135 int isSearch
; /* True for a SEARCH. False for SCAN. */
136 WhereLoop
*pLoop
; /* The controlling WhereLoop object */
137 u32 flags
; /* Flags that describe this loop */
138 char *zMsg
; /* Text to add to EQP output */
139 StrAccum str
; /* EQP output string */
140 char zBuf
[100]; /* Initial space for EQP output string */
142 pLoop
= pLevel
->pWLoop
;
143 flags
= pLoop
->wsFlags
;
144 if( (flags
&WHERE_MULTI_OR
) || (wctrlFlags
&WHERE_OR_SUBCLAUSE
) ) return 0;
146 isSearch
= (flags
&(WHERE_BTM_LIMIT
|WHERE_TOP_LIMIT
))!=0
147 || ((flags
&WHERE_VIRTUALTABLE
)==0 && (pLoop
->u
.btree
.nEq
>0))
148 || (wctrlFlags
&(WHERE_ORDERBY_MIN
|WHERE_ORDERBY_MAX
));
150 sqlite3StrAccumInit(&str
, db
, zBuf
, sizeof(zBuf
), SQLITE_MAX_LENGTH
);
151 sqlite3_str_appendall(&str
, isSearch
? "SEARCH" : "SCAN");
152 if( pItem
->pSelect
){
153 sqlite3_str_appendf(&str
, " SUBQUERY %u", pItem
->pSelect
->selId
);
155 sqlite3_str_appendf(&str
, " TABLE %s", pItem
->zName
);
159 sqlite3_str_appendf(&str
, " AS %s", pItem
->zAlias
);
161 if( (flags
& (WHERE_IPK
|WHERE_VIRTUALTABLE
))==0 ){
162 const char *zFmt
= 0;
165 assert( pLoop
->u
.btree
.pIndex
!=0 );
166 pIdx
= pLoop
->u
.btree
.pIndex
;
167 assert( !(flags
&WHERE_AUTO_INDEX
) || (flags
&WHERE_IDX_ONLY
) );
168 if( !HasRowid(pItem
->pTab
) && IsPrimaryKeyIndex(pIdx
) ){
170 zFmt
= "PRIMARY KEY";
172 }else if( flags
& WHERE_PARTIALIDX
){
173 zFmt
= "AUTOMATIC PARTIAL COVERING INDEX";
174 }else if( flags
& WHERE_AUTO_INDEX
){
175 zFmt
= "AUTOMATIC COVERING INDEX";
176 }else if( flags
& WHERE_IDX_ONLY
){
177 zFmt
= "COVERING INDEX %s";
182 sqlite3_str_append(&str
, " USING ", 7);
183 sqlite3_str_appendf(&str
, zFmt
, pIdx
->zName
);
184 explainIndexRange(&str
, pLoop
);
186 }else if( (flags
& WHERE_IPK
)!=0 && (flags
& WHERE_CONSTRAINT
)!=0 ){
187 const char *zRangeOp
;
188 if( flags
&(WHERE_COLUMN_EQ
|WHERE_COLUMN_IN
) ){
190 }else if( (flags
&WHERE_BOTH_LIMIT
)==WHERE_BOTH_LIMIT
){
191 zRangeOp
= ">? AND rowid<";
192 }else if( flags
&WHERE_BTM_LIMIT
){
195 assert( flags
&WHERE_TOP_LIMIT
);
198 sqlite3_str_appendf(&str
,
199 " USING INTEGER PRIMARY KEY (rowid%s?)",zRangeOp
);
201 #ifndef SQLITE_OMIT_VIRTUALTABLE
202 else if( (flags
& WHERE_VIRTUALTABLE
)!=0 ){
203 sqlite3_str_appendf(&str
, " VIRTUAL TABLE INDEX %d:%s",
204 pLoop
->u
.vtab
.idxNum
, pLoop
->u
.vtab
.idxStr
);
207 #ifdef SQLITE_EXPLAIN_ESTIMATED_ROWS
208 if( pLoop
->nOut
>=10 ){
209 sqlite3_str_appendf(&str
, " (~%llu rows)",
210 sqlite3LogEstToInt(pLoop
->nOut
));
212 sqlite3_str_append(&str
, " (~1 row)", 9);
215 zMsg
= sqlite3StrAccumFinish(&str
);
216 ret
= sqlite3VdbeAddOp4(v
, OP_Explain
, sqlite3VdbeCurrentAddr(v
),
217 pParse
->addrExplain
, 0, zMsg
,P4_DYNAMIC
);
221 #endif /* SQLITE_OMIT_EXPLAIN */
223 #ifdef SQLITE_ENABLE_STMT_SCANSTATUS
225 ** Configure the VM passed as the first argument with an
226 ** sqlite3_stmt_scanstatus() entry corresponding to the scan used to
227 ** implement level pLvl. Argument pSrclist is a pointer to the FROM
228 ** clause that the scan reads data from.
230 ** If argument addrExplain is not 0, it must be the address of an
231 ** OP_Explain instruction that describes the same loop.
233 void sqlite3WhereAddScanStatus(
234 Vdbe
*v
, /* Vdbe to add scanstatus entry to */
235 SrcList
*pSrclist
, /* FROM clause pLvl reads data from */
236 WhereLevel
*pLvl
, /* Level to add scanstatus() entry for */
237 int addrExplain
/* Address of OP_Explain (or 0) */
239 const char *zObj
= 0;
240 WhereLoop
*pLoop
= pLvl
->pWLoop
;
241 if( (pLoop
->wsFlags
& WHERE_VIRTUALTABLE
)==0 && pLoop
->u
.btree
.pIndex
!=0 ){
242 zObj
= pLoop
->u
.btree
.pIndex
->zName
;
244 zObj
= pSrclist
->a
[pLvl
->iFrom
].zName
;
246 sqlite3VdbeScanStatus(
247 v
, addrExplain
, pLvl
->addrBody
, pLvl
->addrVisit
, pLoop
->nOut
, zObj
254 ** Disable a term in the WHERE clause. Except, do not disable the term
255 ** if it controls a LEFT OUTER JOIN and it did not originate in the ON
256 ** or USING clause of that join.
258 ** Consider the term t2.z='ok' in the following queries:
260 ** (1) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok'
261 ** (2) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok'
262 ** (3) SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok'
264 ** The t2.z='ok' is disabled in the in (2) because it originates
265 ** in the ON clause. The term is disabled in (3) because it is not part
266 ** of a LEFT OUTER JOIN. In (1), the term is not disabled.
268 ** Disabling a term causes that term to not be tested in the inner loop
269 ** of the join. Disabling is an optimization. When terms are satisfied
270 ** by indices, we disable them to prevent redundant tests in the inner
271 ** loop. We would get the correct results if nothing were ever disabled,
272 ** but joins might run a little slower. The trick is to disable as much
273 ** as we can without disabling too much. If we disabled in (1), we'd get
274 ** the wrong answer. See ticket #813.
276 ** If all the children of a term are disabled, then that term is also
277 ** automatically disabled. In this way, terms get disabled if derived
278 ** virtual terms are tested first. For example:
280 ** x GLOB 'abc*' AND x>='abc' AND x<'acd'
281 ** \___________/ \______/ \_____/
282 ** parent child1 child2
284 ** Only the parent term was in the original WHERE clause. The child1
285 ** and child2 terms were added by the LIKE optimization. If both of
286 ** the virtual child terms are valid, then testing of the parent can be
289 ** Usually the parent term is marked as TERM_CODED. But if the parent
290 ** term was originally TERM_LIKE, then the parent gets TERM_LIKECOND instead.
291 ** The TERM_LIKECOND marking indicates that the term should be coded inside
292 ** a conditional such that is only evaluated on the second pass of a
293 ** LIKE-optimization loop, when scanning BLOBs instead of strings.
295 static void disableTerm(WhereLevel
*pLevel
, WhereTerm
*pTerm
){
298 while( (pTerm
->wtFlags
& TERM_CODED
)==0
299 && (pLevel
->iLeftJoin
==0 || ExprHasProperty(pTerm
->pExpr
, EP_FromJoin
))
300 && (pLevel
->notReady
& pTerm
->prereqAll
)==0
302 if( nLoop
&& (pTerm
->wtFlags
& TERM_LIKE
)!=0 ){
303 pTerm
->wtFlags
|= TERM_LIKECOND
;
305 pTerm
->wtFlags
|= TERM_CODED
;
307 if( pTerm
->iParent
<0 ) break;
308 pTerm
= &pTerm
->pWC
->a
[pTerm
->iParent
];
311 if( pTerm
->nChild
!=0 ) break;
317 ** Code an OP_Affinity opcode to apply the column affinity string zAff
318 ** to the n registers starting at base.
320 ** As an optimization, SQLITE_AFF_BLOB entries (which are no-ops) at the
321 ** beginning and end of zAff are ignored. If all entries in zAff are
322 ** SQLITE_AFF_BLOB, then no code gets generated.
324 ** This routine makes its own copy of zAff so that the caller is free
325 ** to modify zAff after this routine returns.
327 static void codeApplyAffinity(Parse
*pParse
, int base
, int n
, char *zAff
){
328 Vdbe
*v
= pParse
->pVdbe
;
330 assert( pParse
->db
->mallocFailed
);
335 /* Adjust base and n to skip over SQLITE_AFF_BLOB entries at the beginning
336 ** and end of the affinity string.
338 while( n
>0 && zAff
[0]==SQLITE_AFF_BLOB
){
343 while( n
>1 && zAff
[n
-1]==SQLITE_AFF_BLOB
){
347 /* Code the OP_Affinity opcode if there is anything left to do. */
349 sqlite3VdbeAddOp4(v
, OP_Affinity
, base
, n
, 0, zAff
, n
);
354 ** Expression pRight, which is the RHS of a comparison operation, is
355 ** either a vector of n elements or, if n==1, a scalar expression.
356 ** Before the comparison operation, affinity zAff is to be applied
357 ** to the pRight values. This function modifies characters within the
358 ** affinity string to SQLITE_AFF_BLOB if either:
360 ** * the comparison will be performed with no affinity, or
361 ** * the affinity change in zAff is guaranteed not to change the value.
363 static void updateRangeAffinityStr(
364 Expr
*pRight
, /* RHS of comparison */
365 int n
, /* Number of vector elements in comparison */
366 char *zAff
/* Affinity string to modify */
370 Expr
*p
= sqlite3VectorFieldSubexpr(pRight
, i
);
371 if( sqlite3CompareAffinity(p
, zAff
[i
])==SQLITE_AFF_BLOB
372 || sqlite3ExprNeedsNoAffinityChange(p
, zAff
[i
])
374 zAff
[i
] = SQLITE_AFF_BLOB
;
381 ** pX is an expression of the form: (vector) IN (SELECT ...)
382 ** In other words, it is a vector IN operator with a SELECT clause on the
383 ** LHS. But not all terms in the vector are indexable and the terms might
384 ** not be in the correct order for indexing.
386 ** This routine makes a copy of the input pX expression and then adjusts
387 ** the vector on the LHS with corresponding changes to the SELECT so that
388 ** the vector contains only index terms and those terms are in the correct
389 ** order. The modified IN expression is returned. The caller is responsible
390 ** for deleting the returned expression.
394 ** CREATE TABLE t1(a,b,c,d,e,f);
395 ** CREATE INDEX t1x1 ON t1(e,c);
396 ** SELECT * FROM t1 WHERE (a,b,c,d,e) IN (SELECT v,w,x,y,z FROM t2)
397 ** \_______________________________________/
400 ** Since only columns e and c can be used with the index, in that order,
401 ** the modified IN expression that is returned will be:
403 ** (e,c) IN (SELECT z,x FROM t2)
405 ** The reduced pX is different from the original (obviously) and thus is
406 ** only used for indexing, to improve performance. The original unaltered
407 ** IN expression must also be run on each output row for correctness.
409 static Expr
*removeUnindexableInClauseTerms(
410 Parse
*pParse
, /* The parsing context */
411 int iEq
, /* Look at loop terms starting here */
412 WhereLoop
*pLoop
, /* The current loop */
413 Expr
*pX
/* The IN expression to be reduced */
415 sqlite3
*db
= pParse
->db
;
416 Expr
*pNew
= sqlite3ExprDup(db
, pX
, 0);
417 if( db
->mallocFailed
==0 ){
418 ExprList
*pOrigRhs
= pNew
->x
.pSelect
->pEList
; /* Original unmodified RHS */
419 ExprList
*pOrigLhs
= pNew
->pLeft
->x
.pList
; /* Original unmodified LHS */
420 ExprList
*pRhs
= 0; /* New RHS after modifications */
421 ExprList
*pLhs
= 0; /* New LHS after mods */
422 int i
; /* Loop counter */
423 Select
*pSelect
; /* Pointer to the SELECT on the RHS */
425 for(i
=iEq
; i
<pLoop
->nLTerm
; i
++){
426 if( pLoop
->aLTerm
[i
]->pExpr
==pX
){
427 int iField
= pLoop
->aLTerm
[i
]->iField
- 1;
428 assert( pOrigRhs
->a
[iField
].pExpr
!=0 );
429 pRhs
= sqlite3ExprListAppend(pParse
, pRhs
, pOrigRhs
->a
[iField
].pExpr
);
430 pOrigRhs
->a
[iField
].pExpr
= 0;
431 assert( pOrigLhs
->a
[iField
].pExpr
!=0 );
432 pLhs
= sqlite3ExprListAppend(pParse
, pLhs
, pOrigLhs
->a
[iField
].pExpr
);
433 pOrigLhs
->a
[iField
].pExpr
= 0;
436 sqlite3ExprListDelete(db
, pOrigRhs
);
437 sqlite3ExprListDelete(db
, pOrigLhs
);
438 pNew
->pLeft
->x
.pList
= pLhs
;
439 pNew
->x
.pSelect
->pEList
= pRhs
;
440 if( pLhs
&& pLhs
->nExpr
==1 ){
441 /* Take care here not to generate a TK_VECTOR containing only a
442 ** single value. Since the parser never creates such a vector, some
443 ** of the subroutines do not handle this case. */
444 Expr
*p
= pLhs
->a
[0].pExpr
;
445 pLhs
->a
[0].pExpr
= 0;
446 sqlite3ExprDelete(db
, pNew
->pLeft
);
449 pSelect
= pNew
->x
.pSelect
;
450 if( pSelect
->pOrderBy
){
451 /* If the SELECT statement has an ORDER BY clause, zero the
452 ** iOrderByCol variables. These are set to non-zero when an
453 ** ORDER BY term exactly matches one of the terms of the
454 ** result-set. Since the result-set of the SELECT statement may
455 ** have been modified or reordered, these variables are no longer
456 ** set correctly. Since setting them is just an optimization,
457 ** it's easiest just to zero them here. */
458 ExprList
*pOrderBy
= pSelect
->pOrderBy
;
459 for(i
=0; i
<pOrderBy
->nExpr
; i
++){
460 pOrderBy
->a
[i
].u
.x
.iOrderByCol
= 0;
465 printf("For indexing, change the IN expr:\n");
466 sqlite3TreeViewExpr(0, pX
, 0);
468 sqlite3TreeViewExpr(0, pNew
, 0);
476 ** Generate code for a single equality term of the WHERE clause. An equality
477 ** term can be either X=expr or X IN (...). pTerm is the term to be
480 ** The current value for the constraint is left in a register, the index
481 ** of which is returned. An attempt is made store the result in iTarget but
482 ** this is only guaranteed for TK_ISNULL and TK_IN constraints. If the
483 ** constraint is a TK_EQ or TK_IS, then the current value might be left in
484 ** some other register and it is the caller's responsibility to compensate.
486 ** For a constraint of the form X=expr, the expression is evaluated in
487 ** straight-line code. For constraints of the form X IN (...)
488 ** this routine sets up a loop that will iterate over all values of X.
490 static int codeEqualityTerm(
491 Parse
*pParse
, /* The parsing context */
492 WhereTerm
*pTerm
, /* The term of the WHERE clause to be coded */
493 WhereLevel
*pLevel
, /* The level of the FROM clause we are working on */
494 int iEq
, /* Index of the equality term within this level */
495 int bRev
, /* True for reverse-order IN operations */
496 int iTarget
/* Attempt to leave results in this register */
498 Expr
*pX
= pTerm
->pExpr
;
499 Vdbe
*v
= pParse
->pVdbe
;
500 int iReg
; /* Register holding results */
502 assert( pLevel
->pWLoop
->aLTerm
[iEq
]==pTerm
);
504 if( pX
->op
==TK_EQ
|| pX
->op
==TK_IS
){
505 iReg
= sqlite3ExprCodeTarget(pParse
, pX
->pRight
, iTarget
);
506 }else if( pX
->op
==TK_ISNULL
){
508 sqlite3VdbeAddOp2(v
, OP_Null
, 0, iReg
);
509 #ifndef SQLITE_OMIT_SUBQUERY
511 int eType
= IN_INDEX_NOOP
;
514 WhereLoop
*pLoop
= pLevel
->pWLoop
;
519 if( (pLoop
->wsFlags
& WHERE_VIRTUALTABLE
)==0
520 && pLoop
->u
.btree
.pIndex
!=0
521 && pLoop
->u
.btree
.pIndex
->aSortOrder
[iEq
]
527 assert( pX
->op
==TK_IN
);
530 for(i
=0; i
<iEq
; i
++){
531 if( pLoop
->aLTerm
[i
] && pLoop
->aLTerm
[i
]->pExpr
==pX
){
532 disableTerm(pLevel
, pTerm
);
536 for(i
=iEq
;i
<pLoop
->nLTerm
; i
++){
537 assert( pLoop
->aLTerm
[i
]!=0 );
538 if( pLoop
->aLTerm
[i
]->pExpr
==pX
) nEq
++;
541 if( (pX
->flags
& EP_xIsSelect
)==0 || pX
->x
.pSelect
->pEList
->nExpr
==1 ){
542 eType
= sqlite3FindInIndex(pParse
, pX
, IN_INDEX_LOOP
, 0, 0);
544 sqlite3
*db
= pParse
->db
;
545 pX
= removeUnindexableInClauseTerms(pParse
, iEq
, pLoop
, pX
);
547 if( !db
->mallocFailed
){
548 aiMap
= (int*)sqlite3DbMallocZero(pParse
->db
, sizeof(int)*nEq
);
549 eType
= sqlite3FindInIndex(pParse
, pX
, IN_INDEX_LOOP
, 0, aiMap
);
550 pTerm
->pExpr
->iTable
= pX
->iTable
;
552 sqlite3ExprDelete(db
, pX
);
556 if( eType
==IN_INDEX_INDEX_DESC
){
561 sqlite3VdbeAddOp2(v
, bRev
? OP_Last
: OP_Rewind
, iTab
, 0);
562 VdbeCoverageIf(v
, bRev
);
563 VdbeCoverageIf(v
, !bRev
);
564 assert( (pLoop
->wsFlags
& WHERE_MULTI_OR
)==0 );
566 pLoop
->wsFlags
|= WHERE_IN_ABLE
;
567 if( pLevel
->u
.in
.nIn
==0 ){
568 pLevel
->addrNxt
= sqlite3VdbeMakeLabel(v
);
571 i
= pLevel
->u
.in
.nIn
;
572 pLevel
->u
.in
.nIn
+= nEq
;
573 pLevel
->u
.in
.aInLoop
=
574 sqlite3DbReallocOrFree(pParse
->db
, pLevel
->u
.in
.aInLoop
,
575 sizeof(pLevel
->u
.in
.aInLoop
[0])*pLevel
->u
.in
.nIn
);
576 pIn
= pLevel
->u
.in
.aInLoop
;
578 int iMap
= 0; /* Index in aiMap[] */
580 for(i
=iEq
;i
<pLoop
->nLTerm
; i
++){
581 if( pLoop
->aLTerm
[i
]->pExpr
==pX
){
582 int iOut
= iReg
+ i
- iEq
;
583 if( eType
==IN_INDEX_ROWID
){
584 testcase( nEq
>1 ); /* Happens with a UNIQUE index on ROWID */
585 pIn
->addrInTop
= sqlite3VdbeAddOp2(v
, OP_Rowid
, iTab
, iOut
);
587 int iCol
= aiMap
? aiMap
[iMap
++] : 0;
588 pIn
->addrInTop
= sqlite3VdbeAddOp3(v
,OP_Column
,iTab
, iCol
, iOut
);
590 sqlite3VdbeAddOp1(v
, OP_IsNull
, iOut
); VdbeCoverage(v
);
593 pIn
->eEndLoopOp
= bRev
? OP_Prev
: OP_Next
;
594 if( iEq
>0 && (pLoop
->wsFlags
& WHERE_VIRTUALTABLE
)==0 ){
595 pIn
->iBase
= iReg
- i
;
597 pLoop
->wsFlags
|= WHERE_IN_EARLYOUT
;
602 pIn
->eEndLoopOp
= OP_Noop
;
608 pLevel
->u
.in
.nIn
= 0;
610 sqlite3DbFree(pParse
->db
, aiMap
);
613 disableTerm(pLevel
, pTerm
);
618 ** Generate code that will evaluate all == and IN constraints for an
621 ** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c).
622 ** Suppose the WHERE clause is this: a==5 AND b IN (1,2,3) AND c>5 AND c<10
623 ** The index has as many as three equality constraints, but in this
624 ** example, the third "c" value is an inequality. So only two
625 ** constraints are coded. This routine will generate code to evaluate
626 ** a==5 and b IN (1,2,3). The current values for a and b will be stored
627 ** in consecutive registers and the index of the first register is returned.
629 ** In the example above nEq==2. But this subroutine works for any value
630 ** of nEq including 0. If nEq==0, this routine is nearly a no-op.
631 ** The only thing it does is allocate the pLevel->iMem memory cell and
632 ** compute the affinity string.
634 ** The nExtraReg parameter is 0 or 1. It is 0 if all WHERE clause constraints
635 ** are == or IN and are covered by the nEq. nExtraReg is 1 if there is
636 ** an inequality constraint (such as the "c>=5 AND c<10" in the example) that
637 ** occurs after the nEq quality constraints.
639 ** This routine allocates a range of nEq+nExtraReg memory cells and returns
640 ** the index of the first memory cell in that range. The code that
641 ** calls this routine will use that memory range to store keys for
642 ** start and termination conditions of the loop.
643 ** key value of the loop. If one or more IN operators appear, then
644 ** this routine allocates an additional nEq memory cells for internal
647 ** Before returning, *pzAff is set to point to a buffer containing a
648 ** copy of the column affinity string of the index allocated using
649 ** sqlite3DbMalloc(). Except, entries in the copy of the string associated
650 ** with equality constraints that use BLOB or NONE affinity are set to
651 ** SQLITE_AFF_BLOB. This is to deal with SQL such as the following:
653 ** CREATE TABLE t1(a TEXT PRIMARY KEY, b);
654 ** SELECT ... FROM t1 AS t2, t1 WHERE t1.a = t2.b;
656 ** In the example above, the index on t1(a) has TEXT affinity. But since
657 ** the right hand side of the equality constraint (t2.b) has BLOB/NONE affinity,
658 ** no conversion should be attempted before using a t2.b value as part of
659 ** a key to search the index. Hence the first byte in the returned affinity
660 ** string in this example would be set to SQLITE_AFF_BLOB.
662 static int codeAllEqualityTerms(
663 Parse
*pParse
, /* Parsing context */
664 WhereLevel
*pLevel
, /* Which nested loop of the FROM we are coding */
665 int bRev
, /* Reverse the order of IN operators */
666 int nExtraReg
, /* Number of extra registers to allocate */
667 char **pzAff
/* OUT: Set to point to affinity string */
669 u16 nEq
; /* The number of == or IN constraints to code */
670 u16 nSkip
; /* Number of left-most columns to skip */
671 Vdbe
*v
= pParse
->pVdbe
; /* The vm under construction */
672 Index
*pIdx
; /* The index being used for this loop */
673 WhereTerm
*pTerm
; /* A single constraint term */
674 WhereLoop
*pLoop
; /* The WhereLoop object */
675 int j
; /* Loop counter */
676 int regBase
; /* Base register */
677 int nReg
; /* Number of registers to allocate */
678 char *zAff
; /* Affinity string to return */
680 /* This module is only called on query plans that use an index. */
681 pLoop
= pLevel
->pWLoop
;
682 assert( (pLoop
->wsFlags
& WHERE_VIRTUALTABLE
)==0 );
683 nEq
= pLoop
->u
.btree
.nEq
;
684 nSkip
= pLoop
->nSkip
;
685 pIdx
= pLoop
->u
.btree
.pIndex
;
688 /* Figure out how many memory cells we will need then allocate them.
690 regBase
= pParse
->nMem
+ 1;
691 nReg
= pLoop
->u
.btree
.nEq
+ nExtraReg
;
692 pParse
->nMem
+= nReg
;
694 zAff
= sqlite3DbStrDup(pParse
->db
,sqlite3IndexAffinityStr(pParse
->db
,pIdx
));
695 assert( zAff
!=0 || pParse
->db
->mallocFailed
);
698 int iIdxCur
= pLevel
->iIdxCur
;
699 sqlite3VdbeAddOp1(v
, (bRev
?OP_Last
:OP_Rewind
), iIdxCur
);
700 VdbeCoverageIf(v
, bRev
==0);
701 VdbeCoverageIf(v
, bRev
!=0);
702 VdbeComment((v
, "begin skip-scan on %s", pIdx
->zName
));
703 j
= sqlite3VdbeAddOp0(v
, OP_Goto
);
704 pLevel
->addrSkip
= sqlite3VdbeAddOp4Int(v
, (bRev
?OP_SeekLT
:OP_SeekGT
),
705 iIdxCur
, 0, regBase
, nSkip
);
706 VdbeCoverageIf(v
, bRev
==0);
707 VdbeCoverageIf(v
, bRev
!=0);
708 sqlite3VdbeJumpHere(v
, j
);
709 for(j
=0; j
<nSkip
; j
++){
710 sqlite3VdbeAddOp3(v
, OP_Column
, iIdxCur
, j
, regBase
+j
);
711 testcase( pIdx
->aiColumn
[j
]==XN_EXPR
);
712 VdbeComment((v
, "%s", explainIndexColumnName(pIdx
, j
)));
716 /* Evaluate the equality constraints
718 assert( zAff
==0 || (int)strlen(zAff
)>=nEq
);
719 for(j
=nSkip
; j
<nEq
; j
++){
721 pTerm
= pLoop
->aLTerm
[j
];
723 /* The following testcase is true for indices with redundant columns.
724 ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */
725 testcase( (pTerm
->wtFlags
& TERM_CODED
)!=0 );
726 testcase( pTerm
->wtFlags
& TERM_VIRTUAL
);
727 r1
= codeEqualityTerm(pParse
, pTerm
, pLevel
, j
, bRev
, regBase
+j
);
730 sqlite3ReleaseTempReg(pParse
, regBase
);
733 sqlite3VdbeAddOp2(v
, OP_SCopy
, r1
, regBase
+j
);
736 if( pTerm
->eOperator
& WO_IN
){
737 if( pTerm
->pExpr
->flags
& EP_xIsSelect
){
738 /* No affinity ever needs to be (or should be) applied to a value
739 ** from the RHS of an "? IN (SELECT ...)" expression. The
740 ** sqlite3FindInIndex() routine has already ensured that the
741 ** affinity of the comparison has been applied to the value. */
742 if( zAff
) zAff
[j
] = SQLITE_AFF_BLOB
;
744 }else if( (pTerm
->eOperator
& WO_ISNULL
)==0 ){
745 Expr
*pRight
= pTerm
->pExpr
->pRight
;
746 if( (pTerm
->wtFlags
& TERM_IS
)==0 && sqlite3ExprCanBeNull(pRight
) ){
747 sqlite3VdbeAddOp2(v
, OP_IsNull
, regBase
+j
, pLevel
->addrBrk
);
751 if( sqlite3CompareAffinity(pRight
, zAff
[j
])==SQLITE_AFF_BLOB
){
752 zAff
[j
] = SQLITE_AFF_BLOB
;
754 if( sqlite3ExprNeedsNoAffinityChange(pRight
, zAff
[j
]) ){
755 zAff
[j
] = SQLITE_AFF_BLOB
;
764 #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
766 ** If the most recently coded instruction is a constant range constraint
767 ** (a string literal) that originated from the LIKE optimization, then
768 ** set P3 and P5 on the OP_String opcode so that the string will be cast
769 ** to a BLOB at appropriate times.
771 ** The LIKE optimization trys to evaluate "x LIKE 'abc%'" as a range
772 ** expression: "x>='ABC' AND x<'abd'". But this requires that the range
773 ** scan loop run twice, once for strings and a second time for BLOBs.
774 ** The OP_String opcodes on the second pass convert the upper and lower
775 ** bound string constants to blobs. This routine makes the necessary changes
776 ** to the OP_String opcodes for that to happen.
778 ** Except, of course, if SQLITE_LIKE_DOESNT_MATCH_BLOBS is defined, then
779 ** only the one pass through the string space is required, so this routine
782 static void whereLikeOptimizationStringFixup(
783 Vdbe
*v
, /* prepared statement under construction */
784 WhereLevel
*pLevel
, /* The loop that contains the LIKE operator */
785 WhereTerm
*pTerm
/* The upper or lower bound just coded */
787 if( pTerm
->wtFlags
& TERM_LIKEOPT
){
789 assert( pLevel
->iLikeRepCntr
>0 );
790 pOp
= sqlite3VdbeGetOp(v
, -1);
792 assert( pOp
->opcode
==OP_String8
793 || pTerm
->pWC
->pWInfo
->pParse
->db
->mallocFailed
);
794 pOp
->p3
= (int)(pLevel
->iLikeRepCntr
>>1); /* Register holding counter */
795 pOp
->p5
= (u8
)(pLevel
->iLikeRepCntr
&1); /* ASC or DESC */
799 # define whereLikeOptimizationStringFixup(A,B,C)
802 #ifdef SQLITE_ENABLE_CURSOR_HINTS
804 ** Information is passed from codeCursorHint() down to individual nodes of
805 ** the expression tree (by sqlite3WalkExpr()) using an instance of this
809 int iTabCur
; /* Cursor for the main table */
810 int iIdxCur
; /* Cursor for the index, if pIdx!=0. Unused otherwise */
811 Index
*pIdx
; /* The index used to access the table */
815 ** This function is called for every node of an expression that is a candidate
816 ** for a cursor hint on an index cursor. For TK_COLUMN nodes that reference
817 ** the table CCurHint.iTabCur, verify that the same column can be
818 ** accessed through the index. If it cannot, then set pWalker->eCode to 1.
820 static int codeCursorHintCheckExpr(Walker
*pWalker
, Expr
*pExpr
){
821 struct CCurHint
*pHint
= pWalker
->u
.pCCurHint
;
822 assert( pHint
->pIdx
!=0 );
823 if( pExpr
->op
==TK_COLUMN
824 && pExpr
->iTable
==pHint
->iTabCur
825 && sqlite3ColumnOfIndex(pHint
->pIdx
, pExpr
->iColumn
)<0
833 ** Test whether or not expression pExpr, which was part of a WHERE clause,
834 ** should be included in the cursor-hint for a table that is on the rhs
835 ** of a LEFT JOIN. Set Walker.eCode to non-zero before returning if the
836 ** expression is not suitable.
838 ** An expression is unsuitable if it might evaluate to non NULL even if
839 ** a TK_COLUMN node that does affect the value of the expression is set
840 ** to NULL. For example:
845 ** CASE WHEN col THEN 0 ELSE 1 END
847 static int codeCursorHintIsOrFunction(Walker
*pWalker
, Expr
*pExpr
){
849 || pExpr
->op
==TK_ISNULL
|| pExpr
->op
==TK_ISNOT
850 || pExpr
->op
==TK_NOTNULL
|| pExpr
->op
==TK_CASE
853 }else if( pExpr
->op
==TK_FUNCTION
){
856 if( 0==sqlite3IsLikeFunction(pWalker
->pParse
->db
, pExpr
, &d1
, d2
) ){
866 ** This function is called on every node of an expression tree used as an
867 ** argument to the OP_CursorHint instruction. If the node is a TK_COLUMN
868 ** that accesses any table other than the one identified by
869 ** CCurHint.iTabCur, then do the following:
871 ** 1) allocate a register and code an OP_Column instruction to read
872 ** the specified column into the new register, and
874 ** 2) transform the expression node to a TK_REGISTER node that reads
875 ** from the newly populated register.
877 ** Also, if the node is a TK_COLUMN that does access the table idenified
878 ** by pCCurHint.iTabCur, and an index is being used (which we will
879 ** know because CCurHint.pIdx!=0) then transform the TK_COLUMN into
880 ** an access of the index rather than the original table.
882 static int codeCursorHintFixExpr(Walker
*pWalker
, Expr
*pExpr
){
883 int rc
= WRC_Continue
;
884 struct CCurHint
*pHint
= pWalker
->u
.pCCurHint
;
885 if( pExpr
->op
==TK_COLUMN
){
886 if( pExpr
->iTable
!=pHint
->iTabCur
){
887 int reg
= ++pWalker
->pParse
->nMem
; /* Register for column value */
888 sqlite3ExprCode(pWalker
->pParse
, pExpr
, reg
);
889 pExpr
->op
= TK_REGISTER
;
891 }else if( pHint
->pIdx
!=0 ){
892 pExpr
->iTable
= pHint
->iIdxCur
;
893 pExpr
->iColumn
= sqlite3ColumnOfIndex(pHint
->pIdx
, pExpr
->iColumn
);
894 assert( pExpr
->iColumn
>=0 );
896 }else if( pExpr
->op
==TK_AGG_FUNCTION
){
897 /* An aggregate function in the WHERE clause of a query means this must
898 ** be a correlated sub-query, and expression pExpr is an aggregate from
899 ** the parent context. Do not walk the function arguments in this case.
901 ** todo: It should be possible to replace this node with a TK_REGISTER
902 ** expression, as the result of the expression must be stored in a
903 ** register at this point. The same holds for TK_AGG_COLUMN nodes. */
910 ** Insert an OP_CursorHint instruction if it is appropriate to do so.
912 static void codeCursorHint(
913 struct SrcList_item
*pTabItem
, /* FROM clause item */
914 WhereInfo
*pWInfo
, /* The where clause */
915 WhereLevel
*pLevel
, /* Which loop to provide hints for */
916 WhereTerm
*pEndRange
/* Hint this end-of-scan boundary term if not NULL */
918 Parse
*pParse
= pWInfo
->pParse
;
919 sqlite3
*db
= pParse
->db
;
920 Vdbe
*v
= pParse
->pVdbe
;
922 WhereLoop
*pLoop
= pLevel
->pWLoop
;
927 struct CCurHint sHint
;
930 if( OptimizationDisabled(db
, SQLITE_CursorHints
) ) return;
931 iCur
= pLevel
->iTabCur
;
932 assert( iCur
==pWInfo
->pTabList
->a
[pLevel
->iFrom
].iCursor
);
933 sHint
.iTabCur
= iCur
;
934 sHint
.iIdxCur
= pLevel
->iIdxCur
;
935 sHint
.pIdx
= pLoop
->u
.btree
.pIndex
;
936 memset(&sWalker
, 0, sizeof(sWalker
));
937 sWalker
.pParse
= pParse
;
938 sWalker
.u
.pCCurHint
= &sHint
;
940 for(i
=0; i
<pWC
->nTerm
; i
++){
942 if( pTerm
->wtFlags
& (TERM_VIRTUAL
|TERM_CODED
) ) continue;
943 if( pTerm
->prereqAll
& pLevel
->notReady
) continue;
945 /* Any terms specified as part of the ON(...) clause for any LEFT
946 ** JOIN for which the current table is not the rhs are omitted
947 ** from the cursor-hint.
949 ** If this table is the rhs of a LEFT JOIN, "IS" or "IS NULL" terms
950 ** that were specified as part of the WHERE clause must be excluded.
951 ** This is to address the following:
953 ** SELECT ... t1 LEFT JOIN t2 ON (t1.a=t2.b) WHERE t2.c IS NULL;
955 ** Say there is a single row in t2 that matches (t1.a=t2.b), but its
956 ** t2.c values is not NULL. If the (t2.c IS NULL) constraint is
957 ** pushed down to the cursor, this row is filtered out, causing
958 ** SQLite to synthesize a row of NULL values. Which does match the
959 ** WHERE clause, and so the query returns a row. Which is incorrect.
961 ** For the same reason, WHERE terms such as:
963 ** WHERE 1 = (t2.c IS NULL)
965 ** are also excluded. See codeCursorHintIsOrFunction() for details.
967 if( pTabItem
->fg
.jointype
& JT_LEFT
){
968 Expr
*pExpr
= pTerm
->pExpr
;
969 if( !ExprHasProperty(pExpr
, EP_FromJoin
)
970 || pExpr
->iRightJoinTable
!=pTabItem
->iCursor
973 sWalker
.xExprCallback
= codeCursorHintIsOrFunction
;
974 sqlite3WalkExpr(&sWalker
, pTerm
->pExpr
);
975 if( sWalker
.eCode
) continue;
978 if( ExprHasProperty(pTerm
->pExpr
, EP_FromJoin
) ) continue;
981 /* All terms in pWLoop->aLTerm[] except pEndRange are used to initialize
982 ** the cursor. These terms are not needed as hints for a pure range
983 ** scan (that has no == terms) so omit them. */
984 if( pLoop
->u
.btree
.nEq
==0 && pTerm
!=pEndRange
){
985 for(j
=0; j
<pLoop
->nLTerm
&& pLoop
->aLTerm
[j
]!=pTerm
; j
++){}
986 if( j
<pLoop
->nLTerm
) continue;
989 /* No subqueries or non-deterministic functions allowed */
990 if( sqlite3ExprContainsSubquery(pTerm
->pExpr
) ) continue;
992 /* For an index scan, make sure referenced columns are actually in
996 sWalker
.xExprCallback
= codeCursorHintCheckExpr
;
997 sqlite3WalkExpr(&sWalker
, pTerm
->pExpr
);
998 if( sWalker
.eCode
) continue;
1001 /* If we survive all prior tests, that means this term is worth hinting */
1002 pExpr
= sqlite3ExprAnd(db
, pExpr
, sqlite3ExprDup(db
, pTerm
->pExpr
, 0));
1005 sWalker
.xExprCallback
= codeCursorHintFixExpr
;
1006 sqlite3WalkExpr(&sWalker
, pExpr
);
1007 sqlite3VdbeAddOp4(v
, OP_CursorHint
,
1008 (sHint
.pIdx
? sHint
.iIdxCur
: sHint
.iTabCur
), 0, 0,
1009 (const char*)pExpr
, P4_EXPR
);
1013 # define codeCursorHint(A,B,C,D) /* No-op */
1014 #endif /* SQLITE_ENABLE_CURSOR_HINTS */
1017 ** Cursor iCur is open on an intkey b-tree (a table). Register iRowid contains
1018 ** a rowid value just read from cursor iIdxCur, open on index pIdx. This
1019 ** function generates code to do a deferred seek of cursor iCur to the
1020 ** rowid stored in register iRowid.
1022 ** Normally, this is just:
1024 ** OP_DeferredSeek $iCur $iRowid
1026 ** However, if the scan currently being coded is a branch of an OR-loop and
1027 ** the statement currently being coded is a SELECT, then P3 of OP_DeferredSeek
1028 ** is set to iIdxCur and P4 is set to point to an array of integers
1029 ** containing one entry for each column of the table cursor iCur is open
1030 ** on. For each table column, if the column is the i'th column of the
1031 ** index, then the corresponding array entry is set to (i+1). If the column
1032 ** does not appear in the index at all, the array entry is set to 0.
1034 static void codeDeferredSeek(
1035 WhereInfo
*pWInfo
, /* Where clause context */
1036 Index
*pIdx
, /* Index scan is using */
1037 int iCur
, /* Cursor for IPK b-tree */
1038 int iIdxCur
/* Index cursor */
1040 Parse
*pParse
= pWInfo
->pParse
; /* Parse context */
1041 Vdbe
*v
= pParse
->pVdbe
; /* Vdbe to generate code within */
1043 assert( iIdxCur
>0 );
1044 assert( pIdx
->aiColumn
[pIdx
->nColumn
-1]==-1 );
1046 sqlite3VdbeAddOp3(v
, OP_DeferredSeek
, iIdxCur
, 0, iCur
);
1047 if( (pWInfo
->wctrlFlags
& WHERE_OR_SUBCLAUSE
)
1048 && DbMaskAllZero(sqlite3ParseToplevel(pParse
)->writeMask
)
1051 Table
*pTab
= pIdx
->pTable
;
1052 int *ai
= (int*)sqlite3DbMallocZero(pParse
->db
, sizeof(int)*(pTab
->nCol
+1));
1055 for(i
=0; i
<pIdx
->nColumn
-1; i
++){
1056 assert( pIdx
->aiColumn
[i
]<pTab
->nCol
);
1057 if( pIdx
->aiColumn
[i
]>=0 ) ai
[pIdx
->aiColumn
[i
]+1] = i
+1;
1059 sqlite3VdbeChangeP4(v
, -1, (char*)ai
, P4_INTARRAY
);
1065 ** If the expression passed as the second argument is a vector, generate
1066 ** code to write the first nReg elements of the vector into an array
1067 ** of registers starting with iReg.
1069 ** If the expression is not a vector, then nReg must be passed 1. In
1070 ** this case, generate code to evaluate the expression and leave the
1071 ** result in register iReg.
1073 static void codeExprOrVector(Parse
*pParse
, Expr
*p
, int iReg
, int nReg
){
1075 if( p
&& sqlite3ExprIsVector(p
) ){
1076 #ifndef SQLITE_OMIT_SUBQUERY
1077 if( (p
->flags
& EP_xIsSelect
) ){
1078 Vdbe
*v
= pParse
->pVdbe
;
1079 int iSelect
= sqlite3CodeSubselect(pParse
, p
, 0, 0);
1080 sqlite3VdbeAddOp3(v
, OP_Copy
, iSelect
, iReg
, nReg
-1);
1085 ExprList
*pList
= p
->x
.pList
;
1086 assert( nReg
<=pList
->nExpr
);
1087 for(i
=0; i
<nReg
; i
++){
1088 sqlite3ExprCode(pParse
, pList
->a
[i
].pExpr
, iReg
+i
);
1093 sqlite3ExprCode(pParse
, p
, iReg
);
1097 /* An instance of the IdxExprTrans object carries information about a
1098 ** mapping from an expression on table columns into a column in an index
1099 ** down through the Walker.
1101 typedef struct IdxExprTrans
{
1102 Expr
*pIdxExpr
; /* The index expression */
1103 int iTabCur
; /* The cursor of the corresponding table */
1104 int iIdxCur
; /* The cursor for the index */
1105 int iIdxCol
; /* The column for the index */
1108 /* The walker node callback used to transform matching expressions into
1109 ** a reference to an index column for an index on an expression.
1111 ** If pExpr matches, then transform it into a reference to the index column
1112 ** that contains the value of pExpr.
1114 static int whereIndexExprTransNode(Walker
*p
, Expr
*pExpr
){
1115 IdxExprTrans
*pX
= p
->u
.pIdxTrans
;
1116 if( sqlite3ExprCompare(0, pExpr
, pX
->pIdxExpr
, pX
->iTabCur
)==0 ){
1117 pExpr
->op
= TK_COLUMN
;
1118 pExpr
->iTable
= pX
->iIdxCur
;
1119 pExpr
->iColumn
= pX
->iIdxCol
;
1123 return WRC_Continue
;
1128 ** For an indexes on expression X, locate every instance of expression X
1129 ** in pExpr and change that subexpression into a reference to the appropriate
1130 ** column of the index.
1132 static void whereIndexExprTrans(
1133 Index
*pIdx
, /* The Index */
1134 int iTabCur
, /* Cursor of the table that is being indexed */
1135 int iIdxCur
, /* Cursor of the index itself */
1136 WhereInfo
*pWInfo
/* Transform expressions in this WHERE clause */
1138 int iIdxCol
; /* Column number of the index */
1139 ExprList
*aColExpr
; /* Expressions that are indexed */
1142 aColExpr
= pIdx
->aColExpr
;
1143 if( aColExpr
==0 ) return; /* Not an index on expressions */
1144 memset(&w
, 0, sizeof(w
));
1145 w
.xExprCallback
= whereIndexExprTransNode
;
1147 x
.iTabCur
= iTabCur
;
1148 x
.iIdxCur
= iIdxCur
;
1149 for(iIdxCol
=0; iIdxCol
<aColExpr
->nExpr
; iIdxCol
++){
1150 if( pIdx
->aiColumn
[iIdxCol
]!=XN_EXPR
) continue;
1151 assert( aColExpr
->a
[iIdxCol
].pExpr
!=0 );
1152 x
.iIdxCol
= iIdxCol
;
1153 x
.pIdxExpr
= aColExpr
->a
[iIdxCol
].pExpr
;
1154 sqlite3WalkExpr(&w
, pWInfo
->pWhere
);
1155 sqlite3WalkExprList(&w
, pWInfo
->pOrderBy
);
1156 sqlite3WalkExprList(&w
, pWInfo
->pResultSet
);
1161 ** Generate code for the start of the iLevel-th loop in the WHERE clause
1162 ** implementation described by pWInfo.
1164 Bitmask
sqlite3WhereCodeOneLoopStart(
1165 WhereInfo
*pWInfo
, /* Complete information about the WHERE clause */
1166 int iLevel
, /* Which level of pWInfo->a[] should be coded */
1167 Bitmask notReady
/* Which tables are currently available */
1169 int j
, k
; /* Loop counters */
1170 int iCur
; /* The VDBE cursor for the table */
1171 int addrNxt
; /* Where to jump to continue with the next IN case */
1172 int omitTable
; /* True if we use the index only */
1173 int bRev
; /* True if we need to scan in reverse order */
1174 WhereLevel
*pLevel
; /* The where level to be coded */
1175 WhereLoop
*pLoop
; /* The WhereLoop object being coded */
1176 WhereClause
*pWC
; /* Decomposition of the entire WHERE clause */
1177 WhereTerm
*pTerm
; /* A WHERE clause term */
1178 Parse
*pParse
; /* Parsing context */
1179 sqlite3
*db
; /* Database connection */
1180 Vdbe
*v
; /* The prepared stmt under constructions */
1181 struct SrcList_item
*pTabItem
; /* FROM clause term being coded */
1182 int addrBrk
; /* Jump here to break out of the loop */
1183 int addrHalt
; /* addrBrk for the outermost loop */
1184 int addrCont
; /* Jump here to continue with next cycle */
1185 int iRowidReg
= 0; /* Rowid is stored in this register, if not zero */
1186 int iReleaseReg
= 0; /* Temp register to free before returning */
1187 Index
*pIdx
= 0; /* Index used by loop (if any) */
1188 int iLoop
; /* Iteration of constraint generator loop */
1190 pParse
= pWInfo
->pParse
;
1194 pLevel
= &pWInfo
->a
[iLevel
];
1195 pLoop
= pLevel
->pWLoop
;
1196 pTabItem
= &pWInfo
->pTabList
->a
[pLevel
->iFrom
];
1197 iCur
= pTabItem
->iCursor
;
1198 pLevel
->notReady
= notReady
& ~sqlite3WhereGetMask(&pWInfo
->sMaskSet
, iCur
);
1199 bRev
= (pWInfo
->revMask
>>iLevel
)&1;
1200 omitTable
= (pLoop
->wsFlags
& WHERE_IDX_ONLY
)!=0
1201 && (pWInfo
->wctrlFlags
& WHERE_OR_SUBCLAUSE
)==0;
1202 VdbeModuleComment((v
, "Begin WHERE-loop%d: %s",iLevel
,pTabItem
->pTab
->zName
));
1204 /* Create labels for the "break" and "continue" instructions
1205 ** for the current loop. Jump to addrBrk to break out of a loop.
1206 ** Jump to cont to go immediately to the next iteration of the
1209 ** When there is an IN operator, we also have a "addrNxt" label that
1210 ** means to continue with the next IN value combination. When
1211 ** there are no IN operators in the constraints, the "addrNxt" label
1212 ** is the same as "addrBrk".
1214 addrBrk
= pLevel
->addrBrk
= pLevel
->addrNxt
= sqlite3VdbeMakeLabel(v
);
1215 addrCont
= pLevel
->addrCont
= sqlite3VdbeMakeLabel(v
);
1217 /* If this is the right table of a LEFT OUTER JOIN, allocate and
1218 ** initialize a memory cell that records if this table matches any
1219 ** row of the left table of the join.
1221 assert( (pWInfo
->wctrlFlags
& WHERE_OR_SUBCLAUSE
)
1222 || pLevel
->iFrom
>0 || (pTabItem
[0].fg
.jointype
& JT_LEFT
)==0
1224 if( pLevel
->iFrom
>0 && (pTabItem
[0].fg
.jointype
& JT_LEFT
)!=0 ){
1225 pLevel
->iLeftJoin
= ++pParse
->nMem
;
1226 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, pLevel
->iLeftJoin
);
1227 VdbeComment((v
, "init LEFT JOIN no-match flag"));
1230 /* Compute a safe address to jump to if we discover that the table for
1231 ** this loop is empty and can never contribute content. */
1232 for(j
=iLevel
; j
>0 && pWInfo
->a
[j
].iLeftJoin
==0; j
--){}
1233 addrHalt
= pWInfo
->a
[j
].addrBrk
;
1235 /* Special case of a FROM clause subquery implemented as a co-routine */
1236 if( pTabItem
->fg
.viaCoroutine
){
1237 int regYield
= pTabItem
->regReturn
;
1238 sqlite3VdbeAddOp3(v
, OP_InitCoroutine
, regYield
, 0, pTabItem
->addrFillSub
);
1239 pLevel
->p2
= sqlite3VdbeAddOp2(v
, OP_Yield
, regYield
, addrBrk
);
1241 VdbeComment((v
, "next row of %s", pTabItem
->pTab
->zName
));
1242 pLevel
->op
= OP_Goto
;
1245 #ifndef SQLITE_OMIT_VIRTUALTABLE
1246 if( (pLoop
->wsFlags
& WHERE_VIRTUALTABLE
)!=0 ){
1247 /* Case 1: The table is a virtual-table. Use the VFilter and VNext
1248 ** to access the data.
1250 int iReg
; /* P3 Value for OP_VFilter */
1252 int nConstraint
= pLoop
->nLTerm
;
1253 int iIn
; /* Counter for IN constraints */
1255 iReg
= sqlite3GetTempRange(pParse
, nConstraint
+2);
1256 addrNotFound
= pLevel
->addrBrk
;
1257 for(j
=0; j
<nConstraint
; j
++){
1258 int iTarget
= iReg
+j
+2;
1259 pTerm
= pLoop
->aLTerm
[j
];
1260 if( NEVER(pTerm
==0) ) continue;
1261 if( pTerm
->eOperator
& WO_IN
){
1262 codeEqualityTerm(pParse
, pTerm
, pLevel
, j
, bRev
, iTarget
);
1263 addrNotFound
= pLevel
->addrNxt
;
1265 Expr
*pRight
= pTerm
->pExpr
->pRight
;
1266 codeExprOrVector(pParse
, pRight
, iTarget
, 1);
1269 sqlite3VdbeAddOp2(v
, OP_Integer
, pLoop
->u
.vtab
.idxNum
, iReg
);
1270 sqlite3VdbeAddOp2(v
, OP_Integer
, nConstraint
, iReg
+1);
1271 sqlite3VdbeAddOp4(v
, OP_VFilter
, iCur
, addrNotFound
, iReg
,
1272 pLoop
->u
.vtab
.idxStr
,
1273 pLoop
->u
.vtab
.needFree
? P4_DYNAMIC
: P4_STATIC
);
1275 pLoop
->u
.vtab
.needFree
= 0;
1277 pLevel
->op
= pWInfo
->eOnePass
? OP_Noop
: OP_VNext
;
1278 pLevel
->p2
= sqlite3VdbeCurrentAddr(v
);
1279 iIn
= pLevel
->u
.in
.nIn
;
1280 for(j
=nConstraint
-1; j
>=0; j
--){
1281 pTerm
= pLoop
->aLTerm
[j
];
1282 if( j
<16 && (pLoop
->u
.vtab
.omitMask
>>j
)&1 ){
1283 disableTerm(pLevel
, pTerm
);
1284 }else if( (pTerm
->eOperator
& WO_IN
)!=0 ){
1285 Expr
*pCompare
; /* The comparison operator */
1286 Expr
*pRight
; /* RHS of the comparison */
1287 VdbeOp
*pOp
; /* Opcode to access the value of the IN constraint */
1289 /* Reload the constraint value into reg[iReg+j+2]. The same value
1290 ** was loaded into the same register prior to the OP_VFilter, but
1291 ** the xFilter implementation might have changed the datatype or
1292 ** encoding of the value in the register, so it *must* be reloaded. */
1293 assert( pLevel
->u
.in
.aInLoop
!=0 || db
->mallocFailed
);
1294 if( !db
->mallocFailed
){
1296 pOp
= sqlite3VdbeGetOp(v
, pLevel
->u
.in
.aInLoop
[--iIn
].addrInTop
);
1297 assert( pOp
->opcode
==OP_Column
|| pOp
->opcode
==OP_Rowid
);
1298 assert( pOp
->opcode
!=OP_Column
|| pOp
->p3
==iReg
+j
+2 );
1299 assert( pOp
->opcode
!=OP_Rowid
|| pOp
->p2
==iReg
+j
+2 );
1300 testcase( pOp
->opcode
==OP_Rowid
);
1301 sqlite3VdbeAddOp3(v
, pOp
->opcode
, pOp
->p1
, pOp
->p2
, pOp
->p3
);
1304 /* Generate code that will continue to the next row if
1305 ** the IN constraint is not satisfied */
1306 pCompare
= sqlite3PExpr(pParse
, TK_EQ
, 0, 0);
1307 assert( pCompare
!=0 || db
->mallocFailed
);
1309 pCompare
->pLeft
= pTerm
->pExpr
->pLeft
;
1310 pCompare
->pRight
= pRight
= sqlite3Expr(db
, TK_REGISTER
, 0);
1312 pRight
->iTable
= iReg
+j
+2;
1313 sqlite3ExprIfFalse(pParse
, pCompare
, pLevel
->addrCont
, 0);
1315 pCompare
->pLeft
= 0;
1316 sqlite3ExprDelete(db
, pCompare
);
1320 /* These registers need to be preserved in case there is an IN operator
1321 ** loop. So we could deallocate the registers here (and potentially
1322 ** reuse them later) if (pLoop->wsFlags & WHERE_IN_ABLE)==0. But it seems
1323 ** simpler and safer to simply not reuse the registers.
1325 ** sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2);
1328 #endif /* SQLITE_OMIT_VIRTUALTABLE */
1330 if( (pLoop
->wsFlags
& WHERE_IPK
)!=0
1331 && (pLoop
->wsFlags
& (WHERE_COLUMN_IN
|WHERE_COLUMN_EQ
))!=0
1333 /* Case 2: We can directly reference a single row using an
1334 ** equality comparison against the ROWID field. Or
1335 ** we reference multiple rows using a "rowid IN (...)"
1338 assert( pLoop
->u
.btree
.nEq
==1 );
1339 pTerm
= pLoop
->aLTerm
[0];
1341 assert( pTerm
->pExpr
!=0 );
1342 assert( omitTable
==0 );
1343 testcase( pTerm
->wtFlags
& TERM_VIRTUAL
);
1344 iReleaseReg
= ++pParse
->nMem
;
1345 iRowidReg
= codeEqualityTerm(pParse
, pTerm
, pLevel
, 0, bRev
, iReleaseReg
);
1346 if( iRowidReg
!=iReleaseReg
) sqlite3ReleaseTempReg(pParse
, iReleaseReg
);
1347 addrNxt
= pLevel
->addrNxt
;
1348 sqlite3VdbeAddOp3(v
, OP_SeekRowid
, iCur
, addrNxt
, iRowidReg
);
1350 pLevel
->op
= OP_Noop
;
1351 }else if( (pLoop
->wsFlags
& WHERE_IPK
)!=0
1352 && (pLoop
->wsFlags
& WHERE_COLUMN_RANGE
)!=0
1354 /* Case 3: We have an inequality comparison against the ROWID field.
1356 int testOp
= OP_Noop
;
1358 int memEndValue
= 0;
1359 WhereTerm
*pStart
, *pEnd
;
1361 assert( omitTable
==0 );
1364 if( pLoop
->wsFlags
& WHERE_BTM_LIMIT
) pStart
= pLoop
->aLTerm
[j
++];
1365 if( pLoop
->wsFlags
& WHERE_TOP_LIMIT
) pEnd
= pLoop
->aLTerm
[j
++];
1366 assert( pStart
!=0 || pEnd
!=0 );
1372 codeCursorHint(pTabItem
, pWInfo
, pLevel
, pEnd
);
1374 Expr
*pX
; /* The expression that defines the start bound */
1375 int r1
, rTemp
; /* Registers for holding the start boundary */
1376 int op
; /* Cursor seek operation */
1378 /* The following constant maps TK_xx codes into corresponding
1379 ** seek opcodes. It depends on a particular ordering of TK_xx
1381 const u8 aMoveOp
[] = {
1382 /* TK_GT */ OP_SeekGT
,
1383 /* TK_LE */ OP_SeekLE
,
1384 /* TK_LT */ OP_SeekLT
,
1385 /* TK_GE */ OP_SeekGE
1387 assert( TK_LE
==TK_GT
+1 ); /* Make sure the ordering.. */
1388 assert( TK_LT
==TK_GT
+2 ); /* ... of the TK_xx values... */
1389 assert( TK_GE
==TK_GT
+3 ); /* ... is correcct. */
1391 assert( (pStart
->wtFlags
& TERM_VNULL
)==0 );
1392 testcase( pStart
->wtFlags
& TERM_VIRTUAL
);
1395 testcase( pStart
->leftCursor
!=iCur
); /* transitive constraints */
1396 if( sqlite3ExprIsVector(pX
->pRight
) ){
1397 r1
= rTemp
= sqlite3GetTempReg(pParse
);
1398 codeExprOrVector(pParse
, pX
->pRight
, r1
, 1);
1399 testcase( pX
->op
==TK_GT
);
1400 testcase( pX
->op
==TK_GE
);
1401 testcase( pX
->op
==TK_LT
);
1402 testcase( pX
->op
==TK_LE
);
1403 op
= aMoveOp
[((pX
->op
- TK_GT
- 1) & 0x3) | 0x1];
1404 assert( pX
->op
!=TK_GT
|| op
==OP_SeekGE
);
1405 assert( pX
->op
!=TK_GE
|| op
==OP_SeekGE
);
1406 assert( pX
->op
!=TK_LT
|| op
==OP_SeekLE
);
1407 assert( pX
->op
!=TK_LE
|| op
==OP_SeekLE
);
1409 r1
= sqlite3ExprCodeTemp(pParse
, pX
->pRight
, &rTemp
);
1410 disableTerm(pLevel
, pStart
);
1411 op
= aMoveOp
[(pX
->op
- TK_GT
)];
1413 sqlite3VdbeAddOp3(v
, op
, iCur
, addrBrk
, r1
);
1414 VdbeComment((v
, "pk"));
1415 VdbeCoverageIf(v
, pX
->op
==TK_GT
);
1416 VdbeCoverageIf(v
, pX
->op
==TK_LE
);
1417 VdbeCoverageIf(v
, pX
->op
==TK_LT
);
1418 VdbeCoverageIf(v
, pX
->op
==TK_GE
);
1419 sqlite3ReleaseTempReg(pParse
, rTemp
);
1421 sqlite3VdbeAddOp2(v
, bRev
? OP_Last
: OP_Rewind
, iCur
, addrHalt
);
1422 VdbeCoverageIf(v
, bRev
==0);
1423 VdbeCoverageIf(v
, bRev
!=0);
1429 assert( (pEnd
->wtFlags
& TERM_VNULL
)==0 );
1430 testcase( pEnd
->leftCursor
!=iCur
); /* Transitive constraints */
1431 testcase( pEnd
->wtFlags
& TERM_VIRTUAL
);
1432 memEndValue
= ++pParse
->nMem
;
1433 codeExprOrVector(pParse
, pX
->pRight
, memEndValue
, 1);
1434 if( 0==sqlite3ExprIsVector(pX
->pRight
)
1435 && (pX
->op
==TK_LT
|| pX
->op
==TK_GT
)
1437 testOp
= bRev
? OP_Le
: OP_Ge
;
1439 testOp
= bRev
? OP_Lt
: OP_Gt
;
1441 if( 0==sqlite3ExprIsVector(pX
->pRight
) ){
1442 disableTerm(pLevel
, pEnd
);
1445 start
= sqlite3VdbeCurrentAddr(v
);
1446 pLevel
->op
= bRev
? OP_Prev
: OP_Next
;
1449 assert( pLevel
->p5
==0 );
1450 if( testOp
!=OP_Noop
){
1451 iRowidReg
= ++pParse
->nMem
;
1452 sqlite3VdbeAddOp2(v
, OP_Rowid
, iCur
, iRowidReg
);
1453 sqlite3VdbeAddOp3(v
, testOp
, memEndValue
, addrBrk
, iRowidReg
);
1454 VdbeCoverageIf(v
, testOp
==OP_Le
);
1455 VdbeCoverageIf(v
, testOp
==OP_Lt
);
1456 VdbeCoverageIf(v
, testOp
==OP_Ge
);
1457 VdbeCoverageIf(v
, testOp
==OP_Gt
);
1458 sqlite3VdbeChangeP5(v
, SQLITE_AFF_NUMERIC
| SQLITE_JUMPIFNULL
);
1460 }else if( pLoop
->wsFlags
& WHERE_INDEXED
){
1461 /* Case 4: A scan using an index.
1463 ** The WHERE clause may contain zero or more equality
1464 ** terms ("==" or "IN" operators) that refer to the N
1465 ** left-most columns of the index. It may also contain
1466 ** inequality constraints (>, <, >= or <=) on the indexed
1467 ** column that immediately follows the N equalities. Only
1468 ** the right-most column can be an inequality - the rest must
1469 ** use the "==" and "IN" operators. For example, if the
1470 ** index is on (x,y,z), then the following clauses are all
1476 ** x=5 AND y>5 AND y<10
1477 ** x=5 AND y=5 AND z<=10
1479 ** The z<10 term of the following cannot be used, only
1484 ** N may be zero if there are inequality constraints.
1485 ** If there are no inequality constraints, then N is at
1488 ** This case is also used when there are no WHERE clause
1489 ** constraints but an index is selected anyway, in order
1490 ** to force the output order to conform to an ORDER BY.
1492 static const u8 aStartOp
[] = {
1495 OP_Rewind
, /* 2: (!start_constraints && startEq && !bRev) */
1496 OP_Last
, /* 3: (!start_constraints && startEq && bRev) */
1497 OP_SeekGT
, /* 4: (start_constraints && !startEq && !bRev) */
1498 OP_SeekLT
, /* 5: (start_constraints && !startEq && bRev) */
1499 OP_SeekGE
, /* 6: (start_constraints && startEq && !bRev) */
1500 OP_SeekLE
/* 7: (start_constraints && startEq && bRev) */
1502 static const u8 aEndOp
[] = {
1503 OP_IdxGE
, /* 0: (end_constraints && !bRev && !endEq) */
1504 OP_IdxGT
, /* 1: (end_constraints && !bRev && endEq) */
1505 OP_IdxLE
, /* 2: (end_constraints && bRev && !endEq) */
1506 OP_IdxLT
, /* 3: (end_constraints && bRev && endEq) */
1508 u16 nEq
= pLoop
->u
.btree
.nEq
; /* Number of == or IN terms */
1509 u16 nBtm
= pLoop
->u
.btree
.nBtm
; /* Length of BTM vector */
1510 u16 nTop
= pLoop
->u
.btree
.nTop
; /* Length of TOP vector */
1511 int regBase
; /* Base register holding constraint values */
1512 WhereTerm
*pRangeStart
= 0; /* Inequality constraint at range start */
1513 WhereTerm
*pRangeEnd
= 0; /* Inequality constraint at range end */
1514 int startEq
; /* True if range start uses ==, >= or <= */
1515 int endEq
; /* True if range end uses ==, >= or <= */
1516 int start_constraints
; /* Start of range is constrained */
1517 int nConstraint
; /* Number of constraint terms */
1518 int iIdxCur
; /* The VDBE cursor for the index */
1519 int nExtraReg
= 0; /* Number of extra registers needed */
1520 int op
; /* Instruction opcode */
1521 char *zStartAff
; /* Affinity for start of range constraint */
1522 char *zEndAff
= 0; /* Affinity for end of range constraint */
1523 u8 bSeekPastNull
= 0; /* True to seek past initial nulls */
1524 u8 bStopAtNull
= 0; /* Add condition to terminate at NULLs */
1526 pIdx
= pLoop
->u
.btree
.pIndex
;
1527 iIdxCur
= pLevel
->iIdxCur
;
1528 assert( nEq
>=pLoop
->nSkip
);
1530 /* If this loop satisfies a sort order (pOrderBy) request that
1531 ** was passed to this function to implement a "SELECT min(x) ..."
1532 ** query, then the caller will only allow the loop to run for
1533 ** a single iteration. This means that the first row returned
1534 ** should not have a NULL value stored in 'x'. If column 'x' is
1535 ** the first one after the nEq equality constraints in the index,
1536 ** this requires some special handling.
1538 assert( pWInfo
->pOrderBy
==0
1539 || pWInfo
->pOrderBy
->nExpr
==1
1540 || (pWInfo
->wctrlFlags
&WHERE_ORDERBY_MIN
)==0 );
1541 if( (pWInfo
->wctrlFlags
&WHERE_ORDERBY_MIN
)!=0
1543 && (pIdx
->nKeyCol
>nEq
)
1545 assert( pLoop
->nSkip
==0 );
1550 /* Find any inequality constraint terms for the start and end
1554 if( pLoop
->wsFlags
& WHERE_BTM_LIMIT
){
1555 pRangeStart
= pLoop
->aLTerm
[j
++];
1556 nExtraReg
= MAX(nExtraReg
, pLoop
->u
.btree
.nBtm
);
1557 /* Like optimization range constraints always occur in pairs */
1558 assert( (pRangeStart
->wtFlags
& TERM_LIKEOPT
)==0 ||
1559 (pLoop
->wsFlags
& WHERE_TOP_LIMIT
)!=0 );
1561 if( pLoop
->wsFlags
& WHERE_TOP_LIMIT
){
1562 pRangeEnd
= pLoop
->aLTerm
[j
++];
1563 nExtraReg
= MAX(nExtraReg
, pLoop
->u
.btree
.nTop
);
1564 #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
1565 if( (pRangeEnd
->wtFlags
& TERM_LIKEOPT
)!=0 ){
1566 assert( pRangeStart
!=0 ); /* LIKE opt constraints */
1567 assert( pRangeStart
->wtFlags
& TERM_LIKEOPT
); /* occur in pairs */
1568 pLevel
->iLikeRepCntr
= (u32
)++pParse
->nMem
;
1569 sqlite3VdbeAddOp2(v
, OP_Integer
, 1, (int)pLevel
->iLikeRepCntr
);
1570 VdbeComment((v
, "LIKE loop counter"));
1571 pLevel
->addrLikeRep
= sqlite3VdbeCurrentAddr(v
);
1572 /* iLikeRepCntr actually stores 2x the counter register number. The
1573 ** bottom bit indicates whether the search order is ASC or DESC. */
1575 testcase( pIdx
->aSortOrder
[nEq
]==SQLITE_SO_DESC
);
1576 assert( (bRev
& ~1)==0 );
1577 pLevel
->iLikeRepCntr
<<=1;
1578 pLevel
->iLikeRepCntr
|= bRev
^ (pIdx
->aSortOrder
[nEq
]==SQLITE_SO_DESC
);
1581 if( pRangeStart
==0 ){
1582 j
= pIdx
->aiColumn
[nEq
];
1583 if( (j
>=0 && pIdx
->pTable
->aCol
[j
].notNull
==0) || j
==XN_EXPR
){
1588 assert( pRangeEnd
==0 || (pRangeEnd
->wtFlags
& TERM_VNULL
)==0 );
1590 /* If we are doing a reverse order scan on an ascending index, or
1591 ** a forward order scan on a descending index, interchange the
1592 ** start and end terms (pRangeStart and pRangeEnd).
1594 if( (nEq
<pIdx
->nKeyCol
&& bRev
==(pIdx
->aSortOrder
[nEq
]==SQLITE_SO_ASC
))
1595 || (bRev
&& pIdx
->nKeyCol
==nEq
)
1597 SWAP(WhereTerm
*, pRangeEnd
, pRangeStart
);
1598 SWAP(u8
, bSeekPastNull
, bStopAtNull
);
1599 SWAP(u8
, nBtm
, nTop
);
1602 /* Generate code to evaluate all constraint terms using == or IN
1603 ** and store the values of those terms in an array of registers
1604 ** starting at regBase.
1606 codeCursorHint(pTabItem
, pWInfo
, pLevel
, pRangeEnd
);
1607 regBase
= codeAllEqualityTerms(pParse
,pLevel
,bRev
,nExtraReg
,&zStartAff
);
1608 assert( zStartAff
==0 || sqlite3Strlen30(zStartAff
)>=nEq
);
1609 if( zStartAff
&& nTop
){
1610 zEndAff
= sqlite3DbStrDup(db
, &zStartAff
[nEq
]);
1612 addrNxt
= pLevel
->addrNxt
;
1614 testcase( pRangeStart
&& (pRangeStart
->eOperator
& WO_LE
)!=0 );
1615 testcase( pRangeStart
&& (pRangeStart
->eOperator
& WO_GE
)!=0 );
1616 testcase( pRangeEnd
&& (pRangeEnd
->eOperator
& WO_LE
)!=0 );
1617 testcase( pRangeEnd
&& (pRangeEnd
->eOperator
& WO_GE
)!=0 );
1618 startEq
= !pRangeStart
|| pRangeStart
->eOperator
& (WO_LE
|WO_GE
);
1619 endEq
= !pRangeEnd
|| pRangeEnd
->eOperator
& (WO_LE
|WO_GE
);
1620 start_constraints
= pRangeStart
|| nEq
>0;
1622 /* Seek the index cursor to the start of the range. */
1625 Expr
*pRight
= pRangeStart
->pExpr
->pRight
;
1626 codeExprOrVector(pParse
, pRight
, regBase
+nEq
, nBtm
);
1627 whereLikeOptimizationStringFixup(v
, pLevel
, pRangeStart
);
1628 if( (pRangeStart
->wtFlags
& TERM_VNULL
)==0
1629 && sqlite3ExprCanBeNull(pRight
)
1631 sqlite3VdbeAddOp2(v
, OP_IsNull
, regBase
+nEq
, addrNxt
);
1635 updateRangeAffinityStr(pRight
, nBtm
, &zStartAff
[nEq
]);
1637 nConstraint
+= nBtm
;
1638 testcase( pRangeStart
->wtFlags
& TERM_VIRTUAL
);
1639 if( sqlite3ExprIsVector(pRight
)==0 ){
1640 disableTerm(pLevel
, pRangeStart
);
1645 }else if( bSeekPastNull
){
1646 sqlite3VdbeAddOp2(v
, OP_Null
, 0, regBase
+nEq
);
1649 start_constraints
= 1;
1651 codeApplyAffinity(pParse
, regBase
, nConstraint
- bSeekPastNull
, zStartAff
);
1652 if( pLoop
->nSkip
>0 && nConstraint
==pLoop
->nSkip
){
1653 /* The skip-scan logic inside the call to codeAllEqualityConstraints()
1654 ** above has already left the cursor sitting on the correct row,
1655 ** so no further seeking is needed */
1657 if( pLoop
->wsFlags
& WHERE_IN_EARLYOUT
){
1658 sqlite3VdbeAddOp1(v
, OP_SeekHit
, iIdxCur
);
1660 op
= aStartOp
[(start_constraints
<<2) + (startEq
<<1) + bRev
];
1662 sqlite3VdbeAddOp4Int(v
, op
, iIdxCur
, addrNxt
, regBase
, nConstraint
);
1664 VdbeCoverageIf(v
, op
==OP_Rewind
); testcase( op
==OP_Rewind
);
1665 VdbeCoverageIf(v
, op
==OP_Last
); testcase( op
==OP_Last
);
1666 VdbeCoverageIf(v
, op
==OP_SeekGT
); testcase( op
==OP_SeekGT
);
1667 VdbeCoverageIf(v
, op
==OP_SeekGE
); testcase( op
==OP_SeekGE
);
1668 VdbeCoverageIf(v
, op
==OP_SeekLE
); testcase( op
==OP_SeekLE
);
1669 VdbeCoverageIf(v
, op
==OP_SeekLT
); testcase( op
==OP_SeekLT
);
1672 /* Load the value for the inequality constraint at the end of the
1677 Expr
*pRight
= pRangeEnd
->pExpr
->pRight
;
1678 codeExprOrVector(pParse
, pRight
, regBase
+nEq
, nTop
);
1679 whereLikeOptimizationStringFixup(v
, pLevel
, pRangeEnd
);
1680 if( (pRangeEnd
->wtFlags
& TERM_VNULL
)==0
1681 && sqlite3ExprCanBeNull(pRight
)
1683 sqlite3VdbeAddOp2(v
, OP_IsNull
, regBase
+nEq
, addrNxt
);
1687 updateRangeAffinityStr(pRight
, nTop
, zEndAff
);
1688 codeApplyAffinity(pParse
, regBase
+nEq
, nTop
, zEndAff
);
1690 assert( pParse
->db
->mallocFailed
);
1692 nConstraint
+= nTop
;
1693 testcase( pRangeEnd
->wtFlags
& TERM_VIRTUAL
);
1695 if( sqlite3ExprIsVector(pRight
)==0 ){
1696 disableTerm(pLevel
, pRangeEnd
);
1700 }else if( bStopAtNull
){
1701 sqlite3VdbeAddOp2(v
, OP_Null
, 0, regBase
+nEq
);
1705 sqlite3DbFree(db
, zStartAff
);
1706 sqlite3DbFree(db
, zEndAff
);
1708 /* Top of the loop body */
1709 pLevel
->p2
= sqlite3VdbeCurrentAddr(v
);
1711 /* Check if the index cursor is past the end of the range. */
1713 op
= aEndOp
[bRev
*2 + endEq
];
1714 sqlite3VdbeAddOp4Int(v
, op
, iIdxCur
, addrNxt
, regBase
, nConstraint
);
1715 testcase( op
==OP_IdxGT
); VdbeCoverageIf(v
, op
==OP_IdxGT
);
1716 testcase( op
==OP_IdxGE
); VdbeCoverageIf(v
, op
==OP_IdxGE
);
1717 testcase( op
==OP_IdxLT
); VdbeCoverageIf(v
, op
==OP_IdxLT
);
1718 testcase( op
==OP_IdxLE
); VdbeCoverageIf(v
, op
==OP_IdxLE
);
1721 if( pLoop
->wsFlags
& WHERE_IN_EARLYOUT
){
1722 sqlite3VdbeAddOp2(v
, OP_SeekHit
, iIdxCur
, 1);
1725 /* Seek the table cursor, if required */
1727 /* pIdx is a covering index. No need to access the main table. */
1728 }else if( HasRowid(pIdx
->pTable
) ){
1729 if( (pWInfo
->wctrlFlags
& WHERE_SEEK_TABLE
) || (
1730 (pWInfo
->wctrlFlags
& WHERE_SEEK_UNIQ_TABLE
)
1731 && (pWInfo
->eOnePass
==ONEPASS_SINGLE
)
1733 iRowidReg
= ++pParse
->nMem
;
1734 sqlite3VdbeAddOp2(v
, OP_IdxRowid
, iIdxCur
, iRowidReg
);
1735 sqlite3VdbeAddOp3(v
, OP_NotExists
, iCur
, 0, iRowidReg
);
1738 codeDeferredSeek(pWInfo
, pIdx
, iCur
, iIdxCur
);
1740 }else if( iCur
!=iIdxCur
){
1741 Index
*pPk
= sqlite3PrimaryKeyIndex(pIdx
->pTable
);
1742 iRowidReg
= sqlite3GetTempRange(pParse
, pPk
->nKeyCol
);
1743 for(j
=0; j
<pPk
->nKeyCol
; j
++){
1744 k
= sqlite3ColumnOfIndex(pIdx
, pPk
->aiColumn
[j
]);
1745 sqlite3VdbeAddOp3(v
, OP_Column
, iIdxCur
, k
, iRowidReg
+j
);
1747 sqlite3VdbeAddOp4Int(v
, OP_NotFound
, iCur
, addrCont
,
1748 iRowidReg
, pPk
->nKeyCol
); VdbeCoverage(v
);
1751 /* If pIdx is an index on one or more expressions, then look through
1752 ** all the expressions in pWInfo and try to transform matching expressions
1753 ** into reference to index columns.
1755 ** Do not do this for the RHS of a LEFT JOIN. This is because the
1756 ** expression may be evaluated after OP_NullRow has been executed on
1757 ** the cursor. In this case it is important to do the full evaluation,
1758 ** as the result of the expression may not be NULL, even if all table
1759 ** column values are. https://www.sqlite.org/src/info/7fa8049685b50b5a
1761 if( pLevel
->iLeftJoin
==0 ){
1762 whereIndexExprTrans(pIdx
, iCur
, iIdxCur
, pWInfo
);
1765 /* Record the instruction used to terminate the loop. */
1766 if( pLoop
->wsFlags
& WHERE_ONEROW
){
1767 pLevel
->op
= OP_Noop
;
1769 pLevel
->op
= OP_Prev
;
1771 pLevel
->op
= OP_Next
;
1773 pLevel
->p1
= iIdxCur
;
1774 pLevel
->p3
= (pLoop
->wsFlags
&WHERE_UNQ_WANTED
)!=0 ? 1:0;
1775 if( (pLoop
->wsFlags
& WHERE_CONSTRAINT
)==0 ){
1776 pLevel
->p5
= SQLITE_STMTSTATUS_FULLSCAN_STEP
;
1778 assert( pLevel
->p5
==0 );
1780 if( omitTable
) pIdx
= 0;
1783 #ifndef SQLITE_OMIT_OR_OPTIMIZATION
1784 if( pLoop
->wsFlags
& WHERE_MULTI_OR
){
1785 /* Case 5: Two or more separately indexed terms connected by OR
1789 ** CREATE TABLE t1(a,b,c,d);
1790 ** CREATE INDEX i1 ON t1(a);
1791 ** CREATE INDEX i2 ON t1(b);
1792 ** CREATE INDEX i3 ON t1(c);
1794 ** SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
1796 ** In the example, there are three indexed terms connected by OR.
1797 ** The top of the loop looks like this:
1799 ** Null 1 # Zero the rowset in reg 1
1801 ** Then, for each indexed term, the following. The arguments to
1802 ** RowSetTest are such that the rowid of the current row is inserted
1803 ** into the RowSet. If it is already present, control skips the
1804 ** Gosub opcode and jumps straight to the code generated by WhereEnd().
1806 ** sqlite3WhereBegin(<term>)
1807 ** RowSetTest # Insert rowid into rowset
1809 ** sqlite3WhereEnd()
1811 ** Following the above, code to terminate the loop. Label A, the target
1812 ** of the Gosub above, jumps to the instruction right after the Goto.
1814 ** Null 1 # Zero the rowset in reg 1
1815 ** Goto B # The loop is finished.
1817 ** A: <loop body> # Return data, whatever.
1819 ** Return 2 # Jump back to the Gosub
1821 ** B: <after the loop>
1823 ** Added 2014-05-26: If the table is a WITHOUT ROWID table, then
1824 ** use an ephemeral index instead of a RowSet to record the primary
1825 ** keys of the rows we have already seen.
1828 WhereClause
*pOrWc
; /* The OR-clause broken out into subterms */
1829 SrcList
*pOrTab
; /* Shortened table list or OR-clause generation */
1830 Index
*pCov
= 0; /* Potential covering index (or NULL) */
1831 int iCovCur
= pParse
->nTab
++; /* Cursor used for index scans (if any) */
1833 int regReturn
= ++pParse
->nMem
; /* Register used with OP_Gosub */
1834 int regRowset
= 0; /* Register for RowSet object */
1835 int regRowid
= 0; /* Register holding rowid */
1836 int iLoopBody
= sqlite3VdbeMakeLabel(v
); /* Start of loop body */
1837 int iRetInit
; /* Address of regReturn init */
1838 int untestedTerms
= 0; /* Some terms not completely tested */
1839 int ii
; /* Loop counter */
1840 u16 wctrlFlags
; /* Flags for sub-WHERE clause */
1841 Expr
*pAndExpr
= 0; /* An ".. AND (...)" expression */
1842 Table
*pTab
= pTabItem
->pTab
;
1844 pTerm
= pLoop
->aLTerm
[0];
1846 assert( pTerm
->eOperator
& WO_OR
);
1847 assert( (pTerm
->wtFlags
& TERM_ORINFO
)!=0 );
1848 pOrWc
= &pTerm
->u
.pOrInfo
->wc
;
1849 pLevel
->op
= OP_Return
;
1850 pLevel
->p1
= regReturn
;
1852 /* Set up a new SrcList in pOrTab containing the table being scanned
1853 ** by this loop in the a[0] slot and all notReady tables in a[1..] slots.
1854 ** This becomes the SrcList in the recursive call to sqlite3WhereBegin().
1856 if( pWInfo
->nLevel
>1 ){
1857 int nNotReady
; /* The number of notReady tables */
1858 struct SrcList_item
*origSrc
; /* Original list of tables */
1859 nNotReady
= pWInfo
->nLevel
- iLevel
- 1;
1860 pOrTab
= sqlite3StackAllocRaw(db
,
1861 sizeof(*pOrTab
)+ nNotReady
*sizeof(pOrTab
->a
[0]));
1862 if( pOrTab
==0 ) return notReady
;
1863 pOrTab
->nAlloc
= (u8
)(nNotReady
+ 1);
1864 pOrTab
->nSrc
= pOrTab
->nAlloc
;
1865 memcpy(pOrTab
->a
, pTabItem
, sizeof(*pTabItem
));
1866 origSrc
= pWInfo
->pTabList
->a
;
1867 for(k
=1; k
<=nNotReady
; k
++){
1868 memcpy(&pOrTab
->a
[k
], &origSrc
[pLevel
[k
].iFrom
], sizeof(pOrTab
->a
[k
]));
1871 pOrTab
= pWInfo
->pTabList
;
1874 /* Initialize the rowset register to contain NULL. An SQL NULL is
1875 ** equivalent to an empty rowset. Or, create an ephemeral index
1876 ** capable of holding primary keys in the case of a WITHOUT ROWID.
1878 ** Also initialize regReturn to contain the address of the instruction
1879 ** immediately following the OP_Return at the bottom of the loop. This
1880 ** is required in a few obscure LEFT JOIN cases where control jumps
1881 ** over the top of the loop into the body of it. In this case the
1882 ** correct response for the end-of-loop code (the OP_Return) is to
1883 ** fall through to the next instruction, just as an OP_Next does if
1884 ** called on an uninitialized cursor.
1886 if( (pWInfo
->wctrlFlags
& WHERE_DUPLICATES_OK
)==0 ){
1887 if( HasRowid(pTab
) ){
1888 regRowset
= ++pParse
->nMem
;
1889 sqlite3VdbeAddOp2(v
, OP_Null
, 0, regRowset
);
1891 Index
*pPk
= sqlite3PrimaryKeyIndex(pTab
);
1892 regRowset
= pParse
->nTab
++;
1893 sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, regRowset
, pPk
->nKeyCol
);
1894 sqlite3VdbeSetP4KeyInfo(pParse
, pPk
);
1896 regRowid
= ++pParse
->nMem
;
1898 iRetInit
= sqlite3VdbeAddOp2(v
, OP_Integer
, 0, regReturn
);
1900 /* If the original WHERE clause is z of the form: (x1 OR x2 OR ...) AND y
1901 ** Then for every term xN, evaluate as the subexpression: xN AND z
1902 ** That way, terms in y that are factored into the disjunction will
1903 ** be picked up by the recursive calls to sqlite3WhereBegin() below.
1905 ** Actually, each subexpression is converted to "xN AND w" where w is
1906 ** the "interesting" terms of z - terms that did not originate in the
1907 ** ON or USING clause of a LEFT JOIN, and terms that are usable as
1910 ** This optimization also only applies if the (x1 OR x2 OR ...) term
1911 ** is not contained in the ON clause of a LEFT JOIN.
1912 ** See ticket http://www.sqlite.org/src/info/f2369304e4
1916 for(iTerm
=0; iTerm
<pWC
->nTerm
; iTerm
++){
1917 Expr
*pExpr
= pWC
->a
[iTerm
].pExpr
;
1918 if( &pWC
->a
[iTerm
] == pTerm
) continue;
1919 testcase( pWC
->a
[iTerm
].wtFlags
& TERM_VIRTUAL
);
1920 testcase( pWC
->a
[iTerm
].wtFlags
& TERM_CODED
);
1921 if( (pWC
->a
[iTerm
].wtFlags
& (TERM_VIRTUAL
|TERM_CODED
))!=0 ) continue;
1922 if( (pWC
->a
[iTerm
].eOperator
& WO_ALL
)==0 ) continue;
1923 testcase( pWC
->a
[iTerm
].wtFlags
& TERM_ORINFO
);
1924 pExpr
= sqlite3ExprDup(db
, pExpr
, 0);
1925 pAndExpr
= sqlite3ExprAnd(db
, pAndExpr
, pExpr
);
1928 pAndExpr
= sqlite3PExpr(pParse
, TK_AND
|TKFLG_DONTFOLD
, 0, pAndExpr
);
1932 /* Run a separate WHERE clause for each term of the OR clause. After
1933 ** eliminating duplicates from other WHERE clauses, the action for each
1934 ** sub-WHERE clause is to to invoke the main loop body as a subroutine.
1936 wctrlFlags
= WHERE_OR_SUBCLAUSE
| (pWInfo
->wctrlFlags
& WHERE_SEEK_TABLE
);
1937 ExplainQueryPlan((pParse
, 1, "MULTI-INDEX OR"));
1938 for(ii
=0; ii
<pOrWc
->nTerm
; ii
++){
1939 WhereTerm
*pOrTerm
= &pOrWc
->a
[ii
];
1940 if( pOrTerm
->leftCursor
==iCur
|| (pOrTerm
->eOperator
& WO_AND
)!=0 ){
1941 WhereInfo
*pSubWInfo
; /* Info for single OR-term scan */
1942 Expr
*pOrExpr
= pOrTerm
->pExpr
; /* Current OR clause term */
1943 int jmp1
= 0; /* Address of jump operation */
1944 assert( (pTabItem
[0].fg
.jointype
& JT_LEFT
)==0
1945 || ExprHasProperty(pOrExpr
, EP_FromJoin
)
1948 pAndExpr
->pLeft
= pOrExpr
;
1951 /* Loop through table entries that match term pOrTerm. */
1952 WHERETRACE(0xffff, ("Subplan for OR-clause:\n"));
1953 pSubWInfo
= sqlite3WhereBegin(pParse
, pOrTab
, pOrExpr
, 0, 0,
1954 wctrlFlags
, iCovCur
);
1955 assert( pSubWInfo
|| pParse
->nErr
|| db
->mallocFailed
);
1957 WhereLoop
*pSubLoop
;
1958 int addrExplain
= sqlite3WhereExplainOneScan(
1959 pParse
, pOrTab
, &pSubWInfo
->a
[0], 0
1961 sqlite3WhereAddScanStatus(v
, pOrTab
, &pSubWInfo
->a
[0], addrExplain
);
1963 /* This is the sub-WHERE clause body. First skip over
1964 ** duplicate rows from prior sub-WHERE clauses, and record the
1965 ** rowid (or PRIMARY KEY) for the current row so that the same
1966 ** row will be skipped in subsequent sub-WHERE clauses.
1968 if( (pWInfo
->wctrlFlags
& WHERE_DUPLICATES_OK
)==0 ){
1969 int iSet
= ((ii
==pOrWc
->nTerm
-1)?-1:ii
);
1970 if( HasRowid(pTab
) ){
1971 sqlite3ExprCodeGetColumnOfTable(v
, pTab
, iCur
, -1, regRowid
);
1972 jmp1
= sqlite3VdbeAddOp4Int(v
, OP_RowSetTest
, regRowset
, 0,
1976 Index
*pPk
= sqlite3PrimaryKeyIndex(pTab
);
1977 int nPk
= pPk
->nKeyCol
;
1981 /* Read the PK into an array of temp registers. */
1982 r
= sqlite3GetTempRange(pParse
, nPk
);
1983 for(iPk
=0; iPk
<nPk
; iPk
++){
1984 int iCol
= pPk
->aiColumn
[iPk
];
1985 sqlite3ExprCodeGetColumnOfTable(v
, pTab
, iCur
, iCol
, r
+iPk
);
1988 /* Check if the temp table already contains this key. If so,
1989 ** the row has already been included in the result set and
1990 ** can be ignored (by jumping past the Gosub below). Otherwise,
1991 ** insert the key into the temp table and proceed with processing
1994 ** Use some of the same optimizations as OP_RowSetTest: If iSet
1995 ** is zero, assume that the key cannot already be present in
1996 ** the temp table. And if iSet is -1, assume that there is no
1997 ** need to insert the key into the temp table, as it will never
1998 ** be tested for. */
2000 jmp1
= sqlite3VdbeAddOp4Int(v
, OP_Found
, regRowset
, 0, r
, nPk
);
2004 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, r
, nPk
, regRowid
);
2005 sqlite3VdbeAddOp4Int(v
, OP_IdxInsert
, regRowset
, regRowid
,
2007 if( iSet
) sqlite3VdbeChangeP5(v
, OPFLAG_USESEEKRESULT
);
2010 /* Release the array of temp registers */
2011 sqlite3ReleaseTempRange(pParse
, r
, nPk
);
2015 /* Invoke the main loop body as a subroutine */
2016 sqlite3VdbeAddOp2(v
, OP_Gosub
, regReturn
, iLoopBody
);
2018 /* Jump here (skipping the main loop body subroutine) if the
2019 ** current sub-WHERE row is a duplicate from prior sub-WHEREs. */
2020 if( jmp1
) sqlite3VdbeJumpHere(v
, jmp1
);
2022 /* The pSubWInfo->untestedTerms flag means that this OR term
2023 ** contained one or more AND term from a notReady table. The
2024 ** terms from the notReady table could not be tested and will
2025 ** need to be tested later.
2027 if( pSubWInfo
->untestedTerms
) untestedTerms
= 1;
2029 /* If all of the OR-connected terms are optimized using the same
2030 ** index, and the index is opened using the same cursor number
2031 ** by each call to sqlite3WhereBegin() made by this loop, it may
2032 ** be possible to use that index as a covering index.
2034 ** If the call to sqlite3WhereBegin() above resulted in a scan that
2035 ** uses an index, and this is either the first OR-connected term
2036 ** processed or the index is the same as that used by all previous
2037 ** terms, set pCov to the candidate covering index. Otherwise, set
2038 ** pCov to NULL to indicate that no candidate covering index will
2041 pSubLoop
= pSubWInfo
->a
[0].pWLoop
;
2042 assert( (pSubLoop
->wsFlags
& WHERE_AUTO_INDEX
)==0 );
2043 if( (pSubLoop
->wsFlags
& WHERE_INDEXED
)!=0
2044 && (ii
==0 || pSubLoop
->u
.btree
.pIndex
==pCov
)
2045 && (HasRowid(pTab
) || !IsPrimaryKeyIndex(pSubLoop
->u
.btree
.pIndex
))
2047 assert( pSubWInfo
->a
[0].iIdxCur
==iCovCur
);
2048 pCov
= pSubLoop
->u
.btree
.pIndex
;
2053 /* Finish the loop through table entries that match term pOrTerm. */
2054 sqlite3WhereEnd(pSubWInfo
);
2058 ExplainQueryPlanPop(pParse
);
2059 pLevel
->u
.pCovidx
= pCov
;
2060 if( pCov
) pLevel
->iIdxCur
= iCovCur
;
2062 pAndExpr
->pLeft
= 0;
2063 sqlite3ExprDelete(db
, pAndExpr
);
2065 sqlite3VdbeChangeP1(v
, iRetInit
, sqlite3VdbeCurrentAddr(v
));
2066 sqlite3VdbeGoto(v
, pLevel
->addrBrk
);
2067 sqlite3VdbeResolveLabel(v
, iLoopBody
);
2069 if( pWInfo
->nLevel
>1 ) sqlite3StackFree(db
, pOrTab
);
2070 if( !untestedTerms
) disableTerm(pLevel
, pTerm
);
2072 #endif /* SQLITE_OMIT_OR_OPTIMIZATION */
2075 /* Case 6: There is no usable index. We must do a complete
2076 ** scan of the entire table.
2078 static const u8 aStep
[] = { OP_Next
, OP_Prev
};
2079 static const u8 aStart
[] = { OP_Rewind
, OP_Last
};
2080 assert( bRev
==0 || bRev
==1 );
2081 if( pTabItem
->fg
.isRecursive
){
2082 /* Tables marked isRecursive have only a single row that is stored in
2083 ** a pseudo-cursor. No need to Rewind or Next such cursors. */
2084 pLevel
->op
= OP_Noop
;
2086 codeCursorHint(pTabItem
, pWInfo
, pLevel
, 0);
2087 pLevel
->op
= aStep
[bRev
];
2089 pLevel
->p2
= 1 + sqlite3VdbeAddOp2(v
, aStart
[bRev
], iCur
, addrHalt
);
2090 VdbeCoverageIf(v
, bRev
==0);
2091 VdbeCoverageIf(v
, bRev
!=0);
2092 pLevel
->p5
= SQLITE_STMTSTATUS_FULLSCAN_STEP
;
2096 #ifdef SQLITE_ENABLE_STMT_SCANSTATUS
2097 pLevel
->addrVisit
= sqlite3VdbeCurrentAddr(v
);
2100 /* Insert code to test every subexpression that can be completely
2101 ** computed using the current set of tables.
2103 ** This loop may run between one and three times, depending on the
2104 ** constraints to be generated. The value of stack variable iLoop
2105 ** determines the constraints coded by each iteration, as follows:
2107 ** iLoop==1: Code only expressions that are entirely covered by pIdx.
2108 ** iLoop==2: Code remaining expressions that do not contain correlated
2110 ** iLoop==3: Code all remaining expressions.
2112 ** An effort is made to skip unnecessary iterations of the loop.
2114 iLoop
= (pIdx
? 1 : 2);
2116 int iNext
= 0; /* Next value for iLoop */
2117 for(pTerm
=pWC
->a
, j
=pWC
->nTerm
; j
>0; j
--, pTerm
++){
2119 int skipLikeAddr
= 0;
2120 testcase( pTerm
->wtFlags
& TERM_VIRTUAL
);
2121 testcase( pTerm
->wtFlags
& TERM_CODED
);
2122 if( pTerm
->wtFlags
& (TERM_VIRTUAL
|TERM_CODED
) ) continue;
2123 if( (pTerm
->prereqAll
& pLevel
->notReady
)!=0 ){
2124 testcase( pWInfo
->untestedTerms
==0
2125 && (pWInfo
->wctrlFlags
& WHERE_OR_SUBCLAUSE
)!=0 );
2126 pWInfo
->untestedTerms
= 1;
2131 if( (pTabItem
->fg
.jointype
&JT_LEFT
) && !ExprHasProperty(pE
,EP_FromJoin
) ){
2135 if( iLoop
==1 && !sqlite3ExprCoveredByIndex(pE
, pLevel
->iTabCur
, pIdx
) ){
2139 if( iLoop
<3 && (pTerm
->wtFlags
& TERM_VARSELECT
) ){
2140 if( iNext
==0 ) iNext
= 3;
2144 if( (pTerm
->wtFlags
& TERM_LIKECOND
)!=0 ){
2145 /* If the TERM_LIKECOND flag is set, that means that the range search
2146 ** is sufficient to guarantee that the LIKE operator is true, so we
2147 ** can skip the call to the like(A,B) function. But this only works
2148 ** for strings. So do not skip the call to the function on the pass
2149 ** that compares BLOBs. */
2150 #ifdef SQLITE_LIKE_DOESNT_MATCH_BLOBS
2153 u32 x
= pLevel
->iLikeRepCntr
;
2155 skipLikeAddr
= sqlite3VdbeAddOp1(v
, (x
&1)?OP_IfNot
:OP_If
,(int)(x
>>1));
2160 #ifdef WHERETRACE_ENABLED /* 0xffff */
2161 if( sqlite3WhereTrace
){
2162 VdbeNoopComment((v
, "WhereTerm[%d] (%p) priority=%d",
2163 pWC
->nTerm
-j
, pTerm
, iLoop
));
2166 sqlite3ExprIfFalse(pParse
, pE
, addrCont
, SQLITE_JUMPIFNULL
);
2167 if( skipLikeAddr
) sqlite3VdbeJumpHere(v
, skipLikeAddr
);
2168 pTerm
->wtFlags
|= TERM_CODED
;
2173 /* Insert code to test for implied constraints based on transitivity
2174 ** of the "==" operator.
2176 ** Example: If the WHERE clause contains "t1.a=t2.b" and "t2.b=123"
2177 ** and we are coding the t1 loop and the t2 loop has not yet coded,
2178 ** then we cannot use the "t1.a=t2.b" constraint, but we can code
2179 ** the implied "t1.a=123" constraint.
2181 for(pTerm
=pWC
->a
, j
=pWC
->nTerm
; j
>0; j
--, pTerm
++){
2184 if( pTerm
->wtFlags
& (TERM_VIRTUAL
|TERM_CODED
) ) continue;
2185 if( (pTerm
->eOperator
& (WO_EQ
|WO_IS
))==0 ) continue;
2186 if( (pTerm
->eOperator
& WO_EQUIV
)==0 ) continue;
2187 if( pTerm
->leftCursor
!=iCur
) continue;
2188 if( pLevel
->iLeftJoin
) continue;
2190 assert( !ExprHasProperty(pE
, EP_FromJoin
) );
2191 assert( (pTerm
->prereqRight
& pLevel
->notReady
)!=0 );
2192 pAlt
= sqlite3WhereFindTerm(pWC
, iCur
, pTerm
->u
.leftColumn
, notReady
,
2193 WO_EQ
|WO_IN
|WO_IS
, 0);
2194 if( pAlt
==0 ) continue;
2195 if( pAlt
->wtFlags
& (TERM_CODED
) ) continue;
2196 if( (pAlt
->eOperator
& WO_IN
)
2197 && (pAlt
->pExpr
->flags
& EP_xIsSelect
)
2198 && (pAlt
->pExpr
->x
.pSelect
->pEList
->nExpr
>1)
2202 testcase( pAlt
->eOperator
& WO_EQ
);
2203 testcase( pAlt
->eOperator
& WO_IS
);
2204 testcase( pAlt
->eOperator
& WO_IN
);
2205 VdbeModuleComment((v
, "begin transitive constraint"));
2206 sEAlt
= *pAlt
->pExpr
;
2207 sEAlt
.pLeft
= pE
->pLeft
;
2208 sqlite3ExprIfFalse(pParse
, &sEAlt
, addrCont
, SQLITE_JUMPIFNULL
);
2211 /* For a LEFT OUTER JOIN, generate code that will record the fact that
2212 ** at least one row of the right table has matched the left table.
2214 if( pLevel
->iLeftJoin
){
2215 pLevel
->addrFirst
= sqlite3VdbeCurrentAddr(v
);
2216 sqlite3VdbeAddOp2(v
, OP_Integer
, 1, pLevel
->iLeftJoin
);
2217 VdbeComment((v
, "record LEFT JOIN hit"));
2218 for(pTerm
=pWC
->a
, j
=0; j
<pWC
->nTerm
; j
++, pTerm
++){
2219 testcase( pTerm
->wtFlags
& TERM_VIRTUAL
);
2220 testcase( pTerm
->wtFlags
& TERM_CODED
);
2221 if( pTerm
->wtFlags
& (TERM_VIRTUAL
|TERM_CODED
) ) continue;
2222 if( (pTerm
->prereqAll
& pLevel
->notReady
)!=0 ){
2223 assert( pWInfo
->untestedTerms
);
2226 assert( pTerm
->pExpr
);
2227 sqlite3ExprIfFalse(pParse
, pTerm
->pExpr
, addrCont
, SQLITE_JUMPIFNULL
);
2228 pTerm
->wtFlags
|= TERM_CODED
;
2232 return pLevel
->notReady
;