sql - Distance between two coordinates, how can I simplify this and/or use a different technique?

Question

I need to write a query which allows me to find all locations within a range (Miles) from a provided location.

The table is like this:

id  |  name  |  lat  |  lng 

So I have been doing research and found: this my sql presentation

I have tested it on a table with around 100 rows and will have plenty more! - Must be scalable.

I tried something more simple like this first:

//just some test data this would be required by user input    
set @orig_lat=55.857807; set @orig_lng=-4.242511; set @dist=10;

SELECT *, 3956 * 2 * ASIN(
          SQRT( POWER(SIN((orig.lat - abs(dest.lat)) * pi()/180 / 2), 2) 
              + COS(orig.lat * pi()/180 ) * COS(abs(dest.lat) * pi()/180)  
              * POWER(SIN((orig.lng - dest.lng) * pi()/180 / 2), 2) )) 
          AS distance
  FROM locations dest, locations orig
 WHERE orig.id = '1'
HAVING distance < 1
 ORDER BY distance;

This returned rows in around 50ms which is pretty good! However this would slow down dramatically as the rows increase.

EXPLAIN shows it's only using the PRIMARY key which is obvious.

---

Then after reading the article linked above. I tried something like this:

// defining variables - this when made into a stored procedure will call
// the values with a SELECT query.
set @mylon = -4.242511;
set @mylat = 55.857807;
set @dist = 0.5;

-- calculate lon and lat for the rectangle:
set @lon1 = @mylon-@dist/abs(cos(radians(@mylat))*69);
set @lon2 = @mylon+@dist/abs(cos(radians(@mylat))*69);
set @lat1 = @mylat-(@dist/69); 
set @lat2 = @mylat+(@dist/69);

-- run the query:

SELECT *, 3956 * 2 * ASIN(
          SQRT( POWER(SIN((@mylat - abs(dest.lat)) * pi()/180 / 2) ,2)
              + COS(@mylat * pi()/180 ) * COS(abs(dest.lat) * pi()/180)
              * POWER(SIN((@mylon - dest.lng) * pi()/180 / 2), 2) ))
          AS distance
  FROM locations dest
 WHERE dest.lng BETWEEN @lon1 AND @lon2
   AND dest.lat BETWEEN @lat1 AND @lat2
HAVING distance < @dist
 ORDER BY distance;

The time of this query is around 240ms, this is not too bad, but is slower than the last. But I can imagine at much higher number of rows this would work out faster. However anEXPLAIN shows the possible keys as lat,lng or PRIMARY and used PRIMARY.

How can I do this better???

I know I could store the lat lng as a POINT(); but I also haven't found too much documentation on this which shows if it's faster or accurate?

Any other ideas would be happily accepted!

Thanks very much!

-Stefan

---

UPDATE:

As Jonathan Leffler pointed out I had made a few mistakes which I hadn't noticed:

I had only put abs() on one of the lat values. I was using an id search in the WHERE clause in the second one as well, when there was no need. In the first query was purely experimental the second one is more likely to hit production.

After these changes EXPLAIN shows the key is now using lng column and average time to respond around 180ms now which is an improvement.

Answer 1

Any other ideas would be happily accepted!

If you want speed (and simplicity) you'll want some decent geospatial support from your database. This introduces geospatial datatypes, geospatial indexes and (a lot of) functions for processing / building / analyzing geospatial data.

MySQL implements a part of the OpenGIS specifications although it is / was (last time I checked it was) very very rough around the edges / premature (not useful for any real work).

PostGis on PostgreSql would make this trivially easy and readable:

(this finds all points from tableb which are closer then 1000 meters from point a in tablea with id 123)

select 
    myvalue
from 
    tablea, tableb
where 
    st_dwithin(tablea.the_geom, tableb.the_geom, 1000)
and
    tablea.id = 123