Country lookups in under a millisecond

MapSocket’s geofencing API tags every location update with the country and, for some countries, the state or province it’s in. That powers country allow and block lists, region entry and exit events, and the region fields on each tracked user.

The boundaries come from Natural Earth, loaded into a regions table. The first version of the lookup was the query you’d write first:

SELECT type, code, name FROM regions
WHERE ST_Intersects(geom, ST_SetSRID(ST_MakePoint($1, $2), 4326));

There’s a GiST index on geom. On our test machine it still took about 450 ms per point.

Why the index didn’t help

A spatial index stores each geometry’s bounding box. For a point in Lisbon, the index quickly narrows things down to the regions whose boxes contain Lisbon. That’s Portugal, but also any large country whose box happens to reach that far.

Then PostGIS has to run the exact point-in-polygon test against each candidate, and country polygons are huge. A detailed coastline has tens of thousands of vertices. Testing against a few of those dominates the query time.

Cut the polygons into small pieces

ST_Subdivide splits a geometry into parts with at most a given number of vertices. We store the parts in their own table, each pointing back to its region:

CREATE TABLE region_parts (
  region_id int REFERENCES regions(id) ON DELETE CASCADE,
  geom geometry(Polygon, 4326) NOT NULL
);
INSERT INTO region_parts (region_id, geom)
  SELECT id, (ST_Dump(ST_Subdivide(geom, 128))).geom FROM regions;
CREATE INDEX ON region_parts USING gist (geom);

Now each part has a tight bounding box, the index returns one or two candidates, and each exact test runs against at most 128 vertices. The same lookup takes 0–1 ms.

The coastline problem

Faster lookups surfaced a different issue. Natural Earth’s boundaries are generalised, so a phone on the Lisbon waterfront could be “in the sea” and get no country at all. At the 1:50m scale this happened often enough to matter.

Two changes fixed it. We moved countries to the more detailed 1:10m data, and when a point falls in no region we take the nearest one within 25 km. That catches harbours, beaches and bridges without ever assigning a point in open ocean to a country.

Takeaway

If you run point-in-polygon queries against large, detailed polygons, an index alone isn’t enough. Subdivide once at load time and the index starts doing its job.