Postgres – How to achieve UNION behaviour with UNION ALL?

I have a table with parent and child ids.

create table if not exists stack (
    parent int,
    child int
)

Each parent can have multiple children and each child can have multiple children again.

insert into stack (parent, child) values
    (1,2),
    (2,3),
    (3,4),
    (4,5),
    (5,6),
    (6,7),
    (7,8),
    (8,9),
    (9,null),
    (1,7),
    (7,8),
    (8,9),
    (9,null);

The data looks like this.

|parent|child|
|------|-----|
|1     |2    |
|2     |3    |
|3     |4    |
|4     |5    |
|5     |6    |
|6     |7    |
|7     |8    |
|8     |9    |
|9     |NULL |
|1     |7    |
|7     |8    |
|8     |9    |
|9     |NULL |

I’d like to find all children. I can use a recursive cte with a UNION ALL.

with recursive cte as (
select
    child
from
    stack
where
      stack.parent = 1
union
select
    stack.child
from
    cte
left join stack on
    cte.child = stack.parent
where
    cte.child is not null
  )
select * from cte;

This gives me the result I’d like to achieve.

|child|
|-----|
|2    |
|7    |
|3    |
|8    |
|4    |
|9    |
|5    |
|NULL |
|6    |

However I’d like to include the depth / level and also the path for each node. I can do this using a different recursive cte.

with recursive cte as (
select
    parent,
    child,
    0 as level,
    array[parent,
    child] as path
from
    stack
where
      stack.parent = 1
union all
select
    stack.parent,
    stack.child,
    cte.level + 1,
    cte.path || stack.child
from
    cte
left join stack on
    cte.child = stack.parent
where
    cte.child is not null
  )
select * from cte;

That gives me this data.

|parent|child|level|path                |
|------|-----|-----|--------------------|
|1     |2    |0    |{1,2}               |
|1     |7    |0    |{1,7}               |
|2     |3    |1    |{1,2,3}             |
|7     |8    |1    |{1,7,8}             |
|7     |8    |1    |{1,7,8}             |
|3     |4    |2    |{1,2,3,4}           |
|8     |9    |2    |{1,7,8,9}           |
|8     |9    |2    |{1,7,8,9}           |
|8     |9    |2    |{1,7,8,9}           |
|8     |9    |2    |{1,7,8,9}           |
|4     |5    |3    |{1,2,3,4,5}         |
|9     |     |3    |{1,7,8,9,}          |
|9     |     |3    |{1,7,8,9,}          |
|9     |     |3    |{1,7,8,9,}          |
|9     |     |3    |{1,7,8,9,}          |
|9     |     |3    |{1,7,8,9,}          |
|9     |     |3    |{1,7,8,9,}          |
|9     |     |3    |{1,7,8,9,}          |
|9     |     |3    |{1,7,8,9,}          |
|5     |6    |4    |{1,2,3,4,5,6}       |
|6     |7    |5    |{1,2,3,4,5,6,7}     |
|7     |8    |6    |{1,2,3,4,5,6,7,8}   |
|7     |8    |6    |{1,2,3,4,5,6,7,8}   |
|8     |9    |7    |{1,2,3,4,5,6,7,8,9} |
|8     |9    |7    |{1,2,3,4,5,6,7,8,9} |
|8     |9    |7    |{1,2,3,4,5,6,7,8,9} |
|8     |9    |7    |{1,2,3,4,5,6,7,8,9} |
|9     |     |8    |{1,2,3,4,5,6,7,8,9,}|
|9     |     |8    |{1,2,3,4,5,6,7,8,9,}|
|9     |     |8    |{1,2,3,4,5,6,7,8,9,}|
|9     |     |8    |{1,2,3,4,5,6,7,8,9,}|
|9     |     |8    |{1,2,3,4,5,6,7,8,9,}|
|9     |     |8    |{1,2,3,4,5,6,7,8,9,}|
|9     |     |8    |{1,2,3,4,5,6,7,8,9,}|
|9     |     |8    |{1,2,3,4,5,6,7,8,9,}|

My problem is that I have a lot of duplicate data. I’d like to get the same result as the UNION query but with the level and the path.

I tried something like

where
    cte.child is not null
    and stack.parent not in (cte.parent)

or

where
    cte.child is not null
    and not exists (select parent from cte where cte.parent = stack.parent)

but the first does not change anything and the second returns an error.

ERROR: recursive reference to query "cte" must not appear within a subquery

Any ideas? Thank you very much!

Answer

Your problem is inappropriate table data. Your table contains the information that 8 is a direct child to 7 twice for instance. I suggest you remove the duplicate data and implement a unique constraint on the pairs.

If you cannot do so for some reason, make the rows distinct in your query:

with recursive
  good_stack as (select distinct * from stack)
 ,cte as 
  (
    select
      parent,
      child,
      0 as level,
      array[parent,
      child] as path
    from good_stack
    where good_stack.parent = 1
    union all
    select
      good_stack.parent,
      good_stack.child,
      cte.level + 1,
      cte.path || good_stack.child
    from cte
    left join good_stack on cte.child = good_stack.parent
    where cte.child is not null and good_stack.child is not null
  )
select * from cte;

Demo: https://dbfiddle.uk/?rdbms=postgres_13&fiddle=acb1d7a1a1d26c3fd9caf0e7dedc12b2

(You may also make the columns not nullable. The entries 9|null add no information. If the table were lacking these entries, 9 would still be without a child.)