pg.ddx.io pgsql-sql@postgresql.org mailing list archive
help / color / mirror / Atom feedWITH RECURSION output ordering with trees
6+ messages / 3 participants
[nested] [flat]
* WITH RECURSION output ordering with trees
@ 2009-07-10 09:10 Philippe Lang <philippe.lang@attiksystem.ch>
2009-07-10 11:09 ` Re: WITH RECURSION output ordering with trees Philippe Lang <philippe.lang@attiksystem.ch>
2009-07-10 11:23 ` Re: WITH RECURSION output ordering with trees Thomas Kellerer <spam_eater@gmx.net>
0 siblings, 2 replies; 6+ messages in thread
From: Philippe Lang @ 2009-07-10 09:10 UTC (permalink / raw)
To: pgsql-sql
Hi,
I'm playing with the new "WITH RECURSIVE" feature of 8.4. I'm trying to
figure out how to use it with trees.
Here is the test code I use:
---------------------------------------------------------
--DROP TABLE recursion;
CREATE TABLE recursion
(
id serial,
lookup varchar(16),
parent_id integer,
primary key(id),
foreign key(parent_id) references recursion(id)
);
INSERT INTO recursion VALUES(1, 'a1', NULL);
INSERT INTO recursion VALUES(2, 'b11', 1);
INSERT INTO recursion VALUES(645, 'c111', 2);
INSERT INTO recursion VALUES(823, 'c112', 2);
INSERT INTO recursion VALUES(243, 'c113', 2);
INSERT INTO recursion VALUES(6, 'b12', 1);
INSERT INTO recursion VALUES(845, 'c121', 6);
INSERT INTO recursion VALUES(583, 'c122', 6);
INSERT INTO recursion VALUES(9, 'b13', 1);
INSERT INTO recursion VALUES(10, 'c131', 9);
WITH RECURSIVE parse_tree (depth, id, lookup, parent_id) AS
(
SELECT
0,
parent.id,
parent.lookup,
parent.parent_id
FROM recursion AS parent
WHERE parent_id IS NULL
UNION ALL
SELECT
parent.depth + 1,
child.id,
child.lookup,
child.parent_id
FROM parse_tree parent, recursion AS child
WHERE child.parent_id = parent.id
)
SELECT * FROM parse_tree;
---------------------------------------------------------
Here is the result:
depth | id | lookup | parent_id
-------+-----+--------+-----------
0 | 1 | a1 |
1 | 2 | b11 | 1
1 | 6 | b12 | 1
1 | 9 | b13 | 1
2 | 645 | c111 | 2
2 | 823 | c112 | 2
2 | 243 | c113 | 2
2 | 845 | c121 | 6
2 | 583 | c122 | 6
2 | 10 | c131 | 9
I'd like to perform a real recursion, and show the tree structure in a
more appopriate way, like this:
depth | id | lookup | parent_id
-------+-----+--------+-----------
0 | 1 | a1 |
1 | 2 | b11 | 1
2 | 645 | c111 | 2
2 | 823 | c112 | 2
2 | 243 | c113 | 2
1 | 6 | b12 | 1
2 | 845 | c121 | 6
2 | 583 | c122 | 6
1 | 9 | b13 | 1
2 | 10 | c131 | 9
Any idea how to do that? (without trying to sort on the lookup column,
whose values can be random outside this test)
Best regards,
Philippe Lang
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: WITH RECURSION output ordering with trees
2009-07-10 09:10 WITH RECURSION output ordering with trees Philippe Lang <philippe.lang@attiksystem.ch>
@ 2009-07-10 11:09 ` Philippe Lang <philippe.lang@attiksystem.ch>
1 sibling, 0 replies; 6+ messages in thread
From: Philippe Lang @ 2009-07-10 11:09 UTC (permalink / raw)
To: pgsql-sql
pgsql-sql-owner@postgresql.org wrote:
> Hi,
>
> I'm playing with the new "WITH RECURSIVE" feature of 8.4. I'm trying
> to figure out how to use it with trees.
>
> Here is the test code I use:
>
> ---------------------------------------------------------
> --DROP TABLE recursion;
>
> CREATE TABLE recursion
> (
> id serial,
> lookup varchar(16),
> parent_id integer,
> primary key(id),
> foreign key(parent_id) references recursion(id) );
>
> INSERT INTO recursion VALUES(1, 'a1', NULL);
> INSERT INTO recursion VALUES(2, 'b11', 1);
> INSERT INTO recursion VALUES(645, 'c111', 2);
> INSERT INTO recursion VALUES(823, 'c112', 2);
> INSERT INTO recursion VALUES(243, 'c113', 2);
> INSERT INTO recursion VALUES(6, 'b12', 1);
> INSERT INTO recursion VALUES(845, 'c121', 6);
> INSERT INTO recursion VALUES(583, 'c122', 6);
> INSERT INTO recursion VALUES(9, 'b13', 1);
> INSERT INTO recursion VALUES(10, 'c131', 9);
>
> WITH RECURSIVE parse_tree (depth, id, lookup, parent_id) AS (
> SELECT
> 0,
> parent.id,
> parent.lookup,
> parent.parent_id
> FROM recursion AS parent
> WHERE parent_id IS NULL
>
> UNION ALL
>
> SELECT
> parent.depth + 1,
> child.id,
> child.lookup,
> child.parent_id
> FROM parse_tree parent, recursion AS child
> WHERE child.parent_id = parent.id
> )
>
> SELECT * FROM parse_tree;
> ---------------------------------------------------------
>
> Here is the result:
>
> depth | id | lookup | parent_id
> -------+-----+--------+-----------
> 0 | 1 | a1 |
> 1 | 2 | b11 | 1
> 1 | 6 | b12 | 1
> 1 | 9 | b13 | 1
> 2 | 645 | c111 | 2
> 2 | 823 | c112 | 2
> 2 | 243 | c113 | 2
> 2 | 845 | c121 | 6
> 2 | 583 | c122 | 6
> 2 | 10 | c131 | 9
>
> I'd like to perform a real recursion, and show the tree structure in
> a more appopriate way, like this:
>
> depth | id | lookup | parent_id
> -------+-----+--------+-----------
> 0 | 1 | a1 |
> 1 | 2 | b11 | 1
> 2 | 645 | c111 | 2
> 2 | 823 | c112 | 2
> 2 | 243 | c113 | 2
> 1 | 6 | b12 | 1
> 2 | 845 | c121 | 6
> 2 | 583 | c122 | 6
> 1 | 9 | b13 | 1
> 2 | 10 | c131 | 9
>
> Any idea how to do that? (without trying to sort on the lookup
> column, whose values can be random outside this test)
Hi again,
I reply to my own post: I found a way to parse the tree with the help of
the tablefunc contrib package:
---------------------------------------------------------
SELECT
t.depth,
t.id,
r.lookup,
t.parent_id
FROM connectby('recursion', 'id', 'parent_id', 'lookup', '1', 0)
AS t(id integer, parent_id integer, depth integer, o integer)
INNER JOIN recursion AS r
ON t.id = r.id
---------------------------------------------------------
depth | id | lookup | parent_id
-------+-----+--------+-----------
0 | 1 | a1 |
1 | 2 | b11 | 1
2 | 645 | c111 | 2
2 | 823 | c112 | 2
2 | 243 | c113 | 2
1 | 6 | b12 | 1
2 | 845 | c121 | 6
2 | 583 | c122 | 6
1 | 9 | b13 | 1
2 | 10 | c131 | 9
I guess this is hard to achieve with a "WITH RECURSIVE" call.
So my question is now: is the inclusion of "START WITH... CONNECT BY"
planned for Postgresql? I read a patch had been developed for Postgresql
8.3:
http://www.postgresql-support.de/blog/blog_hans.html
Best regards,
Philippe Lang
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: WITH RECURSION output ordering with trees
2009-07-10 09:10 WITH RECURSION output ordering with trees Philippe Lang <philippe.lang@attiksystem.ch>
@ 2009-07-10 11:23 ` Thomas Kellerer <spam_eater@gmx.net>
2009-07-10 11:50 ` Re: WITH RECURSION output ordering with trees Philippe Lang <philippe.lang@attiksystem.ch>
1 sibling, 1 reply; 6+ messages in thread
From: Thomas Kellerer @ 2009-07-10 11:23 UTC (permalink / raw)
To: pgsql-sql
Philippe Lang, 10.07.2009 11:10:
> Hi,
>
> I'm playing with the new "WITH RECURSIVE" feature of 8.4. I'm trying to
> figure out how to use it with trees.
>
> Here is the test code I use:
>
> I'd like to perform a real recursion, and show the tree structure in a
> more appopriate way, like this:
>
> Any idea how to do that? (without trying to sort on the lookup column,
> whose values can be random outside this test)
The manual has a nice hint on this adding up IDs to "generate" a path like column that can be used for sorting.
Try the following:
WITH RECURSIVE parse_tree (depth, id, lookup, parent_id, sort_path) AS
(
SELECT 0,
parent.id,
cast(parent.lookup as text),
parent.parent_id,
array[0] as sort_path
FROM recursion_sample parent
WHERE parent_id IS NULL
UNION ALL
SELECT
parent.depth + 1,
child.id,
rpad(' ', depth * 2) || child.lookup,
child.parent_id,
parent.sort_path || child.id
FROM parse_tree parent JOIN recursion_sample child on child.parent_id = parent.id
)
select id, lookup
from parse_tree
order by sort_path
;
This will output:
id | lookup
-----+--------
1 | a1
2 | b11
243 | c113
645 | c111
823 | c112
6 | b12
583 | c122
845 | c121
9 | b13
10 | c131
(10 rows)
Thomas
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: WITH RECURSION output ordering with trees
2009-07-10 09:10 WITH RECURSION output ordering with trees Philippe Lang <philippe.lang@attiksystem.ch>
2009-07-10 11:23 ` Re: WITH RECURSION output ordering with trees Thomas Kellerer <spam_eater@gmx.net>
@ 2009-07-10 11:50 ` Philippe Lang <philippe.lang@attiksystem.ch>
2009-07-10 12:33 ` Re: WITH RECURSION output ordering with trees Harald Fuchs <hari.fuchs@gmail.com>
0 siblings, 1 reply; 6+ messages in thread
From: Philippe Lang @ 2009-07-10 11:50 UTC (permalink / raw)
To: Thomas Kellerer <spam_eater@gmx.net>; pgsql-sql
pgsql-sql-owner@postgresql.org wrote:
> Philippe Lang, 10.07.2009 11:10:
>> Hi,
>>
>> I'm playing with the new "WITH RECURSIVE" feature of 8.4. I'm trying
>> to figure out how to use it with trees.
>>
>> Here is the test code I use:
>>
>> I'd like to perform a real recursion, and show the tree structure in
>> a more appopriate way, like this:
>>
>> Any idea how to do that? (without trying to sort on the lookup
>> column, whose values can be random outside this test)
>
>
> The manual has a nice hint on this adding up IDs to "generate" a path
> like column that can be used for sorting.
>
> Try the following:
>
> WITH RECURSIVE parse_tree (depth, id, lookup, parent_id, sort_path)
> AS ( SELECT 0,
> parent.id,
> cast(parent.lookup as text),
> parent.parent_id,
> array[0] as sort_path
> FROM recursion_sample parent
> WHERE parent_id IS NULL
> UNION ALL
> SELECT
> parent.depth + 1,
> child.id,
> rpad(' ', depth * 2) || child.lookup,
> child.parent_id,
> parent.sort_path || child.id
> FROM parse_tree parent JOIN recursion_sample child on
> child.parent_id = parent.id )
> select id, lookup
> from parse_tree
> order by sort_path
> ;
>
> This will output:
>
> id | lookup
> -----+--------
> 1 | a1
> 2 | b11
> 243 | c113
> 645 | c111
> 823 | c112
> 6 | b12
> 583 | c122
> 845 | c121
> 9 | b13
> 10 | c131
> (10 rows)
Hi Thomas,
Thanks for your answer. Si there a built-in function that would allow
generating the sort path based on the value of the lookup column,
instead of the id, which has no meaning at all?
If yes, we would get instead:
depth | id | lookup | parent_id
-------+-----+--------+-----------
0 | 1 | a1 |
1 | 2 | b11 | 1
2 | 645 | c111 | 2
2 | 823 | c112 | 2
2 | 243 | c113 | 2
1 | 6 | b12 | 1
2 | 845 | c121 | 6
2 | 583 | c122 | 6
1 | 9 | b13 | 1
2 | 10 | c131 | 9
Best regards,
Philippe Lang
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: WITH RECURSION output ordering with trees
2009-07-10 09:10 WITH RECURSION output ordering with trees Philippe Lang <philippe.lang@attiksystem.ch>
2009-07-10 11:23 ` Re: WITH RECURSION output ordering with trees Thomas Kellerer <spam_eater@gmx.net>
2009-07-10 11:50 ` Re: WITH RECURSION output ordering with trees Philippe Lang <philippe.lang@attiksystem.ch>
@ 2009-07-10 12:33 ` Harald Fuchs <hari.fuchs@gmail.com>
2009-07-10 13:05 ` Re: WITH RECURSION output ordering with trees Philippe Lang <philippe.lang@attiksystem.ch>
0 siblings, 1 reply; 6+ messages in thread
From: Harald Fuchs @ 2009-07-10 12:33 UTC (permalink / raw)
To: pgsql-sql
In article <E6A0649F1FBFA3408A37F505400E7AC215CE69@email.attiksystem.ch>,
"Philippe Lang" <philippe.lang@attiksystem.ch> writes:
> Thanks for your answer. Si there a built-in function that would allow
> generating the sort path based on the value of the lookup column,
> instead of the id, which has no meaning at all?
> If yes, we would get instead:
> depth | id | lookup | parent_id
> -------+-----+--------+-----------
> 0 | 1 | a1 |
> 1 | 2 | b11 | 1
> 2 | 645 | c111 | 2
> 2 | 823 | c112 | 2
> 2 | 243 | c113 | 2
> 1 | 6 | b12 | 1
> 2 | 845 | c121 | 6
> 2 | 583 | c122 | 6
> 1 | 9 | b13 | 1
> 2 | 10 | c131 | 9
Try this:
WITH RECURSIVE parse_tree (depth, id, lookup, parent_id, path) AS (
SELECT 0, parent.id, parent.lookup, parent.parent_id, parent.lookup::text
FROM recursion AS parent
WHERE parent_id IS NULL
UNION ALL
SELECT parent.depth + 1, child.id, child.lookup, child.parent_id,
parent.path || '.' || child.lookup
FROM parse_tree parent
JOIN recursion AS child ON child.parent_id = parent.id
)
SELECT depth, id, lookup, parent_id
FROM parse_tree
ORDER BY path
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: WITH RECURSION output ordering with trees
2009-07-10 09:10 WITH RECURSION output ordering with trees Philippe Lang <philippe.lang@attiksystem.ch>
2009-07-10 11:23 ` Re: WITH RECURSION output ordering with trees Thomas Kellerer <spam_eater@gmx.net>
2009-07-10 11:50 ` Re: WITH RECURSION output ordering with trees Philippe Lang <philippe.lang@attiksystem.ch>
2009-07-10 12:33 ` Re: WITH RECURSION output ordering with trees Harald Fuchs <hari.fuchs@gmail.com>
@ 2009-07-10 13:05 ` Philippe Lang <philippe.lang@attiksystem.ch>
0 siblings, 0 replies; 6+ messages in thread
From: Philippe Lang @ 2009-07-10 13:05 UTC (permalink / raw)
To: Harald Fuchs <hari.fuchs@gmail.com>; pgsql-sql
pgsql-sql-owner@postgresql.org wrote:
> In article
> <E6A0649F1FBFA3408A37F505400E7AC215CE69@email.attiksystem.ch>,
> "Philippe Lang" <philippe.lang@attiksystem.ch> writes:
>
>> Thanks for your answer. Si there a built-in function that would allow
>> generating the sort path based on the value of the lookup column,
>> instead of the id, which has no meaning at all?
>
>> If yes, we would get instead:
>
>> depth | id | lookup | parent_id
>> -------+-----+--------+-----------
>> 0 | 1 | a1 |
>> 1 | 2 | b11 | 1
>> 2 | 645 | c111 | 2
>> 2 | 823 | c112 | 2
>> 2 | 243 | c113 | 2
>> 1 | 6 | b12 | 1
>> 2 | 845 | c121 | 6
>> 2 | 583 | c122 | 6
>> 1 | 9 | b13 | 1
>> 2 | 10 | c131 | 9
>
> Try this:
>
> WITH RECURSIVE parse_tree (depth, id, lookup, parent_id, path) AS (
> SELECT 0, parent.id, parent.lookup, parent.parent_id,
> parent.lookup::text FROM recursion AS parent
> WHERE parent_id IS NULL
> UNION ALL
> SELECT parent.depth + 1, child.id, child.lookup, child.parent_id,
> parent.path || '.' || child.lookup
> FROM parse_tree parent
> JOIN recursion AS child ON child.parent_id = parent.id
> )
> SELECT depth, id, lookup, parent_id
> FROM parse_tree
> ORDER BY path
Works great, thanks! Of course, concatenating lookups...
Best regards,
Philippe
^ permalink raw reply [nested|flat] 6+ messages in thread
end of thread, other threads:[~2009-07-10 13:05 UTC | newest]
Thread overview: 6+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2009-07-10 09:10 WITH RECURSION output ordering with trees Philippe Lang <philippe.lang@attiksystem.ch>
2009-07-10 11:09 ` Philippe Lang <philippe.lang@attiksystem.ch>
2009-07-10 11:23 ` Thomas Kellerer <spam_eater@gmx.net>
2009-07-10 11:50 ` Philippe Lang <philippe.lang@attiksystem.ch>
2009-07-10 12:33 ` Harald Fuchs <hari.fuchs@gmail.com>
2009-07-10 13:05 ` Philippe Lang <philippe.lang@attiksystem.ch>
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