I'm trying to write a query to identify the path to each furthest descendant of a particular parent node in a table of tree structures like:

    0     1
    |     |
    2     3
    |     |
    4     5
   / \    |
 *6*  8  *7*

There are many parents, all children have one parent, parents have 0-5 children (but the graph is very "long" – most parents only have one child). There are no cycles.

I'm trying to efficiently identify the path to the furthest descendants of a specific node (and not to any intermediate nodes). E.g. in the above:

  • get_leaf_paths(1) would return 1 row: {1, 3, 5, 7}
  • get_leaf_paths(2) would return 2 rows: {2, 4, 6} and {2, 4, 8, 9}

Sample table:

    id bigint PRIMARY KEY,
    parent_id bigint,
    FOREIGN KEY (parent_id) REFERENCES graph(id)
INSERT INTO graph (id, parent_id)
    VALUES (0, NULL),
           (1, NULL),
           (2, 0),
           (3, 1),
           (4, 2),
           (5, 3),
           (6, 4),
           (7, 5),
           (8, 4),
           (9, 8);

I'm hoping for a result that looks something like:

SELECT get_leaf_paths.* FROM get_leaf_paths(0);
{0, 2, 4, 6}
{0, 2, 4, 8, 9}
(2 rows)

In my initial attempt at a function with a recursive query, I've had trouble selecting only the furthest leaves, especially since some branches are shorter than others (e.g. 6 and 9 above are at different depths). The paths can be very deep (thousands or millions of elements), so I would also like to avoid the excessive memory usage of generating paths for every intermediate node.

Any ideas would be greatly appreciated. Thanks!

1 Answer 1

cte AS ( SELECT id, 
                id::TEXT path,
                NOT EXISTS ( SELECT NULL
                             FROM graph gr
                             WHERE graph.id = gr.parent_id ) is_leaf
                FROM graph 
                WHERE id = 2 /* initital node id */
         UNION ALL
         SELECT graph.id, 
                cte.path || ',' || graph.id,
                NOT EXISTS ( SELECT NULL
                             FROM graph gr
                             WHERE graph.id = gr.parent_id ) 
         FROM cte JOIN graph ON cte.id = graph.parent_id)
SELECT path 
FROM cte
WHERE is_leaf


Multiple initial nodes may be applied too (WHERE id IN (0, 1)).

  • Thanks for the quick answer! This seems to produce a path for every intermediate node too – when running this query for a node with ~1 million children, would you expect it to waste a lot of memory, or can Postgres avoid creating all those unused paths? Or is there another way to optimize this for very long paths? Apr 9, 2021 at 5:59
  • 1
    can Postgres avoid creating all those unused paths? Noway. CTE must collect ALL rows, that's outer query which eliminates intermediate rows. If this is often-executed task then update your table structure and store FQP in it.
    – Akina
    Apr 9, 2021 at 6:02
  • Could you clarify what you mean by FQP? How could I update the table structure to make this more efficient? (Thanks!) Apr 9, 2021 at 6:17
  • 1
    Fully Qualified Path. I.e. each node stores additionally full path to the root node. In this case the query will be simple - CTE not needed, you only check that initial node is present in FQP and the node have no childs.
    – Akina
    Apr 9, 2021 at 6:29
  • 1
    Alternatively, if the most nodes have only one child, you may compact your table and store the structure (id, parent_id, intermediate_ids) where intermediate_ids is a chain of 1-child nodes (i.e. you'll store only roots, leafs and multi-child nodes rows).
    – Akina
    Apr 9, 2021 at 6:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.