Should a recursive CTE use UNION or UNION ALL?
UNION ALL keeps every produced row and is faster. UNION removes duplicates against all rows found so far, which can stop some cycles but costs extra work. For trees, use UNION ALL; for graphs with possible loops, add explicit cycle protection.
Explain it simply
Imagine finding all cities reachable by train from Pune. In a graph, you can reach the same city by many routes, and some routes loop back. UNION ALL keeps every discovery, so loops can repeat forever. UNION asks "have I already seen this exact row?" and drops repeats, so a loop that returns to an already-seen row stops.
UNION has a cost: it must hold and compare all rows so far. It also only removes rows that are identical in every column, so a changing counter column (like depth) defeats it.
Example
-- UNION removes already-seen rows, so this ends even with loops
WITH RECURSIVE reach(city) AS (
SELECT 'Pune'
UNION
SELECT r.to_city
FROM routes r JOIN reach ON r.from_city = reach.city
)
SELECT city FROM reach;PostgreSQL 14 also added dedicated syntax for it:
WITH RECURSIVE reach(city) AS (
...
) CYCLE city SET is_cycle USING path
SELECT * FROM reach WHERE NOT is_cycle;What to say in the interview
"For a plain tree, UNION ALL is correct and faster. For graphs that can loop, UNION dedupes whole rows so the recursion terminates, but it breaks if I carry depth, so I use the CYCLE clause from version 14 or a path array instead."
Common mistakes
- Using UNION with a depth column and expecting it to remove duplicate cities.