postgresqlcommon-table-expressionrecursive-query

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


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

Solution

  • Generally I solve this problem by synthesising 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