Design a proximity service

There is no WHERE clause that makes this fast

The obvious query asks for businesses whose latitude and longitude both fall inside a box around the user. Put a normal index on each column and run it.

A B-tree index is one-dimensional. It answers “latitude between these two values” very quickly, and then holds a band stretching across the entire globe, which it must filter row by row on longitude. It can use one of the two indexes, not both. Two-dimensional proximity is not a query-tuning problem; it is a data structure problem. You need an index that maps two dimensions onto one.

Every option divides the map into smaller areas and indexes those, and they fall into two families. Hash-based ones (an even grid, geohash) compute a cell from the coordinates with a function. Tree-based ones (quadtree, Google S2, R-tree) recursively split space, adapting to where the data actually is.

Fold two dimensions into one string

The simplest hash is an even grid: chop the world into equal squares and store each business's square. It works until you remember the world is not evenly populated.

Geohash keeps the idea of cells but builds them recursively. Halve the world by longitude: that is the first bit. Halve the remaining half by latitude: the second bit. Keep alternating, then write the bits five at a time as base-32 characters.

Each character shrinks the cell by a factor of about 32, so a shared prefix bounds how far apart two places can be. That turns “near me” into a prefix match, an indexed string range scan that every database already does well. To search a radius, pick the shortest geohash whose cell still covers the circle: about 6 characters for half a kilometre, 5 for a kilometre, 4 for 2 to 5 km, and 3 for 20 km.

The nearest restaurant is 50 metres away and the index cannot see it

Prefix matching is fast, and it is not the same thing as proximity. Two places can be metres apart and share no prefix at all if a cell boundary runs between them.

The index knows about cells, not distance, so a business 20 metres away across a boundary has a different prefix and never appears. The standard fix is to query the user's cell and its eight neighbours, which geohash lets you compute directly from the code. One lookup becomes nine, still far cheaper than a scan.

Let the index follow the density instead of the map

A fixed grid gives Manhattan and the Pacific the same cell size, so query cost depends on where the user stands. A quadtree instead starts with one cell for the whole map and splits any cell holding too many businesses into four, recursively.

Dense areas end up as many small cells and empty ones as a few large cells, so every leaf holds about the same number of businesses and a city costs the same to query as a desert. The price is a structure that lives in memory and must be built (minutes for 200 million businesses) and carefully rebalanced, rather than computed from the coordinates.

Google's S2 takes a third route. It threads a Hilbert curve through the sphere, a single line that visits every cell, so points close on the ground stay close on the line. Because it can cover arbitrary regions at mixed resolutions, it is the specialist for geofencing.

With the index chosen, the rest is plumbing. The business table is the source of truth, sharded by business ID. The geospatial index table maps a geohash to business IDs, one row per pair so updates lock a single row; at around 2 GB it needs read replicas, not sharding. Cache hot cells and business objects, and deploy the read path per region, both to be close to users and to keep location data where privacy law says it must live.