Recursive CTE Queries for PostGIS Lineage

Part of: Lineage Query Patterns and Graph Traversal

A lineage graph stored in PostgreSQL is walked with a recursive common table expression, and the difference between a query that returns in eight milliseconds and one that never returns is entirely in how that CTE is written. This how-to gives the working shapes — ancestors, descendants, depth-limited, cycle-safe — and the specific mistakes that turn each of them into a table scan or an infinite loop.

The reason this deserves its own treatment rather than a paragraph in a schema guide: recursive CTEs are the one place in SQL where the planner’s usual protections do not apply. A missing index on the recursive join produces a plan that is correct and quadratic, and quadratic on a lineage graph means a query that works in development and hangs in production.

Prerequisites

  • An edge table with parent and child entity references, per Lineage Query Patterns and Graph Traversal.
  • Indexes on both directions of the edge — one on the parent column, one on the child.
  • PostgreSQL 8.4 or later for WITH RECURSIVE; 14 or later for CYCLE.
  • A test graph large enough that a bad plan is visible, which is more than a hundred rows.

The Two Directions Are Different Queries

Ancestry and impact walk the same table in opposite directions, and they are not symmetric in cost or in what they need.

Ancestors and descendants join different columns Ancestor walks join the recursive term to the child column and need an index there; descendant walks join to the parent column and need the other index. ANCESTORS — "what built this?" source A intermediate start here JOIN e ON e.child_id = w.id needs index on (child_id) usually narrow — bounded fan-in DESCENDANTS — "what breaks?" start here product 1 product 2 …and their products JOIN e ON e.parent_id = w.id needs index on (parent_id) explodes — one source, many consumers

The asymmetry in the italic lines is what surprises people. A dataset typically has a handful of inputs, so an ancestor walk stays narrow at every level and terminates quickly. The same dataset may feed dozens of products, each feeding more, so a descendant walk fans out geometrically and needs a depth limit or a result cap that the ancestor walk does not.

Both indexes are required and having only one is the commonest cause of a slow lineage query. The index that serves ancestry does nothing for impact, and a system whose ancestry queries are fast tells you nothing about whether its impact queries are.

The Shape That Works

Every useful traversal is the same skeleton: a non-recursive term seeding the start node, a recursive term joining the edge table, and a UNION — not UNION ALL — to collapse repeats.

The choice between UNION and UNION ALL is the second-commonest mistake. A lineage graph is a DAG, not a tree, and a node reachable by two paths will be visited twice under UNION ALL, then its whole subtree twice, and the duplication compounds at every level. On a moderately connected graph this is the difference between a hundred rows and a million.

UNION deduplicates, which fixes the explosion but does not prevent an infinite loop on a genuine cycle, because the cycle is detected only by the exact row repeating. Carry a path array and check membership, or use the CYCLE clause on PostgreSQL 14 and later, which does the same thing with less code.

Select only the columns the traversal needs in the recursive term. Every column carried through the recursion is materialised at every level, and a traversal dragging a geometry column through fifteen levels is doing enormous work to produce a result set that then throws the geometry away. Join back for the payload after the recursion finishes.

Depth, Limits and the Escape Hatch

An unbounded traversal is a production incident waiting for the right graph shape, and the bounds cost nothing to add.

Three guards every lineage traversal needs Depth bounds the levels, the path array stops cycles, and a statement timeout catches whatever the first two missed. depth column depth + 1 in the recursive term, WHERE depth < 20 bounds the work path array path || id, and NOT id = ANY(path) or the CYCLE clause stops the loop statement timeout set per session on the lineage role — the last resort catches the rest Return the depth to the caller — a truncated result must be distinguishable from a complete one. A result silently cut at depth 20 reads as "no further ancestors". That is a wrong answer, not a slow one.

The bottom row is the point of the whole section. A depth limit that silently truncates converts a performance problem into a correctness problem, and the correctness problem is worse because nothing signals it. Return the maximum depth reached and let the caller compare it against the limit.

Set the depth limit generously — twenty levels is far beyond any real geospatial derivation chain — so that hitting it means something is wrong rather than meaning the graph is deep. A limit tuned so tightly that legitimate chains hit it trains everyone to ignore the truncation flag.

Filtering Inside the Recursion, Not After It

Where the predicate goes decides how much work the query does, and the intuitive placement is usually the expensive one.

