Why architecture matters here
Architecture matters here because the difference between designs is not a constant factor — it is a complexity class. A scan-and-compute query is linear in the corpus, so it degrades continuously as you grow and looks fine in staging with ten thousand rows. A cell-indexed query is roughly proportional to the points near you, which is bounded by geography rather than by how successful your product becomes.
The distribution is the second reason, and it is the one that gets skipped. Points of interest are not uniformly spread over the earth; they cluster into cities with brutal skew. Any design assuming even density is tuned for the ocean and will melt in Manhattan. A cell size that yields fifty candidates in a suburb yields fifty thousand downtown, and that single cell becomes both the latency tail and the hot shard.
Finally, this sits on the interactive path. Proximity search backs map panning, delivery dispatch, and ride matching — features where a hundred milliseconds is felt directly. That budget is what forces the two-stage structure: an index-only coarse filter that a B-tree can serve, followed by exact distance on a candidate set small enough that the trigonometry no longer matters.
The correctness stakes deserve their own mention, because they are unusually quiet. A proximity bug does not throw. It returns a list of restaurants that are genuinely nearby and genuinely real — it just silently omits the closest one because it sat across a cell boundary. Nothing in the response looks wrong, no error rate moves, no alert fires, and the user has no way to know what they did not see. Compare that to a crashed endpoint, which announces itself immediately. Wrong-but-plausible results are the hardest class of bug to detect from the outside, and this domain produces them by default, which is why an exact brute-force oracle in CI is not optional here the way it might be elsewhere.
The architecture: every piece explained
Geohash. Recursively bisect longitude and latitude, interleaving the bits — even bits for longitude, odd for latitude — and base32-encode the result. Each character adds five bits and refines the cell. The magic property is that a shared prefix implies spatial proximity, so 'nearby' becomes a string prefix match, which every B-tree and key-value store already does well. That is the whole trick: a range scan over a text index.
S2 and Hilbert curves. Geohash's curve is Z-order (Morton), which has a specific weakness: it jumps. Adjacent cells can be far apart on the curve, so the 1D index scatters points that are 2D neighbours. S2 projects the sphere onto six cube faces and orders cells along a Hilbert curve, which never jumps — consecutive curve positions are always adjacent cells. Better locality means fewer, tighter ranges per query, and working on a sphere avoids the pole and meridian distortion that plagues flat schemes.
Quadtrees. Where geohash and S2 impose a fixed grid, a quadtree splits adaptively: a node holding more than K points divides into four children, so dense regions get deep subdivision and empty ocean stays one shallow node. This directly attacks the density-skew problem, at the cost of a tree structure that is harder to shard and rebalance than an ordering key.
H3 and the shape of a cell. Uber's H3 makes a different trade by tiling with hexagons, and the reason is worth understanding because it is not aesthetic. A square cell has two kinds of neighbour — four across edges and four across corners — whose centre distances differ by about 41 percent, so 'adjacent' means two different things depending on direction. Hexagons have six neighbours all equidistant, which makes them markedly better for flow modelling, gradient work, and anything that aggregates over rings of neighbours. The cost is that hexagons cannot subdivide perfectly, so H3's hierarchy is approximate where geohash's is exact.
The seam problem. Every fixed grid has a fatal edge case, and it is the same one in all of them: a point just across a cell boundary is metres away and shares no prefix. Query only your own cell and you will confidently miss the closest restaurant because it is on the other side of an invisible line. This is not an edge case in the rare sense — for any query near a boundary, and most are, the true nearest neighbour is frequently in an adjacent cell.
Neighbour cells and refinement. The standard fix is to compute the query cell plus its eight neighbours and scan all nine, choosing a cell size at least as large as the search radius so nine cells provably cover it. That yields a candidate superset — every true match plus extras from the corners. Stage two computes exact haversine distance on that superset, filters to the real radius, and ranks. Coarse filter narrows with the index; refinement is exact but cheap because the set is small.
Why the superset direction is the only safe one. The asymmetry between the two stages is the load-bearing property of the whole design, and it is easy to miss. Stage one is allowed to return points that do not belong, because stage two computes exact distance and removes them. Stage one is never allowed to miss a point that does belong, because nothing downstream can recover it — stage two only ever filters. That is precisely why cells must be at least as large as the search radius and why all nine are scanned: not for speed, but so the coarse filter's error is provably one-directional. Any optimisation that shrinks the candidate set by making stage one cleverer risks converting a slow-but-correct query into a fast wrong answer, and that trade is almost never worth it.
End-to-end flow
Walk a query: find open restaurants within two kilometres, ranked by distance. At write time every restaurant was assigned a geohash at a precision whose cell is roughly five kilometres — comfortably larger than the query radius — and that string was indexed as an ordinary column.
The request arrives with a coordinate. The service computes the geohash of the query point at the matching precision, then derives the eight neighbouring cells arithmetically. Nine short strings — no database access yet.
Now the coarse filter: a single indexed query with nine prefix ranges. The B-tree walks nine contiguous ranges and returns perhaps twelve hundred candidates. Everything within two kilometres is guaranteed present because the cells cover the radius; the extras are corner points up to several kilometres out. Critically, no trigonometry has run.
Refinement follows. The service computes haversine distance for each of the twelve hundred candidates and discards those beyond two kilometres, leaving perhaps three hundred. Twelve hundred distance computations is microseconds of arithmetic on rows already in memory — the same function that was unusable across five million rows is free across twelve hundred.
Business filters apply next: open now, rating above four, cuisine match. Order matters and is easy to get wrong — filtering before the coarse geo stage discards the index's leverage, while filtering after is nearly free, because the predicates run over three hundred rows instead of five million. Sort by the distance already computed, take the top twenty, return.
Then the city centre breaks the assumptions. The same nine cells in downtown Manhattan return not twelve hundred candidates but ninety thousand, because the grid is fixed and density is not. Latency jumps from eight milliseconds to four hundred. The fixes are the real design work: use finer precision with more neighbour cells where density is high, switch to an adaptive structure, cap candidates with a radius that shrinks under load, or precompute results for hot cells and serve them from cache. This is where a textbook design meets an actual map.
Notice what the density fix does to the seam guarantee, because this is where the two halves of the design collide. Dropping to a finer precision downtown shrinks each cell below the two-kilometre radius, and the moment that happens, nine cells no longer cover the search area — the coarse filter starts missing real matches, silently, in exactly the market you care most about. Finer cells require proportionally more neighbours, which claws back some of the savings. The honest framing is that cell size is not a tuning knob you can turn freely; it is bound to the radius by a correctness constraint, and density skew has to be solved within that constraint rather than by ignoring it.