Graph Traversal in SQL: Recursive CTEs and Adjacency Lists for Network and Relationship Analysis

Introduction

You have an organizational chart stored in a database. The CEO sits at the top, VPs report to her, directors report to VPs, managers report to directors, and individual contributors report to managers. A simple enough structure — until your CEO asks you to answer a question that sounds trivial but isn't: "Who are all the people, at every level, who report up to Sarah Chen, the VP of Engineering?" You could write a series of nested joins, one for each level, but you don't know how many levels deep Sarah's organization goes. You could pull the entire table into Python and traverse it there, but that defeats the purpose of having a database. What you actually need is graph traversal, right inside SQL.

This is the problem that recursive CTEs were born to solve. Adjacency lists — tables where each row stores a node and its parent — are the most natural way to represent hierarchical and network data in relational databases. And recursive CTEs are the engine that lets you walk those structures up and down, find paths between nodes, compute depths, detect cycles, and aggregate values across entire branches of a tree. These aren't exotic techniques. They appear constantly in production systems: org charts, bill of materials, geographic hierarchies, social network friend-of-a-friend queries, category trees in e-commerce, and dependency graphs in build systems.

By the end of this lesson, you'll understand not just the syntax of recursive CTEs, but why they execute the way they do, where they break down, and how to engineer them for correctness and performance on real datasets. We'll work through progressively complex scenarios from basic hierarchy traversal to cycle detection to path reconstruction.

What you'll learn:

• How adjacency lists model graph relationships in SQL and when to use them versus alternative representations
• The exact execution model of recursive CTEs — what "recursion" really means at the engine level
• How to traverse hierarchies both top-down and bottom-up, with depth tracking and path construction
• How to detect and handle cycles in graph data safely
• Performance characteristics, indexing strategies, and the trade-offs that emerge at scale
• Advanced patterns including finding shortest paths, computing subtree aggregates, and working with network graphs (not just trees)

---

Prerequisites

You should be comfortable with:

• Standard CTEs (WITH clauses) and how they differ from subqueries
• JOINs including self-joins
• Window functions and aggregate functions
• Basic understanding of query execution plans (knowing what an index scan vs. sequential scan means)

This lesson uses PostgreSQL syntax throughout, with notes on where SQL Server, MySQL 8+, and SQLite diverge meaningfully.

---

Understanding the Adjacency List Model

Before you write a single recursive query, you need to understand what you're working with. The adjacency list is the simplest way to represent a graph in a relational table: each row contains a node identifier and the identifier of its parent (or neighbor, in an undirected graph).

Here's our working dataset — an employee hierarchy for a technology company:

CREATE TABLE employees (
    employee_id   INT PRIMARY KEY,
    name          VARCHAR(100) NOT NULL,
    title         VARCHAR(100),
    manager_id    INT REFERENCES employees(employee_id),
    department    VARCHAR(50),
    salary        NUMERIC(10,2)
);

INSERT INTO employees VALUES
  (1,  'Diana Okonkwo',   'CEO',                      NULL, 'Executive',    450000),
  (2,  'Sarah Chen',      'VP of Engineering',         1,   'Engineering',  280000),
  (3,  'Marcus Rivera',   'VP of Sales',               1,   'Sales',        260000),
  (4,  'Priya Patel',     'Director of Backend',       2,   'Engineering',  195000),
  (5,  'James Oduya',     'Director of Frontend',      2,   'Engineering',  190000),
  (6,  'Lena Nakamura',   'Director of Sales East',    3,   'Sales',        175000),
  (7,  'Tom Bauer',       'Director of Sales West',    3,   'Sales',        172000),
  (8,  'Aisha Grant',     'Senior Backend Engineer',   4,   'Engineering',  155000),
  (9,  'Ravi Menon',      'Senior Backend Engineer',   4,   'Engineering',  152000),
  (10, 'Sofia Alvarez',   'Frontend Engineer',         5,   'Engineering',  135000),
  (11, 'Dev Sharma',      'Frontend Engineer',         5,   'Engineering',  132000),
  (12, 'Claire Dubois',   'Account Executive',         6,   'Sales',        120000),
  (13, 'Noah Williams',   'Account Executive',         6,   'Sales',        118000),
  (14, 'Yuki Tanaka',     'Account Executive',         7,   'Sales',        117000),
  (15, 'Ben Osei',        'Sales Development Rep',     7,   'Sales',         95000);

The elegance here is also the challenge: manager_id is a foreign key that points back into the same table. This self-referential relationship is what makes the data a graph rather than a flat table. The CEO (employee_id = 1) has a NULL manager_id — she's the root of the tree.

Why Adjacency Lists? The Alternatives

You should know that adjacency lists are not the only way to store hierarchical data in SQL. The main alternatives are:

Nested sets store a left and right value for each node, where a node's entire subtree falls within its left-right range. Range queries (SELECT * FROM nodes WHERE left > 5 AND right < 20) are extremely fast, but insertions require rewriting half the table. These work well for read-heavy, infrequently-modified hierarchies.

