| blob | 7a8342675d7f6a104b9ae5f9367ebe971eea4a53 |
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 */
299 ){
303 ){
309 }
310 }
315 }
316 }
318 /* Verify the affinity and collating sequence match */
325 }
331 }
332 }
338 ){
341 }
344 #ifdef WHERETRACE_ENABLED
352 }
354 }
355 #endif
357 }
358 }
359 }
367 }
369 }
371 /*
372 ** This is whereScanInit() for the case of an index on an expression.
373 ** It is factored out into a separate tail-recursion subroutine so that
374 ** the normal whereScanInit() routine, which is a high-runner, does not
375 ** need to push registers onto the stack as part of its prologue.
376 */
380 }
382 /*
383 ** Initialize a WHERE clause scanner object. Return a pointer to the
384 ** first match. Return NULL if there are no matches.
385 **
386 ** The scanner will be searching the WHERE clause pWC. It will look
387 ** for terms of the form "X <op> <expr>" where X is column iColumn of table
388 ** iCur. Or if pIdx!=0 then X is column iColumn of index pIdx. pIdx
389 ** must be one of the indexes of table iCur.
390 **
391 ** The <op> must be one of the operators described by opMask.
392 **
393 ** If the search is for X and the WHERE clause contains terms of the
394 ** form X=Y then this routine might also return terms of the form
395 ** "Y <op> <expr>". The number of levels of transitivity is limited,
396 ** but is enough to handle most commonly occurring SQL statements.
397 **
398 ** If X is not the INTEGER PRIMARY KEY then X must be compatible with
399 ** index pIdx.
400 */
408 ){
432 }
435 }
438 }
440 /*
441 ** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
442 ** where X is a reference to the iColumn of table iCur or of index pIdx
443 ** if pIdx!=0 and <op> is one of the WO_xx operator codes specified by
444 ** the op parameter. Return a pointer to the term. Return 0 if not found.
445 **
446 ** If pIdx!=0 then it must be one of the indexes of table iCur.
447 ** Search for terms matching the iColumn-th column of pIdx
448 ** rather than the iColumn-th column of table iCur.
449 **
450 ** The term returned might by Y=<expr> if there is another constraint in
451 ** the WHERE clause that specifies that X=Y. Any such constraints will be
452 ** identified by the WO_EQUIV bit in the pTerm->eOperator field. The
453 ** aiCur[]/iaColumn[] arrays hold X and all its equivalents. There are 11
454 ** slots in aiCur[]/aiColumn[] so that means we can look for X plus up to 10
455 ** other equivalent values. Hence a search for X will return <expr> if X=A1
456 ** and A1=A2 and A2=A3 and ... and A9=A10 and A10=<expr>.
457 **
458 ** If there are multiple terms in the WHERE clause of the form "X <op> <expr>"
459 ** then try for the one with no dependencies on <expr> - in other words where
460 ** <expr> is a constant expression of some kind. Only return entries of
461 ** the form "X <op> Y" where Y is a column in another table if no terms of
462 ** the form "X <op> <const-expr>" exist. If no terms with a constant RHS
463 ** exist, try to return a term that does not use WO_EQUIV.
464 */
472 ){
475 WhereScan scan;
484 }
486 }
488 }
490 }
492 /*
493 ** This function searches pList for an entry that matches the iCol-th column
494 ** of index pIdx.
495 **
496 ** If such an expression is found, its index in pList->a[] is returned. If
497 ** no expression is found, -1 is returned.
498 */
505 ){
515 ){
519 }
520 }
521 }
524 }
526 /*
527 ** Return TRUE if the iCol-th column of index pIdx is NOT NULL
528 */
542 }
543 }
545 /*
546 ** Return true if the DISTINCT expression-list passed as the third argument
547 ** is redundant.
548 **
549 ** A DISTINCT list is redundant if any subset of the columns in the
550 ** DISTINCT list are collectively unique and individually non-null.
551 */
557 ){
563 /* If there is more than one table or sub-select in the FROM clause of
564 ** this query, then it will not be possible to show that the DISTINCT
565 ** clause is redundant. */
570 /* If any of the expressions is an IPK column on table iBase, then return
571 ** true. Note: The (p->iTable==iBase) part of this test may be false if the
572 ** current SELECT is a correlated sub-query.
573 */
579 }
581 /* Loop through all indices on the table, checking each to see if it makes
582 ** the DISTINCT qualifier redundant. It does so if:
583 **
584 ** 1. The index is itself UNIQUE, and
585 **
586 ** 2. All of the columns in the index are either part of the pDistinct
587 ** list, or else the WHERE clause contains a term of the form "col=X",
588 ** where X is a constant value. The collation sequences of the
589 ** comparison and select-list expressions must match those of the index.
590 **
591 ** 3. All of those index columns for which the WHERE clause does not
592 ** contain a "col=X" term are subject to a NOT NULL constraint.
593 */
601 }
602 }
604 /* This index implies that the DISTINCT qualifier is redundant. */
606 }
607 }
610 }
613 /*
614 ** Estimate the logarithm of the input value to base 2.
615 */
618 }
620 /*
621 ** Convert OP_Column opcodes to OP_Copy in previously generated code.
622 **
623 ** This routine runs over generated VDBE code and translates OP_Column
624 ** opcodes into OP_Copy when the table is being accessed via co-routine
625 ** instead of via table lookup.
626 **
627 ** If the iAutoidxCur is not zero, then any OP_Rowid instructions on
628 ** cursor iTabCur are transformed into OP_Sequence opcode for the
629 ** iAutoidxCur cursor, in order to generate unique rowids for the
630 ** automatic index being generated.
631 */
638 ){
653 #ifdef SQLITE_ALLOW_ROWID_IN_VIEW
657 }
658 #endif
659 }
660 }
661 }
663 /*
664 ** Two routines for printing the content of an sqlite3_index_info
665 ** structure. Used for testing and debugging only. If neither
666 ** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines
667 ** are no-ops.
668 */
669 #if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(WHERETRACE_ENABLED)
675 i,
680 }
683 i,
686 }
687 }
693 i,
696 }
702 }
703 #else
704 #define whereTraceIndexInfoInputs(A)
705 #define whereTraceIndexInfoOutputs(A)
706 #endif
708 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
709 /*
710 ** Return TRUE if the WHERE clause term pTerm is of a form where it
711 ** could be used with an index to access pSrc, assuming an appropriate
712 ** index existed.
713 */
717 Bitmask notReady /* Tables in outer loops of the join */
718 ){
725 ){
726 /* Cannot use an IS term from the WHERE clause as an index driver for
727 ** the RHS of a LEFT JOIN. Such a term can only be used if it is from
728 ** the ON clause. */
730 }
738 }
739 #endif
742 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
743 /*
744 ** Generate code to construct the Index object for an automatic index
745 ** and to set up the WhereLevel object pLevel so that the code generator
746 ** makes use of the automatic index.
747 */
754 ){
779 /* Generate code to skip over the creation and initialization of the
780 ** transient index on 2nd and subsequent iterations of the loop. */
785 /* Count the number of columns that will be added to the index
786 ** and used to match WHERE clause constraints */
803 }
806 Bitmask cMask;
817 }
821 }
824 }
825 }
826 }
832 /* Count the number of additional columns needed to create a
833 ** covering index. A "covering index" is an index that contains all
834 ** columns that are needed by the query. With a covering index, the
835 ** original table never needs to be accessed. Automatic indices must
836 ** be a covering index because the index will not be updated if the
837 ** original table changes and the index and table cannot both be used
838 ** if they go out of sync.
839 */
846 }
849 }
851 /* Construct the Index object to describe this index */
862 Bitmask cMask;
875 n++;
876 }
877 }
878 }
881 /* Add additional columns needed to make the automatic index into
882 ** a covering index */
887 n++;
888 }
889 }
894 n++;
895 }
896 }
901 /* Create the automatic index */
908 /* Fill the automatic index with content */
919 }
924 }
928 );
943 }
947 /* Jump here when skipping the initialization */
950 end_auto_index_create:
952 }
955 #ifndef SQLITE_OMIT_VIRTUALTABLE
956 /*
957 ** Allocate and populate an sqlite3_index_info structure. It is the
958 ** responsibility of the caller to eventually release the structure
959 ** by passing the pointer returned by this function to sqlite3_free().
960 */
968 ){
980 /* Count the number of possible WHERE clause constraints referring
981 ** to this virtual table */
994 nTerm++;
995 }
997 /* If the ORDER BY clause contains only columns in the current
998 ** virtual table then allocate space for the aOrderBy part of
999 ** the sqlite3_index_info structure.
1000 */
1008 }
1011 }
1012 }
1014 /* Allocate the sqlite3_index_info structure
1015 */
1022 }
1034 u16 op;
1045 /* tag-20191211-002: WHERE-clause constraints are not useful to the
1046 ** right-hand table of a LEFT JOIN. See tag-20191211-001 for the
1047 ** equivalent restriction for ordinary tables. */
1050 ){
1052 }
1066 }
1069 /* The direct assignment in the previous line is possible only because
1070 ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical. The
1071 ** following asserts verify this fact. */
1081 ){
1086 }
1087 }
1089 j++;
1090 }
1096 }
1100 }
1102 /*
1103 ** The table object reference passed as the second argument to this function
1104 ** must represent a virtual table. This function invokes the xBestIndex()
1105 ** method of the virtual table with the sqlite3_index_info object that
1106 ** comes in as the 3rd argument to this function.
1107 **
1108 ** If an error occurs, pParse is populated with an error message and an
1109 ** appropriate error code is returned. A return of SQLITE_CONSTRAINT from
1110 ** xBestIndex is not considered an error. SQLITE_CONSTRAINT indicates that
1111 ** the current configuration of "unusable" flags in sqlite3_index_info can
1112 ** not result in a valid plan.
1113 **
1114 ** Whether or not an error is returned, it is the responsibility of the
1115 ** caller to eventually free p->idxStr if p->needToFreeIdxStr indicates
1116 ** that this is required.
1117 */
1133 }
1134 }
1138 }
1141 #ifdef SQLITE_ENABLE_STAT4
1142 /*
1143 ** Estimate the location of a particular key among all keys in an
1144 ** index. Store the results in aStat as follows:
1145 **
1146 ** aStat[0] Est. number of rows less than pRec
1147 ** aStat[1] Est. number of rows equal to pRec
1148 **
1149 ** Return the index of the sample that is the smallest sample that
1150 ** is greater than or equal to pRec. Note that this index is not an index
1151 ** into the aSample[] array - it is an index into a virtual set of samples
1152 ** based on the contents of aSample[] and the number of fields in record
1153 ** pRec.
1154 */
1161 ){
1172 #ifndef SQLITE_DEBUG
1174 #endif
1179 /* Do a binary search to find the first sample greater than or equal
1180 ** to pRec. If pRec contains a single field, the set of samples to search
1181 ** is simply the aSample[] array. If the samples in aSample[] contain more
1182 ** than one fields, all fields following the first are ignored.
1183 **
1184 ** If pRec contains N fields, where N is more than one, then as well as the
1185 ** samples in aSample[] (truncated to N fields), the search also has to
1186 ** consider prefixes of those samples. For example, if the set of samples
1187 ** in aSample is:
1188 **
1189 ** aSample[0] = (a, 5)
1190 ** aSample[1] = (a, 10)
1191 ** aSample[2] = (b, 5)
1192 ** aSample[3] = (c, 100)
1193 ** aSample[4] = (c, 105)
1194 **
1195 ** Then the search space should ideally be the samples above and the
1196 ** unique prefixes [a], [b] and [c]. But since that is hard to organize,
1197 ** the code actually searches this set:
1198 **
1199 ** 0: (a)
1200 ** 1: (a, 5)
1201 ** 2: (a, 10)
1202 ** 3: (a, 10)
1203 ** 4: (b)
1204 ** 5: (b, 5)
1205 ** 6: (c)
1206 ** 7: (c, 100)
1207 ** 8: (c, 105)
1208 ** 9: (c, 105)
1209 **
1210 ** For each sample in the aSample[] array, N samples are present in the
1211 ** effective sample array. In the above, samples 0 and 1 are based on
1212 ** sample aSample[0]. Samples 2 and 3 on aSample[1] etc.
1213 **
1214 ** Often, sample i of each block of N effective samples has (i+1) fields.
1215 ** Except, each sample may be extended to ensure that it is greater than or
1216 ** equal to the previous sample in the array. For example, in the above,
1217 ** sample 2 is the first sample of a block of N samples, so at first it
1218 ** appears that it should be 1 field in size. However, that would make it
1219 ** smaller than sample 1, so the binary search would not work. As a result,
1220 ** it is extended to two fields. The duplicates that this creates do not
1221 ** cause any problems.
1222 */
1233 /* The proposed effective sample is a prefix of sample aSample[iSamp].
1234 ** Specifically, the shortest prefix of at least (1 + iTest%nField)
1235 ** fields that is greater than the previous effective sample. */
1238 }
1241 }
1255 }
1259 #ifdef SQLITE_DEBUG
1260 /* The following assert statements check that the binary search code
1261 ** above found the right answer. This block serves no purpose other
1262 ** than to invoke the asserts. */
1265 /* If (res==0) is true, then pRec must be equal to sample i. */
1271 );
1273 /* Unless i==pIdx->nSample, indicating that pRec is larger than
1274 ** all samples in the aSample[] array, pRec must be smaller than the
1275 ** (iCol+1) field prefix of sample i. */
1282 /* if i==0 and iCol==0, then record pRec is smaller than all samples
1283 ** in the aSample[] array. Otherwise, if (iCol>0) then pRec must
1284 ** be greater than or equal to the (iCol) field prefix of sample i.
1285 ** If (i>0), then pRec must also be greater than sample (i-1). */
1290 }
1295 }
1296 }
1297 }
1301 /* Record pRec is equal to sample i */
1306 /* At this point, the (iCol+1) field prefix of aSample[i] is the first
1307 ** sample that is greater than pRec. Or, if i==pIdx->nSample then pRec
1308 ** is larger than all samples in the array. */
1314 }
1320 }
1325 }
1328 }
1330 /* Restore the pRec->nField value before returning. */
1333 }
1336 /*
1337 ** If it is not NULL, pTerm is a term that provides an upper or lower
1338 ** bound on a range scan. Without considering pTerm, it is estimated
1339 ** that the scan will visit nNew rows. This function returns the number
1340 ** estimated to be visited after taking pTerm into account.
1341 **
1342 ** If the user explicitly specified a likelihood() value for this term,
1343 ** then the return value is the likelihood multiplied by the number of
1344 ** input rows. Otherwise, this function assumes that an "IS NOT NULL" term
1345 ** has a likelihood of 0.50, and any other term a likelihood of 0.25.
1346 */
1354 }
1355 }
1357 }
1360 #ifdef SQLITE_ENABLE_STAT4
1361 /*
1362 ** Return the affinity for a single column of an index.
1363 */
1368 }
1371 }
1372 #endif
1375 #ifdef SQLITE_ENABLE_STAT4
1376 /*
1377 ** This function is called to estimate the number of rows visited by a
1378 ** range-scan on a skip-scan index. For example:
1379 **
1380 ** CREATE INDEX i1 ON t1(a, b, c);
1381 ** SELECT * FROM t1 WHERE a=? AND c BETWEEN ? AND ?;
1382 **
1383 ** Value pLoop->nOut is currently set to the estimated number of rows
1384 ** visited for scanning (a=? AND b=?). This function reduces that estimate
1385 ** by some factor to account for the (c BETWEEN ? AND ?) expression based
1386 ** on the stat4 data for the index. this scan will be peformed multiple
1387 ** times (once for each (a,b) combination that matches a=?) is dealt with
1388 ** by the caller.
1389 **
1390 ** It does this by scanning through all stat4 samples, comparing values
1391 ** extracted from pLower and pUpper with the corresponding column in each
1392 ** sample. If L and U are the number of samples found to be less than or
1393 ** equal to the values extracted from pLower and pUpper respectively, and
1394 ** N is the total number of samples, the pLoop->nOut value is adjusted
1395 ** as follows:
1396 **
1397 ** nOut = nOut * ( min(U - L, 1) / N )
1398 **
1399 ** If pLower is NULL, or a value cannot be extracted from the term, L is
1400 ** set to zero. If pUpper is NULL, or a value cannot be extracted from it,
1401 ** U is set to N.
1402 **
1403 ** Normally, this function sets *pbDone to 1 before returning. However,
1404 ** if no value can be extracted from either pLower or pUpper (and so the
1405 ** estimate of the number of rows delivered remains unchanged), *pbDone
1406 ** is left as is.
1407 **
1408 ** If an error occurs, an SQLite error code is returned. Otherwise,
1409 ** SQLITE_OK.
1410 */
1417 ){
1435 }
1439 }
1449 }
1453 }
1454 }
1458 /* If there is both an upper and lower bound specified, and the
1459 ** comparisons indicate that they are close together, use the fallback
1460 ** method (assume that the scan visits 1/64 of the rows) for estimating
1461 ** the number of rows visited. Otherwise, estimate the number of rows
1462 ** using the method described in the header comment for this function. */
1469 }
1473 }
1480 }
1483 /*
1484 ** This function is used to estimate the number of rows that will be visited
1485 ** by scanning an index for a range of values. The range may have an upper
1486 ** bound, a lower bound, or both. The WHERE clause terms that set the upper
1487 ** and lower bounds are represented by pLower and pUpper respectively. For
1488 ** example, assuming that index p is on t1(a):
1489 **
1490 ** ... FROM t1 WHERE a > ? AND a < ? ...
1491 ** |_____| |_____|
1492 ** | |
1493 ** pLower pUpper
1494 **
1495 ** If either of the upper or lower bound is not present, then NULL is passed in
1496 ** place of the corresponding WhereTerm.
1497 **
1498 ** The value in (pBuilder->pNew->u.btree.nEq) is the number of the index
1499 ** column subject to the range constraint. Or, equivalently, the number of
1500 ** equality constraints optimized by the proposed index scan. For example,
1501 ** assuming index p is on t1(a, b), and the SQL query is:
1502 **
1503 ** ... FROM t1 WHERE a = ? AND b > ? AND b < ? ...
1504 **
1505 ** then nEq is set to 1 (as the range restricted column, b, is the second
1506 ** left-most column of the index). Or, if the query is:
1507 **
1508 ** ... FROM t1 WHERE a > ? AND a < ? ...
1509 **
1510 ** then nEq is set to 0.
1511 **
1512 ** When this function is called, *pnOut is set to the sqlite3LogEst() of the
1513 ** number of rows that the index scan is expected to visit without
1514 ** considering the range constraints. If nEq is 0, then *pnOut is the number of
1515 ** rows in the index. Assuming no error occurs, *pnOut is adjusted (reduced)
1516 ** to account for the range constraints pLower and pUpper.
1517 **
1518 ** In the absence of sqlite_stat4 ANALYZE data, or if such data cannot be
1519 ** used, a single range inequality reduces the search space by a factor of 4.
1520 ** and a pair of constraints (x>? AND x<?) reduces the expected number of
1521 ** rows visited by a factor of 64.
1522 */
1529 ){
1532 LogEst nNew;
1534 #ifdef SQLITE_ENABLE_STAT4
1540 ){
1547 /* Variable iLower will be set to the estimate of the number of rows in
1548 ** the index that are less than the lower bound of the range query. The
1549 ** lower bound being the concatenation of $P and $L, where $P is the
1550 ** key-prefix formed by the nEq values matched against the nEq left-most
1551 ** columns of the index, and $L is the value in pLower.
1552 **
1553 ** Or, if pLower is NULL or $L cannot be extracted from it (because it
1554 ** is not a simple variable or literal value), the lower bound of the
1555 ** range is $P. Due to a quirk in the way whereKeyStats() works, even
1556 ** if $L is available, whereKeyStats() is called for both ($P) and
1557 ** ($P:$L) and the larger of the two returned values is used.
1558 **
1559 ** Similarly, iUpper is to be set to the estimate of the number of rows
1560 ** less than the upper bound of the range query. Where the upper bound
1561 ** is either ($P) or ($P:$U). Again, even if $U is available, both values
1562 ** of iUpper are requested of whereKeyStats() and the smaller used.
1563 **
1564 ** The number of rows between the two bounds is then just iUpper-iLower.
1565 */
1574 }
1575 /* Determine iLower and iUpper using ($P) only. */
1580 /* Note: this call could be optimized away - since the same values must
1581 ** have been requested when testing key $P in whereEqualScanEst(). */
1585 }
1591 /* The roles of pLower and pUpper are swapped for a DESC index */
1594 }
1596 /* If possible, improve on the iLower estimate using ($P:$L). */
1602 tRowcnt iNew;
1608 nOut--;
1610 }
1611 }
1613 /* If possible, improve on the iUpper estimate using ($P:$U). */
1619 tRowcnt iNew;
1625 nOut--;
1627 }
1628 }
1634 /* TUNING: If both iUpper and iLower are derived from the same
1635 ** sample, then assume they are 4x more selective. This brings
1636 ** the estimated selectivity more in line with what it would be
1637 ** if estimated without the use of STAT4 tables. */
1641 }
1644 }
1647 }
1652 }
1653 }
1654 #else
1658 #endif
1663 /* TUNING: If there is both an upper and lower limit and neither limit
1664 ** has an application-defined likelihood(), assume the range is
1665 ** reduced by an additional 75%. This means that, by default, an open-ended
1666 ** range query (e.g. col > ?) is assumed to match 1/4 of the rows in the
1667 ** index. While a closed range (e.g. col BETWEEN ? AND ?) is estimated to
1668 ** match 1/64 of the index. */
1671 }
1676 #if defined(WHERETRACE_ENABLED)
1680 }
1681 #endif
1684 }
1686 #ifdef SQLITE_ENABLE_STAT4
1687 /*
1688 ** Estimate the number of rows that will be returned based on
1689 ** an equality constraint x=VALUE and where that VALUE occurs in
1690 ** the histogram data. This only works when x is the left-most
1691 ** column of an index and sqlite_stat4 histogram data is available
1692 ** for that index. When pExpr==NULL that means the constraint is
1693 ** "x IS NULL" instead of "x=VALUE".
1694 **
1695 ** Write the estimated row count into *pnRow and return SQLITE_OK.
1696 ** If unable to make an estimate, leave *pnRow unchanged and return
1697 ** non-zero.
1698 **
1699 ** This routine can fail if it is unable to load a collating sequence
1700 ** required for string comparison, or if unable to allocate memory
1701 ** for a UTF conversion required for comparison. The error is stored
1702 ** in the pParse structure.
1703 */
1709 ){
1723 /* If values are not available for all fields of the index to the left
1724 ** of this one, no estimate can be made. Return SQLITE_NOTFOUND. */
1727 }
1729 /* This is an optimization only. The call to sqlite3Stat4ProbeSetValue()
1730 ** below would return the same value. */
1734 }
1748 }
1751 #ifdef SQLITE_ENABLE_STAT4
1752 /*
1753 ** Estimate the number of rows that will be returned based on
1754 ** an IN constraint where the right-hand side of the IN operator
1755 ** is a list of values. Example:
1756 **
1757 ** WHERE x IN (1,2,3,4)
1758 **
1759 ** Write the estimated row count into *pnRow and return SQLITE_OK.
1760 ** If unable to make an estimate, leave *pnRow unchanged and return
1761 ** non-zero.
1762 **
1763 ** This routine can fail if it is unable to load a collating sequence
1764 ** required for string comparison, or if unable to allocate memory
1765 ** for a UTF conversion required for comparison. The error is stored
1766 ** in the pParse structure.
1767 */
1773 ){
1788 }
1794 }
1797 }
1801 #ifdef WHERETRACE_ENABLED
1802 /*
1803 ** Print the content of a WhereTerm object
1804 */
1825 }
1829 /* The 0x10000 .wheretrace flag causes extra information to be
1830 ** shown about each Term */
1834 }
1837 }
1840 }
1843 }
1844 }
1845 #endif
1847 #ifdef WHERETRACE_ENABLED
1848 /*
1849 ** Show the complete content of a WhereClause
1850 */
1855 }
1856 }
1857 #endif
1859 #ifdef WHERETRACE_ENABLED
1860 /*
1861 ** Print a WhereLoop object for debugging purposes
1862 */
1880 }
1884 }
1892 }
1895 }
1900 }
1906 }
1907 }
1908 }
1909 #endif
1911 /*
1912 ** Convert bulk memory into a valid WhereLoop that can be passed
1913 ** to whereLoopClear harmlessly.
1914 */
1920 }
1922 /*
1923 ** Clear the WhereLoop.u union. Leave WhereLoop.pLTerm intact.
1924 */
1935 }
1936 }
1937 }
1939 /*
1940 ** Deallocate internal memory used by a WhereLoop object
1941 */
1946 }
1948 /*
1949 ** Increase the memory allocation for pLoop->aLTerm[] to be at least n.
1950 */
1962 }
1964 /*
1965 ** Transfer content from the second pLoop into the first.
1966 */
1972 }
1979 }
1981 }
1983 /*
1984 ** Delete a WhereLoop object
1985 */
1989 }
1991 /*
1992 ** Free a WhereInfo structure
1993 */
2002 }
2003 }
2009 }
2012 }
2014 /* Undo all Expr node modifications
2015 */
2022 }
2023 }
2025 /*
2026 ** Return TRUE if all of the following are true:
2027 **
2028 ** (1) X has the same or lower cost, or returns the same or fewer rows,
2029 ** than Y.
2030 ** (2) X uses fewer WHERE clause terms than Y
2031 ** (3) Every WHERE clause term used by X is also used by Y
2032 ** (4) X skips at least as many columns as Y
2033 ** (5) If X is a covering index, than Y is too
2034 **
2035 ** Conditions (2) and (3) mean that X is a "proper subset" of Y.
2036 ** If X is a proper subset of Y then Y is a better choice and ought
2037 ** to have a lower cost. This routine returns TRUE when that cost
2038 ** relationship is inverted and needs to be adjusted. Constraint (4)
2039 ** was added because if X uses skip-scan less than Y it still might
2040 ** deserve a lower cost even if it is a proper subset of Y. Constraint (5)
2041 ** was added because a covering index probably deserves to have a lower cost
2042 ** than a non-covering index even if it is a proper subset.
2043 */
2047 ){
2051 }
2058 }
2060 }
2064 }
2066 }
2068 /*
2069 ** Try to adjust the cost and number of output rows of WhereLoop pTemplate
2070 ** upwards or downwards so that:
2071 **
2072 ** (1) pTemplate costs less than any other WhereLoops that are a proper
2073 ** subset of pTemplate
2074 **
2075 ** (2) pTemplate costs more than any other WhereLoops for which pTemplate
2076 ** is a proper subset.
2077 **
2078 ** To say "WhereLoop X is a proper subset of Y" means that X uses fewer
2079 ** WHERE clause terms than Y and that every WHERE clause term used by X is
2080 ** also used by Y.
2081 */
2088 /* Adjust pTemplate cost downward so that it is cheaper than its
2089 ** subset p. */
2097 /* Adjust pTemplate cost upward so that it is costlier than p since
2098 ** pTemplate is a proper subset of p */
2105 }
2106 }
2107 }
2109 /*
2110 ** Search the list of WhereLoops in *ppPrev looking for one that can be
2111 ** replaced by pTemplate.
2112 **
2113 ** Return NULL if pTemplate does not belong on the WhereLoop list.
2114 ** In other words if pTemplate ought to be dropped from further consideration.
2115 **
2116 ** If pX is a WhereLoop that pTemplate can replace, then return the
2117 ** link that points to pX.
2118 **
2119 ** If pTemplate cannot replace any existing element of the list but needs
2120 ** to be added to the list as a new entry, then return a pointer to the
2121 ** tail of the list.
2122 */
2126 ){
2130 /* If either the iTab or iSortIdx values for two WhereLoop are different
2131 ** then those WhereLoops need to be considered separately. Neither is
2132 ** a candidate to replace the other. */
2134 }
2135 /* In the current implementation, the rSetup value is either zero
2136 ** or the cost of building an automatic index (NlogN) and the NlogN
2137 ** is the same for compatible WhereLoops. */
2141 /* whereLoopAddBtree() always generates and inserts the automatic index
2142 ** case first. Hence compatible candidate WhereLoops never have a larger
2143 ** rSetup. Call this SETUP-INVARIANT */
2146 /* Any loop using an appliation-defined index (or PRIMARY KEY or
2147 ** UNIQUE constraint) with one or more == constraints is better
2148 ** than an automatic index. Unless it is a skip-scan. */
2154 ){
2156 }
2158 /* If existing WhereLoop p is better than pTemplate, pTemplate can be
2159 ** discarded. WhereLoop p is better if:
2160 ** (1) p has no more dependencies than pTemplate, and
2161 ** (2) p has an equal or lower cost than pTemplate
2162 */
2167 ){
2169 }
2171 /* If pTemplate is always better than p, then cause p to be overwritten
2172 ** with pTemplate. pTemplate is better than p if:
2173 ** (1) pTemplate has no more dependences than p, and
2174 ** (2) pTemplate has an equal or lower cost than p.
2175 */
2179 ){
2182 }
2183 }
2185 }
2187 /*
2188 ** Insert or replace a WhereLoop entry using the template supplied.
2189 **
2190 ** An existing WhereLoop entry might be overwritten if the new template
2191 ** is better and has fewer dependencies. Or the template will be ignored
2192 ** and no insert will occur if an existing WhereLoop is faster and has
2193 ** fewer dependencies than the template. Otherwise a new WhereLoop is
2194 ** added based on the template.
2195 **
2196 ** If pBuilder->pOrSet is not NULL then we care about only the
2197 ** prerequisites and rRun and nOut costs of the N best loops. That
2198 ** information is gathered in the pBuilder->pOrSet object. This special
2199 ** processing mode is used only for OR clause processing.
2200 **
2201 ** When accumulating multiple loops (when pBuilder->pOrSet is NULL) we
2202 ** still might overwrite similar loops with the new template if the
2203 ** new template is better. Loops may be overwritten if the following
2204 ** conditions are met:
2205 **
2206 ** (1) They have the same iTab.
2207 ** (2) They have the same iSortIdx.
2208 ** (3) The template has same or fewer dependencies than the current loop
2209 ** (4) The template has the same or lower cost than the current loop
2210 */
2217 /* Stop the search once we hit the query planner search limit */
2222 }
2227 /* If pBuilder->pOrSet is defined, then only keep track of the costs
2228 ** and prereqs.
2229 */
2232 #if WHERETRACE_ENABLED
2235 #endif
2242 }
2243 #endif
2244 }
2246 }
2248 /* Look for an existing WhereLoop to replace with pTemplate
2249 */
2253 /* There already exists a WhereLoop on the list that is better
2254 ** than pTemplate, so just ignore pTemplate */
2259 }
2260 #endif
2264 }
2266 /* If we reach this point it means that either p[] should be overwritten
2267 ** with pTemplate[] if p[] exists, or if p==NULL then allocate a new
2268 ** WhereLoop and insert it.
2269 */
2278 }
2280 }
2281 #endif
2283 /* Allocate a new WhereLoop to add to the end of the list */
2289 /* We will be overwriting WhereLoop p[]. But before we do, first
2290 ** go through the rest of the list and delete any other entries besides
2291 ** p[] that are also supplated by pTemplate */
2304 }
2305 #endif
2307 }
2308 }
2314 }
2315 }
2317 }
2319 /*
2320 ** Adjust the WhereLoop.nOut value downward to account for terms of the
2321 ** WHERE clause that reference the loop but which are not used by an
2322 ** index.
2323 *
2324 ** For every WHERE clause term that is not used by the index
2325 ** and which has a truth probability assigned by one of the likelihood(),
2326 ** likely(), or unlikely() SQL functions, reduce the estimated number
2327 ** of output rows by the probability specified.
2328 **
2329 ** TUNING: For every WHERE clause term that is not used by the index
2330 ** and which does not have an assigned truth probability, heuristics
2331 ** described below are used to try to estimate the truth probability.
2332 ** TODO --> Perhaps this is something that could be improved by better
2333 ** table statistics.
2334 **
2335 ** Heuristic 1: Estimate the truth probability as 93.75%. The 93.75%
2336 ** value corresponds to -1 in LogEst notation, so this means decrement
2337 ** the WhereLoop.nOut field for every such WHERE clause term.
2338 **
2339 ** Heuristic 2: If there exists one or more WHERE clause terms of the
2340 ** form "x==EXPR" and EXPR is not a constant 0 or 1, then make sure the
2341 ** final output row estimate is no greater than 1/4 of the total number
2342 ** of rows in the table. In other words, assume that x==EXPR will filter
2343 ** out at least 3 out of 4 rows. If EXPR is -1 or 0 or 1, then maybe the
2344 ** "x" column is boolean or else -1 or 0 or 1 is a common default value
2345 ** on the "x" column and so in that case only cap the output row estimate
2346 ** at 1/2 instead of 1/4.
2347 */
2351 LogEst nRow /* Number of rows in the entire table */
2352 ){
2369 }
2372 /* If a truth probability is specified using the likelihood() hints,
2373 ** then use the probability provided by the application. */
2376 /* In the absence of explicit truth probabilities, use heuristics to
2377 ** guess a reasonable truth probability. */
2381 ){
2389 }
2393 }
2394 }
2395 }
2396 }
2397 }
2399 }
2401 /*
2402 ** Term pTerm is a vector range comparison operation. The first comparison
2403 ** in the vector can be optimized using column nEq of the index. This
2404 ** function returns the total number of vector elements that can be used
2405 ** as part of the range comparison.
2406 **
2407 ** For example, if the query is:
2408 **
2409 ** WHERE a = ? AND (b, c, d) > (?, ?, ?)
2410 **
2411 ** and the index:
2412 **
2413 ** CREATE INDEX ... ON (a, b, c, d, e)
2414 **
2415 ** then this function would be invoked with nEq=1. The value returned in
2416 ** this case is 3.
2417 */
2424 ){
2430 /* Test if comparison i of pTerm is compatible with column (i+nEq)
2431 ** of the index. If not, exit the loop. */
2444 }
2446 /* Check that the LHS of the comparison is a column reference to
2447 ** the right column of the right source table. And that the sort
2448 ** order of the index column is the same as the sort order of the
2449 ** leftmost index column. */
2454 ){
2456 }
2466 }
2468 }
2470 /*
2471 ** Adjust the cost C by the costMult facter T. This only occurs if
2472 ** compiled with -DSQLITE_ENABLE_COSTMULT
2473 */
2474 #ifdef SQLITE_ENABLE_COSTMULT
2475 # define ApplyCostMultiplier(C,T) C += T
2476 #else
2477 # define ApplyCostMultiplier(C,T)
2478 #endif
2480 /*
2481 ** We have so far matched pBuilder->pNew->u.btree.nEq terms of the
2482 ** index pIndex. Try to match one more.
2483 **
2484 ** When this function is called, pBuilder->pNew->nOut contains the
2485 ** number of rows expected to be visited by filtering using the nEq
2486 ** terms only. If it is modified, this value is restored before this
2487 ** function returns.
2488 **
2489 ** If pProbe->idxType==SQLITE_IDXTYPE_IPK, that means pIndex is
2490 ** a fake index used for the INTEGER PRIMARY KEY.
2491 */
2496 LogEst nInMul /* log(Number of iterations due to IN) */
2497 ){
2531 }
2553 LogEst rCostIdx;
2556 #ifdef SQLITE_ENABLE_STAT4
2558 #endif
2561 ){
2563 }
2566 /* Do not allow the upper bound of a LIKE optimization range constraint
2567 ** to mix with a lower range bound from some other source */
2570 /* tag-20191211-001: Do not allow constraints from the WHERE clause to
2571 ** be used by the right table of a LEFT JOIN. Only constraints in the
2572 ** ON clause are allowed. See tag-20191211-002 for the vtab equivalent. */
2575 ){
2577 }
2583 }
2597 );
2602 /* "x IN (SELECT ...)": TUNING: the SELECT returns 25 rows */
2606 /* The expression may actually be of the form (x, y) IN (SELECT...).
2607 ** In this case there is a separate term for each of (x) and (y).
2608 ** However, the nIn multiplier should only be applied once, not once
2609 ** for each such term. The following loop checks that pTerm is the
2610 ** first such term in use, and sets nIn back to 0 if it is not. */
2613 }
2615 /* "x IN (value, value, ...)" */
2617 }
2620 /* Let:
2621 ** N = the total number of rows in the table
2622 ** K = the number of entries on the RHS of the IN operator
2623 ** M = the number of rows in the table that match terms to the
2624 ** to the left in the same index. If the IN operator is on
2625 ** the left-most index column, M==N.
2626 **
2627 ** Given the definitions above, it is better to omit the IN operator
2628 ** from the index lookup and instead do a scan of the M elements,
2629 ** testing each scanned row against the IN operator separately, if:
2630 **
2631 ** M*log(K) < K*log(N)
2632 **
2633 ** Our estimates for M, K, and N might be inaccurate, so we build in
2634 ** a safety margin of 2 (LogEst: 10) that favors using the IN operator
2635 ** with the index, as using an index has better worst-case behavior.
2636 ** If we do not have real sqlite_stat1 data, always prefer to use
2637 ** the index. Do not bother with this optimization on very small
2638 ** tables (less than 2 rows) as it is pointless in that case.
2639 */
2642 /* TUNING v----- 10 to bias toward indexed IN */
2661 }
2662 }
2670 ){
2673 ){
2677 }
2678 }
2688 );
2692 /* Range constraints that come from the LIKE optimization are
2693 ** always used in pairs. */
2702 }
2710 );
2714 }
2716 /* At this point pNew->nOut is set to the number of rows expected to
2717 ** be visited by the index scan before considering term pTerm, or the
2718 ** values of nIn and nInMul. In other words, assuming that all
2719 ** "x IN(...)" terms are replaced with "x = ?". This block updates
2720 ** the value of pNew->nOut to account for pTerm (but not nIn/nInMul). */
2723 /* Adjust nOut using stat4 data. Or, if there is no stat4
2724 ** data, using some other estimate. */
2737 #ifdef SQLITE_ENABLE_STAT4
2744 ){
2753 }
2759 /* TUNING: Mark terms as "low selectivity" if they seem likely
2760 ** to be true for half or more of the rows in the table.
2761 ** See tag-202002240-1 */
2763 ){
2769 }
2770 #endif
2773 /* If the term has previously been used with an assumption of
2774 ** higher selectivity, then set the flag to rerun the
2775 ** loop computations. */
2777 }
2778 }
2781 }
2782 }
2784 #endif
2785 {
2788 /* TUNING: If there is no likelihood() value, assume that a
2789 ** "col IS NULL" expression matches twice as many rows
2790 ** as (col=?). */
2792 }
2793 }
2794 }
2795 }
2797 /* Set rCostIdx to the cost of visiting selected rows in index. Add
2798 ** it to pNew->rRun, which is currently set to the cost of the index
2799 ** seek only. Then, if this is a non-covering index, add the cost of
2800 ** visiting the rows in the main table. */
2806 }
2819 }
2825 ){
2827 }
2829 #ifdef SQLITE_ENABLE_STAT4
2831 #endif
2832 }
2842 /* Consider using a skip-scan if there are no WHERE clause constraints
2843 ** available for the left-most terms of the index, and if the average
2844 ** number of repeats in the left-most terms is at least 18.
2845 **
2846 ** The magic number 18 is selected on the basis that scanning 17 rows
2847 ** is almost always quicker than an index seek (even though if the index
2848 ** contains fewer than 2^17 rows we assume otherwise in other parts of
2849 ** the code). And, even if it is not, it should not be too much slower.
2850 ** On the other hand, the extra seeks could end up being significantly
2851 ** more expensive. */
2861 ){
2862 LogEst nIter;
2869 /* TUNING: Because uncertainties in the estimates for skip-scan queries,
2870 ** add a 1.375 fudge factor to make skip-scan slightly less likely. */
2877 }
2882 }
2884 /*
2885 ** Return True if it is possible that pIndex might be useful in
2886 ** implementing the ORDER BY clause in pBuilder.
2887 **
2888 ** Return False if pBuilder does not contain an ORDER BY clause or
2889 ** if there is no way for pIndex to be useful in implementing that
2890 ** ORDER BY clause.
2891 */
2895 int iCursor
2896 ){
2910 }
2916 }
2917 }
2918 }
2919 }
2921 }
2923 /* Check to see if a partial index with pPartIndexWhere can be used
2924 ** in the current query. Return true if it can be and false if not.
2925 */
2931 ){
2938 }
2947 ){
2949 }
2950 }
2952 }
2954 /*
2955 ** Add all WhereLoop objects for a single table of the join where the table
2956 ** is identified by pBuilder->pNew->iTab. That table is guaranteed to be
2957 ** a b-tree table, not a virtual table.
2958 **
2959 ** The costs (WhereLoop.rRun) of the b-tree loops added by this function
2960 ** are calculated as follows:
2961 **
2962 ** For a full scan, assuming the table (or index) contains nRow rows:
2963 **
2964 ** cost = nRow * 3.0 // full-table scan
2965 ** cost = nRow * K // scan of covering index
2966 ** cost = nRow * (K+3.0) // scan of non-covering index
2967 **
2968 ** where K is a value between 1.1 and 3.0 set based on the relative
2969 ** estimated average size of the index and table records.
2970 **
2971 ** For an index scan, where nVisit is the number of index rows visited
2972 ** by the scan, and nSeek is the number of seek operations required on
2973 ** the index b-tree:
2974 **
2975 ** cost = nSeek * (log(nRow) + K * nVisit) // covering index
2976 ** cost = nSeek * (log(nRow) + (K+3.0) * nVisit) // non-covering index
2977 **
2978 ** Normally, nSeek is 1. nSeek values greater than 1 come about if the
2979 ** WHERE clause includes "x IN (....)" terms used in place of "x=?". Or when
2980 ** implicit "x IN (SELECT x FROM tbl)" terms are added for skip-scans.
2981 **
2982 ** The estimated values (nRow, nVisit, nSeek) often contain a large amount
2983 ** of uncertainty. For this reason, scoring is designed to pick plans that
2984 ** "do the least harm" if the estimates are inaccurate. For example, a
2985 ** log(nRow) factor is omitted from a non-covering index scan in order to
2986 ** bias the scoring in favor of using an index, since the worst-case
2987 ** performance of using an index is far better than the worst-case performance
2988 ** of a full table scan.
2989 */
2992 Bitmask mPrereq /* Extra prerequesites for using this table */
2993 ){
3019 /* An INDEXED BY clause specifies a particular index to use */
3024 /* There is no INDEXED BY clause. Create a fake Index object in local
3025 ** variable sPk to represent the rowid primary key index. Make this
3026 ** fake index the first in a chain of Index objects with all of the real
3027 ** indices to follow */
3042 /* The real indices of the table are only considered if the
3043 ** NOT INDEXED qualifier is omitted from the FROM clause */
3045 }
3047 }
3050 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
3051 /* Automatic indexes */
3060 ){
3061 /* Generate auto-index WhereLoops */
3074 /* TUNING: One-time cost for computing the automatic index is
3075 ** estimated to be X*N*log2(N) where N is the number of rows in
3076 ** the table being indexed and where X is 7 (LogEst=28) for normal
3077 ** tables or 0.5 (LogEst=-10) for views and subqueries. The value
3078 ** of X is smaller for views and subqueries so that the query planner
3079 ** will be more aggressive about generating automatic indexes for
3080 ** those objects, since there is no opportunity to add schema
3081 ** indexes on subqueries and views. */
3087 }
3090 /* TUNING: Each index lookup yields 20 rows in the table. This
3091 ** is more than the usual guess of 10 rows, since we have no way
3092 ** of knowing how selective the index will ultimately be. It would
3093 ** not be unreasonable to make this value much larger. */
3099 }
3100 }
3101 }
3104 /* Loop over all indices. If there was an INDEXED BY clause, then only
3105 ** consider index pProbe. */
3108 ){
3113 ){
3116 }
3131 /* The ONEPASS_DESIRED flags never occurs together with ORDER BY */
3134 /* Integer primary key index */
3137 /* Full table scan */
3139 /* TUNING: Cost of full table scan is 3.0*N. The 3.0 factor is an
3140 ** extra cost designed to discourage the use of full table scans,
3141 ** since index lookups have better worst-case performance if our
3142 ** stat guesses are wrong. Reduce the 3.0 penalty slightly
3143 ** (to 2.75) if we have valid STAT4 information for the table.
3144 ** At 2.75, a full table scan is preferred over using an index on
3145 ** a column with just two distinct values where each value has about
3146 ** an equal number of appearances. Without STAT4 data, we still want
3147 ** to use an index in that case, since the constraint might be for
3148 ** the scarcer of the two values, and in that case an index lookup is
3149 ** better.
3150 */
3151 #ifdef SQLITE_ENABLE_STAT4
3153 #else
3155 #endif
3162 Bitmask m;
3169 }
3171 /* Full scan via index */
3182 )
3183 ){
3186 /* The cost of visiting the index rows is N*K, where K is
3187 ** between 1.1 and 3.0, depending on the relative sizes of the
3188 ** index and table rows. */
3191 /* If this is a non-covering index scan, add in the cost of
3192 ** doing table lookups. The cost will be 3x the number of
3193 ** lookups. Take into account WHERE clause terms that can be
3194 ** satisfied using just the index, and that do not require a
3195 ** table lookup. */
3204 }
3205 /* pTerm can be evaluated using just the index. So reduce
3206 ** the expected number of table lookups accordingly */
3210 nLookup--;
3212 }
3213 }
3216 }
3222 }
3223 }
3228 /* If a non-unique index is used, or if a prefix of the key for
3229 ** unique index is used (making the index functionally non-unique)
3230 ** then the sqlite_stat1 data becomes important for scoring the
3231 ** plan */
3233 }
3234 #ifdef SQLITE_ENABLE_STAT4
3238 #endif
3239 }
3241 }
3243 #ifndef SQLITE_OMIT_VIRTUALTABLE
3245 /*
3246 ** Argument pIdxInfo is already populated with all constraints that may
3247 ** be used by the virtual table identified by pBuilder->pNew->iTab. This
3248 ** function marks a subset of those constraints usable, invokes the
3249 ** xBestIndex method and adds the returned plan to pBuilder.
3250 **
3251 ** A constraint is marked usable if:
3252 **
3253 ** * Argument mUsable indicates that its prerequisites are available, and
3254 **
3255 ** * It is not one of the operators specified in the mExclude mask passed
3256 ** as the fourth argument (which in practice is either WO_IN or 0).
3257 **
3258 ** Argument mPrereq is a mask of tables that must be scanned before the
3259 ** virtual table in question. These are added to the plans prerequisites
3260 ** before it is added to pBuilder.
3261 **
3262 ** Output parameter *pbIn is set to true if the plan added to pBuilder
3263 ** uses one or more WO_IN terms, or false otherwise.
3264 */
3273 ){
3289 /* Set the usable flag on the subset of constraints identified by
3290 ** arguments mUsable and mExclude. */
3297 ){
3299 }
3300 }
3302 /* Initialize the output fields of the sqlite3_index_info structure */
3313 /* Invoke the virtual table xBestIndex() method */
3317 /* If the xBestIndex method returns SQLITE_CONSTRAINT, that means
3318 ** that the particular combination of parameters provided is unusable.
3319 ** Make no entries in the loop table.
3320 */
3323 }
3325 }
3342 ){
3346 }
3363 }
3364 }
3366 /* A virtual table that is constrained by an IN clause may not
3367 ** consume the ORDER BY clause because (1) the order of IN terms
3368 ** is not necessarily related to the order of output terms and
3369 ** (2) Multiple outputs from a single IN value will not merge
3370 ** together. */
3374 }
3375 }
3376 }
3381 /* The non-zero argvIdx values must be contiguous. Raise an
3382 ** error if they are not */
3386 }
3387 }
3399 /* Set the WHERE_ONEROW flag if the xBestIndex() method indicated
3400 ** that the scan will visit at most one row. Clear it otherwise. */
3405 }
3410 }
3416 }
3418 /*
3419 ** If this function is invoked from within an xBestIndex() callback, it
3420 ** returns a pointer to a buffer containing the name of the collation
3421 ** sequence associated with element iCons of the sqlite3_index_info.aConstraint
3422 ** array. Or, if iCons is out of range or there is no active xBestIndex
3423 ** call, return NULL.
3424 */
3434 }
3436 }
3438 }
3440 /*
3441 ** Add all WhereLoop objects for a table of the join identified by
3442 ** pBuilder->pNew->iTab. That table is guaranteed to be a virtual table.
3443 **
3444 ** If there are no LEFT or CROSS JOIN joins in the query, both mPrereq and
3445 ** mUnusable are set to 0. Otherwise, mPrereq is a mask of all FROM clause
3446 ** entries that occur before the virtual table in the FROM clause and are
3447 ** separated from it by at least one LEFT or CROSS JOIN. Similarly, the
3448 ** mUnusable mask contains all FROM clause entries that occur after the
3449 ** virtual table and are separated from it by at least one LEFT or
3450 ** CROSS JOIN.
3451 **
3452 ** For example, if the query were:
3453 **
3454 ** ... FROM t1, t2 LEFT JOIN t3, t4, vt CROSS JOIN t5, t6;
3455 **
3456 ** then mPrereq corresponds to (t1, t2) and mUnusable to (t5, t6).
3457 **
3458 ** All the tables in mPrereq must be scanned before the current virtual
3459 ** table. So any terms for which all prerequisites are satisfied by
3460 ** mPrereq may be specified as "usable" in all calls to xBestIndex.
3461 ** Conversely, all tables in mUnusable must be scanned after the current
3462 ** virtual table, so any terms for which the prerequisites overlap with
3463 ** mUnusable should always be configured as "not-usable" for xBestIndex.
3464 */
3468 Bitmask mUnusable /* Tables that must be scanned after this one */
3469 ){
3480 u16 mNoOmit;
3500 }
3502 /* First call xBestIndex() with all constraints usable. */
3507 /* If the call to xBestIndex() with all terms enabled produced a plan
3508 ** that does not require any source tables (IOW: a plan with mBest==0)
3509 ** and does not use an IN(...) operator, then there is no point in making
3510 ** any further calls to xBestIndex() since they will all return the same
3511 ** result (if the xBestIndex() implementation is sane). */
3518 /* If the plan produced by the earlier call uses an IN(...) term, call
3519 ** xBestIndex again, this time with IN(...) terms disabled. */
3529 }
3530 }
3532 /* Call xBestIndex once for each distinct value of (prereqRight & ~mPrereq)
3533 ** in the set of terms that apply to the current virtual table. */
3539 Bitmask mThis = (
3541 );
3543 }
3554 }
3555 }
3557 /* If the calls to xBestIndex() in the above loop did not find a plan
3558 ** that requires no source tables at all (i.e. one guaranteed to be
3559 ** usable), make a call here with all source tables disabled */
3565 }
3567 /* If the calls to xBestIndex() have so far failed to find a plan
3568 ** that requires no source tables at all and does not use an IN(...)
3569 ** operator, make a final call to obtain one here. */
3574 }
3575 }
3581 }
3584 /*
3585 ** Add WhereLoop entries to handle OR terms. This works for either
3586 ** btrees or virtual tables.
3587 */
3590 Bitmask mPrereq,
3591 Bitmask mUnusable
3592 ){
3599 WhereClause tempWC;
3600 WhereLoopBuilder sSubBuild;
3614 ){
3638 }
3640 #ifdef WHERETRACE_ENABLED
3645 }
3646 #endif
3647 #ifndef SQLITE_OMIT_VIRTUALTABLE
3651 #endif
3652 {
3654 }
3657 }
3669 WhereOrSet sPrev;
3677 }
3678 }
3679 }
3680 }
3688 /* TUNING: Currently sSum.a[i].rRun is set to the sum of the costs
3689 ** of all sub-scans required by the OR-scan. However, due to rounding
3690 ** errors, it may be that the cost of the OR-scan is equal to its
3691 ** most expensive sub-scan. Add the smallest possible penalty
3692 ** (equivalent to multiplying the cost by 1.07) to ensure that
3693 ** this does not happen. Otherwise, for WHERE clauses such as the
3694 ** following where there is an index on "y":
3695 **
3696 ** WHERE likelihood(x=?, 0.99) OR y=?
3697 **
3698 ** the planner may elect to "OR" together a full-table scan and an
3699 ** index lookup. And other similarly odd results. */
3704 }
3706 }
3707 }
3709 }
3711 /*
3712 ** Add all WhereLoop objects for all tables
3713 */
3726 /* Loop over the tables in the join, from left to right */
3736 /* This condition is true when pItem is the FROM clause term on the
3737 ** right-hand-side of a LEFT or CROSS JOIN. */
3741 }
3742 #ifndef SQLITE_OMIT_VIRTUALTABLE
3748 }
3749 }
3753 {
3755 }
3758 }
3762 /* We hit the query planner search limit set by iPlanLimit */
3767 }
3768 }
3769 }
3773 }
3775 /*
3776 ** Examine a WherePath (with the addition of the extra WhereLoop of the 6th
3777 ** parameters) to see if it outputs rows in the requested ORDER BY
3778 ** (or GROUP BY) without requiring a separate sort operation. Return N:
3779 **
3780 ** N>0: N terms of the ORDER BY clause are satisfied
3781 ** N==0: No terms of the ORDER BY clause are satisfied
3782 ** N<0: Unknown yet how many terms of ORDER BY might be satisfied.
3783 **
3784 ** Note that processing for WHERE_GROUPBY and WHERE_DISTINCTBY is not as
3785 ** strict. With GROUP BY and DISTINCT the only requirement is that
3786 ** equivalent rows appear immediately adjacent to one another. GROUP BY
3787 ** and DISTINCT do not require rows to appear in any particular order as long
3788 ** as equivalent rows are grouped together. Thus for GROUP BY and DISTINCT
3789 ** the pOrderBy terms can be matched in any order. With ORDER BY, the
3790 ** pOrderBy terms must be matched in strict left-to-right order.
3791 */
3800 ){
3826 /*
3827 ** We say the WhereLoop is "one-row" if it generates no more than one
3828 ** row of output. A WhereLoop is one-row if all of the following are true:
3829 ** (a) All index columns match with WHERE_COLUMN_EQ.
3830 ** (b) The index is unique
3831 ** Any WhereLoop with an WHERE_COLUMN_EQ constraint on the rowid is one-row.
3832 ** Every one-row WhereLoop will have the WHERE_ONEROW bit set in wsFlags.
3833 **
3834 ** We say the WhereLoop is "order-distinct" if the set of columns from
3835 ** that WhereLoop that are in the ORDER BY clause are different for every
3836 ** row of the WhereLoop. Every one-row WhereLoop is automatically
3837 ** order-distinct. A WhereLoop that has no columns in the ORDER BY clause
3838 ** is not order-distinct. To be order-distinct is not quite the same as being
3839 ** UNIQUE since a UNIQUE column or index can have multiple rows that
3840 ** are NULL and NULL values are equivalent for the purpose of order-distinct.
3841 ** To be order-distinct, the columns must be UNIQUE and NOT NULL.
3842 **
3843 ** The rowid for a table is always UNIQUE and NOT NULL so whenever the
3844 ** rowid appears in the ORDER BY clause, the corresponding WhereLoop is
3845 ** automatically order-distinct.
3846 */
3861 }
3869 }
3873 }
3877 }
3880 /* Mark off any ORDER BY term X that is a column in the table of
3881 ** the current loop for which there is term in the WHERE
3882 ** clause of the form X IS NULL or X=? that reference only outer
3883 ** loops.
3884 */
3895 /* IN terms are only valid for sorting in the ORDER BY LIMIT
3896 ** optimization, and then only if they are actually used
3897 ** by the query plan */
3902 }
3910 }
3912 }
3914 }
3929 /* All relevant terms of the index must also be non-NULL in order
3930 ** for isOrderDistinct to be true. So the isOrderDistint value
3931 ** computed here might be a false positive. Corrections will be
3932 ** made at tag-20210426-1 below */
3935 }
3937 /* Loop through all columns of the index and deal with the ones
3938 ** that are not constrained by == or IN.
3939 */
3947 );
3951 /* Skip over == and IS and ISNULL terms. (Also skip IN terms when
3952 ** doing WHERE_ORDERBY_LIMIT processing). Except, IS and ISNULL
3953 ** terms imply that the index is not UNIQUE NOT NULL in which case
3954 ** the loop need to be marked as not order-distinct because it can
3955 ** have repeated NULL rows.
3956 **
3957 ** If the current term is a column of an ((?,?) IN (SELECT...))
3958 ** expression for which the SELECT returns more than one column,
3959 ** check that it is the only column used by this loop. Otherwise,
3960 ** if it is one of two or more, none of the columns can be
3961 ** considered to match an ORDER BY term.
3962 */
3969 }
3972 /* ALWAYS() justification: eOp is an equality operator due to the
3973 ** j<pLoop->u.btree.nEq constraint above. Any equality other
3974 ** than WO_IN is captured by the previous "if". So this one
3975 ** always has to be WO_IN. */
3982 }
3983 }
3984 }
3985 }
3987 /* Get the column number in the table (iColumn) and sort order
3988 ** (revIdx) for the j-th column of the index.
3989 */
3997 }
3999 /* An unconstrained column that might be NULL means that this
4000 ** WhereLoop is not well-ordered. tag-20210426-1
4001 */
4006 ){
4008 }
4011 }
4012 }
4014 /* Find the ORDER BY term that corresponds to the j-th column
4015 ** of the index and mark that ORDER BY term off
4016 */
4033 }
4034 }
4038 }
4041 }
4044 }
4046 /* Make sure the sort order is compatible in an ORDER BY clause.
4047 ** Sort order is irrelevant for a GROUP BY clause. */
4051 }
4056 }
4057 }
4063 }
4064 }
4069 }
4072 /* No match found */
4076 }
4078 }
4083 }
4086 /* Mark off any other ORDER BY terms that reference pLoop */
4091 Bitmask mTerm;
4098 }
4099 }
4100 }
4107 }
4109 }
4111 }
4114 /*
4115 ** If the WHERE_GROUPBY flag is set in the mask passed to sqlite3WhereBegin(),
4116 ** the planner assumes that the specified pOrderBy list is actually a GROUP
4117 ** BY clause - and so any order that groups rows as required satisfies the
4118 ** request.
4119 **
4120 ** Normally, in this case it is not possible for the caller to determine
4121 ** whether or not the rows are really being delivered in sorted order, or
4122 ** just in some other order that provides the required grouping. However,
4123 ** if the WHERE_SORTBYGROUP flag is also passed to sqlite3WhereBegin(), then
4124 ** this function may be called on the returned WhereInfo object. It returns
4125 ** true if the rows really will be sorted in the specified order, or false
4126 ** otherwise.
4127 **
4128 ** For example, assuming:
4129 **
4130 ** CREATE INDEX i1 ON t1(x, Y);
4131 **
4132 ** then
4133 **
4134 ** SELECT * FROM t1 GROUP BY x,y ORDER BY x,y; -- IsSorted()==1
4135 ** SELECT * FROM t1 GROUP BY y,x ORDER BY y,x; -- IsSorted()==0
4136 */
4141 }
4143 #ifdef WHERETRACE_ENABLED
4144 /* For debugging use only: */
4152 }
4153 #endif
4155 /*
4156 ** Return the cost of sorting nRow rows, assuming that the keys have
4157 ** nOrderby columns and that the first nSorted columns are already in
4158 ** order.
4159 */
4162 LogEst nRow,
4164 int nSorted
4165 ){
4166 /* TUNING: Estimated cost of a full external sort, where N is
4167 ** the number of rows to sort is:
4168 **
4169 ** cost = (3.0 * N * log(N)).
4170 **
4171 ** Or, if the order-by clause has X terms but only the last Y
4172 ** terms are out of order, then block-sorting will reduce the
4173 ** sorting cost to:
4174 **
4175 ** cost = (3.0 * N * log(N)) * (Y/X)
4176 **
4177 ** The (Y/X) term is implemented using stack variable rScale
4178 ** below.
4179 */
4185 /* Multiple by log(M) where M is the number of output rows.
4186 ** Use the LIMIT for M if it is smaller. Or if this sort is for
4187 ** a DISTINCT operator, M will be the number of distinct output
4188 ** rows, so fudge it downwards a bit.
4189 */
4193 /* TUNING: In the sort for a DISTINCT operator, assume that the DISTINCT
4194 ** reduces the number of output rows by a factor of 2 */
4196 }
4199 }
4201 /*
4202 ** Given the list of WhereLoop objects at pWInfo->pLoops, this routine
4203 ** attempts to find the lowest cost path that visits each WhereLoop
4204 ** once. This path is then loaded into the pWInfo->a[].pWLoop fields.
4205 **
4206 ** Assume that the total number of output rows that will need to be sorted
4207 ** will be nRowEst (in the 10*log2 representation). Or, ignore sorting
4208 ** costs if nRowEst==0.
4209 **
4210 ** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation
4211 ** error occurs.
4212 */
4238 /* TUNING: For simple queries, only the best path is tracked.
4239 ** For 2-way joins, the 5 best paths are followed.
4240 ** For joins of 3 or more tables, track the 10 best paths */
4245 /* If nRowEst is zero and there is an ORDER BY clause, ignore it. In this
4246 ** case the purpose of this call is to estimate the number of rows returned
4247 ** by the overall query. Once this estimate has been obtained, the caller
4248 ** will invoke this function a second time, passing the estimate as the
4249 ** nRowEst parameter. */
4254 }
4256 /* Allocate and initialize space for aTo, aFrom and aSortCost[] */
4267 }
4269 /* If there is an ORDER BY clause and it is not being ignored, set up
4270 ** space for the aSortCost[] array. Each element of the aSortCost array
4271 ** is either zero - meaning it has not yet been initialized - or the
4272 ** cost of sorting nRowEst rows of data where the first X terms of
4273 ** the ORDER BY clause are already in order, where X is the array
4274 ** index. */
4277 }
4281 /* Seed the search with a single WherePath containing zero WhereLoops.
4282 **
4283 ** TUNING: Do not let the number of iterations go above 28. If the cost
4284 ** of computing an automatic index is not paid back within the first 28
4285 ** rows, then do not use the automatic index. */
4290 /* If nLoop is zero, then there are no FROM terms in the query. Since
4291 ** in this case the query may return a maximum of one row, the results
4292 ** are already in the requested order. Set isOrdered to nOrderBy to
4293 ** indicate this. Or, if nLoop is greater than zero, set isOrdered to
4294 ** -1, indicating that the result set may or may not be ordered,
4295 ** depending on the loops added to the current plan. */
4297 }
4299 /* Compute successively longer WherePaths using the previous generation
4300 ** of WherePaths as the basis for the next. Keep track of the mxChoice
4301 ** best paths at each generation */
4316 /* Do not use an automatic index if the this loop is expected
4317 ** to run less than 1.25 times. It is tempting to also exclude
4318 ** automatic index usage on an outer loop, but sometimes an automatic
4319 ** index is useful in the outer loop of a correlated subquery. */
4322 }
4324 /* At this point, pWLoop is a candidate to be the next loop.
4325 ** Compute its cost */
4336 }
4341 );
4342 }
4343 /* TUNING: Add a small extra penalty (5) to sorting as an
4344 ** extra encouragment to the query planner to select a plan
4345 ** where the rows emerge in the correct order without any sorting
4346 ** required. */
4356 }
4358 /* Check to see if pWLoop should be added to the set of
4359 ** mxChoice best-so-far paths.
4360 **
4361 ** First look for an existing path among best-so-far paths
4362 ** that covers the same set of loops and has the same isOrdered
4363 ** setting as the current path candidate.
4364 **
4365 ** The term "((pTo->isOrdered^isOrdered)&0x80)==0" is equivalent
4366 ** to (pTo->isOrdered==(-1))==(isOrdered==(-1))" for the range
4367 ** of legal values for isOrdered, -1..64.
4368 */
4372 ){
4375 }
4376 }
4378 /* None of the existing best-so-far paths match the candidate. */
4381 ){
4382 /* The current candidate is no better than any of the mxChoice
4383 ** paths currently in the best-so-far buffer. So discard
4384 ** this candidate as not viable. */
4390 }
4391 #endif
4393 }
4394 /* If we reach this points it means that the new candidate path
4395 ** needs to be added to the set of best-so-far paths. */
4397 /* Increase the size of the aTo set by one */
4400 /* New path replaces the prior worst to keep count below mxChoice */
4402 }
4409 }
4410 #endif
4412 /* Control reaches here if best-so-far path pTo=aTo[jj] covers the
4413 ** same set of loops and has the same isOrdered setting as the
4414 ** candidate path. Check to see if the candidate should replace
4415 ** pTo or if the candidate should be skipped.
4416 **
4417 ** The conditional is an expanded vector comparison equivalent to:
4418 ** (pTo->rCost,pTo->nRow,pTo->rUnsorted) <= (rCost,nOut,rUnsorted)
4419 */
4424 )
4425 )
4426 ){
4436 }
4437 #endif
4438 /* Discard the candidate path from further consideration */
4441 }
4443 /* Control reaches here if the candidate path is better than the
4444 ** pTo path. Replace pTo with the candidate. */
4454 }
4455 #endif
4456 }
4457 /* pWLoop is a winner. Add it to the set of best so far */
4473 ){
4477 }
4478 }
4479 }
4480 }
4481 }
4494 }
4495 }
4496 }
4497 #endif
4499 /* Swap the roles of aFrom and aTo for the next generation */
4504 }
4510 }
4512 /* Find the lowest cost path. pFrom will be left pointing to that path */
4516 }
4518 /* Load the lowest cost path into pWInfo */
4524 }
4528 && nRowEst
4529 ){
4530 Bitmask notUsed;
4535 }
4536 }
4542 }
4552 ){
4561 }
4562 }
4563 }
4567 ){
4569 }
4570 }
4573 ){
4577 );
4582 }
4583 }
4584 }
4589 /* Free temporary memory and return success */
4592 }
4594 /*
4595 ** Most queries use only a single table (they are not joins) and have
4596 ** simple == constraints against indexed fields. This routine attempts
4597 ** to plan those simple cases using much less ceremony than the
4598 ** general-purpose query planner, and thereby yield faster sqlite3_prepare()
4599 ** times for the common case.
4600 **
4601 ** Return non-zero on success, if this query can be handled by this
4602 ** no-frills query planner. Return zero if this query needs the
4603 ** general-purpose query planner.
4604 */
4615 WhereScan scan;
4637 /* TUNING: Cost of a rowid lookup is 10 */
4654 }
4659 }
4663 /* TUNING: Cost of a unique index lookup is 15 */
4666 }
4667 }
4678 }
4680 #ifdef SQLITE_DEBUG
4682 #endif
4683 #ifdef WHERETRACE_ENABLED
4686 }
4687 #endif
4689 }
4691 }
4693 /*
4694 ** Helper function for exprIsDeterministic().
4695 */
4700 }
4702 }
4704 /*
4705 ** Return true if the expression contains no non-deterministic SQL
4706 ** functions. Do not consider non-deterministic SQL functions that are
4707 ** part of sub-select statements.
4708 */
4710 Walker w;
4717 }
4720 #ifdef WHERETRACE_ENABLED
4721 /*
4722 ** Display all WhereLoops in pWInfo
4723 */
4733 }
4734 }
4735 }
4736 # define WHERETRACE_ALL_LOOPS(W,C) showAllWhereLoops(W,C)
4737 #else
4738 # define WHERETRACE_ALL_LOOPS(W,C)
4739 #endif
4741 /*
4742 ** Generate the beginning of the loop used for WHERE clause processing.
4743 ** The return value is a pointer to an opaque structure that contains
4744 ** information needed to terminate the loop. Later, the calling routine
4745 ** should invoke sqlite3WhereEnd() with the return value of this function
4746 ** in order to complete the WHERE clause processing.
4747 **
4748 ** If an error occurs, this routine returns NULL.
4749 **
4750 ** The basic idea is to do a nested loop, one loop for each table in
4751 ** the FROM clause of a select. (INSERT and UPDATE statements are the
4752 ** same as a SELECT with only a single table in the FROM clause.) For
4753 ** example, if the SQL is this:
4754 **
4755 ** SELECT * FROM t1, t2, t3 WHERE ...;
4756 **
4757 ** Then the code generated is conceptually like the following:
4758 **
4759 ** foreach row1 in t1 do \ Code generated
4760 ** foreach row2 in t2 do |-- by sqlite3WhereBegin()
4761 ** foreach row3 in t3 do /
4762 ** ...
4763 ** end \ Code generated
4764 ** end |-- by sqlite3WhereEnd()
4765 ** end /
4766 **
4767 ** Note that the loops might not be nested in the order in which they
4768 ** appear in the FROM clause if a different order is better able to make
4769 ** use of indices. Note also that when the IN operator appears in
4770 ** the WHERE clause, it might result in additional nested loops for
4771 ** scanning through all values on the right-hand side of the IN.
4772 **
4773 ** There are Btree cursors associated with each table. t1 uses cursor
4774 ** number pTabList->a[0].iCursor. t2 uses the cursor pTabList->a[1].iCursor.
4775 ** And so forth. This routine generates code to open those VDBE cursors
4776 ** and sqlite3WhereEnd() generates the code to close them.
4777 **
4778 ** The code that sqlite3WhereBegin() generates leaves the cursors named
4779 ** in pTabList pointing at their appropriate entries. The [...] code
4780 ** can use OP_Column and OP_Rowid opcodes on these cursors to extract
4781 ** data from the various tables of the loop.
4782 **
4783 ** If the WHERE clause is empty, the foreach loops must each scan their
4784 ** entire tables. Thus a three-way join is an O(N^3) operation. But if
4785 ** the tables have indices and there are terms in the WHERE clause that
4786 ** refer to those indices, a complete table scan can be avoided and the
4787 ** code will run much faster. Most of the work of this routine is checking
4788 ** to see if there are indices that can be used to speed up the loop.
4789 **
4790 ** Terms of the WHERE clause are also used to limit which rows actually
4791 ** make it to the "..." in the middle of the loop. After each "foreach",
4792 ** terms of the WHERE clause that use only terms in that loop and outer
4793 ** loops are evaluated and if false a jump is made around all subsequent
4794 ** inner loops (or around the "..." if the test occurs within the inner-
4795 ** most loop)
4796 **
4797 ** OUTER JOINS
4798 **
4799 ** An outer join of tables t1 and t2 is conceptally coded as follows:
4800 **
4801 ** foreach row1 in t1 do
4802 ** flag = 0
4803 ** foreach row2 in t2 do
4804 ** start:
4805 ** ...
4806 ** flag = 1
4807 ** end
4808 ** if flag==0 then
4809 ** move the row2 cursor to a null row
4810 ** goto start
4811 ** fi
4812 ** end
4813 **
4814 ** ORDER BY CLAUSE PROCESSING
4815 **
4816 ** pOrderBy is a pointer to the ORDER BY clause (or the GROUP BY clause
4817 ** if the WHERE_GROUPBY flag is set in wctrlFlags) of a SELECT statement
4818 ** if there is one. If there is no ORDER BY clause or if this routine
4819 ** is called from an UPDATE or DELETE statement, then pOrderBy is NULL.
4820 **
4821 ** The iIdxCur parameter is the cursor number of an index. If
4822 ** WHERE_OR_SUBCLAUSE is set, iIdxCur is the cursor number of an index
4823 ** to use for OR clause processing. The WHERE clause should use this
4824 ** specific cursor. If WHERE_ONEPASS_DESIRED is set, then iIdxCur is
4825 ** the first cursor in an array of cursors for all indices. iIdxCur should
4826 ** be used to compute the appropriate cursor depending on which index is
4827 ** used.
4828 */
4837 ** If WHERE_USE_LIMIT, then the limit amount */
4838 ){
4856 ));
4858 /* Only one of WHERE_OR_SUBCLAUSE or WHERE_USE_LIMIT */
4862 /* Variable initialization */
4866 /* An ORDER/GROUP BY clause of more than 63 terms cannot be optimized */
4871 /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via
4872 ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */
4875 }
4877 /* The number of tables in the FROM clause is limited by the number of
4878 ** bits in a Bitmask
4879 */
4884 }
4886 /* This function normally generates a nested loop for all tables in
4887 ** pTabList. But if the WHERE_OR_SUBCLAUSE flag is set, then we should
4888 ** only generate code for the first table in pTabList and assume that
4889 ** any cursors associated with subsequent tables are uninitialized.
4890 */
4893 /* Allocate and initialize the WhereInfo structure that will become the
4894 ** return value. A single allocation is used to store the WhereInfo
4895 ** struct, the contents of WhereInfo.a[], the WhereClause structure
4896 ** and the WhereMaskSet structure. Since WhereClause contains an 8-byte
4897 ** field (type Bitmask) it must be aligned on an 8-byte boundary on
4898 ** some architectures. Hence the ROUND8() below.
4899 */
4906 }
4928 #ifdef SQLITE_DEBUG
4930 #endif
4932 /* Split the WHERE clause into separate subexpressions where each
4933 ** subexpression is separated by an AND operator.
4934 */
4939 /* Special case: No FROM clause
4940 */
4945 }
4948 /* Assign a bit from the bitmask to every term in the FROM clause.
4949 **
4950 ** The N-th term of the FROM clause is assigned a bitmask of 1<<N.
4951 **
4952 ** The rule of the previous sentence ensures thta if X is the bitmask for
4953 ** a table T, then X-1 is the bitmask for all other tables to the left of T.
4954 ** Knowing the bitmask for all tables to the left of a left join is
4955 ** important. Ticket #3015.
4956 **
4957 ** Note that bitmasks are created for all pTabList->nSrc tables in
4958 ** pTabList, not just the first nTabList tables. nTabList is normally
4959 ** equal to pTabList->nSrc but might be shortened to 1 if the
4960 ** WHERE_OR_SUBCLAUSE flag is set.
4961 */
4967 #ifdef SQLITE_DEBUG
4968 {
4974 }
4975 }
4976 #endif
4977 }
4979 /* Analyze all of the subexpressions. */
4983 /* Special case: WHERE terms that do not refer to any tables in the join
4984 ** (constant expressions). Evaluate each such term, and jump over all the
4985 ** generated code if the result is not true.
4986 **
4987 ** Do not do this if the expression contains non-deterministic functions
4988 ** that are not within a sub-select. This is not strictly required, but
4989 ** preserves SQLite's legacy behaviour in the following two cases:
4990 **
4991 ** FROM ... WHERE random()>0; -- eval random() once per row
4992 ** FROM ... WHERE (SELECT random())>0; -- eval random() once overall
4993 */
5000 }
5001 }
5005 /* The DISTINCT marking is pointless. Ignore it. */
5008 /* Try to ORDER BY the result set to make distinct processing easier */
5011 }
5012 }
5014 /* Construct the WhereLoop objects */
5015 #if defined(WHERETRACE_ENABLED)
5020 }
5023 Select sSelect;
5031 }
5032 }
5036 }
5037 #endif
5043 #ifdef SQLITE_ENABLE_STAT4
5044 /* If one or more WhereTerm.truthProb values were used in estimating
5045 ** loop parameters, but then those truthProb values were subsequently
5046 ** changed based on STAT4 information while computing subsequent loops,
5047 ** then we need to rerun the whole loop building process so that all
5048 ** loops will be built using the revised truthProb values. */
5058 }
5061 }
5062 #endif
5070 }
5071 }
5074 }
5077 }
5078 #ifdef WHERETRACE_ENABLED
5083 }
5088 }
5092 }
5096 }
5097 }
5101 }
5102 }
5103 #endif
5105 /* Attempt to omit tables from the join that do not affect the result.
5106 ** For a table to not affect the result, the following must be true:
5107 **
5108 ** 1) The query must not be an aggregate.
5109 ** 2) The table must be the RHS of a LEFT JOIN.
5110 ** 3) Either the query must be DISTINCT, or else the ON or USING clause
5111 ** must contain a constraint that limits the scan of the table to
5112 ** at most a single row.
5113 ** 4) The table must not be referenced by any part of the query apart
5114 ** from its own USING or ON clause.
5115 **
5116 ** For example, given:
5117 **
5118 ** CREATE TABLE t1(ipk INTEGER PRIMARY KEY, v1);
5119 ** CREATE TABLE t2(ipk INTEGER PRIMARY KEY, v2);
5120 ** CREATE TABLE t3(ipk INTEGER PRIMARY KEY, v3);
5121 **
5122 ** then table t2 can be omitted from the following:
5123 **
5124 ** SELECT v1, v3 FROM t1
5125 ** LEFT JOIN t2 ON (t1.ipk=t2.ipk)
5126 ** LEFT JOIN t3 ON (t1.ipk=t3.ipk)
5127 **
5128 ** or from:
5129 **
5130 ** SELECT DISTINCT v1, v3 FROM t1
5131 ** LEFT JOIN t2
5132 ** LEFT JOIN t3 ON (t1.ipk=t3.ipk)
5133 */
5139 ){
5144 }
5153 ){
5155 }
5162 ){
5164 }
5165 }
5166 }
5173 }
5174 }
5178 }
5180 nTabList--;
5181 }
5182 }
5183 #if defined(WHERETRACE_ENABLED)
5187 }
5189 #endif
5192 /* If the caller is an UPDATE or DELETE statement that is requesting
5193 ** to use a one-pass algorithm, determine if this is appropriate.
5194 **
5195 ** A one-pass approach can be used if the caller has requested one
5196 ** and either (a) the scan visits at most one row or (b) each
5197 ** of the following are true:
5198 **
5199 ** * the caller has indicated that a one-pass approach can be used
5200 ** with multiple rows (by setting WHERE_ONEPASS_MULTIROW), and
5201 ** * the table is not a virtual table, and
5202 ** * either the scan does not use the OR optimization or the caller
5203 ** is a DELETE operation (WHERE_DUPLICATES_OK is only specified
5204 ** for DELETE).
5205 **
5206 ** The last qualification is because an UPDATE statement uses
5207 ** WhereInfo.aiCurOnePass[1] to determine whether or not it really can
5208 ** use a one-pass approach, and this is not set accurately for scans
5209 ** that use the OR optimization.
5210 */
5220 )){
5225 }
5227 }
5228 }
5229 }
5231 /* Open all tables in the pTabList and any indices selected for
5232 ** searching those tables.
5233 */
5244 /* Do nothing */
5246 #ifndef SQLITE_OMIT_VIRTUALTABLE
5252 /* noop */
5254 #endif
5261 };
5269 ){
5270 /* If we know that only a prefix of the record will be used,
5271 ** it is advantageous to reduce the "column count" field in
5272 ** the P4 operand of the OP_OpenRead/Write opcode. */
5278 }
5279 #ifdef SQLITE_ENABLE_CURSOR_HINTS
5283 #endif
5284 {
5286 }
5287 #ifdef SQLITE_ENABLE_COLUMN_USED_MASK
5290 #endif
5293 }
5298 /* iAuxArg is always set to a positive value if ONEPASS is possible */
5302 ){
5303 /* This is one term of an OR-optimization using the PRIMARY KEY of a
5304 ** WITHOUT ROWID table. No need for a separate index */
5312 iIndexCur++;
5314 }
5322 }
5335 ){
5337 }
5339 #ifdef SQLITE_ENABLE_COLUMN_USED_MASK
5340 {
5349 }
5352 }
5354 }
5355 }
5357 }
5361 /* Generate the code to do the search. Each iteration of the for
5362 ** loop below generates code for a single nested loop of the VM
5363 ** program.
5364 */
5371 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
5376 }
5377 #endif
5380 );
5386 }
5387 }
5389 /* Done. */
5394 /* Jump here if malloc fails */
5395 whereBeginError:
5401 }
5403 }
5405 /*
5406 ** Part of sqlite3WhereEnd() will rewrite opcodes to reference the
5407 ** index rather than the main table. In SQLITE_DEBUG mode, we want
5408 ** to trace those changes if PRAGMA vdbe_addoptrace=on. This routine
5409 ** does that.
5410 */
5411 #ifndef SQLITE_DEBUG
5413 #else
5414 # define OpcodeRewriteTrace(D,K,P) sqlite3WhereOpcodeRewriteTrace(D,K,P)
5418 VdbeOp *pOp
5419 ){
5422 }
5423 #endif
5425 /*
5426 ** Generate the end of the WHERE loop. See comments on
5427 ** sqlite3WhereBegin() for additional information.
5428 */
5439 /* Generate loop termination code.
5440 */
5447 #ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT
5457 ){
5462 }
5469 }
5471 /* The common case: Advance to the next row */
5483 }
5484 #ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT
5486 #endif
5489 }
5504 /* For LEFT JOIN queries, cursor pIn->iCur may not have been
5505 ** opened yet. This occurs for WHERE clauses such as
5506 ** "a = ? AND b IN (...)", where the index is on (a, b). If
5507 ** the RHS of the (a=?) is NULL, then the "b IN (...)" may
5508 ** never have been coded, but the body of the loop run to
5509 ** return the null-row. So, if the cursor is not open yet,
5510 ** jump over the OP_Next or OP_Prev instruction about to
5511 ** be coded. */
5515 }
5521 /* Retarget the OP_IsNull against the left operand of IN so
5522 ** it jumps past the OP_IfNoHope. This is because the
5523 ** OP_IsNull also bypasses the OP_Affinity opcode that is
5524 ** required by OP_IfNoHope. */
5526 }
5527 }
5532 }
5534 }
5535 }
5542 }
5543 #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
5548 }
5549 #endif
5557 }
5560 ){
5566 }
5568 }
5573 }
5575 }
5578 }
5580 /* The "break" point is here, just past the end of the outer loop.
5581 ** Set it.
5582 */
5595 /* For a co-routine, change all OP_Column references to the table of
5596 ** the co-routine into OP_Copy of result contained in a register.
5597 ** OP_Rowid becomes OP_Null.
5598 */
5604 }
5606 #ifdef SQLITE_ENABLE_EARLY_CURSOR_CLOSE
5607 /* Close all of the cursors that were opened by sqlite3WhereBegin.
5608 ** Except, do not close cursors that will be reused by the OR optimization
5609 ** (WHERE_OR_SUBCLAUSE). And do not close the OP_OpenWrite cursors
5610 ** created for the ONEPASS optimization.
5611 */
5615 ){
5619 }
5623 ){
5625 }
5626 }
5627 #endif
5629 /* If this scan uses an index, make VDBE code substitutions to read data
5630 ** from the index instead of from the table where possible. In some cases
5631 ** this optimization prevents the table from ever being read, which can
5632 ** yield a significant performance boost.
5633 **
5634 ** Calls to the code generator in between sqlite3WhereBegin and
5635 ** sqlite3WhereEnd will have created code that references the table
5636 ** directly. This loop scans all that code looking for opcodes
5637 ** that reference the table and converts them into opcodes that
5638 ** reference the index.
5639 */
5644 }
5647 ){
5652 }
5654 #ifdef SQLITE_DEBUG
5657 }
5658 /* Proof that the "+1" on the k value above is safe */
5663 #endif
5669 /* no-op */
5671 #ifdef SQLITE_ENABLE_OFFSET_SQL_FUNC
5673 #endif
5674 ){
5684 }
5690 }
5700 }
5701 #ifdef SQLITE_DEBUG
5702 k++;
5703 #endif
5705 #ifdef SQLITE_DEBUG
5707 #endif
5708 }
5709 }
5711 /* Final cleanup
5712 */
5717 }