5 ms·

Efficient Distance Querying in MySQL

61 points by aarondf 5y ago

JoshuaDavid 5y ago
If for whatever reason you can't[1] use a spatial index, you can use something like geohash[2] as a generalized version of the "generated prefix columns that you then use a prefix function on" concept mentioned in the article. [1] TBH the first thing to look at is whether this is a real constraint [2] https://en.wikipedia.org/wiki/Geohash https://en.wikipedia.org/wiki/Geohash
tnorthcutt 5y ago
This was super informative – I especially like that you showed your thinking through a step by step process, instead of just "here's the best thing to do". That makes it possible to apply this same lesson to other areas as well.
nwallin 5y ago
This is an interesting article about strategies to use when traditional indexes just won't do, but for the love of the index please use MySQL's (or postgres' or sqlite's) built in spatial index for this particular class of problems. It will does this sort of thing much, much more efficiently than 99% of in house solutions. https://dev.mysql.com/doc/refman/8.0/en/spatial-types.html https://dev.mysql.com/doc/refman/8.0/en/spatial-types.html http://postgis.refractions.net/ http://postgis.refractions.net/ https://sqlite.org/rtree.html https://sqlite.org/rtree.html
- IdontRememberIt 5y ago
  With mysql 5.7, range searches on indexes (BETWEEN() or equivalent) are notoriously slow with large datasets. We discovered that spacial index (flatten to 1 dimension) can be used to solve a common issue: ip range queries. The query costs dropped and all the query metrics improved.
  - hu3 5y ago
    Does it improve in newer versions of MySQL? I'll need to so similar work soon.
karmakaze 5y ago
To get around not using the more of the index, the query could be split into parts, one for each tranche combined with UNION ALL. Each part can examine a narrow subset of rows, disjoint from the other parts.
itake 5y ago
title should be updated to say 2d distances.
fitzn 5y ago
This is clever and a great read. Reminds me a bit of finding hashes, for example, that are within a certain Hamming distance to a target value (hash). If the distance you're interested in is small (e.g., 1 bit), then it might be faster to check for 64 exact target values than to check all values for off-by-1 bit. Very cool. Thank you for posting.
dandelany 5y ago
Great post. Just to be pedantic for a moment: > it gives you results that are 100% correct, which is pretty important! Not quite 100% correct, as the `ST_Distance_Sphere` function uses a spherical earth model, & in fact the earth is an oblate spheroid :) The slower-but-more-accurate `ST_Distance_Spheroid` also exists if you care about such things.
- nixpulvis 5y ago
  It's hardly pedantic, the differences can be on the order of kilometers over large distances. The GPS uses WGS 84 as the reference ellipsoid model, for example. (if my memory serves)
Ginden 5y ago
Author is quite clever in reinventing solutions for solved problems.
paisawalla 5y ago
If you are choosing a backend for a project, and you think there's a chance that your use case could require spatial querying: use postgres, so that if the need arises, you can enable postgis. You will get all of the features described here natively, with support for indexing and other improvements as well.
bawolff 5y ago
The row estimates in EXPLAIN are just estimates and often very wrong. You should count actual rows read instead via something like SHOW HANDLER.
hiyer 5y ago
A few years back I was working at a real estate firm where you could search for available rentals by location. The houses were saved with their latitude and longitude values. Their original search implementation used to fetch all the records from the database and then filter them based on some parameters - IIRC translate back from the lat-long to some location and check if it fell within the area. The number of rows was not too high - 10k or so, so this used to run in single-digit seconds. At that time MySQL had neither spatial indices nor a native haversine method. I switched out the search method to translate the area name to a lat-long on the frontend (based on google maps) and then use a haversine in the query to retrieve results. It was still a couple of orders of magnitude faster than the previous solution, and more accurate to boot.
LegitShady 5y ago
I feel like I have had this in oracle for a dozen years without anything custom. Interesting approach when there's no built in spatial package.
konfusinomicon 5y ago
semi related...I once spent hours working on a bug only to the later realize that mysql uses longitude latitude in spatial methods instead of the other way around..fun times!

