Recursive Queries: Navigating Trees & Graphs

Standard SQL is "horizontal"—it processes rows in batches. But what happens when a row in a table references another row in the same table?

• A manager who has employees, who are also managers.
• A folder that contains sub-folders, which contain files.
• A "Shortest Path" problem in a delivery network.

To solve these, you need Recursion. This flagship guide explores how the database engine handles "Self-Referential Logic" and how to architect high-fidelity graph traversals without collapsing into a stack overflow.

1. The Physics of the "Working Table"

Recursive CTEs look like magic, but they are powered by a very specific hardware process: the Working Table Iteration.

The Anatomy of the Loop

A recursive query consists of two parts linked by a UNION or UNION ALL:

1. The Anchor Member: This is the "Base Case." It's the starting point of your recursion (e.g., the CEO at the top of the tree).
2. The Recursive Member: This is the "Step Case." It's the query that joins the previous result back to the table to find the next level.

The Mirror of Execution

When you run WITH RECURSIVE, the engine creates two temporary tables in RAM:

• The Result Table: This stores the final output.
• The Working Table: This stores only the rows found in the last iteration.

The Loop Physics:

• The engine runs the Anchor and puts the results into both tables.
• It then runs the Recursive Member against the Working Table.
• It takes those new rows, puts them in the Result Table, and replaces the Working Table with them.
• It repeats this until the Working Table is empty.

The Architect's Lesson: The database never looks at the "Entire" result set during recursion; it only looks at the "Current Level." This is why recursion in SQL is surprisingly memory-efficient.

2. Real-World Hierarchy: The Organization Tree

Let's build a classic "Management Chain" report.

