Re: SELECT all the rows where id is children of other node.

> On Aug 19, 2019, at 7:42 PM, pabloa98 <pabloa98(at)gmail(dot)com> wrote:
>
> Hello,
>
> I have a huge table (100 million rows) of relations between nodes by id in a Postgresql 11 server. Like this:
>
> CREATE TABLE relations (
> pid INTEGER NOT NULL,
> cid INTEGER NOT NULL,
> )
>
> This table has parent-child relations references between nodes by id. Like:
>
> pid -> cid
> n1 -> n2
> n1 -> n3
> n1 -> n4
> n2 -> n21
> n2 -> n22
> n2 -> n23
> n22 -> n221
> n22 -> n222
>
> I would like to get a list of all the nodes being children (direct or indirect) of any other node.
>
> Example. The children of:
>
> 1) n3: [] (n3 has not children)
> 2) n22: [n221, n222] (n22 has 2 children: n221 and n222)
> 3) n1: [n2, n21, n22, n23, n221, n222] (n1 has 6 children including indirect children).
>
> this pseudo SQL:
>
> SELECT *
> FROM relations
> WHERE has_parent(myId)
>
> It can be solved with a recursive function or stored procedure. But that requires several passes. Is it possible to solve it in one pass? Perhaps using some low-level function or join or some index expression or auxiliary columns?
>
> It is OK to create an index or similar using recursive expressions. However, the SELECT expressions should be solved in one pass because of speed.
>
>
> Pablo

Back at my desk now, to show the possibilities.

with recursive descendants(parent, child) as
(select p.p, p.c from kids p where not exists (select 1 from kids c where c.c = p.p) group by p.p, p.c
union all
select k.* from kids k, descendants d where k.p = d.child)
select * from descendants;

parent | child
--------+-------
1 | 3
1 | 2
1 | 4
2 | 21
2 | 22
2 | 23
22 | 221
22 | 222
(8 rows)

with recursive descendants(parent, child) as
(select p.p, p.c from kids p where not exists (select 1 from kids c where c.c = p.p) group by p.p, p.c
union all
select k.* from kids k, descendants d where k.p = d.child)
select d.parent, array_agg(d.child) from descendants d group by d.parent;

parent | array_agg
--------+------------
1 | {3,2,4}
22 | {221,222}
2 | {21,22,23}
(3 rows)