Proximity search

Proximity search answers “what is near this point?”: restaurants that deliver to you, the nearest free drivers, friends within 2 km. An ordinary index sorts data along one line, but nearness lives in two dimensions, so you need a structure that keeps nearby points together, plus a separate plan for points that move. This playbook climbs from scanning every row to live in-memory indexes, with the arithmetic that says when each rung breaks.

Picture it first: the late-night chemist and the auto stand

It is 11 pm and you need a chemist that is still open. From crude to clever:

1. Phone every chemist in the directory. Correct, and hopeless.
2. Use a directory sorted by how far north each shop is. You jump to your latitude, but that band crosses the whole city.
3. Use a map book: look on your page and the 8 around it, in case you live near an edge.
4. Use a map book with more pages for busy areas.
5. For autos, forget the book. They move every minute, so the stand’s dispatcher keeps a whiteboard of where each driver last radioed from and wipes off anyone gone quiet.

Map it back: a full scan, a B-tree on latitude, geohash or S2 cells, a quadtree or R-tree, and an in-memory index of live positions with expiry. Static and moving points need different tools; tell them apart first.

Spotting the pattern

Listen for these cues:

• “Near me”, “nearby”: drivers, restaurants, stores, ATMs, friends, dating matches.
• A radius or a count: “within 5 km”, “the 10 nearest”.
• Sorted by distance or ETA. ETA also needs a road network.
• A map viewport: “show the pins in view” is a bounding-box query.
• Geofencing: “is this address inside the delivery zone?” The stored things are areas; the query is a point.
• Location updates every few seconds, which make it a write-and-freshness problem.

The biggest fork is static versus moving. Restaurants change a few times a day and are read millions of times, so a disk-based spatial index with replicas and caches is ideal. Drivers report every few seconds and each position is stale almost at once, so you need an index that absorbs hundreds of thousands of overwrites a second and forgets anyone who stops reporting.

It does not apply when:

• The product filters by a named area. “Do you deliver to PIN 560034?” is an equality lookup (database indexes).
• N is small. A chain with 300 stores can compute every distance in memory: 300 × about 1 µs = 0.3 ms.
• “Near” means similar. “Restaurants like this one” is vector search.

Two running examples, with assumed numbers:

• Restaurants that deliver to you (static). 500,000 restaurants nationwide; a Bengaluru-sized city, roughly 40 km across, has 60,000: about 40 per km² on average (60,000 ÷ 1,500 km²), up to 200 per km² in the busiest areas. A search covers 3 km; peak is 5,000 searches a second nationwide, 1,000 in Bengaluru.
• Nearest available drivers (moving). 1,000,000 drivers online at peak, each phone reporting every 4 seconds: 1,000,000 ÷ 4 = 250,000 updates a second. Bengaluru’s 100,000 drivers send 25,000 a second.

Levels 0 and 1: scan, then draw a box

Level 0: compute the distance to every row

SELECT id, name, haversine_km(lat, lng, 12.9756, 77.6050) AS km
FROM restaurants
ORDER BY km
LIMIT 20;

Haversine gives the great-circle distance between two points, and no index helps with an expression computed on every row. So the database reads all 500,000 restaurants, computes their distances and sorts them. At about 1 µs per row that is 0.5 seconds of CPU per search: a 16-core server manages 16 ÷ 0.5 = 32 searches a second, against a peak of 5,000. Filtering by city cuts the scan to 60,000 rows (60 ms), but Bengaluru’s 1,000 searches a second still need 60 cores. Moving objects fail the same way: Uber’s Ringpop post describes an early system that searched through every car in memory for each request, which stopped scaling as the company grew.

Say: “A scan costs N times the per-row work on every query. Fine for a few thousand points, not for a national catalogue.”

Level 1: a bounding box on lat and lng

Turn the circle into a box an ordinary index can use. A degree of latitude is about 111 km; a degree of longitude is 111 km × cos(latitude): 108 km in Bengaluru (13°N), 97 km in Delhi (28.6°N).

-- 3 km around MG Road: Δlat = 3 / 111 ≈ 0.027°, Δlng = 3 / 108 ≈ 0.028°
SELECT id, name
FROM restaurants
WHERE lat BETWEEN 12.9486 AND 13.0026
  AND lng BETWEEN 77.5772 AND 77.6328
  AND haversine_km(lat, lng, 12.9756, 77.6050) <= 3;   -- exact test on the survivors

The circle fills π ÷ 4 ≈ 79% of its box. The bigger problem is that a B-tree orders rows along one dimension: an index on lat finds every row in a band 6 km tall across the whole city, then checks longitude. A composite (lat, lng) index is no better, because once the first column is a range the second cannot shorten the scan (composite index design). At 40 restaurants per km²:

