Recursive CTEs for trees: categories, org charts and bills of materials

Most trees in a database are stored the same way: each row points at its parent. A category has a parent_id, an employee has a manager_id, a part in a bill of materials sits under the assembly it goes into. It's the easiest shape to write to, and it answers "who is my direct parent" with a plain join. What it can't do with a plain join is go all the way: every category under Bikes, however deep; everyone who reports to the CTO, directly or not; how many bolts are in one finished product.

WITH RECURSIVE does that, and it's the same idea on PostgreSQL, MySQL 8 and SQLite. The details aren't: how you order the result as a tree, what happens when the data has a loop in it, and how wide MySQL lets a path column grow. We ran every query below on PostgreSQL 18.6, MySQL 8.4.13 and SQLite 3.50.4, then timed a 200,000-node tree against the two usual alternatives, a closure table and Postgres's ltree.

The tables

Ten people and one bike. Small enough to check every answer by eye:

Put an index on the parent column (manager_id, parent). Nothing creates one for you on PostgreSQL or SQLite, and as the timings further down show, the recursive step leans on it.

Walking down: everyone under someone

Read it as a loop. The first SELECT (the anchor) runs once and gives Leo. The second runs against the rows the previous round produced: round one finds Leo's reports, round two theirs, and so on until a round finds nothing. UNION ALL glues the rounds together. depth and path are just columns you carry along and extend each round; they cost almost nothing and make the result readable. On MySQL write CONCAT(s.path, ' > ', e.name) and on SQLite s.path || ' > ' || e.name; the rest is identical.

If you want everyone except Leo, filter WHERE depth > 0 outside. Don't try to leave the anchor out: the recursion needs it to start.

MySQL: the path column that stops at 40 characters

MySQL decides each column's type from the anchor alone. Start the path from a varchar(40) column and every longer path built from it has to fit in 40 characters. We built a path of job titles from the CEO down:

That's with MySQL 8.4's default strict mode, and it's the good outcome. With sql_mode = '' (still common on older servers and some hosted ones), the same query runs and Ben's path comes back as CEO > CTO > Engineering lead > Backend d, cut at 40 characters, with no error and nothing in SHOW WARNINGS. The names-based path in the previous section only worked because it never got past 22 characters.

The fix is to give the anchor the width you need: CAST(title AS CHAR(1000)) AS path. PostgreSQL and SQLite don't have the problem; text has no width to outgrow.

Walking up: someone's chain of managers

Swap the join around and the same shape climbs instead of descending:

This is what breadcrumbs on a category page are (reverse the order), and what an approval chain is. It only ever follows one row per level, so it's fast even without the parent index: it uses the primary key.

A variation worth knowing: start the anchor from every row instead of one, carrying the starting id along, and you get every (manager, person below them) pair in one pass. Group that and you have headcount at all levels: Maya 9, Leo 6, Sam 3, Ana, Ines and Yuki 1 each.

Showing it as a tree

A recursive CTE returns rows level by level, not in tree order, and without an ORDER BY no engine promises any order at all. To print a tree (each person under their manager, indented) you need a sort key that puts every row right after its parent. Carry the path of ids and sort by it:

On PostgreSQL the path is an integer array, which sorts element by element: {1,2,4,7,10} comes before {1,2,4,8}, and 10 doesn't sort before 2 the way it would as text. MySQL and SQLite have no arrays, so build a string from zero-padded ids, CONCAT(t.sort_path, '/', LPAD(e.id, 6, '0')) (with the anchor CAST to a wide CHAR, as above), and sort by that. Pad to the width of your largest id, or 10 will land between 1 and 2 again.

PostgreSQL 14 added a shorter way: SEARCH DEPTH FIRST BY name SET ord after the CTE builds the sort column for you and orders siblings by the column you name, so you can have them alphabetical (Ana before Leo) rather than by id. SQLite has its own trick: an ORDER BY inside the recursive part decides which row it expands next, and ORDER BY depth DESC makes it walk depth-first, so the rows come out in tree order. That's documented SQLite behaviour, but it's still the order of a CTE; we'd keep an explicit path to sort by in anything that matters.

A bill of materials: multiplying down the tree

A bill of materials adds one thing to the walk down: quantities multiply. A bike has 2 wheels and each wheel has 36 spokes, so the bike has 72 spokes. Carry the running quantity and multiply it each round:

The sum matters because a part can be reached by more than one route. Bolts go into each wheel (2 per wheel, 2 wheels) and into the drivetrain (4), so the walk produces two bolt rows, 4 and 4, and the bike needs 8. The total cost of one bike comes to 381.80 on all three engines. The reverse walk, "which assemblies use a bolt", starts from WHERE child = 'bolt' and climbs through parent: wheel, drivetrain, bike.

