Recursive CTEs for Hierarchical Data

1. Why normal queries fail on hierarchies

Hierarchical data such as category trees, org charts, or bills of materials has a property an ordinary SQL query cannot express: an unknown nesting depth. A table with a parent_id column can be joined only one level deep with a single JOIN. A second level needs a second JOIN, a third needs a third, and so on, until in the worst case the tree depth exceeds the number of joins written, and the query stops being generic.

That is exactly where a recursive CTE comes in. It is the only standard SQL construct that can repeatedly apply a query to its own intermediate result until no new rows are added. That makes a tree traversal of arbitrary depth possible in a single statement, without application code loading levels one at a time and without a hardcoded maximum depth.

A recursive CTE differs from an ordinary CTE by the RECURSIVE keyword and by the fact that it references itself within its own definition. Standard SQL allows this self-reference exclusively in this context, which makes WITH RECURSIVE a clearly scoped but powerful tool whenever tree structures need to be represented in the relational model.

2. The syntax of WITH RECURSIVE

A recursive CTE consists of two parts joined by UNION or UNION ALL: the anchor query, also called the base case, and the recursive part. The anchor query supplies the starting rows, typically the root nodes of a tree with no parent. The recursive part references the recursive CTE itself and is executed repeatedly until it no longer returns new rows. Each iteration uses only the rows newly added in the previous iteration, not the entire result accumulated so far.

PostgreSQL and MySQL 8 require the RECURSIVE keyword directly after WITH, even if only one of several CTEs in the clause is actually recursive. SQL Server does not need this keyword, there the plain self-reference in the recursive part is enough. Oracle also supports WITH RECURSIVE syntax starting with version 11g Release 2, but alternatively offers the older, Oracle-specific CONNECT BY syntax for the same purpose.

-- Recursive CTE skeleton: anchor UNION ALL recursive part
WITH RECURSIVE category_tree AS (
    -- Anchor: root categories with no parent
    SELECT category_id, name, parent_id, 1 AS level
    FROM categories
    WHERE parent_id IS NULL

    UNION ALL

    -- Recursive part: join child rows to the previous iteration
    SELECT c.category_id, c.name, c.parent_id, ct.level + 1
    FROM categories c
    JOIN category_tree ct ON c.parent_id = ct.category_id
)
SELECT category_id, name, level
FROM category_tree
ORDER BY level, name;

3. Practical example: category tree, top down

The classic use case for a recursive CTE is walking a category tree downward: starting from a root category, all subcategories at any depth need to be found, for example to display all products in a main category including every subcategory. The anchor query starts at the desired category, and the recursive part finds the direct children of the most recently found nodes on each iteration.

In practice this result is usually joined directly with the products table: the recursive CTE returns the set of all relevant category IDs, and a subsequent JOIN or a WHERE category_id IN (SELECT category_id FROM category_tree) filters the products. This combination replaces application logic that would otherwise have to recursively load categories and collect the IDs on the client side.

-- Find all products under "Electronics", including every subcategory
WITH RECURSIVE subtree AS (
    SELECT category_id, name, parent_id
    FROM categories
    WHERE name = 'Electronics'

    UNION ALL

    SELECT c.category_id, c.name, c.parent_id
    FROM categories c
    JOIN subtree st ON c.parent_id = st.category_id
)
SELECT p.product_id, p.product_name, s.name AS category_name
FROM products p
JOIN subtree s ON s.category_id = p.category_id
ORDER BY s.name, p.product_name;

4. Practical example: org chart, bottom up

Not every tree traversal goes downward. A typical counterexample is finding the entire management chain of an employee in an org chart: starting from a specific employee, all managers up to the top of the company need to be found. Here the anchor query starts at the employee itself, and the recursive part follows the manager_id column upward, instead of moving downward to children via parent_id as in the category tree.

This direction is symmetric to the first one: instead of c.parent_id = ct.category_id in the JOIN, here it is e.employee_id = eh.manager_id, so the relationship is reversed. A recursive CTE has no fixed direction, it simply follows the join condition defined in the recursive part, whether that leads downward to children or upward to parents.

-- Walk up the management chain from a given employee to the CEO
WITH RECURSIVE reporting_chain AS (
    SELECT employee_id, full_name, manager_id, 0 AS steps_up
    FROM employees
    WHERE employee_id = 4711

    UNION ALL

    SELECT e.employee_id, e.full_name, e.manager_id, rc.steps_up + 1
    FROM employees e
    JOIN reporting_chain rc ON e.employee_id = rc.manager_id
)
SELECT employee_id, full_name, steps_up
FROM reporting_chain
ORDER BY steps_up;

5. Depth, path and ordering within the tree

Besides the plain rows, a recursive CTE often also produces metadata about the position within the tree. A depth counter, initialized with a fixed starting value in the anchor query and incremented by one on each iteration in the recursive part, makes visible how far a node is from the root. This depth is useful for indentation in a tree display or as a filter to cap the traversal at a maximum number of levels.

For correct visual ordering, where child nodes should appear directly under their parent, a simple ordering by depth is not enough. The common approach is a path array or a path string that gets extended with the current ID on each iteration, for example with PostgreSQL's array type or with string concatenation. A subsequent ORDER BY path sorts the whole tree in correct hierarchical order, with every descendant appearing directly under its respective ancestor.

