| blob | a620a5ac0653024cd2fa8b7713a10d7d8bd62747 |
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 */
23 #ifndef SQLITE_OMIT_EXPLAIN
25 /*
26 ** Return the name of the i-th column of the pIdx index.
27 */
33 }
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 */
50 ){
60 }
69 }
71 }
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 */
99 }
105 }
108 }
110 }
112 /*
113 ** This function is a no-op unless currently processing an EXPLAIN QUERY PLAN
114 ** command, or if stmt_scanstatus_v2() stats are enabled, or if SQLITE_DEBUG
115 ** was defined at compile-time. If it is not a no-op, a single OP_Explain
116 ** opcode 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 */
125 u16 wctrlFlags /* Flags passed to sqlite3WhereBegin() */
126 ){
128 #if !defined(SQLITE_DEBUG)
130 #endif
131 {
163 }
172 }
177 }
184 #else
186 #endif
198 }
200 }
201 #ifndef SQLITE_OMIT_VIRTUALTABLE
205 }
206 #endif
209 }
210 #ifdef SQLITE_EXPLAIN_ESTIMATED_ROWS
216 }
217 #endif
222 }
224 }
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 */
240 ){
261 }
267 }
268 }
276 }
279 #ifdef SQLITE_ENABLE_STMT_SCANSTATUS
280 /*
281 ** Configure the VM passed as the first argument with an
282 ** sqlite3_stmt_scanstatus() entry corresponding to the scan used to
283 ** implement level pLvl. Argument pSrclist is a pointer to the FROM
284 ** clause that the scan reads data from.
285 **
286 ** If argument addrExplain is not 0, it must be the address of an
287 ** OP_Explain instruction that describes the same loop.
288 */
294 ){
306 }
309 );
314 }
317 }
324 }
325 }
326 }
327 #endif
330 /*
331 ** Disable a term in the WHERE clause. Except, do not disable the term
332 ** if it controls a LEFT OUTER JOIN and it did not originate in the ON
333 ** or USING clause of that join.
334 **
335 ** Consider the term t2.z='ok' in the following queries:
336 **
337 ** (1) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok'
338 ** (2) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok'
339 ** (3) SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok'
340 **
341 ** The t2.z='ok' is disabled in the in (2) because it originates
342 ** in the ON clause. The term is disabled in (3) because it is not part
343 ** of a LEFT OUTER JOIN. In (1), the term is not disabled.
344 **
345 ** Disabling a term causes that term to not be tested in the inner loop
346 ** of the join. Disabling is an optimization. When terms are satisfied
347 ** by indices, we disable them to prevent redundant tests in the inner
348 ** loop. We would get the correct results if nothing were ever disabled,
349 ** but joins might run a little slower. The trick is to disable as much
350 ** as we can without disabling too much. If we disabled in (1), we'd get
351 ** the wrong answer. See ticket #813.
352 **
353 ** If all the children of a term are disabled, then that term is also
354 ** automatically disabled. In this way, terms get disabled if derived
355 ** virtual terms are tested first. For example:
356 **
357 ** x GLOB 'abc*' AND x>='abc' AND x<'acd'
358 ** \___________/ \______/ \_____/
359 ** parent child1 child2
360 **
361 ** Only the parent term was in the original WHERE clause. The child1
362 ** and child2 terms were added by the LIKE optimization. If both of
363 ** the virtual child terms are valid, then testing of the parent can be
364 ** skipped.
365 **
366 ** Usually the parent term is marked as TERM_CODED. But if the parent
367 ** term was originally TERM_LIKE, then the parent gets TERM_LIKECOND instead.
368 ** The TERM_LIKECOND marking indicates that the term should be coded inside
369 ** a conditional such that is only evaluated on the second pass of a
370 ** LIKE-optimization loop, when scanning BLOBs instead of strings.
371 */
378 ){
383 }
384 #ifdef WHERETRACE_ENABLED
388 }
389 #endif
395 nLoop++;
396 }
397 }
399 /*
400 ** Code an OP_Affinity opcode to apply the column affinity string zAff
401 ** to the n registers starting at base.
402 **
403 ** As an optimization, SQLITE_AFF_BLOB and SQLITE_AFF_NONE entries (which
404 ** are no-ops) at the beginning and end of zAff are ignored. If all entries
405 ** in zAff are SQLITE_AFF_BLOB or SQLITE_AFF_NONE, then no code gets generated.
406 **
407 ** This routine makes its own copy of zAff so that the caller is free
408 ** to modify zAff after this routine returns.
409 */
415 }
418 /* Adjust base and n to skip over SQLITE_AFF_BLOB and SQLITE_AFF_NONE
419 ** entries at the beginning and end of the affinity string.
420 */
423 n--;
424 base++;
425 zAff++;
426 }
428 n--;
429 }
431 /* Code the OP_Affinity opcode if there is anything left to do. */
434 }
435 }
437 /*
438 ** Expression pRight, which is the RHS of a comparison operation, is
439 ** either a vector of n elements or, if n==1, a scalar expression.
440 ** Before the comparison operation, affinity zAff is to be applied
441 ** to the pRight values. This function modifies characters within the
442 ** affinity string to SQLITE_AFF_BLOB if either:
443 **
444 ** * the comparison will be performed with no affinity, or
445 ** * the affinity change in zAff is guaranteed not to change the value.
446 */
451 ){
457 ){
459 }
460 }
461 }
464 /*
465 ** pX is an expression of the form: (vector) IN (SELECT ...)
466 ** In other words, it is a vector IN operator with a SELECT clause on the
467 ** LHS. But not all terms in the vector are indexable and the terms might
468 ** not be in the correct order for indexing.
469 **
470 ** This routine makes a copy of the input pX expression and then adjusts
471 ** the vector on the LHS with corresponding changes to the SELECT so that
472 ** the vector contains only index terms and those terms are in the correct
473 ** order. The modified IN expression is returned. The caller is responsible
474 ** for deleting the returned expression.
475 **
476 ** Example:
477 **
478 ** CREATE TABLE t1(a,b,c,d,e,f);
479 ** CREATE INDEX t1x1 ON t1(e,c);
480 ** SELECT * FROM t1 WHERE (a,b,c,d,e) IN (SELECT v,w,x,y,z FROM t2)
481 ** \_______________________________________/
482 ** The pX expression
483 **
484 ** Since only columns e and c can be used with the index, in that order,
485 ** the modified IN expression that is returned will be:
486 **
487 ** (e,c) IN (SELECT z,x FROM t2)
488 **
489 ** The reduced pX is different from the original (obviously) and thus is
490 ** only used for indexing, to improve performance. The original unaltered
491 ** IN expression must also be run on each output row for correctness.
492 */
498 ){
517 }
530 }
531 }
532 }
537 }
540 /* Take care here not to generate a TK_VECTOR containing only a
541 ** single value. Since the parser never creates such a vector, some
542 ** of the subroutines do not handle this case. */
547 }
549 /* If the SELECT statement has an ORDER BY clause, zero the
550 ** iOrderByCol variables. These are set to non-zero when an
551 ** ORDER BY term exactly matches one of the terms of the
552 ** result-set. Since the result-set of the SELECT statement may
553 ** have been modified or reordered, these variables are no longer
554 ** set correctly. Since setting them is just an optimization,
555 ** it's easiest just to zero them here. */
559 }
560 }
562 #if 0
567 #endif
568 }
569 }
571 }
574 /*
575 ** Generate code for a single equality term of the WHERE clause. An equality
576 ** term can be either X=expr or X IN (...). pTerm is the term to be
577 ** coded.
578 **
579 ** The current value for the constraint is left in a register, the index
580 ** of which is returned. An attempt is made store the result in iTarget but
581 ** this is only guaranteed for TK_ISNULL and TK_IN constraints. If the
582 ** constraint is a TK_EQ or TK_IS, then the current value might be left in
583 ** some other register and it is the caller's responsibility to compensate.
584 **
585 ** For a constraint of the form X=expr, the expression is evaluated in
586 ** straight-line code. For constraints of the form X IN (...)
587 ** this routine sets up a loop that will iterate over all values of X.
588 */
596 ){
608 #ifndef SQLITE_OMIT_SUBQUERY
621 ){
625 }
633 }
634 }
638 }
652 }
658 }
660 }
665 }
674 }
677 }
697 }
707 }
710 }
711 pIn++;
712 }
713 }
719 ){
721 }
724 }
726 #endif
727 }
729 /* As an optimization, try to disable the WHERE clause term that is
730 ** driving the index as it will always be true. The correct answer is
731 ** obtained regardless, but we might get the answer with fewer CPU cycles
732 ** by omitting the term.
733 **
734 ** But do not disable the term unless we are certain that the term is
735 ** not a transitive constraint. For an example of where that does not
736 ** work, see https://sqlite.org/forum/forumpost/eb8613976a (2021-05-04)
737 */
740 ){
742 }
745 }
747 /*
748 ** Generate code that will evaluate all == and IN constraints for an
749 ** index scan.
750 **
751 ** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c).
752 ** Suppose the WHERE clause is this: a==5 AND b IN (1,2,3) AND c>5 AND c<10
753 ** The index has as many as three equality constraints, but in this
754 ** example, the third "c" value is an inequality. So only two
755 ** constraints are coded. This routine will generate code to evaluate
756 ** a==5 and b IN (1,2,3). The current values for a and b will be stored
757 ** in consecutive registers and the index of the first register is returned.
758 **
759 ** In the example above nEq==2. But this subroutine works for any value
760 ** of nEq including 0. If nEq==0, this routine is nearly a no-op.
761 ** The only thing it does is allocate the pLevel->iMem memory cell and
762 ** compute the affinity string.
763 **
764 ** The nExtraReg parameter is 0 or 1. It is 0 if all WHERE clause constraints
765 ** are == or IN and are covered by the nEq. nExtraReg is 1 if there is
766 ** an inequality constraint (such as the "c>=5 AND c<10" in the example) that
767 ** occurs after the nEq quality constraints.
768 **
769 ** This routine allocates a range of nEq+nExtraReg memory cells and returns
770 ** the index of the first memory cell in that range. The code that
771 ** calls this routine will use that memory range to store keys for
772 ** start and termination conditions of the loop.
773 ** key value of the loop. If one or more IN operators appear, then
774 ** this routine allocates an additional nEq memory cells for internal
775 ** use.
776 **
777 ** Before returning, *pzAff is set to point to a buffer containing a
778 ** copy of the column affinity string of the index allocated using
779 ** sqlite3DbMalloc(). Except, entries in the copy of the string associated
780 ** with equality constraints that use BLOB or NONE affinity are set to
781 ** SQLITE_AFF_BLOB. This is to deal with SQL such as the following:
782 **
783 ** CREATE TABLE t1(a TEXT PRIMARY KEY, b);
784 ** SELECT ... FROM t1 AS t2, t1 WHERE t1.a = t2.b;
785 **
786 ** In the example above, the index on t1(a) has TEXT affinity. But since
787 ** the right hand side of the equality constraint (t2.b) has BLOB/NONE affinity,
788 ** no conversion should be attempted before using a t2.b value as part of
789 ** a key to search the index. Hence the first byte in the returned affinity
790 ** string in this example would be set to SQLITE_AFF_BLOB.
791 */
798 ){
810 /* This module is only called on query plans that use an index. */
818 /* Figure out how many memory cells we will need then allocate them.
819 */
845 }
846 }
848 /* Evaluate the equality constraints
849 */
855 /* The following testcase is true for indices with redundant columns.
856 ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */
866 }
867 }
870 /* No affinity ever needs to be (or should be) applied to a value
871 ** from the RHS of an "? IN (SELECT ...)" expression. The
872 ** sqlite3FindInIndex() routine has already ensured that the
873 ** affinity of the comparison has been applied to the value. */
875 }
881 }
886 }
889 }
890 }
891 }
892 }
895 }
897 #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
898 /*
899 ** If the most recently coded instruction is a constant range constraint
900 ** (a string literal) that originated from the LIKE optimization, then
901 ** set P3 and P5 on the OP_String opcode so that the string will be cast
902 ** to a BLOB at appropriate times.
903 **
904 ** The LIKE optimization trys to evaluate "x LIKE 'abc%'" as a range
905 ** expression: "x>='ABC' AND x<'abd'". But this requires that the range
906 ** scan loop run twice, once for strings and a second time for BLOBs.
907 ** The OP_String opcodes on the second pass convert the upper and lower
908 ** bound string constants to blobs. This routine makes the necessary changes
909 ** to the OP_String opcodes for that to happen.
910 **
911 ** Except, of course, if SQLITE_LIKE_DOESNT_MATCH_BLOBS is defined, then
912 ** only the one pass through the string space is required, so this routine
913 ** becomes a no-op.
914 */
919 ){
929 }
930 }
931 #else
932 # define whereLikeOptimizationStringFixup(A,B,C)
933 #endif
935 #ifdef SQLITE_ENABLE_CURSOR_HINTS
936 /*
937 ** Information is passed from codeCursorHint() down to individual nodes of
938 ** the expression tree (by sqlite3WalkExpr()) using an instance of this
939 ** structure.
940 */
945 };
947 /*
948 ** This function is called for every node of an expression that is a candidate
949 ** for a cursor hint on an index cursor. For TK_COLUMN nodes that reference
950 ** the table CCurHint.iTabCur, verify that the same column can be
951 ** accessed through the index. If it cannot, then set pWalker->eCode to 1.
952 */
959 ){
961 }
963 }
965 /*
966 ** Test whether or not expression pExpr, which was part of a WHERE clause,
967 ** should be included in the cursor-hint for a table that is on the rhs
968 ** of a LEFT JOIN. Set Walker.eCode to non-zero before returning if the
969 ** expression is not suitable.
970 **
971 ** An expression is unsuitable if it might evaluate to non NULL even if
972 ** a TK_COLUMN node that does affect the value of the expression is set
973 ** to NULL. For example:
974 **
975 ** col IS NULL
976 ** col IS NOT NULL
977 ** coalesce(col, 1)
978 ** CASE WHEN col THEN 0 ELSE 1 END
979 */
984 ){
991 }
992 }
995 }
998 /*
999 ** This function is called on every node of an expression tree used as an
1000 ** argument to the OP_CursorHint instruction. If the node is a TK_COLUMN
1001 ** that accesses any table other than the one identified by
1002 ** CCurHint.iTabCur, then do the following:
1003 **
1004 ** 1) allocate a register and code an OP_Column instruction to read
1005 ** the specified column into the new register, and
1006 **
1007 ** 2) transform the expression node to a TK_REGISTER node that reads
1008 ** from the newly populated register.
1009 **
1010 ** Also, if the node is a TK_COLUMN that does access the table identified
1011 ** by pCCurHint.iTabCur, and an index is being used (which we will
1012 ** know because CCurHint.pIdx!=0) then transform the TK_COLUMN into
1013 ** an access of the index rather than the original table.
1014 */
1029 }
1037 /* Do not walk disabled expressions. tag-20230504-1 */
1039 }
1041 }
1043 /*
1044 ** Insert an OP_CursorHint instruction if it is appropriate to do so.
1045 */
1051 ){
1062 Walker sWalker;
1079 /* Any terms specified as part of the ON(...) clause for any LEFT
1080 ** JOIN for which the current table is not the rhs are omitted
1081 ** from the cursor-hint.
1082 **
1083 ** If this table is the rhs of a LEFT JOIN, "IS" or "IS NULL" terms
1084 ** that were specified as part of the WHERE clause must be excluded.
1085 ** This is to address the following:
1086 **
1087 ** SELECT ... t1 LEFT JOIN t2 ON (t1.a=t2.b) WHERE t2.c IS NULL;
1088 **
1089 ** Say there is a single row in t2 that matches (t1.a=t2.b), but its
1090 ** t2.c values is not NULL. If the (t2.c IS NULL) constraint is
1091 ** pushed down to the cursor, this row is filtered out, causing
1092 ** SQLite to synthesize a row of NULL values. Which does match the
1093 ** WHERE clause, and so the query returns a row. Which is incorrect.
1094 **
1095 ** For the same reason, WHERE terms such as:
1096 **
1097 ** WHERE 1 = (t2.c IS NULL)
1098 **
1099 ** are also excluded. See codeCursorHintIsOrFunction() for details.
1100 */
1105 ){
1110 }
1113 }
1115 /* All terms in pWLoop->aLTerm[] except pEndRange are used to initialize
1116 ** the cursor. These terms are not needed as hints for a pure range
1117 ** scan (that has no == terms) so omit them. */
1121 }
1123 /* No subqueries or non-deterministic functions allowed */
1126 /* For an index scan, make sure referenced columns are actually in
1127 ** the index. */
1133 }
1135 /* If we survive all prior tests, that means this term is worth hinting */
1137 }
1144 }
1145 }
1146 #else
1150 /*
1151 ** Cursor iCur is open on an intkey b-tree (a table). Register iRowid contains
1152 ** a rowid value just read from cursor iIdxCur, open on index pIdx. This
1153 ** function generates code to do a deferred seek of cursor iCur to the
1154 ** rowid stored in register iRowid.
1155 **
1156 ** Normally, this is just:
1157 **
1158 ** OP_DeferredSeek $iCur $iRowid
1159 **
1160 ** Which causes a seek on $iCur to the row with rowid $iRowid.
1161 **
1162 ** However, if the scan currently being coded is a branch of an OR-loop and
1163 ** the statement currently being coded is a SELECT, then additional information
1164 ** is added that might allow OP_Column to omit the seek and instead do its
1165 ** lookup on the index, thus avoiding an expensive seek operation. To
1166 ** enable this optimization, the P3 of OP_DeferredSeek is set to iIdxCur
1167 ** and P4 is set to an array of integers containing one entry for each column
1168 ** in the table. For each table column, if the column is the i'th
1169 ** column of the index, then the corresponding array entry is set to (i+1).
1170 ** If the column does not appear in the index at all, the array entry is set
1171 ** to 0. The OP_Column opcode can check this array to see if the column it
1172 ** wants is in the index and if it is, it will substitute the index cursor
1173 ** and column number and continue with those new values, rather than seeking
1174 ** the table cursor.
1175 */
1181 ){
1192 ){
1205 }
1207 }
1208 }
1209 }
1211 /*
1212 ** If the expression passed as the second argument is a vector, generate
1213 ** code to write the first nReg elements of the vector into an array
1214 ** of registers starting with iReg.
1215 **
1216 ** If the expression is not a vector, then nReg must be passed 1. In
1217 ** this case, generate code to evaluate the expression and leave the
1218 ** result in register iReg.
1219 */
1223 #ifndef SQLITE_OMIT_SUBQUERY
1231 #endif
1232 {
1240 }
1241 }
1245 }
1246 }
1248 /*
1249 ** The pTruth expression is always true because it is the WHERE clause
1250 ** a partial index that is driving a query loop. Look through all of the
1251 ** WHERE clause terms on the query, and if any of those terms must be
1252 ** true because pTruth is true, then mark those WHERE clause terms as
1253 ** coded.
1254 */
1258 WhereClause *pWC
1259 ){
1265 }
1272 }
1273 }
1274 }
1276 /*
1277 ** This routine is called right after An OP_Filter has been generated and
1278 ** before the corresponding index search has been performed. This routine
1279 ** checks to see if there are additional Bloom filters in inner loops that
1280 ** can be checked prior to doing the index lookup. If there are available
1281 ** inner-loop Bloom filters, then evaluate those filters now, before the
1282 ** index lookup. The idea is that a Bloom filter check is way faster than
1283 ** an index lookup, and the Bloom filter might return false, meaning that
1284 ** the index lookup can be skipped.
1285 **
1286 ** We know that an inner loop uses a Bloom filter because it has the
1287 ** WhereLevel.regFilter set. If an inner-loop Bloom filter is checked,
1288 ** then clear the WhereLevel.regFilter value to prevent the Bloom filter
1289 ** from being checked a second time when the inner loop is evaluated.
1290 */
1296 Bitmask notReady /* Loops that are not ready */
1297 ){
1303 /* ,--- Because sqlite3ConstructBloomFilter() has will not have set
1304 ** vvvvv--' pLevel->regFilter if this were true. */
1334 }
1337 }
1338 }
1340 /*
1341 ** Loop pLoop is a WHERE_INDEXED level that uses at least one IN(...)
1342 ** operator. Return true if level pLoop is guaranteed to visit only one
1343 ** row for each key generated for the index.
1344 */
1349 ){
1354 }
1355 }
1357 }
1359 }
1361 /*
1362 ** Generate code for the start of the iLevel-th loop in the WHERE clause
1363 ** implementation described by pWInfo.
1364 */
1371 Bitmask notReady /* Which tables are currently available */
1372 ){
1404 }
1405 }
1410 }
1413 }
1414 #endif
1416 /* Create labels for the "break" and "continue" instructions
1417 ** for the current loop. Jump to addrBrk to break out of a loop.
1418 ** Jump to cont to go immediately to the next iteration of the
1419 ** loop.
1420 **
1421 ** When there is an IN operator, we also have a "addrNxt" label that
1422 ** means to continue with the next IN value combination. When
1423 ** there are no IN operators in the constraints, the "addrNxt" label
1424 ** is the same as "addrBrk".
1425 */
1429 /* If this is the right table of a LEFT OUTER JOIN, allocate and
1430 ** initialize a memory cell that records if this table matches any
1431 ** row of the left table of the join.
1432 */
1435 );
1440 }
1442 /* Compute a safe address to jump to if we discover that the table for
1443 ** this loop is empty and can never contribute content. */
1447 }
1450 /* Special case of a FROM clause subquery implemented as a co-routine */
1460 #ifndef SQLITE_OMIT_VIRTUALTABLE
1462 /* Case 1: The table is a virtual-table. Use the VFilter and VNext
1463 ** to access the data.
1464 */
1484 }
1490 ){
1496 }
1497 }
1498 }
1506 /* An OOM inside of AddOp4(OP_VFilter) instruction above might have freed
1507 ** the u.vtab.idxStr. NULL it out to prevent a use-after-free */
1519 }
1523 ){
1529 /* Reload the constraint value into reg[iReg+j+2]. The same value
1530 ** was loaded into the same register prior to the OP_VFilter, but
1531 ** the xFilter implementation might have changed the datatype or
1532 ** encoding of the value in the register, so it *must* be reloaded.
1533 */
1538 ){
1542 }
1543 }
1545 /* Generate code that will continue to the next row if
1546 ** the IN constraint is not satisfied
1547 */
1560 }
1566 );
1567 }
1569 }
1571 }
1572 }
1574 /* These registers need to be preserved in case there is an IN operator
1575 ** loop. So we could deallocate the registers here (and potentially
1576 ** reuse them later) if (pLoop->wsFlags & WHERE_IN_ABLE)==0. But it seems
1577 ** simpler and safer to simply not reuse the registers.
1578 **
1579 ** sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2);
1580 */
1586 ){
1587 /* Case 2: We can directly reference a single row using an
1588 ** equality comparison against the ROWID field. Or
1589 ** we reference multiple rows using a "rowid IN (...)"
1590 ** construct.
1591 */
1608 }
1614 ){
1615 /* Case 3: We have an inequality comparison against the ROWID field.
1616 */
1631 }
1638 /* The following constant maps TK_xx codes into corresponding
1639 ** seek opcodes. It depends on a particular ordering of TK_xx
1640 */
1645 /* TK_GE */ OP_SeekGE
1646 };
1672 }
1684 }
1696 ){
1700 }
1703 }
1704 }
1719 }
1721 /* Case 4: A scan using an index.
1722 **
1723 ** The WHERE clause may contain zero or more equality
1724 ** terms ("==" or "IN" operators) that refer to the N
1725 ** left-most columns of the index. It may also contain
1726 ** inequality constraints (>, <, >= or <=) on the indexed
1727 ** column that immediately follows the N equalities. Only
1728 ** the right-most column can be an inequality - the rest must
1729 ** use the "==" and "IN" operators. For example, if the
1730 ** index is on (x,y,z), then the following clauses are all
1731 ** optimized:
1732 **
1733 ** x=5
1734 ** x=5 AND y=10
1735 ** x=5 AND y<10
1736 ** x=5 AND y>5 AND y<10
1737 ** x=5 AND y=5 AND z<=10
1738 **
1739 ** The z<10 term of the following cannot be used, only
1740 ** the x=5 term:
1741 **
1742 ** x=5 AND z<10
1743 **
1744 ** N may be zero if there are inequality constraints.
1745 ** If there are no inequality constraints, then N is at
1746 ** least one.
1747 **
1748 ** This case is also used when there are no WHERE clause
1749 ** constraints but an index is selected anyway, in order
1750 ** to force the output order to conform to an ORDER BY.
1751 */
1760 OP_SeekLE /* 7: (start_constraints && startEq && bRev) */
1761 };
1767 };
1793 /* Find any inequality constraint terms for the start and end
1794 ** of the range.
1795 */
1800 /* Like optimization range constraints always occur in pairs */
1803 }
1807 #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
1815 /* iLikeRepCntr actually stores 2x the counter register number. The
1816 ** bottom bit indicates whether the search order is ASC or DESC. */
1822 }
1823 #endif
1828 }
1829 }
1830 }
1833 /* If the WHERE_BIGNULL_SORT flag is set, then index column nEq uses
1834 ** a non-default "big-null" sort (either ASC NULLS LAST or DESC NULLS
1835 ** FIRST). In both cases separate ordered scans are made of those
1836 ** index entries for which the column is null and for those for which
1837 ** it is not. For an ASC sort, the non-NULL entries are scanned first.
1838 ** For DESC, NULL entries are scanned first.
1839 */
1842 ){
1851 }
1853 }
1855 /* If we are doing a reverse order scan on an ascending index, or
1856 ** a forward order scan on a descending index, interchange the
1857 ** start and end terms (pRangeStart and pRangeEnd).
1858 */
1863 }
1866 /* In case OP_SeekScan is used, ensure that the index cursor does not
1867 ** point to a valid row for the first iteration of this loop. */
1869 }
1871 /* Generate code to evaluate all constraint terms using == or IN
1872 ** and store the values of those terms in an array of registers
1873 ** starting at regBase.
1874 */
1880 }
1891 /* Seek the index cursor to the start of the range. */
1899 ){
1902 }
1905 }
1912 }
1918 nConstraint++;
1922 nConstraint++;
1923 }
1926 /* The skip-scan logic inside the call to codeAllEqualityConstraints()
1927 ** above has already left the cursor sitting on the correct row,
1928 ** so no further seeking is needed */
1933 }
1939 }
1945 /* TUNING: The OP_SeekScan opcode seeks to reduce the number
1946 ** of expensive seek operations by replacing a single seek with
1947 ** 1 or more step operations. The question is, how many steps
1948 ** should we try before giving up and going with a seek. The cost
1949 ** of a seek is proportional to the logarithm of the of the number
1950 ** of entries in the tree, so basing the number of steps to try
1951 ** on the estimated number of rows in the btree seems like a good
1952 ** guess. */
1959 }
1961 }
1986 }
1987 }
1989 /* Load the value for the inequality constraint at the end of the
1990 ** range (if any).
1991 */
2001 ){
2004 }
2010 }
2018 }
2023 }
2024 nConstraint++;
2025 }
2029 /* Top of the loop body */
2032 /* Check if the index cursor is past the end of the range. */
2035 /* Except, skip the end-of-range check while doing the NULL-scan */
2039 }
2047 }
2049 /* During a NULL-scan, check to see if we have reached the end of
2050 ** the NULLs */
2064 }
2068 }
2070 /* Seek the table cursor, if required */
2074 /* pIdx is a covering index. No need to access the main table. */
2083 }
2086 }
2089 /* If a partial index is driving the loop, try to eliminate WHERE clause
2090 ** terms from the query that must be true due to the WHERE clause of
2091 ** the partial index.
2092 **
2093 ** 2019-11-02 ticket 623eff57e76d45f6: This optimization does not work
2094 ** for a LEFT JOIN.
2095 */
2098 }
2101 /* The following assert() is not a requirement, merely an observation:
2102 ** The OR-optimization doesn't work for the right hand table of
2103 ** a LEFT JOIN: */
2105 }
2107 /* Record the instruction used to terminate the loop. */
2110 ){
2116 }
2123 }
2127 #ifndef SQLITE_OMIT_OR_OPTIMIZATION
2129 /* Case 5: Two or more separately indexed terms connected by OR
2130 **
2131 ** Example:
2132 **
2133 ** CREATE TABLE t1(a,b,c,d);
2134 ** CREATE INDEX i1 ON t1(a);
2135 ** CREATE INDEX i2 ON t1(b);
2136 ** CREATE INDEX i3 ON t1(c);
2137 **
2138 ** SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
2139 **
2140 ** In the example, there are three indexed terms connected by OR.
2141 ** The top of the loop looks like this:
2142 **
2143 ** Null 1 # Zero the rowset in reg 1
2144 **
2145 ** Then, for each indexed term, the following. The arguments to
2146 ** RowSetTest are such that the rowid of the current row is inserted
2147 ** into the RowSet. If it is already present, control skips the
2148 ** Gosub opcode and jumps straight to the code generated by WhereEnd().
2149 **
2150 ** sqlite3WhereBegin(<term>)
2151 ** RowSetTest # Insert rowid into rowset
2152 ** Gosub 2 A
2153 ** sqlite3WhereEnd()
2154 **
2155 ** Following the above, code to terminate the loop. Label A, the target
2156 ** of the Gosub above, jumps to the instruction right after the Goto.
2157 **
2158 ** Null 1 # Zero the rowset in reg 1
2159 ** Goto B # The loop is finished.
2160 **
2161 ** A: <loop body> # Return data, whatever.
2162 **
2163 ** Return 2 # Jump back to the Gosub
2164 **
2165 ** B: <after the loop>
2166 **
2167 ** Added 2014-05-26: If the table is a WITHOUT ROWID table, then
2168 ** use an ephemeral index instead of a RowSet to record the primary
2169 ** keys of the rows we have already seen.
2170 **
2171 */
2195 /* Set up a new SrcList in pOrTab containing the table being scanned
2196 ** by this loop in the a[0] slot and all notReady tables in a[1..] slots.
2197 ** This becomes the SrcList in the recursive call to sqlite3WhereBegin().
2198 */
2212 }
2215 }
2217 /* Initialize the rowset register to contain NULL. An SQL NULL is
2218 ** equivalent to an empty rowset. Or, create an ephemeral index
2219 ** capable of holding primary keys in the case of a WITHOUT ROWID.
2220 **
2221 ** Also initialize regReturn to contain the address of the instruction
2222 ** immediately following the OP_Return at the bottom of the loop. This
2223 ** is required in a few obscure LEFT JOIN cases where control jumps
2224 ** over the top of the loop into the body of it. In this case the
2225 ** correct response for the end-of-loop code (the OP_Return) is to
2226 ** fall through to the next instruction, just as an OP_Next does if
2227 ** called on an uninitialized cursor.
2228 */
2238 }
2240 }
2243 /* If the original WHERE clause is z of the form: (x1 OR x2 OR ...) AND y
2244 ** Then for every term xN, evaluate as the subexpression: xN AND y
2245 ** That way, terms in y that are factored into the disjunction will
2246 ** be picked up by the recursive calls to sqlite3WhereBegin() below.
2247 **
2248 ** Actually, each subexpression is converted to "xN AND w" where w is
2249 ** the "interesting" terms of z - terms that did not originate in the
2250 ** ON or USING clause of a LEFT JOIN, and terms that are usable as
2251 ** indices.
2252 **
2253 ** This optimization also only applies if the (x1 OR x2 OR ...) term
2254 ** is not contained in the ON clause of a LEFT JOIN.
2255 ** See ticket http://www.sqlite.org/src/info/f2369304e4
2256 **
2257 ** 2022-02-04: Do not push down slices of a row-value comparison.
2258 ** In other words, "w" or "y" may not be a slice of a vector. Otherwise,
2259 ** the initialization of the right-hand operand of the vector comparison
2260 ** might not occur, or might occur only in an OR branch that is not
2261 ** taken. dbsqlfuzz 80a9fade844b4fb43564efc972bcb2c68270f5d1.
2262 **
2263 ** 2022-03-03: Do not push down expressions that involve subqueries.
2264 ** The subquery might get coded as a subroutine. Any table-references
2265 ** in the subquery might be resolved to index-references for the index on
2266 ** the OR branch in which the subroutine is coded. But if the subroutine
2267 ** is invoked from a different OR branch that uses a different index, such
2268 ** index-references will not work. tag-20220303a
2269 ** https://sqlite.org/forum/forumpost/36937b197273d403
2270 */
2281 }
2286 }
2288 /* The extra 0x10000 bit on the opcode is masked off and does not
2289 ** become part of the new Expr.op. However, it does make the
2290 ** op==TK_AND comparison inside of sqlite3PExpr() false, and this
2291 ** prevents sqlite3PExpr() from applying the AND short-circuit
2292 ** optimization, which we do not want here. */
2294 }
2295 }
2297 /* Run a separate WHERE clause for each term of the OR clause. After
2298 ** eliminating duplicates from other WHERE clauses, the action for each
2299 ** sub-WHERE clause is to to invoke the main loop body as a subroutine.
2300 */
2316 }
2320 }
2321 /* Loop through table entries that match term pOrTerm. */
2331 );
2334 /* This is the sub-WHERE clause body. First skip over
2335 ** duplicate rows from prior sub-WHERE clauses, and record the
2336 ** rowid (or PRIMARY KEY) for the current row so that the same
2337 ** row will be skipped in subsequent sub-WHERE clauses.
2338 */
2352 /* Read the PK into an array of temp registers. */
2357 }
2359 /* Check if the temp table already contains this key. If so,
2360 ** the row has already been included in the result set and
2361 ** can be ignored (by jumping past the Gosub below). Otherwise,
2362 ** insert the key into the temp table and proceed with processing
2363 ** the row.
2364 **
2365 ** Use some of the same optimizations as OP_RowSetTest: If iSet
2366 ** is zero, assume that the key cannot already be present in
2367 ** the temp table. And if iSet is -1, assume that there is no
2368 ** need to insert the key into the temp table, as it will never
2369 ** be tested for. */
2373 }
2379 }
2381 /* Release the array of temp registers */
2383 }
2384 }
2386 /* Invoke the main loop body as a subroutine */
2389 /* Jump here (skipping the main loop body subroutine) if the
2390 ** current sub-WHERE row is a duplicate from prior sub-WHEREs. */
2393 /* The pSubWInfo->untestedTerms flag means that this OR term
2394 ** contained one or more AND term from a notReady table. The
2395 ** terms from the notReady table could not be tested and will
2396 ** need to be tested later.
2397 */
2400 /* If all of the OR-connected terms are optimized using the same
2401 ** index, and the index is opened using the same cursor number
2402 ** by each call to sqlite3WhereBegin() made by this loop, it may
2403 ** be possible to use that index as a covering index.
2404 **
2405 ** If the call to sqlite3WhereBegin() above resulted in a scan that
2406 ** uses an index, and this is either the first OR-connected term
2407 ** processed or the index is the same as that used by all previous
2408 ** terms, set pCov to the candidate covering index. Otherwise, set
2409 ** pCov to NULL to indicate that no candidate covering index will
2410 ** be available.
2411 */
2417 ){
2422 }
2425 }
2427 /* Finish the loop through table entries that match term pOrTerm. */
2430 }
2432 }
2433 }
2443 }
2448 /* Set the P2 operand of the OP_Return opcode that will end the current
2449 ** loop to point to this spot, which is the top of the next containing
2450 ** loop. The byte-code formatter will use that P2 value as a hint to
2451 ** indent everything in between the this point and the final OP_Return.
2452 ** See tag-20220407a in vdbe.c and shell.c */
2461 {
2462 /* Case 6: There is no usable index. We must do a complete
2463 ** scan of the entire table.
2464 */
2469 /* Tables marked isRecursive have only a single row that is stored in
2470 ** a pseudo-cursor. No need to Rewind or Next such cursors. */
2480 }
2481 }
2483 #ifdef SQLITE_ENABLE_STMT_SCANSTATUS
2485 #endif
2487 /* Insert code to test every subexpression that can be completely
2488 ** computed using the current set of tables.
2489 **
2490 ** This loop may run between one and three times, depending on the
2491 ** constraints to be generated. The value of stack variable iLoop
2492 ** determines the constraints coded by each iteration, as follows:
2493 **
2494 ** iLoop==1: Code only expressions that are entirely covered by pIdx.
2495 ** iLoop==2: Code remaining expressions that do not contain correlated
2496 ** sub-queries.
2497 ** iLoop==3: Code all remaining expressions.
2498 **
2499 ** An effort is made to skip unnecessary iterations of the loop.
2500 **
2501 ** This optimization of causing simple query restrictions to occur before
2502 ** more complex one is call the "push-down" optimization in MySQL. Here
2503 ** in SQLite, the name is "MySQL push-down", since there is also another
2504 ** totally unrelated optimization called "WHERE-clause push-down".
2505 ** Sometimes the qualifier is omitted, resulting in an ambiguity, so beware.
2506 */
2521 }
2526 /* Defer processing WHERE clause constraints until after outer
2527 ** join processing. tag-20220513a */
2535 /* An ON clause that is not ripe */
2537 }
2538 }
2539 }
2543 }
2547 }
2550 /* If the TERM_LIKECOND flag is set, that means that the range search
2551 ** is sufficient to guarantee that the LIKE operator is true, so we
2552 ** can skip the call to the like(A,B) function. But this only works
2553 ** for strings. So do not skip the call to the function on the pass
2554 ** that compares BLOBs. */
2555 #ifdef SQLITE_LIKE_DOESNT_MATCH_BLOBS
2557 #else
2563 }
2564 #endif
2565 }
2570 }
2574 }
2575 #endif
2579 }
2583 /* Insert code to test for implied constraints based on transitivity
2584 ** of the "==" operator.
2585 **
2586 ** Example: If the WHERE clause contains "t1.a=t2.b" and "t2.b=123"
2587 ** and we are coding the t1 loop and the t2 loop has not yet coded,
2588 ** then we cannot use the "t1.a=t2.b" constraint, but we can code
2589 ** the implied "t1.a=123" constraint.
2590 */
2604 }
2605 #endif
2616 ){
2618 }
2627 }
2629 /* For a RIGHT OUTER JOIN, record the fact that the current row has
2630 ** been matched at least once.
2631 */
2639 /* pTab is the right-hand table of the RIGHT JOIN. Generate code that
2640 ** will record that the current row of that table has been matched at
2641 ** least once. This is accomplished by storing the PK for the row in
2642 ** both the iMatch index and the regBloom Bloom filter.
2643 */
2657 }
2658 }
2668 }
2670 /* For a LEFT OUTER JOIN, generate code that will record the fact that
2671 ** at least one row of the right table has matched the left table.
2672 */
2679 }
2680 }
2683 /* Create a subroutine used to process all interior loops and code
2684 ** of the RIGHT JOIN. During normal operation, the subroutine will
2685 ** be in-line with the rest of the code. But at the end, a separate
2686 ** loop will run that invokes this subroutine for unmatched rows
2687 ** of pTab, with all tables to left begin set to NULL.
2688 */
2695 /* WHERE clause constraints must be deferred until after outer join
2696 ** row elimination has completed, since WHERE clause constraints apply
2697 ** to the results of the OUTER JOIN. The following loop generates the
2698 ** appropriate WHERE clause constraint checks. tag-20220513a.
2699 */
2700 code_outer_join_constraints:
2708 }
2713 }
2714 }
2719 iLevel);
2721 }
2725 }
2726 #endif
2728 }
2730 /*
2731 ** Generate the code for the loop that finds all non-matched terms
2732 ** for a RIGHT JOIN.
2733 */
2737 WhereLevel *pLevel
2738 ){
2747 SrcList sFrom;
2764 );
2765 }
2770 }
2771 }
2778 ){
2780 }
2785 }
2786 }
2813 }
2814 }
2822 }
2827 }