Recursive CTEs: Trees & Graphs
Advanced · 24 min read · ▶ live playground · ✦ checkpoint
Recursive CTEs let SQL answer questions that need "keep following the link until there is nowhere left to go." They are how you walk org charts, category trees, threaded comments, route maps, and ingredient lists without hard-coding "join to the same table three times and hope the tree is only three levels deep."
A recursive CTE is a WITH query that can feed one round of rows into the next round. It has two halves: the anchor, which finds the first rows, and the recursive step, which finds the next rows from the latest rows found.
Anchor, recursive step, stop
The café staff table already stores a hierarchy: each row has a manager_id pointing back to another staff row, and Rosa has NULL because she is the root.
WITH RECURSIVE org_tree AS (
SELECT s.id,
s.name,
s.role,
s.manager_id,
0 AS depth,
s.name AS path,
'/' || s.id || '/' AS path_ids
FROM staff AS s
WHERE s.manager_id IS NULL
UNION ALL
SELECT s.id,
s.name,
s.role,
s.manager_id,
ot.depth + 1 AS depth,
ot.path || ' > ' || s.name AS path,
ot.path_ids || s.id || '/' AS path_ids
FROM staff AS s
JOIN org_tree AS ot
ON s.manager_id = ot.id
WHERE ot.depth < 10
AND ot.path_ids NOT LIKE '%/' || s.id || '/%'
)
SELECT name,
role,
depth,
path
FROM org_tree
ORDER BY path_ids; name | role | depth | path
-------+---------+-------+--------------------
Rosa | owner | 0 | Rosa
Ken | manager | 1 | Rosa > Ken
Ada | barista | 2 | Rosa > Ken > Ada
Tomas | barista | 2 | Rosa > Ken > Tomas
Yuki | baker | 2 | Rosa > Ken > Yuki
Priya | barista | 2 | Rosa > Ken > Priya
(6 rows)Read it top to bottom. The anchor asks for rows with no manager: Rosa. The recursive step joins staff to the latest rows in org_tree: Ken reports to Rosa, then Ada, Tomas, Yuki, and Priya report to Ken.
Two columns make recursion readable. Depth is how many links away a row is from the anchor. Path is the breadcrumb trail you followed to reach that row. The final WHERE is the safety rail: ot.depth < 10 caps the walk, and the path_ids check refuses to revisit an id that is already in the current path.
Pretty-printing a tree
Once you carry depth and path, display is just another expression. repeat(' ', depth) indents each row by two spaces per level, and the final ORDER BY path_ids keeps parents before children.
WITH RECURSIVE org_tree AS (
SELECT s.id,
s.name,
s.role,
0 AS depth,
'/' || s.id || '/' AS path_ids
FROM staff AS s
WHERE s.manager_id IS NULL
UNION ALL
SELECT s.id,
s.name,
s.role,
ot.depth + 1 AS depth,
ot.path_ids || s.id || '/' AS path_ids
FROM staff AS s
JOIN org_tree AS ot
ON s.manager_id = ot.id
WHERE ot.depth < 10
AND ot.path_ids NOT LIKE '%/' || s.id || '/%'
)
SELECT repeat(' ', depth) || name AS org_chart,
role
FROM org_tree
ORDER BY path_ids; org_chart | role
-----------+---------
Rosa | owner
Ken | manager
Ada | barista
Tomas | barista
Yuki | baker
Priya | barista
(6 rows)This is the same pattern for product categories and threaded comments. Change the table and the link column, keep the shape: anchor at the roots, recursive step from parent to child, carry depth and path, order by the path.
Cycle detection: graphs that bite back
A graph is data made of things and links between them. A cycle appears when following links can bring you back to a thing you already visited. Trees do not allow cycles; graphs often do.
This route map has one on purpose: kitchen → counter → pickup → kitchen. The query is a reachability query: from kitchen, which stops can you reach by following any number of links, including the zero-hop starting stop?
WITH RECURSIVE walk AS (
SELECT 'kitchen'::text AS stop,
0 AS depth,
'kitchen'::text AS path,
'/kitchen/'::text AS path_key
UNION ALL
SELECT cr.to_stop AS stop,
w.depth + 1 AS depth,
w.path || ' > ' || cr.to_stop AS path,
w.path_key || cr.to_stop || '/' AS path_key
FROM walk AS w
JOIN cafe_routes AS cr
ON cr.from_stop = w.stop
WHERE w.depth < 6
AND w.path_key NOT LIKE '%/' || cr.to_stop || '/%'
)
SELECT stop,
depth,
path
FROM walk
ORDER BY path; stop | depth | path
---------+-------+----------------------------
kitchen | 0 | kitchen
counter | 1 | kitchen > counter
patio | 2 | kitchen > counter > patio
pickup | 2 | kitchen > counter > pickup
(4 rows)The route from pickup back to kitchen exists, but the query refuses to follow it because /kitchen/ is already inside path_key. The depth cap is a second guard; the path guard is the one that preserves the meaning: each displayed route visits a stop at most once.
Bill-of-materials: multiply down the tree
A bill of materials lists what a thing is made of, including parts made of smaller parts. Recursion handles the "parts inside parts" walk; multiplication carries quantity down each link.
WITH RECURSIVE exploded AS (
SELECT dp.parent,
dp.child,
dp.qty,
1 AS depth,
'/' || dp.parent || '/' || dp.child || '/' AS path_key
FROM drink_parts AS dp
WHERE dp.parent = 'latte_kit'
UNION ALL
SELECT dp.parent,
dp.child,
e.qty * dp.qty AS qty,
e.depth + 1 AS depth,
e.path_key || dp.child || '/' AS path_key
FROM exploded AS e
JOIN drink_parts AS dp
ON dp.parent = e.child
WHERE e.depth < 5
AND e.path_key NOT LIKE '%/' || dp.child || '/%'
)
SELECT e.child AS ingredient,
sum(e.qty) AS total_qty
FROM exploded AS e
WHERE NOT EXISTS (
SELECT 1
FROM drink_parts AS dp
WHERE dp.parent = e.child
)
GROUP BY e.child
ORDER BY e.child; ingredient | total_qty
-------------+-----------
beans_grams | 36
milk_ml | 180
water_ml | 60
(3 rows)Two espresso shots at 18 grams each become 36 grams of beans. The same query shape works for assemblies, package dependencies, access-control inheritance, and "which downstream records are affected if this node changes?"
Recursive CTEs are the tool for "unknown number of hops." Next, Section 14 turns from walking existing links to generating rows that do not exist yet: number series and date spines.
Checkpoint
Answer all three to mark this lesson complete