SQL Recursive CTE Explained: Anchor, Recursive Step and Cycles

Some questions cannot be answered with a fixed number of joins. "Who reports to this manager, at any depth?" "Which parts go into this product, including the parts of its parts?" Each needs as many joins as the data is deep, and nobody knows that depth when writing the query. A recursive common table expression is SQL's answer: a query that keeps joining its own previous output until nothing new comes back. Interviewers use it to check that you can go past GROUP BY, and that you know what happens when the data contains a loop.

The problem it solves

Hierarchies and graphs are usually stored as an adjacency list: each row names its parent, its manager or the thing it feeds from. One self-join finds the direct children. Two self-joins find the grandchildren. To find every descendant you would need one join per level, and the number of levels is in the data, not in the schema.

Without recursion the options are poor: one query per level from application code, a hard-coded chain of joins, or a denormalised path column that must be kept up to date. A recursive CTE walks the hierarchy in one statement.

The intuition

Start with a plain CTE. WITH name AS (SELECT ...) gives a subquery a name, so the main query can read top to bottom instead of inside out, and can use the same result twice.

Add RECURSIVE, and the CTE may refer to itself. It then has two parts joined by UNION ALL:

1. The anchor: a normal query that produces the starting rows.
2. The recursive step: a query that joins the table to the CTE itself.

The engine runs it in passes. The anchor's rows are the first pass. Each following pass runs the recursive step against only the rows the previous pass produced and appends what it finds. When a pass returns no rows, the recursion stops on its own, and the CTE's result is everything every pass produced. It is breadth-first search written in SQL: the rows of each pass are the next frontier.

That stopping rule is also the danger. If the data contains a cycle, every pass finds rows again and the query never ends. There are two standard guards:

• A depth cap: carry a counter column and add WHERE depth < limit to the recursive step.
• A visited check: use UNION instead of UNION ALL. In SQLite and PostgreSQL, UNION drops any row identical to one already produced, so a walk that only carries the node name stops once no new node appears. It stops working as soon as the row also carries a counter or a path, because those rows are never identical.

PostgreSQL, MySQL 8 and SQLite spell it WITH RECURSIVE; SQL Server and Oracle write recursive CTEs without the keyword. The SQL cheat sheet lists the shape next to the other query forms.

Watch it run

The animation uses five gates, each naming the one it feeds from; the chain is in the data, not in the schema. A recursive CTE starts with an anchor, the rows the walk begins from: the spring. The recursive arm joins the table back onto what the previous pass produced, and finds the mill. Only the newest rows feed the next pass, so nothing is walked twice: the mill leads to the town. One more hop reaches the harbour. The next pass finds nothing to join, so the recursion stops on its own. The quarry was never reached, because it feeds nothing the anchor could get to. Then the animation breaks it: let the harbour feed the mill, and every pass finds the same rows again. So a recursive CTE over graph data needs a visited set, or a depth cap.

The code

Run with Python's sqlite3 module on SQLite 3.37. The lesson's gate table, walked downstream from the spring, carrying the hop count and the path as extra columns:

import sqlite3

db = sqlite3.connect(":memory:")
db.executescript("""
  CREATE TABLE gate (name TEXT PRIMARY KEY, feeds TEXT);   -- feeds = the gate upstream
  INSERT INTO gate VALUES ('spring', NULL), ('mill', 'spring'), ('town', 'mill'),
                          ('harbour', 'town'), ('quarry', NULL);
""")

DOWNSTREAM = """
  WITH RECURSIVE downstream(name, hops, path) AS (
    SELECT name, 0, name FROM gate WHERE name = ?                    -- anchor
    UNION ALL
    SELECT g.name, d.hops + 1, d.path || ' > ' || g.name             -- one step further
    FROM gate g JOIN downstream d ON g.feeds = d.name
  )
  SELECT name, hops, path FROM downstream ORDER BY hops"""
for row in db.execute(DOWNSTREAM, ("spring",)):
    print(row)
# ('spring', 0, 'spring')
# ('mill', 1, 'spring > mill')
# ('town', 2, 'spring > mill > town')
# ('harbour', 3, 'spring > mill > town > harbour')

A recursive CTE without a table, generating the numbers 1 to 5, and a plain CTE with two named steps, finding the gate that neither is fed nor feeds anything:

print(db.execute("""
  WITH RECURSIVE n(i) AS (SELECT 1 UNION ALL SELECT i + 1 FROM n WHERE i < 5)
  SELECT group_concat(i) FROM n""").fetchone())          # ('1,2,3,4,5',)

print(db.execute("""
  WITH sources AS (SELECT name FROM gate WHERE feeds IS NULL),
       fed AS (SELECT DISTINCT feeds AS name FROM gate WHERE feeds IS NOT NULL)
  SELECT name FROM sources WHERE name NOT IN (SELECT name FROM fed)""").fetchall())
