Helm7

Recursive CTE Explained: Graph Traversal in SQL

The Helm7 team · Published 15 November 2026 · Checked 16 November 2026 · 7 min read

recursive cte: intertwined tree roots showing natural branching patterns
Photo by Sharath G. on Pexels

A recursive CTE is the part of SQL that lets one query follow links, row after row, until it runs out of road. It is how you answer who reports to whom, what depends on what, and which records are connected to this one, without a graph database. The syntax is short, but three things go wrong in practice: loops, runaway growth and a LIMIT that does less than you hope. Here are working queries for each.

In short

  • A recursive CTE has a starting term, UNION ALL, and a recursive term that refers to the CTE. It ends when a round returns no rows.
  • Use the CYCLE clause (Postgres 14 and later) to stop loops, and filter out the flagged row.
  • Cycle detection does not limit width. Cap fan-out with a lateral subquery, cap depth in the recursive term and set a statement timeout.
  • A LIMIT in the parent query can stop recursion early, but the manual does not recommend relying on it in production, and sorting or joining the output defeats it.
  • Index the column you follow. Without it every hop scans the table.

What is a recursive CTE?

A common table expression, or CTE, is a named subquery you write at the top of a statement with WITH. A recursive CTE is one that refers to itself. Postgres runs it in rounds, feeding each round's output back in as the next round's input, and stops when a round produces nothing.

That makes it the natural tool for data that points at other data of the same kind. Org charts, category trees, bills of materials, comment threads and link graphs all fit. Anything where the number of hops is not known in advance fits as well, and that is exactly the case that ordinary joins cannot handle.

What are the two parts of a recursive CTE?

The PostgreSQL manual describes the shape: a non-recursive term, then UNION or UNION ALL, then a recursive term. Only the recursive term may refer to the CTE's own output. The first term is the starting point. The second says how to take one more step.

WITH RECURSIVE t(n) AS (
    VALUES (1)
  UNION ALL
    SELECT n+1 FROM t WHERE n < 100
)
SELECT sum(n) FROM t;
The counting example from the PostgreSQL manual: start at 1, add 1 until 100

The WHERE clause is what ends it. At 100 the recursive term returns no rows, the working table is empty, and Postgres stops. Every recursive CTE needs a condition like that, or a guarantee from the data that it will run dry.

On UNION against UNION ALL: with UNION ALL every row is kept. With UNION, Postgres discards rows that duplicate an earlier result row. That can stop a loop, but only when whole rows repeat. If you carry a depth counter, no two rows are ever identical, so UNION will not save you. Prefer UNION ALL and handle loops on purpose.

How do you walk a graph with a recursive CTE?

Store the graph as an edges table: one row per link, with a source, a destination and optionally a label. Foreign keys work too, as the join condition. The walk starts at one node and joins to the edges table each round.

CREATE TABLE edges (src bigint, dst bigint, label text);

WITH RECURSIVE reach(id, depth) AS (
  SELECT 1::bigint, 0
  UNION ALL
  SELECT e.dst, r.depth + 1
  FROM reach r
  JOIN edges e ON e.src = r.id
  WHERE r.depth < 3
)
SELECT id, min(depth) AS hops
FROM reach
GROUP BY id
ORDER BY hops, id;
Everything reachable from node 1 in at most three hops

Round zero holds node 1. Each later round joins the previous round's nodes to their outgoing edges and adds one to the depth. The final SELECT collapses duplicates, because a node reachable by two routes appears once per route. The min(depth) gives the shortest one.

Walking against the arrows is the same query with src and dst swapped. Walking both ways means joining on either column, and it makes loops far more likely, so the next section matters more.

How do you stop a recursive CTE going in circles?

Graphs have loops. If A links to B and B links back to A, a plain traversal walks A, B, A, B until your depth cap or your patience runs out. Since version 14, Postgres has built-in syntax for this.

WITH RECURSIVE reach(id, depth) AS (
  SELECT 1::bigint, 0
  UNION ALL
  SELECT e.dst, r.depth + 1
  FROM reach r
  JOIN edges e ON e.src = r.id
  WHERE r.depth < 3
) CYCLE id SET is_cycle USING path
SELECT id, min(depth) AS hops
FROM reach
WHERE NOT is_cycle
GROUP BY id;
The CYCLE clause tracks visited ids and flags a repeat
“The CYCLE clause specifies first the list of columns to track for cycle detection”
PostgreSQL documentation, Section 7.8, WITH queries

The manual adds that the cycle and path columns are implicitly added to the CTE's output. Postgres stops following a branch the moment it revisits a tracked value. The row that closes the loop is still returned, flagged is_cycle, so filter it out if you do not want it. We ran this against a small test graph with a loop from node 4 back to node 1 and it terminated cleanly with the depth cap well out of reach.

A related clause, SEARCH, adds a column you can sort by to get breadth-first or depth-first order. It orders the output. It does not change which rows are visited.

How do you cap depth and fan-out?

Cycle detection stops loops. It does not stop explosions. A node with 10,000 outgoing links will produce 10,000 rows in one round, and each of those can do the same. Three caps keep a traversal predictable.

