Recursive CTEs

The idea

A recursive CTE is a loop written as a query. You hand it a starting set of rows, the anchor, and one rule for turning rows into more rows. The database applies that rule round after round, and each round works only on what the round before it produced.

When a round produces nothing, the loop is finished, and everything gathered along the way is the answer. That is how you walk a hierarchy whose depth you don't know in advance: managers, folders, parts inside parts, flight legs.

The catch is the last sentence. If the data contains a ring, no round is ever empty.

Walk the org chart, round by round

How it works

Three parts, always in this order. The anchor term runs once and produces the first rows. The recursive term names the CTE itself and joins it to some edge table. The union between them glues the rounds together.

The important subtlety: inside the recursive term, the CTE name does not mean "everything so far". It means the working table: only the rows the previous round produced. The engine runs the recursive term, appends the output to the result, replaces the working table with that output, and repeats. An empty round empties the working table, and the loop ends.

WITH RECURSIVE walk (id, name, depth, path, seen) AS (

    -- anchor term: runs once, the rows the walk starts from
    SELECT e.id, e.name, 0, e.name, ARRAY[e.id]
    FROM   emp e
    WHERE  e.name = 'Ada'

    UNION ALL

    -- recursive term: joins the PREVIOUS round back to the edges
    SELECT c.id,
           c.name,
           w.depth + 1,
           w.path || ' > ' || c.name,
           w.seen || c.id
    FROM   walk w
    JOIN   reports_to r ON r.manager_id = w.id
    JOIN   emp        c ON c.id = r.employee_id
    WHERE  w.depth < 32            -- depth guard: a hard ceiling
      AND  NOT c.id = ANY(w.seen)    -- path guard: never re-enter a node
)
SELECT depth, path FROM walk ORDER BY depth, path;

Postgres flavour. WITH RECURSIVE is also SQLite and MySQL 8; SQL Server writes plain WITH and caps depth with OPTION (MAXRECURSION n). Without arrays, the portable path guard is a delimited string: strpos(w.path, '>' || c.name || '>') = 0.

If it helps to see the loop unrolled, this is the same machine in Python:

def recursive_cte(anchor_rows, step, distinct=False):
    result  = list(anchor_rows)
    working = list(anchor_rows)      # the working table: last round ONLY
    seen    = set(anchor_rows)

    while working:                   # a round that adds nothing ends it
        produced = []
        for row in working:
            for child in step(row):  # the recursive term's join
                if distinct:         # UNION instead of UNION ALL
                    if child in seen:
                        continue
                    seen.add(child)
                produced.append(child)
        result += produced
        working = produced           # NOT result -- only the new rows
    return result

Cost

The join key on the edge table must be indexed: every round is a fresh lookup per frontier row. The trade-off: a recursive CTE recomputes the walk on every query, but keeps writes cheap and the data normalised. A closure table or a materialised path column flips that: reads become one index range scan, writes have to maintain the derived rows.

Watch out for

• The working table is not the result. Inside the recursive term the CTE holds only the previous round's rows, so you cannot ask "have I ever emitted this node?" there. Global de-duplication has to come from UNION, or you carry the visited set along each branch as an array or delimited string.
• UNION stops cycles only by accident. It de-duplicates, so a round that only revisits nodes produces nothing new and the loop ends. But add a depth or path column and every row is unique again: the dedup never fires, and you are back to an infinite walk with a sort on top.
• Ship a guard, always. A WHERE w.depth < n in the recursive term, or a path check, or Postgres 14+'s CYCLE id SET is_cycle USING p. Engine limits are a fire alarm, not a design: MySQL's cte_max_recursion_depth (1000) and SQL Server's MAXRECURSION (100) raise an error and throw away the result. Postgres has no limit at all and will simply run until it fills a disk.
• DAGs multiply rows quietly. With UNION ALL, a node reachable by three distinct paths is emitted three times, at possibly different depths. That is correct path enumeration, and it is usually not what the ticket asked for. Dedupe with SELECT DISTINCT ON (id) ... ORDER BY id, depth outside the CTE.
• The recursive term has rules. It may reference the CTE exactly once, not inside a subquery or on the nullable side of an outer join, and (in Postgres) it may not contain ORDER BY, LIMIT, DISTINCT or an aggregate. Sort and limit the final SELECT instead, and if you forget the word RECURSIVE, the error is a puzzling relation "walk" does not exist.

Worked example

A reporting-lines report starts timing out. The query walks down from the CEO with a depth guard of 5, and it returns 10 rows for a company everyone knows is four levels deep.

So you look at the shape of the output rather than the plan. Rounds 0 through 3 behave: one row, then two, then three, then one. Gus at depth 3, the bottom. Round 4 should have been empty. Instead it produces Bo again, at depth 4, with the path Ada > Bo > Dee > Gus > Bo. A repeated name inside a single path names the offending edge outright: someone added a reports_to row saying Gus manages Bo, and Bo already sits above Gus. Round 6 hits depth < 5 and stops: the guard, not the data, is what ended the query.

Two fixes, and you want both: delete the bad link, and add AND NOT c.id = ANY(w.seen) so the next one closes the ring instead of the connection pool. Try it in the demo above: turn on the bad link, watch the depth counter climb past 3, then switch the path guard on.

Check yourself