# Recursive Common Table Expressions: Graph Traversal Inside the Optimizer > Why recursive CTEs are the most under-used powerful feature in standard SQL, how they actually execute under the hood, and the failure modes that turn elegant queries into runaway memory consumers. --- ## TL;DR - A recursive CTE (`WITH RECURSIVE`) is fixed-point iteration inside a single SQL statement: an anchor member seeds a working table, then a recursive member runs against that working table over and over until it produces no new rows. - It turns graph and hierarchy work (tree walks, transitive closure, shortest paths, bill-of-materials explosion, sequence generation) into roughly 10 lines of declarative SQL that the database executes with its own joins, indexes, and planner. - The execution engine fixes the recursive member's plan once, at planning time, and reuses it every iteration. A plan that is fine for a 10-row working table can be disastrous when that table grows to 100,000 rows. - The three classic failure modes are cardinality explosion (use `UNION` to deduplicate, not `UNION ALL`), non-termination on cyclic data (track a path array or limit depth), and a missing index on the recursion join key. - Reach for an alternative (closure table, materialized path, a graph database, or application code) when the graph is dense, very deep, order-dependent, or traversed constantly. --- ## Table of Contents - [1. What a Recursive CTE Actually Is](#1-what-a-recursive-cte-actually-is) - [2. The Classical Examples](#2-the-classical-examples) - [2.1 Number Series Generation](#21-number-series-generation) - [2.2 Hierarchical Tree Walk](#22-hierarchical-tree-walk) - [2.3 Transitive Closure (Graph Reachability)](#23-transitive-closure-graph-reachability) - [2.4 Shortest Path](#24-shortest-path) - [3. Execution Internals: How PostgreSQL Actually Runs This](#3-execution-internals-how-postgresql-actually-runs-this) - [3.1 The Optimizer Cannot See Through Recursion](#31-the-optimizer-cannot-see-through-recursion) - [3.2 PostgreSQL vs. SQL Server vs. MySQL vs. Oracle](#32-postgresql-vs-sql-server-vs-mysql-vs-oracle) - [4. The Three Performance Pitfalls](#4-the-three-performance-pitfalls) - [4.1 Cardinality Explosion](#41-cardinality-explosion) - [4.2 The Working Table That Never Shrinks](#42-the-working-table-that-never-shrinks) - [4.3 Missing Indexes on the Recursion Join](#43-missing-indexes-on-the-recursion-join) - [5. Cycle Detection: The Real-World Necessity](#5-cycle-detection-the-real-world-necessity) - [5.1 Path Tracking](#51-path-tracking) - [5.2 SQL:1999 CYCLE Clause](#52-sql1999-cycle-clause) - [5.3 Depth Limiting](#53-depth-limiting) - [6. Beyond Hierarchies: Less Obvious Use Cases](#6-beyond-hierarchies-less-obvious-use-cases) - [6.1 Range Generation and Time Series](#61-range-generation-and-time-series) - [6.2 Running Totals That SQL Window Functions Cannot Express](#62-running-totals-that-sql-window-functions-cannot-express) - [6.3 Permission and Capability Inheritance](#63-permission-and-capability-inheritance) - [6.4 Bill-of-Materials Explosion](#64-bill-of-materials-explosion) - [7. Comparison with Alternative Approaches](#7-comparison-with-alternative-approaches) - [7.1 Stored Procedures with Loops](#71-stored-procedures-with-loops) - [7.2 Application-Level Recursion](#72-application-level-recursion) - [7.3 Materialized Path / Nested Set](#73-materialized-path--nested-set) - [7.4 Closure Tables](#74-closure-tables) - [8. Operational Concerns](#8-operational-concerns) - [8.1 Memory Consumption](#81-memory-consumption) - [8.2 Timeout and Statement Killing](#82-timeout-and-statement-killing) - [8.3 Replication Considerations](#83-replication-considerations) - [8.4 Explain Analyze Reading](#84-explain-analyze-reading) - [9. When NOT to Use Recursive CTEs](#9-when-not-to-use-recursive-ctes) - [10. The Senior Engineer's Mental Model](#10-the-senior-engineers-mental-model) - [11. References](#11-references) --- ## 1. What a Recursive CTE Actually Is A Common Table Expression (CTE) is a named subquery scoped to a single statement, introduced by SQL:1999 and now supported in every serious relational database. A *recursive* CTE is a CTE that refers to itself, producing iterative computation inside a single SQL statement: graph traversals, hierarchy walks, sequence generation, and transitive closure, all expressible without leaving the relational model. The canonical form: ```sql WITH RECURSIVE t(...) AS ( -- anchor (non-recursive) member SELECT ... UNION [ALL] -- recursive member: references t SELECT ... FROM t JOIN ... WHERE ... ) SELECT * FROM t; ``` Mechanically, the execution model is: 1. Evaluate the **anchor** member; its rows become the initial *working table* and are also appended to the *result table*. 2. Evaluate the **recursive** member against the working table; the resulting rows become the new working table and are appended to the result table. 3. Repeat step 2 until the working table is empty. 4. Return the result table. This is a fixed-point iteration. The recursion terminates when an iteration produces no new rows. If it never does, the query runs forever (or until the database imposes a recursion-depth limit: `max_recursive_iterations` in MySQL 8, no built-in limit in PostgreSQL). ```mermaid flowchart TD Start([Begin recursive CTE]) Anchor[Evaluate anchor member] Anchor --> InitWT[Working table = anchor rows
Result table = anchor rows] InitWT --> Check{Working table empty?} Check -- yes --> Done([Return result table]) Check -- no --> Recur[Evaluate recursive member
using working table] Recur --> NewWT[New rows become next working table
append to result table] NewWT --> Check style Start fill:#cef style Done fill:#bfb style Check fill:#fed ``` *Figure 1: The fixed-point execution model of a recursive CTE. The working table holds only the rows produced by the most recent iteration; the result table accumulates all rows produced so far.* The relational beauty: a graph traversal that would take 50 lines of imperative code (mutable visited set, queue, loop, deduplication) becomes 10 lines of SQL that the database executes with knowledge of the cardinality, the indexes, and the join planner. The catch: the iterative semantics conflict with SQL's set-oriented optimizer in subtle ways, and the abstraction leaks when the recursion depth or fan-out is not what the developer expected. --- ## 2. The Classical Examples ### 2.1 Number Series Generation The simplest recursive CTE, generating integers from 1 to N, illustrates the mechanics without the noise of joins: ```sql WITH RECURSIVE series(n) AS ( SELECT 1 UNION ALL SELECT n + 1 FROM series WHERE n < 100 ) SELECT n FROM series; ``` Anchor: `SELECT 1` produces one row. First iteration: `SELECT n + 1 FROM series WHERE n < 100` evaluates against the working table {(1)}, producing {(2)}. Working table becomes {(2)}; result table is {(1), (2)}. Second iteration: working table {(2)} produces {(3)}. Continues until iteration produces no rows (when n reaches 100, the WHERE filter eliminates it). Total: 100 rows. This pattern is invaluable for filling date gaps, generating calendar dimensions, or any "I need N rows" requirement. ### 2.2 Hierarchical Tree Walk The use case recursive CTEs were invented for: an adjacency-list table where each row references its parent. ```sql WITH RECURSIVE descendants AS ( SELECT id, parent_id, name, 0 AS depth, ARRAY[id] AS path FROM categories WHERE id = :root_id UNION ALL SELECT c.id, c.parent_id, c.name, d.depth + 1, d.path || c.id FROM categories c JOIN descendants d ON c.parent_id = d.id WHERE NOT c.id = ANY(d.path) -- cycle prevention ) SELECT * FROM descendants ORDER BY depth, id; ``` Anchor: the root. Recursive member: every child of any node in the current working table. The `path` array records the ancestry; the `NOT c.id = ANY(d.path)` cycle guard prevents infinite recursion if the data has cycles (which should never happen in a tree, but does happen in production data). For a balanced binary tree of 1 million nodes, the depth is `log_2(10^6)`, roughly 20. The total work is bounded by the result-set size (the entire subtree), and at each depth the optimizer can use a `(parent_id)` index on the categories table to do an efficient nested-loop join. ### 2.3 Transitive Closure (Graph Reachability) "Which nodes are reachable from node X?" is the canonical graph problem, and the canonical recursive CTE: ```sql WITH RECURSIVE reachable AS ( SELECT :start_node AS node UNION SELECT e.dst FROM reachable r JOIN edges e ON e.src = r.node ) SELECT node FROM reachable; ``` Note `UNION` (without ALL) instead of `UNION ALL`. `UNION` deduplicates: a node already in `reachable` is not added again. This both gives correct semantics (we want each reachable node once) and bounds the recursion (eventually all reachable nodes are in the set, the recursive member produces only already-seen rows, they are filtered out, and the next iteration produces an empty working table, terminating the loop). Without the `UNION` deduplication, a graph with any cycle would loop forever. With it, the worst case for the recursion depth is the graph diameter (longest shortest path), and the total result-set size is the number of reachable nodes. ### 2.4 Shortest Path A recursive CTE can compute shortest paths through Dijkstra-like iteration: ```sql WITH RECURSIVE shortest(node, distance, path) AS ( SELECT :start, 0, ARRAY[:start] UNION ALL SELECT e.dst, s.distance + e.weight, s.path || e.dst FROM shortest s JOIN edges e ON e.src = s.node WHERE NOT e.dst = ANY(s.path) ) SELECT node, MIN(distance) AS shortest_distance FROM shortest GROUP BY node; ``` This is BFS-with-paths, computing every simple path from the start node and aggregating to find the minimum. It is *not* algorithmically optimal (it explores exponentially many paths in a dense graph), but for sparse graphs (typical organizational hierarchies, family trees, file system trees), it works adequately and is dramatically simpler than implementing Dijkstra outside SQL. For dense graphs, the right tool is a graph database (Neo4j) or a specialized library (NetworkX, igraph), not a recursive CTE. Knowing where the recursive CTE stops being efficient is part of choosing it. --- ## 3. Execution Internals: How PostgreSQL Actually Runs This Understanding the execution is essential for predicting performance. PostgreSQL implements recursive CTEs via a `WorkTable Scan` node and a `Recursive Union` node: ``` Recursive Union |-- Anchor query (executed once) `-- Recursive query `-- WorkTable Scan (the "working table", last iteration's output) ``` The `WorkTable Scan` is the magic: at each iteration, it materializes the previous iteration's results as the input for the recursive member. The recursive member's plan is fixed at planning time and executed identically each iteration. Critical observations: - **The recursive member's plan does not adapt across iterations.** If the working table is initially 10 rows and grows to 100,000, the same plan runs both times. A nested-loop join may be optimal initially and disastrous at scale. - **The working table is in-memory** (subject to `work_mem`). A recursion that produces millions of rows per iteration will overflow and spill to disk (or fail). - **The result table is also accumulated**, often into a tuplestore. The total memory footprint is roughly the sum of all iteration outputs. ### 3.1 The Optimizer Cannot See Through Recursion The optimizer plans the anchor and the recursive member separately. It has cardinality estimates for the anchor (from table statistics) but only a rough guess for the recursive member's cardinality per iteration, typically derived from the recursive member's selectivity multiplied by an assumed iteration count. The estimate is almost always wrong. This has practical consequences: - The query may use a nested-loop join when a hash join would be vastly better (because the optimizer underestimates how large the working table will grow). - The query may use a hash join when nested loop would be cheaper (the opposite case). - Predicate pushdown across the CTE boundary is limited, though both PostgreSQL 12+ and MySQL 8.0 have improved this. The senior engineer's response: `EXPLAIN ANALYZE` the recursive query, paying particular attention to the `WorkTable Scan` row counts at each iteration. If they grow exponentially, the recursion is going to explode. ### 3.2 PostgreSQL vs. SQL Server vs. MySQL vs. Oracle The standard's vocabulary is consistent (`WITH RECURSIVE`) but implementations differ: - **PostgreSQL:** `UNION` (deduplicating) and `UNION ALL` both work. CYCLE clause added in 14 for declarative cycle detection. - **SQL Server:** `UNION ALL` only in the recursive member (UNION is not allowed). Uses MAXRECURSION hint (default 100) to bound iterations. - **MySQL 8.0:** `UNION` and `UNION ALL` supported; depth limit via `cte_max_recursion_depth` (default 1000). - **Oracle:** Both `WITH RECURSIVE` (since 11.2) and the legacy `CONNECT BY` hierarchical syntax. CONNECT BY is more compact for trees but less expressive (no general recursion). - **DB2:** Among the first to implement recursive CTEs; full SQL-standard support. A senior engineer should be able to read all four dialects and translate between them: they are syntactically similar, but the failure modes (depth limits, cycle handling) differ. --- ## 4. The Three Performance Pitfalls ### 4.1 Cardinality Explosion The recursive member's row count per iteration can explode unexpectedly. Consider a "find all employees in the org reporting up to me, and all their direct reports' direct reports" query on a typical org chart: a VP with 5,000 reports through 4 levels has roughly 5,000 nodes in the result. But if the recursion explores all *paths* rather than all *nodes* (using `UNION ALL` without deduplication), the count is the number of distinct paths, which in a graph with cycles or multiple paths can be exponentially larger than the node count. The classical example: a manufacturing bill-of-materials graph where part A uses part B and part C, both of which use part D. Path-enumerating recursion counts D twice. For a deep graph with many shared sub-components, paths explode geometrically. The fix: use `UNION` (deduplicating) when you want distinct nodes; use `UNION ALL` only when paths matter and you have bounded the search. ### 4.2 The Working Table That Never Shrinks The recursion terminates when the working table is empty. If the recursive member always produces at least one row, the recursion runs forever. ```sql -- BUG: never terminates if there are cycles WITH RECURSIVE walk AS ( SELECT :start AS node UNION ALL SELECT e.dst FROM walk JOIN edges e ON e.src = walk.node ) SELECT * FROM walk; ``` If the graph has a cycle, the working table keeps producing the same nodes over and over, and the recursion never terminates. Even with `UNION` (deduplicating), if the deduplication is by a column that varies, such as a `path` array that grows each iteration, every iteration produces "new" rows and termination depends on cycle detection in the WHERE clause. The defensive pattern: - Always use `UNION` rather than `UNION ALL` unless you need duplicates. - Always track a path or use a maximum-depth WHERE clause. - Always test with malformed (cyclic) input. ### 4.3 Missing Indexes on the Recursion Join The recursive member typically joins `working_table` to a base table on some key. If that key is not indexed in the base table, each iteration performs a sequential scan of the base table for every row in the working table. For a working table of size *k* and base table of size *N*, that is `O(k * N)` per iteration. With iterations, the total can dwarf the result-set size. The fix: ensure an index on the join key. For the `descendants` example, an index on `categories(parent_id)` is essential. Without it, even a 10,000-node tree can take minutes. --- ## 5. Cycle Detection: The Real-World Necessity Real-world graph data has cycles. Family trees have step-parent relationships that create cycles. Org charts have dotted-line reports that loop. Even "obviously acyclic" data, such as a category tree built from a UI, can develop cycles from data-entry bugs or migration errors. A recursive CTE that does not handle cycles is a production outage waiting to happen. The two standard techniques: ### 5.1 Path Tracking The most robust approach: maintain an array of visited nodes and exclude any node already in the path. ```sql WITH RECURSIVE walk AS ( SELECT id, parent_id, ARRAY[id] AS path FROM nodes WHERE id = :start UNION ALL SELECT n.id, n.parent_id, w.path || n.id FROM walk w JOIN nodes n ON n.parent_id = w.id WHERE NOT n.id = ANY(w.path) -- cycle guard ) SELECT * FROM walk; ``` The cost: the path array grows on every iteration, increasing the row size and the join-comparison cost. For very deep recursion (hundreds of levels), this becomes noticeable. ### 5.2 SQL:1999 CYCLE Clause Standard SQL provides a declarative `CYCLE` clause for cycle detection: ```sql WITH RECURSIVE walk(id, parent_id) AS ( SELECT id, parent_id FROM nodes WHERE id = :start UNION ALL SELECT n.id, n.parent_id FROM walk w JOIN nodes n ON n.parent_id = w.id ) CYCLE id SET is_cycle USING cycle_path SELECT * FROM walk WHERE NOT is_cycle; ``` PostgreSQL 14+ implements this. The CYCLE clause asks the engine to track cycles for you, exposing two columns (`is_cycle` and the path). The engine's implementation is the same path-tracking under the hood; the syntax just hides it. ### 5.3 Depth Limiting When you know the maximum reasonable depth (e.g., an org chart should not exceed 20 levels), enforce it in the WHERE clause: ```sql WHERE depth < 20 ``` This is the cheapest cycle guard and the most pragmatic for hierarchies with known bounds. It does not detect cycles; it just bounds the damage. --- ## 6. Beyond Hierarchies: Less Obvious Use Cases ### 6.1 Range Generation and Time Series Generating one row per day in a date range: ```sql WITH RECURSIVE dates(d) AS ( SELECT DATE '2026-01-01' UNION ALL SELECT d + INTERVAL '1 day' FROM dates WHERE d < DATE '2026-12-31' ) SELECT d FROM dates; ``` PostgreSQL has `generate_series` for this specific case (much faster), but recursive CTEs work in databases without it. The technique generalizes to any sequence: business hours, settlement windows, sample points. ### 6.2 Running Totals That SQL Window Functions Cannot Express Modern SQL has window functions that handle most cumulative computations. But there are cases, particularly when the "cumulative" computation depends on the *value* of a prior row, not just its position, that require recursion: ```sql -- account balance after each transaction, computed recursively WITH RECURSIVE balance AS ( SELECT 1 AS seq, 0::numeric AS bal UNION ALL SELECT b.seq + 1, b.bal + t.amount FROM balance b JOIN transactions t ON t.seq = b.seq + 1 ) SELECT * FROM balance; ``` A window function `SUM(amount) OVER (ORDER BY seq)` is faster and clearer for this specific case. The recursive form is needed when the per-row computation is non-associative or path-dependent (e.g., a balance that applies a fee whenever it crosses zero). ### 6.3 Permission and Capability Inheritance Role-based access control with inherited permissions: a user's effective permissions are the union of their direct permissions and the permissions of every role they inherit, transitively. ```sql WITH RECURSIVE inherited_roles AS ( SELECT role_id FROM user_roles WHERE user_id = :uid UNION SELECT ir.parent_role_id FROM inherited_roles iro JOIN inheritance ir ON ir.child_role_id = iro.role_id ) SELECT DISTINCT p.permission FROM inherited_roles ir JOIN role_permissions rp ON rp.role_id = ir.role_id JOIN permissions p ON p.id = rp.permission_id; ``` A graph-traversal problem expressed concisely as recursion. The alternative, materializing the closure in a separate table, is faster at read time but requires maintenance triggers and storage. ### 6.4 Bill-of-Materials Explosion The classical manufacturing problem: given a top-level product, find all components, all components of components, etc., with quantities: ```sql WITH RECURSIVE bom AS ( SELECT product_id, component_id, quantity, 1 AS level FROM product_components WHERE product_id = :top_product UNION ALL SELECT pc.product_id, pc.component_id, b.quantity * pc.quantity, b.level + 1 FROM bom b JOIN product_components pc ON pc.product_id = b.component_id ) SELECT component_id, SUM(quantity) AS total_quantity FROM bom GROUP BY component_id; ``` Note the multiplication: each level scales by the parent's quantity. This is the canonical example of why recursive CTEs are not just for tree-walks but for arbitrary "compute this for each level of decomposition" problems. --- ## 7. Comparison with Alternative Approaches ### 7.1 Stored Procedures with Loops ```plsql DO $$ DECLARE visited INT[] = ARRAY[]::INT[]; queue INT[] = ARRAY[:start_node]; current INT; BEGIN WHILE array_length(queue, 1) > 0 LOOP current := queue[1]; queue := queue[2:]; IF NOT current = ANY(visited) THEN visited := visited || current; queue := queue || (SELECT array_agg(dst) FROM edges WHERE src = current); END IF; END LOOP; END $$; ``` Imperative loops can express anything but are slower than recursive CTEs because every iteration is interpreted PL/pgSQL, the query planner cannot optimize across iterations, and the in-memory data structures are PL types rather than tuplestores. Use stored procedures when the recursion structure cannot be expressed as a fixed-point iteration (e.g., when iteration order matters or when you need early termination conditions that depend on aggregate state). ### 7.2 Application-Level Recursion ```python def descendants(root_id): result = [] stack = [root_id] while stack: node = stack.pop() result.append(node) children = db.query("SELECT id FROM categories WHERE parent_id = ?", node) stack.extend(children) return result ``` This is the N+1 problem from a different angle. Each iteration of the application's loop is a separate query, with all the network-round-trip overhead. For a deep hierarchy, the application-level approach is 10-100x slower than the SQL recursive CTE. The exception: when the depth is bounded and small (e.g., 2 levels), the application-level approach is comparable and simpler. ### 7.3 Materialized Path / Nested Set For mostly-read tree data, *materialized path* (each row stores its full ancestor path as a string like `/1/5/22/`) or *nested set* (each row stores `(left, right)` integers defining its subtree range) trades write complexity for vastly faster reads. - **Materialized path:** the descendants query is `WHERE path LIKE '/1/5/22/%'`: index-friendly, no recursion needed. - **Nested set:** the descendants query is `WHERE left BETWEEN parent.left AND parent.right`: extremely fast, but every insert renumbers half the tree. These are right when reads vastly outnumber writes and the tree is shallow. For deep or write-heavy trees, the adjacency-list + recursive CTE remains the right choice. ```mermaid flowchart LR AL[Adjacency list
+ recursive CTE] MP[Materialized path] NS[Nested set] CL[Closure table] AL -. Read: O log N * depth
Write: O 1 .-> Use1[Read-heavy or write-heavy
general purpose] MP -. Read: O 1 with index
Write: O subtree on move .-> Use2[Read-heavy, shallow tree] NS -. Read: O 1 with index
Write: O N on insert .-> Use3[Read-only or rare writes] CL -. Read: O 1 join
Write: O depth per insert .-> Use4[Read-heavy, moderate writes] ``` *Figure 2: Tree storage strategies, their query characteristics, and when each is appropriate.* ### 7.4 Closure Tables A *closure table* stores every ancestor-descendant pair explicitly. For a tree node *X* with ancestors *A1, A2, A3*, the closure table has rows `(A1, X)`, `(A2, X)`, `(A3, X)`, `(X, X)`. Descendant queries become a single JOIN. The cost: closure-table size is O(N * depth), and every insert/move requires updating multiple closure rows. Closure tables are the right choice for trees that change occasionally, are queried frequently for ancestors-or-descendants, and have bounded depth (so the closure table stays a reasonable size). --- ## 8. Operational Concerns ### 8.1 Memory Consumption The result table accumulates every row produced. For a recursion that visits 10 million rows, the database must hold 10 million rows in memory (or spill to `work_mem` and then disk). Set `work_mem` appropriately for the session running the recursion; default 4 MB will spill almost immediately. ### 8.2 Timeout and Statement Killing A runaway recursive CTE consumes CPU, memory, and possibly disk for as long as it runs. Set `statement_timeout` (PostgreSQL) for sessions that run recursive queries to bound the damage. For administrative queries, consider running them in a dedicated session that other queries do not share. ### 8.3 Replication Considerations A long-running recursive query on a streaming replica pins the snapshot and can cause replication lag if the primary is producing WAL faster than the replica can apply it. The `hot_standby_feedback` setting trades replication lag for queries-not-being-cancelled; both options have downsides. ### 8.4 Explain Analyze Reading ``` Recursive Union (cost=0.00..N rows=M) CTE Scan on cte -> Append -> Anchor query result -> Recursive query result -> WorkTable Scan on cte (cost=0.00..K rows=L) ``` What to look for: - The estimated row count vs. actual row count on the WorkTable Scan. Huge divergences indicate the optimizer's estimate is wrong, which means the join algorithm chosen may be suboptimal. - The number of loops on inner side of nested joins inside the recursive member. If this is large, an index is probably missing. - The total time vs. the time per iteration. Slow first iterations indicate the anchor query is slow; slow later iterations indicate the recursion is producing large working tables. --- ## 9. When NOT to Use Recursive CTEs Recursive CTEs are powerful but are not always the right tool: - **Very deep recursion (10,000+ levels):** The iteration overhead becomes significant. Consider materialized paths or graph databases. - **Dense graphs with high fan-out:** The result-table size explodes. Use a graph database (Neo4j, NebulaGraph) designed for traversals. - **Recursion order matters:** SQL recursive CTEs are set-oriented; the order of rows within an iteration is undefined. For ordered traversals (in-order tree walks), an application-level recursion is clearer. - **Cross-row state mutations:** The recursion is a *pure* fixed-point computation. If your "recursion" involves updating state that subsequent iterations depend on, you want a stored procedure or application-level code. - **Repeated traversal of the same data:** If you traverse the same hierarchy a thousand times per minute, denormalize via a closure table or materialized view. --- ## 10. The Senior Engineer's Mental Model A recursive CTE is fixed-point iteration over relations. Each iteration has access only to the *previous* iteration's output (the working table), not the entire history. Termination requires that some iteration produces an empty working table. Performance requires that each iteration's plan (fixed at planning time, applied identically every iteration) is well-chosen for the typical working-table size. The pitfalls (cardinality explosion, infinite recursion via cycles, missing indexes on join keys, optimizer mis-estimation) are the same pitfalls as any iterative graph algorithm written in any language; SQL just hides them behind elegant syntax. Knowing they exist is what distinguishes a senior who reaches for the recursive CTE confidently from one who has been bitten by a 4-hour bill-of-materials query that took down the production warehouse. Used well, recursive CTEs let the database do graph work that would otherwise require an external graph engine, with the joins, indexes, and concurrency primitives the database already has. Used poorly, they become the slowest 20 lines of SQL you have ever written. --- ## 11. References - ISO/IEC 9075-2:2016, *SQL, Part 2: Foundation (SQL/Foundation)*. The CYCLE clause and recursive CTE semantics are defined here. - PostgreSQL Documentation. *WITH Queries (Common Table Expressions)*. https://www.postgresql.org/docs/current/queries-with.html - Celko, Joe. *Joe Celko's Trees and Hierarchies in SQL for Smarties*, 2nd ed., Morgan Kaufmann, 2012. The comprehensive reference on hierarchy storage in SQL. - Karwin, Bill. *SQL Antipatterns*. Pragmatic Bookshelf, 2010. Chapters on naive trees and the case for closure tables. - Karwin, Bill. *Rendering Trees with Closure Tables*. https://karwin.com/blog/index.php/2010/03/24/rendering-trees-with-closure-tables/ - SQL Server Documentation. *WITH common_table_expression (Transact-SQL)*. https://learn.microsoft.com/sql/t-sql/queries/with-common-table-expression-transact-sql - Oracle Database SQL Language Reference. *SELECT (Recursive Subquery Factoring)*. https://docs.oracle.com/en/database/oracle/oracle-database/18/sqlrf/SELECT.html - ORACLE-BASE. *Recursive Subquery Factoring: Hierarchical Queries Using Recursive WITH Clauses*. https://oracle-base.com/articles/11g/recursive-subquery-factoring-11gr2 - MySQL Reference Manual. *WITH (Common Table Expressions)*. https://dev.mysql.com/doc/refman/8.0/en/with.html

Recursive Common Table Expressions: Why and When to use them