Graph retrieval was 70x slower than it needed to be

On a copy of a production knowledgebase with about 306,000 vertices and 671,000 edges, the local search phase of one query took 28.26 s, with every index the graph store is supposed to have already built. Vector search for the same query took 0.04 s. The fix was to stop asking Apache AGE's Cypher layer to do a one-hop neighbour lookup and write that SQL ourselves: expanding 48 entities to their neighbours went from 8.5–11.8 s to 0.13–0.17 s, and local search went from 28.26 s to 0.77 s.

This is how we got there, including the first fix that only half worked, and why I'd now reach for plain SQL any time a graph extension sits on top of a general-purpose query planner.

Where the time went

Our retrieval pipeline keeps its knowledge graph inside PostgreSQL using Apache AGE, the extension that adds Cypher and property-graph storage to Postgres. A mix query runs vector search over chunks, then two graph phases: local search, which takes the entities that matched the question and expands them to their neighbours, and global search, which works from relationships. Then comes rerank and the answer.

On the production knowledgebase, one mix query broke down like this:

Measured on the production graph before any of this work, from the plan document.

Vector search at 0.05 s told us the database itself was fast, so the slow part was the AGE graph access paths. We set two conditions. Each graph phase had to finish in under one second on production hardware, for knowledgebases of any size, and retrieval results had to be byte-identical before and after every change, because we were rewriting the most fundamental part of the product.

The missing indexes got us halfway

The first EXPLAIN was not subtle:

Seq Scan on base n  (cost=0.00..45150.34)
  Filter: (properties @> '{"entity_id": "<entity>"}'::agtype)
  Rows Removed by Filter: 306424
  Execution Time: 151.293 ms

Every entity lookup scanned all of the vertices to find one row, at 151 ms a go, and global search does around 100 of those per query. The graph tables carried only AGE's two internal primary keys.

Our code already had the index DDL: the graph storage's initialize() builds a full set of functional btree, GIN and edge indexes. Graphs lacked them because of a fast-path that assumed "the graph exists, so the indexes exist". Knowledgebase imports, and any query that touched a graph name before it was initialised, created the graph bare, and from then on the fast-path skipped the DDL forever. The production knowledgebase had been imported, so it had none of the canonical set, only a GIN index I'd added by hand earlier.

That GIN index on properties serves Cypher's containment match (properties @> {...}), but several of our direct-SQL helpers look entities up with an equality on entity_id, which a GIN can't serve. Those need the functional btree. The hand-added GIN fixed one path and missed the other, which is why local search was still around 17 s.

So we wrote a backfill that brings every existing graph up to the canonical index set, and changed the fast-path to check for a sentinel index in pg_index instead of trusting the graph row. The backfill follows four rules:

• Plain CREATE INDEX, never CONCURRENTLY. A concurrent build waits out every open snapshot in the database, and this workload always has long readers (17-second graph reads for a start). We'd already seen an 8-minute stall from exactly that. A plain build takes a SHARE lock, which blocks writers but never readers, and took about 3 s per index on this graph.
• lock_timeout of 10 s on every statement, so a build that can't get its lock gives up and retries later instead of stalling a graph merge.
• Drop INVALID indexes first. CREATE INDEX IF NOT EXISTS matches an invalid leftover by name and silently does nothing, so a failed build hides itself forever.
• Dedupe by index definition, not name, then ANALYZE each graph serially. The functional index only gets planner statistics from ANALYZE.

The order of deployment mattered too. The hardened fast-path had to ship after the backfill had run everywhere; otherwise the first load of an old knowledgebase would have tried to build all its indexes concurrently while holding the graph-initialisation lock.

Node lookups on production dropped to 0.100 ms, and production local search went from 17 s to 9.43 s and global search to 3.97 s, still on the old query code. The local copy, though, had carried every canonical index from the start, and its local search still took 28.26 s, so indexes alone were not going to fix the traversal.

Why AGE's join plan scans the whole graph

