From 44d5be0e5308e951c0c5dc522b4bcacf2bcbc476 Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Sat, 4 Oct 2008 21:56:55 +0000 Subject: [PATCH] Implement SQL-standard WITH clauses, including WITH RECURSIVE. There are some unimplemented aspects: recursive queries must use UNION ALL (should allow UNION too), and we don't have SEARCH or CYCLE clauses. These might or might not get done for 8.4, but even without them it's a pretty useful feature. There are also a couple of small loose ends and definitional quibbles, which I'll send a memo about to pgsql-hackers shortly. But let's land the patch now so we can get on with other development. Yoshiyuki Asaba, with lots of help from Tatsuo Ishii and Tom Lane --- doc/src/sgml/errcodes.sgml | 8 +- doc/src/sgml/queries.sgml | 200 ++++++- doc/src/sgml/ref/select.sgml | 188 ++++++- doc/src/sgml/ref/select_into.sgml | 25 +- src/backend/catalog/dependency.c | 4 +- src/backend/commands/explain.c | 50 +- src/backend/executor/Makefile | 11 +- src/backend/executor/execAmi.c | 19 +- src/backend/executor/execProcnode.c | 54 +- src/backend/executor/nodeCtescan.c | 335 +++++++++++ src/backend/executor/nodeRecursiveunion.c | 225 ++++++++ src/backend/executor/nodeSubplan.c | 47 +- src/backend/executor/nodeWorktablescan.c | 194 +++++++ src/backend/nodes/copyfuncs.c | 123 +++- src/backend/nodes/equalfuncs.c | 46 +- src/backend/nodes/nodeFuncs.c | 351 +++++++++++- src/backend/nodes/outfuncs.c | 118 +++- src/backend/nodes/print.c | 18 +- src/backend/nodes/readfuncs.c | 40 +- src/backend/optimizer/path/allpaths.c | 120 +++- src/backend/optimizer/path/clausesel.c | 36 +- src/backend/optimizer/path/costsize.c | 118 +++- src/backend/optimizer/path/joinpath.c | 13 +- src/backend/optimizer/plan/createplan.c | 235 +++++++- src/backend/optimizer/plan/planner.c | 36 +- src/backend/optimizer/plan/setrefs.c | 32 +- src/backend/optimizer/plan/subselect.c | 168 +++++- src/backend/optimizer/prep/prepjointree.c | 22 +- src/backend/optimizer/prep/prepunion.c | 72 ++- src/backend/optimizer/util/clauses.c | 3 +- src/backend/optimizer/util/pathnode.c | 41 +- src/backend/optimizer/util/plancat.c | 24 +- src/backend/optimizer/util/relnode.c | 3 +- src/backend/parser/Makefile | 4 +- src/backend/parser/analyze.c | 107 +++- src/backend/parser/gram.y | 122 +++- src/backend/parser/keywords.c | 12 +- src/backend/parser/parse_agg.c | 42 +- src/backend/parser/parse_clause.c | 58 +- src/backend/parser/parse_cte.c | 899 ++++++++++++++++++++++++++++++ src/backend/parser/parse_relation.c | 159 +++++- src/backend/parser/parse_target.c | 58 +- src/backend/parser/parse_type.c | 3 +- src/backend/rewrite/rewriteDefine.c | 14 +- src/backend/rewrite/rewriteHandler.c | 57 +- src/backend/rewrite/rewriteManip.c | 28 +- src/backend/utils/adt/ruleutils.c | 108 +++- src/backend/utils/cache/plancache.c | 14 +- src/backend/utils/sort/tuplestore.c | 96 +++- src/bin/psql/tab-complete.c | 8 +- src/include/catalog/catversion.h | 4 +- src/include/executor/nodeCtescan.h | 25 + src/include/executor/nodeRecursiveunion.h | 25 + src/include/executor/nodeWorktablescan.h | 25 + src/include/nodes/execnodes.h | 59 +- src/include/nodes/nodeFuncs.h | 12 +- src/include/nodes/nodes.h | 10 +- src/include/nodes/parsenodes.h | 77 ++- src/include/nodes/plannodes.h | 38 +- src/include/nodes/primnodes.h | 9 +- src/include/nodes/relation.h | 18 +- src/include/optimizer/cost.h | 6 +- src/include/optimizer/pathnode.h | 4 +- src/include/optimizer/planmain.h | 4 +- src/include/optimizer/planner.h | 5 +- src/include/optimizer/subselect.h | 4 +- src/include/parser/parse_cte.h | 21 + src/include/parser/parse_node.h | 7 +- src/include/parser/parse_relation.h | 8 +- src/include/utils/errcodes.h | 3 +- src/include/utils/tuplestore.h | 4 +- src/interfaces/ecpg/preproc/preproc.y | 4 +- src/pl/plpgsql/src/plerrcodes.h | 6 +- src/test/regress/expected/with.out | 666 ++++++++++++++++++++++ src/test/regress/parallel_schedule | 4 +- src/test/regress/serial_schedule | 3 +- src/test/regress/sql/with.sql | 387 +++++++++++++ 77 files changed, 5893 insertions(+), 313 deletions(-) create mode 100644 src/backend/executor/nodeCtescan.c create mode 100644 src/backend/executor/nodeRecursiveunion.c create mode 100644 src/backend/executor/nodeWorktablescan.c create mode 100644 src/backend/parser/parse_cte.c create mode 100644 src/include/executor/nodeCtescan.h create mode 100644 src/include/executor/nodeRecursiveunion.h create mode 100644 src/include/executor/nodeWorktablescan.h create mode 100644 src/include/parser/parse_cte.h create mode 100644 src/test/regress/expected/with.out create mode 100644 src/test/regress/sql/with.sql diff --git a/doc/src/sgml/errcodes.sgml b/doc/src/sgml/errcodes.sgml index 474c0ca8da..574e7f5fba 100644 --- a/doc/src/sgml/errcodes.sgml +++ b/doc/src/sgml/errcodes.sgml @@ -1,4 +1,4 @@ - + <productname>PostgreSQL</productname> Error Codes @@ -991,6 +991,12 @@ +42P19 +INVALID RECURSION +invalid_recursion + + + 42830 INVALID FOREIGN KEY invalid_foreign_key diff --git a/doc/src/sgml/queries.sgml b/doc/src/sgml/queries.sgml index e3b6be4d97..b3d72ceb7f 100644 --- a/doc/src/sgml/queries.sgml +++ b/doc/src/sgml/queries.sgml @@ -1,4 +1,4 @@ - + Queries @@ -28,10 +28,11 @@ used to specify queries. The general syntax of the SELECT command is -SELECT select_list FROM table_expression sort_specification +WITH with_queries SELECT select_list FROM table_expression sort_specification The following sections describe the details of the select list, the - table expression, and the sort specification. + table expression, and the sort specification. WITH + queries are treated last since they are an advanced feature. @@ -107,7 +108,7 @@ SELECT random(); The <literal>FROM</literal> Clause - + The derives a table from one or more other tables given in a comma-separated @@ -211,7 +212,7 @@ FROM table_reference , table_r T1 { INNER | { LEFT | RIGHT | FULL } OUTER } JOIN T2 USING ( join column list ) T1 NATURAL { INNER | { LEFT | RIGHT | FULL } OUTER } JOIN T2 - + The words INNER and OUTER are optional in all forms. @@ -303,7 +304,7 @@ FROM table_reference , table_r - + RIGHT OUTER JOIN @@ -326,7 +327,7 @@ FROM table_reference , table_r - + FULL OUTER JOIN @@ -1042,7 +1043,7 @@ SELECT a AS value, b + c AS sum FROM ... If no output column name is specified using AS, the system assigns a default column name. For simple column references, - this is the name of the referenced column. For function + this is the name of the referenced column. For function calls, this is the name of the function. For complex expressions, the system will generate a generic name. @@ -1302,7 +1303,7 @@ SELECT a, max(b) FROM table1 GROUP BY a ORDER BY 1; SELECT a + b AS sum, c FROM table1 ORDER BY sum + c; -- wrong - This restriction is made to reduce ambiguity. There is still + This restriction is made to reduce ambiguity. There is still ambiguity if an ORDER BY item is a simple name that could match either an output column name or a column from the table expression. The output column is used in such cases. This would @@ -1455,4 +1456,185 @@ SELECT select_list FROM table_expression + + + <literal>WITH</literal> Queries + + + WITH + in SELECT + + + + common table expression + WITH + + + + WITH provides a way to write subqueries for use in a larger + SELECT query. The subqueries can be thought of as defining + temporary tables that exist just for this query. One use of this feature + is to break down complicated queries into simpler parts. An example is: + + +WITH regional_sales AS ( + SELECT region, SUM(amount) AS total_sales + FROM orders + GROUP BY region + ), top_regions AS ( + SELECT region + FROM regional_sales + WHERE total_sales > (SELECT SUM(total_sales)/10 FROM regional_sales) + ) +SELECT region, + product, + SUM(quantity) AS product_units, + SUM(amount) AS product_sales +FROM orders +WHERE region IN (SELECT region FROM top_regions) +GROUP BY region, product; + + + which displays per-product sales totals in only the top sales regions. + This example could have been written without WITH, + but we'd have needed two levels of nested sub-SELECTs. It's a bit + easier to follow this way. + + + + The optional RECURSIVE modifier changes WITH + from a mere syntactic convenience into a feature that accomplishes + things not otherwise possible in standard SQL. Using + RECURSIVE, a WITH query can refer to its own + output. A very simple example is this query to sum the integers from 1 + through 100: + + +WITH RECURSIVE t(n) AS ( + VALUES (1) + UNION ALL + SELECT n+1 FROM t WHERE n < 100 +) +SELECT sum(n) FROM t; + + + The general form of a recursive WITH query is always a + non-recursive term, then UNION ALL, then a + recursive term, where only the recursive term can contain + a reference to the query's own output. Such a query is executed as + follows: + + + + Recursive Query Evaluation + + + + Evaluate the non-recursive term. Include all its output rows in the + result of the recursive query, and also place them in a temporary + working table. + + + + + + So long as the working table is not empty, repeat these steps: + + + + + Evaluate the recursive term, substituting the current contents of + the working table for the recursive self-reference. Include all its + output rows in the result of the recursive query, and also place them + in a temporary intermediate table. + + + + + + Replace the contents of the working table with the contents of the + intermediate table, then empty the intermediate table. + + + + + + + + + Strictly speaking, this process is iteration not recursion, but + RECURSIVE is the terminology chosen by the SQL standards + committee. + + + + + In the example above, the working table has just a single row in each step, + and it takes on the values from 1 through 100 in successive steps. In + the 100th step, there is no output because of the WHERE + clause, and so the query terminates. + + + + Recursive queries are typically used to deal with hierarchical or + tree-structured data. A useful example is this query to find all the + direct and indirect sub-parts of a product, given only a table that + shows immediate inclusions: + + +WITH RECURSIVE included_parts(sub_part, part, quantity) AS ( + SELECT sub_part, part, quantity FROM parts WHERE part = 'our_product' + UNION ALL + SELECT p.sub_part, p.part, p.quantity + FROM included_parts pr, parts p + WHERE p.part = pr.sub_part + ) +SELECT sub_part, SUM(quantity) as total_quantity +FROM included_parts +GROUP BY sub_part + + + + + When working with recursive queries it is important to be sure that + the recursive part of the query will eventually return no tuples, + or else the query will loop indefinitely. A useful trick for + development purposes is to place a LIMIT in the parent + query. For example, this query would loop forever without the + LIMIT: + + +WITH RECURSIVE t(n) AS ( + SELECT 1 + UNION ALL + SELECT n+1 FROM t +) +SELECT n FROM t LIMIT 100; + + + This works because PostgreSQL's implementation + evaluates only as many rows of a WITH query as are actually + demanded by the parent query. Using this trick in production is not + recommended, because other systems might work differently. + + + + A useful property of WITH queries is that they are evaluated + only once per execution of the parent query, even if they are referred to + more than once by the parent query or sibling WITH queries. + Thus, expensive calculations that are needed in multiple places can be + placed within a WITH query to avoid redundant work. Another + possible application is to prevent unwanted multiple evaluations of + functions with side-effects. + However, the other side of this coin is that the optimizer is less able to + push restrictions from the parent query down into a WITH query + than an ordinary sub-query. The WITH query will generally be + evaluated as stated, without suppression of rows that the parent query + might discard afterwards. (But, as mentioned above, evaluation might stop + early if the reference(s) to the query demand only a limited number of + rows.) + + + + diff --git a/doc/src/sgml/ref/select.sgml b/doc/src/sgml/ref/select.sgml index d8ed7aef9c..e72d9c126f 100644 --- a/doc/src/sgml/ref/select.sgml +++ b/doc/src/sgml/ref/select.sgml @@ -1,5 +1,5 @@ @@ -20,6 +20,7 @@ PostgreSQL documentation +[ WITH [ RECURSIVE ] with_query [, ...] ] SELECT [ ALL | DISTINCT [ ON ( expression [, ...] ) ] ] * | expression [ [ AS ] output_name ] [, ...] [ FROM from_item [, ...] ] @@ -36,9 +37,14 @@ where from_item can be one of: [ ONLY ] table_name [ * ] [ [ AS ] alias [ ( column_alias [, ...] ) ] ] ( select ) [ AS ] alias [ ( column_alias [, ...] ) ] + with_query_name [ [ AS ] alias [ ( column_alias [, ...] ) ] ] function_name ( [ argument [, ...] ] ) [ AS ] alias [ ( column_alias [, ...] | column_definition [, ...] ) ] function_name ( [ argument [, ...] ] ) AS ( column_definition [, ...] ) from_item [ NATURAL ] join_type from_item [ ON join_condition | USING ( join_column [, ...] ) ] + +and with_query is: + + with_query_name [ ( column_name [, ...] ) ] AS ( select ) @@ -53,6 +59,17 @@ where from_item can be one of: + All queries in the WITH list are computed. + These effectively serve as temporary tables that can be referenced + in the FROM list. A WITH query + that is referenced more than once in FROM is + computed only once. + (See below.) + + + + + All elements in the FROM list are computed. (Each element in the FROM list is a real or virtual table.) If more than one element is specified in the @@ -163,6 +180,56 @@ where from_item can be one of: Parameters + + <literal>WITH</literal> Clause + + + The WITH clause allows you to specify one or more + subqueries that can be referenced by name in the primary query. + The subqueries effectively act as temporary tables or views + for the duration of the primary query. + + + + A name (without schema qualification) must be specified for each + WITH query. Optionally, a list of column names + can be specified; if this is omitted, + the column names are inferred from the subquery. + + + + If RECURSIVE is specified, it allows a + subquery to reference itself by name. Such a subquery must have + the form + +non_recursive_term UNION ALL recursive_term + + where the recursive self-reference must appear on the right-hand + side of UNION ALL. Only one recursive self-reference + is permitted per query. + + + + Another effect of RECURSIVE is that + WITH queries need not be ordered: a query + can reference another one that is later in the list. (However, + circular references, or mutual recursion, are not implemented.) + Without RECURSIVE, WITH queries + can only reference sibling WITH queries + that are earlier in the WITH list. + + + + A useful property of WITH queries is that they + are evaluated only once per execution of the primary query, + even if the primary query refers to them more than once. + + + + See for additional information. + + + <literal>FROM</literal> Clause @@ -197,7 +264,7 @@ where from_item can be one of: - + alias @@ -215,7 +282,7 @@ where from_item can be one of: - + select @@ -234,6 +301,21 @@ where from_item can be one of: + with_query_name + + + A WITH query is referenced by writing its name, + just as though the query's name were a table name. (In fact, + the WITH query hides any real table of the same name + for the purposes of the primary query. If necessary, you can + refer to a real table of the same name by schema-qualifying + the table's name.) + An alias can be provided in the same way as for a table. + + + + + function_name @@ -256,7 +338,7 @@ where from_item can be one of: - + join_type @@ -339,7 +421,7 @@ where from_item can be one of: - + ON join_condition @@ -352,7 +434,7 @@ where from_item can be one of: - + USING ( join_column [, ...] ) @@ -380,7 +462,7 @@ where from_item can be one of: - + <literal>WHERE</literal> Clause @@ -397,7 +479,7 @@ WHERE condition substituted for any variable references. - + <literal>GROUP BY</literal> Clause @@ -444,7 +526,7 @@ HAVING condition where condition is the same as specified for the WHERE clause. - + HAVING eliminates group rows that do not satisfy the condition. HAVING is different @@ -456,7 +538,7 @@ HAVING condition unambiguously reference a grouping column, unless the reference appears within an aggregate function. - + The presence of HAVING turns a query into a grouped query even if there is no GROUP BY clause. This is the @@ -518,7 +600,7 @@ HAVING condition the output column names will be the same as the table columns' names. - + <literal>UNION</literal> Clause @@ -537,7 +619,7 @@ HAVING condition the UNION, not to its right-hand input expression.) - + The UNION operator computes the set union of the rows returned by the involved SELECT @@ -548,7 +630,7 @@ HAVING condition number of columns, and corresponding columns must be of compatible data types. - + The result of UNION does not contain any duplicate rows unless the ALL option is specified. @@ -556,13 +638,13 @@ HAVING condition UNION ALL is usually significantly quicker than UNION; use ALL when you can.) - + Multiple UNION operators in the same SELECT statement are evaluated left to right, unless otherwise indicated by parentheses. - + Currently, FOR UPDATE and FOR SHARE cannot be specified either for a UNION result or for any input of a @@ -590,7 +672,7 @@ HAVING condition SELECT statements. A row is in the intersection of two result sets if it appears in both result sets. - + The result of INTERSECT does not contain any duplicate rows unless the ALL option is specified. @@ -598,7 +680,7 @@ HAVING condition left table and n duplicates in the right table will appear min(m,n) times in the result set. - + Multiple INTERSECT operators in the same SELECT statement are evaluated left to right, @@ -608,7 +690,7 @@ HAVING condition C will be read as A UNION (B INTERSECT C). - + Currently, FOR UPDATE and FOR SHARE cannot be specified either for an INTERSECT result or for any input of @@ -635,7 +717,7 @@ HAVING condition that are in the result of the left SELECT statement but not in the result of the right one. - + The result of EXCEPT does not contain any duplicate rows unless the ALL option is specified. @@ -643,14 +725,14 @@ HAVING condition left table and n duplicates in the right table will appear max(m-n,0) times in the result set. - + Multiple EXCEPT operators in the same SELECT statement are evaluated left to right, unless parentheses dictate otherwise. EXCEPT binds at the same level as UNION. - + Currently, FOR UPDATE and FOR SHARE cannot be specified either for an EXCEPT result or for any input of @@ -689,7 +771,7 @@ ORDER BY expression [ ASC | DESC | possible to assign a name to an output column using the AS clause. - + It is also possible to use arbitrary expressions in the ORDER BY clause, including columns that do not @@ -712,7 +794,7 @@ SELECT name FROM distributors ORDER BY code; make in the same situation. This inconsistency is made to be compatible with the SQL standard. - + Optionally one can add the key word ASC (ascending) or DESC (descending) after any expression in the @@ -789,7 +871,7 @@ SELECT DISTINCT ON (location) location, time, report desired precedence of rows within each DISTINCT ON group. - + <literal>LIMIT</literal> Clause @@ -1106,8 +1188,60 @@ SELECT * FROM distributors_2(111) AS (f1 int, f2 text); 111 | Walt Disney + + + This example shows how to use a simple WITH clause: + + +WITH t AS ( + SELECT random() as x FROM generate_series(1, 3) + ) +SELECT * FROM t +UNION ALL +SELECT * FROM t + + x +-------------------- + 0.534150459803641 + 0.520092216785997 + 0.0735620250925422 + 0.534150459803641 + 0.520092216785997 + 0.0735620250925422 + + + Notice that the WITH query was evaluated only once, + so that we got two sets of the same three random values. + + + + This example uses WITH RECURSIVE to find all + subordinates (direct or indirect) of the employee Mary, and their + level of indirectness, from a table that shows only direct + subordinates: + + +WITH RECURSIVE employee_recursive(distance, employee_name, manager_name) AS ( + SELECT 1, employee_name, manager_name + FROM employee + WHERE manager_name = 'Mary' + UNION ALL + SELECT er.distance + 1, e.employee_name, e.manager_name + FROM employee_recursive er, employee e + WHERE er.employee_name = e.manager_name + ) +SELECT distance, employee_name FROM employee_recursive; + + + Notice the typical form of recursive queries: + an initial condition, followed by UNION ALL, + followed by the recursive part of the query. Be sure that the + recursive part of the query will eventually return no tuples, or + else the query will loop indefinitely. (See + for more examples.) + - + Compatibility @@ -1116,7 +1250,7 @@ SELECT * FROM distributors_2(111) AS (f1 int, f2 text); with the SQL standard. But there are some extensions and some missing features. - + Omitted <literal>FROM</literal> Clauses @@ -1196,7 +1330,7 @@ SELECT distributors.* WHERE distributors.name = 'Westward'; SQL:1999 and later use a slightly different definition which is not - entirely upward compatible with SQL-92. + entirely upward compatible with SQL-92. In most cases, however, PostgreSQL will interpret an ORDER BY or GROUP BY expression the same way SQL:1999 does. diff --git a/doc/src/sgml/ref/select_into.sgml b/doc/src/sgml/ref/select_into.sgml index 915e859ea9..de9a86a878 100644 --- a/doc/src/sgml/ref/select_into.sgml +++ b/doc/src/sgml/ref/select_into.sgml @@ -1,5 +1,5 @@ @@ -20,17 +20,18 @@ PostgreSQL documentation -SELECT [ ALL | DISTINCT [ ON ( expression [, ...] ) ] ] - * | expression [ [ AS ] output_name ] [, ...] - INTO [ TEMPORARY | TEMP ] [ TABLE ] new_table - [ FROM from_item [, ...] ] - [ WHERE condition ] - [ GROUP BY expression [, ...] ] - [ HAVING condition [, ...] ] - [ { UNION | INTERSECT | EXCEPT } [ ALL ] select ] +[ WITH [ RECURSIVE ] with_query [, ...] ] +SELECT [ ALL | DISTINCT [ ON ( expression [, ...] ) ] ] + * | expression [ [ AS ] output_name ] [, ...] + INTO [ TEMPORARY | TEMP ] [ TABLE ] new_table + [ FROM from_item [, ...] ] + [ WHERE condition ] + [ GROUP BY expression [, ...] ] + [ HAVING condition [, ...] ] + [ { UNION | INTERSECT | EXCEPT } [ ALL ] select ] [ ORDER BY expression [ ASC | DESC | USING operator ] [ NULLS { FIRST | LAST } ] [, ...] ] - [ LIMIT { count | ALL } ] - [ OFFSET start ] + [ LIMIT { count | ALL } ] + [ OFFSET start ] [ FOR { UPDATE | SHARE } [ OF table_name [, ...] ] [ NOWAIT ] [...] ] @@ -46,7 +47,7 @@ SELECT [ ALL | DISTINCT [ ON ( expressionSELECT. - + Parameters diff --git a/src/backend/catalog/dependency.c b/src/backend/catalog/dependency.c index 3521f5ec95..b830d66842 100644 --- a/src/backend/catalog/dependency.c +++ b/src/backend/catalog/dependency.c @@ -8,7 +8,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/catalog/dependency.c,v 1.80 2008/08/25 22:42:32 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/catalog/dependency.c,v 1.81 2008/10/04 21:56:52 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -1557,7 +1557,7 @@ find_expr_references_walker(Node *node, * Add whole-relation refs for each plain relation mentioned in the * subquery's rtable, as well as datatype refs for any datatypes used * as a RECORD function's output. (Note: query_tree_walker takes care - * of recursing into RTE_FUNCTION and RTE_SUBQUERY RTEs, so no need to + * of recursing into RTE_FUNCTION RTEs, subqueries, etc, so no need to * do that here. But keep it from looking at join alias lists.) */ foreach(rtable, query->rtable) diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c index 81f1dd0c31..48334d1947 100644 --- a/src/backend/commands/explain.c +++ b/src/backend/commands/explain.c @@ -7,7 +7,7 @@ * Portions Copyright (c) 1994-5, Regents of the University of California * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/commands/explain.c,v 1.178 2008/08/19 18:30:04 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/commands/explain.c,v 1.179 2008/10/04 21:56:52 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -429,6 +429,9 @@ explain_outNode(StringInfo str, case T_Append: pname = "Append"; break; + case T_RecursiveUnion: + pname = "Recursive Union"; + break; case T_BitmapAnd: pname = "BitmapAnd"; break; @@ -537,6 +540,12 @@ explain_outNode(StringInfo str, case T_ValuesScan: pname = "Values Scan"; break; + case T_CteScan: + pname = "CTE Scan"; + break; + case T_WorkTableScan: + pname = "WorkTable Scan"; + break; case T_Material: pname = "Materialize"; break; @@ -721,6 +730,40 @@ explain_outNode(StringInfo str, quote_identifier(valsname)); } break; + case T_CteScan: + if (((Scan *) plan)->scanrelid > 0) + { + RangeTblEntry *rte = rt_fetch(((Scan *) plan)->scanrelid, + es->rtable); + + /* Assert it's on a non-self-reference CTE */ + Assert(rte->rtekind == RTE_CTE); + Assert(!rte->self_reference); + + appendStringInfo(str, " on %s", + quote_identifier(rte->ctename)); + if (strcmp(rte->eref->aliasname, rte->ctename) != 0) + appendStringInfo(str, " %s", + quote_identifier(rte->eref->aliasname)); + } + break; + case T_WorkTableScan: + if (((Scan *) plan)->scanrelid > 0) + { + RangeTblEntry *rte = rt_fetch(((Scan *) plan)->scanrelid, + es->rtable); + + /* Assert it's on a self-reference CTE */ + Assert(rte->rtekind == RTE_CTE); + Assert(rte->self_reference); + + appendStringInfo(str, " on %s", + quote_identifier(rte->ctename)); + if (strcmp(rte->eref->aliasname, rte->ctename) != 0) + appendStringInfo(str, " %s", + quote_identifier(rte->eref->aliasname)); + } + break; default: break; } @@ -787,6 +830,8 @@ explain_outNode(StringInfo str, case T_SeqScan: case T_FunctionScan: case T_ValuesScan: + case T_CteScan: + case T_WorkTableScan: show_scan_qual(plan->qual, "Filter", ((Scan *) plan)->scanrelid, @@ -1071,6 +1116,9 @@ show_plan_tlist(Plan *plan, /* The tlist of an Append isn't real helpful, so suppress it */ if (IsA(plan, Append)) return; + /* Likewise for RecursiveUnion */ + if (IsA(plan, RecursiveUnion)) + return; /* Set up deparsing context */ context = deparse_context_for_plan((Node *) outerPlan(plan), diff --git a/src/backend/executor/Makefile b/src/backend/executor/Makefile index 38364a9cd1..b4a0492751 100644 --- a/src/backend/executor/Makefile +++ b/src/backend/executor/Makefile @@ -4,7 +4,7 @@ # Makefile for executor # # IDENTIFICATION -# $PostgreSQL: pgsql/src/backend/executor/Makefile,v 1.27 2008/02/19 10:30:07 petere Exp $ +# $PostgreSQL: pgsql/src/backend/executor/Makefile,v 1.28 2008/10/04 21:56:52 tgl Exp $ # #------------------------------------------------------------------------- @@ -18,9 +18,10 @@ OBJS = execAmi.o execCurrent.o execGrouping.o execJunk.o execMain.o \ nodeBitmapAnd.o nodeBitmapOr.o \ nodeBitmapHeapscan.o nodeBitmapIndexscan.o nodeHash.o \ nodeHashjoin.o nodeIndexscan.o nodeMaterial.o nodeMergejoin.o \ - nodeNestloop.o nodeFunctionscan.o nodeResult.o nodeSeqscan.o \ - nodeSetOp.o nodeSort.o nodeUnique.o \ - nodeValuesscan.o nodeLimit.o nodeGroup.o \ - nodeSubplan.o nodeSubqueryscan.o nodeTidscan.o tstoreReceiver.o spi.o + nodeNestloop.o nodeFunctionscan.o nodeRecursiveunion.o nodeResult.o \ + nodeSeqscan.o nodeSetOp.o nodeSort.o nodeUnique.o \ + nodeValuesscan.o nodeCtescan.o nodeWorktablescan.o \ + nodeLimit.o nodeGroup.o nodeSubplan.o nodeSubqueryscan.o nodeTidscan.o \ + tstoreReceiver.o spi.o include $(top_srcdir)/src/backend/common.mk diff --git a/src/backend/executor/execAmi.c b/src/backend/executor/execAmi.c index afddf4d392..1de3f5a778 100644 --- a/src/backend/executor/execAmi.c +++ b/src/backend/executor/execAmi.c @@ -6,7 +6,7 @@ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/backend/executor/execAmi.c,v 1.98 2008/10/01 19:51:49 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/executor/execAmi.c,v 1.99 2008/10/04 21:56:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -30,6 +30,7 @@ #include "executor/nodeMaterial.h" #include "executor/nodeMergejoin.h" #include "executor/nodeNestloop.h" +#include "executor/nodeRecursiveunion.h" #include "executor/nodeResult.h" #include "executor/nodeSeqscan.h" #include "executor/nodeSetOp.h" @@ -39,6 +40,8 @@ #include "executor/nodeTidscan.h" #include "executor/nodeUnique.h" #include "executor/nodeValuesscan.h" +#include "executor/nodeCtescan.h" +#include "executor/nodeWorktablescan.h" /* @@ -121,6 +124,10 @@ ExecReScan(PlanState *node, ExprContext *exprCtxt) ExecReScanAppend((AppendState *) node, exprCtxt); break; + case T_RecursiveUnionState: + ExecRecursiveUnionReScan((RecursiveUnionState *) node, exprCtxt); + break; + case T_BitmapAndState: ExecReScanBitmapAnd((BitmapAndState *) node, exprCtxt); break; @@ -161,6 +168,14 @@ ExecReScan(PlanState *node, ExprContext *exprCtxt) ExecValuesReScan((ValuesScanState *) node, exprCtxt); break; + case T_CteScanState: + ExecCteScanReScan((CteScanState *) node, exprCtxt); + break; + + case T_WorkTableScanState: + ExecWorkTableScanReScan((WorkTableScanState *) node, exprCtxt); + break; + case T_NestLoopState: ExecReScanNestLoop((NestLoopState *) node, exprCtxt); break; @@ -396,6 +411,8 @@ ExecSupportsBackwardScan(Plan *node) case T_TidScan: case T_FunctionScan: case T_ValuesScan: + case T_CteScan: + case T_WorkTableScan: return true; case T_SubqueryScan: diff --git a/src/backend/executor/execProcnode.c b/src/backend/executor/execProcnode.c index 385c415974..e689ec00f8 100644 --- a/src/backend/executor/execProcnode.c +++ b/src/backend/executor/execProcnode.c @@ -12,7 +12,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/executor/execProcnode.c,v 1.62 2008/01/01 19:45:49 momjian Exp $ + * $PostgreSQL: pgsql/src/backend/executor/execProcnode.c,v 1.63 2008/10/04 21:56:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -94,6 +94,7 @@ #include "executor/nodeMaterial.h" #include "executor/nodeMergejoin.h" #include "executor/nodeNestloop.h" +#include "executor/nodeRecursiveunion.h" #include "executor/nodeResult.h" #include "executor/nodeSeqscan.h" #include "executor/nodeSetOp.h" @@ -103,8 +104,11 @@ #include "executor/nodeTidscan.h" #include "executor/nodeUnique.h" #include "executor/nodeValuesscan.h" +#include "executor/nodeCtescan.h" +#include "executor/nodeWorktablescan.h" #include "miscadmin.h" + /* ------------------------------------------------------------------------ * ExecInitNode * @@ -147,6 +151,11 @@ ExecInitNode(Plan *node, EState *estate, int eflags) estate, eflags); break; + case T_RecursiveUnion: + result = (PlanState *) ExecInitRecursiveUnion((RecursiveUnion *) node, + estate, eflags); + break; + case T_BitmapAnd: result = (PlanState *) ExecInitBitmapAnd((BitmapAnd *) node, estate, eflags); @@ -200,6 +209,16 @@ ExecInitNode(Plan *node, EState *estate, int eflags) estate, eflags); break; + case T_CteScan: + result = (PlanState *) ExecInitCteScan((CteScan *) node, + estate, eflags); + break; + + case T_WorkTableScan: + result = (PlanState *) ExecInitWorkTableScan((WorkTableScan *) node, + estate, eflags); + break; + /* * join nodes */ @@ -323,6 +342,10 @@ ExecProcNode(PlanState *node) result = ExecAppend((AppendState *) node); break; + case T_RecursiveUnionState: + result = ExecRecursiveUnion((RecursiveUnionState *) node); + break; + /* BitmapAndState does not yield tuples */ /* BitmapOrState does not yield tuples */ @@ -360,6 +383,14 @@ ExecProcNode(PlanState *node) result = ExecValuesScan((ValuesScanState *) node); break; + case T_CteScanState: + result = ExecCteScan((CteScanState *) node); + break; + + case T_WorkTableScanState: + result = ExecWorkTableScan((WorkTableScanState *) node); + break; + /* * join nodes */ @@ -501,6 +532,9 @@ ExecCountSlotsNode(Plan *node) case T_Append: return ExecCountSlotsAppend((Append *) node); + case T_RecursiveUnion: + return ExecCountSlotsRecursiveUnion((RecursiveUnion *) node); + case T_BitmapAnd: return ExecCountSlotsBitmapAnd((BitmapAnd *) node); @@ -534,6 +568,12 @@ ExecCountSlotsNode(Plan *node) case T_ValuesScan: return ExecCountSlotsValuesScan((ValuesScan *) node); + case T_CteScan: + return ExecCountSlotsCteScan((CteScan *) node); + + case T_WorkTableScan: + return ExecCountSlotsWorkTableScan((WorkTableScan *) node); + /* * join nodes */ @@ -620,6 +660,10 @@ ExecEndNode(PlanState *node) ExecEndAppend((AppendState *) node); break; + case T_RecursiveUnionState: + ExecEndRecursiveUnion((RecursiveUnionState *) node); + break; + case T_BitmapAndState: ExecEndBitmapAnd((BitmapAndState *) node); break; @@ -663,6 +707,14 @@ ExecEndNode(PlanState *node) ExecEndValuesScan((ValuesScanState *) node); break; + case T_CteScanState: + ExecEndCteScan((CteScanState *) node); + break; + + case T_WorkTableScanState: + ExecEndWorkTableScan((WorkTableScanState *) node); + break; + /* * join nodes */ diff --git a/src/backend/executor/nodeCtescan.c b/src/backend/executor/nodeCtescan.c new file mode 100644 index 0000000000..b4ae27df38 --- /dev/null +++ b/src/backend/executor/nodeCtescan.c @@ -0,0 +1,335 @@ +/*------------------------------------------------------------------------- + * + * nodeCtescan.c + * routines to handle CteScan nodes. + * + * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * + * IDENTIFICATION + * $PostgreSQL: pgsql/src/backend/executor/nodeCtescan.c,v 1.1 2008/10/04 21:56:53 tgl Exp $ + * + *------------------------------------------------------------------------- + */ + +#include "postgres.h" + +#include "executor/execdebug.h" +#include "executor/nodeCtescan.h" +#include "miscadmin.h" + +static TupleTableSlot *CteScanNext(CteScanState *node); + +/* ---------------------------------------------------------------- + * CteScanNext + * + * This is a workhorse for ExecCteScan + * ---------------------------------------------------------------- + */ +static TupleTableSlot * +CteScanNext(CteScanState *node) +{ + EState *estate; + ScanDirection dir; + bool forward; + Tuplestorestate *tuplestorestate; + bool eof_tuplestore; + TupleTableSlot *slot; + + /* + * get state info from node + */ + estate = node->ss.ps.state; + dir = estate->es_direction; + forward = ScanDirectionIsForward(dir); + tuplestorestate = node->leader->cte_table; + tuplestore_select_read_pointer(tuplestorestate, node->readptr); + slot = node->ss.ss_ScanTupleSlot; + + /* + * If we are not at the end of the tuplestore, or are going backwards, try + * to fetch a tuple from tuplestore. + */ + eof_tuplestore = tuplestore_ateof(tuplestorestate); + + if (!forward && eof_tuplestore) + { + if (!node->leader->eof_cte) + { + /* + * When reversing direction at tuplestore EOF, the first + * gettupleslot call will fetch the last-added tuple; but we want + * to return the one before that, if possible. So do an extra + * fetch. + */ + if (!tuplestore_advance(tuplestorestate, forward)) + return NULL; /* the tuplestore must be empty */ + } + eof_tuplestore = false; + } + + /* + * If we can fetch another tuple from the tuplestore, return it. + */ + if (!eof_tuplestore) + { + if (tuplestore_gettupleslot(tuplestorestate, forward, slot)) + return slot; + if (forward) + eof_tuplestore = true; + } + + /* + * If necessary, try to fetch another row from the CTE query. + * + * Note: the eof_cte state variable exists to short-circuit further calls + * of the CTE plan. It's not optional, unfortunately, because some plan + * node types are not robust about being called again when they've already + * returned NULL. + */ + if (eof_tuplestore && !node->leader->eof_cte) + { + TupleTableSlot *cteslot; + + /* + * We can only get here with forward==true, so no need to worry about + * which direction the subplan will go. + */ + cteslot = ExecProcNode(node->cteplanstate); + if (TupIsNull(cteslot)) + { + node->leader->eof_cte = true; + return NULL; + } + + /* + * Append a copy of the returned tuple to tuplestore. NOTE: because + * our read pointer is certainly in EOF state, its read position will + * move forward over the added tuple. This is what we want. Also, + * any other readers will *not* move past the new tuple, which is + * what they want. + */ + tuplestore_puttupleslot(tuplestorestate, cteslot); + + /* + * We MUST copy the CTE query's output tuple into our own slot. + * This is because other CteScan nodes might advance the CTE query + * before we are called again, and our output tuple must stay + * stable over that. + */ + return ExecCopySlot(slot, cteslot); + } + + /* + * Nothing left ... + */ + return ExecClearTuple(slot); +} + +/* ---------------------------------------------------------------- + * ExecCteScan(node) + * + * Scans the CTE sequentially and returns the next qualifying tuple. + * It calls the ExecScan() routine and passes it the access method + * which retrieves tuples sequentially. + * ---------------------------------------------------------------- + */ +TupleTableSlot * +ExecCteScan(CteScanState *node) +{ + /* + * use CteScanNext as access method + */ + return ExecScan(&node->ss, (ExecScanAccessMtd) CteScanNext); +} + + +/* ---------------------------------------------------------------- + * ExecInitCteScan + * ---------------------------------------------------------------- + */ +CteScanState * +ExecInitCteScan(CteScan *node, EState *estate, int eflags) +{ + CteScanState *scanstate; + ParamExecData *prmdata; + + /* check for unsupported flags */ + Assert(!(eflags & EXEC_FLAG_MARK)); + + /* + * For the moment we have to force the tuplestore to allow REWIND, because + * we might be asked to rescan the CTE even though upper levels didn't + * tell us to be prepared to do it efficiently. Annoying, since this + * prevents truncation of the tuplestore. XXX FIXME + */ + eflags |= EXEC_FLAG_REWIND; + + /* + * CteScan should not have any children. + */ + Assert(outerPlan(node) == NULL); + Assert(innerPlan(node) == NULL); + + /* + * create new CteScanState for node + */ + scanstate = makeNode(CteScanState); + scanstate->ss.ps.plan = (Plan *) node; + scanstate->ss.ps.state = estate; + scanstate->eflags = eflags; + scanstate->cte_table = NULL; + scanstate->eof_cte = false; + + /* + * Find the already-initialized plan for the CTE query. + */ + scanstate->cteplanstate = (PlanState *) list_nth(estate->es_subplanstates, + node->ctePlanId - 1); + + /* + * The Param slot associated with the CTE query is used to hold a + * pointer to the CteState of the first CteScan node that initializes + * for this CTE. This node will be the one that holds the shared + * state for all the CTEs. + */ + prmdata = &(estate->es_param_exec_vals[node->cteParam]); + Assert(prmdata->execPlan == NULL); + Assert(!prmdata->isnull); + scanstate->leader = (CteScanState *) DatumGetPointer(prmdata->value); + if (scanstate->leader == NULL) + { + /* I am the leader */ + prmdata->value = PointerGetDatum(scanstate); + scanstate->leader = scanstate; + scanstate->cte_table = tuplestore_begin_heap(true, false, work_mem); + tuplestore_set_eflags(scanstate->cte_table, scanstate->eflags); + scanstate->readptr = 0; + } + else + { + /* Not the leader */ + Assert(IsA(scanstate->leader, CteScanState)); + scanstate->readptr = + tuplestore_alloc_read_pointer(scanstate->leader->cte_table, + scanstate->eflags); + } + + /* + * Miscellaneous initialization + * + * create expression context for node + */ + ExecAssignExprContext(estate, &scanstate->ss.ps); + + /* + * initialize child expressions + */ + scanstate->ss.ps.targetlist = (List *) + ExecInitExpr((Expr *) node->scan.plan.targetlist, + (PlanState *) scanstate); + scanstate->ss.ps.qual = (List *) + ExecInitExpr((Expr *) node->scan.plan.qual, + (PlanState *) scanstate); + +#define CTESCAN_NSLOTS 2 + + /* + * tuple table initialization + */ + ExecInitResultTupleSlot(estate, &scanstate->ss.ps); + ExecInitScanTupleSlot(estate, &scanstate->ss); + + /* + * The scan tuple type (ie, the rowtype we expect to find in the work + * table) is the same as the result rowtype of the CTE query. + */ + ExecAssignScanType(&scanstate->ss, + ExecGetResultType(scanstate->cteplanstate)); + + /* + * Initialize result tuple type and projection info. + */ + ExecAssignResultTypeFromTL(&scanstate->ss.ps); + ExecAssignScanProjectionInfo(&scanstate->ss); + + scanstate->ss.ps.ps_TupFromTlist = false; + + return scanstate; +} + +int +ExecCountSlotsCteScan(CteScan *node) +{ + return ExecCountSlotsNode(outerPlan(node)) + + ExecCountSlotsNode(innerPlan(node)) + + CTESCAN_NSLOTS; +} + +/* ---------------------------------------------------------------- + * ExecEndCteScan + * + * frees any storage allocated through C routines. + * ---------------------------------------------------------------- + */ +void +ExecEndCteScan(CteScanState *node) +{ + /* + * Free exprcontext + */ + ExecFreeExprContext(&node->ss.ps); + + /* + * clean out the tuple table + */ + ExecClearTuple(node->ss.ps.ps_ResultTupleSlot); + ExecClearTuple(node->ss.ss_ScanTupleSlot); + + /* + * If I am the leader, free the tuplestore. + */ + if (node->leader == node) + tuplestore_end(node->cte_table); +} + +/* ---------------------------------------------------------------- + * ExecCteScanReScan + * + * Rescans the relation. + * ---------------------------------------------------------------- + */ +void +ExecCteScanReScan(CteScanState *node, ExprContext *exprCtxt) +{ + Tuplestorestate *tuplestorestate; + + tuplestorestate = node->leader->cte_table; + + ExecClearTuple(node->ss.ps.ps_ResultTupleSlot); + + if (node->leader == node) + { + /* + * The leader is responsible for clearing the tuplestore if a new + * scan of the underlying CTE is required. + */ + if (node->cteplanstate->chgParam != NULL) + { + tuplestore_clear(tuplestorestate); + node->eof_cte = false; + } + else + { + tuplestore_select_read_pointer(tuplestorestate, node->readptr); + tuplestore_rescan(tuplestorestate); + } + } + else + { + /* Not leader, so just rewind my own pointer */ + tuplestore_select_read_pointer(tuplestorestate, node->readptr); + tuplestore_rescan(tuplestorestate); + } +} diff --git a/src/backend/executor/nodeRecursiveunion.c b/src/backend/executor/nodeRecursiveunion.c new file mode 100644 index 0000000000..7136a62301 --- /dev/null +++ b/src/backend/executor/nodeRecursiveunion.c @@ -0,0 +1,225 @@ +/*------------------------------------------------------------------------- + * + * nodeRecursiveunion.c + * routines to handle RecursiveUnion nodes. + * + * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * + * IDENTIFICATION + * $PostgreSQL: pgsql/src/backend/executor/nodeRecursiveunion.c,v 1.1 2008/10/04 21:56:53 tgl Exp $ + * + *------------------------------------------------------------------------- + */ +#include "postgres.h" + +#include "executor/execdebug.h" +#include "executor/nodeRecursiveunion.h" +#include "miscadmin.h" + + +/* ---------------------------------------------------------------- + * ExecRecursiveUnion(node) + * + * Scans the recursive query sequentially and returns the next + * qualifying tuple. + * + * 1. evaluate non recursive term and assign the result to RT + * + * 2. execute recursive terms + * + * 2.1 WT := RT + * 2.2 while WT is not empty repeat 2.3 to 2.6. if WT is empty returns RT + * 2.3 replace the name of recursive term with WT + * 2.4 evaluate the recursive term and store into WT + * 2.5 append WT to RT + * 2.6 go back to 2.2 + * ---------------------------------------------------------------- + */ +TupleTableSlot * +ExecRecursiveUnion(RecursiveUnionState *node) +{ + PlanState *outerPlan = outerPlanState(node); + PlanState *innerPlan = innerPlanState(node); + RecursiveUnion *plan = (RecursiveUnion *) node->ps.plan; + TupleTableSlot *slot; + + /* 1. Evaluate non-recursive term */ + if (!node->recursing) + { + slot = ExecProcNode(outerPlan); + if (!TupIsNull(slot)) + { + tuplestore_puttupleslot(node->working_table, slot); + return slot; + } + node->recursing = true; + } + +retry: + /* 2. Execute recursive term */ + slot = ExecProcNode(innerPlan); + if (TupIsNull(slot)) + { + if (node->intermediate_empty) + return NULL; + + /* done with old working table ... */ + tuplestore_end(node->working_table); + + /* intermediate table becomes working table */ + node->working_table = node->intermediate_table; + + /* create new empty intermediate table */ + node->intermediate_table = tuplestore_begin_heap(false, false, work_mem); + node->intermediate_empty = true; + + /* and reset the inner plan */ + innerPlan->chgParam = bms_add_member(innerPlan->chgParam, + plan->wtParam); + goto retry; + } + else + { + node->intermediate_empty = false; + tuplestore_puttupleslot(node->intermediate_table, slot); + } + + return slot; +} + +/* ---------------------------------------------------------------- + * ExecInitRecursiveUnionScan + * ---------------------------------------------------------------- + */ +RecursiveUnionState * +ExecInitRecursiveUnion(RecursiveUnion *node, EState *estate, int eflags) +{ + RecursiveUnionState *rustate; + ParamExecData *prmdata; + + /* check for unsupported flags */ + Assert(!(eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK))); + + /* + * create state structure + */ + rustate = makeNode(RecursiveUnionState); + rustate->ps.plan = (Plan *) node; + rustate->ps.state = estate; + + /* initialize processing state */ + rustate->recursing = false; + rustate->intermediate_empty = true; + rustate->working_table = tuplestore_begin_heap(false, false, work_mem); + rustate->intermediate_table = tuplestore_begin_heap(false, false, work_mem); + + /* + * Make the state structure available to descendant WorkTableScan nodes + * via the Param slot reserved for it. + */ + prmdata = &(estate->es_param_exec_vals[node->wtParam]); + Assert(prmdata->execPlan == NULL); + prmdata->value = PointerGetDatum(rustate); + prmdata->isnull = false; + + /* + * Miscellaneous initialization + * + * RecursiveUnion plans don't have expression contexts because they never + * call ExecQual or ExecProject. + */ + Assert(node->plan.qual == NIL); + +#define RECURSIVEUNION_NSLOTS 1 + + /* + * RecursiveUnion nodes still have Result slots, which hold pointers to + * tuples, so we have to initialize them. + */ + ExecInitResultTupleSlot(estate, &rustate->ps); + + /* + * Initialize result tuple type and projection info. (Note: we have + * to set up the result type before initializing child nodes, because + * nodeWorktablescan.c expects it to be valid.) + */ + ExecAssignResultTypeFromTL(&rustate->ps); + rustate->ps.ps_ProjInfo = NULL; + + /* + * initialize child nodes + */ + outerPlanState(rustate) = ExecInitNode(outerPlan(node), estate, eflags); + innerPlanState(rustate) = ExecInitNode(innerPlan(node), estate, eflags); + + return rustate; +} + +int +ExecCountSlotsRecursiveUnion(RecursiveUnion *node) +{ + return ExecCountSlotsNode(outerPlan(node)) + + ExecCountSlotsNode(innerPlan(node)) + + RECURSIVEUNION_NSLOTS; +} + +/* ---------------------------------------------------------------- + * ExecEndRecursiveUnionScan + * + * frees any storage allocated through C routines. + * ---------------------------------------------------------------- + */ +void +ExecEndRecursiveUnion(RecursiveUnionState *node) +{ + /* Release tuplestores */ + tuplestore_end(node->working_table); + tuplestore_end(node->intermediate_table); + + /* + * clean out the upper tuple table + */ + ExecClearTuple(node->ps.ps_ResultTupleSlot); + + /* + * close down subplans + */ + ExecEndNode(outerPlanState(node)); + ExecEndNode(innerPlanState(node)); +} + +/* ---------------------------------------------------------------- + * ExecRecursiveUnionReScan + * + * Rescans the relation. + * ---------------------------------------------------------------- + */ +void +ExecRecursiveUnionReScan(RecursiveUnionState *node, ExprContext *exprCtxt) +{ + PlanState *outerPlan = outerPlanState(node); + PlanState *innerPlan = innerPlanState(node); + RecursiveUnion *plan = (RecursiveUnion *) node->ps.plan; + + /* + * Set recursive term's chgParam to tell it that we'll modify the + * working table and therefore it has to rescan. + */ + innerPlan->chgParam = bms_add_member(innerPlan->chgParam, plan->wtParam); + + /* + * if chgParam of subnode is not null then plan will be re-scanned by + * first ExecProcNode. Because of above, we only have to do this to + * the non-recursive term. + */ + if (outerPlan->chgParam == NULL) + ExecReScan(outerPlan, exprCtxt); + + /* reset processing state */ + node->recursing = false; + node->intermediate_empty = true; + tuplestore_clear(node->working_table); + tuplestore_clear(node->intermediate_table); +} diff --git a/src/backend/executor/nodeSubplan.c b/src/backend/executor/nodeSubplan.c index 3ebb045f92..338d94e760 100644 --- a/src/backend/executor/nodeSubplan.c +++ b/src/backend/executor/nodeSubplan.c @@ -7,7 +7,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/executor/nodeSubplan.c,v 1.94 2008/08/22 00:16:03 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/executor/nodeSubplan.c,v 1.95 2008/10/04 21:56:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -66,9 +66,13 @@ ExecSubPlan(SubPlanState *node, if (isDone) *isDone = ExprSingleResult; + /* Sanity checks */ + if (subplan->subLinkType == CTE_SUBLINK) + elog(ERROR, "CTE subplans should not be executed via ExecSubPlan"); if (subplan->setParam != NIL) elog(ERROR, "cannot set parent params from subquery"); + /* Select appropriate evaluation strategy */ if (subplan->useHashTable) return ExecHashSubPlan(node, econtext, isNull); else @@ -688,11 +692,14 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent) * If this plan is un-correlated or undirect correlated one and want to * set params for parent plan then mark parameters as needing evaluation. * + * A CTE subplan's output parameter is never to be evaluated in the normal + * way, so skip this in that case. + * * Note that in the case of un-correlated subqueries we don't care about * setting parent->chgParam here: indices take care about it, for others - * it doesn't matter... */ - if (subplan->setParam != NIL) + if (subplan->setParam != NIL && subplan->subLinkType != CTE_SUBLINK) { ListCell *lst; @@ -907,22 +914,21 @@ ExecSetParamPlan(SubPlanState *node, ExprContext *econtext) bool found = false; ArrayBuildState *astate = NULL; - /* - * Must switch to per-query memory context. - */ - oldcontext = MemoryContextSwitchTo(econtext->ecxt_per_query_memory); - if (subLinkType == ANY_SUBLINK || subLinkType == ALL_SUBLINK) elog(ERROR, "ANY/ALL subselect unsupported as initplan"); + if (subLinkType == CTE_SUBLINK) + elog(ERROR, "CTE subplans should not be executed via ExecSetParamPlan"); /* - * By definition, an initplan has no parameters from our query level, but - * it could have some from an outer level. Rescan it if needed. + * Must switch to per-query memory context. */ - if (planstate->chgParam != NULL) - ExecReScan(planstate, NULL); + oldcontext = MemoryContextSwitchTo(econtext->ecxt_per_query_memory); + /* + * Run the plan. (If it needs to be rescanned, the first ExecProcNode + * call will take care of that.) + */ for (slot = ExecProcNode(planstate); !TupIsNull(slot); slot = ExecProcNode(planstate)) @@ -932,7 +938,7 @@ ExecSetParamPlan(SubPlanState *node, ExprContext *econtext) if (subLinkType == EXISTS_SUBLINK) { - /* There can be only one param... */ + /* There can be only one setParam... */ int paramid = linitial_int(subplan->setParam); ParamExecData *prm = &(econtext->ecxt_param_exec_vals[paramid]); @@ -994,7 +1000,7 @@ ExecSetParamPlan(SubPlanState *node, ExprContext *econtext) if (subLinkType == ARRAY_SUBLINK) { - /* There can be only one param... */ + /* There can be only one setParam... */ int paramid = linitial_int(subplan->setParam); ParamExecData *prm = &(econtext->ecxt_param_exec_vals[paramid]); @@ -1014,7 +1020,7 @@ ExecSetParamPlan(SubPlanState *node, ExprContext *econtext) { if (subLinkType == EXISTS_SUBLINK) { - /* There can be only one param... */ + /* There can be only one setParam... */ int paramid = linitial_int(subplan->setParam); ParamExecData *prm = &(econtext->ecxt_param_exec_vals[paramid]); @@ -1059,18 +1065,25 @@ ExecReScanSetParamPlan(SubPlanState *node, PlanState *parent) elog(ERROR, "extParam set of initplan is empty"); /* - * Don't actually re-scan: ExecSetParamPlan does it if needed. + * Don't actually re-scan: it'll happen inside ExecSetParamPlan if needed. */ /* - * Mark this subplan's output parameters as needing recalculation + * Mark this subplan's output parameters as needing recalculation. + * + * CTE subplans are never executed via parameter recalculation; instead + * they get run when called by nodeCtescan.c. So don't mark the output + * parameter of a CTE subplan as dirty, but do set the chgParam bit + * for it so that dependent plan nodes will get told to rescan. */ foreach(l, subplan->setParam) { int paramid = lfirst_int(l); ParamExecData *prm = &(estate->es_param_exec_vals[paramid]); - prm->execPlan = node; + if (subplan->subLinkType != CTE_SUBLINK) + prm->execPlan = node; + parent->chgParam = bms_add_member(parent->chgParam, paramid); } } diff --git a/src/backend/executor/nodeWorktablescan.c b/src/backend/executor/nodeWorktablescan.c new file mode 100644 index 0000000000..2f09c5e22d --- /dev/null +++ b/src/backend/executor/nodeWorktablescan.c @@ -0,0 +1,194 @@ +/*------------------------------------------------------------------------- + * + * nodeWorktablescan.c + * routines to handle WorkTableScan nodes. + * + * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * + * IDENTIFICATION + * $PostgreSQL: pgsql/src/backend/executor/nodeWorktablescan.c,v 1.1 2008/10/04 21:56:53 tgl Exp $ + * + *------------------------------------------------------------------------- + */ + +#include "postgres.h" + +#include "executor/execdebug.h" +#include "executor/nodeWorktablescan.h" + +static TupleTableSlot *WorkTableScanNext(WorkTableScanState *node); + +/* ---------------------------------------------------------------- + * WorkTableScanNext + * + * This is a workhorse for ExecWorkTableScan + * ---------------------------------------------------------------- + */ +static TupleTableSlot * +WorkTableScanNext(WorkTableScanState *node) +{ + TupleTableSlot *slot; + EState *estate; + ScanDirection direction; + Tuplestorestate *tuplestorestate; + + /* + * get information from the estate and scan state + */ + estate = node->ss.ps.state; + direction = estate->es_direction; + + tuplestorestate = node->rustate->working_table; + + /* + * Get the next tuple from tuplestore. Return NULL if no more tuples. + */ + slot = node->ss.ss_ScanTupleSlot; + (void) tuplestore_gettupleslot(tuplestorestate, + ScanDirectionIsForward(direction), + slot); + return slot; +} + +/* ---------------------------------------------------------------- + * ExecWorkTableScan(node) + * + * Scans the worktable sequentially and returns the next qualifying tuple. + * It calls the ExecScan() routine and passes it the access method + * which retrieves tuples sequentially. + * ---------------------------------------------------------------- + */ +TupleTableSlot * +ExecWorkTableScan(WorkTableScanState *node) +{ + /* + * use WorkTableScanNext as access method + */ + return ExecScan(&node->ss, (ExecScanAccessMtd) WorkTableScanNext); +} + + +/* ---------------------------------------------------------------- + * ExecInitWorkTableScan + * ---------------------------------------------------------------- + */ +WorkTableScanState * +ExecInitWorkTableScan(WorkTableScan *node, EState *estate, int eflags) +{ + WorkTableScanState *scanstate; + ParamExecData *prmdata; + + /* check for unsupported flags */ + Assert(!(eflags & EXEC_FLAG_MARK)); + + /* + * WorkTableScan should not have any children. + */ + Assert(outerPlan(node) == NULL); + Assert(innerPlan(node) == NULL); + + /* + * create new WorkTableScanState for node + */ + scanstate = makeNode(WorkTableScanState); + scanstate->ss.ps.plan = (Plan *) node; + scanstate->ss.ps.state = estate; + + /* + * Find the ancestor RecursiveUnion's state + * via the Param slot reserved for it. + */ + prmdata = &(estate->es_param_exec_vals[node->wtParam]); + Assert(prmdata->execPlan == NULL); + Assert(!prmdata->isnull); + scanstate->rustate = (RecursiveUnionState *) DatumGetPointer(prmdata->value); + Assert(scanstate->rustate && IsA(scanstate->rustate, RecursiveUnionState)); + + /* + * Miscellaneous initialization + * + * create expression context for node + */ + ExecAssignExprContext(estate, &scanstate->ss.ps); + + /* + * initialize child expressions + */ + scanstate->ss.ps.targetlist = (List *) + ExecInitExpr((Expr *) node->scan.plan.targetlist, + (PlanState *) scanstate); + scanstate->ss.ps.qual = (List *) + ExecInitExpr((Expr *) node->scan.plan.qual, + (PlanState *) scanstate); + +#define WORKTABLESCAN_NSLOTS 2 + + /* + * tuple table initialization + */ + ExecInitResultTupleSlot(estate, &scanstate->ss.ps); + ExecInitScanTupleSlot(estate, &scanstate->ss); + + /* + * The scan tuple type (ie, the rowtype we expect to find in the work + * table) is the same as the result rowtype of the ancestor RecursiveUnion + * node. Note this depends on the assumption that RecursiveUnion doesn't + * allow projection. + */ + ExecAssignScanType(&scanstate->ss, + ExecGetResultType(&scanstate->rustate->ps)); + + /* + * Initialize result tuple type and projection info. + */ + ExecAssignResultTypeFromTL(&scanstate->ss.ps); + ExecAssignScanProjectionInfo(&scanstate->ss); + + scanstate->ss.ps.ps_TupFromTlist = false; + + return scanstate; +} + +int +ExecCountSlotsWorkTableScan(WorkTableScan *node) +{ + return ExecCountSlotsNode(outerPlan(node)) + + ExecCountSlotsNode(innerPlan(node)) + + WORKTABLESCAN_NSLOTS; +} + +/* ---------------------------------------------------------------- + * ExecEndWorkTableScan + * + * frees any storage allocated through C routines. + * ---------------------------------------------------------------- + */ +void +ExecEndWorkTableScan(WorkTableScanState *node) +{ + /* + * Free exprcontext + */ + ExecFreeExprContext(&node->ss.ps); + + /* + * clean out the tuple table + */ + ExecClearTuple(node->ss.ps.ps_ResultTupleSlot); + ExecClearTuple(node->ss.ss_ScanTupleSlot); +} + +/* ---------------------------------------------------------------- + * ExecWorkTableScanReScan + * + * Rescans the relation. + * ---------------------------------------------------------------- + */ +void +ExecWorkTableScanReScan(WorkTableScanState *node, ExprContext *exprCtxt) +{ + ExecClearTuple(node->ss.ps.ps_ResultTupleSlot); + tuplestore_rescan(node->rustate->working_table); +} diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c index 9cfa1700f4..57ef558c40 100644 --- a/src/backend/nodes/copyfuncs.c +++ b/src/backend/nodes/copyfuncs.c @@ -15,7 +15,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/nodes/copyfuncs.c,v 1.405 2008/09/09 18:58:08 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/nodes/copyfuncs.c,v 1.406 2008/10/04 21:56:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -177,6 +177,27 @@ _copyAppend(Append *from) } /* + * _copyRecursiveUnion + */ +static RecursiveUnion * +_copyRecursiveUnion(RecursiveUnion *from) +{ + RecursiveUnion *newnode = makeNode(RecursiveUnion); + + /* + * copy node superclass fields + */ + CopyPlanFields((Plan *) from, (Plan *) newnode); + + /* + * copy remainder of node + */ + COPY_SCALAR_FIELD(wtParam); + + return newnode; +} + +/* * _copyBitmapAnd */ static BitmapAnd * @@ -422,6 +443,49 @@ _copyValuesScan(ValuesScan *from) } /* + * _copyCteScan + */ +static CteScan * +_copyCteScan(CteScan *from) +{ + CteScan *newnode = makeNode(CteScan); + + /* + * copy node superclass fields + */ + CopyScanFields((Scan *) from, (Scan *) newnode); + + /* + * copy remainder of node + */ + COPY_SCALAR_FIELD(ctePlanId); + COPY_SCALAR_FIELD(cteParam); + + return newnode; +} + +/* + * _copyWorkTableScan + */ +static WorkTableScan * +_copyWorkTableScan(WorkTableScan *from) +{ + WorkTableScan *newnode = makeNode(WorkTableScan); + + /* + * copy node superclass fields + */ + CopyScanFields((Scan *) from, (Scan *) newnode); + + /* + * copy remainder of node + */ + COPY_SCALAR_FIELD(wtParam); + + return newnode; +} + +/* * CopyJoinFields * * This function copies the fields of the Join node. It is used by @@ -1572,12 +1636,17 @@ _copyRangeTblEntry(RangeTblEntry *from) COPY_SCALAR_FIELD(rtekind); COPY_SCALAR_FIELD(relid); COPY_NODE_FIELD(subquery); + COPY_SCALAR_FIELD(jointype); + COPY_NODE_FIELD(joinaliasvars); COPY_NODE_FIELD(funcexpr); COPY_NODE_FIELD(funccoltypes); COPY_NODE_FIELD(funccoltypmods); COPY_NODE_FIELD(values_lists); - COPY_SCALAR_FIELD(jointype); - COPY_NODE_FIELD(joinaliasvars); + COPY_STRING_FIELD(ctename); + COPY_SCALAR_FIELD(ctelevelsup); + COPY_SCALAR_FIELD(self_reference); + COPY_NODE_FIELD(ctecoltypes); + COPY_NODE_FIELD(ctecoltypmods); COPY_NODE_FIELD(alias); COPY_NODE_FIELD(eref); COPY_SCALAR_FIELD(inh); @@ -1632,6 +1701,36 @@ _copyRowMarkClause(RowMarkClause *from) return newnode; } +static WithClause * +_copyWithClause(WithClause *from) +{ + WithClause *newnode = makeNode(WithClause); + + COPY_NODE_FIELD(ctes); + COPY_SCALAR_FIELD(recursive); + COPY_LOCATION_FIELD(location); + + return newnode; +} + +static CommonTableExpr * +_copyCommonTableExpr(CommonTableExpr *from) +{ + CommonTableExpr *newnode = makeNode(CommonTableExpr); + + COPY_STRING_FIELD(ctename); + COPY_NODE_FIELD(aliascolnames); + COPY_NODE_FIELD(ctequery); + COPY_LOCATION_FIELD(location); + COPY_SCALAR_FIELD(cterecursive); + COPY_SCALAR_FIELD(cterefcount); + COPY_NODE_FIELD(ctecolnames); + COPY_NODE_FIELD(ctecoltypes); + COPY_NODE_FIELD(ctecoltypmods); + + return newnode; +} + static A_Expr * _copyAExpr(A_Expr *from) { @@ -1931,6 +2030,8 @@ _copyQuery(Query *from) COPY_SCALAR_FIELD(hasAggs); COPY_SCALAR_FIELD(hasSubLinks); COPY_SCALAR_FIELD(hasDistinctOn); + COPY_SCALAR_FIELD(hasRecursive); + COPY_NODE_FIELD(cteList); COPY_NODE_FIELD(rtable); COPY_NODE_FIELD(jointree); COPY_NODE_FIELD(targetList); @@ -1999,6 +2100,7 @@ _copySelectStmt(SelectStmt *from) COPY_NODE_FIELD(whereClause); COPY_NODE_FIELD(groupClause); COPY_NODE_FIELD(havingClause); + COPY_NODE_FIELD(withClause); COPY_NODE_FIELD(valuesLists); COPY_NODE_FIELD(sortClause); COPY_NODE_FIELD(limitOffset); @@ -3104,6 +3206,9 @@ copyObject(void *from) case T_Append: retval = _copyAppend(from); break; + case T_RecursiveUnion: + retval = _copyRecursiveUnion(from); + break; case T_BitmapAnd: retval = _copyBitmapAnd(from); break; @@ -3137,6 +3242,12 @@ copyObject(void *from) case T_ValuesScan: retval = _copyValuesScan(from); break; + case T_CteScan: + retval = _copyCteScan(from); + break; + case T_WorkTableScan: + retval = _copyWorkTableScan(from); + break; case T_Join: retval = _copyJoin(from); break; @@ -3672,6 +3783,12 @@ copyObject(void *from) case T_RowMarkClause: retval = _copyRowMarkClause(from); break; + case T_WithClause: + retval = _copyWithClause(from); + break; + case T_CommonTableExpr: + retval = _copyCommonTableExpr(from); + break; case T_FkConstraint: retval = _copyFkConstraint(from); break; diff --git a/src/backend/nodes/equalfuncs.c b/src/backend/nodes/equalfuncs.c index f0939b4777..f01ebe33e8 100644 --- a/src/backend/nodes/equalfuncs.c +++ b/src/backend/nodes/equalfuncs.c @@ -22,7 +22,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/nodes/equalfuncs.c,v 1.331 2008/09/01 20:42:44 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/nodes/equalfuncs.c,v 1.332 2008/10/04 21:56:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -808,6 +808,8 @@ _equalQuery(Query *a, Query *b) COMPARE_SCALAR_FIELD(hasAggs); COMPARE_SCALAR_FIELD(hasSubLinks); COMPARE_SCALAR_FIELD(hasDistinctOn); + COMPARE_SCALAR_FIELD(hasRecursive); + COMPARE_NODE_FIELD(cteList); COMPARE_NODE_FIELD(rtable); COMPARE_NODE_FIELD(jointree); COMPARE_NODE_FIELD(targetList); @@ -868,6 +870,7 @@ _equalSelectStmt(SelectStmt *a, SelectStmt *b) COMPARE_NODE_FIELD(whereClause); COMPARE_NODE_FIELD(groupClause); COMPARE_NODE_FIELD(havingClause); + COMPARE_NODE_FIELD(withClause); COMPARE_NODE_FIELD(valuesLists); COMPARE_NODE_FIELD(sortClause); COMPARE_NODE_FIELD(limitOffset); @@ -1932,12 +1935,17 @@ _equalRangeTblEntry(RangeTblEntry *a, RangeTblEntry *b) COMPARE_SCALAR_FIELD(rtekind); COMPARE_SCALAR_FIELD(relid); COMPARE_NODE_FIELD(subquery); + COMPARE_SCALAR_FIELD(jointype); + COMPARE_NODE_FIELD(joinaliasvars); COMPARE_NODE_FIELD(funcexpr); COMPARE_NODE_FIELD(funccoltypes); COMPARE_NODE_FIELD(funccoltypmods); COMPARE_NODE_FIELD(values_lists); - COMPARE_SCALAR_FIELD(jointype); - COMPARE_NODE_FIELD(joinaliasvars); + COMPARE_STRING_FIELD(ctename); + COMPARE_SCALAR_FIELD(ctelevelsup); + COMPARE_SCALAR_FIELD(self_reference); + COMPARE_NODE_FIELD(ctecoltypes); + COMPARE_NODE_FIELD(ctecoltypmods); COMPARE_NODE_FIELD(alias); COMPARE_NODE_FIELD(eref); COMPARE_SCALAR_FIELD(inh); @@ -1970,6 +1978,32 @@ _equalRowMarkClause(RowMarkClause *a, RowMarkClause *b) } static bool +_equalWithClause(WithClause *a, WithClause *b) +{ + COMPARE_NODE_FIELD(ctes); + COMPARE_SCALAR_FIELD(recursive); + COMPARE_LOCATION_FIELD(location); + + return true; +} + +static bool +_equalCommonTableExpr(CommonTableExpr *a, CommonTableExpr *b) +{ + COMPARE_STRING_FIELD(ctename); + COMPARE_NODE_FIELD(aliascolnames); + COMPARE_NODE_FIELD(ctequery); + COMPARE_LOCATION_FIELD(location); + COMPARE_SCALAR_FIELD(cterecursive); + COMPARE_SCALAR_FIELD(cterefcount); + COMPARE_NODE_FIELD(ctecolnames); + COMPARE_NODE_FIELD(ctecoltypes); + COMPARE_NODE_FIELD(ctecoltypmods); + + return true; +} + +static bool _equalFkConstraint(FkConstraint *a, FkConstraint *b) { COMPARE_STRING_FIELD(constr_name); @@ -2593,6 +2627,12 @@ equal(void *a, void *b) case T_RowMarkClause: retval = _equalRowMarkClause(a, b); break; + case T_WithClause: + retval = _equalWithClause(a, b); + break; + case T_CommonTableExpr: + retval = _equalCommonTableExpr(a, b); + break; case T_FkConstraint: retval = _equalFkConstraint(a, b); break; diff --git a/src/backend/nodes/nodeFuncs.c b/src/backend/nodes/nodeFuncs.c index a061641566..0127c6e14b 100644 --- a/src/backend/nodes/nodeFuncs.c +++ b/src/backend/nodes/nodeFuncs.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/nodes/nodeFuncs.c,v 1.32 2008/09/01 20:42:44 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/nodes/nodeFuncs.c,v 1.33 2008/10/04 21:56:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -870,6 +870,12 @@ exprLocation(Node *expr) /* XMLSERIALIZE keyword should always be the first thing */ loc = ((XmlSerialize *) expr)->location; break; + case T_WithClause: + loc = ((WithClause *) expr)->location; + break; + case T_CommonTableExpr: + loc = ((CommonTableExpr *) expr)->location; + break; default: /* for any other node type it's just unknown... */ loc = -1; @@ -1205,6 +1211,17 @@ expression_tree_walker(Node *node, case T_Query: /* Do nothing with a sub-Query, per discussion above */ break; + case T_CommonTableExpr: + { + CommonTableExpr *cte = (CommonTableExpr *) node; + + /* + * Invoke the walker on the CTE's Query node, so it + * can recurse into the sub-query if it wants to. + */ + return walker(cte->ctequery, context); + } + break; case T_List: foreach(temp, (List *) node) { @@ -1313,6 +1330,11 @@ query_tree_walker(Query *query, return true; if (walker(query->limitCount, context)) return true; + if (!(flags & QTW_IGNORE_CTE_SUBQUERIES)) + { + if (walker((Node *) query->cteList, context)) + return true; + } if (range_table_walker(query->rtable, walker, context, flags)) return true; return false; @@ -1335,10 +1357,16 @@ range_table_walker(List *rtable, { RangeTblEntry *rte = (RangeTblEntry *) lfirst(rt); + /* For historical reasons, visiting RTEs is not the default */ + if (flags & QTW_EXAMINE_RTES) + if (walker(rte, context)) + return true; + switch (rte->rtekind) { case RTE_RELATION: case RTE_SPECIAL: + case RTE_CTE: /* nothing to do */ break; case RTE_SUBQUERY: @@ -1806,6 +1834,21 @@ expression_tree_mutator(Node *node, case T_Query: /* Do nothing with a sub-Query, per discussion above */ return node; + case T_CommonTableExpr: + { + CommonTableExpr *cte = (CommonTableExpr *) node; + CommonTableExpr *newnode; + + FLATCOPY(newnode, cte, CommonTableExpr); + + /* + * Also invoke the mutator on the CTE's Query node, so it + * can recurse into the sub-query if it wants to. + */ + MUTATE(newnode->ctequery, cte->ctequery, Node *); + return (Node *) newnode; + } + break; case T_List: { /* @@ -1935,6 +1978,10 @@ query_tree_mutator(Query *query, MUTATE(query->havingQual, query->havingQual, Node *); MUTATE(query->limitOffset, query->limitOffset, Node *); MUTATE(query->limitCount, query->limitCount, Node *); + if (!(flags & QTW_IGNORE_CTE_SUBQUERIES)) + MUTATE(query->cteList, query->cteList, List *); + else /* else copy CTE list as-is */ + query->cteList = copyObject(query->cteList); query->rtable = range_table_mutator(query->rtable, mutator, context, flags); return query; @@ -1964,6 +2011,7 @@ range_table_mutator(List *rtable, { case RTE_RELATION: case RTE_SPECIAL: + case RTE_CTE: /* we don't bother to copy eref, aliases, etc; OK? */ break; case RTE_SUBQUERY: @@ -2044,3 +2092,304 @@ query_or_expression_tree_mutator(Node *node, else return mutator(node, context); } + + +/* + * raw_expression_tree_walker --- walk raw parse trees + * + * This has exactly the same API as expression_tree_walker, but instead of + * walking post-analysis parse trees, it knows how to walk the node types + * found in raw grammar output. (There is not currently any need for a + * combined walker, so we keep them separate in the name of efficiency.) + * Unlike expression_tree_walker, there is no special rule about query + * boundaries: we descend to everything that's possibly interesting. + * + * Currently, the node type coverage extends to SelectStmt and everything + * that could appear under it, but not other statement types. + */ +bool +raw_expression_tree_walker(Node *node, bool (*walker) (), void *context) +{ + ListCell *temp; + + /* + * The walker has already visited the current node, and so we need only + * recurse into any sub-nodes it has. + */ + if (node == NULL) + return false; + + /* Guard against stack overflow due to overly complex expressions */ + check_stack_depth(); + + switch (nodeTag(node)) + { + case T_SetToDefault: + case T_CurrentOfExpr: + case T_Integer: + case T_Float: + case T_String: + case T_BitString: + case T_Null: + case T_ParamRef: + case T_A_Const: + case T_A_Star: + /* primitive node types with no subnodes */ + break; + case T_Alias: + /* we assume the colnames list isn't interesting */ + break; + case T_RangeVar: + return walker(((RangeVar *) node)->alias, context); + case T_SubLink: + { + SubLink *sublink = (SubLink *) node; + + if (walker(sublink->testexpr, context)) + return true; + /* we assume the operName is not interesting */ + if (walker(sublink->subselect, context)) + return true; + } + break; + case T_CaseExpr: + { + CaseExpr *caseexpr = (CaseExpr *) node; + + if (walker(caseexpr->arg, context)) + return true; + /* we assume walker doesn't care about CaseWhens, either */ + foreach(temp, caseexpr->args) + { + CaseWhen *when = (CaseWhen *) lfirst(temp); + + Assert(IsA(when, CaseWhen)); + if (walker(when->expr, context)) + return true; + if (walker(when->result, context)) + return true; + } + if (walker(caseexpr->defresult, context)) + return true; + } + break; + case T_RowExpr: + return walker(((RowExpr *) node)->args, context); + case T_CoalesceExpr: + return walker(((CoalesceExpr *) node)->args, context); + case T_MinMaxExpr: + return walker(((MinMaxExpr *) node)->args, context); + case T_XmlExpr: + { + XmlExpr *xexpr = (XmlExpr *) node; + + if (walker(xexpr->named_args, context)) + return true; + /* we assume walker doesn't care about arg_names */ + if (walker(xexpr->args, context)) + return true; + } + break; + case T_NullTest: + return walker(((NullTest *) node)->arg, context); + case T_BooleanTest: + return walker(((BooleanTest *) node)->arg, context); + case T_JoinExpr: + { + JoinExpr *join = (JoinExpr *) node; + + if (walker(join->larg, context)) + return true; + if (walker(join->rarg, context)) + return true; + if (walker(join->quals, context)) + return true; + if (walker(join->alias, context)) + return true; + /* using list is deemed uninteresting */ + } + break; + case T_IntoClause: + { + IntoClause *into = (IntoClause *) node; + + if (walker(into->rel, context)) + return true; + /* colNames, options are deemed uninteresting */ + } + break; + case T_List: + foreach(temp, (List *) node) + { + if (walker((Node *) lfirst(temp), context)) + return true; + } + break; + case T_SelectStmt: + { + SelectStmt *stmt = (SelectStmt *) node; + + if (walker(stmt->distinctClause, context)) + return true; + if (walker(stmt->intoClause, context)) + return true; + if (walker(stmt->targetList, context)) + return true; + if (walker(stmt->fromClause, context)) + return true; + if (walker(stmt->whereClause, context)) + return true; + if (walker(stmt->groupClause, context)) + return true; + if (walker(stmt->havingClause, context)) + return true; + if (walker(stmt->withClause, context)) + return true; + if (walker(stmt->valuesLists, context)) + return true; + if (walker(stmt->sortClause, context)) + return true; + if (walker(stmt->limitOffset, context)) + return true; + if (walker(stmt->limitCount, context)) + return true; + if (walker(stmt->lockingClause, context)) + return true; + if (walker(stmt->larg, context)) + return true; + if (walker(stmt->rarg, context)) + return true; + } + break; + case T_A_Expr: + { + A_Expr *expr = (A_Expr *) node; + + if (walker(expr->lexpr, context)) + return true; + if (walker(expr->rexpr, context)) + return true; + /* operator name is deemed uninteresting */ + } + break; + case T_ColumnRef: + /* we assume the fields contain nothing interesting */ + break; + case T_FuncCall: + { + FuncCall *fcall = (FuncCall *) node; + + if (walker(fcall->args, context)) + return true; + /* function name is deemed uninteresting */ + } + break; + case T_A_Indices: + { + A_Indices *indices = (A_Indices *) node; + + if (walker(indices->lidx, context)) + return true; + if (walker(indices->uidx, context)) + return true; + } + break; + case T_A_Indirection: + { + A_Indirection *indir = (A_Indirection *) node; + + if (walker(indir->arg, context)) + return true; + if (walker(indir->indirection, context)) + return true; + } + break; + case T_A_ArrayExpr: + return walker(((A_ArrayExpr *) node)->elements, context); + case T_ResTarget: + { + ResTarget *rt = (ResTarget *) node; + + if (walker(rt->indirection, context)) + return true; + if (walker(rt->val, context)) + return true; + } + break; + case T_TypeCast: + { + TypeCast *tc = (TypeCast *) node; + + if (walker(tc->arg, context)) + return true; + if (walker(tc->typename, context)) + return true; + } + break; + case T_SortBy: + return walker(((SortBy *) node)->node, context); + case T_RangeSubselect: + { + RangeSubselect *rs = (RangeSubselect *) node; + + if (walker(rs->subquery, context)) + return true; + if (walker(rs->alias, context)) + return true; + } + break; + case T_RangeFunction: + { + RangeFunction *rf = (RangeFunction *) node; + + if (walker(rf->funccallnode, context)) + return true; + if (walker(rf->alias, context)) + return true; + } + break; + case T_TypeName: + { + TypeName *tn = (TypeName *) node; + + if (walker(tn->typmods, context)) + return true; + if (walker(tn->arrayBounds, context)) + return true; + /* type name itself is deemed uninteresting */ + } + break; + case T_ColumnDef: + { + ColumnDef *coldef = (ColumnDef *) node; + + if (walker(coldef->typename, context)) + return true; + if (walker(coldef->raw_default, context)) + return true; + /* for now, constraints are ignored */ + } + break; + case T_LockingClause: + return walker(((LockingClause *) node)->lockedRels, context); + case T_XmlSerialize: + { + XmlSerialize *xs = (XmlSerialize *) node; + + if (walker(xs->expr, context)) + return true; + if (walker(xs->typename, context)) + return true; + } + break; + case T_WithClause: + return walker(((WithClause *) node)->ctes, context); + case T_CommonTableExpr: + return walker(((CommonTableExpr *) node)->ctequery, context); + default: + elog(ERROR, "unrecognized node type: %d", + (int) nodeTag(node)); + break; + } + return false; +} diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index 0b74b3a063..6d39a51a98 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/nodes/outfuncs.c,v 1.339 2008/09/09 18:58:08 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/nodes/outfuncs.c,v 1.340 2008/10/04 21:56:53 tgl Exp $ * * NOTES * Every node type that can appear in stored rules' parsetrees *must* @@ -332,6 +332,16 @@ _outAppend(StringInfo str, Append *node) } static void +_outRecursiveUnion(StringInfo str, RecursiveUnion *node) +{ + WRITE_NODE_TYPE("RECURSIVEUNION"); + + _outPlanInfo(str, (Plan *) node); + + WRITE_INT_FIELD(wtParam); +} + +static void _outBitmapAnd(StringInfo str, BitmapAnd *node) { WRITE_NODE_TYPE("BITMAPAND"); @@ -447,6 +457,27 @@ _outValuesScan(StringInfo str, ValuesScan *node) } static void +_outCteScan(StringInfo str, CteScan *node) +{ + WRITE_NODE_TYPE("CTESCAN"); + + _outScanInfo(str, (Scan *) node); + + WRITE_INT_FIELD(ctePlanId); + WRITE_INT_FIELD(cteParam); +} + +static void +_outWorkTableScan(StringInfo str, WorkTableScan *node) +{ + WRITE_NODE_TYPE("WORKTABLESCAN"); + + _outScanInfo(str, (Scan *) node); + + WRITE_INT_FIELD(wtParam); +} + +static void _outJoin(StringInfo str, Join *node) { WRITE_NODE_TYPE("JOIN"); @@ -1382,6 +1413,7 @@ _outPlannerInfo(StringInfo str, PlannerInfo *node) WRITE_NODE_FIELD(resultRelations); WRITE_NODE_FIELD(returningLists); WRITE_NODE_FIELD(init_plans); + WRITE_NODE_FIELD(cte_plan_ids); WRITE_NODE_FIELD(eq_classes); WRITE_NODE_FIELD(canon_pathkeys); WRITE_NODE_FIELD(left_join_clauses); @@ -1398,6 +1430,8 @@ _outPlannerInfo(StringInfo str, PlannerInfo *node) WRITE_BOOL_FIELD(hasJoinRTEs); WRITE_BOOL_FIELD(hasHavingQual); WRITE_BOOL_FIELD(hasPseudoConstantQuals); + WRITE_BOOL_FIELD(hasRecursion); + WRITE_INT_FIELD(wt_param_id); } static void @@ -1648,6 +1682,7 @@ _outSelectStmt(StringInfo str, SelectStmt *node) WRITE_NODE_FIELD(whereClause); WRITE_NODE_FIELD(groupClause); WRITE_NODE_FIELD(havingClause); + WRITE_NODE_FIELD(withClause); WRITE_NODE_FIELD(valuesLists); WRITE_NODE_FIELD(sortClause); WRITE_NODE_FIELD(limitOffset); @@ -1793,6 +1828,8 @@ _outQuery(StringInfo str, Query *node) WRITE_BOOL_FIELD(hasAggs); WRITE_BOOL_FIELD(hasSubLinks); WRITE_BOOL_FIELD(hasDistinctOn); + WRITE_BOOL_FIELD(hasRecursive); + WRITE_NODE_FIELD(cteList); WRITE_NODE_FIELD(rtable); WRITE_NODE_FIELD(jointree); WRITE_NODE_FIELD(targetList); @@ -1829,6 +1866,32 @@ _outRowMarkClause(StringInfo str, RowMarkClause *node) } static void +_outWithClause(StringInfo str, WithClause *node) +{ + WRITE_NODE_TYPE("WITHCLAUSE"); + + WRITE_NODE_FIELD(ctes); + WRITE_BOOL_FIELD(recursive); + WRITE_LOCATION_FIELD(location); +} + +static void +_outCommonTableExpr(StringInfo str, CommonTableExpr *node) +{ + WRITE_NODE_TYPE("COMMONTABLEEXPR"); + + WRITE_STRING_FIELD(ctename); + WRITE_NODE_FIELD(aliascolnames); + WRITE_NODE_FIELD(ctequery); + WRITE_LOCATION_FIELD(location); + WRITE_BOOL_FIELD(cterecursive); + WRITE_INT_FIELD(cterefcount); + WRITE_NODE_FIELD(ctecolnames); + WRITE_NODE_FIELD(ctecoltypes); + WRITE_NODE_FIELD(ctecoltypmods); +} + +static void _outSetOperationStmt(StringInfo str, SetOperationStmt *node) { WRITE_NODE_TYPE("SETOPERATIONSTMT"); @@ -1861,6 +1924,10 @@ _outRangeTblEntry(StringInfo str, RangeTblEntry *node) case RTE_SUBQUERY: WRITE_NODE_FIELD(subquery); break; + case RTE_JOIN: + WRITE_ENUM_FIELD(jointype, JoinType); + WRITE_NODE_FIELD(joinaliasvars); + break; case RTE_FUNCTION: WRITE_NODE_FIELD(funcexpr); WRITE_NODE_FIELD(funccoltypes); @@ -1869,9 +1936,12 @@ _outRangeTblEntry(StringInfo str, RangeTblEntry *node) case RTE_VALUES: WRITE_NODE_FIELD(values_lists); break; - case RTE_JOIN: - WRITE_ENUM_FIELD(jointype, JoinType); - WRITE_NODE_FIELD(joinaliasvars); + case RTE_CTE: + WRITE_STRING_FIELD(ctename); + WRITE_UINT_FIELD(ctelevelsup); + WRITE_BOOL_FIELD(self_reference); + WRITE_NODE_FIELD(ctecoltypes); + WRITE_NODE_FIELD(ctecoltypmods); break; default: elog(ERROR, "unrecognized RTE kind: %d", (int) node->rtekind); @@ -2060,6 +2130,25 @@ _outSortBy(StringInfo str, SortBy *node) } static void +_outRangeSubselect(StringInfo str, RangeSubselect *node) +{ + WRITE_NODE_TYPE("RANGESUBSELECT"); + + WRITE_NODE_FIELD(subquery); + WRITE_NODE_FIELD(alias); +} + +static void +_outRangeFunction(StringInfo str, RangeFunction *node) +{ + WRITE_NODE_TYPE("RANGEFUNCTION"); + + WRITE_NODE_FIELD(funccallnode); + WRITE_NODE_FIELD(alias); + WRITE_NODE_FIELD(coldeflist); +} + +static void _outConstraint(StringInfo str, Constraint *node) { WRITE_NODE_TYPE("CONSTRAINT"); @@ -2159,6 +2248,9 @@ _outNode(StringInfo str, void *obj) case T_Append: _outAppend(str, obj); break; + case T_RecursiveUnion: + _outRecursiveUnion(str, obj); + break; case T_BitmapAnd: _outBitmapAnd(str, obj); break; @@ -2192,6 +2284,12 @@ _outNode(StringInfo str, void *obj) case T_ValuesScan: _outValuesScan(str, obj); break; + case T_CteScan: + _outCteScan(str, obj); + break; + case T_WorkTableScan: + _outWorkTableScan(str, obj); + break; case T_Join: _outJoin(str, obj); break; @@ -2473,6 +2571,12 @@ _outNode(StringInfo str, void *obj) case T_RowMarkClause: _outRowMarkClause(str, obj); break; + case T_WithClause: + _outWithClause(str, obj); + break; + case T_CommonTableExpr: + _outCommonTableExpr(str, obj); + break; case T_SetOperationStmt: _outSetOperationStmt(str, obj); break; @@ -2509,6 +2613,12 @@ _outNode(StringInfo str, void *obj) case T_SortBy: _outSortBy(str, obj); break; + case T_RangeSubselect: + _outRangeSubselect(str, obj); + break; + case T_RangeFunction: + _outRangeFunction(str, obj); + break; case T_Constraint: _outConstraint(str, obj); break; diff --git a/src/backend/nodes/print.c b/src/backend/nodes/print.c index 58a7495d37..3338e1b830 100644 --- a/src/backend/nodes/print.c +++ b/src/backend/nodes/print.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/nodes/print.c,v 1.89 2008/06/19 00:46:04 alvherre Exp $ + * $PostgreSQL: pgsql/src/backend/nodes/print.c,v 1.90 2008/10/04 21:56:53 tgl Exp $ * * HISTORY * AUTHOR DATE MAJOR EVENT @@ -272,6 +272,14 @@ print_rt(List *rtable) printf("%d\t%s\t[subquery]", i, rte->eref->aliasname); break; + case RTE_JOIN: + printf("%d\t%s\t[join]", + i, rte->eref->aliasname); + break; + case RTE_SPECIAL: + printf("%d\t%s\t[special]", + i, rte->eref->aliasname); + break; case RTE_FUNCTION: printf("%d\t%s\t[rangefunction]", i, rte->eref->aliasname); @@ -280,12 +288,8 @@ print_rt(List *rtable) printf("%d\t%s\t[values list]", i, rte->eref->aliasname); break; - case RTE_JOIN: - printf("%d\t%s\t[join]", - i, rte->eref->aliasname); - break; - case RTE_SPECIAL: - printf("%d\t%s\t[special]", + case RTE_CTE: + printf("%d\t%s\t[cte]", i, rte->eref->aliasname); break; default: diff --git a/src/backend/nodes/readfuncs.c b/src/backend/nodes/readfuncs.c index 1eca85d0b6..3f7ce455df 100644 --- a/src/backend/nodes/readfuncs.c +++ b/src/backend/nodes/readfuncs.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/nodes/readfuncs.c,v 1.214 2008/09/01 20:42:44 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/nodes/readfuncs.c,v 1.215 2008/10/04 21:56:53 tgl Exp $ * * NOTES * Path and Plan nodes do not have any readfuncs support, because we @@ -155,6 +155,8 @@ _readQuery(void) READ_BOOL_FIELD(hasAggs); READ_BOOL_FIELD(hasSubLinks); READ_BOOL_FIELD(hasDistinctOn); + READ_BOOL_FIELD(hasRecursive); + READ_NODE_FIELD(cteList); READ_NODE_FIELD(rtable); READ_NODE_FIELD(jointree); READ_NODE_FIELD(targetList); @@ -231,6 +233,27 @@ _readRowMarkClause(void) } /* + * _readCommonTableExpr + */ +static CommonTableExpr * +_readCommonTableExpr(void) +{ + READ_LOCALS(CommonTableExpr); + + READ_STRING_FIELD(ctename); + READ_NODE_FIELD(aliascolnames); + READ_NODE_FIELD(ctequery); + READ_LOCATION_FIELD(location); + READ_BOOL_FIELD(cterecursive); + READ_INT_FIELD(cterefcount); + READ_NODE_FIELD(ctecolnames); + READ_NODE_FIELD(ctecoltypes); + READ_NODE_FIELD(ctecoltypmods); + + READ_DONE(); +} + +/* * _readSetOperationStmt */ static SetOperationStmt * @@ -1007,6 +1030,10 @@ _readRangeTblEntry(void) case RTE_SUBQUERY: READ_NODE_FIELD(subquery); break; + case RTE_JOIN: + READ_ENUM_FIELD(jointype, JoinType); + READ_NODE_FIELD(joinaliasvars); + break; case RTE_FUNCTION: READ_NODE_FIELD(funcexpr); READ_NODE_FIELD(funccoltypes); @@ -1015,9 +1042,12 @@ _readRangeTblEntry(void) case RTE_VALUES: READ_NODE_FIELD(values_lists); break; - case RTE_JOIN: - READ_ENUM_FIELD(jointype, JoinType); - READ_NODE_FIELD(joinaliasvars); + case RTE_CTE: + READ_STRING_FIELD(ctename); + READ_UINT_FIELD(ctelevelsup); + READ_BOOL_FIELD(self_reference); + READ_NODE_FIELD(ctecoltypes); + READ_NODE_FIELD(ctecoltypmods); break; default: elog(ERROR, "unrecognized RTE kind: %d", @@ -1060,6 +1090,8 @@ parseNodeString(void) return_value = _readSortGroupClause(); else if (MATCH("ROWMARKCLAUSE", 13)) return_value = _readRowMarkClause(); + else if (MATCH("COMMONTABLEEXPR", 15)) + return_value = _readCommonTableExpr(); else if (MATCH("SETOPERATIONSTMT", 16)) return_value = _readSetOperationStmt(); else if (MATCH("ALIAS", 5)) diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 3dc41c6807..a942249fd0 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/path/allpaths.c,v 1.173 2008/08/25 22:42:32 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/path/allpaths.c,v 1.174 2008/10/04 21:56:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -57,6 +57,10 @@ static void set_function_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte); static void set_values_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte); +static void set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel, + RangeTblEntry *rte); +static void set_worktable_pathlist(PlannerInfo *root, RelOptInfo *rel, + RangeTblEntry *rte); static RelOptInfo *make_rel_from_joinlist(PlannerInfo *root, List *joinlist); static bool subquery_is_pushdown_safe(Query *subquery, Query *topquery, bool *differentTypes); @@ -173,14 +177,22 @@ set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, } else if (rel->rtekind == RTE_FUNCTION) { - /* RangeFunction --- generate a separate plan for it */ + /* RangeFunction --- generate a suitable path for it */ set_function_pathlist(root, rel, rte); } else if (rel->rtekind == RTE_VALUES) { - /* Values list --- generate a separate plan for it */ + /* Values list --- generate a suitable path for it */ set_values_pathlist(root, rel, rte); } + else if (rel->rtekind == RTE_CTE) + { + /* CTE reference --- generate a suitable path for it */ + if (rte->self_reference) + set_worktable_pathlist(root, rel, rte); + else + set_cte_pathlist(root, rel, rte); + } else { /* Plain relation */ @@ -585,8 +597,8 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel, /* Generate the plan for the subquery */ rel->subplan = subquery_planner(root->glob, subquery, - root->query_level + 1, - tuple_fraction, + root, + false, tuple_fraction, &subroot); rel->subrtable = subroot->parse->rtable; @@ -641,6 +653,104 @@ set_values_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) } /* + * set_cte_pathlist + * Build the (single) access path for a non-self-reference CTE RTE + */ +static void +set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) +{ + Plan *cteplan; + PlannerInfo *cteroot; + Index levelsup; + int ndx; + ListCell *lc; + int plan_id; + + /* + * Find the referenced CTE, and locate the plan previously made for it. + */ + levelsup = rte->ctelevelsup; + cteroot = root; + while (levelsup-- > 0) + { + cteroot = cteroot->parent_root; + if (!cteroot) /* shouldn't happen */ + elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename); + } + /* + * Note: cte_plan_ids can be shorter than cteList, if we are still working + * on planning the CTEs (ie, this is a side-reference from another CTE). + * So we mustn't use forboth here. + */ + ndx = 0; + foreach(lc, cteroot->parse->cteList) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + + if (strcmp(cte->ctename, rte->ctename) == 0) + break; + ndx++; + } + if (lc == NULL) /* shouldn't happen */ + elog(ERROR, "could not find CTE \"%s\"", rte->ctename); + if (ndx >= list_length(cteroot->cte_plan_ids)) + elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename); + plan_id = list_nth_int(cteroot->cte_plan_ids, ndx); + Assert(plan_id > 0); + cteplan = (Plan *) list_nth(root->glob->subplans, plan_id - 1); + + /* Mark rel with estimated output rows, width, etc */ + set_cte_size_estimates(root, rel, cteplan); + + /* Generate appropriate path */ + add_path(rel, create_ctescan_path(root, rel)); + + /* Select cheapest path (pretty easy in this case...) */ + set_cheapest(rel); +} + +/* + * set_worktable_pathlist + * Build the (single) access path for a self-reference CTE RTE + */ +static void +set_worktable_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) +{ + Plan *cteplan; + PlannerInfo *cteroot; + Index levelsup; + + /* + * We need to find the non-recursive term's plan, which is in the plan + * level that's processing the recursive UNION, which is one level + * *below* where the CTE comes from. + */ + levelsup = rte->ctelevelsup; + if (levelsup == 0) /* shouldn't happen */ + elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename); + levelsup--; + cteroot = root; + while (levelsup-- > 0) + { + cteroot = cteroot->parent_root; + if (!cteroot) /* shouldn't happen */ + elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename); + } + cteplan = cteroot->non_recursive_plan; + if (!cteplan) /* shouldn't happen */ + elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename); + + /* Mark rel with estimated output rows, width, etc */ + set_cte_size_estimates(root, rel, cteplan); + + /* Generate appropriate path */ + add_path(rel, create_worktablescan_path(root, rel)); + + /* Select cheapest path (pretty easy in this case...) */ + set_cheapest(rel); +} + +/* * make_rel_from_joinlist * Build access paths using a "joinlist" to guide the join path search. * diff --git a/src/backend/optimizer/path/clausesel.c b/src/backend/optimizer/path/clausesel.c index 9ffdc32e77..e3e4e9f02c 100644 --- a/src/backend/optimizer/path/clausesel.c +++ b/src/backend/optimizer/path/clausesel.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/path/clausesel.c,v 1.93 2008/08/22 00:16:03 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/path/clausesel.c,v 1.94 2008/10/04 21:56:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -550,29 +550,17 @@ clause_selectivity(PlannerInfo *root, if (var->varlevelsup == 0 && (varRelid == 0 || varRelid == (int) var->varno)) { - RangeTblEntry *rte = planner_rt_fetch(var->varno, root); - - if (rte->rtekind == RTE_SUBQUERY) - { - /* - * XXX not smart about subquery references... any way to do - * better than default? - */ - } - else - { - /* - * A Var at the top of a clause must be a bool Var. This is - * equivalent to the clause reln.attribute = 't', so we - * compute the selectivity as if that is what we have. - */ - s1 = restriction_selectivity(root, - BooleanEqualOperator, - list_make2(var, - makeBoolConst(true, - false)), - varRelid); - } + /* + * A Var at the top of a clause must be a bool Var. This is + * equivalent to the clause reln.attribute = 't', so we + * compute the selectivity as if that is what we have. + */ + s1 = restriction_selectivity(root, + BooleanEqualOperator, + list_make2(var, + makeBoolConst(true, + false)), + varRelid); } } else if (IsA(clause, Const)) diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index bbc77db4e2..7bfc66cac3 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -54,7 +54,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/path/costsize.c,v 1.197 2008/09/05 21:07:29 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/path/costsize.c,v 1.198 2008/10/04 21:56:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -934,6 +934,84 @@ cost_valuesscan(Path *path, PlannerInfo *root, RelOptInfo *baserel) } /* + * cost_ctescan + * Determines and returns the cost of scanning a CTE RTE. + * + * Note: this is used for both self-reference and regular CTEs; the + * possible cost differences are below the threshold of what we could + * estimate accurately anyway. Note that the costs of evaluating the + * referenced CTE query are added into the final plan as initplan costs, + * and should NOT be counted here. + */ +void +cost_ctescan(Path *path, PlannerInfo *root, RelOptInfo *baserel) +{ + Cost startup_cost = 0; + Cost run_cost = 0; + Cost cpu_per_tuple; + + /* Should only be applied to base relations that are CTEs */ + Assert(baserel->relid > 0); + Assert(baserel->rtekind == RTE_CTE); + + /* Charge one CPU tuple cost per row for tuplestore manipulation */ + cpu_per_tuple = cpu_tuple_cost; + + /* Add scanning CPU costs */ + startup_cost += baserel->baserestrictcost.startup; + cpu_per_tuple += cpu_tuple_cost + baserel->baserestrictcost.per_tuple; + run_cost += cpu_per_tuple * baserel->tuples; + + path->startup_cost = startup_cost; + path->total_cost = startup_cost + run_cost; +} + +/* + * cost_recursive_union + * Determines and returns the cost of performing a recursive union, + * and also the estimated output size. + * + * We are given Plans for the nonrecursive and recursive terms. + * + * Note that the arguments and output are Plans, not Paths as in most of + * the rest of this module. That's because we don't bother setting up a + * Path representation for recursive union --- we have only one way to do it. + */ +void +cost_recursive_union(Plan *runion, Plan *nrterm, Plan *rterm) +{ + Cost startup_cost; + Cost total_cost; + double total_rows; + + /* We probably have decent estimates for the non-recursive term */ + startup_cost = nrterm->startup_cost; + total_cost = nrterm->total_cost; + total_rows = nrterm->plan_rows; + + /* + * We arbitrarily assume that about 10 recursive iterations will be + * needed, and that we've managed to get a good fix on the cost and + * output size of each one of them. These are mighty shaky assumptions + * but it's hard to see how to do better. + */ + total_cost += 10 * rterm->total_cost; + total_rows += 10 * rterm->plan_rows; + + /* + * Also charge cpu_tuple_cost per row to account for the costs of + * manipulating the tuplestores. (We don't worry about possible + * spill-to-disk costs.) + */ + total_cost += cpu_tuple_cost * total_rows; + + runion->startup_cost = startup_cost; + runion->total_cost = total_cost; + runion->plan_rows = total_rows; + runion->plan_width = Max(nrterm->plan_width, rterm->plan_width); +} + +/* * cost_sort * Determines and returns the cost of sorting a relation, including * the cost of reading the input data. @@ -2475,6 +2553,44 @@ set_values_size_estimates(PlannerInfo *root, RelOptInfo *rel) set_baserel_size_estimates(root, rel); } +/* + * set_cte_size_estimates + * Set the size estimates for a base relation that is a CTE reference. + * + * The rel's targetlist and restrictinfo list must have been constructed + * already, and we need the completed plan for the CTE (if a regular CTE) + * or the non-recursive term (if a self-reference). + * + * We set the same fields as set_baserel_size_estimates. + */ +void +set_cte_size_estimates(PlannerInfo *root, RelOptInfo *rel, Plan *cteplan) +{ + RangeTblEntry *rte; + + /* Should only be applied to base relations that are CTE references */ + Assert(rel->relid > 0); + rte = planner_rt_fetch(rel->relid, root); + Assert(rte->rtekind == RTE_CTE); + + if (rte->self_reference) + { + /* + * In a self-reference, arbitrarily assume the average worktable + * size is about 10 times the nonrecursive term's size. + */ + rel->tuples = 10 * cteplan->plan_rows; + } + else + { + /* Otherwise just believe the CTE plan's output estimate */ + rel->tuples = cteplan->plan_rows; + } + + /* Now estimate number of output rows, etc */ + set_baserel_size_estimates(root, rel); +} + /* * set_rel_width diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c index 845f429a4b..eaf0ffa427 100644 --- a/src/backend/optimizer/path/joinpath.c +++ b/src/backend/optimizer/path/joinpath.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/path/joinpath.c,v 1.117 2008/08/14 18:47:59 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/path/joinpath.c,v 1.118 2008/10/04 21:56:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -408,10 +408,15 @@ match_unsorted_outer(PlannerInfo *root, * If the cheapest inner path is a join or seqscan, we should consider * materializing it. (This is a heuristic: we could consider it * always, but for inner indexscans it's probably a waste of time.) + * Also skip it if the inner path materializes its output anyway. */ - if (!(IsA(inner_cheapest_total, IndexPath) || - IsA(inner_cheapest_total, BitmapHeapPath) || - IsA(inner_cheapest_total, TidPath))) + if (!(inner_cheapest_total->pathtype == T_IndexScan || + inner_cheapest_total->pathtype == T_BitmapHeapScan || + inner_cheapest_total->pathtype == T_TidScan || + inner_cheapest_total->pathtype == T_Material || + inner_cheapest_total->pathtype == T_FunctionScan || + inner_cheapest_total->pathtype == T_CteScan || + inner_cheapest_total->pathtype == T_WorkTableScan)) matpath = (Path *) create_material_path(innerrel, inner_cheapest_total); diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index 1195024b5f..aabbf64a75 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -10,7 +10,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.248 2008/09/05 21:07:29 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.249 2008/10/04 21:56:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -62,6 +62,10 @@ static FunctionScan *create_functionscan_plan(PlannerInfo *root, Path *best_path List *tlist, List *scan_clauses); static ValuesScan *create_valuesscan_plan(PlannerInfo *root, Path *best_path, List *tlist, List *scan_clauses); +static CteScan *create_ctescan_plan(PlannerInfo *root, Path *best_path, + List *tlist, List *scan_clauses); +static WorkTableScan *create_worktablescan_plan(PlannerInfo *root, Path *best_path, + List *tlist, List *scan_clauses); static NestLoop *create_nestloop_plan(PlannerInfo *root, NestPath *best_path, Plan *outer_plan, Plan *inner_plan); static MergeJoin *create_mergejoin_plan(PlannerInfo *root, MergePath *best_path, @@ -93,6 +97,10 @@ static FunctionScan *make_functionscan(List *qptlist, List *qpqual, List *funccoltypes, List *funccoltypmods); static ValuesScan *make_valuesscan(List *qptlist, List *qpqual, Index scanrelid, List *values_lists); +static CteScan *make_ctescan(List *qptlist, List *qpqual, + Index scanrelid, int ctePlanId, int cteParam); +static WorkTableScan *make_worktablescan(List *qptlist, List *qpqual, + Index scanrelid, int wtParam); static BitmapAnd *make_bitmap_and(List *bitmapplans); static BitmapOr *make_bitmap_or(List *bitmapplans); static NestLoop *make_nestloop(List *tlist, @@ -148,6 +156,8 @@ create_plan(PlannerInfo *root, Path *best_path) case T_SubqueryScan: case T_FunctionScan: case T_ValuesScan: + case T_CteScan: + case T_WorkTableScan: plan = create_scan_plan(root, best_path); break; case T_HashJoin: @@ -270,6 +280,20 @@ create_scan_plan(PlannerInfo *root, Path *best_path) scan_clauses); break; + case T_CteScan: + plan = (Plan *) create_ctescan_plan(root, + best_path, + tlist, + scan_clauses); + break; + + case T_WorkTableScan: + plan = (Plan *) create_worktablescan_plan(root, + best_path, + tlist, + scan_clauses); + break; + default: elog(ERROR, "unrecognized node type: %d", (int) best_path->pathtype); @@ -324,12 +348,13 @@ use_physical_tlist(RelOptInfo *rel) /* * We can do this for real relation scans, subquery scans, function scans, - * and values scans (but not for, eg, joins). + * values scans, and CTE scans (but not for, eg, joins). */ if (rel->rtekind != RTE_RELATION && rel->rtekind != RTE_SUBQUERY && rel->rtekind != RTE_FUNCTION && - rel->rtekind != RTE_VALUES) + rel->rtekind != RTE_VALUES && + rel->rtekind != RTE_CTE) return false; /* @@ -375,6 +400,8 @@ disuse_physical_tlist(Plan *plan, Path *path) case T_SubqueryScan: case T_FunctionScan: case T_ValuesScan: + case T_CteScan: + case T_WorkTableScan: plan->targetlist = build_relation_tlist(path->parent); break; default: @@ -1335,6 +1362,145 @@ create_valuesscan_plan(PlannerInfo *root, Path *best_path, return scan_plan; } +/* + * create_ctescan_plan + * Returns a ctescan plan for the base relation scanned by 'best_path' + * with restriction clauses 'scan_clauses' and targetlist 'tlist'. + */ +static CteScan * +create_ctescan_plan(PlannerInfo *root, Path *best_path, + List *tlist, List *scan_clauses) +{ + CteScan *scan_plan; + Index scan_relid = best_path->parent->relid; + RangeTblEntry *rte; + SubPlan *ctesplan = NULL; + int plan_id; + int cte_param_id; + PlannerInfo *cteroot; + Index levelsup; + int ndx; + ListCell *lc; + + Assert(scan_relid > 0); + rte = planner_rt_fetch(scan_relid, root); + Assert(rte->rtekind == RTE_CTE); + Assert(!rte->self_reference); + + /* + * Find the referenced CTE, and locate the SubPlan previously made for it. + */ + levelsup = rte->ctelevelsup; + cteroot = root; + while (levelsup-- > 0) + { + cteroot = cteroot->parent_root; + if (!cteroot) /* shouldn't happen */ + elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename); + } + /* + * Note: cte_plan_ids can be shorter than cteList, if we are still working + * on planning the CTEs (ie, this is a side-reference from another CTE). + * So we mustn't use forboth here. + */ + ndx = 0; + foreach(lc, cteroot->parse->cteList) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + + if (strcmp(cte->ctename, rte->ctename) == 0) + break; + ndx++; + } + if (lc == NULL) /* shouldn't happen */ + elog(ERROR, "could not find CTE \"%s\"", rte->ctename); + if (ndx >= list_length(cteroot->cte_plan_ids)) + elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename); + plan_id = list_nth_int(cteroot->cte_plan_ids, ndx); + Assert(plan_id > 0); + foreach(lc, cteroot->init_plans) + { + ctesplan = (SubPlan *) lfirst(lc); + if (ctesplan->plan_id == plan_id) + break; + } + if (lc == NULL) /* shouldn't happen */ + elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename); + + /* + * We need the CTE param ID, which is the sole member of the + * SubPlan's setParam list. + */ + cte_param_id = linitial_int(ctesplan->setParam); + + /* Sort clauses into best execution order */ + scan_clauses = order_qual_clauses(root, scan_clauses); + + /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */ + scan_clauses = extract_actual_clauses(scan_clauses, false); + + scan_plan = make_ctescan(tlist, scan_clauses, scan_relid, + plan_id, cte_param_id); + + copy_path_costsize(&scan_plan->scan.plan, best_path); + + return scan_plan; +} + +/* + * create_worktablescan_plan + * Returns a worktablescan plan for the base relation scanned by 'best_path' + * with restriction clauses 'scan_clauses' and targetlist 'tlist'. + */ +static WorkTableScan * +create_worktablescan_plan(PlannerInfo *root, Path *best_path, + List *tlist, List *scan_clauses) +{ + WorkTableScan *scan_plan; + Index scan_relid = best_path->parent->relid; + RangeTblEntry *rte; + Index levelsup; + PlannerInfo *cteroot; + + Assert(scan_relid > 0); + rte = planner_rt_fetch(scan_relid, root); + Assert(rte->rtekind == RTE_CTE); + Assert(rte->self_reference); + + /* + * We need to find the worktable param ID, which is in the plan level + * that's processing the recursive UNION, which is one level *below* + * where the CTE comes from. + */ + levelsup = rte->ctelevelsup; + if (levelsup == 0) /* shouldn't happen */ + elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename); + levelsup--; + cteroot = root; + while (levelsup-- > 0) + { + cteroot = cteroot->parent_root; + if (!cteroot) /* shouldn't happen */ + elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename); + } + if (cteroot->wt_param_id < 0) /* shouldn't happen */ + elog(ERROR, "could not find param ID for CTE \"%s\"", rte->ctename); + + /* Sort clauses into best execution order */ + scan_clauses = order_qual_clauses(root, scan_clauses); + + /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */ + scan_clauses = extract_actual_clauses(scan_clauses, false); + + scan_plan = make_worktablescan(tlist, scan_clauses, scan_relid, + cteroot->wt_param_id); + + copy_path_costsize(&scan_plan->scan.plan, best_path); + + return scan_plan; +} + + /***************************************************************************** * * JOIN METHODS @@ -2291,6 +2457,48 @@ make_valuesscan(List *qptlist, return node; } +static CteScan * +make_ctescan(List *qptlist, + List *qpqual, + Index scanrelid, + int ctePlanId, + int cteParam) +{ + CteScan *node = makeNode(CteScan); + Plan *plan = &node->scan.plan; + + /* cost should be inserted by caller */ + plan->targetlist = qptlist; + plan->qual = qpqual; + plan->lefttree = NULL; + plan->righttree = NULL; + node->scan.scanrelid = scanrelid; + node->ctePlanId = ctePlanId; + node->cteParam = cteParam; + + return node; +} + +static WorkTableScan * +make_worktablescan(List *qptlist, + List *qpqual, + Index scanrelid, + int wtParam) +{ + WorkTableScan *node = makeNode(WorkTableScan); + Plan *plan = &node->scan.plan; + + /* cost should be inserted by caller */ + plan->targetlist = qptlist; + plan->qual = qpqual; + plan->lefttree = NULL; + plan->righttree = NULL; + node->scan.scanrelid = scanrelid; + node->wtParam = wtParam; + + return node; +} + Append * make_append(List *appendplans, bool isTarget, List *tlist) { @@ -2333,6 +2541,26 @@ make_append(List *appendplans, bool isTarget, List *tlist) return node; } +RecursiveUnion * +make_recursive_union(List *tlist, + Plan *lefttree, + Plan *righttree, + int wtParam) +{ + RecursiveUnion *node = makeNode(RecursiveUnion); + Plan *plan = &node->plan; + + cost_recursive_union(plan, lefttree, righttree); + + plan->targetlist = tlist; + plan->qual = NIL; + plan->lefttree = lefttree; + plan->righttree = righttree; + node->wtParam = wtParam; + + return node; +} + static BitmapAnd * make_bitmap_and(List *bitmapplans) { @@ -3284,6 +3512,7 @@ is_projection_capable_plan(Plan *plan) case T_SetOp: case T_Limit: case T_Append: + case T_RecursiveUnion: return false; default: break; diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index ec2b0f794a..0a704dc654 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/plan/planner.c,v 1.243 2008/09/09 18:58:08 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/plan/planner.c,v 1.244 2008/10/04 21:56:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -173,7 +173,8 @@ standard_planner(Query *parse, int cursorOptions, ParamListInfo boundParams) } /* primary planning entry point (may recurse for subqueries) */ - top_plan = subquery_planner(glob, parse, 1, tuple_fraction, &root); + top_plan = subquery_planner(glob, parse, NULL, + false, tuple_fraction, &root); /* * If creating a plan for a scrollable cursor, make sure it can run @@ -228,7 +229,8 @@ standard_planner(Query *parse, int cursorOptions, ParamListInfo boundParams) * * glob is the global state for the current planner run. * parse is the querytree produced by the parser & rewriter. - * level is the current recursion depth (1 at the top-level Query). + * parent_root is the immediate parent Query's info (NULL at the top level). + * hasRecursion is true if this is a recursive WITH query. * tuple_fraction is the fraction of tuples we expect will be retrieved. * tuple_fraction is interpreted as explained for grouping_planner, below. * @@ -249,7 +251,8 @@ standard_planner(Query *parse, int cursorOptions, ParamListInfo boundParams) */ Plan * subquery_planner(PlannerGlobal *glob, Query *parse, - Index level, double tuple_fraction, + PlannerInfo *parent_root, + bool hasRecursion, double tuple_fraction, PlannerInfo **subroot) { int num_old_subplans = list_length(glob->subplans); @@ -263,12 +266,28 @@ subquery_planner(PlannerGlobal *glob, Query *parse, root = makeNode(PlannerInfo); root->parse = parse; root->glob = glob; - root->query_level = level; + root->query_level = parent_root ? parent_root->query_level + 1 : 1; + root->parent_root = parent_root; root->planner_cxt = CurrentMemoryContext; root->init_plans = NIL; + root->cte_plan_ids = NIL; root->eq_classes = NIL; root->append_rel_list = NIL; + root->hasRecursion = hasRecursion; + if (hasRecursion) + root->wt_param_id = SS_assign_worktable_param(root); + else + root->wt_param_id = -1; + root->non_recursive_plan = NULL; + + /* + * If there is a WITH list, process each WITH query and build an + * initplan SubPlan structure for it. + */ + if (parse->cteList) + SS_process_ctes(root); + /* * Look for ANY and EXISTS SubLinks in WHERE and JOIN/ON clauses, and try * to transform them into joins. Note that this step does not descend @@ -776,7 +795,9 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) /* * Construct the plan for set operations. The result will not need - * any work except perhaps a top-level sort and/or LIMIT. + * any work except perhaps a top-level sort and/or LIMIT. Note that + * any special work for recursive unions is the responsibility of + * plan_set_operations. */ result_plan = plan_set_operations(root, tuple_fraction, &set_sortclauses); @@ -838,6 +859,9 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) MemSet(&agg_counts, 0, sizeof(AggClauseCounts)); + /* A recursive query should always have setOperations */ + Assert(!root->hasRecursion); + /* Preprocess GROUP BY clause, if any */ if (parse->groupClause) preprocess_groupclause(root); diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c index 1836262872..6d7ec283b3 100644 --- a/src/backend/optimizer/plan/setrefs.c +++ b/src/backend/optimizer/plan/setrefs.c @@ -9,7 +9,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/plan/setrefs.c,v 1.144 2008/09/09 18:58:08 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/plan/setrefs.c,v 1.145 2008/10/04 21:56:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -201,11 +201,13 @@ set_plan_references(PlannerGlobal *glob, Plan *plan, List *rtable) /* zap unneeded sub-structure */ newrte->subquery = NULL; + newrte->joinaliasvars = NIL; newrte->funcexpr = NULL; newrte->funccoltypes = NIL; newrte->funccoltypmods = NIL; newrte->values_lists = NIL; - newrte->joinaliasvars = NIL; + newrte->ctecoltypes = NIL; + newrte->ctecoltypmods = NIL; glob->finalrtable = lappend(glob->finalrtable, newrte); @@ -343,7 +345,28 @@ set_plan_refs(PlannerGlobal *glob, Plan *plan, int rtoffset) fix_scan_list(glob, splan->values_lists, rtoffset); } break; + case T_CteScan: + { + CteScan *splan = (CteScan *) plan; + + splan->scan.scanrelid += rtoffset; + splan->scan.plan.targetlist = + fix_scan_list(glob, splan->scan.plan.targetlist, rtoffset); + splan->scan.plan.qual = + fix_scan_list(glob, splan->scan.plan.qual, rtoffset); + } + break; + case T_WorkTableScan: + { + WorkTableScan *splan = (WorkTableScan *) plan; + splan->scan.scanrelid += rtoffset; + splan->scan.plan.targetlist = + fix_scan_list(glob, splan->scan.plan.targetlist, rtoffset); + splan->scan.plan.qual = + fix_scan_list(glob, splan->scan.plan.qual, rtoffset); + } + break; case T_NestLoop: case T_MergeJoin: case T_HashJoin: @@ -434,6 +457,11 @@ set_plan_refs(PlannerGlobal *glob, Plan *plan, int rtoffset) } } break; + case T_RecursiveUnion: + /* This doesn't evaluate targetlist or check quals either */ + set_dummy_tlist_references(plan, rtoffset); + Assert(plan->qual == NIL); + break; case T_BitmapAnd: { BitmapAnd *splan = (BitmapAnd *) plan; diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c index fe8be5b1bb..00d84d5682 100644 --- a/src/backend/optimizer/plan/subselect.c +++ b/src/backend/optimizer/plan/subselect.c @@ -7,7 +7,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/plan/subselect.c,v 1.140 2008/08/28 23:09:46 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/plan/subselect.c,v 1.141 2008/10/04 21:56:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -213,6 +213,20 @@ generate_new_param(PlannerInfo *root, Oid paramtype, int32 paramtypmod) } /* + * Assign a (nonnegative) PARAM_EXEC ID for a recursive query's worktable. + */ +int +SS_assign_worktable_param(PlannerInfo *root) +{ + Param *param; + + /* We generate a Param of datatype INTERNAL */ + param = generate_new_param(root, INTERNALOID, -1); + /* ... but the caller only cares about its ID */ + return param->paramid; +} + +/* * Get the datatype of the first column of the plan's output. * * This is stored for ARRAY_SUBLINK and for exprType(), which doesn't have any @@ -308,8 +322,8 @@ make_subplan(PlannerInfo *root, Query *orig_subquery, SubLinkType subLinkType, * Generate the plan for the subquery. */ plan = subquery_planner(root->glob, subquery, - root->query_level + 1, - tuple_fraction, + root, + false, tuple_fraction, &subroot); /* And convert to SubPlan or InitPlan format. */ @@ -342,8 +356,8 @@ make_subplan(PlannerInfo *root, Query *orig_subquery, SubLinkType subLinkType, { /* Generate the plan for the ANY subquery; we'll need all rows */ plan = subquery_planner(root->glob, subquery, - root->query_level + 1, - 0.0, + root, + false, 0.0, &subroot); /* Now we can check if it'll fit in work_mem */ @@ -549,6 +563,8 @@ build_subplan(PlannerInfo *root, Plan *plan, List *rtable, { case T_Material: case T_FunctionScan: + case T_CteScan: + case T_WorkTableScan: case T_Sort: use_material = false; break; @@ -798,6 +814,123 @@ hash_ok_operator(OpExpr *expr) return true; } + +/* + * SS_process_ctes: process a query's WITH list + * + * We plan each interesting WITH item and convert it to an initplan. + * A side effect is to fill in root->cte_plan_ids with a list that + * parallels root->parse->cteList and provides the subplan ID for + * each CTE's initplan. + */ +void +SS_process_ctes(PlannerInfo *root) +{ + ListCell *lc; + + Assert(root->cte_plan_ids == NIL); + + foreach(lc, root->parse->cteList) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + Query *subquery; + Plan *plan; + PlannerInfo *subroot; + SubPlan *splan; + Bitmapset *tmpset; + int paramid; + Param *prm; + + /* + * Ignore CTEs that are not actually referenced anywhere. + */ + if (cte->cterefcount == 0) + { + /* Make a dummy entry in cte_plan_ids */ + root->cte_plan_ids = lappend_int(root->cte_plan_ids, -1); + continue; + } + + /* + * Copy the source Query node. Probably not necessary, but let's + * keep this similar to make_subplan. + */ + subquery = (Query *) copyObject(cte->ctequery); + + /* + * Generate the plan for the CTE query. Always plan for full + * retrieval --- we don't have enough info to predict otherwise. + */ + plan = subquery_planner(root->glob, subquery, + root, + cte->cterecursive, 0.0, + &subroot); + + /* + * Make a SubPlan node for it. This is just enough unlike + * build_subplan that we can't share code. + * + * Note plan_id isn't set till further down, likewise the cost fields. + */ + splan = makeNode(SubPlan); + splan->subLinkType = CTE_SUBLINK; + splan->testexpr = NULL; + splan->paramIds = NIL; + splan->firstColType = get_first_col_type(plan); + splan->useHashTable = false; + splan->unknownEqFalse = false; + splan->setParam = NIL; + splan->parParam = NIL; + splan->args = NIL; + + /* + * Make parParam and args lists of param IDs and expressions that + * current query level will pass to this child plan. Even though + * this is an initplan, there could be side-references to earlier + * initplan's outputs, specifically their CTE output parameters. + */ + tmpset = bms_copy(plan->extParam); + while ((paramid = bms_first_member(tmpset)) >= 0) + { + PlannerParamItem *pitem = list_nth(root->glob->paramlist, paramid); + + if (pitem->abslevel == root->query_level) + { + prm = (Param *) pitem->item; + if (!IsA(prm, Param) || + prm->paramtype != INTERNALOID) + elog(ERROR, "bogus local parameter passed to WITH query"); + + splan->parParam = lappend_int(splan->parParam, paramid); + splan->args = lappend(splan->args, copyObject(prm)); + } + } + bms_free(tmpset); + + /* + * Assign a param to represent the query output. We only really + * care about reserving a parameter ID number. + */ + prm = generate_new_param(root, INTERNALOID, -1); + splan->setParam = list_make1_int(prm->paramid); + + /* + * Add the subplan and its rtable to the global lists. + */ + root->glob->subplans = lappend(root->glob->subplans, plan); + root->glob->subrtables = lappend(root->glob->subrtables, + subroot->parse->rtable); + splan->plan_id = list_length(root->glob->subplans); + + root->init_plans = lappend(root->init_plans, splan); + + root->cte_plan_ids = lappend_int(root->cte_plan_ids, splan->plan_id); + + /* Lastly, fill in the cost estimates for use later */ + cost_subplan(root, splan, plan); + } +} + /* * convert_ANY_sublink_to_join: can we convert an ANY SubLink to a join? * @@ -1589,6 +1722,9 @@ SS_finalize_plan(PlannerInfo *root, Plan *plan, bool attach_initplans) paramid++; } + /* Also include the recursion working table, if any */ + if (root->wt_param_id >= 0) + valid_params = bms_add_member(valid_params, root->wt_param_id); /* * Now recurse through plan tree. @@ -1719,6 +1855,18 @@ finalize_plan(PlannerInfo *root, Plan *plan, Bitmapset *valid_params) &context); break; + case T_CteScan: + context.paramids = + bms_add_member(context.paramids, + ((CteScan *) plan)->cteParam); + break; + + case T_WorkTableScan: + context.paramids = + bms_add_member(context.paramids, + ((WorkTableScan *) plan)->wtParam); + break; + case T_Append: { ListCell *l; @@ -1790,6 +1938,7 @@ finalize_plan(PlannerInfo *root, Plan *plan, Bitmapset *valid_params) &context); break; + case T_RecursiveUnion: case T_Hash: case T_Agg: case T_SeqScan: @@ -1816,6 +1965,15 @@ finalize_plan(PlannerInfo *root, Plan *plan, Bitmapset *valid_params) plan->righttree, valid_params)); + /* + * RecursiveUnion *generates* its worktable param, so don't bubble that up + */ + if (IsA(plan, RecursiveUnion)) + { + context.paramids = bms_del_member(context.paramids, + ((RecursiveUnion *) plan)->wtParam); + } + /* Now we have all the paramids */ if (!bms_is_subset(context.paramids, valid_params)) diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c index 965856385d..21bd8332f4 100644 --- a/src/backend/optimizer/prep/prepjointree.c +++ b/src/backend/optimizer/prep/prepjointree.c @@ -16,7 +16,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/prep/prepjointree.c,v 1.54 2008/08/25 22:42:33 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/prep/prepjointree.c,v 1.55 2008/10/04 21:56:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -567,10 +567,18 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte, subroot->parse = subquery; subroot->glob = root->glob; subroot->query_level = root->query_level; + subroot->parent_root = root->parent_root; subroot->planner_cxt = CurrentMemoryContext; subroot->init_plans = NIL; + subroot->cte_plan_ids = NIL; subroot->eq_classes = NIL; subroot->append_rel_list = NIL; + subroot->hasRecursion = false; + subroot->wt_param_id = -1; + subroot->non_recursive_plan = NULL; + + /* No CTEs to worry about */ + Assert(subquery->cteList == NIL); /* * Pull up any SubLinks within the subquery's quals, so that we don't @@ -916,8 +924,8 @@ is_simple_subquery(Query *subquery) return false; /* - * Can't pull up a subquery involving grouping, aggregation, sorting, or - * limiting. + * Can't pull up a subquery involving grouping, aggregation, sorting, + * limiting, or WITH. (XXX WITH could possibly be allowed later) */ if (subquery->hasAggs || subquery->groupClause || @@ -925,7 +933,8 @@ is_simple_subquery(Query *subquery) subquery->sortClause || subquery->distinctClause || subquery->limitOffset || - subquery->limitCount) + subquery->limitCount || + subquery->cteList) return false; /* @@ -985,11 +994,12 @@ is_simple_union_all(Query *subquery) return false; Assert(IsA(topop, SetOperationStmt)); - /* Can't handle ORDER BY, LIMIT/OFFSET, or locking */ + /* Can't handle ORDER BY, LIMIT/OFFSET, locking, or WITH */ if (subquery->sortClause || subquery->limitOffset || subquery->limitCount || - subquery->rowMarks) + subquery->rowMarks || + subquery->cteList) return false; /* Recursively check the tree of set operations */ diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c index 7dc274797e..0836fde517 100644 --- a/src/backend/optimizer/prep/prepunion.c +++ b/src/backend/optimizer/prep/prepunion.c @@ -22,7 +22,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/prep/prepunion.c,v 1.155 2008/08/28 23:09:46 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/prep/prepunion.c,v 1.156 2008/10/04 21:56:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -56,6 +56,10 @@ static Plan *recurse_set_operations(Node *setOp, PlannerInfo *root, List *colTypes, bool junkOK, int flag, List *refnames_tlist, List **sortClauses, double *pNumGroups); +static Plan *generate_recursion_plan(SetOperationStmt *setOp, + PlannerInfo *root, double tuple_fraction, + List *refnames_tlist, + List **sortClauses); static Plan *generate_union_plan(SetOperationStmt *op, PlannerInfo *root, double tuple_fraction, List *refnames_tlist, @@ -148,6 +152,14 @@ plan_set_operations(PlannerInfo *root, double tuple_fraction, Assert(leftmostQuery != NULL); /* + * If the topmost node is a recursive union, it needs special processing. + */ + if (root->hasRecursion) + return generate_recursion_plan(topop, root, tuple_fraction, + leftmostQuery->targetList, + sortClauses); + + /* * Recurse on setOperations tree to generate plans for set ops. The final * output plan should have just the column types shown as the output from * the top-level node, plus possibly resjunk working columns (we can rely @@ -200,8 +212,8 @@ recurse_set_operations(Node *setOp, PlannerInfo *root, * Generate plan for primitive subquery */ subplan = subquery_planner(root->glob, subquery, - root->query_level + 1, - tuple_fraction, + root, + false, tuple_fraction, &subroot); /* @@ -294,6 +306,58 @@ recurse_set_operations(Node *setOp, PlannerInfo *root, } /* + * Generate plan for a recursive UNION node + */ +static Plan * +generate_recursion_plan(SetOperationStmt *setOp, PlannerInfo *root, + double tuple_fraction, + List *refnames_tlist, + List **sortClauses) +{ + Plan *plan; + Plan *lplan; + Plan *rplan; + List *tlist; + + /* Parser should have rejected other cases */ + if (setOp->op != SETOP_UNION || !setOp->all) + elog(ERROR, "only UNION ALL queries can be recursive"); + /* Worktable ID should be assigned */ + Assert(root->wt_param_id >= 0); + + /* + * Unlike a regular UNION node, process the left and right inputs + * separately without any intention of combining them into one Append. + */ + lplan = recurse_set_operations(setOp->larg, root, tuple_fraction, + setOp->colTypes, false, -1, + refnames_tlist, sortClauses, NULL); + /* The right plan will want to look at the left one ... */ + root->non_recursive_plan = lplan; + rplan = recurse_set_operations(setOp->rarg, root, tuple_fraction, + setOp->colTypes, false, -1, + refnames_tlist, sortClauses, NULL); + root->non_recursive_plan = NULL; + + /* + * Generate tlist for RecursiveUnion plan node --- same as in Append cases + */ + tlist = generate_append_tlist(setOp->colTypes, false, + list_make2(lplan, rplan), + refnames_tlist); + + /* + * And make the plan node. + */ + plan = (Plan *) make_recursive_union(tlist, lplan, rplan, + root->wt_param_id); + + *sortClauses = NIL; /* result of UNION ALL is always unsorted */ + + return plan; +} + +/* * Generate plan for a UNION or UNION ALL node */ static Plan * @@ -1346,7 +1410,7 @@ adjust_appendrel_attrs(Node *node, AppendRelInfo *appinfo) newnode = query_tree_mutator((Query *) node, adjust_appendrel_attrs_mutator, (void *) appinfo, - QTW_IGNORE_RT_SUBQUERIES); + QTW_IGNORE_RC_SUBQUERIES); if (newnode->resultRelation == appinfo->parent_relid) { newnode->resultRelation = appinfo->child_relid; diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c index 097105a89a..bd0192d829 100644 --- a/src/backend/optimizer/util/clauses.c +++ b/src/backend/optimizer/util/clauses.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/util/clauses.c,v 1.267 2008/09/09 18:58:08 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/util/clauses.c,v 1.268 2008/10/04 21:56:53 tgl Exp $ * * HISTORY * AUTHOR DATE MAJOR EVENT @@ -3361,6 +3361,7 @@ inline_function(Oid funcid, Oid result_type, List *args, querytree->intoClause || querytree->hasAggs || querytree->hasSubLinks || + querytree->cteList || querytree->rtable || querytree->jointree->fromlist || querytree->jointree->quals || diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index 8e32895fb2..a922abcee8 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/util/pathnode.c,v 1.147 2008/09/05 21:07:29 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/util/pathnode.c,v 1.148 2008/10/04 21:56:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -1220,6 +1220,45 @@ create_valuesscan_path(PlannerInfo *root, RelOptInfo *rel) } /* + * create_ctescan_path + * Creates a path corresponding to a scan of a non-self-reference CTE, + * returning the pathnode. + */ +Path * +create_ctescan_path(PlannerInfo *root, RelOptInfo *rel) +{ + Path *pathnode = makeNode(Path); + + pathnode->pathtype = T_CteScan; + pathnode->parent = rel; + pathnode->pathkeys = NIL; /* XXX for now, result is always unordered */ + + cost_ctescan(pathnode, root, rel); + + return pathnode; +} + +/* + * create_worktablescan_path + * Creates a path corresponding to a scan of a self-reference CTE, + * returning the pathnode. + */ +Path * +create_worktablescan_path(PlannerInfo *root, RelOptInfo *rel) +{ + Path *pathnode = makeNode(Path); + + pathnode->pathtype = T_WorkTableScan; + pathnode->parent = rel; + pathnode->pathkeys = NIL; /* result is always unordered */ + + /* Cost is the same as for a regular CTE scan */ + cost_ctescan(pathnode, root, rel); + + return pathnode; +} + +/* * create_nestloop_path * Creates a pathnode corresponding to a nestloop join between two * relations. diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c index e6cd2f26b9..044cb8bbe6 100644 --- a/src/backend/optimizer/util/plancat.c +++ b/src/backend/optimizer/util/plancat.c @@ -9,7 +9,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/util/plancat.c,v 1.151 2008/09/01 20:42:44 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/util/plancat.c,v 1.152 2008/10/04 21:56:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -657,8 +657,8 @@ relation_excluded_by_constraints(PlannerInfo *root, * dropped cols. * * We also support building a "physical" tlist for subqueries, functions, - * and values lists, since the same optimization can occur in SubqueryScan, - * FunctionScan, and ValuesScan nodes. + * values lists, and CTEs, since the same optimization can occur in + * SubqueryScan, FunctionScan, ValuesScan, CteScan, and WorkTableScan nodes. */ List * build_physical_tlist(PlannerInfo *root, RelOptInfo *rel) @@ -733,6 +733,9 @@ build_physical_tlist(PlannerInfo *root, RelOptInfo *rel) break; case RTE_FUNCTION: + case RTE_VALUES: + case RTE_CTE: + /* Not all of these can have dropped cols, but share code anyway */ expandRTE(rte, varno, 0, -1, true /* include dropped */ , NULL, &colvars); foreach(l, colvars) @@ -757,21 +760,6 @@ build_physical_tlist(PlannerInfo *root, RelOptInfo *rel) } break; - case RTE_VALUES: - expandRTE(rte, varno, 0, -1, false /* dropped not applicable */ , - NULL, &colvars); - foreach(l, colvars) - { - var = (Var *) lfirst(l); - - tlist = lappend(tlist, - makeTargetEntry((Expr *) var, - var->varattno, - NULL, - false)); - } - break; - default: /* caller error */ elog(ERROR, "unsupported RTE kind %d in build_physical_tlist", diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c index f5592d17bb..2fb6cd2efe 100644 --- a/src/backend/optimizer/util/relnode.c +++ b/src/backend/optimizer/util/relnode.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/util/relnode.c,v 1.90 2008/08/14 18:47:59 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/util/relnode.c,v 1.91 2008/10/04 21:56:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -101,6 +101,7 @@ build_simple_rel(PlannerInfo *root, int relid, RelOptKind reloptkind) case RTE_SUBQUERY: case RTE_FUNCTION: case RTE_VALUES: + case RTE_CTE: /* * Subquery, function, or values list --- set up attr range and diff --git a/src/backend/parser/Makefile b/src/backend/parser/Makefile index 04b9ed61f4..8cefea14ac 100644 --- a/src/backend/parser/Makefile +++ b/src/backend/parser/Makefile @@ -2,7 +2,7 @@ # # Makefile for parser # -# $PostgreSQL: pgsql/src/backend/parser/Makefile,v 1.47 2008/08/29 13:02:32 petere Exp $ +# $PostgreSQL: pgsql/src/backend/parser/Makefile,v 1.48 2008/10/04 21:56:54 tgl Exp $ # #------------------------------------------------------------------------- @@ -12,7 +12,7 @@ include $(top_builddir)/src/Makefile.global override CPPFLAGS := -I$(srcdir) $(CPPFLAGS) -OBJS= analyze.o gram.o keywords.o parser.o parse_agg.o parse_clause.o \ +OBJS= analyze.o gram.o keywords.o parser.o parse_agg.o parse_cte.o parse_clause.o \ parse_expr.o parse_func.o parse_node.o parse_oper.o parse_relation.o \ parse_type.o parse_coerce.o parse_target.o parse_utilcmd.o scansup.o diff --git a/src/backend/parser/analyze.c b/src/backend/parser/analyze.c index 18585b860b..8934c04bb2 100644 --- a/src/backend/parser/analyze.c +++ b/src/backend/parser/analyze.c @@ -17,7 +17,7 @@ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/backend/parser/analyze.c,v 1.379 2008/09/01 20:42:44 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/parser/analyze.c,v 1.380 2008/10/04 21:56:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -32,6 +32,7 @@ #include "parser/parse_agg.h" #include "parser/parse_clause.h" #include "parser/parse_coerce.h" +#include "parser/parse_cte.h" #include "parser/parse_oper.h" #include "parser/parse_relation.h" #include "parser/parse_target.h" @@ -309,6 +310,8 @@ transformInsertStmt(ParseState *pstate, InsertStmt *stmt) pstate->p_relnamespace = NIL; sub_varnamespace = pstate->p_varnamespace; pstate->p_varnamespace = NIL; + /* There can't be any outer WITH to worry about */ + Assert(pstate->p_ctenamespace == NIL); } else { @@ -447,6 +450,13 @@ transformInsertStmt(ParseState *pstate, InsertStmt *stmt) List *exprsLists = NIL; int sublist_length = -1; + /* process the WITH clause */ + if (selectStmt->withClause) + { + qry->hasRecursive = selectStmt->withClause->recursive; + qry->cteList = transformWithClause(pstate, selectStmt->withClause); + } + foreach(lc, selectStmt->valuesLists) { List *sublist = (List *) lfirst(lc); @@ -540,6 +550,13 @@ transformInsertStmt(ParseState *pstate, InsertStmt *stmt) Assert(list_length(valuesLists) == 1); + /* process the WITH clause */ + if (selectStmt->withClause) + { + qry->hasRecursive = selectStmt->withClause->recursive; + qry->cteList = transformWithClause(pstate, selectStmt->withClause); + } + /* Do basic expression transformation (same as a ROW() expr) */ exprList = transformExpressionList(pstate, (List *) linitial(valuesLists)); @@ -694,6 +711,13 @@ transformSelectStmt(ParseState *pstate, SelectStmt *stmt) /* make FOR UPDATE/FOR SHARE info available to addRangeTableEntry */ pstate->p_locking_clause = stmt->lockingClause; + /* process the WITH clause */ + if (stmt->withClause) + { + qry->hasRecursive = stmt->withClause->recursive; + qry->cteList = transformWithClause(pstate, stmt->withClause); + } + /* process the FROM clause */ transformFromClause(pstate, stmt->fromClause); @@ -814,6 +838,13 @@ transformValuesClause(ParseState *pstate, SelectStmt *stmt) Assert(stmt->havingClause == NULL); Assert(stmt->op == SETOP_NONE); + /* process the WITH clause */ + if (stmt->withClause) + { + qry->hasRecursive = stmt->withClause->recursive; + qry->cteList = transformWithClause(pstate, stmt->withClause); + } + /* * For each row of VALUES, transform the raw expressions and gather type * information. This is also a handy place to reject DEFAULT nodes, which @@ -1059,6 +1090,13 @@ transformSetOperationStmt(ParseState *pstate, SelectStmt *stmt) (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), errmsg("SELECT FOR UPDATE/SHARE is not allowed with UNION/INTERSECT/EXCEPT"))); + /* process the WITH clause */ + if (stmt->withClause) + { + qry->hasRecursive = stmt->withClause->recursive; + qry->cteList = transformWithClause(pstate, stmt->withClause); + } + /* * Recursively transform the components of the tree. */ @@ -1101,21 +1139,22 @@ transformSetOperationStmt(ParseState *pstate, SelectStmt *stmt) TargetEntry *lefttle = (TargetEntry *) lfirst(left_tlist); char *colName; TargetEntry *tle; - Expr *expr; + Var *var; Assert(!lefttle->resjunk); colName = pstrdup(lefttle->resname); - expr = (Expr *) makeVar(leftmostRTI, - lefttle->resno, - colType, - colTypmod, - 0); - tle = makeTargetEntry(expr, + var = makeVar(leftmostRTI, + lefttle->resno, + colType, + colTypmod, + 0); + var->location = exprLocation((Node *) lefttle->expr); + tle = makeTargetEntry((Expr *) var, (AttrNumber) pstate->p_next_resno++, colName, false); qry->targetList = lappend(qry->targetList, tle); - targetvars = lappend(targetvars, expr); + targetvars = lappend(targetvars, var); targetnames = lappend(targetnames, makeString(colName)); left_tlist = lnext(left_tlist); } @@ -1841,6 +1880,30 @@ transformLockingClause(ParseState *pstate, Query *qry, LockingClause *lc) */ transformLockingClause(pstate, rte->subquery, allrels); break; + case RTE_CTE: + { + /* + * We allow FOR UPDATE/SHARE of a WITH query to be + * propagated into the WITH, but it doesn't seem + * very sane to allow this for a reference to an + * outer-level WITH. And it definitely wouldn't + * work for a self-reference, since we're not done + * analyzing the CTE anyway. + */ + CommonTableExpr *cte; + + if (rte->ctelevelsup > 0 || rte->self_reference) + ereport(ERROR, + (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), + errmsg("SELECT FOR UPDATE/SHARE cannot be applied to an outer-level WITH query"))); + cte = GetCTEForRTE(pstate, rte); + /* should be analyzed by now */ + Assert(IsA(cte->ctequery, Query)); + transformLockingClause(pstate, + (Query *) cte->ctequery, + allrels); + } + break; default: /* ignore JOIN, SPECIAL, FUNCTION RTEs */ break; @@ -1908,6 +1971,32 @@ transformLockingClause(ParseState *pstate, Query *qry, LockingClause *lc) errmsg("SELECT FOR UPDATE/SHARE cannot be applied to VALUES"), parser_errposition(pstate, thisrel->location))); break; + case RTE_CTE: + { + /* + * We allow FOR UPDATE/SHARE of a WITH query + * to be propagated into the WITH, but it + * doesn't seem very sane to allow this for a + * reference to an outer-level WITH. And it + * definitely wouldn't work for a + * self-reference, since we're not done + * analyzing the CTE anyway. + */ + CommonTableExpr *cte; + + if (rte->ctelevelsup > 0 || rte->self_reference) + ereport(ERROR, + (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), + errmsg("SELECT FOR UPDATE/SHARE cannot be applied to an outer-level WITH query"), + parser_errposition(pstate, thisrel->location))); + cte = GetCTEForRTE(pstate, rte); + /* should be analyzed by now */ + Assert(IsA(cte->ctequery, Query)); + transformLockingClause(pstate, + (Query *) cte->ctequery, + allrels); + } + break; default: elog(ERROR, "unrecognized RTE type: %d", (int) rte->rtekind); diff --git a/src/backend/parser/gram.y b/src/backend/parser/gram.y index d487e59fd7..5ee0699624 100644 --- a/src/backend/parser/gram.y +++ b/src/backend/parser/gram.y @@ -11,7 +11,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/parser/gram.y,v 2.624 2008/09/23 09:20:35 heikki Exp $ + * $PostgreSQL: pgsql/src/backend/parser/gram.y,v 2.625 2008/10/04 21:56:54 tgl Exp $ * * HISTORY * AUTHOR DATE MAJOR EVENT @@ -119,7 +119,8 @@ static List *extractArgTypes(List *parameters); static SelectStmt *findLeftmostSelect(SelectStmt *node); static void insertSelectOptions(SelectStmt *stmt, List *sortClause, List *lockingClause, - Node *limitOffset, Node *limitCount); + Node *limitOffset, Node *limitCount, + WithClause *withClause); static Node *makeSetOp(SetOperation op, bool all, Node *larg, Node *rarg); static Node *doNegate(Node *n, int location); static void doNegateFloat(Value *v); @@ -160,6 +161,7 @@ static TypeName *TableFuncTypeName(List *columns); Alias *alias; RangeVar *range; IntoClause *into; + WithClause *with; A_Indices *aind; ResTarget *target; PrivTarget *privtarget; @@ -377,6 +379,10 @@ static TypeName *TableFuncTypeName(List *columns); %type document_or_content %type xml_whitespace_option +%type common_table_expr +%type with_clause +%type cte_list + /* * If you make any token changes, update the keyword table in @@ -443,9 +449,9 @@ static TypeName *TableFuncTypeName(List *columns); QUOTE - READ REAL REASSIGN RECHECK REFERENCES REINDEX RELATIVE_P RELEASE RENAME - REPEATABLE REPLACE REPLICA RESET RESTART RESTRICT RETURNING RETURNS REVOKE - RIGHT ROLE ROLLBACK ROW ROWS RULE + READ REAL REASSIGN RECHECK RECURSIVE REFERENCES REINDEX RELATIVE_P RELEASE + RENAME REPEATABLE REPLACE REPLICA RESET RESTART RESTRICT RETURNING RETURNS + REVOKE RIGHT ROLE ROLLBACK ROW ROWS RULE SAVEPOINT SCHEMA SCROLL SEARCH SECOND_P SECURITY SELECT SEQUENCE SERIALIZABLE SESSION SESSION_USER SET SETOF SHARE @@ -6276,6 +6282,10 @@ select_with_parens: ; /* + * This rule parses the equivalent of the standard's . + * The duplicative productions are annoying, but hard to get rid of without + * creating shift/reduce conflicts. + * * FOR UPDATE/SHARE may be before or after LIMIT/OFFSET. * In <=7.2.X, LIMIT/OFFSET had to be after FOR UPDATE * We now support both orderings, but prefer LIMIT/OFFSET before FOR UPDATE/SHARE @@ -6286,21 +6296,51 @@ select_no_parens: | select_clause sort_clause { insertSelectOptions((SelectStmt *) $1, $2, NIL, - NULL, NULL); + NULL, NULL, NULL); $$ = $1; } | select_clause opt_sort_clause for_locking_clause opt_select_limit { insertSelectOptions((SelectStmt *) $1, $2, $3, - list_nth($4, 0), list_nth($4, 1)); + list_nth($4, 0), list_nth($4, 1), + NULL); $$ = $1; } | select_clause opt_sort_clause select_limit opt_for_locking_clause { insertSelectOptions((SelectStmt *) $1, $2, $4, - list_nth($3, 0), list_nth($3, 1)); + list_nth($3, 0), list_nth($3, 1), + NULL); $$ = $1; } + | with_clause simple_select + { + insertSelectOptions((SelectStmt *) $2, NULL, NIL, + NULL, NULL, + $1); + $$ = $2; + } + | with_clause select_clause sort_clause + { + insertSelectOptions((SelectStmt *) $2, $3, NIL, + NULL, NULL, + $1); + $$ = $2; + } + | with_clause select_clause opt_sort_clause for_locking_clause opt_select_limit + { + insertSelectOptions((SelectStmt *) $2, $3, $4, + list_nth($5, 0), list_nth($5, 1), + $1); + $$ = $2; + } + | with_clause select_clause opt_sort_clause select_limit opt_for_locking_clause + { + insertSelectOptions((SelectStmt *) $2, $3, $5, + list_nth($4, 0), list_nth($4, 1), + $1); + $$ = $2; + } ; select_clause: @@ -6323,10 +6363,10 @@ select_clause: * (SELECT foo UNION SELECT bar) ORDER BY baz * not * SELECT foo UNION (SELECT bar ORDER BY baz) - * Likewise FOR UPDATE and LIMIT. Therefore, those clauses are described - * as part of the select_no_parens production, not simple_select. - * This does not limit functionality, because you can reintroduce sort and - * limit clauses inside parentheses. + * Likewise for WITH, FOR UPDATE and LIMIT. Therefore, those clauses are + * described as part of the select_no_parens production, not simple_select. + * This does not limit functionality, because you can reintroduce these + * clauses inside parentheses. * * NOTE: only the leftmost component SelectStmt should have INTO. * However, this is not checked by the grammar; parse analysis must check it. @@ -6361,6 +6401,47 @@ simple_select: } ; +/* + * SQL standard WITH clause looks like: + * + * WITH [ RECURSIVE ] [ (,...) ] + * AS (query) [ SEARCH or CYCLE clause ] + * + * We don't currently support the SEARCH or CYCLE clause. + */ +with_clause: + WITH cte_list + { + $$ = makeNode(WithClause); + $$->ctes = $2; + $$->recursive = false; + $$->location = @1; + } + | WITH RECURSIVE cte_list + { + $$ = makeNode(WithClause); + $$->ctes = $3; + $$->recursive = true; + $$->location = @1; + } + ; + +cte_list: + common_table_expr { $$ = list_make1($1); } + | cte_list ',' common_table_expr { $$ = lappend($1, $3); } + ; + +common_table_expr: name opt_name_list AS select_with_parens + { + CommonTableExpr *n = makeNode(CommonTableExpr); + n->ctename = $1; + n->aliascolnames = $2; + n->ctequery = $4; + n->location = @1; + $$ = (Node *) n; + } + ; + into_clause: INTO OptTempTableName { @@ -9349,6 +9430,7 @@ unreserved_keyword: | READ | REASSIGN | RECHECK + | RECURSIVE | REINDEX | RELATIVE_P | RELEASE @@ -9416,7 +9498,6 @@ unreserved_keyword: | VIEW | VOLATILE | WHITESPACE_P - | WITH | WITHOUT | WORK | WRITE @@ -9599,6 +9680,7 @@ reserved_keyword: | VARIADIC | WHEN | WHERE + | WITH ; @@ -9922,8 +10004,11 @@ findLeftmostSelect(SelectStmt *node) static void insertSelectOptions(SelectStmt *stmt, List *sortClause, List *lockingClause, - Node *limitOffset, Node *limitCount) + Node *limitOffset, Node *limitCount, + WithClause *withClause) { + Assert(IsA(stmt, SelectStmt)); + /* * Tests here are to reject constructs like * (SELECT foo ORDER BY bar) ORDER BY baz @@ -9957,6 +10042,15 @@ insertSelectOptions(SelectStmt *stmt, scanner_errposition(exprLocation(limitCount)))); stmt->limitCount = limitCount; } + if (withClause) + { + if (stmt->withClause) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("multiple WITH clauses not allowed"), + scanner_errposition(exprLocation((Node *) withClause)))); + stmt->withClause = withClause; + } } static Node * diff --git a/src/backend/parser/keywords.c b/src/backend/parser/keywords.c index 0f17aa131e..c55bfd8b5c 100644 --- a/src/backend/parser/keywords.c +++ b/src/backend/parser/keywords.c @@ -11,7 +11,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/parser/keywords.c,v 1.201 2008/09/23 09:20:36 heikki Exp $ + * $PostgreSQL: pgsql/src/backend/parser/keywords.c,v 1.202 2008/10/04 21:56:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -305,6 +305,7 @@ const ScanKeyword ScanKeywords[] = { {"real", REAL, COL_NAME_KEYWORD}, {"reassign", REASSIGN, UNRESERVED_KEYWORD}, {"recheck", RECHECK, UNRESERVED_KEYWORD}, + {"recursive", RECURSIVE, UNRESERVED_KEYWORD}, {"references", REFERENCES, RESERVED_KEYWORD}, {"reindex", REINDEX, UNRESERVED_KEYWORD}, {"relative", RELATIVE_P, UNRESERVED_KEYWORD}, @@ -403,15 +404,6 @@ const ScanKeyword ScanKeywords[] = { {"when", WHEN, RESERVED_KEYWORD}, {"where", WHERE, RESERVED_KEYWORD}, {"whitespace", WHITESPACE_P, UNRESERVED_KEYWORD}, - - /* - * XXX we mark WITH as reserved to force it to be quoted in dumps, even - * though it is currently unreserved according to gram.y. This is because - * we expect we'll have to make it reserved to implement SQL WITH clauses. - * If that patch manages to do without reserving WITH, adjust this entry - * at that time; in any case this should be back in sync with gram.y after - * WITH clauses are implemented. - */ {"with", WITH, RESERVED_KEYWORD}, {"without", WITHOUT, UNRESERVED_KEYWORD}, {"work", WORK, UNRESERVED_KEYWORD}, diff --git a/src/backend/parser/parse_agg.c b/src/backend/parser/parse_agg.c index d85f64c7ab..e2645462d5 100644 --- a/src/backend/parser/parse_agg.c +++ b/src/backend/parser/parse_agg.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/parser/parse_agg.c,v 1.83 2008/09/01 20:42:44 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/parser/parse_agg.c,v 1.84 2008/10/04 21:56:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -102,6 +102,7 @@ parseCheckAggregates(ParseState *pstate, Query *qry) bool have_non_var_grouping; ListCell *l; bool hasJoinRTEs; + bool hasSelfRefRTEs; PlannerInfo *root; Node *clause; @@ -109,6 +110,21 @@ parseCheckAggregates(ParseState *pstate, Query *qry) Assert(pstate->p_hasAggs || qry->groupClause || qry->havingQual); /* + * Scan the range table to see if there are JOIN or self-reference CTE + * entries. We'll need this info below. + */ + hasJoinRTEs = hasSelfRefRTEs = false; + foreach(l, pstate->p_rtable) + { + RangeTblEntry *rte = (RangeTblEntry *) lfirst(l); + + if (rte->rtekind == RTE_JOIN) + hasJoinRTEs = true; + else if (rte->rtekind == RTE_CTE && rte->self_reference) + hasSelfRefRTEs = true; + } + + /* * Aggregates must never appear in WHERE or JOIN/ON clauses. * * (Note this check should appear first to deliver an appropriate error @@ -157,20 +173,6 @@ parseCheckAggregates(ParseState *pstate, Query *qry) * underlying vars, so that aliased and unaliased vars will be correctly * taken as equal. We can skip the expense of doing this if no rangetable * entries are RTE_JOIN kind. - */ - hasJoinRTEs = false; - foreach(l, pstate->p_rtable) - { - RangeTblEntry *rte = (RangeTblEntry *) lfirst(l); - - if (rte->rtekind == RTE_JOIN) - { - hasJoinRTEs = true; - break; - } - } - - /* * We use the planner's flatten_join_alias_vars routine to do the * flattening; it wants a PlannerInfo root node, which fortunately can be * mostly dummy. @@ -217,6 +219,16 @@ parseCheckAggregates(ParseState *pstate, Query *qry) clause = flatten_join_alias_vars(root, clause); check_ungrouped_columns(clause, pstate, groupClauses, have_non_var_grouping); + + /* + * Per spec, aggregates can't appear in a recursive term. + */ + if (pstate->p_hasAggs && hasSelfRefRTEs) + ereport(ERROR, + (errcode(ERRCODE_INVALID_RECURSION), + errmsg("aggregates not allowed in a recursive query's recursive term"), + parser_errposition(pstate, + locate_agg_of_level((Node *) qry, 0)))); } diff --git a/src/backend/parser/parse_clause.c b/src/backend/parser/parse_clause.c index 2f547f29be..dbf1775961 100644 --- a/src/backend/parser/parse_clause.c +++ b/src/backend/parser/parse_clause.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/parser/parse_clause.c,v 1.179 2008/09/01 20:42:44 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/parser/parse_clause.c,v 1.180 2008/10/04 21:56:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -54,6 +54,8 @@ static Node *transformJoinOnClause(ParseState *pstate, JoinExpr *j, List *relnamespace, Relids containedRels); static RangeTblEntry *transformTableEntry(ParseState *pstate, RangeVar *r); +static RangeTblEntry *transformCTEReference(ParseState *pstate, RangeVar *r, + CommonTableExpr *cte, Index levelsup); static RangeTblEntry *transformRangeSubselect(ParseState *pstate, RangeSubselect *r); static RangeTblEntry *transformRangeFunction(ParseState *pstate, @@ -422,6 +424,20 @@ transformTableEntry(ParseState *pstate, RangeVar *r) return rte; } +/* + * transformCTEReference --- transform a RangeVar that references a common + * table expression (ie, a sub-SELECT defined in a WITH clause) + */ +static RangeTblEntry * +transformCTEReference(ParseState *pstate, RangeVar *r, + CommonTableExpr *cte, Index levelsup) +{ + RangeTblEntry *rte; + + rte = addRangeTableEntryForCTE(pstate, cte, levelsup, r->alias, true); + + return rte; +} /* * transformRangeSubselect --- transform a sub-SELECT appearing in FROM @@ -609,12 +625,46 @@ transformFromClauseItem(ParseState *pstate, Node *n, { if (IsA(n, RangeVar)) { - /* Plain relation reference */ + /* Plain relation reference, or perhaps a CTE reference */ + RangeVar *rv = (RangeVar *) n; RangeTblRef *rtr; - RangeTblEntry *rte; + RangeTblEntry *rte = NULL; int rtindex; - rte = transformTableEntry(pstate, (RangeVar *) n); + /* + * If it is an unqualified name, it might be a reference to some + * CTE visible in this or a parent query. + */ + if (!rv->schemaname) + { + ParseState *ps; + Index levelsup; + + for (ps = pstate, levelsup = 0; + ps != NULL; + ps = ps->parentParseState, levelsup++) + { + ListCell *lc; + + foreach(lc, ps->p_ctenamespace) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + + if (strcmp(rv->relname, cte->ctename) == 0) + { + rte = transformCTEReference(pstate, rv, cte, levelsup); + break; + } + } + if (rte) + break; + } + } + + /* if not found as a CTE, must be a table reference */ + if (!rte) + rte = transformTableEntry(pstate, rv); + /* assume new rte is at end */ rtindex = list_length(pstate->p_rtable); Assert(rte == rt_fetch(rtindex, pstate->p_rtable)); diff --git a/src/backend/parser/parse_cte.c b/src/backend/parser/parse_cte.c new file mode 100644 index 0000000000..64f5e51c28 --- /dev/null +++ b/src/backend/parser/parse_cte.c @@ -0,0 +1,899 @@ +/*------------------------------------------------------------------------- + * + * parse_cte.c + * handle CTEs (common table expressions) in parser + * + * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * + * IDENTIFICATION + * $PostgreSQL: pgsql/src/backend/parser/parse_cte.c,v 2.1 2008/10/04 21:56:54 tgl Exp $ + * + *------------------------------------------------------------------------- + */ +#include "postgres.h" + +#include "nodes/nodeFuncs.h" +#include "parser/analyze.h" +#include "parser/parse_cte.h" +#include "utils/builtins.h" + + +/* Enumeration of contexts in which a self-reference is disallowed */ +typedef enum +{ + RECURSION_OK, + RECURSION_NONRECURSIVETERM, /* inside the left-hand term */ + RECURSION_SUBLINK, /* inside a sublink */ + RECURSION_OUTERJOIN, /* inside nullable side of an outer join */ + RECURSION_INTERSECT, /* underneath INTERSECT (ALL) */ + RECURSION_EXCEPT /* underneath EXCEPT (ALL) */ +} RecursionContext; + +/* Associated error messages --- each must have one %s for CTE name */ +static const char * const recursion_errormsgs[] = { + /* RECURSION_OK */ + NULL, + /* RECURSION_NONRECURSIVETERM */ + gettext_noop("recursive reference to query \"%s\" must not appear within its non-recursive term"), + /* RECURSION_SUBLINK */ + gettext_noop("recursive reference to query \"%s\" must not appear within a subquery"), + /* RECURSION_OUTERJOIN */ + gettext_noop("recursive reference to query \"%s\" must not appear within an outer join"), + /* RECURSION_INTERSECT */ + gettext_noop("recursive reference to query \"%s\" must not appear within INTERSECT"), + /* RECURSION_EXCEPT */ + gettext_noop("recursive reference to query \"%s\" must not appear within EXCEPT") +}; + +/* + * For WITH RECURSIVE, we have to find an ordering of the clause members + * with no forward references, and determine which members are recursive + * (i.e., self-referential). It is convenient to do this with an array + * of CteItems instead of a list of CommonTableExprs. + */ +typedef struct CteItem +{ + CommonTableExpr *cte; /* One CTE to examine */ + int id; /* Its ID number for dependencies */ + Node *non_recursive_term; /* Its nonrecursive part, if identified */ + Bitmapset *depends_on; /* CTEs depended on (not including self) */ +} CteItem; + +/* CteState is what we need to pass around in the tree walkers */ +typedef struct CteState +{ + /* global state: */ + ParseState *pstate; /* global parse state */ + CteItem *items; /* array of CTEs and extra data */ + int numitems; /* number of CTEs */ + /* working state during a tree walk: */ + int curitem; /* index of item currently being examined */ + List *innerwiths; /* list of lists of CommonTableExpr */ + /* working state for checkWellFormedRecursion walk only: */ + int selfrefcount; /* number of self-references detected */ + RecursionContext context; /* context to allow or disallow self-ref */ +} CteState; + + +static void analyzeCTE(ParseState *pstate, CommonTableExpr *cte); +static void analyzeCTETargetList(ParseState *pstate, CommonTableExpr *cte, List *tlist); + +/* Dependency processing functions */ +static void makeDependencyGraph(CteState *cstate); +static bool makeDependencyGraphWalker(Node *node, CteState *cstate); +static void TopologicalSort(ParseState *pstate, CteItem *items, int numitems); + +/* Recursion validity checker functions */ +static void checkWellFormedRecursion(CteState *cstate); +static bool checkWellFormedRecursionWalker(Node *node, CteState *cstate); +static void checkWellFormedSelectStmt(SelectStmt *stmt, CteState *cstate); + + +/* + * transformWithClause - + * Transform the list of WITH clause "common table expressions" into + * Query nodes. + * + * The result is the list of transformed CTEs to be put into the output + * Query. (This is in fact the same as the ending value of p_ctenamespace, + * but it seems cleaner to not expose that in the function's API.) + */ +List * +transformWithClause(ParseState *pstate, WithClause *withClause) +{ + ListCell *lc; + + /* Only one WITH clause per query level */ + Assert(pstate->p_ctenamespace == NIL); + + /* + * For either type of WITH, there must not be duplicate CTE names in + * the list. Check this right away so we needn't worry later. + * + * Also, tentatively mark each CTE as non-recursive, and initialize + * its reference count to zero. + */ + foreach(lc, withClause->ctes) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + ListCell *rest; + + for_each_cell(rest, lnext(lc)) + { + CommonTableExpr *cte2 = (CommonTableExpr *) lfirst(rest); + + if (strcmp(cte->ctename, cte2->ctename) == 0) + ereport(ERROR, + (errcode(ERRCODE_DUPLICATE_ALIAS), + errmsg("WITH query name \"%s\" specified more than once", + cte2->ctename), + parser_errposition(pstate, cte2->location))); + } + + cte->cterecursive = false; + cte->cterefcount = 0; + } + + if (withClause->recursive) + { + /* + * For WITH RECURSIVE, we rearrange the list elements if needed + * to eliminate forward references. First, build a work array + * and set up the data structure needed by the tree walkers. + */ + CteState cstate; + int i; + + cstate.pstate = pstate; + cstate.numitems = list_length(withClause->ctes); + cstate.items = (CteItem *) palloc0(cstate.numitems * sizeof(CteItem)); + i = 0; + foreach(lc, withClause->ctes) + { + cstate.items[i].cte = (CommonTableExpr *) lfirst(lc); + cstate.items[i].id = i; + i++; + } + + /* + * Find all the dependencies and sort the CteItems into a safe + * processing order. Also, mark CTEs that contain self-references. + */ + makeDependencyGraph(&cstate); + + /* + * Check that recursive queries are well-formed. + */ + checkWellFormedRecursion(&cstate); + + /* + * Set up the ctenamespace for parse analysis. Per spec, all + * the WITH items are visible to all others, so stuff them all in + * before parse analysis. We build the list in safe processing + * order so that the planner can process the queries in sequence. + */ + for (i = 0; i < cstate.numitems; i++) + { + CommonTableExpr *cte = cstate.items[i].cte; + + pstate->p_ctenamespace = lappend(pstate->p_ctenamespace, cte); + } + + /* + * Do parse analysis in the order determined by the topological sort. + */ + for (i = 0; i < cstate.numitems; i++) + { + CommonTableExpr *cte = cstate.items[i].cte; + + /* + * If it's recursive, we have to do a throwaway parse analysis + * of the non-recursive term in order to determine the set of + * output columns for the recursive CTE. + */ + if (cte->cterecursive) + { + Node *nrt; + Query *nrq; + + if (!cstate.items[i].non_recursive_term) + elog(ERROR, "could not find non-recursive term for %s", + cte->ctename); + /* copy the term to be sure we don't modify original query */ + nrt = copyObject(cstate.items[i].non_recursive_term); + nrq = parse_sub_analyze(nrt, pstate); + analyzeCTETargetList(pstate, cte, nrq->targetList); + } + + analyzeCTE(pstate, cte); + } + } + else + { + /* + * For non-recursive WITH, just analyze each CTE in sequence and then + * add it to the ctenamespace. This corresponds to the spec's + * definition of the scope of each WITH name. + */ + foreach(lc, withClause->ctes) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + + analyzeCTE(pstate, cte); + pstate->p_ctenamespace = lappend(pstate->p_ctenamespace, cte); + } + } + + return pstate->p_ctenamespace; +} + + +/* + * Perform the actual parse analysis transformation of one CTE. All + * CTEs it depends on have already been loaded into pstate->p_ctenamespace, + * and have been marked with the correct output column names/types. + */ +static void +analyzeCTE(ParseState *pstate, CommonTableExpr *cte) +{ + Query *query; + + /* Analysis not done already */ + Assert(IsA(cte->ctequery, SelectStmt)); + + query = parse_sub_analyze(cte->ctequery, pstate); + cte->ctequery = (Node *) query; + + /* + * Check that we got something reasonable. Many of these conditions are + * impossible given restrictions of the grammar, but check 'em anyway. + * (These are the same checks as in transformRangeSubselect.) + */ + if (!IsA(query, Query) || + query->commandType != CMD_SELECT || + query->utilityStmt != NULL) + elog(ERROR, "unexpected non-SELECT command in subquery in WITH"); + if (query->intoClause) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("subquery in WITH cannot have SELECT INTO"), + parser_errposition(pstate, + exprLocation((Node *) query->intoClause)))); + + if (!cte->cterecursive) + { + /* Compute the output column names/types if not done yet */ + analyzeCTETargetList(pstate, cte, query->targetList); + } + else + { + /* + * Verify that the previously determined output column types match + * what the query really produced. We have to check this because + * the recursive term could have overridden the non-recursive term, + * and we don't have any easy way to fix that. + */ + ListCell *lctlist, + *lctyp, + *lctypmod; + int varattno; + + lctyp = list_head(cte->ctecoltypes); + lctypmod = list_head(cte->ctecoltypmods); + varattno = 0; + foreach(lctlist, query->targetList) + { + TargetEntry *te = (TargetEntry *) lfirst(lctlist); + Node *texpr; + + if (te->resjunk) + continue; + varattno++; + Assert(varattno == te->resno); + if (lctyp == NULL || lctypmod == NULL) /* shouldn't happen */ + elog(ERROR, "wrong number of output columns in WITH"); + texpr = (Node *) te->expr; + if (exprType(texpr) != lfirst_oid(lctyp) || + exprTypmod(texpr) != lfirst_int(lctypmod)) + ereport(ERROR, + (errcode(ERRCODE_DATATYPE_MISMATCH), + errmsg("recursive query \"%s\" column %d has type %s in non-recursive term but type %s overall", + cte->ctename, varattno, + format_type_with_typemod(lfirst_oid(lctyp), + lfirst_int(lctypmod)), + format_type_with_typemod(exprType(texpr), + exprTypmod(texpr))), + errhint("Cast the output of the non-recursive term to the correct type."), + parser_errposition(pstate, exprLocation(texpr)))); + lctyp = lnext(lctyp); + lctypmod = lnext(lctypmod); + } + if (lctyp != NULL || lctypmod != NULL) /* shouldn't happen */ + elog(ERROR, "wrong number of output columns in WITH"); + } +} + +/* + * Compute derived fields of a CTE, given the transformed output targetlist + */ +static void +analyzeCTETargetList(ParseState *pstate, CommonTableExpr *cte, List *tlist) +{ + int numaliases; + int varattno; + ListCell *tlistitem; + + /* + * We need to determine column names and types. The alias column names + * override anything coming from the query itself. (Note: the SQL spec + * says that the alias list must be empty or exactly as long as the + * output column set; but we allow it to be shorter for consistency + * with Alias handling.) + */ + cte->ctecolnames = copyObject(cte->aliascolnames); + cte->ctecoltypes = cte->ctecoltypmods = NIL; + numaliases = list_length(cte->aliascolnames); + varattno = 0; + foreach(tlistitem, tlist) + { + TargetEntry *te = (TargetEntry *) lfirst(tlistitem); + + if (te->resjunk) + continue; + varattno++; + Assert(varattno == te->resno); + if (varattno > numaliases) + { + char *attrname; + + attrname = pstrdup(te->resname); + cte->ctecolnames = lappend(cte->ctecolnames, makeString(attrname)); + } + cte->ctecoltypes = lappend_oid(cte->ctecoltypes, + exprType((Node *) te->expr)); + cte->ctecoltypmods = lappend_int(cte->ctecoltypmods, + exprTypmod((Node *) te->expr)); + } + if (varattno < numaliases) + ereport(ERROR, + (errcode(ERRCODE_INVALID_COLUMN_REFERENCE), + errmsg("WITH query \"%s\" has %d columns available but %d columns specified", + cte->ctename, varattno, numaliases), + parser_errposition(pstate, cte->location))); +} + + +/* + * Identify the cross-references of a list of WITH RECURSIVE items, + * and sort into an order that has no forward references. + */ +static void +makeDependencyGraph(CteState *cstate) +{ + int i; + + for (i = 0; i < cstate->numitems; i++) + { + CommonTableExpr *cte = cstate->items[i].cte; + + cstate->curitem = i; + cstate->innerwiths = NIL; + makeDependencyGraphWalker((Node *) cte->ctequery, cstate); + Assert(cstate->innerwiths == NIL); + } + + TopologicalSort(cstate->pstate, cstate->items, cstate->numitems); +} + +/* + * Tree walker function to detect cross-references and self-references of the + * CTEs in a WITH RECURSIVE list. + */ +static bool +makeDependencyGraphWalker(Node *node, CteState *cstate) +{ + if (node == NULL) + return false; + if (IsA(node, RangeVar)) + { + RangeVar *rv = (RangeVar *) node; + + /* If unqualified name, might be a CTE reference */ + if (!rv->schemaname) + { + ListCell *lc; + int i; + + /* ... but first see if it's captured by an inner WITH */ + foreach(lc, cstate->innerwiths) + { + List *withlist = (List *) lfirst(lc); + ListCell *lc2; + + foreach(lc2, withlist) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc2); + + if (strcmp(rv->relname, cte->ctename) == 0) + return false; /* yes, so bail out */ + } + } + + /* No, could be a reference to the query level we are working on */ + for (i = 0; i < cstate->numitems; i++) + { + CommonTableExpr *cte = cstate->items[i].cte; + + if (strcmp(rv->relname, cte->ctename) == 0) + { + int myindex = cstate->curitem; + + if (i != myindex) + { + /* Add cross-item dependency */ + cstate->items[myindex].depends_on = + bms_add_member(cstate->items[myindex].depends_on, + cstate->items[i].id); + } + else + { + /* Found out this one is self-referential */ + cte->cterecursive = true; + } + break; + } + } + } + return false; + } + if (IsA(node, SelectStmt)) + { + SelectStmt *stmt = (SelectStmt *) node; + ListCell *lc; + + if (stmt->withClause) + { + if (stmt->withClause->recursive) + { + /* + * In the RECURSIVE case, all query names of the WITH are + * visible to all WITH items as well as the main query. + * So push them all on, process, pop them all off. + */ + cstate->innerwiths = lcons(stmt->withClause->ctes, + cstate->innerwiths); + foreach(lc, stmt->withClause->ctes) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + + (void) makeDependencyGraphWalker(cte->ctequery, cstate); + } + (void) raw_expression_tree_walker(node, + makeDependencyGraphWalker, + (void *) cstate); + cstate->innerwiths = list_delete_first(cstate->innerwiths); + } + else + { + /* + * In the non-RECURSIVE case, query names are visible to + * the WITH items after them and to the main query. + */ + ListCell *cell1; + + cstate->innerwiths = lcons(NIL, cstate->innerwiths); + cell1 = list_head(cstate->innerwiths); + foreach(lc, stmt->withClause->ctes) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + + (void) makeDependencyGraphWalker(cte->ctequery, cstate); + lfirst(cell1) = lappend((List *) lfirst(cell1), cte); + } + (void) raw_expression_tree_walker(node, + makeDependencyGraphWalker, + (void *) cstate); + cstate->innerwiths = list_delete_first(cstate->innerwiths); + } + /* We're done examining the SelectStmt */ + return false; + } + /* if no WITH clause, just fall through for normal processing */ + } + if (IsA(node, WithClause)) + { + /* + * Prevent raw_expression_tree_walker from recursing directly into + * a WITH clause. We need that to happen only under the control + * of the code above. + */ + return false; + } + return raw_expression_tree_walker(node, + makeDependencyGraphWalker, + (void *) cstate); +} + +/* + * Sort by dependencies, using a standard topological sort operation + */ +static void +TopologicalSort(ParseState *pstate, CteItem *items, int numitems) +{ + int i, j; + + /* for each position in sequence ... */ + for (i = 0; i < numitems; i++) + { + /* ... scan the remaining items to find one that has no dependencies */ + for (j = i; j < numitems; j++) + { + if (bms_is_empty(items[j].depends_on)) + break; + } + + /* if we didn't find one, the dependency graph has a cycle */ + if (j >= numitems) + ereport(ERROR, + (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), + errmsg("mutual recursion between WITH items is not implemented"), + parser_errposition(pstate, items[i].cte->location))); + + /* + * Found one. Move it to front and remove it from every other + * item's dependencies. + */ + if (i != j) + { + CteItem tmp; + + tmp = items[i]; + items[i] = items[j]; + items[j] = tmp; + } + /* + * Items up through i are known to have no dependencies left, + * so we can skip them in this loop. + */ + for (j = i + 1; j < numitems; j++) + { + items[j].depends_on = bms_del_member(items[j].depends_on, + items[i].id); + } + } +} + + +/* + * Check that recursive queries are well-formed. + */ +static void +checkWellFormedRecursion(CteState *cstate) +{ + int i; + + for (i = 0; i < cstate->numitems; i++) + { + CommonTableExpr *cte = cstate->items[i].cte; + SelectStmt *stmt = (SelectStmt *) cte->ctequery; + + Assert(IsA(stmt, SelectStmt)); /* not analyzed yet */ + + /* Ignore items that weren't found to be recursive */ + if (!cte->cterecursive) + continue; + + /* Must have top-level UNION ALL */ + if (stmt->op != SETOP_UNION || !stmt->all) + ereport(ERROR, + (errcode(ERRCODE_INVALID_RECURSION), + errmsg("recursive query \"%s\" does not have the form non-recursive-term UNION ALL recursive-term", + cte->ctename), + parser_errposition(cstate->pstate, cte->location))); + + /* The left-hand operand mustn't contain self-reference at all */ + cstate->curitem = i; + cstate->innerwiths = NIL; + cstate->selfrefcount = 0; + cstate->context = RECURSION_NONRECURSIVETERM; + checkWellFormedRecursionWalker((Node *) stmt->larg, cstate); + Assert(cstate->innerwiths == NIL); + + /* Right-hand operand should contain one reference in a valid place */ + cstate->curitem = i; + cstate->innerwiths = NIL; + cstate->selfrefcount = 0; + cstate->context = RECURSION_OK; + checkWellFormedRecursionWalker((Node *) stmt->rarg, cstate); + Assert(cstate->innerwiths == NIL); + if (cstate->selfrefcount != 1) /* shouldn't happen */ + elog(ERROR, "missing recursive reference"); + + /* + * Disallow ORDER BY and similar decoration atop the UNION ALL. + * These don't make sense because it's impossible to figure out what + * they mean when we have only part of the recursive query's results. + * (If we did allow them, we'd have to check for recursive references + * inside these subtrees.) + */ + if (stmt->sortClause) + ereport(ERROR, + (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), + errmsg("ORDER BY in a recursive query is not implemented"), + parser_errposition(cstate->pstate, + exprLocation((Node *) stmt->sortClause)))); + if (stmt->limitOffset) + ereport(ERROR, + (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), + errmsg("OFFSET in a recursive query is not implemented"), + parser_errposition(cstate->pstate, + exprLocation(stmt->limitOffset)))); + if (stmt->limitCount) + ereport(ERROR, + (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), + errmsg("LIMIT in a recursive query is not implemented"), + parser_errposition(cstate->pstate, + exprLocation(stmt->limitCount)))); + if (stmt->lockingClause) + ereport(ERROR, + (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), + errmsg("FOR UPDATE/SHARE in a recursive query is not implemented"), + parser_errposition(cstate->pstate, + exprLocation((Node *) stmt->lockingClause)))); + + /* + * Save non_recursive_term. + */ + cstate->items[i].non_recursive_term = (Node *) stmt->larg; + } +} + +/* + * Tree walker function to detect invalid self-references in a recursive query. + */ +static bool +checkWellFormedRecursionWalker(Node *node, CteState *cstate) +{ + RecursionContext save_context = cstate->context; + + if (node == NULL) + return false; + if (IsA(node, RangeVar)) + { + RangeVar *rv = (RangeVar *) node; + + /* If unqualified name, might be a CTE reference */ + if (!rv->schemaname) + { + ListCell *lc; + CommonTableExpr *mycte; + + /* ... but first see if it's captured by an inner WITH */ + foreach(lc, cstate->innerwiths) + { + List *withlist = (List *) lfirst(lc); + ListCell *lc2; + + foreach(lc2, withlist) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc2); + + if (strcmp(rv->relname, cte->ctename) == 0) + return false; /* yes, so bail out */ + } + } + + /* No, could be a reference to the query level we are working on */ + mycte = cstate->items[cstate->curitem].cte; + if (strcmp(rv->relname, mycte->ctename) == 0) + { + /* Found a recursive reference to the active query */ + if (cstate->context != RECURSION_OK) + ereport(ERROR, + (errcode(ERRCODE_INVALID_RECURSION), + errmsg(recursion_errormsgs[cstate->context], + mycte->ctename), + parser_errposition(cstate->pstate, + rv->location))); + /* Count references */ + if (++(cstate->selfrefcount) > 1) + ereport(ERROR, + (errcode(ERRCODE_INVALID_RECURSION), + errmsg("recursive reference to query \"%s\" must not appear more than once", + mycte->ctename), + parser_errposition(cstate->pstate, + rv->location))); + } + } + return false; + } + if (IsA(node, SelectStmt)) + { + SelectStmt *stmt = (SelectStmt *) node; + ListCell *lc; + + if (stmt->withClause) + { + if (stmt->withClause->recursive) + { + /* + * In the RECURSIVE case, all query names of the WITH are + * visible to all WITH items as well as the main query. + * So push them all on, process, pop them all off. + */ + cstate->innerwiths = lcons(stmt->withClause->ctes, + cstate->innerwiths); + foreach(lc, stmt->withClause->ctes) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + + (void) checkWellFormedRecursionWalker(cte->ctequery, cstate); + } + checkWellFormedSelectStmt(stmt, cstate); + cstate->innerwiths = list_delete_first(cstate->innerwiths); + } + else + { + /* + * In the non-RECURSIVE case, query names are visible to + * the WITH items after them and to the main query. + */ + ListCell *cell1; + + cstate->innerwiths = lcons(NIL, cstate->innerwiths); + cell1 = list_head(cstate->innerwiths); + foreach(lc, stmt->withClause->ctes) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + + (void) checkWellFormedRecursionWalker(cte->ctequery, cstate); + lfirst(cell1) = lappend((List *) lfirst(cell1), cte); + } + checkWellFormedSelectStmt(stmt, cstate); + cstate->innerwiths = list_delete_first(cstate->innerwiths); + } + } + else + checkWellFormedSelectStmt(stmt, cstate); + /* We're done examining the SelectStmt */ + return false; + } + if (IsA(node, WithClause)) + { + /* + * Prevent raw_expression_tree_walker from recursing directly into + * a WITH clause. We need that to happen only under the control + * of the code above. + */ + return false; + } + if (IsA(node, JoinExpr)) + { + JoinExpr *j = (JoinExpr *) node; + + switch (j->jointype) + { + case JOIN_INNER: + checkWellFormedRecursionWalker(j->larg, cstate); + checkWellFormedRecursionWalker(j->rarg, cstate); + checkWellFormedRecursionWalker(j->quals, cstate); + break; + case JOIN_LEFT: + checkWellFormedRecursionWalker(j->larg, cstate); + if (save_context == RECURSION_OK) + cstate->context = RECURSION_OUTERJOIN; + checkWellFormedRecursionWalker(j->rarg, cstate); + cstate->context = save_context; + checkWellFormedRecursionWalker(j->quals, cstate); + break; + case JOIN_FULL: + if (save_context == RECURSION_OK) + cstate->context = RECURSION_OUTERJOIN; + checkWellFormedRecursionWalker(j->larg, cstate); + checkWellFormedRecursionWalker(j->rarg, cstate); + cstate->context = save_context; + checkWellFormedRecursionWalker(j->quals, cstate); + break; + case JOIN_RIGHT: + if (save_context == RECURSION_OK) + cstate->context = RECURSION_OUTERJOIN; + checkWellFormedRecursionWalker(j->larg, cstate); + cstate->context = save_context; + checkWellFormedRecursionWalker(j->rarg, cstate); + checkWellFormedRecursionWalker(j->quals, cstate); + break; + default: + elog(ERROR, "unrecognized join type: %d", + (int) j->jointype); + } + return false; + } + if (IsA(node, SubLink)) + { + SubLink *sl = (SubLink *) node; + + /* + * we intentionally override outer context, since subquery is + * independent + */ + cstate->context = RECURSION_SUBLINK; + checkWellFormedRecursionWalker(sl->subselect, cstate); + cstate->context = save_context; + checkWellFormedRecursionWalker(sl->testexpr, cstate); + return false; + } + return raw_expression_tree_walker(node, + checkWellFormedRecursionWalker, + (void *) cstate); +} + +/* + * subroutine for checkWellFormedRecursionWalker: process a SelectStmt + * without worrying about its WITH clause + */ +static void +checkWellFormedSelectStmt(SelectStmt *stmt, CteState *cstate) +{ + RecursionContext save_context = cstate->context; + + if (save_context != RECURSION_OK) + { + /* just recurse without changing state */ + raw_expression_tree_walker((Node *) stmt, + checkWellFormedRecursionWalker, + (void *) cstate); + } + else + { + switch (stmt->op) + { + case SETOP_NONE: + case SETOP_UNION: + raw_expression_tree_walker((Node *) stmt, + checkWellFormedRecursionWalker, + (void *) cstate); + break; + case SETOP_INTERSECT: + if (stmt->all) + cstate->context = RECURSION_INTERSECT; + checkWellFormedRecursionWalker((Node *) stmt->larg, + cstate); + checkWellFormedRecursionWalker((Node *) stmt->rarg, + cstate); + cstate->context = save_context; + checkWellFormedRecursionWalker((Node *) stmt->sortClause, + cstate); + checkWellFormedRecursionWalker((Node *) stmt->limitOffset, + cstate); + checkWellFormedRecursionWalker((Node *) stmt->limitCount, + cstate); + checkWellFormedRecursionWalker((Node *) stmt->lockingClause, + cstate); + break; + break; + case SETOP_EXCEPT: + if (stmt->all) + cstate->context = RECURSION_EXCEPT; + checkWellFormedRecursionWalker((Node *) stmt->larg, + cstate); + cstate->context = RECURSION_EXCEPT; + checkWellFormedRecursionWalker((Node *) stmt->rarg, + cstate); + cstate->context = save_context; + checkWellFormedRecursionWalker((Node *) stmt->sortClause, + cstate); + checkWellFormedRecursionWalker((Node *) stmt->limitOffset, + cstate); + checkWellFormedRecursionWalker((Node *) stmt->limitCount, + cstate); + checkWellFormedRecursionWalker((Node *) stmt->lockingClause, + cstate); + break; + default: + elog(ERROR, "unrecognized set op: %d", + (int) stmt->op); + } + } +} diff --git a/src/backend/parser/parse_relation.c b/src/backend/parser/parse_relation.c index 6accd96f0d..fa2da35c6b 100644 --- a/src/backend/parser/parse_relation.c +++ b/src/backend/parser/parse_relation.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/parser/parse_relation.c,v 1.135 2008/09/01 20:42:44 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/parser/parse_relation.c,v 1.136 2008/10/04 21:56:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -319,6 +319,35 @@ GetRTEByRangeTablePosn(ParseState *pstate, } /* + * Fetch the CTE for a CTE-reference RTE. + */ +CommonTableExpr * +GetCTEForRTE(ParseState *pstate, RangeTblEntry *rte) +{ + Index levelsup; + ListCell *lc; + + Assert(rte->rtekind == RTE_CTE); + levelsup = rte->ctelevelsup; + while (levelsup-- > 0) + { + pstate = pstate->parentParseState; + if (!pstate) /* shouldn't happen */ + elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename); + } + foreach(lc, pstate->p_ctenamespace) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + + if (strcmp(cte->ctename, rte->ctename) == 0) + return cte; + } + /* shouldn't happen */ + elog(ERROR, "could not find CTE \"%s\"", rte->ctename); + return NULL; /* keep compiler quiet */ +} + +/* * scanRTEForColumn * Search the column names of a single RTE for the given name. * If found, return an appropriate Var node, else return NULL. @@ -1109,6 +1138,88 @@ addRangeTableEntryForJoin(ParseState *pstate, } /* + * Add an entry for a CTE reference to the pstate's range table (p_rtable). + * + * This is much like addRangeTableEntry() except that it makes a CTE RTE. + */ +RangeTblEntry * +addRangeTableEntryForCTE(ParseState *pstate, + CommonTableExpr *cte, + Index levelsup, + Alias *alias, + bool inFromCl) +{ + RangeTblEntry *rte = makeNode(RangeTblEntry); + char *refname = alias ? alias->aliasname : cte->ctename; + Alias *eref; + int numaliases; + int varattno; + ListCell *lc; + + rte->rtekind = RTE_CTE; + rte->ctename = cte->ctename; + rte->ctelevelsup = levelsup; + + /* Self-reference if and only if CTE's parse analysis isn't completed */ + rte->self_reference = !IsA(cte->ctequery, Query); + Assert(cte->cterecursive || !rte->self_reference); + /* Bump the CTE's refcount if this isn't a self-reference */ + if (!rte->self_reference) + cte->cterefcount++; + + rte->ctecoltypes = cte->ctecoltypes; + rte->ctecoltypmods = cte->ctecoltypmods; + + rte->alias = alias; + if (alias) + eref = copyObject(alias); + else + eref = makeAlias(refname, NIL); + numaliases = list_length(eref->colnames); + + /* fill in any unspecified alias columns */ + varattno = 0; + foreach(lc, cte->ctecolnames) + { + varattno++; + if (varattno > numaliases) + eref->colnames = lappend(eref->colnames, lfirst(lc)); + } + if (varattno < numaliases) + ereport(ERROR, + (errcode(ERRCODE_INVALID_COLUMN_REFERENCE), + errmsg("table \"%s\" has %d columns available but %d columns specified", + refname, varattno, numaliases))); + + rte->eref = eref; + + /*---------- + * Flags: + * - this RTE should be expanded to include descendant tables, + * - this RTE is in the FROM clause, + * - this RTE should be checked for appropriate access rights. + * + * Subqueries are never checked for access rights. + *---------- + */ + rte->inh = false; /* never true for subqueries */ + rte->inFromCl = inFromCl; + + rte->requiredPerms = 0; + rte->checkAsUser = InvalidOid; + + /* + * Add completed RTE to pstate's range table list, but not to join list + * nor namespace --- caller must do that if appropriate. + */ + if (pstate != NULL) + pstate->p_rtable = lappend(pstate->p_rtable, rte); + + return rte; +} + + +/* * Has the specified refname been selected FOR UPDATE/FOR SHARE? * * Note: we pay no attention to whether it's FOR UPDATE vs FOR SHARE. @@ -1444,6 +1555,41 @@ expandRTE(RangeTblEntry *rte, int rtindex, int sublevels_up, } } break; + case RTE_CTE: + { + ListCell *aliasp_item = list_head(rte->eref->colnames); + ListCell *lct; + ListCell *lcm; + + varattno = 0; + forboth(lct, rte->ctecoltypes, lcm, rte->ctecoltypmods) + { + Oid coltype = lfirst_oid(lct); + int32 coltypmod = lfirst_int(lcm); + + varattno++; + + if (colnames) + { + /* Assume there is one alias per output column */ + char *label = strVal(lfirst(aliasp_item)); + + *colnames = lappend(*colnames, makeString(pstrdup(label))); + aliasp_item = lnext(aliasp_item); + } + + if (colvars) + { + Var *varnode; + + varnode = makeVar(rtindex, varattno, + coltype, coltypmod, + sublevels_up); + *colvars = lappend(*colvars, varnode); + } + } + } + break; default: elog(ERROR, "unrecognized RTE kind: %d", (int) rte->rtekind); } @@ -1750,6 +1896,14 @@ get_rte_attribute_type(RangeTblEntry *rte, AttrNumber attnum, *vartypmod = exprTypmod(aliasvar); } break; + case RTE_CTE: + { + /* CTE RTE --- get type info from lists in the RTE */ + Assert(attnum > 0 && attnum <= list_length(rte->ctecoltypes)); + *vartype = list_nth_oid(rte->ctecoltypes, attnum - 1); + *vartypmod = list_nth_int(rte->ctecoltypmods, attnum - 1); + } + break; default: elog(ERROR, "unrecognized RTE kind: %d", (int) rte->rtekind); } @@ -1788,7 +1942,8 @@ get_rte_attribute_is_dropped(RangeTblEntry *rte, AttrNumber attnum) break; case RTE_SUBQUERY: case RTE_VALUES: - /* Subselect and Values RTEs never have dropped columns */ + case RTE_CTE: + /* Subselect, Values, CTE RTEs never have dropped columns */ result = false; break; case RTE_JOIN: diff --git a/src/backend/parser/parse_target.c b/src/backend/parser/parse_target.c index 20d91a142f..3ead26194e 100644 --- a/src/backend/parser/parse_target.c +++ b/src/backend/parser/parse_target.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/parser/parse_target.c,v 1.164 2008/09/01 20:42:44 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/parser/parse_target.c,v 1.165 2008/10/04 21:56:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -296,6 +296,24 @@ markTargetListOrigin(ParseState *pstate, TargetEntry *tle, case RTE_VALUES: /* not a simple relation, leave it unmarked */ break; + case RTE_CTE: + /* CTE reference: copy up from the subquery */ + if (attnum != InvalidAttrNumber) + { + CommonTableExpr *cte = GetCTEForRTE(pstate, rte); + TargetEntry *ste; + + /* should be analyzed by now */ + Assert(IsA(cte->ctequery, Query)); + ste = get_tle_by_resno(((Query *) cte->ctequery)->targetList, + attnum); + if (ste == NULL || ste->resjunk) + elog(ERROR, "subquery %s does not have attribute %d", + rte->eref->aliasname, attnum); + tle->resorigtbl = ste->resorigtbl; + tle->resorigcol = ste->resorigcol; + } + break; } } @@ -1176,6 +1194,44 @@ expandRecordVariable(ParseState *pstate, Var *var, int levelsup) * its result columns as RECORD, which is not allowed. */ break; + case RTE_CTE: + { + /* CTE reference: examine subquery's output expr */ + CommonTableExpr *cte = GetCTEForRTE(pstate, rte); + TargetEntry *ste; + + /* should be analyzed by now */ + Assert(IsA(cte->ctequery, Query)); + ste = get_tle_by_resno(((Query *) cte->ctequery)->targetList, + attnum); + if (ste == NULL || ste->resjunk) + elog(ERROR, "subquery %s does not have attribute %d", + rte->eref->aliasname, attnum); + expr = (Node *) ste->expr; + if (IsA(expr, Var)) + { + /* + * Recurse into the CTE to see what its Var refers to. We + * have to build an additional level of ParseState to keep + * in step with varlevelsup in the CTE; furthermore it + * could be an outer CTE. + */ + ParseState mypstate; + Index levelsup; + + MemSet(&mypstate, 0, sizeof(mypstate)); + /* this loop must work, since GetCTEForRTE did */ + for (levelsup = 0; levelsup < rte->ctelevelsup; levelsup++) + pstate = pstate->parentParseState; + mypstate.parentParseState = pstate; + mypstate.p_rtable = ((Query *) cte->ctequery)->rtable; + /* don't bother filling the rest of the fake pstate */ + + return expandRecordVariable(&mypstate, (Var *) expr, 0); + } + /* else fall through to inspect the expression */ + } + break; } /* diff --git a/src/backend/parser/parse_type.c b/src/backend/parser/parse_type.c index 960542029f..0253cfe159 100644 --- a/src/backend/parser/parse_type.c +++ b/src/backend/parser/parse_type.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/parser/parse_type.c,v 1.99 2008/09/01 20:42:45 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/parser/parse_type.c,v 1.100 2008/10/04 21:56:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -611,6 +611,7 @@ parseTypeString(const char *str, Oid *type_id, int32 *typmod_p) stmt->whereClause != NULL || stmt->groupClause != NIL || stmt->havingClause != NULL || + stmt->withClause != NULL || stmt->valuesLists != NIL || stmt->sortClause != NIL || stmt->limitOffset != NULL || diff --git a/src/backend/rewrite/rewriteDefine.c b/src/backend/rewrite/rewriteDefine.c index 7ca90a5485..75653240c9 100644 --- a/src/backend/rewrite/rewriteDefine.c +++ b/src/backend/rewrite/rewriteDefine.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/rewrite/rewriteDefine.c,v 1.129 2008/08/25 22:42:34 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/rewrite/rewriteDefine.c,v 1.130 2008/10/04 21:56:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -635,17 +635,23 @@ setRuleCheckAsUser_Query(Query *qry, Oid userid) rte->checkAsUser = userid; } + /* Recurse into subquery-in-WITH */ + foreach(l, qry->cteList) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(l); + + setRuleCheckAsUser_Query((Query *) cte->ctequery, userid); + } + /* If there are sublinks, search for them and process their RTEs */ - /* ignore subqueries in rtable because we already processed them */ if (qry->hasSubLinks) query_tree_walker(qry, setRuleCheckAsUser_walker, (void *) &userid, - QTW_IGNORE_RT_SUBQUERIES); + QTW_IGNORE_RC_SUBQUERIES); } /* * Change the firing semantics of an existing rule. - * */ void EnableDisableRule(Relation rel, const char *rulename, diff --git a/src/backend/rewrite/rewriteHandler.c b/src/backend/rewrite/rewriteHandler.c index 305b91202a..f07be31e3a 100644 --- a/src/backend/rewrite/rewriteHandler.c +++ b/src/backend/rewrite/rewriteHandler.c @@ -7,7 +7,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/rewrite/rewriteHandler.c,v 1.180 2008/09/24 16:52:46 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/rewrite/rewriteHandler.c,v 1.181 2008/10/04 21:56:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -215,13 +215,21 @@ AcquireRewriteLocks(Query *parsetree) } } + /* Recurse into subqueries in WITH */ + foreach(l, parsetree->cteList) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(l); + + AcquireRewriteLocks((Query *) cte->ctequery); + } + /* * Recurse into sublink subqueries, too. But we already did the ones in - * the rtable. + * the rtable and cteList. */ if (parsetree->hasSubLinks) query_tree_walker(parsetree, acquireLocksOnSubLinks, NULL, - QTW_IGNORE_RT_SUBQUERIES); + QTW_IGNORE_RC_SUBQUERIES); } /* @@ -1228,6 +1236,35 @@ markQueryForLocking(Query *qry, Node *jtnode, bool forUpdate, bool noWait) markQueryForLocking(rte->subquery, (Node *) rte->subquery->jointree, forUpdate, noWait); } + else if (rte->rtekind == RTE_CTE) + { + /* + * We allow FOR UPDATE/SHARE of a WITH query to be propagated into + * the WITH, but it doesn't seem very sane to allow this for a + * reference to an outer-level WITH (compare + * transformLockingClause). Which simplifies life here. + */ + CommonTableExpr *cte = NULL; + ListCell *lc; + + if (rte->ctelevelsup > 0 || rte->self_reference) + ereport(ERROR, + (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), + errmsg("SELECT FOR UPDATE/SHARE cannot be applied to an outer-level WITH query"))); + foreach(lc, qry->cteList) + { + cte = (CommonTableExpr *) lfirst(lc); + if (strcmp(cte->ctename, rte->ctename) == 0) + break; + } + if (lc == NULL) /* shouldn't happen */ + elog(ERROR, "could not find CTE \"%s\"", rte->ctename); + /* should be analyzed by now */ + Assert(IsA(cte->ctequery, Query)); + markQueryForLocking((Query *) cte->ctequery, + (Node *) ((Query *) cte->ctequery)->jointree, + forUpdate, noWait); + } } else if (IsA(jtnode, FromExpr)) { @@ -1295,6 +1332,7 @@ static Query * fireRIRrules(Query *parsetree, List *activeRIRs) { int rt_index; + ListCell *lc; /* * don't try to convert this into a foreach loop, because rtable list can @@ -1407,13 +1445,22 @@ fireRIRrules(Query *parsetree, List *activeRIRs) heap_close(rel, NoLock); } + /* Recurse into subqueries in WITH */ + foreach(lc, parsetree->cteList) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + + cte->ctequery = (Node *) + fireRIRrules((Query *) cte->ctequery, activeRIRs); + } + /* * Recurse into sublink subqueries, too. But we already did the ones in - * the rtable. + * the rtable and cteList. */ if (parsetree->hasSubLinks) query_tree_walker(parsetree, fireRIRonSubLink, (void *) activeRIRs, - QTW_IGNORE_RT_SUBQUERIES); + QTW_IGNORE_RC_SUBQUERIES); return parsetree; } diff --git a/src/backend/rewrite/rewriteManip.c b/src/backend/rewrite/rewriteManip.c index c8652ff5f2..b5d82dd0e7 100644 --- a/src/backend/rewrite/rewriteManip.c +++ b/src/backend/rewrite/rewriteManip.c @@ -7,7 +7,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/rewrite/rewriteManip.c,v 1.113 2008/09/01 20:42:45 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/rewrite/rewriteManip.c,v 1.114 2008/10/04 21:56:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -183,13 +183,13 @@ bool checkExprHasSubLink(Node *node) { /* - * If a Query is passed, examine it --- but we need not recurse into - * sub-Queries. + * If a Query is passed, examine it --- but we should not recurse into + * sub-Queries that are in its rangetable or CTE list. */ return query_or_expression_tree_walker(node, checkExprHasSubLink_walker, NULL, - QTW_IGNORE_RT_SUBQUERIES); + QTW_IGNORE_RC_SUBQUERIES); } static bool @@ -543,7 +543,7 @@ adjust_relid_set(Relids relids, int oldrelid, int newrelid) * that sublink are not affected, only outer references to vars that belong * to the expression's original query level or parents thereof. * - * Aggref nodes are adjusted similarly. + * Likewise for other nodes containing levelsup fields, such as Aggref. * * NOTE: although this has the form of a walker, we cheat and modify the * Var nodes in-place. The given expression tree should have been copied @@ -585,6 +585,17 @@ IncrementVarSublevelsUp_walker(Node *node, agg->agglevelsup += context->delta_sublevels_up; /* fall through to recurse into argument */ } + if (IsA(node, RangeTblEntry)) + { + RangeTblEntry *rte = (RangeTblEntry *) node; + + if (rte->rtekind == RTE_CTE) + { + if (rte->ctelevelsup >= context->min_sublevels_up) + rte->ctelevelsup += context->delta_sublevels_up; + } + return false; /* allow range_table_walker to continue */ + } if (IsA(node, Query)) { /* Recurse into subselects */ @@ -593,7 +604,8 @@ IncrementVarSublevelsUp_walker(Node *node, context->min_sublevels_up++; result = query_tree_walker((Query *) node, IncrementVarSublevelsUp_walker, - (void *) context, 0); + (void *) context, + QTW_EXAMINE_RTES); context->min_sublevels_up--; return result; } @@ -617,7 +629,7 @@ IncrementVarSublevelsUp(Node *node, int delta_sublevels_up, query_or_expression_tree_walker(node, IncrementVarSublevelsUp_walker, (void *) &context, - 0); + QTW_EXAMINE_RTES); } /* @@ -636,7 +648,7 @@ IncrementVarSublevelsUp_rtable(List *rtable, int delta_sublevels_up, range_table_walker(rtable, IncrementVarSublevelsUp_walker, (void *) &context, - 0); + QTW_EXAMINE_RTES); } diff --git a/src/backend/utils/adt/ruleutils.c b/src/backend/utils/adt/ruleutils.c index 71fea45ddd..fd21152b49 100644 --- a/src/backend/utils/adt/ruleutils.c +++ b/src/backend/utils/adt/ruleutils.c @@ -9,7 +9,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/utils/adt/ruleutils.c,v 1.284 2008/09/06 20:18:08 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/utils/adt/ruleutils.c,v 1.285 2008/10/04 21:56:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -145,6 +145,7 @@ static void make_viewdef(StringInfo buf, HeapTuple ruletup, TupleDesc rulettc, static void get_query_def(Query *query, StringInfo buf, List *parentnamespace, TupleDesc resultDesc, int prettyFlags, int startIndent); static void get_values_def(List *values_lists, deparse_context *context); +static void get_with_clause(Query *query, deparse_context *context); static void get_select_query_def(Query *query, deparse_context *context, TupleDesc resultDesc); static void get_insert_query_def(Query *query, deparse_context *context); @@ -2205,6 +2206,73 @@ get_values_def(List *values_lists, deparse_context *context) } /* ---------- + * get_with_clause - Parse back a WITH clause + * ---------- + */ +static void +get_with_clause(Query *query, deparse_context *context) +{ + StringInfo buf = context->buf; + const char *sep; + ListCell *l; + + if (query->cteList == NIL) + return; + + if (PRETTY_INDENT(context)) + { + context->indentLevel += PRETTYINDENT_STD; + appendStringInfoChar(buf, ' '); + } + + if (query->hasRecursive) + sep = "WITH RECURSIVE "; + else + sep = "WITH "; + foreach(l, query->cteList) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(l); + + appendStringInfoString(buf, sep); + appendStringInfoString(buf, quote_identifier(cte->ctename)); + if (cte->aliascolnames) + { + bool first = true; + ListCell *col; + + appendStringInfoChar(buf, '('); + foreach(col, cte->aliascolnames) + { + if (first) + first = false; + else + appendStringInfoString(buf, ", "); + appendStringInfoString(buf, + quote_identifier(strVal(lfirst(col)))); + } + appendStringInfoChar(buf, ')'); + } + appendStringInfoString(buf, " AS ("); + if (PRETTY_INDENT(context)) + appendContextKeyword(context, "", 0, 0, 0); + get_query_def((Query *) cte->ctequery, buf, context->namespaces, NULL, + context->prettyFlags, context->indentLevel); + if (PRETTY_INDENT(context)) + appendContextKeyword(context, "", 0, 0, 0); + appendStringInfoChar(buf, ')'); + sep = ", "; + } + + if (PRETTY_INDENT(context)) + { + context->indentLevel -= PRETTYINDENT_STD; + appendContextKeyword(context, "", 0, 0, 0); + } + else + appendStringInfoChar(buf, ' '); +} + +/* ---------- * get_select_query_def - Parse back a SELECT parsetree * ---------- */ @@ -2214,13 +2282,16 @@ get_select_query_def(Query *query, deparse_context *context, { StringInfo buf = context->buf; bool force_colno; - char *sep; + const char *sep; ListCell *l; + /* Insert the WITH clause if given */ + get_with_clause(query, context); + /* * If the Query node has a setOperations tree, then it's the top level of - * a UNION/INTERSECT/EXCEPT query; only the ORDER BY and LIMIT fields are - * interesting in the top query itself. + * a UNION/INTERSECT/EXCEPT query; only the WITH, ORDER BY and LIMIT + * fields are interesting in the top query itself. */ if (query->setOperations) { @@ -2507,8 +2578,9 @@ get_setop_query(Node *setOp, Query *query, deparse_context *context, Assert(subquery != NULL); Assert(subquery->setOperations == NULL); - /* Need parens if ORDER BY, FOR UPDATE, or LIMIT; see gram.y */ - need_paren = (subquery->sortClause || + /* Need parens if WITH, ORDER BY, FOR UPDATE, or LIMIT; see gram.y */ + need_paren = (subquery->cteList || + subquery->sortClause || subquery->rowMarks || subquery->limitOffset || subquery->limitCount); @@ -2523,6 +2595,12 @@ get_setop_query(Node *setOp, Query *query, deparse_context *context, { SetOperationStmt *op = (SetOperationStmt *) setOp; + if (PRETTY_INDENT(context)) + { + context->indentLevel += PRETTYINDENT_STD; + appendStringInfoSpaces(buf, PRETTYINDENT_STD); + } + /* * We force parens whenever nesting two SetOperationStmts. There are * some cases in which parens are needed around a leaf query too, but @@ -2570,6 +2648,9 @@ get_setop_query(Node *setOp, Query *query, deparse_context *context, get_setop_query(op->rarg, query, context, resultDesc); if (need_paren) appendStringInfoChar(buf, ')'); + + if (PRETTY_INDENT(context)) + context->indentLevel -= PRETTYINDENT_STD; } else { @@ -2730,11 +2811,15 @@ get_insert_query_def(Query *query, deparse_context *context) } else if (values_rte) { + /* A WITH clause is possible here */ + get_with_clause(query, context); /* Add the multi-VALUES expression lists */ get_values_def(values_rte->values_lists, context); } else { + /* A WITH clause is possible here */ + get_with_clause(query, context); /* Add the single-VALUES expression list */ appendContextKeyword(context, "VALUES (", -PRETTYINDENT_STD, PRETTYINDENT_STD, 2); @@ -3360,6 +3445,13 @@ get_name_for_var_field(Var *var, int fieldno, * its result columns as RECORD, which is not allowed. */ break; + case RTE_CTE: + /* + * XXX not implemented yet, we need more infrastructure in + * deparse_namespace and explain.c. + */ + elog(ERROR, "deparsing field references to whole-row vars from WITH queries not implemented yet"); + break; } /* @@ -5029,6 +5121,7 @@ get_sublink_expr(SubLink *sublink, deparse_context *context) need_paren = false; break; + case CTE_SUBLINK: /* shouldn't occur in a SubLink */ default: elog(ERROR, "unrecognized sublink type: %d", (int) sublink->subLinkType); @@ -5130,6 +5223,9 @@ get_from_clause_item(Node *jtnode, Query *query, deparse_context *context) /* Values list RTE */ get_values_def(rte->values_lists, context); break; + case RTE_CTE: + appendStringInfoString(buf, quote_identifier(rte->ctename)); + break; default: elog(ERROR, "unrecognized RTE kind: %d", (int) rte->rtekind); break; diff --git a/src/backend/utils/cache/plancache.c b/src/backend/utils/cache/plancache.c index 48addf3f53..fd535c0090 100644 --- a/src/backend/utils/cache/plancache.c +++ b/src/backend/utils/cache/plancache.c @@ -35,7 +35,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/utils/cache/plancache.c,v 1.22 2008/09/15 23:37:39 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/utils/cache/plancache.c,v 1.23 2008/10/04 21:56:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -728,15 +728,23 @@ ScanQueryForLocks(Query *parsetree, bool acquire) } } + /* Recurse into subquery-in-WITH */ + foreach(lc, parsetree->cteList) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + + ScanQueryForLocks((Query *) cte->ctequery, acquire); + } + /* * Recurse into sublink subqueries, too. But we already did the ones in - * the rtable. + * the rtable and cteList. */ if (parsetree->hasSubLinks) { query_tree_walker(parsetree, ScanQueryWalker, (void *) &acquire, - QTW_IGNORE_RT_SUBQUERIES); + QTW_IGNORE_RC_SUBQUERIES); } } diff --git a/src/backend/utils/sort/tuplestore.c b/src/backend/utils/sort/tuplestore.c index 3b53ad28a5..e127de34e5 100644 --- a/src/backend/utils/sort/tuplestore.c +++ b/src/backend/utils/sort/tuplestore.c @@ -46,7 +46,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/utils/sort/tuplestore.c,v 1.40 2008/10/01 19:51:49 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/utils/sort/tuplestore.c,v 1.41 2008/10/04 21:56:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -86,7 +86,7 @@ typedef enum typedef struct { int eflags; /* capability flags */ - bool eof_reached; /* read reached EOF */ + bool eof_reached; /* read has reached EOF */ int current; /* next array index to read */ int file; /* temp file# */ off_t offset; /* byte offset in file */ @@ -374,6 +374,39 @@ tuplestore_alloc_read_pointer(Tuplestorestate *state, int eflags) } /* + * tuplestore_clear + * + * Delete all the contents of a tuplestore, and reset its read pointers + * to the start. + */ +void +tuplestore_clear(Tuplestorestate *state) +{ + int i; + TSReadPointer *readptr; + + if (state->myfile) + BufFileClose(state->myfile); + state->myfile = NULL; + if (state->memtuples) + { + for (i = 0; i < state->memtupcount; i++) + { + FREEMEM(state, GetMemoryChunkSpace(state->memtuples[i])); + pfree(state->memtuples[i]); + } + } + state->status = TSS_INMEM; + state->memtupcount = 0; + readptr = state->readptrs; + for (i = 0; i < state->readptrcount; readptr++, i++) + { + readptr->eof_reached = false; + readptr->current = 0; + } +} + +/* * tuplestore_end * * Release resources and clean up. @@ -463,9 +496,13 @@ tuplestore_ateof(Tuplestorestate *state) * * Note that the input tuple is always copied; the caller need not save it. * - * Any read pointer that is currently "AT EOF" remains so (the read pointer - * implicitly advances along with the write pointer); otherwise the read - * pointer is unchanged. This is for the convenience of nodeMaterial.c. + * If the active read pointer is currently "at EOF", it remains so (the read + * pointer implicitly advances along with the write pointer); otherwise the + * read pointer is unchanged. Non-active read pointers do not move, which + * means they are certain to not be "at EOF" immediately after puttuple. + * This curious-seeming behavior is for the convenience of nodeMaterial.c and + * nodeCtescan.c, which would otherwise need to do extra pointer repositioning + * steps. * * tuplestore_puttupleslot() is a convenience routine to collect data from * a TupleTableSlot without an extra copy operation. @@ -519,11 +556,27 @@ tuplestore_putvalues(Tuplestorestate *state, TupleDesc tdesc, static void tuplestore_puttuple_common(Tuplestorestate *state, void *tuple) { + TSReadPointer *readptr; + int i; + switch (state->status) { case TSS_INMEM: /* + * Update read pointers as needed; see API spec above. + */ + readptr = state->readptrs; + for (i = 0; i < state->readptrcount; readptr++, i++) + { + if (readptr->eof_reached && i != state->activeptr) + { + readptr->eof_reached = false; + readptr->current = state->memtupcount; + } + } + + /* * Grow the array as needed. Note that we try to grow the array * when there is still one free slot remaining --- if we fail, * there'll still be room to store the incoming tuple, and then @@ -572,6 +625,24 @@ tuplestore_puttuple_common(Tuplestorestate *state, void *tuple) dumptuples(state); break; case TSS_WRITEFILE: + + /* + * Update read pointers as needed; see API spec above. + * Note: BufFileTell is quite cheap, so not worth trying + * to avoid multiple calls. + */ + readptr = state->readptrs; + for (i = 0; i < state->readptrcount; readptr++, i++) + { + if (readptr->eof_reached && i != state->activeptr) + { + readptr->eof_reached = false; + BufFileTell(state->myfile, + &readptr->file, + &readptr->offset); + } + } + WRITETUP(state, tuple); break; case TSS_READFILE: @@ -588,6 +659,21 @@ tuplestore_puttuple_common(Tuplestorestate *state, void *tuple) SEEK_SET) != 0) elog(ERROR, "tuplestore seek to EOF failed"); state->status = TSS_WRITEFILE; + + /* + * Update read pointers as needed; see API spec above. + */ + readptr = state->readptrs; + for (i = 0; i < state->readptrcount; readptr++, i++) + { + if (readptr->eof_reached && i != state->activeptr) + { + readptr->eof_reached = false; + readptr->file = state->writepos_file; + readptr->offset = state->writepos_offset; + } + } + WRITETUP(state, tuple); break; default: diff --git a/src/bin/psql/tab-complete.c b/src/bin/psql/tab-complete.c index fbccb2b0ae..aeac562dd8 100644 --- a/src/bin/psql/tab-complete.c +++ b/src/bin/psql/tab-complete.c @@ -3,7 +3,7 @@ * * Copyright (c) 2000-2008, PostgreSQL Global Development Group * - * $PostgreSQL: pgsql/src/bin/psql/tab-complete.c,v 1.172 2008/09/08 00:47:40 tgl Exp $ + * $PostgreSQL: pgsql/src/bin/psql/tab-complete.c,v 1.173 2008/10/04 21:56:54 tgl Exp $ */ /*---------------------------------------------------------------------- @@ -615,7 +615,7 @@ psql_completion(char *text, int start, int end) "GRANT", "INSERT", "LISTEN", "LOAD", "LOCK", "MOVE", "NOTIFY", "PREPARE", "REASSIGN", "REINDEX", "RELEASE", "RESET", "REVOKE", "ROLLBACK", "SAVEPOINT", "SELECT", "SET", "SHOW", "START", "TRUNCATE", "UNLISTEN", - "UPDATE", "VACUUM", "VALUES", NULL + "UPDATE", "VACUUM", "VALUES", "WITH", NULL }; static const char *const backslash_commands[] = { @@ -2044,6 +2044,10 @@ psql_completion(char *text, int start, int end) pg_strcasecmp(prev2_wd, "ANALYZE") == 0)) COMPLETE_WITH_SCHEMA_QUERY(Query_for_list_of_tables, NULL); +/* WITH [RECURSIVE] */ + else if (pg_strcasecmp(prev_wd, "WITH") == 0) + COMPLETE_WITH_CONST("RECURSIVE"); + /* ANALYZE */ /* If the previous word is ANALYZE, produce list of tables */ else if (pg_strcasecmp(prev_wd, "ANALYZE") == 0) diff --git a/src/include/catalog/catversion.h b/src/include/catalog/catversion.h index e333b6d6d6..260d4621cd 100644 --- a/src/include/catalog/catversion.h +++ b/src/include/catalog/catversion.h @@ -37,7 +37,7 @@ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/catalog/catversion.h,v 1.491 2008/10/03 07:33:09 heikki Exp $ + * $PostgreSQL: pgsql/src/include/catalog/catversion.h,v 1.492 2008/10/04 21:56:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -53,6 +53,6 @@ */ /* yyyymmddN */ -#define CATALOG_VERSION_NO 200810031 +#define CATALOG_VERSION_NO 200810041 #endif diff --git a/src/include/executor/nodeCtescan.h b/src/include/executor/nodeCtescan.h new file mode 100644 index 0000000000..e453069164 --- /dev/null +++ b/src/include/executor/nodeCtescan.h @@ -0,0 +1,25 @@ +/*------------------------------------------------------------------------- + * + * nodeCtescan.h + * + * + * + * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * $PostgreSQL: pgsql/src/include/executor/nodeCtescan.h,v 1.1 2008/10/04 21:56:55 tgl Exp $ + * + *------------------------------------------------------------------------- + */ +#ifndef NODECTESCAN_H +#define NODECTESCAN_H + +#include "nodes/execnodes.h" + +extern int ExecCountSlotsCteScan(CteScan *node); +extern CteScanState *ExecInitCteScan(CteScan *node, EState *estate, int eflags); +extern TupleTableSlot *ExecCteScan(CteScanState *node); +extern void ExecEndCteScan(CteScanState *node); +extern void ExecCteScanReScan(CteScanState *node, ExprContext *exprCtxt); + +#endif /* NODECTESCAN_H */ diff --git a/src/include/executor/nodeRecursiveunion.h b/src/include/executor/nodeRecursiveunion.h new file mode 100644 index 0000000000..561f82a69b --- /dev/null +++ b/src/include/executor/nodeRecursiveunion.h @@ -0,0 +1,25 @@ +/*------------------------------------------------------------------------- + * + * nodeRecursiveunion.h + * + * + * + * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * $PostgreSQL: pgsql/src/include/executor/nodeRecursiveunion.h,v 1.1 2008/10/04 21:56:55 tgl Exp $ + * + *------------------------------------------------------------------------- + */ +#ifndef NODERECURSIVEUNION_H +#define NODERECURSIVEUNION_H + +#include "nodes/execnodes.h" + +extern int ExecCountSlotsRecursiveUnion(RecursiveUnion *node); +extern RecursiveUnionState *ExecInitRecursiveUnion(RecursiveUnion *node, EState *estate, int eflags); +extern TupleTableSlot *ExecRecursiveUnion(RecursiveUnionState *node); +extern void ExecEndRecursiveUnion(RecursiveUnionState *node); +extern void ExecRecursiveUnionReScan(RecursiveUnionState *node, ExprContext *exprCtxt); + +#endif /* NODERECURSIVEUNION_H */ diff --git a/src/include/executor/nodeWorktablescan.h b/src/include/executor/nodeWorktablescan.h new file mode 100644 index 0000000000..fb4e309a91 --- /dev/null +++ b/src/include/executor/nodeWorktablescan.h @@ -0,0 +1,25 @@ +/*------------------------------------------------------------------------- + * + * nodeWorktablescan.h + * + * + * + * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * $PostgreSQL: pgsql/src/include/executor/nodeWorktablescan.h,v 1.1 2008/10/04 21:56:55 tgl Exp $ + * + *------------------------------------------------------------------------- + */ +#ifndef NODEWORKTABLESCAN_H +#define NODEWORKTABLESCAN_H + +#include "nodes/execnodes.h" + +extern int ExecCountSlotsWorkTableScan(WorkTableScan *node); +extern WorkTableScanState *ExecInitWorkTableScan(WorkTableScan *node, EState *estate, int eflags); +extern TupleTableSlot *ExecWorkTableScan(WorkTableScanState *node); +extern void ExecEndWorkTableScan(WorkTableScanState *node); +extern void ExecWorkTableScanReScan(WorkTableScanState *node, ExprContext *exprCtxt); + +#endif /* NODEWORKTABLESCAN_H */ diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index eb187ce459..02c9c8f056 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/nodes/execnodes.h,v 1.188 2008/10/01 19:51:49 tgl Exp $ + * $PostgreSQL: pgsql/src/include/nodes/execnodes.h,v 1.189 2008/10/04 21:56:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -947,6 +947,26 @@ typedef struct AppendState } AppendState; /* ---------------- + * RecursiveUnionState information + * + * RecursiveUnionState is used for performing a recursive union. + * + * recursing T when we're done scanning the non-recursive term + * intermediate_empty T if intermediate_table is currently empty + * working_table working table (to be scanned by recursive term) + * intermediate_table current recursive output (next generation of WT) + * ---------------- + */ +typedef struct RecursiveUnionState +{ + PlanState ps; /* its first field is NodeTag */ + bool recursing; + bool intermediate_empty; + Tuplestorestate *working_table; + Tuplestorestate *intermediate_table; +} RecursiveUnionState; + +/* ---------------- * BitmapAndState information * ---------------- */ @@ -1179,6 +1199,43 @@ typedef struct ValuesScanState int marked_idx; } ValuesScanState; +/* ---------------- + * CteScanState information + * + * CteScan nodes are used to scan a CommonTableExpr query. + * + * Multiple CteScan nodes can read out from the same CTE query. We use + * a tuplestore to hold rows that have been read from the CTE query but + * not yet consumed by all readers. + * ---------------- + */ +typedef struct CteScanState +{ + ScanState ss; /* its first field is NodeTag */ + int eflags; /* capability flags to pass to tuplestore */ + int readptr; /* index of my tuplestore read pointer */ + PlanState *cteplanstate; /* PlanState for the CTE query itself */ + /* Link to the "leader" CteScanState (possibly this same node) */ + struct CteScanState *leader; + /* The remaining fields are only valid in the "leader" CteScanState */ + Tuplestorestate *cte_table; /* rows already read from the CTE query */ + bool eof_cte; /* reached end of CTE query? */ +} CteScanState; + +/* ---------------- + * WorkTableScanState information + * + * WorkTableScan nodes are used to scan the work table created by + * a RecursiveUnion node. We locate the RecursiveUnion node + * during executor startup. + * ---------------- + */ +typedef struct WorkTableScanState +{ + ScanState ss; /* its first field is NodeTag */ + RecursiveUnionState *rustate; +} WorkTableScanState; + /* ---------------------------------------------------------------- * Join State Information * ---------------------------------------------------------------- diff --git a/src/include/nodes/nodeFuncs.h b/src/include/nodes/nodeFuncs.h index 5ea2efe81e..bf24297eaa 100644 --- a/src/include/nodes/nodeFuncs.h +++ b/src/include/nodes/nodeFuncs.h @@ -6,7 +6,7 @@ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/nodes/nodeFuncs.h,v 1.28 2008/08/28 23:09:48 tgl Exp $ + * $PostgreSQL: pgsql/src/include/nodes/nodeFuncs.h,v 1.29 2008/10/04 21:56:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -18,8 +18,11 @@ /* flags bits for query_tree_walker and query_tree_mutator */ #define QTW_IGNORE_RT_SUBQUERIES 0x01 /* subqueries in rtable */ -#define QTW_IGNORE_JOINALIASES 0x02 /* JOIN alias var lists */ -#define QTW_DONT_COPY_QUERY 0x04 /* do not copy top Query */ +#define QTW_IGNORE_CTE_SUBQUERIES 0x02 /* subqueries in cteList */ +#define QTW_IGNORE_RC_SUBQUERIES 0x03 /* both of above */ +#define QTW_IGNORE_JOINALIASES 0x04 /* JOIN alias var lists */ +#define QTW_EXAMINE_RTES 0x08 /* examine RTEs */ +#define QTW_DONT_COPY_QUERY 0x10 /* do not copy top Query */ extern Oid exprType(Node *expr); @@ -49,4 +52,7 @@ extern bool query_or_expression_tree_walker(Node *node, bool (*walker) (), extern Node *query_or_expression_tree_mutator(Node *node, Node *(*mutator) (), void *context, int flags); +extern bool raw_expression_tree_walker(Node *node, bool (*walker) (), + void *context); + #endif /* NODEFUNCS_H */ diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h index c02b4c1790..4aa5ce4345 100644 --- a/src/include/nodes/nodes.h +++ b/src/include/nodes/nodes.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/nodes/nodes.h,v 1.212 2008/09/09 18:58:08 tgl Exp $ + * $PostgreSQL: pgsql/src/include/nodes/nodes.h,v 1.213 2008/10/04 21:56:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -44,6 +44,7 @@ typedef enum NodeTag T_Plan = 100, T_Result, T_Append, + T_RecursiveUnion, T_BitmapAnd, T_BitmapOr, T_Scan, @@ -55,6 +56,8 @@ typedef enum NodeTag T_SubqueryScan, T_FunctionScan, T_ValuesScan, + T_CteScan, + T_WorkTableScan, T_Join, T_NestLoop, T_MergeJoin, @@ -78,6 +81,7 @@ typedef enum NodeTag T_PlanState = 200, T_ResultState, T_AppendState, + T_RecursiveUnionState, T_BitmapAndState, T_BitmapOrState, T_ScanState, @@ -89,6 +93,8 @@ typedef enum NodeTag T_SubqueryScanState, T_FunctionScanState, T_ValuesScanState, + T_CteScanState, + T_WorkTableScanState, T_JoinState, T_NestLoopState, T_MergeJoinState, @@ -352,6 +358,8 @@ typedef enum NodeTag T_LockingClause, T_RowMarkClause, T_XmlSerialize, + T_WithClause, + T_CommonTableExpr, /* * TAGS FOR RANDOM OTHER STUFF diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h index 8b8757659b..2660d7adb8 100644 --- a/src/include/nodes/parsenodes.h +++ b/src/include/nodes/parsenodes.h @@ -13,7 +13,7 @@ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/nodes/parsenodes.h,v 1.375 2008/09/08 00:47:41 tgl Exp $ + * $PostgreSQL: pgsql/src/include/nodes/parsenodes.h,v 1.376 2008/10/04 21:56:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -115,6 +115,9 @@ typedef struct Query bool hasAggs; /* has aggregates in tlist or havingQual */ bool hasSubLinks; /* has subquery SubLink */ bool hasDistinctOn; /* distinctClause is from DISTINCT ON */ + bool hasRecursive; /* WITH RECURSIVE was specified */ + + List *cteList; /* WITH list (of CommonTableExpr's) */ List *rtable; /* list of range table entries */ FromExpr *jointree; /* table join tree (FROM and WHERE clauses) */ @@ -563,7 +566,8 @@ typedef enum RTEKind RTE_JOIN, /* join */ RTE_SPECIAL, /* special rule relation (NEW or OLD) */ RTE_FUNCTION, /* function in FROM */ - RTE_VALUES /* VALUES (), (), ... */ + RTE_VALUES, /* VALUES (), (), ... */ + RTE_CTE /* common table expr (WITH list element) */ } RTEKind; typedef struct RangeTblEntry @@ -589,6 +593,20 @@ typedef struct RangeTblEntry Query *subquery; /* the sub-query */ /* + * Fields valid for a join RTE (else NULL/zero): + * + * joinaliasvars is a list of Vars or COALESCE expressions corresponding + * to the columns of the join result. An alias Var referencing column K + * of the join result can be replaced by the K'th element of joinaliasvars + * --- but to simplify the task of reverse-listing aliases correctly, we + * do not do that until planning time. In a Query loaded from a stored + * rule, it is also possible for joinaliasvars items to be NULL Consts, + * denoting columns dropped since the rule was made. + */ + JoinType jointype; /* type of join */ + List *joinaliasvars; /* list of alias-var expansions */ + + /* * Fields valid for a function RTE (else NULL): * * If the function returns RECORD, funccoltypes lists the column types @@ -605,18 +623,13 @@ typedef struct RangeTblEntry List *values_lists; /* list of expression lists */ /* - * Fields valid for a join RTE (else NULL/zero): - * - * joinaliasvars is a list of Vars or COALESCE expressions corresponding - * to the columns of the join result. An alias Var referencing column K - * of the join result can be replaced by the K'th element of joinaliasvars - * --- but to simplify the task of reverse-listing aliases correctly, we - * do not do that until planning time. In a Query loaded from a stored - * rule, it is also possible for joinaliasvars items to be NULL Consts, - * denoting columns dropped since the rule was made. + * Fields valid for a CTE RTE (else NULL/zero): */ - JoinType jointype; /* type of join */ - List *joinaliasvars; /* list of alias-var expansions */ + char *ctename; /* name of the WITH list item */ + Index ctelevelsup; /* number of query levels up */ + bool self_reference; /* is this a recursive self-reference? */ + List *ctecoltypes; /* OID list of column type OIDs */ + List *ctecoltypmods; /* integer list of column typmods */ /* * Fields valid in all RTEs: @@ -697,6 +710,43 @@ typedef struct RowMarkClause bool noWait; /* NOWAIT option */ } RowMarkClause; +/* + * WithClause - + * representation of WITH clause + * + * Note: WithClause does not propagate into the Query representation; + * but CommonTableExpr does. + */ +typedef struct WithClause +{ + NodeTag type; + List *ctes; /* list of CommonTableExprs */ + bool recursive; /* true = WITH RECURSIVE */ + int location; /* token location, or -1 if unknown */ +} WithClause; + +/* + * CommonTableExpr - + * representation of WITH list element + * + * We don't currently support the SEARCH or CYCLE clause. + */ +typedef struct CommonTableExpr +{ + NodeTag type; + char *ctename; /* query name (never qualified) */ + List *aliascolnames; /* optional list of column names */ + Node *ctequery; /* subquery (SelectStmt or Query) */ + int location; /* token location, or -1 if unknown */ + /* These fields are set during parse analysis: */ + bool cterecursive; /* is this CTE actually recursive? */ + int cterefcount; /* number of RTEs referencing this CTE + * (excluding internal self-references) */ + List *ctecolnames; /* list of output column names */ + List *ctecoltypes; /* OID list of output column type OIDs */ + List *ctecoltypmods; /* integer list of output column typmods */ +} CommonTableExpr; + /***************************************************************************** * Optimizable Statements *****************************************************************************/ @@ -781,6 +831,7 @@ typedef struct SelectStmt Node *whereClause; /* WHERE qualification */ List *groupClause; /* GROUP BY clauses */ Node *havingClause; /* HAVING conditional-expression */ + WithClause *withClause; /* WITH clause */ /* * In a "leaf" node representing a VALUES list, the above fields are all diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h index 2f0ed9a5d7..cdf06b0020 100644 --- a/src/include/nodes/plannodes.h +++ b/src/include/nodes/plannodes.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/nodes/plannodes.h,v 1.103 2008/09/09 18:58:08 tgl Exp $ + * $PostgreSQL: pgsql/src/include/nodes/plannodes.h,v 1.104 2008/10/04 21:56:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -183,6 +183,20 @@ typedef struct Append } Append; /* ---------------- + * RecursiveUnion node - + * Generate a recursive union of two subplans. + * + * The "outer" subplan is always the non-recursive term, and the "inner" + * subplan is the recursive term. + * ---------------- + */ +typedef struct RecursiveUnion +{ + Plan plan; + int wtParam; /* ID of Param representing work table */ +} RecursiveUnion; + +/* ---------------- * BitmapAnd node - * Generate the intersection of the results of sub-plans. * @@ -358,6 +372,28 @@ typedef struct ValuesScan List *values_lists; /* list of expression lists */ } ValuesScan; +/* ---------------- + * CteScan node + * ---------------- + */ +typedef struct CteScan +{ + Scan scan; + int ctePlanId; /* ID of init SubPlan for CTE */ + int cteParam; /* ID of Param representing CTE output */ +} CteScan; + +/* ---------------- + * WorkTableScan node + * ---------------- + */ +typedef struct WorkTableScan +{ + Scan scan; + int wtParam; /* ID of Param representing work table */ +} WorkTableScan; + + /* * ========== * Join nodes diff --git a/src/include/nodes/primnodes.h b/src/include/nodes/primnodes.h index e144251dd1..e8614492fe 100644 --- a/src/include/nodes/primnodes.h +++ b/src/include/nodes/primnodes.h @@ -10,7 +10,7 @@ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/nodes/primnodes.h,v 1.141 2008/09/01 20:42:45 tgl Exp $ + * $PostgreSQL: pgsql/src/include/nodes/primnodes.h,v 1.142 2008/10/04 21:56:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -386,6 +386,7 @@ typedef struct BoolExpr * ROWCOMPARE_SUBLINK (lefthand) op (SELECT ...) * EXPR_SUBLINK (SELECT with single targetlist item ...) * ARRAY_SUBLINK ARRAY(SELECT with single targetlist item ...) + * CTE_SUBLINK WITH query (never actually part of an expression) * For ALL, ANY, and ROWCOMPARE, the lefthand is a list of expressions of the * same length as the subselect's targetlist. ROWCOMPARE will *always* have * a list with more than one entry; if the subselect has just one target @@ -412,6 +413,9 @@ typedef struct BoolExpr * * In EXISTS, EXPR, and ARRAY SubLinks, testexpr and operName are unused and * are always null. + * + * The CTE_SUBLINK case never occurs in actual SubLink nodes, but it is used + * in SubPlans generated for WITH subqueries. */ typedef enum SubLinkType { @@ -420,7 +424,8 @@ typedef enum SubLinkType ANY_SUBLINK, ROWCOMPARE_SUBLINK, EXPR_SUBLINK, - ARRAY_SUBLINK + ARRAY_SUBLINK, + CTE_SUBLINK /* for SubPlans only */ } SubLinkType; diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h index c66bc05a74..9cb4370c85 100644 --- a/src/include/nodes/relation.h +++ b/src/include/nodes/relation.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.159 2008/09/09 18:58:08 tgl Exp $ + * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.160 2008/10/04 21:56:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -104,6 +104,8 @@ typedef struct PlannerInfo Index query_level; /* 1 at the outermost Query */ + struct PlannerInfo *parent_root; /* NULL at outermost Query */ + /* * simple_rel_array holds pointers to "base rels" and "other rels" (see * comments for RelOptInfo for more info). It is indexed by rangetable @@ -138,7 +140,9 @@ typedef struct PlannerInfo List *returningLists; /* list of lists of TargetEntry, or NIL */ - List *init_plans; /* init subplans for query */ + List *init_plans; /* init SubPlans for query */ + + List *cte_plan_ids; /* per-CTE-item list of subplan IDs */ List *eq_classes; /* list of active EquivalenceClasses */ @@ -178,6 +182,11 @@ typedef struct PlannerInfo bool hasHavingQual; /* true if havingQual was non-null */ bool hasPseudoConstantQuals; /* true if any RestrictInfo has * pseudoconstant = true */ + bool hasRecursion; /* true if planning a recursive WITH item */ + + /* These fields are used only when hasRecursion is true: */ + int wt_param_id; /* PARAM_EXEC ID for the work table */ + struct Plan *non_recursive_plan; /* plan for non-recursive term */ } PlannerInfo; @@ -542,8 +551,9 @@ typedef struct PathKey } PathKey; /* - * Type "Path" is used as-is for sequential-scan paths. For other - * path types it is the first component of a larger struct. + * Type "Path" is used as-is for sequential-scan paths, as well as some other + * simple plan types that we don't need any extra information in the path for. + * For other path types it is the first component of a larger struct. * * Note: "pathtype" is the NodeTag of the Plan node we could build from this * Path. It is partially redundant with the Path's NodeTag, but allows us diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h index 8ad8f7f062..181327caa8 100644 --- a/src/include/optimizer/cost.h +++ b/src/include/optimizer/cost.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/optimizer/cost.h,v 1.92 2008/08/22 00:16:04 tgl Exp $ + * $PostgreSQL: pgsql/src/include/optimizer/cost.h,v 1.93 2008/10/04 21:56:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -72,6 +72,8 @@ extern void cost_functionscan(Path *path, PlannerInfo *root, RelOptInfo *baserel); extern void cost_valuesscan(Path *path, PlannerInfo *root, RelOptInfo *baserel); +extern void cost_ctescan(Path *path, PlannerInfo *root, RelOptInfo *baserel); +extern void cost_recursive_union(Plan *runion, Plan *nrterm, Plan *rterm); extern void cost_sort(Path *path, PlannerInfo *root, List *pathkeys, Cost input_cost, double tuples, int width, double limit_tuples); @@ -104,6 +106,8 @@ extern void set_joinrel_size_estimates(PlannerInfo *root, RelOptInfo *rel, List *restrictlist); extern void set_function_size_estimates(PlannerInfo *root, RelOptInfo *rel); extern void set_values_size_estimates(PlannerInfo *root, RelOptInfo *rel); +extern void set_cte_size_estimates(PlannerInfo *root, RelOptInfo *rel, + Plan *cteplan); /* * prototypes for clausesel.c diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h index 1db1674e12..b8a256aa1b 100644 --- a/src/include/optimizer/pathnode.h +++ b/src/include/optimizer/pathnode.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/optimizer/pathnode.h,v 1.78 2008/08/14 18:48:00 tgl Exp $ + * $PostgreSQL: pgsql/src/include/optimizer/pathnode.h,v 1.79 2008/10/04 21:56:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -54,6 +54,8 @@ extern UniquePath *create_unique_path(PlannerInfo *root, RelOptInfo *rel, extern Path *create_subqueryscan_path(RelOptInfo *rel, List *pathkeys); extern Path *create_functionscan_path(PlannerInfo *root, RelOptInfo *rel); extern Path *create_valuesscan_path(PlannerInfo *root, RelOptInfo *rel); +extern Path *create_ctescan_path(PlannerInfo *root, RelOptInfo *rel); +extern Path *create_worktablescan_path(PlannerInfo *root, RelOptInfo *rel); extern NestPath *create_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h index a6b15187ce..1e8017fb6d 100644 --- a/src/include/optimizer/planmain.h +++ b/src/include/optimizer/planmain.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/optimizer/planmain.h,v 1.112 2008/09/09 18:58:09 tgl Exp $ + * $PostgreSQL: pgsql/src/include/optimizer/planmain.h,v 1.113 2008/10/04 21:56:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -42,6 +42,8 @@ extern Plan *create_plan(PlannerInfo *root, Path *best_path); extern SubqueryScan *make_subqueryscan(List *qptlist, List *qpqual, Index scanrelid, Plan *subplan, List *subrtable); extern Append *make_append(List *appendplans, bool isTarget, List *tlist); +extern RecursiveUnion *make_recursive_union(List *tlist, + Plan *lefttree, Plan *righttree, int wtParam); extern Sort *make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys, double limit_tuples); extern Sort *make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, diff --git a/src/include/optimizer/planner.h b/src/include/optimizer/planner.h index 0405868b74..3529fd1850 100644 --- a/src/include/optimizer/planner.h +++ b/src/include/optimizer/planner.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/optimizer/planner.h,v 1.44 2008/01/01 19:45:58 momjian Exp $ + * $PostgreSQL: pgsql/src/include/optimizer/planner.h,v 1.45 2008/10/04 21:56:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -30,7 +30,8 @@ extern PlannedStmt *planner(Query *parse, int cursorOptions, extern PlannedStmt *standard_planner(Query *parse, int cursorOptions, ParamListInfo boundParams); extern Plan *subquery_planner(PlannerGlobal *glob, Query *parse, - Index level, double tuple_fraction, + PlannerInfo *parent_root, + bool hasRecursion, double tuple_fraction, PlannerInfo **subroot); #endif /* PLANNER_H */ diff --git a/src/include/optimizer/subselect.h b/src/include/optimizer/subselect.h index 97e230a2db..e227221e94 100644 --- a/src/include/optimizer/subselect.h +++ b/src/include/optimizer/subselect.h @@ -5,7 +5,7 @@ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/optimizer/subselect.h,v 1.33 2008/08/17 01:20:00 tgl Exp $ + * $PostgreSQL: pgsql/src/include/optimizer/subselect.h,v 1.34 2008/10/04 21:56:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -15,6 +15,7 @@ #include "nodes/plannodes.h" #include "nodes/relation.h" +extern void SS_process_ctes(PlannerInfo *root); extern bool convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink, Relids available_rels, Node **new_qual, List **fromlist); @@ -28,5 +29,6 @@ extern void SS_finalize_plan(PlannerInfo *root, Plan *plan, bool attach_initplans); extern Param *SS_make_initplan_from_plan(PlannerInfo *root, Plan *plan, Oid resulttype, int32 resulttypmod); +extern int SS_assign_worktable_param(PlannerInfo *root); #endif /* SUBSELECT_H */ diff --git a/src/include/parser/parse_cte.h b/src/include/parser/parse_cte.h new file mode 100644 index 0000000000..142e833f3e --- /dev/null +++ b/src/include/parser/parse_cte.h @@ -0,0 +1,21 @@ +/*------------------------------------------------------------------------- + * + * parse_cte.h + * handle CTEs (common table expressions) in parser + * + * + * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * $PostgreSQL: pgsql/src/include/parser/parse_cte.h,v 1.1 2008/10/04 21:56:55 tgl Exp $ + * + *------------------------------------------------------------------------- + */ +#ifndef PARSE_CTE_H +#define PARSE_CTE_H + +#include "parser/parse_node.h" + +extern List *transformWithClause(ParseState *pstate, WithClause *withClause); + +#endif /* PARSE_CTE_H */ diff --git a/src/include/parser/parse_node.h b/src/include/parser/parse_node.h index 460655d3b1..05817cf51a 100644 --- a/src/include/parser/parse_node.h +++ b/src/include/parser/parse_node.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/parser/parse_node.h,v 1.56 2008/09/01 20:42:45 tgl Exp $ + * $PostgreSQL: pgsql/src/include/parser/parse_node.h,v 1.57 2008/10/04 21:56:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -50,6 +50,10 @@ * implicit RTEs into p_relnamespace but not p_varnamespace, so that they * do not affect the set of columns available for unqualified references. * + * p_ctenamespace: list of CommonTableExprs (WITH items) that are visible + * at the moment. This is different from p_relnamespace because you have + * to make an RTE before you can access a CTE. + * * p_paramtypes: an array of p_numparams type OIDs for $n parameter symbols * (zeroth entry in array corresponds to $1). If p_variableparams is true, the * set of param types is not predetermined; in that case, a zero array entry @@ -68,6 +72,7 @@ typedef struct ParseState * node's fromlist) */ List *p_relnamespace; /* current namespace for relations */ List *p_varnamespace; /* current namespace for columns */ + List *p_ctenamespace; /* current namespace for common table exprs */ Oid *p_paramtypes; /* OIDs of types for $n parameter symbols */ int p_numparams; /* allocated size of p_paramtypes[] */ int p_next_resno; /* next targetlist resno to assign */ diff --git a/src/include/parser/parse_relation.h b/src/include/parser/parse_relation.h index 1c4e1b6b8e..9c81d4b50b 100644 --- a/src/include/parser/parse_relation.h +++ b/src/include/parser/parse_relation.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/parser/parse_relation.h,v 1.58 2008/09/01 20:42:45 tgl Exp $ + * $PostgreSQL: pgsql/src/include/parser/parse_relation.h,v 1.59 2008/10/04 21:56:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -31,6 +31,7 @@ extern int RTERangeTablePosn(ParseState *pstate, extern RangeTblEntry *GetRTEByRangeTablePosn(ParseState *pstate, int varno, int sublevels_up); +extern CommonTableExpr *GetCTEForRTE(ParseState *pstate, RangeTblEntry *rte); extern Node *scanRTEForColumn(ParseState *pstate, RangeTblEntry *rte, char *colname, int location); extern Node *colNameToVar(ParseState *pstate, char *colname, bool localonly, @@ -72,6 +73,11 @@ extern RangeTblEntry *addRangeTableEntryForJoin(ParseState *pstate, List *aliasvars, Alias *alias, bool inFromCl); +extern RangeTblEntry *addRangeTableEntryForCTE(ParseState *pstate, + CommonTableExpr *cte, + Index levelsup, + Alias *alias, + bool inFromCl); extern void addRTEtoQuery(ParseState *pstate, RangeTblEntry *rte, bool addToJoinList, bool addToRelNameSpace, bool addToVarNameSpace); diff --git a/src/include/utils/errcodes.h b/src/include/utils/errcodes.h index 9cfdd16bde..baecd7bafc 100644 --- a/src/include/utils/errcodes.h +++ b/src/include/utils/errcodes.h @@ -11,7 +11,7 @@ * * Copyright (c) 2003-2008, PostgreSQL Global Development Group * - * $PostgreSQL: pgsql/src/include/utils/errcodes.h,v 1.25 2008/05/15 22:39:49 tgl Exp $ + * $PostgreSQL: pgsql/src/include/utils/errcodes.h,v 1.26 2008/10/04 21:56:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -246,6 +246,7 @@ #define ERRCODE_INSUFFICIENT_PRIVILEGE MAKE_SQLSTATE('4','2', '5','0','1') #define ERRCODE_CANNOT_COERCE MAKE_SQLSTATE('4','2', '8','4','6') #define ERRCODE_GROUPING_ERROR MAKE_SQLSTATE('4','2', '8','0','3') +#define ERRCODE_INVALID_RECURSION MAKE_SQLSTATE('4','2', 'P','1','9') #define ERRCODE_INVALID_FOREIGN_KEY MAKE_SQLSTATE('4','2', '8','3','0') #define ERRCODE_INVALID_NAME MAKE_SQLSTATE('4','2', '6','0','2') #define ERRCODE_NAME_TOO_LONG MAKE_SQLSTATE('4','2', '6','2','2') diff --git a/src/include/utils/tuplestore.h b/src/include/utils/tuplestore.h index 3fe32f682b..201e8ba055 100644 --- a/src/include/utils/tuplestore.h +++ b/src/include/utils/tuplestore.h @@ -24,7 +24,7 @@ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/utils/tuplestore.h,v 1.24 2008/10/01 19:51:50 tgl Exp $ + * $PostgreSQL: pgsql/src/include/utils/tuplestore.h,v 1.25 2008/10/04 21:56:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -74,6 +74,8 @@ extern bool tuplestore_ateof(Tuplestorestate *state); extern void tuplestore_rescan(Tuplestorestate *state); +extern void tuplestore_clear(Tuplestorestate *state); + extern void tuplestore_end(Tuplestorestate *state); #endif /* TUPLESTORE_H */ diff --git a/src/interfaces/ecpg/preproc/preproc.y b/src/interfaces/ecpg/preproc/preproc.y index 5b69d8b306..b0d126e9ba 100644 --- a/src/interfaces/ecpg/preproc/preproc.y +++ b/src/interfaces/ecpg/preproc/preproc.y @@ -1,4 +1,4 @@ -/* $PostgreSQL: pgsql/src/interfaces/ecpg/preproc/preproc.y,v 1.372 2008/09/23 09:20:39 heikki Exp $ */ +/* $PostgreSQL: pgsql/src/interfaces/ecpg/preproc/preproc.y,v 1.373 2008/10/04 21:56:55 tgl Exp $ */ /* Copyright comment */ %{ @@ -473,7 +473,7 @@ add_typedef(char *name, char * dimension, char * length, enum ECPGttype type_enu QUOTE - READ REAL REASSIGN RECHECK REFERENCES REINDEX RELATIVE_P RELEASE RENAME + READ REAL REASSIGN RECHECK RECURSIVE REFERENCES REINDEX RELATIVE_P RELEASE RENAME REPEATABLE REPLACE REPLICA RESET RESTART RESTRICT RETURNING RETURNS REVOKE RIGHT ROLE ROLLBACK ROW ROWS RULE diff --git a/src/pl/plpgsql/src/plerrcodes.h b/src/pl/plpgsql/src/plerrcodes.h index e6ab24dfd0..77fd1a24e3 100644 --- a/src/pl/plpgsql/src/plerrcodes.h +++ b/src/pl/plpgsql/src/plerrcodes.h @@ -9,7 +9,7 @@ * * Copyright (c) 2003-2008, PostgreSQL Global Development Group * - * $PostgreSQL: pgsql/src/pl/plpgsql/src/plerrcodes.h,v 1.14 2008/05/15 22:39:49 tgl Exp $ + * $PostgreSQL: pgsql/src/pl/plpgsql/src/plerrcodes.h,v 1.15 2008/10/04 21:56:55 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -484,6 +484,10 @@ }, { + "invalid_recursion", ERRCODE_INVALID_RECURSION +}, + +{ "invalid_foreign_key", ERRCODE_INVALID_FOREIGN_KEY }, diff --git a/src/test/regress/expected/with.out b/src/test/regress/expected/with.out new file mode 100644 index 0000000000..ac91642c7b --- /dev/null +++ b/src/test/regress/expected/with.out @@ -0,0 +1,666 @@ +-- +-- Tests for common table expressions (WITH query, ... SELECT ...) +-- +-- Basic WITH +WITH q1(x,y) AS (SELECT 1,2) +SELECT * FROM q1, q1 AS q2; + x | y | x | y +---+---+---+--- + 1 | 2 | 1 | 2 +(1 row) + +-- Multiple uses are evaluated only once +SELECT count(*) FROM ( + WITH q1(x) AS (SELECT random() FROM generate_series(1, 5)) + SELECT * FROM q1 + UNION + SELECT * FROM q1 +) ss; + count +------- + 5 +(1 row) + +-- WITH RECURSIVE +-- sum of 1..100 +WITH RECURSIVE t(n) AS ( + VALUES (1) +UNION ALL + SELECT n+1 FROM t WHERE n < 100 +) +SELECT sum(n) FROM t; + sum +------ + 5050 +(1 row) + +WITH RECURSIVE t(n) AS ( + SELECT (VALUES(1)) +UNION ALL + SELECT n+1 FROM t WHERE n < 5 +) +SELECT * FROM t; + n +--- + 1 + 2 + 3 + 4 + 5 +(5 rows) + +-- This'd be an infinite loop, but outside query reads only as much as needed +WITH RECURSIVE t(n) AS ( + VALUES (1) +UNION ALL + SELECT n+1 FROM t) +SELECT * FROM t LIMIT 10; + n +---- + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 +(10 rows) + +-- +-- Some examples with a tree +-- +-- department structure represented here is as follows: +-- +-- ROOT-+->A-+->B-+->C +-- | | +-- | +->D-+->F +-- +->E-+->G +CREATE TEMP TABLE department ( + id INTEGER PRIMARY KEY, -- department ID + parent_department INTEGER REFERENCES department, -- upper department ID + name TEXT -- department name +); +NOTICE: CREATE TABLE / PRIMARY KEY will create implicit index "department_pkey" for table "department" +INSERT INTO department VALUES (0, NULL, 'ROOT'); +INSERT INTO department VALUES (1, 0, 'A'); +INSERT INTO department VALUES (2, 1, 'B'); +INSERT INTO department VALUES (3, 2, 'C'); +INSERT INTO department VALUES (4, 2, 'D'); +INSERT INTO department VALUES (5, 0, 'E'); +INSERT INTO department VALUES (6, 4, 'F'); +INSERT INTO department VALUES (7, 5, 'G'); +-- extract all departments under 'A'. Result should be A, B, C, D and F +WITH RECURSIVE subdepartment AS +( + -- non recursive term + SELECT * FROM department WHERE name = 'A' + UNION ALL + -- recursive term + SELECT d.* FROM department AS d, subdepartment AS sd + WHERE d.parent_department = sd.id +) +SELECT * FROM subdepartment ORDER BY name; + id | parent_department | name +----+-------------------+------ + 1 | 0 | A + 2 | 1 | B + 3 | 2 | C + 4 | 2 | D + 6 | 4 | F +(5 rows) + +-- extract all departments under 'A' with "level" number +WITH RECURSIVE subdepartment(level, id, parent_department, name) AS +( + -- non recursive term + SELECT 1, * FROM department WHERE name = 'A' + UNION ALL + -- recursive term + SELECT sd.level + 1, d.* FROM department AS d, subdepartment AS sd + WHERE d.parent_department = sd.id +) +SELECT * FROM subdepartment ORDER BY name; + level | id | parent_department | name +-------+----+-------------------+------ + 1 | 1 | 0 | A + 2 | 2 | 1 | B + 3 | 3 | 2 | C + 3 | 4 | 2 | D + 4 | 6 | 4 | F +(5 rows) + +-- extract all departments under 'A' with "level" number. +-- Only shows level 2 or more +WITH RECURSIVE subdepartment(level, id, parent_department, name) AS +( + -- non recursive term + SELECT 1, * FROM department WHERE name = 'A' + UNION ALL + -- recursive term + SELECT sd.level + 1, d.* FROM department AS d, subdepartment AS sd + WHERE d.parent_department = sd.id +) +SELECT * FROM subdepartment WHERE level >= 2 ORDER BY name; + level | id | parent_department | name +-------+----+-------------------+------ + 2 | 2 | 1 | B + 3 | 3 | 2 | C + 3 | 4 | 2 | D + 4 | 6 | 4 | F +(4 rows) + +-- "RECURSIVE" is ignored if the query has no self-reference +WITH RECURSIVE subdepartment AS +( + -- note lack of recursive UNION structure + SELECT * FROM department WHERE name = 'A' +) +SELECT * FROM subdepartment ORDER BY name; + id | parent_department | name +----+-------------------+------ + 1 | 0 | A +(1 row) + +-- inside subqueries +SELECT count(*) FROM ( + WITH RECURSIVE t(n) AS ( + SELECT 1 UNION ALL SELECT n + 1 FROM t WHERE n < 500 + ) + SELECT * FROM t) AS t WHERE n < ( + SELECT count(*) FROM ( + WITH RECURSIVE t(n) AS ( + SELECT 1 UNION ALL SELECT n + 1 FROM t WHERE n < 100 + ) + SELECT * FROM t WHERE n < 50000 + ) AS t WHERE n < 100); + count +------- + 98 +(1 row) + +-- use same CTE twice at different subquery levels +WITH q1(x,y) AS ( + SELECT hundred, sum(ten) FROM tenk1 GROUP BY hundred + ) +SELECT count(*) FROM q1 WHERE y > (SELECT sum(y)/100 FROM q1 qsub); + count +------- + 50 +(1 row) + +-- via a VIEW +CREATE TEMPORARY VIEW vsubdepartment AS + WITH RECURSIVE subdepartment AS + ( + -- non recursive term + SELECT * FROM department WHERE name = 'A' + UNION ALL + -- recursive term + SELECT d.* FROM department AS d, subdepartment AS sd + WHERE d.parent_department = sd.id + ) + SELECT * FROM subdepartment; +SELECT * FROM vsubdepartment ORDER BY name; + id | parent_department | name +----+-------------------+------ + 1 | 0 | A + 2 | 1 | B + 3 | 2 | C + 4 | 2 | D + 6 | 4 | F +(5 rows) + +-- Check reverse listing +SELECT pg_get_viewdef('vsubdepartment'::regclass); + pg_get_viewdef +--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- + WITH RECURSIVE subdepartment AS (SELECT department.id, department.parent_department, department.name FROM department WHERE (department.name = 'A'::text) UNION ALL SELECT d.id, d.parent_department, d.name FROM department d, subdepartment sd WHERE (d.parent_department = sd.id)) SELECT subdepartment.id, subdepartment.parent_department, subdepartment.name FROM subdepartment; +(1 row) + +SELECT pg_get_viewdef('vsubdepartment'::regclass, true); + pg_get_viewdef +-------------------------------------------------------------------------------------- + WITH RECURSIVE subdepartment AS ( + SELECT department.id, department.parent_department, department.name + FROM department + WHERE department.name = 'A'::text + UNION ALL + SELECT d.id, d.parent_department, d.name + FROM department d, subdepartment sd + WHERE d.parent_department = sd.id + ) + SELECT subdepartment.id, subdepartment.parent_department, subdepartment.name + FROM subdepartment; +(1 row) + +-- recursive term has sub-UNION +WITH RECURSIVE t(i,j) AS ( + VALUES (1,2) + UNION ALL + SELECT t2.i, t.j+1 FROM + (SELECT 2 AS i UNION ALL SELECT 3 AS i) AS t2 + JOIN t ON (t2.i = t.i+1)) + SELECT * FROM t; + i | j +---+--- + 1 | 2 + 2 | 3 + 3 | 4 +(3 rows) + +-- +-- different tree example +-- +CREATE TEMPORARY TABLE tree( + id INTEGER PRIMARY KEY, + parent_id INTEGER REFERENCES tree(id) +); +NOTICE: CREATE TABLE / PRIMARY KEY will create implicit index "tree_pkey" for table "tree" +INSERT INTO tree +VALUES (1, NULL), (2, 1), (3,1), (4,2), (5,2), (6,2), (7,3), (8,3), + (9,4), (10,4), (11,7), (12,7), (13,7), (14, 9), (15,11), (16,11); +-- +-- get all paths from "second level" nodes to leaf nodes +-- +WITH RECURSIVE t(id, path) AS ( + VALUES(1,ARRAY[]::integer[]) +UNION ALL + SELECT tree.id, t.path || tree.id + FROM tree JOIN t ON (tree.parent_id = t.id) +) +SELECT t1.*, t2.* FROM t AS t1 JOIN t AS t2 ON + (t1.path[1] = t2.path[1] AND + array_upper(t1.path,1) = 1 AND + array_upper(t2.path,1) > 1) + ORDER BY t1.id, t2.id; + id | path | id | path +----+------+----+------------- + 2 | {2} | 4 | {2,4} + 2 | {2} | 5 | {2,5} + 2 | {2} | 6 | {2,6} + 2 | {2} | 9 | {2,4,9} + 2 | {2} | 10 | {2,4,10} + 2 | {2} | 14 | {2,4,9,14} + 3 | {3} | 7 | {3,7} + 3 | {3} | 8 | {3,8} + 3 | {3} | 11 | {3,7,11} + 3 | {3} | 12 | {3,7,12} + 3 | {3} | 13 | {3,7,13} + 3 | {3} | 15 | {3,7,11,15} + 3 | {3} | 16 | {3,7,11,16} +(13 rows) + +-- just count 'em +WITH RECURSIVE t(id, path) AS ( + VALUES(1,ARRAY[]::integer[]) +UNION ALL + SELECT tree.id, t.path || tree.id + FROM tree JOIN t ON (tree.parent_id = t.id) +) +SELECT t1.id, count(t2.*) FROM t AS t1 JOIN t AS t2 ON + (t1.path[1] = t2.path[1] AND + array_upper(t1.path,1) = 1 AND + array_upper(t2.path,1) > 1) + GROUP BY t1.id + ORDER BY t1.id; + id | count +----+------- + 2 | 6 + 3 | 7 +(2 rows) + +-- +-- test multiple WITH queries +-- +WITH RECURSIVE + y (id) AS (VALUES (1)), + x (id) AS (SELECT * FROM y UNION ALL SELECT id+1 FROM x WHERE id < 5) +SELECT * FROM x; + id +---- + 1 + 2 + 3 + 4 + 5 +(5 rows) + +-- forward reference OK +WITH RECURSIVE + x(id) AS (SELECT * FROM y UNION ALL SELECT id+1 FROM x WHERE id < 5), + y(id) AS (values (1)) + SELECT * FROM x; + id +---- + 1 + 2 + 3 + 4 + 5 +(5 rows) + +WITH RECURSIVE + x(id) AS + (VALUES (1) UNION ALL SELECT id+1 FROM x WHERE id < 5), + y(id) AS + (VALUES (1) UNION ALL SELECT id+1 FROM y WHERE id < 10) + SELECT y.*, x.* FROM y LEFT JOIN x USING (id); + id | id +----+---- + 1 | 1 + 2 | 2 + 3 | 3 + 4 | 4 + 5 | 5 + 6 | + 7 | + 8 | + 9 | + 10 | +(10 rows) + +WITH RECURSIVE + x(id) AS + (VALUES (1) UNION ALL SELECT id+1 FROM x WHERE id < 5), + y(id) AS + (VALUES (1) UNION ALL SELECT id+1 FROM x WHERE id < 10) + SELECT y.*, x.* FROM y LEFT JOIN x USING (id); + id | id +----+---- + 1 | 1 + 2 | 2 + 3 | 3 + 4 | 4 + 5 | 5 + 6 | +(6 rows) + +WITH RECURSIVE + x(id) AS + (SELECT 1 UNION ALL SELECT id+1 FROM x WHERE id < 3 ), + y(id) AS + (SELECT * FROM x UNION ALL SELECT * FROM x), + z(id) AS + (SELECT * FROM x UNION ALL SELECT id+1 FROM z WHERE id < 10) + SELECT * FROM z; + id +---- + 1 + 2 + 3 + 2 + 3 + 4 + 3 + 4 + 5 + 4 + 5 + 6 + 5 + 6 + 7 + 6 + 7 + 8 + 7 + 8 + 9 + 8 + 9 + 10 + 9 + 10 + 10 +(27 rows) + +WITH RECURSIVE + x(id) AS + (SELECT 1 UNION ALL SELECT id+1 FROM x WHERE id < 3 ), + y(id) AS + (SELECT * FROM x UNION ALL SELECT * FROM x), + z(id) AS + (SELECT * FROM y UNION ALL SELECT id+1 FROM z WHERE id < 10) + SELECT * FROM z; + id +---- + 1 + 2 + 3 + 1 + 2 + 3 + 2 + 3 + 4 + 2 + 3 + 4 + 3 + 4 + 5 + 3 + 4 + 5 + 4 + 5 + 6 + 4 + 5 + 6 + 5 + 6 + 7 + 5 + 6 + 7 + 6 + 7 + 8 + 6 + 7 + 8 + 7 + 8 + 9 + 7 + 8 + 9 + 8 + 9 + 10 + 8 + 9 + 10 + 9 + 10 + 9 + 10 + 10 + 10 +(54 rows) + +-- +-- error cases +-- +-- UNION (should be supported someday) +WITH RECURSIVE x(n) AS (SELECT 1 UNION SELECT n+1 FROM x) + SELECT * FROM x; +ERROR: recursive query "x" does not have the form non-recursive-term UNION ALL recursive-term +LINE 1: WITH RECURSIVE x(n) AS (SELECT 1 UNION SELECT n+1 FROM x) + ^ +-- INTERSECT +WITH RECURSIVE x(n) AS (SELECT 1 INTERSECT SELECT n+1 FROM x) + SELECT * FROM x; +ERROR: recursive query "x" does not have the form non-recursive-term UNION ALL recursive-term +LINE 1: WITH RECURSIVE x(n) AS (SELECT 1 INTERSECT SELECT n+1 FROM x... + ^ +WITH RECURSIVE x(n) AS (SELECT 1 INTERSECT ALL SELECT n+1 FROM x) + SELECT * FROM x; +ERROR: recursive query "x" does not have the form non-recursive-term UNION ALL recursive-term +LINE 1: WITH RECURSIVE x(n) AS (SELECT 1 INTERSECT ALL SELECT n+1 FR... + ^ +-- EXCEPT +WITH RECURSIVE x(n) AS (SELECT 1 EXCEPT SELECT n+1 FROM x) + SELECT * FROM x; +ERROR: recursive query "x" does not have the form non-recursive-term UNION ALL recursive-term +LINE 1: WITH RECURSIVE x(n) AS (SELECT 1 EXCEPT SELECT n+1 FROM x) + ^ +WITH RECURSIVE x(n) AS (SELECT 1 EXCEPT ALL SELECT n+1 FROM x) + SELECT * FROM x; +ERROR: recursive query "x" does not have the form non-recursive-term UNION ALL recursive-term +LINE 1: WITH RECURSIVE x(n) AS (SELECT 1 EXCEPT ALL SELECT n+1 FROM ... + ^ +-- no non-recursive term +WITH RECURSIVE x(n) AS (SELECT n FROM x) + SELECT * FROM x; +ERROR: recursive query "x" does not have the form non-recursive-term UNION ALL recursive-term +LINE 1: WITH RECURSIVE x(n) AS (SELECT n FROM x) + ^ +-- recursive term in the left hand side (strictly speaking, should allow this) +WITH RECURSIVE x(n) AS (SELECT n FROM x UNION ALL SELECT 1) + SELECT * FROM x; +ERROR: recursive reference to query "x" must not appear within its non-recursive term +LINE 1: WITH RECURSIVE x(n) AS (SELECT n FROM x UNION ALL SELECT 1) + ^ +CREATE TEMPORARY TABLE y (a INTEGER); +INSERT INTO y SELECT generate_series(1, 10); +-- LEFT JOIN +WITH RECURSIVE x(n) AS (SELECT a FROM y WHERE a = 1 + UNION ALL + SELECT x.n+1 FROM y LEFT JOIN x ON x.n = y.a WHERE n < 10) +SELECT * FROM x; +ERROR: recursive reference to query "x" must not appear within an outer join +LINE 3: SELECT x.n+1 FROM y LEFT JOIN x ON x.n = y.a WHERE n < 10) + ^ +-- RIGHT JOIN +WITH RECURSIVE x(n) AS (SELECT a FROM y WHERE a = 1 + UNION ALL + SELECT x.n+1 FROM x RIGHT JOIN y ON x.n = y.a WHERE n < 10) +SELECT * FROM x; +ERROR: recursive reference to query "x" must not appear within an outer join +LINE 3: SELECT x.n+1 FROM x RIGHT JOIN y ON x.n = y.a WHERE n < 10) + ^ +-- FULL JOIN +WITH RECURSIVE x(n) AS (SELECT a FROM y WHERE a = 1 + UNION ALL + SELECT x.n+1 FROM x FULL JOIN y ON x.n = y.a WHERE n < 10) +SELECT * FROM x; +ERROR: recursive reference to query "x" must not appear within an outer join +LINE 3: SELECT x.n+1 FROM x FULL JOIN y ON x.n = y.a WHERE n < 10) + ^ +-- subquery +WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x + WHERE n IN (SELECT * FROM x)) + SELECT * FROM x; +ERROR: recursive reference to query "x" must not appear within a subquery +LINE 2: WHERE n IN (SELECT * FROM x)) + ^ +-- aggregate functions +WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT count(*) FROM x) + SELECT * FROM x; +ERROR: aggregates not allowed in a recursive query's recursive term +LINE 1: WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT count(*) F... + ^ +WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT sum(n) FROM x) + SELECT * FROM x; +ERROR: aggregates not allowed in a recursive query's recursive term +LINE 1: WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT sum(n) FRO... + ^ +-- ORDER BY +WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x ORDER BY 1) + SELECT * FROM x; +ERROR: ORDER BY in a recursive query is not implemented +LINE 1: ...VE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x ORDER BY 1) + ^ +-- LIMIT/OFFSET +WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x LIMIT 10 OFFSET 1) + SELECT * FROM x; +ERROR: OFFSET in a recursive query is not implemented +LINE 1: ... AS (SELECT 1 UNION ALL SELECT n+1 FROM x LIMIT 10 OFFSET 1) + ^ +-- FOR UPDATE +WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x FOR UPDATE) + SELECT * FROM x; +ERROR: FOR UPDATE/SHARE in a recursive query is not implemented +-- target list has a recursive query name +WITH RECURSIVE x(id) AS (values (1) + UNION ALL + SELECT (SELECT * FROM x) FROM x WHERE id < 5 +) SELECT * FROM x; +ERROR: recursive reference to query "x" must not appear within a subquery +LINE 3: SELECT (SELECT * FROM x) FROM x WHERE id < 5 + ^ +-- mutual recursive query (not implemented) +WITH RECURSIVE + x (id) AS (SELECT 1 UNION ALL SELECT id+1 FROM y WHERE id < 5), + y (id) AS (SELECT 1 UNION ALL SELECT id+1 FROM x WHERE id < 5) +SELECT * FROM x; +ERROR: mutual recursion between WITH items is not implemented +LINE 2: x (id) AS (SELECT 1 UNION ALL SELECT id+1 FROM y WHERE id ... + ^ +-- non-linear recursion is not allowed +WITH RECURSIVE foo(i) AS + (values (1) + UNION ALL + (SELECT i+1 FROM foo WHERE i < 10 + UNION ALL + SELECT i+1 FROM foo WHERE i < 5) +) SELECT * FROM foo; +ERROR: recursive reference to query "foo" must not appear more than once +LINE 6: SELECT i+1 FROM foo WHERE i < 5) + ^ +WITH RECURSIVE foo(i) AS + (values (1) + UNION ALL + SELECT * FROM + (SELECT i+1 FROM foo WHERE i < 10 + UNION ALL + SELECT i+1 FROM foo WHERE i < 5) AS t +) SELECT * FROM foo; +ERROR: recursive reference to query "foo" must not appear more than once +LINE 7: SELECT i+1 FROM foo WHERE i < 5) AS t + ^ +WITH RECURSIVE foo(i) AS + (values (1) + UNION ALL + (SELECT i+1 FROM foo WHERE i < 10 + EXCEPT + SELECT i+1 FROM foo WHERE i < 5) +) SELECT * FROM foo; +ERROR: recursive reference to query "foo" must not appear within EXCEPT +LINE 6: SELECT i+1 FROM foo WHERE i < 5) + ^ +WITH RECURSIVE foo(i) AS + (values (1) + UNION ALL + (SELECT i+1 FROM foo WHERE i < 10 + INTERSECT + SELECT i+1 FROM foo WHERE i < 5) +) SELECT * FROM foo; +ERROR: recursive reference to query "foo" must not appear more than once +LINE 6: SELECT i+1 FROM foo WHERE i < 5) + ^ +-- Wrong type induced from non-recursive term +WITH RECURSIVE foo(i) AS + (SELECT i FROM (VALUES(1),(2)) t(i) + UNION ALL + SELECT (i+1)::numeric(10,0) FROM foo WHERE i < 10) +SELECT * FROM foo; +ERROR: recursive query "foo" column 1 has type integer in non-recursive term but type numeric overall +LINE 2: (SELECT i FROM (VALUES(1),(2)) t(i) + ^ +HINT: Cast the output of the non-recursive term to the correct type. +-- rejects different typmod, too (should we allow this?) +WITH RECURSIVE foo(i) AS + (SELECT i::numeric(3,0) FROM (VALUES(1),(2)) t(i) + UNION ALL + SELECT (i+1)::numeric(10,0) FROM foo WHERE i < 10) +SELECT * FROM foo; +ERROR: recursive query "foo" column 1 has type numeric(3,0) in non-recursive term but type numeric overall +LINE 2: (SELECT i::numeric(3,0) FROM (VALUES(1),(2)) t(i) + ^ +HINT: Cast the output of the non-recursive term to the correct type. diff --git a/src/test/regress/parallel_schedule b/src/test/regress/parallel_schedule index c00604ede5..d822005873 100644 --- a/src/test/regress/parallel_schedule +++ b/src/test/regress/parallel_schedule @@ -1,5 +1,5 @@ # ---------- -# $PostgreSQL: pgsql/src/test/regress/parallel_schedule,v 1.48 2008/10/03 15:37:18 petere Exp $ +# $PostgreSQL: pgsql/src/test/regress/parallel_schedule,v 1.49 2008/10/04 21:56:55 tgl Exp $ # # By convention, we put no more than twenty tests in any one parallel group; # this limits the number of connections needed to run the tests. @@ -83,7 +83,7 @@ test: select_views portals_p2 rules foreign_key cluster dependency guc bitmapops # Another group of parallel tests # ---------- # "plpgsql" cannot run concurrently with "rules", nor can "plancache" -test: plancache limit plpgsql copy2 temp domain rangefuncs prepare without_oid conversion truncate alter_table sequence polymorphism rowtypes returning largeobject xml +test: plancache limit plpgsql copy2 temp domain rangefuncs prepare without_oid conversion truncate alter_table sequence polymorphism rowtypes returning largeobject with xml # run stats by itself because its delay may be insufficient under heavy load test: stats diff --git a/src/test/regress/serial_schedule b/src/test/regress/serial_schedule index 88d0aba5f3..f90a404235 100644 --- a/src/test/regress/serial_schedule +++ b/src/test/regress/serial_schedule @@ -1,4 +1,4 @@ -# $PostgreSQL: pgsql/src/test/regress/serial_schedule,v 1.45 2008/10/03 15:37:18 petere Exp $ +# $PostgreSQL: pgsql/src/test/regress/serial_schedule,v 1.46 2008/10/04 21:56:55 tgl Exp $ # This should probably be in an order similar to parallel_schedule. test: boolean test: char @@ -114,6 +114,7 @@ test: polymorphism test: rowtypes test: returning test: largeobject +test: with test: xml test: stats test: tablespace diff --git a/src/test/regress/sql/with.sql b/src/test/regress/sql/with.sql new file mode 100644 index 0000000000..0ad59abdc9 --- /dev/null +++ b/src/test/regress/sql/with.sql @@ -0,0 +1,387 @@ +-- +-- Tests for common table expressions (WITH query, ... SELECT ...) +-- + +-- Basic WITH +WITH q1(x,y) AS (SELECT 1,2) +SELECT * FROM q1, q1 AS q2; + +-- Multiple uses are evaluated only once +SELECT count(*) FROM ( + WITH q1(x) AS (SELECT random() FROM generate_series(1, 5)) + SELECT * FROM q1 + UNION + SELECT * FROM q1 +) ss; + +-- WITH RECURSIVE + +-- sum of 1..100 +WITH RECURSIVE t(n) AS ( + VALUES (1) +UNION ALL + SELECT n+1 FROM t WHERE n < 100 +) +SELECT sum(n) FROM t; + +WITH RECURSIVE t(n) AS ( + SELECT (VALUES(1)) +UNION ALL + SELECT n+1 FROM t WHERE n < 5 +) +SELECT * FROM t; + +-- This'd be an infinite loop, but outside query reads only as much as needed +WITH RECURSIVE t(n) AS ( + VALUES (1) +UNION ALL + SELECT n+1 FROM t) +SELECT * FROM t LIMIT 10; + +-- +-- Some examples with a tree +-- +-- department structure represented here is as follows: +-- +-- ROOT-+->A-+->B-+->C +-- | | +-- | +->D-+->F +-- +->E-+->G + +CREATE TEMP TABLE department ( + id INTEGER PRIMARY KEY, -- department ID + parent_department INTEGER REFERENCES department, -- upper department ID + name TEXT -- department name +); + +INSERT INTO department VALUES (0, NULL, 'ROOT'); +INSERT INTO department VALUES (1, 0, 'A'); +INSERT INTO department VALUES (2, 1, 'B'); +INSERT INTO department VALUES (3, 2, 'C'); +INSERT INTO department VALUES (4, 2, 'D'); +INSERT INTO department VALUES (5, 0, 'E'); +INSERT INTO department VALUES (6, 4, 'F'); +INSERT INTO department VALUES (7, 5, 'G'); + + +-- extract all departments under 'A'. Result should be A, B, C, D and F +WITH RECURSIVE subdepartment AS +( + -- non recursive term + SELECT * FROM department WHERE name = 'A' + + UNION ALL + + -- recursive term + SELECT d.* FROM department AS d, subdepartment AS sd + WHERE d.parent_department = sd.id +) +SELECT * FROM subdepartment ORDER BY name; + +-- extract all departments under 'A' with "level" number +WITH RECURSIVE subdepartment(level, id, parent_department, name) AS +( + -- non recursive term + SELECT 1, * FROM department WHERE name = 'A' + + UNION ALL + + -- recursive term + SELECT sd.level + 1, d.* FROM department AS d, subdepartment AS sd + WHERE d.parent_department = sd.id +) +SELECT * FROM subdepartment ORDER BY name; + +-- extract all departments under 'A' with "level" number. +-- Only shows level 2 or more +WITH RECURSIVE subdepartment(level, id, parent_department, name) AS +( + -- non recursive term + SELECT 1, * FROM department WHERE name = 'A' + + UNION ALL + + -- recursive term + SELECT sd.level + 1, d.* FROM department AS d, subdepartment AS sd + WHERE d.parent_department = sd.id +) +SELECT * FROM subdepartment WHERE level >= 2 ORDER BY name; + +-- "RECURSIVE" is ignored if the query has no self-reference +WITH RECURSIVE subdepartment AS +( + -- note lack of recursive UNION structure + SELECT * FROM department WHERE name = 'A' +) +SELECT * FROM subdepartment ORDER BY name; + +-- inside subqueries +SELECT count(*) FROM ( + WITH RECURSIVE t(n) AS ( + SELECT 1 UNION ALL SELECT n + 1 FROM t WHERE n < 500 + ) + SELECT * FROM t) AS t WHERE n < ( + SELECT count(*) FROM ( + WITH RECURSIVE t(n) AS ( + SELECT 1 UNION ALL SELECT n + 1 FROM t WHERE n < 100 + ) + SELECT * FROM t WHERE n < 50000 + ) AS t WHERE n < 100); + +-- use same CTE twice at different subquery levels +WITH q1(x,y) AS ( + SELECT hundred, sum(ten) FROM tenk1 GROUP BY hundred + ) +SELECT count(*) FROM q1 WHERE y > (SELECT sum(y)/100 FROM q1 qsub); + +-- via a VIEW +CREATE TEMPORARY VIEW vsubdepartment AS + WITH RECURSIVE subdepartment AS + ( + -- non recursive term + SELECT * FROM department WHERE name = 'A' + UNION ALL + -- recursive term + SELECT d.* FROM department AS d, subdepartment AS sd + WHERE d.parent_department = sd.id + ) + SELECT * FROM subdepartment; + +SELECT * FROM vsubdepartment ORDER BY name; + +-- Check reverse listing +SELECT pg_get_viewdef('vsubdepartment'::regclass); +SELECT pg_get_viewdef('vsubdepartment'::regclass, true); + +-- recursive term has sub-UNION +WITH RECURSIVE t(i,j) AS ( + VALUES (1,2) + UNION ALL + SELECT t2.i, t.j+1 FROM + (SELECT 2 AS i UNION ALL SELECT 3 AS i) AS t2 + JOIN t ON (t2.i = t.i+1)) + + SELECT * FROM t; + +-- +-- different tree example +-- +CREATE TEMPORARY TABLE tree( + id INTEGER PRIMARY KEY, + parent_id INTEGER REFERENCES tree(id) +); + +INSERT INTO tree +VALUES (1, NULL), (2, 1), (3,1), (4,2), (5,2), (6,2), (7,3), (8,3), + (9,4), (10,4), (11,7), (12,7), (13,7), (14, 9), (15,11), (16,11); + +-- +-- get all paths from "second level" nodes to leaf nodes +-- +WITH RECURSIVE t(id, path) AS ( + VALUES(1,ARRAY[]::integer[]) +UNION ALL + SELECT tree.id, t.path || tree.id + FROM tree JOIN t ON (tree.parent_id = t.id) +) +SELECT t1.*, t2.* FROM t AS t1 JOIN t AS t2 ON + (t1.path[1] = t2.path[1] AND + array_upper(t1.path,1) = 1 AND + array_upper(t2.path,1) > 1) + ORDER BY t1.id, t2.id; + +-- just count 'em +WITH RECURSIVE t(id, path) AS ( + VALUES(1,ARRAY[]::integer[]) +UNION ALL + SELECT tree.id, t.path || tree.id + FROM tree JOIN t ON (tree.parent_id = t.id) +) +SELECT t1.id, count(t2.*) FROM t AS t1 JOIN t AS t2 ON + (t1.path[1] = t2.path[1] AND + array_upper(t1.path,1) = 1 AND + array_upper(t2.path,1) > 1) + GROUP BY t1.id + ORDER BY t1.id; + +-- +-- test multiple WITH queries +-- +WITH RECURSIVE + y (id) AS (VALUES (1)), + x (id) AS (SELECT * FROM y UNION ALL SELECT id+1 FROM x WHERE id < 5) +SELECT * FROM x; + +-- forward reference OK +WITH RECURSIVE + x(id) AS (SELECT * FROM y UNION ALL SELECT id+1 FROM x WHERE id < 5), + y(id) AS (values (1)) + SELECT * FROM x; + +WITH RECURSIVE + x(id) AS + (VALUES (1) UNION ALL SELECT id+1 FROM x WHERE id < 5), + y(id) AS + (VALUES (1) UNION ALL SELECT id+1 FROM y WHERE id < 10) + SELECT y.*, x.* FROM y LEFT JOIN x USING (id); + +WITH RECURSIVE + x(id) AS + (VALUES (1) UNION ALL SELECT id+1 FROM x WHERE id < 5), + y(id) AS + (VALUES (1) UNION ALL SELECT id+1 FROM x WHERE id < 10) + SELECT y.*, x.* FROM y LEFT JOIN x USING (id); + +WITH RECURSIVE + x(id) AS + (SELECT 1 UNION ALL SELECT id+1 FROM x WHERE id < 3 ), + y(id) AS + (SELECT * FROM x UNION ALL SELECT * FROM x), + z(id) AS + (SELECT * FROM x UNION ALL SELECT id+1 FROM z WHERE id < 10) + SELECT * FROM z; + +WITH RECURSIVE + x(id) AS + (SELECT 1 UNION ALL SELECT id+1 FROM x WHERE id < 3 ), + y(id) AS + (SELECT * FROM x UNION ALL SELECT * FROM x), + z(id) AS + (SELECT * FROM y UNION ALL SELECT id+1 FROM z WHERE id < 10) + SELECT * FROM z; + +-- +-- error cases +-- + +-- UNION (should be supported someday) +WITH RECURSIVE x(n) AS (SELECT 1 UNION SELECT n+1 FROM x) + SELECT * FROM x; + +-- INTERSECT +WITH RECURSIVE x(n) AS (SELECT 1 INTERSECT SELECT n+1 FROM x) + SELECT * FROM x; + +WITH RECURSIVE x(n) AS (SELECT 1 INTERSECT ALL SELECT n+1 FROM x) + SELECT * FROM x; + +-- EXCEPT +WITH RECURSIVE x(n) AS (SELECT 1 EXCEPT SELECT n+1 FROM x) + SELECT * FROM x; + +WITH RECURSIVE x(n) AS (SELECT 1 EXCEPT ALL SELECT n+1 FROM x) + SELECT * FROM x; + +-- no non-recursive term +WITH RECURSIVE x(n) AS (SELECT n FROM x) + SELECT * FROM x; + +-- recursive term in the left hand side (strictly speaking, should allow this) +WITH RECURSIVE x(n) AS (SELECT n FROM x UNION ALL SELECT 1) + SELECT * FROM x; + +CREATE TEMPORARY TABLE y (a INTEGER); +INSERT INTO y SELECT generate_series(1, 10); + +-- LEFT JOIN + +WITH RECURSIVE x(n) AS (SELECT a FROM y WHERE a = 1 + UNION ALL + SELECT x.n+1 FROM y LEFT JOIN x ON x.n = y.a WHERE n < 10) +SELECT * FROM x; + +-- RIGHT JOIN +WITH RECURSIVE x(n) AS (SELECT a FROM y WHERE a = 1 + UNION ALL + SELECT x.n+1 FROM x RIGHT JOIN y ON x.n = y.a WHERE n < 10) +SELECT * FROM x; + +-- FULL JOIN +WITH RECURSIVE x(n) AS (SELECT a FROM y WHERE a = 1 + UNION ALL + SELECT x.n+1 FROM x FULL JOIN y ON x.n = y.a WHERE n < 10) +SELECT * FROM x; + +-- subquery +WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x + WHERE n IN (SELECT * FROM x)) + SELECT * FROM x; + +-- aggregate functions +WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT count(*) FROM x) + SELECT * FROM x; + +WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT sum(n) FROM x) + SELECT * FROM x; + +-- ORDER BY +WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x ORDER BY 1) + SELECT * FROM x; + +-- LIMIT/OFFSET +WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x LIMIT 10 OFFSET 1) + SELECT * FROM x; + +-- FOR UPDATE +WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x FOR UPDATE) + SELECT * FROM x; + +-- target list has a recursive query name +WITH RECURSIVE x(id) AS (values (1) + UNION ALL + SELECT (SELECT * FROM x) FROM x WHERE id < 5 +) SELECT * FROM x; + +-- mutual recursive query (not implemented) +WITH RECURSIVE + x (id) AS (SELECT 1 UNION ALL SELECT id+1 FROM y WHERE id < 5), + y (id) AS (SELECT 1 UNION ALL SELECT id+1 FROM x WHERE id < 5) +SELECT * FROM x; + +-- non-linear recursion is not allowed +WITH RECURSIVE foo(i) AS + (values (1) + UNION ALL + (SELECT i+1 FROM foo WHERE i < 10 + UNION ALL + SELECT i+1 FROM foo WHERE i < 5) +) SELECT * FROM foo; + +WITH RECURSIVE foo(i) AS + (values (1) + UNION ALL + SELECT * FROM + (SELECT i+1 FROM foo WHERE i < 10 + UNION ALL + SELECT i+1 FROM foo WHERE i < 5) AS t +) SELECT * FROM foo; + +WITH RECURSIVE foo(i) AS + (values (1) + UNION ALL + (SELECT i+1 FROM foo WHERE i < 10 + EXCEPT + SELECT i+1 FROM foo WHERE i < 5) +) SELECT * FROM foo; + +WITH RECURSIVE foo(i) AS + (values (1) + UNION ALL + (SELECT i+1 FROM foo WHERE i < 10 + INTERSECT + SELECT i+1 FROM foo WHERE i < 5) +) SELECT * FROM foo; + +-- Wrong type induced from non-recursive term +WITH RECURSIVE foo(i) AS + (SELECT i FROM (VALUES(1),(2)) t(i) + UNION ALL + SELECT (i+1)::numeric(10,0) FROM foo WHERE i < 10) +SELECT * FROM foo; + +-- rejects different typmod, too (should we allow this?) +WITH RECURSIVE foo(i) AS + (SELECT i::numeric(3,0) FROM (VALUES(1),(2)) t(i) + UNION ALL + SELECT (i+1)::numeric(10,0) FROM foo WHERE i < 10) +SELECT * FROM foo; -- 2.11.0