SQL Recursive CTEs: Hierarchies, Trees, Graph Traversal, Bill-of-Materials

sql recursive cte is the one piece of SQL that turns "impossible without a loop" into "one query with a WITH RECURSIVE." Org-chart traversal, category-tree explosion, friendship-graph BFS, multi-level bill-of-materials rollup — every one of these used to be a Python script pulling rows in batches until a manager column was NULL. Since 2018 or so, every serious dialect has shipped a standards-compliant recursive CTE. The engineering trade-off is no longer "can I do this in SQL?" but "which anchor, which recursive term, and where does the termination live?"

This guide is the mid-to-senior data-engineer walkthrough you wished existed the first time an interviewer asked you to write a recursive query sql on the whiteboard, sketch a sql hierarchy query for an org chart, roll up a bill of materials sql, or run a graph traversal sql with cycle detection. It walks through the recursive CTE anatomy (anchor + recursive term + UNION ALL + termination + dialect keyword differences), single-parent hierarchies (employee-manager tree, depth level column, path array, ORDER BY sibling column, category tree), multi-parent graph traversal (undirected friendship graph BFS, visited-path arrays, cycle detection with NOT ... = ANY(path), Postgres SEARCH BREADTH FIRST / SEARCH DEPTH FIRST and CYCLE clauses), bill-of-materials rollup with quantity multiplication, and the 5-dialect max-recursion matrix (Postgres / MySQL 8 / SQL Server / Snowflake / BigQuery). Each section pairs a teaching block with a Solution-Tail interview answer — code, a step-by-step trace, an output table, then a concept-by-concept breakdown of why it works.

When you want hands-on reps immediately after reading, drill the CTE practice library →, rehearse on hard-difficulty CTE problems →, and sharpen the SQL axis with the SQL CTE drills →.

---

On this page

• Why recursive CTEs matter in 2026
• Recursive CTE anatomy
• Hierarchies and trees — org chart / category tree
• Graph traversal and cycle detection
• Bill-of-materials and dialect quirks
• Cheat sheet — recursive CTE recipes
• Frequently asked questions
• Practice on PipeCode

---

1. Why recursive CTEs matter in 2026

Recursive CTEs replace app-side loops for hierarchies, trees, graphs, and BOMs — one query, no round-trips

The one-sentence invariant: a sql recursive cte walks a self-referential structure inside the database by repeatedly joining a "frontier" to the parent table, so the shape of the answer is not "loop in Python, one query per level" but "one query, one plan, one pass through the buffer pool". Every other consequence — depth column, path array, cycle detection, BOM rollup — is a specific application of the same anchor-plus-recursive-term shape. Once you internalise the shape, recursive query sql becomes a template you fill in rather than an algorithm you invent.

Three axes interviewers actually probe.

• Structure. A sql hierarchy query walks a single-parent tree (manager_id points to at most one manager). A graph traversal sql walks a multi-parent DAG or cyclic graph (a friendship edge table where any node can point to many). A recursive CTE handles both; the second requires cycle detection and the first does not.
• Termination. The recursive term must produce zero rows eventually, or the plan runs until the dialect's max-recursion setting fires. For a tree, termination is automatic (leaves have no children). For a graph, termination is engineered — a visited-path array plus a NOT visited predicate.
• Rollup. BOM rollup multiplies quantities along every edge: child_accumulated = parent_accumulated × this_edge_qty. The recursive term does the arithmetic; the outer aggregate sums per component. Interviewers love to see the multiplication happen inside the CTE, not after.

Hierarchies vs graphs — the structural split.

• Single-parent tree. Employee-manager, filesystem, category tree, comment thread. Each row points to at most one parent. Cycle detection is not required because a tree by definition cannot have cycles.
• Multi-parent DAG. BOM (a wheel appears in a bike and a scooter), permission chain (a role inherits from multiple parent roles), lineage graph (a dataset has multiple upstream sources). Cycles are impossible by construction but paths can revisit the same node — dedup at the outer query.
• Cyclic graph. Social network, biological pathway, dependency graph with feedback. Cycles are possible; cycle detection is mandatory to prevent infinite recursion.

Dialect status matrix — 2026 reality.

• Postgres — first-class since 8.4 (2009). WITH RECURSIVE, SEARCH BREADTH FIRST / DEPTH FIRST, CYCLE clause. Deepest feature set of any mainstream engine.
• MySQL 8+ — recursive CTE since 8.0 (2018). WITH RECURSIVE required. cte_max_recursion_depth default 1000. No SEARCH or CYCLE clauses — roll your own.
• SQL Server — recursive CTE since 2005. WITH (recursion inferred from the self-reference). Default MAXRECURSION 100, override per-query with OPTION (MAXRECURSION N).
• Snowflake — supported. WITH RECURSIVE. Effectively unbounded depth; watch cost.
• BigQuery — supported since 2022. WITH RECURSIVE. Default 500 iterations, no per-query override — pre-flatten deeper structures or move to a graph DB.
• DuckDB — first-class since 0.7. WITH RECURSIVE and effective for local analytics.

Where a recursive CTE replaces app-side code.

• Python loop that hits the DB N times. Any code that walks a parent chain by issuing "SELECT * FROM t WHERE id = ?" in a while loop is a recursive CTE waiting to happen. One query, one round trip.
• ORM select_related chains. Django / SQLAlchemy select_related cannot follow a self-referential foreign key of unknown depth. Recursive CTE fixes it.
• Materialised transitive closure. A "closure table" (one row per ancestor-descendant pair) can be regenerated from a recursive CTE nightly, without maintaining triggers or app-side denormalisation.
• Graph DB for shallow depth. Neo4j / TigerGraph shine at depth > 5 with millions of nodes. For depth ≤ 4 or nodes ≤ 100K, a recursive CTE against Postgres is usually cheaper and simpler.

What interviewers listen for.

• Do you say "anchor + recursive term + UNION ALL + termination" in the first sentence? — senior signal.
• Do you distinguish "single-parent tree (no cycle guard needed)" vs "multi-parent or cyclic graph (cycle guard mandatory)"? — required answer.
• Do you mention max-recursion overrides per dialect (MySQL cte_max_recursion_depth, SQL Server MAXRECURSION) unprompted? — senior signal.
• Do you push back on "just use a graph database" with "recursive CTE is the right answer for shallow depth and small node count"? — senior signal.

Worked example — a single query that would take a Python loop

Detailed explanation.

• The problem shape. Given an employees table with (id, name, manager_id), list every employee under CEO Alice with their depth from the top. The naive shape is a Python loop: fetch direct reports of Alice, then their direct reports, then their direct reports, joining a level column each time. A recursive CTE does the same walk in one query.
• Why one query wins. Each Python-loop iteration pays a full network round-trip. The recursive CTE runs entirely inside the executor with a single plan, materialising the intermediate frontier in a worktable. Latency drops from O(depth × round-trip) to O(single query).
• What the recursive CTE looks like. Anchor selects Alice (WHERE manager_id IS NULL). Recursive term joins employees to the CTE by matching employees.manager_id = cte.id, adding a level + 1. Terminates when a level has no direct reports.

Question. Rewrite the Python "walk the org chart" loop as a single recursive CTE. Return employee_id, name, level (root = 0), and sort depth-first.

Input.

id	name	manager_id
1	Alice	NULL
2	Bob	1
3	Carol	1
4	Dan	2
5	Eve	2
6	Frank	3
7	Grace	4

Code.

WITH RECURSIVE org_chart AS (
    -- anchor: the CEO
    SELECT id, name, manager_id, 0 AS level, ARRAY[id] AS path
    FROM employees
    WHERE manager_id IS NULL

    UNION ALL

    -- recursive term: children of the current frontier
    SELECT e.id, e.name, e.manager_id, oc.level + 1, oc.path || e.id
    FROM employees e
    JOIN org_chart oc ON e.manager_id = oc.id
)
SELECT id, name, level
FROM org_chart
ORDER BY path;

Step-by-step explanation.

1. Anchor. Runs once. Selects Alice — the only row where manager_id IS NULL. Materialises the initial frontier {Alice} with level = 0 and path = [1].
2. Recursive step 1. Joins the frontier {Alice} to employees on e.manager_id = oc.id (i.e. manager_id = 1). Emits Bob and Carol with level = 1 and paths [1, 2], [1, 3].
3. Recursive step 2. New frontier is {Bob, Carol}. Joining on manager_id IN (2, 3) emits Dan (level=2, [1,2,4]), Eve (level=2, [1,2,5]), Frank (level=2, [1,3,6]).
4. Recursive step 3. Frontier {Dan, Eve, Frank} produces Grace (level=3, [1,2,4,7]). No other children exist.
5. Recursive step 4. Frontier is {Grace}. Nobody reports to Grace → recursive term returns zero rows → CTE terminates.
6. Outer query. Selects every accumulated row and orders by path, which renders the tree in depth-first order (Alice → Bob → Dan → Grace → Eve → Carol → Frank).

Output.

id	name	level
1	Alice	0
2	Bob	1
4	Dan	2
7	Grace	3
5	Eve	2
3	Carol	1
6	Frank	2

Rule of thumb. Any time you catch yourself writing a while row.parent_id is not None loop in application code against a table with a self-referential FK, stop and write a recursive CTE. One query beats N round-trips every time.

Worked example — hierarchies vs graphs, side by side

Detailed explanation.

• A hierarchy is a special graph. A tree is a graph where every node has at most one parent and the reachability from the root has no cycle. A recursive CTE against a tree never revisits a node.
• A graph can have cycles. A friendship edge table can encode alice → bob, bob → carol, carol → alice. Without a cycle guard, the recursive CTE loops forever until MAXRECURSION fires.
• The syntactic split is small. The only difference between a tree walker and a graph walker is one extra WHERE clause and one accumulated array. The mental model is identical.

Question. Given the same recursive CTE skeleton, show the delta between walking a tree and walking a potentially cyclic graph. Highlight the cycle-guard predicate.

Input — tree (employees).

id	name	manager_id
1	Alice	NULL
2	Bob	1

Input — graph (friendships, undirected).

a	b
1	2
2	3
3	1

Code.

-- Tree walker — no cycle guard needed
WITH RECURSIVE org_chart AS (
    SELECT id, name, 0 AS level FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, oc.level + 1
    FROM employees e
    JOIN org_chart oc ON e.manager_id = oc.id
)
SELECT * FROM org_chart;

-- Graph walker — CYCLE GUARD IS MANDATORY
WITH RECURSIVE friends AS (
    SELECT 1 AS start_id, 1 AS node_id, 0 AS hop, ARRAY[1] AS path
    UNION ALL
    SELECT f.start_id,
           CASE WHEN fr.a = f.node_id THEN fr.b ELSE fr.a END AS node_id,
           f.hop + 1,
           f.path || CASE WHEN fr.a = f.node_id THEN fr.b ELSE fr.a END
    FROM friends f
    JOIN friendships fr ON f.node_id IN (fr.a, fr.b)
    WHERE NOT (CASE WHEN fr.a = f.node_id THEN fr.b ELSE fr.a END = ANY(f.path))  -- cycle guard
)
SELECT * FROM friends;

Step-by-step explanation.

