PHP/MySQL中的地理搜索(距离)(性能)

Question

我有一个MySQL表(MyISAM)，其中包含大约200k个经纬度对条目，我根据从另一个纬度/经度对到另一个纬度/经度对的距离(大圆公式)进行选择。(例如，所有半径在50.281852，2.504883左右的10 all范围内的条目)

我的问题是，这个查询大约需要0,28秒。仅为这200k个条目运行(每天都会继续获得更多条目)。而0,28秒。正常情况下，这个查询非常频繁地运行，因为它支持我的web-app的主要功能，而且通常它是更大查询的一部分。

有没有什么方法可以加快速度呢？显然，MySQL每次都必须遍历所有200k个条目，并对每个条目执行大圆公式。我在Stack Overflow上读到了一些关于geohashing，R-Trees之类的东西，但我不认为这是我想要的方式。部分原因是我从来不是一个数学迷，但更主要的原因是我认为这个问题已经被比我更聪明的人在库/扩展等库中解决了，这个库已经过广泛的测试，并正在定期更新。

MySQL似乎有一个空间扩展，但它没有提供距离函数。我应该寻找另一个数据库来放置这个坐标对吗？PostgreSQL似乎有一个相当成熟的空间扩展。你对它有什么了解吗？或者，PostgreSQL会不会简单地使用大圆公式来获取某个区域内的所有条目？

有没有专门的独立产品或mysql扩展可以做我正在寻找的事情？

或者有没有一个PHP库我可以用来做计算？使用APC，我可以轻松地将经度-长度对放入内存(这200k个条目大约需要5MB)，然后在PHP中运行查询。然而，这种方法的问题是，我会有一个类似SELECT的MySQL查询。从..其中id位于(id1，id2，..)对于所有的结果，可能高达几千个。MySQL处理这些查询的能力如何？然后(因为这是一个处理数字的任务)用PHP做这件事就足够快了吗？

我应该/不应该做什么还有其他想法吗？

为了完整起见，下面是示例查询，去掉了所有不相关的部分(正如我所说的，这通常是连接多个表的大型查询的一部分)：

SELECT id,
       6371 * acos( sin( radians( 52.4042924 ) ) * sin( radians( lat ) ) + cos( radians( 50.281852 ) ) * cos( radians( lat ) ) * cos( radians( 2.504883 ) - radians( lon ) ) ) AS dst
FROM geoloc
HAVING dst <10
ORDER BY dst ASC

Answer 1

计算一个边界框以选择SQL查询的WHERE子句中的行的子集，这样您就只对这部分行执行代价高昂的距离计算，而不是对表中的整个200k记录执行距离计算。此article on Movable Type中描述了该方法(带有PHP代码示例)。然后，您可以在针对该子集的查询中包含Haversine计算，以计算实际距离，并在该点上包含HAVING子句。

它是有助于提高性能的边界框，因为它意味着您只在数据的一小部分上进行昂贵的距离计算。这实际上与Patrick所建议的方法相同，但是Movable链接有对该方法的大量解释，以及可用于构建边界框和SQL查询的PHP代码。

编辑

如果你认为半正弦不够准确，那么还有Vincenty公式。

//  Vincenty formula to calculate great circle distance between 2 locations expressed as Lat/Long in KM

