Recap — Building Recursive Queries

# Building Recursive Queries Some problems are inherently recursive: org charts (everyone under a manager), category trees (all sub-categories of "electronics"), social graphs (friends-of-friends). Recursive CTEs are the SQL tool for them. ## The anatomy Every recursive CTE has three pieces: ```sql WITH RECURSIVE descendants AS ( -- 1. Base case (anchor) SELECT id, manager_id, name, 1 AS depth FROM employees WHERE id = 100 -- start with employee 100 UNION ALL -- 2. Recursive case SELECT e.id, e.manager_id, e.name, d.depth + 1 FROM employees e JOIN descendants d ON e.manager_id = d.id -- 3. Termination is implicit when recursive case produces no new rows ) SELECT * FROM descendants ORDER BY depth; ``` How it runs: 1. Run the base case — gets employee 100. 2. Run the recursive case using the just-added rows — gets direct reports. 3. Run again on the new rows — gets reports' reports. 4. Continue until the recursive case adds no new rows. ## Cumulative path You can carry information through the recursion. Build a path string: ```sql WITH RECURSIVE descendants AS ( SELECT id, manager_id, name, name AS path, 1 AS depth FROM employees WHERE manager_id IS NULL -- start at top of org UNION ALL SELECT e.id, e.manager_id, e.name, d.path || ' > ' || e.name, d.depth + 1 FROM employees e JOIN descendants d ON e.manager_id = d.id ) SELECT id, name, depth, path FROM descendants ORDER BY path; ``` The `path` column accumulates as recursion descends, giving you `CEO > VP > Director > Manager > IC`. ## Category trees — all descendants of a node ```sql WITH RECURSIVE subtree AS ( SELECT id, parent_id, name FROM categories WHERE id = :root_category_id UNION ALL SELECT c.id, c.parent_id, c.name FROM categories c JOIN subtree s ON c.parent_id = s.id ) SELECT * FROM subtree; ``` Same pattern. The base case picks the root; the recursive case finds children. ## All ancestors of a node — reverse direction Flip the join direction: ```sql WITH RECURSIVE ancestors AS ( SELECT id, parent_id, name FROM categories WHERE id = :leaf_id UNION ALL SELECT c.id, c.parent_id, c.name FROM categories c JOIN ancestors a ON a.parent_id = c.id -- note: a.parent_id = c.id, not the other way ) SELECT * FROM ancestors; ``` The trick is in the JOIN direction. Walking down: `child.parent_id = parent.id`. Walking up: `parent.id = child.parent_id` — i.e., `ancestors.parent_id = categories.id`. ## Preventing infinite loops Cycles in your data (A reports to B, B reports to A) cause infinite recursion. Most databases cap recursion depth (PostgreSQL: 100 by default, configurable). Defense: ```sql WITH RECURSIVE descendants AS ( SELECT id, manager_id, name, 1 AS depth, ARRAY[id] AS path_ids FROM employees WHERE id = 100 UNION ALL SELECT e.id, e.manager_id, e.name, d.depth + 1, d.path_ids || e.id FROM employees e JOIN descendants d ON e.manager_id = d.id WHERE NOT e.id = ANY(d.path_ids) -- skip if we've already visited ) SELECT * FROM descendants; ``` The `path_ids` array tracks visited nodes; `NOT id = ANY(...)` skips cycles. Always do this in production data. ## When NOT to use recursive CTEs - **Fixed depth** — if hierarchy is at most 3 levels, just LEFT JOIN 3 times. Faster and clearer. - **Tree-as-path columns** — if your data has `category_path = 'electronics/laptops/gaming'`, splitting strings is often faster than recursion. - **Specialised storage** — materialised paths, nested sets, and closure tables outperform recursion for read-heavy workloads. If you maintain a category tree in production, use one of these. ## Common interview pitfalls 1. **Forgetting `RECURSIVE`** — some databases require the keyword (PostgreSQL does; SQL Server doesn't). 2. **JOIN direction in ancestors vs descendants** — easy to get backwards. Walk through it carefully. 3. **Infinite loop on cyclic data** — most interview data is clean, but the right answer mentions cycle protection. ## Takeaway Recursive CTEs aren't elegant or fast, but they're the only portable SQL tool for hierarchy traversal. Memorize the 3-part anatomy. Interviewers love this question because it filters out analysts who only know GROUP BY.