Skip to content
Ephizen logo ephizen / wiki
CS 402

Recursive CTEs

WITH RECURSIVE walks trees and graphs in pure SQL — org charts, bill-of-materials, transitive closures, and the occasional Fibonacci.

SQL II — Analytical advanced #sql #queries #graphs

TL;DR

WITH RECURSIVE lets a CTE reference itself. The shape is always the same:

WITH RECURSIVE name AS (
    -- BASE: the seed rows
    SELECT … FROM …

    UNION ALL

    -- RECURSIVE: rows derived from the previous iteration
    SELECT … FROM name JOIN … ON …
)
SELECT * FROM name;

The engine repeatedly applies the recursive part to the most recent iteration’s rows until the recursive part returns zero rows. The union of all iterations is the result.

It’s how you walk hierarchies (org charts, file trees, bill of materials), compute transitive closures (friend-of-friend, package dependencies), and generate sequences (date spines, Fibonacci, Mandelbrot if you must).

The two things to get right: (1) a base case that defines the seeds; (2) a termination condition built into the recursive case so it eventually returns no new rows. Forget the second and you get an infinite loop — in Postgres, capped at runaway-protection limits or memory; in BigQuery, a hard recursion-depth limit.

A worked example — walking an org chart

CREATE TABLE employees (id int, name text, manager_id int);
INSERT INTO employees VALUES
  (1, 'CEO',    NULL),
  (2, 'VP-A',   1),
  (3, 'VP-B',   1),
  (4, 'Mgr-A1', 2),
  (5, 'Mgr-A2', 2),
  (6, 'Mgr-B1', 3),
  (7, 'IC-A1a', 4),
  (8, 'IC-A1b', 4),
  (9, 'IC-B1a', 6);

Standard tree: manager_id points to the parent’s id. The CEO has no manager (NULL).

Goal. For every employee, list the chain of managers from them up to the CEO, with the depth.

WITH RECURSIVE chain AS (
    -- BASE: every employee starts as themselves at depth 0
    SELECT id, name, manager_id, 0 AS depth, name::text AS path
    FROM   employees

    UNION ALL

    -- RECURSIVE: walk one step up the tree
    SELECT e.id, e.name, m.manager_id, c.depth + 1, c.path || ' > ' || m.name
    FROM   chain c
    JOIN   employees e ON e.id = c.id
    JOIN   employees m ON m.id = c.manager_id
)
SELECT name, depth, path
FROM   chain
WHERE  manager_id IS NULL
ORDER  BY name;

The base case yields one row per employee at depth 0 with manager_id pointing to their direct manager. The recursive case “climbs” by joining each chain row to its manager. Termination: when c.manager_id IS NULL (the CEO), the recursive join can’t find a manager m to add, so the row isn’t extended further.

Output (one row per employee, showing the path to root):

+--------+-------+-------------------------+
| name   | depth | path                    |
+--------+-------+-------------------------+
| CEO    |   0   | CEO                     |
| IC-A1a |   3   | IC-A1a > Mgr-A1 > VP-A > CEO |
| IC-A1b |   3   | IC-A1b > Mgr-A1 > VP-A > CEO |
| IC-B1a |   3   | IC-B1a > Mgr-B1 > VP-B > CEO |
| Mgr-A1 |   2   | Mgr-A1 > VP-A > CEO     |
| Mgr-A2 |   2   | Mgr-A2 > VP-A > CEO     |
| Mgr-B1 |   2   | Mgr-B1 > VP-B > CEO     |
| VP-A   |   1   | VP-A > CEO              |
| VP-B   |   1   | VP-B > CEO              |
+--------+-------+-------------------------+

That’s the entire pattern. Every other recursive CTE you’ll write is a variation.

The other direction — descendants of a node

“All employees under VP-A”:

WITH RECURSIVE descendants AS (
    SELECT id, name, manager_id, 0 AS depth FROM employees WHERE id = 2  -- VP-A
    UNION ALL
    SELECT e.id, e.name, e.manager_id, d.depth + 1
    FROM   descendants d
    JOIN   employees e ON e.manager_id = d.id
)
SELECT * FROM descendants ORDER BY depth, name;

Same shape, different join direction.

Generating sequences — date spines

A common ETL need: a row per day in a range, even when the source data doesn’t have one.

-- Postgres: built-in generate_series is shorter
SELECT day::date FROM generate_series('2026-04-01'::date, '2026-04-30', '1 day') day;

