最快的方法找到两个Lat/长点之间的距离。

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

我目前在mysql数据库中有将近100万个位置，都有经度和纬度信息。

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.

我试图通过一个查询找到一个点和许多其他点之间的距离。它没有我想要的那么快特别是每秒100+的命中率。

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

除了mysql，还有更快的查询或系统吗?我使用这个查询:

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.

注:提供的距离以英里为单位。如果你需要公里，使用6371而不是3959。

15 个解决方案

#1

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

  使用MyISAM表中的几何数据类型的点值创建您的点。从Mysql 5.7.5开始，InnoDB表现在也支持空间索引。

• Create a SPATIAL index on these points

  在这些点上创建一个空间索引

• Use MBRContains() to find the values:

  使用MBRContains()查找值:

  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:

，或MySQL 5.1及以上版本:

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

这将选择框内的所有点(@lat +/- 10公里，@lon +/- 10公里)。

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)

  可能应用额外的精细滤波来计算大圆距离(对于大圆距离)

#2

Not a MySql specific answer, but it'll improve the performance of your sql statement.

不是特定于MySql的答案，但它将提高sql语句的性能。

What you're effectively doing is calculating the distance to every point in the table, to see if it's within 10 units of a given point.

你有效地做的是计算到表格中每个点的距离，看看它是否在给定点的10个单位内。

What you can do before you run this sql, is create four points that draw a box 20 units on a side, with your point in the center i.e.. (x1,y1 ) . . . (x4, y4), where (x1,y1) is (givenlong + 10 units, givenLat + 10units) . . . (givenLong - 10units, givenLat -10 units). Actually, you only need two points, top left and bottom right call them (X1, Y1) and (X2, Y2)

在运行这个sql之前，您可以做的是创建四个点，在一边画一个20个单元的方框，在中间点，也就是。(x1,y1)。(x4, y4)，式(x1,y1)为(givenlong + 10个单位，givenLat + 10个单位)…(givenLong - 10units, givenLat - 10units)。实际上，你只需要两个点，左上角和右下角的点(X1, Y1)和(X2, Y2)

Now your SQL statement use these points to exclude rows that definitely are more than 10u from your given point, it can use indexes on the latitudes & longitudes, so will be orders of magnitude faster than what you currently have.

现在，SQL语句使用这些点来排除距离给定点超过10u的行，它可以在纬度和经度上使用索引，因此速度将比当前的数量级更快。

e.g.

如。

select . . . 
where locations.lat between X1 and X2 
and   locations.Long between y1 and y2;

The box approach can return false positives (you can pick up points in the corners of the box that are > 10u from the given point), so you still need to calculate the distance of each point. However this again will be much faster because you have drastically limited the number of points to test to the points within the box.

box方法可以返回假阳性(您可以从给定的点上获取> 10u的框角中的点)，因此您仍然需要计算每个点的距离。然而，这将会更快，因为您已经彻底地将测试点的数量限制在了框内的点上。

I call this technique "Thinking inside the box" :)

我把这种技巧叫做“在盒子里思考”:

EDIT: Can this be put into one SQL statement?

编辑:可以将它放入一个SQL语句中吗?

I have no idea what mySql or Php is capable of, sorry. I don't know where the best place is to build the four points, or how they could be passed to a mySql query in Php. However, once you have the four points, there's nothing stopping you combining your own SQL statemen with mine.

我不知道mySql或Php能做什么，抱歉。我不知道最好的地方是在哪里构建这四个点，或者如何将它们传递给Php中的mySql查询。但是，一旦您有了这四点，就没有什么可以阻止您将自己的SQL statemen和我的SQL statemen结合起来。

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 
and locations.lat between X1 and X2 
and locations.Long between y1 and y2
having distance < 10 ORDER BY distance;

I know with MS SQL I can build a SQL statement that declares four floats (X1, Y1, X2, Y2) and calculates them before the "main" select statement, like I said, I've no idea if this can be done with MySql. However I'd still be inclined to build the four points in C# and pass them as parameters to the SQL query.

我知道使用MS SQL我可以构建一个SQL语句来声明四个浮点数(X1, Y1, X2, Y2)，并在“main”select语句之前计算它们，就像我说的，我不知道用MySql是否可以做到这一点。但是，我仍然倾向于在c#中构建这四个点，并将它们作为参数传递给SQL查询。

