Design nearby places search (Yelp)

Open a maps app in Bengaluru at 8 pm and type “biryani”. In a fraction of a second you see twenty places within a couple of kilometres — open now, around ₹400 for two, rated four stars or better — with the close-and-good ones on top. That is nearby places search, the heart of Yelp and of every “near me” result. With ten thousand rows it is one SQL query. It becomes a design problem because “near” is two-dimensional while ordinary indexes are one-dimensional; because one query must mix text, filters, distance and quality in under 200 ms; because Connaught Place has thousands of shops within a kilometre while a village in western Rajasthan has three within twenty; and because a 5.0 with two reviews must not outrank a 4.6 with three thousand. You will design it for about 200 million places worldwide.

Understand the problem

Nearby search is a read-heavy search problem with a spatial twist. Name its shape early: a small write path that must be correct (places and reviews), and a huge read path (search) that may be a little stale. Most of the design follows from agreeing how stale.

Functional requirements

1. Users should be able to search for places near a point or inside the visible map, by keyword or category (“biryani”, “ATM”, “dentist”), with filters for open now, price level and minimum rating, ranked by a mix of distance and quality.
2. Users should be able to open a place and see its details — address, hours, photos — and its reviews.
3. Users should be able to write a review with a 1–5 star rating and some text, and see the place’s rating reflect it soon after.
4. Business owners should be able to add a place or update theirs — hours, price, photos, categories — and see the change in search within minutes, not seconds.

Non-functional requirements

• Scale. About 200M places worldwide and 100M daily active users, each running about five searches a day (a map pan counts as one): roughly 6,000 searches a second on average and 20,000 at the dinner-time peak. The estimates below show the arithmetic.
• Low latency. Search under 80 ms at p50 and under 200 ms at p99, measured at the server; the place page under 150 ms at p99. A map that stutters while you pan feels broken.
• Read-heavy. Searches and page views outnumber writes about 200 to 1: only about 2M new reviews and 2M place edits a day.
• Fresh, not strongly consistent, search. An owner’s edit should be searchable within 5 minutes (aim for under a minute), and a new review should count in the place’s search rating within about 5 minutes. The person who wrote a review must see it on the place page immediately.
• Availability. 99.99% for search — slightly stale results beat no results. 99.9% for writes, and an acknowledged review is never lost.
• Correct geography. Distances are great-circle distances in metres, and a place 10 m outside a grid cell must not disappear from results.

Out of scope

• Reservations and ordering. Transactional flows with their own consistency needs; see food delivery.
• Ads ranking. Sponsored results come from a separate auction and are merged into the list.
• Photo storage internals. Photos live in blob storage behind a CDN; we only store references.
• Recommendation feeds. “Places you might like” is a personalisation problem, not a query.
• Review fraud detection. Important, but it runs beside this design; it comes back in the follow-ups.

The set-up

Plan the approach

Build the simplest version of each requirement on a relational database with a spatial index, then spend the deep dives on what makes the problem hard: indexing two dimensions, combining text with geography, ranking, uneven density, a fresh search index, and serving 20,000 queries a second.

Core entities

• Place. place_id, name, categories, location (latitude, longitude), address, weekly opening hours with a time zone, price level 1–4, attributes (“pure veg”, “wheelchair access”), owner and updated_at.
• Review. review_id, place_id, user_id, a rating from 1 to 5, text, photo IDs and created_at. One review per user per place.
• Place stats. Review count, sum of ratings and a derived quality score. Kept in their own row so that reviews never contend with an owner’s edit of the place.
• User and business owner accounts; an owner is linked to the places they have claimed.
• Search document. A denormalised, read-only copy of a place and its stats, plus precomputed fields such as cell IDs and opening-hour ranges, that lives in the search index.

As tables in PostgreSQL with the PostGIS extension:

CREATE TABLE places (
  place_id    BIGINT PRIMARY KEY,
  name        TEXT NOT NULL,
  categories  TEXT[] NOT NULL,
  geog        GEOGRAPHY(POINT, 4326) NOT NULL,  -- WGS 84 longitude/latitude
  price_level SMALLINT,                         -- 1 = ₹ … 4 = ₹₹₹₹
  hours       JSONB,                            -- weekly hours in local time
  tz          TEXT NOT NULL,                    -- e.g. 'Asia/Kolkata'
  owner_id    BIGINT,
  version     INT NOT NULL DEFAULT 1,
  updated_at  TIMESTAMPTZ NOT NULL DEFAULT now()
);
CREATE INDEX places_geog_gist ON places USING GIST (geog);

CREATE TABLE place_stats (
  place_id     BIGINT PRIMARY KEY REFERENCES places,
  review_count INT    NOT NULL DEFAULT 0,
  rating_sum   BIGINT NOT NULL DEFAULT 0,
  quality      REAL                             -- recomputed asynchronously
);

