Recursive CTEs — Use recursive CTEs conceptually (intro) - SQL

SECTION 1

Historical Context & Motivation

Relational databases were born from Edgar F. Codd's 1970 paper on the relational model, but the original SQL specification lacked a critical ability: the power to express recursive queries. Early SQL could join tables, filter rows, and aggregate data, yet it could not naturally traverse tree-structured or graph-structured relationships — the kind of data that arises in organizational charts, bill-of-materials explosions, file-system paths, and network routing tables. Practitioners resorted to vendor-specific extensions, procedural loops in application code, or fixed-depth self-joins that assumed a maximum nesting level. These workarounds were fragile, non-portable, and intellectually unsatisfying because the underlying problem — computing the transitive closure of a relation — had been well understood in mathematical logic and graph theory for decades.

1970 • Codd's Relational Model

Edgar F. Codd publishes "A Relational Model of Data for Large Shared Data Banks," establishing the theoretical foundation for SQL. The model focuses on flat relations and does not address recursive querying.

1986 • SQL-86 Standard

The first ANSI SQL standard formalizes SELECT, INSERT, UPDATE, and DELETE, but offers no mechanism for recursive or hierarchical queries. Vendors like Oracle introduce proprietary syntax such as CONNECT BY to fill the gap.

1999 • SQL:1999 — Recursive CTEs

The SQL:1999 standard introduces Common Table Expressions (CTEs) with the WITH RECURSIVE clause, providing a vendor-neutral way to express recursive queries in declarative SQL.

2005–2012 • Widespread Engine Adoption

PostgreSQL (8.4, 2009), SQL Server (2005), SQLite (3.8.3, 2014), and MySQL (8.0, 2018) progressively add support for recursive CTEs, making the feature practically universal across major engines.

2020s • Graph & Hierarchical Workloads

Modern analytics increasingly model social graphs, supply chains, and knowledge graphs. Recursive CTEs remain a foundational tool, now complemented by SQL/PGQ (Property Graph Queries) proposals in SQL:2023.

The central question that recursive CTEs answer is deceptively simple: How can a single SQL statement repeatedly reference its own intermediate result until a termination condition is met? Understanding the conceptual model behind this mechanism is the focus of this lesson.

SECTION 2

Core Principles & Definitions

A Common Table Expression (CTE) is a named temporary result set defined inside a WITH clause, scoped to a single statement. A recursive CTE extends this idea by allowing the CTE to reference itself. The SQL engine evaluates the self-reference iteratively, feeding each iteration's output back as input for the next, until no new rows are produced (the fixed-point is reached). Grasping the interplay of three structural components — the anchor member, the recursive member, and the termination condition — is essential before writing any recursive query.

Anchor Member

The non-recursive SELECT that produces the initial row set — the seed from which all subsequent rows grow. It executes exactly once.

Recursive Member

A SELECT that joins the CTE's own name (the working table) with other tables or itself, producing new rows from the previous iteration's output.

UNION ALL Combiner

The anchor and recursive members are combined via UNION ALL (or UNION for de-duplication). Each iteration appends new rows to the cumulative result.

Termination Condition

Recursion halts when the recursive member returns an empty result set. Guard clauses — WHERE depth < N or engine-level MAXRECURSION — prevent infinite loops.

Fixed-Point Semantics

The engine repeats the recursive member until no new tuples are generated — the least fixed point of the recursive definition. This mirrors the evaluation strategy of Datalog programs.

✦

KEY TAKEAWAY

Think of a recursive CTE like a breadth-first search managed entirely by the database engine. The anchor member is the starting node you push onto the queue; the recursive member is the rule that discovers neighbors; and the UNION ALL accumulates every node you have visited. The process stops when the queue (working table) is empty — exactly the BFS termination condition you know from algorithms class.

SECTION 3

Visual Explanation — Execution Flow

The anchor member (top-left, cyan border) seeds the working table. The recursive member (top-right, violet border) reads the working table from the previous iteration and produces new rows. Each iteration's output is appended to the final result via UNION ALL. When the recursive member returns an empty set (green box, bottom-right), execution terminates.

The diagram above captures the two-phase loop that underpins every recursive CTE. During each iteration, only the newly produced rows from the previous pass populate the working table — not the entire accumulated result. This distinction is critical: the engine does not re-scan all previously found rows, which keeps the cost proportional to the number of new tuples per iteration rather than the total result size. Once the recursive member yields zero rows, the engine concatenates every iteration's contribution into the final output, which is then available to the outer SELECT statement.

