Benchmarking GDS shortestPath Against Hand-Written Cypher

Someone posts a benchmark showing GDS Dijkstra is “50× faster than Cypher,” and someone else posts one showing the opposite, and both ran real code. The reason they disagree is that one timed only the algorithm on a resident projection and the other timed the projection build on every call. A benchmark that leaves out the gds.graph.project cost is comparing a warm cache against a cold engine — apples to oranges — and it will send you to the wrong architecture. This page gives you one async harness that times three things on the same graph and driver: GDS with the projection built once and reused, GDS with the projection built and dropped per query (the honest cold number), and a bounded live Cypher traversal. It reports p50 and p95 for each so you can read where the crossover actually sits on your data instead of on someone’s blog. The decision this measurement feeds is laid out in Neo4j GDS vs Custom Cypher Routing.

Prerequisites & Versions

The harness uses only the async driver, the standard library, and the GDS plugin already installed on the server. No graphdatascience client is required — GDS procedures are called as ordinary Cypher.

pip install "neo4j>=5.18"

The graph must already carry a stable id index and a numeric routing weight (travel_s) on the relationship, exactly as modeled in the parent guide. Benchmark against a graph whose size and topology resemble production — the whole point is defeated by a toy graph, as the failure patterns below explain.

Implementation

The harness runs a warm-up pass (untimed, to prime the page cache and JIT the driver’s serialization path), then collects latency samples for each strategy and prints percentiles. The cold-GDS sample deliberately wraps project + stream + drop in a single timed block, because that is what a request pays when it cannot reuse a projection.

import asyncio
import time
from neo4j import AsyncGraphDatabase

GDS_PROJECT = (
    "CALL gds.graph.project($g, 'RoadNode', "
    "{CONNECTED_TO: {properties: 'travel_s'}}) "
    "YIELD graphName RETURN graphName"
)
GDS_DROP = "CALL gds.graph.drop($g, false) YIELD graphName RETURN graphName"
GDS_STREAM = """
MATCH (s:RoadNode {id: $src}), (t:RoadNode {id: $dst})
CALL gds.shortestPath.dijkstra.stream($g, {
    sourceNode: s, targetNode: t, relationshipWeightProperty: 'travel_s'
})
YIELD totalCost RETURN totalCost AS cost
"""
CYPHER_ROUTE = """
MATCH (s:RoadNode {id: $src}), (t:RoadNode {id: $dst})
MATCH p = (s)-[:CONNECTED_TO*1..15]->(t)
WITH reduce(c = 0.0, r IN relationships(p) | c + r.travel_s) AS cost
RETURN min(cost) AS cost
"""


def percentile(samples: list[float], p: float) -> float:
    """Linear-interpolated percentile; p in [0, 1]."""
    s = sorted(samples)
    k = (len(s) - 1) * p
    lo = int(k)
    hi = min(lo + 1, len(s) - 1)
    return s[lo] + (s[hi] - s[lo]) * (k - lo)


async def _time_call(coro_factory) -> float:
    start = time.perf_counter()
    await coro_factory()
    return (time.perf_counter() - start) * 1000.0  # milliseconds


async def bench(driver, src: str, dst: str, reps: int = 200, cold_reps: int = 20):
    async with driver.session(database="neo4j") as s:

        async def gds_stream():
            await (await s.run(GDS_STREAM, g="warm", src=src, dst=dst)).consume()

        async def cypher_route():
            await (await s.run(CYPHER_ROUTE, src=src, dst=dst)).consume()

        async def gds_cold_cycle():
            await (await s.run(GDS_PROJECT, g="cold")).consume()
            try:
                await (await s.run(GDS_STREAM, g="cold", src=src, dst=dst)).consume()
            finally:
                await (await s.run(GDS_DROP, g="cold")).consume()

        # --- warm-up: prime page cache + plan cache, results discarded ---
        await (await s.run(GDS_PROJECT, g="warm")).consume()
        for _ in range(20):
            await gds_stream()
            await cypher_route()

        # --- resident-projection GDS: project once, time the streams ---
        warm_gds = [await _time_call(gds_stream) for _ in range(reps)]

        # --- live Cypher: time each bounded traversal ---
        cypher = [await _time_call(cypher_route) for _ in range(reps)]

        await (await s.run(GDS_DROP, g="warm")).consume()

        # --- cold GDS: project + stream + drop counted as one request ---
        cold_gds = [await _time_call(gds_cold_cycle) for _ in range(cold_reps)]

    return {"gds_warm": warm_gds, "cypher": cypher, "gds_cold": cold_gds}


def report(name: str, samples: list[float]) -> None:
    print(
        f"{name:<12} n={len(samples):<4} "
        f"p50={percentile(samples, 0.50):8.2f} ms  "
        f"p95={percentile(samples, 0.95):8.2f} ms"
    )


async def main():
    driver = AsyncGraphDatabase.driver(
        "neo4j+s://your-cluster.databases.neo4j.io",
        auth=("neo4j", "secure-password"),
        max_connection_pool_size=20,
    )
    try:
        results = await bench(driver, src="N-1001", dst="N-2087")
        report("GDS warm", results["gds_warm"])
        report("Cypher", results["cypher"])
        report("GDS cold", results["gds_cold"])
    finally:
        await driver.close()


