| blob | a998c0a4f4d113aca22660cb8411ca5ea9db8420 |
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 }
318 }
319 }
320 }
321 #endif
324 /*
325 ** Disable a term in the WHERE clause. Except, do not disable the term
326 ** if it controls a LEFT OUTER JOIN and it did not originate in the ON
327 ** or USING clause of that join.
328 **
329 ** Consider the term t2.z='ok' in the following queries:
330 **
331 ** (1) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok'
332 ** (2) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok'
333 ** (3) SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok'
334 **
335 ** The t2.z='ok' is disabled in the in (2) because it originates
336 ** in the ON clause. The term is disabled in (3) because it is not part
337 ** of a LEFT OUTER JOIN. In (1), the term is not disabled.
338 **
339 ** Disabling a term causes that term to not be tested in the inner loop
340 ** of the join. Disabling is an optimization. When terms are satisfied
341 ** by indices, we disable them to prevent redundant tests in the inner
342 ** loop. We would get the correct results if nothing were ever disabled,
343 ** but joins might run a little slower. The trick is to disable as much
344 ** as we can without disabling too much. If we disabled in (1), we'd get
345 ** the wrong answer. See ticket #813.
346 **
347 ** If all the children of a term are disabled, then that term is also
348 ** automatically disabled. In this way, terms get disabled if derived
349 ** virtual terms are tested first. For example:
350 **
351 ** x GLOB 'abc*' AND x>='abc' AND x<'acd'
352 ** \___________/ \______/ \_____/
353 ** parent child1 child2
354 **
355 ** Only the parent term was in the original WHERE clause. The child1
356 ** and child2 terms were added by the LIKE optimization. If both of
357 ** the virtual child terms are valid, then testing of the parent can be
358 ** skipped.
359 **
360 ** Usually the parent term is marked as TERM_CODED. But if the parent
361 ** term was originally TERM_LIKE, then the parent gets TERM_LIKECOND instead.
362 ** The TERM_LIKECOND marking indicates that the term should be coded inside
363 ** a conditional such that is only evaluated on the second pass of a
364 ** LIKE-optimization loop, when scanning BLOBs instead of strings.
365 */
372 ){
377 }
378 #ifdef WHERETRACE_ENABLED
382 }
383 #endif
389 nLoop++;
390 }
391 }
393 /*
394 ** Code an OP_Affinity opcode to apply the column affinity string zAff
395 ** to the n registers starting at base.
396 **
397 ** As an optimization, SQLITE_AFF_BLOB and SQLITE_AFF_NONE entries (which
398 ** are no-ops) at the beginning and end of zAff are ignored. If all entries
399 ** in zAff are SQLITE_AFF_BLOB or SQLITE_AFF_NONE, then no code gets generated.
400 **
401 ** This routine makes its own copy of zAff so that the caller is free
402 ** to modify zAff after this routine returns.
403 */
409 }
412 /* Adjust base and n to skip over SQLITE_AFF_BLOB and SQLITE_AFF_NONE
413 ** entries at the beginning and end of the affinity string.
414 */
417 n--;
418 base++;
419 zAff++;
420 }
422 n--;
423 }
425 /* Code the OP_Affinity opcode if there is anything left to do. */
428 }
429 }
431 /*
432 ** Expression pRight, which is the RHS of a comparison operation, is
433 ** either a vector of n elements or, if n==1, a scalar expression.
434 ** Before the comparison operation, affinity zAff is to be applied
435 ** to the pRight values. This function modifies characters within the
436 ** affinity string to SQLITE_AFF_BLOB if either:
437 **
438 ** * the comparison will be performed with no affinity, or
439 ** * the affinity change in zAff is guaranteed not to change the value.
440 */
445 ){
451 ){
453 }
454 }
455 }
458 /*
459 ** pX is an expression of the form: (vector) IN (SELECT ...)
460 ** In other words, it is a vector IN operator with a SELECT clause on the
461 ** LHS. But not all terms in the vector are indexable and the terms might
462 ** not be in the correct order for indexing.
463 **
464 ** This routine makes a copy of the input pX expression and then adjusts
465 ** the vector on the LHS with corresponding changes to the SELECT so that
466 ** the vector contains only index terms and those terms are in the correct
467 ** order. The modified IN expression is returned. The caller is responsible
468 ** for deleting the returned expression.
469 **
470 ** Example:
471 **
472 ** CREATE TABLE t1(a,b,c,d,e,f);
473 ** CREATE INDEX t1x1 ON t1(e,c);
474 ** SELECT * FROM t1 WHERE (a,b,c,d,e) IN (SELECT v,w,x,y,z FROM t2)
475 ** \_______________________________________/
476 ** The pX expression
477 **
478 ** Since only columns e and c can be used with the index, in that order,
479 ** the modified IN expression that is returned will be:
480 **
481 ** (e,c) IN (SELECT z,x FROM t2)
482 **
483 ** The reduced pX is different from the original (obviously) and thus is
484 ** only used for indexing, to improve performance. The original unaltered
485 ** IN expression must also be run on each output row for correctness.
486 */
492 ){
511 }
524 }
525 }
526 }
531 }
534 /* Take care here not to generate a TK_VECTOR containing only a
535 ** single value. Since the parser never creates such a vector, some
536 ** of the subroutines do not handle this case. */
541 }
543 /* If the SELECT statement has an ORDER BY clause, zero the
544 ** iOrderByCol variables. These are set to non-zero when an
545 ** ORDER BY term exactly matches one of the terms of the
546 ** result-set. Since the result-set of the SELECT statement may
547 ** have been modified or reordered, these variables are no longer
548 ** set correctly. Since setting them is just an optimization,
549 ** it's easiest just to zero them here. */
553 }
554 }
556 #if 0
561 #endif
562 }
563 }
565 }
568 /*
569 ** Generate code for a single equality term of the WHERE clause. An equality
570 ** term can be either X=expr or X IN (...). pTerm is the term to be
571 ** coded.
572 **
573 ** The current value for the constraint is left in a register, the index
574 ** of which is returned. An attempt is made store the result in iTarget but
575 ** this is only guaranteed for TK_ISNULL and TK_IN constraints. If the
576 ** constraint is a TK_EQ or TK_IS, then the current value might be left in
577 ** some other register and it is the caller's responsibility to compensate.
578 **
579 ** For a constraint of the form X=expr, the expression is evaluated in
580 ** straight-line code. For constraints of the form X IN (...)
581 ** this routine sets up a loop that will iterate over all values of X.
582 */
590 ){
602 #ifndef SQLITE_OMIT_SUBQUERY
615 ){
619 }
627 }
628 }
632 }
646 }
652 }
654 }
659 }
668 }
671 }
691 }
701 }
704 }
705 pIn++;
706 }
707 }
713 ){
715 }
718 }
720 #endif
721 }
723 /* As an optimization, try to disable the WHERE clause term that is
724 ** driving the index as it will always be true. The correct answer is
725 ** obtained regardless, but we might get the answer with fewer CPU cycles
726 ** by omitting the term.
727 **
728 ** But do not disable the term unless we are certain that the term is
729 ** not a transitive constraint. For an example of where that does not
730 ** work, see https://sqlite.org/forum/forumpost/eb8613976a (2021-05-04)
731 */
734 ){
736 }
739 }
741 /*
742 ** Generate code that will evaluate all == and IN constraints for an
743 ** index scan.
744 **
745 ** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c).
746 ** Suppose the WHERE clause is this: a==5 AND b IN (1,2,3) AND c>5 AND c<10
747 ** The index has as many as three equality constraints, but in this
748 ** example, the third "c" value is an inequality. So only two
749 ** constraints are coded. This routine will generate code to evaluate
750 ** a==5 and b IN (1,2,3). The current values for a and b will be stored
751 ** in consecutive registers and the index of the first register is returned.
752 **
753 ** In the example above nEq==2. But this subroutine works for any value
754 ** of nEq including 0. If nEq==0, this routine is nearly a no-op.
755 ** The only thing it does is allocate the pLevel->iMem memory cell and
756 ** compute the affinity string.
757 **
758 ** The nExtraReg parameter is 0 or 1. It is 0 if all WHERE clause constraints
759 ** are == or IN and are covered by the nEq. nExtraReg is 1 if there is
760 ** an inequality constraint (such as the "c>=5 AND c<10" in the example) that
761 ** occurs after the nEq quality constraints.
762 **
763 ** This routine allocates a range of nEq+nExtraReg memory cells and returns
764 ** the index of the first memory cell in that range. The code that
765 ** calls this routine will use that memory range to store keys for
766 ** start and termination conditions of the loop.
767 ** key value of the loop. If one or more IN operators appear, then
768 ** this routine allocates an additional nEq memory cells for internal
769 ** use.
770 **
771 ** Before returning, *pzAff is set to point to a buffer containing a
772 ** copy of the column affinity string of the index allocated using
773 ** sqlite3DbMalloc(). Except, entries in the copy of the string associated
774 ** with equality constraints that use BLOB or NONE affinity are set to
775 ** SQLITE_AFF_BLOB. This is to deal with SQL such as the following:
776 **
777 ** CREATE TABLE t1(a TEXT PRIMARY KEY, b);
778 ** SELECT ... FROM t1 AS t2, t1 WHERE t1.a = t2.b;
779 **
780 ** In the example above, the index on t1(a) has TEXT affinity. But since
781 ** the right hand side of the equality constraint (t2.b) has BLOB/NONE affinity,
782 ** no conversion should be attempted before using a t2.b value as part of
783 ** a key to search the index. Hence the first byte in the returned affinity
784 ** string in this example would be set to SQLITE_AFF_BLOB.
785 */
792 ){
804 /* This module is only called on query plans that use an index. */
812 /* Figure out how many memory cells we will need then allocate them.
813 */
839 }
840 }
842 /* Evaluate the equality constraints
843 */
849 /* The following testcase is true for indices with redundant columns.
850 ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */
860 }
861 }
862 }
867 /* No affinity ever needs to be (or should be) applied to a value
868 ** from the RHS of an "? IN (SELECT ...)" expression. The
869 ** sqlite3FindInIndex() routine has already ensured that the
870 ** affinity of the comparison has been applied to the value. */
872 }
878 }
883 }
886 }
887 }
888 }
889 }
892 }
894 #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
895 /*
896 ** If the most recently coded instruction is a constant range constraint
897 ** (a string literal) that originated from the LIKE optimization, then
898 ** set P3 and P5 on the OP_String opcode so that the string will be cast
899 ** to a BLOB at appropriate times.
900 **
901 ** The LIKE optimization trys to evaluate "x LIKE 'abc%'" as a range
902 ** expression: "x>='ABC' AND x<'abd'". But this requires that the range
903 ** scan loop run twice, once for strings and a second time for BLOBs.
904 ** The OP_String opcodes on the second pass convert the upper and lower
905 ** bound string constants to blobs. This routine makes the necessary changes
906 ** to the OP_String opcodes for that to happen.
907 **
908 ** Except, of course, if SQLITE_LIKE_DOESNT_MATCH_BLOBS is defined, then
909 ** only the one pass through the string space is required, so this routine
910 ** becomes a no-op.
911 */
916 ){
926 }
927 }
928 #else
929 # define whereLikeOptimizationStringFixup(A,B,C)
930 #endif
932 #ifdef SQLITE_ENABLE_CURSOR_HINTS
933 /*
934 ** Information is passed from codeCursorHint() down to individual nodes of
935 ** the expression tree (by sqlite3WalkExpr()) using an instance of this
936 ** structure.
937 */
942 };
944 /*
945 ** This function is called for every node of an expression that is a candidate
946 ** for a cursor hint on an index cursor. For TK_COLUMN nodes that reference
947 ** the table CCurHint.iTabCur, verify that the same column can be
948 ** accessed through the index. If it cannot, then set pWalker->eCode to 1.
949 */
956 ){
958 }
960 }
962 /*
963 ** Test whether or not expression pExpr, which was part of a WHERE clause,
964 ** should be included in the cursor-hint for a table that is on the rhs
965 ** of a LEFT JOIN. Set Walker.eCode to non-zero before returning if the
966 ** expression is not suitable.
967 **
968 ** An expression is unsuitable if it might evaluate to non NULL even if
969 ** a TK_COLUMN node that does affect the value of the expression is set
970 ** to NULL. For example:
971 **
972 ** col IS NULL
973 ** col IS NOT NULL
974 ** coalesce(col, 1)
975 ** CASE WHEN col THEN 0 ELSE 1 END
976 */
981 ){
988 }
989 }
992 }
995 /*
996 ** This function is called on every node of an expression tree used as an
997 ** argument to the OP_CursorHint instruction. If the node is a TK_COLUMN
998 ** that accesses any table other than the one identified by
999 ** CCurHint.iTabCur, then do the following:
1000 **
1001 ** 1) allocate a register and code an OP_Column instruction to read
1002 ** the specified column into the new register, and
1003 **
1004 ** 2) transform the expression node to a TK_REGISTER node that reads
1005 ** from the newly populated register.
1006 **
1007 ** Also, if the node is a TK_COLUMN that does access the table idenified
1008 ** by pCCurHint.iTabCur, and an index is being used (which we will
1009 ** know because CCurHint.pIdx!=0) then transform the TK_COLUMN into
1010 ** an access of the index rather than the original table.
1011 */
1026 }
1034 /* Do not walk disabled expressions. tag-20230504-1 */
1036 }
1038 }
1040 /*
1041 ** Insert an OP_CursorHint instruction if it is appropriate to do so.
1042 */
1048 ){
1059 Walker sWalker;
1076 /* Any terms specified as part of the ON(...) clause for any LEFT
1077 ** JOIN for which the current table is not the rhs are omitted
1078 ** from the cursor-hint.
1079 **
1080 ** If this table is the rhs of a LEFT JOIN, "IS" or "IS NULL" terms
1081 ** that were specified as part of the WHERE clause must be excluded.
1082 ** This is to address the following:
1083 **
1084 ** SELECT ... t1 LEFT JOIN t2 ON (t1.a=t2.b) WHERE t2.c IS NULL;
1085 **
1086 ** Say there is a single row in t2 that matches (t1.a=t2.b), but its
1087 ** t2.c values is not NULL. If the (t2.c IS NULL) constraint is
1088 ** pushed down to the cursor, this row is filtered out, causing
1089 ** SQLite to synthesize a row of NULL values. Which does match the
1090 ** WHERE clause, and so the query returns a row. Which is incorrect.
1091 **
1092 ** For the same reason, WHERE terms such as:
1093 **
1094 ** WHERE 1 = (t2.c IS NULL)
1095 **
1096 ** are also excluded. See codeCursorHintIsOrFunction() for details.
1097 */
1102 ){
1107 }
1110 }
1112 /* All terms in pWLoop->aLTerm[] except pEndRange are used to initialize
1113 ** the cursor. These terms are not needed as hints for a pure range
1114 ** scan (that has no == terms) so omit them. */
1118 }
1120 /* No subqueries or non-deterministic functions allowed */
1123 /* For an index scan, make sure referenced columns are actually in
1124 ** the index. */
1130 }
1132 /* If we survive all prior tests, that means this term is worth hinting */
1134 }
1141 }
1142 }
1143 #else
1147 /*
1148 ** Cursor iCur is open on an intkey b-tree (a table). Register iRowid contains
1149 ** a rowid value just read from cursor iIdxCur, open on index pIdx. This
1150 ** function generates code to do a deferred seek of cursor iCur to the
1151 ** rowid stored in register iRowid.
1152 **
1153 ** Normally, this is just:
1154 **
1155 ** OP_DeferredSeek $iCur $iRowid
1156 **
1157 ** Which causes a seek on $iCur to the row with rowid $iRowid.
1158 **
1159 ** However, if the scan currently being coded is a branch of an OR-loop and
1160 ** the statement currently being coded is a SELECT, then additional information
1161 ** is added that might allow OP_Column to omit the seek and instead do its
1162 ** lookup on the index, thus avoiding an expensive seek operation. To
1163 ** enable this optimization, the P3 of OP_DeferredSeek is set to iIdxCur
1164 ** and P4 is set to an array of integers containing one entry for each column
1165 ** in the table. For each table column, if the column is the i'th
1166 ** column of the index, then the corresponding array entry is set to (i+1).
1167 ** If the column does not appear in the index at all, the array entry is set
1168 ** to 0. The OP_Column opcode can check this array to see if the column it
1169 ** wants is in the index and if it is, it will substitute the index cursor
1170 ** and column number and continue with those new values, rather than seeking
1171 ** the table cursor.
1172 */
1178 ){
1189 ){
1202 }
1204 }
1205 }
1206 }
1208 /*
1209 ** If the expression passed as the second argument is a vector, generate
1210 ** code to write the first nReg elements of the vector into an array
1211 ** of registers starting with iReg.
1212 **
1213 ** If the expression is not a vector, then nReg must be passed 1. In
1214 ** this case, generate code to evaluate the expression and leave the
1215 ** result in register iReg.
1216 */
1220 #ifndef SQLITE_OMIT_SUBQUERY
1228 #endif
1229 {
1237 }
1238 }
1242 }
1243 }
1245 /*
1246 ** The pTruth expression is always true because it is the WHERE clause
1247 ** a partial index that is driving a query loop. Look through all of the
1248 ** WHERE clause terms on the query, and if any of those terms must be
1249 ** true because pTruth is true, then mark those WHERE clause terms as
1250 ** coded.
1251 */
1255 WhereClause *pWC
1256 ){
1262 }
1269 }
1270 }
1271 }
1273 /*
1274 ** This routine is called right after An OP_Filter has been generated and
1275 ** before the corresponding index search has been performed. This routine
1276 ** checks to see if there are additional Bloom filters in inner loops that
1277 ** can be checked prior to doing the index lookup. If there are available
1278 ** inner-loop Bloom filters, then evaluate those filters now, before the
1279 ** index lookup. The idea is that a Bloom filter check is way faster than
1280 ** an index lookup, and the Bloom filter might return false, meaning that
1281 ** the index lookup can be skipped.
1282 **
1283 ** We know that an inner loop uses a Bloom filter because it has the
1284 ** WhereLevel.regFilter set. If an inner-loop Bloom filter is checked,
1285 ** then clear the WhereLevel.regFilter value to prevent the Bloom filter
1286 ** from being checked a second time when the inner loop is evaluated.
1287 */
1293 Bitmask notReady /* Loops that are not ready */
1294 ){
1300 /* ,--- Because sqlite3ConstructBloomFilter() has will not have set
1301 ** vvvvv--' pLevel->regFilter if this were true. */
1331 }
1334 }
1335 }
1337 /*
1338 ** Generate code for the start of the iLevel-th loop in the WHERE clause
1339 ** implementation described by pWInfo.
1340 */
1347 Bitmask notReady /* Which tables are currently available */
1348 ){
1380 }
1381 }
1386 }
1389 }
1390 #endif
1392 /* Create labels for the "break" and "continue" instructions
1393 ** for the current loop. Jump to addrBrk to break out of a loop.
1394 ** Jump to cont to go immediately to the next iteration of the
1395 ** loop.
1396 **
1397 ** When there is an IN operator, we also have a "addrNxt" label that
1398 ** means to continue with the next IN value combination. When
1399 ** there are no IN operators in the constraints, the "addrNxt" label
1400 ** is the same as "addrBrk".
1401 */
1405 /* If this is the right table of a LEFT OUTER JOIN, allocate and
1406 ** initialize a memory cell that records if this table matches any
1407 ** row of the left table of the join.
1408 */
1411 );
1416 }
1418 /* Compute a safe address to jump to if we discover that the table for
1419 ** this loop is empty and can never contribute content. */
1423 }
1426 /* Special case of a FROM clause subquery implemented as a co-routine */
1436 #ifndef SQLITE_OMIT_VIRTUALTABLE
1438 /* Case 1: The table is a virtual-table. Use the VFilter and VNext
1439 ** to access the data.
1440 */
1460 }
1466 ){
1472 }
1473 }
1474 }
1482 /* An OOM inside of AddOp4(OP_VFilter) instruction above might have freed
1483 ** the u.vtab.idxStr. NULL it out to prevent a use-after-free */
1495 }
1499 ){
1505 /* Reload the constraint value into reg[iReg+j+2]. The same value
1506 ** was loaded into the same register prior to the OP_VFilter, but
1507 ** the xFilter implementation might have changed the datatype or
1508 ** encoding of the value in the register, so it *must* be reloaded.
1509 */
1514 ){
1518 }
1519 }
1521 /* Generate code that will continue to the next row if
1522 ** the IN constraint is not satisfied
1523 */
1536 }
1542 );
1543 }
1545 }
1547 }
1548 }
1550 /* These registers need to be preserved in case there is an IN operator
1551 ** loop. So we could deallocate the registers here (and potentially
1552 ** reuse them later) if (pLoop->wsFlags & WHERE_IN_ABLE)==0. But it seems
1553 ** simpler and safer to simply not reuse the registers.
1554 **
1555 ** sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2);
1556 */
1562 ){
1563 /* Case 2: We can directly reference a single row using an
1564 ** equality comparison against the ROWID field. Or
1565 ** we reference multiple rows using a "rowid IN (...)"
1566 ** construct.
1567 */
1584 }
1590 ){
1591 /* Case 3: We have an inequality comparison against the ROWID field.
1592 */
1607 }
1614 /* The following constant maps TK_xx codes into corresponding
1615 ** seek opcodes. It depends on a particular ordering of TK_xx
1616 */
1621 /* TK_GE */ OP_SeekGE
1622 };
1648 }
1660 }
1672 ){
1676 }
1679 }
1680 }
1695 }
1697 /* Case 4: A scan using an index.
1698 **
1699 ** The WHERE clause may contain zero or more equality
1700 ** terms ("==" or "IN" operators) that refer to the N
1701 ** left-most columns of the index. It may also contain
1702 ** inequality constraints (>, <, >= or <=) on the indexed
1703 ** column that immediately follows the N equalities. Only
1704 ** the right-most column can be an inequality - the rest must
1705 ** use the "==" and "IN" operators. For example, if the
1706 ** index is on (x,y,z), then the following clauses are all
1707 ** optimized:
1708 **
1709 ** x=5
1710 ** x=5 AND y=10
1711 ** x=5 AND y<10
1712 ** x=5 AND y>5 AND y<10
1713 ** x=5 AND y=5 AND z<=10
1714 **
1715 ** The z<10 term of the following cannot be used, only
1716 ** the x=5 term:
1717 **
1718 ** x=5 AND z<10
1719 **
1720 ** N may be zero if there are inequality constraints.
1721 ** If there are no inequality constraints, then N is at
1722 ** least one.
1723 **
1724 ** This case is also used when there are no WHERE clause
1725 ** constraints but an index is selected anyway, in order
1726 ** to force the output order to conform to an ORDER BY.
1727 */
1736 OP_SeekLE /* 7: (start_constraints && startEq && bRev) */
1737 };
1743 };
1769 /* Find any inequality constraint terms for the start and end
1770 ** of the range.
1771 */
1776 /* Like optimization range constraints always occur in pairs */
1779 }
1783 #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
1791 /* iLikeRepCntr actually stores 2x the counter register number. The
1792 ** bottom bit indicates whether the search order is ASC or DESC. */
1798 }
1799 #endif
1804 }
1805 }
1806 }
1809 /* If the WHERE_BIGNULL_SORT flag is set, then index column nEq uses
1810 ** a non-default "big-null" sort (either ASC NULLS LAST or DESC NULLS
1811 ** FIRST). In both cases separate ordered scans are made of those
1812 ** index entries for which the column is null and for those for which
1813 ** it is not. For an ASC sort, the non-NULL entries are scanned first.
1814 ** For DESC, NULL entries are scanned first.
1815 */
1818 ){
1827 }
1829 }
1831 /* If we are doing a reverse order scan on an ascending index, or
1832 ** a forward order scan on a descending index, interchange the
1833 ** start and end terms (pRangeStart and pRangeEnd).
1834 */
1839 }
1842 /* In case OP_SeekScan is used, ensure that the index cursor does not
1843 ** point to a valid row for the first iteration of this loop. */
1845 }
1847 /* Generate code to evaluate all constraint terms using == or IN
1848 ** and store the values of those terms in an array of registers
1849 ** starting at regBase.
1850 */
1856 }
1867 /* Seek the index cursor to the start of the range. */
1875 ){
1878 }
1881 }
1888 }
1894 nConstraint++;
1898 nConstraint++;
1899 }
1902 /* The skip-scan logic inside the call to codeAllEqualityConstraints()
1903 ** above has already left the cursor sitting on the correct row,
1904 ** so no further seeking is needed */
1909 }
1915 }
1921 /* TUNING: The OP_SeekScan opcode seeks to reduce the number
1922 ** of expensive seek operations by replacing a single seek with
1923 ** 1 or more step operations. The question is, how many steps
1924 ** should we try before giving up and going with a seek. The cost
1925 ** of a seek is proportional to the logarithm of the of the number
1926 ** of entries in the tree, so basing the number of steps to try
1927 ** on the estimated number of rows in the btree seems like a good
1928 ** guess. */
1935 }
1937 }
1962 }
1963 }
1965 /* Load the value for the inequality constraint at the end of the
1966 ** range (if any).
1967 */
1977 ){
1980 }
1986 }
1994 }
1999 }
2000 nConstraint++;
2001 }
2005 /* Top of the loop body */
2008 /* Check if the index cursor is past the end of the range. */
2011 /* Except, skip the end-of-range check while doing the NULL-scan */
2015 }
2023 }
2025 /* During a NULL-scan, check to see if we have reached the end of
2026 ** the NULLs */
2040 }
2044 }
2046 /* Seek the table cursor, if required */
2050 /* pIdx is a covering index. No need to access the main table. */
2059 }
2062 }
2065 /* If a partial index is driving the loop, try to eliminate WHERE clause
2066 ** terms from the query that must be true due to the WHERE clause of
2067 ** the partial index.
2068 **
2069 ** 2019-11-02 ticket 623eff57e76d45f6: This optimization does not work
2070 ** for a LEFT JOIN.
2071 */
2074 }
2077 /* The following assert() is not a requirement, merely an observation:
2078 ** The OR-optimization doesn't work for the right hand table of
2079 ** a LEFT JOIN: */
2081 }
2083 /* Record the instruction used to terminate the loop. */
2090 }
2097 }
2101 #ifndef SQLITE_OMIT_OR_OPTIMIZATION
2103 /* Case 5: Two or more separately indexed terms connected by OR
2104 **
2105 ** Example:
2106 **
2107 ** CREATE TABLE t1(a,b,c,d);
2108 ** CREATE INDEX i1 ON t1(a);
2109 ** CREATE INDEX i2 ON t1(b);
2110 ** CREATE INDEX i3 ON t1(c);
2111 **
2112 ** SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
2113 **
2114 ** In the example, there are three indexed terms connected by OR.
2115 ** The top of the loop looks like this:
2116 **
2117 ** Null 1 # Zero the rowset in reg 1
2118 **
2119 ** Then, for each indexed term, the following. The arguments to
2120 ** RowSetTest are such that the rowid of the current row is inserted
2121 ** into the RowSet. If it is already present, control skips the
2122 ** Gosub opcode and jumps straight to the code generated by WhereEnd().
2123 **
2124 ** sqlite3WhereBegin(<term>)
2125 ** RowSetTest # Insert rowid into rowset
2126 ** Gosub 2 A
2127 ** sqlite3WhereEnd()
2128 **
2129 ** Following the above, code to terminate the loop. Label A, the target
2130 ** of the Gosub above, jumps to the instruction right after the Goto.
2131 **
2132 ** Null 1 # Zero the rowset in reg 1
2133 ** Goto B # The loop is finished.
2134 **
2135 ** A: <loop body> # Return data, whatever.
2136 **
2137 ** Return 2 # Jump back to the Gosub
2138 **
2139 ** B: <after the loop>
2140 **
2141 ** Added 2014-05-26: If the table is a WITHOUT ROWID table, then
2142 ** use an ephemeral index instead of a RowSet to record the primary
2143 ** keys of the rows we have already seen.
2144 **
2145 */
2169 /* Set up a new SrcList in pOrTab containing the table being scanned
2170 ** by this loop in the a[0] slot and all notReady tables in a[1..] slots.
2171 ** This becomes the SrcList in the recursive call to sqlite3WhereBegin().
2172 */
2186 }
2189 }
2191 /* Initialize the rowset register to contain NULL. An SQL NULL is
2192 ** equivalent to an empty rowset. Or, create an ephemeral index
2193 ** capable of holding primary keys in the case of a WITHOUT ROWID.
2194 **
2195 ** Also initialize regReturn to contain the address of the instruction
2196 ** immediately following the OP_Return at the bottom of the loop. This
2197 ** is required in a few obscure LEFT JOIN cases where control jumps
2198 ** over the top of the loop into the body of it. In this case the
2199 ** correct response for the end-of-loop code (the OP_Return) is to
2200 ** fall through to the next instruction, just as an OP_Next does if
2201 ** called on an uninitialized cursor.
2202 */
2212 }
2214 }
2217 /* If the original WHERE clause is z of the form: (x1 OR x2 OR ...) AND y
2218 ** Then for every term xN, evaluate as the subexpression: xN AND y
2219 ** That way, terms in y that are factored into the disjunction will
2220 ** be picked up by the recursive calls to sqlite3WhereBegin() below.
2221 **
2222 ** Actually, each subexpression is converted to "xN AND w" where w is
2223 ** the "interesting" terms of z - terms that did not originate in the
2224 ** ON or USING clause of a LEFT JOIN, and terms that are usable as
2225 ** indices.
2226 **
2227 ** This optimization also only applies if the (x1 OR x2 OR ...) term
2228 ** is not contained in the ON clause of a LEFT JOIN.
2229 ** See ticket http://www.sqlite.org/src/info/f2369304e4
2230 **
2231 ** 2022-02-04: Do not push down slices of a row-value comparison.
2232 ** In other words, "w" or "y" may not be a slice of a vector. Otherwise,
2233 ** the initialization of the right-hand operand of the vector comparison
2234 ** might not occur, or might occur only in an OR branch that is not
2235 ** taken. dbsqlfuzz 80a9fade844b4fb43564efc972bcb2c68270f5d1.
2236 **
2237 ** 2022-03-03: Do not push down expressions that involve subqueries.
2238 ** The subquery might get coded as a subroutine. Any table-references
2239 ** in the subquery might be resolved to index-references for the index on
2240 ** the OR branch in which the subroutine is coded. But if the subroutine
2241 ** is invoked from a different OR branch that uses a different index, such
2242 ** index-references will not work. tag-20220303a
2243 ** https://sqlite.org/forum/forumpost/36937b197273d403
2244 */
2255 }
2260 }
2262 /* The extra 0x10000 bit on the opcode is masked off and does not
2263 ** become part of the new Expr.op. However, it does make the
2264 ** op==TK_AND comparison inside of sqlite3PExpr() false, and this
2265 ** prevents sqlite3PExpr() from applying the AND short-circuit
2266 ** optimization, which we do not want here. */
2268 }
2269 }
2271 /* Run a separate WHERE clause for each term of the OR clause. After
2272 ** eliminating duplicates from other WHERE clauses, the action for each
2273 ** sub-WHERE clause is to to invoke the main loop body as a subroutine.
2274 */
2290 }
2294 }
2295 /* Loop through table entries that match term pOrTerm. */
2305 );
2308 /* This is the sub-WHERE clause body. First skip over
2309 ** duplicate rows from prior sub-WHERE clauses, and record the
2310 ** rowid (or PRIMARY KEY) for the current row so that the same
2311 ** row will be skipped in subsequent sub-WHERE clauses.
2312 */
2326 /* Read the PK into an array of temp registers. */
2331 }
2333 /* Check if the temp table already contains this key. If so,
2334 ** the row has already been included in the result set and
2335 ** can be ignored (by jumping past the Gosub below). Otherwise,
2336 ** insert the key into the temp table and proceed with processing
2337 ** the row.
2338 **
2339 ** Use some of the same optimizations as OP_RowSetTest: If iSet
2340 ** is zero, assume that the key cannot already be present in
2341 ** the temp table. And if iSet is -1, assume that there is no
2342 ** need to insert the key into the temp table, as it will never
2343 ** be tested for. */
2347 }
2353 }
2355 /* Release the array of temp registers */
2357 }
2358 }
2360 /* Invoke the main loop body as a subroutine */
2363 /* Jump here (skipping the main loop body subroutine) if the
2364 ** current sub-WHERE row is a duplicate from prior sub-WHEREs. */
2367 /* The pSubWInfo->untestedTerms flag means that this OR term
2368 ** contained one or more AND term from a notReady table. The
2369 ** terms from the notReady table could not be tested and will
2370 ** need to be tested later.
2371 */
2374 /* If all of the OR-connected terms are optimized using the same
2375 ** index, and the index is opened using the same cursor number
2376 ** by each call to sqlite3WhereBegin() made by this loop, it may
2377 ** be possible to use that index as a covering index.
2378 **
2379 ** If the call to sqlite3WhereBegin() above resulted in a scan that
2380 ** uses an index, and this is either the first OR-connected term
2381 ** processed or the index is the same as that used by all previous
2382 ** terms, set pCov to the candidate covering index. Otherwise, set
2383 ** pCov to NULL to indicate that no candidate covering index will
2384 ** be available.
2385 */
2391 ){
2396 }
2399 }
2401 /* Finish the loop through table entries that match term pOrTerm. */
2404 }
2406 }
2407 }
2417 }
2422 /* Set the P2 operand of the OP_Return opcode that will end the current
2423 ** loop to point to this spot, which is the top of the next containing
2424 ** loop. The byte-code formatter will use that P2 value as a hint to
2425 ** indent everything in between the this point and the final OP_Return.
2426 ** See tag-20220407a in vdbe.c and shell.c */
2435 {
2436 /* Case 6: There is no usable index. We must do a complete
2437 ** scan of the entire table.
2438 */
2443 /* Tables marked isRecursive have only a single row that is stored in
2444 ** a pseudo-cursor. No need to Rewind or Next such cursors. */
2454 }
2455 }
2457 #ifdef SQLITE_ENABLE_STMT_SCANSTATUS
2459 #endif
2461 /* Insert code to test every subexpression that can be completely
2462 ** computed using the current set of tables.
2463 **
2464 ** This loop may run between one and three times, depending on the
2465 ** constraints to be generated. The value of stack variable iLoop
2466 ** determines the constraints coded by each iteration, as follows:
2467 **
2468 ** iLoop==1: Code only expressions that are entirely covered by pIdx.
2469 ** iLoop==2: Code remaining expressions that do not contain correlated
2470 ** sub-queries.
2471 ** iLoop==3: Code all remaining expressions.
2472 **
2473 ** An effort is made to skip unnecessary iterations of the loop.
2474 */
2489 }
2494 /* Defer processing WHERE clause constraints until after outer
2495 ** join processing. tag-20220513a */
2503 /* An ON clause that is not ripe */
2505 }
2506 }
2507 }
2511 }
2515 }
2518 /* If the TERM_LIKECOND flag is set, that means that the range search
2519 ** is sufficient to guarantee that the LIKE operator is true, so we
2520 ** can skip the call to the like(A,B) function. But this only works
2521 ** for strings. So do not skip the call to the function on the pass
2522 ** that compares BLOBs. */
2523 #ifdef SQLITE_LIKE_DOESNT_MATCH_BLOBS
2525 #else
2531 }
2532 #endif
2533 }
2538 }
2542 }
2543 #endif
2547 }
2551 /* Insert code to test for implied constraints based on transitivity
2552 ** of the "==" operator.
2553 **
2554 ** Example: If the WHERE clause contains "t1.a=t2.b" and "t2.b=123"
2555 ** and we are coding the t1 loop and the t2 loop has not yet coded,
2556 ** then we cannot use the "t1.a=t2.b" constraint, but we can code
2557 ** the implied "t1.a=123" constraint.
2558 */
2572 }
2573 #endif
2584 ){
2586 }
2595 }
2597 /* For a RIGHT OUTER JOIN, record the fact that the current row has
2598 ** been matched at least once.
2599 */
2607 /* pTab is the right-hand table of the RIGHT JOIN. Generate code that
2608 ** will record that the current row of that table has been matched at
2609 ** least once. This is accomplished by storing the PK for the row in
2610 ** both the iMatch index and the regBloom Bloom filter.
2611 */
2625 }
2626 }
2636 }
2638 /* For a LEFT OUTER JOIN, generate code that will record the fact that
2639 ** at least one row of the right table has matched the left table.
2640 */
2647 }
2648 }
2651 /* Create a subroutine used to process all interior loops and code
2652 ** of the RIGHT JOIN. During normal operation, the subroutine will
2653 ** be in-line with the rest of the code. But at the end, a separate
2654 ** loop will run that invokes this subroutine for unmatched rows
2655 ** of pTab, with all tables to left begin set to NULL.
2656 */
2663 /* WHERE clause constraints must be deferred until after outer join
2664 ** row elimination has completed, since WHERE clause constraints apply
2665 ** to the results of the OUTER JOIN. The following loop generates the
2666 ** appropriate WHERE clause constraint checks. tag-20220513a.
2667 */
2668 code_outer_join_constraints:
2676 }
2681 }
2682 }
2687 iLevel);
2689 }
2693 }
2694 #endif
2696 }
2698 /*
2699 ** Generate the code for the loop that finds all non-matched terms
2700 ** for a RIGHT JOIN.
2701 */
2705 WhereLevel *pLevel
2706 ){
2715 SrcList sFrom;
2729 }
2730 }
2737 ){
2739 }
2744 }
2745 }
2772 }
2773 }
2781 }
2786 }