Какой подход быстрее для получения всех POI из MySQL/MariaDB с PHP/Laravel

Поправьте меня если я ошибаюсь.

Есть три подхода, чтобы получить ближайшие дома, которые пользователи создали на моем сайте:

  1. Чтобы создать таблицу с двумя столбцами (широта, долгота), которые оба являются плавающими и говорят:

Вот:

$latitude = 50;
$longitude = 60;

SELECT * FROM my_table
    WHERE (latitude  <= $latitude+10  AND latitude  >= $latitude-10)
      AND (longitude <= $longitude+10 AND longitude >= $longitude-10)

например, 10 здесь означает 1 км.

В этом подходе мы также можем использовать формулу harvesine.

  1. Чтобы объединить эти столбцы (широта, долгота) в один столбец с именем point как тип POINT и снова выполнить поиск по каждой строке один за другим.

  2. Чтобы классифицировать несколько точек (координаты домов, которые создали пользователи) в качестве категории для одного раздела страны, то есть города, и если запрос идет с широтой и долготой $, чтобы увидеть ближайшие дома, я проверю, в какой категории они хранятся. В ПОРЯДКЕ НЕ ДЛЯ ОБОЗРЕНИЯ ВСЕХ СТРОК, а В поиске только той части, к которой принадлежит этот запрос (координата)

Как я полагаю, подход № 1 медленный из-за условий для каждой строки таблицы и снова медленный, если я использую формулу харвесина.

Если я использую ST_Distance, мне снова кажется, что он медленный, потому что снова у него много вычислений.

Но если я использую подход № 3, кажется, что быстрее проверить каждый раздел для конкретного пользователя точки, чем проверить все строки. Я знаю, как установить точку для каждого дома, но я не знаю, как создать несколько домашних позиций, как раздел, возможно, в другой таблице.

Кстати, в новых версиях MySQL и MariaDB пространственные индексы поддерживаются в InnoDB.

Мои вопросы:

  1. Подход № 1 действительно медленный или другие функции ST_* такие же, как этот подход, чтобы проверять все строки с этими формулами, упомянутыми там одна за другой? Какой из них быстрее?

  2. Подход № 2 делает что-то кроме простых условий, чтобы сделать это быстрее? Я имею в виду, вносит ли он какие-либо изменения при использовании типа POINT вместо float и использовании функций ST_* вместо того, чтобы делать это самостоятельно? Я хочу знать, отличается ли алгоритм.

  3. Если подход № 3 является самым быстрым в этих трех подходах, как я могу классифицировать точки, чтобы не искать все строки в таблице?

  4. Как я могу использовать пространственные индексы, чтобы сделать это как можно быстрее?

  5. Если существуют какие-либо другие подходы, и я не упомянул, не могли бы вы сказать, как я могу получить ближайшие дома, просто имея координаты в MySQL/MariaDB в PHP/Laravel?

Спасибо всем

Источник

2 ответа

Решение

Какая формула вы используете для расстояния, не имеет большого значения. Гораздо важнее количество строк, которые вы должны прочитать, обработать и отсортировать. В лучшем случае вы можете использовать индекс для условия в предложении WHERE, чтобы ограничить количество обрабатываемых строк. Вы можете попытаться классифицировать ваши местоположения - но это зависит от характера ваших данных, если это будет работать хорошо. Вам также необходимо выяснить, какую "категорию" использовать. Более общим решением было бы использование SPATIAL INDEX и функции ST_Within().

Теперь давайте запустим несколько тестов..

В моей БД (MySQL 5.7.18) у меня есть следующая таблица:

CREATE TABLE `cities` (
    `cityId` MEDIUMINT(9) UNSIGNED NOT NULL AUTO_INCREMENT,
    `country` CHAR(2) NOT NULL COLLATE 'utf8mb4_unicode_ci',
    `city` VARCHAR(100) NOT NULL COLLATE 'utf8mb4_unicode_ci',
    `accentCity` VARCHAR(100) NOT NULL COLLATE 'utf8mb4_unicode_ci',
    `region` CHAR(2) NULL DEFAULT NULL COLLATE 'utf8mb4_unicode_ci',
    `population` INT(10) UNSIGNED NULL DEFAULT NULL,
    `latitude` DECIMAL(10,7) NOT NULL,
    `longitude` DECIMAL(10,7) NOT NULL,
    `geoPoint` POINT NOT NULL,
    PRIMARY KEY (`cityId`),
    SPATIAL INDEX `geoPoint` (`geoPoint`)
) COLLATE='utf8mb4_unicode_ci' ENGINE=InnoDB

Данные поступают из базы данных городов свободного мира и содержат 3173958 (3,1 млн) строк.

Обратите внимание, что geoPoint избыточен и равен POINT(longitude, latitude),

Concider пользователь находится где-то в Лондоне

set @lon = 0.0;
set @lat = 51.5;

и вы хотите найти ближайшее место из cities Таблица.

"Тривиальный" запрос будет

select c.cityId, c.accentCity, st_distance_sphere(c.geoPoint, point(@lon, @lat)) as dist
from cities c
order by dist
limit 1

Результат

988204 Blackwall 1085.8212159861014

