---
# === IDENTITY ===
id: software/patterns/sql-recursive-cte/2026
canonical_question: "How do I write recursive CTE queries for hierarchies (org charts, MLM, BOM)?"
aliases:
  - "SQL recursive common table expression"
  - "WITH RECURSIVE query for tree traversal"
  - "hierarchical query SQL adjacency list"
  - "bill of materials recursive SQL query"
  - "org chart SQL query parent child"
  - "SQL self-referencing table hierarchy traversal"
entity_type: software_reference
domain: software > patterns > sql_recursive_cte
region: global
jurisdiction: global
temporal_scope: 2015-2026

# === VERIFICATION ===
last_verified: 2026-02-23
confidence: 0.95
version: 1.0
first_published: 2026-02-23

# === TEMPORAL VALIDITY ===
temporal_validity:
  status: stable
  last_breaking_change: "SQL:1999 introduced recursive CTEs; syntax stable since"
  next_review: 2026-08-22
  change_sensitivity: low

# === CONSTRAINTS ===
constraints:
  - "MySQL requires WITH RECURSIVE keyword even for simple recursion; PostgreSQL and SQL Server accept WITH alone but RECURSIVE is recommended for clarity"
  - "SQL Server limits recursion to 100 levels by default (MAXRECURSION); MySQL limits to 1000 (cte_max_recursion_depth)"
  - "Never use UNION (dedup) in recursive CTEs on large hierarchies without understanding the O(n log n) sort cost per iteration"
  - "Recursive member must not contain aggregate functions, GROUP BY, window functions, or subqueries referencing the CTE (MySQL restriction; PostgreSQL is more permissive)"
  - "Always implement cycle detection or depth limits in graphs that may contain cycles to prevent infinite recursion"

# === SKIP CONDITIONS ===
skip_this_unit_if:
  - condition: "Need to traverse a DAG or general graph with multiple parents per node"
    use_instead: "Use closure table pattern or graph database (Neo4j, Apache AGE)"
  - condition: "Hierarchy has millions of nodes and read performance is critical"
    use_instead: "Consider nested set or materialized path models for read-heavy workloads"

# === AGENT HINTS ===
inputs_needed:
  - key: database_engine
    question: "Which database engine are you using?"
    type: choice
    options: ["PostgreSQL", "MySQL 8.0+", "SQL Server", "SQLite", "Oracle"]
  - key: hierarchy_type
    question: "What kind of hierarchy are you modeling?"
    type: choice
    options: ["org chart (single parent)", "bill of materials (multi-level assembly)", "category tree", "MLM/referral chain", "file system / nested comments"]
  - key: read_write_ratio
    question: "Is your workload primarily reads or writes?"
    type: choice
    options: ["read-heavy (>90% reads)", "balanced", "write-heavy (frequent inserts/moves)"]

# === DISTRIBUTION ===
canonical_source: "https://knowledgelib.io/software/patterns/sql-recursive-cte/2026"
suggested_citation: "Source: knowledgelib.io -- AI Knowledge Library (verified 2026-02-23)"

# === RELATED UNITS ===
related_kos:
  depends_on: []
  related_to:
    - id: "software/debugging/postgresql-slow-queries/2026"
      label: "PostgreSQL Slow Query Debugging"
    - id: "software/debugging/mysql-deadlocks/2026"
      label: "MySQL Deadlock Debugging"
  solves: []
  alternative_to: []
  often_confused_with: []

