Benchmarking Lineage Traversal Query Cost

Part of: Lineage Query Patterns and Graph Traversal

Lineage traversal performance degrades in a way that ordinary load testing does not catch. The query is fine on a test graph of a thousand nodes, fine in production for eighteen months, and then a single new derivation creates a hub and the same query starts timing out. This how-to builds a benchmark that measures the thing that actually governs cost — graph shape — rather than the thing that is easy to measure, which is row count.

The governing insight: traversal cost is driven by fan-out and connectivity, not by size. A benchmark that scales the node count while holding the shape constant will report linear growth and predict nothing, because production graphs do not grow that way.

Prerequisites

  • A traversal implementation to measure, per Lineage Query Patterns and Graph Traversal.
  • A way to generate synthetic graphs with controlled shape parameters.
  • A copy of production graph statistics — degree distribution and depth — even if not the data.
  • Somewhere to store results so runs are comparable over time.

Measure the Shape Parameters First

Before benchmarking anything, characterise the real graph, because the benchmark’s job is to reproduce its shape at larger scale.

The four parameters that predict traversal cost Out-degree distribution, chain depth, diamond density and hub concentration each govern a different component of the cost. PARAMETER MEASURED AS PREDICTS out-degree p50 / p99 children per node — report both, never the mean descendant fan-out maximum chain depth longest path to a source across all terminal nodes recursion levels diamond density nodes reachable by more than one path, as a fraction dedup work, path blow-up hub concentration share of edges touching the top 1% of nodes worst-case latency

The out-degree row carries an instruction worth following literally. Lineage out-degree is heavy-tailed, so the mean is dominated by a handful of hubs and describes no actual node. A p50 of one and a p99 of two hundred is a completely different benchmark target from a mean of four, and only the percentiles tell you that.

Diamond density is the parameter most often overlooked and the one that separates a well-behaved traversal from a pathological one. It is also cheap to measure: count the nodes whose ancestor set is smaller than the sum of their parents’ ancestor sets.

Benchmark the Worst Case, Not the Average

An average-case benchmark on a heavy-tailed graph measures the wrong thing, because the queries that cause incidents are the ones that touch hubs.

Build the seed set deliberately from three strata: a random sample, the highest-degree nodes, and the deepest nodes. Report the three separately. A single aggregate number across all three hides exactly the tail you are trying to characterise.

Report percentiles, not means, for the same reason. The mean traversal latency across a thousand random seeds is a number that describes no query anybody will run, while the p99 is the one that determines whether an incident response works.

Run the hub stratum at every scale, because that is where superlinear behaviour first appears. A benchmark that scales cleanly on random seeds and quadratically on hub seeds is telling you precisely which production change will break it.

Scale the Shape, Not Just the Size

Growing a synthetic graph by adding nodes with the same average connectivity produces a graph that gets bigger and no harder to traverse, which is a benchmark that always passes.

Two ways to scale a synthetic lineage graph Uniform growth keeps traversal cost linear and predicts nothing; preferential attachment reproduces the hub accumulation that real graphs show. UNIFORM GROWTH every new node gets 2 parents chosen at random traversal cost: linear predicts nothing real PREFERENTIAL ATTACHMENT new nodes prefer well-connected parents — reference layers win traversal cost: superlinear at the tail matches what real graphs do Everyone builds a reference layer on top of the popular reference layer. That is why lineage graphs are heavy-tailed, and why uniform synthetic graphs mislead.

Validate the generator against the real statistics before trusting any result from it. Generate at production scale, measure the four parameters, and compare against the production figures. A generator that produces the right node count and the wrong degree distribution is producing a graph that answers a different question.

Where the production graph cannot be measured directly for access reasons, its shape statistics almost always can be. Degree distributions and depths are aggregate figures with no sensitive content, and getting them exported is usually far easier than getting the graph.

Guard Against Regressions in the Plan, Not the Time

Wall-clock benchmarks are noisy enough that a two-fold regression can hide inside normal variance, and the interesting regressions are structural.

