18.3 How do "nearby within radius" queries work?

On the map: The store is in B4, near its bottom edge. A rider is 44 metres away, but just across the line in C4. If you only look in B4, you miss the closest rider of all. So you look in B4 and the eight squares around it, then measure.

In the system: The standard recipe:

1. Pick a cell size at least as big as the search radius. For a 2 km radius, 5-character geohash cells (about 4.8 km) work.
2. Find the query point's cell and its 8 neighbours.
3. Fetch every rider in those 9 cells. These are candidates.
4. Compute the real distance to each candidate and drop anyone outside the radius.
5. Sort by distance and return the nearest few.

Figure: cells only narrow the search; distance decides the answer.

The real distance on a sphere uses the haversine formula, which takes two (lat, lng) points and the Earth's radius (about 6,371 km) and returns the great-circle distance. Plain sqrt(dlat² + dlng²) in degrees is wrong because longitude degrees shrink away from the equator.

In the chapter's code, with 5,000 riders spread over about 30 km × 30 km: the 9 cells hold 1,140 candidates, of which 71 are really within 2 km. That's far less work than checking all 5,000, and the answer is identical to the brute-force check. The 9 cells cover about 209 km², while the 2 km circle is only about 12.6 km², which is why the distance filter matters.

Ways to tighten it:

• Use smaller cells and more of them, covering the circle more closely (S2's region coverer does this).
• For "the nearest 5 riders" instead of a fixed radius, start small and widen (more rings of cells) until you have enough.

In practice you rarely write this yourself: Redis (GEOSEARCH ... BYRADIUS), PostgreSQL with PostGIS (a spatial GiST index and ST_DWithin), Elasticsearch (geo_distance) and MongoDB (2dsphere indexes) all do it for you.

Memory code: "Search nine squares, then measure; never trust the border."

---