In a WITH RECURSIVE query, what does each iteration read, and when does iteration stop?
answer
- Not a call stack
- There is a frontier and a result
- Each pass reads only what the last pass made
- The seed query is never re-run
- Empty pass ends it: iterate to fixpoint
basics
~20 sEach pass of the recursive member sees only the rows the previous pass produced, not the whole accumulated result. Its output is appended to the result and becomes the input for the next pass. Iteration stops when a pass produces no rows.
solid answer
~50 sThe evaluation model is iteration to a fixpoint, not call-stack recursion. The anchor member is evaluated once; its rows go into the final result and also into a *working set*. Then the recursive member is evaluated with the CTE's self-reference bound to that working set only — the rows from the immediately preceding pass, not everything produced so far. Whatever it returns is appended to the result and replaces the working set. That repeats until a pass returns no rows (with `UNION`, no rows that are not already in the result), at which point the CTE is complete and the outer query reads it. Two consequences matter in interviews: the anchor never re-runs, and you cannot see earlier generations from inside the recursive member, so running totals over the whole result must be computed outside the CTE.
code
sql · 8 linesWITH RECURSIVE t(n) AS (
SELECT 1
UNION ALL
SELECT n * 2 FROM t WHERE n < 20
)
SELECT n FROM t;
-- 1, 2, 4, 8, 16, 32 -- the predicate filters the input of a pass,
-- so the final row may exceed the boundgo deeper
Learn the loop in plain words: the seed query runs once, then the second query keeps running on the rows just produced, and it stops when a run produces nothing.
Be able to trace a short recursive CTE pass by pass on a whiteboard and name the working set. Explain why the last row can exceed the bound in the WHERE clause.
Use the model to explain query behaviour under pressure: why a running total inside the recursive member is impossible, why row order is not guaranteed, and why an outer filter cannot bound the loop.
Judge when this iteration model is the right tool at all — the frontier grows with the data, so set expectations about worst-case row counts before a recursive CTE ships in a hot path.
## The word "recursive" is misleading Nothing pushes a stack frame. The standard defines a recursive CTE by an **iterative fixpoint** procedure: apply a rule over and over until applying it once more adds nothing. Candidates who narrate it as function recursion usually get the next question wrong, because the mental model predicts the wrong thing about what the self-reference can see. ## The vocabulary Two collections exist during evaluation: - The **result** — everything produced so far, and what the outer query will eventually read. - The **working set** (PostgreSQL calls it the working table) — the rows produced by the most recent pass, and the *only* rows the self-reference resolves to on the next pass. ## The algorithm 1. Evaluate the anchor member once. Put its rows in the result and in the working set. 2. If the working set is empty, stop. 3. Evaluate the recursive member with the CTE's self-reference standing for the current working set. 4. Append the rows it produced to the result. With `UNION`, discard rows that already appear in the result before appending. 5. Replace the working set with the rows appended in step 4 and go back to step 2. The anchor is evaluated exactly once. The recursive member is evaluated once per pass, over a shrinking-or-growing frontier, until a pass contributes nothing. ## Worked trace ```sql WITH RECURSIVE t(n) AS ( SELECT 1 UNION ALL SELECT n * 2 FROM t WHERE n < 20 ) SELECT n FROM t; ``` - Anchor: working set `{1}`, result `{1}`. - Pass 1: reads `1`, `1 < 20` holds, emits `2`. Result `{1,2}`, working set `{2}`. - Pass 2: emits `4`. Pass 3: `8`. Pass 4: `16`. - Pass 5: reads `16`, `16 < 20` holds, emits `32`. Result now `{1,2,4,8,16,32}`, working set `{32}`. - Pass 6: reads `32`, `32 < 20` is false, emits nothing. Iteration stops. The final answer is `1, 2, 4, 8, 16, 32`. Note that the last row **exceeds** the bound: the predicate filters the *input* of a pass, not its output. That off-by-one is a favourite interview trap. ## Why "only the previous pass" matters Because the self-reference is bound to the working set rather than the accumulated result, you cannot look back over earlier generations from inside the recursive member. A query that tries to compute a running total with `SUM()` over the CTE, or to check "have I already emitted this value?" by scanning the CTE, is not expressible that way — and the standard's restrictions on the recursive member (no aggregates, no `GROUP BY`, one self-reference) exist precisely because operations like those would not have a well-defined fixpoint. The portable workaround is to compute per-row state you can carry forward as an extra column (a depth counter, an accumulated path string), and do the aggregation in the outer query once the CTE is complete. ## Termination The only thing that ends the loop is an empty pass. With `UNION ALL`, a pass is empty when the recursive member's `FROM`/`JOIN`/`WHERE` yields no rows for any row in the working set — normally because a counter crossed its bound or a join found no children. With `UNION`, a pass also ends the loop when every row it produced was already in the result, which is why `UNION` terminates on data where the same row is reachable by several routes. Nothing about the outer query participates in this. A `WHERE` or `ORDER BY` outside the CTE filters or sorts the finished result; it cannot make the iteration stop earlier. Whether an outer `LIMIT` can cut the iteration short depends on the engine and the chosen plan, so never treat it as the stop condition. ## Order of rows The standard gives a recursive CTE no guaranteed output order, but engines that evaluate it this way naturally emit rows generation by generation, which looks like breadth-first order. That is an artifact of the evaluation, not a promise: if order matters, sort explicitly in the outer query on a column you carried along, such as a depth counter. ## What to say in an interview Narrate the five steps, use the words *anchor*, *working set* and *fixpoint*, state that the anchor runs once, state that each pass sees only the previous pass's rows, and finish with "it stops when a pass produces no rows." That answer is complete.
- How many times is the anchor member evaluated?Exactly once, at the start. It seeds both the result and the first working set, and is never revisited. Candidates who picture function-call recursion often say it re-runs each pass as a base case; that would produce duplicate seed rows on every iteration, which is not what happens.
- Why can't the recursive member compute a running total over the rows produced so far?Its self-reference resolves only to the previous pass's rows, not the accumulated result, and the standard forbids aggregates in the recursive member because an aggregate could invalidate rows already emitted, leaving no well-defined fixpoint. Carry a per-row value forward as an extra column and aggregate in the outer query.
- Does the outer query's WHERE clause affect how many iterations run?No. The CTE is defined independently of the statement that reads it, so an outer filter removes rows from a finished result. The stop condition has to live in the recursive member's own WHERE clause. Whether an outer LIMIT can cut iteration short is engine- and plan-dependent, so never rely on it.
It is a ripple, not a stack: the anchor drops the stone, each pass sees only the ring the last pass made, and the water goes still when a ring adds nothing new.
saying these in an interview costs you the question
- Says the self-reference sees every row produced so far
- Describes it as function recursion with a call stack
- Claims the anchor member re-runs on each pass
- Thinks iteration stops when the outer query has enough rows
- Cannot say what makes one pass the last one