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

Question

我有一个 MySQL 表 (MyISAM)，其中包含大约 200k 个经纬度对条目，我根据与另一个纬度/经度对的距离(大圆公式)从中选择这些条目。 (例如，50.281852、2.504883 周围 10 公里半径范围内的所有条目)

我的问题是这个查询大约需要 0.28 秒。只为那些 200k 条目运行(每天都在继续增加)。而 0,28 秒。通常情况下会很好，这个查询经常运行，因为它支持我的网络应用程序的主要功能，而且它经常是更大查询的一部分。

有什么办法可以加快速度吗？显然，MySQL 每次都必须遍历所有 200k 条目，并对每个条目执行大圆公式。我在 Stack Overflow 上阅读了一些关于 geohashing、R-Trees 等的内容，但我认为这不是我想要的方式。部分是因为我从来都不是数学的忠实粉丝，但主要是因为我认为这个问题已经被比我更聪明的人在图书馆/扩展/等方面解决了。已经过广泛测试并定期更新。

MySQL 似乎具有空间扩展功能，但不提供距离功能。我应该查看另一个数据库来放入这个坐标对吗？ PostgreSQL 似乎有一个相当成熟的空间扩展。你知道吗？或者 PostgreSQL 是否会简单地使用大圆公式来获取特定区域内的所有条目？

是否有专门的独立产品或 mysql 扩展已经满足了我的需求？

或者是否有我可以用来进行计算的 PHP 库？使用 APC，我可以轻松地将经纬度对放入内存(这 200k 个条目大约需要 5MB)，然后在 PHP 中运行查询。然而，这种方法的问题是，然后我会有一个 MySQL 查询，如 SELECT .. FROM .. WHERE id in (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 Type 链接对该方法进行了广泛的解释，以及可用于构建边界框和 SQL 查询的 PHP 代码。

编辑

如果您认为半正弦不够准确，那么还有文森蒂公式。

//  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);