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