SECTION 4

How It Works — Formal Structure

Although recursive CTEs are not typically described with algebraic equations, their evaluation semantics have a precise formal interpretation rooted in least-fixed-point computation from Datalog and logic programming. Understanding this framework clarifies why the SQL syntax looks the way it does and what guarantees the engine provides.

Canonical Syntax Template

RECURSIVE CTE TEMPLATE

WITH RECURSIVE cte_name (col₁, col₂, …) AS ( ⟨anchor_query⟩ UNION ALL ⟨recursive_query referencing cte_name⟩ ) SELECT … FROM cte_name;

cte_name — the alias the CTE uses to reference itself. anchor_query — base case; must not reference cte_name. recursive_query — inductive step; must reference cte_name at least once. UNION ALL appends rows without de-duplication (use UNION for implicit cycle detection via duplicate elimination).

Fixed-Point Evaluation Model

ITERATIVE EVALUATION

R₀ = Anchor(∅) Rᵢ₊₁ = Recursive(Rᵢ) Result = R₀ ∪ R₁ ∪ R₂ ∪ … ∪ Rₙ where Rₙ₊₁ = ∅

R₀ is the seed result from the anchor. Rᵢ₊₁ denotes the new rows produced when the recursive member reads Rᵢ. Iteration stops when Rₙ₊₁ is empty. The final result is the union of all intermediate sets.

⚠

MySQL Syntax Note

MySQL 8.0+ supports WITH RECURSIVE and requires the RECURSIVE keyword even when many other engines (PostgreSQL, SQL Server via WITH alone) do not mandate it. SQL Server uses OPTION (MAXRECURSION n) as a safety valve; PostgreSQL and SQLite do not impose a default limit but support cycle detection via CYCLE clause (SQL:2011).

Observe that the engine's strategy mirrors a classic worklist algorithm: maintain a set of items to process (the working table), apply a transformation (the recursive SELECT), collect the output, and repeat until convergence. This conceptual mapping is why recursive CTEs feel natural once you have studied BFS, iterative deepening, or transitive closure algorithms in a data structures course.

SECTION 5

Detailed Breakdown — Common Use Cases

Recursive CTEs unlock a family of query patterns that are impossible or impractical with flat SQL. The following diagram classifies the most common real-world scenarios, grouped by the nature of the data relationship involved.

The three major families of recursive CTE use cases — hierarchy traversal, series generation, and graph problems — all share the same anchor → recursive → terminate pattern shown at the bottom.

Use Case	Anchor Produces	Recursive Step	Terminates When
Org chart	Root employee (CEO)	Join employees on mgr_id = parent id	No more subordinates
Date series	Start date	Add INTERVAL '1 day'	`date > end_date`
Shortest path	Source node	Traverse edges, accumulate cost	All reachable nodes visited
Number sequence	1 (or desired start)	`n + 1`	`n >= max_value`

Common recursive CTE patterns with anchor, recursive step, and termination conditions

SECTION 6

Worked Example — Organizational Hierarchy

Suppose we have an employees table with columns id, name, and manager_id (a self-referencing foreign key — NULL for the CEO). Our goal is to list every employee along with their depth in the reporting hierarchy.

List All Employees with Hierarchy Depth

1
Step 1 — Define the Anchor

The anchor selects the root of the tree — the CEO, whose manager_id is NULL. We assign depth 0 as the starting level.

SELECT id, name, 0 AS depth FROM employees WHERE manager_id IS NULL
2
Step 2 — Define the Recursive Member

The recursive member joins the employees table with the CTE itself (named org). Each iteration finds employees whose manager_id matches an id in the current working table, and increments depth by 1.

SELECT e.id, e.name, org.depth + 1 FROM employees e INNER JOIN org ON e.manager_id = org.id
3
Step 3 — Combine with UNION ALL

We combine the anchor and recursive member using UNION ALL. Each iteration's new rows are appended without de-duplication because each employee appears exactly once in a proper tree structure.

WITH RECURSIVE org(id, name, depth) AS ( SELECT id, name, 0 FROM employees WHERE manager_id IS NULL UNION ALL SELECT e.id, e.name, org.depth + 1 FROM employees e JOIN org ON e.manager_id = org.id ) SELECT * FROM org ORDER BY depth, name;
4
Step 4 — Trace the Execution

