1

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*
      |
     *9*

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:

CREATE TABLE graph (
    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);
path
-----
{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
WITH RECURSIVE
cte AS ( SELECT id, 
                parent_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, 
                graph.parent_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

https://dbfiddle.uk/?rdbms=postgres_12&fiddle=2e40ff454f302033bf5e8cba8b0b0d85

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

6
  • 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? – Jason Dreyzehner Apr 9 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 at 6:02
  • Could you clarify what you mean by FQP? How could I update the table structure to make this more efficient? (Thanks!) – Jason Dreyzehner Apr 9 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 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 at 6:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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