Count childs of parent with sql or save in column?

Question

In postgres I have a threaded setup where parent id has many childs and childs can have childs. What is the most efficient way to get the count with a sql statement similar to this:

WITH RECURSIVE cte (id, message, author, path, parent_id, depth)  AS (
    SELECT  id,
        message,
        author,
        array[id] AS path,
        parent_id,
        1 AS depth
    FROM comments
    WHERE parent_id IS NULL

    UNION ALL

    SELECT comments.id,
        comments.message,
        comments.author,
        cte.path || comments.id,
        comments.parent_id,
        cte.depth + 1 AS depth
    FROM comments
    JOIN cte 
        ON comments.parent_id = cte.id
)
SELECT id, message, author, path, depth 
FROM cte
ORDER BY path;`

Is it better to count the child, or have a column that keeps track when a row is insert an increment and pull that column with the query?

If counting from sql, how would I implement that?

Answer 1

I assume you want to count the number of immediate childrent for each node in the tree. One easy solution is to do that with a sub-select:

WITH RECURSIVE cte (id, message, author, path, parent_id, depth)  AS (
    SELECT  id,
        message,
        author,
        array[id] AS path,
        parent_id,
        1 AS depth
    FROM comments
    WHERE parent_id IS NULL

    UNION ALL

    SELECT comments.id,
        comments.message,
        comments.author,
        cte.path || comments.id,
        comments.parent_id,
        cte.depth + 1 AS depth
    FROM comments
    JOIN cte 
        ON comments.parent_id = cte.id
)
SELECT id, message, author, path, depth
     , (select count(1) from cte as cte2
        where cte2.parent_id = cte.id) as num_children
FROM cte
ORDER BY path;

An alternative is to use comments instead of cte:

     , (select count(1) from comments as c
        where c.parent_id = cte.id) as num_children

Personally I would stay away from storing this number.

If all you are interested in is the number of children for all nodes there is no need to recursively traverse the tree, a self join or a sub-select is sufficient:

select id, message, author
     , (select count(1) from comments as c2
        where c2.parent_id = c1.id) as num_children
from comments as c1

The transformation to use a join instead is straight forward.

If you are interested in alternatives to recursively traverse the tree there are options such as NESTED SETS. You can google for the details, but the idea is to store an upper bound and a lower bound for each node. A node is an ancestor to another node if it subsumes that node. Main drawback with this approach is that it is difficult to maintain the bounds.

Yet another approach is to store a MATERIALIZED PATH for each node (much like your array).

None of these have a parent_id attribute. A third approach that do use the parent_id attribute is to have a separate ancestor table. This is known as the TRANSITIVE CLOSURE of parent_id. It is suitible to maintain this relation with triggers.

Finally, all of these models (including the recursive one you mention) have benefits as well as drawbacks, choose the one that fits your scenario best.