CREATE TABLE reviews (
  review_id  BIGINT PRIMARY KEY,
  place_id   BIGINT NOT NULL,
  user_id    BIGINT NOT NULL,
  rating     SMALLINT NOT NULL CHECK (rating BETWEEN 1 AND 5),
  body       TEXT,
  created_at TIMESTAMPTZ NOT NULL DEFAULT now(),
  UNIQUE (place_id, user_id)
);

API

Search takes either a point and a radius, or the bounding box of the visible map:

GET /v1/search?lat=12.9352&lng=77.6245&radius_m=2000&q=biryani&open_now=true&price_max=2&min_rating=4&limit=20
GET /v1/search?bbox=12.920,77.607,12.964,77.651&q=biryani&zoom=15&limit=50

{
  "results": [
    { "place_id": "p_5a17", "name": "Nawab's Kitchen", "distance_m": 1510,
      "rating": 4.6, "review_count": 3012, "price_level": 2, "open_now": true,
      "location": { "lat": 12.9455, "lng": 77.6302 } },
    { "place_id": "p_81c2", "name": "Dum Biryani Corner", "distance_m": 640,
      "rating": 4.1, "review_count": 380, "price_level": 2, "open_now": true,
      "location": { "lat": 12.9371, "lng": 77.6190 } }
  ],
  "radius_used_m": 2000,
  "next_cursor": "eyJzY29yZSI6MC41LCJpZCI6InBfODFjMiJ9"
}

The cursor encodes the last score and place ID, so page two continues where page one stopped even if new places were indexed in between (see cursor pagination). radius_used_m tells the client when the server widened the search.

Place page and reviews:

GET  /v1/places/p_5a17                        → details, photo URLs, rating summary
GET  /v1/places/p_5a17/reviews?sort=recent&cursor=…
POST /v1/places/p_5a17/reviews                body: rating, text, photo_ids
     Idempotency-Key: 6f1c…                    a retry on flaky 4G never posts twice

Owners:

POST  /v1/places                              → a new place, pending verification
PATCH /v1/places/p_5a17                       body: only the changed fields
      If-Match: "12"                           reject if someone else edited version 12 first

Back-of-envelope estimates

These numbers decide whether storage or computation shapes the design. (For the method, see back-of-envelope estimation.)

Search traffic. 100M daily users × 5 searches = 500M searches a day. 500M ÷ 86,400 s ≈ 5,800 searches/s on average. Dinner time runs about 3× the average: 5,800 × 3 ≈ 17,400/s, so plan for 20,000/s.

Place pages. 100M × 3 views = 300M a day; 300M ÷ 86,400 ≈ 3,500/s, about 10,000/s at peak.

Writes. 2M reviews a day ÷ 86,400 ≈ 23/s, and 2M place edits a day (1% of places) is another 23/s. Even at 5× peak, 46 × 5 = 230 writes/s — one well-sized primary database.

Read-to-write ratio. (500M + 300M) ÷ (2M + 2M) = 800M ÷ 4M = 200 : 1.

Storage. A place row with hours, attributes and address is about 2 KB: 200M × 2 KB = 400 GB. A search document with only the searchable and sortable fields is about 1 KB: 200 GB per copy, 600 GB with three copies. The coordinates alone are 200M × 16 bytes = 3.2 GB. Reviews average about 1 KB of text; a billion existing reviews is 1 TB, growing by 2M × 1 KB = 2 GB a day, about 730 GB a year.

Search CPU. Plan for the broad queries, not the narrow ones: “restaurants” with no other filter keeps about 2,000 candidates after its filters and spends roughly 10 µs scoring each: 2,000 × 10 µs = 20 ms of CPU per query. 20,000 queries/s × 20 ms = 400 CPU-seconds every second, so 400 cores busy; at a 50% utilisation target that is 800 cores, or 50 machines with 16 cores, before any caching.

Latency budget. Gateway and search service ≈ 10 ms; index query ≈ 40 ms at p50 and 140 ms at p99; hydrating 20 result cards from a cache ≈ 10 ms. The p99 lands near 10 + 140 + 10 = 160 ms, inside the 200 ms target.

What the numbers decide: the data is small and writes are trivial; the cost is CPU per query and tail latency. So search needs its own copy of the data, built for search, replicated widely and fed asynchronously — and the write path can stay simple.

High-level design

Build one requirement at a time. By the end of this section the design works for a country-sized catalogue at moderate traffic; the deep dives make it global and fast.

Users should be able to search for places nearby

