The whole course ▾

System Design · Lesson 27 of 39 · Week 6

Geospatial: finding what's nearby

Updated 22 Oct 2026 · By Akshay, software engineer, India · 5 min read

An order is ready at a restaurant in Bengaluru. Which of QuickBite's 300,000 riders are within two kilometres? Today: geospatial search.

The video for this lesson is coming soon.

New System Design videos go up at 6 pm. Subscribe on YouTube so you don't miss it.

Got a doubt? Ask in the comments under the video.Subscribe

QuickBite in this lesson

Finding riders near a restaurant.

QuickBite is the food delivery app we grow through the course, from one server to millions of orders.

Riders near a restaurant

Riders near a restaurant
Restaurant
order ready
Matching
service
Locations DB
300,000 riders
find riders
lat and lng ranges
two ranges, one index
75,000 updates a second

In lesson eighteen, every rider's phone sent its GPS position every four seconds. Today we put those positions to work.

An order is ready at a restaurant. The matching service needs every free rider within two kilometres, and it needs them fast, because the food is getting cold. Rider positions live in a locations DB: one row per rider, with a latitude and a longitude, rewritten every four seconds by every one of three hundred thousand riders. And matching runs for every order, thousands of times a minute at dinner.

The obvious query: latitude between this and that, and longitude between this and that. With an index on latitude, the database finds every rider in a thin strip right across the country, then checks each one's longitude. An index helps with one range, not two at once. And the table takes seventy-five thousand updates a second, three hundred thousand riders every four seconds. We need a way to turn two dimensions into one.

Geohash: a map as a string

Geohash: a map as a string
How a geohash works
1
Cut the map in half: east or west?
2
Cut again: north or south?
3
Keep alternating; 5 bits per letter
4
6 letters ~ a box about 1 km wide
WHY IT HELPS
Twodimensionsbecome
onestring:"ridersnear
me"becomesaprefix
lookup.

The classic trick is to cut the map into boxes, and give every box a name that reads like a string.

A geohash turns a location into a short string. Cut the world map in half, east and west, and note which half we're in: a zero or a one. Then cut that half again, north and south, and note another bit. Keep alternating, and every five bits become one letter or digit. Six characters describe a box roughly a kilometre wide. And here's the key property: places close together usually share the same first characters.

Now store each rider's geohash in an ordinary indexed column. Finding the riders in a box is a prefix search, which a B-tree from lesson ten does perfectly. Or keep one set per box in memory, holding the riders inside it, updated as they move. Either way, two awkward ranges became one quick lookup. At moderate scale, Postgres users can also reach for PostGIS, an extension with real spatial indexes.

The edge problem

The edge problem
Search nine cells, not one
1
Find the restaurant's cell
2
Add the 8 cells around it
3
Gather riders from all 9
4
Filter by real distance; nearest first
CHOOSE THE CELL SIZE
Cellsaboutthesizeof
thesearchradius:too
big,toomanyriders;too
small,toomanycells.

There's one trap, and interviewers love asking about it.

A rider fifty metres away, but across a cell boundary, can have a completely different geohash. So never search just one box. Find the restaurant's cell, add the eight cells around it, and gather the riders from all nine. Then compute the real distance to each one, keep those within two kilometres, and sort them, nearest first. Nine quick lookups, and a small filter in memory. It's a pattern you'll reuse in every nearby search.

And choose the cell size to match the search. If cells are much bigger than two kilometres, the nine cells hold thousands of riders to filter. If they're much smaller, you need dozens of cells to cover the circle. Cells roughly the size of the search radius keep both numbers small.

Uneven cities

Uneven cities
Fixed grid, like geohash
The same size everywhere
Crowded cells downtown
Nearly empty cells outside
Quadtree
Splits a square when it's crowded
Small squares downtown, big outside
Each square holds about the same
AND H3
Uber'sH3coversthe
earthinhexagons:every
neighbouristhesame
distanceaway.

