Design nearby places

"Coffee near me" sounds like a simple filter, but a database index sorts things in one dimension and the map has two. The whole design turns on one idea: turn 2-D positions into 1-D keys (cells) that an ordinary index can range-scan, and choose cells that stay small where places are dense and large where they're sparse. It follows the interview framework phase by phase.

1. The prompt

"Design Yelp, or 'nearby places': users search for businesses near a location, optionally filtered by category and rating, sorted by distance or relevance. Owners add and update listings."

Unlike ride hailing (D13), places barely move: the data changes slowly and is read constantly. The interview is about the spatial index and about serving 50,000 searches a second from something small enough to copy everywhere.

2. Frame the problem

3. What it must do

1. A user can search for places within a radius of a point, with filters.
2. A user can view a place's details and reviews.
3. Owners can add or edit places; changes appear within minutes.

Not now:

• Routing: a separate system.
• Moving objects: that's D13.
• Review moderation.

4. How well it must do it

5. Numbers that change the design

6. The nouns

• Place.
• Geo index entry: a cell key and a place.
• Review.
• Owner.

places     place_id, name, lat, lng, category, rating, hours, owner_id, updated_at   (source of truth, sharded by place_id)
geo index  cell_key (geohash / quadtree leaf / S2 cell) → [place_id, lat, lng, category, rating]
reviews    (place_id, review_id) → author, stars, text

7. The contract

GET  /v1/search?lat=…&lng=…&radius=2000&category=coffee&cursor=…   → {places: [...], next_cursor}
GET  /v1/places/{id}       → details
POST /v1/places            → create   ·   PATCH /v1/places/{id} → edit (owner from the session)

Data flow: (1) owners write to the places database → (2) a change stream (or a rebuild every few minutes) updates the geo index replicas → (3) a search finds cells overlapping the circle → (4) exact distance check, filter, rank → (5) hydrate details.

8. First working version

A places table with lat/lng columns and indexes, and a search service that queries it.

8.1 Searching

Query a bounding box around the point on the indexed columns, then compute exact distances and sort.

8.2 Viewing a place

Read the place and its first page of reviews by id.

8.3 Editing

Owners update their row; the next search sees it.

9. Make it hold up

9.1 Why a normal index isn't enough, and what is fast

WHERE lat BETWEEN a AND b AND lng BETWEEN c AND d with an index on lat finds every place in a thin band of latitude around the whole planet, then filters by longitude. A composite index on (lat, lng) has the same problem: it is sorted by latitude first. You need a key where nearby on the map means nearby in the index.

9.2 Edges: searching neighbours too correct distances

Two cafés across the street can be in different cells with different geohash prefixes. A query must cover every cell that overlaps the search circle (typically the centre cell and its 8 neighbours at a suitable precision), then compute real distances to filter and sort. The cells are a coarse filter; the distance check gives the exact answer.

9.3 Where the index lives read-heavy scale

• Simplest good answer: PostgreSQL with PostGIS (or Elasticsearch or OpenSearch with a geo field), with read replicas. Category and rating filters combine naturally with the geo filter, and search engines add text relevance.
• Custom in-memory service: because the index is only a few GB, each search server can hold a full copy (a quadtree or sorted cell keys) built from the database and refreshed every few minutes from a change stream. Reads never touch the database until the details lookup.
• Sharding: sharding the geo index by region makes hot cities hot shards; with an index this small, replication beats sharding. Shard the place-details store by place id.

9.4 Dense cities and empty countryside fast

A fixed grid is a bad fit for both: in Manhattan one cell holds thousands of places and every query examines most of them; in the countryside a 2 km search needs dozens of empty cells. A quadtree splits a cell only when it holds more than, say, 100 places, so cell size follows density. With S2 or H3, choose the cell level from the radius: small radius, fine cells; large radius, coarse cells.

9.5 Filtering, ranking and caching fast · read-heavy scale

Filter first by geo and category, then rank the candidate set (distance, rating, open now, personalisation) and paginate with a cursor. Round the query point to a cell and cache results per (cell, radius, category) for popular areas; city centres repeat constantly. Place details come from a cache keyed by place id.

9.6 Keeping the index fresh available

Edits go to the places database, the source of truth. A change stream (change data capture) feeds index updates to every replica within minutes; alternatively, rebuild the whole index every few minutes and swap it atomically. Either way, searches never wait on writes.

9.7 The whole design after the deep dives

A search, and a new café appearing, through the final design.

10. Interviewer follow-ups

Variation: searching places to stay by date

"Design the search for a holiday-rental site, like Airbnb" adds dates and guests to the map search. A listing matches only if it's in the area, fits the group, and is free every night of the stay, and the price depends on those nights.

• Availability as a calendar per listing. One bit per night for the next year is 46 bytes a listing; 10 million listings fit in under half a gigabyte, so the whole calendar can sit in memory next to the search.
• Search in stages. The location index finds candidates in the map area; the calendar check removes listings that aren't free; pricing totals the stay; then rank and page. Each stage shrinks the list for the next.
• Search may be slightly stale. A booking updates the calendar within seconds, so a listing booked a moment ago can still appear. The booking step re-checks (Design D15), and the page says the dates just went.
• Cache the stable part. Dates multiply the possible queries, so caching whole results rarely hits. Cache the area's candidate list instead, and run the calendar and price stages on every search.

11. When things break

12. Wrap-up and the clock

Trade-offs we made:

• Cells that turn 2-D into 1-D keys.
• Adaptive cells (quadtree or S2/H3 levels) over a fixed grid.
• A small index replicated everywhere instead of sharded.
• Minutes of freshness via change streams.
• Caching per cell.

What we'd watch:

• Search p99.
• Places examined per result.
• Index age.
• Cache hit rate per cell.
• Replica load.

At 10×:

• More replicas.
• Edge caching.
• Per-region indexes if data outgrows memory.

Common mistakes:

• Two-column range queries.
• Forgetting neighbour cells.
• One cell size for everywhere.
• Sharding a small index by region.
• Skipping the exact distance check.

13. Try it, check yourself, read more

400 places: most in a dense downtown, the rest spread out. Tap the map to move the search circle. Orange cells are the ones the index must read; orange points are examined but outside the circle; teal points are the answers.