In my previous post about geo-spatial search in MySQL I described (along with other things) how to use geo-distance functions. In this post I will describe the geo-spatial distance functions in more details.
If you need to calculate an exact distance between 2 points on Earth in MySQL (very common for geo-enabled applications) you have at least 3 choices.
- Use stored function and implement haversine formula
- Use UDF (user defined function) for haversine (see below)
- In MySQL 5.6 you can use st_distance function (newly documented), however, you will get the distance on plane and not on earth; the value returned will be good for sorting by distance but will not represent actual miles or kilometers.
MySQL stored function for calculating distance on Earth
I previously gave an example for a MySQL-stored function which implements the haversine formula. However, the approach I used was not very precise: it was optimized for speed. If you need a more precise haversine formula implementation you can use this function (result will be in miles):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | delimiter // create DEFINER = CURRENT_USER function haversine_distance_sp (lat1 double, lon1 double, lat2 double, lon2 double) returns double begin declare R int DEFAULT 3958.76; declare phi1 double; declare phi2 double; declare d_phi double; declare d_lambda double; declare a double; declare c double; declare d double; set phi1 = radians(lat1); set phi2 = radians(lat2); set d_phi = radians(lat2-lat1); set d_lambda = radians(lon2-lon1); set a = sin(d_phi/2) * sin(d_phi/2) + cos(phi1) * cos(phi2) * sin(d_lambda/2) * sin(d_lambda/2); set c = 2 * atan2(sqrt(a), sqrt(1-a)); set d = R * c; return d; end; // delimiter ; |
(the algorithm is based on the standard formula, I’ve used the well-known Movable Type scripts calculator)
This is a slower implementation as it uses arctangent, however it is more precise.
MySQL UDF for Haversine distance
Another approach, which will give you much more performance is to use UDF. There are a number of implementations, I’ve used lib_mysqludf_haversine.
Here is the simple steps to install it in MySQL 5.6 (will also work with earlier versions):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | $ wget 'https://github.com/lucasepe/lib_mysqludf_haversine/archive/master.zip' $ unzip master.zip $ cd lib_mysqludf_haversine-master/ $ make mysql> show global variables like 'plugin%'; +---------------+-------------------------+ | Variable_name | Value | +---------------+-------------------------+ | plugin_dir | /usr/lib64/mysql/plugin | +---------------+-------------------------+ 1 row in set (0.00 sec) $ sudo cp lib_mysqludf_haversine.so /usr/lib64/mysql/plugin/ mysql> CREATE FUNCTION haversine_distance RETURNS REAL SONAME 'lib_mysqludf_haversine.so'; mysql> select haversine_distance(37.470295464, -122.572938858498, 37.760150536, -122.20701914150199, 'mi') as dist_in_miles; +---------------+ | dist_in_miles | +---------------+ | 28.330467 | +---------------+ 1 row in set (0.00 sec) |
Please note:
- Make sure you have the mysql-devel or percona-server-devel package installed (MySQL development libraries) before installing.
- You will need to specify the last parameter to be “mi” if you want to get the results in miles, otherwise it will give you kilometers.
MySQL ST_distance function
In MySQL 5.6 you can use ST_distance function:
1 2 3 4 5 6 7 | mysql> select st_distance(point(37.470295464, -122.572938858498), point( 37.760150536, -122.20701914150199)) as distance_plane; +---------------------+ | distance_plane | +---------------------+ | 0.46681174155173943 | +---------------------+ 1 row in set (0.00 sec) |
As we can see it does not give us an actual distance in mile or kilometers as it does not take into account that we have latitude and longitude, rather than X and Y on plane.
Geo Distance Functions Performance
The stored procedures and functions in MySQL are known to be slower, especially with trigonometrical functions. I’ve did a quick test, using MySQL function benchmark.
First I set 2 points (10 miles from SFO airport)
1 2 3 4 | set @rlon1 = 122.572938858498; set @rlat1 = 37.470295464; set @rlon2 = -122.20701914150199; set @rlat2 = 37.760150536; |
Next I use 4 function to benchmark:
- Less precise stored function (haversine)
- More precise stored function (haversine)
- UDF for haversine
- MySQL 5.6 native ST_distance (plane)
The benchmark function will execute the above function 100000 times.
Here are the results:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | mysql> select benchmark(100000, haversine_old_sp(@rlat1, @rlon1, @rlat2, @rlon2)) as less_precise_mysql_stored_proc; +--------------------------------+ | less_precise_mysql_stored_proc | +--------------------------------+ | 0 | +--------------------------------+ 1 row in set (1.46 sec) mysql> select benchmark(100000, haversine_distance_sp(@rlat1, @rlon1, @rlat2, @rlon2)) as more_precise_mysql_stored_proc; +--------------------------------+ | more_precise_mysql_stored_proc | +--------------------------------+ | 0 | +--------------------------------+ 1 row in set (2.58 sec) mysql> select benchmark(100000, haversine_distance(@rlat1, @rlon1, @rlat2, @rlon2, 'mi')) as udf_haversine_function; +------------------------+ | udf_haversine_function | +------------------------+ | 0 | +------------------------+ 1 row in set (0.17 sec) mysql> select benchmark(100000, st_distance(point(@rlat1, @rlon1), point(@rlat2, @rlon1))) as mysql_builtin_st_distance; +---------------------------+ | mysql_builtin_st_distance | +---------------------------+ | 0 | +---------------------------+ 1 row in set (0.10 sec) |
As we can see the UDF gives much faster response time (which is comparable to built-in function).
Benchmark chart (smaller the better)
Conclusion
The lib_mysqludf_haversine UDF provides a good function for geo-distance search in MySQL. Please let me know in the comments what geo-distance functions or approaches do you use in your applications.
Incorrect benchmark for the ST_distance function. In fact, you’re measuring not only the speed of the function itself, but two conversions from text to point each iteration as well.
select benchmark(100000, st_distance(point(@rlat1, @rlon1), point(@rlat2, @rlon1))) as mysql_builtin_st_distance;
…
1 row in set (0.08 sec)
set @p1 = point(@rlat1, @rlon1), @p2 = point(@rlat2, @rlon1); select benchmark(100000, st_distance(@p1, @p2)) as mysql_builtin_st_distance;
…
1 row in set (0.01 sec)
Eliah,
Yes, that is a good point, you are right! I will update the post.
Thank you for pointing it out!
PS: I wish the built-in function st_distance support the SRID and can calculate distance on earth.
Hello,
Thank you for this article and the benchmarks.
Suppose I have to deploy my MySQL on Amazon RDS so what should be the approach for Installing lib_mysqludf_haversine ?
Helpful post – I did a bit of my own research for a project this morning and found something quite interesting. The main performance bottleneck seems to be stored procedures / functions themselves – probably interpretation. Without installing any kind of third party library I was able to produce comparable performance to the UDF Haversine result, just by inlining the algebra directly into the SQL. Would guess that’s going to be an adequate approach in most scenarios, e.g. where statements are issued from another language that supports templating / prepared statements.