A filter in the outer SELECT runs after the entire traversal has completed, so a query for “ancestors of type raster” walks the whole graph and then discards most of it. Pushing the same predicate into the recursive term prunes those branches before they are expanded, which on a wide graph is an order-of-magnitude difference.

The catch is that pruning changes the meaning. Filtering inside the recursion stops the walk at a non-matching node, so anything beyond it is unreachable even if it matches. That is correct for “stop at trust boundaries” and wrong for “find all rasters anywhere in the ancestry”, and the two read almost identically in SQL.

Decide which you mean and write a comment saying so. This is the single most common source of a lineage query that returns plausible but incomplete results, and it is invisible in review because both versions look right.

Where you need the unpruned semantics with better performance, filter on edge properties rather than node properties. Edge predicates prune the join itself and do not change reachability through unmatched nodes, because the edge either exists in the traversal or it does not.

Materialising What Gets Asked Constantly

Some traversals run often enough that recomputing them is waste, and the transitive closure is the usual candidate.

A closure table storing every reachable pair turns a traversal into a single indexed lookup, at the cost of storage that grows with the square of connectivity and maintenance on every edge insert. It is the right trade for a graph that is read constantly and written rarely, which describes most lineage stores.

Maintain it incrementally rather than rebuilding. An inserted edge adds the cross product of the new parent’s ancestors and the new child’s descendants, which is a bounded operation; a full rebuild is not, and a nightly rebuild leaves the closure wrong for a day.

Keep the recursive query as the reference implementation and test the closure against it. A closure that has drifted from the graph gives fast wrong answers, which is strictly worse than slow right ones, and drift is detectable only by comparison.

Returning the Result the Caller Actually Wants

A traversal that returns a flat list of identifiers pushes the interesting work back onto the application, and the CTE is already holding the information needed to avoid that.

Three result shapes from one traversal A flat list is cheapest and least useful; carrying depth and path costs almost nothing and answers far more; server-side tree assembly saves the client work at a real cost. flat id list cheapest to compute no structure at all caller re-queries to draw id + depth + path two extra columns already computed anyway the default choice assembled JSON tree one aggregate per level real server cost only for small results The path column is free: the cycle guard already maintains it. Return it, and the caller can render a tree without a second query.

The middle column is the default because both extra columns are already being maintained. The depth counter exists for the bound and the path array exists for the cycle guard, so returning them costs one word each in the select list and saves the caller from reconstructing the structure it needs.

Sort by path rather than by depth when the caller will render a tree. A path-ordered result comes out in depth-first order, which is exactly the sequence a renderer walks, and it removes the sort from the client entirely.

Assemble a tree server-side only when the result is small and the caller is a browser. Aggregating JSON per level is genuine work in the database, and it turns a streaming result into one that must be fully materialised before anything is sent.

Keep the payload join outside the recursion regardless of the shape chosen. The recursion should carry identifiers and its two bookkeeping columns; everything a human reads is joined on afterwards, once, against the deduplicated node set.

Verification

Assert the cycle guard by inserting a deliberate cycle into a test graph and confirming the query terminates with a cycle flag rather than running until the timeout. A guard that has never stopped a cycle has not been shown to work.

Assert UNION versus UNION ALL behaviour on a diamond — a node reachable by two paths — and confirm it appears exactly once. This is the fixture that catches the duplication bug, and a linear test graph will never reveal it.

Assert the truncation flag by setting the depth limit below the known depth of a fixture chain and confirming the caller can tell the result is incomplete. Then assert it is absent when the limit is generous.

Run EXPLAIN ANALYZE in the test suite and assert the recursive term uses an index scan. A regression here is a plan change rather than a result change, so no assertion on the output will catch it.

Gotchas & edge cases

  • The recursive term cannot reference the CTE twice. PostgreSQL permits exactly one self-reference, which rules out the obvious formulation of a bidirectional walk. Run two traversals and union the results.
  • LIMIT does not stop the recursion. An outer LIMIT 10 still computes the full traversal before discarding. Bound with depth, not with LIMIT.
  • Array-based cycle detection is O(n) per row. On deep graphs the membership check dominates. The CYCLE clause uses a more efficient representation where available.
  • Time-scoped traversals need the predicate in both terms. An as-of query that filters validity only in the non-recursive term silently walks through edges that did not exist at that time.
  • Statement timeouts leave no trace. A cancelled traversal returns an error the caller may swallow, producing an empty lineage panel that looks like a dataset with no ancestry. Log and surface the distinction.