7 ms·
Calculate Latitude/Longitude Distances in MySQL with the Haversine Function
- akharris 16y agoOne of those things you never think about when reading a map or driving in a car, but it's the explanation behind why you fly all the way up past nova scotia when on a plane to europe.
- lzimm 16y agowont that completely negate the value of the indices that lat/lon may/may not sit on and result in a complete tablescan?
- zachster 16y agoI've got this on a site I'm building that offers a sort by distance option. There's definitely a performance hit. I'm going to look into 'dumber' ways of filtering out the data prior to running this function. Maybe start by including state in the where clause, for example. Any other ideas? One solution I saw used more simple arithmetic to calculate a range of coordinates within levels of distance. That could be pre-cached, but it's a lot less accurate.
- joshu 16y agoUse tiles.
- bravo_sierra 16y agoFor what? How?
- joshu 16y agoHash the points into large tiles. Only calculate the nearby tiles, then find the items that are in the list of tiles (which is faster, due to being indexed.) Then use Haversine or whatever to filter.
- nl 16y agoGeohash: http://en.wikipedia.org/wiki/Geohash http://en.wikipedia.org/wiki/Geohash (Edit: to be more specific, you can get a pretty good distance measurement using Geohash and comparing strings. Obviously, indexing strings is something databases do well. The exact distance a single character corresponds to depends on longitude & latitude, but there are lookup tables for that. There are also edge conditions to be aware of which may affect your application) Or, use Postgres which has geospatial indexes.
- zachster 16y agoThanks for the pointer! This looks interesting. The edge conditions seem like they might pose a problem. I'll have to check out how often it would occur. Maybe the geospatial indexes are a better bet. It looks like MongoDB supports them also. Good excuse to try that out.
- thibaut_barrere 16y agoI've been using either MySQL with Sphinx or MongoDB with the built-in geonear successfully. If you're already using MongoDB, it's really dead-easy to setup (see the docs).
- nl 16y agoIf you are prepared to introduce new technology specifically to solve this problem, then you should take a look at LocalLucene, too: http://www.gissearch.com/locallucene http://www.gissearch.com/locallucene
- bravo_sierra 16y agoThe edge cases happen all the time. Using a B-Tree on a Geohash (like MongoDB does) is a bit more efficient that just indexing min/max values, but not by much. MySQL, PostgreSQL and even SQLite have R-Tree indices that perform 10x better.
- bravo_sierra 16y agoMySQL can use R-Trees too - http://dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html http://dev.mysql.com/doc/refman/5.0/en/spatial-extensions.ht...
- mthoms 16y agoI haven't yet used either of these but PostGres earthdistance http://www.postgresql.org/docs/8.3/static/earthdistance.html http://www.postgresql.org/docs/8.3/static/earthdistance.html or PostGis http://www.postgis.org/ http://www.postgis.org/ might be good options (if you don't mind leaving MySQL behind that is).
- bad_user 16y agoI'm not sure what the author is doing, but take a look at this presentation: http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-M... You can basically reduce the filtering done to something like: WHERE lat BETWEEN val1 AND val2 AND lon BETWEEN val3 AND val4. So indexing will work.
- codesink 16y agotrue, the distance calculation must NOT be in the WHERE clause if you want to use indexes (and you want). What I'm doing, given a max distance and a search point, is to calculate the bounding box in which I want to search in filter results with WHERE lat BETWEEN lat_min AND lat_max AND lng BETWEEN lng_min AND lng_max Calculating latitude min/max is trivial knowing that 1 latitude degree is 111.2KM. Longitude is a bit more convoluted because longitude degree size changes moving north/south. $lat_min = $lat - $range_km * (1 / 111.2); $lat_max = $lat + $range_km * (1 / 111.2); $k = $range_km/6371.04; $lng_min = $lng - rad2deg($k/cos(deg2rad($lat))); $lng_max = $lng + rad2deg($k/cos(deg2rad($lat)));
- bravo_sierra 16y agoWhy in the world would you use this when MySQL has almost proper geospatial support? It's far more efficient and less incorrect. I swear - next time I'm going to get a R-Tree novelty account.
- bad_user 16y agoBecause Mysql doesn't have support for distance searches.
- bravo_sierra 16y agoUsing the Buffer function it does. Then MySQL will utilize the geometry index, rather than scanning the table. Not clear in the docs, but it's there.
- bad_user 16y agoDo you have an example?
- thibaut_barrere 16y agoI'm interested as well (really, as someone who uses sphinx for that currently).
- bad_user 16y agoHey, I'm also using Sphinx :) Also, thing is filtering is not much of a problem as you can use the Haversine formula ... it gets to be a problem if you also want sorting from closest to furthest.
- codesink 16y agogeospatial index do NOT work if you're using InnoDB; so you must choose between geospatial queries or transactions (that MyISAM don't support).
- philfreo 16y agoSphinx (http://sphinxsearch.com/ http://sphinxsearch.com/) is really good at geo/spatial searches on MySQL data Example: http://www.god-object.com/2009/10/20/geospatial-search-using-sphinx-search-and-php/ http://www.god-object.com/2009/10/20/geospatial-search-using...
- thibaut_barrere 16y agoSeconded; I've been using it with the thinking_sphinx rubygems and it always worked great.
- ljegou 16y agoBeware, coordinates are not always expressed in the same referencial (geoid, ellipsoid, etc.).
- wazoox 16y ago<rant>I've got a better idea: use postgis and get rid of mysql and its quirks. Yep, I just reinstalled an old app yesterday, and for some unfathomable reason it loses communication with mysql at some point (it worked perfectly for what, 6 years?). Gosh, I hate mysql.</rant>
- thibaut_barrere 16y agoHonest question: if it's unfathomable, what makes you think it's caused by mysql, rather than some system update, driver or app dependency issue ?
- wazoox 16y agoIt's a perl program running on Debian stable. Apparently it fails to communicate properly with mysql 5, but works fine with mysql 4. I assume the Debian dbd-mysql package to be compatible with the Debian mysql 5 server, so of course it could be Debian fault, or some error in the program. But I prefer to unjustly incriminate mysql because postgres is so much better anyway :)
- thibaut_barrere 16y agoAnecdote on Haversine: in 1.6, MongoDB's built-in "geonear" was using non-spherical indexing, but I needed to get more accurate results in a project, so I queried 3 times more records and used Haversine afterward to sort records again, client-side. Here's the ruby code: http://gist.github.com/559482 http://gist.github.com/559482 Since then, MongoDB 1.7 has been released with spherical sort support (http://www.mongodb.org/display/DOCS/Geospatial+Indexing#GeospatialIndexing-TheEarthisRoundbutMapsareFlat http://www.mongodb.org/display/DOCS/Geospatial+Indexing#Geos...)