# === SOURCES (7 authoritative sources) ===
sources:
  - id: src1
    title: "PostgreSQL 18: WITH Queries (Common Table Expressions)"
    author: PostgreSQL Global Development Group
    url: https://www.postgresql.org/docs/current/queries-with.html
    type: official_docs
    published: 2025-09-01
    reliability: authoritative
  - id: src2
    title: "MySQL 8.4 Reference Manual: WITH (Common Table Expressions)"
    author: Oracle Corporation
    url: https://dev.mysql.com/doc/refman/8.4/en/with.html
    type: official_docs
    published: 2024-04-01
    reliability: authoritative
  - id: src3
    title: "Recursive Queries Using Common Table Expressions (SQL Server)"
    author: Microsoft
    url: https://learn.microsoft.com/en-us/sql/t-sql/queries/recursive-common-table-expression-transact-sql
    type: official_docs
    published: 2025-09-11
    reliability: authoritative
  - id: src4
    title: "Hierarchical and Recursive Queries in SQL"
    author: Wikipedia contributors
    url: https://en.wikipedia.org/wiki/Hierarchical_and_recursive_queries_in_SQL
    type: community_resource
    published: 2025-01-15
    reliability: moderate_high
  - id: src5
    title: "Nested Set Model"
    author: Wikipedia contributors
    url: https://en.wikipedia.org/wiki/Nested_set_model
    type: community_resource
    published: 2025-01-10
    reliability: moderate_high
  - id: src6
    title: "Work with Recursive CTEs (BigQuery)"
    author: Google Cloud
    url: https://cloud.google.com/bigquery/docs/recursive-ctes
    type: official_docs
    published: 2025-06-01
    reliability: high
  - id: src7
    title: "From Trees to Tables: Storing Hierarchical Data in Relational Databases"
    author: Rishabh Dev Manu
    url: https://medium.com/@rishabhdevmanu/from-trees-to-tables-storing-hierarchical-data-in-relational-databases-a5e5e6e1bd64
    type: technical_blog
    published: 2024-08-15
    reliability: moderate_high
---

# SQL Recursive CTE Queries for Hierarchies

## TL;DR

- **Bottom line**: Use `WITH RECURSIVE` to traverse adjacency-list hierarchies (org charts, BOM, categories) by defining an anchor query for root nodes and a recursive member that joins children to already-found rows, terminating when no new rows are produced.
- **Key tool/command**: `WITH RECURSIVE cte AS (SELECT ... UNION ALL SELECT ... FROM cte JOIN ...) SELECT * FROM cte`
- **Watch out for**: Infinite recursion in cyclic data -- always add a depth counter (`WHERE depth < N`) or cycle detection (`CYCLE` clause in PostgreSQL 14+).
- **Works with**: PostgreSQL 8.4+, MySQL 8.0+, SQL Server 2005+, SQLite 3.8.3+, Oracle 11g R2+, BigQuery.

## Constraints
<!-- Agents: read this section before recommending any action from this unit.
     These are hard constraints that must not be violated. -->

- MySQL requires the `RECURSIVE` keyword in `WITH RECURSIVE`; omitting it causes "Table doesn't exist" errors. PostgreSQL and SQL Server accept `WITH` alone but `RECURSIVE` is best practice for portability. [src2]
- SQL Server defaults to `MAXRECURSION 100` -- queries exceeding 100 levels error out. Override with `OPTION (MAXRECURSION 0)` for unlimited (dangerous) or a specific limit. [src3]
- MySQL defaults `cte_max_recursion_depth` to 1000. Increase per session with `SET SESSION cte_max_recursion_depth = N`. [src2]
- Recursive members in MySQL must not use aggregate functions, `GROUP BY`, window functions, `DISTINCT`, `ORDER BY`, or subqueries referencing the CTE. PostgreSQL is more permissive. [src2]
- In MySQL, the CTE must not appear on the right side of a `LEFT JOIN` in the recursive member. [src2]
- Always test with `LIMIT` or a depth cap before running on production data to avoid runaway queries.

## Quick Reference