-- Track depth and a sortable materialized path through the tree
WITH RECURSIVE category_tree AS (
    SELECT category_id, name, parent_id,
           1 AS depth,
           ARRAY[category_id] AS path,
           name::text AS path_label
    FROM categories
    WHERE parent_id IS NULL

    UNION ALL

    SELECT c.category_id, c.name, c.parent_id,
           ct.depth + 1,
           ct.path || c.category_id,
           ct.path_label || ' / ' || c.name
    FROM categories c
    JOIN category_tree ct ON c.parent_id = ct.category_id
)
SELECT REPEAT('  ', depth - 1) || name AS indented_name, path_label
FROM category_tree
ORDER BY path;

6. Setting termination conditions correctly

A recursive CTE terminates automatically once the recursive part returns no new rows in an iteration, because no record exists anymore that satisfies the join condition. That is the normal case for a tree without cycles: eventually all leaf nodes are reached, there are no further children, and the recursion stops on its own. This implicit termination is entirely sufficient for most tree structures with correct foreign key constraints.

Additionally, an explicit condition in the recursive part can cap the recursion early, for example WHERE ct.depth < 10, to set a hard upper bound for unexpectedly deep or corrupted data. SQL Server offers the MAXRECURSION query option as a server-side safety limit, which aborts a recursive CTE with an error after a set number of iterations, 100 levels by default, which is a sensible safety net against corrupted data, particularly in production environments.

7. Detecting cycles and avoiding infinite loops

The biggest danger with a recursive CTE is a cycle in the data: if node A points to node B, and node B, due to a data error, points back to node A, the implicit condition never terminates, because each iteration keeps finding new combinations. Without a safeguard, the database runs into an infinite loop until memory or a hard iteration limit aborts the statement.

PostgreSQL 14 introduced native cycle detection with CYCLE, which automatically checks whether a node already appears in the current path and stops the recursion at that point, without failing the whole statement. In older versions and other databases, the same check is implemented manually via a path array and a WHERE NOT c.category_id = ANY(ct.path) condition in the recursive part, which prevents an already visited node from being picked up again by the recursion.

-- PostgreSQL 14+: native cycle detection
WITH RECURSIVE category_tree AS (
    SELECT category_id, parent_id, name
    FROM categories
    WHERE parent_id IS NULL

    UNION ALL

    SELECT c.category_id, c.parent_id, c.name
    FROM categories c
    JOIN category_tree ct ON c.parent_id = ct.category_id
) CYCLE category_id SET is_cycle USING path
SELECT category_id, name, is_cycle
FROM category_tree;

-- Portable manual cycle guard using a path array
WITH RECURSIVE category_tree AS (
    SELECT category_id, parent_id, name, ARRAY[category_id] AS visited
    FROM categories
    WHERE parent_id IS NULL

    UNION ALL

    SELECT c.category_id, c.parent_id, c.name, ct.visited || c.category_id
    FROM categories c
    JOIN category_tree ct ON c.parent_id = ct.category_id
    WHERE NOT c.category_id = ANY(ct.visited)
)
SELECT category_id, name FROM category_tree;

8. Performance on large hierarchies

On large hierarchies with tens of thousands of nodes, the performance of a recursive CTE depends significantly on an index on the foreign key column used for the recursive join, typically parent_id. Without that index every iteration degenerates into a full table scan, which leads to quadratic instead of linear runtime on deep trees. A simple index on parent_id often reduces this to acceptable runtimes even on very large tables.

For extremely large or very deep hierarchies that are read often but changed rarely, a recursive CTE is not always the fastest solution. Alternatives such as a nested set model or a materialized path column updated on every change shift the cost from the read operation to the write operation and can be noticeably faster than a recursive traversal on every request for read-heavy workloads.

9. Common mistakes with recursive CTEs

The most common mistake is missing a termination condition on cyclic or potentially corrupted data, which leads directly into an infinite loop. The second common mistake is using UNION instead of UNION ALL between the anchor query and the recursive part: UNION deduplicates the entire accumulated result set on every iteration, which drastically hurts performance on large trees, while UNION ALL skips deduplication and is the correct choice in practically all cases, as long as no cycles are present.

A third mistake is trying to use an aggregate function like SUM or COUNT over the entire recursive CTE inside the recursive part. Aggregate functions are not allowed in the recursive part under standard SQL, because the result is not yet complete at the time of the iteration. Anyone needing a sum over the whole tree aggregates in a separate query built on top of the recursive CTE after the recursion has finished.

10. Summary

A recursive CTE is the standard SQL tool for tree structures of arbitrary depth. It consists of an anchor query that supplies the starting nodes, and a recursive part that references itself and processes only the newly added rows on each iteration. Whether a category tree is traversed downward or a management chain upward is decided solely by the direction of the join condition in the recursive part.

Termination usually happens implicitly once no new rows are found, but should always be safeguarded with a path array or native cycle detection like CYCLE in PostgreSQL 14 whenever the data could be cyclic. UNION ALL instead of UNION is the right choice for performance, an index on the foreign key column is mandatory on large hierarchies. For extremely large, rarely changed trees, it is worth looking at alternatives such as nested sets or materialized paths.

11. FAQ: Recursive CTEs