From 44d5be0e5308e951c0c5dc522b4bcacf2bcbc476 Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Sat, 4 Oct 2008 21:56:55 +0000 Subject: 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 ++--- 4 files changed, 372 insertions(+), 49 deletions(-) (limited to 'doc/src') diff --git a/doc/src/sgml/errcodes.sgml b/doc/src/sgml/errcodes.sgml index 474c0ca8da7..574e7f5fbad 100644 --- a/doc/src/sgml/errcodes.sgml +++ b/doc/src/sgml/errcodes.sgml @@ -1,4 +1,4 @@ - + <productname>PostgreSQL</productname> Error Codes @@ -990,6 +990,12 @@ grouping_error + +42P19 +INVALID RECURSION +invalid_recursion + + 42830 INVALID FOREIGN KEY diff --git a/doc/src/sgml/queries.sgml b/doc/src/sgml/queries.sgml index e3b6be4d97b..b3d72ceb7f8 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 d8ed7aef9c6..e72d9c126f6 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 ) @@ -51,6 +57,17 @@ where from_item can be one of: The general processing of SELECT is as follows: + + + 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. @@ -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 @@ -233,6 +300,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 915e859ea98..de9a86a878c 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 -- cgit v1.2.3