Comments 41
latitude - 2
longitude - 2
... WHERE latitude > 1 AND latitude < 3 AND longitude > 1 AND longitude < 3
А потом уже искал более точными алгоритмами, если это требовалось.
WHERE x BETWEEN X(@top_lft) AND X(@bot_rgt)
AND y BETWEEN Y(@top_lft) AND Y(@bot_rgt)
SELECT g.name, geodist(X(@src), Y(@src), x, y) AS dist
т.е. функция вызовется всех записей в таблице, и только потом уже выполнится условие.
select a
from t
where a > ? and a < ? and a*a < ?
и
select a, a*a as s
from t
where a > ? and a < ?
having s < ?
Планировщик показывает одинаковую картину, при наличии индекса по «a»
a*a — достаточный пример неиндексируемого выражения, чтобы проверить описанное выше.
Скорость вычисления расстояния с помощью хранимой процедуры — это отдельный вопрос, не имеющий отношения к вашему замечанию о «предварительной выборке».
А тесты скорости при выборке большого количества записей были бы очень кстати.
Вопрос к знатокам: а оптимальнее ли перекладывать это все на БД? Я остановился на варианте делаем выборку слабым алгоритмом точек 200 и их уже вне БД обрабатываем более точными алгоритмами, выбирая оптимальные точки.
у них обоих есть расширения для индексации 2d и 2dSphere координат, выборка в итоге достаточна шустрая, без лишних телодвижений
| lat | lng | param1 | param2 | param3 |
Нужно найти места в районе 10 км + формула для подсчёта веса параметров, например (param1 + param2)/param3 (формула более сложная, параметров около 5, точно уже не помню).
Объём бд — 3+ миллиона записей и постоянно пополняется. Хранить вес не возможно, так как параметры очень часто изменяются.
Пробовали перенести на монго — он не осиливал подсчёт по формуле за разумное время. На мускуле после оптимизаций выходило до пол-секунды(зависимо от объёма данных после грубо уточняющей выборки).
Насколько я помню в PostgreSQL много очень процедур для вычисления пространственных данных, насчет MySQL не скажу.
В России этими проблемами занимается Олег Бартунов, вот его презентация на эту тему.
Оу, с заглавной буквы — вИликий учОный Хаверсин (-:
Haversine == haversed sine / half the version, en.wikipedia.org/wiki/Versine
The versine or versed sine, versin(θ), is a trigonometric function equal to 1 − cos(θ) and 2sin2(½θ). It appeared in some of the earliest trigonometric tables and was once widespread, but it is now little-used. There are several related functions, most notably the haversine, half the versine, known in the haversine formula of navigation.
P.S. Можно конечно брутфорсить(считать длинны в реалтайме), но при количестве координат, выходящим за пределы десятков тысяч позиций это станет неприлично долгим.
Таким образом мы рассчитывали метрическое окно попадания в коде, а запрос к базе уже был просто на попадание в диапазон.
P.S. Формула
var R = 6371; // km
var dLat = (lat2-lat1).toRad();
var dLon = (lon2-lon1).toRad();
var lat1 = lat1.toRad();
var lat2 = lat2.toRad();
var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
Math.sin(dLon/2) * Math.sin(dLon/2) * Math.cos(lat1) * Math.cos(lat2);
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
var d = R * c;
Если задача с довольно большой точностью выбрать достаточно большой «квадрат» с нужной стороной(сторона превышает несколько сотен или тысяч километров) — то вот тут задача становится ВЕСЬМА нетривиальной.
И кстати да, например для вывода на карту быстрее делать выборку с MBRContains с LIMIT и ORDER BY created DESC, а потом уже проверять расстояния. Тогда действительно работает быстро.
src_lat - ABS(dst_lat)
Зачем здесь брать модуль? Если вы возьмете две точки на одном меридиане, но с противоположными широтами, то ваша формула будет считать их за одну точку и вернет ноль в качестве расстояния.
Кроме того, вот тут модуль тоже не нужен:
COS(ABS(dst_lat) * PI()/180)
поскольку косинус — четная функция, т.е. cos(x) = cos(-x).
поточнее и побыстрее будет
static const double DEG_TO_RAD = 0.017453292519943295769236907684886;
/// Earth's quatratic mean radius for WGS-84
static const double EARTH_RADIUS_IN_METERS = 6372797.560856;
/** Computes the arc, in radian, between two WGS-84 positions.
*
* The result is equal to <code>Distance(from,to)/EARTH_RADIUS_IN_METERS
* 2*asin(sqrt(h(d/EARTH_RADIUS_IN_METERS )))
*
* - d is the distance in meters between 'from' and 'to' positions.
* - h is the haversine function: <code>h(x)=sin²(x/2)
*
* The haversine formula gives:
* h(d/R) = h(from.lat-to.lat)+h(from.lon-to.lon)+cos(from.lat)*cos(to.lat)
*
* http://en.wikipedia.org/wiki/Law_of_haversines
*/
double ArcInRadians(const Position& from, const Position& to) {
double latitudeArc = (from.lat - to.lat) * DEG_TO_RAD;
double longitudeArc = (from.lon - to.lon) * DEG_TO_RAD;
double latitudeH = sin(latitudeArc * 0.5);
latitudeH *= latitudeH;
double lontitudeH = sin(longitudeArc * 0.5);
lontitudeH *= lontitudeH;
double tmp = cos(from.lat*DEG_TO_RAD) * cos(to.lat*DEG_TO_RAD);
return 2.0 * asin(sqrt(latitudeH + tmp*lontitudeH));
}
/** Computes the distance, in meters, between two WGS-84 positions.
*
* The result is equal to <code>EARTH_RADIUS_IN_METERS*ArcInRadians(from,to)</code>
*
* ArcInRadians
*/
double DistanceInMeters(const Position& from, const Position& to) {
return EARTH_RADIUS_IN_METERS*ArcInRadians(from, to);
}
Произвести индексацию таблицы с координатами по id, lat, lon
и искать уже в сфинксе по встроеному в него geodist'у.
Вполне шустро на 1млн. записей и результаты поиска сразу в метрах от точки поиска.
...
DROP PROCEDURE IF EXISTS geobox $$
CREATE PROCEDURE geobox (
...
SET lat_top := src_lat - (dist / 69);
...
SET lat_bot := src_lat + (dist / 69);
Latitude увеличивается на север, т.е. TOP > BOTTOM, а у вас наоборот. Или я запутался в чем-то?
Написано:
-- dist -> расстояние от центра в километрах
А по факту работает с милями. Ибо 69 — это количество миль в 1 градусе longtitude. Для километров там должна быть цифра 111.2
В 2016-м году не изобретайте велосипед, но используйте PostgreSQL 9.5+ с PostGIS 2.2+, там это всё есть и работает шустро (если создать индекс).
Вот, например, запрос из одного моего тестового задания, ищущий 3 ближайших точки из таблицы (я тестировал на 100 000) и его план запроса:
SELECT
ST_X(vehicles.position::geometry) AS longitude,
ST_Y(vehicles.position::geometry) AS latitude,
vehicles.position <-> 'POINT(37.058515 55.923175)'::geography AS distance_sphere,
ST_Distance(points.position, 'POINT(37.058515 55.923175)'::geography) AS distance_spheroid
FROM vehicles
WHERE available = true
ORDER BY vehicles.position <-> 'POINT(37.058515 55.923175)'::geography ASC
LIMIT 3;
Limit (cost=0.28..1.66 rows=3 width=56) (actual time=15.580..15.658 rows=3 loops=1)
-> Index Scan using vehicles_position_idx on vehicles (cost=0.28..22812.28 rows=49500 width=56) (actual time=15.578..15.655 rows=3 loops=1)
Order By: ("position" <-> '0101000020E6100000A8A9656B7D8742400EBE30992AF64B40'::geography)
Filter: available
Rows Removed by Filter: 12
Planning time: 0.215 ms
Execution time: 15.751 ms
Я как раз использовал формулу гаверсинусов для расчёта расстояния и получаемое значение очень близко к значению, возвращаемому оператором geography <-> geography
, который же как раз умеет ускоряться за счёт GiST-индексов. Однако функция ST_Distance считает дистанцию более точно, используя не сферу, а более приближенный к форме земли сфероид.
Если интересно, то можете посмотреть:
- в документацию: http://postgis.net/docs/manual-2.2/geometry_distance_knn.html
- в моё тестовое приложение: https://github.com/Envek/etatata
А так же можно поставить себе PostGIS, например, из следующего Docker-образа: https://hub.docker.com/r/mdillon/postgis/ и поиграться запросами следующего вида:
SELECT
points.position <-> 'POINT(37.058515 55.923175)'::geography AS "a <-> b",
ST_Distance(points.position, 'POINT(37.058515 55.923175)'::geography) AS "ST_Distance(a, b)",
ST_Distance(points.position, 'POINT(37.058515 55.923175)'::geography, true) AS "ST_Distance(a, b, true)",
ST_Distance(points.position, 'POINT(37.058515 55.923175)'::geography, false) AS "ST_Distance(a, b, false)"
FROM (
SELECT
ST_SetSRID(ST_MakePoint(37.61778 + (n*random() - 5000.00)/50000.00, 55.75583 + (n*random() - 5000.00)/50000.00),4326) AS position
FROM generate_series(1,3) As n
) points;
Определение расстояния между географическими точками в MySQL