# [('quarry',)]

Now the animation's loop: the harbour feeds the mill. With UNION ALL and no guard the walk never ends; LIMIT cuts it off after nine rows so it can be printed. A depth cap stops it at five hops, and UNION over the node name alone stops it once every node has been seen:

db.execute("UPDATE gate SET feeds = 'harbour' WHERE name = 'mill'")   # mill now fed by the harbour: a loop
print(db.execute("""
  WITH RECURSIVE walk(name, hops) AS (
    SELECT 'mill', 0
    UNION ALL
    SELECT g.name, w.hops + 1 FROM gate g JOIN walk w ON g.feeds = w.name)
  SELECT group_concat(name, ' > ') FROM (SELECT name FROM walk LIMIT 9)""").fetchone())
# ('mill > town > harbour > mill > town > harbour > mill > town > harbour',)

print(db.execute("""
  WITH RECURSIVE walk(name, hops) AS (
    SELECT 'mill', 0
    UNION ALL
    SELECT g.name, w.hops + 1 FROM gate g JOIN walk w ON g.feeds = w.name
    WHERE w.hops < 5)                                      -- depth cap
  SELECT count(*), max(hops) FROM walk""").fetchone())    # (6, 5)

print(db.execute("""
  WITH RECURSIVE seen(name) AS (
    SELECT 'mill'
    UNION                                                  -- not ALL: repeated rows are dropped
    SELECT g.name FROM gate g JOIN seen s ON g.feeds = s.name)
  SELECT group_concat(name, ', ') FROM seen""").fetchone())   # ('mill, town, harbour',)

Checked against a breadth-first search in Python on 300 seeded random directed graphs with cycles and self-loops. The UNION walk must return exactly the reachable nodes, and a depth-capped UNION ALL walk with min(hops) must return every shortest distance:

import random
from collections import deque

random.seed(23)
ok = True
for _ in range(300):
    n = random.randint(1, 12)
    edges = {(random.randrange(n), random.randrange(n)) for _ in range(random.randint(0, 20))}
    g = sqlite3.connect(":memory:")
    g.execute("CREATE TABLE edge (src INTEGER, dst INTEGER)")
    g.executemany("INSERT INTO edge VALUES (?, ?)", sorted(edges))
    start = random.randrange(n)
    got = {r[0] for r in g.execute("""
      WITH RECURSIVE seen(node) AS (
        SELECT ? UNION SELECT e.dst FROM edge e JOIN seen s ON e.src = s.node)
      SELECT node FROM seen""", (start,))}
    dist, q = {start: 0}, deque([start])                    # brute force: plain BFS
    while q:
        u = q.popleft()
        for a, b in edges:
            if a == u and b not in dist:
                dist[b] = dist[u] + 1
                q.append(b)
    ok &= got == set(dist)
    shortest = dict(g.execute("""
      WITH RECURSIVE walk(node, hops) AS (
        SELECT ?, 0
        UNION ALL
        SELECT e.dst, w.hops + 1 FROM edge e JOIN walk w ON e.src = w.node WHERE w.hops < ?)
      SELECT node, min(hops) FROM walk GROUP BY node""", (start, n)).fetchall())
    ok &= shortest == dist
print(ok)                                                  # True

The complexity

• Tree or forest: each row is produced once, so the work is proportional to the rows reached. An index on the join column, feeds here, turns each pass into lookups instead of scans.
• UNION visited walk: each node is added once, like BFS.
• Depth-capped UNION ALL on a graph: it enumerates walks, not nodes, and their number can grow exponentially with the cap.

Where it goes wrong

• No guard on graph data. One cycle from bad data and the query runs until something kills it.
• Expecting UNION to stop a cycle while carrying a path or counter. Those rows differ on every pass, so nothing is deduplicated.
• Putting the depth cap in the outer query. The recursion still runs forever; the condition must be in the recursive step.
• Aggregates in the recursive step. Most engines forbid them; aggregate in the outer query.
• Relying on output order. Add ORDER BY in the outer query, as the first example does with hops.

When it shows up in interviews

It shows up in SQL rounds as "find every employee under this manager", "expand a bill of materials" or "generate a series of dates". It builds on joins, and the ranking questions that come next usually want window functions. The traversal itself is breadth-first search, and the cycle problem is the one from detecting cycles in graphs.

How to say it in an interview

"The depth of the hierarchy is in the data, so I use a recursive CTE. The anchor selects the starting row; the recursive step joins the table to the rows the previous pass produced; the engine repeats until a pass returns nothing, which is effectively a breadth-first search. Because graph data can contain cycles I add a guard: a depth cap in the recursive step, or UNION over just the node id so repeated rows are dropped. I index the join column so each pass is a set of lookups, and I order the result in the outer query."