--- title: "Multi-hop graph traversal inside SurrealDB" description: "Move breadth-first search into SurrealDB: recursive traversal with a depth range, predicates pushed into every hop, and what EXPLAIN says about edge indexes." url: https://surrealdb.com/blog/multi-hop-graph-traversal-inside-surrealdb date: 2026-09-08 authors: "Martin Schaer" --- # Multi-hop graph traversal inside SurrealDB ![Multi-hop graph traversal inside SurrealDB](https://cdn.surrealdb.com/zmcgast89tb20zbwxie6k102.auto) 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: ```python 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: - measuring the frontier explosion before doing anything about it, - pushing edge and node predicates *into* the traversal, - recursive traversal with a depth range, in one statement, - capping the frontier at each hop (and the footgun that comes with it), - returning the walk itself for citations, - seeding the traversal from a vector search, in the same query, - and what `EXPLAIN` says about which indexes actually matter. --- ## Why does the application-side loop cost more than it looks? Three hops of hand-rolled BFS against this dataset: | | Application-side BFS | Server-side traversal | | --- | --- | --- | | Round trips | 6 | 1 | | Bytes returned | ~4,900 | 241 | | Median latency (localhost) | ~1.5 ms | ~0.5 ms | 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`](https://gist.github.com/martinschaer/fabb6f0aeb294677f356c5404927b57e), 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: **Bash** ```bash curl -sSf https://install.surrealdb.com | sh ``` **PowerShell** ```powershell iwr https://windows.surrealdb.com -useb | iex ``` | File | Purpose | | --- | --- | | [`schema.surql`](https://gist.github.com/martinschaer/5129f6a59ddb8fc5f9ffc5421a0c554c) | Entities, documents, the two edge tables, and the indexes | | [`seed.surql`](https://gist.github.com/martinschaer/b17463942c6c292b2f5c3a4acc5a2962) | 2,000 entities, 16,000 typed edges, 800 documents, 3,197 mentions | | [`queries.surql`](https://gist.github.com/martinschaer/0b2c73a7a8619cb4a5e8a1573f43d58d) | Every traversal in this post | | [`bfs_bench.py`](https://gist.github.com/martinschaer/fabb6f0aeb294677f356c5404927b57e) | Application-side BFS vs. server-side traversal, with an equality assertion | Start a throwaway in-memory server and load the data: ```bash 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): ```bash 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. ![Schema diagram](https://cdn.surrealdb.com/w(1600)q(80)/nkzh5v87mwxk1nwwuf3sh443.auto) ```surql 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>; 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](#step-9-what-the-planner-actually-does) 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: ```surql 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; ``` ```json [{ "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. ```surql 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; ``` ```json [{ "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: ```surql 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; ``` ```json 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: ```surql 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: ```surql 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*. ```surql 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); ``` ```json [ ["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: ```surql 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; ``` ```json [ { "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. ```surql 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] )))); ``` ```json [ { "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 `EXPLAIN`s settle the indexing question: ```surql 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]; ``` ```text 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. **Index your entry points.** Seeding by `kb` (or by name, or by vector) is a normal lookup and wants a normal index. 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. **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 ```bash python3 bfs_bench.py ``` ```text 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 | Lever | Syntax | Use when | | --- | --- | --- | | Corpus / tenant | `->entity[WHERE kb = $kb]` | Always, at the seed *and* at every hop | | Relation-type whitelist | `->related_to[WHERE relation_type IN $types]` | Some edge types are noise (`co_occurs` here) | | Confidence floor | `->related_to[WHERE confidence >= 0.7]` | Edges carry extraction scores | | Node visibility | `->entity[WHERE active = true]` | Soft deletes, drafts, per-tenant visibility | | Depth | `.{1..3+collect}` | Always, make it a request parameter, not a constant | | Per-hop cap | `->related_to[0..K]` | Mega-nodes whose edges are all legitimate; mind the `NONE` footgun | | Post-traversal rank | `GROUP BY … ORDER BY …` | Cheaper than re-querying: rank the survivors, return top-K | 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](https://surrealdb.com/docs/surrealql/datamodel/idioms): the recursion syntax in full, `+collect` and `+path`, and the per-hop predicates - [`RELATE`](https://surrealdb.com/docs/surrealql/statements/relate): edge tables, and what `TYPE RELATION` gives you - [`DEFINE INDEX`](https://surrealdb.com/docs/surrealql/statements/define/indexes): entry-point indexes and the HNSW knobs (`EFC`, `M`, `M0`) - [`EXPLAIN`](https://surrealdb.com/docs/surrealql/statements/select#the-explain-clause): 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](https://surrealdb.com/cloud) - [Start building](https://surrealdb.com/docs) - [Join our Discord server](https://discord.gg/surrealdb)