Sorry I can't be more help, if anyone can answer the MySQL & Php specific portions of this, feel free to edit this answer to do so.

对不起，我不能提供更多的帮助，如果有人能回答MySQL和Php的特定部分，请随意编辑这个答案。

#3

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.

检查这个报告以得到一个好的答案。基本上，它展示了注释中显示的两种不同的方法，并详细解释了为什么/什么时候应该使用其中一种方法，以及为什么“in the box”计算非常有趣。

Geo Distance Search with MySQL

使用MySQL进行地理距离搜索

#4

on this blog post, the following MySql function was posted. I haven't tested it much, but from what I gathered from the post, if your latitude and longitude fields are indexed, this may work well for you:

在这篇博文中，我们发布了以下MySql函数。我还没有对它进行过多的测试，但是从我从邮报上收集的信息来看，如果您的纬度和经度字段被编入索引，这可能对您很有用:

DELIMITER $$

DROP FUNCTION IF EXISTS `get_distance_in_miles_between_geo_locations` $$
CREATE FUNCTION get_distance_in_miles_between_geo_locations(geo1_latitude decimal(10,6), geo1_longitude decimal(10,6), geo2_latitude decimal(10,6), geo2_longitude decimal(10,6)) 
returns decimal(10,3) DETERMINISTIC
BEGIN
  return ((ACOS(SIN(geo1_latitude * PI() / 180) * SIN(geo2_latitude * PI() / 180) + COS(geo1_latitude * PI() / 180) * COS(geo2_latitude * PI() / 180) * COS((geo1_longitude - geo2_longitude) * PI() / 180)) * 180 / PI()) * 60 * 1.1515);
END $$

DELIMITER ;

Sample usage: Assuming a table called Places with fields latitude & longitude:

示例用法:假设有一个表，名为Places latitude & longitude:

select get_distance_in_miles_between_geo_locations(-34.017330, 22.809500, latitude, longitude) as distance_from_input from places;

选择get_distance_in_miles_locations en_geo_locations(-34.017330、22.809500、纬度、经度)作为distance_from_places输入;

all snagged from this post

所有人都从这柱子上被截住了

#5

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.

这是在MySQL点之间的距离计算查询,我已经使用很长一段数据库,它完美的工作!注意:做更改(数据库名、表名、列等)按照您的要求。

#6

set @latitude=53.754842;
set @longitude=-2.708077;
set @radius=20;

set @lng_min = @longitude - @radius/abs(cos(radians(@latitude))*69);
set @lng_max = @longitude + @radius/abs(cos(radians(@latitude))*69);
set @lat_min = @latitude - (@radius/69);
set @lat_max = @latitude + (@radius/69);

SELECT * FROM postcode
WHERE (longitude BETWEEN @lng_min AND @lng_max)
AND (latitude BETWEEN @lat_min and @lat_max);

source

源

#7

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

详细介绍如何作为MySQL插件安装的完整代码如下: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.

我去年发表了这篇评论。因为好心的@TylerCollier建议我把答案贴在这里。

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

另一种方法是编写一个自定义UDF函数，该函数返回两点的haversine距离。这个函数可以接受输入:

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:

获取距离小于40公里的所有记录。或者:

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.

获取距离小于25英尺的所有记录。

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;
}

#8

A fast, simple and accurate (for smaller distances) approximation can be done with a spherical projection. At least in my routing algorithm I get a 20% boost compared to the correct calculation. In Java code it looks like:

一个快速、简单和精确的(对于较小的距离)近似可以用一个球面投影来完成。至少在我的路由算法中，与正确的计算相比，我得到了20%的提升。在Java代码中，它看起来是:

public double approxDistKm(double fromLat, double fromLon, double toLat, double toLon) {
    double dLat = Math.toRadians(toLat - fromLat);
    double dLon = Math.toRadians(toLon - fromLon);
    double tmp = Math.cos(Math.toRadians((fromLat + toLat) / 2)) * dLon;
    double d = dLat * dLat + tmp * tmp;
    return R * Math.sqrt(d);
}

Not sure about MySQL (sorry!).

不确定MySQL(对不起!)。

Be sure you know about the limitation (the third param of assertEquals means the accuracy in kilometers):

