| blob | 84deb5e9ea6b8812e896f8bbfba5c94f7f09421b |
1 /*
2 ** 2001 September 15
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. This module is responsible for
14 ** generating the code that loops through a table looking for applicable
15 ** rows. Indices are selected and used to speed the search when doing
16 ** so is applicable. Because this module is responsible for selecting
17 ** indices, you might also think of this module as the "query optimizer".
18 */
22 /*
23 ** Extra information appended to the end of sqlite3_index_info but not
24 ** visible to the xBestIndex function, at least not directly. The
25 ** sqlite3_vtab_collation() interface knows how to reach it, however.
26 **
27 ** This object is not an API and can be changed from one release to the
28 ** next. As long as allocateIndexInfo() and sqlite3_vtab_collation()
29 ** agree on the structure, all will be well.
30 */
39 ** because extra space is allocated to hold up
40 ** to nTerm such values */
41 };
43 /* Forward declaration of methods */
46 /*
47 ** Return the estimated number of output rows from a WHERE clause
48 */
51 }
53 /*
54 ** Return one of the WHERE_DISTINCT_xxxxx values to indicate how this
55 ** WHERE clause returns outputs for DISTINCT processing.
56 */
59 }
61 /*
62 ** Return the number of ORDER BY terms that are satisfied by the
63 ** WHERE clause. A return of 0 means that the output must be
64 ** completely sorted. A return equal to the number of ORDER BY
65 ** terms means that no sorting is needed at all. A return that
66 ** is positive but less than the number of ORDER BY terms means that
67 ** block sorting is required.
68 */
71 }
73 /*
74 ** In the ORDER BY LIMIT optimization, if the inner-most loop is known
75 ** to emit rows in increasing order, and if the last row emitted by the
76 ** inner-most loop did not fit within the sorter, then we can skip all
77 ** subsequent rows for the current iteration of the inner loop (because they
78 ** will not fit in the sorter either) and continue with the second inner
79 ** loop - the loop immediately outside the inner-most.
80 **
81 ** When a row does not fit in the sorter (because the sorter already
82 ** holds LIMIT+OFFSET rows that are smaller), then a jump is made to the
83 ** label returned by this function.
84 **
85 ** If the ORDER BY LIMIT optimization applies, the jump destination should
86 ** be the continuation for the second-inner-most loop. If the ORDER BY
87 ** LIMIT optimization does not apply, then the jump destination should
88 ** be the continuation for the inner-most loop.
89 **
90 ** It is always safe for this routine to return the continuation of the
91 ** inner-most loop, in the sense that a correct answer will result.
92 ** Returning the continuation the second inner loop is an optimization
93 ** that might make the code run a little faster, but should not change
94 ** the final answer.
95 */
99 /* The ORDER BY LIMIT optimization does not apply. Jump to the
100 ** continuation of the inner-most loop. */
102 }
106 }
108 /*
109 ** While generating code for the min/max optimization, after handling
110 ** the aggregate-step call to min() or max(), check to see if any
111 ** additional looping is required. If the output order is such that
112 ** we are certain that the correct answer has already been found, then
113 ** code an OP_Goto to by pass subsequent processing.
114 **
115 ** Any extra OP_Goto that is coded here is an optimization. The
116 ** correct answer should be obtained regardless. This OP_Goto just
117 ** makes the answer appear faster.
118 */
129 }
130 }
132 }
134 /*
135 ** Return the VDBE address or label to jump to in order to continue
136 ** immediately with the next row of a WHERE clause.
137 */
141 }
143 /*
144 ** Return the VDBE address or label to jump to in order to break
145 ** out of a WHERE loop.
146 */
149 }
151 /*
152 ** Return ONEPASS_OFF (0) if an UPDATE or DELETE statement is unable to
153 ** operate directly on the rowids returned by a WHERE clause. Return
154 ** ONEPASS_SINGLE (1) if the statement can operation directly because only
155 ** a single row is to be changed. Return ONEPASS_MULTI (2) if the one-pass
156 ** optimization can be used on multiple
157 **
158 ** If the ONEPASS optimization is used (if this routine returns true)
159 ** then also write the indices of open cursors used by ONEPASS
160 ** into aiCur[0] and aiCur[1]. iaCur[0] gets the cursor of the data
161 ** table and iaCur[1] gets the cursor used by an auxiliary index.
162 ** Either value may be -1, indicating that cursor is not used.
163 ** Any cursors returned will have been opened for writing.
164 **
165 ** aiCur[0] and aiCur[1] both get -1 if the where-clause logic is
166 ** unable to use the ONEPASS optimization.
167 */
170 #ifdef WHERETRACE_ENABLED
175 }
176 #endif
178 }
180 /*
181 ** Return TRUE if the WHERE loop uses the OP_DeferredSeek opcode to move
182 ** the data cursor to the row selected by the index cursor.
183 */
186 }
188 /*
189 ** Move the content of pSrc into pDest
190 */
194 }
196 /*
197 ** Try to insert a new prerequisite/cost entry into the WhereOrSet pSet.
198 **
199 ** The new entry might overwrite an existing entry, or it might be
200 ** appended, or it might be discarded. Do whatever is the right thing
201 ** so that pSet keeps the N_OR_COST best entries seen so far.
202 */
207 LogEst nOut /* Number of outputs for the new entry */
208 ){
209 u16 i;
214 }
217 }
218 }
226 }
228 }
229 whereOrInsert_done:
234 }
236 /*
237 ** Return the bitmask for the given cursor number. Return 0 if
238 ** iCursor is not in the set.
239 */
247 }
251 }
252 }
254 }
256 /* Allocate memory that is automatically freed when pWInfo is freed.
257 */
265 pBlock++;
266 }
268 }
273 pOldBlk--;
276 }
278 }
280 /*
281 ** Create a new mask for cursor iCursor.
282 **
283 ** There is one cursor per table in the FROM clause. The number of
284 ** tables in the FROM clause is limited by a test early in the
285 ** sqlite3WhereBegin() routine. So we know that the pMaskSet->ix[]
286 ** array will never overflow.
287 */
291 }
293 /*
294 ** If the right-hand branch of the expression is a TK_COLUMN, then return
295 ** a pointer to the right-hand branch. Otherwise, return NULL.
296 */
301 }
303 }
305 /*
306 ** Term pTerm is guaranteed to be a WO_IN term. It may be a component term
307 ** of a vector IN expression of the form "(x, y, ...) IN (SELECT ...)".
308 ** This function checks to see if the term is compatible with an index
309 ** column with affinity idxaff (one of the SQLITE_AFF_XYZ values). If so,
310 ** it returns a pointer to the name of the collation sequence (e.g. "BINARY"
311 ** or "NOCASE") used by the comparison in pTerm. If it is not compatible
312 ** with affinity idxaff, NULL is returned.
313 */
317 u8 idxaff
318 ){
320 Expr inexpr;
332 }
337 }
339 }
341 /*
342 ** Advance to the next WhereTerm that matches according to the criteria
343 ** established when the pScan object was initialized by whereScanInit().
344 ** Return NULL if there are no more matching WhereTerms.
345 */
370 ){
374 ){
380 }
381 }
386 }
387 }
389 /* Verify the affinity and collating sequence match */
402 }
406 }
410 }
411 }
417 ){
420 }
423 #ifdef WHERETRACE_ENABLED
431 }
433 }
434 #endif
436 }
437 }
438 }
446 }
448 }
450 /*
451 ** This is whereScanInit() for the case of an index on an expression.
452 ** It is factored out into a separate tail-recursion subroutine so that
453 ** the normal whereScanInit() routine, which is a high-runner, does not
454 ** need to push registers onto the stack as part of its prologue.
455 */
459 }
461 /*
462 ** Initialize a WHERE clause scanner object. Return a pointer to the
463 ** first match. Return NULL if there are no matches.
464 **
465 ** The scanner will be searching the WHERE clause pWC. It will look
466 ** for terms of the form "X <op> <expr>" where X is column iColumn of table
467 ** iCur. Or if pIdx!=0 then X is column iColumn of index pIdx. pIdx
468 ** must be one of the indexes of table iCur.
469 **
470 ** The <op> must be one of the operators described by opMask.
471 **
472 ** If the search is for X and the WHERE clause contains terms of the
473 ** form X=Y then this routine might also return terms of the form
474 ** "Y <op> <expr>". The number of levels of transitivity is limited,
475 ** but is enough to handle most commonly occurring SQL statements.
476 **
477 ** If X is not the INTEGER PRIMARY KEY then X must be compatible with
478 ** index pIdx.
479 */
487 ){
511 }
514 }
517 }
519 /*
520 ** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
521 ** where X is a reference to the iColumn of table iCur or of index pIdx
522 ** if pIdx!=0 and <op> is one of the WO_xx operator codes specified by
523 ** the op parameter. Return a pointer to the term. Return 0 if not found.
524 **
525 ** If pIdx!=0 then it must be one of the indexes of table iCur.
526 ** Search for terms matching the iColumn-th column of pIdx
527 ** rather than the iColumn-th column of table iCur.
528 **
529 ** The term returned might by Y=<expr> if there is another constraint in
530 ** the WHERE clause that specifies that X=Y. Any such constraints will be
531 ** identified by the WO_EQUIV bit in the pTerm->eOperator field. The
532 ** aiCur[]/iaColumn[] arrays hold X and all its equivalents. There are 11
533 ** slots in aiCur[]/aiColumn[] so that means we can look for X plus up to 10
534 ** other equivalent values. Hence a search for X will return <expr> if X=A1
535 ** and A1=A2 and A2=A3 and ... and A9=A10 and A10=<expr>.
536 **
537 ** If there are multiple terms in the WHERE clause of the form "X <op> <expr>"
538 ** then try for the one with no dependencies on <expr> - in other words where
539 ** <expr> is a constant expression of some kind. Only return entries of
540 ** the form "X <op> Y" where Y is a column in another table if no terms of
541 ** the form "X <op> <const-expr>" exist. If no terms with a constant RHS
542 ** exist, try to return a term that does not use WO_EQUIV.
543 */
551 ){
554 WhereScan scan;
563 }
565 }
567 }
569 }
571 /*
572 ** This function searches pList for an entry that matches the iCol-th column
573 ** of index pIdx.
574 **
575 ** If such an expression is found, its index in pList->a[] is returned. If
576 ** no expression is found, -1 is returned.
577 */
584 ){
594 ){
598 }
599 }
600 }
603 }
605 /*
606 ** Return TRUE if the iCol-th column of index pIdx is NOT NULL
607 */
621 }
622 }
624 /*
625 ** Return true if the DISTINCT expression-list passed as the third argument
626 ** is redundant.
627 **
628 ** A DISTINCT list is redundant if any subset of the columns in the
629 ** DISTINCT list are collectively unique and individually non-null.
630 */
636 ){
642 /* If there is more than one table or sub-select in the FROM clause of
643 ** this query, then it will not be possible to show that the DISTINCT
644 ** clause is redundant. */
649 /* If any of the expressions is an IPK column on table iBase, then return
650 ** true. Note: The (p->iTable==iBase) part of this test may be false if the
651 ** current SELECT is a correlated sub-query.
652 */
658 }
660 /* Loop through all indices on the table, checking each to see if it makes
661 ** the DISTINCT qualifier redundant. It does so if:
662 **
663 ** 1. The index is itself UNIQUE, and
664 **
665 ** 2. All of the columns in the index are either part of the pDistinct
666 ** list, or else the WHERE clause contains a term of the form "col=X",
667 ** where X is a constant value. The collation sequences of the
668 ** comparison and select-list expressions must match those of the index.
669 **
670 ** 3. All of those index columns for which the WHERE clause does not
671 ** contain a "col=X" term are subject to a NOT NULL constraint.
672 */
680 }
681 }
683 /* This index implies that the DISTINCT qualifier is redundant. */
685 }
686 }
689 }
692 /*
693 ** Estimate the logarithm of the input value to base 2.
694 */
697 }
699 /*
700 ** Convert OP_Column opcodes to OP_Copy in previously generated code.
701 **
702 ** This routine runs over generated VDBE code and translates OP_Column
703 ** opcodes into OP_Copy when the table is being accessed via co-routine
704 ** instead of via table lookup.
705 **
706 ** If the iAutoidxCur is not zero, then any OP_Rowid instructions on
707 ** cursor iTabCur are transformed into OP_Sequence opcode for the
708 ** iAutoidxCur cursor, in order to generate unique rowids for the
709 ** automatic index being generated.
710 */
717 ){
725 #ifdef SQLITE_DEBUG
728 }
729 #endif
736 #ifdef SQLITE_DEBUG
739 }
740 #endif
743 #ifdef SQLITE_ALLOW_ROWID_IN_VIEW
747 }
748 #endif
749 }
750 }
751 }
753 /*
754 ** Two routines for printing the content of an sqlite3_index_info
755 ** structure. Used for testing and debugging only. If neither
756 ** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines
757 ** are no-ops.
758 */
759 #if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(WHERETRACE_ENABLED)
763 ){
770 i,
776 }
779 i,
782 }
783 }
787 ){
793 i,
796 }
802 }
803 #else
804 #define whereTraceIndexInfoInputs(A,B)
805 #define whereTraceIndexInfoOutputs(A,B)
806 #endif
808 /*
809 ** We know that pSrc is an operand of an outer join. Return true if
810 ** pTerm is a constraint that is compatible with that join.
811 **
812 ** pTerm must be EP_OuterON if pSrc is the right operand of an
813 ** outer join. pTerm can be either EP_OuterON or EP_InnerON if pSrc
814 ** is the left operand of a RIGHT join.
815 **
816 ** See https://sqlite.org/forum/forumpost/206d99a16dd9212f
817 ** for an example of a WHERE clause constraints that may not be used on
818 ** the right table of a RIGHT JOIN because the constraint implies a
819 ** not-NULL condition on the left table of the RIGHT JOIN.
820 */
824 ){
832 ){
834 }
837 ){
839 }
841 }
845 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
846 /*
847 ** Return TRUE if the WHERE clause term pTerm is of a form where it
848 ** could be used with an index to access pSrc, assuming an appropriate
849 ** index existed.
850 */
855 ){
862 ){
864 }
872 }
873 #endif
876 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
878 #ifdef SQLITE_ENABLE_STMT_SCANSTATUS
879 /*
880 ** Argument pIdx represents an automatic index that the current statement
881 ** will create and populate. Add an OP_Explain with text of the form:
882 **
883 ** CREATE AUTOMATIC INDEX ON <table>(<cols>) [WHERE <expr>]
884 **
885 ** This is only required if sqlite3_stmt_scanstatus() is enabled, to
886 ** associate an SQLITE_SCANSTAT_NCYCLE and SQLITE_SCANSTAT_NLOOP
887 ** values with. In order to avoid breaking legacy code and test cases,
888 ** the OP_Explain is not added if this is an EXPLAIN QUERY PLAN command.
889 */
895 ){
912 }
919 );
921 }
922 }
923 }
924 #else
925 # define explainAutomaticIndex(a,b,c,d)
926 #endif
928 /*
929 ** Generate code to construct the Index object for an automatic index
930 ** and to set up the WhereLevel object pLevel so that the code generator
931 ** makes use of the automatic index.
932 */
938 ){
964 #ifdef SQLITE_ENABLE_STMT_SCANSTATUS
966 #endif
968 /* Generate code to skip over the creation and initialization of the
969 ** transient index on 2nd and subsequent iterations of the loop. */
974 /* Count the number of columns that will be added to the index
975 ** and used to match WHERE clause constraints */
985 /* Make the automatic index a partial index if there are terms in the
986 ** WHERE clause (or the ON clause of a LEFT join) that constrain which
987 ** rows of the target table (pSrc) that can be used. */
990 ){
993 }
996 Bitmask cMask;
1007 }
1011 }
1014 }
1015 }
1016 }
1022 /* Count the number of additional columns needed to create a
1023 ** covering index. A "covering index" is an index that contains all
1024 ** columns that are needed by the query. With a covering index, the
1025 ** original table never needs to be accessed. Automatic indices must
1026 ** be a covering index because the index will not be updated if the
1027 ** original table changes and the index and table cannot both be used
1028 ** if they go out of sync.
1029 */
1034 }
1040 }
1043 }
1045 /* Construct the Index object to describe this index */
1056 Bitmask cMask;
1069 n++;
1072 ){
1073 /* TUNING: only use a Bloom filter on an automatic index
1074 ** if one or more key columns has the ability to hold numeric
1075 ** values, since strings all have the same hash in the Bloom
1076 ** filter implementation and hence a Bloom filter on a text column
1077 ** is not usually helpful. */
1079 }
1080 }
1081 }
1082 }
1085 /* Add additional columns needed to make the automatic index into
1086 ** a covering index */
1091 n++;
1092 }
1093 }
1098 n++;
1099 }
1100 }
1105 /* Create the automatic index */
1116 }
1118 /* Fill the automatic index with content */
1129 }
1134 }
1138 );
1142 }
1158 }
1162 /* Jump here when skipping the initialization */
1166 end_auto_index_create:
1168 }
1171 /*
1172 ** Generate bytecode that will initialize a Bloom filter that is appropriate
1173 ** for pLevel.
1174 **
1175 ** If there are inner loops within pLevel that have the WHERE_BLOOMFILTER
1176 ** flag set, initialize a Bloomfilter for them as well. Except don't do
1177 ** this recursive initialization if the SQLITE_BloomPulldown optimization has
1178 ** been turned off.
1179 **
1180 ** When the Bloom filter is initialized, the WHERE_BLOOMFILTER flag is cleared
1181 ** from the loop, but the regFilter value is set to a register that implements
1182 ** the Bloom filter. When regFilter is positive, the
1183 ** sqlite3WhereCodeOneLoopStart() will generate code to test the Bloom filter
1184 ** and skip the subsequence B-Tree seek if the Bloom filter indicates that
1185 ** no matching rows exist.
1186 **
1187 ** This routine may only be called if it has previously been determined that
1188 ** the loop would benefit from a Bloom filter, and the WHERE_BLOOMFILTER bit
1189 ** is set.
1190 */
1195 Bitmask notReady /* Loops that are not ready */
1196 ){
1224 u64 sz;
1231 /* The Bloom filter is a Blob held in a register. Initialize it
1232 ** to zero-filled blob of at least 80K bits, but maybe more if the
1233 ** estimated size of the table is larger. We could actually
1234 ** measure the size of the table at run-time using OP_Count with
1235 ** P3==1 and use that value to initialize the blob. But that makes
1236 ** testing complicated. By basing the blob size on the value in the
1237 ** sqlite_stat1 table, testing is much easier.
1238 */
1250 }
1259 ){
1261 }
1262 }
1276 }
1279 }
1295 ==WHERE_BLOOMFILTER
1296 ){
1297 /* This is a candidate for bloom-filter pull-down (early evaluation).
1298 ** The test that WHERE_COLUMN_IN is omitted is important, as we are
1299 ** not able to do early evaluation of bloom filters that make use of
1300 ** the IN operator */
1302 }
1303 }
1308 }
1311 #ifndef SQLITE_OMIT_VIRTUALTABLE
1312 /*
1313 ** Allocate and populate an sqlite3_index_info structure. It is the
1314 ** responsibility of the caller to eventually release the structure
1315 ** by passing the pointer returned by this function to freeIndexInfo().
1316 */
1323 ){
1344 /* Find all WHERE clause constraints referring to this virtual table.
1345 ** Mark each term with the TERM_OK flag. Set nTerm to the number of
1346 ** terms found.
1347 */
1365 ){
1367 }
1368 nTerm++;
1370 }
1372 /* If the ORDER BY clause contains only columns in the current
1373 ** virtual table then allocate space for the aOrderBy part of
1374 ** the sqlite3_index_info structure.
1375 */
1383 /* Skip over constant terms in the ORDER BY clause */
1386 }
1388 /* Virtual tables are unable to deal with NULLS FIRST */
1391 /* First case - a direct column references without a COLLATE operator */
1395 }
1397 /* 2nd case - a column reference with a COLLATE operator. Only match
1398 ** of the COLLATE operator matches the collation of the column. */
1402 ){
1412 }
1414 /* No matches cause a break out of the loop */
1416 }
1423 }
1424 }
1425 }
1427 /* Allocate the sqlite3_index_info structure
1428 */
1436 }
1449 u16 op;
1457 }
1459 }
1467 }
1470 /* The direct assignment in the previous line is possible only because
1471 ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical. The
1472 ** following asserts verify this fact. */
1482 ){
1487 }
1488 }
1490 j++;
1491 }
1502 j++;
1503 }
1508 }
1510 /*
1511 ** Free an sqlite3_index_info structure allocated by allocateIndexInfo()
1512 ** and possibly modified by xBestIndex methods.
1513 */
1524 }
1526 }
1528 /*
1529 ** The table object reference passed as the second argument to this function
1530 ** must represent a virtual table. This function invokes the xBestIndex()
1531 ** method of the virtual table with the sqlite3_index_info object that
1532 ** comes in as the 3rd argument to this function.
1533 **
1534 ** If an error occurs, pParse is populated with an error message and an
1535 ** appropriate error code is returned. A return of SQLITE_CONSTRAINT from
1536 ** xBestIndex is not considered an error. SQLITE_CONSTRAINT indicates that
1537 ** the current configuration of "unusable" flags in sqlite3_index_info can
1538 ** not result in a valid plan.
1539 **
1540 ** Whether or not an error is returned, it is the responsibility of the
1541 ** caller to eventually free p->idxStr if p->needToFreeIdxStr indicates
1542 ** that this is required.
1543 */
1561 }
1562 }
1565 }
1569 }
1572 #ifdef SQLITE_ENABLE_STAT4
1573 /*
1574 ** Estimate the location of a particular key among all keys in an
1575 ** index. Store the results in aStat as follows:
1576 **
1577 ** aStat[0] Est. number of rows less than pRec
1578 ** aStat[1] Est. number of rows equal to pRec
1579 **
1580 ** Return the index of the sample that is the smallest sample that
1581 ** is greater than or equal to pRec. Note that this index is not an index
1582 ** into the aSample[] array - it is an index into a virtual set of samples
1583 ** based on the contents of aSample[] and the number of fields in record
1584 ** pRec.
1585 */
1592 ){
1603 #ifndef SQLITE_DEBUG
1605 #endif
1611 /* Do a binary search to find the first sample greater than or equal
1612 ** to pRec. If pRec contains a single field, the set of samples to search
1613 ** is simply the aSample[] array. If the samples in aSample[] contain more
1614 ** than one fields, all fields following the first are ignored.
1615 **
1616 ** If pRec contains N fields, where N is more than one, then as well as the
1617 ** samples in aSample[] (truncated to N fields), the search also has to
1618 ** consider prefixes of those samples. For example, if the set of samples
1619 ** in aSample is:
1620 **
1621 ** aSample[0] = (a, 5)
1622 ** aSample[1] = (a, 10)
1623 ** aSample[2] = (b, 5)
1624 ** aSample[3] = (c, 100)
1625 ** aSample[4] = (c, 105)
1626 **
1627 ** Then the search space should ideally be the samples above and the
1628 ** unique prefixes [a], [b] and [c]. But since that is hard to organize,
1629 ** the code actually searches this set:
1630 **
1631 ** 0: (a)
1632 ** 1: (a, 5)
1633 ** 2: (a, 10)
1634 ** 3: (a, 10)
1635 ** 4: (b)
1636 ** 5: (b, 5)
1637 ** 6: (c)
1638 ** 7: (c, 100)
1639 ** 8: (c, 105)
1640 ** 9: (c, 105)
1641 **
1642 ** For each sample in the aSample[] array, N samples are present in the
1643 ** effective sample array. In the above, samples 0 and 1 are based on
1644 ** sample aSample[0]. Samples 2 and 3 on aSample[1] etc.
1645 **
1646 ** Often, sample i of each block of N effective samples has (i+1) fields.
1647 ** Except, each sample may be extended to ensure that it is greater than or
1648 ** equal to the previous sample in the array. For example, in the above,
1649 ** sample 2 is the first sample of a block of N samples, so at first it
1650 ** appears that it should be 1 field in size. However, that would make it
1651 ** smaller than sample 1, so the binary search would not work. As a result,
1652 ** it is extended to two fields. The duplicates that this creates do not
1653 ** cause any problems.
1654 */
1659 }
1670 /* The proposed effective sample is a prefix of sample aSample[iSamp].
1671 ** Specifically, the shortest prefix of at least (1 + iTest%nField)
1672 ** fields that is greater than the previous effective sample. */
1675 }
1678 }
1692 }
1696 #ifdef SQLITE_DEBUG
1697 /* The following assert statements check that the binary search code
1698 ** above found the right answer. This block serves no purpose other
1699 ** than to invoke the asserts. */
1702 /* If (res==0) is true, then pRec must be equal to sample i. */
1708 );
1710 /* Unless i==pIdx->nSample, indicating that pRec is larger than
1711 ** all samples in the aSample[] array, pRec must be smaller than the
1712 ** (iCol+1) field prefix of sample i. */
1719 /* if i==0 and iCol==0, then record pRec is smaller than all samples
1720 ** in the aSample[] array. Otherwise, if (iCol>0) then pRec must
1721 ** be greater than or equal to the (iCol) field prefix of sample i.
1722 ** If (i>0), then pRec must also be greater than sample (i-1). */
1727 }
1732 }
1733 }
1734 }
1738 /* Record pRec is equal to sample i */
1743 /* At this point, the (iCol+1) field prefix of aSample[i] is the first
1744 ** sample that is greater than pRec. Or, if i==pIdx->nSample then pRec
1745 ** is larger than all samples in the array. */
1751 }
1757 }
1762 }
1765 }
1767 /* Restore the pRec->nField value before returning. */
1770 }
1773 /*
1774 ** If it is not NULL, pTerm is a term that provides an upper or lower
1775 ** bound on a range scan. Without considering pTerm, it is estimated
1776 ** that the scan will visit nNew rows. This function returns the number
1777 ** estimated to be visited after taking pTerm into account.
1778 **
1779 ** If the user explicitly specified a likelihood() value for this term,
1780 ** then the return value is the likelihood multiplied by the number of
1781 ** input rows. Otherwise, this function assumes that an "IS NOT NULL" term
1782 ** has a likelihood of 0.50, and any other term a likelihood of 0.25.
1783 */
1791 }
1792 }
1794 }
1797 #ifdef SQLITE_ENABLE_STAT4
1798 /*
1799 ** Return the affinity for a single column of an index.
1800 */
1805 }
1808 }
1809 #endif
1812 #ifdef SQLITE_ENABLE_STAT4
1813 /*
1814 ** This function is called to estimate the number of rows visited by a
1815 ** range-scan on a skip-scan index. For example:
1816 **
1817 ** CREATE INDEX i1 ON t1(a, b, c);
1818 ** SELECT * FROM t1 WHERE a=? AND c BETWEEN ? AND ?;
1819 **
1820 ** Value pLoop->nOut is currently set to the estimated number of rows
1821 ** visited for scanning (a=? AND b=?). This function reduces that estimate
1822 ** by some factor to account for the (c BETWEEN ? AND ?) expression based
1823 ** on the stat4 data for the index. this scan will be performed multiple
1824 ** times (once for each (a,b) combination that matches a=?) is dealt with
1825 ** by the caller.
1826 **
1827 ** It does this by scanning through all stat4 samples, comparing values
1828 ** extracted from pLower and pUpper with the corresponding column in each
1829 ** sample. If L and U are the number of samples found to be less than or
1830 ** equal to the values extracted from pLower and pUpper respectively, and
1831 ** N is the total number of samples, the pLoop->nOut value is adjusted
1832 ** as follows:
1833 **
1834 ** nOut = nOut * ( min(U - L, 1) / N )
1835 **
1836 ** If pLower is NULL, or a value cannot be extracted from the term, L is
1837 ** set to zero. If pUpper is NULL, or a value cannot be extracted from it,
1838 ** U is set to N.
1839 **
1840 ** Normally, this function sets *pbDone to 1 before returning. However,
1841 ** if no value can be extracted from either pLower or pUpper (and so the
1842 ** estimate of the number of rows delivered remains unchanged), *pbDone
1843 ** is left as is.
1844 **
1845 ** If an error occurs, an SQLite error code is returned. Otherwise,
1846 ** SQLITE_OK.
1847 */
1854 ){
1872 }
1876 }
1886 }
1890 }
1891 }
1895 /* If there is both an upper and lower bound specified, and the
1896 ** comparisons indicate that they are close together, use the fallback
1897 ** method (assume that the scan visits 1/64 of the rows) for estimating
1898 ** the number of rows visited. Otherwise, estimate the number of rows
1899 ** using the method described in the header comment for this function. */
1906 }
1910 }
1917 }
1920 /*
1921 ** This function is used to estimate the number of rows that will be visited
1922 ** by scanning an index for a range of values. The range may have an upper
1923 ** bound, a lower bound, or both. The WHERE clause terms that set the upper
1924 ** and lower bounds are represented by pLower and pUpper respectively. For
1925 ** example, assuming that index p is on t1(a):
1926 **
1927 ** ... FROM t1 WHERE a > ? AND a < ? ...
1928 ** |_____| |_____|
1929 ** | |
1930 ** pLower pUpper
1931 **
1932 ** If either of the upper or lower bound is not present, then NULL is passed in
1933 ** place of the corresponding WhereTerm.
1934 **
1935 ** The value in (pBuilder->pNew->u.btree.nEq) is the number of the index
1936 ** column subject to the range constraint. Or, equivalently, the number of
1937 ** equality constraints optimized by the proposed index scan. For example,
1938 ** assuming index p is on t1(a, b), and the SQL query is:
1939 **
1940 ** ... FROM t1 WHERE a = ? AND b > ? AND b < ? ...
1941 **
1942 ** then nEq is set to 1 (as the range restricted column, b, is the second
1943 ** left-most column of the index). Or, if the query is:
1944 **
1945 ** ... FROM t1 WHERE a > ? AND a < ? ...
1946 **
1947 ** then nEq is set to 0.
1948 **
1949 ** When this function is called, *pnOut is set to the sqlite3LogEst() of the
1950 ** number of rows that the index scan is expected to visit without
1951 ** considering the range constraints. If nEq is 0, then *pnOut is the number of
1952 ** rows in the index. Assuming no error occurs, *pnOut is adjusted (reduced)
1953 ** to account for the range constraints pLower and pUpper.
1954 **
1955 ** In the absence of sqlite_stat4 ANALYZE data, or if such data cannot be
1956 ** used, a single range inequality reduces the search space by a factor of 4.
1957 ** and a pair of constraints (x>? AND x<?) reduces the expected number of
1958 ** rows visited by a factor of 64.
1959 */
1966 ){
1969 LogEst nNew;
1971 #ifdef SQLITE_ENABLE_STAT4
1977 ){
1984 /* Variable iLower will be set to the estimate of the number of rows in
1985 ** the index that are less than the lower bound of the range query. The
1986 ** lower bound being the concatenation of $P and $L, where $P is the
1987 ** key-prefix formed by the nEq values matched against the nEq left-most
1988 ** columns of the index, and $L is the value in pLower.
1989 **
1990 ** Or, if pLower is NULL or $L cannot be extracted from it (because it
1991 ** is not a simple variable or literal value), the lower bound of the
1992 ** range is $P. Due to a quirk in the way whereKeyStats() works, even
1993 ** if $L is available, whereKeyStats() is called for both ($P) and
1994 ** ($P:$L) and the larger of the two returned values is used.
1995 **
1996 ** Similarly, iUpper is to be set to the estimate of the number of rows
1997 ** less than the upper bound of the range query. Where the upper bound
1998 ** is either ($P) or ($P:$U). Again, even if $U is available, both values
1999 ** of iUpper are requested of whereKeyStats() and the smaller used.
2000 **
2001 ** The number of rows between the two bounds is then just iUpper-iLower.
2002 */
2011 }
2012 /* Determine iLower and iUpper using ($P) only. */
2017 /* Note: this call could be optimized away - since the same values must
2018 ** have been requested when testing key $P in whereEqualScanEst(). */
2022 }
2028 /* The roles of pLower and pUpper are swapped for a DESC index */
2031 }
2033 /* If possible, improve on the iLower estimate using ($P:$L). */
2039 tRowcnt iNew;
2045 nOut--;
2047 }
2048 }
2050 /* If possible, improve on the iUpper estimate using ($P:$U). */
2056 tRowcnt iNew;
2062 nOut--;
2064 }
2065 }
2071 /* TUNING: If both iUpper and iLower are derived from the same
2072 ** sample, then assume they are 4x more selective. This brings
2073 ** the estimated selectivity more in line with what it would be
2074 ** if estimated without the use of STAT4 tables. */
2079 }
2082 }
2085 }
2090 }
2091 }
2092 #else
2096 #endif
2101 /* TUNING: If there is both an upper and lower limit and neither limit
2102 ** has an application-defined likelihood(), assume the range is
2103 ** reduced by an additional 75%. This means that, by default, an open-ended
2104 ** range query (e.g. col > ?) is assumed to match 1/4 of the rows in the
2105 ** index. While a closed range (e.g. col BETWEEN ? AND ?) is estimated to
2106 ** match 1/64 of the index. */
2109 }
2114 #if defined(WHERETRACE_ENABLED)
2118 }
2119 #endif
2122 }
2124 #ifdef SQLITE_ENABLE_STAT4
2125 /*
2126 ** Estimate the number of rows that will be returned based on
2127 ** an equality constraint x=VALUE and where that VALUE occurs in
2128 ** the histogram data. This only works when x is the left-most
2129 ** column of an index and sqlite_stat4 histogram data is available
2130 ** for that index. When pExpr==NULL that means the constraint is
2131 ** "x IS NULL" instead of "x=VALUE".
2132 **
2133 ** Write the estimated row count into *pnRow and return SQLITE_OK.
2134 ** If unable to make an estimate, leave *pnRow unchanged and return
2135 ** non-zero.
2136 **
2137 ** This routine can fail if it is unable to load a collating sequence
2138 ** required for string comparison, or if unable to allocate memory
2139 ** for a UTF conversion required for comparison. The error is stored
2140 ** in the pParse structure.
2141 */
2147 ){
2161 /* If values are not available for all fields of the index to the left
2162 ** of this one, no estimate can be made. Return SQLITE_NOTFOUND. */
2165 }
2167 /* This is an optimization only. The call to sqlite3Stat4ProbeSetValue()
2168 ** below would return the same value. */
2172 }
2186 }
2189 #ifdef SQLITE_ENABLE_STAT4
2190 /*
2191 ** Estimate the number of rows that will be returned based on
2192 ** an IN constraint where the right-hand side of the IN operator
2193 ** is a list of values. Example:
2194 **
2195 ** WHERE x IN (1,2,3,4)
2196 **
2197 ** Write the estimated row count into *pnRow and return SQLITE_OK.
2198 ** If unable to make an estimate, leave *pnRow unchanged and return
2199 ** non-zero.
2200 **
2201 ** This routine can fail if it is unable to load a collating sequence
2202 ** required for string comparison, or if unable to allocate memory
2203 ** for a UTF conversion required for comparison. The error is stored
2204 ** in the pParse structure.
2205 */
2211 ){
2226 }
2232 }
2235 }
2239 #ifdef WHERETRACE_ENABLED
2240 /*
2241 ** Print the content of a WhereTerm object
2242 */
2263 }
2267 /* The 0x10000 .wheretrace flag causes extra information to be
2268 ** shown about each Term */
2272 }
2275 }
2278 }
2281 }
2282 }
2283 #endif
2285 #ifdef WHERETRACE_ENABLED
2286 /*
2287 ** Show the complete content of a WhereClause
2288 */
2293 }
2294 }
2295 #endif
2297 #ifdef WHERETRACE_ENABLED
2298 /*
2299 ** Print a WhereLoop object for debugging purposes
2300 **
2301 ** Format example:
2302 **
2303 ** .--- Position in WHERE clause rSetup, rRun, nOut ---.
2304 ** | |
2305 ** | .--- selfMask nTerm ------. |
2306 ** | | | |
2307 ** | | .-- prereq Idx wsFlags----. | |
2308 ** | | | Name | | |
2309 ** | | | __|__ nEq ---. ___|__ | __|__
2310 ** | / \ / \ / \ | / \ / \ / \
2311 ** 1.002.001 t2.t2xy 2 f 010241 N 2 cost 0,56,31
2312 */
2327 }
2335 }
2339 }
2347 }
2350 }
2355 }
2361 }
2362 }
2363 }
2366 }
2371 }
2372 }
2373 #endif
2375 /*
2376 ** Convert bulk memory into a valid WhereLoop that can be passed
2377 ** to whereLoopClear harmlessly.
2378 */
2384 }
2386 /*
2387 ** Clear the WhereLoop.u union. Leave WhereLoop.pLTerm intact.
2388 */
2399 }
2400 }
2401 }
2403 /*
2404 ** Deallocate internal memory used by a WhereLoop object. Leave the
2405 ** object in an initialized state, as if it had been newly allocated.
2406 */
2412 }
2416 }
2418 /*
2419 ** Increase the memory allocation for pLoop->aLTerm[] to be at least n.
2420 */
2432 }
2434 /*
2435 ** Transfer content from the second pLoop into the first.
2436 */
2441 ){
2444 }
2451 }
2453 }
2455 /*
2456 ** Delete a WhereLoop object
2457 */
2462 }
2464 /*
2465 ** Free a WhereInfo structure
2466 */
2475 }
2480 }
2482 }
2484 /*
2485 ** Return TRUE if X is a proper subset of Y but is of equal or less cost.
2486 ** In other words, return true if all constraints of X are also part of Y
2487 ** and Y has additional constraints that might speed the search that X lacks
2488 ** but the cost of running X is not more than the cost of running Y.
2489 **
2490 ** In other words, return true if the cost relationwship between X and Y
2491 ** is inverted and needs to be adjusted.
2492 **
2493 ** Case 1:
2494 **
2495 ** (1a) X and Y use the same index.
2496 ** (1b) X has fewer == terms than Y
2497 ** (1c) Neither X nor Y use skip-scan
2498 ** (1d) X does not have a a greater cost than Y
2499 **
2500 ** Case 2:
2501 **
2502 ** (2a) X has the same or lower cost, or returns the same or fewer rows,
2503 ** than Y.
2504 ** (2b) X uses fewer WHERE clause terms than Y
2505 ** (2c) Every WHERE clause term used by X is also used by Y
2506 ** (2d) X skips at least as many columns as Y
2507 ** (2e) If X is a covering index, than Y is too
2508 */
2512 ){
2520 ){
2522 }
2525 }
2531 }
2533 }
2537 }
2539 }
2541 /*
2542 ** Try to adjust the cost and number of output rows of WhereLoop pTemplate
2543 ** upwards or downwards so that:
2544 **
2545 ** (1) pTemplate costs less than any other WhereLoops that are a proper
2546 ** subset of pTemplate
2547 **
2548 ** (2) pTemplate costs more than any other WhereLoops for which pTemplate
2549 ** is a proper subset.
2550 **
2551 ** To say "WhereLoop X is a proper subset of Y" means that X uses fewer
2552 ** WHERE clause terms than Y and that every WHERE clause term used by X is
2553 ** also used by Y.
2554 */
2561 /* Adjust pTemplate cost downward so that it is cheaper than its
2562 ** subset p. */
2570 /* Adjust pTemplate cost upward so that it is costlier than p since
2571 ** pTemplate is a proper subset of p */
2578 }
2579 }
2580 }
2582 /*
2583 ** Search the list of WhereLoops in *ppPrev looking for one that can be
2584 ** replaced by pTemplate.
2585 **
2586 ** Return NULL if pTemplate does not belong on the WhereLoop list.
2587 ** In other words if pTemplate ought to be dropped from further consideration.
2588 **
2589 ** If pX is a WhereLoop that pTemplate can replace, then return the
2590 ** link that points to pX.
2591 **
2592 ** If pTemplate cannot replace any existing element of the list but needs
2593 ** to be added to the list as a new entry, then return a pointer to the
2594 ** tail of the list.
2595 */
2599 ){
2603 /* If either the iTab or iSortIdx values for two WhereLoop are different
2604 ** then those WhereLoops need to be considered separately. Neither is
2605 ** a candidate to replace the other. */
2607 }
2608 /* In the current implementation, the rSetup value is either zero
2609 ** or the cost of building an automatic index (NlogN) and the NlogN
2610 ** is the same for compatible WhereLoops. */
2614 /* whereLoopAddBtree() always generates and inserts the automatic index
2615 ** case first. Hence compatible candidate WhereLoops never have a larger
2616 ** rSetup. Call this SETUP-INVARIANT */
2619 /* Any loop using an application-defined index (or PRIMARY KEY or
2620 ** UNIQUE constraint) with one or more == constraints is better
2621 ** than an automatic index. Unless it is a skip-scan. */
2627 ){
2629 }
2631 /* If existing WhereLoop p is better than pTemplate, pTemplate can be
2632 ** discarded. WhereLoop p is better if:
2633 ** (1) p has no more dependencies than pTemplate, and
2634 ** (2) p has an equal or lower cost than pTemplate
2635 */
2640 ){
2642 }
2644 /* If pTemplate is always better than p, then cause p to be overwritten
2645 ** with pTemplate. pTemplate is better than p if:
2646 ** (1) pTemplate has no more dependencies than p, and
2647 ** (2) pTemplate has an equal or lower cost than p.
2648 */
2652 ){
2655 }
2656 }
2658 }
2660 /*
2661 ** Insert or replace a WhereLoop entry using the template supplied.
2662 **
2663 ** An existing WhereLoop entry might be overwritten if the new template
2664 ** is better and has fewer dependencies. Or the template will be ignored
2665 ** and no insert will occur if an existing WhereLoop is faster and has
2666 ** fewer dependencies than the template. Otherwise a new WhereLoop is
2667 ** added based on the template.
2668 **
2669 ** If pBuilder->pOrSet is not NULL then we care about only the
2670 ** prerequisites and rRun and nOut costs of the N best loops. That
2671 ** information is gathered in the pBuilder->pOrSet object. This special
2672 ** processing mode is used only for OR clause processing.
2673 **
2674 ** When accumulating multiple loops (when pBuilder->pOrSet is NULL) we
2675 ** still might overwrite similar loops with the new template if the
2676 ** new template is better. Loops may be overwritten if the following
2677 ** conditions are met:
2678 **
2679 ** (1) They have the same iTab.
2680 ** (2) They have the same iSortIdx.
2681 ** (3) The template has same or fewer dependencies than the current loop
2682 ** (4) The template has the same or lower cost than the current loop
2683 */
2690 /* Stop the search once we hit the query planner search limit */
2695 }
2700 /* If pBuilder->pOrSet is defined, then only keep track of the costs
2701 ** and prereqs.
2702 */
2705 #if WHERETRACE_ENABLED
2708 #endif
2715 }
2716 #endif
2717 }
2719 }
2721 /* Look for an existing WhereLoop to replace with pTemplate
2722 */
2726 /* There already exists a WhereLoop on the list that is better
2727 ** than pTemplate, so just ignore pTemplate */
2732 }
2733 #endif
2737 }
2739 /* If we reach this point it means that either p[] should be overwritten
2740 ** with pTemplate[] if p[] exists, or if p==NULL then allocate a new
2741 ** WhereLoop and insert it.
2742 */
2751 }
2753 }
2754 #endif
2756 /* Allocate a new WhereLoop to add to the end of the list */
2762 /* We will be overwriting WhereLoop p[]. But before we do, first
2763 ** go through the rest of the list and delete any other entries besides
2764 ** p[] that are also supplanted by pTemplate */
2777 }
2778 #endif
2780 }
2781 }
2787 }
2788 }
2790 }
2792 /*
2793 ** Adjust the WhereLoop.nOut value downward to account for terms of the
2794 ** WHERE clause that reference the loop but which are not used by an
2795 ** index.
2796 *
2797 ** For every WHERE clause term that is not used by the index
2798 ** and which has a truth probability assigned by one of the likelihood(),
2799 ** likely(), or unlikely() SQL functions, reduce the estimated number
2800 ** of output rows by the probability specified.
2801 **
2802 ** TUNING: For every WHERE clause term that is not used by the index
2803 ** and which does not have an assigned truth probability, heuristics
2804 ** described below are used to try to estimate the truth probability.
2805 ** TODO --> Perhaps this is something that could be improved by better
2806 ** table statistics.
2807 **
2808 ** Heuristic 1: Estimate the truth probability as 93.75%. The 93.75%
2809 ** value corresponds to -1 in LogEst notation, so this means decrement
2810 ** the WhereLoop.nOut field for every such WHERE clause term.
2811 **
2812 ** Heuristic 2: If there exists one or more WHERE clause terms of the
2813 ** form "x==EXPR" and EXPR is not a constant 0 or 1, then make sure the
2814 ** final output row estimate is no greater than 1/4 of the total number
2815 ** of rows in the table. In other words, assume that x==EXPR will filter
2816 ** out at least 3 out of 4 rows. If EXPR is -1 or 0 or 1, then maybe the
2817 ** "x" column is boolean or else -1 or 0 or 1 is a common default value
2818 ** on the "x" column and so in that case only cap the output row estimate
2819 ** at 1/2 instead of 1/4.
2820 */
2824 LogEst nRow /* Number of rows in the entire table */
2825 ){
2842 }
2846 /* If there are extra terms in the WHERE clause not used by an index
2847 ** that depend only on the table being scanned, and that will tend to
2848 ** cause many rows to be omitted, then mark that table as
2849 ** "self-culling".
2850 **
2851 ** 2022-03-24: Self-culling only applies if either the extra terms
2852 ** are straight comparison operators that are non-true with NULL
2853 ** operand, or if the loop is not an OUTER JOIN.
2854 */
2858 ){
2860 }
2861 }
2863 /* If a truth probability is specified using the likelihood() hints,
2864 ** then use the probability provided by the application. */
2867 /* In the absence of explicit truth probabilities, use heuristics to
2868 ** guess a reasonable truth probability. */
2872 ){
2880 }
2884 }
2885 }
2886 }
2887 }
2888 }
2891 }
2892 }
2894 /*
2895 ** Term pTerm is a vector range comparison operation. The first comparison
2896 ** in the vector can be optimized using column nEq of the index. This
2897 ** function returns the total number of vector elements that can be used
2898 ** as part of the range comparison.
2899 **
2900 ** For example, if the query is:
2901 **
2902 ** WHERE a = ? AND (b, c, d) > (?, ?, ?)
2903 **
2904 ** and the index:
2905 **
2906 ** CREATE INDEX ... ON (a, b, c, d, e)
2907 **
2908 ** then this function would be invoked with nEq=1. The value returned in
2909 ** this case is 3.
2910 */
2917 ){
2923 /* Test if comparison i of pTerm is compatible with column (i+nEq)
2924 ** of the index. If not, exit the loop. */
2937 }
2939 /* Check that the LHS of the comparison is a column reference to
2940 ** the right column of the right source table. And that the sort
2941 ** order of the index column is the same as the sort order of the
2942 ** leftmost index column. */
2947 ){
2949 }
2959 }
2961 }
2963 /*
2964 ** Adjust the cost C by the costMult factor T. This only occurs if
2965 ** compiled with -DSQLITE_ENABLE_COSTMULT
2966 */
2967 #ifdef SQLITE_ENABLE_COSTMULT
2968 # define ApplyCostMultiplier(C,T) C += T
2969 #else
2970 # define ApplyCostMultiplier(C,T)
2971 #endif
2973 /*
2974 ** We have so far matched pBuilder->pNew->u.btree.nEq terms of the
2975 ** index pIndex. Try to match one more.
2976 **
2977 ** When this function is called, pBuilder->pNew->nOut contains the
2978 ** number of rows expected to be visited by filtering using the nEq
2979 ** terms only. If it is modified, this value is restored before this
2980 ** function returns.
2981 **
2982 ** If pProbe->idxType==SQLITE_IDXTYPE_IPK, that means pIndex is
2983 ** a fake index used for the INTEGER PRIMARY KEY.
2984 */
2989 LogEst nInMul /* log(Number of iterations due to IN) */
2990 ){
3015 }
3027 }
3032 }
3033 }
3054 LogEst rCostIdx;
3057 #ifdef SQLITE_ENABLE_STAT4
3059 #endif
3062 ){
3064 }
3067 /* Do not allow the upper bound of a LIKE optimization range constraint
3068 ** to mix with a lower range bound from some other source */
3073 ){
3075 }
3080 }
3088 ){
3090 }
3098 );
3103 /* "x IN (SELECT ...)": TUNING: the SELECT returns 25 rows */
3107 /* The expression may actually be of the form (x, y) IN (SELECT...).
3108 ** In this case there is a separate term for each of (x) and (y).
3109 ** However, the nIn multiplier should only be applied once, not once
3110 ** for each such term. The following loop checks that pTerm is the
3111 ** first such term in use, and sets nIn back to 0 if it is not. */
3114 }
3116 /* "x IN (value, value, ...)" */
3118 }
3121 /* Let:
3122 ** N = the total number of rows in the table
3123 ** K = the number of entries on the RHS of the IN operator
3124 ** M = the number of rows in the table that match terms to the
3125 ** to the left in the same index. If the IN operator is on
3126 ** the left-most index column, M==N.
3127 **
3128 ** Given the definitions above, it is better to omit the IN operator
3129 ** from the index lookup and instead do a scan of the M elements,
3130 ** testing each scanned row against the IN operator separately, if:
3131 **
3132 ** M*log(K) < K*log(N)
3133 **
3134 ** Our estimates for M, K, and N might be inaccurate, so we build in
3135 ** a safety margin of 2 (LogEst: 10) that favors using the IN operator
3136 ** with the index, as using an index has better worst-case behavior.
3137 ** If we do not have real sqlite_stat1 data, always prefer to use
3138 ** the index. Do not bother with this optimization on very small
3139 ** tables (less than 2 rows) as it is pointless in that case.
3140 */
3143 /* TUNING v----- 10 to bias toward indexed IN */
3162 }
3163 }
3171 ){
3174 ){
3178 }
3179 }
3186 );
3195 /* Range constraints that come from the LIKE optimization are
3196 ** always used in pairs. */
3205 }
3215 }
3216 }
3218 /* At this point pNew->nOut is set to the number of rows expected to
3219 ** be visited by the index scan before considering term pTerm, or the
3220 ** values of nIn and nInMul. In other words, assuming that all
3221 ** "x IN(...)" terms are replaced with "x = ?". This block updates
3222 ** the value of pNew->nOut to account for pTerm (but not nIn/nInMul). */
3225 /* Adjust nOut using stat4 data. Or, if there is no stat4
3226 ** data, using some other estimate. */
3239 #ifdef SQLITE_ENABLE_STAT4
3246 ){
3255 }
3261 /* TUNING: Mark terms as "low selectivity" if they seem likely
3262 ** to be true for half or more of the rows in the table.
3263 ** See tag-202002240-1 */
3265 ){
3271 }
3272 #endif
3275 /* If the term has previously been used with an assumption of
3276 ** higher selectivity, then set the flag to rerun the
3277 ** loop computations. */
3279 }
3280 }
3283 }
3284 }
3286 #endif
3287 {
3290 /* TUNING: If there is no likelihood() value, assume that a
3291 ** "col IS NULL" expression matches twice as many rows
3292 ** as (col=?). */
3294 }
3295 }
3296 }
3297 }
3299 /* Set rCostIdx to the estimated cost of visiting selected rows in the
3300 ** index. The estimate is the sum of two values:
3301 ** 1. The cost of doing one search-by-key to find the first matching
3302 ** entry
3303 ** 2. Stepping forward in the index pNew->nOut times to find all
3304 ** additional matching entries.
3305 */
3308 /* The pProbe->szIdxRow is low for an IPK table since the interior
3309 ** pages are small. Thus szIdxRow gives a good estimate of seek cost.
3310 ** But the leaf pages are full-size, so pProbe->szIdxRow would badly
3311 ** under-estimate the scanning cost. */
3315 }
3318 /* Estimate the cost of running the loop. If all data is coming
3319 ** from the index, then this is just the cost of doing the index
3320 ** lookup and scan. But if some data is coming out of the main table,
3321 ** we also have to add in the cost of doing pNew->nOut searches to
3322 ** locate the row in the main table that corresponds to the index entry.
3323 */
3327 }
3340 }
3346 ){
3349 }
3351 }
3353 #ifdef SQLITE_ENABLE_STAT4
3355 #endif
3356 }
3366 /* Consider using a skip-scan if there are no WHERE clause constraints
3367 ** available for the left-most terms of the index, and if the average
3368 ** number of repeats in the left-most terms is at least 18.
3369 **
3370 ** The magic number 18 is selected on the basis that scanning 17 rows
3371 ** is almost always quicker than an index seek (even though if the index
3372 ** contains fewer than 2^17 rows we assume otherwise in other parts of
3373 ** the code). And, even if it is not, it should not be too much slower.
3374 ** On the other hand, the extra seeks could end up being significantly
3375 ** more expensive. */
3385 ){
3386 LogEst nIter;
3393 /* TUNING: Because uncertainties in the estimates for skip-scan queries,
3394 ** add a 1.375 fudge factor to make skip-scan slightly less likely. */
3401 }
3406 }
3408 /*
3409 ** Return True if it is possible that pIndex might be useful in
3410 ** implementing the ORDER BY clause in pBuilder.
3411 **
3412 ** Return False if pBuilder does not contain an ORDER BY clause or
3413 ** if there is no way for pIndex to be useful in implementing that
3414 ** ORDER BY clause.
3415 */
3419 int iCursor
3420 ){
3432 ){
3436 }
3442 }
3443 }
3444 }
3445 }
3447 }
3449 /* Check to see if a partial index with pPartIndexWhere can be used
3450 ** in the current query. Return true if it can be and false if not.
3451 */
3457 ){
3467 }
3476 ){
3478 }
3479 }
3481 }
3483 /*
3484 ** pIdx is an index containing expressions. Check it see if any of the
3485 ** expressions in the index match the pExpr expression.
3486 */
3490 int iTabCur
3491 ){
3496 ){
3498 }
3499 }
3501 }
3503 /*
3504 ** Structure passed to the whereIsCoveringIndex Walker callback.
3505 */
3512 };
3514 /*
3515 ** Information passed in is pWalk->u.pCovIdxCk. Call it pCk.
3516 **
3517 ** If the Expr node references the table with cursor pCk->iTabCur, then
3518 ** make sure that column is covered by the index pCk->pIdx. We know that
3519 ** all columns less than 63 (really BMS-1) are covered, so we don't need
3520 ** to check them. But we do need to check any column at 63 or greater.
3521 **
3522 ** If the index does not cover the column, then set pWalk->eCode to
3523 ** non-zero and return WRC_Abort to stop the search.
3524 **
3525 ** If this node does not disprove that the index can be a covering index,
3526 ** then just return WRC_Continue, to continue the search.
3527 **
3528 ** If pCk->pIdx contains indexed expressions and one of those expressions
3529 ** matches pExpr, then prune the search.
3530 */
3541 /* if( pExpr->iColumn<(BMS-1) && pIdx->bHasExpr==0 ) return WRC_Continue;*/
3548 }
3555 }
3557 }
3560 /*
3561 ** pIdx is an index that covers all of the low-number columns used by
3562 ** pWInfo->pSelect (columns from 0 through 62) or an index that has
3563 ** expressions terms. Hence, we cannot determine whether or not it is
3564 ** a covering index by using the colUsed bitmasks. We have to do a search
3565 ** to see if the index is covering. This routine does that search.
3566 **
3567 ** The return value is one of these:
3568 **
3569 ** 0 The index is definitely not a covering index
3570 **
3571 ** WHERE_IDX_ONLY The index is definitely a covering index
3572 **
3573 ** WHERE_EXPRIDX The index is likely a covering index, but it is
3574 ** difficult to determine precisely because of the
3575 ** expressions that are indexed. Score it as a
3576 ** covering index, but still keep the main table open
3577 ** just in case we need it.
3578 **
3579 ** This routine is an optimization. It is always safe to return zero.
3580 ** But returning one of the other two values when zero should have been
3581 ** returned can lead to incorrect bytecode and assertion faults.
3582 */
3587 ){
3590 Walker w;
3592 /* We don't have access to the full query, so we cannot check to see
3593 ** if pIdx is covering. Assume it is not. */
3595 }
3599 }
3601 /* pIdx does not index any columns greater than 62, but we know from
3602 ** colMask that columns greater than 62 are used, so this is not a
3603 ** covering index */
3605 }
3606 }
3622 }
3624 }
3626 /*
3627 ** This is an sqlite3ParserAddCleanup() callback that is invoked to
3628 ** free the Parse->pIdxEpr list when the Parse object is destroyed.
3629 */
3637 }
3638 }
3640 /*
3641 ** This function is called for a partial index - one with a WHERE clause - in
3642 ** two scenarios. In both cases, it determines whether or not the WHERE
3643 ** clause on the index implies that a column of the table may be safely
3644 ** replaced by a constant expression. For example, in the following
3645 ** SELECT:
3646 **
3647 ** CREATE INDEX i1 ON t1(b, c) WHERE a=<expr>;
3648 ** SELECT a, b, c FROM t1 WHERE a=<expr> AND b=?;
3649 **
3650 ** The "a" in the select-list may be replaced by <expr>, iff:
3651 **
3652 ** (a) <expr> is a constant expression, and
3653 ** (b) The (a=<expr>) comparison uses the BINARY collation sequence, and
3654 ** (c) Column "a" has an affinity other than NONE or BLOB.
3655 **
3656 ** If argument pItem is NULL, then pMask must not be NULL. In this case this
3657 ** function is being called as part of determining whether or not pIdx
3658 ** is a covering index. This function clears any bits in (*pMask)
3659 ** corresponding to columns that may be replaced by constants as described
3660 ** above.
3661 **
3662 ** Otherwise, if pItem is not NULL, then this function is being called
3663 ** as part of coding a loop that uses index pIdx. In this case, add entries
3664 ** to the Parse.pIdxPartExpr list for each column that can be replaced
3665 ** by a constant.
3666 */
3674 ){
3681 }
3686 u8 aff;
3710 }
3711 }
3714 }
3715 }
3716 }
3717 }
3720 /*
3721 ** Add all WhereLoop objects for a single table of the join where the table
3722 ** is identified by pBuilder->pNew->iTab. That table is guaranteed to be
3723 ** a b-tree table, not a virtual table.
3724 **
3725 ** The costs (WhereLoop.rRun) of the b-tree loops added by this function
3726 ** are calculated as follows:
3727 **
3728 ** For a full scan, assuming the table (or index) contains nRow rows:
3729 **
3730 ** cost = nRow * 3.0 // full-table scan
3731 ** cost = nRow * K // scan of covering index
3732 ** cost = nRow * (K+3.0) // scan of non-covering index
3733 **
3734 ** where K is a value between 1.1 and 3.0 set based on the relative
3735 ** estimated average size of the index and table records.
3736 **
3737 ** For an index scan, where nVisit is the number of index rows visited
3738 ** by the scan, and nSeek is the number of seek operations required on
3739 ** the index b-tree:
3740 **
3741 ** cost = nSeek * (log(nRow) + K * nVisit) // covering index
3742 ** cost = nSeek * (log(nRow) + (K+3.0) * nVisit) // non-covering index
3743 **
3744 ** Normally, nSeek is 1. nSeek values greater than 1 come about if the
3745 ** WHERE clause includes "x IN (....)" terms used in place of "x=?". Or when
3746 ** implicit "x IN (SELECT x FROM tbl)" terms are added for skip-scans.
3747 **
3748 ** The estimated values (nRow, nVisit, nSeek) often contain a large amount
3749 ** of uncertainty. For this reason, scoring is designed to pick plans that
3750 ** "do the least harm" if the estimates are inaccurate. For example, a
3751 ** log(nRow) factor is omitted from a non-covering index scan in order to
3752 ** bias the scoring in favor of using an index, since the worst-case
3753 ** performance of using an index is far better than the worst-case performance
3754 ** of a full table scan.
3755 */
3758 Bitmask mPrereq /* Extra prerequisites for using this table */
3759 ){
3785 /* An INDEXED BY clause specifies a particular index to use */
3790 /* There is no INDEXED BY clause. Create a fake Index object in local
3791 ** variable sPk to represent the rowid primary key index. Make this
3792 ** fake index the first in a chain of Index objects with all of the real
3793 ** indices to follow */
3808 /* The real indices of the table are only considered if the
3809 ** NOT INDEXED qualifier is omitted from the FROM clause */
3811 }
3813 }
3816 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
3817 /* Automatic indexes */
3827 ){
3828 /* Generate auto-index WhereLoops */
3841 /* TUNING: One-time cost for computing the automatic index is
3842 ** estimated to be X*N*log2(N) where N is the number of rows in
3843 ** the table being indexed and where X is 7 (LogEst=28) for normal
3844 ** tables or 0.5 (LogEst=-10) for views and subqueries. The value
3845 ** of X is smaller for views and subqueries so that the query planner
3846 ** will be more aggressive about generating automatic indexes for
3847 ** those objects, since there is no opportunity to add schema
3848 ** indexes on subqueries and views. */
3854 ** on ephemeral materializations of views */
3855 }
3858 /* TUNING: Each index lookup yields 20 rows in the table. This
3859 ** is more than the usual guess of 10 rows, since we have no way
3860 ** of knowing how selective the index will ultimately be. It would
3861 ** not be unreasonable to make this value much larger. */
3867 }
3868 }
3869 }
3872 /* Loop over all indices. If there was an INDEXED BY clause, then only
3873 ** consider index pProbe. */
3876 ){
3880 ){
3883 }
3898 /* The ONEPASS_DESIRED flags never occurs together with ORDER BY */
3901 /* Integer primary key index */
3904 /* Full table scan */
3906 /* TUNING: Cost of full table scan is 3.0*N. The 3.0 factor is an
3907 ** extra cost designed to discourage the use of full table scans,
3908 ** since index lookups have better worst-case performance if our
3909 ** stat guesses are wrong. Reduce the 3.0 penalty slightly
3910 ** (to 2.75) if we have valid STAT4 information for the table.
3911 ** At 2.75, a full table scan is preferred over using an index on
3912 ** a column with just two distinct values where each value has about
3913 ** an equal number of appearances. Without STAT4 data, we still want
3914 ** to use an index in that case, since the constraint might be for
3915 ** the scarcer of the two values, and in that case an index lookup is
3916 ** better.
3917 */
3918 #ifdef SQLITE_ENABLE_STAT4
3920 #else
3922 #endif
3929 Bitmask m;
3938 );
3939 }
3960 }
3961 }
3964 ){
3969 }
3970 }
3972 /* Full scan via index */
3983 )
3984 ){
3987 /* The cost of visiting the index rows is N*K, where K is
3988 ** between 1.1 and 3.0, depending on the relative sizes of the
3989 ** index and table rows. */
3992 /* If this is a non-covering index scan, add in the cost of
3993 ** doing table lookups. The cost will be 3x the number of
3994 ** lookups. Take into account WHERE clause terms that can be
3995 ** satisfied using just the index, and that do not require a
3996 ** table lookup. */
4005 }
4006 /* pTerm can be evaluated using just the index. So reduce
4007 ** the expected number of table lookups accordingly */
4011 nLookup--;
4013 }
4014 }
4017 }
4021 /* Do not do an SCAN of a index-on-expression in a RIGHT JOIN
4022 ** because the cursor used to access the index might not be
4023 ** positioned to the correct row during the right-join no-match
4024 ** loop. */
4027 }
4030 }
4031 }
4036 /* If a non-unique index is used, or if a prefix of the key for
4037 ** unique index is used (making the index functionally non-unique)
4038 ** then the sqlite_stat1 data becomes important for scoring the
4039 ** plan */
4041 }
4042 #ifdef SQLITE_ENABLE_STAT4
4046 #endif
4047 }
4049 }
4051 #ifndef SQLITE_OMIT_VIRTUALTABLE
4053 /*
4054 ** Return true if pTerm is a virtual table LIMIT or OFFSET term.
4055 */
4060 }
4062 /*
4063 ** Return true if the first nCons constraints in the pUsage array are
4064 ** marked as in-use (have argvIndex>0). False otherwise.
4065 */
4068 int nCons
4069 ){
4073 }
4075 }
4077 /*
4078 ** Argument pIdxInfo is already populated with all constraints that may
4079 ** be used by the virtual table identified by pBuilder->pNew->iTab. This
4080 ** function marks a subset of those constraints usable, invokes the
4081 ** xBestIndex method and adds the returned plan to pBuilder.
4082 **
4083 ** A constraint is marked usable if:
4084 **
4085 ** * Argument mUsable indicates that its prerequisites are available, and
4086 **
4087 ** * It is not one of the operators specified in the mExclude mask passed
4088 ** as the fourth argument (which in practice is either WO_IN or 0).
4089 **
4090 ** Argument mPrereq is a mask of tables that must be scanned before the
4091 ** virtual table in question. These are added to the plans prerequisites
4092 ** before it is added to pBuilder.
4093 **
4094 ** Output parameter *pbIn is set to true if the plan added to pBuilder
4095 ** uses one or more WO_IN terms, or false otherwise.
4096 */
4106 ){
4123 /* Set the usable flag on the subset of constraints identified by
4124 ** arguments mUsable and mExclude. */
4132 ){
4134 }
4135 }
4137 /* Initialize the output fields of the sqlite3_index_info structure */
4149 /* Invoke the virtual table xBestIndex() method */
4153 /* If the xBestIndex method returns SQLITE_CONSTRAINT, that means
4154 ** that the particular combination of parameters provided is unusable.
4155 ** Make no entries in the loop table.
4156 */
4159 }
4161 }
4178 ){
4182 }
4199 }
4202 }
4203 }
4207 /* A virtual table that is constrained by an IN clause may not
4208 ** consume the ORDER BY clause because (1) the order of IN terms
4209 ** is not necessarily related to the order of output terms and
4210 ** (2) Multiple outputs from a single IN value will not merge
4211 ** together. */
4215 }
4217 /* Unless pbRetryLimit is non-NULL, there should be no LIMIT/OFFSET
4218 ** terms. And if there are any, they should follow all other terms. */
4224 /* If there is an IN(...) term handled as an == (separate call to
4225 ** xFilter for each value on the RHS of the IN) and a LIMIT or
4226 ** OFFSET term handled as well, the plan is unusable. Similarly,
4227 ** if there is a LIMIT/OFFSET and there are other unused terms,
4228 ** the plan cannot be used. In these cases set variable *pbRetryLimit
4229 ** to true to tell the caller to retry with LIMIT and OFFSET
4230 ** disabled. */
4235 }
4238 }
4239 }
4240 }
4245 /* The non-zero argvIdx values must be contiguous. Raise an
4246 ** error if they are not */
4250 }
4251 }
4263 /* Set the WHERE_ONEROW flag if the xBestIndex() method indicated
4264 ** that the scan will visit at most one row. Clear it otherwise. */
4269 }
4274 }
4280 }
4282 /*
4283 ** Return the collating sequence for a constraint passed into xBestIndex.
4284 **
4285 ** pIdxInfo must be an sqlite3_index_info structure passed into xBestIndex.
4286 ** This routine depends on there being a HiddenIndexInfo structure immediately
4287 ** following the sqlite3_index_info structure.
4288 **
4289 ** Return a pointer to the collation name:
4290 **
4291 ** 1. If there is an explicit COLLATE operator on the constraint, return it.
4292 **
4293 ** 2. Else, if the column has an alternative collation, return that.
4294 **
4295 ** 3. Otherwise, return "BINARY".
4296 */
4306 }
4308 }
4310 }
4312 /*
4313 ** Return true if constraint iCons is really an IN(...) constraint, or
4314 ** false otherwise. If iCons is an IN(...) constraint, set (if bHandle!=0)
4315 ** or clear (if bHandle==0) the flag to handle it using an iterator.
4316 */
4325 }
4327 }
4329 }
4331 /*
4332 ** This interface is callable from within the xBestIndex callback only.
4333 **
4334 ** If possible, set (*ppVal) to point to an object containing the value
4335 ** on the right-hand-side of constraint iCons.
4336 */
4341 ){
4353 );
4355 }
4357 }
4362 }
4365 }
4367 /*
4368 ** Return true if ORDER BY clause may be handled as DISTINCT.
4369 */
4374 }
4376 /*
4377 ** Cause the prepared statement that is associated with a call to
4378 ** xBestIndex to potentially use all schemas. If the statement being
4379 ** prepared is read-only, then just start read transactions on all
4380 ** schemas. But if this is a write operation, start writes on all
4381 ** schemas.
4382 **
4383 ** This is used by the (built-in) sqlite_dbpage virtual table.
4384 */
4390 }
4394 }
4395 }
4396 }
4398 /*
4399 ** Add all WhereLoop objects for a table of the join identified by
4400 ** pBuilder->pNew->iTab. That table is guaranteed to be a virtual table.
4401 **
4402 ** If there are no LEFT or CROSS JOIN joins in the query, both mPrereq and
4403 ** mUnusable are set to 0. Otherwise, mPrereq is a mask of all FROM clause
4404 ** entries that occur before the virtual table in the FROM clause and are
4405 ** separated from it by at least one LEFT or CROSS JOIN. Similarly, the
4406 ** mUnusable mask contains all FROM clause entries that occur after the
4407 ** virtual table and are separated from it by at least one LEFT or
4408 ** CROSS JOIN.
4409 **
4410 ** For example, if the query were:
4411 **
4412 ** ... FROM t1, t2 LEFT JOIN t3, t4, vt CROSS JOIN t5, t6;
4413 **
4414 ** then mPrereq corresponds to (t1, t2) and mUnusable to (t5, t6).
4415 **
4416 ** All the tables in mPrereq must be scanned before the current virtual
4417 ** table. So any terms for which all prerequisites are satisfied by
4418 ** mPrereq may be specified as "usable" in all calls to xBestIndex.
4419 ** Conversely, all tables in mUnusable must be scanned after the current
4420 ** virtual table, so any terms for which the prerequisites overlap with
4421 ** mUnusable should always be configured as "not-usable" for xBestIndex.
4422 */
4426 Bitmask mUnusable /* Tables that must be scanned after this one */
4427 ){
4438 u16 mNoOmit;
4458 }
4460 /* First call xBestIndex() with all constraints usable. */
4465 );
4470 );
4471 }
4473 /* If the call to xBestIndex() with all terms enabled produced a plan
4474 ** that does not require any source tables (IOW: a plan with mBest==0)
4475 ** and does not use an IN(...) operator, then there is no point in making
4476 ** any further calls to xBestIndex() since they will all return the same
4477 ** result (if the xBestIndex() implementation is sane). */
4484 /* If the plan produced by the earlier call uses an IN(...) term, call
4485 ** xBestIndex again, this time with IN(...) terms disabled. */
4495 }
4496 }
4498 /* Call xBestIndex once for each distinct value of (prereqRight & ~mPrereq)
4499 ** in the set of terms that apply to the current virtual table. */
4505 Bitmask mThis = (
4507 );
4509 }
4520 }
4521 }
4523 /* If the calls to xBestIndex() in the above loop did not find a plan
4524 ** that requires no source tables at all (i.e. one guaranteed to be
4525 ** usable), make a call here with all source tables disabled */
4531 }
4533 /* If the calls to xBestIndex() have so far failed to find a plan
4534 ** that requires no source tables at all and does not use an IN(...)
4535 ** operator, make a final call to obtain one here. */
4540 }
4541 }
4547 }
4550 /*
4551 ** Add WhereLoop entries to handle OR terms. This works for either
4552 ** btrees or virtual tables.
4553 */
4556 Bitmask mPrereq,
4557 Bitmask mUnusable
4558 ){
4565 WhereClause tempWC;
4566 WhereLoopBuilder sSubBuild;
4577 /* The multi-index OR optimization does not work for RIGHT and FULL JOIN */
4583 ){
4607 }
4609 #ifdef WHERETRACE_ENABLED
4614 }
4615 #endif
4616 #ifndef SQLITE_OMIT_VIRTUALTABLE
4620 #endif
4621 {
4623 }
4626 }
4636 WhereOrSet sPrev;
4644 }
4645 }
4646 }
4647 }
4655 /* TUNING: Currently sSum.a[i].rRun is set to the sum of the costs
4656 ** of all sub-scans required by the OR-scan. However, due to rounding
4657 ** errors, it may be that the cost of the OR-scan is equal to its
4658 ** most expensive sub-scan. Add the smallest possible penalty
4659 ** (equivalent to multiplying the cost by 1.07) to ensure that
4660 ** this does not happen. Otherwise, for WHERE clauses such as the
4661 ** following where there is an index on "y":
4662 **
4663 ** WHERE likelihood(x=?, 0.99) OR y=?
4664 **
4665 ** the planner may elect to "OR" together a full-table scan and an
4666 ** index lookup. And other similarly odd results. */
4671 }
4673 }
4674 }
4676 }
4678 /*
4679 ** Add all WhereLoop objects for all tables
4680 */
4696 /* Loop over the tables in the join, from left to right */
4699 /* Verify that pNew has already been initialized */
4713 ){
4714 /* Add prerequisites to prevent reordering of FROM clause terms
4715 ** across CROSS joins and outer joins. The bFirstPastRJ boolean
4716 ** prevents the right operand of a RIGHT JOIN from being swapped with
4717 ** other elements even further to the right.
4718 **
4719 ** The JT_LTORJ case and the hasRightJoin flag work together to
4720 ** prevent FROM-clause terms from moving from the right side of
4721 ** a LEFT JOIN over to the left side of that join if the LEFT JOIN
4722 ** is itself on the left side of a RIGHT JOIN.
4723 */
4729 }
4730 #ifndef SQLITE_OMIT_VIRTUALTABLE
4736 }
4737 }
4741 {
4743 }
4746 }
4750 /* We hit the query planner search limit set by iPlanLimit */
4755 }
4756 }
4757 }
4761 }
4763 /*
4764 ** Examine a WherePath (with the addition of the extra WhereLoop of the 6th
4765 ** parameters) to see if it outputs rows in the requested ORDER BY
4766 ** (or GROUP BY) without requiring a separate sort operation. Return N:
4767 **
4768 ** N>0: N terms of the ORDER BY clause are satisfied
4769 ** N==0: No terms of the ORDER BY clause are satisfied
4770 ** N<0: Unknown yet how many terms of ORDER BY might be satisfied.
4771 **
4772 ** Note that processing for WHERE_GROUPBY and WHERE_DISTINCTBY is not as
4773 ** strict. With GROUP BY and DISTINCT the only requirement is that
4774 ** equivalent rows appear immediately adjacent to one another. GROUP BY
4775 ** and DISTINCT do not require rows to appear in any particular order as long
4776 ** as equivalent rows are grouped together. Thus for GROUP BY and DISTINCT
4777 ** the pOrderBy terms can be matched in any order. With ORDER BY, the
4778 ** pOrderBy terms must be matched in strict left-to-right order.
4779 */
4788 ){
4814 /*
4815 ** We say the WhereLoop is "one-row" if it generates no more than one
4816 ** row of output. A WhereLoop is one-row if all of the following are true:
4817 ** (a) All index columns match with WHERE_COLUMN_EQ.
4818 ** (b) The index is unique
4819 ** Any WhereLoop with an WHERE_COLUMN_EQ constraint on the rowid is one-row.
4820 ** Every one-row WhereLoop will have the WHERE_ONEROW bit set in wsFlags.
4821 **
4822 ** We say the WhereLoop is "order-distinct" if the set of columns from
4823 ** that WhereLoop that are in the ORDER BY clause are different for every
4824 ** row of the WhereLoop. Every one-row WhereLoop is automatically
4825 ** order-distinct. A WhereLoop that has no columns in the ORDER BY clause
4826 ** is not order-distinct. To be order-distinct is not quite the same as being
4827 ** UNIQUE since a UNIQUE column or index can have multiple rows that
4828 ** are NULL and NULL values are equivalent for the purpose of order-distinct.
4829 ** To be order-distinct, the columns must be UNIQUE and NOT NULL.
4830 **
4831 ** The rowid for a table is always UNIQUE and NOT NULL so whenever the
4832 ** rowid appears in the ORDER BY clause, the corresponding WhereLoop is
4833 ** automatically order-distinct.
4834 */
4849 }
4857 }
4861 ){
4863 }
4867 }
4870 /* Mark off any ORDER BY term X that is a column in the table of
4871 ** the current loop for which there is term in the WHERE
4872 ** clause of the form X IS NULL or X=? that reference only outer
4873 ** loops.
4874 */
4885 /* IN terms are only valid for sorting in the ORDER BY LIMIT
4886 ** optimization, and then only if they are actually used
4887 ** by the query plan */
4892 }
4900 }
4902 }
4904 }
4919 /* All relevant terms of the index must also be non-NULL in order
4920 ** for isOrderDistinct to be true. So the isOrderDistint value
4921 ** computed here might be a false positive. Corrections will be
4922 ** made at tag-20210426-1 below */
4925 }
4927 /* Loop through all columns of the index and deal with the ones
4928 ** that are not constrained by == or IN.
4929 */
4937 );
4941 /* Skip over == and IS and ISNULL terms. (Also skip IN terms when
4942 ** doing WHERE_ORDERBY_LIMIT processing). Except, IS and ISNULL
4943 ** terms imply that the index is not UNIQUE NOT NULL in which case
4944 ** the loop need to be marked as not order-distinct because it can
4945 ** have repeated NULL rows.
4946 **
4947 ** If the current term is a column of an ((?,?) IN (SELECT...))
4948 ** expression for which the SELECT returns more than one column,
4949 ** check that it is the only column used by this loop. Otherwise,
4950 ** if it is one of two or more, none of the columns can be
4951 ** considered to match an ORDER BY term.
4952 */
4959 }
4962 /* ALWAYS() justification: eOp is an equality operator due to the
4963 ** j<pLoop->u.btree.nEq constraint above. Any equality other
4964 ** than WO_IN is captured by the previous "if". So this one
4965 ** always has to be WO_IN. */
4972 }
4973 }
4974 }
4975 }
4977 /* Get the column number in the table (iColumn) and sort order
4978 ** (revIdx) for the j-th column of the index.
4979 */
4987 }
4989 /* An unconstrained column that might be NULL means that this
4990 ** WhereLoop is not well-ordered. tag-20210426-1
4991 */
4996 ){
4998 }
5001 }
5002 }
5004 /* Find the ORDER BY term that corresponds to the j-th column
5005 ** of the index and mark that ORDER BY term off
5006 */
5023 }
5024 }
5028 }
5031 }
5034 }
5036 /* Make sure the sort order is compatible in an ORDER BY clause.
5037 ** Sort order is irrelevant for a GROUP BY clause. */
5041 ){
5043 }
5048 }
5049 }
5055 }
5056 }
5061 }
5064 /* No match found */
5068 }
5070 }
5075 }
5078 /* Mark off any other ORDER BY terms that reference pLoop */
5083 Bitmask mTerm;
5090 }
5091 }
5092 }
5099 }
5101 }
5103 }
5106 /*
5107 ** If the WHERE_GROUPBY flag is set in the mask passed to sqlite3WhereBegin(),
5108 ** the planner assumes that the specified pOrderBy list is actually a GROUP
5109 ** BY clause - and so any order that groups rows as required satisfies the
5110 ** request.
5111 **
5112 ** Normally, in this case it is not possible for the caller to determine
5113 ** whether or not the rows are really being delivered in sorted order, or
5114 ** just in some other order that provides the required grouping. However,
5115 ** if the WHERE_SORTBYGROUP flag is also passed to sqlite3WhereBegin(), then
5116 ** this function may be called on the returned WhereInfo object. It returns
5117 ** true if the rows really will be sorted in the specified order, or false
5118 ** otherwise.
5119 **
5120 ** For example, assuming:
5121 **
5122 ** CREATE INDEX i1 ON t1(x, Y);
5123 **
5124 ** then
5125 **
5126 ** SELECT * FROM t1 GROUP BY x,y ORDER BY x,y; -- IsSorted()==1
5127 ** SELECT * FROM t1 GROUP BY y,x ORDER BY y,x; -- IsSorted()==0
5128 */
5133 }
5135 #ifdef WHERETRACE_ENABLED
5136 /* For debugging use only: */
5144 }
5145 #endif
5147 /*
5148 ** Return the cost of sorting nRow rows, assuming that the keys have
5149 ** nOrderby columns and that the first nSorted columns are already in
5150 ** order.
5151 */
5157 ){
5158 /* Estimated cost of a full external sort, where N is
5159 ** the number of rows to sort is:
5160 **
5161 ** cost = (K * N * log(N)).
5162 **
5163 ** Or, if the order-by clause has X terms but only the last Y
5164 ** terms are out of order, then block-sorting will reduce the
5165 ** sorting cost to:
5166 **
5167 ** cost = (K * N * log(N)) * (Y/X)
5168 **
5169 ** The constant K is at least 2.0 but will be larger if there are a
5170 ** large number of columns to be sorted, as the sorting time is
5171 ** proportional to the amount of content to be sorted. The algorithm
5172 ** does not currently distinguish between fat columns (BLOBs and TEXTs)
5173 ** and skinny columns (INTs). It just uses the number of columns as
5174 ** an approximation for the row width.
5175 **
5176 ** And extra factor of 2.0 or 3.0 is added to the sorting cost if the sort
5177 ** is built using OP_IdxInsert and OP_Sort rather than with OP_SorterInsert.
5178 */
5182 /* TUNING: sorting cost proportional to the number of output columns: */
5186 /* Scale the result by (Y/X) */
5188 }
5190 /* Multiple by log(M) where M is the number of output rows.
5191 ** Use the LIMIT for M if it is smaller. Or if this sort is for
5192 ** a DISTINCT operator, M will be the number of distinct output
5193 ** rows, so fudge it downwards a bit.
5194 */
5199 }
5202 }
5204 /* TUNING: In the sort for a DISTINCT operator, assume that the DISTINCT
5205 ** reduces the number of output rows by a factor of 2 */
5207 }
5210 }
5212 /*
5213 ** Given the list of WhereLoop objects at pWInfo->pLoops, this routine
5214 ** attempts to find the lowest cost path that visits each WhereLoop
5215 ** once. This path is then loaded into the pWInfo->a[].pWLoop fields.
5216 **
5217 ** Assume that the total number of output rows that will need to be sorted
5218 ** will be nRowEst (in the 10*log2 representation). Or, ignore sorting
5219 ** costs if nRowEst==0.
5220 **
5221 ** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation
5222 ** error occurs.
5223 */
5247 /* TUNING: For simple queries, only the best path is tracked.
5248 ** For 2-way joins, the 5 best paths are followed.
5249 ** For joins of 3 or more tables, track the 10 best paths */
5255 /* If nRowEst is zero and there is an ORDER BY clause, ignore it. In this
5256 ** case the purpose of this call is to estimate the number of rows returned
5257 ** by the overall query. Once this estimate has been obtained, the caller
5258 ** will invoke this function a second time, passing the estimate as the
5259 ** nRowEst parameter. */
5264 }
5266 /* Allocate and initialize space for aTo, aFrom and aSortCost[] */
5277 }
5279 /* If there is an ORDER BY clause and it is not being ignored, set up
5280 ** space for the aSortCost[] array. Each element of the aSortCost array
5281 ** is either zero - meaning it has not yet been initialized - or the
5282 ** cost of sorting nRowEst rows of data where the first X terms of
5283 ** the ORDER BY clause are already in order, where X is the array
5284 ** index. */
5287 }
5291 /* Seed the search with a single WherePath containing zero WhereLoops.
5292 **
5293 ** TUNING: Do not let the number of iterations go above 28. If the cost
5294 ** of computing an automatic index is not paid back within the first 28
5295 ** rows, then do not use the automatic index. */
5300 /* If nLoop is zero, then there are no FROM terms in the query. Since
5301 ** in this case the query may return a maximum of one row, the results
5302 ** are already in the requested order. Set isOrdered to nOrderBy to
5303 ** indicate this. Or, if nLoop is greater than zero, set isOrdered to
5304 ** -1, indicating that the result set may or may not be ordered,
5305 ** depending on the loops added to the current plan. */
5307 }
5309 /* Compute successively longer WherePaths using the previous generation
5310 ** of WherePaths as the basis for the next. Keep track of the mxChoice
5311 ** best paths at each generation */
5326 /* Do not use an automatic index if the this loop is expected
5327 ** to run less than 1.25 times. It is tempting to also exclude
5328 ** automatic index usage on an outer loop, but sometimes an automatic
5329 ** index is useful in the outer loop of a correlated subquery. */
5332 }
5334 /* At this point, pWLoop is a candidate to be the next loop.
5335 ** Compute its cost */
5348 }
5353 );
5354 }
5355 /* TUNING: Add a small extra penalty (3) to sorting as an
5356 ** extra encouragement to the query planner to select a plan
5357 ** where the rows emerge in the correct order without any sorting
5358 ** required. */
5368 }
5370 /* Check to see if pWLoop should be added to the set of
5371 ** mxChoice best-so-far paths.
5372 **
5373 ** First look for an existing path among best-so-far paths
5374 ** that covers the same set of loops and has the same isOrdered
5375 ** setting as the current path candidate.
5376 **
5377 ** The term "((pTo->isOrdered^isOrdered)&0x80)==0" is equivalent
5378 ** to (pTo->isOrdered==(-1))==(isOrdered==(-1))" for the range
5379 ** of legal values for isOrdered, -1..64.
5380 */
5384 ){
5387 }
5388 }
5390 /* None of the existing best-so-far paths match the candidate. */
5393 ){
5394 /* The current candidate is no better than any of the mxChoice
5395 ** paths currently in the best-so-far buffer. So discard
5396 ** this candidate as not viable. */
5402 }
5403 #endif
5405 }
5406 /* If we reach this points it means that the new candidate path
5407 ** needs to be added to the set of best-so-far paths. */
5409 /* Increase the size of the aTo set by one */
5412 /* New path replaces the prior worst to keep count below mxChoice */
5414 }
5421 }
5422 #endif
5424 /* Control reaches here if best-so-far path pTo=aTo[jj] covers the
5425 ** same set of loops and has the same isOrdered setting as the
5426 ** candidate path. Check to see if the candidate should replace
5427 ** pTo or if the candidate should be skipped.
5428 **
5429 ** The conditional is an expanded vector comparison equivalent to:
5430 ** (pTo->rCost,pTo->nRow,pTo->rUnsorted) <= (rCost,nOut,rUnsorted)
5431 */
5436 )
5437 )
5438 ){
5448 }
5449 #endif
5450 /* Discard the candidate path from further consideration */
5453 }
5455 /* Control reaches here if the candidate path is better than the
5456 ** pTo path. Replace pTo with the candidate. */
5466 }
5467 #endif
5468 }
5469 /* pWLoop is a winner. Add it to the set of best so far */
5485 ){
5489 }
5490 }
5491 }
5492 }
5493 }
5506 }
5507 }
5508 }
5509 #endif
5511 /* Swap the roles of aFrom and aTo for the next generation */
5516 }
5522 }
5524 /* Find the lowest cost path. pFrom will be left pointing to that path */
5528 }
5530 /* Load the lowest cost path into pWInfo */
5536 }
5540 && nRowEst
5541 ){
5542 Bitmask notUsed;
5547 }
5548 }
5555 }
5556 /* vvv--- See check-in [12ad822d9b827777] on 2023-03-16 ---vvv */
5567 ){
5576 }
5577 }
5578 }
5582 ){
5584 }
5585 }
5588 ){
5592 );
5597 }
5598 }
5599 }
5603 /* Free temporary memory and return success */
5606 }
5608 /*
5609 ** This routine implements a heuristic designed to improve query planning.
5610 ** This routine is called in between the first and second call to
5611 ** wherePathSolver(). Hence the name "Interstage" "Heuristic".
5612 **
5613 ** The first call to wherePathSolver() (hereafter just "solver()") computes
5614 ** the best path without regard to the order of the outputs. The second call
5615 ** to the solver() builds upon the first call to try to find an alternative
5616 ** path that satisfies the ORDER BY clause.
5617 **
5618 ** This routine looks at the results of the first solver() run, and for
5619 ** every FROM clause term in the resulting query plan that uses an equality
5620 ** constraint against an index, disable other WhereLoops for that same
5621 ** FROM clause term that would try to do a full-table scan. This prevents
5622 ** an index search from being converted into a full-table scan in order to
5623 ** satisfy an ORDER BY clause, since even though we might get slightly better
5624 ** performance using the full-scan without sorting if the output size
5625 ** estimates are very precise, we might also get severe performance
5626 ** degradation using the full-scan if the output size estimate is too large.
5627 ** It is better to err on the side of caution.
5628 **
5629 ** Except, if the first solver() call generated a full-table scan in an outer
5630 ** loop then stop this analysis at the first full-scan, since the second
5631 ** solver() run might try to swap that full-scan for another in order to
5632 ** get the output into the correct order. In other words, we allow a
5633 ** rewrite like this:
5634 **
5635 ** First Solver() Second Solver()
5636 ** |-- SCAN t1 |-- SCAN t2
5637 ** |-- SEARCH t2 `-- SEARCH t1
5638 ** `-- SORT USING B-TREE
5639 **
5640 ** The purpose of this routine is to disallow rewrites such as:
5641 **
5642 ** First Solver() Second Solver()
5643 ** |-- SEARCH t1 |-- SCAN t2 <--- bad!
5644 ** |-- SEARCH t2 `-- SEARCH t1
5645 ** `-- SORT USING B-TREE
5646 **
5647 ** See test cases in test/whereN.test for the real-world query that
5648 ** originally provoked this heuristic.
5649 */
5652 #ifdef WHERETRACE_ENABLED
5654 #endif
5665 /* Auto-index and index-constrained loops allowed to remain */
5667 }
5668 #ifdef WHERETRACE_ENABLED
5673 }
5675 }
5678 }
5681 }
5682 }
5683 }
5685 /*
5686 ** Most queries use only a single table (they are not joins) and have
5687 ** simple == constraints against indexed fields. This routine attempts
5688 ** to plan those simple cases using much less ceremony than the
5689 ** general-purpose query planner, and thereby yield faster sqlite3_prepare()
5690 ** times for the common case.
5691 **
5692 ** Return non-zero on success, if this query can be handled by this
5693 ** no-frills query planner. Return zero if this query needs the
5694 ** general-purpose query planner.
5695 */
5706 WhereScan scan;
5718 }
5732 /* TUNING: Cost of a rowid lookup is 10 */
5749 }
5754 }
5758 /* TUNING: Cost of a unique index lookup is 15 */
5761 }
5762 }
5773 }
5775 #ifdef SQLITE_DEBUG
5777 #endif
5778 #ifdef WHERETRACE_ENABLED
5781 }
5782 #endif
5784 }
5786 }
5788 /*
5789 ** Helper function for exprIsDeterministic().
5790 */
5795 }
5797 }
5799 /*
5800 ** Return true if the expression contains no non-deterministic SQL
5801 ** functions. Do not consider non-deterministic SQL functions that are
5802 ** part of sub-select statements.
5803 */
5805 Walker w;
5812 }
5815 #ifdef WHERETRACE_ENABLED
5816 /*
5817 ** Display all WhereLoops in pWInfo
5818 */
5828 }
5829 }
5830 }
5831 # define WHERETRACE_ALL_LOOPS(W,C) showAllWhereLoops(W,C)
5832 #else
5833 # define WHERETRACE_ALL_LOOPS(W,C)
5834 #endif
5836 /* Attempt to omit tables from a join that do not affect the result.
5837 ** For a table to not affect the result, the following must be true:
5838 **
5839 ** 1) The query must not be an aggregate.
5840 ** 2) The table must be the RHS of a LEFT JOIN.
5841 ** 3) Either the query must be DISTINCT, or else the ON or USING clause
5842 ** must contain a constraint that limits the scan of the table to
5843 ** at most a single row.
5844 ** 4) The table must not be referenced by any part of the query apart
5845 ** from its own USING or ON clause.
5846 ** 5) The table must not have an inner-join ON or USING clause if there is
5847 ** a RIGHT JOIN anywhere in the query. Otherwise the ON/USING clause
5848 ** might move from the right side to the left side of the RIGHT JOIN.
5849 ** Note: Due to (2), this condition can only arise if the table is
5850 ** the right-most table of a subquery that was flattened into the
5851 ** main query and that subquery was the right-hand operand of an
5852 ** inner join that held an ON or USING clause.
5853 ** 6) The ORDER BY clause has 63 or fewer terms
5854 ** 7) The omit-noop-join optimization is enabled.
5855 **
5856 ** Items (1), (6), and (7) are checked by the caller.
5857 **
5858 ** For example, given:
5859 **
5860 ** CREATE TABLE t1(ipk INTEGER PRIMARY KEY, v1);
5861 ** CREATE TABLE t2(ipk INTEGER PRIMARY KEY, v2);
5862 ** CREATE TABLE t3(ipk INTEGER PRIMARY KEY, v3);
5863 **
5864 ** then table t2 can be omitted from the following:
5865 **
5866 ** SELECT v1, v3 FROM t1
5867 ** LEFT JOIN t2 ON (t1.ipk=t2.ipk)
5868 ** LEFT JOIN t3 ON (t1.ipk=t3.ipk)
5869 **
5870 ** or from:
5871 **
5872 ** SELECT DISTINCT v1, v3 FROM t1
5873 ** LEFT JOIN t2
5874 ** LEFT JOIN t3 ON (t1.ipk=t3.ipk)
5875 */
5878 Bitmask notReady
5879 ){
5881 Bitmask tabUsed;
5884 /* Preconditions checked by the caller */
5888 /* These two preconditions checked by the caller combine to guarantee
5889 ** condition (1) of the header comment */
5896 }
5907 ){
5909 }
5916 ){
5918 }
5919 }
5923 ){
5925 }
5926 }
5933 }
5934 }
5938 }
5941 }
5943 }
5945 /*
5946 ** Check to see if there are any SEARCH loops that might benefit from
5947 ** using a Bloom filter. Consider a Bloom filter if:
5948 **
5949 ** (1) The SEARCH happens more than N times where N is the number
5950 ** of rows in the table that is being considered for the Bloom
5951 ** filter.
5952 ** (2) Some searches are expected to find zero rows. (This is determined
5953 ** by the WHERE_SELFCULL flag on the term.)
5954 ** (3) Bloom-filter processing is not disabled. (Checked by the
5955 ** caller.)
5956 ** (4) The size of the table being searched is known by ANALYZE.
5957 **
5958 ** This block of code merely checks to see if a Bloom filter would be
5959 ** appropriate, and if so sets the WHERE_BLOOMFILTER flag on the
5960 ** WhereLoop. The implementation of the Bloom filter comes further
5961 ** down where the code for each WhereLoop is generated.
5962 */
5965 ){
5980 /* vvvvvv--- Always the case if WHERE_COLUMN_EQ is defined */
5982 ){
5988 "-> use Bloom-filter on loop %c because there are ~%.1e "
5992 }
5993 }
5995 }
5996 }
5998 /*
5999 ** Expression Node callback for sqlite3ExprCanReturnSubtype().
6000 **
6001 ** Only a function call is able to return a subtype. So if the node
6002 ** is not a function call, return WRC_Prune immediately.
6003 **
6004 ** A function call is able to return a subtype if it has the
6005 ** SQLITE_RESULT_SUBTYPE property.
6006 **
6007 ** Assume that every function is able to pass-through a subtype from
6008 ** one of its argument (using sqlite3_result_value()). Most functions
6009 ** are not this way, but we don't have a mechanism to distinguish those
6010 ** that are from those that are not, so assume they all work this way.
6011 ** That means that if one of its arguments is another function and that
6012 ** other function is able to return a subtype, then this function is
6013 ** able to return a subtype.
6014 */
6021 }
6029 }
6031 }
6033 /*
6034 ** Return TRUE if expression pExpr is able to return a subtype.
6035 **
6036 ** A TRUE return does not guarantee that a subtype will be returned.
6037 ** It only indicates that a subtype return is possible. False positives
6038 ** are acceptable as they only disable an optimization. False negatives,
6039 ** on the other hand, can lead to incorrect answers.
6040 */
6042 Walker w;
6048 }
6050 /*
6051 ** The index pIdx is used by a query and contains one or more expressions.
6052 ** In other words pIdx is an index on an expression. iIdxCur is the cursor
6053 ** number for the index and iDataCur is the cursor number for the corresponding
6054 ** table.
6055 **
6056 ** This routine adds IndexedExpr entries to the Parse->pIdxEpr field for
6057 ** each of the expressions in the index so that the expression code generator
6058 ** will know to replace occurrences of the indexed expression with
6059 ** references to the corresponding column of the index.
6060 */
6066 ){
6081 }
6084 /* Functions that might set a subtype should not be replaced by the
6085 ** value taken from an expression index since the index omits the
6086 ** subtype. https://sqlite.org/forum/forumpost/68d284c86b082c3e */
6088 }
6092 #ifdef WHERETRACE_ENABLED
6096 }
6097 #endif
6105 }
6106 #ifdef SQLITE_ENABLE_EXPLAIN_COMMENTS
6108 #endif
6113 }
6114 }
6115 }
6117 /*
6118 ** Set the reverse-scan order mask to one for all tables in the query
6119 ** with the exception of MATERIALIZED common table expressions that have
6120 ** their own internal ORDER BY clauses.
6121 **
6122 ** This implements the PRAGMA reverse_unordered_selects=ON setting.
6123 ** (Also SQLITE_DBCONFIG_REVERSE_SCANORDER).
6124 */
6133 ){
6135 }
6136 }
6137 }
6139 /*
6140 ** Generate the beginning of the loop used for WHERE clause processing.
6141 ** The return value is a pointer to an opaque structure that contains
6142 ** information needed to terminate the loop. Later, the calling routine
6143 ** should invoke sqlite3WhereEnd() with the return value of this function
6144 ** in order to complete the WHERE clause processing.
6145 **
6146 ** If an error occurs, this routine returns NULL.
6147 **
6148 ** The basic idea is to do a nested loop, one loop for each table in
6149 ** the FROM clause of a select. (INSERT and UPDATE statements are the
6150 ** same as a SELECT with only a single table in the FROM clause.) For
6151 ** example, if the SQL is this:
6152 **
6153 ** SELECT * FROM t1, t2, t3 WHERE ...;
6154 **
6155 ** Then the code generated is conceptually like the following:
6156 **
6157 ** foreach row1 in t1 do \ Code generated
6158 ** foreach row2 in t2 do |-- by sqlite3WhereBegin()
6159 ** foreach row3 in t3 do /
6160 ** ...
6161 ** end \ Code generated
6162 ** end |-- by sqlite3WhereEnd()
6163 ** end /
6164 **
6165 ** Note that the loops might not be nested in the order in which they
6166 ** appear in the FROM clause if a different order is better able to make
6167 ** use of indices. Note also that when the IN operator appears in
6168 ** the WHERE clause, it might result in additional nested loops for
6169 ** scanning through all values on the right-hand side of the IN.
6170 **
6171 ** There are Btree cursors associated with each table. t1 uses cursor
6172 ** number pTabList->a[0].iCursor. t2 uses the cursor pTabList->a[1].iCursor.
6173 ** And so forth. This routine generates code to open those VDBE cursors
6174 ** and sqlite3WhereEnd() generates the code to close them.
6175 **
6176 ** The code that sqlite3WhereBegin() generates leaves the cursors named
6177 ** in pTabList pointing at their appropriate entries. The [...] code
6178 ** can use OP_Column and OP_Rowid opcodes on these cursors to extract
6179 ** data from the various tables of the loop.
6180 **
6181 ** If the WHERE clause is empty, the foreach loops must each scan their
6182 ** entire tables. Thus a three-way join is an O(N^3) operation. But if
6183 ** the tables have indices and there are terms in the WHERE clause that
6184 ** refer to those indices, a complete table scan can be avoided and the
6185 ** code will run much faster. Most of the work of this routine is checking
6186 ** to see if there are indices that can be used to speed up the loop.
6187 **
6188 ** Terms of the WHERE clause are also used to limit which rows actually
6189 ** make it to the "..." in the middle of the loop. After each "foreach",
6190 ** terms of the WHERE clause that use only terms in that loop and outer
6191 ** loops are evaluated and if false a jump is made around all subsequent
6192 ** inner loops (or around the "..." if the test occurs within the inner-
6193 ** most loop)
6194 **
6195 ** OUTER JOINS
6196 **
6197 ** An outer join of tables t1 and t2 is conceptually coded as follows:
6198 **
6199 ** foreach row1 in t1 do
6200 ** flag = 0
6201 ** foreach row2 in t2 do
6202 ** start:
6203 ** ...
6204 ** flag = 1
6205 ** end
6206 ** if flag==0 then
6207 ** move the row2 cursor to a null row
6208 ** goto start
6209 ** fi
6210 ** end
6211 **
6212 ** ORDER BY CLAUSE PROCESSING
6213 **
6214 ** pOrderBy is a pointer to the ORDER BY clause (or the GROUP BY clause
6215 ** if the WHERE_GROUPBY flag is set in wctrlFlags) of a SELECT statement
6216 ** if there is one. If there is no ORDER BY clause or if this routine
6217 ** is called from an UPDATE or DELETE statement, then pOrderBy is NULL.
6218 **
6219 ** The iIdxCur parameter is the cursor number of an index. If
6220 ** WHERE_OR_SUBCLAUSE is set, iIdxCur is the cursor number of an index
6221 ** to use for OR clause processing. The WHERE clause should use this
6222 ** specific cursor. If WHERE_ONEPASS_DESIRED is set, then iIdxCur is
6223 ** the first cursor in an array of cursors for all indices. iIdxCur should
6224 ** be used to compute the appropriate cursor depending on which index is
6225 ** used.
6226 */
6236 ** If WHERE_USE_LIMIT, then the limit amount */
6237 ){
6255 ));
6257 /* Only one of WHERE_OR_SUBCLAUSE or WHERE_USE_LIMIT */
6261 /* Variable initialization */
6265 /* An ORDER/GROUP BY clause of more than 63 terms cannot be optimized */
6271 }
6273 /* The number of tables in the FROM clause is limited by the number of
6274 ** bits in a Bitmask
6275 */
6280 }
6282 /* This function normally generates a nested loop for all tables in
6283 ** pTabList. But if the WHERE_OR_SUBCLAUSE flag is set, then we should
6284 ** only generate code for the first table in pTabList and assume that
6285 ** any cursors associated with subsequent tables are uninitialized.
6286 */
6289 /* Allocate and initialize the WhereInfo structure that will become the
6290 ** return value. A single allocation is used to store the WhereInfo
6291 ** struct, the contents of WhereInfo.a[], the WhereClause structure
6292 ** and the WhereMaskSet structure. Since WhereClause contains an 8-byte
6293 ** field (type Bitmask) it must be aligned on an 8-byte boundary on
6294 ** some architectures. Hence the ROUND8() below.
6295 */
6299 }
6305 }
6309 #if WHERETRACE_ENABLED
6311 #endif
6327 ** a valid cursor number, to avoid an initial
6328 ** test for pMaskSet->n==0 in sqlite3WhereGetMask() */
6334 #ifdef SQLITE_DEBUG
6336 #endif
6338 /* Split the WHERE clause into separate subexpressions where each
6339 ** subexpression is separated by an AND operator.
6340 */
6344 /* Special case: No FROM clause
6345 */
6350 ){
6352 }
6355 ){
6357 }
6359 /* Assign a bit from the bitmask to every term in the FROM clause.
6360 **
6361 ** The N-th term of the FROM clause is assigned a bitmask of 1<<N.
6362 **
6363 ** The rule of the previous sentence ensures that if X is the bitmask for
6364 ** a table T, then X-1 is the bitmask for all other tables to the left of T.
6365 ** Knowing the bitmask for all tables to the left of a left join is
6366 ** important. Ticket #3015.
6367 **
6368 ** Note that bitmasks are created for all pTabList->nSrc tables in
6369 ** pTabList, not just the first nTabList tables. nTabList is normally
6370 ** equal to pTabList->nSrc but might be shortened to 1 if the
6371 ** WHERE_OR_SUBCLAUSE flag is set.
6372 */
6378 #ifdef SQLITE_DEBUG
6379 {
6385 }
6386 }
6387 #endif
6388 }
6390 /* Analyze all of the subexpressions. */
6394 }
6397 /* The False-WHERE-Term-Bypass optimization:
6398 **
6399 ** If there are WHERE terms that are false, then no rows will be output,
6400 ** so skip over all of the code generated here.
6401 **
6402 ** Conditions:
6403 **
6404 ** (1) The WHERE term must not refer to any tables in the join.
6405 ** (2) The term must not come from an ON clause on the
6406 ** right-hand side of a LEFT or FULL JOIN.
6407 ** (3) The term must not come from an ON clause, or there must be
6408 ** no RIGHT or FULL OUTER joins in pTabList.
6409 ** (4) If the expression contains non-deterministic functions
6410 ** that are not within a sub-select. This is not required
6411 ** for correctness but rather to preserves SQLite's legacy
6412 ** behaviour in the following two cases:
6413 **
6414 ** WHERE random()>0; -- eval random() once per row
6415 ** WHERE (SELECT random())>0; -- eval random() just once overall
6416 **
6417 ** Note that the Where term need not be a constant in order for this
6418 ** optimization to apply, though it does need to be constant relative to
6419 ** the current subquery (condition 1). The term might include variables
6420 ** from outer queries so that the value of the term changes from one
6421 ** invocation of the current subquery to the next.
6422 */
6434 ){
6437 }
6438 }
6442 /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via
6443 ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */
6447 /* The DISTINCT marking is pointless. Ignore it. */
6450 /* Try to ORDER BY the result set to make distinct processing easier */
6453 }
6454 }
6456 /* Construct the WhereLoop objects */
6457 #if defined(WHERETRACE_ENABLED)
6462 }
6465 Select sSelect;
6473 }
6477 }
6478 }
6479 #endif
6485 #ifdef SQLITE_ENABLE_STAT4
6486 /* If one or more WhereTerm.truthProb values were used in estimating
6487 ** loop parameters, but then those truthProb values were subsequently
6488 ** changed based on STAT4 information while computing subsequent loops,
6489 ** then we need to rerun the whole loop building process so that all
6490 ** loops will be built using the revised truthProb values. */
6500 }
6503 }
6504 #endif
6513 }
6515 /* TUNING: Assume that a DISTINCT clause on a subquery reduces
6516 ** the output size by a factor of 8 (LogEst -30).
6517 */
6522 }
6524 }
6528 }
6531 }
6533 #ifdef WHERETRACE_ENABLED
6538 }
6543 }
6547 }
6551 }
6552 }
6556 }
6557 }
6558 #endif
6560 /* Attempt to omit tables from a join that do not affect the result.
6561 ** See the comment on whereOmitNoopJoin() for further information.
6562 **
6563 ** This query optimization is factored out into a separate "no-inline"
6564 ** procedure to keep the sqlite3WhereBegin() procedure from becoming
6565 ** too large. If sqlite3WhereBegin() becomes too large, that prevents
6566 ** some C-compiler optimizers from in-lining the
6567 ** sqlite3WhereCodeOneLoopStart() procedure, and it is important to
6568 ** in-line sqlite3WhereCodeOneLoopStart() for performance reasons.
6569 */
6575 ){
6579 }
6581 /* Check to see if there are any SEARCH loops that might benefit from
6582 ** using a Bloom filter.
6583 */
6586 ){
6588 }
6590 #if defined(WHERETRACE_ENABLED)
6594 }
6596 #endif
6599 /* If the caller is an UPDATE or DELETE statement that is requesting
6600 ** to use a one-pass algorithm, determine if this is appropriate.
6601 **
6602 ** A one-pass approach can be used if the caller has requested one
6603 ** and either (a) the scan visits at most one row or (b) each
6604 ** of the following are true:
6605 **
6606 ** * the caller has indicated that a one-pass approach can be used
6607 ** with multiple rows (by setting WHERE_ONEPASS_MULTIROW), and
6608 ** * the table is not a virtual table, and
6609 ** * either the scan does not use the OR optimization or the caller
6610 ** is a DELETE operation (WHERE_DUPLICATES_OK is only specified
6611 ** for DELETE).
6612 **
6613 ** The last qualification is because an UPDATE statement uses
6614 ** WhereInfo.aiCurOnePass[1] to determine whether or not it really can
6615 ** use a one-pass approach, and this is not set accurately for scans
6616 ** that use the OR optimization.
6617 */
6628 )){
6633 }
6635 }
6636 }
6637 }
6639 /* Open all tables in the pTabList and any indices selected for
6640 ** searching those tables.
6641 */
6652 /* Do nothing */
6654 #ifndef SQLITE_OMIT_VIRTUALTABLE
6660 /* noop */
6662 #endif
6666 ){
6671 };
6680 ){
6681 /* If we know that only a prefix of the record will be used,
6682 ** it is advantageous to reduce the "column count" field in
6683 ** the P4 operand of the OP_OpenRead/Write opcode. */
6689 }
6690 #ifdef SQLITE_ENABLE_CURSOR_HINTS
6694 #endif
6695 {
6697 }
6698 #ifdef SQLITE_ENABLE_COLUMN_USED_MASK
6701 #endif
6704 }
6709 /* iAuxArg is always set to a positive value if ONEPASS is possible */
6713 ){
6714 /* This is one term of an OR-optimization using the PRIMARY KEY of a
6715 ** WITHOUT ROWID table. No need for a separate index */
6723 iIndexCur++;
6725 }
6735 }
6739 );
6740 }
6741 }
6755 ){
6757 }
6759 #ifdef SQLITE_ENABLE_COLUMN_USED_MASK
6760 {
6769 }
6772 }
6774 }
6775 }
6779 ){
6795 }
6800 }
6802 /* The nature of RIGHT JOIN processing is such that it messes up
6803 ** the output order. So omit any ORDER BY/GROUP BY elimination
6804 ** optimizations. We need to do an actual sort for RIGHT JOIN. */
6807 }
6808 }
6812 /* Generate the code to do the search. Each iteration of the for
6813 ** loop below generates code for a single nested loop of the VM
6814 ** program.
6815 */
6831 }
6832 }
6836 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
6838 #endif
6841 }
6843 }
6846 );
6852 }
6853 }
6855 /* Done. */
6860 /* Jump here if malloc fails */
6861 whereBeginError:
6865 }
6866 #ifdef WHERETRACE_ENABLED
6867 /* Prevent harmless compiler warnings about debugging routines
6868 ** being declared but never used */
6872 }
6874 /*
6875 ** Part of sqlite3WhereEnd() will rewrite opcodes to reference the
6876 ** index rather than the main table. In SQLITE_DEBUG mode, we want
6877 ** to trace those changes if PRAGMA vdbe_addoptrace=on. This routine
6878 ** does that.
6879 */
6880 #ifndef SQLITE_DEBUG
6882 #else
6883 # define OpcodeRewriteTrace(D,K,P) sqlite3WhereOpcodeRewriteTrace(D,K,P)
6887 VdbeOp *pOp
6888 ){
6891 }
6892 #endif
6894 /*
6895 ** Generate the end of the WHERE loop. See comments on
6896 ** sqlite3WhereBegin() for additional information.
6897 */
6909 /* Generate loop termination code.
6910 */
6916 /* Terminate the subroutine that forms the interior of the loop of
6917 ** the RIGHT JOIN table */
6924 nRJ++;
6925 }
6928 #ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT
6938 ){
6943 }
6950 }
6952 /* The common case: Advance to the next row */
6964 }
6965 #ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT
6967 #endif
6970 }
6985 /* For LEFT JOIN queries, cursor pIn->iCur may not have been
6986 ** opened yet. This occurs for WHERE clauses such as
6987 ** "a = ? AND b IN (...)", where the index is on (a, b). If
6988 ** the RHS of the (a=?) is NULL, then the "b IN (...)" may
6989 ** never have been coded, but the body of the loop run to
6990 ** return the null-row. So, if the cursor is not open yet,
6991 ** jump over the OP_Next or OP_Prev instruction about to
6992 ** be coded. */
6996 }
7002 /* Retarget the OP_IsNull against the left operand of IN so
7003 ** it jumps past the OP_IfNoHope. This is because the
7004 ** OP_IsNull also bypasses the OP_Affinity opcode that is
7005 ** required by OP_IfNoHope. */
7007 }
7008 }
7013 }
7015 }
7016 }
7021 }
7027 }
7028 #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
7033 }
7034 #endif
7048 }
7050 }
7053 ){
7059 }
7061 }
7066 }
7068 }
7071 }
7083 /* Do RIGHT JOIN processing. Generate code that will output the
7084 ** unmatched rows of the right operand of the RIGHT JOIN with
7085 ** all of the columns of the left operand set to NULL.
7086 */
7090 }
7092 /* For a co-routine, change all OP_Column references to the table of
7093 ** the co-routine into OP_Copy of result contained in a register.
7094 ** OP_Rowid becomes OP_Null.
7095 */
7102 }
7104 /* If this scan uses an index, make VDBE code substitutions to read data
7105 ** from the index instead of from the table where possible. In some cases
7106 ** this optimization prevents the table from ever being read, which can
7107 ** yield a significant performance boost.
7108 **
7109 ** Calls to the code generator in between sqlite3WhereBegin and
7110 ** sqlite3WhereEnd will have created code that references the table
7111 ** directly. This loop scans all that code looking for opcodes
7112 ** that reference the table and converts them into opcodes that
7113 ** reference the index.
7114 */
7119 }
7122 ){
7127 }
7132 #ifdef WHERETRACE_ENABLED
7137 }
7138 #endif
7141 }
7143 }
7144 }
7146 #ifdef SQLITE_DEBUG
7150 }
7151 /* Proof that the "+1" on the k value above is safe */
7156 #endif
7162 /* no-op */
7164 #ifdef SQLITE_ENABLE_OFFSET_SQL_FUNC
7166 #endif
7167 ){
7170 #ifdef SQLITE_ENABLE_OFFSET_SQL_FUNC
7172 /* Do not need to translate the column number */
7174 #endif
7182 }
7189 /* Unable to translate the table reference into an index
7190 ** reference. Verify that this is harmless - that the
7191 ** table being referenced really is open.
7192 */
7196 }
7197 }
7205 }
7206 #ifdef SQLITE_DEBUG
7207 k++;
7208 #endif
7210 #ifdef SQLITE_DEBUG
7212 #endif
7213 }
7214 }
7216 /* The "break" point is here, just past the end of the outer loop.
7217 ** Set it.
7218 */
7221 /* Final cleanup
7222 */
7227 }