On 2020-09-22 20:29, Pavel Stehule wrote:
The result is correct. When I tried to use UNION instead UNION ALL, the pg crash
I fixed the crash, but UNION [DISTINCT] won't actually work here because row/record types are not hashable. I'm leaving the partial support in, but I'm documenting it as currently not supported.
looks so clause USING in cycle detection is unsupported for DB2 and Oracle - the examples from these databases doesn't work on PG without modifications
Yeah, the path clause is actually not necessary from a user's perspective, but it's required for internal bookkeeping. We could perhaps come up with a mechanism to make it invisible coming out of the CTE (maybe give the CTE a target list internally), but that seems like a separate project.
The attached patch fixes the issues you have reported (also the view issue from the other email). I have also moved the whole rewrite support to a new file to not blow up rewriteHandler.c so much.
-- Peter Eisentraut http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
From 4b36e81def50be44bd1f68247e33a22343520b5e Mon Sep 17 00:00:00 2001 From: Peter Eisentraut <pe...@eisentraut.org> Date: Fri, 9 Oct 2020 11:32:10 +0200 Subject: [PATCH v3] SEARCH and CYCLE clauses Discussion: https://www.postgresql.org/message-id/flat/db80ceee-6f97-9b4a-8ee8-3ba0c58e5...@2ndquadrant.com --- doc/src/sgml/queries.sgml | 213 ++++++- doc/src/sgml/ref/select.sgml | 44 ++ src/backend/nodes/copyfuncs.c | 39 ++ src/backend/nodes/equalfuncs.c | 35 ++ src/backend/nodes/nodeFuncs.c | 6 + src/backend/nodes/outfuncs.c | 35 ++ src/backend/nodes/readfuncs.c | 43 ++ src/backend/parser/analyze.c | 47 +- src/backend/parser/gram.y | 58 +- src/backend/parser/parse_agg.c | 7 + src/backend/parser/parse_cte.c | 117 ++++ src/backend/parser/parse_expr.c | 4 + src/backend/parser/parse_func.c | 3 + src/backend/parser/parse_relation.c | 54 +- src/backend/parser/parse_target.c | 21 +- src/backend/rewrite/Makefile | 1 + src/backend/rewrite/rewriteHandler.c | 18 + src/backend/rewrite/rewriteSearchCycle.c | 709 +++++++++++++++++++++++ src/backend/utils/adt/ruleutils.c | 47 ++ src/include/nodes/nodes.h | 2 + src/include/nodes/parsenodes.h | 28 +- src/include/parser/analyze.h | 2 + src/include/parser/kwlist.h | 2 + src/include/parser/parse_node.h | 2 + src/include/rewrite/rewriteSearchCycle.h | 21 + src/test/regress/expected/with.out | 433 ++++++++++++++ src/test/regress/sql/with.sql | 210 +++++++ 27 files changed, 2153 insertions(+), 48 deletions(-) create mode 100644 src/backend/rewrite/rewriteSearchCycle.c create mode 100644 src/include/rewrite/rewriteSearchCycle.h diff --git a/doc/src/sgml/queries.sgml b/doc/src/sgml/queries.sgml index 77fb1991ae..34b3e48986 100644 --- a/doc/src/sgml/queries.sgml +++ b/doc/src/sgml/queries.sgml @@ -2011,6 +2011,10 @@ <title><command>SELECT</command> in <literal>WITH</literal></title> but we'd have needed two levels of nested sub-<command>SELECT</command>s. It's a bit easier to follow this way. </para> + </sect2> + + <sect2 id="queries-with-recursive"> + <title>Recursive Queries</title> <para> <indexterm> @@ -2114,6 +2118,153 @@ <title>Recursive Query Evaluation</title> </programlisting> </para> + <sect3 id="queries-with-search"> + <title>Search Order</title> + + <para> + When computing a tree traversal using a recursive query, you might want to + order the results in either depth-first or breadth-first order. This can + be done by computing an ordering column alongside the other data columns + and using that to sort the results at the end. Note that this does not + actually control in which order the query evaluation visits the rows; that + is as always in SQL implementation-dependent. This approach merely + provides a convenient way to order the results afterwards. + </para> + + <para> + To create a depth-first order, we compute for each result row an array of + rows that we have visited so far. For example, consider the following + query that searches a table <structname>tree</structname> using a + <structfield>link</structfield> field: + +<programlisting> +WITH RECURSIVE search_tree(id, link, data) AS ( + SELECT t.id, t.link, t.data + FROM tree t + UNION ALL + SELECT t.id, t.link, t.data + FROM tree t, search_tree st + WHERE t.id = st.link +) +SELECT * FROM search_tree; +</programlisting> + + To add depth-first ordering information, you can write this: + +<programlisting> +WITH RECURSIVE search_tree(id, link, data, <emphasis>path</emphasis>) AS ( + SELECT t.id, t.link, t.data, <emphasis>ARRAY[t.id]</emphasis> + FROM tree t + UNION ALL + SELECT t.id, t.link, t.data, <emphasis>path || t.id</emphasis> + FROM tree t, search_tree st + WHERE t.id = st.link +) +SELECT * FROM search_tree <emphasis>ORDER BY path</emphasis>; +</programlisting> + </para> + + <para> + In the general case where more than one field needs to be used to identify + a row, use an array of rows. For example, if we needed to track fields + <structfield>f1</structfield> and <structfield>f2</structfield>: + +<programlisting> +WITH RECURSIVE search_tree(id, link, data, <emphasis>path</emphasis>) AS ( + SELECT t.id, t.link, t.data, <emphasis>ARRAY[ROW(t.f1, t.f2)]</emphasis> + FROM tree t + UNION ALL + SELECT t.id, t.link, t.data, <emphasis>path || ROW(t.f1, t.f2)</emphasis> + FROM tree t, search_tree st + WHERE t.id = st.link +) +SELECT * FROM search_tree <emphasis>ORDER BY path</emphasis>; +</programlisting> + </para> + + <note> + <para> + The queries shown in this and the following section involving (explicit + or implicit) <literal>ROW</literal> constructors in the target list only + support <literal>UNION ALL</literal> (not plain <literal>UNION</literal>) + in the current implementation. + </para> + </note> + + <tip> + <para> + Omit the <literal>ROW()</literal> syntax in the common case where only one + field needs to be tracked. This allows a simple array rather than a + composite-type array to be used, gaining efficiency. + </para> + </tip> + + <para> + To create a breadth-first order, you can add a column that tracks the depth + of the search, for example: + +<programlisting> +WITH RECURSIVE search_tree(id, link, data, <emphasis>level</emphasis>) AS ( + SELECT t.id, t.link, t.data, <emphasis>0</emphasis> + FROM tree t + UNION ALL + SELECT t.id, t.link, t.data, <emphasis>level + 1</emphasis> + FROM tree t, search_tree st + WHERE t.id = st.link +) +SELECT * FROM search_tree <emphasis>ORDER BY level</emphasis>; +</programlisting> + + To get a stable sort, add data columns as secondary sorting columns. + </para> + + <tip> + <para> + The recursive query evaluation algorithm produces its output in + breadth-first search order. However, this is an implementation detail and + it is perhaps unsound to rely on it. The order of the rows within each + level is certainly undefined, so some explicit ordering might be desired + in any case. + </para> + </tip> + + <para> + There is built-in syntax to compute a depth- or breadth-first sort column. + For example: + +<programlisting> +WITH RECURSIVE search_tree(id, link, data) AS ( + SELECT t.id, t.link, t.data + FROM tree t + UNION ALL + SELECT t.id, t.link, t.data + FROM tree t, search_tree st + WHERE t.id = st.link +) <emphasis>SEARCH DEPTH FIRST BY id SET ordercol</emphasis> +SELECT * FROM search_tree ORDER BY ordercol; + +WITH RECURSIVE search_tree(id, link, data) AS ( + SELECT t.id, t.link, t.data + FROM tree t + UNION ALL + SELECT t.id, t.link, t.data + FROM tree t, search_tree st + WHERE t.id = st.link +) <emphasis>SEARCH BREADTH FIRST BY id SET ordercol</emphasis> +SELECT * FROM search_tree ORDER BY ordercol; +</programlisting> + This syntax is internally expanded to something similar to the above + hand-written forms. The <literal>SEARCH</literal> clause specifies whether + depth- or breadth first search is wanted, the list of columns to track for + sorting, and a column name that will contain the result data that can be + used for sorting. That column will implicitly be added to the output rows + of the CTE. + </para> + </sect3> + + <sect3 id="queries-with-cycle"> + <title>Cycle Detection</title> + <para> When working with recursive queries it is important to be sure that the recursive part of the query will eventually return no tuples, @@ -2144,18 +2295,18 @@ <title>Recursive Query Evaluation</title> <literal>UNION ALL</literal> to <literal>UNION</literal> would not eliminate the looping. Instead we need to recognize whether we have reached the same row again while following a particular path of links. We add two columns - <structfield>path</structfield> and <structfield>cycle</structfield> to the loop-prone query: + <structfield>is_cycle</structfield> and <structfield>path</structfield> to the loop-prone query: <programlisting> -WITH RECURSIVE search_graph(id, link, data, depth, path, cycle) AS ( +WITH RECURSIVE search_graph(id, link, data, depth, is_cycle, path) AS ( SELECT g.id, g.link, g.data, 1, - ARRAY[g.id], - false + false, + ARRAY[g.id] FROM graph g UNION ALL SELECT g.id, g.link, g.data, sg.depth + 1, - path || g.id, - g.id = ANY(path) + g.id = ANY(path), + path || g.id FROM graph g, search_graph sg WHERE g.id = sg.link AND NOT cycle ) @@ -2172,15 +2323,15 @@ <title>Recursive Query Evaluation</title> compare fields <structfield>f1</structfield> and <structfield>f2</structfield>: <programlisting> -WITH RECURSIVE search_graph(id, link, data, depth, path, cycle) AS ( +WITH RECURSIVE search_graph(id, link, data, depth, is_cycle, path) AS ( SELECT g.id, g.link, g.data, 1, - ARRAY[ROW(g.f1, g.f2)], - false + false, + ARRAY[ROW(g.f1, g.f2)] FROM graph g UNION ALL SELECT g.id, g.link, g.data, sg.depth + 1, - path || ROW(g.f1, g.f2), - ROW(g.f1, g.f2) = ANY(path) + ROW(g.f1, g.f2) = ANY(path), + path || ROW(g.f1, g.f2) FROM graph g, search_graph sg WHERE g.id = sg.link AND NOT cycle ) @@ -2196,12 +2347,39 @@ <title>Recursive Query Evaluation</title> </para> </tip> + <para> + There is built-in syntax to simplify cycle detection. The above query can + also be written like this: +<programlisting> +WITH RECURSIVE search_graph(id, link, data, depth) AS ( + SELECT g.id, g.link, g.data, 1 + FROM graph g + UNION ALL + SELECT g.id, g.link, g.data, sg.depth + 1 + FROM graph g, search_graph sg + WHERE g.id = sg.link +) <emphasis>CYCLE id SET is_cycle TO true DEFAULT false USING path</emphasis> +SELECT * FROM search_graph; +</programlisting> + and it will be internally rewritten to the above form. The + <literal>CYCLE</literal> clause specifies first the list of columns to + track for cycle detection, then a column name that will show whether a + cycle has been detected, then two values to use in that column for the yes + and no cases, and finally the name of another column that will track the + path. The cycle and path columns will implicitly be added to the output + rows of the CTE. + </para> + <tip> <para> - The recursive query evaluation algorithm produces its output in - breadth-first search order. You can display the results in depth-first - search order by making the outer query <literal>ORDER BY</literal> a - <quote>path</quote> column constructed in this way. + The cycle path column is computed in the same way as the depth-first + ordering column show in the previous section. A query can have both a + <literal>SEARCH</literal> and a <literal>CYCLE</literal> clause, but a + depth-first search specification and a cycle detection specification would + create redundant computations, so it's more efficient to just use the + <literal>CYCLE</literal> clause and order by the path column. If + breadth-first ordering is wanted, then specifying both + <literal>SEARCH</literal> and <literal>CYCLE</literal> can be useful. </para> </tip> @@ -2229,6 +2407,11 @@ <title>Recursive Query Evaluation</title> outer query will usually try to fetch all of the <literal>WITH</literal> query's output anyway. </para> + </sect3> + </sect2> + + <sect2> + <title>Common Table Expression Materialization</title> <para> A useful property of <literal>WITH</literal> queries is that they are diff --git a/doc/src/sgml/ref/select.sgml b/doc/src/sgml/ref/select.sgml index b4dea9b6ac..7b79c6fe91 100644 --- a/doc/src/sgml/ref/select.sgml +++ b/doc/src/sgml/ref/select.sgml @@ -73,6 +73,8 @@ <phrase>and <replaceable class="parameter">with_query</replaceable> is:</phrase> <replaceable class="parameter">with_query_name</replaceable> [ ( <replaceable class="parameter">column_name</replaceable> [, ...] ) ] AS [ [ NOT ] MATERIALIZED ] ( <replaceable class="parameter">select</replaceable> | <replaceable class="parameter">values</replaceable> | <replaceable class="parameter">insert</replaceable> | <replaceable class="parameter">update</replaceable> | <replaceable class="parameter">delete</replaceable> ) + [ SEARCH { BREADTH | DEPTH } FIRST BY <replaceable>column_name</replaceable> [, ...] SET <replaceable>search_seq_col_name</replaceable> ] + [ CYCLE <replaceable>column_name</replaceable> [, ...] SET <replaceable>cycle_mark_col_name</replaceable> TO <replaceable>cycle_mark_value</replaceable> DEFAULT <replaceable>cycle_mark_default</replaceable> USING <replaceable>cycle_path_col_name</replaceable> ] TABLE [ ONLY ] <replaceable class="parameter">table_name</replaceable> [ * ] </synopsis> @@ -276,6 +278,48 @@ <title><literal>WITH</literal> Clause</title> queries that do not use recursion or forward references. </para> + <para> + The optional <literal>SEARCH</literal> clause computes a <firstterm>search + sequence column</firstterm> that can be used for ordering the results of a + recursive query in either breadth-first or depth-first order. The + supplied column name list specifies the row key that is to be used for + keeping track of visited rows. A column named + <replaceable>search_seq_col_name</replaceable> will be added to the result + column list of the <literal>WITH</literal> query. This column can be + ordered by in the outer query to achieve the respective ordering. See + <xref linkend="queries-with-search"/> for examples. + </para> + + <para> + The optional <literal>CYCLE</literal> clause is used to detect cycles in + recursive queries. The supplied column name list specifies the row key + that is to be used for keeping track of visited rows. A column named + <replaceable>cycle_mark_col_name</replaceable> will be added to the result + column list of the <literal>WITH</literal> query. This column will be set + to <replaceable>cycle_mark_value</replaceable> when a cycle has been + detected, else to <replaceable>cycle_mark_default</replaceable>. + Furthermore, processing of the recursive union will stop when a cycle has + been detected. <replaceable>cycle_mark_value</replaceable> and + <replaceable>cycle_mark_default</replaceable> must be constants and they + must be coercible to a common data type, and the data type must have an + inequality operator. (The SQL standard requires that they be character + strings, but PostgreSQL does not require that.) Furthermore, a column + named <replaceable>cycle_path_col_name</replaceable> will be added to the + result column list of the <literal>WITH</literal> query. This column is + used internally for tracking visited rows. See <xref + linkend="queries-with-cycle"/> for examples. + </para> + + <para> + Both the <literal>SEARCH</literal> and the <literal>CYCLE</literal> clause + are only valid for recursive <literal>WITH</literal> queries. The current + implementation only supports recursive queries using <literal>UNION + ALL</literal> (not plain <literal>UNION</literal> or equivalently + <literal>UNION DISTINCT</literal>). If both clauses are used, the column + added by the <literal>SEARCH</literal> clause appears before the columns + added by the <literal>CYCLE</literal> clause. + </para> + <para> The primary query and the <literal>WITH</literal> queries are all (notionally) executed at the same time. This implies that the effects of diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c index 0409a40b82..ed40d77a9d 100644 --- a/src/backend/nodes/copyfuncs.c +++ b/src/backend/nodes/copyfuncs.c @@ -2588,6 +2588,37 @@ _copyOnConflictClause(const OnConflictClause *from) return newnode; } +static CTESearchClause * +_copyCTESearchClause(const CTESearchClause *from) +{ + CTESearchClause *newnode = makeNode(CTESearchClause); + + COPY_NODE_FIELD(search_col_list); + COPY_SCALAR_FIELD(search_breadth_first); + COPY_STRING_FIELD(search_seq_column); + COPY_LOCATION_FIELD(location); + + return newnode; +} + +static CTECycleClause * +_copyCTECycleClause(const CTECycleClause *from) +{ + CTECycleClause *newnode = makeNode(CTECycleClause); + + COPY_NODE_FIELD(cycle_col_list); + COPY_STRING_FIELD(cycle_mark_column); + COPY_NODE_FIELD(cycle_mark_value); + COPY_NODE_FIELD(cycle_mark_default); + COPY_SCALAR_FIELD(cycle_mark_type); + COPY_SCALAR_FIELD(cycle_mark_typmod); + COPY_SCALAR_FIELD(cycle_mark_collation); + COPY_STRING_FIELD(cycle_path_column); + COPY_LOCATION_FIELD(location); + + return newnode; +} + static CommonTableExpr * _copyCommonTableExpr(const CommonTableExpr *from) { @@ -2604,6 +2635,8 @@ _copyCommonTableExpr(const CommonTableExpr *from) COPY_NODE_FIELD(ctecoltypes); COPY_NODE_FIELD(ctecoltypmods); COPY_NODE_FIELD(ctecolcollations); + COPY_NODE_FIELD(search_clause); + COPY_NODE_FIELD(cycle_clause); return newnode; } @@ -5672,6 +5705,12 @@ copyObjectImpl(const void *from) case T_OnConflictClause: retval = _copyOnConflictClause(from); break; + case T_CTESearchClause: + retval = _copyCTESearchClause(from); + break; + case T_CTECycleClause: + retval = _copyCTECycleClause(from); + break; case T_CommonTableExpr: retval = _copyCommonTableExpr(from); break; diff --git a/src/backend/nodes/equalfuncs.c b/src/backend/nodes/equalfuncs.c index e2d1b987bf..6bacee3882 100644 --- a/src/backend/nodes/equalfuncs.c +++ b/src/backend/nodes/equalfuncs.c @@ -2830,6 +2830,33 @@ _equalOnConflictClause(const OnConflictClause *a, const OnConflictClause *b) return true; } +static bool +_equalCTESearchClause(const CTESearchClause *a, const CTESearchClause *b) +{ + COMPARE_NODE_FIELD(search_col_list); + COMPARE_SCALAR_FIELD(search_breadth_first); + COMPARE_STRING_FIELD(search_seq_column); + COMPARE_LOCATION_FIELD(location); + + return true; +} + +static bool +_equalCTECycleClause(const CTECycleClause *a, const CTECycleClause *b) +{ + COMPARE_NODE_FIELD(cycle_col_list); + COMPARE_STRING_FIELD(cycle_mark_column); + COMPARE_NODE_FIELD(cycle_mark_value); + COMPARE_NODE_FIELD(cycle_mark_default); + COMPARE_SCALAR_FIELD(cycle_mark_type); + COMPARE_SCALAR_FIELD(cycle_mark_typmod); + COMPARE_SCALAR_FIELD(cycle_mark_collation); + COMPARE_STRING_FIELD(cycle_path_column); + COMPARE_LOCATION_FIELD(location); + + return true; +} + static bool _equalCommonTableExpr(const CommonTableExpr *a, const CommonTableExpr *b) { @@ -2844,6 +2871,8 @@ _equalCommonTableExpr(const CommonTableExpr *a, const CommonTableExpr *b) COMPARE_NODE_FIELD(ctecoltypes); COMPARE_NODE_FIELD(ctecoltypmods); COMPARE_NODE_FIELD(ctecolcollations); + COMPARE_NODE_FIELD(search_clause); + COMPARE_NODE_FIELD(cycle_clause); return true; } @@ -3724,6 +3753,12 @@ equal(const void *a, const void *b) case T_OnConflictClause: retval = _equalOnConflictClause(a, b); break; + case T_CTESearchClause: + retval = _equalCTESearchClause(a, b); + break; + case T_CTECycleClause: + retval = _equalCTECycleClause(a, b); + break; case T_CommonTableExpr: retval = _equalCommonTableExpr(a, b); break; diff --git a/src/backend/nodes/nodeFuncs.c b/src/backend/nodes/nodeFuncs.c index 1dc873ed25..abd632a1b4 100644 --- a/src/backend/nodes/nodeFuncs.c +++ b/src/backend/nodes/nodeFuncs.c @@ -1575,6 +1575,12 @@ exprLocation(const Node *expr) case T_OnConflictClause: loc = ((const OnConflictClause *) expr)->location; break; + case T_CTESearchClause: + loc = ((const CTESearchClause *) expr)->location; + break; + case T_CTECycleClause: + loc = ((const CTECycleClause *) expr)->location; + break; case T_CommonTableExpr: loc = ((const CommonTableExpr *) expr)->location; break; diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index f0386480ab..e88aa74231 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -3047,6 +3047,33 @@ _outWithClause(StringInfo str, const WithClause *node) WRITE_LOCATION_FIELD(location); } +static void +_outCTESearchClause(StringInfo str, const CTESearchClause *node) +{ + WRITE_NODE_TYPE("CTESEARCHCLAUSE"); + + WRITE_NODE_FIELD(search_col_list); + WRITE_BOOL_FIELD(search_breadth_first); + WRITE_STRING_FIELD(search_seq_column); + WRITE_LOCATION_FIELD(location); +} + +static void +_outCTECycleClause(StringInfo str, const CTECycleClause *node) +{ + WRITE_NODE_TYPE("CTECYCLECLAUSE"); + + WRITE_NODE_FIELD(cycle_col_list); + WRITE_STRING_FIELD(cycle_mark_column); + WRITE_NODE_FIELD(cycle_mark_value); + WRITE_NODE_FIELD(cycle_mark_default); + WRITE_OID_FIELD(cycle_mark_type); + WRITE_INT_FIELD(cycle_mark_typmod); + WRITE_OID_FIELD(cycle_mark_collation); + WRITE_STRING_FIELD(cycle_path_column); + WRITE_LOCATION_FIELD(location); +} + static void _outCommonTableExpr(StringInfo str, const CommonTableExpr *node) { @@ -3063,6 +3090,8 @@ _outCommonTableExpr(StringInfo str, const CommonTableExpr *node) WRITE_NODE_FIELD(ctecoltypes); WRITE_NODE_FIELD(ctecoltypmods); WRITE_NODE_FIELD(ctecolcollations); + WRITE_NODE_FIELD(search_clause); + WRITE_NODE_FIELD(cycle_clause); } static void @@ -4233,6 +4262,12 @@ outNode(StringInfo str, const void *obj) case T_WithClause: _outWithClause(str, obj); break; + case T_CTESearchClause: + _outCTESearchClause(str, obj); + break; + case T_CTECycleClause: + _outCTECycleClause(str, obj); + break; case T_CommonTableExpr: _outCommonTableExpr(str, obj); break; diff --git a/src/backend/nodes/readfuncs.c b/src/backend/nodes/readfuncs.c index 42050ab719..43f88d6c94 100644 --- a/src/backend/nodes/readfuncs.c +++ b/src/backend/nodes/readfuncs.c @@ -409,6 +409,43 @@ _readRowMarkClause(void) READ_DONE(); } +/* + * _readCTESearchClause + */ +static CTESearchClause * +_readCTESearchClause(void) +{ + READ_LOCALS(CTESearchClause); + + READ_NODE_FIELD(search_col_list); + READ_BOOL_FIELD(search_breadth_first); + READ_STRING_FIELD(search_seq_column); + READ_LOCATION_FIELD(location); + + READ_DONE(); +} + +/* + * _readCTECycleClause + */ +static CTECycleClause * +_readCTECycleClause(void) +{ + READ_LOCALS(CTECycleClause); + + READ_NODE_FIELD(cycle_col_list); + READ_STRING_FIELD(cycle_mark_column); + READ_NODE_FIELD(cycle_mark_value); + READ_NODE_FIELD(cycle_mark_default); + READ_OID_FIELD(cycle_mark_type); + READ_INT_FIELD(cycle_mark_typmod); + READ_OID_FIELD(cycle_mark_collation); + READ_STRING_FIELD(cycle_path_column); + READ_LOCATION_FIELD(location); + + READ_DONE(); +} + /* * _readCommonTableExpr */ @@ -428,6 +465,8 @@ _readCommonTableExpr(void) READ_NODE_FIELD(ctecoltypes); READ_NODE_FIELD(ctecoltypmods); READ_NODE_FIELD(ctecolcollations); + READ_NODE_FIELD(search_clause); + READ_NODE_FIELD(cycle_clause); READ_DONE(); } @@ -2652,6 +2691,10 @@ parseNodeString(void) return_value = _readWindowClause(); else if (MATCH("ROWMARKCLAUSE", 13)) return_value = _readRowMarkClause(); + else if (MATCH("CTESEARCHCLAUSE", 15)) + return_value = _readCTESearchClause(); + else if (MATCH("CTECYCLECLAUSE", 14)) + return_value = _readCTECycleClause(); else if (MATCH("COMMONTABLEEXPR", 15)) return_value = _readCommonTableExpr(); else if (MATCH("SETOPERATIONSTMT", 16)) diff --git a/src/backend/parser/analyze.c b/src/backend/parser/analyze.c index c159fb2957..96026ab669 100644 --- a/src/backend/parser/analyze.c +++ b/src/backend/parser/analyze.c @@ -1811,6 +1811,33 @@ transformSetOperationStmt(ParseState *pstate, SelectStmt *stmt) return qry; } +/* + * Make a SortGroupClause node for a SetOperationStmt's groupClauses + */ +SortGroupClause * +makeSortGroupClauseForSetOp(Oid rescoltype) +{ + SortGroupClause *grpcl = makeNode(SortGroupClause); + Oid sortop; + Oid eqop; + bool hashable; + + /* determine the eqop and optional sortop */ + get_sort_group_operators(rescoltype, + false, true, false, + &sortop, &eqop, NULL, + &hashable); + + /* we don't have a tlist yet, so can't assign sortgrouprefs */ + grpcl->tleSortGroupRef = 0; + grpcl->eqop = eqop; + grpcl->sortop = sortop; + grpcl->nulls_first = false; /* OK with or without sortop */ + grpcl->hashable = hashable; + + return grpcl; +} + /* * transformSetOperationTree * Recursively transform leaves and internal nodes of a set-op tree @@ -2114,31 +2141,15 @@ transformSetOperationTree(ParseState *pstate, SelectStmt *stmt, */ if (op->op != SETOP_UNION || !op->all) { - SortGroupClause *grpcl = makeNode(SortGroupClause); - Oid sortop; - Oid eqop; - bool hashable; ParseCallbackState pcbstate; setup_parser_errposition_callback(&pcbstate, pstate, bestlocation); - /* determine the eqop and optional sortop */ - get_sort_group_operators(rescoltype, - false, true, false, - &sortop, &eqop, NULL, - &hashable); + op->groupClauses = lappend(op->groupClauses, + makeSortGroupClauseForSetOp(rescoltype)); cancel_parser_errposition_callback(&pcbstate); - - /* we don't have a tlist yet, so can't assign sortgrouprefs */ - grpcl->tleSortGroupRef = 0; - grpcl->eqop = eqop; - grpcl->sortop = sortop; - grpcl->nulls_first = false; /* OK with or without sortop */ - grpcl->hashable = hashable; - - op->groupClauses = lappend(op->groupClauses, grpcl); } /* diff --git a/src/backend/parser/gram.y b/src/backend/parser/gram.y index 480d168346..164dad0b89 100644 --- a/src/backend/parser/gram.y +++ b/src/backend/parser/gram.y @@ -495,6 +495,7 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query); %type <list> row explicit_row implicit_row type_list array_expr_list %type <node> case_expr case_arg when_clause case_default %type <list> when_clause_list +%type <node> opt_search_clause opt_cycle_clause %type <ival> sub_type opt_materialized %type <value> NumericOnly %type <list> NumericOnly_list @@ -631,7 +632,7 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query); ASSERTION ASSIGNMENT ASYMMETRIC AT ATTACH ATTRIBUTE AUTHORIZATION BACKWARD BEFORE BEGIN_P BETWEEN BIGINT BINARY BIT - BOOLEAN_P BOTH BY + BOOLEAN_P BOTH BREADTH BY CACHE CALL CALLED CASCADE CASCADED CASE CAST CATALOG_P CHAIN CHAR_P CHARACTER CHARACTERISTICS CHECK CHECKPOINT CLASS CLOSE @@ -643,7 +644,7 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query); CURRENT_TIME CURRENT_TIMESTAMP CURRENT_USER CURSOR CYCLE DATA_P DATABASE DAY_P DEALLOCATE DEC DECIMAL_P DECLARE DEFAULT DEFAULTS - DEFERRABLE DEFERRED DEFINER DELETE_P DELIMITER DELIMITERS DEPENDS DESC + DEFERRABLE DEFERRED DEFINER DELETE_P DELIMITER DELIMITERS DEPENDS DEPTH DESC DETACH DICTIONARY DISABLE_P DISCARD DISTINCT DO DOCUMENT_P DOMAIN_P DOUBLE_P DROP @@ -11340,8 +11341,6 @@ simple_select: * WITH [ RECURSIVE ] <query name> [ (<column>,...) ] * AS (query) [ SEARCH or CYCLE clause ] * - * We don't currently support the SEARCH or CYCLE clause. - * * Recognizing WITH_LA here allows a CTE to be named TIME or ORDINALITY. */ with_clause: @@ -11373,13 +11372,15 @@ cte_list: | cte_list ',' common_table_expr { $$ = lappend($1, $3); } ; -common_table_expr: name opt_name_list AS opt_materialized '(' PreparableStmt ')' +common_table_expr: name opt_name_list AS opt_materialized '(' PreparableStmt ')' opt_search_clause opt_cycle_clause { CommonTableExpr *n = makeNode(CommonTableExpr); n->ctename = $1; n->aliascolnames = $2; n->ctematerialized = $4; n->ctequery = $6; + n->search_clause = castNode(CTESearchClause, $8); + n->cycle_clause = castNode(CTECycleClause, $9); n->location = @1; $$ = (Node *) n; } @@ -11391,6 +11392,49 @@ opt_materialized: | /*EMPTY*/ { $$ = CTEMaterializeDefault; } ; +opt_search_clause: + SEARCH DEPTH FIRST_P BY columnList SET ColId + { + CTESearchClause *n = makeNode(CTESearchClause); + n->search_col_list = $5; + n->search_breadth_first = false; + n->search_seq_column = $7; + n->location = @1; + $$ = (Node *) n; + } + | SEARCH BREADTH FIRST_P BY columnList SET ColId + { + CTESearchClause *n = makeNode(CTESearchClause); + n->search_col_list = $5; + n->search_breadth_first = true; + n->search_seq_column = $7; + n->location = @1; + $$ = (Node *) n; + } + | /*EMPTY*/ + { + $$ = NULL; + } + ; + +opt_cycle_clause: + CYCLE columnList SET ColId TO AexprConst DEFAULT AexprConst USING ColId + { + CTECycleClause *n = makeNode(CTECycleClause); + n->cycle_col_list = $2; + n->cycle_mark_column = $4; + n->cycle_mark_value = $6; + n->cycle_mark_default = $8; + n->cycle_path_column = $10; + n->location = @1; + $$ = (Node *) n; + } + | /*EMPTY*/ + { + $$ = NULL; + } + ; + opt_with_clause: with_clause { $$ = $1; } | /*EMPTY*/ { $$ = NULL; } @@ -15079,6 +15123,7 @@ unreserved_keyword: | BACKWARD | BEFORE | BEGIN_P + | BREADTH | BY | CACHE | CALL @@ -15123,6 +15168,7 @@ unreserved_keyword: | DELIMITER | DELIMITERS | DEPENDS + | DEPTH | DETACH | DICTIONARY | DISABLE_P @@ -15590,6 +15636,7 @@ bare_label_keyword: | BIT | BOOLEAN_P | BOTH + | BREADTH | BY | CACHE | CALL @@ -15654,6 +15701,7 @@ bare_label_keyword: | DELIMITER | DELIMITERS | DEPENDS + | DEPTH | DESC | DETACH | DICTIONARY diff --git a/src/backend/parser/parse_agg.c b/src/backend/parser/parse_agg.c index 783f3fe8f2..dd3d97d85f 100644 --- a/src/backend/parser/parse_agg.c +++ b/src/backend/parser/parse_agg.c @@ -545,6 +545,10 @@ check_agglevels_and_constraints(ParseState *pstate, Node *expr) break; + case EXPR_KIND_CYCLE_MARK: + errkind = true; + break; + /* * There is intentionally no default: case here, so that the * compiler will warn if we add a new ParseExprKind without @@ -933,6 +937,9 @@ transformWindowFuncCall(ParseState *pstate, WindowFunc *wfunc, case EXPR_KIND_GENERATED_COLUMN: err = _("window functions are not allowed in column generation expressions"); break; + case EXPR_KIND_CYCLE_MARK: + errkind = true; + break; /* * There is intentionally no default: case here, so that the diff --git a/src/backend/parser/parse_cte.c b/src/backend/parser/parse_cte.c index 1fca7485ca..87dedb4c28 100644 --- a/src/backend/parser/parse_cte.c +++ b/src/backend/parser/parse_cte.c @@ -18,7 +18,10 @@ #include "catalog/pg_type.h" #include "nodes/nodeFuncs.h" #include "parser/analyze.h" +#include "parser/parse_coerce.h" +#include "parser/parse_collate.h" #include "parser/parse_cte.h" +#include "parser/parse_expr.h" #include "utils/builtins.h" #include "utils/lsyscache.h" @@ -334,6 +337,120 @@ analyzeCTE(ParseState *pstate, CommonTableExpr *cte) if (lctyp != NULL || lctypmod != NULL || lccoll != NULL) /* shouldn't happen */ elog(ERROR, "wrong number of output columns in WITH"); } + + if (cte->search_clause || cte->cycle_clause) + { + if (!cte->cterecursive) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("WITH query is not recursive"), + parser_errposition(pstate, cte->location))); + + /* + * SQL requires a WITH list element (CTE) to be "expandable" in order + * to allow a search or cycle clause. That is a stronger requirement + * than just being recursive. As of this writing, PostgreSQL only + * allows expandable CTEs as recursive CTEs anyway. In the future, + * there might be further checks required here. + */ + } + + if (cte->search_clause) + { + ListCell *lc; + List *seen = NIL; + + foreach(lc, cte->search_clause->search_col_list) + { + Value *colname = lfirst(lc); + + if (!list_member(cte->ctecolnames, colname)) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("search column \"%s\" not in WITH query column list", + strVal(colname)), + parser_errposition(pstate, cte->search_clause->location))); + + if (list_member(seen, colname)) + ereport(ERROR, + (errcode(ERRCODE_DUPLICATE_COLUMN), + errmsg("search column \"%s\" specified more than once", + strVal(colname)), + parser_errposition(pstate, cte->search_clause->location))); + seen = lappend(seen, colname); + } + + if (list_member(cte->ctecolnames, makeString(cte->search_clause->search_seq_column))) + ereport(ERROR, + errcode(ERRCODE_SYNTAX_ERROR), + errmsg("search sequence column name \"%s\" already used in WITH query column list", + cte->search_clause->search_seq_column), + parser_errposition(pstate, cte->search_clause->location)); + } + + if (cte->cycle_clause) + { + ListCell *lc; + List *seen = NIL; + int typmod1; + int typmod2; + + foreach(lc, cte->cycle_clause->cycle_col_list) + { + Value *colname = lfirst(lc); + + if (!list_member(cte->ctecolnames, colname)) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("cycle column \"%s\" not in WITH query column list", + strVal(colname)), + parser_errposition(pstate, cte->cycle_clause->location))); + + if (list_member(seen, colname)) + ereport(ERROR, + (errcode(ERRCODE_DUPLICATE_COLUMN), + errmsg("cycle column \"%s\" specified more than once", + strVal(colname)), + parser_errposition(pstate, cte->cycle_clause->location))); + seen = lappend(seen, colname); + } + + if (list_member(cte->ctecolnames, makeString(cte->cycle_clause->cycle_mark_column))) + ereport(ERROR, + errcode(ERRCODE_SYNTAX_ERROR), + errmsg("cycle column name \"%s\" already used in WITH query column list", + cte->cycle_clause->cycle_mark_column), + parser_errposition(pstate, cte->cycle_clause->location)); + + cte->cycle_clause->cycle_mark_value = transformExpr(pstate, cte->cycle_clause->cycle_mark_value, + EXPR_KIND_CYCLE_MARK); + cte->cycle_clause->cycle_mark_default = transformExpr(pstate, cte->cycle_clause->cycle_mark_default, + EXPR_KIND_CYCLE_MARK); + cte->cycle_clause->cycle_mark_type = select_common_type(pstate, + list_make2(cte->cycle_clause->cycle_mark_value, + cte->cycle_clause->cycle_mark_default), + "CYCLE", NULL); + cte->cycle_clause->cycle_mark_value = coerce_to_common_type(pstate, + cte->cycle_clause->cycle_mark_value, + cte->cycle_clause->cycle_mark_type, + "CYCLE/SET/TO"); + cte->cycle_clause->cycle_mark_default = coerce_to_common_type(pstate, + cte->cycle_clause->cycle_mark_default, + cte->cycle_clause->cycle_mark_type, + "CYCLE/SET/DEFAULT"); + + typmod1 = exprTypmod(cte->cycle_clause->cycle_mark_value); + typmod2 = exprTypmod(cte->cycle_clause->cycle_mark_default); + if (typmod1 == typmod2) + cte->cycle_clause->cycle_mark_typmod = typmod1; + else + cte->cycle_clause->cycle_mark_typmod = -1; + + cte->cycle_clause->cycle_mark_collation = select_common_collation(pstate, + list_make2(cte->cycle_clause->cycle_mark_value, + cte->cycle_clause->cycle_mark_default), + true); + } } /* diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c index d24420c583..a91ebce7ea 100644 --- a/src/backend/parser/parse_expr.c +++ b/src/backend/parser/parse_expr.c @@ -571,6 +571,7 @@ transformColumnRef(ParseState *pstate, ColumnRef *cref) case EXPR_KIND_CALL_ARGUMENT: case EXPR_KIND_COPY_WHERE: case EXPR_KIND_GENERATED_COLUMN: + case EXPR_KIND_CYCLE_MARK: /* okay */ break; @@ -1897,6 +1898,7 @@ transformSubLink(ParseState *pstate, SubLink *sublink) case EXPR_KIND_RETURNING: case EXPR_KIND_VALUES: case EXPR_KIND_VALUES_SINGLE: + case EXPR_KIND_CYCLE_MARK: /* okay */ break; case EXPR_KIND_CHECK_CONSTRAINT: @@ -3541,6 +3543,8 @@ ParseExprKindName(ParseExprKind exprKind) return "WHERE"; case EXPR_KIND_GENERATED_COLUMN: return "GENERATED AS"; + case EXPR_KIND_CYCLE_MARK: + return "CYCLE"; /* * There is intentionally no default: case here, so that the diff --git a/src/backend/parser/parse_func.c b/src/backend/parser/parse_func.c index 9c3b6ad916..57c376a4ad 100644 --- a/src/backend/parser/parse_func.c +++ b/src/backend/parser/parse_func.c @@ -2519,6 +2519,9 @@ check_srf_call_placement(ParseState *pstate, Node *last_srf, int location) case EXPR_KIND_GENERATED_COLUMN: err = _("set-returning functions are not allowed in column generation expressions"); break; + case EXPR_KIND_CYCLE_MARK: + errkind = true; + break; /* * There is intentionally no default: case here, so that the diff --git a/src/backend/parser/parse_relation.c b/src/backend/parser/parse_relation.c index a56bd86181..a5efd39499 100644 --- a/src/backend/parser/parse_relation.c +++ b/src/backend/parser/parse_relation.c @@ -2235,6 +2235,8 @@ addRangeTableEntryForCTE(ParseState *pstate, int numaliases; int varattno; ListCell *lc; + int n_dontexpand_columns = 0; + ParseNamespaceItem *psi; Assert(pstate != NULL); @@ -2267,9 +2269,9 @@ addRangeTableEntryForCTE(ParseState *pstate, parser_errposition(pstate, rv->location))); } - rte->coltypes = cte->ctecoltypes; - rte->coltypmods = cte->ctecoltypmods; - rte->colcollations = cte->ctecolcollations; + rte->coltypes = list_copy(cte->ctecoltypes); + rte->coltypmods = list_copy(cte->ctecoltypmods); + rte->colcollations = list_copy(cte->ctecolcollations); rte->alias = alias; if (alias) @@ -2294,6 +2296,34 @@ addRangeTableEntryForCTE(ParseState *pstate, rte->eref = eref; + if (cte->search_clause) + { + rte->eref->colnames = lappend(rte->eref->colnames, makeString(cte->search_clause->search_seq_column)); + if (cte->search_clause->search_breadth_first) + rte->coltypes = lappend_oid(rte->coltypes, RECORDOID); + else + rte->coltypes = lappend_oid(rte->coltypes, RECORDARRAYOID); + rte->coltypmods = lappend_int(rte->coltypmods, -1); + rte->colcollations = lappend_oid(rte->colcollations, InvalidOid); + + n_dontexpand_columns += 1; + } + + if (cte->cycle_clause) + { + rte->eref->colnames = lappend(rte->eref->colnames, makeString(cte->cycle_clause->cycle_mark_column)); + rte->coltypes = lappend_oid(rte->coltypes, cte->cycle_clause->cycle_mark_type); + rte->coltypmods = lappend_int(rte->coltypmods, cte->cycle_clause->cycle_mark_typmod); + rte->colcollations = lappend_oid(rte->colcollations, cte->cycle_clause->cycle_mark_collation); + + rte->eref->colnames = lappend(rte->eref->colnames, makeString(cte->cycle_clause->cycle_path_column)); + rte->coltypes = lappend_oid(rte->coltypes, RECORDARRAYOID); + rte->coltypmods = lappend_int(rte->coltypmods, -1); + rte->colcollations = lappend_oid(rte->colcollations, InvalidOid); + + n_dontexpand_columns += 2; + } + /* * Set flags and access permissions. * @@ -2321,9 +2351,19 @@ addRangeTableEntryForCTE(ParseState *pstate, * Build a ParseNamespaceItem, but don't add it to the pstate's namespace * list --- caller must do that if appropriate. */ - return buildNSItemFromLists(rte, list_length(pstate->p_rtable), + psi = buildNSItemFromLists(rte, list_length(pstate->p_rtable), rte->coltypes, rte->coltypmods, rte->colcollations); + + /* + * The columns added by search and cycle clauses are not included in star + * expansion in queries contained in the CTE. + */ + if (rte->ctelevelsup > 0) + for (int i = 0; i < n_dontexpand_columns; i++) + psi->p_nscolumns[list_length(psi->p_rte->eref->colnames) - 1 - i].p_dontexpand = true; + + return psi; } /* @@ -3008,7 +3048,11 @@ expandNSItemVars(ParseNamespaceItem *nsitem, const char *colname = strVal(colnameval); ParseNamespaceColumn *nscol = nsitem->p_nscolumns + colindex; - if (colname[0]) + if (nscol->p_dontexpand) + { + /* skip */ + } + else if (colname[0]) { Var *var; diff --git a/src/backend/parser/parse_target.c b/src/backend/parser/parse_target.c index 566c517837..70120bb537 100644 --- a/src/backend/parser/parse_target.c +++ b/src/backend/parser/parse_target.c @@ -409,10 +409,25 @@ markTargetListOrigin(ParseState *pstate, TargetEntry *tle, { CommonTableExpr *cte = GetCTEForRTE(pstate, rte, netlevelsup); TargetEntry *ste; + List *tl = GetCTETargetList(cte); + int extra_cols = 0; + + /* + * RTE for CTE will already have the search and cycle columns + * added, but the subquery won't, so skip looking those up. + */ + if (cte->search_clause) + extra_cols += 1; + if (cte->cycle_clause) + extra_cols += 2; + if (extra_cols && + attnum > list_length(tl) && + attnum <= list_length(tl) + extra_cols) + break; - ste = get_tle_by_resno(GetCTETargetList(cte), attnum); + ste = get_tle_by_resno(tl, attnum); if (ste == NULL || ste->resjunk) - elog(ERROR, "subquery %s does not have attribute %d", + elog(ERROR, "CTE %s does not have attribute %d", rte->eref->aliasname, attnum); tle->resorigtbl = ste->resorigtbl; tle->resorigcol = ste->resorigcol; @@ -1606,7 +1621,7 @@ expandRecordVariable(ParseState *pstate, Var *var, int levelsup) ste = get_tle_by_resno(GetCTETargetList(cte), attnum); if (ste == NULL || ste->resjunk) - elog(ERROR, "subquery %s does not have attribute %d", + elog(ERROR, "CTE %s does not have attribute %d", rte->eref->aliasname, attnum); expr = (Node *) ste->expr; if (IsA(expr, Var)) diff --git a/src/backend/rewrite/Makefile b/src/backend/rewrite/Makefile index b435b3e985..4680752e6a 100644 --- a/src/backend/rewrite/Makefile +++ b/src/backend/rewrite/Makefile @@ -17,6 +17,7 @@ OBJS = \ rewriteHandler.o \ rewriteManip.o \ rewriteRemove.o \ + rewriteSearchCycle.o \ rewriteSupport.o \ rowsecurity.o diff --git a/src/backend/rewrite/rewriteHandler.c b/src/backend/rewrite/rewriteHandler.c index fe777c3103..74b0fa7cdf 100644 --- a/src/backend/rewrite/rewriteHandler.c +++ b/src/backend/rewrite/rewriteHandler.c @@ -37,6 +37,7 @@ #include "rewrite/rewriteDefine.h" #include "rewrite/rewriteHandler.h" #include "rewrite/rewriteManip.h" +#include "rewrite/rewriteSearchCycle.h" #include "rewrite/rowsecurity.h" #include "utils/builtins.h" #include "utils/lsyscache.h" @@ -1864,6 +1865,23 @@ fireRIRrules(Query *parsetree, List *activeRIRs) int rt_index; ListCell *lc; + /* + * Expand SEARCH and CYCLE clauses in CTEs. + * + * This is just a convenient place to do this, since we are already + * looking at each Query. + */ + foreach(lc, parsetree->cteList) + { + CommonTableExpr *cte = lfirst_node(CommonTableExpr, lc); + + if (cte->search_clause || cte->cycle_clause) + { + cte = rewriteSearchAndCycle(cte); + lfirst(lc) = cte; + } + } + /* * don't try to convert this into a foreach loop, because rtable list can * get changed each time through... diff --git a/src/backend/rewrite/rewriteSearchCycle.c b/src/backend/rewrite/rewriteSearchCycle.c new file mode 100644 index 0000000000..8053fea907 --- /dev/null +++ b/src/backend/rewrite/rewriteSearchCycle.c @@ -0,0 +1,709 @@ +/*------------------------------------------------------------------------- + * + * rewriteSearchCycle.c + * Support for rewriting SEARCH and CYCLE clauses. + * + * Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * IDENTIFICATION + * src/backend/rewrite/rewriteSearchCycle.c + * + *------------------------------------------------------------------------- + */ +#include "postgres.h" + +#include "catalog/pg_operator_d.h" +#include "catalog/pg_type_d.h" +#include "nodes/makefuncs.h" +#include "nodes/pg_list.h" +#include "parser/analyze.h" +#include "parser/parsetree.h" +#include "rewrite/rewriteManip.h" +#include "rewrite/rewriteSearchCycle.h" +#include "utils/builtins.h" +#include "utils/fmgroids.h" +#include "utils/lsyscache.h" +#include "utils/typcache.h" + + +/*---------- + * Rewrite a CTE with SEARCH or CYCLE clause + * + * Consider a CTE like + * + * WITH RECURSIVE ctename (col1, col2, col3) AS ( + * query1 + * UNION [ALL] + * SELECT trosl FROM ctename + * ) + * + * With a search clause + * + * SEARCH BREADTH FIRST BY col1, col2 SET sqc + * + * the CTE is rewritten to + * + * WITH RECURSIVE ctename (col1, col2, col3, sqc) AS ( + * SELECT col1, col2, col3, -- original WITH column list + * ROW(0, col1, col2) -- initial row of search columns + * FROM (query1) "*TLOCRN*" (col1, col2, col3) + * UNION [ALL] + * SELECT col1, col2, col3, -- same as above + * ROW(sqc.level + 1, col1, col2) -- count levels + * FROM (SELECT trosl, ctename.sqc FROM ctename) "*TROCRN*" (col1, col2, col3, sqc) + * ) + * + * (This isn't quite legal SQL: sqc.level is meant to refer to the first + * column of sqc, which has a row type, but the field names are not defined + * here. Representing this properly in SQL would be more complicated (and the + * SQL standard actually does it in that more complicated way), but the + * internal representation allows us to construct it this way.) + * + * With a search caluse + * + * SEARCH DEPTH FIRST BY col1, col2 SET sqc + * + * the CTE is rewritten to + * + * WITH RECURSIVE ctename (col1, col2, col3, sqc) AS ( + * SELECT col1, col2, col3, -- original WITH column list + * ARRAY[ROW(col1, col2)] -- initial row of search columns + * FROM (query1) "*TLOCRN*" (col1, col2, col3) + * UNION [ALL] + * SELECT col1, col2, col3, -- same as above + * sqc || ARRAY[ROW(col1, col2)] -- record rows seen + * FROM (SELECT trosl, ctename.sqc FROM ctename) "*TROCRN*" (col1, col2, col3, sqc) + * ) + * + * With a cycle clause + * + * CYCLE col1, col2 SET cmc TO 'Y' DEFAULT 'N' USING cpa + * + * (cmc = cycle mark column, cpa = cycle path) the CTE is rewritten to + * + * WITH RECURSIVE ctename (col1, col2, col3, cmc, cpa) AS ( + * SELECT col1, col2, col3, -- original WITH column list + * 'N', -- cycle mark default + * ARRAY[ROW(col1, col2)] -- initial row of cycle columns + * FROM (query1) "*TLOCRN*" (col1, col2, col3) + * UNION [ALL] + * SELECT col1, col2, col3, -- same as above + * CASE WHEN ROW(col1, col2) = ANY (ARRAY[cpa]) THEN 'Y' ELSE 'N' END, -- compute cycle mark column + * cpa || ARRAY[ROW(col1, col2)] -- record rows seen + * FROM (SELECT trosl, ctename.cmc, ctename.cpa FROM ctename) "*TROCRN*" (col1, col2, col3, cmc, cpa) + * WHERE cmc <> 'Y' + * ) + * + * The expression to compute the cycle mark column in the right-hand query is + * written as + * + * CASE WHEN ROW(col1, col2) IN (SELECT p.* FROM TABLE(cpa) p) THEN cmv ELSE cmd END + * + * in the SQL standard, but in PostgreSQL we can use the scalar-array operator + * expression shown above. + * + * Also, in some of the cases where operators are shown above we actually + * directly produce the underlying function call. + * + * If both a search clause and a cycle clause is specified, then the search + * clause column is added before the cycle clause columns. + */ + +/* + * Make a RowExpr from the specified column names, which have to be among the + * output columns of the CTE. + * + * XXX We already looked up the columns in parse_cte.c. Maybe we should + * record the positions there instead of looking them up again here. + */ +static RowExpr * +make_path_rowexpr(const CommonTableExpr *cte, const List *col_list) +{ + RowExpr *rowexpr; + ListCell *lc; + + rowexpr = makeNode(RowExpr); + rowexpr->row_typeid = RECORDOID; + rowexpr->row_format = COERCE_IMPLICIT_CAST; + rowexpr->location = -1; + + foreach(lc, col_list) + { + char *colname = strVal(lfirst(lc)); + + for (int i = 0; i < list_length(cte->ctecolnames); i++) + { + char *colname2 = strVal(list_nth(cte->ctecolnames, i)); + + if (strcmp(colname, colname2) == 0) + { + Var *var; + + var = makeVar(1, i + 1, + list_nth_oid(cte->ctecoltypes, i), + list_nth_int(cte->ctecoltypmods, i), + list_nth_oid(cte->ctecolcollations, i), + 0); + rowexpr->args = lappend(rowexpr->args, var); + rowexpr->colnames = lappend(rowexpr->colnames, makeString(colname)); + break; + } + } + } + + return rowexpr; +} + +/* + * Wrap a RowExpr in an ArrayExpr, for the initial search depth first or cycle + * row. + */ +static Expr * +make_path_initial_array(RowExpr *rowexpr) +{ + ArrayExpr *arr; + + arr = makeNode(ArrayExpr); + arr->array_typeid = RECORDARRAYOID; + arr->element_typeid = RECORDOID; + arr->location = -1; + arr->elements = list_make1(rowexpr); + + return (Expr *) arr; +} + +/* + * Make an array catenation expression like + * + * cpa || ARRAY[ROW(cols)] + * + * where the varattno of cpa is provided as path_varattno. + */ +static Expr * +make_path_cat_expr(RowExpr *rowexpr, AttrNumber path_varattno) +{ + ArrayExpr *arr; + FuncExpr *fexpr; + + arr = makeNode(ArrayExpr); + arr->array_typeid = RECORDARRAYOID; + arr->element_typeid = RECORDOID; + arr->location = -1; + arr->elements = list_make1(rowexpr); + + fexpr = makeFuncExpr(F_ARRAY_CAT, RECORDARRAYOID, + list_make2(makeVar(1, path_varattno, RECORDARRAYOID, -1, 0, 0), + arr), + InvalidOid, InvalidOid, COERCE_EXPLICIT_CALL); + + return (Expr *) fexpr; +} + +/* + * The real work happens here. + */ +CommonTableExpr * +rewriteSearchAndCycle(CommonTableExpr *cte) +{ + Query *ctequery; + SetOperationStmt *sos; + int rti1, + rti2; + RangeTblEntry *rte1, + *rte2, + *newrte; + Query *newq1, + *newq2; + Query *newsubquery; + RangeTblRef *rtr; + Oid search_seq_type = InvalidOid; + AttrNumber sqc_attno = InvalidAttrNumber; + AttrNumber cmc_attno = InvalidAttrNumber; + AttrNumber cpa_attno = InvalidAttrNumber; + TargetEntry *tle; + RowExpr *cycle_col_rowexpr = NULL; + RowExpr *search_col_rowexpr = NULL; + List *ewcl; + int cte_rtindex = -1; + + Assert(cte->search_clause || cte->cycle_clause); + + cte = copyObject(cte); + + ctequery = castNode(Query, cte->ctequery); + + /* + * The top level of the CTE's query should be a UNION. Find the two + * subqueries. + */ + Assert(ctequery->setOperations); + sos = castNode(SetOperationStmt, ctequery->setOperations); + Assert(sos->op == SETOP_UNION); + + /* + * XXX The SEARCH and CYCLE clauses won't currently work with UNION + * DISTINCT, because the record and _record types are not hashable. This + * would result in a perhaps slightly confusing error message later, so + * we'll give a more precise message here. If that restriction is ever + * lifted, this can be removed. + */ + if (!sos->all) + { + if (cte->search_clause) + ereport(ERROR, + errcode(ERRCODE_FEATURE_NOT_SUPPORTED), + errmsg("SEARCH clause not supported with UNION DISTINCT")); + if (cte->cycle_clause) + ereport(ERROR, + errcode(ERRCODE_FEATURE_NOT_SUPPORTED), + errmsg("CYCLE clause not supported with UNION DISTINCT")); + } + + rti1 = castNode(RangeTblRef, sos->larg)->rtindex; + rti2 = castNode(RangeTblRef, sos->rarg)->rtindex; + + rte1 = rt_fetch(rti1, ctequery->rtable); + rte2 = rt_fetch(rti2, ctequery->rtable); + + Assert(rte1->rtekind == RTE_SUBQUERY); + Assert(rte2->rtekind == RTE_SUBQUERY); + + /* + * We'll need this a few times later. + */ + if (cte->search_clause) + { + if (cte->search_clause->search_breadth_first) + search_seq_type = RECORDOID; + else + search_seq_type = RECORDARRAYOID; + } + + /* + * Attribute numbers of the added columns in the CTE's column list + */ + if (cte->search_clause) + sqc_attno = list_length(cte->ctecolnames) + 1; + if (cte->cycle_clause) + { + cmc_attno = list_length(cte->ctecolnames) + 1; + cpa_attno = list_length(cte->ctecolnames) + 2; + if (cte->search_clause) + { + cmc_attno++; + cpa_attno++; + } + } + + /* + * Make new left subquery + */ + newq1 = makeNode(Query); + newq1->commandType = CMD_SELECT; + newq1->canSetTag = true; + + newrte = makeNode(RangeTblEntry); + newrte->rtekind = RTE_SUBQUERY; + newrte->alias = makeAlias("*TLOCRN*", cte->ctecolnames); + newrte->eref = newrte->alias; + newsubquery = copyObject(rte1->subquery); + IncrementVarSublevelsUp((Node *) newsubquery, 1, 1); + newrte->subquery = newsubquery; + newrte->inFromCl = true; + newq1->rtable = list_make1(newrte); + + rtr = makeNode(RangeTblRef); + rtr->rtindex = 1; + newq1->jointree = makeFromExpr(list_make1(rtr), NULL); + + /* + * Make target list + */ + for (int i = 0; i < list_length(cte->ctecolnames); i++) + { + Var *var; + + var = makeVar(1, i + 1, + list_nth_oid(cte->ctecoltypes, i), + list_nth_int(cte->ctecoltypmods, i), + list_nth_oid(cte->ctecolcollations, i), + 0); + tle = makeTargetEntry((Expr *) var, i + 1, strVal(list_nth(cte->ctecolnames, i)), false); + tle->resorigtbl = castNode(TargetEntry, list_nth(rte1->subquery->targetList, i))->resorigtbl; + tle->resorigcol = castNode(TargetEntry, list_nth(rte1->subquery->targetList, i))->resorigcol; + newq1->targetList = lappend(newq1->targetList, tle); + } + + if (cte->search_clause) + { + Expr *texpr; + + search_col_rowexpr = make_path_rowexpr(cte, cte->search_clause->search_col_list); + if (cte->search_clause->search_breadth_first) + { + search_col_rowexpr->args = lcons(makeConst(INT8OID, -1, InvalidOid, sizeof(int64), + Int64GetDatum(0), false, FLOAT8PASSBYVAL), + search_col_rowexpr->args); + search_col_rowexpr->colnames = lcons(makeString("*LEVEL*"), search_col_rowexpr->colnames); + texpr = (Expr *) search_col_rowexpr; + } + else + texpr = make_path_initial_array(search_col_rowexpr); + tle = makeTargetEntry(texpr, + list_length(newq1->targetList) + 1, + cte->search_clause->search_seq_column, + false); + newq1->targetList = lappend(newq1->targetList, tle); + } + if (cte->cycle_clause) + { + tle = makeTargetEntry((Expr *) cte->cycle_clause->cycle_mark_default, + list_length(newq1->targetList) + 1, + cte->cycle_clause->cycle_mark_column, + false); + newq1->targetList = lappend(newq1->targetList, tle); + cycle_col_rowexpr = make_path_rowexpr(cte, cte->cycle_clause->cycle_col_list); + tle = makeTargetEntry(make_path_initial_array(cycle_col_rowexpr), + list_length(newq1->targetList) + 1, + cte->cycle_clause->cycle_path_column, + false); + newq1->targetList = lappend(newq1->targetList, tle); + } + + rte1->subquery = newq1; + + if (cte->search_clause) + { + rte1->eref->colnames = lappend(rte1->eref->colnames, makeString(cte->search_clause->search_seq_column)); + } + if (cte->cycle_clause) + { + rte1->eref->colnames = lappend(rte1->eref->colnames, makeString(cte->cycle_clause->cycle_mark_column)); + rte1->eref->colnames = lappend(rte1->eref->colnames, makeString(cte->cycle_clause->cycle_path_column)); + } + + /* + * Make new right subquery + */ + newq2 = makeNode(Query); + newq2->commandType = CMD_SELECT; + newq2->canSetTag = true; + + newrte = makeNode(RangeTblEntry); + newrte->rtekind = RTE_SUBQUERY; + ewcl = copyObject(cte->ctecolnames); + if (cte->search_clause) + { + ewcl = lappend(ewcl, makeString(cte->search_clause->search_seq_column)); + } + if (cte->cycle_clause) + { + ewcl = lappend(ewcl, makeString(cte->cycle_clause->cycle_mark_column)); + ewcl = lappend(ewcl, makeString(cte->cycle_clause->cycle_path_column)); + } + newrte->alias = makeAlias("*TROCRN*", ewcl); + newrte->eref = newrte->alias; + + /* + * Find the reference to our CTE in the range table + */ + for (int rti = 1; rti <= list_length(rte2->subquery->rtable); rti++) + { + RangeTblEntry *e = rt_fetch(rti, rte2->subquery->rtable); + + if (e->rtekind == RTE_CTE && strcmp(cte->ctename, e->ctename) == 0) + { + cte_rtindex = rti; + break; + } + } + Assert(cte_rtindex > 0); + + newsubquery = copyObject(rte2->subquery); + IncrementVarSublevelsUp((Node *) newsubquery, 1, 1); + + /* + * Add extra columns to target list of subquery of right subquery + */ + if (cte->search_clause) + { + Var *var; + + /* ctename.sqc */ + var = makeVar(cte_rtindex, sqc_attno, + search_seq_type, -1, InvalidOid, 0); + tle = makeTargetEntry((Expr *) var, + list_length(newsubquery->targetList) + 1, + cte->search_clause->search_seq_column, + false); + newsubquery->targetList = lappend(newsubquery->targetList, tle); + } + if (cte->cycle_clause) + { + Var *var; + + /* ctename.cmc */ + var = makeVar(cte_rtindex, cmc_attno, + cte->cycle_clause->cycle_mark_type, + cte->cycle_clause->cycle_mark_typmod, + cte->cycle_clause->cycle_mark_collation, 0); + tle = makeTargetEntry((Expr *) var, + list_length(newsubquery->targetList) + 1, + cte->cycle_clause->cycle_mark_column, + false); + newsubquery->targetList = lappend(newsubquery->targetList, tle); + + /* ctename.cpa */ + var = makeVar(cte_rtindex, cpa_attno, + RECORDARRAYOID, -1, InvalidOid, 0); + tle = makeTargetEntry((Expr *) var, + list_length(newsubquery->targetList) + 1, + cte->cycle_clause->cycle_path_column, + false); + newsubquery->targetList = lappend(newsubquery->targetList, tle); + } + + newrte->subquery = newsubquery; + newrte->inFromCl = true; + newq2->rtable = list_make1(newrte); + + rtr = makeNode(RangeTblRef); + rtr->rtindex = 1; + + if (cte->cycle_clause) + { + TypeCacheEntry *typentry; + Oid op; + OpExpr *opexpr; + + /* + * Add cmc <> cmv condition + */ + + typentry = lookup_type_cache(cte->cycle_clause->cycle_mark_type, TYPECACHE_EQ_OPR); + if (!typentry->eq_opr) + ereport(ERROR, + errcode(ERRCODE_UNDEFINED_FUNCTION), + errmsg("could not identify an equality operator for type %s", + format_type_be(cte->cycle_clause->cycle_mark_type))); + op = get_negator(typentry->eq_opr); + if (!op) + ereport(ERROR, + errcode(ERRCODE_UNDEFINED_FUNCTION), + errmsg("could not identify an inequality operator for type %s", + format_type_be(cte->cycle_clause->cycle_mark_type))); + + opexpr = makeNode(OpExpr); + opexpr->location = -1; + opexpr->opno = op; + opexpr->opresulttype = BOOLOID; + opexpr->inputcollid = cte->cycle_clause->cycle_mark_collation; + opexpr->args = list_make2(makeVar(1, cmc_attno, + cte->cycle_clause->cycle_mark_type, + cte->cycle_clause->cycle_mark_typmod, + cte->cycle_clause->cycle_mark_collation, 0), + cte->cycle_clause->cycle_mark_value); + + newq2->jointree = makeFromExpr(list_make1(rtr), (Node *) opexpr); + } + else + newq2->jointree = makeFromExpr(list_make1(rtr), NULL); + + /* + * Make target list + */ + for (int i = 0; i < list_length(cte->ctecolnames); i++) + { + Var *var; + + var = makeVar(1, i + 1, + list_nth_oid(cte->ctecoltypes, i), + list_nth_int(cte->ctecoltypmods, i), + list_nth_oid(cte->ctecolcollations, i), + 0); + tle = makeTargetEntry((Expr *) var, i + 1, strVal(list_nth(cte->ctecolnames, i)), false); + tle->resorigtbl = castNode(TargetEntry, list_nth(rte2->subquery->targetList, i))->resorigtbl; + tle->resorigcol = castNode(TargetEntry, list_nth(rte2->subquery->targetList, i))->resorigcol; + newq2->targetList = lappend(newq2->targetList, tle); + } + + if (cte->search_clause) + { + Expr *texpr; + + if (cte->search_clause->search_breadth_first) + { + FieldSelect *fs; + FuncExpr *fexpr; + + /* + * ROW(sqc.level + 1, cols) + */ + + search_col_rowexpr = copyObject(search_col_rowexpr); + + fs = makeNode(FieldSelect); + fs->arg = (Expr *) makeVar(1, sqc_attno, RECORDOID, -1, 0, 0); + fs->fieldnum = 1; + fs->resulttype = INT8OID; + fs->resulttypmod = -1; + + fexpr = makeFuncExpr(F_INT8INC, INT8OID, list_make1(fs), InvalidOid, InvalidOid, COERCE_EXPLICIT_CALL); + + lfirst(list_head(search_col_rowexpr->args)) = fexpr; + + texpr = (Expr *) search_col_rowexpr; + } + else + { + /* + * sqc || ARRAY[ROW(cols)] + */ + texpr = make_path_cat_expr(search_col_rowexpr, sqc_attno); + } + tle = makeTargetEntry(texpr, + list_length(newq2->targetList) + 1, + cte->search_clause->search_seq_column, + false); + newq2->targetList = lappend(newq2->targetList, tle); + } + + if (cte->cycle_clause) + { + ScalarArrayOpExpr *saoe; + CaseExpr *caseexpr; + CaseWhen *casewhen; + + /* + * CASE WHEN ROW(cols) = ANY (ARRAY[cpa]) THEN cmv ELSE cmd END + */ + + saoe = makeNode(ScalarArrayOpExpr); + saoe->location = -1; + saoe->opno = RECORD_EQ_OP; + saoe->useOr = true; + saoe->args = list_make2(cycle_col_rowexpr, + makeVar(1, cpa_attno, RECORDARRAYOID, -1, 0, 0)); + + caseexpr = makeNode(CaseExpr); + caseexpr->location = -1; + caseexpr->casetype = cte->cycle_clause->cycle_mark_type; + caseexpr->casecollid = cte->cycle_clause->cycle_mark_collation; + casewhen = makeNode(CaseWhen); + casewhen->location = -1; + casewhen->expr = (Expr *) saoe; + casewhen->result = (Expr *) cte->cycle_clause->cycle_mark_value; + caseexpr->args = list_make1(casewhen); + caseexpr->defresult = (Expr *) cte->cycle_clause->cycle_mark_default; + + tle = makeTargetEntry((Expr *) caseexpr, + list_length(newq2->targetList) + 1, + cte->cycle_clause->cycle_mark_column, + false); + newq2->targetList = lappend(newq2->targetList, tle); + + /* + * cpa || ARRAY[ROW(cols)] + */ + tle = makeTargetEntry(make_path_cat_expr(cycle_col_rowexpr, cpa_attno), + list_length(newq2->targetList) + 1, + cte->cycle_clause->cycle_path_column, + false); + newq2->targetList = lappend(newq2->targetList, tle); + } + + rte2->subquery = newq2; + + if (cte->search_clause) + { + rte2->eref->colnames = lappend(rte2->eref->colnames, makeString(cte->search_clause->search_seq_column)); + } + if (cte->cycle_clause) + { + rte2->eref->colnames = lappend(rte2->eref->colnames, makeString(cte->cycle_clause->cycle_mark_column)); + rte2->eref->colnames = lappend(rte2->eref->colnames, makeString(cte->cycle_clause->cycle_path_column)); + } + + /* + * Add the additional columns to the SetOperationStmt + */ + if (cte->search_clause) + { + sos->colTypes = lappend_oid(sos->colTypes, search_seq_type); + sos->colTypmods = lappend_int(sos->colTypmods, -1); + sos->colCollations = lappend_oid(sos->colCollations, InvalidOid); + if (!sos->all) + sos->groupClauses = lappend(sos->groupClauses, + makeSortGroupClauseForSetOp(search_seq_type)); + } + if (cte->cycle_clause) + { + sos->colTypes = lappend_oid(sos->colTypes, cte->cycle_clause->cycle_mark_type); + sos->colTypmods = lappend_int(sos->colTypmods, cte->cycle_clause->cycle_mark_typmod); + sos->colCollations = lappend_oid(sos->colCollations, cte->cycle_clause->cycle_mark_collation); + if (!sos->all) + sos->groupClauses = lappend(sos->groupClauses, + makeSortGroupClauseForSetOp(cte->cycle_clause->cycle_mark_type)); + + sos->colTypes = lappend_oid(sos->colTypes, RECORDARRAYOID); + sos->colTypmods = lappend_int(sos->colTypmods, -1); + sos->colCollations = lappend_oid(sos->colCollations, InvalidOid); + if (!sos->all) + sos->groupClauses = lappend(sos->groupClauses, + makeSortGroupClauseForSetOp(RECORDARRAYOID)); + } + + /* + * Add the additional columns to the CTE query's target list + */ + if (cte->search_clause) + { + ctequery->targetList = lappend(ctequery->targetList, + makeTargetEntry((Expr *) makeVar(1, sqc_attno, + search_seq_type, -1, InvalidOid, 0), + list_length(ctequery->targetList) + 1, + cte->search_clause->search_seq_column, + false)); + } + if (cte->cycle_clause) + { + ctequery->targetList = lappend(ctequery->targetList, + makeTargetEntry((Expr *) makeVar(1, cmc_attno, + cte->cycle_clause->cycle_mark_type, + cte->cycle_clause->cycle_mark_typmod, + cte->cycle_clause->cycle_mark_collation, 0), + list_length(ctequery->targetList) + 1, + cte->cycle_clause->cycle_mark_column, + false)); + ctequery->targetList = lappend(ctequery->targetList, + makeTargetEntry((Expr *) makeVar(1, cpa_attno, + RECORDARRAYOID, -1, InvalidOid, 0), + list_length(ctequery->targetList) + 1, + cte->cycle_clause->cycle_path_column, + false)); + } + + /* + * Add the additional columns to the CTE's output columns + */ + cte->ctecolnames = ewcl; + if (cte->search_clause) + { + cte->ctecoltypes = lappend_oid(cte->ctecoltypes, search_seq_type); + cte->ctecoltypmods = lappend_int(cte->ctecoltypmods, -1); + cte->ctecolcollations = lappend_oid(cte->ctecolcollations, InvalidOid); + } + if (cte->cycle_clause) + { + cte->ctecoltypes = lappend_oid(cte->ctecoltypes, cte->cycle_clause->cycle_mark_type); + cte->ctecoltypmods = lappend_int(cte->ctecoltypmods, cte->cycle_clause->cycle_mark_typmod); + cte->ctecolcollations = lappend_oid(cte->ctecolcollations, cte->cycle_clause->cycle_mark_collation); + + cte->ctecoltypes = lappend_oid(cte->ctecoltypes, RECORDARRAYOID); + cte->ctecoltypmods = lappend_int(cte->ctecoltypmods, -1); + cte->ctecolcollations = lappend_oid(cte->ctecolcollations, InvalidOid); + } + + return cte; +} diff --git a/src/backend/utils/adt/ruleutils.c b/src/backend/utils/adt/ruleutils.c index 62023c20b2..ded405f435 100644 --- a/src/backend/utils/adt/ruleutils.c +++ b/src/backend/utils/adt/ruleutils.c @@ -5172,6 +5172,53 @@ get_with_clause(Query *query, deparse_context *context) if (PRETTY_INDENT(context)) appendContextKeyword(context, "", 0, 0, 0); appendStringInfoChar(buf, ')'); + + if (cte->search_clause) + { + bool first = true; + ListCell *lc; + + appendStringInfo(buf, " SEARCH %s FIRST BY ", + cte->search_clause->search_breadth_first ? "BREADTH" : "DEPTH"); + + foreach(lc, cte->search_clause->search_col_list) + { + if (first) + first = false; + else + appendStringInfoString(buf, ", "); + appendStringInfoString(buf, + quote_identifier(strVal(lfirst(lc)))); + } + + appendStringInfo(buf, " SET %s", quote_identifier(cte->search_clause->search_seq_column)); + } + + if (cte->cycle_clause) + { + bool first = true; + ListCell *lc; + + appendStringInfoString(buf, " CYCLE "); + + foreach(lc, cte->cycle_clause->cycle_col_list) + { + if (first) + first = false; + else + appendStringInfoString(buf, ", "); + appendStringInfoString(buf, + quote_identifier(strVal(lfirst(lc)))); + } + + appendStringInfo(buf, " SET %s", quote_identifier(cte->cycle_clause->cycle_mark_column)); + appendStringInfoString(buf, " TO "); + get_rule_expr(cte->cycle_clause->cycle_mark_value, context, false); + appendStringInfoString(buf, " DEFAULT "); + get_rule_expr(cte->cycle_clause->cycle_mark_default, context, false); + appendStringInfo(buf, " USING %s", quote_identifier(cte->cycle_clause->cycle_path_column)); + } + sep = ", "; } diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h index 7ddd8c011b..b375c113e1 100644 --- a/src/include/nodes/nodes.h +++ b/src/include/nodes/nodes.h @@ -471,6 +471,8 @@ typedef enum NodeTag T_WithClause, T_InferClause, T_OnConflictClause, + T_CTESearchClause, + T_CTECycleClause, T_CommonTableExpr, T_RoleSpec, T_TriggerTransition, diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h index 60c2f45466..1b54e6bd51 100644 --- a/src/include/nodes/parsenodes.h +++ b/src/include/nodes/parsenodes.h @@ -1435,9 +1435,8 @@ typedef struct OnConflictClause /* * CommonTableExpr - * representation of WITH list element - * - * We don't currently support the SEARCH or CYCLE clause. */ + typedef enum CTEMaterialize { CTEMaterializeDefault, /* no option specified */ @@ -1445,6 +1444,29 @@ typedef enum CTEMaterialize CTEMaterializeNever /* NOT MATERIALIZED */ } CTEMaterialize; +typedef struct CTESearchClause +{ + NodeTag type; + List *search_col_list; + bool search_breadth_first; + char *search_seq_column; + int location; +} CTESearchClause; + +typedef struct CTECycleClause +{ + NodeTag type; + List *cycle_col_list; + char *cycle_mark_column; + Node *cycle_mark_value; + Node *cycle_mark_default; + Oid cycle_mark_type; /* type of _value and _default */ + int cycle_mark_typmod; + Oid cycle_mark_collation; + char *cycle_path_column; + int location; +} CTECycleClause; + typedef struct CommonTableExpr { NodeTag type; @@ -1462,6 +1484,8 @@ typedef struct CommonTableExpr List *ctecoltypes; /* OID list of output column type OIDs */ List *ctecoltypmods; /* integer list of output column typmods */ List *ctecolcollations; /* OID list of column collation OIDs */ + CTESearchClause *search_clause; + CTECycleClause *cycle_clause; } CommonTableExpr; /* Convenience macro to get the output tlist of a CTE's query */ diff --git a/src/include/parser/analyze.h b/src/include/parser/analyze.h index 9d09a02141..52df482ca8 100644 --- a/src/include/parser/analyze.h +++ b/src/include/parser/analyze.h @@ -46,6 +46,8 @@ extern void applyLockingClause(Query *qry, Index rtindex, extern List *BuildOnConflictExcludedTargetlist(Relation targetrel, Index exclRelIndex); +extern SortGroupClause *makeSortGroupClauseForSetOp(Oid rescoltype); + extern void fill_extraUpdatedCols(RangeTblEntry *target_rte, TupleDesc tupdesc); #endif /* ANALYZE_H */ diff --git a/src/include/parser/kwlist.h b/src/include/parser/kwlist.h index 71dcdf2889..9ceab31a2a 100644 --- a/src/include/parser/kwlist.h +++ b/src/include/parser/kwlist.h @@ -60,6 +60,7 @@ PG_KEYWORD("binary", BINARY, TYPE_FUNC_NAME_KEYWORD, BARE_LABEL) PG_KEYWORD("bit", BIT, COL_NAME_KEYWORD, BARE_LABEL) PG_KEYWORD("boolean", BOOLEAN_P, COL_NAME_KEYWORD, BARE_LABEL) PG_KEYWORD("both", BOTH, RESERVED_KEYWORD, BARE_LABEL) +PG_KEYWORD("breadth", BREADTH, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("by", BY, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("cache", CACHE, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("call", CALL, UNRESERVED_KEYWORD, BARE_LABEL) @@ -128,6 +129,7 @@ PG_KEYWORD("delete", DELETE_P, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("delimiter", DELIMITER, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("delimiters", DELIMITERS, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("depends", DEPENDS, UNRESERVED_KEYWORD, BARE_LABEL) +PG_KEYWORD("depth", DEPTH, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("desc", DESC, RESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("detach", DETACH, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("dictionary", DICTIONARY, UNRESERVED_KEYWORD, BARE_LABEL) diff --git a/src/include/parser/parse_node.h b/src/include/parser/parse_node.h index d25819aa28..95e8ec85f2 100644 --- a/src/include/parser/parse_node.h +++ b/src/include/parser/parse_node.h @@ -78,6 +78,7 @@ typedef enum ParseExprKind EXPR_KIND_CALL_ARGUMENT, /* procedure argument in CALL */ EXPR_KIND_COPY_WHERE, /* WHERE condition in COPY FROM */ EXPR_KIND_GENERATED_COLUMN, /* generation expression for a column */ + EXPR_KIND_CYCLE_MARK, /* cycle mark value */ } ParseExprKind; @@ -294,6 +295,7 @@ struct ParseNamespaceColumn Oid p_varcollid; /* OID of collation, or InvalidOid */ Index p_varnosyn; /* rangetable index of syntactic referent */ AttrNumber p_varattnosyn; /* attribute number of syntactic referent */ + bool p_dontexpand; /* not included in star expansion */ }; /* Support for parser_errposition_callback function */ diff --git a/src/include/rewrite/rewriteSearchCycle.h b/src/include/rewrite/rewriteSearchCycle.h new file mode 100644 index 0000000000..257fb7cdab --- /dev/null +++ b/src/include/rewrite/rewriteSearchCycle.h @@ -0,0 +1,21 @@ +/*------------------------------------------------------------------------- + * + * rewriteSearchCycle.h + * Support for rewriting SEARCH and CYCLE clauses. + * + * + * Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * src/include/rewrite/rewriteSearchCycle.h + * + *------------------------------------------------------------------------- + */ +#ifndef REWRITESEARCHCYCLE_H +#define REWRITESEARCHCYCLE_H + +#include "nodes/parsenodes.h" + +extern CommonTableExpr *rewriteSearchAndCycle(CommonTableExpr *cte); + +#endif /* REWRITESEARCHCYCLE_H */ diff --git a/src/test/regress/expected/with.out b/src/test/regress/expected/with.out index 67eaeb4f3e..ac9cb60a83 100644 --- a/src/test/regress/expected/with.out +++ b/src/test/regress/expected/with.out @@ -568,6 +568,148 @@ SELECT t1.id, t2.path, t2 FROM t AS t1 JOIN t AS t2 ON 16 | {3,7,11,16} | (16,"{3,7,11,16}") (16 rows) +-- SEARCH clause +create temp table graph0( f int, t int, label text ); +insert into graph0 values + (1, 2, 'arc 1 -> 2'), + (1, 3, 'arc 1 -> 3'), + (2, 3, 'arc 2 -> 3'), + (1, 4, 'arc 1 -> 4'), + (4, 5, 'arc 4 -> 5'); +with recursive search_graph(f, t, label) as ( + select * from graph0 g + union all + select g.* + from graph0 g, search_graph sg + where g.f = sg.t +) search depth first by f, t set seq +select * from search_graph order by seq; + f | t | label | seq +---+---+------------+------------------- + 1 | 2 | arc 1 -> 2 | {"(1,2)"} + 2 | 3 | arc 2 -> 3 | {"(1,2)","(2,3)"} + 1 | 3 | arc 1 -> 3 | {"(1,3)"} + 1 | 4 | arc 1 -> 4 | {"(1,4)"} + 4 | 5 | arc 4 -> 5 | {"(1,4)","(4,5)"} + 2 | 3 | arc 2 -> 3 | {"(2,3)"} + 4 | 5 | arc 4 -> 5 | {"(4,5)"} +(7 rows) + +with recursive search_graph(f, t, label) as ( + select * from graph0 g + union distinct + select g.* + from graph0 g, search_graph sg + where g.f = sg.t +) search depth first by f, t set seq +select * from search_graph order by seq; +ERROR: SEARCH clause not supported with UNION DISTINCT +with recursive search_graph(f, t, label) as ( + select * from graph0 g + union all + select g.* + from graph0 g, search_graph sg + where g.f = sg.t +) search breadth first by f, t set seq +select * from search_graph order by seq; + f | t | label | seq +---+---+------------+--------- + 1 | 2 | arc 1 -> 2 | (0,1,2) + 1 | 3 | arc 1 -> 3 | (0,1,3) + 1 | 4 | arc 1 -> 4 | (0,1,4) + 2 | 3 | arc 2 -> 3 | (0,2,3) + 4 | 5 | arc 4 -> 5 | (0,4,5) + 2 | 3 | arc 2 -> 3 | (1,2,3) + 4 | 5 | arc 4 -> 5 | (1,4,5) +(7 rows) + +with recursive search_graph(f, t, label) as ( + select * from graph0 g + union distinct + select g.* + from graph0 g, search_graph sg + where g.f = sg.t +) search breadth first by f, t set seq +select * from search_graph order by seq; +ERROR: SEARCH clause not supported with UNION DISTINCT +-- various syntax errors +with recursive search_graph(f, t, label) as ( + select * from graph0 g + union all + select g.* + from graph0 g, search_graph sg + where g.f = sg.t +) search depth first by foo, tar set seq +select * from search_graph; +ERROR: search column "foo" not in WITH query column list +LINE 7: ) search depth first by foo, tar set seq + ^ +with recursive search_graph(f, t, label) as ( + select * from graph0 g + union all + select g.* + from graph0 g, search_graph sg + where g.f = sg.t +) search depth first by f, t set label +select * from search_graph; +ERROR: search sequence column name "label" already used in WITH query column list +LINE 7: ) search depth first by f, t set label + ^ +with recursive search_graph(f, t, label) as ( + select * from graph0 g + union all + select g.* + from graph0 g, search_graph sg + where g.f = sg.t +) search depth first by f, t, f set seq +select * from search_graph; +ERROR: search column "f" specified more than once +LINE 7: ) search depth first by f, t, f set seq + ^ +-- test ruleutils and view expansion +create temp view v_search as +with recursive search_graph(f, t, label) as ( + select * from graph0 g + union all + select g.* + from graph0 g, search_graph sg + where g.f = sg.t +) search depth first by f, t set seq +select f, t, label from search_graph; +select pg_get_viewdef('v_search'); + pg_get_viewdef +------------------------------------------------ + WITH RECURSIVE search_graph(f, t, label) AS (+ + SELECT g.f, + + g.t, + + g.label + + FROM graph0 g + + UNION ALL + + SELECT g.f, + + g.t, + + g.label + + FROM graph0 g, + + search_graph sg + + WHERE (g.f = sg.t) + + ) SEARCH DEPTH FIRST BY f, t SET seq + + SELECT search_graph.f, + + search_graph.t, + + search_graph.label + + FROM search_graph; +(1 row) + +select * from v_search; + f | t | label +---+---+------------ + 1 | 2 | arc 1 -> 2 + 1 | 3 | arc 1 -> 3 + 2 | 3 | arc 2 -> 3 + 1 | 4 | arc 1 -> 4 + 4 | 5 | arc 4 -> 5 + 2 | 3 | arc 2 -> 3 + 4 | 5 | arc 4 -> 5 +(7 rows) + -- -- test cycle detection -- @@ -654,6 +796,297 @@ select * from search_graph order by path; 5 | 1 | arc 5 -> 1 | {"(5,1)","(1,4)","(4,5)","(5,1)"} | t (25 rows) +-- CYCLE clause +with recursive search_graph(f, t, label) as ( + select * from graph g + union all + select g.* + from graph g, search_graph sg + where g.f = sg.t +) cycle f, t set is_cycle to true default false using path +select * from search_graph; + f | t | label | is_cycle | path +---+---+------------+----------+------------------------------------------- + 1 | 2 | arc 1 -> 2 | f | {"(1,2)"} + 1 | 3 | arc 1 -> 3 | f | {"(1,3)"} + 2 | 3 | arc 2 -> 3 | f | {"(2,3)"} + 1 | 4 | arc 1 -> 4 | f | {"(1,4)"} + 4 | 5 | arc 4 -> 5 | f | {"(4,5)"} + 5 | 1 | arc 5 -> 1 | f | {"(5,1)"} + 1 | 2 | arc 1 -> 2 | f | {"(5,1)","(1,2)"} + 1 | 3 | arc 1 -> 3 | f | {"(5,1)","(1,3)"} + 1 | 4 | arc 1 -> 4 | f | {"(5,1)","(1,4)"} + 2 | 3 | arc 2 -> 3 | f | {"(1,2)","(2,3)"} + 4 | 5 | arc 4 -> 5 | f | {"(1,4)","(4,5)"} + 5 | 1 | arc 5 -> 1 | f | {"(4,5)","(5,1)"} + 1 | 2 | arc 1 -> 2 | f | {"(4,5)","(5,1)","(1,2)"} + 1 | 3 | arc 1 -> 3 | f | {"(4,5)","(5,1)","(1,3)"} + 1 | 4 | arc 1 -> 4 | f | {"(4,5)","(5,1)","(1,4)"} + 2 | 3 | arc 2 -> 3 | f | {"(5,1)","(1,2)","(2,3)"} + 4 | 5 | arc 4 -> 5 | f | {"(5,1)","(1,4)","(4,5)"} + 5 | 1 | arc 5 -> 1 | f | {"(1,4)","(4,5)","(5,1)"} + 1 | 2 | arc 1 -> 2 | f | {"(1,4)","(4,5)","(5,1)","(1,2)"} + 1 | 3 | arc 1 -> 3 | f | {"(1,4)","(4,5)","(5,1)","(1,3)"} + 1 | 4 | arc 1 -> 4 | t | {"(1,4)","(4,5)","(5,1)","(1,4)"} + 2 | 3 | arc 2 -> 3 | f | {"(4,5)","(5,1)","(1,2)","(2,3)"} + 4 | 5 | arc 4 -> 5 | t | {"(4,5)","(5,1)","(1,4)","(4,5)"} + 5 | 1 | arc 5 -> 1 | t | {"(5,1)","(1,4)","(4,5)","(5,1)"} + 2 | 3 | arc 2 -> 3 | f | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"} +(25 rows) + +with recursive search_graph(f, t, label) as ( + select * from graph g + union distinct + select g.* + from graph g, search_graph sg + where g.f = sg.t +) cycle f, t set is_cycle to true default false using path +select * from search_graph; +ERROR: CYCLE clause not supported with UNION DISTINCT +-- multiple CTEs +with recursive +graph(f, t, label) as ( + values (1, 2, 'arc 1 -> 2'), + (1, 3, 'arc 1 -> 3'), + (2, 3, 'arc 2 -> 3'), + (1, 4, 'arc 1 -> 4'), + (4, 5, 'arc 4 -> 5'), + (5, 1, 'arc 5 -> 1') +), +search_graph(f, t, label) as ( + select * from graph g + union all + select g.* + from graph g, search_graph sg + where g.f = sg.t +) cycle f, t set is_cycle to true default false using path +select f, t, label from search_graph; + f | t | label +---+---+------------ + 1 | 2 | arc 1 -> 2 + 1 | 3 | arc 1 -> 3 + 2 | 3 | arc 2 -> 3 + 1 | 4 | arc 1 -> 4 + 4 | 5 | arc 4 -> 5 + 5 | 1 | arc 5 -> 1 + 2 | 3 | arc 2 -> 3 + 4 | 5 | arc 4 -> 5 + 5 | 1 | arc 5 -> 1 + 1 | 4 | arc 1 -> 4 + 1 | 3 | arc 1 -> 3 + 1 | 2 | arc 1 -> 2 + 5 | 1 | arc 5 -> 1 + 1 | 4 | arc 1 -> 4 + 1 | 3 | arc 1 -> 3 + 1 | 2 | arc 1 -> 2 + 4 | 5 | arc 4 -> 5 + 2 | 3 | arc 2 -> 3 + 1 | 4 | arc 1 -> 4 + 1 | 3 | arc 1 -> 3 + 1 | 2 | arc 1 -> 2 + 4 | 5 | arc 4 -> 5 + 2 | 3 | arc 2 -> 3 + 5 | 1 | arc 5 -> 1 + 2 | 3 | arc 2 -> 3 +(25 rows) + +-- star expansion +with recursive a as ( + select 1 as b + union all + select * from a +) cycle b set c to true default false using p +select * from a; + b | c | p +---+---+----------- + 1 | f | {(1)} + 1 | t | {(1),(1)} +(2 rows) + +-- search+cycle +with recursive search_graph(f, t, label) as ( + select * from graph g + union all + select g.* + from graph g, search_graph sg + where g.f = sg.t +) search depth first by f, t set seq + cycle f, t set is_cycle to true default false using path +select * from search_graph; + f | t | label | seq | is_cycle | path +---+---+------------+-------------------------------------------+----------+------------------------------------------- + 1 | 2 | arc 1 -> 2 | {"(1,2)"} | f | {"(1,2)"} + 1 | 3 | arc 1 -> 3 | {"(1,3)"} | f | {"(1,3)"} + 2 | 3 | arc 2 -> 3 | {"(2,3)"} | f | {"(2,3)"} + 1 | 4 | arc 1 -> 4 | {"(1,4)"} | f | {"(1,4)"} + 4 | 5 | arc 4 -> 5 | {"(4,5)"} | f | {"(4,5)"} + 5 | 1 | arc 5 -> 1 | {"(5,1)"} | f | {"(5,1)"} + 1 | 2 | arc 1 -> 2 | {"(5,1)","(1,2)"} | f | {"(5,1)","(1,2)"} + 1 | 3 | arc 1 -> 3 | {"(5,1)","(1,3)"} | f | {"(5,1)","(1,3)"} + 1 | 4 | arc 1 -> 4 | {"(5,1)","(1,4)"} | f | {"(5,1)","(1,4)"} + 2 | 3 | arc 2 -> 3 | {"(1,2)","(2,3)"} | f | {"(1,2)","(2,3)"} + 4 | 5 | arc 4 -> 5 | {"(1,4)","(4,5)"} | f | {"(1,4)","(4,5)"} + 5 | 1 | arc 5 -> 1 | {"(4,5)","(5,1)"} | f | {"(4,5)","(5,1)"} + 1 | 2 | arc 1 -> 2 | {"(4,5)","(5,1)","(1,2)"} | f | {"(4,5)","(5,1)","(1,2)"} + 1 | 3 | arc 1 -> 3 | {"(4,5)","(5,1)","(1,3)"} | f | {"(4,5)","(5,1)","(1,3)"} + 1 | 4 | arc 1 -> 4 | {"(4,5)","(5,1)","(1,4)"} | f | {"(4,5)","(5,1)","(1,4)"} + 2 | 3 | arc 2 -> 3 | {"(5,1)","(1,2)","(2,3)"} | f | {"(5,1)","(1,2)","(2,3)"} + 4 | 5 | arc 4 -> 5 | {"(5,1)","(1,4)","(4,5)"} | f | {"(5,1)","(1,4)","(4,5)"} + 5 | 1 | arc 5 -> 1 | {"(1,4)","(4,5)","(5,1)"} | f | {"(1,4)","(4,5)","(5,1)"} + 1 | 2 | arc 1 -> 2 | {"(1,4)","(4,5)","(5,1)","(1,2)"} | f | {"(1,4)","(4,5)","(5,1)","(1,2)"} + 1 | 3 | arc 1 -> 3 | {"(1,4)","(4,5)","(5,1)","(1,3)"} | f | {"(1,4)","(4,5)","(5,1)","(1,3)"} + 1 | 4 | arc 1 -> 4 | {"(1,4)","(4,5)","(5,1)","(1,4)"} | t | {"(1,4)","(4,5)","(5,1)","(1,4)"} + 2 | 3 | arc 2 -> 3 | {"(4,5)","(5,1)","(1,2)","(2,3)"} | f | {"(4,5)","(5,1)","(1,2)","(2,3)"} + 4 | 5 | arc 4 -> 5 | {"(4,5)","(5,1)","(1,4)","(4,5)"} | t | {"(4,5)","(5,1)","(1,4)","(4,5)"} + 5 | 1 | arc 5 -> 1 | {"(5,1)","(1,4)","(4,5)","(5,1)"} | t | {"(5,1)","(1,4)","(4,5)","(5,1)"} + 2 | 3 | arc 2 -> 3 | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"} | f | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"} +(25 rows) + +with recursive search_graph(f, t, label) as ( + select * from graph g + union all + select g.* + from graph g, search_graph sg + where g.f = sg.t +) search breadth first by f, t set seq + cycle f, t set is_cycle to true default false using path +select * from search_graph; + f | t | label | seq | is_cycle | path +---+---+------------+---------+----------+------------------------------------------- + 1 | 2 | arc 1 -> 2 | (0,1,2) | f | {"(1,2)"} + 1 | 3 | arc 1 -> 3 | (0,1,3) | f | {"(1,3)"} + 2 | 3 | arc 2 -> 3 | (0,2,3) | f | {"(2,3)"} + 1 | 4 | arc 1 -> 4 | (0,1,4) | f | {"(1,4)"} + 4 | 5 | arc 4 -> 5 | (0,4,5) | f | {"(4,5)"} + 5 | 1 | arc 5 -> 1 | (0,5,1) | f | {"(5,1)"} + 1 | 2 | arc 1 -> 2 | (1,1,2) | f | {"(5,1)","(1,2)"} + 1 | 3 | arc 1 -> 3 | (1,1,3) | f | {"(5,1)","(1,3)"} + 1 | 4 | arc 1 -> 4 | (1,1,4) | f | {"(5,1)","(1,4)"} + 2 | 3 | arc 2 -> 3 | (1,2,3) | f | {"(1,2)","(2,3)"} + 4 | 5 | arc 4 -> 5 | (1,4,5) | f | {"(1,4)","(4,5)"} + 5 | 1 | arc 5 -> 1 | (1,5,1) | f | {"(4,5)","(5,1)"} + 1 | 2 | arc 1 -> 2 | (2,1,2) | f | {"(4,5)","(5,1)","(1,2)"} + 1 | 3 | arc 1 -> 3 | (2,1,3) | f | {"(4,5)","(5,1)","(1,3)"} + 1 | 4 | arc 1 -> 4 | (2,1,4) | f | {"(4,5)","(5,1)","(1,4)"} + 2 | 3 | arc 2 -> 3 | (2,2,3) | f | {"(5,1)","(1,2)","(2,3)"} + 4 | 5 | arc 4 -> 5 | (2,4,5) | f | {"(5,1)","(1,4)","(4,5)"} + 5 | 1 | arc 5 -> 1 | (2,5,1) | f | {"(1,4)","(4,5)","(5,1)"} + 1 | 2 | arc 1 -> 2 | (3,1,2) | f | {"(1,4)","(4,5)","(5,1)","(1,2)"} + 1 | 3 | arc 1 -> 3 | (3,1,3) | f | {"(1,4)","(4,5)","(5,1)","(1,3)"} + 1 | 4 | arc 1 -> 4 | (3,1,4) | t | {"(1,4)","(4,5)","(5,1)","(1,4)"} + 2 | 3 | arc 2 -> 3 | (3,2,3) | f | {"(4,5)","(5,1)","(1,2)","(2,3)"} + 4 | 5 | arc 4 -> 5 | (3,4,5) | t | {"(4,5)","(5,1)","(1,4)","(4,5)"} + 5 | 1 | arc 5 -> 1 | (3,5,1) | t | {"(5,1)","(1,4)","(4,5)","(5,1)"} + 2 | 3 | arc 2 -> 3 | (4,2,3) | f | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"} +(25 rows) + +-- various syntax errors +with recursive search_graph(f, t, label) as ( + select * from graph g + union all + select g.* + from graph g, search_graph sg + where g.f = sg.t +) cycle foo, tar set is_cycle to true default false using path +select * from search_graph; +ERROR: cycle column "foo" not in WITH query column list +LINE 7: ) cycle foo, tar set is_cycle to true default false using pa... + ^ +with recursive search_graph(f, t, label) as ( + select * from graph g + union all + select g.* + from graph g, search_graph sg + where g.f = sg.t +) cycle f, t set is_cycle to true default 55 using path +select * from search_graph; +ERROR: CYCLE types boolean and integer cannot be matched +LINE 7: ) cycle f, t set is_cycle to true default 55 using path + ^ +with recursive search_graph(f, t, label) as ( + select * from graph g + union all + select g.* + from graph g, search_graph sg + where g.f = sg.t +) cycle f, t set f to true default false using path +select * from search_graph; +ERROR: cycle column name "f" already used in WITH query column list +LINE 7: ) cycle f, t set f to true default false using path + ^ +with recursive search_graph(f, t, label) as ( + select * from graph g + union all + select g.* + from graph g, search_graph sg + where g.f = sg.t +) cycle f, t, f set is_cycle to true default false using path +select * from search_graph; +ERROR: cycle column "f" specified more than once +LINE 7: ) cycle f, t, f set is_cycle to true default false using pat... + ^ +-- test ruleutils and view expansion +create temp view v_cycle as +with recursive search_graph(f, t, label) as ( + select * from graph g + union all + select g.* + from graph g, search_graph sg + where g.f = sg.t +) cycle f, t set is_cycle to true default false using path +select f, t, label from search_graph; +select pg_get_viewdef('v_cycle'); + pg_get_viewdef +-------------------------------------------------------------------- + WITH RECURSIVE search_graph(f, t, label) AS ( + + SELECT g.f, + + g.t, + + g.label + + FROM graph g + + UNION ALL + + SELECT g.f, + + g.t, + + g.label + + FROM graph g, + + search_graph sg + + WHERE (g.f = sg.t) + + ) CYCLE f, t SET is_cycle TO true DEFAULT false USING path+ + SELECT search_graph.f, + + search_graph.t, + + search_graph.label + + FROM search_graph; +(1 row) + +select * from v_cycle; + f | t | label +---+---+------------ + 1 | 2 | arc 1 -> 2 + 1 | 3 | arc 1 -> 3 + 2 | 3 | arc 2 -> 3 + 1 | 4 | arc 1 -> 4 + 4 | 5 | arc 4 -> 5 + 5 | 1 | arc 5 -> 1 + 1 | 2 | arc 1 -> 2 + 1 | 3 | arc 1 -> 3 + 1 | 4 | arc 1 -> 4 + 2 | 3 | arc 2 -> 3 + 4 | 5 | arc 4 -> 5 + 5 | 1 | arc 5 -> 1 + 1 | 2 | arc 1 -> 2 + 1 | 3 | arc 1 -> 3 + 1 | 4 | arc 1 -> 4 + 2 | 3 | arc 2 -> 3 + 4 | 5 | arc 4 -> 5 + 5 | 1 | arc 5 -> 1 + 1 | 2 | arc 1 -> 2 + 1 | 3 | arc 1 -> 3 + 1 | 4 | arc 1 -> 4 + 2 | 3 | arc 2 -> 3 + 4 | 5 | arc 4 -> 5 + 5 | 1 | arc 5 -> 1 + 2 | 3 | arc 2 -> 3 +(25 rows) + -- -- test multiple WITH queries -- diff --git a/src/test/regress/sql/with.sql b/src/test/regress/sql/with.sql index f85645efde..af6329165c 100644 --- a/src/test/regress/sql/with.sql +++ b/src/test/regress/sql/with.sql @@ -295,6 +295,96 @@ CREATE TEMPORARY TABLE tree( SELECT t1.id, t2.path, t2 FROM t AS t1 JOIN t AS t2 ON (t1.id=t2.id); +-- SEARCH clause + +create temp table graph0( f int, t int, label text ); + +insert into graph0 values + (1, 2, 'arc 1 -> 2'), + (1, 3, 'arc 1 -> 3'), + (2, 3, 'arc 2 -> 3'), + (1, 4, 'arc 1 -> 4'), + (4, 5, 'arc 4 -> 5'); + +with recursive search_graph(f, t, label) as ( + select * from graph0 g + union all + select g.* + from graph0 g, search_graph sg + where g.f = sg.t +) search depth first by f, t set seq +select * from search_graph order by seq; + +with recursive search_graph(f, t, label) as ( + select * from graph0 g + union distinct + select g.* + from graph0 g, search_graph sg + where g.f = sg.t +) search depth first by f, t set seq +select * from search_graph order by seq; + +with recursive search_graph(f, t, label) as ( + select * from graph0 g + union all + select g.* + from graph0 g, search_graph sg + where g.f = sg.t +) search breadth first by f, t set seq +select * from search_graph order by seq; + +with recursive search_graph(f, t, label) as ( + select * from graph0 g + union distinct + select g.* + from graph0 g, search_graph sg + where g.f = sg.t +) search breadth first by f, t set seq +select * from search_graph order by seq; + +-- various syntax errors +with recursive search_graph(f, t, label) as ( + select * from graph0 g + union all + select g.* + from graph0 g, search_graph sg + where g.f = sg.t +) search depth first by foo, tar set seq +select * from search_graph; + +with recursive search_graph(f, t, label) as ( + select * from graph0 g + union all + select g.* + from graph0 g, search_graph sg + where g.f = sg.t +) search depth first by f, t set label +select * from search_graph; + +with recursive search_graph(f, t, label) as ( + select * from graph0 g + union all + select g.* + from graph0 g, search_graph sg + where g.f = sg.t +) search depth first by f, t, f set seq +select * from search_graph; + +-- test ruleutils and view expansion +create temp view v_search as +with recursive search_graph(f, t, label) as ( + select * from graph0 g + union all + select g.* + from graph0 g, search_graph sg + where g.f = sg.t +) search depth first by f, t set seq +select f, t, label from search_graph; + +select pg_get_viewdef('v_search'); + +select * from v_search; + -- -- test cycle detection -- @@ -327,6 +417,126 @@ CREATE TEMPORARY TABLE tree( ) select * from search_graph order by path; +-- CYCLE clause + +with recursive search_graph(f, t, label) as ( + select * from graph g + union all + select g.* + from graph g, search_graph sg + where g.f = sg.t +) cycle f, t set is_cycle to true default false using path +select * from search_graph; + +with recursive search_graph(f, t, label) as ( + select * from graph g + union distinct + select g.* + from graph g, search_graph sg + where g.f = sg.t +) cycle f, t set is_cycle to true default false using path +select * from search_graph; + +-- multiple CTEs +with recursive +graph(f, t, label) as ( + values (1, 2, 'arc 1 -> 2'), + (1, 3, 'arc 1 -> 3'), + (2, 3, 'arc 2 -> 3'), + (1, 4, 'arc 1 -> 4'), + (4, 5, 'arc 4 -> 5'), + (5, 1, 'arc 5 -> 1') +), +search_graph(f, t, label) as ( + select * from graph g + union all + select g.* + from graph g, search_graph sg + where g.f = sg.t +) cycle f, t set is_cycle to true default false using path +select f, t, label from search_graph; + +-- star expansion +with recursive a as ( + select 1 as b + union all + select * from a +) cycle b set c to true default false using p +select * from a; + +-- search+cycle +with recursive search_graph(f, t, label) as ( + select * from graph g + union all + select g.* + from graph g, search_graph sg + where g.f = sg.t +) search depth first by f, t set seq + cycle f, t set is_cycle to true default false using path +select * from search_graph; + +with recursive search_graph(f, t, label) as ( + select * from graph g + union all + select g.* + from graph g, search_graph sg + where g.f = sg.t +) search breadth first by f, t set seq + cycle f, t set is_cycle to true default false using path +select * from search_graph; + +-- various syntax errors +with recursive search_graph(f, t, label) as ( + select * from graph g + union all + select g.* + from graph g, search_graph sg + where g.f = sg.t +) cycle foo, tar set is_cycle to true default false using path +select * from search_graph; + +with recursive search_graph(f, t, label) as ( + select * from graph g + union all + select g.* + from graph g, search_graph sg + where g.f = sg.t +) cycle f, t set is_cycle to true default 55 using path +select * from search_graph; + +with recursive search_graph(f, t, label) as ( + select * from graph g + union all + select g.* + from graph g, search_graph sg + where g.f = sg.t +) cycle f, t set f to true default false using path +select * from search_graph; + +with recursive search_graph(f, t, label) as ( + select * from graph g + union all + select g.* + from graph g, search_graph sg + where g.f = sg.t +) cycle f, t, f set is_cycle to true default false using path +select * from search_graph; + +-- test ruleutils and view expansion +create temp view v_cycle as +with recursive search_graph(f, t, label) as ( + select * from graph g + union all + select g.* + from graph g, search_graph sg + where g.f = sg.t +) cycle f, t set is_cycle to true default false using path +select f, t, label from search_graph; + +select pg_get_viewdef('v_cycle'); + +select * from v_cycle; + -- -- test multiple WITH queries -- base-commit: f13f2e484172a1c865cd067796cee3568467dd51 -- 2.28.0
