Design Nearby Places Search

The final over ends at 10:40 pm, and about thirty thousand fans pour out of Chinnaswamy Stadium onto MG Road, hungry. Within minutes, thousands of phones in a few city blocks ask the same app for food nearby. Two things can go wrong. The servers that hold this corner of Bengaluru take ten times their usual load while the rest of the country is quiet. And Priya, standing on MG Road, sees a list of cafés that leaves out the one across the street, 43 m away, because an invisible grid line runs between them. Both problems come from the same question: how does a system turn "near me" into something an index can search?

The product: the search behind "restaurants near me". A user shares their location, picks a category or types a word, and sees nearby places ranked by distance and rating, with filters such as open now. Owners add and edit their listings. Plan for about 200 million places worldwide and the dinner-time peak. One search runs through the chapter: Priya, on MG Road in Bengaluru, looking for cafés within 500 m.

Priya's search looks simple, but its core problem is unusual: an ordinary database index cannot answer "what is near this point" efficiently, because nearness depends on two numbers at once. Most of this chapter is about turning a two-dimensional position into something an index can search.

Here is what is in scope today, and what is not:

Reviews matter here only as the rating they feed into ranking. The non-functional requirements:

• Fast: results in under 200 ms at the 99th percentile, including the dinner-time peak.
• Complete near the user: a café 43 m away, like the one across the street from Priya, must never be missing because a cell border runs between them.
• Read-heavy: searches outnumber listing updates by hundreds to one.
• Fresh enough: an owner's new opening hours show up within a few minutes, not instantly.
• Global: about 200 million places, dense in cities and sparse everywhere else.

The stadium crowd is a local spike; size the global flows first. Assume 200 million places worldwide and 100 million searches a day. Two numbers matter most: the search rate, and the size of the index.

Searches outnumber edits by about 500 to 1, so the design optimises the read path and lets edits arrive in batches. Now the index. A geo index needs only what the search itself uses: the place id, its position, its cell, and a few fields to filter and rank on. Everything else stays in the database.

That number shapes the design: with a minimal index, every search server can hold a full copy of the world, and you add servers for throughput, not capacity. Real indexes carry more per place, such as names and keywords for text search, opening hours and ranking signals. At about 1 KB per place the index is 200 GB, which is usually split into shards by region.

With the flows sized, the calls are few. Priya's search is one read with a position and filters; the rest are ordinary reads and writes.

GET   /v1/places/search?lat=12.9755&lng=77.6072&radius=500&category=cafe&open_now=true&limit=20
      -> 200 { places: [{ id, name, lat, lng, distanceM, rating, reviewCount }], nextCursor }
GET   /v1/places/{placeId}                                -> 200 { name, address, hours, photos[] }
POST  /v1/places          { name, lat, lng, category, hours }  -> 202 { placeId, status: "in review" }
PATCH /v1/places/{placeId}       { hours, phone }              -> 202 (visible within minutes)
POST  /v1/places/{placeId}/reviews   { stars, text }           -> 201

Search returns only what the result list shows; the place page loads full details separately.

Changes to places return 202 Accepted because they are not visible at once. A new place may need checking before it appears, since fake listings are a real problem, and changes reach the search index in batches every minute or so, which the requirements allow.

The phone sends its exact position, but the server groups nearby positions for caching, as the caching deep dive explains. Two people standing 30 m apart should usually read the same cached lists.

Behind those calls, the places table is the source of truth. The geo index is a derived copy, rebuilt from it, that holds only what search needs.

One index entry holds only the fields a search touches:

rating_avg and rating_count are updated as reviews arrive, so ranking never reads the reviews themselves. status lets a place be hidden (closed, under review) without deleting it. Because the index is derived, losing it loses nothing: it can always be rebuilt from the table.

Put together, a search runs in three steps: work out which cells cover the search circle (named rectangles on a grid, explained in the first deep dive), ask the geo index shards that own those cells for candidates, then rank them and attach details for the top results. The scene follows Priya's search, and then the crowd behind her:

The search service does the thinking: it turns the circle into cells, merges answers, filters by exact distance and ranks. The shards answer one question only, which places are in these cells, and shard C is never asked. Cells that share a prefix sit together on one shard, so most searches touch one shard and only those near a shard boundary, like Priya's, touch two.