Время выполнения: ~ 4.970 сек

Если вы используете менее сложную функцию ST_Distance()вы получите тот же результат со временем выполнения ~ 4.580 сек - что не так уж и много.

Обратите внимание, что вам не нужно хранить географическую точку в таблице. Вы можете так же хорошо использовать (point(c.longitude, c.latitude) вместо c.geoPoint, К моему удивлению, это даже быстрее (~3,6 с ST_Distance и ~ 4,0 сек для ST_Distance_Sphere). Это может быть даже быстрее, если бы у меня не было geoPoint колонка вообще. Но это все равно не имеет большого значения, так как вы не хотите, чтобы пользователь ждал, так что регистрируйте изменение, если вы можете добиться большего.

Теперь давайте посмотрим, как мы можем использовать пространственный индекс с ST_Within(),

Вам нужно определить полигон, который будет содержать ближайшее местоположение. Простой способ - использовать ST_Buffer(), который сгенерирует многоугольник с 32 точками и будет почти кругом *.

set @point = point(@lon, @lat);
set @radius = 0.1;
set @polygon = ST_Buffer(@point, @radius);

select c.cityId, c.accentCity, st_distance_sphere(c.geoPoint, point(@lon, @lat)) as dist
from cities c
where st_within(c.geoPoint, @polygon)
order by dist
limit 1

Результат тот же. Время выполнения составляет ~ 0,000 секунд (так говорит мой клиент (HeidiSQL)).

* Обратите внимание, что @radius обозначается в градусах и, таким образом, многоугольник будет больше похож на эллипс, а не на круг. Но в моих тестах я всегда получал тот же результат, что и с простым и медленным решением. Я хотел бы исследовать больше крайних случаев, прежде чем использовать его в своем производственном коде.

Теперь вам нужно найти оптимальный радиус для вашего приложения / данных. Если он слишком маленький - вы можете не получить результатов или пропустить ближайшую точку. Если он слишком большой - вам может понадобиться обработать слишком много строк.

Вот несколько цифр для данного теста:

  • @radius = 0,001: результата нет
  • @radius = 0,01: ровно одна локация (вроде повезло) - время выполнения ~ 0,000 сек
  • @radius = 0,1: 55 локаций - время выполнения ~ 0,000 сек.
  • @radius = 1.0: 2183 локаций - время выполнения ~ 0.030 сек
Источник

Ограничивающая коробка и Haversine

В вашем брифе SELECT, вы используете подход "ограничивающего прямоугольника", при котором на карте рисуется грубый квадрат. Однако у него есть пара недостатков.

  • 50 и 60 предположительно в градусах; Вы говорите, что 10 в км. Вы не можете смешивать их без преобразования одного или другого.
  • градусы долготы короче градуса широты; cos() необходимо исправить это.

Их наличие помогает ограничить рамку, которая значительно фильтрует строки, а затем дополнительный тест haversine округляет область охвата теста.

INDEX(latitude)
INDEX(longitude)

Этот подход имеет "среднюю" производительность - один из индексов будет использоваться с ограничительной рамкой, тем самым быстро ограничивая кандидатов полосой восток-запад (или север-юг) по всему земному шару. Но это все еще может быть много кандидатов.

Отфильтровав большинство строк, количество вызовов Haversine не так уж и плохо; не беспокойтесь о производительности функции.

Если у вас есть один миллион домов, последний ограничивающий прямоугольник, содержащий 5 домов (плюс несколько, не прошедших проверку на хаверсин), вероятно, будет касаться нескольких тысяч строк - из-за использования только одного из двух индексов. Это все же намного лучше, чем выборка всех миллионов строк и проверка каждой из них с помощью функции расстояния.

ТОЧКА и ПРОСТРАНСТВЕННЫЙ индекс

Переключение на POINT требует перехода на SPATIAL индекс. В этом режиме ST_Distance_Sphere() доступен вместо haversine. (Внимание: эта функция существует только в самых последних версиях.)

Отфильтровав большинство строк, количество обращений к ST_Distance или же ST_Distance_Sphere не так уж плохо; не беспокойтесь о производительности функции.

SPATIAL поиски используют R-Trees. Я не очень хорошо понимаю их производительность в вашем запросе.

Подход 3

Начав с другой классификации точек, вы добавите сложность. Вы также добавляете необходимость проверять соседние регионы, чтобы увидеть, есть ли поблизости точки. Я не могу судить об относительной производительности без более подробной информации.

Мой подход

У меня есть некоторый сложный код, который масштабируется до произвольного количества точек. Поскольку ваш набор данных, вероятно, достаточно мал для кэширования в ОЗУ, он может оказаться для вас излишним. http://mysql.rjweb.org/doc.php/latlng

Только для миллиона домов приведенная выше пара индексов может быть "достаточно хорошей", чтобы вам не приходилось прибегать к "моему алгоритму". Мой алгоритм будет касаться только около 20 строк, чтобы получить желаемые 5 - независимо от общего количества строк.

Другие заметки

Если вы храните оба лат / лнг и POINTстол будет громоздким; имейте это в виду, если пытаетесь смешать ограничивающие рамки и ST функции.

Источник
Другие вопросы по тегам