recursive CTEs

A recursive CTE is a CTE that refers to itself. It's how sql walks through trees and chains when you don't know how deep they go, org charts, category trees, folder structures, "who referred who".

It looks scary but there are only two parts.

the shape

WITH RECURSIVE name AS (
  -- 1. anchor: where to start
  SELECT ...

  UNION ALL

  -- 2. recursive part: how to get the next level from the previous one
  SELECT ...
  FROM some_table
  JOIN name ON ...   -- refers to itself
)
SELECT * FROM name;

How it runs:

1. run the anchor, that's level 1
2. run the recursive part using only the rows from the last step, that's level 2
3. repeat with the new rows
4. stop when a step returns nothing

warm up: counting to 5

WITH RECURSIVE nums AS (
  SELECT 1 AS n
  UNION ALL
  SELECT n + 1 FROM nums WHERE n < 5
)
SELECT * FROM nums;

Starts with 1, keeps adding 1, the WHERE stops it at 5. Without that WHERE it'd run forever (well, until postgres runs out of memory).

the org chart

Start at the boss, then keep finding people whose manager is someone we already found.

WITH RECURSIVE org AS (
  SELECT employee_id, name, manager_id, 1 AS level
  FROM employees
  WHERE manager_id IS NULL                 -- Vikram

  UNION ALL

  SELECT e.employee_id, e.name, e.manager_id, o.level + 1
  FROM employees e
  JOIN org o ON e.manager_id = o.employee_id
)
SELECT * FROM org ORDER BY level, name;

name	level
Vikram	1
Anita	2
Sameer	2
Dev	3
Meera	3
Pooja	3
Rohit	3
Isha	4

Works whether the tree is 4 levels or 40.

showing the path

Build up a string as you go:

WITH RECURSIVE org AS (
  SELECT employee_id, name, name::text AS path
  FROM employees WHERE manager_id IS NULL
  UNION ALL
  SELECT e.employee_id, e.name, o.path || ' > ' || e.name
  FROM employees e
  JOIN org o ON e.manager_id = o.employee_id
)
SELECT path FROM org ORDER BY path;

Vikram > Anita > Rohit > Isha. The ::text cast in the anchor matters, the column type is decided by the anchor, and VARCHAR(50) would overflow on long paths.

going up instead of down

All of Isha's bosses, start at Isha and follow manager_id upward:

WITH RECURSIVE chain AS (
  SELECT employee_id, name, manager_id FROM employees WHERE name = 'Isha'
  UNION ALL
  SELECT e.employee_id, e.name, e.manager_id
  FROM employees e
  JOIN chain c ON e.employee_id = c.manager_id
)
SELECT name FROM chain;

generating dates

Super practical, filling gaps in reports. Every month from jan to jul, even ones with no orders:

WITH RECURSIVE months AS (
  SELECT DATE '2024-01-01' AS month
  UNION ALL
  SELECT (month + INTERVAL '1 month')::date FROM months WHERE month < '2024-07-01'
)
SELECT m.month, COALESCE(SUM(o.amount), 0) AS revenue
FROM months m
LEFT JOIN orders o ON DATE_TRUNC('month', o.order_date) = m.month
GROUP BY m.month
ORDER BY m.month;

January shows 0 instead of just missing. (postgres also has generate_series for this, which is easier, but the recursive way works in other databases too.)

infinite loops

If your data has a cycle (A manages B, B manages A), the recursion never ends. Protect yourself:

• add a depth limit, WHERE o.level < 20
• or track visited ids in an array and stop if you've seen one: WHERE NOT e.employee_id = ANY(o.visited)
• postgres 14+ has a CYCLE clause that does this for you

stuff that trips people up

• forgetting the word RECURSIVE (needed in postgres and mysql).
• no stopping condition.
• type mismatch between anchor and recursive part, especially for strings that grow.
• using UNION instead of UNION ALL, works but slower, and it changes the cycle behaviour.

practice

Check queries.sql.

-- recursive CTEs
-- run sample-data.sql first

-- examples ---------------------------------------------------------

WITH RECURSIVE nums AS (
  SELECT 1 AS n
  UNION ALL
  SELECT n + 1 FROM nums WHERE n < 5
)
SELECT * FROM nums;

WITH RECURSIVE org AS (
  SELECT employee_id, name, manager_id, 1 AS level
  FROM employees WHERE manager_id IS NULL
  UNION ALL
  SELECT e.employee_id, e.name, e.manager_id, o.level + 1
  FROM employees e
  JOIN org o ON e.manager_id = o.employee_id
)
SELECT * FROM org ORDER BY level, name;

WITH RECURSIVE org AS (
  SELECT employee_id, name, name::text AS path
  FROM employees WHERE manager_id IS NULL
  UNION ALL
  SELECT e.employee_id, e.name, o.path || ' > ' || e.name
  FROM employees e
  JOIN org o ON e.manager_id = o.employee_id
)
SELECT path FROM org ORDER BY path;


-- practice ---------------------------------------------------------

-- 1. generate the numbers 1 to 10 and their squares
-- 2. everyone under Anita (directly or indirectly), not including Anita
-- 3. the full chain of bosses above Isha, with how many levels up each one is
-- 4. for each manager, the total salary of everyone under them (all levels)
-- 5. every day from 2024-03-01 to 2024-03-31, with the number of orders placed that day


-- answers ----------------------------------------------------------

-- 1
WITH RECURSIVE n AS (
  SELECT 1 AS x
  UNION ALL
  SELECT x + 1 FROM n WHERE x < 10
)
SELECT x, x * x AS square FROM n;

-- 2
WITH RECURSIVE team AS (
  SELECT employee_id, name FROM employees WHERE manager_id = (SELECT employee_id FROM employees WHERE name = 'Anita')
  UNION ALL
  SELECT e.employee_id, e.name
  FROM employees e JOIN team t ON e.manager_id = t.employee_id
)
SELECT name FROM team;
-- Rohit, Meera, Isha

-- 3
WITH RECURSIVE chain AS (
  SELECT employee_id, name, manager_id, 0 AS levels_up FROM employees WHERE name = 'Isha'
  UNION ALL
  SELECT e.employee_id, e.name, e.manager_id, c.levels_up + 1
  FROM employees e JOIN chain c ON e.employee_id = c.manager_id
)
SELECT name, levels_up FROM chain WHERE levels_up > 0;

-- 4
WITH RECURSIVE reports AS (
  -- every (manager, employee under them) pair
  SELECT manager_id AS boss_id, employee_id, salary
  FROM employees WHERE manager_id IS NOT NULL
  UNION ALL
  SELECT e.manager_id, r.employee_id, r.salary
  FROM reports r
  JOIN employees e ON r.boss_id = e.employee_id
  WHERE e.manager_id IS NOT NULL
)
SELECT b.name AS manager, SUM(r.salary) AS team_salary
FROM reports r JOIN employees b ON r.boss_id = b.employee_id
GROUP BY b.name
ORDER BY team_salary DESC;

-- 5
WITH RECURSIVE days AS (
  SELECT DATE '2024-03-01' AS d
  UNION ALL
  SELECT d + 1 FROM days WHERE d < '2024-03-31'
)
SELECT days.d, COUNT(o.order_id) AS orders
FROM days
LEFT JOIN orders o ON o.order_date = days.d
GROUP BY days.d
ORDER BY days.d;