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

[Rob Sargent <robjsargent@xxxxxxxxx>]

On Aug 19, 2019, at 7:42 PM, pabloa98 <pabloa98@xxxxxxxxx> 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)