Loading...
Loading...
Spatial indexing for location-based services like Uber and Yelp
Snowflake sorts one dimension into 64 bits and UUIDv7 keeps the sort at 16 bytes with zero worker slots, yet every scheme orders a single line. Finding drivers within 2km on millions of latitude-longitude rows cannot scan all. Geohashing, meaning encoding 2D position as a string where shared prefixes mean shared cells, turns proximity into prefix search a B-tree, meaning an ordered string index, answers with range scans. Nearby points share prefixes, so one indexed column prunes millions to hundreds before exact math confirms.
lat/lng → interleave bits → base32 string (37.7749,-122.4194) → 9q8yyk... (precision 5 ≈ 5km cell, 6 ≈ 1.2km, 7 ≈ 150m) Nearby points share prefix: 9q8yyk* are all in same neighborhood
Naive radius search computes Haversine distance, meaning great-circle distance over the earth, per row, which scans everything. Geohash instead halves longitude then latitude ranges alternately, appending one bit per halving, then groups bits five-to-one into base32. Each prefix is a coarser cell; each added character refines 32x. Quadtree, meaning recursive quadrant subdivision holding points in leaves, adapts instead to density such as dense cities versus sparse deserts. Like a mail system routing by zip prefix before checking the street address, prefix prunes and math decides.
Encode by repeatedly halving lat/lng ranges and appending bits: even bits for longitude, odd for latitude, then base32. Prefix means coarser cell; adding characters refines. Edge case: points across cell borders share short prefix but are close; must query 8 neighbors.
Recursively split space into quadrants; leaf holds points. Good for dynamic density (city dense, desert sparse) vs fixed geohash grid. H3 from Uber, a ride-hailing company, uses hexagons for uniform neighbor distance; S2 from Google uses Hilbert curves, meaning locality-preserving space-filling paths, for boundary locality.
Every geohash character adds 5 bits alternating longitude, latitude, longitude, shrinking cells roughly 32x. Four characters span a metro near 39km by 19km, five a neighborhood near 4.9km, six city blocks near 1.2km by 0.6km, seven a building near 153m, eight a storefront near 38m by 19m. A 2km rider search therefore indexes at precision 6, fetches its cell plus 8 neighbors in 9 prefix scans, then Haversine-filters candidates. The index prunes; the math verdicts.
| Chars | Cell size | Feels like |
|---|---|---|
| 4 | ~39km × 19km | Metro area: “drivers in the Bay” |
| 5 | ~4.9km × 4.9km | Neighborhood: first filter for 5km radius |
| 6 | ~1.2km × 0.6km | City blocks: 2km search fetches these + neighbors |
| 7 | ~153m × 153m | Building: pickup-point precision |
| 8 | ~38m × 19m | Single storefront: track a courier, not a fleet |
Worked query: 2km radius around the rider → index at precision 6 (cells ~1.2km), fetch the rider cell plus 8 neighbors (9 prefix scans), then filter all candidates by exact Haversine distance. The index prunes millions to hundreds; the math, not the prefix, decides who is actually near.
Two scooters 50 meters apart can hash to neighboring prefixes across a cell boundary, so pure prefix search calls them distant while a matching-prefix driver 2km away looks near. At high latitudes longitude degrees shrink, stretching fixed-precision cells into slivers with uneven neighbor distances. The ritual is always 9 cells plus exact filter at precision sized so the radius covers 1 to 2 cells, capped per cell so one downtown cell cannot return 50,000 drivers. H3 hexagons from Uber, a ride-hailing company, equalize neighbor distances; S2 Hilbert curves from Google preserve locality across boundaries at trickier encode cost.
Always query the target cell plus its 8 neighbors, then exact-filter. Better: choose precision so the radius covers 1–2 cells (radius 2km → precision 5 or 6, never 8; hundreds of tiny cells mean hundreds of range scans). Cap results per cell so one dense downtown cell cannot return 50,000 drivers.
H3 from Uber, a ride-hailing company, tiles the earth in hexagons where every neighbor sits equidistant, unlike rectangles with far corners. S2 from Google walks a Hilbert curve so nearby points stay nearby across boundaries. Reach for them when density varies wildly or k-nearest traversal matters more than prefix simplicity.
Take latitude 37.7749, longitude minus 122.4194. Halve longitude range minus 180 to 180 and record the half: one bit. Halve latitude minus 90 to 90: second bit. Alternate twenty-odd times, then read groups of five as base32 over an alphabet skipping confusing characters. The first character alone narrows to the Bay Area; dropping the last zooms out 32x, appending zooms in 32x.
lng −122.4194 in [−180,180): bit1 = 0 (west half) → [−180,0) next: −122.4194 in [−180,0)? bit = 0 → [−180,−90) ... (repeat, alternating lat) bitstream (lng,lat,lng,lat...): 0 1 1 0 0 | 1 1 1 0 1 | ... groups of 5 → base32 alphabet "0123456789bcdefghjkmnpqrstuvwxyz" (no a,i,l,o) → "9q8yyk...", first char "9" already narrows to the SF Bay Area dropping the last char zooms out 32x; appending one zooms in 32x.
Five bits per character keeps strings short (precision 7 needs 35 bits; 7 chars, not 21 decimals), and the alphabet skips vowels and lookalikes so a driver reading a cell code over the phone cannot confuse it. Every character is one zoom level your B-tree can prefix-scan.
Plain geohash interleaving is a Z-order curve, meaning simple bit interleave that jumps at quadrant seams and causes border misses. Hilbert curves as in Google S2 rotate each quadrant so the path never jumps: neighbors stay neighbors at trickier encode cost. Shared prefix implies candidates; Haversine confirms.
Two million drivers updating every 5s means 400k writes per second against constant nearest-20-within-3km queries. The write path upserts one row per driver keyed by geohash-7 plus driver_id, sharded by driver_id since the secondary index never contends. The read path scans 9 prefixes at precision 6 and Haversine-filters to 20. Nine scans times 50 rows is 450 rows per query in milliseconds versus millions scanned. Redis GEO commands in the in-memory store mirror it: GEOADD stores interleaved scores in a sorted set, GEORADIUS walks score ranges.
Write: UPDATE drivers SET geohash7 = encode(lat,lng), lat, lng, updated_at
WHERE driver_id = ? (400k/s; shard by driver_id, index is secondary)
Read: cell = encode(rider, precision 6)
candidates = scan(prefix=cell) + scan(8 neighbors) // 9 range scans
ranked = candidates.map(haversine).filter(d ≤ 3km).take(20)
Cost: 9 prefix scans × ~50 rows each ≈ 450 rows read per query; milliseconds.
Redis path: GEOADD drivers lng lat id (sorted-set score = 52-bit geohash int)
GEORADIUS ... COUNT 20; same idea, in-memory.Friday night packs 40,000 drivers into one downtown geohash-6 cell against 200 suburban. Sharding by cell prefix makes downtown the hot shard doing all writes while ten suburban shards idle. Subdivide dense cells by appending a seventh character until each shard holds bounded driver counts rather than bounded areas: one 40k cell becomes 32 children near 1.2k each, spreading heat 32 ways. Reads fan out to more prefixes but each returns fast, so split until p99 flattens.
Naive shard key: geohash6 → downtown cell 9q8yyk = 40k drivers (hot), rural = 200 (idle) Split: shard key = geohash7 for cells over 5k drivers 9q8yyk splits into 32 geohash7 children ≈ 1.2k drivers each; heat spreads 32 ways quadtree logic on a geohash index: split the cell, not the table Read cost: radius query now fans out to MORE shard prefixes, but each returns fast. scatter (more shards touched) vs hot-spot (one shard drowns): split until p99 flattens.
Delivery zones are polygons such as Mission district boundaries, not circles. Covering turns any polygon into minimal cell prefixes: cover the bounding box coarse at precision 5, subdivide border cells to 7, keep fully-inside cells coarse, drop fully-outside ones. The database runs one prefix scan per covering cell then exact point-in-polygon filters. S2's GetCovering, Google's Hilbert-cell covering routine, does exactly this. Cap near 50 cells: 200 prefixes is a full scan in disguise, so coarsen borders and let exact filtering earn its keep.
Finer border cells hug the boundary (fewer false candidates) but multiply range scans, so cap the covering at ~50 cells. A zone query touching 200 prefixes is a full-table scan in disguise; coarsen the border and let the exact filter earn its keep.
Surge pricing must catch drivers crossing the stadium zone among 2M drivers at 5s cadence, meaning 400k fixes per second. Per-fix polygon checks need a fleet; cell containment needs fractions of a core. Precompute covering once: interior cells answer IN with no math, outside cells answer OUT by hash lookup, and only 5% border fixes pay exact point-in-polygon. Encoding plus set lookup runs near a microsecond each, so 400k fixes cost 0.4 cores.
Zone covering (computed once per zone change):
interior cells (fully inside): {9q8yyk, 9q8yym, ...} → fix inside = IN, no math
border cells (straddle edge): {9q8yys, ...} → exact point-in-polygon, rarely hit
outside cells: everything else → OUT, one hash lookup
Per-fix cost: encode (ns) + hash-set lookup (ns); polygon math only for ~5% border fixes.
400k fixes/s × ~1μs ≈ 0.4 CPU cores; the naive polygon path needed a fleet.GEOADD never stores latitude and longitude separately: it interleaves them into one 52-bit geohash integer used as the sorted-set score, meaning the ordering key in Redis' in-memory ordered structure. Members order by cell, so radius search computes covering cells then walks score ranges rather than scanning. Coordinates lose a little precision from 64 to 52 bits, still sub-meter and finer than dispatch needs. Shard one sorted set per metro, since a planetary set reintroduces the hot key.
GEOADD drivers -122.4194 37.7749 driver:7 → score = interleave(lat, lng) as 52-bit int nearby scores cluster: same-cell drivers share high bits → skiplist range, not scan GEORADIUS drivers -122.4 37.77 3 km → compute covering cells → ZRANGEBYSCORE per cell precision cost: 52 bits ≈ sub-meter; finer than any dispatch decision needs. Sharding caution: one sorted set per metro; a planetary GEO set reintroduces the hot key.
Driver fixes arrive at 400k per second and each row carries an updated_at timestamp, meaning the last-seen time used to exclude stale drivers. The naive read filters by recency after the prefix scan, which drags dead rows through every query when a third of the fleet goes offline at night. Rejected alternative: an hourly cron DELETE sweeping stale rows. Between sweeps queries still read 44% dead rows, and each sweep deletes 600k rows at once, churning vacuum for hours. The working pattern pairs writes with TTL-aware compaction: upserts carry short expirations in Redis, meaning in-memory entries vanishing automatically, or partition the Postgres table by time so whole stale partitions drop at once. Queries then scan only live candidates, and the exact Haversine filter never pays for drivers who logged off hours ago.
Stale math: 2M drivers, 30% offline > 2min → 600k dead rows per scan set
filter-after-scan: 450 live + 200 dead rows read per query → 44% wasted I/O
TTL path (Redis): GEOADD with EXPIRE 30s per member via sorted-set + sidecar expiry
partition path (Postgres): daily partitions on updated_at, drop partitions older
than 1h from the live view; queries prune dead time before touching prefixes.
Edge case: tunnels and parking garages freeze GPS; last fix lingers inside the zone
and over-counts supply. Require fix age under 30s for dispatch, under 5min for maps.Nine prefix scans return 20 drivers from 2M updating at 400k fixes per second, and TTL compaction keeps dead rows out of every query. Yet the same pipe carries abuse: a scraper at 100k requests per second hides among 200-per-second humans. What charges each principal fairly without throttling a 5,000-person office behind one address?