blob: 9c51b5669c2821e5200bb75f6685a2c7d5afcdaf [file] [log] [blame]
drh6f82e852015-06-06 20:12:09 +00001/*
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
dan1d9bc9b2016-08-08 18:42:08 +000024
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].zName;
33}
34
drh6f82e852015-06-06 20:12:09 +000035/*
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 */
dan1d9bc9b2016-08-08 18:42:08 +000045 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 " */
drh6f82e852015-06-06 20:12:09 +000049 const char *zOp /* Name of the operator */
50){
dan1d9bc9b2016-08-08 18:42:08 +000051 int i;
drh6f82e852015-06-06 20:12:09 +000052
dan1d9bc9b2016-08-08 18:42:08 +000053 assert( nTerm>=1 );
drh0cdbe1a2018-05-09 13:46:26 +000054 if( bAnd ) sqlite3_str_append(pStr, " AND ", 5);
dan1d9bc9b2016-08-08 18:42:08 +000055
drh0cdbe1a2018-05-09 13:46:26 +000056 if( nTerm>1 ) sqlite3_str_append(pStr, "(", 1);
dan1d9bc9b2016-08-08 18:42:08 +000057 for(i=0; i<nTerm; i++){
drh0cdbe1a2018-05-09 13:46:26 +000058 if( i ) sqlite3_str_append(pStr, ",", 1);
59 sqlite3_str_appendall(pStr, explainIndexColumnName(pIdx, iTerm+i));
dan1d9bc9b2016-08-08 18:42:08 +000060 }
drh0cdbe1a2018-05-09 13:46:26 +000061 if( nTerm>1 ) sqlite3_str_append(pStr, ")", 1);
dan1d9bc9b2016-08-08 18:42:08 +000062
drh0cdbe1a2018-05-09 13:46:26 +000063 sqlite3_str_append(pStr, zOp, 1);
dan1d9bc9b2016-08-08 18:42:08 +000064
drh0cdbe1a2018-05-09 13:46:26 +000065 if( nTerm>1 ) sqlite3_str_append(pStr, "(", 1);
dan1d9bc9b2016-08-08 18:42:08 +000066 for(i=0; i<nTerm; i++){
drh0cdbe1a2018-05-09 13:46:26 +000067 if( i ) sqlite3_str_append(pStr, ",", 1);
68 sqlite3_str_append(pStr, "?", 1);
dan1d9bc9b2016-08-08 18:42:08 +000069 }
drh0cdbe1a2018-05-09 13:46:26 +000070 if( nTerm>1 ) sqlite3_str_append(pStr, ")", 1);
drhc7c46802015-08-27 20:33:38 +000071}
72
73/*
drh6f82e852015-06-06 20:12:09 +000074** 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*/
drh8faee872015-09-19 18:08:13 +000087static void explainIndexRange(StrAccum *pStr, WhereLoop *pLoop){
drh6f82e852015-06-06 20:12:09 +000088 Index *pIndex = pLoop->u.btree.pIndex;
89 u16 nEq = pLoop->u.btree.nEq;
90 u16 nSkip = pLoop->nSkip;
91 int i, j;
drh6f82e852015-06-06 20:12:09 +000092
93 if( nEq==0 && (pLoop->wsFlags&(WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))==0 ) return;
drh0cdbe1a2018-05-09 13:46:26 +000094 sqlite3_str_append(pStr, " (", 2);
drh6f82e852015-06-06 20:12:09 +000095 for(i=0; i<nEq; i++){
drhc7c46802015-08-27 20:33:38 +000096 const char *z = explainIndexColumnName(pIndex, i);
drh0cdbe1a2018-05-09 13:46:26 +000097 if( i ) sqlite3_str_append(pStr, " AND ", 5);
98 sqlite3_str_appendf(pStr, i>=nSkip ? "%s=?" : "ANY(%s)", z);
drh6f82e852015-06-06 20:12:09 +000099 }
100
101 j = i;
102 if( pLoop->wsFlags&WHERE_BTM_LIMIT ){
dan1d9bc9b2016-08-08 18:42:08 +0000103 explainAppendTerm(pStr, pIndex, pLoop->u.btree.nBtm, j, i, ">");
104 i = 1;
drh6f82e852015-06-06 20:12:09 +0000105 }
106 if( pLoop->wsFlags&WHERE_TOP_LIMIT ){
dan1d9bc9b2016-08-08 18:42:08 +0000107 explainAppendTerm(pStr, pIndex, pLoop->u.btree.nTop, j, i, "<");
drh6f82e852015-06-06 20:12:09 +0000108 }
drh0cdbe1a2018-05-09 13:46:26 +0000109 sqlite3_str_append(pStr, ")", 1);
drh6f82e852015-06-06 20:12:09 +0000110}
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 */
drh6f82e852015-06-06 20:12:09 +0000125 u16 wctrlFlags /* Flags passed to sqlite3WhereBegin() */
126){
127 int ret = 0;
128#if !defined(SQLITE_DEBUG) && !defined(SQLITE_ENABLE_STMT_SCANSTATUS)
drhef7231b2017-12-21 21:41:13 +0000129 if( sqlite3ParseToplevel(pParse)->explain==2 )
drh6f82e852015-06-06 20:12:09 +0000130#endif
131 {
132 struct SrcList_item *pItem = &pTabList->a[pLevel->iFrom];
133 Vdbe *v = pParse->pVdbe; /* VM being constructed */
134 sqlite3 *db = pParse->db; /* Database handle */
drh6f82e852015-06-06 20:12:09 +0000135 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;
drhce943bc2016-05-19 18:56:33 +0000144 if( (flags&WHERE_MULTI_OR) || (wctrlFlags&WHERE_OR_SUBCLAUSE) ) return 0;
drh6f82e852015-06-06 20:12:09 +0000145
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);
drh0cdbe1a2018-05-09 13:46:26 +0000151 sqlite3_str_appendall(&str, isSearch ? "SEARCH" : "SCAN");
drh6f82e852015-06-06 20:12:09 +0000152 if( pItem->pSelect ){
drhfef37762018-07-10 19:48:35 +0000153 sqlite3_str_appendf(&str, " SUBQUERY %u", pItem->pSelect->selId);
drh6f82e852015-06-06 20:12:09 +0000154 }else{
drh0cdbe1a2018-05-09 13:46:26 +0000155 sqlite3_str_appendf(&str, " TABLE %s", pItem->zName);
drh6f82e852015-06-06 20:12:09 +0000156 }
157
158 if( pItem->zAlias ){
drh0cdbe1a2018-05-09 13:46:26 +0000159 sqlite3_str_appendf(&str, " AS %s", pItem->zAlias);
drh6f82e852015-06-06 20:12:09 +0000160 }
161 if( (flags & (WHERE_IPK|WHERE_VIRTUALTABLE))==0 ){
162 const char *zFmt = 0;
163 Index *pIdx;
164
165 assert( pLoop->u.btree.pIndex!=0 );
166 pIdx = pLoop->u.btree.pIndex;
167 assert( !(flags&WHERE_AUTO_INDEX) || (flags&WHERE_IDX_ONLY) );
168 if( !HasRowid(pItem->pTab) && IsPrimaryKeyIndex(pIdx) ){
169 if( isSearch ){
170 zFmt = "PRIMARY KEY";
171 }
172 }else if( flags & WHERE_PARTIALIDX ){
173 zFmt = "AUTOMATIC PARTIAL COVERING INDEX";
174 }else if( flags & WHERE_AUTO_INDEX ){
175 zFmt = "AUTOMATIC COVERING INDEX";
176 }else if( flags & WHERE_IDX_ONLY ){
177 zFmt = "COVERING INDEX %s";
178 }else{
179 zFmt = "INDEX %s";
180 }
181 if( zFmt ){
drh0cdbe1a2018-05-09 13:46:26 +0000182 sqlite3_str_append(&str, " USING ", 7);
183 sqlite3_str_appendf(&str, zFmt, pIdx->zName);
drh8faee872015-09-19 18:08:13 +0000184 explainIndexRange(&str, pLoop);
drh6f82e852015-06-06 20:12:09 +0000185 }
186 }else if( (flags & WHERE_IPK)!=0 && (flags & WHERE_CONSTRAINT)!=0 ){
drhd37bea52015-09-02 15:37:50 +0000187 const char *zRangeOp;
drh6f82e852015-06-06 20:12:09 +0000188 if( flags&(WHERE_COLUMN_EQ|WHERE_COLUMN_IN) ){
drhd37bea52015-09-02 15:37:50 +0000189 zRangeOp = "=";
drh6f82e852015-06-06 20:12:09 +0000190 }else if( (flags&WHERE_BOTH_LIMIT)==WHERE_BOTH_LIMIT ){
drhd37bea52015-09-02 15:37:50 +0000191 zRangeOp = ">? AND rowid<";
drh6f82e852015-06-06 20:12:09 +0000192 }else if( flags&WHERE_BTM_LIMIT ){
drhd37bea52015-09-02 15:37:50 +0000193 zRangeOp = ">";
drh6f82e852015-06-06 20:12:09 +0000194 }else{
195 assert( flags&WHERE_TOP_LIMIT);
drhd37bea52015-09-02 15:37:50 +0000196 zRangeOp = "<";
drh6f82e852015-06-06 20:12:09 +0000197 }
drh0cdbe1a2018-05-09 13:46:26 +0000198 sqlite3_str_appendf(&str,
199 " USING INTEGER PRIMARY KEY (rowid%s?)",zRangeOp);
drh6f82e852015-06-06 20:12:09 +0000200 }
201#ifndef SQLITE_OMIT_VIRTUALTABLE
202 else if( (flags & WHERE_VIRTUALTABLE)!=0 ){
drh0cdbe1a2018-05-09 13:46:26 +0000203 sqlite3_str_appendf(&str, " VIRTUAL TABLE INDEX %d:%s",
drh6f82e852015-06-06 20:12:09 +0000204 pLoop->u.vtab.idxNum, pLoop->u.vtab.idxStr);
205 }
206#endif
207#ifdef SQLITE_EXPLAIN_ESTIMATED_ROWS
208 if( pLoop->nOut>=10 ){
drh0cdbe1a2018-05-09 13:46:26 +0000209 sqlite3_str_appendf(&str, " (~%llu rows)",
210 sqlite3LogEstToInt(pLoop->nOut));
drh6f82e852015-06-06 20:12:09 +0000211 }else{
drh0cdbe1a2018-05-09 13:46:26 +0000212 sqlite3_str_append(&str, " (~1 row)", 9);
drh6f82e852015-06-06 20:12:09 +0000213 }
214#endif
215 zMsg = sqlite3StrAccumFinish(&str);
drhbd462bc2018-12-24 20:21:06 +0000216 sqlite3ExplainBreakpoint("",zMsg);
drhe2ca99c2018-05-02 00:33:43 +0000217 ret = sqlite3VdbeAddOp4(v, OP_Explain, sqlite3VdbeCurrentAddr(v),
218 pParse->addrExplain, 0, zMsg,P4_DYNAMIC);
drh6f82e852015-06-06 20:12:09 +0000219 }
220 return ret;
221}
222#endif /* SQLITE_OMIT_EXPLAIN */
223
224#ifdef SQLITE_ENABLE_STMT_SCANSTATUS
225/*
226** Configure the VM passed as the first argument with an
227** sqlite3_stmt_scanstatus() entry corresponding to the scan used to
228** implement level pLvl. Argument pSrclist is a pointer to the FROM
229** clause that the scan reads data from.
230**
231** If argument addrExplain is not 0, it must be the address of an
232** OP_Explain instruction that describes the same loop.
233*/
234void sqlite3WhereAddScanStatus(
235 Vdbe *v, /* Vdbe to add scanstatus entry to */
236 SrcList *pSrclist, /* FROM clause pLvl reads data from */
237 WhereLevel *pLvl, /* Level to add scanstatus() entry for */
238 int addrExplain /* Address of OP_Explain (or 0) */
239){
240 const char *zObj = 0;
241 WhereLoop *pLoop = pLvl->pWLoop;
242 if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 && pLoop->u.btree.pIndex!=0 ){
243 zObj = pLoop->u.btree.pIndex->zName;
244 }else{
245 zObj = pSrclist->a[pLvl->iFrom].zName;
246 }
247 sqlite3VdbeScanStatus(
248 v, addrExplain, pLvl->addrBody, pLvl->addrVisit, pLoop->nOut, zObj
249 );
250}
251#endif
252
253
254/*
255** Disable a term in the WHERE clause. Except, do not disable the term
256** if it controls a LEFT OUTER JOIN and it did not originate in the ON
257** or USING clause of that join.
258**
259** Consider the term t2.z='ok' in the following queries:
260**
261** (1) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok'
262** (2) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok'
263** (3) SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok'
264**
265** The t2.z='ok' is disabled in the in (2) because it originates
266** in the ON clause. The term is disabled in (3) because it is not part
267** of a LEFT OUTER JOIN. In (1), the term is not disabled.
268**
269** Disabling a term causes that term to not be tested in the inner loop
270** of the join. Disabling is an optimization. When terms are satisfied
271** by indices, we disable them to prevent redundant tests in the inner
272** loop. We would get the correct results if nothing were ever disabled,
273** but joins might run a little slower. The trick is to disable as much
274** as we can without disabling too much. If we disabled in (1), we'd get
275** the wrong answer. See ticket #813.
276**
277** If all the children of a term are disabled, then that term is also
278** automatically disabled. In this way, terms get disabled if derived
279** virtual terms are tested first. For example:
280**
281** x GLOB 'abc*' AND x>='abc' AND x<'acd'
282** \___________/ \______/ \_____/
283** parent child1 child2
284**
285** Only the parent term was in the original WHERE clause. The child1
286** and child2 terms were added by the LIKE optimization. If both of
287** the virtual child terms are valid, then testing of the parent can be
288** skipped.
289**
290** Usually the parent term is marked as TERM_CODED. But if the parent
291** term was originally TERM_LIKE, then the parent gets TERM_LIKECOND instead.
292** The TERM_LIKECOND marking indicates that the term should be coded inside
293** a conditional such that is only evaluated on the second pass of a
294** LIKE-optimization loop, when scanning BLOBs instead of strings.
295*/
296static void disableTerm(WhereLevel *pLevel, WhereTerm *pTerm){
297 int nLoop = 0;
drh9d9c41e2017-10-31 03:40:15 +0000298 assert( pTerm!=0 );
299 while( (pTerm->wtFlags & TERM_CODED)==0
drh6f82e852015-06-06 20:12:09 +0000300 && (pLevel->iLeftJoin==0 || ExprHasProperty(pTerm->pExpr, EP_FromJoin))
301 && (pLevel->notReady & pTerm->prereqAll)==0
302 ){
303 if( nLoop && (pTerm->wtFlags & TERM_LIKE)!=0 ){
304 pTerm->wtFlags |= TERM_LIKECOND;
305 }else{
306 pTerm->wtFlags |= TERM_CODED;
307 }
308 if( pTerm->iParent<0 ) break;
309 pTerm = &pTerm->pWC->a[pTerm->iParent];
drh9d9c41e2017-10-31 03:40:15 +0000310 assert( pTerm!=0 );
drh6f82e852015-06-06 20:12:09 +0000311 pTerm->nChild--;
312 if( pTerm->nChild!=0 ) break;
313 nLoop++;
314 }
315}
316
317/*
318** Code an OP_Affinity opcode to apply the column affinity string zAff
319** to the n registers starting at base.
320**
drh96fb16e2019-08-06 14:37:24 +0000321** As an optimization, SQLITE_AFF_BLOB and SQLITE_AFF_NONE entries (which
322** are no-ops) at the beginning and end of zAff are ignored. If all entries
323** in zAff are SQLITE_AFF_BLOB or SQLITE_AFF_NONE, then no code gets generated.
drh6f82e852015-06-06 20:12:09 +0000324**
325** This routine makes its own copy of zAff so that the caller is free
326** to modify zAff after this routine returns.
327*/
328static void codeApplyAffinity(Parse *pParse, int base, int n, char *zAff){
329 Vdbe *v = pParse->pVdbe;
330 if( zAff==0 ){
331 assert( pParse->db->mallocFailed );
332 return;
333 }
334 assert( v!=0 );
335
drh96fb16e2019-08-06 14:37:24 +0000336 /* Adjust base and n to skip over SQLITE_AFF_BLOB and SQLITE_AFF_NONE
337 ** entries at the beginning and end of the affinity string.
drh6f82e852015-06-06 20:12:09 +0000338 */
drh96fb16e2019-08-06 14:37:24 +0000339 assert( SQLITE_AFF_NONE<SQLITE_AFF_BLOB );
340 while( n>0 && zAff[0]<=SQLITE_AFF_BLOB ){
drh6f82e852015-06-06 20:12:09 +0000341 n--;
342 base++;
343 zAff++;
344 }
drh96fb16e2019-08-06 14:37:24 +0000345 while( n>1 && zAff[n-1]<=SQLITE_AFF_BLOB ){
drh6f82e852015-06-06 20:12:09 +0000346 n--;
347 }
348
349 /* Code the OP_Affinity opcode if there is anything left to do. */
350 if( n>0 ){
drh9b34abe2016-01-16 15:12:35 +0000351 sqlite3VdbeAddOp4(v, OP_Affinity, base, n, 0, zAff, n);
drh6f82e852015-06-06 20:12:09 +0000352 }
353}
354
danb7ca2172016-08-26 17:54:46 +0000355/*
356** Expression pRight, which is the RHS of a comparison operation, is
357** either a vector of n elements or, if n==1, a scalar expression.
358** Before the comparison operation, affinity zAff is to be applied
359** to the pRight values. This function modifies characters within the
360** affinity string to SQLITE_AFF_BLOB if either:
361**
362** * the comparison will be performed with no affinity, or
363** * the affinity change in zAff is guaranteed not to change the value.
364*/
365static void updateRangeAffinityStr(
danb7ca2172016-08-26 17:54:46 +0000366 Expr *pRight, /* RHS of comparison */
367 int n, /* Number of vector elements in comparison */
368 char *zAff /* Affinity string to modify */
369){
370 int i;
371 for(i=0; i<n; i++){
372 Expr *p = sqlite3VectorFieldSubexpr(pRight, i);
373 if( sqlite3CompareAffinity(p, zAff[i])==SQLITE_AFF_BLOB
374 || sqlite3ExprNeedsNoAffinityChange(p, zAff[i])
375 ){
376 zAff[i] = SQLITE_AFF_BLOB;
377 }
378 }
379}
drh6f82e852015-06-06 20:12:09 +0000380
drh24102432017-11-17 21:01:04 +0000381
382/*
383** pX is an expression of the form: (vector) IN (SELECT ...)
384** In other words, it is a vector IN operator with a SELECT clause on the
385** LHS. But not all terms in the vector are indexable and the terms might
386** not be in the correct order for indexing.
drh9b1ecb62017-11-17 17:32:40 +0000387**
drh24102432017-11-17 21:01:04 +0000388** This routine makes a copy of the input pX expression and then adjusts
389** the vector on the LHS with corresponding changes to the SELECT so that
390** the vector contains only index terms and those terms are in the correct
391** order. The modified IN expression is returned. The caller is responsible
392** for deleting the returned expression.
393**
394** Example:
395**
396** CREATE TABLE t1(a,b,c,d,e,f);
397** CREATE INDEX t1x1 ON t1(e,c);
398** SELECT * FROM t1 WHERE (a,b,c,d,e) IN (SELECT v,w,x,y,z FROM t2)
399** \_______________________________________/
400** The pX expression
401**
402** Since only columns e and c can be used with the index, in that order,
403** the modified IN expression that is returned will be:
404**
405** (e,c) IN (SELECT z,x FROM t2)
406**
407** The reduced pX is different from the original (obviously) and thus is
408** only used for indexing, to improve performance. The original unaltered
409** IN expression must also be run on each output row for correctness.
drh9b1ecb62017-11-17 17:32:40 +0000410*/
drh24102432017-11-17 21:01:04 +0000411static Expr *removeUnindexableInClauseTerms(
412 Parse *pParse, /* The parsing context */
413 int iEq, /* Look at loop terms starting here */
414 WhereLoop *pLoop, /* The current loop */
415 Expr *pX /* The IN expression to be reduced */
416){
417 sqlite3 *db = pParse->db;
dan69843342019-12-22 17:32:25 +0000418 Expr *pNew;
dan69843342019-12-22 17:32:25 +0000419 pNew = sqlite3ExprDup(db, pX, 0);
drh24102432017-11-17 21:01:04 +0000420 if( db->mallocFailed==0 ){
421 ExprList *pOrigRhs = pNew->x.pSelect->pEList; /* Original unmodified RHS */
422 ExprList *pOrigLhs = pNew->pLeft->x.pList; /* Original unmodified LHS */
423 ExprList *pRhs = 0; /* New RHS after modifications */
424 ExprList *pLhs = 0; /* New LHS after mods */
425 int i; /* Loop counter */
426 Select *pSelect; /* Pointer to the SELECT on the RHS */
427
428 for(i=iEq; i<pLoop->nLTerm; i++){
429 if( pLoop->aLTerm[i]->pExpr==pX ){
430 int iField = pLoop->aLTerm[i]->iField - 1;
drhc6e519f2018-11-03 13:11:24 +0000431 if( pOrigRhs->a[iField].pExpr==0 ) continue; /* Duplicate PK column */
drh24102432017-11-17 21:01:04 +0000432 pRhs = sqlite3ExprListAppend(pParse, pRhs, pOrigRhs->a[iField].pExpr);
433 pOrigRhs->a[iField].pExpr = 0;
434 assert( pOrigLhs->a[iField].pExpr!=0 );
435 pLhs = sqlite3ExprListAppend(pParse, pLhs, pOrigLhs->a[iField].pExpr);
436 pOrigLhs->a[iField].pExpr = 0;
437 }
drh9b1ecb62017-11-17 17:32:40 +0000438 }
drh24102432017-11-17 21:01:04 +0000439 sqlite3ExprListDelete(db, pOrigRhs);
440 sqlite3ExprListDelete(db, pOrigLhs);
441 pNew->pLeft->x.pList = pLhs;
442 pNew->x.pSelect->pEList = pRhs;
443 if( pLhs && pLhs->nExpr==1 ){
444 /* Take care here not to generate a TK_VECTOR containing only a
445 ** single value. Since the parser never creates such a vector, some
446 ** of the subroutines do not handle this case. */
447 Expr *p = pLhs->a[0].pExpr;
448 pLhs->a[0].pExpr = 0;
449 sqlite3ExprDelete(db, pNew->pLeft);
450 pNew->pLeft = p;
451 }
452 pSelect = pNew->x.pSelect;
453 if( pSelect->pOrderBy ){
454 /* If the SELECT statement has an ORDER BY clause, zero the
455 ** iOrderByCol variables. These are set to non-zero when an
456 ** ORDER BY term exactly matches one of the terms of the
457 ** result-set. Since the result-set of the SELECT statement may
458 ** have been modified or reordered, these variables are no longer
459 ** set correctly. Since setting them is just an optimization,
460 ** it's easiest just to zero them here. */
461 ExprList *pOrderBy = pSelect->pOrderBy;
462 for(i=0; i<pOrderBy->nExpr; i++){
463 pOrderBy->a[i].u.x.iOrderByCol = 0;
464 }
465 }
466
467#if 0
468 printf("For indexing, change the IN expr:\n");
469 sqlite3TreeViewExpr(0, pX, 0);
470 printf("Into:\n");
471 sqlite3TreeViewExpr(0, pNew, 0);
472#endif
drh9b1ecb62017-11-17 17:32:40 +0000473 }
drh24102432017-11-17 21:01:04 +0000474 return pNew;
drh9b1ecb62017-11-17 17:32:40 +0000475}
drh9b1ecb62017-11-17 17:32:40 +0000476
477
drh6f82e852015-06-06 20:12:09 +0000478/*
479** Generate code for a single equality term of the WHERE clause. An equality
480** term can be either X=expr or X IN (...). pTerm is the term to be
481** coded.
482**
drh099a0f52016-09-06 15:25:53 +0000483** The current value for the constraint is left in a register, the index
484** of which is returned. An attempt is made store the result in iTarget but
485** this is only guaranteed for TK_ISNULL and TK_IN constraints. If the
486** constraint is a TK_EQ or TK_IS, then the current value might be left in
487** some other register and it is the caller's responsibility to compensate.
drh6f82e852015-06-06 20:12:09 +0000488**
drh4602b8e2016-08-19 18:28:00 +0000489** For a constraint of the form X=expr, the expression is evaluated in
490** straight-line code. For constraints of the form X IN (...)
drh6f82e852015-06-06 20:12:09 +0000491** this routine sets up a loop that will iterate over all values of X.
492*/
493static int codeEqualityTerm(
494 Parse *pParse, /* The parsing context */
495 WhereTerm *pTerm, /* The term of the WHERE clause to be coded */
496 WhereLevel *pLevel, /* The level of the FROM clause we are working on */
497 int iEq, /* Index of the equality term within this level */
498 int bRev, /* True for reverse-order IN operations */
499 int iTarget /* Attempt to leave results in this register */
500){
501 Expr *pX = pTerm->pExpr;
502 Vdbe *v = pParse->pVdbe;
503 int iReg; /* Register holding results */
504
dan8da209b2016-07-26 18:06:08 +0000505 assert( pLevel->pWLoop->aLTerm[iEq]==pTerm );
drh6f82e852015-06-06 20:12:09 +0000506 assert( iTarget>0 );
507 if( pX->op==TK_EQ || pX->op==TK_IS ){
drhfc7f27b2016-08-20 00:07:01 +0000508 iReg = sqlite3ExprCodeTarget(pParse, pX->pRight, iTarget);
drh6f82e852015-06-06 20:12:09 +0000509 }else if( pX->op==TK_ISNULL ){
510 iReg = iTarget;
511 sqlite3VdbeAddOp2(v, OP_Null, 0, iReg);
512#ifndef SQLITE_OMIT_SUBQUERY
513 }else{
drhac6b47d2016-08-24 00:51:48 +0000514 int eType = IN_INDEX_NOOP;
drh6f82e852015-06-06 20:12:09 +0000515 int iTab;
516 struct InLoop *pIn;
517 WhereLoop *pLoop = pLevel->pWLoop;
dan8da209b2016-07-26 18:06:08 +0000518 int i;
519 int nEq = 0;
520 int *aiMap = 0;
drh6f82e852015-06-06 20:12:09 +0000521
522 if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0
523 && pLoop->u.btree.pIndex!=0
524 && pLoop->u.btree.pIndex->aSortOrder[iEq]
525 ){
526 testcase( iEq==0 );
527 testcase( bRev );
528 bRev = !bRev;
529 }
530 assert( pX->op==TK_IN );
531 iReg = iTarget;
dan8da209b2016-07-26 18:06:08 +0000532
533 for(i=0; i<iEq; i++){
534 if( pLoop->aLTerm[i] && pLoop->aLTerm[i]->pExpr==pX ){
535 disableTerm(pLevel, pTerm);
536 return iTarget;
537 }
538 }
539 for(i=iEq;i<pLoop->nLTerm; i++){
drh24102432017-11-17 21:01:04 +0000540 assert( pLoop->aLTerm[i]!=0 );
541 if( pLoop->aLTerm[i]->pExpr==pX ) nEq++;
dan8da209b2016-07-26 18:06:08 +0000542 }
543
drh2c041312018-12-24 02:34:49 +0000544 iTab = 0;
dan8da209b2016-07-26 18:06:08 +0000545 if( (pX->flags & EP_xIsSelect)==0 || pX->x.pSelect->pEList->nExpr==1 ){
drh2c041312018-12-24 02:34:49 +0000546 eType = sqlite3FindInIndex(pParse, pX, IN_INDEX_LOOP, 0, 0, &iTab);
dan8da209b2016-07-26 18:06:08 +0000547 }else{
548 sqlite3 *db = pParse->db;
drh24102432017-11-17 21:01:04 +0000549 pX = removeUnindexableInClauseTerms(pParse, iEq, pLoop, pX);
drh9b1ecb62017-11-17 17:32:40 +0000550
drhac6b47d2016-08-24 00:51:48 +0000551 if( !db->mallocFailed ){
drh24102432017-11-17 21:01:04 +0000552 aiMap = (int*)sqlite3DbMallocZero(pParse->db, sizeof(int)*nEq);
drh2c041312018-12-24 02:34:49 +0000553 eType = sqlite3FindInIndex(pParse, pX, IN_INDEX_LOOP, 0, aiMap, &iTab);
554 pTerm->pExpr->iTable = iTab;
drhac6b47d2016-08-24 00:51:48 +0000555 }
drh24102432017-11-17 21:01:04 +0000556 sqlite3ExprDelete(db, pX);
557 pX = pTerm->pExpr;
dan8da209b2016-07-26 18:06:08 +0000558 }
559
drh6f82e852015-06-06 20:12:09 +0000560 if( eType==IN_INDEX_INDEX_DESC ){
561 testcase( bRev );
562 bRev = !bRev;
563 }
drh6f82e852015-06-06 20:12:09 +0000564 sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iTab, 0);
565 VdbeCoverageIf(v, bRev);
566 VdbeCoverageIf(v, !bRev);
567 assert( (pLoop->wsFlags & WHERE_MULTI_OR)==0 );
dan8da209b2016-07-26 18:06:08 +0000568
drh6f82e852015-06-06 20:12:09 +0000569 pLoop->wsFlags |= WHERE_IN_ABLE;
570 if( pLevel->u.in.nIn==0 ){
drhec4ccdb2018-12-29 02:26:59 +0000571 pLevel->addrNxt = sqlite3VdbeMakeLabel(pParse);
drh6f82e852015-06-06 20:12:09 +0000572 }
dan8da209b2016-07-26 18:06:08 +0000573
574 i = pLevel->u.in.nIn;
575 pLevel->u.in.nIn += nEq;
drh6f82e852015-06-06 20:12:09 +0000576 pLevel->u.in.aInLoop =
577 sqlite3DbReallocOrFree(pParse->db, pLevel->u.in.aInLoop,
578 sizeof(pLevel->u.in.aInLoop[0])*pLevel->u.in.nIn);
579 pIn = pLevel->u.in.aInLoop;
580 if( pIn ){
dan8da209b2016-07-26 18:06:08 +0000581 int iMap = 0; /* Index in aiMap[] */
582 pIn += i;
dan7887d7f2016-08-24 12:22:17 +0000583 for(i=iEq;i<pLoop->nLTerm; i++){
dan8da209b2016-07-26 18:06:08 +0000584 if( pLoop->aLTerm[i]->pExpr==pX ){
danedc35372016-09-16 16:30:57 +0000585 int iOut = iReg + i - iEq;
dan8da209b2016-07-26 18:06:08 +0000586 if( eType==IN_INDEX_ROWID ){
danedc35372016-09-16 16:30:57 +0000587 pIn->addrInTop = sqlite3VdbeAddOp2(v, OP_Rowid, iTab, iOut);
dan8da209b2016-07-26 18:06:08 +0000588 }else{
589 int iCol = aiMap ? aiMap[iMap++] : 0;
dan8da209b2016-07-26 18:06:08 +0000590 pIn->addrInTop = sqlite3VdbeAddOp3(v,OP_Column,iTab, iCol, iOut);
591 }
drh03181c82016-08-18 19:04:57 +0000592 sqlite3VdbeAddOp1(v, OP_IsNull, iOut); VdbeCoverage(v);
dan8da209b2016-07-26 18:06:08 +0000593 if( i==iEq ){
594 pIn->iCur = iTab;
drhf1949b62018-06-07 17:32:59 +0000595 pIn->eEndLoopOp = bRev ? OP_Prev : OP_Next;
drh056f5392018-06-07 16:07:00 +0000596 if( iEq>0 && (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 ){
drh86d0ea72018-06-05 15:16:25 +0000597 pIn->iBase = iReg - i;
598 pIn->nPrefix = i;
drhf7b0a5f2018-06-07 14:59:22 +0000599 pLoop->wsFlags |= WHERE_IN_EARLYOUT;
drh86d0ea72018-06-05 15:16:25 +0000600 }else{
601 pIn->nPrefix = 0;
602 }
dan8da209b2016-07-26 18:06:08 +0000603 }else{
604 pIn->eEndLoopOp = OP_Noop;
605 }
dan7887d7f2016-08-24 12:22:17 +0000606 pIn++;
dan8da209b2016-07-26 18:06:08 +0000607 }
drh6f82e852015-06-06 20:12:09 +0000608 }
drh6f82e852015-06-06 20:12:09 +0000609 }else{
610 pLevel->u.in.nIn = 0;
611 }
dan8da209b2016-07-26 18:06:08 +0000612 sqlite3DbFree(pParse->db, aiMap);
drh6f82e852015-06-06 20:12:09 +0000613#endif
614 }
615 disableTerm(pLevel, pTerm);
616 return iReg;
617}
618
619/*
620** Generate code that will evaluate all == and IN constraints for an
621** index scan.
622**
623** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c).
624** Suppose the WHERE clause is this: a==5 AND b IN (1,2,3) AND c>5 AND c<10
625** The index has as many as three equality constraints, but in this
626** example, the third "c" value is an inequality. So only two
627** constraints are coded. This routine will generate code to evaluate
628** a==5 and b IN (1,2,3). The current values for a and b will be stored
629** in consecutive registers and the index of the first register is returned.
630**
631** In the example above nEq==2. But this subroutine works for any value
632** of nEq including 0. If nEq==0, this routine is nearly a no-op.
633** The only thing it does is allocate the pLevel->iMem memory cell and
634** compute the affinity string.
635**
636** The nExtraReg parameter is 0 or 1. It is 0 if all WHERE clause constraints
637** are == or IN and are covered by the nEq. nExtraReg is 1 if there is
638** an inequality constraint (such as the "c>=5 AND c<10" in the example) that
639** occurs after the nEq quality constraints.
640**
641** This routine allocates a range of nEq+nExtraReg memory cells and returns
642** the index of the first memory cell in that range. The code that
643** calls this routine will use that memory range to store keys for
644** start and termination conditions of the loop.
645** key value of the loop. If one or more IN operators appear, then
646** this routine allocates an additional nEq memory cells for internal
647** use.
648**
649** Before returning, *pzAff is set to point to a buffer containing a
650** copy of the column affinity string of the index allocated using
651** sqlite3DbMalloc(). Except, entries in the copy of the string associated
652** with equality constraints that use BLOB or NONE affinity are set to
653** SQLITE_AFF_BLOB. This is to deal with SQL such as the following:
654**
655** CREATE TABLE t1(a TEXT PRIMARY KEY, b);
656** SELECT ... FROM t1 AS t2, t1 WHERE t1.a = t2.b;
657**
658** In the example above, the index on t1(a) has TEXT affinity. But since
659** the right hand side of the equality constraint (t2.b) has BLOB/NONE affinity,
660** no conversion should be attempted before using a t2.b value as part of
661** a key to search the index. Hence the first byte in the returned affinity
662** string in this example would be set to SQLITE_AFF_BLOB.
663*/
664static int codeAllEqualityTerms(
665 Parse *pParse, /* Parsing context */
666 WhereLevel *pLevel, /* Which nested loop of the FROM we are coding */
667 int bRev, /* Reverse the order of IN operators */
668 int nExtraReg, /* Number of extra registers to allocate */
669 char **pzAff /* OUT: Set to point to affinity string */
670){
671 u16 nEq; /* The number of == or IN constraints to code */
672 u16 nSkip; /* Number of left-most columns to skip */
673 Vdbe *v = pParse->pVdbe; /* The vm under construction */
674 Index *pIdx; /* The index being used for this loop */
675 WhereTerm *pTerm; /* A single constraint term */
676 WhereLoop *pLoop; /* The WhereLoop object */
677 int j; /* Loop counter */
678 int regBase; /* Base register */
679 int nReg; /* Number of registers to allocate */
680 char *zAff; /* Affinity string to return */
681
682 /* This module is only called on query plans that use an index. */
683 pLoop = pLevel->pWLoop;
684 assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 );
685 nEq = pLoop->u.btree.nEq;
686 nSkip = pLoop->nSkip;
687 pIdx = pLoop->u.btree.pIndex;
688 assert( pIdx!=0 );
689
690 /* Figure out how many memory cells we will need then allocate them.
691 */
692 regBase = pParse->nMem + 1;
693 nReg = pLoop->u.btree.nEq + nExtraReg;
694 pParse->nMem += nReg;
695
drhe9107692015-08-25 19:20:04 +0000696 zAff = sqlite3DbStrDup(pParse->db,sqlite3IndexAffinityStr(pParse->db,pIdx));
drh4df86af2016-02-04 11:48:00 +0000697 assert( zAff!=0 || pParse->db->mallocFailed );
drh6f82e852015-06-06 20:12:09 +0000698
699 if( nSkip ){
700 int iIdxCur = pLevel->iIdxCur;
701 sqlite3VdbeAddOp1(v, (bRev?OP_Last:OP_Rewind), iIdxCur);
702 VdbeCoverageIf(v, bRev==0);
703 VdbeCoverageIf(v, bRev!=0);
704 VdbeComment((v, "begin skip-scan on %s", pIdx->zName));
705 j = sqlite3VdbeAddOp0(v, OP_Goto);
706 pLevel->addrSkip = sqlite3VdbeAddOp4Int(v, (bRev?OP_SeekLT:OP_SeekGT),
707 iIdxCur, 0, regBase, nSkip);
708 VdbeCoverageIf(v, bRev==0);
709 VdbeCoverageIf(v, bRev!=0);
710 sqlite3VdbeJumpHere(v, j);
711 for(j=0; j<nSkip; j++){
712 sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, j, regBase+j);
drh4b92f982015-09-29 17:20:14 +0000713 testcase( pIdx->aiColumn[j]==XN_EXPR );
drhe63e8a62015-09-18 18:09:28 +0000714 VdbeComment((v, "%s", explainIndexColumnName(pIdx, j)));
drh6f82e852015-06-06 20:12:09 +0000715 }
716 }
717
718 /* Evaluate the equality constraints
719 */
720 assert( zAff==0 || (int)strlen(zAff)>=nEq );
721 for(j=nSkip; j<nEq; j++){
722 int r1;
723 pTerm = pLoop->aLTerm[j];
724 assert( pTerm!=0 );
725 /* The following testcase is true for indices with redundant columns.
726 ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */
727 testcase( (pTerm->wtFlags & TERM_CODED)!=0 );
728 testcase( pTerm->wtFlags & TERM_VIRTUAL );
729 r1 = codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, regBase+j);
730 if( r1!=regBase+j ){
731 if( nReg==1 ){
732 sqlite3ReleaseTempReg(pParse, regBase);
733 regBase = r1;
734 }else{
735 sqlite3VdbeAddOp2(v, OP_SCopy, r1, regBase+j);
736 }
737 }
drhc097e122016-09-07 13:30:40 +0000738 if( pTerm->eOperator & WO_IN ){
739 if( pTerm->pExpr->flags & EP_xIsSelect ){
740 /* No affinity ever needs to be (or should be) applied to a value
741 ** from the RHS of an "? IN (SELECT ...)" expression. The
742 ** sqlite3FindInIndex() routine has already ensured that the
743 ** affinity of the comparison has been applied to the value. */
744 if( zAff ) zAff[j] = SQLITE_AFF_BLOB;
745 }
746 }else if( (pTerm->eOperator & WO_ISNULL)==0 ){
747 Expr *pRight = pTerm->pExpr->pRight;
748 if( (pTerm->wtFlags & TERM_IS)==0 && sqlite3ExprCanBeNull(pRight) ){
749 sqlite3VdbeAddOp2(v, OP_IsNull, regBase+j, pLevel->addrBrk);
750 VdbeCoverage(v);
751 }
752 if( zAff ){
753 if( sqlite3CompareAffinity(pRight, zAff[j])==SQLITE_AFF_BLOB ){
754 zAff[j] = SQLITE_AFF_BLOB;
dan27189602016-09-03 15:31:20 +0000755 }
drhc097e122016-09-07 13:30:40 +0000756 if( sqlite3ExprNeedsNoAffinityChange(pRight, zAff[j]) ){
757 zAff[j] = SQLITE_AFF_BLOB;
drh6f82e852015-06-06 20:12:09 +0000758 }
759 }
760 }
761 }
762 *pzAff = zAff;
763 return regBase;
764}
765
drh41d2e662015-12-01 21:23:07 +0000766#ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
drh6f82e852015-06-06 20:12:09 +0000767/*
drh44aebff2016-05-02 10:25:42 +0000768** If the most recently coded instruction is a constant range constraint
769** (a string literal) that originated from the LIKE optimization, then
770** set P3 and P5 on the OP_String opcode so that the string will be cast
771** to a BLOB at appropriate times.
drh6f82e852015-06-06 20:12:09 +0000772**
773** The LIKE optimization trys to evaluate "x LIKE 'abc%'" as a range
774** expression: "x>='ABC' AND x<'abd'". But this requires that the range
775** scan loop run twice, once for strings and a second time for BLOBs.
776** The OP_String opcodes on the second pass convert the upper and lower
mistachkine234cfd2016-07-10 19:35:10 +0000777** bound string constants to blobs. This routine makes the necessary changes
drh6f82e852015-06-06 20:12:09 +0000778** to the OP_String opcodes for that to happen.
drh41d2e662015-12-01 21:23:07 +0000779**
780** Except, of course, if SQLITE_LIKE_DOESNT_MATCH_BLOBS is defined, then
781** only the one pass through the string space is required, so this routine
782** becomes a no-op.
drh6f82e852015-06-06 20:12:09 +0000783*/
784static void whereLikeOptimizationStringFixup(
785 Vdbe *v, /* prepared statement under construction */
786 WhereLevel *pLevel, /* The loop that contains the LIKE operator */
787 WhereTerm *pTerm /* The upper or lower bound just coded */
788){
789 if( pTerm->wtFlags & TERM_LIKEOPT ){
790 VdbeOp *pOp;
791 assert( pLevel->iLikeRepCntr>0 );
792 pOp = sqlite3VdbeGetOp(v, -1);
793 assert( pOp!=0 );
794 assert( pOp->opcode==OP_String8
795 || pTerm->pWC->pWInfo->pParse->db->mallocFailed );
drh44aebff2016-05-02 10:25:42 +0000796 pOp->p3 = (int)(pLevel->iLikeRepCntr>>1); /* Register holding counter */
797 pOp->p5 = (u8)(pLevel->iLikeRepCntr&1); /* ASC or DESC */
drh6f82e852015-06-06 20:12:09 +0000798 }
799}
drh41d2e662015-12-01 21:23:07 +0000800#else
801# define whereLikeOptimizationStringFixup(A,B,C)
802#endif
drh6f82e852015-06-06 20:12:09 +0000803
drhbec24762015-08-13 20:07:13 +0000804#ifdef SQLITE_ENABLE_CURSOR_HINTS
drh2f2b0272015-08-14 18:50:04 +0000805/*
806** Information is passed from codeCursorHint() down to individual nodes of
807** the expression tree (by sqlite3WalkExpr()) using an instance of this
808** structure.
809*/
810struct CCurHint {
811 int iTabCur; /* Cursor for the main table */
812 int iIdxCur; /* Cursor for the index, if pIdx!=0. Unused otherwise */
813 Index *pIdx; /* The index used to access the table */
814};
815
816/*
817** This function is called for every node of an expression that is a candidate
818** for a cursor hint on an index cursor. For TK_COLUMN nodes that reference
819** the table CCurHint.iTabCur, verify that the same column can be
820** accessed through the index. If it cannot, then set pWalker->eCode to 1.
821*/
822static int codeCursorHintCheckExpr(Walker *pWalker, Expr *pExpr){
823 struct CCurHint *pHint = pWalker->u.pCCurHint;
824 assert( pHint->pIdx!=0 );
825 if( pExpr->op==TK_COLUMN
826 && pExpr->iTable==pHint->iTabCur
drhb9bcf7c2019-10-19 13:29:10 +0000827 && sqlite3TableColumnToIndex(pHint->pIdx, pExpr->iColumn)<0
drh2f2b0272015-08-14 18:50:04 +0000828 ){
829 pWalker->eCode = 1;
830 }
831 return WRC_Continue;
832}
833
dane6912fd2016-06-17 19:27:13 +0000834/*
835** Test whether or not expression pExpr, which was part of a WHERE clause,
836** should be included in the cursor-hint for a table that is on the rhs
837** of a LEFT JOIN. Set Walker.eCode to non-zero before returning if the
838** expression is not suitable.
839**
840** An expression is unsuitable if it might evaluate to non NULL even if
841** a TK_COLUMN node that does affect the value of the expression is set
842** to NULL. For example:
843**
844** col IS NULL
845** col IS NOT NULL
846** coalesce(col, 1)
847** CASE WHEN col THEN 0 ELSE 1 END
848*/
849static int codeCursorHintIsOrFunction(Walker *pWalker, Expr *pExpr){
dan2b693d62016-06-20 17:22:06 +0000850 if( pExpr->op==TK_IS
dane6912fd2016-06-17 19:27:13 +0000851 || pExpr->op==TK_ISNULL || pExpr->op==TK_ISNOT
852 || pExpr->op==TK_NOTNULL || pExpr->op==TK_CASE
853 ){
854 pWalker->eCode = 1;
dan2b693d62016-06-20 17:22:06 +0000855 }else if( pExpr->op==TK_FUNCTION ){
856 int d1;
drh1d42ea72017-07-27 20:24:29 +0000857 char d2[4];
dan2b693d62016-06-20 17:22:06 +0000858 if( 0==sqlite3IsLikeFunction(pWalker->pParse->db, pExpr, &d1, d2) ){
859 pWalker->eCode = 1;
860 }
dane6912fd2016-06-17 19:27:13 +0000861 }
dan2b693d62016-06-20 17:22:06 +0000862
dane6912fd2016-06-17 19:27:13 +0000863 return WRC_Continue;
864}
865
drhbec24762015-08-13 20:07:13 +0000866
867/*
868** This function is called on every node of an expression tree used as an
869** argument to the OP_CursorHint instruction. If the node is a TK_COLUMN
drh2f2b0272015-08-14 18:50:04 +0000870** that accesses any table other than the one identified by
871** CCurHint.iTabCur, then do the following:
drhbec24762015-08-13 20:07:13 +0000872**
873** 1) allocate a register and code an OP_Column instruction to read
874** the specified column into the new register, and
875**
876** 2) transform the expression node to a TK_REGISTER node that reads
877** from the newly populated register.
drh2f2b0272015-08-14 18:50:04 +0000878**
879** Also, if the node is a TK_COLUMN that does access the table idenified
880** by pCCurHint.iTabCur, and an index is being used (which we will
881** know because CCurHint.pIdx!=0) then transform the TK_COLUMN into
882** an access of the index rather than the original table.
drhbec24762015-08-13 20:07:13 +0000883*/
884static int codeCursorHintFixExpr(Walker *pWalker, Expr *pExpr){
885 int rc = WRC_Continue;
drh2f2b0272015-08-14 18:50:04 +0000886 struct CCurHint *pHint = pWalker->u.pCCurHint;
danbe312ae2018-09-10 19:27:12 +0000887 if( pExpr->op==TK_COLUMN ){
drh2f2b0272015-08-14 18:50:04 +0000888 if( pExpr->iTable!=pHint->iTabCur ){
drh2f2b0272015-08-14 18:50:04 +0000889 int reg = ++pWalker->pParse->nMem; /* Register for column value */
dane3e79212018-09-11 13:38:35 +0000890 sqlite3ExprCode(pWalker->pParse, pExpr, reg);
drh2f2b0272015-08-14 18:50:04 +0000891 pExpr->op = TK_REGISTER;
892 pExpr->iTable = reg;
893 }else if( pHint->pIdx!=0 ){
894 pExpr->iTable = pHint->iIdxCur;
drhb9bcf7c2019-10-19 13:29:10 +0000895 pExpr->iColumn = sqlite3TableColumnToIndex(pHint->pIdx, pExpr->iColumn);
drh2f2b0272015-08-14 18:50:04 +0000896 assert( pExpr->iColumn>=0 );
897 }
drhbec24762015-08-13 20:07:13 +0000898 }else if( pExpr->op==TK_AGG_FUNCTION ){
899 /* An aggregate function in the WHERE clause of a query means this must
900 ** be a correlated sub-query, and expression pExpr is an aggregate from
901 ** the parent context. Do not walk the function arguments in this case.
902 **
903 ** todo: It should be possible to replace this node with a TK_REGISTER
904 ** expression, as the result of the expression must be stored in a
905 ** register at this point. The same holds for TK_AGG_COLUMN nodes. */
906 rc = WRC_Prune;
907 }
908 return rc;
909}
910
911/*
912** Insert an OP_CursorHint instruction if it is appropriate to do so.
913*/
914static void codeCursorHint(
danb324cf72016-06-17 14:33:32 +0000915 struct SrcList_item *pTabItem, /* FROM clause item */
drhb413a542015-08-17 17:19:28 +0000916 WhereInfo *pWInfo, /* The where clause */
917 WhereLevel *pLevel, /* Which loop to provide hints for */
918 WhereTerm *pEndRange /* Hint this end-of-scan boundary term if not NULL */
drhbec24762015-08-13 20:07:13 +0000919){
920 Parse *pParse = pWInfo->pParse;
921 sqlite3 *db = pParse->db;
922 Vdbe *v = pParse->pVdbe;
drhbec24762015-08-13 20:07:13 +0000923 Expr *pExpr = 0;
drh2f2b0272015-08-14 18:50:04 +0000924 WhereLoop *pLoop = pLevel->pWLoop;
drhbec24762015-08-13 20:07:13 +0000925 int iCur;
926 WhereClause *pWC;
927 WhereTerm *pTerm;
drhb413a542015-08-17 17:19:28 +0000928 int i, j;
drh2f2b0272015-08-14 18:50:04 +0000929 struct CCurHint sHint;
930 Walker sWalker;
drhbec24762015-08-13 20:07:13 +0000931
932 if( OptimizationDisabled(db, SQLITE_CursorHints) ) return;
drh2f2b0272015-08-14 18:50:04 +0000933 iCur = pLevel->iTabCur;
934 assert( iCur==pWInfo->pTabList->a[pLevel->iFrom].iCursor );
935 sHint.iTabCur = iCur;
936 sHint.iIdxCur = pLevel->iIdxCur;
937 sHint.pIdx = pLoop->u.btree.pIndex;
938 memset(&sWalker, 0, sizeof(sWalker));
939 sWalker.pParse = pParse;
940 sWalker.u.pCCurHint = &sHint;
drhbec24762015-08-13 20:07:13 +0000941 pWC = &pWInfo->sWC;
942 for(i=0; i<pWC->nTerm; i++){
943 pTerm = &pWC->a[i];
944 if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
945 if( pTerm->prereqAll & pLevel->notReady ) continue;
danb324cf72016-06-17 14:33:32 +0000946
947 /* Any terms specified as part of the ON(...) clause for any LEFT
948 ** JOIN for which the current table is not the rhs are omitted
949 ** from the cursor-hint.
950 **
dane6912fd2016-06-17 19:27:13 +0000951 ** If this table is the rhs of a LEFT JOIN, "IS" or "IS NULL" terms
952 ** that were specified as part of the WHERE clause must be excluded.
953 ** This is to address the following:
danb324cf72016-06-17 14:33:32 +0000954 **
955 ** SELECT ... t1 LEFT JOIN t2 ON (t1.a=t2.b) WHERE t2.c IS NULL;
956 **
dane6912fd2016-06-17 19:27:13 +0000957 ** Say there is a single row in t2 that matches (t1.a=t2.b), but its
958 ** t2.c values is not NULL. If the (t2.c IS NULL) constraint is
959 ** pushed down to the cursor, this row is filtered out, causing
960 ** SQLite to synthesize a row of NULL values. Which does match the
961 ** WHERE clause, and so the query returns a row. Which is incorrect.
962 **
963 ** For the same reason, WHERE terms such as:
964 **
965 ** WHERE 1 = (t2.c IS NULL)
966 **
967 ** are also excluded. See codeCursorHintIsOrFunction() for details.
danb324cf72016-06-17 14:33:32 +0000968 */
969 if( pTabItem->fg.jointype & JT_LEFT ){
dane6912fd2016-06-17 19:27:13 +0000970 Expr *pExpr = pTerm->pExpr;
971 if( !ExprHasProperty(pExpr, EP_FromJoin)
972 || pExpr->iRightJoinTable!=pTabItem->iCursor
danb324cf72016-06-17 14:33:32 +0000973 ){
dane6912fd2016-06-17 19:27:13 +0000974 sWalker.eCode = 0;
975 sWalker.xExprCallback = codeCursorHintIsOrFunction;
976 sqlite3WalkExpr(&sWalker, pTerm->pExpr);
977 if( sWalker.eCode ) continue;
danb324cf72016-06-17 14:33:32 +0000978 }
979 }else{
980 if( ExprHasProperty(pTerm->pExpr, EP_FromJoin) ) continue;
981 }
drhb413a542015-08-17 17:19:28 +0000982
983 /* All terms in pWLoop->aLTerm[] except pEndRange are used to initialize
drhbcf40a72015-08-18 15:58:05 +0000984 ** the cursor. These terms are not needed as hints for a pure range
985 ** scan (that has no == terms) so omit them. */
986 if( pLoop->u.btree.nEq==0 && pTerm!=pEndRange ){
987 for(j=0; j<pLoop->nLTerm && pLoop->aLTerm[j]!=pTerm; j++){}
988 if( j<pLoop->nLTerm ) continue;
drhb413a542015-08-17 17:19:28 +0000989 }
990
991 /* No subqueries or non-deterministic functions allowed */
drhbec24762015-08-13 20:07:13 +0000992 if( sqlite3ExprContainsSubquery(pTerm->pExpr) ) continue;
drhb413a542015-08-17 17:19:28 +0000993
994 /* For an index scan, make sure referenced columns are actually in
995 ** the index. */
drh2f2b0272015-08-14 18:50:04 +0000996 if( sHint.pIdx!=0 ){
997 sWalker.eCode = 0;
998 sWalker.xExprCallback = codeCursorHintCheckExpr;
999 sqlite3WalkExpr(&sWalker, pTerm->pExpr);
1000 if( sWalker.eCode ) continue;
1001 }
drhb413a542015-08-17 17:19:28 +00001002
1003 /* If we survive all prior tests, that means this term is worth hinting */
drhd5c851c2019-04-19 13:38:34 +00001004 pExpr = sqlite3ExprAnd(pParse, pExpr, sqlite3ExprDup(db, pTerm->pExpr, 0));
drhbec24762015-08-13 20:07:13 +00001005 }
1006 if( pExpr!=0 ){
drhbec24762015-08-13 20:07:13 +00001007 sWalker.xExprCallback = codeCursorHintFixExpr;
drhbec24762015-08-13 20:07:13 +00001008 sqlite3WalkExpr(&sWalker, pExpr);
drh2f2b0272015-08-14 18:50:04 +00001009 sqlite3VdbeAddOp4(v, OP_CursorHint,
1010 (sHint.pIdx ? sHint.iIdxCur : sHint.iTabCur), 0, 0,
1011 (const char*)pExpr, P4_EXPR);
drhbec24762015-08-13 20:07:13 +00001012 }
1013}
1014#else
danb324cf72016-06-17 14:33:32 +00001015# define codeCursorHint(A,B,C,D) /* No-op */
drhbec24762015-08-13 20:07:13 +00001016#endif /* SQLITE_ENABLE_CURSOR_HINTS */
drh6f82e852015-06-06 20:12:09 +00001017
1018/*
dande892d92016-01-29 19:29:45 +00001019** Cursor iCur is open on an intkey b-tree (a table). Register iRowid contains
1020** a rowid value just read from cursor iIdxCur, open on index pIdx. This
1021** function generates code to do a deferred seek of cursor iCur to the
1022** rowid stored in register iRowid.
1023**
1024** Normally, this is just:
1025**
drh170ad682017-06-02 15:44:22 +00001026** OP_DeferredSeek $iCur $iRowid
dande892d92016-01-29 19:29:45 +00001027**
1028** However, if the scan currently being coded is a branch of an OR-loop and
drh170ad682017-06-02 15:44:22 +00001029** the statement currently being coded is a SELECT, then P3 of OP_DeferredSeek
dande892d92016-01-29 19:29:45 +00001030** is set to iIdxCur and P4 is set to point to an array of integers
1031** containing one entry for each column of the table cursor iCur is open
1032** on. For each table column, if the column is the i'th column of the
1033** index, then the corresponding array entry is set to (i+1). If the column
1034** does not appear in the index at all, the array entry is set to 0.
1035*/
1036static void codeDeferredSeek(
1037 WhereInfo *pWInfo, /* Where clause context */
1038 Index *pIdx, /* Index scan is using */
1039 int iCur, /* Cursor for IPK b-tree */
dande892d92016-01-29 19:29:45 +00001040 int iIdxCur /* Index cursor */
1041){
1042 Parse *pParse = pWInfo->pParse; /* Parse context */
1043 Vdbe *v = pParse->pVdbe; /* Vdbe to generate code within */
1044
1045 assert( iIdxCur>0 );
1046 assert( pIdx->aiColumn[pIdx->nColumn-1]==-1 );
1047
drh170ad682017-06-02 15:44:22 +00001048 sqlite3VdbeAddOp3(v, OP_DeferredSeek, iIdxCur, 0, iCur);
drhce943bc2016-05-19 18:56:33 +00001049 if( (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)
dancddb6ba2016-02-01 13:58:56 +00001050 && DbMaskAllZero(sqlite3ParseToplevel(pParse)->writeMask)
dande892d92016-01-29 19:29:45 +00001051 ){
1052 int i;
1053 Table *pTab = pIdx->pTable;
drhb1702022016-01-30 00:45:18 +00001054 int *ai = (int*)sqlite3DbMallocZero(pParse->db, sizeof(int)*(pTab->nCol+1));
dande892d92016-01-29 19:29:45 +00001055 if( ai ){
drhb1702022016-01-30 00:45:18 +00001056 ai[0] = pTab->nCol;
dande892d92016-01-29 19:29:45 +00001057 for(i=0; i<pIdx->nColumn-1; i++){
drh4fb24c82019-11-06 17:31:18 +00001058 int x1, x2;
dande892d92016-01-29 19:29:45 +00001059 assert( pIdx->aiColumn[i]<pTab->nCol );
drh4fb24c82019-11-06 17:31:18 +00001060 x1 = pIdx->aiColumn[i];
1061 x2 = sqlite3TableColumnToStorage(pTab, x1);
1062 testcase( x1!=x2 );
mistachkinbde3a4f2019-11-06 19:25:45 +00001063 if( x1>=0 ) ai[x2+1] = i+1;
dande892d92016-01-29 19:29:45 +00001064 }
1065 sqlite3VdbeChangeP4(v, -1, (char*)ai, P4_INTARRAY);
1066 }
1067 }
1068}
1069
dan553168c2016-08-01 20:14:31 +00001070/*
1071** If the expression passed as the second argument is a vector, generate
1072** code to write the first nReg elements of the vector into an array
1073** of registers starting with iReg.
1074**
1075** If the expression is not a vector, then nReg must be passed 1. In
1076** this case, generate code to evaluate the expression and leave the
1077** result in register iReg.
1078*/
dan71c57db2016-07-09 20:23:55 +00001079static void codeExprOrVector(Parse *pParse, Expr *p, int iReg, int nReg){
1080 assert( nReg>0 );
dand03024d2017-09-09 19:41:12 +00001081 if( p && sqlite3ExprIsVector(p) ){
danf9b2e052016-08-02 17:45:00 +00001082#ifndef SQLITE_OMIT_SUBQUERY
1083 if( (p->flags & EP_xIsSelect) ){
1084 Vdbe *v = pParse->pVdbe;
drh85bcdce2018-12-23 21:27:29 +00001085 int iSelect;
1086 assert( p->op==TK_SELECT );
1087 iSelect = sqlite3CodeSubselect(pParse, p);
danf9b2e052016-08-02 17:45:00 +00001088 sqlite3VdbeAddOp3(v, OP_Copy, iSelect, iReg, nReg-1);
1089 }else
1090#endif
1091 {
1092 int i;
dan71c57db2016-07-09 20:23:55 +00001093 ExprList *pList = p->x.pList;
1094 assert( nReg<=pList->nExpr );
1095 for(i=0; i<nReg; i++){
1096 sqlite3ExprCode(pParse, pList->a[i].pExpr, iReg+i);
1097 }
dan71c57db2016-07-09 20:23:55 +00001098 }
1099 }else{
1100 assert( nReg==1 );
1101 sqlite3ExprCode(pParse, p, iReg);
1102 }
1103}
1104
drheac5fc02017-04-11 01:01:27 +00001105/* An instance of the IdxExprTrans object carries information about a
1106** mapping from an expression on table columns into a column in an index
1107** down through the Walker.
1108*/
drhaca19e12017-04-07 19:41:31 +00001109typedef struct IdxExprTrans {
1110 Expr *pIdxExpr; /* The index expression */
1111 int iTabCur; /* The cursor of the corresponding table */
1112 int iIdxCur; /* The cursor for the index */
1113 int iIdxCol; /* The column for the index */
drhc7476732019-10-24 20:29:25 +00001114 int iTabCol; /* The column for the table */
drhaca19e12017-04-07 19:41:31 +00001115} IdxExprTrans;
1116
drheac5fc02017-04-11 01:01:27 +00001117/* The walker node callback used to transform matching expressions into
1118** a reference to an index column for an index on an expression.
1119**
1120** If pExpr matches, then transform it into a reference to the index column
1121** that contains the value of pExpr.
1122*/
drhaca19e12017-04-07 19:41:31 +00001123static int whereIndexExprTransNode(Walker *p, Expr *pExpr){
1124 IdxExprTrans *pX = p->u.pIdxTrans;
dan5aa550c2017-06-24 18:10:29 +00001125 if( sqlite3ExprCompare(0, pExpr, pX->pIdxExpr, pX->iTabCur)==0 ){
danb6ce71b2019-08-20 11:43:44 +00001126 pExpr->affExpr = sqlite3ExprAffinity(pExpr);
drhaca19e12017-04-07 19:41:31 +00001127 pExpr->op = TK_COLUMN;
1128 pExpr->iTable = pX->iIdxCur;
1129 pExpr->iColumn = pX->iIdxCol;
drheda079c2018-09-20 19:02:15 +00001130 pExpr->y.pTab = 0;
drh6c1c85c2019-12-22 18:55:04 +00001131 testcase( ExprHasProperty(pExpr, EP_Skip) );
1132 testcase( ExprHasProperty(pExpr, EP_Unlikely) );
1133 ExprClearProperty(pExpr, EP_Skip|EP_Unlikely);
drhaca19e12017-04-07 19:41:31 +00001134 return WRC_Prune;
1135 }else{
1136 return WRC_Continue;
1137 }
1138}
1139
drhc7476732019-10-24 20:29:25 +00001140#ifndef SQLITE_OMIT_GENERATED_COLUMNS
1141/* A walker node callback that translates a column reference to a table
1142** into a corresponding column reference of an index.
1143*/
1144static int whereIndexExprTransColumn(Walker *p, Expr *pExpr){
1145 if( pExpr->op==TK_COLUMN ){
1146 IdxExprTrans *pX = p->u.pIdxTrans;
1147 if( pExpr->iTable==pX->iTabCur && pExpr->iColumn==pX->iTabCol ){
drh57f7ece2019-11-21 18:28:44 +00001148 assert( pExpr->y.pTab!=0 );
1149 pExpr->affExpr = sqlite3TableColumnAffinity(pExpr->y.pTab,pExpr->iColumn);
drhc7476732019-10-24 20:29:25 +00001150 pExpr->iTable = pX->iIdxCur;
1151 pExpr->iColumn = pX->iIdxCol;
drh4485ac12019-10-24 21:02:06 +00001152 pExpr->y.pTab = 0;
drhc7476732019-10-24 20:29:25 +00001153 }
1154 }
1155 return WRC_Continue;
1156}
1157#endif /* SQLITE_OMIT_GENERATED_COLUMNS */
1158
drhaca19e12017-04-07 19:41:31 +00001159/*
drhf49759b2017-08-25 19:51:51 +00001160** For an indexes on expression X, locate every instance of expression X
1161** in pExpr and change that subexpression into a reference to the appropriate
1162** column of the index.
drhc7476732019-10-24 20:29:25 +00001163**
1164** 2019-10-24: Updated to also translate references to a VIRTUAL column in
1165** the table into references to the corresponding (stored) column of the
1166** index.
drhaca19e12017-04-07 19:41:31 +00001167*/
1168static void whereIndexExprTrans(
1169 Index *pIdx, /* The Index */
1170 int iTabCur, /* Cursor of the table that is being indexed */
1171 int iIdxCur, /* Cursor of the index itself */
1172 WhereInfo *pWInfo /* Transform expressions in this WHERE clause */
1173){
1174 int iIdxCol; /* Column number of the index */
1175 ExprList *aColExpr; /* Expressions that are indexed */
drhc7476732019-10-24 20:29:25 +00001176 Table *pTab;
drhaca19e12017-04-07 19:41:31 +00001177 Walker w;
1178 IdxExprTrans x;
1179 aColExpr = pIdx->aColExpr;
drhc7476732019-10-24 20:29:25 +00001180 if( aColExpr==0 && !pIdx->bHasVCol ){
1181 /* The index does not reference any expressions or virtual columns
1182 ** so no translations are needed. */
1183 return;
1184 }
1185 pTab = pIdx->pTable;
drhaca19e12017-04-07 19:41:31 +00001186 memset(&w, 0, sizeof(w));
drhaca19e12017-04-07 19:41:31 +00001187 w.u.pIdxTrans = &x;
1188 x.iTabCur = iTabCur;
1189 x.iIdxCur = iIdxCur;
drhc7476732019-10-24 20:29:25 +00001190 for(iIdxCol=0; iIdxCol<pIdx->nColumn; iIdxCol++){
1191 i16 iRef = pIdx->aiColumn[iIdxCol];
1192 if( iRef==XN_EXPR ){
1193 assert( aColExpr->a[iIdxCol].pExpr!=0 );
1194 x.pIdxExpr = aColExpr->a[iIdxCol].pExpr;
drhe86f3402019-12-26 00:20:56 +00001195 if( sqlite3ExprIsConstant(x.pIdxExpr) ) continue;
drhc7476732019-10-24 20:29:25 +00001196 w.xExprCallback = whereIndexExprTransNode;
1197#ifndef SQLITE_OMIT_GENERATED_COLUMNS
drhed0c3482019-12-20 22:46:41 +00001198 }else if( iRef>=0
1199 && (pTab->aCol[iRef].colFlags & COLFLAG_VIRTUAL)!=0
1200 && (pTab->aCol[iRef].zColl==0
1201 || sqlite3StrICmp(pTab->aCol[iRef].zColl, sqlite3StrBINARY)==0)
1202 ){
1203 /* Check to see if there are direct references to generated columns
1204 ** that are contained in the index. Pulling the generated column
1205 ** out of the index is an optimization only - the main table is always
1206 ** available if the index cannot be used. To avoid unnecessary
1207 ** complication, omit this optimization if the collating sequence for
1208 ** the column is non-standard */
drhc7476732019-10-24 20:29:25 +00001209 x.iTabCol = iRef;
1210 w.xExprCallback = whereIndexExprTransColumn;
1211#endif /* SQLITE_OMIT_GENERATED_COLUMNS */
1212 }else{
1213 continue;
1214 }
drhaca19e12017-04-07 19:41:31 +00001215 x.iIdxCol = iIdxCol;
drhaca19e12017-04-07 19:41:31 +00001216 sqlite3WalkExpr(&w, pWInfo->pWhere);
1217 sqlite3WalkExprList(&w, pWInfo->pOrderBy);
1218 sqlite3WalkExprList(&w, pWInfo->pResultSet);
1219 }
1220}
drhaca19e12017-04-07 19:41:31 +00001221
dande892d92016-01-29 19:29:45 +00001222/*
drh610f11d2019-03-18 10:30:00 +00001223** The pTruth expression is always true because it is the WHERE clause
drhb531aa82019-03-01 18:07:05 +00001224** a partial index that is driving a query loop. Look through all of the
1225** WHERE clause terms on the query, and if any of those terms must be
1226** true because pTruth is true, then mark those WHERE clause terms as
1227** coded.
1228*/
1229static void whereApplyPartialIndexConstraints(
1230 Expr *pTruth,
1231 int iTabCur,
1232 WhereClause *pWC
1233){
1234 int i;
1235 WhereTerm *pTerm;
1236 while( pTruth->op==TK_AND ){
1237 whereApplyPartialIndexConstraints(pTruth->pLeft, iTabCur, pWC);
1238 pTruth = pTruth->pRight;
1239 }
1240 for(i=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
1241 Expr *pExpr;
1242 if( pTerm->wtFlags & TERM_CODED ) continue;
1243 pExpr = pTerm->pExpr;
1244 if( sqlite3ExprCompare(0, pExpr, pTruth, iTabCur)==0 ){
1245 pTerm->wtFlags |= TERM_CODED;
1246 }
1247 }
1248}
1249
1250/*
drh6f82e852015-06-06 20:12:09 +00001251** Generate code for the start of the iLevel-th loop in the WHERE clause
1252** implementation described by pWInfo.
1253*/
1254Bitmask sqlite3WhereCodeOneLoopStart(
drh47df8a22018-12-25 00:15:37 +00001255 Parse *pParse, /* Parsing context */
1256 Vdbe *v, /* Prepared statement under construction */
drh6f82e852015-06-06 20:12:09 +00001257 WhereInfo *pWInfo, /* Complete information about the WHERE clause */
1258 int iLevel, /* Which level of pWInfo->a[] should be coded */
drh47df8a22018-12-25 00:15:37 +00001259 WhereLevel *pLevel, /* The current level pointer */
drh6f82e852015-06-06 20:12:09 +00001260 Bitmask notReady /* Which tables are currently available */
1261){
1262 int j, k; /* Loop counters */
1263 int iCur; /* The VDBE cursor for the table */
1264 int addrNxt; /* Where to jump to continue with the next IN case */
drh6f82e852015-06-06 20:12:09 +00001265 int bRev; /* True if we need to scan in reverse order */
drh6f82e852015-06-06 20:12:09 +00001266 WhereLoop *pLoop; /* The WhereLoop object being coded */
1267 WhereClause *pWC; /* Decomposition of the entire WHERE clause */
1268 WhereTerm *pTerm; /* A WHERE clause term */
drh6f82e852015-06-06 20:12:09 +00001269 sqlite3 *db; /* Database connection */
drh6f82e852015-06-06 20:12:09 +00001270 struct SrcList_item *pTabItem; /* FROM clause term being coded */
1271 int addrBrk; /* Jump here to break out of the loop */
drh3a3b4202017-02-15 22:36:15 +00001272 int addrHalt; /* addrBrk for the outermost loop */
drh6f82e852015-06-06 20:12:09 +00001273 int addrCont; /* Jump here to continue with next cycle */
1274 int iRowidReg = 0; /* Rowid is stored in this register, if not zero */
1275 int iReleaseReg = 0; /* Temp register to free before returning */
dan6f654a42017-04-28 19:59:55 +00001276 Index *pIdx = 0; /* Index used by loop (if any) */
danebc63012017-07-10 14:33:00 +00001277 int iLoop; /* Iteration of constraint generator loop */
drh6f82e852015-06-06 20:12:09 +00001278
drh6f82e852015-06-06 20:12:09 +00001279 pWC = &pWInfo->sWC;
1280 db = pParse->db;
drh6f82e852015-06-06 20:12:09 +00001281 pLoop = pLevel->pWLoop;
1282 pTabItem = &pWInfo->pTabList->a[pLevel->iFrom];
1283 iCur = pTabItem->iCursor;
1284 pLevel->notReady = notReady & ~sqlite3WhereGetMask(&pWInfo->sMaskSet, iCur);
1285 bRev = (pWInfo->revMask>>iLevel)&1;
drh6f82e852015-06-06 20:12:09 +00001286 VdbeModuleComment((v, "Begin WHERE-loop%d: %s",iLevel,pTabItem->pTab->zName));
drh118efd12019-12-28 14:07:22 +00001287#if WHERETRACE_ENABLED /* 0x20800 */
1288 if( sqlite3WhereTrace & 0x800 ){
drha4b2df52019-12-28 16:20:23 +00001289 sqlite3DebugPrintf("Coding level %d of %d: notReady=%llx iFrom=%d\n",
1290 iLevel, pWInfo->nLevel, (u64)notReady, pLevel->iFrom);
drh118efd12019-12-28 14:07:22 +00001291 sqlite3WhereLoopPrint(pLoop, pWC);
1292 }
1293 if( sqlite3WhereTrace & 0x20000 ){
drhf1bb31e2019-12-28 14:33:26 +00001294 if( iLevel==0 ){
1295 sqlite3DebugPrintf("WHERE clause being coded:\n");
1296 sqlite3TreeViewExpr(0, pWInfo->pWhere, 0);
1297 }
1298 sqlite3DebugPrintf("All WHERE-clause terms before coding:\n");
drh118efd12019-12-28 14:07:22 +00001299 sqlite3WhereClausePrint(pWC);
1300 }
1301#endif
drh6f82e852015-06-06 20:12:09 +00001302
1303 /* Create labels for the "break" and "continue" instructions
1304 ** for the current loop. Jump to addrBrk to break out of a loop.
1305 ** Jump to cont to go immediately to the next iteration of the
1306 ** loop.
1307 **
1308 ** When there is an IN operator, we also have a "addrNxt" label that
1309 ** means to continue with the next IN value combination. When
1310 ** there are no IN operators in the constraints, the "addrNxt" label
1311 ** is the same as "addrBrk".
1312 */
drhec4ccdb2018-12-29 02:26:59 +00001313 addrBrk = pLevel->addrBrk = pLevel->addrNxt = sqlite3VdbeMakeLabel(pParse);
1314 addrCont = pLevel->addrCont = sqlite3VdbeMakeLabel(pParse);
drh6f82e852015-06-06 20:12:09 +00001315
1316 /* If this is the right table of a LEFT OUTER JOIN, allocate and
1317 ** initialize a memory cell that records if this table matches any
1318 ** row of the left table of the join.
1319 */
dan820fcd22018-04-24 18:53:24 +00001320 assert( (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)
1321 || pLevel->iFrom>0 || (pTabItem[0].fg.jointype & JT_LEFT)==0
1322 );
drh8a48b9c2015-08-19 15:20:00 +00001323 if( pLevel->iFrom>0 && (pTabItem[0].fg.jointype & JT_LEFT)!=0 ){
drh6f82e852015-06-06 20:12:09 +00001324 pLevel->iLeftJoin = ++pParse->nMem;
1325 sqlite3VdbeAddOp2(v, OP_Integer, 0, pLevel->iLeftJoin);
1326 VdbeComment((v, "init LEFT JOIN no-match flag"));
1327 }
1328
drh3a3b4202017-02-15 22:36:15 +00001329 /* Compute a safe address to jump to if we discover that the table for
1330 ** this loop is empty and can never contribute content. */
1331 for(j=iLevel; j>0 && pWInfo->a[j].iLeftJoin==0; j--){}
1332 addrHalt = pWInfo->a[j].addrBrk;
1333
drh6f82e852015-06-06 20:12:09 +00001334 /* Special case of a FROM clause subquery implemented as a co-routine */
drh8a48b9c2015-08-19 15:20:00 +00001335 if( pTabItem->fg.viaCoroutine ){
drh6f82e852015-06-06 20:12:09 +00001336 int regYield = pTabItem->regReturn;
1337 sqlite3VdbeAddOp3(v, OP_InitCoroutine, regYield, 0, pTabItem->addrFillSub);
1338 pLevel->p2 = sqlite3VdbeAddOp2(v, OP_Yield, regYield, addrBrk);
1339 VdbeCoverage(v);
drhfef37762018-07-10 19:48:35 +00001340 VdbeComment((v, "next row of %s", pTabItem->pTab->zName));
drh6f82e852015-06-06 20:12:09 +00001341 pLevel->op = OP_Goto;
1342 }else
1343
1344#ifndef SQLITE_OMIT_VIRTUALTABLE
1345 if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)!=0 ){
1346 /* Case 1: The table is a virtual-table. Use the VFilter and VNext
1347 ** to access the data.
1348 */
1349 int iReg; /* P3 Value for OP_VFilter */
1350 int addrNotFound;
1351 int nConstraint = pLoop->nLTerm;
drhdbc49162016-03-02 03:28:07 +00001352 int iIn; /* Counter for IN constraints */
drh6f82e852015-06-06 20:12:09 +00001353
drh6f82e852015-06-06 20:12:09 +00001354 iReg = sqlite3GetTempRange(pParse, nConstraint+2);
1355 addrNotFound = pLevel->addrBrk;
1356 for(j=0; j<nConstraint; j++){
1357 int iTarget = iReg+j+2;
1358 pTerm = pLoop->aLTerm[j];
drh599d5762016-03-08 01:11:51 +00001359 if( NEVER(pTerm==0) ) continue;
drh6f82e852015-06-06 20:12:09 +00001360 if( pTerm->eOperator & WO_IN ){
1361 codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, iTarget);
1362 addrNotFound = pLevel->addrNxt;
1363 }else{
dan6256c1c2016-08-08 20:15:41 +00001364 Expr *pRight = pTerm->pExpr->pRight;
drhfc7f27b2016-08-20 00:07:01 +00001365 codeExprOrVector(pParse, pRight, iTarget, 1);
drh6f82e852015-06-06 20:12:09 +00001366 }
1367 }
1368 sqlite3VdbeAddOp2(v, OP_Integer, pLoop->u.vtab.idxNum, iReg);
1369 sqlite3VdbeAddOp2(v, OP_Integer, nConstraint, iReg+1);
1370 sqlite3VdbeAddOp4(v, OP_VFilter, iCur, addrNotFound, iReg,
1371 pLoop->u.vtab.idxStr,
drh861b1302016-12-07 20:22:31 +00001372 pLoop->u.vtab.needFree ? P4_DYNAMIC : P4_STATIC);
drh6f82e852015-06-06 20:12:09 +00001373 VdbeCoverage(v);
1374 pLoop->u.vtab.needFree = 0;
drh6f82e852015-06-06 20:12:09 +00001375 pLevel->p1 = iCur;
dan354474a2015-09-29 10:11:26 +00001376 pLevel->op = pWInfo->eOnePass ? OP_Noop : OP_VNext;
drh6f82e852015-06-06 20:12:09 +00001377 pLevel->p2 = sqlite3VdbeCurrentAddr(v);
drhdbc49162016-03-02 03:28:07 +00001378 iIn = pLevel->u.in.nIn;
1379 for(j=nConstraint-1; j>=0; j--){
1380 pTerm = pLoop->aLTerm[j];
drh68748ec2019-10-14 20:32:31 +00001381 if( (pTerm->eOperator & WO_IN)!=0 ) iIn--;
drhdbc49162016-03-02 03:28:07 +00001382 if( j<16 && (pLoop->u.vtab.omitMask>>j)&1 ){
1383 disableTerm(pLevel, pTerm);
drh4ec3e822019-10-15 19:01:55 +00001384 }else if( (pTerm->eOperator & WO_IN)!=0
1385 && sqlite3ExprVectorSize(pTerm->pExpr->pLeft)==1
dan2d822692019-10-14 15:15:50 +00001386 ){
drhdbc49162016-03-02 03:28:07 +00001387 Expr *pCompare; /* The comparison operator */
1388 Expr *pRight; /* RHS of the comparison */
1389 VdbeOp *pOp; /* Opcode to access the value of the IN constraint */
1390
1391 /* Reload the constraint value into reg[iReg+j+2]. The same value
1392 ** was loaded into the same register prior to the OP_VFilter, but
1393 ** the xFilter implementation might have changed the datatype or
1394 ** encoding of the value in the register, so it *must* be reloaded. */
1395 assert( pLevel->u.in.aInLoop!=0 || db->mallocFailed );
drhfb826b82016-03-08 00:39:58 +00001396 if( !db->mallocFailed ){
drh68748ec2019-10-14 20:32:31 +00001397 assert( iIn>=0 && iIn<pLevel->u.in.nIn );
1398 pOp = sqlite3VdbeGetOp(v, pLevel->u.in.aInLoop[iIn].addrInTop);
drhdbc49162016-03-02 03:28:07 +00001399 assert( pOp->opcode==OP_Column || pOp->opcode==OP_Rowid );
1400 assert( pOp->opcode!=OP_Column || pOp->p3==iReg+j+2 );
1401 assert( pOp->opcode!=OP_Rowid || pOp->p2==iReg+j+2 );
1402 testcase( pOp->opcode==OP_Rowid );
1403 sqlite3VdbeAddOp3(v, pOp->opcode, pOp->p1, pOp->p2, pOp->p3);
1404 }
1405
1406 /* Generate code that will continue to the next row if
1407 ** the IN constraint is not satisfied */
drhabfd35e2016-12-06 22:47:23 +00001408 pCompare = sqlite3PExpr(pParse, TK_EQ, 0, 0);
drhdbc49162016-03-02 03:28:07 +00001409 assert( pCompare!=0 || db->mallocFailed );
1410 if( pCompare ){
1411 pCompare->pLeft = pTerm->pExpr->pLeft;
1412 pCompare->pRight = pRight = sqlite3Expr(db, TK_REGISTER, 0);
drh237b2b72016-03-07 19:08:27 +00001413 if( pRight ){
1414 pRight->iTable = iReg+j+2;
1415 sqlite3ExprIfFalse(pParse, pCompare, pLevel->addrCont, 0);
1416 }
drhdbc49162016-03-02 03:28:07 +00001417 pCompare->pLeft = 0;
1418 sqlite3ExprDelete(db, pCompare);
1419 }
1420 }
1421 }
drh68748ec2019-10-14 20:32:31 +00001422 assert( iIn==0 || db->mallocFailed );
drhba26faa2016-04-09 18:04:28 +00001423 /* These registers need to be preserved in case there is an IN operator
1424 ** loop. So we could deallocate the registers here (and potentially
1425 ** reuse them later) if (pLoop->wsFlags & WHERE_IN_ABLE)==0. But it seems
1426 ** simpler and safer to simply not reuse the registers.
1427 **
1428 ** sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2);
1429 */
drh6f82e852015-06-06 20:12:09 +00001430 }else
1431#endif /* SQLITE_OMIT_VIRTUALTABLE */
1432
1433 if( (pLoop->wsFlags & WHERE_IPK)!=0
1434 && (pLoop->wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_EQ))!=0
1435 ){
1436 /* Case 2: We can directly reference a single row using an
1437 ** equality comparison against the ROWID field. Or
1438 ** we reference multiple rows using a "rowid IN (...)"
1439 ** construct.
1440 */
1441 assert( pLoop->u.btree.nEq==1 );
1442 pTerm = pLoop->aLTerm[0];
1443 assert( pTerm!=0 );
1444 assert( pTerm->pExpr!=0 );
drh6f82e852015-06-06 20:12:09 +00001445 testcase( pTerm->wtFlags & TERM_VIRTUAL );
1446 iReleaseReg = ++pParse->nMem;
1447 iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, 0, bRev, iReleaseReg);
1448 if( iRowidReg!=iReleaseReg ) sqlite3ReleaseTempReg(pParse, iReleaseReg);
1449 addrNxt = pLevel->addrNxt;
drheeb95652016-05-26 20:56:38 +00001450 sqlite3VdbeAddOp3(v, OP_SeekRowid, iCur, addrNxt, iRowidReg);
drh6f82e852015-06-06 20:12:09 +00001451 VdbeCoverage(v);
drh6f82e852015-06-06 20:12:09 +00001452 pLevel->op = OP_Noop;
drhbc0a55c2019-02-22 21:33:56 +00001453 if( (pTerm->prereqAll & pLevel->notReady)==0 ){
1454 pTerm->wtFlags |= TERM_CODED;
1455 }
drh6f82e852015-06-06 20:12:09 +00001456 }else if( (pLoop->wsFlags & WHERE_IPK)!=0
1457 && (pLoop->wsFlags & WHERE_COLUMN_RANGE)!=0
1458 ){
1459 /* Case 3: We have an inequality comparison against the ROWID field.
1460 */
1461 int testOp = OP_Noop;
1462 int start;
1463 int memEndValue = 0;
1464 WhereTerm *pStart, *pEnd;
1465
drh6f82e852015-06-06 20:12:09 +00001466 j = 0;
1467 pStart = pEnd = 0;
1468 if( pLoop->wsFlags & WHERE_BTM_LIMIT ) pStart = pLoop->aLTerm[j++];
1469 if( pLoop->wsFlags & WHERE_TOP_LIMIT ) pEnd = pLoop->aLTerm[j++];
1470 assert( pStart!=0 || pEnd!=0 );
1471 if( bRev ){
1472 pTerm = pStart;
1473 pStart = pEnd;
1474 pEnd = pTerm;
1475 }
danb324cf72016-06-17 14:33:32 +00001476 codeCursorHint(pTabItem, pWInfo, pLevel, pEnd);
drh6f82e852015-06-06 20:12:09 +00001477 if( pStart ){
1478 Expr *pX; /* The expression that defines the start bound */
1479 int r1, rTemp; /* Registers for holding the start boundary */
dan19ff12d2016-07-29 20:58:19 +00001480 int op; /* Cursor seek operation */
drh6f82e852015-06-06 20:12:09 +00001481
1482 /* The following constant maps TK_xx codes into corresponding
1483 ** seek opcodes. It depends on a particular ordering of TK_xx
1484 */
1485 const u8 aMoveOp[] = {
1486 /* TK_GT */ OP_SeekGT,
1487 /* TK_LE */ OP_SeekLE,
1488 /* TK_LT */ OP_SeekLT,
1489 /* TK_GE */ OP_SeekGE
1490 };
1491 assert( TK_LE==TK_GT+1 ); /* Make sure the ordering.. */
1492 assert( TK_LT==TK_GT+2 ); /* ... of the TK_xx values... */
1493 assert( TK_GE==TK_GT+3 ); /* ... is correcct. */
1494
1495 assert( (pStart->wtFlags & TERM_VNULL)==0 );
1496 testcase( pStart->wtFlags & TERM_VIRTUAL );
1497 pX = pStart->pExpr;
1498 assert( pX!=0 );
1499 testcase( pStart->leftCursor!=iCur ); /* transitive constraints */
dan625015e2016-07-30 16:39:28 +00001500 if( sqlite3ExprIsVector(pX->pRight) ){
dan19ff12d2016-07-29 20:58:19 +00001501 r1 = rTemp = sqlite3GetTempReg(pParse);
1502 codeExprOrVector(pParse, pX->pRight, r1, 1);
drh4d1c6842018-02-13 18:48:08 +00001503 testcase( pX->op==TK_GT );
1504 testcase( pX->op==TK_GE );
1505 testcase( pX->op==TK_LT );
1506 testcase( pX->op==TK_LE );
1507 op = aMoveOp[((pX->op - TK_GT - 1) & 0x3) | 0x1];
1508 assert( pX->op!=TK_GT || op==OP_SeekGE );
1509 assert( pX->op!=TK_GE || op==OP_SeekGE );
1510 assert( pX->op!=TK_LT || op==OP_SeekLE );
1511 assert( pX->op!=TK_LE || op==OP_SeekLE );
dan19ff12d2016-07-29 20:58:19 +00001512 }else{
1513 r1 = sqlite3ExprCodeTemp(pParse, pX->pRight, &rTemp);
1514 disableTerm(pLevel, pStart);
1515 op = aMoveOp[(pX->op - TK_GT)];
1516 }
1517 sqlite3VdbeAddOp3(v, op, iCur, addrBrk, r1);
drh6f82e852015-06-06 20:12:09 +00001518 VdbeComment((v, "pk"));
1519 VdbeCoverageIf(v, pX->op==TK_GT);
1520 VdbeCoverageIf(v, pX->op==TK_LE);
1521 VdbeCoverageIf(v, pX->op==TK_LT);
1522 VdbeCoverageIf(v, pX->op==TK_GE);
drh6f82e852015-06-06 20:12:09 +00001523 sqlite3ReleaseTempReg(pParse, rTemp);
drh6f82e852015-06-06 20:12:09 +00001524 }else{
drh3a3b4202017-02-15 22:36:15 +00001525 sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iCur, addrHalt);
drh6f82e852015-06-06 20:12:09 +00001526 VdbeCoverageIf(v, bRev==0);
1527 VdbeCoverageIf(v, bRev!=0);
1528 }
1529 if( pEnd ){
1530 Expr *pX;
1531 pX = pEnd->pExpr;
1532 assert( pX!=0 );
1533 assert( (pEnd->wtFlags & TERM_VNULL)==0 );
1534 testcase( pEnd->leftCursor!=iCur ); /* Transitive constraints */
1535 testcase( pEnd->wtFlags & TERM_VIRTUAL );
1536 memEndValue = ++pParse->nMem;
dan19ff12d2016-07-29 20:58:19 +00001537 codeExprOrVector(pParse, pX->pRight, memEndValue, 1);
dan625015e2016-07-30 16:39:28 +00001538 if( 0==sqlite3ExprIsVector(pX->pRight)
1539 && (pX->op==TK_LT || pX->op==TK_GT)
1540 ){
drh6f82e852015-06-06 20:12:09 +00001541 testOp = bRev ? OP_Le : OP_Ge;
1542 }else{
1543 testOp = bRev ? OP_Lt : OP_Gt;
1544 }
dan553168c2016-08-01 20:14:31 +00001545 if( 0==sqlite3ExprIsVector(pX->pRight) ){
1546 disableTerm(pLevel, pEnd);
1547 }
drh6f82e852015-06-06 20:12:09 +00001548 }
1549 start = sqlite3VdbeCurrentAddr(v);
1550 pLevel->op = bRev ? OP_Prev : OP_Next;
1551 pLevel->p1 = iCur;
1552 pLevel->p2 = start;
1553 assert( pLevel->p5==0 );
1554 if( testOp!=OP_Noop ){
1555 iRowidReg = ++pParse->nMem;
1556 sqlite3VdbeAddOp2(v, OP_Rowid, iCur, iRowidReg);
drh6f82e852015-06-06 20:12:09 +00001557 sqlite3VdbeAddOp3(v, testOp, memEndValue, addrBrk, iRowidReg);
1558 VdbeCoverageIf(v, testOp==OP_Le);
1559 VdbeCoverageIf(v, testOp==OP_Lt);
1560 VdbeCoverageIf(v, testOp==OP_Ge);
1561 VdbeCoverageIf(v, testOp==OP_Gt);
1562 sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC | SQLITE_JUMPIFNULL);
1563 }
1564 }else if( pLoop->wsFlags & WHERE_INDEXED ){
1565 /* Case 4: A scan using an index.
1566 **
1567 ** The WHERE clause may contain zero or more equality
1568 ** terms ("==" or "IN" operators) that refer to the N
1569 ** left-most columns of the index. It may also contain
1570 ** inequality constraints (>, <, >= or <=) on the indexed
1571 ** column that immediately follows the N equalities. Only
1572 ** the right-most column can be an inequality - the rest must
1573 ** use the "==" and "IN" operators. For example, if the
1574 ** index is on (x,y,z), then the following clauses are all
1575 ** optimized:
1576 **
1577 ** x=5
1578 ** x=5 AND y=10
1579 ** x=5 AND y<10
1580 ** x=5 AND y>5 AND y<10
1581 ** x=5 AND y=5 AND z<=10
1582 **
1583 ** The z<10 term of the following cannot be used, only
1584 ** the x=5 term:
1585 **
1586 ** x=5 AND z<10
1587 **
1588 ** N may be zero if there are inequality constraints.
1589 ** If there are no inequality constraints, then N is at
1590 ** least one.
1591 **
1592 ** This case is also used when there are no WHERE clause
1593 ** constraints but an index is selected anyway, in order
1594 ** to force the output order to conform to an ORDER BY.
1595 */
1596 static const u8 aStartOp[] = {
1597 0,
1598 0,
1599 OP_Rewind, /* 2: (!start_constraints && startEq && !bRev) */
1600 OP_Last, /* 3: (!start_constraints && startEq && bRev) */
1601 OP_SeekGT, /* 4: (start_constraints && !startEq && !bRev) */
1602 OP_SeekLT, /* 5: (start_constraints && !startEq && bRev) */
1603 OP_SeekGE, /* 6: (start_constraints && startEq && !bRev) */
1604 OP_SeekLE /* 7: (start_constraints && startEq && bRev) */
1605 };
1606 static const u8 aEndOp[] = {
1607 OP_IdxGE, /* 0: (end_constraints && !bRev && !endEq) */
1608 OP_IdxGT, /* 1: (end_constraints && !bRev && endEq) */
1609 OP_IdxLE, /* 2: (end_constraints && bRev && !endEq) */
1610 OP_IdxLT, /* 3: (end_constraints && bRev && endEq) */
1611 };
1612 u16 nEq = pLoop->u.btree.nEq; /* Number of == or IN terms */
dan71c57db2016-07-09 20:23:55 +00001613 u16 nBtm = pLoop->u.btree.nBtm; /* Length of BTM vector */
1614 u16 nTop = pLoop->u.btree.nTop; /* Length of TOP vector */
drh6f82e852015-06-06 20:12:09 +00001615 int regBase; /* Base register holding constraint values */
1616 WhereTerm *pRangeStart = 0; /* Inequality constraint at range start */
1617 WhereTerm *pRangeEnd = 0; /* Inequality constraint at range end */
1618 int startEq; /* True if range start uses ==, >= or <= */
1619 int endEq; /* True if range end uses ==, >= or <= */
1620 int start_constraints; /* Start of range is constrained */
1621 int nConstraint; /* Number of constraint terms */
drh6f82e852015-06-06 20:12:09 +00001622 int iIdxCur; /* The VDBE cursor for the index */
1623 int nExtraReg = 0; /* Number of extra registers needed */
1624 int op; /* Instruction opcode */
1625 char *zStartAff; /* Affinity for start of range constraint */
danb7ca2172016-08-26 17:54:46 +00001626 char *zEndAff = 0; /* Affinity for end of range constraint */
drh6f82e852015-06-06 20:12:09 +00001627 u8 bSeekPastNull = 0; /* True to seek past initial nulls */
1628 u8 bStopAtNull = 0; /* Add condition to terminate at NULLs */
drh47df8a22018-12-25 00:15:37 +00001629 int omitTable; /* True if we use the index only */
drh74e1b862019-08-23 13:08:49 +00001630 int regBignull = 0; /* big-null flag register */
drh6f82e852015-06-06 20:12:09 +00001631
1632 pIdx = pLoop->u.btree.pIndex;
1633 iIdxCur = pLevel->iIdxCur;
1634 assert( nEq>=pLoop->nSkip );
1635
drh6f82e852015-06-06 20:12:09 +00001636 /* Find any inequality constraint terms for the start and end
1637 ** of the range.
1638 */
1639 j = nEq;
1640 if( pLoop->wsFlags & WHERE_BTM_LIMIT ){
1641 pRangeStart = pLoop->aLTerm[j++];
dan71c57db2016-07-09 20:23:55 +00001642 nExtraReg = MAX(nExtraReg, pLoop->u.btree.nBtm);
drh6f82e852015-06-06 20:12:09 +00001643 /* Like optimization range constraints always occur in pairs */
1644 assert( (pRangeStart->wtFlags & TERM_LIKEOPT)==0 ||
1645 (pLoop->wsFlags & WHERE_TOP_LIMIT)!=0 );
1646 }
1647 if( pLoop->wsFlags & WHERE_TOP_LIMIT ){
1648 pRangeEnd = pLoop->aLTerm[j++];
dan71c57db2016-07-09 20:23:55 +00001649 nExtraReg = MAX(nExtraReg, pLoop->u.btree.nTop);
drh41d2e662015-12-01 21:23:07 +00001650#ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
drh6f82e852015-06-06 20:12:09 +00001651 if( (pRangeEnd->wtFlags & TERM_LIKEOPT)!=0 ){
1652 assert( pRangeStart!=0 ); /* LIKE opt constraints */
1653 assert( pRangeStart->wtFlags & TERM_LIKEOPT ); /* occur in pairs */
drh44aebff2016-05-02 10:25:42 +00001654 pLevel->iLikeRepCntr = (u32)++pParse->nMem;
1655 sqlite3VdbeAddOp2(v, OP_Integer, 1, (int)pLevel->iLikeRepCntr);
drh6f82e852015-06-06 20:12:09 +00001656 VdbeComment((v, "LIKE loop counter"));
1657 pLevel->addrLikeRep = sqlite3VdbeCurrentAddr(v);
drh44aebff2016-05-02 10:25:42 +00001658 /* iLikeRepCntr actually stores 2x the counter register number. The
1659 ** bottom bit indicates whether the search order is ASC or DESC. */
1660 testcase( bRev );
1661 testcase( pIdx->aSortOrder[nEq]==SQLITE_SO_DESC );
1662 assert( (bRev & ~1)==0 );
1663 pLevel->iLikeRepCntr <<=1;
1664 pLevel->iLikeRepCntr |= bRev ^ (pIdx->aSortOrder[nEq]==SQLITE_SO_DESC);
drh6f82e852015-06-06 20:12:09 +00001665 }
drh41d2e662015-12-01 21:23:07 +00001666#endif
drh48590fc2016-10-10 13:29:15 +00001667 if( pRangeStart==0 ){
1668 j = pIdx->aiColumn[nEq];
1669 if( (j>=0 && pIdx->pTable->aCol[j].notNull==0) || j==XN_EXPR ){
1670 bSeekPastNull = 1;
1671 }
drh6f82e852015-06-06 20:12:09 +00001672 }
1673 }
1674 assert( pRangeEnd==0 || (pRangeEnd->wtFlags & TERM_VNULL)==0 );
1675
dan15750a22019-08-16 21:07:19 +00001676 /* If the WHERE_BIGNULL_SORT flag is set, then index column nEq uses
1677 ** a non-default "big-null" sort (either ASC NULLS LAST or DESC NULLS
1678 ** FIRST). In both cases separate ordered scans are made of those
1679 ** index entries for which the column is null and for those for which
1680 ** it is not. For an ASC sort, the non-NULL entries are scanned first.
1681 ** For DESC, NULL entries are scanned first.
1682 */
dan15750a22019-08-16 21:07:19 +00001683 if( (pLoop->wsFlags & (WHERE_TOP_LIMIT|WHERE_BTM_LIMIT))==0
1684 && (pLoop->wsFlags & WHERE_BIGNULL_SORT)!=0
1685 ){
1686 assert( bSeekPastNull==0 && nExtraReg==0 && nBtm==0 && nTop==0 );
1687 assert( pRangeEnd==0 && pRangeStart==0 );
dan4adb1d02019-12-28 18:08:39 +00001688 testcase( pLoop->nSkip>0 );
dan15750a22019-08-16 21:07:19 +00001689 nExtraReg = 1;
1690 bSeekPastNull = 1;
1691 pLevel->regBignull = regBignull = ++pParse->nMem;
dancc491f42019-08-17 17:55:54 +00001692 pLevel->addrBignull = sqlite3VdbeMakeLabel(pParse);
dan15750a22019-08-16 21:07:19 +00001693 }
1694
drh6f82e852015-06-06 20:12:09 +00001695 /* If we are doing a reverse order scan on an ascending index, or
1696 ** a forward order scan on a descending index, interchange the
1697 ** start and end terms (pRangeStart and pRangeEnd).
1698 */
1699 if( (nEq<pIdx->nKeyCol && bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC))
1700 || (bRev && pIdx->nKeyCol==nEq)
1701 ){
1702 SWAP(WhereTerm *, pRangeEnd, pRangeStart);
1703 SWAP(u8, bSeekPastNull, bStopAtNull);
dan71c57db2016-07-09 20:23:55 +00001704 SWAP(u8, nBtm, nTop);
drh6f82e852015-06-06 20:12:09 +00001705 }
1706
drhbcf40a72015-08-18 15:58:05 +00001707 /* Generate code to evaluate all constraint terms using == or IN
1708 ** and store the values of those terms in an array of registers
1709 ** starting at regBase.
1710 */
danb324cf72016-06-17 14:33:32 +00001711 codeCursorHint(pTabItem, pWInfo, pLevel, pRangeEnd);
drhbcf40a72015-08-18 15:58:05 +00001712 regBase = codeAllEqualityTerms(pParse,pLevel,bRev,nExtraReg,&zStartAff);
1713 assert( zStartAff==0 || sqlite3Strlen30(zStartAff)>=nEq );
danb7ca2172016-08-26 17:54:46 +00001714 if( zStartAff && nTop ){
1715 zEndAff = sqlite3DbStrDup(db, &zStartAff[nEq]);
1716 }
dancc491f42019-08-17 17:55:54 +00001717 addrNxt = (regBignull ? pLevel->addrBignull : pLevel->addrNxt);
drhbcf40a72015-08-18 15:58:05 +00001718
drh6f82e852015-06-06 20:12:09 +00001719 testcase( pRangeStart && (pRangeStart->eOperator & WO_LE)!=0 );
1720 testcase( pRangeStart && (pRangeStart->eOperator & WO_GE)!=0 );
1721 testcase( pRangeEnd && (pRangeEnd->eOperator & WO_LE)!=0 );
1722 testcase( pRangeEnd && (pRangeEnd->eOperator & WO_GE)!=0 );
1723 startEq = !pRangeStart || pRangeStart->eOperator & (WO_LE|WO_GE);
1724 endEq = !pRangeEnd || pRangeEnd->eOperator & (WO_LE|WO_GE);
1725 start_constraints = pRangeStart || nEq>0;
1726
1727 /* Seek the index cursor to the start of the range. */
1728 nConstraint = nEq;
1729 if( pRangeStart ){
1730 Expr *pRight = pRangeStart->pExpr->pRight;
dan71c57db2016-07-09 20:23:55 +00001731 codeExprOrVector(pParse, pRight, regBase+nEq, nBtm);
drh6f82e852015-06-06 20:12:09 +00001732 whereLikeOptimizationStringFixup(v, pLevel, pRangeStart);
1733 if( (pRangeStart->wtFlags & TERM_VNULL)==0
1734 && sqlite3ExprCanBeNull(pRight)
1735 ){
1736 sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt);
1737 VdbeCoverage(v);
1738 }
1739 if( zStartAff ){
drhe3c6b612016-10-05 20:10:32 +00001740 updateRangeAffinityStr(pRight, nBtm, &zStartAff[nEq]);
drh6f82e852015-06-06 20:12:09 +00001741 }
dan71c57db2016-07-09 20:23:55 +00001742 nConstraint += nBtm;
drh6f82e852015-06-06 20:12:09 +00001743 testcase( pRangeStart->wtFlags & TERM_VIRTUAL );
dan625015e2016-07-30 16:39:28 +00001744 if( sqlite3ExprIsVector(pRight)==0 ){
dan71c57db2016-07-09 20:23:55 +00001745 disableTerm(pLevel, pRangeStart);
1746 }else{
1747 startEq = 1;
1748 }
drh426f4ab2016-07-26 04:31:14 +00001749 bSeekPastNull = 0;
drh6f82e852015-06-06 20:12:09 +00001750 }else if( bSeekPastNull ){
drh6f82e852015-06-06 20:12:09 +00001751 startEq = 0;
drh0086e072019-08-23 16:12:20 +00001752 sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
drh6f82e852015-06-06 20:12:09 +00001753 start_constraints = 1;
drh0086e072019-08-23 16:12:20 +00001754 nConstraint++;
dan15750a22019-08-16 21:07:19 +00001755 }else if( regBignull ){
1756 sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
1757 start_constraints = 1;
1758 nConstraint++;
drh6f82e852015-06-06 20:12:09 +00001759 }
1760 codeApplyAffinity(pParse, regBase, nConstraint - bSeekPastNull, zStartAff);
drh0bf2ad62016-02-22 21:19:54 +00001761 if( pLoop->nSkip>0 && nConstraint==pLoop->nSkip ){
1762 /* The skip-scan logic inside the call to codeAllEqualityConstraints()
1763 ** above has already left the cursor sitting on the correct row,
1764 ** so no further seeking is needed */
1765 }else{
drhf7b0a5f2018-06-07 14:59:22 +00001766 if( pLoop->wsFlags & WHERE_IN_EARLYOUT ){
drh8c2b6d72018-06-05 20:45:20 +00001767 sqlite3VdbeAddOp1(v, OP_SeekHit, iIdxCur);
1768 }
dan15750a22019-08-16 21:07:19 +00001769 if( regBignull ){
drhec3dda52019-08-23 13:32:03 +00001770 sqlite3VdbeAddOp2(v, OP_Integer, 1, regBignull);
drha31d3552019-08-23 17:09:02 +00001771 VdbeComment((v, "NULL-scan pass ctr"));
dan15750a22019-08-16 21:07:19 +00001772 }
1773
drha6d2f8e2016-02-22 20:52:26 +00001774 op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev];
1775 assert( op!=0 );
1776 sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
1777 VdbeCoverage(v);
1778 VdbeCoverageIf(v, op==OP_Rewind); testcase( op==OP_Rewind );
1779 VdbeCoverageIf(v, op==OP_Last); testcase( op==OP_Last );
1780 VdbeCoverageIf(v, op==OP_SeekGT); testcase( op==OP_SeekGT );
1781 VdbeCoverageIf(v, op==OP_SeekGE); testcase( op==OP_SeekGE );
1782 VdbeCoverageIf(v, op==OP_SeekLE); testcase( op==OP_SeekLE );
1783 VdbeCoverageIf(v, op==OP_SeekLT); testcase( op==OP_SeekLT );
danddd74212019-08-02 18:43:59 +00001784
drh0086e072019-08-23 16:12:20 +00001785 assert( bSeekPastNull==0 || bStopAtNull==0 );
dan15750a22019-08-16 21:07:19 +00001786 if( regBignull ){
drh0086e072019-08-23 16:12:20 +00001787 assert( bSeekPastNull==1 || bStopAtNull==1 );
drh5f6a4ea2019-08-23 17:00:22 +00001788 assert( bSeekPastNull==!bStopAtNull );
drh0086e072019-08-23 16:12:20 +00001789 assert( bStopAtNull==startEq );
danddd74212019-08-02 18:43:59 +00001790 sqlite3VdbeAddOp2(v, OP_Goto, 0, sqlite3VdbeCurrentAddr(v)+2);
drh0086e072019-08-23 16:12:20 +00001791 op = aStartOp[(nConstraint>1)*4 + 2 + bRev];
1792 sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase,
1793 nConstraint-startEq);
1794 VdbeCoverage(v);
1795 VdbeCoverageIf(v, op==OP_Rewind); testcase( op==OP_Rewind );
1796 VdbeCoverageIf(v, op==OP_Last); testcase( op==OP_Last );
1797 VdbeCoverageIf(v, op==OP_SeekGE); testcase( op==OP_SeekGE );
1798 VdbeCoverageIf(v, op==OP_SeekLE); testcase( op==OP_SeekLE );
1799 assert( op==OP_Rewind || op==OP_Last || op==OP_SeekGE || op==OP_SeekLE);
danddd74212019-08-02 18:43:59 +00001800 }
drha6d2f8e2016-02-22 20:52:26 +00001801 }
drh0bf2ad62016-02-22 21:19:54 +00001802
drh6f82e852015-06-06 20:12:09 +00001803 /* Load the value for the inequality constraint at the end of the
1804 ** range (if any).
1805 */
1806 nConstraint = nEq;
1807 if( pRangeEnd ){
1808 Expr *pRight = pRangeEnd->pExpr->pRight;
dan71c57db2016-07-09 20:23:55 +00001809 codeExprOrVector(pParse, pRight, regBase+nEq, nTop);
drh6f82e852015-06-06 20:12:09 +00001810 whereLikeOptimizationStringFixup(v, pLevel, pRangeEnd);
1811 if( (pRangeEnd->wtFlags & TERM_VNULL)==0
1812 && sqlite3ExprCanBeNull(pRight)
1813 ){
1814 sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt);
1815 VdbeCoverage(v);
1816 }
drh0c36fca2016-08-26 18:17:08 +00001817 if( zEndAff ){
drhe3c6b612016-10-05 20:10:32 +00001818 updateRangeAffinityStr(pRight, nTop, zEndAff);
drh0c36fca2016-08-26 18:17:08 +00001819 codeApplyAffinity(pParse, regBase+nEq, nTop, zEndAff);
1820 }else{
1821 assert( pParse->db->mallocFailed );
1822 }
dan71c57db2016-07-09 20:23:55 +00001823 nConstraint += nTop;
drh6f82e852015-06-06 20:12:09 +00001824 testcase( pRangeEnd->wtFlags & TERM_VIRTUAL );
dan71c57db2016-07-09 20:23:55 +00001825
dan625015e2016-07-30 16:39:28 +00001826 if( sqlite3ExprIsVector(pRight)==0 ){
dan71c57db2016-07-09 20:23:55 +00001827 disableTerm(pLevel, pRangeEnd);
1828 }else{
1829 endEq = 1;
1830 }
drh6f82e852015-06-06 20:12:09 +00001831 }else if( bStopAtNull ){
dan15750a22019-08-16 21:07:19 +00001832 if( regBignull==0 ){
1833 sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
1834 endEq = 0;
1835 }
drh6f82e852015-06-06 20:12:09 +00001836 nConstraint++;
1837 }
1838 sqlite3DbFree(db, zStartAff);
danb7ca2172016-08-26 17:54:46 +00001839 sqlite3DbFree(db, zEndAff);
drh6f82e852015-06-06 20:12:09 +00001840
1841 /* Top of the loop body */
1842 pLevel->p2 = sqlite3VdbeCurrentAddr(v);
1843
1844 /* Check if the index cursor is past the end of the range. */
1845 if( nConstraint ){
dan15750a22019-08-16 21:07:19 +00001846 if( regBignull ){
drh5f6a4ea2019-08-23 17:00:22 +00001847 /* Except, skip the end-of-range check while doing the NULL-scan */
drhec3dda52019-08-23 13:32:03 +00001848 sqlite3VdbeAddOp2(v, OP_IfNot, regBignull, sqlite3VdbeCurrentAddr(v)+3);
drha31d3552019-08-23 17:09:02 +00001849 VdbeComment((v, "If NULL-scan 2nd pass"));
drh505ae9d2019-08-22 21:13:56 +00001850 VdbeCoverage(v);
dan15750a22019-08-16 21:07:19 +00001851 }
drh6f82e852015-06-06 20:12:09 +00001852 op = aEndOp[bRev*2 + endEq];
1853 sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
1854 testcase( op==OP_IdxGT ); VdbeCoverageIf(v, op==OP_IdxGT );
1855 testcase( op==OP_IdxGE ); VdbeCoverageIf(v, op==OP_IdxGE );
1856 testcase( op==OP_IdxLT ); VdbeCoverageIf(v, op==OP_IdxLT );
1857 testcase( op==OP_IdxLE ); VdbeCoverageIf(v, op==OP_IdxLE );
1858 }
dan15750a22019-08-16 21:07:19 +00001859 if( regBignull ){
drh5f6a4ea2019-08-23 17:00:22 +00001860 /* During a NULL-scan, check to see if we have reached the end of
1861 ** the NULLs */
1862 assert( bSeekPastNull==!bStopAtNull );
1863 assert( bSeekPastNull+bStopAtNull==1 );
1864 assert( nConstraint+bSeekPastNull>0 );
drhec3dda52019-08-23 13:32:03 +00001865 sqlite3VdbeAddOp2(v, OP_If, regBignull, sqlite3VdbeCurrentAddr(v)+2);
drha31d3552019-08-23 17:09:02 +00001866 VdbeComment((v, "If NULL-scan 1st pass"));
drh505ae9d2019-08-22 21:13:56 +00001867 VdbeCoverage(v);
drh5f6a4ea2019-08-23 17:00:22 +00001868 op = aEndOp[bRev*2 + bSeekPastNull];
1869 sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase,
1870 nConstraint+bSeekPastNull);
1871 testcase( op==OP_IdxGT ); VdbeCoverageIf(v, op==OP_IdxGT );
1872 testcase( op==OP_IdxGE ); VdbeCoverageIf(v, op==OP_IdxGE );
1873 testcase( op==OP_IdxLT ); VdbeCoverageIf(v, op==OP_IdxLT );
1874 testcase( op==OP_IdxLE ); VdbeCoverageIf(v, op==OP_IdxLE );
dan15750a22019-08-16 21:07:19 +00001875 }
drh6f82e852015-06-06 20:12:09 +00001876
drhf7b0a5f2018-06-07 14:59:22 +00001877 if( pLoop->wsFlags & WHERE_IN_EARLYOUT ){
drh8c2b6d72018-06-05 20:45:20 +00001878 sqlite3VdbeAddOp2(v, OP_SeekHit, iIdxCur, 1);
1879 }
1880
drh6f82e852015-06-06 20:12:09 +00001881 /* Seek the table cursor, if required */
drh47df8a22018-12-25 00:15:37 +00001882 omitTable = (pLoop->wsFlags & WHERE_IDX_ONLY)!=0
1883 && (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)==0;
drh6f82e852015-06-06 20:12:09 +00001884 if( omitTable ){
1885 /* pIdx is a covering index. No need to access the main table. */
1886 }else if( HasRowid(pIdx->pTable) ){
drh7a969842019-12-09 14:34:37 +00001887 if( (pWInfo->wctrlFlags & WHERE_SEEK_TABLE)
1888 || ( (pWInfo->wctrlFlags & WHERE_SEEK_UNIQ_TABLE)!=0
1889 && (pWInfo->eOnePass==ONEPASS_SINGLE || pLoop->nLTerm==0) )
1890 ){
drh784c1b92016-01-30 16:59:56 +00001891 iRowidReg = ++pParse->nMem;
1892 sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, iRowidReg);
danc6157e12015-09-14 09:23:47 +00001893 sqlite3VdbeAddOp3(v, OP_NotExists, iCur, 0, iRowidReg);
drh66336f32015-09-14 14:08:25 +00001894 VdbeCoverage(v);
danc6157e12015-09-14 09:23:47 +00001895 }else{
drh784c1b92016-01-30 16:59:56 +00001896 codeDeferredSeek(pWInfo, pIdx, iCur, iIdxCur);
danc6157e12015-09-14 09:23:47 +00001897 }
drh6f82e852015-06-06 20:12:09 +00001898 }else if( iCur!=iIdxCur ){
1899 Index *pPk = sqlite3PrimaryKeyIndex(pIdx->pTable);
1900 iRowidReg = sqlite3GetTempRange(pParse, pPk->nKeyCol);
1901 for(j=0; j<pPk->nKeyCol; j++){
drhb9bcf7c2019-10-19 13:29:10 +00001902 k = sqlite3TableColumnToIndex(pIdx, pPk->aiColumn[j]);
drh6f82e852015-06-06 20:12:09 +00001903 sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, k, iRowidReg+j);
1904 }
1905 sqlite3VdbeAddOp4Int(v, OP_NotFound, iCur, addrCont,
1906 iRowidReg, pPk->nKeyCol); VdbeCoverage(v);
1907 }
1908
drhdb535392019-11-03 00:07:41 +00001909 if( pLevel->iLeftJoin==0 ){
1910 /* If pIdx is an index on one or more expressions, then look through
1911 ** all the expressions in pWInfo and try to transform matching expressions
1912 ** into reference to index columns. Also attempt to translate references
1913 ** to virtual columns in the table into references to (stored) columns
1914 ** of the index.
1915 **
1916 ** Do not do this for the RHS of a LEFT JOIN. This is because the
1917 ** expression may be evaluated after OP_NullRow has been executed on
1918 ** the cursor. In this case it is important to do the full evaluation,
1919 ** as the result of the expression may not be NULL, even if all table
1920 ** column values are. https://www.sqlite.org/src/info/7fa8049685b50b5a
1921 **
1922 ** Also, do not do this when processing one index an a multi-index
1923 ** OR clause, since the transformation will become invalid once we
1924 ** move forward to the next index.
1925 ** https://sqlite.org/src/info/4e8e4857d32d401f
1926 */
1927 if( (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)==0 ){
1928 whereIndexExprTrans(pIdx, iCur, iIdxCur, pWInfo);
1929 }
1930
1931 /* If a partial index is driving the loop, try to eliminate WHERE clause
1932 ** terms from the query that must be true due to the WHERE clause of
1933 ** the partial index.
1934 **
1935 ** 2019-11-02 ticket 623eff57e76d45f6: This optimization does not work
1936 ** for a LEFT JOIN.
1937 */
1938 if( pIdx->pPartIdxWhere ){
1939 whereApplyPartialIndexConstraints(pIdx->pPartIdxWhere, iCur, pWC);
1940 }
1941 }else{
drhdb535392019-11-03 00:07:41 +00001942 testcase( pIdx->pPartIdxWhere );
drh06fc2452019-11-04 12:49:15 +00001943 /* The following assert() is not a requirement, merely an observation:
1944 ** The OR-optimization doesn't work for the right hand table of
1945 ** a LEFT JOIN: */
1946 assert( (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)==0 );
dan4da04f72018-04-24 14:05:14 +00001947 }
drhdb535392019-11-03 00:07:41 +00001948
dan71c57db2016-07-09 20:23:55 +00001949 /* Record the instruction used to terminate the loop. */
drh6f82e852015-06-06 20:12:09 +00001950 if( pLoop->wsFlags & WHERE_ONEROW ){
1951 pLevel->op = OP_Noop;
1952 }else if( bRev ){
1953 pLevel->op = OP_Prev;
1954 }else{
1955 pLevel->op = OP_Next;
1956 }
1957 pLevel->p1 = iIdxCur;
1958 pLevel->p3 = (pLoop->wsFlags&WHERE_UNQ_WANTED)!=0 ? 1:0;
1959 if( (pLoop->wsFlags & WHERE_CONSTRAINT)==0 ){
1960 pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
1961 }else{
1962 assert( pLevel->p5==0 );
1963 }
dan6f654a42017-04-28 19:59:55 +00001964 if( omitTable ) pIdx = 0;
drh6f82e852015-06-06 20:12:09 +00001965 }else
1966
1967#ifndef SQLITE_OMIT_OR_OPTIMIZATION
1968 if( pLoop->wsFlags & WHERE_MULTI_OR ){
1969 /* Case 5: Two or more separately indexed terms connected by OR
1970 **
1971 ** Example:
1972 **
1973 ** CREATE TABLE t1(a,b,c,d);
1974 ** CREATE INDEX i1 ON t1(a);
1975 ** CREATE INDEX i2 ON t1(b);
1976 ** CREATE INDEX i3 ON t1(c);
1977 **
1978 ** SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
1979 **
1980 ** In the example, there are three indexed terms connected by OR.
1981 ** The top of the loop looks like this:
1982 **
1983 ** Null 1 # Zero the rowset in reg 1
1984 **
1985 ** Then, for each indexed term, the following. The arguments to
1986 ** RowSetTest are such that the rowid of the current row is inserted
1987 ** into the RowSet. If it is already present, control skips the
1988 ** Gosub opcode and jumps straight to the code generated by WhereEnd().
1989 **
1990 ** sqlite3WhereBegin(<term>)
1991 ** RowSetTest # Insert rowid into rowset
1992 ** Gosub 2 A
1993 ** sqlite3WhereEnd()
1994 **
1995 ** Following the above, code to terminate the loop. Label A, the target
1996 ** of the Gosub above, jumps to the instruction right after the Goto.
1997 **
1998 ** Null 1 # Zero the rowset in reg 1
1999 ** Goto B # The loop is finished.
2000 **
2001 ** A: <loop body> # Return data, whatever.
2002 **
2003 ** Return 2 # Jump back to the Gosub
2004 **
2005 ** B: <after the loop>
2006 **
2007 ** Added 2014-05-26: If the table is a WITHOUT ROWID table, then
2008 ** use an ephemeral index instead of a RowSet to record the primary
2009 ** keys of the rows we have already seen.
2010 **
2011 */
2012 WhereClause *pOrWc; /* The OR-clause broken out into subterms */
2013 SrcList *pOrTab; /* Shortened table list or OR-clause generation */
2014 Index *pCov = 0; /* Potential covering index (or NULL) */
2015 int iCovCur = pParse->nTab++; /* Cursor used for index scans (if any) */
2016
2017 int regReturn = ++pParse->nMem; /* Register used with OP_Gosub */
2018 int regRowset = 0; /* Register for RowSet object */
2019 int regRowid = 0; /* Register holding rowid */
drhec4ccdb2018-12-29 02:26:59 +00002020 int iLoopBody = sqlite3VdbeMakeLabel(pParse);/* Start of loop body */
drh6f82e852015-06-06 20:12:09 +00002021 int iRetInit; /* Address of regReturn init */
2022 int untestedTerms = 0; /* Some terms not completely tested */
2023 int ii; /* Loop counter */
2024 u16 wctrlFlags; /* Flags for sub-WHERE clause */
2025 Expr *pAndExpr = 0; /* An ".. AND (...)" expression */
2026 Table *pTab = pTabItem->pTab;
dan145b4ea2016-07-29 18:12:12 +00002027
drh6f82e852015-06-06 20:12:09 +00002028 pTerm = pLoop->aLTerm[0];
2029 assert( pTerm!=0 );
2030 assert( pTerm->eOperator & WO_OR );
2031 assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
2032 pOrWc = &pTerm->u.pOrInfo->wc;
2033 pLevel->op = OP_Return;
2034 pLevel->p1 = regReturn;
2035
2036 /* Set up a new SrcList in pOrTab containing the table being scanned
2037 ** by this loop in the a[0] slot and all notReady tables in a[1..] slots.
2038 ** This becomes the SrcList in the recursive call to sqlite3WhereBegin().
2039 */
2040 if( pWInfo->nLevel>1 ){
2041 int nNotReady; /* The number of notReady tables */
2042 struct SrcList_item *origSrc; /* Original list of tables */
2043 nNotReady = pWInfo->nLevel - iLevel - 1;
2044 pOrTab = sqlite3StackAllocRaw(db,
2045 sizeof(*pOrTab)+ nNotReady*sizeof(pOrTab->a[0]));
2046 if( pOrTab==0 ) return notReady;
2047 pOrTab->nAlloc = (u8)(nNotReady + 1);
2048 pOrTab->nSrc = pOrTab->nAlloc;
2049 memcpy(pOrTab->a, pTabItem, sizeof(*pTabItem));
2050 origSrc = pWInfo->pTabList->a;
2051 for(k=1; k<=nNotReady; k++){
2052 memcpy(&pOrTab->a[k], &origSrc[pLevel[k].iFrom], sizeof(pOrTab->a[k]));
2053 }
2054 }else{
2055 pOrTab = pWInfo->pTabList;
2056 }
2057
2058 /* Initialize the rowset register to contain NULL. An SQL NULL is
2059 ** equivalent to an empty rowset. Or, create an ephemeral index
2060 ** capable of holding primary keys in the case of a WITHOUT ROWID.
2061 **
2062 ** Also initialize regReturn to contain the address of the instruction
2063 ** immediately following the OP_Return at the bottom of the loop. This
2064 ** is required in a few obscure LEFT JOIN cases where control jumps
2065 ** over the top of the loop into the body of it. In this case the
2066 ** correct response for the end-of-loop code (the OP_Return) is to
2067 ** fall through to the next instruction, just as an OP_Next does if
2068 ** called on an uninitialized cursor.
2069 */
2070 if( (pWInfo->wctrlFlags & WHERE_DUPLICATES_OK)==0 ){
2071 if( HasRowid(pTab) ){
2072 regRowset = ++pParse->nMem;
2073 sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset);
2074 }else{
2075 Index *pPk = sqlite3PrimaryKeyIndex(pTab);
2076 regRowset = pParse->nTab++;
2077 sqlite3VdbeAddOp2(v, OP_OpenEphemeral, regRowset, pPk->nKeyCol);
2078 sqlite3VdbeSetP4KeyInfo(pParse, pPk);
2079 }
2080 regRowid = ++pParse->nMem;
2081 }
2082 iRetInit = sqlite3VdbeAddOp2(v, OP_Integer, 0, regReturn);
2083
2084 /* If the original WHERE clause is z of the form: (x1 OR x2 OR ...) AND y
2085 ** Then for every term xN, evaluate as the subexpression: xN AND z
2086 ** That way, terms in y that are factored into the disjunction will
2087 ** be picked up by the recursive calls to sqlite3WhereBegin() below.
2088 **
2089 ** Actually, each subexpression is converted to "xN AND w" where w is
2090 ** the "interesting" terms of z - terms that did not originate in the
2091 ** ON or USING clause of a LEFT JOIN, and terms that are usable as
2092 ** indices.
2093 **
2094 ** This optimization also only applies if the (x1 OR x2 OR ...) term
2095 ** is not contained in the ON clause of a LEFT JOIN.
2096 ** See ticket http://www.sqlite.org/src/info/f2369304e4
2097 */
2098 if( pWC->nTerm>1 ){
2099 int iTerm;
2100 for(iTerm=0; iTerm<pWC->nTerm; iTerm++){
2101 Expr *pExpr = pWC->a[iTerm].pExpr;
2102 if( &pWC->a[iTerm] == pTerm ) continue;
drh3b83f0c2016-01-29 16:57:06 +00002103 testcase( pWC->a[iTerm].wtFlags & TERM_VIRTUAL );
2104 testcase( pWC->a[iTerm].wtFlags & TERM_CODED );
2105 if( (pWC->a[iTerm].wtFlags & (TERM_VIRTUAL|TERM_CODED))!=0 ) continue;
drh6f82e852015-06-06 20:12:09 +00002106 if( (pWC->a[iTerm].eOperator & WO_ALL)==0 ) continue;
2107 testcase( pWC->a[iTerm].wtFlags & TERM_ORINFO );
2108 pExpr = sqlite3ExprDup(db, pExpr, 0);
drhd5c851c2019-04-19 13:38:34 +00002109 pAndExpr = sqlite3ExprAnd(pParse, pAndExpr, pExpr);
drh6f82e852015-06-06 20:12:09 +00002110 }
2111 if( pAndExpr ){
drhf1722ba2019-04-05 20:56:46 +00002112 /* The extra 0x10000 bit on the opcode is masked off and does not
2113 ** become part of the new Expr.op. However, it does make the
2114 ** op==TK_AND comparison inside of sqlite3PExpr() false, and this
2115 ** prevents sqlite3PExpr() from implementing AND short-circuit
2116 ** optimization, which we do not want here. */
2117 pAndExpr = sqlite3PExpr(pParse, TK_AND|0x10000, 0, pAndExpr);
drh6f82e852015-06-06 20:12:09 +00002118 }
2119 }
2120
2121 /* Run a separate WHERE clause for each term of the OR clause. After
2122 ** eliminating duplicates from other WHERE clauses, the action for each
2123 ** sub-WHERE clause is to to invoke the main loop body as a subroutine.
2124 */
drhce943bc2016-05-19 18:56:33 +00002125 wctrlFlags = WHERE_OR_SUBCLAUSE | (pWInfo->wctrlFlags & WHERE_SEEK_TABLE);
drh5d72d922018-05-04 00:39:43 +00002126 ExplainQueryPlan((pParse, 1, "MULTI-INDEX OR"));
drh6f82e852015-06-06 20:12:09 +00002127 for(ii=0; ii<pOrWc->nTerm; ii++){
2128 WhereTerm *pOrTerm = &pOrWc->a[ii];
2129 if( pOrTerm->leftCursor==iCur || (pOrTerm->eOperator & WO_AND)!=0 ){
2130 WhereInfo *pSubWInfo; /* Info for single OR-term scan */
2131 Expr *pOrExpr = pOrTerm->pExpr; /* Current OR clause term */
drh728e0f92015-10-10 14:41:28 +00002132 int jmp1 = 0; /* Address of jump operation */
dan820fcd22018-04-24 18:53:24 +00002133 assert( (pTabItem[0].fg.jointype & JT_LEFT)==0
2134 || ExprHasProperty(pOrExpr, EP_FromJoin)
2135 );
2136 if( pAndExpr ){
drh6f82e852015-06-06 20:12:09 +00002137 pAndExpr->pLeft = pOrExpr;
2138 pOrExpr = pAndExpr;
2139 }
2140 /* Loop through table entries that match term pOrTerm. */
drhbd462bc2018-12-24 20:21:06 +00002141 ExplainQueryPlan((pParse, 1, "INDEX %d", ii+1));
drh6f82e852015-06-06 20:12:09 +00002142 WHERETRACE(0xffff, ("Subplan for OR-clause:\n"));
2143 pSubWInfo = sqlite3WhereBegin(pParse, pOrTab, pOrExpr, 0, 0,
2144 wctrlFlags, iCovCur);
2145 assert( pSubWInfo || pParse->nErr || db->mallocFailed );
2146 if( pSubWInfo ){
2147 WhereLoop *pSubLoop;
2148 int addrExplain = sqlite3WhereExplainOneScan(
drhe2188f02018-05-07 11:37:34 +00002149 pParse, pOrTab, &pSubWInfo->a[0], 0
drh6f82e852015-06-06 20:12:09 +00002150 );
2151 sqlite3WhereAddScanStatus(v, pOrTab, &pSubWInfo->a[0], addrExplain);
2152
2153 /* This is the sub-WHERE clause body. First skip over
2154 ** duplicate rows from prior sub-WHERE clauses, and record the
2155 ** rowid (or PRIMARY KEY) for the current row so that the same
2156 ** row will be skipped in subsequent sub-WHERE clauses.
2157 */
2158 if( (pWInfo->wctrlFlags & WHERE_DUPLICATES_OK)==0 ){
drh6f82e852015-06-06 20:12:09 +00002159 int iSet = ((ii==pOrWc->nTerm-1)?-1:ii);
2160 if( HasRowid(pTab) ){
drh6df9c4b2019-10-18 12:52:08 +00002161 sqlite3ExprCodeGetColumnOfTable(v, pTab, iCur, -1, regRowid);
drh728e0f92015-10-10 14:41:28 +00002162 jmp1 = sqlite3VdbeAddOp4Int(v, OP_RowSetTest, regRowset, 0,
drh8c607192018-08-04 15:53:55 +00002163 regRowid, iSet);
drh6f82e852015-06-06 20:12:09 +00002164 VdbeCoverage(v);
2165 }else{
2166 Index *pPk = sqlite3PrimaryKeyIndex(pTab);
2167 int nPk = pPk->nKeyCol;
2168 int iPk;
drh8c607192018-08-04 15:53:55 +00002169 int r;
drh6f82e852015-06-06 20:12:09 +00002170
2171 /* Read the PK into an array of temp registers. */
2172 r = sqlite3GetTempRange(pParse, nPk);
2173 for(iPk=0; iPk<nPk; iPk++){
2174 int iCol = pPk->aiColumn[iPk];
drh6df9c4b2019-10-18 12:52:08 +00002175 sqlite3ExprCodeGetColumnOfTable(v, pTab, iCur, iCol,r+iPk);
drh6f82e852015-06-06 20:12:09 +00002176 }
2177
2178 /* Check if the temp table already contains this key. If so,
2179 ** the row has already been included in the result set and
2180 ** can be ignored (by jumping past the Gosub below). Otherwise,
2181 ** insert the key into the temp table and proceed with processing
2182 ** the row.
2183 **
2184 ** Use some of the same optimizations as OP_RowSetTest: If iSet
2185 ** is zero, assume that the key cannot already be present in
2186 ** the temp table. And if iSet is -1, assume that there is no
2187 ** need to insert the key into the temp table, as it will never
2188 ** be tested for. */
2189 if( iSet ){
drh728e0f92015-10-10 14:41:28 +00002190 jmp1 = sqlite3VdbeAddOp4Int(v, OP_Found, regRowset, 0, r, nPk);
drh6f82e852015-06-06 20:12:09 +00002191 VdbeCoverage(v);
2192 }
2193 if( iSet>=0 ){
2194 sqlite3VdbeAddOp3(v, OP_MakeRecord, r, nPk, regRowid);
drh9b4eaeb2016-11-09 00:10:33 +00002195 sqlite3VdbeAddOp4Int(v, OP_IdxInsert, regRowset, regRowid,
2196 r, nPk);
drh6f82e852015-06-06 20:12:09 +00002197 if( iSet ) sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);
2198 }
2199
2200 /* Release the array of temp registers */
2201 sqlite3ReleaseTempRange(pParse, r, nPk);
2202 }
2203 }
2204
2205 /* Invoke the main loop body as a subroutine */
2206 sqlite3VdbeAddOp2(v, OP_Gosub, regReturn, iLoopBody);
2207
2208 /* Jump here (skipping the main loop body subroutine) if the
2209 ** current sub-WHERE row is a duplicate from prior sub-WHEREs. */
drh728e0f92015-10-10 14:41:28 +00002210 if( jmp1 ) sqlite3VdbeJumpHere(v, jmp1);
drh6f82e852015-06-06 20:12:09 +00002211
2212 /* The pSubWInfo->untestedTerms flag means that this OR term
2213 ** contained one or more AND term from a notReady table. The
2214 ** terms from the notReady table could not be tested and will
2215 ** need to be tested later.
2216 */
2217 if( pSubWInfo->untestedTerms ) untestedTerms = 1;
2218
2219 /* If all of the OR-connected terms are optimized using the same
2220 ** index, and the index is opened using the same cursor number
2221 ** by each call to sqlite3WhereBegin() made by this loop, it may
2222 ** be possible to use that index as a covering index.
2223 **
2224 ** If the call to sqlite3WhereBegin() above resulted in a scan that
2225 ** uses an index, and this is either the first OR-connected term
2226 ** processed or the index is the same as that used by all previous
2227 ** terms, set pCov to the candidate covering index. Otherwise, set
2228 ** pCov to NULL to indicate that no candidate covering index will
2229 ** be available.
2230 */
2231 pSubLoop = pSubWInfo->a[0].pWLoop;
2232 assert( (pSubLoop->wsFlags & WHERE_AUTO_INDEX)==0 );
2233 if( (pSubLoop->wsFlags & WHERE_INDEXED)!=0
2234 && (ii==0 || pSubLoop->u.btree.pIndex==pCov)
2235 && (HasRowid(pTab) || !IsPrimaryKeyIndex(pSubLoop->u.btree.pIndex))
2236 ){
2237 assert( pSubWInfo->a[0].iIdxCur==iCovCur );
2238 pCov = pSubLoop->u.btree.pIndex;
drh6f82e852015-06-06 20:12:09 +00002239 }else{
2240 pCov = 0;
2241 }
2242
2243 /* Finish the loop through table entries that match term pOrTerm. */
2244 sqlite3WhereEnd(pSubWInfo);
drhbd462bc2018-12-24 20:21:06 +00002245 ExplainQueryPlanPop(pParse);
drh6f82e852015-06-06 20:12:09 +00002246 }
2247 }
2248 }
drh5d72d922018-05-04 00:39:43 +00002249 ExplainQueryPlanPop(pParse);
drh6f82e852015-06-06 20:12:09 +00002250 pLevel->u.pCovidx = pCov;
2251 if( pCov ) pLevel->iIdxCur = iCovCur;
2252 if( pAndExpr ){
2253 pAndExpr->pLeft = 0;
2254 sqlite3ExprDelete(db, pAndExpr);
2255 }
2256 sqlite3VdbeChangeP1(v, iRetInit, sqlite3VdbeCurrentAddr(v));
drh076e85f2015-09-03 13:46:12 +00002257 sqlite3VdbeGoto(v, pLevel->addrBrk);
drh6f82e852015-06-06 20:12:09 +00002258 sqlite3VdbeResolveLabel(v, iLoopBody);
2259
drhdd2d9a32019-05-07 17:47:43 +00002260 if( pWInfo->nLevel>1 ){ sqlite3StackFree(db, pOrTab); }
drh6f82e852015-06-06 20:12:09 +00002261 if( !untestedTerms ) disableTerm(pLevel, pTerm);
2262 }else
2263#endif /* SQLITE_OMIT_OR_OPTIMIZATION */
2264
2265 {
2266 /* Case 6: There is no usable index. We must do a complete
2267 ** scan of the entire table.
2268 */
2269 static const u8 aStep[] = { OP_Next, OP_Prev };
2270 static const u8 aStart[] = { OP_Rewind, OP_Last };
2271 assert( bRev==0 || bRev==1 );
drh8a48b9c2015-08-19 15:20:00 +00002272 if( pTabItem->fg.isRecursive ){
drh6f82e852015-06-06 20:12:09 +00002273 /* Tables marked isRecursive have only a single row that is stored in
2274 ** a pseudo-cursor. No need to Rewind or Next such cursors. */
2275 pLevel->op = OP_Noop;
2276 }else{
danb324cf72016-06-17 14:33:32 +00002277 codeCursorHint(pTabItem, pWInfo, pLevel, 0);
drh6f82e852015-06-06 20:12:09 +00002278 pLevel->op = aStep[bRev];
2279 pLevel->p1 = iCur;
drh3a3b4202017-02-15 22:36:15 +00002280 pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrHalt);
drh6f82e852015-06-06 20:12:09 +00002281 VdbeCoverageIf(v, bRev==0);
2282 VdbeCoverageIf(v, bRev!=0);
2283 pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
2284 }
2285 }
2286
2287#ifdef SQLITE_ENABLE_STMT_SCANSTATUS
2288 pLevel->addrVisit = sqlite3VdbeCurrentAddr(v);
2289#endif
2290
2291 /* Insert code to test every subexpression that can be completely
2292 ** computed using the current set of tables.
dan6f654a42017-04-28 19:59:55 +00002293 **
danebc63012017-07-10 14:33:00 +00002294 ** This loop may run between one and three times, depending on the
2295 ** constraints to be generated. The value of stack variable iLoop
2296 ** determines the constraints coded by each iteration, as follows:
2297 **
2298 ** iLoop==1: Code only expressions that are entirely covered by pIdx.
2299 ** iLoop==2: Code remaining expressions that do not contain correlated
2300 ** sub-queries.
2301 ** iLoop==3: Code all remaining expressions.
2302 **
2303 ** An effort is made to skip unnecessary iterations of the loop.
drh6ab3eb52017-04-29 14:56:55 +00002304 */
danebc63012017-07-10 14:33:00 +00002305 iLoop = (pIdx ? 1 : 2);
drh6ab3eb52017-04-29 14:56:55 +00002306 do{
danebc63012017-07-10 14:33:00 +00002307 int iNext = 0; /* Next value for iLoop */
dan6f654a42017-04-28 19:59:55 +00002308 for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){
2309 Expr *pE;
2310 int skipLikeAddr = 0;
2311 testcase( pTerm->wtFlags & TERM_VIRTUAL );
2312 testcase( pTerm->wtFlags & TERM_CODED );
2313 if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
2314 if( (pTerm->prereqAll & pLevel->notReady)!=0 ){
2315 testcase( pWInfo->untestedTerms==0
2316 && (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)!=0 );
2317 pWInfo->untestedTerms = 1;
2318 continue;
2319 }
2320 pE = pTerm->pExpr;
2321 assert( pE!=0 );
dan820fcd22018-04-24 18:53:24 +00002322 if( (pTabItem->fg.jointype&JT_LEFT) && !ExprHasProperty(pE,EP_FromJoin) ){
dan6f654a42017-04-28 19:59:55 +00002323 continue;
2324 }
danebc63012017-07-10 14:33:00 +00002325
dan8674ec52017-07-10 14:39:42 +00002326 if( iLoop==1 && !sqlite3ExprCoveredByIndex(pE, pLevel->iTabCur, pIdx) ){
danebc63012017-07-10 14:33:00 +00002327 iNext = 2;
dan6f654a42017-04-28 19:59:55 +00002328 continue;
2329 }
dand3930b12017-07-10 15:17:30 +00002330 if( iLoop<3 && (pTerm->wtFlags & TERM_VARSELECT) ){
danebc63012017-07-10 14:33:00 +00002331 if( iNext==0 ) iNext = 3;
2332 continue;
2333 }
2334
drh4de33532018-04-02 00:16:36 +00002335 if( (pTerm->wtFlags & TERM_LIKECOND)!=0 ){
dan6f654a42017-04-28 19:59:55 +00002336 /* If the TERM_LIKECOND flag is set, that means that the range search
2337 ** is sufficient to guarantee that the LIKE operator is true, so we
2338 ** can skip the call to the like(A,B) function. But this only works
2339 ** for strings. So do not skip the call to the function on the pass
2340 ** that compares BLOBs. */
drh41d2e662015-12-01 21:23:07 +00002341#ifdef SQLITE_LIKE_DOESNT_MATCH_BLOBS
dan6f654a42017-04-28 19:59:55 +00002342 continue;
drh41d2e662015-12-01 21:23:07 +00002343#else
dan6f654a42017-04-28 19:59:55 +00002344 u32 x = pLevel->iLikeRepCntr;
drh4de33532018-04-02 00:16:36 +00002345 if( x>0 ){
2346 skipLikeAddr = sqlite3VdbeAddOp1(v, (x&1)?OP_IfNot:OP_If,(int)(x>>1));
drh6f883592019-03-30 20:37:04 +00002347 VdbeCoverageIf(v, (x&1)==1);
2348 VdbeCoverageIf(v, (x&1)==0);
drh4de33532018-04-02 00:16:36 +00002349 }
drh41d2e662015-12-01 21:23:07 +00002350#endif
dan6f654a42017-04-28 19:59:55 +00002351 }
drh66a0bf32017-07-10 16:38:14 +00002352#ifdef WHERETRACE_ENABLED /* 0xffff */
2353 if( sqlite3WhereTrace ){
2354 VdbeNoopComment((v, "WhereTerm[%d] (%p) priority=%d",
2355 pWC->nTerm-j, pTerm, iLoop));
2356 }
drh118efd12019-12-28 14:07:22 +00002357 if( sqlite3WhereTrace & 0x800 ){
2358 sqlite3DebugPrintf("Coding auxiliary constraint:\n");
2359 sqlite3WhereTermPrint(pTerm, pWC->nTerm-j);
2360 }
drh66a0bf32017-07-10 16:38:14 +00002361#endif
dan6f654a42017-04-28 19:59:55 +00002362 sqlite3ExprIfFalse(pParse, pE, addrCont, SQLITE_JUMPIFNULL);
2363 if( skipLikeAddr ) sqlite3VdbeJumpHere(v, skipLikeAddr);
2364 pTerm->wtFlags |= TERM_CODED;
drh6f82e852015-06-06 20:12:09 +00002365 }
danebc63012017-07-10 14:33:00 +00002366 iLoop = iNext;
2367 }while( iLoop>0 );
drh6f82e852015-06-06 20:12:09 +00002368
2369 /* Insert code to test for implied constraints based on transitivity
2370 ** of the "==" operator.
2371 **
2372 ** Example: If the WHERE clause contains "t1.a=t2.b" and "t2.b=123"
2373 ** and we are coding the t1 loop and the t2 loop has not yet coded,
2374 ** then we cannot use the "t1.a=t2.b" constraint, but we can code
2375 ** the implied "t1.a=123" constraint.
2376 */
2377 for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){
drhcb43a932016-10-03 01:21:51 +00002378 Expr *pE, sEAlt;
drh6f82e852015-06-06 20:12:09 +00002379 WhereTerm *pAlt;
2380 if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
2381 if( (pTerm->eOperator & (WO_EQ|WO_IS))==0 ) continue;
2382 if( (pTerm->eOperator & WO_EQUIV)==0 ) continue;
2383 if( pTerm->leftCursor!=iCur ) continue;
drha4b2df52019-12-28 16:20:23 +00002384 if( pTabItem->fg.jointype & JT_LEFT ) continue;
drh6f82e852015-06-06 20:12:09 +00002385 pE = pTerm->pExpr;
drh118efd12019-12-28 14:07:22 +00002386#ifdef WHERETRACE_ENABLED /* 0x800 */
2387 if( sqlite3WhereTrace & 0x800 ){
2388 sqlite3DebugPrintf("Coding transitive constraint:\n");
2389 sqlite3WhereTermPrint(pTerm, pWC->nTerm-j);
2390 }
2391#endif
drhf1bb31e2019-12-28 14:33:26 +00002392 assert( !ExprHasProperty(pE, EP_FromJoin) );
drh6f82e852015-06-06 20:12:09 +00002393 assert( (pTerm->prereqRight & pLevel->notReady)!=0 );
2394 pAlt = sqlite3WhereFindTerm(pWC, iCur, pTerm->u.leftColumn, notReady,
2395 WO_EQ|WO_IN|WO_IS, 0);
2396 if( pAlt==0 ) continue;
2397 if( pAlt->wtFlags & (TERM_CODED) ) continue;
dana916b572018-01-23 16:38:57 +00002398 if( (pAlt->eOperator & WO_IN)
2399 && (pAlt->pExpr->flags & EP_xIsSelect)
drha599e152018-12-24 14:30:11 +00002400 && (pAlt->pExpr->x.pSelect->pEList->nExpr>1)
dana916b572018-01-23 16:38:57 +00002401 ){
2402 continue;
2403 }
drh6f82e852015-06-06 20:12:09 +00002404 testcase( pAlt->eOperator & WO_EQ );
2405 testcase( pAlt->eOperator & WO_IS );
2406 testcase( pAlt->eOperator & WO_IN );
2407 VdbeModuleComment((v, "begin transitive constraint"));
drhcb43a932016-10-03 01:21:51 +00002408 sEAlt = *pAlt->pExpr;
2409 sEAlt.pLeft = pE->pLeft;
2410 sqlite3ExprIfFalse(pParse, &sEAlt, addrCont, SQLITE_JUMPIFNULL);
drh6f82e852015-06-06 20:12:09 +00002411 }
2412
2413 /* For a LEFT OUTER JOIN, generate code that will record the fact that
2414 ** at least one row of the right table has matched the left table.
2415 */
2416 if( pLevel->iLeftJoin ){
2417 pLevel->addrFirst = sqlite3VdbeCurrentAddr(v);
2418 sqlite3VdbeAddOp2(v, OP_Integer, 1, pLevel->iLeftJoin);
2419 VdbeComment((v, "record LEFT JOIN hit"));
drh6f82e852015-06-06 20:12:09 +00002420 for(pTerm=pWC->a, j=0; j<pWC->nTerm; j++, pTerm++){
2421 testcase( pTerm->wtFlags & TERM_VIRTUAL );
2422 testcase( pTerm->wtFlags & TERM_CODED );
2423 if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
2424 if( (pTerm->prereqAll & pLevel->notReady)!=0 ){
2425 assert( pWInfo->untestedTerms );
2426 continue;
2427 }
2428 assert( pTerm->pExpr );
2429 sqlite3ExprIfFalse(pParse, pTerm->pExpr, addrCont, SQLITE_JUMPIFNULL);
2430 pTerm->wtFlags |= TERM_CODED;
2431 }
2432 }
2433
drh118efd12019-12-28 14:07:22 +00002434#if WHERETRACE_ENABLED /* 0x20800 */
2435 if( sqlite3WhereTrace & 0x20000 ){
drhf1bb31e2019-12-28 14:33:26 +00002436 sqlite3DebugPrintf("All WHERE-clause terms after coding level %d:\n",
2437 iLevel);
drh118efd12019-12-28 14:07:22 +00002438 sqlite3WhereClausePrint(pWC);
2439 }
2440 if( sqlite3WhereTrace & 0x800 ){
2441 sqlite3DebugPrintf("End Coding level %d: notReady=%llx\n",
2442 iLevel, (u64)pLevel->notReady);
2443 }
2444#endif
drh6f82e852015-06-06 20:12:09 +00002445 return pLevel->notReady;
2446}