Postgres: Nested records in a Recursive query in depth first manner

Question

I am working on a simple comment system where a user can comment on other comments, thus creating a hierarchy. To get the comments in a hierarchical order I am using Common Table Expression in Postgres.

Below are the fields and the query used:

id
user_id
parent_comment_id
message

WITH RECURSIVE CommentCTE AS (
    SELECT id, parent_comment_id, user_id
    FROM comment
    WHERE parent_comment_id is NULL

    UNION ALL

    SELECT child.id, child.parent_comment_id, child.user_id
    FROM comment child
    JOIN CommentCTE
    ON child.parent_comment_id = CommentCTE.id
)
SELECT * FROM CommentCTE

The above query returns records in a breadth first manner:

id       parent_comment_id       user_id
10              null                30
9               null                30
11               9                  30
14              10                  31
15              10                  31
12              11                  30
13              12                  31

But can it be modified to achieve something like below where records are returned together for that comment set, in a depth first manner? The point is to get the data in this way to make rendering on the Front-end smoother.

id       parent_comment_id       user_id
9               null                30
11               9                  30
12              11                  30
13              12                  31
10              null                30
14              10                  31
15              10                  31

Borisonekenobi · Accepted Answer · 2024-06-08 18:29:16Z

9

Generally, I solve this problem by synthesizing a "Path" column which can be sorted lexically, e.g. 0001:0003:0006:0009 is a child of 0001:0003:0006. Each child entry can be created by concatenating the path element to the parent's path. You don't have to return this column to the client, just use it for sorting.

id	parent_comment_id	user_id	sort_key
9	null	30	0009
11	9	30	0009:0011
12	11	30	0009:0011:0012
13	12	31	0009:0011:0012:0013
10	null	30	0010
14	10	31	0010:0014
15	10	31	0010:0015

The path element doesn't have to be anything in particular provided it sorts lexically in the order you want children at that level to sort, and is unique at that level. Basing it on an auto-incrementing ID is fine.

Using a fixed length path element is not strictly speaking necessary but makes it easier to reason about.

WITH RECURSIVE CommentCTE AS (
    SELECT id, parent_comment_id, user_id, 
           lpad(id::text, 4) sort_key
    FROM comment
    WHERE parent_comment_id is NULL

    UNION ALL

    SELECT child.id, child.parent_comment_id, child.user_id, 
           concat(CommentCTE.sort_key, ':', lpad(id::text, 4))
    FROM comment child
    JOIN CommentCTE
      ON child.parent_comment_id = CommentCTE.id
)
SELECT * FROM CommentCTE order by sort_key;

edited Jun 8, 2024 at 18:29

Borisonekenobi

5294 silver badges19 bronze badges

answered Apr 30, 2018 at 12:18

Ben

35.8k6 gold badges81 silver badges117 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Ben Over a year ago

Occurs to me now that in PostgreSQL the ideal data type for the column, is something like int[] rather than text.

ashwin mahajan Over a year ago

Reason? Because ordering or comparing integers would be faster than strings?

Ben Over a year ago

I mean it should be an array of whatever the type of 'Id' column is, this means you avoid all the conversion to text. Comparison would be similar time.

Ciro Santilli OurBigBook.com Over a year ago

Here's the array version you mentioned btw: stackoverflow.com/a/77282307/895245

Ciro Santilli OurBigBook.com · Accepted Answer · 2023-10-27 07:25:24Z

Path enumeration with arrays for preorder traversal

Ben mentioned string concatenation, but as he noted in the comments, an array approach is even cleaner:

WITH RECURSIVE CommentCTE AS (
SELECT id, parent_comment_id, user_id, 
    array[0] sort_key
FROM comment
WHERE parent_comment_id is NULL

UNION ALL

SELECT child.id, child.parent_comment_id, child.user_id,
    CommentCTE.sort_key || id
FROM comment child
JOIN CommentCTE
ON child.parent_comment_id = CommentCTE.id
)
SELECT * FROM CommentCTE order by sort_key

This approach is actually mentioned in the documentation at: https://www.postgresql.org/docs/16/queries-with.html#QUERIES-WITH-RECURSIVE

Also since 14 we have the SEARCH keyword which offers a shortcut for that solution:

WITH RECURSIVE CommentCTE AS (
SELECT id, parent_comment_id, user_id
FROM comment
WHERE parent_comment_id is NULL

UNION ALL

SELECT child.id, child.parent_comment_id, child.user_id
FROM comment child
JOIN CommentCTE
ON child.parent_comment_id = CommentCTE.id
)
SEARCH DEPTH FIRST BY "id" SET "sort_key"

SELECT * FROM CommentCTE order by sort_key

I have provided a minimal runnable example of this at: Preorder tree traversal using recursive CTEs in SQL

Collectives™ on Stack Overflow

Postgres: Nested records in a Recursive query in depth first manner

2 Answers 2

4 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related