| blob | 6719d474718f08fbed67aab1caa65365d870db0b |
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 ** An instance of the following object is used to record information about
19 ** how to process the DISTINCT keyword, to simplify passing that information
20 ** into the selectInnerLoop() routine.
21 */
28 };
30 /*
31 ** An instance of the following object is used to record information about
32 ** the ORDER BY (or GROUP BY) clause of query is being coded.
33 **
34 ** The aDefer[] array is used by the sorter-references optimization. For
35 ** example, assuming there is no index that can be used for the ORDER BY,
36 ** for the query:
37 **
38 ** SELECT a, bigblob FROM t1 ORDER BY a LIMIT 10;
39 **
40 ** it may be more efficient to add just the "a" values to the sorter, and
41 ** retrieve the associated "bigblob" values directly from table t1 as the
42 ** 10 smallest "a" values are extracted from the sorter.
43 **
44 ** When the sorter-reference optimization is used, there is one entry in the
45 ** aDefer[] array for each database table that may be read as values are
46 ** extracted from the sorter.
47 */
59 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
66 #endif
68 };
71 /*
72 ** Delete all the content of a Select structure. Deallocate the structure
73 ** itself depending on the value of bFree
74 **
75 ** If bFree==1, call sqlite3DbFree() on the p object.
76 ** If bFree==0, Leave the first Select object unfreed
77 */
89 #ifndef SQLITE_OMIT_WINDOWFUNC
92 }
96 }
97 #endif
101 }
102 }
104 /*
105 ** Initialize a SelectDest structure.
106 */
114 }
117 /*
118 ** Allocate a new Select structure and return a pointer to that
119 ** structure.
120 */
131 ){
133 Select standin;
138 }
142 }
162 #ifndef SQLITE_OMIT_WINDOWFUNC
165 #endif
171 }
173 }
176 /*
177 ** Delete the given Select structure and all of its substructures.
178 */
181 }
183 /*
184 ** Return a pointer to the right-most SELECT statement in a compound.
185 */
189 }
191 /*
192 ** Given 1 to 3 identifiers preceding the JOIN keyword, determine the
193 ** type of join. Return an integer constant that expresses that type
194 ** in terms of the following bit values:
195 **
196 ** JT_INNER
197 ** JT_CROSS
198 ** JT_OUTER
199 ** JT_NATURAL
200 ** JT_LEFT
201 ** JT_RIGHT
202 **
203 ** A full outer join is the combination of JT_LEFT and JT_RIGHT.
204 **
205 ** If an illegal or unsupported join type is seen, then still return
206 ** a join type, but put an error in the pParse structure.
207 */
212 /* 0123456789 123456789 123456789 123 */
226 };
238 }
239 }
244 }
245 }
249 ){
261 }
263 }
265 /*
266 ** Return the index of a column in a table. Return -1 if the column
267 ** is not contained in the table.
268 */
275 }
277 }
279 /*
280 ** Search the first N tables in pSrc, from left to right, looking for a
281 ** table that has a column named zCol.
282 **
283 ** When found, set *piTab and *piCol to the table index and column index
284 ** of the matching column and return TRUE.
285 **
286 ** If not found, return FALSE.
287 */
295 ){
304 ){
308 }
310 }
311 }
313 }
315 /*
316 ** This function is used to add terms implied by JOIN syntax to the
317 ** WHERE clause expression of a SELECT statement. The new term, which
318 ** is ANDed with the existing WHERE clause, is of the form:
319 **
320 ** (tab1.col1 = tab2.col2)
321 **
322 ** where tab1 is the iSrc'th table in SrcList pSrc and tab2 is the
323 ** (iSrc+1)'th. Column col1 is column iColLeft of tab1, and col2 is
324 ** column iColRight of tab2.
325 */
335 ){
351 ** in sqlite3DbMallocRawNN() called from
352 ** sqlite3PExpr(). */
358 }
360 }
362 /*
363 ** Set the EP_FromJoin property on all terms of the given expression.
364 ** And set the Expr.w.iRightJoinTable to iTable for every term in the
365 ** expression.
366 **
367 ** The EP_FromJoin property is used on terms of an expression to tell
368 ** the LEFT OUTER JOIN processing logic that this term is part of the
369 ** join restriction specified in the ON or USING clause and not a part
370 ** of the more general WHERE clause. These terms are moved over to the
371 ** WHERE clause during join processing but we need to remember that they
372 ** originated in the ON or USING clause.
373 **
374 ** The Expr.w.iRightJoinTable tells the WHERE clause processing that the
375 ** expression depends on table w.iRightJoinTable even if that table is not
376 ** explicitly mentioned in the expression. That information is needed
377 ** for cases like this:
378 **
379 ** SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.b AND t1.x=5
380 **
381 ** The where clause needs to defer the handling of the t1.x=5
382 ** term until after the t2 loop of the join. In that way, a
383 ** NULL t2 row will be inserted whenever t1.x!=5. If we do not
384 ** defer the handling of t1.x=5, it will be processed immediately
385 ** after the t1 loop and rows with t1.x!=5 will never appear in
386 ** the output, which is incorrect.
387 */
400 }
401 }
402 }
405 }
406 }
408 /* Undo the work of sqlite3SetJoinExpr(). In the expression p, convert every
409 ** term that is marked with EP_FromJoin and w.iRightJoinTable==iTable into
410 ** an ordinary term that omits the EP_FromJoin mark.
411 **
412 ** This happens when a LEFT JOIN is simplified into an ordinary JOIN.
413 */
419 }
422 }
429 }
430 }
431 }
434 }
435 }
437 /*
438 ** This routine processes the join information for a SELECT statement.
439 ** ON and USING clauses are converted into extra terms of the WHERE clause.
440 ** NATURAL joins also create extra WHERE clause terms.
441 **
442 ** The terms of a FROM clause are contained in the Select.pSrc structure.
443 ** The left most table is the first entry in Select.pSrc. The right-most
444 ** table is the last entry. The join operator is held in the entry to
445 ** the left. Thus entry 0 contains the join operator for the join between
446 ** entries 0 and 1. Any ON or USING clauses associated with the join are
447 ** also attached to the left entry.
448 **
449 ** This routine returns the number of errors encountered.
450 */
467 /* When the NATURAL keyword is present, add WHERE clause terms for
468 ** every column that the two tables have in common.
469 */
475 }
486 }
487 }
488 }
490 /* Disallow both ON and USING clauses in the same join
491 */
496 }
498 /* Add the ON clause to the end of the WHERE clause, connected by
499 ** an AND operator.
500 */
505 }
507 /* Create extra terms on the WHERE clause for each column named
508 ** in the USING clause. Example: If the two tables to be joined are
509 ** A and B and the USING clause names X, Y, and Z, then add this
510 ** to the WHERE clause: A.X=B.X AND A.Y=B.Y AND A.Z=B.Z
511 ** Report an error if any column mentioned in the USING clause is
512 ** not contained in both tables to be joined.
513 */
526 ){
530 }
533 }
534 }
535 }
537 }
539 /*
540 ** An instance of this object holds information (beyond pParse and pSelect)
541 ** needed to load the next result row that is to be added to the sorter.
542 */
547 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
550 #endif
551 };
553 /*
554 ** This routine does the work of loading query data into an array of
555 ** registers so that it can be added to the sorter.
556 */
561 ){
564 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
568 }
569 #endif
570 }
572 /*
573 ** Code the OP_MakeRecord instruction that generates the entry to be
574 ** added into the sorter.
575 **
576 ** Return the register in which the result is stored.
577 */
583 int nBase
584 ){
590 }
593 }
595 /*
596 ** Generate code that will push the record in registers regData
597 ** through regData+nData-1 onto the sorter.
598 */
607 ){
621 /* Three cases:
622 ** (1) The data to be sorted has already been packed into a Record
623 ** by a prior OP_MakeRecord. In this case nData==1 and regData
624 ** will be completely unrelated to regOrigData.
625 ** (2) All output columns are included in the sort record. In that
626 ** case regData==regOrigData.
627 ** (3) Some output columns are omitted from the sort record due to
628 ** the SQLITE_ENABLE_SORTER_REFERENCE optimization, or due to the
629 ** SQLITE_ECEL_OMITREF optimization, or due to the
630 ** SortCtx.pDeferredRowLoad optimiation. In any of these cases
631 ** regOrigData is 0 to prevent this routine from trying to copy
632 ** values that might not yet exist.
633 */
642 }
650 }
653 }
670 }
692 }
696 }
698 /* At this point the values for the new sorter entry are stored
699 ** in an array of registers. They need to be composed into a record
700 ** and inserted into the sorter if either (a) there are currently
701 ** less than LIMIT+OFFSET items or (b) the new record is smaller than
702 ** the largest record currently in the sorter. If (b) is true and there
703 ** are already LIMIT+OFFSET items in the sorter, delete the largest
704 ** entry before inserting the new one. This way there are never more
705 ** than LIMIT+OFFSET items in the sorter.
706 **
707 ** If the new record does not need to be inserted into the sorter,
708 ** jump to the next iteration of the loop. If the pSort->labelOBLopt
709 ** value is not zero, then it is a label of where to jump. Otherwise,
710 ** just bypass the row insert logic. See the header comment on the
711 ** sqlite3WhereOrderByLimitOptLabel() function for additional info.
712 */
721 }
724 }
729 }
735 }
736 }
738 /*
739 ** Add code to implement the OFFSET
740 */
745 ){
749 }
750 }
752 /*
753 ** Add code that will check to make sure the array of registers starting at
754 ** iMem form a distinct entry. This is used by both "SELECT DISTINCT ..." and
755 ** distinct aggregates ("SELECT count(DISTINCT <expr>) ..."). Three strategies
756 ** are available. Which is used depends on the value of parameter eTnctType,
757 ** as follows:
758 **
759 ** WHERE_DISTINCT_UNORDERED/WHERE_DISTINCT_NOOP:
760 ** Build an ephemeral table that contains all entries seen before and
761 ** skip entries which have been seen before.
762 **
763 ** Parameter iTab is the cursor number of an ephemeral table that must
764 ** be opened before the VM code generated by this routine is executed.
765 ** The ephemeral cursor table is queried for a record identical to the
766 ** record formed by the current array of registers. If one is found,
767 ** jump to VM address addrRepeat. Otherwise, insert a new record into
768 ** the ephemeral cursor and proceed.
769 **
770 ** The returned value in this case is a copy of parameter iTab.
771 **
772 ** WHERE_DISTINCT_ORDERED:
773 ** In this case rows are being delivered sorted order. The ephermal
774 ** table is not required. Instead, the current set of values
775 ** is compared against previous row. If they match, the new row
776 ** is not distinct and control jumps to VM address addrRepeat. Otherwise,
777 ** the VM program proceeds with processing the new row.
778 **
779 ** The returned value in this case is the register number of the first
780 ** in an array of registers used to store the previous result row so that
781 ** it can be compared to the next. The caller must ensure that this
782 ** register is initialized to NULL. (The fixDistinctOpenEph() routine
783 ** will take care of this initialization.)
784 **
785 ** WHERE_DISTINCT_UNIQUE:
786 ** In this case it has already been determined that the rows are distinct.
787 ** No special action is required. The return value is zero.
788 **
789 ** Parameter pEList is the list of expressions used to generated the
790 ** contents of each row. It is used by this routine to determine (a)
791 ** how many elements there are in the array of registers and (b) the
792 ** collation sequences that should be used for the comparisons if
793 ** eTnctType is WHERE_DISTINCT_ORDERED.
794 */
802 ){
813 /* Allocate space for the previous row */
826 }
829 }
833 }
836 /* nothing to do */
838 }
850 }
851 }
854 }
856 /*
857 ** This routine runs after codeDistinct(). It makes necessary
858 ** adjustments to the OP_OpenEphemeral opcode that the codeDistinct()
859 ** routine made use of. This processing must be done separately since
860 ** sometimes codeDistinct is called before the OP_OpenEphemeral is actually
861 ** laid down.
862 **
863 ** WHERE_DISTINCT_NOOP:
864 ** WHERE_DISTINCT_UNORDERED:
865 **
866 ** No adjustments necessary. This function is a no-op.
867 **
868 ** WHERE_DISTINCT_UNIQUE:
869 **
870 ** The ephemeral table is not needed. So change the
871 ** OP_OpenEphemeral opcode into an OP_Noop.
872 **
873 ** WHERE_DISTINCT_ORDERED:
874 **
875 ** The ephemeral table is not needed. But we do need register
876 ** iVal to be initialized to NULL. So change the OP_OpenEphemeral
877 ** into an OP_Null on the iVal register.
878 */
884 ){
887 ){
892 }
894 /* Change the OP_OpenEphemeral to an OP_Null that sets the MEM_Cleared
895 ** bit on the first register of the previous value. This will cause the
896 ** OP_Ne added in codeDistinct() to always fail on the first iteration of
897 ** the loop even if the first row is all NULLs. */
902 }
903 }
904 }
906 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
907 /*
908 ** This function is called as part of inner-loop generation for a SELECT
909 ** statement with an ORDER BY that is not optimized by an index. It
910 ** determines the expressions, if any, that the sorter-reference
911 ** optimization should be used for. The sorter-reference optimization
912 ** is used for SELECT queries like:
913 **
914 ** SELECT a, bigblob FROM t1 ORDER BY a LIMIT 10
915 **
916 ** If the optimization is used for expression "bigblob", then instead of
917 ** storing values read from that column in the sorter records, the PK of
918 ** the row from table t1 is stored instead. Then, as records are extracted from
919 ** the sorter to return to the user, the required value of bigblob is
920 ** retrieved directly from table t1. If the values are very large, this
921 ** can be more efficient than storing them directly in the sorter records.
922 **
923 ** The ExprList_item.bSorterRef flag is set for each expression in pEList
924 ** for which the sorter-reference optimization should be enabled.
925 ** Additionally, the pSort->aDefer[] array is populated with entries
926 ** for all cursors required to evaluate all selected expressions. Finally.
927 ** output variable (*ppExtra) is set to an expression list containing
928 ** expressions for all extra PK values that should be stored in the
929 ** sorter records.
930 */
936 ){
951 ){
955 }
966 }
975 }
976 }
980 nDefer++;
981 }
982 }
984 }
985 }
986 }
989 }
990 #endif
992 /*
993 ** This routine generates the code for the inside of the inner loop
994 ** of a SELECT.
995 **
996 ** If srcTab is negative, then the p->pEList expressions
997 ** are evaluated in order to get the data for this row. If srcTab is
998 ** zero or more, then data is pulled from srcTab and p->pEList is used only
999 ** to get the number of columns and the collation sequence for each column.
1000 */
1010 ){
1020 /* Usually, regResult is the first cell in an array of memory cells
1021 ** containing the current result row. In this case regOrig is set to the
1022 ** same value. However, if the results are being sent to the sorter, the
1023 ** values for any expressions that are also part of the sort-key are omitted
1024 ** from this array. In this case regOrig is set to zero. */
1035 }
1037 /* Pull the requested columns.
1038 */
1046 }
1050 /* This is an error condition that can result, for example, when a SELECT
1051 ** on the right-hand side of an INSERT contains more result columns than
1052 ** there are columns in the table on the left. The error will be caught
1053 ** and reported later. But we need to make sure enough memory is allocated
1054 ** to avoid other spurious errors in the meantime. */
1056 }
1063 }
1065 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
1067 #endif
1068 /* If the destination is an EXISTS(...) expression, the actual
1069 ** values returned by the SELECT are not required.
1070 */
1077 }
1079 /* For each expression in p->pEList that is a copy of an expression in
1080 ** the ORDER BY clause (pSort->pOrderBy), set the associated
1081 ** iOrderByCol value to one more than the index of the ORDER BY
1082 ** expression within the sort-key that pushOntoSorter() will generate.
1083 ** This allows the p->pEList field to be omitted from the sorted record,
1084 ** saving space and CPU cycles. */
1091 }
1092 }
1093 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
1096 /* If there are any extra PK columns to add to the sorter records,
1097 ** allocate extra memory cells and adjust the OpenEphemeral
1098 ** instruction to account for the larger records. This is only
1099 ** required if there are one or more WITHOUT ROWID tables with
1100 ** composite primary keys in the SortCtx.aDefer[] array. */
1105 }
1106 #endif
1108 /* Adjust nResultCol to account for columns that are omitted
1109 ** from the sorter by the optimizations in this branch */
1113 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
1115 #endif
1116 ){
1117 nResultCol--;
1119 }
1120 }
1130 }
1133 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
1137 #endif
1141 ){
1148 }
1149 }
1151 /* If the DISTINCT keyword was present on the SELECT statement
1152 ** and this row has been seen before, then do not make this row
1153 ** part of the result.
1154 */
1163 }
1164 }
1167 /* In this mode, write each query result to the key of the temporary
1168 ** table iParm.
1169 */
1170 #ifndef SQLITE_OMIT_COMPOUND_SELECT
1178 }
1180 /* Construct a record from the query result, but instead of
1181 ** saving that record, use it as a key to delete elements from
1182 ** the temporary table iParm.
1183 */
1187 }
1190 /* Store the result as data using a unique key.
1191 */
1202 #ifndef SQLITE_OMIT_CTE
1204 /* If the destination is DistFifo, then cursor (iParm+1) is open
1205 ** on an ephemeral index. If the current row is already present
1206 ** in the index, do not write it to the output. If not, add the
1207 ** current row to the index and proceed with writing it to the
1208 ** output table as well. */
1214 }
1215 #endif
1225 }
1228 }
1238 /* If the UPDATE FROM join is an aggregate that matches no rows, it
1239 ** might still be trying to return one row, because that is what
1240 ** aggregates do. Don't record that empty row in the output table. */
1249 }
1250 }
1252 }
1254 #ifndef SQLITE_OMIT_SUBQUERY
1255 /* If we are creating a set for an "expr IN (SELECT ...)" construct,
1256 ** then there should be a single item on the stack. Write this
1257 ** item into the set table with bogus data.
1258 */
1261 /* At first glance you would think we could optimize out the
1262 ** ORDER BY in this case since the order of entries in the set
1263 ** does not matter. But there might be a LIMIT clause, in which
1264 ** case the order does matter */
1274 }
1276 }
1279 /* If any row exist in the result set, record that fact and abort.
1280 */
1283 /* The LIMIT clause will terminate the loop for us */
1285 }
1287 /* If this is a scalar select that is part of an expression, then
1288 ** store the results in the appropriate memory cell or array of
1289 ** memory cells and break out of the scan loop.
1290 */
1299 /* The LIMIT clause will jump out of the loop for us */
1300 }
1302 }
1311 nPrefixReg);
1316 }
1318 }
1320 #ifndef SQLITE_OMIT_CTE
1321 /* Write the results into a priority queue that is order according to
1322 ** pDest->pOrderBy (in pSO). pDest->iSDParm (in iParm) is the cursor for an
1323 ** index with pSO->nExpr+2 columns. Build a key using pSO for the first
1324 ** pSO->nExpr columns, then make sure all keys are unique by adding a
1325 ** final OP_Sequence column. The last column is the record as a blob.
1326 */
1340 /* If the destination is DistQueue, then cursor (iParm+1) is open
1341 ** on a second ephemeral index that holds all values every previously
1342 ** added to the queue. */
1346 }
1351 }
1356 }
1364 }
1369 #if !defined(SQLITE_OMIT_TRIGGER)
1370 /* Discard the results. This is used for SELECT statements inside
1371 ** the body of a TRIGGER. The purpose of such selects is to call
1372 ** user-defined functions that have side effects. We do not care
1373 ** about the actual results of the select.
1374 */
1378 }
1379 #endif
1380 }
1382 /* Jump to the end of the loop if the LIMIT is reached. Except, if
1383 ** there is a sorter, in which case the sorter has already limited
1384 ** the output for us.
1385 */
1388 }
1389 }
1391 /*
1392 ** Allocate a KeyInfo object sufficient for an index of N key columns and
1393 ** X extra columns.
1394 */
1408 }
1410 }
1412 /*
1413 ** Deallocate a KeyInfo object
1414 */
1420 }
1421 }
1423 /*
1424 ** Make a new pointer to a KeyInfo object
1425 */
1430 }
1432 }
1434 #ifdef SQLITE_DEBUG
1435 /*
1436 ** Return TRUE if a KeyInfo object can be change. The KeyInfo object
1437 ** can only be changed if this is just a single reference to the object.
1438 **
1439 ** This routine is used only inside of assert() statements.
1440 */
1444 /*
1445 ** Given an expression list, generate a KeyInfo structure that records
1446 ** the collating sequence for each expression in that expression list.
1447 **
1448 ** If the ExprList is an ORDER BY or GROUP BY clause then the resulting
1449 ** KeyInfo structure is appropriate for initializing a virtual index to
1450 ** implement that clause. If the ExprList is the result set of a SELECT
1451 ** then the KeyInfo structure is appropriate for initializing a virtual
1452 ** index to implement a DISTINCT test.
1453 **
1454 ** Space to hold the KeyInfo structure is obtained from malloc. The calling
1455 ** function is responsible for seeing that this structure is eventually
1456 ** freed.
1457 */
1463 ){
1477 }
1478 }
1480 }
1482 /*
1483 ** Name of the connection operator, used for error messages.
1484 */
1492 }
1494 }
1496 #ifndef SQLITE_OMIT_EXPLAIN
1497 /*
1498 ** Unless an "EXPLAIN QUERY PLAN" command is being processed, this function
1499 ** is a no-op. Otherwise, it adds a single row of output to the EQP result,
1500 ** where the caption is of the form:
1501 **
1502 ** "USE TEMP B-TREE FOR xxx"
1503 **
1504 ** where xxx is one of "DISTINCT", "ORDER BY" or "GROUP BY". Exactly which
1505 ** is determined by the zUsage argument.
1506 */
1509 }
1511 /*
1512 ** Assign expression b to lvalue a. A second, no-op, version of this macro
1513 ** is provided when SQLITE_OMIT_EXPLAIN is defined. This allows the code
1514 ** in sqlite3Select() to assign values to structure member variables that
1515 ** only exist if SQLITE_OMIT_EXPLAIN is not defined without polluting the
1516 ** code with #ifndef directives.
1517 */
1518 # define explainSetInteger(a, b) a = b
1520 #else
1521 /* No-op versions of the explainXXX() functions and macros. */
1522 # define explainTempTable(y,z)
1523 # define explainSetInteger(y,z)
1524 #endif
1527 /*
1528 ** If the inner loop was generated using a non-null pOrderBy argument,
1529 ** then the results were placed in a sorter. After the loop is terminated
1530 ** we need to run the sorter and output the results. The following
1531 ** routine generates the code needed to do that.
1532 */
1539 ){
1564 }
1566 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
1567 /* Open any cursors needed for sorter-reference expressions */
1573 }
1574 #endif
1580 }
1590 }
1591 }
1598 }
1612 }
1614 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
1616 #endif
1618 }
1619 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
1640 }
1645 }
1646 }
1648 }
1649 #endif
1651 #ifdef SQLITE_ENABLE_SORTER_REFERENCES
1655 #endif
1656 {
1662 }
1665 }
1666 }
1675 }
1676 #ifndef SQLITE_OMIT_SUBQUERY
1683 }
1685 /* The LIMIT clause will terminate the loop for us */
1687 }
1688 #endif
1697 }
1699 }
1708 }
1710 }
1711 }
1717 }
1719 }
1720 /* The bottom of the loop
1721 */
1727 }
1730 }
1732 /*
1733 ** Return a pointer to a string containing the 'declaration type' of the
1734 ** expression pExpr. The string may be treated as static by the caller.
1735 **
1736 ** Also try to estimate the size of the returned value and return that
1737 ** result in *pEstWidth.
1738 **
1739 ** The declaration type is the exact datatype definition extracted from the
1740 ** original CREATE TABLE statement if the expression is a column. The
1741 ** declaration type for a ROWID field is INTEGER. Exactly when an expression
1742 ** is considered a column can be complex in the presence of subqueries. The
1743 ** result-set expression in all of the following SELECT statements is
1744 ** considered a column by this function.
1745 **
1746 ** SELECT col FROM tbl;
1747 ** SELECT (SELECT col FROM tbl;
1748 ** SELECT (SELECT col FROM tbl);
1749 ** SELECT abc FROM (SELECT col AS abc FROM tbl);
1750 **
1751 ** The declaration type for any expression other than a column is NULL.
1752 **
1753 ** This routine has either 3 or 6 parameters depending on whether or not
1754 ** the SQLITE_ENABLE_COLUMN_METADATA compile-time option is used.
1755 */
1756 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1757 # define columnType(A,B,C,D,E) columnTypeImpl(A,B,C,D,E)
1759 # define columnType(A,B,C,D,E) columnTypeImpl(A,B)
1760 #endif
1763 #ifndef SQLITE_ENABLE_COLUMN_METADATA
1764 Expr *pExpr
1765 #else
1770 #endif
1771 ){
1774 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1778 #endif
1784 /* The expression is a column. Locate the table the column is being
1785 ** extracted from in NameContext.pSrcList. This table may be real
1786 ** database table or a subquery.
1787 */
1799 }
1800 }
1803 /* At one time, code such as "SELECT new.x" within a trigger would
1804 ** cause this condition to run. Since then, we have restructured how
1805 ** trigger code is generated and so this condition is no longer
1806 ** possible. However, it can still be true for statements like
1807 ** the following:
1808 **
1809 ** CREATE TABLE t1(col INTEGER);
1810 ** SELECT (SELECT t1.col) FROM FROM t1;
1811 **
1812 ** when columnType() is called on the expression "t1.col" in the
1813 ** sub-select. In this case, set the column type to NULL, even
1814 ** though it should really be "INTEGER".
1815 **
1816 ** This is not a problem, as the column type of "t1.col" is never
1817 ** used. When columnType() is called on the expression
1818 ** "(SELECT t1.col)", the correct type is returned (see the TK_SELECT
1819 ** branch below. */
1821 }
1825 /* The "table" is actually a sub-select or a view in the FROM clause
1826 ** of the SELECT statement. Return the declaration type and origin
1827 ** data for the result-set column of the sub-select.
1828 */
1830 #ifdef SQLITE_ALLOW_ROWID_IN_VIEW
1832 #else
1834 #endif
1835 ){
1836 /* If iCol is less than zero, then the expression requests the
1837 ** rowid of the sub-select or view. This expression is legal (see
1838 ** test case misc2.2.2) - it always evaluates to NULL.
1839 */
1840 NameContext sNC;
1846 }
1848 /* A real table or a CTE table */
1850 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1859 }
1864 }
1865 #else
1871 }
1872 #endif
1873 }
1875 }
1876 #ifndef SQLITE_OMIT_SUBQUERY
1878 /* The expression is a sub-select. Return the declaration type and
1879 ** origin info for the single column in the result set of the SELECT
1880 ** statement.
1881 */
1882 NameContext sNC;
1893 }
1894 #endif
1895 }
1897 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1903 }
1904 #endif
1906 }
1908 /*
1909 ** Generate code that will tell the VDBE the declaration types of columns
1910 ** in the result set.
1911 */
1916 ){
1917 #ifndef SQLITE_OMIT_DECLTYPE
1920 NameContext sNC;
1927 #ifdef SQLITE_ENABLE_COLUMN_METADATA
1933 /* The vdbe must make its own copy of the column-type and other
1934 ** column specific strings, in case the schema is reset before this
1935 ** virtual machine is deleted.
1936 */
1940 #else
1942 #endif
1944 }
1946 }
1949 /*
1950 ** Compute the column names for a SELECT statement.
1951 **
1952 ** The only guarantee that SQLite makes about column names is that if the
1953 ** column has an AS clause assigning it a name, that will be the name used.
1954 ** That is the only documented guarantee. However, countless applications
1955 ** developed over the years have made baseless assumptions about column names
1956 ** and will break if those assumptions changes. Hence, use extreme caution
1957 ** when modifying this routine to avoid breaking legacy.
1958 **
1959 ** See Also: sqlite3ColumnsFromExprList()
1960 **
1961 ** The PRAGMA short_column_names and PRAGMA full_column_names settings are
1962 ** deprecated. The default setting is short=ON, full=OFF. 99.9% of all
1963 ** applications should operate this way. Nevertheless, we need to support the
1964 ** other modes for legacy:
1965 **
1966 ** short=OFF, full=OFF: Column name is the text of the expression has it
1967 ** originally appears in the SELECT statement. In
1968 ** other words, the zSpan of the result expression.
1969 **
1970 ** short=ON, full=OFF: (This is the default setting). If the result
1971 ** refers directly to a table column, then the
1972 ** result column name is just the table column
1973 ** name: COLUMN. Otherwise use zSpan.
1974 **
1975 ** full=ON, short=ANY: If the result refers directly to a table column,
1976 ** then the result column name with the table name
1977 ** prefix, ex: TABLE.COLUMN. Otherwise use zSpan.
1978 */
1982 ){
1992 #ifndef SQLITE_OMIT_EXPLAIN
1993 /* If this is an EXPLAIN, skip this step */
1996 }
1997 #endif
2000 /* Column names are determined by the left-most term of a compound select */
2019 /* An AS clause always takes first priority */
2033 }
2040 }
2045 }
2046 }
2048 }
2050 /*
2051 ** Given an expression list (which is really the list of expressions
2052 ** that form the result set of a SELECT statement) compute appropriate
2053 ** column names for a table that would hold the expression list.
2054 **
2055 ** All column names will be unique.
2056 **
2057 ** Only the column names are computed. Column.zType, Column.zColl,
2058 ** and other fields of Column are zeroed.
2059 **
2060 ** Return SQLITE_OK on success. If a memory allocation error occurs,
2061 ** store NULL in *paCol and 0 in *pnCol and return SQLITE_NOMEM.
2062 **
2063 ** The only guarantee that SQLite makes about column names is that if the
2064 ** column has an AS clause assigning it a name, that will be the name used.
2065 ** That is the only documented guarantee. However, countless applications
2066 ** developed over the years have made baseless assumptions about column names
2067 ** and will break if those assumptions changes. Hence, use extreme caution
2068 ** when modifying this routine to avoid breaking legacy.
2069 **
2070 ** See Also: sqlite3GenerateColumnNames()
2071 */
2077 ){
2097 }
2103 /* Get an appropriate name for the column
2104 */
2106 /* If the column contains an "AS <name>" phrase, use <name> as the name */
2112 }
2116 ){
2117 /* For columns use the column name name */
2125 /* Use the original text of the column expression as its name */
2127 }
2128 }
2133 }
2135 /* Make sure the column name is unique. If the name is not unique,
2136 ** append an integer to the name so that it becomes unique.
2137 */
2144 }
2147 }
2153 }
2154 }
2159 }
2164 }
2166 }
2168 /*
2169 ** Add type and collation information to a column list based on
2170 ** a SELECT statement.
2171 **
2172 ** The column list presumably came from selectColumnNamesFromExprList().
2173 ** The column list has only names, not types or collations. This
2174 ** routine goes through and adds the types and collations.
2175 **
2176 ** This routine requires that all identifiers in the SELECT
2177 ** statement be resolved.
2178 */
2184 ){
2186 NameContext sNC;
2206 /* pCol->szEst = ... // Column size est for SELECT tables never used */
2218 }
2219 }
2225 }
2226 }
2228 }
2230 /*
2231 ** Given a SELECT statement, generate a Table structure that describes
2232 ** the result set of that SELECT.
2233 */
2237 u64 savedFlags;
2249 }
2259 }
2261 }
2263 /*
2264 ** Get a VDBE for the given parser context. Create a new one if necessary.
2265 ** If an error occurs, return NULL and leave a message in pParse.
2266 */
2270 }
2273 ){
2275 }
2277 }
2280 /*
2281 ** Compute the iLimit and iOffset fields of the SELECT based on the
2282 ** pLimit expressions. pLimit->pLeft and pLimit->pRight hold the expressions
2283 ** that appear in the original SQL statement after the LIMIT and OFFSET
2284 ** keywords. Or NULL if those keywords are omitted. iLimit and iOffset
2285 ** are the integer memory register numbers for counters used to compute
2286 ** the limit and offset. If there is no limit and/or offset, then
2287 ** iLimit and iOffset are negative.
2288 **
2289 ** This routine changes the values of iLimit and iOffset only if
2290 ** a limit or offset is defined by pLimit->pLeft and pLimit->pRight. iLimit
2291 ** and iOffset should have been preset to appropriate default values (zero)
2292 ** prior to calling this routine.
2293 **
2294 ** The iOffset register (if it exists) is initialized to the value
2295 ** of the OFFSET. The iLimit register is initialized to LIMIT. Register
2296 ** iOffset+1 is initialized to LIMIT+OFFSET.
2297 **
2298 ** Only if pLimit->pLeft!=0 do the limit registers get
2299 ** redefined. The UNION ALL operator uses this property to force
2300 ** the reuse of the same limit and offset registers across multiple
2301 ** SELECT statements.
2302 */
2312 /*
2313 ** "LIMIT -1" always shows all rows. There is some
2314 ** controversy about what the correct behavior should be.
2315 ** The current implementation interprets "LIMIT 0" to mean
2316 ** no rows.
2317 */
2332 }
2338 }
2347 }
2348 }
2349 }
2351 #ifndef SQLITE_OMIT_COMPOUND_SELECT
2352 /*
2353 ** Return the appropriate collating sequence for the iCol-th column of
2354 ** the result set for the compound-select statement "p". Return NULL if
2355 ** the column has no default collating sequence.
2356 **
2357 ** The collating sequence for the compound select is taken from the
2358 ** left-most term of the select that has a collating sequence.
2359 */
2366 }
2368 /* iCol must be less than p->pEList->nExpr. Otherwise an error would
2369 ** have been thrown during name resolution and we would not have gotten
2370 ** this far */
2373 }
2375 }
2377 /*
2378 ** The select statement passed as the second parameter is a compound SELECT
2379 ** with an ORDER BY clause. This function allocates and returns a KeyInfo
2380 ** structure suitable for implementing the ORDER BY.
2381 **
2382 ** Space to hold the KeyInfo structure is obtained from malloc. The calling
2383 ** function is responsible for ensuring that this structure is eventually
2384 ** freed.
2385 */
2405 }
2409 }
2410 }
2413 }
2415 #ifndef SQLITE_OMIT_CTE
2416 /*
2417 ** This routine generates VDBE code to compute the content of a WITH RECURSIVE
2418 ** query of the form:
2419 **
2420 ** <recursive-table> AS (<setup-query> UNION [ALL] <recursive-query>)
2421 ** \___________/ \_______________/
2422 ** p->pPrior p
2423 **
2424 **
2425 ** There is exactly one reference to the recursive-table in the FROM clause
2426 ** of recursive-query, marked with the SrcList->a[].fg.isRecursive flag.
2427 **
2428 ** The setup-query runs once to generate an initial set of rows that go
2429 ** into a Queue table. Rows are extracted from the Queue table one by
2430 ** one. Each row extracted from Queue is output to pDest. Then the single
2431 ** extracted row (now in the iCurrent table) becomes the content of the
2432 ** recursive-table for a recursive-query run. The output of the recursive-query
2433 ** is added back into the Queue table. Then another row is extracted from Queue
2434 ** and the iteration continues until the Queue table is empty.
2435 **
2436 ** If the compound query operator is UNION then no duplicate rows are ever
2437 ** inserted into the Queue table. The iDistinct table keeps a copy of all rows
2438 ** that have ever been inserted into Queue and causes duplicates to be
2439 ** discarded. If the operator is UNION ALL, then duplicates are allowed.
2440 **
2441 ** If the query has an ORDER BY, then entries in the Queue table are kept in
2442 ** ORDER BY order and the first entry is extracted for each cycle. Without
2443 ** an ORDER BY, the Queue table is just a FIFO.
2444 **
2445 ** If a LIMIT clause is provided, then the iteration stops after LIMIT rows
2446 ** have been output to pDest. A LIMIT of zero means to output no rows and a
2447 ** negative LIMIT means to output all rows. If there is also an OFFSET clause
2448 ** with a positive value, then the first OFFSET outputs are discarded rather
2449 ** than being sent to pDest. The LIMIT count does not begin until after OFFSET
2450 ** rows have been skipped.
2451 */
2456 ){
2476 #ifndef SQLITE_OMIT_WINDOWFUNC
2480 }
2481 #endif
2483 /* Obtain authorization to do a recursive query */
2486 /* Process the LIMIT and OFFSET clauses, if they exist */
2497 /* Locate the cursor number of the Current table */
2502 }
2503 }
2505 /* Allocate cursors numbers for Queue and Distinct. The cursor number for
2506 ** the Distinct table must be exactly one greater than Queue in order
2507 ** for the SRT_DistFifo and SRT_DistQueue destinations to work. */
2514 }
2517 /* Allocate cursors for Current, Queue, and Distinct. */
2527 }
2532 }
2534 /* Detach the ORDER BY clause from the compound SELECT */
2537 /* Figure out how many elements of the compound SELECT are part of the
2538 ** recursive query. Make sure no recursive elements use aggregate
2539 ** functions. Mark the recursive elements as UNION ALL even if they
2540 ** are really UNION because the distinctness will be enforced by the
2541 ** iDistinct table. pFirstRec is left pointing to the left-most
2542 ** recursive term of the CTE.
2543 */
2548 }
2551 }
2553 /* Store the results of the setup-query in Queue. */
2561 /* Find the next row in the Queue and output that row */
2564 /* Transfer the next row in Queue over to Current */
2570 }
2573 /* Output the single row in Current */
2581 }
2584 /* Execute the recursive SELECT taking the single row in Current as
2585 ** the value for the recursive-table. Store the results in the Queue.
2586 */
2593 /* Keep running the loop until the Queue is empty */
2597 end_of_recursive_query:
2602 }
2605 /* Forward references */
2610 );
2612 /*
2613 ** Handle the special case of a compound-select that originates from a
2614 ** VALUES clause. By handling this as a special case, we avoid deep
2615 ** recursion, and thus do not need to enforce the SQLITE_LIMIT_COMPOUND_SELECT
2616 ** on a VALUES clause.
2617 **
2618 ** Because the Select object originates from a VALUES clause:
2619 ** (1) There is no LIMIT or OFFSET or else there is a LIMIT of exactly 1
2620 ** (2) All terms are UNION ALL
2621 ** (3) There is no ORDER BY clause
2622 **
2623 ** The "LIMIT of exactly 1" case of condition (1) comes about when a VALUES
2624 ** clause occurs within scalar expression (ex: "SELECT (VALUES(1),(2),(3))").
2625 ** The sqlite3CodeSubselect will have added the LIMIT 1 clause in tht case.
2626 ** Since the limit is exactly 1, we only need to evalutes the left-most VALUES.
2627 */
2632 ){
2641 #ifndef SQLITE_OMIT_WINDOWFUNC
2643 #endif
2656 }
2658 }
2660 /*
2661 ** Return true if the SELECT statement which is known to be the recursive
2662 ** part of a recursive CTE still has its anchor terms attached. If the
2663 ** anchor terms have already been removed, then return false.
2664 */
2668 }
2670 /*
2671 ** This routine is called to process a compound query form from
2672 ** two or more separate queries using UNION, UNION ALL, EXCEPT, or
2673 ** INTERSECT
2674 **
2675 ** "p" points to the right-most of the two queries. the query on the
2676 ** left is p->pPrior. The left query could also be a compound query
2677 ** in which case this routine will be called recursively.
2678 **
2679 ** The results of the total query are to be written into a destination
2680 ** of type eDest with parameter iParm.
2681 **
2682 ** Example 1: Consider a three-way compound SQL statement.
2683 **
2684 ** SELECT a FROM t1 UNION SELECT b FROM t2 UNION SELECT c FROM t3
2685 **
2686 ** This statement is parsed up as follows:
2687 **
2688 ** SELECT c FROM t3
2689 ** |
2690 ** `-----> SELECT b FROM t2
2691 ** |
2692 ** `------> SELECT a FROM t1
2693 **
2694 ** The arrows in the diagram above represent the Select.pPrior pointer.
2695 ** So if this routine is called with p equal to the t3 query, then
2696 ** pPrior will be the t2 query. p->op will be TK_UNION in this case.
2697 **
2698 ** Notice that because of the way SQLite parses compound SELECTs, the
2699 ** individual selects always group from left to right.
2700 */
2705 ){
2713 /* Make sure there is no ORDER BY or LIMIT clause on prior SELECTs. Only
2714 ** the last (right-most) SELECT in the series may have an ORDER BY or LIMIT.
2715 */
2728 /* Create the destination temporary table if necessary
2729 */
2734 }
2736 /* Special handling for a compound-select that originates as a VALUES clause.
2737 */
2742 }
2744 /* Make sure all SELECTs in the statement have the same number of elements
2745 ** in their result sets.
2746 */
2750 #ifndef SQLITE_OMIT_CTE
2754 #endif
2756 /* Compound SELECTs that have an ORDER BY clause are handled separately.
2757 */
2762 #ifndef SQLITE_OMIT_EXPLAIN
2766 }
2767 #endif
2769 /* Generate code for the left and right SELECT statements.
2770 */
2784 }
2794 }
2795 }
2806 ){
2808 }
2811 }
2813 }
2821 SelectDest uniondest;
2827 /* We can reuse a temporary table generated by a SELECT to our
2828 ** right.
2829 */
2833 /* We will need to create our own temporary table to hold the
2834 ** intermediate results.
2835 */
2843 }
2846 /* Code the SELECT statements to our left
2847 */
2854 }
2856 /* Code the current SELECT statement
2857 */
2863 }
2879 }
2885 /* Convert the data in the temporary table into whatever form
2886 ** it is that we currently need.
2887 */
2903 }
2905 }
2911 SelectDest intersectdest;
2914 /* INTERSECT is different from the others since it requires
2915 ** two temporary tables. Hence it has its own case. Begin
2916 ** by allocating the tables we will need.
2917 */
2928 /* Code the SELECTs to our left into temporary table "tab1".
2929 */
2935 }
2937 /* Code the current SELECT into temporary table "tab2"
2938 */
2955 }
2959 /* Generate code to take the intersection of the two temporary
2960 ** tables.
2961 */
2981 }
2982 }
2984 #ifndef SQLITE_OMIT_EXPLAIN
2987 }
2988 #endif
2989 }
2992 /* Compute collating sequences used by
2993 ** temporary tables needed to implement the compound select.
2994 ** Attach the KeyInfo structure to all temporary tables.
2995 **
2996 ** This section is run by the right-most SELECT statement only.
2997 ** SELECT statements to the left always skip this part. The right-most
2998 ** SELECT might also skip this part if it has no ORDER BY clause and
2999 ** no temp tables are required.
3000 */
3015 }
3020 }
3021 }
3027 /* If [0] is unused then [1] is also unused. So we can
3028 ** always safely abort as soon as the first unused slot is found */
3031 }
3034 P4_KEYINFO);
3036 }
3037 }
3039 }
3041 multi_select_end:
3047 pDelete);
3048 }
3050 }
3053 /*
3054 ** Error message for when two or more terms of a compound select have different
3055 ** size result sets.
3056 */
3064 }
3065 }
3067 /*
3068 ** Code an output subroutine for a coroutine implementation of a
3069 ** SELECT statment.
3070 **
3071 ** The data to be output is contained in pIn->iSdst. There are
3072 ** pIn->nSdst columns to be output. pDest is where the output should
3073 ** be sent.
3074 **
3075 ** regReturn is the number of the register holding the subroutine
3076 ** return address.
3077 **
3078 ** If regPrev>0 then it is the first register in a vector that
3079 ** records the previous output. mem[regPrev] is a flag that is false
3080 ** if there has been no previous output. If regPrev>0 then code is
3081 ** generated to suppress duplicates. pKeyInfo is used for comparing
3082 ** keys.
3083 **
3084 ** If the LIMIT found in p->iLimit is reached, jump immediately to
3085 ** iBreak.
3086 */
3096 ){
3104 /* Suppress duplicates for UNION, EXCEPT, and INTERSECT
3105 */
3115 }
3118 /* Suppress the first OFFSET entries if there is an OFFSET clause
3119 */
3125 /* Store the result as data using a unique key.
3126 */
3137 }
3139 #ifndef SQLITE_OMIT_SUBQUERY
3140 /* If we are creating a set for an "expr IN (SELECT ...)".
3141 */
3152 }
3154 /* If this is a scalar select that is part of an expression, then
3155 ** store the results in the appropriate memory cell and break out
3156 ** of the scan loop. Note that the select might return multiple columns
3157 ** if it is the RHS of a row-value IN operator.
3158 */
3162 /* The LIMIT clause will jump out of the loop for us */
3164 }
3167 /* The results are stored in a sequence of registers
3168 ** starting at pDest->iSdst. Then the co-routine yields.
3169 */
3174 }
3178 }
3180 /* If none of the above, then the result destination must be
3181 ** SRT_Output. This routine is never called with any other
3182 ** destination other than the ones handled above or SRT_Output.
3183 **
3184 ** For SRT_Output, results are stored in a sequence of registers.
3185 ** Then the OP_ResultRow opcode is used to cause sqlite3_step() to
3186 ** return the next row of result.
3187 */
3192 }
3193 }
3195 /* Jump to the end of the loop if the LIMIT is reached.
3196 */
3199 }
3201 /* Generate the subroutine return
3202 */
3207 }
3209 /*
3210 ** Alternative compound select code generator for cases when there
3211 ** is an ORDER BY clause.
3212 **
3213 ** We assume a query of the following form:
3214 **
3215 ** <selectA> <operator> <selectB> ORDER BY <orderbylist>
3216 **
3217 ** <operator> is one of UNION ALL, UNION, EXCEPT, or INTERSECT. The idea
3218 ** is to code both <selectA> and <selectB> with the ORDER BY clause as
3219 ** co-routines. Then run the co-routines in parallel and merge the results
3220 ** into the output. In addition to the two coroutines (called selectA and
3221 ** selectB) there are 7 subroutines:
3222 **
3223 ** outA: Move the output of the selectA coroutine into the output
3224 ** of the compound query.
3225 **
3226 ** outB: Move the output of the selectB coroutine into the output
3227 ** of the compound query. (Only generated for UNION and
3228 ** UNION ALL. EXCEPT and INSERTSECT never output a row that
3229 ** appears only in B.)
3230 **
3231 ** AltB: Called when there is data from both coroutines and A<B.
3232 **
3233 ** AeqB: Called when there is data from both coroutines and A==B.
3234 **
3235 ** AgtB: Called when there is data from both coroutines and A>B.
3236 **
3237 ** EofA: Called when data is exhausted from selectA.
3238 **
3239 ** EofB: Called when data is exhausted from selectB.
3240 **
3241 ** The implementation of the latter five subroutines depend on which
3242 ** <operator> is used:
3243 **
3244 **
3245 ** UNION ALL UNION EXCEPT INTERSECT
3246 ** ------------- ----------------- -------------- -----------------
3247 ** AltB: outA, nextA outA, nextA outA, nextA nextA
3248 **
3249 ** AeqB: outA, nextA nextA nextA outA, nextA
3250 **
3251 ** AgtB: outB, nextB outB, nextB nextB nextB
3252 **
3253 ** EofA: outB, nextB outB, nextB halt halt
3254 **
3255 ** EofB: outA, nextA outA, nextA outA, nextA halt
3256 **
3257 ** In the AltB, AeqB, and AgtB subroutines, an EOF on A following nextA
3258 ** causes an immediate jump to EofA and an EOF on B following nextB causes
3259 ** an immediate jump to EofB. Within EofA and EofB, and EOF on entry or
3260 ** following nextX causes a jump to the end of the select processing.
3261 **
3262 ** Duplicate removal in the UNION, EXCEPT, and INTERSECT cases is handled
3263 ** within the output subroutine. The regPrev register set holds the previously
3264 ** output value. A comparison is made against this value and the output
3265 ** is skipped if the next results would be the same as the previous.
3266 **
3267 ** The implementation plan is to implement the two coroutines and seven
3268 ** subroutines first, then put the control logic at the bottom. Like this:
3269 **
3270 ** goto Init
3271 ** coA: coroutine for left query (A)
3272 ** coB: coroutine for right query (B)
3273 ** outA: output one row of A
3274 ** outB: output one row of B (UNION and UNION ALL only)
3275 ** EofA: ...
3276 ** EofB: ...
3277 ** AltB: ...
3278 ** AeqB: ...
3279 ** AgtB: ...
3280 ** Init: initialize coroutine registers
3281 ** yield coA
3282 ** if eof(A) goto EofA
3283 ** yield coB
3284 ** if eof(B) goto EofB
3285 ** Cmpr: Compare A, B
3286 ** Jump AltB, AeqB, AgtB
3287 ** End: ...
3288 **
3289 ** We call AltB, AeqB, AgtB, EofA, and EofB "subroutines" but they are not
3290 ** actually called using Gosub and they do not Return. EofA and EofB loop
3291 ** until all data is exhausted then jump to the "end" labe. AltB, AeqB,
3292 ** and AgtB jump to either L2 or to one of EofA or EofB.
3293 */
3294 #ifndef SQLITE_OMIT_COMPOUND_SELECT
3299 ){
3346 /* Patch up the ORDER BY clause
3347 */
3354 /* For operators other than UNION ALL we have to make sure that
3355 ** the ORDER BY clause covers every term of the result set. Add
3356 ** terms to the ORDER BY clause as necessary.
3357 */
3365 }
3373 }
3374 }
3375 }
3377 /* Compute the comparison permutation and keyinfo that is used with
3378 ** the permutation used to determine if the next
3379 ** row of results comes from selectA or selectB. Also add explicit
3380 ** collations to the ORDER BY clause terms so that when the subqueries
3381 ** to the right and the left are evaluated, they use the correct
3382 ** collation.
3383 */
3393 }
3397 }
3399 /* Allocate a range of temporary registers and the KeyInfo needed
3400 ** for the logic that removes duplicate result rows when the
3401 ** operator is UNION, EXCEPT, or INTERSECT (but not UNION ALL).
3402 */
3417 }
3418 }
3419 }
3421 /* Separate the left and the right query from one another
3422 */
3426 ){
3428 nSelect++;
3430 }
3431 }
3437 }
3448 /* Compute the limit registers */
3454 regLimitA);
3458 }
3471 /* Generate a coroutine to evaluate the SELECT statement to the
3472 ** left of the compound operator - the "A" select.
3473 */
3483 /* Generate a coroutine to evaluate the SELECT statement on
3484 ** the right - the "B" select
3485 */
3499 /* Generate a subroutine that outputs the current row of the A
3500 ** select as the next output row of the compound select.
3501 */
3507 /* Generate a subroutine that outputs the current row of the B
3508 ** select as the next output row of the compound select.
3509 */
3515 }
3518 /* Generate a subroutine to run when the results from select A
3519 ** are exhausted and only data in select B remains.
3520 */
3530 }
3532 /* Generate a subroutine to run when the results from select B
3533 ** are exhausted and only data in select A remains.
3534 */
3543 }
3545 /* Generate code to handle the case of A<B
3546 */
3552 /* Generate code to handle the case of A==B
3553 */
3558 addrAltB++;
3561 addrAeqB =
3564 }
3566 /* Generate code to handle the case of A>B
3567 */
3572 }
3576 /* This code runs once to initialize everything.
3577 */
3582 /* Implement the main merge loop
3583 */
3591 /* Jump to the this point in order to terminate the query.
3592 */
3595 /* Reassembly the compound query so that it will be freed correctly
3596 ** by the calling function */
3599 }
3605 /*** TBD: Insert subroutine calls to close cursors on incomplete
3606 **** subqueries ****/
3609 }
3610 #endif
3612 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3614 /* An instance of the SubstContext object describes an substitution edit
3615 ** to be performed on a parse tree.
3616 **
3617 ** All references to columns in table iTable are to be replaced by corresponding
3618 ** expressions in pEList.
3619 */
3628 /* Forward Declarations */
3632 /*
3633 ** Scan through the expression pExpr. Replace every reference to
3634 ** a column in table number iTable with a copy of the iColumn-th
3635 ** entry in pEList. (But leave references to the ROWID column
3636 ** unchanged.)
3637 **
3638 ** This routine is part of the flattening procedure. A subquery
3639 ** whose result set is defined by pEList appears as entry in the
3640 ** FROM clause of a SELECT such that the VDBE cursor assigned to that
3641 ** FORM clause entry is iTable. This routine makes the necessary
3642 ** changes to pExpr so that it refers directly to the source table
3643 ** of the subquery rather the result set of the subquery.
3644 */
3648 ){
3652 ){
3654 }
3658 ){
3659 #ifdef SQLITE_ALLOW_ROWID_IN_VIEW
3663 #endif
3664 {
3667 Expr ifNullRow;
3681 }
3687 }
3690 }
3693 }
3697 /* Ensure that the expression now has an implicit collation sequence,
3698 ** just as it did when it was a column of a view or sub-query. */
3703 );
3704 }
3706 }
3707 }
3711 }
3718 }
3719 #ifndef SQLITE_OMIT_WINDOWFUNC
3725 }
3726 #endif
3727 }
3729 }
3733 ){
3738 }
3739 }
3744 ){
3761 }
3762 }
3764 }
3767 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3768 /*
3769 ** pSelect is a SELECT statement and pSrcItem is one item in the FROM
3770 ** clause of that SELECT.
3771 **
3772 ** This routine scans the entire SELECT statement and recomputes the
3773 ** pSrcItem->colUsed mask.
3774 */
3783 }
3787 ){
3788 Walker w;
3796 }
3799 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3800 /*
3801 ** Assign new cursor numbers to each of the items in pSrc. For each
3802 ** new cursor number assigned, set an entry in the aCsrMap[] array
3803 ** to map the old cursor number to the new:
3804 **
3805 ** aCsrMap[iOld+1] = iNew;
3806 **
3807 ** The array is guaranteed by the caller to be large enough for all
3808 ** existing cursor numbers in pSrc. aCsrMap[0] is the array size.
3809 **
3810 ** If pSrc contains any sub-selects, call this routine recursively
3811 ** on the FROM clause of each such sub-select, with iExcept set to -1.
3812 */
3818 ){
3827 }
3831 }
3832 }
3833 }
3834 }
3836 /*
3837 ** *piCursor is a cursor number. Change it if it needs to be mapped.
3838 */
3844 }
3845 }
3847 /*
3848 ** Expression walker callback used by renumberCursors() to update
3849 ** Expr objects to match newly assigned cursor numbers.
3850 */
3855 }
3858 }
3860 }
3862 /*
3863 ** Assign a new cursor number to each cursor in the FROM clause (Select.pSrc)
3864 ** of the SELECT statement passed as the second argument, and to each
3865 ** cursor in the FROM clause of any FROM clause sub-selects, recursively.
3866 ** Except, do not assign a new cursor number to the iExcept'th element in
3867 ** the FROM clause of (*p). Update all expressions and other references
3868 ** to refer to the new cursor numbers.
3869 **
3870 ** Argument aCsrMap is an array that may be used for temporary working
3871 ** space. Two guarantees are made by the caller:
3872 **
3873 ** * the array is larger than the largest cursor number used within the
3874 ** select statement passed as an argument, and
3875 **
3876 ** * the array entries for all cursor numbers that do *not* appear in
3877 ** FROM clauses of the select statement as described above are
3878 ** initialized to zero.
3879 */
3885 ){
3886 Walker w;
3893 }
3896 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
3897 /*
3898 ** This routine attempts to flatten subqueries as a performance optimization.
3899 ** This routine returns 1 if it makes changes and 0 if no flattening occurs.
3900 **
3901 ** To understand the concept of flattening, consider the following
3902 ** query:
3903 **
3904 ** SELECT a FROM (SELECT x+y AS a FROM t1 WHERE z<100) WHERE a>5
3905 **
3906 ** The default way of implementing this query is to execute the
3907 ** subquery first and store the results in a temporary table, then
3908 ** run the outer query on that temporary table. This requires two
3909 ** passes over the data. Furthermore, because the temporary table
3910 ** has no indices, the WHERE clause on the outer query cannot be
3911 ** optimized.
3912 **
3913 ** This routine attempts to rewrite queries such as the above into
3914 ** a single flat select, like this:
3915 **
3916 ** SELECT x+y AS a FROM t1 WHERE z<100 AND a>5
3917 **
3918 ** The code generated for this simplification gives the same result
3919 ** but only has to scan the data once. And because indices might
3920 ** exist on the table t1, a complete scan of the data might be
3921 ** avoided.
3922 **
3923 ** Flattening is subject to the following constraints:
3924 **
3925 ** (**) We no longer attempt to flatten aggregate subqueries. Was:
3926 ** The subquery and the outer query cannot both be aggregates.
3927 **
3928 ** (**) We no longer attempt to flatten aggregate subqueries. Was:
3929 ** (2) If the subquery is an aggregate then
3930 ** (2a) the outer query must not be a join and
3931 ** (2b) the outer query must not use subqueries
3932 ** other than the one FROM-clause subquery that is a candidate
3933 ** for flattening. (This is due to ticket [2f7170d73bf9abf80]
3934 ** from 2015-02-09.)
3935 **
3936 ** (3) If the subquery is the right operand of a LEFT JOIN then
3937 ** (3a) the subquery may not be a join and
3938 ** (3b) the FROM clause of the subquery may not contain a virtual
3939 ** table and
3940 ** (3c) the outer query may not be an aggregate.
3941 ** (3d) the outer query may not be DISTINCT.
3942 **
3943 ** (4) The subquery can not be DISTINCT.
3944 **
3945 ** (**) At one point restrictions (4) and (5) defined a subset of DISTINCT
3946 ** sub-queries that were excluded from this optimization. Restriction
3947 ** (4) has since been expanded to exclude all DISTINCT subqueries.
3948 **
3949 ** (**) We no longer attempt to flatten aggregate subqueries. Was:
3950 ** If the subquery is aggregate, the outer query may not be DISTINCT.
3951 **
3952 ** (7) The subquery must have a FROM clause. TODO: For subqueries without
3953 ** A FROM clause, consider adding a FROM clause with the special
3954 ** table sqlite_once that consists of a single row containing a
3955 ** single NULL.
3956 **
3957 ** (8) If the subquery uses LIMIT then the outer query may not be a join.
3958 **
3959 ** (9) If the subquery uses LIMIT then the outer query may not be aggregate.
3960 **
3961 ** (**) Restriction (10) was removed from the code on 2005-02-05 but we
3962 ** accidently carried the comment forward until 2014-09-15. Original
3963 ** constraint: "If the subquery is aggregate then the outer query
3964 ** may not use LIMIT."
3965 **
3966 ** (11) The subquery and the outer query may not both have ORDER BY clauses.
3967 **
3968 ** (**) Not implemented. Subsumed into restriction (3). Was previously
3969 ** a separate restriction deriving from ticket #350.
3970 **
3971 ** (13) The subquery and outer query may not both use LIMIT.
3972 **
3973 ** (14) The subquery may not use OFFSET.
3974 **
3975 ** (15) If the outer query is part of a compound select, then the
3976 ** subquery may not use LIMIT.
3977 ** (See ticket #2339 and ticket [02a8e81d44]).
3978 **
3979 ** (16) If the outer query is aggregate, then the subquery may not
3980 ** use ORDER BY. (Ticket #2942) This used to not matter
3981 ** until we introduced the group_concat() function.
3982 **
3983 ** (17) If the subquery is a compound select, then
3984 ** (17a) all compound operators must be a UNION ALL, and
3985 ** (17b) no terms within the subquery compound may be aggregate
3986 ** or DISTINCT, and
3987 ** (17c) every term within the subquery compound must have a FROM clause
3988 ** (17d) the outer query may not be
3989 ** (17d1) aggregate, or
3990 ** (17d2) DISTINCT
3991 ** (17e) the subquery may not contain window functions, and
3992 ** (17f) the subquery must not be the RHS of a LEFT JOIN.
3993 **
3994 ** The parent and sub-query may contain WHERE clauses. Subject to
3995 ** rules (11), (13) and (14), they may also contain ORDER BY,
3996 ** LIMIT and OFFSET clauses. The subquery cannot use any compound
3997 ** operator other than UNION ALL because all the other compound
3998 ** operators have an implied DISTINCT which is disallowed by
3999 ** restriction (4).
4000 **
4001 ** Also, each component of the sub-query must return the same number
4002 ** of result columns. This is actually a requirement for any compound
4003 ** SELECT statement, but all the code here does is make sure that no
4004 ** such (illegal) sub-query is flattened. The caller will detect the
4005 ** syntax error and return a detailed message.
4006 **
4007 ** (18) If the sub-query is a compound select, then all terms of the
4008 ** ORDER BY clause of the parent must be copies of a term returned
4009 ** by the parent query.
4010 **
4011 ** (19) If the subquery uses LIMIT then the outer query may not
4012 ** have a WHERE clause.
4013 **
4014 ** (20) If the sub-query is a compound select, then it must not use
4015 ** an ORDER BY clause. Ticket #3773. We could relax this constraint
4016 ** somewhat by saying that the terms of the ORDER BY clause must
4017 ** appear as unmodified result columns in the outer query. But we
4018 ** have other optimizations in mind to deal with that case.
4019 **
4020 ** (21) If the subquery uses LIMIT then the outer query may not be
4021 ** DISTINCT. (See ticket [752e1646fc]).
4022 **
4023 ** (22) The subquery may not be a recursive CTE.
4024 **
4025 ** (23) If the outer query is a recursive CTE, then the sub-query may not be
4026 ** a compound query. This restriction is because transforming the
4027 ** parent to a compound query confuses the code that handles
4028 ** recursive queries in multiSelect().
4029 **
4030 ** (**) We no longer attempt to flatten aggregate subqueries. Was:
4031 ** The subquery may not be an aggregate that uses the built-in min() or
4032 ** or max() functions. (Without this restriction, a query like:
4033 ** "SELECT x FROM (SELECT max(y), x FROM t1)" would not necessarily
4034 ** return the value X for which Y was maximal.)
4035 **
4036 ** (25) If either the subquery or the parent query contains a window
4037 ** function in the select list or ORDER BY clause, flattening
4038 ** is not attempted.
4039 **
4040 **
4041 ** In this routine, the "p" parameter is a pointer to the outer query.
4042 ** The subquery is p->pSrc->a[iFrom]. isAgg is true if the outer query
4043 ** uses aggregates.
4044 **
4045 ** If flattening is not attempted, this routine is a no-op and returns 0.
4046 ** If flattening is attempted this routine returns 1.
4047 **
4048 ** All of the expression analysis must occur on both the outer query and
4049 ** the subquery before this routine runs.
4050 */
4056 ){
4073 /* Check to see if flattening is permitted. Return 0 if not.
4074 */
4085 #ifndef SQLITE_OMIT_WINDOWFUNC
4087 #endif
4091 /* Prior to version 3.1.2, when LIMIT and OFFSET had to be simple constants,
4092 ** not arbitrary expressions, we allowed some combining of LIMIT and OFFSET
4093 ** because they could be computed at compile-time. But when LIMIT and OFFSET
4094 ** became arbitrary expressions, we were forced to add restrictions (13)
4095 ** and (14). */
4100 }
4105 }
4108 }
4113 }
4116 }
4118 /*
4119 ** If the subquery is the right operand of a LEFT JOIN, then the
4120 ** subquery may not be a join itself (3a). Example of why this is not
4121 ** allowed:
4122 **
4123 ** t1 LEFT OUTER JOIN (t2 JOIN t3)
4124 **
4125 ** If we flatten the above, we would get
4126 **
4127 ** (t1 LEFT OUTER JOIN t2) JOIN t3
4128 **
4129 ** which is not at all the same thing.
4130 **
4131 ** If the subquery is the right operand of a LEFT JOIN, then the outer
4132 ** query cannot be an aggregate. (3c) This is an artifact of the way
4133 ** aggregates are processed - there is no mechanism to determine if
4134 ** the LEFT JOIN table should be all-NULL.
4135 **
4136 ** See also tickets #306, #350, and #3300.
4137 */
4144 ){
4146 }
4147 }
4148 #ifdef SQLITE_EXTRA_IFNULLROW
4150 /* Setting isLeftJoin to -1 causes OP_IfNullRow opcodes to be generated for
4151 ** every reference to any result column from subquery in a join, even
4152 ** though they are not necessary. This will stress-test the OP_IfNullRow
4153 ** opcode. */
4155 }
4156 #endif
4158 /* Restriction (17): If the sub-query is a compound SELECT, then it must
4159 ** use only the UNION ALL operator. And none of the simple select queries
4160 ** that make up the compound SELECT are allowed to be aggregate or distinct
4161 ** queries.
4162 */
4166 }
4169 }
4179 #ifndef SQLITE_OMIT_WINDOWFUNC
4181 #endif
4182 ){
4184 }
4186 }
4188 /* Restriction (18). */
4193 }
4194 }
4196 /* Restriction (23) */
4203 }
4204 }
4206 /***** If we reach this point, flattening is permitted. *****/
4210 /* Authorize the subquery */
4216 /* Delete the transient structures associated with thesubquery */
4227 /* If the sub-query is a compound SELECT statement, then (by restrictions
4228 ** 17 and 18 above) it must be a UNION ALL and the parent query must
4229 ** be of the form:
4230 **
4231 ** SELECT <expr-list> FROM (<sub-query>) <where-clause>
4232 **
4233 ** followed by any ORDER BY, LIMIT and/or OFFSET clauses. This block
4234 ** creates N-1 copies of the parent query without any ORDER BY, LIMIT or
4235 ** OFFSET clauses and joins them to the left-hand-side of the original
4236 ** using UNION ALL operators. In this case N is the number of simple
4237 ** select statements in the compound sub-query.
4238 **
4239 ** Example:
4240 **
4241 ** SELECT a+1 FROM (
4242 ** SELECT x FROM tab
4243 ** UNION ALL
4244 ** SELECT y FROM tab
4245 ** UNION ALL
4246 ** SELECT abs(z*2) FROM tab2
4247 ** ) WHERE a!=5 ORDER BY 1
4248 **
4249 ** Transformed into:
4250 **
4251 ** SELECT x+1 FROM tab WHERE x+1!=5
4252 ** UNION ALL
4253 ** SELECT y+1 FROM tab WHERE y+1!=5
4254 ** UNION ALL
4255 ** SELECT abs(z*2)+1 FROM tab2 WHERE abs(z*2)+1!=5
4256 ** ORDER BY 1
4257 **
4258 ** We call this the "compound-subquery flattening".
4259 */
4281 }
4288 }
4290 }
4295 }
4297 /* Defer deleting the Table object associated with the
4298 ** subquery until code generation is
4299 ** complete, since there may still exist Expr.pTab entries that
4300 ** refer to the subquery even after flattening. Ticket #3346.
4301 **
4302 ** pSubitem->pTab is always non-NULL by test restrictions and tests above.
4303 */
4310 pTabToDel);
4314 }
4316 }
4318 /* The following loop runs once for each term in a compound-subquery
4319 ** flattening (as described above). If we are doing a different kind
4320 ** of flattening - a flattening other than a compound-subquery flattening -
4321 ** then this loop only runs once.
4322 **
4323 ** This loop moves all of the FROM elements of the subquery into the
4324 ** the FROM clause of the outer query. Before doing this, remember
4325 ** the cursor number for the original outer query FROM element in
4326 ** iParent. The iParent cursor will never be used. Subsequent code
4327 ** will scan expressions looking for iParent references and replace
4328 ** those references with expressions that resolve to the subquery FROM
4329 ** elements we are now copying in.
4330 */
4342 }
4344 /* The subquery uses a single slot of the FROM clause of the outer
4345 ** query. If the subquery has more than one element in its FROM clause,
4346 ** then expand the outer query to make space for it to hold all elements
4347 ** of the subquery.
4348 **
4349 ** Example:
4350 **
4351 ** SELECT * FROM tabA, (SELECT * FROM sub1, sub2), tabB;
4352 **
4353 ** The outer query has 3 slots in its FROM clause. One slot of the
4354 ** outer query (the middle slot) is used by the subquery. The next
4355 ** block of code will expand the outer query FROM clause to 4 slots.
4356 ** The middle slot is expanded to two slots in order to make space
4357 ** for the two elements in the FROM clause of the subquery.
4358 */
4363 }
4365 /* Transfer the FROM clause terms from the subquery into the
4366 ** outer query.
4367 */
4374 }
4377 /* Now begin substituting subquery result set expressions for
4378 ** references to the iParent in the outer query.
4379 **
4380 ** Example:
4381 **
4382 ** SELECT a+5, b*10 FROM (SELECT x*3 AS a, y+10 AS b FROM t1) WHERE a>b;
4383 ** \ \_____________ subquery __________/ /
4384 ** \_____________________ outer query ______________________________/
4385 **
4386 ** We look at every expression in the outer query and every place we see
4387 ** "a" we substitute "x*3" and every place we see "b" we substitute "y+10".
4388 */
4390 /* At this point, any non-zero iOrderByCol values indicate that the
4391 ** ORDER BY column expression is identical to the iOrderByCol'th
4392 ** expression returned by SELECT statement pSub. Since these values
4393 ** do not necessarily correspond to columns in SELECT statement pParent,
4394 ** zero them before transfering the ORDER BY clause.
4395 **
4396 ** Not doing this may cause an error if a subsequent call to this
4397 ** function attempts to flatten a compound sub-query into pParent
4398 ** (the only way this can happen is if the compound sub-query is
4399 ** currently part of pSub->pSrc). See ticket [d11a6e908f]. */
4403 }
4407 }
4412 }
4418 }
4419 }
4421 SubstContext x;
4428 }
4430 /* The flattened query is a compound if either the inner or the
4431 ** outer query is a compound. */
4435 /*
4436 ** SELECT ... FROM (SELECT ... LIMIT a OFFSET b) LIMIT x OFFSET y;
4437 **
4438 ** One is tempted to try to add a and b to combine the limits. But this
4439 ** does not work if either limit is negative.
4440 */
4444 }
4446 /* Recompute the SrcList_item.colUsed masks for the flattened
4447 ** tables. */
4450 }
4451 }
4453 /* Finially, delete what is left of the subquery and return
4454 ** success.
4455 */
4460 #if SELECTTRACE_ENABLED
4464 }
4465 #endif
4468 }
4471 /*
4472 ** A structure to keep track of all of the column values that are fixed to
4473 ** a known value due to WHERE clause constraints of the form COLUMN=VALUE.
4474 */
4483 };
4485 /*
4486 ** Add a new entry to the pConst object. Except, do not add duplicate
4487 ** pColumn entires. Also, do not add if doing so would not be appropriate.
4488 **
4489 ** The caller guarantees the pColumn is a column and pValue is a constant.
4490 ** This routine has to do some additional checks before completing the
4491 ** insert.
4492 */
4498 ){
4507 }
4509 /* 2018-10-25 ticket [cf5ed20f]
4510 ** Make sure the same pColumn is not inserted more than once */
4516 ){
4518 }
4519 }
4522 }
4532 }
4533 }
4535 /*
4536 ** Find all terms of COLUMN=VALUE or VALUE=COLUMN in pExpr where VALUE
4537 ** is a constant expression and where the term must be true because it
4538 ** is part of the AND-connected terms of the expression. For each term
4539 ** found, add it to the pConst structure.
4540 */
4549 }
4557 }
4560 }
4561 }
4563 /*
4564 ** This is a helper function for Walker callback propagateConstantExprRewrite().
4565 **
4566 ** Argument pExpr is a candidate expression to be replaced by a value. If
4567 ** pExpr is equivalent to one of the columns named in pWalker->u.pConst,
4568 ** then overwrite it with the corresponding value. Except, do not do so
4569 ** if argument bIgnoreAffBlob is non-zero and the affinity of pExpr
4570 ** is SQLITE_AFF_BLOB.
4571 */
4575 int bIgnoreAffBlob
4576 ){
4584 }
4592 }
4593 /* A match is found. Add the EP_FixedCol property */
4601 }
4603 }
4605 /*
4606 ** This is a Walker expression callback. pExpr is a node from the WHERE
4607 ** clause of a SELECT statement. This function examines pExpr to see if
4608 ** any substitutions based on the contents of pWalker->u.pConst should
4609 ** be made to pExpr or its immediate children.
4610 **
4611 ** A substitution is made if:
4612 **
4613 ** + pExpr is a column with an affinity other than BLOB that matches
4614 ** one of the columns in pWalker->u.pConst, or
4615 **
4616 ** + pExpr is a binary comparison operator (=, <=, >=, <, >) that
4617 ** uses an affinity other than TEXT and one of its immediate
4618 ** children is a column that matches one of the columns in
4619 ** pWalker->u.pConst.
4620 */
4630 ){
4635 }
4636 }
4637 }
4639 }
4641 /*
4642 ** The WHERE-clause constant propagation optimization.
4643 **
4644 ** If the WHERE clause contains terms of the form COLUMN=CONSTANT or
4645 ** CONSTANT=COLUMN that are top-level AND-connected terms that are not
4646 ** part of a ON clause from a LEFT JOIN, then throughout the query
4647 ** replace all other occurrences of COLUMN with CONSTANT.
4648 **
4649 ** For example, the query:
4650 **
4651 ** SELECT * FROM t1, t2, t3 WHERE t1.a=39 AND t2.b=t1.a AND t3.c=t2.b
4652 **
4653 ** Is transformed into
4654 **
4655 ** SELECT * FROM t1, t2, t3 WHERE t1.a=39 AND t2.b=39 AND t3.c=39
4656 **
4657 ** Return true if any transformations where made and false if not.
4658 **
4659 ** Implementation note: Constant propagation is tricky due to affinity
4660 ** and collating sequence interactions. Consider this example:
4661 **
4662 ** CREATE TABLE t1(a INT,b TEXT);
4663 ** INSERT INTO t1 VALUES(123,'0123');
4664 ** SELECT * FROM t1 WHERE a=123 AND b=a;
4665 ** SELECT * FROM t1 WHERE a=123 AND b=123;
4666 **
4667 ** The two SELECT statements above should return different answers. b=a
4668 ** is alway true because the comparison uses numeric affinity, but b=123
4669 ** is false because it uses text affinity and '0123' is not the same as '123'.
4670 ** To work around this, the expression tree is not actually changed from
4671 ** "b=a" to "b=123" but rather the "a" in "b=a" is tagged with EP_FixedCol
4672 ** and the "123" value is hung off of the pLeft pointer. Code generator
4673 ** routines know to generate the constant "123" instead of looking up the
4674 ** column value. Also, to avoid collation problems, this optimization is
4675 ** only attempted if the "a=123" term uses the default BINARY collation.
4676 **
4677 ** 2021-05-25 forum post 6a06202608: Another troublesome case is...
4678 **
4679 ** CREATE TABLE t1(x);
4680 ** INSERT INTO t1 VALUES(10.0);
4681 ** SELECT 1 FROM t1 WHERE x=10 AND x LIKE 10;
4682 **
4683 ** The query should return no rows, because the t1.x value is '10.0' not '10'
4684 ** and '10.0' is not LIKE '10'. But if we are not careful, the first WHERE
4685 ** term "x=10" will cause the second WHERE term to become "10 LIKE 10",
4686 ** resulting in a false positive. To avoid this, constant propagation for
4687 ** columns with BLOB affinity is only allowed if the constant is used with
4688 ** operators ==, <=, <, >=, >, or IS in a way that will cause the correct
4689 ** type conversions to occur. See logic associated with the bHasAffBlob flag
4690 ** for details.
4691 */
4695 ){
4696 WhereConst x;
4697 Walker w;
4718 }
4721 }
4723 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
4724 # if !defined(SQLITE_OMIT_WINDOWFUNC)
4725 /*
4726 ** This function is called to determine whether or not it is safe to
4727 ** push WHERE clause expression pExpr down to FROM clause sub-query
4728 ** pSubq, which contains at least one window function. Return 1
4729 ** if it is safe and the expression should be pushed down, or 0
4730 ** otherwise.
4731 **
4732 ** It is only safe to push the expression down if it consists only
4733 ** of constants and copies of expressions that appear in the PARTITION
4734 ** BY clause of all window function used by the sub-query. It is safe
4735 ** to filter out entire partitions, but not rows within partitions, as
4736 ** this may change the results of the window functions.
4737 **
4738 ** At the time this function is called it is guaranteed that
4739 **
4740 ** * the sub-query uses only one distinct window frame, and
4741 ** * that the window frame has a PARTITION BY clase.
4742 */
4748 }
4752 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
4753 /*
4754 ** Make copies of relevant WHERE clause terms of the outer query into
4755 ** the WHERE clause of subquery. Example:
4756 **
4757 ** SELECT * FROM (SELECT a AS x, c-d AS y FROM t1) WHERE x=5 AND y=10;
4758 **
4759 ** Transformed into:
4760 **
4761 ** SELECT * FROM (SELECT a AS x, c-d AS y FROM t1 WHERE a=5 AND c-d=10)
4762 ** WHERE x=5 AND y=10;
4763 **
4764 ** The hope is that the terms added to the inner query will make it more
4765 ** efficient.
4766 **
4767 ** Do not attempt this optimization if:
4768 **
4769 ** (1) (** This restriction was removed on 2017-09-29. We used to
4770 ** disallow this optimization for aggregate subqueries, but now
4771 ** it is allowed by putting the extra terms on the HAVING clause.
4772 ** The added HAVING clause is pointless if the subquery lacks
4773 ** a GROUP BY clause. But such a HAVING clause is also harmless
4774 ** so there does not appear to be any reason to add extra logic
4775 ** to suppress it. **)
4776 **
4777 ** (2) The inner query is the recursive part of a common table expression.
4778 **
4779 ** (3) The inner query has a LIMIT clause (since the changes to the WHERE
4780 ** clause would change the meaning of the LIMIT).
4781 **
4782 ** (4) The inner query is the right operand of a LEFT JOIN and the
4783 ** expression to be pushed down does not come from the ON clause
4784 ** on that LEFT JOIN.
4785 **
4786 ** (5) The WHERE clause expression originates in the ON or USING clause
4787 ** of a LEFT JOIN where iCursor is not the right-hand table of that
4788 ** left join. An example:
4789 **
4790 ** SELECT *
4791 ** FROM (SELECT 1 AS a1 UNION ALL SELECT 2) AS aa
4792 ** JOIN (SELECT 1 AS b2 UNION ALL SELECT 2) AS bb ON (a1=b2)
4793 ** LEFT JOIN (SELECT 8 AS c3 UNION ALL SELECT 9) AS cc ON (b2=2);
4794 **
4795 ** The correct answer is three rows: (1,1,NULL),(2,2,8),(2,2,9).
4796 ** But if the (b2=2) term were to be pushed down into the bb subquery,
4797 ** then the (1,1,NULL) row would be suppressed.
4798 **
4799 ** (6) Window functions make things tricky as changes to the WHERE clause
4800 ** of the inner query could change the window over which window
4801 ** functions are calculated. Therefore, do not attempt the optimization
4802 ** if:
4803 **
4804 ** (6a) The inner query uses multiple incompatible window partitions.
4805 **
4806 ** (6b) The inner query is a compound and uses window-functions.
4807 **
4808 ** (6c) The WHERE clause does not consist entirely of constants and
4809 ** copies of expressions found in the PARTITION BY clause of
4810 ** all window-functions used by the sub-query. It is safe to
4811 ** filter out entire partitions, as this does not change the
4812 ** window over which any window-function is calculated.
4813 **
4814 ** (7) The inner query is a Common Table Expression (CTE) that should
4815 ** be materialized. (This restriction is implemented in the calling
4816 ** routine.)
4817 **
4818 ** Return 0 if no changes are made and non-zero if one or more WHERE clause
4819 ** terms are duplicated into the subquery.
4820 */
4827 ){
4833 #ifndef SQLITE_OMIT_WINDOWFUNC
4838 }
4841 }
4842 #endif
4844 #ifdef SQLITE_DEBUG
4845 /* Only the first term of a compound can have a WITH clause. But make
4846 ** sure no other terms are marked SF_Recursive in case something changes
4847 ** in the future.
4848 */
4849 {
4853 }
4854 }
4855 #endif
4859 }
4864 }
4868 ){
4870 }
4873 ){
4875 }
4877 nChng++;
4880 SubstContext x;
4889 #ifndef SQLITE_OMIT_WINDOWFUNC
4891 /* Restriction 6c has prevented push-down in this case */
4893 nChng--;
4895 }
4896 #endif
4901 }
4903 }
4904 }
4906 }
4909 /*
4910 ** The pFunc is the only aggregate function in the query. Check to see
4911 ** if the query is a candidate for the min/max optimization.
4912 **
4913 ** If the query is a candidate for the min/max optimization, then set
4914 ** *ppMinMax to be an ORDER BY clause to be used for the optimization
4915 ** and return either WHERE_ORDERBY_MIN or WHERE_ORDERBY_MAX depending on
4916 ** whether pFunc is a min() or max() function.
4917 **
4918 ** If the query is not a candidate for the min/max optimization, return
4919 ** WHERE_ORDERBY_NORMAL (which must be zero).
4920 **
4921 ** This routine must be called after aggregate functions have been
4922 ** located but before their arguments have been subjected to aggregate
4923 ** analysis.
4924 */
4941 ){
4943 }
4950 }
4956 }
4961 }
4963 /*
4964 ** The select statement passed as the first argument is an aggregate query.
4965 ** The second argument is the associated aggregate-info object. This
4966 ** function tests if the SELECT is of the form:
4967 **
4968 ** SELECT count(*) FROM <tbl>
4969 **
4970 ** where table is a database table, not a sub-select or view. If the query
4971 ** does match this pattern, then a pointer to the Table object representing
4972 ** <tbl> is returned. Otherwise, NULL is returned.
4973 **
4974 ** This routine checks to see if it is safe to use the count optimization.
4975 ** A correct answer is still obtained (though perhaps more slowly) if
4976 ** this routine returns NULL when it could have returned a table pointer.
4977 ** But returning the pointer when NULL should have been returned can
4978 ** result in incorrect answers and/or crashes. So, when in doubt, return NULL.
4979 */
4991 ){
4993 }
5009 }
5011 /*
5012 ** If the source-list item passed as an argument was augmented with an
5013 ** INDEXED BY clause, then try to locate the specified index. If there
5014 ** was such a clause and the named index cannot be found, return
5015 ** SQLITE_ERROR and leave an error in pParse. Otherwise, populate
5016 ** pFrom->pIndex and return SQLITE_OK.
5017 */
5028 );
5033 }
5037 }
5039 /*
5040 ** Detect compound SELECT statements that use an ORDER BY clause with
5041 ** an alternative collating sequence.
5042 **
5043 ** SELECT ... FROM t1 EXCEPT SELECT ... FROM t2 ORDER BY .. COLLATE ...
5044 **
5045 ** These are rewritten as a subquery:
5046 **
5047 ** SELECT * FROM (SELECT ... FROM t1 EXCEPT SELECT ... FROM t2)
5048 ** ORDER BY ... COLLATE ...
5049 **
5050 ** This transformation is necessary because the multiSelectOrderBy() routine
5051 ** above that generates the code for a compound SELECT with an ORDER BY clause
5052 ** uses a merge algorithm that requires the same collating sequence on the
5053 ** result columns as on the ORDER BY clause. See ticket
5054 ** http://www.sqlite.org/src/info/6709574d2a
5055 **
5056 ** This transformation is only needed for EXCEPT, INTERSECT, and UNION.
5057 ** The UNION ALL operator works fine with multiSelectOrderBy() even when
5058 ** there are COLLATE terms in the ORDER BY.
5059 */
5068 Token dummy;
5075 #ifndef SQLITE_OMIT_WINDOWFUNC
5076 /* If iOrderByCol is already non-zero, then it has already been matched
5077 ** to a result column of the SELECT statement. This occurs when the
5078 ** SELECT is rewritten for window-functions processing and then passed
5079 ** to sqlite3SelectPrep() and similar a second time. The rewriting done
5080 ** by this function is not required in this case. */
5082 #endif
5085 }
5088 /* If we reach this point, that means the transformation is required. */
5108 #ifndef SQLITE_OMIT_WINDOWFUNC
5110 #endif
5118 }
5120 /*
5121 ** Check to see if the FROM clause term pFrom has table-valued function
5122 ** arguments. If it does, leave an error message in pParse and return
5123 ** non-zero, since pFrom is not allowed to be a table-valued function.
5124 */
5129 }
5131 }
5133 #ifndef SQLITE_OMIT_CTE
5134 /*
5135 ** Argument pWith (which may be NULL) points to a linked list of nested
5136 ** WITH contexts, from inner to outermost. If the table identified by
5137 ** FROM clause element pItem is really a common-table-expression (CTE)
5138 ** then return a pointer to the CTE definition for that table. Otherwise
5139 ** return NULL.
5140 **
5141 ** If a non-NULL value is returned, set *ppContext to point to the With
5142 ** object that the returned CTE belongs to.
5143 */
5148 ){
5159 }
5160 }
5162 }
5164 }
5166 /* The code generator maintains a stack of active WITH clauses
5167 ** with the inner-most WITH clause being at the top of the stack.
5168 **
5169 ** This routine pushes the WITH clause passed as the second argument
5170 ** onto the top of the stack. If argument bFree is true, then this
5171 ** WITH clause will never be popped from the stack but should instead
5172 ** be freed along with the Parse object. In other cases, when
5173 ** bFree==0, the With object will be freed along with the SELECT
5174 ** statement with which it is associated.
5175 **
5176 ** This routine returns a copy of pWith. Or, if bFree is true and
5177 ** the pWith object is destroyed immediately due to an OOM condition,
5178 ** then this routine return NULL.
5179 **
5180 ** If bFree is true, do not continue to use the pWith pointer after
5181 ** calling this routine, Instead, use only the return value.
5182 */
5188 pWith);
5190 }
5195 }
5196 }
5198 }
5200 /*
5201 ** This function checks if argument pFrom refers to a CTE declared by
5202 ** a WITH clause on the stack currently maintained by the parser (on the
5203 ** pParse->pWith linked list). And if currently processing a CTE
5204 ** CTE expression, through routine checks to see if the reference is
5205 ** a recursive reference to the CTE.
5206 **
5207 ** If pFrom matches a CTE according to either of these two above, pFrom->pTab
5208 ** and other fields are populated accordingly.
5209 **
5210 ** Return 0 if no match is found.
5211 ** Return 1 if a match is found.
5212 ** Return 2 if an error condition is detected.
5213 */
5218 ){
5224 /* There are no WITH clauses in the stack. No match is possible */
5226 }
5228 /* Prior errors might have left pParse->pWith in a goofy state, so
5229 ** go no further. */
5231 }
5233 /* The FROM term contains a schema qualifier (ex: main.t1) and so
5234 ** it cannot possibly be a CTE reference. */
5236 }
5238 /* The FROM term is specifically excluded from matching a CTE.
5239 ** (1) It is part of a trigger that used to have zDatabase but had
5240 ** zDatabase removed by sqlite3FixTriggerStep().
5241 ** (2) This is the first term in the FROM clause of an UPDATE.
5242 */
5244 }
5258 /* If pCte->zCteErr is non-NULL at this point, then this is an illegal
5259 ** recursive reference to CTE pCte. Leave an error in pParse and return
5260 ** early. If pCte->zCteErr is NULL, then this is not a recursive reference.
5261 ** In this case, proceed. */
5265 }
5276 ){
5279 }
5281 }
5295 }
5301 }
5303 /* Check if this is a recursive CTE. */
5315 ){
5322 );
5324 }
5328 }
5329 }
5332 }
5350 }
5355 }
5356 }
5365 );
5368 }
5370 }
5378 }
5380 }
5384 }
5386 }
5387 #endif
5389 #ifndef SQLITE_OMIT_CTE
5390 /*
5391 ** If the SELECT passed as the second argument has an associated WITH
5392 ** clause, pop it from the stack stored as part of the Parse object.
5393 **
5394 ** This function is used as the xSelectCallback2() callback by
5395 ** sqlite3SelectExpand() when walking a SELECT tree to resolve table
5396 ** names and other FROM clause elements.
5397 */
5405 }
5406 }
5407 }
5408 #endif
5410 /*
5411 ** The SrcList_item structure passed as the second argument represents a
5412 ** sub-query in the FROM clause of a SELECT statement. This function
5413 ** allocates and populates the SrcList_item.pTab object. If successful,
5414 ** SQLITE_OK is returned. Otherwise, if an OOM error is encountered,
5415 ** SQLITE_NOMEM.
5416 */
5429 }
5434 #ifndef SQLITE_ALLOW_ROWID_IN_VIEW
5435 /* The usual case - do not allow ROWID on a subquery */
5437 #else
5439 #endif
5443 }
5445 /*
5446 ** This routine is a Walker callback for "expanding" a SELECT statement.
5447 ** "Expanding" means to do the following:
5448 **
5449 ** (1) Make sure VDBE cursor numbers have been assigned to every
5450 ** element of the FROM clause.
5451 **
5452 ** (2) Fill in the pTabList->a[].pTab fields in the SrcList that
5453 ** defines FROM clause. When views appear in the FROM clause,
5454 ** fill pTabList->a[].pSelect with a copy of the SELECT statement
5455 ** that implements the view. A copy is made of the view's SELECT
5456 ** statement so that we can freely modify or delete that statement
5457 ** without worrying about messing up the persistent representation
5458 ** of the view.
5459 **
5460 ** (3) Add terms to the WHERE clause to accommodate the NATURAL keyword
5461 ** on joins and the ON and USING clause of joins.
5462 **
5463 ** (4) Scan the list of columns in the result set (pEList) looking
5464 ** for instances of the "*" operator or the TABLE.* operator.
5465 ** If found, expand each "*" to be every column in every table
5466 ** and TABLE.* to be every column in TABLE.
5467 **
5468 */
5483 }
5487 }
5489 /* Renumber selId because it has been copied from a view */
5491 }
5499 }
5500 }
5502 }
5505 /* Make sure cursor numbers have been assigned to all entries in
5506 ** the FROM clause of the SELECT statement.
5507 */
5510 /* Look up every table named in the FROM clause of the select. If
5511 ** an entry of the FROM clause is a subquery instead of a table or view,
5512 ** then create a transient table structure to describe the subquery.
5513 */
5520 #ifndef SQLITE_OMIT_SUBQUERY
5522 /* A sub-query in the FROM clause of a SELECT */
5527 #endif
5528 #ifndef SQLITE_OMIT_CTE
5533 #endif
5535 /* An ordinary table or view name in the FROM clause */
5544 }
5548 }
5549 #if !defined(SQLITE_OMIT_VIEW) || !defined(SQLITE_OMIT_VIRTUALTABLE)
5551 i16 nCol;
5558 ){
5561 }
5563 }
5564 #ifndef SQLITE_OMIT_VIRTUALTABLE
5569 ){
5572 }
5574 #endif
5581 }
5582 #endif
5583 }
5585 /* Locate the index named by the INDEXED BY clause, if any. */
5588 }
5589 }
5591 /* Process NATURAL keywords, and ON and USING clauses of joins.
5592 */
5596 }
5598 /* For every "*" that occurs in the column list, insert the names of
5599 ** all columns in all tables. And for every TABLE.* insert the names
5600 ** of all columns in TABLE. The parser inserted a special expression
5601 ** with the TK_ASTERISK operator for each "*" that it found in the column
5602 ** list. The following code just has to locate the TK_ASTERISK
5603 ** expressions and expand each one to the list of all columns in
5604 ** all tables.
5605 **
5606 ** The first loop just checks to see if there are any "*" operators
5607 ** that need expanding.
5608 */
5616 }
5618 /*
5619 ** If we get here it means the result set contains one or more "*"
5620 ** operators that need to be expanded. Loop through each expression
5621 ** in the result set and expand them one by one.
5622 */
5636 ){
5637 /* This particular expression does not need to be expanded.
5638 */
5644 }
5647 /* This expression is a "*" or a "TABLE.*" and needs to be
5648 ** expanded. */
5655 }
5664 }
5670 }
5673 }
5683 ){
5685 }
5687 /* If a column is marked as 'hidden', omit it from the expanded
5688 ** result-set list unless the SELECT has the SF_IncludeHidden
5689 ** bit set.
5690 */
5693 ){
5695 }
5701 ){
5702 /* In a NATURAL join, omit the join columns from the
5703 ** table to the right of the join */
5705 }
5707 /* In a join with a USING clause, omit columns in the
5708 ** using clause from the table on the right. */
5710 }
5711 }
5722 }
5726 }
5729 }
5743 }
5745 }
5747 }
5748 }
5754 }
5755 }
5756 }
5757 }
5760 }
5765 }
5768 }
5769 }
5771 }
5773 #if SQLITE_DEBUG
5774 /*
5775 ** Always assert. This xSelectCallback2 implementation proves that the
5776 ** xSelectCallback2 is never invoked.
5777 */
5781 }
5782 #endif
5783 /*
5784 ** This routine "expands" a SELECT statement and all of its subqueries.
5785 ** For additional information on what it means to "expand" a SELECT
5786 ** statement, see the comment on the selectExpand worker callback above.
5787 **
5788 ** Expanding a SELECT statement is the first step in processing a
5789 ** SELECT statement. The SELECT statement must be expanded before
5790 ** name resolution is performed.
5791 **
5792 ** If anything goes wrong, an error message is written into pParse.
5793 ** The calling function can detect the problem by looking at pParse->nErr
5794 ** and/or pParse->db->mallocFailed.
5795 */
5797 Walker w;
5804 }
5809 }
5812 #ifndef SQLITE_OMIT_SUBQUERY
5813 /*
5814 ** This is a Walker.xSelectCallback callback for the sqlite3SelectTypeInfo()
5815 ** interface.
5816 **
5817 ** For each FROM-clause subquery, add Column.zType and Column.zColl
5818 ** information to the Table structure that represents the result set
5819 ** of that subquery.
5820 **
5821 ** The Table structure that represents the result set was constructed
5822 ** by selectExpander() but the type and collation information was omitted
5823 ** at that point because identifiers had not yet been resolved. This
5824 ** routine is called after identifier resolution.
5825 */
5841 /* A sub-query in the FROM clause of a SELECT */
5846 SQLITE_AFF_NONE);
5847 }
5848 }
5849 }
5850 }
5851 #endif
5854 /*
5855 ** This routine adds datatype and collating sequence information to
5856 ** the Table structures of all FROM-clause subqueries in a
5857 ** SELECT statement.
5858 **
5859 ** Use this routine after name resolution.
5860 */
5862 #ifndef SQLITE_OMIT_SUBQUERY
5863 Walker w;
5869 #endif
5870 }
5873 /*
5874 ** This routine sets up a SELECT statement for processing. The
5875 ** following is accomplished:
5876 **
5877 ** * VDBE Cursor numbers are assigned to all FROM-clause terms.
5878 ** * Ephemeral Table objects are created for all FROM-clause subqueries.
5879 ** * ON and USING clauses are shifted into WHERE statements
5880 ** * Wildcards "*" and "TABLE.*" in result sets are expanded.
5881 ** * Identifiers in expression are matched to tables.
5882 **
5883 ** This routine acts recursively on all subqueries within the SELECT.
5884 */
5889 ){
5899 }
5901 /*
5902 ** Reset the aggregate accumulator.
5903 **
5904 ** The aggregate accumulator is a set of memory cells that hold
5905 ** intermediate results while calculating an aggregate. This
5906 ** routine generates code that stores NULLs in all of those memory
5907 ** cells.
5908 */
5918 #ifdef SQLITE_DEBUG
5919 /* Verify that all AggInfo registers are within the range specified by
5920 ** AggInfo.mnReg..AggInfo.mxReg */
5925 }
5929 }
5930 #endif
5946 }
5947 }
5948 }
5949 }
5951 /*
5952 ** Invoke the OP_AggFinalize opcode for every aggregate function
5953 ** in the AggInfo structure.
5954 */
5965 }
5966 }
5969 /*
5970 ** Update the accumulator memory cells for an aggregate based on
5971 ** the current cursor position.
5972 **
5973 ** If regAcc is non-zero and there are no min() or max() aggregates
5974 ** in pAggInfo, then only populate the pAggInfo->nAccumulator accumulator
5975 ** registers if register regAcc contains 0. The caller will take care
5976 ** of setting and clearing regAcc.
5977 */
5982 int eDistinctType
5983 ){
6004 && regAcc
6005 ){
6006 /* If regAcc==0, there there exists some min() or max() function
6007 ** without a FILTER clause that will ensure the magnet registers
6008 ** are populated. */
6010 /* If this is the first row of the group (regAcc contains 0), clear the
6011 ** "magnet" register regHit so that the accumulator registers
6012 ** are populated if the FILTER clause jumps over the the
6013 ** invocation of min() or max() altogether. Or, if this is not
6014 ** the first row (regAcc contains 1), set the magnet register so that
6015 ** the accumulators are not populated unless the min()/max() is invoked
6016 ** and indicates that they should be. */
6018 }
6021 }
6029 }
6033 }
6036 }
6044 }
6047 }
6050 }
6057 }
6058 }
6061 }
6064 }
6067 }
6072 }
6073 }
6075 /*
6076 ** Add a single OP_Explain instruction to the VDBE to explain a simple
6077 ** count(*) query ("SELECT count(*) FROM pTab").
6078 */
6079 #ifndef SQLITE_OMIT_EXPLAIN
6084 ){
6091 );
6092 }
6093 }
6094 #else
6095 # define explainSimpleCount(a,b,c)
6096 #endif
6098 /*
6099 ** sqlite3WalkExpr() callback used by havingToWhere().
6100 **
6101 ** If the node passed to the callback is a TK_AND node, return
6102 ** WRC_Continue to tell sqlite3WalkExpr() to iterate through child nodes.
6103 **
6104 ** Otherwise, return WRC_Prune. In this case, also check if the
6105 ** sub-expression matches the criteria for being moved to the WHERE
6106 ** clause. If so, add it to the WHERE clause and replace the sub-expression
6107 ** within the HAVING expression with a constant "1".
6108 */
6112 /* This routine is called before the HAVING clause of the current
6113 ** SELECT is analyzed for aggregates. So if pExpr->pAggInfo is set
6114 ** here, it indicates that the expression is a correlated reference to a
6115 ** column from an outer aggregate query, or an aggregate function that
6116 ** belongs to an outer query. Do not move the expression to the WHERE
6117 ** clause in this obscure case, as doing so may corrupt the outer Select
6118 ** statements AggInfo structure. */
6122 ){
6131 }
6132 }
6134 }
6136 }
6138 /*
6139 ** Transfer eligible terms from the HAVING clause of a query, which is
6140 ** processed after grouping, to the WHERE clause, which is processed before
6141 ** grouping. For example, the query:
6142 **
6143 ** SELECT * FROM <tables> WHERE a=? GROUP BY b HAVING b=? AND c=?
6144 **
6145 ** can be rewritten as:
6146 **
6147 ** SELECT * FROM <tables> WHERE a=? AND b=? GROUP BY b HAVING c=?
6148 **
6149 ** A term of the HAVING expression is eligible for transfer if it consists
6150 ** entirely of constants and expressions that are also GROUP BY terms that
6151 ** use the "BINARY" collation sequence.
6152 */
6154 Walker sWalker;
6160 #if SELECTTRACE_ENABLED
6164 }
6165 #endif
6166 }
6168 /*
6169 ** Check to see if the pThis entry of pTabList is a self-join of a prior view.
6170 ** If it is, then return the SrcList_item for the prior view. If it is not,
6171 ** then return 0.
6172 */
6176 ){
6191 /* The query flattener left two different CTE tables with identical
6192 ** names in the same FROM clause. */
6194 }
6196 /* The view was modified by some other optimization such as
6197 ** pushDownWhereTerms() */
6199 }
6201 }
6203 }
6205 /*
6206 ** Deallocate a single AggInfo object
6207 */
6212 }
6214 #ifdef SQLITE_COUNTOFVIEW_OPTIMIZATION
6215 /*
6216 ** Attempt to transform a query of the form
6217 **
6218 ** SELECT count(*) FROM (SELECT x FROM t1 UNION ALL SELECT y FROM t2)
6219 **
6220 ** Into this:
6221 **
6222 ** SELECT (SELECT count(*) FROM t1)+(SELECT count(*) FROM t2)
6223 **
6224 ** The transformation only works if all of the following are true:
6225 **
6226 ** * The subquery is a UNION ALL of two or more terms
6227 ** * The subquery does not have a LIMIT clause
6228 ** * There is no WHERE or GROUP BY or HAVING clauses on the subqueries
6229 ** * The outer query is a simple count(*) with no WHERE clause or other
6230 ** extraneous syntax.
6231 **
6232 ** Return TRUE if the optimization is undertaken.
6233 */
6261 /* If we reach this point then it is OK to perform the transformation */
6287 }
6289 }
6293 #if SELECTTRACE_ENABLED
6297 }
6298 #endif
6300 }
6303 /*
6304 ** Generate code for the SELECT statement given in the p argument.
6305 **
6306 ** The results are returned according to the SelectDest structure.
6307 ** See comments in sqliteInt.h for further information.
6308 **
6309 ** This routine returns the number of errors. If any errors are
6310 ** encountered, then an appropriate error message is left in
6311 ** pParse->zErrMsg.
6312 **
6313 ** This routine does NOT free the Select structure passed in. The
6314 ** calling function needs to do that.
6315 */
6320 ){
6344 }
6347 #if SELECTTRACE_ENABLED
6351 }
6352 #endif
6362 /* All of these destinations are also able to ignore the ORDER BY clause */
6364 #if SELECTTRACE_ENABLED
6368 }
6369 #endif
6375 }
6378 }
6382 }
6385 #if SELECTTRACE_ENABLED
6389 }
6390 #endif
6392 /* If the SF_UFSrcCheck flag is set, then this function is being called
6393 ** as part of populating the temp table for an UPDATE...FROM statement.
6394 ** In this case, it is an error if the target object (pSrc->a[0]) name
6395 ** or alias is duplicated within FROM clause (pSrc->a[1..n]).
6396 **
6397 ** Postgres disallows this case too. The reason is that some other
6398 ** systems handle this case differently, and not all the same way,
6399 ** which is just confusing. To avoid this, we follow PG's lead and
6400 ** disallow it altogether. */
6409 );
6411 }
6412 }
6414 /* Clear the SF_UFSrcCheck flag. The check has already been performed,
6415 ** and leaving this flag set can cause errors if a compound sub-query
6416 ** in p->pSrc is flattened into this query and this function called
6417 ** again as part of compound SELECT processing. */
6419 }
6423 }
6425 #ifndef SQLITE_OMIT_WINDOWFUNC
6429 }
6430 #if SELECTTRACE_ENABLED
6434 }
6435 #endif
6442 /* Try to do various optimizations (flattening subqueries, and strength
6443 ** reduction of join operators) in the FROM clause up into the main query
6444 */
6445 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
6451 /* The expander should have already created transient Table objects
6452 ** even for FROM clause elements such as subqueries that do not correspond
6453 ** to a real table */
6456 /* Convert LEFT JOIN into JOIN if there are terms of the right table
6457 ** of the LEFT JOIN used in the WHERE clause.
6458 */
6462 ){
6467 }
6469 /* No futher action if this term of the FROM clause is no a subquery */
6472 /* Catch mismatch in the declared columns of a view and the number of
6473 ** columns in the SELECT on the RHS */
6478 }
6480 /* Do not try to flatten an aggregate subquery.
6481 **
6482 ** Flattening an aggregate subquery is only possible if the outer query
6483 ** is not a join. But if the outer query is not a join, then the subquery
6484 ** will be implemented as a co-routine and there is no advantage to
6485 ** flattening in that case.
6486 */
6490 /* If a FROM-clause subquery has an ORDER BY clause that is not
6491 ** really doing anything, then delete it now so that it does not
6492 ** interfere with query flattening. See the discussion at
6493 ** https://sqlite.org/forum/forumpost/2d76f2bcf65d256a
6494 **
6495 ** Beware of these cases where the ORDER BY clause may not be safely
6496 ** omitted:
6497 **
6498 ** (1) There is also a LIMIT clause
6499 ** (2) The subquery was added to help with window-function
6500 ** processing
6501 ** (3) The subquery is in the FROM clause of an UPDATE
6502 ** (4) The outer query uses an aggregate function other than
6503 ** the built-in count(), min(), or max().
6504 ** (5) The ORDER BY isn't going to accomplish anything because
6505 ** one of:
6506 ** (a) The outer query has a different ORDER BY clause
6507 ** (b) The subquery is part of a join
6508 ** See forum post 062d576715d277c8
6509 */
6516 ){
6521 }
6523 /* If the outer query contains a "complex" result set (that is,
6524 ** if the result set of the outer query uses functions or subqueries)
6525 ** and if the subquery contains an ORDER BY clause and if
6526 ** it will be implemented as a co-routine, then do not flatten. This
6527 ** restriction allows SQL constructs like this:
6528 **
6529 ** SELECT expensive_function(x)
6530 ** FROM (SELECT x FROM tab ORDER BY y LIMIT 10);
6531 **
6532 ** The expensive_function() is only computed on the 10 rows that
6533 ** are output, rather than every row of the table.
6534 **
6535 ** The requirement that the outer query have a complex result set
6536 ** means that flattening does occur on simpler SQL constraints without
6537 ** the expensive_function() like:
6538 **
6539 ** SELECT x FROM (SELECT x FROM tab ORDER BY y LIMIT 10);
6540 */
6546 ){
6548 }
6552 /* This subquery can be absorbed into its parent. */
6554 }
6559 }
6560 }
6561 #endif
6563 #ifndef SQLITE_OMIT_COMPOUND_SELECT
6564 /* Handle compound SELECT statements using the separate multiSelect()
6565 ** procedure.
6566 */
6569 #if SELECTTRACE_ENABLED
6573 }
6574 #endif
6577 }
6578 #endif
6580 /* Do the WHERE-clause constant propagation optimization if this is
6581 ** a join. No need to speed time on this operation for non-join queries
6582 ** as the equivalent optimization will be handled by query planner in
6583 ** sqlite3WhereBegin().
6584 */
6589 ){
6590 #if SELECTTRACE_ENABLED
6594 }
6595 #endif
6598 }
6600 #ifdef SQLITE_COUNTOFVIEW_OPTIMIZATION
6603 ){
6607 }
6608 #endif
6610 /* For each term in the FROM clause, do two things:
6611 ** (1) Authorized unreferenced tables
6612 ** (2) Generate code for all sub-queries
6613 */
6617 SelectDest dest;
6619 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
6621 #endif
6623 /* Issue SQLITE_READ authorizations with a fake column name for any
6624 ** tables that are referenced but from which no values are extracted.
6625 ** Examples of where these kinds of null SQLITE_READ authorizations
6626 ** would occur:
6627 **
6628 ** SELECT count(*) FROM t1; -- SQLITE_READ t1.""
6629 ** SELECT t1.* FROM t1, t2; -- SQLITE_READ t2.""
6630 **
6631 ** The fake column name is an empty string. It is possible for a table to
6632 ** have a column named by the empty string, in which case there is no way to
6633 ** distinguish between an unreferenced table and an actual reference to the
6634 ** "" column. The original design was for the fake column name to be a NULL,
6635 ** which would be unambiguous. But legacy authorization callbacks might
6636 ** assume the column name is non-NULL and segfault. The use of an empty
6637 ** string for the fake column name seems safer.
6638 */
6641 }
6643 #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
6644 /* Generate code for all sub-queries in the FROM clause
6645 */
6649 /* The code for a subquery should only be generated once. */
6652 /* Increment Parse.nHeight by the height of the largest expression
6653 ** tree referred to by this, the parent select. The child select
6654 ** may contain expression trees of at most
6655 ** (SQLITE_MAX_EXPR_DEPTH-Parse.nHeight) height. This is a bit
6656 ** more conservative than necessary, but much easier than enforcing
6657 ** an exact limit.
6658 */
6661 /* Make copies of constant WHERE-clause terms in the outer query down
6662 ** inside the subquery. This can help the subquery to run more efficiently.
6663 */
6669 ){
6670 #if SELECTTRACE_ENABLED
6675 }
6676 #endif
6680 }
6685 /* Generate code to implement the subquery
6686 **
6687 ** The subquery is implemented as a co-routine if:
6688 ** (1) the subquery is guaranteed to be the outer loop (so that
6689 ** it does not need to be computed more than once), and
6690 ** (2) the subquery is not a CTE that should be materialized
6691 **
6692 ** TODO: Are there other reasons beside (1) and (2) to use a co-routine
6693 ** implementation?
6694 */
6699 ){
6700 /* Implement a co-routine that will return a single row of the result
6701 ** set on each invocation.
6702 */
6719 /* This is a CTE for which materialization code has already been
6720 ** generated. Invoke the subroutine to compute the materialization,
6721 ** the make the pItem->iCursor be a copy of the ephemerial table that
6722 ** holds the result of the materialization. */
6728 }
6731 /* This view has already been materialized by a prior entry in
6732 ** this same FROM clause. Reuse it. */
6735 }
6739 /* Materialize the view. If the view is not correlated, generate a
6740 ** subroutine to do the materialization so that subsequent uses of
6741 ** the same view can reuse the materialization. */
6750 /* If the subquery is not correlated and if we are not inside of
6751 ** a trigger, then we only need to compute the value of the subquery
6752 ** once. */
6757 }
6773 }
6774 }
6778 #endif
6779 }
6781 /* Various elements of the SELECT copied into local variables for
6782 ** convenience */
6789 #if SELECTTRACE_ENABLED
6793 }
6794 #endif
6796 /* If the query is DISTINCT with an ORDER BY but is not an aggregate, and
6797 ** if the select-list is the same as the ORDER BY list, then this query
6798 ** can be rewritten as a GROUP BY. In other words, this:
6799 **
6800 ** SELECT DISTINCT xyz FROM ... ORDER BY xyz
6801 **
6802 ** is transformed to:
6803 **
6804 ** SELECT xyz FROM ... GROUP BY xyz ORDER BY xyz
6805 **
6806 ** The second form is preferred as a single index (or temp-table) may be
6807 ** used for both the ORDER BY and DISTINCT processing. As originally
6808 ** written the query must use a temp-table for at least one of the ORDER
6809 ** BY and DISTINCT, and an index or separate temp-table for the other.
6810 */
6813 #ifndef SQLITE_OMIT_WINDOWFUNC
6815 #endif
6816 ){
6820 /* Notice that even thought SF_Distinct has been cleared from p->selFlags,
6821 ** the sDistinct.isTnct is still set. Hence, isTnct represents the
6822 ** original setting of the SF_Distinct flag, not the current setting */
6825 #if SELECTTRACE_ENABLED
6829 }
6830 #endif
6831 }
6833 /* If there is an ORDER BY clause, then create an ephemeral index to
6834 ** do the sorting. But this sorting ephemeral index might end up
6835 ** being unused if the data can be extracted in pre-sorted order.
6836 ** If that is the case, then the OP_OpenEphemeral instruction will be
6837 ** changed to an OP_Noop once we figure out that the sorting index is
6838 ** not needed. The sSort.addrSortIndex variable is used to facilitate
6839 ** that change.
6840 */
6850 );
6853 }
6855 /* If the output is destined for a temporary table, open that table.
6856 */
6859 }
6861 /* Set the limiter.
6862 */
6866 }
6871 }
6873 /* Open an ephemeral index to use for the distinct set.
6874 */
6880 P4_KEYINFO);
6885 }
6888 /* No aggregate functions and no GROUP BY clause */
6891 #ifndef SQLITE_OMIT_WINDOWFUNC
6895 }
6896 #endif
6900 /* Begin the database scan. */
6907 }
6910 }
6916 }
6917 }
6920 /* If sorting index that was created by a prior OP_OpenEphemeral
6921 ** instruction ended up not being needed, then change the OP_OpenEphemeral
6922 ** into an OP_Noop.
6923 */
6926 }
6929 #ifndef SQLITE_OMIT_WINDOWFUNC
6949 {
6950 /* Use the standard inner loop. */
6955 /* End the database scan loop.
6956 */
6959 }
6961 /* This case when there exist aggregate functions or a GROUP BY clause
6962 ** or both */
6967 ** one row of the input to the aggregator has been
6968 ** processed */
6976 /* Remove any and all aliases between the result set and the
6977 ** GROUP BY clause.
6978 */
6985 }
6988 }
6992 /* If there is both a GROUP BY and an ORDER BY clause and they are
6993 ** identical, then it may be possible to disable the ORDER BY clause
6994 ** on the grounds that the GROUP BY will cause elements to come out
6995 ** in the correct order. It also may not - the GROUP BY might use a
6996 ** database index that causes rows to be grouped together as required
6997 ** but not actually sorted. Either way, record the fact that the
6998 ** ORDER BY and GROUP BY clauses are the same by setting the orderByGrp
6999 ** variable. */
7002 /* The GROUP BY processing doesn't care whether rows are delivered in
7003 ** ASC or DESC order - only that each group is returned contiguously.
7004 ** So set the ASC/DESC flags in the GROUP BY to match those in the
7005 ** ORDER BY to maximize the chances of rows being delivered in an
7006 ** order that makes the ORDER BY redundant. */
7010 }
7013 }
7014 }
7018 }
7020 /* Create a label to jump to when we want to abort the query */
7023 /* Convert TK_COLUMN nodes into TK_AGG_COLUMN and make entries in
7024 ** sAggInfo for all TK_AGG_FUNCTION nodes in expressions of the
7025 ** SELECT statement.
7026 */
7032 }
7035 }
7054 }
7056 }
7062 }
7068 #ifndef SQLITE_OMIT_WINDOWFUNC
7072 }
7073 #endif
7075 }
7078 #if SELECTTRACE_ENABLED
7086 }
7091 }
7096 }
7097 }
7098 #endif
7101 /* Processing for aggregates with GROUP BY is very different and
7102 ** much more complex than aggregates without a GROUP BY.
7103 */
7123 ){
7129 }
7131 /* If there is a GROUP BY clause we might need a sorting index to
7132 ** implement it. Allocate that sorting index now. If it turns out
7133 ** that we do not need it after all, the OP_SorterOpen instruction
7134 ** will be converted into a Noop.
7135 */
7143 /* Initialize memory locations used by GROUP BY aggregate processing
7144 */
7159 /* Begin a loop that will extract all source rows in GROUP BY order.
7160 ** This might involve two separate loops with an OP_Sort in between, or
7161 ** it might be a single loop that uses an index to extract information
7162 ** in the right order to begin with.
7163 */
7168 );
7172 }
7176 /* The optimizer is able to deliver rows in group by order so
7177 ** we do not have to sort. The OP_OpenEphemeral table will be
7178 ** cancelled later because we still need to use the pKeyInfo
7179 */
7182 /* Rows are coming out in undetermined order. We have to push
7183 ** each row into a sorting index, terminate the first loop,
7184 ** then loop over the sorting index in order to get the output
7185 ** in sorted order
7186 */
7202 nCol++;
7203 j++;
7204 }
7205 }
7215 j++;
7216 }
7217 }
7231 }
7233 /* If the index or temporary table used by the GROUP BY sort
7234 ** will naturally deliver rows in the order required by the ORDER BY
7235 ** clause, cancel the ephemeral table open coded earlier.
7236 **
7237 ** This is an optimization - the correct answer should result regardless.
7238 ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER to
7239 ** disable this optimization for testing purposes. */
7242 ){
7245 }
7247 /* Evaluate the current GROUP BY terms and store in b0, b1, b2...
7248 ** (b0 is memory location iBMem+0, b1 is iBMem+1, and so forth)
7249 ** Then compare the current GROUP BY terms against the GROUP BY terms
7250 ** from the previous row currently stored in a0, a1, a2...
7251 */
7256 }
7263 }
7264 }
7270 /* Generate code that runs whenever the GROUP BY changes.
7271 ** Changes in the GROUP BY are detected by the previous code
7272 ** block. If there were no changes, this block is skipped.
7273 **
7274 ** This code copies current group by terms in b0,b1,b2,...
7275 ** over to a0,a1,a2. It then calls the output subroutine
7276 ** and resets the aggregate accumulator registers in preparation
7277 ** for the next GROUP BY batch.
7278 */
7287 /* Update the aggregate accumulators based on the content of
7288 ** the current row
7289 */
7295 /* End of the loop
7296 */
7304 }
7307 /* Output the final row of result
7308 */
7312 /* Jump over the subroutines
7313 */
7316 /* Generate a subroutine that outputs a single row of the result
7317 ** set. This subroutine first looks at the iUseFlag. If iUseFlag
7318 ** is less than or equal to zero, the subroutine is a no-op. If
7319 ** the processing calls for the query to abort, this subroutine
7320 ** increments the iAbortFlag memory location before returning in
7321 ** order to signal the caller to abort.
7322 */
7341 /* Generate a subroutine that will reset the group-by accumulator
7342 */
7352 }
7357 /* If isSimpleCount() returns a pointer to a Table structure, then
7358 ** the SQL statement is of the form:
7359 **
7360 ** SELECT count(*) FROM <tbl>
7361 **
7362 ** where the Table structure returned represents table <tbl>.
7363 **
7364 ** This statement is so common that it is optimized specially. The
7365 ** OP_Count instruction is executed either on the intkey table that
7366 ** contains the data for table <tbl> or on one of its indexes. It
7367 ** is better to execute the op on an index, as indexes are almost
7368 ** always spread across less pages than their corresponding tables.
7369 */
7380 /* Search for the index that has the lowest scan cost.
7381 **
7382 ** (2011-04-15) Do not do a full scan of an unordered index.
7383 **
7384 ** (2013-10-03) Do not count the entries in a partial index.
7385 **
7386 ** In practice the KeyInfo structure will not be used. It is only
7387 ** passed to keep OP_OpenRead happy.
7388 */
7396 ){
7398 }
7399 }
7400 }
7404 }
7406 /* Open a read-only cursor, execute the OP_Count, close the cursor. */
7410 }
7420 /* If there are accumulator registers but no min() or max() functions
7421 ** without FILTER clauses, allocate register regAcc. Register regAcc
7422 ** will contain 0 the first time the inner loop runs, and 1 thereafter.
7423 ** The code generated by updateAccumulator() uses this to ensure
7424 ** that the accumulator registers are (a) updated only once if
7425 ** there are no min() or max functions or (b) always updated for the
7426 ** first row visited by the aggregate, so that they are updated at
7427 ** least once even if the FILTER clause means the min() or max()
7428 ** function visits zero rows. */
7433 }
7436 }
7437 }
7441 }
7446 }
7448 /* This case runs if the aggregate has no GROUP BY clause. The
7449 ** processing is much simpler since there is only a single row
7450 ** of output.
7451 */
7455 /* If this query is a candidate for the min/max optimization, then
7456 ** minMaxFlag will have been previously set to either
7457 ** WHERE_ORDERBY_MIN or WHERE_ORDERBY_MAX and pMinMaxOrderBy will
7458 ** be an appropriate ORDER BY expression for the optimization.
7459 */
7468 }
7475 }
7480 }
7484 }
7490 }
7497 }
7499 /* If there is an ORDER BY clause, then we need to sort the results
7500 ** and send them to the callback one by one.
7501 */
7507 }
7509 /* Jump here to skip this query
7510 */
7513 /* The SELECT has been coded. If there is an error in the Parse structure,
7514 ** set the return code to 1. Otherwise 0. */
7517 /* Control jumps to here if an error is encountered above, or upon
7518 ** successful coding of the SELECT.
7519 */
7520 select_end:
7524 #ifdef SQLITE_DEBUG
7531 }
7537 }
7538 }
7539 #endif
7541 #if SELECTTRACE_ENABLED
7545 }
7546 #endif
7549 }