| blob | ad309006d106cea34fc855a8ade89369f17c40d2 |
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 /* Test variable that can be set to enable WHERE tracing */
41 #if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
43 #endif
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 TRUE if the WHERE clause returns rows in ORDER BY order.
63 ** Return FALSE if the output needs to be sorted.
64 */
67 }
69 /*
70 ** In the ORDER BY LIMIT optimization, if the inner-most loop is known
71 ** to emit rows in increasing order, and if the last row emitted by the
72 ** inner-most loop did not fit within the sorter, then we can skip all
73 ** subsequent rows for the current iteration of the inner loop (because they
74 ** will not fit in the sorter either) and continue with the second inner
75 ** loop - the loop immediately outside the inner-most.
76 **
77 ** When a row does not fit in the sorter (because the sorter already
78 ** holds LIMIT+OFFSET rows that are smaller), then a jump is made to the
79 ** label returned by this function.
80 **
81 ** If the ORDER BY LIMIT optimization applies, the jump destination should
82 ** be the continuation for the second-inner-most loop. If the ORDER BY
83 ** LIMIT optimization does not apply, then the jump destination should
84 ** be the continuation for the inner-most loop.
85 **
86 ** It is always safe for this routine to return the continuation of the
87 ** inner-most loop, in the sense that a correct answer will result.
88 ** Returning the continuation the second inner loop is an optimization
89 ** that might make the code run a little faster, but should not change
90 ** the final answer.
91 */
95 /* The ORDER BY LIMIT optimization does not apply. Jump to the
96 ** continuation of the inner-most loop. */
98 }
102 }
104 /*
105 ** Return the VDBE address or label to jump to in order to continue
106 ** immediately with the next row of a WHERE clause.
107 */
111 }
113 /*
114 ** Return the VDBE address or label to jump to in order to break
115 ** out of a WHERE loop.
116 */
119 }
121 /*
122 ** Return ONEPASS_OFF (0) if an UPDATE or DELETE statement is unable to
123 ** operate directly on the rowids returned by a WHERE clause. Return
124 ** ONEPASS_SINGLE (1) if the statement can operation directly because only
125 ** a single row is to be changed. Return ONEPASS_MULTI (2) if the one-pass
126 ** optimization can be used on multiple
127 **
128 ** If the ONEPASS optimization is used (if this routine returns true)
129 ** then also write the indices of open cursors used by ONEPASS
130 ** into aiCur[0] and aiCur[1]. iaCur[0] gets the cursor of the data
131 ** table and iaCur[1] gets the cursor used by an auxiliary index.
132 ** Either value may be -1, indicating that cursor is not used.
133 ** Any cursors returned will have been opened for writing.
134 **
135 ** aiCur[0] and aiCur[1] both get -1 if the where-clause logic is
136 ** unable to use the ONEPASS optimization.
137 */
140 #ifdef WHERETRACE_ENABLED
145 }
146 #endif
148 }
150 /*
151 ** Return TRUE if the WHERE loop uses the OP_DeferredSeek opcode to move
152 ** the data cursor to the row selected by the index cursor.
153 */
156 }
158 /*
159 ** Move the content of pSrc into pDest
160 */
164 }
166 /*
167 ** Try to insert a new prerequisite/cost entry into the WhereOrSet pSet.
168 **
169 ** The new entry might overwrite an existing entry, or it might be
170 ** appended, or it might be discarded. Do whatever is the right thing
171 ** so that pSet keeps the N_OR_COST best entries seen so far.
172 */
177 LogEst nOut /* Number of outputs for the new entry */
178 ){
179 u16 i;
184 }
187 }
188 }
196 }
198 }
199 whereOrInsert_done:
204 }
206 /*
207 ** Return the bitmask for the given cursor number. Return 0 if
208 ** iCursor is not in the set.
209 */
216 }
217 }
219 }
221 /*
222 ** Create a new mask for cursor iCursor.
223 **
224 ** There is one cursor per table in the FROM clause. The number of
225 ** tables in the FROM clause is limited by a test early in the
226 ** sqlite3WhereBegin() routine. So we know that the pMaskSet->ix[]
227 ** array will never overflow.
228 */
232 }
234 /*
235 ** Advance to the next WhereTerm that matches according to the criteria
236 ** established when the pScan object was initialized by whereScanInit().
237 ** Return NULL if there are no more matching WhereTerms.
238 */
261 ){
265 ==TK_COLUMN
266 ){
272 }
273 }
278 }
279 }
281 /* Verify the affinity and collating sequence match */
288 }
294 }
295 }
300 ){
303 }
307 }
308 }
309 }
317 }
319 }
321 /*
322 ** This is whereScanInit() for the case of an index on an expression.
323 ** It is factored out into a separate tail-recursion subroutine so that
324 ** the normal whereScanInit() routine, which is a high-runner, does not
325 ** need to push registers onto the stack as part of its prologue.
326 */
330 }
332 /*
333 ** Initialize a WHERE clause scanner object. Return a pointer to the
334 ** first match. Return NULL if there are no matches.
335 **
336 ** The scanner will be searching the WHERE clause pWC. It will look
337 ** for terms of the form "X <op> <expr>" where X is column iColumn of table
338 ** iCur. Or if pIdx!=0 then X is column iColumn of index pIdx. pIdx
339 ** must be one of the indexes of table iCur.
340 **
341 ** The <op> must be one of the operators described by opMask.
342 **
343 ** If the search is for X and the WHERE clause contains terms of the
344 ** form X=Y then this routine might also return terms of the form
345 ** "Y <op> <expr>". The number of levels of transitivity is limited,
346 ** but is enough to handle most commonly occurring SQL statements.
347 **
348 ** If X is not the INTEGER PRIMARY KEY then X must be compatible with
349 ** index pIdx.
350 */
358 ){
382 }
385 }
388 }
390 /*
391 ** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
392 ** where X is a reference to the iColumn of table iCur or of index pIdx
393 ** if pIdx!=0 and <op> is one of the WO_xx operator codes specified by
394 ** the op parameter. Return a pointer to the term. Return 0 if not found.
395 **
396 ** If pIdx!=0 then it must be one of the indexes of table iCur.
397 ** Search for terms matching the iColumn-th column of pIdx
398 ** rather than the iColumn-th column of table iCur.
399 **
400 ** The term returned might by Y=<expr> if there is another constraint in
401 ** the WHERE clause that specifies that X=Y. Any such constraints will be
402 ** identified by the WO_EQUIV bit in the pTerm->eOperator field. The
403 ** aiCur[]/iaColumn[] arrays hold X and all its equivalents. There are 11
404 ** slots in aiCur[]/aiColumn[] so that means we can look for X plus up to 10
405 ** other equivalent values. Hence a search for X will return <expr> if X=A1
406 ** and A1=A2 and A2=A3 and ... and A9=A10 and A10=<expr>.
407 **
408 ** If there are multiple terms in the WHERE clause of the form "X <op> <expr>"
409 ** then try for the one with no dependencies on <expr> - in other words where
410 ** <expr> is a constant expression of some kind. Only return entries of
411 ** the form "X <op> Y" where Y is a column in another table if no terms of
412 ** the form "X <op> <const-expr>" exist. If no terms with a constant RHS
413 ** exist, try to return a term that does not use WO_EQUIV.
414 */
422 ){
425 WhereScan scan;
434 }
436 }
438 }
440 }
442 /*
443 ** This function searches pList for an entry that matches the iCol-th column
444 ** of index pIdx.
445 **
446 ** If such an expression is found, its index in pList->a[] is returned. If
447 ** no expression is found, -1 is returned.
448 */
455 ){
464 ){
468 }
469 }
470 }
473 }
475 /*
476 ** Return TRUE if the iCol-th column of index pIdx is NOT NULL
477 */
491 }
492 }
494 /*
495 ** Return true if the DISTINCT expression-list passed as the third argument
496 ** is redundant.
497 **
498 ** A DISTINCT list is redundant if any subset of the columns in the
499 ** DISTINCT list are collectively unique and individually non-null.
500 */
506 ){
512 /* If there is more than one table or sub-select in the FROM clause of
513 ** this query, then it will not be possible to show that the DISTINCT
514 ** clause is redundant. */
519 /* If any of the expressions is an IPK column on table iBase, then return
520 ** true. Note: The (p->iTable==iBase) part of this test may be false if the
521 ** current SELECT is a correlated sub-query.
522 */
526 }
528 /* Loop through all indices on the table, checking each to see if it makes
529 ** the DISTINCT qualifier redundant. It does so if:
530 **
531 ** 1. The index is itself UNIQUE, and
532 **
533 ** 2. All of the columns in the index are either part of the pDistinct
534 ** list, or else the WHERE clause contains a term of the form "col=X",
535 ** where X is a constant value. The collation sequences of the
536 ** comparison and select-list expressions must match those of the index.
537 **
538 ** 3. All of those index columns for which the WHERE clause does not
539 ** contain a "col=X" term are subject to a NOT NULL constraint.
540 */
547 }
548 }
550 /* This index implies that the DISTINCT qualifier is redundant. */
552 }
553 }
556 }
559 /*
560 ** Estimate the logarithm of the input value to base 2.
561 */
564 }
566 /*
567 ** Convert OP_Column opcodes to OP_Copy in previously generated code.
568 **
569 ** This routine runs over generated VDBE code and translates OP_Column
570 ** opcodes into OP_Copy when the table is being accessed via co-routine
571 ** instead of via table lookup.
572 **
573 ** If the iAutoidxCur is not zero, then any OP_Rowid instructions on
574 ** cursor iTabCur are transformed into OP_Sequence opcode for the
575 ** iAutoidxCur cursor, in order to generate unique rowids for the
576 ** automatic index being generated.
577 */
584 ){
604 }
605 }
606 }
607 }
609 /*
610 ** Two routines for printing the content of an sqlite3_index_info
611 ** structure. Used for testing and debugging only. If neither
612 ** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines
613 ** are no-ops.
614 */
615 #if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(WHERETRACE_ENABLED)
621 i,
626 }
629 i,
632 }
633 }
639 i,
642 }
648 }
649 #else
650 #define whereTraceIndexInfoInputs(A)
651 #define whereTraceIndexInfoOutputs(A)
652 #endif
654 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
655 /*
656 ** Return TRUE if the WHERE clause term pTerm is of a form where it
657 ** could be used with an index to access pSrc, assuming an appropriate
658 ** index existed.
659 */
663 Bitmask notReady /* Tables in outer loops of the join */
664 ){
671 ){
672 /* Cannot use an IS term from the WHERE clause as an index driver for
673 ** the RHS of a LEFT JOIN. Such a term can only be used if it is from
674 ** the ON clause. */
676 }
683 }
684 #endif
687 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
688 /*
689 ** Generate code to construct the Index object for an automatic index
690 ** and to set up the WhereLevel object pLevel so that the code generator
691 ** makes use of the automatic index.
692 */
699 ){
724 /* Generate code to skip over the creation and initialization of the
725 ** transient index on 2nd and subsequent iterations of the loop. */
730 /* Count the number of columns that will be added to the index
731 ** and used to match WHERE clause constraints */
748 }
759 }
763 }
766 }
767 }
768 }
774 /* Count the number of additional columns needed to create a
775 ** covering index. A "covering index" is an index that contains all
776 ** columns that are needed by the query. With a covering index, the
777 ** original table never needs to be accessed. Automatic indices must
778 ** be a covering index because the index will not be updated if the
779 ** original table changes and the index and table cannot both be used
780 ** if they go out of sync.
781 */
788 }
791 }
793 /* Construct the Index object to describe this index */
814 n++;
815 }
816 }
817 }
820 /* Add additional columns needed to make the automatic index into
821 ** a covering index */
826 n++;
827 }
828 }
833 n++;
834 }
835 }
840 /* Create the automatic index */
847 /* Fill the automatic index with content */
858 }
863 }
867 );
882 }
886 /* Jump here when skipping the initialization */
889 end_auto_index_create:
891 }
894 #ifndef SQLITE_OMIT_VIRTUALTABLE
895 /*
896 ** Allocate and populate an sqlite3_index_info structure. It is the
897 ** responsibility of the caller to eventually release the structure
898 ** by passing the pointer returned by this function to sqlite3_free().
899 */
907 ){
919 /* Count the number of possible WHERE clause constraints referring
920 ** to this virtual table */
932 nTerm++;
933 }
935 /* If the ORDER BY clause contains only columns in the current
936 ** virtual table then allocate space for the aOrderBy part of
937 ** the sqlite3_index_info structure.
938 */
946 }
949 }
950 }
952 /* Allocate the sqlite3_index_info structure
953 */
960 }
972 u16 op;
983 /* tag-20191211-002: WHERE-clause constraints are not useful to the
984 ** right-hand table of a LEFT JOIN. See tag-20191211-001 for the
985 ** equivalent restriction for ordinary tables. */
988 ){
990 }
1003 }
1006 /* The direct assignment in the previous line is possible only because
1007 ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical. The
1008 ** following asserts verify this fact. */
1018 ){
1023 }
1024 }
1026 j++;
1027 }
1033 }
1037 }
1039 /*
1040 ** The table object reference passed as the second argument to this function
1041 ** must represent a virtual table. This function invokes the xBestIndex()
1042 ** method of the virtual table with the sqlite3_index_info object that
1043 ** comes in as the 3rd argument to this function.
1044 **
1045 ** If an error occurs, pParse is populated with an error message and an
1046 ** appropriate error code is returned. A return of SQLITE_CONSTRAINT from
1047 ** xBestIndex is not considered an error. SQLITE_CONSTRAINT indicates that
1048 ** the current configuration of "unusable" flags in sqlite3_index_info can
1049 ** not result in a valid plan.
1050 **
1051 ** Whether or not an error is returned, it is the responsibility of the
1052 ** caller to eventually free p->idxStr if p->needToFreeIdxStr indicates
1053 ** that this is required.
1054 */
1070 }
1071 }
1075 }
1078 #ifdef SQLITE_ENABLE_STAT4
1079 /*
1080 ** Estimate the location of a particular key among all keys in an
1081 ** index. Store the results in aStat as follows:
1082 **
1083 ** aStat[0] Est. number of rows less than pRec
1084 ** aStat[1] Est. number of rows equal to pRec
1085 **
1086 ** Return the index of the sample that is the smallest sample that
1087 ** is greater than or equal to pRec. Note that this index is not an index
1088 ** into the aSample[] array - it is an index into a virtual set of samples
1089 ** based on the contents of aSample[] and the number of fields in record
1090 ** pRec.
1091 */
1098 ){
1109 #ifndef SQLITE_DEBUG
1111 #endif
1116 /* Do a binary search to find the first sample greater than or equal
1117 ** to pRec. If pRec contains a single field, the set of samples to search
1118 ** is simply the aSample[] array. If the samples in aSample[] contain more
1119 ** than one fields, all fields following the first are ignored.
1120 **
1121 ** If pRec contains N fields, where N is more than one, then as well as the
1122 ** samples in aSample[] (truncated to N fields), the search also has to
1123 ** consider prefixes of those samples. For example, if the set of samples
1124 ** in aSample is:
1125 **
1126 ** aSample[0] = (a, 5)
1127 ** aSample[1] = (a, 10)
1128 ** aSample[2] = (b, 5)
1129 ** aSample[3] = (c, 100)
1130 ** aSample[4] = (c, 105)
1131 **
1132 ** Then the search space should ideally be the samples above and the
1133 ** unique prefixes [a], [b] and [c]. But since that is hard to organize,
1134 ** the code actually searches this set:
1135 **
1136 ** 0: (a)
1137 ** 1: (a, 5)
1138 ** 2: (a, 10)
1139 ** 3: (a, 10)
1140 ** 4: (b)
1141 ** 5: (b, 5)
1142 ** 6: (c)
1143 ** 7: (c, 100)
1144 ** 8: (c, 105)
1145 ** 9: (c, 105)
1146 **
1147 ** For each sample in the aSample[] array, N samples are present in the
1148 ** effective sample array. In the above, samples 0 and 1 are based on
1149 ** sample aSample[0]. Samples 2 and 3 on aSample[1] etc.
1150 **
1151 ** Often, sample i of each block of N effective samples has (i+1) fields.
1152 ** Except, each sample may be extended to ensure that it is greater than or
1153 ** equal to the previous sample in the array. For example, in the above,
1154 ** sample 2 is the first sample of a block of N samples, so at first it
1155 ** appears that it should be 1 field in size. However, that would make it
1156 ** smaller than sample 1, so the binary search would not work. As a result,
1157 ** it is extended to two fields. The duplicates that this creates do not
1158 ** cause any problems.
1159 */
1170 /* The proposed effective sample is a prefix of sample aSample[iSamp].
1171 ** Specifically, the shortest prefix of at least (1 + iTest%nField)
1172 ** fields that is greater than the previous effective sample. */
1175 }
1178 }
1192 }
1196 #ifdef SQLITE_DEBUG
1197 /* The following assert statements check that the binary search code
1198 ** above found the right answer. This block serves no purpose other
1199 ** than to invoke the asserts. */
1202 /* If (res==0) is true, then pRec must be equal to sample i. */
1208 );
1210 /* Unless i==pIdx->nSample, indicating that pRec is larger than
1211 ** all samples in the aSample[] array, pRec must be smaller than the
1212 ** (iCol+1) field prefix of sample i. */
1219 /* if i==0 and iCol==0, then record pRec is smaller than all samples
1220 ** in the aSample[] array. Otherwise, if (iCol>0) then pRec must
1221 ** be greater than or equal to the (iCol) field prefix of sample i.
1222 ** If (i>0), then pRec must also be greater than sample (i-1). */
1227 }
1232 }
1233 }
1234 }
1238 /* Record pRec is equal to sample i */
1243 /* At this point, the (iCol+1) field prefix of aSample[i] is the first
1244 ** sample that is greater than pRec. Or, if i==pIdx->nSample then pRec
1245 ** is larger than all samples in the array. */
1251 }
1257 }
1262 }
1265 }
1267 /* Restore the pRec->nField value before returning. */
1270 }
1273 /*
1274 ** If it is not NULL, pTerm is a term that provides an upper or lower
1275 ** bound on a range scan. Without considering pTerm, it is estimated
1276 ** that the scan will visit nNew rows. This function returns the number
1277 ** estimated to be visited after taking pTerm into account.
1278 **
1279 ** If the user explicitly specified a likelihood() value for this term,
1280 ** then the return value is the likelihood multiplied by the number of
1281 ** input rows. Otherwise, this function assumes that an "IS NOT NULL" term
1282 ** has a likelihood of 0.50, and any other term a likelihood of 0.25.
1283 */
1291 }
1292 }
1294 }
1297 #ifdef SQLITE_ENABLE_STAT4
1298 /*
1299 ** Return the affinity for a single column of an index.
1300 */
1305 }
1308 }
1309 #endif
1312 #ifdef SQLITE_ENABLE_STAT4
1313 /*
1314 ** This function is called to estimate the number of rows visited by a
1315 ** range-scan on a skip-scan index. For example:
1316 **
1317 ** CREATE INDEX i1 ON t1(a, b, c);
1318 ** SELECT * FROM t1 WHERE a=? AND c BETWEEN ? AND ?;
1319 **
1320 ** Value pLoop->nOut is currently set to the estimated number of rows
1321 ** visited for scanning (a=? AND b=?). This function reduces that estimate
1322 ** by some factor to account for the (c BETWEEN ? AND ?) expression based
1323 ** on the stat4 data for the index. this scan will be peformed multiple
1324 ** times (once for each (a,b) combination that matches a=?) is dealt with
1325 ** by the caller.
1326 **
1327 ** It does this by scanning through all stat4 samples, comparing values
1328 ** extracted from pLower and pUpper with the corresponding column in each
1329 ** sample. If L and U are the number of samples found to be less than or
1330 ** equal to the values extracted from pLower and pUpper respectively, and
1331 ** N is the total number of samples, the pLoop->nOut value is adjusted
1332 ** as follows:
1333 **
1334 ** nOut = nOut * ( min(U - L, 1) / N )
1335 **
1336 ** If pLower is NULL, or a value cannot be extracted from the term, L is
1337 ** set to zero. If pUpper is NULL, or a value cannot be extracted from it,
1338 ** U is set to N.
1339 **
1340 ** Normally, this function sets *pbDone to 1 before returning. However,
1341 ** if no value can be extracted from either pLower or pUpper (and so the
1342 ** estimate of the number of rows delivered remains unchanged), *pbDone
1343 ** is left as is.
1344 **
1345 ** If an error occurs, an SQLite error code is returned. Otherwise,
1346 ** SQLITE_OK.
1347 */
1354 ){
1372 }
1376 }
1386 }
1390 }
1391 }
1395 /* If there is both an upper and lower bound specified, and the
1396 ** comparisons indicate that they are close together, use the fallback
1397 ** method (assume that the scan visits 1/64 of the rows) for estimating
1398 ** the number of rows visited. Otherwise, estimate the number of rows
1399 ** using the method described in the header comment for this function. */
1406 }
1410 }
1417 }
1420 /*
1421 ** This function is used to estimate the number of rows that will be visited
1422 ** by scanning an index for a range of values. The range may have an upper
1423 ** bound, a lower bound, or both. The WHERE clause terms that set the upper
1424 ** and lower bounds are represented by pLower and pUpper respectively. For
1425 ** example, assuming that index p is on t1(a):
1426 **
1427 ** ... FROM t1 WHERE a > ? AND a < ? ...
1428 ** |_____| |_____|
1429 ** | |
1430 ** pLower pUpper
1431 **
1432 ** If either of the upper or lower bound is not present, then NULL is passed in
1433 ** place of the corresponding WhereTerm.
1434 **
1435 ** The value in (pBuilder->pNew->u.btree.nEq) is the number of the index
1436 ** column subject to the range constraint. Or, equivalently, the number of
1437 ** equality constraints optimized by the proposed index scan. For example,
1438 ** assuming index p is on t1(a, b), and the SQL query is:
1439 **
1440 ** ... FROM t1 WHERE a = ? AND b > ? AND b < ? ...
1441 **
1442 ** then nEq is set to 1 (as the range restricted column, b, is the second
1443 ** left-most column of the index). Or, if the query is:
1444 **
1445 ** ... FROM t1 WHERE a > ? AND a < ? ...
1446 **
1447 ** then nEq is set to 0.
1448 **
1449 ** When this function is called, *pnOut is set to the sqlite3LogEst() of the
1450 ** number of rows that the index scan is expected to visit without
1451 ** considering the range constraints. If nEq is 0, then *pnOut is the number of
1452 ** rows in the index. Assuming no error occurs, *pnOut is adjusted (reduced)
1453 ** to account for the range constraints pLower and pUpper.
1454 **
1455 ** In the absence of sqlite_stat4 ANALYZE data, or if such data cannot be
1456 ** used, a single range inequality reduces the search space by a factor of 4.
1457 ** and a pair of constraints (x>? AND x<?) reduces the expected number of
1458 ** rows visited by a factor of 64.
1459 */
1466 ){
1469 LogEst nNew;
1471 #ifdef SQLITE_ENABLE_STAT4
1477 ){
1484 /* Variable iLower will be set to the estimate of the number of rows in
1485 ** the index that are less than the lower bound of the range query. The
1486 ** lower bound being the concatenation of $P and $L, where $P is the
1487 ** key-prefix formed by the nEq values matched against the nEq left-most
1488 ** columns of the index, and $L is the value in pLower.
1489 **
1490 ** Or, if pLower is NULL or $L cannot be extracted from it (because it
1491 ** is not a simple variable or literal value), the lower bound of the
1492 ** range is $P. Due to a quirk in the way whereKeyStats() works, even
1493 ** if $L is available, whereKeyStats() is called for both ($P) and
1494 ** ($P:$L) and the larger of the two returned values is used.
1495 **
1496 ** Similarly, iUpper is to be set to the estimate of the number of rows
1497 ** less than the upper bound of the range query. Where the upper bound
1498 ** is either ($P) or ($P:$U). Again, even if $U is available, both values
1499 ** of iUpper are requested of whereKeyStats() and the smaller used.
1500 **
1501 ** The number of rows between the two bounds is then just iUpper-iLower.
1502 */
1511 }
1512 /* Determine iLower and iUpper using ($P) only. */
1517 /* Note: this call could be optimized away - since the same values must
1518 ** have been requested when testing key $P in whereEqualScanEst(). */
1522 }
1528 /* The roles of pLower and pUpper are swapped for a DESC index */
1531 }
1533 /* If possible, improve on the iLower estimate using ($P:$L). */
1539 tRowcnt iNew;
1545 nOut--;
1547 }
1548 }
1550 /* If possible, improve on the iUpper estimate using ($P:$U). */
1556 tRowcnt iNew;
1562 nOut--;
1564 }
1565 }
1571 /* TUNING: If both iUpper and iLower are derived from the same
1572 ** sample, then assume they are 4x more selective. This brings
1573 ** the estimated selectivity more in line with what it would be
1574 ** if estimated without the use of STAT4 tables. */
1578 }
1581 }
1584 }
1589 }
1590 }
1591 #else
1595 #endif
1600 /* TUNING: If there is both an upper and lower limit and neither limit
1601 ** has an application-defined likelihood(), assume the range is
1602 ** reduced by an additional 75%. This means that, by default, an open-ended
1603 ** range query (e.g. col > ?) is assumed to match 1/4 of the rows in the
1604 ** index. While a closed range (e.g. col BETWEEN ? AND ?) is estimated to
1605 ** match 1/64 of the index. */
1608 }
1613 #if defined(WHERETRACE_ENABLED)
1617 }
1618 #endif
1621 }
1623 #ifdef SQLITE_ENABLE_STAT4
1624 /*
1625 ** Estimate the number of rows that will be returned based on
1626 ** an equality constraint x=VALUE and where that VALUE occurs in
1627 ** the histogram data. This only works when x is the left-most
1628 ** column of an index and sqlite_stat4 histogram data is available
1629 ** for that index. When pExpr==NULL that means the constraint is
1630 ** "x IS NULL" instead of "x=VALUE".
1631 **
1632 ** Write the estimated row count into *pnRow and return SQLITE_OK.
1633 ** If unable to make an estimate, leave *pnRow unchanged and return
1634 ** non-zero.
1635 **
1636 ** This routine can fail if it is unable to load a collating sequence
1637 ** required for string comparison, or if unable to allocate memory
1638 ** for a UTF conversion required for comparison. The error is stored
1639 ** in the pParse structure.
1640 */
1646 ){
1660 /* If values are not available for all fields of the index to the left
1661 ** of this one, no estimate can be made. Return SQLITE_NOTFOUND. */
1664 }
1666 /* This is an optimization only. The call to sqlite3Stat4ProbeSetValue()
1667 ** below would return the same value. */
1671 }
1685 }
1688 #ifdef SQLITE_ENABLE_STAT4
1689 /*
1690 ** Estimate the number of rows that will be returned based on
1691 ** an IN constraint where the right-hand side of the IN operator
1692 ** is a list of values. Example:
1693 **
1694 ** WHERE x IN (1,2,3,4)
1695 **
1696 ** Write the estimated row count into *pnRow and return SQLITE_OK.
1697 ** If unable to make an estimate, leave *pnRow unchanged and return
1698 ** non-zero.
1699 **
1700 ** This routine can fail if it is unable to load a collating sequence
1701 ** required for string comparison, or if unable to allocate memory
1702 ** for a UTF conversion required for comparison. The error is stored
1703 ** in the pParse structure.
1704 */
1710 ){
1725 }
1731 }
1734 }
1738 #ifdef WHERETRACE_ENABLED
1739 /*
1740 ** Print the content of a WhereTerm object
1741 */
1761 }
1765 /* The 0x10000 .wheretrace flag causes extra information to be
1766 ** shown about each Term */
1770 }
1773 }
1776 }
1779 }
1780 }
1781 #endif
1783 #ifdef WHERETRACE_ENABLED
1784 /*
1785 ** Show the complete content of a WhereClause
1786 */
1791 }
1792 }
1793 #endif
1795 #ifdef WHERETRACE_ENABLED
1796 /*
1797 ** Print a WhereLoop object for debugging purposes
1798 */
1816 }
1820 }
1828 }
1831 }
1836 }
1842 }
1843 }
1844 }
1845 #endif
1847 /*
1848 ** Convert bulk memory into a valid WhereLoop that can be passed
1849 ** to whereLoopClear harmlessly.
1850 */
1856 }
1858 /*
1859 ** Clear the WhereLoop.u union. Leave WhereLoop.pLTerm intact.
1860 */
1871 }
1872 }
1873 }
1875 /*
1876 ** Deallocate internal memory used by a WhereLoop object
1877 */
1882 }
1884 /*
1885 ** Increase the memory allocation for pLoop->aLTerm[] to be at least n.
1886 */
1898 }
1900 /*
1901 ** Transfer content from the second pLoop into the first.
1902 */
1908 }
1915 }
1917 }
1919 /*
1920 ** Delete a WhereLoop object
1921 */
1925 }
1927 /*
1928 ** Free a WhereInfo structure
1929 */
1937 }
1938 }
1944 }
1947 }
1949 /*
1950 ** Return TRUE if all of the following are true:
1951 **
1952 ** (1) X has the same or lower cost that Y
1953 ** (2) X uses fewer WHERE clause terms than Y
1954 ** (3) Every WHERE clause term used by X is also used by Y
1955 ** (4) X skips at least as many columns as Y
1956 ** (5) If X is a covering index, than Y is too
1957 **
1958 ** Conditions (2) and (3) mean that X is a "proper subset" of Y.
1959 ** If X is a proper subset of Y then Y is a better choice and ought
1960 ** to have a lower cost. This routine returns TRUE when that cost
1961 ** relationship is inverted and needs to be adjusted. Constraint (4)
1962 ** was added because if X uses skip-scan less than Y it still might
1963 ** deserve a lower cost even if it is a proper subset of Y. Constraint (5)
1964 ** was added because a covering index probably deserves to have a lower cost
1965 ** than a non-covering index even if it is a proper subset.
1966 */
1970 ){
1974 }
1979 }
1984 }
1986 }
1990 }
1992 }
1994 /*
1995 ** Try to adjust the cost of WhereLoop pTemplate upwards or downwards so
1996 ** that:
1997 **
1998 ** (1) pTemplate costs less than any other WhereLoops that are a proper
1999 ** subset of pTemplate
2000 **
2001 ** (2) pTemplate costs more than any other WhereLoops for which pTemplate
2002 ** is a proper subset.
2003 **
2004 ** To say "WhereLoop X is a proper subset of Y" means that X uses fewer
2005 ** WHERE clause terms than Y and that every WHERE clause term used by X is
2006 ** also used by Y.
2007 */
2014 /* Adjust pTemplate cost downward so that it is cheaper than its
2015 ** subset p. */
2021 /* Adjust pTemplate cost upward so that it is costlier than p since
2022 ** pTemplate is a proper subset of p */
2027 }
2028 }
2029 }
2031 /*
2032 ** Search the list of WhereLoops in *ppPrev looking for one that can be
2033 ** replaced by pTemplate.
2034 **
2035 ** Return NULL if pTemplate does not belong on the WhereLoop list.
2036 ** In other words if pTemplate ought to be dropped from further consideration.
2037 **
2038 ** If pX is a WhereLoop that pTemplate can replace, then return the
2039 ** link that points to pX.
2040 **
2041 ** If pTemplate cannot replace any existing element of the list but needs
2042 ** to be added to the list as a new entry, then return a pointer to the
2043 ** tail of the list.
2044 */
2048 ){
2052 /* If either the iTab or iSortIdx values for two WhereLoop are different
2053 ** then those WhereLoops need to be considered separately. Neither is
2054 ** a candidate to replace the other. */
2056 }
2057 /* In the current implementation, the rSetup value is either zero
2058 ** or the cost of building an automatic index (NlogN) and the NlogN
2059 ** is the same for compatible WhereLoops. */
2063 /* whereLoopAddBtree() always generates and inserts the automatic index
2064 ** case first. Hence compatible candidate WhereLoops never have a larger
2065 ** rSetup. Call this SETUP-INVARIANT */
2068 /* Any loop using an appliation-defined index (or PRIMARY KEY or
2069 ** UNIQUE constraint) with one or more == constraints is better
2070 ** than an automatic index. Unless it is a skip-scan. */
2076 ){
2078 }
2080 /* If existing WhereLoop p is better than pTemplate, pTemplate can be
2081 ** discarded. WhereLoop p is better if:
2082 ** (1) p has no more dependencies than pTemplate, and
2083 ** (2) p has an equal or lower cost than pTemplate
2084 */
2089 ){
2091 }
2093 /* If pTemplate is always better than p, then cause p to be overwritten
2094 ** with pTemplate. pTemplate is better than p if:
2095 ** (1) pTemplate has no more dependences than p, and
2096 ** (2) pTemplate has an equal or lower cost than p.
2097 */
2101 ){
2104 }
2105 }
2107 }
2109 /*
2110 ** Insert or replace a WhereLoop entry using the template supplied.
2111 **
2112 ** An existing WhereLoop entry might be overwritten if the new template
2113 ** is better and has fewer dependencies. Or the template will be ignored
2114 ** and no insert will occur if an existing WhereLoop is faster and has
2115 ** fewer dependencies than the template. Otherwise a new WhereLoop is
2116 ** added based on the template.
2117 **
2118 ** If pBuilder->pOrSet is not NULL then we care about only the
2119 ** prerequisites and rRun and nOut costs of the N best loops. That
2120 ** information is gathered in the pBuilder->pOrSet object. This special
2121 ** processing mode is used only for OR clause processing.
2122 **
2123 ** When accumulating multiple loops (when pBuilder->pOrSet is NULL) we
2124 ** still might overwrite similar loops with the new template if the
2125 ** new template is better. Loops may be overwritten if the following
2126 ** conditions are met:
2127 **
2128 ** (1) They have the same iTab.
2129 ** (2) They have the same iSortIdx.
2130 ** (3) The template has same or fewer dependencies than the current loop
2131 ** (4) The template has the same or lower cost than the current loop
2132 */
2139 /* Stop the search once we hit the query planner search limit */
2144 }
2149 /* If pBuilder->pOrSet is defined, then only keep track of the costs
2150 ** and prereqs.
2151 */
2154 #if WHERETRACE_ENABLED
2157 #endif
2164 }
2165 #endif
2166 }
2168 }
2170 /* Look for an existing WhereLoop to replace with pTemplate
2171 */
2175 /* There already exists a WhereLoop on the list that is better
2176 ** than pTemplate, so just ignore pTemplate */
2181 }
2182 #endif
2186 }
2188 /* If we reach this point it means that either p[] should be overwritten
2189 ** with pTemplate[] if p[] exists, or if p==NULL then allocate a new
2190 ** WhereLoop and insert it.
2191 */
2200 }
2202 }
2203 #endif
2205 /* Allocate a new WhereLoop to add to the end of the list */
2211 /* We will be overwriting WhereLoop p[]. But before we do, first
2212 ** go through the rest of the list and delete any other entries besides
2213 ** p[] that are also supplated by pTemplate */
2226 }
2227 #endif
2229 }
2230 }
2236 }
2237 }
2239 }
2241 /*
2242 ** Adjust the WhereLoop.nOut value downward to account for terms of the
2243 ** WHERE clause that reference the loop but which are not used by an
2244 ** index.
2245 *
2246 ** For every WHERE clause term that is not used by the index
2247 ** and which has a truth probability assigned by one of the likelihood(),
2248 ** likely(), or unlikely() SQL functions, reduce the estimated number
2249 ** of output rows by the probability specified.
2250 **
2251 ** TUNING: For every WHERE clause term that is not used by the index
2252 ** and which does not have an assigned truth probability, heuristics
2253 ** described below are used to try to estimate the truth probability.
2254 ** TODO --> Perhaps this is something that could be improved by better
2255 ** table statistics.
2256 **
2257 ** Heuristic 1: Estimate the truth probability as 93.75%. The 93.75%
2258 ** value corresponds to -1 in LogEst notation, so this means decrement
2259 ** the WhereLoop.nOut field for every such WHERE clause term.
2260 **
2261 ** Heuristic 2: If there exists one or more WHERE clause terms of the
2262 ** form "x==EXPR" and EXPR is not a constant 0 or 1, then make sure the
2263 ** final output row estimate is no greater than 1/4 of the total number
2264 ** of rows in the table. In other words, assume that x==EXPR will filter
2265 ** out at least 3 out of 4 rows. If EXPR is -1 or 0 or 1, then maybe the
2266 ** "x" column is boolean or else -1 or 0 or 1 is a common default value
2267 ** on the "x" column and so in that case only cap the output row estimate
2268 ** at 1/2 instead of 1/4.
2269 */
2273 LogEst nRow /* Number of rows in the entire table */
2274 ){
2291 }
2294 /* If a truth probability is specified using the likelihood() hints,
2295 ** then use the probability provided by the application. */
2298 /* In the absence of explicit truth probabilities, use heuristics to
2299 ** guess a reasonable truth probability. */
2303 ){
2311 }
2315 }
2316 }
2317 }
2318 }
2319 }
2321 }
2323 /*
2324 ** Term pTerm is a vector range comparison operation. The first comparison
2325 ** in the vector can be optimized using column nEq of the index. This
2326 ** function returns the total number of vector elements that can be used
2327 ** as part of the range comparison.
2328 **
2329 ** For example, if the query is:
2330 **
2331 ** WHERE a = ? AND (b, c, d) > (?, ?, ?)
2332 **
2333 ** and the index:
2334 **
2335 ** CREATE INDEX ... ON (a, b, c, d, e)
2336 **
2337 ** then this function would be invoked with nEq=1. The value returned in
2338 ** this case is 3.
2339 */
2346 ){
2352 /* Test if comparison i of pTerm is compatible with column (i+nEq)
2353 ** of the index. If not, exit the loop. */
2363 }
2365 /* Check that the LHS of the comparison is a column reference to
2366 ** the right column of the right source table. And that the sort
2367 ** order of the index column is the same as the sort order of the
2368 ** leftmost index column. */
2373 ){
2375 }
2385 }
2387 }
2389 /*
2390 ** Adjust the cost C by the costMult facter T. This only occurs if
2391 ** compiled with -DSQLITE_ENABLE_COSTMULT
2392 */
2393 #ifdef SQLITE_ENABLE_COSTMULT
2394 # define ApplyCostMultiplier(C,T) C += T
2395 #else
2396 # define ApplyCostMultiplier(C,T)
2397 #endif
2399 /*
2400 ** We have so far matched pBuilder->pNew->u.btree.nEq terms of the
2401 ** index pIndex. Try to match one more.
2402 **
2403 ** When this function is called, pBuilder->pNew->nOut contains the
2404 ** number of rows expected to be visited by filtering using the nEq
2405 ** terms only. If it is modified, this value is restored before this
2406 ** function returns.
2407 **
2408 ** If pProbe->idxType==SQLITE_IDXTYPE_IPK, that means pIndex is
2409 ** a fake index used for the INTEGER PRIMARY KEY.
2410 */
2415 LogEst nInMul /* log(Number of iterations due to IN) */
2416 ){
2450 }
2470 LogEst rCostIdx;
2473 #ifdef SQLITE_ENABLE_STAT4
2475 #endif
2478 ){
2480 }
2483 /* Do not allow the upper bound of a LIKE optimization range constraint
2484 ** to mix with a lower range bound from some other source */
2487 /* tag-20191211-001: Do not allow constraints from the WHERE clause to
2488 ** be used by the right table of a LEFT JOIN. Only constraints in the
2489 ** ON clause are allowed. See tag-20191211-002 for the vtab equivalent. */
2492 ){
2494 }
2500 }
2514 );
2519 /* "x IN (SELECT ...)": TUNING: the SELECT returns 25 rows */
2523 /* The expression may actually be of the form (x, y) IN (SELECT...).
2524 ** In this case there is a separate term for each of (x) and (y).
2525 ** However, the nIn multiplier should only be applied once, not once
2526 ** for each such term. The following loop checks that pTerm is the
2527 ** first such term in use, and sets nIn back to 0 if it is not. */
2530 }
2532 /* "x IN (value, value, ...)" */
2534 }
2537 /* Let:
2538 ** N = the total number of rows in the table
2539 ** K = the number of entries on the RHS of the IN operator
2540 ** M = the number of rows in the table that match terms to the
2541 ** to the left in the same index. If the IN operator is on
2542 ** the left-most index column, M==N.
2543 **
2544 ** Given the definitions above, it is better to omit the IN operator
2545 ** from the index lookup and instead do a scan of the M elements,
2546 ** testing each scanned row against the IN operator separately, if:
2547 **
2548 ** M*log(K) < K*log(N)
2549 **
2550 ** Our estimates for M, K, and N might be inaccurate, so we build in
2551 ** a safety margin of 2 (LogEst: 10) that favors using the IN operator
2552 ** with the index, as using an index has better worst-case behavior.
2553 ** If we do not have real sqlite_stat1 data, always prefer to use
2554 ** the index.
2555 */
2568 }
2569 }
2577 ){
2580 ){
2584 }
2585 }
2594 );
2598 /* Range contraints that come from the LIKE optimization are
2599 ** always used in pairs. */
2608 }
2616 );
2620 }
2622 /* At this point pNew->nOut is set to the number of rows expected to
2623 ** be visited by the index scan before considering term pTerm, or the
2624 ** values of nIn and nInMul. In other words, assuming that all
2625 ** "x IN(...)" terms are replaced with "x = ?". This block updates
2626 ** the value of pNew->nOut to account for pTerm (but not nIn/nInMul). */
2629 /* Adjust nOut using stat4 data. Or, if there is no stat4
2630 ** data, using some other estimate. */
2643 #ifdef SQLITE_ENABLE_STAT4
2650 ){
2659 }
2665 /* TUNING: Mark terms as "low selectivity" if they seem likely
2666 ** to be true for half or more of the rows in the table.
2667 ** See tag-202002240-1 */
2669 ){
2675 }
2676 #endif
2679 /* If the term has previously been used with an assumption of
2680 ** higher selectivity, then set the flag to rerun the
2681 ** loop computations. */
2683 }
2684 }
2687 }
2688 }
2690 #endif
2691 {
2694 /* TUNING: If there is no likelihood() value, assume that a
2695 ** "col IS NULL" expression matches twice as many rows
2696 ** as (col=?). */
2698 }
2699 }
2700 }
2701 }
2703 /* Set rCostIdx to the cost of visiting selected rows in index. Add
2704 ** it to pNew->rRun, which is currently set to the cost of the index
2705 ** seek only. Then, if this is a non-covering index, add the cost of
2706 ** visiting the rows in the main table. */
2712 }
2725 }
2729 ){
2731 }
2733 #ifdef SQLITE_ENABLE_STAT4
2735 #endif
2736 }
2746 /* Consider using a skip-scan if there are no WHERE clause constraints
2747 ** available for the left-most terms of the index, and if the average
2748 ** number of repeats in the left-most terms is at least 18.
2749 **
2750 ** The magic number 18 is selected on the basis that scanning 17 rows
2751 ** is almost always quicker than an index seek (even though if the index
2752 ** contains fewer than 2^17 rows we assume otherwise in other parts of
2753 ** the code). And, even if it is not, it should not be too much slower.
2754 ** On the other hand, the extra seeks could end up being significantly
2755 ** more expensive. */
2765 ){
2766 LogEst nIter;
2773 /* TUNING: Because uncertainties in the estimates for skip-scan queries,
2774 ** add a 1.375 fudge factor to make skip-scan slightly less likely. */
2781 }
2786 }
2788 /*
2789 ** Return True if it is possible that pIndex might be useful in
2790 ** implementing the ORDER BY clause in pBuilder.
2791 **
2792 ** Return False if pBuilder does not contain an ORDER BY clause or
2793 ** if there is no way for pIndex to be useful in implementing that
2794 ** ORDER BY clause.
2795 */
2799 int iCursor
2800 ){
2813 }
2819 }
2820 }
2821 }
2822 }
2824 }
2826 /* Check to see if a partial index with pPartIndexWhere can be used
2827 ** in the current query. Return true if it can be and false if not.
2828 */
2834 ){
2841 }
2849 ){
2851 }
2852 }
2854 }
2856 /*
2857 ** Add all WhereLoop objects for a single table of the join where the table
2858 ** is identified by pBuilder->pNew->iTab. That table is guaranteed to be
2859 ** a b-tree table, not a virtual table.
2860 **
2861 ** The costs (WhereLoop.rRun) of the b-tree loops added by this function
2862 ** are calculated as follows:
2863 **
2864 ** For a full scan, assuming the table (or index) contains nRow rows:
2865 **
2866 ** cost = nRow * 3.0 // full-table scan
2867 ** cost = nRow * K // scan of covering index
2868 ** cost = nRow * (K+3.0) // scan of non-covering index
2869 **
2870 ** where K is a value between 1.1 and 3.0 set based on the relative
2871 ** estimated average size of the index and table records.
2872 **
2873 ** For an index scan, where nVisit is the number of index rows visited
2874 ** by the scan, and nSeek is the number of seek operations required on
2875 ** the index b-tree:
2876 **
2877 ** cost = nSeek * (log(nRow) + K * nVisit) // covering index
2878 ** cost = nSeek * (log(nRow) + (K+3.0) * nVisit) // non-covering index
2879 **
2880 ** Normally, nSeek is 1. nSeek values greater than 1 come about if the
2881 ** WHERE clause includes "x IN (....)" terms used in place of "x=?". Or when
2882 ** implicit "x IN (SELECT x FROM tbl)" terms are added for skip-scans.
2883 **
2884 ** The estimated values (nRow, nVisit, nSeek) often contain a large amount
2885 ** of uncertainty. For this reason, scoring is designed to pick plans that
2886 ** "do the least harm" if the estimates are inaccurate. For example, a
2887 ** log(nRow) factor is omitted from a non-covering index scan in order to
2888 ** bias the scoring in favor of using an index, since the worst-case
2889 ** performance of using an index is far better than the worst-case performance
2890 ** of a full table scan.
2891 */
2894 Bitmask mPrereq /* Extra prerequesites for using this table */
2895 ){
2921 /* An INDEXED BY clause specifies a particular index to use */
2926 /* There is no INDEXED BY clause. Create a fake Index object in local
2927 ** variable sPk to represent the rowid primary key index. Make this
2928 ** fake index the first in a chain of Index objects with all of the real
2929 ** indices to follow */
2944 /* The real indices of the table are only considered if the
2945 ** NOT INDEXED qualifier is omitted from the FROM clause */
2947 }
2949 }
2953 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
2954 /* Automatic indexes */
2963 ){
2964 /* Generate auto-index WhereLoops */
2975 /* TUNING: One-time cost for computing the automatic index is
2976 ** estimated to be X*N*log2(N) where N is the number of rows in
2977 ** the table being indexed and where X is 7 (LogEst=28) for normal
2978 ** tables or 0.5 (LogEst=-10) for views and subqueries. The value
2979 ** of X is smaller for views and subqueries so that the query planner
2980 ** will be more aggressive about generating automatic indexes for
2981 ** those objects, since there is no opportunity to add schema
2982 ** indexes on subqueries and views. */
2988 }
2991 /* TUNING: Each index lookup yields 20 rows in the table. This
2992 ** is more than the usual guess of 10 rows, since we have no way
2993 ** of knowing how selective the index will ultimately be. It would
2994 ** not be unreasonable to make this value much larger. */
3000 }
3001 }
3002 }
3005 /* Loop over all indices. If there was an INDEXED BY clause, then only
3006 ** consider index pProbe. */
3009 ){
3014 ){
3017 }
3031 /* The ONEPASS_DESIRED flags never occurs together with ORDER BY */
3034 /* Integer primary key index */
3037 /* Full table scan */
3039 /* TUNING: Cost of full table scan is (N*3.0). */
3047 Bitmask m;
3054 }
3056 /* Full scan via index */
3066 )
3067 ){
3070 /* The cost of visiting the index rows is N*K, where K is
3071 ** between 1.1 and 3.0, depending on the relative sizes of the
3072 ** index and table rows. */
3075 /* If this is a non-covering index scan, add in the cost of
3076 ** doing table lookups. The cost will be 3x the number of
3077 ** lookups. Take into account WHERE clause terms that can be
3078 ** satisfied using just the index, and that do not require a
3079 ** table lookup. */
3088 }
3089 /* pTerm can be evaluated using just the index. So reduce
3090 ** the expected number of table lookups accordingly */
3094 nLookup--;
3096 }
3097 }
3100 }
3106 }
3107 }
3112 /* If a non-unique index is used, or if a prefix of the key for
3113 ** unique index is used (making the index functionally non-unique)
3114 ** then the sqlite_stat1 data becomes important for scoring the
3115 ** plan */
3117 }
3118 #ifdef SQLITE_ENABLE_STAT4
3122 #endif
3123 }
3125 }
3127 #ifndef SQLITE_OMIT_VIRTUALTABLE
3129 /*
3130 ** Argument pIdxInfo is already populated with all constraints that may
3131 ** be used by the virtual table identified by pBuilder->pNew->iTab. This
3132 ** function marks a subset of those constraints usable, invokes the
3133 ** xBestIndex method and adds the returned plan to pBuilder.
3134 **
3135 ** A constraint is marked usable if:
3136 **
3137 ** * Argument mUsable indicates that its prerequisites are available, and
3138 **
3139 ** * It is not one of the operators specified in the mExclude mask passed
3140 ** as the fourth argument (which in practice is either WO_IN or 0).
3141 **
3142 ** Argument mPrereq is a mask of tables that must be scanned before the
3143 ** virtual table in question. These are added to the plans prerequisites
3144 ** before it is added to pBuilder.
3145 **
3146 ** Output parameter *pbIn is set to true if the plan added to pBuilder
3147 ** uses one or more WO_IN terms, or false otherwise.
3148 */
3157 ){
3173 /* Set the usable flag on the subset of constraints identified by
3174 ** arguments mUsable and mExclude. */
3181 ){
3183 }
3184 }
3186 /* Initialize the output fields of the sqlite3_index_info structure */
3197 /* Invoke the virtual table xBestIndex() method */
3201 /* If the xBestIndex method returns SQLITE_CONSTRAINT, that means
3202 ** that the particular combination of parameters provided is unusable.
3203 ** Make no entries in the loop table.
3204 */
3207 }
3209 }
3226 ){
3230 }
3247 }
3248 }
3250 /* A virtual table that is constrained by an IN clause may not
3251 ** consume the ORDER BY clause because (1) the order of IN terms
3252 ** is not necessarily related to the order of output terms and
3253 ** (2) Multiple outputs from a single IN value will not merge
3254 ** together. */
3258 }
3259 }
3260 }
3265 /* The non-zero argvIdx values must be contiguous. Raise an
3266 ** error if they are not */
3270 }
3271 }
3283 /* Set the WHERE_ONEROW flag if the xBestIndex() method indicated
3284 ** that the scan will visit at most one row. Clear it otherwise. */
3289 }
3294 }
3300 }
3302 /*
3303 ** If this function is invoked from within an xBestIndex() callback, it
3304 ** returns a pointer to a buffer containing the name of the collation
3305 ** sequence associated with element iCons of the sqlite3_index_info.aConstraint
3306 ** array. Or, if iCons is out of range or there is no active xBestIndex
3307 ** call, return NULL.
3308 */
3318 }
3320 }
3322 }
3324 /*
3325 ** Add all WhereLoop objects for a table of the join identified by
3326 ** pBuilder->pNew->iTab. That table is guaranteed to be a virtual table.
3327 **
3328 ** If there are no LEFT or CROSS JOIN joins in the query, both mPrereq and
3329 ** mUnusable are set to 0. Otherwise, mPrereq is a mask of all FROM clause
3330 ** entries that occur before the virtual table in the FROM clause and are
3331 ** separated from it by at least one LEFT or CROSS JOIN. Similarly, the
3332 ** mUnusable mask contains all FROM clause entries that occur after the
3333 ** virtual table and are separated from it by at least one LEFT or
3334 ** CROSS JOIN.
3335 **
3336 ** For example, if the query were:
3337 **
3338 ** ... FROM t1, t2 LEFT JOIN t3, t4, vt CROSS JOIN t5, t6;
3339 **
3340 ** then mPrereq corresponds to (t1, t2) and mUnusable to (t5, t6).
3341 **
3342 ** All the tables in mPrereq must be scanned before the current virtual
3343 ** table. So any terms for which all prerequisites are satisfied by
3344 ** mPrereq may be specified as "usable" in all calls to xBestIndex.
3345 ** Conversely, all tables in mUnusable must be scanned after the current
3346 ** virtual table, so any terms for which the prerequisites overlap with
3347 ** mUnusable should always be configured as "not-usable" for xBestIndex.
3348 */
3352 Bitmask mUnusable /* Tables that must be scanned after this one */
3353 ){
3364 u16 mNoOmit;
3384 }
3386 /* First call xBestIndex() with all constraints usable. */
3391 /* If the call to xBestIndex() with all terms enabled produced a plan
3392 ** that does not require any source tables (IOW: a plan with mBest==0)
3393 ** and does not use an IN(...) operator, then there is no point in making
3394 ** any further calls to xBestIndex() since they will all return the same
3395 ** result (if the xBestIndex() implementation is sane). */
3402 /* If the plan produced by the earlier call uses an IN(...) term, call
3403 ** xBestIndex again, this time with IN(...) terms disabled. */
3413 }
3414 }
3416 /* Call xBestIndex once for each distinct value of (prereqRight & ~mPrereq)
3417 ** in the set of terms that apply to the current virtual table. */
3423 Bitmask mThis = (
3425 );
3427 }
3438 }
3439 }
3441 /* If the calls to xBestIndex() in the above loop did not find a plan
3442 ** that requires no source tables at all (i.e. one guaranteed to be
3443 ** usable), make a call here with all source tables disabled */
3449 }
3451 /* If the calls to xBestIndex() have so far failed to find a plan
3452 ** that requires no source tables at all and does not use an IN(...)
3453 ** operator, make a final call to obtain one here. */
3458 }
3459 }
3465 }
3468 /*
3469 ** Add WhereLoop entries to handle OR terms. This works for either
3470 ** btrees or virtual tables.
3471 */
3474 Bitmask mPrereq,
3475 Bitmask mUnusable
3476 ){
3483 WhereClause tempWC;
3484 WhereLoopBuilder sSubBuild;
3498 ){
3522 }
3524 #ifdef WHERETRACE_ENABLED
3529 }
3530 #endif
3531 #ifndef SQLITE_OMIT_VIRTUALTABLE
3535 #endif
3536 {
3538 }
3541 }
3551 WhereOrSet sPrev;
3559 }
3560 }
3561 }
3562 }
3570 /* TUNING: Currently sSum.a[i].rRun is set to the sum of the costs
3571 ** of all sub-scans required by the OR-scan. However, due to rounding
3572 ** errors, it may be that the cost of the OR-scan is equal to its
3573 ** most expensive sub-scan. Add the smallest possible penalty
3574 ** (equivalent to multiplying the cost by 1.07) to ensure that
3575 ** this does not happen. Otherwise, for WHERE clauses such as the
3576 ** following where there is an index on "y":
3577 **
3578 ** WHERE likelihood(x=?, 0.99) OR y=?
3579 **
3580 ** the planner may elect to "OR" together a full-table scan and an
3581 ** index lookup. And other similarly odd results. */
3586 }
3588 }
3589 }
3591 }
3593 /*
3594 ** Add all WhereLoop objects for all tables
3595 */
3609 /* Loop over the tables in the join, from left to right */
3619 /* This condition is true when pItem is the FROM clause term on the
3620 ** right-hand-side of a LEFT or CROSS JOIN. */
3622 }
3624 #ifndef SQLITE_OMIT_VIRTUALTABLE
3630 }
3631 }
3635 {
3637 }
3640 }
3644 /* We hit the query planner search limit set by iPlanLimit */
3649 }
3650 }
3651 }
3655 }
3657 /*
3658 ** Examine a WherePath (with the addition of the extra WhereLoop of the 6th
3659 ** parameters) to see if it outputs rows in the requested ORDER BY
3660 ** (or GROUP BY) without requiring a separate sort operation. Return N:
3661 **
3662 ** N>0: N terms of the ORDER BY clause are satisfied
3663 ** N==0: No terms of the ORDER BY clause are satisfied
3664 ** N<0: Unknown yet how many terms of ORDER BY might be satisfied.
3665 **
3666 ** Note that processing for WHERE_GROUPBY and WHERE_DISTINCTBY is not as
3667 ** strict. With GROUP BY and DISTINCT the only requirement is that
3668 ** equivalent rows appear immediately adjacent to one another. GROUP BY
3669 ** and DISTINCT do not require rows to appear in any particular order as long
3670 ** as equivalent rows are grouped together. Thus for GROUP BY and DISTINCT
3671 ** the pOrderBy terms can be matched in any order. With ORDER BY, the
3672 ** pOrderBy terms must be matched in strict left-to-right order.
3673 */
3682 ){
3708 /*
3709 ** We say the WhereLoop is "one-row" if it generates no more than one
3710 ** row of output. A WhereLoop is one-row if all of the following are true:
3711 ** (a) All index columns match with WHERE_COLUMN_EQ.
3712 ** (b) The index is unique
3713 ** Any WhereLoop with an WHERE_COLUMN_EQ constraint on the rowid is one-row.
3714 ** Every one-row WhereLoop will have the WHERE_ONEROW bit set in wsFlags.
3715 **
3716 ** We say the WhereLoop is "order-distinct" if the set of columns from
3717 ** that WhereLoop that are in the ORDER BY clause are different for every
3718 ** row of the WhereLoop. Every one-row WhereLoop is automatically
3719 ** order-distinct. A WhereLoop that has no columns in the ORDER BY clause
3720 ** is not order-distinct. To be order-distinct is not quite the same as being
3721 ** UNIQUE since a UNIQUE column or index can have multiple rows that
3722 ** are NULL and NULL values are equivalent for the purpose of order-distinct.
3723 ** To be order-distinct, the columns must be UNIQUE and NOT NULL.
3724 **
3725 ** The rowid for a table is always UNIQUE and NOT NULL so whenever the
3726 ** rowid appears in the ORDER BY clause, the corresponding WhereLoop is
3727 ** automatically order-distinct.
3728 */
3749 }
3753 }
3757 }
3760 /* Mark off any ORDER BY term X that is a column in the table of
3761 ** the current loop for which there is term in the WHERE
3762 ** clause of the form X IS NULL or X=? that reference only outer
3763 ** loops.
3764 */
3774 /* IN terms are only valid for sorting in the ORDER BY LIMIT
3775 ** optimization, and then only if they are actually used
3776 ** by the query plan */
3780 }
3788 }
3790 }
3792 }
3809 }
3811 /* Loop through all columns of the index and deal with the ones
3812 ** that are not constrained by == or IN.
3813 */
3821 );
3825 /* Skip over == and IS and ISNULL terms. (Also skip IN terms when
3826 ** doing WHERE_ORDERBY_LIMIT processing). Except, IS and ISNULL
3827 ** terms imply that the index is not UNIQUE NOT NULL in which case
3828 ** the loop need to be marked as not order-distinct because it can
3829 ** have repeated NULL rows.
3830 **
3831 ** If the current term is a column of an ((?,?) IN (SELECT...))
3832 ** expression for which the SELECT returns more than one column,
3833 ** check that it is the only column used by this loop. Otherwise,
3834 ** if it is one of two or more, none of the columns can be
3835 ** considered to match an ORDER BY term.
3836 */
3843 }
3846 /* ALWAYS() justification: eOp is an equality operator due to the
3847 ** j<pLoop->u.btree.nEq constraint above. Any equality other
3848 ** than WO_IN is captured by the previous "if". So this one
3849 ** always has to be WO_IN. */
3856 }
3857 }
3858 }
3859 }
3861 /* Get the column number in the table (iColumn) and sort order
3862 ** (revIdx) for the j-th column of the index.
3863 */
3871 }
3873 /* An unconstrained column that might be NULL means that this
3874 ** WhereLoop is not well-ordered
3875 */
3880 ){
3882 }
3884 /* Find the ORDER BY term that corresponds to the j-th column
3885 ** of the index and mark that ORDER BY term off
3886 */
3902 }
3903 }
3907 }
3910 }
3913 }
3915 /* Make sure the sort order is compatible in an ORDER BY clause.
3916 ** Sort order is irrelevant for a GROUP BY clause. */
3920 }
3925 }
3926 }
3932 }
3933 }
3938 }
3941 /* No match found */
3945 }
3947 }
3952 }
3955 /* Mark off any other ORDER BY terms that reference pLoop */
3960 Bitmask mTerm;
3967 }
3968 }
3969 }
3976 }
3978 }
3980 }
3983 /*
3984 ** If the WHERE_GROUPBY flag is set in the mask passed to sqlite3WhereBegin(),
3985 ** the planner assumes that the specified pOrderBy list is actually a GROUP
3986 ** BY clause - and so any order that groups rows as required satisfies the
3987 ** request.
3988 **
3989 ** Normally, in this case it is not possible for the caller to determine
3990 ** whether or not the rows are really being delivered in sorted order, or
3991 ** just in some other order that provides the required grouping. However,
3992 ** if the WHERE_SORTBYGROUP flag is also passed to sqlite3WhereBegin(), then
3993 ** this function may be called on the returned WhereInfo object. It returns
3994 ** true if the rows really will be sorted in the specified order, or false
3995 ** otherwise.
3996 **
3997 ** For example, assuming:
3998 **
3999 ** CREATE INDEX i1 ON t1(x, Y);
4000 **
4001 ** then
4002 **
4003 ** SELECT * FROM t1 GROUP BY x,y ORDER BY x,y; -- IsSorted()==1
4004 ** SELECT * FROM t1 GROUP BY y,x ORDER BY y,x; -- IsSorted()==0
4005 */
4010 }
4012 #ifdef WHERETRACE_ENABLED
4013 /* For debugging use only: */
4021 }
4022 #endif
4024 /*
4025 ** Return the cost of sorting nRow rows, assuming that the keys have
4026 ** nOrderby columns and that the first nSorted columns are already in
4027 ** order.
4028 */
4031 LogEst nRow,
4033 int nSorted
4034 ){
4035 /* TUNING: Estimated cost of a full external sort, where N is
4036 ** the number of rows to sort is:
4037 **
4038 ** cost = (3.0 * N * log(N)).
4039 **
4040 ** Or, if the order-by clause has X terms but only the last Y
4041 ** terms are out of order, then block-sorting will reduce the
4042 ** sorting cost to:
4043 **
4044 ** cost = (3.0 * N * log(N)) * (Y/X)
4045 **
4046 ** The (Y/X) term is implemented using stack variable rScale
4047 ** below. */
4053 /* Multiple by log(M) where M is the number of output rows.
4054 ** Use the LIMIT for M if it is smaller */
4057 }
4060 }
4062 /*
4063 ** Given the list of WhereLoop objects at pWInfo->pLoops, this routine
4064 ** attempts to find the lowest cost path that visits each WhereLoop
4065 ** once. This path is then loaded into the pWInfo->a[].pWLoop fields.
4066 **
4067 ** Assume that the total number of output rows that will need to be sorted
4068 ** will be nRowEst (in the 10*log2 representation). Or, ignore sorting
4069 ** costs if nRowEst==0.
4070 **
4071 ** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation
4072 ** error occurs.
4073 */
4099 /* TUNING: For simple queries, only the best path is tracked.
4100 ** For 2-way joins, the 5 best paths are followed.
4101 ** For joins of 3 or more tables, track the 10 best paths */
4106 /* If nRowEst is zero and there is an ORDER BY clause, ignore it. In this
4107 ** case the purpose of this call is to estimate the number of rows returned
4108 ** by the overall query. Once this estimate has been obtained, the caller
4109 ** will invoke this function a second time, passing the estimate as the
4110 ** nRowEst parameter. */
4115 }
4117 /* Allocate and initialize space for aTo, aFrom and aSortCost[] */
4128 }
4130 /* If there is an ORDER BY clause and it is not being ignored, set up
4131 ** space for the aSortCost[] array. Each element of the aSortCost array
4132 ** is either zero - meaning it has not yet been initialized - or the
4133 ** cost of sorting nRowEst rows of data where the first X terms of
4134 ** the ORDER BY clause are already in order, where X is the array
4135 ** index. */
4138 }
4142 /* Seed the search with a single WherePath containing zero WhereLoops.
4143 **
4144 ** TUNING: Do not let the number of iterations go above 28. If the cost
4145 ** of computing an automatic index is not paid back within the first 28
4146 ** rows, then do not use the automatic index. */
4151 /* If nLoop is zero, then there are no FROM terms in the query. Since
4152 ** in this case the query may return a maximum of one row, the results
4153 ** are already in the requested order. Set isOrdered to nOrderBy to
4154 ** indicate this. Or, if nLoop is greater than zero, set isOrdered to
4155 ** -1, indicating that the result set may or may not be ordered,
4156 ** depending on the loops added to the current plan. */
4158 }
4160 /* Compute successively longer WherePaths using the previous generation
4161 ** of WherePaths as the basis for the next. Keep track of the mxChoice
4162 ** best paths at each generation */
4177 /* Do not use an automatic index if the this loop is expected
4178 ** to run less than 1.25 times. It is tempting to also exclude
4179 ** automatic index usage on an outer loop, but sometimes an automatic
4180 ** index is useful in the outer loop of a correlated subquery. */
4183 }
4185 /* At this point, pWLoop is a candidate to be the next loop.
4186 ** Compute its cost */
4197 }
4202 );
4203 }
4204 /* TUNING: Add a small extra penalty (5) to sorting as an
4205 ** extra encouragment to the query planner to select a plan
4206 ** where the rows emerge in the correct order without any sorting
4207 ** required. */
4217 }
4219 /* Check to see if pWLoop should be added to the set of
4220 ** mxChoice best-so-far paths.
4221 **
4222 ** First look for an existing path among best-so-far paths
4223 ** that covers the same set of loops and has the same isOrdered
4224 ** setting as the current path candidate.
4225 **
4226 ** The term "((pTo->isOrdered^isOrdered)&0x80)==0" is equivalent
4227 ** to (pTo->isOrdered==(-1))==(isOrdered==(-1))" for the range
4228 ** of legal values for isOrdered, -1..64.
4229 */
4233 ){
4236 }
4237 }
4239 /* None of the existing best-so-far paths match the candidate. */
4242 ){
4243 /* The current candidate is no better than any of the mxChoice
4244 ** paths currently in the best-so-far buffer. So discard
4245 ** this candidate as not viable. */
4251 }
4252 #endif
4254 }
4255 /* If we reach this points it means that the new candidate path
4256 ** needs to be added to the set of best-so-far paths. */
4258 /* Increase the size of the aTo set by one */
4261 /* New path replaces the prior worst to keep count below mxChoice */
4263 }
4270 }
4271 #endif
4273 /* Control reaches here if best-so-far path pTo=aTo[jj] covers the
4274 ** same set of loops and has the same isOrdered setting as the
4275 ** candidate path. Check to see if the candidate should replace
4276 ** pTo or if the candidate should be skipped.
4277 **
4278 ** The conditional is an expanded vector comparison equivalent to:
4279 ** (pTo->rCost,pTo->nRow,pTo->rUnsorted) <= (rCost,nOut,rUnsorted)
4280 */
4285 )
4286 )
4287 ){
4297 }
4298 #endif
4299 /* Discard the candidate path from further consideration */
4302 }
4304 /* Control reaches here if the candidate path is better than the
4305 ** pTo path. Replace pTo with the candidate. */
4315 }
4316 #endif
4317 }
4318 /* pWLoop is a winner. Add it to the set of best so far */
4334 ){
4338 }
4339 }
4340 }
4341 }
4342 }
4355 }
4356 }
4357 }
4358 #endif
4360 /* Swap the roles of aFrom and aTo for the next generation */
4365 }
4371 }
4373 /* Find the lowest cost path. pFrom will be left pointing to that path */
4377 }
4379 /* Load the lowest cost path into pWInfo */
4385 }
4389 && nRowEst
4390 ){
4391 Bitmask notUsed;
4396 }
4397 }
4403 }
4413 ){
4422 }
4423 }
4424 }
4425 }
4426 }
4429 ){
4433 );
4438 }
4439 }
4440 }
4445 /* Free temporary memory and return success */
4448 }
4450 /*
4451 ** Most queries use only a single table (they are not joins) and have
4452 ** simple == constraints against indexed fields. This routine attempts
4453 ** to plan those simple cases using much less ceremony than the
4454 ** general-purpose query planner, and thereby yield faster sqlite3_prepare()
4455 ** times for the common case.
4456 **
4457 ** Return non-zero on success, if this query can be handled by this
4458 ** no-frills query planner. Return zero if this query needs the
4459 ** general-purpose query planner.
4460 */
4491 /* TUNING: Cost of a rowid lookup is 10 */
4507 }
4512 }
4516 /* TUNING: Cost of a unique index lookup is 15 */
4519 }
4520 }
4531 }
4532 #ifdef SQLITE_DEBUG
4534 #endif
4536 }
4538 }
4540 /*
4541 ** Helper function for exprIsDeterministic().
4542 */
4547 }
4549 }
4551 /*
4552 ** Return true if the expression contains no non-deterministic SQL
4553 ** functions. Do not consider non-deterministic SQL functions that are
4554 ** part of sub-select statements.
4555 */
4557 Walker w;
4564 }
4567 #ifdef WHERETRACE_ENABLED
4568 /*
4569 ** Display all WhereLoops in pWInfo
4570 */
4580 }
4581 }
4582 }
4583 # define WHERETRACE_ALL_LOOPS(W,C) showAllWhereLoops(W,C)
4584 #else
4585 # define WHERETRACE_ALL_LOOPS(W,C)
4586 #endif
4588 /*
4589 ** Generate the beginning of the loop used for WHERE clause processing.
4590 ** The return value is a pointer to an opaque structure that contains
4591 ** information needed to terminate the loop. Later, the calling routine
4592 ** should invoke sqlite3WhereEnd() with the return value of this function
4593 ** in order to complete the WHERE clause processing.
4594 **
4595 ** If an error occurs, this routine returns NULL.
4596 **
4597 ** The basic idea is to do a nested loop, one loop for each table in
4598 ** the FROM clause of a select. (INSERT and UPDATE statements are the
4599 ** same as a SELECT with only a single table in the FROM clause.) For
4600 ** example, if the SQL is this:
4601 **
4602 ** SELECT * FROM t1, t2, t3 WHERE ...;
4603 **
4604 ** Then the code generated is conceptually like the following:
4605 **
4606 ** foreach row1 in t1 do \ Code generated
4607 ** foreach row2 in t2 do |-- by sqlite3WhereBegin()
4608 ** foreach row3 in t3 do /
4609 ** ...
4610 ** end \ Code generated
4611 ** end |-- by sqlite3WhereEnd()
4612 ** end /
4613 **
4614 ** Note that the loops might not be nested in the order in which they
4615 ** appear in the FROM clause if a different order is better able to make
4616 ** use of indices. Note also that when the IN operator appears in
4617 ** the WHERE clause, it might result in additional nested loops for
4618 ** scanning through all values on the right-hand side of the IN.
4619 **
4620 ** There are Btree cursors associated with each table. t1 uses cursor
4621 ** number pTabList->a[0].iCursor. t2 uses the cursor pTabList->a[1].iCursor.
4622 ** And so forth. This routine generates code to open those VDBE cursors
4623 ** and sqlite3WhereEnd() generates the code to close them.
4624 **
4625 ** The code that sqlite3WhereBegin() generates leaves the cursors named
4626 ** in pTabList pointing at their appropriate entries. The [...] code
4627 ** can use OP_Column and OP_Rowid opcodes on these cursors to extract
4628 ** data from the various tables of the loop.
4629 **
4630 ** If the WHERE clause is empty, the foreach loops must each scan their
4631 ** entire tables. Thus a three-way join is an O(N^3) operation. But if
4632 ** the tables have indices and there are terms in the WHERE clause that
4633 ** refer to those indices, a complete table scan can be avoided and the
4634 ** code will run much faster. Most of the work of this routine is checking
4635 ** to see if there are indices that can be used to speed up the loop.
4636 **
4637 ** Terms of the WHERE clause are also used to limit which rows actually
4638 ** make it to the "..." in the middle of the loop. After each "foreach",
4639 ** terms of the WHERE clause that use only terms in that loop and outer
4640 ** loops are evaluated and if false a jump is made around all subsequent
4641 ** inner loops (or around the "..." if the test occurs within the inner-
4642 ** most loop)
4643 **
4644 ** OUTER JOINS
4645 **
4646 ** An outer join of tables t1 and t2 is conceptally coded as follows:
4647 **
4648 ** foreach row1 in t1 do
4649 ** flag = 0
4650 ** foreach row2 in t2 do
4651 ** start:
4652 ** ...
4653 ** flag = 1
4654 ** end
4655 ** if flag==0 then
4656 ** move the row2 cursor to a null row
4657 ** goto start
4658 ** fi
4659 ** end
4660 **
4661 ** ORDER BY CLAUSE PROCESSING
4662 **
4663 ** pOrderBy is a pointer to the ORDER BY clause (or the GROUP BY clause
4664 ** if the WHERE_GROUPBY flag is set in wctrlFlags) of a SELECT statement
4665 ** if there is one. If there is no ORDER BY clause or if this routine
4666 ** is called from an UPDATE or DELETE statement, then pOrderBy is NULL.
4667 **
4668 ** The iIdxCur parameter is the cursor number of an index. If
4669 ** WHERE_OR_SUBCLAUSE is set, iIdxCur is the cursor number of an index
4670 ** to use for OR clause processing. The WHERE clause should use this
4671 ** specific cursor. If WHERE_ONEPASS_DESIRED is set, then iIdxCur is
4672 ** the first cursor in an array of cursors for all indices. iIdxCur should
4673 ** be used to compute the appropriate cursor depending on which index is
4674 ** used.
4675 */
4684 ** If WHERE_USE_LIMIT, then the limit amount */
4685 ){
4703 ));
4705 /* Only one of WHERE_OR_SUBCLAUSE or WHERE_USE_LIMIT */
4709 /* Variable initialization */
4713 /* An ORDER/GROUP BY clause of more than 63 terms cannot be optimized */
4718 /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via
4719 ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */
4722 }
4724 /* The number of tables in the FROM clause is limited by the number of
4725 ** bits in a Bitmask
4726 */
4731 }
4733 /* This function normally generates a nested loop for all tables in
4734 ** pTabList. But if the WHERE_OR_SUBCLAUSE flag is set, then we should
4735 ** only generate code for the first table in pTabList and assume that
4736 ** any cursors associated with subsequent tables are uninitialized.
4737 */
4740 /* Allocate and initialize the WhereInfo structure that will become the
4741 ** return value. A single allocation is used to store the WhereInfo
4742 ** struct, the contents of WhereInfo.a[], the WhereClause structure
4743 ** and the WhereMaskSet structure. Since WhereClause contains an 8-byte
4744 ** field (type Bitmask) it must be aligned on an 8-byte boundary on
4745 ** some architectures. Hence the ROUND8() below.
4746 */
4753 }
4775 #ifdef SQLITE_DEBUG
4777 #endif
4779 /* Split the WHERE clause into separate subexpressions where each
4780 ** subexpression is separated by an AND operator.
4781 */
4786 /* Special case: No FROM clause
4787 */
4792 }
4795 /* Assign a bit from the bitmask to every term in the FROM clause.
4796 **
4797 ** The N-th term of the FROM clause is assigned a bitmask of 1<<N.
4798 **
4799 ** The rule of the previous sentence ensures thta if X is the bitmask for
4800 ** a table T, then X-1 is the bitmask for all other tables to the left of T.
4801 ** Knowing the bitmask for all tables to the left of a left join is
4802 ** important. Ticket #3015.
4803 **
4804 ** Note that bitmasks are created for all pTabList->nSrc tables in
4805 ** pTabList, not just the first nTabList tables. nTabList is normally
4806 ** equal to pTabList->nSrc but might be shortened to 1 if the
4807 ** WHERE_OR_SUBCLAUSE flag is set.
4808 */
4814 #ifdef SQLITE_DEBUG
4815 {
4821 }
4822 }
4823 #endif
4824 }
4826 /* Analyze all of the subexpressions. */
4830 /* Special case: WHERE terms that do not refer to any tables in the join
4831 ** (constant expressions). Evaluate each such term, and jump over all the
4832 ** generated code if the result is not true.
4833 **
4834 ** Do not do this if the expression contains non-deterministic functions
4835 ** that are not within a sub-select. This is not strictly required, but
4836 ** preserves SQLite's legacy behaviour in the following two cases:
4837 **
4838 ** FROM ... WHERE random()>0; -- eval random() once per row
4839 ** FROM ... WHERE (SELECT random())>0; -- eval random() once overall
4840 */
4847 }
4848 }
4852 /* The DISTINCT marking is pointless. Ignore it. */
4855 /* Try to ORDER BY the result set to make distinct processing easier */
4858 }
4859 }
4861 /* Construct the WhereLoop objects */
4862 #if defined(WHERETRACE_ENABLED)
4867 }
4870 Select sSelect;
4878 }
4879 }
4883 }
4884 #endif
4890 #ifdef SQLITE_ENABLE_STAT4
4891 /* If one or more WhereTerm.truthProb values were used in estimating
4892 ** loop parameters, but then those truthProb values were subsequently
4893 ** changed based on STAT4 information while computing subsequent loops,
4894 ** then we need to rerun the whole loop building process so that all
4895 ** loops will be built using the revised truthProb values. */
4905 }
4908 }
4909 #endif
4917 }
4918 }
4921 }
4924 }
4925 #ifdef WHERETRACE_ENABLED
4930 }
4935 }
4939 }
4943 }
4944 }
4948 }
4949 }
4950 #endif
4952 /* Attempt to omit tables from the join that do not affect the result.
4953 ** For a table to not affect the result, the following must be true:
4954 **
4955 ** 1) The query must not be an aggregate.
4956 ** 2) The table must be the RHS of a LEFT JOIN.
4957 ** 3) Either the query must be DISTINCT, or else the ON or USING clause
4958 ** must contain a constraint that limits the scan of the table to
4959 ** at most a single row.
4960 ** 4) The table must not be referenced by any part of the query apart
4961 ** from its own USING or ON clause.
4962 **
4963 ** For example, given:
4964 **
4965 ** CREATE TABLE t1(ipk INTEGER PRIMARY KEY, v1);
4966 ** CREATE TABLE t2(ipk INTEGER PRIMARY KEY, v2);
4967 ** CREATE TABLE t3(ipk INTEGER PRIMARY KEY, v3);
4968 **
4969 ** then table t2 can be omitted from the following:
4970 **
4971 ** SELECT v1, v3 FROM t1
4972 ** LEFT JOIN t2 ON (t1.ipk=t2.ipk)
4973 ** LEFT JOIN t3 ON (t1.ipk=t3.ipk)
4974 **
4975 ** or from:
4976 **
4977 ** SELECT DISTINCT v1, v3 FROM t1
4978 ** LEFT JOIN t2
4979 ** LEFT JOIN t3 ON (t1.ipk=t3.ipk)
4980 */
4985 ){
4990 }
4999 ){
5001 }
5008 ){
5010 }
5011 }
5012 }
5019 }
5020 }
5024 }
5026 nTabList--;
5027 }
5028 }
5029 #if defined(WHERETRACE_ENABLED)
5033 }
5035 #endif
5038 /* If the caller is an UPDATE or DELETE statement that is requesting
5039 ** to use a one-pass algorithm, determine if this is appropriate.
5040 **
5041 ** A one-pass approach can be used if the caller has requested one
5042 ** and either (a) the scan visits at most one row or (b) each
5043 ** of the following are true:
5044 **
5045 ** * the caller has indicated that a one-pass approach can be used
5046 ** with multiple rows (by setting WHERE_ONEPASS_MULTIROW), and
5047 ** * the table is not a virtual table, and
5048 ** * either the scan does not use the OR optimization or the caller
5049 ** is a DELETE operation (WHERE_DUPLICATES_OK is only specified
5050 ** for DELETE).
5051 **
5052 ** The last qualification is because an UPDATE statement uses
5053 ** WhereInfo.aiCurOnePass[1] to determine whether or not it really can
5054 ** use a one-pass approach, and this is not set accurately for scans
5055 ** that use the OR optimization.
5056 */
5066 )){
5071 }
5073 }
5074 }
5075 }
5077 /* Open all tables in the pTabList and any indices selected for
5078 ** searching those tables.
5079 */
5090 /* Do nothing */
5092 #ifndef SQLITE_OMIT_VIRTUALTABLE
5098 /* noop */
5100 #endif
5107 };
5115 ){
5116 /* If we know that only a prefix of the record will be used,
5117 ** it is advantageous to reduce the "column count" field in
5118 ** the P4 operand of the OP_OpenRead/Write opcode. */
5124 }
5125 #ifdef SQLITE_ENABLE_CURSOR_HINTS
5129 #endif
5130 {
5132 }
5133 #ifdef SQLITE_ENABLE_COLUMN_USED_MASK
5136 #endif
5139 }
5144 /* iAuxArg is always set to a positive value if ONEPASS is possible */
5148 ){
5149 /* This is one term of an OR-optimization using the PRIMARY KEY of a
5150 ** WITHOUT ROWID table. No need for a separate index */
5158 iIndexCur++;
5160 }
5168 }
5180 ){
5182 }
5184 #ifdef SQLITE_ENABLE_COLUMN_USED_MASK
5185 {
5194 }
5197 }
5199 }
5200 }
5202 }
5206 /* Generate the code to do the search. Each iteration of the for
5207 ** loop below generates code for a single nested loop of the VM
5208 ** program.
5209 */
5215 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
5220 }
5221 #endif
5224 );
5230 }
5231 }
5233 /* Done. */
5237 /* Jump here if malloc fails */
5238 whereBeginError:
5242 }
5244 }
5246 /*
5247 ** Part of sqlite3WhereEnd() will rewrite opcodes to reference the
5248 ** index rather than the main table. In SQLITE_DEBUG mode, we want
5249 ** to trace those changes if PRAGMA vdbe_addoptrace=on. This routine
5250 ** does that.
5251 */
5252 #ifndef SQLITE_DEBUG
5254 #else
5255 # define OpcodeRewriteTrace(D,K,P) sqlite3WhereOpcodeRewriteTrace(D,K,P)
5259 VdbeOp *pOp
5260 ){
5263 }
5264 #endif
5266 /*
5267 ** Generate the end of the WHERE loop. See comments on
5268 ** sqlite3WhereBegin() for additional information.
5269 */
5279 /* Generate loop termination code.
5280 */
5287 #ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT
5297 ){
5302 }
5309 }
5311 /* The common case: Advance to the next row */
5323 }
5324 #ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT
5326 #endif
5329 }
5340 /* For LEFT JOIN queries, cursor pIn->iCur may not have been
5341 ** opened yet. This occurs for WHERE clauses such as
5342 ** "a = ? AND b IN (...)", where the index is on (a, b). If
5343 ** the RHS of the (a=?) is NULL, then the "b IN (...)" may
5344 ** never have been coded, but the body of the loop run to
5345 ** return the null-row. So, if the cursor is not open yet,
5346 ** jump over the OP_Next or OP_Prev instruction about to
5347 ** be coded. */
5351 );
5353 }
5359 }
5360 }
5365 }
5367 }
5368 }
5375 }
5376 #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
5381 }
5382 #endif
5390 }
5393 ){
5395 }
5400 }
5402 }
5405 }
5407 /* The "break" point is here, just past the end of the outer loop.
5408 ** Set it.
5409 */
5422 /* For a co-routine, change all OP_Column references to the table of
5423 ** the co-routine into OP_Copy of result contained in a register.
5424 ** OP_Rowid becomes OP_Null.
5425 */
5431 }
5433 #ifdef SQLITE_ENABLE_EARLY_CURSOR_CLOSE
5434 /* Close all of the cursors that were opened by sqlite3WhereBegin.
5435 ** Except, do not close cursors that will be reused by the OR optimization
5436 ** (WHERE_OR_SUBCLAUSE). And do not close the OP_OpenWrite cursors
5437 ** created for the ONEPASS optimization.
5438 */
5442 ){
5446 }
5450 ){
5452 }
5453 }
5454 #endif
5456 /* If this scan uses an index, make VDBE code substitutions to read data
5457 ** from the index instead of from the table where possible. In some cases
5458 ** this optimization prevents the table from ever being read, which can
5459 ** yield a significant performance boost.
5460 **
5461 ** Calls to the code generator in between sqlite3WhereBegin and
5462 ** sqlite3WhereEnd will have created code that references the table
5463 ** directly. This loop scans all that code looking for opcodes
5464 ** that reference the table and converts them into opcodes that
5465 ** reference the index.
5466 */
5471 }
5475 ){
5478 #ifdef SQLITE_DEBUG
5481 }
5482 #endif
5487 #ifdef SQLITE_ENABLE_OFFSET_SQL_FUNC
5489 #endif
5490 ){
5500 }
5506 }
5516 }
5517 }
5518 #ifdef SQLITE_DEBUG
5520 #endif
5521 }
5522 }
5524 /* Undo all Expr node modifications */
5530 }
5532 /* Final cleanup
5533 */
5537 }