Ways to bound a recursive traversal and what each one protects against
CapHowProtects againstCatch
DepthWHERE r.depth < 3 in the recursive termRunaway distanceDoes nothing about width
Fan-out per rowLATERAL subquery with ORDER BY and LIMIT nOne popular node flooding a roundYou choose which n links survive, so order them deliberately
Total rowsLIMIT in the final SELECT, or a counter in the CTEA huge result reaching the applicationMay not stop the work, see the next section
TimeSET LOCAL statement_timeoutAnything you forgotThe query fails instead of returning partial results

Here is the fan-out cap in code. Instead of a plain join, each row asks a lateral subquery for at most two outgoing edges, in a stable order.

WITH RECURSIVE reach(id, depth) AS (
  SELECT 1::bigint, 0
  UNION ALL
  SELECT e.dst, r.depth + 1
  FROM reach r
  CROSS JOIN LATERAL (
    SELECT dst FROM edges
    WHERE src = r.id
    ORDER BY dst
    LIMIT 2
  ) e
  WHERE r.depth < 3
) CYCLE id SET is_cycle USING path
SELECT id, depth FROM reach WHERE NOT is_cycle;
At most two outgoing edges per node per hop

An index on edges (src) makes each lateral lookup cheap. Without one, every hop scans the whole table, and a modest graph gets slow in a hurry.

Does LIMIT stop a recursive CTE early?

Sometimes, and the manual is careful about when. Postgres evaluates a WITH query lazily, so a LIMIT in the parent can end the recursion once enough rows have been fetched. This query would run for ever without its LIMIT and finishes instantly with it.

WITH RECURSIVE t(n) AS (
    SELECT 1
  UNION ALL
    SELECT n+1 FROM t
)
SELECT n FROM t LIMIT 100;
An infinite recursion that a parent LIMIT stops (from the PostgreSQL manual)
“PostgreSQL's implementation evaluates only as many rows of a WITH query as are actually fetched by the parent query.”
PostgreSQL documentation, Section 7.8, WITH queries

Read the next lines of the manual before you rely on it. It says using the trick in production is not recommended, because other systems might work differently. It also says the trick usually fails if the outer query sorts the recursive output or joins it to another table, because the outer query then tries to fetch everything anyway. So treat LIMIT as a test aid and a last backstop, and keep the depth and fan-out caps as the real guard.

How to build a safe recursive CTE traversal, step by step

  1. 1Index the join columnCreate an index on the column you follow, such as edges (src). Add one on dst too if you will walk backwards.
  2. 2Write the starting termSelect the start node with a depth of zero. Cast literals so both terms have the same column types, as in 1::bigint.
  3. 3Write the recursive termJoin the CTE to the edges table and add one to the depth. Use UNION ALL.
  4. 4Add the depth capPut WHERE r.depth < n in the recursive term. Start with 2 or 3 and raise it only when a real question needs more.
  5. 5Add the CYCLE clauseWrite CYCLE id SET is_cycle USING path after the closing bracket, and filter on NOT is_cycle in the final SELECT.
  6. 6Cap the fan-outReplace the plain join with a lateral subquery that orders and limits the outgoing edges per node.
  7. 7Collapse and limit the outputGROUP BY the node and take min(depth), then add a LIMIT. Run EXPLAIN ANALYZE on a realistic graph and set a statement timeout as the final guard.

Where this shows up in Helm7

We use exactly this pattern. When you switch on relationships for a database on the databases page, a traversal compiles to a single WITH RECURSIVE query with a CYCLE clause. The caps are a depth of 4, a fan-out of 50 per row per hop, 500 nodes in total and a five-second statement timeout. It runs as your application's own database role, so row level security applies to every hop.

You do not need Helm7 for any of this. Every query above runs on stock Postgres 14 or later. If you want to see how a traversal combines with vector search for retrieval, read GraphRAG on plain Postgres. To decide whether Postgres is the right home for a graph at all, the LLM memory database comparison sets it beside graph and vector databases.

Common questions

  • What is a recursive CTE used for?

    It follows links of unknown length. Common uses are org charts, category trees, bills of materials, dependency graphs and any traversal where the number of hops is not known in advance.

  • What is the difference between UNION and UNION ALL in a recursive CTE?

    UNION ALL keeps every row. UNION discards rows that duplicate an earlier result row, which can stop some loops but not if you carry a counter such as depth. The CYCLE clause is the reliable way to stop a loop.

  • Which Postgres version has the CYCLE clause?

    The CYCLE and SEARCH clauses arrived in PostgreSQL 14. On older versions you track the path in an array column and test for membership yourself.

  • Can a recursive CTE replace a graph database?

    For walks of a few hops over moderate graphs, yes. Very deep traversals over huge edge sets, or workloads built around graph algorithms, are where a dedicated graph database can pull ahead.

Sources

  1. PostgreSQL documentation: WITH queries
  2. PostgreSQL documentation: row security policies

Run your entire app stack, end to end, from $12 a month.

App, Postgres, auth, storage, jobs and domains on one platform, planned and priced before anything changes.

More from the blog