Комментарии 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
т.е. функция вызовется всех записей в таблице, и только потом уже выполнится условие.
Проверил, на MySQL нет разницы в производительности между
и
Планировщик показывает одинаковую картину, при наличии индекса по «a»
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 — не сильно сложный пример.
На малых. Цель понять принципиальную возможность ограничения области поиска с помощью индекса. Такая возможность подтверждается показаниями explain в обоих случаях.
a*a — достаточный пример неиндексируемого выражения, чтобы проверить описанное выше.
Скорость вычисления расстояния с помощью хранимой процедуры — это отдельный вопрос, не имеющий отношения к вашему замечанию о «предварительной выборке».
a*a — достаточный пример неиндексируемого выражения, чтобы проверить описанное выше.
Скорость вычисления расстояния с помощью хранимой процедуры — это отдельный вопрос, не имеющий отношения к вашему замечанию о «предварительной выборке».
В комментарии ниже я приводил пример с сложной формулой вычисления. Она не является хранимой процедурой, но суть, в данном случае, та же.
т.е. утверждение «функция вызовется всех записей в таблице» неверное
Удобное решение, особенно для генерации отчетов или промежуточных данных для нечастых операций. Можно спокойно применять в desktop-приложениях и в мобильных приложениях (если, конечно, БД поддерживает функции). На его основе можно также сделать и вычисление длины более сложных путей.
А тесты скорости при выборке большого количества записей были бы очень кстати.
А тесты скорости при выборке большого количества записей были бы очень кстати.
При нескольких миллионах записей есть смысл применять несколько алгоритмов, чтобы сначала менее точным отсекать совсем далекие точки, а потом уже точным обрабатывать оставшийся массив.
Вопрос к знатокам: а оптимальнее ли перекладывать это все на БД? Я остановился на варианте делаем выборку слабым алгоритмом точек 200 и их уже вне БД обрабатываем более точными алгоритмами, выбирая оптимальные точки.
Вопрос к знатокам: а оптимальнее ли перекладывать это все на БД? Я остановился на варианте делаем выборку слабым алгоритмом точек 200 и их уже вне БД обрабатываем более точными алгоритмами, выбирая оптимальные точки.
а не проще в этом случае перейти на PostgreSQL или MongoDB?
у них обоих есть расширения для индексации 2d и 2dSphere координат, выборка в итоге достаточна шустрая, без лишних телодвижений
у них обоих есть расширения для индексации 2d и 2dSphere координат, выборка в итоге достаточна шустрая, без лишних телодвижений
С PostgreSQL не сталкивался, а в MongoDB это хорошо в случае, когда выборка только по координатам. Если есть какие-то ещё условия выборки — работает не так уж и быстро.
Можете привести конкретный пример и объем данных?
База вида
Нужно найти места в районе 10 км + формула для подсчёта веса параметров, например (param1 + param2)/param3 (формула более сложная, параметров около 5, точно уже не помню).
Объём бд — 3+ миллиона записей и постоянно пополняется. Хранить вес не возможно, так как параметры очень часто изменяются.
Пробовали перенести на монго — он не осиливал подсчёт по формуле за разумное время. На мускуле после оптимизаций выходило до пол-секунды(зависимо от объёма данных после грубо уточняющей выборки).
| lat | lng | param1 | param2 | param3 |Нужно найти места в районе 10 км + формула для подсчёта веса параметров, например (param1 + param2)/param3 (формула более сложная, параметров около 5, точно уже не помню).
Объём бд — 3+ миллиона записей и постоянно пополняется. Хранить вес не возможно, так как параметры очень часто изменяются.
Пробовали перенести на монго — он не осиливал подсчёт по формуле за разумное время. На мускуле после оптимизаций выходило до пол-секунды(зависимо от объёма данных после грубо уточняющей выборки).
Немного непонятно определение «Хранить вес не возможно, так как параметры очень часто изменяются.». На сколько часто? Раз в секунду? Или же они зависят от какого-то третьего значения, которого нет в этой таблице, который динамически меняется?
Извините, читал по-дагонали… PostGIS сюда не подойдет?
Насколько я помню в PostgreSQL много очень процедур для вычисления пространственных данных, насчет MySQL не скажу.
Насколько я помню в PostgreSQL много очень процедур для вычисления пространственных данных, насчет MySQL не скажу.
Поддержу, Postgresql и Postgis — сильно проще. Поиск ближайших из коробки, кстати, не так давно релизнули.
В России этими проблемами занимается Олег Бартунов, вот его презентация на эту тему.
В России этими проблемами занимается Олег Бартунов, вот его презентация на эту тему.
Формула называется по-русски «формула гаверсинусов».
> формуле Хаверсина
Оу, с заглавной буквы — вИликий учОный Хаверсин (-:
Haversine == haversed sine / half the version, en.wikipedia.org/wiki/Versine
Оу, с заглавной буквы — вИликий учОный Хаверсин (-:
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.
Я так понимаю, число 6367 в километрах взяли как среднее значение радиуса земли между 6356.78 к полюсам и 6378.14 к экватору?
Вставлю свои три копейки. Описанное выше будет работать пока расстояние будет довольно небольшим, то есть до тех пор покуда ваш радиус не вылетит за пределы -180/180 или -90/90. А дальше уже начинаются проблемы. По крайней мере я так и не отыскал нормального решения к сожалению. Может быть кто-то подскажет в какую сторону смотреть?
Простите, а на какой планете у вас угловые координаты вылетают за пределы [-180, 180], [-90, 90]?
планета Земля. Если есть желание сделать выборку в большом радиусе (5000 км) и вы находитесь скажем на Аляске, а другой человек где-то в Сибири(стоит отметить что радиус должен быть достаточно большим что бы вышеназванное было истиной), то тот человек что находится в Сибири обнаружен не будет(если искать относительно человека в Аляске), ибо вы упретесь в -180. И что дальше делать мне в общем-то непонятно. К сожалению, как я уже сказал выше пока что решения не нашел и буду рад предложениям. Понимаю, что случай в принципе довольно искуственный, но все же имеет право на существование.
P.S. Можно конечно брутфорсить(считать длинны в реалтайме), но при количестве координат, выходящим за пределы десятков тысяч позиций это станет неприлично долгим.
P.S. Можно конечно брутфорсить(считать длинны в реалтайме), но при количестве координат, выходящим за пределы десятков тысяч позиций это станет неприлично долгим.
Когда в свое время у нас стояла такая же задача, мы решили ее путем хранения в базе кроме широты и долготы еще дополнительно координат в метрах переведенных из градусов по проекции меркатор.
Таким образом мы рассчитывали метрическое окно попадания в коде, а запрос к базе уже был просто на попадание в диапазон.
P.S. Формула
Таким образом мы рассчитывали метрическое окно попадания в коде, а запрос к базе уже был просто на попадание в диапазон.
P.S. Формула
Это же вроде будет работать только для представления Земли как идеальной сферы, а не, скажем, для WGS84?
Вроде есть для этого? ST_Distance_Sphere более быстрая и ST_Distance_Spheroid более точная
Вник в суть. И подумал, может если есть возможно перенести эти расчеты на клиентскую сторону?
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;
наткнулся еще на класс написанный на js (если надо напишу в лс)
Если задача заключается лишь в том что бы подсчитать расстояние между точками, то тут сложности нет. Можно начать отсюда, а дальше по линкам внутри википедии.
Если задача с довольно большой точностью выбрать достаточно большой «квадрат» с нужной стороной(сторона превышает несколько сотен или тысяч километров) — то вот тут задача становится ВЕСЬМА нетривиальной.
Если задача с довольно большой точностью выбрать достаточно большой «квадрат» с нужной стороной(сторона превышает несколько сотен или тысяч километров) — то вот тут задача становится ВЕСЬМА нетривиальной.
Between по 2 ключам никогда индексируется. Если уж Вы используйте spatial — функции, там есть замечательная MBRContains и SPATIAL KEY.
И кстати да, например для вывода на карту быстрее делать выборку с MBRContains с LIMIT и ORDER BY created DESC, а потом уже проверять расстояния. Тогда действительно работает быстро.
И кстати да, например для вывода на карту быстрее делать выборку с MBRContains с LIMIT и ORDER BY created DESC, а потом уже проверять расстояния. Тогда действительно работает быстро.
По-моему, у вас ошибка в формуле, вот здесь:
Зачем здесь брать модуль? Если вы возьмете две точки на одном меридиане, но с противоположными широтами, то ваша формула будет считать их за одну точку и вернет ноль в качестве расстояния.
Кроме того, вот тут модуль тоже не нужен:
поскольку косинус — четная функция, т.е. cos(x) = cos(-x).
src_lat - ABS(dst_lat)
Зачем здесь брать модуль? Если вы возьмете две точки на одном меридиане, но с противоположными широтами, то ваша формула будет считать их за одну точку и вернет ноль в качестве расстояния.
Кроме того, вот тут модуль тоже не нужен:
COS(ABS(dst_lat) * PI()/180)
поскольку косинус — четная функция, т.е. cos(x) = cos(-x).
для большей производительности, я бы реализовал в UDF
поточнее и побыстрее будет
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);
}
поточнее и побыстрее будет
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);
}
НЛО прилетело и опубликовало эту надпись здесь
Кстати хорошим решением может быть Sphinx.
Произвести индексацию таблицы с координатами по id, lat, lon
и искать уже в сфинксе по встроеному в него geodist'у.
Вполне шустро на 1млн. записей и результаты поиска сразу в метрах от точки поиска.
Произвести индексацию таблицы с координатами по id, lat, lon
и искать уже в сфинксе по встроеному в него geodist'у.
Вполне шустро на 1млн. записей и результаты поиска сразу в метрах от точки поиска.
Вот тут кажется ошибочка
Latitude увеличивается на север, т.е. TOP > BOTTOM, а у вас наоборот. Или я запутался в чем-то?
...
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, а у вас наоборот. Или я запутался в чем-то?
И вот ещё ошибка:
Написано:
А по факту работает с милями. Ибо 69 — это количество миль в 1 градусе longtitude. Для километров там должна быть цифра 111.2
Написано:
-- 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