PostgreSQL Recursive CTEs for Hierarchies

Adjacency lists are the most common way to store a tree in a relational database: every row has a parent_id pointing at another row in the same table. They’re easy to write to (moving a subtree is one UPDATE) and awkward to read from, because “give me everything under Computers” needs an unknown number of joins. A recursive common table expression is how you write that unknown number of joins as one query.

The examples below ran on SQLite 3.53 through Python’s sqlite3 module, whose WITH RECURSIVE follows the same evaluation rules as PostgreSQL for everything shown. Where PostgreSQL has syntax SQLite lacks (arrays, the CYCLE and SEARCH clauses), the section says so.

How PostgreSQL evaluates WITH RECURSIVE

The name is a little misleading. Nothing calls itself. PostgreSQL runs an iteration, and knowing the loop is what lets you reason about the output:

1. Run the anchor (the query before UNION ALL). Its rows go into the result and into a scratch “working table”.
2. Run the recursive term (the query after UNION ALL), where every reference to the CTE’s own name reads only the working table, not the whole result so far.
3. Whatever that produced becomes the new working table and is appended to the result.
4. Repeat from step 2 until the recursive term returns zero rows.

Two consequences follow. First, each round sees only the previous level, so a join on parent_id = s.id walks exactly one level per round. Second, termination depends entirely on the data: if every round finds at least one new row, the loop doesn’t end. There’s no built-in maximum depth in PostgreSQL.

The recursive term also has restrictions that interviewers sometimes probe. It can reference the CTE only once, and PostgreSQL rejects that reference inside a subquery, inside an aggregate, or on the nullable side of an outer join. ORDER BY and LIMIT on the recursive part aren’t supported either. If you need “the deepest child” or “a count per level”, compute it in the outer SELECT after the recursion finishes.

Walking down a category tree

Here’s a small product catalogue:

CREATE TABLE categories (
  id        integer PRIMARY KEY,
  parent_id integer REFERENCES categories(id),
  name      text NOT NULL
);

INSERT INTO categories VALUES
  (1, NULL, 'Electronics'),
  (2, 1,    'Computers'),
  (3, 2,    'Laptops'),
  (4, 2,    'Desktops'),
  (5, 3,    'Gaming laptops'),
  (6, 1,    'Phones'),
  (7, 1,    'Accessories'),
  (8, 7,    'Chargers');

A typical request: the category page for Computers must list every subcategory, indented, so the front end needs each row’s depth and a sortable path.

WITH RECURSIVE subtree AS (
  SELECT id, parent_id, name, 0 AS depth, name AS path
  FROM categories
  WHERE id = 2
  UNION ALL
  SELECT c.id, c.parent_id, c.name, s.depth + 1, s.path || ' > ' || c.name
  FROM categories c
  JOIN subtree s ON c.parent_id = s.id
)
SELECT id, name, depth, path
FROM subtree
ORDER BY path;

id | name           | depth | path
2  | Computers      | 0     | Computers
4  | Desktops       | 1     | Computers > Desktops
3  | Laptops        | 1     | Computers > Laptops
5  | Gaming laptops | 2     | Computers > Laptops > Gaming laptops

Trace the rounds. The anchor finds Computers and gives it depth 0. Round one joins the working table (just Computers) to categories and finds Laptops and Desktops. Round two starts from those two and finds Gaming laptops. Round three starts from Gaming laptops, finds no children, and the loop stops after four rows.

Notice that depth and path are built inside the recursion. That’s the main design decision in any hierarchical query. Once the CTE has finished, the rows are just a flat bag; nothing remembers which round produced which row, and SQL never promises the output order of a CTE. If you want depth, a breadcrumb or a display order, carry the column through every iteration.

Gotcha

In PostgreSQL the anchor fixes each column’s type. If name were varchar(100), s.path || ' > ' || c.name produces text, and PostgreSQL rejects the query with an error of the form recursive query "subtree" column 5 has type ... in non-recursive term but type ... overall. Cast in the anchor (name::text AS path) and the error goes away.

Sorting by the string path works here because the names happen to sort well, but it breaks when a name contains characters that sort before > or when siblings need a custom order. In PostgreSQL the sturdier option is an array of sort keys, ARRAY[id] AS path in the anchor and s.path || c.id in the recursive term, since arrays compare element by element. PostgreSQL 14 added SEARCH DEPTH FIRST BY id SET ordercol, which builds that array column for you.

Walking up: ancestors and breadcrumbs

Reverse the join condition and the same machinery climbs instead of descends. The breadcrumb for Gaming laptops:

WITH RECURSIVE ancestors AS (
  SELECT id, parent_id, name, 0 AS hops
  FROM categories
  WHERE id = 5
  UNION ALL
  SELECT c.id, c.parent_id, c.name, a.hops + 1
  FROM categories c
  JOIN ancestors a ON c.id = a.parent_id
)
SELECT name, hops FROM ancestors ORDER BY hops DESC;

