Walking graphs in SQL

The three shapes: tree, DAG, graph

Before you write the recursion, ask: does this data form a tree, a DAG, or a general graph? The answer decides whether your query is naturally safe, needs a dedup step, or will hang on real data without an explicit brake. The same recursive engine handles three structures of increasing danger, all over edges(src, dst) (or manager_id, parent_id):

• a tree — each node has one parent (org chart, categories). Traversal always terminates; no cycle risk.
• a DAG — directed, no cycles, but a node can have many parents (a bill of materials: a bolt used by ten assemblies). Terminates, but the same node is reached by many paths, so you may visit it repeatedly.
• a general graph — directed with cycles possible (dependency graphs, social follows). Cycles mean you must carry cycle protection or the walk never ends, exactly as in lesson 04.

The workhorse pattern for all three is path accumulation: carry an array of the nodes visited so far, both to detect cycles and to report the actual route. Here, “all parts inside assembly 1, with the path that reaches each” over a bill of materials:

WITH RECURSIVE bom AS (
  -- anchor: direct children of assembly 1
  SELECT dst AS part, ARRAY[1, dst] AS path, 1 AS depth
  FROM edges
  WHERE src = 1

  UNION ALL

  -- recursive term: descend, appending each node to the path
  SELECT e.dst, b.path || e.dst, b.depth + 1
  FROM edges e
  JOIN bom b ON e.src = b.part
  WHERE NOT e.dst = ANY(b.path)        -- cycle/repeat guard
    AND b.depth < 30                   -- depth seatbelt
)
SELECT part, path, depth FROM bom ORDER BY depth, part;

Reachability, shortest-ish paths, and what SQL can express

This pattern answers the common production questions cleanly. Reachability — “is B reachable from A?” — is EXISTS over the walk. Transitive closure — “all nodes reachable from A” — is SELECT DISTINCT over the walk. You can even approximate shortest path by carrying depth (hop count) and taking the minimum per destination, since the working-table loop expands breadth-first by level. What SQL recursion does not give you cheaply is true weighted shortest path (Dijkstra/A*): you can express it, but the engine has no priority queue, so it explores far more paths than a purpose-built algorithm and the cost is brutal on real graphs.

-- Fewest-hops distance from node 1 to every reachable node
WITH RECURSIVE walk AS (
  SELECT dst, 1 AS hops, ARRAY[1, dst] AS path FROM edges WHERE src = 1
  UNION ALL
  SELECT e.dst, w.hops + 1, w.path || e.dst
  FROM edges e JOIN walk w ON e.src = w.dst
  WHERE NOT e.dst = ANY(w.path)
)
SELECT dst, min(hops) AS shortest_hops
FROM walk GROUP BY dst ORDER BY dst;

The wall: path explosion and per-hop joins

Now the senior part — why this gets slow, and the numbers. Two costs compound. First, each iteration is a join of the whole working table against edges; without an index on edges(src), every hop is a sequential scan, and a 6-hop walk over a 10M-edge table is six full scans. Always index the join column (src, or manager_id/parent_id). Second, and worse, is path explosion: in a dense graph the number of distinct paths grows combinatorially with depth, so the working table can balloon to far more rows than there are nodes — you’re enumerating routes, not nodes. A graph with a few thousand nodes but high fan-out can produce millions of intermediate path rows, blow past work_mem (default 4 MB), spill to disk, and turn a conceptually small traversal into a multi-GB sort.

The mitigations, in order: index the join column; cap depth aggressively (most real questions need 3–6 hops, not unbounded); if you only need reachable nodes, deduplicate early with UNION (per-pass dedup) or restructure to track visited nodes instead of full paths so the working table stays bounded by node count, not path count. With those, recursive CTEs comfortably handle org charts, category trees, and BOMs up to roughly low-millions of edges with bounded depth. Together, these three mitigations shift the bottleneck from memory and disk back to network latency — which is where it belongs for a well-indexed hierarchy query. Skip even one of them on a dense graph and the wall reappears quickly.

Past that — millions of edges with deep or unbounded traversal, frequent shortest-path or centrality queries, or graph-shaped as the primary workload — you’ve outgrown the tool. A relational engine joins sets; it has no native adjacency index, no graph-aware operators. Reach for a graph database (Neo4j and its ilk) or Postgres’s pgRouting/Apache AGE extensions, which add real graph algorithms. The production rule: recursive CTEs are perfect for occasional hierarchy and reachability queries over moderate graphs that already live in your relational schema; they are the wrong default for a graph-centric product.