CTEs and recursive queries

Article.

A common table expression names an intermediate result so a query reads as a sequence of steps instead of a nest of subqueries. That much is presentation. The parts worth knowing are that a CTE used to be an optimisation fence and sometimes still is, and that WITH RECURSIVE is a genuine loop — the only one in standard SQL.

The readability case

Here is the same question written twice: which customers spent more than twice the average last quarter?

-- Nested. You read it inside-out, and the middle is load-bearing.
SELECT c.name, t.total
FROM customer c
JOIN (
    SELECT customer_id, sum(amount) AS total
    FROM invoice
    WHERE paid_at >= date_trunc('quarter', now()) - interval '3 months'
      AND paid_at <  date_trunc('quarter', now())
    GROUP BY customer_id
) t ON t.customer_id = c.id
WHERE t.total > (
    SELECT avg(total) * 2 FROM (
        SELECT sum(amount) AS total FROM invoice
        WHERE paid_at >= date_trunc('quarter', now()) - interval '3 months'
          AND paid_at <  date_trunc('quarter', now())
        GROUP BY customer_id
    ) x
);

The same query, named

The subquery is written twice, so it can drift. The CTE version names it once:

WITH last_quarter AS (
    SELECT customer_id, sum(amount) AS total
    FROM invoice
    WHERE paid_at >= date_trunc('quarter', now()) - interval '3 months'
      AND paid_at <  date_trunc('quarter', now())
    GROUP BY customer_id
),
threshold AS (
    SELECT avg(total) * 2 AS cutoff FROM last_quarter
)
SELECT c.name, q.total
FROM last_quarter q
JOIN customer c ON c.id = q.customer_id
CROSS JOIN threshold t
WHERE q.total > t.cutoff;

Top to bottom, each step named, the definition in one place. That is most of why people use them.

The optimisation fence

This is the part that separates people who have used CTEs from people who have debugged them.

Before Postgres 12, a CTE was always materialised. The planner computed it fully, into a temporary result, and could not push conditions from the outer query into it. WITH was effectively a barrier.

That behaviour bites like this:

WITH all_invoices AS (
    SELECT * FROM invoice          -- 40 million rows
)
SELECT * FROM all_invoices WHERE id = 12345;

On Postgres 11, that materialises forty million rows and then finds one. The same query without the CTE is an index lookup. The CTE turned a 0.1ms query into a sequential scan of the whole table — and nothing in the SQL says so.

What changed in 12

Postgres 12 inlines a CTE by default, so the planner can push the predicate down and the query above becomes the index lookup you expected. But only when all three hold:

• it is referenced exactly once,
• it is not recursive,
• it has no side effects (no INSERT/UPDATE/DELETE inside it).

Referenced twice, it is materialised again. That is usually what you want — computing it once and reusing it — but it means the same CTE changes execution strategy when someone adds a second reference, with no other edit.

You can say which you want:

WITH RECURSIVE ok AS MATERIALIZED (          -- force the fence
    SELECT ...
), fast AS NOT MATERIALIZED (                -- force inlining
    SELECT ...
)

MATERIALIZED is the right choice when the CTE is expensive and referenced several times, or when it calls a volatile function you want evaluated exactly once. NOT MATERIALIZED is the escape hatch when the planner’s default is costing you a predicate pushdown.

Confirming which you got

Check, do not assume. The plan tells you which happened:

EXPLAIN ANALYZE
WITH x AS (SELECT * FROM invoice) SELECT * FROM x WHERE id = 12345;

A CTE Scan node in the output means it was materialised. No CTE Scan means it was inlined. See Reading a query plan.

Other engines differ, and the difference is not cosmetic. SQL Server and Oracle inline CTEs as a rule; MySQL 8 also inlines by default. Porting a query that relied on the fence — a CTE calling a volatile function once, say — will silently change its behaviour rather than fail.

WITH RECURSIVE

The recursive form is a loop, and the syntax hides that badly. It has three parts:

WITH RECURSIVE subordinates AS (
    -- 1. anchor: the starting rows, evaluated once
    SELECT id, manager_id, name, 1 AS depth
    FROM employee
    WHERE id = 42

    UNION ALL

    -- 2. recursive term: joins against the CTE itself
    SELECT e.id, e.manager_id, e.name, s.depth + 1
    FROM employee e
    JOIN subordinates s ON e.manager_id = s.id
)
-- 3. the outer query, run once the loop is finished
SELECT * FROM subordinates ORDER BY depth, name;

How it actually executes

The mental model that makes recursive CTEs predictable is the working table:

1. Run the anchor. Put its rows in the working table and in the result.
2. Run the recursive term, with subordinates bound to only the working table — not to everything accumulated so far.
3. Whatever came back becomes the new working table, and is appended to the result.
4. Repeat until step 2 returns no rows.

That step 2 detail is the one people get wrong. The recursive term does not see the full accumulated result; it sees only the previous iteration’s output. A query written as though it can look back at everything found so far will quietly return the wrong rows.

UNION ALL versus UNION follows from this. UNION deduplicates against the accumulated result on every iteration, which is slower and is sometimes the only thing stopping a cyclic graph from looping forever. UNION ALL does not deduplicate — faster, and it will loop forever on a cycle.

Cycles, and the query that never returns

A hierarchy is a tree until someone’s manager field points at their own subordinate. Then UNION ALL recurses until the server runs out of memory or disk.

Postgres 14 added a declarative guard:

WITH RECURSIVE subordinates AS (
    SELECT id, manager_id, name FROM employee WHERE id = 42
    UNION ALL
    SELECT e.id, e.manager_id, e.name
    FROM employee e JOIN subordinates s ON e.manager_id = s.id
) CYCLE id SET is_cycle USING path
SELECT * FROM subordinates WHERE NOT is_cycle;

CYCLE id SET is_cycle USING path tracks the ids visited in path, flags the row where one repeats, and stops descending there. Before 14, you carried the path yourself:

SELECT e.id, ..., s.path || e.id
FROM employee e
JOIN subordinates s ON e.manager_id = s.id
WHERE NOT e.id = ANY(s.path)      -- the manual cycle guard

Carry a depth column and cap it regardless. A cycle guard protects against a loop; a depth cap protects against a hierarchy that is legitimately 400 levels deep and a query that should never have been asked.

Where this goes wrong in production

The unbounded recursion in a request handler. A recursive CTE over a graph has no useful upper bound on work. One malformed row — a cycle introduced by a bad import — turns an endpoint into a query that pins a CPU and holds a connection until the statement timeout fires. If you have no statement timeout, it holds it until someone notices.

Set one, specifically for the endpoints that run recursion:

SET LOCAL statement_timeout = '2s';

Recursion where a different data structure belonged. Recursive CTEs are fine for a few thousand rows and shallow depth. For deep or wide graph traversal run repeatedly, the cost is real and the alternatives are better: a materialised path or ltree column for hierarchies that are read far more than written, a closure table when you need arbitrary ancestor queries, or an actual graph database when traversal is the workload.

The senior answer to “would you use a recursive CTE for this?” is often no, and the reason is that the shape of the query hides how much work it does.

Related

• Window functions - window functions, the other half of analytical SQL
• Reading a query plan - reading the plan to see which strategy you got
• Sharding and Partitioning - why recursion and sharding do not mix