Here is an updated patch that I think fixes all the cases that you
identified. (The issue of what kinds of constants or expressions to
accept for cycle marks has not been touched.) To fix the star expansion
I had to add a little bit of infrastructure that could also be used as a
more general facility "don't include this column in star expansion", so
this could perhaps use some consideration from a more general angle as well.
More tests and breakage reports welcome.
--
Peter Eisentraut http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
From f4fc5f63c53ba954066d38f968f54fb8fbf76c59 Mon Sep 17 00:00:00 2001
From: Peter Eisentraut <pe...@eisentraut.org>
Date: Mon, 15 Jun 2020 11:43:52 +0200
Subject: [PATCH v2] SEARCH and CYCLE clauses
Discussion:
https://www.postgresql.org/message-id/flat/db80ceee-6f97-9b4a-8ee8-3ba0c58e5...@2ndquadrant.com
---
doc/src/sgml/queries.sgml | 204 +++++++-
doc/src/sgml/ref/select.sgml | 41 ++
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/gram.y | 56 ++-
src/backend/parser/parse_cte.c | 117 +++++
src/backend/parser/parse_relation.c | 54 ++-
src/backend/parser/parse_target.c | 21 +-
src/backend/rewrite/rewriteHandler.c | 673 +++++++++++++++++++++++++++
src/backend/utils/adt/ruleutils.c | 47 ++
src/include/nodes/nodes.h | 2 +
src/include/nodes/parsenodes.h | 28 +-
src/include/parser/kwlist.h | 2 +
src/include/parser/parse_node.h | 1 +
src/test/regress/expected/with.out | 364 +++++++++++++++
src/test/regress/sql/with.sql | 179 +++++++
19 files changed, 1917 insertions(+), 30 deletions(-)
diff --git a/doc/src/sgml/queries.sgml b/doc/src/sgml/queries.sgml
index 572e968273..f98d8d3dc1 100644
--- a/doc/src/sgml/queries.sgml
+++ b/doc/src/sgml/queries.sgml
@@ -1979,6 +1979,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>
@@ -2082,6 +2086,144 @@ <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(g.f1, g.f2)]</emphasis>
+ FROM tree t
+ UNION ALL
+ SELECT t.id, t.link, t.data, <emphasis>path || ROW(g.f1, g.f2)</emphasis>
+ FROM tree t, search_tree st
+ WHERE t.id = st.link
+)
+SELECT * FROM search_tree <emphasis>ORDER BY path</emphasis>;
+</programlisting>
+ </para>
+
+ <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,
@@ -2112,18 +2254,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
)
@@ -2140,15 +2282,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
)
@@ -2164,12 +2306,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, link 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>
@@ -2197,6 +2366,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 b93e4ca208..8cb35e1d0a 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,45 @@ <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. If both
+ clauses are used, the column added by the <literal>SEARCH</literal> clause
+ appear 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 d8cf87e6d0..871f9b4786 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;
}
@@ -5673,6 +5706,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 627b026b19..481582b418 100644
--- a/src/backend/nodes/equalfuncs.c
+++ b/src/backend/nodes/equalfuncs.c
@@ -2831,6 +2831,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)
{
@@ -2845,6 +2872,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;
}
@@ -3725,6 +3754,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 d85ca9f7c5..88d85e1453 100644
--- a/src/backend/nodes/nodeFuncs.c
+++ b/src/backend/nodes/nodeFuncs.c
@@ -1526,6 +1526,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 e2f177515d..94dc84be39 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -3046,6 +3046,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)
{
@@ -3062,6 +3089,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
@@ -4232,6 +4261,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/gram.y b/src/backend/parser/gram.y
index e669d75a5a..e13096fb93 100644
--- a/src/backend/parser/gram.y
+++ b/src/backend/parser/gram.y
@@ -496,6 +496,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
@@ -630,7 +631,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
@@ -642,7 +643,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
@@ -11309,8 +11310,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:
@@ -11342,13 +11341,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;
}
@@ -11360,6 +11361,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; }
@@ -15044,6 +15088,7 @@ unreserved_keyword:
| BACKWARD
| BEFORE
| BEGIN_P
+ | BREADTH
| BY
| CACHE
| CALL
@@ -15088,6 +15133,7 @@ unreserved_keyword:
| DELIMITER
| DELIMITERS
| DEPENDS
+ | DEPTH
| DETACH
| DICTIONARY
| DISABLE_P
diff --git a/src/backend/parser/parse_cte.c b/src/backend/parser/parse_cte.c
index 1fca7485ca..cbfdbf03b2 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));
+
+ // TODO: needs new EXPR_KIND_*, or bypass transformExpr() and
call
+ // make_const() directly
+ cte->cycle_clause->cycle_mark_value = transformExpr(pstate,
cte->cycle_clause->cycle_mark_value, EXPR_KIND_OTHER);
+ cte->cycle_clause->cycle_mark_default = transformExpr(pstate,
cte->cycle_clause->cycle_mark_default, EXPR_KIND_OTHER);
+ 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_relation.c
b/src/backend/parser/parse_relation.c
index b875a50646..41d9dff770 100644
--- a/src/backend/parser/parse_relation.c
+++ b/src/backend/parser/parse_relation.c
@@ -2205,6 +2205,8 @@ addRangeTableEntryForCTE(ParseState *pstate,
int numaliases;
int varattno;
ListCell *lc;
+ int n_dontexpand_columns = 0;
+ ParseNamespaceItem *psi;
Assert(pstate != NULL);
@@ -2237,9 +2239,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)
@@ -2264,6 +2266,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.
*
@@ -2291,9 +2321,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;
}
/*
@@ -2978,7 +3018,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/rewriteHandler.c
b/src/backend/rewrite/rewriteHandler.c
index fe777c3103..be74ddaf61 100644
--- a/src/backend/rewrite/rewriteHandler.c
+++ b/src/backend/rewrite/rewriteHandler.c
@@ -24,6 +24,7 @@
#include "access/sysattr.h"
#include "access/table.h"
#include "catalog/dependency.h"
+#include "catalog/pg_operator_d.h"
#include "catalog/pg_type.h"
#include "commands/trigger.h"
#include "foreign/fdwapi.h"
@@ -39,8 +40,10 @@
#include "rewrite/rewriteManip.h"
#include "rewrite/rowsecurity.h"
#include "utils/builtins.h"
+#include "utils/fmgroids.h"
#include "utils/lsyscache.h"
#include "utils/rel.h"
+#include "utils/typcache.h"
/* We use a list of these to detect recursion in RewriteQuery */
@@ -3442,6 +3445,660 @@ rewriteTargetView(Query *parsetree, Relation view)
}
+/*----------
+ * 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(CommonTableExpr *cte, 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.
+ */
+static 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);
+
+ 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 (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);
+
+ sos->colTypes = lappend_oid(sos->colTypes, RECORDARRAYOID);
+ sos->colTypmods = lappend_int(sos->colTypmods, -1);
+ sos->colCollations = lappend_oid(sos->colCollations,
InvalidOid);
+ }
+
+ /*
+ * 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;
+}
+
+
/*
* RewriteQuery -
* rewrites the query and apply the rules again on the queries rewritten
@@ -3460,6 +4117,22 @@ RewriteQuery(Query *parsetree, List *rewrite_events)
List *rewritten = NIL;
ListCell *lc1;
+ /*
+ * Zeroth, expand SEARCH and CYCLE clauses in CTEs.
+ *
+ * XXX Where is the best place to put this?
+ */
+ foreach(lc1, parsetree->cteList)
+ {
+ CommonTableExpr *cte = lfirst_node(CommonTableExpr, lc1);
+
+ if (cte->search_clause || cte->cycle_clause)
+ {
+ cte = rewriteSearchAndCycle(cte);
+ lfirst(lc1) = cte;
+ }
+ }
+
/*
* First, recursively process any insert/update/delete statements in
WITH
* clauses. (We have to do this first because the WITH clauses may get
diff --git a/src/backend/utils/adt/ruleutils.c
b/src/backend/utils/adt/ruleutils.c
index 076c3c019f..25039691e5 100644
--- a/src/backend/utils/adt/ruleutils.c
+++ b/src/backend/utils/adt/ruleutils.c
@@ -5182,6 +5182,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 381d84b4e4..3c6f521f84 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -472,6 +472,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 5e1ffafb91..f4a3f466b3 100644
--- a/src/include/nodes/parsenodes.h
+++ b/src/include/nodes/parsenodes.h
@@ -1434,9 +1434,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 */
@@ -1444,6 +1443,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;
@@ -1461,6 +1483,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/kwlist.h b/src/include/parser/kwlist.h
index 08f22ce211..5e5b76e6de 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)
PG_KEYWORD("bit", BIT, COL_NAME_KEYWORD)
PG_KEYWORD("boolean", BOOLEAN_P, COL_NAME_KEYWORD)
PG_KEYWORD("both", BOTH, RESERVED_KEYWORD)
+PG_KEYWORD("breadth", BREADTH, UNRESERVED_KEYWORD)
PG_KEYWORD("by", BY, UNRESERVED_KEYWORD)
PG_KEYWORD("cache", CACHE, UNRESERVED_KEYWORD)
PG_KEYWORD("call", CALL, UNRESERVED_KEYWORD)
@@ -128,6 +129,7 @@ PG_KEYWORD("delete", DELETE_P, UNRESERVED_KEYWORD)
PG_KEYWORD("delimiter", DELIMITER, UNRESERVED_KEYWORD)
PG_KEYWORD("delimiters", DELIMITERS, UNRESERVED_KEYWORD)
PG_KEYWORD("depends", DEPENDS, UNRESERVED_KEYWORD)
+PG_KEYWORD("depth", DEPTH, UNRESERVED_KEYWORD)
PG_KEYWORD("desc", DESC, RESERVED_KEYWORD)
PG_KEYWORD("detach", DETACH, UNRESERVED_KEYWORD)
PG_KEYWORD("dictionary", DICTIONARY, UNRESERVED_KEYWORD)
diff --git a/src/include/parser/parse_node.h b/src/include/parser/parse_node.h
index d25819aa28..0b0fdabb1a 100644
--- a/src/include/parser/parse_node.h
+++ b/src/include/parser/parse_node.h
@@ -294,6 +294,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/test/regress/expected/with.out
b/src/test/regress/expected/with.out
index 67eaeb4f3e..fc4ff42afc 100644
--- a/src/test/regress/expected/with.out
+++ b/src/test/regress/expected/with.out
@@ -568,6 +568,118 @@ 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 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)
+
+-- 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
+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)
+
--
-- test cycle detection
--
@@ -654,6 +766,258 @@ 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)
+
+-- 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
+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)
+
--
-- test multiple WITH queries
--
diff --git a/src/test/regress/sql/with.sql b/src/test/regress/sql/with.sql
index f85645efde..a9c3f6748a 100644
--- a/src/test/regress/sql/with.sql
+++ b/src/test/regress/sql/with.sql
@@ -295,6 +295,76 @@ 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 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;
+
+-- 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
+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');
+
--
-- test cycle detection
--
@@ -327,6 +397,115 @@ 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;
+
+-- 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
+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');
+
--
-- test multiple WITH queries
--
base-commit: 3baa7e38d51579b69e1228f3e1a43f56001b6d64
--
2.27.0
