Recursive CTE Plan Shapes #

A WITH RECURSIVE query walks an org chart from one manager down to all reports. For a team of 40 it returns instantly. For the head of a division with 30,000 reports it takes 25 seconds, and the plan shows a hash join inside the recursive part building a hash table over all 4 million employees on every iteration.

Non-recursive CTEs are inlined or materialized as described in CTE and subquery planning. Recursive CTEs are always executed as a loop, and their plans have a fixed skeleton with one weak point: the planner cannot know how many iterations or rows the recursion will produce.

The Planner Condition #

A recursive CTE has a non-recursive term and a recursive term joined by UNION or UNION ALL:

WITH RECURSIVE reports AS (
  SELECT id, manager_id, 1 AS depth FROM employees WHERE id = 7001      -- non-recursive term
  UNION ALL
  SELECT e.id, e.manager_id, r.depth + 1
  FROM employees e JOIN reports r ON e.manager_id = r.id                  -- recursive term
)
SELECT count(*) FROM reports;

Execution is iterative:

  1. Run the non-recursive term; put its rows in the working table and in the result.
  2. Run the recursive term with the working table as input — it appears in the plan as a WorkTable Scan — producing the next level.
  3. Replace the working table with the new rows and repeat until an iteration produces nothing.

The plan shows this as a Recursive Union node with two children, typically under a CTE Scan. With UNION (not ALL), Recursive Union also keeps a hash table of rows already produced to discard duplicates, which is how cycles terminate — at the cost of memory.

The planner must plan the recursive term once, before knowing how big the working table will be at any iteration. It estimates the working table as the non-recursive term’s row estimate multiplied by recursive_worktable_factor (PostgreSQL 15+, default 10). For a start of one row, every iteration is planned as if it held 10 rows — and the join algorithm inside the recursive term is chosen for that size, whether the real level holds 3 rows or 30,000.

The loop inside a Recursive Union A stack of plan nodes. CTE Scan reads the final result. Recursive Union runs the non-recursive term once, then repeats the recursive term. The recursive term joins employees to a WorkTable Scan holding the previous level. The join inside the recursive term is planned once for an estimated working table size. CTE Scan on reports reads the accumulated result Recursive Union loops until a level is empty Index Scan (non-recursive term) the starting row(s) Join in recursive term planned once for all iterations WorkTable Scan on reports previous level's rows working table estimate = start rows × recursive_worktable_factor

Annotated EXPLAIN Evidence #

EXPLAIN (ANALYZE, BUFFERS) <the query above, id = 20>;
Aggregate  (actual time=25104.2..25104.2 rows=1 loops=1)
  ->  CTE Scan on reports  (actual time=0.03..25098.6 rows=30412 loops=1)
        CTE reports
          ->  Recursive Union  (actual time=0.02..25090.1 rows=30412 loops=1)
                ->  Index Scan using employees_pkey on employees  (actual rows=1 loops=1)
                      Index Cond: (id = 20)
                ->  Hash Join  (actual time=2104.2..2508.4 rows=3041 loops=10)
                      Hash Cond: (e.manager_id = r.id)
                      ->  Seq Scan on employees e  (actual rows=4000012 loops=10)
                      ->  Hash  (actual rows=3041 loops=10)
                            ->  WorkTable Scan on reports r  (actual rows=3041 loops=10)
Execution Time: 25106.8 ms
-- loops=10: ten levels of hierarchy
-- the recursive term scans all 4M employees on every level
-- planned for a 10-row working table (1 × recursive_worktable_factor), yet chose a hash join

The same query with an index on manager_id:

CREATE INDEX CONCURRENTLY employees_manager_id_idx ON employees (manager_id);
                ->  Nested Loop  (actual time=0.02..3.9 rows=3041 loops=10)
                      ->  WorkTable Scan on reports r  (actual rows=3041 loops=10)
                      ->  Index Scan using employees_manager_id_idx on employees e
                            (actual rows=1 loops=30412)
                            Index Cond: (manager_id = r.id)
Execution Time: 48.2 ms
-- each level probes the index once per row in the previous level
Reading a recursive CTE plan Four plan lines are annotated. Recursive Union with loops showing the number of levels. The join inside the recursive term with loops equal to the depth. A Seq Scan on employees with loops ten meaning the full table was read per level. The WorkTable Scan rows per loop showing the average level size. Recursive Union (rows=30412) total rows across all levels Hash Join … loops=10 recursion depth = 10 levels Seq Scan on employees e (rows=4000012 loops=10) whole table read per level WorkTable Scan (rows=3041 loops=10) average level size loops on the recursive term's nodes count iterations, not rows

