patternsqlpostgresqlTip
Recursive CTEs for hierarchical data like org trees and comment threads
Viewed 0 times
recursive CTEWITH RECURSIVEhierarchytree traversaladjacency listorg chartcomment thread
Problem
Fetching all descendants in an adjacency-list hierarchy (parent_id column) requires multiple round trips to the database or application-level recursion, both of which are slow and fragile.
Solution
Use WITH RECURSIVE to traverse the hierarchy in a single query:
-- Fetch entire subtree rooted at node 5:
WITH RECURSIVE subtree AS (
-- Base case: start node
SELECT id, parent_id, name, 0 AS depth
FROM categories
WHERE id = 5
UNION ALL
-- Recursive case: children of current level
SELECT c.id, c.parent_id, c.name, s.depth + 1
FROM categories c
INNER JOIN subtree s ON c.parent_id = s.id
)
SELECT id, name, depth,
repeat(' ', depth) || name AS indented_name
FROM subtree
ORDER BY depth, name;
-- Guard against cycles:
WITH RECURSIVE safe_tree AS (
SELECT id, parent_id, ARRAY[id] AS path
FROM nodes WHERE parent_id IS NULL
UNION ALL
SELECT n.id, n.parent_id, t.path || n.id
FROM nodes n
JOIN safe_tree t ON n.parent_id = t.id
WHERE NOT n.id = ANY(t.path)
)
-- Fetch entire subtree rooted at node 5:
WITH RECURSIVE subtree AS (
-- Base case: start node
SELECT id, parent_id, name, 0 AS depth
FROM categories
WHERE id = 5
UNION ALL
-- Recursive case: children of current level
SELECT c.id, c.parent_id, c.name, s.depth + 1
FROM categories c
INNER JOIN subtree s ON c.parent_id = s.id
)
SELECT id, name, depth,
repeat(' ', depth) || name AS indented_name
FROM subtree
ORDER BY depth, name;
-- Guard against cycles:
WITH RECURSIVE safe_tree AS (
SELECT id, parent_id, ARRAY[id] AS path
FROM nodes WHERE parent_id IS NULL
UNION ALL
SELECT n.id, n.parent_id, t.path || n.id
FROM nodes n
JOIN safe_tree t ON n.parent_id = t.id
WHERE NOT n.id = ANY(t.path)
)
Why
WITH RECURSIVE implements a fixpoint iteration: the recursive term keeps adding rows until it produces no new ones. This is equivalent to a BFS traversal and runs entirely inside PostgreSQL.
Gotchas
- Infinite loops are possible with cyclic data; guard with a path array and cycle check
- UNION ALL is required (not UNION) for proper recursive semantics; UNION would deduplicate and may terminate early
- Add a depth or iteration counter and a WHERE depth < 100 guard for safety
- ltree extension offers an alternative for very deep or frequently-queried hierarchies
Code Snippets
Traverse upward to find all ancestor nodes
-- Ancestors (upward traversal):
WITH RECURSIVE ancestors AS (
SELECT id, parent_id, name FROM categories WHERE id = 42
UNION ALL
SELECT c.id, c.parent_id, c.name
FROM categories c
JOIN ancestors a ON c.id = a.parent_id
)
SELECT * FROM ancestors;Context
Adjacency-list tables representing category trees, org charts, folder structures, or threaded comments
Revisions (0)
No revisions yet.