PHP/MySQL中的地理搜索(距离)(性能) [英] Geo-Search (Distance) in PHP/MySQL (Performance)

问题描述

我有一个MySQL表(MyISAM)，其中包含我根据与另一对lat/long对之间的距离(大圆公式)从中选择的大约20万个lat/long对条目. (例如，距离50.281852，2.504883在10公里半径内的所有条目)

I have a MySQL-table (MyISAM) containing about 200k entries of lat/long pairs that I select from, based on the pairs distance (great circle formula) from another lat/long pair. (e.g. all entries that are within a 10km radius around 50.281852, 2.504883)

我的问题是此查询大约需要0.28秒.仅针对这200k条目运行(每天仍在增加).而0.28秒.通常情况下会很好，此查询会经常运行，因为它会增强我的Web应用程序的主要功能，而且通常是较大查询的一部分.

My problem is that this query takes about 0,28 sec. to run just for those 200k entries (which continue to get more every day). While 0,28 sec. would be fine normally, this query runs very often as it powers the main feature of my web-app, and often times it's part of a larger query.

有什么办法可以加快速度吗?显然，MySQL每次必须遍历所有200k条目，并为每个条目执行大圈公式.我在stackoverflow上阅读了一些有关geohashing，R-Trees之类的内容，但是我不认为这是我想要的方式.部分原因是我从来都不是数学的忠实拥护者，但主要是因为我认为这个问题已经由比我聪明的人在图书馆/扩展名/等等中解决了.已经过广泛测试，并且会定期更新.

Is there any way to speed this up? Obviosly MySQL has to run through all 200k entries every time and perform the great circle formula for every entry. I read something about geohashing, R-Trees and the like here on stackoverflow but I don't think that's the way I want to go. Partly because I've never been a big fan of maths, but mostly because I think that this problem has already been solved by someone smarter than me in a library/extension/etc. that has been tested extensively and is being updated regularly.

MySQL似乎具有空间扩展性，但没有提供距离功能.我是否应该在寻找另一个数据库来放置这些坐标对? PostgreSQL似乎具有相当成熟的Spatial扩展.你对此一无所知吗?还是PostgreSQL只是简单地使用大圆公式来获取特定区域内的所有条目?

MySQL seems to have a spatial extension but that one doesn't provide a distance function. Should I be looking at another database to put this coordinate-pairs in? PostgreSQL seems to have a fairly mature Spatial extension. Do you know anything about it? Or would PostgreSQL too simply just use the great circle formula to get all entries within a certain region?

也许有专门的独立产品或mysql扩展已经可以满足我的需求吗?

Is there maybe a specialized stand-alone product or mysql-extension that already does what I'm looking for?

或者也许我可以使用一个PHP库来进行计算?使用APC，我可以轻松地将经纬度对放入内存(200k条目需要约5MB)，然后在PHP内运行查询.但是，这种方法的问题是，然后我将有一个SELECT .. FROM .. WHERE id在(id1，id2，..)中的MySQL查询，因为所有结果最多可达几千个. MySQL如何处理此类查询?然后(由于这是一个数字运算任务)在PHP中执行此操作是否足够快?

Or is there maybe A PHP library I could use to do the calculations? Using APC I could easily fit the lat-long pairs into memory (those 200k entries take about 5MB) and then run the query inside of PHP. The problem with this approach however is that then I'd have a MySQL query like SELECT .. FROM .. WHERE id in (id1, id2, ..) for all the results wich can be up to a few thousand. How well does MySQL handle Queries like these? And then (since this is a number-crunching task) would doing this in PHP be fast enough?

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

Any other Ideas what I should/shouldn't do?

对于完整性，这是示例查询，其中删除了所有不相关的部分(如我所说，通常这是我联接多个表的较大查询的一部分):

For completenes, here is the sample query, stripped of any irrelevant parts (as I said, usually this is part of a bigger query where I join multiple tables):

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子句中的行的子集，以便您仅对它执行昂贵的距离计算行的子集，而不是针对表中的整个200k记录.此方法在有关可移动类型的文章(使用PHP代码示例).然后，您可以针对该子集在查询中包含Haversine计算，以计算实际距离，并在该点将HAVING子句作为因子.

Calculate a bounding box to select a subset of the rows in the WHERE clause of your SQL query, so that you're only executing the expensive distance calculation on that subset of rows rather than against the entire 200k records in your table. The method is described in this article on Movable Type (with PHP code examples). Then you can include the Haversine calculation in your query against that subset to calculate the actual distances, and factor in the HAVING clause at that point.

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

It's the bounding box that helps your performance, because it means you're only doing the expensive distance calculation on a small subset of your data. This is effectively the same method that Patrick has suggested, but the Movable Type link has extensive explanations of the method, as well as PHP code that you can use to build the bounding box and your SQL query.

编辑

如果您认为Haversine不够准确，那么还有Vincenty公式.

If you don't think haversine is accurate enough, then there's also the Vincenty formula.

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

这篇关于PHP/MySQL中的地理搜索(距离)(性能)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！