Step-by-Step Resolution #

  1. Read the depth from loops on the nodes under the recursive term, and the level size from the WorkTable Scan rows per loop.

  2. Check whether the recursive term probes or scans. A Seq Scan with loops equal to the depth reads the whole table per level. An index scan with loops equal to the total result rows probes per parent.

  3. Index the join column of the recursive term — usually the parent pointer (manager_id, parent_id).

  4. Adjust the working table estimate when level sizes are consistently far from the default guess:

    SET LOCAL recursive_worktable_factor = 1000;   -- PostgreSQL 15+, for wide hierarchies

    A larger factor makes set-based joins look better; a smaller one favours nested loops.

  5. Prefer UNION ALL when the data cannot contain cycles; it avoids the duplicate-tracking hash table. When cycles are possible, PostgreSQL 14’s CYCLE clause detects them explicitly by path:

    WITH RECURSIVE reports AS (…)
CYCLE id SET is_cycle USING path
SELECT * FROM reports WHERE NOT is_cycle;

  6. Bound the recursion with a depth column and a WHERE depth < n in the recursive term to protect against runaway loops.

Index on the parent pointer changes everything Without an index on manager_id, a 40-person team takes 7.5 seconds because each of its three levels scans all employees, and a 30 thousand person division takes 25 seconds. With the index, the same queries take 0.3 milliseconds and 48 milliseconds. no index, 40 reports 7.5 s no index, 30,412 reports 25.1 s index, 40 reports 0.3 ms index, 30,412 reports 48 ms without the index, cost scales with depth × table size

Before and After #

-- BEFORE: no index on manager_id
Recursive Union → Hash Join → Seq Scan on employees (rows=4000012 loops=10)     Execution Time: 25106.8 ms

-- AFTER: index on employees(manager_id)
Recursive Union → Nested Loop → Index Scan using employees_manager_id_idx (loops=30412)   Execution Time: 48.2 ms

Why the hash join was chosen for a 10-row estimate #

With no index on manager_id, a nested loop would have needed a sequential scan of employees per working-table row — ten full scans per iteration at the estimated size. Hashing the working table and scanning employees once per iteration was genuinely the cheapest plan available. The index created the missing option, and once it existed the 10-row estimate strongly favoured it. This is the usual pattern: recursive term plans are poor mostly because of missing indexes on the recursion key, and only secondarily because of the working table estimate.

When both options exist and the estimate is badly wrong in the large direction — a graph walk whose levels hold hundreds of thousands of rows — the nested loop chosen for a 10-row estimate can become the problem instead. That is when recursive_worktable_factor earns its keep, and the planning trade-off is the same as any parameterized nested loop.

The CTE Scan on top also matters when the result is used more than once. A recursive CTE is always materialized, so referencing it several times reads the stored result rather than recomputing the recursion, but its row estimate for the outer query is equally rough and can distort joins above it.

Common Pitfalls #

No index on the parent column. Every level scans the table. Diagnostic signal: Seq Scan with loops equal to depth. Fix: index the recursion join column.

UNION on large acyclic hierarchies. Duplicate tracking holds every row in a hash table. Diagnostic signal: memory growth in Recursive Union. Fix: UNION ALL, with CYCLE only where cycles are possible.

Unbounded recursion on dirty data. A cycle with UNION ALL loops forever. Diagnostic signal: statement timeout on specific start nodes. Fix: depth limits or the CYCLE clause.

Filtering after the CTE. WHERE depth <= 3 outside the CTE still computes every level. Diagnostic signal: large loops despite a shallow filter. Fix: put the depth limit inside the recursive term.

Frequently Asked Questions #

What is a WorkTable Scan in EXPLAIN? #

It reads the working table of a recursive CTE — the rows produced by the previous iteration — as input to the recursive term. Its loops count equals the number of iterations executed.

How does PostgreSQL estimate the size of a recursive CTE? #

It plans the recursive term once, assuming the working table holds the non-recursive term’s estimated rows multiplied by recursive_worktable_factor, which defaults to 10 from PostgreSQL 15. Actual level sizes can be far larger or smaller.

Should I use UNION or UNION ALL in a recursive CTE? #

Use UNION ALL when the data cannot contain cycles, because UNION keeps a hash table of all rows produced to remove duplicates. Where cycles are possible, prefer the CYCLE clause or an explicit depth limit.

Up: CTE and Subquery Planning