Path enumeration stores the full path from root to each node as a string (e.g., '1/2/4/8'). Queries become simple string operations (WHERE path LIKE '1/2/%'), but path maintenance on updates is fragile.

Closure tables store every ancestor-descendant pair in a separate table. Queries are simple joins, inserts are O(depth), but storage grows quadratically with depth.

Adjacency lists win when your hierarchy changes frequently, when you need to traverse it in arbitrary directions, and when depth is variable. Their weakness is that you can't answer "give me all descendants" without recursion. That's exactly what we're here to fix.

---

How Recursive CTEs Actually Work

The syntax looks like recursion, but what's actually happening is iterative. Understanding this distinction is the difference between writing recursive CTEs confidently and writing them by cargo-cult.

Here's the canonical structure:

WITH RECURSIVE cte_name AS (
    -- Anchor member: the starting point (runs once)
    SELECT ...
    FROM ...
    WHERE ...  -- initial condition

    UNION ALL

    -- Recursive member: references cte_name itself
    SELECT ...
    FROM ...
    JOIN cte_name ON ...  -- joins back to previous iteration's results
)
SELECT * FROM cte_name;

What the engine actually does:

1. Execute the anchor member. Store the results in a working table (call it W).
2. Execute the recursive member, joining against W. Store the new rows produced in a temporary result table R.
3. Replace W with R.
4. Repeat step 2 until R is empty (no new rows were produced).
5. Return the union of all rows produced across all iterations.

This is called iterative computation with a fixed point. The "recursion" terminates not because of a base case like in functional recursion, but because eventually the join in the recursive member produces zero new rows. If your data has cycles and you don't guard against them, it never terminates — which is a very bad day.

The SQL standard specifies UNION ALL for this behavior (which keeps duplicate rows between iterations). You can use UNION (which deduplicates), but this incurs a significant performance cost and doesn't protect you from infinite loops the way you might hope — it prevents duplicates at the result level, not cycles in the traversal.

Critical note for SQL Server users: SQL Server supports recursive CTEs but enforces a default maximum recursion depth of 100. You can override it with OPTION (MAXRECURSION 0) (unlimited) or a specific number. PostgreSQL has no built-in limit but you can set enable_hashjoin and other parameters. MySQL 8+ defaults to a depth of 1000, configurable via cte_max_recursion_depth. Know your platform's defaults before deploying to production.

---

Your First Traversal: Top-Down Hierarchy

Let's start with the most common operation: given a starting node, find all descendants. We want to find everyone who reports, directly or indirectly, to Sarah Chen (employee_id = 2).

WITH RECURSIVE org_tree AS (
    -- Anchor: start with Sarah Chen herself
    SELECT
        employee_id,
        name,
        title,
        manager_id,
        0 AS depth
    FROM employees
    WHERE employee_id = 2

    UNION ALL

    -- Recursive: find direct reports of each row in org_tree
    SELECT
        e.employee_id,
        e.name,
        e.title,
        e.manager_id,
        ot.depth + 1
    FROM employees e
    JOIN org_tree ot ON e.manager_id = ot.employee_id
)
SELECT
    employee_id,
    REPEAT('  ', depth) || name AS indented_name,
    title,
    depth
FROM org_tree
ORDER BY depth, name;

 employee_id | indented_name                        | title                       | depth
-------------+--------------------------------------+-----------------------------+-------
           2 | Sarah Chen                           | VP of Engineering           |     0
           4 |   Priya Patel                        | Director of Backend         |     1
           5 |   James Oduya                        | Director of Frontend        |     1
           8 |     Aisha Grant                      | Senior Backend Engineer     |     2
           9 |     Ravi Menon                       | Senior Backend Engineer     |     2
          10 |     Sofia Alvarez                    | Frontend Engineer           |     2
          11 |     Dev Sharma                       | Frontend Engineer           |     2

Let's trace through what happened. Iteration 0 (anchor): Sarah Chen, depth 0. Iteration 1: join employees to org_tree where manager_id = 2 — finds Priya (4) and James (5), both at depth 1. Iteration 2: join employees to org_tree where manager_id IN (4, 5) — finds Aisha (8), Ravi (9), Sofia (10), Dev (11) at depth 2. Iteration 3: join employees to org_tree where manager_id IN (8, 9, 10, 11) — finds nobody, because none of these are managers. The recursion terminates.

The depth column is something you computed, not something stored in the table. This is one of the most useful patterns in recursive CTEs: carry forward computed metadata from iteration to iteration by including it as a column in your SELECT and incrementing it in the recursive member.

---

Path Tracking: Knowing How You Got There

Depth tells you how far from the root you are. Path tells you which route you took to get there. This matters for displaying breadcrumbs, debugging unexpected query results, and building the foundation for cycle detection.

