Road routing and network traversal
A graph_edge field with a numeric cost field turns an index of edge documents into a routing engine. It answers the question a radius cannot: what is within ten minutes' drive, where geo_distance can only say "within five kilometres". The difference is a river, a motorway junction, a one-way system — things that make two points a kilometre apart a twenty-minute drive.
It was built for road networks, but nothing in it is specific to roads.
The shape of it
An edge is a document. There is no separate graph store to keep in step with the index. You index roads the way you index anything else, and the adjacency is derived from the segments Lucene already wrote — so a deleted document is a closed road, immediately, with no rebuild.
Node identity is borrowed from your data. A node is whatever long you say it is: an OSM node id, a customer id, an H3 cell. The index mints no identifiers, so the ids in your queries and results are the ones you already have.
Derived structures live outside the index. Adjacency and routing hierarchies are written to a scratch directory belonging to the shard rather than into the Lucene commit, and read back memory-mapped rather than held on the heap. Snapshots therefore contain exactly what Lucene wrote, replicas derive their own copies, and a continental network can coexist with everything else the node is doing.
Mapping
PUT /roads
{
"settings": { "number_of_shards": 1 },
"mappings": {
"properties": {
"road": { "type": "graph_edge" },
"seconds": { "type": "long" }
}
}
}
One shard, enforced
A graph_edge field cannot be created on a multi-shard index; the mapping is refused. A traversal sees only the segments one shard holds, so a network split across shards would return a route that stops at the shard boundary and report it as though the road ended there.
This is less restrictive than it sounds. A network costs about 5.5 bytes per edge, so a continental road network is roughly 0.7 GB — comfortably one shard. And the data you search need not live with it; see Querying a different index.
The cost field
Must be an integral type (long, integer, short, byte) with doc values.
A float or double cost is rejected rather than accepted. Its doc values are an encoded bit pattern that reads back as a perfectly valid long and an absurd travel time — a wrong answer with no error anywhere to show for it.
Indexing edges
One edge per document, with source and target. A two-way street is two documents, which is the point: the two directions usually have different costs.
POST /roads/_bulk
{ "index": { "_id": "main-st.eastbound" } }
{ "road": { "source": 1, "target": 2 }, "seconds": 60 }
{ "index": { "_id": "main-st.westbound" } }
{ "road": { "source": 2, "target": 1 }, "seconds": 75 }
Build the routing accelerator
Do this after loading a network, before anybody queries it.
POST /roads/_graph/build?field=road&weight_field=seconds
{
"_shards": { "total": 2, "successful": 2, "failed": 0 },
"built": 2, "already_built": 0,
"nodes": 1048576, "edge_documents": 4194304, "graph_edges": 2097152,
"hierarchy_edges": 5242880, "fill_in": 2.5,
"took": "2.4m", "took_in_millis": 144218
}
Why this is not optional
Routing needs a contraction hierarchy, and building one is work proportional to the whole network rather than to the question asked. Without this call it happens inside whichever search routes first — on a search thread, holding a lock every other routing request queues behind. At a million junctions that is minutes of a small, fixed, shared pool: not a slow query, but every unrelated query on the node waiting behind a graph contraction.
So a search declines to contract more than index.graph.routing.max_inline_build_edges (default 200000) for itself, and points you here instead:
the routing index for [road] weighted by [seconds] has not been built, and this network
has 4194304 edges, which is more than [index.graph.routing.max_inline_build_edges] allows
a search request to contract for itself (200000). Build it first with
POST /roads/_graph/build, or raise that setting to accept a slow first query.
Small networks are unaffected — under the ceiling they still build inline with no ceremony.
Things worth knowing
- Idempotent. Called against a network already contracted, it reports
already_builtand does nothing — so it belongs at the end of a load script without a check first. - It reaches every shard copy, not just the primary. Derived structures are per node and a search may be served by any copy; warming only the primary would leave a replica to contract on its own request thread the first time the round-robin reached it — the same failure in its most confusing form, intermittent and dependent on which copy answered.
- Two edge counts, deliberately.
edge_documentsis what you indexed, one per direction of travel.graph_edgesis what was contracted: the hierarchy is built over the undirected shape, carrying the two directions as separate weights on one edge. Comparing the wrong one against your document count suggests half your roads went missing. fill_inpredicts query speed. Contraction adds edges; road networks settle around 2–3×. Far above that means the topology is not what this accelerator suits — better learned here than from query latency.
When to rebuild
| What changed | What it costs |
|---|---|
| A road's travel time | A customization: seconds, automatic |
| A road closed (document deleted) | A customization: seconds, automatic |
| Many new roads added | A contraction: call _graph/build again |
Route between two nodes
GET /roads/_route?field=road&weight_field=seconds&from=1&to=4
{ "found": true, "cost": 120, "hops": 2, "route": [1, 2, 4] }
GET and POST are both accepted — a route is a read, and some clients cannot send a body on a GET, so the four parameters may be given in the query string or in a body:
POST /roads/_route
{ "field": "road", "weight_field": "seconds", "from": 12345, "to": 67890 }
| Parameter | Type | Required/Optional | Description |
|---|---|---|---|
field | String | Required | The graph_edge field describing the network. |
weight_field | String | Required | The integral field carrying each edge's cost. |
from | Long | Required | The node to start from. |
to | Long | Required | The node to reach. |
"found": false is an ordinary answer, not an error — two junctions can genuinely be unreachable.
road_distance
Matches documents reachable within a cost budget, scoring by nearness — so sorting by score sorts by road distance.
GET /places/_search
{
"query": {
"road_distance": {
"field": "road",
"weight_field": "seconds",
"source": 1,
"max": 600,
"node_field": "junction",
"graph_index": "roads"
}
}
}
| Parameter | Type | Required/Optional | Description |
|---|---|---|---|
field | String | Required | The graph_edge field describing the network. |
weight_field | String | Required | The integral field carrying each edge's cost. |
source | Long | Required | The node to measure from. |
max | Long | Required | The cost budget, in the units of weight_field. |
node_field | String | Optional | The field on the searched documents holding a node id. Omit to match the edge documents themselves. |
graph_index | String | Optional | The index holding the network, when it is not the index being searched. |
What it matches
By default, the edge documents leaving each reachable node — so the result carries the roads and everything indexed on them.
Given node_field, it instead matches any document whose numeric field holds a reachable node id. That is how a restaurant, a charging point or a depot joins the network: it records the junction it sits on.
Nearest-few is the same query
Score is nearness, so sorting by score sorts by road distance and size decides how many come back. There is no separate nearest-neighbour query because there is no separate computation — one sweep produces every distance, and a budget wide enough not to bite leaves the ranking to do the work.
Querying a different index
graph_index is what removes the single-shard restriction from your data. The network is asked once, during rewrite, on the one shard that holds it; what reaches the searched index is a set of node ids it filters locally, knowing nothing about graphs.
So places can have five shards or fifty. Its shard count is about how many places there are, which is what it should be about.
Traverse without costs
graph_traversal walks the same field ignoring weights, matching the edge documents reachable from a source:
GET /roads/_search
{ "query": { "graph_traversal": { "field": "road", "source": 1, "hops": 3 } } }
Add node_field to match documents by their node, and graph_index to walk a graph held on another index. That combination is what powers concept vocabularies.
Use graph_traversal, not road_distance, for concept vocabularies. road_distance is backed by a contraction hierarchy, which is quadratic in node degree and therefore catastrophic on hub-and-spoke topology. A road junction has degree three; an upper-level concept has thousands of children. A 50,000-concept taxonomy will not finish contracting, while a 929,000-junction road network takes about 1.3 seconds.
Operating it
What it costs
GET /roads/_graph/stats
{
"graph": {
"disk": "184.2mb", "disk_in_bytes": 193138688,
"adjacency": { "segments_held": 7, "builds": 12, "hits": 3841 },
"routing": { "hierarchy_builds": 2, "customizations": 96 }
}
}
disk is the one nothing else reports. The derived files sit outside the shard's index directory by design, so they appear in neither index size nor segment stats — a directory that can rival the index itself, invisible until a disk fills.
hierarchy_builds against customizations is the pair worth watching. A build is the expensive half and a customization the cheap one, so builds climbing in step with customizations means the topology is churning and the split the design rests on is buying nothing.
Settings
| Setting | Default | Description |
|---|---|---|
index.graph.routing.max_inline_build_edges | 200000 | The largest network a search may contract on its own thread. Dynamic. Set to 0 to require an explicit build for every network. |
This ceiling is conservative on purpose, because build cost depends far more on the shape of a graph than its size. A square grid at exactly the default — 50k nodes, 200k edge documents — takes about 8.5 seconds of CPU. The Massachusetts road network, eleven times larger at 929k junctions and 2.2M edge documents, takes about 1.7 seconds. A road network contracts to roughly twice its original edges; a uniform grid does not. If you know your data is road-shaped, raise it.
Memory
Builds are accounted against the request circuit breaker, so a network too large for the heap fails that request rather than the node. The resident structures are memory-mapped and cost essentially no heap; it is the transient build arrays — tens of bytes per edge — that the breaker is protecting you from.
Cancelling a build
A build is a cancellable task, so one started by mistake on a very large network can be taken back:
GET /_tasks?actions=*graph/build*&detailed
POST /_tasks/<node_id>:<task_id>/_cancel
Cancellation is cooperative: the contraction asks, at points of its own choosing, whether it is still wanted, and abandons within milliseconds. It is deliberately not done by interrupting the thread — a build spends much of its time reading the index, and interrupting a thread inside an NIO read closes the channel underneath it for every other user of that file.
Cancelling reaches the data nodes, not just the coordinator, so the work genuinely stops rather than the call merely returning. A cancelled build leaves nothing behind; the next call starts fresh.
Measured on real road networks
Two Geofabrik extracts, converted to edge documents and built with the default ordering, on an idle machine:
| Massachusetts | Switzerland | |
|---|---|---|
| Junctions | 928,732 | 1,202,480 |
| Edge documents | 2,196,112 | 2,563,726 |
| Average degree | 2.40 | 2.21 |
| Contract | 0.87 s | 1.00 s |
| Customize | 0.47 s | 0.67 s |
| Fill-in | 2.08× | 1.83× |
| Distance query, p50 / p99 | 365 µs / 652 µs | 276 µs / 518 µs |
| Full route with path, p50 / p99 | 564 µs / 1,358 µs | 505 µs / 1,093 µs |
Both verified against Dijkstra over the full directed graph on random reachable pairs.
Two things to take from this. A million-junction network builds in under two seconds, so _graph/build is not the ceremony it might look like — it exists because build cost scales with the network rather than the query, not because it is always slow. And query latency is sub-millisecond, which is what makes road distance usable as a filter inside an ordinary search rather than a separate service.
Measure on a quiet machine if you repeat this. The same benchmark under a concurrent build reported a p999 of 105 ms against a true 1.4 ms — that tail is almost entirely the scheduler, not the algorithm.
Scale is validated on synthetic grids rather than a full continental extract. Grids are a pessimistic case for contraction — real road networks have better separator structure — so the measured build costs should be an upper bound. That is reasoning, not measurement.