What's the right way to measure locations within a radius in mySQL?

Question

I'm writing an app that needs to allow a user to select elements that are within some radius of their location. There is no way to know how many locations there will be ultimately, but it might be tens of thousands. The user doing the search is one of the location nodes (and not just an arbitrary position submitted by their phone or whatnot)

I see answers like this: mysql lat lon calulation to show locations within radius but I'm concerned that this is a really serious undertaking given that the math involved will need to be calculated for every single "other" location.

The other approach I was considering is to have a relational table that identifies the distance between each location (that I'd populate every time a location was added), granted it will have a ton of rows to define every possible relationship, but then selecting against *that table will be super fast, especially if the distances are indexed.

Would love to get some advice from someone who's done this in mySQL and can warn/advise me for or against the best approach.

david strachan · Accepted Answer · 2014-10-24T12:05:53.623

The following SQL query uses Spherical Law of Cosines to calculate the distance between a coordinate and coordinates in a table. It limits result to 10 and orders by distance. This is used instead of the Haversine Formula which is too complicated to perform with MySQL

Spherical Law of Cosines

Where R = 3,959 miles or 6,371km

d = acos( sin(lat1).sin(lat2) + cos(lat1).cos(lat2).cos(lng2-lng1) ).R

SQL

SELECT  name, lat, lng, ( 3959 * acos( cos( radians($center_lat) ) 
                        * cos( radians( lat ) ) * cos( radians( lng )
                        - radians($center_lng) ) + sin( radians($center_lat) ) 
                        * sin( radians( lat ) ) ) ) AS distance FROM table 
                        ORDER BY distance LIMIT 0 , 10

Where $center_lat & $center_lng are coordinates of location.

The query uses SQL Math functions

Query took 0.2506 sec on database with 50,068 rows

The spatial functions avaialable in MySQL are not suitable for your porpose see this Blog

when you say R=3959, you mean that it finds every location within that distance from the center_lng,center_lat and then limits the result to 10? Is it substantially slower if I reduce that radius to 50 but then not set a limit and let it give me every result that falls into that circle? — Yevgeny Simkin, Oct 24 '14 at 18:01
Removing the LIMIT should not affect the time to execute the query,but could effect the time taken to display results. — david strachan, Oct 24 '14 at 19:22

score 1 · Answer 2 · answered Oct 24 '14 at 04:20

GIS is a good place to start for radius distance but eventually (scale) you will have to resolve down to lat/long grids. Radius is expensive to calculate where grids are quite simple to store and look up. FWIW GIS functionality in MySQL does not scale well on many cores (10+) prior to 5.6 in my experience and may not be fixed until 5.7.

score 0 · Answer 3 · edited May 23 '17 at 10:33

If you precalculate some of the data that you actually need and store this in the database, it should be quite fast to make some calculation based on that data.

From my answer in this question:

Sorting zip code proximity question on SO

you can use a calculation like

$iRadius * 2 * ASIN(SQRT(POWER(SIN(( $fLat - abs(pos.lat)) * pi() / 180 / 2),2) +
COS( $fLat * pi()/180) * COS(abs(pos.lat) * pi() / 180) * POWER(SIN(( $fLon - pos.lon) *
pi() / 180 / 2), 2) )) AS distance

where loads of the actual mathematical functions can be precalculated and also be stored in the database. This should help you speed up the query.

And if you know that you are only interested in a specific radius you can even ignore lat/lon values with a greater difference (since that already implies they have a specific distance), so you only make the calculation for lat/lon values in a specific range from your location.

I used this approach to calculate distances to zip codes (>60.000) in under 0.1s

The question always is: How many values will you have to compute against?

What's the right way to measure locations within a radius in mySQL?

3 Answers3