Proximity Service: geospatial indexes, geohashes and serving

Proximity Service: scope, scale and why a naive query fails ended on the question every spatial index answers: how do you map two dimensions onto one, so that an ordinary index can find neighbours? This lesson answers it, goes one level deeper on the recommended answer, and then serves it.

This is the deep dive and the one new idea this section owns: geospatial indexing for a static dataset. Four options, compared honestly, then a recommendation.

Geospatial indexing options

Option 1: an evenly divided grid

Divide the world into fixed squares — say 1 km on a side — and give each a cell identifier. Each place is stored with its cell. A search fetches the cells overlapping the query circle.

Good: trivial to implement, trivial to reason about, and a cell lookup is one indexed equality.

Bad: density. The world's land surface is roughly 150 million km², so 1 km cells give 150 million cells, and the overwhelming majority are empty ocean, desert, or farmland. Meanwhile one cell covering a dense city block might hold 10,000 places, so a single-cell query returns 10,000 rows and the index has bought nothing there. The structure is wrong at both extremes at once.

Option 2: geohash

Recursively halve the world — first by longitude, then by latitude, alternating — and record each choice as a bit. Encode the bits in base 32 to get a short string. Each additional character refines the cell.

Good: a cell is a string, so it works in any database with an ordinary index. A prefix match is a range scan: everything starting gcpvj lies in one cell. Precision is chosen by string length, so one column serves several radii.

Bad: cells are still fixed-size at a given precision, so density is handled by choosing a different precision rather than by the structure adapting. And there is a boundary problem, which the geohash deep dive below handles in detail.

Option 3: quadtree

Start with one cell covering the world. Whenever a cell holds more than a chosen number of places — say 100 — split it into four. Repeat. Dense areas end up deep, empty areas stay shallow.

Good: it adapts to density, which is the grid's fatal flaw. Every leaf holds a bounded number of places, so query cost is predictable everywhere.

Bad: it is an in-memory tree, not a database index. You build it at start-up and hold it in the process. For 200 million places at 100 per leaf that is about 2 million leaves and roughly 2.7 million nodes — a couple of gigabytes, and minutes to build. Updates mutate shared structure and need locking or copy-on-write. Every server holds its own copy and they must be rebuilt consistently.

Option 4: S2

Google's S2 library projects the sphere onto the six faces of a cube and orders cells along a Hilbert curve — a space-filling curve chosen because points close on the curve are usually close on the sphere. A cell becomes a 64-bit integer, and a region becomes a small set of integer ranges.

Good: integer range queries, well-defined hierarchy across 30 levels, good handling of region covering, and it is mathematically careful about the sphere in ways the flat schemes are not.

Bad: it is the least intuitive to explain on a whiteboard under time pressure, and its main advantages over geohash appear at large scale and in region-covering problems rather than in simple radius search.

The comparison

Recommendation: geohash. With 200 million places and a rarely-changing dataset, the deciding factor is operational simplicity — a geohash column with an ordinary index needs no bespoke in-memory structure, no rebuild coordination, and no custom replication. Handle density by choosing precision per radius and by capping results per cell. Mention S2 as the choice if region-covering queries or a very wide range of radii come into scope, and quadtree as the better fit if the workload were dominated by extreme density variation.

The geohash deep dive

The geohash recommendation needs one level more detail, because two things about geohashes are counter-intuitive and both are standard interview probes.

How the encoding works

Start with the whole world: latitude in [-90, 90], longitude in [-180, 180]. Alternate axes, starting with longitude:

1. Is the longitude in the upper or lower half of its range? Upper → bit 1, lower → bit 0. Narrow the range to that half.
2. Same for latitude.
3. Repeat, alternating.

The result is a bit string that describes an ever-smaller rectangle. Group the bits five at a time and encode each group in base 32 to get a readable string. Every character adds five bits of precision.

(Cell dimensions vary with latitude because longitude lines converge toward the poles; these are mid-latitude approximations.)

To search a 5 km radius, choose precision 5 or 6 depending on how much filtering you are willing to do afterwards.

Why a shared prefix means proximity

Two locations sharing the first n characters made the same first 5n binary choices, so they lie in the same rectangle at that precision. gcpvj and gcpvn are in the same ~5 km cell.

This is what makes geohashes so useful in an ordinary database: "find everything near here" becomes WHERE geohash LIKE 'gcpvj%', which is a range scan on a plain index, and range scans are what B-trees are excellent at.

The boundary problem

Here is the counter-intuitive part: a shared prefix implies proximity, but proximity does not imply a shared prefix.