function VincentyDistance($lat1,$lat2,$lon1,$lon2){
    $a = 6378137 - 21 * sin($lat1);
    $b = 6356752.3142;
    $f = 1/298.257223563;

    $p1_lat = $lat1/57.29577951;
    $p2_lat = $lat2/57.29577951;
    $p1_lon = $lon1/57.29577951;
    $p2_lon = $lon2/57.29577951;

    $L = $p2_lon - $p1_lon;

    $U1 = atan((1-$f) * tan($p1_lat));
    $U2 = atan((1-$f) * tan($p2_lat));

    $sinU1 = sin($U1);
    $cosU1 = cos($U1);
    $sinU2 = sin($U2);
    $cosU2 = cos($U2);

    $lambda = $L;
    $lambdaP = 2*M_PI;
    $iterLimit = 20;

    while(abs($lambda-$lambdaP) > 1e-12 && $iterLimit>0) {
        $sinLambda = sin($lambda);
        $cosLambda = cos($lambda);
        $sinSigma = sqrt(($cosU2*$sinLambda) * ($cosU2*$sinLambda) + ($cosU1*$sinU2-$sinU1*$cosU2*$cosLambda) * ($cosU1*$sinU2-$sinU1*$cosU2*$cosLambda));

        //if ($sinSigma==0){return 0;}  // co-incident points
        $cosSigma = $sinU1*$sinU2 + $cosU1*$cosU2*$cosLambda;
        $sigma = atan2($sinSigma, $cosSigma);
        $alpha = asin($cosU1 * $cosU2 * $sinLambda / $sinSigma);
        $cosSqAlpha = cos($alpha) * cos($alpha);
        $cos2SigmaM = $cosSigma - 2*$sinU1*$sinU2/$cosSqAlpha;
        $C = $f/16*$cosSqAlpha*(4+$f*(4-3*$cosSqAlpha));
        $lambdaP = $lambda;
        $lambda = $L + (1-$C) * $f * sin($alpha) * ($sigma + $C*$sinSigma*($cos2SigmaM+$C*$cosSigma*(-1+2*$cos2SigmaM*$cos2SigmaM)));
    }

    $uSq = $cosSqAlpha*($a*$a-$b*$b)/($b*$b);
    $A = 1 + $uSq/16384*(4096+$uSq*(-768+$uSq*(320-175*$uSq)));
    $B = $uSq/1024 * (256+$uSq*(-128+$uSq*(74-47*$uSq)));

    $deltaSigma = $B*$sinSigma*($cos2SigmaM+$B/4*($cosSigma*(-1+2*$cos2SigmaM*$cos2SigmaM)- $B/6*$cos2SigmaM*(-3+4*$sinSigma*$sinSigma)*(-3+4*$cos2SigmaM*$cos2SigmaM)));

    $s = $b*$A*($sigma-$deltaSigma);
    return $s/1000;
}


echo VincentyDistance($lat1,$lat2,$lon1,$lon2);

Answer 2

如果你从不同的角度来处理这个问题呢？

直线上的10公里是：

纬度上的

1. 等于~1‘(分钟)经度上的
2. 等于~6’(分钟)

以此为基础，进行一些快速计算，并在查询中添加到WHERE子句中，移除所有位于'box‘之外的位置，该’box‘是通过添加假定为1’经度& 6‘长的缓冲区而创建的

​

​

基于此图像进行操作：

您正在搜索的

1. 全球定位系统位置(34°12‘34.0"，-85°1’1.0") 34.2094444444，-85.0169444444

1. 您可以找到最小/最大纬度/经度

2a。最小纬度- 34.1927777778，-85.0169444444

2b。最小经度- 34.2094444444，-85.1169444444

2c。最大纬度- 34.2261111111，-85.0169444444

2d。最大经度- 34.2094444444，-84.9169444444

1. 使用每个方向的最小和最大值运行查询

SELECT * FROM geoloc lat >= 34.1927777和lat <= 34.2261111以及long >= -85.1169444和long <= SELECT

您可以将距离计算与SQL查询集成在一起，也可以使用PHP库/类在提取数据后运行距离检查。无论哪种方式，您都将计算次数减少了很大百分比。

我使用以下函数来计算两个US84全球定位系统位置之间的距离。传递了两个参数，每个参数都是一个数组，第一个元素是纬度，第二个元素是经度。我相信它有几英尺的精确度，这应该足以满足除了最铁杆的GPS爱好者之外的所有人的需求。另外，我相信这使用了Haversine距离公式。

$distance = calculateGPSDistance(array(34.32343，-86.342343)，array(34.433223，-96.0032344))；

function calculateGPSDistance($site1, $site2)
{
    $distance = 0;
    $earthMeanRadius = 2.0891 * pow(10, 7);

    $deltaLatitude = deg2rad($site2[0] - $site1[0]);
    $deltaLongitude = deg2rad($site2[1] - $site1[1]);
    $a = sin($deltaLatitude / 2) * sin($deltaLatitude / 2) + cos(deg2rad($site1[0])) * 
        cos(deg2rad($site2[0])) * sin($deltaLongitude / 2) * sin($deltaLongitude / 2);
    $c = 2 * atan2(sqrt($a), sqrt(1-$a));
    $distance = $earthMeanRadius * $c;

    return $distance;
}

更新

我忘了提一下，我的distance函数将返回以英尺为单位的距离。

Answer 3

你可以试试四键。它是一个空间索引，并降低了维度。它将地图细分为多个瓦片，但您可以使用它来存储点。你可以下载我的php类hilbert-curve @ phpclasses.org。它还包括一条z曲线和一条摩尔曲线。重要的是要知道它使用了墨卡托投影。您可以查找Bing地图平铺。它解释了如何使用一个四元键。您需要x，y坐标和z(缩放或深度)值。然后它会给你一个四键。