PHP/MySQL 中的地理搜索（距离）（性能）

Question

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

我的问题是此查询大约需要 0.28 秒。仅针对这 20 万条条目运行（每天都会增加更多）。而 0.28 秒。通常情况下没问题，这个查询经常运行，因为它为我的网络应用程序的主要功能提供了支持，而且很多时候它是更大查询的一部分。

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

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

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

或者是否有一个 PHP 库可以用来进行计算？使用 APC，我可以轻松地将经纬度对放入内存中（这 200k 条目大约需要 5MB），然后在 PHP 中运行查询。然而，这种方法的问题是，然后我会有一个像 SELECT .. FROM .. WHERE id in (id1, id2, ..) 这样的 MySQL 查询来获取最多可达几千个的所有结果。 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 记录执行昂贵的距离计算。该方法在关于 Movable Type 的文章中进行了描述（使用 PHP代码示例）。然后，您可以在针对该子集的查询中包含半正矢计算，以计算实际距离，并在该点考虑 HAVING 子句。

边界框有助于提高性能，因为这意味着您只需对一小部分数据进行昂贵的距离计算。这实际上与 Patrick 建议的方法相同，但 Movable Type 链接对该方法以及可用于构建边界框和 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'（分钟）

以此为基础，做一些快速数学运算，然后在查询中添加到 < code>WHERE 子句删除“框”之外的任何位置，该“框”是通过添加缓冲区（假设纬度为 1'）而创建的。 6 英尺长

使用此图像：

1. 您正在搜索的 GPS 位置 (34° 12' 34.0", -85° 1' 1.0") [34.2094444444, -85.0169444444]

2. 您找到最小/最大纬度/经度

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

   2b。分钟经度 - 34.2094444444，-85.1169444444

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

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

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

   <前><代码>选择*

   来自地质定位

   在哪里

   纬度 >= 34.1927777 并且

   纬度 <= 34.2261111 并且

   长 >= -85.1169444 并且

   长 <= -84.9169444；

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

我使用以下函数来计算两个 US84 GPS 位置之间的距离。传递两个参数，每个参数都是一个数组，第一个元素是纬度，第二个元素是经度。我相信它的精度可达几英尺，这对于除了最铁杆的 GPS 爱好者之外的所有人来说应该足够了。另外，我相信这使用了半正矢距离公式。

$距离 = 计算GPS距离(数组(34.32343, -86.342343), 数组(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;
}

更新

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

Answer 3

到目前为止我所做的就是上面@Mark 所描述的。我想对于小型网站来说这是一个可行的解决方案，只是对我的情况不太好（200k 条目本地化在以给定点为中心的某个 100x100 平方公里的盒子内。我正在使用 Mark 的相同技巧，但性能太差了。5 个用户/第二次查询附近的纬度/经度点几个小时，查询开始需要长达 10 - 15 秒的时间；这种情况发生在我调整了 my.cnf 中的 mySQL 设置之后。想想当全球有 200 万个条目时会发生什么

所以，现在是第 2 步：希尔伯特曲线。 。
它应该通过在一列（hilbert_number）上仅使用一个索引来解决（lat，lon）列上的B树索引是浪费的问题（在范围扫描中，仅使用B树索引的一部分）。 hilbert_number 是根据希尔伯特曲线上点的纬度/经度坐标计算得出的数字。

但第二个问题仍然存在，即通过半正矢公式测试固定点与先前结果子集中的所有内容之间的距离。这部分可能会非常慢。因此，我正在考虑以某种方式更直接地测试距离，将所有内容放在希尔伯特曲线上，并对结果子集应用一些位掩码，而不是应用半正弦公式。我只是不知道该怎么做...

无论如何，我用来减少结果子集中点数的另一个技巧是使用两个边界框，并在子集中仅包含灰色/白色点进一步的半正矢测试：

我现在需要做的是切换到希尔伯特数并看看它的行为。但我怀疑这是否会提高 10 倍的性能！

Answer 4

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