1. Tree. The recursive term joins children of the frontier via manager_id = oc.id. Because every child has exactly one manager, no row is ever emitted twice. Termination is automatic when the frontier hits leaves.
2. Graph. The recursive term joins any edge incident to the frontier node. Without a guard, once we visit 1 → 2 → 3, the next step matches 3 → 1 and we start the cycle again. The WHERE NOT (... = ANY(f.path)) predicate blocks re-visiting a node.
3. The path array is the memory. It records every node visited from the starting point along this particular walk. Two different walks from the same start can share prefixes but the path is per-row, not per-CTE-wide.
4. Cost of the guard. Adding = ANY(f.path) is an O(depth) linear scan per recursive step. For deep graphs, this is negligible compared to the join cost.
5. Termination. With the guard in place, the recursive term returns zero rows once every reachable node has been visited from every reachable start. Same as the tree — the frontier eventually drains.

Output — tree walker.

id	name	level
1	Alice	0
2	Bob	1

Output — graph walker (BFS from node 1).

start_id	node_id	hop	path
1	1	0	[1]
1	2	1	[1, 2]
1	3	2	[1, 2, 3]

Rule of thumb. If the structure guarantees a single-parent tree, skip the cycle guard. If the structure has any multi-parent or bidirectional edges, add the guard as a matter of course — even if you "know" the data is cycle-free today, tomorrow's bug will insert one.

Worked example — when NOT to use a recursive CTE

Detailed explanation.

• Depth > 1000 with millions of nodes. Recursive CTE cost is O(edges × depth × node_count in the worktable). At millions of nodes and depth > 10, the plan gets expensive fast. Move to a graph DB or a materialised closure table.
• Read-heavy workload with rare structural changes. If the tree changes weekly but the query runs every second, materialise a closure table once and query it directly. O(1) lookup vs O(depth) recursion.
• BigQuery hard limits. BigQuery's 500-iteration cap and per-slot cost model make deep recursive CTEs pricy; pre-flatten with a dbt materialised transitive closure model.
• You need shortest path, not any path. A recursive CTE finds paths; it does not naturally give the shortest. Cypher / Gremlin do; a recursive CTE with ORDER BY hop LIMIT 1 works but wastes IO.

Question. Given a 20M-node, average-depth-15 hierarchy queried 500 times per second, would you use a recursive CTE? What's the alternative?

Input.

Constraint	Value
Nodes	20 M
Average depth	15
Read QPS	500
Structural change QPS	~1 per day

Code.

-- Closure table — one row per (ancestor, descendant, depth) pair
CREATE TABLE org_closure (
    ancestor_id BIGINT,
    descendant_id BIGINT,
    depth INT,
    PRIMARY KEY (ancestor_id, descendant_id)
);

-- Rebuild from the recursive CTE nightly
INSERT INTO org_closure
WITH RECURSIVE walk AS (
    SELECT id AS ancestor_id, id AS descendant_id, 0 AS depth FROM employees
    UNION ALL
    SELECT w.ancestor_id, e.id, w.depth + 1
    FROM walk w
    JOIN employees e ON e.manager_id = w.descendant_id
)
SELECT * FROM walk;

-- The 500 QPS read now hits a single index lookup, not a recursive CTE
SELECT descendant_id
FROM org_closure
WHERE ancestor_id = :root_id;

Step-by-step explanation.

1. The closure table stores one row per (ancestor, descendant, depth) pair — the transitive closure of the hierarchy. For a tree with N nodes and average depth D, the table has roughly N × D rows.
2. Rebuilding is a single recursive CTE, run once per day (or triggered on structural change). The write cost is amortised.
3. Reads become a single-index lookup: WHERE ancestor_id = :root_id returns all descendants without any recursion at query time.
4. For 500 QPS, the closure table is O(1) per read; the recursive CTE is O(depth × frontier size), roughly 100x slower.
5. The trade-off is disk space (N × D rows) and write amplification on structural changes. For a nightly-rebuilt table with 15-average depth, this is 300M rows for 20M nodes — a couple of GB, trivial on modern storage.

Output.

Approach	Read latency	Write cost	Storage
Recursive CTE at query time	30-200 ms per read	zero	zero
Closure table + nightly rebuild	1-5 ms per read	one recursive CTE / day	~N × D rows
Graph DB (Neo4j)	1-10 ms per read	continuous	native graph store

Rule of thumb. Use a recursive CTE at query time for depth ≤ 10 with reads ≤ 10 QPS. Materialise a closure table for depth > 10 or reads > 100 QPS. Move to a graph DB only when both depth and QPS are high and the structural change rate is comparable to the read rate.

Senior interview question on recursive CTE fit

A senior interviewer often opens with: "When would you reach for a recursive CTE, and when would you push back and say 'not in SQL'? Walk me through the 3-4 questions you ask, in order, and what answers push you one way or the other."

Solution Using a 4-question decision framework

Recursive CTE fit — decision framework
======================================

1. Is the structure self-referential?
   - yes (parent_id, edges table)  → recursive CTE eligible
   - no (flat facts)               → not applicable

2. What is the max depth?
   - ≤ 10 (org chart, category tree) → recursive CTE fine
   - 10–100 (deep BOM)               → recursive CTE + max-recursion override
   - > 100 (very deep DAG)           → closure table or graph DB

3. What is the read QPS?
   - ≤ 10 QPS  → recursive CTE at query time
   - 10–100    → recursive CTE + result cache (Redis / materialised view)
   - > 100     → closure table (rebuilt nightly) or graph DB

4. Are cycles possible?
   - no (tree by construction)  → no cycle guard needed
   - yes (graph, feedback)      → cycle guard + path array mandatory

Step-by-step trace.

Use case	Q1 self-ref	Q2 depth	Q3 read QPS	Q4 cycles	Picked
Small org chart (500 people)	yes	5	2	no	recursive CTE at query time
Product category tree (5k rows)	yes	4	200	no	closure table + rebuild on change
Friendship graph (10M users)	yes	∞	100	yes	graph DB or 2-hop closure
Multi-level BOM (aerospace)	yes	30	20	no (DAG)	recursive CTE + MAXRECURSION override
Dataset lineage graph	yes	20	10	possible	recursive CTE + cycle guard

After the 4-question pass, the fit is usually unambiguous. The remaining edge cases — where recursive CTE, closure table, and graph DB all work — default to whatever the team already operates.

Output:

Approach	When it wins
Recursive CTE at query time	Shallow depth, low-to-medium QPS, tree or bounded DAG
Closure table + nightly rebuild	Medium depth, high QPS, low structural change rate
Graph database (Neo4j, TigerGraph)	Deep, cyclic, and high-QPS at the same time

Why this works — concept by concept:

• Self-referential structure — the gate — recursive CTE is only relevant when the data model has a self-reference (a foreign key back to the same table or an edges table). Flat facts do not need recursion.
• Depth budget — every dialect has a default max recursion. Postgres is effectively unbounded, MySQL is 1000, SQL Server is 100, BigQuery is 500. Depth greater than the default forces an override or a redesign.
• QPS budget — recursive CTEs are O(depth × frontier size) per query. High-QPS reads amortise better against a materialised closure table or a graph DB.
• Cycle possibility — trees do not need a guard; graphs always do. Add the guard whenever the structure has multi-parent or bidirectional edges — even if today's data is clean.
• Cost — recursive CTE at query time is zero infrastructure; closure table adds one nightly job and disk space; graph DB adds a new system to operate. The three tiers scale with the complexity of the workload, not the elegance of the model.

SQL
Topic — CTE
Recursive CTE problems (all difficulty)

Practice →

SQL Topic — CTE · SQL CTE problems in SQL

Practice →

---

2. Recursive CTE anatomy

WITH RECURSIVE cte AS (anchor UNION ALL recursive_term) SELECT ... FROM cte — the only shape you ever need

The mental model in one line: a recursive CTE has exactly two SELECTs stitched by UNION ALL — the anchor runs once and seeds a "frontier"; the recursive term runs repeatedly, each time joining cte to a base table until it returns zero rows. Once you say that out loud, every sql cte interview question about recursion becomes a template you fill in.

The three moving parts.

• Anchor SELECT. The base case. Runs once. Materialises the first "generation" of rows into the CTE's worktable. The anchor is the only place where the CTE's column list is established — the recursive term's column list must match exactly (types included).
• UNION ALL connector. Fuses the anchor and the recursive term. Almost always UNION ALL — you want every generation appended, not deduplicated at the CTE level. UNION (implicit DISTINCT) is legal in the standard but rare in practice.
• Recursive term SELECT. Joins cte (self-reference) to a base table. On every iteration, the executor treats the previous iteration's output as the "current" CTE contents; the recursive term joins that frontier to the base table and emits the next generation. Termination happens when the recursive term returns zero rows.

The stream-vs-set duality.

• Conceptually, the CTE contains the union of all generations by the time the outer query reads from it.
• Operationally, the executor materialises the anchor's rows into a worktable, then iterates: read from the worktable, join to base, insert result back into the worktable, repeat.
• The outer query sees the union — same data as the conceptual model, materialised via the operational one.

UNION ALL vs UNION — the dedup trade-off.

• UNION ALL — preserves all rows. Faster (no sort/hash). The right default.
• UNION — implicit SELECT DISTINCT on every step. Silently dedupes generations. Sometimes useful for cyclic graphs but a cycle guard is usually better.
• Practical rule. Always start with UNION ALL. If you need dedup, do it in the outer query with SELECT DISTINCT where you can see it, not hidden inside the recursion.

Termination — the recursive term must eventually return zero rows.

• Tree termination. Automatic. Leaves have no children; the frontier drains.
• Bounded numeric termination. A WHERE n < 10 predicate on the recursive term forces zero rows once the counter passes the bound.
• Graph termination. The cycle guard (path predicate) removes already-visited nodes; the frontier drains once every reachable node is visited.
• What happens without termination. The dialect's max-recursion setting fires: MySQL errors at 1000, SQL Server at 100, Postgres runs until stack overflow. Never rely on the max-recursion to save you — it is a safety net, not a design.

Running numbers 1..N — the "hello world" that proves the shape.

• The simplest possible recursive CTE. Anchor emits 1. Recursive term emits n + 1 WHERE n < N. Terminates at n = N.
• Reveals the shape without any joins. Useful for generating date series, ID gaps analysis, cross-joining a schedule to a calendar.

Dialect keyword differences.

• Postgres, MySQL 8+, Snowflake, BigQuery, DuckDB — WITH RECURSIVE cte AS (...). The RECURSIVE keyword is required.
• SQL Server — WITH cte AS (...). Recursion is inferred from the self-reference; no RECURSIVE keyword. The rest of the shape is identical.
• Oracle 11g+ — supports the standard WITH cte(col) AS (anchor UNION ALL recursive_term) since 11gR2. Older Oracle uses CONNECT BY syntax (proprietary; do not use in new code).

The generic template — memorise this.

WITH RECURSIVE cte AS (
    -- ANCHOR: base case, runs once
    SELECT ... FROM base_table WHERE <root_condition>

    UNION ALL

    -- RECURSIVE TERM: joins CTE to base table, runs until 0 rows
    SELECT ... FROM base_table b JOIN cte ON <link>
    WHERE <termination_predicate>
)
SELECT ... FROM cte
ORDER BY ...;

