Multi-hop graph traversal inside SurrealDB

If you store a knowledge graph, there is a good chance you walk it twice. Once when you write the edges, and once, on every single query, in a loop that lives in application code:

frontier = [seed]
for depth in range(3):
    edges = db.query("SELECT out, relation_type, confidence FROM related_to WHERE in IN $f", f=frontier)
    frontier = [e["out"] for e in edges if e["relation_type"] in TYPES and e["confidence"] >= 0.7]
    ...

That loop is breadth-first search, hand-rolled over a database connection. It usually exists for a good historical reason: at some point the traversal was faster in the app than in the database, someone benchmarked it, and the loop stayed. On SurrealDB 3.x that trade-off has flipped: graph execution is a first-class part of the query engine. Every hop you walk in application code is a network round trip, a serialized result set, and a filter the planner never got to see.

This post takes a GraphRAG-style retrieval workload (2,000 entities, 16,000 typed edges, 800 documents) and moves the walk server-side, step by step:

Why does the application-side loop cost more than it looks?

Three hops of hand-rolled BFS against this dataset:

Both return the same 14 entities. The latency gap on localhost is the least interesting column: on a real network, six round trips against a database 1 ms away is 6 ms of pure waiting before any work happens. The interesting columns are the other two:

• •

  Round trips are serial. Hop n+1 cannot start until hop n has been received, filtered, and de-duplicated in your process. The database sits idle in between.

• •

  The bytes are the pruning you didn't push down. The app-side loop pulls every outgoing edge of the frontier across the wire and then throws most of them away in Python. The server-side version applies the same predicates during the walk and returns only what survives.

Those numbers come from bfs_bench.py, which runs both implementations and asserts they return an identical set before reporting timings; reproduce them yourself at the end of this post.

What you'll need

Just the surreal binary:

curl -sSf https://install.surrealdb.com | sh

Start a throwaway in-memory server and load the data:

surreal start --user root --pass root memory

surreal import --endpoint http://127.0.0.1:8000 -u root -p root --ns kg --db kg schema.surql
surreal import --endpoint http://127.0.0.1:8000 -u root -p root --ns kg --db kg seed.surql   # ~10s

Both files start with OPTION IMPORT;, which surreal import requires; it disables events and field processing for bulk speed. surreal import prints no query results, so run the queries over the HTTP /sql endpoint instead (piping a file into surreal sql is line-buffered and mangles multi-line statements):

curl -s -X POST http://127.0.0.1:8000/sql -u root:root \
  -H "surreal-ns: kg" -H "surreal-db: kg" -H "Accept: application/json" \
  --data-binary @queries.surql

Step 1: the schema

Two node tables, two RELATION tables. related_to carries the two fields the traversal prunes on: a relation_type and a confidence score written by whatever extracted the edge. kb is the corpus/tenant partition every query filters on.

DEFINE TABLE OVERWRITE entity SCHEMAFULL;
DEFINE FIELD OVERWRITE name      ON entity TYPE string;
DEFINE FIELD OVERWRITE kind      ON entity TYPE string
    ASSERT $value IN ['product', 'component', 'error', 'concept'];
DEFINE FIELD OVERWRITE kb        ON entity TYPE string;
DEFINE FIELD OVERWRITE active    ON entity TYPE bool DEFAULT true;
DEFINE FIELD OVERWRITE embedding ON entity TYPE option<array<float, 8>>;

DEFINE TABLE OVERWRITE related_to TYPE RELATION IN entity OUT entity SCHEMAFULL;
DEFINE FIELD OVERWRITE relation_type ON related_to TYPE string
    ASSERT $value IN ['is_a', 'part_of', 'see_also', 'co_occurs'];
DEFINE FIELD OVERWRITE confidence    ON related_to TYPE float
    ASSERT $value >= 0.0 AND $value <= 1.0;

DEFINE TABLE OVERWRITE mentions TYPE RELATION IN document OUT entity SCHEMAFULL;
DEFINE FIELD OVERWRITE confidence ON mentions TYPE float;

-- ---------------------------------------------------------------------------
-- Three indexes, and it is worth being precise about what each is for:

-- Entry point: queries seed the traversal by corpus.
DEFINE INDEX OVERWRITE idx_entity_kb   ON entity FIELDS kb;
DEFINE INDEX OVERWRITE idx_entity_name ON entity FIELDS name;

-- Vector seed for the hybrid pattern.
DEFINE INDEX OVERWRITE idx_entity_vec ON entity FIELDS embedding
    HNSW DIMENSION 8 DIST COSINE TYPE F32 EFC 150 M 12;

-- Edge de-duplication, NOT a traversal index.
DEFINE INDEX OVERWRITE idx_rel_unique ON related_to FIELDS in, out, relation_type UNIQUE;

The common instinct when moving traversal server-side is to index in and out on the edge table. You don't need to, and Step 9 shows why: arrow traversal never looks at a secondary index at all.

The seed data is synthetic but shaped like the real thing: is_a / part_of / see_also edges are high-confidence and sparse (one per entity, mean confidence 0.84 / 0.87 / 0.72), while co_occurs edges are noisy and dense: five per entity, mean confidence 0.49. That mix is what makes an unpruned walk explode.

Step 2: measure the frontier before you tune anything

The first question is not "how fast is a hop" but "how many nodes does a hop reach". Start at one entity and count:

SELECT
    array::len(->related_to->entity)                                       AS hop1,
    array::len(->related_to->entity->related_to->entity)                   AS hop2_paths,
    array::len(array::distinct(->related_to->entity->related_to->entity))  AS hop2_nodes,
    array::len(->related_to->entity->related_to->entity->related_to->entity)
                                                                           AS hop3_paths,
    array::len(array::distinct(
        ->related_to->entity->related_to->entity->related_to->entity))     AS hop3_nodes,
    -- `+collect` returns the de-duplicated union of every node within 3 hops.
    array::len($seed.{1..3+collect}(->related_to->entity))                 AS reachable
FROM $seed;

[{ "hop1": 8, "hop2_paths": 64, "hop2_nodes": 63, "hop3_paths": 512, "hop3_nodes": 451, "reachable": 512 }]

Eight edges become 512 walked paths at depth three, and the de-duplicated three-hop neighbourhood is 512 of 2,000 entities, a quarter of the graph, from one seed. Nothing here is a database performance problem; it is a cardinality problem, and it would be exactly as bad in application code. The difference is where you can cheaply do something about it.

Step 3: push the filters into the traversal

SurrealQL puts a predicate on each half of a hop: the first bracket filters the edge, the second filters the node it lands on.

SELECT
    name,
    ->related_to[WHERE relation_type IN $types AND confidence >= $min_conf]
    ->entity[WHERE kb = $kb AND active = true].name AS neighbours
FROM $seed;

[{ "name": "concept-7", "neighbours": ["error-22", "error-62"] }]

Eight neighbours became two. The co_occurs noise never leaves storage, and the cross-corpus and inactive nodes never materialize. The part that matters at depth: those six discarded neighbours never get expanded at the next hop. The application-side loop filters after the rows have crossed the wire, one hop too late to keep the next hop small.

Step 4: the recommended pattern: recursive traversal with a depth range

Repeating ->related_to->entity three times works, but the depth is baked into the query text. The recursion syntax takes a range and a body, and +collect returns the de-duplicated set of everything visited:

LET $ctx = array::distinct($seed.{1..3+collect}(
    ->related_to[WHERE relation_type IN $types AND confidence >= $min_conf]
    ->entity[WHERE kb = $kb AND active = true]
));
RETURN array::len($ctx);
SELECT id, name, kind FROM $ctx ORDER BY id LIMIT 5;

14
[
  { "id": "entity:22",  "kind": "error",   "name": "error-22" },
  { "id": "entity:62",  "kind": "error",   "name": "error-62" },
  { "id": "entity:67",  "kind": "concept", "name": "concept-67" },
  { "id": "entity:167", "kind": "concept", "name": "concept-167" },
  { "id": "entity:187", "kind": "concept", "name": "concept-187" }
]

512 reachable nodes become a 14-entity context set, in one statement, with the depth (1..3) as an ordinary part of the query you can raise or lower per request. That set is small enough to hand to a language model; the unpruned one never was.

