| blob | 199e13f113609c856c064866cb1f8bfc2aad2b17 |
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;
120 }
123 }
129 #if SELECTTRACE_ENABLED
131 #endif
152 }
155 }
157 #if SELECTTRACE_ENABLED
158 /*
159 ** Set the name of a Select object
160 */
164 }
165 }
166 #endif
169 /*
170 ** Delete the given Select structure and all of its substructures.
171 */
174 }
176 /*
177 ** Return a pointer to the right-most SELECT statement in a compound.
178 */
182 }
184 /*
185 ** Given 1 to 3 identifiers preceding the JOIN keyword, determine the
186 ** type of join. Return an integer constant that expresses that type
187 ** in terms of the following bit values:
188 **
189 ** JT_INNER
190 ** JT_CROSS
191 ** JT_OUTER
192 ** JT_NATURAL
193 ** JT_LEFT
194 ** JT_RIGHT
195 **
196 ** A full outer join is the combination of JT_LEFT and JT_RIGHT.
197 **
198 ** If an illegal or unsupported join type is seen, then still return
199 ** a join type, but put an error in the pParse structure.
200 */
205 /* 0123456789 123456789 123456789 123 */
219 };
231 }
232 }
237 }
238 }
242 ){
254 }
256 }
258 /*
259 ** Return the index of a column in a table. Return -1 if the column
260 ** is not contained in the table.
261 */
266 }
268 }
270 /*
271 ** Search the first N tables in pSrc, from left to right, looking for a
272 ** table that has a column named zCol.
273 **
274 ** When found, set *piTab and *piCol to the table index and column index
275 ** of the matching column and return TRUE.
276 **
277 ** If not found, return FALSE.
278 */
285 ){
296 }
298 }
299 }
301 }
303 /*
304 ** This function is used to add terms implied by JOIN syntax to the
305 ** WHERE clause expression of a SELECT statement. The new term, which
306 ** is ANDed with the existing WHERE clause, is of the form:
307 **
308 ** (tab1.col1 = tab2.col2)
309 **
310 ** where tab1 is the iSrc'th table in SrcList pSrc and tab2 is the
311 ** (iSrc+1)'th. Column col1 is column iColLeft of tab1, and col2 is
312 ** column iColRight of tab2.
313 */
323 ){
343 }
345 }
347 /*
348 ** Set the EP_FromJoin property on all terms of the given expression.
349 ** And set the Expr.iRightJoinTable to iTable for every term in the
350 ** expression.
351 **
352 ** The EP_FromJoin property is used on terms of an expression to tell
353 ** the LEFT OUTER JOIN processing logic that this term is part of the
354 ** join restriction specified in the ON or USING clause and not a part
355 ** of the more general WHERE clause. These terms are moved over to the
356 ** WHERE clause during join processing but we need to remember that they
357 ** originated in the ON or USING clause.
358 **
359 ** The Expr.iRightJoinTable tells the WHERE clause processing that the
360 ** expression depends on table iRightJoinTable even if that table is not
361 ** explicitly mentioned in the expression. That information is needed
362 ** for cases like this:
363 **
364 ** SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.b AND t1.x=5
365 **
366 ** The where clause needs to defer the handling of the t1.x=5
367 ** term until after the t2 loop of the join. In that way, a
368 ** NULL t2 row will be inserted whenever t1.x!=5. If we do not
369 ** defer the handling of t1.x=5, it will be processed immediately
370 ** after the t1 loop and rows with t1.x!=5 will never appear in
371 ** the output, which is incorrect.
372 */
383 }
384 }
387 }
388 }
390 /*
391 ** This routine processes the join information for a SELECT statement.
392 ** ON and USING clauses are converted into extra terms of the WHERE clause.
393 ** NATURAL joins also create extra WHERE clause terms.
394 **
395 ** The terms of a FROM clause are contained in the Select.pSrc structure.
396 ** The left most table is the first entry in Select.pSrc. The right-most
397 ** table is the last entry. The join operator is held in the entry to
398 ** the left. Thus entry 0 contains the join operator for the join between
399 ** entries 0 and 1. Any ON or USING clauses associated with the join are
400 ** also attached to the left entry.
401 **
402 ** This routine returns the number of errors encountered.
403 */
421 /* When the NATURAL keyword is present, add WHERE clause terms for
422 ** every column that the two tables have in common.
423 */
429 }
439 }
440 }
441 }
443 /* Disallow both ON and USING clauses in the same join
444 */
449 }
451 /* Add the ON clause to the end of the WHERE clause, connected by
452 ** an AND operator.
453 */
458 }
460 /* Create extra terms on the WHERE clause for each column named
461 ** in the USING clause. Example: If the two tables to be joined are
462 ** A and B and the USING clause names X, Y, and Z, then add this
463 ** to the WHERE clause: A.X=B.X AND A.Y=B.Y AND A.Z=B.Z
464 ** Report an error if any column mentioned in the USING clause is
465 ** not contained in both tables to be joined.
466 */
479 ){
483 }
486 }
487 }
488 }
490 }
492 /* Forward reference */
498 );
500 /*
501 ** Generate code that will push the record in registers regData
502 ** through regData+nData-1 onto the sorter.
503 */
512 ){
531 }
539 }
542 }
559 }
580 }
584 }
589 }
594 /* Fill the sorter until it contains LIMIT+OFFSET entries. (The iLimit
595 ** register is initialized with value of LIMIT+OFFSET.) After the sorter
596 ** fills up, delete the least entry in the sorter after each insert.
597 ** Thus we never hold more than the LIMIT+OFFSET rows in memory at once */
604 }
607 /* If the inner loop is driven by an index such that values from
608 ** the same iteration of the inner loop are in sorted order, then
609 ** immediately jump to the next iteration of an inner loop if the
610 ** entry from the current iteration does not fit into the top
611 ** LIMIT+OFFSET entries of the sorter. */
616 }
618 }
619 }
621 /*
622 ** Add code to implement the OFFSET
623 */
628 ){
632 }
633 }
635 /*
636 ** Add code that will check to make sure the N registers starting at iMem
637 ** form a distinct entry. iTab is a sorting index that holds previously
638 ** seen combinations of the N values. A new entry is made in iTab
639 ** if the current N values are new.
640 **
641 ** A jump to addrRepeat is made and the N+1 values are popped from the
642 ** stack if the top N elements are not distinct.
643 */
650 ){
660 }
662 /*
663 ** This routine generates the code for the inside of the inner loop
664 ** of a SELECT.
665 **
666 ** If srcTab is negative, then the pEList expressions
667 ** are evaluated in order to get the data for this row. If srcTab is
668 ** zero or more, then data is pulled from srcTab and pEList is used only
669 ** to get number columns and the datatype for each column.
670 */
681 ){
698 }
700 /* Pull the requested columns.
701 */
709 }
713 /* This is an error condition that can result, for example, when a SELECT
714 ** on the right-hand side of an INSERT contains more result columns than
715 ** there are columns in the table on the left. The error will be caught
716 ** and reported later. But we need to make sure enough memory is allocated
717 ** to avoid other spurious errors in the meantime. */
719 }
726 }
728 /* If the destination is an EXISTS(...) expression, the actual
729 ** values returned by the SELECT are not required.
730 */
731 u8 ecelFlags;
736 }
738 }
740 /* If the DISTINCT keyword was present on the SELECT statement
741 ** and this row has been seen before, then do not make this row
742 ** part of the result.
743 */
751 /* Allocate space for the previous row */
755 /* Change the OP_OpenEphemeral coded earlier to an OP_Null
756 ** sets the MEM_Cleared bit on the first register of the
757 ** previous value. This will cause the OP_Ne below to always
758 ** fail on the first iteration of the loop even if the first
759 ** row is all NULLs.
760 */
776 }
779 }
783 }
788 }
793 regResult);
795 }
796 }
799 }
800 }
803 /* In this mode, write each query result to the key of the temporary
804 ** table iParm.
805 */
806 #ifndef SQLITE_OMIT_COMPOUND_SELECT
814 }
816 /* Construct a record from the query result, but instead of
817 ** saving that record, use it as a key to delete elements from
818 ** the temporary table iParm.
819 */
823 }
826 /* Store the result as data using a unique key.
827 */
838 #ifndef SQLITE_OMIT_CTE
840 /* If the destination is DistFifo, then cursor (iParm+1) is open
841 ** on an ephemeral index. If the current row is already present
842 ** in the index, do not write it to the output. If not, add the
843 ** current row to the index and proceed with writing it to the
844 ** output table as well. */
850 }
851 #endif
860 }
863 }
865 #ifndef SQLITE_OMIT_SUBQUERY
866 /* If we are creating a set for an "expr IN (SELECT ...)" construct,
867 ** then there should be a single item on the stack. Write this
868 ** item into the set table with bogus data.
869 */
872 /* At first glance you would think we could optimize out the
873 ** ORDER BY in this case since the order of entries in the set
874 ** does not matter. But there might be a LIMIT clause, in which
875 ** case the order does matter */
886 }
888 }
890 /* If any row exist in the result set, record that fact and abort.
891 */
894 /* The LIMIT clause will terminate the loop for us */
896 }
898 /* If this is a scalar select that is part of an expression, then
899 ** store the results in the appropriate memory cell or array of
900 ** memory cells and break out of the scan loop.
901 */
909 /* The LIMIT clause will jump out of the loop for us */
910 }
912 }
921 nPrefixReg);
927 }
929 }
931 #ifndef SQLITE_OMIT_CTE
932 /* Write the results into a priority queue that is order according to
933 ** pDest->pOrderBy (in pSO). pDest->iSDParm (in iParm) is the cursor for an
934 ** index with pSO->nExpr+2 columns. Build a key using pSO for the first
935 ** pSO->nExpr columns, then make sure all keys are unique by adding a
936 ** final OP_Sequence column. The last column is the record as a blob.
937 */
951 /* If the destination is DistQueue, then cursor (iParm+1) is open
952 ** on a second ephemeral index that holds all values every previously
953 ** added to the queue. */
957 }
962 }
967 }
975 }
980 #if !defined(SQLITE_OMIT_TRIGGER)
981 /* Discard the results. This is used for SELECT statements inside
982 ** the body of a TRIGGER. The purpose of such selects is to call
983 ** user-defined functions that have side effects. We do not care
984 ** about the actual results of the select.
985 */
989 }
990 #endif
991 }
993 /* Jump to the end of the loop if the LIMIT is reached. Except, if
994 ** there is a sorter, in which case the sorter has already limited
995 ** the output for us.
996 */
999 }
1000 }
1002 /*
1003 ** Allocate a KeyInfo object sufficient for an index of N key columns and
1004 ** X extra columns.
1005 */
1019 }
1021 }
1023 /*
1024 ** Deallocate a KeyInfo object
1025 */
1031 }
1032 }
1034 /*
1035 ** Make a new pointer to a KeyInfo object
1036 */
1041 }
1043 }
1045 #ifdef SQLITE_DEBUG
1046 /*
1047 ** Return TRUE if a KeyInfo object can be change. The KeyInfo object
1048 ** can only be changed if this is just a single reference to the object.
1049 **
1050 ** This routine is used only inside of assert() statements.
1051 */
1055 /*
1056 ** Given an expression list, generate a KeyInfo structure that records
1057 ** the collating sequence for each expression in that expression list.
1058 **
1059 ** If the ExprList is an ORDER BY or GROUP BY clause then the resulting
1060 ** KeyInfo structure is appropriate for initializing a virtual index to
1061 ** implement that clause. If the ExprList is the result set of a SELECT
1062 ** then the KeyInfo structure is appropriate for initializing a virtual
1063 ** index to implement a DISTINCT test.
1064 **
1065 ** Space to hold the KeyInfo structure is obtained from malloc. The calling
1066 ** function is responsible for seeing that this structure is eventually
1067 ** freed.
1068 */
1074 ){
1091 }
1092 }
1094 }
1096 /*
1097 ** Name of the connection operator, used for error messages.
1098 */
1106 }
1108 }
1110 #ifndef SQLITE_OMIT_EXPLAIN
1111 /*
1112 ** Unless an "EXPLAIN QUERY PLAN" command is being processed, this function
1113 ** is a no-op. Otherwise, it adds a single row of output to the EQP result,
1114 ** where the caption is of the form:
1115 **
1116 ** "USE TEMP B-TREE FOR xxx"
1117 **
1118 ** where xxx is one of "DISTINCT", "ORDER BY" or "GROUP BY". Exactly which
1119 ** is determined by the zUsage argument.
1120 */
1126 }
1127 }
1129 /*
1130 ** Assign expression b to lvalue a. A second, no-op, version of this macro
1131 ** is provided when SQLITE_OMIT_EXPLAIN is defined. This allows the code
1132 ** in sqlite3Select() to assign values to structure member variables that
1133 ** only exist if SQLITE_OMIT_EXPLAIN is not defined without polluting the
1134 ** code with #ifndef directives.
1135 */
1136 # define explainSetInteger(a, b) a = b
1138 #else
1139 /* No-op versions of the explainXXX() functions and macros. */
1140 # define explainTempTable(y,z)
1141 # define explainSetInteger(y,z)
1142 #endif
1144 #if !defined(SQLITE_OMIT_EXPLAIN) && !defined(SQLITE_OMIT_COMPOUND_SELECT)
1145 /*
1146 ** Unless an "EXPLAIN QUERY PLAN" command is being processed, this function
1147 ** is a no-op. Otherwise, it adds a single row of output to the EQP result,
1148 ** where the caption is of one of the two forms:
1149 **
1150 ** "COMPOSITE SUBQUERIES iSub1 and iSub2 (op)"
1151 ** "COMPOSITE SUBQUERIES iSub1 and iSub2 USING TEMP B-TREE (op)"
1152 **
1153 ** where iSub1 and iSub2 are the integers passed as the corresponding
1154 ** function parameters, and op is the text representation of the parameter
1155 ** of the same name. The parameter "op" must be one of TK_UNION, TK_EXCEPT,
1156 ** TK_INTERSECT or TK_ALL. The first form is used if argument bUseTmp is
1157 ** false, or the second form if it is true.
1158 */
1165 ){
1172 );
1174 }
1175 }
1176 #else
1177 /* No-op versions of the explainXXX() functions and macros. */
1178 # define explainComposite(v,w,x,y,z)
1179 #endif
1181 /*
1182 ** If the inner loop was generated using a non-null pOrderBy argument,
1183 ** then the results were placed in a sorter. After the loop is terminated
1184 ** we need to run the sorter and output the results. The following
1185 ** routine generates the code needed to do that.
1186 */
1193 ){
1210 #ifdef SQLITE_ENABLE_EXPLAIN_COMMENTS
1212 #endif
1219 }
1229 }
1236 }
1249 }
1253 }
1260 }
1261 #ifndef SQLITE_OMIT_SUBQUERY
1269 }
1271 /* The LIMIT clause will terminate the loop for us */
1273 }
1274 #endif
1284 }
1286 }
1287 }
1293 }
1295 }
1296 /* The bottom of the loop
1297 */
1303 }
1306 }
1308 /*
1309 ** Return a pointer to a string containing the 'declaration type' of the
1310 ** expression pExpr. The string may be treated as static by the caller.
1311 **
1312 ** Also try to estimate the size of the returned value and return that
1313 ** result in *pEstWidth.
1314 **
1315 ** The declaration type is the exact datatype definition extracted from the
1316 ** original CREATE TABLE statement if the expression is a column. The
1317 ** declaration type for a ROWID field is INTEGER. Exactly when an expression
1318 ** is considered a column can be complex in the presence of subqueries. The
1319 ** result-set expression in all of the following SELECT statements is
1320 ** considered a column by this function.
1321 **
1322 ** SELECT col FROM tbl;
1323 ** SELECT (SELECT col FROM tbl;
1324 ** SELECT (SELECT col FROM tbl);
1325 ** SELECT abc FROM (SELECT col AS abc FROM tbl);
1326 **
1327 ** The declaration type for any expression other than a column is NULL.
1328 **
1329 ** This routine has either 3 or 6 parameters depending on whether or not
1330 ** the SQLITE_ENABLE_COLUMN_METADATA compile-time option is used.
1331 */
1332 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1333 # define columnType(A,B,C,D,E,F) columnTypeImpl(A,B,C,D,E,F)
1335 # define columnType(A,B,C,D,E,F) columnTypeImpl(A,B,F)
1336 #endif
1340 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1344 #endif
1345 u8 *pEstWidth
1346 ){
1350 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1354 #endif
1361 /* The expression is a column. Locate the table the column is being
1362 ** extracted from in NameContext.pSrcList. This table may be real
1363 ** database table or a subquery.
1364 */
1378 }
1379 }
1382 /* At one time, code such as "SELECT new.x" within a trigger would
1383 ** cause this condition to run. Since then, we have restructured how
1384 ** trigger code is generated and so this condition is no longer
1385 ** possible. However, it can still be true for statements like
1386 ** the following:
1387 **
1388 ** CREATE TABLE t1(col INTEGER);
1389 ** SELECT (SELECT t1.col) FROM FROM t1;
1390 **
1391 ** when columnType() is called on the expression "t1.col" in the
1392 ** sub-select. In this case, set the column type to NULL, even
1393 ** though it should really be "INTEGER".
1394 **
1395 ** This is not a problem, as the column type of "t1.col" is never
1396 ** used. When columnType() is called on the expression
1397 ** "(SELECT t1.col)", the correct type is returned (see the TK_SELECT
1398 ** branch below. */
1400 }
1404 /* The "table" is actually a sub-select or a view in the FROM clause
1405 ** of the SELECT statement. Return the declaration type and origin
1406 ** data for the result-set column of the sub-select.
1407 */
1409 /* If iCol is less than zero, then the expression requests the
1410 ** rowid of the sub-select or view. This expression is legal (see
1411 ** test case misc2.2.2) - it always evaluates to NULL.
1412 **
1413 ** The ALWAYS() is because iCol>=pS->pEList->nExpr will have been
1414 ** caught already by name resolution.
1415 */
1416 NameContext sNC;
1422 }
1424 /* A real table */
1428 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1436 }
1441 }
1442 #else
1448 }
1449 #endif
1450 }
1452 }
1453 #ifndef SQLITE_OMIT_SUBQUERY
1455 /* The expression is a sub-select. Return the declaration type and
1456 ** origin info for the single column in the result set of the SELECT
1457 ** statement.
1458 */
1459 NameContext sNC;
1468 }
1469 #endif
1470 }
1472 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1478 }
1479 #endif
1482 }
1484 /*
1485 ** Generate code that will tell the VDBE the declaration types of columns
1486 ** in the result set.
1487 */
1492 ){
1493 #ifndef SQLITE_OMIT_DECLTYPE
1496 NameContext sNC;
1502 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1508 /* The vdbe must make its own copy of the column-type and other
1509 ** column specific strings, in case the schema is reset before this
1510 ** virtual machine is deleted.
1511 */
1515 #else
1517 #endif
1519 }
1521 }
1523 /*
1524 ** Generate code that will tell the VDBE the names of columns
1525 ** in the result set. This information is used to provide the
1526 ** azCol[] values in the callback.
1527 */
1532 ){
1538 #ifndef SQLITE_OMIT_EXPLAIN
1539 /* If this is an EXPLAIN, skip this step */
1542 }
1543 #endif
1565 }
1574 }
1584 }
1589 }
1590 }
1592 }
1594 /*
1595 ** Given an expression list (which is really the list of expressions
1596 ** that form the result set of a SELECT statement) compute appropriate
1597 ** column names for a table that would hold the expression list.
1598 **
1599 ** All column names will be unique.
1600 **
1601 ** Only the column names are computed. Column.zType, Column.zColl,
1602 ** and other fields of Column are zeroed.
1603 **
1604 ** Return SQLITE_OK on success. If a memory allocation error occurs,
1605 ** store NULL in *paCol and 0 in *pnCol and return SQLITE_NOMEM.
1606 */
1612 ){
1631 }
1637 /* Get an appropriate name for the column
1638 */
1641 /* If the column contains an "AS <name>" phrase, use <name> as the name */
1648 }
1650 /* For columns use the column name name */
1659 /* Use the original text of the column expression as its name */
1661 }
1662 }
1665 /* Make sure the column name is unique. If the name is not unique,
1666 ** append an integer to the name so that it becomes unique.
1667 */
1674 }
1677 }
1682 }
1683 }
1688 }
1693 }
1695 }
1697 /*
1698 ** Add type and collation information to a column list based on
1699 ** a SELECT statement.
1700 **
1701 ** The column list presumably came from selectColumnNamesFromExprList().
1702 ** The column list has only names, not types or collations. This
1703 ** routine goes through and adds the types and collations.
1704 **
1705 ** This routine requires that all identifiers in the SELECT
1706 ** statement be resolved.
1707 */
1712 ){
1714 NameContext sNC;
1742 }
1743 }
1748 }
1749 }
1751 }
1753 /*
1754 ** Given a SELECT statement, generate a Table structure that describes
1755 ** the result set of that SELECT.
1756 */
1772 }
1773 /* The sqlite3ResultSetOfSelect() is only used n contexts where lookaside
1774 ** is disabled */
1785 }
1787 }
1789 /*
1790 ** Get a VDBE for the given parser context. Create a new one if necessary.
1791 ** If an error occurs, return NULL and leave a message in pParse.
1792 */
1798 ){
1800 }
1802 }
1806 }
1809 /*
1810 ** Compute the iLimit and iOffset fields of the SELECT based on the
1811 ** pLimit and pOffset expressions. pLimit and pOffset hold the expressions
1812 ** that appear in the original SQL statement after the LIMIT and OFFSET
1813 ** keywords. Or NULL if those keywords are omitted. iLimit and iOffset
1814 ** are the integer memory register numbers for counters used to compute
1815 ** the limit and offset. If there is no limit and/or offset, then
1816 ** iLimit and iOffset are negative.
1817 **
1818 ** This routine changes the values of iLimit and iOffset only if
1819 ** a limit or offset is defined by pLimit and pOffset. iLimit and
1820 ** iOffset should have been preset to appropriate default values (zero)
1821 ** prior to calling this routine.
1822 **
1823 ** The iOffset register (if it exists) is initialized to the value
1824 ** of the OFFSET. The iLimit register is initialized to LIMIT. Register
1825 ** iOffset+1 is initialized to LIMIT+OFFSET.
1826 **
1827 ** Only if pLimit!=0 or pOffset!=0 do the limit registers get
1828 ** redefined. The UNION ALL operator uses this property to force
1829 ** the reuse of the same limit and offset registers across multiple
1830 ** SELECT statements.
1831 */
1839 /*
1840 ** "LIMIT -1" always shows all rows. There is some
1841 ** controversy about what the correct behavior should be.
1842 ** The current implementation interprets "LIMIT 0" to mean
1843 ** no rows.
1844 */
1859 }
1865 }
1874 }
1875 }
1876 }
1878 #ifndef SQLITE_OMIT_COMPOUND_SELECT
1879 /*
1880 ** Return the appropriate collating sequence for the iCol-th column of
1881 ** the result set for the compound-select statement "p". Return NULL if
1882 ** the column has no default collating sequence.
1883 **
1884 ** The collating sequence for the compound select is taken from the
1885 ** left-most term of the select that has a collating sequence.
1886 */
1893 }
1895 /* iCol must be less than p->pEList->nExpr. Otherwise an error would
1896 ** have been thrown during name resolution and we would not have gotten
1897 ** this far */
1900 }
1902 }
1904 /*
1905 ** The select statement passed as the second parameter is a compound SELECT
1906 ** with an ORDER BY clause. This function allocates and returns a KeyInfo
1907 ** structure suitable for implementing the ORDER BY.
1908 **
1909 ** Space to hold the KeyInfo structure is obtained from malloc. The calling
1910 ** function is responsible for ensuring that this structure is eventually
1911 ** freed.
1912 */
1932 }
1936 }
1937 }
1940 }
1942 #ifndef SQLITE_OMIT_CTE
1943 /*
1944 ** This routine generates VDBE code to compute the content of a WITH RECURSIVE
1945 ** query of the form:
1946 **
1947 ** <recursive-table> AS (<setup-query> UNION [ALL] <recursive-query>)
1948 ** \___________/ \_______________/
1949 ** p->pPrior p
1950 **
1951 **
1952 ** There is exactly one reference to the recursive-table in the FROM clause
1953 ** of recursive-query, marked with the SrcList->a[].fg.isRecursive flag.
1954 **
1955 ** The setup-query runs once to generate an initial set of rows that go
1956 ** into a Queue table. Rows are extracted from the Queue table one by
1957 ** one. Each row extracted from Queue is output to pDest. Then the single
1958 ** extracted row (now in the iCurrent table) becomes the content of the
1959 ** recursive-table for a recursive-query run. The output of the recursive-query
1960 ** is added back into the Queue table. Then another row is extracted from Queue
1961 ** and the iteration continues until the Queue table is empty.
1962 **
1963 ** If the compound query operator is UNION then no duplicate rows are ever
1964 ** inserted into the Queue table. The iDistinct table keeps a copy of all rows
1965 ** that have ever been inserted into Queue and causes duplicates to be
1966 ** discarded. If the operator is UNION ALL, then duplicates are allowed.
1967 **
1968 ** If the query has an ORDER BY, then entries in the Queue table are kept in
1969 ** ORDER BY order and the first entry is extracted for each cycle. Without
1970 ** an ORDER BY, the Queue table is just a FIFO.
1971 **
1972 ** If a LIMIT clause is provided, then the iteration stops after LIMIT rows
1973 ** have been output to pDest. A LIMIT of zero means to output no rows and a
1974 ** negative LIMIT means to output all rows. If there is also an OFFSET clause
1975 ** with a positive value, then the first OFFSET outputs are discarded rather
1976 ** than being sent to pDest. The LIMIT count does not begin until after OFFSET
1977 ** rows have been skipped.
1978 */
1983 ){
2002 /* Obtain authorization to do a recursive query */
2005 /* Process the LIMIT and OFFSET clauses, if they exist */
2016 /* Locate the cursor number of the Current table */
2021 }
2022 }
2024 /* Allocate cursors numbers for Queue and Distinct. The cursor number for
2025 ** the Distinct table must be exactly one greater than Queue in order
2026 ** for the SRT_DistFifo and SRT_DistQueue destinations to work. */
2033 }
2036 /* Allocate cursors for Current, Queue, and Distinct. */
2046 }
2051 }
2053 /* Detach the ORDER BY clause from the compound SELECT */
2056 /* Store the results of the setup-query in Queue. */
2062 /* Find the next row in the Queue and output that row */
2065 /* Transfer the next row in Queue over to Current */
2071 }
2074 /* Output the single row in Current */
2082 }
2085 /* Execute the recursive SELECT taking the single row in Current as
2086 ** the value for the recursive-table. Store the results in the Queue.
2087 */
2095 }
2097 /* Keep running the loop until the Queue is empty */
2101 end_of_recursive_query:
2107 }
2110 /* Forward references */
2115 );
2117 /*
2118 ** Handle the special case of a compound-select that originates from a
2119 ** VALUES clause. By handling this as a special case, we avoid deep
2120 ** recursion, and thus do not need to enforce the SQLITE_LIMIT_COMPOUND_SELECT
2121 ** on a VALUES clause.
2122 **
2123 ** Because the Select object originates from a VALUES clause:
2124 ** (1) It has no LIMIT or OFFSET
2125 ** (2) All terms are UNION ALL
2126 ** (3) There is no ORDER BY clause
2127 */
2132 ){
2146 nRow++;
2156 }
2158 }
2160 /*
2161 ** This routine is called to process a compound query form from
2162 ** two or more separate queries using UNION, UNION ALL, EXCEPT, or
2163 ** INTERSECT
2164 **
2165 ** "p" points to the right-most of the two queries. the query on the
2166 ** left is p->pPrior. The left query could also be a compound query
2167 ** in which case this routine will be called recursively.
2168 **
2169 ** The results of the total query are to be written into a destination
2170 ** of type eDest with parameter iParm.
2171 **
2172 ** Example 1: Consider a three-way compound SQL statement.
2173 **
2174 ** SELECT a FROM t1 UNION SELECT b FROM t2 UNION SELECT c FROM t3
2175 **
2176 ** This statement is parsed up as follows:
2177 **
2178 ** SELECT c FROM t3
2179 ** |
2180 ** `-----> SELECT b FROM t2
2181 ** |
2182 ** `------> SELECT a FROM t1
2183 **
2184 ** The arrows in the diagram above represent the Select.pPrior pointer.
2185 ** So if this routine is called with p equal to the t3 query, then
2186 ** pPrior will be the t2 query. p->op will be TK_UNION in this case.
2187 **
2188 ** Notice that because of the way SQLite parses compound SELECTs, the
2189 ** individual selects always group from left to right.
2190 */
2195 ){
2202 #ifndef SQLITE_OMIT_EXPLAIN
2205 #endif
2207 /* Make sure there is no ORDER BY or LIMIT clause on prior SELECTs. Only
2208 ** the last (right-most) SELECT in the series may have an ORDER BY or LIMIT.
2209 */
2220 }
2226 }
2231 /* Create the destination temporary table if necessary
2232 */
2237 }
2239 /* Special handling for a compound-select that originates as a VALUES clause.
2240 */
2244 }
2246 /* Make sure all SELECTs in the statement have the same number of elements
2247 ** in their result sets.
2248 */
2252 #ifndef SQLITE_OMIT_CTE
2256 #endif
2258 /* Compound SELECTs that have an ORDER BY clause are handled separately.
2259 */
2264 /* Generate code for the left and right SELECT statements.
2265 */
2281 }
2291 }
2292 }
2302 ){
2304 }
2307 }
2309 }
2317 SelectDest uniondest;
2323 /* We can reuse a temporary table generated by a SELECT to our
2324 ** right.
2325 */
2330 /* We will need to create our own temporary table to hold the
2331 ** intermediate results.
2332 */
2340 }
2342 /* Code the SELECT statements to our left
2343 */
2350 }
2352 /* Code the current SELECT statement
2353 */
2359 }
2369 /* Query flattening in sqlite3Select() might refill p->pOrderBy.
2370 ** Be sure to delete p->pOrderBy, therefore, to avoid a memory leak. */
2377 }
2384 /* Convert the data in the temporary table into whatever form
2385 ** it is that we currently need.
2386 */
2395 }
2407 }
2409 }
2415 SelectDest intersectdest;
2418 /* INTERSECT is different from the others since it requires
2419 ** two temporary tables. Hence it has its own case. Begin
2420 ** by allocating the tables we will need.
2421 */
2432 /* Code the SELECTs to our left into temporary table "tab1".
2433 */
2439 }
2441 /* Code the current SELECT into temporary table "tab2"
2442 */
2462 /* Generate code to take the intersection of the two temporary
2463 ** tables.
2464 */
2470 }
2487 }
2488 }
2492 /* Compute collating sequences used by
2493 ** temporary tables needed to implement the compound select.
2494 ** Attach the KeyInfo structure to all temporary tables.
2495 **
2496 ** This section is run by the right-most SELECT statement only.
2497 ** SELECT statements to the left always skip this part. The right-most
2498 ** SELECT might also skip this part if it has no ORDER BY clause and
2499 ** no temp tables are required.
2500 */
2514 }
2519 }
2520 }
2526 /* If [0] is unused then [1] is also unused. So we can
2527 ** always safely abort as soon as the first unused slot is found */
2530 }
2533 P4_KEYINFO);
2535 }
2536 }
2538 }
2540 multi_select_end:
2545 }
2548 /*
2549 ** Error message for when two or more terms of a compound select have different
2550 ** size result sets.
2551 */
2558 }
2559 }
2561 /*
2562 ** Code an output subroutine for a coroutine implementation of a
2563 ** SELECT statment.
2564 **
2565 ** The data to be output is contained in pIn->iSdst. There are
2566 ** pIn->nSdst columns to be output. pDest is where the output should
2567 ** be sent.
2568 **
2569 ** regReturn is the number of the register holding the subroutine
2570 ** return address.
2571 **
2572 ** If regPrev>0 then it is the first register in a vector that
2573 ** records the previous output. mem[regPrev] is a flag that is false
2574 ** if there has been no previous output. If regPrev>0 then code is
2575 ** generated to suppress duplicates. pKeyInfo is used for comparing
2576 ** keys.
2577 **
2578 ** If the LIMIT found in p->iLimit is reached, jump immediately to
2579 ** iBreak.
2580 */
2590 ){
2598 /* Suppress duplicates for UNION, EXCEPT, and INTERSECT
2599 */
2609 }
2612 /* Suppress the first OFFSET entries if there is an OFFSET clause
2613 */
2619 /* Store the result as data using a unique key.
2620 */
2631 }
2633 #ifndef SQLITE_OMIT_SUBQUERY
2634 /* If we are creating a set for an "expr IN (SELECT ...)".
2635 */
2646 }
2648 /* If this is a scalar select that is part of an expression, then
2649 ** store the results in the appropriate memory cell and break out
2650 ** of the scan loop.
2651 */
2655 /* The LIMIT clause will jump out of the loop for us */
2657 }
2660 /* The results are stored in a sequence of registers
2661 ** starting at pDest->iSdst. Then the co-routine yields.
2662 */
2667 }
2671 }
2673 /* If none of the above, then the result destination must be
2674 ** SRT_Output. This routine is never called with any other
2675 ** destination other than the ones handled above or SRT_Output.
2676 **
2677 ** For SRT_Output, results are stored in a sequence of registers.
2678 ** Then the OP_ResultRow opcode is used to cause sqlite3_step() to
2679 ** return the next row of result.
2680 */
2686 }
2687 }
2689 /* Jump to the end of the loop if the LIMIT is reached.
2690 */
2693 }
2695 /* Generate the subroutine return
2696 */
2701 }
2703 /*
2704 ** Alternative compound select code generator for cases when there
2705 ** is an ORDER BY clause.
2706 **
2707 ** We assume a query of the following form:
2708 **
2709 ** <selectA> <operator> <selectB> ORDER BY <orderbylist>
2710 **
2711 ** <operator> is one of UNION ALL, UNION, EXCEPT, or INTERSECT. The idea
2712 ** is to code both <selectA> and <selectB> with the ORDER BY clause as
2713 ** co-routines. Then run the co-routines in parallel and merge the results
2714 ** into the output. In addition to the two coroutines (called selectA and
2715 ** selectB) there are 7 subroutines:
2716 **
2717 ** outA: Move the output of the selectA coroutine into the output
2718 ** of the compound query.
2719 **
2720 ** outB: Move the output of the selectB coroutine into the output
2721 ** of the compound query. (Only generated for UNION and
2722 ** UNION ALL. EXCEPT and INSERTSECT never output a row that
2723 ** appears only in B.)
2724 **
2725 ** AltB: Called when there is data from both coroutines and A<B.
2726 **
2727 ** AeqB: Called when there is data from both coroutines and A==B.
2728 **
2729 ** AgtB: Called when there is data from both coroutines and A>B.
2730 **
2731 ** EofA: Called when data is exhausted from selectA.
2732 **
2733 ** EofB: Called when data is exhausted from selectB.
2734 **
2735 ** The implementation of the latter five subroutines depend on which
2736 ** <operator> is used:
2737 **
2738 **
2739 ** UNION ALL UNION EXCEPT INTERSECT
2740 ** ------------- ----------------- -------------- -----------------
2741 ** AltB: outA, nextA outA, nextA outA, nextA nextA
2742 **
2743 ** AeqB: outA, nextA nextA nextA outA, nextA
2744 **
2745 ** AgtB: outB, nextB outB, nextB nextB nextB
2746 **
2747 ** EofA: outB, nextB outB, nextB halt halt
2748 **
2749 ** EofB: outA, nextA outA, nextA outA, nextA halt
2750 **
2751 ** In the AltB, AeqB, and AgtB subroutines, an EOF on A following nextA
2752 ** causes an immediate jump to EofA and an EOF on B following nextB causes
2753 ** an immediate jump to EofB. Within EofA and EofB, and EOF on entry or
2754 ** following nextX causes a jump to the end of the select processing.
2755 **
2756 ** Duplicate removal in the UNION, EXCEPT, and INTERSECT cases is handled
2757 ** within the output subroutine. The regPrev register set holds the previously
2758 ** output value. A comparison is made against this value and the output
2759 ** is skipped if the next results would be the same as the previous.
2760 **
2761 ** The implementation plan is to implement the two coroutines and seven
2762 ** subroutines first, then put the control logic at the bottom. Like this:
2763 **
2764 ** goto Init
2765 ** coA: coroutine for left query (A)
2766 ** coB: coroutine for right query (B)
2767 ** outA: output one row of A
2768 ** outB: output one row of B (UNION and UNION ALL only)
2769 ** EofA: ...
2770 ** EofB: ...
2771 ** AltB: ...
2772 ** AeqB: ...
2773 ** AgtB: ...
2774 ** Init: initialize coroutine registers
2775 ** yield coA
2776 ** if eof(A) goto EofA
2777 ** yield coB
2778 ** if eof(B) goto EofB
2779 ** Cmpr: Compare A, B
2780 ** Jump AltB, AeqB, AgtB
2781 ** End: ...
2782 **
2783 ** We call AltB, AeqB, AgtB, EofA, and EofB "subroutines" but they are not
2784 ** actually called using Gosub and they do not Return. EofA and EofB loop
2785 ** until all data is exhausted then jump to the "end" labe. AltB, AeqB,
2786 ** and AgtB jump to either L2 or to one of EofA or EofB.
2787 */
2788 #ifndef SQLITE_OMIT_COMPOUND_SELECT
2793 ){
2828 #ifndef SQLITE_OMIT_EXPLAIN
2831 #endif
2842 /* Patch up the ORDER BY clause
2843 */
2851 /* For operators other than UNION ALL we have to make sure that
2852 ** the ORDER BY clause covers every term of the result set. Add
2853 ** terms to the ORDER BY clause as necessary.
2854 */
2861 }
2869 }
2870 }
2871 }
2873 /* Compute the comparison permutation and keyinfo that is used with
2874 ** the permutation used to determine if the next
2875 ** row of results comes from selectA or selectB. Also add explicit
2876 ** collations to the ORDER BY clause terms so that when the subqueries
2877 ** to the right and the left are evaluated, they use the correct
2878 ** collation.
2879 */
2888 }
2892 }
2894 /* Reattach the ORDER BY clause to the query.
2895 */
2899 /* Allocate a range of temporary registers and the KeyInfo needed
2900 ** for the logic that removes duplicate result rows when the
2901 ** operator is UNION, EXCEPT, or INTERSECT (but not UNION ALL).
2902 */
2917 }
2918 }
2919 }
2921 /* Separate the left and the right query from one another
2922 */
2928 }
2930 /* Compute the limit registers */
2936 regLimitA);
2940 }
2953 /* Generate a coroutine to evaluate the SELECT statement to the
2954 ** left of the compound operator - the "A" select.
2955 */
2965 /* Generate a coroutine to evaluate the SELECT statement on
2966 ** the right - the "B" select
2967 */
2981 /* Generate a subroutine that outputs the current row of the A
2982 ** select as the next output row of the compound select.
2983 */
2989 /* Generate a subroutine that outputs the current row of the B
2990 ** select as the next output row of the compound select.
2991 */
2997 }
3000 /* Generate a subroutine to run when the results from select A
3001 ** are exhausted and only data in select B remains.
3002 */
3012 }
3014 /* Generate a subroutine to run when the results from select B
3015 ** are exhausted and only data in select A remains.
3016 */
3025 }
3027 /* Generate code to handle the case of A<B
3028 */
3034 /* Generate code to handle the case of A==B
3035 */
3040 addrAltB++;
3043 addrAeqB =
3046 }
3048 /* Generate code to handle the case of A>B
3049 */
3054 }
3058 /* This code runs once to initialize everything.
3059 */
3064 /* Implement the main merge loop
3065 */
3073 /* Jump to the this point in order to terminate the query.
3074 */
3077 /* Set the number of output columns
3078 */
3083 }
3085 /* Reassembly the compound query so that it will be freed correctly
3086 ** by the calling function */
3089 }
3093 /*** TBD: Insert subroutine calls to close cursors on incomplete
3094 **** subqueries ****/
3097 }
3098 #endif
3100 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3101 /* Forward Declarations */
3105 /*
3106 ** Scan through the expression pExpr. Replace every reference to
3107 ** a column in table number iTable with a copy of the iColumn-th
3108 ** entry in pEList. (But leave references to the ROWID column
3109 ** unchanged.)
3110 **
3111 ** This routine is part of the flattening procedure. A subquery
3112 ** whose result set is defined by pEList appears as entry in the
3113 ** FROM clause of a SELECT such that the VDBE cursor assigned to that
3114 ** FORM clause entry is iTable. This routine make the necessary
3115 ** changes to pExpr so that it refers directly to the source table
3116 ** of the subquery rather the result set of the subquery.
3117 */
3123 ){
3135 }
3143 }
3144 }
3146 }
3152 ){
3157 }
3158 }
3165 ){
3182 }
3183 }
3185 }
3188 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3189 /*
3190 ** This routine attempts to flatten subqueries as a performance optimization.
3191 ** This routine returns 1 if it makes changes and 0 if no flattening occurs.
3192 **
3193 ** To understand the concept of flattening, consider the following
3194 ** query:
3195 **
3196 ** SELECT a FROM (SELECT x+y AS a FROM t1 WHERE z<100) WHERE a>5
3197 **
3198 ** The default way of implementing this query is to execute the
3199 ** subquery first and store the results in a temporary table, then
3200 ** run the outer query on that temporary table. This requires two
3201 ** passes over the data. Furthermore, because the temporary table
3202 ** has no indices, the WHERE clause on the outer query cannot be
3203 ** optimized.
3204 **
3205 ** This routine attempts to rewrite queries such as the above into
3206 ** a single flat select, like this:
3207 **
3208 ** SELECT x+y AS a FROM t1 WHERE z<100 AND a>5
3209 **
3210 ** The code generated for this simplification gives the same result
3211 ** but only has to scan the data once. And because indices might
3212 ** exist on the table t1, a complete scan of the data might be
3213 ** avoided.
3214 **
3215 ** Flattening is only attempted if all of the following are true:
3216 **
3217 ** (1) The subquery and the outer query do not both use aggregates.
3218 **
3219 ** (2) The subquery is not an aggregate or (2a) the outer query is not a join
3220 ** and (2b) the outer query does not use subqueries other than the one
3221 ** FROM-clause subquery that is a candidate for flattening. (2b is
3222 ** due to ticket [2f7170d73bf9abf80] from 2015-02-09.)
3223 **
3224 ** (3) The subquery is not the right operand of a left outer join
3225 ** (Originally ticket #306. Strengthened by ticket #3300)
3226 **
3227 ** (4) The subquery is not DISTINCT.
3228 **
3229 ** (**) At one point restrictions (4) and (5) defined a subset of DISTINCT
3230 ** sub-queries that were excluded from this optimization. Restriction
3231 ** (4) has since been expanded to exclude all DISTINCT subqueries.
3232 **
3233 ** (6) The subquery does not use aggregates or the outer query is not
3234 ** DISTINCT.
3235 **
3236 ** (7) The subquery has a FROM clause. TODO: For subqueries without
3237 ** A FROM clause, consider adding a FROM close with the special
3238 ** table sqlite_once that consists of a single row containing a
3239 ** single NULL.
3240 **
3241 ** (8) The subquery does not use LIMIT or the outer query is not a join.
3242 **
3243 ** (9) The subquery does not use LIMIT or the outer query does not use
3244 ** aggregates.
3245 **
3246 ** (**) Restriction (10) was removed from the code on 2005-02-05 but we
3247 ** accidently carried the comment forward until 2014-09-15. Original
3248 ** text: "The subquery does not use aggregates or the outer query
3249 ** does not use LIMIT."
3250 **
3251 ** (11) The subquery and the outer query do not both have ORDER BY clauses.
3252 **
3253 ** (**) Not implemented. Subsumed into restriction (3). Was previously
3254 ** a separate restriction deriving from ticket #350.
3255 **
3256 ** (13) The subquery and outer query do not both use LIMIT.
3257 **
3258 ** (14) The subquery does not use OFFSET.
3259 **
3260 ** (15) The outer query is not part of a compound select or the
3261 ** subquery does not have a LIMIT clause.
3262 ** (See ticket #2339 and ticket [02a8e81d44]).
3263 **
3264 ** (16) The outer query is not an aggregate or the subquery does
3265 ** not contain ORDER BY. (Ticket #2942) This used to not matter
3266 ** until we introduced the group_concat() function.
3267 **
3268 ** (17) The sub-query is not a compound select, or it is a UNION ALL
3269 ** compound clause made up entirely of non-aggregate queries, and
3270 ** the parent query:
3271 **
3272 ** * is not itself part of a compound select,
3273 ** * is not an aggregate or DISTINCT query, and
3274 ** * is not a join
3275 **
3276 ** The parent and sub-query may contain WHERE clauses. Subject to
3277 ** rules (11), (13) and (14), they may also contain ORDER BY,
3278 ** LIMIT and OFFSET clauses. The subquery cannot use any compound
3279 ** operator other than UNION ALL because all the other compound
3280 ** operators have an implied DISTINCT which is disallowed by
3281 ** restriction (4).
3282 **
3283 ** Also, each component of the sub-query must return the same number
3284 ** of result columns. This is actually a requirement for any compound
3285 ** SELECT statement, but all the code here does is make sure that no
3286 ** such (illegal) sub-query is flattened. The caller will detect the
3287 ** syntax error and return a detailed message.
3288 **
3289 ** (18) If the sub-query is a compound select, then all terms of the
3290 ** ORDER by clause of the parent must be simple references to
3291 ** columns of the sub-query.
3292 **
3293 ** (19) The subquery does not use LIMIT or the outer query does not
3294 ** have a WHERE clause.
3295 **
3296 ** (20) If the sub-query is a compound select, then it must not use
3297 ** an ORDER BY clause. Ticket #3773. We could relax this constraint
3298 ** somewhat by saying that the terms of the ORDER BY clause must
3299 ** appear as unmodified result columns in the outer query. But we
3300 ** have other optimizations in mind to deal with that case.
3301 **
3302 ** (21) The subquery does not use LIMIT or the outer query is not
3303 ** DISTINCT. (See ticket [752e1646fc]).
3304 **
3305 ** (22) The subquery is not a recursive CTE.
3306 **
3307 ** (23) The parent is not a recursive CTE, or the sub-query is not a
3308 ** compound query. This restriction is because transforming the
3309 ** parent to a compound query confuses the code that handles
3310 ** recursive queries in multiSelect().
3311 **
3312 ** (24) The subquery is not an aggregate that uses the built-in min() or
3313 ** or max() functions. (Without this restriction, a query like:
3314 ** "SELECT x FROM (SELECT max(y), x FROM t1)" would not necessarily
3315 ** return the value X for which Y was maximal.)
3316 **
3317 **
3318 ** In this routine, the "p" parameter is a pointer to the outer query.
3319 ** The subquery is p->pSrc->a[iFrom]. isAgg is true if the outer query
3320 ** uses aggregates and subqueryIsAgg is true if the subquery uses aggregates.
3321 **
3322 ** If flattening is not attempted, this routine is a no-op and returns 0.
3323 ** If flattening is attempted this routine returns 1.
3324 **
3325 ** All of the expression analysis must occur on both the outer query and
3326 ** the subquery before this routine runs.
3327 */
3334 ){
3348 /* Check to see if flattening is permitted. Return 0 if not.
3349 */
3365 ){
3367 }
3368 }
3372 /* Prior to version 3.1.2, when LIMIT and OFFSET had to be simple constants,
3373 ** not arbitrary expressions, we allowed some combining of LIMIT and OFFSET
3374 ** because they could be computed at compile-time. But when LIMIT and OFFSET
3375 ** became arbitrary expressions, we were forced to add restrictions (13)
3376 ** and (14). */
3381 }
3386 }
3389 }
3392 }
3397 }
3402 }
3405 }
3407 /* OBSOLETE COMMENT 1:
3408 ** Restriction 3: If the subquery is a join, make sure the subquery is
3409 ** not used as the right operand of an outer join. Examples of why this
3410 ** is not allowed:
3411 **
3412 ** t1 LEFT OUTER JOIN (t2 JOIN t3)
3413 **
3414 ** If we flatten the above, we would get
3415 **
3416 ** (t1 LEFT OUTER JOIN t2) JOIN t3
3417 **
3418 ** which is not at all the same thing.
3419 **
3420 ** OBSOLETE COMMENT 2:
3421 ** Restriction 12: If the subquery is the right operand of a left outer
3422 ** join, make sure the subquery has no WHERE clause.
3423 ** An examples of why this is not allowed:
3424 **
3425 ** t1 LEFT OUTER JOIN (SELECT * FROM t2 WHERE t2.x>0)
3426 **
3427 ** If we flatten the above, we would get
3428 **
3429 ** (t1 LEFT OUTER JOIN t2) WHERE t2.x>0
3430 **
3431 ** But the t2.x>0 test will always fail on a NULL row of t2, which
3432 ** effectively converts the OUTER JOIN into an INNER JOIN.
3433 **
3434 ** THIS OVERRIDES OBSOLETE COMMENTS 1 AND 2 ABOVE:
3435 ** Ticket #3300 shows that flattening the right term of a LEFT JOIN
3436 ** is fraught with danger. Best to avoid the whole thing. If the
3437 ** subquery is the right term of a LEFT JOIN, then do not flatten.
3438 */
3441 }
3443 /* Restriction 17: If the sub-query is a compound SELECT, then it must
3444 ** use only the UNION ALL operator. And none of the simple select queries
3445 ** that make up the compound SELECT are allowed to be aggregate or distinct
3446 ** queries.
3447 */
3451 }
3454 }
3463 ){
3465 }
3467 }
3469 /* Restriction 18. */
3474 }
3475 }
3476 }
3478 /***** If we reach this point, flattening is permitted. *****/
3482 /* Authorize the subquery */
3488 /* If the sub-query is a compound SELECT statement, then (by restrictions
3489 ** 17 and 18 above) it must be a UNION ALL and the parent query must
3490 ** be of the form:
3491 **
3492 ** SELECT <expr-list> FROM (<sub-query>) <where-clause>
3493 **
3494 ** followed by any ORDER BY, LIMIT and/or OFFSET clauses. This block
3495 ** creates N-1 copies of the parent query without any ORDER BY, LIMIT or
3496 ** OFFSET clauses and joins them to the left-hand-side of the original
3497 ** using UNION ALL operators. In this case N is the number of simple
3498 ** select statements in the compound sub-query.
3499 **
3500 ** Example:
3501 **
3502 ** SELECT a+1 FROM (
3503 ** SELECT x FROM tab
3504 ** UNION ALL
3505 ** SELECT y FROM tab
3506 ** UNION ALL
3507 ** SELECT abs(z*2) FROM tab2
3508 ** ) WHERE a!=5 ORDER BY 1
3509 **
3510 ** Transformed into:
3511 **
3512 ** SELECT x+1 FROM tab WHERE x+1!=5
3513 ** UNION ALL
3514 ** SELECT y+1 FROM tab WHERE y+1!=5
3515 ** UNION ALL
3516 ** SELECT abs(z*2)+1 FROM tab2 WHERE abs(z*2)+1!=5
3517 ** ORDER BY 1
3518 **
3519 ** We call this the "compound-subquery flattening".
3520 */
3549 }
3551 }
3553 /* Begin flattening the iFrom-th entry of the FROM clause
3554 ** in the outer query.
3555 */
3558 /* Delete the transient table structure associated with the
3559 ** subquery
3560 */
3569 /* Defer deleting the Table object associated with the
3570 ** subquery until code generation is
3571 ** complete, since there may still exist Expr.pTab entries that
3572 ** refer to the subquery even after flattening. Ticket #3346.
3573 **
3574 ** pSubitem->pTab is always non-NULL by test restrictions and tests above.
3575 */
3584 }
3586 }
3588 /* The following loop runs once for each term in a compound-subquery
3589 ** flattening (as described above). If we are doing a different kind
3590 ** of flattening - a flattening other than a compound-subquery flattening -
3591 ** then this loop only runs once.
3592 **
3593 ** This loop moves all of the FROM elements of the subquery into the
3594 ** the FROM clause of the outer query. Before doing this, remember
3595 ** the cursor number for the original outer query FROM element in
3596 ** iParent. The iParent cursor will never be used. Subsequent code
3597 ** will scan expressions looking for iParent references and replace
3598 ** those references with expressions that resolve to the subquery FROM
3599 ** elements we are now copying in.
3600 */
3617 }
3618 }
3620 /* The subquery uses a single slot of the FROM clause of the outer
3621 ** query. If the subquery has more than one element in its FROM clause,
3622 ** then expand the outer query to make space for it to hold all elements
3623 ** of the subquery.
3624 **
3625 ** Example:
3626 **
3627 ** SELECT * FROM tabA, (SELECT * FROM sub1, sub2), tabB;
3628 **
3629 ** The outer query has 3 slots in its FROM clause. One slot of the
3630 ** outer query (the middle slot) is used by the subquery. The next
3631 ** block of code will expand the outer query FROM clause to 4 slots.
3632 ** The middle slot is expanded to two slots in order to make space
3633 ** for the two elements in the FROM clause of the subquery.
3634 */
3639 }
3640 }
3642 /* Transfer the FROM clause terms from the subquery into the
3643 ** outer query.
3644 */
3650 }
3653 /* Now begin substituting subquery result set expressions for
3654 ** references to the iParent in the outer query.
3655 **
3656 ** Example:
3657 **
3658 ** SELECT a+5, b*10 FROM (SELECT x*3 AS a, y+10 AS b FROM t1) WHERE a>b;
3659 ** \ \_____________ subquery __________/ /
3660 ** \_____________________ outer query ______________________________/
3661 **
3662 ** We look at every expression in the outer query and every place we see
3663 ** "a" we substitute "x*3" and every place we see "b" we substitute "y+10".
3664 */
3671 }
3672 }
3674 /* At this point, any non-zero iOrderByCol values indicate that the
3675 ** ORDER BY column expression is identical to the iOrderByCol'th
3676 ** expression returned by SELECT statement pSub. Since these values
3677 ** do not necessarily correspond to columns in SELECT statement pParent,
3678 ** zero them before transfering the ORDER BY clause.
3679 **
3680 ** Not doing this may cause an error if a subsequent call to this
3681 ** function attempts to flatten a compound sub-query into pParent
3682 ** (the only way this can happen is if the compound sub-query is
3683 ** currently part of pSub->pSrc). See ticket [d11a6e908f]. */
3687 }
3692 }
3700 );
3705 }
3708 /* The flattened query is distinct if either the inner or the
3709 ** outer query is distinct.
3710 */
3713 /*
3714 ** SELECT ... FROM (SELECT ... LIMIT a OFFSET b) LIMIT x OFFSET y;
3715 **
3716 ** One is tempted to try to add a and b to combine the limits. But this
3717 ** does not work if either limit is negative.
3718 */
3722 }
3723 }
3725 /* Finially, delete what is left of the subquery and return
3726 ** success.
3727 */
3730 #if SELECTTRACE_ENABLED
3734 }
3735 #endif
3738 }
3743 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3744 /*
3745 ** Make copies of relevant WHERE clause terms of the outer query into
3746 ** the WHERE clause of subquery. Example:
3747 **
3748 ** SELECT * FROM (SELECT a AS x, c-d AS y FROM t1) WHERE x=5 AND y=10;
3749 **
3750 ** Transformed into:
3751 **
3752 ** SELECT * FROM (SELECT a AS x, c-d AS y FROM t1 WHERE a=5 AND c-d=10)
3753 ** WHERE x=5 AND y=10;
3754 **
3755 ** The hope is that the terms added to the inner query will make it more
3756 ** efficient.
3757 **
3758 ** Do not attempt this optimization if:
3759 **
3760 ** (1) The inner query is an aggregate. (In that case, we'd really want
3761 ** to copy the outer WHERE-clause terms onto the HAVING clause of the
3762 ** inner query. But they probably won't help there so do not bother.)
3763 **
3764 ** (2) The inner query is the recursive part of a common table expression.
3765 **
3766 ** (3) The inner query has a LIMIT clause (since the changes to the WHERE
3767 ** close would change the meaning of the LIMIT).
3768 **
3769 ** (4) The inner query is the right operand of a LEFT JOIN. (The caller
3770 ** enforces this restriction since this routine does not have enough
3771 ** information to know.)
3772 **
3773 ** (5) The WHERE clause expression originates in the ON or USING clause
3774 ** of a LEFT JOIN.
3775 **
3776 ** Return 0 if no changes are made and non-zero if one or more WHERE clause
3777 ** terms are duplicated into the subquery.
3778 */
3784 ){
3795 }
3796 }
3799 }
3803 }
3806 nChng++;
3812 }
3813 }
3815 }
3818 /*
3819 ** Based on the contents of the AggInfo structure indicated by the first
3820 ** argument, this function checks if the following are true:
3821 **
3822 ** * the query contains just a single aggregate function,
3823 ** * the aggregate function is either min() or max(), and
3824 ** * the argument to the aggregate function is a column value.
3825 **
3826 ** If all of the above are true, then WHERE_ORDERBY_MIN or WHERE_ORDERBY_MAX
3827 ** is returned as appropriate. Also, *ppMinMax is set to point to the
3828 ** list of arguments passed to the aggregate before returning.
3829 **
3830 ** Or, if the conditions above are not met, *ppMinMax is set to 0 and
3831 ** WHERE_ORDERBY_NORMAL is returned.
3832 */
3850 }
3851 }
3852 }
3856 }
3858 /*
3859 ** The select statement passed as the first argument is an aggregate query.
3860 ** The second argument is the associated aggregate-info object. This
3861 ** function tests if the SELECT is of the form:
3862 **
3863 ** SELECT count(*) FROM <tbl>
3864 **
3865 ** where table is a database table, not a sub-select or view. If the query
3866 ** does match this pattern, then a pointer to the Table object representing
3867 ** <tbl> is returned. Otherwise, 0 is returned.
3868 */
3877 ){
3879 }
3891 }
3893 /*
3894 ** If the source-list item passed as an argument was augmented with an
3895 ** INDEXED BY clause, then try to locate the specified index. If there
3896 ** was such a clause and the named index cannot be found, return
3897 ** SQLITE_ERROR and leave an error in pParse. Otherwise, populate
3898 ** pFrom->pIndex and return SQLITE_OK.
3899 */
3908 );
3913 }
3915 }
3917 }
3918 /*
3919 ** Detect compound SELECT statements that use an ORDER BY clause with
3920 ** an alternative collating sequence.
3921 **
3922 ** SELECT ... FROM t1 EXCEPT SELECT ... FROM t2 ORDER BY .. COLLATE ...
3923 **
3924 ** These are rewritten as a subquery:
3925 **
3926 ** SELECT * FROM (SELECT ... FROM t1 EXCEPT SELECT ... FROM t2)
3927 ** ORDER BY ... COLLATE ...
3928 **
3929 ** This transformation is necessary because the multiSelectOrderBy() routine
3930 ** above that generates the code for a compound SELECT with an ORDER BY clause
3931 ** uses a merge algorithm that requires the same collating sequence on the
3932 ** result columns as on the ORDER BY clause. See ticket
3933 ** http://www.sqlite.org/src/info/6709574d2a
3934 **
3935 ** This transformation is only needed for EXCEPT, INTERSECT, and UNION.
3936 ** The UNION ALL operator works fine with multiSelectOrderBy() even when
3937 ** there are COLLATE terms in the ORDER BY.
3938 */
3947 Token dummy;
3956 }
3959 /* If we reach this point, that means the transformation is required. */
3987 }
3989 /*
3990 ** Check to see if the FROM clause term pFrom has table-valued function
3991 ** arguments. If it does, leave an error message in pParse and return
3992 ** non-zero, since pFrom is not allowed to be a table-valued function.
3993 */
3998 }
4000 }
4002 #ifndef SQLITE_OMIT_CTE
4003 /*
4004 ** Argument pWith (which may be NULL) points to a linked list of nested
4005 ** WITH contexts, from inner to outermost. If the table identified by
4006 ** FROM clause element pItem is really a common-table-expression (CTE)
4007 ** then return a pointer to the CTE definition for that table. Otherwise
4008 ** return NULL.
4009 **
4010 ** If a non-NULL value is returned, set *ppContext to point to the With
4011 ** object that the returned CTE belongs to.
4012 */
4017 ){
4027 }
4028 }
4029 }
4030 }
4032 }
4034 /* The code generator maintains a stack of active WITH clauses
4035 ** with the inner-most WITH clause being at the top of the stack.
4036 **
4037 ** This routine pushes the WITH clause passed as the second argument
4038 ** onto the top of the stack. If argument bFree is true, then this
4039 ** WITH clause will never be popped from the stack. In this case it
4040 ** should be freed along with the Parse object. In other cases, when
4041 ** bFree==0, the With object will be freed along with the SELECT
4042 ** statement with which it is associated.
4043 */
4051 }
4052 }
4054 /*
4055 ** This function checks if argument pFrom refers to a CTE declared by
4056 ** a WITH clause on the stack currently maintained by the parser. And,
4057 ** if currently processing a CTE expression, if it is a recursive
4058 ** reference to the current CTE.
4059 **
4060 ** If pFrom falls into either of the two categories above, pFrom->pTab
4061 ** and other fields are populated accordingly. The caller should check
4062 ** (pFrom->pTab!=0) to determine whether or not a successful match
4063 ** was found.
4064 **
4065 ** Whether or not a match is found, SQLITE_OK is returned if no error
4066 ** occurs. If an error does occur, an error message is stored in the
4067 ** parser and some error code other than SQLITE_OK returned.
4068 */
4072 ){
4089 /* If pCte->zCteErr is non-NULL at this point, then this is an illegal
4090 ** recursive reference to CTE pCte. Leave an error in pParse and return
4091 ** early. If pCte->zCteErr is NULL, then this is not a recursive reference.
4092 ** In this case, proceed. */
4096 }
4111 /* Check if this is a recursive CTE. */
4122 ){
4127 }
4128 }
4129 }
4131 /* Only one recursive reference is permitted. */
4135 );
4137 }
4152 );
4155 }
4157 }
4165 }
4167 }
4170 }
4173 }
4174 #endif
4176 #ifndef SQLITE_OMIT_CTE
4177 /*
4178 ** If the SELECT passed as the second argument has an associated WITH
4179 ** clause, pop it from the stack stored as part of the Parse object.
4180 **
4181 ** This function is used as the xSelectCallback2() callback by
4182 ** sqlite3SelectExpand() when walking a SELECT tree to resolve table
4183 ** names and other FROM clause elements.
4184 */
4191 }
4192 }
4193 #else
4194 #define selectPopWith 0
4195 #endif
4197 /*
4198 ** This routine is a Walker callback for "expanding" a SELECT statement.
4199 ** "Expanding" means to do the following:
4200 **
4201 ** (1) Make sure VDBE cursor numbers have been assigned to every
4202 ** element of the FROM clause.
4203 **
4204 ** (2) Fill in the pTabList->a[].pTab fields in the SrcList that
4205 ** defines FROM clause. When views appear in the FROM clause,
4206 ** fill pTabList->a[].pSelect with a copy of the SELECT statement
4207 ** that implements the view. A copy is made of the view's SELECT
4208 ** statement so that we can freely modify or delete that statement
4209 ** without worrying about messing up the persistent representation
4210 ** of the view.
4211 **
4212 ** (3) Add terms to the WHERE clause to accommodate the NATURAL keyword
4213 ** on joins and the ON and USING clause of joins.
4214 **
4215 ** (4) Scan the list of columns in the result set (pEList) looking
4216 ** for instances of the "*" operator or the TABLE.* operator.
4217 ** If found, expand each "*" to be every column in every table
4218 ** and TABLE.* to be every column in TABLE.
4219 **
4220 */
4234 }
4237 }
4242 }
4244 /* Make sure cursor numbers have been assigned to all entries in
4245 ** the FROM clause of the SELECT statement.
4246 */
4249 /* Look up every table named in the FROM clause of the select. If
4250 ** an entry of the FROM clause is a subquery instead of a table or view,
4251 ** then create a transient table structure to describe the subquery.
4252 */
4258 #ifndef SQLITE_OMIT_CTE
4261 #endif
4263 #ifndef SQLITE_OMIT_SUBQUERY
4265 /* A sub-query in the FROM clause of a SELECT */
4278 #endif
4280 /* An ordinary table or view name in the FROM clause */
4289 }
4293 }
4294 #if !defined(SQLITE_OMIT_VIEW) || !defined (SQLITE_OMIT_VIRTUALTABLE)
4296 i16 nCol;
4305 }
4306 #endif
4307 }
4309 /* Locate the index named by the INDEXED BY clause, if any. */
4312 }
4313 }
4315 /* Process NATURAL keywords, and ON and USING clauses of joins.
4316 */
4319 }
4321 /* For every "*" that occurs in the column list, insert the names of
4322 ** all columns in all tables. And for every TABLE.* insert the names
4323 ** of all columns in TABLE. The parser inserted a special expression
4324 ** with the TK_ASTERISK operator for each "*" that it found in the column
4325 ** list. The following code just has to locate the TK_ASTERISK
4326 ** expressions and expand each one to the list of all columns in
4327 ** all tables.
4328 **
4329 ** The first loop just checks to see if there are any "*" operators
4330 ** that need expanding.
4331 */
4338 }
4340 /*
4341 ** If we get here it means the result set contains one or more "*"
4342 ** operators that need to be expanded. Loop through each expression
4343 ** in the result set and expand them one by one.
4344 */
4357 ){
4358 /* This particular expression does not need to be expanded.
4359 */
4366 }
4369 /* This expression is a "*" or a "TABLE.*" and needs to be
4370 ** expanded. */
4377 }
4386 }
4392 }
4395 }
4405 ){
4407 }
4409 /* If a column is marked as 'hidden', omit it from the expanded
4410 ** result-set list unless the SELECT has the SF_IncludeHidden
4411 ** bit set.
4412 */
4415 ){
4417 }
4423 ){
4424 /* In a NATURAL join, omit the join columns from the
4425 ** table to the right of the join */
4427 }
4429 /* In a join with a USING clause, omit columns in the
4430 ** using clause from the table on the right. */
4432 }
4433 }
4444 }
4448 }
4451 }
4464 }
4466 }
4468 }
4469 }
4475 }
4476 }
4477 }
4478 }
4481 }
4482 #if SQLITE_MAX_COLUMN
4486 }
4487 #endif
4489 }
4491 /*
4492 ** No-op routine for the parse-tree walker.
4493 **
4494 ** When this routine is the Walker.xExprCallback then expression trees
4495 ** are walked without any actions being taken at each node. Presumably,
4496 ** when this routine is used for Walker.xExprCallback then
4497 ** Walker.xSelectCallback is set to do something useful for every
4498 ** subquery in the parser tree.
4499 */
4503 }
4505 /*
4506 ** This routine "expands" a SELECT statement and all of its subqueries.
4507 ** For additional information on what it means to "expand" a SELECT
4508 ** statement, see the comment on the selectExpand worker callback above.
4509 **
4510 ** Expanding a SELECT statement is the first step in processing a
4511 ** SELECT statement. The SELECT statement must be expanded before
4512 ** name resolution is performed.
4513 **
4514 ** If anything goes wrong, an error message is written into pParse.
4515 ** The calling function can detect the problem by looking at pParse->nErr
4516 ** and/or pParse->db->mallocFailed.
4517 */
4519 Walker w;
4526 }
4530 }
4532 }
4535 #ifndef SQLITE_OMIT_SUBQUERY
4536 /*
4537 ** This is a Walker.xSelectCallback callback for the sqlite3SelectTypeInfo()
4538 ** interface.
4539 **
4540 ** For each FROM-clause subquery, add Column.zType and Column.zColl
4541 ** information to the Table structure that represents the result set
4542 ** of that subquery.
4543 **
4544 ** The Table structure that represents the result set was constructed
4545 ** by selectExpander() but the type and collation information was omitted
4546 ** at that point because identifiers had not yet been resolved. This
4547 ** routine is called after identifier resolution.
4548 */
4564 /* A sub-query in the FROM clause of a SELECT */
4569 }
4570 }
4571 }
4572 }
4573 #endif
4576 /*
4577 ** This routine adds datatype and collating sequence information to
4578 ** the Table structures of all FROM-clause subqueries in a
4579 ** SELECT statement.
4580 **
4581 ** Use this routine after name resolution.
4582 */
4584 #ifndef SQLITE_OMIT_SUBQUERY
4585 Walker w;
4591 #endif
4592 }
4595 /*
4596 ** This routine sets up a SELECT statement for processing. The
4597 ** following is accomplished:
4598 **
4599 ** * VDBE Cursor numbers are assigned to all FROM-clause terms.
4600 ** * Ephemeral Table objects are created for all FROM-clause subqueries.
4601 ** * ON and USING clauses are shifted into WHERE statements
4602 ** * Wildcards "*" and "TABLE.*" in result sets are expanded.
4603 ** * Identifiers in expression are matched to tables.
4604 **
4605 ** This routine acts recursively on all subqueries within the SELECT.
4606 */
4611 ){
4622 }
4624 /*
4625 ** Reset the aggregate accumulator.
4626 **
4627 ** The aggregate accumulator is a set of memory cells that hold
4628 ** intermediate results while calculating an aggregate. This
4629 ** routine generates code that stores NULLs in all of those memory
4630 ** cells.
4631 */
4638 #ifdef SQLITE_DEBUG
4639 /* Verify that all AggInfo registers are within the range specified by
4640 ** AggInfo.mnReg..AggInfo.mxReg */
4645 }
4649 }
4650 #endif
4664 }
4665 }
4666 }
4667 }
4669 /*
4670 ** Invoke the OP_AggFinalize opcode for every aggregate function
4671 ** in the AggInfo structure.
4672 */
4682 }
4683 }
4685 /*
4686 ** Update the accumulator memory cells for an aggregate based on
4687 ** the current cursor position.
4688 */
4711 }
4717 }
4725 }
4728 }
4731 }
4740 }
4741 }
4743 /* Before populating the accumulator registers, clear the column cache.
4744 ** Otherwise, if any of the required column values are already present
4745 ** in registers, sqlite3ExprCode() may use OP_SCopy to copy the value
4746 ** to pC->iMem. But by the time the value is used, the original register
4747 ** may have been used, invalidating the underlying buffer holding the
4748 ** text or blob value. See ticket [883034dcb5].
4749 **
4750 ** Another solution would be to change the OP_SCopy used to copy cached
4751 ** values to an OP_Copy.
4752 */
4755 }
4759 }
4764 }
4765 }
4767 /*
4768 ** Add a single OP_Explain instruction to the VDBE to explain a simple
4769 ** count(*) query ("SELECT count(*) FROM pTab").
4770 */
4771 #ifndef SQLITE_OMIT_EXPLAIN
4776 ){
4783 );
4786 );
4787 }
4788 }
4789 #else
4790 # define explainSimpleCount(a,b,c)
4791 #endif
4793 /*
4794 ** Generate code for the SELECT statement given in the p argument.
4795 **
4796 ** The results are returned according to the SelectDest structure.
4797 ** See comments in sqliteInt.h for further information.
4798 **
4799 ** This routine returns the number of errors. If any errors are
4800 ** encountered, then an appropriate error message is left in
4801 ** pParse->zErrMsg.
4802 **
4803 ** This routine does NOT free the Select structure passed in. The
4804 ** calling function needs to do that.
4805 */
4810 ){
4827 #ifndef SQLITE_OMIT_EXPLAIN
4830 #endif
4835 }
4838 #if SELECTTRACE_ENABLED
4843 }
4844 #endif
4855 /* If ORDER BY makes no difference in the output then neither does
4856 ** DISTINCT so it can be removed too. */
4860 }
4867 }
4870 #if SELECTTRACE_ENABLED
4874 }
4875 #endif
4877 /* Try to flatten subqueries in the FROM clause up into the main query
4878 */
4879 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
4887 /* Catch mismatch in the declared columns of a view and the number of
4888 ** columns in the SELECT on the RHS */
4893 }
4897 /* This subquery can be absorbed into its parent. */
4901 }
4903 }
4908 }
4909 }
4910 #endif
4912 /* Get a pointer the VDBE under construction, allocating a new VDBE if one
4913 ** does not already exist */
4917 #ifndef SQLITE_OMIT_COMPOUND_SELECT
4918 /* Handle compound SELECT statements using the separate multiSelect()
4919 ** procedure.
4920 */
4924 #if SELECTTRACE_ENABLED
4927 #endif
4929 }
4930 #endif
4932 /* Generate code for all sub-queries in the FROM clause
4933 */
4934 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
4937 SelectDest dest;
4941 /* Sometimes the code for a subquery will be generated more than
4942 ** once, if the subquery is part of the WHERE clause in a LEFT JOIN,
4943 ** for example. In that case, do not regenerate the code to manifest
4944 ** a view or the co-routine to implement a view. The first instance
4945 ** is sufficient, though the subroutine to manifest the view does need
4946 ** to be invoked again. */
4950 }
4952 }
4954 /* Increment Parse.nHeight by the height of the largest expression
4955 ** tree referred to by this, the parent select. The child select
4956 ** may contain expression trees of at most
4957 ** (SQLITE_MAX_EXPR_DEPTH-Parse.nHeight) height. This is a bit
4958 ** more conservative than necessary, but much easier than enforcing
4959 ** an exact limit.
4960 */
4963 /* Make copies of constant WHERE-clause terms in the outer query down
4964 ** inside the subquery. This can help the subquery to run more efficiently.
4965 */
4968 ){
4969 #if SELECTTRACE_ENABLED
4973 }
4974 #endif
4975 }
4977 /* Generate code to implement the subquery
4978 **
4979 ** The subquery is implemented as a co-routine if all of these are true:
4980 ** (1) The subquery is guaranteed to be the outer loop (so that it
4981 ** does not need to be computed more than once)
4982 ** (2) The ALL keyword after SELECT is omitted. (Applications are
4983 ** allowed to say "SELECT ALL" instead of just "SELECT" to disable
4984 ** the use of co-routines.)
4985 ** (3) Co-routines are not disabled using sqlite3_test_control()
4986 ** with SQLITE_TESTCTRL_OPTIMIZATIONS.
4987 **
4988 ** TODO: Are there other reasons beside (1) to use a co-routine
4989 ** implementation?
4990 */
4996 ){
4997 /* Implement a co-routine that will return a single row of the result
4998 ** set on each invocation.
4999 */
5015 /* Generate a subroutine that will fill an ephemeral table with
5016 ** the content of this subquery. pItem->addrFillSub will point
5017 ** to the address of the generated subroutine. pItem->regReturn
5018 ** is a register allocated to hold the subroutine return address
5019 */
5028 /* If the subquery is not correlated and if we are not inside of
5029 ** a trigger, then we only need to compute the value of the subquery
5030 ** once. */
5035 }
5045 }
5048 }
5049 #endif
5051 /* Various elements of the SELECT copied into local variables for
5052 ** convenience */
5059 #if SELECTTRACE_ENABLED
5063 }
5064 #endif
5066 /* If the query is DISTINCT with an ORDER BY but is not an aggregate, and
5067 ** if the select-list is the same as the ORDER BY list, then this query
5068 ** can be rewritten as a GROUP BY. In other words, this:
5069 **
5070 ** SELECT DISTINCT xyz FROM ... ORDER BY xyz
5071 **
5072 ** is transformed to:
5073 **
5074 ** SELECT xyz FROM ... GROUP BY xyz ORDER BY xyz
5075 **
5076 ** The second form is preferred as a single index (or temp-table) may be
5077 ** used for both the ORDER BY and DISTINCT processing. As originally
5078 ** written the query must use a temp-table for at least one of the ORDER
5079 ** BY and DISTINCT, and an index or separate temp-table for the other.
5080 */
5083 ){
5086 /* Notice that even thought SF_Distinct has been cleared from p->selFlags,
5087 ** the sDistinct.isTnct is still set. Hence, isTnct represents the
5088 ** original setting of the SF_Distinct flag, not the current setting */
5091 #if SELECTTRACE_ENABLED
5095 }
5096 #endif
5097 }
5099 /* If there is an ORDER BY clause, then create an ephemeral index to
5100 ** do the sorting. But this sorting ephemeral index might end up
5101 ** being unused if the data can be extracted in pre-sorted order.
5102 ** If that is the case, then the OP_OpenEphemeral instruction will be
5103 ** changed to an OP_Noop once we figure out that the sorting index is
5104 ** not needed. The sSort.addrSortIndex variable is used to facilitate
5105 ** that change.
5106 */
5115 );
5118 }
5120 /* If the output is destined for a temporary table, open that table.
5121 */
5124 }
5126 /* Set the limiter.
5127 */
5134 }
5136 /* Open an ephemeral index to use for the distinct set.
5137 */
5143 P4_KEYINFO);
5148 }
5151 /* No aggregate functions and no GROUP BY clause */
5156 /* Begin the database scan. */
5162 }
5165 }
5171 }
5172 }
5174 /* If sorting index that was created by a prior OP_OpenEphemeral
5175 ** instruction ended up not being needed, then change the OP_OpenEphemeral
5176 ** into an OP_Noop.
5177 */
5180 }
5182 /* Use the standard inner loop. */
5187 /* End the database scan loop.
5188 */
5191 /* This case when there exist aggregate functions or a GROUP BY clause
5192 ** or both */
5197 ** one row of the input to the aggregator has been
5198 ** processed */
5206 /* Remove any and all aliases between the result set and the
5207 ** GROUP BY clause.
5208 */
5215 }
5218 }
5224 }
5226 /* If there is both a GROUP BY and an ORDER BY clause and they are
5227 ** identical, then it may be possible to disable the ORDER BY clause
5228 ** on the grounds that the GROUP BY will cause elements to come out
5229 ** in the correct order. It also may not - the GROUP BY might use a
5230 ** database index that causes rows to be grouped together as required
5231 ** but not actually sorted. Either way, record the fact that the
5232 ** ORDER BY and GROUP BY clauses are the same by setting the orderByGrp
5233 ** variable. */
5236 }
5238 /* Create a label to jump to when we want to abort the query */
5241 /* Convert TK_COLUMN nodes into TK_AGG_COLUMN and make entries in
5242 ** sAggInfo for all TK_AGG_FUNCTION nodes in expressions of the
5243 ** SELECT statement.
5244 */
5256 }
5263 }
5267 /* Processing for aggregates with GROUP BY is very different and
5268 ** much more complex than aggregates without a GROUP BY.
5269 */
5281 /* If there is a GROUP BY clause we might need a sorting index to
5282 ** implement it. Allocate that sorting index now. If it turns out
5283 ** that we do not need it after all, the OP_SorterOpen instruction
5284 ** will be converted into a Noop.
5285 */
5292 /* Initialize memory locations used by GROUP BY aggregate processing
5293 */
5310 /* Begin a loop that will extract all source rows in GROUP BY order.
5311 ** This might involve two separate loops with an OP_Sort in between, or
5312 ** it might be a single loop that uses an index to extract information
5313 ** in the right order to begin with.
5314 */
5318 );
5321 /* The optimizer is able to deliver rows in group by order so
5322 ** we do not have to sort. The OP_OpenEphemeral table will be
5323 ** cancelled later because we still need to use the pKeyInfo
5324 */
5327 /* Rows are coming out in undetermined order. We have to push
5328 ** each row into a sorting index, terminate the first loop,
5329 ** then loop over the sorting index in order to get the output
5330 ** in sorted order
5331 */
5347 nCol++;
5348 j++;
5349 }
5350 }
5361 j++;
5362 }
5363 }
5378 }
5380 /* If the index or temporary table used by the GROUP BY sort
5381 ** will naturally deliver rows in the order required by the ORDER BY
5382 ** clause, cancel the ephemeral table open coded earlier.
5383 **
5384 ** This is an optimization - the correct answer should result regardless.
5385 ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER to
5386 ** disable this optimization for testing purposes. */
5389 ){
5392 }
5394 /* Evaluate the current GROUP BY terms and store in b0, b1, b2...
5395 ** (b0 is memory location iBMem+0, b1 is iBMem+1, and so forth)
5396 ** Then compare the current GROUP BY terms against the GROUP BY terms
5397 ** from the previous row currently stored in a0, a1, a2...
5398 */
5404 }
5411 }
5412 }
5418 /* Generate code that runs whenever the GROUP BY changes.
5419 ** Changes in the GROUP BY are detected by the previous code
5420 ** block. If there were no changes, this block is skipped.
5421 **
5422 ** This code copies current group by terms in b0,b1,b2,...
5423 ** over to a0,a1,a2. It then calls the output subroutine
5424 ** and resets the aggregate accumulator registers in preparation
5425 ** for the next GROUP BY batch.
5426 */
5435 /* Update the aggregate accumulators based on the content of
5436 ** the current row
5437 */
5443 /* End of the loop
5444 */
5451 }
5453 /* Output the final row of result
5454 */
5458 /* Jump over the subroutines
5459 */
5462 /* Generate a subroutine that outputs a single row of the result
5463 ** set. This subroutine first looks at the iUseFlag. If iUseFlag
5464 ** is less than or equal to zero, the subroutine is a no-op. If
5465 ** the processing calls for the query to abort, this subroutine
5466 ** increments the iAbortFlag memory location before returning in
5467 ** order to signal the caller to abort.
5468 */
5487 /* Generate a subroutine that will reset the group-by accumulator
5488 */
5496 #ifndef SQLITE_OMIT_BTREECOUNT
5499 /* If isSimpleCount() returns a pointer to a Table structure, then
5500 ** the SQL statement is of the form:
5501 **
5502 ** SELECT count(*) FROM <tbl>
5503 **
5504 ** where the Table structure returned represents table <tbl>.
5505 **
5506 ** This statement is so common that it is optimized specially. The
5507 ** OP_Count instruction is executed either on the intkey table that
5508 ** contains the data for table <tbl> or on one of its indexes. It
5509 ** is better to execute the op on an index, as indexes are almost
5510 ** always spread across less pages than their corresponding tables.
5511 */
5522 /* Search for the index that has the lowest scan cost.
5523 **
5524 ** (2011-04-15) Do not do a full scan of an unordered index.
5525 **
5526 ** (2013-10-03) Do not count the entries in a partial index.
5527 **
5528 ** In practice the KeyInfo structure will not be used. It is only
5529 ** passed to keep OP_OpenRead happy.
5530 */
5537 ){
5539 }
5540 }
5544 }
5546 /* Open a read-only cursor, execute the OP_Count, close the cursor. */
5550 }
5556 {
5557 /* Check if the query is of one of the following forms:
5558 **
5559 ** SELECT min(x) FROM ...
5560 ** SELECT max(x) FROM ...
5561 **
5562 ** If it is, then ask the code in where.c to attempt to sort results
5563 ** as if there was an "ORDER ON x" or "ORDER ON x DESC" clause.
5564 ** If where.c is able to produce results sorted in this order, then
5565 ** add vdbe code to break out of the processing loop after the
5566 ** first iteration (since the first iteration of the loop is
5567 ** guaranteed to operate on the row with the minimum or maximum
5568 ** value of x, the only row required).
5569 **
5570 ** A special flag must be passed to sqlite3WhereBegin() to slightly
5571 ** modify behavior as follows:
5572 **
5573 ** + If the query is a "SELECT min(x)", then the loop coded by
5574 ** where.c should not iterate over any values with a NULL value
5575 ** for x.
5576 **
5577 ** + The optimizer code in where.c (the thing that decides which
5578 ** index or indices to use) should place a different priority on
5579 ** satisfying the 'ORDER BY' clause than it does in other cases.
5580 ** Refer to code and comments in where.c for details.
5581 */
5589 }
5599 }
5600 }
5602 /* This case runs if the aggregate has no GROUP BY clause. The
5603 ** processing is much simpler since there is only a single row
5604 ** of output.
5605 */
5611 }
5618 }
5621 }
5628 }
5635 }
5637 /* If there is an ORDER BY clause, then we need to sort the results
5638 ** and send them to the callback one by one.
5639 */
5644 }
5646 /* Jump here to skip this query
5647 */
5650 /* The SELECT has been coded. If there is an error in the Parse structure,
5651 ** set the return code to 1. Otherwise 0. */
5654 /* Control jumps to here if an error is encountered above, or upon
5655 ** successful coding of the SELECT.
5656 */
5657 select_end:
5660 /* Identify column names if results of the SELECT are to be output.
5661 */
5664 }
5668 #if SELECTTRACE_ENABLED
5671 #endif
5673 }