| blob | 820e9224903ed1e2950bfec2e4db8867ee1c21a7 |
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 }
3967 }
3968 }
3970 /* Full scan via index */
3981 )
3982 ){
3985 /* The cost of visiting the index rows is N*K, where K is
3986 ** between 1.1 and 3.0, depending on the relative sizes of the
3987 ** index and table rows. */
3990 /* If this is a non-covering index scan, add in the cost of
3991 ** doing table lookups. The cost will be 3x the number of
3992 ** lookups. Take into account WHERE clause terms that can be
3993 ** satisfied using just the index, and that do not require a
3994 ** table lookup. */
4003 }
4004 /* pTerm can be evaluated using just the index. So reduce
4005 ** the expected number of table lookups accordingly */
4009 nLookup--;
4011 }
4012 }
4015 }
4019 /* Do not do an SCAN of a index-on-expression in a RIGHT JOIN
4020 ** because the cursor used to access the index might not be
4021 ** positioned to the correct row during the right-join no-match
4022 ** loop. */
4025 }
4028 }
4029 }
4034 /* If a non-unique index is used, or if a prefix of the key for
4035 ** unique index is used (making the index functionally non-unique)
4036 ** then the sqlite_stat1 data becomes important for scoring the
4037 ** plan */
4039 }
4040 #ifdef SQLITE_ENABLE_STAT4
4044 #endif
4045 }
4047 }
4049 #ifndef SQLITE_OMIT_VIRTUALTABLE
4051 /*
4052 ** Return true if pTerm is a virtual table LIMIT or OFFSET term.
4053 */
4058 }
4060 /*
4061 ** Return true if the first nCons constraints in the pUsage array are
4062 ** marked as in-use (have argvIndex>0). False otherwise.
4063 */
4066 int nCons
4067 ){
4071 }
4073 }
4075 /*
4076 ** Argument pIdxInfo is already populated with all constraints that may
4077 ** be used by the virtual table identified by pBuilder->pNew->iTab. This
4078 ** function marks a subset of those constraints usable, invokes the
4079 ** xBestIndex method and adds the returned plan to pBuilder.
4080 **
4081 ** A constraint is marked usable if:
4082 **
4083 ** * Argument mUsable indicates that its prerequisites are available, and
4084 **
4085 ** * It is not one of the operators specified in the mExclude mask passed
4086 ** as the fourth argument (which in practice is either WO_IN or 0).
4087 **
4088 ** Argument mPrereq is a mask of tables that must be scanned before the
4089 ** virtual table in question. These are added to the plans prerequisites
4090 ** before it is added to pBuilder.
4091 **
4092 ** Output parameter *pbIn is set to true if the plan added to pBuilder
4093 ** uses one or more WO_IN terms, or false otherwise.
4094 */
4104 ){
4121 /* Set the usable flag on the subset of constraints identified by
4122 ** arguments mUsable and mExclude. */
4130 ){
4132 }
4133 }
4135 /* Initialize the output fields of the sqlite3_index_info structure */
4147 /* Invoke the virtual table xBestIndex() method */
4151 /* If the xBestIndex method returns SQLITE_CONSTRAINT, that means
4152 ** that the particular combination of parameters provided is unusable.
4153 ** Make no entries in the loop table.
4154 */
4157 }
4159 }
4176 ){
4180 }
4197 }
4200 }
4201 }
4205 /* A virtual table that is constrained by an IN clause may not
4206 ** consume the ORDER BY clause because (1) the order of IN terms
4207 ** is not necessarily related to the order of output terms and
4208 ** (2) Multiple outputs from a single IN value will not merge
4209 ** together. */
4213 }
4215 /* Unless pbRetryLimit is non-NULL, there should be no LIMIT/OFFSET
4216 ** terms. And if there are any, they should follow all other terms. */
4222 /* If there is an IN(...) term handled as an == (separate call to
4223 ** xFilter for each value on the RHS of the IN) and a LIMIT or
4224 ** OFFSET term handled as well, the plan is unusable. Similarly,
4225 ** if there is a LIMIT/OFFSET and there are other unused terms,
4226 ** the plan cannot be used. In these cases set variable *pbRetryLimit
4227 ** to true to tell the caller to retry with LIMIT and OFFSET
4228 ** disabled. */
4233 }
4236 }
4237 }
4238 }
4243 /* The non-zero argvIdx values must be contiguous. Raise an
4244 ** error if they are not */
4248 }
4249 }
4261 /* Set the WHERE_ONEROW flag if the xBestIndex() method indicated
4262 ** that the scan will visit at most one row. Clear it otherwise. */
4267 }
4272 }
4278 }
4280 /*
4281 ** Return the collating sequence for a constraint passed into xBestIndex.
4282 **
4283 ** pIdxInfo must be an sqlite3_index_info structure passed into xBestIndex.
4284 ** This routine depends on there being a HiddenIndexInfo structure immediately
4285 ** following the sqlite3_index_info structure.
4286 **
4287 ** Return a pointer to the collation name:
4288 **
4289 ** 1. If there is an explicit COLLATE operator on the constraint, return it.
4290 **
4291 ** 2. Else, if the column has an alternative collation, return that.
4292 **
4293 ** 3. Otherwise, return "BINARY".
4294 */
4304 }
4306 }
4308 }
4310 /*
4311 ** Return true if constraint iCons is really an IN(...) constraint, or
4312 ** false otherwise. If iCons is an IN(...) constraint, set (if bHandle!=0)
4313 ** or clear (if bHandle==0) the flag to handle it using an iterator.
4314 */
4323 }
4325 }
4327 }
4329 /*
4330 ** This interface is callable from within the xBestIndex callback only.
4331 **
4332 ** If possible, set (*ppVal) to point to an object containing the value
4333 ** on the right-hand-side of constraint iCons.
4334 */
4339 ){
4351 );
4353 }
4355 }
4360 }
4363 }
4365 /*
4366 ** Return true if ORDER BY clause may be handled as DISTINCT.
4367 */
4372 }
4374 /*
4375 ** Cause the prepared statement that is associated with a call to
4376 ** xBestIndex to potentially use all schemas. If the statement being
4377 ** prepared is read-only, then just start read transactions on all
4378 ** schemas. But if this is a write operation, start writes on all
4379 ** schemas.
4380 **
4381 ** This is used by the (built-in) sqlite_dbpage virtual table.
4382 */
4388 }
4392 }
4393 }
4394 }
4396 /*
4397 ** Add all WhereLoop objects for a table of the join identified by
4398 ** pBuilder->pNew->iTab. That table is guaranteed to be a virtual table.
4399 **
4400 ** If there are no LEFT or CROSS JOIN joins in the query, both mPrereq and
4401 ** mUnusable are set to 0. Otherwise, mPrereq is a mask of all FROM clause
4402 ** entries that occur before the virtual table in the FROM clause and are
4403 ** separated from it by at least one LEFT or CROSS JOIN. Similarly, the
4404 ** mUnusable mask contains all FROM clause entries that occur after the
4405 ** virtual table and are separated from it by at least one LEFT or
4406 ** CROSS JOIN.
4407 **
4408 ** For example, if the query were:
4409 **
4410 ** ... FROM t1, t2 LEFT JOIN t3, t4, vt CROSS JOIN t5, t6;
4411 **
4412 ** then mPrereq corresponds to (t1, t2) and mUnusable to (t5, t6).
4413 **
4414 ** All the tables in mPrereq must be scanned before the current virtual
4415 ** table. So any terms for which all prerequisites are satisfied by
4416 ** mPrereq may be specified as "usable" in all calls to xBestIndex.
4417 ** Conversely, all tables in mUnusable must be scanned after the current
4418 ** virtual table, so any terms for which the prerequisites overlap with
4419 ** mUnusable should always be configured as "not-usable" for xBestIndex.
4420 */
4424 Bitmask mUnusable /* Tables that must be scanned after this one */
4425 ){
4436 u16 mNoOmit;
4456 }
4458 /* First call xBestIndex() with all constraints usable. */
4463 );
4468 );
4469 }
4471 /* If the call to xBestIndex() with all terms enabled produced a plan
4472 ** that does not require any source tables (IOW: a plan with mBest==0)
4473 ** and does not use an IN(...) operator, then there is no point in making
4474 ** any further calls to xBestIndex() since they will all return the same
4475 ** result (if the xBestIndex() implementation is sane). */
4482 /* If the plan produced by the earlier call uses an IN(...) term, call
4483 ** xBestIndex again, this time with IN(...) terms disabled. */
4493 }
4494 }
4496 /* Call xBestIndex once for each distinct value of (prereqRight & ~mPrereq)
4497 ** in the set of terms that apply to the current virtual table. */
4503 Bitmask mThis = (
4505 );
4507 }
4518 }
4519 }
4521 /* If the calls to xBestIndex() in the above loop did not find a plan
4522 ** that requires no source tables at all (i.e. one guaranteed to be
4523 ** usable), make a call here with all source tables disabled */
4529 }
4531 /* If the calls to xBestIndex() have so far failed to find a plan
4532 ** that requires no source tables at all and does not use an IN(...)
4533 ** operator, make a final call to obtain one here. */
4538 }
4539 }
4545 }
4548 /*
4549 ** Add WhereLoop entries to handle OR terms. This works for either
4550 ** btrees or virtual tables.
4551 */
4554 Bitmask mPrereq,
4555 Bitmask mUnusable
4556 ){
4563 WhereClause tempWC;
4564 WhereLoopBuilder sSubBuild;
4575 /* The multi-index OR optimization does not work for RIGHT and FULL JOIN */
4581 ){
4605 }
4607 #ifdef WHERETRACE_ENABLED
4612 }
4613 #endif
4614 #ifndef SQLITE_OMIT_VIRTUALTABLE
4618 #endif
4619 {
4621 }
4624 }
4634 WhereOrSet sPrev;
4642 }
4643 }
4644 }
4645 }
4653 /* TUNING: Currently sSum.a[i].rRun is set to the sum of the costs
4654 ** of all sub-scans required by the OR-scan. However, due to rounding
4655 ** errors, it may be that the cost of the OR-scan is equal to its
4656 ** most expensive sub-scan. Add the smallest possible penalty
4657 ** (equivalent to multiplying the cost by 1.07) to ensure that
4658 ** this does not happen. Otherwise, for WHERE clauses such as the
4659 ** following where there is an index on "y":
4660 **
4661 ** WHERE likelihood(x=?, 0.99) OR y=?
4662 **
4663 ** the planner may elect to "OR" together a full-table scan and an
4664 ** index lookup. And other similarly odd results. */
4669 }
4671 }
4672 }
4674 }
4676 /*
4677 ** Add all WhereLoop objects for all tables
4678 */
4694 /* Loop over the tables in the join, from left to right */
4697 /* Verify that pNew has already been initialized */
4711 ){
4712 /* Add prerequisites to prevent reordering of FROM clause terms
4713 ** across CROSS joins and outer joins. The bFirstPastRJ boolean
4714 ** prevents the right operand of a RIGHT JOIN from being swapped with
4715 ** other elements even further to the right.
4716 **
4717 ** The JT_LTORJ case and the hasRightJoin flag work together to
4718 ** prevent FROM-clause terms from moving from the right side of
4719 ** a LEFT JOIN over to the left side of that join if the LEFT JOIN
4720 ** is itself on the left side of a RIGHT JOIN.
4721 */
4727 }
4728 #ifndef SQLITE_OMIT_VIRTUALTABLE
4734 }
4735 }
4739 {
4741 }
4744 }
4748 /* We hit the query planner search limit set by iPlanLimit */
4753 }
4754 }
4755 }
4759 }
4761 /*
4762 ** Examine a WherePath (with the addition of the extra WhereLoop of the 6th
4763 ** parameters) to see if it outputs rows in the requested ORDER BY
4764 ** (or GROUP BY) without requiring a separate sort operation. Return N:
4765 **
4766 ** N>0: N terms of the ORDER BY clause are satisfied
4767 ** N==0: No terms of the ORDER BY clause are satisfied
4768 ** N<0: Unknown yet how many terms of ORDER BY might be satisfied.
4769 **
4770 ** Note that processing for WHERE_GROUPBY and WHERE_DISTINCTBY is not as
4771 ** strict. With GROUP BY and DISTINCT the only requirement is that
4772 ** equivalent rows appear immediately adjacent to one another. GROUP BY
4773 ** and DISTINCT do not require rows to appear in any particular order as long
4774 ** as equivalent rows are grouped together. Thus for GROUP BY and DISTINCT
4775 ** the pOrderBy terms can be matched in any order. With ORDER BY, the
4776 ** pOrderBy terms must be matched in strict left-to-right order.
4777 */
4786 ){
4812 /*
4813 ** We say the WhereLoop is "one-row" if it generates no more than one
4814 ** row of output. A WhereLoop is one-row if all of the following are true:
4815 ** (a) All index columns match with WHERE_COLUMN_EQ.
4816 ** (b) The index is unique
4817 ** Any WhereLoop with an WHERE_COLUMN_EQ constraint on the rowid is one-row.
4818 ** Every one-row WhereLoop will have the WHERE_ONEROW bit set in wsFlags.
4819 **
4820 ** We say the WhereLoop is "order-distinct" if the set of columns from
4821 ** that WhereLoop that are in the ORDER BY clause are different for every
4822 ** row of the WhereLoop. Every one-row WhereLoop is automatically
4823 ** order-distinct. A WhereLoop that has no columns in the ORDER BY clause
4824 ** is not order-distinct. To be order-distinct is not quite the same as being
4825 ** UNIQUE since a UNIQUE column or index can have multiple rows that
4826 ** are NULL and NULL values are equivalent for the purpose of order-distinct.
4827 ** To be order-distinct, the columns must be UNIQUE and NOT NULL.
4828 **
4829 ** The rowid for a table is always UNIQUE and NOT NULL so whenever the
4830 ** rowid appears in the ORDER BY clause, the corresponding WhereLoop is
4831 ** automatically order-distinct.
4832 */
4847 }
4855 }
4859 ){
4861 }
4865 }
4868 /* Mark off any ORDER BY term X that is a column in the table of
4869 ** the current loop for which there is term in the WHERE
4870 ** clause of the form X IS NULL or X=? that reference only outer
4871 ** loops.
4872 */
4883 /* IN terms are only valid for sorting in the ORDER BY LIMIT
4884 ** optimization, and then only if they are actually used
4885 ** by the query plan */
4890 }
4898 }
4900 }
4902 }
4917 /* All relevant terms of the index must also be non-NULL in order
4918 ** for isOrderDistinct to be true. So the isOrderDistint value
4919 ** computed here might be a false positive. Corrections will be
4920 ** made at tag-20210426-1 below */
4923 }
4925 /* Loop through all columns of the index and deal with the ones
4926 ** that are not constrained by == or IN.
4927 */
4935 );
4939 /* Skip over == and IS and ISNULL terms. (Also skip IN terms when
4940 ** doing WHERE_ORDERBY_LIMIT processing). Except, IS and ISNULL
4941 ** terms imply that the index is not UNIQUE NOT NULL in which case
4942 ** the loop need to be marked as not order-distinct because it can
4943 ** have repeated NULL rows.
4944 **
4945 ** If the current term is a column of an ((?,?) IN (SELECT...))
4946 ** expression for which the SELECT returns more than one column,
4947 ** check that it is the only column used by this loop. Otherwise,
4948 ** if it is one of two or more, none of the columns can be
4949 ** considered to match an ORDER BY term.
4950 */
4957 }
4960 /* ALWAYS() justification: eOp is an equality operator due to the
4961 ** j<pLoop->u.btree.nEq constraint above. Any equality other
4962 ** than WO_IN is captured by the previous "if". So this one
4963 ** always has to be WO_IN. */
4970 }
4971 }
4972 }
4973 }
4975 /* Get the column number in the table (iColumn) and sort order
4976 ** (revIdx) for the j-th column of the index.
4977 */
4985 }
4987 /* An unconstrained column that might be NULL means that this
4988 ** WhereLoop is not well-ordered. tag-20210426-1
4989 */
4994 ){
4996 }
4999 }
5000 }
5002 /* Find the ORDER BY term that corresponds to the j-th column
5003 ** of the index and mark that ORDER BY term off
5004 */
5021 }
5022 }
5026 }
5029 }
5032 }
5034 /* Make sure the sort order is compatible in an ORDER BY clause.
5035 ** Sort order is irrelevant for a GROUP BY clause. */
5039 ){
5041 }
5046 }
5047 }
5053 }
5054 }
5059 }
5062 /* No match found */
5066 }
5068 }
5073 }
5076 /* Mark off any other ORDER BY terms that reference pLoop */
5081 Bitmask mTerm;
5088 }
5089 }
5090 }
5097 }
5099 }
5101 }
5104 /*
5105 ** If the WHERE_GROUPBY flag is set in the mask passed to sqlite3WhereBegin(),
5106 ** the planner assumes that the specified pOrderBy list is actually a GROUP
5107 ** BY clause - and so any order that groups rows as required satisfies the
5108 ** request.
5109 **
5110 ** Normally, in this case it is not possible for the caller to determine
5111 ** whether or not the rows are really being delivered in sorted order, or
5112 ** just in some other order that provides the required grouping. However,
5113 ** if the WHERE_SORTBYGROUP flag is also passed to sqlite3WhereBegin(), then
5114 ** this function may be called on the returned WhereInfo object. It returns
5115 ** true if the rows really will be sorted in the specified order, or false
5116 ** otherwise.
5117 **
5118 ** For example, assuming:
5119 **
5120 ** CREATE INDEX i1 ON t1(x, Y);
5121 **
5122 ** then
5123 **
5124 ** SELECT * FROM t1 GROUP BY x,y ORDER BY x,y; -- IsSorted()==1
5125 ** SELECT * FROM t1 GROUP BY y,x ORDER BY y,x; -- IsSorted()==0
5126 */
5131 }
5133 #ifdef WHERETRACE_ENABLED
5134 /* For debugging use only: */
5142 }
5143 #endif
5145 /*
5146 ** Return the cost of sorting nRow rows, assuming that the keys have
5147 ** nOrderby columns and that the first nSorted columns are already in
5148 ** order.
5149 */
5155 ){
5156 /* Estimated cost of a full external sort, where N is
5157 ** the number of rows to sort is:
5158 **
5159 ** cost = (K * N * log(N)).
5160 **
5161 ** Or, if the order-by clause has X terms but only the last Y
5162 ** terms are out of order, then block-sorting will reduce the
5163 ** sorting cost to:
5164 **
5165 ** cost = (K * N * log(N)) * (Y/X)
5166 **
5167 ** The constant K is at least 2.0 but will be larger if there are a
5168 ** large number of columns to be sorted, as the sorting time is
5169 ** proportional to the amount of content to be sorted. The algorithm
5170 ** does not currently distinguish between fat columns (BLOBs and TEXTs)
5171 ** and skinny columns (INTs). It just uses the number of columns as
5172 ** an approximation for the row width.
5173 **
5174 ** And extra factor of 2.0 or 3.0 is added to the sorting cost if the sort
5175 ** is built using OP_IdxInsert and OP_Sort rather than with OP_SorterInsert.
5176 */
5180 /* TUNING: sorting cost proportional to the number of output columns: */
5184 /* Scale the result by (Y/X) */
5186 }
5188 /* Multiple by log(M) where M is the number of output rows.
5189 ** Use the LIMIT for M if it is smaller. Or if this sort is for
5190 ** a DISTINCT operator, M will be the number of distinct output
5191 ** rows, so fudge it downwards a bit.
5192 */
5197 }
5200 }
5202 /* TUNING: In the sort for a DISTINCT operator, assume that the DISTINCT
5203 ** reduces the number of output rows by a factor of 2 */
5205 }
5208 }
5210 /*
5211 ** Given the list of WhereLoop objects at pWInfo->pLoops, this routine
5212 ** attempts to find the lowest cost path that visits each WhereLoop
5213 ** once. This path is then loaded into the pWInfo->a[].pWLoop fields.
5214 **
5215 ** Assume that the total number of output rows that will need to be sorted
5216 ** will be nRowEst (in the 10*log2 representation). Or, ignore sorting
5217 ** costs if nRowEst==0.
5218 **
5219 ** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation
5220 ** error occurs.
5221 */
5245 /* TUNING: For simple queries, only the best path is tracked.
5246 ** For 2-way joins, the 5 best paths are followed.
5247 ** For joins of 3 or more tables, track the 10 best paths */
5253 /* If nRowEst is zero and there is an ORDER BY clause, ignore it. In this
5254 ** case the purpose of this call is to estimate the number of rows returned
5255 ** by the overall query. Once this estimate has been obtained, the caller
5256 ** will invoke this function a second time, passing the estimate as the
5257 ** nRowEst parameter. */
5262 }
5264 /* Allocate and initialize space for aTo, aFrom and aSortCost[] */
5275 }
5277 /* If there is an ORDER BY clause and it is not being ignored, set up
5278 ** space for the aSortCost[] array. Each element of the aSortCost array
5279 ** is either zero - meaning it has not yet been initialized - or the
5280 ** cost of sorting nRowEst rows of data where the first X terms of
5281 ** the ORDER BY clause are already in order, where X is the array
5282 ** index. */
5285 }
5289 /* Seed the search with a single WherePath containing zero WhereLoops.
5290 **
5291 ** TUNING: Do not let the number of iterations go above 28. If the cost
5292 ** of computing an automatic index is not paid back within the first 28
5293 ** rows, then do not use the automatic index. */
5298 /* If nLoop is zero, then there are no FROM terms in the query. Since
5299 ** in this case the query may return a maximum of one row, the results
5300 ** are already in the requested order. Set isOrdered to nOrderBy to
5301 ** indicate this. Or, if nLoop is greater than zero, set isOrdered to
5302 ** -1, indicating that the result set may or may not be ordered,
5303 ** depending on the loops added to the current plan. */
5305 }
5307 /* Compute successively longer WherePaths using the previous generation
5308 ** of WherePaths as the basis for the next. Keep track of the mxChoice
5309 ** best paths at each generation */
5324 /* Do not use an automatic index if the this loop is expected
5325 ** to run less than 1.25 times. It is tempting to also exclude
5326 ** automatic index usage on an outer loop, but sometimes an automatic
5327 ** index is useful in the outer loop of a correlated subquery. */
5330 }
5332 /* At this point, pWLoop is a candidate to be the next loop.
5333 ** Compute its cost */
5346 }
5351 );
5352 }
5353 /* TUNING: Add a small extra penalty (3) to sorting as an
5354 ** extra encouragement to the query planner to select a plan
5355 ** where the rows emerge in the correct order without any sorting
5356 ** required. */
5366 }
5368 /* Check to see if pWLoop should be added to the set of
5369 ** mxChoice best-so-far paths.
5370 **
5371 ** First look for an existing path among best-so-far paths
5372 ** that covers the same set of loops and has the same isOrdered
5373 ** setting as the current path candidate.
5374 **
5375 ** The term "((pTo->isOrdered^isOrdered)&0x80)==0" is equivalent
5376 ** to (pTo->isOrdered==(-1))==(isOrdered==(-1))" for the range
5377 ** of legal values for isOrdered, -1..64.
5378 */
5382 ){
5385 }
5386 }
5388 /* None of the existing best-so-far paths match the candidate. */
5391 ){
5392 /* The current candidate is no better than any of the mxChoice
5393 ** paths currently in the best-so-far buffer. So discard
5394 ** this candidate as not viable. */
5400 }
5401 #endif
5403 }
5404 /* If we reach this points it means that the new candidate path
5405 ** needs to be added to the set of best-so-far paths. */
5407 /* Increase the size of the aTo set by one */
5410 /* New path replaces the prior worst to keep count below mxChoice */
5412 }
5419 }
5420 #endif
5422 /* Control reaches here if best-so-far path pTo=aTo[jj] covers the
5423 ** same set of loops and has the same isOrdered setting as the
5424 ** candidate path. Check to see if the candidate should replace
5425 ** pTo or if the candidate should be skipped.
5426 **
5427 ** The conditional is an expanded vector comparison equivalent to:
5428 ** (pTo->rCost,pTo->nRow,pTo->rUnsorted) <= (rCost,nOut,rUnsorted)
5429 */
5434 )
5435 )
5436 ){
5446 }
5447 #endif
5448 /* Discard the candidate path from further consideration */
5451 }
5453 /* Control reaches here if the candidate path is better than the
5454 ** pTo path. Replace pTo with the candidate. */
5464 }
5465 #endif
5466 }
5467 /* pWLoop is a winner. Add it to the set of best so far */
5483 ){
5487 }
5488 }
5489 }
5490 }
5491 }
5504 }
5505 }
5506 }
5507 #endif
5509 /* Swap the roles of aFrom and aTo for the next generation */
5514 }
5520 }
5522 /* Find the lowest cost path. pFrom will be left pointing to that path */
5526 }
5528 /* Load the lowest cost path into pWInfo */
5534 }
5538 && nRowEst
5539 ){
5540 Bitmask notUsed;
5545 }
5546 }
5553 }
5554 /* vvv--- See check-in [12ad822d9b827777] on 2023-03-16 ---vvv */
5565 ){
5574 }
5575 }
5576 }
5580 ){
5582 }
5583 }
5586 ){
5590 );
5595 }
5596 }
5597 }
5601 /* Free temporary memory and return success */
5604 }
5606 /*
5607 ** This routine implements a heuristic designed to improve query planning.
5608 ** This routine is called in between the first and second call to
5609 ** wherePathSolver(). Hence the name "Interstage" "Heuristic".
5610 **
5611 ** The first call to wherePathSolver() (hereafter just "solver()") computes
5612 ** the best path without regard to the order of the outputs. The second call
5613 ** to the solver() builds upon the first call to try to find an alternative
5614 ** path that satisfies the ORDER BY clause.
5615 **
5616 ** This routine looks at the results of the first solver() run, and for
5617 ** every FROM clause term in the resulting query plan that uses an equality
5618 ** constraint against an index, disable other WhereLoops for that same
5619 ** FROM clause term that would try to do a full-table scan. This prevents
5620 ** an index search from being converted into a full-table scan in order to
5621 ** satisfy an ORDER BY clause, since even though we might get slightly better
5622 ** performance using the full-scan without sorting if the output size
5623 ** estimates are very precise, we might also get severe performance
5624 ** degradation using the full-scan if the output size estimate is too large.
5625 ** It is better to err on the side of caution.
5626 **
5627 ** Except, if the first solver() call generated a full-table scan in an outer
5628 ** loop then stop this analysis at the first full-scan, since the second
5629 ** solver() run might try to swap that full-scan for another in order to
5630 ** get the output into the correct order. In other words, we allow a
5631 ** rewrite like this:
5632 **
5633 ** First Solver() Second Solver()
5634 ** |-- SCAN t1 |-- SCAN t2
5635 ** |-- SEARCH t2 `-- SEARCH t1
5636 ** `-- SORT USING B-TREE
5637 **
5638 ** The purpose of this routine is to disallow rewrites such as:
5639 **
5640 ** First Solver() Second Solver()
5641 ** |-- SEARCH t1 |-- SCAN t2 <--- bad!
5642 ** |-- SEARCH t2 `-- SEARCH t1
5643 ** `-- SORT USING B-TREE
5644 **
5645 ** See test cases in test/whereN.test for the real-world query that
5646 ** originally provoked this heuristic.
5647 */
5650 #ifdef WHERETRACE_ENABLED
5652 #endif
5663 /* Auto-index and index-constrained loops allowed to remain */
5665 }
5666 #ifdef WHERETRACE_ENABLED
5671 }
5673 }
5676 }
5679 }
5680 }
5681 }
5683 /*
5684 ** Most queries use only a single table (they are not joins) and have
5685 ** simple == constraints against indexed fields. This routine attempts
5686 ** to plan those simple cases using much less ceremony than the
5687 ** general-purpose query planner, and thereby yield faster sqlite3_prepare()
5688 ** times for the common case.
5689 **
5690 ** Return non-zero on success, if this query can be handled by this
5691 ** no-frills query planner. Return zero if this query needs the
5692 ** general-purpose query planner.
5693 */
5704 WhereScan scan;
5716 }
5730 /* TUNING: Cost of a rowid lookup is 10 */
5747 }
5752 }
5756 /* TUNING: Cost of a unique index lookup is 15 */
5759 }
5760 }
5771 }
5773 #ifdef SQLITE_DEBUG
5775 #endif
5776 #ifdef WHERETRACE_ENABLED
5779 }
5780 #endif
5782 }
5784 }
5786 /*
5787 ** Helper function for exprIsDeterministic().
5788 */
5793 }
5795 }
5797 /*
5798 ** Return true if the expression contains no non-deterministic SQL
5799 ** functions. Do not consider non-deterministic SQL functions that are
5800 ** part of sub-select statements.
5801 */
5803 Walker w;
5810 }
5813 #ifdef WHERETRACE_ENABLED
5814 /*
5815 ** Display all WhereLoops in pWInfo
5816 */
5826 }
5827 }
5828 }
5829 # define WHERETRACE_ALL_LOOPS(W,C) showAllWhereLoops(W,C)
5830 #else
5831 # define WHERETRACE_ALL_LOOPS(W,C)
5832 #endif
5834 /* Attempt to omit tables from a join that do not affect the result.
5835 ** For a table to not affect the result, the following must be true:
5836 **
5837 ** 1) The query must not be an aggregate.
5838 ** 2) The table must be the RHS of a LEFT JOIN.
5839 ** 3) Either the query must be DISTINCT, or else the ON or USING clause
5840 ** must contain a constraint that limits the scan of the table to
5841 ** at most a single row.
5842 ** 4) The table must not be referenced by any part of the query apart
5843 ** from its own USING or ON clause.
5844 ** 5) The table must not have an inner-join ON or USING clause if there is
5845 ** a RIGHT JOIN anywhere in the query. Otherwise the ON/USING clause
5846 ** might move from the right side to the left side of the RIGHT JOIN.
5847 ** Note: Due to (2), this condition can only arise if the table is
5848 ** the right-most table of a subquery that was flattened into the
5849 ** main query and that subquery was the right-hand operand of an
5850 ** inner join that held an ON or USING clause.
5851 **
5852 ** For example, given:
5853 **
5854 ** CREATE TABLE t1(ipk INTEGER PRIMARY KEY, v1);
5855 ** CREATE TABLE t2(ipk INTEGER PRIMARY KEY, v2);
5856 ** CREATE TABLE t3(ipk INTEGER PRIMARY KEY, v3);
5857 **
5858 ** then table t2 can be omitted from the following:
5859 **
5860 ** SELECT v1, v3 FROM t1
5861 ** LEFT JOIN t2 ON (t1.ipk=t2.ipk)
5862 ** LEFT JOIN t3 ON (t1.ipk=t3.ipk)
5863 **
5864 ** or from:
5865 **
5866 ** SELECT DISTINCT v1, v3 FROM t1
5867 ** LEFT JOIN t2
5868 ** LEFT JOIN t3 ON (t1.ipk=t3.ipk)
5869 */
5872 Bitmask notReady
5873 ){
5875 Bitmask tabUsed;
5878 /* Preconditions checked by the caller */
5882 /* These two preconditions checked by the caller combine to guarantee
5883 ** condition (1) of the header comment */
5890 }
5901 ){
5903 }
5910 ){
5912 }
5913 }
5917 ){
5919 }
5920 }
5927 }
5928 }
5932 }
5935 }
5937 }
5939 /*
5940 ** Check to see if there are any SEARCH loops that might benefit from
5941 ** using a Bloom filter. Consider a Bloom filter if:
5942 **
5943 ** (1) The SEARCH happens more than N times where N is the number
5944 ** of rows in the table that is being considered for the Bloom
5945 ** filter.
5946 ** (2) Some searches are expected to find zero rows. (This is determined
5947 ** by the WHERE_SELFCULL flag on the term.)
5948 ** (3) Bloom-filter processing is not disabled. (Checked by the
5949 ** caller.)
5950 ** (4) The size of the table being searched is known by ANALYZE.
5951 **
5952 ** This block of code merely checks to see if a Bloom filter would be
5953 ** appropriate, and if so sets the WHERE_BLOOMFILTER flag on the
5954 ** WhereLoop. The implementation of the Bloom filter comes further
5955 ** down where the code for each WhereLoop is generated.
5956 */
5959 ){
5974 /* vvvvvv--- Always the case if WHERE_COLUMN_EQ is defined */
5976 ){
5982 "-> use Bloom-filter on loop %c because there are ~%.1e "
5986 }
5987 }
5989 }
5990 }
5992 /*
5993 ** The index pIdx is used by a query and contains one or more expressions.
5994 ** In other words pIdx is an index on an expression. iIdxCur is the cursor
5995 ** number for the index and iDataCur is the cursor number for the corresponding
5996 ** table.
5997 **
5998 ** This routine adds IndexedExpr entries to the Parse->pIdxEpr field for
5999 ** each of the expressions in the index so that the expression code generator
6000 ** will know to replace occurrences of the indexed expression with
6001 ** references to the corresponding column of the index.
6002 */
6008 ){
6023 }
6026 /* Functions that might set a subtype should not be replaced by the
6027 ** value taken from an expression index since the index omits the
6028 ** subtype. https://sqlite.org/forum/forumpost/68d284c86b082c3e */
6037 }
6038 }
6042 #ifdef WHERETRACE_ENABLED
6046 }
6047 #endif
6055 }
6056 #ifdef SQLITE_ENABLE_EXPLAIN_COMMENTS
6058 #endif
6063 }
6064 }
6065 }
6067 /*
6068 ** Set the reverse-scan order mask to one for all tables in the query
6069 ** with the exception of MATERIALIZED common table expressions that have
6070 ** their own internal ORDER BY clauses.
6071 **
6072 ** This implements the PRAGMA reverse_unordered_selects=ON setting.
6073 ** (Also SQLITE_DBCONFIG_REVERSE_SCANORDER).
6074 */
6083 ){
6085 }
6086 }
6087 }
6089 /*
6090 ** Generate the beginning of the loop used for WHERE clause processing.
6091 ** The return value is a pointer to an opaque structure that contains
6092 ** information needed to terminate the loop. Later, the calling routine
6093 ** should invoke sqlite3WhereEnd() with the return value of this function
6094 ** in order to complete the WHERE clause processing.
6095 **
6096 ** If an error occurs, this routine returns NULL.
6097 **
6098 ** The basic idea is to do a nested loop, one loop for each table in
6099 ** the FROM clause of a select. (INSERT and UPDATE statements are the
6100 ** same as a SELECT with only a single table in the FROM clause.) For
6101 ** example, if the SQL is this:
6102 **
6103 ** SELECT * FROM t1, t2, t3 WHERE ...;
6104 **
6105 ** Then the code generated is conceptually like the following:
6106 **
6107 ** foreach row1 in t1 do \ Code generated
6108 ** foreach row2 in t2 do |-- by sqlite3WhereBegin()
6109 ** foreach row3 in t3 do /
6110 ** ...
6111 ** end \ Code generated
6112 ** end |-- by sqlite3WhereEnd()
6113 ** end /
6114 **
6115 ** Note that the loops might not be nested in the order in which they
6116 ** appear in the FROM clause if a different order is better able to make
6117 ** use of indices. Note also that when the IN operator appears in
6118 ** the WHERE clause, it might result in additional nested loops for
6119 ** scanning through all values on the right-hand side of the IN.
6120 **
6121 ** There are Btree cursors associated with each table. t1 uses cursor
6122 ** number pTabList->a[0].iCursor. t2 uses the cursor pTabList->a[1].iCursor.
6123 ** And so forth. This routine generates code to open those VDBE cursors
6124 ** and sqlite3WhereEnd() generates the code to close them.
6125 **
6126 ** The code that sqlite3WhereBegin() generates leaves the cursors named
6127 ** in pTabList pointing at their appropriate entries. The [...] code
6128 ** can use OP_Column and OP_Rowid opcodes on these cursors to extract
6129 ** data from the various tables of the loop.
6130 **
6131 ** If the WHERE clause is empty, the foreach loops must each scan their
6132 ** entire tables. Thus a three-way join is an O(N^3) operation. But if
6133 ** the tables have indices and there are terms in the WHERE clause that
6134 ** refer to those indices, a complete table scan can be avoided and the
6135 ** code will run much faster. Most of the work of this routine is checking
6136 ** to see if there are indices that can be used to speed up the loop.
6137 **
6138 ** Terms of the WHERE clause are also used to limit which rows actually
6139 ** make it to the "..." in the middle of the loop. After each "foreach",
6140 ** terms of the WHERE clause that use only terms in that loop and outer
6141 ** loops are evaluated and if false a jump is made around all subsequent
6142 ** inner loops (or around the "..." if the test occurs within the inner-
6143 ** most loop)
6144 **
6145 ** OUTER JOINS
6146 **
6147 ** An outer join of tables t1 and t2 is conceptually coded as follows:
6148 **
6149 ** foreach row1 in t1 do
6150 ** flag = 0
6151 ** foreach row2 in t2 do
6152 ** start:
6153 ** ...
6154 ** flag = 1
6155 ** end
6156 ** if flag==0 then
6157 ** move the row2 cursor to a null row
6158 ** goto start
6159 ** fi
6160 ** end
6161 **
6162 ** ORDER BY CLAUSE PROCESSING
6163 **
6164 ** pOrderBy is a pointer to the ORDER BY clause (or the GROUP BY clause
6165 ** if the WHERE_GROUPBY flag is set in wctrlFlags) of a SELECT statement
6166 ** if there is one. If there is no ORDER BY clause or if this routine
6167 ** is called from an UPDATE or DELETE statement, then pOrderBy is NULL.
6168 **
6169 ** The iIdxCur parameter is the cursor number of an index. If
6170 ** WHERE_OR_SUBCLAUSE is set, iIdxCur is the cursor number of an index
6171 ** to use for OR clause processing. The WHERE clause should use this
6172 ** specific cursor. If WHERE_ONEPASS_DESIRED is set, then iIdxCur is
6173 ** the first cursor in an array of cursors for all indices. iIdxCur should
6174 ** be used to compute the appropriate cursor depending on which index is
6175 ** used.
6176 */
6186 ** If WHERE_USE_LIMIT, then the limit amount */
6187 ){
6205 ));
6207 /* Only one of WHERE_OR_SUBCLAUSE or WHERE_USE_LIMIT */
6211 /* Variable initialization */
6215 /* An ORDER/GROUP BY clause of more than 63 terms cannot be optimized */
6220 }
6222 /* The number of tables in the FROM clause is limited by the number of
6223 ** bits in a Bitmask
6224 */
6229 }
6231 /* This function normally generates a nested loop for all tables in
6232 ** pTabList. But if the WHERE_OR_SUBCLAUSE flag is set, then we should
6233 ** only generate code for the first table in pTabList and assume that
6234 ** any cursors associated with subsequent tables are uninitialized.
6235 */
6238 /* Allocate and initialize the WhereInfo structure that will become the
6239 ** return value. A single allocation is used to store the WhereInfo
6240 ** struct, the contents of WhereInfo.a[], the WhereClause structure
6241 ** and the WhereMaskSet structure. Since WhereClause contains an 8-byte
6242 ** field (type Bitmask) it must be aligned on an 8-byte boundary on
6243 ** some architectures. Hence the ROUND8() below.
6244 */
6248 }
6254 }
6258 #if WHERETRACE_ENABLED
6260 #endif
6276 ** a valid cursor number, to avoid an initial
6277 ** test for pMaskSet->n==0 in sqlite3WhereGetMask() */
6283 #ifdef SQLITE_DEBUG
6285 #endif
6287 /* Split the WHERE clause into separate subexpressions where each
6288 ** subexpression is separated by an AND operator.
6289 */
6293 /* Special case: No FROM clause
6294 */
6299 ){
6301 }
6304 ){
6306 }
6308 /* Assign a bit from the bitmask to every term in the FROM clause.
6309 **
6310 ** The N-th term of the FROM clause is assigned a bitmask of 1<<N.
6311 **
6312 ** The rule of the previous sentence ensures that if X is the bitmask for
6313 ** a table T, then X-1 is the bitmask for all other tables to the left of T.
6314 ** Knowing the bitmask for all tables to the left of a left join is
6315 ** important. Ticket #3015.
6316 **
6317 ** Note that bitmasks are created for all pTabList->nSrc tables in
6318 ** pTabList, not just the first nTabList tables. nTabList is normally
6319 ** equal to pTabList->nSrc but might be shortened to 1 if the
6320 ** WHERE_OR_SUBCLAUSE flag is set.
6321 */
6327 #ifdef SQLITE_DEBUG
6328 {
6334 }
6335 }
6336 #endif
6337 }
6339 /* Analyze all of the subexpressions. */
6343 }
6346 /* The False-WHERE-Term-Bypass optimization:
6347 **
6348 ** If there are WHERE terms that are false, then no rows will be output,
6349 ** so skip over all of the code generated here.
6350 **
6351 ** Conditions:
6352 **
6353 ** (1) The WHERE term must not refer to any tables in the join.
6354 ** (2) The term must not come from an ON clause on the
6355 ** right-hand side of a LEFT or FULL JOIN.
6356 ** (3) The term must not come from an ON clause, or there must be
6357 ** no RIGHT or FULL OUTER joins in pTabList.
6358 ** (4) If the expression contains non-deterministic functions
6359 ** that are not within a sub-select. This is not required
6360 ** for correctness but rather to preserves SQLite's legacy
6361 ** behaviour in the following two cases:
6362 **
6363 ** WHERE random()>0; -- eval random() once per row
6364 ** WHERE (SELECT random())>0; -- eval random() just once overall
6365 **
6366 ** Note that the Where term need not be a constant in order for this
6367 ** optimization to apply, though it does need to be constant relative to
6368 ** the current subquery (condition 1). The term might include variables
6369 ** from outer queries so that the value of the term changes from one
6370 ** invocation of the current subquery to the next.
6371 */
6383 ){
6386 }
6387 }
6391 /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via
6392 ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */
6396 /* The DISTINCT marking is pointless. Ignore it. */
6399 /* Try to ORDER BY the result set to make distinct processing easier */
6402 }
6403 }
6405 /* Construct the WhereLoop objects */
6406 #if defined(WHERETRACE_ENABLED)
6411 }
6414 Select sSelect;
6422 }
6426 }
6427 }
6428 #endif
6434 #ifdef SQLITE_ENABLE_STAT4
6435 /* If one or more WhereTerm.truthProb values were used in estimating
6436 ** loop parameters, but then those truthProb values were subsequently
6437 ** changed based on STAT4 information while computing subsequent loops,
6438 ** then we need to rerun the whole loop building process so that all
6439 ** loops will be built using the revised truthProb values. */
6449 }
6452 }
6453 #endif
6462 }
6464 /* TUNING: Assume that a DISTINCT clause on a subquery reduces
6465 ** the output size by a factor of 8 (LogEst -30).
6466 */
6471 }
6473 }
6477 }
6480 }
6482 #ifdef WHERETRACE_ENABLED
6487 }
6492 }
6496 }
6500 }
6501 }
6505 }
6506 }
6507 #endif
6509 /* Attempt to omit tables from a join that do not affect the result.
6510 ** See the comment on whereOmitNoopJoin() for further information.
6511 **
6512 ** This query optimization is factored out into a separate "no-inline"
6513 ** procedure to keep the sqlite3WhereBegin() procedure from becoming
6514 ** too large. If sqlite3WhereBegin() becomes too large, that prevents
6515 ** some C-compiler optimizers from in-lining the
6516 ** sqlite3WhereCodeOneLoopStart() procedure, and it is important to
6517 ** in-line sqlite3WhereCodeOneLoopStart() for performance reasons.
6518 */
6524 ){
6528 }
6530 /* Check to see if there are any SEARCH loops that might benefit from
6531 ** using a Bloom filter.
6532 */
6535 ){
6537 }
6539 #if defined(WHERETRACE_ENABLED)
6543 }
6545 #endif
6548 /* If the caller is an UPDATE or DELETE statement that is requesting
6549 ** to use a one-pass algorithm, determine if this is appropriate.
6550 **
6551 ** A one-pass approach can be used if the caller has requested one
6552 ** and either (a) the scan visits at most one row or (b) each
6553 ** of the following are true:
6554 **
6555 ** * the caller has indicated that a one-pass approach can be used
6556 ** with multiple rows (by setting WHERE_ONEPASS_MULTIROW), and
6557 ** * the table is not a virtual table, and
6558 ** * either the scan does not use the OR optimization or the caller
6559 ** is a DELETE operation (WHERE_DUPLICATES_OK is only specified
6560 ** for DELETE).
6561 **
6562 ** The last qualification is because an UPDATE statement uses
6563 ** WhereInfo.aiCurOnePass[1] to determine whether or not it really can
6564 ** use a one-pass approach, and this is not set accurately for scans
6565 ** that use the OR optimization.
6566 */
6577 )){
6582 }
6584 }
6585 }
6586 }
6588 /* Open all tables in the pTabList and any indices selected for
6589 ** searching those tables.
6590 */
6601 /* Do nothing */
6603 #ifndef SQLITE_OMIT_VIRTUALTABLE
6609 /* noop */
6611 #endif
6615 ){
6620 };
6629 ){
6630 /* If we know that only a prefix of the record will be used,
6631 ** it is advantageous to reduce the "column count" field in
6632 ** the P4 operand of the OP_OpenRead/Write opcode. */
6638 }
6639 #ifdef SQLITE_ENABLE_CURSOR_HINTS
6643 #endif
6644 {
6646 }
6647 #ifdef SQLITE_ENABLE_COLUMN_USED_MASK
6650 #endif
6653 }
6658 /* iAuxArg is always set to a positive value if ONEPASS is possible */
6662 ){
6663 /* This is one term of an OR-optimization using the PRIMARY KEY of a
6664 ** WITHOUT ROWID table. No need for a separate index */
6672 iIndexCur++;
6674 }
6684 }
6688 );
6689 }
6690 }
6704 ){
6706 }
6708 #ifdef SQLITE_ENABLE_COLUMN_USED_MASK
6709 {
6718 }
6721 }
6723 }
6724 }
6728 ){
6744 }
6749 }
6751 /* The nature of RIGHT JOIN processing is such that it messes up
6752 ** the output order. So omit any ORDER BY/GROUP BY elimination
6753 ** optimizations. We need to do an actual sort for RIGHT JOIN. */
6756 }
6757 }
6761 /* Generate the code to do the search. Each iteration of the for
6762 ** loop below generates code for a single nested loop of the VM
6763 ** program.
6764 */
6780 }
6781 }
6785 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
6787 #endif
6790 }
6792 }
6795 );
6801 }
6802 }
6804 /* Done. */
6809 /* Jump here if malloc fails */
6810 whereBeginError:
6814 }
6815 #ifdef WHERETRACE_ENABLED
6816 /* Prevent harmless compiler warnings about debugging routines
6817 ** being declared but never used */
6821 }
6823 /*
6824 ** Part of sqlite3WhereEnd() will rewrite opcodes to reference the
6825 ** index rather than the main table. In SQLITE_DEBUG mode, we want
6826 ** to trace those changes if PRAGMA vdbe_addoptrace=on. This routine
6827 ** does that.
6828 */
6829 #ifndef SQLITE_DEBUG
6831 #else
6832 # define OpcodeRewriteTrace(D,K,P) sqlite3WhereOpcodeRewriteTrace(D,K,P)
6836 VdbeOp *pOp
6837 ){
6840 }
6841 #endif
6843 #ifdef SQLITE_DEBUG
6844 /*
6845 ** Return true if cursor iCur is opened by instruction k of the
6846 ** bytecode. Used inside of assert() only.
6847 */
6858 }
6860 }
6863 /*
6864 ** Generate the end of the WHERE loop. See comments on
6865 ** sqlite3WhereBegin() for additional information.
6866 */
6878 /* Generate loop termination code.
6879 */
6885 /* Terminate the subroutine that forms the interior of the loop of
6886 ** the RIGHT JOIN table */
6893 nRJ++;
6894 }
6897 #ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT
6907 ){
6912 }
6919 }
6921 /* The common case: Advance to the next row */
6933 }
6934 #ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT
6936 #endif
6939 }
6954 /* For LEFT JOIN queries, cursor pIn->iCur may not have been
6955 ** opened yet. This occurs for WHERE clauses such as
6956 ** "a = ? AND b IN (...)", where the index is on (a, b). If
6957 ** the RHS of the (a=?) is NULL, then the "b IN (...)" may
6958 ** never have been coded, but the body of the loop run to
6959 ** return the null-row. So, if the cursor is not open yet,
6960 ** jump over the OP_Next or OP_Prev instruction about to
6961 ** be coded. */
6965 }
6971 /* Retarget the OP_IsNull against the left operand of IN so
6972 ** it jumps past the OP_IfNoHope. This is because the
6973 ** OP_IsNull also bypasses the OP_Affinity opcode that is
6974 ** required by OP_IfNoHope. */
6976 }
6977 }
6982 }
6984 }
6985 }
6990 }
6996 }
6997 #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
7002 }
7003 #endif
7017 }
7019 }
7022 ){
7028 }
7030 }
7035 }
7037 }
7040 }
7052 /* Do RIGHT JOIN processing. Generate code that will output the
7053 ** unmatched rows of the right operand of the RIGHT JOIN with
7054 ** all of the columns of the left operand set to NULL.
7055 */
7059 }
7061 /* For a co-routine, change all OP_Column references to the table of
7062 ** the co-routine into OP_Copy of result contained in a register.
7063 ** OP_Rowid becomes OP_Null.
7064 */
7071 }
7073 /* If this scan uses an index, make VDBE code substitutions to read data
7074 ** from the index instead of from the table where possible. In some cases
7075 ** this optimization prevents the table from ever being read, which can
7076 ** yield a significant performance boost.
7077 **
7078 ** Calls to the code generator in between sqlite3WhereBegin and
7079 ** sqlite3WhereEnd will have created code that references the table
7080 ** directly. This loop scans all that code looking for opcodes
7081 ** that reference the table and converts them into opcodes that
7082 ** reference the index.
7083 */
7088 }
7091 ){
7096 }
7101 #ifdef WHERETRACE_ENABLED
7106 }
7107 #endif
7110 }
7112 }
7113 }
7115 #ifdef SQLITE_DEBUG
7119 }
7120 /* Proof that the "+1" on the k value above is safe */
7125 #endif
7131 /* no-op */
7133 #ifdef SQLITE_ENABLE_OFFSET_SQL_FUNC
7135 #endif
7136 ){
7139 #ifdef SQLITE_ENABLE_OFFSET_SQL_FUNC
7141 /* Do not need to translate the column number */
7143 #endif
7151 }
7158 /* Unable to translate the table reference into an index
7159 ** reference. Verify that this is harmless - that the
7160 ** table being referenced really is open.
7161 */
7162 #ifdef SQLITE_ENABLE_OFFSET_SQL_FUNC
7166 );
7167 #else
7170 );
7171 #endif
7172 }
7180 }
7181 #ifdef SQLITE_DEBUG
7182 k++;
7183 #endif
7185 #ifdef SQLITE_DEBUG
7187 #endif
7188 }
7189 }
7191 /* The "break" point is here, just past the end of the outer loop.
7192 ** Set it.
7193 */
7196 /* Final cleanup
7197 */
7202 }