Recursive CTEs — Traversing Hierarchies

---

title: “Hierarchies and Recursive CTEs” part: 3 topic_number: 1 slug: “hierarchies-recursive-cte” difficulty: “Advanced” prerequisites: “self-joins, correlated-subqueries” —

Recursive CTEs — Traversing Hierarchies

What Is It?

A CTE (Common Table Expression) is a temporary named result set. A Recursive CTE calls itself repeatedly to traverse hierarchical data like org charts, category trees, or bill-of-materials structures.

Real-world analogy: Like a family tree — you start with one person, find their children, then their children’s children, and so on, until you’ve mapped the entire lineage.

When you’d use it:

• Organizational hierarchies (employees and managers)
• Category/subcategory trees
• File system directories
• Bill of materials (parts containing subparts)
• Graph traversal

---

Syntax Breakdown

WITH RECURSIVE cte_name AS (
    -- Anchor: starting point (base case)
    SELECT ...
    FROM table
    WHERE condition
    
    UNION ALL
    
    -- Recursive: calls itself (recursive case)
    SELECT ...
    FROM table
    JOIN cte_name ON relationship
)
SELECT * FROM cte_name;

Key components:

• WITH RECURSIVE keyword
• Anchor member: initial rows (non-recursive SELECT)
• UNION ALL: combines anchor with recursive results
• Recursive member: SELECT that references the CTE itself
• Termination: recursion stops when recursive member returns no rows

---

How Recursion Actually Works — Step by Step

Before reading the SQL, here’s exactly what MySQL does internally:

Org chart (simplified):
  Alice (id=1, manager=NULL)   ← top of the tree
    └── Bob (id=2, manager=1)
          └── Carol (id=3, manager=2)

WITH RECURSIVE employee_hierarchy AS (
    -- ANCHOR: seed the result with the starting row(s)
    SELECT id, name, manager_id, 1 AS level FROM employees WHERE id = 1

    UNION ALL

    -- RECURSIVE: find direct reports of whatever's in the CTE so far
    SELECT e.id, e.name, e.manager_id, eh.level + 1
    FROM employees e
    JOIN employee_hierarchy eh ON e.manager_id = eh.id
)

Iteration 1 — Anchor runs once:

Result so far: [ Alice, level=1 ]

Iteration 2 — Recursive member runs against iteration 1’s output:

