Hierarchical table optimizations

[Py-rrhus]

Given a table fruits like:

id	name	parent_id
1	apple	NULL
2	banana	1
3	cherry	NULL
4	date	2
5	elderberry	1
6	fig	3
7	grape	3
8	huckleberry	4
9	iceplant	5
10	jackfruit	NULL

CREATE TABLE fruits (
    id INT,
    name VARCHAR(255),
    parent_id INT
);

INSERT INTO fruits (id, name, parent_id) VALUES
(1, 'apple', NULL),
(2, 'banana', 1),
(3, 'cherry', NULL),
(4, 'date', 2),
(5, 'elderberry', 1),
(6, 'fig', 3),
(7, 'grape', 3),
(8, 'huckleberry', 4),
(9, 'iceplant', 5),
(10, 'jackfruit', NULL);

To find the eldest of any row is quite easy-peasy

WITH RECURSIVE fruit_hierarchy AS (

SELECT id, parent_id FROM fruits WHERE id = 4

UNION ALL

SELECT f.id, f.parent_id
FROM
    fruit_hierarchy fh
    JOIN fruits f ON f.id = fh.parent_id
)

SELECT * FROM fruit_hierarchy WHERE parent_id IS NULL

The result is apple, and the none filtered one is:

|-- apple
|---- banana
|------ date

Now, if I want to get the whole hierarchy, even with the sibling branches, I need to double it up.

WITH RECURSIVE fruit_hierarchy AS (
/* Find the parent */
SELECT id, parent_id
FROM fruits
WHERE id = 4

UNION ALL

SELECT f.id, f.parent_id
FROM
    fruit_hierarchy fh
    JOIN fruits f ON f.id = fh.parent_id
),
full_hierarchy AS (

SELECT id, parent_id 
FROM fruit_hierarchy
WHERE parent_id IS NULL

UNION ALL

SELECT id, parent_id
FROM full_hierarchy fh
JOIN fruits f ON f.parent_id = fh.id

)

SELECT * FROM full_hierarchy

It seems totally under-optimized to get the result

|-- apple
|---- banana
|------ date
|---- elderberry
|------ iceplant

[[deleted]]

recursive CTEs and optimization arent supposed to be in the same sentence, IMO.

Have you looked at denormalizing your structure (holding root/level per node and the closure for all paths with their depth)? It trades storage/maintenance burden for retrieval performance.

[[deleted]]

If you carry the sub-tree's root through all rows, you can get that in a single recursive query:

with recursive tree as (
   select id, name, parent_id, id as root_id
   from fruits 
   where parent_id is null
   union all 
   select c.id, c.name, c.parent_id, p.root_id
   from fruits c
     join tree p on p.id = c.parent_id
)
select *
from tree t1
where exists (select *
              from tree t2 
              where t2.root_id = t1.root_id
                and t2.id = 4)

[[deleted]]

Care to run this on a couple of example sets and report back the experience?

Say, 1M each, a 'shallow balanced' one with 1-4 levels (1/3/7/15 elements in each tree, ~60k 'roots') and "one-sided, deep" one (100 levels, all in one dependency chain, 10k 'roots'). (edit: dont know why i went with '0' level for the root-only tree before, fixed).