Iteration 0: the anchor returns (1, 'Alice', 0) — the CEO. Iteration 1: the recursive member finds Alice's direct reports, e.g., (2, 'Bob', 1), (3, 'Carol', 1). Iteration 2: Bob's and Carol's reports are discovered at depth 2. The process continues until no new employees remain.

Final output: every row in the employees table, each annotated with its depth in the hierarchy.

SECTION 7

Strengths, Limitations & Pitfalls

Strengths	Limitations	Mitigation Strategies
Declarative — no procedural loops or application-side recursion needed	No guaranteed optimization; engines may materialize every iteration	Index the join column (e.g., manager_id) to accelerate each recursive pass
Standard SQL — portable across PostgreSQL, SQL Server, MySQL 8+, SQLite, Oracle	Infinite recursion risk if data contains cycles (directed graph with back-edges)	Add `WHERE depth < N` guard, or use `CYCLE` clause (SQL:2011)
Handles arbitrary-depth hierarchies without schema changes	Cannot express aggregation (GROUP BY) inside the recursive member in most engines	Perform aggregation in the outer SELECT that reads from the CTE
Composes well with window functions, JOINs, and subqueries in the outer query	Performance degrades on very deep or very wide recursions (millions of rows per iteration)	Consider materialized closure tables or graph databases for extreme workloads

Strengths and limitations of recursive CTEs with practical mitigation strategies

✦

KEY TAKEAWAY

Recursive CTEs occupy a sweet spot in the trade-off space: they are far more expressive than self-joins (which assume a fixed maximum depth) and far more portable than vendor-specific syntax like Oracle's CONNECT BY. However, they are not a replacement for specialized graph databases when your workload involves billions of edges or complex shortest-path algorithms with weighted priorities. Think of them as the relational world's general-purpose BFS/DFS engine — powerful for moderate-scale hierarchical and recursive problems, but not a dedicated graph processor.

SECTION 8

Connection to Advanced Topics

Recursive CTEs are the introductory gateway to several advanced database and computer science topics. Understanding where this concept leads will help you situate it within the broader landscape of query languages and data processing paradigms.

Recursive CTE (This Lesson)	Advanced Concept
Anchor + recursive member → fixed point	Datalog — a logic programming language where recursive rules are evaluated to a least fixed point; same formal semantics
`UNION ALL` accumulates all intermediate rows	Semi-naïve evaluation — an optimization that only computes truly new tuples each iteration, avoiding redundant work
Traverses parent→child edges to compute reachability	Graph query languages (SQL/PGQ, Cypher, SPARQL) — dedicated syntax for pattern matching and path traversal over property graphs and RDF
Depth column tracks iteration count	Closure tables / Nested sets — pre-materialized hierarchy representations that trade write-time cost for O(1) ancestor queries
Single-statement, set-at-a-time recursion	PL/pgSQL / T-SQL procedural loops — row-at-a-time imperative recursion; more flexible but harder to optimize

Mapping recursive CTEs to more advanced database and CS concepts

Looking forward, the SQL:2023 standard introduces SQL/PGQ (Property Graph Queries), which allows graph pattern matching directly over relational tables using a syntax inspired by Cypher. Recursive CTEs will remain the fallback for engines that do not yet support PGQ, and understanding their fixed-point semantics will make learning Datalog, SPARQL, or any logic-based query language significantly easier.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain in your own words why the anchor member of a recursive CTE must not reference the CTE's own name. What would happen conceptually if it did?

Show answer

The anchor member serves as the base case — it produces the seed rows that bootstrap the recursion. If the anchor referenced the CTE itself, the engine would face a chicken-and-egg problem: it needs results from the CTE to produce the first results of the CTE, creating a dependency cycle with no starting point. The SQL standard explicitly forbids self-reference in the anchor to guarantee that the iterative evaluation has a well-defined starting state (R₀ ≠ ∅). This mirrors the requirement in mathematical induction that the base case be independently provable.

Question 2: BASIC CALCULATION

Write a recursive CTE that generates the integers 1 through 10. Your query should output a single column named n.

Show answer

The anchor selects the value 1. The recursive member increments n by 1 and uses WHERE n < 10 as the termination guard. The complete query is: WITH RECURSIVE nums(n) AS (SELECT 1 UNION ALL SELECT n + 1 FROM nums WHERE n < 10) SELECT n FROM nums; The anchor produces {1}, iteration 1 produces {2}, and so on until the working table at iteration 10 yields {11}, which the WHERE clause filters out, resulting in an empty set that halts execution. The final UNION ALL of all iterations yields rows 1 through 10.

