Geospatial search

A food delivery app needs to show the closest restaurants to a given lat/long. Ten million restaurants in the database, a query per page load, sub-100ms latency. This is the classic nearest-neighbor problem.

bounding-box
sql
SELECT id, name, latitude, longitude
FROM restaurants
WHERE latitude  BETWEEN $1 AND $2
  AND longitude BETWEEN $3 AND $4
ORDER BY (latitude - $5) * (latitude - $5)
       + (longitude - $6) * (longitude - $6)
LIMIT 20;

Compute a bounding box around the user and filter by lat/long range. Simple and fast without PostGIS.

postgis-knn
sql
SELECT id, name,
       ST_Distance(location, ST_MakePoint($1, $2)::geography) AS distance_m
FROM restaurants
ORDER BY location <-> ST_MakePoint($1, $2)::geography
LIMIT 20;

With PostGIS, the GIST index on geography turns nearest-neighbor into a single operator.

The bounding box version does not need PostGIS at all. It uses a simple B-tree index on latitude and longitude and filters with a rectangle. Fast for most cases but wrong near the poles and the international date line. The PostGIS version handles the edge cases correctly and uses a specialized GIST index for true nearest-neighbor queries. Use bounding box for simple internal tools. Use PostGIS when correctness and scale both matter.

Quiz: Quiz

Loading practice…

Checkpoint: High scale checkpoint

Loading practice…