Assert on the query plan. A traversal that was using an index scan on the recursive join and is now using a sequential scan has regressed catastrophically even if the benchmark graph is small enough that the times look similar. That assertion is deterministic where timing is not.

Assert on work counters — rows examined, database hits, buffers read — rather than on seconds. They are stable across machines, they are not affected by a noisy neighbour, and they change for the reasons you want to detect.

Keep timing measurements too, but treat them as informational. They catch the regressions that counters miss, chiefly those caused by data volume per row rather than row count, and they are what anyone reading the report will look at first.

Recording Results So They Stay Comparable

A benchmark whose results cannot be compared across months answers the question once and then becomes a ritual.

Record the shape parameters alongside every result. A run that got slower because the benchmark graph got denser is not a regression, and without the parameters recorded there is no way to tell that from a real one.

Record the software versions of everything in the path — database, driver, the traversal code — because a change in any of them explains a step change in the numbers and none of them are visible in the result otherwise.

Store results in a form that survives the tooling. A benchmark harness will be rewritten; the numbers should outlive it, which means a plain table rather than an artefact of whatever framework produced it.

Report in a Form That Prompts a Decision

A benchmark that outputs a table of milliseconds gets read once. One that states the threshold it is measuring against gets acted on.

Benchmark results stated against budgets Each stratum reported against an explicit latency budget, with a projection of when current growth will breach it. STRATUM p99 BUDGET HEADROOM random seeds 42 ms 200 ms 4.8× — comfortable deepest chains 130 ms 200 ms 1.5× — watch it hub seeds 3 400 ms 2 000 ms breached — act now At the current edge growth rate, the deep stratum breaches in roughly five months. That sentence is what turns a benchmark into a plan.

Set a separate budget per stratum rather than one number for everything. Hub traversals are legitimately slower and holding them to an interactive budget produces a permanently red benchmark that everyone learns to ignore.

Derive the budgets from where the query is used. A traversal behind a page load has a budget of a couple of hundred milliseconds; the same traversal in a nightly report has a budget of minutes, and stating which one you are measuring is half the value of the report.

Project forward from the observed growth. Extrapolating current edge growth against the measured cost curve gives a date, and a date is what gets work scheduled where a percentage does not.

Publish the report where the people who can act on it already look. A benchmark result in a build artefact nobody opens is a measurement, not a signal.

Verification

Assert the generator reproduces target parameters by generating a graph with specified degree and depth targets and measuring what came out. A generator that silently misses its targets invalidates everything downstream.

Assert the benchmark detects a known regression by deliberately dropping an index and confirming the suite fails. A benchmark that has never failed has not been shown to measure anything.

Assert stratum separation by confirming the hub stratum reports materially worse latency than the random stratum. If they are the same, the strata are not being built as intended.

Assert result comparability by running the identical benchmark twice and confirming the work counters match exactly. Any variation there is nondeterminism that will masquerade as a regression later.

Gotchas & edge cases

  • Concurrency changes the shape of the answer. A traversal measured alone and the same traversal measured while ten others run give different numbers, and only the second reflects an incident, when everyone queries at once.
  • Cache warmth dominates small benchmarks. The first run reads from disk and the rest from memory. Decide which you are measuring and either warm deliberately or clear deliberately — not whichever happens.
  • Synthetic identifiers change index behaviour. Sequential integers cluster in a B-tree in a way random identifiers do not, which can flatter the benchmark substantially. Match the production identifier scheme.
  • Connection setup can exceed query time. For sub-millisecond traversals, pooling behaviour is most of the measurement. Measure inside the connection.
  • A benchmark is not a load test. Measuring one traversal at a time characterises the query; measuring many at once characterises the system. Both are worth having and they answer different questions, so do not let one stand in for the other.
  • Percentiles need enough samples. A p99 from a hundred runs is one data point. Run enough that the tail is populated, or report a maximum and say so.
  • The benchmark graph is not a security-free zone. Synthetic graphs derived from production structure can leak the structure. Treat shape statistics as the shareable artefact, not the generated graph.