Геолокаційні запити в PostgreSQL без важкої артилерії
Привіт, мене звуть Павло Дмитрієв. Я працюю iOS-розробником у компанії Postindustria. Багаторічний Python-досвід подекуди дається взнаки, тож я часто беру участь і в «бекендних» завданнях, адже в нас таке заохочується. Саме тому сьогодні я хотів би розповісти про випадок, що допоміг мені ще раз переконатися в перевагах PostgreSQL і дізнатися, як за допомогою СКБД найлегше виконувати операції з геокоординатами. Звичайно, «зубри» DBA усе це знають, але, сподіваюся, стаття буде цікава для тих, хто ще не з’їв на цьому кількох собак.
У повсякденній рутині програмування часто виникають завдання на кшталт «знайти всіх користувачів додатку поруч з містом X» або «відсортувати щось за віддаленістю від чогось». В одному старому проєкті це взагалі робили на рівні коду, тобто для пошуку вибирали точки, що потрапляють у заданий квадрат запитом на кшталт:
WHERE lat > 10 AND lat < 20 AND lng > 30 AND lng < 45
А потім усе, що опинялося в цій «мережі», додатково фільтрувалося в Python-скриптi. Гадаю, зрозуміло, що продуктивність цього підходу швидко сповзала десь на рівень плінтуса, до того ж повсякчас лізли баги з обробленням граничних умов. Не те щоб їх неможливо було розв’язати, але ліпше подивімося, як це можна зробити на рівні БД. І ні, це не для того, щоб перекласти все зі своїх плечей на DBA.
Востаннє подібне завдання цілком природно виникло під час створення проєкту Zin (dating-стартап з ухилом в безпеку), а для застосунків такого типу локацію користувача можна сміливо вважати за наріжний камінь. Коротко кажучи, нам треба було знаходити найближчі до користувача оголошення в нашій базі й сортувати їх за відстанню.
Окремо зазначу, що нас цікавила відстань за дугою «великого кола», без поправок на рельєф, до того ж припустима похибка була доволі велика, тож головним критерієм стала саме простота реалізації. Забігаючи трохи наперед, скажу, що точність вийшла кращою, ніж ми сподівалися, і я це продемонструю.
Тестові дані
БД проєкту містить приватні дані, тож для прикладів я використовуватиму два інших датасети. Перший — велика таблиця міст і їхніх координат, узята звідси. Вона трохи надлишкова, бо містить не тільки «міста» в їхньому традиційному розумінні, а й райони міст, деякі туристичні принади й таке інше; але раз нам потрібна насамперед кількість, то це не стане проблемою. Тож ось структура нашої першої таблиці.
CREATE TABLE cities (
id integer DEFAULT nextval('public.cities_seq'::regclass) NOT NULL,
name character varying NOT NULL,
region character varying NOT NULL,
lat double precision NOT NULL,
lng double precision NOT NULL
);
ALTER TABLE ONLY cities
ADD CONSTRAINT cities_pkey PRIMARY KEY (id);
CREATE INDEX cities_name_low_idx ON cities USING btree (lower((name)::text));
CREATE INDEX cities_location_idx ON cities USING gist (ll_to_earth(lat, lng));
Усе дуже просто: ім’я місця, код країни, до якої воно належить, і кілька атрибутів для зберігання широти й довготи. Додатково будуємо два індекси: BTREE для пошуку за назвою і той, що нам знадобиться для запитів по координатах. Останній використовує тип GIST (хвала розробникам PostgreSQL за цей чудовий механізм) і функцію ll_to_earth, про яку поговоримо пізніше.
Зазвичай, у вас буде два основні способи зберегти локації: використовувати пару чисел в окремих стовпчиках для ширини та довжини або ж використати той чи інший специфічний тип з-поміж тих, про які ми поговоримо нижче (point, earth, cube, etc.). Великої різниці з погляду швидкості жоден з варіантів не дає, тому зазвичай використовують саме окремі стовпчики. Але тут уже треба аналізувати варіанти, виходячи з конкретики вашого завдання.
Не наводитиму допоміжні Python-скрипти, які я використовував для збору даних і їх перевантаження в БД; якщо вони комусь цікаві, то ось посилання на GitHub з ними.
Переносимо записи в БД і переконуємося, що цього досить, щоб показати всі особливості, пов’язані з продуктивністю.
SELECT COUNT(*), pg_size_pretty(pg_relation_size('cities')) AS data, pg_size_pretty(pg_indexes_size('cities')) AS idxs
FROM cities;
count | data | idxs
----------+--------+---------
12005938 | 848 MB | 1836 MB
(1 row)
Time: 2073.919 ms (00:02.074)
Щоб наочніше продемонструвати складні запити, я також створив дві невеликі таблички: перша містить найбільші міста Чорногорії (15), а друга — найближчі до них піцерії (172); останні я брав з Foursquare, скрипт для цього також є на GitHub.
Фух, це був довгий вступ, тож перейдімо до наявних опцій.
PostGIS
Це саме та «важка артилерія», без якої я обіцяв обійтися в назві цієї статті. Але ж не згадати його було б нелогічно, хоча б для того, щоб зрозуміти, чому саме ми вирішили його не використовувати.
Так, звичайно, цей метод має величезні переваги: найвища точність і гнучкість, відсутність граничних умов, можливість змінити просторову прив’язку.
Але все це дається досить великою ціною, починаючи з прірви залежностей (проста установка через homebrew має більше ніж 30 залежностей, зокрема GCC, Qt, Boost і таке інше) і закінчуючи підвищеною складністю (нестандартні типи даних, 5000+ рядків додаткових таблиць із довідниками).
Тож цілком очевидно, що ми хотіли б використати щось простіше, і, на щастя, основна команда PostgreSQL розробила додаток earthdistance, що містить усе потрібне для нас. Установити його просто:
CREATE EXTENSION earthdistance CASCADE;
Цей додаток дає два способи роботи з координатами.
Оператор <@>
Не знаю, як саме називати цю синтаксичну химеру (може, «око»?), та суть дуже проста: цей оператор приблизно розраховує ту саму big circle distance між двома точками на земній кулі. Для точок використовується вбудований тип даних point, але слід пам’ятати, що спочатку маємо вказувати довготу, а вже потім широту; це суперечить «звичному» порядку, але саме довгота відповідає координаті X, тому й іде першою. Друга особливість, про яку не слід забувати, це те, що результат повертається в статутних милях (тих, що мають 5280 футів або приблизно 1609 метрів), тож завжди треба ділити/множити на цю константу.
Переваги цього методу очевидні: він легкий і використовує найпростіші типи даних. Але є в нього й недоліки: окрім точності (Земля вважається ідеальною сферою), граничних умов на полюсах і
Наведу приклад, як знайти місця, ближчі за 10 км до якоїсь точки (скажімо, до міста з поетичною назвою Бар), що має приблизно такі координати: 42.1° пн. ш., 19.1° сх. д.
SELECT *, (point(lng, lat) <@> point(19.1, 42.1)) * 1609.344 AS distance FROM cities WHERE (point(lng, lat) <@> point(19.1, 42.1)) < (10000 / 1609.344) ORDER BY distance;
id | name | lat | lng | region | distance ----------+-----------------------------+----------+----------+--------+-------------------- 27696013 | Bjelisi | 42.10083 | 19.10417 | ME | 356.2025188423806 27699128 | Topolica | 42.09833 | 19.09417 | ME | 515.6034584176577 27696061 | Bar | 42.0937 | 19.09841 | ME | 712.7044816072382 27708312 | King Nikola's Palace | 42.10062 | 19.09129 | ME | 721.903811067934 27708268 | Princess | 42.10158 | 19.09132 | ME | 737.3598549548324 27708234 | Bar Port | 42.09701 | 19.09132 | ME | 789.5619694327141 27708184 | Castello | 42.10701 | 19.09623 | ME | 839.2352057529451 27699126 | Popovici | 42.09194 | 19.10528 | ME | 996.5017600203865 27708313 | Antivari Pier (historical) | 42.09708 | 19.08834 | ME | 1015.3313902853366 27695933 | Rikavac | 42.09278 | 19.08972 | ME | 1167.8829329656053 … (232 rows) Time: 2844.305 ms (00:02.844)
Як бачите, сам запит — простий, але час виконання не дуже тішить око, навіть без EXPLAIN зрозуміло, що працює звичайний SCAN.
Здебільшого, щоб зоптимізувати такі запити й допомогти їм використовувати індекс, долучають оператор обчислення відстані між точками «за прямою» <->, додатково потім уточнюючи результат за допомогою <@>, але проблеми з полюсами та
Вам знайоме це почуття, коли автор книжки чи статті силоміць підводить вас до того рішення, яке він заздалегідь визначив для себе як правильне? Саме час його відчути. Ми переходимо до третього чи, точніше сказати, до другого з половиною (бо він входить у той самий застосунок earthdistance) методу.
Функція earth_distance та її помічники
Може, дехто буде зі мною не згоден, але я вважаю, що команда розробників PostgreSQL — одні з найкмітливіших людей на планеті (а те, що вони створили свій проєкт безплатним і відкритим, робить їх ще й найщирішими). До чого це я веду?
Оператор <@> можна вважати «2D-шляхом» до розв’язання завдання, і якщо він працює не дуже добре, треба переходити в 3D, що й зроблено в earth_distance. Цей модуль дозволяє перетворити будь-які координати на планеті на тривимірну точку в просторі й потім працювати з нею. Оскільки вбудованого типу даних для 3D-точки в Postgres немає, використовується тип cube, а точніше його «нащадок» earth, в якому додаються деякі перевірки на «здоровий глузд» на кшталт «точка не може бути далеко віддалена від поверхні». Звичайно, куб вважається «нульовим», тобто його протилежні вершини збігаються.
Спочатку кілька корисних функцій:
-
ll_to_earth(latitude, longitude)— перетворює пару «широта — довжина» на той самий тип earth, обчислюючи тривимірну позицію точки в просторі. -
earth_distance(point1, point2)— обчислює відстань між двома точками у форматі earth. -
earth_box(point, radius)— створює куб такого розміру, щоб у нього потрапляли всі точки, розміщені на відстані не більше ніж radius від point. Цей куб є приблизним критерієм пошуку, але завдяки операторові <@> (входження кубу в куб) дозволяє ефективно використовувати GIST-індекси, проводячи потім «доуточнення» запиту.
Розглянемо приклад.
SELECT *, ROUND(earth_distance(ll_to_earth(42.1, 19.1), ll_to_earth(lat, lng))::NUMERIC, 2) AS distance FROM cities WHERE earth_box(ll_to_earth (42.1, 19.1), 10000) @> ll_to_earth (lat, lng) AND earth_distance(ll_to_earth (42.1, 19.1), ll_to_earth (lat, lng)) < 10000 ORDER BY distance;
id | name | lat | lng | region | distance ----------+-----------------------------+----------+----------+--------+---------- 27696013 | Bjelisi | 42.10083 | 19.10417 | ME | 356.60 27699128 | Topolica | 42.09833 | 19.09417 | ME | 516.18 27696061 | Bar | 42.0937 | 19.09841 | ME | 713.51 27708312 | King Nikola's Palace | 42.10062 | 19.09129 | ME | 722.72 27708268 | Princess | 42.10158 | 19.09132 | ME | 738.19 27708234 | Bar Port | 42.09701 | 19.09132 | ME | 790.45 27708184 | Castello | 42.10701 | 19.09623 | ME | 840.18 27699126 | Popovici | 42.09194 | 19.10528 | ME | 997.62 27708313 | Antivari Pier (historical) | 42.09708 | 19.08834 | ME | 1016.48 27695933 | Rikavac | 42.09278 | 19.08972 | ME | 1169.20 … (232 rows) Time: 102.084 ms
Як бачите, результат куди ліпший за продуктивністю, навіть на звичайнісінькому MacBook Pro 2016, оброблення 12М+ записів майже вклалася в 100 мс. Поглянемо на EXPLAIN-запитові.
Gather Merge (cost=45002.12..45441.98 rows=3770 width=69)
Workers Planned: 2
-> Sort (cost=44002.10..44006.81 rows=1885 width=69)
Sort Key: (round((sec_to_gc(cube_distance('(4471920.234086516, 1548541.2222539173, 4276093.607391206)'::cube, (ll_to_earth(lat, lng))::cube)))::numeric, 2))
-> Parallel Bitmap Heap Scan on cities (cost=651.34..43899.55 rows=1885 width=69)
Recheck Cond: ('(4461920.235110745, 1538541.2232781458, 4266093.608415434),(4481920.233062288, 1558541.2212296887, 4286093.606366977)'::cube @> (ll_to_earth(lat, lng))::cube)
Filter: (sec_to_gc(cube_distance('(4471920.234086516, 1548541.2222539173, 4276093.607391206)'::cube, (ll_to_earth(lat, lng))::cube)) < '10000'::double precision)
-> Bitmap Index Scan on cities_location_idx (cost=0.00..650.21 rows=13572 width=0)
Index Cond: ((ll_to_earth(lat, lng))::cube <@ '(4461920.235110745, 1538541.2232781458, 4266093.608415434),(4481920.233062288, 1558541.2212296887, 4286093.606366977)'::cube)
Сканування індексу + додаткове уточнення дають нам дуже пристойну швидкість. Тож якщо ваша база велика, зменшити «охоплення» запиту — завжди гарна ідея, бо ж ситуація, коли треба знаходити щось по всьому світові, зустрічається нечасто; набагато частіше ми обмежуємо пошук якимось регіоном.
Мабуть, вас цікавить питання, наскільки розбіжні результати обчислень різними методами (принаймні мені було дуже цікаво). Це легко дізнатися.
SELECT name, ST_Distance(ST_MakePoint(lng, lat)::geography, ST_MakePoint(19.1, 42.1)::geography) AS postgis_distance, earth_distance(ll_to_earth(42.1, 19.1), ll_to_earth (lat, lng)) AS earth_distance, (point(lng, lat) <@> point(19.1, 42.1)) * 1609.344 AS point_distance FROM cities WHERE earth_box(ll_to_earth (42.1, 19.1), 10000) @> ll_to_earth (lat, lng) AND earth_distance(ll_to_earth (42.1, 19.1), ll_to_earth (lat, lng)) < 10000 ORDER BY earth_distance;
name | postgis_distance | earth_distance | point_distance -----------------------------+------------------+--------------------+-------------------- Bjelisi | 357.05152825 | 356.6040157475758 | 356.2025188423806 Topolica | 516.71294939 | 516.1846255398445 | 515.6034584176577 Bar | 712.02799946 | 713.5078129379874 | 712.7044816072382 King Nikola's Palace | 723.77941534 | 722.717511506365 | 721.903811067934 Princess | 739.14564214 | 738.1909768134576 | 737.3598549548324 Bar Port | 791.12180279 | 790.4519313791742 | 789.5619694327141 Castello | 838.76185601 | 840.1811573389859 | 839.2352057529451 Popovici | 996.13740888 | 997.6249760322966 | 996.5017600203865 Antivari Pier (historical) | 1017.61930422 | 1016.4758302850378 | 1015.3313902853366 Rikavac | 1168.91272962 | 1169.199322822384 | 1167.8829329656053 … Knjezdovo | 9751.02688274 | 9743.710964250973 | 9732.740617250734 Rt Sapavica | 9776.31845857 | 9772.941912657994 | 9761.938654824216 Livrsanik | 9790.74772202 | 9781.953343427898 | 9770.939939713666 Kabeta | 9803.27894257 | 9791.177885397401 | 9780.154095863507 Pecurice | 9825.29031086 | 9833.21849793169 | 9822.147375291843 Dedici | 9825.38102702 | 9836.570130079455 | 9825.495233870668 Kozjak | 9860.53074801 | 9882.053049767033 | 9870.926944792083 Livari | 9899.30877216 | 9888.084255774567 | 9876.95136032431 Ocas | 9877.66304883 | 9893.775540351273 | 9882.636237141522 Kamisora | 9932.59217935 | 9926.356311450303 | 9915.180325874655 Lunje | 9955.46356913 | 9951.533852256645 | 9940.329519539344 Pepici | 9950.93625773 | 9971.099451151647 | 9959.873089720966 Bajraktari | 9993.82232318 | 9992.844754025287 | 9981.593909774985 (228 rows) Time: 500.176 ms
Тож, як бачите, розбіжність складає десь до 30 метрів на 10 км у найгірших випадках, що для більшості сценаріїв є доволі прийнятною похибкою. До речі, ми чекали значно більшої похибки й ця нас цілком влаштовувала.
Підсумуємо інформацію про «метод кубів». Його переваги: швидкість, простота, можливість «переоцінити» розмір планети, змінивши таким чином одиниці виміру. З недоліків залишається сама точність, бо планета, як і раніше, вважається сферою.
Цікавіші запити
Тепер, коли ми знаємо основи, поговоримо про складніші запити. Наведу кілька прикладів, використовуючи для наочності «зменшений датасет» з піцеріями.
Приміром, нам треба знайти найвіддаленіші від нас піцерії, а після цього визначити, до яких міст вони належать (вважатимемо, що піцерія належить до міста, центр якого розміщений найближче до неї). Звичайно, зробити це можна безліччю методів (бо ж це SQL); наведу той, що, на мій погляд, найточніше висловлює «алгоритм» пошуку.
WITH pizzerias AS ( SELECT name, ll_to_earth(lat, lng) as point, earth_distance(ll_to_earth(lat, lng), ll_to_earth(42.1, 19.1)) AS distance FROM pizzerias ORDER BY distance DESC LIMIT 25 ) SELECT c.name AS city, p.name, p.distance FROM pizzerias p, LATERAL (SELECT name FROM cities_min c ORDER BY earth_distance(ll_to_earth(c.lat, c.lng), p.point) LIMIT 1) c;
city | name | distance --------------+---------------------------+-------------------- Pljevlja | Brut | 141584.33308274313 Zabljak | Balkan | 117451.9785288297 Zabljak | Caffe pizzeria Balkan | 117435.32995569201 Zabljak | Lazar | 117308.9999099511 Bijelo Polje | cezar | 116663.29228130652 Bijelo Polje | Orao | 116642.62285195319 Bijelo Polje | Pierre | 116580.71776744149 Bijelo Polje | Padrino | 104133.00996894344 Kolasin | Padrino Pizzerua | 103643.11705954213 Kolasin | Pizzeria Kapri | 87709.3205690596 Niksic | Chaplin | 76339.67053537675 Niksic | Pizzeria Garfield | 76139.35825221038 Niksic | Stari Nikšić | 76118.70681853226 Niksic | Piazza Restaurant & Caffe | 76110.42052261815 Niksic | K2 | 75899.71658365549 Niksic | Šef | 75850.41193677587 Herceg Novi | Grifonee | 62681.009366742284 Herceg Novi | Nautilus | 62597.163060010935 Herceg Novi | Caffe Pizzeria Biblioteka | 62586.73859525146 Herceg Novi | Forte | 61781.28207372379 Herceg Novi | Atelier | 61018.18974275154 Herceg Novi | Popaj | 60869.123535469735 Herceg Novi | Cafe Pizzeria Trg | 60721.08839248005 Herceg Novi | Caffe Pizzeria 5 | 60702.71868706536 Herceg Novi | Pic Nic | 60417.41134618965 (25 rows) Time: 8.487 ms
Спочатку ми вибираємо найвіддаленіші заклади, використовуючи сортування за відстанню за зменшенням. Після цього нам лишається «пройти» цими даними, вибираючи для кожного рядка найближче місто.
Ще один цікавий запит. Знайдімо, в яких містах найбільше закладів з піцою; вважатимемо, що там більше люблять італійські смаколики. Логічніше, звичайно, було б рахувати відношення кількості піцерій на душу населення, але мені було ліньки шукати інформацію за населеністю, тому обчислимо «абсолютну» любов. Вважатимемо, що піцерія розміщена в місті, якщо від неї до центру не більше ніж 10 км.
SELECT c.name, count(cp) FROM cities_min c, LATERAL (SELECT "name" FROM pizzerias p WHERE earth_distance(ll_to_earth(p.lat, p.lng), ll_to_earth(c.lat, c.lng)) < 10000 ) AS cp GROUP BY c.name ORDER BY count(cp) DESC;
name | count --------------+------- Podgorica | 46 Tivat | 36 Kotor | 31 Budva | 23 Bar | 19 Herceg Novi | 16 Ulcinj | 16 Petrovac | 11 Niksic | 6 Cetinje | 6 Danilovgrad | 3 Bijelo Polje | 3 Zabljak | 3 Pljevlja | 1 Kolasin | 1 (15 rows) Time: 65.703 ms
Мабуть, результати говорять самі за себе: якщо відкинути столицю, туристичні міста на узбережжі виказують значно більшу любов до піци, ніж ті, що розміщуються в горах (навіть наявність гірськолижних курортів не дуже впливає на традиціоналізм місцевих горян).
Висновки
- PostgreSQL має два вбудованих механізми для роботи з локаціями: оператор <@> та набір функцій earth_distance.
- Використовувати ліпше другий, але їх можливо комбінувати.
- PostGIS — найточніший метод оброблення таких даних, але він складніший з усіх боків, тому здебільшого можна обійтися простішим методом earth_distance.
- Звузити межі пошуку, задавши певний обмежений простір для запиту, — завжди слушна ідея.
Матеріал також доступний у форматі відео.