WITH RECURSIVE org_tree AS (
    SELECT
        employee_id,
        name,
        manager_id,
        0 AS depth,
        ARRAY[employee_id] AS path,
        name::TEXT AS path_names
    FROM employees
    WHERE employee_id = 1  -- Start from the CEO

    UNION ALL

    SELECT
        e.employee_id,
        e.name,
        e.manager_id,
        ot.depth + 1,
        ot.path || e.employee_id,
        ot.path_names || ' -> ' || e.name
    FROM employees e
    JOIN org_tree ot ON e.manager_id = ot.employee_id
)
SELECT
    employee_id,
    name,
    depth,
    path,
    path_names
FROM org_tree
ORDER BY path;

 employee_id | name           | depth | path        | path_names
-------------+----------------+-------+-------------+------------------------------------------
           1 | Diana Okonkwo  |     0 | {1}         | Diana Okonkwo
           2 | Sarah Chen     |     1 | {1,2}       | Diana Okonkwo -> Sarah Chen
           3 | Marcus Rivera  |     1 | {1,3}       | Diana Okonkwo -> Marcus Rivera
           4 | Priya Patel    |     2 | {1,2,4}     | Diana Okonkwo -> Sarah Chen -> Priya Patel
          ...

The path column is an array (PostgreSQL syntax) built by appending the current node's ID with ||. The path_names column builds a human-readable version. The ARRAY[employee_id] in the anchor initializes a one-element array; each recursive step appends to it.

PostgreSQL-specific: The array concatenation with || is PostgreSQL syntax. In SQL Server, you'd use CAST(employee_id AS VARCHAR) + '/' and concatenate strings. In MySQL 8+, use CONCAT(path, ',', employee_id). The pattern is the same; the syntax differs.

---

Bottom-Up Traversal: Finding All Ancestors

The direction matters. Sometimes you don't want descendants — you want ancestors. "Given employee Ben Osei (15), what's his entire management chain up to the CEO?" This is the bottom-up traversal, and the only change is in the JOIN direction of the recursive member.

WITH RECURSIVE management_chain AS (
    -- Anchor: start with the target employee
    SELECT
        employee_id,
        name,
        title,
        manager_id,
        0 AS depth
    FROM employees
    WHERE employee_id = 15

    UNION ALL

    -- Recursive: find the manager of each current row
    SELECT
        e.employee_id,
        e.name,
        e.title,
        e.manager_id,
        mc.depth + 1
    FROM employees e
    JOIN management_chain mc ON e.employee_id = mc.manager_id
    --                          ^^^                ^^^
    --                          Note the JOIN is reversed
)
SELECT
    depth,
    employee_id,
    name,
    title
FROM management_chain
ORDER BY depth DESC;

 depth | employee_id | name           | title
-------+-------------+----------------+---------------------------
     3 |           1 | Diana Okonkwo  | CEO
     2 |           3 | Marcus Rivera  | VP of Sales
     1 |           7 | Tom Bauer      | Director of Sales West
     0 |          15 | Ben Osei       | Sales Development Rep

Notice the subtle reversal: in the top-down traversal, we joined on e.manager_id = ot.employee_id (find rows whose manager is in our current set). In the bottom-up traversal, we join on e.employee_id = mc.manager_id (find the row that is the manager of our current set). This is the fundamental toggle between descending and ascending in a hierarchy.

The depth DESC ordering in the output puts the CEO first, giving us the chain in natural reading order from top to bottom.

---

Subtree Aggregates: Rolling Up Numbers Through a Hierarchy

Here's where recursive CTEs unlock genuinely powerful business analysis. The question: "What is the total salary cost of each VP's entire organization, including everyone at all levels below them?"

This is a subtree aggregate, and it's non-trivial to compute without recursion. With it, we have two main approaches. The first — and usually better one — is to traverse once, collecting all members, then aggregate:

WITH RECURSIVE all_reports AS (
    SELECT
        employee_id,
        name,
        manager_id,
        salary,
        employee_id AS subtree_root  -- Track which root this member belongs to
    FROM employees
    WHERE manager_id IS NULL OR employee_id IN (
        SELECT employee_id FROM employees WHERE title LIKE 'VP%'
    )

    UNION ALL

    SELECT
        e.employee_id,
        e.name,
        e.manager_id,
        e.salary,
        ar.subtree_root
    FROM employees e
    JOIN all_reports ar ON e.manager_id = ar.employee_id
    WHERE ar.subtree_root != ar.employee_id  -- Don't traverse from non-VP roots
)

Actually, let me show you a cleaner approach: run a separate traversal for each VP, then union. Better still, use one traversal from the root and tag each row with its VP ancestor:

WITH RECURSIVE org_with_vp AS (
    -- Anchor: VPs themselves, tagged as their own VP ancestor
    SELECT
        employee_id,
        name,
        salary,
        manager_id,
        employee_id AS vp_ancestor_id,
        name AS vp_ancestor_name
    FROM employees
    WHERE title LIKE 'VP%'

    UNION ALL

    -- Recursive: everyone who reports into a VP subtree
    SELECT
        e.employee_id,
        e.name,
        e.salary,
        e.manager_id,
        ow.vp_ancestor_id,
        ow.vp_ancestor_name
    FROM employees e
    JOIN org_with_vp ow ON e.manager_id = ow.employee_id
)
SELECT
    vp_ancestor_id,
    vp_ancestor_name,
    COUNT(*) AS headcount,
    SUM(salary) AS total_salary_cost,
    ROUND(AVG(salary), 0) AS avg_salary
FROM org_with_vp
GROUP BY vp_ancestor_id, vp_ancestor_name
ORDER BY total_salary_cost DESC;

 vp_ancestor_id | vp_ancestor_name | headcount | total_salary_cost | avg_salary
----------------+------------------+-----------+-------------------+------------
              2 | Sarah Chen       |         6 |        1039000.00 |     173167
              3 | Marcus Rivera    |         6 |         797000.00 |     132833

The key technique here is the vp_ancestor_id column that gets passed down through every iteration of the recursion. The VP's own row initializes it to its own employee_id. Every descendant inherits it. After the CTE terminates, a simple GROUP BY gives you the rollup. This pattern — "carry a tag from the root, aggregate at the end" — is one of the most reusable patterns in hierarchical SQL.

---

Cycle Detection: When Your Graph Isn't a Tree

Everything above assumed a tree: each node has at most one parent, and there are no cycles. Real-world data is messier. Graphs have cycles. Data quality issues create them in supposedly hierarchical data (the person who is somehow their own skip-level manager, or circular category parent assignments). Running a recursive CTE on a cyclic graph without protection will run forever — or until your database kills the query.

Let's simulate a cycle to make this concrete:

-- Suppose we accidentally create a cycle: Sarah reports to Ben, who reports to Sarah
-- (This would normally be caught by a tree structure, but let's model an undirected graph)
CREATE TABLE network_connections (
    node_a INT,
    node_b INT,
    weight NUMERIC
);

INSERT INTO network_connections VALUES
  (1, 2, 1.0), (2, 3, 0.8), (3, 4, 1.2),
  (4, 5, 0.9), (2, 5, 2.1), (1, 5, 3.0),
  (3, 5, 0.7);

This is an undirected graph (each edge appears once). Without cycle protection, a traversal from node 1 would loop forever: 1 -> 2 -> 3 -> 4 -> 5 -> 3 -> 4 -> 5 -> ...

The solution is to track the path you've taken and refuse to visit a node you've already seen:

WITH RECURSIVE graph_traversal AS (
    -- Anchor: start at node 1
    SELECT
        node_b AS current_node,
        1 AS visited_from,
        ARRAY[1, node_b] AS visited_nodes,
        weight AS total_weight,
        1 AS hops
    FROM network_connections
    WHERE node_a = 1

    UNION ALL

    -- Recursive: traverse edges from current node, but don't revisit
    SELECT
        CASE WHEN nc.node_a = gt.current_node THEN nc.node_b ELSE nc.node_a END,
        gt.current_node,
        gt.visited_nodes || CASE WHEN nc.node_a = gt.current_node THEN nc.node_b ELSE nc.node_a END,
        gt.total_weight + nc.weight,
        gt.hops + 1
    FROM network_connections nc
    JOIN graph_traversal gt
      ON (nc.node_a = gt.current_node OR nc.node_b = gt.current_node)
    WHERE
        -- The cycle prevention: don't visit nodes already in our path
        NOT (CASE WHEN nc.node_a = gt.current_node THEN nc.node_b ELSE nc.node_a END = ANY(gt.visited_nodes))
        AND gt.hops < 10  -- Safety limit
)
SELECT
    current_node,
    visited_nodes AS path,
    total_weight,
    hops
FROM graph_traversal
ORDER BY hops, total_weight;

The two cycle prevention mechanisms here are:

1. Path-based visited check: NOT (next_node = ANY(visited_nodes)) — if the node we're about to visit is already in our path array, skip it. This is the gold standard because it prevents cycles regardless of graph structure.

2. Depth/hop limit: AND gt.hops < 10 — a safety net. Even if your cycle detection has a bug, the query terminates. In production, always include a depth limit.

Performance warning: The = ANY(array) check requires scanning the entire path array on each iteration. For shallow graphs this is fine, but for deep graphs with thousands of nodes, this check becomes expensive. An alternative for very large graphs is to maintain a separate visited table with a hash of visited nodes, but this requires procedural code (a stored procedure or a loop in application code) rather than pure SQL.

---

Finding Shortest Paths

A classic graph theory problem — and a practical one. In a network of data centers connected by fiber links, what's the minimum-latency path between two nodes? In a social network, what's the shortest chain of introductions between two people?

For unweighted graphs (shortest by hop count), BFS (breadth-first search) naturally falls out of a recursive CTE because we expand one level per iteration:

WITH RECURSIVE shortest_path AS (
    -- Anchor: start at source node
    SELECT
        node_b AS current_node,
        ARRAY[1, node_b] AS path,
        1 AS hops
    FROM network_connections
    WHERE node_a = 1  -- source

    UNION ALL

    SELECT
        CASE WHEN nc.node_a = sp.current_node THEN nc.node_b ELSE nc.node_a END,
        sp.path || CASE WHEN nc.node_a = sp.current_node THEN nc.node_b ELSE nc.node_a END,
        sp.hops + 1
    FROM network_connections nc
    JOIN shortest_path sp
      ON (nc.node_a = sp.current_node OR nc.node_b = sp.current_node)
    WHERE
        NOT (CASE WHEN nc.node_a = sp.current_node THEN nc.node_b ELSE nc.node_a END = ANY(sp.path))
)
SELECT path, hops
FROM shortest_path
WHERE current_node = 5  -- destination
ORDER BY hops
LIMIT 1;

   path    | hops
-----------+------
 {1,5}     |    1

In this case there's a direct edge from 1 to 5, so the shortest path is one hop. For weighted shortest paths (Dijkstra's algorithm), pure SQL recursive CTEs get unwieldy because Dijkstra requires a priority queue — you always want to explore the lowest-cost unvisited node next, but SQL's set-based iteration doesn't support priority ordering within the recursive step. You can approximate it with careful query construction, but for serious weighted graph analysis, consider pgRouting (a PostgreSQL extension) or pulling the data into a graph database or graph algorithm library.

