PostgreSQL – retrieve all IDs in a tree for a given subnode

postgresqlrecursivetree

I have a non-binary tree of customer, and I need to obtain all the IDs in a tree for the given node.

The table is very simple, just an join table with a parent id and child id.
This is a representation of the tree I stored in my db.

In this example if I search for node 17 I need in return 14-17. If I search for 11 I need in return 1-6-5-4-8-11-12-7-2-10-3.

The order is not important. I only need the ID to avoid circularity when adding children to a node.

I created this query.
The ancestor part works fine, I retrieve all parent nodes, but for the descendants I have some trouble. I'm only able to retrieve some part of the tree.
For example, with node 11 I retrieve 4-10-6-11-7-8, so all right part of the tree is missing.

WITH RECURSIVE
-- starting node(s)
starting (parent, child) AS
(
  SELECT t.parent, t.child
  FROM public.customerincustomer AS t
  WHERE t.child = :node or t.parent = :node
)
,
ancestors (parent, child) AS
(
  SELECT t.parent, t.child
  FROM public.customerincustomer AS t
  WHERE t.parent IN (SELECT parent FROM starting)
  UNION ALL
  SELECT t.parent, t.child
  FROM public.customerincustomer AS t JOIN ancestors AS a ON t.child = a.parent
),
descendants (parent, child) AS
(
  SELECT t.parent, t.child
  FROM public.customerincustomer AS t
  WHERE t.parent IN (SELECT parent FROM starting) or t.child in (select child from starting)
  UNION ALL
  SELECT t.parent, t.child
  FROM public.customerincustomer AS t JOIN ancestors AS a ON t.parent = a.child
)

table ancestors
union all
table descendants

UPDATE

I see that many examples included in the tree table also the root in form (root_id, null).

In my case I don't have this record.

For example, taking the smallest tree 14->17, in my table I have only one record
parent, child

14 17

Best Answer

A very primitive implementation:

It basically divides the problem into two subproblems:

First find all the ancestors of the node in question (including the node itself). If the node has no parents, then this would be just itself.
Then find the descendants of all those ancestors (including themselves). We may have several nodes in the ancestors result set, we may get duplicates here, so we use UNION (and not UNION ALL) to remove them.
Note that the query will work even if the input node is a root with has no children.
It will also work if the data set is not a forest of trees but an arbitrary directed graph (where nodes can have more than one parent).

The query:

WITH RECURSIVE 
ancestors (parent) AS
(
  SELECT :node                      -- start with the given node
  UNION ALL
  SELECT t.parent                   -- and find all its ancestors
  FROM public.customerincustomer AS t JOIN ancestors AS a ON t.child = a.parent
),
descendants (customer) AS
(
  SELECT parent AS customer       -- now start with all the ancestors
  FROM ancestors
  UNION 
  SELECT t.child                  -- and find all their descendants
  FROM public.customerincustomer AS t JOIN descendants AS d ON t.parent = d.customer
)
SELECT customer
FROM descendants ;

Related Solutions

PostgreSQL tree structure and recursive CTE optimization

If you really have to modify these data rarely, then you can simply store the result of the CTE in a table, and run queries against this table. You can define indexes based on your typical queries.
Then TRUNCATE and repopulate (and ANALYZE) as necessary.

On the other hand, if you can put the CTE in separate stored procedures rather than a view, you can easily put your conditions in the CTE part rather then the final SELECT (which is basically what you do querying against tree_view_1), so that much less rows will be involved in the recursion. From the query plan it looks like that PostgreSQL estimates row numbers based on some far-from-true assumptions, probably producing suboptimal plans - this effect can be reduced somewhat with the SP solution.

EDIT I may miss something, but just noticed that in the non-recursive term you don't filter the rows. Possibly you want to include only root nodes there (WHERE parent_id IS NULL) - I'd expect much less rows and recursions this way.

EDIT 2 AS it slowly became clear for me from the comments, I misthought the recursion in the original question going the other way. Here I mean starting from the root nodes and going deeper in the recursion.

Postgresql – How to sort the results of a recursive query in an expanded tree-like fashion

An array representing the path from the root up to the leaf should achieve the desired sort order:

WITH RECURSIVE node_rec AS (
   (SELECT 1 AS depth, ARRAY[node] AS path, *
    FROM   nodes
    WHERE  parent IS NULL
    LIMIT  10
   )    
    UNION ALL
    SELECT r.depth + 1, r.path || n.node, n.*
    FROM   node_rec r 
    JOIN   nodes    n ON n.parent = r.node
    WHERE  r.depth < 4
)
SELECT *
FROM   node_rec
ORDER  BY path;

If two or more child nodes have the same parent node, I want them to be sorted by their timestamp.

Shift the path by one towards the root and order by that column additionally:

WITH RECURSIVE node_rec AS (
   (SELECT 1 AS depth, ARRAY[node] AS path, *
    FROM   nodes
    WHERE  parent IS NULL
    LIMIT  10
   )    
    UNION ALL
    SELECT r.depth + 1, r.path || n.parent, n.*
    FROM   node_rec r 
    JOIN   nodes    n ON n.parent = r.node
    WHERE  r.depth < 4
)
SELECT *
FROM   node_rec
ORDER  BY path, ts;

UPDATE

Best Answer

Related Solutions

PostgreSQL tree structure and recursive CTE optimization

Postgresql – How to sort the results of a recursive query in an expanded tree-like fashion

Related Question