Start with what most teams already run: PostgreSQL with the PostGIS extension. The geog column has a GiST index, which PostGIS implements as an R-tree over bounding boxes. ST_DWithin is index-assisted: the index finds places whose boxes touch the search circle, then PostGIS checks the exact distance in metres for only those candidates. Category, price and rating are ordinary predicates on the same rows.

The flow:

1. The client sends its location, a radius (or the map’s bounding box) and the filters.
2. The search service validates them, clamps the radius, and builds one parameterised query.
3. PostgreSQL uses the GiST index for the radius, applies the other predicates, sorts the survivors by distance and returns 20 rows.

“Open now” and real ranking are left out for now; both get deep dives.

Users should be able to open a place

A place page needs the place row, its stats and the first page of reviews. A place service reads them; reviews are paged with an index on (place_id, created_at DESC). Popular places are read thousands of times an hour and change rarely, so the service uses a cache-aside Redis cache keyed by place ID with a 10-minute TTL, deleted whenever the place is edited (see caching strategies). Photos are URLs pointing at blob storage behind a CDN; the app downloads them directly.

Users should be able to write a review

A review service inserts the review and, in this first version, updates the place’s stats in the same transaction:

BEGIN;
INSERT INTO reviews (review_id, place_id, user_id, rating, body)
VALUES (:id, :place, :user, 5, :body);                    -- UNIQUE(place_id, user_id)
UPDATE place_stats
   SET review_count = review_count + 1, rating_sum = rating_sum + 5
 WHERE place_id = :place;
COMMIT;

The unique constraint enforces one review per user per place; the idempotency key makes a retried POST return the first result. The response carries the stored review so the app shows it at once, and for the next minute that user’s place-page reads go to the primary — read-your-writes without slowing anyone else.

Business owners should be able to add and update places

A business service checks that the caller owns the place, geocodes the address, maps categories onto a fixed taxonomy (“Biryani”, “South Indian”, “Cafe”), parses opening hours, and writes to the primary with a version check (If-Match) so two managers cannot silently overwrite each other. New places stay “pending” until verified, which keeps spam out of search. Each edit deletes the place’s cache entry.

Search still reads the same database, so an edit is searchable once replication catches up — about a second. That changes when search moves to its own index.

This works: one PostGIS database answers a 2 km radius query over a city in milliseconds, and for one country at a few thousand searches a second you could stop here. At 200M places, 20,000 searches a second, free text and real ranking, it strains — and those are the deep dives.

Deep dives

Why can’t we just index latitude and longitude?

It is the first thing everyone tries: two numeric columns, a B-tree index, and WHERE lat BETWEEN … AND lng BETWEEN …. It is also the reason geospatial indexes exist, so explain it crisply.

Bad: a B-tree on lat, on (lat, lng), or one on each. A B-tree orders rows along one dimension. A ±2 km box around Koramangala is lat BETWEEN 12.917 AND 12.953 — a band 4 km tall that wraps the planet, about 39,000 km long at this latitude. An index on lat walks every place in it. A composite (lat, lng) index barely helps: the second column only narrows rows with equal latitudes, and almost none are equal. Two indexes combined with a bitmap AND read both bands — latitude, and a 4 km-wide longitude band from pole to pole — and intersect them.

Do the arithmetic once. The band is 4 km × 39,057 km ≈ 156,000 km²; the circle is π × 2² ≈ 12.6 km². The index reads a region about 12,000 times larger than the answer. Most of it is ocean, but in a dense country one unlucky latitude can mean hundreds of thousands of index entries for a few thousand results — and the cost depends on where the user stands, a bad property for a p99 target.

There are two ways out, and every geospatial index is one of them:

• Map two dimensions onto one so that nearby points get nearby keys — a space-filling curve. Geohash, S2 and H3 cell IDs work like this, and then an ordinary B-tree or sorted key-value store can range-scan them.
• Split space in two dimensions at once with a tree whose nodes are regions: quadtrees, R-trees and k-d trees.

Which geospatial index should we use?

All of them use PostGIS’s two-pass trick: a cheap index step returns a superset of cells or boxes touching the search area, and an exact distance check removes the extras. They differ in cell shape, density adaptation, where the index lives, and how updates work.

Geohash. Interleave the bits of longitude and latitude, halving the world each time, and write every 5 bits as one base-32 character. The result is a string in which a prefix is a cell: every place inside cell tdr1w6 has a geohash that starts with tdr1w6, and every extra character divides the cell into 32. Cell sizes at the equator are about 4.9 km × 4.9 km for 5 characters, 1.2 km × 609 m for 6, and 153 m × 152 m for 7. To search 500 m around a point you compute its 6-character cell, then fetch that cell and its 8 neighbours — 9 prefix scans on any sorted store.

