MapTiler Engineering Blog

Ideas you will meet

Geospatial

Geohash, quadtree, H3 and location search.

What we already know about this

Our own lessons on these ideas. Read them here before you start, so it makes sense.

• Real-World Systems · 10 minDesign a nearby-places service (Yelp)Find restaurants within a few kilometres: geohashes, quadtrees and how to query a map efficiently.Read hereClose

  The problem

  Given a location and a radius, return nearby businesses, ranked and filtered (cuisine, open now, rating). It is read-heavy: millions of searches a day but few changes to the places themselves.

  Estimates: 200 million places at around 1 KB each is about 200 GB, which fits in memory across a few machines. Search traffic might be tens of thousands of queries per second at peak.

  Why not a simple range query

  WHERE lat BETWEEN a AND b AND lon BETWEEN c AND d works in a toy system, but an index serves one dimension well: it returns all rows in the latitude band (a strip around the world), then must filter by longitude. We need an index that understands two dimensions together.

  Idea 1: geohash

  A geohash converts a location into a short string by repeatedly halving the map: each extra character narrows the cell.

  • Locations in the same cell share a prefix, so a string-prefix index can find them.
  • A longer hash means a smaller cell (about 150 m on a side at 7 characters, roughly).
  • Border problem: nearby points can fall in neighbouring cells with different prefixes, so query the cell and its 8 neighbours, then filter by exact distance.

  100%

  Figure SDA-RWS-04-1 · Nearby search with geohash cells · © forcsguy.com

  100%

  Figure SDA-RWS-04-2 · Longer codes mean smaller cells · © forcsguy.com

  Idea 2: quadtree

  A quadtree is a tree where each node is a square region. If a region holds more than N places (say 100), it splits into four child squares, repeatedly. Leaves hold the places.

  • Dense areas (city centres) become deep and fine; sparse areas stay coarse.
  • To search, find the leaf containing the user, then widen to neighbouring leaves until you have enough places.
  • Built in memory, it is fast. Rebuild it periodically (for example nightly) or update incrementally as places change.

  Production systems often use S2 or H3: hierarchical cell systems on a sphere with good neighbour handling.

  100%

  Figure SDA-RWS-04-3 · Building a quadtree: split only where it is crowded · © forcsguy.com

  Architecture

  100%

  Figure SDA-RWS-04-4 · Nearby places architecture · © forcsguy.com

  • The search service looks up candidate place ids by cell, fetches details from a cache or database, filters, ranks and returns a page.
  • Writes (a business is added or moves) are rare. They go to the places database; an index builder refreshes the geo index, and it is fine if that is a few minutes behind.

  Rolling out a quadtree service

  A quadtree lives in each server's memory and is built at start-up. With hundreds of millions of places that can take minutes, during which the server cannot answer. Restarting every server at once would take the whole fleet down. Deploy to a small slice at a time so the rest keeps serving, and only move on when the slice is healthy.

  Scale

  • The index is small enough to replicate on every search node, which scales reads simply.
  • If it grew past one machine, shard by region (cell prefix), taking care with queries that cross shard borders.
  • Cache results for popular areas; most users search the same few hotspots.
  • Filters such as "open now" or cuisine can be applied after the geo lookup, or stored as extra index fields.

  Ranking and details

  Distance is only one signal. Combine rating, popularity, relevance to the query, and personalisation. Keep ranking in a separate step so you can improve it without touching the index.

  Real-world reading

  Related reading

  • H3: Uber's Hexagonal Hierarchical Spatial IndexUber Engineering · UberCase Studies
  • Location Intelligence Resources | Blog & GuidesFoursquare engineers · FoursquareBlogs
  • Optimizing CAL Report Hadoop MapReduce Jobs at eBayeBay engineers · eBayCase Studies
  • MongoDB: Shard KeysMongoDB · MongoDB Inc.Documentation

  Show 6 moreShow fewer

  • Grab EngineeringGrab engineers · GrabBlogs
  • PlanetScale BlogPlanetScale engineers · PlanetScaleBlogs
  • Cross Shard Transactions at 10 Million RPS at DropboxDropbox engineers · DropboxCase Studies
  • MapTiler Engineering BlogMapTiler engineers · MapTilerBlogs
  • Presto at GrabGrab engineers · GrabCase Studies
  • Small Improvements Engineering BlogSmall Improvements engineers · Small ImprovementsBlogs

  Open this lesson with its quiz and exercise