name           | hops
Electronics    | 3
Computers      | 2
Laptops        | 1
Gaming laptops | 0

Going up is cheap: each round looks up one row by primary key. Going down is where indexes matter. The recursive term in the first query is c.parent_id = s.id, executed once per round, so without an index on categories(parent_id) every round is a sequential scan of the whole table. PostgreSQL doesn’t create indexes for foreign keys automatically, which is a detail worth saying out loud in an interview. Run EXPLAIN ANALYZE and look at the node under the WorkTable Scan: you want an index scan on parent_id, not a Seq Scan repeated for every level.

When the data has a cycle

Hierarchies are supposed to be acyclic, but nothing in an adjacency list enforces it. Somebody moves Electronics under Gaming laptops in an admin screen:

UPDATE categories SET parent_id = 5 WHERE id = 1;

Now Computers → Laptops → Gaming laptops → Electronics → Computers is a loop, and the first query never finishes. Every round finds children, because the working table always contains a node that has a child. You’ll see it as a query that runs until statement_timeout cancels it, or until temporary files fill the disk.

The bluntest guard is a depth cap in the recursive term:

  SELECT c.id, c.name, s.depth + 1
  FROM categories c
  JOIN subtree s ON c.parent_id = s.id
  WHERE s.depth < 6

It does stop, but grouping the output by depth shows what you get back:

depth | names
0     | Computers
1     | Desktops, Laptops
2     | Gaming laptops
3     | Electronics
4     | Accessories, Computers, Phones
5     | Chargers, Desktops, Laptops
6     | Gaming laptops

Computers, Laptops and Desktops appear twice. A cap protects the server, not the correctness of the answer. It’s still worth having on top of a real guard, as a ceiling a tree should never reach.

The real guard is to remember which ids the current branch has visited and refuse to step onto one again. In PostgreSQL that’s an array column:

-- PostgreSQL
WITH RECURSIVE subtree AS (
  SELECT id, name, ARRAY[id] AS seen
  FROM categories
  WHERE id = 2
  UNION ALL
  SELECT c.id, c.name, s.seen || c.id
  FROM categories c
  JOIN subtree s ON c.parent_id = s.id
  WHERE c.id <> ALL (s.seen)
)
SELECT id, name, seen FROM subtree;

SQLite has no arrays, so the version I ran used a delimited string (',2,3,') and instr() to test membership. It returned each of the eight categories exactly once, with Electronics reached at the end of the 2,3,5,1 path. On PostgreSQL 14 and later you can write the same thing declaratively: CYCLE id SET is_cycle USING path after the CTE body marks the row that closes a loop and stops following it, and you filter WHERE NOT is_cycle in the outer query.

What about switching UNION ALL to UNION? UNION discards any row that duplicates a row already produced, so a plain (id, name) CTE does terminate: my run returned 8 rows. But as soon as you carry depth or path, the repeated visit is a different row (depth 4 instead of 0), deduplication can’t see it, and the loop is back. Treat UNION as a way to collapse genuine duplicates in a graph with shared descendants, not as cycle protection.

Interview practice: the org chart that hung

“An internal HR tool runs a recursive CTE to compute everyone who reports, directly or indirectly, to a given manager. It worked for a year. Yesterday it started timing out for one VP, and only for her. What do you check, and how do you fix it so it can’t happen again?”

Answer and reasoning

A timeout for one starting point but not others points at the data under that VP, not at the query plan, since the same query is fine for every other manager. The most likely cause is a reporting cycle: someone in her organisation now has her, or one of her reports, as their manager. I’d confirm it with a guarded version of the query that carries the visited path and returns the row where the next step would revisit an id, or on PostgreSQL 14+ with CYCLE manager_id SET is_cycle USING path and WHERE is_cycle. That names the exact two employees involved.

I’d also rule out the less dramatic explanation: her organisation is simply large and employees(manager_id) has no index, so each level is a full scan. EXPLAIN ANALYZE with a depth cap would show a Seq Scan under the recursive part. That explains slowness, though, not a sudden hang that only started yesterday.

For the fix, the query gets a visited-path guard plus a generous depth cap, so bad data produces a wrong-but-bounded answer instead of an outage. Then the write side needs protection, because the query is only where the bug surfaced. A constraint can’t express “no cycles” directly, so I’d add a check in the transaction that changes a manager (or a trigger) that walks up from the new manager and rejects the update if it reaches the employee being moved. If the tree rarely changes and is read constantly, I’d also mention a closure table or the ltree extension as alternatives that make reads cheap and cycles impossible to store.

Further reading

• SQL interview questions
• SQL quiz questions
• What a CTE is for in PostgreSQL
• Reading EXPLAIN ANALYZE output
• PostgreSQL documentation: WITH queries