请确保您知道这个限制(assertEquals的第三个参数表示以公里为单位的精度):

    float lat = 24.235f;
    float lon = 47.234f;
    CalcDistance dist = new CalcDistance();
    double res = 15.051;
    assertEquals(res, dist.calcDistKm(lat, lon, lat - 0.1, lon + 0.1), 1e-3);
    assertEquals(res, dist.approxDistKm(lat, lon, lat - 0.1, lon + 0.1), 1e-3);

    res = 150.748;
    assertEquals(res, dist.calcDistKm(lat, lon, lat - 1, lon + 1), 1e-3);
    assertEquals(res, dist.approxDistKm(lat, lon, lat - 1, lon + 1), 1e-2);

    res = 1527.919;
    assertEquals(res, dist.calcDistKm(lat, lon, lat - 10, lon + 10), 1e-3);
    assertEquals(res, dist.approxDistKm(lat, lon, lat - 10, lon + 10), 10);

#9

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. http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL

下面是对MySQL的地理距离搜索的详细描述，该解决方案基于对MySQL实现的Haversine公式。完整的解决方案描述与理论、实现和进一步的性能优化。虽然空间优化部分在我的案例中并不正确。http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL

#10

   select
   (((acos(sin(('$latitude'*pi()/180)) * sin((`lat`*pi()/180))+cos(('$latitude'*pi()/180)) 
    * cos((`lat`*pi()/180)) * cos((('$longitude'- `lng`)*pi()/180))))*180/pi())*60*1.1515) 
    AS distance
    from table having distance<22;

#11

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.

使用MySQL的Geo距离搜索，基于Haversine公式在MySQL中实现的解决方案。这是一个完整的解决方案描述，理论、实现和进一步的性能优化。虽然空间优化部分在我的案例中没有正确工作。

I noticed two mistakes in this:

我注意到其中有两个错误:

1. the use of abs in the select statement on p8. I just omitted abs and it worked.

   在p8的select语句中使用abs。我只是省略了abs，它起作用了。

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.

   空间搜索距离函数p27不转换为弧度或经度乘以cos(纬度),除非他在考虑空间数据加载这个(不能告诉从上下文的文章),但他对p26例子表明他的空间数据点不含有成弧度或角度。

#12

A MySQL function which returns the number of metres between the two coordinates:

一个MySQL函数，返回两个坐标之间的米数:

CREATE FUNCTION DISTANCE_BETWEEN (lat1 DOUBLE, lon1 DOUBLE, lat2 DOUBLE, lon2 DOUBLE)
RETURNS DOUBLE DETERMINISTIC
RETURN ACOS( SIN(lat1*PI()/180)*SIN(lat2*PI()/180) + COS(lat1*PI()/180)*COS(lat2*PI()/180)*COS(lon2*PI()/180-lon1*PI()/180) ) * 6371000

To return the value in a different format, replace the 6371000 in the function with the radius of Earth in your choice of unit. For example, kilometres would be 6367 and miles would be 3957.

要以不同的格式返回值，请在选择单元时将函数中的6371000替换为地球的半径。例如，公里是6367英里，英里是3957英里。

To use the function, just call it as you would any other function in MySQL. For example, if you had a table city, you could find the distance between every city to every other city:

要使用这个函数，只需像在MySQL中调用其他函数一样调用它。例如，如果你有一个桌城，你可以找到每个城市到其他城市的距离:

SELECT
    `city1`.`name`,
    `city2`.`name`,
    ROUND(DISTANCE_BETWEEN(`city1`.`latitude`, `city1`.`longitude`, `city2`.`latitude`, `city2`.`longitude`)) AS `distance`
FROM
    `city` AS `city1`
JOIN
    `city` AS `city2`

#13

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

如果你使用的是MySQL 5.7。*，然后您可以使用st_distance_sphere(POINT, POINT)。

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

#14

I recommend to use the function st_distance_sphere from MySQL5.7, it returns the mimimum spherical distance between two points in meters.

我建议使用MySQL5.7中的函数st_distance_sphere，它会返回米米母的球形距离，在米的两个点之间。

st_distance_sphere(POINT(@lat1,@long1),POINT(@lat2,@long2))

st_distance_sphere(点(@lat1 @long1)点(@lat2 @long2))

I tested and it's faster than use MBRContains

我测试过了，它比使用MBRContains要快

#15

$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";