AGE stores each vertex label as a table (ours is base) with an agtype properties column, and each edge label as a table that inherits from a parent, _ag_label_edge, with start_id and end_id columns. A Cypher query is wrapped in a cypher() function call, compiled to SQL joins over those tables, and handed to the ordinary Postgres planner.

The neighbour expansion looked like this (the outgoing half; the incoming half flips the arrow):

SELECT * FROM cypher('<graph>', $$
  UNWIND [<ids>] AS node_id
  MATCH (n:base {entity_id: node_id})
  OPTIONAL MATCH (n:base)-[]->(connected:base)
  RETURN node_id, connected.entity_id AS connected_id
$$) AS (node_id text, connected_id text)

What we wanted is O(degree): find the vertex, walk the edge index on start_id, fetch the vertex on the other end. The planner saw three relations to join, one of them connected:base with 305,000 rows. Our plan analysis showed a sequential scan of base connected as the outer loop, checking the indexed edge once per vertex. On the local copy with every index in place, the measured plan was a merge join that walked 67,886 edge-index entries to resolve two nodes. Either way the work scaled with the size of the graph, not the degree of the node.

A general-purpose planner can't see that connected is only ever reached through a single edge from a single known vertex. It costs the query as a join like any other.

The same thing was happening one step later. Local and global search both fetch edge properties for batches of (source, target) pairs, and that was Cypher too:

UNWIND $pairs AS p
WITH p.src AS src_eid, p.tgt AS tgt_eid
MATCH (a:base {entity_id: src_eid})
MATCH (b:base {entity_id: tgt_eid})
MATCH (a)-[r]->(b)
RETURN src_eid AS source, tgt_eid AS target, properties(r) AS edge_properties

That cost about 13 ms per pair. Measured on its own, a 9.9k-pair expansion took 132 s, against 1.05 s for the edge-degree lookup that runs alongside it.

Walking the edge index directly

The replacement for neighbour expansion is plain SQL against the same tables AGE uses:

WITH input(v) AS (
  SELECT v FROM unnest($1::text[]) AS t(v)
),
ids(node_id) AS (
  SELECT (to_json(v)::text)::agtype FROM input
),
vids AS (
  SELECT b.id AS vid, i.node_id
  FROM <graph>.base b
  JOIN ids i
    ON ag_catalog.agtype_access_operator(
         VARIADIC ARRAY[b.properties, '"entity_id"'::agtype]
       ) = i.node_id
)
SELECT v.node_id::text AS node_id, 'out' AS dir,
       ag_catalog.agtype_access_operator(
         VARIADIC ARRAY[cb.properties, '"entity_id"'::agtype]
       )::text AS connected_id
FROM vids v
JOIN <graph>."_ag_label_edge" e ON e.start_id = v.vid
JOIN <graph>.base cb ON cb.id = e.end_id
UNION ALL
-- same again with e.end_id = v.vid and cb.id = e.start_id, dir 'in'

The vids CTE resolves each entity through the functional btree on entity_id. The edge joins hit the start and end indexes on the parent edge table, and the join back to base fetches the neighbour by primary key. Nothing in there gives the planner a reason to scan 305,000 rows. The pair lookup got the same treatment, joining both resolved endpoints to _ag_label_edge on the composite start-and-end index, which makes it one index probe per pair.

The SQL is short. Making it return exactly what Cypher returned took more care, and getting any of these wrong would have silently changed what the model gets shown:

The scan has to be on the parent _ag_label_edge, not on the DIRECTED label table. Our ontology extraction writes typed relationship labels as separate edge tables, and Postgres inheritance means a scan of the parent covers them all. A DIRECTED-only query would quietly drop exactly the typed relationships that extraction exists to surface.

Both endpoints are inner-joined to base. That reproduces the (n:base)-[]-(connected:base) pattern exactly, and it keeps out the bridge edges Certant Strata uses, since a bridge never connects two base vertices.

Entity ids are bound raw and escaped by to_json(). The old code ran ids through a normaliser built for interpolating Cypher string literals. Pass a normalised id as a SQL parameter and it gets escaped twice, resolves to no vertex, and that entity comes back with no neighbours at all. Any id with a double quote or backslash in it would have been hit, and our graphs have real ones: entity names with inch sizes in them, for a start.

