| blob | 3b422f1100349609920c592ba6ab4e096d1ef2ff |
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 sqlite3DebugPrintf X
26 #else
27 # define SELECTTRACE(K,P,S,X)
28 #endif
31 /*
32 ** An instance of the following object is used to record information about
33 ** how to process the DISTINCT keyword, to simplify passing that information
34 ** into the selectInnerLoop() routine.
35 */
42 };
44 /*
45 ** An instance of the following object is used to record information about
46 ** the ORDER BY (or GROUP BY) clause of query is being coded.
47 */
57 };
60 /*
61 ** Delete all the content of a Select structure but do not deallocate
62 ** the select structure itself.
63 */
75 }
77 /*
78 ** Initialize a SelectDest structure.
79 */
86 }
89 /*
90 ** Allocate a new Select structure and return a pointer to that
91 ** structure.
92 */
104 ){
106 Select standin;
114 }
117 }
138 }
141 }
143 #if SELECTTRACE_ENABLED
144 /*
145 ** Set the name of a Select object
146 */
150 }
151 }
152 #endif
155 /*
156 ** Delete the given Select structure and all of its substructures.
157 */
162 }
163 }
165 /*
166 ** Return a pointer to the right-most SELECT statement in a compound.
167 */
171 }
173 /*
174 ** Given 1 to 3 identifiers preceding the JOIN keyword, determine the
175 ** type of join. Return an integer constant that expresses that type
176 ** in terms of the following bit values:
177 **
178 ** JT_INNER
179 ** JT_CROSS
180 ** JT_OUTER
181 ** JT_NATURAL
182 ** JT_LEFT
183 ** JT_RIGHT
184 **
185 ** A full outer join is the combination of JT_LEFT and JT_RIGHT.
186 **
187 ** If an illegal or unsupported join type is seen, then still return
188 ** a join type, but put an error in the pParse structure.
189 */
194 /* 0123456789 123456789 123456789 123 */
208 };
220 }
221 }
226 }
227 }
231 ){
243 }
245 }
247 /*
248 ** Return the index of a column in a table. Return -1 if the column
249 ** is not contained in the table.
250 */
255 }
257 }
259 /*
260 ** Search the first N tables in pSrc, from left to right, looking for a
261 ** table that has a column named zCol.
262 **
263 ** When found, set *piTab and *piCol to the table index and column index
264 ** of the matching column and return TRUE.
265 **
266 ** If not found, return FALSE.
267 */
274 ){
285 }
287 }
288 }
290 }
292 /*
293 ** This function is used to add terms implied by JOIN syntax to the
294 ** WHERE clause expression of a SELECT statement. The new term, which
295 ** is ANDed with the existing WHERE clause, is of the form:
296 **
297 ** (tab1.col1 = tab2.col2)
298 **
299 ** where tab1 is the iSrc'th table in SrcList pSrc and tab2 is the
300 ** (iSrc+1)'th. Column col1 is column iColLeft of tab1, and col2 is
301 ** column iColRight of tab2.
302 */
312 ){
332 }
334 }
336 /*
337 ** Set the EP_FromJoin property on all terms of the given expression.
338 ** And set the Expr.iRightJoinTable to iTable for every term in the
339 ** expression.
340 **
341 ** The EP_FromJoin property is used on terms of an expression to tell
342 ** the LEFT OUTER JOIN processing logic that this term is part of the
343 ** join restriction specified in the ON or USING clause and not a part
344 ** of the more general WHERE clause. These terms are moved over to the
345 ** WHERE clause during join processing but we need to remember that they
346 ** originated in the ON or USING clause.
347 **
348 ** The Expr.iRightJoinTable tells the WHERE clause processing that the
349 ** expression depends on table iRightJoinTable even if that table is not
350 ** explicitly mentioned in the expression. That information is needed
351 ** for cases like this:
352 **
353 ** SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.b AND t1.x=5
354 **
355 ** The where clause needs to defer the handling of the t1.x=5
356 ** term until after the t2 loop of the join. In that way, a
357 ** NULL t2 row will be inserted whenever t1.x!=5. If we do not
358 ** defer the handling of t1.x=5, it will be processed immediately
359 ** after the t1 loop and rows with t1.x!=5 will never appear in
360 ** the output, which is incorrect.
361 */
370 }
371 }
373 /*
374 ** This routine processes the join information for a SELECT statement.
375 ** ON and USING clauses are converted into extra terms of the WHERE clause.
376 ** NATURAL joins also create extra WHERE clause terms.
377 **
378 ** The terms of a FROM clause are contained in the Select.pSrc structure.
379 ** The left most table is the first entry in Select.pSrc. The right-most
380 ** table is the last entry. The join operator is held in the entry to
381 ** the left. Thus entry 0 contains the join operator for the join between
382 ** entries 0 and 1. Any ON or USING clauses associated with the join are
383 ** also attached to the left entry.
384 **
385 ** This routine returns the number of errors encountered.
386 */
404 /* When the NATURAL keyword is present, add WHERE clause terms for
405 ** every column that the two tables have in common.
406 */
412 }
422 }
423 }
424 }
426 /* Disallow both ON and USING clauses in the same join
427 */
432 }
434 /* Add the ON clause to the end of the WHERE clause, connected by
435 ** an AND operator.
436 */
441 }
443 /* Create extra terms on the WHERE clause for each column named
444 ** in the USING clause. Example: If the two tables to be joined are
445 ** A and B and the USING clause names X, Y, and Z, then add this
446 ** to the WHERE clause: A.X=B.X AND A.Y=B.Y AND A.Z=B.Z
447 ** Report an error if any column mentioned in the USING clause is
448 ** not contained in both tables to be joined.
449 */
462 ){
466 }
469 }
470 }
471 }
473 }
475 /* Forward reference */
481 );
483 /*
484 ** Generate code that will push the record in registers regData
485 ** through regData+nData-1 onto the sorter.
486 */
494 ){
511 }
515 }
518 }
536 }
555 }
560 }
569 }
577 }
578 }
580 /*
581 ** Add code to implement the OFFSET
582 */
587 ){
594 }
595 }
597 /*
598 ** Add code that will check to make sure the N registers starting at iMem
599 ** form a distinct entry. iTab is a sorting index that holds previously
600 ** seen combinations of the N values. A new entry is made in iTab
601 ** if the current N values are new.
602 **
603 ** A jump to addrRepeat is made and the N+1 values are popped from the
604 ** stack if the top N elements are not distinct.
605 */
612 ){
622 }
624 #ifndef SQLITE_OMIT_SUBQUERY
625 /*
626 ** Generate an error message when a SELECT is used within a subexpression
627 ** (example: "a IN (SELECT * FROM table)") but it has more than 1 result
628 ** column. We do this in a subroutine because the error used to occur
629 ** in multiple places. (The error only occurs in one place now, but we
630 ** retain the subroutine to minimize code disruption.)
631 */
636 ){
644 }
645 }
646 #endif
648 /*
649 ** This routine generates the code for the inside of the inner loop
650 ** of a SELECT.
651 **
652 ** If srcTab is negative, then the pEList expressions
653 ** are evaluated in order to get the data for this row. If srcTab is
654 ** zero or more, then data is pulled from srcTab and pEList is used only
655 ** to get number columns and the datatype for each column.
656 */
667 ){
684 }
686 /* Pull the requested columns.
687 */
695 }
699 /* This is an error condition that can result, for example, when a SELECT
700 ** on the right-hand side of an INSERT contains more result columns than
701 ** there are columns in the table on the left. The error will be caught
702 ** and reported later. But we need to make sure enough memory is allocated
703 ** to avoid other spurious errors in the meantime. */
705 }
712 }
714 /* If the destination is an EXISTS(...) expression, the actual
715 ** values returned by the SELECT are not required.
716 */
719 }
721 /* If the DISTINCT keyword was present on the SELECT statement
722 ** and this row has been seen before, then do not make this row
723 ** part of the result.
724 */
732 /* Allocate space for the previous row */
736 /* Change the OP_OpenEphemeral coded earlier to an OP_Null
737 ** sets the MEM_Cleared bit on the first register of the
738 ** previous value. This will cause the OP_Ne below to always
739 ** fail on the first iteration of the loop even if the first
740 ** row is all NULLs.
741 */
757 }
760 }
764 }
769 }
775 }
776 }
779 }
780 }
783 /* In this mode, write each query result to the key of the temporary
784 ** table iParm.
785 */
786 #ifndef SQLITE_OMIT_COMPOUND_SELECT
794 }
796 /* Construct a record from the query result, but instead of
797 ** saving that record, use it as a key to delete elements from
798 ** the temporary table iParm.
799 */
803 }
806 /* Store the result as data using a unique key.
807 */
816 #ifndef SQLITE_OMIT_CTE
818 /* If the destination is DistFifo, then cursor (iParm+1) is open
819 ** on an ephemeral index. If the current row is already present
820 ** in the index, do not write it to the output. If not, add the
821 ** current row to the index and proceed with writing it to the
822 ** output table as well. */
827 }
828 #endif
837 }
840 }
842 #ifndef SQLITE_OMIT_SUBQUERY
843 /* If we are creating a set for an "expr IN (SELECT ...)" construct,
844 ** then there should be a single item on the stack. Write this
845 ** item into the set table with bogus data.
846 */
852 /* At first glance you would think we could optimize out the
853 ** ORDER BY in this case since the order of entries in the set
854 ** does not matter. But there might be a LIMIT clause, in which
855 ** case the order does matter */
863 }
865 }
867 /* If any row exist in the result set, record that fact and abort.
868 */
871 /* The LIMIT clause will terminate the loop for us */
873 }
875 /* If this is a scalar select that is part of an expression, then
876 ** store the results in the appropriate memory cell and break out
877 ** of the scan loop.
878 */
885 /* The LIMIT clause will jump out of the loop for us */
886 }
888 }
902 }
904 }
906 #ifndef SQLITE_OMIT_CTE
907 /* Write the results into a priority queue that is order according to
908 ** pDest->pOrderBy (in pSO). pDest->iSDParm (in iParm) is the cursor for an
909 ** index with pSO->nExpr+2 columns. Build a key using pSO for the first
910 ** pSO->nExpr columns, then make sure all keys are unique by adding a
911 ** final OP_Sequence column. The last column is the record as a blob.
912 */
926 /* If the destination is DistQueue, then cursor (iParm+1) is open
927 ** on a second ephemeral index that holds all values every previously
928 ** added to the queue. */
932 }
937 }
942 }
950 }
955 #if !defined(SQLITE_OMIT_TRIGGER)
956 /* Discard the results. This is used for SELECT statements inside
957 ** the body of a TRIGGER. The purpose of such selects is to call
958 ** user-defined functions that have side effects. We do not care
959 ** about the actual results of the select.
960 */
964 }
965 #endif
966 }
968 /* Jump to the end of the loop if the LIMIT is reached. Except, if
969 ** there is a sorter, in which case the sorter has already limited
970 ** the output for us.
971 */
974 }
975 }
977 /*
978 ** Allocate a KeyInfo object sufficient for an index of N key columns and
979 ** X extra columns.
980 */
993 }
995 }
997 /*
998 ** Deallocate a KeyInfo object
999 */
1005 }
1006 }
1008 /*
1009 ** Make a new pointer to a KeyInfo object
1010 */
1015 }
1017 }
1019 #ifdef SQLITE_DEBUG
1020 /*
1021 ** Return TRUE if a KeyInfo object can be change. The KeyInfo object
1022 ** can only be changed if this is just a single reference to the object.
1023 **
1024 ** This routine is used only inside of assert() statements.
1025 */
1029 /*
1030 ** Given an expression list, generate a KeyInfo structure that records
1031 ** the collating sequence for each expression in that expression list.
1032 **
1033 ** If the ExprList is an ORDER BY or GROUP BY clause then the resulting
1034 ** KeyInfo structure is appropriate for initializing a virtual index to
1035 ** implement that clause. If the ExprList is the result set of a SELECT
1036 ** then the KeyInfo structure is appropriate for initializing a virtual
1037 ** index to implement a DISTINCT test.
1038 **
1039 ** Space to hold the KeyInfo structure is obtained from malloc. The calling
1040 ** function is responsible for seeing that this structure is eventually
1041 ** freed.
1042 */
1048 ){
1065 }
1066 }
1068 }
1070 #ifndef SQLITE_OMIT_COMPOUND_SELECT
1071 /*
1072 ** Name of the connection operator, used for error messages.
1073 */
1081 }
1083 }
1086 #ifndef SQLITE_OMIT_EXPLAIN
1087 /*
1088 ** Unless an "EXPLAIN QUERY PLAN" command is being processed, this function
1089 ** is a no-op. Otherwise, it adds a single row of output to the EQP result,
1090 ** where the caption is of the form:
1091 **
1092 ** "USE TEMP B-TREE FOR xxx"
1093 **
1094 ** where xxx is one of "DISTINCT", "ORDER BY" or "GROUP BY". Exactly which
1095 ** is determined by the zUsage argument.
1096 */
1102 }
1103 }
1105 /*
1106 ** Assign expression b to lvalue a. A second, no-op, version of this macro
1107 ** is provided when SQLITE_OMIT_EXPLAIN is defined. This allows the code
1108 ** in sqlite3Select() to assign values to structure member variables that
1109 ** only exist if SQLITE_OMIT_EXPLAIN is not defined without polluting the
1110 ** code with #ifndef directives.
1111 */
1112 # define explainSetInteger(a, b) a = b
1114 #else
1115 /* No-op versions of the explainXXX() functions and macros. */
1116 # define explainTempTable(y,z)
1117 # define explainSetInteger(y,z)
1118 #endif
1120 #if !defined(SQLITE_OMIT_EXPLAIN) && !defined(SQLITE_OMIT_COMPOUND_SELECT)
1121 /*
1122 ** Unless an "EXPLAIN QUERY PLAN" command is being processed, this function
1123 ** is a no-op. Otherwise, it adds a single row of output to the EQP result,
1124 ** where the caption is of one of the two forms:
1125 **
1126 ** "COMPOSITE SUBQUERIES iSub1 and iSub2 (op)"
1127 ** "COMPOSITE SUBQUERIES iSub1 and iSub2 USING TEMP B-TREE (op)"
1128 **
1129 ** where iSub1 and iSub2 are the integers passed as the corresponding
1130 ** function parameters, and op is the text representation of the parameter
1131 ** of the same name. The parameter "op" must be one of TK_UNION, TK_EXCEPT,
1132 ** TK_INTERSECT or TK_ALL. The first form is used if argument bUseTmp is
1133 ** false, or the second form if it is true.
1134 */
1141 ){
1148 );
1150 }
1151 }
1152 #else
1153 /* No-op versions of the explainXXX() functions and macros. */
1154 # define explainComposite(v,w,x,y,z)
1155 #endif
1157 /*
1158 ** If the inner loop was generated using a non-null pOrderBy argument,
1159 ** then the results were placed in a sorter. After the loop is terminated
1160 ** we need to run the sorter and output the results. The following
1161 ** routine generates the code needed to do that.
1162 */
1169 ){
1186 #ifdef SQLITE_ENABLE_EXPLAIN_COMMENTS
1188 #endif
1194 }
1204 }
1211 }
1224 }
1228 }
1238 }
1239 #ifndef SQLITE_OMIT_SUBQUERY
1247 }
1251 /* The LIMIT clause will terminate the loop for us */
1253 }
1254 #endif
1264 }
1266 }
1267 }
1271 }
1272 /* The bottom of the loop
1273 */
1279 }
1282 }
1284 /*
1285 ** Return a pointer to a string containing the 'declaration type' of the
1286 ** expression pExpr. The string may be treated as static by the caller.
1287 **
1288 ** Also try to estimate the size of the returned value and return that
1289 ** result in *pEstWidth.
1290 **
1291 ** The declaration type is the exact datatype definition extracted from the
1292 ** original CREATE TABLE statement if the expression is a column. The
1293 ** declaration type for a ROWID field is INTEGER. Exactly when an expression
1294 ** is considered a column can be complex in the presence of subqueries. The
1295 ** result-set expression in all of the following SELECT statements is
1296 ** considered a column by this function.
1297 **
1298 ** SELECT col FROM tbl;
1299 ** SELECT (SELECT col FROM tbl;
1300 ** SELECT (SELECT col FROM tbl);
1301 ** SELECT abc FROM (SELECT col AS abc FROM tbl);
1302 **
1303 ** The declaration type for any expression other than a column is NULL.
1304 **
1305 ** This routine has either 3 or 6 parameters depending on whether or not
1306 ** the SQLITE_ENABLE_COLUMN_METADATA compile-time option is used.
1307 */
1308 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1309 # define columnType(A,B,C,D,E,F) columnTypeImpl(A,B,C,D,E,F)
1316 u8 *pEstWidth
1317 ){
1322 # define columnType(A,B,C,D,E,F) columnTypeImpl(A,B,F)
1326 u8 *pEstWidth
1327 ){
1337 /* The expression is a column. Locate the table the column is being
1338 ** extracted from in NameContext.pSrcList. This table may be real
1339 ** database table or a subquery.
1340 */
1354 }
1355 }
1358 /* At one time, code such as "SELECT new.x" within a trigger would
1359 ** cause this condition to run. Since then, we have restructured how
1360 ** trigger code is generated and so this condition is no longer
1361 ** possible. However, it can still be true for statements like
1362 ** the following:
1363 **
1364 ** CREATE TABLE t1(col INTEGER);
1365 ** SELECT (SELECT t1.col) FROM FROM t1;
1366 **
1367 ** when columnType() is called on the expression "t1.col" in the
1368 ** sub-select. In this case, set the column type to NULL, even
1369 ** though it should really be "INTEGER".
1370 **
1371 ** This is not a problem, as the column type of "t1.col" is never
1372 ** used. When columnType() is called on the expression
1373 ** "(SELECT t1.col)", the correct type is returned (see the TK_SELECT
1374 ** branch below. */
1376 }
1380 /* The "table" is actually a sub-select or a view in the FROM clause
1381 ** of the SELECT statement. Return the declaration type and origin
1382 ** data for the result-set column of the sub-select.
1383 */
1385 /* If iCol is less than zero, then the expression requests the
1386 ** rowid of the sub-select or view. This expression is legal (see
1387 ** test case misc2.2.2) - it always evaluates to NULL.
1388 */
1389 NameContext sNC;
1395 }
1397 /* A real table */
1401 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1409 }
1414 }
1415 #else
1421 }
1422 #endif
1423 }
1425 }
1426 #ifndef SQLITE_OMIT_SUBQUERY
1428 /* The expression is a sub-select. Return the declaration type and
1429 ** origin info for the single column in the result set of the SELECT
1430 ** statement.
1431 */
1432 NameContext sNC;
1441 }
1442 #endif
1443 }
1445 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1451 }
1452 #endif
1455 }
1457 /*
1458 ** Generate code that will tell the VDBE the declaration types of columns
1459 ** in the result set.
1460 */
1465 ){
1466 #ifndef SQLITE_OMIT_DECLTYPE
1469 NameContext sNC;
1475 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1481 /* The vdbe must make its own copy of the column-type and other
1482 ** column specific strings, in case the schema is reset before this
1483 ** virtual machine is deleted.
1484 */
1488 #else
1490 #endif
1492 }
1494 }
1496 /*
1497 ** Generate code that will tell the VDBE the names of columns
1498 ** in the result set. This information is used to provide the
1499 ** azCol[] values in the callback.
1500 */
1505 ){
1511 #ifndef SQLITE_OMIT_EXPLAIN
1512 /* If this is an EXPLAIN, skip this step */
1515 }
1516 #endif
1536 }
1545 }
1555 }
1560 }
1561 }
1563 }
1565 /*
1566 ** Given an expression list (which is really the list of expressions
1567 ** that form the result set of a SELECT statement) compute appropriate
1568 ** column names for a table that would hold the expression list.
1569 **
1570 ** All column names will be unique.
1571 **
1572 ** Only the column names are computed. Column.zType, Column.zColl,
1573 ** and other fields of Column are zeroed.
1574 **
1575 ** Return SQLITE_OK on success. If a memory allocation error occurs,
1576 ** store NULL in *paCol and 0 in *pnCol and return SQLITE_NOMEM.
1577 */
1583 ){
1600 }
1605 /* Get an appropriate name for the column
1606 */
1609 /* If the column contains an "AS <name>" phrase, use <name> as the name */
1617 }
1619 /* For columns use the column name name */
1629 /* Use the original text of the column expression as its name */
1631 }
1632 }
1636 }
1638 /* Make sure the column name is unique. If the name is not unique,
1639 ** append an integer to the name so that it becomes unique.
1640 */
1654 }
1655 }
1657 }
1661 }
1666 }
1668 }
1670 /*
1671 ** Add type and collation information to a column list based on
1672 ** a SELECT statement.
1673 **
1674 ** The column list presumably came from selectColumnNamesFromExprList().
1675 ** The column list has only names, not types or collations. This
1676 ** routine goes through and adds the types and collations.
1677 **
1678 ** This routine requires that all identifiers in the SELECT
1679 ** statement be resolved.
1680 */
1685 ){
1687 NameContext sNC;
1711 }
1712 }
1714 }
1716 /*
1717 ** Given a SELECT statement, generate a Table structure that describes
1718 ** the result set of that SELECT.
1719 */
1735 }
1736 /* The sqlite3ResultSetOfSelect() is only used n contexts where lookaside
1737 ** is disabled */
1748 }
1750 }
1752 /*
1753 ** Get a VDBE for the given parser context. Create a new one if necessary.
1754 ** If an error occurs, return NULL and leave a message in pParse.
1755 */
1763 ){
1765 }
1767 }
1769 }
1772 /*
1773 ** Compute the iLimit and iOffset fields of the SELECT based on the
1774 ** pLimit and pOffset expressions. pLimit and pOffset hold the expressions
1775 ** that appear in the original SQL statement after the LIMIT and OFFSET
1776 ** keywords. Or NULL if those keywords are omitted. iLimit and iOffset
1777 ** are the integer memory register numbers for counters used to compute
1778 ** the limit and offset. If there is no limit and/or offset, then
1779 ** iLimit and iOffset are negative.
1780 **
1781 ** This routine changes the values of iLimit and iOffset only if
1782 ** a limit or offset is defined by pLimit and pOffset. iLimit and
1783 ** iOffset should have been preset to appropriate default values (zero)
1784 ** prior to calling this routine.
1785 **
1786 ** The iOffset register (if it exists) is initialized to the value
1787 ** of the OFFSET. The iLimit register is initialized to LIMIT. Register
1788 ** iOffset+1 is initialized to LIMIT+OFFSET.
1789 **
1790 ** Only if pLimit!=0 or pOffset!=0 do the limit registers get
1791 ** redefined. The UNION ALL operator uses this property to force
1792 ** the reuse of the same limit and offset registers across multiple
1793 ** SELECT statements.
1794 */
1802 /*
1803 ** "LIMIT -1" always shows all rows. There is some
1804 ** controversy about what the correct behavior should be.
1805 ** The current implementation interprets "LIMIT 0" to mean
1806 ** no rows.
1807 */
1821 }
1827 }
1842 }
1843 }
1844 }
1846 #ifndef SQLITE_OMIT_COMPOUND_SELECT
1847 /*
1848 ** Return the appropriate collating sequence for the iCol-th column of
1849 ** the result set for the compound-select statement "p". Return NULL if
1850 ** the column has no default collating sequence.
1851 **
1852 ** The collating sequence for the compound select is taken from the
1853 ** left-most term of the select that has a collating sequence.
1854 */
1861 }
1865 }
1867 }
1869 /*
1870 ** The select statement passed as the second parameter is a compound SELECT
1871 ** with an ORDER BY clause. This function allocates and returns a KeyInfo
1872 ** structure suitable for implementing the ORDER BY.
1873 **
1874 ** Space to hold the KeyInfo structure is obtained from malloc. The calling
1875 ** function is responsible for ensuring that this structure is eventually
1876 ** freed.
1877 */
1897 }
1901 }
1902 }
1905 }
1907 #ifndef SQLITE_OMIT_CTE
1908 /*
1909 ** This routine generates VDBE code to compute the content of a WITH RECURSIVE
1910 ** query of the form:
1911 **
1912 ** <recursive-table> AS (<setup-query> UNION [ALL] <recursive-query>)
1913 ** \___________/ \_______________/
1914 ** p->pPrior p
1915 **
1916 **
1917 ** There is exactly one reference to the recursive-table in the FROM clause
1918 ** of recursive-query, marked with the SrcList->a[].isRecursive flag.
1919 **
1920 ** The setup-query runs once to generate an initial set of rows that go
1921 ** into a Queue table. Rows are extracted from the Queue table one by
1922 ** one. Each row extracted from Queue is output to pDest. Then the single
1923 ** extracted row (now in the iCurrent table) becomes the content of the
1924 ** recursive-table for a recursive-query run. The output of the recursive-query
1925 ** is added back into the Queue table. Then another row is extracted from Queue
1926 ** and the iteration continues until the Queue table is empty.
1927 **
1928 ** If the compound query operator is UNION then no duplicate rows are ever
1929 ** inserted into the Queue table. The iDistinct table keeps a copy of all rows
1930 ** that have ever been inserted into Queue and causes duplicates to be
1931 ** discarded. If the operator is UNION ALL, then duplicates are allowed.
1932 **
1933 ** If the query has an ORDER BY, then entries in the Queue table are kept in
1934 ** ORDER BY order and the first entry is extracted for each cycle. Without
1935 ** an ORDER BY, the Queue table is just a FIFO.
1936 **
1937 ** If a LIMIT clause is provided, then the iteration stops after LIMIT rows
1938 ** have been output to pDest. A LIMIT of zero means to output no rows and a
1939 ** negative LIMIT means to output all rows. If there is also an OFFSET clause
1940 ** with a positive value, then the first OFFSET outputs are discarded rather
1941 ** than being sent to pDest. The LIMIT count does not begin until after OFFSET
1942 ** rows have been skipped.
1943 */
1948 ){
1967 /* Obtain authorization to do a recursive query */
1970 /* Process the LIMIT and OFFSET clauses, if they exist */
1981 /* Locate the cursor number of the Current table */
1986 }
1987 }
1989 /* Allocate cursors numbers for Queue and Distinct. The cursor number for
1990 ** the Distinct table must be exactly one greater than Queue in order
1991 ** for the SRT_DistFifo and SRT_DistQueue destinations to work. */
1998 }
2001 /* Allocate cursors for Current, Queue, and Distinct. */
2011 }
2016 }
2018 /* Detach the ORDER BY clause from the compound SELECT */
2021 /* Store the results of the setup-query in Queue. */
2027 /* Find the next row in the Queue and output that row */
2030 /* Transfer the next row in Queue over to Current */
2036 }
2039 /* Output the single row in Current */
2047 }
2050 /* Execute the recursive SELECT taking the single row in Current as
2051 ** the value for the recursive-table. Store the results in the Queue.
2052 */
2058 /* Keep running the loop until the Queue is empty */
2062 end_of_recursive_query:
2068 }
2071 /* Forward references */
2076 );
2079 /*
2080 ** This routine is called to process a compound query form from
2081 ** two or more separate queries using UNION, UNION ALL, EXCEPT, or
2082 ** INTERSECT
2083 **
2084 ** "p" points to the right-most of the two queries. the query on the
2085 ** left is p->pPrior. The left query could also be a compound query
2086 ** in which case this routine will be called recursively.
2087 **
2088 ** The results of the total query are to be written into a destination
2089 ** of type eDest with parameter iParm.
2090 **
2091 ** Example 1: Consider a three-way compound SQL statement.
2092 **
2093 ** SELECT a FROM t1 UNION SELECT b FROM t2 UNION SELECT c FROM t3
2094 **
2095 ** This statement is parsed up as follows:
2096 **
2097 ** SELECT c FROM t3
2098 ** |
2099 ** `-----> SELECT b FROM t2
2100 ** |
2101 ** `------> SELECT a FROM t1
2102 **
2103 ** The arrows in the diagram above represent the Select.pPrior pointer.
2104 ** So if this routine is called with p equal to the t3 query, then
2105 ** pPrior will be the t2 query. p->op will be TK_UNION in this case.
2106 **
2107 ** Notice that because of the way SQLite parses compound SELECTs, the
2108 ** individual selects always group from left to right.
2109 */
2114 ){
2121 #ifndef SQLITE_OMIT_EXPLAIN
2124 #endif
2126 /* Make sure there is no ORDER BY or LIMIT clause on prior SELECTs. Only
2127 ** the last (right-most) SELECT in the series may have an ORDER BY or LIMIT.
2128 */
2139 }
2145 }
2150 /* Create the destination temporary table if necessary
2151 */
2157 }
2159 /* Make sure all SELECTs in the statement have the same number of elements
2160 ** in their result sets.
2161 */
2169 }
2172 }
2174 #ifndef SQLITE_OMIT_CTE
2178 #endif
2180 /* Compound SELECTs that have an ORDER BY clause are handled separately.
2181 */
2186 /* Generate code for the left and right SELECT statements.
2187 */
2203 }
2210 }
2220 ){
2222 }
2225 }
2227 }
2235 SelectDest uniondest;
2241 /* We can reuse a temporary table generated by a SELECT to our
2242 ** right.
2243 */
2248 /* We will need to create our own temporary table to hold the
2249 ** intermediate results.
2250 */
2258 }
2260 /* Code the SELECT statements to our left
2261 */
2268 }
2270 /* Code the current SELECT statement
2271 */
2277 }
2287 /* Query flattening in sqlite3Select() might refill p->pOrderBy.
2288 ** Be sure to delete p->pOrderBy, therefore, to avoid a memory leak. */
2300 /* Convert the data in the temporary table into whatever form
2301 ** it is that we currently need.
2302 */
2311 }
2323 }
2325 }
2331 SelectDest intersectdest;
2334 /* INTERSECT is different from the others since it requires
2335 ** two temporary tables. Hence it has its own case. Begin
2336 ** by allocating the tables we will need.
2337 */
2348 /* Code the SELECTs to our left into temporary table "tab1".
2349 */
2355 }
2357 /* Code the current SELECT into temporary table "tab2"
2358 */
2378 /* Generate code to take the intersection of the two temporary
2379 ** tables.
2380 */
2386 }
2403 }
2404 }
2408 /* Compute collating sequences used by
2409 ** temporary tables needed to implement the compound select.
2410 ** Attach the KeyInfo structure to all temporary tables.
2411 **
2412 ** This section is run by the right-most SELECT statement only.
2413 ** SELECT statements to the left always skip this part. The right-most
2414 ** SELECT might also skip this part if it has no ORDER BY clause and
2415 ** no temp tables are required.
2416 */
2430 }
2435 }
2436 }
2442 /* If [0] is unused then [1] is also unused. So we can
2443 ** always safely abort as soon as the first unused slot is found */
2446 }
2449 P4_KEYINFO);
2451 }
2452 }
2454 }
2456 multi_select_end:
2461 }
2464 /*
2465 ** Code an output subroutine for a coroutine implementation of a
2466 ** SELECT statment.
2467 **
2468 ** The data to be output is contained in pIn->iSdst. There are
2469 ** pIn->nSdst columns to be output. pDest is where the output should
2470 ** be sent.
2471 **
2472 ** regReturn is the number of the register holding the subroutine
2473 ** return address.
2474 **
2475 ** If regPrev>0 then it is the first register in a vector that
2476 ** records the previous output. mem[regPrev] is a flag that is false
2477 ** if there has been no previous output. If regPrev>0 then code is
2478 ** generated to suppress duplicates. pKeyInfo is used for comparing
2479 ** keys.
2480 **
2481 ** If the LIMIT found in p->iLimit is reached, jump immediately to
2482 ** iBreak.
2483 */
2493 ){
2501 /* Suppress duplicates for UNION, EXCEPT, and INTERSECT
2502 */
2512 }
2515 /* Suppress the first OFFSET entries if there is an OFFSET clause
2516 */
2520 /* Store the result as data using a unique key.
2521 */
2535 }
2537 #ifndef SQLITE_OMIT_SUBQUERY
2538 /* If we are creating a set for an "expr IN (SELECT ...)" construct,
2539 ** then there should be a single item on the stack. Write this
2540 ** item into the set table with bogus data.
2541 */
2553 }
2556 /* If any row exist in the result set, record that fact and abort.
2557 */
2560 /* The LIMIT clause will terminate the loop for us */
2562 }
2563 #endif
2565 /* If this is a scalar select that is part of an expression, then
2566 ** store the results in the appropriate memory cell and break out
2567 ** of the scan loop.
2568 */
2572 /* The LIMIT clause will jump out of the loop for us */
2574 }
2577 /* The results are stored in a sequence of registers
2578 ** starting at pDest->iSdst. Then the co-routine yields.
2579 */
2584 }
2588 }
2590 /* If none of the above, then the result destination must be
2591 ** SRT_Output. This routine is never called with any other
2592 ** destination other than the ones handled above or SRT_Output.
2593 **
2594 ** For SRT_Output, results are stored in a sequence of registers.
2595 ** Then the OP_ResultRow opcode is used to cause sqlite3_step() to
2596 ** return the next row of result.
2597 */
2603 }
2604 }
2606 /* Jump to the end of the loop if the LIMIT is reached.
2607 */
2610 }
2612 /* Generate the subroutine return
2613 */
2618 }
2620 /*
2621 ** Alternative compound select code generator for cases when there
2622 ** is an ORDER BY clause.
2623 **
2624 ** We assume a query of the following form:
2625 **
2626 ** <selectA> <operator> <selectB> ORDER BY <orderbylist>
2627 **
2628 ** <operator> is one of UNION ALL, UNION, EXCEPT, or INTERSECT. The idea
2629 ** is to code both <selectA> and <selectB> with the ORDER BY clause as
2630 ** co-routines. Then run the co-routines in parallel and merge the results
2631 ** into the output. In addition to the two coroutines (called selectA and
2632 ** selectB) there are 7 subroutines:
2633 **
2634 ** outA: Move the output of the selectA coroutine into the output
2635 ** of the compound query.
2636 **
2637 ** outB: Move the output of the selectB coroutine into the output
2638 ** of the compound query. (Only generated for UNION and
2639 ** UNION ALL. EXCEPT and INSERTSECT never output a row that
2640 ** appears only in B.)
2641 **
2642 ** AltB: Called when there is data from both coroutines and A<B.
2643 **
2644 ** AeqB: Called when there is data from both coroutines and A==B.
2645 **
2646 ** AgtB: Called when there is data from both coroutines and A>B.
2647 **
2648 ** EofA: Called when data is exhausted from selectA.
2649 **
2650 ** EofB: Called when data is exhausted from selectB.
2651 **
2652 ** The implementation of the latter five subroutines depend on which
2653 ** <operator> is used:
2654 **
2655 **
2656 ** UNION ALL UNION EXCEPT INTERSECT
2657 ** ------------- ----------------- -------------- -----------------
2658 ** AltB: outA, nextA outA, nextA outA, nextA nextA
2659 **
2660 ** AeqB: outA, nextA nextA nextA outA, nextA
2661 **
2662 ** AgtB: outB, nextB outB, nextB nextB nextB
2663 **
2664 ** EofA: outB, nextB outB, nextB halt halt
2665 **
2666 ** EofB: outA, nextA outA, nextA outA, nextA halt
2667 **
2668 ** In the AltB, AeqB, and AgtB subroutines, an EOF on A following nextA
2669 ** causes an immediate jump to EofA and an EOF on B following nextB causes
2670 ** an immediate jump to EofB. Within EofA and EofB, and EOF on entry or
2671 ** following nextX causes a jump to the end of the select processing.
2672 **
2673 ** Duplicate removal in the UNION, EXCEPT, and INTERSECT cases is handled
2674 ** within the output subroutine. The regPrev register set holds the previously
2675 ** output value. A comparison is made against this value and the output
2676 ** is skipped if the next results would be the same as the previous.
2677 **
2678 ** The implementation plan is to implement the two coroutines and seven
2679 ** subroutines first, then put the control logic at the bottom. Like this:
2680 **
2681 ** goto Init
2682 ** coA: coroutine for left query (A)
2683 ** coB: coroutine for right query (B)
2684 ** outA: output one row of A
2685 ** outB: output one row of B (UNION and UNION ALL only)
2686 ** EofA: ...
2687 ** EofB: ...
2688 ** AltB: ...
2689 ** AeqB: ...
2690 ** AgtB: ...
2691 ** Init: initialize coroutine registers
2692 ** yield coA
2693 ** if eof(A) goto EofA
2694 ** yield coB
2695 ** if eof(B) goto EofB
2696 ** Cmpr: Compare A, B
2697 ** Jump AltB, AeqB, AgtB
2698 ** End: ...
2699 **
2700 ** We call AltB, AeqB, AgtB, EofA, and EofB "subroutines" but they are not
2701 ** actually called using Gosub and they do not Return. EofA and EofB loop
2702 ** until all data is exhausted then jump to the "end" labe. AltB, AeqB,
2703 ** and AgtB jump to either L2 or to one of EofA or EofB.
2704 */
2705 #ifndef SQLITE_OMIT_COMPOUND_SELECT
2710 ){
2745 #ifndef SQLITE_OMIT_EXPLAIN
2748 #endif
2759 /* Patch up the ORDER BY clause
2760 */
2768 /* For operators other than UNION ALL we have to make sure that
2769 ** the ORDER BY clause covers every term of the result set. Add
2770 ** terms to the ORDER BY clause as necessary.
2771 */
2778 }
2786 }
2787 }
2788 }
2790 /* Compute the comparison permutation and keyinfo that is used with
2791 ** the permutation used to determine if the next
2792 ** row of results comes from selectA or selectB. Also add explicit
2793 ** collations to the ORDER BY clause terms so that when the subqueries
2794 ** to the right and the left are evaluated, they use the correct
2795 ** collation.
2796 */
2804 }
2808 }
2810 /* Reattach the ORDER BY clause to the query.
2811 */
2815 /* Allocate a range of temporary registers and the KeyInfo needed
2816 ** for the logic that removes duplicate result rows when the
2817 ** operator is UNION, EXCEPT, or INTERSECT (but not UNION ALL).
2818 */
2833 }
2834 }
2835 }
2837 /* Separate the left and the right query from one another
2838 */
2844 }
2846 /* Compute the limit registers */
2852 regLimitA);
2856 }
2869 /* Generate a coroutine to evaluate the SELECT statement to the
2870 ** left of the compound operator - the "A" select.
2871 */
2881 /* Generate a coroutine to evaluate the SELECT statement on
2882 ** the right - the "B" select
2883 */
2897 /* Generate a subroutine that outputs the current row of the A
2898 ** select as the next output row of the compound select.
2899 */
2905 /* Generate a subroutine that outputs the current row of the B
2906 ** select as the next output row of the compound select.
2907 */
2913 }
2916 /* Generate a subroutine to run when the results from select A
2917 ** are exhausted and only data in select B remains.
2918 */
2928 }
2930 /* Generate a subroutine to run when the results from select B
2931 ** are exhausted and only data in select A remains.
2932 */
2941 }
2943 /* Generate code to handle the case of A<B
2944 */
2950 /* Generate code to handle the case of A==B
2951 */
2956 addrAltB++;
2959 addrAeqB =
2962 }
2964 /* Generate code to handle the case of A>B
2965 */
2970 }
2974 /* This code runs once to initialize everything.
2975 */
2980 /* Implement the main merge loop
2981 */
2989 /* Jump to the this point in order to terminate the query.
2990 */
2993 /* Set the number of output columns
2994 */
2999 }
3001 /* Reassembly the compound query so that it will be freed correctly
3002 ** by the calling function */
3005 }
3009 /*** TBD: Insert subroutine calls to close cursors on incomplete
3010 **** subqueries ****/
3013 }
3014 #endif
3016 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3017 /* Forward Declarations */
3021 /*
3022 ** Scan through the expression pExpr. Replace every reference to
3023 ** a column in table number iTable with a copy of the iColumn-th
3024 ** entry in pEList. (But leave references to the ROWID column
3025 ** unchanged.)
3026 **
3027 ** This routine is part of the flattening procedure. A subquery
3028 ** whose result set is defined by pEList appears as entry in the
3029 ** FROM clause of a SELECT such that the VDBE cursor assigned to that
3030 ** FORM clause entry is iTable. This routine make the necessary
3031 ** changes to pExpr so that it refers directly to the source table
3032 ** of the subquery rather the result set of the subquery.
3033 */
3039 ){
3051 }
3059 }
3060 }
3062 }
3068 ){
3073 }
3074 }
3080 ){
3096 }
3097 }
3098 }
3101 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3102 /*
3103 ** This routine attempts to flatten subqueries as a performance optimization.
3104 ** This routine returns 1 if it makes changes and 0 if no flattening occurs.
3105 **
3106 ** To understand the concept of flattening, consider the following
3107 ** query:
3108 **
3109 ** SELECT a FROM (SELECT x+y AS a FROM t1 WHERE z<100) WHERE a>5
3110 **
3111 ** The default way of implementing this query is to execute the
3112 ** subquery first and store the results in a temporary table, then
3113 ** run the outer query on that temporary table. This requires two
3114 ** passes over the data. Furthermore, because the temporary table
3115 ** has no indices, the WHERE clause on the outer query cannot be
3116 ** optimized.
3117 **
3118 ** This routine attempts to rewrite queries such as the above into
3119 ** a single flat select, like this:
3120 **
3121 ** SELECT x+y AS a FROM t1 WHERE z<100 AND a>5
3122 **
3123 ** The code generated for this simplification gives the same result
3124 ** but only has to scan the data once. And because indices might
3125 ** exist on the table t1, a complete scan of the data might be
3126 ** avoided.
3127 **
3128 ** Flattening is only attempted if all of the following are true:
3129 **
3130 ** (1) The subquery and the outer query do not both use aggregates.
3131 **
3132 ** (2) The subquery is not an aggregate or the outer query is not a join.
3133 **
3134 ** (3) The subquery is not the right operand of a left outer join
3135 ** (Originally ticket #306. Strengthened by ticket #3300)
3136 **
3137 ** (4) The subquery is not DISTINCT.
3138 **
3139 ** (**) At one point restrictions (4) and (5) defined a subset of DISTINCT
3140 ** sub-queries that were excluded from this optimization. Restriction
3141 ** (4) has since been expanded to exclude all DISTINCT subqueries.
3142 **
3143 ** (6) The subquery does not use aggregates or the outer query is not
3144 ** DISTINCT.
3145 **
3146 ** (7) The subquery has a FROM clause. TODO: For subqueries without
3147 ** A FROM clause, consider adding a FROM close with the special
3148 ** table sqlite_once that consists of a single row containing a
3149 ** single NULL.
3150 **
3151 ** (8) The subquery does not use LIMIT or the outer query is not a join.
3152 **
3153 ** (9) The subquery does not use LIMIT or the outer query does not use
3154 ** aggregates.
3155 **
3156 ** (**) Restriction (10) was removed from the code on 2005-02-05 but we
3157 ** accidently carried the comment forward until 2014-09-15. Original
3158 ** text: "The subquery does not use aggregates or the outer query does not
3159 ** use LIMIT."
3160 **
3161 ** (11) The subquery and the outer query do not both have ORDER BY clauses.
3162 **
3163 ** (**) Not implemented. Subsumed into restriction (3). Was previously
3164 ** a separate restriction deriving from ticket #350.
3165 **
3166 ** (13) The subquery and outer query do not both use LIMIT.
3167 **
3168 ** (14) The subquery does not use OFFSET.
3169 **
3170 ** (15) The outer query is not part of a compound select or the
3171 ** subquery does not have a LIMIT clause.
3172 ** (See ticket #2339 and ticket [02a8e81d44]).
3173 **
3174 ** (16) The outer query is not an aggregate or the subquery does
3175 ** not contain ORDER BY. (Ticket #2942) This used to not matter
3176 ** until we introduced the group_concat() function.
3177 **
3178 ** (17) The sub-query is not a compound select, or it is a UNION ALL
3179 ** compound clause made up entirely of non-aggregate queries, and
3180 ** the parent query:
3181 **
3182 ** * is not itself part of a compound select,
3183 ** * is not an aggregate or DISTINCT query, and
3184 ** * is not a join
3185 **
3186 ** The parent and sub-query may contain WHERE clauses. Subject to
3187 ** rules (11), (13) and (14), they may also contain ORDER BY,
3188 ** LIMIT and OFFSET clauses. The subquery cannot use any compound
3189 ** operator other than UNION ALL because all the other compound
3190 ** operators have an implied DISTINCT which is disallowed by
3191 ** restriction (4).
3192 **
3193 ** Also, each component of the sub-query must return the same number
3194 ** of result columns. This is actually a requirement for any compound
3195 ** SELECT statement, but all the code here does is make sure that no
3196 ** such (illegal) sub-query is flattened. The caller will detect the
3197 ** syntax error and return a detailed message.
3198 **
3199 ** (18) If the sub-query is a compound select, then all terms of the
3200 ** ORDER by clause of the parent must be simple references to
3201 ** columns of the sub-query.
3202 **
3203 ** (19) The subquery does not use LIMIT or the outer query does not
3204 ** have a WHERE clause.
3205 **
3206 ** (20) If the sub-query is a compound select, then it must not use
3207 ** an ORDER BY clause. Ticket #3773. We could relax this constraint
3208 ** somewhat by saying that the terms of the ORDER BY clause must
3209 ** appear as unmodified result columns in the outer query. But we
3210 ** have other optimizations in mind to deal with that case.
3211 **
3212 ** (21) The subquery does not use LIMIT or the outer query is not
3213 ** DISTINCT. (See ticket [752e1646fc]).
3214 **
3215 ** (22) The subquery is not a recursive CTE.
3216 **
3217 ** (23) The parent is not a recursive CTE, or the sub-query is not a
3218 ** compound query. This restriction is because transforming the
3219 ** parent to a compound query confuses the code that handles
3220 ** recursive queries in multiSelect().
3221 **
3222 ** (24) The subquery is not an aggregate that uses the built-in min() or
3223 ** or max() functions. (Without this restriction, a query like:
3224 ** "SELECT x FROM (SELECT max(y), x FROM t1)" would not necessarily
3225 ** return the value X for which Y was maximal.)
3226 **
3227 **
3228 ** In this routine, the "p" parameter is a pointer to the outer query.
3229 ** The subquery is p->pSrc->a[iFrom]. isAgg is true if the outer query
3230 ** uses aggregates and subqueryIsAgg is true if the subquery uses aggregates.
3231 **
3232 ** If flattening is not attempted, this routine is a no-op and returns 0.
3233 ** If flattening is attempted this routine returns 1.
3234 **
3235 ** All of the expression analysis must occur on both the outer query and
3236 ** the subquery before this routine runs.
3237 */
3244 ){
3258 /* Check to see if flattening is permitted. Return 0 if not.
3259 */
3273 /* Prior to version 3.1.2, when LIMIT and OFFSET had to be simple constants,
3274 ** not arbitrary expressions, we allowed some combining of LIMIT and OFFSET
3275 ** because they could be computed at compile-time. But when LIMIT and OFFSET
3276 ** became arbitrary expressions, we were forced to add restrictions (13)
3277 ** and (14). */
3282 }
3287 }
3290 }
3293 }
3298 }
3303 }
3306 }
3308 /* OBSOLETE COMMENT 1:
3309 ** Restriction 3: If the subquery is a join, make sure the subquery is
3310 ** not used as the right operand of an outer join. Examples of why this
3311 ** is not allowed:
3312 **
3313 ** t1 LEFT OUTER JOIN (t2 JOIN t3)
3314 **
3315 ** If we flatten the above, we would get
3316 **
3317 ** (t1 LEFT OUTER JOIN t2) JOIN t3
3318 **
3319 ** which is not at all the same thing.
3320 **
3321 ** OBSOLETE COMMENT 2:
3322 ** Restriction 12: If the subquery is the right operand of a left outer
3323 ** join, make sure the subquery has no WHERE clause.
3324 ** An examples of why this is not allowed:
3325 **
3326 ** t1 LEFT OUTER JOIN (SELECT * FROM t2 WHERE t2.x>0)
3327 **
3328 ** If we flatten the above, we would get
3329 **
3330 ** (t1 LEFT OUTER JOIN t2) WHERE t2.x>0
3331 **
3332 ** But the t2.x>0 test will always fail on a NULL row of t2, which
3333 ** effectively converts the OUTER JOIN into an INNER JOIN.
3334 **
3335 ** THIS OVERRIDES OBSOLETE COMMENTS 1 AND 2 ABOVE:
3336 ** Ticket #3300 shows that flattening the right term of a LEFT JOIN
3337 ** is fraught with danger. Best to avoid the whole thing. If the
3338 ** subquery is the right term of a LEFT JOIN, then do not flatten.
3339 */
3342 }
3344 /* Restriction 17: If the sub-query is a compound SELECT, then it must
3345 ** use only the UNION ALL operator. And none of the simple select queries
3346 ** that make up the compound SELECT are allowed to be aggregate or distinct
3347 ** queries.
3348 */
3352 }
3355 }
3364 ){
3366 }
3368 }
3370 /* Restriction 18. */
3375 }
3376 }
3377 }
3379 /***** If we reach this point, flattening is permitted. *****/
3383 /* Authorize the subquery */
3389 /* If the sub-query is a compound SELECT statement, then (by restrictions
3390 ** 17 and 18 above) it must be a UNION ALL and the parent query must
3391 ** be of the form:
3392 **
3393 ** SELECT <expr-list> FROM (<sub-query>) <where-clause>
3394 **
3395 ** followed by any ORDER BY, LIMIT and/or OFFSET clauses. This block
3396 ** creates N-1 copies of the parent query without any ORDER BY, LIMIT or
3397 ** OFFSET clauses and joins them to the left-hand-side of the original
3398 ** using UNION ALL operators. In this case N is the number of simple
3399 ** select statements in the compound sub-query.
3400 **
3401 ** Example:
3402 **
3403 ** SELECT a+1 FROM (
3404 ** SELECT x FROM tab
3405 ** UNION ALL
3406 ** SELECT y FROM tab
3407 ** UNION ALL
3408 ** SELECT abs(z*2) FROM tab2
3409 ** ) WHERE a!=5 ORDER BY 1
3410 **
3411 ** Transformed into:
3412 **
3413 ** SELECT x+1 FROM tab WHERE x+1!=5
3414 ** UNION ALL
3415 ** SELECT y+1 FROM tab WHERE y+1!=5
3416 ** UNION ALL
3417 ** SELECT abs(z*2)+1 FROM tab2 WHERE abs(z*2)+1!=5
3418 ** ORDER BY 1
3419 **
3420 ** We call this the "compound-subquery flattening".
3421 */
3450 }
3452 }
3454 /* Begin flattening the iFrom-th entry of the FROM clause
3455 ** in the outer query.
3456 */
3459 /* Delete the transient table structure associated with the
3460 ** subquery
3461 */
3470 /* Defer deleting the Table object associated with the
3471 ** subquery until code generation is
3472 ** complete, since there may still exist Expr.pTab entries that
3473 ** refer to the subquery even after flattening. Ticket #3346.
3474 **
3475 ** pSubitem->pTab is always non-NULL by test restrictions and tests above.
3476 */
3485 }
3487 }
3489 /* The following loop runs once for each term in a compound-subquery
3490 ** flattening (as described above). If we are doing a different kind
3491 ** of flattening - a flattening other than a compound-subquery flattening -
3492 ** then this loop only runs once.
3493 **
3494 ** This loop moves all of the FROM elements of the subquery into the
3495 ** the FROM clause of the outer query. Before doing this, remember
3496 ** the cursor number for the original outer query FROM element in
3497 ** iParent. The iParent cursor will never be used. Subsequent code
3498 ** will scan expressions looking for iParent references and replace
3499 ** those references with expressions that resolve to the subquery FROM
3500 ** elements we are now copying in.
3501 */
3518 }
3519 }
3521 /* The subquery uses a single slot of the FROM clause of the outer
3522 ** query. If the subquery has more than one element in its FROM clause,
3523 ** then expand the outer query to make space for it to hold all elements
3524 ** of the subquery.
3525 **
3526 ** Example:
3527 **
3528 ** SELECT * FROM tabA, (SELECT * FROM sub1, sub2), tabB;
3529 **
3530 ** The outer query has 3 slots in its FROM clause. One slot of the
3531 ** outer query (the middle slot) is used by the subquery. The next
3532 ** block of code will expand the out query to 4 slots. The middle
3533 ** slot is expanded to two slots in order to make space for the
3534 ** two elements in the FROM clause of the subquery.
3535 */
3540 }
3541 }
3543 /* Transfer the FROM clause terms from the subquery into the
3544 ** outer query.
3545 */
3550 }
3553 /* Now begin substituting subquery result set expressions for
3554 ** references to the iParent in the outer query.
3555 **
3556 ** Example:
3557 **
3558 ** SELECT a+5, b*10 FROM (SELECT x*3 AS a, y+10 AS b FROM t1) WHERE a>b;
3559 ** \ \_____________ subquery __________/ /
3560 ** \_____________________ outer query ______________________________/
3561 **
3562 ** We look at every expression in the outer query and every place we see
3563 ** "a" we substitute "x*3" and every place we see "b" we substitute "y+10".
3564 */
3571 }
3572 }
3577 }
3579 /* At this point, any non-zero iOrderByCol values indicate that the
3580 ** ORDER BY column expression is identical to the iOrderByCol'th
3581 ** expression returned by SELECT statement pSub. Since these values
3582 ** do not necessarily correspond to columns in SELECT statement pParent,
3583 ** zero them before transfering the ORDER BY clause.
3584 **
3585 ** Not doing this may cause an error if a subsequent call to this
3586 ** function attempts to flatten a compound sub-query into pParent
3587 ** (the only way this can happen is if the compound sub-query is
3588 ** currently part of pSub->pSrc). See ticket [d11a6e908f]. */
3592 }
3599 }
3604 }
3617 }
3619 /* The flattened query is distinct if either the inner or the
3620 ** outer query is distinct.
3621 */
3624 /*
3625 ** SELECT ... FROM (SELECT ... LIMIT a OFFSET b) LIMIT x OFFSET y;
3626 **
3627 ** One is tempted to try to add a and b to combine the limits. But this
3628 ** does not work if either limit is negative.
3629 */
3633 }
3634 }
3636 /* Finially, delete what is left of the subquery and return
3637 ** success.
3638 */
3641 #if SELECTTRACE_ENABLED
3645 }
3646 #endif
3649 }
3652 /*
3653 ** Based on the contents of the AggInfo structure indicated by the first
3654 ** argument, this function checks if the following are true:
3655 **
3656 ** * the query contains just a single aggregate function,
3657 ** * the aggregate function is either min() or max(), and
3658 ** * the argument to the aggregate function is a column value.
3659 **
3660 ** If all of the above are true, then WHERE_ORDERBY_MIN or WHERE_ORDERBY_MAX
3661 ** is returned as appropriate. Also, *ppMinMax is set to point to the
3662 ** list of arguments passed to the aggregate before returning.
3663 **
3664 ** Or, if the conditions above are not met, *ppMinMax is set to 0 and
3665 ** WHERE_ORDERBY_NORMAL is returned.
3666 */
3684 }
3685 }
3686 }
3690 }
3692 /*
3693 ** The select statement passed as the first argument is an aggregate query.
3694 ** The second argument is the associated aggregate-info object. This
3695 ** function tests if the SELECT is of the form:
3696 **
3697 ** SELECT count(*) FROM <tbl>
3698 **
3699 ** where table is a database table, not a sub-select or view. If the query
3700 ** does match this pattern, then a pointer to the Table object representing
3701 ** <tbl> is returned. Otherwise, 0 is returned.
3702 */
3711 ){
3713 }
3725 }
3727 /*
3728 ** If the source-list item passed as an argument was augmented with an
3729 ** INDEXED BY clause, then try to locate the specified index. If there
3730 ** was such a clause and the named index cannot be found, return
3731 ** SQLITE_ERROR and leave an error in pParse. Otherwise, populate
3732 ** pFrom->pIndex and return SQLITE_OK.
3733 */
3742 );
3747 }
3749 }
3751 }
3752 /*
3753 ** Detect compound SELECT statements that use an ORDER BY clause with
3754 ** an alternative collating sequence.
3755 **
3756 ** SELECT ... FROM t1 EXCEPT SELECT ... FROM t2 ORDER BY .. COLLATE ...
3757 **
3758 ** These are rewritten as a subquery:
3759 **
3760 ** SELECT * FROM (SELECT ... FROM t1 EXCEPT SELECT ... FROM t2)
3761 ** ORDER BY ... COLLATE ...
3762 **
3763 ** This transformation is necessary because the multiSelectOrderBy() routine
3764 ** above that generates the code for a compound SELECT with an ORDER BY clause
3765 ** uses a merge algorithm that requires the same collating sequence on the
3766 ** result columns as on the ORDER BY clause. See ticket
3767 ** http://www.sqlite.org/src/info/6709574d2a
3768 **
3769 ** This transformation is only needed for EXCEPT, INTERSECT, and UNION.
3770 ** The UNION ALL operator works fine with multiSelectOrderBy() even when
3771 ** there are COLLATE terms in the ORDER BY.
3772 */
3781 Token dummy;
3790 }
3793 /* If we reach this point, that means the transformation is required. */
3818 }
3820 #ifndef SQLITE_OMIT_CTE
3821 /*
3822 ** Argument pWith (which may be NULL) points to a linked list of nested
3823 ** WITH contexts, from inner to outermost. If the table identified by
3824 ** FROM clause element pItem is really a common-table-expression (CTE)
3825 ** then return a pointer to the CTE definition for that table. Otherwise
3826 ** return NULL.
3827 **
3828 ** If a non-NULL value is returned, set *ppContext to point to the With
3829 ** object that the returned CTE belongs to.
3830 */
3835 ){
3845 }
3846 }
3847 }
3848 }
3850 }
3852 /* The code generator maintains a stack of active WITH clauses
3853 ** with the inner-most WITH clause being at the top of the stack.
3854 **
3855 ** This routine pushes the WITH clause passed as the second argument
3856 ** onto the top of the stack. If argument bFree is true, then this
3857 ** WITH clause will never be popped from the stack. In this case it
3858 ** should be freed along with the Parse object. In other cases, when
3859 ** bFree==0, the With object will be freed along with the SELECT
3860 ** statement with which it is associated.
3861 */
3868 }
3869 }
3871 /*
3872 ** This function checks if argument pFrom refers to a CTE declared by
3873 ** a WITH clause on the stack currently maintained by the parser. And,
3874 ** if currently processing a CTE expression, if it is a recursive
3875 ** reference to the current CTE.
3876 **
3877 ** If pFrom falls into either of the two categories above, pFrom->pTab
3878 ** and other fields are populated accordingly. The caller should check
3879 ** (pFrom->pTab!=0) to determine whether or not a successful match
3880 ** was found.
3881 **
3882 ** Whether or not a match is found, SQLITE_OK is returned if no error
3883 ** occurs. If an error does occur, an error message is stored in the
3884 ** parser and some error code other than SQLITE_OK returned.
3885 */
3889 ){
3906 /* If pCte->zErr is non-NULL at this point, then this is an illegal
3907 ** recursive reference to CTE pCte. Leave an error in pParse and return
3908 ** early. If pCte->zErr is NULL, then this is not a recursive reference.
3909 ** In this case, proceed. */
3913 }
3927 /* Check if this is a recursive CTE. */
3938 ){
3943 }
3944 }
3945 }
3947 /* Only one recursive reference is permitted. */
3951 );
3953 }
3967 );
3970 }
3972 }
3980 }
3982 }
3985 }
3988 }
3989 #endif
3991 #ifndef SQLITE_OMIT_CTE
3992 /*
3993 ** If the SELECT passed as the second argument has an associated WITH
3994 ** clause, pop it from the stack stored as part of the Parse object.
3995 **
3996 ** This function is used as the xSelectCallback2() callback by
3997 ** sqlite3SelectExpand() when walking a SELECT tree to resolve table
3998 ** names and other FROM clause elements.
3999 */
4006 }
4007 }
4008 #else
4009 #define selectPopWith 0
4010 #endif
4012 /*
4013 ** This routine is a Walker callback for "expanding" a SELECT statement.
4014 ** "Expanding" means to do the following:
4015 **
4016 ** (1) Make sure VDBE cursor numbers have been assigned to every
4017 ** element of the FROM clause.
4018 **
4019 ** (2) Fill in the pTabList->a[].pTab fields in the SrcList that
4020 ** defines FROM clause. When views appear in the FROM clause,
4021 ** fill pTabList->a[].pSelect with a copy of the SELECT statement
4022 ** that implements the view. A copy is made of the view's SELECT
4023 ** statement so that we can freely modify or delete that statement
4024 ** without worrying about messing up the persistent representation
4025 ** of the view.
4026 **
4027 ** (3) Add terms to the WHERE clause to accommodate the NATURAL keyword
4028 ** on joins and the ON and USING clause of joins.
4029 **
4030 ** (4) Scan the list of columns in the result set (pEList) looking
4031 ** for instances of the "*" operator or the TABLE.* operator.
4032 ** If found, expand each "*" to be every column in every table
4033 ** and TABLE.* to be every column in TABLE.
4034 **
4035 */
4049 }
4052 }
4057 /* Make sure cursor numbers have been assigned to all entries in
4058 ** the FROM clause of the SELECT statement.
4059 */
4062 /* Look up every table named in the FROM clause of the select. If
4063 ** an entry of the FROM clause is a subquery instead of a table or view,
4064 ** then create a transient table structure to describe the subquery.
4065 */
4071 /* This statement has already been prepared. There is no need
4072 ** to go further. */
4074 #ifndef SQLITE_OMIT_CTE
4076 #endif
4078 }
4079 #ifndef SQLITE_OMIT_CTE
4082 #endif
4084 #ifndef SQLITE_OMIT_SUBQUERY
4086 /* A sub-query in the FROM clause of a SELECT */
4099 #endif
4101 /* An ordinary table or view name in the FROM clause */
4110 }
4112 #if !defined(SQLITE_OMIT_VIEW) || !defined (SQLITE_OMIT_VIRTUALTABLE)
4114 /* We reach here if the named table is a really a view */
4120 }
4121 #endif
4122 }
4124 /* Locate the index named by the INDEXED BY clause, if any. */
4127 }
4128 }
4130 /* Process NATURAL keywords, and ON and USING clauses of joins.
4131 */
4134 }
4136 /* For every "*" that occurs in the column list, insert the names of
4137 ** all columns in all tables. And for every TABLE.* insert the names
4138 ** of all columns in TABLE. The parser inserted a special expression
4139 ** with the TK_ALL operator for each "*" that it found in the column list.
4140 ** The following code just has to locate the TK_ALL expressions and expand
4141 ** each one to the list of all columns in all tables.
4142 **
4143 ** The first loop just checks to see if there are any "*" operators
4144 ** that need expanding.
4145 */
4152 }
4154 /*
4155 ** If we get here it means the result set contains one or more "*"
4156 ** operators that need to be expanded. Loop through each expression
4157 ** in the result set and expand them one by one.
4158 */
4165 /* When processing FROM-clause subqueries, it is always the case
4166 ** that full_column_names=OFF and short_column_names=ON. The
4167 ** sqlite3ResultSetOfSelect() routine makes it so. */
4177 /* This particular expression does not need to be expanded.
4178 */
4185 }
4188 /* This expression is a "*" or a "TABLE.*" and needs to be
4189 ** expanded. */
4196 }
4205 }
4211 }
4214 }
4224 ){
4226 }
4228 /* If a column is marked as 'hidden' (currently only possible
4229 ** for virtual tables), do not include it in the expanded
4230 ** result-set list.
4231 */
4235 }
4241 ){
4242 /* In a NATURAL join, omit the join columns from the
4243 ** table to the right of the join */
4245 }
4247 /* In a join with a USING clause, omit columns in the
4248 ** using clause from the table on the right. */
4250 }
4251 }
4262 }
4266 }
4269 }
4283 }
4285 }
4287 }
4288 }
4294 }
4295 }
4296 }
4297 }
4300 }
4301 #if SQLITE_MAX_COLUMN
4304 }
4305 #endif
4307 }
4309 /*
4310 ** No-op routine for the parse-tree walker.
4311 **
4312 ** When this routine is the Walker.xExprCallback then expression trees
4313 ** are walked without any actions being taken at each node. Presumably,
4314 ** when this routine is used for Walker.xExprCallback then
4315 ** Walker.xSelectCallback is set to do something useful for every
4316 ** subquery in the parser tree.
4317 */
4321 }
4323 /*
4324 ** This routine "expands" a SELECT statement and all of its subqueries.
4325 ** For additional information on what it means to "expand" a SELECT
4326 ** statement, see the comment on the selectExpand worker callback above.
4327 **
4328 ** Expanding a SELECT statement is the first step in processing a
4329 ** SELECT statement. The SELECT statement must be expanded before
4330 ** name resolution is performed.
4331 **
4332 ** If anything goes wrong, an error message is written into pParse.
4333 ** The calling function can detect the problem by looking at pParse->nErr
4334 ** and/or pParse->db->mallocFailed.
4335 */
4337 Walker w;
4344 }
4348 }
4351 #ifndef SQLITE_OMIT_SUBQUERY
4352 /*
4353 ** This is a Walker.xSelectCallback callback for the sqlite3SelectTypeInfo()
4354 ** interface.
4355 **
4356 ** For each FROM-clause subquery, add Column.zType and Column.zColl
4357 ** information to the Table structure that represents the result set
4358 ** of that subquery.
4359 **
4360 ** The Table structure that represents the result set was constructed
4361 ** by selectExpander() but the type and collation information was omitted
4362 ** at that point because identifiers had not yet been resolved. This
4363 ** routine is called after identifier resolution.
4364 */
4379 /* A sub-query in the FROM clause of a SELECT */
4384 }
4385 }
4386 }
4387 }
4388 }
4389 #endif
4392 /*
4393 ** This routine adds datatype and collating sequence information to
4394 ** the Table structures of all FROM-clause subqueries in a
4395 ** SELECT statement.
4396 **
4397 ** Use this routine after name resolution.
4398 */
4400 #ifndef SQLITE_OMIT_SUBQUERY
4401 Walker w;
4407 #endif
4408 }
4411 /*
4412 ** This routine sets up a SELECT statement for processing. The
4413 ** following is accomplished:
4414 **
4415 ** * VDBE Cursor numbers are assigned to all FROM-clause terms.
4416 ** * Ephemeral Table objects are created for all FROM-clause subqueries.
4417 ** * ON and USING clauses are shifted into WHERE statements
4418 ** * Wildcards "*" and "TABLE.*" in result sets are expanded.
4419 ** * Identifiers in expression are matched to tables.
4420 **
4421 ** This routine acts recursively on all subqueries within the SELECT.
4422 */
4427 ){
4438 }
4440 /*
4441 ** Reset the aggregate accumulator.
4442 **
4443 ** The aggregate accumulator is a set of memory cells that hold
4444 ** intermediate results while calculating an aggregate. This
4445 ** routine generates code that stores NULLs in all of those memory
4446 ** cells.
4447 */
4454 #ifdef SQLITE_DEBUG
4455 /* Verify that all AggInfo registers are within the range specified by
4456 ** AggInfo.mnReg..AggInfo.mxReg */
4461 }
4465 }
4466 #endif
4480 }
4481 }
4482 }
4483 }
4485 /*
4486 ** Invoke the OP_AggFinalize opcode for every aggregate function
4487 ** in the AggInfo structure.
4488 */
4498 }
4499 }
4501 /*
4502 ** Update the accumulator memory cells for an aggregate based on
4503 ** the current cursor position.
4504 */
4527 }
4532 }
4540 }
4543 }
4546 }
4555 }
4556 }
4558 /* Before populating the accumulator registers, clear the column cache.
4559 ** Otherwise, if any of the required column values are already present
4560 ** in registers, sqlite3ExprCode() may use OP_SCopy to copy the value
4561 ** to pC->iMem. But by the time the value is used, the original register
4562 ** may have been used, invalidating the underlying buffer holding the
4563 ** text or blob value. See ticket [883034dcb5].
4564 **
4565 ** Another solution would be to change the OP_SCopy used to copy cached
4566 ** values to an OP_Copy.
4567 */
4570 }
4574 }
4579 }
4580 }
4582 /*
4583 ** Add a single OP_Explain instruction to the VDBE to explain a simple
4584 ** count(*) query ("SELECT count(*) FROM pTab").
4585 */
4586 #ifndef SQLITE_OMIT_EXPLAIN
4591 ){
4598 );
4601 );
4602 }
4603 }
4604 #else
4605 # define explainSimpleCount(a,b,c)
4606 #endif
4608 /*
4609 ** Generate code for the SELECT statement given in the p argument.
4610 **
4611 ** The results are returned according to the SelectDest structure.
4612 ** See comments in sqliteInt.h for further information.
4613 **
4614 ** This routine returns the number of errors. If any errors are
4615 ** encountered, then an appropriate error message is left in
4616 ** pParse->zErrMsg.
4617 **
4618 ** This routine does NOT free the Select structure passed in. The
4619 ** calling function needs to do that.
4620 */
4625 ){
4642 #ifndef SQLITE_OMIT_EXPLAIN
4645 #endif
4650 }
4653 #if SELECTTRACE_ENABLED
4658 }
4659 #endif
4670 /* If ORDER BY makes no difference in the output then neither does
4671 ** DISTINCT so it can be removed too. */
4675 }
4683 }
4687 /* Begin generating code.
4688 */
4692 /* If writing to memory or generating a set
4693 ** only a single column may be output.
4694 */
4695 #ifndef SQLITE_OMIT_SUBQUERY
4698 }
4699 #endif
4701 /* Generate code for all sub-queries in the FROM clause
4702 */
4703 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
4706 SelectDest dest;
4712 /* Sometimes the code for a subquery will be generated more than
4713 ** once, if the subquery is part of the WHERE clause in a LEFT JOIN,
4714 ** for example. In that case, do not regenerate the code to manifest
4715 ** a view or the co-routine to implement a view. The first instance
4716 ** is sufficient, though the subroutine to manifest the view does need
4717 ** to be invoked again. */
4721 }
4723 }
4725 /* Increment Parse.nHeight by the height of the largest expression
4726 ** tree referred to by this, the parent select. The child select
4727 ** may contain expression trees of at most
4728 ** (SQLITE_MAX_EXPR_DEPTH-Parse.nHeight) height. This is a bit
4729 ** more conservative than necessary, but much easier than enforcing
4730 ** an exact limit.
4731 */
4736 /* This subquery can be absorbed into its parent. */
4740 }
4744 ){
4745 /* Implement a co-routine that will return a single row of the result
4746 ** set on each invocation.
4747 */
4763 /* Generate a subroutine that will fill an ephemeral table with
4764 ** the content of this subquery. pItem->addrFillSub will point
4765 ** to the address of the generated subroutine. pItem->regReturn
4766 ** is a register allocated to hold the subroutine return address
4767 */
4776 /* If the subquery is not correlated and if we are not inside of
4777 ** a trigger, then we only need to compute the value of the subquery
4778 ** once. */
4783 }
4793 }
4796 }
4801 }
4802 }
4804 #endif
4810 #ifndef SQLITE_OMIT_COMPOUND_SELECT
4811 /* If there is are a sequence of queries, do the earlier ones first.
4812 */
4816 #if SELECTTRACE_ENABLED
4819 #endif
4821 }
4822 #endif
4824 /* If the query is DISTINCT with an ORDER BY but is not an aggregate, and
4825 ** if the select-list is the same as the ORDER BY list, then this query
4826 ** can be rewritten as a GROUP BY. In other words, this:
4827 **
4828 ** SELECT DISTINCT xyz FROM ... ORDER BY xyz
4829 **
4830 ** is transformed to:
4831 **
4832 ** SELECT xyz FROM ... GROUP BY xyz
4833 **
4834 ** The second form is preferred as a single index (or temp-table) may be
4835 ** used for both the ORDER BY and DISTINCT processing. As originally
4836 ** written the query must use a temp-table for at least one of the ORDER
4837 ** BY and DISTINCT, and an index or separate temp-table for the other.
4838 */
4841 ){
4846 /* Notice that even thought SF_Distinct has been cleared from p->selFlags,
4847 ** the sDistinct.isTnct is still set. Hence, isTnct represents the
4848 ** original setting of the SF_Distinct flag, not the current setting */
4850 }
4852 /* If there is an ORDER BY clause, then this sorting
4853 ** index might end up being unused if the data can be
4854 ** extracted in pre-sorted order. If that is the case, then the
4855 ** OP_OpenEphemeral instruction will be changed to an OP_Noop once
4856 ** we figure out that the sorting index is not needed. The addrSortIndex
4857 ** variable is used to facilitate that change.
4858 */
4867 );
4870 }
4872 /* If the output is destined for a temporary table, open that table.
4873 */
4876 }
4878 /* Set the limiter.
4879 */
4886 }
4888 /* Open a virtual index to use for the distinct set.
4889 */
4895 P4_KEYINFO);
4900 }
4903 /* No aggregate functions and no GROUP BY clause */
4906 /* Begin the database scan. */
4912 }
4915 }
4920 }
4921 }
4923 /* If sorting index that was created by a prior OP_OpenEphemeral
4924 ** instruction ended up not being needed, then change the OP_OpenEphemeral
4925 ** into an OP_Noop.
4926 */
4929 }
4931 /* Use the standard inner loop. */
4936 /* End the database scan loop.
4937 */
4940 /* This case when there exist aggregate functions or a GROUP BY clause
4941 ** or both */
4946 ** one row of the input to the aggregator has been
4947 ** processed */
4955 /* Remove any and all aliases between the result set and the
4956 ** GROUP BY clause.
4957 */
4964 }
4967 }
4971 }
4974 /* If there is both a GROUP BY and an ORDER BY clause and they are
4975 ** identical, then it may be possible to disable the ORDER BY clause
4976 ** on the grounds that the GROUP BY will cause elements to come out
4977 ** in the correct order. It also may not - the GROUP BY may use a
4978 ** database index that causes rows to be grouped together as required
4979 ** but not actually sorted. Either way, record the fact that the
4980 ** ORDER BY and GROUP BY clauses are the same by setting the orderByGrp
4981 ** variable. */
4984 }
4986 /* Create a label to jump to when we want to abort the query */
4989 /* Convert TK_COLUMN nodes into TK_AGG_COLUMN and make entries in
4990 ** sAggInfo for all TK_AGG_FUNCTION nodes in expressions of the
4991 ** SELECT statement.
4992 */
5004 }
5011 }
5015 /* Processing for aggregates with GROUP BY is very different and
5016 ** much more complex than aggregates without a GROUP BY.
5017 */
5029 /* If there is a GROUP BY clause we might need a sorting index to
5030 ** implement it. Allocate that sorting index now. If it turns out
5031 ** that we do not need it after all, the OP_SorterOpen instruction
5032 ** will be converted into a Noop.
5033 */
5040 /* Initialize memory locations used by GROUP BY aggregate processing
5041 */
5058 /* Begin a loop that will extract all source rows in GROUP BY order.
5059 ** This might involve two separate loops with an OP_Sort in between, or
5060 ** it might be a single loop that uses an index to extract information
5061 ** in the right order to begin with.
5062 */
5066 );
5069 /* The optimizer is able to deliver rows in group by order so
5070 ** we do not have to sort. The OP_OpenEphemeral table will be
5071 ** cancelled later because we still need to use the pKeyInfo
5072 */
5075 /* Rows are coming out in undetermined order. We have to push
5076 ** each row into a sorting index, terminate the first loop,
5077 ** then loop over the sorting index in order to get the output
5078 ** in sorted order
5079 */
5095 nCol++;
5096 j++;
5097 }
5098 }
5113 }
5114 j++;
5115 }
5116 }
5131 }
5133 /* If the index or temporary table used by the GROUP BY sort
5134 ** will naturally deliver rows in the order required by the ORDER BY
5135 ** clause, cancel the ephemeral table open coded earlier.
5136 **
5137 ** This is an optimization - the correct answer should result regardless.
5138 ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER to
5139 ** disable this optimization for testing purposes. */
5142 ){
5145 }
5147 /* Evaluate the current GROUP BY terms and store in b0, b1, b2...
5148 ** (b0 is memory location iBMem+0, b1 is iBMem+1, and so forth)
5149 ** Then compare the current GROUP BY terms against the GROUP BY terms
5150 ** from the previous row currently stored in a0, a1, a2...
5151 */
5156 }
5163 }
5164 }
5170 /* Generate code that runs whenever the GROUP BY changes.
5171 ** Changes in the GROUP BY are detected by the previous code
5172 ** block. If there were no changes, this block is skipped.
5173 **
5174 ** This code copies current group by terms in b0,b1,b2,...
5175 ** over to a0,a1,a2. It then calls the output subroutine
5176 ** and resets the aggregate accumulator registers in preparation
5177 ** for the next GROUP BY batch.
5178 */
5187 /* Update the aggregate accumulators based on the content of
5188 ** the current row
5189 */
5195 /* End of the loop
5196 */
5203 }
5205 /* Output the final row of result
5206 */
5210 /* Jump over the subroutines
5211 */
5214 /* Generate a subroutine that outputs a single row of the result
5215 ** set. This subroutine first looks at the iUseFlag. If iUseFlag
5216 ** is less than or equal to zero, the subroutine is a no-op. If
5217 ** the processing calls for the query to abort, this subroutine
5218 ** increments the iAbortFlag memory location before returning in
5219 ** order to signal the caller to abort.
5220 */
5238 /* Generate a subroutine that will reset the group-by accumulator
5239 */
5247 #ifndef SQLITE_OMIT_BTREECOUNT
5250 /* If isSimpleCount() returns a pointer to a Table structure, then
5251 ** the SQL statement is of the form:
5252 **
5253 ** SELECT count(*) FROM <tbl>
5254 **
5255 ** where the Table structure returned represents table <tbl>.
5256 **
5257 ** This statement is so common that it is optimized specially. The
5258 ** OP_Count instruction is executed either on the intkey table that
5259 ** contains the data for table <tbl> or on one of its indexes. It
5260 ** is better to execute the op on an index, as indexes are almost
5261 ** always spread across less pages than their corresponding tables.
5262 */
5273 /* Search for the index that has the lowest scan cost.
5274 **
5275 ** (2011-04-15) Do not do a full scan of an unordered index.
5276 **
5277 ** (2013-10-03) Do not count the entries in a partial index.
5278 **
5279 ** In practice the KeyInfo structure will not be used. It is only
5280 ** passed to keep OP_OpenRead happy.
5281 */
5288 ){
5290 }
5291 }
5295 }
5297 /* Open a read-only cursor, execute the OP_Count, close the cursor. */
5301 }
5307 {
5308 /* Check if the query is of one of the following forms:
5309 **
5310 ** SELECT min(x) FROM ...
5311 ** SELECT max(x) FROM ...
5312 **
5313 ** If it is, then ask the code in where.c to attempt to sort results
5314 ** as if there was an "ORDER ON x" or "ORDER ON x DESC" clause.
5315 ** If where.c is able to produce results sorted in this order, then
5316 ** add vdbe code to break out of the processing loop after the
5317 ** first iteration (since the first iteration of the loop is
5318 ** guaranteed to operate on the row with the minimum or maximum
5319 ** value of x, the only row required).
5320 **
5321 ** A special flag must be passed to sqlite3WhereBegin() to slightly
5322 ** modify behavior as follows:
5323 **
5324 ** + If the query is a "SELECT min(x)", then the loop coded by
5325 ** where.c should not iterate over any values with a NULL value
5326 ** for x.
5327 **
5328 ** + The optimizer code in where.c (the thing that decides which
5329 ** index or indices to use) should place a different priority on
5330 ** satisfying the 'ORDER BY' clause than it does in other cases.
5331 ** Refer to code and comments in where.c for details.
5332 */
5340 }
5349 }
5350 }
5352 /* This case runs if the aggregate has no GROUP BY clause. The
5353 ** processing is much simpler since there is only a single row
5354 ** of output.
5355 */
5361 }
5368 }
5371 }
5378 }
5385 }
5387 /* If there is an ORDER BY clause, then we need to sort the results
5388 ** and send them to the callback one by one.
5389 */
5393 }
5395 /* Jump here to skip this query
5396 */
5399 /* The SELECT was successfully coded. Set the return code to 0
5400 ** to indicate no errors.
5401 */
5404 /* Control jumps to here if an error is encountered above, or upon
5405 ** successful coding of the SELECT.
5406 */
5407 select_end:
5410 /* Identify column names if results of the SELECT are to be output.
5411 */
5414 }
5418 #if SELECTTRACE_ENABLED
5421 #endif
5423 }
5425 #ifdef SQLITE_DEBUG
5426 /*
5427 ** Generate a human-readable description of a the Select object.
5428 */
5435 );
5451 StrAccum x;
5459 }
5462 }
5465 }
5468 }
5473 }
5475 }
5477 }
5482 }
5485 }
5490 }
5493 }
5498 }
5503 }
5510 }
5514 }
5516 }