logo标签列表

在PHP/MySQL中进行地理搜索（距离）（性能）

phpmysqlperformancedistancegis
13
我有一个包含大约200k个经纬度对的MySQL表(MyISAM)。我会基于这些对之间的距离(大圆公式)从中进行选择，以及另一对经纬度的距离。例如: 所有在50.281852, 2.504883半径10公里范围内的条目。
我的问题是，仅仅为了这200k个项目(每天都在增加)，这个查询就需要大约0.28秒才能运行。通常情况下，0.28秒是可以接受的，但由于该查询经常运行且作为Web应用程序主要功能的一部分，因此它可能会成为更大查询的一部分。
有没有什么方法可以提高速度？显然，MySQL必须每次遍历所有200k个条目，并针对每个条目执行大圆公式。我在Stack Overflow上读到了一些关于地理散列、R-Tree等方面的内容，但我不认为那是我想走的路。部分原因是因为我从未是数学的忠实拥护者，但主要是因为我认为这个问题已经被某位比我聪明的人在一个被广泛测试和定期更新的库/扩展程序中解决了。
MySQL似乎有一个空间扩展，但它并没有提供距离函数。我应该寻找另一个数据库来存储这些坐标对吗？ PostgreSQL似乎有一个相当成熟的空间扩展。你了解它吗? 或者PostgreSQL也会像MySQL一样使用大圆公式来获取某个区域内的所有条目吗？
也许已经有一个专门的独立产品或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
当在半径（距离）仅为10英里（15公里）的范围内搜索时，您是否可以省略整个曲率方程并计算圆形？ - GDmac
4个回答
15

如果您从不同的角度解决问题会怎样呢？

10公里直线距离为：

  1. 纬度上约等于1'（分）
  2. 经度上约等于6'（分）

基于此，进行一些快速计算，并在查询中添加到WHERE子句中，删除任何位于以1'纬度和6'经度为假设创建的“框”之外的位置。

gps buffer zone circle

根据这张图片：

  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. 使用每个方向的最小值和最大值运行您的查询

SELECT *

FROM geoloc

WHERE

lat >= 34.1927777 AND

lat <= 34.2261111 AND

long >= -85.1169444 AND

long <= -84.9169444;
您可以将距离计算整合到SQL查询中，或者在获取数据后使用PHP库/类来运行距离检查。两种方式都可以大幅减少计算量。 我使用以下函数来计算两个美国84 GPS位置之间的距离。传递了两个参数，每个参数都是一个数组，第一个元素是纬度，第二个元素是经度。我相信它的精度可达几英尺，这应该足以满足除了最难核心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;
}

更新

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

这对欧洲有效吗？Haversine公式和Great Circle公式有什么区别？ - Dexter
@Bubbles 是的，这个在欧洲应该没有问题。我相信Haversine公式使用大圆公式，但从我的经验来看，在现实世界中它可以给出更准确的距离。你可以在维基百科上了解Haversine的相关知识（http://en.wikipedia.org/wiki/Haversine_formula）。 - Patrick
@epitaph 赢了？赢了还是输了？OP只是在尝试找到更好的方法让他们的网站工作。有时候，最计算效率高的算法并不是最好的选择。在更新生产网站上的代码时，易用性和集成性都很重要。 - Patrick
15

通过计算一个边界框来选择SQL查询WHERE子句中的行的子集，这样你只需要在该行子集上执行昂贵的距离计算，而不是针对表中全部20万条记录进行计算。该方法在Movable Type文章中有描述（附有PHP代码示例）。然后，您可以在对该子集进行的查询中包含Haversine计算，以计算实际距离，并在该点处考虑HAVING子句。

它是边界框帮助提高性能，因为它意味着您仅对数据的一个小子集执行昂贵的距离计算。这实际上是Patrick建议的相同方法，但是Movable Type链接详细解释了该方法，以及可用于构建边界框和SQL查询的PHP代码。

编辑

