Thread: WITH RECURSION output ordering with trees
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
UNIONALL SELECT parent.depth + 1, child.id, child.lookup, child.parent_id FROM parse_tree parent,
recursionAS 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
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
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_sampleparent 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
childon child.parent_id = parent.id
)
select id, lookup
from parse_tree
order by sort_path
;
This will output:
id | lookup
-----+-------- 1 | a1 2 | b11243 | c113645 | c111823 | c112 6 | b12583 | c122845 | c121 9 | b13 10 |
c131
(10 rows)
Thomas
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
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 FROMparse_tree parent JOIN recursion AS child ON child.parent_id = parent.id ) SELECT depth, id, lookup, parent_id FROM parse_tree ORDER BY path
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