61 points by aarondf 5y ago

If for whatever reason you can't[1] use a spatial index, you can use something like geohash[2] as a generalized version of the "generated prefix columns that you then use a prefix function on" concept mentioned in the article. [1] TBH the first thing to look at is whether this is a real constraint [2] https://en.wikipedia.org/wiki/Geohash https://en.wikipedia.org/wiki/Geohash

tnorthcutt 5y ago

This was super informative – I especially like that you showed your thinking through a step by step process, instead of just "here's the best thing to do". That makes it possible to apply this same lesson to other areas as well.

nwallin 5y ago

This is an interesting article about strategies to use when traditional indexes just won't do, but for the love of the index please use MySQL's (or postgres' or sqlite's) built in spatial index for this particular class of problems. It will does this sort of thing much, much more efficiently than 99% of in house solutions. https://dev.mysql.com/doc/refman/8.0/en/spatial-types.html https://dev.mysql.com/doc/refman/8.0/en/spatial-types.html http://postgis.refractions.net/ http://postgis.refractions.net/ https://sqlite.org/rtree.html https://sqlite.org/rtree.html

IdontRememberIt 5y ago
With mysql 5.7, range searches on indexes (BETWEEN() or equivalent) are notoriously slow with large datasets. We discovered that spacial index (flatten to 1 dimension) can be used to solve a common issue: ip range queries. The query costs dropped and all the query metrics improved.
- hu3 5y ago
  Does it improve in newer versions of MySQL? I'll need to so similar work soon.

karmakaze 5y ago

To get around not using the more of the index, the query could be split into parts, one for each tranche combined with UNION ALL. Each part can examine a narrow subset of rows, disjoint from the other parts.

itake 5y ago

title should be updated to say 2d distances.

fitzn 5y ago

This is clever and a great read. Reminds me a bit of finding hashes, for example, that are within a certain Hamming distance to a target value (hash). If the distance you're interested in is small (e.g., 1 bit), then it might be faster to check for 64 exact target values than to check all values for off-by-1 bit. Very cool. Thank you for posting.

dandelany 5y ago

Great post. Just to be pedantic for a moment: > it gives you results that are 100% correct, which is pretty important! Not quite 100% correct, as the `ST_Distance_Sphere` function uses a spherical earth model, & in fact the earth is an oblate spheroid :) The slower-but-more-accurate `ST_Distance_Spheroid` also exists if you care about such things.

nixpulvis 5y ago
It's hardly pedantic, the differences can be on the order of kilometers over large distances. The GPS uses WGS 84 as the reference ellipsoid model, for example. (if my memory serves)

Ginden 5y ago

Author is quite clever in reinventing solutions for solved problems.

paisawalla 5y ago

If you are choosing a backend for a project, and you think there's a chance that your use case could require spatial querying: use postgres, so that if the need arises, you can enable postgis. You will get all of the features described here natively, with support for indexing and other improvements as well.

bawolff 5y ago

The row estimates in EXPLAIN are just estimates and often very wrong. You should count actual rows read instead via something like SHOW HANDLER.

hiyer 5y ago

A few years back I was working at a real estate firm where you could search for available rentals by location. The houses were saved with their latitude and longitude values. Their original search implementation used to fetch all the records from the database and then filter them based on some parameters - IIRC translate back from the lat-long to some location and check if it fell within the area. The number of rows was not too high - 10k or so, so this used to run in single-digit seconds. At that time MySQL had neither spatial indices nor a native haversine method. I switched out the search method to translate the area name to a lat-long on the frontend (based on google maps) and then use a haversine in the query to retrieve results. It was still a couple of orders of magnitude faster than the previous solution, and more accurate to boot.

LegitShady 5y ago

I feel like I have had this in oracle for a dozen years without anything custom. Interesting approach when there's no built in spatial package.

konfusinomicon 5y ago

semi related...I once spent hours working on a bug only to the later realize that mysql uses longitude latitude in spatial methods instead of the other way around..fun times!