---

Bill of Materials: Multi-Level Product Assembly

The bill of materials (BOM) problem is the industrial counterpart of the org chart. A manufactured product contains sub-assemblies, which contain components, which contain raw materials. You need to know the total quantity and cost of every leaf-level material that goes into a finished product.

CREATE TABLE bom (
    component_id    INT,
    parent_id       INT,         -- NULL for finished products
    component_name  VARCHAR(100),
    quantity        NUMERIC,     -- quantity of this component per parent unit
    unit_cost       NUMERIC
);

INSERT INTO bom VALUES
  (1, NULL, 'Mountain Bike',         1,    NULL),
  (2, 1,    'Frame Assembly',        1,    NULL),
  (3, 1,    'Drivetrain Assembly',   1,    NULL),
  (4, 1,    'Wheel Set',             2,    NULL),
  (5, 2,    'Carbon Frame',          1,    185.00),
  (6, 2,    'Headset',               1,    22.00),
  (7, 3,    'Crankset',              1,    64.00),
  (8, 3,    'Rear Derailleur',       1,    89.00),
  (9, 3,    'Chain',                 1,    18.00),
  (10,4,    'Rim',                   1,    45.00),
  (11,4,    'Hub',                   1,    38.00),
  (12,4,    'Spokes',                36,    0.35);

The challenge here: each component has a quantity, and when you have nested assemblies, you need to multiply quantities all the way down. A Wheel Set (quantity 2 per bike) contains 36 Spokes each — so a complete bike needs 72 spokes, not 36.

WITH RECURSIVE exploded_bom AS (
    -- Anchor: the finished product
    SELECT
        component_id,
        parent_id,
        component_name,
        quantity AS quantity_per_parent,
        quantity AS total_quantity,  -- at the top level, same thing
        unit_cost,
        0 AS level
    FROM bom
    WHERE parent_id IS NULL

    UNION ALL

    SELECT
        b.component_id,
        b.parent_id,
        b.component_name,
        b.quantity,
        -- Multiply this component's quantity by the total quantity of its parent
        b.quantity * eb.total_quantity AS total_quantity,
        b.unit_cost,
        eb.level + 1
    FROM bom b
    JOIN exploded_bom eb ON b.parent_id = eb.component_id
)
SELECT
    REPEAT('  ', level) || component_name AS component,
    total_quantity,
    unit_cost,
    ROUND(total_quantity * COALESCE(unit_cost, 0), 2) AS extended_cost
FROM exploded_bom
ORDER BY level, component_name;

 component                    | total_quantity | unit_cost | extended_cost
------------------------------+----------------+-----------+--------------
 Mountain Bike                |              1 |           |          0.00
   Drivetrain Assembly        |              1 |           |          0.00
   Frame Assembly             |              1 |           |          0.00
   Wheel Set                  |              2 |           |          0.00
     Carbon Frame             |              1 |    185.00 |        185.00
     Chain                    |              1 |     18.00 |         18.00
     Crankset                 |              1 |     64.00 |         64.00
     Headset                  |              1 |     22.00 |         22.00
     Hub                      |              2 |     38.00 |         76.00
     Rear Derailleur          |              1 |     89.00 |         89.00
     Rim                      |              2 |     45.00 |         90.00
     Spokes                   |             72 |      0.35 |         25.20

The Spokes correctly show 72 (36 per wheel × 2 wheels). The Hubs show quantity 2, cost $76. The total cost of all raw materials sums to $569.20. The total_quantity * COALESCE(unit_cost, 0) expression gives you the extended cost per component — NULL costs (sub-assemblies) are treated as zero, and a final SUM over the leaf nodes gives you the total material cost for the product.

