Order SQL results where each record referencing another record on the same table comes after the referenced record

I have the following data:

id, parent_id
1, 3
2, null
3, 2
4, 2

Where parent_id is a reference to the SAME table.

I need to sort these columns so that each record is after its parent (not necessarily immediately after).

So I would expect this result:

id, parent_id
2, null
3, 2
1, 3
4, 2

I’m guessing there is no clean efficient way to do this without any significant schema changes, but in case anybody can think of a method I’m asking this here.

One possible method would be to do multiple queries where each time the parent_id must be in one of the previous queries results. But this wouldn’t be very efficient.

Answer

You will need to recurse to accomplish this:

with recursive hier as (
  select *, 0 as hlevel
    from idparent
   where parent_id is null
  union all
  select c.*, p.hlevel + 1
    from hier p
    join idparent c on p.id = c.parent_id
)
select * from hier
 order by hlevel;

 id | parent_id | hlevel 
----+-----------+--------
  2 |           |      0
  3 |         2 |      1
  4 |         2 |      1
  1 |         3 |      2
(4 rows)