Cypher Traversal Patterns for Spatial Provenance

Part of: Lineage Query Patterns and Graph Traversal

Cypher makes lineage traversals short enough to read, which is its real advantage over a recursive CTE — the query says what it looks for rather than how to walk. It also makes it trivially easy to write a query that traverses the entire graph, because the syntax for unbounded depth is one character shorter than the syntax for bounded depth. This how-to gives the traversal shapes that hold up on a real provenance graph, and the specific patterns that make a spatial one different.

The spatial part matters more than it first appears. Geospatial lineage graphs have a property that generic ones do not: entities have extents, and the interesting questions are often scoped by area rather than by identity. Cypher has no spatial index worth relying on for this, so the pattern throughout is to resolve the spatial part elsewhere and hand the graph a set of identifiers.

Prerequisites

  • A property graph with entity nodes and derivation relationships, per Lineage Query Patterns and Graph Traversal.
  • Indexes on the identifier properties used to seed traversals.
  • A spatial store — PostGIS or an index service — for extent-based selection.
  • A test graph with a diamond and a cycle in it.

Bound Every Variable-Length Pattern

The * quantifier without bounds is the single most dangerous construct in a lineage query, and it is also the most natural thing to write.

Variable-length pattern forms and their cost An unbounded pattern expands every path; an upper bound caps the depth; shortest-path returns one route per pair and expands far less. PATTERN EXPANDS USE WHEN -[:DERIVED_FROM*]-> no bound at all every path, all lengths never, in production code -[:DERIVED_FROM*1..12]-> explicit upper bound paths up to 12 hops full ancestry where you need every node shortestPath((a)-[*..12]->(b)) one route per pair one path, pruned early "is B derived from A, and how?"

The third row is under-used and often the right answer. Most questions phrased as “show me the lineage between these two datasets” want one representative path, not the combinatorial set of every route, and shortestPath prunes aggressively where an unbounded pattern does not.

Pick the upper bound from the deepest chain you actually have, plus a margin. Query the maximum depth in your graph once, and set the bound at roughly twice it. That way the bound never truncates a legitimate answer, and a query that hits it is reporting a graph problem — usually a cycle — rather than a query problem.

Collect Distinct Nodes, Not Paths

The default result of a variable-length match is a row per path, and lineage questions almost always want a set of nodes.

On a graph with any diamonds — and every real lineage graph has them, because two products commonly share a source — the path count is combinatorially larger than the node count. Returning paths and deduplicating in the application transfers an enormous result set for no reason.

Use DISTINCT on the node, and where the traversal is purely about reachability rather than route, consider unwinding the path nodes and collecting distinct across the whole match. The query gets marginally longer and the result gets orders of magnitude smaller.

Where the route genuinely matters, return the path but bound the number of paths explicitly. A caller asking “how is B derived from A” is satisfied by three example routes and will not read three thousand.

Spatial Scoping Happens Outside the Graph

The characteristic geospatial question — “what feeds the products covering this area?” — needs a spatial predicate the graph store cannot efficiently answer.

Resolve the extent first, traverse second The spatial store answers which datasets intersect the area; the graph store traverses from that seed set, with neither doing the other's job. area of interest a polygon from the user or from a map viewport PostGIS GiST index on extents → 40 dataset ids Cypher UNWIND $ids AS id MATCH … traverse Each store does what it indexes well. Neither is asked to do the other's job. The anti-pattern: storing extents as node properties and filtering in Cypher. No spatial index, so it scans every node — correct, and unusable past a few thousand.

The seed list must be bounded. A viewport covering a whole country resolves to thousands of datasets, and a traversal seeded from thousands of nodes is a full graph walk with extra steps. Cap the seed count and tell the caller when the cap bites, rather than silently starting a traversal that will not finish.

Pass the seed as a parameter rather than interpolating it into the query text. Parameterised queries are planned once and reused; a query with four hundred literals embedded is planned from scratch every time and blows the plan cache.

Traversal Cost Is Governed by Fan-Out, Not Node Count