Find employees whose manager_id is in [Alice's id=1]
→ finds Bob
Result so far: [ Alice(1), Bob(2) ]

Iteration 3 — Recursive member runs against iteration 2’s NEW rows:

Find employees whose manager_id is in [Bob's id=2]
→ finds Carol
Result so far: [ Alice(1), Bob(2), Carol(3) ]

Iteration 4 — Recursive member runs against iteration 3’s NEW rows:

Find employees whose manager_id is in [Carol's id=3]
→ finds nobody
→ returns 0 rows → STOPS

Final result: Alice + Bob + Carol, with levels 1, 2, 3.

The key insight: each iteration only looks at rows added in the previous iteration, not the whole accumulated result. That’s why it doesn’t loop forever.

---

---

Basic Example: Manager Hierarchy

Setup: Ensure manager_id column exists

-- Already added earlier, but if not:
-- ALTER TABLE employees ADD COLUMN manager_id INT NULL;
-- UPDATE employees SET manager_id = ... (set relationships)

Find All Reports Under a Manager

WITH RECURSIVE employee_hierarchy AS (
    -- Anchor: start with Alice (employee_id = 1)
    SELECT 
        employee_id,
        first_name,
        last_name,
        manager_id,
        1 AS level
    FROM employees
    WHERE employee_id = 1  -- Starting point
    
    UNION ALL
    
    -- Recursive: find direct reports
    SELECT 
        e.employee_id,
        e.first_name,
        e.last_name,
        e.manager_id,
        eh.level + 1
    FROM employees e
    JOIN employee_hierarchy eh ON e.manager_id = eh.employee_id
)
SELECT 
    employee_id,
    CONCAT(REPEAT('  ', level - 1), first_name, ' ', last_name) AS employee,
    level
FROM employee_hierarchy
ORDER BY level, last_name;

Expected output:

employee_id	employee	level
1	Alice Johnson	1
3	Carol Williams	2
5	Eve Davis	2
7	George Jones	2

Alice and all her direct/indirect reports, indented by level.

How it works:

1. Anchor: Selects Alice (level 1)
2. Recursive: Finds employees where manager_id = employee_id from previous iteration
3. Stops: When no more employees have those IDs as managers

---

Going Deeper

Full Organization Chart

WITH RECURSIVE org_chart AS (
    -- Anchor: top-level managers (no boss)
    SELECT 
        employee_id,
        first_name,
        last_name,
        manager_id,
        1 AS level,
        CAST(first_name AS CHAR(200)) AS path
    FROM employees
    WHERE manager_id IS NULL
    
    UNION ALL
    
    -- Recursive: find reports at each level
    SELECT 
        e.employee_id,
        e.first_name,
        e.last_name,
        e.manager_id,
        oc.level + 1,
        CONCAT(oc.path, ' -> ', e.first_name)
    FROM employees e
    JOIN org_chart oc ON e.manager_id = oc.employee_id
)
SELECT 
    employee_id,
    CONCAT(REPEAT('  ', level - 1), first_name, ' ', last_name) AS employee,
    level,
    path
FROM org_chart
ORDER BY path;

Expected output:

employee_id	employee	level	path
1	Alice Johnson	1	Alice
3	Carol Williams	2	Alice -> Carol
5	Eve Davis	2	Alice -> Eve
7	George Jones	2	Alice -> George
2	Bob Smith	1	Bob
4	David Brown	2	Bob -> David
6	Frank Miller	2	Bob -> Frank

Complete hierarchy with reporting paths.

Count Subordinates

WITH RECURSIVE subordinates AS (
    SELECT 
        employee_id,
        first_name,
        last_name,
        manager_id
    FROM employees
    WHERE manager_id IS NULL
    
    UNION ALL
    
    SELECT 
        e.employee_id,
        e.first_name,
        e.last_name,
        e.manager_id
    FROM employees e
    JOIN subordinates s ON e.manager_id = s.employee_id
)
SELECT 
    e.first_name,
    e.last_name,
    COUNT(s.employee_id) - 1 AS total_subordinates  -- -1 to exclude self
FROM employees e
LEFT JOIN subordinates s ON e.employee_id = s.manager_id 
    OR s.manager_id IN (
        SELECT employee_id FROM subordinates WHERE manager_id = e.employee_id
    )
WHERE e.manager_id IS NULL
GROUP BY e.employee_id, e.first_name, e.last_name;

Expected output:

first_name	last_name	total_subordinates
Alice	Johnson	3
Bob	Smith	2

Managers with count of all reports (direct + indirect).

Find Distance Between Employees

WITH RECURSIVE path_to_top AS (
    SELECT 
        employee_id,
        manager_id,
        1 AS distance,
        CAST(employee_id AS CHAR(200)) AS path
    FROM employees
    WHERE employee_id = 7  -- George Jones
    
    UNION ALL
    
    SELECT 
        e.employee_id,
        e.manager_id,
        p.distance + 1,
        CONCAT(p.path, ' -> ', e.employee_id)
    FROM employees e
    JOIN path_to_top p ON e.employee_id = p.manager_id
)
SELECT * FROM path_to_top;

Expected output:

employee_id	manager_id	distance	path
7	1	1	7
1	NULL	2	7 -> 1

Shows George is 1 level below Alice (distance 2 to reach top).

Pause and Predict: What prevents infinite recursion in MySQL?

Answer

**`cte_max_recursion_depth` system variable** (default: 1000) MySQL stops after 1000 iterations to prevent infinite loops. You can adjust it: ```sql SET SESSION cte_max_recursion_depth = 5000; ``` Or use query hint: ```sql WITH RECURSIVE cte AS (...) SELECT /*+ SET_VAR(cte_max_recursion_depth=5000) */ * FROM cte; ``` Always ensure your data has proper termination conditions!

---

Watch Out — Common Mistakes

Mistake #1: Forgetting UNION ALL

--  WRONG (UNION removes duplicates, breaks recursion)
WITH RECURSIVE cte AS (
    SELECT ... FROM ...
    UNION  -- Missing ALL
    SELECT ... FROM cte ...
)

Why UNION ALL is required (not just recommended): UNION removes duplicates by comparing every new row against all previous rows. In a recursive CTE, MySQL uses the new rows only to drive the next iteration. With UNION, MySQL can’t identify which rows are “new” vs “existing” — so it either stops early or errors. Always use UNION ALL.

-- • CORRECT
WITH RECURSIVE cte AS (
    SELECT ... FROM ...
    UNION ALL
    SELECT ... FROM cte ...
)

Mistake #2: No Termination Condition

--  INFINITE LOOP (no stopping condition)
WITH RECURSIVE bad_cte AS (
    SELECT 1 AS n
    UNION ALL
    SELECT n + 1 FROM bad_cte  -- Never stops!
)
SELECT * FROM bad_cte;

Fix: Add WHERE clause to stop:

-- • CORRECT
WITH RECURSIVE numbers AS (
    SELECT 1 AS n
    UNION ALL
    SELECT n + 1 FROM numbers WHERE n < 10
)
SELECT * FROM numbers;

Mistake #3: Circular References in Data

-- If employee 5's manager is 10, and employee 10's manager is 5 → circular!
-- Recursive CTE will hit max depth or loop indefinitely

Prevention: Validate data integrity, add level limits:

WITH RECURSIVE org AS (
    SELECT employee_id, manager_id, 1 AS level FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.employee_id, e.manager_id, o.level + 1
    FROM employees e
    JOIN org o ON e.manager_id = o.employee_id
    WHERE o.level < 10  -- Safety limit
)
SELECT * FROM org;

---

Edge Case Spotlight

Multiple Root Nodes

-- When multiple employees have no manager
WITH RECURSIVE org AS (
    SELECT employee_id, first_name, manager_id, 1 AS level,
           employee_id AS root_id  -- Track which tree
    FROM employees WHERE manager_id IS NULL
    
    UNION ALL
    
    SELECT e.employee_id, e.first_name, e.manager_id, o.level + 1, o.root_id
    FROM employees e
    JOIN org o ON e.manager_id = o.employee_id
)
SELECT root_id, COUNT(*) AS team_size
FROM org
GROUP BY root_id;

Shows size of each separate hierarchy.

---

Try This

Exercise 1 (Guided)

Create a CTE that generates numbers 1 to 20. Show only even numbers.

Hint

Anchor: SELECT 1, Recursive: SELECT n+1 WHERE n < 20, Filter: WHERE MOD(n, 2) = 0

Exercise 2 (Independent)

Find the “depth” of the organization (maximum number of levels). Show the deepest employee’s name and their level.

Hint

Recursive CTE with level tracking, then SELECT MAX(level) or ORDER BY level DESC LIMIT 1.

Exercise 3 (Challenge)

Create a “management span” report: for each manager, show their name, level in org, direct report count, and total subordinate count (all levels below them). Only include actual managers.

Hint

Two CTEs: one recursive for hierarchy, one to count direct vs. all subordinates. Join them together.

---

Answer Key

Exercise 1 Answer

```sql WITH RECURSIVE numbers AS ( SELECT 1 AS n UNION ALL SELECT n + 1 FROM numbers WHERE n < 20 ) SELECT n FROM numbers WHERE n % 2 = 0; ``` **Expected output:** | n | |---| | 2 | | 4 | | 6 | | 8 | | 10 | | 12 | | 14 | | 16 | | 18 | | 20 | Even numbers from 1-20.

Exercise 2 Answer

```sql WITH RECURSIVE org_depth AS ( SELECT employee_id, first_name, last_name, manager_id, 1 AS level FROM employees WHERE manager_id IS NULL UNION ALL SELECT e.employee_id, e.first_name, e.last_name, e.manager_id, od.level + 1 FROM employees e JOIN org_depth od ON e.manager_id = od.employee_id ) SELECT first_name, last_name, level FROM org_depth ORDER BY level DESC LIMIT 1; ``` **Expected output:** | first_name | last_name | level | |------------|-----------|-------| | George | Jones | 2 | Deepest employee in the hierarchy.

Exercise 3 Answer

```sql WITH RECURSIVE all_subordinates AS ( -- Get all employee relationships recursively SELECT employee_id, manager_id, employee_id AS original_employee, 0 AS distance FROM employees UNION ALL SELECT e.employee_id, e.manager_id, sub.original_employee, sub.distance + 1 FROM employees e JOIN all_subordinates sub ON e.manager_id = sub.employee_id ), org_levels AS ( -- Calculate manager levels SELECT employee_id, first_name, last_name, manager_id, 1 AS level FROM employees WHERE manager_id IS NULL UNION ALL SELECT e.employee_id, e.first_name, e.last_name, e.manager_id, ol.level + 1 FROM employees e JOIN org_levels ol ON e.manager_id = ol.employee_id ) SELECT ol.first_name, ol.last_name, ol.level, COUNT(DISTINCT CASE WHEN sub.distance = 1 THEN sub.employee_id END) AS direct_reports, COUNT(DISTINCT CASE WHEN sub.distance >= 1 THEN sub.employee_id END) AS total_subordinates FROM org_levels ol LEFT JOIN all_subordinates sub ON ol.employee_id = sub.original_employee GROUP BY ol.employee_id, ol.first_name, ol.last_name, ol.level HAVING direct_reports > 0 ORDER BY ol.level, total_subordinates DESC; ``` **Expected output:** | first_name | last_name | level | direct_reports | total_subordinates | |------------|-----------|-------|----------------|--------------------| | Alice | Johnson | 1 | 3 | 3 | | Bob | Smith | 1 | 2 | 2 | Comprehensive management span analysis.

---

Quick Recap

• Recursive CTEs traverse hierarchical data
• Anchor defines starting point
• Recursive member calls the CTE itself
• Always use UNION ALL (not UNION)
• Recursion stops when no rows returned
• cte_max_recursion_depth prevents infinite loops
• Track level or path to understand depth
• Validate data to prevent circular references

---

Up Next

Next topic: Date and Time Functions → part3_02_date_functions.md

Type ‘next’ when ready to continue!