Recursive CTE in PostgreSQL for trees and cycles
A recursive CTE in PostgreSQL runs as a loop over a working table. Tracking paths on a graph of just 30 nodes grew its result from 30 rows to 88,572.
On a dependency graph with 30 reachable nodes, one recursive CTE returns 30 rows and a slightly different one returns 88,572. Add a cycle and there is no upper bound at all. Against a table of six rows, a walk that counted its hops ran until it hit a 16 MB cap set for this experiment:
ERROR: temporary file size exceeds temp_file_limit (16384kB)A stock postgres:17 container reports temp_file_limit as -1 and statement_timeout as 0, so
without that cap nothing inside PostgreSQL would have stopped the query.
Recursive CTEs have a reputation for being clever and hard to reason about. They become much easier
once you know the loop PostgreSQL runs. That loop accounts for both results, along with the depth
guard and the CYCLE clause.
Start with a tree, the friendly case. Each folder points at its parent:
CREATE TABLE folders (
id integer PRIMARY KEY,
parent_id integer REFERENCES folders (id),
name text NOT NULL
);
INSERT INTO folders VALUES
(1, NULL, 'root'),
(2, 1, 'docs'),
(3, 1, 'src'),
(4, 3, 'api'),
(5, 3, 'web'),
(6, 2, 'adr'),
(7, 4, 'handlers'),
(8, 7, 'billing');A fixed number of self-joins sees a fixed number of levels. A recursive CTE has two terms joined by
UNION ALL, and it keeps going until the data runs out:
WITH RECURSIVE subtree AS (
SELECT id, name, 0 AS depth
FROM folders
WHERE id = 3
UNION ALL
SELECT f.id, f.name, s.depth + 1
FROM folders AS f
JOIN subtree AS s ON f.parent_id = s.id
)
SELECT id, name, depth FROM subtree ORDER BY depth, id; id | name | depth
----+----------+-------
3 | src | 0
4 | api | 1
5 | web | 1
7 | handlers | 2
8 | billing | 3The word "recursive" misleads here. The
PostgreSQL manual
says these queries are "evaluated iteratively". The first term runs once and its rows go into a
temporary working table. Then the second term runs repeatedly, and each time the name subtree
means the contents of the working table, which holds the previous pass and nothing older. New rows
join the result and replace the working table. An empty pass ends the loop.
The working table holds only the last pass
-
Anchor
Reads: folder id = 3
Adds to result: src
-
Pass 1
Reads: src
Adds to result: api, web
-
Pass 2
Reads: api, web
Adds to result: handlers
-
Pass 3
Reads: handlers
Adds to result: billing
-
Pass 4
Reads: billing
Finds no children, so the loop stops
A cycle never empties the working table
logging, then config, then logging again, each time with a higher hop count, so UNION sees no duplicate to discard.
The second term has limits. PostgreSQL rejects an aggregate there with
aggregate functions are not allowed in a recursive query's recursive term, and a LEFT JOIN with
the self-reference on the nullable side fails with
recursive reference to query "t" must not appear within an outer join. Compute totals in the outer
query, after the walk finishes.
A counter in the WHERE clause of the second term caps how far a walk can go:
SELECT f.id, f.name, s.depth + 1
FROM folders AS f
JOIN subtree AS s ON f.parent_id = s.id
WHERE s.depth < 2This is a cheap safety net against bad data, but it returns a correct-looking answer with rows
missing. On this table the guard drops billing and raises no error. If a guard exists for safety,
report when it fired. Checking whether any row at the limit still has children gives you that
signal, and here it flags handlers.
The manual also suggests a LIMIT in the outer query for testing a query that might loop. It works
because PostgreSQL evaluates only the rows the parent fetches, but the same page advises against
relying on it in production, and it usually stops working once the outer query sorts or joins the
results.
Row order from a recursive CTE is unspecified unless you ask for one. For an indented tree listing,
the SEARCH clause adds a sort column:
WITH RECURSIVE subtree AS (
SELECT id, name, 0 AS depth FROM folders WHERE parent_id IS NULL
UNION ALL
SELECT f.id, f.name, s.depth + 1
FROM folders AS f
JOIN subtree AS s ON f.parent_id = s.id
) SEARCH DEPTH FIRST BY name SET visit_order
SELECT repeat(' ', depth) || name AS tree
FROM subtree
ORDER BY visit_order;root
docs
adr
src
api
handlers
billing
webSEARCH BREADTH FIRST BY name returns the levels in order instead: root, then docs and src, and so
on. Both forms only sort the finished output. The manual says the clause does not control the order in
which the query visits rows.
Here is a package dependency table where logging and config depend on each other, which a tree
cannot do:
CREATE TABLE package_deps (
package text NOT NULL,
depends_on text NOT NULL,
PRIMARY KEY (package, depends_on)
);
INSERT INTO package_deps VALUES
('app', 'auth'),
('app', 'http'),
('auth', 'http'),
('http', 'logging'),
('logging', 'config'),
('config', 'logging');A walk from app that carries a hops counter is what hit the temp_file_limit cap. Limited with
LIMIT 12, its output ends with config and logging trading places at 5 hops, then 6, and it would continue
forever. Swapping UNION ALL for UNION does not help, because the growing counter makes every row
unique.
Remove the counter and UNION does work. A pass that finds only rows already seen adds nothing, the
working table empties, and you get auth, config, http and logging once each. That is the
right query when the question is "what can this reach?".
When you need the hop count or the route, use the CYCLE clause. It tracks the listed columns along
each route and stops following a route once it revisits a value:
WITH RECURSIVE reach AS (
SELECT depends_on AS package, 1 AS hops
FROM package_deps
WHERE package = 'app'
UNION ALL
SELECT d.depends_on, r.hops + 1
FROM package_deps AS d
JOIN reach AS r ON d.package = r.package
) CYCLE package SET is_cycle USING path
SELECT package, hops, is_cycle
FROM reach
ORDER BY hops, package; package | hops | is_cycle
---------+------+----------
auth | 1 | f
http | 1 | f
http | 2 | f
logging | 2 | f
config | 3 | f
logging | 3 | f
config | 4 | f
logging | 4 | t
logging | 5 | tThe two t rows are the visits that closed the loop, so they repeat a package already on their
route. Filter them with WHERE NOT is_cycle before you count anything. The path column holds the
route as an array, which is useful for explaining why one package pulls in another.
A pass costs one join between the working table and the base table, which leaves two things to check.
The timings below are single runs of postgres:17 in Docker on a laptop.
The first is the join itself. Walking a 156-row subtree in a 500,000-row table with no index on
parent_id, the plan hash-joined a full sequential scan in each of its 4 passes and took 222.9 ms.
After CREATE INDEX ON big_folders (parent_id), the same query used a nested loop with an index scan
and took 0.5 ms. How database indexes work covers why that lookup
is so much cheaper, and the database track guide covers reading a plan when a
walk seems slow.
The second is what the working table contains. CYCLE keeps every distinct route as its own row,
because two routes to one node carry different paths. The test graph has 10 layers of 3 nodes each,
where each node depends on all 3 nodes in the next layer and a root points at the first layer. That
makes 30 reachable nodes and 84 edges:
rows execution
UNION, no hop count 30 0.9 ms
CYCLE, with path 88,572 521.4 msThe second number is the sum of routes per layer, 3 + 9 + 27 up to 3^10, which is
(3^11 - 3) / 2 = 88,572. Add one more layer and it roughly triples, while the UNION version gains
3 rows.
On 30 nodes,
UNIONreturned 30 rows andCYCLEreturned 88,572, becauseUNIONcounts nodes and path tracking counts routes.
The cost of a tree walk rarely surprises anyone, because a tree has exactly one route to each node. On a graph with many diamonds, routes grow exponentially with depth, so a query that passed review on a small fixture can still run out of memory or temp space on real data.
For a tree enforced by a foreign key, use UNION ALL with an index on the parent column and carry
whatever depth you need. A bad import can still create a loop if the rows point at each other, so add
a guard where that risk is real, and make it visible when it fires.
For a graph where you need the set of reachable nodes, drop the counters and use UNION. PostgreSQL
then does the deduplication, and the working table stays small.
For a graph where you need hop counts or routes, use CYCLE or a path array, and check how many
routes your real data has before shipping, since each one becomes a row.
A walk with no cycle guard terminates on any acyclic sample, so a loop-free fixture proves nothing. "Follow the Money, Mind the Loop", one of the SQL exercises on Katabench, keeps its cycles out of the visible data for that reason.
Practice Databases & EF Core
- Open in the editor: Filter Before You Fetch
EF Core and SQL Easy Free, no account needed
Filter Before You Fetch
Filter measurements on the database, not after loading the whole table.
- Open the Pro kata: Everyone Under the CTO
EF Core and SQL Hard Katabench Pro
Everyone Under the CTO
Walk a self-referencing org chart to any depth with WITH RECURSIVE and a depth counter.
More like this: EF Core practice →