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

我有一个MySQL表（MyISAM），其中包含大约200k条经纬度/长对，根据来自另一个纬度/长度对的距离（大圆公式）select。 （例如，在50.281852，2.504883附近的10km范围内的所有条目）

我的问题是，这个查询大约需要0.28秒。 只为那些200k条目运行（每天继续获得更多）。 虽然0,28秒 通常会很好，这个查询运行的频率非常高，因为它支持我的web应用程序的主要function，而且通常是更大查询的一部分。

有什么办法可以加速吗？ 显然，MySQL必须每次运行所有200k条目，并为每个条目执行大圆公式。 我在这里阅读了一些关于geohashing，R-Trees之类的东西，但是我不认为这是我想要去的方式。 部分原因是我从来没有成为一个math迷，但主要是因为我认为这个问题已经被图书馆/扩展等比我聪明的人解决了。 已经过广泛的testing，并且正在定期更新。

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

有可能是一个专门的独立产品或MySQL的扩展已经做了我在找什么？

或者可能有一个PHP库，我可以用来做计算？ 使用APC，我可以很容易地把经纬度对放入内存（这些200k条目大约需要5MB），然后在PHP中运行查询。 然而，这种方法的问题是，那么我会有一个MySQL查询像SELECT .. FROM .. WHERE id（id1，id2，..）所有的结果至多可以达到几千。 MySQL如何处理这些查询？ 然后（因为这是一个数字处理任务）会这样做在PHP中足够快？

任何其他的想法我应该/不应该做什么？

完整版，这里是示例查询，剥离了任何不相关的部分（正如我所说，通常这是一个更大的查询，我join了多个表的一部分）： 

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

谢谢！

计算边界框以在SQL查询的WHERE子句中select行的子集，以便仅对该行子集执行昂贵的距离计算，而不是针对表中的整个200klogging。 这个方法在Movable Type这篇文章中有介绍（用PHP代码实例）。 然后，可以在查询中将Haversine计算包含在该子集中，以计算实际距离，并在该点处考虑HAVING子句。

边界框可以帮助您的性能，因为这意味着您只需要对数据的一小部分进行昂贵的距离计算。 这与Patrick所build议的方法实际上是一样的，但Movable Type链接对该方法以及可用于构build边界框和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);

如果从另一个angular度来看问题呢？

直线10公里是：

  1. 在纬度上等于〜1'（分钟）
  2. 在经度上等于〜6'（分钟）

以此为基础，做一些快速的math计算，并在查询中添加WHERE子句，删除通过添加缓冲区假设长度为1'lat＆6'而创build的“框”之外的任何位置

GPS缓冲区圈

从这个图像工作：

  1. 您正在search的GPS位置（34°12'34.0“，-85°1'1.0”）[34.2094444444，-85.0169444444]

  2. 您可以find最小/最大纬度/经度

    2A。 最低纬度 – 34.1927777778，-85.0169444444

    2B。 Min Longitude – 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库/类来运行距离检查。 无论哪种方式，你已经减less了大量的计算。

我使用以下函数计算两个US84 GPS位置之间的距离。 传递两个参数，每个参数都是一个数组，其中第一个元素是纬度，第二个元素是经度。 我相信它有一个准确的几英尺，这应该是足够的，除了最难的核心GPS ophiles。 此外，我相信这使用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; }

UPDATE

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

我到现在为止所做的就像上面描述的@Mark一样。 一个可行的小网站解决scheme我觉得，对于我的情况来说，这只是一个不错的例子（200k条目集中在一个100×100平方公里的盒子里，以一个特定的点为中心），我使用了Mark的这个技巧，但是性能太差，5个用户/第二个查询附近经纬度的时间为几个小时，查询开始时间为10 – 15秒;这是在my.cnf中调整了mySQL设置之后发生的，甚至不想去想那时会发生什么全球将有200万人参赛。

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

但是，第二个问题，testing固定点和前一个结果子集之间的距离，通过Haversine公式仍然存在。 那部分可能很慢。 所以我正在考虑以某种方式更直接地testing距离，把所有的东西放在希尔伯特曲线上，然后对结果子集应用一些位掩码，而不是应用Haversine公式。 我只是不知道该怎么去…

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

内部和外部的BB

我现在需要做的是切换到希尔伯特数字，看看它是如何performance的。 但是我怀疑这会增加10倍的performance！

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

Interesting Posts