• the band: 6 km × 40 km = 240 km², so 9,600 rows read;
• the box: 36 km², 1,440 rows;
• the circle: π × 3² ≈ 28 km², so 1,130 rows kept.

You gain a 50-fold cut in rows touched (500,000 to under 10,000) with ordinary indexes. You pay with waste that grows with the width of your data, not your radius. It breaks in big, dense areas, and on “nearest 20”, where you must guess the box size and retry.

Say: “A B-tree is one-dimensional, so a lat/lng box reads a whole latitude band. I want nearby on the map to mean nearby in the index.”

Level 2: geohash cells

A geohash interleaves longitude and latitude bits into one sortable base-32 string (geospatial indexes walks through the encoding). MG Road in Bengaluru (12.9756°N, 77.6050°E) becomes tdr1vf…. A prefix is a cell: every point starting tdr1v lies in one rectangle, and each extra character splits it into 32. A cell is a key range: in an indexed column, a Redis score or a DynamoDB sort key, “everything in tdr1v” is one scan, gh >= 'tdr1v' AND gh < 'tdr1w'.

The edge problem. Nearby points need not share a prefix. A restaurant 700 m east of MG Road sits in tdr1y and shares only tdr1 with you, while a place 4 km west shares your whole cell. So a geohash query reads your cell and its 8 neighbours, then filters by exact distance.

Picking a precision. The 3 × 3 read is safe when a cell is at least as wide as the radius: length 5 for 3 km. Finer cells waste less area but need more lookups. Sizes come from the Elasticsearch geohash table, widths scaled by cos 13°:

Length 6 is the sweet spot here; cells adjacent in key order merge into one range scan, so 55 cells means far fewer scans.

Redis packages the 3 × 3 version: GEOADD stores a 52-bit geohash as a sorted-set score, and GEOSEARCH scans the 1 + 8 cells around the shape, dropping members outside it by haversine distance (up to 0.5% error, per the docs).

GEOADD rest:blr 77.6050 12.9756 r:1042 77.6115 12.9756 r:2210   # longitude first
GEOSEARCH rest:blr FROMLONLAT 77.6050 12.9756 BYRADIUS 3 km ASC COUNT 20 WITHDIST

One trap: COUNT 20 without ANY still finds and sorts every match in the area, so cost follows the matches, not the 20.

You gain 2-D locality on any ordered store, and the cell doubles as a shard key. You pay with neighbour bookkeeping and fixed cells that narrow away from the equator. It breaks on density skew: at 200 per km² a length-5 cell holds about 23 km² × 200 ≈ 4,600 restaurants, while an outskirts cell may hold none. The radius holding the nearest 20 is about 180 m in the centre (20 ÷ 200 = 0.1 km²) but 1.8 km at 2 per km²: a 100-fold change in density is a 10-fold change in radius, and no single precision suits both.

Say: “I key restaurants by geohash, read my cell and its 8 neighbours, and filter by exact distance.”

Level 3: a quadtree that adapts to density

A quadtree splits any square holding more than K points into four, until every leaf holds K or fewer: small leaves where it is busy, big ones where it is empty. With K = 100, a leaf covers about 0.5 km² in the 200-per-km² centre and 50 km² on the 2-per-km² outskirts. For the nearest 20, visit leaves in order of distance, keep the best 20 points so far, and stop when the next leaf is farther than the 20th point: a handful of leaves wherever you are (geospatial indexes details this best-first search).

The whole country fits in application memory: 500,000 restaurants × about 32 bytes ≈ 16 MB, so every search server holds a copy, rebuilt nightly and patched from a change stream.

You gain density adaptivity and fast nearest-K with no database on the query path. You pay with a structure you build and sync yourself. It breaks on moving points: 250,000 updates a second would each delete and re-insert a point, sometimes splitting or merging nodes, in a tree thousands of queries are reading. Fixed cells cope better: an update usually stays in the same cell.

Say: “For static places in memory, a quadtree adapts to the dense centre. Not for drivers.”

Level 4: a spatial index in the database

Databases ship 2-D indexes. In PostgreSQL with PostGIS, a GiST index on a geometry or geography column is an R-tree: nested bounding rectangles that adapt to density like a quadtree but stay balanced on disk. Queries run in two passes: the index finds rectangles that might match, then an exact test runs on the survivors.

