Part 3 of 8 · 2 min read
First design
A SQL query on a table.
APIs. GET /v1/search/nearby takes latitude, longitude and an optional radius (default 5,000 meters), and returns a list of places, usually paginated. A second set of calls handles one place: get details, add, update and delete.
Parts. A load balancer. A location-based service that finds nearby places: it only reads, has high traffic, and is stateless, so more servers can be added at peak. A business service for owner changes (few writes) and detail views (many reads). A database cluster with a primary for writes and replicas for reads. Replicas lag a little behind, which is fine because place data need not be real time.
Data. A business table with an id, address, city, country, latitude and longitude.
First search. Draw a square around the user, and ask the database for every place with latitude and longitude inside it.
SELECT id FROM business
WHERE latitude BETWEEN my_lat - r AND my_lat + r
AND longitude BETWEEN my_long - r AND my_long + r
This is slow. Without an index it reads the whole table. With one index on each column, the database finds all places in the latitude band, and all places in the longitude band, and then must intersect two large sets. A normal index helps with one dimension only. The idea needed is to map two-dimensional data to one dimension.
A worked example (made up). A city has 5 million places. The latitude band holds 200,000 of them and the longitude band holds 250,000. The database must compare these two lists to find the few hundred that are in both. This is far more work than reading only the few hundred.
Common mistake
Believing that two single-column indexes make a two-dimensional query fast. Each index narrows only one direction. The intersection of two big sets is still big.
Check yourself: 1. What does the location service do, and what does it not do? 2. Why do two separate indexes not solve the problem? 3. What is the goal of a geospatial index?