The neighbours matter because of edge effects: two points 22 m apart across a cell edge get different hashes (tdr1w6 and tdr1w7), and two points 69 m apart across the Greenwich meridian, gcpuzgp and u10hb50, share no prefix at all — a Z-order curve jumps at every quadrant boundary. The gain is simplicity: a geohash is a plain string for PostgreSQL, Cassandra, DynamoDB or a Redis sorted set (Redis’s GEOSEARCH stores 52-bit geohashes as scores). The cost: one cell size everywhere — too coarse in Connaught Place, too fine in the desert — and a 3 × 3 block over-fetches.

Quadtree. Start with the world as one square. Whenever a node holds more than N places — say 100 — split it into four quadrants, and recurse. Dense areas get deep trees with tiny leaves; empty areas stop early with huge leaves. Around Connaught Place a leaf of 100 places might be only about 150 m across, roughly 18 levels deep; in western Rajasthan a single leaf can cover 10 km and sit about 12 levels down. A query walks down to the leaves that intersect the circle, or runs a best-first search for the K nearest places.

Size it before you propose it. Leaves capped at 100 and typically half full give about 4M leaves for 200M places; a quadtree with L leaves has (L − 1) ÷ 3 internal nodes, about 1.3M more. At 64 bytes per node (a box and four child pointers): 5.3M × 64 B ≈ 340 MB. Leaves hold an 8-byte ID and 8 bytes of coordinates per place: 200M × 16 B = 3.2 GB. Total about 3.5 GB — every search server can hold a full copy, rebuild it in minutes at start-up, and apply a stream of edits afterwards. The gain is density-adaptive cells and natural K-nearest queries; the cost is that sharding, replication and concurrent updates are all your code.

S2. Google’s S2 library projects the sphere onto the six faces of a cube and builds a quadtree on each face, 30 levels deep; a level-30 leaf cell is about 1 cm across. Every cell gets a 64-bit ID that is its position along a Hilbert curve, so a cell is a contiguous range of IDs and its children are sub-ranges. Level 12 cells are about 3–6 km² (edges around 2 km), level 13 about 0.8–1.6 km², level 14 about 0.2–0.4 km². A region coverer approximates your search circle with a small number of cells of mixed levels — say 8 — and each becomes one range scan on any sorted store. The Hilbert curve is the quiet improvement over geohash.

S2 suits range scans on Bigtable-, Spanner- or Cassandra-style stores. It costs a library dependency, and its 64-bit IDs are harder to eyeball than tdr1w6.

H3. Uber’s H3 tiles the Earth with hexagons at 16 resolutions; each cell has 7 children, plus 12 pentagons per resolution. Average areas are about 5.2 km² at resolution 7, 0.74 km² at 8 and 0.11 km² at 9. All six neighbours of a hexagon share an edge and sit at the same distance, which makes “cells within k steps” rings and smoothing clean — ideal for heatmaps, delivery zones and surge areas. The cost for search: children only approximately fill their parent, so containment queries need care.

R-tree (PostGIS GiST). Nested bounding boxes that stay balanced as data changes, for points and shapes alike — neighbourhood polygons, delivery areas — inside your transactional database. The cost is what surrounds it: text relevance, ranking and 20,000 queries a second are not what an OLTP database is built for.

BKD tree (Lucene, Elasticsearch, OpenSearch). A geo_point is indexed in a block k-d tree, split along the widest dimension until a cell holds at most 1,024 points, stored as one on-disk leaf block. It adapts to density like a quadtree, is immutable per segment (updates arrive as new segments, merged in the background), and — crucially — sits next to an inverted index for text and doc values for filters and scoring.

The recommendation: serve search from a Lucene-based engine’s geo_point. Finding nearby points is easy for every option above; the hard part is combining geography with text, filters and ranking. Also store a geohash or S2 cell ID on each document for cache keys, shard routing and map grid aggregations. Keep PostGIS in the source database for shapes and admin queries. If the interviewer wants you to build the index yourself, a quadtree or S2 on a key-value store shows you understand density and locality.

How do we combine text, filters and distance in one query?

“Biryani, open now, under ₹₹, rated 4+, within 2 km” has four kinds of condition. Where they are evaluated decides the latency.

Bad: separate systems, joined in the application. A geo service returns 8,000 place IDs within 2 km, a text service returns every “biryani” match in the city, and the application intersects, filters, sorts and pages — moving thousands of IDs per request. Yelp lived a version of this: its legacy engine published index snapshots every few minutes, so fresher features came from a second store queried in parallel, and merging the two in the application “did not scale well”.

Good: one index, with a filter context. Put everything on one document — location as geo_point, name and categories as text, price, rating and hours as numeric and range fields — and send one bool query. Radius, price, rating and open-now go in the filter clause: yes-or-no, unscored, cacheable as bitsets. Only the text match is scored.

