| blob | 5315520db49d0b722799ba26e1cb3c73cf341c66 |
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 */
35 };
37 /* Forward declaration of methods */
40 /*
41 ** Return the estimated number of output rows from a WHERE clause
42 */
45 }
47 /*
48 ** Return one of the WHERE_DISTINCT_xxxxx values to indicate how this
49 ** WHERE clause returns outputs for DISTINCT processing.
50 */
53 }
55 /*
56 ** Return the number of ORDER BY terms that are satisfied by the
57 ** WHERE clause. A return of 0 means that the output must be
58 ** completely sorted. A return equal to the number of ORDER BY
59 ** terms means that no sorting is needed at all. A return that
60 ** is positive but less than the number of ORDER BY terms means that
61 ** block sorting is required.
62 */
65 }
67 /*
68 ** In the ORDER BY LIMIT optimization, if the inner-most loop is known
69 ** to emit rows in increasing order, and if the last row emitted by the
70 ** inner-most loop did not fit within the sorter, then we can skip all
71 ** subsequent rows for the current iteration of the inner loop (because they
72 ** will not fit in the sorter either) and continue with the second inner
73 ** loop - the loop immediately outside the inner-most.
74 **
75 ** When a row does not fit in the sorter (because the sorter already
76 ** holds LIMIT+OFFSET rows that are smaller), then a jump is made to the
77 ** label returned by this function.
78 **
79 ** If the ORDER BY LIMIT optimization applies, the jump destination should
80 ** be the continuation for the second-inner-most loop. If the ORDER BY
81 ** LIMIT optimization does not apply, then the jump destination should
82 ** be the continuation for the inner-most loop.
83 **
84 ** It is always safe for this routine to return the continuation of the
85 ** inner-most loop, in the sense that a correct answer will result.
86 ** Returning the continuation the second inner loop is an optimization
87 ** that might make the code run a little faster, but should not change
88 ** the final answer.
89 */
93 /* The ORDER BY LIMIT optimization does not apply. Jump to the
94 ** continuation of the inner-most loop. */
96 }
100 }
102 /*
103 ** While generating code for the min/max optimization, after handling
104 ** the aggregate-step call to min() or max(), check to see if any
105 ** additional looping is required. If the output order is such that
106 ** we are certain that the correct answer has already been found, then
107 ** code an OP_Goto to by pass subsequent processing.
108 **
109 ** Any extra OP_Goto that is coded here is an optimization. The
110 ** correct answer should be obtained regardless. This OP_Goto just
111 ** makes the answer appear faster.
112 */
123 }
124 }
126 }
128 /*
129 ** Return the VDBE address or label to jump to in order to continue
130 ** immediately with the next row of a WHERE clause.
131 */
135 }
137 /*
138 ** Return the VDBE address or label to jump to in order to break
139 ** out of a WHERE loop.
140 */
143 }
145 /*
146 ** Return ONEPASS_OFF (0) if an UPDATE or DELETE statement is unable to
147 ** operate directly on the rowids returned by a WHERE clause. Return
148 ** ONEPASS_SINGLE (1) if the statement can operation directly because only
149 ** a single row is to be changed. Return ONEPASS_MULTI (2) if the one-pass
150 ** optimization can be used on multiple
151 **
152 ** If the ONEPASS optimization is used (if this routine returns true)
153 ** then also write the indices of open cursors used by ONEPASS
154 ** into aiCur[0] and aiCur[1]. iaCur[0] gets the cursor of the data
155 ** table and iaCur[1] gets the cursor used by an auxiliary index.
156 ** Either value may be -1, indicating that cursor is not used.
157 ** Any cursors returned will have been opened for writing.
158 **
159 ** aiCur[0] and aiCur[1] both get -1 if the where-clause logic is
160 ** unable to use the ONEPASS optimization.
161 */
164 #ifdef WHERETRACE_ENABLED
169 }
170 #endif
172 }
174 /*
175 ** Return TRUE if the WHERE loop uses the OP_DeferredSeek opcode to move
176 ** the data cursor to the row selected by the index cursor.
177 */
180 }
182 /*
183 ** Move the content of pSrc into pDest
184 */
188 }
190 /*
191 ** Try to insert a new prerequisite/cost entry into the WhereOrSet pSet.
192 **
193 ** The new entry might overwrite an existing entry, or it might be
194 ** appended, or it might be discarded. Do whatever is the right thing
195 ** so that pSet keeps the N_OR_COST best entries seen so far.
196 */
201 LogEst nOut /* Number of outputs for the new entry */
202 ){
203 u16 i;
208 }
211 }
212 }
220 }
222 }
223 whereOrInsert_done:
228 }
230 /*
231 ** Return the bitmask for the given cursor number. Return 0 if
232 ** iCursor is not in the set.
233 */
240 }
241 }
243 }
245 /*
246 ** Create a new mask for cursor iCursor.
247 **
248 ** There is one cursor per table in the FROM clause. The number of
249 ** tables in the FROM clause is limited by a test early in the
250 ** sqlite3WhereBegin() routine. So we know that the pMaskSet->ix[]
251 ** array will never overflow.
252 */
256 }
258 /*
259 ** If the right-hand branch of the expression is a TK_COLUMN, then return
260 ** a pointer to the right-hand branch. Otherwise, return NULL.
261 */
266 }
268 }
270 /*
271 ** Advance to the next WhereTerm that matches according to the criteria
272 ** established when the pScan object was initialized by whereScanInit().
273 ** Return NULL if there are no more matching WhereTerms.
274 */
297 ){
301 ){
307 }
308 }
313 }
314 }
316 /* Verify the affinity and collating sequence match */
323 }
329 }
330 }
335 ){
338 }
341 #ifdef WHERETRACE_ENABLED
349 }
351 }
352 #endif
354 }
355 }
356 }
364 }
366 }
368 /*
369 ** This is whereScanInit() for the case of an index on an expression.
370 ** It is factored out into a separate tail-recursion subroutine so that
371 ** the normal whereScanInit() routine, which is a high-runner, does not
372 ** need to push registers onto the stack as part of its prologue.
373 */
377 }
379 /*
380 ** Initialize a WHERE clause scanner object. Return a pointer to the
381 ** first match. Return NULL if there are no matches.
382 **
383 ** The scanner will be searching the WHERE clause pWC. It will look
384 ** for terms of the form "X <op> <expr>" where X is column iColumn of table
385 ** iCur. Or if pIdx!=0 then X is column iColumn of index pIdx. pIdx
386 ** must be one of the indexes of table iCur.
387 **
388 ** The <op> must be one of the operators described by opMask.
389 **
390 ** If the search is for X and the WHERE clause contains terms of the
391 ** form X=Y then this routine might also return terms of the form
392 ** "Y <op> <expr>". The number of levels of transitivity is limited,
393 ** but is enough to handle most commonly occurring SQL statements.
394 **
395 ** If X is not the INTEGER PRIMARY KEY then X must be compatible with
396 ** index pIdx.
397 */
405 ){
429 }
432 }
435 }
437 /*
438 ** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
439 ** where X is a reference to the iColumn of table iCur or of index pIdx
440 ** if pIdx!=0 and <op> is one of the WO_xx operator codes specified by
441 ** the op parameter. Return a pointer to the term. Return 0 if not found.
442 **
443 ** If pIdx!=0 then it must be one of the indexes of table iCur.
444 ** Search for terms matching the iColumn-th column of pIdx
445 ** rather than the iColumn-th column of table iCur.
446 **
447 ** The term returned might by Y=<expr> if there is another constraint in
448 ** the WHERE clause that specifies that X=Y. Any such constraints will be
449 ** identified by the WO_EQUIV bit in the pTerm->eOperator field. The
450 ** aiCur[]/iaColumn[] arrays hold X and all its equivalents. There are 11
451 ** slots in aiCur[]/aiColumn[] so that means we can look for X plus up to 10
452 ** other equivalent values. Hence a search for X will return <expr> if X=A1
453 ** and A1=A2 and A2=A3 and ... and A9=A10 and A10=<expr>.
454 **
455 ** If there are multiple terms in the WHERE clause of the form "X <op> <expr>"
456 ** then try for the one with no dependencies on <expr> - in other words where
457 ** <expr> is a constant expression of some kind. Only return entries of
458 ** the form "X <op> Y" where Y is a column in another table if no terms of
459 ** the form "X <op> <const-expr>" exist. If no terms with a constant RHS
460 ** exist, try to return a term that does not use WO_EQUIV.
461 */
469 ){
472 WhereScan scan;
481 }
483 }
485 }
487 }
489 /*
490 ** This function searches pList for an entry that matches the iCol-th column
491 ** of index pIdx.
492 **
493 ** If such an expression is found, its index in pList->a[] is returned. If
494 ** no expression is found, -1 is returned.
495 */
502 ){
512 ){
516 }
517 }
518 }
521 }
523 /*
524 ** Return TRUE if the iCol-th column of index pIdx is NOT NULL
525 */
539 }
540 }
542 /*
543 ** Return true if the DISTINCT expression-list passed as the third argument
544 ** is redundant.
545 **
546 ** A DISTINCT list is redundant if any subset of the columns in the
547 ** DISTINCT list are collectively unique and individually non-null.
548 */
554 ){
560 /* If there is more than one table or sub-select in the FROM clause of
561 ** this query, then it will not be possible to show that the DISTINCT
562 ** clause is redundant. */
567 /* If any of the expressions is an IPK column on table iBase, then return
568 ** true. Note: The (p->iTable==iBase) part of this test may be false if the
569 ** current SELECT is a correlated sub-query.
570 */
576 }
578 /* Loop through all indices on the table, checking each to see if it makes
579 ** the DISTINCT qualifier redundant. It does so if:
580 **
581 ** 1. The index is itself UNIQUE, and
582 **
583 ** 2. All of the columns in the index are either part of the pDistinct
584 ** list, or else the WHERE clause contains a term of the form "col=X",
585 ** where X is a constant value. The collation sequences of the
586 ** comparison and select-list expressions must match those of the index.
587 **
588 ** 3. All of those index columns for which the WHERE clause does not
589 ** contain a "col=X" term are subject to a NOT NULL constraint.
590 */
598 }
599 }
601 /* This index implies that the DISTINCT qualifier is redundant. */
603 }
604 }
607 }
610 /*
611 ** Estimate the logarithm of the input value to base 2.
612 */
615 }
617 /*
618 ** Convert OP_Column opcodes to OP_Copy in previously generated code.
619 **
620 ** This routine runs over generated VDBE code and translates OP_Column
621 ** opcodes into OP_Copy when the table is being accessed via co-routine
622 ** instead of via table lookup.
623 **
624 ** If the iAutoidxCur is not zero, then any OP_Rowid instructions on
625 ** cursor iTabCur are transformed into OP_Sequence opcode for the
626 ** iAutoidxCur cursor, in order to generate unique rowids for the
627 ** automatic index being generated.
628 */
635 ){
650 #ifdef SQLITE_ALLOW_ROWID_IN_VIEW
654 }
655 #endif
656 }
657 }
658 }
660 /*
661 ** Two routines for printing the content of an sqlite3_index_info
662 ** structure. Used for testing and debugging only. If neither
663 ** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines
664 ** are no-ops.
665 */
666 #if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(WHERETRACE_ENABLED)
672 i,
677 }
680 i,
683 }
684 }
690 i,
693 }
699 }
700 #else
701 #define whereTraceIndexInfoInputs(A)
702 #define whereTraceIndexInfoOutputs(A)
703 #endif
705 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
706 /*
707 ** Return TRUE if the WHERE clause term pTerm is of a form where it
708 ** could be used with an index to access pSrc, assuming an appropriate
709 ** index existed.
710 */
714 Bitmask notReady /* Tables in outer loops of the join */
715 ){
722 ){
723 /* Cannot use an IS term from the WHERE clause as an index driver for
724 ** the RHS of a LEFT JOIN. Such a term can only be used if it is from
725 ** the ON clause. */
727 }
734 }
735 #endif
738 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
739 /*
740 ** Generate code to construct the Index object for an automatic index
741 ** and to set up the WhereLevel object pLevel so that the code generator
742 ** makes use of the automatic index.
743 */
750 ){
775 /* Generate code to skip over the creation and initialization of the
776 ** transient index on 2nd and subsequent iterations of the loop. */
781 /* Count the number of columns that will be added to the index
782 ** and used to match WHERE clause constraints */
799 }
810 }
814 }
817 }
818 }
819 }
825 /* Count the number of additional columns needed to create a
826 ** covering index. A "covering index" is an index that contains all
827 ** columns that are needed by the query. With a covering index, the
828 ** original table never needs to be accessed. Automatic indices must
829 ** be a covering index because the index will not be updated if the
830 ** original table changes and the index and table cannot both be used
831 ** if they go out of sync.
832 */
839 }
842 }
844 /* Construct the Index object to describe this index */
865 n++;
866 }
867 }
868 }
871 /* Add additional columns needed to make the automatic index into
872 ** a covering index */
877 n++;
878 }
879 }
884 n++;
885 }
886 }
891 /* Create the automatic index */
898 /* Fill the automatic index with content */
909 }
914 }
918 );
933 }
937 /* Jump here when skipping the initialization */
940 end_auto_index_create:
942 }
945 #ifndef SQLITE_OMIT_VIRTUALTABLE
946 /*
947 ** Allocate and populate an sqlite3_index_info structure. It is the
948 ** responsibility of the caller to eventually release the structure
949 ** by passing the pointer returned by this function to sqlite3_free().
950 */
958 ){
970 /* Count the number of possible WHERE clause constraints referring
971 ** to this virtual table */
983 nTerm++;
984 }
986 /* If the ORDER BY clause contains only columns in the current
987 ** virtual table then allocate space for the aOrderBy part of
988 ** the sqlite3_index_info structure.
989 */
997 }
1000 }
1001 }
1003 /* Allocate the sqlite3_index_info structure
1004 */
1011 }
1023 u16 op;
1034 /* tag-20191211-002: WHERE-clause constraints are not useful to the
1035 ** right-hand table of a LEFT JOIN. See tag-20191211-001 for the
1036 ** equivalent restriction for ordinary tables. */
1039 ){
1041 }
1054 }
1057 /* The direct assignment in the previous line is possible only because
1058 ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical. The
1059 ** following asserts verify this fact. */
1069 ){
1074 }
1075 }
1077 j++;
1078 }
1084 }
1088 }
1090 /*
1091 ** The table object reference passed as the second argument to this function
1092 ** must represent a virtual table. This function invokes the xBestIndex()
1093 ** method of the virtual table with the sqlite3_index_info object that
1094 ** comes in as the 3rd argument to this function.
1095 **
1096 ** If an error occurs, pParse is populated with an error message and an
1097 ** appropriate error code is returned. A return of SQLITE_CONSTRAINT from
1098 ** xBestIndex is not considered an error. SQLITE_CONSTRAINT indicates that
1099 ** the current configuration of "unusable" flags in sqlite3_index_info can
1100 ** not result in a valid plan.
1101 **
1102 ** Whether or not an error is returned, it is the responsibility of the
1103 ** caller to eventually free p->idxStr if p->needToFreeIdxStr indicates
1104 ** that this is required.
1105 */
1121 }
1122 }
1126 }
1129 #ifdef SQLITE_ENABLE_STAT4
1130 /*
1131 ** Estimate the location of a particular key among all keys in an
1132 ** index. Store the results in aStat as follows:
1133 **
1134 ** aStat[0] Est. number of rows less than pRec
1135 ** aStat[1] Est. number of rows equal to pRec
1136 **
1137 ** Return the index of the sample that is the smallest sample that
1138 ** is greater than or equal to pRec. Note that this index is not an index
1139 ** into the aSample[] array - it is an index into a virtual set of samples
1140 ** based on the contents of aSample[] and the number of fields in record
1141 ** pRec.
1142 */
1149 ){
1160 #ifndef SQLITE_DEBUG
1162 #endif
1167 /* Do a binary search to find the first sample greater than or equal
1168 ** to pRec. If pRec contains a single field, the set of samples to search
1169 ** is simply the aSample[] array. If the samples in aSample[] contain more
1170 ** than one fields, all fields following the first are ignored.
1171 **
1172 ** If pRec contains N fields, where N is more than one, then as well as the
1173 ** samples in aSample[] (truncated to N fields), the search also has to
1174 ** consider prefixes of those samples. For example, if the set of samples
1175 ** in aSample is:
1176 **
1177 ** aSample[0] = (a, 5)
1178 ** aSample[1] = (a, 10)
1179 ** aSample[2] = (b, 5)
1180 ** aSample[3] = (c, 100)
1181 ** aSample[4] = (c, 105)
1182 **
1183 ** Then the search space should ideally be the samples above and the
1184 ** unique prefixes [a], [b] and [c]. But since that is hard to organize,
1185 ** the code actually searches this set:
1186 **
1187 ** 0: (a)
1188 ** 1: (a, 5)
1189 ** 2: (a, 10)
1190 ** 3: (a, 10)
1191 ** 4: (b)
1192 ** 5: (b, 5)
1193 ** 6: (c)
1194 ** 7: (c, 100)
1195 ** 8: (c, 105)
1196 ** 9: (c, 105)
1197 **
1198 ** For each sample in the aSample[] array, N samples are present in the
1199 ** effective sample array. In the above, samples 0 and 1 are based on
1200 ** sample aSample[0]. Samples 2 and 3 on aSample[1] etc.
1201 **
1202 ** Often, sample i of each block of N effective samples has (i+1) fields.
1203 ** Except, each sample may be extended to ensure that it is greater than or
1204 ** equal to the previous sample in the array. For example, in the above,
1205 ** sample 2 is the first sample of a block of N samples, so at first it
1206 ** appears that it should be 1 field in size. However, that would make it
1207 ** smaller than sample 1, so the binary search would not work. As a result,
1208 ** it is extended to two fields. The duplicates that this creates do not
1209 ** cause any problems.
1210 */
1221 /* The proposed effective sample is a prefix of sample aSample[iSamp].
1222 ** Specifically, the shortest prefix of at least (1 + iTest%nField)
1223 ** fields that is greater than the previous effective sample. */
1226 }
1229 }
1243 }
1247 #ifdef SQLITE_DEBUG
1248 /* The following assert statements check that the binary search code
1249 ** above found the right answer. This block serves no purpose other
1250 ** than to invoke the asserts. */
1253 /* If (res==0) is true, then pRec must be equal to sample i. */
1259 );
1261 /* Unless i==pIdx->nSample, indicating that pRec is larger than
1262 ** all samples in the aSample[] array, pRec must be smaller than the
1263 ** (iCol+1) field prefix of sample i. */
1270 /* if i==0 and iCol==0, then record pRec is smaller than all samples
1271 ** in the aSample[] array. Otherwise, if (iCol>0) then pRec must
1272 ** be greater than or equal to the (iCol) field prefix of sample i.
1273 ** If (i>0), then pRec must also be greater than sample (i-1). */
1278 }
1283 }
1284 }
1285 }
1289 /* Record pRec is equal to sample i */
1294 /* At this point, the (iCol+1) field prefix of aSample[i] is the first
1295 ** sample that is greater than pRec. Or, if i==pIdx->nSample then pRec
1296 ** is larger than all samples in the array. */
1302 }
1308 }
1313 }
1316 }
1318 /* Restore the pRec->nField value before returning. */
1321 }
1324 /*
1325 ** If it is not NULL, pTerm is a term that provides an upper or lower
1326 ** bound on a range scan. Without considering pTerm, it is estimated
1327 ** that the scan will visit nNew rows. This function returns the number
1328 ** estimated to be visited after taking pTerm into account.
1329 **
1330 ** If the user explicitly specified a likelihood() value for this term,
1331 ** then the return value is the likelihood multiplied by the number of
1332 ** input rows. Otherwise, this function assumes that an "IS NOT NULL" term
1333 ** has a likelihood of 0.50, and any other term a likelihood of 0.25.
1334 */
1342 }
1343 }
1345 }
1348 #ifdef SQLITE_ENABLE_STAT4
1349 /*
1350 ** Return the affinity for a single column of an index.
1351 */
1356 }
1359 }
1360 #endif
1363 #ifdef SQLITE_ENABLE_STAT4
1364 /*
1365 ** This function is called to estimate the number of rows visited by a
1366 ** range-scan on a skip-scan index. For example:
1367 **
1368 ** CREATE INDEX i1 ON t1(a, b, c);
1369 ** SELECT * FROM t1 WHERE a=? AND c BETWEEN ? AND ?;
1370 **
1371 ** Value pLoop->nOut is currently set to the estimated number of rows
1372 ** visited for scanning (a=? AND b=?). This function reduces that estimate
1373 ** by some factor to account for the (c BETWEEN ? AND ?) expression based
1374 ** on the stat4 data for the index. this scan will be peformed multiple
1375 ** times (once for each (a,b) combination that matches a=?) is dealt with
1376 ** by the caller.
1377 **
1378 ** It does this by scanning through all stat4 samples, comparing values
1379 ** extracted from pLower and pUpper with the corresponding column in each
1380 ** sample. If L and U are the number of samples found to be less than or
1381 ** equal to the values extracted from pLower and pUpper respectively, and
1382 ** N is the total number of samples, the pLoop->nOut value is adjusted
1383 ** as follows:
1384 **
1385 ** nOut = nOut * ( min(U - L, 1) / N )
1386 **
1387 ** If pLower is NULL, or a value cannot be extracted from the term, L is
1388 ** set to zero. If pUpper is NULL, or a value cannot be extracted from it,
1389 ** U is set to N.
1390 **
1391 ** Normally, this function sets *pbDone to 1 before returning. However,
1392 ** if no value can be extracted from either pLower or pUpper (and so the
1393 ** estimate of the number of rows delivered remains unchanged), *pbDone
1394 ** is left as is.
1395 **
1396 ** If an error occurs, an SQLite error code is returned. Otherwise,
1397 ** SQLITE_OK.
1398 */
1405 ){
1423 }
1427 }
1437 }
1441 }
1442 }
1446 /* If there is both an upper and lower bound specified, and the
1447 ** comparisons indicate that they are close together, use the fallback
1448 ** method (assume that the scan visits 1/64 of the rows) for estimating
1449 ** the number of rows visited. Otherwise, estimate the number of rows
1450 ** using the method described in the header comment for this function. */
1457 }
1461 }
1468 }
1471 /*
1472 ** This function is used to estimate the number of rows that will be visited
1473 ** by scanning an index for a range of values. The range may have an upper
1474 ** bound, a lower bound, or both. The WHERE clause terms that set the upper
1475 ** and lower bounds are represented by pLower and pUpper respectively. For
1476 ** example, assuming that index p is on t1(a):
1477 **
1478 ** ... FROM t1 WHERE a > ? AND a < ? ...
1479 ** |_____| |_____|
1480 ** | |
1481 ** pLower pUpper
1482 **
1483 ** If either of the upper or lower bound is not present, then NULL is passed in
1484 ** place of the corresponding WhereTerm.
1485 **
1486 ** The value in (pBuilder->pNew->u.btree.nEq) is the number of the index
1487 ** column subject to the range constraint. Or, equivalently, the number of
1488 ** equality constraints optimized by the proposed index scan. For example,
1489 ** assuming index p is on t1(a, b), and the SQL query is:
1490 **
1491 ** ... FROM t1 WHERE a = ? AND b > ? AND b < ? ...
1492 **
1493 ** then nEq is set to 1 (as the range restricted column, b, is the second
1494 ** left-most column of the index). Or, if the query is:
1495 **
1496 ** ... FROM t1 WHERE a > ? AND a < ? ...
1497 **
1498 ** then nEq is set to 0.
1499 **
1500 ** When this function is called, *pnOut is set to the sqlite3LogEst() of the
1501 ** number of rows that the index scan is expected to visit without
1502 ** considering the range constraints. If nEq is 0, then *pnOut is the number of
1503 ** rows in the index. Assuming no error occurs, *pnOut is adjusted (reduced)
1504 ** to account for the range constraints pLower and pUpper.
1505 **
1506 ** In the absence of sqlite_stat4 ANALYZE data, or if such data cannot be
1507 ** used, a single range inequality reduces the search space by a factor of 4.
1508 ** and a pair of constraints (x>? AND x<?) reduces the expected number of
1509 ** rows visited by a factor of 64.
1510 */
1517 ){
1520 LogEst nNew;
1522 #ifdef SQLITE_ENABLE_STAT4
1528 ){
1535 /* Variable iLower will be set to the estimate of the number of rows in
1536 ** the index that are less than the lower bound of the range query. The
1537 ** lower bound being the concatenation of $P and $L, where $P is the
1538 ** key-prefix formed by the nEq values matched against the nEq left-most
1539 ** columns of the index, and $L is the value in pLower.
1540 **
1541 ** Or, if pLower is NULL or $L cannot be extracted from it (because it
1542 ** is not a simple variable or literal value), the lower bound of the
1543 ** range is $P. Due to a quirk in the way whereKeyStats() works, even
1544 ** if $L is available, whereKeyStats() is called for both ($P) and
1545 ** ($P:$L) and the larger of the two returned values is used.
1546 **
1547 ** Similarly, iUpper is to be set to the estimate of the number of rows
1548 ** less than the upper bound of the range query. Where the upper bound
1549 ** is either ($P) or ($P:$U). Again, even if $U is available, both values
1550 ** of iUpper are requested of whereKeyStats() and the smaller used.
1551 **
1552 ** The number of rows between the two bounds is then just iUpper-iLower.
1553 */
1562 }
1563 /* Determine iLower and iUpper using ($P) only. */
1568 /* Note: this call could be optimized away - since the same values must
1569 ** have been requested when testing key $P in whereEqualScanEst(). */
1573 }
1579 /* The roles of pLower and pUpper are swapped for a DESC index */
1582 }
1584 /* If possible, improve on the iLower estimate using ($P:$L). */
1590 tRowcnt iNew;
1596 nOut--;
1598 }
1599 }
1601 /* If possible, improve on the iUpper estimate using ($P:$U). */
1607 tRowcnt iNew;
1613 nOut--;
1615 }
1616 }
1622 /* TUNING: If both iUpper and iLower are derived from the same
1623 ** sample, then assume they are 4x more selective. This brings
1624 ** the estimated selectivity more in line with what it would be
1625 ** if estimated without the use of STAT4 tables. */
1629 }
1632 }
1635 }
1640 }
1641 }
1642 #else
1646 #endif
1651 /* TUNING: If there is both an upper and lower limit and neither limit
1652 ** has an application-defined likelihood(), assume the range is
1653 ** reduced by an additional 75%. This means that, by default, an open-ended
1654 ** range query (e.g. col > ?) is assumed to match 1/4 of the rows in the
1655 ** index. While a closed range (e.g. col BETWEEN ? AND ?) is estimated to
1656 ** match 1/64 of the index. */
1659 }
1664 #if defined(WHERETRACE_ENABLED)
1668 }
1669 #endif
1672 }
1674 #ifdef SQLITE_ENABLE_STAT4
1675 /*
1676 ** Estimate the number of rows that will be returned based on
1677 ** an equality constraint x=VALUE and where that VALUE occurs in
1678 ** the histogram data. This only works when x is the left-most
1679 ** column of an index and sqlite_stat4 histogram data is available
1680 ** for that index. When pExpr==NULL that means the constraint is
1681 ** "x IS NULL" instead of "x=VALUE".
1682 **
1683 ** Write the estimated row count into *pnRow and return SQLITE_OK.
1684 ** If unable to make an estimate, leave *pnRow unchanged and return
1685 ** non-zero.
1686 **
1687 ** This routine can fail if it is unable to load a collating sequence
1688 ** required for string comparison, or if unable to allocate memory
1689 ** for a UTF conversion required for comparison. The error is stored
1690 ** in the pParse structure.
1691 */
1697 ){
1711 /* If values are not available for all fields of the index to the left
1712 ** of this one, no estimate can be made. Return SQLITE_NOTFOUND. */
1715 }
1717 /* This is an optimization only. The call to sqlite3Stat4ProbeSetValue()
1718 ** below would return the same value. */
1722 }
1736 }
1739 #ifdef SQLITE_ENABLE_STAT4
1740 /*
1741 ** Estimate the number of rows that will be returned based on
1742 ** an IN constraint where the right-hand side of the IN operator
1743 ** is a list of values. Example:
1744 **
1745 ** WHERE x IN (1,2,3,4)
1746 **
1747 ** Write the estimated row count into *pnRow and return SQLITE_OK.
1748 ** If unable to make an estimate, leave *pnRow unchanged and return
1749 ** non-zero.
1750 **
1751 ** This routine can fail if it is unable to load a collating sequence
1752 ** required for string comparison, or if unable to allocate memory
1753 ** for a UTF conversion required for comparison. The error is stored
1754 ** in the pParse structure.
1755 */
1761 ){
1776 }
1782 }
1785 }
1789 #ifdef WHERETRACE_ENABLED
1790 /*
1791 ** Print the content of a WhereTerm object
1792 */
1812 }
1816 /* The 0x10000 .wheretrace flag causes extra information to be
1817 ** shown about each Term */
1821 }
1824 }
1827 }
1830 }
1831 }
1832 #endif
1834 #ifdef WHERETRACE_ENABLED
1835 /*
1836 ** Show the complete content of a WhereClause
1837 */
1842 }
1843 }
1844 #endif
1846 #ifdef WHERETRACE_ENABLED
1847 /*
1848 ** Print a WhereLoop object for debugging purposes
1849 */
1867 }
1871 }
1879 }
1882 }
1887 }
1893 }
1894 }
1895 }
1896 #endif
1898 /*
1899 ** Convert bulk memory into a valid WhereLoop that can be passed
1900 ** to whereLoopClear harmlessly.
1901 */
1907 }
1909 /*
1910 ** Clear the WhereLoop.u union. Leave WhereLoop.pLTerm intact.
1911 */
1922 }
1923 }
1924 }
1926 /*
1927 ** Deallocate internal memory used by a WhereLoop object
1928 */
1933 }
1935 /*
1936 ** Increase the memory allocation for pLoop->aLTerm[] to be at least n.
1937 */
1949 }
1951 /*
1952 ** Transfer content from the second pLoop into the first.
1953 */
1959 }
1966 }
1968 }
1970 /*
1971 ** Delete a WhereLoop object
1972 */
1976 }
1978 /*
1979 ** Free a WhereInfo structure
1980 */
1988 }
1989 }
1995 }
1998 }
2000 /* Undo all Expr node modifications
2001 */
2008 }
2009 }
2011 /*
2012 ** Return TRUE if all of the following are true:
2013 **
2014 ** (1) X has the same or lower cost that Y
2015 ** (2) X uses fewer WHERE clause terms than Y
2016 ** (3) Every WHERE clause term used by X is also used by Y
2017 ** (4) X skips at least as many columns as Y
2018 ** (5) If X is a covering index, than Y is too
2019 **
2020 ** Conditions (2) and (3) mean that X is a "proper subset" of Y.
2021 ** If X is a proper subset of Y then Y is a better choice and ought
2022 ** to have a lower cost. This routine returns TRUE when that cost
2023 ** relationship is inverted and needs to be adjusted. Constraint (4)
2024 ** was added because if X uses skip-scan less than Y it still might
2025 ** deserve a lower cost even if it is a proper subset of Y. Constraint (5)
2026 ** was added because a covering index probably deserves to have a lower cost
2027 ** than a non-covering index even if it is a proper subset.
2028 */
2032 ){
2036 }
2041 }
2046 }
2048 }
2052 }
2054 }
2056 /*
2057 ** Try to adjust the cost of WhereLoop pTemplate upwards or downwards so
2058 ** that:
2059 **
2060 ** (1) pTemplate costs less than any other WhereLoops that are a proper
2061 ** subset of pTemplate
2062 **
2063 ** (2) pTemplate costs more than any other WhereLoops for which pTemplate
2064 ** is a proper subset.
2065 **
2066 ** To say "WhereLoop X is a proper subset of Y" means that X uses fewer
2067 ** WHERE clause terms than Y and that every WHERE clause term used by X is
2068 ** also used by Y.
2069 */
2076 /* Adjust pTemplate cost downward so that it is cheaper than its
2077 ** subset p. */
2083 /* Adjust pTemplate cost upward so that it is costlier than p since
2084 ** pTemplate is a proper subset of p */
2089 }
2090 }
2091 }
2093 /*
2094 ** Search the list of WhereLoops in *ppPrev looking for one that can be
2095 ** replaced by pTemplate.
2096 **
2097 ** Return NULL if pTemplate does not belong on the WhereLoop list.
2098 ** In other words if pTemplate ought to be dropped from further consideration.
2099 **
2100 ** If pX is a WhereLoop that pTemplate can replace, then return the
2101 ** link that points to pX.
2102 **
2103 ** If pTemplate cannot replace any existing element of the list but needs
2104 ** to be added to the list as a new entry, then return a pointer to the
2105 ** tail of the list.
2106 */
2110 ){
2114 /* If either the iTab or iSortIdx values for two WhereLoop are different
2115 ** then those WhereLoops need to be considered separately. Neither is
2116 ** a candidate to replace the other. */
2118 }
2119 /* In the current implementation, the rSetup value is either zero
2120 ** or the cost of building an automatic index (NlogN) and the NlogN
2121 ** is the same for compatible WhereLoops. */
2125 /* whereLoopAddBtree() always generates and inserts the automatic index
2126 ** case first. Hence compatible candidate WhereLoops never have a larger
2127 ** rSetup. Call this SETUP-INVARIANT */
2130 /* Any loop using an appliation-defined index (or PRIMARY KEY or
2131 ** UNIQUE constraint) with one or more == constraints is better
2132 ** than an automatic index. Unless it is a skip-scan. */
2138 ){
2140 }
2142 /* If existing WhereLoop p is better than pTemplate, pTemplate can be
2143 ** discarded. WhereLoop p is better if:
2144 ** (1) p has no more dependencies than pTemplate, and
2145 ** (2) p has an equal or lower cost than pTemplate
2146 */
2151 ){
2153 }
2155 /* If pTemplate is always better than p, then cause p to be overwritten
2156 ** with pTemplate. pTemplate is better than p if:
2157 ** (1) pTemplate has no more dependences than p, and
2158 ** (2) pTemplate has an equal or lower cost than p.
2159 */
2163 ){
2166 }
2167 }
2169 }
2171 /*
2172 ** Insert or replace a WhereLoop entry using the template supplied.
2173 **
2174 ** An existing WhereLoop entry might be overwritten if the new template
2175 ** is better and has fewer dependencies. Or the template will be ignored
2176 ** and no insert will occur if an existing WhereLoop is faster and has
2177 ** fewer dependencies than the template. Otherwise a new WhereLoop is
2178 ** added based on the template.
2179 **
2180 ** If pBuilder->pOrSet is not NULL then we care about only the
2181 ** prerequisites and rRun and nOut costs of the N best loops. That
2182 ** information is gathered in the pBuilder->pOrSet object. This special
2183 ** processing mode is used only for OR clause processing.
2184 **
2185 ** When accumulating multiple loops (when pBuilder->pOrSet is NULL) we
2186 ** still might overwrite similar loops with the new template if the
2187 ** new template is better. Loops may be overwritten if the following
2188 ** conditions are met:
2189 **
2190 ** (1) They have the same iTab.
2191 ** (2) They have the same iSortIdx.
2192 ** (3) The template has same or fewer dependencies than the current loop
2193 ** (4) The template has the same or lower cost than the current loop
2194 */
2201 /* Stop the search once we hit the query planner search limit */
2206 }
2211 /* If pBuilder->pOrSet is defined, then only keep track of the costs
2212 ** and prereqs.
2213 */
2216 #if WHERETRACE_ENABLED
2219 #endif
2226 }
2227 #endif
2228 }
2230 }
2232 /* Look for an existing WhereLoop to replace with pTemplate
2233 */
2237 /* There already exists a WhereLoop on the list that is better
2238 ** than pTemplate, so just ignore pTemplate */
2243 }
2244 #endif
2248 }
2250 /* If we reach this point it means that either p[] should be overwritten
2251 ** with pTemplate[] if p[] exists, or if p==NULL then allocate a new
2252 ** WhereLoop and insert it.
2253 */
2262 }
2264 }
2265 #endif
2267 /* Allocate a new WhereLoop to add to the end of the list */
2273 /* We will be overwriting WhereLoop p[]. But before we do, first
2274 ** go through the rest of the list and delete any other entries besides
2275 ** p[] that are also supplated by pTemplate */
2288 }
2289 #endif
2291 }
2292 }
2298 }
2299 }
2301 }
2303 /*
2304 ** Adjust the WhereLoop.nOut value downward to account for terms of the
2305 ** WHERE clause that reference the loop but which are not used by an
2306 ** index.
2307 *
2308 ** For every WHERE clause term that is not used by the index
2309 ** and which has a truth probability assigned by one of the likelihood(),
2310 ** likely(), or unlikely() SQL functions, reduce the estimated number
2311 ** of output rows by the probability specified.
2312 **
2313 ** TUNING: For every WHERE clause term that is not used by the index
2314 ** and which does not have an assigned truth probability, heuristics
2315 ** described below are used to try to estimate the truth probability.
2316 ** TODO --> Perhaps this is something that could be improved by better
2317 ** table statistics.
2318 **
2319 ** Heuristic 1: Estimate the truth probability as 93.75%. The 93.75%
2320 ** value corresponds to -1 in LogEst notation, so this means decrement
2321 ** the WhereLoop.nOut field for every such WHERE clause term.
2322 **
2323 ** Heuristic 2: If there exists one or more WHERE clause terms of the
2324 ** form "x==EXPR" and EXPR is not a constant 0 or 1, then make sure the
2325 ** final output row estimate is no greater than 1/4 of the total number
2326 ** of rows in the table. In other words, assume that x==EXPR will filter
2327 ** out at least 3 out of 4 rows. If EXPR is -1 or 0 or 1, then maybe the
2328 ** "x" column is boolean or else -1 or 0 or 1 is a common default value
2329 ** on the "x" column and so in that case only cap the output row estimate
2330 ** at 1/2 instead of 1/4.
2331 */
2335 LogEst nRow /* Number of rows in the entire table */
2336 ){
2353 }
2356 /* If a truth probability is specified using the likelihood() hints,
2357 ** then use the probability provided by the application. */
2360 /* In the absence of explicit truth probabilities, use heuristics to
2361 ** guess a reasonable truth probability. */
2365 ){
2373 }
2377 }
2378 }
2379 }
2380 }
2381 }
2383 }
2385 /*
2386 ** Term pTerm is a vector range comparison operation. The first comparison
2387 ** in the vector can be optimized using column nEq of the index. This
2388 ** function returns the total number of vector elements that can be used
2389 ** as part of the range comparison.
2390 **
2391 ** For example, if the query is:
2392 **
2393 ** WHERE a = ? AND (b, c, d) > (?, ?, ?)
2394 **
2395 ** and the index:
2396 **
2397 ** CREATE INDEX ... ON (a, b, c, d, e)
2398 **
2399 ** then this function would be invoked with nEq=1. The value returned in
2400 ** this case is 3.
2401 */
2408 ){
2414 /* Test if comparison i of pTerm is compatible with column (i+nEq)
2415 ** of the index. If not, exit the loop. */
2425 }
2427 /* Check that the LHS of the comparison is a column reference to
2428 ** the right column of the right source table. And that the sort
2429 ** order of the index column is the same as the sort order of the
2430 ** leftmost index column. */
2435 ){
2437 }
2447 }
2449 }
2451 /*
2452 ** Adjust the cost C by the costMult facter T. This only occurs if
2453 ** compiled with -DSQLITE_ENABLE_COSTMULT
2454 */
2455 #ifdef SQLITE_ENABLE_COSTMULT
2456 # define ApplyCostMultiplier(C,T) C += T
2457 #else
2458 # define ApplyCostMultiplier(C,T)
2459 #endif
2461 /*
2462 ** We have so far matched pBuilder->pNew->u.btree.nEq terms of the
2463 ** index pIndex. Try to match one more.
2464 **
2465 ** When this function is called, pBuilder->pNew->nOut contains the
2466 ** number of rows expected to be visited by filtering using the nEq
2467 ** terms only. If it is modified, this value is restored before this
2468 ** function returns.
2469 **
2470 ** If pProbe->idxType==SQLITE_IDXTYPE_IPK, that means pIndex is
2471 ** a fake index used for the INTEGER PRIMARY KEY.
2472 */
2477 LogEst nInMul /* log(Number of iterations due to IN) */
2478 ){
2512 }
2534 LogEst rCostIdx;
2537 #ifdef SQLITE_ENABLE_STAT4
2539 #endif
2542 ){
2544 }
2547 /* Do not allow the upper bound of a LIKE optimization range constraint
2548 ** to mix with a lower range bound from some other source */
2551 /* tag-20191211-001: Do not allow constraints from the WHERE clause to
2552 ** be used by the right table of a LEFT JOIN. Only constraints in the
2553 ** ON clause are allowed. See tag-20191211-002 for the vtab equivalent. */
2556 ){
2558 }
2564 }
2578 );
2583 /* "x IN (SELECT ...)": TUNING: the SELECT returns 25 rows */
2587 /* The expression may actually be of the form (x, y) IN (SELECT...).
2588 ** In this case there is a separate term for each of (x) and (y).
2589 ** However, the nIn multiplier should only be applied once, not once
2590 ** for each such term. The following loop checks that pTerm is the
2591 ** first such term in use, and sets nIn back to 0 if it is not. */
2594 }
2596 /* "x IN (value, value, ...)" */
2598 }
2601 /* Let:
2602 ** N = the total number of rows in the table
2603 ** K = the number of entries on the RHS of the IN operator
2604 ** M = the number of rows in the table that match terms to the
2605 ** to the left in the same index. If the IN operator is on
2606 ** the left-most index column, M==N.
2607 **
2608 ** Given the definitions above, it is better to omit the IN operator
2609 ** from the index lookup and instead do a scan of the M elements,
2610 ** testing each scanned row against the IN operator separately, if:
2611 **
2612 ** M*log(K) < K*log(N)
2613 **
2614 ** Our estimates for M, K, and N might be inaccurate, so we build in
2615 ** a safety margin of 2 (LogEst: 10) that favors using the IN operator
2616 ** with the index, as using an index has better worst-case behavior.
2617 ** If we do not have real sqlite_stat1 data, always prefer to use
2618 ** the index. Do not bother with this optimization on very small
2619 ** tables (less than 2 rows) as it is pointless in that case.
2620 */
2623 /* TUNING v----- 10 to bias toward indexed IN */
2642 }
2643 }
2651 ){
2654 ){
2658 }
2659 }
2669 );
2673 /* Range constraints that come from the LIKE optimization are
2674 ** always used in pairs. */
2683 }
2691 );
2695 }
2697 /* At this point pNew->nOut is set to the number of rows expected to
2698 ** be visited by the index scan before considering term pTerm, or the
2699 ** values of nIn and nInMul. In other words, assuming that all
2700 ** "x IN(...)" terms are replaced with "x = ?". This block updates
2701 ** the value of pNew->nOut to account for pTerm (but not nIn/nInMul). */
2704 /* Adjust nOut using stat4 data. Or, if there is no stat4
2705 ** data, using some other estimate. */
2718 #ifdef SQLITE_ENABLE_STAT4
2725 ){
2734 }
2740 /* TUNING: Mark terms as "low selectivity" if they seem likely
2741 ** to be true for half or more of the rows in the table.
2742 ** See tag-202002240-1 */
2744 ){
2750 }
2751 #endif
2754 /* If the term has previously been used with an assumption of
2755 ** higher selectivity, then set the flag to rerun the
2756 ** loop computations. */
2758 }
2759 }
2762 }
2763 }
2765 #endif
2766 {
2769 /* TUNING: If there is no likelihood() value, assume that a
2770 ** "col IS NULL" expression matches twice as many rows
2771 ** as (col=?). */
2773 }
2774 }
2775 }
2776 }
2778 /* Set rCostIdx to the cost of visiting selected rows in index. Add
2779 ** it to pNew->rRun, which is currently set to the cost of the index
2780 ** seek only. Then, if this is a non-covering index, add the cost of
2781 ** visiting the rows in the main table. */
2787 }
2800 }
2806 ){
2808 }
2810 #ifdef SQLITE_ENABLE_STAT4
2812 #endif
2813 }
2823 /* Consider using a skip-scan if there are no WHERE clause constraints
2824 ** available for the left-most terms of the index, and if the average
2825 ** number of repeats in the left-most terms is at least 18.
2826 **
2827 ** The magic number 18 is selected on the basis that scanning 17 rows
2828 ** is almost always quicker than an index seek (even though if the index
2829 ** contains fewer than 2^17 rows we assume otherwise in other parts of
2830 ** the code). And, even if it is not, it should not be too much slower.
2831 ** On the other hand, the extra seeks could end up being significantly
2832 ** more expensive. */
2842 ){
2843 LogEst nIter;
2850 /* TUNING: Because uncertainties in the estimates for skip-scan queries,
2851 ** add a 1.375 fudge factor to make skip-scan slightly less likely. */
2858 }
2863 }
2865 /*
2866 ** Return True if it is possible that pIndex might be useful in
2867 ** implementing the ORDER BY clause in pBuilder.
2868 **
2869 ** Return False if pBuilder does not contain an ORDER BY clause or
2870 ** if there is no way for pIndex to be useful in implementing that
2871 ** ORDER BY clause.
2872 */
2876 int iCursor
2877 ){
2891 }
2897 }
2898 }
2899 }
2900 }
2902 }
2904 /* Check to see if a partial index with pPartIndexWhere can be used
2905 ** in the current query. Return true if it can be and false if not.
2906 */
2912 ){
2919 }
2928 ){
2930 }
2931 }
2933 }
2935 /*
2936 ** Add all WhereLoop objects for a single table of the join where the table
2937 ** is identified by pBuilder->pNew->iTab. That table is guaranteed to be
2938 ** a b-tree table, not a virtual table.
2939 **
2940 ** The costs (WhereLoop.rRun) of the b-tree loops added by this function
2941 ** are calculated as follows:
2942 **
2943 ** For a full scan, assuming the table (or index) contains nRow rows:
2944 **
2945 ** cost = nRow * 3.0 // full-table scan
2946 ** cost = nRow * K // scan of covering index
2947 ** cost = nRow * (K+3.0) // scan of non-covering index
2948 **
2949 ** where K is a value between 1.1 and 3.0 set based on the relative
2950 ** estimated average size of the index and table records.
2951 **
2952 ** For an index scan, where nVisit is the number of index rows visited
2953 ** by the scan, and nSeek is the number of seek operations required on
2954 ** the index b-tree:
2955 **
2956 ** cost = nSeek * (log(nRow) + K * nVisit) // covering index
2957 ** cost = nSeek * (log(nRow) + (K+3.0) * nVisit) // non-covering index
2958 **
2959 ** Normally, nSeek is 1. nSeek values greater than 1 come about if the
2960 ** WHERE clause includes "x IN (....)" terms used in place of "x=?". Or when
2961 ** implicit "x IN (SELECT x FROM tbl)" terms are added for skip-scans.
2962 **
2963 ** The estimated values (nRow, nVisit, nSeek) often contain a large amount
2964 ** of uncertainty. For this reason, scoring is designed to pick plans that
2965 ** "do the least harm" if the estimates are inaccurate. For example, a
2966 ** log(nRow) factor is omitted from a non-covering index scan in order to
2967 ** bias the scoring in favor of using an index, since the worst-case
2968 ** performance of using an index is far better than the worst-case performance
2969 ** of a full table scan.
2970 */
2973 Bitmask mPrereq /* Extra prerequesites for using this table */
2974 ){
3000 /* An INDEXED BY clause specifies a particular index to use */
3005 /* There is no INDEXED BY clause. Create a fake Index object in local
3006 ** variable sPk to represent the rowid primary key index. Make this
3007 ** fake index the first in a chain of Index objects with all of the real
3008 ** indices to follow */
3023 /* The real indices of the table are only considered if the
3024 ** NOT INDEXED qualifier is omitted from the FROM clause */
3026 }
3028 }
3032 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
3033 /* Automatic indexes */
3042 ){
3043 /* Generate auto-index WhereLoops */
3054 /* TUNING: One-time cost for computing the automatic index is
3055 ** estimated to be X*N*log2(N) where N is the number of rows in
3056 ** the table being indexed and where X is 7 (LogEst=28) for normal
3057 ** tables or 0.5 (LogEst=-10) for views and subqueries. The value
3058 ** of X is smaller for views and subqueries so that the query planner
3059 ** will be more aggressive about generating automatic indexes for
3060 ** those objects, since there is no opportunity to add schema
3061 ** indexes on subqueries and views. */
3067 }
3070 /* TUNING: Each index lookup yields 20 rows in the table. This
3071 ** is more than the usual guess of 10 rows, since we have no way
3072 ** of knowing how selective the index will ultimately be. It would
3073 ** not be unreasonable to make this value much larger. */
3079 }
3080 }
3081 }
3084 /* Loop over all indices. If there was an INDEXED BY clause, then only
3085 ** consider index pProbe. */
3088 ){
3093 ){
3096 }
3111 /* The ONEPASS_DESIRED flags never occurs together with ORDER BY */
3114 /* Integer primary key index */
3117 /* Full table scan */
3119 /* TUNING: Cost of full table scan is 3.0*N. The 3.0 factor is an
3120 ** extra cost designed to discourage the use of full table scans,
3121 ** since index lookups have better worst-case performance if our
3122 ** stat guesses are wrong. Reduce the 3.0 penalty slightly
3123 ** (to 2.75) if we have valid STAT4 information for the table.
3124 ** At 2.75, a full table scan is preferred over using an index on
3125 ** a column with just two distinct values where each value has about
3126 ** an equal number of appearances. Without STAT4 data, we still want
3127 ** to use an index in that case, since the constraint might be for
3128 ** the scarcer of the two values, and in that case an index lookup is
3129 ** better.
3130 */
3131 #ifdef SQLITE_ENABLE_STAT4
3133 #else
3135 #endif
3142 Bitmask m;
3149 }
3151 /* Full scan via index */
3162 )
3163 ){
3166 /* The cost of visiting the index rows is N*K, where K is
3167 ** between 1.1 and 3.0, depending on the relative sizes of the
3168 ** index and table rows. */
3171 /* If this is a non-covering index scan, add in the cost of
3172 ** doing table lookups. The cost will be 3x the number of
3173 ** lookups. Take into account WHERE clause terms that can be
3174 ** satisfied using just the index, and that do not require a
3175 ** table lookup. */
3184 }
3185 /* pTerm can be evaluated using just the index. So reduce
3186 ** the expected number of table lookups accordingly */
3190 nLookup--;
3192 }
3193 }
3196 }
3202 }
3203 }
3208 /* If a non-unique index is used, or if a prefix of the key for
3209 ** unique index is used (making the index functionally non-unique)
3210 ** then the sqlite_stat1 data becomes important for scoring the
3211 ** plan */
3213 }
3214 #ifdef SQLITE_ENABLE_STAT4
3218 #endif
3219 }
3221 }
3223 #ifndef SQLITE_OMIT_VIRTUALTABLE
3225 /*
3226 ** Argument pIdxInfo is already populated with all constraints that may
3227 ** be used by the virtual table identified by pBuilder->pNew->iTab. This
3228 ** function marks a subset of those constraints usable, invokes the
3229 ** xBestIndex method and adds the returned plan to pBuilder.
3230 **
3231 ** A constraint is marked usable if:
3232 **
3233 ** * Argument mUsable indicates that its prerequisites are available, and
3234 **
3235 ** * It is not one of the operators specified in the mExclude mask passed
3236 ** as the fourth argument (which in practice is either WO_IN or 0).
3237 **
3238 ** Argument mPrereq is a mask of tables that must be scanned before the
3239 ** virtual table in question. These are added to the plans prerequisites
3240 ** before it is added to pBuilder.
3241 **
3242 ** Output parameter *pbIn is set to true if the plan added to pBuilder
3243 ** uses one or more WO_IN terms, or false otherwise.
3244 */
3253 ){
3269 /* Set the usable flag on the subset of constraints identified by
3270 ** arguments mUsable and mExclude. */
3277 ){
3279 }
3280 }
3282 /* Initialize the output fields of the sqlite3_index_info structure */
3293 /* Invoke the virtual table xBestIndex() method */
3297 /* If the xBestIndex method returns SQLITE_CONSTRAINT, that means
3298 ** that the particular combination of parameters provided is unusable.
3299 ** Make no entries in the loop table.
3300 */
3303 }
3305 }
3322 ){
3326 }
3343 }
3344 }
3346 /* A virtual table that is constrained by an IN clause may not
3347 ** consume the ORDER BY clause because (1) the order of IN terms
3348 ** is not necessarily related to the order of output terms and
3349 ** (2) Multiple outputs from a single IN value will not merge
3350 ** together. */
3354 }
3355 }
3356 }
3361 /* The non-zero argvIdx values must be contiguous. Raise an
3362 ** error if they are not */
3366 }
3367 }
3379 /* Set the WHERE_ONEROW flag if the xBestIndex() method indicated
3380 ** that the scan will visit at most one row. Clear it otherwise. */
3385 }
3390 }
3396 }
3398 /*
3399 ** If this function is invoked from within an xBestIndex() callback, it
3400 ** returns a pointer to a buffer containing the name of the collation
3401 ** sequence associated with element iCons of the sqlite3_index_info.aConstraint
3402 ** array. Or, if iCons is out of range or there is no active xBestIndex
3403 ** call, return NULL.
3404 */
3414 }
3416 }
3418 }
3420 /*
3421 ** Add all WhereLoop objects for a table of the join identified by
3422 ** pBuilder->pNew->iTab. That table is guaranteed to be a virtual table.
3423 **
3424 ** If there are no LEFT or CROSS JOIN joins in the query, both mPrereq and
3425 ** mUnusable are set to 0. Otherwise, mPrereq is a mask of all FROM clause
3426 ** entries that occur before the virtual table in the FROM clause and are
3427 ** separated from it by at least one LEFT or CROSS JOIN. Similarly, the
3428 ** mUnusable mask contains all FROM clause entries that occur after the
3429 ** virtual table and are separated from it by at least one LEFT or
3430 ** CROSS JOIN.
3431 **
3432 ** For example, if the query were:
3433 **
3434 ** ... FROM t1, t2 LEFT JOIN t3, t4, vt CROSS JOIN t5, t6;
3435 **
3436 ** then mPrereq corresponds to (t1, t2) and mUnusable to (t5, t6).
3437 **
3438 ** All the tables in mPrereq must be scanned before the current virtual
3439 ** table. So any terms for which all prerequisites are satisfied by
3440 ** mPrereq may be specified as "usable" in all calls to xBestIndex.
3441 ** Conversely, all tables in mUnusable must be scanned after the current
3442 ** virtual table, so any terms for which the prerequisites overlap with
3443 ** mUnusable should always be configured as "not-usable" for xBestIndex.
3444 */
3448 Bitmask mUnusable /* Tables that must be scanned after this one */
3449 ){
3460 u16 mNoOmit;
3480 }
3482 /* First call xBestIndex() with all constraints usable. */
3487 /* If the call to xBestIndex() with all terms enabled produced a plan
3488 ** that does not require any source tables (IOW: a plan with mBest==0)
3489 ** and does not use an IN(...) operator, then there is no point in making
3490 ** any further calls to xBestIndex() since they will all return the same
3491 ** result (if the xBestIndex() implementation is sane). */
3498 /* If the plan produced by the earlier call uses an IN(...) term, call
3499 ** xBestIndex again, this time with IN(...) terms disabled. */
3509 }
3510 }
3512 /* Call xBestIndex once for each distinct value of (prereqRight & ~mPrereq)
3513 ** in the set of terms that apply to the current virtual table. */
3519 Bitmask mThis = (
3521 );
3523 }
3534 }
3535 }
3537 /* If the calls to xBestIndex() in the above loop did not find a plan
3538 ** that requires no source tables at all (i.e. one guaranteed to be
3539 ** usable), make a call here with all source tables disabled */
3545 }
3547 /* If the calls to xBestIndex() have so far failed to find a plan
3548 ** that requires no source tables at all and does not use an IN(...)
3549 ** operator, make a final call to obtain one here. */
3554 }
3555 }
3561 }
3564 /*
3565 ** Add WhereLoop entries to handle OR terms. This works for either
3566 ** btrees or virtual tables.
3567 */
3570 Bitmask mPrereq,
3571 Bitmask mUnusable
3572 ){
3579 WhereClause tempWC;
3580 WhereLoopBuilder sSubBuild;
3594 ){
3618 }
3620 #ifdef WHERETRACE_ENABLED
3625 }
3626 #endif
3627 #ifndef SQLITE_OMIT_VIRTUALTABLE
3631 #endif
3632 {
3634 }
3637 }
3649 WhereOrSet sPrev;
3657 }
3658 }
3659 }
3660 }
3668 /* TUNING: Currently sSum.a[i].rRun is set to the sum of the costs
3669 ** of all sub-scans required by the OR-scan. However, due to rounding
3670 ** errors, it may be that the cost of the OR-scan is equal to its
3671 ** most expensive sub-scan. Add the smallest possible penalty
3672 ** (equivalent to multiplying the cost by 1.07) to ensure that
3673 ** this does not happen. Otherwise, for WHERE clauses such as the
3674 ** following where there is an index on "y":
3675 **
3676 ** WHERE likelihood(x=?, 0.99) OR y=?
3677 **
3678 ** the planner may elect to "OR" together a full-table scan and an
3679 ** index lookup. And other similarly odd results. */
3684 }
3686 }
3687 }
3689 }
3691 /*
3692 ** Add all WhereLoop objects for all tables
3693 */
3706 /* Loop over the tables in the join, from left to right */
3716 /* This condition is true when pItem is the FROM clause term on the
3717 ** right-hand-side of a LEFT or CROSS JOIN. */
3721 }
3722 #ifndef SQLITE_OMIT_VIRTUALTABLE
3728 }
3729 }
3733 {
3735 }
3738 }
3742 /* We hit the query planner search limit set by iPlanLimit */
3747 }
3748 }
3749 }
3753 }
3755 /*
3756 ** Examine a WherePath (with the addition of the extra WhereLoop of the 6th
3757 ** parameters) to see if it outputs rows in the requested ORDER BY
3758 ** (or GROUP BY) without requiring a separate sort operation. Return N:
3759 **
3760 ** N>0: N terms of the ORDER BY clause are satisfied
3761 ** N==0: No terms of the ORDER BY clause are satisfied
3762 ** N<0: Unknown yet how many terms of ORDER BY might be satisfied.
3763 **
3764 ** Note that processing for WHERE_GROUPBY and WHERE_DISTINCTBY is not as
3765 ** strict. With GROUP BY and DISTINCT the only requirement is that
3766 ** equivalent rows appear immediately adjacent to one another. GROUP BY
3767 ** and DISTINCT do not require rows to appear in any particular order as long
3768 ** as equivalent rows are grouped together. Thus for GROUP BY and DISTINCT
3769 ** the pOrderBy terms can be matched in any order. With ORDER BY, the
3770 ** pOrderBy terms must be matched in strict left-to-right order.
3771 */
3780 ){
3806 /*
3807 ** We say the WhereLoop is "one-row" if it generates no more than one
3808 ** row of output. A WhereLoop is one-row if all of the following are true:
3809 ** (a) All index columns match with WHERE_COLUMN_EQ.
3810 ** (b) The index is unique
3811 ** Any WhereLoop with an WHERE_COLUMN_EQ constraint on the rowid is one-row.
3812 ** Every one-row WhereLoop will have the WHERE_ONEROW bit set in wsFlags.
3813 **
3814 ** We say the WhereLoop is "order-distinct" if the set of columns from
3815 ** that WhereLoop that are in the ORDER BY clause are different for every
3816 ** row of the WhereLoop. Every one-row WhereLoop is automatically
3817 ** order-distinct. A WhereLoop that has no columns in the ORDER BY clause
3818 ** is not order-distinct. To be order-distinct is not quite the same as being
3819 ** UNIQUE since a UNIQUE column or index can have multiple rows that
3820 ** are NULL and NULL values are equivalent for the purpose of order-distinct.
3821 ** To be order-distinct, the columns must be UNIQUE and NOT NULL.
3822 **
3823 ** The rowid for a table is always UNIQUE and NOT NULL so whenever the
3824 ** rowid appears in the ORDER BY clause, the corresponding WhereLoop is
3825 ** automatically order-distinct.
3826 */
3841 }
3849 }
3853 }
3857 }
3860 /* Mark off any ORDER BY term X that is a column in the table of
3861 ** the current loop for which there is term in the WHERE
3862 ** clause of the form X IS NULL or X=? that reference only outer
3863 ** loops.
3864 */
3875 /* IN terms are only valid for sorting in the ORDER BY LIMIT
3876 ** optimization, and then only if they are actually used
3877 ** by the query plan */
3882 }
3890 }
3892 }
3894 }
3909 /* All relevant terms of the index must also be non-NULL in order
3910 ** for isOrderDistinct to be true. So the isOrderDistint value
3911 ** computed here might be a false positive. Corrections will be
3912 ** made at tag-20210426-1 below */
3915 }
3917 /* Loop through all columns of the index and deal with the ones
3918 ** that are not constrained by == or IN.
3919 */
3927 );
3931 /* Skip over == and IS and ISNULL terms. (Also skip IN terms when
3932 ** doing WHERE_ORDERBY_LIMIT processing). Except, IS and ISNULL
3933 ** terms imply that the index is not UNIQUE NOT NULL in which case
3934 ** the loop need to be marked as not order-distinct because it can
3935 ** have repeated NULL rows.
3936 **
3937 ** If the current term is a column of an ((?,?) IN (SELECT...))
3938 ** expression for which the SELECT returns more than one column,
3939 ** check that it is the only column used by this loop. Otherwise,
3940 ** if it is one of two or more, none of the columns can be
3941 ** considered to match an ORDER BY term.
3942 */
3949 }
3952 /* ALWAYS() justification: eOp is an equality operator due to the
3953 ** j<pLoop->u.btree.nEq constraint above. Any equality other
3954 ** than WO_IN is captured by the previous "if". So this one
3955 ** always has to be WO_IN. */
3962 }
3963 }
3964 }
3965 }
3967 /* Get the column number in the table (iColumn) and sort order
3968 ** (revIdx) for the j-th column of the index.
3969 */
3977 }
3979 /* An unconstrained column that might be NULL means that this
3980 ** WhereLoop is not well-ordered. tag-20210426-1
3981 */
3986 ){
3988 }
3991 }
3992 }
3994 /* Find the ORDER BY term that corresponds to the j-th column
3995 ** of the index and mark that ORDER BY term off
3996 */
4013 }
4014 }
4018 }
4021 }
4024 }
4026 /* Make sure the sort order is compatible in an ORDER BY clause.
4027 ** Sort order is irrelevant for a GROUP BY clause. */
4031 }
4036 }
4037 }
4043 }
4044 }
4049 }
4052 /* No match found */
4056 }
4058 }
4063 }
4066 /* Mark off any other ORDER BY terms that reference pLoop */
4071 Bitmask mTerm;
4078 }
4079 }
4080 }
4087 }
4089 }
4091 }
4094 /*
4095 ** If the WHERE_GROUPBY flag is set in the mask passed to sqlite3WhereBegin(),
4096 ** the planner assumes that the specified pOrderBy list is actually a GROUP
4097 ** BY clause - and so any order that groups rows as required satisfies the
4098 ** request.
4099 **
4100 ** Normally, in this case it is not possible for the caller to determine
4101 ** whether or not the rows are really being delivered in sorted order, or
4102 ** just in some other order that provides the required grouping. However,
4103 ** if the WHERE_SORTBYGROUP flag is also passed to sqlite3WhereBegin(), then
4104 ** this function may be called on the returned WhereInfo object. It returns
4105 ** true if the rows really will be sorted in the specified order, or false
4106 ** otherwise.
4107 **
4108 ** For example, assuming:
4109 **
4110 ** CREATE INDEX i1 ON t1(x, Y);
4111 **
4112 ** then
4113 **
4114 ** SELECT * FROM t1 GROUP BY x,y ORDER BY x,y; -- IsSorted()==1
4115 ** SELECT * FROM t1 GROUP BY y,x ORDER BY y,x; -- IsSorted()==0
4116 */
4121 }
4123 #ifdef WHERETRACE_ENABLED
4124 /* For debugging use only: */
4132 }
4133 #endif
4135 /*
4136 ** Return the cost of sorting nRow rows, assuming that the keys have
4137 ** nOrderby columns and that the first nSorted columns are already in
4138 ** order.
4139 */
4142 LogEst nRow,
4144 int nSorted
4145 ){
4146 /* TUNING: Estimated cost of a full external sort, where N is
4147 ** the number of rows to sort is:
4148 **
4149 ** cost = (3.0 * N * log(N)).
4150 **
4151 ** Or, if the order-by clause has X terms but only the last Y
4152 ** terms are out of order, then block-sorting will reduce the
4153 ** sorting cost to:
4154 **
4155 ** cost = (3.0 * N * log(N)) * (Y/X)
4156 **
4157 ** The (Y/X) term is implemented using stack variable rScale
4158 ** below.
4159 */
4165 /* Multiple by log(M) where M is the number of output rows.
4166 ** Use the LIMIT for M if it is smaller. Or if this sort is for
4167 ** a DISTINCT operator, M will be the number of distinct output
4168 ** rows, so fudge it downwards a bit.
4169 */
4173 /* TUNING: In the sort for a DISTINCT operator, assume that the DISTINCT
4174 ** reduces the number of output rows by a factor of 2 */
4176 }
4179 }
4181 /*
4182 ** Given the list of WhereLoop objects at pWInfo->pLoops, this routine
4183 ** attempts to find the lowest cost path that visits each WhereLoop
4184 ** once. This path is then loaded into the pWInfo->a[].pWLoop fields.
4185 **
4186 ** Assume that the total number of output rows that will need to be sorted
4187 ** will be nRowEst (in the 10*log2 representation). Or, ignore sorting
4188 ** costs if nRowEst==0.
4189 **
4190 ** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation
4191 ** error occurs.
4192 */
4218 /* TUNING: For simple queries, only the best path is tracked.
4219 ** For 2-way joins, the 5 best paths are followed.
4220 ** For joins of 3 or more tables, track the 10 best paths */
4225 /* If nRowEst is zero and there is an ORDER BY clause, ignore it. In this
4226 ** case the purpose of this call is to estimate the number of rows returned
4227 ** by the overall query. Once this estimate has been obtained, the caller
4228 ** will invoke this function a second time, passing the estimate as the
4229 ** nRowEst parameter. */
4234 }
4236 /* Allocate and initialize space for aTo, aFrom and aSortCost[] */
4247 }
4249 /* If there is an ORDER BY clause and it is not being ignored, set up
4250 ** space for the aSortCost[] array. Each element of the aSortCost array
4251 ** is either zero - meaning it has not yet been initialized - or the
4252 ** cost of sorting nRowEst rows of data where the first X terms of
4253 ** the ORDER BY clause are already in order, where X is the array
4254 ** index. */
4257 }
4261 /* Seed the search with a single WherePath containing zero WhereLoops.
4262 **
4263 ** TUNING: Do not let the number of iterations go above 28. If the cost
4264 ** of computing an automatic index is not paid back within the first 28
4265 ** rows, then do not use the automatic index. */
4270 /* If nLoop is zero, then there are no FROM terms in the query. Since
4271 ** in this case the query may return a maximum of one row, the results
4272 ** are already in the requested order. Set isOrdered to nOrderBy to
4273 ** indicate this. Or, if nLoop is greater than zero, set isOrdered to
4274 ** -1, indicating that the result set may or may not be ordered,
4275 ** depending on the loops added to the current plan. */
4277 }
4279 /* Compute successively longer WherePaths using the previous generation
4280 ** of WherePaths as the basis for the next. Keep track of the mxChoice
4281 ** best paths at each generation */
4296 /* Do not use an automatic index if the this loop is expected
4297 ** to run less than 1.25 times. It is tempting to also exclude
4298 ** automatic index usage on an outer loop, but sometimes an automatic
4299 ** index is useful in the outer loop of a correlated subquery. */
4302 }
4304 /* At this point, pWLoop is a candidate to be the next loop.
4305 ** Compute its cost */
4316 }
4321 );
4322 }
4323 /* TUNING: Add a small extra penalty (5) to sorting as an
4324 ** extra encouragment to the query planner to select a plan
4325 ** where the rows emerge in the correct order without any sorting
4326 ** required. */
4336 }
4338 /* Check to see if pWLoop should be added to the set of
4339 ** mxChoice best-so-far paths.
4340 **
4341 ** First look for an existing path among best-so-far paths
4342 ** that covers the same set of loops and has the same isOrdered
4343 ** setting as the current path candidate.
4344 **
4345 ** The term "((pTo->isOrdered^isOrdered)&0x80)==0" is equivalent
4346 ** to (pTo->isOrdered==(-1))==(isOrdered==(-1))" for the range
4347 ** of legal values for isOrdered, -1..64.
4348 */
4352 ){
4355 }
4356 }
4358 /* None of the existing best-so-far paths match the candidate. */
4361 ){
4362 /* The current candidate is no better than any of the mxChoice
4363 ** paths currently in the best-so-far buffer. So discard
4364 ** this candidate as not viable. */
4370 }
4371 #endif
4373 }
4374 /* If we reach this points it means that the new candidate path
4375 ** needs to be added to the set of best-so-far paths. */
4377 /* Increase the size of the aTo set by one */
4380 /* New path replaces the prior worst to keep count below mxChoice */
4382 }
4389 }
4390 #endif
4392 /* Control reaches here if best-so-far path pTo=aTo[jj] covers the
4393 ** same set of loops and has the same isOrdered setting as the
4394 ** candidate path. Check to see if the candidate should replace
4395 ** pTo or if the candidate should be skipped.
4396 **
4397 ** The conditional is an expanded vector comparison equivalent to:
4398 ** (pTo->rCost,pTo->nRow,pTo->rUnsorted) <= (rCost,nOut,rUnsorted)
4399 */
4404 )
4405 )
4406 ){
4416 }
4417 #endif
4418 /* Discard the candidate path from further consideration */
4421 }
4423 /* Control reaches here if the candidate path is better than the
4424 ** pTo path. Replace pTo with the candidate. */
4434 }
4435 #endif
4436 }
4437 /* pWLoop is a winner. Add it to the set of best so far */
4453 ){
4457 }
4458 }
4459 }
4460 }
4461 }
4474 }
4475 }
4476 }
4477 #endif
4479 /* Swap the roles of aFrom and aTo for the next generation */
4484 }
4490 }
4492 /* Find the lowest cost path. pFrom will be left pointing to that path */
4496 }
4498 /* Load the lowest cost path into pWInfo */
4504 }
4508 && nRowEst
4509 ){
4510 Bitmask notUsed;
4515 }
4516 }
4522 }
4532 ){
4541 }
4542 }
4543 }
4547 ){
4549 }
4550 }
4553 ){
4557 );
4562 }
4563 }
4564 }
4569 /* Free temporary memory and return success */
4572 }
4574 /*
4575 ** Most queries use only a single table (they are not joins) and have
4576 ** simple == constraints against indexed fields. This routine attempts
4577 ** to plan those simple cases using much less ceremony than the
4578 ** general-purpose query planner, and thereby yield faster sqlite3_prepare()
4579 ** times for the common case.
4580 **
4581 ** Return non-zero on success, if this query can be handled by this
4582 ** no-frills query planner. Return zero if this query needs the
4583 ** general-purpose query planner.
4584 */
4615 /* TUNING: Cost of a rowid lookup is 10 */
4631 }
4636 }
4640 /* TUNING: Cost of a unique index lookup is 15 */
4643 }
4644 }
4655 }
4656 #ifdef SQLITE_DEBUG
4658 #endif
4660 }
4662 }
4664 /*
4665 ** Helper function for exprIsDeterministic().
4666 */
4671 }
4673 }
4675 /*
4676 ** Return true if the expression contains no non-deterministic SQL
4677 ** functions. Do not consider non-deterministic SQL functions that are
4678 ** part of sub-select statements.
4679 */
4681 Walker w;
4688 }
4691 #ifdef WHERETRACE_ENABLED
4692 /*
4693 ** Display all WhereLoops in pWInfo
4694 */
4704 }
4705 }
4706 }
4707 # define WHERETRACE_ALL_LOOPS(W,C) showAllWhereLoops(W,C)
4708 #else
4709 # define WHERETRACE_ALL_LOOPS(W,C)
4710 #endif
4712 /*
4713 ** Generate the beginning of the loop used for WHERE clause processing.
4714 ** The return value is a pointer to an opaque structure that contains
4715 ** information needed to terminate the loop. Later, the calling routine
4716 ** should invoke sqlite3WhereEnd() with the return value of this function
4717 ** in order to complete the WHERE clause processing.
4718 **
4719 ** If an error occurs, this routine returns NULL.
4720 **
4721 ** The basic idea is to do a nested loop, one loop for each table in
4722 ** the FROM clause of a select. (INSERT and UPDATE statements are the
4723 ** same as a SELECT with only a single table in the FROM clause.) For
4724 ** example, if the SQL is this:
4725 **
4726 ** SELECT * FROM t1, t2, t3 WHERE ...;
4727 **
4728 ** Then the code generated is conceptually like the following:
4729 **
4730 ** foreach row1 in t1 do \ Code generated
4731 ** foreach row2 in t2 do |-- by sqlite3WhereBegin()
4732 ** foreach row3 in t3 do /
4733 ** ...
4734 ** end \ Code generated
4735 ** end |-- by sqlite3WhereEnd()
4736 ** end /
4737 **
4738 ** Note that the loops might not be nested in the order in which they
4739 ** appear in the FROM clause if a different order is better able to make
4740 ** use of indices. Note also that when the IN operator appears in
4741 ** the WHERE clause, it might result in additional nested loops for
4742 ** scanning through all values on the right-hand side of the IN.
4743 **
4744 ** There are Btree cursors associated with each table. t1 uses cursor
4745 ** number pTabList->a[0].iCursor. t2 uses the cursor pTabList->a[1].iCursor.
4746 ** And so forth. This routine generates code to open those VDBE cursors
4747 ** and sqlite3WhereEnd() generates the code to close them.
4748 **
4749 ** The code that sqlite3WhereBegin() generates leaves the cursors named
4750 ** in pTabList pointing at their appropriate entries. The [...] code
4751 ** can use OP_Column and OP_Rowid opcodes on these cursors to extract
4752 ** data from the various tables of the loop.
4753 **
4754 ** If the WHERE clause is empty, the foreach loops must each scan their
4755 ** entire tables. Thus a three-way join is an O(N^3) operation. But if
4756 ** the tables have indices and there are terms in the WHERE clause that
4757 ** refer to those indices, a complete table scan can be avoided and the
4758 ** code will run much faster. Most of the work of this routine is checking
4759 ** to see if there are indices that can be used to speed up the loop.
4760 **
4761 ** Terms of the WHERE clause are also used to limit which rows actually
4762 ** make it to the "..." in the middle of the loop. After each "foreach",
4763 ** terms of the WHERE clause that use only terms in that loop and outer
4764 ** loops are evaluated and if false a jump is made around all subsequent
4765 ** inner loops (or around the "..." if the test occurs within the inner-
4766 ** most loop)
4767 **
4768 ** OUTER JOINS
4769 **
4770 ** An outer join of tables t1 and t2 is conceptally coded as follows:
4771 **
4772 ** foreach row1 in t1 do
4773 ** flag = 0
4774 ** foreach row2 in t2 do
4775 ** start:
4776 ** ...
4777 ** flag = 1
4778 ** end
4779 ** if flag==0 then
4780 ** move the row2 cursor to a null row
4781 ** goto start
4782 ** fi
4783 ** end
4784 **
4785 ** ORDER BY CLAUSE PROCESSING
4786 **
4787 ** pOrderBy is a pointer to the ORDER BY clause (or the GROUP BY clause
4788 ** if the WHERE_GROUPBY flag is set in wctrlFlags) of a SELECT statement
4789 ** if there is one. If there is no ORDER BY clause or if this routine
4790 ** is called from an UPDATE or DELETE statement, then pOrderBy is NULL.
4791 **
4792 ** The iIdxCur parameter is the cursor number of an index. If
4793 ** WHERE_OR_SUBCLAUSE is set, iIdxCur is the cursor number of an index
4794 ** to use for OR clause processing. The WHERE clause should use this
4795 ** specific cursor. If WHERE_ONEPASS_DESIRED is set, then iIdxCur is
4796 ** the first cursor in an array of cursors for all indices. iIdxCur should
4797 ** be used to compute the appropriate cursor depending on which index is
4798 ** used.
4799 */
4808 ** If WHERE_USE_LIMIT, then the limit amount */
4809 ){
4827 ));
4829 /* Only one of WHERE_OR_SUBCLAUSE or WHERE_USE_LIMIT */
4833 /* Variable initialization */
4837 /* An ORDER/GROUP BY clause of more than 63 terms cannot be optimized */
4842 /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via
4843 ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */
4846 }
4848 /* The number of tables in the FROM clause is limited by the number of
4849 ** bits in a Bitmask
4850 */
4855 }
4857 /* This function normally generates a nested loop for all tables in
4858 ** pTabList. But if the WHERE_OR_SUBCLAUSE flag is set, then we should
4859 ** only generate code for the first table in pTabList and assume that
4860 ** any cursors associated with subsequent tables are uninitialized.
4861 */
4864 /* Allocate and initialize the WhereInfo structure that will become the
4865 ** return value. A single allocation is used to store the WhereInfo
4866 ** struct, the contents of WhereInfo.a[], the WhereClause structure
4867 ** and the WhereMaskSet structure. Since WhereClause contains an 8-byte
4868 ** field (type Bitmask) it must be aligned on an 8-byte boundary on
4869 ** some architectures. Hence the ROUND8() below.
4870 */
4877 }
4899 #ifdef SQLITE_DEBUG
4901 #endif
4903 /* Split the WHERE clause into separate subexpressions where each
4904 ** subexpression is separated by an AND operator.
4905 */
4910 /* Special case: No FROM clause
4911 */
4916 }
4919 /* Assign a bit from the bitmask to every term in the FROM clause.
4920 **
4921 ** The N-th term of the FROM clause is assigned a bitmask of 1<<N.
4922 **
4923 ** The rule of the previous sentence ensures thta if X is the bitmask for
4924 ** a table T, then X-1 is the bitmask for all other tables to the left of T.
4925 ** Knowing the bitmask for all tables to the left of a left join is
4926 ** important. Ticket #3015.
4927 **
4928 ** Note that bitmasks are created for all pTabList->nSrc tables in
4929 ** pTabList, not just the first nTabList tables. nTabList is normally
4930 ** equal to pTabList->nSrc but might be shortened to 1 if the
4931 ** WHERE_OR_SUBCLAUSE flag is set.
4932 */
4938 #ifdef SQLITE_DEBUG
4939 {
4945 }
4946 }
4947 #endif
4948 }
4950 /* Analyze all of the subexpressions. */
4954 /* Special case: WHERE terms that do not refer to any tables in the join
4955 ** (constant expressions). Evaluate each such term, and jump over all the
4956 ** generated code if the result is not true.
4957 **
4958 ** Do not do this if the expression contains non-deterministic functions
4959 ** that are not within a sub-select. This is not strictly required, but
4960 ** preserves SQLite's legacy behaviour in the following two cases:
4961 **
4962 ** FROM ... WHERE random()>0; -- eval random() once per row
4963 ** FROM ... WHERE (SELECT random())>0; -- eval random() once overall
4964 */
4971 }
4972 }
4976 /* The DISTINCT marking is pointless. Ignore it. */
4979 /* Try to ORDER BY the result set to make distinct processing easier */
4982 }
4983 }
4985 /* Construct the WhereLoop objects */
4986 #if defined(WHERETRACE_ENABLED)
4991 }
4994 Select sSelect;
5002 }
5003 }
5007 }
5008 #endif
5014 #ifdef SQLITE_ENABLE_STAT4
5015 /* If one or more WhereTerm.truthProb values were used in estimating
5016 ** loop parameters, but then those truthProb values were subsequently
5017 ** changed based on STAT4 information while computing subsequent loops,
5018 ** then we need to rerun the whole loop building process so that all
5019 ** loops will be built using the revised truthProb values. */
5029 }
5032 }
5033 #endif
5041 }
5042 }
5045 }
5048 }
5049 #ifdef WHERETRACE_ENABLED
5054 }
5059 }
5063 }
5067 }
5068 }
5072 }
5073 }
5074 #endif
5076 /* Attempt to omit tables from the join that do not affect the result.
5077 ** For a table to not affect the result, the following must be true:
5078 **
5079 ** 1) The query must not be an aggregate.
5080 ** 2) The table must be the RHS of a LEFT JOIN.
5081 ** 3) Either the query must be DISTINCT, or else the ON or USING clause
5082 ** must contain a constraint that limits the scan of the table to
5083 ** at most a single row.
5084 ** 4) The table must not be referenced by any part of the query apart
5085 ** from its own USING or ON clause.
5086 **
5087 ** For example, given:
5088 **
5089 ** CREATE TABLE t1(ipk INTEGER PRIMARY KEY, v1);
5090 ** CREATE TABLE t2(ipk INTEGER PRIMARY KEY, v2);
5091 ** CREATE TABLE t3(ipk INTEGER PRIMARY KEY, v3);
5092 **
5093 ** then table t2 can be omitted from the following:
5094 **
5095 ** SELECT v1, v3 FROM t1
5096 ** LEFT JOIN t2 ON (t1.ipk=t2.ipk)
5097 ** LEFT JOIN t3 ON (t1.ipk=t3.ipk)
5098 **
5099 ** or from:
5100 **
5101 ** SELECT DISTINCT v1, v3 FROM t1
5102 ** LEFT JOIN t2
5103 ** LEFT JOIN t3 ON (t1.ipk=t3.ipk)
5104 */
5110 ){
5115 }
5124 ){
5126 }
5133 ){
5135 }
5136 }
5137 }
5144 }
5145 }
5149 }
5151 nTabList--;
5152 }
5153 }
5154 #if defined(WHERETRACE_ENABLED)
5158 }
5160 #endif
5163 /* If the caller is an UPDATE or DELETE statement that is requesting
5164 ** to use a one-pass algorithm, determine if this is appropriate.
5165 **
5166 ** A one-pass approach can be used if the caller has requested one
5167 ** and either (a) the scan visits at most one row or (b) each
5168 ** of the following are true:
5169 **
5170 ** * the caller has indicated that a one-pass approach can be used
5171 ** with multiple rows (by setting WHERE_ONEPASS_MULTIROW), and
5172 ** * the table is not a virtual table, and
5173 ** * either the scan does not use the OR optimization or the caller
5174 ** is a DELETE operation (WHERE_DUPLICATES_OK is only specified
5175 ** for DELETE).
5176 **
5177 ** The last qualification is because an UPDATE statement uses
5178 ** WhereInfo.aiCurOnePass[1] to determine whether or not it really can
5179 ** use a one-pass approach, and this is not set accurately for scans
5180 ** that use the OR optimization.
5181 */
5191 )){
5196 }
5198 }
5199 }
5200 }
5202 /* Open all tables in the pTabList and any indices selected for
5203 ** searching those tables.
5204 */
5215 /* Do nothing */
5217 #ifndef SQLITE_OMIT_VIRTUALTABLE
5223 /* noop */
5225 #endif
5232 };
5240 ){
5241 /* If we know that only a prefix of the record will be used,
5242 ** it is advantageous to reduce the "column count" field in
5243 ** the P4 operand of the OP_OpenRead/Write opcode. */
5249 }
5250 #ifdef SQLITE_ENABLE_CURSOR_HINTS
5254 #endif
5255 {
5257 }
5258 #ifdef SQLITE_ENABLE_COLUMN_USED_MASK
5261 #endif
5264 }
5269 /* iAuxArg is always set to a positive value if ONEPASS is possible */
5273 ){
5274 /* This is one term of an OR-optimization using the PRIMARY KEY of a
5275 ** WITHOUT ROWID table. No need for a separate index */
5283 iIndexCur++;
5285 }
5293 }
5306 ){
5308 }
5310 #ifdef SQLITE_ENABLE_COLUMN_USED_MASK
5311 {
5320 }
5323 }
5325 }
5326 }
5328 }
5332 /* Generate the code to do the search. Each iteration of the for
5333 ** loop below generates code for a single nested loop of the VM
5334 ** program.
5335 */
5341 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
5346 }
5347 #endif
5350 );
5356 }
5357 }
5359 /* Done. */
5364 /* Jump here if malloc fails */
5365 whereBeginError:
5371 }
5373 }
5375 /*
5376 ** Part of sqlite3WhereEnd() will rewrite opcodes to reference the
5377 ** index rather than the main table. In SQLITE_DEBUG mode, we want
5378 ** to trace those changes if PRAGMA vdbe_addoptrace=on. This routine
5379 ** does that.
5380 */
5381 #ifndef SQLITE_DEBUG
5383 #else
5384 # define OpcodeRewriteTrace(D,K,P) sqlite3WhereOpcodeRewriteTrace(D,K,P)
5388 VdbeOp *pOp
5389 ){
5392 }
5393 #endif
5395 /*
5396 ** Generate the end of the WHERE loop. See comments on
5397 ** sqlite3WhereBegin() for additional information.
5398 */
5409 /* Generate loop termination code.
5410 */
5417 #ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT
5427 ){
5432 }
5439 }
5441 /* The common case: Advance to the next row */
5453 }
5454 #ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT
5456 #endif
5459 }
5474 /* For LEFT JOIN queries, cursor pIn->iCur may not have been
5475 ** opened yet. This occurs for WHERE clauses such as
5476 ** "a = ? AND b IN (...)", where the index is on (a, b). If
5477 ** the RHS of the (a=?) is NULL, then the "b IN (...)" may
5478 ** never have been coded, but the body of the loop run to
5479 ** return the null-row. So, if the cursor is not open yet,
5480 ** jump over the OP_Next or OP_Prev instruction about to
5481 ** be coded. */
5485 }
5491 /* Retarget the OP_IsNull against the left operand of IN so
5492 ** it jumps past the OP_IfNoHope. This is because the
5493 ** OP_IsNull also bypasses the OP_Affinity opcode that is
5494 ** required by OP_IfNoHope. */
5496 }
5497 }
5502 }
5504 }
5505 }
5512 }
5513 #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
5518 }
5519 #endif
5527 }
5530 ){
5532 }
5537 }
5539 }
5542 }
5544 /* The "break" point is here, just past the end of the outer loop.
5545 ** Set it.
5546 */
5559 /* For a co-routine, change all OP_Column references to the table of
5560 ** the co-routine into OP_Copy of result contained in a register.
5561 ** OP_Rowid becomes OP_Null.
5562 */
5568 }
5570 #ifdef SQLITE_ENABLE_EARLY_CURSOR_CLOSE
5571 /* Close all of the cursors that were opened by sqlite3WhereBegin.
5572 ** Except, do not close cursors that will be reused by the OR optimization
5573 ** (WHERE_OR_SUBCLAUSE). And do not close the OP_OpenWrite cursors
5574 ** created for the ONEPASS optimization.
5575 */
5579 ){
5583 }
5587 ){
5589 }
5590 }
5591 #endif
5593 /* If this scan uses an index, make VDBE code substitutions to read data
5594 ** from the index instead of from the table where possible. In some cases
5595 ** this optimization prevents the table from ever being read, which can
5596 ** yield a significant performance boost.
5597 **
5598 ** Calls to the code generator in between sqlite3WhereBegin and
5599 ** sqlite3WhereEnd will have created code that references the table
5600 ** directly. This loop scans all that code looking for opcodes
5601 ** that reference the table and converts them into opcodes that
5602 ** reference the index.
5603 */
5608 }
5611 ){
5616 }
5618 #ifdef SQLITE_DEBUG
5621 }
5622 /* Proof that the "+1" on the k value above is safe */
5627 #endif
5633 /* no-op */
5635 #ifdef SQLITE_ENABLE_OFFSET_SQL_FUNC
5637 #endif
5638 ){
5648 }
5654 }
5664 }
5665 #ifdef SQLITE_DEBUG
5666 k++;
5667 #endif
5669 #ifdef SQLITE_DEBUG
5671 #endif
5672 }
5673 }
5675 /* Final cleanup
5676 */
5681 }