1

I am trying to come up with the most efficient way to resolve the following problem. I have a large table locations in which points are stored using two doubles, one for Lat and one for Lng, which are indexed, as well as a radius.

I am trying to select all locations that are within the radius of a given Latitude and Longitude. My current approach is to run a subquery that first gathers all results within a "geographic square", and then from those results, calculate the distance and determine whether it is within range like so:

Subquery (select only those within a rough mile x mile square):

SELECT * FROM events WHERE $lat +0.015 > lat AND lat > $lat-0.015 AND $lng +0.02 > lng AND lng > $lng-0.02

Determine distance via Haversine:

SELECT * FROM ( the subquery ) WHERE Radius >= ( 20903520 * acos( cos(RADIANS(Lat)) * cos(RADIANS($lat)) * cos(RADIANS(Lng - $lng)) + sin(RADIANS(Lat)) * sin(RADIANS($lat))))

My question is, what is a better way of approaching this? I'm fairly sure this is among the least efficient ways of going about this and any help is greatly appreciated.

Kony2013
  • 171
  • 9
  • You shouldn't use `MySQL`, `Subqueries` and `Efficient` in one sentence, unless there is also 'not' in there somewhere. – GolezTrol Feb 12 '15 at 19:10
  • Very true, however I'm at a complete loss at how to best approach this. Any thoughts? – Kony2013 Feb 12 '15 at 19:10
  • I'm not sure, but MySQL has some interesting Lat/Long features itself. Maybe you can have a look the answers to [Fastest Way to Find Distance Between Two Lat/Long Points](http://stackoverflow.com/questions/1006654/fastest-way-to-find-distance-between-two-lat-long-points) or dive into the [GEO spacial extensions](http://dev.mysql.com/doc/refman/5.7/en/spatial-extensions.html). – GolezTrol Feb 12 '15 at 19:15

1 Answers1

0

Another solution is found here: http://mysql.rjweb.org/doc.php/latlng It is essentially O(1), whereas most index-based solutions are O(sqrt(N)).

My technique works with InnoDB. Spatial indexes require MyISAM (until 5.7).

Rick James
  • 135,179
  • 13
  • 127
  • 222