The big idea

What is a proximity service?

"Show restaurants within 2km of me." "Find the 5 nearest drivers." "Which friends are close?" Every one is the same question: given a point, find the objects near it — fast, over millions of pins, potentially while both the searcher and the objects are moving.

A proximity service answers nearest/nearby queries at scale. The whole problem is indexing 2D space so "near this point" becomes a cheap lookup instead of measuring the distance to everything. The tools: geohash, quadtrees, and grid/S2 cells — plus caching, geo-sharding, and handling objects that move.

How to read this: Each step opens with a real design decision — make the call before I show you what ships. Watch the design grow, and at the end drop the spatial index and drop the hot-cell cache to see what makes nearby-search fast. Hit Begin.

Step 1 · Why SQL can't

The distance-scan trap

The naive query: store lat, lng per place and run SELECT … WHERE distance(loc, me) < 2km. Why does this melt over millions of places?

Design decision: A SQL distance filter over a lat/lng column. Why doesn't it scale?

The call: A B-tree indexes one dimension, so a 2D "near" query degrades to scanning + distance-checking every row. — Ordinary indexes are 1D; a bounding-box on lat AND lng still can't prune well, so the database ends up computing distance to a huge fraction of rows. You need a spatial index that maps 2D → a lookup key.

A normal B-tree indexes one dimension. Nearness is inherently 2D — indexing latitude and longitude separately can't prune it, so the query degrades to computing distance against a huge fraction of the table. At millions of pins that's a full scan per query. You need an index that maps 2D space to a lookup key.

The 2D indexing problem: The entire field of spatial indexing exists to solve one thing: reduce the 2D "what's near here?" question to a fast, one-dimensional lookup. Geohash, quadtrees and S2 are three ways to do exactly that.

Step 2 · A service over the pins

Query, then filter

Put a proximity service in front of the places store. Its job splits into two phases regardless of the index used. What are they?

The service works in two phases: (1) candidate selection — use a spatial index to grab the small set of objects in the relevant area (cheap, approximate), then (2) refine — compute the exact distance to just those candidates, filter to the true radius, and rank/sort. The index gets you from millions to dozens; exact math runs only on the dozens.

Coarse index, fine filter: Every spatial approach follows this shape: the index gives a fast, slightly-too-broad candidate set (a cell or few), and a precise distance filter trims it. You never compute distance to everything — only to what the index already narrowed to.

Step 3 · Encode 2D into 1D

Geohash

You want a single indexable key such that nearby points share it — so a query becomes a prefix/range lookup on an ordinary index. How do you turn (lat, lng) into that?

Design decision: How do you turn a 2D coordinate into a 1D key where nearby points cluster?

The call: Concatenate lat and lng as a number. — Simple concatenation doesn't preserve 2D locality — points close in space can be far apart in the concatenated value. Geohash's bit-interleaving is what makes nearby points share a prefix.

Use a geohash: recursively bisect the globe, interleaving latitude and longitude bits into a short base32 string. Longer shared prefix ⇒ closer in space, so a cell is just a prefix, and "nearby" becomes a prefix/range lookup on an ordinary index. A 6-char geohash is a ~1.2km cell; to search, look up the point's cell plus its 8 neighbor cells and refine.

Geohash = locality-preserving key: Geohash maps 2D → 1D while keeping nearby things near in the key space — the one property a plain hash or concatenation lacks. Precision is just prefix length: shorter = bigger cell. Any B-tree/KV store can now do spatial range queries.

Step 4 · Adapt to density

Quadtrees & S2 cells

Geohash cells are a fixed grid — but the world isn't uniform. A downtown cell holds 10,000 restaurants while a rural cell holds 3. Fixed cells are too coarse where it's dense and too fine where it's empty. How do you adapt to density?

Use a quadtree: recursively subdivide a region into 4 quadrants only where density is high, so dense areas get many small cells and sparse areas stay one big cell — each leaf holds a bounded number of objects. Search descends to the leaf covering your point (and neighbors). Google's S2 takes a related approach (a hierarchy of cells over a sphere, avoiding geohash's rectangular distortion). Choice depends on data: geohash is simplest; quadtree/S2 adapt to skew.