CREATE TABLE restaurants (
  id       bigint PRIMARY KEY,
  name     text NOT NULL,
  is_open  boolean NOT NULL,
  geog     geography(Point, 4326) NOT NULL   -- longitude, latitude on WGS 84
);
CREATE INDEX restaurants_geog_idx ON restaurants USING GIST (geog);

-- open restaurants within 3 km of MG Road, nearest first
SELECT id, name,
       ST_Distance(geog, 'SRID=4326;POINT(77.6050 12.9756)'::geography) AS metres
FROM restaurants
WHERE is_open
  AND ST_DWithin(geog, 'SRID=4326;POINT(77.6050 12.9756)'::geography, 3000)
ORDER BY geog <-> 'SRID=4326;POINT(77.6050 12.9756)'::geography
LIMIT 20;

Three details interviewers like:

• ST_DWithin on geography takes metres and includes an index-assisted bounding-box test.
• <-> gives index-assisted nearest-neighbour ordering, only in ORDER BY and against a constant; for geography it uses sphere distance. Drop ST_DWithin and you get “nearest 20 at any distance”.
• On geometry, distances are in the coordinate system’s units: degrees, for plain latitude and longitude.

Elasticsearch does the same job for search-shaped queries such as “biryani, open now, within 3 km”: map the location as a geo_point, filter with geo_distance and sort by _geo_distance. Distances use the sphere (arc) by default; plane is faster but inaccurate over long distances and near the poles.

{
  "query": { "bool": {
    "must":   { "match": { "cuisine": "biryani" } },
    "filter": [
      { "term": { "is_open": true } },
      { "geo_distance": { "distance": "3km", "location": { "lat": 12.9756, "lon": 77.6050 } } }
    ]
  } },
  "sort": [ { "_geo_distance": { "location": { "lat": 12.9756, "lon": 77.6050 }, "order": "asc", "unit": "km" } } ],
  "size": 20
}

“Just use PostGIS or Elasticsearch” is right when points are static or slow-changing, you need filters, text or polygons alongside distance, and writes are modest. Restaurants qualify: 500,000 × 10 changes a day ÷ 86,400 s ≈ 60 writes a second; for 5,000 searches a second, add replicas and cache popular cells (scaling reads). Most nearby-places designs should stop here.

You gain a mature index that handles density, edges, polygons and nearest-K beside the rest of your data. You pay with a heavier engine per query. It breaks on high-rate updates: each driver ping as an UPDATE writes a row version, an index entry and WAL, and leaves a dead row for vacuum. One primary takes about 18,000 single-row writes a second in the scaling writes cost model; 250,000 pings a second is 14 times that.

Say: “Restaurants are static, so PostGIS with a GiST index, ST_DWithin and KNN ordering, or Elasticsearch if search needs text. Neither is where driver pings go.”

Level 5: S2 and H3 cells

Geohash cells distort with latitude, its Z-order jumps (tdr1v and tdr4j touch on the map but sit far apart in key order), and it has seams at the poles and the 180° meridian. S2 and H3 fix these, each turning a location into a 64-bit cell ID for any index or key-value store; internals are in geospatial indexes.

• S2 (Google) projects the sphere onto a cube’s six faces, splits square cells four ways down to level 30 (about 1 cm) and numbers them along a Hilbert curve. Children nest exactly, and any region becomes a few cells of mixed sizes, each one contiguous ID range.
• H3 (Uber) tiles the sphere with hexagons at 16 resolutions, each about a seventh of the area of the last: 5.16 km² on average at resolution 7, 0.74 km² at 8, 0.105 km² at 9. All six neighbours are equally far away, so a k-ring (cells within k steps: 1 + 3k(k + 1), so 7, 19, 37) approximates a circle well. Children only approximately fit their parent, and each resolution has 12 pentagons, placed in the oceans.

Cells earn their place in four jobs:

• Neighbour search for moving points. Key each driver by a resolution-8 hexagon; a k-ring of 2 is 19 × 0.74 ≈ 14 km², roughly a 2 km radius.
• Aggregation. Uber’s H3 post describes measuring supply and demand per hexagon to set surge prices: a GROUP BY on the cell ID.
• Sharding. Coarse cells map to shards, so each query touches one or two (database sharding).
• Geofencing. Cover each delivery zone with cells once; “which zones contain this point?” becomes one lookup. A 5 km zone is π × 5² ≈ 78.5 km², about 106 resolution-8 cells, so 500,000 restaurants need 500,000 × 106 ≈ 53 million entries. Only edge cells need an exact polygon test.

You gain uniform, sphere-aware IDs for keys, shards and buckets. You pay with a library and unreadable IDs. They break as a complete answer: a cell system says which bucket a point is in, not where to keep buckets that change 250,000 times a second.

