Calculate Latitude/Longitude Distances in MySQL with the Haversine Function

Re:Calculate Latitude/Longitude Distances in MySQL with the ... by zachster on Thursday October 28, 2010 @01:28AM (#1841866)

I'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.

[ Parent | on HN ]

Re:Calculate Latitude/Longitude Distances in MySQL with the ... by nl on Thursday October 28, 2010 @01:33AM (#1841875)

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.

[ Parent | on HN ]

Re:Calculate Latitude/Longitude Distances in MySQL with the ... by zachster on Thursday October 28, 2010 @01:45AM (#1841905)

Thanks 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.

[ Parent | on HN ]

Re:Calculate Latitude/Longitude Distances in MySQL with the ... by bravo_sierra on Thursday October 28, 2010 @02:08AM (#1841950)

The 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.

[ Parent | on HN ]

Re:Calculate Latitude/Longitude Distances in MySQL with the ... by nl on Thursday October 28, 2010 @01:53AM (#1841922)

If 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

[ Parent | on HN ]

Re:Calculate Latitude/Longitude Distances in MySQL with the ... by thibaut_barrere on Thursday October 28, 2010 @04:47AM (#1842227)

I'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).

[ Parent | on HN ]

Re:Calculate Latitude/Longitude Distances in MySQL with the ... by bravo_sierra on Thursday October 28, 2010 @01:58AM (#1841928)

MySQL can use R-Trees too - http://dev.mysql.com/doc/refman/5.0/en/spatial-extensions.ht...

[ Parent | on HN ]

Re:Calculate Latitude/Longitude Distances in MySQL with the ... by mthoms on Thursday October 28, 2010 @02:12AM (#1841958)

I haven't yet used either of these but PostGres earthdistance http://www.postgresql.org/docs/8.3/static/earthdistance.html or PostGis http://www.postgis.org/ might be good options (if you don't mind leaving MySQL behind that is).

[ Parent | on HN ]

Re:Calculate Latitude/Longitude Distances in MySQL with the ... by joshu on Thursday October 28, 2010 @01:30AM (#1841869)

Use tiles.

[ Parent | on HN ]

Re:Calculate Latitude/Longitude Distances in MySQL with the ... by bravo_sierra on Thursday October 28, 2010 @02:02AM (#1841935)

For what? How?

[ Parent | on HN ]

Re:Calculate Latitude/Longitude Distances in MySQL with the ... by joshu on Friday October 29, 2010 @01:37AM (#1846291)

Hash 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.

[ Parent | on HN ]