Graph query performance intuitions built on total node counts are misleading, and the correct mental model is simpler.

The work a traversal does is the product of the fan-out at each level, so a graph of ten million nodes with a fan-out of two is far cheaper to walk than one of ten thousand nodes with a fan-out of forty. Measure your fan-out distribution before worrying about graph size.

The distribution matters more than the mean. Lineage graphs are heavy-tailed — a national reference layer may feed six hundred products while the median dataset feeds one — and a traversal that touches one of those hubs does most of its work there. Knowing which nodes are hubs tells you which queries will be slow before anyone runs them.

Consider excluding known hubs from generic traversals and reporting them specially. “This chain passes through the national basemap, which feeds 600 products” is a more useful answer than six hundred rows, and it is enormously cheaper.

Profile with the query planner rather than by timing. A PROFILE showing database hits per operator points directly at the expanding step, where a wall-clock measurement tells you only that something was slow.

Model the Relationship Types You Will Filter On

Cypher’s advantage over SQL here is that relationship type is part of the pattern rather than a predicate, and that only pays off if the types were chosen well when the graph was built.

Relationship typing decides what can be pruned A single generic relationship type forces every filter into a property predicate evaluated after expansion; specific types prune during the match itself. ONE GENERIC TYPE -[r:RELATED_TO*1..8]-> WHERE all(x IN r WHERE x.kind = 'derived') expands everything, filters after SPECIFIC TYPES -[:DERIVED_FROM*1..8]-> CITES, VALIDATED_BY and SUPERSEDES never expanded prunes during the match Type is structural. Property is data. Only structure prunes an expansion. Choose types for the filters you will need, not for how the data was described.

Keep the type vocabulary small and stable. A dozen types is comfortable; a hundred means the modelling has drifted into encoding data as structure, and every query must then enumerate types it wants, which is worse than a property filter.

Use a union of types where a query spans several: matching two or three named types still prunes the rest, which is most of the benefit. The pattern is only marginally longer than the generic one.

Reserve properties for what genuinely varies per edge — timestamps, parameter digests, confidence — rather than for anything a query will filter a traversal by. The distinction is easy to state and easy to lose during a schema change, so state it in the model documentation.

Where an existing graph already uses one generic type, migrating is a bulk relationship rewrite rather than a redesign, and it is usually worth doing before optimising anything else.

Verification

Assert the diamond case: a node reachable by two routes must appear once in a distinct-node result and twice in a path result. Both behaviours are correct; the test pins which one your query has.

Assert the bound by running against a fixture chain deeper than the limit and confirming the result is flagged as truncated rather than silently short. Cypher will not tell you; the application must compare the returned depth against the bound.

Assert the seed cap fires by passing a seed list one element over the limit. A cap that has never been exercised is a cap nobody has confirmed exists.

Assert parameterisation by checking the query plan cache does not grow across a hundred invocations with different seeds. Plan-cache pressure from literal interpolation is invisible in any functional test.

Gotchas & edge cases

  • Labels are not free filters. A label on a node narrows the seed lookup and does nothing during expansion, so a traversal restricted by label still walks every relationship and discards afterwards.
  • Relationship direction is easy to invert. -[:DERIVED_FROM]-> and <-[:DERIVED_FROM]- both parse and both return results, and the wrong one silently answers the opposite question. Name the query for the direction and test both.
  • shortestPath with a lower bound of zero matches the start node. *0.. includes a zero-length path, so the start node appears in its own ancestry. Almost never what is wanted.
  • The query text is part of the plan cache key. Two queries differing only in whitespace are planned twice. Build them from constants rather than assembling strings per call, or the cache fills with near-identical entries.
  • Node property indexes do not help variable-length patterns. They speed the seed lookup only; the expansion is driven by relationship storage.
  • Deleted entities leave dangling relationships in some models. A traversal reaching a node with no properties is usually a soft-delete artefact, not a graph error. Filter explicitly rather than crashing on a missing property.
  • OPTIONAL MATCH inside a traversal changes cardinality. It preserves rows with nulls, which turns a clean node set into a set with holes. Prefer a second query.