Question 3: INTERMEDIATE

Given a table categories(id INT, name TEXT, parent_id INT) representing a product category tree (root categories have parent_id = NULL), write a recursive CTE that returns each category's id, name, and full materialized path (e.g., 'Electronics > Computers > Laptops').

Show answer

The anchor selects root categories and initializes the path to their name alone. The recursive member concatenates the parent's path with ' > ' and the child's name.

WITH RECURSIVE cat_path(id, name, path) AS (SELECT id, name, CAST(name AS TEXT) FROM categories WHERE parent_id IS NULL UNION ALL SELECT c.id, c.name, cp.path || ' > ' || c.name FROM categories c JOIN cat_path cp ON c.parent_id = cp.id) SELECT id, name, path FROM cat_path ORDER BY path;

The key insight is that string concatenation in the recursive member builds the path incrementally. Each iteration extends paths by one level. The CAST ensures type compatibility across the UNION ALL. This pattern is directly applicable to file-system path construction, URL routing hierarchies, and taxonomy breadcrumbs.

Question 4: APPLIED

A social network stores friendships in a table friends(user_a INT, user_b INT) (symmetric: if (1,2) exists, (2,1) also exists). Write a recursive CTE that finds all users reachable from user 1 within 3 degrees of separation. Include a degree column and explain how you prevent infinite cycles.

Show answer

WITH RECURSIVE network(user_id, degree, visited_path) AS (SELECT 1, 0, ARRAY[1] UNION ALL SELECT f.user_b, n.degree + 1, n.visited_path || f.user_b FROM friends f JOIN network n ON f.user_a = n.user_id WHERE n.degree < 3 AND NOT f.user_b = ANY(n.visited_path)) SELECT DISTINCT user_id, MIN(degree) AS min_degree FROM network GROUP BY user_id ORDER BY min_degree;

Cycle prevention is handled by the visited_path array: before adding user_b to the next iteration, we check that the user is not already in the path via NOT f.user_b = ANY(n.visited_path). The WHERE n.degree < 3 guard provides a hard depth limit. The outer query uses DISTINCT and MIN(degree) because a user may be reachable via multiple paths. This pattern (PostgreSQL array-based cycle detection) is a practical alternative to the SQL:2011 CYCLE clause.

Question 5: CRITICAL THINKING

A colleague proposes replacing all recursive CTEs in your codebase with iterative application-level code (e.g., a Python while loop issuing repeated queries). Argue for or against this proposal. Consider correctness, performance, maintainability, and the conditions under which each approach is superior.

Show answer

Recursive CTEs execute entirely within the database engine, eliminating network round-trips between the application and the DBMS — each iteration of a Python loop would require a separate query, incurring latency and connection overhead proportional to the recursion depth. From a correctness standpoint, the CTE approach operates on a consistent snapshot (within a single statement's isolation level), whereas application loops may observe phantom reads between queries unless wrapped in an explicit serializable transaction. Maintainability favors CTEs because the recursive logic lives in a single, self-contained SQL statement rather than being split across procedural code and query templates. However, the application-level approach can be superior when: (1) the recursion requires complex control flow not expressible in SQL (e.g., dynamic pruning heuristics), (2) intermediate results must be processed by non-SQL libraries (ML inference, external API calls), or (3) the database engine's recursive CTE implementation is known to be inefficient for the specific workload (e.g., very deep recursion on MySQL). In general, prefer recursive CTEs for declarative tree/graph traversals within the DBMS, and reserve procedural recursion for cases that genuinely require imperative flexibility.

SUMMARY

Lesson Summary

Summary

A recursive CTE is a self-referencing Common Table Expression composed of an anchor member (base case) and a recursive member (inductive step), combined by UNION ALL. The SQL engine evaluates the recursive member iteratively, feeding each pass's output as the next pass's input, until the working table is empty — reaching the least fixed point. This mechanism enables hierarchy traversal (org charts, category trees), series generation (date and number sequences), and graph reachability queries — all in standard, portable SQL.

Key pitfalls include infinite recursion on cyclic data (mitigated by depth guards or the CYCLE clause) and performance degradation on very wide or deep recursions. Recursive CTEs share fixed-point semantics with Datalog and connect forward to SQL/PGQ, closure tables, and dedicated graph query languages. Mastering this concept equips you to solve a broad class of hierarchical and network problems without leaving the relational paradigm.