Why can't an ordinary index answer Priya's search? The obvious query is a box: latitude between two values and longitude between two others. With one index on lat and another on lng, the database can narrow the search well with only one of them. The lat index returns a thin strip that runs right round the planet at that latitude, and every row in the strip is then checked for longitude. Some databases can intersect the two indexes, but each one still reads a long strip across the planet.

-- Slow: two ranges on two columns; an ordinary index narrows only one
SELECT id FROM places
WHERE lat BETWEEN 12.9667 AND 12.9847 AND lng BETWEEN 77.5969 AND 77.6153;

-- Fast: one range on one indexed column
SELECT id, lat, lng FROM places WHERE geohash LIKE 'tdr1vf%';

A prefix match on a sorted column is a single range scan.

A geohash is that one key. It names each cell of a grid laid over the world with a short string, and every point inside a cell has a geohash that starts with the cell's name. Each extra character makes the cell smaller:

Priya's 500 m search will use length 6, as a later page works out. First, how the string is built.

A geohash halves the world again and again, alternating between longitude and latitude and starting with longitude: the east half is a 1 and the west half a 0, then the north half a 1 and the south half a 0. Every 5 bits become one character from a 32-character alphabet, 0123456789bcdefghjkmnpqrstuvwxyz: the digits and the letters except a, i, l and o. Here are the first five halvings for a café on MG Road, about 120 m west of Priya, at (12.9757, 77.6061):

The bits 11001 make 25, and character 25 of the alphabet, counting from 0, is t. Carry on for 35 bits and the café's geohash is tdr1vfp.

Each extra character splits a cell into 32 smaller ones, which is why a cell's name is a prefix of every geohash inside it: the café's cell is tdr1vf at length 6 and tdr1v at length 5. A café near Cubbon Park, about 1.4 km west, is tdr1vdm: the same 5-character prefix, a different 6th character.

Prefixes have one trap: two places can be very close and still share only a short prefix, or none at all, if a cell border runs between them.

The miss had nothing to do with distance. Prefixes follow the order of the halvings, so a border can split two close neighbours at a coarse level; the cure is to read the neighbours every time and let exact distance decide.

Here is Priya's cell with its eight neighbours at length 6:

In the east column, tdr1y4 sits right next to tdr1vf yet shares only tdr1, a cell about 39 km wide. Across the equator or the 0° line of longitude, neighbours share no characters at all, because their very first bits differ.

The standard fix: search the user's cell and its eight neighbours, then filter every candidate by its exact distance (the haversine formula gives the distance between two points on a sphere). Geohash libraries compute the eight neighbouring names for you, and in SQL the block is nine short prefix ranges on the same index.

Nine cells fix the border, but how big should each cell be? For the 3 × 3 block to cover the whole circle wherever the user stands in the centre cell, the cell's shorter side must be at least the radius: the block then reaches at least one full cell beyond the centre cell on every side. That rule picks the cell length for each radius:

Length 6 suits Priya's 500 m: its shorter side is about 610 m, so the block reaches at least 610 m beyond her cell on every side, about 110 m to spare. The spare also absorbs a GPS fix that is a few tens of metres off. A 650 m radius would break the rule and needs length 5, or every length-6 cell the circle touches.

The waste is the price: for 500 m you read about eight times the circle's area. In a dense market area with, say, 1,000 places per square kilometre, that is about 6,600 candidates to keep roughly 800. It works, but it is why dense areas want smaller cells: either search every small cell that touches the circle, or let the cells adapt to density, which leads to quadtrees.

Fixed cells waste work where places are crowded: the block around MG Road holds hundreds of cafés, a block in a village almost none. A quadtree starts with one box covering the whole map. Whenever a box holds more than a set number of places, say 100, it splits into four equal quarters, and those split again where needed. Busy city centres end up with tiny boxes and oceans stay as huge ones, so every leaf holds at most 100 places wherever it is. It is the same four-way split as the map tiles in the maps chapter, except that a box splits only where it is crowded.