---

Performance: Where Recursive CTEs Break Down and What to Do

Recursive CTEs are powerful, but they're not free. Understanding their performance characteristics is what separates solutions that work in development from ones that survive production.

Indexing Strategy

The single most important thing you can do is ensure you have an index on the join column in the recursive member. For a typical parent-child traversal:

-- This index makes all the difference
CREATE INDEX idx_employees_manager_id ON employees(manager_id);

Without this index, every iteration of the recursion does a sequential scan of the table, joining against the working table. With the index, each iteration does an index lookup. On a table with 10,000 employees, this can be the difference between a 50ms query and a 50-second query.

For path queries where you frequently look up "give me the subtree under node X," you should also consider the manager_id, employee_id composite index to enable index-only scans:

CREATE INDEX idx_employees_manager_employee ON employees(manager_id, employee_id);

The N+1 Problem in Recursion

Each iteration of the recursive CTE is essentially a separate query execution. For a tree with depth D and average branching factor B, the total number of rows processed is approximately (B^(D+1) - 1) / (B - 1). For a balanced binary tree of depth 20, that's over a million rows. For a star-shaped hierarchy where one node has 10,000 direct children, the anchor returns 10,000 rows and the first recursive iteration does a 10,000-row join.

This isn't necessarily a problem — it's just the nature of the traversal. But if you're calling this query in a loop (for each of 1,000 employees, find their subtree), you should restructure: do one traversal of the entire tree, tag each row with its ancestor, and join the results to your list of employees in a single pass.

When to Materialize

If you're running the same hierarchical query repeatedly and the underlying data changes infrequently, consider materializing the results:

CREATE MATERIALIZED VIEW employee_hierarchy AS
WITH RECURSIVE org_tree AS (
    SELECT
        employee_id,
        name,
        manager_id,
        0 AS depth,
        ARRAY[employee_id] AS ancestors,
        name::TEXT AS full_path
    FROM employees
    WHERE manager_id IS NULL

    UNION ALL

    SELECT
        e.employee_id,
        e.name,
        e.manager_id,
        ot.depth + 1,
        ot.ancestors || e.employee_id,
        ot.full_path || ' > ' || e.name
    FROM employees e
    JOIN org_tree ot ON e.manager_id = ot.employee_id
)
SELECT * FROM org_tree;

CREATE INDEX idx_eh_employee_id ON employee_hierarchy(employee_id);
CREATE INDEX idx_eh_depth ON employee_hierarchy(depth);

-- Refresh when org chart changes
REFRESH MATERIALIZED VIEW employee_hierarchy;

After materialization, "find all descendants of Sarah Chen" becomes a simple array lookup — no recursion needed at query time.

Depth Limits and Termination Guarantees

Always include a depth limit in production code that touches data you don't fully control:

WHERE ot.depth < 50  -- Reasonable for an org chart; adjust for your domain

This is cheap insurance. A depth limit doesn't hurt well-formed data (an org chart rarely exceeds 10-12 levels), but it prevents a bad data row from running your database out of memory.

---

Advanced Pattern: Finding Common Ancestors

A classic tree problem: given two nodes, find their lowest common ancestor (LCA) — the deepest node that is an ancestor of both. This is useful in category hierarchies ("find the most specific shared category for these two products") and org charts ("who is the most junior person who manages both Sarah and Marcus?").

WITH RECURSIVE
-- Get all ancestors of node 8 (Aisha Grant)
ancestors_of_8 AS (
    SELECT employee_id, manager_id, 0 AS depth
    FROM employees WHERE employee_id = 8

    UNION ALL

    SELECT e.employee_id, e.manager_id, a.depth + 1
    FROM employees e
    JOIN ancestors_of_8 a ON e.employee_id = a.manager_id
),
-- Get all ancestors of node 11 (Dev Sharma)
ancestors_of_11 AS (
    SELECT employee_id, manager_id, 0 AS depth
    FROM employees WHERE employee_id = 11

    UNION ALL

    SELECT e.employee_id, e.manager_id, a.depth + 1
    FROM employees e
    JOIN ancestors_of_11 a ON e.employee_id = a.manager_id
)
-- Find common ancestors and pick the deepest (lowest depth = closest to root, so MAX depth = lowest in tree)
SELECT
    a8.employee_id,
    e.name,
    e.title,
    a8.depth AS depth_from_8,
    a11.depth AS depth_from_11
FROM ancestors_of_8 a8
JOIN ancestors_of_11 a11 ON a8.employee_id = a11.employee_id
JOIN employees e ON a8.employee_id = e.employee_id
ORDER BY a8.depth DESC
LIMIT 1;

 employee_id | name        | title              | depth_from_8 | depth_from_11
-------------+-------------+--------------------+--------------+--------------
           1 | Diana Okonkwo | CEO               |            3 |             3