Common interview probes on anatomy.

• "What is the difference between the anchor and the recursive term?" — anchor runs once and seeds the CTE; recursive term joins CTE to a base table and runs until zero rows.
• "Why UNION ALL and not UNION?" — UNION ALL preserves rows; UNION dedupes. Dedup at the CTE level is almost always the wrong place; do it in the outer query.
• "How do you terminate a recursive CTE?" — the recursive term must return zero rows. For trees, automatic. For counters, a WHERE n < bound. For graphs, a cycle guard.
• "What if I omit RECURSIVE in Postgres?" — you get a syntax error on the self-reference; Postgres does not infer recursion.

Worked example — running numbers 1..N

Detailed explanation.

• Why start here. Running numbers is the smallest recursive CTE — no joins, no path arrays, just a counter. It shows the shape (anchor + recursive + termination) with nothing else in the way.
• The termination predicate. WHERE n < 10 on the recursive term. On the 10th iteration, n = 10, so n < 10 is false → no rows → CTE terminates. The final CTE contains n = 1, 2, ..., 10.
• Where this is useful. Generating a date series (WITH RECURSIVE dates AS (...) SELECT current_date + n * interval '1 day' FROM dates), building a slot table for calendar joins, generating a range for gaps-and-islands prep work.

Question. Write a recursive CTE that generates the numbers 1 through 10 as a single-column result set. Show it in Postgres, MySQL 8, and SQL Server syntax.

Input.

(none — the CTE generates its own input)

Code.

-- Postgres / MySQL 8 / Snowflake / BigQuery — WITH RECURSIVE required
WITH RECURSIVE nums AS (
    SELECT 1 AS n                        -- anchor
    UNION ALL
    SELECT n + 1 FROM nums WHERE n < 10   -- recursive term
)
SELECT n FROM nums;

-- SQL Server — recursion inferred, no RECURSIVE keyword
WITH nums AS (
    SELECT 1 AS n
    UNION ALL
    SELECT n + 1 FROM nums WHERE n < 10
)
SELECT n FROM nums;

Step-by-step explanation.

1. Iteration 0 (anchor). Executes SELECT 1. Worktable now has {n=1}. This is the initial "current CTE contents."
2. Iteration 1 (recursive). Executes SELECT n + 1 FROM nums WHERE n < 10 against the current CTE contents. n = 1 < 10, so it emits n = 2. Worktable accumulates {n=1, n=2}.
3. Iteration 2 (recursive). The "current CTE" for this step is just the previous iteration's output ({n=2}), not the entire worktable. This is the SQL-standard semantics for recursive CTE — the recursive term joins the incremental frontier, not the union. Emits n = 3. Worktable now {1, 2, 3}.
4. Iterations 3-9. Same shape. Emits n = 4, 5, 6, 7, 8, 9, 10. Worktable accumulates through n = 10.
5. Iteration 10. Current frontier is {n = 10}. 10 < 10 is false → recursive term emits zero rows → CTE terminates.
6. Outer SELECT. Reads all 10 rows from the accumulated worktable. Returns 1 through 10.

Output.

n
1
2
3
4
5
6
7
8
9
10

Rule of thumb. The running-numbers pattern is the fastest way to sanity-check that a dialect supports recursive CTEs and that your syntax is right. If this 4-line query fails, you know to check the RECURSIVE keyword and the anchor+recursive shape before touching anything more complex.

Worked example — UNION ALL vs UNION

Detailed explanation.

• UNION ALL preserves every emitted row. The worktable grows monotonically; the recursive term joins the current step's output to the base table.
• UNION performs an implicit SELECT DISTINCT between the anchor and the recursive term. In practice, this means the executor dedupes across generations. If a generation would emit a row that already appeared in the worktable, that row is silently dropped.
• The trap. In a cyclic graph, UNION can sometimes accidentally save you (the cycle produces a duplicate row that gets deduped), but it hides the bug rather than fixing it. Use a cycle guard, not UNION, for graph traversal.

Question. Show the difference between UNION ALL and UNION when the recursive term can re-emit the same row. Use a tiny 3-node cyclic graph.

Input — edges (directed cycle).

src	dst
1	2
2	3
3	1

Code.

-- UNION ALL — will run until MAXRECURSION fires
WITH RECURSIVE walk_all AS (
    SELECT 1 AS start_id, 1 AS node_id, 0 AS hop
    UNION ALL
    SELECT w.start_id, e.dst, w.hop + 1
    FROM walk_all w
    JOIN edges e ON w.node_id = e.src
)
SELECT * FROM walk_all;
-- ERROR: max recursion 100 exhausted (SQL Server) / 1000 (MySQL)

-- UNION — implicit DISTINCT dedupes and (accidentally) terminates
WITH RECURSIVE walk_dist AS (
    SELECT 1 AS start_id, 1 AS node_id, 0 AS hop
    UNION
    SELECT w.start_id, e.dst, w.hop + 1
    FROM walk_dist w
    JOIN edges e ON w.node_id = e.src
)
SELECT * FROM walk_dist;

Step-by-step explanation.

1. UNION ALL — infinite loop. Anchor emits {1}. Recursive step 1 emits {2} (via edge 1→2). Step 2 emits {3} (via 2→3). Step 3 emits {1} (via 3→1) — but with a different hop (3) than the anchor (0). Since UNION ALL compares all columns, (1, 1, 0) and (1, 1, 3) are different rows; the executor keeps recursing forever.
2. UNION — silent dedup. Same steps 1-3. Step 3 emits (1, 1, 3). UNION compares — wait, is (1, 1, 3) equal to (1, 1, 0)? No, hop differs. So the dedup still lets it through. If you drop hop from the SELECT, then UNION would collapse the cycle to a single row and terminate. But that also loses information you probably wanted.
3. The lesson. UNION only terminates a cycle if the columns you SELECT collapse to already-seen values. Any hop column, timestamp, or path array defeats the accidental termination.
4. The correct fix. Add a cycle guard. Track visited nodes in a path array and filter with NOT node_id = ANY(path). Do not rely on UNION for termination.
5. Cost. UNION costs an extra hash/sort per step to dedupe. On non-cyclic recursion, that overhead is pure waste — always use UNION ALL unless you have measured UNION and it is cheaper.

Output — UNION ALL on 3-cycle.

start_id	node_id	hop
1	1	0
1	2	1
1	3	2
1	1	3
...	...	... (runs until MAXRECURSION)

Rule of thumb. Default to UNION ALL. Reach for UNION only when you have measured a specific dedup win and can articulate exactly which duplicate you are dropping. For graph traversal, use a cycle guard — never rely on UNION to save you.

Worked example — dialect keyword differences

Detailed explanation.

• Postgres, MySQL 8+, Snowflake, BigQuery, DuckDB — the WITH RECURSIVE keyword is mandatory. Omit it and you get a syntax error at parse time.
• SQL Server — no RECURSIVE keyword exists. The parser detects recursion from the self-reference. The rest of the shape (anchor + UNION ALL + recursive term) is identical.
• Oracle — supports the standard WITH ... AS (anchor UNION ALL recursive_term) since 11g Release 2. Legacy code uses CONNECT BY — do not use in new code, it is not portable.

Question. Write the same running-numbers 1..5 CTE in the four dominant dialects. Highlight the keyword differences.

Input.

(none — the CTE generates its own input)

Code.

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

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

-- SQL Server (no RECURSIVE keyword)
WITH nums AS (
    SELECT 1 AS n
    UNION ALL
    SELECT n + 1 FROM nums WHERE n < 5
)
SELECT n FROM nums
OPTION (MAXRECURSION 1000);   -- optional; default 100

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

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

Step-by-step explanation.

