Data & storage / 3 / 15
Geo search: who is nearby
A taxi app must find the ten nearest free drivers around a rider, while 50 000 drivers send their position every 4 seconds. Why a normal index does not help, and how geohash, neighbour cells, a quadtree and S2/H3 cells answer "who is within 2 km" in milliseconds.
- 14 min
- Intermediate
- 11 steps
- Search p95
- 900 ms
- Drivers read
- 50 000
- Nearest missed
- 0 %
- Ghost drivers
- 0
- request
- reply
- redelivery
- duplicate
- lost
Numbers are a model scenario, not measurements
The real request
Matching API → Drivers DBRequest
SELECT id, lat, lng FROM drivers
WHERE status = 'free'
AND distance_km(lat, lng, 41.3110, 69.2797) < 21
ORDER BY distance_km(lat, lng, 41.3110, 69.2797)
LIMIT 10;
Response
10 rows, Seq Scan on drivers2
rows examined: 50000, time: 780 ms3
distance_km— A function of the row's values. No ordinary index can answer it in advance.Seq Scan— The plan reads the whole table, row by row.examined— 50 000 rows read to return 10. Almost all of the work is wasted.
Build it yourselfCheat sheetCompare lessons
Course: 74 lessons
01 Foundations
02 Scaling
03 Data & storage
04 Communication
05 Reliability
06 Architecture
07 Security
08 Shipping
09 Whole systems
10 Business processes
11 Case studies