One constraint to know: the recursion body must be a graph path. You cannot wrap it in a function or project fields inside it: .{1..3+collect}(->related_to->entity.{id, name}) fails with "Expected a record ID during recursive graph traversal". Collect the ids first, then SELECT the fields you want from them, as above.

Step 5: capping the frontier, and the footgun that comes with it

Predicate pruning fails you in one specific case: a mega-node whose edges are all legitimate. For that, slice the edge set per hop. entity:1 reaches 488 nodes in three unpruned hops; capping every hop at three edges brings it to 39:

RETURN array::len(array::distinct(entity:1.{1..3+collect}(->related_to->entity)));          -- 488
RETURN array::len(array::distinct(entity:1.{1..3+collect}(->related_to[0..3]->entity)));    -- 39

Two caveats, both sharp:

An out-of-range slice evaluates to NONE, not to the short array. If a hop has fewer than K matching edges, that branch produces nothing at all. Combine a cap with a selective predicate and the whole traversal usually collapses:

RETURN array::len(array::distinct($seed.{1..3+collect}(
    ->related_to[WHERE relation_type IN $types AND confidence >= $min_conf][0..3]
    ->entity)));  -- 0: only two edges survive the filter at hop 1

The cap takes an arbitrary K, not the best K. [0..3] slices in record-id order; there is no ordering step inside the recursion body. Use it to bound blast radius on dense hubs, not to select the strongest edges; for that, raise the confidence threshold instead.

Step 6: return the walk, not just the destination

Swap +collect for +path and each result is the route taken. That is your citation trail: not just what the retriever surfaced, but why.

RETURN array::slice($seed.{1..3+path}(
    ->related_to[WHERE relation_type IN $types AND confidence >= $min_conf]
    ->entity[WHERE kb = $kb AND active = true]
), 0, 3);

[
  ["entity:22", "entity:67", "entity:202"],
  ["entity:22", "entity:67", "entity:482"],
  ["entity:22", "entity:67", "entity:742"]
]

Reconstructing this in the application-side loop means threading parent pointers through every level of the BFS by hand.

Step 7: what retrieval actually wants: ranked documents

The context set is a means, not an end. A retriever wants source documents, ranked by how much of the neighbourhood they cover, which is a reverse hop from the entities into mentions, aggregated:

SELECT
    in.title AS title,
    count() AS entities_covered,
    math::round(math::sum(confidence) * 100) / 100 AS score
FROM array::flatten((SELECT VALUE <-mentions FROM $ctx))
WHERE in.kb = $kb
GROUP BY title
ORDER BY entities_covered DESC, score DESC
LIMIT 5;

[
  { "title": "doc-11",  "entities_covered": 4, "score": 3.02 },
  { "title": "doc-191", "entities_covered": 2, "score": 1.61 },
  { "title": "doc-386", "entities_covered": 2, "score": 1.46 },
  { "title": "doc-146", "entities_covered": 1, "score": 0.98 },
  { "title": "doc-86",  "entities_covered": 1, "score": 0.83 }
]

Graph walk, reverse hop, aggregation, and ranking: one statement, one round trip. The application-side version is three more round trips and a defaultdict counter.

Step 8: seed the traversal from a vector search

Traversal assumes you already know where to start. Usually you don't: you have a question, and an embedding of it. Because the vector index lives in the same database as the graph, the seed lookup and the expansion are the same query: no separate vector store, no ids shuttled between two systems.

LET $query_vec = entity:7.embedding;
SELECT id, name, vector::distance::knn() AS dist
FROM entity WHERE embedding <|5,64|> $query_vec ORDER BY dist ASC;

LET $vec_seeds = (SELECT VALUE id FROM entity WHERE embedding <|5,64|> $query_vec);
RETURN array::len(array::distinct(array::flatten($vec_seeds.{1..2+collect}(
    ->related_to[WHERE relation_type IN $types AND confidence >= $min_conf]
    ->entity[WHERE kb = $kb AND active = true]
))));

[
  { "id": "entity:7",    "name": "concept-7",    "dist": 0.0 },
  { "id": "entity:927",  "name": "concept-927",  "dist": 0.0000065369 },
  { "id": "entity:1847", "name": "concept-1847", "dist": 0.0000259079 },
  { "id": "entity:1687", "name": "concept-1687", "dist": 0.0002512339 },
  { "id": "entity:767",  "name": "concept-767",  "dist": 0.0003424725 }
]
26

