Geospatial / proximity lookup

The most common wrong answer is WHERE lat BETWEEN ? AND ? AND lng BETWEEN ? AND ?, and understanding exactly why it fails is what separates a real answer.

A B-tree on lat can efficiently return every row inside a latitude band; a B-tree on lng can return every row inside a longitude band. But these are two independent one-dimensional lookups. The query planner fetches one band and the other and intersects them — and the intersection of "everyone at this latitude" with "everyone at this longitude" is a candidate set proportional to the bands, not to the answer. In a dense city, a latitude band alone can contain hundreds of thousands of points stretching east-west across the whole map; you pay to fetch and intersect all of them to find the few actually near your point.

A true spatial index is inherently two-dimensional: an R-tree partitions the plane into nested bounding boxes so a query descends only into boxes that overlap the search region; a grid index (geohash/S2/H3) maps the 2-D point to a single locality-preserving cell id so nearby points share a key prefix. Either way the work is proportional to the number of points near the query, not to a band across the entire dataset. That's the whole game: collapse two dimensions into one index that preserves locality.

Every grid-based index — geohash, S2, H3 — has the same Achilles' heel: two points can be metres apart yet fall in different cells, so a single-cell lookup silently misses near neighbours sitting just across an edge.

The fix is universal and you should state it unprompted: query the target cell plus its ring of neighbours, then filter by the true distance. For geohash that's the 8 adjacent cells; for H3 it's kRing(cell, k); for S2 it's the neighbouring cells at your level. After gathering candidates from all those cells, compute the actual Haversine (great-circle) distance and drop anything beyond R.

For nearest-K the logic generalises to a ring-expansion: start at the target cell, expand outward ring by ring, maintaining a running top-K heap, and stop only when the nearest possible point in any unsearched ring is farther than your current K-th result. For a large radius you may need to query many rings — at which point a coarser resolution (bigger cells, fewer of them) is the better trade. This is precisely why resolution selection matters: it sets how many cells a given radius touches.

A production location system has two very different jobs: remember where everything is (durable, analytical, recoverable) and answer "who's near me right now" in under a millisecond (hot, volatile, high-write). Trying to do both in one store is the architectural mistake.

So you layer them. PostGIS (or any durable spatial store) is the truth: every driver ping is persisted for recovery, billing, trip history, and analytics. Redis GEO is the hot tier: a derived, in-memory index that serves the dispatch loop and can be thrown away and rebuilt from truth at any time. Dispatch reads Redis; if Redis is unavailable, it falls back to PostGIS at higher latency rather than failing — graceful degradation, not an outage.

The discipline that makes this safe: the hot tier must be reconstructible from truth, writes go to truth first (or at least durably), and stale entries age out via TTL/last_seen so a crashed client's last position doesn't haunt dispatch forever. The same two-tier shape recurs everywhere in this curriculum — a durable system of record behind a fast derived view — and naming it explicitly signals senior thinking.

Geospatial load is brutally non-uniform. A stadium at closing time, an airport arrivals curb, or a downtown core at rush hour concentrates thousands of drivers and riders into a handful of cells. Your average global QPS looks fine while one cell is melting.

The mitigations stack:

• Shard by region so a busy metro is isolated from quiet ones and can scale independently.
• Split hot cells to a finer resolution dynamically, so the load of one dense area spreads across more partitions instead of one.
• Cache popular viewport queries (the map everyone is staring at) with a short TTL, since many users request the same area simultaneously.
• Track per-cell query and update rates, not just global averages — the metric that reveals the hot spot is the per-partition one.

There's also a demand-side angle: those same dense cells are where surge pricing and supply-positioning algorithms run, because the uniform cell grid is a natural substrate for aggregating supply and demand. So the cell index isn't only a lookup structure — at scale it's also the coordinate system for the marketplace's balancing logic.

Moving objects make location data perishable. A driver's position from 40 seconds ago is worse than useless for dispatch — it can send a rider to where the car was. So freshness is a first-class design concern, not an afterthought.

Every stored position carries a `last_seen` timestamp (and often a TTL so it auto-expires). Dispatch filters out anyone whose last_seen is older than a threshold (say, 10 seconds) so it only ever offers genuinely-present drivers. The tension is the heartbeat cadence: pinging every second gives near-perfect accuracy but drains battery and floods the write path with millions of GEOADDs; pinging every 30 seconds is cheap but lets dispatch act on stale data. Production systems tune this adaptively — faster heartbeats when a driver is on a trip or near a likely match, slower when idle in a quiet area.