Hmm — that returns the CEO because both Aisha (under Backend, under Engineering) and Dev (under Frontend, under Engineering) ultimately report to the CEO. But the LCA should actually be Sarah Chen (VP of Engineering), who is the closest shared ancestor. Let me check: Aisha's chain is 8 -> 4 -> 2 -> 1. Dev's chain is 11 -> 5 -> 2 -> 1. They share nodes 2 and 1. Node 2 is at depth 2 from Aisha and depth 2 from Dev, versus depth 3 for node 1. We want the one with maximum depth_from_8 (which means closest to the leaves), so ORDER BY a8.depth DESC LIMIT 1 should give Sarah Chen (depth 2), not the CEO (depth 3). Let me verify the depth calculation: depth 0 = the node itself, depth 1 = parent, depth 2 = grandparent. Sarah Chen is at depth 2 from Aisha. Diana is at depth 3. ORDER BY depth DESC gives us the highest depth value first, which is the furthest ancestor from the node — which is the CEO, not Sarah. The correct ordering is ORDER BY a8.depth ASC LIMIT 1 to get the lowest depth that's shared (the closest shared ancestor):

ORDER BY a8.depth ASC
LIMIT 1;

 employee_id | name       | title             | depth_from_8 | depth_from_11
-------------+------------+-------------------+--------------+--------------
           2 | Sarah Chen | VP of Engineering |            2 |             2

The lowest common ancestor is Sarah Chen — the most specific manager who oversees both Aisha and Dev.

---

Hands-On Exercise

It's time to apply what you've learned on a new domain. Set up the following schema representing a software dependency graph:

CREATE TABLE packages (
    package_id    INT PRIMARY KEY,
    package_name  VARCHAR(50) NOT NULL,
    version       VARCHAR(20),
    is_vulnerable BOOLEAN DEFAULT FALSE
);

CREATE TABLE dependencies (
    package_id    INT REFERENCES packages(package_id),
    depends_on_id INT REFERENCES packages(package_id),
    PRIMARY KEY (package_id, depends_on_id)
);

INSERT INTO packages VALUES
  (1,  'webapp',       '3.2.0', FALSE),
  (2,  'api-client',   '2.1.0', FALSE),
  (3,  'auth-lib',     '1.5.0', FALSE),
  (4,  'crypto-utils', '0.9.0', TRUE),   -- Vulnerable!
  (5,  'http-core',    '4.0.1', FALSE),
  (6,  'json-parser',  '2.3.0', FALSE),
  (7,  'log-writer',   '1.2.0', FALSE),
  (8,  'date-utils',   '3.1.0', FALSE),
  (9,  'cache-layer',  '1.0.0', FALSE),
  (10, 'base64',       '2.0.0', FALSE);

INSERT INTO dependencies VALUES
  (1, 2), (1, 3), (1, 7),
  (2, 5), (2, 6),
  (3, 4), (3, 5),
  (5, 10),
  (6, 8),
  (9, 4);

Exercise 1 — Dependency Tree: Write a recursive CTE that, starting from webapp (package_id = 1), finds all direct and transitive dependencies. Include depth and the full dependency path.

Exercise 2 — Vulnerability Impact Analysis: Write a query that finds every package that is transitively exposed to the vulnerability in crypto-utils (package_id = 4). A package is exposed if it depends on crypto-utils, or depends on something that depends on it, at any depth. Show the dependency path that leads to the vulnerable package.

Exercise 3 — Depth-First vs. Breadth-First: The recursive CTE naturally produces BFS ordering (all nodes at depth 1 before depth 2, etc.). How would you identify the order in which nodes were discovered? Add a discovery_order column using a row number over the result set.

Exercise 4 — Cycle Safety: Add a circular dependency to the data (INSERT INTO dependencies VALUES (4, 1); — crypto-utils depends on webapp, creating a cycle). Modify your Exercise 1 query to handle this safely using path-based cycle detection. Verify that the query terminates and correctly identifies the point where the cycle would be entered.

Bonus: Rewrite the vulnerability analysis as a bottom-up traversal: starting from crypto-utils, find everything that depends on it (its "reverse dependencies"). Compare the query structure to your top-down version from Exercise 2.

---

Common Mistakes & Troubleshooting

Mistake 1: Forgetting UNION ALL vs. UNION

Using UNION (without ALL) in a recursive CTE causes deduplication at each iteration step. This has two problems: it's much slower (requires a sort or hash operation per iteration), and it doesn't actually prevent infinite loops in cyclic graphs — it prevents duplicate rows in the output, not revisiting the same node during traversal. Use UNION ALL and add explicit cycle detection.

Mistake 2: Non-Deterministic Termination Assumptions

If you write a recursive member that can join to rows from the anchor that aren't in the current iteration's working table, you might be surprised by the result count. The recursive member only joins against the previous iteration's output, not the accumulated full result. This is usually what you want, but if your join condition is wrong, you might produce fewer rows than expected.

