- PVSM.RU - https://www.pvsm.ru -
При разработке ПО часто возникают интересные задачи. Одна из таких: работа с гео-координатами пользователей. Если вашим сервисом пользуются миллионы пользователей и запросы к РСУБД происходят часто, то выбор алгоритма играет важную роль. О том как оптимально обрабатывать большое количество запросов и искать ближайшие гео-позиции рассказано под катом.
В процессе разработки сервиса push-уведомлений Pushwoosh [1] возникла достаточно известная задача. Имеется много геозон. Геозона задается географическими координатами. Когда пользователь проходит мимо одной из таких геозон(например закусочная) ему должно приходить push-уведомление(«Йоу, заходи к нам и подкрепись с 20% скидкой). Для простоты будем считать радиус всех геозон одинаковым. В условиях большого количества геозон и большого количества пользователей(у нас их 500 миллионов!), которые постоянно перемещаются — поиск ближайшей геозоны должен осуществляться максимально быстро. В англоязычной литературе эта задача известна как Nearest neighbor search [2]. На первый взгляд кажется, что чтобы решить эту задачу нужно посчитать расстояния от пользователя до каждой геозоны и сложность данного алгоритма линейна O(n), где n — количество геозон. Но давайте решим эту задачу за логарифм O(log n)!
Начнем с простого — широты и долготы. Чтобы указать положение точки на поверхности Земли можно воспользоваться:
Нужно обратить внимание что x — это долгота, y — широта(Google Maps, Яндекс.Карты и все остальные сервисы указывают долготу первой).
Географические координаты можно перевести в пространственные — просто точка (x,y,z). Кому интересно более подробно можно посмотреть википедию [3].
Количество знаков после запятой определяет точность:
Градусы | Дистанция |
---|---|
1 | 111 km |
0.1 | 11.1 km |
0.01 | 1.11 km |
0.001 | 111 m |
0.0001 | 11.1 m |
0.00001 | 1.11 m |
0.000001 | 11.1 cm |
Если нужна точность до одного метра, то следует хранить 5 знаков после запятой.
Пусть у нас есть сервис, которым пользуются миллионы людей, и мы хотим хранить их географические координаты. Очевидный подход в данном случае завести в таблице два поля — широта/долгота. Можно использовать double precision(float8), который занимает 8 байт. В итоге нам потребуется 16 байт для хранения координат одного пользователя.
Но есть и другой подход, который называется geohashing. Идея простая. Широта и долгота кодируется в число, которое затем кодируется в base-32. Карта разбивается на матрицу размера 4x8 и каждой ячейке присваивается некоторый символ(alphanumeric).
Чтобы повысить точность, каждая ячейка разбивается на более мелкие, при этом к коду добавляются символы(если быть точным цифры, а после происходит кодирование в base-32).
Разбиение можно производить до необходимой точности. Такой код уникален для каждой точки.
Подробно алгоритм построения я описывать не буду, о нем можно почитать в википедии [4]. Его идея похожа на арифметическое кодирование [5]. Данный код обратим. Многие технологии уже имеют встроенные методы для работы с гео-хешами, например, MongoDB [6].
Пример: координаты 57.64911,10.40744 будут закодированы в u4pruydqqvj (11 символов). Если требуется меньшая точность, то и код будет меньше.
Особенность данного кода в том, что ОБЫЧНО близлежащие точки имеют одинаковый префикс. И можно посчитав разницу между гео-хешами определить близость двух точек. Но к сожалению данный алгоритм не точен, это хорошо видно из предыдущих изображений. Ячейки с кодами 7 и 8 находятся дальше друг от друга, чем ячейки 2 и 8.
В качестве примера приведу картинку, где гео-хеш дает неверный результат(geohashdelta — разность между геохешами без base32)
Если точностью в задаче можно пренебречь, то можно создать в таблице поле geohash, добавить по нему индекс и производить поиск за логарифм.
Можно написать хранимую процедуру
create or replace function gc_dist(_lat1 float8, _lon1 float8, _lat2 float8, _lon2 float8) returns float8 as
$$
DECLARE
radian CONSTANT float8 := PI()/360;
BEGIN
return ACOS(SIN($1*radian) * SIN($3*radian) + COS($1*radian) * COS($3*radian) * COS($4*radian-$2*radian)) * 6371;
END;
$$ LANGUAGE plpgsql;
и использовать её
explain SELECT *, gc_dist(54.838971, 83.106560, lat, lng) AS pdist FROM geozones WHERE applicationid = 3890 ORDER BY pdist ASC LIMIT 10;
Но в итоге будет Seq Scan, что очень не приятно.
Limit (cost=634.72..634.75 rows=10 width=69)
-> Sort (cost=634.72..639.72 rows=2001 width=69)
Sort Key: (gc_dist(54.838971::double precision, 83.10656::double precision, (lat)::double precision, (lng)::double precision))
-> Seq Scan on geozones (cost=0.00..591.48 rows=2001 width=69)
Что делать, когда точностью пренебречь не получается? Для этого уже есть специальная структура данных K-d tree [7]. Можно перевести широту и долготу в (x,y,z) построить по ним дерево и производить поиск по дереву в среднем за логарифм.
PostGIS [8] — это расширение, которое значительно расширяет обработку географических объектов в РСУБД PostgreSQL.
Для решения нашей задачи будет использовать трехмерную систему координат SRID 4326(WGS 84 [9]). Данная система координат определяет координаты относительно центра масс Земли, погрешность составляет менее 2 см.
Если у вас ubuntu-подобная система, то PostGIS можно установить из пакета(для PostgreSQL 9.1):
sudo apt-get install python-software-properties;
sudo apt-add-repository ppa:ubuntugis/ppa;
sudo apt-get update;
sudo apt-get install postgresql-9.1-postgis;
И подключить необходимые экстеншены:
CREATE EXTENSION postgis;
CREATE EXTENSION btree_gist; -- for GIST compound index
С помощью dx можно посмотреть все установленные экстеншены.
Создадим отношение с индексом по полю location
CREATE TABLE geozones_test (
uid SERIAL PRIMARY KEY,
lat DOUBLE PRECISION NOT NULL CHECK(lat > -90 and lat <= 90),
lng DOUBLE PRECISION NOT NULL CHECK(lng > -180 and lng <= 180),
location GEOMETRY(POINT, 4326) NOT NULL -- PostGIS geom field with SRID 4326
);
CREATE INDEX geozones_test_location_idx ON geozones_test USING GIST(location);
После чего для поиска ближайшей геозоны можно воспользоваться следующим запросом
SELECT *, ST_Distance(location::geography, 'SRID=4326;POINT(83.106560 54.838971)'::geography)/1000 as dist_km
FROM geozones_test ORDER BY location <-> 'SRID=4326;POINT(83.106560 54.838971)' limit 10;
Здесь <-> — distance operator. Мы посчитали дистанцию и нашли ближайшие 10 геозон!
СТОП скажите Вы! Ведь данный запрос должен просмотреть все записи в таблице и посчитать расстояние до каждой геозоны O(n).
Давайте посмотрим EXPLAIN ANALYZE запроса
EXPLAIN ANALYZE
SELECT *, ST_Distance(location::geography, 'SRID=4326;POINT(83.106560 54.838971)'::geography)/1000 as dist_km
FROM geozones_test ORDER BY location <-> 'SRID=4326;POINT(83.106560 54.838971)' limit 10;
Limit (cost=0.00..40.36 rows=10 width=227) (actual time=0.236..0.510 rows=10 loops=1)
-> Index Scan using geozones_test_location_idx on geozones_test (cost=0.00..43460.37 rows=10768 width=227) (actual time=0.235..0.506 rows=10 loops=1)
Order By: (location <-> '0101000020E6100000F4C308E1D1C654406EA5D766636B4B40'::geometry)
Total runtime: 0.579 ms
Index Scan! Где же магия?
А она находится в GiST индексе.
PostgreSQL поддерживает 3 типа индексов:
GiST-индекс реализованный PostGIS поддерживает distance operator [10] <-> при поиске. Также данный индекс может быть составным!
Данный функционал можно реализовать и без использования PostGIS, воспользовавшись индексом btree-gist [11], но PostGIS предоставляет удобные методы для перевода широты и долготы в WGS 84.
[1] Интересные примеры запросов postgresql.ru.net/postgis/ch04_6.html [12]
[2] Восхищение простотой использования boundlessgeo.com/2011/09/indexed-nearest-neighbour-search-in-postgis/ [13]
[3] Презентация о том, что данный подход можно использовать не только для широты/долготы, но и для улиц и других интересных объектов www.hagander.net/talks/Find%20your%20neighbours.pdf [14]
[4] Презентация разработчиков KNN GIst-index www.sai.msu.su/ [15]~megera/postgres/talks/pgcon-2010-1.pdf
P.S.
Postgres version >= 9.1
PostGIS version >= 2.0
Автор: FallDi
Источник [16]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/postgresql/63863
Ссылки в тексте:
[1] Pushwoosh: http://www.pushwoosh.com/
[2] Nearest neighbor search: http://en.wikipedia.org/wiki/Nearest_neighbor_search
[3] википедию: http://ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D0%BA%D0%BE%D0%BE%D1%80%D0%B4%D0%B8%D0%BD%D0%B0%D1%82%D1%8B
[4] википедии: http://en.wikipedia.org/wiki/Geohash
[5] арифметическое кодирование: http://ru.wikipedia.org/wiki/%D0%90%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BA%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5
[6] MongoDB: http://docs.mongodb.org/manual/core/geospatial-indexes/
[7] K-d tree: http://en.wikipedia.org/wiki/K-d_tree
[8] PostGIS: http://postgis.net/
[9] WGS 84: http://en.wikipedia.org/wiki/WGS84
[10] distance operator: http://www.postgis.org/documentation/manual-svn/geometry_distance_centroid.html
[11] btree-gist: http://www.postgresql.org/docs/9.1/static/btree-gist.html
[12] postgresql.ru.net/postgis/ch04_6.html: http://postgresql.ru.net/postgis/ch04_6.html
[13] boundlessgeo.com/2011/09/indexed-nearest-neighbour-search-in-postgis/: http://boundlessgeo.com/2011/09/indexed-nearest-neighbour-search-in-postgis/
[14] www.hagander.net/talks/Find%20your%20neighbours.pdf: http://www.hagander.net/talks/Find%20your%20neighbours.pdf
[15] www.sai.msu.su/: http://www.sai.msu.su/
[16] Источник: http://habrahabr.ru/post/228023/
Нажмите здесь для печати.