shortestPath benchmark — 500K nodes / ~3.97M edges

Single-process traversal latency at scale. Generated by:

go test ./pkg/cypher/ -run TestLargeScaleShortestPath_HopBuckets \
    -timeout 30m -largescale -v

Hardware: Apple M3 Max. Storage chain: BadgerDB → AsyncEngine → NamespacedEngine → StorageExecutor (the same chain the HTTP server uses).

Setup

• 500,000 Star nodes across 1,000 sectors (500 per sector)
• 3,969,418 HYPERLANE edges (forward+reverse), avg ~16 per node
• Direct BulkCreateNodes / BulkCreateEdges, property index built after bulk insert + count verify (mirrors a typical "load → index → query" workflow)
• Reference BFS over 200 random sources to bucket pairs by exact hop distance
• 30 random pairs benched per depth bucket

Seed timings

phase	time
build nodes in memory	215ms
BulkCreateNodes (500K)	234ms
build edges in memory	1.25s
BulkCreateEdges (3.97M)	1.54s
flush AsyncEngine → Badger	3m28s
count verify (500K nodes, 3.97M edges)	5µs
build property index (post-flush)	157ms
build reference adjacency in test process	1.39s
sample depth buckets (200 sources)	39ms
total seed wall-clock	3m32s

The 3m28s flush is the dominant seed cost — Badger's level-0 / level-1 compaction work for 4M edge writes. Once on disk, queries are read-only and benefit from the per-engine edge body cache and per-node adjacency cache.

Latency table (depths 1–60, 30 samples per bucket)

hops	min	median	p95	max
1	17.5µs	94.8µs	319.5µs	328.0µs
2	15.6µs	106.6µs	137.0µs	342.8µs
3	19.7µs	162.3µs	225.5µs	229.9µs
4	21.0µs	342.7µs	4.6ms	6.3ms
5	22.1µs	1.23ms	4.97ms	36.4ms
6	21.0µs	1.26ms	1.57ms	1.96ms
7	18.9µs	1.56ms	4.98ms	16.0ms
8	22.8µs	2.39ms	24.6ms	39.6ms
9	19.9µs	46.3ms	51.7ms	53.6ms
10	27.1µs	44.5ms	51.4ms	53.2ms
11	22.9µs	51.7ms	57.3ms	67.3ms
12	21.5µs	63.4ms	79.6ms	85.3ms
13	25.5µs	76.6ms	84.2ms	90.8ms
14	25.8µs	78.9ms	89.1ms	106.3ms
15	23.6µs	80.8ms	93.1ms	93.3ms
16	24.0µs	97.9ms	112.7ms	115.6ms
17	24.5µs	108.8ms	113.3ms	125.2ms
18	30.0µs	111.0ms	118.7ms	131.0ms
19	24.3µs	121.1ms	135.3ms	141.1ms
20	23.5µs	134.2ms	146.0ms	148.3ms
21	25.3µs	137.1ms	150.0ms	161.2ms
22	25.0µs	147.3ms	167.0ms	175.1ms
23	29.5µs	152.4ms	162.5ms	163.4ms
24	23.3µs	157.4ms	171.3ms	172.6ms
25	25.5µs	180.7ms	280.1ms	357.7ms
26	25.6µs	181.4ms	207.3ms	301.1ms
27	23.7µs	182.0ms	192.6ms	195.4ms
28	27.1µs	188.7ms	202.5ms	210.3ms
29	25.8µs	211.4ms	232.3ms	236.4ms
30	24.0µs	210.9ms	223.5ms	229.4ms
31	23.4µs	212.3ms	234.7ms	237.9ms
32	22.5µs	218.8ms	239.4ms	242.9ms
33	23.5µs	241.4ms	260.9ms	268.6ms
34	24.0µs	239.3ms	254.6ms	255.3ms
35	26.6µs	246.1ms	259.4ms	264.6ms
36	24.0µs	275.2ms	290.6ms	296.0ms
37	24.9µs	274.5ms	289.1ms	293.8ms
38	24.4µs	277.5ms	292.0ms	299.0ms
39	26.1µs	282.4ms	297.4ms	301.7ms
40	28.8µs	612.7ms	640.3ms	642.4ms
41	26.8µs	614.3ms	644.0ms	652.3ms
42	24.5µs	618.7ms	648.0ms	652.6ms
43	25.0µs	640.0ms	665.9ms	666.9ms
44	27.7µs	694.4ms	781.8ms	800.9ms
45	26.0µs	684.7ms	725.2ms	732.4ms
46	25.5µs	683.1ms	704.1ms	710.8ms
47	25.8µs	709.6ms	738.5ms	751.8ms
48	26.7µs	751.3ms	867.6ms	897.4ms
49	24.6µs	764.2ms	940.3ms	984.9ms
50	25.3µs	770.0ms	794.9ms	798.8ms
51	25.5µs	789.7ms	835.4ms	854.2ms
52	28.7µs	818.3ms	864.7ms	872.7ms
53	25.4µs	817.7ms	845.3ms	884.1ms
54	25.4µs	821.3ms	856.9ms	862.5ms
55	26.4µs	879.1ms	1.02s	1.03s
56	25.5µs	1.00s	1.08s	1.11s
57	25.0µs	976.8ms	1.08s	1.17s
58	25.6µs	972.6ms	1.12s	1.13s
59	28.7µs	1.01s	1.06s	1.08s
60	25.4µs	1.02s	1.05s	1.07s

