pg.ddx.io pgsql-hackers@postgresql.org mailing list archive help / color / mirror / Atom feed From: Peter Eisentraut <peter.eisentraut@2ndquadrant.com>
To: Pavel Stehule <pavel.stehule@gmail.com>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Subject: Re: SEARCH and CYCLE clauses
Date: Fri, 9 Oct 2020 11:40:40 +0200
Message-ID: <52beaf44-ccc3-0ba1-45c7-74aa251cd6ab@2ndquadrant.com> (raw )
In-Reply-To: <CAFj8pRD8hn1vEdX+EMXQ2hz2pkfyJ2a9cV6R8mbaLYn-MRexdQ@mail.gmail.com >
References: <db80ceee-6f97-9b4a-8ee8-3ba0c58e5be2@2ndquadrant.com >
<CAFj8pRD8hn1vEdX+EMXQ2hz2pkfyJ2a9cV6R8mbaLYn-MRexdQ@mail.gmail.com >
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 <peter@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-3ba0c58e5be2@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
Attachments:
[text/plain] v3-0001-SEARCH-and-CYCLE-clauses.patch (94.5K, ../52beaf44-ccc3-0ba1-45c7-74aa251cd6ab@2ndquadrant.com/2-v3-0001-SEARCH-and-CYCLE-clauses.patch)
download | inline diff:
From 4b36e81def50be44bd1f68247e33a22343520b5e Mon Sep 17 00:00:00 2001
From: Peter Eisentraut <peter@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-3ba0c58e5be2@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
view thread (27+ messages) latest in thread
Message-ID: <52beaf44-ccc3-0ba1-45c7-74aa251cd6ab@2ndquadrant.com>
Permalink: ../52beaf44-ccc3-0ba1-45c7-74aa251cd6ab@2ndquadrant.com/
Also on: postgresql.org/message-id/52beaf44-ccc3-0ba1-45c7-74aa251cd6ab@2ndquadrant.com
copy link · copy postgr.es · copy git am
reply Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: peter.eisentraut@2ndquadrant.com, pavel.stehule@gmail.com
Subject: Re: SEARCH and CYCLE clauses
In-Reply-To: <52beaf44-ccc3-0ba1-45c7-74aa251cd6ab@2ndquadrant.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox