В настоящее время часто встречается задача - на карте расположено множество точек и необходимо выделить их подмножество (отфильтровать) по критерию расстояния от некоторой “особой” точки. В качестве примеров укажем сайты маркетплейсов, где точки пункты выдачи, в сетевых компаниях это офисы на карте, логистические компании отслеживают передвижение транспортных средств, операторы такси находят на карте ближайшие автомобили и можно перечислить еще много областей применения. При кажущейся простоте постановки задачи её решение требует значительных ресурсов, так как запросы к базе данных, как правило, очень тяжелые. Здесь на примере задачи ‘Пункты выдачи’ с фильтрацией по расстоянию (радиусу) от накопительного узла товаров показывается как можно сократить количество обработанных строк в запросе. Реализация задачи на БД mySQL.
Координаты исходной точки могут быть получены несколькими способами, первый если устройство пользователя оборудовано GPS и пользователь разрешил передачу своих координат, то мы получаем координаты пользователя без затруднений, второй способ менее точный мы получаем координаты пользователя из его IP, для этого используется библиотека maxmind.
В БД mySQL 5.7 появилась встроенная функция ST_Distance_Sphere для расчета (евклидово) расстояния между двумя точками. Данная функция принимает широту и долготу двух точек, а возвращает расстояние между ними в метрах, далее мы производим сравнение с критической величиной радиуса и определяем попадает ли данная точка в круг с этим радиусом.
WHERE (ST_Distance_Sphere(point(longitude, latitude), point(longitude2, latitude2)) ) <= radius
На этом решение задачи можно было бы закончить, но если выполнить данный запрос на миллионе строк, то запрос будет заметно тормозить.
На лицо необходимость предварительной фильтрации. Было решено производить фильтрацию при помощи квадрата, внутрь которого будет вписана окружность критического радиуса. При этом пункты выдачи, которые попадают в квадрат, но не попадают в окружность в последующем будут отфильтрованы как раз при помощи функции ST_Distance_Sphere , то есть львиная доля фильтрации придется именно на квадрат. Итак, как сделать фильтрацию по квадрату более быстрой, чем фильтрация при помощи функции ST_Distance_Sphere.
Вычисляем координаты вершин квадрата.
Сторона квадрата будет равняться диаметру окружности, то есть радиус*2.
Формула вычисления координат вершин квадрата:
Distance - искомая нами дистанция в километрах (радиус).
Экваториальная окружность Земли составляет около 40 075 км (не будем использовать меридианную 40 008).
Окружность 360 градусов.
Для полного понимания данных расчетов необходимо понимать:
Широта и долгота измеряются в градусах:
градусом географической широты является 1/180 часть меридиана (latitude - широта значения от -90 до 90)
градусом географической долготы является 1/360 часть экватора (longitude - долгота значения от -180 до 180)
Небольшое отхождение от темы. Данная формула не работает для тех кто считает что земля плоская))), а таких с каждым днем все больше(((
Итак, мы вычислили координаты вершин квадрата, в который вписан наш круг и можем применить промежуточную фильтрацию + основную. Фильтрация по WHERE between работает быстрее, чем встроенная фильтрация по ST_Distance_Sphere
WHERE longitude between longitudeMin and longitudeMax
and latitude between latitudeMin and latitudeMax
and (ST_Distance_Sphere(point(longitude, latitude),
point(longitude2, latitude2)) ) <= radius // radius в метрахВ качестве оптимизации добавляем индекс на столбцы:longitude, latitude
CREATE INDEX coordinate ON table_name (latitude, longitude);
Данная оптимизация позволила без тормозов обрабатывать 2 млн. записей.
Но было решено на этом не останавливаться и произвести еще одну оптимизацию.
В связи с тем что пользователи чаще всего используют фильтр с радиусом 0-5 км, было решено добавить еще один столбец в таблицу для фильтрации, этот столбец будет целочисленными и его значение будет от -90 000 до 90000.
ALTER TABLE table_name ADD COLUMN latitudeInt INT DEFAULT NULL
Заполнять этот столбцы мы будем по формуле: latitudeInt = Math.round(latitude*1000). Итак, что же мы делаем, по факту имея в БД значение latitude хх.хххххххх мы его приводим к целочисленному виду и округляем до 5 знаков ххххх. При текущей фильтрации с радиусом 0-5 км пяти знаков достаточно для произведения фильтрации, тем самым мы упрощаем процесс фильтрации, тем более фильтрацию с помощью функции ST_Distance_Sphere мы оставляем.
Представим, что координаты исходной точки latitude = 10.111 и longitude = 41.000 по формуле выше вычисляем:
longitude min - 40.98951994951971
longitude max - 41.01048005048029
latitude min - 10.10051684341859
latitude max - 10.12131565814199
По latitude min и latitude max вычисляем искомый диапазон latitudeInt.
getRange(latMin, latMax) {
const latitudeMinInt = Math.floor(latMin * 1000)
const latitudeMaxInt = Math.ceil(latMax * 1000)
const mas = [latitudeMinInt];
for (let index = 1; index < latitudeMaxInt - latitudeMinInt + 1; index++) {
mas.push(latitudeMinInt+index)
}
return mas;
}В нашем случае диапазон будет:
[10102,10103,10104,10105,10106,10107,10108,10109,10110,10111,10112,10113,10114,10115,10116,10117,10118,10119,10120,10121,10122]
В случае если несколько пунктов выдачи попали например, в диапазон 10107 - 10108, то фактически мы их склеили одним значением поля latitudeInt
Теперь фильтры будут представлены следующим образом:
latitudeIntMas = [10102,10103,10104,10105,10106,10107,10108,10109,10110,10111,10112, 10113,10114,10115,10116,10117,10118,10119,10120,10121,10122]
longitudeMin - 40.98951994951971
longitudeMax -41.01048005048029
WHERE latitudeInt in (latitudeIntMas )
AND longitude between longitudeMin and longitudeMax
AND (ST_Distance_Sphere(point(longitude, latitude), point(longitude2, latitude2)) ) <= radius // radius в метрах
Так же добавляем индекс
CREATE INDEX latitudeInt ON table_name (latitudeInt);
Заметим, что данные расчеты не учитывают кривизну земли, но для основного запроса потребителя 0-5 км погрешность не является существенной.
Я постарался максимально подробно рассказать о моем кейсе. Надеюсь этот опыт поможет другим разработчикам, так как данный функционал используется на многих проектах. Если вы решали подобные задачи, пишите в комментариях, будет интересно посмотреть решения других разработчиков.
