Recursive CTEs: walking trees and filling in dates

A recursive CTE refers to itself. An anchor query gives the starting rows. Then a recursive part, joined with UNION ALL, keeps adding rows from the previous round until no new rows appear.

Why it matters

An org chart can be any number of levels deep, so a fixed number of self joins can't walk it. The same goes for folder trees, category trees and "every day in this range, including days with no orders". Recursion handles any depth.

The idea

The anchor runs once: for the org chart, "the person with no manager" (Asha, level 0). Then the recursive part runs on the rows found in the previous round: "employees whose manager is in the previous round". That finds Ben, Chen, Dara and Fatima (level 1), then their reports Eli, Gus and Hana (level 2), and so on.

When a round finds nothing, it stops. Always give it a way to stop — a WHERE that eventually fails — or it runs forever.

Passing a message down a phone tree. The boss calls her direct reports, each of them calls theirs, and the calling stops when someone has nobody left to call.

A phone tree stops on its own. Data can loop — if A manages B and B manages A — and a recursive CTE would go round forever. Put a limit on the depth when the data might not be a clean tree.

Syntax

WITH RECURSIVE tree AS (
  SELECT ... FROM t WHERE <start>            -- anchor
  UNION ALL
  SELECT ... FROM t JOIN tree ON <next step>  -- recursive part
)
SELECT * FROM tree;

How it works

  1. Anchor: WHERE manager_id IS NULL finds Asha, level 0.
  2. Round 1: employees whose manager_id is Asha's id get level 0 + 1 = 1.
  3. Round 2: employees managed by anyone found in round 1 get level 2: Eli and Gus (Dara), Hana (Ben).
  4. Round 3 finds nobody managed by Eli, Gus or Hana, so the recursion stops.
  5. For a date range, the anchor is the first day and each round adds one day until the last day.

Key points

Common mistakes

Not true: The anchor part of a recursive CTE runs again in every round.
In fact: The anchor runs once, to give the starting rows. Only the recursive part repeats, each time using the rows found in the round before.

In the interview

A recursive CTE has two parts, joined with UNION ALL. The anchor member produces the starting rows. The recursive member joins back to the CTE to produce the next level, and repeats until no new rows appear. I use it for hierarchies of unknown depth, like an org chart with a level column, and for generating date series to fill gaps. I always give it a clear termination condition, and a depth limit if the data might contain cycles.

Part of Unit 4: Subqueries, CTEs and set operations in the free SQL course.