Гео-поиск (расстояние) в PHP / MySQL (производительность)

Question

У меня есть MySQL-таблица (MyISAM), содержащая около 200 тыс. Записей пар лат / лонг, из которых я выбираю, исходя из расстояния между парами (формула большого круга) из другой пары лат / лонг.(например, все записи, которые находятся в радиусе 10 км от 50.281852, 2.504883)

Моя проблема в том, что этот запрос занимает около 0,28 сек.запустить только для этих 200 000 записей (которые продолжают получать больше с каждым днем).Время 0,28 сек.было бы нормально нормально, этот запрос выполняется очень часто, так как он обеспечивает основную функцию моего веб-приложения, и часто это часть большого запроса.

Есть ли способ ускорить это?Obviosly MySQL должен каждый раз проходить все 200 тыс. Записей и выполнять формулу большого круга для каждой записи.Я читал кое-что о гео-хешировании, R-деревьях и тому подобном здесь на stackoverflow, но я не думаю, что это именно то, чего я хочу.Частично потому, что я никогда не был большим поклонником математики, но в основном потому, что я думаю, что эта проблема уже была решена кем-то умнее меня в библиотеке / расширении / и т.д.это было тщательно протестировано и регулярно обновляется.

Кажется, что MySQL имеет пространственное расширение, но у него нет функции расстояния.Должен ли я смотреть на другую базу данных, чтобы поместить эти пары координат?PostgreSQL, похоже, имеет довольно зрелое пространственное расширение.Вы знаете что-нибудь об этом?Или PostgreSQL слишком просто использует формулу большого круга для получения всех записей в определенном регионе?

Возможно, существует специализированный автономный продукт или расширение mysql, которое уже делает то, что я ищу?

Или, может быть, есть библиотека PHP, которую я мог бы использовать для расчетов?Используя APC, я мог легко поместить пары lat-long в память (эти 200-килобайтные записи занимают около 5 МБ), а затем выполнить запрос внутри PHP.Однако проблема с этим подходом состоит в том, что тогда у меня будет запрос MySQL, такой как SELECT .. FROM .. WHERE, идентификатор в (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

Что если вы подойдете к задаче под другим углом?

10 км по прямой линии:

1. на широте равно ~ 1 '(минута)
2. по долготе равно ~ 6 '(минут)

Используя это в качестве основы, сделайте небольшую математику и добавьте в свой запрос предложение WHERE, удалив все местоположениякоторые находятся вне «поля», созданного путем добавления буферной зоны с допущением 1 'lat & 6' long

Работа с этим изображением:

1. GPS-местоположение, которое вы ищете (34 ° 12 '34.0 ", -85 ° 1' 1.0") [34.2094444444, -85.0169444444]

2. Вы найдете минимальную / максимальную широту /долгота

   2а.Мин. Широта - 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 для запуска проверки расстояния после извлечения данных.В любом случае вы сократили количество вычислений на большой процент.

Я использую следующую функцию для вычисления расстояния между двумя местоположениями US84 GPS.Передаются два параметра, каждый из которых представляет собой массив, первый элемент которого представляет собой широту, а второй элемент - долготу.Я считаю, что он имеет точность в несколько футов, что должно быть достаточно для всех, кроме самых сложных основных GPS-офилов.Кроме того, я полагаю, что здесь используется формула расстояния Хаверсайна.

$ distance = calculateGPSDistance (массив (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 2

Рассчитайте ограничивающий прямоугольник, чтобы выбрать подмножество строк в предложении WHERE вашего SQL-запроса, чтобы вы выполняли только дорогостоящее вычисление расстояния для этого подмножества строк, а не для всех записей 200 КБ в вашей таблице.Метод описан в этой статье на Movable Type (с примерами кода PHP).Затем вы можете включить вычисление Haversine в ваш запрос по этому подмножеству, чтобы вычислить фактические расстояния, и учесть условие HAVING в этой точке.только делать дорогостоящий расчет расстояния на небольшом подмножестве ваших данных.По сути, это тот же метод, который предложил Патрик, но ссылка «Подвижный тип» содержит подробные объяснения метода, а также PHP-код, который можно использовать для создания ограничивающего прямоугольника и вашего запроса SQL.

РЕДАКТИРОВАТЬ

Если вы не думаете, что haversine является достаточно точным, то есть также формула Винсенти.

//  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 3

То, что я делал до сих пор, так же, как @Mark, описанный выше. Полагаю, что это жизнеспособное решение для небольших сайтов, но не очень хорошее для моего случая (200 тыс. Записей, локализованных внутри блока размером 100х100 кв. Км, сосредоточенного вокруг заданной точки. Я использовал этот же прием Марка, но производительность слишком низкая. 5 пользователей / второй запрос на ближайшие точки широты / долготы в течение нескольких часов, и запросы начинают занимать до 10 - 15 секунд, и это происходит после Я изменил настройки mySQL в my.cnf. Даже не хочу думать о том, что произойдет, когда во всем мире будет 2 миллиона записей.

Итак, время для шага 2: Кривая Гильберта . Это должно решить проблему индекса B-дерева для столбцов (широта, долгота), которая является расточительной (при сканировании в диапазоне, используется только одна часть индекса B-дерева), используя только один индекс на один столбец (hilbert_number). hilbert_number - это число, рассчитываемое на основе координат широты / долготы точки на кривой Гильберта.

Но осталась вторая проблема, состоящая в проверке расстояния между фиксированной точкой и всем от предыдущего поднабора результатов по формуле Хаверсина. Эта часть может быть очень медленной. Так что я думал о том, чтобы как-то более непосредственно проверить расстояние, поместить все на кривую Гильберта и применить некоторую битовую маску к этому подмножеству результатов вместо применения формулы Хаверсайна. Я просто не знаю, как бы я поступил об этом ...

В любом случае, другой прием, который я использовал для уменьшения количества точек в подмножестве результатов, заключался в том, чтобы использовать два ограничивающих прямоугольника и включать в подмножество только серые / белые точки для дальнейшего тестирования Хаверсайна:

Что мне сейчас нужно сделать, так это переключиться на числа Гильберта и посмотреть, как оно себя ведет. Но я сомневаюсь, что это увеличит производительность в 10 раз!

Answer 4

Вы можете попробовать Quadkey. Это пространственный индекс и уменьшить размерность. Карта подразделяется на тайлы, но вы можете использовать ее для хранения очков. Вы можете скачать мой php класс hilbert-curve @ phpclasses.org. Он также включает в себя z-кривую и кривую Мура. Важно знать, что он использует проекцию Меркатора. Вы можете искать плитки карт Bing. Это объясняет, как использовать Quadkey. Вам нужны координаты x, y и значение z (увеличение или глубина). Тогда это дает вам quadkey.