if __name__ == "__main__":
    asyncio.run(main())

Numbers like these are illustrative — the shape is what matters. GDS cold is dominated by the projection build, GDS warm is a raw in-memory algorithm run, and Cypher sits between them. Where your workload lands on the amortized curve decides everything.

How It Works

Three details make the harness honest, and each maps to a line in the code:

• Warm-up is separated from measurement. The first 20 iterations run untimed. This lets the OS page cache load the working set, the Neo4j plan cache compile the query once, and the driver’s Bolt serialization path settle. Without it, the first sample carries cold-start cost that has nothing to do with steady-state latency, and it lands disproportionately in p95.
• The cold GDS sample wraps the full lifecycle. gds_cold_cycle times project + stream + drop as one unit. This is the number a stateless request pays when it cannot reuse a projection, and it is the one dishonest benchmarks omit. Timing only gds_stream after a resident projection gives you the GDS warm number, which is real but only achievable if your architecture actually keeps the projection resident.
• Cypher and warm GDS use identical reps and the same session. Both collect reps samples over one pooled session so pool acquisition, network round-trip, and result draining are counted the same way for both. The comparison is only fair if the overhead outside the algorithm is held constant.

percentile() interpolates rather than picking a nearest rank, so p95 is stable even at modest sample counts. Reporting p50 and p95 together is deliberate: p50 tells you the typical cost, p95 tells you the tail that your SLO actually has to survive. A strategy with a great median and a terrible tail — common for cold GDS, where an occasional large projection stalls — looks fine on averages and fails in production. For the algorithmic reason GDS Dijkstra and the Cypher expansion can even be compared head to head, see Routing Algorithms in Python.

Common Failure Patterns

1. Excluding projection cost. The headline mistake. Timing gds.shortestPath.dijkstra.stream against a projection you built once, then presenting it as “GDS latency,” compares a warm in-memory structure against Cypher’s cold walk of the live graph. If your service is stateless and rebuilds the projection per request, the honest number is the full cycle:

# WRONG for a stateless service — projection cost hidden
latency = await _time_call(gds_stream)          # 6 ms, but a lie if you re-project
# RIGHT — count what the request actually pays
latency = await _time_call(gds_cold_cycle)      # 840 ms, project + stream + drop

Report the number that matches your deployment. If you keep a resident projection, gds_warm is honest; if you do not, gds_cold is.

2. Tiny, unrepresentative graphs. A 50-node test graph makes both engines look instant and inverts the result: projection overhead dominates so Cypher “wins,” and you conclude GDS is useless. On a real continental graph the algorithm cost grows and the projection amortizes across many queries, flipping the verdict. Benchmark on a graph whose node count, degree distribution, and query span match production, or the crossover point you measure is fiction.

3. Ignoring page-cache and JIT warm-up. The first query after a fresh connection pays for cache misses and query compilation. Fold that into your samples and p95 spikes for reasons unrelated to the algorithm:

# Drop the warm-up loop and the first samples poison the tail
samples = [await _time_call(cypher_route) for _ in range(200)]  # sample 0 is cold
# Prime first, measure second (as bench() does)
for _ in range(20):
    await cypher_route()                                        # discarded
samples = [await _time_call(cypher_route) for _ in range(200)]

Performance Notes

The amortized cost per query for GDS is the projection lifecycle spread across the queries it serves, plus the per-stream algorithm time; Cypher pays a flat per-query cost:

$$C_\text{GDS}(N) = \frac{T_\text{project} + T_\text{drop}}{N} + t_\text{stream}, \qquad C_\text{Cypher} = t_\text{cypher}$$

The crossover $N^{*}$ — the reuse count above which GDS is cheaper per query — is found by setting them equal:

$$N^{*} = \frac{T_\text{project} + T_\text{drop}}{t_\text{cypher} - t_\text{stream}}$$

With the illustrative numbers from the chart ($T_\text{project} + T_\text{drop} \approx 840$ ms, $t_\text{cypher} \approx 22$ ms, $t_\text{stream} \approx 6$ ms), $N^{*} \approx 840 / 16 \approx 53$. Serve fewer than ~53 queries per projection and live Cypher is the cheaper choice; serve more and GDS pulls ahead — the gap widening toward $t_\text{stream}$ as $N$ grows. Plug your own measured values into that formula and you have a defensible architecture decision instead of a vibe.

Budget the benchmark itself against wall time: 200 warm reps plus 20 cold cycles is a few seconds of Cypher and warm GDS but potentially minutes of cold cycles on a large graph, since each cold cycle rebuilds the projection. Keep cold_reps small and rely on the resident-projection samples for tight percentiles. The plan-cache and seek-versus-scan hygiene that keeps t_cypher stable across runs is covered in cypher performance tuning.

Related

• Neo4j GDS vs Custom Cypher Routing: When to Use Each — the decision this benchmark informs, with the full cost model and trade-offs.
• Routing Algorithms in Python — the Dijkstra and A* internals both strategies execute.
• Cypher Performance Tuning — keeping the live-traversal latency stable and index-backed across runs.

This guide supports Neo4j GDS vs Custom Cypher Routing, part of Network Routing Algorithms in Python.

For authoritative reference, consult the Neo4j Graph Data Science documentation.