From 06224652f23441588b9d50cab7311e2c6ec05414 Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Tue, 14 Oct 2008 00:41:35 +0000 Subject: [PATCH] Add docs and regression test about sorting the output of a recursive query in depth-first search order. Upon close reading of SQL:2008, it seems that the spec's SEARCH DEPTH FIRST and SEARCH BREADTH FIRST options do not actually guarantee any particular result order: what they do is provide a constructed column that the user can then sort on in the outer query. So this is actually just as much functionality ... --- doc/src/sgml/queries.sgml | 15 ++++++++++-- src/test/regress/expected/with.out | 38 ++++++++++++++++++++++++++++++ src/test/regress/sql/with.sql | 10 ++++++++ 3 files changed, 61 insertions(+), 2 deletions(-) diff --git a/doc/src/sgml/queries.sgml b/doc/src/sgml/queries.sgml index ef9383a2f7..283dd0a73d 100644 --- a/doc/src/sgml/queries.sgml +++ b/doc/src/sgml/queries.sgml @@ -1,4 +1,4 @@ - + Queries @@ -1681,6 +1681,15 @@ SELECT * FROM search_graph; + + + 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 ORDER BY a + path column constructed in this way. + + + A helpful trick for testing queries when you are not certain if they might loop is to place a LIMIT @@ -1699,7 +1708,9 @@ SELECT n FROM t LIMIT 100; This works because PostgreSQL's implementation evaluates only as many rows of a WITH query as are actually fetched by the parent query. Using this trick in production is not - recommended, because other systems might work differently. + recommended, because other systems might work differently. Also, it + usually won't work if you make the outer query sort the recursive query's + results or join them to some other table. diff --git a/src/test/regress/expected/with.out b/src/test/regress/expected/with.out index 765910d48b..13bbb90325 100644 --- a/src/test/regress/expected/with.out +++ b/src/test/regress/expected/with.out @@ -499,6 +499,44 @@ select * from search_graph; 2 | 3 | arc 2 -> 3 | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"} | f (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 + union all + select g.*, path || row(g.f, g.t), row(g.f, g.t) = any(path) + from graph g, search_graph sg + where g.f = sg.t and not 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 +(25 rows) + -- -- test multiple WITH queries -- diff --git a/src/test/regress/sql/with.sql b/src/test/regress/sql/with.sql index 3107cbcb91..d79be72a35 100644 --- a/src/test/regress/sql/with.sql +++ b/src/test/regress/sql/with.sql @@ -272,6 +272,16 @@ with recursive search_graph(f, t, label, path, cycle) as ( ) 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 + union all + select g.*, path || row(g.f, g.t), row(g.f, g.t) = any(path) + from graph g, search_graph sg + where g.f = sg.t and not cycle +) +select * from search_graph order by path; + -- -- test multiple WITH queries -- -- 2.40.0