| Scenario | Pattern | Time | Space | Trade-off |
|---|---|---|---|---|
| Simple parent-child tree (org chart) | Recursive CTE + adjacency list | O(n) per level, O(n*d) total | O(n) result set | Easy writes, recursive reads |
| Bill of materials with quantity rollup | Recursive CTE + SUM aggregation in outer query | O(n*d) | O(n) | Aggregation outside CTE only (MySQL restriction) |
| Find all ancestors (bottom-up traversal) | Recursive CTE anchored at leaf, join to parent | O(d) per leaf | O(d) | Reverse direction anchor |
| Depth-limited subtree | Recursive CTE + `WHERE depth < N` | O(n) bounded by N | O(n) | Prevents runaway on bad data |
| Full path string (breadcrumb) | Recursive CTE + string concatenation per level | O(n*d) | O(n * avg_path_len) | Path grows with depth; use `||` (PG) or `CONCAT` (MySQL) |
| Cycle-safe graph traversal | Recursive CTE + CYCLE clause (PG 14+) or path array | O(n*d) | O(n * d) for path array | Prevents infinite loops in cyclic data |
| Tree ordering (depth-first) | Recursive CTE + SEARCH DEPTH FIRST (PG 14+) or path array sort | O(n*d + n log n) | O(n * d) | Correct visual tree ordering |
| Tree ordering (breadth-first) | Recursive CTE + depth counter + ORDER BY depth | O(n*d + n log n) | O(n) | Level-by-level processing |
| Read-heavy flat hierarchy (<6 levels) | Materialized path (e.g., `/1/3/7/`) + LIKE queries | O(n) scan or O(log n) with index | O(n * path_len) | Fast reads, costly subtree moves |
| Read-heavy deep hierarchy | Nested set model (lft/rgt columns) | O(1) subtree check, O(n) rebuild | O(n) | Fastest reads, expensive writes |
| Balanced read-write | Closure table (ancestor, descendant, depth) | O(d) insert, O(1) subtree query | O(n * d) rows | Extra table, best query flexibility |
| Very large trees (>1M nodes) | Recursive CTE + pagination via keyset | O(page_size * d) | O(page_size) | Avoids loading entire tree into memory |

## Decision Tree

> Full script: [decision-tree.txt](scripts/decision-tree.txt) (25 lines)

```
START
|-- Which storage model is already in place?
|   |-- ADJACENCY LIST (parent_id column) --> Use recursive CTE (this unit)
|   |-- NESTED SET (lft/rgt columns) --> Use range queries, no recursion needed
|   |-- MATERIALIZED PATH (/1/3/7/) --> Use LIKE or ltree, no recursion needed
# ... (see full script)
```

## Step-by-Step Guide

### 1. Create the adjacency-list table

Design the table with a self-referencing foreign key. The root node(s) have `NULL` in the parent column. [src1]

```sql
CREATE TABLE employees (
    id         INT PRIMARY KEY,
    name       VARCHAR(100) NOT NULL,
    title      VARCHAR(100),
    manager_id INT REFERENCES employees(id),  -- NULL = root
    INDEX idx_manager (manager_id)             -- critical for join performance
);
```

**Verify**: `SELECT * FROM employees WHERE manager_id IS NULL;` --> returns root node(s)

### 2. Write the anchor member

The anchor selects the starting point(s) of your traversal -- typically root nodes or a specific subtree root. [src1]

```sql
-- Anchor: find the CEO (root node)
SELECT id, name, title, manager_id, 0 AS depth
FROM employees
WHERE manager_id IS NULL
```

**Verify**: Returns exactly one row (or the expected number of root nodes)

### 3. Write the recursive member

The recursive member joins the base table to the CTE, finding children of already-discovered nodes. Always increment the depth counter. [src1] [src3]

```sql
-- Recursive: find direct reports of already-found employees
SELECT e.id, e.name, e.title, e.manager_id, cte.depth + 1
FROM employees e
INNER JOIN org_tree cte ON e.manager_id = cte.id
WHERE cte.depth < 20  -- safety limit
```

**Verify**: Each iteration returns one level deeper; eventually returns 0 rows (termination)

### 4. Combine into a complete recursive CTE

```sql
WITH RECURSIVE org_tree AS (
    -- Anchor: root node(s)
    SELECT id, name, title, manager_id, 0 AS depth
    FROM employees
    WHERE manager_id IS NULL

    UNION ALL

    -- Recursive: children of found nodes
    SELECT e.id, e.name, e.title, e.manager_id, ot.depth + 1
    FROM employees e
    INNER JOIN org_tree ot ON e.manager_id = ot.id
    WHERE ot.depth < 20
)
SELECT * FROM org_tree ORDER BY depth, name;
```

**Verify**: `SELECT COUNT(*) FROM org_tree;` --> matches total employee count

### 5. Add path tracking for breadcrumbs

Build a full path string for display or sorting. Syntax varies by engine. [src1]

```sql
-- PostgreSQL: array concatenation
WITH RECURSIVE org_tree AS (
    SELECT id, name, manager_id, 0 AS depth,
           ARRAY[name] AS path
    FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id, ot.depth + 1,
           ot.path || e.name
    FROM employees e
    INNER JOIN org_tree ot ON e.manager_id = ot.id
)
SELECT *, array_to_string(path, ' > ') AS breadcrumb
FROM org_tree ORDER BY path;
```