Great: one query that also ranks. Wrap the bool query in a function_score that multiplies text relevance by a distance decay and a quality score, so the engine ranks while it searches. A second stage then re-ranks the top 200 with a learned model and personal signals. Yelp’s 2017 migration ran its ranking code inside Elasticsearch as a plugin for this reason, hot-reloading new versions without restarting the cluster.

{
  "size": 200,
  "query": {
    "function_score": {
      "query": {
        "bool": {
          "must":   [ { "match": { "name_and_categories": "biryani" } } ],
          "filter": [
            { "geo_distance": { "distance": "2km",
                "location": { "lat": 12.9352, "lon": 77.6245 } } },
            { "range": { "price_level": { "lte": 2 } } },
            { "range": { "rating": { "gte": 4.0 } } },
            { "term":  { "open_minutes_utc": 5190 } }
          ]
        }
      },
      "functions": [
        { "gauss": { "location": { "origin": { "lat": 12.9352, "lon": 77.6245 },
                                   "scale": "2km", "decay": 0.5 } } },
        { "field_value_factor": { "field": "quality", "missing": 0.1 } }
      ],
      "score_mode": "multiply",
      "boost_mode": "multiply"
    }
  }
}

Two fields in that query need precomputing, because the engine cannot work them out cheaply at query time:

• Open now. Hours are stored in local time, and “now” differs per place. The indexer converts weekly hours into minutes of the week in UTC, stored as an integer range field: Monday 11:00–23:00 in India (UTC+5:30) becomes 05:30–17:30 UTC, the range 330–1050. The query computes the current UTC minute once — Thursday 20:00 IST is 3 × 1,440 + 870 = 5,190 — and matches ranges containing it. Ranges crossing the end of the week are split, and places in zones about to change daylight-saving offset are re-indexed.
• Quality. A single precomputed number per place from the rating maths in the next deep dive, updated asynchronously as reviews arrive.

The filter on rating uses the rating the user sees, because that is what “4+ stars” means to them; the ranking uses quality, which is fairer.

How do we rank by distance and quality?

Filters decide which places qualify; ranking decides which twenty the user actually sees. Two naive orders fail in opposite ways.

Bad: nearest first. The closest qualifying place wins even if it is mediocre and a much-loved one is 600 m further. Users stop trusting the list.

Bad: highest average rating first. A place with two five-star reviews (both from the owner’s cousins) averages 5.0 and beats a place averaging 4.6 over 3,000 reviews. A small sample is noisy, and a raw average rewards the noise.

Good: a Bayesian average. Pretend every place starts with C imaginary reviews at the typical rating m, then add its real ones:

quality_rating = (C × m + sum of ratings) ÷ (C + number of ratings)

With m = 3.8 (the mean for this category in this city) and C = 20 (roughly the median review count), the two-review place scores (20 × 3.8 + 2 × 5) ÷ (20 + 2) = 86 ÷ 22 ≈ 3.91, and the 3,000-review place scores (76 + 3,000 × 4.6) ÷ 3,020 = 13,876 ÷ 3,020 ≈ 4.59. A few reviews barely move a new place away from the typical rating; thousands of reviews let the real average speak. Compute m per category and city, because a 4.0 for a biryani place in Hyderabad and a 4.0 for a café in Pune are not the same signal.

Great: multiply a distance decay by quality, then re-rank. Distance should cost gradually, not cut off at a hard edge. A Gaussian decay with scale 2 km and decay 0.5 scores a place 1.0 at your feet, 0.5 at 2 km and about 0.21 at 3 km. Turn the Bayesian rating into a 0–1 quality, (rating − 3) ÷ 2, and multiply. The two-review place 300 m away scores 0.985 × 0.455 ≈ 0.45; the 4.6 place 1.5 km away scores 0.677 × 0.797 ≈ 0.54 and ranks first. With the raw average, the two-review place would have scored 0.98 × 1.0 = 0.98 and buried everything.

Tune the decay to context: walking in Connaught Place, a scale near 800 m; driving in rural Rajasthan, 15 km. The search service picks it from local density (next deep dive) and the map’s zoom level. A second stage then re-ranks the top 200 with a model trained on clicks, calls and direction requests, adding personal and time-of-day signals. Keep the first stage simple and explainable, so a bad model release degrades to a sensible order rather than nonsense.

How do we handle dense cities and empty deserts?

A fixed radius is wrong almost everywhere. Around Connaught Place there might be 40 biryani places per square kilometre; in the countryside of western Rajasthan perhaps one per 20 km² — 0.05 per km².

Bad: always 2 km. In the city, π × 2² × 40 ≈ 500 candidates to score, most of them never shown, and the p99 suffers. In the desert, π × 2² × 0.05 ≈ 0.6 — usually an empty page, the worst possible answer.

