Mysql: Fastest Way to Find Distance Between Two Lat/Long Points

I currently have just under a million locations in a mysql database all with longitude and latitude information.

I am trying to find the distance between one point and many other points via a query. It's not as fast as I want it to be especially with 100+ hits a second.

Is there a faster query or possibly a faster system other than mysql for this? I'm using this query:

SELECT 
  name, 
   ( 3959 * acos( cos( radians(42.290763) ) * cos( radians( locations.lat ) ) 
   * cos( radians(locations.lng) - radians(-71.35368)) + sin(radians(42.290763)) 
   * sin( radians(locations.lat)))) AS distance 
FROM locations 
WHERE active = 1 
HAVING distance < 10 
ORDER BY distance;

Note: The provided distance is in Miles. If you need Kilometers, use 6371 instead of 3959.

 Answers

• Create your points using Point values of Geometry data types in MyISAM table. As of Mysql 5.7.5, InnoDB tables now also support SPATIAL indices.
• Create a SPATIAL index on these points
• Use MBRContains() to find the values:

  SELECT  *
  FROM    table
  WHERE   MBRContains(LineFromText(CONCAT(
          '('
          , @lon + 10 / ( 111.1 / cos(RADIANS(@lon)))
          , ' '
          , @lat + 10 / 111.1
          , ','
          , @lon - 10 / ( 111.1 / cos(RADIANS(@lat)))
          , ' '
          , @lat - 10 / 111.1 
          , ')' )
          ,mypoint)
  

, or, in MySQL 5.1 and above:

    SELECT  *
    FROM    table
    WHERE   MBRContains
                    (
                    LineString
                            (
                            Point (
                                    @lon + 10 / ( 111.1 / COS(RADIANS(@lat))),
                                    @lat + 10 / 111.1
                                  ),
                            Point (
                                    @lon - 10 / ( 111.1 / COS(RADIANS(@lat))),
                                    @lat - 10 / 111.1
                                  ) 
                            ),
                    mypoint
                    )

This will select all points approximately within the box (@lat +/- 10 km, @lon +/- 10km).

This actually is not a box, but a spherical rectangle: latitude and longitude bound segment of the sphere. This may differ from a plain rectangle on the Franz Joseph Land, but quite close to it on most inhabited places.

• Apply additional filtering to select everything inside the circle (not the square)
• Possibly apply additional fine filtering to account for the big circle distance (for large distances)

---

Check this presentation for a good answer. Basically it shows the two different approaches shown in the comments, with a detailed explanation on why/when you should use one or the other and why the "in the box" calculation can be very interesting.

---

SELECT * FROM (SELECT *,(((acos(sin((43.6980168*pi()/180)) * 
sin((latitude*pi()/180))+cos((43.6980168*pi()/180)) * 
cos((latitude*pi()/180)) * cos(((7.266903899999988- longitude)* 
pi()/180))))*180/pi())*60*1.1515 ) as distance 
FROM wp_users WHERE 1 GROUP BY ID limit 0,10) as X 
ORDER BY ID DESC

This is the distance calculation query between to points in MySQL, I have used it in a long database, it it working perfect! Note: do the changes (database name, table name, column etc) as per your requirements.

---

The full code with details about how to install as MySQL plugin are here: https://github.com/lucasepe/lib_mysqludf_haversine

I posted this last year as comment. Since kindly @TylerCollier suggested me to post as answer, here it is.

Another way is to write a custom UDF function that returns the haversine distance from two points. This function can take in input:

lat1 (real), lng1 (real), lat2 (real), lng2 (real), type (string - optinal - 'km', 'ft', 'mi')

So we can write something like this:

SELECT id, name FROM MY_PLACES WHERE haversine_distance(lat1, lng1, lat2, lng2) < 40;

to fetch all records with a distance less then 40 kilometers. Or:

SELECT id, name FROM MY_PLACES WHERE haversine_distance(lat1, lng1, lat2, lng2, 'ft') < 25;

to fetch all records with a distance less then 25 feet.

The core function is:

double
haversine_distance( UDF_INIT* initid, UDF_ARGS* args, char* is_null, char *error ) {
    double result = *(double*) initid->ptr;
    /*Earth Radius in Kilometers.*/ 
    double R = 6372.797560856;
    double DEG_TO_RAD = M_PI/180.0;
    double RAD_TO_DEG = 180.0/M_PI;
    double lat1 = *(double*) args->args[0];
    double lon1 = *(double*) args->args[1];
    double lat2 = *(double*) args->args[2];
    double lon2 = *(double*) args->args[3];
    double dlon = (lon2 - lon1) * DEG_TO_RAD;
    double dlat = (lat2 - lat1) * DEG_TO_RAD;
    double a = pow(sin(dlat * 0.5),2) + 
        cos(lat1*DEG_TO_RAD) * cos(lat2*DEG_TO_RAD) * pow(sin(dlon * 0.5),2);
    double c = 2.0 * atan2(sqrt(a), sqrt(1-a));
    result = ( R * c );
    /*
     * If we have a 5th distance type argument...
     */
    if (args->arg_count == 5) {
        str_to_lowercase(args->args[4]);
        if (strcmp(args->args[4], "ft") == 0) result *= 3280.8399;
        if (strcmp(args->args[4], "mi") == 0) result *= 0.621371192;
    }

    return result;
}

---

Here is a very detailed description of Geo Distance Search with MySQL a solution based on implementation of Haversine Formula to mysql. The complete solution description with theory, implementation and further performance optimization. Although the spatial optimization part didn't work correct in my case. 

---

Have a read of Geo Distance Search with MySQL, a solution based on implementation of Haversine Formula to MySQL. This is a complete solution description with theory, implementation and further performance optimization. Although the spatial optimization part didn't work correctly in my case.

I noticed two mistakes in this:

1. the use of abs in the select statement on p8. I just omitted abs and it worked.
2. the spatial search distance function on p27 does not convert to radians or multiply longitude by cos(latitude), unless his spatial data is loaded with this in consideration (cannot tell from context of article), but his example on p26 indicates that his spatial data POINT is not loaded with radians or degrees.

---

if you are using MySQL 5.7.*, then you can use st_distance_sphere(POINT, POINT).

Select st_distance_sphere(POINT(-2.997065, 53.404146 ), POINT(58.615349, 23.56676 ))/1000  as distcance

---

$objectQuery = "SELECT table_master.*, ((acos(sin((" . $latitude . "*pi()/180)) * sin((`latitude`*pi()/180))+cos((" . $latitude . "*pi()/180)) * cos((`latitude`*pi()/180)) * cos(((" . $longitude . "- `longtude`)* pi()/180))))*180/pi())*60*1.1515  as distance FROM `table_post_broadcasts` JOIN table_master ON table_post_broadcasts.master_id = table_master.id WHERE table_master.type_of_post ='type' HAVING distance <='" . $Radius . "' ORDER BY distance asc";