The vertex lookup is a CTE join, not a scalar subquery, because duplicate entity_id relics can exist, and a scalar subquery returning two rows is an error. The join expands each duplicate the same way the Cypher MATCH did.

UNION ALL with no DISTINCT, to keep the multiplicity of parallel edges. The caller dedupes.

Edge properties are cast with ::varchar, not ::text. AGE's agtype-to-text cast only works on scalars and raises "agtype argument must resolve to a scalar value" on a property map.

One more change went in before any of this. Local search sorts relations by rank and weight, then truncates to a token budget, and that sort had no tiebreaker. Relations tied at the truncation boundary came out in whatever order the plan produced them, so the context sent to the answer model was already nondeterministic, and any index or query change would perturb it. We added a two-pass stable sort (by the source-target key first, then the existing rank and weight sort) so that before-and-after comparisons could be exact.

Proving it returned the same answers

The gate for shipping was a script that runs the old Cypher implementation and the new SQL against the same real nodes and compares sorted output. It covers five graph shapes, each chosen to catch one of the traps above: zero-degree, high-degree and special-character entities; a knowledgebase where two entities are joined only by a typed relationship; a Strata knowledgebase with bridge edges; duplicate entity_id vertices; and self-loops.

All 45 checks passed, byte-identical. The only difference in behaviour was in the new code's favour: nine out of ten real entity ids containing special characters crashed the old implementation with a KeyError: it keyed its results by the normalised id while Cypher returned the raw one. That bug was live in the shipping code. The SQL path keys everything by the raw id, so those entities now get their neighbours.

We kept the Cypher implementation in the code for one release behind an environment flag, both as a rollback that doesn't need a redeploy and as the reference the comparison script runs against.

The numbers

On the local copy of the production knowledgebase (306k vertices, 671k edges, full index set):

Local measurements, 4 July 2026, from the project notes and the plan document's addendum.

With only the neighbour expansion rewritten, local search dropped from 28.26 s to 15.26 s, with the traversal down to 0.15 s and the rest sitting in the per-pair edge lookup. Rewriting that too is what took local search to 0.77 s, a 37x improvement, and global search to 1.21 s, because global search goes through the same pair lookup.

On a pre-production copy of the same graph that had been imported bare, with neither the indexes nor the new code, one fixed query's local search took 1,004.80 s. With both, it took 0.90 s, and global search went from 35.08 s to 1.27 s.

In production, an internal mix query ran local search in 0.43 s and global in 1.28 s. A streamed query through the chat interface ran local search in 0.39 s and global in 1.35 s, with the whole answer arriving in 19.07 s. The rest of that time is rerank and answer generation. In later warm measurements the graph phases sat at 0.4–0.9 s while the answer model's time ranged from 2 s to 24 s across samples, and the graph stayed fast even on the 24-second run. A cold first query on a freshly deployed instance took 2.6 s in the graph phase before the Postgres buffers warmed.

In those acceptance runs global search was still just over a second, so the target isn't fully met there. Profiling it is the open follow-up.

When to bypass the graph query language

Cypher on AGE is fine for exploration and for ad hoc queries whose shape you don't know in advance. It hurt us on the two fixed-shape queries on the hot path: one hop out from a known vertex, and an edge between two known vertices. Those were being compiled into generic joins and costed by a planner that has no idea a graph traversal is involved.

If you run a property graph as an extension over a general-purpose relational engine, this is what I'd check:

1. Run EXPLAIN ANALYZE on the SQL that your hot Cypher queries turn into, with production-sized data. Look at what the outer loop scans.
2. Check that the indexes exist and that the specific lookup uses them. Containment and equality want different index types.
3. If the plan walks a range proportional to the graph when it should be proportional to the degree, write the traversal as SQL against the label tables and let the edge indexes do the work.
4. Scan the parent edge table if you have more than one edge label, and bind parameters raw.
5. Keep the old implementation as a reference and compare outputs on real data, including the ugly ids, before you switch.