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 entries (which are no-ops) at the
322 ** beginning and end of zAff are ignored. If all entries in zAff are
323 ** SQLITE_AFF_BLOB, 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 entries at the beginning
337 ** and end of the affinity string.
339 while( n
>0 && zAff
[0]==SQLITE_AFF_BLOB
){
344 while( n
>1 && zAff
[n
-1]==SQLITE_AFF_BLOB
){
348 /* Code the OP_Affinity opcode if there is anything left to do. */
350 sqlite3VdbeAddOp4(v
, OP_Affinity
, base
, n
, 0, zAff
, n
);
355 ** Expression pRight, which is the RHS of a comparison operation, is
356 ** either a vector of n elements or, if n==1, a scalar expression.
357 ** Before the comparison operation, affinity zAff is to be applied
358 ** to the pRight values. This function modifies characters within the
359 ** affinity string to SQLITE_AFF_BLOB if either:
361 ** * the comparison will be performed with no affinity, or
362 ** * the affinity change in zAff is guaranteed not to change the value.
364 static void updateRangeAffinityStr(
365 Expr
*pRight
, /* RHS of comparison */
366 int n
, /* Number of vector elements in comparison */
367 char *zAff
/* Affinity string to modify */
371 Expr
*p
= sqlite3VectorFieldSubexpr(pRight
, i
);
372 if( sqlite3CompareAffinity(p
, zAff
[i
])==SQLITE_AFF_BLOB
373 || sqlite3ExprNeedsNoAffinityChange(p
, zAff
[i
])
375 zAff
[i
] = SQLITE_AFF_BLOB
;
382 ** pX is an expression of the form: (vector) IN (SELECT ...)
383 ** In other words, it is a vector IN operator with a SELECT clause on the
384 ** LHS. But not all terms in the vector are indexable and the terms might
385 ** not be in the correct order for indexing.
387 ** This routine makes a copy of the input pX expression and then adjusts
388 ** the vector on the LHS with corresponding changes to the SELECT so that
389 ** the vector contains only index terms and those terms are in the correct
390 ** order. The modified IN expression is returned. The caller is responsible
391 ** for deleting the returned expression.
395 ** CREATE TABLE t1(a,b,c,d,e,f);
396 ** CREATE INDEX t1x1 ON t1(e,c);
397 ** SELECT * FROM t1 WHERE (a,b,c,d,e) IN (SELECT v,w,x,y,z FROM t2)
398 ** \_______________________________________/
401 ** Since only columns e and c can be used with the index, in that order,
402 ** the modified IN expression that is returned will be:
404 ** (e,c) IN (SELECT z,x FROM t2)
406 ** The reduced pX is different from the original (obviously) and thus is
407 ** only used for indexing, to improve performance. The original unaltered
408 ** IN expression must also be run on each output row for correctness.
410 static Expr
*removeUnindexableInClauseTerms(
411 Parse
*pParse
, /* The parsing context */
412 int iEq
, /* Look at loop terms starting here */
413 WhereLoop
*pLoop
, /* The current loop */
414 Expr
*pX
/* The IN expression to be reduced */
416 sqlite3
*db
= pParse
->db
;
417 Expr
*pNew
= sqlite3ExprDup(db
, pX
, 0);
418 if( db
->mallocFailed
==0 ){
419 ExprList
*pOrigRhs
= pNew
->x
.pSelect
->pEList
; /* Original unmodified RHS */
420 ExprList
*pOrigLhs
= pNew
->pLeft
->x
.pList
; /* Original unmodified LHS */
421 ExprList
*pRhs
= 0; /* New RHS after modifications */
422 ExprList
*pLhs
= 0; /* New LHS after mods */
423 int i
; /* Loop counter */
424 Select
*pSelect
; /* Pointer to the SELECT on the RHS */
426 for(i
=iEq
; i
<pLoop
->nLTerm
; i
++){
427 if( pLoop
->aLTerm
[i
]->pExpr
==pX
){
428 int iField
= pLoop
->aLTerm
[i
]->iField
- 1;
429 if( pOrigRhs
->a
[iField
].pExpr
==0 ) continue; /* Duplicate PK column */
430 pRhs
= sqlite3ExprListAppend(pParse
, pRhs
, pOrigRhs
->a
[iField
].pExpr
);
431 pOrigRhs
->a
[iField
].pExpr
= 0;
432 assert( pOrigLhs
->a
[iField
].pExpr
!=0 );
433 pLhs
= sqlite3ExprListAppend(pParse
, pLhs
, pOrigLhs
->a
[iField
].pExpr
);
434 pOrigLhs
->a
[iField
].pExpr
= 0;
437 sqlite3ExprListDelete(db
, pOrigRhs
);
438 sqlite3ExprListDelete(db
, pOrigLhs
);
439 pNew
->pLeft
->x
.pList
= pLhs
;
440 pNew
->x
.pSelect
->pEList
= pRhs
;
441 if( pLhs
&& pLhs
->nExpr
==1 ){
442 /* Take care here not to generate a TK_VECTOR containing only a
443 ** single value. Since the parser never creates such a vector, some
444 ** of the subroutines do not handle this case. */
445 Expr
*p
= pLhs
->a
[0].pExpr
;
446 pLhs
->a
[0].pExpr
= 0;
447 sqlite3ExprDelete(db
, pNew
->pLeft
);
450 pSelect
= pNew
->x
.pSelect
;
451 if( pSelect
->pOrderBy
){
452 /* If the SELECT statement has an ORDER BY clause, zero the
453 ** iOrderByCol variables. These are set to non-zero when an
454 ** ORDER BY term exactly matches one of the terms of the
455 ** result-set. Since the result-set of the SELECT statement may
456 ** have been modified or reordered, these variables are no longer
457 ** set correctly. Since setting them is just an optimization,
458 ** it's easiest just to zero them here. */
459 ExprList
*pOrderBy
= pSelect
->pOrderBy
;
460 for(i
=0; i
<pOrderBy
->nExpr
; i
++){
461 pOrderBy
->a
[i
].u
.x
.iOrderByCol
= 0;
466 printf("For indexing, change the IN expr:\n");
467 sqlite3TreeViewExpr(0, pX
, 0);
469 sqlite3TreeViewExpr(0, pNew
, 0);
477 ** Generate code for a single equality term of the WHERE clause. An equality
478 ** term can be either X=expr or X IN (...). pTerm is the term to be
481 ** The current value for the constraint is left in a register, the index
482 ** of which is returned. An attempt is made store the result in iTarget but
483 ** this is only guaranteed for TK_ISNULL and TK_IN constraints. If the
484 ** constraint is a TK_EQ or TK_IS, then the current value might be left in
485 ** some other register and it is the caller's responsibility to compensate.
487 ** For a constraint of the form X=expr, the expression is evaluated in
488 ** straight-line code. For constraints of the form X IN (...)
489 ** this routine sets up a loop that will iterate over all values of X.
491 static int codeEqualityTerm(
492 Parse
*pParse
, /* The parsing context */
493 WhereTerm
*pTerm
, /* The term of the WHERE clause to be coded */
494 WhereLevel
*pLevel
, /* The level of the FROM clause we are working on */
495 int iEq
, /* Index of the equality term within this level */
496 int bRev
, /* True for reverse-order IN operations */
497 int iTarget
/* Attempt to leave results in this register */
499 Expr
*pX
= pTerm
->pExpr
;
500 Vdbe
*v
= pParse
->pVdbe
;
501 int iReg
; /* Register holding results */
503 assert( pLevel
->pWLoop
->aLTerm
[iEq
]==pTerm
);
505 if( pX
->op
==TK_EQ
|| pX
->op
==TK_IS
){
506 iReg
= sqlite3ExprCodeTarget(pParse
, pX
->pRight
, iTarget
);
507 }else if( pX
->op
==TK_ISNULL
){
509 sqlite3VdbeAddOp2(v
, OP_Null
, 0, iReg
);
510 #ifndef SQLITE_OMIT_SUBQUERY
512 int eType
= IN_INDEX_NOOP
;
515 WhereLoop
*pLoop
= pLevel
->pWLoop
;
520 if( (pLoop
->wsFlags
& WHERE_VIRTUALTABLE
)==0
521 && pLoop
->u
.btree
.pIndex
!=0
522 && pLoop
->u
.btree
.pIndex
->aSortOrder
[iEq
]
528 assert( pX
->op
==TK_IN
);
531 for(i
=0; i
<iEq
; i
++){
532 if( pLoop
->aLTerm
[i
] && pLoop
->aLTerm
[i
]->pExpr
==pX
){
533 disableTerm(pLevel
, pTerm
);
537 for(i
=iEq
;i
<pLoop
->nLTerm
; i
++){
538 assert( pLoop
->aLTerm
[i
]!=0 );
539 if( pLoop
->aLTerm
[i
]->pExpr
==pX
) nEq
++;
543 if( (pX
->flags
& EP_xIsSelect
)==0 || pX
->x
.pSelect
->pEList
->nExpr
==1 ){
544 eType
= sqlite3FindInIndex(pParse
, pX
, IN_INDEX_LOOP
, 0, 0, &iTab
);
546 sqlite3
*db
= pParse
->db
;
547 pX
= removeUnindexableInClauseTerms(pParse
, iEq
, pLoop
, pX
);
549 if( !db
->mallocFailed
){
550 aiMap
= (int*)sqlite3DbMallocZero(pParse
->db
, sizeof(int)*nEq
);
551 eType
= sqlite3FindInIndex(pParse
, pX
, IN_INDEX_LOOP
, 0, aiMap
, &iTab
);
552 pTerm
->pExpr
->iTable
= iTab
;
554 sqlite3ExprDelete(db
, pX
);
558 if( eType
==IN_INDEX_INDEX_DESC
){
562 sqlite3VdbeAddOp2(v
, bRev
? OP_Last
: OP_Rewind
, iTab
, 0);
563 VdbeCoverageIf(v
, bRev
);
564 VdbeCoverageIf(v
, !bRev
);
565 assert( (pLoop
->wsFlags
& WHERE_MULTI_OR
)==0 );
567 pLoop
->wsFlags
|= WHERE_IN_ABLE
;
568 if( pLevel
->u
.in
.nIn
==0 ){
569 pLevel
->addrNxt
= sqlite3VdbeMakeLabel(pParse
);
572 i
= pLevel
->u
.in
.nIn
;
573 pLevel
->u
.in
.nIn
+= nEq
;
574 pLevel
->u
.in
.aInLoop
=
575 sqlite3DbReallocOrFree(pParse
->db
, pLevel
->u
.in
.aInLoop
,
576 sizeof(pLevel
->u
.in
.aInLoop
[0])*pLevel
->u
.in
.nIn
);
577 pIn
= pLevel
->u
.in
.aInLoop
;
579 int iMap
= 0; /* Index in aiMap[] */
581 for(i
=iEq
;i
<pLoop
->nLTerm
; i
++){
582 if( pLoop
->aLTerm
[i
]->pExpr
==pX
){
583 int iOut
= iReg
+ i
- iEq
;
584 if( eType
==IN_INDEX_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(pParse
, 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
;
1080 assert( p
->op
==TK_SELECT
);
1081 iSelect
= sqlite3CodeSubselect(pParse
, p
);
1082 sqlite3VdbeAddOp3(v
, OP_Copy
, iSelect
, iReg
, nReg
-1);
1087 ExprList
*pList
= p
->x
.pList
;
1088 assert( nReg
<=pList
->nExpr
);
1089 for(i
=0; i
<nReg
; i
++){
1090 sqlite3ExprCode(pParse
, pList
->a
[i
].pExpr
, iReg
+i
);
1095 sqlite3ExprCode(pParse
, p
, iReg
);
1099 /* An instance of the IdxExprTrans object carries information about a
1100 ** mapping from an expression on table columns into a column in an index
1101 ** down through the Walker.
1103 typedef struct IdxExprTrans
{
1104 Expr
*pIdxExpr
; /* The index expression */
1105 int iTabCur
; /* The cursor of the corresponding table */
1106 int iIdxCur
; /* The cursor for the index */
1107 int iIdxCol
; /* The column for the index */
1110 /* The walker node callback used to transform matching expressions into
1111 ** a reference to an index column for an index on an expression.
1113 ** If pExpr matches, then transform it into a reference to the index column
1114 ** that contains the value of pExpr.
1116 static int whereIndexExprTransNode(Walker
*p
, Expr
*pExpr
){
1117 IdxExprTrans
*pX
= p
->u
.pIdxTrans
;
1118 if( sqlite3ExprCompare(0, pExpr
, pX
->pIdxExpr
, pX
->iTabCur
)==0 ){
1119 pExpr
->op
= TK_COLUMN
;
1120 pExpr
->iTable
= pX
->iIdxCur
;
1121 pExpr
->iColumn
= pX
->iIdxCol
;
1125 return WRC_Continue
;
1130 ** For an indexes on expression X, locate every instance of expression X
1131 ** in pExpr and change that subexpression into a reference to the appropriate
1132 ** column of the index.
1134 static void whereIndexExprTrans(
1135 Index
*pIdx
, /* The Index */
1136 int iTabCur
, /* Cursor of the table that is being indexed */
1137 int iIdxCur
, /* Cursor of the index itself */
1138 WhereInfo
*pWInfo
/* Transform expressions in this WHERE clause */
1140 int iIdxCol
; /* Column number of the index */
1141 ExprList
*aColExpr
; /* Expressions that are indexed */
1144 aColExpr
= pIdx
->aColExpr
;
1145 if( aColExpr
==0 ) return; /* Not an index on expressions */
1146 memset(&w
, 0, sizeof(w
));
1147 w
.xExprCallback
= whereIndexExprTransNode
;
1149 x
.iTabCur
= iTabCur
;
1150 x
.iIdxCur
= iIdxCur
;
1151 for(iIdxCol
=0; iIdxCol
<aColExpr
->nExpr
; iIdxCol
++){
1152 if( pIdx
->aiColumn
[iIdxCol
]!=XN_EXPR
) continue;
1153 assert( aColExpr
->a
[iIdxCol
].pExpr
!=0 );
1154 x
.iIdxCol
= iIdxCol
;
1155 x
.pIdxExpr
= aColExpr
->a
[iIdxCol
].pExpr
;
1156 sqlite3WalkExpr(&w
, pWInfo
->pWhere
);
1157 sqlite3WalkExprList(&w
, pWInfo
->pOrderBy
);
1158 sqlite3WalkExprList(&w
, pWInfo
->pResultSet
);
1163 ** The pTruth expression is always true because it is the WHERE clause
1164 ** a partial index that is driving a query loop. Look through all of the
1165 ** WHERE clause terms on the query, and if any of those terms must be
1166 ** true because pTruth is true, then mark those WHERE clause terms as
1169 static void whereApplyPartialIndexConstraints(
1176 while( pTruth
->op
==TK_AND
){
1177 whereApplyPartialIndexConstraints(pTruth
->pLeft
, iTabCur
, pWC
);
1178 pTruth
= pTruth
->pRight
;
1180 for(i
=0, pTerm
=pWC
->a
; i
<pWC
->nTerm
; i
++, pTerm
++){
1182 if( pTerm
->wtFlags
& TERM_CODED
) continue;
1183 pExpr
= pTerm
->pExpr
;
1184 if( sqlite3ExprCompare(0, pExpr
, pTruth
, iTabCur
)==0 ){
1185 pTerm
->wtFlags
|= TERM_CODED
;
1191 ** Generate code for the start of the iLevel-th loop in the WHERE clause
1192 ** implementation described by pWInfo.
1194 Bitmask
sqlite3WhereCodeOneLoopStart(
1195 Parse
*pParse
, /* Parsing context */
1196 Vdbe
*v
, /* Prepared statement under construction */
1197 WhereInfo
*pWInfo
, /* Complete information about the WHERE clause */
1198 int iLevel
, /* Which level of pWInfo->a[] should be coded */
1199 WhereLevel
*pLevel
, /* The current level pointer */
1200 Bitmask notReady
/* Which tables are currently available */
1202 int j
, k
; /* Loop counters */
1203 int iCur
; /* The VDBE cursor for the table */
1204 int addrNxt
; /* Where to jump to continue with the next IN case */
1205 int bRev
; /* True if we need to scan in reverse order */
1206 WhereLoop
*pLoop
; /* The WhereLoop object being coded */
1207 WhereClause
*pWC
; /* Decomposition of the entire WHERE clause */
1208 WhereTerm
*pTerm
; /* A WHERE clause term */
1209 sqlite3
*db
; /* Database connection */
1210 struct SrcList_item
*pTabItem
; /* FROM clause term being coded */
1211 int addrBrk
; /* Jump here to break out of the loop */
1212 int addrHalt
; /* addrBrk for the outermost loop */
1213 int addrCont
; /* Jump here to continue with next cycle */
1214 int iRowidReg
= 0; /* Rowid is stored in this register, if not zero */
1215 int iReleaseReg
= 0; /* Temp register to free before returning */
1216 Index
*pIdx
= 0; /* Index used by loop (if any) */
1217 int iLoop
; /* Iteration of constraint generator loop */
1221 pLoop
= pLevel
->pWLoop
;
1222 pTabItem
= &pWInfo
->pTabList
->a
[pLevel
->iFrom
];
1223 iCur
= pTabItem
->iCursor
;
1224 pLevel
->notReady
= notReady
& ~sqlite3WhereGetMask(&pWInfo
->sMaskSet
, iCur
);
1225 bRev
= (pWInfo
->revMask
>>iLevel
)&1;
1226 VdbeModuleComment((v
, "Begin WHERE-loop%d: %s",iLevel
,pTabItem
->pTab
->zName
));
1228 /* Create labels for the "break" and "continue" instructions
1229 ** for the current loop. Jump to addrBrk to break out of a loop.
1230 ** Jump to cont to go immediately to the next iteration of the
1233 ** When there is an IN operator, we also have a "addrNxt" label that
1234 ** means to continue with the next IN value combination. When
1235 ** there are no IN operators in the constraints, the "addrNxt" label
1236 ** is the same as "addrBrk".
1238 addrBrk
= pLevel
->addrBrk
= pLevel
->addrNxt
= sqlite3VdbeMakeLabel(pParse
);
1239 addrCont
= pLevel
->addrCont
= sqlite3VdbeMakeLabel(pParse
);
1241 /* If this is the right table of a LEFT OUTER JOIN, allocate and
1242 ** initialize a memory cell that records if this table matches any
1243 ** row of the left table of the join.
1245 assert( (pWInfo
->wctrlFlags
& WHERE_OR_SUBCLAUSE
)
1246 || pLevel
->iFrom
>0 || (pTabItem
[0].fg
.jointype
& JT_LEFT
)==0
1248 if( pLevel
->iFrom
>0 && (pTabItem
[0].fg
.jointype
& JT_LEFT
)!=0 ){
1249 pLevel
->iLeftJoin
= ++pParse
->nMem
;
1250 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, pLevel
->iLeftJoin
);
1251 VdbeComment((v
, "init LEFT JOIN no-match flag"));
1254 /* Compute a safe address to jump to if we discover that the table for
1255 ** this loop is empty and can never contribute content. */
1256 for(j
=iLevel
; j
>0 && pWInfo
->a
[j
].iLeftJoin
==0; j
--){}
1257 addrHalt
= pWInfo
->a
[j
].addrBrk
;
1259 /* Special case of a FROM clause subquery implemented as a co-routine */
1260 if( pTabItem
->fg
.viaCoroutine
){
1261 int regYield
= pTabItem
->regReturn
;
1262 sqlite3VdbeAddOp3(v
, OP_InitCoroutine
, regYield
, 0, pTabItem
->addrFillSub
);
1263 pLevel
->p2
= sqlite3VdbeAddOp2(v
, OP_Yield
, regYield
, addrBrk
);
1265 VdbeComment((v
, "next row of %s", pTabItem
->pTab
->zName
));
1266 pLevel
->op
= OP_Goto
;
1269 #ifndef SQLITE_OMIT_VIRTUALTABLE
1270 if( (pLoop
->wsFlags
& WHERE_VIRTUALTABLE
)!=0 ){
1271 /* Case 1: The table is a virtual-table. Use the VFilter and VNext
1272 ** to access the data.
1274 int iReg
; /* P3 Value for OP_VFilter */
1276 int nConstraint
= pLoop
->nLTerm
;
1277 int iIn
; /* Counter for IN constraints */
1279 iReg
= sqlite3GetTempRange(pParse
, nConstraint
+2);
1280 addrNotFound
= pLevel
->addrBrk
;
1281 for(j
=0; j
<nConstraint
; j
++){
1282 int iTarget
= iReg
+j
+2;
1283 pTerm
= pLoop
->aLTerm
[j
];
1284 if( NEVER(pTerm
==0) ) continue;
1285 if( pTerm
->eOperator
& WO_IN
){
1286 codeEqualityTerm(pParse
, pTerm
, pLevel
, j
, bRev
, iTarget
);
1287 addrNotFound
= pLevel
->addrNxt
;
1289 Expr
*pRight
= pTerm
->pExpr
->pRight
;
1290 codeExprOrVector(pParse
, pRight
, iTarget
, 1);
1293 sqlite3VdbeAddOp2(v
, OP_Integer
, pLoop
->u
.vtab
.idxNum
, iReg
);
1294 sqlite3VdbeAddOp2(v
, OP_Integer
, nConstraint
, iReg
+1);
1295 sqlite3VdbeAddOp4(v
, OP_VFilter
, iCur
, addrNotFound
, iReg
,
1296 pLoop
->u
.vtab
.idxStr
,
1297 pLoop
->u
.vtab
.needFree
? P4_DYNAMIC
: P4_STATIC
);
1299 pLoop
->u
.vtab
.needFree
= 0;
1301 pLevel
->op
= pWInfo
->eOnePass
? OP_Noop
: OP_VNext
;
1302 pLevel
->p2
= sqlite3VdbeCurrentAddr(v
);
1303 iIn
= pLevel
->u
.in
.nIn
;
1304 for(j
=nConstraint
-1; j
>=0; j
--){
1305 pTerm
= pLoop
->aLTerm
[j
];
1306 if( j
<16 && (pLoop
->u
.vtab
.omitMask
>>j
)&1 ){
1307 disableTerm(pLevel
, pTerm
);
1308 }else if( (pTerm
->eOperator
& WO_IN
)!=0 ){
1309 Expr
*pCompare
; /* The comparison operator */
1310 Expr
*pRight
; /* RHS of the comparison */
1311 VdbeOp
*pOp
; /* Opcode to access the value of the IN constraint */
1313 /* Reload the constraint value into reg[iReg+j+2]. The same value
1314 ** was loaded into the same register prior to the OP_VFilter, but
1315 ** the xFilter implementation might have changed the datatype or
1316 ** encoding of the value in the register, so it *must* be reloaded. */
1317 assert( pLevel
->u
.in
.aInLoop
!=0 || db
->mallocFailed
);
1318 if( !db
->mallocFailed
){
1320 pOp
= sqlite3VdbeGetOp(v
, pLevel
->u
.in
.aInLoop
[--iIn
].addrInTop
);
1321 assert( pOp
->opcode
==OP_Column
|| pOp
->opcode
==OP_Rowid
);
1322 assert( pOp
->opcode
!=OP_Column
|| pOp
->p3
==iReg
+j
+2 );
1323 assert( pOp
->opcode
!=OP_Rowid
|| pOp
->p2
==iReg
+j
+2 );
1324 testcase( pOp
->opcode
==OP_Rowid
);
1325 sqlite3VdbeAddOp3(v
, pOp
->opcode
, pOp
->p1
, pOp
->p2
, pOp
->p3
);
1328 /* Generate code that will continue to the next row if
1329 ** the IN constraint is not satisfied */
1330 pCompare
= sqlite3PExpr(pParse
, TK_EQ
, 0, 0);
1331 assert( pCompare
!=0 || db
->mallocFailed
);
1333 pCompare
->pLeft
= pTerm
->pExpr
->pLeft
;
1334 pCompare
->pRight
= pRight
= sqlite3Expr(db
, TK_REGISTER
, 0);
1336 pRight
->iTable
= iReg
+j
+2;
1337 sqlite3ExprIfFalse(pParse
, pCompare
, pLevel
->addrCont
, 0);
1339 pCompare
->pLeft
= 0;
1340 sqlite3ExprDelete(db
, pCompare
);
1344 /* These registers need to be preserved in case there is an IN operator
1345 ** loop. So we could deallocate the registers here (and potentially
1346 ** reuse them later) if (pLoop->wsFlags & WHERE_IN_ABLE)==0. But it seems
1347 ** simpler and safer to simply not reuse the registers.
1349 ** sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2);
1352 #endif /* SQLITE_OMIT_VIRTUALTABLE */
1354 if( (pLoop
->wsFlags
& WHERE_IPK
)!=0
1355 && (pLoop
->wsFlags
& (WHERE_COLUMN_IN
|WHERE_COLUMN_EQ
))!=0
1357 /* Case 2: We can directly reference a single row using an
1358 ** equality comparison against the ROWID field. Or
1359 ** we reference multiple rows using a "rowid IN (...)"
1362 assert( pLoop
->u
.btree
.nEq
==1 );
1363 pTerm
= pLoop
->aLTerm
[0];
1365 assert( pTerm
->pExpr
!=0 );
1366 testcase( pTerm
->wtFlags
& TERM_VIRTUAL
);
1367 iReleaseReg
= ++pParse
->nMem
;
1368 iRowidReg
= codeEqualityTerm(pParse
, pTerm
, pLevel
, 0, bRev
, iReleaseReg
);
1369 if( iRowidReg
!=iReleaseReg
) sqlite3ReleaseTempReg(pParse
, iReleaseReg
);
1370 addrNxt
= pLevel
->addrNxt
;
1371 sqlite3VdbeAddOp3(v
, OP_SeekRowid
, iCur
, addrNxt
, iRowidReg
);
1373 pLevel
->op
= OP_Noop
;
1374 if( (pTerm
->prereqAll
& pLevel
->notReady
)==0 ){
1375 pTerm
->wtFlags
|= TERM_CODED
;
1377 }else if( (pLoop
->wsFlags
& WHERE_IPK
)!=0
1378 && (pLoop
->wsFlags
& WHERE_COLUMN_RANGE
)!=0
1380 /* Case 3: We have an inequality comparison against the ROWID field.
1382 int testOp
= OP_Noop
;
1384 int memEndValue
= 0;
1385 WhereTerm
*pStart
, *pEnd
;
1389 if( pLoop
->wsFlags
& WHERE_BTM_LIMIT
) pStart
= pLoop
->aLTerm
[j
++];
1390 if( pLoop
->wsFlags
& WHERE_TOP_LIMIT
) pEnd
= pLoop
->aLTerm
[j
++];
1391 assert( pStart
!=0 || pEnd
!=0 );
1397 codeCursorHint(pTabItem
, pWInfo
, pLevel
, pEnd
);
1399 Expr
*pX
; /* The expression that defines the start bound */
1400 int r1
, rTemp
; /* Registers for holding the start boundary */
1401 int op
; /* Cursor seek operation */
1403 /* The following constant maps TK_xx codes into corresponding
1404 ** seek opcodes. It depends on a particular ordering of TK_xx
1406 const u8 aMoveOp
[] = {
1407 /* TK_GT */ OP_SeekGT
,
1408 /* TK_LE */ OP_SeekLE
,
1409 /* TK_LT */ OP_SeekLT
,
1410 /* TK_GE */ OP_SeekGE
1412 assert( TK_LE
==TK_GT
+1 ); /* Make sure the ordering.. */
1413 assert( TK_LT
==TK_GT
+2 ); /* ... of the TK_xx values... */
1414 assert( TK_GE
==TK_GT
+3 ); /* ... is correcct. */
1416 assert( (pStart
->wtFlags
& TERM_VNULL
)==0 );
1417 testcase( pStart
->wtFlags
& TERM_VIRTUAL
);
1420 testcase( pStart
->leftCursor
!=iCur
); /* transitive constraints */
1421 if( sqlite3ExprIsVector(pX
->pRight
) ){
1422 r1
= rTemp
= sqlite3GetTempReg(pParse
);
1423 codeExprOrVector(pParse
, pX
->pRight
, r1
, 1);
1424 testcase( pX
->op
==TK_GT
);
1425 testcase( pX
->op
==TK_GE
);
1426 testcase( pX
->op
==TK_LT
);
1427 testcase( pX
->op
==TK_LE
);
1428 op
= aMoveOp
[((pX
->op
- TK_GT
- 1) & 0x3) | 0x1];
1429 assert( pX
->op
!=TK_GT
|| op
==OP_SeekGE
);
1430 assert( pX
->op
!=TK_GE
|| op
==OP_SeekGE
);
1431 assert( pX
->op
!=TK_LT
|| op
==OP_SeekLE
);
1432 assert( pX
->op
!=TK_LE
|| op
==OP_SeekLE
);
1434 r1
= sqlite3ExprCodeTemp(pParse
, pX
->pRight
, &rTemp
);
1435 disableTerm(pLevel
, pStart
);
1436 op
= aMoveOp
[(pX
->op
- TK_GT
)];
1438 sqlite3VdbeAddOp3(v
, op
, iCur
, addrBrk
, r1
);
1439 VdbeComment((v
, "pk"));
1440 VdbeCoverageIf(v
, pX
->op
==TK_GT
);
1441 VdbeCoverageIf(v
, pX
->op
==TK_LE
);
1442 VdbeCoverageIf(v
, pX
->op
==TK_LT
);
1443 VdbeCoverageIf(v
, pX
->op
==TK_GE
);
1444 sqlite3ReleaseTempReg(pParse
, rTemp
);
1446 sqlite3VdbeAddOp2(v
, bRev
? OP_Last
: OP_Rewind
, iCur
, addrHalt
);
1447 VdbeCoverageIf(v
, bRev
==0);
1448 VdbeCoverageIf(v
, bRev
!=0);
1454 assert( (pEnd
->wtFlags
& TERM_VNULL
)==0 );
1455 testcase( pEnd
->leftCursor
!=iCur
); /* Transitive constraints */
1456 testcase( pEnd
->wtFlags
& TERM_VIRTUAL
);
1457 memEndValue
= ++pParse
->nMem
;
1458 codeExprOrVector(pParse
, pX
->pRight
, memEndValue
, 1);
1459 if( 0==sqlite3ExprIsVector(pX
->pRight
)
1460 && (pX
->op
==TK_LT
|| pX
->op
==TK_GT
)
1462 testOp
= bRev
? OP_Le
: OP_Ge
;
1464 testOp
= bRev
? OP_Lt
: OP_Gt
;
1466 if( 0==sqlite3ExprIsVector(pX
->pRight
) ){
1467 disableTerm(pLevel
, pEnd
);
1470 start
= sqlite3VdbeCurrentAddr(v
);
1471 pLevel
->op
= bRev
? OP_Prev
: OP_Next
;
1474 assert( pLevel
->p5
==0 );
1475 if( testOp
!=OP_Noop
){
1476 iRowidReg
= ++pParse
->nMem
;
1477 sqlite3VdbeAddOp2(v
, OP_Rowid
, iCur
, iRowidReg
);
1478 sqlite3VdbeAddOp3(v
, testOp
, memEndValue
, addrBrk
, iRowidReg
);
1479 VdbeCoverageIf(v
, testOp
==OP_Le
);
1480 VdbeCoverageIf(v
, testOp
==OP_Lt
);
1481 VdbeCoverageIf(v
, testOp
==OP_Ge
);
1482 VdbeCoverageIf(v
, testOp
==OP_Gt
);
1483 sqlite3VdbeChangeP5(v
, SQLITE_AFF_NUMERIC
| SQLITE_JUMPIFNULL
);
1485 }else if( pLoop
->wsFlags
& WHERE_INDEXED
){
1486 /* Case 4: A scan using an index.
1488 ** The WHERE clause may contain zero or more equality
1489 ** terms ("==" or "IN" operators) that refer to the N
1490 ** left-most columns of the index. It may also contain
1491 ** inequality constraints (>, <, >= or <=) on the indexed
1492 ** column that immediately follows the N equalities. Only
1493 ** the right-most column can be an inequality - the rest must
1494 ** use the "==" and "IN" operators. For example, if the
1495 ** index is on (x,y,z), then the following clauses are all
1501 ** x=5 AND y>5 AND y<10
1502 ** x=5 AND y=5 AND z<=10
1504 ** The z<10 term of the following cannot be used, only
1509 ** N may be zero if there are inequality constraints.
1510 ** If there are no inequality constraints, then N is at
1513 ** This case is also used when there are no WHERE clause
1514 ** constraints but an index is selected anyway, in order
1515 ** to force the output order to conform to an ORDER BY.
1517 static const u8 aStartOp
[] = {
1520 OP_Rewind
, /* 2: (!start_constraints && startEq && !bRev) */
1521 OP_Last
, /* 3: (!start_constraints && startEq && bRev) */
1522 OP_SeekGT
, /* 4: (start_constraints && !startEq && !bRev) */
1523 OP_SeekLT
, /* 5: (start_constraints && !startEq && bRev) */
1524 OP_SeekGE
, /* 6: (start_constraints && startEq && !bRev) */
1525 OP_SeekLE
/* 7: (start_constraints && startEq && bRev) */
1527 static const u8 aEndOp
[] = {
1528 OP_IdxGE
, /* 0: (end_constraints && !bRev && !endEq) */
1529 OP_IdxGT
, /* 1: (end_constraints && !bRev && endEq) */
1530 OP_IdxLE
, /* 2: (end_constraints && bRev && !endEq) */
1531 OP_IdxLT
, /* 3: (end_constraints && bRev && endEq) */
1533 u16 nEq
= pLoop
->u
.btree
.nEq
; /* Number of == or IN terms */
1534 u16 nBtm
= pLoop
->u
.btree
.nBtm
; /* Length of BTM vector */
1535 u16 nTop
= pLoop
->u
.btree
.nTop
; /* Length of TOP vector */
1536 int regBase
; /* Base register holding constraint values */
1537 WhereTerm
*pRangeStart
= 0; /* Inequality constraint at range start */
1538 WhereTerm
*pRangeEnd
= 0; /* Inequality constraint at range end */
1539 int startEq
; /* True if range start uses ==, >= or <= */
1540 int endEq
; /* True if range end uses ==, >= or <= */
1541 int start_constraints
; /* Start of range is constrained */
1542 int nConstraint
; /* Number of constraint terms */
1543 int iIdxCur
; /* The VDBE cursor for the index */
1544 int nExtraReg
= 0; /* Number of extra registers needed */
1545 int op
; /* Instruction opcode */
1546 char *zStartAff
; /* Affinity for start of range constraint */
1547 char *zEndAff
= 0; /* Affinity for end of range constraint */
1548 u8 bSeekPastNull
= 0; /* True to seek past initial nulls */
1549 u8 bStopAtNull
= 0; /* Add condition to terminate at NULLs */
1550 int omitTable
; /* True if we use the index only */
1553 pIdx
= pLoop
->u
.btree
.pIndex
;
1554 iIdxCur
= pLevel
->iIdxCur
;
1555 assert( nEq
>=pLoop
->nSkip
);
1557 /* If this loop satisfies a sort order (pOrderBy) request that
1558 ** was passed to this function to implement a "SELECT min(x) ..."
1559 ** query, then the caller will only allow the loop to run for
1560 ** a single iteration. This means that the first row returned
1561 ** should not have a NULL value stored in 'x'. If column 'x' is
1562 ** the first one after the nEq equality constraints in the index,
1563 ** this requires some special handling.
1565 assert( pWInfo
->pOrderBy
==0
1566 || pWInfo
->pOrderBy
->nExpr
==1
1567 || (pWInfo
->wctrlFlags
&WHERE_ORDERBY_MIN
)==0 );
1568 if( (pWInfo
->wctrlFlags
&WHERE_ORDERBY_MIN
)!=0
1570 && (pIdx
->nKeyCol
>nEq
)
1572 assert( pLoop
->nSkip
==0 );
1577 /* Find any inequality constraint terms for the start and end
1581 if( pLoop
->wsFlags
& WHERE_BTM_LIMIT
){
1582 pRangeStart
= pLoop
->aLTerm
[j
++];
1583 nExtraReg
= MAX(nExtraReg
, pLoop
->u
.btree
.nBtm
);
1584 /* Like optimization range constraints always occur in pairs */
1585 assert( (pRangeStart
->wtFlags
& TERM_LIKEOPT
)==0 ||
1586 (pLoop
->wsFlags
& WHERE_TOP_LIMIT
)!=0 );
1588 if( pLoop
->wsFlags
& WHERE_TOP_LIMIT
){
1589 pRangeEnd
= pLoop
->aLTerm
[j
++];
1590 nExtraReg
= MAX(nExtraReg
, pLoop
->u
.btree
.nTop
);
1591 #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
1592 if( (pRangeEnd
->wtFlags
& TERM_LIKEOPT
)!=0 ){
1593 assert( pRangeStart
!=0 ); /* LIKE opt constraints */
1594 assert( pRangeStart
->wtFlags
& TERM_LIKEOPT
); /* occur in pairs */
1595 pLevel
->iLikeRepCntr
= (u32
)++pParse
->nMem
;
1596 sqlite3VdbeAddOp2(v
, OP_Integer
, 1, (int)pLevel
->iLikeRepCntr
);
1597 VdbeComment((v
, "LIKE loop counter"));
1598 pLevel
->addrLikeRep
= sqlite3VdbeCurrentAddr(v
);
1599 /* iLikeRepCntr actually stores 2x the counter register number. The
1600 ** bottom bit indicates whether the search order is ASC or DESC. */
1602 testcase( pIdx
->aSortOrder
[nEq
]==SQLITE_SO_DESC
);
1603 assert( (bRev
& ~1)==0 );
1604 pLevel
->iLikeRepCntr
<<=1;
1605 pLevel
->iLikeRepCntr
|= bRev
^ (pIdx
->aSortOrder
[nEq
]==SQLITE_SO_DESC
);
1608 if( pRangeStart
==0 ){
1609 j
= pIdx
->aiColumn
[nEq
];
1610 if( (j
>=0 && pIdx
->pTable
->aCol
[j
].notNull
==0) || j
==XN_EXPR
){
1615 assert( pRangeEnd
==0 || (pRangeEnd
->wtFlags
& TERM_VNULL
)==0 );
1617 /* If we are doing a reverse order scan on an ascending index, or
1618 ** a forward order scan on a descending index, interchange the
1619 ** start and end terms (pRangeStart and pRangeEnd).
1621 if( (nEq
<pIdx
->nKeyCol
&& bRev
==(pIdx
->aSortOrder
[nEq
]==SQLITE_SO_ASC
))
1622 || (bRev
&& pIdx
->nKeyCol
==nEq
)
1624 SWAP(WhereTerm
*, pRangeEnd
, pRangeStart
);
1625 SWAP(u8
, bSeekPastNull
, bStopAtNull
);
1626 SWAP(u8
, nBtm
, nTop
);
1629 /* Generate code to evaluate all constraint terms using == or IN
1630 ** and store the values of those terms in an array of registers
1631 ** starting at regBase.
1633 codeCursorHint(pTabItem
, pWInfo
, pLevel
, pRangeEnd
);
1634 regBase
= codeAllEqualityTerms(pParse
,pLevel
,bRev
,nExtraReg
,&zStartAff
);
1635 assert( zStartAff
==0 || sqlite3Strlen30(zStartAff
)>=nEq
);
1636 if( zStartAff
&& nTop
){
1637 zEndAff
= sqlite3DbStrDup(db
, &zStartAff
[nEq
]);
1639 addrNxt
= pLevel
->addrNxt
;
1641 testcase( pRangeStart
&& (pRangeStart
->eOperator
& WO_LE
)!=0 );
1642 testcase( pRangeStart
&& (pRangeStart
->eOperator
& WO_GE
)!=0 );
1643 testcase( pRangeEnd
&& (pRangeEnd
->eOperator
& WO_LE
)!=0 );
1644 testcase( pRangeEnd
&& (pRangeEnd
->eOperator
& WO_GE
)!=0 );
1645 startEq
= !pRangeStart
|| pRangeStart
->eOperator
& (WO_LE
|WO_GE
);
1646 endEq
= !pRangeEnd
|| pRangeEnd
->eOperator
& (WO_LE
|WO_GE
);
1647 start_constraints
= pRangeStart
|| nEq
>0;
1649 /* Seek the index cursor to the start of the range. */
1652 Expr
*pRight
= pRangeStart
->pExpr
->pRight
;
1653 codeExprOrVector(pParse
, pRight
, regBase
+nEq
, nBtm
);
1654 whereLikeOptimizationStringFixup(v
, pLevel
, pRangeStart
);
1655 if( (pRangeStart
->wtFlags
& TERM_VNULL
)==0
1656 && sqlite3ExprCanBeNull(pRight
)
1658 sqlite3VdbeAddOp2(v
, OP_IsNull
, regBase
+nEq
, addrNxt
);
1662 updateRangeAffinityStr(pRight
, nBtm
, &zStartAff
[nEq
]);
1664 nConstraint
+= nBtm
;
1665 testcase( pRangeStart
->wtFlags
& TERM_VIRTUAL
);
1666 if( sqlite3ExprIsVector(pRight
)==0 ){
1667 disableTerm(pLevel
, pRangeStart
);
1672 }else if( bSeekPastNull
){
1673 sqlite3VdbeAddOp2(v
, OP_Null
, 0, regBase
+nEq
);
1676 start_constraints
= 1;
1678 codeApplyAffinity(pParse
, regBase
, nConstraint
- bSeekPastNull
, zStartAff
);
1679 if( pLoop
->nSkip
>0 && nConstraint
==pLoop
->nSkip
){
1680 /* The skip-scan logic inside the call to codeAllEqualityConstraints()
1681 ** above has already left the cursor sitting on the correct row,
1682 ** so no further seeking is needed */
1684 if( pLoop
->wsFlags
& WHERE_IN_EARLYOUT
){
1685 sqlite3VdbeAddOp1(v
, OP_SeekHit
, iIdxCur
);
1687 op
= aStartOp
[(start_constraints
<<2) + (startEq
<<1) + bRev
];
1689 sqlite3VdbeAddOp4Int(v
, op
, iIdxCur
, addrNxt
, regBase
, nConstraint
);
1691 VdbeCoverageIf(v
, op
==OP_Rewind
); testcase( op
==OP_Rewind
);
1692 VdbeCoverageIf(v
, op
==OP_Last
); testcase( op
==OP_Last
);
1693 VdbeCoverageIf(v
, op
==OP_SeekGT
); testcase( op
==OP_SeekGT
);
1694 VdbeCoverageIf(v
, op
==OP_SeekGE
); testcase( op
==OP_SeekGE
);
1695 VdbeCoverageIf(v
, op
==OP_SeekLE
); testcase( op
==OP_SeekLE
);
1696 VdbeCoverageIf(v
, op
==OP_SeekLT
); testcase( op
==OP_SeekLT
);
1699 /* Load the value for the inequality constraint at the end of the
1704 Expr
*pRight
= pRangeEnd
->pExpr
->pRight
;
1705 codeExprOrVector(pParse
, pRight
, regBase
+nEq
, nTop
);
1706 whereLikeOptimizationStringFixup(v
, pLevel
, pRangeEnd
);
1707 if( (pRangeEnd
->wtFlags
& TERM_VNULL
)==0
1708 && sqlite3ExprCanBeNull(pRight
)
1710 sqlite3VdbeAddOp2(v
, OP_IsNull
, regBase
+nEq
, addrNxt
);
1714 updateRangeAffinityStr(pRight
, nTop
, zEndAff
);
1715 codeApplyAffinity(pParse
, regBase
+nEq
, nTop
, zEndAff
);
1717 assert( pParse
->db
->mallocFailed
);
1719 nConstraint
+= nTop
;
1720 testcase( pRangeEnd
->wtFlags
& TERM_VIRTUAL
);
1722 if( sqlite3ExprIsVector(pRight
)==0 ){
1723 disableTerm(pLevel
, pRangeEnd
);
1727 }else if( bStopAtNull
){
1728 sqlite3VdbeAddOp2(v
, OP_Null
, 0, regBase
+nEq
);
1732 sqlite3DbFree(db
, zStartAff
);
1733 sqlite3DbFree(db
, zEndAff
);
1735 /* Top of the loop body */
1736 pLevel
->p2
= sqlite3VdbeCurrentAddr(v
);
1738 /* Check if the index cursor is past the end of the range. */
1740 op
= aEndOp
[bRev
*2 + endEq
];
1741 sqlite3VdbeAddOp4Int(v
, op
, iIdxCur
, addrNxt
, regBase
, nConstraint
);
1742 testcase( op
==OP_IdxGT
); VdbeCoverageIf(v
, op
==OP_IdxGT
);
1743 testcase( op
==OP_IdxGE
); VdbeCoverageIf(v
, op
==OP_IdxGE
);
1744 testcase( op
==OP_IdxLT
); VdbeCoverageIf(v
, op
==OP_IdxLT
);
1745 testcase( op
==OP_IdxLE
); VdbeCoverageIf(v
, op
==OP_IdxLE
);
1748 if( pLoop
->wsFlags
& WHERE_IN_EARLYOUT
){
1749 sqlite3VdbeAddOp2(v
, OP_SeekHit
, iIdxCur
, 1);
1752 /* Seek the table cursor, if required */
1753 omitTable
= (pLoop
->wsFlags
& WHERE_IDX_ONLY
)!=0
1754 && (pWInfo
->wctrlFlags
& WHERE_OR_SUBCLAUSE
)==0;
1756 /* pIdx is a covering index. No need to access the main table. */
1757 }else if( HasRowid(pIdx
->pTable
) ){
1758 if( (pWInfo
->wctrlFlags
& WHERE_SEEK_TABLE
) || (
1759 (pWInfo
->wctrlFlags
& WHERE_SEEK_UNIQ_TABLE
)
1760 && (pWInfo
->eOnePass
==ONEPASS_SINGLE
)
1762 iRowidReg
= ++pParse
->nMem
;
1763 sqlite3VdbeAddOp2(v
, OP_IdxRowid
, iIdxCur
, iRowidReg
);
1764 sqlite3VdbeAddOp3(v
, OP_NotExists
, iCur
, 0, iRowidReg
);
1767 codeDeferredSeek(pWInfo
, pIdx
, iCur
, iIdxCur
);
1769 }else if( iCur
!=iIdxCur
){
1770 Index
*pPk
= sqlite3PrimaryKeyIndex(pIdx
->pTable
);
1771 iRowidReg
= sqlite3GetTempRange(pParse
, pPk
->nKeyCol
);
1772 for(j
=0; j
<pPk
->nKeyCol
; j
++){
1773 k
= sqlite3ColumnOfIndex(pIdx
, pPk
->aiColumn
[j
]);
1774 sqlite3VdbeAddOp3(v
, OP_Column
, iIdxCur
, k
, iRowidReg
+j
);
1776 sqlite3VdbeAddOp4Int(v
, OP_NotFound
, iCur
, addrCont
,
1777 iRowidReg
, pPk
->nKeyCol
); VdbeCoverage(v
);
1780 /* If pIdx is an index on one or more expressions, then look through
1781 ** all the expressions in pWInfo and try to transform matching expressions
1782 ** into reference to index columns.
1784 ** Do not do this for the RHS of a LEFT JOIN. This is because the
1785 ** expression may be evaluated after OP_NullRow has been executed on
1786 ** the cursor. In this case it is important to do the full evaluation,
1787 ** as the result of the expression may not be NULL, even if all table
1788 ** column values are. https://www.sqlite.org/src/info/7fa8049685b50b5a
1790 ** Also, do not do this when processing one index an a multi-index
1791 ** OR clause, since the transformation will become invalid once we
1792 ** move forward to the next index.
1793 ** https://sqlite.org/src/info/4e8e4857d32d401f
1795 if( pLevel
->iLeftJoin
==0 && (pWInfo
->wctrlFlags
& WHERE_OR_SUBCLAUSE
)==0 ){
1796 whereIndexExprTrans(pIdx
, iCur
, iIdxCur
, pWInfo
);
1799 /* If a partial index is driving the loop, try to eliminate WHERE clause
1800 ** terms from the query that must be true due to the WHERE clause of
1801 ** the partial index
1803 if( pIdx
->pPartIdxWhere
){
1804 whereApplyPartialIndexConstraints(pIdx
->pPartIdxWhere
, iCur
, pWC
);
1807 /* Record the instruction used to terminate the loop. */
1808 if( pLoop
->wsFlags
& WHERE_ONEROW
){
1809 pLevel
->op
= OP_Noop
;
1811 pLevel
->op
= OP_Prev
;
1813 pLevel
->op
= OP_Next
;
1815 pLevel
->p1
= iIdxCur
;
1816 pLevel
->p3
= (pLoop
->wsFlags
&WHERE_UNQ_WANTED
)!=0 ? 1:0;
1817 if( (pLoop
->wsFlags
& WHERE_CONSTRAINT
)==0 ){
1818 pLevel
->p5
= SQLITE_STMTSTATUS_FULLSCAN_STEP
;
1820 assert( pLevel
->p5
==0 );
1822 if( omitTable
) pIdx
= 0;
1825 #ifndef SQLITE_OMIT_OR_OPTIMIZATION
1826 if( pLoop
->wsFlags
& WHERE_MULTI_OR
){
1827 /* Case 5: Two or more separately indexed terms connected by OR
1831 ** CREATE TABLE t1(a,b,c,d);
1832 ** CREATE INDEX i1 ON t1(a);
1833 ** CREATE INDEX i2 ON t1(b);
1834 ** CREATE INDEX i3 ON t1(c);
1836 ** SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
1838 ** In the example, there are three indexed terms connected by OR.
1839 ** The top of the loop looks like this:
1841 ** Null 1 # Zero the rowset in reg 1
1843 ** Then, for each indexed term, the following. The arguments to
1844 ** RowSetTest are such that the rowid of the current row is inserted
1845 ** into the RowSet. If it is already present, control skips the
1846 ** Gosub opcode and jumps straight to the code generated by WhereEnd().
1848 ** sqlite3WhereBegin(<term>)
1849 ** RowSetTest # Insert rowid into rowset
1851 ** sqlite3WhereEnd()
1853 ** Following the above, code to terminate the loop. Label A, the target
1854 ** of the Gosub above, jumps to the instruction right after the Goto.
1856 ** Null 1 # Zero the rowset in reg 1
1857 ** Goto B # The loop is finished.
1859 ** A: <loop body> # Return data, whatever.
1861 ** Return 2 # Jump back to the Gosub
1863 ** B: <after the loop>
1865 ** Added 2014-05-26: If the table is a WITHOUT ROWID table, then
1866 ** use an ephemeral index instead of a RowSet to record the primary
1867 ** keys of the rows we have already seen.
1870 WhereClause
*pOrWc
; /* The OR-clause broken out into subterms */
1871 SrcList
*pOrTab
; /* Shortened table list or OR-clause generation */
1872 Index
*pCov
= 0; /* Potential covering index (or NULL) */
1873 int iCovCur
= pParse
->nTab
++; /* Cursor used for index scans (if any) */
1875 int regReturn
= ++pParse
->nMem
; /* Register used with OP_Gosub */
1876 int regRowset
= 0; /* Register for RowSet object */
1877 int regRowid
= 0; /* Register holding rowid */
1878 int iLoopBody
= sqlite3VdbeMakeLabel(pParse
);/* Start of loop body */
1879 int iRetInit
; /* Address of regReturn init */
1880 int untestedTerms
= 0; /* Some terms not completely tested */
1881 int ii
; /* Loop counter */
1882 u16 wctrlFlags
; /* Flags for sub-WHERE clause */
1883 Expr
*pAndExpr
= 0; /* An ".. AND (...)" expression */
1884 Table
*pTab
= pTabItem
->pTab
;
1886 pTerm
= pLoop
->aLTerm
[0];
1888 assert( pTerm
->eOperator
& WO_OR
);
1889 assert( (pTerm
->wtFlags
& TERM_ORINFO
)!=0 );
1890 pOrWc
= &pTerm
->u
.pOrInfo
->wc
;
1891 pLevel
->op
= OP_Return
;
1892 pLevel
->p1
= regReturn
;
1894 /* Set up a new SrcList in pOrTab containing the table being scanned
1895 ** by this loop in the a[0] slot and all notReady tables in a[1..] slots.
1896 ** This becomes the SrcList in the recursive call to sqlite3WhereBegin().
1898 if( pWInfo
->nLevel
>1 ){
1899 int nNotReady
; /* The number of notReady tables */
1900 struct SrcList_item
*origSrc
; /* Original list of tables */
1901 nNotReady
= pWInfo
->nLevel
- iLevel
- 1;
1902 pOrTab
= sqlite3StackAllocRaw(db
,
1903 sizeof(*pOrTab
)+ nNotReady
*sizeof(pOrTab
->a
[0]));
1904 if( pOrTab
==0 ) return notReady
;
1905 pOrTab
->nAlloc
= (u8
)(nNotReady
+ 1);
1906 pOrTab
->nSrc
= pOrTab
->nAlloc
;
1907 memcpy(pOrTab
->a
, pTabItem
, sizeof(*pTabItem
));
1908 origSrc
= pWInfo
->pTabList
->a
;
1909 for(k
=1; k
<=nNotReady
; k
++){
1910 memcpy(&pOrTab
->a
[k
], &origSrc
[pLevel
[k
].iFrom
], sizeof(pOrTab
->a
[k
]));
1913 pOrTab
= pWInfo
->pTabList
;
1916 /* Initialize the rowset register to contain NULL. An SQL NULL is
1917 ** equivalent to an empty rowset. Or, create an ephemeral index
1918 ** capable of holding primary keys in the case of a WITHOUT ROWID.
1920 ** Also initialize regReturn to contain the address of the instruction
1921 ** immediately following the OP_Return at the bottom of the loop. This
1922 ** is required in a few obscure LEFT JOIN cases where control jumps
1923 ** over the top of the loop into the body of it. In this case the
1924 ** correct response for the end-of-loop code (the OP_Return) is to
1925 ** fall through to the next instruction, just as an OP_Next does if
1926 ** called on an uninitialized cursor.
1928 if( (pWInfo
->wctrlFlags
& WHERE_DUPLICATES_OK
)==0 ){
1929 if( HasRowid(pTab
) ){
1930 regRowset
= ++pParse
->nMem
;
1931 sqlite3VdbeAddOp2(v
, OP_Null
, 0, regRowset
);
1933 Index
*pPk
= sqlite3PrimaryKeyIndex(pTab
);
1934 regRowset
= pParse
->nTab
++;
1935 sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, regRowset
, pPk
->nKeyCol
);
1936 sqlite3VdbeSetP4KeyInfo(pParse
, pPk
);
1938 regRowid
= ++pParse
->nMem
;
1940 iRetInit
= sqlite3VdbeAddOp2(v
, OP_Integer
, 0, regReturn
);
1942 /* If the original WHERE clause is z of the form: (x1 OR x2 OR ...) AND y
1943 ** Then for every term xN, evaluate as the subexpression: xN AND z
1944 ** That way, terms in y that are factored into the disjunction will
1945 ** be picked up by the recursive calls to sqlite3WhereBegin() below.
1947 ** Actually, each subexpression is converted to "xN AND w" where w is
1948 ** the "interesting" terms of z - terms that did not originate in the
1949 ** ON or USING clause of a LEFT JOIN, and terms that are usable as
1952 ** This optimization also only applies if the (x1 OR x2 OR ...) term
1953 ** is not contained in the ON clause of a LEFT JOIN.
1954 ** See ticket http://www.sqlite.org/src/info/f2369304e4
1958 for(iTerm
=0; iTerm
<pWC
->nTerm
; iTerm
++){
1959 Expr
*pExpr
= pWC
->a
[iTerm
].pExpr
;
1960 if( &pWC
->a
[iTerm
] == pTerm
) continue;
1961 testcase( pWC
->a
[iTerm
].wtFlags
& TERM_VIRTUAL
);
1962 testcase( pWC
->a
[iTerm
].wtFlags
& TERM_CODED
);
1963 if( (pWC
->a
[iTerm
].wtFlags
& (TERM_VIRTUAL
|TERM_CODED
))!=0 ) continue;
1964 if( (pWC
->a
[iTerm
].eOperator
& WO_ALL
)==0 ) continue;
1965 testcase( pWC
->a
[iTerm
].wtFlags
& TERM_ORINFO
);
1966 pExpr
= sqlite3ExprDup(db
, pExpr
, 0);
1967 pAndExpr
= sqlite3ExprAnd(pParse
, pAndExpr
, pExpr
);
1970 /* The extra 0x10000 bit on the opcode is masked off and does not
1971 ** become part of the new Expr.op. However, it does make the
1972 ** op==TK_AND comparison inside of sqlite3PExpr() false, and this
1973 ** prevents sqlite3PExpr() from implementing AND short-circuit
1974 ** optimization, which we do not want here. */
1975 pAndExpr
= sqlite3PExpr(pParse
, TK_AND
|0x10000, 0, pAndExpr
);
1979 /* Run a separate WHERE clause for each term of the OR clause. After
1980 ** eliminating duplicates from other WHERE clauses, the action for each
1981 ** sub-WHERE clause is to to invoke the main loop body as a subroutine.
1983 wctrlFlags
= WHERE_OR_SUBCLAUSE
| (pWInfo
->wctrlFlags
& WHERE_SEEK_TABLE
);
1984 ExplainQueryPlan((pParse
, 1, "MULTI-INDEX OR"));
1985 for(ii
=0; ii
<pOrWc
->nTerm
; ii
++){
1986 WhereTerm
*pOrTerm
= &pOrWc
->a
[ii
];
1987 if( pOrTerm
->leftCursor
==iCur
|| (pOrTerm
->eOperator
& WO_AND
)!=0 ){
1988 WhereInfo
*pSubWInfo
; /* Info for single OR-term scan */
1989 Expr
*pOrExpr
= pOrTerm
->pExpr
; /* Current OR clause term */
1990 int jmp1
= 0; /* Address of jump operation */
1991 assert( (pTabItem
[0].fg
.jointype
& JT_LEFT
)==0
1992 || ExprHasProperty(pOrExpr
, EP_FromJoin
)
1995 pAndExpr
->pLeft
= pOrExpr
;
1998 /* Loop through table entries that match term pOrTerm. */
1999 ExplainQueryPlan((pParse
, 1, "INDEX %d", ii
+1));
2000 WHERETRACE(0xffff, ("Subplan for OR-clause:\n"));
2001 pSubWInfo
= sqlite3WhereBegin(pParse
, pOrTab
, pOrExpr
, 0, 0,
2002 wctrlFlags
, iCovCur
);
2003 assert( pSubWInfo
|| pParse
->nErr
|| db
->mallocFailed
);
2005 WhereLoop
*pSubLoop
;
2006 int addrExplain
= sqlite3WhereExplainOneScan(
2007 pParse
, pOrTab
, &pSubWInfo
->a
[0], 0
2009 sqlite3WhereAddScanStatus(v
, pOrTab
, &pSubWInfo
->a
[0], addrExplain
);
2011 /* This is the sub-WHERE clause body. First skip over
2012 ** duplicate rows from prior sub-WHERE clauses, and record the
2013 ** rowid (or PRIMARY KEY) for the current row so that the same
2014 ** row will be skipped in subsequent sub-WHERE clauses.
2016 if( (pWInfo
->wctrlFlags
& WHERE_DUPLICATES_OK
)==0 ){
2017 int iSet
= ((ii
==pOrWc
->nTerm
-1)?-1:ii
);
2018 if( HasRowid(pTab
) ){
2019 sqlite3ExprCodeGetColumnOfTable(v
, pTab
, iCur
, -1, regRowid
);
2020 jmp1
= sqlite3VdbeAddOp4Int(v
, OP_RowSetTest
, regRowset
, 0,
2024 Index
*pPk
= sqlite3PrimaryKeyIndex(pTab
);
2025 int nPk
= pPk
->nKeyCol
;
2029 /* Read the PK into an array of temp registers. */
2030 r
= sqlite3GetTempRange(pParse
, nPk
);
2031 for(iPk
=0; iPk
<nPk
; iPk
++){
2032 int iCol
= pPk
->aiColumn
[iPk
];
2033 sqlite3ExprCodeGetColumnOfTable(v
, pTab
, iCur
, iCol
, r
+iPk
);
2036 /* Check if the temp table already contains this key. If so,
2037 ** the row has already been included in the result set and
2038 ** can be ignored (by jumping past the Gosub below). Otherwise,
2039 ** insert the key into the temp table and proceed with processing
2042 ** Use some of the same optimizations as OP_RowSetTest: If iSet
2043 ** is zero, assume that the key cannot already be present in
2044 ** the temp table. And if iSet is -1, assume that there is no
2045 ** need to insert the key into the temp table, as it will never
2046 ** be tested for. */
2048 jmp1
= sqlite3VdbeAddOp4Int(v
, OP_Found
, regRowset
, 0, r
, nPk
);
2052 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, r
, nPk
, regRowid
);
2053 sqlite3VdbeAddOp4Int(v
, OP_IdxInsert
, regRowset
, regRowid
,
2055 if( iSet
) sqlite3VdbeChangeP5(v
, OPFLAG_USESEEKRESULT
);
2058 /* Release the array of temp registers */
2059 sqlite3ReleaseTempRange(pParse
, r
, nPk
);
2063 /* Invoke the main loop body as a subroutine */
2064 sqlite3VdbeAddOp2(v
, OP_Gosub
, regReturn
, iLoopBody
);
2066 /* Jump here (skipping the main loop body subroutine) if the
2067 ** current sub-WHERE row is a duplicate from prior sub-WHEREs. */
2068 if( jmp1
) sqlite3VdbeJumpHere(v
, jmp1
);
2070 /* The pSubWInfo->untestedTerms flag means that this OR term
2071 ** contained one or more AND term from a notReady table. The
2072 ** terms from the notReady table could not be tested and will
2073 ** need to be tested later.
2075 if( pSubWInfo
->untestedTerms
) untestedTerms
= 1;
2077 /* If all of the OR-connected terms are optimized using the same
2078 ** index, and the index is opened using the same cursor number
2079 ** by each call to sqlite3WhereBegin() made by this loop, it may
2080 ** be possible to use that index as a covering index.
2082 ** If the call to sqlite3WhereBegin() above resulted in a scan that
2083 ** uses an index, and this is either the first OR-connected term
2084 ** processed or the index is the same as that used by all previous
2085 ** terms, set pCov to the candidate covering index. Otherwise, set
2086 ** pCov to NULL to indicate that no candidate covering index will
2089 pSubLoop
= pSubWInfo
->a
[0].pWLoop
;
2090 assert( (pSubLoop
->wsFlags
& WHERE_AUTO_INDEX
)==0 );
2091 if( (pSubLoop
->wsFlags
& WHERE_INDEXED
)!=0
2092 && (ii
==0 || pSubLoop
->u
.btree
.pIndex
==pCov
)
2093 && (HasRowid(pTab
) || !IsPrimaryKeyIndex(pSubLoop
->u
.btree
.pIndex
))
2095 assert( pSubWInfo
->a
[0].iIdxCur
==iCovCur
);
2096 pCov
= pSubLoop
->u
.btree
.pIndex
;
2101 /* Finish the loop through table entries that match term pOrTerm. */
2102 sqlite3WhereEnd(pSubWInfo
);
2103 ExplainQueryPlanPop(pParse
);
2107 ExplainQueryPlanPop(pParse
);
2108 pLevel
->u
.pCovidx
= pCov
;
2109 if( pCov
) pLevel
->iIdxCur
= iCovCur
;
2111 pAndExpr
->pLeft
= 0;
2112 sqlite3ExprDelete(db
, pAndExpr
);
2114 sqlite3VdbeChangeP1(v
, iRetInit
, sqlite3VdbeCurrentAddr(v
));
2115 sqlite3VdbeGoto(v
, pLevel
->addrBrk
);
2116 sqlite3VdbeResolveLabel(v
, iLoopBody
);
2118 if( pWInfo
->nLevel
>1 ){ sqlite3StackFree(db
, pOrTab
); }
2119 if( !untestedTerms
) disableTerm(pLevel
, pTerm
);
2121 #endif /* SQLITE_OMIT_OR_OPTIMIZATION */
2124 /* Case 6: There is no usable index. We must do a complete
2125 ** scan of the entire table.
2127 static const u8 aStep
[] = { OP_Next
, OP_Prev
};
2128 static const u8 aStart
[] = { OP_Rewind
, OP_Last
};
2129 assert( bRev
==0 || bRev
==1 );
2130 if( pTabItem
->fg
.isRecursive
){
2131 /* Tables marked isRecursive have only a single row that is stored in
2132 ** a pseudo-cursor. No need to Rewind or Next such cursors. */
2133 pLevel
->op
= OP_Noop
;
2135 codeCursorHint(pTabItem
, pWInfo
, pLevel
, 0);
2136 pLevel
->op
= aStep
[bRev
];
2138 pLevel
->p2
= 1 + sqlite3VdbeAddOp2(v
, aStart
[bRev
], iCur
, addrHalt
);
2139 VdbeCoverageIf(v
, bRev
==0);
2140 VdbeCoverageIf(v
, bRev
!=0);
2141 pLevel
->p5
= SQLITE_STMTSTATUS_FULLSCAN_STEP
;
2145 #ifdef SQLITE_ENABLE_STMT_SCANSTATUS
2146 pLevel
->addrVisit
= sqlite3VdbeCurrentAddr(v
);
2149 /* Insert code to test every subexpression that can be completely
2150 ** computed using the current set of tables.
2152 ** This loop may run between one and three times, depending on the
2153 ** constraints to be generated. The value of stack variable iLoop
2154 ** determines the constraints coded by each iteration, as follows:
2156 ** iLoop==1: Code only expressions that are entirely covered by pIdx.
2157 ** iLoop==2: Code remaining expressions that do not contain correlated
2159 ** iLoop==3: Code all remaining expressions.
2161 ** An effort is made to skip unnecessary iterations of the loop.
2163 iLoop
= (pIdx
? 1 : 2);
2165 int iNext
= 0; /* Next value for iLoop */
2166 for(pTerm
=pWC
->a
, j
=pWC
->nTerm
; j
>0; j
--, pTerm
++){
2168 int skipLikeAddr
= 0;
2169 testcase( pTerm
->wtFlags
& TERM_VIRTUAL
);
2170 testcase( pTerm
->wtFlags
& TERM_CODED
);
2171 if( pTerm
->wtFlags
& (TERM_VIRTUAL
|TERM_CODED
) ) continue;
2172 if( (pTerm
->prereqAll
& pLevel
->notReady
)!=0 ){
2173 testcase( pWInfo
->untestedTerms
==0
2174 && (pWInfo
->wctrlFlags
& WHERE_OR_SUBCLAUSE
)!=0 );
2175 pWInfo
->untestedTerms
= 1;
2180 if( (pTabItem
->fg
.jointype
&JT_LEFT
) && !ExprHasProperty(pE
,EP_FromJoin
) ){
2184 if( iLoop
==1 && !sqlite3ExprCoveredByIndex(pE
, pLevel
->iTabCur
, pIdx
) ){
2188 if( iLoop
<3 && (pTerm
->wtFlags
& TERM_VARSELECT
) ){
2189 if( iNext
==0 ) iNext
= 3;
2193 if( (pTerm
->wtFlags
& TERM_LIKECOND
)!=0 ){
2194 /* If the TERM_LIKECOND flag is set, that means that the range search
2195 ** is sufficient to guarantee that the LIKE operator is true, so we
2196 ** can skip the call to the like(A,B) function. But this only works
2197 ** for strings. So do not skip the call to the function on the pass
2198 ** that compares BLOBs. */
2199 #ifdef SQLITE_LIKE_DOESNT_MATCH_BLOBS
2202 u32 x
= pLevel
->iLikeRepCntr
;
2204 skipLikeAddr
= sqlite3VdbeAddOp1(v
, (x
&1)?OP_IfNot
:OP_If
,(int)(x
>>1));
2205 VdbeCoverageIf(v
, (x
&1)==1);
2206 VdbeCoverageIf(v
, (x
&1)==0);
2210 #ifdef WHERETRACE_ENABLED /* 0xffff */
2211 if( sqlite3WhereTrace
){
2212 VdbeNoopComment((v
, "WhereTerm[%d] (%p) priority=%d",
2213 pWC
->nTerm
-j
, pTerm
, iLoop
));
2216 sqlite3ExprIfFalse(pParse
, pE
, addrCont
, SQLITE_JUMPIFNULL
);
2217 if( skipLikeAddr
) sqlite3VdbeJumpHere(v
, skipLikeAddr
);
2218 pTerm
->wtFlags
|= TERM_CODED
;
2223 /* Insert code to test for implied constraints based on transitivity
2224 ** of the "==" operator.
2226 ** Example: If the WHERE clause contains "t1.a=t2.b" and "t2.b=123"
2227 ** and we are coding the t1 loop and the t2 loop has not yet coded,
2228 ** then we cannot use the "t1.a=t2.b" constraint, but we can code
2229 ** the implied "t1.a=123" constraint.
2231 for(pTerm
=pWC
->a
, j
=pWC
->nTerm
; j
>0; j
--, pTerm
++){
2234 if( pTerm
->wtFlags
& (TERM_VIRTUAL
|TERM_CODED
) ) continue;
2235 if( (pTerm
->eOperator
& (WO_EQ
|WO_IS
))==0 ) continue;
2236 if( (pTerm
->eOperator
& WO_EQUIV
)==0 ) continue;
2237 if( pTerm
->leftCursor
!=iCur
) continue;
2238 if( pLevel
->iLeftJoin
) continue;
2240 assert( !ExprHasProperty(pE
, EP_FromJoin
) );
2241 assert( (pTerm
->prereqRight
& pLevel
->notReady
)!=0 );
2242 pAlt
= sqlite3WhereFindTerm(pWC
, iCur
, pTerm
->u
.leftColumn
, notReady
,
2243 WO_EQ
|WO_IN
|WO_IS
, 0);
2244 if( pAlt
==0 ) continue;
2245 if( pAlt
->wtFlags
& (TERM_CODED
) ) continue;
2246 if( (pAlt
->eOperator
& WO_IN
)
2247 && (pAlt
->pExpr
->flags
& EP_xIsSelect
)
2248 && (pAlt
->pExpr
->x
.pSelect
->pEList
->nExpr
>1)
2252 testcase( pAlt
->eOperator
& WO_EQ
);
2253 testcase( pAlt
->eOperator
& WO_IS
);
2254 testcase( pAlt
->eOperator
& WO_IN
);
2255 VdbeModuleComment((v
, "begin transitive constraint"));
2256 sEAlt
= *pAlt
->pExpr
;
2257 sEAlt
.pLeft
= pE
->pLeft
;
2258 sqlite3ExprIfFalse(pParse
, &sEAlt
, addrCont
, SQLITE_JUMPIFNULL
);
2261 /* For a LEFT OUTER JOIN, generate code that will record the fact that
2262 ** at least one row of the right table has matched the left table.
2264 if( pLevel
->iLeftJoin
){
2265 pLevel
->addrFirst
= sqlite3VdbeCurrentAddr(v
);
2266 sqlite3VdbeAddOp2(v
, OP_Integer
, 1, pLevel
->iLeftJoin
);
2267 VdbeComment((v
, "record LEFT JOIN hit"));
2268 for(pTerm
=pWC
->a
, j
=0; j
<pWC
->nTerm
; j
++, pTerm
++){
2269 testcase( pTerm
->wtFlags
& TERM_VIRTUAL
);
2270 testcase( pTerm
->wtFlags
& TERM_CODED
);
2271 if( pTerm
->wtFlags
& (TERM_VIRTUAL
|TERM_CODED
) ) continue;
2272 if( (pTerm
->prereqAll
& pLevel
->notReady
)!=0 ){
2273 assert( pWInfo
->untestedTerms
);
2276 assert( pTerm
->pExpr
);
2277 sqlite3ExprIfFalse(pParse
, pTerm
->pExpr
, addrCont
, SQLITE_JUMPIFNULL
);
2278 pTerm
->wtFlags
|= TERM_CODED
;
2282 return pLevel
->notReady
;