This is also why a bill of materials is not strictly a tree. A part with two parents is normal here and is not a loop. Keep that in mind for the next section: a guard that stops at any part seen twice would wrongly cut the bolts.

Loops: when the data isn't a tree

Nothing in an adjacency-list table stops a loop. One bad update, Maya now reporting to Ben (who is four levels below her), and walking down from Leo goes round forever: Leo, Sam, Ines, Ben, Maya, Leo again. What each engine did with the plain query from the start of the article:

MySQL's cte_max_recursion_depth (1000 by default) turns out to be a decent safety net. PostgreSQL and SQLite have none: the query keeps producing rows until it's cancelled or runs out of memory. A LIMIT on the outer query does stop it on both (we tried LIMIT 8: eight rows, ending with Maya at depth 4, and done), because they only compute as many rows as the outer query asks for. But then you get a quietly truncated answer instead of an error.

Using UNION instead of UNION ALL removes rows that are exact duplicates of rows already produced, which does stop the loop, but only if you carry no depth or path column (those make every row different). Without them, the walk down from Leo returned 10 rows: the whole company, because the loop led up through Maya and back down to Ana and Omar. No error, just a wrong answer. Detect the loop and report it instead.

PostgreSQL 14+: the CYCLE clause

CYCLE adds two columns: a flag that's true on the row where an id repeats on its own path, and the path itself. The recursion stops following that branch, and the path tells you exactly where the loop is: 2 → 4 → 7 → 10 → 1 → 2.

Any engine: carry the path and check it

The commas on both sides matter: without them, id 1 would be "found" inside 10 or 21. The check is per path, so the bolt that appears under both the wheel and the drivetrain is fine: it's on two different paths, never twice on one. Keep a loop check in any query that walks data people can edit, and a CHECK or trigger that refuses an update making a node its own ancestor if you can afford one.

A big tree: recursive CTE vs closure table vs ltree

The alternatives to walking an adjacency list at query time all store the tree's shape in advance. A closure table keeps one row for every (ancestor, descendant) pair. PostgreSQL's ltree extension stores each node's full path, like 1.2.7.32, and finds a subtree with an index. To see what that buys, we built a tree of 200,000 nodes on PostgreSQL 18 (every node has 5 children, 8 levels below the root) and fetched two subtrees and one chain of ancestors, median of 20 runs:

The parent index is the first win: 4 to 15 times faster on the subtrees for a 39 ms CREATE INDEX. After that the precomputed models are faster at reading a big subtree (2.4 ms vs 13.9 ms for 19,531 nodes), and the gap shrinks as the subtree gets smaller. For walking up, there's nothing to gain: the adjacency list follows the primary key nine times.

The price is on the write side. We moved node 32 and its 3,906 descendants under another parent, inside a transaction we rolled back:

So: walk the adjacency list with a recursive CTE when the tree changes often, when it's a few thousand rows (most category trees and org charts), or when you need it on MySQL and SQLite too, where ltree doesn't exist. Reach for a closure table or ltree when you read large subtrees far more often than you move them (a product catalogue that's filtered by category on every page view is the classic case), and remember that both have to be kept in step with every insert, move and delete, by triggers or by application code. Many teams keep parent_id as the truth and rebuild the closure table from it with the recursive CTE above.

Run it on your own data

We ran all of this in Pilotbase with the three databases side by side, which is the quickest way to see where the dialects part: the same tree query in three tabs, three result grids. If a recursive query is slow, run EXPLAIN ANALYZE on it and paste the output into explainViewer: a Seq Scan on the table inside the recursive part, repeated once per level, is the missing parent index.

If you need a bigger tree to test against, our article on generating test data in SQL builds millions of rows with generate_series and recursive CTEs, and for date-based reports the calendar table article uses the same recursive trick to build one row per day on MySQL and SQLite.

Related: Fake data that looks real: generate_series, random() and a million test rows in SQL · A calendar table in SQL: one row per day for reports that don't skip empty days

Sources: PostgreSQL 18 documentation, WITH Queries (recursive queries, SEARCH and CYCLE, added in PostgreSQL 14) and the ltree module; MySQL 8.4 Reference Manual, WITH (Common Table Expressions): recursive CTEs, column types taken from the nonrecursive part, cte_max_recursion_depth; SQLite documentation, The WITH Clause (recursive CTEs, ORDER BY and LIMIT in the recursive select). Test data, SQL and timings are our own, run on 2026-10-23 on PostgreSQL 18.6, MySQL 8.4.13 and SQLite 3.50.4 in Docker on a desktop PC.