Proximity Service: scope, scale and why a naive query fails

The prompt: "Design a service that finds nearby places." Open an app, and it shows the restaurants, shops, or petrol stations within a few kilometres of where you are standing.

Attempt it for 45 minutes before reading. Write down the database query you would issue first, then work out how many rows it touches. That calculation, done honestly, is what makes the rest of the design necessary.

This lesson does that calculation. It scopes the problem, puts numbers on reads, writes and storage, and then tries the ordinary database tools and measures how badly they fail. The failure is what tells you what a spatial index has to do.

Why this section is foundational

Section 19 (Nearby Friends) and Section 20 (Google Maps) both build directly on this one. This is where the vocabulary of geospatial indexing is established — grids, geohashes, quadtrees — and the two later sections assume it. Section 19 in particular exists to show where this design stops working, so it is worth being clear here about the assumptions that make it work.

The most important of those assumptions is that the data barely moves. A restaurant's location is fixed. That single property is what makes a precomputed index viable, and it is exactly the property Section 19 removes.

The five questions

1. Is the search radius fixed or user-selected? A fixed radius (always 5 km) lets you choose one index granularity and stop thinking about it. A user-selected radius from 500 m to 50 km means the index must answer at several scales, which favours some structures over others.

2. How many places, and how often do they change? Ask for both. Two hundred million places that change a few thousand times a day is a completely different problem from two hundred million points that each move every 30 seconds — which is the Nearby Friends problem in Section 19.

3. What is the latency target? Nearby search sits in front of a user waiting on a map screen. Around 100 ms of server time is a reasonable target, and it rules out anything that scans a large fraction of the data.

4. Ranked by distance only, or by other signals? Distance-only is a pure geometry problem. Distance plus rating, plus whether the place is open, plus paid placement, is a retrieval problem followed by a ranking problem — and separating those two phases is the right structure either way.

5. Is business data in scope, or only coordinates? Scope the place details — name, hours, photos — as a separate store, because it is an ordinary key-value lookup and mixing it into the geospatial discussion is a distraction.

Requirements and scale

Functional: given a latitude, longitude, and radius, return the places within it; return details for a place; add, update, and remove places.

Non-functional: 99th-percentile search latency under 100 ms server-side; high availability for search, since a map screen with no results is a broken product; the index may be minutes stale, because a new café appearing in results a few minutes late harms nobody.

The numbers

Invented figures for a global places service. A day is 100,000 seconds (see Rounding aggressively and staying fast).

Search rate:

100M × 5 = 500 million searches/day

500M ÷ 100,000 s = 5,000 searches/s average, and at a 4× peak, 20,000/s

The asymmetry:

500,000,000 reads ÷ 10,000 writes = 50,000 reads per write

That ratio is the licence to precompute. An index that takes an hour to build and answers in a millisecond is an excellent trade when it is read half a billion times between rebuilds. Compare with Section 19 (Nearby Friends), where every point moves and the ratio inverts.

Storage

The geospatial index itself is small. An entry is a cell identifier and a place identifier: call it 8 bytes plus 8 bytes, with overhead, 24 bytes.

200M places × 24 bytes = about 5 GB

Five gigabytes fits in memory on a single machine. This is the most important storage fact in the design, and it shapes Serving and follow-ups: the index does not need sharding for capacity, so it can be replicated instead, which is far simpler and fails better.

Place details are separate and larger. Name, address, hours, category, photos references, rating: perhaps 2 KB per place.

200M × 2 KB = 400 GB

Ordinary key-value data, partitioned by place identifier, cached by identifier. It never participates in a geospatial query — the geo index returns identifiers, and a second lookup hydrates them. Keeping those two stores separate is a design decision worth stating.

Bandwidth

A response of 20 nearby places with summary details is perhaps 20 KB. At 20,000 searches per second that is 400 MB/s of response traffic — real, but unremarkable, and reducible by returning identifiers plus a thin summary and letting the client fetch detail on tap.

Why a naive query fails

Before reaching for a spatial index, establish that the ordinary tools fail. Assert it and the interviewer has no reason to believe you; measure it and the rest of the design is inevitable.

Attempt one: compute distance to everything

SELECT place_id, name FROM placesWHERE haversine(lat, lng, :user_lat, :user_lng) < 5000ORDER BY 3 LIMIT 20;

This is correct and unusable. The distance is computed from the row's own columns, so no index can help: the database must read all 200 million rows and evaluate a trigonometric function on each.

Cost it. Even at an optimistic 5 million rows per second per core of scan-and-compute:

200,000,000 ÷ 5,000,000 = 40 seconds of CPU per query

Against a 100 ms budget, that is 400× over. At 5,000 queries per second it would need 200,000 cores doing nothing else. The failure is not marginal — it is three orders of magnitude.

Attempt two: index latitude and longitude

The instinct is to add a bounding box so an index can be used:

WHERE lat BETWEEN :lat-0.05 AND :lat+0.05  AND lng BETWEEN :lng-0.05 AND :lng+0.05

This is better and still fails, for a reason worth understanding properly.

Count the rows. A band of ±0.05° of latitude spans roughly 11 km. If the 200 million places were spread evenly across 180° of latitude:

200M × (0.1 ÷ 180) = about 111,000 rows in the latitude band

The longitude band similarly holds around 55,000 rows. The database retrieves one of those sets — over a hundred thousand rows — and filters it row by row. The final answer is perhaps 200 places.

111,000 rows read to return 200 = 555 rows read per useful row

And that is the uniform-distribution case, which is the optimistic one. Places cluster in cities. A latitude band through a dense metropolitan region contains far more than the average, so the query is slowest exactly where users are densest.

At 5,000 queries per second, 111,000 row reads each is 550 million row reads per second. No amount of replication makes that reasonable.

What the failure tells you

The problem is dimensional. Two coordinates describe a point on a plane, and a one-dimensional ordering cannot preserve two-dimensional closeness. Every technique in Geospatial indexing options is a different answer to the same question: how do you map two dimensions onto one, so that an ordinary index can find neighbours?