| blob | a5f04767bfa19f112b7e987340e6ff113a35d42b |
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 file contains C code routines that are called by the parser
13 ** to handle SELECT statements in SQLite.
14 */
17 /*
18 ** Trace output macros
19 */
20 #if SELECTTRACE_ENABLED
22 # define SELECTTRACE(K,P,S,X) \
23 if(sqlite3SelectTrace&(K)) \
25 (S)->zSelName,(S)),\
26 sqlite3DebugPrintf X
27 #else
28 # define SELECTTRACE(K,P,S,X)
29 #endif
32 /*
33 ** An instance of the following object is used to record information about
34 ** how to process the DISTINCT keyword, to simplify passing that information
35 ** into the selectInnerLoop() routine.
36 */
43 };
45 /*
46 ** An instance of the following object is used to record information about
47 ** the ORDER BY (or GROUP BY) clause of query is being coded.
48 */
60 };
63 /*
64 ** Delete all the content of a Select structure. Deallocate the structure
65 ** itself only if bFree is true.
66 */
82 }
83 }
85 /*
86 ** Initialize a SelectDest structure.
87 */
94 }
97 /*
98 ** Allocate a new Select structure and return a pointer to that
99 ** structure.
100 */
112 ){
114 Select standin;
119 }
123 }
129 #if SELECTTRACE_ENABLED
131 #endif
153 }
156 }
158 #if SELECTTRACE_ENABLED
159 /*
160 ** Set the name of a Select object
161 */
165 }
166 }
167 #endif
170 /*
171 ** Delete the given Select structure and all of its substructures.
172 */
175 }
177 /*
178 ** Return a pointer to the right-most SELECT statement in a compound.
179 */
183 }
185 /*
186 ** Given 1 to 3 identifiers preceding the JOIN keyword, determine the
187 ** type of join. Return an integer constant that expresses that type
188 ** in terms of the following bit values:
189 **
190 ** JT_INNER
191 ** JT_CROSS
192 ** JT_OUTER
193 ** JT_NATURAL
194 ** JT_LEFT
195 ** JT_RIGHT
196 **
197 ** A full outer join is the combination of JT_LEFT and JT_RIGHT.
198 **
199 ** If an illegal or unsupported join type is seen, then still return
200 ** a join type, but put an error in the pParse structure.
201 */
206 /* 0123456789 123456789 123456789 123 */
220 };
232 }
233 }
238 }
239 }
243 ){
255 }
257 }
259 /*
260 ** Return the index of a column in a table. Return -1 if the column
261 ** is not contained in the table.
262 */
267 }
269 }
271 /*
272 ** Search the first N tables in pSrc, from left to right, looking for a
273 ** table that has a column named zCol.
274 **
275 ** When found, set *piTab and *piCol to the table index and column index
276 ** of the matching column and return TRUE.
277 **
278 ** If not found, return FALSE.
279 */
286 ){
297 }
299 }
300 }
302 }
304 /*
305 ** This function is used to add terms implied by JOIN syntax to the
306 ** WHERE clause expression of a SELECT statement. The new term, which
307 ** is ANDed with the existing WHERE clause, is of the form:
308 **
309 ** (tab1.col1 = tab2.col2)
310 **
311 ** where tab1 is the iSrc'th table in SrcList pSrc and tab2 is the
312 ** (iSrc+1)'th. Column col1 is column iColLeft of tab1, and col2 is
313 ** column iColRight of tab2.
314 */
324 ){
344 }
346 }
348 /*
349 ** Set the EP_FromJoin property on all terms of the given expression.
350 ** And set the Expr.iRightJoinTable to iTable for every term in the
351 ** expression.
352 **
353 ** The EP_FromJoin property is used on terms of an expression to tell
354 ** the LEFT OUTER JOIN processing logic that this term is part of the
355 ** join restriction specified in the ON or USING clause and not a part
356 ** of the more general WHERE clause. These terms are moved over to the
357 ** WHERE clause during join processing but we need to remember that they
358 ** originated in the ON or USING clause.
359 **
360 ** The Expr.iRightJoinTable tells the WHERE clause processing that the
361 ** expression depends on table iRightJoinTable even if that table is not
362 ** explicitly mentioned in the expression. That information is needed
363 ** for cases like this:
364 **
365 ** SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.b AND t1.x=5
366 **
367 ** The where clause needs to defer the handling of the t1.x=5
368 ** term until after the t2 loop of the join. In that way, a
369 ** NULL t2 row will be inserted whenever t1.x!=5. If we do not
370 ** defer the handling of t1.x=5, it will be processed immediately
371 ** after the t1 loop and rows with t1.x!=5 will never appear in
372 ** the output, which is incorrect.
373 */
384 }
385 }
388 }
389 }
391 /*
392 ** This routine processes the join information for a SELECT statement.
393 ** ON and USING clauses are converted into extra terms of the WHERE clause.
394 ** NATURAL joins also create extra WHERE clause terms.
395 **
396 ** The terms of a FROM clause are contained in the Select.pSrc structure.
397 ** The left most table is the first entry in Select.pSrc. The right-most
398 ** table is the last entry. The join operator is held in the entry to
399 ** the left. Thus entry 0 contains the join operator for the join between
400 ** entries 0 and 1. Any ON or USING clauses associated with the join are
401 ** also attached to the left entry.
402 **
403 ** This routine returns the number of errors encountered.
404 */
422 /* When the NATURAL keyword is present, add WHERE clause terms for
423 ** every column that the two tables have in common.
424 */
430 }
440 }
441 }
442 }
444 /* Disallow both ON and USING clauses in the same join
445 */
450 }
452 /* Add the ON clause to the end of the WHERE clause, connected by
453 ** an AND operator.
454 */
459 }
461 /* Create extra terms on the WHERE clause for each column named
462 ** in the USING clause. Example: If the two tables to be joined are
463 ** A and B and the USING clause names X, Y, and Z, then add this
464 ** to the WHERE clause: A.X=B.X AND A.Y=B.Y AND A.Z=B.Z
465 ** Report an error if any column mentioned in the USING clause is
466 ** not contained in both tables to be joined.
467 */
480 ){
484 }
487 }
488 }
489 }
491 }
493 /* Forward reference */
499 );
501 /*
502 ** Generate code that will push the record in registers regData
503 ** through regData+nData-1 onto the sorter.
504 */
513 ){
532 }
540 }
543 }
560 }
581 }
585 }
590 }
596 /* Fill the sorter until it contains LIMIT+OFFSET entries. (The iLimit
597 ** register is initialized with value of LIMIT+OFFSET.) After the sorter
598 ** fills up, delete the least entry in the sorter after each insert.
599 ** Thus we never hold more than the LIMIT+OFFSET rows in memory at once */
606 }
609 /* If the inner loop is driven by an index such that values from
610 ** the same iteration of the inner loop are in sorted order, then
611 ** immediately jump to the next iteration of an inner loop if the
612 ** entry from the current iteration does not fit into the top
613 ** LIMIT+OFFSET entries of the sorter. */
618 }
620 }
621 }
623 /*
624 ** Add code to implement the OFFSET
625 */
630 ){
634 }
635 }
637 /*
638 ** Add code that will check to make sure the N registers starting at iMem
639 ** form a distinct entry. iTab is a sorting index that holds previously
640 ** seen combinations of the N values. A new entry is made in iTab
641 ** if the current N values are new.
642 **
643 ** A jump to addrRepeat is made and the N+1 values are popped from the
644 ** stack if the top N elements are not distinct.
645 */
652 ){
663 }
665 /*
666 ** This routine generates the code for the inside of the inner loop
667 ** of a SELECT.
668 **
669 ** If srcTab is negative, then the p->pEList expressions
670 ** are evaluated in order to get the data for this row. If srcTab is
671 ** zero or more, then data is pulled from srcTab and p->pEList is used only
672 ** to get the number of columns and the collation sequence for each column.
673 */
683 ){
692 /* Usually, regResult is the first cell in an array of memory cells
693 ** containing the current result row. In this case regOrig is set to the
694 ** same value. However, if the results are being sent to the sorter, the
695 ** values for any expressions that are also part of the sort-key are omitted
696 ** from this array. In this case regOrig is set to zero. */
707 }
709 /* Pull the requested columns.
710 */
718 }
722 /* This is an error condition that can result, for example, when a SELECT
723 ** on the right-hand side of an INSERT contains more result columns than
724 ** there are columns in the table on the left. The error will be caught
725 ** and reported later. But we need to make sure enough memory is allocated
726 ** to avoid other spurious errors in the meantime. */
728 }
735 }
737 /* If the destination is an EXISTS(...) expression, the actual
738 ** values returned by the SELECT are not required.
739 */
740 u8 ecelFlags;
745 }
747 /* For each expression in p->pEList that is a copy of an expression in
748 ** the ORDER BY clause (pSort->pOrderBy), set the associated
749 ** iOrderByCol value to one more than the index of the ORDER BY
750 ** expression within the sort-key that pushOntoSorter() will generate.
751 ** This allows the p->pEList field to be omitted from the sorted record,
752 ** saving space and CPU cycles. */
758 }
759 }
763 }
766 }
768 /* If the DISTINCT keyword was present on the SELECT statement
769 ** and this row has been seen before, then do not make this row
770 ** part of the result.
771 */
779 /* Allocate space for the previous row */
783 /* Change the OP_OpenEphemeral coded earlier to an OP_Null
784 ** sets the MEM_Cleared bit on the first register of the
785 ** previous value. This will cause the OP_Ne below to always
786 ** fail on the first iteration of the loop even if the first
787 ** row is all NULLs.
788 */
804 }
807 }
811 }
816 }
821 regResult);
823 }
824 }
827 }
828 }
831 /* In this mode, write each query result to the key of the temporary
832 ** table iParm.
833 */
834 #ifndef SQLITE_OMIT_COMPOUND_SELECT
842 }
844 /* Construct a record from the query result, but instead of
845 ** saving that record, use it as a key to delete elements from
846 ** the temporary table iParm.
847 */
851 }
854 /* Store the result as data using a unique key.
855 */
866 #ifndef SQLITE_OMIT_CTE
868 /* If the destination is DistFifo, then cursor (iParm+1) is open
869 ** on an ephemeral index. If the current row is already present
870 ** in the index, do not write it to the output. If not, add the
871 ** current row to the index and proceed with writing it to the
872 ** output table as well. */
878 }
879 #endif
888 }
891 }
893 #ifndef SQLITE_OMIT_SUBQUERY
894 /* If we are creating a set for an "expr IN (SELECT ...)" construct,
895 ** then there should be a single item on the stack. Write this
896 ** item into the set table with bogus data.
897 */
900 /* At first glance you would think we could optimize out the
901 ** ORDER BY in this case since the order of entries in the set
902 ** does not matter. But there might be a LIMIT clause, in which
903 ** case the order does matter */
914 }
916 }
918 /* If any row exist in the result set, record that fact and abort.
919 */
922 /* The LIMIT clause will terminate the loop for us */
924 }
926 /* If this is a scalar select that is part of an expression, then
927 ** store the results in the appropriate memory cell or array of
928 ** memory cells and break out of the scan loop.
929 */
938 /* The LIMIT clause will jump out of the loop for us */
939 }
941 }
950 nPrefixReg);
956 }
958 }
960 #ifndef SQLITE_OMIT_CTE
961 /* Write the results into a priority queue that is order according to
962 ** pDest->pOrderBy (in pSO). pDest->iSDParm (in iParm) is the cursor for an
963 ** index with pSO->nExpr+2 columns. Build a key using pSO for the first
964 ** pSO->nExpr columns, then make sure all keys are unique by adding a
965 ** final OP_Sequence column. The last column is the record as a blob.
966 */
980 /* If the destination is DistQueue, then cursor (iParm+1) is open
981 ** on a second ephemeral index that holds all values every previously
982 ** added to the queue. */
986 }
991 }
996 }
1004 }
1009 #if !defined(SQLITE_OMIT_TRIGGER)
1010 /* Discard the results. This is used for SELECT statements inside
1011 ** the body of a TRIGGER. The purpose of such selects is to call
1012 ** user-defined functions that have side effects. We do not care
1013 ** about the actual results of the select.
1014 */
1018 }
1019 #endif
1020 }
1022 /* Jump to the end of the loop if the LIMIT is reached. Except, if
1023 ** there is a sorter, in which case the sorter has already limited
1024 ** the output for us.
1025 */
1028 }
1029 }
1031 /*
1032 ** Allocate a KeyInfo object sufficient for an index of N key columns and
1033 ** X extra columns.
1034 */
1048 }
1050 }
1052 /*
1053 ** Deallocate a KeyInfo object
1054 */
1060 }
1061 }
1063 /*
1064 ** Make a new pointer to a KeyInfo object
1065 */
1070 }
1072 }
1074 #ifdef SQLITE_DEBUG
1075 /*
1076 ** Return TRUE if a KeyInfo object can be change. The KeyInfo object
1077 ** can only be changed if this is just a single reference to the object.
1078 **
1079 ** This routine is used only inside of assert() statements.
1080 */
1084 /*
1085 ** Given an expression list, generate a KeyInfo structure that records
1086 ** the collating sequence for each expression in that expression list.
1087 **
1088 ** If the ExprList is an ORDER BY or GROUP BY clause then the resulting
1089 ** KeyInfo structure is appropriate for initializing a virtual index to
1090 ** implement that clause. If the ExprList is the result set of a SELECT
1091 ** then the KeyInfo structure is appropriate for initializing a virtual
1092 ** index to implement a DISTINCT test.
1093 **
1094 ** Space to hold the KeyInfo structure is obtained from malloc. The calling
1095 ** function is responsible for seeing that this structure is eventually
1096 ** freed.
1097 */
1103 ){
1117 }
1118 }
1120 }
1122 /*
1123 ** Name of the connection operator, used for error messages.
1124 */
1132 }
1134 }
1136 #ifndef SQLITE_OMIT_EXPLAIN
1137 /*
1138 ** Unless an "EXPLAIN QUERY PLAN" command is being processed, this function
1139 ** is a no-op. Otherwise, it adds a single row of output to the EQP result,
1140 ** where the caption is of the form:
1141 **
1142 ** "USE TEMP B-TREE FOR xxx"
1143 **
1144 ** where xxx is one of "DISTINCT", "ORDER BY" or "GROUP BY". Exactly which
1145 ** is determined by the zUsage argument.
1146 */
1152 }
1153 }
1155 /*
1156 ** Assign expression b to lvalue a. A second, no-op, version of this macro
1157 ** is provided when SQLITE_OMIT_EXPLAIN is defined. This allows the code
1158 ** in sqlite3Select() to assign values to structure member variables that
1159 ** only exist if SQLITE_OMIT_EXPLAIN is not defined without polluting the
1160 ** code with #ifndef directives.
1161 */
1162 # define explainSetInteger(a, b) a = b
1164 #else
1165 /* No-op versions of the explainXXX() functions and macros. */
1166 # define explainTempTable(y,z)
1167 # define explainSetInteger(y,z)
1168 #endif
1170 #if !defined(SQLITE_OMIT_EXPLAIN) && !defined(SQLITE_OMIT_COMPOUND_SELECT)
1171 /*
1172 ** Unless an "EXPLAIN QUERY PLAN" command is being processed, this function
1173 ** is a no-op. Otherwise, it adds a single row of output to the EQP result,
1174 ** where the caption is of one of the two forms:
1175 **
1176 ** "COMPOSITE SUBQUERIES iSub1 and iSub2 (op)"
1177 ** "COMPOSITE SUBQUERIES iSub1 and iSub2 USING TEMP B-TREE (op)"
1178 **
1179 ** where iSub1 and iSub2 are the integers passed as the corresponding
1180 ** function parameters, and op is the text representation of the parameter
1181 ** of the same name. The parameter "op" must be one of TK_UNION, TK_EXCEPT,
1182 ** TK_INTERSECT or TK_ALL. The first form is used if argument bUseTmp is
1183 ** false, or the second form if it is true.
1184 */
1191 ){
1198 );
1200 }
1201 }
1202 #else
1203 /* No-op versions of the explainXXX() functions and macros. */
1204 # define explainComposite(v,w,x,y,z)
1205 #endif
1207 /*
1208 ** If the inner loop was generated using a non-null pOrderBy argument,
1209 ** then the results were placed in a sorter. After the loop is terminated
1210 ** we need to run the sorter and output the results. The following
1211 ** routine generates the code needed to do that.
1212 */
1219 ){
1244 }
1254 }
1261 }
1274 }
1281 }
1284 }
1292 }
1293 #ifndef SQLITE_OMIT_SUBQUERY
1301 }
1303 /* The LIMIT clause will terminate the loop for us */
1305 }
1306 #endif
1316 }
1318 }
1319 }
1325 }
1327 }
1328 /* The bottom of the loop
1329 */
1335 }
1338 }
1340 /*
1341 ** Return a pointer to a string containing the 'declaration type' of the
1342 ** expression pExpr. The string may be treated as static by the caller.
1343 **
1344 ** Also try to estimate the size of the returned value and return that
1345 ** result in *pEstWidth.
1346 **
1347 ** The declaration type is the exact datatype definition extracted from the
1348 ** original CREATE TABLE statement if the expression is a column. The
1349 ** declaration type for a ROWID field is INTEGER. Exactly when an expression
1350 ** is considered a column can be complex in the presence of subqueries. The
1351 ** result-set expression in all of the following SELECT statements is
1352 ** considered a column by this function.
1353 **
1354 ** SELECT col FROM tbl;
1355 ** SELECT (SELECT col FROM tbl;
1356 ** SELECT (SELECT col FROM tbl);
1357 ** SELECT abc FROM (SELECT col AS abc FROM tbl);
1358 **
1359 ** The declaration type for any expression other than a column is NULL.
1360 **
1361 ** This routine has either 3 or 6 parameters depending on whether or not
1362 ** the SQLITE_ENABLE_COLUMN_METADATA compile-time option is used.
1363 */
1364 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1365 # define columnType(A,B,C,D,E,F) columnTypeImpl(A,B,C,D,E,F)
1367 # define columnType(A,B,C,D,E,F) columnTypeImpl(A,B,F)
1368 #endif
1372 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1376 #endif
1377 u8 *pEstWidth
1378 ){
1382 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1386 #endif
1393 /* The expression is a column. Locate the table the column is being
1394 ** extracted from in NameContext.pSrcList. This table may be real
1395 ** database table or a subquery.
1396 */
1410 }
1411 }
1414 /* At one time, code such as "SELECT new.x" within a trigger would
1415 ** cause this condition to run. Since then, we have restructured how
1416 ** trigger code is generated and so this condition is no longer
1417 ** possible. However, it can still be true for statements like
1418 ** the following:
1419 **
1420 ** CREATE TABLE t1(col INTEGER);
1421 ** SELECT (SELECT t1.col) FROM FROM t1;
1422 **
1423 ** when columnType() is called on the expression "t1.col" in the
1424 ** sub-select. In this case, set the column type to NULL, even
1425 ** though it should really be "INTEGER".
1426 **
1427 ** This is not a problem, as the column type of "t1.col" is never
1428 ** used. When columnType() is called on the expression
1429 ** "(SELECT t1.col)", the correct type is returned (see the TK_SELECT
1430 ** branch below. */
1432 }
1436 /* The "table" is actually a sub-select or a view in the FROM clause
1437 ** of the SELECT statement. Return the declaration type and origin
1438 ** data for the result-set column of the sub-select.
1439 */
1441 /* If iCol is less than zero, then the expression requests the
1442 ** rowid of the sub-select or view. This expression is legal (see
1443 ** test case misc2.2.2) - it always evaluates to NULL.
1444 */
1445 NameContext sNC;
1451 }
1453 /* A real table */
1457 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1465 }
1470 }
1471 #else
1477 }
1478 #endif
1479 }
1481 }
1482 #ifndef SQLITE_OMIT_SUBQUERY
1484 /* The expression is a sub-select. Return the declaration type and
1485 ** origin info for the single column in the result set of the SELECT
1486 ** statement.
1487 */
1488 NameContext sNC;
1497 }
1498 #endif
1499 }
1501 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1507 }
1508 #endif
1511 }
1513 /*
1514 ** Generate code that will tell the VDBE the declaration types of columns
1515 ** in the result set.
1516 */
1521 ){
1522 #ifndef SQLITE_OMIT_DECLTYPE
1525 NameContext sNC;
1532 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1538 /* The vdbe must make its own copy of the column-type and other
1539 ** column specific strings, in case the schema is reset before this
1540 ** virtual machine is deleted.
1541 */
1545 #else
1547 #endif
1549 }
1551 }
1554 /*
1555 ** Compute the column names for a SELECT statement.
1556 **
1557 ** The only guarantee that SQLite makes about column names is that if the
1558 ** column has an AS clause assigning it a name, that will be the name used.
1559 ** That is the only documented guarantee. However, countless applications
1560 ** developed over the years have made baseless assumptions about column names
1561 ** and will break if those assumptions changes. Hence, use extreme caution
1562 ** when modifying this routine to avoid breaking legacy.
1563 **
1564 ** See Also: sqlite3ColumnsFromExprList()
1565 **
1566 ** The PRAGMA short_column_names and PRAGMA full_column_names settings are
1567 ** deprecated. The default setting is short=ON, full=OFF. 99.9% of all
1568 ** applications should operate this way. Nevertheless, we need to support the
1569 ** other modes for legacy:
1570 **
1571 ** short=OFF, full=OFF: Column name is the text of the expression has it
1572 ** originally appears in the SELECT statement. In
1573 ** other words, the zSpan of the result expression.
1574 **
1575 ** short=ON, full=OFF: (This is the default setting). If the result
1576 ** refers directly to a table column, then the
1577 ** result column name is just the table column
1578 ** name: COLUMN. Otherwise use zSpan.
1579 **
1580 ** full=ON, short=ANY: If the result refers directly to a table column,
1581 ** then the result column name with the table name
1582 ** prefix, ex: TABLE.COLUMN. Otherwise use zSpan.
1583 */
1587 ){
1597 #ifndef SQLITE_OMIT_EXPLAIN
1598 /* If this is an EXPLAIN, skip this step */
1601 }
1602 #endif
1605 /* Column names are determined by the left-most term of a compound select */
1622 /* An AS clause always takes first priority */
1636 }
1643 }
1648 }
1649 }
1651 }
1653 /*
1654 ** Given an expression list (which is really the list of expressions
1655 ** that form the result set of a SELECT statement) compute appropriate
1656 ** column names for a table that would hold the expression list.
1657 **
1658 ** All column names will be unique.
1659 **
1660 ** Only the column names are computed. Column.zType, Column.zColl,
1661 ** and other fields of Column are zeroed.
1662 **
1663 ** Return SQLITE_OK on success. If a memory allocation error occurs,
1664 ** store NULL in *paCol and 0 in *pnCol and return SQLITE_NOMEM.
1665 **
1666 ** The only guarantee that SQLite makes about column names is that if the
1667 ** column has an AS clause assigning it a name, that will be the name used.
1668 ** That is the only documented guarantee. However, countless applications
1669 ** developed over the years have made baseless assumptions about column names
1670 ** and will break if those assumptions changes. Hence, use extreme caution
1671 ** when modifying this routine to avoid breaking legacy.
1672 **
1673 ** See Also: generateColumnNames()
1674 */
1680 ){
1698 }
1704 /* Get an appropriate name for the column
1705 */
1707 /* If the column contains an "AS <name>" phrase, use <name> as the name */
1713 }
1716 ){
1717 /* For columns use the column name name */
1726 /* Use the original text of the column expression as its name */
1728 }
1729 }
1734 }
1736 /* Make sure the column name is unique. If the name is not unique,
1737 ** append an integer to the name so that it becomes unique.
1738 */
1745 }
1748 }
1753 }
1754 }
1759 }
1764 }
1766 }
1768 /*
1769 ** Add type and collation information to a column list based on
1770 ** a SELECT statement.
1771 **
1772 ** The column list presumably came from selectColumnNamesFromExprList().
1773 ** The column list has only names, not types or collations. This
1774 ** routine goes through and adds the types and collations.
1775 **
1776 ** This routine requires that all identifiers in the SELECT
1777 ** statement be resolved.
1778 */
1783 ){
1785 NameContext sNC;
1813 }
1814 }
1819 }
1820 }
1822 }
1824 /*
1825 ** Given a SELECT statement, generate a Table structure that describes
1826 ** the result set of that SELECT.
1827 */
1843 }
1844 /* The sqlite3ResultSetOfSelect() is only used n contexts where lookaside
1845 ** is disabled */
1856 }
1858 }
1860 /*
1861 ** Get a VDBE for the given parser context. Create a new one if necessary.
1862 ** If an error occurs, return NULL and leave a message in pParse.
1863 */
1867 }
1870 ){
1872 }
1874 }
1877 /*
1878 ** Compute the iLimit and iOffset fields of the SELECT based on the
1879 ** pLimit and pOffset expressions. pLimit and pOffset hold the expressions
1880 ** that appear in the original SQL statement after the LIMIT and OFFSET
1881 ** keywords. Or NULL if those keywords are omitted. iLimit and iOffset
1882 ** are the integer memory register numbers for counters used to compute
1883 ** the limit and offset. If there is no limit and/or offset, then
1884 ** iLimit and iOffset are negative.
1885 **
1886 ** This routine changes the values of iLimit and iOffset only if
1887 ** a limit or offset is defined by pLimit and pOffset. iLimit and
1888 ** iOffset should have been preset to appropriate default values (zero)
1889 ** prior to calling this routine.
1890 **
1891 ** The iOffset register (if it exists) is initialized to the value
1892 ** of the OFFSET. The iLimit register is initialized to LIMIT. Register
1893 ** iOffset+1 is initialized to LIMIT+OFFSET.
1894 **
1895 ** Only if pLimit!=0 or pOffset!=0 do the limit registers get
1896 ** redefined. The UNION ALL operator uses this property to force
1897 ** the reuse of the same limit and offset registers across multiple
1898 ** SELECT statements.
1899 */
1907 /*
1908 ** "LIMIT -1" always shows all rows. There is some
1909 ** controversy about what the correct behavior should be.
1910 ** The current implementation interprets "LIMIT 0" to mean
1911 ** no rows.
1912 */
1927 }
1933 }
1942 }
1943 }
1944 }
1946 #ifndef SQLITE_OMIT_COMPOUND_SELECT
1947 /*
1948 ** Return the appropriate collating sequence for the iCol-th column of
1949 ** the result set for the compound-select statement "p". Return NULL if
1950 ** the column has no default collating sequence.
1951 **
1952 ** The collating sequence for the compound select is taken from the
1953 ** left-most term of the select that has a collating sequence.
1954 */
1961 }
1963 /* iCol must be less than p->pEList->nExpr. Otherwise an error would
1964 ** have been thrown during name resolution and we would not have gotten
1965 ** this far */
1968 }
1970 }
1972 /*
1973 ** The select statement passed as the second parameter is a compound SELECT
1974 ** with an ORDER BY clause. This function allocates and returns a KeyInfo
1975 ** structure suitable for implementing the ORDER BY.
1976 **
1977 ** Space to hold the KeyInfo structure is obtained from malloc. The calling
1978 ** function is responsible for ensuring that this structure is eventually
1979 ** freed.
1980 */
2000 }
2004 }
2005 }
2008 }
2010 #ifndef SQLITE_OMIT_CTE
2011 /*
2012 ** This routine generates VDBE code to compute the content of a WITH RECURSIVE
2013 ** query of the form:
2014 **
2015 ** <recursive-table> AS (<setup-query> UNION [ALL] <recursive-query>)
2016 ** \___________/ \_______________/
2017 ** p->pPrior p
2018 **
2019 **
2020 ** There is exactly one reference to the recursive-table in the FROM clause
2021 ** of recursive-query, marked with the SrcList->a[].fg.isRecursive flag.
2022 **
2023 ** The setup-query runs once to generate an initial set of rows that go
2024 ** into a Queue table. Rows are extracted from the Queue table one by
2025 ** one. Each row extracted from Queue is output to pDest. Then the single
2026 ** extracted row (now in the iCurrent table) becomes the content of the
2027 ** recursive-table for a recursive-query run. The output of the recursive-query
2028 ** is added back into the Queue table. Then another row is extracted from Queue
2029 ** and the iteration continues until the Queue table is empty.
2030 **
2031 ** If the compound query operator is UNION then no duplicate rows are ever
2032 ** inserted into the Queue table. The iDistinct table keeps a copy of all rows
2033 ** that have ever been inserted into Queue and causes duplicates to be
2034 ** discarded. If the operator is UNION ALL, then duplicates are allowed.
2035 **
2036 ** If the query has an ORDER BY, then entries in the Queue table are kept in
2037 ** ORDER BY order and the first entry is extracted for each cycle. Without
2038 ** an ORDER BY, the Queue table is just a FIFO.
2039 **
2040 ** If a LIMIT clause is provided, then the iteration stops after LIMIT rows
2041 ** have been output to pDest. A LIMIT of zero means to output no rows and a
2042 ** negative LIMIT means to output all rows. If there is also an OFFSET clause
2043 ** with a positive value, then the first OFFSET outputs are discarded rather
2044 ** than being sent to pDest. The LIMIT count does not begin until after OFFSET
2045 ** rows have been skipped.
2046 */
2051 ){
2070 /* Obtain authorization to do a recursive query */
2073 /* Process the LIMIT and OFFSET clauses, if they exist */
2085 /* Locate the cursor number of the Current table */
2090 }
2091 }
2093 /* Allocate cursors numbers for Queue and Distinct. The cursor number for
2094 ** the Distinct table must be exactly one greater than Queue in order
2095 ** for the SRT_DistFifo and SRT_DistQueue destinations to work. */
2102 }
2105 /* Allocate cursors for Current, Queue, and Distinct. */
2115 }
2120 }
2122 /* Detach the ORDER BY clause from the compound SELECT */
2125 /* Store the results of the setup-query in Queue. */
2131 /* Find the next row in the Queue and output that row */
2134 /* Transfer the next row in Queue over to Current */
2140 }
2143 /* Output the single row in Current */
2151 }
2154 /* Execute the recursive SELECT taking the single row in Current as
2155 ** the value for the recursive-table. Store the results in the Queue.
2156 */
2164 }
2166 /* Keep running the loop until the Queue is empty */
2170 end_of_recursive_query:
2176 }
2179 /* Forward references */
2184 );
2186 /*
2187 ** Handle the special case of a compound-select that originates from a
2188 ** VALUES clause. By handling this as a special case, we avoid deep
2189 ** recursion, and thus do not need to enforce the SQLITE_LIMIT_COMPOUND_SELECT
2190 ** on a VALUES clause.
2191 **
2192 ** Because the Select object originates from a VALUES clause:
2193 ** (1) It has no LIMIT or OFFSET
2194 ** (2) All terms are UNION ALL
2195 ** (3) There is no ORDER BY clause
2196 */
2201 ){
2215 nRow++;
2225 }
2227 }
2229 /*
2230 ** This routine is called to process a compound query form from
2231 ** two or more separate queries using UNION, UNION ALL, EXCEPT, or
2232 ** INTERSECT
2233 **
2234 ** "p" points to the right-most of the two queries. the query on the
2235 ** left is p->pPrior. The left query could also be a compound query
2236 ** in which case this routine will be called recursively.
2237 **
2238 ** The results of the total query are to be written into a destination
2239 ** of type eDest with parameter iParm.
2240 **
2241 ** Example 1: Consider a three-way compound SQL statement.
2242 **
2243 ** SELECT a FROM t1 UNION SELECT b FROM t2 UNION SELECT c FROM t3
2244 **
2245 ** This statement is parsed up as follows:
2246 **
2247 ** SELECT c FROM t3
2248 ** |
2249 ** `-----> SELECT b FROM t2
2250 ** |
2251 ** `------> SELECT a FROM t1
2252 **
2253 ** The arrows in the diagram above represent the Select.pPrior pointer.
2254 ** So if this routine is called with p equal to the t3 query, then
2255 ** pPrior will be the t2 query. p->op will be TK_UNION in this case.
2256 **
2257 ** Notice that because of the way SQLite parses compound SELECTs, the
2258 ** individual selects always group from left to right.
2259 */
2264 ){
2271 #ifndef SQLITE_OMIT_EXPLAIN
2274 #endif
2276 /* Make sure there is no ORDER BY or LIMIT clause on prior SELECTs. Only
2277 ** the last (right-most) SELECT in the series may have an ORDER BY or LIMIT.
2278 */
2289 }
2294 /* Create the destination temporary table if necessary
2295 */
2300 }
2302 /* Special handling for a compound-select that originates as a VALUES clause.
2303 */
2307 }
2309 /* Make sure all SELECTs in the statement have the same number of elements
2310 ** in their result sets.
2311 */
2315 #ifndef SQLITE_OMIT_CTE
2319 #endif
2321 /* Compound SELECTs that have an ORDER BY clause are handled separately.
2322 */
2327 /* Generate code for the left and right SELECT statements.
2328 */
2344 }
2354 }
2355 }
2365 ){
2367 }
2370 }
2372 }
2380 SelectDest uniondest;
2386 /* We can reuse a temporary table generated by a SELECT to our
2387 ** right.
2388 */
2393 /* We will need to create our own temporary table to hold the
2394 ** intermediate results.
2395 */
2403 }
2405 /* Code the SELECT statements to our left
2406 */
2413 }
2415 /* Code the current SELECT statement
2416 */
2422 }
2432 /* Query flattening in sqlite3Select() might refill p->pOrderBy.
2433 ** Be sure to delete p->pOrderBy, therefore, to avoid a memory leak. */
2440 }
2447 /* Convert the data in the temporary table into whatever form
2448 ** it is that we currently need.
2449 */
2465 }
2467 }
2473 SelectDest intersectdest;
2476 /* INTERSECT is different from the others since it requires
2477 ** two temporary tables. Hence it has its own case. Begin
2478 ** by allocating the tables we will need.
2479 */
2490 /* Code the SELECTs to our left into temporary table "tab1".
2491 */
2497 }
2499 /* Code the current SELECT into temporary table "tab2"
2500 */
2520 /* Generate code to take the intersection of the two temporary
2521 ** tables.
2522 */
2540 }
2541 }
2545 /* Compute collating sequences used by
2546 ** temporary tables needed to implement the compound select.
2547 ** Attach the KeyInfo structure to all temporary tables.
2548 **
2549 ** This section is run by the right-most SELECT statement only.
2550 ** SELECT statements to the left always skip this part. The right-most
2551 ** SELECT might also skip this part if it has no ORDER BY clause and
2552 ** no temp tables are required.
2553 */
2567 }
2572 }
2573 }
2579 /* If [0] is unused then [1] is also unused. So we can
2580 ** always safely abort as soon as the first unused slot is found */
2583 }
2586 P4_KEYINFO);
2588 }
2589 }
2591 }
2593 multi_select_end:
2598 }
2601 /*
2602 ** Error message for when two or more terms of a compound select have different
2603 ** size result sets.
2604 */
2611 }
2612 }
2614 /*
2615 ** Code an output subroutine for a coroutine implementation of a
2616 ** SELECT statment.
2617 **
2618 ** The data to be output is contained in pIn->iSdst. There are
2619 ** pIn->nSdst columns to be output. pDest is where the output should
2620 ** be sent.
2621 **
2622 ** regReturn is the number of the register holding the subroutine
2623 ** return address.
2624 **
2625 ** If regPrev>0 then it is the first register in a vector that
2626 ** records the previous output. mem[regPrev] is a flag that is false
2627 ** if there has been no previous output. If regPrev>0 then code is
2628 ** generated to suppress duplicates. pKeyInfo is used for comparing
2629 ** keys.
2630 **
2631 ** If the LIMIT found in p->iLimit is reached, jump immediately to
2632 ** iBreak.
2633 */
2643 ){
2651 /* Suppress duplicates for UNION, EXCEPT, and INTERSECT
2652 */
2662 }
2665 /* Suppress the first OFFSET entries if there is an OFFSET clause
2666 */
2672 /* Store the result as data using a unique key.
2673 */
2684 }
2686 #ifndef SQLITE_OMIT_SUBQUERY
2687 /* If we are creating a set for an "expr IN (SELECT ...)".
2688 */
2700 }
2702 /* If this is a scalar select that is part of an expression, then
2703 ** store the results in the appropriate memory cell and break out
2704 ** of the scan loop.
2705 */
2709 /* The LIMIT clause will jump out of the loop for us */
2711 }
2714 /* The results are stored in a sequence of registers
2715 ** starting at pDest->iSdst. Then the co-routine yields.
2716 */
2721 }
2725 }
2727 /* If none of the above, then the result destination must be
2728 ** SRT_Output. This routine is never called with any other
2729 ** destination other than the ones handled above or SRT_Output.
2730 **
2731 ** For SRT_Output, results are stored in a sequence of registers.
2732 ** Then the OP_ResultRow opcode is used to cause sqlite3_step() to
2733 ** return the next row of result.
2734 */
2740 }
2741 }
2743 /* Jump to the end of the loop if the LIMIT is reached.
2744 */
2747 }
2749 /* Generate the subroutine return
2750 */
2755 }
2757 /*
2758 ** Alternative compound select code generator for cases when there
2759 ** is an ORDER BY clause.
2760 **
2761 ** We assume a query of the following form:
2762 **
2763 ** <selectA> <operator> <selectB> ORDER BY <orderbylist>
2764 **
2765 ** <operator> is one of UNION ALL, UNION, EXCEPT, or INTERSECT. The idea
2766 ** is to code both <selectA> and <selectB> with the ORDER BY clause as
2767 ** co-routines. Then run the co-routines in parallel and merge the results
2768 ** into the output. In addition to the two coroutines (called selectA and
2769 ** selectB) there are 7 subroutines:
2770 **
2771 ** outA: Move the output of the selectA coroutine into the output
2772 ** of the compound query.
2773 **
2774 ** outB: Move the output of the selectB coroutine into the output
2775 ** of the compound query. (Only generated for UNION and
2776 ** UNION ALL. EXCEPT and INSERTSECT never output a row that
2777 ** appears only in B.)
2778 **
2779 ** AltB: Called when there is data from both coroutines and A<B.
2780 **
2781 ** AeqB: Called when there is data from both coroutines and A==B.
2782 **
2783 ** AgtB: Called when there is data from both coroutines and A>B.
2784 **
2785 ** EofA: Called when data is exhausted from selectA.
2786 **
2787 ** EofB: Called when data is exhausted from selectB.
2788 **
2789 ** The implementation of the latter five subroutines depend on which
2790 ** <operator> is used:
2791 **
2792 **
2793 ** UNION ALL UNION EXCEPT INTERSECT
2794 ** ------------- ----------------- -------------- -----------------
2795 ** AltB: outA, nextA outA, nextA outA, nextA nextA
2796 **
2797 ** AeqB: outA, nextA nextA nextA outA, nextA
2798 **
2799 ** AgtB: outB, nextB outB, nextB nextB nextB
2800 **
2801 ** EofA: outB, nextB outB, nextB halt halt
2802 **
2803 ** EofB: outA, nextA outA, nextA outA, nextA halt
2804 **
2805 ** In the AltB, AeqB, and AgtB subroutines, an EOF on A following nextA
2806 ** causes an immediate jump to EofA and an EOF on B following nextB causes
2807 ** an immediate jump to EofB. Within EofA and EofB, and EOF on entry or
2808 ** following nextX causes a jump to the end of the select processing.
2809 **
2810 ** Duplicate removal in the UNION, EXCEPT, and INTERSECT cases is handled
2811 ** within the output subroutine. The regPrev register set holds the previously
2812 ** output value. A comparison is made against this value and the output
2813 ** is skipped if the next results would be the same as the previous.
2814 **
2815 ** The implementation plan is to implement the two coroutines and seven
2816 ** subroutines first, then put the control logic at the bottom. Like this:
2817 **
2818 ** goto Init
2819 ** coA: coroutine for left query (A)
2820 ** coB: coroutine for right query (B)
2821 ** outA: output one row of A
2822 ** outB: output one row of B (UNION and UNION ALL only)
2823 ** EofA: ...
2824 ** EofB: ...
2825 ** AltB: ...
2826 ** AeqB: ...
2827 ** AgtB: ...
2828 ** Init: initialize coroutine registers
2829 ** yield coA
2830 ** if eof(A) goto EofA
2831 ** yield coB
2832 ** if eof(B) goto EofB
2833 ** Cmpr: Compare A, B
2834 ** Jump AltB, AeqB, AgtB
2835 ** End: ...
2836 **
2837 ** We call AltB, AeqB, AgtB, EofA, and EofB "subroutines" but they are not
2838 ** actually called using Gosub and they do not Return. EofA and EofB loop
2839 ** until all data is exhausted then jump to the "end" labe. AltB, AeqB,
2840 ** and AgtB jump to either L2 or to one of EofA or EofB.
2841 */
2842 #ifndef SQLITE_OMIT_COMPOUND_SELECT
2847 ){
2882 #ifndef SQLITE_OMIT_EXPLAIN
2885 #endif
2896 /* Patch up the ORDER BY clause
2897 */
2905 /* For operators other than UNION ALL we have to make sure that
2906 ** the ORDER BY clause covers every term of the result set. Add
2907 ** terms to the ORDER BY clause as necessary.
2908 */
2915 }
2923 }
2924 }
2925 }
2927 /* Compute the comparison permutation and keyinfo that is used with
2928 ** the permutation used to determine if the next
2929 ** row of results comes from selectA or selectB. Also add explicit
2930 ** collations to the ORDER BY clause terms so that when the subqueries
2931 ** to the right and the left are evaluated, they use the correct
2932 ** collation.
2933 */
2942 }
2946 }
2948 /* Reattach the ORDER BY clause to the query.
2949 */
2953 /* Allocate a range of temporary registers and the KeyInfo needed
2954 ** for the logic that removes duplicate result rows when the
2955 ** operator is UNION, EXCEPT, or INTERSECT (but not UNION ALL).
2956 */
2971 }
2972 }
2973 }
2975 /* Separate the left and the right query from one another
2976 */
2982 }
2984 /* Compute the limit registers */
2990 regLimitA);
2994 }
3007 /* Generate a coroutine to evaluate the SELECT statement to the
3008 ** left of the compound operator - the "A" select.
3009 */
3019 /* Generate a coroutine to evaluate the SELECT statement on
3020 ** the right - the "B" select
3021 */
3035 /* Generate a subroutine that outputs the current row of the A
3036 ** select as the next output row of the compound select.
3037 */
3043 /* Generate a subroutine that outputs the current row of the B
3044 ** select as the next output row of the compound select.
3045 */
3051 }
3054 /* Generate a subroutine to run when the results from select A
3055 ** are exhausted and only data in select B remains.
3056 */
3066 }
3068 /* Generate a subroutine to run when the results from select B
3069 ** are exhausted and only data in select A remains.
3070 */
3079 }
3081 /* Generate code to handle the case of A<B
3082 */
3088 /* Generate code to handle the case of A==B
3089 */
3094 addrAltB++;
3097 addrAeqB =
3100 }
3102 /* Generate code to handle the case of A>B
3103 */
3108 }
3112 /* This code runs once to initialize everything.
3113 */
3118 /* Implement the main merge loop
3119 */
3127 /* Jump to the this point in order to terminate the query.
3128 */
3131 /* Reassembly the compound query so that it will be freed correctly
3132 ** by the calling function */
3135 }
3139 /*** TBD: Insert subroutine calls to close cursors on incomplete
3140 **** subqueries ****/
3143 }
3144 #endif
3146 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3148 /* An instance of the SubstContext object describes an substitution edit
3149 ** to be performed on a parse tree.
3150 **
3151 ** All references to columns in table iTable are to be replaced by corresponding
3152 ** expressions in pEList.
3153 */
3162 /* Forward Declarations */
3166 /*
3167 ** Scan through the expression pExpr. Replace every reference to
3168 ** a column in table number iTable with a copy of the iColumn-th
3169 ** entry in pEList. (But leave references to the ROWID column
3170 ** unchanged.)
3171 **
3172 ** This routine is part of the flattening procedure. A subquery
3173 ** whose result set is defined by pEList appears as entry in the
3174 ** FROM clause of a SELECT such that the VDBE cursor assigned to that
3175 ** FORM clause entry is iTable. This routine makes the necessary
3176 ** changes to pExpr so that it refers directly to the source table
3177 ** of the subquery rather the result set of the subquery.
3178 */
3182 ){
3186 ){
3188 }
3195 Expr ifNullRow;
3208 }
3212 }
3216 }
3219 }
3220 }
3224 }
3231 }
3232 }
3234 }
3238 ){
3243 }
3244 }
3249 ){
3266 }
3267 }
3269 }
3272 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3273 /*
3274 ** This routine attempts to flatten subqueries as a performance optimization.
3275 ** This routine returns 1 if it makes changes and 0 if no flattening occurs.
3276 **
3277 ** To understand the concept of flattening, consider the following
3278 ** query:
3279 **
3280 ** SELECT a FROM (SELECT x+y AS a FROM t1 WHERE z<100) WHERE a>5
3281 **
3282 ** The default way of implementing this query is to execute the
3283 ** subquery first and store the results in a temporary table, then
3284 ** run the outer query on that temporary table. This requires two
3285 ** passes over the data. Furthermore, because the temporary table
3286 ** has no indices, the WHERE clause on the outer query cannot be
3287 ** optimized.
3288 **
3289 ** This routine attempts to rewrite queries such as the above into
3290 ** a single flat select, like this:
3291 **
3292 ** SELECT x+y AS a FROM t1 WHERE z<100 AND a>5
3293 **
3294 ** The code generated for this simplification gives the same result
3295 ** but only has to scan the data once. And because indices might
3296 ** exist on the table t1, a complete scan of the data might be
3297 ** avoided.
3298 **
3299 ** Flattening is only attempted if all of the following are true:
3300 **
3301 ** (1) The subquery and the outer query do not both use aggregates.
3302 **
3303 ** (2) The subquery is not an aggregate or (2a) the outer query is not a join
3304 ** and (2b) the outer query does not use subqueries other than the one
3305 ** FROM-clause subquery that is a candidate for flattening. (2b is
3306 ** due to ticket [2f7170d73bf9abf80] from 2015-02-09.)
3307 **
3308 ** (3) The subquery is not the right operand of a LEFT JOIN
3309 ** or (a) the subquery is not itself a join and (b) the FROM clause
3310 ** of the subquery does not contain a virtual table and (c) the
3311 ** outer query is not an aggregate.
3312 **
3313 ** (4) The subquery is not DISTINCT.
3314 **
3315 ** (**) At one point restrictions (4) and (5) defined a subset of DISTINCT
3316 ** sub-queries that were excluded from this optimization. Restriction
3317 ** (4) has since been expanded to exclude all DISTINCT subqueries.
3318 **
3319 ** (6) The subquery does not use aggregates or the outer query is not
3320 ** DISTINCT.
3321 **
3322 ** (7) The subquery has a FROM clause. TODO: For subqueries without
3323 ** A FROM clause, consider adding a FROM clause with the special
3324 ** table sqlite_once that consists of a single row containing a
3325 ** single NULL.
3326 **
3327 ** (8) The subquery does not use LIMIT or the outer query is not a join.
3328 **
3329 ** (9) The subquery does not use LIMIT or the outer query does not use
3330 ** aggregates.
3331 **
3332 ** (**) Restriction (10) was removed from the code on 2005-02-05 but we
3333 ** accidently carried the comment forward until 2014-09-15. Original
3334 ** text: "The subquery does not use aggregates or the outer query
3335 ** does not use LIMIT."
3336 **
3337 ** (11) The subquery and the outer query do not both have ORDER BY clauses.
3338 **
3339 ** (**) Not implemented. Subsumed into restriction (3). Was previously
3340 ** a separate restriction deriving from ticket #350.
3341 **
3342 ** (13) The subquery and outer query do not both use LIMIT.
3343 **
3344 ** (14) The subquery does not use OFFSET.
3345 **
3346 ** (15) The outer query is not part of a compound select or the
3347 ** subquery does not have a LIMIT clause.
3348 ** (See ticket #2339 and ticket [02a8e81d44]).
3349 **
3350 ** (16) The outer query is not an aggregate or the subquery does
3351 ** not contain ORDER BY. (Ticket #2942) This used to not matter
3352 ** until we introduced the group_concat() function.
3353 **
3354 ** (17) The sub-query is not a compound select, or it is a UNION ALL
3355 ** compound clause made up entirely of non-aggregate queries, and
3356 ** the parent query:
3357 **
3358 ** * is not itself part of a compound select,
3359 ** * is not an aggregate or DISTINCT query, and
3360 ** * is not a join
3361 **
3362 ** The parent and sub-query may contain WHERE clauses. Subject to
3363 ** rules (11), (13) and (14), they may also contain ORDER BY,
3364 ** LIMIT and OFFSET clauses. The subquery cannot use any compound
3365 ** operator other than UNION ALL because all the other compound
3366 ** operators have an implied DISTINCT which is disallowed by
3367 ** restriction (4).
3368 **
3369 ** Also, each component of the sub-query must return the same number
3370 ** of result columns. This is actually a requirement for any compound
3371 ** SELECT statement, but all the code here does is make sure that no
3372 ** such (illegal) sub-query is flattened. The caller will detect the
3373 ** syntax error and return a detailed message.
3374 **
3375 ** (18) If the sub-query is a compound select, then all terms of the
3376 ** ORDER by clause of the parent must be simple references to
3377 ** columns of the sub-query.
3378 **
3379 ** (19) The subquery does not use LIMIT or the outer query does not
3380 ** have a WHERE clause.
3381 **
3382 ** (20) If the sub-query is a compound select, then it must not use
3383 ** an ORDER BY clause. Ticket #3773. We could relax this constraint
3384 ** somewhat by saying that the terms of the ORDER BY clause must
3385 ** appear as unmodified result columns in the outer query. But we
3386 ** have other optimizations in mind to deal with that case.
3387 **
3388 ** (21) The subquery does not use LIMIT or the outer query is not
3389 ** DISTINCT. (See ticket [752e1646fc]).
3390 **
3391 ** (22) The subquery is not a recursive CTE.
3392 **
3393 ** (23) The parent is not a recursive CTE, or the sub-query is not a
3394 ** compound query. This restriction is because transforming the
3395 ** parent to a compound query confuses the code that handles
3396 ** recursive queries in multiSelect().
3397 **
3398 ** (24) The subquery is not an aggregate that uses the built-in min() or
3399 ** or max() functions. (Without this restriction, a query like:
3400 ** "SELECT x FROM (SELECT max(y), x FROM t1)" would not necessarily
3401 ** return the value X for which Y was maximal.)
3402 **
3403 **
3404 ** In this routine, the "p" parameter is a pointer to the outer query.
3405 ** The subquery is p->pSrc->a[iFrom]. isAgg is true if the outer query
3406 ** uses aggregates and subqueryIsAgg is true if the subquery uses aggregates.
3407 **
3408 ** If flattening is not attempted, this routine is a no-op and returns 0.
3409 ** If flattening is attempted this routine returns 1.
3410 **
3411 ** All of the expression analysis must occur on both the outer query and
3412 ** the subquery before this routine runs.
3413 */
3420 ){
3435 /* Check to see if flattening is permitted. Return 0 if not.
3436 */
3452 ){
3454 }
3455 }
3459 /* Prior to version 3.1.2, when LIMIT and OFFSET had to be simple constants,
3460 ** not arbitrary expressions, we allowed some combining of LIMIT and OFFSET
3461 ** because they could be computed at compile-time. But when LIMIT and OFFSET
3462 ** became arbitrary expressions, we were forced to add restrictions (13)
3463 ** and (14). */
3468 }
3473 }
3476 }
3479 }
3484 }
3489 }
3492 }
3494 /*
3495 ** If the subquery is the right operand of a LEFT JOIN, then the
3496 ** subquery may not be a join itself. Example of why this is not allowed:
3497 **
3498 ** t1 LEFT OUTER JOIN (t2 JOIN t3)
3499 **
3500 ** If we flatten the above, we would get
3501 **
3502 ** (t1 LEFT OUTER JOIN t2) JOIN t3
3503 **
3504 ** which is not at all the same thing.
3505 **
3506 ** If the subquery is the right operand of a LEFT JOIN, then the outer
3507 ** query cannot be an aggregate. This is an artifact of the way aggregates
3508 ** are processed - there is no mechanism to determine if the LEFT JOIN
3509 ** table should be all-NULL.
3510 **
3511 ** See also tickets #306, #350, and #3300.
3512 */
3517 }
3518 }
3519 #ifdef SQLITE_EXTRA_IFNULLROW
3521 /* Setting isLeftJoin to -1 causes OP_IfNullRow opcodes to be generated for
3522 ** every reference to any result column from subquery in a join, even
3523 ** though they are not necessary. This will stress-test the OP_IfNullRow
3524 ** opcode. */
3526 }
3527 #endif
3529 /* Restriction 17: If the sub-query is a compound SELECT, then it must
3530 ** use only the UNION ALL operator. And none of the simple select queries
3531 ** that make up the compound SELECT are allowed to be aggregate or distinct
3532 ** queries.
3533 */
3537 }
3540 }
3549 ){
3551 }
3553 }
3555 /* Restriction 18. */
3560 }
3561 }
3562 }
3564 /***** If we reach this point, flattening is permitted. *****/
3568 /* Authorize the subquery */
3574 /* If the sub-query is a compound SELECT statement, then (by restrictions
3575 ** 17 and 18 above) it must be a UNION ALL and the parent query must
3576 ** be of the form:
3577 **
3578 ** SELECT <expr-list> FROM (<sub-query>) <where-clause>
3579 **
3580 ** followed by any ORDER BY, LIMIT and/or OFFSET clauses. This block
3581 ** creates N-1 copies of the parent query without any ORDER BY, LIMIT or
3582 ** OFFSET clauses and joins them to the left-hand-side of the original
3583 ** using UNION ALL operators. In this case N is the number of simple
3584 ** select statements in the compound sub-query.
3585 **
3586 ** Example:
3587 **
3588 ** SELECT a+1 FROM (
3589 ** SELECT x FROM tab
3590 ** UNION ALL
3591 ** SELECT y FROM tab
3592 ** UNION ALL
3593 ** SELECT abs(z*2) FROM tab2
3594 ** ) WHERE a!=5 ORDER BY 1
3595 **
3596 ** Transformed into:
3597 **
3598 ** SELECT x+1 FROM tab WHERE x+1!=5
3599 ** UNION ALL
3600 ** SELECT y+1 FROM tab WHERE y+1!=5
3601 ** UNION ALL
3602 ** SELECT abs(z*2)+1 FROM tab2 WHERE abs(z*2)+1!=5
3603 ** ORDER BY 1
3604 **
3605 ** We call this the "compound-subquery flattening".
3606 */
3635 }
3637 }
3639 /* Begin flattening the iFrom-th entry of the FROM clause
3640 ** in the outer query.
3641 */
3644 /* Delete the transient table structure associated with the
3645 ** subquery
3646 */
3655 /* Defer deleting the Table object associated with the
3656 ** subquery until code generation is
3657 ** complete, since there may still exist Expr.pTab entries that
3658 ** refer to the subquery even after flattening. Ticket #3346.
3659 **
3660 ** pSubitem->pTab is always non-NULL by test restrictions and tests above.
3661 */
3670 }
3672 }
3674 /* The following loop runs once for each term in a compound-subquery
3675 ** flattening (as described above). If we are doing a different kind
3676 ** of flattening - a flattening other than a compound-subquery flattening -
3677 ** then this loop only runs once.
3678 **
3679 ** This loop moves all of the FROM elements of the subquery into the
3680 ** the FROM clause of the outer query. Before doing this, remember
3681 ** the cursor number for the original outer query FROM element in
3682 ** iParent. The iParent cursor will never be used. Subsequent code
3683 ** will scan expressions looking for iParent references and replace
3684 ** those references with expressions that resolve to the subquery FROM
3685 ** elements we are now copying in.
3686 */
3703 }
3704 }
3706 /* The subquery uses a single slot of the FROM clause of the outer
3707 ** query. If the subquery has more than one element in its FROM clause,
3708 ** then expand the outer query to make space for it to hold all elements
3709 ** of the subquery.
3710 **
3711 ** Example:
3712 **
3713 ** SELECT * FROM tabA, (SELECT * FROM sub1, sub2), tabB;
3714 **
3715 ** The outer query has 3 slots in its FROM clause. One slot of the
3716 ** outer query (the middle slot) is used by the subquery. The next
3717 ** block of code will expand the outer query FROM clause to 4 slots.
3718 ** The middle slot is expanded to two slots in order to make space
3719 ** for the two elements in the FROM clause of the subquery.
3720 */
3725 }
3726 }
3728 /* Transfer the FROM clause terms from the subquery into the
3729 ** outer query.
3730 */
3737 }
3740 /* Now begin substituting subquery result set expressions for
3741 ** references to the iParent in the outer query.
3742 **
3743 ** Example:
3744 **
3745 ** SELECT a+5, b*10 FROM (SELECT x*3 AS a, y+10 AS b FROM t1) WHERE a>b;
3746 ** \ \_____________ subquery __________/ /
3747 ** \_____________________ outer query ______________________________/
3748 **
3749 ** We look at every expression in the outer query and every place we see
3750 ** "a" we substitute "x*3" and every place we see "b" we substitute "y+10".
3751 */
3753 /* At this point, any non-zero iOrderByCol values indicate that the
3754 ** ORDER BY column expression is identical to the iOrderByCol'th
3755 ** expression returned by SELECT statement pSub. Since these values
3756 ** do not necessarily correspond to columns in SELECT statement pParent,
3757 ** zero them before transfering the ORDER BY clause.
3758 **
3759 ** Not doing this may cause an error if a subsequent call to this
3760 ** function attempts to flatten a compound sub-query into pParent
3761 ** (the only way this can happen is if the compound sub-query is
3762 ** currently part of pSub->pSrc). See ticket [d11a6e908f]. */
3766 }
3771 }
3775 }
3782 );
3787 }
3789 SubstContext x;
3796 }
3798 /* The flattened query is distinct if either the inner or the
3799 ** outer query is distinct.
3800 */
3803 /*
3804 ** SELECT ... FROM (SELECT ... LIMIT a OFFSET b) LIMIT x OFFSET y;
3805 **
3806 ** One is tempted to try to add a and b to combine the limits. But this
3807 ** does not work if either limit is negative.
3808 */
3812 }
3813 }
3815 /* Finially, delete what is left of the subquery and return
3816 ** success.
3817 */
3820 #if SELECTTRACE_ENABLED
3824 }
3825 #endif
3828 }
3833 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3834 /*
3835 ** Make copies of relevant WHERE clause terms of the outer query into
3836 ** the WHERE clause of subquery. Example:
3837 **
3838 ** SELECT * FROM (SELECT a AS x, c-d AS y FROM t1) WHERE x=5 AND y=10;
3839 **
3840 ** Transformed into:
3841 **
3842 ** SELECT * FROM (SELECT a AS x, c-d AS y FROM t1 WHERE a=5 AND c-d=10)
3843 ** WHERE x=5 AND y=10;
3844 **
3845 ** The hope is that the terms added to the inner query will make it more
3846 ** efficient.
3847 **
3848 ** Do not attempt this optimization if:
3849 **
3850 ** (1) The inner query is an aggregate. (In that case, we'd really want
3851 ** to copy the outer WHERE-clause terms onto the HAVING clause of the
3852 ** inner query. But they probably won't help there so do not bother.)
3853 **
3854 ** (2) The inner query is the recursive part of a common table expression.
3855 **
3856 ** (3) The inner query has a LIMIT clause (since the changes to the WHERE
3857 ** close would change the meaning of the LIMIT).
3858 **
3859 ** (4) The inner query is the right operand of a LEFT JOIN. (The caller
3860 ** enforces this restriction since this routine does not have enough
3861 ** information to know.)
3862 **
3863 ** (5) The WHERE clause expression originates in the ON or USING clause
3864 ** of a LEFT JOIN.
3865 **
3866 ** Return 0 if no changes are made and non-zero if one or more WHERE clause
3867 ** terms are duplicated into the subquery.
3868 */
3874 ){
3885 }
3886 }
3889 }
3893 }
3896 nChng++;
3898 SubstContext x;
3908 }
3909 }
3911 }
3914 /*
3915 ** Based on the contents of the AggInfo structure indicated by the first
3916 ** argument, this function checks if the following are true:
3917 **
3918 ** * the query contains just a single aggregate function,
3919 ** * the aggregate function is either min() or max(), and
3920 ** * the argument to the aggregate function is a column value.
3921 **
3922 ** If all of the above are true, then WHERE_ORDERBY_MIN or WHERE_ORDERBY_MAX
3923 ** is returned as appropriate. Also, *ppMinMax is set to point to the
3924 ** list of arguments passed to the aggregate before returning.
3925 **
3926 ** Or, if the conditions above are not met, *ppMinMax is set to 0 and
3927 ** WHERE_ORDERBY_NORMAL is returned.
3928 */
3946 }
3947 }
3948 }
3952 }
3954 /*
3955 ** The select statement passed as the first argument is an aggregate query.
3956 ** The second argument is the associated aggregate-info object. This
3957 ** function tests if the SELECT is of the form:
3958 **
3959 ** SELECT count(*) FROM <tbl>
3960 **
3961 ** where table is a database table, not a sub-select or view. If the query
3962 ** does match this pattern, then a pointer to the Table object representing
3963 ** <tbl> is returned. Otherwise, 0 is returned.
3964 */
3973 ){
3975 }
3987 }
3989 /*
3990 ** If the source-list item passed as an argument was augmented with an
3991 ** INDEXED BY clause, then try to locate the specified index. If there
3992 ** was such a clause and the named index cannot be found, return
3993 ** SQLITE_ERROR and leave an error in pParse. Otherwise, populate
3994 ** pFrom->pIndex and return SQLITE_OK.
3995 */
4004 );
4009 }
4011 }
4013 }
4014 /*
4015 ** Detect compound SELECT statements that use an ORDER BY clause with
4016 ** an alternative collating sequence.
4017 **
4018 ** SELECT ... FROM t1 EXCEPT SELECT ... FROM t2 ORDER BY .. COLLATE ...
4019 **
4020 ** These are rewritten as a subquery:
4021 **
4022 ** SELECT * FROM (SELECT ... FROM t1 EXCEPT SELECT ... FROM t2)
4023 ** ORDER BY ... COLLATE ...
4024 **
4025 ** This transformation is necessary because the multiSelectOrderBy() routine
4026 ** above that generates the code for a compound SELECT with an ORDER BY clause
4027 ** uses a merge algorithm that requires the same collating sequence on the
4028 ** result columns as on the ORDER BY clause. See ticket
4029 ** http://www.sqlite.org/src/info/6709574d2a
4030 **
4031 ** This transformation is only needed for EXCEPT, INTERSECT, and UNION.
4032 ** The UNION ALL operator works fine with multiSelectOrderBy() even when
4033 ** there are COLLATE terms in the ORDER BY.
4034 */
4043 Token dummy;
4052 }
4055 /* If we reach this point, that means the transformation is required. */
4083 }
4085 /*
4086 ** Check to see if the FROM clause term pFrom has table-valued function
4087 ** arguments. If it does, leave an error message in pParse and return
4088 ** non-zero, since pFrom is not allowed to be a table-valued function.
4089 */
4094 }
4096 }
4098 #ifndef SQLITE_OMIT_CTE
4099 /*
4100 ** Argument pWith (which may be NULL) points to a linked list of nested
4101 ** WITH contexts, from inner to outermost. If the table identified by
4102 ** FROM clause element pItem is really a common-table-expression (CTE)
4103 ** then return a pointer to the CTE definition for that table. Otherwise
4104 ** return NULL.
4105 **
4106 ** If a non-NULL value is returned, set *ppContext to point to the With
4107 ** object that the returned CTE belongs to.
4108 */
4113 ){
4123 }
4124 }
4125 }
4126 }
4128 }
4130 /* The code generator maintains a stack of active WITH clauses
4131 ** with the inner-most WITH clause being at the top of the stack.
4132 **
4133 ** This routine pushes the WITH clause passed as the second argument
4134 ** onto the top of the stack. If argument bFree is true, then this
4135 ** WITH clause will never be popped from the stack. In this case it
4136 ** should be freed along with the Parse object. In other cases, when
4137 ** bFree==0, the With object will be freed along with the SELECT
4138 ** statement with which it is associated.
4139 */
4147 }
4148 }
4150 /*
4151 ** This function checks if argument pFrom refers to a CTE declared by
4152 ** a WITH clause on the stack currently maintained by the parser. And,
4153 ** if currently processing a CTE expression, if it is a recursive
4154 ** reference to the current CTE.
4155 **
4156 ** If pFrom falls into either of the two categories above, pFrom->pTab
4157 ** and other fields are populated accordingly. The caller should check
4158 ** (pFrom->pTab!=0) to determine whether or not a successful match
4159 ** was found.
4160 **
4161 ** Whether or not a match is found, SQLITE_OK is returned if no error
4162 ** occurs. If an error does occur, an error message is stored in the
4163 ** parser and some error code other than SQLITE_OK returned.
4164 */
4168 ){
4185 /* If pCte->zCteErr is non-NULL at this point, then this is an illegal
4186 ** recursive reference to CTE pCte. Leave an error in pParse and return
4187 ** early. If pCte->zCteErr is NULL, then this is not a recursive reference.
4188 ** In this case, proceed. */
4192 }
4207 /* Check if this is a recursive CTE. */
4218 ){
4223 }
4224 }
4225 }
4227 /* Only one recursive reference is permitted. */
4231 );
4233 }
4248 }
4257 );
4260 }
4262 }
4270 }
4272 }
4275 }
4278 }
4279 #endif
4281 #ifndef SQLITE_OMIT_CTE
4282 /*
4283 ** If the SELECT passed as the second argument has an associated WITH
4284 ** clause, pop it from the stack stored as part of the Parse object.
4285 **
4286 ** This function is used as the xSelectCallback2() callback by
4287 ** sqlite3SelectExpand() when walking a SELECT tree to resolve table
4288 ** names and other FROM clause elements.
4289 */
4297 }
4298 }
4299 }
4300 #else
4301 #define selectPopWith 0
4302 #endif
4304 /*
4305 ** This routine is a Walker callback for "expanding" a SELECT statement.
4306 ** "Expanding" means to do the following:
4307 **
4308 ** (1) Make sure VDBE cursor numbers have been assigned to every
4309 ** element of the FROM clause.
4310 **
4311 ** (2) Fill in the pTabList->a[].pTab fields in the SrcList that
4312 ** defines FROM clause. When views appear in the FROM clause,
4313 ** fill pTabList->a[].pSelect with a copy of the SELECT statement
4314 ** that implements the view. A copy is made of the view's SELECT
4315 ** statement so that we can freely modify or delete that statement
4316 ** without worrying about messing up the persistent representation
4317 ** of the view.
4318 **
4319 ** (3) Add terms to the WHERE clause to accommodate the NATURAL keyword
4320 ** on joins and the ON and USING clause of joins.
4321 **
4322 ** (4) Scan the list of columns in the result set (pEList) looking
4323 ** for instances of the "*" operator or the TABLE.* operator.
4324 ** If found, expand each "*" to be every column in every table
4325 ** and TABLE.* to be every column in TABLE.
4326 **
4327 */
4341 }
4344 }
4349 }
4351 /* Make sure cursor numbers have been assigned to all entries in
4352 ** the FROM clause of the SELECT statement.
4353 */
4356 /* Look up every table named in the FROM clause of the select. If
4357 ** an entry of the FROM clause is a subquery instead of a table or view,
4358 ** then create a transient table structure to describe the subquery.
4359 */
4365 #ifndef SQLITE_OMIT_CTE
4368 #endif
4370 #ifndef SQLITE_OMIT_SUBQUERY
4372 /* A sub-query in the FROM clause of a SELECT */
4385 #endif
4387 /* An ordinary table or view name in the FROM clause */
4396 }
4400 }
4401 #if !defined(SQLITE_OMIT_VIEW) || !defined (SQLITE_OMIT_VIRTUALTABLE)
4403 i16 nCol;
4412 }
4413 #endif
4414 }
4416 /* Locate the index named by the INDEXED BY clause, if any. */
4419 }
4420 }
4422 /* Process NATURAL keywords, and ON and USING clauses of joins.
4423 */
4426 }
4428 /* For every "*" that occurs in the column list, insert the names of
4429 ** all columns in all tables. And for every TABLE.* insert the names
4430 ** of all columns in TABLE. The parser inserted a special expression
4431 ** with the TK_ASTERISK operator for each "*" that it found in the column
4432 ** list. The following code just has to locate the TK_ASTERISK
4433 ** expressions and expand each one to the list of all columns in
4434 ** all tables.
4435 **
4436 ** The first loop just checks to see if there are any "*" operators
4437 ** that need expanding.
4438 */
4445 }
4447 /*
4448 ** If we get here it means the result set contains one or more "*"
4449 ** operators that need to be expanded. Loop through each expression
4450 ** in the result set and expand them one by one.
4451 */
4464 ){
4465 /* This particular expression does not need to be expanded.
4466 */
4473 }
4476 /* This expression is a "*" or a "TABLE.*" and needs to be
4477 ** expanded. */
4484 }
4493 }
4499 }
4502 }
4512 ){
4514 }
4516 /* If a column is marked as 'hidden', omit it from the expanded
4517 ** result-set list unless the SELECT has the SF_IncludeHidden
4518 ** bit set.
4519 */
4522 ){
4524 }
4530 ){
4531 /* In a NATURAL join, omit the join columns from the
4532 ** table to the right of the join */
4534 }
4536 /* In a join with a USING clause, omit columns in the
4537 ** using clause from the table on the right. */
4539 }
4540 }
4551 }
4555 }
4558 }
4571 }
4573 }
4575 }
4576 }
4582 }
4583 }
4584 }
4585 }
4588 }
4589 #if SQLITE_MAX_COLUMN
4593 }
4594 #endif
4596 }
4598 /*
4599 ** No-op routine for the parse-tree walker.
4600 **
4601 ** When this routine is the Walker.xExprCallback then expression trees
4602 ** are walked without any actions being taken at each node. Presumably,
4603 ** when this routine is used for Walker.xExprCallback then
4604 ** Walker.xSelectCallback is set to do something useful for every
4605 ** subquery in the parser tree.
4606 */
4610 }
4612 /*
4613 ** No-op routine for the parse-tree walker for SELECT statements.
4614 ** subquery in the parser tree.
4615 */
4619 }
4621 #if SQLITE_DEBUG
4622 /*
4623 ** Always assert. This xSelectCallback2 implementation proves that the
4624 ** xSelectCallback2 is never invoked.
4625 */
4629 }
4630 #endif
4631 /*
4632 ** This routine "expands" a SELECT statement and all of its subqueries.
4633 ** For additional information on what it means to "expand" a SELECT
4634 ** statement, see the comment on the selectExpand worker callback above.
4635 **
4636 ** Expanding a SELECT statement is the first step in processing a
4637 ** SELECT statement. The SELECT statement must be expanded before
4638 ** name resolution is performed.
4639 **
4640 ** If anything goes wrong, an error message is written into pParse.
4641 ** The calling function can detect the problem by looking at pParse->nErr
4642 ** and/or pParse->db->mallocFailed.
4643 */
4645 Walker w;
4652 }
4656 }
4659 #ifndef SQLITE_OMIT_SUBQUERY
4660 /*
4661 ** This is a Walker.xSelectCallback callback for the sqlite3SelectTypeInfo()
4662 ** interface.
4663 **
4664 ** For each FROM-clause subquery, add Column.zType and Column.zColl
4665 ** information to the Table structure that represents the result set
4666 ** of that subquery.
4667 **
4668 ** The Table structure that represents the result set was constructed
4669 ** by selectExpander() but the type and collation information was omitted
4670 ** at that point because identifiers had not yet been resolved. This
4671 ** routine is called after identifier resolution.
4672 */
4688 /* A sub-query in the FROM clause of a SELECT */
4693 }
4694 }
4695 }
4696 }
4697 #endif
4700 /*
4701 ** This routine adds datatype and collating sequence information to
4702 ** the Table structures of all FROM-clause subqueries in a
4703 ** SELECT statement.
4704 **
4705 ** Use this routine after name resolution.
4706 */
4708 #ifndef SQLITE_OMIT_SUBQUERY
4709 Walker w;
4715 #endif
4716 }
4719 /*
4720 ** This routine sets up a SELECT statement for processing. The
4721 ** following is accomplished:
4722 **
4723 ** * VDBE Cursor numbers are assigned to all FROM-clause terms.
4724 ** * Ephemeral Table objects are created for all FROM-clause subqueries.
4725 ** * ON and USING clauses are shifted into WHERE statements
4726 ** * Wildcards "*" and "TABLE.*" in result sets are expanded.
4727 ** * Identifiers in expression are matched to tables.
4728 **
4729 ** This routine acts recursively on all subqueries within the SELECT.
4730 */
4735 ){
4746 }
4748 /*
4749 ** Reset the aggregate accumulator.
4750 **
4751 ** The aggregate accumulator is a set of memory cells that hold
4752 ** intermediate results while calculating an aggregate. This
4753 ** routine generates code that stores NULLs in all of those memory
4754 ** cells.
4755 */
4762 #ifdef SQLITE_DEBUG
4763 /* Verify that all AggInfo registers are within the range specified by
4764 ** AggInfo.mnReg..AggInfo.mxReg */
4769 }
4773 }
4774 #endif
4788 }
4789 }
4790 }
4791 }
4793 /*
4794 ** Invoke the OP_AggFinalize opcode for every aggregate function
4795 ** in the AggInfo structure.
4796 */
4806 }
4807 }
4809 /*
4810 ** Update the accumulator memory cells for an aggregate based on
4811 ** the current cursor position.
4812 */
4835 }
4841 }
4849 }
4852 }
4855 }
4864 }
4865 }
4867 /* Before populating the accumulator registers, clear the column cache.
4868 ** Otherwise, if any of the required column values are already present
4869 ** in registers, sqlite3ExprCode() may use OP_SCopy to copy the value
4870 ** to pC->iMem. But by the time the value is used, the original register
4871 ** may have been used, invalidating the underlying buffer holding the
4872 ** text or blob value. See ticket [883034dcb5].
4873 **
4874 ** Another solution would be to change the OP_SCopy used to copy cached
4875 ** values to an OP_Copy.
4876 */
4879 }
4883 }
4888 }
4889 }
4891 /*
4892 ** Add a single OP_Explain instruction to the VDBE to explain a simple
4893 ** count(*) query ("SELECT count(*) FROM pTab").
4894 */
4895 #ifndef SQLITE_OMIT_EXPLAIN
4900 ){
4907 );
4910 );
4911 }
4912 }
4913 #else
4914 # define explainSimpleCount(a,b,c)
4915 #endif
4917 /*
4918 ** Context object for havingToWhereExprCb().
4919 */
4923 };
4925 /*
4926 ** sqlite3WalkExpr() callback used by havingToWhere().
4927 **
4928 ** If the node passed to the callback is a TK_AND node, return
4929 ** WRC_Continue to tell sqlite3WalkExpr() to iterate through child nodes.
4930 **
4931 ** Otherwise, return WRC_Prune. In this case, also check if the
4932 ** sub-expression matches the criteria for being moved to the WHERE
4933 ** clause. If so, add it to the WHERE clause and replace the sub-expression
4934 ** within the HAVING expression with a constant "1".
4935 */
4947 }
4948 }
4950 }
4952 }
4954 /*
4955 ** Transfer eligible terms from the HAVING clause of a query, which is
4956 ** processed after grouping, to the WHERE clause, which is processed before
4957 ** grouping. For example, the query:
4958 **
4959 ** SELECT * FROM <tables> WHERE a=? GROUP BY b HAVING b=? AND c=?
4960 **
4961 ** can be rewritten as:
4962 **
4963 ** SELECT * FROM <tables> WHERE a=? AND b=? GROUP BY b HAVING c=?
4964 **
4965 ** A term of the HAVING expression is eligible for transfer if it consists
4966 ** entirely of constants and expressions that are also GROUP BY terms that
4967 ** use the "BINARY" collation sequence.
4968 */
4973 Expr **ppWhere
4974 ){
4976 Walker sWalker;
4986 }
4988 /*
4989 ** Check to see if the pThis entry of pTabList is a self-join of a prior view.
4990 ** If it is, then return the SrcList_item for the prior view. If it is not,
4991 ** then return 0.
4992 */
4996 ){
5006 ){
5007 /* The view was modified by some other optimization such as
5008 ** pushDownWhereTerms() */
5010 }
5012 }
5014 }
5016 #ifdef SQLITE_COUNTOFVIEW_OPTIMIZATION
5017 /*
5018 ** Attempt to transform a query of the form
5019 **
5020 ** SELECT count(*) FROM (SELECT x FROM t1 UNION ALL SELECT y FROM t2)
5021 **
5022 ** Into this:
5023 **
5024 ** SELECT (SELECT count(*) FROM t1)+(SELECT count(*) FROM t2)
5025 **
5026 ** The transformation only works if all of the following are true:
5027 **
5028 ** * The subquery is a UNION ALL of two or more terms
5029 ** * There is no WHERE or GROUP BY or HAVING clauses on the subqueries
5030 ** * The outer query is a simple count(*)
5031 **
5032 ** Return TRUE if the optimization is undertaken.
5033 */
5056 /* If we reach this point then it is OK to perform the transformation */
5082 }
5084 }
5088 #if SELECTTRACE_ENABLED
5092 }
5093 #endif
5095 }
5098 /*
5099 ** Generate code for the SELECT statement given in the p argument.
5100 **
5101 ** The results are returned according to the SelectDest structure.
5102 ** See comments in sqliteInt.h for further information.
5103 **
5104 ** This routine returns the number of errors. If any errors are
5105 ** encountered, then an appropriate error message is left in
5106 ** pParse->zErrMsg.
5107 **
5108 ** This routine does NOT free the Select structure passed in. The
5109 ** calling function needs to do that.
5110 */
5115 ){
5132 #ifndef SQLITE_OMIT_EXPLAIN
5135 #endif
5140 }
5143 #if SELECTTRACE_ENABLED
5148 }
5149 #endif
5160 /* If ORDER BY makes no difference in the output then neither does
5161 ** DISTINCT so it can be removed too. */
5165 }
5172 }
5175 #if SELECTTRACE_ENABLED
5179 }
5180 #endif
5182 /* Get a pointer the VDBE under construction, allocating a new VDBE if one
5183 ** does not already exist */
5188 }
5190 /* Try to flatten subqueries in the FROM clause up into the main query
5191 */
5192 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
5200 /* Catch mismatch in the declared columns of a view and the number of
5201 ** columns in the SELECT on the RHS */
5206 }
5210 /* This subquery can be absorbed into its parent. */
5214 }
5216 }
5221 }
5222 }
5223 #endif
5225 #ifndef SQLITE_OMIT_COMPOUND_SELECT
5226 /* Handle compound SELECT statements using the separate multiSelect()
5227 ** procedure.
5228 */
5232 #if SELECTTRACE_ENABLED
5235 #endif
5237 }
5238 #endif
5240 /* For each term in the FROM clause, do two things:
5241 ** (1) Authorized unreferenced tables
5242 ** (2) Generate code for all sub-queries
5243 */
5246 SelectDest dest;
5249 /* Issue SQLITE_READ authorizations with a fake column name for any
5250 ** tables that are referenced but from which no values are extracted.
5251 ** Examples of where these kinds of null SQLITE_READ authorizations
5252 ** would occur:
5253 **
5254 ** SELECT count(*) FROM t1; -- SQLITE_READ t1.""
5255 ** SELECT t1.* FROM t1, t2; -- SQLITE_READ t2.""
5256 **
5257 ** The fake column name is an empty string. It is possible for a table to
5258 ** have a column named by the empty string, in which case there is no way to
5259 ** distinguish between an unreferenced table and an actual reference to the
5260 ** "" column. The original design was for the fake column name to be a NULL,
5261 ** which would be unambiguous. But legacy authorization callbacks might
5262 ** assume the column name is non-NULL and segfault. The use of an empty
5263 ** string for the fake column name seems safer.
5264 */
5267 }
5269 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
5270 /* Generate code for all sub-queries in the FROM clause
5271 */
5275 /* Sometimes the code for a subquery will be generated more than
5276 ** once, if the subquery is part of the WHERE clause in a LEFT JOIN,
5277 ** for example. In that case, do not regenerate the code to manifest
5278 ** a view or the co-routine to implement a view. The first instance
5279 ** is sufficient, though the subroutine to manifest the view does need
5280 ** to be invoked again. */
5283 /* The subroutine that manifests the view might be a one-time routine,
5284 ** or it might need to be rerun on each iteration because it
5285 ** encodes a correlated subquery. */
5288 }
5290 }
5292 /* Increment Parse.nHeight by the height of the largest expression
5293 ** tree referred to by this, the parent select. The child select
5294 ** may contain expression trees of at most
5295 ** (SQLITE_MAX_EXPR_DEPTH-Parse.nHeight) height. This is a bit
5296 ** more conservative than necessary, but much easier than enforcing
5297 ** an exact limit.
5298 */
5301 /* Make copies of constant WHERE-clause terms in the outer query down
5302 ** inside the subquery. This can help the subquery to run more efficiently.
5303 */
5306 ){
5307 #if SELECTTRACE_ENABLED
5311 }
5312 #endif
5313 }
5315 /* Generate code to implement the subquery
5316 **
5317 ** The subquery is implemented as a co-routine if all of these are true:
5318 ** (1) The subquery is guaranteed to be the outer loop (so that it
5319 ** does not need to be computed more than once)
5320 ** (2) REMOVED (2017-09-28): The ALL keyword after SELECT is omitted.
5321 ** (3) Co-routines are not disabled using sqlite3_test_control()
5322 ** with SQLITE_TESTCTRL_OPTIMIZATIONS.
5323 **
5324 ** TODO: Are there other reasons beside (1) to use a co-routine
5325 ** implementation?
5326 */
5330 /*** constraint removed: && (p->selFlags & SF_All)==0 (2) */
5332 ){
5333 /* Implement a co-routine that will return a single row of the result
5334 ** set on each invocation.
5335 */
5351 /* Generate a subroutine that will fill an ephemeral table with
5352 ** the content of this subquery. pItem->addrFillSub will point
5353 ** to the address of the generated subroutine. pItem->regReturn
5354 ** is a register allocated to hold the subroutine return address
5355 */
5366 /* If the subquery is not correlated and if we are not inside of
5367 ** a trigger, then we only need to compute the value of the subquery
5368 ** once. */
5373 }
5384 }
5391 }
5394 #endif
5395 }
5397 /* Various elements of the SELECT copied into local variables for
5398 ** convenience */
5405 #if SELECTTRACE_ENABLED
5409 }
5410 #endif
5412 #ifdef SQLITE_COUNTOFVIEW_OPTIMIZATION
5415 ){
5419 }
5420 #endif
5422 /* If the query is DISTINCT with an ORDER BY but is not an aggregate, and
5423 ** if the select-list is the same as the ORDER BY list, then this query
5424 ** can be rewritten as a GROUP BY. In other words, this:
5425 **
5426 ** SELECT DISTINCT xyz FROM ... ORDER BY xyz
5427 **
5428 ** is transformed to:
5429 **
5430 ** SELECT xyz FROM ... GROUP BY xyz ORDER BY xyz
5431 **
5432 ** The second form is preferred as a single index (or temp-table) may be
5433 ** used for both the ORDER BY and DISTINCT processing. As originally
5434 ** written the query must use a temp-table for at least one of the ORDER
5435 ** BY and DISTINCT, and an index or separate temp-table for the other.
5436 */
5439 ){
5442 /* Notice that even thought SF_Distinct has been cleared from p->selFlags,
5443 ** the sDistinct.isTnct is still set. Hence, isTnct represents the
5444 ** original setting of the SF_Distinct flag, not the current setting */
5447 #if SELECTTRACE_ENABLED
5451 }
5452 #endif
5453 }
5455 /* If there is an ORDER BY clause, then create an ephemeral index to
5456 ** do the sorting. But this sorting ephemeral index might end up
5457 ** being unused if the data can be extracted in pre-sorted order.
5458 ** If that is the case, then the OP_OpenEphemeral instruction will be
5459 ** changed to an OP_Noop once we figure out that the sorting index is
5460 ** not needed. The sSort.addrSortIndex variable is used to facilitate
5461 ** that change.
5462 */
5471 );
5474 }
5476 /* If the output is destined for a temporary table, open that table.
5477 */
5480 }
5482 /* Set the limiter.
5483 */
5487 }
5492 }
5494 /* Open an ephemeral index to use for the distinct set.
5495 */
5501 P4_KEYINFO);
5506 }
5509 /* No aggregate functions and no GROUP BY clause */
5514 /* Begin the database scan. */
5520 }
5523 }
5529 }
5530 }
5532 /* If sorting index that was created by a prior OP_OpenEphemeral
5533 ** instruction ended up not being needed, then change the OP_OpenEphemeral
5534 ** into an OP_Noop.
5535 */
5538 }
5540 /* Use the standard inner loop. */
5546 /* End the database scan loop.
5547 */
5550 /* This case when there exist aggregate functions or a GROUP BY clause
5551 ** or both */
5556 ** one row of the input to the aggregator has been
5557 ** processed */
5565 /* Remove any and all aliases between the result set and the
5566 ** GROUP BY clause.
5567 */
5574 }
5577 }
5583 }
5585 /* If there is both a GROUP BY and an ORDER BY clause and they are
5586 ** identical, then it may be possible to disable the ORDER BY clause
5587 ** on the grounds that the GROUP BY will cause elements to come out
5588 ** in the correct order. It also may not - the GROUP BY might use a
5589 ** database index that causes rows to be grouped together as required
5590 ** but not actually sorted. Either way, record the fact that the
5591 ** ORDER BY and GROUP BY clauses are the same by setting the orderByGrp
5592 ** variable. */
5595 }
5597 /* Create a label to jump to when we want to abort the query */
5600 /* Convert TK_COLUMN nodes into TK_AGG_COLUMN and make entries in
5601 ** sAggInfo for all TK_AGG_FUNCTION nodes in expressions of the
5602 ** SELECT statement.
5603 */
5618 }
5620 }
5627 }
5631 /* Processing for aggregates with GROUP BY is very different and
5632 ** much more complex than aggregates without a GROUP BY.
5633 */
5645 /* If there is a GROUP BY clause we might need a sorting index to
5646 ** implement it. Allocate that sorting index now. If it turns out
5647 ** that we do not need it after all, the OP_SorterOpen instruction
5648 ** will be converted into a Noop.
5649 */
5656 /* Initialize memory locations used by GROUP BY aggregate processing
5657 */
5674 /* Begin a loop that will extract all source rows in GROUP BY order.
5675 ** This might involve two separate loops with an OP_Sort in between, or
5676 ** it might be a single loop that uses an index to extract information
5677 ** in the right order to begin with.
5678 */
5682 );
5685 /* The optimizer is able to deliver rows in group by order so
5686 ** we do not have to sort. The OP_OpenEphemeral table will be
5687 ** cancelled later because we still need to use the pKeyInfo
5688 */
5691 /* Rows are coming out in undetermined order. We have to push
5692 ** each row into a sorting index, terminate the first loop,
5693 ** then loop over the sorting index in order to get the output
5694 ** in sorted order
5695 */
5711 nCol++;
5712 j++;
5713 }
5714 }
5725 j++;
5726 }
5727 }
5742 }
5744 /* If the index or temporary table used by the GROUP BY sort
5745 ** will naturally deliver rows in the order required by the ORDER BY
5746 ** clause, cancel the ephemeral table open coded earlier.
5747 **
5748 ** This is an optimization - the correct answer should result regardless.
5749 ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER to
5750 ** disable this optimization for testing purposes. */
5753 ){
5756 }
5758 /* Evaluate the current GROUP BY terms and store in b0, b1, b2...
5759 ** (b0 is memory location iBMem+0, b1 is iBMem+1, and so forth)
5760 ** Then compare the current GROUP BY terms against the GROUP BY terms
5761 ** from the previous row currently stored in a0, a1, a2...
5762 */
5768 }
5775 }
5776 }
5782 /* Generate code that runs whenever the GROUP BY changes.
5783 ** Changes in the GROUP BY are detected by the previous code
5784 ** block. If there were no changes, this block is skipped.
5785 **
5786 ** This code copies current group by terms in b0,b1,b2,...
5787 ** over to a0,a1,a2. It then calls the output subroutine
5788 ** and resets the aggregate accumulator registers in preparation
5789 ** for the next GROUP BY batch.
5790 */
5799 /* Update the aggregate accumulators based on the content of
5800 ** the current row
5801 */
5807 /* End of the loop
5808 */
5815 }
5817 /* Output the final row of result
5818 */
5822 /* Jump over the subroutines
5823 */
5826 /* Generate a subroutine that outputs a single row of the result
5827 ** set. This subroutine first looks at the iUseFlag. If iUseFlag
5828 ** is less than or equal to zero, the subroutine is a no-op. If
5829 ** the processing calls for the query to abort, this subroutine
5830 ** increments the iAbortFlag memory location before returning in
5831 ** order to signal the caller to abort.
5832 */
5851 /* Generate a subroutine that will reset the group-by accumulator
5852 */
5860 #ifndef SQLITE_OMIT_BTREECOUNT
5863 /* If isSimpleCount() returns a pointer to a Table structure, then
5864 ** the SQL statement is of the form:
5865 **
5866 ** SELECT count(*) FROM <tbl>
5867 **
5868 ** where the Table structure returned represents table <tbl>.
5869 **
5870 ** This statement is so common that it is optimized specially. The
5871 ** OP_Count instruction is executed either on the intkey table that
5872 ** contains the data for table <tbl> or on one of its indexes. It
5873 ** is better to execute the op on an index, as indexes are almost
5874 ** always spread across less pages than their corresponding tables.
5875 */
5886 /* Search for the index that has the lowest scan cost.
5887 **
5888 ** (2011-04-15) Do not do a full scan of an unordered index.
5889 **
5890 ** (2013-10-03) Do not count the entries in a partial index.
5891 **
5892 ** In practice the KeyInfo structure will not be used. It is only
5893 ** passed to keep OP_OpenRead happy.
5894 */
5901 ){
5903 }
5904 }
5908 }
5910 /* Open a read-only cursor, execute the OP_Count, close the cursor. */
5914 }
5920 {
5921 /* Check if the query is of one of the following forms:
5922 **
5923 ** SELECT min(x) FROM ...
5924 ** SELECT max(x) FROM ...
5925 **
5926 ** If it is, then ask the code in where.c to attempt to sort results
5927 ** as if there was an "ORDER ON x" or "ORDER ON x DESC" clause.
5928 ** If where.c is able to produce results sorted in this order, then
5929 ** add vdbe code to break out of the processing loop after the
5930 ** first iteration (since the first iteration of the loop is
5931 ** guaranteed to operate on the row with the minimum or maximum
5932 ** value of x, the only row required).
5933 **
5934 ** A special flag must be passed to sqlite3WhereBegin() to slightly
5935 ** modify behavior as follows:
5936 **
5937 ** + If the query is a "SELECT min(x)", then the loop coded by
5938 ** where.c should not iterate over any values with a NULL value
5939 ** for x.
5940 **
5941 ** + The optimizer code in where.c (the thing that decides which
5942 ** index or indices to use) should place a different priority on
5943 ** satisfying the 'ORDER BY' clause than it does in other cases.
5944 ** Refer to code and comments in where.c for details.
5945 */
5953 }
5963 }
5964 }
5966 /* This case runs if the aggregate has no GROUP BY clause. The
5967 ** processing is much simpler since there is only a single row
5968 ** of output.
5969 */
5975 }
5982 }
5985 }
5992 }
5999 }
6001 /* If there is an ORDER BY clause, then we need to sort the results
6002 ** and send them to the callback one by one.
6003 */
6008 }
6010 /* Jump here to skip this query
6011 */
6014 /* The SELECT has been coded. If there is an error in the Parse structure,
6015 ** set the return code to 1. Otherwise 0. */
6018 /* Control jumps to here if an error is encountered above, or upon
6019 ** successful coding of the SELECT.
6020 */
6021 select_end:
6026 #if SELECTTRACE_ENABLED
6029 #endif
6031 }