Adaptive vs fixed grid: Geohash/grid: fixed cells, dead simple, uneven under skew. Quadtree: cells subdivide with density, so each holds ~equal objects — great for hotspots. S2: spherical cells, accurate globally. All answer "nearby" by finding the covering cell(s); they differ in how they carve space.

Step 5 · The boundary problem

Don't miss the pin across the street

Your point sits near the edge of its cell, and the nearest restaurant is just across the boundary in the next cell. Search only your cell and you'd miss it. How do you avoid this classic bug?

Always search the point's cell plus its neighboring cells (for geohash, the 8 surrounding cells; for a quadtree, adjacent leaves), so a nearby object just over a boundary is included in the candidate set. Then the exact-distance refine step naturally keeps only what's truly within the radius. Pick a cell size close to the typical search radius so "cell + neighbors" reliably covers it without pulling in too much.

Cell + neighbors, then refine: Cell boundaries are arbitrary lines; nearness ignores them. Querying neighbor cells guarantees you don't miss a close object that fell on the other side, and the distance filter removes the extra. Matching cell size to search radius keeps the candidate set small but complete.

Step 6 · Popular places, hot cells

Caching

Nearby-search is overwhelmingly read-heavy, and reads concentrate on dense, popular areas — a downtown cell is queried constantly with near-identical results. Recomputing it every time is wasteful. How do you cut that load?

Cache the results for hot cells. Since a cell's nearby-list changes slowly (places don't move; a new restaurant is rare), cache the candidate list per popular cell and serve repeat queries from cache, invalidating on the occasional update. For largely-static data (restaurants), the index and caches are very stable; caching the densest, most-queried cells removes most of the compute for the areas that get the most traffic.

Read-heavy + slow-changing: Static places are ideal for caching: the answer for "near this downtown cell" is stable for hours. Cache hot cells and you serve the busiest queries from memory. (Moving objects — next step — break this assumption and need a different treatment.)

Step 7 · Moving objects & scale

Drivers, and a planet of pins

Two escalations: the objects move (finding nearby drivers means their cell changes every few seconds), and the dataset is global — too big for one machine. How do you handle motion and scale?

For moving objects, reindex on update: each GPS ping moves the object to its new cell (cheap for a grid/geohash — recompute the key and update one entry). Keep this hot, frequently-written index in memory (Redis geo commands do exactly this) and don't cache it aggressively (it changes constantly). For scale, geo-shard: partition the index/data by region so each shard owns an area, and route a query to the shard(s) covering its search box — a natural partition since queries are inherently local. Add read replicas for hot regions.

Static vs dynamic + geo-shard: Static places → index + cache heavily. Moving objects → in-memory index, constant reindex, little caching. Both geo-shard cleanly because space itself is the partition key: a query only touches the region(s) it covers, so sharding by area scales without cross-shard fan-out (except at region borders).

Step 8 · The sharp edges

Density, precision & borders

Spatial systems have their own gremlins: extreme density hotspots (a stadium), the precision/recall tradeoff of cell size, cross-shard border queries, and the earth being a sphere, not a plane.

Handle density hotspots with adaptive cells (quadtree/S2) or dynamic cell splitting so no cell returns 10,000 candidates. Tune cell size to the query radius to balance too-many-candidates vs too-many-neighbor-cells. Handle border queries (search box spanning shards) by querying the few overlapping shards and merging. Use proper spherical distance (haversine) and a projection-aware index (S2) for global accuracy. And separate static from dynamic objects so each gets the right indexing/caching strategy.

Design for the unhappy path: Stadium → adaptive cells. Cell too big/small → tune to radius. Query across shards → merge overlapping regions. Round earth → spherical math + S2. The elegant "cell lookup + refine" core needs these adjustments to stay fast and correct across real, skewed, spherical geography.

You did it

You just designed a proximity service.

• S — Q
• T — h
• G — e
• Q — u
• A — l
• C — a
• R — e