pg.ddx.io pgsql-hackers@postgresql.org mailing list archive help / color / mirror / Atom feed From: Peter Eisentraut <peter.eisentraut@2ndquadrant.com>
To: pgsql-hackers <pgsql-hackers@postgresql.org>
Cc: Vik Fearing <vik@postgresfriends.org>
Subject: Re: SEARCH and CYCLE clauses
Date: Fri, 3 Jul 2020 09:08:26 +0200
Message-ID: <c5603982-0088-7f14-0caa-fdcd0c837b57@2ndquadrant.com> (raw )
In-Reply-To: <1a7fbf28-7bca-501e-3cbb-04e6776e1716@2ndquadrant.com >
References: <db80ceee-6f97-9b4a-8ee8-3ba0c58e5be2@2ndquadrant.com >
<54e533c5-09e5-7f41-9892-d4e0f7c62598@postgresfriends.org >
<b267acb8-edc0-31a8-0645-2992d1f0f393@postgresfriends.org >
<1cfc9079-9595-d167-00e6-5014438cc3e2@2ndquadrant.com >
<9ce4d370-048c-1d67-fffb-a86f17120132@postgresfriends.org >
<1a7fbf28-7bca-501e-3cbb-04e6776e1716@2ndquadrant.com >
While the larger patch is being considered, I think some simpler and
separable pieces could be addressed.
Here is a patch that adjusts the existing cycle detection example and
test queries to put the cycle column before the path column. The CYCLE
clause puts them in that order, and so if we added that feature that
would make the sequence of examples more consistent and easier to follow.
(And while the order of columns has no semantic meaning, for a human
left-to-right reader it also makes a bit more sense because the cycle
flag is computed against the previous path value, so it happens "before"
the path column.)
--
Peter Eisentraut http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
From 1042cad84631406eeec8715ab93c0451702b5c0d Mon Sep 17 00:00:00 2001
From: Peter Eisentraut <peter@eisentraut.org>
Date: Fri, 3 Jul 2020 08:51:12 +0200
Subject: [PATCH] Adjust cycle detection examples and tests
Adjust the existing cycle detection example and test queries to put
the cycle column before the path column. This is mainly because the
SQL-standard CYCLE clause puts them in that order, and so if we added
that feature that would make the sequence of examples more consistent
and easier to follow.
---
doc/src/sgml/queries.sgml | 26 +++---
src/test/regress/expected/with.out | 124 ++++++++++++++---------------
src/test/regress/sql/with.sql | 16 ++--
3 files changed, 83 insertions(+), 83 deletions(-)
diff --git a/doc/src/sgml/queries.sgml b/doc/src/sgml/queries.sgml
index 572e968273..ef0ca56c66 100644
--- a/doc/src/sgml/queries.sgml
+++ b/doc/src/sgml/queries.sgml
@@ -2112,20 +2112,20 @@ <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
+ WHERE g.id = sg.link AND NOT is_cycle
)
SELECT * FROM search_graph;
</programlisting>
@@ -2140,17 +2140,17 @@ <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
+ WHERE g.id = sg.link AND NOT is_cycle
)
SELECT * FROM search_graph;
</programlisting>
diff --git a/src/test/regress/expected/with.out b/src/test/regress/expected/with.out
index 67eaeb4f3e..457f3bf04f 100644
--- a/src/test/regress/expected/with.out
+++ b/src/test/regress/expected/with.out
@@ -579,79 +579,79 @@ insert into graph values
(1, 4, 'arc 1 -> 4'),
(4, 5, 'arc 4 -> 5'),
(5, 1, 'arc 5 -> 1');
-with recursive search_graph(f, t, label, path, cycle) as (
- select *, array[row(g.f, g.t)], false from graph g
+with recursive search_graph(f, t, label, is_cycle, path) as (
+ select *, false, array[row(g.f, g.t)] from graph g
union all
- select g.*, path || row(g.f, g.t), row(g.f, g.t) = any(path)
+ select g.*, row(g.f, g.t) = any(path), path || row(g.f, g.t)
from graph g, search_graph sg
- where g.f = sg.t and not cycle
+ where g.f = sg.t and not is_cycle
)
select * from search_graph;
- f | t | label | path | cycle
----+---+------------+-------------------------------------------+-------
- 1 | 2 | arc 1 -> 2 | {"(1,2)"} | f
- 1 | 3 | arc 1 -> 3 | {"(1,3)"} | f
- 2 | 3 | arc 2 -> 3 | {"(2,3)"} | f
- 1 | 4 | arc 1 -> 4 | {"(1,4)"} | f
- 4 | 5 | arc 4 -> 5 | {"(4,5)"} | f
- 5 | 1 | arc 5 -> 1 | {"(5,1)"} | f
- 1 | 2 | arc 1 -> 2 | {"(5,1)","(1,2)"} | f
- 1 | 3 | arc 1 -> 3 | {"(5,1)","(1,3)"} | f
- 1 | 4 | arc 1 -> 4 | {"(5,1)","(1,4)"} | f
- 2 | 3 | arc 2 -> 3 | {"(1,2)","(2,3)"} | f
- 4 | 5 | arc 4 -> 5 | {"(1,4)","(4,5)"} | f
- 5 | 1 | arc 5 -> 1 | {"(4,5)","(5,1)"} | f
- 1 | 2 | arc 1 -> 2 | {"(4,5)","(5,1)","(1,2)"} | f
- 1 | 3 | arc 1 -> 3 | {"(4,5)","(5,1)","(1,3)"} | f
- 1 | 4 | arc 1 -> 4 | {"(4,5)","(5,1)","(1,4)"} | f
- 2 | 3 | arc 2 -> 3 | {"(5,1)","(1,2)","(2,3)"} | f
- 4 | 5 | arc 4 -> 5 | {"(5,1)","(1,4)","(4,5)"} | f
- 5 | 1 | arc 5 -> 1 | {"(1,4)","(4,5)","(5,1)"} | f
- 1 | 2 | arc 1 -> 2 | {"(1,4)","(4,5)","(5,1)","(1,2)"} | f
- 1 | 3 | arc 1 -> 3 | {"(1,4)","(4,5)","(5,1)","(1,3)"} | f
- 1 | 4 | arc 1 -> 4 | {"(1,4)","(4,5)","(5,1)","(1,4)"} | t
- 2 | 3 | arc 2 -> 3 | {"(4,5)","(5,1)","(1,2)","(2,3)"} | f
- 4 | 5 | arc 4 -> 5 | {"(4,5)","(5,1)","(1,4)","(4,5)"} | t
- 5 | 1 | arc 5 -> 1 | {"(5,1)","(1,4)","(4,5)","(5,1)"} | t
- 2 | 3 | arc 2 -> 3 | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"} | f
+ 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)
-- ordering by the path column has same effect as SEARCH DEPTH FIRST
-with recursive search_graph(f, t, label, path, cycle) as (
- select *, array[row(g.f, g.t)], false from graph g
+with recursive search_graph(f, t, label, is_cycle, path) as (
+ select *, false, array[row(g.f, g.t)] from graph g
union all
- select g.*, path || row(g.f, g.t), row(g.f, g.t) = any(path)
+ select g.*, row(g.f, g.t) = any(path), path || row(g.f, g.t)
from graph g, search_graph sg
- where g.f = sg.t and not cycle
+ where g.f = sg.t and not is_cycle
)
select * from search_graph order by path;
- f | t | label | path | cycle
----+---+------------+-------------------------------------------+-------
- 1 | 2 | arc 1 -> 2 | {"(1,2)"} | f
- 2 | 3 | arc 2 -> 3 | {"(1,2)","(2,3)"} | f
- 1 | 3 | arc 1 -> 3 | {"(1,3)"} | f
- 1 | 4 | arc 1 -> 4 | {"(1,4)"} | f
- 4 | 5 | arc 4 -> 5 | {"(1,4)","(4,5)"} | f
- 5 | 1 | arc 5 -> 1 | {"(1,4)","(4,5)","(5,1)"} | f
- 1 | 2 | arc 1 -> 2 | {"(1,4)","(4,5)","(5,1)","(1,2)"} | f
- 2 | 3 | arc 2 -> 3 | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"} | f
- 1 | 3 | arc 1 -> 3 | {"(1,4)","(4,5)","(5,1)","(1,3)"} | f
- 1 | 4 | arc 1 -> 4 | {"(1,4)","(4,5)","(5,1)","(1,4)"} | t
- 2 | 3 | arc 2 -> 3 | {"(2,3)"} | f
- 4 | 5 | arc 4 -> 5 | {"(4,5)"} | f
- 5 | 1 | arc 5 -> 1 | {"(4,5)","(5,1)"} | f
- 1 | 2 | arc 1 -> 2 | {"(4,5)","(5,1)","(1,2)"} | f
- 2 | 3 | arc 2 -> 3 | {"(4,5)","(5,1)","(1,2)","(2,3)"} | f
- 1 | 3 | arc 1 -> 3 | {"(4,5)","(5,1)","(1,3)"} | f
- 1 | 4 | arc 1 -> 4 | {"(4,5)","(5,1)","(1,4)"} | f
- 4 | 5 | arc 4 -> 5 | {"(4,5)","(5,1)","(1,4)","(4,5)"} | t
- 5 | 1 | arc 5 -> 1 | {"(5,1)"} | f
- 1 | 2 | arc 1 -> 2 | {"(5,1)","(1,2)"} | f
- 2 | 3 | arc 2 -> 3 | {"(5,1)","(1,2)","(2,3)"} | f
- 1 | 3 | arc 1 -> 3 | {"(5,1)","(1,3)"} | f
- 1 | 4 | arc 1 -> 4 | {"(5,1)","(1,4)"} | f
- 4 | 5 | arc 4 -> 5 | {"(5,1)","(1,4)","(4,5)"} | f
- 5 | 1 | arc 5 -> 1 | {"(5,1)","(1,4)","(4,5)","(5,1)"} | t
+ f | t | label | is_cycle | path
+---+---+------------+----------+-------------------------------------------
+ 1 | 2 | arc 1 -> 2 | f | {"(1,2)"}
+ 2 | 3 | arc 2 -> 3 | f | {"(1,2)","(2,3)"}
+ 1 | 3 | arc 1 -> 3 | f | {"(1,3)"}
+ 1 | 4 | arc 1 -> 4 | f | {"(1,4)"}
+ 4 | 5 | arc 4 -> 5 | f | {"(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)"}
+ 2 | 3 | arc 2 -> 3 | f | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"}
+ 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 | {"(2,3)"}
+ 4 | 5 | arc 4 -> 5 | f | {"(4,5)"}
+ 5 | 1 | arc 5 -> 1 | f | {"(4,5)","(5,1)"}
+ 1 | 2 | arc 1 -> 2 | f | {"(4,5)","(5,1)","(1,2)"}
+ 2 | 3 | arc 2 -> 3 | f | {"(4,5)","(5,1)","(1,2)","(2,3)"}
+ 1 | 3 | arc 1 -> 3 | f | {"(4,5)","(5,1)","(1,3)"}
+ 1 | 4 | arc 1 -> 4 | f | {"(4,5)","(5,1)","(1,4)"}
+ 4 | 5 | arc 4 -> 5 | t | {"(4,5)","(5,1)","(1,4)","(4,5)"}
+ 5 | 1 | arc 5 -> 1 | f | {"(5,1)"}
+ 1 | 2 | arc 1 -> 2 | f | {"(5,1)","(1,2)"}
+ 2 | 3 | arc 2 -> 3 | f | {"(5,1)","(1,2)","(2,3)"}
+ 1 | 3 | arc 1 -> 3 | f | {"(5,1)","(1,3)"}
+ 1 | 4 | arc 1 -> 4 | f | {"(5,1)","(1,4)"}
+ 4 | 5 | arc 4 -> 5 | f | {"(5,1)","(1,4)","(4,5)"}
+ 5 | 1 | arc 5 -> 1 | t | {"(5,1)","(1,4)","(4,5)","(5,1)"}
(25 rows)
--
diff --git a/src/test/regress/sql/with.sql b/src/test/regress/sql/with.sql
index f85645efde..2eea297a71 100644
--- a/src/test/regress/sql/with.sql
+++ b/src/test/regress/sql/with.sql
@@ -308,22 +308,22 @@ CREATE TEMPORARY TABLE tree(
(4, 5, 'arc 4 -> 5'),
(5, 1, 'arc 5 -> 1');
-with recursive search_graph(f, t, label, path, cycle) as (
- select *, array[row(g.f, g.t)], false from graph g
+with recursive search_graph(f, t, label, is_cycle, path) as (
+ select *, false, array[row(g.f, g.t)] from graph g
union all
- select g.*, path || row(g.f, g.t), row(g.f, g.t) = any(path)
+ select g.*, row(g.f, g.t) = any(path), path || row(g.f, g.t)
from graph g, search_graph sg
- where g.f = sg.t and not cycle
+ where g.f = sg.t and not is_cycle
)
select * from search_graph;
-- ordering by the path column has same effect as SEARCH DEPTH FIRST
-with recursive search_graph(f, t, label, path, cycle) as (
- select *, array[row(g.f, g.t)], false from graph g
+with recursive search_graph(f, t, label, is_cycle, path) as (
+ select *, false, array[row(g.f, g.t)] from graph g
union all
- select g.*, path || row(g.f, g.t), row(g.f, g.t) = any(path)
+ select g.*, row(g.f, g.t) = any(path), path || row(g.f, g.t)
from graph g, search_graph sg
- where g.f = sg.t and not cycle
+ where g.f = sg.t and not is_cycle
)
select * from search_graph order by path;
--
2.27.0
Attachments:
[text/plain] 0001-Adjust-cycle-detection-examples-and-tests.patch (12.3K, ../c5603982-0088-7f14-0caa-fdcd0c837b57@2ndquadrant.com/2-0001-Adjust-cycle-detection-examples-and-tests.patch)
download | inline diff:
From 1042cad84631406eeec8715ab93c0451702b5c0d Mon Sep 17 00:00:00 2001
From: Peter Eisentraut <peter@eisentraut.org>
Date: Fri, 3 Jul 2020 08:51:12 +0200
Subject: [PATCH] Adjust cycle detection examples and tests
Adjust the existing cycle detection example and test queries to put
the cycle column before the path column. This is mainly because the
SQL-standard CYCLE clause puts them in that order, and so if we added
that feature that would make the sequence of examples more consistent
and easier to follow.
---
doc/src/sgml/queries.sgml | 26 +++---
src/test/regress/expected/with.out | 124 ++++++++++++++---------------
src/test/regress/sql/with.sql | 16 ++--
3 files changed, 83 insertions(+), 83 deletions(-)
diff --git a/doc/src/sgml/queries.sgml b/doc/src/sgml/queries.sgml
index 572e968273..ef0ca56c66 100644
--- a/doc/src/sgml/queries.sgml
+++ b/doc/src/sgml/queries.sgml
@@ -2112,20 +2112,20 @@ <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
+ WHERE g.id = sg.link AND NOT is_cycle
)
SELECT * FROM search_graph;
</programlisting>
@@ -2140,17 +2140,17 @@ <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
+ WHERE g.id = sg.link AND NOT is_cycle
)
SELECT * FROM search_graph;
</programlisting>
diff --git a/src/test/regress/expected/with.out b/src/test/regress/expected/with.out
index 67eaeb4f3e..457f3bf04f 100644
--- a/src/test/regress/expected/with.out
+++ b/src/test/regress/expected/with.out
@@ -579,79 +579,79 @@ insert into graph values
(1, 4, 'arc 1 -> 4'),
(4, 5, 'arc 4 -> 5'),
(5, 1, 'arc 5 -> 1');
-with recursive search_graph(f, t, label, path, cycle) as (
- select *, array[row(g.f, g.t)], false from graph g
+with recursive search_graph(f, t, label, is_cycle, path) as (
+ select *, false, array[row(g.f, g.t)] from graph g
union all
- select g.*, path || row(g.f, g.t), row(g.f, g.t) = any(path)
+ select g.*, row(g.f, g.t) = any(path), path || row(g.f, g.t)
from graph g, search_graph sg
- where g.f = sg.t and not cycle
+ where g.f = sg.t and not is_cycle
)
select * from search_graph;
- f | t | label | path | cycle
----+---+------------+-------------------------------------------+-------
- 1 | 2 | arc 1 -> 2 | {"(1,2)"} | f
- 1 | 3 | arc 1 -> 3 | {"(1,3)"} | f
- 2 | 3 | arc 2 -> 3 | {"(2,3)"} | f
- 1 | 4 | arc 1 -> 4 | {"(1,4)"} | f
- 4 | 5 | arc 4 -> 5 | {"(4,5)"} | f
- 5 | 1 | arc 5 -> 1 | {"(5,1)"} | f
- 1 | 2 | arc 1 -> 2 | {"(5,1)","(1,2)"} | f
- 1 | 3 | arc 1 -> 3 | {"(5,1)","(1,3)"} | f
- 1 | 4 | arc 1 -> 4 | {"(5,1)","(1,4)"} | f
- 2 | 3 | arc 2 -> 3 | {"(1,2)","(2,3)"} | f
- 4 | 5 | arc 4 -> 5 | {"(1,4)","(4,5)"} | f
- 5 | 1 | arc 5 -> 1 | {"(4,5)","(5,1)"} | f
- 1 | 2 | arc 1 -> 2 | {"(4,5)","(5,1)","(1,2)"} | f
- 1 | 3 | arc 1 -> 3 | {"(4,5)","(5,1)","(1,3)"} | f
- 1 | 4 | arc 1 -> 4 | {"(4,5)","(5,1)","(1,4)"} | f
- 2 | 3 | arc 2 -> 3 | {"(5,1)","(1,2)","(2,3)"} | f
- 4 | 5 | arc 4 -> 5 | {"(5,1)","(1,4)","(4,5)"} | f
- 5 | 1 | arc 5 -> 1 | {"(1,4)","(4,5)","(5,1)"} | f
- 1 | 2 | arc 1 -> 2 | {"(1,4)","(4,5)","(5,1)","(1,2)"} | f
- 1 | 3 | arc 1 -> 3 | {"(1,4)","(4,5)","(5,1)","(1,3)"} | f
- 1 | 4 | arc 1 -> 4 | {"(1,4)","(4,5)","(5,1)","(1,4)"} | t
- 2 | 3 | arc 2 -> 3 | {"(4,5)","(5,1)","(1,2)","(2,3)"} | f
- 4 | 5 | arc 4 -> 5 | {"(4,5)","(5,1)","(1,4)","(4,5)"} | t
- 5 | 1 | arc 5 -> 1 | {"(5,1)","(1,4)","(4,5)","(5,1)"} | t
- 2 | 3 | arc 2 -> 3 | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"} | f
+ 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)
-- ordering by the path column has same effect as SEARCH DEPTH FIRST
-with recursive search_graph(f, t, label, path, cycle) as (
- select *, array[row(g.f, g.t)], false from graph g
+with recursive search_graph(f, t, label, is_cycle, path) as (
+ select *, false, array[row(g.f, g.t)] from graph g
union all
- select g.*, path || row(g.f, g.t), row(g.f, g.t) = any(path)
+ select g.*, row(g.f, g.t) = any(path), path || row(g.f, g.t)
from graph g, search_graph sg
- where g.f = sg.t and not cycle
+ where g.f = sg.t and not is_cycle
)
select * from search_graph order by path;
- f | t | label | path | cycle
----+---+------------+-------------------------------------------+-------
- 1 | 2 | arc 1 -> 2 | {"(1,2)"} | f
- 2 | 3 | arc 2 -> 3 | {"(1,2)","(2,3)"} | f
- 1 | 3 | arc 1 -> 3 | {"(1,3)"} | f
- 1 | 4 | arc 1 -> 4 | {"(1,4)"} | f
- 4 | 5 | arc 4 -> 5 | {"(1,4)","(4,5)"} | f
- 5 | 1 | arc 5 -> 1 | {"(1,4)","(4,5)","(5,1)"} | f
- 1 | 2 | arc 1 -> 2 | {"(1,4)","(4,5)","(5,1)","(1,2)"} | f
- 2 | 3 | arc 2 -> 3 | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"} | f
- 1 | 3 | arc 1 -> 3 | {"(1,4)","(4,5)","(5,1)","(1,3)"} | f
- 1 | 4 | arc 1 -> 4 | {"(1,4)","(4,5)","(5,1)","(1,4)"} | t
- 2 | 3 | arc 2 -> 3 | {"(2,3)"} | f
- 4 | 5 | arc 4 -> 5 | {"(4,5)"} | f
- 5 | 1 | arc 5 -> 1 | {"(4,5)","(5,1)"} | f
- 1 | 2 | arc 1 -> 2 | {"(4,5)","(5,1)","(1,2)"} | f
- 2 | 3 | arc 2 -> 3 | {"(4,5)","(5,1)","(1,2)","(2,3)"} | f
- 1 | 3 | arc 1 -> 3 | {"(4,5)","(5,1)","(1,3)"} | f
- 1 | 4 | arc 1 -> 4 | {"(4,5)","(5,1)","(1,4)"} | f
- 4 | 5 | arc 4 -> 5 | {"(4,5)","(5,1)","(1,4)","(4,5)"} | t
- 5 | 1 | arc 5 -> 1 | {"(5,1)"} | f
- 1 | 2 | arc 1 -> 2 | {"(5,1)","(1,2)"} | f
- 2 | 3 | arc 2 -> 3 | {"(5,1)","(1,2)","(2,3)"} | f
- 1 | 3 | arc 1 -> 3 | {"(5,1)","(1,3)"} | f
- 1 | 4 | arc 1 -> 4 | {"(5,1)","(1,4)"} | f
- 4 | 5 | arc 4 -> 5 | {"(5,1)","(1,4)","(4,5)"} | f
- 5 | 1 | arc 5 -> 1 | {"(5,1)","(1,4)","(4,5)","(5,1)"} | t
+ f | t | label | is_cycle | path
+---+---+------------+----------+-------------------------------------------
+ 1 | 2 | arc 1 -> 2 | f | {"(1,2)"}
+ 2 | 3 | arc 2 -> 3 | f | {"(1,2)","(2,3)"}
+ 1 | 3 | arc 1 -> 3 | f | {"(1,3)"}
+ 1 | 4 | arc 1 -> 4 | f | {"(1,4)"}
+ 4 | 5 | arc 4 -> 5 | f | {"(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)"}
+ 2 | 3 | arc 2 -> 3 | f | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"}
+ 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 | {"(2,3)"}
+ 4 | 5 | arc 4 -> 5 | f | {"(4,5)"}
+ 5 | 1 | arc 5 -> 1 | f | {"(4,5)","(5,1)"}
+ 1 | 2 | arc 1 -> 2 | f | {"(4,5)","(5,1)","(1,2)"}
+ 2 | 3 | arc 2 -> 3 | f | {"(4,5)","(5,1)","(1,2)","(2,3)"}
+ 1 | 3 | arc 1 -> 3 | f | {"(4,5)","(5,1)","(1,3)"}
+ 1 | 4 | arc 1 -> 4 | f | {"(4,5)","(5,1)","(1,4)"}
+ 4 | 5 | arc 4 -> 5 | t | {"(4,5)","(5,1)","(1,4)","(4,5)"}
+ 5 | 1 | arc 5 -> 1 | f | {"(5,1)"}
+ 1 | 2 | arc 1 -> 2 | f | {"(5,1)","(1,2)"}
+ 2 | 3 | arc 2 -> 3 | f | {"(5,1)","(1,2)","(2,3)"}
+ 1 | 3 | arc 1 -> 3 | f | {"(5,1)","(1,3)"}
+ 1 | 4 | arc 1 -> 4 | f | {"(5,1)","(1,4)"}
+ 4 | 5 | arc 4 -> 5 | f | {"(5,1)","(1,4)","(4,5)"}
+ 5 | 1 | arc 5 -> 1 | t | {"(5,1)","(1,4)","(4,5)","(5,1)"}
(25 rows)
--
diff --git a/src/test/regress/sql/with.sql b/src/test/regress/sql/with.sql
index f85645efde..2eea297a71 100644
--- a/src/test/regress/sql/with.sql
+++ b/src/test/regress/sql/with.sql
@@ -308,22 +308,22 @@ CREATE TEMPORARY TABLE tree(
(4, 5, 'arc 4 -> 5'),
(5, 1, 'arc 5 -> 1');
-with recursive search_graph(f, t, label, path, cycle) as (
- select *, array[row(g.f, g.t)], false from graph g
+with recursive search_graph(f, t, label, is_cycle, path) as (
+ select *, false, array[row(g.f, g.t)] from graph g
union all
- select g.*, path || row(g.f, g.t), row(g.f, g.t) = any(path)
+ select g.*, row(g.f, g.t) = any(path), path || row(g.f, g.t)
from graph g, search_graph sg
- where g.f = sg.t and not cycle
+ where g.f = sg.t and not is_cycle
)
select * from search_graph;
-- ordering by the path column has same effect as SEARCH DEPTH FIRST
-with recursive search_graph(f, t, label, path, cycle) as (
- select *, array[row(g.f, g.t)], false from graph g
+with recursive search_graph(f, t, label, is_cycle, path) as (
+ select *, false, array[row(g.f, g.t)] from graph g
union all
- select g.*, path || row(g.f, g.t), row(g.f, g.t) = any(path)
+ select g.*, row(g.f, g.t) = any(path), path || row(g.f, g.t)
from graph g, search_graph sg
- where g.f = sg.t and not cycle
+ where g.f = sg.t and not is_cycle
)
select * from search_graph order by path;
--
2.27.0
view thread (27+ messages) latest in thread
Message-ID: <c5603982-0088-7f14-0caa-fdcd0c837b57@2ndquadrant.com>
Permalink: ../c5603982-0088-7f14-0caa-fdcd0c837b57@2ndquadrant.com/
Also on: postgresql.org/message-id/c5603982-0088-7f14-0caa-fdcd0c837b57@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, vik@postgresfriends.org
Subject: Re: SEARCH and CYCLE clauses
In-Reply-To: <c5603982-0088-7f14-0caa-fdcd0c837b57@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