Say: “H3 for anything I aggregate or ring-search, like surge or nearby drivers; S2 when I need exact nesting and range scans. Either makes a good shard key.”

Level 6: moving objects at scale

Drivers flip the problem from reads to writes and freshness:

• Don’t write each ping to the index database: 250,000 updates a second, each useful for about 4 seconds. Uber’s Ringpop post says database storage “would be useless” for such fleeting data, so its Geospatial service holds it in memory on workers placed by consistent hashing. Send the full trail to a log for trip history (scaling writes).
• Keep only the latest position, in memory, sharded by cell: one Redis geo set per length-5 cell, such as geo:{tdr1v}. One key per city would be a hot key taking Bengaluru’s 25,000 updates a second; by cell it is about 1,500 ÷ 23 ≈ 65 keys at about 400 a second each, spread over shards by hash slot.
• Make each ping cheap. At 30 km/h a driver moves about 33 m in 4 seconds, against a 4.8 km cell, so most pings are one GEOADD to the same key plus a last-seen update; only on crossing an edge do you also ZREM from the old key. A small Lua script does this atomically and ignores pings older than the stored one.
• Expire the silent. Sorted-set members can’t have their own TTL, so keep a companion set, seen:{tdr1v}, scored by last-ping time, and let a sweeper remove drivers silent for 30 seconds from both; the shared hash tag keeps both keys on one shard.
• Size it. At roughly 100 bytes per sorted-set entry (an estimate), two entries per driver is about 200 MB per million drivers. The pressure is commands: about 2 per ping × 250,000 = 500,000 a second, or 5 Redis primaries at the 100,000-per-second planning figure from scaling reads. Plan 8 for headroom.

On the read side, three habits matter.

Expand the ring. Ask for available drivers within 1 km; if fewer than 20 come back, try 2 km, then 4 km, and stop at 8 km. At 20 available drivers per km² in the centre, π × 1² × 20 ≈ 63, so the first ring is enough; at 0.5 per km² on the outskirts you need π r² × 0.5 ≥ 20, so r ≥ 3.6 km: the third ring. Each ring reads at most 9 cell keys in parallel.

Rank by ETA, not distance. A driver 600 m away across a railway line, with the nearest crossing 2 km off, can be 8 minutes away; one 1.5 km away on the same road, 4 minutes. Send the 20 candidates to the routing engine for an ETA matrix and choose from that.

Claim before you offer. Two riders can pick the same driver at once. Change the driver’s status atomically from available to offered with a short lease, say 15 seconds, before sending the offer; if the compare-and-set fails, take the next candidate (contention and double booking). The rider’s map of nearby cars is a separate, lossy stream (real-time updates).

1. The rider app asks matching for cars near the pickup.
2. Matching runs GEOSEARCH on nearby cell keys at 1, 2, then 4 km until it has about 20 available drivers.
3. The routing engine returns road ETAs; matching sorts by them.
4. Matching claims the best driver, then sends the offer.

You gain sub-millisecond geo queries over live data, with writes of one or two in-memory operations. You pay with data you can lose: if a shard dies, its drivers vanish until their next ping rebuilds it. It breaks mostly in operations: hot cells around a stadium after a match, and pickups whose rings fan out across shards.

Choosing an approach

Most designs combine two rungs: a spatial index for static places and a live index for moving things.

Which classic problems use it

Common mistakes

• Euclidean distance on raw degrees. sqrt(Δlat² + Δlng²) treats a degree of longitude as 111 km; in Delhi it is 97 km, at 60°N about 55 km. Use haversine, or let the store do it.
• Reading one geohash cell, and missing the restaurant 100 m away across an edge. Read the 8 neighbours, or cover the circle.
• The wrong precision. Too fine reads about 1,300 cells at length 7 for 3 km; too coarse reads the whole city at length 4.
• Writing every driver ping into PostGIS or any disk index.
• Ranking by straight-line distance when rivers, railway lines and one-way streets decide the real wait.
• No expiry. A driver whose app was killed stays on the map until a sweeper removes them.
• Swapping latitude and longitude. Redis, GeoJSON and WKT take longitude first; Elasticsearch’s "lat,lon" string takes latitude first. Swap MG Road’s pair and it lands in the Arctic, near Svalbard.
• Ignoring the antimeridian and the poles in a global product: a box crossing 180° (Fiji, the Bering Strait) must be split in two, and Redis rejects latitudes beyond ±85.05°.

Cheat sheet