-- Recursive equivalent (works in any dialect that supports WITH RECURSIVE)
WITH RECURSIVE days(day) AS (
    SELECT DATE '2026-04-01'
    UNION ALL
    SELECT day + 1 FROM days WHERE day < DATE '2026-04-30'
)
SELECT * FROM days;

The termination is WHERE day < ... — the recursive case stops adding rows when the date passes the bound.

Graph traversals — friend-of-friend

CREATE TABLE friendships (a int, b int);  -- undirected: store both directions

WITH RECURSIVE reach(node, depth) AS (
    SELECT 1, 0                                      -- start at user 1
    UNION                                            -- UNION (not ALL) for cycle protection
    SELECT f.b, r.depth + 1
    FROM   reach r
    JOIN   friendships f ON f.a = r.node
    WHERE  r.depth < 3                                -- limit to 3 hops
)
SELECT DISTINCT node, MIN(depth) AS shortest_hops
FROM   reach
GROUP  BY node;

Two protections against infinite loops in cyclic graphs:

  1. UNION instead of UNION ALL — dedups rows already in reach, so once a node is reached at depth k, repeated visits at depth ≥ k are dropped.
  2. Depth bound (r.depth < 3) — hard cap regardless of dedup.

Use both. UNION ALL + no bound + cycles = your query never returns.

Recursive search with a “visited” set

For deep graphs where you need explicit cycle tracking, carry a path:

WITH RECURSIVE walk(node, path, has_cycle) AS (
    SELECT 1, ARRAY[1], false
    UNION ALL
    SELECT e.dst, w.path || e.dst, e.dst = ANY(w.path)
    FROM   walk w
    JOIN   edges e ON e.src = w.node
    WHERE  NOT w.has_cycle
)
SELECT * FROM walk;

Postgres has built-in cycle detection via CYCLE clause:

WITH RECURSIVE walk AS (
    SELECT 1 AS node UNION ALL
    SELECT e.dst FROM walk JOIN edges e ON e.src = walk.node
) CYCLE node SET is_cycle USING path
SELECT * FROM walk;

Snowflake/BigQuery handle this differently (or not at all). Postgres-only trick.

Common pitfalls

  • No termination condition → infinite loop. Either dedup with UNION, bound with a depth counter, or both.
  • Referencing the recursive CTE twice in the recursive part. Standard SQL forbids it. Postgres errors out. Restructure to reference once.
  • Using aggregates or window functions in the recursive part. Also forbidden by standard SQL. Compute aggregates after the recursion in the outer SELECT.
  • UNION ALL in cyclic graphs. Without dedup, every cycle is re-explored forever. Use UNION.
  • Performance. Recursive CTEs run iteratively, materializing each step. For deep recursion or wide branching, expect quadratic-ish costs. For graph algorithms over large data, a real graph DB (Neo4j) or a Spark GraphX job may be wiser.
  • BigQuery’s recursion limit. Default depth is 100. If you legitimately need deeper, structure differently or process in batches.

Production patterns for ML

1. Date / hour spines for feature pipelines. A WITH RECURSIVE sequence (or generate_series in Postgres) joined cross-product to your entity table guarantees one row per (entity, time-bucket) even when the source data is sparse:

WITH RECURSIVE hours(h) AS (
    SELECT '2026-04-01 00:00'::timestamptz
    UNION ALL
    SELECT h + INTERVAL '1 hour' FROM hours WHERE h < '2026-04-02 00:00'
)
SELECT u.id, h.h AS hour,
       COALESCE(COUNT(e.*), 0) AS events
FROM   users u
CROSS  JOIN hours h
LEFT   JOIN events e
       ON  e.user_id = u.id
       AND e.ts >= h.h AND e.ts < h.h + INTERVAL '1 hour'
GROUP  BY u.id, h.h;

2. Transitive feature lookups. “All ancestor categories of this product” for a feature:

WITH RECURSIVE category_chain AS (
    SELECT product_id, category_id, 0 AS depth FROM products
    UNION ALL
    SELECT cc.product_id, c.parent_id, cc.depth + 1
    FROM   category_chain cc
    JOIN   categories c ON c.id = cc.category_id
    WHERE  c.parent_id IS NOT NULL
)
SELECT product_id, ARRAY_AGG(category_id ORDER BY depth) AS category_path
FROM   category_chain
GROUP  BY product_id;

The model gets the full category breadcrumb as a feature, computed in pure SQL.

Resources