Recursive CTEs for trees

Concepts covered: Recursive Queries

A chain of self joins reaches as many levels as it has aliases: 2 aliases, 2 levels. A genre catalog nested 9 deep, or an org chart that runs 4 levels in one division and 11 in another, needs a query that keeps joining until there is nothing left to join. A recursive CTE does that. It names a result set, seeds it with starting rows, and keeps adding rows derived from the rows it already holds until a pass adds none.

Anchor, step, stop

The CTE has 2 members joined by UNION ALL. The anchor runs once and returns the starting rows, here the employees with no manager. The recursive member joins the base table to the CTE by name, so it finds employees whose manager is already in the result. The engine runs the recursive member against the rows the previous pass produced, appends whatever comes back, then runs it again against only those new rows, and stops the first time a pass returns 0 rows.

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

The depth column is carried by hand: the anchor sets it to 1 and the recursive member adds 1 to the depth of the row it joined through, so each pass is one level deeper. ORDER BY depth, emp_id lays the tree out top down: Alice at 1, Bob and Carol at 2, Dave, Erin and Frank at 3. The column list after the CTE name fixes the output columns, and both members must return the same number of columns with matching types.

The anchor member of a recursive CTE is WHERE manager_id IS NULL, but a data fix set every manager_id to a real value, so no row has NULL. What does the CTE return?

• Every employee, because the recursive member scans the whole base table on each pass
• An error, because UNION ALL requires both members to return at least 1 row
• The employees with managers, because the recursive member runs once against the base table
• 0 rows, because the recursive member only joins to rows the anchor already placed in the CTE

Starting from the middle

Change the anchor and the same shape answers a different question. Anchoring on emp_id 2 returns Bob and everyone below him, however deep that subtree runs, with Bob himself at depth 0. A headcount per division, a total budget under one cost center, or every subgenre under Drama is this query with a different WHERE in the anchor and an aggregate over the result.

WITH RECURSIVE team (emp_id, name, depth) AS (
  SELECT
    emp_id,
    name,
    0 AS depth
  FROM employees
  WHERE emp_id = 2
  UNION ALL
  SELECT
    e.emp_id,
    e.name,
    t.depth + 1
  FROM employees e
  JOIN team t
    ON e.manager_id = t.emp_id
)
SELECT
  emp_id,
  name,
  depth
FROM team
ORDER BY depth, emp_id

Three rows come back: Bob at depth 0, then Dave and Erin at depth 1. Nobody reports to Dave or Erin, so the pass after them finds no rows and the recursion ends. Wrapping the final SELECT in COUNT(*) turns the listing into a headcount of 3.

When recursion does not stop

The recursive member stops when it adds nothing, and 2 things defeat that. A cycle in the data, where emp_id 7 reports to 8 and 8 reports to 7, hands each pass the same rows forever. A recursive member whose join condition is always true grows without bound. Engines guard against both with a maximum recursion depth, a setting that fails the query instead of running until memory is gone, and many ship with a low default that a deep tree will hit. A depth column with WHERE o.depth < 20 inside the recursive member is a guard you control, and it stops a cycle at a size you chose.

Chained self joins

• Fixed number of levels, 1 alias each
• All levels for a node in one wide row
• Planned as one set of hash joins

Recursive CTE

• Any depth, discovered at run time
• One row per node with its depth
• One join per pass, planned pass by pass

A recursive CTE over a 12 level tree runs 12 passes, each one a join against the base table. The engine does not know the depth before it starts, so it cannot plan the whole traversal at once; with a known depth and a large table, a chain of self joins is often faster.

List Carol and everyone below her in employees, with Carol at depth 0. Order the pieces into the recursive CTE; one piece does not belong.

About this lesson

This section is part of the Joins: Advanced lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.