**Verify**: Breadcrumb column shows `CEO > VP Sales > Regional Manager > Rep`

### 6. Add cycle detection (for graphs with possible cycles)

Use PostgreSQL 14+ CYCLE clause or manual path-based detection. [src1]

```sql
-- PostgreSQL 14+: built-in CYCLE clause
WITH RECURSIVE graph_walk AS (
    SELECT id, parent_id, name, 0 AS depth
    FROM nodes WHERE id = 1
    UNION ALL
    SELECT n.id, n.parent_id, n.name, gw.depth + 1
    FROM nodes n
    INNER JOIN graph_walk gw ON n.parent_id = gw.id
) CYCLE id SET is_cycle USING path
SELECT * FROM graph_walk WHERE NOT is_cycle;
```

**Verify**: `SELECT COUNT(*) FROM graph_walk WHERE is_cycle;` --> shows detected cycles

## Code Examples
<!-- Keep inline examples <= 15 lines. For longer scripts, extract to scripts/ subdirectory -->

### PostgreSQL: Org Chart with Depth-First Ordering

```sql
-- Input:  employees table with (id, name, title, manager_id)
-- Output: full org tree with depth, path, and visual indentation
WITH RECURSIVE org_tree AS (
    SELECT id, name, title, manager_id, 0 AS depth,
           ARRAY[id] AS path, name::text AS breadcrumb
    FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.title, e.manager_id, ot.depth + 1,
           ot.path || e.id, ot.breadcrumb || ' > ' || e.name
    FROM employees e
    INNER JOIN org_tree ot ON e.manager_id = ot.id
    WHERE ot.depth < 50  -- safety cap
)
SELECT id, repeat('  ', depth) || name AS indented_name,
       title, depth, breadcrumb
FROM org_tree ORDER BY path;
```

### MySQL 8.0+: Bill of Materials with Quantity Rollup

```sql
-- Input:  bom table with (assembly_id, component_id, quantity)
-- Output: all components needed for assembly 1 with total quantities
WITH RECURSIVE bom_tree AS (
    SELECT component_id, assembly_id, quantity, 1 AS depth,
           CAST(CONCAT('/', assembly_id, '/', component_id) AS CHAR(1000)) AS path
    FROM bom WHERE assembly_id = 1
    UNION ALL
    SELECT b.component_id, b.assembly_id, b.quantity * bt.quantity, bt.depth + 1,
           CONCAT(bt.path, '/', b.component_id)
    FROM bom b
    INNER JOIN bom_tree bt ON b.assembly_id = bt.component_id
    WHERE bt.depth < 20
)
SELECT component_id, SUM(quantity) AS total_needed, MAX(depth) AS max_depth
FROM bom_tree GROUP BY component_id ORDER BY total_needed DESC;
```

### SQL Server: Recursive CTE with MAXRECURSION

```sql
-- Input:  categories table with (id, name, parent_id)
-- Output: full category tree with level and path
WITH category_tree AS (
    -- Anchor: root categories
    SELECT id, name, parent_id, 0 AS level,
           CAST(name AS NVARCHAR(MAX)) AS full_path
    FROM categories WHERE parent_id IS NULL
    UNION ALL
    -- Recursive: subcategories
    SELECT c.id, c.name, c.parent_id, ct.level + 1,
           CAST(ct.full_path + N' > ' + c.name AS NVARCHAR(MAX))
    FROM categories c
    INNER JOIN category_tree ct ON c.parent_id = ct.id
)
SELECT id, name, level, full_path
FROM category_tree
ORDER BY full_path
OPTION (MAXRECURSION 200);  -- allow up to 200 levels
```

## Anti-Patterns

### Wrong: No depth limit on recursive CTE

```sql
-- BAD -- infinite recursion if data has cycles or is deeper than expected
WITH RECURSIVE tree AS (
    SELECT id, parent_id FROM nodes WHERE id = 1
    UNION ALL
    SELECT n.id, n.parent_id
    FROM nodes n JOIN tree t ON n.parent_id = t.id
)
SELECT * FROM tree;
```

### Correct: Always include a depth safety cap