WITH RECURSIVE org_chart AS (
    -- Anchor: Find the CEO
    SELECT id, name, manager_id, 1 as level
    FROM employees
    WHERE manager_id IS NULL

    UNION ALL

    -- Recursive: Find everyone who reports to the previous level
    SELECT e.id, e.name, e.manager_id, oc.level + 1
    FROM employees e
- **The Architect's Rule**: In 99% of recursive queries, use `UNION ALL` to prevent the O(N log N) sort bottleneck.

---

## 2. Hardware-Mirror: The Working Set

How does the database physically run a recursive query? It uses an internal storage mechanism called the **Working Set**.

### The Physics of the Loop
1.  **Step 1**: The engine runs the Anchor and puts the results in the "Temporary Table."
2.  **Step 2**: It moves those results to the **Working Set**.
3.  **Step 3**: It runs the Recursive Term, using the Working Set as the input. The results are appended to the temporary table.
4.  **Step 4**: It replaces the Working Set with the results from the *previous* step and repeats until the Working Set is empty.

**Architect's Note**: Every step of the recursion consumes RAM. If your hierarchy is 10,000 levels deep, your database will hit a "Memory Wall." For massive graphs, consider using a dedicated Graph Database or limit your recursion depth.

### The RAM Wall: Working Set vs. Intermediate Table
As the recursion deepens, the database maintains two areas in memory:
1. **The Intermediate Table**: The total result set found so far.
2. **The Working Set**: Only the rows found in the *last* step (the "Active Frontier").
- **The Physics**: In every step, the engine joins the **Working Set** against the base table. This is why recursion is efficient; it doesn't re-join the whole history every time.
- **DANGER**: If your branch factor is high (e.g., every person has 500 friends), the Working Set can explode exponentially (1 -> 500 -> 250,000). This will lead to an out-of-memory (OOM) crash in seconds.

---

## 3. The "Death Loop" and Cycle Detection

The greatest danger in recursion is the **Cycle**. 
- User A is friends with User B.
- User B is friends with User C.
- User C is friends with User A.
Without protection, your query will run forever, eating 100% of your CPU until the server crashes.

### The Professional Fix: The CYCLE Clause
Modern PostgreSQL (v14+) provides a native `CYCLE` clause.
`CYCLE id SET is_cycle USING path`
- The database automatically tracks the `id` values it has seen. 
- If it sees the same `id` twice in the same path, it sets `is_cycle = true` and stops the recursion for that branch. This is the **Safety Valve** of graph theory.

---

## 4. Case Study: The "Social Degrees" Engine

A dating app wanted to show: *"You have 5 mutual friends with Sarah."* or *"Sarah is a 3rd-degree connection."*
**The Strategy**: A Recursive CTE that searches exactly 3 levels deep.

```sql
WITH RECURSIVE social_path AS (
    SELECT friend_id, 1 as degree
    FROM friendships WHERE user_id = 'ME'
    UNION ALL
    SELECT f.friend_id, s.degree + 1
    FROM friendships f
    INNER JOIN social_path s ON f.user_id = s.friend_id
    WHERE s.degree < 3 -- Strict limit to prevent performance explosion
)
SELECT DISTINCT friend_id FROM social_path;

The Result: By limiting the degree to 3, the database only has to scan a small branch of the network. Even with 10 million users, the "Third Degree" check returned in 12 milliseconds.

5. Alternative: Path-Based Hierarchies (LTREE)

5.1 Architecting Closure Tables: The High-Speed Alternative

If your tree is read-heavy and you need instant "Sub-tree" searches, Recursive CTEs might be too slow. Enter the Closure Table.

• The Architecture: You create a separate table category_relationships that stores every ancestor-descendant pair.
• The Physics: If Root has Child, and Child has Grandchild, the Closure Table stores:
  1. (Root, Child, 1)
  2. (Root, Grandchild, 2)
  3. (Child, Grandchild, 1)
• The Performance Mirror: To find all descendants of Root, you perform a single, indexed SELECT on the closure table (WHERE ancestor_id = Root). You have traded Disk Space (N^2 storage) for O(1) Search Latency. This is how Reddit handles million-comment threads with sub-millisecond load times.

6. Project War Room: The 10-Level Org Chart

Imagine a global enterprise with 500,000 employees. The CEO wants a report of the "Total Salary Weight" for every branch.

• The Recursive Approach: You use a CTE to sum salaries as you descend.
• The Performance Mirror: 1.5 seconds.
• The Optimization: You add Path Materialization. You store a /CEO/VP/Director/Manager/ string in each row.
• The Hardware Win: By using a GIST Index on the path, the 1.5-second recursive query becomes a 15ms index scan.
• The Lesson: Recursion is for logic; Materialization is for scale.

7. Summary: The Recursive Checklist

1. Anchor Fidelity: Ensure your anchor returns exactly the starting rows you need.
2. Breadth-First Default: Understand that you are processing levels, not branches, by default.
3. Depth Sentry: Always filter by depth to prevent runaways.
4. Closure Tables for Scale: If reading is 1,000x more frequent than writing, move your hierarchy to a Closure Table.
5. Index the Foreign Keys: Use B-Tree indexes on parent_id for recursive joins.

Recursive queries are the "High-Level Logic" of SQL. By mastering the movement of the working set and the safety of cycle detection, you gain the power to traverse complex human and machine networks with ease. You graduate from "Querying rows" to "Architecting Graphs."

Masterclass Recursion Checklist

• Implement Sovereign Cycle Detection: Use the CYCLE clause to prevent infinite loops.
• Audit Anchor Specificity: Ensure the starting query is as narrow as possible.
• Compare Recursive CTE performance vs. a Closure Table for a 5-level hierarchy.
• Advanced Goal: Build a "Shortest Path" finder for a simple delivery node network.

Read next: SQL Transactions: The ACID Concurrency Mirror →

Frequently Asked Questions

Q: How do I retrieve all descendants of a node in a hierarchical table using SQL?

Use a recursive CTE. The anchor selects the starting node; the recursive member joins back to the CTE to find children: WITH RECURSIVE tree AS (SELECT * FROM categories WHERE id = 1 UNION ALL SELECT c.* FROM categories c JOIN tree t ON c.parent_id = t.id) SELECT * FROM tree. This traverses the entire subtree regardless of depth. Add a depth counter column to the anchor (as 0) and increment it in the recursive member to know each node's level. Add a cycle detection check (WHERE id NOT IN (SELECT id FROM tree)) if your data might contain cycles.

Q: What is the adjacency list model and what are its trade-offs for storing trees?

The adjacency list model stores each node with a parent_id reference to its parent — simple to implement and update, but querying subtrees requires recursive CTEs or multiple self-joins. The nested set model stores left and right bounds encoding the tree structure, making subtree queries a simple range check but making insertions and moves expensive (many rows must be updated). The closure table model stores all ancestor-descendant pairs in a separate table, making both reads and writes efficient at the cost of storage. For most relational databases with recursive CTE support, the adjacency list model is the standard choice.

Q: What is the difference between depth-first and breadth-first traversal in a recursive CTE?

By default, recursive CTEs in PostgreSQL process rows in the order they are added to the working table — effectively breadth-first (all nodes at depth 1, then depth 2, etc.). To force depth-first ordering, use SEARCH DEPTH FIRST BY column SET order_column (PostgreSQL 14+), or simulate it by tracking a path array and sorting on it. Breadth-first is useful for level-by-level reports; depth-first is useful when you want to process a complete branch before moving to the next sibling, such as generating indented tree output.

Part of the SQL Mastery Course — engineering the paths.