This also shapes the write architecture: at millions of moving objects, the location-update stream is a high-throughput firehose in its own right. It's common to ingest pings through a queue or stream (so a burst doesn't overwhelm the store), debounce/aggregate them, and only materialise the latest position into the hot tier — turning a write-heavy firehose into a manageable "latest known position per object" view.

"Find drivers within 2 km" is only the first stage of a real matching system, and strong candidates make the distinction explicit: the spatial index provides recall, but the actual decision adds filtering and ranking.

1. 1Spatial recall. GEOSEARCH (or ST_DWithin/kRing) returns every driver inside the radius — a cheap, index-backed candidate set, typically over-fetched a little so the next stages have room to filter.
2. 2Business filter. Drop anyone who isn't available, doesn't match the requested vehicle type, is stale (old last_seen), or is already on a trip. This is a yes/no pass that doesn't care about ranking.
3. 3Rank. Score the survivors by what actually matters — usually ETA (which accounts for road network and traffic, not just straight-line distance), plus driver rating, acceptance likelihood, and marketplace fairness — and offer the trip to the best one.

The crucial insight is that geometric distance is a proxy, not the objective: a driver 1.5 km away across a river with no nearby bridge has a worse ETA than one 2 km away on a direct road. So the spatial index deliberately returns a generous candidate set, and the ranking stage applies the expensive, road-aware ETA model to just those candidates — the same cheap-recall-then-expensive-rank shape you see in search. Keeping these stages separate keeps the hot spatial query fast while letting the matching logic be as smart as it needs to be.

Uber built and open-sourced H3, a hierarchical hexagonal geospatial index, because the obvious alternatives didn't fit a planet-scale, real-time marketplace. Latitude/longitude with range queries doesn't scale; square grids (and geohash) have the awkward property that a cell's edge neighbours and corner neighbours are at different distances, which complicates "expanding ring" searches and smoothing.

Hexagons solve this: every one of a hexagon's six neighbours is equidistant from the centre, so ring-based neighbour expansion (kRing) and spatial smoothing are uniform. H3 is hierarchical — each cell subdivides into finer children — so Uber can pick a resolution per task: coarse cells for city-level supply/demand analytics, fine cells for precise dispatch.

Critically, H3 is more than a lookup structure for Uber — it's the coordinate system for the entire marketplace. Supply and demand are bucketed into cells to compute surge pricing, position idle drivers toward predicted demand, and visualise the network. Because cells are uniform and store-agnostic (a cell id is just an integer key), the same index sharded across a distributed store serves both the sub-second dispatch query and the batch analytics that balance the market.

The lesson for an interview: at planet scale the spatial index isn't a detail bolted onto a database — it's the foundational coordinate system, and the choice of cell shape and resolution has consequences far beyond "find nearby."

Google's S2 library underpins geospatial features across Google Maps, and its core idea is elegant: project the sphere onto the six faces of a cube, then recursively subdivide each face into a quadtree of cells, numbering them along a Hilbert space-filling curve. The Hilbert curve is the trick — it maps 2-D cells to 1-D 64-bit integer ids such that cells close in space stay close in id, so a spatial range becomes a small number of contiguous integer ranges.

That property is what makes S2 so practical: because each cell is a single sortable integer that preserves locality, you can index points in an ordinary B-tree or any key-value store and answer "points near here" as a handful of integer range scans — no specialised spatial datastore required. S2 cells are hierarchical (30 levels, from the whole face down to roughly a square centimetre) so you choose resolution by use case, and the library provides the neighbour, covering, and containment operations a region query needs.

S2 covers an arbitrary region (a circle, a polygon) by computing the minimal set of cells that tile it, then querying those cell-id ranges — the covering plus a true-distance filter. The takeaway parallels H3: reduce 2-D proximity to 1-D locality-preserving keys so commodity stores can serve spatial queries, and let resolution be a tunable dial.

Tinder's core query is intensely geospatial: show a user a stack of nearby, eligible profiles, fast, at enormous scale. Their engineering team described moving to geosharding — partitioning the recommendation index by geographic region rather than by a random user-id hash.

The motivation is locality of access: a user in a given city overwhelmingly needs candidates from that same region, so co-locating each region's profiles on the same shard means a recommendation query hits one (or a few adjacent) shards instead of fanning out across the whole fleet. They map regions using a geohash/S2-style cell scheme and assign cells to shards, balancing shard sizes against population density — a dense metropolitan cell may be its own shard while a sparse rural area groups many cells together. This is the exact density-aware sharding this pattern describes: uniform cells, non-uniform population, so shard boundaries follow demand, not geometry.

Boundary handling matters here too — a user near a region edge must draw candidates from neighbouring shards — which is the cell-neighbour problem one level up at the shard granularity. The payoff was dramatically reduced query fan-out and latency: most recommendation requests became local to a shard.