BrevFeed
Sign in

28. Recursive CTEs: hierarchies and graphs

📖 Reading · 6 min
💡 Most code boxes below are live — edit one and hit Run. Boxes without a Run button are reference-only (they need a real Postgres server).

The problem plain SQL can't express

Every query so far operates on a fixed, known set of tables. But some questions require an unknown number of steps: "all subordinates under this manager, at any depth," "every category reachable from this one via sub-categories," "every day between two dates." Plain JOIN can't express "repeat this join an unknown number of times" — you'd need to write a different query for depth 1, depth 2, depth 3... A recursive CTE is SQL's answer: a WITH block that references itself.

The anatomy of a recursive CTE

WITH RECURSIVE cte_name AS (
    -- 1. Base case: the starting row(s), no self-reference here
    SELECT ...
    UNION ALL
    -- 2. Recursive case: references cte_name itself, building on prior results
    SELECT ...
    FROM cte_name
    JOIN some_table ON ...
)
SELECT * FROM cte_name;

Execution, conceptually: run the base case once to produce an initial result set. Then repeatedly run the recursive case, feeding in only the rows produced by the previous iteration (not the whole accumulated set each time), appending new rows to the total result — until an iteration produces zero new rows, at which point recursion stops. This "feed only the newest rows back in" detail is what makes it recursion rather than an infinite unbounded self-join, and it's the part people most often get wrong when hand-simulating what a recursive CTE does.

UNION ALL (not UNION) is standard between the two parts — using UNION would force a full duplicate-check across the whole accumulated result on every iteration, expensive and usually unnecessary since the recursion structure itself typically prevents exact duplicate rows.

Example 1: a number series (the simplest possible recursive CTE)

WITH RECURSIVE counter AS (
    SELECT 1 AS n                    -- base case: start at 1
    UNION ALL
    SELECT n + 1 FROM counter WHERE n < 10   -- recursive case: +1 each time, stop at 10
)
SELECT n FROM counter;

This produces the numbers 1 through 10. Trace it by hand once: base case gives {1}. Iteration 1 takes {1}, produces {2} (since 1 < 10). Iteration 2 takes {2}, produces {3}. ... Iteration 9 takes {9}, produces {10}. Iteration 10 takes {10}, the WHERE n < 10 condition is now false, produces nothing — recursion stops. Ten total rows accumulated across all iterations.

(For this specific use case — a number series — Postgres's built-in generate_series(1, 10) is simpler and what you'd actually use in real code. The recursive version above exists purely to demonstrate the mechanics on the simplest possible case before tackling a real hierarchy.)

Example 2: hierarchy traversal, using pagila's category structure

pagila's category table is flat (no parent-category column), so this lesson builds a small hypothetical hierarchy to demonstrate the pattern properly — the shape below is exactly what you'd use for a real employee.manager_id self-reference or a genuine nested-category schema:

CREATE TEMP TABLE category_tree (
    category_id integer PRIMARY KEY,
    name text,
    parent_id integer REFERENCES category_tree(category_id)
);

INSERT INTO category_tree VALUES
    (1, 'Media', NULL),
    (2, 'Film', 1),
    (3, 'Music', 1),
    (4, 'Action Film', 2),
    (5, 'Comedy Film', 2);

WITH RECURSIVE tree AS (
    -- Base case: root nodes (no parent)
    SELECT category_id, name, parent_id, 0 AS depth
    FROM category_tree
    WHERE parent_id IS NULL
    UNION ALL
    -- Recursive case: children of whatever was found in the previous step
    SELECT c.category_id, c.name, c.parent_id, t.depth + 1
    FROM category_tree c
    JOIN tree t ON c.parent_id = t.category_id
)
SELECT repeat('  ', depth) || name AS indented_name, depth
FROM tree
ORDER BY depth, name;

The depth column is a common, useful addition — computed as 0 in the base case and parent's depth + 1 in the recursive case, giving you "how deep in the tree is this row" essentially for free, useful both for display (indentation, as above) and as a safety bound.

Guarding against runaway recursion

A cyclic graph (A → B → A) would recurse forever without a guard, since nothing would ever produce zero new rows. Two standard defenses:

  1. A depth limit, as a WHERE depth < N in the recursive term — simple, always works, requires picking a sensible max depth.
  2. Cycle detection, tracking visited nodes in an array and checking NOT (next_node = ANY(visited_path)) before adding a new row — more precise, standard for genuinely graph-shaped (not strictly-hierarchical) data.

Postgres also enforces a hard safety valve: WITH RECURSIVE has no built-in row limit by default, so an actual infinite recursion will exhaust memory/time — always test a new recursive CTE against small, known-bounded data first, and add an explicit depth guard for anything touching data you don't fully control the shape of.

Check yourself

  1. Why does the recursive term use UNION ALL rather than UNION by convention?
  2. In the number-series example, trace by hand: what row(s) does iteration 3 receive as input, and what does it produce as output?
  3. What are the two standard defenses against infinite recursion on cyclic data, and when would you reach for each?
← Previous Next →