Five vector hits expand into a 26-entity neighbourhood at depth two. (The distances are tiny because these are synthetic 8-dimensional cluster vectors, not real embeddings. The ordering is what matters here.)

Two HNSW rules that bite silently rather than erroring: the K and EF in <|5,64|> must be literal integers (<|$k, 64|> is a parse error), and the query vector must be a bound parameter or literal array; an inline record-field access inside the operator skips the index and returns null distances.

Step 9: what the planner actually does

Three EXPLAINs settle the indexing question:

EXPLAIN SELECT id FROM entity WHERE kb = $kb;
EXPLAIN SELECT ->related_to->entity FROM $seed;
EXPLAIN SELECT out FROM related_to WHERE in IN [entity:7, entity:22];

SelectProject [ctx: Db] [projections: id]
    IndexScan [ctx: Db] [index: idx_entity_kb, access: = 'kb_alpha', direction: Forward]

Project [ctx: Db]
  field.lookup: GraphEdgeScan [ctx: Db] [direction: ->, tables: related_to, output: TargetVertex]
      CurrentValueSource [ctx: Rt]
    RecordIdScan [ctx: Db] [record_id: entity:7]

SelectProject [ctx: Db] [projections: out]
    Filter [ctx: Db] [predicate: in INSIDE [entity:7, entity:22]]
        UnionIndexScan [ctx: Db] [table: related_to, branches: 2]
            IndexScan [ctx: Db] [index: idx_rel_unique, access: [entity:7], direction: Forward]
            IndexScan [ctx: Db] [index: idx_rel_unique, access: [entity:22], direction: Forward]

Read them in order:

1. 1.

   Index your entry points. Seeding by kb (or by name, or by vector) is a normal lookup and wants a normal index.

2. 2.

   Arrow traversal is a GraphEdgeScan. Edges hang off the record itself; the walk is a direct scan of them, with no secondary index in the plan. Adding DEFINE INDEX ... ON related_to FIELDS in buys the traversal nothing and costs you write throughput.

3. 3.

   Querying the edge table relationally is a different story. SELECT ... FROM related_to WHERE in IN [...], precisely the shape the application-side BFS is forced into, does need an index on in, here served by the unique constraint. Which is the point: the app-side loop creates the indexing requirement that server-side traversal doesn't have.

Filters on edge fields (relation_type, confidence) inside a traversal are applied to the edges already reached, so they need no index either.

Reproducing the benchmark

python3 bfs_bench.py

context set: 14 entities (both approaches agree)

application-side BFS       1.65 ms median   6 round trip(s)   4,905 bytes returned
server-side traversal      0.49 ms median   1 round trip(s)   241 bytes returned

The script asserts that both implementations return the identical 14-entity set before it reports anything: if a future SurrealDB release changes traversal semantics, the assertion fails loudly instead of quietly publishing a wrong number. It also signs in once and reuses a keep-alive connection. HTTP basic auth re-hashes the root password on every request (tens of milliseconds), enough to swamp both measurements if you let it.

The pruning checklist

Three practical notes to close on:

• •

  Prune at every hop, not at the end. A predicate at hop 1 removes an entire subtree at hop 3. This is the whole game at depth ≥ 2.

• •

  Measure the frontier, not the latency. Instrument the size of the returned set first; if a query is slow at three hops, cardinality is almost always the reason.

• •

  2–3 hops is comfortable with good pruning. Beyond that, frontier management stops being a query-tuning exercise and becomes a modelling one: precompute the top-N neighbours per hub node at write time and traverse the precomputed edges instead.

Further reading

• •

  Graph idioms: the recursion syntax in full, +collect and +path, and the per-hop predicates

• •

  RELATE: edge tables, and what TYPE RELATION gives you

• •

  DEFINE INDEX: entry-point indexes and the HNSW knobs (EFC, M, M0)

• •

  EXPLAIN: reading the plans from Step 9 against your own graph

Get started

Point this at your own graph. Take one hand-rolled BFS loop, rewrite it as a single recursive traversal with your predicates on each hop, and compare the round trips and bytes returned.

• •

  Create a free cloud instance

• •

  Start building

• •

  Join our Discord server