CSE Roadmap

Common tier · about 3 hours · 5 parts

Part 4 of 5 · 2 min read

Recursive CTEs

Walking a hierarchy of unknown depth, by referring to the CTE from inside its own definition.

Recursive CTEs

Think of finding every person who reports, directly or indirectly, to one specific manager. The chain of reporting could be two levels deep or ten. Nobody knows in advance how many.

In plain words: a recursive CTE has two parts: a base case, finding the starting rows, and a recursive case, which refers to the CTE's own name to find the next level, repeated until no new rows are found. Without both parts correctly bounded, a recursive CTE can loop forever.

A worked example. Finding a book category and every one of its subcategories, using a categories (category_id, parent_id, name) table.

The key lines.

WITH RECURSIVE subcategories AS (
    SELECT category_id, parent_id, name FROM categories WHERE category_id = 1
    UNION ALL
    SELECT c.category_id, c.parent_id, c.name
    FROM categories c
    JOIN subcategories s ON c.parent_id = s.category_id
)
SELECT * FROM subcategories;

Recursive CTE, base case, recursive case

A recursive CTE repeatedly refers to its own result to walk a hierarchy of unknown depth. The base case supplies the starting rows. The recursive case finds the next level from rows already found, stopping once no new rows appear.

Example: the base case above starts at category 1; the recursive case finds every category whose parent_id matches a category already found, one level at a time, until no deeper level remains.

For the curious What stops the recursion

The recursion stops naturally once a step's recursive case finds zero new rows, meaning no category anywhere has a parent_id matching anything just found. A hierarchy with a cycle, which should never happen in a correctly designed tree, could make a recursive CTE loop forever unless the database enforces a limit.

Quick notes

  • A CTE, written WITH, names a subquery's result so it can be referenced like a table, including more than once.
  • A CTE computes exactly the same result as an equivalent nested subquery; it only changes how the query reads.
  • A recursive CTE needs a base case and a recursive case to walk a hierarchy of unknown depth.
  • The recursive case refers to the CTE's own name, stopping once a step finds no new rows.
  • A cycle in the underlying data could make a naive recursive CTE loop forever.