Two points ten metres apart, on opposite sides of a cell boundary, can share no prefix at all. The extreme case is a point immediately east of the prime meridian and one immediately west: the first bit differs, so their geohashes differ in the first character. A user standing at that boundary querying by prefix would see nothing to the west of themselves.

This is not a rare edge case. Boundaries exist everywhere, at every precision, and a random query point has a meaningful chance of sitting near one — for a 5 km cell and a 1 km search radius, roughly a third of query circles cross at least one boundary.

The standard fix

Query the cell and its eight neighbours, then filter by true distance.

Geohash libraries provide neighbour calculation directly, because the arithmetic — incrementing a row or column in the interleaved bit encoding, with wrapping at the poles and the antimeridian — is fiddly enough that you should not write it under interview pressure. Name the function and move on.

So the real query is nine prefix lookups instead of one, unioned, then filtered:

1. Compute the query point's geohash at the chosen precision.
2. Compute its eight neighbours.
3. Fetch place identifiers from all nine cells — nine index range scans, each returning perhaps a few hundred rows.
4. Compute true distance for each candidate and discard those outside the radius.
5. Rank and return the top 20.

Step 4 is not optional. A cell is a rectangle and the query is a circle, so cell membership is an approximation. The cells are the retrieval step; exact distance is the filter step. Nine cells at a few hundred rows each is a few thousand distance computations — microseconds, against the 111,000-row scan that Why a naive query fails rejected.

Serving and follow-ups

The index is decided. What remains is deployment, caching, and the questions that follow.

Replicate, do not shard

Requirements and scale established that the geospatial index is about 5 GB. That changes the serving design completely.

Run N identical read replicas, each holding the whole index in memory, behind a load balancer. Any replica answers any query. Capacity scales linearly with replica count; losing a replica costs capacity, not coverage; and there is no shard map, no cross-shard query, and no rebalancing.

At 20,000 peak queries per second, if one replica comfortably serves 2,000 per second, that is 10 replicas plus headroom. Compare with sharding by region, which introduces a routing layer, makes queries near a shard boundary span two shards, and creates hot shards over dense regions.

Say this explicitly in the interview, because the reflex to shard is strong and resisting it with a number is a stronger answer: shard for capacity, not for habit.

Caching by cell

The natural cache key is the cell, not the query.

geo:6:gcpvj0 → [place_id, place_id, ...]

Two properties make this work well. Cell contents change only when a place is added or removed — 10,000 times a day across 200 million places — so entries are valid for hours. And queries concentrate: a small number of cells covering dense urban areas serve a large share of all traffic, so a modest cache achieves a high hit rate.

With a nine-cell query, a cache hit on all nine returns the candidate set with no database contact at all. Invalidate a cell on place update, and set a time-to-live of an hour as a backstop against missed invalidations.

Cache the place details separately, keyed by identifier — a different lifetime, a different change pattern, and shared across every query that returns that place.

Keeping business data separate

The geospatial index answers "which identifiers are near here". A second lookup fetches names, hours, ratings, and photos. Two reasons to keep them apart:

1. Different change rates. Coordinates almost never change; opening hours, ratings, and temporary closures change constantly. Mixing them means invalidating the geo cache for a rating update.
2. Different scaling. The geo index is 5 GB and replicated; the details store is 400 GB and partitioned. Forcing one storage decision on both is worse for each.

Ranking beyond distance

Split retrieval from ranking, as every search system does:

1. Retrieve — nine cells, distance filter, producing perhaps 200 candidates.
2. Rank — score each candidate on distance, rating, review count, open-now status, and any business rules, then take the top 20.

Ranking on 200 candidates in the application tier is cheap and lets the scoring function change without touching the index. Pushing ranking into the database ties the ranking logic to the storage layer, which is exactly the coupling you regret in six months.

One honest note: "nearest" is straight-line distance, and users often mean travel time. Converting one to the other requires routing, which is Section 20 (Google Maps).

Follow-ups worth preparing

• Very dense cells. A cell in a city centre with 10,000 places: cap results per cell, or index dense regions at a finer precision and record which precision applies per region.
• Adding a place. One row in the index and one in the details store, plus a cell invalidation. At 10,000 a day this needs no special machinery — which is the whole point of the read/write asymmetry from Requirements and scale.
• Filtered search (only Italian restaurants, only open now). Retrieve by cell, then filter — or maintain a per-category index, which multiplies index size by the number of categories.
• Moving to travel-time ranking, which is Section 20 (Google Maps), and moving to moving points, which is Section 19 (Nearby Friends) and requires a different architecture entirely.