1. Every dialect ships the same anchor + UNION ALL + recursive-term shape. The syntactic delta is exactly one keyword (RECURSIVE) and, for SQL Server, an optional OPTION (MAXRECURSION N) at the outer query.
2. Postgres, MySQL, Snowflake, BigQuery, DuckDB all require RECURSIVE. Omitting it gives a syntax error, not a silent non-recursive interpretation.
3. SQL Server's parser infers recursion when the CTE's FROM clause references itself. This is a legacy design choice (SQL Server 2005 pre-dated the SQL standard's RECURSIVE keyword); it works but is easy to miss when porting.
4. Oracle 11gR2+ supports the standard shape too, without RECURSIVE (Oracle also infers). Legacy Oracle used CONNECT BY PRIOR, which is proprietary and less flexible than the standard CTE — do not use in new code.
5. When porting between dialects, adding or removing the RECURSIVE keyword is usually the only change required. If you also need a max-recursion override, the syntax differs per dialect (see H2-5).

Output.

n
1
2
3
4
5

Rule of thumb. Write portable code by defaulting to WITH RECURSIVE. On SQL Server, the keyword is accepted (as of 2019+) but harmless. This keeps you code-compatible across every mainstream engine except very old Oracle.

Senior interview question on recursive CTE anatomy

A senior interviewer might ask: "Walk me through exactly what the database does when it executes a recursive CTE. What is the anchor doing, what is the recursive term doing, and how does the executor know when to stop? Where can it go wrong?"

Solution Using the anchor + iterative-frontier execution model

Recursive CTE execution — inside the executor
=============================================

Setup
-----
1. Parser detects the WITH RECURSIVE cte AS (...) shape.
2. The CTE's column list is fixed from the anchor SELECT.
3. Executor allocates two worktables:
   - "accumulated" — every row ever emitted
   - "current" — rows emitted in the last iteration

Anchor (runs once)
------------------
4. Execute the anchor SELECT.
5. Insert rows into BOTH "accumulated" and "current".

Recursive term (iterates)
-------------------------
6. While "current" is not empty:
   a. Execute the recursive term with cte := "current".
   b. Insert emitted rows into "accumulated".
   c. Replace "current" with the emitted rows.
7. Loop terminates when the recursive term emits zero rows.

Outer query
-----------
8. The outer SELECT reads "accumulated" as if it were a regular table.

Failure modes
-------------
9. No termination → max-recursion setting fires → error.
10. Column list mismatch between anchor and recursive term → error.
11. Recursive term references the CTE more than once → error in some dialects.

Step-by-step trace.

For running-numbers 1..3 in Postgres:

Iteration	Current worktable	Recursive term emits	Accumulated
0 (anchor)	—	{1}	{1}
1	{1}	{2}	{1, 2}
2	{2}	{3}	{1, 2, 3}
3	{3}	{} (3 < 3 false)	{1, 2, 3}
4	terminate	—	{1, 2, 3}

The current worktable is the incremental frontier — the last iteration's output, not the whole accumulated set. This is the semantic that lets the executor be O(edges) per step rather than O(accumulated).

Output:

Executor concept	What it does
Anchor SELECT	Runs once; seeds the CTE
Current worktable	Holds the last iteration's output
Accumulated worktable	Holds every emitted row
Recursive term	Joins base to current; emits next generation
Termination	Recursive term returns zero rows
Outer SELECT	Reads accumulated as if it were a regular table

Why this works — concept by concept:

• Anchor + recursive term — the shape is a standards-defined two-part CTE. The anchor supplies the base case and the column types; the recursive term supplies the induction step. Interviewers listen for this vocabulary.
• Incremental frontier — the recursive term joins to the last iteration's output, not the whole accumulated set. This is why the executor is O(edges × depth) not O(edges × accumulated²).
• UNION ALL semantics — every recursive-term row is appended without dedup. Dedup at the CTE level is expensive and rarely correct; use UNION ALL and dedup in the outer query if needed.
• Termination is your job — the recursive term must produce zero rows; the executor does not infer termination. Max-recursion settings are a safety net for accidental infinite loops.
• Cost — O(anchor + Σ recursive-term over generations). For a tree of N nodes at depth D, roughly O(N) since each edge is visited once. For a graph without a cycle guard, O(∞).

SQL
Topic — CTE
Recursive CTE anatomy problems

Practice →

SQL Topic — CTE · hard Hard CTE interview problems

Practice →

---

3. Hierarchies and trees — org chart / category tree

sql hierarchy query walks a single-parent tree — anchor selects the root, recursive term joins children, depth column and path array make the tree navigable

The mental model in one line: a hierarchy is a tree where every row has at most one parent; the recursive CTE anchors on the roots (WHERE manager_id IS NULL), the recursive term joins children of the current frontier (WHERE e.manager_id = t.id), a level + 1 column tracks depth, and a path array (or concatenated string) records ancestry. Once you say that out loud, every sql hierarchy query interview question about org charts, category trees, comment threads, and filesystems becomes the same skeleton with the label swapped.

The canonical shape.

• Anchor. Selects the roots — rows where the parent column is NULL, or a specific starting row when you want a sub-tree.
• Recursive term. Joins the base table to the CTE where base.parent_id = cte.id. Emits the direct reports of every current-frontier row.
• Level column. cte.level + 1 on every recursive step. Root is level 0 (or 1 — pick one and stick to it).
• Path array. cte.path || base.id on every recursive step. Records the full ancestry chain from root to this row.
• Termination. Automatic — leaves have no children; the recursive term drains.

Two-column identity: (level, path).

• Combined, (level, path) uniquely identifies each row's position in the tree.
• ORDER BY path renders the tree in depth-first order (siblings appear together, then their children, then the next sibling).
• ORDER BY level, name renders the tree in breadth-first level order (all level-0, then all level-1, then all level-2).

Path array vs concatenated string.

• Postgres. Native array support: ARRAY[id], path || e.id. Comparisons are natural (= ANY, <@).
• MySQL. CONCAT(cte.path, '/', e.id) returns a string. Watch for lexicographic sort order ('2' > '10').
• SQL Server / Snowflake / BigQuery. Use CONCAT or string helpers; padded integers (FORMAT(id, '000000')) keep sort order sane.

Where the anchor changes shape.

• Whole tree. WHERE parent_id IS NULL.
• Descendants of a specific row. WHERE id = :root_id.
• Ancestors of a specific row. Flip the join direction — anchor is WHERE id = :leaf_id, recursive term is JOIN employees e ON cte.manager_id = e.id. Walks up instead of down.

Depth-first vs breadth-first ordering.

• Depth-first (DFS). Emit each sub-tree in full before moving to the next sibling. ORDER BY path on a tuple-encoded or padded-string path produces DFS.
• Breadth-first (BFS). Emit all level-0, then level-1, then level-2. ORDER BY level, name produces BFS.
• Postgres shortcut. SEARCH DEPTH FIRST BY id SET seq or SEARCH BREADTH FIRST BY id SET seq adds a seq column that sorts correctly without hand-coding the path.

Category tree — the e-commerce twin.

• Products belong to categories that belong to categories: Electronics → Computers → Laptops → Gaming Laptops.
• Same shape as the org chart, just different labels. Anchor is WHERE parent_category_id IS NULL; recursive term joins children.
• Common interview probe: "given a category id, list every product in that category or any descendant category." Solved with a recursive CTE on categories plus a join to products.

Common interview probes on hierarchies.

• "How do you list every employee under a specific manager?" — recursive CTE with the manager as the anchor, recursive term joins direct reports.
• "How do you compute the depth of every node in an org chart?" — recursive CTE anchored on manager_id IS NULL, with level + 1 per recursive step.
• "How do you find the CEO of an arbitrary employee?" — flip the direction — anchor on that employee, recursive term walks up.
• "How do you sort the tree depth-first?" — carry a path array (or padded-string) and ORDER BY path in the outer query.

Worked example — employees under a specific manager

Detailed explanation.

• The interview probe. "Given manager_id = 2 (Bob), list every employee under Bob with their depth and full path from Bob." This is the "subtree query" — the anchor is a specific row rather than the whole root set.
• The delta from the whole-tree walk. Only the anchor changes. Instead of WHERE manager_id IS NULL, it becomes WHERE id = 2. The recursive term is identical.
• What the path represents. path = [2, 4, 7] means Grace's chain from Bob (the query root) is Bob → Dan → Grace. Note that this path starts at Bob, not at the tree root (Alice) — it is a subtree path.

Question. Write a recursive CTE that returns every employee under manager_id = 2 (Bob), with level (Bob = 0) and path (starts at Bob).

Input — employees.

id	name	manager_id
1	Alice	NULL
2	Bob	1
3	Carol	1
4	Dan	2
5	Eve	2
6	Frank	3
7	Grace	4

Code.

WITH RECURSIVE subtree AS (
    -- anchor: Bob himself
    SELECT id, name, manager_id, 0 AS level, ARRAY[id] AS path
    FROM employees
    WHERE id = 2

    UNION ALL

    -- recursive: children of the frontier
    SELECT e.id, e.name, e.manager_id, s.level + 1, s.path || e.id
    FROM employees e
    JOIN subtree s ON e.manager_id = s.id
)
SELECT id, name, level, path
FROM subtree
ORDER BY path;

Step-by-step explanation.

1. Anchor. Selects Bob (id=2). Emits (2, Bob, 1, 0, [2]). Frontier is {Bob}.
2. Recursive step 1. Joins children of Bob. Emits Dan (level=1, path=[2, 4]) and Eve (level=1, path=[2, 5]). Frontier now {Dan, Eve}.
3. Recursive step 2. Children of Dan: Grace (level=2, path=[2, 4, 7]). Children of Eve: none. Frontier now {Grace}.
4. Recursive step 3. Children of Grace: none. Recursive term emits zero rows → CTE terminates.
5. Outer query. ORDER BY path gives depth-first traversal from Bob: Bob → Dan → Grace → Eve.

Output.

id	name	level	path
2	Bob	0	[2]
4	Dan	1	[2, 4]
7	Grace	2	[2, 4, 7]
5	Eve	1	[2, 5]

Rule of thumb. For subtree queries, change only the anchor. The recursive term stays identical across "whole tree," "subtree under X," and "ancestors of X" (though for ancestors, the join direction flips).

Worked example — ancestors of an employee

Detailed explanation.

• The direction flip. For descendants, the recursive term joins e.manager_id = cte.id. For ancestors, it joins cte.manager_id = e.id — cte holds the child, e is the parent.
• The termination. Automatic. The root has manager_id IS NULL; the recursive term joining a NULL manager_id emits zero rows.
• The path. Prepends parents as you walk up: [7, 4, 2, 1] for Grace's ancestry to Alice. path[1] is Grace, path[-1] (or reversed) is the CEO.

Question. Given employee_id = 7 (Grace), return every ancestor in the chain up to the CEO, with depth (Grace = 0, CEO = 3 in this tree).

Input — same employees table as above.

Code.

WITH RECURSIVE ancestors AS (
    -- anchor: Grace herself
    SELECT id, name, manager_id, 0 AS depth_up
    FROM employees
    WHERE id = 7

    UNION ALL

    -- recursive: walk UP via manager_id
    SELECT e.id, e.name, e.manager_id, a.depth_up + 1
    FROM employees e
    JOIN ancestors a ON a.manager_id = e.id
)
SELECT id, name, depth_up
FROM ancestors
ORDER BY depth_up;

Step-by-step explanation.

1. Anchor. Selects Grace (id=7). Frontier {Grace}, depth_up = 0.
2. Recursive step 1. Joins Grace's manager: Dan (id=4). Emits (4, Dan, 2, 1). Frontier {Dan}.
3. Recursive step 2. Joins Dan's manager: Bob (id=2). Emits (2, Bob, 1, 2). Frontier {Bob}.
4. Recursive step 3. Joins Bob's manager: Alice (id=1). Emits (1, Alice, NULL, 3). Frontier {Alice}.
5. Recursive step 4. Alice's manager_id IS NULL. The recursive term's join ON a.manager_id = e.id has NULL on the left side → no match → zero rows emitted → CTE terminates.
6. Outer query. Orders by depth_up — starts at Grace (0), ends at the CEO Alice (3).

Output.

id	name	depth_up
7	Grace	0
4	Dan	1
2	Bob	2
1	Alice	3

Rule of thumb. The direction of the recursive term's join determines "up" vs "down." Descendants use e.manager_id = cte.id; ancestors use cte.manager_id = e.id. Everything else stays the same.

Worked example — category tree with product rollup

Detailed explanation.

• The e-commerce twin. A categories table has (id, name, parent_category_id). A products table has (id, name, category_id). Interview probe: "list every product in category 3 or any descendant category of 3."
• The two-CTE chain. First recursive CTE walks the category tree from id = 3. Second (regular) CTE joins products to that walk.
• Why not a single query. You can inline the join, but the two-step form is more readable and often easier for the optimiser to plan.

Question. Given category_id = 3 (Computers), return every product in that category or any descendant. Show the category tree walk and the product join.

Input — categories.

id	name	parent_category_id
1	Everything	NULL
2	Books	1
3	Computers	1
4	Laptops	3
5	Gaming	4
6	Desktops	3

Input — products.

id	name	category_id
100	Novel	2
200	Textbook	2
300	MacBook	4
400	Alienware	5
500	iMac	6

Code.

WITH RECURSIVE cat_tree AS (
    -- anchor: Computers
    SELECT id, name, parent_category_id
    FROM categories
    WHERE id = 3

    UNION ALL

    -- recursive: descendants
    SELECT c.id, c.name, c.parent_category_id
    FROM categories c
    JOIN cat_tree ct ON c.parent_category_id = ct.id
)
SELECT p.id, p.name, c.name AS category
FROM products p
JOIN cat_tree c ON p.category_id = c.id
ORDER BY p.id;

Step-by-step explanation.

1. Anchor. Selects Computers (id=3). Frontier {Computers}.
2. Recursive step 1. Children of Computers: Laptops (id=4), Desktops (id=6). Frontier {Laptops, Desktops}.
3. Recursive step 2. Children of Laptops: Gaming (id=5). Children of Desktops: none. Frontier {Gaming}.
4. Recursive step 3. Children of Gaming: none. Recursive term emits zero rows → CTE terminates. cat_tree now contains {Computers, Laptops, Desktops, Gaming}.
5. Outer query. Joins products to cat_tree. Every product whose category_id matches any row in the tree passes through. MacBook (Laptops), Alienware (Gaming), iMac (Desktops) match; Novel and Textbook (both Books) do not.

Output.

id	name	category
300	MacBook	Laptops
400	Alienware	Gaming
500	iMac	Desktops

Rule of thumb. For "products in a category or any descendant category," write the recursive CTE on the category tree first, then join products. The two-step shape reads naturally and gives the planner clear boundaries to reason about.

Senior interview question on org-chart traversal

A senior interviewer might ask: "Write a SQL query that returns, for every employee, their name, their level in the org chart (CEO = 0), their manager's name, and the total number of employees under them (direct + indirect reports). One query, no application code."

Solution Using a recursive CTE plus an aggregate join

WITH RECURSIVE org AS (
    -- anchor: the CEO
    SELECT id, name, manager_id, 0 AS level, ARRAY[id] AS path
    FROM employees
    WHERE manager_id IS NULL

    UNION ALL

    -- recursive: children
    SELECT e.id, e.name, e.manager_id, o.level + 1, o.path || e.id
    FROM employees e
    JOIN org o ON e.manager_id = o.id
),
reports_count AS (
    -- for every row, count how many other rows have this row's id in their path
    SELECT o1.id AS emp_id,
           COUNT(o2.id) - 1 AS total_reports   -- minus self
    FROM org o1
    JOIN org o2 ON o1.id = ANY(o2.path)
    GROUP BY o1.id
)
SELECT o.name AS employee,
       o.level,
       m.name AS manager,
       r.total_reports
FROM org o
LEFT JOIN employees m ON o.manager_id = m.id
JOIN reports_count r ON o.id = r.emp_id
ORDER BY o.path;

Step-by-step trace.

Using the seven-row employees table:

Step	What it does
1	Anchor: emit (Alice, 0, [1])
2	Recursive: children of Alice → Bob (level 1, [1,2]), Carol (level 1, [1,3])
3	Recursive: children of Bob, Carol → Dan [1,2,4], Eve [1,2,5], Frank [1,3,6]
4	Recursive: children of Dan/Eve/Frank → Grace [1,2,4,7]
5	Recursive: zero rows → CTE org terminates
6	reports_count CTE joins org to itself where o1.id = ANY(o2.path) — for every ancestor, count descendants
7	Outer SELECT joins org to employees (via manager_id) and to reports_count
8	ORDER BY path renders DFS

The self-join in reports_count uses o1.id = ANY(o2.path): row o1 is "in the path of" row o2 if and only if o1 is an ancestor of o2. Grouping by o1.id and counting o2.id (minus 1 for self) gives the count of descendants.

Output:

employee	level	manager	total_reports
Alice	0	(NULL)	6
Bob	1	Alice	3
Dan	2	Bob	1
Grace	3	Dan	0
Eve	2	Bob	0
Carol	1	Alice	1
Frank	2	Carol	0

Why this works — concept by concept:

• Path array as ancestry chain — carrying the full path from root to this row makes every ancestor addressable. o1.id = ANY(o2.path) is a set-membership test that returns TRUE if and only if o1 is an ancestor of o2.
• Self-join on org — the CTE is used twice in the same query: once to enumerate rows, once to count descendants via path membership. A regular CTE is fine here because the second usage does not itself recurse.
• LEFT JOIN for the manager name — the CEO's manager_id is NULL; a LEFT JOIN preserves the row with a NULL manager name rather than dropping it.
• ORDER BY path — arrays compare element-wise; [1] < [1,2] < [1,2,4] < [1,2,4,7] < [1,2,5] < [1,3] < [1,3,6]. That is exactly the DFS pre-order.
• Cost — recursive CTE is O(N) for a tree of N nodes. The reports_count self-join is O(N × avg_depth); on org charts with depth ≤ 10 and N ≤ 100K, that's a millisecond query.

SQL
Topic — tree
Tree traversal problems

Practice →

SQL Topic — CTEs CTE hierarchy problems

Practice →

---

4. Graph traversal and cycle detection

graph traversal sql walks a multi-parent (possibly cyclic) edge table — the path array is your memory, the NOT visited predicate is your cycle guard, and Postgres has built-in SEARCH and CYCLE clauses

The mental model in one line: a graph is an edges table (src, dst) where any node can point to many; the recursive CTE anchors on the starting node, the recursive term joins every incident edge to the frontier, an accumulated path array records visited nodes, and a NOT node = ANY(path) predicate blocks cycles. Once you say that out loud, every friendship-BFS, permission-chain, or dependency-graph interview question becomes the same recipe with different labels.

Directed vs undirected edges.

• Directed. edges(src, dst) means src → dst only. Recursive term joins edges.src = cte.node_id; emits edges.dst.
• Undirected. Same table, but src ↔ dst (both ways). Recursive term joins where edges.src = cte.node_id or edges.dst = cte.node_id; emits the other endpoint.
• Symmetric edge trick. Store undirected edges as two rows ((a, b) and (b, a)) and treat as directed. Trades storage for query simplicity.

BFS via recursive CTE.

• Anchor emits the starting node with hop = 0, path = [start].
• Recursive term joins each frontier node to edges, filtered by NOT dst = ANY(path). Increments hop, appends dst to path.
• Terminates when every reachable-from-start node has been visited (frontier drains).

Cycle detection — three flavours.

• Path array with = ANY (Postgres, DuckDB) — WHERE NOT child = ANY(cte.path). O(depth) per row, but O(depth) is small.
• Concatenated string with LIKE (MySQL, SQL Server) — WHERE cte.path NOT LIKE CONCAT('%,', child, ',%'). Same idea; slower on very deep paths.
• Postgres CYCLE clause — declarative: CYCLE id SET is_cycle USING path. Adds is_cycle and path columns automatically; you filter WHERE NOT is_cycle in the outer query.

Postgres SEARCH and CYCLE — the built-ins.

• SEARCH BREADTH FIRST BY col SET seq — adds a seq column that, when you ORDER BY seq, gives BFS order.
• SEARCH DEPTH FIRST BY col SET seq — same, but DFS order.
• CYCLE col SET is_cycle USING path — adds is_cycle (bool) and path (array) columns. Sets is_cycle = true the moment a cycle is detected; the recursive term stops on cycle-flagged rows. Combines cleanly with SEARCH.

Shortest path — recursive CTE + aggregation.

• Recursive CTE walks all paths from a start.
• Outer query: SELECT MIN(hop) FROM cte WHERE node_id = :target.
• Not efficient for large graphs (recursive term enumerates every path), but correct.
• For large graphs, use a graph DB or an app-side BFS with proper visited state.

Common interview probes on graphs.

• "How do you detect a cycle in a graph in SQL?" — accumulate a path array in the recursive CTE; filter NOT child = ANY(path) on the recursive term.
• "How do you find the shortest path between two nodes?" — recursive CTE that walks all paths; MIN(hop) FROM cte WHERE node_id = :target. Slow but correct.
• "What does Postgres' SEARCH BREADTH FIRST clause do?" — adds an ordering column that sorts BFS-first without hand-coding path arithmetic.
• "When would you not use a recursive CTE for a graph?" — high-QPS shortest-path queries on large graphs → graph DB.

Worked example — undirected friendship graph BFS

Detailed explanation.

• The setup. A friendships(a, b) table storing undirected edges. To make the join symmetric, we treat both friendships.a = cte.node_id and friendships.b = cte.node_id as matches.
• The visited-path guard. Without a guard, the recursive term keeps re-visiting nodes and looping through the triangle 1-2-3 forever. WHERE NOT other_endpoint = ANY(path) stops it.
• The output shape. For each starting node, we get one row per reachable node with hop (distance) and path (the sequence).

Question. Given an undirected friendship graph, write a recursive CTE that returns every friend-of-a-friend (up to 3 hops) from user 1, with the hop distance and the full path.

Input — friendships (undirected).

a	b
1	2
1	3
2	4
3	4
4	5

Code.

WITH RECURSIVE bfs AS (
    -- anchor: user 1
    SELECT 1 AS node_id, 0 AS hop, ARRAY[1] AS path
    UNION ALL
    SELECT other AS node_id, b.hop + 1, b.path || other
    FROM bfs b
    JOIN LATERAL (
        SELECT CASE WHEN f.a = b.node_id THEN f.b ELSE f.a END AS other
        FROM friendships f
        WHERE b.node_id IN (f.a, f.b)
    ) e ON true
    WHERE NOT other = ANY(b.path)
      AND b.hop < 3
)
SELECT node_id, hop, path
FROM bfs
ORDER BY hop, node_id;

Step-by-step explanation.

1. Anchor. Emits user 1 with hop = 0, path = [1]. Frontier {1}.
2. Recursive step 1. For frontier node 1, joins friendships where 1 IN (a, b). Matches edges (1,2) and (1,3). The LATERAL picks the other endpoint. Filter NOT other = ANY(path) is true for both. Filter hop < 3 is true. Emits nodes 2 and 3 with hop = 1. Paths [1, 2] and [1, 3].
3. Recursive step 2. Frontier is {2, 3}. From node 2: edges (1,2) and (2,4). Other endpoints: 1 (blocked by path guard), 4 (allowed). From node 3: edges (1,3) and (3,4). Other endpoints: 1 (blocked), 4 (allowed via different path [1, 3, 4]). Emits (4, 2, [1, 2, 4]) and (4, 2, [1, 3, 4]).
4. Recursive step 3. Frontier is {4 (from path [1,2,4]), 4 (from path [1,3,4])}. From node 4: edges (2,4), (3,4), (4,5). Other endpoints: 2, 3, 5. Path guards block 2 and 3 (already in each path). 5 is allowed. Emits (5, 3, [1, 2, 4, 5]) and (5, 3, [1, 3, 4, 5]).
5. Recursive step 4. Frontier is {5, 5}. But hop < 3 is false (would be 4) → recursive term emits zero rows → CTE terminates.
6. Outer query. Orders by (hop, node_id). Returns 1 at hop 0, 2/3 at hop 1, 4 at hop 2 (two paths), 5 at hop 3 (two paths).

Output.

node_id	hop	path
1	0	[1]
2	1	[1, 2]
3	1	[1, 3]
4	2	[1, 2, 4]
4	2	[1, 3, 4]
5	3	[1, 2, 4, 5]
5	3	[1, 3, 4, 5]

Rule of thumb. BFS in SQL emits every reachable path, not every unique node. For "unique nodes at each hop," dedup with SELECT DISTINCT node_id, MIN(hop) in the outer query. Two paths to the same node at the same hop is a signal of shortest-path ties.

Worked example — cycle detection with a directed graph

Detailed explanation.

• The setup. A directed edges(src, dst) table containing a cycle 1 → 2 → 3 → 1. Without a cycle guard, the recursive term loops forever.
• The path predicate. WHERE NOT dst = ANY(path) prevents re-visiting. When dst = 1 and path = [1, 2, 3], the guard blocks the emission.
• Detecting the cycle explicitly. If the interviewer wants "list the cycles," track the cycle with an additional flag: is_cycle := dst = ANY(path) on the emit; then WHERE is_cycle in the outer query.

Question. Given a directed graph with a cycle 1 → 2 → 3 → 1, walk from node 1 and detect the cycle. Return the path that closes the loop.

Input — edges (directed).

src	dst
1	2
2	3
3	1
3	4

Code.

WITH RECURSIVE walk AS (
    SELECT 1 AS node_id, ARRAY[1] AS path, false AS is_cycle
    UNION ALL
    SELECT e.dst,
           w.path || e.dst,
           e.dst = ANY(w.path) AS is_cycle
    FROM walk w
    JOIN edges e ON w.node_id = e.src
    WHERE NOT w.is_cycle                       -- stop expanding once cycle found on this path
)
SELECT node_id, path, is_cycle
FROM walk
ORDER BY array_length(path, 1);

Step-by-step explanation.

1. Anchor. (1, [1], false). Frontier {1}.
2. Recursive step 1. Edge 1 → 2. dst = 2 not in [1] → is_cycle = false. Emits (2, [1, 2], false).
3. Recursive step 2. Edge 2 → 3. dst = 3 not in [1, 2] → is_cycle = false. Emits (3, [1, 2, 3], false).
4. Recursive step 3. From node 3: edges 3 → 1 and 3 → 4.
   • 3 → 1: dst = 1 is in [1, 2, 3] → is_cycle = true. Emits (1, [1, 2, 3, 1], true).
   • 3 → 4: dst = 4 not in [1, 2, 3] → is_cycle = false. Emits (4, [1, 2, 3, 4], false).
5. Recursive step 4. Frontier row (1, [1, 2, 3, 1], true) is blocked from expanding by WHERE NOT w.is_cycle. Frontier row (4, [1, 2, 3, 4], false): no outgoing edges from 4 → emits nothing.
6. Recursive step 5. Zero rows → CTE terminates.
7. Outer query. WHERE is_cycle returns exactly the row(s) that closed a cycle.

Output.

node_id	path	is_cycle
1	[1]	false
2	[1, 2]	false
3	[1, 2, 3]	false
1	[1, 2, 3, 1]	true
4	[1, 2, 3, 4]	false

Rule of thumb. For every graph traversal, add a path column and a cycle guard even if you "know" the data is cycle-free. The overhead is O(depth) per row — negligible — and the safety is invaluable. For explicit cycle reporting, add an is_cycle boolean and stop expanding on true.

Worked example — Postgres SEARCH + CYCLE built-ins

Detailed explanation.

• What SEARCH does. Adds an ordering column that, when you ORDER BY it, gives DFS or BFS order without hand-coding.
• What CYCLE does. Adds is_cycle (bool) and path (array) columns automatically. Sets is_cycle = true the moment a cycle is detected; the recursive term stops expanding cycle-flagged rows.
• Why prefer them. Declarative, less error-prone, harder to introduce a bug. And often the planner can optimise a CYCLE-clause CTE more aggressively than a hand-coded path predicate.

Question. Rewrite the cycle-detection query using Postgres' SEARCH DEPTH FIRST and CYCLE clauses. Compare readability.

Input — same directed edges table with a 1 → 2 → 3 → 1 cycle.

Code.

WITH RECURSIVE walk (node_id) AS (
    SELECT 1
    UNION ALL
    SELECT e.dst
    FROM walk w
    JOIN edges e ON w.node_id = e.src
)
SEARCH DEPTH FIRST BY node_id SET seq
CYCLE node_id SET is_cycle USING path
SELECT node_id, path, is_cycle, seq
FROM walk
ORDER BY seq;

Step-by-step explanation.

1. Postgres synthesises the path column automatically because of the CYCLE ... USING path clause. No manual ARRAY[node_id] in the anchor.
2. The CYCLE clause tracks visited nodes for us. When the recursive term is about to emit a row whose node_id is already in path, Postgres marks is_cycle = true and does not expand that row further.
3. The SEARCH DEPTH FIRST BY node_id SET seq adds a seq integer column. Rows sorted by seq are in DFS pre-order.
4. The outer query orders by seq. Postgres has already done the visited-set bookkeeping.
5. Compared to the hand-coded version: no explicit path array, no explicit NOT ... = ANY(path) predicate, no explicit is_cycle boolean. Postgres does all three declaratively.

Output.

node_id	path	is_cycle	seq
1	{1}	false	1
2	{1, 2}	false	2
3	{1, 2, 3}	false	3
1	{1, 2, 3, 1}	true	4
4	{1, 2, 3, 4}	false	5

Rule of thumb. On Postgres 14+, prefer SEARCH and CYCLE for any graph traversal — cleaner code, fewer bugs, and often a better plan. On other dialects, hand-code the path array and predicate. The mental model is identical.

Senior interview question on graph traversal

A senior interviewer might ask: "Given a directed graph edges table, write a recursive CTE that finds the shortest path between two specific nodes, protects against cycles, and returns the path as an array. Walk me through how it works and where it can go wrong."

Solution Using a path-tracking recursive CTE + MIN aggregation

WITH RECURSIVE paths AS (
    SELECT :start_id AS node_id, ARRAY[:start_id]::int[] AS path, 0 AS hop
    UNION ALL
    SELECT e.dst,
           p.path || e.dst,
           p.hop + 1
    FROM paths p
    JOIN edges e ON p.node_id = e.src
    WHERE NOT e.dst = ANY(p.path)              -- cycle guard
      AND p.hop < 20                            -- depth cap for safety
)
SELECT path, hop
FROM paths
WHERE node_id = :target_id
ORDER BY hop
LIMIT 1;

Step-by-step trace.

Given edges = {(1,2), (1,3), (2,4), (3,4), (4,5), (2,5)}, :start_id = 1, :target_id = 5:

Iteration	Frontier	Emitted rows
0 (anchor)	—	(1, [1], 0)
1	{1}	(2, [1,2], 1), (3, [1,3], 1)
2	{2, 3}	(4, [1,2,4], 2), (5, [1,2,5], 2), (4, [1,3,4], 2)
3	{4, 4, 5}	(5, [1,2,4,5], 3), (5, [1,3,4,5], 3)
4	{5, 5}	none (5 has no outgoing)
5	zero rows → terminate

Outer query WHERE node_id = 5 ORDER BY hop LIMIT 1 returns ([1, 2, 5], 2).

Output:

path	hop
{1, 2, 5}	2

Why this works — concept by concept:

• Path array as memory — the recursive CTE has no other place to record "which nodes have I already visited on this branch." The path array is per-row, not per-CTE, so parallel branches keep independent memory.
• Cycle guard as pre-emit filter — WHERE NOT e.dst = ANY(p.path) runs before the row is emitted. That way, we never insert a cycle-closing row, so the recursive term drains naturally.
• Depth cap as belt-and-braces — AND p.hop < 20 is a safety net for graphs with unexpectedly long paths or subtle bugs in the cycle guard. Never rely on the dialect's max-recursion — engineer termination.
• ORDER BY hop LIMIT 1 for shortest — the recursive CTE enumerates every path; the outer aggregate picks the minimum. Correct but not efficient — for high-QPS shortest-path queries, use a graph DB.
• Cost — for a graph with average branching factor b and depth cap d, worst-case is O(b^d). Path arrays and cycle guards keep it near O(edges) in practice, but skewed graphs can blow up. For millions of edges, move to a graph DB.

SQL
Topic — graph
Graph traversal problems

Practice →

SQL Topic — recursion Recursion practice problems

Practice →

---

5. Bill-of-materials and dialect quirks

bill of materials sql rolls up child quantities into parent quantities, multiplying along every edge — and every dialect has its own max-recursion cap

The mental model in one line: a multi-level BOM is a DAG where each parent points to child components with a per-edge quantity weight; the recursive CTE anchors on the top-level product, joins children in the recursive term, multiplies accumulated_qty = parent_accumulated × edge_qty, and terminates when a component has no further sub-components; every dialect has its own default cap on recursion depth (Postgres effectively unbounded, MySQL 1000, SQL Server 100, Snowflake unbounded, BigQuery 500). Once you internalise "multiply along the edge, sum at the leaf," every bill of materials sql interview surface collapses to a template.

The BOM data model.

• bom(parent_id, child_id, qty) — a "child_id appears qty times inside parent_id."
• The graph is a DAG — a wheel appears in a bike and a scooter; there is no cycle by construction.
• Roll-up is the natural operation: "for a bike, how many spokes total?" — walk down, multiply along every edge.

The multiplication trick.

• Anchor: SELECT product_id, ARRAY[product_id] AS path, 1 AS accumulated_qty, 0 AS level FROM bom_top WHERE product_id = :root.
• Recursive term: SELECT b.child_id, cte.path || b.child_id, cte.accumulated_qty * b.qty, cte.level + 1 FROM bom b JOIN cte ON b.parent_id = cte.product_id.
• Termination: automatic — a leaf component has no bom rows as parent.

The rollup.

• The CTE enumerates every path from root to leaf, carrying the accumulated quantity.
• To answer "how much of each component in total," sum the accumulated quantity per component: SELECT component_id, SUM(accumulated_qty) FROM cte GROUP BY component_id.
• This handles the DAG shape: if a wheel appears in the bike and a wheel appears in the trailer (which is also inside the bike as a sub-assembly), summing at the outer query aggregates both occurrences.

Dialect max-recursion matrix.

Dialect	Default cap	Override
Postgres	effectively unbounded (stack depth)	SET LOCAL max_stack_depth = '4MB'
MySQL 8+	cte_max_recursion_depth = 1000	SET cte_max_recursion_depth = 5000
SQL Server	MAXRECURSION 100	OPTION (MAXRECURSION 5000) per query
Snowflake	effectively unbounded	none needed
BigQuery	500 iterations	none per-query; redesign
DuckDB	effectively unbounded	none needed

When the max recursion fires.

• The engine raises a specific error: MySQL says "Recursive query aborted after N iterations", SQL Server says "Maximum recursion depth exceeded", BigQuery says "Recursive query iteration limit reached."
• The error is a hard stop — no partial results. Wrap your CTE in a LIMIT on the outer query does not prevent recursion from running to the cap.
• The right fix depends on the shape:
  • Legitimate deep recursion — override the cap (SQL Server OPTION (MAXRECURSION 5000), MySQL SET cte_max_recursion_depth = 5000).
  • Infinite loop — the recursive term never returns zero rows; find the bug (missing termination, missing cycle guard).
  • BigQuery hard 500 cap — pre-flatten the closure with a materialised model.

When to switch to a graph database.

• Depth > 100 with millions of nodes. Recursive CTE cost grows with edges × depth. At depth > 100, a native graph engine's index-free adjacency wins by an order of magnitude.
• High-QPS shortest-path queries. Graph DBs (Neo4j, TigerGraph) are built for this; recursive CTEs enumerate all paths and pick min, which is O(paths) not O(edges).
• Frequent structural change plus deep queries. Materialised closure tables become a maintenance burden; graph DBs handle live updates natively.
• Path expressiveness matters. Cypher's MATCH (a)-[:KNOWS*1..3]-(b) is more readable than a recursive CTE for people who write graph queries daily.

Common interview probes on BOM.

• "How do you sum the total quantity of each raw material for a bike?" — recursive CTE + GROUP BY component_id, SUM(accumulated_qty).
• "What happens if a component appears in two sub-assemblies?" — the CTE emits two rows with the same component_id; the outer SUM adds them correctly.
• "What's the difference between MAXRECURSION in SQL Server and cte_max_recursion_depth in MySQL?" — same concept; different names. SQL Server is per-query hint; MySQL is a session variable.
• "When does a BOM query hit the recursion cap?" — very deep sub-assemblies (aerospace, complex electronics) or a buggy self-reference that never terminates.

Worked example — multi-level BOM rollup

Detailed explanation.

• The setup. A bom(parent_id, child_id, qty) table. A bike has 1 frame and 2 wheels. A frame has 3 aluminium bars and 8 steel bolts. A wheel has 1 rubber tyre and 32 spokes.
• The multiplication. Walking down, accumulated_qty is multiplied by each edge's qty. A spoke's accumulated qty is 1 (bike) × 2 (wheels per bike) × 32 (spokes per wheel) = 64.
• The output. For each component, the total quantity needed to build one bike.

Question. Given the BOM below, compute the total quantity of every raw material required to build 1 bike.

Input — bom.

parent_id	child_id	qty
bike	frame	1
bike	wheel	2
frame	aluminium_bar	3
frame	steel_bolt	8
wheel	rubber_tyre	1
wheel	spoke	32

Code.

WITH RECURSIVE rollup AS (
    -- anchor: the top-level product
    SELECT 'bike'::text AS component_id,
           1::bigint    AS accumulated_qty,
           0            AS level
    UNION ALL

    -- recursive: children of the frontier, quantity multiplied along the edge
    SELECT b.child_id,
           r.accumulated_qty * b.qty,
           r.level + 1
    FROM rollup r
    JOIN bom b ON r.component_id = b.parent_id
)
SELECT component_id,
       SUM(accumulated_qty) AS total_qty,
       MAX(level)           AS max_depth
FROM rollup
WHERE component_id != 'bike'      -- exclude the top-level product from the tally
GROUP BY component_id
ORDER BY total_qty DESC;

Step-by-step explanation.

1. Anchor. Emits ('bike', 1, 0). Frontier {bike}.
2. Recursive step 1. From bike: children frame (qty 1) and wheel (qty 2). Emits ('frame', 1*1 = 1, 1) and ('wheel', 1*2 = 2, 1). Frontier {frame, wheel}.
3. Recursive step 2. From frame: children aluminium_bar (qty 3) and steel_bolt (qty 8). Emits ('aluminium_bar', 1*3 = 3, 2) and ('steel_bolt', 1*8 = 8, 2). From wheel: children rubber_tyre (qty 1) and spoke (qty 32). Emits ('rubber_tyre', 2*1 = 2, 2) and ('spoke', 2*32 = 64, 2).
4. Recursive step 3. No leaf component has a bom row as parent → recursive term emits zero rows → CTE terminates.
5. Outer query. Groups by component_id, sums accumulated_qty. Every leaf has exactly one row here (DAG has no shared component), so the sum equals the accumulated. Filters out bike (the top-level product itself).

Output.

component_id	total_qty	max_depth
spoke	64	2
steel_bolt	8	2
aluminium_bar	3	2
wheel	2	1
rubber_tyre	2	2
frame	1	1

Rule of thumb. BOM rollup multiplies along every edge and sums at the outer query. The multiplication happens inside the recursive term (never after); the summing happens outside (never inside). Get this split right and every BOM question follows.

Worked example — dialect max-recursion overrides

Detailed explanation.

• Why the caps exist. Every dialect has an implicit safety cap to prevent runaway recursion from burning CPU forever. The cap is intentionally low so that a buggy CTE fails fast.
• When to override. Deep BOMs (aerospace: 30+ levels), deep organisational structures (multinationals: 20+), deep dataset lineage graphs. The default cap is not enough for these workloads.
• How to override per dialect. MySQL uses a session variable. SQL Server uses a per-query hint. Postgres has no explicit cap — you tune max_stack_depth at the server level. BigQuery has no per-query override — you must pre-flatten.

Question. Show the max-recursion override syntax in MySQL 8, SQL Server, and Postgres. What happens if the cap fires in each dialect?

Input.

(none — configuration syntax varies)

Code.

-- MySQL 8+ — session variable, applies to subsequent CTEs in this session
SET SESSION cte_max_recursion_depth = 5000;

WITH RECURSIVE deep AS (
    SELECT 1 AS n
    UNION ALL
    SELECT n + 1 FROM deep WHERE n < 2000
)
SELECT COUNT(*) FROM deep;

-- SQL Server — per-query hint, no session change needed
WITH deep AS (
    SELECT 1 AS n
    UNION ALL
    SELECT n + 1 FROM deep WHERE n < 2000
)
SELECT COUNT(*) FROM deep
OPTION (MAXRECURSION 5000);

-- Postgres — no explicit cap; tune server-level max_stack_depth if needed
-- (typically only needed for depth > 10K)
SET LOCAL max_stack_depth = '4MB';   -- session-scoped

WITH RECURSIVE deep AS (
    SELECT 1 AS n
    UNION ALL
    SELECT n + 1 FROM deep WHERE n < 2000
)
SELECT COUNT(*) FROM deep;

-- BigQuery — no per-query override; 500-iteration cap is hard
-- If depth > 500, pre-flatten with a materialised model

Step-by-step explanation.

1. MySQL. cte_max_recursion_depth is a session variable, default 1000. Setting it to 5000 lets deeper CTEs run. When the cap fires, MySQL errors with "Recursive query aborted after N iterations".
2. SQL Server. OPTION (MAXRECURSION N) is a per-query hint appended to the outer SELECT. Default 100. MAXRECURSION 0 means unbounded (dangerous — use only when you have engineered termination in the recursive term). When the cap fires, SQL Server errors with "Maximum recursion depth of N has been exhausted before statement completion".
3. Postgres. No dedicated cap. Recursion is bounded by max_stack_depth (server-level, typically 2 MB) — you rarely need to touch this for reasonable CTEs. When stack overflow occurs, Postgres crashes the query (not the server) with "stack depth limit exceeded". In practice, Postgres CTEs recurse into the tens of thousands without issue.
4. BigQuery. 500 iterations, hard-coded. No override. If your workload needs deeper recursion, materialise a closure table incrementally via scheduled query or dbt.
5. General pattern. Always specify termination in the recursive term (WHERE n < bound, cycle guard). Rely on the dialect cap as a safety net, never as an intended stopping mechanism.

Output — configuration matrix.

Dialect	Default cap	Override syntax	Error message when fired
Postgres	stack (~10-100K)	SET max_stack_depth	"stack depth limit exceeded"
MySQL 8+	1 000	SET cte_max_recursion_depth = N	"Recursive query aborted after N iterations"
SQL Server	100	OPTION (MAXRECURSION N)	"Maximum recursion depth of N has been exhausted"
Snowflake	unbounded	—	(watch credit cost)
BigQuery	500	none per-query	"Recursive query iteration limit reached"
DuckDB	unbounded	—	(watch memory)

Rule of thumb. For deep BOMs or lineage graphs, override the cap and engineer termination in the recursive term. Never bump the cap to hide an infinite loop — fix the loop instead.

Worked example — when to switch to a graph database

Detailed explanation.

• The signal to switch. Deep + wide + high-QPS + frequent updates → the four ingredients that make recursive CTEs stop being the right answer.
• Depth alone is not enough. A 30-level BOM queried once a day runs fine on a recursive CTE. Add 500 QPS and the CPU becomes the bottleneck; add continuous updates and the closure-table approach becomes lossy.
• Where graph DBs win. Index-free adjacency (traversing an edge is O(1) instead of a B-tree lookup), path expressions ((a)-[:KNOWS*1..3]-(b) in Cypher), and native shortest-path algorithms.

Question. For a 50M-node dependency graph with continuous updates and 200 shortest-path queries per second, would you use recursive CTE, closure table, or graph DB? Justify.

Input.

Constraint	Value
Nodes	50 M
Edges	250 M
Update rate	1000 edge changes / sec
Query rate	200 shortest-path / sec
Depth range	1-15

Code.

Decision:
  - Recursive CTE at query time?
    ✗ 200 QPS × O(edges × depth) = CPU-bound; every query is 100-500 ms.

  - Closure table + nightly rebuild?
    ✗ 1000 updates / sec invalidates the closure faster than we can rebuild.
      Even an incremental maintainer would lag behind.

  - Graph DB (Neo4j / TigerGraph / Amazon Neptune)?
    ✓ Index-free adjacency: each hop is O(1).
    ✓ Native shortest-path algos (Dijkstra, A*) run in ms.
    ✓ Live updates handled natively; no closure-table catchup lag.
    ✓ Path expression is 1 line of Cypher, not 30 lines of SQL.

Verdict: graph DB. Migrate the graph out of the RDBMS; keep the OLTP tables that generate edges in Postgres, ETL edges into Neo4j via a Kafka topic.

Step-by-step explanation.

1. Recursive CTE at query time. Each query walks up to depth 15 with a fanout that could be hundreds of neighbours per hop. At 200 QPS, we need to serve 200 × O(edges × depth) queries per second. Even at 100 ms per query, that's 20 CPU-seconds per wallclock second — several dedicated CPUs, per node in the cluster.
2. Closure table + nightly rebuild. A closure table for 50M nodes with depth 15 could be tens of billions of rows. Rebuilding it once a day is expensive. And with 1000 updates/sec, the closure is stale seconds after the rebuild.
3. Closure table + incremental maintenance. An incremental closure maintainer runs on every edge change: for each new edge (u, v), find all rows (x, u) in the closure and add (x, v). Feasible for lower update rates; at 1000/sec, the maintainer becomes the bottleneck.
4. Graph DB. Native graph engines (Neo4j, TigerGraph, Amazon Neptune) store edges as pointers between node records — traversing an edge is one memory dereference, not a B-tree lookup. 200 QPS with depth-15 shortest-path is a normal load.
5. Migration path. Keep OLTP tables in Postgres. Emit every edge change to a Kafka topic. Consume in the graph DB. Serve reads from the graph DB. This is the standard pattern; it avoids rewriting the OLTP layer.

Output.

Approach	Feasibility
Recursive CTE at 200 QPS on 50M-node graph	✗ CPU-bound
Closure table + nightly rebuild	✗ stale within seconds
Closure table + incremental maintainer	✗ maintainer is the bottleneck
Graph DB with edge stream from Postgres	✓ scales; ms-latency reads

Rule of thumb. When any two of (depth > 20, nodes > 10M, QPS > 100, updates > 100/sec) hold at once, plan a graph DB migration. Recursive CTEs are the right hammer for shallow and low-QPS; deep and hot workloads need a different toolbox.

Senior interview question on end-to-end BOM roll-up

A senior interviewer might frame this as: "Design a BOM roll-up that supports multi-level assemblies, tolerates a 30-level max depth on a MySQL 8 instance, and reports total quantity plus maximum depth per raw component. Show the SQL, the dialect config, and the failure modes."

Solution Using a recursive CTE with dialect override and quantity multiplication

-- MySQL 8+ — session config for deep BOMs
SET SESSION cte_max_recursion_depth = 100;

WITH RECURSIVE rollup AS (
    SELECT :root_id AS component_id,
           1        AS accumulated_qty,
           0        AS level,
           CAST(:root_id AS CHAR(255)) AS path
    UNION ALL
    SELECT b.child_id,
           r.accumulated_qty * b.qty,
           r.level + 1,
           CONCAT(r.path, '>', b.child_id)
    FROM rollup r
    JOIN bom b ON r.component_id = b.parent_id
    WHERE r.level < 50                                        -- engineered safety cap
      AND FIND_IN_SET(b.child_id, REPLACE(r.path, '>', ',')) = 0   -- guard against accidental cycles
)
SELECT component_id,
       SUM(accumulated_qty) AS total_qty,
       MAX(level)           AS max_depth,
       COUNT(*)             AS occurrences
FROM rollup
WHERE component_id != :root_id
GROUP BY component_id
ORDER BY total_qty DESC;

Step-by-step trace.

Given a 3-level BOM (bike → frame → aluminium/steel; bike → wheel → rubber/spoke):

Iteration	Frontier	Emitted rows
0 (anchor)	—	(bike, 1, 0, 'bike')
1	{bike}	(frame, 1, 1, 'bike>frame'), (wheel, 2, 1, 'bike>wheel')
2	{frame, wheel}	(aluminium, 3, 2, ...), (steel, 8, 2, ...), (rubber, 2, 2, ...), (spoke, 64, 2, ...)
3	leaves	zero rows → terminate

Outer query aggregates: spoke → 64, steel → 8, aluminium → 3, wheel → 2, rubber → 2, frame → 1.

The FIND_IN_SET guard uses the string path (MySQL) to detect accidental cycles; the level < 50 cap is a belt-and-braces safety net well under the session's cte_max_recursion_depth.

Output:

component_id	total_qty	max_depth	occurrences
spoke	64	2	1
steel_bolt	8	2	1
aluminium_bar	3	2	1
wheel	2	1	1
rubber_tyre	2	2	1
frame	1	1	1

Why this works — concept by concept:

• Quantity multiplied inside the recursive term — accumulated_qty * b.qty runs on every recursive step. This is the entire point of BOM rollup; skipping it gives you a component list without amounts.
• Session config for MySQL cap — SET SESSION cte_max_recursion_depth = 100 bumps the MySQL default from 1000 down (or up) to a value that matches the workload. Sensible caps prevent runaway CTEs.
• Path column as cycle guard — even for BOMs (which are DAGs by design), the FIND_IN_SET guard catches accidental data-entry cycles that would otherwise cook the query. Cheap insurance.
• Engineered level cap — WHERE r.level < 50 gives you a predictable max depth that is independent of the dialect's implicit cap. If the workload's real depth is 30, the level cap is a safety net; if it fires unexpectedly, you know something is wrong before the dialect's error message surfaces.
• Cost — O(edges) per traversal since each edge is walked once. For a 100K-part BOM at depth 30, that's < 100ms on modern Postgres/MySQL/SQL Server. For BigQuery, the 500-iteration cap prevents very deep BOMs; use a materialised closure table instead.

SQL
Topic — CTE · hard
Hard recursive CTE problems

Practice →

SQL
Topic — SQL
SQL interview problem library

Practice →

---

Cheat sheet — recursive CTE recipes

• Minimum viable recursive CTE. WITH RECURSIVE cte AS (anchor SELECT UNION ALL recursive SELECT joining cte) SELECT ... FROM cte;. Two SELECTs, one UNION ALL, one termination condition. That is the whole shape.
• Running-numbers series generator. WITH RECURSIVE nums AS (SELECT 1 AS n UNION ALL SELECT n + 1 FROM nums WHERE n < :N) SELECT n FROM nums;. The "hello world" — sanity-check dialect support and syntax in 4 lines.
• Ancestors of a row. Anchor WHERE id = :leaf; recursive term JOIN employees e ON cte.manager_id = e.id. Walks up until the root's manager_id IS NULL.
• All descendants of a row. Anchor WHERE id = :root; recursive term JOIN employees e ON e.manager_id = cte.id. Add level + 1 and path || e.id for depth and ancestry.
• BFS from a start node. Anchor emits (start, 0, [start]). Recursive term joins edges to the frontier, filters NOT other = ANY(path), appends to path, increments hop. ORDER BY hop in the outer query.
• Cycle detection idiom. Carry a path array; filter WHERE NOT dst = ANY(path) on the recursive term. Explicit cycle reporting: emit is_cycle := dst = ANY(path) and filter in the outer query.
• Multi-level BOM rollup with quantity multiplication. Recursive term multiplies parent.accumulated_qty * edge.qty. Outer query groups by component and sums accumulated quantities.
• Postgres SEARCH clause. SEARCH DEPTH FIRST BY col SET seq or SEARCH BREADTH FIRST BY col SET seq. Adds a seq column that sorts DFS/BFS without hand-coding a path.
• Postgres CYCLE clause. CYCLE col SET is_cycle USING path. Auto-detects cycles, stops expanding cycle-flagged rows, exposes is_cycle and path columns.
• MySQL max-recursion override. SET SESSION cte_max_recursion_depth = 5000; before your CTE. Default is 1000. Session-scoped.
• SQL Server max-recursion override. OPTION (MAXRECURSION 5000) appended to the outer SELECT. Default is 100. Per-query. MAXRECURSION 0 is unbounded — dangerous.
• BigQuery hard cap. 500 iterations. No per-query override. Deep workloads must pre-flatten via materialised closure model.
• postgres recursive cte deep tuning. Postgres has no per-query cap; the practical limit is max_stack_depth. SET LOCAL max_stack_depth = '4MB' handles depths into the tens of thousands.
• When NOT to use a recursive CTE. Depth > 100 with high QPS → closure table or graph DB. Cyclic graph with shortest-path queries at scale → graph DB. Simple 2-level lookup → plain join, no recursion needed.
• Closure-table pattern. Rebuild once daily from a recursive CTE; store (ancestor_id, descendant_id, depth) with a composite PK. Reads become a single-index lookup.

Frequently asked questions

What is a SQL recursive CTE?

A sql recursive cte is a Common Table Expression that references itself in its own definition, enabling iterative traversal of hierarchies, trees, graphs, and multi-level structures without application-side loops. The shape is fixed: WITH RECURSIVE cte AS (anchor SELECT UNION ALL recursive SELECT joining cte) SELECT ... FROM cte. The anchor runs once and seeds the CTE with base rows; the recursive term joins the CTE to a base table and runs repeatedly until it emits zero rows. Every dialect except SQL Server (which infers recursion) requires the RECURSIVE keyword. Common uses: sql hierarchy query for org charts, graph traversal sql for friendship networks, bill of materials sql for multi-level assemblies, running-number series for date-range generation, and materialised closure-table rebuilds.

Does MySQL support recursive CTEs?

Yes — MySQL added first-class recursive CTE support in MySQL 8.0 (2018). The syntax is WITH RECURSIVE cte AS (anchor UNION ALL recursive_term) SELECT ..., identical to Postgres. Two MySQL-specific things to know: the default max recursion is cte_max_recursion_depth = 1000 (bump it with SET SESSION cte_max_recursion_depth = 5000 if your BOM or lineage graph exceeds 1000 levels), and MySQL does not have first-class SEARCH or CYCLE clauses like Postgres — you roll your own path array and FIND_IN_SET-style cycle guard using string paths (or JSON arrays on 8.0.17+). Older MySQL 5.7 and earlier do not support recursive CTEs — you either upgrade or fall back to application-side loops.

When should I use UNION ALL vs UNION in a recursive CTE?

Almost always UNION ALL. It preserves every row emitted by the recursive term, which is what you want. UNION (implicit SELECT DISTINCT) silently dedupes across generations, adding sort/hash overhead and hiding intent. The one place UNION sometimes "helps" is a cyclic graph where deduping accidentally terminates the recursion — but that is a happy accident, not an engineered termination. The correct fix for a cyclic graph is a cycle guard (path array + NOT node = ANY(path)), not UNION. Default to UNION ALL; reach for UNION only after measuring a specific dedup win and articulating exactly which duplicates you are dropping.

How do I detect cycles in a recursive CTE?

Accumulate a path array on every recursive step, then filter WHERE NOT next_node = ANY(path) before emitting. On Postgres, use array operators natively (ARRAY[node_id], path || node_id, = ANY). On MySQL, use CONCAT for a string path and FIND_IN_SET for the guard. On SQL Server, use CONCAT and a LIKE or a JSON array. Postgres 14+ ships a declarative CYCLE col SET is_cycle USING path clause that does all the bookkeeping for you and stops the recursion the moment a cycle is detected. Always add a cycle guard for anything with multi-parent or bidirectional edges, even if today's data is cycle-free — tomorrow's bug will insert one.

How do I compute the depth of every node in an org chart?

Anchor the recursive CTE on the root (WHERE manager_id IS NULL) with level = 0. In the recursive term, join employees e ON e.manager_id = cte.id and select cte.level + 1 as the new level. Termination is automatic — leaves have no children, so the frontier drains. To get depth-first traversal order, carry a path array (cte.path || e.id) and ORDER BY path in the outer query. Depth-first is what you want when rendering a tree in the UI; breadth-first (ORDER BY level, name) is what you want when reporting "all employees at level N." This is the canonical sql hierarchy query and it works identically across Postgres, MySQL 8+, SQL Server (drop the RECURSIVE keyword), Snowflake, BigQuery, and DuckDB.

What is the difference between a recursive CTE and a graph database query?

A recursive CTE runs inside your OLTP database against a normal table with a self-referential FK — no new system to operate, no ETL to maintain, and depth-≤-10 workloads are typically sub-second. A graph database (Neo4j, TigerGraph, Amazon Neptune) stores edges as native pointers between node records — traversing an edge is O(1) memory dereference rather than a B-tree lookup, path expressions like Cypher's (a)-[:KNOWS*1..3]-(b) are one line instead of thirty, and native shortest-path algorithms (Dijkstra, A*) run in milliseconds even on multi-million-node graphs. Reach for a recursive CTE for shallow depth (≤ 10) and moderate QPS (≤ 100), reach for a graph DB when two or more of "deep + wide + high-QPS + high-update-rate" hold at once. The postgres recursive cte covers 80% of production hierarchy and BOM workloads; the remaining 20% is where graph DBs earn their operational cost.

Practice on PipeCode

• Drill the CTE practice library → for the recursive-CTE shape, anchor + recursive-term probes, and dialect-specific overrides.
• Rehearse on hard-difficulty CTE problems → when the interviewer wants deep BOM rollups and multi-level ancestry queries.
• Sharpen tree traversal problems → for the org-chart / category-tree / filesystem family.
• Stack the graph problems library → for BFS, cycle detection, and shortest-path variants.
• Layer the recursion library → for anchor + recursive-step reasoning that shows up outside CTEs too.
• For general SQL sharpening, work through the SQL problem library →.
• Complement the CTE grind with the CTEs topic collection → for shorter warm-up drills.
• For the broader SQL interview surface, take the SQL for Data Engineering course →.

Pipecode.ai is Leetcode for Data Engineering — every recursive CTE recipe above ships with hands-on practice rooms where you write the anchor + recursive term, wire the cycle guard, and roll up a multi-level BOM against real graded inputs. PipeCode pairs every reading with 450+ DE-focused problems and a real-time scoring engine, so you never have to wonder whether your `sql recursive cte` answer holds up under a senior interviewer's depth probes.

Practice recursive CTEs now →
Graph traversal drills →