• 1° of latitude ≈ 111 km; 1° of longitude ≈ 111 km × cos(latitude): 108 km in Bengaluru, 97 km in Delhi.
• Candidates ≈ density × π r²: 40 per km² × 28 km² ≈ 1,130 within 3 km.
• Radius holding K points ≈ √(K ÷ (π × density)): 180 m for 20 at 200 per km².
• H3 k-ring = 1 + 3k(k + 1) cells: 7, 19, 37.
• Updates per second = online drivers ÷ ping interval: 1,000,000 ÷ 4 s = 250,000.

How to say it in the interview

“First, are the points static or moving? Restaurants are static, about 500,000 changing a few times a day, so PostGIS: a GiST index on a geography column, ST_DWithin for the 3 km radius and the KNN operator for nearest-first, with replicas and a cache of popular cells; Elasticsearch if search needs text. Drivers move: a million phones every 4 seconds is 250,000 updates a second, so pings never touch that database. A location service keeps each driver’s latest position in Redis geo sets keyed by geohash cell, sweeps out drivers silent for 30 seconds, and needs about 8 shards. To match, I search 1, 2, then 4 km until I have 20 available drivers, rank them by road ETA, and claim the best one atomically.”

Why not compute the distance to every row? It costs N times the per-row work on every query: 500,000 × 1 µs is half a second of CPU, about 30 searches a second per server. Fine for a 300-store chain only.

How do you choose a geohash precision? Take the longest geohash whose cell is still at least the radius and read the 3 × 3 block: length 5 for 3 km, about 7× the circle’s area. If that reads too many rows in dense areas, go one level finer and read the 55 or so cells that touch the circle.

Why not keep driver locations in PostGIS? Each of 250,000 updates a second writes a row version, an index entry and WAL, for data stale within seconds. Keep the latest position in memory and the trail in a log.

How do you stop two riders getting the same driver? The geo index only proposes candidates. The driver’s status is the truth: change it from available to offered with a compare-and-set and a short lease before sending the offer, and move to the next candidate if it fails.

Why do ride-hailing systems like hexagons? All six neighbours of a hexagon are equally far away, so k-rings approximate circles and smooth evenly for surge maps; squares have neighbours at two distances. For exact nesting and range scans, S2 fits better.

Where to go next

• Geospatial indexes: geohash, quadtrees, S2 and H3: the internals behind rungs 2, 3 and 5.
• Database indexes and composite index design: why a B-tree is one-dimensional.
• Redis: sorted sets, geo commands and clustering.
• PostgreSQL and Elasticsearch: the two default homes for static places.
• Database sharding and consistent hashing: spreading cells over machines.
• Scaling writes and scaling reads: the ping write path and the place read path.
• Real-time updates: pushing nearby cars to the rider’s map.
• Contention and double booking: claiming a driver exactly once.
• Design Uber and design food delivery: the full designs that use rungs 4 to 6.

References and further reading

1. Redis documentation: GEOADDredis.ioA geo set is a sorted set whose scores are 52-bit interleaved geohashes; radius queries scan the 1 + 8 cells around the shape; haversine distances with up to 0.5% error; latitudes limited to ±85.05°.
2. Redis documentation: GEOSEARCHredis.ioRadius and box searches, ASC ordering, and why COUNT without ANY still examines and sorts every match in the area.
3. PostGIS documentation: ST_DWithinpostgis.netIndex-assisted within-distance test; geography distances are in metres, geometry distances in the units of the coordinate system.
4. PostGIS documentation: the <-> distance operatorpostgis.netIndex-assisted nearest-neighbour ordering, used only in ORDER BY against a constant, with sphere distance for geography.
5. PostGIS workshop: Spatial indexingpostgis.netGiST R-tree indexes over bounding boxes, and the two-pass filter: an approximate index test, then an exact test on the survivors.
6. Elasticsearch reference: Geo-distance queryelastic.coRadius filters on geo_point fields, with arc distance by default and a faster but less accurate plane option.
7. Elasticsearch reference: Geohash grid aggregationelastic.coGeohash cell dimensions for lengths 1 to 12, measured at the equator.
8. H3 documentation: Tables of cell statistics across resolutionsh3geo.orgAverage hexagon areas and edge lengths per resolution, and the 12 pentagons present at every resolution.
9. H3: Uber’s Hexagonal Hierarchical Spatial Index (Uber Engineering)uber.comWhy hexagons (one neighbour distance), one-seventh area per finer resolution, k-rings, 64-bit IDs, and surge pricing measured per hexagon.
10. How Ringpop from Uber Engineering helps distribute your applicationuber.comUber’s Geospatial service keeps every online driver’s location in memory across consistently hashed workers; its predecessor searched every car.