-- Wrong: this CTE will never expand beyond depth 1 in most cases
-- because it's joining on the wrong condition
WITH RECURSIVE broken AS (
    SELECT employee_id, manager_id, 0 AS d FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.employee_id, e.manager_id, b.d + 1
    FROM employees e
    JOIN broken b ON e.employee_id = b.manager_id  -- This is backwards
    --                               ^^^^^^^^^^^
    -- This finds e where e's employee_id = b's manager_id
    -- i.e., it goes UP the tree from b, not down
)

Always trace through one manual iteration on paper when your results look wrong.

Mistake 3: Column Type Mismatches in Path Accumulation

When building path strings or arrays, type mismatches cause silent truncation or errors. The employee_id is an INT; when building a path string with ||, PostgreSQL requires you to cast explicitly: ot.path_names || ' -> ' || e.name::TEXT. Forgetting the cast on the initial anchor is a common source of confusing type errors.

Mistake 4: Inefficient Cycle Detection with NOT IN

This is a performance trap:

-- Slow on large paths
WHERE next_node NOT IN (SELECT unnest(visited_nodes))

-- Fast
WHERE NOT (next_node = ANY(visited_nodes))

The = ANY(array) operator is O(n) in array length but uses array internals efficiently. The NOT IN (SELECT unnest(...)) version creates a subquery that PostgreSQL may not optimize well. On deep paths with hundreds of nodes, this difference becomes significant.

Mistake 5: Querying the CTE Twice

This is subtle. If you write:

WITH RECURSIVE cte AS (...)
SELECT * FROM cte WHERE depth = 5
UNION ALL
SELECT * FROM cte WHERE depth = 0;

PostgreSQL materializes the CTE once by default (prior to PostgreSQL 12, always; after 12, the optimizer decides). But explicit WITH clauses that are referenced multiple times may be executed multiple times depending on your database and version. For recursive CTEs specifically, PostgreSQL executes them once and caches results. SQL Server does the same. But if you're unsure, wrap the recursive CTE in a second CTE:

WITH RECURSIVE inner_cte AS (...),
final AS (SELECT * FROM inner_cte)
SELECT * FROM final WHERE depth = 5
UNION ALL
SELECT * FROM final WHERE depth = 0;

Troubleshooting: Query Runs Forever

1. Check for cycles: add a depth limit (WHERE depth < 20) temporarily to let the query finish and inspect results.
2. Inspect your termination condition: the recursion stops when the recursive member produces zero rows. If you're joining on a non-indexed column, this could be extremely slow rather than infinite.
3. Use EXPLAIN (ANALYZE, VERBOSE) — even on a query that times out if you can get it to finish within a limited depth.

Troubleshooting: Wrong Row Counts

Run the query with LIMIT 0 first to check the schema is right. Then add depth tracking and inspect one depth level at a time by adding WHERE depth = N to the final SELECT. This lets you verify iteration by iteration that the join logic is correct.

---

Summary & Next Steps

You've gone from the mechanics of how recursive CTEs actually execute (iterative working-table expansion, not call-stack recursion) to practical traversal in both directions, all the way to cycle detection, path reconstruction, subtree aggregates, and the bill of materials pattern. The key ideas to carry forward:

The adjacency list is the native graph representation in SQL. It's flexible and efficient for mutable graphs, but requires recursive queries to traverse. Now you can do that traversal with precision.

Carry computed metadata through the recursion. Depth, path arrays, accumulated costs, ancestor tags — these are calculated once per node as you pass through and avoid expensive post-processing.

Cycle detection belongs in every production recursive CTE that touches user-controlled data. Use path arrays and a NOT ... = ANY(...) guard. Always add a depth limit as a secondary safeguard.

Indexing the join column is mandatory. Without an index on the parent foreign key, recursive CTEs scan the full table on every iteration.

Know when to materialize. For hierarchies that are queried far more often than they change, a materialized view eliminates recursion at query time entirely.

Where to go next:

• Explore PostgreSQL's ltree extension, which adds native path operations for label tree data — excellent for category hierarchies where you control the insertion process.
• Study graph databases like Neo4j and their Cypher query language. When your graphs are dense, have many relationship types, or require complex path algorithms (Dijkstra, PageRank, community detection), a dedicated graph engine vastly outperforms recursive SQL.
• Learn pgRouting if you work with geospatial network data — it implements Dijkstra, A*, and many other routing algorithms as PostgreSQL functions.
• Investigate temporal hierarchies: org charts that change over time require combining recursive CTEs with effective-date filtering, which introduces a whole new class of complexity.
• Practice query plan analysis specifically for recursive CTEs: the EXPLAIN output for a recursive query looks different from a standard plan, and learning to read it helps you diagnose performance problems quickly.

Graph traversal is one of those capabilities that, once you have it in your SQL toolkit, you'll find opportunities to use it everywhere. The data you thought required an external graph tool was often just waiting for a well-constructed recursive CTE.