Good: widen until there are enough. Try 2 km; with under 20 results, try 5, 10, then 25 km. Rural users see something, but four sequential 40 ms queries eat the whole latency budget, and firing them in parallel quadruples the load.

Great: choose the radius from precomputed density, once. Keep a small in-memory table of place counts per geohash-5 cell (about 4.9 km × 4.9 km) for the top categories, rebuilt hourly from the index. To get about K = 200 candidates, solve π r² × density = K for r:

r = √(K ÷ (π × density)), clamped between 500 m and 50 km.

For Connaught Place, √(200 ÷ (π × 40)) = √1.59 ≈ 1.3 km. For rural Rajasthan, √(200 ÷ (π × 0.05)) = √1,273 ≈ 36 km. One query either way, and both return a useful list. If strict filters (open now at 2 am) still leave fewer than 20 results, allow one retry at three times the radius, and return radius_used_m so the app can say “showing places up to 36 km away”.

The map viewport needs a different answer. Zoomed out over Delhi NCR, the viewport may hold 200,000 places. Return the top 50 by quality as pins, plus a grid aggregation — geohash or map-tile buckets with counts — for “1,240 places here” bubbles that give way to pins as the user zooms in.

A quadtree gives you some of this for free — its leaves hold about 100 places whether they are 150 m or 10 km across — and the density table is the same idea applied to a search engine.

How do we keep the search index fresh?

Search now has its own copy of every place. The index must follow the database within minutes, survive crashes without losing updates, and never invent data.

Bad: dual writes. Write the database, then the index. If the second write fails, the copies disagree forever; if two edits race, the index may apply them out of order. Yelp rejected this for order search: failing an order because the search write failed is unacceptable, and ignoring the failure loses data.

Bad: periodic batch rebuilds. Simple, but owners wait hours, and finding “what changed” pollutes the schema with flags. Yelp’s pre-2017 business search used snapshots that took minutes to reach serving replicas — too slow for features that needed seconds.

Good: change data capture. Tail the database’s own log — PostgreSQL’s write-ahead log or MySQL’s binlog — and publish each committed change to a Kafka topic keyed by place_id, so one place’s changes stay ordered. An indexer rebuilds each changed place’s document (place plus stats) and bulk-writes it; with a one-second refresh, edits are searchable within seconds, and you alert when lag approaches the 5-minute target. Yelp’s order search has this shape: binlog to Kafka, then a Flink job into Elasticsearch, audited nightly. See change data capture.

Great: CDC plus coalesced rating updates. Updating place_stats inside every review transaction is a hot row waiting to happen: when a street-food stall goes viral after a vlogger’s video, hundreds of reviews and thousands of “helpful” votes contend for one row lock. Each change would also rewrite the search document, and Lucene updates are delete-plus-reinsert, so 1,000 updates an hour leave 1,000 deleted copies to merge away. Instead:

1. The review service inserts the review and an outbox row in one transaction (transactional outbox), and the outbox is relayed to a review-events topic keyed by place_id.
2. A rating aggregator consumes it. One partition owns each place, so there is no contention; it keeps running sums in memory and, at most once every 60 seconds per changed place, writes one UPDATE place_stats with the new count, sum and quality.
3. That update flows through the same CDC path into the index. A place that receives 1,000 reviews in an hour causes 60 index updates, not 1,000.

Two safety nets complete it. A nightly job recomputes stats from the reviews table, repairing drift from deleted or spam-filtered reviews. And because the index is derived data, you can rebuild it: build a new index from a database snapshot, replay Kafka from the offset recorded at snapshot time, then flip an alias. That is how you change analyzers or shard counts without downtime — the change Yelp’s legacy system made so painful that it avoided analyzer improvements.

How do we serve 20,000 searches a second, fast, everywhere?

The index is about 200 GB per copy and changes about 50 times a second, so scaling is about reads: make each query touch little, copy the index widely, and skip it when the answer is cached.

Shard by geography first. Hashing every place across 64 global shards makes a Bengaluru search fan out to all 64, mostly full of other countries. Instead, keep one index per region (South Asia, Europe …), route each query by the location searched, and query both indexes near a regional boundary. Yelp’s original engine had geographic shards so that a San Francisco search never touched Chicago.

Then shard by hash inside a region. Split each regional index into, say, 8 hash shards by place_id; a query fans out to all 8 in parallel, each scoring an eighth of the candidates. Yelp found that adding shards sped up scoring — up to a sweet spot, after which fan-out overhead wins. Avoid sharding by city: Mumbai at 8 pm becomes a hot shard, the kind of hot and cold nodes Yelp later listed among its reasons for building its own engine.