如果您认为Haversine不够准确，则还有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);
4
如果你使用一个带有 WHERE 子句的边界框，过滤掉明显超出范围的纬度/经度记录（特别是如果你在纬度/经度上有一个索引），那么你是基于边界框选择记录，在进行任何 Haversine/Vincenty/距离计算之前...所以你只对落在边界框内的子集进行距离计算，而不是对 200k 条记录进行计算。如果你尝试测试它，会发现非常明显更快。 - Mark Baker
@PHPDna - 我发布它是因为易于理解。我不试图用四叉树、希尔伯特曲线、摩尔曲线和其他人们无法理解的术语来迷惑他们……我会用基本的说明来发布它是如何工作的……我发布它是因为我可以发布实际可用的代码，而不仅仅是指向一个需要注册才能查看代码的网站库……并且我不会系统地对不同意我的人的答案进行否决。 - Mark Baker
我的回答确实回答了OP的问题...... 它展示了一种减少SQL查询检索行数的方法，使得在不需要将每个条目加载到PHP内存中的情况下更快地搜索200k条目......这是对问题的有效回答；虽然它可能不是OP问题的唯一答案，但它是事实正确的......而且PHPClasses还可以注册（尽管那里有很多糟糕编写的库和好的库），但不是每个人都想要注册一个新网站来获取答案。 - Mark Baker
我了解四叉树的工作原理，目前正在编写SPL的C实现，它甚至不使用任何维度的数组...只是指向树中NW/SW/NE/SE节点的空指针或指针。搜索速度很快，但填充四叉树较慢...特别是在处理大量数据时，必须在使用四叉树之前填充整个四叉树。 - Mark Baker
1
如果有200k条目，那么您正在使用错误大小的边界框。在性能方面，使用地理空间感知数据库更好（特别是在2017年）；但也可以创建摘要表来识别“网格”段中的点数，这可以让您了解边界框是否具有合理的大小；或者使用四叉树等替代数据结构，这对于检索区域内的数据点更有效率。 - Mark Baker
显示剩余10条评论
0
你可以尝试使用Quadkey。它是一种空间索引，可以降低维度。它将地图分成瓦片，但您也可以用它来存储点。您可以在phpclasses.org上下载我的PHP类hilbert-curve。它还包括z-curve和moore-curve。重要的是要知道它使用墨卡托投影。您可以查找Bing地图平铺。它解释了如何使用Quadkey。您需要x、y坐标和z（缩放或深度）值。然后它会给您一个Quadkey。
我看了你的PHP代码，但是我不理解它。你有使用它的例子吗？ - Dexter
这个答案不仅用的是糟糕的英语，而且并没有以任何有意义的方式回答问题。 - Christopher Schmidt
0
到目前为止，我所做的就像@Mark上面描述的一样。我想这对于小型网站来说是可行的解决方案，但对于我的情况来说并不是很好（在以给定点为中心的100x100平方公里盒子内本地化了200,000个条目）。我正在使用Mark的同样技巧，但性能太差了。每秒5个用户查询附近的纬度/经度点几个小时后，查询开始需要10-15秒；而且这发生在我已经在my.cnf中调整了MySQL设置之后。甚至不想想当全球有200万条目时会发生什么。
因此，现在是第二步：Hilbert curve。它应该通过使用一个列（hilbert_number）上的一个索引来解决(lat，lon)列上B树索引的浪费问题（在范围扫描中，只使用B树索引的一部分），hilbert_number是基于Hilbert曲线上的点的纬度/经度坐标计算出的数字。

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

无论如何，我采用的另一个技巧是使用两个边界框，并仅包括灰色/白色点以进行进一步的Haversine测试：

inner and outer BB

我现在需要做的是切换到希尔伯特数并观察其行为。但我怀疑这不会使性能提高10倍！
我自己也使用了类似的边界框调整方法，从一个小的框查询开始，然后向外扩展，但是调整查询以使之前的结果不会再次返回，多个查询，但仍然相当有选择性...正如你所说，对于小到中等数据量来说非常有效，并且比单个边界框更有效。当内置数据库地理空间扩展时，我更喜欢使用它们；但这并不总是可行的，而边界框方法仍然相当有效。 - Mark Baker
对于大数据量，我一直在尝试四叉树，并发现它们在搜索方面非常快，但加载速度慢（对于更大的数据集来说内存占用也很高）。这就是为什么我正在编写一个PHP扩展，将四叉树实现为C数据结构而不是PHP数据结构...并且与在纯PHP中实现相比，无论是搜索还是初始加载都更加高效。 - Mark Baker
对于大数据量，我一直在尝试四叉树，并发现它们在搜索方面非常快，但加载速度慢（对于更大的数据集来说还占用了很多内存）。这就是为什么我正在编写一个PHP扩展，将四叉树实现为C数据结构而不是PHP数据结构...并且在搜索和初始加载方面比纯PHP实现要高效得多...但如果我可以将其序列化，那么真正的好处将会出现，因为它可以被持久化在APC、memcached、redis或类似的缓存中，而不必在每个请求上从数据库中重新构建。 - Mark Baker
在某种程度上，这完全取决于您的查询试图回答什么问题。如果您想要所有半径内的点列表，则甚至不需要计算内部边界框中的点的实际距离（仅需计算框本身的角落），只需针对那些位于内部和外部框之间的点进行计算，以查看它们是否应包括或丢弃；但是，如果您想按距离排序列表，则确实需要为所有潜在条目计算距离。 - Mark Baker
嗯，我想速度方面用Java SE的四叉树应该是没问题的吧？你能给我指一下如何使用四叉树进行伪圆形（而不是伪BB）搜索的好教程吗？最好是适用于Hilbert曲线；最好已经在Java中实现过:D - kellogs
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接