Using MySQL Spatial Extensions for Range Queries

Andy Lindeman

2 min read

Jan 9, 2012

Using MySQL Spatial Extensions for Range Queries

We help one of our clients operate a high traffic API that, among other things, returns data that is associated with an IP address range. It’s similar to querying for information from WHOIS.

The IP address ranges are specified in a MySQL database with ip_start and ip_end columns. The IP addresses are first converted to their representation as 32-bit integers.

For instance, the range 1.1.1.1 to 1.1.3.3 would look like:

ip_start     ip_end     ...

16843009

16843523

…

Read on for more about how we helped optimize the queries that search for an IP within these ranges.

Loading new information into the API required that we test whether a new IP range overlapped with a current range in the database.

It is relatively easy to write a query that tests whether one range intersects another in SQL:

	SELECT * FROM ip_ranges
	WHERE ip_start <= @new_ip_end AND
	@new_ip_start <= ip_end;

view raw range.sql hosted with ❤ by GitHub

Unfortunately, even with indexes, this query requires a full table scan in MySQL. On a large table, the query took around 0.25 seconds. While insignificant for one-off queries, loading thousands of new ranges made the time really add up.

We scoped out various solutions, but the one that ended up working best was modeling the problem using MySQL Spatial Extensions.

While IP ranges are not a typical use case for spatial extensions, they can be modeled as 1-dimensional lines. And given that spatial indexes are very efficient at doing queries like Intersects(), we found the solution to be really performant.

The following SQL snippet creates a column called ip_range on the table that is then populated with rectangles in 2-dimensions that represent the IP ranges. We only care about 1-dimension, so the height of the rectangles is unimportant:

	ALTER TABLE ip_ranges add ip_range POLYGON NULL;
	UPDATE ip_ranges
	SET ip_range=Polygon(
	LineString(
	Point(ip_start, 1),
	Point(ip_start, 0),
	Point(ip_end, 0),
	Point(ip_end, 1),
	Point(ip_start, 1)
	)
	);

	ALTER TABLE ip_ranges MODIFY ip_range POLYGON NOT NULL;
	CREATE SPATIAL INDEX index_ip_ranges_on_ip_range on ip_ranges (ip_range);

view raw create_geometry.sql hosted with ❤ by GitHub

With that column and the spatial index, queries to test for range intersection can be written as:

	SELECT * FROM ip_ranges
	WHERE Intersects(ip_range,
	Polygon(
	LineString(
	Point(@new_ip_start, 1),
	Point(@new_ip_start, 0),
	Point(@new_ip_end, 0),
	Point(@new_ip_end, 1),
	Point(@new_ip_start, 1)
	)
	)
	);

view raw range_spatial.sql hosted with ❤ by GitHub

This query achieves the same thing as the earlier query, but runs much faster.

Have you modeled a problem with the geospatial features of a database?

Angie Terrell

Reviewer Big Nerd Ranch

Angie joined BNR in 2014 as a senior UX/UI designer. Just over a year later she became director of design and instruction leading a team of user experience and interface designers. All told, Angie has over 15 years of experience designing a wide array of user experiences