Size check: 200 million places at up to 100 per leaf means at least 2 million leaves, plus about a third as many inner nodes. With the 40-byte entries from before, the whole tree is still about 8 to 10 GB. Each search server can build it in memory from the places table, rebuild it nightly, and apply changes in between.

A quadtree also answers "the nearest 20" naturally: it keeps widening until it has enough, with no radius to guess. So which structure should a design start with?

Both structures can answer Priya's search. They differ in where they live and how they cope with crowded cells:

Start with geohash cells, because they work in an ordinary database and shard by prefix. Move to a quadtree when crowded cells such as those around MG Road make fixed cells wasteful, or when "nearest k" becomes the main query. Either way, you add a service to build, rebuild and keep in sync, so the switch should be earned by measured waste.

The stadium crowd is the caching problem in one picture: thousands of searches, almost never from exactly the same point. So cache by cell, not by point. Store the candidate list for each cell and category, such as cand:tdr1vf:cafe, for a few minutes. Each search reads nine of these lists, then filters by exact distance and ranks for that user's position, which is cheap.

After the match, the same few dozen cells around MG Road are searched thousands of times a minute, so hit ratios are high. Place details need a cache of their own: at the peak, 5,000 searches a second × 20 results is 100,000 detail lookups a second, far more than the database should serve. Cache details by place id for longer, delete an entry when its place changes, and serve photos from a CDN.

Updating business data is a separate, slower path. Owners and editors write to the places table, after review for sensitive edits. Each change emits an event onto a queue; an index updater applies the events to the geo index in batches every minute, then deletes the affected cached lists and details. A full rebuild from the table runs nightly and repairs any update that was lost.

With the design in place, here is how it fails. Each failure has a planned answer, and each row names what the user sees as well as what the system does.

The derived index is what makes most of these survivable: any copy can be rebuilt from the places table. Three trade-offs run through the design:

• Bigger vs smaller cells: bigger cells mean fewer lookups but more candidates to filter; smaller cells the reverse.
• Fixed grid vs quadtree: the grid is simpler and lives in any database; the quadtree adapts to density but is a service you must build and run.
• Cache lifetime vs freshness: longer lifetimes give more hits, but if a deletion is missed, a 5-minute lifetime can show a stale result for up to 5 minutes, which the requirements allow.

Photos dominate the bill: if 30 million place pages a day each load about 1 MB of photos, the CDN moves about 30 TB a day, while the geo index fits in a few servers' memory.

Optional: how to rank the candidates once the cells have found them.

Distance alone ranks poorly: the nearest place may be a 2-star café. Rating alone is worse: it sends you across the city. Combine them into one score, for example:

closeness = 1 - distance / radius              (1 where you stand, 0 at the edge)
quality   = adjusted_rating / 5
score     = 0.5 × closeness + 0.5 × quality    (plus small boosts: open now, popular)

Example weights. The table below uses a search radius of 1 km.

Adjust ratings for review count. A 5.0 from 4 reviews is weak evidence; a 4.6 from 2,000 is strong. A common fix, a Bayesian average, pretends every place starts with some extra reviews at the site-wide average; with example values of 20 extra reviews at 3.8, adjusted = (20 × 3.8 + reviews × stars) ÷ (20 + reviews). A handful of perfect reviews barely moves the number, while thousands of reviews dominate it.

Without the adjustment, New Café B would rank first on its perfect 5.0 (a score of 0.85). With it, B counts as an ordinary 4-star place, and A wins by being closer. The weights, the 20 and the 3.8 are all examples: they are product decisions, tuned by watching which results people actually open.

Keyword searches such as "biryani" combine two indexes: a text index (see the distributed search chapter) finds places whose name, menu or tags match, and the cells limit them to the area. Run the more selective one first. For a common word, take the cells first and match the word within them; for a rare word, find its few matches first and then keep those within the radius.

A 45-minute slot leaves about 40 minutes of design once introductions and your own questions are done. Here is nearby places search on that clock.

Pick the deep dive from the interviewer's question. If they ask how the search finds nearby places at all, go deep on geohash prefixes and the border problem. If they push on dense city centres or "the nearest 20", move to quadtrees. If they ask about load or freshness, cover caching by cell and the edit pipeline.

Interviewers change the problem to see whether your design bends or breaks. Try each one before opening the answer.