```sql
-- GOOD -- depth limit prevents runaway recursion
WITH RECURSIVE tree AS (
    SELECT id, parent_id, 0 AS depth FROM nodes WHERE id = 1
    UNION ALL
    SELECT n.id, n.parent_id, t.depth + 1
    FROM nodes n JOIN tree t ON n.parent_id = t.id
    WHERE t.depth < 100  -- explicit safety limit
)
SELECT * FROM tree;
```

### Wrong: Using aggregate inside MySQL recursive member

```sql
-- BAD -- MySQL error: recursive member cannot use aggregate functions
WITH RECURSIVE rollup AS (
    SELECT id, parent_id, cost FROM items WHERE id = 1
    UNION ALL
    SELECT i.id, i.parent_id, SUM(i.cost)  -- ILLEGAL in MySQL
    FROM items i JOIN rollup r ON i.parent_id = r.id
    GROUP BY i.id
)
SELECT * FROM rollup;
```

### Correct: Aggregate in the outer query, not the recursive member

```sql
-- GOOD -- aggregate after recursion completes
WITH RECURSIVE rollup AS (
    SELECT id, parent_id, cost, 0 AS depth FROM items WHERE id = 1
    UNION ALL
    SELECT i.id, i.parent_id, i.cost, r.depth + 1
    FROM items i JOIN rollup r ON i.parent_id = r.id
    WHERE r.depth < 50
)
SELECT parent_id, SUM(cost) AS total_cost
FROM rollup GROUP BY parent_id;
```

### Wrong: Using UNION instead of UNION ALL (unnecessary dedup cost)

```sql
-- BAD -- UNION forces expensive sort+dedup on every iteration
WITH RECURSIVE tree AS (
    SELECT id, parent_id FROM nodes WHERE id = 1
    UNION  -- dedup is almost never needed in a tree (unique PKs)
    SELECT n.id, n.parent_id
    FROM nodes n JOIN tree t ON n.parent_id = t.id
)
SELECT * FROM tree;
```

### Correct: Use UNION ALL for trees (unique keys guarantee no duplicates)

```sql
-- GOOD -- UNION ALL avoids sort; use cycle detection for graphs instead
WITH RECURSIVE tree AS (
    SELECT id, parent_id, 0 AS depth FROM nodes WHERE id = 1
    UNION ALL
    SELECT n.id, n.parent_id, t.depth + 1
    FROM nodes n JOIN tree t ON n.parent_id = t.id
    WHERE t.depth < 100
)
SELECT * FROM tree;
```

### Wrong: Projecting parent column instead of child in recursive member

```sql
-- BAD -- projects t.id (parent) instead of n.id (child) = infinite loop
WITH RECURSIVE tree AS (
    SELECT id FROM nodes WHERE id = 1
    UNION ALL
    SELECT t.id  -- WRONG: should be n.id
    FROM nodes n JOIN tree t ON n.parent_id = t.id
)
SELECT * FROM tree;
```

### Correct: Always project the child row's columns

```sql
-- GOOD -- projects n.id (the newly discovered child node)
WITH RECURSIVE tree AS (
    SELECT id, 0 AS depth FROM nodes WHERE id = 1
    UNION ALL
    SELECT n.id, t.depth + 1  -- n.id = child being discovered
    FROM nodes n JOIN tree t ON n.parent_id = t.id
    WHERE t.depth < 100
)
SELECT * FROM tree;
```

## Common Pitfalls

