Design proximity search

Why was walking faster than the app?

The delivery service now lists 6,000 kitchens in three cities: home cooks, and the partner kitchens that joined last spring. Customers no longer order from one kitchen. They open the app, tap Kitchens near me, and pick one.

At 12:20 one Monday a student taps it in his hostel room. The spinner turns. He knows a kitchen two lanes away, so he puts on his slippers, walks there and buys lunch at the door. When he gets back, the page has loaded.

The endpoint asks the database for every kitchen with today’s menu, all 6,000 of them, then works out each one’s distance in Python and sorts. When there were 300 kitchens in Pune, nobody noticed. At lunch that Monday it ran 22 times a second, and each run read 6,000 rows and about 12 MB. Multiply those before reading on: 22 searches a second times 12 MB is about 264 MB a second pulled out of the orders database, to show each customer twenty kitchens.

The list has a second fault. It shows two kitchens that closed for the day. One customer paid and waited forty minutes for food nobody was cooking.

When you look for a tea stall near the station, you do not walk past every stall in the city first. You look in the lanes around the station. A database index keeps its values in one sorted order, like points along a single line. Distance on a map depends on two directions at once, north to south and east to west. To search near a point without reading every kitchen in the city, the search needs a way to name the area around the customer: divide the map into cells, and give each cell a name the database can look up. A kitchen across the road can sit in a different cell, so the search also needs to know which neighbouring cells to read.

Pause and predict Kitchens are filed by map cell. The customer stands near the edge of his cell, and the kitchen he wants is across the road in the next one. Which cells must the search read?

What must never go wrong?

The System Context: customers and cooks, kitchen search as its own system, and the maps provider that turns addresses into points.

Two rows of the table come straight from the opening: a kitchen missing from the list loses a sale, and a closed kitchen in the list costs a refund and often the customer.

Core entities, in two minutes

A Kitchen (a point, a city), its status (open now or not), a Cell (a named square of the map) and a Search (a point and a radius, never stored). The API will be built around kitchens and their status.

The estimate that changes the design

The location data is tiny. 6,000 kitchens at about 32 bytes each (an id, two coordinates, a cell name) is 192 KB. Even an interview-scale directory of 200 million places is 6.4 GB: it fits in one machine’s memory. So this design needs no sharding. The data can live anywhere. The question is how to avoid reading all of it for each search.

Reads also far outnumber writes: 22 searches a second, against a few dozen status changes an hour and a handful of address changes a week. So the list of kitchens in one cell changes rarely, which makes it a good thing to cache.

The obvious version, and how it breaks

The first version reads every kitchen and sorts by distance in code.

The next idea is an index on latitude and an index on longitude, with WHERE lat BETWEEN … AND lon BETWEEN …. It helps less than it looks. Each index is one-dimensional: the latitude index returns a band across the whole map, 6 km tall and the full width of the city, and the database then filters that band by longitude (or intersects two large bands). A one-dimensional index cannot answer a two-dimensional question on its own.

Pause and predict Cut the map into cells of about 4.6 by 4.9 km, and read only the kitchens in the customer’s own cell. That is fast. Is it also right for a 3 km search?

Try it below on Pune’s 2,000 kitchens. Start with “Scan every kitchen”: it is always right, and it reads all 2,000 to find about 320 within 3 km. Then switch to “Own cell only” and press Customer next to a cell edge.

Reading only the customer’s own cell is fast, but it gives wrong answers. Next to a cell edge the customer is under 50 metres from kitchens on the other side of the line, and the search never looks there. In the simulator it misses 57 of 272 kitchens within 3 km. Each missed kitchen is a lost sale that nobody notices, because the customer never learns the kitchen was there.

A mental model

Geohash

A short string that names a rectangle of the earth. Each extra character divides the rectangle into 32 smaller ones, so a longer hash is a smaller cell inside the shorter one.

For example: Central Pune at 18.5195° N, 73.8553° E is tek92 with 5 characters (a cell about 4.6 km by 4.9 km) and tek92e with 6 (about 1.2 km by 0.6 km).

Interleaving the bits is what makes this work. Because longitude and latitude bits alternate, every prefix narrows both directions at once, and the strings sort so that a cell is one contiguous range. Any sorted index (a PostgreSQL B+tree from lesson 2.1, a Redis sorted set) can now answer “which kitchens are in this cell?” with one range scan.

The cost shows up at cell edges. Two points a few metres apart can sit in different cells with different prefixes, which is why a search reads the customer’s cell and its 8 neighbours. If every cell is at least as wide and as tall as the radius, those 9 cells must contain the whole circle.

Where should the map index live?

Redis already has geo search built in, which is an argument for writing the least code. The refunds for closed kitchens are an argument for keeping one source of truth about which kitchens are open.

Redis GEO is less code to write, and at a million searches a second it might win. Here it would become a second source of truth that must hold every kitchen’s point and status exactly, and a missing or stale entry silently hides a kitchen or shows a closed one. The geohash column keeps one source of truth and treats the cached copy as something that can be thrown away and rebuilt, at the price of owning a little geometry code.

What to remember

1. A sorted index is one-dimensional. A geohash turns two dimensions into one string whose prefixes are cells, so “near here” becomes a few range scans.
2. Nearby points can sit in different cells: always read the customer’s cell and its 8 neighbours, with cells at least as large as the radius.
3. The cells only give you candidates. The answer comes from the true distance, so filter the candidates after fetching them.
4. Precision is a trade between lookups and wasted candidates. Geohash moves in steps of 32; quadtrees adapt to density; H3 hexagons give equal neighbours.
5. Estimate first. Locations are small, so the hard part is the index and sharding can wait, and data that changes slowly caches well.

Always read the neighbouring cells too, because the nearest kitchen is often across a cell boundary.

In the real world

Real location search adds what our toy leaves out: road distance and travel time from a routing engine (the maps side quest), delivery zones drawn as polygons per kitchen, ranking that mixes distance with rating and price, and cell coverings computed by libraries such as S2, which pick cells of several sizes to fit a circle tightly. At planetary scale the index is still small enough to replicate to every region, which is part of why “near me” is one of the easier large systems to run.

The search now answers in a few milliseconds, and a kitchen that closes leaves the list within half a minute. The next problem moves: riders, whose points change every few seconds.