1/*
2** 2015-06-06
3**
4** The author disclaims copyright to this source code. In place of
5** a legal notice, here is a blessing:
6**
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.
10**
11*************************************************************************
12** This module contains C code that generates VDBE code used to process
13** the WHERE clause of SQL statements.
14**
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.
19*/
20#include "sqliteInt.h"
21#include "whereInt.h"
22
23#ifndef SQLITE_OMIT_EXPLAIN
24
25/*
26** Return the name of the i-th column of the pIdx index.
27*/
28static 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].zCnName;
33}
34
35/*
36** This routine is a helper for explainIndexRange() below
37**
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
41** terms only.
42*/
43static 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 */
50){
51 int i;
52
53 assert( nTerm>=1 );
54 if( bAnd ) sqlite3_str_append(pStr, " AND ", 5);
55
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));
60 }
61 if( nTerm>1 ) sqlite3_str_append(pStr, ")", 1);
62
63 sqlite3_str_append(pStr, zOp, 1);
64
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);
69 }
70 if( nTerm>1 ) sqlite3_str_append(pStr, ")", 1);
71}
72
73/*
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.
77**
78** For example, if the query:
79**
80** SELECT * FROM t1 WHERE a=1 AND b>2;
81**
82** is run and there is an index on (a, b), then this function returns a
83** string similar to:
84**
85** "a=? AND b>?"
86*/
87static 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;
91 int i, j;
92
93 if( nEq==0 && (pLoop->wsFlags&(WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))==0 ) return;
94 sqlite3_str_append(pStr, " (", 2);
95 for(i=0; i<nEq; i++){
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);
99 }
100
101 j = i;
102 if( pLoop->wsFlags&WHERE_BTM_LIMIT ){
103 explainAppendTerm(pStr, pIndex, pLoop->u.btree.nBtm, j, i, ">");
104 i = 1;
105 }
106 if( pLoop->wsFlags&WHERE_TOP_LIMIT ){
107 explainAppendTerm(pStr, pIndex, pLoop->u.btree.nTop, j, i, "<");
108 }
109 sqlite3_str_append(pStr, ")", 1);
110}
111
112/*
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.
117**
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.
120*/
121int 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() */
126){
127 int ret = 0;
128#if !defined(SQLITE_DEBUG) && !defined(SQLITE_ENABLE_STMT_SCANSTATUS)
129 if( sqlite3ParseToplevel(pParse)->explain==2 )
130#endif
131 {
132 SrcItem *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 */
141
142 pLoop = pLevel->pWLoop;
143 flags = pLoop->wsFlags;
144 if( (flags&WHERE_MULTI_OR) || (wctrlFlags&WHERE_OR_SUBCLAUSE) ) return 0;
145
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));
149
150 sqlite3StrAccumInit(&str, db, zBuf, sizeof(zBuf), SQLITE_MAX_LENGTH);
151 str.printfFlags = SQLITE_PRINTF_INTERNAL;
152 sqlite3_str_appendf(&str, "%s %S", isSearch ? "SEARCH" : "SCAN", pItem);
153 if( (flags & (WHERE_IPK|WHERE_VIRTUALTABLE))==0 ){
154 const char *zFmt = 0;
155 Index *pIdx;
156
157 assert( pLoop->u.btree.pIndex!=0 );
158 pIdx = pLoop->u.btree.pIndex;
159 assert( !(flags&WHERE_AUTO_INDEX) || (flags&WHERE_IDX_ONLY) );
160 if( !HasRowid(pItem->pTab) && IsPrimaryKeyIndex(pIdx) ){
161 if( isSearch ){
162 zFmt = "PRIMARY KEY";
163 }
164 }else if( flags & WHERE_PARTIALIDX ){
165 zFmt = "AUTOMATIC PARTIAL COVERING INDEX";
166 }else if( flags & WHERE_AUTO_INDEX ){
167 zFmt = "AUTOMATIC COVERING INDEX";
168 }else if( flags & WHERE_IDX_ONLY ){
169 zFmt = "COVERING INDEX %s";
170 }else{
171 zFmt = "INDEX %s";
172 }
173 if( zFmt ){
174 sqlite3_str_append(&str, " USING ", 7);
175 sqlite3_str_appendf(&str, zFmt, pIdx->zName);
176 explainIndexRange(&str, pLoop);
177 }
178 }else if( (flags & WHERE_IPK)!=0 && (flags & WHERE_CONSTRAINT)!=0 ){
179 char cRangeOp;
180#if 0 /* Better output, but breaks many tests */
181 const Table *pTab = pItem->pTab;
182 const char *zRowid = pTab->iPKey>=0 ? pTab->aCol[pTab->iPKey].zCnName:
183 "rowid";
184#else
185 const char *zRowid = "rowid";
186#endif
187 sqlite3_str_appendf(&str, " USING INTEGER PRIMARY KEY (%s", zRowid);
188 if( flags&(WHERE_COLUMN_EQ|WHERE_COLUMN_IN) ){
189 cRangeOp = '=';
190 }else if( (flags&WHERE_BOTH_LIMIT)==WHERE_BOTH_LIMIT ){
191 sqlite3_str_appendf(&str, ">? AND %s", zRowid);
192 cRangeOp = '<';
193 }else if( flags&WHERE_BTM_LIMIT ){
194 cRangeOp = '>';
195 }else{
196 assert( flags&WHERE_TOP_LIMIT);
197 cRangeOp = '<';
198 }
199 sqlite3_str_appendf(&str, "%c?)", cRangeOp);
200 }
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);
205 }
206#endif
207 if( pItem->fg.jointype & JT_LEFT ){
208 sqlite3_str_appendf(&str, " LEFT-JOIN");
209 }
210#ifdef SQLITE_EXPLAIN_ESTIMATED_ROWS
211 if( pLoop->nOut>=10 ){
212 sqlite3_str_appendf(&str, " (~%llu rows)",
213 sqlite3LogEstToInt(pLoop->nOut));
214 }else{
215 sqlite3_str_append(&str, " (~1 row)", 9);
216 }
217#endif
218 zMsg = sqlite3StrAccumFinish(&str);
219 sqlite3ExplainBreakpoint("",zMsg);
220 ret = sqlite3VdbeAddOp4(v, OP_Explain, sqlite3VdbeCurrentAddr(v),
221 pParse->addrExplain, 0, zMsg,P4_DYNAMIC);
222 }
223 return ret;
224}
225
226/*
227** Add a single OP_Explain opcode that describes a Bloom filter.
228**
229** Or if not processing EXPLAIN QUERY PLAN and not in a SQLITE_DEBUG and/or
230** SQLITE_ENABLE_STMT_SCANSTATUS build, then OP_Explain opcodes are not
231** required and this routine is a no-op.
232**
233** If an OP_Explain opcode is added to the VM, its address is returned.
234** Otherwise, if no OP_Explain is coded, zero is returned.
235*/
236int sqlite3WhereExplainBloomFilter(
237 const Parse *pParse, /* Parse context */
238 const WhereInfo *pWInfo, /* WHERE clause */
239 const WhereLevel *pLevel /* Bloom filter on this level */
240){
241 int ret = 0;
242 SrcItem *pItem = &pWInfo->pTabList->a[pLevel->iFrom];
243 Vdbe *v = pParse->pVdbe; /* VM being constructed */
244 sqlite3 *db = pParse->db; /* Database handle */
245 char *zMsg; /* Text to add to EQP output */
246 int i; /* Loop counter */
247 WhereLoop *pLoop; /* The where loop */
248 StrAccum str; /* EQP output string */
249 char zBuf[100]; /* Initial space for EQP output string */
250
251 sqlite3StrAccumInit(&str, db, zBuf, sizeof(zBuf), SQLITE_MAX_LENGTH);
252 str.printfFlags = SQLITE_PRINTF_INTERNAL;
253 sqlite3_str_appendf(&str, "BLOOM FILTER ON %S (", pItem);
254 pLoop = pLevel->pWLoop;
255 if( pLoop->wsFlags & WHERE_IPK ){
256 const Table *pTab = pItem->pTab;
257 if( pTab->iPKey>=0 ){
258 sqlite3_str_appendf(&str, "%s=?", pTab->aCol[pTab->iPKey].zCnName);
259 }else{
260 sqlite3_str_appendf(&str, "rowid=?");
261 }
262 }else{
263 for(i=pLoop->nSkip; i<pLoop->u.btree.nEq; i++){
264 const char *z = explainIndexColumnName(pLoop->u.btree.pIndex, i);
265 if( i>pLoop->nSkip ) sqlite3_str_append(&str, " AND ", 5);
266 sqlite3_str_appendf(&str, "%s=?", z);
267 }
268 }
269 sqlite3_str_append(&str, ")", 1);
270 zMsg = sqlite3StrAccumFinish(&str);
271 ret = sqlite3VdbeAddOp4(v, OP_Explain, sqlite3VdbeCurrentAddr(v),
272 pParse->addrExplain, 0, zMsg,P4_DYNAMIC);
273 return ret;
274}
275#endif /* SQLITE_OMIT_EXPLAIN */
276
277#ifdef SQLITE_ENABLE_STMT_SCANSTATUS
278/*
279** Configure the VM passed as the first argument with an
280** sqlite3_stmt_scanstatus() entry corresponding to the scan used to
281** implement level pLvl. Argument pSrclist is a pointer to the FROM
282** clause that the scan reads data from.
283**
284** If argument addrExplain is not 0, it must be the address of an
285** OP_Explain instruction that describes the same loop.
286*/
287void sqlite3WhereAddScanStatus(
288 Vdbe *v, /* Vdbe to add scanstatus entry to */
289 SrcList *pSrclist, /* FROM clause pLvl reads data from */
290 WhereLevel *pLvl, /* Level to add scanstatus() entry for */
291 int addrExplain /* Address of OP_Explain (or 0) */
292){
293 const char *zObj = 0;
294 WhereLoop *pLoop = pLvl->pWLoop;
295 if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 && pLoop->u.btree.pIndex!=0 ){
296 zObj = pLoop->u.btree.pIndex->zName;
297 }else{
298 zObj = pSrclist->a[pLvl->iFrom].zName;
299 }
300 sqlite3VdbeScanStatus(
301 v, addrExplain, pLvl->addrBody, pLvl->addrVisit, pLoop->nOut, zObj
302 );
303}
304#endif
305
306
307/*
308** Disable a term in the WHERE clause. Except, do not disable the term
309** if it controls a LEFT OUTER JOIN and it did not originate in the ON
310** or USING clause of that join.
311**
312** Consider the term t2.z='ok' in the following queries:
313**
314** (1) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok'
315** (2) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok'
316** (3) SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok'
317**
318** The t2.z='ok' is disabled in the in (2) because it originates
319** in the ON clause. The term is disabled in (3) because it is not part
320** of a LEFT OUTER JOIN. In (1), the term is not disabled.
321**
322** Disabling a term causes that term to not be tested in the inner loop
323** of the join. Disabling is an optimization. When terms are satisfied
324** by indices, we disable them to prevent redundant tests in the inner
325** loop. We would get the correct results if nothing were ever disabled,
326** but joins might run a little slower. The trick is to disable as much
327** as we can without disabling too much. If we disabled in (1), we'd get
328** the wrong answer. See ticket #813.
329**
330** If all the children of a term are disabled, then that term is also
331** automatically disabled. In this way, terms get disabled if derived
332** virtual terms are tested first. For example:
333**
334** x GLOB 'abc*' AND x>='abc' AND x<'acd'
335** \___________/ \______/ \_____/
336** parent child1 child2
337**
338** Only the parent term was in the original WHERE clause. The child1
339** and child2 terms were added by the LIKE optimization. If both of
340** the virtual child terms are valid, then testing of the parent can be
341** skipped.
342**
343** Usually the parent term is marked as TERM_CODED. But if the parent
344** term was originally TERM_LIKE, then the parent gets TERM_LIKECOND instead.
345** The TERM_LIKECOND marking indicates that the term should be coded inside
346** a conditional such that is only evaluated on the second pass of a
347** LIKE-optimization loop, when scanning BLOBs instead of strings.
348*/
349static void disableTerm(WhereLevel *pLevel, WhereTerm *pTerm){
350 int nLoop = 0;
351 assert( pTerm!=0 );
352 while( (pTerm->wtFlags & TERM_CODED)==0
353 && (pLevel->iLeftJoin==0 || ExprHasProperty(pTerm->pExpr, EP_OuterON))
354 && (pLevel->notReady & pTerm->prereqAll)==0
355 ){
356 if( nLoop && (pTerm->wtFlags & TERM_LIKE)!=0 ){
357 pTerm->wtFlags |= TERM_LIKECOND;
358 }else{
359 pTerm->wtFlags |= TERM_CODED;
360 }
361#ifdef WHERETRACE_ENABLED
362 if( sqlite3WhereTrace & 0x20000 ){
363 sqlite3DebugPrintf("DISABLE-");
364 sqlite3WhereTermPrint(pTerm, (int)(pTerm - (pTerm->pWC->a)));
365 }
366#endif
367 if( pTerm->iParent<0 ) break;
368 pTerm = &pTerm->pWC->a[pTerm->iParent];
369 assert( pTerm!=0 );
370 pTerm->nChild--;
371 if( pTerm->nChild!=0 ) break;
372 nLoop++;
373 }
374}
375
376/*
377** Code an OP_Affinity opcode to apply the column affinity string zAff
378** to the n registers starting at base.
379**
380** As an optimization, SQLITE_AFF_BLOB and SQLITE_AFF_NONE entries (which
381** are no-ops) at the beginning and end of zAff are ignored. If all entries
382** in zAff are SQLITE_AFF_BLOB or SQLITE_AFF_NONE, then no code gets generated.
383**
384** This routine makes its own copy of zAff so that the caller is free
385** to modify zAff after this routine returns.
386*/
387static void codeApplyAffinity(Parse *pParse, int base, int n, char *zAff){
388 Vdbe *v = pParse->pVdbe;
389 if( zAff==0 ){
390 assert( pParse->db->mallocFailed );
391 return;
392 }
393 assert( v!=0 );
394
395 /* Adjust base and n to skip over SQLITE_AFF_BLOB and SQLITE_AFF_NONE
396 ** entries at the beginning and end of the affinity string.
397 */
398 assert( SQLITE_AFF_NONE<SQLITE_AFF_BLOB );
399 while( n>0 && zAff[0]<=SQLITE_AFF_BLOB ){
400 n--;
401 base++;
402 zAff++;
403 }
404 while( n>1 && zAff[n-1]<=SQLITE_AFF_BLOB ){
405 n--;
406 }
407
408 /* Code the OP_Affinity opcode if there is anything left to do. */
409 if( n>0 ){
410 sqlite3VdbeAddOp4(v, OP_Affinity, base, n, 0, zAff, n);
411 }
412}
413
414/*
415** Expression pRight, which is the RHS of a comparison operation, is
416** either a vector of n elements or, if n==1, a scalar expression.
417** Before the comparison operation, affinity zAff is to be applied
418** to the pRight values. This function modifies characters within the
419** affinity string to SQLITE_AFF_BLOB if either:
420**
421** * the comparison will be performed with no affinity, or
422** * the affinity change in zAff is guaranteed not to change the value.
423*/
424static void updateRangeAffinityStr(
425 Expr *pRight, /* RHS of comparison */
426 int n, /* Number of vector elements in comparison */
427 char *zAff /* Affinity string to modify */
428){
429 int i;
430 for(i=0; i<n; i++){
431 Expr *p = sqlite3VectorFieldSubexpr(pRight, i);
432 if( sqlite3CompareAffinity(p, zAff[i])==SQLITE_AFF_BLOB
433 || sqlite3ExprNeedsNoAffinityChange(p, zAff[i])
434 ){
435 zAff[i] = SQLITE_AFF_BLOB;
436 }
437 }
438}
439
440
441/*
442** pX is an expression of the form: (vector) IN (SELECT ...)
443** In other words, it is a vector IN operator with a SELECT clause on the
444** LHS. But not all terms in the vector are indexable and the terms might
445** not be in the correct order for indexing.
446**
447** This routine makes a copy of the input pX expression and then adjusts
448** the vector on the LHS with corresponding changes to the SELECT so that
449** the vector contains only index terms and those terms are in the correct
450** order. The modified IN expression is returned. The caller is responsible
451** for deleting the returned expression.
452**
453** Example:
454**
455** CREATE TABLE t1(a,b,c,d,e,f);
456** CREATE INDEX t1x1 ON t1(e,c);
457** SELECT * FROM t1 WHERE (a,b,c,d,e) IN (SELECT v,w,x,y,z FROM t2)
458** \_______________________________________/
459** The pX expression
460**
461** Since only columns e and c can be used with the index, in that order,
462** the modified IN expression that is returned will be:
463**
464** (e,c) IN (SELECT z,x FROM t2)
465**
466** The reduced pX is different from the original (obviously) and thus is
467** only used for indexing, to improve performance. The original unaltered
468** IN expression must also be run on each output row for correctness.
469*/
470static Expr *removeUnindexableInClauseTerms(
471 Parse *pParse, /* The parsing context */
472 int iEq, /* Look at loop terms starting here */
473 WhereLoop *pLoop, /* The current loop */
474 Expr *pX /* The IN expression to be reduced */
475){
476 sqlite3 *db = pParse->db;
477 Expr *pNew;
478 pNew = sqlite3ExprDup(db, pX, 0);
479 if( db->mallocFailed==0 ){
480 ExprList *pOrigRhs; /* Original unmodified RHS */
481 ExprList *pOrigLhs; /* Original unmodified LHS */
482 ExprList *pRhs = 0; /* New RHS after modifications */
483 ExprList *pLhs = 0; /* New LHS after mods */
484 int i; /* Loop counter */
485 Select *pSelect; /* Pointer to the SELECT on the RHS */
486
487 assert( ExprUseXSelect(pNew) );
488 pOrigRhs = pNew->x.pSelect->pEList;
489 assert( pNew->pLeft!=0 );
490 assert( ExprUseXList(pNew->pLeft) );
491 pOrigLhs = pNew->pLeft->x.pList;
492 for(i=iEq; i<pLoop->nLTerm; i++){
493 if( pLoop->aLTerm[i]->pExpr==pX ){
494 int iField;
495 assert( (pLoop->aLTerm[i]->eOperator & (WO_OR|WO_AND))==0 );
496 iField = pLoop->aLTerm[i]->u.x.iField - 1;
497 if( pOrigRhs->a[iField].pExpr==0 ) continue; /* Duplicate PK column */
498 pRhs = sqlite3ExprListAppend(pParse, pRhs, pOrigRhs->a[iField].pExpr);
499 pOrigRhs->a[iField].pExpr = 0;
500 assert( pOrigLhs->a[iField].pExpr!=0 );
501 pLhs = sqlite3ExprListAppend(pParse, pLhs, pOrigLhs->a[iField].pExpr);
502 pOrigLhs->a[iField].pExpr = 0;
503 }
504 }
505 sqlite3ExprListDelete(db, pOrigRhs);
506 sqlite3ExprListDelete(db, pOrigLhs);
507 pNew->pLeft->x.pList = pLhs;
508 pNew->x.pSelect->pEList = pRhs;
509 if( pLhs && pLhs->nExpr==1 ){
510 /* Take care here not to generate a TK_VECTOR containing only a
511 ** single value. Since the parser never creates such a vector, some
512 ** of the subroutines do not handle this case. */
513 Expr *p = pLhs->a[0].pExpr;
514 pLhs->a[0].pExpr = 0;
515 sqlite3ExprDelete(db, pNew->pLeft);
516 pNew->pLeft = p;
517 }
518 pSelect = pNew->x.pSelect;
519 if( pSelect->pOrderBy ){
520 /* If the SELECT statement has an ORDER BY clause, zero the
521 ** iOrderByCol variables. These are set to non-zero when an
522 ** ORDER BY term exactly matches one of the terms of the
523 ** result-set. Since the result-set of the SELECT statement may
524 ** have been modified or reordered, these variables are no longer
525 ** set correctly. Since setting them is just an optimization,
526 ** it's easiest just to zero them here. */
527 ExprList *pOrderBy = pSelect->pOrderBy;
528 for(i=0; i<pOrderBy->nExpr; i++){
529 pOrderBy->a[i].u.x.iOrderByCol = 0;
530 }
531 }
532
533#if 0
534 printf("For indexing, change the IN expr:\n");
535 sqlite3TreeViewExpr(0, pX, 0);
536 printf("Into:\n");
537 sqlite3TreeViewExpr(0, pNew, 0);
538#endif
539 }
540 return pNew;
541}
542
543
544/*
545** Generate code for a single equality term of the WHERE clause. An equality
546** term can be either X=expr or X IN (...). pTerm is the term to be
547** coded.
548**
549** The current value for the constraint is left in a register, the index
550** of which is returned. An attempt is made store the result in iTarget but
551** this is only guaranteed for TK_ISNULL and TK_IN constraints. If the
552** constraint is a TK_EQ or TK_IS, then the current value might be left in
553** some other register and it is the caller's responsibility to compensate.
554**
555** For a constraint of the form X=expr, the expression is evaluated in
556** straight-line code. For constraints of the form X IN (...)
557** this routine sets up a loop that will iterate over all values of X.
558*/
559static int codeEqualityTerm(
560 Parse *pParse, /* The parsing context */
561 WhereTerm *pTerm, /* The term of the WHERE clause to be coded */
562 WhereLevel *pLevel, /* The level of the FROM clause we are working on */
563 int iEq, /* Index of the equality term within this level */
564 int bRev, /* True for reverse-order IN operations */
565 int iTarget /* Attempt to leave results in this register */
566){
567 Expr *pX = pTerm->pExpr;
568 Vdbe *v = pParse->pVdbe;
569 int iReg; /* Register holding results */
570
571 assert( pLevel->pWLoop->aLTerm[iEq]==pTerm );
572 assert( iTarget>0 );
573 if( pX->op==TK_EQ || pX->op==TK_IS ){
574 iReg = sqlite3ExprCodeTarget(pParse, pX->pRight, iTarget);
575 }else if( pX->op==TK_ISNULL ){
576 iReg = iTarget;
577 sqlite3VdbeAddOp2(v, OP_Null, 0, iReg);
578#ifndef SQLITE_OMIT_SUBQUERY
579 }else{
580 int eType = IN_INDEX_NOOP;
581 int iTab;
582 struct InLoop *pIn;
583 WhereLoop *pLoop = pLevel->pWLoop;
584 int i;
585 int nEq = 0;
586 int *aiMap = 0;
587
588 if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0
589 && pLoop->u.btree.pIndex!=0
590 && pLoop->u.btree.pIndex->aSortOrder[iEq]
591 ){
592 testcase( iEq==0 );
593 testcase( bRev );
594 bRev = !bRev;
595 }
596 assert( pX->op==TK_IN );
597 iReg = iTarget;
598
599 for(i=0; i<iEq; i++){
600 if( pLoop->aLTerm[i] && pLoop->aLTerm[i]->pExpr==pX ){
601 disableTerm(pLevel, pTerm);
602 return iTarget;
603 }
604 }
605 for(i=iEq;i<pLoop->nLTerm; i++){
606 assert( pLoop->aLTerm[i]!=0 );
607 if( pLoop->aLTerm[i]->pExpr==pX ) nEq++;
608 }
609
610 iTab = 0;
611 if( !ExprUseXSelect(pX) || pX->x.pSelect->pEList->nExpr==1 ){
612 eType = sqlite3FindInIndex(pParse, pX, IN_INDEX_LOOP, 0, 0, &iTab);
613 }else{
614 Expr *pExpr = pTerm->pExpr;
615 if( pExpr->iTable==0 || !ExprHasProperty(pExpr, EP_Subrtn) ){
616 sqlite3 *db = pParse->db;
617 pX = removeUnindexableInClauseTerms(pParse, iEq, pLoop, pX);
618 if( !db->mallocFailed ){
619 aiMap = (int*)sqlite3DbMallocZero(pParse->db, sizeof(int)*nEq);
620 eType = sqlite3FindInIndex(pParse, pX, IN_INDEX_LOOP, 0, aiMap,&iTab);
621 pExpr->iTable = iTab;
622 }
623 sqlite3ExprDelete(db, pX);
624 }else{
625 int n = sqlite3ExprVectorSize(pX->pLeft);
626 aiMap = (int*)sqlite3DbMallocZero(pParse->db, sizeof(int)*MAX(nEq,n));
627 eType = sqlite3FindInIndex(pParse, pX, IN_INDEX_LOOP, 0, aiMap, &iTab);
628 }
629 pX = pExpr;
630 }
631
632 if( eType==IN_INDEX_INDEX_DESC ){
633 testcase( bRev );
634 bRev = !bRev;
635 }
636 sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iTab, 0);
637 VdbeCoverageIf(v, bRev);
638 VdbeCoverageIf(v, !bRev);
639
640 assert( (pLoop->wsFlags & WHERE_MULTI_OR)==0 );
641 pLoop->wsFlags |= WHERE_IN_ABLE;
642 if( pLevel->u.in.nIn==0 ){
643 pLevel->addrNxt = sqlite3VdbeMakeLabel(pParse);
644 }
645 if( iEq>0 && (pLoop->wsFlags & WHERE_IN_SEEKSCAN)==0 ){
646 pLoop->wsFlags |= WHERE_IN_EARLYOUT;
647 }
648
649 i = pLevel->u.in.nIn;
650 pLevel->u.in.nIn += nEq;
651 pLevel->u.in.aInLoop =
652 sqlite3WhereRealloc(pTerm->pWC->pWInfo,
653 pLevel->u.in.aInLoop,
654 sizeof(pLevel->u.in.aInLoop[0])*pLevel->u.in.nIn);
655 pIn = pLevel->u.in.aInLoop;
656 if( pIn ){
657 int iMap = 0; /* Index in aiMap[] */
658 pIn += i;
659 for(i=iEq;i<pLoop->nLTerm; i++){
660 if( pLoop->aLTerm[i]->pExpr==pX ){
661 int iOut = iReg + i - iEq;
662 if( eType==IN_INDEX_ROWID ){
663 pIn->addrInTop = sqlite3VdbeAddOp2(v, OP_Rowid, iTab, iOut);
664 }else{
665 int iCol = aiMap ? aiMap[iMap++] : 0;
666 pIn->addrInTop = sqlite3VdbeAddOp3(v,OP_Column,iTab, iCol, iOut);
667 }
668 sqlite3VdbeAddOp1(v, OP_IsNull, iOut); VdbeCoverage(v);
669 if( i==iEq ){
670 pIn->iCur = iTab;
671 pIn->eEndLoopOp = bRev ? OP_Prev : OP_Next;
672 if( iEq>0 ){
673 pIn->iBase = iReg - i;
674 pIn->nPrefix = i;
675 }else{
676 pIn->nPrefix = 0;
677 }
678 }else{
679 pIn->eEndLoopOp = OP_Noop;
680 }
681 pIn++;
682 }
683 }
684 testcase( iEq>0
685 && (pLoop->wsFlags & WHERE_IN_SEEKSCAN)==0
686 && (pLoop->wsFlags & WHERE_VIRTUALTABLE)!=0 );
687 if( iEq>0
688 && (pLoop->wsFlags & (WHERE_IN_SEEKSCAN|WHERE_VIRTUALTABLE))==0
689 ){
690 sqlite3VdbeAddOp3(v, OP_SeekHit, pLevel->iIdxCur, 0, iEq);
691 }
692 }else{
693 pLevel->u.in.nIn = 0;
694 }
695 sqlite3DbFree(pParse->db, aiMap);
696#endif
697 }
698
699 /* As an optimization, try to disable the WHERE clause term that is
700 ** driving the index as it will always be true. The correct answer is
701 ** obtained regardless, but we might get the answer with fewer CPU cycles
702 ** by omitting the term.
703 **
704 ** But do not disable the term unless we are certain that the term is
705 ** not a transitive constraint. For an example of where that does not
706 ** work, see https://sqlite.org/forum/forumpost/eb8613976a (2021-05-04)
707 */
708 if( (pLevel->pWLoop->wsFlags & WHERE_TRANSCONS)==0
709 || (pTerm->eOperator & WO_EQUIV)==0
710 ){
711 disableTerm(pLevel, pTerm);
712 }
713
714 return iReg;
715}
716
717/*
718** Generate code that will evaluate all == and IN constraints for an
719** index scan.
720**
721** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c).
722** Suppose the WHERE clause is this: a==5 AND b IN (1,2,3) AND c>5 AND c<10
723** The index has as many as three equality constraints, but in this
724** example, the third "c" value is an inequality. So only two
725** constraints are coded. This routine will generate code to evaluate
726** a==5 and b IN (1,2,3). The current values for a and b will be stored
727** in consecutive registers and the index of the first register is returned.
728**
729** In the example above nEq==2. But this subroutine works for any value
730** of nEq including 0. If nEq==0, this routine is nearly a no-op.
731** The only thing it does is allocate the pLevel->iMem memory cell and
732** compute the affinity string.
733**
734** The nExtraReg parameter is 0 or 1. It is 0 if all WHERE clause constraints
735** are == or IN and are covered by the nEq. nExtraReg is 1 if there is
736** an inequality constraint (such as the "c>=5 AND c<10" in the example) that
737** occurs after the nEq quality constraints.
738**
739** This routine allocates a range of nEq+nExtraReg memory cells and returns
740** the index of the first memory cell in that range. The code that
741** calls this routine will use that memory range to store keys for
742** start and termination conditions of the loop.
743** key value of the loop. If one or more IN operators appear, then
744** this routine allocates an additional nEq memory cells for internal
745** use.
746**
747** Before returning, *pzAff is set to point to a buffer containing a
748** copy of the column affinity string of the index allocated using
749** sqlite3DbMalloc(). Except, entries in the copy of the string associated
750** with equality constraints that use BLOB or NONE affinity are set to
751** SQLITE_AFF_BLOB. This is to deal with SQL such as the following:
752**
753** CREATE TABLE t1(a TEXT PRIMARY KEY, b);
754** SELECT ... FROM t1 AS t2, t1 WHERE t1.a = t2.b;
755**
756** In the example above, the index on t1(a) has TEXT affinity. But since
757** the right hand side of the equality constraint (t2.b) has BLOB/NONE affinity,
758** no conversion should be attempted before using a t2.b value as part of
759** a key to search the index. Hence the first byte in the returned affinity
760** string in this example would be set to SQLITE_AFF_BLOB.
761*/
762static int codeAllEqualityTerms(
763 Parse *pParse, /* Parsing context */
764 WhereLevel *pLevel, /* Which nested loop of the FROM we are coding */
765 int bRev, /* Reverse the order of IN operators */
766 int nExtraReg, /* Number of extra registers to allocate */
767 char **pzAff /* OUT: Set to point to affinity string */
768){
769 u16 nEq; /* The number of == or IN constraints to code */
770 u16 nSkip; /* Number of left-most columns to skip */
771 Vdbe *v = pParse->pVdbe; /* The vm under construction */
772 Index *pIdx; /* The index being used for this loop */
773 WhereTerm *pTerm; /* A single constraint term */
774 WhereLoop *pLoop; /* The WhereLoop object */
775 int j; /* Loop counter */
776 int regBase; /* Base register */
777 int nReg; /* Number of registers to allocate */
778 char *zAff; /* Affinity string to return */
779
780 /* This module is only called on query plans that use an index. */
781 pLoop = pLevel->pWLoop;
782 assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 );
783 nEq = pLoop->u.btree.nEq;
784 nSkip = pLoop->nSkip;
785 pIdx = pLoop->u.btree.pIndex;
786 assert( pIdx!=0 );
787
788 /* Figure out how many memory cells we will need then allocate them.
789 */
790 regBase = pParse->nMem + 1;
791 nReg = pLoop->u.btree.nEq + nExtraReg;
792 pParse->nMem += nReg;
793
794 zAff = sqlite3DbStrDup(pParse->db,sqlite3IndexAffinityStr(pParse->db,pIdx));
795 assert( zAff!=0 || pParse->db->mallocFailed );
796
797 if( nSkip ){
798 int iIdxCur = pLevel->iIdxCur;
799 sqlite3VdbeAddOp3(v, OP_Null, 0, regBase, regBase+nSkip-1);
800 sqlite3VdbeAddOp1(v, (bRev?OP_Last:OP_Rewind), iIdxCur);
801 VdbeCoverageIf(v, bRev==0);
802 VdbeCoverageIf(v, bRev!=0);
803 VdbeComment((v, "begin skip-scan on %s", pIdx->zName));
804 j = sqlite3VdbeAddOp0(v, OP_Goto);
805 assert( pLevel->addrSkip==0 );
806 pLevel->addrSkip = sqlite3VdbeAddOp4Int(v, (bRev?OP_SeekLT:OP_SeekGT),
807 iIdxCur, 0, regBase, nSkip);
808 VdbeCoverageIf(v, bRev==0);
809 VdbeCoverageIf(v, bRev!=0);
810 sqlite3VdbeJumpHere(v, j);
811 for(j=0; j<nSkip; j++){
812 sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, j, regBase+j);
813 testcase( pIdx->aiColumn[j]==XN_EXPR );
814 VdbeComment((v, "%s", explainIndexColumnName(pIdx, j)));
815 }
816 }
817
818 /* Evaluate the equality constraints
819 */
820 assert( zAff==0 || (int)strlen(zAff)>=nEq );
821 for(j=nSkip; j<nEq; j++){
822 int r1;
823 pTerm = pLoop->aLTerm[j];
824 assert( pTerm!=0 );
825 /* The following testcase is true for indices with redundant columns.
826 ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */
827 testcase( (pTerm->wtFlags & TERM_CODED)!=0 );
828 testcase( pTerm->wtFlags & TERM_VIRTUAL );
829 r1 = codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, regBase+j);
830 if( r1!=regBase+j ){
831 if( nReg==1 ){
832 sqlite3ReleaseTempReg(pParse, regBase);
833 regBase = r1;
834 }else{
835 sqlite3VdbeAddOp2(v, OP_Copy, r1, regBase+j);
836 }
837 }
838 }
839 for(j=nSkip; j<nEq; j++){
840 pTerm = pLoop->aLTerm[j];
841 if( pTerm->eOperator & WO_IN ){
842 if( pTerm->pExpr->flags & EP_xIsSelect ){
843 /* No affinity ever needs to be (or should be) applied to a value
844 ** from the RHS of an "? IN (SELECT ...)" expression. The
845 ** sqlite3FindInIndex() routine has already ensured that the
846 ** affinity of the comparison has been applied to the value. */
847 if( zAff ) zAff[j] = SQLITE_AFF_BLOB;
848 }
849 }else if( (pTerm->eOperator & WO_ISNULL)==0 ){
850 Expr *pRight = pTerm->pExpr->pRight;
851 if( (pTerm->wtFlags & TERM_IS)==0 && sqlite3ExprCanBeNull(pRight) ){
852 sqlite3VdbeAddOp2(v, OP_IsNull, regBase+j, pLevel->addrBrk);
853 VdbeCoverage(v);
854 }
855 if( pParse->nErr==0 ){
856 assert( pParse->db->mallocFailed==0 );
857 if( sqlite3CompareAffinity(pRight, zAff[j])==SQLITE_AFF_BLOB ){
858 zAff[j] = SQLITE_AFF_BLOB;
859 }
860 if( sqlite3ExprNeedsNoAffinityChange(pRight, zAff[j]) ){
861 zAff[j] = SQLITE_AFF_BLOB;
862 }
863 }
864 }
865 }
866 *pzAff = zAff;
867 return regBase;
868}
869
870#ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
871/*
872** If the most recently coded instruction is a constant range constraint
873** (a string literal) that originated from the LIKE optimization, then
874** set P3 and P5 on the OP_String opcode so that the string will be cast
875** to a BLOB at appropriate times.
876**
877** The LIKE optimization trys to evaluate "x LIKE 'abc%'" as a range
878** expression: "x>='ABC' AND x<'abd'". But this requires that the range
879** scan loop run twice, once for strings and a second time for BLOBs.
880** The OP_String opcodes on the second pass convert the upper and lower
881** bound string constants to blobs. This routine makes the necessary changes
882** to the OP_String opcodes for that to happen.
883**
884** Except, of course, if SQLITE_LIKE_DOESNT_MATCH_BLOBS is defined, then
885** only the one pass through the string space is required, so this routine
886** becomes a no-op.
887*/
888static void whereLikeOptimizationStringFixup(
889 Vdbe *v, /* prepared statement under construction */
890 WhereLevel *pLevel, /* The loop that contains the LIKE operator */
891 WhereTerm *pTerm /* The upper or lower bound just coded */
892){
893 if( pTerm->wtFlags & TERM_LIKEOPT ){
894 VdbeOp *pOp;
895 assert( pLevel->iLikeRepCntr>0 );
896 pOp = sqlite3VdbeGetLastOp(v);
897 assert( pOp!=0 );
898 assert( pOp->opcode==OP_String8
899 || pTerm->pWC->pWInfo->pParse->db->mallocFailed );
900 pOp->p3 = (int)(pLevel->iLikeRepCntr>>1); /* Register holding counter */
901 pOp->p5 = (u8)(pLevel->iLikeRepCntr&1); /* ASC or DESC */
902 }
903}
904#else
905# define whereLikeOptimizationStringFixup(A,B,C)
906#endif
907
908#ifdef SQLITE_ENABLE_CURSOR_HINTS
909/*
910** Information is passed from codeCursorHint() down to individual nodes of
911** the expression tree (by sqlite3WalkExpr()) using an instance of this
912** structure.
913*/
914struct CCurHint {
915 int iTabCur; /* Cursor for the main table */
916 int iIdxCur; /* Cursor for the index, if pIdx!=0. Unused otherwise */
917 Index *pIdx; /* The index used to access the table */
918};
919
920/*
921** This function is called for every node of an expression that is a candidate
922** for a cursor hint on an index cursor. For TK_COLUMN nodes that reference
923** the table CCurHint.iTabCur, verify that the same column can be
924** accessed through the index. If it cannot, then set pWalker->eCode to 1.
925*/
926static int codeCursorHintCheckExpr(Walker *pWalker, Expr *pExpr){
927 struct CCurHint *pHint = pWalker->u.pCCurHint;
928 assert( pHint->pIdx!=0 );
929 if( pExpr->op==TK_COLUMN
930 && pExpr->iTable==pHint->iTabCur
931 && sqlite3TableColumnToIndex(pHint->pIdx, pExpr->iColumn)<0
932 ){
933 pWalker->eCode = 1;
934 }
935 return WRC_Continue;
936}
937
938/*
939** Test whether or not expression pExpr, which was part of a WHERE clause,
940** should be included in the cursor-hint for a table that is on the rhs
941** of a LEFT JOIN. Set Walker.eCode to non-zero before returning if the
942** expression is not suitable.
943**
944** An expression is unsuitable if it might evaluate to non NULL even if
945** a TK_COLUMN node that does affect the value of the expression is set
946** to NULL. For example:
947**
948** col IS NULL
949** col IS NOT NULL
950** coalesce(col, 1)
951** CASE WHEN col THEN 0 ELSE 1 END
952*/
953static int codeCursorHintIsOrFunction(Walker *pWalker, Expr *pExpr){
954 if( pExpr->op==TK_IS
955 || pExpr->op==TK_ISNULL || pExpr->op==TK_ISNOT
956 || pExpr->op==TK_NOTNULL || pExpr->op==TK_CASE
957 ){
958 pWalker->eCode = 1;
959 }else if( pExpr->op==TK_FUNCTION ){
960 int d1;
961 char d2[4];
962 if( 0==sqlite3IsLikeFunction(pWalker->pParse->db, pExpr, &d1, d2) ){
963 pWalker->eCode = 1;
964 }
965 }
966
967 return WRC_Continue;
968}
969
970
971/*
972** This function is called on every node of an expression tree used as an
973** argument to the OP_CursorHint instruction. If the node is a TK_COLUMN
974** that accesses any table other than the one identified by
975** CCurHint.iTabCur, then do the following:
976**
977** 1) allocate a register and code an OP_Column instruction to read
978** the specified column into the new register, and
979**
980** 2) transform the expression node to a TK_REGISTER node that reads
981** from the newly populated register.
982**
983** Also, if the node is a TK_COLUMN that does access the table idenified
984** by pCCurHint.iTabCur, and an index is being used (which we will
985** know because CCurHint.pIdx!=0) then transform the TK_COLUMN into
986** an access of the index rather than the original table.
987*/
988static int codeCursorHintFixExpr(Walker *pWalker, Expr *pExpr){
989 int rc = WRC_Continue;
990 struct CCurHint *pHint = pWalker->u.pCCurHint;
991 if( pExpr->op==TK_COLUMN ){
992 if( pExpr->iTable!=pHint->iTabCur ){
993 int reg = ++pWalker->pParse->nMem; /* Register for column value */
994 sqlite3ExprCode(pWalker->pParse, pExpr, reg);
995 pExpr->op = TK_REGISTER;
996 pExpr->iTable = reg;
997 }else if( pHint->pIdx!=0 ){
998 pExpr->iTable = pHint->iIdxCur;
999 pExpr->iColumn = sqlite3TableColumnToIndex(pHint->pIdx, pExpr->iColumn);
1000 assert( pExpr->iColumn>=0 );
1001 }
1002 }else if( pExpr->op==TK_AGG_FUNCTION ){
1003 /* An aggregate function in the WHERE clause of a query means this must
1004 ** be a correlated sub-query, and expression pExpr is an aggregate from
1005 ** the parent context. Do not walk the function arguments in this case.
1006 **
1007 ** todo: It should be possible to replace this node with a TK_REGISTER
1008 ** expression, as the result of the expression must be stored in a
1009 ** register at this point. The same holds for TK_AGG_COLUMN nodes. */
1010 rc = WRC_Prune;
1011 }
1012 return rc;
1013}
1014
1015/*
1016** Insert an OP_CursorHint instruction if it is appropriate to do so.
1017*/
1018static void codeCursorHint(
1019 SrcItem *pTabItem, /* FROM clause item */
1020 WhereInfo *pWInfo, /* The where clause */
1021 WhereLevel *pLevel, /* Which loop to provide hints for */
1022 WhereTerm *pEndRange /* Hint this end-of-scan boundary term if not NULL */
1023){
1024 Parse *pParse = pWInfo->pParse;
1025 sqlite3 *db = pParse->db;
1026 Vdbe *v = pParse->pVdbe;
1027 Expr *pExpr = 0;
1028 WhereLoop *pLoop = pLevel->pWLoop;
1029 int iCur;
1030 WhereClause *pWC;
1031 WhereTerm *pTerm;
1032 int i, j;
1033 struct CCurHint sHint;
1034 Walker sWalker;
1035
1036 if( OptimizationDisabled(db, SQLITE_CursorHints) ) return;
1037 iCur = pLevel->iTabCur;
1038 assert( iCur==pWInfo->pTabList->a[pLevel->iFrom].iCursor );
1039 sHint.iTabCur = iCur;
1040 sHint.iIdxCur = pLevel->iIdxCur;
1041 sHint.pIdx = pLoop->u.btree.pIndex;
1042 memset(&sWalker, 0, sizeof(sWalker));
1043 sWalker.pParse = pParse;
1044 sWalker.u.pCCurHint = &sHint;
1045 pWC = &pWInfo->sWC;
1046 for(i=0; i<pWC->nBase; i++){
1047 pTerm = &pWC->a[i];
1048 if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
1049 if( pTerm->prereqAll & pLevel->notReady ) continue;
1050
1051 /* Any terms specified as part of the ON(...) clause for any LEFT
1052 ** JOIN for which the current table is not the rhs are omitted
1053 ** from the cursor-hint.
1054 **
1055 ** If this table is the rhs of a LEFT JOIN, "IS" or "IS NULL" terms
1056 ** that were specified as part of the WHERE clause must be excluded.
1057 ** This is to address the following:
1058 **
1059 ** SELECT ... t1 LEFT JOIN t2 ON (t1.a=t2.b) WHERE t2.c IS NULL;
1060 **
1061 ** Say there is a single row in t2 that matches (t1.a=t2.b), but its
1062 ** t2.c values is not NULL. If the (t2.c IS NULL) constraint is
1063 ** pushed down to the cursor, this row is filtered out, causing
1064 ** SQLite to synthesize a row of NULL values. Which does match the
1065 ** WHERE clause, and so the query returns a row. Which is incorrect.
1066 **
1067 ** For the same reason, WHERE terms such as:
1068 **
1069 ** WHERE 1 = (t2.c IS NULL)
1070 **
1071 ** are also excluded. See codeCursorHintIsOrFunction() for details.
1072 */
1073 if( pTabItem->fg.jointype & JT_LEFT ){
1074 Expr *pExpr = pTerm->pExpr;
1075 if( !ExprHasProperty(pExpr, EP_OuterON)
1076 || pExpr->w.iJoin!=pTabItem->iCursor
1077 ){
1078 sWalker.eCode = 0;
1079 sWalker.xExprCallback = codeCursorHintIsOrFunction;
1080 sqlite3WalkExpr(&sWalker, pTerm->pExpr);
1081 if( sWalker.eCode ) continue;
1082 }
1083 }else{
1084 if( ExprHasProperty(pTerm->pExpr, EP_OuterON) ) continue;
1085 }
1086
1087 /* All terms in pWLoop->aLTerm[] except pEndRange are used to initialize
1088 ** the cursor. These terms are not needed as hints for a pure range
1089 ** scan (that has no == terms) so omit them. */
1090 if( pLoop->u.btree.nEq==0 && pTerm!=pEndRange ){
1091 for(j=0; j<pLoop->nLTerm && pLoop->aLTerm[j]!=pTerm; j++){}
1092 if( j<pLoop->nLTerm ) continue;
1093 }
1094
1095 /* No subqueries or non-deterministic functions allowed */
1096 if( sqlite3ExprContainsSubquery(pTerm->pExpr) ) continue;
1097
1098 /* For an index scan, make sure referenced columns are actually in
1099 ** the index. */
1100 if( sHint.pIdx!=0 ){
1101 sWalker.eCode = 0;
1102 sWalker.xExprCallback = codeCursorHintCheckExpr;
1103 sqlite3WalkExpr(&sWalker, pTerm->pExpr);
1104 if( sWalker.eCode ) continue;
1105 }
1106
1107 /* If we survive all prior tests, that means this term is worth hinting */
1108 pExpr = sqlite3ExprAnd(pParse, pExpr, sqlite3ExprDup(db, pTerm->pExpr, 0));
1109 }
1110 if( pExpr!=0 ){
1111 sWalker.xExprCallback = codeCursorHintFixExpr;
1112 sqlite3WalkExpr(&sWalker, pExpr);
1113 sqlite3VdbeAddOp4(v, OP_CursorHint,
1114 (sHint.pIdx ? sHint.iIdxCur : sHint.iTabCur), 0, 0,
1115 (const char*)pExpr, P4_EXPR);
1116 }
1117}
1118#else
1119# define codeCursorHint(A,B,C,D) /* No-op */
1120#endif /* SQLITE_ENABLE_CURSOR_HINTS */
1121
1122/*
1123** Cursor iCur is open on an intkey b-tree (a table). Register iRowid contains
1124** a rowid value just read from cursor iIdxCur, open on index pIdx. This
1125** function generates code to do a deferred seek of cursor iCur to the
1126** rowid stored in register iRowid.
1127**
1128** Normally, this is just:
1129**
1130** OP_DeferredSeek $iCur $iRowid
1131**
1132** Which causes a seek on $iCur to the row with rowid $iRowid.
1133**
1134** However, if the scan currently being coded is a branch of an OR-loop and
1135** the statement currently being coded is a SELECT, then additional information
1136** is added that might allow OP_Column to omit the seek and instead do its
1137** lookup on the index, thus avoiding an expensive seek operation. To
1138** enable this optimization, the P3 of OP_DeferredSeek is set to iIdxCur
1139** and P4 is set to an array of integers containing one entry for each column
1140** in the table. For each table column, if the column is the i'th
1141** column of the index, then the corresponding array entry is set to (i+1).
1142** If the column does not appear in the index at all, the array entry is set
1143** to 0. The OP_Column opcode can check this array to see if the column it
1144** wants is in the index and if it is, it will substitute the index cursor
1145** and column number and continue with those new values, rather than seeking
1146** the table cursor.
1147*/
1148static void codeDeferredSeek(
1149 WhereInfo *pWInfo, /* Where clause context */
1150 Index *pIdx, /* Index scan is using */
1151 int iCur, /* Cursor for IPK b-tree */
1152 int iIdxCur /* Index cursor */
1153){
1154 Parse *pParse = pWInfo->pParse; /* Parse context */
1155 Vdbe *v = pParse->pVdbe; /* Vdbe to generate code within */
1156
1157 assert( iIdxCur>0 );
1158 assert( pIdx->aiColumn[pIdx->nColumn-1]==-1 );
1159
1160 pWInfo->bDeferredSeek = 1;
1161 sqlite3VdbeAddOp3(v, OP_DeferredSeek, iIdxCur, 0, iCur);
1162 if( (pWInfo->wctrlFlags & (WHERE_OR_SUBCLAUSE|WHERE_RIGHT_JOIN))
1163 && DbMaskAllZero(sqlite3ParseToplevel(pParse)->writeMask)
1164 ){
1165 int i;
1166 Table *pTab = pIdx->pTable;
1167 u32 *ai = (u32*)sqlite3DbMallocZero(pParse->db, sizeof(u32)*(pTab->nCol+1));
1168 if( ai ){
1169 ai[0] = pTab->nCol;
1170 for(i=0; i<pIdx->nColumn-1; i++){
1171 int x1, x2;
1172 assert( pIdx->aiColumn[i]<pTab->nCol );
1173 x1 = pIdx->aiColumn[i];
1174 x2 = sqlite3TableColumnToStorage(pTab, x1);
1175 testcase( x1!=x2 );
1176 if( x1>=0 ) ai[x2+1] = i+1;
1177 }
1178 sqlite3VdbeChangeP4(v, -1, (char*)ai, P4_INTARRAY);
1179 }
1180 }
1181}
1182
1183/*
1184** If the expression passed as the second argument is a vector, generate
1185** code to write the first nReg elements of the vector into an array
1186** of registers starting with iReg.
1187**
1188** If the expression is not a vector, then nReg must be passed 1. In
1189** this case, generate code to evaluate the expression and leave the
1190** result in register iReg.
1191*/
1192static void codeExprOrVector(Parse *pParse, Expr *p, int iReg, int nReg){
1193 assert( nReg>0 );
1194 if( p && sqlite3ExprIsVector(p) ){
1195#ifndef SQLITE_OMIT_SUBQUERY
1196 if( ExprUseXSelect(p) ){
1197 Vdbe *v = pParse->pVdbe;
1198 int iSelect;
1199 assert( p->op==TK_SELECT );
1200 iSelect = sqlite3CodeSubselect(pParse, p);
1201 sqlite3VdbeAddOp3(v, OP_Copy, iSelect, iReg, nReg-1);
1202 }else
1203#endif
1204 {
1205 int i;
1206 const ExprList *pList;
1207 assert( ExprUseXList(p) );
1208 pList = p->x.pList;
1209 assert( nReg<=pList->nExpr );
1210 for(i=0; i<nReg; i++){
1211 sqlite3ExprCode(pParse, pList->a[i].pExpr, iReg+i);
1212 }
1213 }
1214 }else{
1215 assert( nReg==1 || pParse->nErr );
1216 sqlite3ExprCode(pParse, p, iReg);
1217 }
1218}
1219
1220/*
1221** The pTruth expression is always true because it is the WHERE clause
1222** a partial index that is driving a query loop. Look through all of the
1223** WHERE clause terms on the query, and if any of those terms must be
1224** true because pTruth is true, then mark those WHERE clause terms as
1225** coded.
1226*/
1227static void whereApplyPartialIndexConstraints(
1228 Expr *pTruth,
1229 int iTabCur,
1230 WhereClause *pWC
1231){
1232 int i;
1233 WhereTerm *pTerm;
1234 while( pTruth->op==TK_AND ){
1235 whereApplyPartialIndexConstraints(pTruth->pLeft, iTabCur, pWC);
1236 pTruth = pTruth->pRight;
1237 }
1238 for(i=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
1239 Expr *pExpr;
1240 if( pTerm->wtFlags & TERM_CODED ) continue;
1241 pExpr = pTerm->pExpr;
1242 if( sqlite3ExprCompare(0, pExpr, pTruth, iTabCur)==0 ){
1243 pTerm->wtFlags |= TERM_CODED;
1244 }
1245 }
1246}
1247
1248/*
1249** This routine is called right after An OP_Filter has been generated and
1250** before the corresponding index search has been performed. This routine
1251** checks to see if there are additional Bloom filters in inner loops that
1252** can be checked prior to doing the index lookup. If there are available
1253** inner-loop Bloom filters, then evaluate those filters now, before the
1254** index lookup. The idea is that a Bloom filter check is way faster than
1255** an index lookup, and the Bloom filter might return false, meaning that
1256** the index lookup can be skipped.
1257**
1258** We know that an inner loop uses a Bloom filter because it has the
1259** WhereLevel.regFilter set. If an inner-loop Bloom filter is checked,
1260** then clear the WhereLevel.regFilter value to prevent the Bloom filter
1261** from being checked a second time when the inner loop is evaluated.
1262*/
1263static SQLITE_NOINLINE void filterPullDown(
1264 Parse *pParse, /* Parsing context */
1265 WhereInfo *pWInfo, /* Complete information about the WHERE clause */
1266 int iLevel, /* Which level of pWInfo->a[] should be coded */
1267 int addrNxt, /* Jump here to bypass inner loops */
1268 Bitmask notReady /* Loops that are not ready */
1269){
1270 while( ++iLevel < pWInfo->nLevel ){
1271 WhereLevel *pLevel = &pWInfo->a[iLevel];
1272 WhereLoop *pLoop = pLevel->pWLoop;
1273 if( pLevel->regFilter==0 ) continue;
1274 if( pLevel->pWLoop->nSkip ) continue;
1275 /* ,--- Because sqlite3ConstructBloomFilter() has will not have set
1276 ** vvvvv--' pLevel->regFilter if this were true. */
1277 if( NEVER(pLoop->prereq & notReady) ) continue;
1278 assert( pLevel->addrBrk==0 );
1279 pLevel->addrBrk = addrNxt;
1280 if( pLoop->wsFlags & WHERE_IPK ){
1281 WhereTerm *pTerm = pLoop->aLTerm[0];
1282 int regRowid;
1283 assert( pTerm!=0 );
1284 assert( pTerm->pExpr!=0 );
1285 testcase( pTerm->wtFlags & TERM_VIRTUAL );
1286 regRowid = sqlite3GetTempReg(pParse);
1287 regRowid = codeEqualityTerm(pParse, pTerm, pLevel, 0, 0, regRowid);
1288 sqlite3VdbeAddOp2(pParse->pVdbe, OP_MustBeInt, regRowid, addrNxt);
1289 VdbeCoverage(pParse->pVdbe);
1290 sqlite3VdbeAddOp4Int(pParse->pVdbe, OP_Filter, pLevel->regFilter,
1291 addrNxt, regRowid, 1);
1292 VdbeCoverage(pParse->pVdbe);
1293 }else{
1294 u16 nEq = pLoop->u.btree.nEq;
1295 int r1;
1296 char *zStartAff;
1297
1298 assert( pLoop->wsFlags & WHERE_INDEXED );
1299 assert( (pLoop->wsFlags & WHERE_COLUMN_IN)==0 );
1300 r1 = codeAllEqualityTerms(pParse,pLevel,0,0,&zStartAff);
1301 codeApplyAffinity(pParse, r1, nEq, zStartAff);
1302 sqlite3DbFree(pParse->db, zStartAff);
1303 sqlite3VdbeAddOp4Int(pParse->pVdbe, OP_Filter, pLevel->regFilter,
1304 addrNxt, r1, nEq);
1305 VdbeCoverage(pParse->pVdbe);
1306 }
1307 pLevel->regFilter = 0;
1308 pLevel->addrBrk = 0;
1309 }
1310}
1311
1312/*
1313** Generate code for the start of the iLevel-th loop in the WHERE clause
1314** implementation described by pWInfo.
1315*/
1316Bitmask sqlite3WhereCodeOneLoopStart(
1317 Parse *pParse, /* Parsing context */
1318 Vdbe *v, /* Prepared statement under construction */
1319 WhereInfo *pWInfo, /* Complete information about the WHERE clause */
1320 int iLevel, /* Which level of pWInfo->a[] should be coded */
1321 WhereLevel *pLevel, /* The current level pointer */
1322 Bitmask notReady /* Which tables are currently available */
1323){
1324 int j, k; /* Loop counters */
1325 int iCur; /* The VDBE cursor for the table */
1326 int addrNxt; /* Where to jump to continue with the next IN case */
1327 int bRev; /* True if we need to scan in reverse order */
1328 WhereLoop *pLoop; /* The WhereLoop object being coded */
1329 WhereClause *pWC; /* Decomposition of the entire WHERE clause */
1330 WhereTerm *pTerm; /* A WHERE clause term */
1331 sqlite3 *db; /* Database connection */
1332 SrcItem *pTabItem; /* FROM clause term being coded */
1333 int addrBrk; /* Jump here to break out of the loop */
1334 int addrHalt; /* addrBrk for the outermost loop */
1335 int addrCont; /* Jump here to continue with next cycle */
1336 int iRowidReg = 0; /* Rowid is stored in this register, if not zero */
1337 int iReleaseReg = 0; /* Temp register to free before returning */
1338 Index *pIdx = 0; /* Index used by loop (if any) */
1339 int iLoop; /* Iteration of constraint generator loop */
1340
1341 pWC = &pWInfo->sWC;
1342 db = pParse->db;
1343 pLoop = pLevel->pWLoop;
1344 pTabItem = &pWInfo->pTabList->a[pLevel->iFrom];
1345 iCur = pTabItem->iCursor;
1346 pLevel->notReady = notReady & ~sqlite3WhereGetMask(&pWInfo->sMaskSet, iCur);
1347 bRev = (pWInfo->revMask>>iLevel)&1;
1348 VdbeModuleComment((v, "Begin WHERE-loop%d: %s",iLevel,pTabItem->pTab->zName));
1349#if WHERETRACE_ENABLED /* 0x20800 */
1350 if( sqlite3WhereTrace & 0x800 ){
1351 sqlite3DebugPrintf("Coding level %d of %d: notReady=%llx iFrom=%d\n",
1352 iLevel, pWInfo->nLevel, (u64)notReady, pLevel->iFrom);
1353 sqlite3WhereLoopPrint(pLoop, pWC);
1354 }
1355 if( sqlite3WhereTrace & 0x20000 ){
1356 if( iLevel==0 ){
1357 sqlite3DebugPrintf("WHERE clause being coded:\n");
1358 sqlite3TreeViewExpr(0, pWInfo->pWhere, 0);
1359 }
1360 sqlite3DebugPrintf("All WHERE-clause terms before coding:\n");
1361 sqlite3WhereClausePrint(pWC);
1362 }
1363#endif
1364
1365 /* Create labels for the "break" and "continue" instructions
1366 ** for the current loop. Jump to addrBrk to break out of a loop.
1367 ** Jump to cont to go immediately to the next iteration of the
1368 ** loop.
1369 **
1370 ** When there is an IN operator, we also have a "addrNxt" label that
1371 ** means to continue with the next IN value combination. When
1372 ** there are no IN operators in the constraints, the "addrNxt" label
1373 ** is the same as "addrBrk".
1374 */
1375 addrBrk = pLevel->addrBrk = pLevel->addrNxt = sqlite3VdbeMakeLabel(pParse);
1376 addrCont = pLevel->addrCont = sqlite3VdbeMakeLabel(pParse);
1377
1378 /* If this is the right table of a LEFT OUTER JOIN, allocate and
1379 ** initialize a memory cell that records if this table matches any
1380 ** row of the left table of the join.
1381 */
1382 assert( (pWInfo->wctrlFlags & (WHERE_OR_SUBCLAUSE|WHERE_RIGHT_JOIN))
1383 || pLevel->iFrom>0 || (pTabItem[0].fg.jointype & JT_LEFT)==0
1384 );
1385 if( pLevel->iFrom>0 && (pTabItem[0].fg.jointype & JT_LEFT)!=0 ){
1386 pLevel->iLeftJoin = ++pParse->nMem;
1387 sqlite3VdbeAddOp2(v, OP_Integer, 0, pLevel->iLeftJoin);
1388 VdbeComment((v, "init LEFT JOIN no-match flag"));
1389 }
1390
1391 /* Compute a safe address to jump to if we discover that the table for
1392 ** this loop is empty and can never contribute content. */
1393 for(j=iLevel; j>0; j--){
1394 if( pWInfo->a[j].iLeftJoin ) break;
1395 if( pWInfo->a[j].pRJ ) break;
1396 }
1397 addrHalt = pWInfo->a[j].addrBrk;
1398
1399 /* Special case of a FROM clause subquery implemented as a co-routine */
1400 if( pTabItem->fg.viaCoroutine ){
1401 int regYield = pTabItem->regReturn;
1402 sqlite3VdbeAddOp3(v, OP_InitCoroutine, regYield, 0, pTabItem->addrFillSub);
1403 pLevel->p2 = sqlite3VdbeAddOp2(v, OP_Yield, regYield, addrBrk);
1404 VdbeCoverage(v);
1405 VdbeComment((v, "next row of %s", pTabItem->pTab->zName));
1406 pLevel->op = OP_Goto;
1407 }else
1408
1409#ifndef SQLITE_OMIT_VIRTUALTABLE
1410 if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)!=0 ){
1411 /* Case 1: The table is a virtual-table. Use the VFilter and VNext
1412 ** to access the data.
1413 */
1414 int iReg; /* P3 Value for OP_VFilter */
1415 int addrNotFound;
1416 int nConstraint = pLoop->nLTerm;
1417
1418 iReg = sqlite3GetTempRange(pParse, nConstraint+2);
1419 addrNotFound = pLevel->addrBrk;
1420 for(j=0; j<nConstraint; j++){
1421 int iTarget = iReg+j+2;
1422 pTerm = pLoop->aLTerm[j];
1423 if( NEVER(pTerm==0) ) continue;
1424 if( pTerm->eOperator & WO_IN ){
1425 if( SMASKBIT32(j) & pLoop->u.vtab.mHandleIn ){
1426 int iTab = pParse->nTab++;
1427 int iCache = ++pParse->nMem;
1428 sqlite3CodeRhsOfIN(pParse, pTerm->pExpr, iTab);
1429 sqlite3VdbeAddOp3(v, OP_VInitIn, iTab, iTarget, iCache);
1430 }else{
1431 codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, iTarget);
1432 addrNotFound = pLevel->addrNxt;
1433 }
1434 }else{
1435 Expr *pRight = pTerm->pExpr->pRight;
1436 codeExprOrVector(pParse, pRight, iTarget, 1);
1437 if( pTerm->eMatchOp==SQLITE_INDEX_CONSTRAINT_OFFSET
1438 && pLoop->u.vtab.bOmitOffset
1439 ){
1440 assert( pTerm->eOperator==WO_AUX );
1441 assert( pWInfo->pSelect!=0 );
1442 assert( pWInfo->pSelect->iOffset>0 );
1443 sqlite3VdbeAddOp2(v, OP_Integer, 0, pWInfo->pSelect->iOffset);
1444 VdbeComment((v,"Zero OFFSET counter"));
1445 }
1446 }
1447 }
1448 sqlite3VdbeAddOp2(v, OP_Integer, pLoop->u.vtab.idxNum, iReg);
1449 sqlite3VdbeAddOp2(v, OP_Integer, nConstraint, iReg+1);
1450 sqlite3VdbeAddOp4(v, OP_VFilter, iCur, addrNotFound, iReg,
1451 pLoop->u.vtab.idxStr,
1452 pLoop->u.vtab.needFree ? P4_DYNAMIC : P4_STATIC);
1453 VdbeCoverage(v);
1454 pLoop->u.vtab.needFree = 0;
1455 /* An OOM inside of AddOp4(OP_VFilter) instruction above might have freed
1456 ** the u.vtab.idxStr. NULL it out to prevent a use-after-free */
1457 if( db->mallocFailed ) pLoop->u.vtab.idxStr = 0;
1458 pLevel->p1 = iCur;
1459 pLevel->op = pWInfo->eOnePass ? OP_Noop : OP_VNext;
1460 pLevel->p2 = sqlite3VdbeCurrentAddr(v);
1461 assert( (pLoop->wsFlags & WHERE_MULTI_OR)==0 );
1462
1463 for(j=0; j<nConstraint; j++){
1464 pTerm = pLoop->aLTerm[j];
1465 if( j<16 && (pLoop->u.vtab.omitMask>>j)&1 ){
1466 disableTerm(pLevel, pTerm);
1467 continue;
1468 }
1469 if( (pTerm->eOperator & WO_IN)!=0
1470 && (SMASKBIT32(j) & pLoop->u.vtab.mHandleIn)==0
1471 && !db->mallocFailed
1472 ){
1473 Expr *pCompare; /* The comparison operator */
1474 Expr *pRight; /* RHS of the comparison */
1475 VdbeOp *pOp; /* Opcode to access the value of the IN constraint */
1476 int iIn; /* IN loop corresponding to the j-th constraint */
1477
1478 /* Reload the constraint value into reg[iReg+j+2]. The same value
1479 ** was loaded into the same register prior to the OP_VFilter, but
1480 ** the xFilter implementation might have changed the datatype or
1481 ** encoding of the value in the register, so it *must* be reloaded.
1482 */
1483 for(iIn=0; ALWAYS(iIn<pLevel->u.in.nIn); iIn++){
1484 pOp = sqlite3VdbeGetOp(v, pLevel->u.in.aInLoop[iIn].addrInTop);
1485 if( (pOp->opcode==OP_Column && pOp->p3==iReg+j+2)
1486 || (pOp->opcode==OP_Rowid && pOp->p2==iReg+j+2)
1487 ){
1488 testcase( pOp->opcode==OP_Rowid );
1489 sqlite3VdbeAddOp3(v, pOp->opcode, pOp->p1, pOp->p2, pOp->p3);
1490 break;
1491 }
1492 }
1493
1494 /* Generate code that will continue to the next row if
1495 ** the IN constraint is not satisfied
1496 */
1497 pCompare = sqlite3PExpr(pParse, TK_EQ, 0, 0);
1498 if( !db->mallocFailed ){
1499 int iFld = pTerm->u.x.iField;
1500 Expr *pLeft = pTerm->pExpr->pLeft;
1501 assert( pLeft!=0 );
1502 if( iFld>0 ){
1503 assert( pLeft->op==TK_VECTOR );
1504 assert( ExprUseXList(pLeft) );
1505 assert( iFld<=pLeft->x.pList->nExpr );
1506 pCompare->pLeft = pLeft->x.pList->a[iFld-1].pExpr;
1507 }else{
1508 pCompare->pLeft = pLeft;
1509 }
1510 pCompare->pRight = pRight = sqlite3Expr(db, TK_REGISTER, 0);
1511 if( pRight ){
1512 pRight->iTable = iReg+j+2;
1513 sqlite3ExprIfFalse(
1514 pParse, pCompare, pLevel->addrCont, SQLITE_JUMPIFNULL
1515 );
1516 }
1517 pCompare->pLeft = 0;
1518 }
1519 sqlite3ExprDelete(db, pCompare);
1520 }
1521 }
1522
1523 /* These registers need to be preserved in case there is an IN operator
1524 ** loop. So we could deallocate the registers here (and potentially
1525 ** reuse them later) if (pLoop->wsFlags & WHERE_IN_ABLE)==0. But it seems
1526 ** simpler and safer to simply not reuse the registers.
1527 **
1528 ** sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2);
1529 */
1530 }else
1531#endif /* SQLITE_OMIT_VIRTUALTABLE */
1532
1533 if( (pLoop->wsFlags & WHERE_IPK)!=0
1534 && (pLoop->wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_EQ))!=0
1535 ){
1536 /* Case 2: We can directly reference a single row using an
1537 ** equality comparison against the ROWID field. Or
1538 ** we reference multiple rows using a "rowid IN (...)"
1539 ** construct.
1540 */
1541 assert( pLoop->u.btree.nEq==1 );
1542 pTerm = pLoop->aLTerm[0];
1543 assert( pTerm!=0 );
1544 assert( pTerm->pExpr!=0 );
1545 testcase( pTerm->wtFlags & TERM_VIRTUAL );
1546 iReleaseReg = ++pParse->nMem;
1547 iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, 0, bRev, iReleaseReg);
1548 if( iRowidReg!=iReleaseReg ) sqlite3ReleaseTempReg(pParse, iReleaseReg);
1549 addrNxt = pLevel->addrNxt;
1550 if( pLevel->regFilter ){
1551 sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt);
1552 VdbeCoverage(v);
1553 sqlite3VdbeAddOp4Int(v, OP_Filter, pLevel->regFilter, addrNxt,
1554 iRowidReg, 1);
1555 VdbeCoverage(v);
1556 filterPullDown(pParse, pWInfo, iLevel, addrNxt, notReady);
1557 }
1558 sqlite3VdbeAddOp3(v, OP_SeekRowid, iCur, addrNxt, iRowidReg);
1559 VdbeCoverage(v);
1560 pLevel->op = OP_Noop;
1561 }else if( (pLoop->wsFlags & WHERE_IPK)!=0
1562 && (pLoop->wsFlags & WHERE_COLUMN_RANGE)!=0
1563 ){
1564 /* Case 3: We have an inequality comparison against the ROWID field.
1565 */
1566 int testOp = OP_Noop;
1567 int start;
1568 int memEndValue = 0;
1569 WhereTerm *pStart, *pEnd;
1570
1571 j = 0;
1572 pStart = pEnd = 0;
1573 if( pLoop->wsFlags & WHERE_BTM_LIMIT ) pStart = pLoop->aLTerm[j++];
1574 if( pLoop->wsFlags & WHERE_TOP_LIMIT ) pEnd = pLoop->aLTerm[j++];
1575 assert( pStart!=0 || pEnd!=0 );
1576 if( bRev ){
1577 pTerm = pStart;
1578 pStart = pEnd;
1579 pEnd = pTerm;
1580 }
1581 codeCursorHint(pTabItem, pWInfo, pLevel, pEnd);
1582 if( pStart ){
1583 Expr *pX; /* The expression that defines the start bound */
1584 int r1, rTemp; /* Registers for holding the start boundary */
1585 int op; /* Cursor seek operation */
1586
1587 /* The following constant maps TK_xx codes into corresponding
1588 ** seek opcodes. It depends on a particular ordering of TK_xx
1589 */
1590 const u8 aMoveOp[] = {
1591 /* TK_GT */ OP_SeekGT,
1592 /* TK_LE */ OP_SeekLE,
1593 /* TK_LT */ OP_SeekLT,
1594 /* TK_GE */ OP_SeekGE
1595 };
1596 assert( TK_LE==TK_GT+1 ); /* Make sure the ordering.. */
1597 assert( TK_LT==TK_GT+2 ); /* ... of the TK_xx values... */
1598 assert( TK_GE==TK_GT+3 ); /* ... is correcct. */
1599
1600 assert( (pStart->wtFlags & TERM_VNULL)==0 );
1601 testcase( pStart->wtFlags & TERM_VIRTUAL );
1602 pX = pStart->pExpr;
1603 assert( pX!=0 );
1604 testcase( pStart->leftCursor!=iCur ); /* transitive constraints */
1605 if( sqlite3ExprIsVector(pX->pRight) ){
1606 r1 = rTemp = sqlite3GetTempReg(pParse);
1607 codeExprOrVector(pParse, pX->pRight, r1, 1);
1608 testcase( pX->op==TK_GT );
1609 testcase( pX->op==TK_GE );
1610 testcase( pX->op==TK_LT );
1611 testcase( pX->op==TK_LE );
1612 op = aMoveOp[((pX->op - TK_GT - 1) & 0x3) | 0x1];
1613 assert( pX->op!=TK_GT || op==OP_SeekGE );
1614 assert( pX->op!=TK_GE || op==OP_SeekGE );
1615 assert( pX->op!=TK_LT || op==OP_SeekLE );
1616 assert( pX->op!=TK_LE || op==OP_SeekLE );
1617 }else{
1618 r1 = sqlite3ExprCodeTemp(pParse, pX->pRight, &rTemp);
1619 disableTerm(pLevel, pStart);
1620 op = aMoveOp[(pX->op - TK_GT)];
1621 }
1622 sqlite3VdbeAddOp3(v, op, iCur, addrBrk, r1);
1623 VdbeComment((v, "pk"));
1624 VdbeCoverageIf(v, pX->op==TK_GT);
1625 VdbeCoverageIf(v, pX->op==TK_LE);
1626 VdbeCoverageIf(v, pX->op==TK_LT);
1627 VdbeCoverageIf(v, pX->op==TK_GE);
1628 sqlite3ReleaseTempReg(pParse, rTemp);
1629 }else{
1630 sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iCur, addrHalt);
1631 VdbeCoverageIf(v, bRev==0);
1632 VdbeCoverageIf(v, bRev!=0);
1633 }
1634 if( pEnd ){
1635 Expr *pX;
1636 pX = pEnd->pExpr;
1637 assert( pX!=0 );
1638 assert( (pEnd->wtFlags & TERM_VNULL)==0 );
1639 testcase( pEnd->leftCursor!=iCur ); /* Transitive constraints */
1640 testcase( pEnd->wtFlags & TERM_VIRTUAL );
1641 memEndValue = ++pParse->nMem;
1642 codeExprOrVector(pParse, pX->pRight, memEndValue, 1);
1643 if( 0==sqlite3ExprIsVector(pX->pRight)
1644 && (pX->op==TK_LT || pX->op==TK_GT)
1645 ){
1646 testOp = bRev ? OP_Le : OP_Ge;
1647 }else{
1648 testOp = bRev ? OP_Lt : OP_Gt;
1649 }
1650 if( 0==sqlite3ExprIsVector(pX->pRight) ){
1651 disableTerm(pLevel, pEnd);
1652 }
1653 }
1654 start = sqlite3VdbeCurrentAddr(v);
1655 pLevel->op = bRev ? OP_Prev : OP_Next;
1656 pLevel->p1 = iCur;
1657 pLevel->p2 = start;
1658 assert( pLevel->p5==0 );
1659 if( testOp!=OP_Noop ){
1660 iRowidReg = ++pParse->nMem;
1661 sqlite3VdbeAddOp2(v, OP_Rowid, iCur, iRowidReg);
1662 sqlite3VdbeAddOp3(v, testOp, memEndValue, addrBrk, iRowidReg);
1663 VdbeCoverageIf(v, testOp==OP_Le);
1664 VdbeCoverageIf(v, testOp==OP_Lt);
1665 VdbeCoverageIf(v, testOp==OP_Ge);
1666 VdbeCoverageIf(v, testOp==OP_Gt);
1667 sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC | SQLITE_JUMPIFNULL);
1668 }
1669 }else if( pLoop->wsFlags & WHERE_INDEXED ){
1670 /* Case 4: A scan using an index.
1671 **
1672 ** The WHERE clause may contain zero or more equality
1673 ** terms ("==" or "IN" operators) that refer to the N
1674 ** left-most columns of the index. It may also contain
1675 ** inequality constraints (>, <, >= or <=) on the indexed
1676 ** column that immediately follows the N equalities. Only
1677 ** the right-most column can be an inequality - the rest must
1678 ** use the "==" and "IN" operators. For example, if the
1679 ** index is on (x,y,z), then the following clauses are all
1680 ** optimized:
1681 **
1682 ** x=5
1683 ** x=5 AND y=10
1684 ** x=5 AND y<10
1685 ** x=5 AND y>5 AND y<10
1686 ** x=5 AND y=5 AND z<=10
1687 **
1688 ** The z<10 term of the following cannot be used, only
1689 ** the x=5 term:
1690 **
1691 ** x=5 AND z<10
1692 **
1693 ** N may be zero if there are inequality constraints.
1694 ** If there are no inequality constraints, then N is at
1695 ** least one.
1696 **
1697 ** This case is also used when there are no WHERE clause
1698 ** constraints but an index is selected anyway, in order
1699 ** to force the output order to conform to an ORDER BY.
1700 */
1701 static const u8 aStartOp[] = {
1702 0,
1703 0,
1704 OP_Rewind, /* 2: (!start_constraints && startEq && !bRev) */
1705 OP_Last, /* 3: (!start_constraints && startEq && bRev) */
1706 OP_SeekGT, /* 4: (start_constraints && !startEq && !bRev) */
1707 OP_SeekLT, /* 5: (start_constraints && !startEq && bRev) */
1708 OP_SeekGE, /* 6: (start_constraints && startEq && !bRev) */
1709 OP_SeekLE /* 7: (start_constraints && startEq && bRev) */
1710 };
1711 static const u8 aEndOp[] = {
1712 OP_IdxGE, /* 0: (end_constraints && !bRev && !endEq) */
1713 OP_IdxGT, /* 1: (end_constraints && !bRev && endEq) */
1714 OP_IdxLE, /* 2: (end_constraints && bRev && !endEq) */
1715 OP_IdxLT, /* 3: (end_constraints && bRev && endEq) */
1716 };
1717 u16 nEq = pLoop->u.btree.nEq; /* Number of == or IN terms */
1718 u16 nBtm = pLoop->u.btree.nBtm; /* Length of BTM vector */
1719 u16 nTop = pLoop->u.btree.nTop; /* Length of TOP vector */
1720 int regBase; /* Base register holding constraint values */
1721 WhereTerm *pRangeStart = 0; /* Inequality constraint at range start */
1722 WhereTerm *pRangeEnd = 0; /* Inequality constraint at range end */
1723 int startEq; /* True if range start uses ==, >= or <= */
1724 int endEq; /* True if range end uses ==, >= or <= */
1725 int start_constraints; /* Start of range is constrained */
1726 int nConstraint; /* Number of constraint terms */
1727 int iIdxCur; /* The VDBE cursor for the index */
1728 int nExtraReg = 0; /* Number of extra registers needed */
1729 int op; /* Instruction opcode */
1730 char *zStartAff; /* Affinity for start of range constraint */
1731 char *zEndAff = 0; /* Affinity for end of range constraint */
1732 u8 bSeekPastNull = 0; /* True to seek past initial nulls */
1733 u8 bStopAtNull = 0; /* Add condition to terminate at NULLs */
1734 int omitTable; /* True if we use the index only */
1735 int regBignull = 0; /* big-null flag register */
1736 int addrSeekScan = 0; /* Opcode of the OP_SeekScan, if any */
1737
1738 pIdx = pLoop->u.btree.pIndex;
1739 iIdxCur = pLevel->iIdxCur;
1740 assert( nEq>=pLoop->nSkip );
1741
1742 /* Find any inequality constraint terms for the start and end
1743 ** of the range.
1744 */
1745 j = nEq;
1746 if( pLoop->wsFlags & WHERE_BTM_LIMIT ){
1747 pRangeStart = pLoop->aLTerm[j++];
1748 nExtraReg = MAX(nExtraReg, pLoop->u.btree.nBtm);
1749 /* Like optimization range constraints always occur in pairs */
1750 assert( (pRangeStart->wtFlags & TERM_LIKEOPT)==0 ||
1751 (pLoop->wsFlags & WHERE_TOP_LIMIT)!=0 );
1752 }
1753 if( pLoop->wsFlags & WHERE_TOP_LIMIT ){
1754 pRangeEnd = pLoop->aLTerm[j++];
1755 nExtraReg = MAX(nExtraReg, pLoop->u.btree.nTop);
1756#ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
1757 if( (pRangeEnd->wtFlags & TERM_LIKEOPT)!=0 ){
1758 assert( pRangeStart!=0 ); /* LIKE opt constraints */
1759 assert( pRangeStart->wtFlags & TERM_LIKEOPT ); /* occur in pairs */
1760 pLevel->iLikeRepCntr = (u32)++pParse->nMem;
1761 sqlite3VdbeAddOp2(v, OP_Integer, 1, (int)pLevel->iLikeRepCntr);
1762 VdbeComment((v, "LIKE loop counter"));
1763 pLevel->addrLikeRep = sqlite3VdbeCurrentAddr(v);
1764 /* iLikeRepCntr actually stores 2x the counter register number. The
1765 ** bottom bit indicates whether the search order is ASC or DESC. */
1766 testcase( bRev );
1767 testcase( pIdx->aSortOrder[nEq]==SQLITE_SO_DESC );
1768 assert( (bRev & ~1)==0 );
1769 pLevel->iLikeRepCntr <<=1;
1770 pLevel->iLikeRepCntr |= bRev ^ (pIdx->aSortOrder[nEq]==SQLITE_SO_DESC);
1771 }
1772#endif
1773 if( pRangeStart==0 ){
1774 j = pIdx->aiColumn[nEq];
1775 if( (j>=0 && pIdx->pTable->aCol[j].notNull==0) || j==XN_EXPR ){
1776 bSeekPastNull = 1;
1777 }
1778 }
1779 }
1780 assert( pRangeEnd==0 || (pRangeEnd->wtFlags & TERM_VNULL)==0 );
1781
1782 /* If the WHERE_BIGNULL_SORT flag is set, then index column nEq uses
1783 ** a non-default "big-null" sort (either ASC NULLS LAST or DESC NULLS
1784 ** FIRST). In both cases separate ordered scans are made of those
1785 ** index entries for which the column is null and for those for which
1786 ** it is not. For an ASC sort, the non-NULL entries are scanned first.
1787 ** For DESC, NULL entries are scanned first.
1788 */
1789 if( (pLoop->wsFlags & (WHERE_TOP_LIMIT|WHERE_BTM_LIMIT))==0
1790 && (pLoop->wsFlags & WHERE_BIGNULL_SORT)!=0
1791 ){
1792 assert( bSeekPastNull==0 && nExtraReg==0 && nBtm==0 && nTop==0 );
1793 assert( pRangeEnd==0 && pRangeStart==0 );
1794 testcase( pLoop->nSkip>0 );
1795 nExtraReg = 1;
1796 bSeekPastNull = 1;
1797 pLevel->regBignull = regBignull = ++pParse->nMem;
1798 if( pLevel->iLeftJoin ){
1799 sqlite3VdbeAddOp2(v, OP_Integer, 0, regBignull);
1800 }
1801 pLevel->addrBignull = sqlite3VdbeMakeLabel(pParse);
1802 }
1803
1804 /* If we are doing a reverse order scan on an ascending index, or
1805 ** a forward order scan on a descending index, interchange the
1806 ** start and end terms (pRangeStart and pRangeEnd).
1807 */
1808 if( (nEq<pIdx->nColumn && bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC)) ){
1809 SWAP(WhereTerm *, pRangeEnd, pRangeStart);
1810 SWAP(u8, bSeekPastNull, bStopAtNull);
1811 SWAP(u8, nBtm, nTop);
1812 }
1813
1814 if( iLevel>0 && (pLoop->wsFlags & WHERE_IN_SEEKSCAN)!=0 ){
1815 /* In case OP_SeekScan is used, ensure that the index cursor does not
1816 ** point to a valid row for the first iteration of this loop. */
1817 sqlite3VdbeAddOp1(v, OP_NullRow, iIdxCur);
1818 }
1819
1820 /* Generate code to evaluate all constraint terms using == or IN
1821 ** and store the values of those terms in an array of registers
1822 ** starting at regBase.
1823 */
1824 codeCursorHint(pTabItem, pWInfo, pLevel, pRangeEnd);
1825 regBase = codeAllEqualityTerms(pParse,pLevel,bRev,nExtraReg,&zStartAff);
1826 assert( zStartAff==0 || sqlite3Strlen30(zStartAff)>=nEq );
1827 if( zStartAff && nTop ){
1828 zEndAff = sqlite3DbStrDup(db, &zStartAff[nEq]);
1829 }
1830 addrNxt = (regBignull ? pLevel->addrBignull : pLevel->addrNxt);
1831
1832 testcase( pRangeStart && (pRangeStart->eOperator & WO_LE)!=0 );
1833 testcase( pRangeStart && (pRangeStart->eOperator & WO_GE)!=0 );
1834 testcase( pRangeEnd && (pRangeEnd->eOperator & WO_LE)!=0 );
1835 testcase( pRangeEnd && (pRangeEnd->eOperator & WO_GE)!=0 );
1836 startEq = !pRangeStart || pRangeStart->eOperator & (WO_LE|WO_GE);
1837 endEq = !pRangeEnd || pRangeEnd->eOperator & (WO_LE|WO_GE);
1838 start_constraints = pRangeStart || nEq>0;
1839
1840 /* Seek the index cursor to the start of the range. */
1841 nConstraint = nEq;
1842 if( pRangeStart ){
1843 Expr *pRight = pRangeStart->pExpr->pRight;
1844 codeExprOrVector(pParse, pRight, regBase+nEq, nBtm);
1845 whereLikeOptimizationStringFixup(v, pLevel, pRangeStart);
1846 if( (pRangeStart->wtFlags & TERM_VNULL)==0
1847 && sqlite3ExprCanBeNull(pRight)
1848 ){
1849 sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt);
1850 VdbeCoverage(v);
1851 }
1852 if( zStartAff ){
1853 updateRangeAffinityStr(pRight, nBtm, &zStartAff[nEq]);
1854 }
1855 nConstraint += nBtm;
1856 testcase( pRangeStart->wtFlags & TERM_VIRTUAL );
1857 if( sqlite3ExprIsVector(pRight)==0 ){
1858 disableTerm(pLevel, pRangeStart);
1859 }else{
1860 startEq = 1;
1861 }
1862 bSeekPastNull = 0;
1863 }else if( bSeekPastNull ){
1864 startEq = 0;
1865 sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
1866 start_constraints = 1;
1867 nConstraint++;
1868 }else if( regBignull ){
1869 sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
1870 start_constraints = 1;
1871 nConstraint++;
1872 }
1873 codeApplyAffinity(pParse, regBase, nConstraint - bSeekPastNull, zStartAff);
1874 if( pLoop->nSkip>0 && nConstraint==pLoop->nSkip ){
1875 /* The skip-scan logic inside the call to codeAllEqualityConstraints()
1876 ** above has already left the cursor sitting on the correct row,
1877 ** so no further seeking is needed */
1878 }else{
1879 if( regBignull ){
1880 sqlite3VdbeAddOp2(v, OP_Integer, 1, regBignull);
1881 VdbeComment((v, "NULL-scan pass ctr"));
1882 }
1883 if( pLevel->regFilter ){
1884 sqlite3VdbeAddOp4Int(v, OP_Filter, pLevel->regFilter, addrNxt,
1885 regBase, nEq);
1886 VdbeCoverage(v);
1887 filterPullDown(pParse, pWInfo, iLevel, addrNxt, notReady);
1888 }
1889
1890 op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev];
1891 assert( op!=0 );
1892 if( (pLoop->wsFlags & WHERE_IN_SEEKSCAN)!=0 && op==OP_SeekGE ){
1893 assert( regBignull==0 );
1894 /* TUNING: The OP_SeekScan opcode seeks to reduce the number
1895 ** of expensive seek operations by replacing a single seek with
1896 ** 1 or more step operations. The question is, how many steps
1897 ** should we try before giving up and going with a seek. The cost
1898 ** of a seek is proportional to the logarithm of the of the number
1899 ** of entries in the tree, so basing the number of steps to try
1900 ** on the estimated number of rows in the btree seems like a good
1901 ** guess. */
1902 addrSeekScan = sqlite3VdbeAddOp1(v, OP_SeekScan,
1903 (pIdx->aiRowLogEst[0]+9)/10);
1904 if( pRangeStart ){
1905 sqlite3VdbeChangeP5(v, 1);
1906 sqlite3VdbeChangeP2(v, addrSeekScan, sqlite3VdbeCurrentAddr(v)+1);
1907 addrSeekScan = 0;
1908 }
1909 VdbeCoverage(v);
1910 }
1911 sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
1912 VdbeCoverage(v);
1913 VdbeCoverageIf(v, op==OP_Rewind); testcase( op==OP_Rewind );
1914 VdbeCoverageIf(v, op==OP_Last); testcase( op==OP_Last );
1915 VdbeCoverageIf(v, op==OP_SeekGT); testcase( op==OP_SeekGT );
1916 VdbeCoverageIf(v, op==OP_SeekGE); testcase( op==OP_SeekGE );
1917 VdbeCoverageIf(v, op==OP_SeekLE); testcase( op==OP_SeekLE );
1918 VdbeCoverageIf(v, op==OP_SeekLT); testcase( op==OP_SeekLT );
1919
1920 assert( bSeekPastNull==0 || bStopAtNull==0 );
1921 if( regBignull ){
1922 assert( bSeekPastNull==1 || bStopAtNull==1 );
1923 assert( bSeekPastNull==!bStopAtNull );
1924 assert( bStopAtNull==startEq );
1925 sqlite3VdbeAddOp2(v, OP_Goto, 0, sqlite3VdbeCurrentAddr(v)+2);
1926 op = aStartOp[(nConstraint>1)*4 + 2 + bRev];
1927 sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase,
1928 nConstraint-startEq);
1929 VdbeCoverage(v);
1930 VdbeCoverageIf(v, op==OP_Rewind); testcase( op==OP_Rewind );
1931 VdbeCoverageIf(v, op==OP_Last); testcase( op==OP_Last );
1932 VdbeCoverageIf(v, op==OP_SeekGE); testcase( op==OP_SeekGE );
1933 VdbeCoverageIf(v, op==OP_SeekLE); testcase( op==OP_SeekLE );
1934 assert( op==OP_Rewind || op==OP_Last || op==OP_SeekGE || op==OP_SeekLE);
1935 }
1936 }
1937
1938 /* Load the value for the inequality constraint at the end of the
1939 ** range (if any).
1940 */
1941 nConstraint = nEq;
1942 assert( pLevel->p2==0 );
1943 if( pRangeEnd ){
1944 Expr *pRight = pRangeEnd->pExpr->pRight;
1945 if( addrSeekScan ){
1946 /* For a seek-scan that has a range on the lowest term of the index,
1947 ** we have to make the top of the loop be code that sets the end
1948 ** condition of the range. Otherwise, the OP_SeekScan might jump
1949 ** over that initialization, leaving the range-end value set to the
1950 ** range-start value, resulting in a wrong answer.
1951 ** See ticket 5981a8c041a3c2f3 (2021-11-02).
1952 */
1953 pLevel->p2 = sqlite3VdbeCurrentAddr(v);
1954 }
1955 codeExprOrVector(pParse, pRight, regBase+nEq, nTop);
1956 whereLikeOptimizationStringFixup(v, pLevel, pRangeEnd);
1957 if( (pRangeEnd->wtFlags & TERM_VNULL)==0
1958 && sqlite3ExprCanBeNull(pRight)
1959 ){
1960 sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt);
1961 VdbeCoverage(v);
1962 }
1963 if( zEndAff ){
1964 updateRangeAffinityStr(pRight, nTop, zEndAff);
1965 codeApplyAffinity(pParse, regBase+nEq, nTop, zEndAff);
1966 }else{
1967 assert( pParse->db->mallocFailed );
1968 }
1969 nConstraint += nTop;
1970 testcase( pRangeEnd->wtFlags & TERM_VIRTUAL );
1971
1972 if( sqlite3ExprIsVector(pRight)==0 ){
1973 disableTerm(pLevel, pRangeEnd);
1974 }else{
1975 endEq = 1;
1976 }
1977 }else if( bStopAtNull ){
1978 if( regBignull==0 ){
1979 sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
1980 endEq = 0;
1981 }
1982 nConstraint++;
1983 }
1984 if( zStartAff ) sqlite3DbNNFreeNN(db, zStartAff);
1985 if( zEndAff ) sqlite3DbNNFreeNN(db, zEndAff);
1986
1987 /* Top of the loop body */
1988 if( pLevel->p2==0 ) pLevel->p2 = sqlite3VdbeCurrentAddr(v);
1989
1990 /* Check if the index cursor is past the end of the range. */
1991 if( nConstraint ){
1992 if( regBignull ){
1993 /* Except, skip the end-of-range check while doing the NULL-scan */
1994 sqlite3VdbeAddOp2(v, OP_IfNot, regBignull, sqlite3VdbeCurrentAddr(v)+3);
1995 VdbeComment((v, "If NULL-scan 2nd pass"));
1996 VdbeCoverage(v);
1997 }
1998 op = aEndOp[bRev*2 + endEq];
1999 sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
2000 testcase( op==OP_IdxGT ); VdbeCoverageIf(v, op==OP_IdxGT );
2001 testcase( op==OP_IdxGE ); VdbeCoverageIf(v, op==OP_IdxGE );
2002 testcase( op==OP_IdxLT ); VdbeCoverageIf(v, op==OP_IdxLT );
2003 testcase( op==OP_IdxLE ); VdbeCoverageIf(v, op==OP_IdxLE );
2004 if( addrSeekScan ) sqlite3VdbeJumpHere(v, addrSeekScan);
2005 }
2006 if( regBignull ){
2007 /* During a NULL-scan, check to see if we have reached the end of
2008 ** the NULLs */
2009 assert( bSeekPastNull==!bStopAtNull );
2010 assert( bSeekPastNull+bStopAtNull==1 );
2011 assert( nConstraint+bSeekPastNull>0 );
2012 sqlite3VdbeAddOp2(v, OP_If, regBignull, sqlite3VdbeCurrentAddr(v)+2);
2013 VdbeComment((v, "If NULL-scan 1st pass"));
2014 VdbeCoverage(v);
2015 op = aEndOp[bRev*2 + bSeekPastNull];
2016 sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase,
2017 nConstraint+bSeekPastNull);
2018 testcase( op==OP_IdxGT ); VdbeCoverageIf(v, op==OP_IdxGT );
2019 testcase( op==OP_IdxGE ); VdbeCoverageIf(v, op==OP_IdxGE );
2020 testcase( op==OP_IdxLT ); VdbeCoverageIf(v, op==OP_IdxLT );
2021 testcase( op==OP_IdxLE ); VdbeCoverageIf(v, op==OP_IdxLE );
2022 }
2023
2024 if( (pLoop->wsFlags & WHERE_IN_EARLYOUT)!=0 ){
2025 sqlite3VdbeAddOp3(v, OP_SeekHit, iIdxCur, nEq, nEq);
2026 }
2027
2028 /* Seek the table cursor, if required */
2029 omitTable = (pLoop->wsFlags & WHERE_IDX_ONLY)!=0
2030 && (pWInfo->wctrlFlags & (WHERE_OR_SUBCLAUSE|WHERE_RIGHT_JOIN))==0;
2031 if( omitTable ){
2032 /* pIdx is a covering index. No need to access the main table. */
2033 }else if( HasRowid(pIdx->pTable) ){
2034 codeDeferredSeek(pWInfo, pIdx, iCur, iIdxCur);
2035 }else if( iCur!=iIdxCur ){
2036 Index *pPk = sqlite3PrimaryKeyIndex(pIdx->pTable);
2037 iRowidReg = sqlite3GetTempRange(pParse, pPk->nKeyCol);
2038 for(j=0; j<pPk->nKeyCol; j++){
2039 k = sqlite3TableColumnToIndex(pIdx, pPk->aiColumn[j]);
2040 sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, k, iRowidReg+j);
2041 }
2042 sqlite3VdbeAddOp4Int(v, OP_NotFound, iCur, addrCont,
2043 iRowidReg, pPk->nKeyCol); VdbeCoverage(v);
2044 }
2045
2046 if( pLevel->iLeftJoin==0 ){
2047 /* If a partial index is driving the loop, try to eliminate WHERE clause
2048 ** terms from the query that must be true due to the WHERE clause of
2049 ** the partial index.
2050 **
2051 ** 2019-11-02 ticket 623eff57e76d45f6: This optimization does not work
2052 ** for a LEFT JOIN.
2053 */
2054 if( pIdx->pPartIdxWhere ){
2055 whereApplyPartialIndexConstraints(pIdx->pPartIdxWhere, iCur, pWC);
2056 }
2057 }else{
2058 testcase( pIdx->pPartIdxWhere );
2059 /* The following assert() is not a requirement, merely an observation:
2060 ** The OR-optimization doesn't work for the right hand table of
2061 ** a LEFT JOIN: */
2062 assert( (pWInfo->wctrlFlags & (WHERE_OR_SUBCLAUSE|WHERE_RIGHT_JOIN))==0 );
2063 }
2064
2065 /* Record the instruction used to terminate the loop. */
2066 if( pLoop->wsFlags & WHERE_ONEROW ){
2067 pLevel->op = OP_Noop;
2068 }else if( bRev ){
2069 pLevel->op = OP_Prev;
2070 }else{
2071 pLevel->op = OP_Next;
2072 }
2073 pLevel->p1 = iIdxCur;
2074 pLevel->p3 = (pLoop->wsFlags&WHERE_UNQ_WANTED)!=0 ? 1:0;
2075 if( (pLoop->wsFlags & WHERE_CONSTRAINT)==0 ){
2076 pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
2077 }else{
2078 assert( pLevel->p5==0 );
2079 }
2080 if( omitTable ) pIdx = 0;
2081 }else
2082
2083#ifndef SQLITE_OMIT_OR_OPTIMIZATION
2084 if( pLoop->wsFlags & WHERE_MULTI_OR ){
2085 /* Case 5: Two or more separately indexed terms connected by OR
2086 **
2087 ** Example:
2088 **
2089 ** CREATE TABLE t1(a,b,c,d);
2090 ** CREATE INDEX i1 ON t1(a);
2091 ** CREATE INDEX i2 ON t1(b);
2092 ** CREATE INDEX i3 ON t1(c);
2093 **
2094 ** SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
2095 **
2096 ** In the example, there are three indexed terms connected by OR.
2097 ** The top of the loop looks like this:
2098 **
2099 ** Null 1 # Zero the rowset in reg 1
2100 **
2101 ** Then, for each indexed term, the following. The arguments to
2102 ** RowSetTest are such that the rowid of the current row is inserted
2103 ** into the RowSet. If it is already present, control skips the
2104 ** Gosub opcode and jumps straight to the code generated by WhereEnd().
2105 **
2106 ** sqlite3WhereBegin(<term>)
2107 ** RowSetTest # Insert rowid into rowset
2108 ** Gosub 2 A
2109 ** sqlite3WhereEnd()
2110 **
2111 ** Following the above, code to terminate the loop. Label A, the target
2112 ** of the Gosub above, jumps to the instruction right after the Goto.
2113 **
2114 ** Null 1 # Zero the rowset in reg 1
2115 ** Goto B # The loop is finished.
2116 **
2117 ** A: <loop body> # Return data, whatever.
2118 **
2119 ** Return 2 # Jump back to the Gosub
2120 **
2121 ** B: <after the loop>
2122 **
2123 ** Added 2014-05-26: If the table is a WITHOUT ROWID table, then
2124 ** use an ephemeral index instead of a RowSet to record the primary
2125 ** keys of the rows we have already seen.
2126 **
2127 */
2128 WhereClause *pOrWc; /* The OR-clause broken out into subterms */
2129 SrcList *pOrTab; /* Shortened table list or OR-clause generation */
2130 Index *pCov = 0; /* Potential covering index (or NULL) */
2131 int iCovCur = pParse->nTab++; /* Cursor used for index scans (if any) */
2132
2133 int regReturn = ++pParse->nMem; /* Register used with OP_Gosub */
2134 int regRowset = 0; /* Register for RowSet object */
2135 int regRowid = 0; /* Register holding rowid */
2136 int iLoopBody = sqlite3VdbeMakeLabel(pParse);/* Start of loop body */
2137 int iRetInit; /* Address of regReturn init */
2138 int untestedTerms = 0; /* Some terms not completely tested */
2139 int ii; /* Loop counter */
2140 Expr *pAndExpr = 0; /* An ".. AND (...)" expression */
2141 Table *pTab = pTabItem->pTab;
2142
2143 pTerm = pLoop->aLTerm[0];
2144 assert( pTerm!=0 );
2145 assert( pTerm->eOperator & WO_OR );
2146 assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
2147 pOrWc = &pTerm->u.pOrInfo->wc;
2148 pLevel->op = OP_Return;
2149 pLevel->p1 = regReturn;
2150
2151 /* Set up a new SrcList in pOrTab containing the table being scanned
2152 ** by this loop in the a[0] slot and all notReady tables in a[1..] slots.
2153 ** This becomes the SrcList in the recursive call to sqlite3WhereBegin().
2154 */
2155 if( pWInfo->nLevel>1 ){
2156 int nNotReady; /* The number of notReady tables */
2157 SrcItem *origSrc; /* Original list of tables */
2158 nNotReady = pWInfo->nLevel - iLevel - 1;
2159 pOrTab = sqlite3DbMallocRawNN(db,
2160 sizeof(*pOrTab)+ nNotReady*sizeof(pOrTab->a[0]));
2161 if( pOrTab==0 ) return notReady;
2162 pOrTab->nAlloc = (u8)(nNotReady + 1);
2163 pOrTab->nSrc = pOrTab->nAlloc;
2164 memcpy(pOrTab->a, pTabItem, sizeof(*pTabItem));
2165 origSrc = pWInfo->pTabList->a;
2166 for(k=1; k<=nNotReady; k++){
2167 memcpy(&pOrTab->a[k], &origSrc[pLevel[k].iFrom], sizeof(pOrTab->a[k]));
2168 }
2169 }else{
2170 pOrTab = pWInfo->pTabList;
2171 }
2172
2173 /* Initialize the rowset register to contain NULL. An SQL NULL is
2174 ** equivalent to an empty rowset. Or, create an ephemeral index
2175 ** capable of holding primary keys in the case of a WITHOUT ROWID.
2176 **
2177 ** Also initialize regReturn to contain the address of the instruction
2178 ** immediately following the OP_Return at the bottom of the loop. This
2179 ** is required in a few obscure LEFT JOIN cases where control jumps
2180 ** over the top of the loop into the body of it. In this case the
2181 ** correct response for the end-of-loop code (the OP_Return) is to
2182 ** fall through to the next instruction, just as an OP_Next does if
2183 ** called on an uninitialized cursor.
2184 */
2185 if( (pWInfo->wctrlFlags & WHERE_DUPLICATES_OK)==0 ){
2186 if( HasRowid(pTab) ){
2187 regRowset = ++pParse->nMem;
2188 sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset);
2189 }else{
2190 Index *pPk = sqlite3PrimaryKeyIndex(pTab);
2191 regRowset = pParse->nTab++;
2192 sqlite3VdbeAddOp2(v, OP_OpenEphemeral, regRowset, pPk->nKeyCol);
2193 sqlite3VdbeSetP4KeyInfo(pParse, pPk);
2194 }
2195 regRowid = ++pParse->nMem;
2196 }
2197 iRetInit = sqlite3VdbeAddOp2(v, OP_Integer, 0, regReturn);
2198
2199 /* If the original WHERE clause is z of the form: (x1 OR x2 OR ...) AND y
2200 ** Then for every term xN, evaluate as the subexpression: xN AND y
2201 ** That way, terms in y that are factored into the disjunction will
2202 ** be picked up by the recursive calls to sqlite3WhereBegin() below.
2203 **
2204 ** Actually, each subexpression is converted to "xN AND w" where w is
2205 ** the "interesting" terms of z - terms that did not originate in the
2206 ** ON or USING clause of a LEFT JOIN, and terms that are usable as
2207 ** indices.
2208 **
2209 ** This optimization also only applies if the (x1 OR x2 OR ...) term
2210 ** is not contained in the ON clause of a LEFT JOIN.
2211 ** See ticket http://www.sqlite.org/src/info/f2369304e4
2212 **
2213 ** 2022-02-04: Do not push down slices of a row-value comparison.
2214 ** In other words, "w" or "y" may not be a slice of a vector. Otherwise,
2215 ** the initialization of the right-hand operand of the vector comparison
2216 ** might not occur, or might occur only in an OR branch that is not
2217 ** taken. dbsqlfuzz 80a9fade844b4fb43564efc972bcb2c68270f5d1.
2218 **
2219 ** 2022-03-03: Do not push down expressions that involve subqueries.
2220 ** The subquery might get coded as a subroutine. Any table-references
2221 ** in the subquery might be resolved to index-references for the index on
2222 ** the OR branch in which the subroutine is coded. But if the subroutine
2223 ** is invoked from a different OR branch that uses a different index, such
2224 ** index-references will not work. tag-20220303a
2225 ** https://sqlite.org/forum/forumpost/36937b197273d403
2226 */
2227 if( pWC->nTerm>1 ){
2228 int iTerm;
2229 for(iTerm=0; iTerm<pWC->nTerm; iTerm++){
2230 Expr *pExpr = pWC->a[iTerm].pExpr;
2231 if( &pWC->a[iTerm] == pTerm ) continue;
2232 testcase( pWC->a[iTerm].wtFlags & TERM_VIRTUAL );
2233 testcase( pWC->a[iTerm].wtFlags & TERM_CODED );
2234 testcase( pWC->a[iTerm].wtFlags & TERM_SLICE );
2235 if( (pWC->a[iTerm].wtFlags & (TERM_VIRTUAL|TERM_CODED|TERM_SLICE))!=0 ){
2236 continue;
2237 }
2238 if( (pWC->a[iTerm].eOperator & WO_ALL)==0 ) continue;
2239 if( ExprHasProperty(pExpr, EP_Subquery) ) continue; /* tag-20220303a */
2240 pExpr = sqlite3ExprDup(db, pExpr, 0);
2241 pAndExpr = sqlite3ExprAnd(pParse, pAndExpr, pExpr);
2242 }
2243 if( pAndExpr ){
2244 /* The extra 0x10000 bit on the opcode is masked off and does not
2245 ** become part of the new Expr.op. However, it does make the
2246 ** op==TK_AND comparison inside of sqlite3PExpr() false, and this
2247 ** prevents sqlite3PExpr() from applying the AND short-circuit
2248 ** optimization, which we do not want here. */
2249 pAndExpr = sqlite3PExpr(pParse, TK_AND|0x10000, 0, pAndExpr);
2250 }
2251 }
2252
2253 /* Run a separate WHERE clause for each term of the OR clause. After
2254 ** eliminating duplicates from other WHERE clauses, the action for each
2255 ** sub-WHERE clause is to to invoke the main loop body as a subroutine.
2256 */
2257 ExplainQueryPlan((pParse, 1, "MULTI-INDEX OR"));
2258 for(ii=0; ii<pOrWc->nTerm; ii++){
2259 WhereTerm *pOrTerm = &pOrWc->a[ii];
2260 if( pOrTerm->leftCursor==iCur || (pOrTerm->eOperator & WO_AND)!=0 ){
2261 WhereInfo *pSubWInfo; /* Info for single OR-term scan */
2262 Expr *pOrExpr = pOrTerm->pExpr; /* Current OR clause term */
2263 Expr *pDelete; /* Local copy of OR clause term */
2264 int jmp1 = 0; /* Address of jump operation */
2265 testcase( (pTabItem[0].fg.jointype & JT_LEFT)!=0
2266 && !ExprHasProperty(pOrExpr, EP_OuterON)
2267 ); /* See TH3 vtab25.400 and ticket 614b25314c766238 */
2268 pDelete = pOrExpr = sqlite3ExprDup(db, pOrExpr, 0);
2269 if( db->mallocFailed ){
2270 sqlite3ExprDelete(db, pDelete);
2271 continue;
2272 }
2273 if( pAndExpr ){
2274 pAndExpr->pLeft = pOrExpr;
2275 pOrExpr = pAndExpr;
2276 }
2277 /* Loop through table entries that match term pOrTerm. */
2278 ExplainQueryPlan((pParse, 1, "INDEX %d", ii+1));
2279 WHERETRACE(0xffff, ("Subplan for OR-clause:\n"));
2280 pSubWInfo = sqlite3WhereBegin(pParse, pOrTab, pOrExpr, 0, 0, 0,
2281 WHERE_OR_SUBCLAUSE, iCovCur);
2282 assert( pSubWInfo || pParse->nErr );
2283 if( pSubWInfo ){
2284 WhereLoop *pSubLoop;
2285 int addrExplain = sqlite3WhereExplainOneScan(
2286 pParse, pOrTab, &pSubWInfo->a[0], 0
2287 );
2288 sqlite3WhereAddScanStatus(v, pOrTab, &pSubWInfo->a[0], addrExplain);
2289
2290 /* This is the sub-WHERE clause body. First skip over
2291 ** duplicate rows from prior sub-WHERE clauses, and record the
2292 ** rowid (or PRIMARY KEY) for the current row so that the same
2293 ** row will be skipped in subsequent sub-WHERE clauses.
2294 */
2295 if( (pWInfo->wctrlFlags & WHERE_DUPLICATES_OK)==0 ){
2296 int iSet = ((ii==pOrWc->nTerm-1)?-1:ii);
2297 if( HasRowid(pTab) ){
2298 sqlite3ExprCodeGetColumnOfTable(v, pTab, iCur, -1, regRowid);
2299 jmp1 = sqlite3VdbeAddOp4Int(v, OP_RowSetTest, regRowset, 0,
2300 regRowid, iSet);
2301 VdbeCoverage(v);
2302 }else{
2303 Index *pPk = sqlite3PrimaryKeyIndex(pTab);
2304 int nPk = pPk->nKeyCol;
2305 int iPk;
2306 int r;
2307
2308 /* Read the PK into an array of temp registers. */
2309 r = sqlite3GetTempRange(pParse, nPk);
2310 for(iPk=0; iPk<nPk; iPk++){
2311 int iCol = pPk->aiColumn[iPk];
2312 sqlite3ExprCodeGetColumnOfTable(v, pTab, iCur, iCol,r+iPk);
2313 }
2314
2315 /* Check if the temp table already contains this key. If so,
2316 ** the row has already been included in the result set and
2317 ** can be ignored (by jumping past the Gosub below). Otherwise,
2318 ** insert the key into the temp table and proceed with processing
2319 ** the row.
2320 **
2321 ** Use some of the same optimizations as OP_RowSetTest: If iSet
2322 ** is zero, assume that the key cannot already be present in
2323 ** the temp table. And if iSet is -1, assume that there is no
2324 ** need to insert the key into the temp table, as it will never
2325 ** be tested for. */
2326 if( iSet ){
2327 jmp1 = sqlite3VdbeAddOp4Int(v, OP_Found, regRowset, 0, r, nPk);
2328 VdbeCoverage(v);
2329 }
2330 if( iSet>=0 ){
2331 sqlite3VdbeAddOp3(v, OP_MakeRecord, r, nPk, regRowid);
2332 sqlite3VdbeAddOp4Int(v, OP_IdxInsert, regRowset, regRowid,
2333 r, nPk);
2334 if( iSet ) sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);
2335 }
2336
2337 /* Release the array of temp registers */
2338 sqlite3ReleaseTempRange(pParse, r, nPk);
2339 }
2340 }
2341
2342 /* Invoke the main loop body as a subroutine */
2343 sqlite3VdbeAddOp2(v, OP_Gosub, regReturn, iLoopBody);
2344
2345 /* Jump here (skipping the main loop body subroutine) if the
2346 ** current sub-WHERE row is a duplicate from prior sub-WHEREs. */
2347 if( jmp1 ) sqlite3VdbeJumpHere(v, jmp1);
2348
2349 /* The pSubWInfo->untestedTerms flag means that this OR term
2350 ** contained one or more AND term from a notReady table. The
2351 ** terms from the notReady table could not be tested and will
2352 ** need to be tested later.
2353 */
2354 if( pSubWInfo->untestedTerms ) untestedTerms = 1;
2355
2356 /* If all of the OR-connected terms are optimized using the same
2357 ** index, and the index is opened using the same cursor number
2358 ** by each call to sqlite3WhereBegin() made by this loop, it may
2359 ** be possible to use that index as a covering index.
2360 **
2361 ** If the call to sqlite3WhereBegin() above resulted in a scan that
2362 ** uses an index, and this is either the first OR-connected term
2363 ** processed or the index is the same as that used by all previous
2364 ** terms, set pCov to the candidate covering index. Otherwise, set
2365 ** pCov to NULL to indicate that no candidate covering index will
2366 ** be available.
2367 */
2368 pSubLoop = pSubWInfo->a[0].pWLoop;
2369 assert( (pSubLoop->wsFlags & WHERE_AUTO_INDEX)==0 );
2370 if( (pSubLoop->wsFlags & WHERE_INDEXED)!=0
2371 && (ii==0 || pSubLoop->u.btree.pIndex==pCov)
2372 && (HasRowid(pTab) || !IsPrimaryKeyIndex(pSubLoop->u.btree.pIndex))
2373 ){
2374 assert( pSubWInfo->a[0].iIdxCur==iCovCur );
2375 pCov = pSubLoop->u.btree.pIndex;
2376 }else{
2377 pCov = 0;
2378 }
2379 if( sqlite3WhereUsesDeferredSeek(pSubWInfo) ){
2380 pWInfo->bDeferredSeek = 1;
2381 }
2382
2383 /* Finish the loop through table entries that match term pOrTerm. */
2384 sqlite3WhereEnd(pSubWInfo);
2385 ExplainQueryPlanPop(pParse);
2386 }
2387 sqlite3ExprDelete(db, pDelete);
2388 }
2389 }
2390 ExplainQueryPlanPop(pParse);
2391 assert( pLevel->pWLoop==pLoop );
2392 assert( (pLoop->wsFlags & WHERE_MULTI_OR)!=0 );
2393 assert( (pLoop->wsFlags & WHERE_IN_ABLE)==0 );
2394 pLevel->u.pCoveringIdx = pCov;
2395 if( pCov ) pLevel->iIdxCur = iCovCur;
2396 if( pAndExpr ){
2397 pAndExpr->pLeft = 0;
2398 sqlite3ExprDelete(db, pAndExpr);
2399 }
2400 sqlite3VdbeChangeP1(v, iRetInit, sqlite3VdbeCurrentAddr(v));
2401 sqlite3VdbeGoto(v, pLevel->addrBrk);
2402 sqlite3VdbeResolveLabel(v, iLoopBody);
2403
2404 /* Set the P2 operand of the OP_Return opcode that will end the current
2405 ** loop to point to this spot, which is the top of the next containing
2406 ** loop. The byte-code formatter will use that P2 value as a hint to
2407 ** indent everything in between the this point and the final OP_Return.
2408 ** See tag-20220407a in vdbe.c and shell.c */
2409 assert( pLevel->op==OP_Return );
2410 pLevel->p2 = sqlite3VdbeCurrentAddr(v);
2411
2412 if( pWInfo->nLevel>1 ){ sqlite3DbFreeNN(db, pOrTab); }
2413 if( !untestedTerms ) disableTerm(pLevel, pTerm);
2414 }else
2415#endif /* SQLITE_OMIT_OR_OPTIMIZATION */
2416
2417 {
2418 /* Case 6: There is no usable index. We must do a complete
2419 ** scan of the entire table.
2420 */
2421 static const u8 aStep[] = { OP_Next, OP_Prev };
2422 static const u8 aStart[] = { OP_Rewind, OP_Last };
2423 assert( bRev==0 || bRev==1 );
2424 if( pTabItem->fg.isRecursive ){
2425 /* Tables marked isRecursive have only a single row that is stored in
2426 ** a pseudo-cursor. No need to Rewind or Next such cursors. */
2427 pLevel->op = OP_Noop;
2428 }else{
2429 codeCursorHint(pTabItem, pWInfo, pLevel, 0);
2430 pLevel->op = aStep[bRev];
2431 pLevel->p1 = iCur;
2432 pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrHalt);
2433 VdbeCoverageIf(v, bRev==0);
2434 VdbeCoverageIf(v, bRev!=0);
2435 pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
2436 }
2437 }
2438
2439#ifdef SQLITE_ENABLE_STMT_SCANSTATUS
2440 pLevel->addrVisit = sqlite3VdbeCurrentAddr(v);
2441#endif
2442
2443 /* Insert code to test every subexpression that can be completely
2444 ** computed using the current set of tables.
2445 **
2446 ** This loop may run between one and three times, depending on the
2447 ** constraints to be generated. The value of stack variable iLoop
2448 ** determines the constraints coded by each iteration, as follows:
2449 **
2450 ** iLoop==1: Code only expressions that are entirely covered by pIdx.
2451 ** iLoop==2: Code remaining expressions that do not contain correlated
2452 ** sub-queries.
2453 ** iLoop==3: Code all remaining expressions.
2454 **
2455 ** An effort is made to skip unnecessary iterations of the loop.
2456 */
2457 iLoop = (pIdx ? 1 : 2);
2458 do{
2459 int iNext = 0; /* Next value for iLoop */
2460 for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){
2461 Expr *pE;
2462 int skipLikeAddr = 0;
2463 testcase( pTerm->wtFlags & TERM_VIRTUAL );
2464 testcase( pTerm->wtFlags & TERM_CODED );
2465 if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
2466 if( (pTerm->prereqAll & pLevel->notReady)!=0 ){
2467 testcase( pWInfo->untestedTerms==0
2468 && (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)!=0 );
2469 pWInfo->untestedTerms = 1;
2470 continue;
2471 }
2472 pE = pTerm->pExpr;
2473 assert( pE!=0 );
2474 if( pTabItem->fg.jointype & (JT_LEFT|JT_LTORJ|JT_RIGHT) ){
2475 if( !ExprHasProperty(pE,EP_OuterON|EP_InnerON) ){
2476 /* Defer processing WHERE clause constraints until after outer
2477 ** join processing. tag-20220513a */
2478 continue;
2479 }else if( (pTabItem->fg.jointype & JT_LEFT)==JT_LEFT
2480 && !ExprHasProperty(pE,EP_OuterON) ){
2481 continue;
2482 }else{
2483 Bitmask m = sqlite3WhereGetMask(&pWInfo->sMaskSet, pE->w.iJoin);
2484 if( m & pLevel->notReady ){
2485 /* An ON clause that is not ripe */
2486 continue;
2487 }
2488 }
2489 }
2490 if( iLoop==1 && !sqlite3ExprCoveredByIndex(pE, pLevel->iTabCur, pIdx) ){
2491 iNext = 2;
2492 continue;
2493 }
2494 if( iLoop<3 && (pTerm->wtFlags & TERM_VARSELECT) ){
2495 if( iNext==0 ) iNext = 3;
2496 continue;
2497 }
2498
2499 if( (pTerm->wtFlags & TERM_LIKECOND)!=0 ){
2500 /* If the TERM_LIKECOND flag is set, that means that the range search
2501 ** is sufficient to guarantee that the LIKE operator is true, so we
2502 ** can skip the call to the like(A,B) function. But this only works
2503 ** for strings. So do not skip the call to the function on the pass
2504 ** that compares BLOBs. */
2505#ifdef SQLITE_LIKE_DOESNT_MATCH_BLOBS
2506 continue;
2507#else
2508 u32 x = pLevel->iLikeRepCntr;
2509 if( x>0 ){
2510 skipLikeAddr = sqlite3VdbeAddOp1(v, (x&1)?OP_IfNot:OP_If,(int)(x>>1));
2511 VdbeCoverageIf(v, (x&1)==1);
2512 VdbeCoverageIf(v, (x&1)==0);
2513 }
2514#endif
2515 }
2516#ifdef WHERETRACE_ENABLED /* 0xffff */
2517 if( sqlite3WhereTrace ){
2518 VdbeNoopComment((v, "WhereTerm[%d] (%p) priority=%d",
2519 pWC->nTerm-j, pTerm, iLoop));
2520 }
2521 if( sqlite3WhereTrace & 0x800 ){
2522 sqlite3DebugPrintf("Coding auxiliary constraint:\n");
2523 sqlite3WhereTermPrint(pTerm, pWC->nTerm-j);
2524 }
2525#endif
2526 sqlite3ExprIfFalse(pParse, pE, addrCont, SQLITE_JUMPIFNULL);
2527 if( skipLikeAddr ) sqlite3VdbeJumpHere(v, skipLikeAddr);
2528 pTerm->wtFlags |= TERM_CODED;
2529 }
2530 iLoop = iNext;
2531 }while( iLoop>0 );
2532
2533 /* Insert code to test for implied constraints based on transitivity
2534 ** of the "==" operator.
2535 **
2536 ** Example: If the WHERE clause contains "t1.a=t2.b" and "t2.b=123"
2537 ** and we are coding the t1 loop and the t2 loop has not yet coded,
2538 ** then we cannot use the "t1.a=t2.b" constraint, but we can code
2539 ** the implied "t1.a=123" constraint.
2540 */
2541 for(pTerm=pWC->a, j=pWC->nBase; j>0; j--, pTerm++){
2542 Expr *pE, sEAlt;
2543 WhereTerm *pAlt;
2544 if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
2545 if( (pTerm->eOperator & (WO_EQ|WO_IS))==0 ) continue;
2546 if( (pTerm->eOperator & WO_EQUIV)==0 ) continue;
2547 if( pTerm->leftCursor!=iCur ) continue;
2548 if( pTabItem->fg.jointype & (JT_LEFT|JT_LTORJ|JT_RIGHT) ) continue;
2549 pE = pTerm->pExpr;
2550#ifdef WHERETRACE_ENABLED /* 0x800 */
2551 if( sqlite3WhereTrace & 0x800 ){
2552 sqlite3DebugPrintf("Coding transitive constraint:\n");
2553 sqlite3WhereTermPrint(pTerm, pWC->nTerm-j);
2554 }
2555#endif
2556 assert( !ExprHasProperty(pE, EP_OuterON) );
2557 assert( (pTerm->prereqRight & pLevel->notReady)!=0 );
2558 assert( (pTerm->eOperator & (WO_OR|WO_AND))==0 );
2559 pAlt = sqlite3WhereFindTerm(pWC, iCur, pTerm->u.x.leftColumn, notReady,
2560 WO_EQ|WO_IN|WO_IS, 0);
2561 if( pAlt==0 ) continue;
2562 if( pAlt->wtFlags & (TERM_CODED) ) continue;
2563 if( (pAlt->eOperator & WO_IN)
2564 && ExprUseXSelect(pAlt->pExpr)
2565 && (pAlt->pExpr->x.pSelect->pEList->nExpr>1)
2566 ){
2567 continue;
2568 }
2569 testcase( pAlt->eOperator & WO_EQ );
2570 testcase( pAlt->eOperator & WO_IS );
2571 testcase( pAlt->eOperator & WO_IN );
2572 VdbeModuleComment((v, "begin transitive constraint"));
2573 sEAlt = *pAlt->pExpr;
2574 sEAlt.pLeft = pE->pLeft;
2575 sqlite3ExprIfFalse(pParse, &sEAlt, addrCont, SQLITE_JUMPIFNULL);
2576 pAlt->wtFlags |= TERM_CODED;
2577 }
2578
2579 /* For a RIGHT OUTER JOIN, record the fact that the current row has
2580 ** been matched at least once.
2581 */
2582 if( pLevel->pRJ ){
2583 Table *pTab;
2584 int nPk;
2585 int r;
2586 int jmp1 = 0;
2587 WhereRightJoin *pRJ = pLevel->pRJ;
2588
2589 /* pTab is the right-hand table of the RIGHT JOIN. Generate code that
2590 ** will record that the current row of that table has been matched at
2591 ** least once. This is accomplished by storing the PK for the row in
2592 ** both the iMatch index and the regBloom Bloom filter.
2593 */
2594 pTab = pWInfo->pTabList->a[pLevel->iFrom].pTab;
2595 if( HasRowid(pTab) ){
2596 r = sqlite3GetTempRange(pParse, 2);
2597 sqlite3ExprCodeGetColumnOfTable(v, pTab, pLevel->iTabCur, -1, r+1);
2598 nPk = 1;
2599 }else{
2600 int iPk;
2601 Index *pPk = sqlite3PrimaryKeyIndex(pTab);
2602 nPk = pPk->nKeyCol;
2603 r = sqlite3GetTempRange(pParse, nPk+1);
2604 for(iPk=0; iPk<nPk; iPk++){
2605 int iCol = pPk->aiColumn[iPk];
2606 sqlite3ExprCodeGetColumnOfTable(v, pTab, iCur, iCol,r+1+iPk);
2607 }
2608 }
2609 jmp1 = sqlite3VdbeAddOp4Int(v, OP_Found, pRJ->iMatch, 0, r+1, nPk);
2610 VdbeCoverage(v);
2611 VdbeComment((v, "match against %s", pTab->zName));
2612 sqlite3VdbeAddOp3(v, OP_MakeRecord, r+1, nPk, r);
2613 sqlite3VdbeAddOp4Int(v, OP_IdxInsert, pRJ->iMatch, r, r+1, nPk);
2614 sqlite3VdbeAddOp4Int(v, OP_FilterAdd, pRJ->regBloom, 0, r+1, nPk);
2615 sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);
2616 sqlite3VdbeJumpHere(v, jmp1);
2617 sqlite3ReleaseTempRange(pParse, r, nPk+1);
2618 }
2619
2620 /* For a LEFT OUTER JOIN, generate code that will record the fact that
2621 ** at least one row of the right table has matched the left table.
2622 */
2623 if( pLevel->iLeftJoin ){
2624 pLevel->addrFirst = sqlite3VdbeCurrentAddr(v);
2625 sqlite3VdbeAddOp2(v, OP_Integer, 1, pLevel->iLeftJoin);
2626 VdbeComment((v, "record LEFT JOIN hit"));
2627 if( pLevel->pRJ==0 ){
2628 goto code_outer_join_constraints; /* WHERE clause constraints */
2629 }
2630 }
2631
2632 if( pLevel->pRJ ){
2633 /* Create a subroutine used to process all interior loops and code
2634 ** of the RIGHT JOIN. During normal operation, the subroutine will
2635 ** be in-line with the rest of the code. But at the end, a separate
2636 ** loop will run that invokes this subroutine for unmatched rows
2637 ** of pTab, with all tables to left begin set to NULL.
2638 */
2639 WhereRightJoin *pRJ = pLevel->pRJ;
2640 sqlite3VdbeAddOp2(v, OP_BeginSubrtn, 0, pRJ->regReturn);
2641 pRJ->addrSubrtn = sqlite3VdbeCurrentAddr(v);
2642 assert( pParse->withinRJSubrtn < 255 );
2643 pParse->withinRJSubrtn++;
2644
2645 /* WHERE clause constraints must be deferred until after outer join
2646 ** row elimination has completed, since WHERE clause constraints apply
2647 ** to the results of the OUTER JOIN. The following loop generates the
2648 ** appropriate WHERE clause constraint checks. tag-20220513a.
2649 */
2650 code_outer_join_constraints:
2651 for(pTerm=pWC->a, j=0; j<pWC->nBase; j++, pTerm++){
2652 testcase( pTerm->wtFlags & TERM_VIRTUAL );
2653 testcase( pTerm->wtFlags & TERM_CODED );
2654 if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
2655 if( (pTerm->prereqAll & pLevel->notReady)!=0 ){
2656 assert( pWInfo->untestedTerms );
2657 continue;
2658 }
2659 if( pTabItem->fg.jointype & JT_LTORJ ) continue;
2660 assert( pTerm->pExpr );
2661 sqlite3ExprIfFalse(pParse, pTerm->pExpr, addrCont, SQLITE_JUMPIFNULL);
2662 pTerm->wtFlags |= TERM_CODED;
2663 }
2664 }
2665
2666#if WHERETRACE_ENABLED /* 0x20800 */
2667 if( sqlite3WhereTrace & 0x20000 ){
2668 sqlite3DebugPrintf("All WHERE-clause terms after coding level %d:\n",
2669 iLevel);
2670 sqlite3WhereClausePrint(pWC);
2671 }
2672 if( sqlite3WhereTrace & 0x800 ){
2673 sqlite3DebugPrintf("End Coding level %d: notReady=%llx\n",
2674 iLevel, (u64)pLevel->notReady);
2675 }
2676#endif
2677 return pLevel->notReady;
2678}
2679
2680/*
2681** Generate the code for the loop that finds all non-matched terms
2682** for a RIGHT JOIN.
2683*/
2684SQLITE_NOINLINE void sqlite3WhereRightJoinLoop(
2685 WhereInfo *pWInfo,
2686 int iLevel,
2687 WhereLevel *pLevel
2688){
2689 Parse *pParse = pWInfo->pParse;
2690 Vdbe *v = pParse->pVdbe;
2691 WhereRightJoin *pRJ = pLevel->pRJ;
2692 Expr *pSubWhere = 0;
2693 WhereClause *pWC = &pWInfo->sWC;
2694 WhereInfo *pSubWInfo;
2695 WhereLoop *pLoop = pLevel->pWLoop;
2696 SrcItem *pTabItem = &pWInfo->pTabList->a[pLevel->iFrom];
2697 SrcList sFrom;
2698 Bitmask mAll = 0;
2699 int k;
2700
2701 ExplainQueryPlan((pParse, 1, "RIGHT-JOIN %s", pTabItem->pTab->zName));
2702 sqlite3VdbeNoJumpsOutsideSubrtn(v, pRJ->addrSubrtn, pRJ->endSubrtn,
2703 pRJ->regReturn);
2704 for(k=0; k<iLevel; k++){
2705 int iIdxCur;
2706 mAll |= pWInfo->a[k].pWLoop->maskSelf;
2707 sqlite3VdbeAddOp1(v, OP_NullRow, pWInfo->a[k].iTabCur);
2708 iIdxCur = pWInfo->a[k].iIdxCur;
2709 if( iIdxCur ){
2710 sqlite3VdbeAddOp1(v, OP_NullRow, iIdxCur);
2711 }
2712 }
2713 if( (pTabItem->fg.jointype & JT_LTORJ)==0 ){
2714 mAll |= pLoop->maskSelf;
2715 for(k=0; k<pWC->nTerm; k++){
2716 WhereTerm *pTerm = &pWC->a[k];
2717 if( (pTerm->wtFlags & (TERM_VIRTUAL|TERM_SLICE))!=0
2718 && pTerm->eOperator!=WO_ROWVAL
2719 ){
2720 break;
2721 }
2722 if( pTerm->prereqAll & ~mAll ) continue;
2723 if( ExprHasProperty(pTerm->pExpr, EP_OuterON|EP_InnerON) ) continue;
2724 pSubWhere = sqlite3ExprAnd(pParse, pSubWhere,
2725 sqlite3ExprDup(pParse->db, pTerm->pExpr, 0));
2726 }
2727 }
2728 sFrom.nSrc = 1;
2729 sFrom.nAlloc = 1;
2730 memcpy(&sFrom.a[0], pTabItem, sizeof(SrcItem));
2731 sFrom.a[0].fg.jointype = 0;
2732 assert( pParse->withinRJSubrtn < 100 );
2733 pParse->withinRJSubrtn++;
2734 pSubWInfo = sqlite3WhereBegin(pParse, &sFrom, pSubWhere, 0, 0, 0,
2735 WHERE_RIGHT_JOIN, 0);
2736 if( pSubWInfo ){
2737 int iCur = pLevel->iTabCur;
2738 int r = ++pParse->nMem;
2739 int nPk;
2740 int jmp;
2741 int addrCont = sqlite3WhereContinueLabel(pSubWInfo);
2742 Table *pTab = pTabItem->pTab;
2743 if( HasRowid(pTab) ){
2744 sqlite3ExprCodeGetColumnOfTable(v, pTab, iCur, -1, r);
2745 nPk = 1;
2746 }else{
2747 int iPk;
2748 Index *pPk = sqlite3PrimaryKeyIndex(pTab);
2749 nPk = pPk->nKeyCol;
2750 pParse->nMem += nPk - 1;
2751 for(iPk=0; iPk<nPk; iPk++){
2752 int iCol = pPk->aiColumn[iPk];
2753 sqlite3ExprCodeGetColumnOfTable(v, pTab, iCur, iCol,r+iPk);
2754 }
2755 }
2756 jmp = sqlite3VdbeAddOp4Int(v, OP_Filter, pRJ->regBloom, 0, r, nPk);
2757 VdbeCoverage(v);
2758 sqlite3VdbeAddOp4Int(v, OP_Found, pRJ->iMatch, addrCont, r, nPk);
2759 VdbeCoverage(v);
2760 sqlite3VdbeJumpHere(v, jmp);
2761 sqlite3VdbeAddOp2(v, OP_Gosub, pRJ->regReturn, pRJ->addrSubrtn);
2762 sqlite3WhereEnd(pSubWInfo);
2763 }
2764 sqlite3ExprDelete(pParse->db, pSubWhere);
2765 ExplainQueryPlanPop(pParse);
2766 assert( pParse->withinRJSubrtn>0 );
2767 pParse->withinRJSubrtn--;
2768}
2769