Geospatial index
A geospatial index finds nearby points without a full scan. Checking all 2 million records for each of 500 queries/s is too slow. The index picks a small set of candidates, and then an exact distance check runs.
See it on the board
The same traffic runs on two boards. The simulator measured both when this page was built.
| Measure | Goal | Distance to every place | Cells pick the candidates |
|---|---|---|---|
| p99 latency | under 100 ms | 10.1 s Fail | 23 ms Pass |
| Monthly cost | 8 USD/mo | 8 USD/mo | |
| Error rate | 99.995% | 0% |
Key numbers
| Number | Value |
|---|---|
| Queries per second, one search part | 10,000 ops/s |
| Search query, median | 0.3 ms |
| Default shards | 1 shards |
Index · 4 pages read per query · disk writes per insert: 2
How it works
Find the 20 nearest places is a hard question for an ordinary index. A normal index sorts by one value, such as a name. Distance on a map depends on two values, latitude and longitude, and on the point of the query. There is no single sorted order of places that answers every nearby query.
Without a special index, the database computes the distance to every place. In the mini board there are 2 million places and 500 queries each second. That is one billion distance checks every second, and p99 passes the 100 ms limit.
A geospatial index cuts the map into cells, for example a grid or a tree of boxes. Each place sits in a cell. A query finds the cell of the point and its neighbors, and it takes only the places in those cells. A few hundred places are left instead of 2 million. An exact distance check ranks that small set, and the top 20 come back.
The index gives candidates, not the answer. The final check still uses CPU, so keep the candidate set small. More shards alone do not help: a text-only index cannot turn into a spatial one.
Places near the edge of a cell need the neighbor cells. Places near the poles or the date line need care.
In the levels you turn on the spatial index and check the query time.