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 sqlite3ExplainBreakpoint("",zMsg
);
217 ret
= sqlite3VdbeAddOp4(v
, OP_Explain
, sqlite3VdbeCurrentAddr(v
),
218 pParse
->addrExplain
, 0, zMsg
,P4_DYNAMIC
);
222 #endif /* SQLITE_OMIT_EXPLAIN */
224 #ifdef SQLITE_ENABLE_STMT_SCANSTATUS
226 ** Configure the VM passed as the first argument with an
227 ** sqlite3_stmt_scanstatus() entry corresponding to the scan used to
228 ** implement level pLvl. Argument pSrclist is a pointer to the FROM
229 ** clause that the scan reads data from.
231 ** If argument addrExplain is not 0, it must be the address of an
232 ** OP_Explain instruction that describes the same loop.
234 void sqlite3WhereAddScanStatus(
235 Vdbe
*v
, /* Vdbe to add scanstatus entry to */
236 SrcList
*pSrclist
, /* FROM clause pLvl reads data from */
237 WhereLevel
*pLvl
, /* Level to add scanstatus() entry for */
238 int addrExplain
/* Address of OP_Explain (or 0) */
240 const char *zObj
= 0;
241 WhereLoop
*pLoop
= pLvl
->pWLoop
;
242 if( (pLoop
->wsFlags
& WHERE_VIRTUALTABLE
)==0 && pLoop
->u
.btree
.pIndex
!=0 ){
243 zObj
= pLoop
->u
.btree
.pIndex
->zName
;
245 zObj
= pSrclist
->a
[pLvl
->iFrom
].zName
;
247 sqlite3VdbeScanStatus(
248 v
, addrExplain
, pLvl
->addrBody
, pLvl
->addrVisit
, pLoop
->nOut
, zObj
255 ** Disable a term in the WHERE clause. Except, do not disable the term
256 ** if it controls a LEFT OUTER JOIN and it did not originate in the ON
257 ** or USING clause of that join.
259 ** Consider the term t2.z='ok' in the following queries:
261 ** (1) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok'
262 ** (2) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok'
263 ** (3) SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok'
265 ** The t2.z='ok' is disabled in the in (2) because it originates
266 ** in the ON clause. The term is disabled in (3) because it is not part
267 ** of a LEFT OUTER JOIN. In (1), the term is not disabled.
269 ** Disabling a term causes that term to not be tested in the inner loop
270 ** of the join. Disabling is an optimization. When terms are satisfied
271 ** by indices, we disable them to prevent redundant tests in the inner
272 ** loop. We would get the correct results if nothing were ever disabled,
273 ** but joins might run a little slower. The trick is to disable as much
274 ** as we can without disabling too much. If we disabled in (1), we'd get
275 ** the wrong answer. See ticket #813.
277 ** If all the children of a term are disabled, then that term is also
278 ** automatically disabled. In this way, terms get disabled if derived
279 ** virtual terms are tested first. For example:
281 ** x GLOB 'abc*' AND x>='abc' AND x<'acd'
282 ** \___________/ \______/ \_____/
283 ** parent child1 child2
285 ** Only the parent term was in the original WHERE clause. The child1
286 ** and child2 terms were added by the LIKE optimization. If both of
287 ** the virtual child terms are valid, then testing of the parent can be
290 ** Usually the parent term is marked as TERM_CODED. But if the parent
291 ** term was originally TERM_LIKE, then the parent gets TERM_LIKECOND instead.
292 ** The TERM_LIKECOND marking indicates that the term should be coded inside
293 ** a conditional such that is only evaluated on the second pass of a
294 ** LIKE-optimization loop, when scanning BLOBs instead of strings.
296 static void disableTerm(WhereLevel
*pLevel
, WhereTerm
*pTerm
){
299 while( (pTerm
->wtFlags
& TERM_CODED
)==0
300 && (pLevel
->iLeftJoin
==0 || ExprHasProperty(pTerm
->pExpr
, EP_FromJoin
))
301 && (pLevel
->notReady
& pTerm
->prereqAll
)==0
303 if( nLoop
&& (pTerm
->wtFlags
& TERM_LIKE
)!=0 ){
304 pTerm
->wtFlags
|= TERM_LIKECOND
;
306 pTerm
->wtFlags
|= TERM_CODED
;
308 if( pTerm
->iParent
<0 ) break;
309 pTerm
= &pTerm
->pWC
->a
[pTerm
->iParent
];
312 if( pTerm
->nChild
!=0 ) break;
318 ** Code an OP_Affinity opcode to apply the column affinity string zAff
319 ** to the n registers starting at base.
321 ** As an optimization, SQLITE_AFF_BLOB and SQLITE_AFF_NONE entries (which
322 ** are no-ops) at the beginning and end of zAff are ignored. If all entries
323 ** in zAff are SQLITE_AFF_BLOB or SQLITE_AFF_NONE, then no code gets generated.
325 ** This routine makes its own copy of zAff so that the caller is free
326 ** to modify zAff after this routine returns.
328 static void codeApplyAffinity(Parse
*pParse
, int base
, int n
, char *zAff
){
329 Vdbe
*v
= pParse
->pVdbe
;
331 assert( pParse
->db
->mallocFailed
);
336 /* Adjust base and n to skip over SQLITE_AFF_BLOB and SQLITE_AFF_NONE
337 ** entries at the beginning and end of the affinity string.
339 assert( SQLITE_AFF_NONE
<SQLITE_AFF_BLOB
);
340 while( n
>0 && zAff
[0]<=SQLITE_AFF_BLOB
){
345 while( n
>1 && zAff
[n
-1]<=SQLITE_AFF_BLOB
){
349 /* Code the OP_Affinity opcode if there is anything left to do. */
351 sqlite3VdbeAddOp4(v
, OP_Affinity
, base
, n
, 0, zAff
, n
);
356 ** Expression pRight, which is the RHS of a comparison operation, is
357 ** either a vector of n elements or, if n==1, a scalar expression.
358 ** Before the comparison operation, affinity zAff is to be applied
359 ** to the pRight values. This function modifies characters within the
360 ** affinity string to SQLITE_AFF_BLOB if either:
362 ** * the comparison will be performed with no affinity, or
363 ** * the affinity change in zAff is guaranteed not to change the value.
365 static void updateRangeAffinityStr(
366 Expr
*pRight
, /* RHS of comparison */
367 int n
, /* Number of vector elements in comparison */
368 char *zAff
/* Affinity string to modify */
372 Expr
*p
= sqlite3VectorFieldSubexpr(pRight
, i
);
373 if( sqlite3CompareAffinity(p
, zAff
[i
])==SQLITE_AFF_BLOB
374 || sqlite3ExprNeedsNoAffinityChange(p
, zAff
[i
])
376 zAff
[i
] = SQLITE_AFF_BLOB
;
383 ** pX is an expression of the form: (vector) IN (SELECT ...)
384 ** In other words, it is a vector IN operator with a SELECT clause on the
385 ** LHS. But not all terms in the vector are indexable and the terms might
386 ** not be in the correct order for indexing.
388 ** This routine makes a copy of the input pX expression and then adjusts
389 ** the vector on the LHS with corresponding changes to the SELECT so that
390 ** the vector contains only index terms and those terms are in the correct
391 ** order. The modified IN expression is returned. The caller is responsible
392 ** for deleting the returned expression.
396 ** CREATE TABLE t1(a,b,c,d,e,f);
397 ** CREATE INDEX t1x1 ON t1(e,c);
398 ** SELECT * FROM t1 WHERE (a,b,c,d,e) IN (SELECT v,w,x,y,z FROM t2)
399 ** \_______________________________________/
402 ** Since only columns e and c can be used with the index, in that order,
403 ** the modified IN expression that is returned will be:
405 ** (e,c) IN (SELECT z,x FROM t2)
407 ** The reduced pX is different from the original (obviously) and thus is
408 ** only used for indexing, to improve performance. The original unaltered
409 ** IN expression must also be run on each output row for correctness.
411 static Expr
*removeUnindexableInClauseTerms(
412 Parse
*pParse
, /* The parsing context */
413 int iEq
, /* Look at loop terms starting here */
414 WhereLoop
*pLoop
, /* The current loop */
415 Expr
*pX
/* The IN expression to be reduced */
417 sqlite3
*db
= pParse
->db
;
419 pNew
= sqlite3ExprDup(db
, pX
, 0);
420 if( db
->mallocFailed
==0 ){
421 ExprList
*pOrigRhs
= pNew
->x
.pSelect
->pEList
; /* Original unmodified RHS */
422 ExprList
*pOrigLhs
= pNew
->pLeft
->x
.pList
; /* Original unmodified LHS */
423 ExprList
*pRhs
= 0; /* New RHS after modifications */
424 ExprList
*pLhs
= 0; /* New LHS after mods */
425 int i
; /* Loop counter */
426 Select
*pSelect
; /* Pointer to the SELECT on the RHS */
428 for(i
=iEq
; i
<pLoop
->nLTerm
; i
++){
429 if( pLoop
->aLTerm
[i
]->pExpr
==pX
){
430 int iField
= pLoop
->aLTerm
[i
]->iField
- 1;
431 if( pOrigRhs
->a
[iField
].pExpr
==0 ) continue; /* Duplicate PK column */
432 pRhs
= sqlite3ExprListAppend(pParse
, pRhs
, pOrigRhs
->a
[iField
].pExpr
);
433 pOrigRhs
->a
[iField
].pExpr
= 0;
434 assert( pOrigLhs
->a
[iField
].pExpr
!=0 );
435 pLhs
= sqlite3ExprListAppend(pParse
, pLhs
, pOrigLhs
->a
[iField
].pExpr
);
436 pOrigLhs
->a
[iField
].pExpr
= 0;
439 sqlite3ExprListDelete(db
, pOrigRhs
);
440 sqlite3ExprListDelete(db
, pOrigLhs
);
441 pNew
->pLeft
->x
.pList
= pLhs
;
442 pNew
->x
.pSelect
->pEList
= pRhs
;
443 if( pLhs
&& pLhs
->nExpr
==1 ){
444 /* Take care here not to generate a TK_VECTOR containing only a
445 ** single value. Since the parser never creates such a vector, some
446 ** of the subroutines do not handle this case. */
447 Expr
*p
= pLhs
->a
[0].pExpr
;
448 pLhs
->a
[0].pExpr
= 0;
449 sqlite3ExprDelete(db
, pNew
->pLeft
);
452 pSelect
= pNew
->x
.pSelect
;
453 if( pSelect
->pOrderBy
){
454 /* If the SELECT statement has an ORDER BY clause, zero the
455 ** iOrderByCol variables. These are set to non-zero when an
456 ** ORDER BY term exactly matches one of the terms of the
457 ** result-set. Since the result-set of the SELECT statement may
458 ** have been modified or reordered, these variables are no longer
459 ** set correctly. Since setting them is just an optimization,
460 ** it's easiest just to zero them here. */
461 ExprList
*pOrderBy
= pSelect
->pOrderBy
;
462 for(i
=0; i
<pOrderBy
->nExpr
; i
++){
463 pOrderBy
->a
[i
].u
.x
.iOrderByCol
= 0;
468 printf("For indexing, change the IN expr:\n");
469 sqlite3TreeViewExpr(0, pX
, 0);
471 sqlite3TreeViewExpr(0, pNew
, 0);
479 ** Generate code for a single equality term of the WHERE clause. An equality
480 ** term can be either X=expr or X IN (...). pTerm is the term to be
483 ** The current value for the constraint is left in a register, the index
484 ** of which is returned. An attempt is made store the result in iTarget but
485 ** this is only guaranteed for TK_ISNULL and TK_IN constraints. If the
486 ** constraint is a TK_EQ or TK_IS, then the current value might be left in
487 ** some other register and it is the caller's responsibility to compensate.
489 ** For a constraint of the form X=expr, the expression is evaluated in
490 ** straight-line code. For constraints of the form X IN (...)
491 ** this routine sets up a loop that will iterate over all values of X.
493 static int codeEqualityTerm(
494 Parse
*pParse
, /* The parsing context */
495 WhereTerm
*pTerm
, /* The term of the WHERE clause to be coded */
496 WhereLevel
*pLevel
, /* The level of the FROM clause we are working on */
497 int iEq
, /* Index of the equality term within this level */
498 int bRev
, /* True for reverse-order IN operations */
499 int iTarget
/* Attempt to leave results in this register */
501 Expr
*pX
= pTerm
->pExpr
;
502 Vdbe
*v
= pParse
->pVdbe
;
503 int iReg
; /* Register holding results */
505 assert( pLevel
->pWLoop
->aLTerm
[iEq
]==pTerm
);
507 if( pX
->op
==TK_EQ
|| pX
->op
==TK_IS
){
508 iReg
= sqlite3ExprCodeTarget(pParse
, pX
->pRight
, iTarget
);
509 }else if( pX
->op
==TK_ISNULL
){
511 sqlite3VdbeAddOp2(v
, OP_Null
, 0, iReg
);
512 #ifndef SQLITE_OMIT_SUBQUERY
514 int eType
= IN_INDEX_NOOP
;
517 WhereLoop
*pLoop
= pLevel
->pWLoop
;
522 if( (pLoop
->wsFlags
& WHERE_VIRTUALTABLE
)==0
523 && pLoop
->u
.btree
.pIndex
!=0
524 && pLoop
->u
.btree
.pIndex
->aSortOrder
[iEq
]
530 assert( pX
->op
==TK_IN
);
533 for(i
=0; i
<iEq
; i
++){
534 if( pLoop
->aLTerm
[i
] && pLoop
->aLTerm
[i
]->pExpr
==pX
){
535 disableTerm(pLevel
, pTerm
);
539 for(i
=iEq
;i
<pLoop
->nLTerm
; i
++){
540 assert( pLoop
->aLTerm
[i
]!=0 );
541 if( pLoop
->aLTerm
[i
]->pExpr
==pX
) nEq
++;
545 if( (pX
->flags
& EP_xIsSelect
)==0 || pX
->x
.pSelect
->pEList
->nExpr
==1 ){
546 eType
= sqlite3FindInIndex(pParse
, pX
, IN_INDEX_LOOP
, 0, 0, &iTab
);
548 sqlite3
*db
= pParse
->db
;
549 pX
= removeUnindexableInClauseTerms(pParse
, iEq
, pLoop
, pX
);
551 if( !db
->mallocFailed
){
552 aiMap
= (int*)sqlite3DbMallocZero(pParse
->db
, sizeof(int)*nEq
);
553 eType
= sqlite3FindInIndex(pParse
, pX
, IN_INDEX_LOOP
, 0, aiMap
, &iTab
);
554 pTerm
->pExpr
->iTable
= iTab
;
556 sqlite3ExprDelete(db
, pX
);
560 if( eType
==IN_INDEX_INDEX_DESC
){
564 sqlite3VdbeAddOp2(v
, bRev
? OP_Last
: OP_Rewind
, iTab
, 0);
565 VdbeCoverageIf(v
, bRev
);
566 VdbeCoverageIf(v
, !bRev
);
567 assert( (pLoop
->wsFlags
& WHERE_MULTI_OR
)==0 );
569 pLoop
->wsFlags
|= WHERE_IN_ABLE
;
570 if( pLevel
->u
.in
.nIn
==0 ){
571 pLevel
->addrNxt
= sqlite3VdbeMakeLabel(pParse
);
574 i
= pLevel
->u
.in
.nIn
;
575 pLevel
->u
.in
.nIn
+= nEq
;
576 pLevel
->u
.in
.aInLoop
=
577 sqlite3DbReallocOrFree(pParse
->db
, pLevel
->u
.in
.aInLoop
,
578 sizeof(pLevel
->u
.in
.aInLoop
[0])*pLevel
->u
.in
.nIn
);
579 pIn
= pLevel
->u
.in
.aInLoop
;
581 int iMap
= 0; /* Index in aiMap[] */
583 for(i
=iEq
;i
<pLoop
->nLTerm
; i
++){
584 if( pLoop
->aLTerm
[i
]->pExpr
==pX
){
585 int iOut
= iReg
+ i
- iEq
;
586 if( eType
==IN_INDEX_ROWID
){
587 pIn
->addrInTop
= sqlite3VdbeAddOp2(v
, OP_Rowid
, iTab
, iOut
);
589 int iCol
= aiMap
? aiMap
[iMap
++] : 0;
590 pIn
->addrInTop
= sqlite3VdbeAddOp3(v
,OP_Column
,iTab
, iCol
, iOut
);
592 sqlite3VdbeAddOp1(v
, OP_IsNull
, iOut
); VdbeCoverage(v
);
595 pIn
->eEndLoopOp
= bRev
? OP_Prev
: OP_Next
;
597 pIn
->iBase
= iReg
- i
;
599 pLoop
->wsFlags
|= WHERE_IN_EARLYOUT
;
604 pIn
->eEndLoopOp
= OP_Noop
;
610 pLevel
->u
.in
.nIn
= 0;
612 sqlite3DbFree(pParse
->db
, aiMap
);
615 disableTerm(pLevel
, pTerm
);
620 ** Generate code that will evaluate all == and IN constraints for an
623 ** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c).
624 ** Suppose the WHERE clause is this: a==5 AND b IN (1,2,3) AND c>5 AND c<10
625 ** The index has as many as three equality constraints, but in this
626 ** example, the third "c" value is an inequality. So only two
627 ** constraints are coded. This routine will generate code to evaluate
628 ** a==5 and b IN (1,2,3). The current values for a and b will be stored
629 ** in consecutive registers and the index of the first register is returned.
631 ** In the example above nEq==2. But this subroutine works for any value
632 ** of nEq including 0. If nEq==0, this routine is nearly a no-op.
633 ** The only thing it does is allocate the pLevel->iMem memory cell and
634 ** compute the affinity string.
636 ** The nExtraReg parameter is 0 or 1. It is 0 if all WHERE clause constraints
637 ** are == or IN and are covered by the nEq. nExtraReg is 1 if there is
638 ** an inequality constraint (such as the "c>=5 AND c<10" in the example) that
639 ** occurs after the nEq quality constraints.
641 ** This routine allocates a range of nEq+nExtraReg memory cells and returns
642 ** the index of the first memory cell in that range. The code that
643 ** calls this routine will use that memory range to store keys for
644 ** start and termination conditions of the loop.
645 ** key value of the loop. If one or more IN operators appear, then
646 ** this routine allocates an additional nEq memory cells for internal
649 ** Before returning, *pzAff is set to point to a buffer containing a
650 ** copy of the column affinity string of the index allocated using
651 ** sqlite3DbMalloc(). Except, entries in the copy of the string associated
652 ** with equality constraints that use BLOB or NONE affinity are set to
653 ** SQLITE_AFF_BLOB. This is to deal with SQL such as the following:
655 ** CREATE TABLE t1(a TEXT PRIMARY KEY, b);
656 ** SELECT ... FROM t1 AS t2, t1 WHERE t1.a = t2.b;
658 ** In the example above, the index on t1(a) has TEXT affinity. But since
659 ** the right hand side of the equality constraint (t2.b) has BLOB/NONE affinity,
660 ** no conversion should be attempted before using a t2.b value as part of
661 ** a key to search the index. Hence the first byte in the returned affinity
662 ** string in this example would be set to SQLITE_AFF_BLOB.
664 static int codeAllEqualityTerms(
665 Parse
*pParse
, /* Parsing context */
666 WhereLevel
*pLevel
, /* Which nested loop of the FROM we are coding */
667 int bRev
, /* Reverse the order of IN operators */
668 int nExtraReg
, /* Number of extra registers to allocate */
669 char **pzAff
/* OUT: Set to point to affinity string */
671 u16 nEq
; /* The number of == or IN constraints to code */
672 u16 nSkip
; /* Number of left-most columns to skip */
673 Vdbe
*v
= pParse
->pVdbe
; /* The vm under construction */
674 Index
*pIdx
; /* The index being used for this loop */
675 WhereTerm
*pTerm
; /* A single constraint term */
676 WhereLoop
*pLoop
; /* The WhereLoop object */
677 int j
; /* Loop counter */
678 int regBase
; /* Base register */
679 int nReg
; /* Number of registers to allocate */
680 char *zAff
; /* Affinity string to return */
682 /* This module is only called on query plans that use an index. */
683 pLoop
= pLevel
->pWLoop
;
684 assert( (pLoop
->wsFlags
& WHERE_VIRTUALTABLE
)==0 );
685 nEq
= pLoop
->u
.btree
.nEq
;
686 nSkip
= pLoop
->nSkip
;
687 pIdx
= pLoop
->u
.btree
.pIndex
;
690 /* Figure out how many memory cells we will need then allocate them.
692 regBase
= pParse
->nMem
+ 1;
693 nReg
= pLoop
->u
.btree
.nEq
+ nExtraReg
;
694 pParse
->nMem
+= nReg
;
696 zAff
= sqlite3DbStrDup(pParse
->db
,sqlite3IndexAffinityStr(pParse
->db
,pIdx
));
697 assert( zAff
!=0 || pParse
->db
->mallocFailed
);
700 int iIdxCur
= pLevel
->iIdxCur
;
701 sqlite3VdbeAddOp1(v
, (bRev
?OP_Last
:OP_Rewind
), iIdxCur
);
702 VdbeCoverageIf(v
, bRev
==0);
703 VdbeCoverageIf(v
, bRev
!=0);
704 VdbeComment((v
, "begin skip-scan on %s", pIdx
->zName
));
705 j
= sqlite3VdbeAddOp0(v
, OP_Goto
);
706 pLevel
->addrSkip
= sqlite3VdbeAddOp4Int(v
, (bRev
?OP_SeekLT
:OP_SeekGT
),
707 iIdxCur
, 0, regBase
, nSkip
);
708 VdbeCoverageIf(v
, bRev
==0);
709 VdbeCoverageIf(v
, bRev
!=0);
710 sqlite3VdbeJumpHere(v
, j
);
711 for(j
=0; j
<nSkip
; j
++){
712 sqlite3VdbeAddOp3(v
, OP_Column
, iIdxCur
, j
, regBase
+j
);
713 testcase( pIdx
->aiColumn
[j
]==XN_EXPR
);
714 VdbeComment((v
, "%s", explainIndexColumnName(pIdx
, j
)));
718 /* Evaluate the equality constraints
720 assert( zAff
==0 || (int)strlen(zAff
)>=nEq
);
721 for(j
=nSkip
; j
<nEq
; j
++){
723 pTerm
= pLoop
->aLTerm
[j
];
725 /* The following testcase is true for indices with redundant columns.
726 ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */
727 testcase( (pTerm
->wtFlags
& TERM_CODED
)!=0 );
728 testcase( pTerm
->wtFlags
& TERM_VIRTUAL
);
729 r1
= codeEqualityTerm(pParse
, pTerm
, pLevel
, j
, bRev
, regBase
+j
);
732 sqlite3ReleaseTempReg(pParse
, regBase
);
735 sqlite3VdbeAddOp2(v
, OP_SCopy
, r1
, regBase
+j
);
738 if( pTerm
->eOperator
& WO_IN
){
739 if( pTerm
->pExpr
->flags
& EP_xIsSelect
){
740 /* No affinity ever needs to be (or should be) applied to a value
741 ** from the RHS of an "? IN (SELECT ...)" expression. The
742 ** sqlite3FindInIndex() routine has already ensured that the
743 ** affinity of the comparison has been applied to the value. */
744 if( zAff
) zAff
[j
] = SQLITE_AFF_BLOB
;
746 }else if( (pTerm
->eOperator
& WO_ISNULL
)==0 ){
747 Expr
*pRight
= pTerm
->pExpr
->pRight
;
748 if( (pTerm
->wtFlags
& TERM_IS
)==0 && sqlite3ExprCanBeNull(pRight
) ){
749 sqlite3VdbeAddOp2(v
, OP_IsNull
, regBase
+j
, pLevel
->addrBrk
);
753 if( sqlite3CompareAffinity(pRight
, zAff
[j
])==SQLITE_AFF_BLOB
){
754 zAff
[j
] = SQLITE_AFF_BLOB
;
756 if( sqlite3ExprNeedsNoAffinityChange(pRight
, zAff
[j
]) ){
757 zAff
[j
] = SQLITE_AFF_BLOB
;
766 #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
768 ** If the most recently coded instruction is a constant range constraint
769 ** (a string literal) that originated from the LIKE optimization, then
770 ** set P3 and P5 on the OP_String opcode so that the string will be cast
771 ** to a BLOB at appropriate times.
773 ** The LIKE optimization trys to evaluate "x LIKE 'abc%'" as a range
774 ** expression: "x>='ABC' AND x<'abd'". But this requires that the range
775 ** scan loop run twice, once for strings and a second time for BLOBs.
776 ** The OP_String opcodes on the second pass convert the upper and lower
777 ** bound string constants to blobs. This routine makes the necessary changes
778 ** to the OP_String opcodes for that to happen.
780 ** Except, of course, if SQLITE_LIKE_DOESNT_MATCH_BLOBS is defined, then
781 ** only the one pass through the string space is required, so this routine
784 static void whereLikeOptimizationStringFixup(
785 Vdbe
*v
, /* prepared statement under construction */
786 WhereLevel
*pLevel
, /* The loop that contains the LIKE operator */
787 WhereTerm
*pTerm
/* The upper or lower bound just coded */
789 if( pTerm
->wtFlags
& TERM_LIKEOPT
){
791 assert( pLevel
->iLikeRepCntr
>0 );
792 pOp
= sqlite3VdbeGetOp(v
, -1);
794 assert( pOp
->opcode
==OP_String8
795 || pTerm
->pWC
->pWInfo
->pParse
->db
->mallocFailed
);
796 pOp
->p3
= (int)(pLevel
->iLikeRepCntr
>>1); /* Register holding counter */
797 pOp
->p5
= (u8
)(pLevel
->iLikeRepCntr
&1); /* ASC or DESC */
801 # define whereLikeOptimizationStringFixup(A,B,C)
804 #ifdef SQLITE_ENABLE_CURSOR_HINTS
806 ** Information is passed from codeCursorHint() down to individual nodes of
807 ** the expression tree (by sqlite3WalkExpr()) using an instance of this
811 int iTabCur
; /* Cursor for the main table */
812 int iIdxCur
; /* Cursor for the index, if pIdx!=0. Unused otherwise */
813 Index
*pIdx
; /* The index used to access the table */
817 ** This function is called for every node of an expression that is a candidate
818 ** for a cursor hint on an index cursor. For TK_COLUMN nodes that reference
819 ** the table CCurHint.iTabCur, verify that the same column can be
820 ** accessed through the index. If it cannot, then set pWalker->eCode to 1.
822 static int codeCursorHintCheckExpr(Walker
*pWalker
, Expr
*pExpr
){
823 struct CCurHint
*pHint
= pWalker
->u
.pCCurHint
;
824 assert( pHint
->pIdx
!=0 );
825 if( pExpr
->op
==TK_COLUMN
826 && pExpr
->iTable
==pHint
->iTabCur
827 && sqlite3TableColumnToIndex(pHint
->pIdx
, pExpr
->iColumn
)<0
835 ** Test whether or not expression pExpr, which was part of a WHERE clause,
836 ** should be included in the cursor-hint for a table that is on the rhs
837 ** of a LEFT JOIN. Set Walker.eCode to non-zero before returning if the
838 ** expression is not suitable.
840 ** An expression is unsuitable if it might evaluate to non NULL even if
841 ** a TK_COLUMN node that does affect the value of the expression is set
842 ** to NULL. For example:
847 ** CASE WHEN col THEN 0 ELSE 1 END
849 static int codeCursorHintIsOrFunction(Walker
*pWalker
, Expr
*pExpr
){
851 || pExpr
->op
==TK_ISNULL
|| pExpr
->op
==TK_ISNOT
852 || pExpr
->op
==TK_NOTNULL
|| pExpr
->op
==TK_CASE
855 }else if( pExpr
->op
==TK_FUNCTION
){
858 if( 0==sqlite3IsLikeFunction(pWalker
->pParse
->db
, pExpr
, &d1
, d2
) ){
868 ** This function is called on every node of an expression tree used as an
869 ** argument to the OP_CursorHint instruction. If the node is a TK_COLUMN
870 ** that accesses any table other than the one identified by
871 ** CCurHint.iTabCur, then do the following:
873 ** 1) allocate a register and code an OP_Column instruction to read
874 ** the specified column into the new register, and
876 ** 2) transform the expression node to a TK_REGISTER node that reads
877 ** from the newly populated register.
879 ** Also, if the node is a TK_COLUMN that does access the table idenified
880 ** by pCCurHint.iTabCur, and an index is being used (which we will
881 ** know because CCurHint.pIdx!=0) then transform the TK_COLUMN into
882 ** an access of the index rather than the original table.
884 static int codeCursorHintFixExpr(Walker
*pWalker
, Expr
*pExpr
){
885 int rc
= WRC_Continue
;
886 struct CCurHint
*pHint
= pWalker
->u
.pCCurHint
;
887 if( pExpr
->op
==TK_COLUMN
){
888 if( pExpr
->iTable
!=pHint
->iTabCur
){
889 int reg
= ++pWalker
->pParse
->nMem
; /* Register for column value */
890 sqlite3ExprCode(pWalker
->pParse
, pExpr
, reg
);
891 pExpr
->op
= TK_REGISTER
;
893 }else if( pHint
->pIdx
!=0 ){
894 pExpr
->iTable
= pHint
->iIdxCur
;
895 pExpr
->iColumn
= sqlite3TableColumnToIndex(pHint
->pIdx
, pExpr
->iColumn
);
896 assert( pExpr
->iColumn
>=0 );
898 }else if( pExpr
->op
==TK_AGG_FUNCTION
){
899 /* An aggregate function in the WHERE clause of a query means this must
900 ** be a correlated sub-query, and expression pExpr is an aggregate from
901 ** the parent context. Do not walk the function arguments in this case.
903 ** todo: It should be possible to replace this node with a TK_REGISTER
904 ** expression, as the result of the expression must be stored in a
905 ** register at this point. The same holds for TK_AGG_COLUMN nodes. */
912 ** Insert an OP_CursorHint instruction if it is appropriate to do so.
914 static void codeCursorHint(
915 struct SrcList_item
*pTabItem
, /* FROM clause item */
916 WhereInfo
*pWInfo
, /* The where clause */
917 WhereLevel
*pLevel
, /* Which loop to provide hints for */
918 WhereTerm
*pEndRange
/* Hint this end-of-scan boundary term if not NULL */
920 Parse
*pParse
= pWInfo
->pParse
;
921 sqlite3
*db
= pParse
->db
;
922 Vdbe
*v
= pParse
->pVdbe
;
924 WhereLoop
*pLoop
= pLevel
->pWLoop
;
929 struct CCurHint sHint
;
932 if( OptimizationDisabled(db
, SQLITE_CursorHints
) ) return;
933 iCur
= pLevel
->iTabCur
;
934 assert( iCur
==pWInfo
->pTabList
->a
[pLevel
->iFrom
].iCursor
);
935 sHint
.iTabCur
= iCur
;
936 sHint
.iIdxCur
= pLevel
->iIdxCur
;
937 sHint
.pIdx
= pLoop
->u
.btree
.pIndex
;
938 memset(&sWalker
, 0, sizeof(sWalker
));
939 sWalker
.pParse
= pParse
;
940 sWalker
.u
.pCCurHint
= &sHint
;
942 for(i
=0; i
<pWC
->nTerm
; i
++){
944 if( pTerm
->wtFlags
& (TERM_VIRTUAL
|TERM_CODED
) ) continue;
945 if( pTerm
->prereqAll
& pLevel
->notReady
) continue;
947 /* Any terms specified as part of the ON(...) clause for any LEFT
948 ** JOIN for which the current table is not the rhs are omitted
949 ** from the cursor-hint.
951 ** If this table is the rhs of a LEFT JOIN, "IS" or "IS NULL" terms
952 ** that were specified as part of the WHERE clause must be excluded.
953 ** This is to address the following:
955 ** SELECT ... t1 LEFT JOIN t2 ON (t1.a=t2.b) WHERE t2.c IS NULL;
957 ** Say there is a single row in t2 that matches (t1.a=t2.b), but its
958 ** t2.c values is not NULL. If the (t2.c IS NULL) constraint is
959 ** pushed down to the cursor, this row is filtered out, causing
960 ** SQLite to synthesize a row of NULL values. Which does match the
961 ** WHERE clause, and so the query returns a row. Which is incorrect.
963 ** For the same reason, WHERE terms such as:
965 ** WHERE 1 = (t2.c IS NULL)
967 ** are also excluded. See codeCursorHintIsOrFunction() for details.
969 if( pTabItem
->fg
.jointype
& JT_LEFT
){
970 Expr
*pExpr
= pTerm
->pExpr
;
971 if( !ExprHasProperty(pExpr
, EP_FromJoin
)
972 || pExpr
->iRightJoinTable
!=pTabItem
->iCursor
975 sWalker
.xExprCallback
= codeCursorHintIsOrFunction
;
976 sqlite3WalkExpr(&sWalker
, pTerm
->pExpr
);
977 if( sWalker
.eCode
) continue;
980 if( ExprHasProperty(pTerm
->pExpr
, EP_FromJoin
) ) continue;
983 /* All terms in pWLoop->aLTerm[] except pEndRange are used to initialize
984 ** the cursor. These terms are not needed as hints for a pure range
985 ** scan (that has no == terms) so omit them. */
986 if( pLoop
->u
.btree
.nEq
==0 && pTerm
!=pEndRange
){
987 for(j
=0; j
<pLoop
->nLTerm
&& pLoop
->aLTerm
[j
]!=pTerm
; j
++){}
988 if( j
<pLoop
->nLTerm
) continue;
991 /* No subqueries or non-deterministic functions allowed */
992 if( sqlite3ExprContainsSubquery(pTerm
->pExpr
) ) continue;
994 /* For an index scan, make sure referenced columns are actually in
998 sWalker
.xExprCallback
= codeCursorHintCheckExpr
;
999 sqlite3WalkExpr(&sWalker
, pTerm
->pExpr
);
1000 if( sWalker
.eCode
) continue;
1003 /* If we survive all prior tests, that means this term is worth hinting */
1004 pExpr
= sqlite3ExprAnd(pParse
, pExpr
, sqlite3ExprDup(db
, pTerm
->pExpr
, 0));
1007 sWalker
.xExprCallback
= codeCursorHintFixExpr
;
1008 sqlite3WalkExpr(&sWalker
, pExpr
);
1009 sqlite3VdbeAddOp4(v
, OP_CursorHint
,
1010 (sHint
.pIdx
? sHint
.iIdxCur
: sHint
.iTabCur
), 0, 0,
1011 (const char*)pExpr
, P4_EXPR
);
1015 # define codeCursorHint(A,B,C,D) /* No-op */
1016 #endif /* SQLITE_ENABLE_CURSOR_HINTS */
1019 ** Cursor iCur is open on an intkey b-tree (a table). Register iRowid contains
1020 ** a rowid value just read from cursor iIdxCur, open on index pIdx. This
1021 ** function generates code to do a deferred seek of cursor iCur to the
1022 ** rowid stored in register iRowid.
1024 ** Normally, this is just:
1026 ** OP_DeferredSeek $iCur $iRowid
1028 ** However, if the scan currently being coded is a branch of an OR-loop and
1029 ** the statement currently being coded is a SELECT, then P3 of OP_DeferredSeek
1030 ** is set to iIdxCur and P4 is set to point to an array of integers
1031 ** containing one entry for each column of the table cursor iCur is open
1032 ** on. For each table column, if the column is the i'th column of the
1033 ** index, then the corresponding array entry is set to (i+1). If the column
1034 ** does not appear in the index at all, the array entry is set to 0.
1036 static void codeDeferredSeek(
1037 WhereInfo
*pWInfo
, /* Where clause context */
1038 Index
*pIdx
, /* Index scan is using */
1039 int iCur
, /* Cursor for IPK b-tree */
1040 int iIdxCur
/* Index cursor */
1042 Parse
*pParse
= pWInfo
->pParse
; /* Parse context */
1043 Vdbe
*v
= pParse
->pVdbe
; /* Vdbe to generate code within */
1045 assert( iIdxCur
>0 );
1046 assert( pIdx
->aiColumn
[pIdx
->nColumn
-1]==-1 );
1048 pWInfo
->bDeferredSeek
= 1;
1049 sqlite3VdbeAddOp3(v
, OP_DeferredSeek
, iIdxCur
, 0, iCur
);
1050 if( (pWInfo
->wctrlFlags
& WHERE_OR_SUBCLAUSE
)
1051 && DbMaskAllZero(sqlite3ParseToplevel(pParse
)->writeMask
)
1054 Table
*pTab
= pIdx
->pTable
;
1055 int *ai
= (int*)sqlite3DbMallocZero(pParse
->db
, sizeof(int)*(pTab
->nCol
+1));
1058 for(i
=0; i
<pIdx
->nColumn
-1; i
++){
1060 assert( pIdx
->aiColumn
[i
]<pTab
->nCol
);
1061 x1
= pIdx
->aiColumn
[i
];
1062 x2
= sqlite3TableColumnToStorage(pTab
, x1
);
1064 if( x1
>=0 ) ai
[x2
+1] = i
+1;
1066 sqlite3VdbeChangeP4(v
, -1, (char*)ai
, P4_INTARRAY
);
1072 ** If the expression passed as the second argument is a vector, generate
1073 ** code to write the first nReg elements of the vector into an array
1074 ** of registers starting with iReg.
1076 ** If the expression is not a vector, then nReg must be passed 1. In
1077 ** this case, generate code to evaluate the expression and leave the
1078 ** result in register iReg.
1080 static void codeExprOrVector(Parse
*pParse
, Expr
*p
, int iReg
, int nReg
){
1082 if( p
&& sqlite3ExprIsVector(p
) ){
1083 #ifndef SQLITE_OMIT_SUBQUERY
1084 if( (p
->flags
& EP_xIsSelect
) ){
1085 Vdbe
*v
= pParse
->pVdbe
;
1087 assert( p
->op
==TK_SELECT
);
1088 iSelect
= sqlite3CodeSubselect(pParse
, p
);
1089 sqlite3VdbeAddOp3(v
, OP_Copy
, iSelect
, iReg
, nReg
-1);
1094 ExprList
*pList
= p
->x
.pList
;
1095 assert( nReg
<=pList
->nExpr
);
1096 for(i
=0; i
<nReg
; i
++){
1097 sqlite3ExprCode(pParse
, pList
->a
[i
].pExpr
, iReg
+i
);
1102 sqlite3ExprCode(pParse
, p
, iReg
);
1106 /* An instance of the IdxExprTrans object carries information about a
1107 ** mapping from an expression on table columns into a column in an index
1108 ** down through the Walker.
1110 typedef struct IdxExprTrans
{
1111 Expr
*pIdxExpr
; /* The index expression */
1112 int iTabCur
; /* The cursor of the corresponding table */
1113 int iIdxCur
; /* The cursor for the index */
1114 int iIdxCol
; /* The column for the index */
1115 int iTabCol
; /* The column for the table */
1116 WhereInfo
*pWInfo
; /* Complete WHERE clause information */
1117 sqlite3
*db
; /* Database connection (for malloc()) */
1121 ** Preserve pExpr on the WhereETrans list of the WhereInfo.
1123 static void preserveExpr(IdxExprTrans
*pTrans
, Expr
*pExpr
){
1125 pNew
= sqlite3DbMallocRaw(pTrans
->db
, sizeof(*pNew
));
1126 if( pNew
==0 ) return;
1127 pNew
->pNext
= pTrans
->pWInfo
->pExprMods
;
1128 pTrans
->pWInfo
->pExprMods
= pNew
;
1129 pNew
->pExpr
= pExpr
;
1130 memcpy(&pNew
->orig
, pExpr
, sizeof(*pExpr
));
1133 /* The walker node callback used to transform matching expressions into
1134 ** a reference to an index column for an index on an expression.
1136 ** If pExpr matches, then transform it into a reference to the index column
1137 ** that contains the value of pExpr.
1139 static int whereIndexExprTransNode(Walker
*p
, Expr
*pExpr
){
1140 IdxExprTrans
*pX
= p
->u
.pIdxTrans
;
1141 if( sqlite3ExprCompare(0, pExpr
, pX
->pIdxExpr
, pX
->iTabCur
)==0 ){
1142 preserveExpr(pX
, pExpr
);
1143 pExpr
->affExpr
= sqlite3ExprAffinity(pExpr
);
1144 pExpr
->op
= TK_COLUMN
;
1145 pExpr
->iTable
= pX
->iIdxCur
;
1146 pExpr
->iColumn
= pX
->iIdxCol
;
1148 testcase( ExprHasProperty(pExpr
, EP_Skip
) );
1149 testcase( ExprHasProperty(pExpr
, EP_Unlikely
) );
1150 ExprClearProperty(pExpr
, EP_Skip
|EP_Unlikely
);
1153 return WRC_Continue
;
1157 #ifndef SQLITE_OMIT_GENERATED_COLUMNS
1158 /* A walker node callback that translates a column reference to a table
1159 ** into a corresponding column reference of an index.
1161 static int whereIndexExprTransColumn(Walker
*p
, Expr
*pExpr
){
1162 if( pExpr
->op
==TK_COLUMN
){
1163 IdxExprTrans
*pX
= p
->u
.pIdxTrans
;
1164 if( pExpr
->iTable
==pX
->iTabCur
&& pExpr
->iColumn
==pX
->iTabCol
){
1165 assert( pExpr
->y
.pTab
!=0 );
1166 preserveExpr(pX
, pExpr
);
1167 pExpr
->affExpr
= sqlite3TableColumnAffinity(pExpr
->y
.pTab
,pExpr
->iColumn
);
1168 pExpr
->iTable
= pX
->iIdxCur
;
1169 pExpr
->iColumn
= pX
->iIdxCol
;
1173 return WRC_Continue
;
1175 #endif /* SQLITE_OMIT_GENERATED_COLUMNS */
1178 ** For an indexes on expression X, locate every instance of expression X
1179 ** in pExpr and change that subexpression into a reference to the appropriate
1180 ** column of the index.
1182 ** 2019-10-24: Updated to also translate references to a VIRTUAL column in
1183 ** the table into references to the corresponding (stored) column of the
1186 static void whereIndexExprTrans(
1187 Index
*pIdx
, /* The Index */
1188 int iTabCur
, /* Cursor of the table that is being indexed */
1189 int iIdxCur
, /* Cursor of the index itself */
1190 WhereInfo
*pWInfo
/* Transform expressions in this WHERE clause */
1192 int iIdxCol
; /* Column number of the index */
1193 ExprList
*aColExpr
; /* Expressions that are indexed */
1197 aColExpr
= pIdx
->aColExpr
;
1198 if( aColExpr
==0 && !pIdx
->bHasVCol
){
1199 /* The index does not reference any expressions or virtual columns
1200 ** so no translations are needed. */
1203 pTab
= pIdx
->pTable
;
1204 memset(&w
, 0, sizeof(w
));
1206 x
.iTabCur
= iTabCur
;
1207 x
.iIdxCur
= iIdxCur
;
1209 x
.db
= pWInfo
->pParse
->db
;
1210 for(iIdxCol
=0; iIdxCol
<pIdx
->nColumn
; iIdxCol
++){
1211 i16 iRef
= pIdx
->aiColumn
[iIdxCol
];
1212 if( iRef
==XN_EXPR
){
1213 assert( aColExpr
->a
[iIdxCol
].pExpr
!=0 );
1214 x
.pIdxExpr
= aColExpr
->a
[iIdxCol
].pExpr
;
1215 if( sqlite3ExprIsConstant(x
.pIdxExpr
) ) continue;
1216 w
.xExprCallback
= whereIndexExprTransNode
;
1217 #ifndef SQLITE_OMIT_GENERATED_COLUMNS
1219 && (pTab
->aCol
[iRef
].colFlags
& COLFLAG_VIRTUAL
)!=0
1220 && (pTab
->aCol
[iRef
].zColl
==0
1221 || sqlite3StrICmp(pTab
->aCol
[iRef
].zColl
, sqlite3StrBINARY
)==0)
1223 /* Check to see if there are direct references to generated columns
1224 ** that are contained in the index. Pulling the generated column
1225 ** out of the index is an optimization only - the main table is always
1226 ** available if the index cannot be used. To avoid unnecessary
1227 ** complication, omit this optimization if the collating sequence for
1228 ** the column is non-standard */
1230 w
.xExprCallback
= whereIndexExprTransColumn
;
1231 #endif /* SQLITE_OMIT_GENERATED_COLUMNS */
1235 x
.iIdxCol
= iIdxCol
;
1236 sqlite3WalkExpr(&w
, pWInfo
->pWhere
);
1237 sqlite3WalkExprList(&w
, pWInfo
->pOrderBy
);
1238 sqlite3WalkExprList(&w
, pWInfo
->pResultSet
);
1243 ** The pTruth expression is always true because it is the WHERE clause
1244 ** a partial index that is driving a query loop. Look through all of the
1245 ** WHERE clause terms on the query, and if any of those terms must be
1246 ** true because pTruth is true, then mark those WHERE clause terms as
1249 static void whereApplyPartialIndexConstraints(
1256 while( pTruth
->op
==TK_AND
){
1257 whereApplyPartialIndexConstraints(pTruth
->pLeft
, iTabCur
, pWC
);
1258 pTruth
= pTruth
->pRight
;
1260 for(i
=0, pTerm
=pWC
->a
; i
<pWC
->nTerm
; i
++, pTerm
++){
1262 if( pTerm
->wtFlags
& TERM_CODED
) continue;
1263 pExpr
= pTerm
->pExpr
;
1264 if( sqlite3ExprCompare(0, pExpr
, pTruth
, iTabCur
)==0 ){
1265 pTerm
->wtFlags
|= TERM_CODED
;
1271 ** Generate code for the start of the iLevel-th loop in the WHERE clause
1272 ** implementation described by pWInfo.
1274 Bitmask
sqlite3WhereCodeOneLoopStart(
1275 Parse
*pParse
, /* Parsing context */
1276 Vdbe
*v
, /* Prepared statement under construction */
1277 WhereInfo
*pWInfo
, /* Complete information about the WHERE clause */
1278 int iLevel
, /* Which level of pWInfo->a[] should be coded */
1279 WhereLevel
*pLevel
, /* The current level pointer */
1280 Bitmask notReady
/* Which tables are currently available */
1282 int j
, k
; /* Loop counters */
1283 int iCur
; /* The VDBE cursor for the table */
1284 int addrNxt
; /* Where to jump to continue with the next IN case */
1285 int bRev
; /* True if we need to scan in reverse order */
1286 WhereLoop
*pLoop
; /* The WhereLoop object being coded */
1287 WhereClause
*pWC
; /* Decomposition of the entire WHERE clause */
1288 WhereTerm
*pTerm
; /* A WHERE clause term */
1289 sqlite3
*db
; /* Database connection */
1290 struct SrcList_item
*pTabItem
; /* FROM clause term being coded */
1291 int addrBrk
; /* Jump here to break out of the loop */
1292 int addrHalt
; /* addrBrk for the outermost loop */
1293 int addrCont
; /* Jump here to continue with next cycle */
1294 int iRowidReg
= 0; /* Rowid is stored in this register, if not zero */
1295 int iReleaseReg
= 0; /* Temp register to free before returning */
1296 Index
*pIdx
= 0; /* Index used by loop (if any) */
1297 int iLoop
; /* Iteration of constraint generator loop */
1301 pLoop
= pLevel
->pWLoop
;
1302 pTabItem
= &pWInfo
->pTabList
->a
[pLevel
->iFrom
];
1303 iCur
= pTabItem
->iCursor
;
1304 pLevel
->notReady
= notReady
& ~sqlite3WhereGetMask(&pWInfo
->sMaskSet
, iCur
);
1305 bRev
= (pWInfo
->revMask
>>iLevel
)&1;
1306 VdbeModuleComment((v
, "Begin WHERE-loop%d: %s",iLevel
,pTabItem
->pTab
->zName
));
1307 #if WHERETRACE_ENABLED /* 0x20800 */
1308 if( sqlite3WhereTrace
& 0x800 ){
1309 sqlite3DebugPrintf("Coding level %d of %d: notReady=%llx iFrom=%d\n",
1310 iLevel
, pWInfo
->nLevel
, (u64
)notReady
, pLevel
->iFrom
);
1311 sqlite3WhereLoopPrint(pLoop
, pWC
);
1313 if( sqlite3WhereTrace
& 0x20000 ){
1315 sqlite3DebugPrintf("WHERE clause being coded:\n");
1316 sqlite3TreeViewExpr(0, pWInfo
->pWhere
, 0);
1318 sqlite3DebugPrintf("All WHERE-clause terms before coding:\n");
1319 sqlite3WhereClausePrint(pWC
);
1323 /* Create labels for the "break" and "continue" instructions
1324 ** for the current loop. Jump to addrBrk to break out of a loop.
1325 ** Jump to cont to go immediately to the next iteration of the
1328 ** When there is an IN operator, we also have a "addrNxt" label that
1329 ** means to continue with the next IN value combination. When
1330 ** there are no IN operators in the constraints, the "addrNxt" label
1331 ** is the same as "addrBrk".
1333 addrBrk
= pLevel
->addrBrk
= pLevel
->addrNxt
= sqlite3VdbeMakeLabel(pParse
);
1334 addrCont
= pLevel
->addrCont
= sqlite3VdbeMakeLabel(pParse
);
1336 /* If this is the right table of a LEFT OUTER JOIN, allocate and
1337 ** initialize a memory cell that records if this table matches any
1338 ** row of the left table of the join.
1340 assert( (pWInfo
->wctrlFlags
& WHERE_OR_SUBCLAUSE
)
1341 || pLevel
->iFrom
>0 || (pTabItem
[0].fg
.jointype
& JT_LEFT
)==0
1343 if( pLevel
->iFrom
>0 && (pTabItem
[0].fg
.jointype
& JT_LEFT
)!=0 ){
1344 pLevel
->iLeftJoin
= ++pParse
->nMem
;
1345 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, pLevel
->iLeftJoin
);
1346 VdbeComment((v
, "init LEFT JOIN no-match flag"));
1349 /* Compute a safe address to jump to if we discover that the table for
1350 ** this loop is empty and can never contribute content. */
1351 for(j
=iLevel
; j
>0 && pWInfo
->a
[j
].iLeftJoin
==0; j
--){}
1352 addrHalt
= pWInfo
->a
[j
].addrBrk
;
1354 /* Special case of a FROM clause subquery implemented as a co-routine */
1355 if( pTabItem
->fg
.viaCoroutine
){
1356 int regYield
= pTabItem
->regReturn
;
1357 sqlite3VdbeAddOp3(v
, OP_InitCoroutine
, regYield
, 0, pTabItem
->addrFillSub
);
1358 pLevel
->p2
= sqlite3VdbeAddOp2(v
, OP_Yield
, regYield
, addrBrk
);
1360 VdbeComment((v
, "next row of %s", pTabItem
->pTab
->zName
));
1361 pLevel
->op
= OP_Goto
;
1364 #ifndef SQLITE_OMIT_VIRTUALTABLE
1365 if( (pLoop
->wsFlags
& WHERE_VIRTUALTABLE
)!=0 ){
1366 /* Case 1: The table is a virtual-table. Use the VFilter and VNext
1367 ** to access the data.
1369 int iReg
; /* P3 Value for OP_VFilter */
1371 int nConstraint
= pLoop
->nLTerm
;
1372 int iIn
; /* Counter for IN constraints */
1374 iReg
= sqlite3GetTempRange(pParse
, nConstraint
+2);
1375 addrNotFound
= pLevel
->addrBrk
;
1376 for(j
=0; j
<nConstraint
; j
++){
1377 int iTarget
= iReg
+j
+2;
1378 pTerm
= pLoop
->aLTerm
[j
];
1379 if( NEVER(pTerm
==0) ) continue;
1380 if( pTerm
->eOperator
& WO_IN
){
1381 codeEqualityTerm(pParse
, pTerm
, pLevel
, j
, bRev
, iTarget
);
1382 addrNotFound
= pLevel
->addrNxt
;
1384 Expr
*pRight
= pTerm
->pExpr
->pRight
;
1385 codeExprOrVector(pParse
, pRight
, iTarget
, 1);
1388 sqlite3VdbeAddOp2(v
, OP_Integer
, pLoop
->u
.vtab
.idxNum
, iReg
);
1389 sqlite3VdbeAddOp2(v
, OP_Integer
, nConstraint
, iReg
+1);
1390 sqlite3VdbeAddOp4(v
, OP_VFilter
, iCur
, addrNotFound
, iReg
,
1391 pLoop
->u
.vtab
.idxStr
,
1392 pLoop
->u
.vtab
.needFree
? P4_DYNAMIC
: P4_STATIC
);
1394 pLoop
->u
.vtab
.needFree
= 0;
1396 pLevel
->op
= pWInfo
->eOnePass
? OP_Noop
: OP_VNext
;
1397 pLevel
->p2
= sqlite3VdbeCurrentAddr(v
);
1398 iIn
= pLevel
->u
.in
.nIn
;
1399 for(j
=nConstraint
-1; j
>=0; j
--){
1400 pTerm
= pLoop
->aLTerm
[j
];
1401 if( (pTerm
->eOperator
& WO_IN
)!=0 ) iIn
--;
1402 if( j
<16 && (pLoop
->u
.vtab
.omitMask
>>j
)&1 ){
1403 disableTerm(pLevel
, pTerm
);
1404 }else if( (pTerm
->eOperator
& WO_IN
)!=0
1405 && sqlite3ExprVectorSize(pTerm
->pExpr
->pLeft
)==1
1407 Expr
*pCompare
; /* The comparison operator */
1408 Expr
*pRight
; /* RHS of the comparison */
1409 VdbeOp
*pOp
; /* Opcode to access the value of the IN constraint */
1411 /* Reload the constraint value into reg[iReg+j+2]. The same value
1412 ** was loaded into the same register prior to the OP_VFilter, but
1413 ** the xFilter implementation might have changed the datatype or
1414 ** encoding of the value in the register, so it *must* be reloaded. */
1415 assert( pLevel
->u
.in
.aInLoop
!=0 || db
->mallocFailed
);
1416 if( !db
->mallocFailed
){
1417 assert( iIn
>=0 && iIn
<pLevel
->u
.in
.nIn
);
1418 pOp
= sqlite3VdbeGetOp(v
, pLevel
->u
.in
.aInLoop
[iIn
].addrInTop
);
1419 assert( pOp
->opcode
==OP_Column
|| pOp
->opcode
==OP_Rowid
);
1420 assert( pOp
->opcode
!=OP_Column
|| pOp
->p3
==iReg
+j
+2 );
1421 assert( pOp
->opcode
!=OP_Rowid
|| pOp
->p2
==iReg
+j
+2 );
1422 testcase( pOp
->opcode
==OP_Rowid
);
1423 sqlite3VdbeAddOp3(v
, pOp
->opcode
, pOp
->p1
, pOp
->p2
, pOp
->p3
);
1426 /* Generate code that will continue to the next row if
1427 ** the IN constraint is not satisfied */
1428 pCompare
= sqlite3PExpr(pParse
, TK_EQ
, 0, 0);
1429 assert( pCompare
!=0 || db
->mallocFailed
);
1431 pCompare
->pLeft
= pTerm
->pExpr
->pLeft
;
1432 pCompare
->pRight
= pRight
= sqlite3Expr(db
, TK_REGISTER
, 0);
1434 pRight
->iTable
= iReg
+j
+2;
1436 pParse
, pCompare
, pLevel
->addrCont
, SQLITE_JUMPIFNULL
1439 pCompare
->pLeft
= 0;
1440 sqlite3ExprDelete(db
, pCompare
);
1444 assert( iIn
==0 || db
->mallocFailed
);
1445 /* These registers need to be preserved in case there is an IN operator
1446 ** loop. So we could deallocate the registers here (and potentially
1447 ** reuse them later) if (pLoop->wsFlags & WHERE_IN_ABLE)==0. But it seems
1448 ** simpler and safer to simply not reuse the registers.
1450 ** sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2);
1453 #endif /* SQLITE_OMIT_VIRTUALTABLE */
1455 if( (pLoop
->wsFlags
& WHERE_IPK
)!=0
1456 && (pLoop
->wsFlags
& (WHERE_COLUMN_IN
|WHERE_COLUMN_EQ
))!=0
1458 /* Case 2: We can directly reference a single row using an
1459 ** equality comparison against the ROWID field. Or
1460 ** we reference multiple rows using a "rowid IN (...)"
1463 assert( pLoop
->u
.btree
.nEq
==1 );
1464 pTerm
= pLoop
->aLTerm
[0];
1466 assert( pTerm
->pExpr
!=0 );
1467 testcase( pTerm
->wtFlags
& TERM_VIRTUAL
);
1468 iReleaseReg
= ++pParse
->nMem
;
1469 iRowidReg
= codeEqualityTerm(pParse
, pTerm
, pLevel
, 0, bRev
, iReleaseReg
);
1470 if( iRowidReg
!=iReleaseReg
) sqlite3ReleaseTempReg(pParse
, iReleaseReg
);
1471 addrNxt
= pLevel
->addrNxt
;
1472 sqlite3VdbeAddOp3(v
, OP_SeekRowid
, iCur
, addrNxt
, iRowidReg
);
1474 pLevel
->op
= OP_Noop
;
1475 if( (pTerm
->prereqAll
& pLevel
->notReady
)==0 ){
1476 pTerm
->wtFlags
|= TERM_CODED
;
1478 }else if( (pLoop
->wsFlags
& WHERE_IPK
)!=0
1479 && (pLoop
->wsFlags
& WHERE_COLUMN_RANGE
)!=0
1481 /* Case 3: We have an inequality comparison against the ROWID field.
1483 int testOp
= OP_Noop
;
1485 int memEndValue
= 0;
1486 WhereTerm
*pStart
, *pEnd
;
1490 if( pLoop
->wsFlags
& WHERE_BTM_LIMIT
) pStart
= pLoop
->aLTerm
[j
++];
1491 if( pLoop
->wsFlags
& WHERE_TOP_LIMIT
) pEnd
= pLoop
->aLTerm
[j
++];
1492 assert( pStart
!=0 || pEnd
!=0 );
1498 codeCursorHint(pTabItem
, pWInfo
, pLevel
, pEnd
);
1500 Expr
*pX
; /* The expression that defines the start bound */
1501 int r1
, rTemp
; /* Registers for holding the start boundary */
1502 int op
; /* Cursor seek operation */
1504 /* The following constant maps TK_xx codes into corresponding
1505 ** seek opcodes. It depends on a particular ordering of TK_xx
1507 const u8 aMoveOp
[] = {
1508 /* TK_GT */ OP_SeekGT
,
1509 /* TK_LE */ OP_SeekLE
,
1510 /* TK_LT */ OP_SeekLT
,
1511 /* TK_GE */ OP_SeekGE
1513 assert( TK_LE
==TK_GT
+1 ); /* Make sure the ordering.. */
1514 assert( TK_LT
==TK_GT
+2 ); /* ... of the TK_xx values... */
1515 assert( TK_GE
==TK_GT
+3 ); /* ... is correcct. */
1517 assert( (pStart
->wtFlags
& TERM_VNULL
)==0 );
1518 testcase( pStart
->wtFlags
& TERM_VIRTUAL
);
1521 testcase( pStart
->leftCursor
!=iCur
); /* transitive constraints */
1522 if( sqlite3ExprIsVector(pX
->pRight
) ){
1523 r1
= rTemp
= sqlite3GetTempReg(pParse
);
1524 codeExprOrVector(pParse
, pX
->pRight
, r1
, 1);
1525 testcase( pX
->op
==TK_GT
);
1526 testcase( pX
->op
==TK_GE
);
1527 testcase( pX
->op
==TK_LT
);
1528 testcase( pX
->op
==TK_LE
);
1529 op
= aMoveOp
[((pX
->op
- TK_GT
- 1) & 0x3) | 0x1];
1530 assert( pX
->op
!=TK_GT
|| op
==OP_SeekGE
);
1531 assert( pX
->op
!=TK_GE
|| op
==OP_SeekGE
);
1532 assert( pX
->op
!=TK_LT
|| op
==OP_SeekLE
);
1533 assert( pX
->op
!=TK_LE
|| op
==OP_SeekLE
);
1535 r1
= sqlite3ExprCodeTemp(pParse
, pX
->pRight
, &rTemp
);
1536 disableTerm(pLevel
, pStart
);
1537 op
= aMoveOp
[(pX
->op
- TK_GT
)];
1539 sqlite3VdbeAddOp3(v
, op
, iCur
, addrBrk
, r1
);
1540 VdbeComment((v
, "pk"));
1541 VdbeCoverageIf(v
, pX
->op
==TK_GT
);
1542 VdbeCoverageIf(v
, pX
->op
==TK_LE
);
1543 VdbeCoverageIf(v
, pX
->op
==TK_LT
);
1544 VdbeCoverageIf(v
, pX
->op
==TK_GE
);
1545 sqlite3ReleaseTempReg(pParse
, rTemp
);
1547 sqlite3VdbeAddOp2(v
, bRev
? OP_Last
: OP_Rewind
, iCur
, addrHalt
);
1548 VdbeCoverageIf(v
, bRev
==0);
1549 VdbeCoverageIf(v
, bRev
!=0);
1555 assert( (pEnd
->wtFlags
& TERM_VNULL
)==0 );
1556 testcase( pEnd
->leftCursor
!=iCur
); /* Transitive constraints */
1557 testcase( pEnd
->wtFlags
& TERM_VIRTUAL
);
1558 memEndValue
= ++pParse
->nMem
;
1559 codeExprOrVector(pParse
, pX
->pRight
, memEndValue
, 1);
1560 if( 0==sqlite3ExprIsVector(pX
->pRight
)
1561 && (pX
->op
==TK_LT
|| pX
->op
==TK_GT
)
1563 testOp
= bRev
? OP_Le
: OP_Ge
;
1565 testOp
= bRev
? OP_Lt
: OP_Gt
;
1567 if( 0==sqlite3ExprIsVector(pX
->pRight
) ){
1568 disableTerm(pLevel
, pEnd
);
1571 start
= sqlite3VdbeCurrentAddr(v
);
1572 pLevel
->op
= bRev
? OP_Prev
: OP_Next
;
1575 assert( pLevel
->p5
==0 );
1576 if( testOp
!=OP_Noop
){
1577 iRowidReg
= ++pParse
->nMem
;
1578 sqlite3VdbeAddOp2(v
, OP_Rowid
, iCur
, iRowidReg
);
1579 sqlite3VdbeAddOp3(v
, testOp
, memEndValue
, addrBrk
, iRowidReg
);
1580 VdbeCoverageIf(v
, testOp
==OP_Le
);
1581 VdbeCoverageIf(v
, testOp
==OP_Lt
);
1582 VdbeCoverageIf(v
, testOp
==OP_Ge
);
1583 VdbeCoverageIf(v
, testOp
==OP_Gt
);
1584 sqlite3VdbeChangeP5(v
, SQLITE_AFF_NUMERIC
| SQLITE_JUMPIFNULL
);
1586 }else if( pLoop
->wsFlags
& WHERE_INDEXED
){
1587 /* Case 4: A scan using an index.
1589 ** The WHERE clause may contain zero or more equality
1590 ** terms ("==" or "IN" operators) that refer to the N
1591 ** left-most columns of the index. It may also contain
1592 ** inequality constraints (>, <, >= or <=) on the indexed
1593 ** column that immediately follows the N equalities. Only
1594 ** the right-most column can be an inequality - the rest must
1595 ** use the "==" and "IN" operators. For example, if the
1596 ** index is on (x,y,z), then the following clauses are all
1602 ** x=5 AND y>5 AND y<10
1603 ** x=5 AND y=5 AND z<=10
1605 ** The z<10 term of the following cannot be used, only
1610 ** N may be zero if there are inequality constraints.
1611 ** If there are no inequality constraints, then N is at
1614 ** This case is also used when there are no WHERE clause
1615 ** constraints but an index is selected anyway, in order
1616 ** to force the output order to conform to an ORDER BY.
1618 static const u8 aStartOp
[] = {
1621 OP_Rewind
, /* 2: (!start_constraints && startEq && !bRev) */
1622 OP_Last
, /* 3: (!start_constraints && startEq && bRev) */
1623 OP_SeekGT
, /* 4: (start_constraints && !startEq && !bRev) */
1624 OP_SeekLT
, /* 5: (start_constraints && !startEq && bRev) */
1625 OP_SeekGE
, /* 6: (start_constraints && startEq && !bRev) */
1626 OP_SeekLE
/* 7: (start_constraints && startEq && bRev) */
1628 static const u8 aEndOp
[] = {
1629 OP_IdxGE
, /* 0: (end_constraints && !bRev && !endEq) */
1630 OP_IdxGT
, /* 1: (end_constraints && !bRev && endEq) */
1631 OP_IdxLE
, /* 2: (end_constraints && bRev && !endEq) */
1632 OP_IdxLT
, /* 3: (end_constraints && bRev && endEq) */
1634 u16 nEq
= pLoop
->u
.btree
.nEq
; /* Number of == or IN terms */
1635 u16 nBtm
= pLoop
->u
.btree
.nBtm
; /* Length of BTM vector */
1636 u16 nTop
= pLoop
->u
.btree
.nTop
; /* Length of TOP vector */
1637 int regBase
; /* Base register holding constraint values */
1638 WhereTerm
*pRangeStart
= 0; /* Inequality constraint at range start */
1639 WhereTerm
*pRangeEnd
= 0; /* Inequality constraint at range end */
1640 int startEq
; /* True if range start uses ==, >= or <= */
1641 int endEq
; /* True if range end uses ==, >= or <= */
1642 int start_constraints
; /* Start of range is constrained */
1643 int nConstraint
; /* Number of constraint terms */
1644 int iIdxCur
; /* The VDBE cursor for the index */
1645 int nExtraReg
= 0; /* Number of extra registers needed */
1646 int op
; /* Instruction opcode */
1647 char *zStartAff
; /* Affinity for start of range constraint */
1648 char *zEndAff
= 0; /* Affinity for end of range constraint */
1649 u8 bSeekPastNull
= 0; /* True to seek past initial nulls */
1650 u8 bStopAtNull
= 0; /* Add condition to terminate at NULLs */
1651 int omitTable
; /* True if we use the index only */
1652 int regBignull
= 0; /* big-null flag register */
1654 pIdx
= pLoop
->u
.btree
.pIndex
;
1655 iIdxCur
= pLevel
->iIdxCur
;
1656 assert( nEq
>=pLoop
->nSkip
);
1658 /* Find any inequality constraint terms for the start and end
1662 if( pLoop
->wsFlags
& WHERE_BTM_LIMIT
){
1663 pRangeStart
= pLoop
->aLTerm
[j
++];
1664 nExtraReg
= MAX(nExtraReg
, pLoop
->u
.btree
.nBtm
);
1665 /* Like optimization range constraints always occur in pairs */
1666 assert( (pRangeStart
->wtFlags
& TERM_LIKEOPT
)==0 ||
1667 (pLoop
->wsFlags
& WHERE_TOP_LIMIT
)!=0 );
1669 if( pLoop
->wsFlags
& WHERE_TOP_LIMIT
){
1670 pRangeEnd
= pLoop
->aLTerm
[j
++];
1671 nExtraReg
= MAX(nExtraReg
, pLoop
->u
.btree
.nTop
);
1672 #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
1673 if( (pRangeEnd
->wtFlags
& TERM_LIKEOPT
)!=0 ){
1674 assert( pRangeStart
!=0 ); /* LIKE opt constraints */
1675 assert( pRangeStart
->wtFlags
& TERM_LIKEOPT
); /* occur in pairs */
1676 pLevel
->iLikeRepCntr
= (u32
)++pParse
->nMem
;
1677 sqlite3VdbeAddOp2(v
, OP_Integer
, 1, (int)pLevel
->iLikeRepCntr
);
1678 VdbeComment((v
, "LIKE loop counter"));
1679 pLevel
->addrLikeRep
= sqlite3VdbeCurrentAddr(v
);
1680 /* iLikeRepCntr actually stores 2x the counter register number. The
1681 ** bottom bit indicates whether the search order is ASC or DESC. */
1683 testcase( pIdx
->aSortOrder
[nEq
]==SQLITE_SO_DESC
);
1684 assert( (bRev
& ~1)==0 );
1685 pLevel
->iLikeRepCntr
<<=1;
1686 pLevel
->iLikeRepCntr
|= bRev
^ (pIdx
->aSortOrder
[nEq
]==SQLITE_SO_DESC
);
1689 if( pRangeStart
==0 ){
1690 j
= pIdx
->aiColumn
[nEq
];
1691 if( (j
>=0 && pIdx
->pTable
->aCol
[j
].notNull
==0) || j
==XN_EXPR
){
1696 assert( pRangeEnd
==0 || (pRangeEnd
->wtFlags
& TERM_VNULL
)==0 );
1698 /* If the WHERE_BIGNULL_SORT flag is set, then index column nEq uses
1699 ** a non-default "big-null" sort (either ASC NULLS LAST or DESC NULLS
1700 ** FIRST). In both cases separate ordered scans are made of those
1701 ** index entries for which the column is null and for those for which
1702 ** it is not. For an ASC sort, the non-NULL entries are scanned first.
1703 ** For DESC, NULL entries are scanned first.
1705 if( (pLoop
->wsFlags
& (WHERE_TOP_LIMIT
|WHERE_BTM_LIMIT
))==0
1706 && (pLoop
->wsFlags
& WHERE_BIGNULL_SORT
)!=0
1708 assert( bSeekPastNull
==0 && nExtraReg
==0 && nBtm
==0 && nTop
==0 );
1709 assert( pRangeEnd
==0 && pRangeStart
==0 );
1710 testcase( pLoop
->nSkip
>0 );
1713 pLevel
->regBignull
= regBignull
= ++pParse
->nMem
;
1714 pLevel
->addrBignull
= sqlite3VdbeMakeLabel(pParse
);
1717 /* If we are doing a reverse order scan on an ascending index, or
1718 ** a forward order scan on a descending index, interchange the
1719 ** start and end terms (pRangeStart and pRangeEnd).
1721 if( (nEq
<pIdx
->nKeyCol
&& bRev
==(pIdx
->aSortOrder
[nEq
]==SQLITE_SO_ASC
))
1722 || (bRev
&& pIdx
->nKeyCol
==nEq
)
1724 SWAP(WhereTerm
*, pRangeEnd
, pRangeStart
);
1725 SWAP(u8
, bSeekPastNull
, bStopAtNull
);
1726 SWAP(u8
, nBtm
, nTop
);
1729 /* Generate code to evaluate all constraint terms using == or IN
1730 ** and store the values of those terms in an array of registers
1731 ** starting at regBase.
1733 codeCursorHint(pTabItem
, pWInfo
, pLevel
, pRangeEnd
);
1734 regBase
= codeAllEqualityTerms(pParse
,pLevel
,bRev
,nExtraReg
,&zStartAff
);
1735 assert( zStartAff
==0 || sqlite3Strlen30(zStartAff
)>=nEq
);
1736 if( zStartAff
&& nTop
){
1737 zEndAff
= sqlite3DbStrDup(db
, &zStartAff
[nEq
]);
1739 addrNxt
= (regBignull
? pLevel
->addrBignull
: pLevel
->addrNxt
);
1741 testcase( pRangeStart
&& (pRangeStart
->eOperator
& WO_LE
)!=0 );
1742 testcase( pRangeStart
&& (pRangeStart
->eOperator
& WO_GE
)!=0 );
1743 testcase( pRangeEnd
&& (pRangeEnd
->eOperator
& WO_LE
)!=0 );
1744 testcase( pRangeEnd
&& (pRangeEnd
->eOperator
& WO_GE
)!=0 );
1745 startEq
= !pRangeStart
|| pRangeStart
->eOperator
& (WO_LE
|WO_GE
);
1746 endEq
= !pRangeEnd
|| pRangeEnd
->eOperator
& (WO_LE
|WO_GE
);
1747 start_constraints
= pRangeStart
|| nEq
>0;
1749 /* Seek the index cursor to the start of the range. */
1752 Expr
*pRight
= pRangeStart
->pExpr
->pRight
;
1753 codeExprOrVector(pParse
, pRight
, regBase
+nEq
, nBtm
);
1754 whereLikeOptimizationStringFixup(v
, pLevel
, pRangeStart
);
1755 if( (pRangeStart
->wtFlags
& TERM_VNULL
)==0
1756 && sqlite3ExprCanBeNull(pRight
)
1758 sqlite3VdbeAddOp2(v
, OP_IsNull
, regBase
+nEq
, addrNxt
);
1762 updateRangeAffinityStr(pRight
, nBtm
, &zStartAff
[nEq
]);
1764 nConstraint
+= nBtm
;
1765 testcase( pRangeStart
->wtFlags
& TERM_VIRTUAL
);
1766 if( sqlite3ExprIsVector(pRight
)==0 ){
1767 disableTerm(pLevel
, pRangeStart
);
1772 }else if( bSeekPastNull
){
1774 sqlite3VdbeAddOp2(v
, OP_Null
, 0, regBase
+nEq
);
1775 start_constraints
= 1;
1777 }else if( regBignull
){
1778 sqlite3VdbeAddOp2(v
, OP_Null
, 0, regBase
+nEq
);
1779 start_constraints
= 1;
1782 codeApplyAffinity(pParse
, regBase
, nConstraint
- bSeekPastNull
, zStartAff
);
1783 if( pLoop
->nSkip
>0 && nConstraint
==pLoop
->nSkip
){
1784 /* The skip-scan logic inside the call to codeAllEqualityConstraints()
1785 ** above has already left the cursor sitting on the correct row,
1786 ** so no further seeking is needed */
1788 if( pLoop
->wsFlags
& WHERE_IN_EARLYOUT
){
1789 sqlite3VdbeAddOp1(v
, OP_SeekHit
, iIdxCur
);
1792 sqlite3VdbeAddOp2(v
, OP_Integer
, 1, regBignull
);
1793 VdbeComment((v
, "NULL-scan pass ctr"));
1796 op
= aStartOp
[(start_constraints
<<2) + (startEq
<<1) + bRev
];
1798 sqlite3VdbeAddOp4Int(v
, op
, iIdxCur
, addrNxt
, regBase
, nConstraint
);
1800 VdbeCoverageIf(v
, op
==OP_Rewind
); testcase( op
==OP_Rewind
);
1801 VdbeCoverageIf(v
, op
==OP_Last
); testcase( op
==OP_Last
);
1802 VdbeCoverageIf(v
, op
==OP_SeekGT
); testcase( op
==OP_SeekGT
);
1803 VdbeCoverageIf(v
, op
==OP_SeekGE
); testcase( op
==OP_SeekGE
);
1804 VdbeCoverageIf(v
, op
==OP_SeekLE
); testcase( op
==OP_SeekLE
);
1805 VdbeCoverageIf(v
, op
==OP_SeekLT
); testcase( op
==OP_SeekLT
);
1807 assert( bSeekPastNull
==0 || bStopAtNull
==0 );
1809 assert( bSeekPastNull
==1 || bStopAtNull
==1 );
1810 assert( bSeekPastNull
==!bStopAtNull
);
1811 assert( bStopAtNull
==startEq
);
1812 sqlite3VdbeAddOp2(v
, OP_Goto
, 0, sqlite3VdbeCurrentAddr(v
)+2);
1813 op
= aStartOp
[(nConstraint
>1)*4 + 2 + bRev
];
1814 sqlite3VdbeAddOp4Int(v
, op
, iIdxCur
, addrNxt
, regBase
,
1815 nConstraint
-startEq
);
1817 VdbeCoverageIf(v
, op
==OP_Rewind
); testcase( op
==OP_Rewind
);
1818 VdbeCoverageIf(v
, op
==OP_Last
); testcase( op
==OP_Last
);
1819 VdbeCoverageIf(v
, op
==OP_SeekGE
); testcase( op
==OP_SeekGE
);
1820 VdbeCoverageIf(v
, op
==OP_SeekLE
); testcase( op
==OP_SeekLE
);
1821 assert( op
==OP_Rewind
|| op
==OP_Last
|| op
==OP_SeekGE
|| op
==OP_SeekLE
);
1825 /* Load the value for the inequality constraint at the end of the
1830 Expr
*pRight
= pRangeEnd
->pExpr
->pRight
;
1831 codeExprOrVector(pParse
, pRight
, regBase
+nEq
, nTop
);
1832 whereLikeOptimizationStringFixup(v
, pLevel
, pRangeEnd
);
1833 if( (pRangeEnd
->wtFlags
& TERM_VNULL
)==0
1834 && sqlite3ExprCanBeNull(pRight
)
1836 sqlite3VdbeAddOp2(v
, OP_IsNull
, regBase
+nEq
, addrNxt
);
1840 updateRangeAffinityStr(pRight
, nTop
, zEndAff
);
1841 codeApplyAffinity(pParse
, regBase
+nEq
, nTop
, zEndAff
);
1843 assert( pParse
->db
->mallocFailed
);
1845 nConstraint
+= nTop
;
1846 testcase( pRangeEnd
->wtFlags
& TERM_VIRTUAL
);
1848 if( sqlite3ExprIsVector(pRight
)==0 ){
1849 disableTerm(pLevel
, pRangeEnd
);
1853 }else if( bStopAtNull
){
1854 if( regBignull
==0 ){
1855 sqlite3VdbeAddOp2(v
, OP_Null
, 0, regBase
+nEq
);
1860 sqlite3DbFree(db
, zStartAff
);
1861 sqlite3DbFree(db
, zEndAff
);
1863 /* Top of the loop body */
1864 pLevel
->p2
= sqlite3VdbeCurrentAddr(v
);
1866 /* Check if the index cursor is past the end of the range. */
1869 /* Except, skip the end-of-range check while doing the NULL-scan */
1870 sqlite3VdbeAddOp2(v
, OP_IfNot
, regBignull
, sqlite3VdbeCurrentAddr(v
)+3);
1871 VdbeComment((v
, "If NULL-scan 2nd pass"));
1874 op
= aEndOp
[bRev
*2 + endEq
];
1875 sqlite3VdbeAddOp4Int(v
, op
, iIdxCur
, addrNxt
, regBase
, nConstraint
);
1876 testcase( op
==OP_IdxGT
); VdbeCoverageIf(v
, op
==OP_IdxGT
);
1877 testcase( op
==OP_IdxGE
); VdbeCoverageIf(v
, op
==OP_IdxGE
);
1878 testcase( op
==OP_IdxLT
); VdbeCoverageIf(v
, op
==OP_IdxLT
);
1879 testcase( op
==OP_IdxLE
); VdbeCoverageIf(v
, op
==OP_IdxLE
);
1882 /* During a NULL-scan, check to see if we have reached the end of
1884 assert( bSeekPastNull
==!bStopAtNull
);
1885 assert( bSeekPastNull
+bStopAtNull
==1 );
1886 assert( nConstraint
+bSeekPastNull
>0 );
1887 sqlite3VdbeAddOp2(v
, OP_If
, regBignull
, sqlite3VdbeCurrentAddr(v
)+2);
1888 VdbeComment((v
, "If NULL-scan 1st pass"));
1890 op
= aEndOp
[bRev
*2 + bSeekPastNull
];
1891 sqlite3VdbeAddOp4Int(v
, op
, iIdxCur
, addrNxt
, regBase
,
1892 nConstraint
+bSeekPastNull
);
1893 testcase( op
==OP_IdxGT
); VdbeCoverageIf(v
, op
==OP_IdxGT
);
1894 testcase( op
==OP_IdxGE
); VdbeCoverageIf(v
, op
==OP_IdxGE
);
1895 testcase( op
==OP_IdxLT
); VdbeCoverageIf(v
, op
==OP_IdxLT
);
1896 testcase( op
==OP_IdxLE
); VdbeCoverageIf(v
, op
==OP_IdxLE
);
1899 if( pLoop
->wsFlags
& WHERE_IN_EARLYOUT
){
1900 sqlite3VdbeAddOp2(v
, OP_SeekHit
, iIdxCur
, 1);
1903 /* Seek the table cursor, if required */
1904 omitTable
= (pLoop
->wsFlags
& WHERE_IDX_ONLY
)!=0
1905 && (pWInfo
->wctrlFlags
& WHERE_OR_SUBCLAUSE
)==0;
1907 /* pIdx is a covering index. No need to access the main table. */
1908 }else if( HasRowid(pIdx
->pTable
) ){
1909 if( (pWInfo
->wctrlFlags
& WHERE_SEEK_TABLE
)
1910 || ( (pWInfo
->wctrlFlags
& WHERE_SEEK_UNIQ_TABLE
)!=0
1911 && (pWInfo
->eOnePass
==ONEPASS_SINGLE
|| pLoop
->nLTerm
==0) )
1913 iRowidReg
= ++pParse
->nMem
;
1914 sqlite3VdbeAddOp2(v
, OP_IdxRowid
, iIdxCur
, iRowidReg
);
1915 sqlite3VdbeAddOp3(v
, OP_NotExists
, iCur
, 0, iRowidReg
);
1918 codeDeferredSeek(pWInfo
, pIdx
, iCur
, iIdxCur
);
1920 }else if( iCur
!=iIdxCur
){
1921 Index
*pPk
= sqlite3PrimaryKeyIndex(pIdx
->pTable
);
1922 iRowidReg
= sqlite3GetTempRange(pParse
, pPk
->nKeyCol
);
1923 for(j
=0; j
<pPk
->nKeyCol
; j
++){
1924 k
= sqlite3TableColumnToIndex(pIdx
, pPk
->aiColumn
[j
]);
1925 sqlite3VdbeAddOp3(v
, OP_Column
, iIdxCur
, k
, iRowidReg
+j
);
1927 sqlite3VdbeAddOp4Int(v
, OP_NotFound
, iCur
, addrCont
,
1928 iRowidReg
, pPk
->nKeyCol
); VdbeCoverage(v
);
1931 if( pLevel
->iLeftJoin
==0 ){
1932 /* If pIdx is an index on one or more expressions, then look through
1933 ** all the expressions in pWInfo and try to transform matching expressions
1934 ** into reference to index columns. Also attempt to translate references
1935 ** to virtual columns in the table into references to (stored) columns
1938 ** Do not do this for the RHS of a LEFT JOIN. This is because the
1939 ** expression may be evaluated after OP_NullRow has been executed on
1940 ** the cursor. In this case it is important to do the full evaluation,
1941 ** as the result of the expression may not be NULL, even if all table
1942 ** column values are. https://www.sqlite.org/src/info/7fa8049685b50b5a
1944 ** Also, do not do this when processing one index an a multi-index
1945 ** OR clause, since the transformation will become invalid once we
1946 ** move forward to the next index.
1947 ** https://sqlite.org/src/info/4e8e4857d32d401f
1949 if( (pWInfo
->wctrlFlags
& WHERE_OR_SUBCLAUSE
)==0 ){
1950 whereIndexExprTrans(pIdx
, iCur
, iIdxCur
, pWInfo
);
1953 /* If a partial index is driving the loop, try to eliminate WHERE clause
1954 ** terms from the query that must be true due to the WHERE clause of
1955 ** the partial index.
1957 ** 2019-11-02 ticket 623eff57e76d45f6: This optimization does not work
1960 if( pIdx
->pPartIdxWhere
){
1961 whereApplyPartialIndexConstraints(pIdx
->pPartIdxWhere
, iCur
, pWC
);
1964 testcase( pIdx
->pPartIdxWhere
);
1965 /* The following assert() is not a requirement, merely an observation:
1966 ** The OR-optimization doesn't work for the right hand table of
1968 assert( (pWInfo
->wctrlFlags
& WHERE_OR_SUBCLAUSE
)==0 );
1971 /* Record the instruction used to terminate the loop. */
1972 if( pLoop
->wsFlags
& WHERE_ONEROW
){
1973 pLevel
->op
= OP_Noop
;
1975 pLevel
->op
= OP_Prev
;
1977 pLevel
->op
= OP_Next
;
1979 pLevel
->p1
= iIdxCur
;
1980 pLevel
->p3
= (pLoop
->wsFlags
&WHERE_UNQ_WANTED
)!=0 ? 1:0;
1981 if( (pLoop
->wsFlags
& WHERE_CONSTRAINT
)==0 ){
1982 pLevel
->p5
= SQLITE_STMTSTATUS_FULLSCAN_STEP
;
1984 assert( pLevel
->p5
==0 );
1986 if( omitTable
) pIdx
= 0;
1989 #ifndef SQLITE_OMIT_OR_OPTIMIZATION
1990 if( pLoop
->wsFlags
& WHERE_MULTI_OR
){
1991 /* Case 5: Two or more separately indexed terms connected by OR
1995 ** CREATE TABLE t1(a,b,c,d);
1996 ** CREATE INDEX i1 ON t1(a);
1997 ** CREATE INDEX i2 ON t1(b);
1998 ** CREATE INDEX i3 ON t1(c);
2000 ** SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
2002 ** In the example, there are three indexed terms connected by OR.
2003 ** The top of the loop looks like this:
2005 ** Null 1 # Zero the rowset in reg 1
2007 ** Then, for each indexed term, the following. The arguments to
2008 ** RowSetTest are such that the rowid of the current row is inserted
2009 ** into the RowSet. If it is already present, control skips the
2010 ** Gosub opcode and jumps straight to the code generated by WhereEnd().
2012 ** sqlite3WhereBegin(<term>)
2013 ** RowSetTest # Insert rowid into rowset
2015 ** sqlite3WhereEnd()
2017 ** Following the above, code to terminate the loop. Label A, the target
2018 ** of the Gosub above, jumps to the instruction right after the Goto.
2020 ** Null 1 # Zero the rowset in reg 1
2021 ** Goto B # The loop is finished.
2023 ** A: <loop body> # Return data, whatever.
2025 ** Return 2 # Jump back to the Gosub
2027 ** B: <after the loop>
2029 ** Added 2014-05-26: If the table is a WITHOUT ROWID table, then
2030 ** use an ephemeral index instead of a RowSet to record the primary
2031 ** keys of the rows we have already seen.
2034 WhereClause
*pOrWc
; /* The OR-clause broken out into subterms */
2035 SrcList
*pOrTab
; /* Shortened table list or OR-clause generation */
2036 Index
*pCov
= 0; /* Potential covering index (or NULL) */
2037 int iCovCur
= pParse
->nTab
++; /* Cursor used for index scans (if any) */
2039 int regReturn
= ++pParse
->nMem
; /* Register used with OP_Gosub */
2040 int regRowset
= 0; /* Register for RowSet object */
2041 int regRowid
= 0; /* Register holding rowid */
2042 int iLoopBody
= sqlite3VdbeMakeLabel(pParse
);/* Start of loop body */
2043 int iRetInit
; /* Address of regReturn init */
2044 int untestedTerms
= 0; /* Some terms not completely tested */
2045 int ii
; /* Loop counter */
2046 u16 wctrlFlags
; /* Flags for sub-WHERE clause */
2047 Expr
*pAndExpr
= 0; /* An ".. AND (...)" expression */
2048 Table
*pTab
= pTabItem
->pTab
;
2050 pTerm
= pLoop
->aLTerm
[0];
2052 assert( pTerm
->eOperator
& WO_OR
);
2053 assert( (pTerm
->wtFlags
& TERM_ORINFO
)!=0 );
2054 pOrWc
= &pTerm
->u
.pOrInfo
->wc
;
2055 pLevel
->op
= OP_Return
;
2056 pLevel
->p1
= regReturn
;
2058 /* Set up a new SrcList in pOrTab containing the table being scanned
2059 ** by this loop in the a[0] slot and all notReady tables in a[1..] slots.
2060 ** This becomes the SrcList in the recursive call to sqlite3WhereBegin().
2062 if( pWInfo
->nLevel
>1 ){
2063 int nNotReady
; /* The number of notReady tables */
2064 struct SrcList_item
*origSrc
; /* Original list of tables */
2065 nNotReady
= pWInfo
->nLevel
- iLevel
- 1;
2066 pOrTab
= sqlite3StackAllocRaw(db
,
2067 sizeof(*pOrTab
)+ nNotReady
*sizeof(pOrTab
->a
[0]));
2068 if( pOrTab
==0 ) return notReady
;
2069 pOrTab
->nAlloc
= (u8
)(nNotReady
+ 1);
2070 pOrTab
->nSrc
= pOrTab
->nAlloc
;
2071 memcpy(pOrTab
->a
, pTabItem
, sizeof(*pTabItem
));
2072 origSrc
= pWInfo
->pTabList
->a
;
2073 for(k
=1; k
<=nNotReady
; k
++){
2074 memcpy(&pOrTab
->a
[k
], &origSrc
[pLevel
[k
].iFrom
], sizeof(pOrTab
->a
[k
]));
2077 pOrTab
= pWInfo
->pTabList
;
2080 /* Initialize the rowset register to contain NULL. An SQL NULL is
2081 ** equivalent to an empty rowset. Or, create an ephemeral index
2082 ** capable of holding primary keys in the case of a WITHOUT ROWID.
2084 ** Also initialize regReturn to contain the address of the instruction
2085 ** immediately following the OP_Return at the bottom of the loop. This
2086 ** is required in a few obscure LEFT JOIN cases where control jumps
2087 ** over the top of the loop into the body of it. In this case the
2088 ** correct response for the end-of-loop code (the OP_Return) is to
2089 ** fall through to the next instruction, just as an OP_Next does if
2090 ** called on an uninitialized cursor.
2092 if( (pWInfo
->wctrlFlags
& WHERE_DUPLICATES_OK
)==0 ){
2093 if( HasRowid(pTab
) ){
2094 regRowset
= ++pParse
->nMem
;
2095 sqlite3VdbeAddOp2(v
, OP_Null
, 0, regRowset
);
2097 Index
*pPk
= sqlite3PrimaryKeyIndex(pTab
);
2098 regRowset
= pParse
->nTab
++;
2099 sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, regRowset
, pPk
->nKeyCol
);
2100 sqlite3VdbeSetP4KeyInfo(pParse
, pPk
);
2102 regRowid
= ++pParse
->nMem
;
2104 iRetInit
= sqlite3VdbeAddOp2(v
, OP_Integer
, 0, regReturn
);
2106 /* If the original WHERE clause is z of the form: (x1 OR x2 OR ...) AND y
2107 ** Then for every term xN, evaluate as the subexpression: xN AND z
2108 ** That way, terms in y that are factored into the disjunction will
2109 ** be picked up by the recursive calls to sqlite3WhereBegin() below.
2111 ** Actually, each subexpression is converted to "xN AND w" where w is
2112 ** the "interesting" terms of z - terms that did not originate in the
2113 ** ON or USING clause of a LEFT JOIN, and terms that are usable as
2116 ** This optimization also only applies if the (x1 OR x2 OR ...) term
2117 ** is not contained in the ON clause of a LEFT JOIN.
2118 ** See ticket http://www.sqlite.org/src/info/f2369304e4
2122 for(iTerm
=0; iTerm
<pWC
->nTerm
; iTerm
++){
2123 Expr
*pExpr
= pWC
->a
[iTerm
].pExpr
;
2124 if( &pWC
->a
[iTerm
] == pTerm
) continue;
2125 testcase( pWC
->a
[iTerm
].wtFlags
& TERM_VIRTUAL
);
2126 testcase( pWC
->a
[iTerm
].wtFlags
& TERM_CODED
);
2127 if( (pWC
->a
[iTerm
].wtFlags
& (TERM_VIRTUAL
|TERM_CODED
))!=0 ) continue;
2128 if( (pWC
->a
[iTerm
].eOperator
& WO_ALL
)==0 ) continue;
2129 testcase( pWC
->a
[iTerm
].wtFlags
& TERM_ORINFO
);
2130 pExpr
= sqlite3ExprDup(db
, pExpr
, 0);
2131 pAndExpr
= sqlite3ExprAnd(pParse
, pAndExpr
, pExpr
);
2134 /* The extra 0x10000 bit on the opcode is masked off and does not
2135 ** become part of the new Expr.op. However, it does make the
2136 ** op==TK_AND comparison inside of sqlite3PExpr() false, and this
2137 ** prevents sqlite3PExpr() from implementing AND short-circuit
2138 ** optimization, which we do not want here. */
2139 pAndExpr
= sqlite3PExpr(pParse
, TK_AND
|0x10000, 0, pAndExpr
);
2143 /* Run a separate WHERE clause for each term of the OR clause. After
2144 ** eliminating duplicates from other WHERE clauses, the action for each
2145 ** sub-WHERE clause is to to invoke the main loop body as a subroutine.
2147 wctrlFlags
= WHERE_OR_SUBCLAUSE
| (pWInfo
->wctrlFlags
& WHERE_SEEK_TABLE
);
2148 ExplainQueryPlan((pParse
, 1, "MULTI-INDEX OR"));
2149 for(ii
=0; ii
<pOrWc
->nTerm
; ii
++){
2150 WhereTerm
*pOrTerm
= &pOrWc
->a
[ii
];
2151 if( pOrTerm
->leftCursor
==iCur
|| (pOrTerm
->eOperator
& WO_AND
)!=0 ){
2152 WhereInfo
*pSubWInfo
; /* Info for single OR-term scan */
2153 Expr
*pOrExpr
= pOrTerm
->pExpr
; /* Current OR clause term */
2154 int jmp1
= 0; /* Address of jump operation */
2155 testcase( (pTabItem
[0].fg
.jointype
& JT_LEFT
)!=0
2156 && !ExprHasProperty(pOrExpr
, EP_FromJoin
)
2157 ); /* See TH3 vtab25.400 and ticket 614b25314c766238 */
2159 pAndExpr
->pLeft
= pOrExpr
;
2162 /* Loop through table entries that match term pOrTerm. */
2163 ExplainQueryPlan((pParse
, 1, "INDEX %d", ii
+1));
2164 WHERETRACE(0xffff, ("Subplan for OR-clause:\n"));
2165 pSubWInfo
= sqlite3WhereBegin(pParse
, pOrTab
, pOrExpr
, 0, 0,
2166 wctrlFlags
, iCovCur
);
2167 assert( pSubWInfo
|| pParse
->nErr
|| db
->mallocFailed
);
2169 WhereLoop
*pSubLoop
;
2170 int addrExplain
= sqlite3WhereExplainOneScan(
2171 pParse
, pOrTab
, &pSubWInfo
->a
[0], 0
2173 sqlite3WhereAddScanStatus(v
, pOrTab
, &pSubWInfo
->a
[0], addrExplain
);
2175 /* This is the sub-WHERE clause body. First skip over
2176 ** duplicate rows from prior sub-WHERE clauses, and record the
2177 ** rowid (or PRIMARY KEY) for the current row so that the same
2178 ** row will be skipped in subsequent sub-WHERE clauses.
2180 if( (pWInfo
->wctrlFlags
& WHERE_DUPLICATES_OK
)==0 ){
2181 int iSet
= ((ii
==pOrWc
->nTerm
-1)?-1:ii
);
2182 if( HasRowid(pTab
) ){
2183 sqlite3ExprCodeGetColumnOfTable(v
, pTab
, iCur
, -1, regRowid
);
2184 jmp1
= sqlite3VdbeAddOp4Int(v
, OP_RowSetTest
, regRowset
, 0,
2188 Index
*pPk
= sqlite3PrimaryKeyIndex(pTab
);
2189 int nPk
= pPk
->nKeyCol
;
2193 /* Read the PK into an array of temp registers. */
2194 r
= sqlite3GetTempRange(pParse
, nPk
);
2195 for(iPk
=0; iPk
<nPk
; iPk
++){
2196 int iCol
= pPk
->aiColumn
[iPk
];
2197 sqlite3ExprCodeGetColumnOfTable(v
, pTab
, iCur
, iCol
,r
+iPk
);
2200 /* Check if the temp table already contains this key. If so,
2201 ** the row has already been included in the result set and
2202 ** can be ignored (by jumping past the Gosub below). Otherwise,
2203 ** insert the key into the temp table and proceed with processing
2206 ** Use some of the same optimizations as OP_RowSetTest: If iSet
2207 ** is zero, assume that the key cannot already be present in
2208 ** the temp table. And if iSet is -1, assume that there is no
2209 ** need to insert the key into the temp table, as it will never
2210 ** be tested for. */
2212 jmp1
= sqlite3VdbeAddOp4Int(v
, OP_Found
, regRowset
, 0, r
, nPk
);
2216 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, r
, nPk
, regRowid
);
2217 sqlite3VdbeAddOp4Int(v
, OP_IdxInsert
, regRowset
, regRowid
,
2219 if( iSet
) sqlite3VdbeChangeP5(v
, OPFLAG_USESEEKRESULT
);
2222 /* Release the array of temp registers */
2223 sqlite3ReleaseTempRange(pParse
, r
, nPk
);
2227 /* Invoke the main loop body as a subroutine */
2228 sqlite3VdbeAddOp2(v
, OP_Gosub
, regReturn
, iLoopBody
);
2230 /* Jump here (skipping the main loop body subroutine) if the
2231 ** current sub-WHERE row is a duplicate from prior sub-WHEREs. */
2232 if( jmp1
) sqlite3VdbeJumpHere(v
, jmp1
);
2234 /* The pSubWInfo->untestedTerms flag means that this OR term
2235 ** contained one or more AND term from a notReady table. The
2236 ** terms from the notReady table could not be tested and will
2237 ** need to be tested later.
2239 if( pSubWInfo
->untestedTerms
) untestedTerms
= 1;
2241 /* If all of the OR-connected terms are optimized using the same
2242 ** index, and the index is opened using the same cursor number
2243 ** by each call to sqlite3WhereBegin() made by this loop, it may
2244 ** be possible to use that index as a covering index.
2246 ** If the call to sqlite3WhereBegin() above resulted in a scan that
2247 ** uses an index, and this is either the first OR-connected term
2248 ** processed or the index is the same as that used by all previous
2249 ** terms, set pCov to the candidate covering index. Otherwise, set
2250 ** pCov to NULL to indicate that no candidate covering index will
2253 pSubLoop
= pSubWInfo
->a
[0].pWLoop
;
2254 assert( (pSubLoop
->wsFlags
& WHERE_AUTO_INDEX
)==0 );
2255 if( (pSubLoop
->wsFlags
& WHERE_INDEXED
)!=0
2256 && (ii
==0 || pSubLoop
->u
.btree
.pIndex
==pCov
)
2257 && (HasRowid(pTab
) || !IsPrimaryKeyIndex(pSubLoop
->u
.btree
.pIndex
))
2259 assert( pSubWInfo
->a
[0].iIdxCur
==iCovCur
);
2260 pCov
= pSubLoop
->u
.btree
.pIndex
;
2265 /* Finish the loop through table entries that match term pOrTerm. */
2266 sqlite3WhereEnd(pSubWInfo
);
2267 ExplainQueryPlanPop(pParse
);
2271 ExplainQueryPlanPop(pParse
);
2272 pLevel
->u
.pCovidx
= pCov
;
2273 if( pCov
) pLevel
->iIdxCur
= iCovCur
;
2275 pAndExpr
->pLeft
= 0;
2276 sqlite3ExprDelete(db
, pAndExpr
);
2278 sqlite3VdbeChangeP1(v
, iRetInit
, sqlite3VdbeCurrentAddr(v
));
2279 sqlite3VdbeGoto(v
, pLevel
->addrBrk
);
2280 sqlite3VdbeResolveLabel(v
, iLoopBody
);
2282 if( pWInfo
->nLevel
>1 ){ sqlite3StackFree(db
, pOrTab
); }
2283 if( !untestedTerms
) disableTerm(pLevel
, pTerm
);
2285 #endif /* SQLITE_OMIT_OR_OPTIMIZATION */
2288 /* Case 6: There is no usable index. We must do a complete
2289 ** scan of the entire table.
2291 static const u8 aStep
[] = { OP_Next
, OP_Prev
};
2292 static const u8 aStart
[] = { OP_Rewind
, OP_Last
};
2293 assert( bRev
==0 || bRev
==1 );
2294 if( pTabItem
->fg
.isRecursive
){
2295 /* Tables marked isRecursive have only a single row that is stored in
2296 ** a pseudo-cursor. No need to Rewind or Next such cursors. */
2297 pLevel
->op
= OP_Noop
;
2299 codeCursorHint(pTabItem
, pWInfo
, pLevel
, 0);
2300 pLevel
->op
= aStep
[bRev
];
2302 pLevel
->p2
= 1 + sqlite3VdbeAddOp2(v
, aStart
[bRev
], iCur
, addrHalt
);
2303 VdbeCoverageIf(v
, bRev
==0);
2304 VdbeCoverageIf(v
, bRev
!=0);
2305 pLevel
->p5
= SQLITE_STMTSTATUS_FULLSCAN_STEP
;
2309 #ifdef SQLITE_ENABLE_STMT_SCANSTATUS
2310 pLevel
->addrVisit
= sqlite3VdbeCurrentAddr(v
);
2313 /* Insert code to test every subexpression that can be completely
2314 ** computed using the current set of tables.
2316 ** This loop may run between one and three times, depending on the
2317 ** constraints to be generated. The value of stack variable iLoop
2318 ** determines the constraints coded by each iteration, as follows:
2320 ** iLoop==1: Code only expressions that are entirely covered by pIdx.
2321 ** iLoop==2: Code remaining expressions that do not contain correlated
2323 ** iLoop==3: Code all remaining expressions.
2325 ** An effort is made to skip unnecessary iterations of the loop.
2327 iLoop
= (pIdx
? 1 : 2);
2329 int iNext
= 0; /* Next value for iLoop */
2330 for(pTerm
=pWC
->a
, j
=pWC
->nTerm
; j
>0; j
--, pTerm
++){
2332 int skipLikeAddr
= 0;
2333 testcase( pTerm
->wtFlags
& TERM_VIRTUAL
);
2334 testcase( pTerm
->wtFlags
& TERM_CODED
);
2335 if( pTerm
->wtFlags
& (TERM_VIRTUAL
|TERM_CODED
) ) continue;
2336 if( (pTerm
->prereqAll
& pLevel
->notReady
)!=0 ){
2337 testcase( pWInfo
->untestedTerms
==0
2338 && (pWInfo
->wctrlFlags
& WHERE_OR_SUBCLAUSE
)!=0 );
2339 pWInfo
->untestedTerms
= 1;
2344 if( (pTabItem
->fg
.jointype
&JT_LEFT
) && !ExprHasProperty(pE
,EP_FromJoin
) ){
2348 if( iLoop
==1 && !sqlite3ExprCoveredByIndex(pE
, pLevel
->iTabCur
, pIdx
) ){
2352 if( iLoop
<3 && (pTerm
->wtFlags
& TERM_VARSELECT
) ){
2353 if( iNext
==0 ) iNext
= 3;
2357 if( (pTerm
->wtFlags
& TERM_LIKECOND
)!=0 ){
2358 /* If the TERM_LIKECOND flag is set, that means that the range search
2359 ** is sufficient to guarantee that the LIKE operator is true, so we
2360 ** can skip the call to the like(A,B) function. But this only works
2361 ** for strings. So do not skip the call to the function on the pass
2362 ** that compares BLOBs. */
2363 #ifdef SQLITE_LIKE_DOESNT_MATCH_BLOBS
2366 u32 x
= pLevel
->iLikeRepCntr
;
2368 skipLikeAddr
= sqlite3VdbeAddOp1(v
, (x
&1)?OP_IfNot
:OP_If
,(int)(x
>>1));
2369 VdbeCoverageIf(v
, (x
&1)==1);
2370 VdbeCoverageIf(v
, (x
&1)==0);
2374 #ifdef WHERETRACE_ENABLED /* 0xffff */
2375 if( sqlite3WhereTrace
){
2376 VdbeNoopComment((v
, "WhereTerm[%d] (%p) priority=%d",
2377 pWC
->nTerm
-j
, pTerm
, iLoop
));
2379 if( sqlite3WhereTrace
& 0x800 ){
2380 sqlite3DebugPrintf("Coding auxiliary constraint:\n");
2381 sqlite3WhereTermPrint(pTerm
, pWC
->nTerm
-j
);
2384 sqlite3ExprIfFalse(pParse
, pE
, addrCont
, SQLITE_JUMPIFNULL
);
2385 if( skipLikeAddr
) sqlite3VdbeJumpHere(v
, skipLikeAddr
);
2386 pTerm
->wtFlags
|= TERM_CODED
;
2391 /* Insert code to test for implied constraints based on transitivity
2392 ** of the "==" operator.
2394 ** Example: If the WHERE clause contains "t1.a=t2.b" and "t2.b=123"
2395 ** and we are coding the t1 loop and the t2 loop has not yet coded,
2396 ** then we cannot use the "t1.a=t2.b" constraint, but we can code
2397 ** the implied "t1.a=123" constraint.
2399 for(pTerm
=pWC
->a
, j
=pWC
->nTerm
; j
>0; j
--, pTerm
++){
2402 if( pTerm
->wtFlags
& (TERM_VIRTUAL
|TERM_CODED
) ) continue;
2403 if( (pTerm
->eOperator
& (WO_EQ
|WO_IS
))==0 ) continue;
2404 if( (pTerm
->eOperator
& WO_EQUIV
)==0 ) continue;
2405 if( pTerm
->leftCursor
!=iCur
) continue;
2406 if( pTabItem
->fg
.jointype
& JT_LEFT
) continue;
2408 #ifdef WHERETRACE_ENABLED /* 0x800 */
2409 if( sqlite3WhereTrace
& 0x800 ){
2410 sqlite3DebugPrintf("Coding transitive constraint:\n");
2411 sqlite3WhereTermPrint(pTerm
, pWC
->nTerm
-j
);
2414 assert( !ExprHasProperty(pE
, EP_FromJoin
) );
2415 assert( (pTerm
->prereqRight
& pLevel
->notReady
)!=0 );
2416 pAlt
= sqlite3WhereFindTerm(pWC
, iCur
, pTerm
->u
.leftColumn
, notReady
,
2417 WO_EQ
|WO_IN
|WO_IS
, 0);
2418 if( pAlt
==0 ) continue;
2419 if( pAlt
->wtFlags
& (TERM_CODED
) ) continue;
2420 if( (pAlt
->eOperator
& WO_IN
)
2421 && (pAlt
->pExpr
->flags
& EP_xIsSelect
)
2422 && (pAlt
->pExpr
->x
.pSelect
->pEList
->nExpr
>1)
2426 testcase( pAlt
->eOperator
& WO_EQ
);
2427 testcase( pAlt
->eOperator
& WO_IS
);
2428 testcase( pAlt
->eOperator
& WO_IN
);
2429 VdbeModuleComment((v
, "begin transitive constraint"));
2430 sEAlt
= *pAlt
->pExpr
;
2431 sEAlt
.pLeft
= pE
->pLeft
;
2432 sqlite3ExprIfFalse(pParse
, &sEAlt
, addrCont
, SQLITE_JUMPIFNULL
);
2435 /* For a LEFT OUTER JOIN, generate code that will record the fact that
2436 ** at least one row of the right table has matched the left table.
2438 if( pLevel
->iLeftJoin
){
2439 pLevel
->addrFirst
= sqlite3VdbeCurrentAddr(v
);
2440 sqlite3VdbeAddOp2(v
, OP_Integer
, 1, pLevel
->iLeftJoin
);
2441 VdbeComment((v
, "record LEFT JOIN hit"));
2442 for(pTerm
=pWC
->a
, j
=0; j
<pWC
->nTerm
; j
++, pTerm
++){
2443 testcase( pTerm
->wtFlags
& TERM_VIRTUAL
);
2444 testcase( pTerm
->wtFlags
& TERM_CODED
);
2445 if( pTerm
->wtFlags
& (TERM_VIRTUAL
|TERM_CODED
) ) continue;
2446 if( (pTerm
->prereqAll
& pLevel
->notReady
)!=0 ){
2447 assert( pWInfo
->untestedTerms
);
2450 assert( pTerm
->pExpr
);
2451 sqlite3ExprIfFalse(pParse
, pTerm
->pExpr
, addrCont
, SQLITE_JUMPIFNULL
);
2452 pTerm
->wtFlags
|= TERM_CODED
;
2456 #if WHERETRACE_ENABLED /* 0x20800 */
2457 if( sqlite3WhereTrace
& 0x20000 ){
2458 sqlite3DebugPrintf("All WHERE-clause terms after coding level %d:\n",
2460 sqlite3WhereClausePrint(pWC
);
2462 if( sqlite3WhereTrace
& 0x800 ){
2463 sqlite3DebugPrintf("End Coding level %d: notReady=%llx\n",
2464 iLevel
, (u64
)pLevel
->notReady
);
2467 return pLevel
->notReady
;