Fastest Way to Find Distance Between Two Lat/Long Points

gis, location, mysql

Solution

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(@lat)))
          , ' '
          , @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)

Problem

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

Original source

Related problems