Replicate for throughput. Query load spreads across each shard’s replicas. At about 50 writes a second, the cost of document-level replication — every replica re-indexes every document — doesn’t matter; at high write rates, engines that copy finished segments to replicas, like Yelp’s Nrtsearch, save that CPU.

Cache the popular questions. A few hundred queries — “restaurants”, “coffee”, “ATM”, “petrol pump” — in a few thousand busy cells make up much of the traffic. Snap the point to its 6-character geohash cell (about 1.2 km × 0.6 km) and key Redis on cell, normalised query, filters and a 15-minute time bucket (for “open now”). Cache the top 200 candidates with coordinates for 90 seconds, not the final page: on a hit the service re-ranks them by the user’s exact distance in microseconds, so people at opposite ends of a cell still get correct orders. For map panning, snap viewports to standard tiles and cache per tile and filter set at the CDN for 60 seconds. If 40% of searches hit a cache, the index sees 12,000 queries a second instead of 20,000.

Go multi-region for latency and failure. Each region serves from its own index replicas, plus a standby copy of a neighbouring region’s index. A place’s database primary lives in one home region — at 50 writes a second, cross-region writes are fine — and CDC events are replicated to every region holding that place’s index. If a search cluster fails, traffic moves to the standby with results seconds staler: availability over consistency, easy to defend for search (CAP and PACELC).

The final design

The read path is edge cache, query cache, search service and a regional search index. The write path is three small services on one database. Change data capture is the only bridge between them.

1. Search request. The app sends a point or viewport plus filters. Viewport searches snapped to map tiles are often answered by the CDN; the rest reach the search service through the gateway.
2. Query cache. The service snaps the point to its 6-character geohash cell and looks up cell + query + filters + time bucket. On a hit it re-ranks the 200 cached candidates by the user’s exact distance and returns.
3. Search index. On a miss it picks a radius from the density table and sends one bool + function_score query to the regional index, fanned out to its hash shards. A second-stage model re-ranks the top 200, and the candidates are cached.
4. Place page. The place service reads its cache, falling back to a database replica; photos come from the CDN.
5. Review. The review service writes the review and an outbox row in one transaction; the author sees it immediately.
6. Ratings. The aggregator consumes review events per place and writes each changed place’s stats at most once a minute.
7. Owner edit. The business service validates and geocodes the change, writes the primary with a version check, and drops the place’s cache entry.
8. Indexing. CDC carries every committed change through Kafka to the indexer, which rebuilds the document; the index refreshes every second.

Against the requirements: with 40% of 20,000 searches/s answered by caches, the index serves 12,000/s; at 20 ms of CPU each that is 240 busy cores, about 30 sixteen-core machines at 50% utilisation, spread across regions. The p99 is near 160 ms. Owner edits are searchable in seconds and ratings within a couple of minutes, well inside the 5-minute target. Writes stay near 50/s on one primary, and reviews are durable once acknowledged. Search survives index failures through replicas, a standby region and cached results.

What interviewers look for by level

Follow-up questions

What if users want places along a route, not around a point?

“Petrol pumps on the way to Mysuru” is a corridor search. Buffer the route polyline by about 1 km, query with that shape (ST_DWithin against a line in PostGIS, or a geo_shape query in the search engine), and rank by detour time — the extra minutes to stop — rather than straight-line distance, which needs the routing engine from Google Maps. Cache by route segment, because many drivers share the same highway stretches.

What if places have service areas, like “who delivers to me”?

Now the place is a polygon and the user is a point, so the question flips to “which shapes contain me?”. Index delivery areas as geo_shape polygons (or as sets of H3 cells), and query with the user’s point. With cells, precompute cell → places once and the lookup is a key fetch. This is how food delivery apps answer “restaurants that deliver here”.

What if we must build it on a key-value store, without a search engine?

Use S2 cell IDs. Store each place under a partition key of its level-10 cell (about 80 km²) with the level-30 cell ID as the sort key. For a query, the region coverer returns about 8 cells; each becomes a range scan inside one or two partitions. Filter and rank in the search service. You lose free-text relevance and must build ranking yourself, but you gain a store that scales writes easily — the same layout serves moving objects such as drivers in Uber.

What if fake reviews flood a place?

Treat review trust as a stream-processing problem beside the write path. Score each review asynchronously — account age, device and network reuse, bursts of five-star reviews from new accounts, text similarity — and mark suspicious ones as “not counted” rather than deleting them. The aggregator excludes them from place_stats, so the rating and the search ranking heal within a minute. A rate limit per user and per device on review creation stops the crudest attacks.

What if users want autocomplete on place names as they type?

That is a different index: prefix matches on names (edge n-grams or a completion structure), filtered to a broad area such as the user’s city cell and boosted by popularity. It must answer in about 50 ms per keystroke, so it runs as its own small service and cache. See typeahead.

How to say it in the interview

