Recursive SQL CTEs: Hierarchies, Reachability, and Cycle Paths

Recursive CTEs: distinguish descendants, reachability, and paths

A recursive CTE repeatedly applies a recursive term to rows produced by the previous step. The anchor selects the starting rows. Correctness depends on what each row represents and how the process terminates. These PostgreSQL 16 examples separately answer three questions: which employees descend from a manager, which graph nodes are reachable, and which paths close a cycle.

Specify the question and starting population

A hierarchy normally gives each node at most one parent. A graph can give a node several incoming edges and many paths from the same start. Returning one row per reachable node is different from returning every path. Depth and path columns also affect duplicate elimination, so simply replacing UNION ALL with UNION is not a universal cycle fix.

Follow actual parent relationships in a hierarchy

WITH RECURSIVE employees(id,name,manager_id) AS (
 VALUES(1,'Ada',NULL),(2,'Ben',1),(3,'Cara',1),(4,'Dee',2),
 (5,'Eli',99),(6,'Fay',7),(7,'Gus',6)
), hierarchy(id,name,manager_id,depth,path) AS (
 SELECT id,name,manager_id,0,ARRAY[id] FROM employees WHERE id=1
 UNION ALL
 SELECT e.id,e.name,e.manager_id,h.depth+1,h.path||e.id
 FROM employees e JOIN hierarchy h ON e.manager_id=h.id
 WHERE NOT e.id=ANY(h.path)
)
SELECT id,name,manager_id,depth,path FROM hierarchy ORDER BY path;

id | name | manager_id | depth | path
1 | Ada | NULL | 0 | {1}
2 | Ben | 1 | 1 | {1,2}
4 | Dee | 2 | 2 | {1,2,4}
3 | Cara | 1 | 1 | {1,3}

The anchor includes Ada, so depth zero is the starting manager. The recursive term retains e.manager_id, the employee’s actual direct manager; copying the anchor’s NULL manager would corrupt the relationship. The path guard prevents revisiting a node already on this route. ORDER BY path gives a defined display order; SQL does not promise the final result order without it.

Eli’s parent 99 is missing, and Fay/Gus form a disconnected cycle. None is reachable from Ada, so none appears. This query is not a complete integrity audit of every employee. Starting only at rows with manager_id IS NULL would also miss a rootless cycle. Validate parent references and disconnected components separately if those are requirements.

Use a node-only recursive result for unique reachability

WITH RECURSIVE edges(parent,child) AS (
 VALUES(1,2),(1,3),(2,4),(3,4),(4,2)
), reached(node) AS (
 VALUES(1)
 UNION
 SELECT e.child FROM edges e JOIN reached r ON e.parent=r.node
)
SELECT node FROM reached ORDER BY node;

node
1
2
3
4

Node 4 is reached by two routes, and 4 points back to 2. UNION removes duplicate node rows, including nodes already emitted, so this finite graph reaches a fixed point. The starting node is included. If you added an ever-increasing depth column, (2,1), (2,3), and later rows would differ; UNION would no longer deduplicate by node alone. Keep the result key aligned with the question.

Keep paths when the question needs routes or cycle evidence

WITH RECURSIVE edges(parent,child) AS (
 VALUES(1,2),(1,3),(2,4),(3,4),(4,2)
), walk(node,path,is_cycle) AS (
 SELECT 1,ARRAY[1],false
 UNION ALL
 SELECT e.child,w.path||e.child,e.child=ANY(w.path)
 FROM walk w JOIN edges e ON e.parent=w.node
 WHERE NOT w.is_cycle
)
SELECT node,path,is_cycle FROM walk ORDER BY path;

node | path | is_cycle
1 | {1} | false
2 | {1,2} | false
4 | {1,2,4} | false
2 | {1,2,4,2} | true
3 | {1,3} | false
4 | {1,3,4} | false
2 | {1,3,4,2} | false
4 | {1,3,4,2,4} | true

A closing cycle row is emitted as evidence, then stops expanding because the next iteration requires NOT is_cycle. Node 4 on two routes is intentional. This enumerates non-repeating paths plus their closing-cycle rows, not shortest paths, and its row count can grow rapidly even in an acyclic graph. PostgreSQL also provides a CYCLE clause; choose one consistent representation and test its output.

Bound the work without pretending a partial answer is complete

A depth guard can protect a workload, but a cutoff changes the answer. If you stop at depth two, identify the frontier and report that deeper descendants may exist. An outer LIMIT is not a reliable termination strategy: sorting or other operations can require consuming the recursive result first. PostgreSQL does not use SQL Server’s OPTION(MAXRECURSION ...) syntax.

A parent-key index can help lookups on a real edge table, but the number of generated paths may dominate cost. Keep only necessary state, anchor at the requested entity, and measure with representative branching and depth. Use an appropriate statement timeout in an isolated test environment. Do not use broad planner or server changes to conceal runaway recursion.

Debug the anchor, one step, and termination separately

First run the anchor alone and verify the selected root. Then manually join one step and check the parent/child direction. Inspect a depth or path column to explain traversal; PRINT is not a PostgreSQL SELECT expression. Test a leaf, a missing root, a self-loop, two paths to one node, and a disconnected cycle. Confirm the column types of the anchor and recursive term agree; casts may be needed for growing strings or date arithmetic in some dialects.

Filtering a child out during recursion can also hide all of its descendants. If the business rule only hides a label from the final display but still needs traversal through that node, the filter belongs at a different stage. Security rules may intentionally require pruning; that policy should be stated rather than accidentally inherited from a WHERE clause.

Choose one of the three result contracts

Use the hierarchy query for the named manager’s descendants with direct parent and depth. Use the node-only UNION query for unique reachable nodes. Use the path query for route and cycle evidence when its potential size is acceptable. No one version is a drop-in replacement for the others. The PostgreSQL recursive query reference documents iteration, ordering, and cycle handling.

FAQ

Does a depth limit prove there are no more descendants? No; it proves you stopped searching. Does UNION always prevent infinite recursion? Only if duplicate elimination actually reaches a fixed point for the entire returned row. Why is the root in the result? This anchor includes it; exclude it at the final stage if the contract requires descendants only.