CTEs (WITH clause) — recursive CTEs: Visual walkthrough

We will use the tiniest possible example from the parent note — counting 1 to 5 — because a loop you can count on your fingers is a loop you truly understand. Then we handle the scary cases (org charts, cycles).

Step 1 — What is a "row" and a "table"? (starting from zero)

WHAT. Before any recursion, we need the two nouns SQL is made of. A table is a grid: named columns across the top, and rows stacked underneath. A row is one horizontal slice — one record. That's it. Nothing more mysterious than a spreadsheet.

WHY start here. Every symbol later ( $R$ , $W_{i}$ , $\emptyset$ ) is a bag of rows. If "row" is fuzzy, everything downstream is fuzzy.

PICTURE. On the left: an empty grid with one column called n. On the right: the same grid holding a single row whose n is 1. That single-row bag is the smallest non-empty table we can have.

Figure — CTEs (WITH clause) — recursive CTEs

Step 2 — The two halves of a recursive CTE, named on a picture

WHAT. A recursive CTE is written in two stacked pieces glued by the word UNION ALL. The top piece is the anchor; the bottom piece is the recursive member.

anchor: runs once SELECT 1 AS n UNION ALL recursive member: runs again and again SELECT n+1 FROM nums WHERE n<5

Term by term:

SELECT 1 AS n — "make one row whose column n holds the number 1." This is the seed.
UNION ALL — "stack the rows from below onto the rows from above, keeping duplicates." (Contrast with UNION, which would throw duplicates away — see UNION vs UNION ALL.)
SELECT n+1 FROM nums — "for each row currently in nums, produce a new row that is one bigger."
WHERE n<5 — the guard: only bother producing a next row while n is still below 5.

WHY two halves. The anchor answers "where do we start?" The recursive member answers "given where I am, where do I go next?" Those are exactly the two questions any journey needs — a starting point and a step rule. This mirrors Mathematical Induction: the anchor is the base case, the recursive member is the inductive step.

PICTURE. The query split into a magenta box (anchor) sitting on top of a violet box (recursive member), with the word UNION ALL as the seam between them, and arrows labelling what each box is for.

Step 3 — Meet the two bags: the Result $R$ and the Working table $W$

WHAT. The engine keeps two separate bags of rows while it runs:

$R$ — the Result. Rows only ever get added here. This is what you finally receive.
$W_{i}$ — the Working table for round $i$ . This is a scratchpad that gets overwritten each round. It holds only the rows that were brand-new last round.

WHY two bags, not one. This is the single most important idea on the page. If the recursive member re-read the whole growing result every round, old rows would get re-processed forever. By feeding it only $W_{i - 1}$ — the freshest rows — each row is stepped from exactly once. That is what makes the loop finite on non-cyclic data.

W_{i - 1} recursive member step rule W_{i}, R + = W_{i}

$W_{i - 1}$ — last round's new rows (the input to this round).
the arrow — apply the recursive member.
$W_{i}$ — this round's fresh output.
$R + = W_{i}$ — glue $W_{i}$ onto the permanent result.

PICTURE. Two labelled buckets. The violet arrow shows $W_{i - 1}$ pouring into the step rule; the fresh drops fall into $W_{i}$ ; a second orange arrow copies those same drops into the tall $R$ bucket.

Step 4 — Round 0: run the anchor (seed both bags)

WHAT. The engine runs the anchor once. It produces the single row {n:1}. That row is copied into both the result $R$ and the working table $W_{0}$ .

R = {1}, W_{0} = {1}

both bags now hold the same lone row — this is the only moment $R$ and $W$ agree.

WHY. The recursive member needs an input to chew on. Round 0 manufactures that first input out of thin air (the constant 1). Without it, round 1 would have nothing to read and the loop would produce $\emptyset$ immediately.

PICTURE. Timeline frame 0: the anchor box fires, one magenta row 1 drops into $W_{0}$ , and a copy lands in $R$ .

Step 5 — Rounds 1…4: the recursive member fires, one row at a time

WHAT. Now the loop turns. Each round reads $W_{i - 1}$ , applies SELECT n+1 ... WHERE n<5, calls the output $W_{i}$ , and appends it to $R$ .

Round	Reads $W_{i - 1}$	Guard `n<5`?	Produces $W_{i}$	$R$ after
1	`{1}`	$1 < 5$ ✓	`{2}`	`{1,2}`
2	`{2}`	$2 < 5$ ✓	`{3}`	`{1,2,3}`
3	`{3}`	$3 < 5$ ✓	`{4}`	`{1,2,3,4}`
4	`{4}`	$4 < 5$ ✓	`{5}`	`{1,2,3,4,5}`

Reads $W_{i - 1}$ — only last round's single row, never the whole $R$ .
Guard — the row currently in hand must satisfy n<5 for a next row to be born.
Produces $W_{i}$ — exactly one new row, one bigger.

WHY the guard n < 5 and not something else. The guard is the brake. It answers "should this row spawn a successor?" We chose n<5 because we want the last kept value to be 5. When the row in hand is 5, 5<5 is false, so it spawns nothing — and "nothing" is precisely how the loop learns to stop (Step 6).

PICTURE. A four-frame film strip: each frame shows the single violet input row on the left, the +1 step in the middle, and the fresh orange output row on the right, with the guard test annotated under each.