“I’ll design nearby search for about 200 million places and 20,000 searches a second at peak, with p99 under 200 milliseconds. Writes are tiny — about 50 a second for reviews and owner edits — so this is a read problem, and search may be a few minutes stale.

The source of truth is PostgreSQL. Search runs on a separate Lucene-based index with one document per place: a geo point, text fields, filters and a precomputed quality score. I wouldn’t index latitude and longitude with B-trees — each gives you a band around the planet. Geohash, quadtrees, S2 and H3 all solve that; I’d use the search engine’s BKD-based geo point because the hard part is combining geography with text and ranking, and keep a geohash on each document for caching and grid aggregations.

A search is one query: filters for radius or viewport, category, open now, price and rating, which aren’t scored and are cached as bitsets, wrapped in a function score that multiplies text relevance by a Gaussian distance decay and a Bayesian-average rating, so a 5.0 with two reviews doesn’t beat a 4.6 with three thousand. Open now uses precomputed UTC minute-of-week ranges. The radius comes from a density table: about 1.3 kilometres in Connaught Place and 36 in rural Rajasthan.

To keep the index fresh, change data capture tails the database log into Kafka, and an indexer rebuilds changed documents — owner edits are searchable in seconds. Reviews go through an outbox to an aggregator that updates each place’s stats at most once a minute, which avoids a hot row and index churn for viral places.

For scale, the index is sharded by region, then by hash, with replicas. Popular queries are cached per geohash cell as the top 200 candidates, re-ranked by each user’s exact distance, and map tiles are cached at the CDN. If a region’s index fails, a standby serves slightly stale results — availability over consistency, which is right for search.”

Concepts used in this design

• Geospatial indexes: geohash, quadtrees, S2 and H3 — the structures compared in the second deep dive.
• Proximity search — the general pattern behind every “near me” feature.
• Database indexes — why a B-tree handles one dimension well and two badly.
• Elasticsearch — geo points, filter context and function scores in one query.
• How search engines work — inverted indexes, segments and refresh.
• Change data capture — keeping the index in step with the database.
• Transactional outbox — publishing review events without dual writes.
• Hot keys, cache stampede and invalidation — the viral place’s stats row and popular cells.
• Caching strategies — cache-aside for place pages, candidate caches for search.
• Scaling reads — replicas, caching and sharding for a 200 : 1 workload.
• Database sharding — geographic then hash sharding of the index.
• Strong vs eventual consistency — exact writes, eventually consistent search.
• Design Nearby Friends — the sibling problem where both sides move.

References and further reading

1. Moving Yelp’s Core Business Search to Elasticsearch (Yelp Engineering, 2017)engineeringblog.yelp.comThe legacy geosharded and microsharded Lucene search, its minutes of index delay, merging two stores in the app, and why scoring scaled with more shards.
2. Fast Order Search Using Yelp’s Data Pipeline and Elasticsearch (Yelp Engineering, 2018)engineeringblog.yelp.comWhy batch copies and dual writes were rejected in favour of MySQL binlog to Kafka to a Flink sink into Elasticsearch.
3. Nrtsearch: Yelp’s Fast, Scalable and Cost Effective Search Engine (Yelp Engineering, 2021)engineeringblog.yelp.comCosts of document-based replication, hot and cold nodes, hard autoscaling, and segment replication as the fix.
4. S2 Geometry: S2 cell hierarchys2geometry.ioSix cube faces, levels 0–30, 64-bit cell IDs ordered along a Hilbert curve, and leaf cells about 1 cm across.
5. S2 Geometry: S2 cell statisticss2geometry.ioCell areas and edge lengths per level (level 12 ≈ 3–6 km², level 13 ≈ 0.8–1.6 km², level 14 ≈ 0.2–0.4 km²).
6. H3: tables of cell statistics across resolutionsh3geo.orgCell counts and average hexagon areas per resolution (res 7 ≈ 5.2 km², res 8 ≈ 0.74 km², res 9 ≈ 0.11 km²), 12 pentagons at every resolution.
7. Elasticsearch: geohash grid aggregationelastic.coGeohash cell dimensions at the equator for lengths 1–12 (length 6 ≈ 1.2 km × 609 m).
8. Elasticsearch: function score queryelastic.cogauss, exp and linear decay with origin, scale, offset and decay; field_value_factor; score_mode and boost_mode.
9. PostGIS workshop: spatial indexingpostgis.netGiST R-trees over bounding boxes, the two-pass index-then-exact check, and ST_DWithin as an index-assisted radius query.
10. Multi-dimensional points, coming in Apache Lucene 6.0 (McCandless, Elastic blog)elastic.coBlock k-d trees: split on the widest dimension until a leaf holds at most 1,024 points, and smaller leaves where data is dense.