A recursive Common Table Expression (CTE) in SQL allows you to traverse hierarchical data using a self-referencing query that executes in set-based fashion. The structure consists of an anchor member (the base case, typically root nodes where manager_id IS NULL) and a recursive member (the iterative part that joins the CTE back to itself on the parent-child relationship). The database engine repeatedly executes the recursive member until no new rows are returned, building the result set incrementally without explicit iteration constructs.
This approach leverages SQL's declarative nature, allowing the optimizer to choose efficient join algorithms (typically hash or merge joins) rather than the row-by-row processing inherent to CURSOR or WHILE loops. The syntax uses WITH RECURSIVE in PostgreSQL and MySQL, or simply WITH in SQL Server (where recursion is implicit), followed by the CTE name and column list.
A multinational corporation with 12,000 employees needed to generate complete reporting chains for SOX compliance audits. The existing system used a T-SQL CURSOR that iterated through each employee, recursively called a scalar function to find their manager, and built the hierarchy string by string. This process took 47 minutes to complete, held locks on the Employees table preventing HR updates during business hours, and frequently failed with stack overflow errors when processing deep hierarchies exceeding 100 levels (common in the engineering department's matrix structure).
Solution A: Optimized CURSOR with temp tables. The team considered rewriting the cursor to dump results into a temporary table first, then bulk inserting at the end. This would reduce locking time from 47 minutes to approximately 40 minutes. Pros: Minimal code changes, familiar pattern for the legacy team. Cons: Still row-by-row processing, still vulnerable to deep recursion stack overflows, merely mitigates rather than solves the performance issue.
Solution B: HierarchyID data type. Migrating the table to use SQL Server's native HierarchyID type, which stores tree positions as encoded paths optimized for traversal. Pros: O(1) subtree retrieval, built-in methods like GetAncestor() and GetDescendant(), extremely fast for read-heavy workloads. Cons: Requires massive schema migration (12,000 rows plus historical data), complex to maintain during reorganizations (updating a manager requires recalculating all descendant paths), vendor-locked to SQL Server while the company was considering PostgreSQL migration.
Solution C: Recursive CTE with cycle detection. Implementing a recursive CTE that joins the employee table to itself on manager_id, using a path array to track visited nodes to prevent infinite loops in case of circular references (which had occurred twice due to data entry errors). Pros: Pure ANSI SQL standard (portable to PostgreSQL during migration), set-based execution reduced runtime to 4 minutes 12 seconds, no table locks held during execution (uses snapshot isolation), handles arbitrary depth without stack overflow, detects data quality issues (cycles) automatically.
The team chose Solution C. The implementation used a recursive CTE with a path column accumulating employee IDs using PostgreSQL's array aggregation (or string concatenation in SQL Server), with a WHERE clause checking that the new manager_id did not exist in the accumulated path. The result was a 91% performance improvement, elimination of production locks, and early detection of circular reporting relationships that previously caused application crashes.
Why does a recursive CTE terminate, and what happens if the data contains a circular reference?
Candidates often believe recursive CTEs have built-in cycle detection, but standard SQL recursion terminates only when the recursive member returns zero new rows. If Employee A reports to B, B to C, and C back to A, the CTE runs infinitely (or until hitting implementation limits like SQL Server's default 100 recursion levels). The solution requires manual cycle detection by accumulating visited node IDs in a path column (using arrays or delimited strings) and filtering WHERE new_id != ALL(path_array). Modern PostgreSQL (14+) and SQL Server (2022+) support the standard SQL:1999 CYCLE clause: WITH RECURSIVE cte AS (...) CYCLE id SET is_cycle USING path, which automatically handles this.
How does the execution plan differ between a recursive CTE and a cursor-based approach, and why does it matter for concurrency?
Junior candidates often claim CTEs are "faster" without understanding the execution model. A CURSOR in SQL Server or PostgreSQL forces the engine to materialize a result set and iterate row-by-row, typically using a Keyset or Static cursor type that requires locks or tempdb resources for the duration of the iteration. This creates Shared Locks (or Update Locks) on the underlying tables for the entire 47-minute duration in the example above. Conversely, a recursive CTE is a single SELECT statement. Under Read Committed Snapshot Isolation (RCSI) or Snapshot Isolation, it reads a consistent point-in-time view of the data without holding locks, using version store instead. The optimizer typically chooses Nested Loop Joins for the recursive member with Index Seek operations on the parent-child index, making it O(n log n) rather than O(n²) for cursor approaches.
What is the difference between a recursive CTE and the Nested Sets Model for hierarchical data, and when would you choose one over the other?
Candidates frequently confuse traversal methods with storage models. A recursive CTE is a query-time traversal technique that works on Adjacency Lists (parent_id foreign keys). The Nested Sets Model (left/right values) is a storage design pattern that pre-calculates tree traversal paths. For write-heavy workloads (frequent manager changes), recursive CTEs on adjacency lists are superior because updating a single parent_id is O(1), whereas nested sets require O(n) updates to all right-values to the right of the moved node. For read-heavy, static hierarchies (org charts that change monthly), nested sets provide O(1) subtree retrieval (WHERE left BETWEEN parent.left AND parent.right) versus O(n) for recursive CTEs. A hybrid approach uses Closure Tables (separate table storing all ancestor-descendant pairs), which offers O(1) for both traversal and finding all children, at the cost of O(n²) storage and more complex maintenance. The choice depends on read/write ratio: use recursive CTEs when writes > 5% of operations; use nested sets or closure tables for predominantly static trees.