| blob | bc0110779ea051f46e02c825002686879fffab5d |
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 ** Return the estimated number of output rows from a WHERE clause
24 */
27 }
29 /*
30 ** Return one of the WHERE_DISTINCT_xxxxx values to indicate how this
31 ** WHERE clause returns outputs for DISTINCT processing.
32 */
35 }
37 /*
38 ** Return TRUE if the WHERE clause returns rows in ORDER BY order.
39 ** Return FALSE if the output needs to be sorted.
40 */
43 }
45 /*
46 ** Return the VDBE address or label to jump to in order to continue
47 ** immediately with the next row of a WHERE clause.
48 */
52 }
54 /*
55 ** Return the VDBE address or label to jump to in order to break
56 ** out of a WHERE loop.
57 */
60 }
62 /*
63 ** Return TRUE if an UPDATE or DELETE statement can operate directly on
64 ** the rowids returned by a WHERE clause. Return FALSE if doing an
65 ** UPDATE or DELETE might change subsequent WHERE clause results.
66 **
67 ** If the ONEPASS optimization is used (if this routine returns true)
68 ** then also write the indices of open cursors used by ONEPASS
69 ** into aiCur[0] and aiCur[1]. iaCur[0] gets the cursor of the data
70 ** table and iaCur[1] gets the cursor used by an auxiliary index.
71 ** Either value may be -1, indicating that cursor is not used.
72 ** Any cursors returned will have been opened for writing.
73 **
74 ** aiCur[0] and aiCur[1] both get -1 if the where-clause logic is
75 ** unable to use the ONEPASS optimization.
76 */
80 }
82 /*
83 ** Move the content of pSrc into pDest
84 */
88 }
90 /*
91 ** Try to insert a new prerequisite/cost entry into the WhereOrSet pSet.
92 **
93 ** The new entry might overwrite an existing entry, or it might be
94 ** appended, or it might be discarded. Do whatever is the right thing
95 ** so that pSet keeps the N_OR_COST best entries seen so far.
96 */
101 LogEst nOut /* Number of outputs for the new entry */
102 ){
103 u16 i;
108 }
111 }
112 }
120 }
122 }
123 whereOrInsert_done:
128 }
130 /*
131 ** Initialize a preallocated WhereClause structure.
132 */
136 ){
142 }
144 /* Forward reference */
147 /*
148 ** Deallocate all memory associated with a WhereOrInfo object.
149 */
153 }
155 /*
156 ** Deallocate all memory associated with a WhereAndInfo object.
157 */
161 }
163 /*
164 ** Deallocate a WhereClause structure. The WhereClause structure
165 ** itself is not freed. This routine is the inverse of whereClauseInit().
166 */
174 }
179 }
180 }
183 }
184 }
186 /*
187 ** Add a single new WhereTerm entry to the WhereClause object pWC.
188 ** The new WhereTerm object is constructed from Expr p and with wtFlags.
189 ** The index in pWC->a[] of the new WhereTerm is returned on success.
190 ** 0 is returned if the new WhereTerm could not be added due to a memory
191 ** allocation error. The memory allocation failure will be recorded in
192 ** the db->mallocFailed flag so that higher-level functions can detect it.
193 **
194 ** This routine will increase the size of the pWC->a[] array as necessary.
195 **
196 ** If the wtFlags argument includes TERM_DYNAMIC, then responsibility
197 ** for freeing the expression p is assumed by the WhereClause object pWC.
198 ** This is true even if this routine fails to allocate a new WhereTerm.
199 **
200 ** WARNING: This routine might reallocate the space used to store
201 ** WhereTerms. All pointers to WhereTerms should be invalidated after
202 ** calling this routine. Such pointers may be reinitialized by referencing
203 ** the pWC->a[] array.
204 */
216 }
219 }
223 }
225 }
231 }
237 }
239 /*
240 ** This routine identifies subexpressions in the WHERE clause where
241 ** each subexpression is separated by the AND operator or some other
242 ** operator specified in the op parameter. The WhereClause structure
243 ** is filled with pointers to subexpressions. For example:
244 **
245 ** WHERE a=='hello' AND coalesce(b,11)<10 AND (c+12!=d OR c==22)
246 ** \________/ \_______________/ \________________/
247 ** slot[0] slot[1] slot[2]
248 **
249 ** The original WHERE clause in pExpr is unaltered. All this routine
250 ** does is make slot[] entries point to substructure within pExpr.
251 **
252 ** In the previous sentence and in the diagram, "slot[]" refers to
253 ** the WhereClause.a[] array. The slot[] array grows as needed to contain
254 ** all terms of the WHERE clause.
255 */
264 }
265 }
267 /*
268 ** Initialize a WhereMaskSet object
269 */
270 #define initMaskSet(P) (P)->n=0
272 /*
273 ** Return the bitmask for the given cursor number. Return 0 if
274 ** iCursor is not in the set.
275 */
282 }
283 }
285 }
287 /*
288 ** Create a new mask for cursor iCursor.
289 **
290 ** There is one cursor per table in the FROM clause. The number of
291 ** tables in the FROM clause is limited by a test early in the
292 ** sqlite3WhereBegin() routine. So we know that the pMaskSet->ix[]
293 ** array will never overflow.
294 */
298 }
300 /*
301 ** These routines walk (recursively) an expression tree and generate
302 ** a bitmask indicating which tables are used in that expression
303 ** tree.
304 */
313 }
320 }
322 }
329 }
330 }
332 }
347 }
348 }
350 }
352 }
354 /*
355 ** Return TRUE if the given operator is one of the operators that is
356 ** allowed for an indexable WHERE clause term. The allowed operators are
357 ** "=", "<", ">", "<=", ">=", "IN", and "IS NULL"
358 */
365 }
367 /*
368 ** Commute a comparison operator. Expressions of the form "X op Y"
369 ** are converted into "Y op X".
370 **
371 ** If left/right precedence rules come into play when determining the
372 ** collating sequence, then COLLATE operators are adjusted to ensure
373 ** that the collating sequence does not change. For example:
374 ** "Y collate NOCASE op X" becomes "X op Y" because any collation sequence on
375 ** the left hand side of a comparison overrides any collation sequence
376 ** attached to the right. For the same reason the EP_Collate flag
377 ** is not commuted.
378 */
384 /* Either X and Y both have COLLATE operator or neither do */
386 /* Both X and Y have COLLATE operators. Make sure X is always
387 ** used by clearing the EP_Collate flag from Y. */
390 /* Neither X nor Y have COLLATE operators, but X has a non-default
391 ** collating sequence. So add the EP_Collate marker on X to cause
392 ** it to be searched first. */
394 }
395 }
404 }
405 }
407 /*
408 ** Translate from TK_xx operator to WO_xx bitmask.
409 */
411 u16 c;
420 }
429 }
431 /*
432 ** Advance to the next WhereTerm that matches according to the criteria
433 ** established when the pScan object was initialized by whereScanInit().
434 ** Return NULL if there are no more matching WhereTerms.
435 */
452 ){
455 ){
463 }
464 }
469 }
470 }
472 /* Verify the affinity and collating sequence match */
479 }
486 }
487 }
492 ){
494 }
497 }
498 }
499 }
502 }
506 }
508 }
510 /*
511 ** Initialize a WHERE clause scanner object. Return a pointer to the
512 ** first match. Return NULL if there are no matches.
513 **
514 ** The scanner will be searching the WHERE clause pWC. It will look
515 ** for terms of the form "X <op> <expr>" where X is column iColumn of table
516 ** iCur. The <op> must be one of the operators described by opMask.
517 **
518 ** If the search is for X and the WHERE clause contains terms of the
519 ** form X=Y then this routine might also return terms of the form
520 ** "Y <op> <expr>". The number of levels of transitivity is limited,
521 ** but is enough to handle most commonly occurring SQL statements.
522 **
523 ** If X is not the INTEGER PRIMARY KEY then X must be compatible with
524 ** index pIdx.
525 */
533 ){
536 /* memset(pScan, 0, sizeof(*pScan)); */
543 }
548 }
556 }
558 /*
559 ** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
560 ** where X is a reference to the iColumn of table iCur and <op> is one of
561 ** the WO_xx operator codes specified by the op parameter.
562 ** Return a pointer to the term. Return 0 if not found.
563 **
564 ** The term returned might by Y=<expr> if there is another constraint in
565 ** the WHERE clause that specifies that X=Y. Any such constraints will be
566 ** identified by the WO_EQUIV bit in the pTerm->eOperator field. The
567 ** aEquiv[] array holds X and all its equivalents, with each SQL variable
568 ** taking up two slots in aEquiv[]. The first slot is for the cursor number
569 ** and the second is for the column number. There are 22 slots in aEquiv[]
570 ** so that means we can look for X plus up to 10 other equivalent values.
571 ** Hence a search for X will return <expr> if X=A1 and A1=A2 and A2=A3
572 ** and ... and A9=A10 and A10=<expr>.
573 **
574 ** If there are multiple terms in the WHERE clause of the form "X <op> <expr>"
575 ** then try for the one with no dependencies on <expr> - in other words where
576 ** <expr> is a constant expression of some kind. Only return entries of
577 ** the form "X <op> Y" where Y is a column in another table if no terms of
578 ** the form "X <op> <const-expr>" exist. If no terms with a constant RHS
579 ** exist, try to return a term that does not use WO_EQUIV.
580 */
588 ){
591 WhereScan scan;
598 }
600 }
602 }
604 }
606 /* Forward reference */
609 /*
610 ** Call exprAnalyze on all terms in a WHERE clause.
611 */
615 ){
619 }
620 }
622 #ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
623 /*
624 ** Check to see if the given expression is a LIKE or GLOB operator that
625 ** can be optimized using inequality constraints. Return TRUE if it is
626 ** so and false if not.
627 **
628 ** In order for the operator to be optimizible, the RHS must be a string
629 ** literal that does not begin with a wildcard.
630 */
637 ){
650 }
651 #ifdef SQLITE_EBCDIC
653 #endif
659 ){
660 /* IMP: R-02065-49465 The left-hand side of the LIKE or GLOB operator must
661 ** be the name of an indexed column with TEXT affinity. */
663 }
674 }
679 }
683 cnt++;
684 }
695 /* If the rhs of the LIKE expression is a variable, and the current
696 ** value of the variable means there is no need to invoke the LIKE
697 ** function, then no OP_Variable will be added to the program.
698 ** This causes problems for the sqlite3_bind_parameter_name()
699 ** API. To work around them, add a dummy OP_Variable here.
700 */
705 }
706 }
709 }
710 }
714 }
718 #ifndef SQLITE_OMIT_VIRTUALTABLE
719 /*
720 ** Check to see if the given expression is of the form
721 **
722 ** column MATCH expr
723 **
724 ** If it is then return TRUE. If not, return FALSE.
725 */
728 ){
733 }
736 }
740 }
743 }
745 }
748 /*
749 ** If the pBase expression originated in the ON or USING clause of
750 ** a join, then transfer the appropriate markings over to derived.
751 */
756 }
757 }
759 #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
760 /*
761 ** Analyze a term that consists of two or more OR-connected
762 ** subterms. So in:
763 **
764 ** ... WHERE (a=5) AND (b=7 OR c=9 OR d=13) AND (d=13)
765 ** ^^^^^^^^^^^^^^^^^^^^
766 **
767 ** This routine analyzes terms such as the middle term in the above example.
768 ** A WhereOrTerm object is computed and attached to the term under
769 ** analysis, regardless of the outcome of the analysis. Hence:
770 **
771 ** WhereTerm.wtFlags |= TERM_ORINFO
772 ** WhereTerm.u.pOrInfo = a dynamically allocated WhereOrTerm object
773 **
774 ** The term being analyzed must have two or more of OR-connected subterms.
775 ** A single subterm might be a set of AND-connected sub-subterms.
776 ** Examples of terms under analysis:
777 **
778 ** (A) t1.x=t2.y OR t1.x=t2.z OR t1.y=15 OR t1.z=t3.a+5
779 ** (B) x=expr1 OR expr2=x OR x=expr3
780 ** (C) t1.x=t2.y OR (t1.x=t2.z AND t1.y=15)
781 ** (D) x=expr1 OR (y>11 AND y<22 AND z LIKE '*hello*')
782 ** (E) (p.a=1 AND q.b=2 AND r.c=3) OR (p.x=4 AND q.y=5 AND r.z=6)
783 **
784 ** CASE 1:
785 **
786 ** If all subterms are of the form T.C=expr for some single column of C and
787 ** a single table T (as shown in example B above) then create a new virtual
788 ** term that is an equivalent IN expression. In other words, if the term
789 ** being analyzed is:
790 **
791 ** x = expr1 OR expr2 = x OR x = expr3
792 **
793 ** then create a new virtual term like this:
794 **
795 ** x IN (expr1,expr2,expr3)
796 **
797 ** CASE 2:
798 **
799 ** If all subterms are indexable by a single table T, then set
800 **
801 ** WhereTerm.eOperator = WO_OR
802 ** WhereTerm.u.pOrInfo->indexable |= the cursor number for table T
803 **
804 ** A subterm is "indexable" if it is of the form
805 ** "T.C <op> <expr>" where C is any column of table T and
806 ** <op> is one of "=", "<", "<=", ">", ">=", "IS NULL", or "IN".
807 ** A subterm is also indexable if it is an AND of two or more
808 ** subsubterms at least one of which is indexable. Indexable AND
809 ** subterms have their eOperator set to WO_AND and they have
810 ** u.pAndInfo set to a dynamically allocated WhereAndTerm object.
811 **
812 ** From another point of view, "indexable" means that the subterm could
813 ** potentially be used with an index if an appropriate index exists.
814 ** This analysis does not consider whether or not the index exists; that
815 ** is decided elsewhere. This analysis only looks at whether subterms
816 ** appropriate for indexing exist.
817 **
818 ** All examples A through E above satisfy case 2. But if a term
819 ** also satisfies case 1 (such as B) we know that the optimizer will
820 ** always prefer case 1, so in that case we pretend that case 2 is not
821 ** satisfied.
822 **
823 ** It might be the case that multiple tables are indexable. For example,
824 ** (E) above is indexable on tables P, Q, and R.
825 **
826 ** Terms that satisfy case 2 are candidates for lookup by using
827 ** separate indices to find rowids for each subterm and composing
828 ** the union of all rowids using a RowSet object. This is similar
829 ** to "bitmap indices" in other database engines.
830 **
831 ** OTHERWISE:
832 **
833 ** If neither case 1 nor case 2 apply, then leave the eOperator set to
834 ** zero. This term is not useful for search.
835 */
840 ){
853 /*
854 ** Break the OR clause into its separate subterms. The subterms are
855 ** stored in a WhereClause structure containing within the WhereOrInfo
856 ** object that is attached to the original OR clause term.
857 */
870 /*
871 ** Compute the set of tables that might satisfy cases 1 or 2.
872 */
900 }
901 }
902 }
904 }
906 /* Skip this term for now. We revisit it when we process the
907 ** corresponding TERM_VIRTUAL term */
909 Bitmask b;
914 }
920 }
921 }
922 }
924 /*
925 ** Record the set of tables that satisfy case 2. The set might be
926 ** empty.
927 */
931 /*
932 ** chngToIN holds a set of tables that *might* satisfy case 1. But
933 ** we have to do some additional checking to see if case 1 really
934 ** is satisfied.
935 **
936 ** chngToIN will hold either 0, 1, or 2 bits. The 0-bit case means
937 ** that there is no possibility of transforming the OR clause into an
938 ** IN operator because one or more terms in the OR clause contain
939 ** something other than == on a column in the single table. The 1-bit
940 ** case means that every term of the OR clause is of the form
941 ** "table.column=expr" for some single table. The one bit that is set
942 ** will correspond to the common table. We still need to check to make
943 ** sure the same column is used on all terms. The 2-bit case is when
944 ** the all terms are of the form "table1.column=table2.column". It
945 ** might be possible to form an IN operator with either table1.column
946 ** or table2.column as the LHS if either is common to every term of
947 ** the OR clause.
948 **
949 ** Note that terms of the form "table.column1=table.column2" (the
950 ** same table on both sizes of the ==) cannot be optimized.
951 */
958 /* Search for a table and column that appears on one side or the
959 ** other of the == operator in every subterm. That table and column
960 ** will be recorded in iCursor and iColumn. There might not be any
961 ** such table and column. Set okToChngToIN if an appropriate table
962 ** and column is found but leave okToChngToIN false if not found.
963 */
970 /* This is the 2-bit case and we are on the second iteration and
971 ** current term is from the first iteration. So skip this term. */
974 }
976 /* This term must be of the form t1.a==t2.b where t2 is in the
977 ** chngToIN set but t1 is not. This term will be either preceded
978 ** or follwed by an inverted copy (t2.b==t1.a). Skip this term
979 ** and use its inversion. */
984 }
988 }
990 /* No candidate table+column was found. This can only occur
991 ** on the second iteration */
996 }
999 /* We have found a candidate table and column. Check to see if that
1000 ** table and column is common to every term in the OR clause */
1010 /* If the right-hand side is also a column, then the affinities
1011 ** of both right and left sides must be such that no type
1012 ** conversions are required on the right. (Ticket #2249)
1013 */
1020 }
1021 }
1022 }
1023 }
1025 /* At this point, okToChngToIN is true if original pTerm satisfies
1026 ** case 1. In that case, construct a new virtual term that is
1027 ** pTerm converted into an IN operator.
1028 */
1043 }
1060 }
1062 }
1063 }
1064 }
1067 /*
1068 ** The input to this routine is an WhereTerm structure with only the
1069 ** "pExpr" field filled in. The job of this routine is to analyze the
1070 ** subexpression and populate all the other fields of the WhereTerm
1071 ** structure.
1072 **
1073 ** If the expression is of the form "<expr> <op> X" it gets commuted
1074 ** to the standard form of "X <op> <expr>".
1075 **
1076 ** If the expression is of the form "X <op> Y" where both X and Y are
1077 ** columns, then the original expression is unchanged and a new virtual
1078 ** term of the form "Y <op> X" is added to the WHERE clause and
1079 ** analyzed separately. The original term is marked with TERM_COPIED
1080 ** and the new term is marked with TERM_DYNAMIC (because it's pExpr
1081 ** needs to be freed with the WhereClause) and TERM_VIRTUAL (because it
1082 ** is a commuted copy of a prior term.) The original term has nChild=1
1083 ** and the copy has idxParent set to the index of the original term.
1084 */
1089 ){
1106 }
1119 }
1124 }
1130 ** on left table of a LEFT JOIN. Ticket #3015 */
1131 }
1144 }
1155 }
1166 ){
1169 }
1173 }
1182 }
1183 }
1185 #ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
1186 /* If a term is the BETWEEN operator, create two new virtual terms
1187 ** that define the range that the BETWEEN implements. For example:
1188 **
1189 ** a BETWEEN b AND c
1190 **
1191 ** is converted into:
1192 **
1193 ** (a BETWEEN b AND c) AND (a>=b) AND (a<=c)
1194 **
1195 ** The two new terms are added onto the end of the WhereClause object.
1196 ** The new terms are "dynamic" and are children of the original BETWEEN
1197 ** term. That means that if the BETWEEN term is coded, the children are
1198 ** skipped. Or, if the children are satisfied by an index, the original
1199 ** BETWEEN term is skipped.
1200 */
1219 }
1221 }
1224 #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
1225 /* Analyze a term that is composed of two or more subterms connected by
1226 ** an OR operator.
1227 */
1232 }
1235 #ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
1236 /* Add constraints to reduce the search space on a LIKE or GLOB
1237 ** operator.
1238 **
1239 ** A like pattern of the form "x LIKE 'abc%'" is changed into constraints
1240 **
1241 ** x>='abc' AND x<'abd' AND x LIKE 'abc%'
1242 **
1243 ** The last character of the prefix "abc" is incremented to form the
1244 ** termination condition "abd".
1245 */
1248 ){
1264 /* The point is to increment the last character before the first
1265 ** wildcard. But if we increment '@', that will push it into the
1266 ** alphabetic range where case conversions will mess up the
1267 ** inequality. To avoid this, make sure to also run the full
1268 ** LIKE on all candidate expressions by clearing the isComplete flag
1269 */
1272 }
1274 }
1298 }
1299 }
1302 #ifndef SQLITE_OMIT_VIRTUALTABLE
1303 /* Add a WO_MATCH auxiliary term to the constraint set if the
1304 ** current expression is of the form: column MATCH expr.
1305 ** This information is used by the xBestIndex methods of
1306 ** virtual tables. The native query optimizer does not attempt
1307 ** to do anything with MATCH functions.
1308 */
1335 }
1336 }
1339 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
1340 /* When sqlite_stat3 histogram data is available an operator of the
1341 ** form "x IS NOT NULL" can sometimes be evaluated more efficiently
1342 ** as "x>NULL" if x is not an INTEGER PRIMARY KEY. So construct a
1343 ** virtual term of that form.
1344 **
1345 ** Note that the virtual term must be tagged with TERM_VNULL. This
1346 ** TERM_VNULL tag will suppress the not-null check at the beginning
1347 ** of the loop. Without the TERM_VNULL flag, the not-null check at
1348 ** the start of the loop will prevent any results from being returned.
1349 */
1354 ){
1377 }
1378 }
1381 /* Prevent ON clause terms of a LEFT JOIN from being used to drive
1382 ** an index for tables to the left of the join.
1383 */
1385 }
1387 /*
1388 ** This function searches pList for an entry that matches the iCol-th column
1389 ** of index pIdx.
1390 **
1391 ** If such an expression is found, its index in pList->a[] is returned. If
1392 ** no expression is found, -1 is returned.
1393 */
1400 ){
1409 ){
1413 }
1414 }
1415 }
1418 }
1420 /*
1421 ** Return true if the DISTINCT expression-list passed as the third argument
1422 ** is redundant.
1423 **
1424 ** A DISTINCT list is redundant if the database contains some subset of
1425 ** columns that are unique and non-null.
1426 */
1432 ){
1438 /* If there is more than one table or sub-select in the FROM clause of
1439 ** this query, then it will not be possible to show that the DISTINCT
1440 ** clause is redundant. */
1445 /* If any of the expressions is an IPK column on table iBase, then return
1446 ** true. Note: The (p->iTable==iBase) part of this test may be false if the
1447 ** current SELECT is a correlated sub-query.
1448 */
1452 }
1454 /* Loop through all indices on the table, checking each to see if it makes
1455 ** the DISTINCT qualifier redundant. It does so if:
1456 **
1457 ** 1. The index is itself UNIQUE, and
1458 **
1459 ** 2. All of the columns in the index are either part of the pDistinct
1460 ** list, or else the WHERE clause contains a term of the form "col=X",
1461 ** where X is a constant value. The collation sequences of the
1462 ** comparison and select-list expressions must match those of the index.
1463 **
1464 ** 3. All of those index columns for which the WHERE clause does not
1465 ** contain a "col=X" term are subject to a NOT NULL constraint.
1466 */
1475 }
1476 }
1477 }
1479 /* This index implies that the DISTINCT qualifier is redundant. */
1481 }
1482 }
1485 }
1488 /*
1489 ** Estimate the logarithm of the input value to base 2.
1490 */
1493 }
1495 /*
1496 ** Two routines for printing the content of an sqlite3_index_info
1497 ** structure. Used for testing and debugging only. If neither
1498 ** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines
1499 ** are no-ops.
1500 */
1501 #if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(WHERETRACE_ENABLED)
1507 i,
1512 }
1515 i,
1518 }
1519 }
1525 i,
1528 }
1534 }
1535 #else
1536 #define TRACE_IDX_INPUTS(A)
1537 #define TRACE_IDX_OUTPUTS(A)
1538 #endif
1540 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
1541 /*
1542 ** Return TRUE if the WHERE clause term pTerm is of a form where it
1543 ** could be used with an index to access pSrc, assuming an appropriate
1544 ** index existed.
1545 */
1549 Bitmask notReady /* Tables in outer loops of the join */
1550 ){
1559 }
1560 #endif
1563 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
1564 /*
1565 ** Generate code to construct the Index object for an automatic index
1566 ** and to set up the WhereLevel object pLevel so that the code generator
1567 ** makes use of the automatic index.
1568 */
1575 ){
1595 /* Generate code to skip over the creation and initialization of the
1596 ** transient index on 2nd and subsequent iterations of the loop. */
1601 /* Count the number of columns that will be added to the index
1602 ** and used to match WHERE clause constraints */
1619 }
1624 }
1625 }
1626 }
1632 /* Count the number of additional columns needed to create a
1633 ** covering index. A "covering index" is an index that contains all
1634 ** columns that are needed by the query. With a covering index, the
1635 ** original table never needs to be accessed. Automatic indices must
1636 ** be a covering index because the index will not be updated if the
1637 ** original table changes and the index and table cannot both be used
1638 ** if they go out of sync.
1639 */
1646 }
1649 }
1652 /* Construct the Index object to describe this index */
1672 n++;
1673 }
1674 }
1675 }
1678 /* Add additional columns needed to make the automatic index into
1679 ** a covering index */
1684 n++;
1685 }
1686 }
1691 n++;
1692 }
1693 }
1698 /* Create the automatic index */
1705 /* Fill the automatic index with content */
1716 /* Jump here when skipping the initialization */
1718 }
1721 #ifndef SQLITE_OMIT_VIRTUALTABLE
1722 /*
1723 ** Allocate and populate an sqlite3_index_info structure. It is the
1724 ** responsibility of the caller to eventually release the structure
1725 ** by passing the pointer returned by this function to sqlite3_free().
1726 */
1731 ExprList *pOrderBy
1732 ){
1742 /* Count the number of possible WHERE clause constraints referring
1743 ** to this virtual table */
1752 nTerm++;
1753 }
1755 /* If the ORDER BY clause contains only columns in the current
1756 ** virtual table then allocate space for the aOrderBy part of
1757 ** the sqlite3_index_info structure.
1758 */
1765 }
1768 }
1769 }
1771 /* Allocate the sqlite3_index_info structure
1772 */
1779 }
1781 /* Initialize the structure. The sqlite3_index_info structure contains
1782 ** many fields that are declared "const" to prevent xBestIndex from
1783 ** changing them. We have to do some funky casting in order to
1784 ** initialize those fields.
1785 */
1794 pUsage;
1797 u8 op;
1810 /* The direct assignment in the previous line is possible only because
1811 ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical. The
1812 ** following asserts verify this fact. */
1820 j++;
1821 }
1826 }
1829 }
1831 /*
1832 ** The table object reference passed as the second argument to this function
1833 ** must represent a virtual table. This function invokes the xBestIndex()
1834 ** method of the virtual table with the sqlite3_index_info object that
1835 ** comes in as the 3rd argument to this function.
1836 **
1837 ** If an error occurs, pParse is populated with an error message and a
1838 ** non-zero value is returned. Otherwise, 0 is returned and the output
1839 ** part of the sqlite3_index_info structure is left populated.
1840 **
1841 ** Whether or not an error is returned, it is the responsibility of the
1842 ** caller to eventually free p->idxStr if p->needToFreeIdxStr indicates
1843 ** that this is required.
1844 */
1861 }
1862 }
1870 }
1871 }
1874 }
1878 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
1879 /*
1880 ** Estimate the location of a particular key among all keys in an
1881 ** index. Store the results in aStat as follows:
1882 **
1883 ** aStat[0] Est. number of rows less than pVal
1884 ** aStat[1] Est. number of rows equal to pVal
1885 **
1886 ** Return SQLITE_OK on success.
1887 */
1894 ){
1902 #ifndef SQLITE_DEBUG
1904 #endif
1916 }
1919 #ifdef SQLITE_DEBUG
1920 /* The following assert statements check that the binary search code
1921 ** above found the right answer. This block serves no purpose other
1922 ** than to invoke the asserts. */
1924 /* If (res==0) is true, then sample $i must be equal to pRec */
1929 /* Otherwise, pRec must be smaller than sample $i and larger than
1930 ** sample ($i-1). */
1937 }
1940 /* At this point, aSample[i] is the first sample that is greater than
1941 ** or equal to pVal. Or if i==pIdx->nSample, then all samples are less
1942 ** than pVal. If aSample[i]==pVal, then res==0.
1943 */
1956 }
1962 }
1967 }
1969 }
1970 }
1973 /*
1974 ** If it is not NULL, pTerm is a term that provides an upper or lower
1975 ** bound on a range scan. Without considering pTerm, it is estimated
1976 ** that the scan will visit nNew rows. This function returns the number
1977 ** estimated to be visited after taking pTerm into account.
1978 **
1979 ** If the user explicitly specified a likelihood() value for this term,
1980 ** then the return value is the likelihood multiplied by the number of
1981 ** input rows. Otherwise, this function assumes that an "IS NOT NULL" term
1982 ** has a likelihood of 0.50, and any other term a likelihood of 0.25.
1983 */
1991 }
1992 }
1994 }
1996 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
1997 /*
1998 ** This function is called to estimate the number of rows visited by a
1999 ** range-scan on a skip-scan index. For example:
2000 **
2001 ** CREATE INDEX i1 ON t1(a, b, c);
2002 ** SELECT * FROM t1 WHERE a=? AND c BETWEEN ? AND ?;
2003 **
2004 ** Value pLoop->nOut is currently set to the estimated number of rows
2005 ** visited for scanning (a=? AND b=?). This function reduces that estimate
2006 ** by some factor to account for the (c BETWEEN ? AND ?) expression based
2007 ** on the stat4 data for the index. this scan will be peformed multiple
2008 ** times (once for each (a,b) combination that matches a=?) is dealt with
2009 ** by the caller.
2010 **
2011 ** It does this by scanning through all stat4 samples, comparing values
2012 ** extracted from pLower and pUpper with the corresponding column in each
2013 ** sample. If L and U are the number of samples found to be less than or
2014 ** equal to the values extracted from pLower and pUpper respectively, and
2015 ** N is the total number of samples, the pLoop->nOut value is adjusted
2016 ** as follows:
2017 **
2018 ** nOut = nOut * ( min(U - L, 1) / N )
2019 **
2020 ** If pLower is NULL, or a value cannot be extracted from the term, L is
2021 ** set to zero. If pUpper is NULL, or a value cannot be extracted from it,
2022 ** U is set to N.
2023 **
2024 ** Normally, this function sets *pbDone to 1 before returning. However,
2025 ** if no value can be extracted from either pLower or pUpper (and so the
2026 ** estimate of the number of rows delivered remains unchanged), *pbDone
2027 ** is left as is.
2028 **
2029 ** If an error occurs, an SQLite error code is returned. Otherwise,
2030 ** SQLITE_OK.
2031 */
2038 ){
2057 }
2061 }
2071 }
2075 }
2076 }
2080 /* If there is both an upper and lower bound specified, and the
2081 ** comparisons indicate that they are close together, use the fallback
2082 ** method (assume that the scan visits 1/64 of the rows) for estimating
2083 ** the number of rows visited. Otherwise, estimate the number of rows
2084 ** using the method described in the header comment for this function. */
2091 }
2095 }
2102 }
2105 /*
2106 ** This function is used to estimate the number of rows that will be visited
2107 ** by scanning an index for a range of values. The range may have an upper
2108 ** bound, a lower bound, or both. The WHERE clause terms that set the upper
2109 ** and lower bounds are represented by pLower and pUpper respectively. For
2110 ** example, assuming that index p is on t1(a):
2111 **
2112 ** ... FROM t1 WHERE a > ? AND a < ? ...
2113 ** |_____| |_____|
2114 ** | |
2115 ** pLower pUpper
2116 **
2117 ** If either of the upper or lower bound is not present, then NULL is passed in
2118 ** place of the corresponding WhereTerm.
2119 **
2120 ** The value in (pBuilder->pNew->u.btree.nEq) is the index of the index
2121 ** column subject to the range constraint. Or, equivalently, the number of
2122 ** equality constraints optimized by the proposed index scan. For example,
2123 ** assuming index p is on t1(a, b), and the SQL query is:
2124 **
2125 ** ... FROM t1 WHERE a = ? AND b > ? AND b < ? ...
2126 **
2127 ** then nEq is set to 1 (as the range restricted column, b, is the second
2128 ** left-most column of the index). Or, if the query is:
2129 **
2130 ** ... FROM t1 WHERE a > ? AND a < ? ...
2131 **
2132 ** then nEq is set to 0.
2133 **
2134 ** When this function is called, *pnOut is set to the sqlite3LogEst() of the
2135 ** number of rows that the index scan is expected to visit without
2136 ** considering the range constraints. If nEq is 0, this is the number of
2137 ** rows in the index. Assuming no error occurs, *pnOut is adjusted (reduced)
2138 ** to account for the range constraints pLower and pUpper.
2139 **
2140 ** In the absence of sqlite_stat4 ANALYZE data, or if such data cannot be
2141 ** used, a single range inequality reduces the search space by a factor of 4.
2142 ** and a pair of constraints (x>? AND x<?) reduces the expected number of
2143 ** rows visited by a factor of 64.
2144 */
2151 ){
2154 LogEst nNew;
2156 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
2163 ){
2167 u8 aff;
2169 /* Variable iLower will be set to the estimate of the number of rows in
2170 ** the index that are less than the lower bound of the range query. The
2171 ** lower bound being the concatenation of $P and $L, where $P is the
2172 ** key-prefix formed by the nEq values matched against the nEq left-most
2173 ** columns of the index, and $L is the value in pLower.
2174 **
2175 ** Or, if pLower is NULL or $L cannot be extracted from it (because it
2176 ** is not a simple variable or literal value), the lower bound of the
2177 ** range is $P. Due to a quirk in the way whereKeyStats() works, even
2178 ** if $L is available, whereKeyStats() is called for both ($P) and
2179 ** ($P:$L) and the larger of the two returned values used.
2180 **
2181 ** Similarly, iUpper is to be set to the estimate of the number of rows
2182 ** less than the upper bound of the range query. Where the upper bound
2183 ** is either ($P) or ($P:$U). Again, even if $U is available, both values
2184 ** of iUpper are requested of whereKeyStats() and the smaller used.
2185 */
2186 tRowcnt iLower;
2187 tRowcnt iUpper;
2192 }
2197 }
2198 /* Determine iLower and iUpper using ($P) only. */
2203 /* Note: this call could be optimized away - since the same values must
2204 ** have been requested when testing key $P in whereEqualScanEst(). */
2208 }
2214 /* The roles of pLower and pUpper are swapped for a DESC index */
2216 }
2218 /* If possible, improve on the iLower estimate using ($P:$L). */
2224 tRowcnt iNew;
2228 nOut--;
2230 }
2231 }
2233 /* If possible, improve on the iUpper estimate using ($P:$U). */
2239 tRowcnt iNew;
2243 nOut--;
2245 }
2246 }
2254 }
2257 }
2260 }
2265 }
2266 }
2267 #else
2271 #endif
2276 /* TUNING: If there is both an upper and lower limit, assume the range is
2277 ** reduced by an additional 75%. This means that, by default, an open-ended
2278 ** range query (e.g. col > ?) is assumed to match 1/4 of the rows in the
2279 ** index. While a closed range (e.g. col BETWEEN ? AND ?) is estimated to
2280 ** match 1/64 of the index. */
2286 #if defined(WHERETRACE_ENABLED)
2290 }
2291 #endif
2294 }
2296 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
2297 /*
2298 ** Estimate the number of rows that will be returned based on
2299 ** an equality constraint x=VALUE and where that VALUE occurs in
2300 ** the histogram data. This only works when x is the left-most
2301 ** column of an index and sqlite_stat3 histogram data is available
2302 ** for that index. When pExpr==NULL that means the constraint is
2303 ** "x IS NULL" instead of "x=VALUE".
2304 **
2305 ** Write the estimated row count into *pnRow and return SQLITE_OK.
2306 ** If unable to make an estimate, leave *pnRow unchanged and return
2307 ** non-zero.
2308 **
2309 ** This routine can fail if it is unable to load a collating sequence
2310 ** required for string comparison, or if unable to allocate memory
2311 ** for a UTF conversion required for comparison. The error is stored
2312 ** in the pParse structure.
2313 */
2319 ){
2334 /* If values are not available for all fields of the index to the left
2335 ** of this one, no estimate can be made. Return SQLITE_NOTFOUND. */
2338 }
2340 /* This is an optimization only. The call to sqlite3Stat4ProbeSetValue()
2341 ** below would return the same value. */
2345 }
2359 }
2362 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
2363 /*
2364 ** Estimate the number of rows that will be returned based on
2365 ** an IN constraint where the right-hand side of the IN operator
2366 ** is a list of values. Example:
2367 **
2368 ** WHERE x IN (1,2,3,4)
2369 **
2370 ** Write the estimated row count into *pnRow and return SQLITE_OK.
2371 ** If unable to make an estimate, leave *pnRow unchanged and return
2372 ** non-zero.
2373 **
2374 ** This routine can fail if it is unable to load a collating sequence
2375 ** required for string comparison, or if unable to allocate memory
2376 ** for a UTF conversion required for comparison. The error is stored
2377 ** in the pParse structure.
2378 */
2384 ){
2399 }
2405 }
2408 }
2411 /*
2412 ** Disable a term in the WHERE clause. Except, do not disable the term
2413 ** if it controls a LEFT OUTER JOIN and it did not originate in the ON
2414 ** or USING clause of that join.
2415 **
2416 ** Consider the term t2.z='ok' in the following queries:
2417 **
2418 ** (1) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok'
2419 ** (2) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok'
2420 ** (3) SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok'
2421 **
2422 ** The t2.z='ok' is disabled in the in (2) because it originates
2423 ** in the ON clause. The term is disabled in (3) because it is not part
2424 ** of a LEFT OUTER JOIN. In (1), the term is not disabled.
2425 **
2426 ** Disabling a term causes that term to not be tested in the inner loop
2427 ** of the join. Disabling is an optimization. When terms are satisfied
2428 ** by indices, we disable them to prevent redundant tests in the inner
2429 ** loop. We would get the correct results if nothing were ever disabled,
2430 ** but joins might run a little slower. The trick is to disable as much
2431 ** as we can without disabling too much. If we disabled in (1), we'd get
2432 ** the wrong answer. See ticket #813.
2433 */
2439 ){
2445 }
2446 }
2447 }
2448 }
2450 /*
2451 ** Code an OP_Affinity opcode to apply the column affinity string zAff
2452 ** to the n registers starting at base.
2453 **
2454 ** As an optimization, SQLITE_AFF_NONE entries (which are no-ops) at the
2455 ** beginning and end of zAff are ignored. If all entries in zAff are
2456 ** SQLITE_AFF_NONE, then no code gets generated.
2457 **
2458 ** This routine makes its own copy of zAff so that the caller is free
2459 ** to modify zAff after this routine returns.
2460 */
2466 }
2469 /* Adjust base and n to skip over SQLITE_AFF_NONE entries at the beginning
2470 ** and end of the affinity string.
2471 */
2473 n--;
2474 base++;
2475 zAff++;
2476 }
2478 n--;
2479 }
2481 /* Code the OP_Affinity opcode if there is anything left to do. */
2486 }
2487 }
2490 /*
2491 ** Generate code for a single equality term of the WHERE clause. An equality
2492 ** term can be either X=expr or X IN (...). pTerm is the term to be
2493 ** coded.
2494 **
2495 ** The current value for the constraint is left in register iReg.
2496 **
2497 ** For a constraint of the form X=expr, the expression is evaluated and its
2498 ** result is left on the stack. For constraints of the form X IN (...)
2499 ** this routine sets up a loop that will iterate over all values of X.
2500 */
2508 ){
2519 #ifndef SQLITE_OMIT_SUBQUERY
2529 ){
2533 }
2540 }
2549 }
2562 }
2567 }
2568 #endif
2569 }
2572 }
2574 /*
2575 ** Generate code that will evaluate all == and IN constraints for an
2576 ** index scan.
2577 **
2578 ** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c).
2579 ** Suppose the WHERE clause is this: a==5 AND b IN (1,2,3) AND c>5 AND c<10
2580 ** The index has as many as three equality constraints, but in this
2581 ** example, the third "c" value is an inequality. So only two
2582 ** constraints are coded. This routine will generate code to evaluate
2583 ** a==5 and b IN (1,2,3). The current values for a and b will be stored
2584 ** in consecutive registers and the index of the first register is returned.
2585 **
2586 ** In the example above nEq==2. But this subroutine works for any value
2587 ** of nEq including 0. If nEq==0, this routine is nearly a no-op.
2588 ** The only thing it does is allocate the pLevel->iMem memory cell and
2589 ** compute the affinity string.
2590 **
2591 ** The nExtraReg parameter is 0 or 1. It is 0 if all WHERE clause constraints
2592 ** are == or IN and are covered by the nEq. nExtraReg is 1 if there is
2593 ** an inequality constraint (such as the "c>=5 AND c<10" in the example) that
2594 ** occurs after the nEq quality constraints.
2595 **
2596 ** This routine allocates a range of nEq+nExtraReg memory cells and returns
2597 ** the index of the first memory cell in that range. The code that
2598 ** calls this routine will use that memory range to store keys for
2599 ** start and termination conditions of the loop.
2600 ** key value of the loop. If one or more IN operators appear, then
2601 ** this routine allocates an additional nEq memory cells for internal
2602 ** use.
2603 **
2604 ** Before returning, *pzAff is set to point to a buffer containing a
2605 ** copy of the column affinity string of the index allocated using
2606 ** sqlite3DbMalloc(). Except, entries in the copy of the string associated
2607 ** with equality constraints that use NONE affinity are set to
2608 ** SQLITE_AFF_NONE. This is to deal with SQL such as the following:
2609 **
2610 ** CREATE TABLE t1(a TEXT PRIMARY KEY, b);
2611 ** SELECT ... FROM t1 AS t2, t1 WHERE t1.a = t2.b;
2612 **
2613 ** In the example above, the index on t1(a) has TEXT affinity. But since
2614 ** the right hand side of the equality constraint (t2.b) has NONE affinity,
2615 ** no conversion should be attempted before using a t2.b value as part of
2616 ** a key to search the index. Hence the first byte in the returned affinity
2617 ** string in this example would be set to SQLITE_AFF_NONE.
2618 */
2625 ){
2637 /* This module is only called on query plans that use an index. */
2645 /* Figure out how many memory cells we will need then allocate them.
2646 */
2654 }
2672 }
2673 }
2675 /* Evaluate the equality constraints
2676 */
2682 /* The following testcase is true for indices with redundant columns.
2683 ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */
2693 }
2694 }
2702 }
2706 }
2709 }
2710 }
2711 }
2712 }
2715 }
2717 #ifndef SQLITE_OMIT_EXPLAIN
2718 /*
2719 ** This routine is a helper for explainIndexRange() below
2720 **
2721 ** pStr holds the text of an expression that we are building up one term
2722 ** at a time. This routine adds a new term to the end of the expression.
2723 ** Terms are separated by AND so add the "AND" text for second and subsequent
2724 ** terms only.
2725 */
2731 ){
2736 }
2738 /*
2739 ** Argument pLevel describes a strategy for scanning table pTab. This
2740 ** function appends text to pStr that describes the subset of table
2741 ** rows scanned by the strategy in the form of an SQL expression.
2742 **
2743 ** For example, if the query:
2744 **
2745 ** SELECT * FROM t1 WHERE a=1 AND b>2;
2746 **
2747 ** is run and there is an index on (a, b), then this function returns a
2748 ** string similar to:
2749 **
2750 ** "a=? AND b>?"
2751 */
2769 }
2770 }
2776 }
2780 }
2782 }
2784 /*
2785 ** This function is a no-op unless currently processing an EXPLAIN QUERY PLAN
2786 ** command. If the query being compiled is an EXPLAIN QUERY PLAN, a single
2787 ** record is added to the output to describe the table scan strategy in
2788 ** pLevel.
2789 */
2796 u16 wctrlFlags /* Flags passed to sqlite3WhereBegin() */
2797 ){
2798 #ifndef SQLITE_DEBUG
2800 #endif
2801 {
2828 }
2832 }
2843 }
2850 }
2855 }
2867 }
2870 }
2871 #ifndef SQLITE_OMIT_VIRTUALTABLE
2875 }
2876 #endif
2877 #ifdef SQLITE_EXPLAIN_ESTIMATED_ROWS
2882 }
2883 #endif
2886 }
2887 }
2888 #else
2889 # define explainOneScan(u,v,w,x,y,z)
2893 /*
2894 ** Generate code for the start of the iLevel-th loop in the WHERE clause
2895 ** implementation described by pWInfo.
2896 */
2900 Bitmask notReady /* Which tables are currently available */
2901 ){
2934 /* Create labels for the "break" and "continue" instructions
2935 ** for the current loop. Jump to addrBrk to break out of a loop.
2936 ** Jump to cont to go immediately to the next iteration of the
2937 ** loop.
2938 **
2939 ** When there is an IN operator, we also have a "addrNxt" label that
2940 ** means to continue with the next IN value combination. When
2941 ** there are no IN operators in the constraints, the "addrNxt" label
2942 ** is the same as "addrBrk".
2943 */
2947 /* If this is the right table of a LEFT OUTER JOIN, allocate and
2948 ** initialize a memory cell that records if this table matches any
2949 ** row of the left table of the join.
2950 */
2955 }
2957 /* Special case of a FROM clause subquery implemented as a co-routine */
2967 #ifndef SQLITE_OMIT_VIRTUALTABLE
2969 /* Case 1: The table is a virtual-table. Use the VFilter and VNext
2970 ** to access the data.
2971 */
2988 }
2989 }
3000 }
3001 }
3012 ){
3013 /* Case 2: We can directly reference a single row using an
3014 ** equality comparison against the ROWID field. Or
3015 ** we reference multiple rows using a "rowid IN (...)"
3016 ** construct.
3017 */
3037 ){
3038 /* Case 3: We have an inequality comparison against the ROWID field.
3039 */
3055 }
3060 /* The following constant maps TK_xx codes into corresponding
3061 ** seek opcodes. It depends on a particular ordering of TK_xx
3062 */
3067 /* TK_GE */ OP_SeekGE
3068 };
3092 }
3106 }
3108 }
3124 }
3126 /* Case 4: A scan using an index.
3127 **
3128 ** The WHERE clause may contain zero or more equality
3129 ** terms ("==" or "IN" operators) that refer to the N
3130 ** left-most columns of the index. It may also contain
3131 ** inequality constraints (>, <, >= or <=) on the indexed
3132 ** column that immediately follows the N equalities. Only
3133 ** the right-most column can be an inequality - the rest must
3134 ** use the "==" and "IN" operators. For example, if the
3135 ** index is on (x,y,z), then the following clauses are all
3136 ** optimized:
3137 **
3138 ** x=5
3139 ** x=5 AND y=10
3140 ** x=5 AND y<10
3141 ** x=5 AND y>5 AND y<10
3142 ** x=5 AND y=5 AND z<=10
3143 **
3144 ** The z<10 term of the following cannot be used, only
3145 ** the x=5 term:
3146 **
3147 ** x=5 AND z<10
3148 **
3149 ** N may be zero if there are inequality constraints.
3150 ** If there are no inequality constraints, then N is at
3151 ** least one.
3152 **
3153 ** This case is also used when there are no WHERE clause
3154 ** constraints but an index is selected anyway, in order
3155 ** to force the output order to conform to an ORDER BY.
3156 */
3165 OP_SeekLE /* 7: (start_constraints && startEq && bRev) */
3166 };
3172 };
3194 /* If this loop satisfies a sort order (pOrderBy) request that
3195 ** was passed to this function to implement a "SELECT min(x) ..."
3196 ** query, then the caller will only allow the loop to run for
3197 ** a single iteration. This means that the first row returned
3198 ** should not have a NULL value stored in 'x'. If column 'x' is
3199 ** the first one after the nEq equality constraints in the index,
3200 ** this requires some special handling.
3201 */
3208 ){
3212 }
3214 /* Find any inequality constraint terms for the start and end
3215 ** of the range.
3216 */
3221 }
3228 ){
3230 }
3231 }
3234 /* Generate code to evaluate all constraint terms using == or IN
3235 ** and store the values of those terms in an array of registers
3236 ** starting at regBase.
3237 */
3243 /* If we are doing a reverse order scan on an ascending index, or
3244 ** a forward order scan on a descending index, interchange the
3245 ** start and end terms (pRangeStart and pRangeEnd).
3246 */
3249 ){
3252 }
3262 /* Seek the index cursor to the start of the range. */
3269 ){
3272 }
3275 /* Since the comparison is to be performed with no conversions
3276 ** applied to the operands, set the affinity to apply to pRight to
3277 ** SQLITE_AFF_NONE. */
3279 }
3282 }
3283 }
3284 nConstraint++;
3288 nConstraint++;
3291 }
3304 /* Load the value for the inequality constraint at the end of the
3305 ** range (if any).
3306 */
3314 ){
3317 }
3320 ){
3322 }
3323 nConstraint++;
3328 nConstraint++;
3329 }
3332 /* Top of the loop body */
3335 /* Check if the index cursor is past the end of the range. */
3343 }
3345 /* Seek the table cursor, if required */
3349 /* pIdx is a covering index. No need to access the main table. */
3361 }
3364 }
3366 /* Record the instruction used to terminate the loop. Disable
3367 ** WHERE clause terms made redundant by the index range scan.
3368 */
3375 }
3382 }
3385 #ifndef SQLITE_OMIT_OR_OPTIMIZATION
3387 /* Case 5: Two or more separately indexed terms connected by OR
3388 **
3389 ** Example:
3390 **
3391 ** CREATE TABLE t1(a,b,c,d);
3392 ** CREATE INDEX i1 ON t1(a);
3393 ** CREATE INDEX i2 ON t1(b);
3394 ** CREATE INDEX i3 ON t1(c);
3395 **
3396 ** SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
3397 **
3398 ** In the example, there are three indexed terms connected by OR.
3399 ** The top of the loop looks like this:
3400 **
3401 ** Null 1 # Zero the rowset in reg 1
3402 **
3403 ** Then, for each indexed term, the following. The arguments to
3404 ** RowSetTest are such that the rowid of the current row is inserted
3405 ** into the RowSet. If it is already present, control skips the
3406 ** Gosub opcode and jumps straight to the code generated by WhereEnd().
3407 **
3408 ** sqlite3WhereBegin(<term>)
3409 ** RowSetTest # Insert rowid into rowset
3410 ** Gosub 2 A
3411 ** sqlite3WhereEnd()
3412 **
3413 ** Following the above, code to terminate the loop. Label A, the target
3414 ** of the Gosub above, jumps to the instruction right after the Goto.
3415 **
3416 ** Null 1 # Zero the rowset in reg 1
3417 ** Goto B # The loop is finished.
3418 **
3419 ** A: <loop body> # Return data, whatever.
3420 **
3421 ** Return 2 # Jump back to the Gosub
3422 **
3423 ** B: <after the loop>
3424 **
3425 ** Added 2014-05-26: If the table is a WITHOUT ROWID table, then
3426 ** use an ephemeral index instead of a RowSet to record the primary
3427 ** keys of the rows we have already seen.
3428 **
3429 */
3454 /* Set up a new SrcList in pOrTab containing the table being scanned
3455 ** by this loop in the a[0] slot and all notReady tables in a[1..] slots.
3456 ** This becomes the SrcList in the recursive call to sqlite3WhereBegin().
3457 */
3471 }
3474 }
3476 /* Initialize the rowset register to contain NULL. An SQL NULL is
3477 ** equivalent to an empty rowset. Or, create an ephemeral index
3478 ** capable of holding primary keys in the case of a WITHOUT ROWID.
3479 **
3480 ** Also initialize regReturn to contain the address of the instruction
3481 ** immediately following the OP_Return at the bottom of the loop. This
3482 ** is required in a few obscure LEFT JOIN cases where control jumps
3483 ** over the top of the loop into the body of it. In this case the
3484 ** correct response for the end-of-loop code (the OP_Return) is to
3485 ** fall through to the next instruction, just as an OP_Next does if
3486 ** called on an uninitialized cursor.
3487 */
3497 }
3499 }
3502 /* If the original WHERE clause is z of the form: (x1 OR x2 OR ...) AND y
3503 ** Then for every term xN, evaluate as the subexpression: xN AND z
3504 ** That way, terms in y that are factored into the disjunction will
3505 ** be picked up by the recursive calls to sqlite3WhereBegin() below.
3506 **
3507 ** Actually, each subexpression is converted to "xN AND w" where w is
3508 ** the "interesting" terms of z - terms that did not originate in the
3509 ** ON or USING clause of a LEFT JOIN, and terms that are usable as
3510 ** indices.
3511 **
3512 ** This optimization also only applies if the (x1 OR x2 OR ...) term
3513 ** is not contained in the ON clause of a LEFT JOIN.
3514 ** See ticket http://www.sqlite.org/src/info/f2369304e4
3515 */
3528 }
3531 }
3532 }
3534 /* Run a separate WHERE clause for each term of the OR clause. After
3535 ** eliminating duplicates from other WHERE clauses, the action for each
3536 ** sub-WHERE clause is to to invoke the main loop body as a subroutine.
3537 */
3538 wctrlFlags = WHERE_OMIT_OPEN_CLOSE
3539 | WHERE_FORCE_TABLE
3550 }
3551 /* Loop through table entries that match term pOrTerm. */
3560 );
3561 /* This is the sub-WHERE clause body. First skip over
3562 ** duplicate rows from prior sub-WHERE clauses, and record the
3563 ** rowid (or PRIMARY KEY) for the current row so that the same
3564 ** row will be skipped in subsequent sub-WHERE clauses.
3565 */
3578 /* Read the PK into an array of temp registers. */
3583 }
3585 /* Check if the temp table already contains this key. If so,
3586 ** the row has already been included in the result set and
3587 ** can be ignored (by jumping past the Gosub below). Otherwise,
3588 ** insert the key into the temp table and proceed with processing
3589 ** the row.
3590 **
3591 ** Use some of the same optimizations as OP_RowSetTest: If iSet
3592 ** is zero, assume that the key cannot already be present in
3593 ** the temp table. And if iSet is -1, assume that there is no
3594 ** need to insert the key into the temp table, as it will never
3595 ** be tested for. */
3599 }
3604 }
3606 /* Release the array of temp registers */
3608 }
3609 }
3611 /* Invoke the main loop body as a subroutine */
3614 /* Jump here (skipping the main loop body subroutine) if the
3615 ** current sub-WHERE row is a duplicate from prior sub-WHEREs. */
3618 /* The pSubWInfo->untestedTerms flag means that this OR term
3619 ** contained one or more AND term from a notReady table. The
3620 ** terms from the notReady table could not be tested and will
3621 ** need to be tested later.
3622 */
3625 /* If all of the OR-connected terms are optimized using the same
3626 ** index, and the index is opened using the same cursor number
3627 ** by each call to sqlite3WhereBegin() made by this loop, it may
3628 ** be possible to use that index as a covering index.
3629 **
3630 ** If the call to sqlite3WhereBegin() above resulted in a scan that
3631 ** uses an index, and this is either the first OR-connected term
3632 ** processed or the index is the same as that used by all previous
3633 ** terms, set pCov to the candidate covering index. Otherwise, set
3634 ** pCov to NULL to indicate that no candidate covering index will
3635 ** be available.
3636 */
3642 ){
3648 }
3650 /* Finish the loop through table entries that match term pOrTerm. */
3652 }
3653 }
3654 }
3660 }
3670 {
3671 /* Case 6: There is no usable index. We must do a complete
3672 ** scan of the entire table.
3673 */
3678 /* Tables marked isRecursive have only a single row that is stored in
3679 ** a pseudo-cursor. No need to Rewind or Next such cursors. */
3688 }
3689 }
3691 /* Insert code to test every subexpression that can be completely
3692 ** computed using the current set of tables.
3693 */
3704 }
3709 }
3712 }
3714 /* Insert code to test for implied constraints based on transitivity
3715 ** of the "==" operator.
3716 **
3717 ** Example: If the WHERE clause contains "t1.a=t2.b" and "t2.b=123"
3718 ** and we are coding the t1 loop and the t2 loop has not yet coded,
3719 ** then we cannot use the "t1.a=t2.b" constraint, but we can code
3720 ** the implied "t1.a=123" constraint.
3721 */
3744 }
3745 }
3747 /* For a LEFT OUTER JOIN, generate code that will record the fact that
3748 ** at least one row of the right table has matched the left table.
3749 */
3762 }
3766 }
3767 }
3770 }
3772 #ifdef WHERETRACE_ENABLED
3773 /*
3774 ** Print the content of a WhereTerm object
3775 */
3789 }
3790 }
3791 #endif
3793 #ifdef WHERETRACE_ENABLED
3794 /*
3795 ** Print a WhereLoop object for debugging purposes
3796 */
3813 }
3817 }
3825 }
3828 }
3833 }
3839 }
3840 }
3841 }
3842 #endif
3844 /*
3845 ** Convert bulk memory into a valid WhereLoop that can be passed
3846 ** to whereLoopClear harmlessly.
3847 */
3853 }
3855 /*
3856 ** Clear the WhereLoop.u union. Leave WhereLoop.pLTerm intact.
3857 */
3869 }
3870 }
3871 }
3873 /*
3874 ** Deallocate internal memory used by a WhereLoop object
3875 */
3880 }
3882 /*
3883 ** Increase the memory allocation for pLoop->aLTerm[] to be at least n.
3884 */
3896 }
3898 /*
3899 ** Transfer content from the second pLoop into the first.
3900 */
3906 }
3913 }
3915 }
3917 /*
3918 ** Delete a WhereLoop object
3919 */
3923 }
3925 /*
3926 ** Free a WhereInfo structure
3927 */
3935 }
3937 }
3938 }
3940 /*
3941 ** Return TRUE if both of the following are true:
3942 **
3943 ** (1) X has the same or lower cost that Y
3944 ** (2) X is a proper subset of Y
3945 **
3946 ** By "proper subset" we mean that X uses fewer WHERE clause terms
3947 ** than Y and that every WHERE clause term used by X is also used
3948 ** by Y.
3949 **
3950 ** If X is a proper subset of Y then Y is a better choice and ought
3951 ** to have a lower cost. This routine returns TRUE when that cost
3952 ** relationship is inverted and needs to be adjusted.
3953 */
3957 ){
3963 }
3967 }
3969 }
3971 }
3973 /*
3974 ** Try to adjust the cost of WhereLoop pTemplate upwards or downwards so
3975 ** that:
3976 **
3977 ** (1) pTemplate costs less than any other WhereLoops that are a proper
3978 ** subset of pTemplate
3979 **
3980 ** (2) pTemplate costs more than any other WhereLoops for which pTemplate
3981 ** is a proper subset.
3982 **
3983 ** To say "WhereLoop X is a proper subset of Y" means that X uses fewer
3984 ** WHERE clause terms than Y and that every WHERE clause term used by X is
3985 ** also used by Y.
3986 **
3987 ** This adjustment is omitted for SKIPSCAN loops. In a SKIPSCAN loop, the
3988 ** WhereLoop.nLTerm field is not an accurate measure of the number of WHERE
3989 ** clause terms covered, since some of the first nLTerm entries in aLTerm[]
3990 ** will be NULL (because they are skipped). That makes it more difficult
3991 ** to compare the loops. We could add extra code to do the comparison, and
3992 ** perhaps we will someday. But SKIPSCAN is sufficiently uncommon, and this
3993 ** adjustment is sufficient minor, that it is very difficult to construct
3994 ** a test case where the extra code would improve the query plan. Better
3995 ** to avoid the added complexity and just omit cost adjustments to SKIPSCAN
3996 ** loops.
3997 */
4006 /* Adjust pTemplate cost downward so that it is cheaper than its
4007 ** subset p */
4011 /* Adjust pTemplate cost upward so that it is costlier than p since
4012 ** pTemplate is a proper subset of p */
4015 }
4016 }
4017 }
4019 /*
4020 ** Search the list of WhereLoops in *ppPrev looking for one that can be
4021 ** supplanted by pTemplate.
4022 **
4023 ** Return NULL if the WhereLoop list contains an entry that can supplant
4024 ** pTemplate, in other words if pTemplate does not belong on the list.
4025 **
4026 ** If pX is a WhereLoop that pTemplate can supplant, then return the
4027 ** link that points to pX.
4028 **
4029 ** If pTemplate cannot supplant any existing element of the list but needs
4030 ** to be added to the list, then return a pointer to the tail of the list.
4031 */
4035 ){
4039 /* If either the iTab or iSortIdx values for two WhereLoop are different
4040 ** then those WhereLoops need to be considered separately. Neither is
4041 ** a candidate to replace the other. */
4043 }
4044 /* In the current implementation, the rSetup value is either zero
4045 ** or the cost of building an automatic index (NlogN) and the NlogN
4046 ** is the same for compatible WhereLoops. */
4050 /* whereLoopAddBtree() always generates and inserts the automatic index
4051 ** case first. Hence compatible candidate WhereLoops never have a larger
4052 ** rSetup. Call this SETUP-INVARIANT */
4055 /* Any loop using an appliation-defined index (or PRIMARY KEY or
4056 ** UNIQUE constraint) with one or more == constraints is better
4057 ** than an automatic index. */
4062 ){
4064 }
4066 /* If existing WhereLoop p is better than pTemplate, pTemplate can be
4067 ** discarded. WhereLoop p is better if:
4068 ** (1) p has no more dependencies than pTemplate, and
4069 ** (2) p has an equal or lower cost than pTemplate
4070 */
4075 ){
4077 }
4079 /* If pTemplate is always better than p, then cause p to be overwritten
4080 ** with pTemplate. pTemplate is better than p if:
4081 ** (1) pTemplate has no more dependences than p, and
4082 ** (2) pTemplate has an equal or lower cost than p.
4083 */
4087 ){
4090 }
4091 }
4093 }
4095 /*
4096 ** Insert or replace a WhereLoop entry using the template supplied.
4097 **
4098 ** An existing WhereLoop entry might be overwritten if the new template
4099 ** is better and has fewer dependencies. Or the template will be ignored
4100 ** and no insert will occur if an existing WhereLoop is faster and has
4101 ** fewer dependencies than the template. Otherwise a new WhereLoop is
4102 ** added based on the template.
4103 **
4104 ** If pBuilder->pOrSet is not NULL then we care about only the
4105 ** prerequisites and rRun and nOut costs of the N best loops. That
4106 ** information is gathered in the pBuilder->pOrSet object. This special
4107 ** processing mode is used only for OR clause processing.
4108 **
4109 ** When accumulating multiple loops (when pBuilder->pOrSet is NULL) we
4110 ** still might overwrite similar loops with the new template if the
4111 ** new template is better. Loops may be overwritten if the following
4112 ** conditions are met:
4113 **
4114 ** (1) They have the same iTab.
4115 ** (2) They have the same iSortIdx.
4116 ** (3) The template has same or fewer dependencies than the current loop
4117 ** (4) The template has the same or lower cost than the current loop
4118 */
4124 /* If pBuilder->pOrSet is defined, then only keep track of the costs
4125 ** and prereqs.
4126 */
4128 #if WHERETRACE_ENABLED
4131 #endif
4138 }
4139 #endif
4141 }
4143 /* Look for an existing WhereLoop to replace with pTemplate
4144 */
4149 /* There already exists a WhereLoop on the list that is better
4150 ** than pTemplate, so just ignore pTemplate */
4155 }
4156 #endif
4160 }
4162 /* If we reach this point it means that either p[] should be overwritten
4163 ** with pTemplate[] if p[] exists, or if p==NULL then allocate a new
4164 ** WhereLoop and insert it.
4165 */
4171 }
4174 }
4175 #endif
4177 /* Allocate a new WhereLoop to add to the end of the list */
4183 /* We will be overwriting WhereLoop p[]. But before we do, first
4184 ** go through the rest of the list and delete any other entries besides
4185 ** p[] that are also supplated by pTemplate */
4198 }
4199 #endif
4201 }
4202 }
4208 }
4209 }
4211 }
4213 /*
4214 ** Adjust the WhereLoop.nOut value downward to account for terms of the
4215 ** WHERE clause that reference the loop but which are not used by an
4216 ** index.
4217 **
4218 ** In the current implementation, the first extra WHERE clause term reduces
4219 ** the number of output rows by a factor of 10 and each additional term
4220 ** reduces the number of output rows by sqrt(2).
4221 */
4225 LogEst nRow /* Number of rows in the entire table */
4226 ){
4241 }
4248 }
4249 }
4250 }
4251 /* TUNING: If there is at least one equality constraint in the WHERE
4252 ** clause that does not have a likelihood() explicitly assigned to it
4253 ** then do not let the estimated number of output rows exceed half
4254 ** the number of rows in the table. */
4257 }
4258 }
4260 /*
4261 ** Adjust the cost C by the costMult facter T. This only occurs if
4262 ** compiled with -DSQLITE_ENABLE_COSTMULT
4263 */
4264 #ifdef SQLITE_ENABLE_COSTMULT
4265 # define ApplyCostMultiplier(C,T) C += T
4266 #else
4267 # define ApplyCostMultiplier(C,T)
4268 #endif
4270 /*
4271 ** We have so far matched pBuilder->pNew->u.btree.nEq terms of the
4272 ** index pIndex. Try to match one more.
4273 **
4274 ** When this function is called, pBuilder->pNew->nOut contains the
4275 ** number of rows expected to be visited by filtering using the nEq
4276 ** terms only. If it is modified, this value is restored before this
4277 ** function returns.
4278 **
4279 ** If pProbe->tnum==0, that means pIndex is a fake index used for the
4280 ** INTEGER PRIMARY KEY.
4281 */
4286 LogEst nInMul /* log(Number of iterations due to IN) */
4287 ){
4318 }
4336 /* Consider using a skip-scan if there are no WHERE clause constraints
4337 ** available for the left-most terms of the index, and if the average
4338 ** number of repeats in the left-most terms is at least 18.
4339 **
4340 ** The magic number 18 is selected on the basis that scanning 17 rows
4341 ** is almost always quicker than an index seek (even though if the index
4342 ** contains fewer than 2^17 rows we assume otherwise in other parts of
4343 ** the code). And, even if it is not, it should not be too much slower.
4344 ** On the other hand, the extra seeks could end up being significantly
4345 ** more expensive. */
4351 ){
4352 LogEst nIter;
4359 /* TUNING: When estimating skip-scan for a term that is also indexable,
4360 ** multiply the cost of the skip-scan by 2.0, to make it a little less
4361 ** desirable than the regular index lookup. */
4363 }
4365 /* TUNING: Because uncertainties in the estimates for skip-scan queries,
4366 ** add a 1.375 fudge factor to make skip-scan slightly less likely. */
4372 }
4375 LogEst rCostIdx;
4378 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
4380 #endif
4383 ){
4385 }
4399 );
4405 /* "x IN (SELECT ...)": TUNING: the SELECT returns 25 rows */
4408 /* "x IN (value, value, ...)" */
4410 }
4412 ** changes "x IN (?)" into "x=?". */
4421 }
4422 }
4439 }
4441 /* At this point pNew->nOut is set to the number of rows expected to
4442 ** be visited by the index scan before considering term pTerm, or the
4443 ** values of nIn and nInMul. In other words, assuming that all
4444 ** "x IN(...)" terms are replaced with "x = ?". This block updates
4445 ** the value of pNew->nOut to account for pTerm (but not nIn/nInMul). */
4448 /* Adjust nOut using stat3/stat4 data. Or, if there is no stat3/stat4
4449 ** data, using some other estimate. */
4462 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
4469 ){
4477 }
4484 }
4485 }
4487 #endif
4488 {
4491 /* TUNING: If there is no likelihood() value, assume that a
4492 ** "col IS NULL" expression matches twice as many rows
4493 ** as (col=?). */
4495 }
4496 }
4497 }
4498 }
4500 /* Set rCostIdx to the cost of visiting selected rows in index. Add
4501 ** it to pNew->rRun, which is currently set to the cost of the index
4502 ** seek only. Then, if this is a non-covering index, add the cost of
4503 ** visiting the rows in the main table. */
4508 }
4521 }
4525 ){
4527 }
4529 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
4531 #endif
4532 }
4540 }
4542 /*
4543 ** Return True if it is possible that pIndex might be useful in
4544 ** implementing the ORDER BY clause in pBuilder.
4545 **
4546 ** Return False if pBuilder does not contain an ORDER BY clause or
4547 ** if there is no way for pIndex to be useful in implementing that
4548 ** ORDER BY clause.
4549 */
4553 int iCursor
4554 ){
4567 }
4568 }
4569 }
4571 }
4573 /*
4574 ** Return a bitmask where 1s indicate that the corresponding column of
4575 ** the table is used by an index. Only the first 63 columns are considered.
4576 */
4586 }
4587 }
4589 }
4591 /* Check to see if a partial index with pPartIndexWhere can be used
4592 ** in the current query. Return true if it can be and false if not.
4593 */
4599 }
4601 }
4603 /*
4604 ** Add all WhereLoop objects for a single table of the join where the table
4605 ** is idenfied by pBuilder->pNew->iTab. That table is guaranteed to be
4606 ** a b-tree table, not a virtual table.
4607 **
4608 ** The costs (WhereLoop.rRun) of the b-tree loops added by this function
4609 ** are calculated as follows:
4610 **
4611 ** For a full scan, assuming the table (or index) contains nRow rows:
4612 **
4613 ** cost = nRow * 3.0 // full-table scan
4614 ** cost = nRow * K // scan of covering index
4615 ** cost = nRow * (K+3.0) // scan of non-covering index
4616 **
4617 ** where K is a value between 1.1 and 3.0 set based on the relative
4618 ** estimated average size of the index and table records.
4619 **
4620 ** For an index scan, where nVisit is the number of index rows visited
4621 ** by the scan, and nSeek is the number of seek operations required on
4622 ** the index b-tree:
4623 **
4624 ** cost = nSeek * (log(nRow) + K * nVisit) // covering index
4625 ** cost = nSeek * (log(nRow) + (K+3.0) * nVisit) // non-covering index
4626 **
4627 ** Normally, nSeek is 1. nSeek values greater than 1 come about if the
4628 ** WHERE clause includes "x IN (....)" terms used in place of "x=?". Or when
4629 ** implicit "x IN (SELECT x FROM tbl)" terms are added for skip-scans.
4630 **
4631 ** The estimated values (nRow, nVisit, nSeek) often contain a large amount
4632 ** of uncertainty. For this reason, scoring is designed to pick plans that
4633 ** "do the least harm" if the estimates are inaccurate. For example, a
4634 ** log(nRow) factor is omitted from a non-covering index scan in order to
4635 ** bias the scoring in favor of using an index, since the worst-case
4636 ** performance of using an index is far better than the worst-case performance
4637 ** of a full table scan.
4638 */
4641 Bitmask mExtra /* Extra prerequesites for using this table */
4642 ){
4668 /* An INDEXED BY clause specifies a particular index to use */
4673 /* There is no INDEXED BY clause. Create a fake Index object in local
4674 ** variable sPk to represent the rowid primary key index. Make this
4675 ** fake index the first in a chain of Index objects with all of the real
4676 ** indices to follow */
4690 /* The real indices of the table are only considered if the
4691 ** NOT INDEXED qualifier is omitted from the FROM clause */
4693 }
4695 }
4699 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
4700 /* Automatic indexes */
4709 ){
4710 /* Generate auto-index WhereLoops */
4721 /* TUNING: One-time cost for computing the automatic index is
4722 ** estimated to be X*N*log2(N) where N is the number of rows in
4723 ** the table being indexed and where X is 7 (LogEst=28) for normal
4724 ** tables or 1.375 (LogEst=4) for views and subqueries. The value
4725 ** of X is smaller for views and subqueries so that the query planner
4726 ** will be more aggressive about generating automatic indexes for
4727 ** those objects, since there is no opportunity to add schema
4728 ** indexes on subqueries and views. */
4732 }
4734 /* TUNING: Each index lookup yields 20 rows in the table. This
4735 ** is more than the usual guess of 10 rows, since we have no way
4736 ** of knowing how selective the index will ultimately be. It would
4737 ** not be unreasonable to make this value much larger. */
4743 }
4744 }
4745 }
4748 /* Loop over all indices
4749 */
4755 }
4766 /* The ONEPASS_DESIRED flags never occurs together with ORDER BY */
4769 /* Integer primary key index */
4772 /* Full table scan */
4774 /* TUNING: Cost of full table scan is (N*3.0). */
4782 Bitmask m;
4789 }
4791 /* Full scan via index */
4800 )
4801 ){
4804 /* The cost of visiting the index rows is N*K, where K is
4805 ** between 1.1 and 3.0, depending on the relative sizes of the
4806 ** index and table rows. If this is a non-covering index scan,
4807 ** also add the cost of visiting table rows (N*3.0). */
4811 }
4817 }
4818 }
4821 #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
4825 #endif
4827 /* If there was an INDEXED BY clause, then only that one index is
4828 ** considered. */
4830 }
4832 }
4834 #ifndef SQLITE_OMIT_VIRTUALTABLE
4835 /*
4836 ** Add all WhereLoop objects for a table of the join identified by
4837 ** pBuilder->pNew->iTab. That table is guaranteed to be a virtual table.
4838 */
4841 Bitmask mExtra
4842 ){
4882 }
4886 iPhase++;
4888 }
4899 }
4904 }
4918 }
4919 }
4943 ){
4947 }
4961 /* Do not attempt to use an IN constraint if the virtual table
4962 ** says that the equivalent EQ constraint cannot be safely omitted.
4963 ** If we do attempt to use such a constraint, some rows might be
4964 ** repeated in the output. */
4966 }
4967 /* A virtual table that is constrained by an IN clause may not
4968 ** consume the ORDER BY clause because (1) the order of IN terms
4969 ** is not necessarily related to the order of output terms and
4970 ** (2) Multiple outputs from a single IN value will not merge
4971 ** together. */
4973 }
4974 }
4975 }
4992 }
4993 }
4994 }
4996 whereLoopAddVtab_exit:
5000 }
5003 /*
5004 ** Add WhereLoop entries to handle OR terms. This works for either
5005 ** btrees or virtual tables.
5006 */
5014 WhereClause tempWC;
5015 WhereLoopBuilder sSubBuild;
5029 ){
5053 }
5055 #ifdef WHERETRACE_ENABLED
5061 }
5062 }
5063 #endif
5064 #ifndef SQLITE_OMIT_VIRTUALTABLE
5068 #endif
5069 {
5071 }
5074 }
5083 WhereOrSet sPrev;
5091 }
5092 }
5093 }
5094 }
5102 /* TUNING: Currently sSum.a[i].rRun is set to the sum of the costs
5103 ** of all sub-scans required by the OR-scan. However, due to rounding
5104 ** errors, it may be that the cost of the OR-scan is equal to its
5105 ** most expensive sub-scan. Add the smallest possible penalty
5106 ** (equivalent to multiplying the cost by 1.07) to ensure that
5107 ** this does not happen. Otherwise, for WHERE clauses such as the
5108 ** following where there is an index on "y":
5109 **
5110 ** WHERE likelihood(x=?, 0.99) OR y=?
5111 **
5112 ** the planner may elect to "OR" together a full-table scan and an
5113 ** index lookup. And other similarly odd results. */
5118 }
5120 }
5121 }
5123 }
5125 /*
5126 ** Add all WhereLoop objects for all tables
5127 */
5141 /* Loop over the tables in the join, from left to right */
5149 }
5155 }
5158 }
5161 }
5164 }
5166 /*
5167 ** Examine a WherePath (with the addition of the extra WhereLoop of the 5th
5168 ** parameters) to see if it outputs rows in the requested ORDER BY
5169 ** (or GROUP BY) without requiring a separate sort operation. Return N:
5170 **
5171 ** N>0: N terms of the ORDER BY clause are satisfied
5172 ** N==0: No terms of the ORDER BY clause are satisfied
5173 ** N<0: Unknown yet how many terms of ORDER BY might be satisfied.
5174 **
5175 ** Note that processing for WHERE_GROUPBY and WHERE_DISTINCTBY is not as
5176 ** strict. With GROUP BY and DISTINCT the only requirement is that
5177 ** equivalent rows appear immediately adjacent to one another. GROUP BY
5178 ** and DISTINCT do not require rows to appear in any particular order as long
5179 ** as equivalent rows are grouped together. Thus for GROUP BY and DISTINCT
5180 ** the pOrderBy terms can be matched in any order. With ORDER BY, the
5181 ** pOrderBy terms must be matched in strict left-to-right order.
5182 */
5191 ){
5216 /*
5217 ** We say the WhereLoop is "one-row" if it generates no more than one
5218 ** row of output. A WhereLoop is one-row if all of the following are true:
5219 ** (a) All index columns match with WHERE_COLUMN_EQ.
5220 ** (b) The index is unique
5221 ** Any WhereLoop with an WHERE_COLUMN_EQ constraint on the rowid is one-row.
5222 ** Every one-row WhereLoop will have the WHERE_ONEROW bit set in wsFlags.
5223 **
5224 ** We say the WhereLoop is "order-distinct" if the set of columns from
5225 ** that WhereLoop that are in the ORDER BY clause are different for every
5226 ** row of the WhereLoop. Every one-row WhereLoop is automatically
5227 ** order-distinct. A WhereLoop that has no columns in the ORDER BY clause
5228 ** is not order-distinct. To be order-distinct is not quite the same as being
5229 ** UNIQUE since a UNIQUE column or index can have multiple rows that
5230 ** are NULL and NULL values are equivalent for the purpose of order-distinct.
5231 ** To be order-distinct, the columns must be UNIQUE and NOT NULL.
5232 **
5233 ** The rowid for a table is always UNIQUE and NOT NULL so whenever the
5234 ** rowid appears in the ORDER BY clause, the corresponding WhereLoop is
5235 ** automatically order-distinct.
5236 */
5254 }
5257 /* Mark off any ORDER BY term X that is a column in the table of
5258 ** the current loop for which there is term in the WHERE
5259 ** clause of the form X IS NULL or X=? that reference only outer
5260 ** loops.
5261 */
5279 }
5281 }
5296 }
5298 /* Loop through all columns of the index and deal with the ones
5299 ** that are not constrained by == or IN.
5300 */
5306 /* Skip over == and IS NULL terms */
5310 ){
5314 }
5316 }
5318 /* Get the column number in the table (iColumn) and sort order
5319 ** (revIdx) for the j-th column of the index.
5320 */
5328 }
5330 /* An unconstrained column that might be NULL means that this
5331 ** WhereLoop is not well-ordered
5332 */
5337 ){
5339 }
5341 /* Find the ORDER BY term that corresponds to the j-th column
5342 ** of the index and mark that ORDER BY term off
5343 */
5359 }
5362 }
5364 /* Make sure the sort order is compatible in an ORDER BY clause.
5365 ** Sort order is irrelevant for a GROUP BY clause. */
5372 }
5373 }
5378 }
5381 /* No match found */
5385 }
5387 }
5392 }
5395 /* Mark off any other ORDER BY terms that reference pLoop */
5400 Bitmask mTerm;
5407 }
5408 }
5409 }
5416 }
5418 }
5420 }
5423 /*
5424 ** If the WHERE_GROUPBY flag is set in the mask passed to sqlite3WhereBegin(),
5425 ** the planner assumes that the specified pOrderBy list is actually a GROUP
5426 ** BY clause - and so any order that groups rows as required satisfies the
5427 ** request.
5428 **
5429 ** Normally, in this case it is not possible for the caller to determine
5430 ** whether or not the rows are really being delivered in sorted order, or
5431 ** just in some other order that provides the required grouping. However,
5432 ** if the WHERE_SORTBYGROUP flag is also passed to sqlite3WhereBegin(), then
5433 ** this function may be called on the returned WhereInfo object. It returns
5434 ** true if the rows really will be sorted in the specified order, or false
5435 ** otherwise.
5436 **
5437 ** For example, assuming:
5438 **
5439 ** CREATE INDEX i1 ON t1(x, Y);
5440 **
5441 ** then
5442 **
5443 ** SELECT * FROM t1 GROUP BY x,y ORDER BY x,y; -- IsSorted()==1
5444 ** SELECT * FROM t1 GROUP BY y,x ORDER BY y,x; -- IsSorted()==0
5445 */
5450 }
5452 #ifdef WHERETRACE_ENABLED
5453 /* For debugging use only: */
5461 }
5462 #endif
5464 /*
5465 ** Return the cost of sorting nRow rows, assuming that the keys have
5466 ** nOrderby columns and that the first nSorted columns are already in
5467 ** order.
5468 */
5471 LogEst nRow,
5473 int nSorted
5474 ){
5475 /* TUNING: Estimated cost of a full external sort, where N is
5476 ** the number of rows to sort is:
5477 **
5478 ** cost = (3.0 * N * log(N)).
5479 **
5480 ** Or, if the order-by clause has X terms but only the last Y
5481 ** terms are out of order, then block-sorting will reduce the
5482 ** sorting cost to:
5483 **
5484 ** cost = (3.0 * N * log(N)) * (Y/X)
5485 **
5486 ** The (Y/X) term is implemented using stack variable rScale
5487 ** below. */
5493 /* TUNING: The cost of implementing DISTINCT using a B-TREE is
5494 ** similar but with a larger constant of proportionality.
5495 ** Multiply by an additional factor of 3.0. */
5498 }
5501 }
5503 /*
5504 ** Given the list of WhereLoop objects at pWInfo->pLoops, this routine
5505 ** attempts to find the lowest cost path that visits each WhereLoop
5506 ** once. This path is then loaded into the pWInfo->a[].pWLoop fields.
5507 **
5508 ** Assume that the total number of output rows that will need to be sorted
5509 ** will be nRowEst (in the 10*log2 representation). Or, ignore sorting
5510 ** costs if nRowEst==0.
5511 **
5512 ** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation
5513 ** error occurs.
5514 */
5540 /* TUNING: For simple queries, only the best path is tracked.
5541 ** For 2-way joins, the 5 best paths are followed.
5542 ** For joins of 3 or more tables, track the 10 best paths */
5547 /* If nRowEst is zero and there is an ORDER BY clause, ignore it. In this
5548 ** case the purpose of this call is to estimate the number of rows returned
5549 ** by the overall query. Once this estimate has been obtained, the caller
5550 ** will invoke this function a second time, passing the estimate as the
5551 ** nRowEst parameter. */
5556 }
5558 /* Allocate and initialize space for aTo, aFrom and aSortCost[] */
5569 }
5571 /* If there is an ORDER BY clause and it is not being ignored, set up
5572 ** space for the aSortCost[] array. Each element of the aSortCost array
5573 ** is either zero - meaning it has not yet been initialized - or the
5574 ** cost of sorting nRowEst rows of data where the first X terms of
5575 ** the ORDER BY clause are already in order, where X is the array
5576 ** index. */
5579 }
5583 /* Seed the search with a single WherePath containing zero WhereLoops.
5584 **
5585 ** TUNING: Do not let the number of iterations go above 25. If the cost
5586 ** of computing an automatic index is not paid back within the first 25
5587 ** rows, then do not use the automatic index. */
5592 /* If nLoop is zero, then there are no FROM terms in the query. Since
5593 ** in this case the query may return a maximum of one row, the results
5594 ** are already in the requested order. Set isOrdered to nOrderBy to
5595 ** indicate this. Or, if nLoop is greater than zero, set isOrdered to
5596 ** -1, indicating that the result set may or may not be ordered,
5597 ** depending on the loops added to the current plan. */
5599 }
5601 /* Compute successively longer WherePaths using the previous generation
5602 ** of WherePaths as the basis for the next. Keep track of the mxChoice
5603 ** best paths at each generation */
5617 /* At this point, pWLoop is a candidate to be the next loop.
5618 ** Compute its cost */
5629 }
5634 );
5635 }
5644 }
5646 /* Check to see if pWLoop should be added to the set of
5647 ** mxChoice best-so-far paths.
5648 **
5649 ** First look for an existing path among best-so-far paths
5650 ** that covers the same set of loops and has the same isOrdered
5651 ** setting as the current path candidate.
5652 **
5653 ** The term "((pTo->isOrdered^isOrdered)&0x80)==0" is equivalent
5654 ** to (pTo->isOrdered==(-1))==(isOrdered==(-1))" for the range
5655 ** of legal values for isOrdered, -1..64.
5656 */
5660 ){
5663 }
5664 }
5666 /* None of the existing best-so-far paths match the candidate. */
5669 ){
5670 /* The current candidate is no better than any of the mxChoice
5671 ** paths currently in the best-so-far buffer. So discard
5672 ** this candidate as not viable. */
5678 }
5679 #endif
5681 }
5682 /* If we reach this points it means that the new candidate path
5683 ** needs to be added to the set of best-so-far paths. */
5685 /* Increase the size of the aTo set by one */
5688 /* New path replaces the prior worst to keep count below mxChoice */
5690 }
5697 }
5698 #endif
5700 /* Control reaches here if best-so-far path pTo=aTo[jj] covers the
5701 ** same set of loops and has the sam isOrdered setting as the
5702 ** candidate path. Check to see if the candidate should replace
5703 ** pTo or if the candidate should be skipped */
5714 }
5715 #endif
5716 /* Discard the candidate path from further consideration */
5719 }
5721 /* Control reaches here if the candidate path is better than the
5722 ** pTo path. Replace pTo with the candidate. */
5732 }
5733 #endif
5734 }
5735 /* pWLoop is a winner. Add it to the set of best so far */
5751 ){
5755 }
5756 }
5757 }
5758 }
5759 }
5772 }
5773 }
5774 }
5775 #endif
5777 /* Swap the roles of aFrom and aTo for the next generation */
5782 }
5788 }
5790 /* Find the lowest cost path. pFrom will be left pointing to that path */
5794 }
5796 /* Load the lowest cost path into pWInfo */
5802 }
5806 && nRowEst
5807 ){
5808 Bitmask notUsed;
5813 }
5814 }
5819 }
5824 }
5827 ){
5831 );
5836 }
5837 }
5838 }
5843 /* Free temporary memory and return success */
5846 }
5848 /*
5849 ** Most queries use only a single table (they are not joins) and have
5850 ** simple == constraints against indexed fields. This routine attempts
5851 ** to plan those simple cases using much less ceremony than the
5852 ** general-purpose query planner, and thereby yield faster sqlite3_prepare()
5853 ** times for the common case.
5854 **
5855 ** Return non-zero on success, if this query can be handled by this
5856 ** no-frills query planner. Return zero if this query needs the
5857 ** general-purpose query planner.
5858 */
5888 /* TUNING: Cost of a rowid lookup is 10 */
5902 }
5907 }
5911 /* TUNING: Cost of a unique index lookup is 15 */
5914 }
5915 }
5925 }
5926 #ifdef SQLITE_DEBUG
5928 #endif
5930 }
5932 }
5934 /*
5935 ** Generate the beginning of the loop used for WHERE clause processing.
5936 ** The return value is a pointer to an opaque structure that contains
5937 ** information needed to terminate the loop. Later, the calling routine
5938 ** should invoke sqlite3WhereEnd() with the return value of this function
5939 ** in order to complete the WHERE clause processing.
5940 **
5941 ** If an error occurs, this routine returns NULL.
5942 **
5943 ** The basic idea is to do a nested loop, one loop for each table in
5944 ** the FROM clause of a select. (INSERT and UPDATE statements are the
5945 ** same as a SELECT with only a single table in the FROM clause.) For
5946 ** example, if the SQL is this:
5947 **
5948 ** SELECT * FROM t1, t2, t3 WHERE ...;
5949 **
5950 ** Then the code generated is conceptually like the following:
5951 **
5952 ** foreach row1 in t1 do \ Code generated
5953 ** foreach row2 in t2 do |-- by sqlite3WhereBegin()
5954 ** foreach row3 in t3 do /
5955 ** ...
5956 ** end \ Code generated
5957 ** end |-- by sqlite3WhereEnd()
5958 ** end /
5959 **
5960 ** Note that the loops might not be nested in the order in which they
5961 ** appear in the FROM clause if a different order is better able to make
5962 ** use of indices. Note also that when the IN operator appears in
5963 ** the WHERE clause, it might result in additional nested loops for
5964 ** scanning through all values on the right-hand side of the IN.
5965 **
5966 ** There are Btree cursors associated with each table. t1 uses cursor
5967 ** number pTabList->a[0].iCursor. t2 uses the cursor pTabList->a[1].iCursor.
5968 ** And so forth. This routine generates code to open those VDBE cursors
5969 ** and sqlite3WhereEnd() generates the code to close them.
5970 **
5971 ** The code that sqlite3WhereBegin() generates leaves the cursors named
5972 ** in pTabList pointing at their appropriate entries. The [...] code
5973 ** can use OP_Column and OP_Rowid opcodes on these cursors to extract
5974 ** data from the various tables of the loop.
5975 **
5976 ** If the WHERE clause is empty, the foreach loops must each scan their
5977 ** entire tables. Thus a three-way join is an O(N^3) operation. But if
5978 ** the tables have indices and there are terms in the WHERE clause that
5979 ** refer to those indices, a complete table scan can be avoided and the
5980 ** code will run much faster. Most of the work of this routine is checking
5981 ** to see if there are indices that can be used to speed up the loop.
5982 **
5983 ** Terms of the WHERE clause are also used to limit which rows actually
5984 ** make it to the "..." in the middle of the loop. After each "foreach",
5985 ** terms of the WHERE clause that use only terms in that loop and outer
5986 ** loops are evaluated and if false a jump is made around all subsequent
5987 ** inner loops (or around the "..." if the test occurs within the inner-
5988 ** most loop)
5989 **
5990 ** OUTER JOINS
5991 **
5992 ** An outer join of tables t1 and t2 is conceptally coded as follows:
5993 **
5994 ** foreach row1 in t1 do
5995 ** flag = 0
5996 ** foreach row2 in t2 do
5997 ** start:
5998 ** ...
5999 ** flag = 1
6000 ** end
6001 ** if flag==0 then
6002 ** move the row2 cursor to a null row
6003 ** goto start
6004 ** fi
6005 ** end
6006 **
6007 ** ORDER BY CLAUSE PROCESSING
6008 **
6009 ** pOrderBy is a pointer to the ORDER BY clause (or the GROUP BY clause
6010 ** if the WHERE_GROUPBY flag is set in wctrlFlags) of a SELECT statement
6011 ** if there is one. If there is no ORDER BY clause or if this routine
6012 ** is called from an UPDATE or DELETE statement, then pOrderBy is NULL.
6013 **
6014 ** The iIdxCur parameter is the cursor number of an index. If
6015 ** WHERE_ONETABLE_ONLY is set, iIdxCur is the cursor number of an index
6016 ** to use for OR clause processing. The WHERE clause should use this
6017 ** specific cursor. If WHERE_ONEPASS_DESIRED is set, then iIdxCur is
6018 ** the first cursor in an array of cursors for all indices. iIdxCur should
6019 ** be used to compute the appropriate cursor depending on which index is
6020 ** used.
6021 */
6030 ){
6045 /* Variable initialization */
6049 /* An ORDER/GROUP BY clause of more than 63 terms cannot be optimized */
6054 /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via
6055 ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */
6058 }
6060 /* The number of tables in the FROM clause is limited by the number of
6061 ** bits in a Bitmask
6062 */
6067 }
6069 /* This function normally generates a nested loop for all tables in
6070 ** pTabList. But if the WHERE_ONETABLE_ONLY flag is set, then we should
6071 ** only generate code for the first table in pTabList and assume that
6072 ** any cursors associated with subsequent tables are uninitialized.
6073 */
6076 /* Allocate and initialize the WhereInfo structure that will become the
6077 ** return value. A single allocation is used to store the WhereInfo
6078 ** struct, the contents of WhereInfo.a[], the WhereClause structure
6079 ** and the WhereMaskSet structure. Since WhereClause contains an 8-byte
6080 ** field (type Bitmask) it must be aligned on an 8-byte boundary on
6081 ** some architectures. Hence the ROUND8() below.
6082 */
6089 }
6105 #ifdef SQLITE_DEBUG
6107 #endif
6109 /* Split the WHERE clause into separate subexpressions where each
6110 ** subexpression is separated by an AND operator.
6111 */
6116 /* Special case: a WHERE clause that is constant. Evaluate the
6117 ** expression and either jump over all of the code or fall thru.
6118 */
6122 SQLITE_JUMPIFNULL);
6124 }
6125 }
6127 /* Special case: No FROM clause
6128 */
6133 }
6134 }
6136 /* Assign a bit from the bitmask to every term in the FROM clause.
6137 **
6138 ** When assigning bitmask values to FROM clause cursors, it must be
6139 ** the case that if X is the bitmask for the N-th FROM clause term then
6140 ** the bitmask for all FROM clause terms to the left of the N-th term
6141 ** is (X-1). An expression from the ON clause of a LEFT JOIN can use
6142 ** its Expr.iRightJoinTable value to find the bitmask of the right table
6143 ** of the join. Subtracting one from the right table bitmask gives a
6144 ** bitmask for all tables to the left of the join. Knowing the bitmask
6145 ** for all tables to the left of a left join is important. Ticket #3015.
6146 **
6147 ** Note that bitmasks are created for all pTabList->nSrc tables in
6148 ** pTabList, not just the first nTabList tables. nTabList is normally
6149 ** equal to pTabList->nSrc but might be shortened to 1 if the
6150 ** WHERE_ONETABLE_ONLY flag is set.
6151 */
6154 }
6155 #ifndef NDEBUG
6156 {
6162 }
6163 }
6164 #endif
6166 /* Analyze all of the subexpressions. Note that exprAnalyze() might
6167 ** add new virtual terms onto the end of the WHERE clause. We do not
6168 ** want to analyze these virtual terms, so start analyzing at the end
6169 ** and work forward so that the added virtual terms are never processed.
6170 */
6174 }
6178 /* The DISTINCT marking is pointless. Ignore it. */
6181 /* Try to ORDER BY the result set to make distinct processing easier */
6184 }
6185 }
6187 /* Construct the WhereLoop objects */
6189 #if defined(WHERETRACE_ENABLED)
6190 /* Display all terms of the WHERE clause */
6195 }
6196 }
6197 #endif
6203 /* Display all of the WhereLoop objects if wheretrace is enabled */
6213 }
6214 }
6215 #endif
6222 }
6223 }
6226 }
6229 }
6236 }
6241 }
6245 }
6249 }
6250 }
6254 }
6255 }
6256 #endif
6257 /* Attempt to omit tables from the join that do not effect the result */
6261 ){
6270 ){
6272 }
6278 ){
6280 }
6281 }
6285 nTabList--;
6286 }
6287 }
6291 /* If the caller is an UPDATE or DELETE statement that is requesting
6292 ** to use a one-pass algorithm, determine if this is appropriate.
6293 ** The one-pass algorithm only works if the WHERE clause constrains
6294 ** the statement to update a single row.
6295 */
6302 }
6303 }
6305 /* Open all tables in the pTabList and any indices selected for
6306 ** searching those tables.
6307 */
6319 /* Do nothing */
6321 #ifndef SQLITE_OMIT_VIRTUALTABLE
6327 /* noop */
6329 #endif
6336 };
6348 }
6351 }
6356 /* iIdxCur is always set if to a positive value if ONEPASS is possible */
6360 ){
6361 /* This is one term of an OR-optimization using the PRIMARY KEY of a
6362 ** WITHOUT ROWID table. No need for a separate index */
6370 iIndexCur++;
6372 }
6380 }
6388 }
6389 }
6392 }
6396 /* Generate the code to do the search. Each iteration of the for
6397 ** loop below generates code for a single nested loop of the VM
6398 ** program.
6399 */
6403 #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
6408 }
6409 #endif
6414 }
6416 /* Done. */
6420 /* Jump here if malloc fails */
6421 whereBeginError:
6425 }
6427 }
6429 /*
6430 ** Generate the end of the WHERE loop. See comments on
6431 ** sqlite3WhereBegin() for additional information.
6432 */
6442 /* Generate loop termination code.
6443 */
6458 }
6470 }
6472 }
6479 }
6486 }
6489 }
6494 }
6496 }
6499 }
6501 /* The "break" point is here, just past the end of the outer loop.
6502 ** Set it.
6503 */
6516 /* For a co-routine, change all OP_Column references to the table of
6517 ** the co-routine into OP_SCopy of result contained in a register.
6518 ** OP_Rowid becomes OP_Null.
6519 */
6535 }
6536 }
6538 }
6540 /* Close all of the cursors that were opened by sqlite3WhereBegin.
6541 ** Except, do not close cursors that will be reused by the OR optimization
6542 ** (WHERE_OMIT_OPEN_CLOSE). And do not close the OP_OpenWrite cursors
6543 ** created for the ONEPASS optimization.
6544 */
6548 ){
6552 }
6556 ){
6558 }
6559 }
6561 /* If this scan uses an index, make VDBE code substitutions to read data
6562 ** from the index instead of from the table where possible. In some cases
6563 ** this optimization prevents the table from ever being read, which can
6564 ** yield a significant performance boost.
6565 **
6566 ** Calls to the code generator in between sqlite3WhereBegin and
6567 ** sqlite3WhereEnd will have created code that references the table
6568 ** directly. This loop scans all that code looking for opcodes
6569 ** that reference the table and converts them into opcodes that
6570 ** reference the index.
6571 */
6576 }
6589 }
6594 }
6599 }
6600 }
6601 }
6602 }
6604 /* Final cleanup
6605 */
6609 }