CODEWITHSUNDEEP
postgresqlhierarchical-datarecursive-query
vdegenne
vdegenne

Reputation: 13298

how can I get all ids starting from a given id recursively in a postgresql table that references itself?

the title may not be very clear so let's consider this example (this is not my code, just taking this example to model my request)

I have a table that references itself (like a filesystem)

 id |  parent  | name
----+----------+-------
 1  |   null   |   /
 2  |    1     |  home
 3  |    2     |  user
 4  |    3     |  bin
 5  |    1     |  usr
 6  |    5     |  local

Is it possible to make a sql request so if I choose :

1 I will get a table containing 2,3,4,5,6 (because this is the root) so matching :

2 I will get a table containing 3,4 so matching :

and so on

Upvotes: 1

Views: 1776

Answers (1)

klin
klin

Reputation: 121784

Use recursive common table expression. Always starting from the root, use an array of ids to get paths for a given id in the WHERE clause.

For id = 1:

with recursive cte(id, parent, name, ids) as (
    select id, parent, name, array[id]
    from my_table
    where parent is null
union all
    select t.id, t.parent, concat(c.name, t.name, '/'), ids || t.id
    from cte c
    join my_table t on c.id = t.parent
)
select id, name 
from cte
where 1 = any(ids) and id <> 1

 id |         name          
----+-----------------------
  2 | /home/
  5 | /usr/
  6 | /usr/local/
  3 | /home/user/
  4 | /home/user/bin/
(5 rows)

For id = 2:

with recursive cte(id, parent, name, ids) as (
    select id, parent, name, array[id]
    from my_table
    where parent is null
union all
    select t.id, t.parent, concat(c.name, t.name, '/'), ids || t.id
    from cte c
    join my_table t on c.id = t.parent
)
select id, name 
from cte
where 2 = any(ids) and id <> 2

 id |         name          
----+-----------------------
  3 | /home/user/
  4 | /home/user/bin/
(2 rows)

Bidirectional query

The question is really interesting. The above query works well but is inefficient as it parses all tree nodes even when we're asking for a leaf. The more powerful solution is a bidirectional recursive query. The inner query walks from a given node to top, while the outer one goes from the node to bottom.

with recursive outer_query(id, parent, name) as (
    with recursive inner_query(qid, id, parent, name) as (
        select id, id, parent, name
        from my_table
        where id = 2        -- parameter
    union all
        select qid, t.id, t.parent, concat(t.name, '/', q.name)
        from inner_query q
        join my_table t on q.parent = t.id
    )
    select qid, null::int, right(name, -1)
    from inner_query
    where parent is null
union all
    select t.id, t.parent, concat(q.name, '/', t.name)
    from outer_query q
    join my_table t on q.id = t.parent
)
select id, name
from outer_query
where id <> 2;          -- parameter

Upvotes: 1

Related Questions