Lineage Query Patterns and Graph Traversal

Part of: Storage, Indexing & Query Optimization

A lineage store earns its cost the moment somebody asks it a question, and almost nothing else it does matters. Capture can be immaculate, the schema can be well normalised, the hash chain can verify — and if the queries people actually need are slow, awkward to write, or return answers nobody trusts, the whole apparatus degrades into an expensive write-only log. Lineage query patterns are the small set of question shapes that a provenance store must answer well, and the traversal techniques that make each of them tractable.

There are fewer of these shapes than the variety of questions suggests. Almost every real request — an auditor’s, an engineer’s, a steward’s — reduces to ancestry, impact, reachability, or a time-bounded slice of one of those. Recognising which shape a question is, and knowing the traversal cost profile of each, is what turns an open-ended request into a query with a predictable answer.

In this guide

• The four question shapes
• Recursive traversal in SQL, and where it degrades
• Bounding a traversal so it always returns
• Spatial and temporal predicates inside a walk
• Configuration reference
• Common failure modes and mitigations
• Compliance and governance alignment
• Frequently Asked Questions

The Four Question Shapes

Categorising a request before writing SQL for it saves considerable effort, because the four shapes have genuinely different cost profiles and two of them have a natural bound while two do not.

Ancestry is the shape auditors ask for and the one that behaves best. Each hop upstream reaches the inputs of the current node, and because a derivation graph terminates at external sources, the walk finishes on its own. A dataset with a long history has a deep ancestry chain, not a wide one, so the result set stays small enough to return whole.

Impact is the mirror image and the source of most runaway queries. A widely used reference layer can appear upstream of a large fraction of an agency’s products, so an uncapped downstream walk returns a list that is technically correct and operationally useless. Cap it, paginate it, and treat a query that reaches the cap as a finding rather than as a truncated result.

Reachability is worth recognising separately because it admits an optimisation the others do not: the walk can stop the moment a path is found. Answering “did this superseded source contribute to the published product” does not require enumerating every path, and a bidirectional search from both ends meets in the middle at a fraction of the cost of a full traversal.

Recursive Traversal in SQL, and Where It Degrades

WITH RECURSIVE handles lineage traversal well up to a point, and understanding where that point is prevents both premature migration to a graph engine and surprise timeouts in production.

The divergence shown is the entire story of recursive CTE performance. PostgreSQL plans the recursive term once, using statistics that describe the first iteration, and reuses that plan for every subsequent level. A nested-loop join chosen sensibly for ten rows is still being used at level six where there are ten thousand, and the query’s cost grows far faster than the row count.

This has two practical consequences. First, EXPLAIN ANALYZE on a slow recursive query almost always shows a large gap between rows= and actual rows= on the recursive term, and that gap — not a missing index — is the diagnosis. Second, the remedy is to reduce what the recursion has to handle rather than to make each iteration faster: bound the depth, filter early, and materialise intermediate results where the same subgraph is walked repeatedly.

Ancestry rarely reaches this territory because it converges. Impact does, routinely, which is why the bounding techniques below matter more for downstream queries than for upstream ones.

Bounding a Traversal So It Always Returns

An unbounded traversal over a graph you do not fully control is a query that will eventually not return. Three bounds together make that impossible, and all three are cheap.

A depth column. Carry the recursion level as a column and terminate on it explicitly. This is the bound that matters most, because it is the only one that holds regardless of graph shape. Choose the limit from the measured depth distribution rather than a round number — if the deepest real chain is nine hops, a cap of fifteen is generous and still finite.

A visited set. Track node identifiers already reached and exclude them from further expansion. Without it, a diamond-shaped derivation — two paths from the same ancestor reconverging — revisits the shared subgraph once per path, and the work multiplies with each such diamond. With it, each node is expanded once regardless of how many paths reach it.

A result cap. Stop after some number of rows and report that the cap was hit. This is the bound that turns a hostile query into an informative one: returning ten thousand affected products with a note that more exist is more useful than a timeout, and the note is the signal that the question needs narrowing.

The visited set also protects against the pathological case that constraints cannot prevent. A cycle in the derivation graph — two pipelines each consuming the other’s output — makes an unbounded walk run forever, and while a nightly acyclicity check should catch it, the traversal should not depend on that check having run. Cycles are rare and their absence should not be assumed by code that hangs when the assumption fails.

Spatial and Temporal Predicates Inside a Walk

Lineage questions in a spatial context are rarely purely structural. “Everything downstream of this dataset that covers the flood zone” and “every step applied to this layer during the audit period” both combine a traversal with a filter, and where the filter is applied changes the cost by orders of magnitude.

The caution in the caption is the one that catches people. Pruning a traversal on a temporal predicate is sound when time increases along the derivation direction, because a node outside the window cannot have descendants inside it. Pruning on a spatial predicate is not sound in general: a national dataset outside a county extent can perfectly well be clipped to produce a product inside it, and a walk that stops at the national layer never reaches the clip.