Observations

Three distinct latency regimes show up clearly:

1. Depths 1–4: sub-millisecond. Median 95µs–340µs. BFS visits a few hundred nodes; everything fits in the adjacency cache and the edge body cache.
2. Depths 5–8: 1–3ms median, jumpy tail. Mid-range traversals where the working set just barely exceeds what was cached from earlier benches; tail latencies (p95/max) are noisy because individual queries hit cold subgraphs.
3. Depths 9+: linear scaling with hop count, ~14ms per hop through depth 39, then a 2× discontinuity at depth 40. The median jumps from 282ms → 613ms.

The depth-40 discontinuity

The cliff is consistent with cache-budget exhaustion. The default nodeCacheMaxEntries is 50,000. At depth ~40 over a graph of avg degree 16, BFS visits roughly 40 × 5K avg breadth ≈ 200K nodes — well past the 50K node-cache budget. Beyond that point every neighbor visit pays a fresh Badger iterator hit + edge body decode rather than serving from cache.

Tunable via BadgerEngineOptions.NodeCacheMaxEntries if you want sub-100ms response at depth 60+; raise it past the working set size or split per-node and per-edge cache budgets so a long traversal doesn't evict the path it just walked.

The min column is misleading

The bench's first iteration in each bucket warms the executor's SmartQueryCache (60s TTL). Subsequent iterations with the same (cypher, params) shape — which several queries within a bucket happen to share by coincidence of the random pair sampler — short-circuit through that cache, hence the consistent ~25µs floor across all depths. The median is the honest signal; p95/max show how cache misses look at scale.

Practical takeaway

For a 500K-node, ~4M-edge graph, this delivers:

• Sub-millisecond shortestPath at depths 1–4
• Single-digit milliseconds at depths 5–8
• Linear ~14ms-per-hop through depth ~40
• ~1s for paths spanning the full sector chain (depth 60)

All of this is in-process; HTTP/Bolt overhead adds the usual 1–2ms on top.

Reproducing

go test ./pkg/cypher/ -run TestLargeScaleShortestPath_HopBuckets \
    -timeout 30m -largescale -v

The -largescale flag is required; without it the test skips. Depth ceiling is LARGESCALE_MAX_DEPTH=60 by default — set it lower to spend less time on long-tail buckets while iterating.