- **Infinite recursion from cyclic data**: A `parent_id` pointing back to an ancestor creates an endless loop. Fix: Add `WHERE depth < N` safety cap and use PostgreSQL's `CYCLE` clause or manual path-array cycle detection (`id = ANY(path)`). [src1]
- **MySQL "Table doesn't exist" error**: Forgetting the `RECURSIVE` keyword in `WITH RECURSIVE` causes MySQL to not recognize the self-reference. Fix: Always write `WITH RECURSIVE cte_name AS (...)`. [src2]
- **SQL Server MAXRECURSION 100 error**: Default limit terminates at 100 levels. Fix: Add `OPTION (MAXRECURSION N)` where N is your expected max depth, or `0` for unlimited (only with other safety guards). [src3]
- **Column type truncation in MySQL**: MySQL infers CTE column types solely from the anchor member. If the anchor returns `CHAR(10)` and recursion concatenates longer strings, data is silently truncated. Fix: `CAST(column AS CHAR(1000))` in the anchor member. [src2]
- **Wrong join direction**: Joining `CTE.id = table.id` instead of `CTE.id = table.parent_id` (or vice versa) traverses the wrong direction -- up instead of down or vice versa. Fix: Double-check which column is the FK (child) and which is the PK (parent). [src3]
- **Missing index on parent_id**: Without an index on `parent_id`, each recursive iteration performs a full table scan. Fix: `CREATE INDEX idx_parent ON table(parent_id);` -- this is the single most impactful optimization. [src1]
- **Multiplied rows in BOM queries**: When a component appears in multiple assemblies, recursive CTE correctly duplicates it. But aggregation inside the CTE (MySQL-illegal anyway) or misunderstanding the output leads to wrong totals. Fix: Aggregate in the outer query with `GROUP BY component_id`. [src3]
- **UNION vs UNION ALL performance**: Using `UNION` (with implicit `DISTINCT`) forces a sort/dedup on every recursive iteration. In a proper tree with unique PKs, this is pure overhead. Fix: Use `UNION ALL` for trees; reserve `UNION` only for graphs where dedup replaces cycle detection. [src1]

## Version History & Compatibility

| Engine | Version | Recursive CTE Support | Key Limitation |
|---|---|---|---|
| PostgreSQL | 8.4+ (2009) | Full -- SEARCH/CYCLE clauses added in 14 (2021) | None significant |
| MySQL | 8.0+ (2018) | Full | No aggregates/window functions in recursive member; `cte_max_recursion_depth = 1000` |
| SQL Server | 2005+ | Full | `MAXRECURSION` default 100; no SEARCH/CYCLE clause |
| SQLite | 3.8.3+ (2014) | Full | No built-in cycle detection |
| Oracle | 11g R2+ (2009) | Full (via `WITH` or `CONNECT BY`) | `CONNECT BY` is legacy; prefer standard recursive CTE |
| BigQuery | 2023+ | Full | Requires UNION ALL; no UNION DISTINCT |
| Databricks SQL | 2024+ | Full | Recently added; check version |

## When to Use / When Not to Use

| Use When | Don't Use When | Use Instead |
|---|---|---|
| Adjacency list is already the data model | Hierarchy has >1M nodes and you only need subtree reads | Nested set or materialized path |
| Writes are frequent (inserts, moves, deletes) | You need O(1) "is A ancestor of B?" checks | Nested set model (lft/rgt range check) |
| Hierarchy depth is unknown or variable | Database doesn't support recursive CTEs (MySQL <8.0, old MariaDB) | Application-level recursion or stored procedures |
| Need to compute aggregates over subtrees (BOM cost rollup) | Simple 2-3 level hierarchy with fixed depth | Multiple self-joins (simpler, faster) |
| Data may contain cycles that need detection | Read latency is critical and hierarchy rarely changes | Closure table (pre-computed ancestor-descendant pairs) |
| Building breadcrumb paths or full-path strings | Only need direct children (one level deep) | Simple WHERE parent_id = ? query |

## Important Caveats

- PostgreSQL's `SEARCH` and `CYCLE` clauses (v14+) are syntactic sugar that the planner expands to manual path/array tracking. They are not faster than manual implementations, but are less error-prone and more readable.
- MySQL determines CTE column types solely from the non-recursive (anchor) member. Recursive string concatenation can silently truncate unless you CAST to a sufficiently large type in the anchor.
- SQL Server's `OPTION (MAXRECURSION 0)` removes all recursion limits. Combine with a `WHERE depth < N` clause as a secondary safety net to avoid crashing the server on corrupt data.
- Recursive CTEs are evaluated iteratively (not truly "recursively" in a call-stack sense). Performance scales linearly with tree size but can degrade on very wide trees (millions of children per node) due to the join at each level.
- No major SQL engine parallelizes the recursive member across iterations. Each iteration depends on the previous one's output, making this inherently sequential per level.

## Related Units
<!-- Generated from related_kos frontmatter -->

- [PostgreSQL Slow Query Debugging](/software/debugging/postgresql-slow-queries/2026)
- [MySQL Deadlock Debugging](/software/debugging/mysql-deadlocks/2026)