| blob | 6c2c64d18ecc2f13ccaf5caabbce5aabddc5ca16 |
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 ** Advance to the next WhereTerm that matches according to the criteria
307 ** established when the pScan object was initialized by whereScanInit().
308 ** Return NULL if there are no more matching WhereTerms.
309 */
334 ){
338 ){
344 }
345 }
350 }
351 }
353 /* Verify the affinity and collating sequence match */
360 }
366 }
367 }
373 ){
376 }
379 #ifdef WHERETRACE_ENABLED
387 }
389 }
390 #endif
392 }
393 }
394 }
402 }
404 }
406 /*
407 ** This is whereScanInit() for the case of an index on an expression.
408 ** It is factored out into a separate tail-recursion subroutine so that
409 ** the normal whereScanInit() routine, which is a high-runner, does not
410 ** need to push registers onto the stack as part of its prologue.
411 */
415 }
417 /*
418 ** Initialize a WHERE clause scanner object. Return a pointer to the
419 ** first match. Return NULL if there are no matches.
420 **
421 ** The scanner will be searching the WHERE clause pWC. It will look
422 ** for terms of the form "X <op> <expr>" where X is column iColumn of table
423 ** iCur. Or if pIdx!=0 then X is column iColumn of index pIdx. pIdx
424 ** must be one of the indexes of table iCur.
425 **
426 ** The <op> must be one of the operators described by opMask.
427 **
428 ** If the search is for X and the WHERE clause contains terms of the
429 ** form X=Y then this routine might also return terms of the form
430 ** "Y <op> <expr>". The number of levels of transitivity is limited,
431 ** but is enough to handle most commonly occurring SQL statements.
432 **
433 ** If X is not the INTEGER PRIMARY KEY then X must be compatible with
434 ** index pIdx.
435 */
443 ){
467 }
470 }
473 }
475 /*
476 ** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
477 ** where X is a reference to the iColumn of table iCur or of index pIdx
478 ** if pIdx!=0 and <op> is one of the WO_xx operator codes specified by
479 ** the op parameter. Return a pointer to the term. Return 0 if not found.
480 **
481 ** If pIdx!=0 then it must be one of the indexes of table iCur.
482 ** Search for terms matching the iColumn-th column of pIdx
483 ** rather than the iColumn-th column of table iCur.
484 **
485 ** The term returned might by Y=<expr> if there is another constraint in
486 ** the WHERE clause that specifies that X=Y. Any such constraints will be
487 ** identified by the WO_EQUIV bit in the pTerm->eOperator field. The
488 ** aiCur[]/iaColumn[] arrays hold X and all its equivalents. There are 11
489 ** slots in aiCur[]/aiColumn[] so that means we can look for X plus up to 10
490 ** other equivalent values. Hence a search for X will return <expr> if X=A1
491 ** and A1=A2 and A2=A3 and ... and A9=A10 and A10=<expr>.
492 **
493 ** If there are multiple terms in the WHERE clause of the form "X <op> <expr>"
494 ** then try for the one with no dependencies on <expr> - in other words where
495 ** <expr> is a constant expression of some kind. Only return entries of
496 ** the form "X <op> Y" where Y is a column in another table if no terms of
497 ** the form "X <op> <const-expr>" exist. If no terms with a constant RHS
498 ** exist, try to return a term that does not use WO_EQUIV.
499 */
507 ){
510 WhereScan scan;
519 }
521 }
523 }
525 }
527 /*
528 ** This function searches pList for an entry that matches the iCol-th column
529 ** of index pIdx.
530 **
531 ** If such an expression is found, its index in pList->a[] is returned. If
532 ** no expression is found, -1 is returned.
533 */
540 ){
550 ){
554 }
555 }
556 }
559 }
561 /*
562 ** Return TRUE if the iCol-th column of index pIdx is NOT NULL
563 */
577 }
578 }
580 /*
581 ** Return true if the DISTINCT expression-list passed as the third argument
582 ** is redundant.
583 **
584 ** A DISTINCT list is redundant if any subset of the columns in the
585 ** DISTINCT list are collectively unique and individually non-null.
586 */
592 ){
598 /* If there is more than one table or sub-select in the FROM clause of
599 ** this query, then it will not be possible to show that the DISTINCT
600 ** clause is redundant. */
605 /* If any of the expressions is an IPK column on table iBase, then return
606 ** true. Note: The (p->iTable==iBase) part of this test may be false if the
607 ** current SELECT is a correlated sub-query.
608 */
614 }
616 /* Loop through all indices on the table, checking each to see if it makes
617 ** the DISTINCT qualifier redundant. It does so if:
618 **
619 ** 1. The index is itself UNIQUE, and
620 **
621 ** 2. All of the columns in the index are either part of the pDistinct
622 ** list, or else the WHERE clause contains a term of the form "col=X",
623 ** where X is a constant value. The collation sequences of the
624 ** comparison and select-list expressions must match those of the index.
625 **
626 ** 3. All of those index columns for which the WHERE clause does not
627 ** contain a "col=X" term are subject to a NOT NULL constraint.
628 */
636 }
637 }
639 /* This index implies that the DISTINCT qualifier is redundant. */
641 }
642 }
645 }
648 /*
649 ** Estimate the logarithm of the input value to base 2.
650 */
653 }
655 /*
656 ** Convert OP_Column opcodes to OP_Copy in previously generated code.
657 **
658 ** This routine runs over generated VDBE code and translates OP_Column
659 ** opcodes into OP_Copy when the table is being accessed via co-routine
660 ** instead of via table lookup.
661 **
662 ** If the iAutoidxCur is not zero, then any OP_Rowid instructions on
663 ** cursor iTabCur are transformed into OP_Sequence opcode for the
664 ** iAutoidxCur cursor, in order to generate unique rowids for the
665 ** automatic index being generated.
666 */
673 ){
689 #ifdef SQLITE_ALLOW_ROWID_IN_VIEW
693 }
694 #endif
695 }
696 }
697 }
699 /*
700 ** Two routines for printing the content of an sqlite3_index_info
701 ** structure. Used for testing and debugging only. If neither
702 ** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines
703 ** are no-ops.
704 */
705 #if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(WHERETRACE_ENABLED)
712 i,
718 }
721 i,
724 }
725 }
731 i,
734 }
740 }
741 #else
742 #define whereTraceIndexInfoInputs(A)
743 #define whereTraceIndexInfoOutputs(A)
744 #endif
746 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
747 /*
748 ** Return TRUE if the WHERE clause term pTerm is of a form where it
749 ** could be used with an index to access pSrc, assuming an appropriate
750 ** index existed.
751 */
756 ){
768 ){
770 }
771 }
779 }
780 #endif
783 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
784 /*
785 ** Generate code to construct the Index object for an automatic index
786 ** and to set up the WhereLevel object pLevel so that the code generator
787 ** makes use of the automatic index.
788 */
795 ){
820 /* Generate code to skip over the creation and initialization of the
821 ** transient index on 2nd and subsequent iterations of the loop. */
826 /* Count the number of columns that will be added to the index
827 ** and used to match WHERE clause constraints */
835 /* Make the automatic index a partial index if there are terms in the
836 ** WHERE clause (or the ON clause of a LEFT join) that constrain which
837 ** rows of the target table (pSrc) that can be used. */
840 ){
843 }
846 Bitmask cMask;
857 }
861 }
864 }
865 }
866 }
872 /* Count the number of additional columns needed to create a
873 ** covering index. A "covering index" is an index that contains all
874 ** columns that are needed by the query. With a covering index, the
875 ** original table never needs to be accessed. Automatic indices must
876 ** be a covering index because the index will not be updated if the
877 ** original table changes and the index and table cannot both be used
878 ** if they go out of sync.
879 */
886 }
889 }
891 /* Construct the Index object to describe this index */
902 Bitmask cMask;
915 n++;
916 }
917 }
918 }
921 /* Add additional columns needed to make the automatic index into
922 ** a covering index */
927 n++;
928 }
929 }
934 n++;
935 }
936 }
941 /* Create the automatic index */
950 }
952 /* Fill the automatic index with content */
963 }
968 }
972 );
976 }
991 }
995 /* Jump here when skipping the initialization */
998 end_auto_index_create:
1000 }
1003 /*
1004 ** Generate bytecode that will initialize a Bloom filter that is appropriate
1005 ** for pLevel.
1006 **
1007 ** If there are inner loops within pLevel that have the WHERE_BLOOMFILTER
1008 ** flag set, initialize a Bloomfilter for them as well. Except don't do
1009 ** this recursive initialization if the SQLITE_BloomPulldown optimization has
1010 ** been turned off.
1011 **
1012 ** When the Bloom filter is initialized, the WHERE_BLOOMFILTER flag is cleared
1013 ** from the loop, but the regFilter value is set to a register that implements
1014 ** the Bloom filter. When regFilter is positive, the
1015 ** sqlite3WhereCodeOneLoopStart() will generate code to test the Bloom filter
1016 ** and skip the subsequence B-Tree seek if the Bloom filter indicates that
1017 ** no matching rows exist.
1018 **
1019 ** This routine may only be called if it has previously been determined that
1020 ** the loop would benefit from a Bloom filter, and the WHERE_BLOOMFILTER bit
1021 ** is set.
1022 */
1027 Bitmask notReady /* Loops that are not ready */
1028 ){
1047 u64 sz;
1053 /* The Bloom filter is a Blob held in a register. Initialize it
1054 ** to zero-filled blob of at least 80K bits, but maybe more if the
1055 ** estimated size of the table is larger. We could actually
1056 ** measure the size of the table at run-time using OP_Count with
1057 ** P3==1 and use that value to initialize the blob. But that makes
1058 ** testing complicated. By basing the blob size on the value in the
1059 ** sqlite_stat1 table, testing is much easier.
1060 */
1070 }
1079 ){
1081 }
1082 }
1097 }
1100 }
1116 ==WHERE_BLOOMFILTER
1117 ){
1118 /* This is a candidate for bloom-filter pull-down (early evaluation).
1119 ** The test that WHERE_COLUMN_IN is omitted is important, as we are
1120 ** not able to do early evaluation of bloom filters that make use of
1121 ** the IN operator */
1123 }
1124 }
1127 }
1130 #ifndef SQLITE_OMIT_VIRTUALTABLE
1131 /*
1132 ** Allocate and populate an sqlite3_index_info structure. It is the
1133 ** responsibility of the caller to eventually release the structure
1134 ** by passing the pointer returned by this function to freeIndexInfo().
1135 */
1142 ){
1163 /* Find all WHERE clause constraints referring to this virtual table.
1164 ** Mark each term with the TERM_OK flag. Set nTerm to the number of
1165 ** terms found.
1166 */
1183 /* tag-20191211-002: WHERE-clause constraints are not useful to the
1184 ** right-hand table of a LEFT JOIN nor to the either table of a
1185 ** RIGHT JOIN. See tag-20191211-001 for the
1186 ** equivalent restriction for ordinary tables. */
1195 ){
1197 }
1198 }
1199 nTerm++;
1201 }
1203 /* If the ORDER BY clause contains only columns in the current
1204 ** virtual table then allocate space for the aOrderBy part of
1205 ** the sqlite3_index_info structure.
1206 */
1214 /* Skip over constant terms in the ORDER BY clause */
1217 }
1219 /* Virtual tables are unable to deal with NULLS FIRST */
1222 /* First case - a direct column references without a COLLATE operator */
1226 }
1228 /* 2nd case - a column reference with a COLLATE operator. Only match
1229 ** of the COLLATE operator matches the collation of the column. */
1233 ){
1243 }
1245 /* No matches cause a break out of the loop */
1247 }
1254 }
1255 }
1256 }
1258 /* Allocate the sqlite3_index_info structure
1259 */
1267 }
1280 u16 op;
1288 }
1290 }
1298 }
1301 /* The direct assignment in the previous line is possible only because
1302 ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical. The
1303 ** following asserts verify this fact. */
1313 ){
1318 }
1319 }
1321 j++;
1322 }
1333 j++;
1334 }
1339 }
1341 /*
1342 ** Free an sqlite3_index_info structure allocated by allocateIndexInfo()
1343 ** and possibly modified by xBestIndex methods.
1344 */
1355 }
1357 }
1359 /*
1360 ** The table object reference passed as the second argument to this function
1361 ** must represent a virtual table. This function invokes the xBestIndex()
1362 ** method of the virtual table with the sqlite3_index_info object that
1363 ** comes in as the 3rd argument to this function.
1364 **
1365 ** If an error occurs, pParse is populated with an error message and an
1366 ** appropriate error code is returned. A return of SQLITE_CONSTRAINT from
1367 ** xBestIndex is not considered an error. SQLITE_CONSTRAINT indicates that
1368 ** the current configuration of "unusable" flags in sqlite3_index_info can
1369 ** not result in a valid plan.
1370 **
1371 ** Whether or not an error is returned, it is the responsibility of the
1372 ** caller to eventually free p->idxStr if p->needToFreeIdxStr indicates
1373 ** that this is required.
1374 */
1392 }
1393 }
1397 }
1400 #ifdef SQLITE_ENABLE_STAT4
1401 /*
1402 ** Estimate the location of a particular key among all keys in an
1403 ** index. Store the results in aStat as follows:
1404 **
1405 ** aStat[0] Est. number of rows less than pRec
1406 ** aStat[1] Est. number of rows equal to pRec
1407 **
1408 ** Return the index of the sample that is the smallest sample that
1409 ** is greater than or equal to pRec. Note that this index is not an index
1410 ** into the aSample[] array - it is an index into a virtual set of samples
1411 ** based on the contents of aSample[] and the number of fields in record
1412 ** pRec.
1413 */
1420 ){
1431 #ifndef SQLITE_DEBUG
1433 #endif
1438 /* Do a binary search to find the first sample greater than or equal
1439 ** to pRec. If pRec contains a single field, the set of samples to search
1440 ** is simply the aSample[] array. If the samples in aSample[] contain more
1441 ** than one fields, all fields following the first are ignored.
1442 **
1443 ** If pRec contains N fields, where N is more than one, then as well as the
1444 ** samples in aSample[] (truncated to N fields), the search also has to
1445 ** consider prefixes of those samples. For example, if the set of samples
1446 ** in aSample is:
1447 **
1448 ** aSample[0] = (a, 5)
1449 ** aSample[1] = (a, 10)
1450 ** aSample[2] = (b, 5)
1451 ** aSample[3] = (c, 100)
1452 ** aSample[4] = (c, 105)
1453 **
1454 ** Then the search space should ideally be the samples above and the
1455 ** unique prefixes [a], [b] and [c]. But since that is hard to organize,
1456 ** the code actually searches this set:
1457 **
1458 ** 0: (a)
1459 ** 1: (a, 5)
1460 ** 2: (a, 10)
1461 ** 3: (a, 10)
1462 ** 4: (b)
1463 ** 5: (b, 5)
1464 ** 6: (c)
1465 ** 7: (c, 100)
1466 ** 8: (c, 105)
1467 ** 9: (c, 105)
1468 **
1469 ** For each sample in the aSample[] array, N samples are present in the
1470 ** effective sample array. In the above, samples 0 and 1 are based on
1471 ** sample aSample[0]. Samples 2 and 3 on aSample[1] etc.
1472 **
1473 ** Often, sample i of each block of N effective samples has (i+1) fields.
1474 ** Except, each sample may be extended to ensure that it is greater than or
1475 ** equal to the previous sample in the array. For example, in the above,
1476 ** sample 2 is the first sample of a block of N samples, so at first it
1477 ** appears that it should be 1 field in size. However, that would make it
1478 ** smaller than sample 1, so the binary search would not work. As a result,
1479 ** it is extended to two fields. The duplicates that this creates do not
1480 ** cause any problems.
1481 */
1492 /* The proposed effective sample is a prefix of sample aSample[iSamp].
1493 ** Specifically, the shortest prefix of at least (1 + iTest%nField)
1494 ** fields that is greater than the previous effective sample. */
1497 }
1500 }
1514 }
1518 #ifdef SQLITE_DEBUG
1519 /* The following assert statements check that the binary search code
1520 ** above found the right answer. This block serves no purpose other
1521 ** than to invoke the asserts. */
1524 /* If (res==0) is true, then pRec must be equal to sample i. */
1530 );
1532 /* Unless i==pIdx->nSample, indicating that pRec is larger than
1533 ** all samples in the aSample[] array, pRec must be smaller than the
1534 ** (iCol+1) field prefix of sample i. */
1541 /* if i==0 and iCol==0, then record pRec is smaller than all samples
1542 ** in the aSample[] array. Otherwise, if (iCol>0) then pRec must
1543 ** be greater than or equal to the (iCol) field prefix of sample i.
1544 ** If (i>0), then pRec must also be greater than sample (i-1). */
1549 }
1554 }
1555 }
1556 }
1560 /* Record pRec is equal to sample i */
1565 /* At this point, the (iCol+1) field prefix of aSample[i] is the first
1566 ** sample that is greater than pRec. Or, if i==pIdx->nSample then pRec
1567 ** is larger than all samples in the array. */
1573 }
1579 }
1584 }
1587 }
1589 /* Restore the pRec->nField value before returning. */
1592 }
1595 /*
1596 ** If it is not NULL, pTerm is a term that provides an upper or lower
1597 ** bound on a range scan. Without considering pTerm, it is estimated
1598 ** that the scan will visit nNew rows. This function returns the number
1599 ** estimated to be visited after taking pTerm into account.
1600 **
1601 ** If the user explicitly specified a likelihood() value for this term,
1602 ** then the return value is the likelihood multiplied by the number of
1603 ** input rows. Otherwise, this function assumes that an "IS NOT NULL" term
1604 ** has a likelihood of 0.50, and any other term a likelihood of 0.25.
1605 */
1613 }
1614 }
1616 }
1619 #ifdef SQLITE_ENABLE_STAT4
1620 /*
1621 ** Return the affinity for a single column of an index.
1622 */
1627 }
1630 }
1631 #endif
1634 #ifdef SQLITE_ENABLE_STAT4
1635 /*
1636 ** This function is called to estimate the number of rows visited by a
1637 ** range-scan on a skip-scan index. For example:
1638 **
1639 ** CREATE INDEX i1 ON t1(a, b, c);
1640 ** SELECT * FROM t1 WHERE a=? AND c BETWEEN ? AND ?;
1641 **
1642 ** Value pLoop->nOut is currently set to the estimated number of rows
1643 ** visited for scanning (a=? AND b=?). This function reduces that estimate
1644 ** by some factor to account for the (c BETWEEN ? AND ?) expression based
1645 ** on the stat4 data for the index. this scan will be peformed multiple
1646 ** times (once for each (a,b) combination that matches a=?) is dealt with
1647 ** by the caller.
1648 **
1649 ** It does this by scanning through all stat4 samples, comparing values
1650 ** extracted from pLower and pUpper with the corresponding column in each
1651 ** sample. If L and U are the number of samples found to be less than or
1652 ** equal to the values extracted from pLower and pUpper respectively, and
1653 ** N is the total number of samples, the pLoop->nOut value is adjusted
1654 ** as follows:
1655 **
1656 ** nOut = nOut * ( min(U - L, 1) / N )
1657 **
1658 ** If pLower is NULL, or a value cannot be extracted from the term, L is
1659 ** set to zero. If pUpper is NULL, or a value cannot be extracted from it,
1660 ** U is set to N.
1661 **
1662 ** Normally, this function sets *pbDone to 1 before returning. However,
1663 ** if no value can be extracted from either pLower or pUpper (and so the
1664 ** estimate of the number of rows delivered remains unchanged), *pbDone
1665 ** is left as is.
1666 **
1667 ** If an error occurs, an SQLite error code is returned. Otherwise,
1668 ** SQLITE_OK.
1669 */
1676 ){
1694 }
1698 }
1708 }
1712 }
1713 }
1717 /* If there is both an upper and lower bound specified, and the
1718 ** comparisons indicate that they are close together, use the fallback
1719 ** method (assume that the scan visits 1/64 of the rows) for estimating
1720 ** the number of rows visited. Otherwise, estimate the number of rows
1721 ** using the method described in the header comment for this function. */
1728 }
1732 }
1739 }
1742 /*
1743 ** This function is used to estimate the number of rows that will be visited
1744 ** by scanning an index for a range of values. The range may have an upper
1745 ** bound, a lower bound, or both. The WHERE clause terms that set the upper
1746 ** and lower bounds are represented by pLower and pUpper respectively. For
1747 ** example, assuming that index p is on t1(a):
1748 **
1749 ** ... FROM t1 WHERE a > ? AND a < ? ...
1750 ** |_____| |_____|
1751 ** | |
1752 ** pLower pUpper
1753 **
1754 ** If either of the upper or lower bound is not present, then NULL is passed in
1755 ** place of the corresponding WhereTerm.
1756 **
1757 ** The value in (pBuilder->pNew->u.btree.nEq) is the number of the index
1758 ** column subject to the range constraint. Or, equivalently, the number of
1759 ** equality constraints optimized by the proposed index scan. For example,
1760 ** assuming index p is on t1(a, b), and the SQL query is:
1761 **
1762 ** ... FROM t1 WHERE a = ? AND b > ? AND b < ? ...
1763 **
1764 ** then nEq is set to 1 (as the range restricted column, b, is the second
1765 ** left-most column of the index). Or, if the query is:
1766 **
1767 ** ... FROM t1 WHERE a > ? AND a < ? ...
1768 **
1769 ** then nEq is set to 0.
1770 **
1771 ** When this function is called, *pnOut is set to the sqlite3LogEst() of the
1772 ** number of rows that the index scan is expected to visit without
1773 ** considering the range constraints. If nEq is 0, then *pnOut is the number of
1774 ** rows in the index. Assuming no error occurs, *pnOut is adjusted (reduced)
1775 ** to account for the range constraints pLower and pUpper.
1776 **
1777 ** In the absence of sqlite_stat4 ANALYZE data, or if such data cannot be
1778 ** used, a single range inequality reduces the search space by a factor of 4.
1779 ** and a pair of constraints (x>? AND x<?) reduces the expected number of
1780 ** rows visited by a factor of 64.
1781 */
1788 ){
1791 LogEst nNew;
1793 #ifdef SQLITE_ENABLE_STAT4
1799 ){
1806 /* Variable iLower will be set to the estimate of the number of rows in
1807 ** the index that are less than the lower bound of the range query. The
1808 ** lower bound being the concatenation of $P and $L, where $P is the
1809 ** key-prefix formed by the nEq values matched against the nEq left-most
1810 ** columns of the index, and $L is the value in pLower.
1811 **
1812 ** Or, if pLower is NULL or $L cannot be extracted from it (because it
1813 ** is not a simple variable or literal value), the lower bound of the
1814 ** range is $P. Due to a quirk in the way whereKeyStats() works, even
1815 ** if $L is available, whereKeyStats() is called for both ($P) and
1816 ** ($P:$L) and the larger of the two returned values is used.
1817 **
1818 ** Similarly, iUpper is to be set to the estimate of the number of rows
1819 ** less than the upper bound of the range query. Where the upper bound
1820 ** is either ($P) or ($P:$U). Again, even if $U is available, both values
1821 ** of iUpper are requested of whereKeyStats() and the smaller used.
1822 **
1823 ** The number of rows between the two bounds is then just iUpper-iLower.
1824 */
1833 }
1834 /* Determine iLower and iUpper using ($P) only. */
1839 /* Note: this call could be optimized away - since the same values must
1840 ** have been requested when testing key $P in whereEqualScanEst(). */
1844 }
1850 /* The roles of pLower and pUpper are swapped for a DESC index */
1853 }
1855 /* If possible, improve on the iLower estimate using ($P:$L). */
1861 tRowcnt iNew;
1867 nOut--;
1869 }
1870 }
1872 /* If possible, improve on the iUpper estimate using ($P:$U). */
1878 tRowcnt iNew;
1884 nOut--;
1886 }
1887 }
1893 /* TUNING: If both iUpper and iLower are derived from the same
1894 ** sample, then assume they are 4x more selective. This brings
1895 ** the estimated selectivity more in line with what it would be
1896 ** if estimated without the use of STAT4 tables. */
1900 }
1903 }
1906 }
1911 }
1912 }
1913 #else
1917 #endif
1922 /* TUNING: If there is both an upper and lower limit and neither limit
1923 ** has an application-defined likelihood(), assume the range is
1924 ** reduced by an additional 75%. This means that, by default, an open-ended
1925 ** range query (e.g. col > ?) is assumed to match 1/4 of the rows in the
1926 ** index. While a closed range (e.g. col BETWEEN ? AND ?) is estimated to
1927 ** match 1/64 of the index. */
1930 }
1935 #if defined(WHERETRACE_ENABLED)
1939 }
1940 #endif
1943 }
1945 #ifdef SQLITE_ENABLE_STAT4
1946 /*
1947 ** Estimate the number of rows that will be returned based on
1948 ** an equality constraint x=VALUE and where that VALUE occurs in
1949 ** the histogram data. This only works when x is the left-most
1950 ** column of an index and sqlite_stat4 histogram data is available
1951 ** for that index. When pExpr==NULL that means the constraint is
1952 ** "x IS NULL" instead of "x=VALUE".
1953 **
1954 ** Write the estimated row count into *pnRow and return SQLITE_OK.
1955 ** If unable to make an estimate, leave *pnRow unchanged and return
1956 ** non-zero.
1957 **
1958 ** This routine can fail if it is unable to load a collating sequence
1959 ** required for string comparison, or if unable to allocate memory
1960 ** for a UTF conversion required for comparison. The error is stored
1961 ** in the pParse structure.
1962 */
1968 ){
1982 /* If values are not available for all fields of the index to the left
1983 ** of this one, no estimate can be made. Return SQLITE_NOTFOUND. */
1986 }
1988 /* This is an optimization only. The call to sqlite3Stat4ProbeSetValue()
1989 ** below would return the same value. */
1993 }
2007 }
2010 #ifdef SQLITE_ENABLE_STAT4
2011 /*
2012 ** Estimate the number of rows that will be returned based on
2013 ** an IN constraint where the right-hand side of the IN operator
2014 ** is a list of values. Example:
2015 **
2016 ** WHERE x IN (1,2,3,4)
2017 **
2018 ** Write the estimated row count into *pnRow and return SQLITE_OK.
2019 ** If unable to make an estimate, leave *pnRow unchanged and return
2020 ** non-zero.
2021 **
2022 ** This routine can fail if it is unable to load a collating sequence
2023 ** required for string comparison, or if unable to allocate memory
2024 ** for a UTF conversion required for comparison. The error is stored
2025 ** in the pParse structure.
2026 */
2032 ){
2047 }
2053 }
2056 }
2060 #ifdef WHERETRACE_ENABLED
2061 /*
2062 ** Print the content of a WhereTerm object
2063 */
2084 }
2088 /* The 0x10000 .wheretrace flag causes extra information to be
2089 ** shown about each Term */
2093 }
2096 }
2099 }
2102 }
2103 }
2104 #endif
2106 #ifdef WHERETRACE_ENABLED
2107 /*
2108 ** Show the complete content of a WhereClause
2109 */
2114 }
2115 }
2116 #endif
2118 #ifdef WHERETRACE_ENABLED
2119 /*
2120 ** Print a WhereLoop object for debugging purposes
2121 */
2139 }
2143 }
2151 }
2154 }
2159 }
2165 }
2166 }
2167 }
2168 #endif
2170 /*
2171 ** Convert bulk memory into a valid WhereLoop that can be passed
2172 ** to whereLoopClear harmlessly.
2173 */
2179 }
2181 /*
2182 ** Clear the WhereLoop.u union. Leave WhereLoop.pLTerm intact.
2183 */
2194 }
2195 }
2196 }
2198 /*
2199 ** Deallocate internal memory used by a WhereLoop object
2200 */
2205 }
2207 /*
2208 ** Increase the memory allocation for pLoop->aLTerm[] to be at least n.
2209 */
2221 }
2223 /*
2224 ** Transfer content from the second pLoop into the first.
2225 */
2231 }
2238 }
2240 }
2242 /*
2243 ** Delete a WhereLoop object
2244 */
2248 }
2250 /*
2251 ** Free a WhereInfo structure
2252 */
2260 }
2266 }
2268 }
2270 /* Undo all Expr node modifications
2271 */
2278 }
2279 }
2281 /*
2282 ** Return TRUE if all of the following are true:
2283 **
2284 ** (1) X has the same or lower cost, or returns the same or fewer rows,
2285 ** than Y.
2286 ** (2) X uses fewer WHERE clause terms than Y
2287 ** (3) Every WHERE clause term used by X is also used by Y
2288 ** (4) X skips at least as many columns as Y
2289 ** (5) If X is a covering index, than Y is too
2290 **
2291 ** Conditions (2) and (3) mean that X is a "proper subset" of Y.
2292 ** If X is a proper subset of Y then Y is a better choice and ought
2293 ** to have a lower cost. This routine returns TRUE when that cost
2294 ** relationship is inverted and needs to be adjusted. Constraint (4)
2295 ** was added because if X uses skip-scan less than Y it still might
2296 ** deserve a lower cost even if it is a proper subset of Y. Constraint (5)
2297 ** was added because a covering index probably deserves to have a lower cost
2298 ** than a non-covering index even if it is a proper subset.
2299 */
2303 ){
2307 }
2314 }
2316 }
2320 }
2322 }
2324 /*
2325 ** Try to adjust the cost and number of output rows of WhereLoop pTemplate
2326 ** upwards or downwards so that:
2327 **
2328 ** (1) pTemplate costs less than any other WhereLoops that are a proper
2329 ** subset of pTemplate
2330 **
2331 ** (2) pTemplate costs more than any other WhereLoops for which pTemplate
2332 ** is a proper subset.
2333 **
2334 ** To say "WhereLoop X is a proper subset of Y" means that X uses fewer
2335 ** WHERE clause terms than Y and that every WHERE clause term used by X is
2336 ** also used by Y.
2337 */
2344 /* Adjust pTemplate cost downward so that it is cheaper than its
2345 ** subset p. */
2353 /* Adjust pTemplate cost upward so that it is costlier than p since
2354 ** pTemplate is a proper subset of p */
2361 }
2362 }
2363 }
2365 /*
2366 ** Search the list of WhereLoops in *ppPrev looking for one that can be
2367 ** replaced by pTemplate.
2368 **
2369 ** Return NULL if pTemplate does not belong on the WhereLoop list.
2370 ** In other words if pTemplate ought to be dropped from further consideration.
2371 **
2372 ** If pX is a WhereLoop that pTemplate can replace, then return the
2373 ** link that points to pX.
2374 **
2375 ** If pTemplate cannot replace any existing element of the list but needs
2376 ** to be added to the list as a new entry, then return a pointer to the
2377 ** tail of the list.
2378 */
2382 ){
2386 /* If either the iTab or iSortIdx values for two WhereLoop are different
2387 ** then those WhereLoops need to be considered separately. Neither is
2388 ** a candidate to replace the other. */
2390 }
2391 /* In the current implementation, the rSetup value is either zero
2392 ** or the cost of building an automatic index (NlogN) and the NlogN
2393 ** is the same for compatible WhereLoops. */
2397 /* whereLoopAddBtree() always generates and inserts the automatic index
2398 ** case first. Hence compatible candidate WhereLoops never have a larger
2399 ** rSetup. Call this SETUP-INVARIANT */
2402 /* Any loop using an appliation-defined index (or PRIMARY KEY or
2403 ** UNIQUE constraint) with one or more == constraints is better
2404 ** than an automatic index. Unless it is a skip-scan. */
2410 ){
2412 }
2414 /* If existing WhereLoop p is better than pTemplate, pTemplate can be
2415 ** discarded. WhereLoop p is better if:
2416 ** (1) p has no more dependencies than pTemplate, and
2417 ** (2) p has an equal or lower cost than pTemplate
2418 */
2423 ){
2425 }
2427 /* If pTemplate is always better than p, then cause p to be overwritten
2428 ** with pTemplate. pTemplate is better than p if:
2429 ** (1) pTemplate has no more dependences than p, and
2430 ** (2) pTemplate has an equal or lower cost than p.
2431 */
2435 ){
2438 }
2439 }
2441 }
2443 /*
2444 ** Insert or replace a WhereLoop entry using the template supplied.
2445 **
2446 ** An existing WhereLoop entry might be overwritten if the new template
2447 ** is better and has fewer dependencies. Or the template will be ignored
2448 ** and no insert will occur if an existing WhereLoop is faster and has
2449 ** fewer dependencies than the template. Otherwise a new WhereLoop is
2450 ** added based on the template.
2451 **
2452 ** If pBuilder->pOrSet is not NULL then we care about only the
2453 ** prerequisites and rRun and nOut costs of the N best loops. That
2454 ** information is gathered in the pBuilder->pOrSet object. This special
2455 ** processing mode is used only for OR clause processing.
2456 **
2457 ** When accumulating multiple loops (when pBuilder->pOrSet is NULL) we
2458 ** still might overwrite similar loops with the new template if the
2459 ** new template is better. Loops may be overwritten if the following
2460 ** conditions are met:
2461 **
2462 ** (1) They have the same iTab.
2463 ** (2) They have the same iSortIdx.
2464 ** (3) The template has same or fewer dependencies than the current loop
2465 ** (4) The template has the same or lower cost than the current loop
2466 */
2473 /* Stop the search once we hit the query planner search limit */
2478 }
2483 /* If pBuilder->pOrSet is defined, then only keep track of the costs
2484 ** and prereqs.
2485 */
2488 #if WHERETRACE_ENABLED
2491 #endif
2498 }
2499 #endif
2500 }
2502 }
2504 /* Look for an existing WhereLoop to replace with pTemplate
2505 */
2509 /* There already exists a WhereLoop on the list that is better
2510 ** than pTemplate, so just ignore pTemplate */
2515 }
2516 #endif
2520 }
2522 /* If we reach this point it means that either p[] should be overwritten
2523 ** with pTemplate[] if p[] exists, or if p==NULL then allocate a new
2524 ** WhereLoop and insert it.
2525 */
2534 }
2536 }
2537 #endif
2539 /* Allocate a new WhereLoop to add to the end of the list */
2545 /* We will be overwriting WhereLoop p[]. But before we do, first
2546 ** go through the rest of the list and delete any other entries besides
2547 ** p[] that are also supplated by pTemplate */
2560 }
2561 #endif
2563 }
2564 }
2570 }
2571 }
2573 }
2575 /*
2576 ** Adjust the WhereLoop.nOut value downward to account for terms of the
2577 ** WHERE clause that reference the loop but which are not used by an
2578 ** index.
2579 *
2580 ** For every WHERE clause term that is not used by the index
2581 ** and which has a truth probability assigned by one of the likelihood(),
2582 ** likely(), or unlikely() SQL functions, reduce the estimated number
2583 ** of output rows by the probability specified.
2584 **
2585 ** TUNING: For every WHERE clause term that is not used by the index
2586 ** and which does not have an assigned truth probability, heuristics
2587 ** described below are used to try to estimate the truth probability.
2588 ** TODO --> Perhaps this is something that could be improved by better
2589 ** table statistics.
2590 **
2591 ** Heuristic 1: Estimate the truth probability as 93.75%. The 93.75%
2592 ** value corresponds to -1 in LogEst notation, so this means decrement
2593 ** the WhereLoop.nOut field for every such WHERE clause term.
2594 **
2595 ** Heuristic 2: If there exists one or more WHERE clause terms of the
2596 ** form "x==EXPR" and EXPR is not a constant 0 or 1, then make sure the
2597 ** final output row estimate is no greater than 1/4 of the total number
2598 ** of rows in the table. In other words, assume that x==EXPR will filter
2599 ** out at least 3 out of 4 rows. If EXPR is -1 or 0 or 1, then maybe the
2600 ** "x" column is boolean or else -1 or 0 or 1 is a common default value
2601 ** on the "x" column and so in that case only cap the output row estimate
2602 ** at 1/2 instead of 1/4.
2603 */
2607 LogEst nRow /* Number of rows in the entire table */
2608 ){
2625 }
2628 /* If there are extra terms in the WHERE clause not used by an index
2629 ** that depend only on the table being scanned, and that will tend to
2630 ** cause many rows to be omitted, then mark that table as
2631 ** "self-culling".
2632 **
2633 ** 2022-03-24: Self-culling only applies if either the extra terms
2634 ** are straight comparison operators that are non-true with NULL
2635 ** operand, or if the loop is not an OUTER JOIN.
2636 */
2640 ){
2642 }
2643 }
2645 /* If a truth probability is specified using the likelihood() hints,
2646 ** then use the probability provided by the application. */
2649 /* In the absence of explicit truth probabilities, use heuristics to
2650 ** guess a reasonable truth probability. */
2654 ){
2662 }
2666 }
2667 }
2668 }
2669 }
2670 }
2673 }
2674 }
2676 /*
2677 ** Term pTerm is a vector range comparison operation. The first comparison
2678 ** in the vector can be optimized using column nEq of the index. This
2679 ** function returns the total number of vector elements that can be used
2680 ** as part of the range comparison.
2681 **
2682 ** For example, if the query is:
2683 **
2684 ** WHERE a = ? AND (b, c, d) > (?, ?, ?)
2685 **
2686 ** and the index:
2687 **
2688 ** CREATE INDEX ... ON (a, b, c, d, e)
2689 **
2690 ** then this function would be invoked with nEq=1. The value returned in
2691 ** this case is 3.
2692 */
2699 ){
2705 /* Test if comparison i of pTerm is compatible with column (i+nEq)
2706 ** of the index. If not, exit the loop. */
2719 }
2721 /* Check that the LHS of the comparison is a column reference to
2722 ** the right column of the right source table. And that the sort
2723 ** order of the index column is the same as the sort order of the
2724 ** leftmost index column. */
2729 ){
2731 }
2741 }
2743 }
2745 /*
2746 ** Adjust the cost C by the costMult facter T. This only occurs if
2747 ** compiled with -DSQLITE_ENABLE_COSTMULT
2748 */
2749 #ifdef SQLITE_ENABLE_COSTMULT
2750 # define ApplyCostMultiplier(C,T) C += T
2751 #else
2752 # define ApplyCostMultiplier(C,T)
2753 #endif
2755 /*
2756 ** We have so far matched pBuilder->pNew->u.btree.nEq terms of the
2757 ** index pIndex. Try to match one more.
2758 **
2759 ** When this function is called, pBuilder->pNew->nOut contains the
2760 ** number of rows expected to be visited by filtering using the nEq
2761 ** terms only. If it is modified, this value is restored before this
2762 ** function returns.
2763 **
2764 ** If pProbe->idxType==SQLITE_IDXTYPE_IPK, that means pIndex is
2765 ** a fake index used for the INTEGER PRIMARY KEY.
2766 */
2771 LogEst nInMul /* log(Number of iterations due to IN) */
2772 ){
2806 }
2828 LogEst rCostIdx;
2831 #ifdef SQLITE_ENABLE_STAT4
2833 #endif
2836 ){
2838 }
2841 /* Do not allow the upper bound of a LIKE optimization range constraint
2842 ** to mix with a lower range bound from some other source */
2845 /* tag-20191211-001: Do not allow constraints from the WHERE clause to
2846 ** be used by the right table of a LEFT JOIN nor by the left table of a
2847 ** RIGHT JOIN. Only constraints in the ON clause are allowed.
2848 ** See tag-20191211-002 for the vtab equivalent.
2849 **
2850 ** 2022-06-06: See https://sqlite.org/forum/forumpost/206d99a16dd9212f
2851 ** for an example of a WHERE clause constraints that may not be used on
2852 ** the right table of a RIGHT JOIN because the constraint implies a
2853 ** not-NULL condition on the left table of the RIGHT JOIN.
2854 **
2855 ** 2022-06-10: The same condition applies to termCanDriveIndex() above.
2856 ** https://sqlite.org/forum/forumpost/51e6959f61
2857 */
2866 ){
2868 }
2869 }
2875 }
2889 );
2894 /* "x IN (SELECT ...)": TUNING: the SELECT returns 25 rows */
2898 /* The expression may actually be of the form (x, y) IN (SELECT...).
2899 ** In this case there is a separate term for each of (x) and (y).
2900 ** However, the nIn multiplier should only be applied once, not once
2901 ** for each such term. The following loop checks that pTerm is the
2902 ** first such term in use, and sets nIn back to 0 if it is not. */
2905 }
2907 /* "x IN (value, value, ...)" */
2909 }
2912 /* Let:
2913 ** N = the total number of rows in the table
2914 ** K = the number of entries on the RHS of the IN operator
2915 ** M = the number of rows in the table that match terms to the
2916 ** to the left in the same index. If the IN operator is on
2917 ** the left-most index column, M==N.
2918 **
2919 ** Given the definitions above, it is better to omit the IN operator
2920 ** from the index lookup and instead do a scan of the M elements,
2921 ** testing each scanned row against the IN operator separately, if:
2922 **
2923 ** M*log(K) < K*log(N)
2924 **
2925 ** Our estimates for M, K, and N might be inaccurate, so we build in
2926 ** a safety margin of 2 (LogEst: 10) that favors using the IN operator
2927 ** with the index, as using an index has better worst-case behavior.
2928 ** If we do not have real sqlite_stat1 data, always prefer to use
2929 ** the index. Do not bother with this optimization on very small
2930 ** tables (less than 2 rows) as it is pointless in that case.
2931 */
2934 /* TUNING v----- 10 to bias toward indexed IN */
2953 }
2954 }
2962 ){
2965 ){
2969 }
2970 }
2980 );
2984 /* Range constraints that come from the LIKE optimization are
2985 ** always used in pairs. */
2994 }
3002 );
3006 }
3008 /* At this point pNew->nOut is set to the number of rows expected to
3009 ** be visited by the index scan before considering term pTerm, or the
3010 ** values of nIn and nInMul. In other words, assuming that all
3011 ** "x IN(...)" terms are replaced with "x = ?". This block updates
3012 ** the value of pNew->nOut to account for pTerm (but not nIn/nInMul). */
3015 /* Adjust nOut using stat4 data. Or, if there is no stat4
3016 ** data, using some other estimate. */
3029 #ifdef SQLITE_ENABLE_STAT4
3036 ){
3045 }
3051 /* TUNING: Mark terms as "low selectivity" if they seem likely
3052 ** to be true for half or more of the rows in the table.
3053 ** See tag-202002240-1 */
3055 ){
3061 }
3062 #endif
3065 /* If the term has previously been used with an assumption of
3066 ** higher selectivity, then set the flag to rerun the
3067 ** loop computations. */
3069 }
3070 }
3073 }
3074 }
3076 #endif
3077 {
3080 /* TUNING: If there is no likelihood() value, assume that a
3081 ** "col IS NULL" expression matches twice as many rows
3082 ** as (col=?). */
3084 }
3085 }
3086 }
3087 }
3089 /* Set rCostIdx to the cost of visiting selected rows in index. Add
3090 ** it to pNew->rRun, which is currently set to the cost of the index
3091 ** seek only. Then, if this is a non-covering index, add the cost of
3092 ** visiting the rows in the main table. */
3098 }
3111 }
3117 ){
3119 }
3121 #ifdef SQLITE_ENABLE_STAT4
3123 #endif
3124 }
3134 /* Consider using a skip-scan if there are no WHERE clause constraints
3135 ** available for the left-most terms of the index, and if the average
3136 ** number of repeats in the left-most terms is at least 18.
3137 **
3138 ** The magic number 18 is selected on the basis that scanning 17 rows
3139 ** is almost always quicker than an index seek (even though if the index
3140 ** contains fewer than 2^17 rows we assume otherwise in other parts of
3141 ** the code). And, even if it is not, it should not be too much slower.
3142 ** On the other hand, the extra seeks could end up being significantly
3143 ** more expensive. */
3153 ){
3154 LogEst nIter;
3161 /* TUNING: Because uncertainties in the estimates for skip-scan queries,
3162 ** add a 1.375 fudge factor to make skip-scan slightly less likely. */
3169 }
3174 }
3176 /*
3177 ** Return True if it is possible that pIndex might be useful in
3178 ** implementing the ORDER BY clause in pBuilder.
3179 **
3180 ** Return False if pBuilder does not contain an ORDER BY clause or
3181 ** if there is no way for pIndex to be useful in implementing that
3182 ** ORDER BY clause.
3183 */
3187 int iCursor
3188 ){
3202 }
3208 }
3209 }
3210 }
3211 }
3213 }
3215 /* Check to see if a partial index with pPartIndexWhere can be used
3216 ** in the current query. Return true if it can be and false if not.
3217 */
3223 ){
3233 }
3242 ){
3244 }
3245 }
3247 }
3249 /*
3250 ** Add all WhereLoop objects for a single table of the join where the table
3251 ** is identified by pBuilder->pNew->iTab. That table is guaranteed to be
3252 ** a b-tree table, not a virtual table.
3253 **
3254 ** The costs (WhereLoop.rRun) of the b-tree loops added by this function
3255 ** are calculated as follows:
3256 **
3257 ** For a full scan, assuming the table (or index) contains nRow rows:
3258 **
3259 ** cost = nRow * 3.0 // full-table scan
3260 ** cost = nRow * K // scan of covering index
3261 ** cost = nRow * (K+3.0) // scan of non-covering index
3262 **
3263 ** where K is a value between 1.1 and 3.0 set based on the relative
3264 ** estimated average size of the index and table records.
3265 **
3266 ** For an index scan, where nVisit is the number of index rows visited
3267 ** by the scan, and nSeek is the number of seek operations required on
3268 ** the index b-tree:
3269 **
3270 ** cost = nSeek * (log(nRow) + K * nVisit) // covering index
3271 ** cost = nSeek * (log(nRow) + (K+3.0) * nVisit) // non-covering index
3272 **
3273 ** Normally, nSeek is 1. nSeek values greater than 1 come about if the
3274 ** WHERE clause includes "x IN (....)" terms used in place of "x=?". Or when
3275 ** implicit "x IN (SELECT x FROM tbl)" terms are added for skip-scans.
3276 **
3277 ** The estimated values (nRow, nVisit, nSeek) often contain a large amount
3278 ** of uncertainty. For this reason, scoring is designed to pick plans that
3279 ** "do the least harm" if the estimates are inaccurate. For example, a
3280 ** log(nRow) factor is omitted from a non-covering index scan in order to
3281 ** bias the scoring in favor of using an index, since the worst-case
3282 ** performance of using an index is far better than the worst-case performance
3283 ** of a full table scan.
3284 */
3287 Bitmask mPrereq /* Extra prerequesites for using this table */
3288 ){
3314 /* An INDEXED BY clause specifies a particular index to use */
3319 /* There is no INDEXED BY clause. Create a fake Index object in local
3320 ** variable sPk to represent the rowid primary key index. Make this
3321 ** fake index the first in a chain of Index objects with all of the real
3322 ** indices to follow */
3337 /* The real indices of the table are only considered if the
3338 ** NOT INDEXED qualifier is omitted from the FROM clause */
3340 }
3342 }
3345 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
3346 /* Automatic indexes */
3356 ){
3357 /* Generate auto-index WhereLoops */
3370 /* TUNING: One-time cost for computing the automatic index is
3371 ** estimated to be X*N*log2(N) where N is the number of rows in
3372 ** the table being indexed and where X is 7 (LogEst=28) for normal
3373 ** tables or 0.5 (LogEst=-10) for views and subqueries. The value
3374 ** of X is smaller for views and subqueries so that the query planner
3375 ** will be more aggressive about generating automatic indexes for
3376 ** those objects, since there is no opportunity to add schema
3377 ** indexes on subqueries and views. */
3383 }
3386 /* TUNING: Each index lookup yields 20 rows in the table. This
3387 ** is more than the usual guess of 10 rows, since we have no way
3388 ** of knowing how selective the index will ultimately be. It would
3389 ** not be unreasonable to make this value much larger. */
3395 }
3396 }
3397 }
3400 /* Loop over all indices. If there was an INDEXED BY clause, then only
3401 ** consider index pProbe. */
3404 ){
3408 ){
3411 }
3426 /* The ONEPASS_DESIRED flags never occurs together with ORDER BY */
3429 /* Integer primary key index */
3432 /* Full table scan */
3434 /* TUNING: Cost of full table scan is 3.0*N. The 3.0 factor is an
3435 ** extra cost designed to discourage the use of full table scans,
3436 ** since index lookups have better worst-case performance if our
3437 ** stat guesses are wrong. Reduce the 3.0 penalty slightly
3438 ** (to 2.75) if we have valid STAT4 information for the table.
3439 ** At 2.75, a full table scan is preferred over using an index on
3440 ** a column with just two distinct values where each value has about
3441 ** an equal number of appearances. Without STAT4 data, we still want
3442 ** to use an index in that case, since the constraint might be for
3443 ** the scarcer of the two values, and in that case an index lookup is
3444 ** better.
3445 */
3446 #ifdef SQLITE_ENABLE_STAT4
3448 #else
3450 #endif
3457 Bitmask m;
3464 }
3466 /* Full scan via index */
3477 )
3478 ){
3481 /* The cost of visiting the index rows is N*K, where K is
3482 ** between 1.1 and 3.0, depending on the relative sizes of the
3483 ** index and table rows. */
3486 /* If this is a non-covering index scan, add in the cost of
3487 ** doing table lookups. The cost will be 3x the number of
3488 ** lookups. Take into account WHERE clause terms that can be
3489 ** satisfied using just the index, and that do not require a
3490 ** table lookup. */
3499 }
3500 /* pTerm can be evaluated using just the index. So reduce
3501 ** the expected number of table lookups accordingly */
3505 nLookup--;
3507 }
3508 }
3511 }
3515 /* Do not do an SCAN of a index-on-expression in a RIGHT JOIN
3516 ** because the cursor used to access the index might not be
3517 ** positioned to the correct row during the right-join no-match
3518 ** loop. */
3521 }
3524 }
3525 }
3530 /* If a non-unique index is used, or if a prefix of the key for
3531 ** unique index is used (making the index functionally non-unique)
3532 ** then the sqlite_stat1 data becomes important for scoring the
3533 ** plan */
3535 }
3536 #ifdef SQLITE_ENABLE_STAT4
3540 #endif
3541 }
3543 }
3545 #ifndef SQLITE_OMIT_VIRTUALTABLE
3547 /*
3548 ** Return true if pTerm is a virtual table LIMIT or OFFSET term.
3549 */
3554 }
3556 /*
3557 ** Argument pIdxInfo is already populated with all constraints that may
3558 ** be used by the virtual table identified by pBuilder->pNew->iTab. This
3559 ** function marks a subset of those constraints usable, invokes the
3560 ** xBestIndex method and adds the returned plan to pBuilder.
3561 **
3562 ** A constraint is marked usable if:
3563 **
3564 ** * Argument mUsable indicates that its prerequisites are available, and
3565 **
3566 ** * It is not one of the operators specified in the mExclude mask passed
3567 ** as the fourth argument (which in practice is either WO_IN or 0).
3568 **
3569 ** Argument mPrereq is a mask of tables that must be scanned before the
3570 ** virtual table in question. These are added to the plans prerequisites
3571 ** before it is added to pBuilder.
3572 **
3573 ** Output parameter *pbIn is set to true if the plan added to pBuilder
3574 ** uses one or more WO_IN terms, or false otherwise.
3575 */
3585 ){
3602 /* Set the usable flag on the subset of constraints identified by
3603 ** arguments mUsable and mExclude. */
3611 ){
3613 }
3614 }
3616 /* Initialize the output fields of the sqlite3_index_info structure */
3628 /* Invoke the virtual table xBestIndex() method */
3632 /* If the xBestIndex method returns SQLITE_CONSTRAINT, that means
3633 ** that the particular combination of parameters provided is unusable.
3634 ** Make no entries in the loop table.
3635 */
3638 }
3640 }
3657 ){
3661 }
3678 }
3681 }
3682 }
3686 /* A virtual table that is constrained by an IN clause may not
3687 ** consume the ORDER BY clause because (1) the order of IN terms
3688 ** is not necessarily related to the order of output terms and
3689 ** (2) Multiple outputs from a single IN value will not merge
3690 ** together. */
3694 }
3698 /* If there is an IN(...) term handled as an == (separate call to
3699 ** xFilter for each value on the RHS of the IN) and a LIMIT or
3700 ** OFFSET term handled as well, the plan is unusable. Set output
3701 ** variable *pbRetryLimit to true to tell the caller to retry with
3702 ** LIMIT and OFFSET disabled. */
3707 }
3710 }
3711 }
3712 }
3717 /* The non-zero argvIdx values must be contiguous. Raise an
3718 ** error if they are not */
3722 }
3723 }
3735 /* Set the WHERE_ONEROW flag if the xBestIndex() method indicated
3736 ** that the scan will visit at most one row. Clear it otherwise. */
3741 }
3746 }
3752 }
3754 /*
3755 ** Return the collating sequence for a constraint passed into xBestIndex.
3756 **
3757 ** pIdxInfo must be an sqlite3_index_info structure passed into xBestIndex.
3758 ** This routine depends on there being a HiddenIndexInfo structure immediately
3759 ** following the sqlite3_index_info structure.
3760 **
3761 ** Return a pointer to the collation name:
3762 **
3763 ** 1. If there is an explicit COLLATE operator on the constaint, return it.
3764 **
3765 ** 2. Else, if the column has an alternative collation, return that.
3766 **
3767 ** 3. Otherwise, return "BINARY".
3768 */
3778 }
3780 }
3782 }
3784 /*
3785 ** Return true if constraint iCons is really an IN(...) constraint, or
3786 ** false otherwise. If iCons is an IN(...) constraint, set (if bHandle!=0)
3787 ** or clear (if bHandle==0) the flag to handle it using an iterator.
3788 */
3797 }
3799 }
3801 }
3803 /*
3804 ** This interface is callable from within the xBestIndex callback only.
3805 **
3806 ** If possible, set (*ppVal) to point to an object containing the value
3807 ** on the right-hand-side of constraint iCons.
3808 */
3813 ){
3825 );
3827 }
3829 }
3834 }
3837 }
3839 /*
3840 ** Return true if ORDER BY clause may be handled as DISTINCT.
3841 */
3846 }
3848 #if (defined(SQLITE_ENABLE_DBPAGE_VTAB) || defined(SQLITE_TEST)) \
3849 && !defined(SQLITE_OMIT_VIRTUALTABLE)
3850 /*
3851 ** Cause the prepared statement that is associated with a call to
3852 ** xBestIndex to potentiall use all schemas. If the statement being
3853 ** prepared is read-only, then just start read transactions on all
3854 ** schemas. But if this is a write operation, start writes on all
3855 ** schemas.
3856 **
3857 ** This is used by the (built-in) sqlite_dbpage virtual table.
3858 */
3866 }
3870 }
3871 }
3872 }
3873 #endif
3875 /*
3876 ** Add all WhereLoop objects for a table of the join identified by
3877 ** pBuilder->pNew->iTab. That table is guaranteed to be a virtual table.
3878 **
3879 ** If there are no LEFT or CROSS JOIN joins in the query, both mPrereq and
3880 ** mUnusable are set to 0. Otherwise, mPrereq is a mask of all FROM clause
3881 ** entries that occur before the virtual table in the FROM clause and are
3882 ** separated from it by at least one LEFT or CROSS JOIN. Similarly, the
3883 ** mUnusable mask contains all FROM clause entries that occur after the
3884 ** virtual table and are separated from it by at least one LEFT or
3885 ** CROSS JOIN.
3886 **
3887 ** For example, if the query were:
3888 **
3889 ** ... FROM t1, t2 LEFT JOIN t3, t4, vt CROSS JOIN t5, t6;
3890 **
3891 ** then mPrereq corresponds to (t1, t2) and mUnusable to (t5, t6).
3892 **
3893 ** All the tables in mPrereq must be scanned before the current virtual
3894 ** table. So any terms for which all prerequisites are satisfied by
3895 ** mPrereq may be specified as "usable" in all calls to xBestIndex.
3896 ** Conversely, all tables in mUnusable must be scanned after the current
3897 ** virtual table, so any terms for which the prerequisites overlap with
3898 ** mUnusable should always be configured as "not-usable" for xBestIndex.
3899 */
3903 Bitmask mUnusable /* Tables that must be scanned after this one */
3904 ){
3915 u16 mNoOmit;
3935 }
3937 /* First call xBestIndex() with all constraints usable. */
3942 );
3947 );
3948 }
3950 /* If the call to xBestIndex() with all terms enabled produced a plan
3951 ** that does not require any source tables (IOW: a plan with mBest==0)
3952 ** and does not use an IN(...) operator, then there is no point in making
3953 ** any further calls to xBestIndex() since they will all return the same
3954 ** result (if the xBestIndex() implementation is sane). */
3961 /* If the plan produced by the earlier call uses an IN(...) term, call
3962 ** xBestIndex again, this time with IN(...) terms disabled. */
3972 }
3973 }
3975 /* Call xBestIndex once for each distinct value of (prereqRight & ~mPrereq)
3976 ** in the set of terms that apply to the current virtual table. */
3982 Bitmask mThis = (
3984 );
3986 }
3997 }
3998 }
4000 /* If the calls to xBestIndex() in the above loop did not find a plan
4001 ** that requires no source tables at all (i.e. one guaranteed to be
4002 ** usable), make a call here with all source tables disabled */
4008 }
4010 /* If the calls to xBestIndex() have so far failed to find a plan
4011 ** that requires no source tables at all and does not use an IN(...)
4012 ** operator, make a final call to obtain one here. */
4017 }
4018 }
4024 }
4027 /*
4028 ** Add WhereLoop entries to handle OR terms. This works for either
4029 ** btrees or virtual tables.
4030 */
4033 Bitmask mPrereq,
4034 Bitmask mUnusable
4035 ){
4042 WhereClause tempWC;
4043 WhereLoopBuilder sSubBuild;
4054 /* The multi-index OR optimization does not work for RIGHT and FULL JOIN */
4060 ){
4084 }
4086 #ifdef WHERETRACE_ENABLED
4091 }
4092 #endif
4093 #ifndef SQLITE_OMIT_VIRTUALTABLE
4097 #endif
4098 {
4100 }
4103 }
4115 WhereOrSet sPrev;
4123 }
4124 }
4125 }
4126 }
4134 /* TUNING: Currently sSum.a[i].rRun is set to the sum of the costs
4135 ** of all sub-scans required by the OR-scan. However, due to rounding
4136 ** errors, it may be that the cost of the OR-scan is equal to its
4137 ** most expensive sub-scan. Add the smallest possible penalty
4138 ** (equivalent to multiplying the cost by 1.07) to ensure that
4139 ** this does not happen. Otherwise, for WHERE clauses such as the
4140 ** following where there is an index on "y":
4141 **
4142 ** WHERE likelihood(x=?, 0.99) OR y=?
4143 **
4144 ** the planner may elect to "OR" together a full-table scan and an
4145 ** index lookup. And other similarly odd results. */
4150 }
4152 }
4153 }
4155 }
4157 /*
4158 ** Add all WhereLoop objects for all tables
4159 */
4175 /* Loop over the tables in the join, from left to right */
4186 ){
4187 /* Add prerequisites to prevent reordering of FROM clause terms
4188 ** across CROSS joins and outer joins. The bFirstPastRJ boolean
4189 ** prevents the right operand of a RIGHT JOIN from being swapped with
4190 ** other elements even further to the right.
4191 **
4192 ** The JT_LTORJ case and the hasRightJoin flag work together to
4193 ** prevent FROM-clause terms from moving from the right side of
4194 ** a LEFT JOIN over to the left side of that join if the LEFT JOIN
4195 ** is itself on the left side of a RIGHT JOIN.
4196 */
4202 }
4203 #ifndef SQLITE_OMIT_VIRTUALTABLE
4209 }
4210 }
4214 {
4216 }
4219 }
4223 /* We hit the query planner search limit set by iPlanLimit */
4228 }
4229 }
4230 }
4234 }
4236 /*
4237 ** Examine a WherePath (with the addition of the extra WhereLoop of the 6th
4238 ** parameters) to see if it outputs rows in the requested ORDER BY
4239 ** (or GROUP BY) without requiring a separate sort operation. Return N:
4240 **
4241 ** N>0: N terms of the ORDER BY clause are satisfied
4242 ** N==0: No terms of the ORDER BY clause are satisfied
4243 ** N<0: Unknown yet how many terms of ORDER BY might be satisfied.
4244 **
4245 ** Note that processing for WHERE_GROUPBY and WHERE_DISTINCTBY is not as
4246 ** strict. With GROUP BY and DISTINCT the only requirement is that
4247 ** equivalent rows appear immediately adjacent to one another. GROUP BY
4248 ** and DISTINCT do not require rows to appear in any particular order as long
4249 ** as equivalent rows are grouped together. Thus for GROUP BY and DISTINCT
4250 ** the pOrderBy terms can be matched in any order. With ORDER BY, the
4251 ** pOrderBy terms must be matched in strict left-to-right order.
4252 */
4261 ){
4287 /*
4288 ** We say the WhereLoop is "one-row" if it generates no more than one
4289 ** row of output. A WhereLoop is one-row if all of the following are true:
4290 ** (a) All index columns match with WHERE_COLUMN_EQ.
4291 ** (b) The index is unique
4292 ** Any WhereLoop with an WHERE_COLUMN_EQ constraint on the rowid is one-row.
4293 ** Every one-row WhereLoop will have the WHERE_ONEROW bit set in wsFlags.
4294 **
4295 ** We say the WhereLoop is "order-distinct" if the set of columns from
4296 ** that WhereLoop that are in the ORDER BY clause are different for every
4297 ** row of the WhereLoop. Every one-row WhereLoop is automatically
4298 ** order-distinct. A WhereLoop that has no columns in the ORDER BY clause
4299 ** is not order-distinct. To be order-distinct is not quite the same as being
4300 ** UNIQUE since a UNIQUE column or index can have multiple rows that
4301 ** are NULL and NULL values are equivalent for the purpose of order-distinct.
4302 ** To be order-distinct, the columns must be UNIQUE and NOT NULL.
4303 **
4304 ** The rowid for a table is always UNIQUE and NOT NULL so whenever the
4305 ** rowid appears in the ORDER BY clause, the corresponding WhereLoop is
4306 ** automatically order-distinct.
4307 */
4322 }
4330 }
4334 ){
4336 }
4340 }
4343 /* Mark off any ORDER BY term X that is a column in the table of
4344 ** the current loop for which there is term in the WHERE
4345 ** clause of the form X IS NULL or X=? that reference only outer
4346 ** loops.
4347 */
4358 /* IN terms are only valid for sorting in the ORDER BY LIMIT
4359 ** optimization, and then only if they are actually used
4360 ** by the query plan */
4365 }
4373 }
4375 }
4377 }
4392 /* All relevant terms of the index must also be non-NULL in order
4393 ** for isOrderDistinct to be true. So the isOrderDistint value
4394 ** computed here might be a false positive. Corrections will be
4395 ** made at tag-20210426-1 below */
4398 }
4400 /* Loop through all columns of the index and deal with the ones
4401 ** that are not constrained by == or IN.
4402 */
4410 );
4414 /* Skip over == and IS and ISNULL terms. (Also skip IN terms when
4415 ** doing WHERE_ORDERBY_LIMIT processing). Except, IS and ISNULL
4416 ** terms imply that the index is not UNIQUE NOT NULL in which case
4417 ** the loop need to be marked as not order-distinct because it can
4418 ** have repeated NULL rows.
4419 **
4420 ** If the current term is a column of an ((?,?) IN (SELECT...))
4421 ** expression for which the SELECT returns more than one column,
4422 ** check that it is the only column used by this loop. Otherwise,
4423 ** if it is one of two or more, none of the columns can be
4424 ** considered to match an ORDER BY term.
4425 */
4432 }
4435 /* ALWAYS() justification: eOp is an equality operator due to the
4436 ** j<pLoop->u.btree.nEq constraint above. Any equality other
4437 ** than WO_IN is captured by the previous "if". So this one
4438 ** always has to be WO_IN. */
4445 }
4446 }
4447 }
4448 }
4450 /* Get the column number in the table (iColumn) and sort order
4451 ** (revIdx) for the j-th column of the index.
4452 */
4460 }
4462 /* An unconstrained column that might be NULL means that this
4463 ** WhereLoop is not well-ordered. tag-20210426-1
4464 */
4469 ){
4471 }
4474 }
4475 }
4477 /* Find the ORDER BY term that corresponds to the j-th column
4478 ** of the index and mark that ORDER BY term off
4479 */
4496 }
4497 }
4501 }
4504 }
4507 }
4509 /* Make sure the sort order is compatible in an ORDER BY clause.
4510 ** Sort order is irrelevant for a GROUP BY clause. */
4514 ){
4516 }
4521 }
4522 }
4528 }
4529 }
4534 }
4537 /* No match found */
4541 }
4543 }
4548 }
4551 /* Mark off any other ORDER BY terms that reference pLoop */
4556 Bitmask mTerm;
4563 }
4564 }
4565 }
4572 }
4574 }
4576 }
4579 /*
4580 ** If the WHERE_GROUPBY flag is set in the mask passed to sqlite3WhereBegin(),
4581 ** the planner assumes that the specified pOrderBy list is actually a GROUP
4582 ** BY clause - and so any order that groups rows as required satisfies the
4583 ** request.
4584 **
4585 ** Normally, in this case it is not possible for the caller to determine
4586 ** whether or not the rows are really being delivered in sorted order, or
4587 ** just in some other order that provides the required grouping. However,
4588 ** if the WHERE_SORTBYGROUP flag is also passed to sqlite3WhereBegin(), then
4589 ** this function may be called on the returned WhereInfo object. It returns
4590 ** true if the rows really will be sorted in the specified order, or false
4591 ** otherwise.
4592 **
4593 ** For example, assuming:
4594 **
4595 ** CREATE INDEX i1 ON t1(x, Y);
4596 **
4597 ** then
4598 **
4599 ** SELECT * FROM t1 GROUP BY x,y ORDER BY x,y; -- IsSorted()==1
4600 ** SELECT * FROM t1 GROUP BY y,x ORDER BY y,x; -- IsSorted()==0
4601 */
4606 }
4608 #ifdef WHERETRACE_ENABLED
4609 /* For debugging use only: */
4617 }
4618 #endif
4620 /*
4621 ** Return the cost of sorting nRow rows, assuming that the keys have
4622 ** nOrderby columns and that the first nSorted columns are already in
4623 ** order.
4624 */
4627 LogEst nRow,
4629 int nSorted
4630 ){
4631 /* TUNING: Estimated cost of a full external sort, where N is
4632 ** the number of rows to sort is:
4633 **
4634 ** cost = (3.0 * N * log(N)).
4635 **
4636 ** Or, if the order-by clause has X terms but only the last Y
4637 ** terms are out of order, then block-sorting will reduce the
4638 ** sorting cost to:
4639 **
4640 ** cost = (3.0 * N * log(N)) * (Y/X)
4641 **
4642 ** The (Y/X) term is implemented using stack variable rScale
4643 ** below.
4644 */
4650 /* Multiple by log(M) where M is the number of output rows.
4651 ** Use the LIMIT for M if it is smaller. Or if this sort is for
4652 ** a DISTINCT operator, M will be the number of distinct output
4653 ** rows, so fudge it downwards a bit.
4654 */
4658 /* TUNING: In the sort for a DISTINCT operator, assume that the DISTINCT
4659 ** reduces the number of output rows by a factor of 2 */
4661 }
4664 }
4666 /*
4667 ** Given the list of WhereLoop objects at pWInfo->pLoops, this routine
4668 ** attempts to find the lowest cost path that visits each WhereLoop
4669 ** once. This path is then loaded into the pWInfo->a[].pWLoop fields.
4670 **
4671 ** Assume that the total number of output rows that will need to be sorted
4672 ** will be nRowEst (in the 10*log2 representation). Or, ignore sorting
4673 ** costs if nRowEst==0.
4674 **
4675 ** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation
4676 ** error occurs.
4677 */
4703 /* TUNING: For simple queries, only the best path is tracked.
4704 ** For 2-way joins, the 5 best paths are followed.
4705 ** For joins of 3 or more tables, track the 10 best paths */
4710 /* If nRowEst is zero and there is an ORDER BY clause, ignore it. In this
4711 ** case the purpose of this call is to estimate the number of rows returned
4712 ** by the overall query. Once this estimate has been obtained, the caller
4713 ** will invoke this function a second time, passing the estimate as the
4714 ** nRowEst parameter. */
4719 }
4721 /* Allocate and initialize space for aTo, aFrom and aSortCost[] */
4732 }
4734 /* If there is an ORDER BY clause and it is not being ignored, set up
4735 ** space for the aSortCost[] array. Each element of the aSortCost array
4736 ** is either zero - meaning it has not yet been initialized - or the
4737 ** cost of sorting nRowEst rows of data where the first X terms of
4738 ** the ORDER BY clause are already in order, where X is the array
4739 ** index. */
4742 }
4746 /* Seed the search with a single WherePath containing zero WhereLoops.
4747 **
4748 ** TUNING: Do not let the number of iterations go above 28. If the cost
4749 ** of computing an automatic index is not paid back within the first 28
4750 ** rows, then do not use the automatic index. */
4755 /* If nLoop is zero, then there are no FROM terms in the query. Since
4756 ** in this case the query may return a maximum of one row, the results
4757 ** are already in the requested order. Set isOrdered to nOrderBy to
4758 ** indicate this. Or, if nLoop is greater than zero, set isOrdered to
4759 ** -1, indicating that the result set may or may not be ordered,
4760 ** depending on the loops added to the current plan. */
4762 }
4764 /* Compute successively longer WherePaths using the previous generation
4765 ** of WherePaths as the basis for the next. Keep track of the mxChoice
4766 ** best paths at each generation */
4781 /* Do not use an automatic index if the this loop is expected
4782 ** to run less than 1.25 times. It is tempting to also exclude
4783 ** automatic index usage on an outer loop, but sometimes an automatic
4784 ** index is useful in the outer loop of a correlated subquery. */
4787 }
4789 /* At this point, pWLoop is a candidate to be the next loop.
4790 ** Compute its cost */
4801 }
4806 );
4807 }
4808 /* TUNING: Add a small extra penalty (5) to sorting as an
4809 ** extra encouragment to the query planner to select a plan
4810 ** where the rows emerge in the correct order without any sorting
4811 ** required. */
4821 }
4823 /* Check to see if pWLoop should be added to the set of
4824 ** mxChoice best-so-far paths.
4825 **
4826 ** First look for an existing path among best-so-far paths
4827 ** that covers the same set of loops and has the same isOrdered
4828 ** setting as the current path candidate.
4829 **
4830 ** The term "((pTo->isOrdered^isOrdered)&0x80)==0" is equivalent
4831 ** to (pTo->isOrdered==(-1))==(isOrdered==(-1))" for the range
4832 ** of legal values for isOrdered, -1..64.
4833 */
4837 ){
4840 }
4841 }
4843 /* None of the existing best-so-far paths match the candidate. */
4846 ){
4847 /* The current candidate is no better than any of the mxChoice
4848 ** paths currently in the best-so-far buffer. So discard
4849 ** this candidate as not viable. */
4855 }
4856 #endif
4858 }
4859 /* If we reach this points it means that the new candidate path
4860 ** needs to be added to the set of best-so-far paths. */
4862 /* Increase the size of the aTo set by one */
4865 /* New path replaces the prior worst to keep count below mxChoice */
4867 }
4874 }
4875 #endif
4877 /* Control reaches here if best-so-far path pTo=aTo[jj] covers the
4878 ** same set of loops and has the same isOrdered setting as the
4879 ** candidate path. Check to see if the candidate should replace
4880 ** pTo or if the candidate should be skipped.
4881 **
4882 ** The conditional is an expanded vector comparison equivalent to:
4883 ** (pTo->rCost,pTo->nRow,pTo->rUnsorted) <= (rCost,nOut,rUnsorted)
4884 */
4889 )
4890 )
4891 ){
4901 }
4902 #endif
4903 /* Discard the candidate path from further consideration */
4906 }
4908 /* Control reaches here if the candidate path is better than the
4909 ** pTo path. Replace pTo with the candidate. */
4919 }
4920 #endif
4921 }
4922 /* pWLoop is a winner. Add it to the set of best so far */
4938 ){
4942 }
4943 }
4944 }
4945 }
4946 }
4959 }
4960 }
4961 }
4962 #endif
4964 /* Swap the roles of aFrom and aTo for the next generation */
4969 }
4975 }
4977 /* Find the lowest cost path. pFrom will be left pointing to that path */
4981 }
4983 /* Load the lowest cost path into pWInfo */
4989 }
4993 && nRowEst
4994 ){
4995 Bitmask notUsed;
5000 }
5001 }
5008 }
5017 ){
5026 }
5027 }
5028 }
5032 ){
5034 }
5035 }
5038 ){
5042 );
5047 }
5048 }
5049 }
5054 /* Free temporary memory and return success */
5057 }
5059 /*
5060 ** Most queries use only a single table (they are not joins) and have
5061 ** simple == constraints against indexed fields. This routine attempts
5062 ** to plan those simple cases using much less ceremony than the
5063 ** general-purpose query planner, and thereby yield faster sqlite3_prepare()
5064 ** times for the common case.
5065 **
5066 ** Return non-zero on success, if this query can be handled by this
5067 ** no-frills query planner. Return zero if this query needs the
5068 ** general-purpose query planner.
5069 */
5080 WhereScan scan;
5092 }
5106 /* TUNING: Cost of a rowid lookup is 10 */
5123 }
5128 }
5132 /* TUNING: Cost of a unique index lookup is 15 */
5135 }
5136 }
5147 }
5149 #ifdef SQLITE_DEBUG
5151 #endif
5152 #ifdef WHERETRACE_ENABLED
5155 }
5156 #endif
5158 }
5160 }
5162 /*
5163 ** Helper function for exprIsDeterministic().
5164 */
5169 }
5171 }
5173 /*
5174 ** Return true if the expression contains no non-deterministic SQL
5175 ** functions. Do not consider non-deterministic SQL functions that are
5176 ** part of sub-select statements.
5177 */
5179 Walker w;
5186 }
5189 #ifdef WHERETRACE_ENABLED
5190 /*
5191 ** Display all WhereLoops in pWInfo
5192 */
5202 }
5203 }
5204 }
5205 # define WHERETRACE_ALL_LOOPS(W,C) showAllWhereLoops(W,C)
5206 #else
5207 # define WHERETRACE_ALL_LOOPS(W,C)
5208 #endif
5210 /* Attempt to omit tables from a join that do not affect the result.
5211 ** For a table to not affect the result, the following must be true:
5212 **
5213 ** 1) The query must not be an aggregate.
5214 ** 2) The table must be the RHS of a LEFT JOIN.
5215 ** 3) Either the query must be DISTINCT, or else the ON or USING clause
5216 ** must contain a constraint that limits the scan of the table to
5217 ** at most a single row.
5218 ** 4) The table must not be referenced by any part of the query apart
5219 ** from its own USING or ON clause.
5220 **
5221 ** For example, given:
5222 **
5223 ** CREATE TABLE t1(ipk INTEGER PRIMARY KEY, v1);
5224 ** CREATE TABLE t2(ipk INTEGER PRIMARY KEY, v2);
5225 ** CREATE TABLE t3(ipk INTEGER PRIMARY KEY, v3);
5226 **
5227 ** then table t2 can be omitted from the following:
5228 **
5229 ** SELECT v1, v3 FROM t1
5230 ** LEFT JOIN t2 ON (t1.ipk=t2.ipk)
5231 ** LEFT JOIN t3 ON (t1.ipk=t3.ipk)
5232 **
5233 ** or from:
5234 **
5235 ** SELECT DISTINCT v1, v3 FROM t1
5236 ** LEFT JOIN t2
5237 ** LEFT JOIN t3 ON (t1.ipk=t3.ipk)
5238 */
5241 Bitmask notReady
5242 ){
5244 Bitmask tabUsed;
5246 /* Preconditions checked by the caller */
5250 /* These two preconditions checked by the caller combine to guarantee
5251 ** condition (1) of the header comment */
5258 }
5268 ){
5270 }
5277 ){
5279 }
5280 }
5281 }
5288 }
5289 }
5293 }
5296 }
5298 }
5300 /*
5301 ** Check to see if there are any SEARCH loops that might benefit from
5302 ** using a Bloom filter. Consider a Bloom filter if:
5303 **
5304 ** (1) The SEARCH happens more than N times where N is the number
5305 ** of rows in the table that is being considered for the Bloom
5306 ** filter.
5307 ** (2) Some searches are expected to find zero rows. (This is determined
5308 ** by the WHERE_SELFCULL flag on the term.)
5309 ** (3) Bloom-filter processing is not disabled. (Checked by the
5310 ** caller.)
5311 ** (4) The size of the table being searched is known by ANALYZE.
5312 **
5313 ** This block of code merely checks to see if a Bloom filter would be
5314 ** appropriate, and if so sets the WHERE_BLOOMFILTER flag on the
5315 ** WhereLoop. The implementation of the Bloom filter comes further
5316 ** down where the code for each WhereLoop is generated.
5317 */
5320 ){
5322 LogEst nSearch;
5331 /* vvvvvv--- Always the case if WHERE_COLUMN_EQ is defined */
5333 ){
5339 ){
5344 "-> use Bloom-filter on loop %c because there are ~%.1e "
5348 }
5349 }
5351 }
5352 }
5354 /*
5355 ** Generate the beginning of the loop used for WHERE clause processing.
5356 ** The return value is a pointer to an opaque structure that contains
5357 ** information needed to terminate the loop. Later, the calling routine
5358 ** should invoke sqlite3WhereEnd() with the return value of this function
5359 ** in order to complete the WHERE clause processing.
5360 **
5361 ** If an error occurs, this routine returns NULL.
5362 **
5363 ** The basic idea is to do a nested loop, one loop for each table in
5364 ** the FROM clause of a select. (INSERT and UPDATE statements are the
5365 ** same as a SELECT with only a single table in the FROM clause.) For
5366 ** example, if the SQL is this:
5367 **
5368 ** SELECT * FROM t1, t2, t3 WHERE ...;
5369 **
5370 ** Then the code generated is conceptually like the following:
5371 **
5372 ** foreach row1 in t1 do \ Code generated
5373 ** foreach row2 in t2 do |-- by sqlite3WhereBegin()
5374 ** foreach row3 in t3 do /
5375 ** ...
5376 ** end \ Code generated
5377 ** end |-- by sqlite3WhereEnd()
5378 ** end /
5379 **
5380 ** Note that the loops might not be nested in the order in which they
5381 ** appear in the FROM clause if a different order is better able to make
5382 ** use of indices. Note also that when the IN operator appears in
5383 ** the WHERE clause, it might result in additional nested loops for
5384 ** scanning through all values on the right-hand side of the IN.
5385 **
5386 ** There are Btree cursors associated with each table. t1 uses cursor
5387 ** number pTabList->a[0].iCursor. t2 uses the cursor pTabList->a[1].iCursor.
5388 ** And so forth. This routine generates code to open those VDBE cursors
5389 ** and sqlite3WhereEnd() generates the code to close them.
5390 **
5391 ** The code that sqlite3WhereBegin() generates leaves the cursors named
5392 ** in pTabList pointing at their appropriate entries. The [...] code
5393 ** can use OP_Column and OP_Rowid opcodes on these cursors to extract
5394 ** data from the various tables of the loop.
5395 **
5396 ** If the WHERE clause is empty, the foreach loops must each scan their
5397 ** entire tables. Thus a three-way join is an O(N^3) operation. But if
5398 ** the tables have indices and there are terms in the WHERE clause that
5399 ** refer to those indices, a complete table scan can be avoided and the
5400 ** code will run much faster. Most of the work of this routine is checking
5401 ** to see if there are indices that can be used to speed up the loop.
5402 **
5403 ** Terms of the WHERE clause are also used to limit which rows actually
5404 ** make it to the "..." in the middle of the loop. After each "foreach",
5405 ** terms of the WHERE clause that use only terms in that loop and outer
5406 ** loops are evaluated and if false a jump is made around all subsequent
5407 ** inner loops (or around the "..." if the test occurs within the inner-
5408 ** most loop)
5409 **
5410 ** OUTER JOINS
5411 **
5412 ** An outer join of tables t1 and t2 is conceptally coded as follows:
5413 **
5414 ** foreach row1 in t1 do
5415 ** flag = 0
5416 ** foreach row2 in t2 do
5417 ** start:
5418 ** ...
5419 ** flag = 1
5420 ** end
5421 ** if flag==0 then
5422 ** move the row2 cursor to a null row
5423 ** goto start
5424 ** fi
5425 ** end
5426 **
5427 ** ORDER BY CLAUSE PROCESSING
5428 **
5429 ** pOrderBy is a pointer to the ORDER BY clause (or the GROUP BY clause
5430 ** if the WHERE_GROUPBY flag is set in wctrlFlags) of a SELECT statement
5431 ** if there is one. If there is no ORDER BY clause or if this routine
5432 ** is called from an UPDATE or DELETE statement, then pOrderBy is NULL.
5433 **
5434 ** The iIdxCur parameter is the cursor number of an index. If
5435 ** WHERE_OR_SUBCLAUSE is set, iIdxCur is the cursor number of an index
5436 ** to use for OR clause processing. The WHERE clause should use this
5437 ** specific cursor. If WHERE_ONEPASS_DESIRED is set, then iIdxCur is
5438 ** the first cursor in an array of cursors for all indices. iIdxCur should
5439 ** be used to compute the appropriate cursor depending on which index is
5440 ** used.
5441 */
5451 ** If WHERE_USE_LIMIT, then the limit amount */
5452 ){
5470 ));
5472 /* Only one of WHERE_OR_SUBCLAUSE or WHERE_USE_LIMIT */
5476 /* Variable initialization */
5480 /* An ORDER/GROUP BY clause of more than 63 terms cannot be optimized */
5484 /* The number of tables in the FROM clause is limited by the number of
5485 ** bits in a Bitmask
5486 */
5491 }
5493 /* This function normally generates a nested loop for all tables in
5494 ** pTabList. But if the WHERE_OR_SUBCLAUSE flag is set, then we should
5495 ** only generate code for the first table in pTabList and assume that
5496 ** any cursors associated with subsequent tables are uninitialized.
5497 */
5500 /* Allocate and initialize the WhereInfo structure that will become the
5501 ** return value. A single allocation is used to store the WhereInfo
5502 ** struct, the contents of WhereInfo.a[], the WhereClause structure
5503 ** and the WhereMaskSet structure. Since WhereClause contains an 8-byte
5504 ** field (type Bitmask) it must be aligned on an 8-byte boundary on
5505 ** some architectures. Hence the ROUND8() below.
5506 */
5513 }
5525 #ifndef SQLITE_OMIT_VIRTUALTABLE
5527 #endif
5535 ** a valid cursor number, to avoid an initial
5536 ** test for pMaskSet->n==0 in sqlite3WhereGetMask() */
5542 #ifdef SQLITE_DEBUG
5544 #endif
5546 /* Split the WHERE clause into separate subexpressions where each
5547 ** subexpression is separated by an AND operator.
5548 */
5552 /* Special case: No FROM clause
5553 */
5558 ){
5560 }
5563 /* Assign a bit from the bitmask to every term in the FROM clause.
5564 **
5565 ** The N-th term of the FROM clause is assigned a bitmask of 1<<N.
5566 **
5567 ** The rule of the previous sentence ensures thta if X is the bitmask for
5568 ** a table T, then X-1 is the bitmask for all other tables to the left of T.
5569 ** Knowing the bitmask for all tables to the left of a left join is
5570 ** important. Ticket #3015.
5571 **
5572 ** Note that bitmasks are created for all pTabList->nSrc tables in
5573 ** pTabList, not just the first nTabList tables. nTabList is normally
5574 ** equal to pTabList->nSrc but might be shortened to 1 if the
5575 ** WHERE_OR_SUBCLAUSE flag is set.
5576 */
5582 #ifdef SQLITE_DEBUG
5583 {
5589 }
5590 }
5591 #endif
5592 }
5594 /* Analyze all of the subexpressions. */
5599 /* Special case: WHERE terms that do not refer to any tables in the join
5600 ** (constant expressions). Evaluate each such term, and jump over all the
5601 ** generated code if the result is not true.
5602 **
5603 ** Do not do this if the expression contains non-deterministic functions
5604 ** that are not within a sub-select. This is not strictly required, but
5605 ** preserves SQLite's legacy behaviour in the following two cases:
5606 **
5607 ** FROM ... WHERE random()>0; -- eval random() once per row
5608 ** FROM ... WHERE (SELECT random())>0; -- eval random() once overall
5609 */
5616 }
5617 }
5621 /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via
5622 ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */
5626 /* The DISTINCT marking is pointless. Ignore it. */
5629 /* Try to ORDER BY the result set to make distinct processing easier */
5632 }
5633 }
5635 /* Construct the WhereLoop objects */
5636 #if defined(WHERETRACE_ENABLED)
5641 }
5644 Select sSelect;
5652 }
5653 }
5657 }
5658 #endif
5664 #ifdef SQLITE_ENABLE_STAT4
5665 /* If one or more WhereTerm.truthProb values were used in estimating
5666 ** loop parameters, but then those truthProb values were subsequently
5667 ** changed based on STAT4 information while computing subsequent loops,
5668 ** then we need to rerun the whole loop building process so that all
5669 ** loops will be built using the revised truthProb values. */
5679 }
5682 }
5683 #endif
5691 }
5692 }
5695 }
5698 }
5700 #ifdef WHERETRACE_ENABLED
5705 }
5710 }
5714 }
5718 }
5719 }
5723 }
5724 }
5725 #endif
5727 /* Attempt to omit tables from a join that do not affect the result.
5728 ** See the comment on whereOmitNoopJoin() for further information.
5729 **
5730 ** This query optimization is factored out into a separate "no-inline"
5731 ** procedure to keep the sqlite3WhereBegin() procedure from becoming
5732 ** too large. If sqlite3WhereBegin() becomes too large, that prevents
5733 ** some C-compiler optimizers from in-lining the
5734 ** sqlite3WhereCodeOneLoopStart() procedure, and it is important to
5735 ** in-line sqlite3WhereCodeOneLoopStart() for performance reasons.
5736 */
5742 ){
5746 }
5748 /* Check to see if there are any SEARCH loops that might benefit from
5749 ** using a Bloom filter.
5750 */
5753 ){
5755 }
5757 #if defined(WHERETRACE_ENABLED)
5761 }
5763 #endif
5766 /* If the caller is an UPDATE or DELETE statement that is requesting
5767 ** to use a one-pass algorithm, determine if this is appropriate.
5768 **
5769 ** A one-pass approach can be used if the caller has requested one
5770 ** and either (a) the scan visits at most one row or (b) each
5771 ** of the following are true:
5772 **
5773 ** * the caller has indicated that a one-pass approach can be used
5774 ** with multiple rows (by setting WHERE_ONEPASS_MULTIROW), and
5775 ** * the table is not a virtual table, and
5776 ** * either the scan does not use the OR optimization or the caller
5777 ** is a DELETE operation (WHERE_DUPLICATES_OK is only specified
5778 ** for DELETE).
5779 **
5780 ** The last qualification is because an UPDATE statement uses
5781 ** WhereInfo.aiCurOnePass[1] to determine whether or not it really can
5782 ** use a one-pass approach, and this is not set accurately for scans
5783 ** that use the OR optimization.
5784 */
5794 )){
5799 }
5801 }
5802 }
5803 }
5805 /* Open all tables in the pTabList and any indices selected for
5806 ** searching those tables.
5807 */
5818 /* Do nothing */
5820 #ifndef SQLITE_OMIT_VIRTUALTABLE
5826 /* noop */
5828 #endif
5832 ){
5837 };
5846 ){
5847 /* If we know that only a prefix of the record will be used,
5848 ** it is advantageous to reduce the "column count" field in
5849 ** the P4 operand of the OP_OpenRead/Write opcode. */
5855 }
5856 #ifdef SQLITE_ENABLE_CURSOR_HINTS
5860 #endif
5861 {
5863 }
5864 #ifdef SQLITE_ENABLE_COLUMN_USED_MASK
5867 #endif
5870 }
5875 /* iAuxArg is always set to a positive value if ONEPASS is possible */
5879 ){
5880 /* This is one term of an OR-optimization using the PRIMARY KEY of a
5881 ** WITHOUT ROWID table. No need for a separate index */
5889 iIndexCur++;
5891 }
5899 }
5913 ){
5915 }
5917 #ifdef SQLITE_ENABLE_COLUMN_USED_MASK
5918 {
5927 }
5930 }
5932 }
5933 }
5937 ){
5953 }
5958 }
5960 /* The nature of RIGHT JOIN processing is such that it messes up
5961 ** the output order. So omit any ORDER BY/GROUP BY elimination
5962 ** optimizations. We need to do an actual sort for RIGHT JOIN. */
5965 }
5966 }
5970 /* Generate the code to do the search. Each iteration of the for
5971 ** loop below generates code for a single nested loop of the VM
5972 ** program.
5973 */
5989 }
5990 }
5993 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
5996 #endif
5999 }
6001 }
6004 );
6010 }
6011 }
6013 /* Done. */
6018 /* Jump here if malloc fails */
6019 whereBeginError:
6025 }
6027 }
6029 /*
6030 ** Part of sqlite3WhereEnd() will rewrite opcodes to reference the
6031 ** index rather than the main table. In SQLITE_DEBUG mode, we want
6032 ** to trace those changes if PRAGMA vdbe_addoptrace=on. This routine
6033 ** does that.
6034 */
6035 #ifndef SQLITE_DEBUG
6037 #else
6038 # define OpcodeRewriteTrace(D,K,P) sqlite3WhereOpcodeRewriteTrace(D,K,P)
6042 VdbeOp *pOp
6043 ){
6046 }
6047 #endif
6049 #ifdef SQLITE_DEBUG
6050 /*
6051 ** Return true if cursor iCur is opened by instruction k of the
6052 ** bytecode. Used inside of assert() only.
6053 */
6064 }
6066 }
6069 /*
6070 ** Generate the end of the WHERE loop. See comments on
6071 ** sqlite3WhereBegin() for additional information.
6072 */
6084 /* Generate loop termination code.
6085 */
6091 /* Terminate the subroutine that forms the interior of the loop of
6092 ** the RIGHT JOIN table */
6099 nRJ++;
6100 }
6103 #ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT
6113 ){
6118 }
6125 }
6127 /* The common case: Advance to the next row */
6139 }
6140 #ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT
6142 #endif
6145 }
6160 /* For LEFT JOIN queries, cursor pIn->iCur may not have been
6161 ** opened yet. This occurs for WHERE clauses such as
6162 ** "a = ? AND b IN (...)", where the index is on (a, b). If
6163 ** the RHS of the (a=?) is NULL, then the "b IN (...)" may
6164 ** never have been coded, but the body of the loop run to
6165 ** return the null-row. So, if the cursor is not open yet,
6166 ** jump over the OP_Next or OP_Prev instruction about to
6167 ** be coded. */
6171 }
6177 /* Retarget the OP_IsNull against the left operand of IN so
6178 ** it jumps past the OP_IfNoHope. This is because the
6179 ** OP_IsNull also bypasses the OP_Affinity opcode that is
6180 ** required by OP_IfNoHope. */
6182 }
6183 }
6188 }
6190 }
6191 }
6196 }
6202 }
6203 #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
6208 }
6209 #endif
6217 }
6220 ){
6226 }
6228 }
6233 }
6235 }
6238 }
6251 /* Do RIGHT JOIN processing. Generate code that will output the
6252 ** unmatched rows of the right operand of the RIGHT JOIN with
6253 ** all of the columns of the left operand set to NULL.
6254 */
6258 }
6260 /* For a co-routine, change all OP_Column references to the table of
6261 ** the co-routine into OP_Copy of result contained in a register.
6262 ** OP_Rowid becomes OP_Null.
6263 */
6269 }
6271 /* If this scan uses an index, make VDBE code substitutions to read data
6272 ** from the index instead of from the table where possible. In some cases
6273 ** this optimization prevents the table from ever being read, which can
6274 ** yield a significant performance boost.
6275 **
6276 ** Calls to the code generator in between sqlite3WhereBegin and
6277 ** sqlite3WhereEnd will have created code that references the table
6278 ** directly. This loop scans all that code looking for opcodes
6279 ** that reference the table and converts them into opcodes that
6280 ** reference the index.
6281 */
6286 }
6289 ){
6294 }
6296 #ifdef SQLITE_DEBUG
6299 }
6300 /* Proof that the "+1" on the k value above is safe */
6305 #endif
6311 /* no-op */
6313 #ifdef SQLITE_ENABLE_OFFSET_SQL_FUNC
6315 #endif
6316 ){
6319 #ifdef SQLITE_ENABLE_OFFSET_SQL_FUNC
6321 /* Do not need to translate the column number */
6323 #endif
6331 }
6338 /* Unable to translate the table reference into an index
6339 ** reference. Verify that this is harmless - that the
6340 ** table being referenced really is open.
6341 */
6342 #ifdef SQLITE_ENABLE_OFFSET_SQL_FUNC
6346 );
6347 #else
6350 );
6351 #endif
6352 }
6360 }
6361 #ifdef SQLITE_DEBUG
6362 k++;
6363 #endif
6365 #ifdef SQLITE_DEBUG
6367 #endif
6368 }
6369 }
6371 /* The "break" point is here, just past the end of the outer loop.
6372 ** Set it.
6373 */
6376 /* Final cleanup
6377 */
6382 }