Step 6 — Round 5: the empty round that ends everything

WHAT. Round 5 reads $W_{4} = {5}$ . The guard asks 5 < 5? → false. So SELECT n+1 runs for no qualifying row and produces zero rows:

W_{5} = \emptyset .

The instant a round yields $\emptyset$ , the engine halts and hands you $R$ .

WHY this is the whole termination story. The loop does not stop because "we reached 5" — SQL has no idea 5 is special. It stops because the guard starved the recursive member of input, so it emitted nothing new. The general law from the parent:

R = W_{0} \cup W_{1} \cup \dots \cup W_{n}, W_{n + 1} = \emptyset

the union of every round's fresh rows is the answer;
$W_{n + 1} = \emptyset$ is the stop line — here $n = 4$ , so $W_{5} = \emptyset$ .

PICTURE. Frame 5: the input {5} hits the guard 5<5 = FALSE, the step rule produces an empty bag $\emptyset$ , and a big "STOP — return R" banner fires.

Step 7 — Degenerate case: an anchor that returns nothing

WHAT. What if the anchor itself produces $\emptyset$ ? For example SELECT n FROM emp WHERE 1=0 (a condition that's never true). Then $W_{0} = \emptyset$ immediately, the check "did this round produce new rows?" is already false, and the recursive member never runs even once.

W_{0} = \emptyset \Rightarrow R = \emptyset .

WHY show this. A reader who only saw the happy path would be baffled by an empty result and blame the recursive member. The truth: an empty seed means an empty harvest. The recursion is only as alive as the anchor that starts it — just like induction with no base case proves nothing.

PICTURE. The anchor box fires but drops zero rows into $W_{0}$ ; a dashed grey "recursive member: skipped" box sits unused; final $R$ is an empty grid.

Step 8 — The dangerous case: a cycle, and why `UNION ALL` loops forever

WHAT. Counting always halts because numbers only grow. But a graph (Tree and Graph Data Structures) can loop: A → B → A → B → …. Walk it with plain UNION ALL and no guard, and each round keeps discovering "new" arrivals at A, then B, then A… so $W_{i}$ never empties. Step 6 never triggers.

The fix carries a visited list and refuses to re-enter a node:

WHERE e.dst \neq = ALL r.path

r.path — the array of nodes we've already stepped through on this route.
<> ALL(r.path) — "the next node must differ from every node already visited."

This makes each route strictly grow its path, and since the graph has finitely many nodes, the path can't grow forever → eventually every extension is blocked → $W_{i} = \emptyset$ → halt.

WHY not just always use UNION? UNION de-duplicates each round (see UNION vs UNION ALL) and can act as a free cycle guard — but it also hides legitimately repeated rows and pays a sorting cost. The path guard is precise: it stops cycles without silently dropping honest duplicates.

PICTURE. A 2-node cycle A ⇄ B. Left panel: red endless arrows spiralling — "no guard = forever." Right panel: the path array growing [A] → [A,B], and the return arrow to A crossed out because A is already in the path — "guarded = halts."

The one-picture summary

Everything above compressed into a single loop diagram: anchor seeds $R$ and $W_{0}$ ; the recursive member repeatedly turns $W_{i - 1}$ into $W_{i}$ (appending each $W_{i}$ to $R$ ); the loop exits the moment $W_{i} = \emptyset$ ; and a side note shows the two ways to guarantee that emptiness — a numeric bound or a cycle guard.

Recall Feynman retelling of the whole walkthrough

Picture two buckets: a keeper bucket ( $R$ ) you never pour out of, and a scratch bucket ( $W$ ) you empty and refill every round. First, the anchor drops one starter row into both buckets. Then you repeat one simple move: look only at what's in the scratch bucket right now, apply the step rule (+1, or "who reports to these people?", or "where can I go next?"), and whatever comes out you drop into both buckets again — but the scratch bucket first gets emptied so it holds only the freshest rows. You keep turning the crank. The magic stopping moment is when a turn of the crank produces nothing — the scratch bucket comes up empty. That's the machine saying "no new frontier left," and it hands you the keeper bucket. Counting stops because numbers can't shrink past the guard; graphs stop because we carry a "places I've been" list and refuse to revisit; and if the anchor was empty to begin with, the crank never even turns. Same loop, every time.

Quick self-test

Predict :::

n < 3 instead of n < 5 — how many rows and which?

3 rows: 1, 2, 3 (row 3 fails 3<3 so spawns nothing;

W_{3} = \emptyset

If the anchor is SELECT 10 AS n with the same WHERE n<5, what is

R

Just {10} — the anchor row is kept, but 10<5 is false so the recursive member produces

W_{1} = \emptyset

immediately.

On a 3-node cycle A→B→C→A with the path guard starting at A, what's the longest path?

[A, B, C] — the step back to A is blocked by <> ALL(path), so it never revisits.

Connections

Parent: Recursive CTEs — this page is its visual derivation
Common Table Expressions (WITH clause) — the non-recursive foundation
UNION vs UNION ALL — set semantics decide whether Step 6 or Step 8 governs termination
SQL Joins — the recursive member joins $W_{i - 1}$ back to a base table
Tree and Graph Data Structures — trees always halt (Step 6); graphs need Step 8
Mathematical Induction — anchor = base case, recursive member = inductive step