The safe pattern is therefore to traverse structurally with a temporal bound, then apply the spatial predicate to the result set. That costs a larger intermediate result and gives the right answer. Where the intermediate is genuinely too large, the alternative is to precompute a closure table — materialised ancestor-descendant pairs — and filter that, which trades storage and staleness for query speed in exactly the way a materialised view does.

Both predicates should use the indexes described in Spatial Index Tuning for Provenance Queries. The spatial filter wants a GiST index with a bounding-box pre-filter; the temporal bound wants BRIN on the append-ordered timestamp. Neither helps inside the recursive term, where the planner’s estimate is the binding problem, but both help substantially on the filtering pass.

Returning Results People Can Read

A traversal returns edges. Almost nobody wants edges, and the gap between what the query produces and what the requester needed is where lineage systems acquire their reputation for being technically impressive and practically unusable.

Three presentations cover the demand. A path list — one row per distinct route from source to target, with the steps in order — is what an auditor asking “how did this come about” actually wants, and it is a straightforward post-processing of the traversal output. A flattened node list with a depth column suits impact analysis, where the question is which products are affected rather than by what route. And a grouped summary — counts by depth, by owning team, by dataset type — is what turns a ten-thousand-row impact result into something a manager can act on.

Produce all three from the same traversal rather than writing separate queries. The traversal is the expensive part; reshaping its output is cheap, and offering the three shapes behind one interface means callers stop writing their own variants with subtly different bounds.

Include provenance about the query itself in the response. The depth cap used, whether truncation occurred, the transaction-time bound applied, and the timestamp at which the traversal ran are all things a recipient needs in order to interpret the answer, and all of them are lost the moment results are copied into a document. Emitting them alongside the rows costs nothing and prevents an answer from being cited later without the caveats it was issued with.

Configuration Reference

report_truncation is the setting that keeps a capped query honest. A result silently cut at ten thousand rows looks like a complete answer, and an impact analysis that under-reports is worse than one that fails — it produces confident remediation over an incomplete list. Return the cap status alongside the rows and make callers handle it.

closure_table is worth enabling only after measuring. It makes reachability and impact queries fast at the cost of maintenance on every write and staleness between refreshes, which is the right trade for a compliance dashboard running the same queries all day and the wrong one for exploratory investigation where the next query is unpredictable.

Benchmarking a Traversal Honestly

Traversal performance is easy to measure badly, and a benchmark that flatters the design is worse than none because it postpones the discovery until production.

Benchmark against a graph with production’s shape, not its size. A synthetic graph with uniform fan-out behaves nothing like a real derivation graph, where a handful of reference layers have thousands of descendants and most nodes have two or three. Uniform test data makes impact queries look tractable because no node is a hub, and hubs are precisely what makes them expensive. Sample the real degree distribution and generate to it, or better, benchmark against a copy of the real graph.

Measure the tail, not the mean. Ancestry queries from a typical node take milliseconds and tell you nothing useful; the queries that matter are the ones starting from the most-connected nodes, and those are the ones a real incident will involve. Take the top decile of nodes by degree and benchmark from those.

Vary depth explicitly rather than letting it fall out of the data. A query capped at three hops and one capped at twelve are different queries with different cost profiles, and knowing where the curve bends tells you what cap to set. That inflection point is also the honest answer to whether a graph engine would help — if cost is flat to the depth you actually need, it would not.

Finally, run the benchmark against a warm cache and a cold one, and report both. Lineage queries are infrequent by nature, so the cold-cache number is closer to what an auditor will experience than the warm one a developer sees while iterating.

Common Failure Modes and Mitigations

The last row is worth internalising because it is the most common wasted effort in lineage tuning. A recursive query whose estimate is wrong by two orders of magnitude will not improve with another index, and each speculative index adds write cost to a table that is overwhelmingly write-heavy. Bound the recursion first, and only then look at access paths.

Compliance and Governance Alignment

The GDPR row is the one where an uncapped impact query is most tempting and most dangerous. A subject-access request genuinely needs every derived product, so truncation is not acceptable — but nor is a query that does not return. The resolution is to narrow structurally rather than to raise the cap: start from the specific dataset containing the subject’s data rather than from a shared reference layer, and the fan-out is usually manageable. Where it genuinely is not, a closure table is justified, because this is precisely the recurring query it exists for.

Frequently Asked Questions

Related

• PostGIS vs Neo4j for Spatial Lineage — when traversal cost justifies a graph engine
• Spatial Index Tuning for Provenance Queries — indexes for the filtering pass
• PostGIS Lineage Schema Design — the edge table these walks traverse
• Graph Databases for Lineage Graphs — the same shapes in a graph engine
• Lineage Visualization and Reporting — presenting what these queries return
• Part of: Storage, Indexing & Query Optimization