Geohash cells are all the same size. But riders aren't spread evenly: thousands in central Bengaluru, a handful on the edge of town.

A fixed grid uses the same cell size everywhere, so downtown cells are crowded and outer cells are nearly empty. A quadtree adapts. Start with one square covering the city. When a square holds more than, say, a hundred riders, split it into four smaller squares, and keep splitting wherever it's crowded. Downtown ends up with tiny squares, the outskirts with big ones, and every square holds roughly the same number of riders. It's kept in memory, and adjusted as riders move.

One more, worth knowing by name: H3, which Uber open-sourced, covers the earth in hexagons, at sixteen different sizes. With hexagons, all six neighbours sit the same distance from the centre, unlike squares, whose corner neighbours are further away. That makes rings of nearby cells, and pricing by area, cleaner. Ride-hailing and delivery apps use it widely.

When everything moves

When everything moves
Rider app
Location
service
Redis geo
index
cell -> riders
Matching
service
GPS every 4 s
update
position
1
riders near X
2
CACHE THE ANSWER
Cache"restaurantsnear
thiscell":millionsof
customersaskthesame
question.

Restaurants stay put. Riders don't. So the index has to move with them.

Every four seconds, the rider app sends a position to the location service, which updates the rider in a Redis geo index. Redis supports this directly, with geo commands built on geohashes, so a nearby search is one command. The matching service asks it for riders near the restaurant, and gets an answer in about a millisecond. Positions are only seconds old anyway, so keeping them in memory, rather than in a disk database, is exactly right.

And the customer side is easier still. Customers browsing restaurants near them ask the same question again and again, and restaurants don't move. So cache the answer per cell: restaurants near cell X, refreshed every few minutes. Thousands of customers in the same neighbourhood share one cached result. Riders, which move, are never cached like this.

In the interview

In the interview
SAY THIS IN THE INTERVIEW
GeohashorH3cells,in
memory;searchthecell
anditsneighbours,then
filterbyrealdistance.
Follow-ups to expect
->
Why not indexes on lat and
lng?
->
What about cell edges?
->
Downtown cells are crowded?
THE COMMON MISTAKE
Searchingonecell,
andmissingtherider
justacrosstheline.

Nearby search sits at the heart of ride-hailing, delivery, maps, dating apps, and Yelp.

Say it like this: split the map into geohash or H3 cells, keep moving things in an in-memory index, search the target's cell and its neighbours, then filter by real distance and sort. Then say how often positions update, because that number decides where the index can live.

Then expect these. Why not indexes on latitude and longitude? An index helps with one range, not two. What about cell edges? Search the neighbouring cells too, then filter. And downtown cells are crowded? Use smaller cells there: a quadtree, or a finer H3 resolution in busy areas. And how is one rider chosen? Rank the nearby candidates by distance and direction of travel, then offer the order to the best one, which leads straight into tomorrow's problem.

The common mistake is searching only the cell the restaurant is in. The nearest rider is often just across the boundary. Always include the neighbours.

Quick check

Quick check
?
300,000 riders each send a
position every 4 seconds.
How many updates a second?
75,000 a second.
?
Why search the 8
neighbouring cells, not just
the restaurant's own?
Because a nearby rider can sit
just across a cell boundary, in a
different cell.
Remember
Two ranges are slow: use cells
Search the cell and its
neighbours
Moving things live in memory
Quick check

300,000 riders each send a position every 4 seconds. How many updates a second?

Show the answer

75,000 a second.

Quick check

Why search the 8 neighbouring cells, not just the restaurant's own?

Show the answer

Because a nearby rider can sit just across a cell boundary, in a different cell.

Remember: two ranges at once are slow, so turn the map into cells. Search the cell and its neighbours, then filter by real distance. And things that move every few seconds live in memory. Tomorrow, two riders tap accept on the same order, at the same moment.

Practise with flashcardsYour progress stays on this device.
New System Design videos at 6 pm

Lessons on weekdays, the week's revision on Saturday, a mock interview on Sunday.