Skip to content
Katabench
Try free
8 min read The Katabench team

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:

Text
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.

The working table loop

Start with a tree, the friendly case. Each folder points at its parent:

SQL
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:

SQL
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;
Text
 id |   name   | depth
----+----------+-------
  3 | src      |     0
  4 | api      |     1
  5 | web      |     1
  7 | handlers |     2
  8 | billing  |     3

The 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

  1. Anchor

    Reads: folder id = 3

    Adds to result: src

  2. Pass 1

    Reads: src

    Adds to result: api, web

  3. Pass 2

    Reads: api, web

    Adds to result: handlers

  4. Pass 3

    Reads: handlers

    Adds to result: billing

  5. 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.

Each pass joins the table to the previous pass only. The loop ends when a pass returns zero rows.

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.

Depth guards stop the walk without telling you

A counter in the WHERE clause of the second term caps how far a walk can go:

SQL
    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 < 2

This 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.

SEARCH orders the output

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:

SQL
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;
Text
root
  docs
    adr
  src
    api
      handlers
        billing
    web

SEARCH 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.

Cycles: when rows stop being duplicates

Here is a package dependency table where logging and config depend on each other, which a tree cannot do:

SQL
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:

SQL
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;
Text
 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 | t

The 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.

The cost follows the working table

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:

Text
                      rows     execution
UNION, no hop count     30        0.9 ms
CYCLE, with path    88,572      521.4 ms

The 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, UNION returned 30 rows and CYCLE returned 88,572, because UNION counts 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.

Choosing between UNION, a guard and CYCLE

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

More like this: EF Core practice →

Get new katas and .NET tips in your inbox

A short note when fresh kata land, plus the C# and performance tricks behind the grading. No spam, unsubscribe anytime.