How to design a proximity service

Answer “what is near me?”: take a point, radius, and filters, return the businesses inside that disc, ranked with exact distance. A cell scheme narrows 200 M points to a few hundred candidates; an exact distance test always has the final word.

The core problem

• Disc: the circular region within r metres of the query point. The request is a circle, not a rectangle.
• B-tree is one-dimensional (sorts by one value); a location is two numbers. Every geospatial index flattens 2-D to one sortable key while preserving locality (points near on the map get keys near in sort order).
• Four flattenings: geohash, quadtree, S2, H3. Split: geohash/S2/H3 are fixed, shardable, sortable cell schemes; a quadtree adapts to density but is a bespoke in-memory tree with no shard key.
• Constants: equator 40,000,000 m; 1° latitude = 111,111 m everywhere; 1° longitude shrinks by cos(latitude).

Sizing numbers

• Corpus: 200 M rows × 300 B ≈ 60 GB (180 GB / 3 replicas). Fits in RAM on one box, so no sharding.
• Density at a typical query point: 50 businesses/km² (not the 13.3/km² global mean). Skew Manhattan/Wyoming ≈ 3,904×, so no single fixed grid fits both.
• Candidates = area × density. Density is not load-bearing: it multiplies scanned and returned rows equally, so every amplification ratio is density-independent.
• Points are near-immutable (address changes ~once a decade), so the geo index is derived, rebuildable, ~99.99% static.

Architecture

• Two stores: businesses (source of truth, relational, only writer) and geo_index (derived inverted index, cell_id -> [business_id], in RAM, rebuildable in minutes).
• Update path one-way: edit row → CDC stream → recompute cell → swap index artifact. No durable write path, no agreement protocol, no conflict story.
• Every replica holds the whole 60 GB index, so a search never crosses a shard boundary and there is no fan-in tail. Scale reads by adding identical replicas.

Why a (lat, lng) B-tree fails

• Composite index sorts by lat, then lng only within one lat (leftmost-prefix rule): a range on the leading column unsorts everything after it, so it prunes on latitude only.
• 1 km search at 40.76°N scans ~27,700 rows for ~157 wanted = 176× amplification; the band circles the globe.
• Heap-fetch plan: 27,700 × 100 µs = 2.77 s (fatal). Covering index: ~0.66 ms but still 176× waste, and every added filter multiplies it.
• R-tree (nested bounding boxes, prunes both dimensions; PostGIS) and space-filling curves (geohash, S2, H3) are the two 2-D families.

Geohash

• Interleave lat/lng bits (longitude first), base32, 5 bits per character (the classic mistake).
• Two defects: cells scale with cos(latitude) (not equal area, degenerate at poles); adjacency breaks at every boundary, so always query the centre cell plus its 8 neighbours.
• 32× cliff: one character = 5 bits = five halvings, so dropping precision jumps cell area 2⁵ = 32×. A 2% radius increase can cost 32× the scan.
• Fix: stay at finer precision, query a (2k+1)×(2k+1) block, k = ceil(r / min(w,h)). Steps by 2 bits, not 32.

Quadtree, S2, H3

• Quadtree: splits a node into 4 when it exceeds a bucket; puts resolution where data is (~6 extra levels over Manhattan). But no shard key, splits under contention, bespoke in-memory server. Right only for static single-process data.
• S2: cube projection + Hilbert curve, integer id whose order is the curve order (prefix = containment). Bounded 2.08× area distortion. Keeps exact containment; square neighbours (corners 1.41× further).
• H3: hexagons, all 6 neighbours equidistant, ladder divides by 7. Cutting overfetch to ~2× at 1 km. Cells do not nest exactly (roll-ups leak).
• Trade: S2 = exact containment, awkward adjacency; H3 = uniform adjacency, inexact nesting.

H3 k-ring

• Filled k-ring holds 1 + 3k(k+1) cells: 7, 19, 37, 61 for k = 1..4.
• Ship k = ceil(r / (1.5a)) (1.5·k·a is the safe lower bound on inscribed radius). Never eyeball k: at res 9 a 1 km search needs k=4; k=3 covers only 998.5 m and silently drops a crescent.

The search path and gotchas

• Spatial work is ~34 µs (cell lookups + distance tests, each a ~100 ns memory ref). The cost is hydration: id → row is a ~0.5 ms cache call. Serial 335 candidates = 167 ms; one batched MGET = 0.5 ms.
• Use equirectangular distance, not haversine: dx = dlng×111,111×cos(lat), dy = dlat×111,111, d = sqrt(dx²+dy²). Compute cos(lat) once per query.
• Filter before ranking; exact distance is the last gate (else corner results up to √2·r away).
• Cache cell lists (cell_id key, shared), not query results (unique per user). Size with corpus-forced ~9.93 ids/cell, not the 50/km² query density.

Pragmatic picks

• Default to PostGIS for 200 M static points: ~8 GB index caches fully. Build S2/H3 only when the cell id is a join key across systems (surge, forecasts, zones), a data-platform reason, not latency.

Load-bearing assumptions

Change the set of boxes if false: points are static (else Nearby Friends), 60 GB fits in RAM (else partition + fan-out), answer must be exact (else geometry vanishes), radius varies (else precompute one lookup), a day of staleness is fine (else online mutation path).