Geospatial indexing

Огромное количество продуктов, которые мы делаем, так или иначе работают с геоинформацией. Где находится ближайшее кафе? Или точка выдачи заказа? А ближайший водитель такси? Когда речь идёт о хранении информации об объектах на карте и их поиске, мы приходим к geospatial indexing. Такую задачу ещё иногда называют proximity search (буквально поиск ближайшего).

Посмотрим с вами на общепринятые подходы к решению подобной задачи и попытаемся разобраться, что и где можно заиспользовать из коробки.

Straightforward solution

Давайте начнём с уточнения задачи. Пусть наш пользователь хочет найти все бизнесы рамках некоторого радиуса от его местоположения.

Когда я говорю бизнес, понимаю любое место, где оказывают услуги: магазин, кафе, банк, нотариус, и т.д. Но вообще это может быть что угодно. Люди в сервисе вроде Tinder, курьеры в Лавке или таксист в Uber.

Самым простым подходом будет сделать такой запрос:

SELECT business_id, latitude, longitude 
FROM business 
WHERE (latitude BETWEEN {:my_lat} - radius AND {:my_lat} + radius)
  AND (longitude BETWEEN {:my_long} - radius AND {:my_long} + radius)

Так мы найдём все нужные бизнесы в пределах bounding box нашего круга. Проблема в том, что такой запрос неэффективен. Нам придётся просканировать всю таблицу в БД и проверить каждый отдельный бизнес на условие. Если ваша табличка содержит десятки-сотни миллионов записей, будет неприятно.

Можно попробовать улучшить ситуацию и сделать индексы на latitude и longitude колонки. Это сделает чуть лучше, но не прям.

Даже если у вас есть такие индексы, при запросе мы обойдём все бизнесы в мире (!!!) с подходящей долготой и аналогично с широтой. После чего придётся пересекать два множества объектов. На масштабах планеты это может быть долго. Основная проблема здесь в том, что индексы ускоряют поиск в одном измерении, а не двух. Значит надо замапить долготу и широту в одно единственное измерение, чтобы можно было построить индекс поверх этого измерения.

В нашей задаче есть 2 основных подхода: hash-based и tree-based.

Конечно, тут у нас не все известные подходы, а лишь часть примеров.

Хотя реализации в двух концепциях разные, идея одна и та же: делим карту на небольшие кусочки и строим индекс для быстрого поиска по ним.

Hash-based

Even grid

Even grid -- это когда мы делим планету на равные (в некотором смысле) участки. Каждый участок надо захешировать, после чего по ним можно искать.

Одна ячейка может содержать много бизнесов, и каждый бизнес принадлежит одной ячейке. Детали реализации опустим в силу большой проблемы у такого подхода: неравномерность расположения объектов. В более густонаселённых городах плотность расположения объектов будет выше, чем в городах поменьше.

В идеале уметь хранить участки разного размера. Для более плотных кусочков они будут меньше, когда для менее плотных -- больше:

Потому сразу идём к geohash.

Geohash

Идея довольно простая: давайте поделим планету на 4 квадранта. Каждый из них можем описать двумя битами. У двух левых квадрантов первый бит будет 0, а у двух правых -- 1. Аналогично с верхними/нижними, но со вторым битом.

Дальше берём интересующий нас квадрант и делим его на 4 квадранта поменьше, следуя правилам хеширования выше.

Повторяя такую операцию, мы можем прийти к подходящим для нас размерам.

Можно заметить, что порядок обхода подобной структуры это что-то вроде z-order curves. Похожий подход может использоваться в Delta Lake.

Тут есть небольшое видео с визуализацией уточнения геохеша на сфере.

Бинарное представление можно сконвертить в base32, что позволит работать с геохешом как со строкой.

Посмотрим на пример:

Тут получим u9edd. И логично, что регулируя длину геохеша, мы можем регулировать точность:

Для практических задач нам достаточно иметь геохеш длиной от 4 до 6. Всё что точнее обычно слишком маленькое, а что больше -- слишком большое. Когда мы имеем радиус, в рамках которого нужно что-то найти, нам достаточно понять, какой длины геохеша достаточно, чтобы покрыть наш круг полностью. Например для радиуса 500 метров нам достаточно длины 6.

Ещё одно приятное свойство: геохеш это просто строка. То есть поиск по нему это набор базовых операций со строками. Нам не нужна отдельная БД для такого (хотя и нужны дополнительные навороты в существующие).

Но в каждой бочке мёда.. Конечно, есть корнеркейсы. Например, с соседними ячейками. Если 2 геохеша имеют длинный общий префикс, мы можем с уверенностью утверждать, что они рядом. Но обратное неверно. Например вот геохеш какого-то здания в Краснодаре (szgzbpg):

А вот геохеш другой части этого здания (ub5b005):

Другая проблема -- когда два объекта находятся рядом, но их геохеши отличаются (даже если на 1 символ). Решением тут может быть проверять не только один участок с фиксированным геохешом, но и объекты из всех соседних участков. Вычисление соседних ячеек по геохешу задача несложная и решённая (например, libgeohash в примерно 300 строк).

Конечно, любая попытка положить нашу прекрасную планету (неидеальный эллипсоид) на плоскость будет тянуть за собой трейдофы. Можно посмотреть короткий 6-минутный ролик Why all world maps are wrong.

Cartesian tiers

Когда яндексишь cartesian tiers, первые ссылки будут про Solr. Это такой движок для полнотекстового поиска поверх Lucene. Подразумевается, что текстовые данные могут иметь также и location метаинформацию. И этим можно пользоваться для поиска/скоринга результатов поиска.

Суть подхода в том, чтобы описать карту мира набором слоёв. Первый, как и геохеш, состоит из 4 квадрантов. Второй слой есть первый, в котором каждый квадрант поделили ещё на 4 (всего 16). И т.д. Для практики, говорят, достаточно 20 слоёв (порядка 10^12 квадрантов на самом нижнем). Все операции происходят так же, как и с геохешом, но учитывая свои детали реализации. Останавливаться тут не будем.

Tree-based

Quadtree

Идея тут такая же: рекурсивно делим карту на 4 части, пока у нас выполняется некоторое условие. Таким условием может являться, например, количество объектов на участке. Так мы не будем делиться слишком глубоко в местах, где у нас мало интересующих нас объектов (небольшие города или океан).

Это всё-таки дерево, так что можно представить примерно так:

Но более корректно будет представление на плоскости:

В дефолтной реализации каждая нода дерева будет хранить координаты для левого верхнего и правого нижнего углов + 4 указателя на детей. И обычно такие индексы всегда in-memory. Это не беда, т.к. даже для большого количества объектов весить индекс будет единицы Гб.

Все нужные операции выполняются аналогично, правда тут вам надо "ходить" по дереву в родителя и искать ноды-сиблинги. Т.к. высота дерева небольшая, это не должно быть очень долго.

Правда любые операции по изменению локаций объектов могут привести к сильной перебалансировке дерева. Потому часто quadtree перестраивают в часы отсутствия нагрузки. Оффлайн процесс такой.

Ещё quadtree можно использовать в играх, если речь идёт о трекании объектов на плоскости и каких-то операций с ними. На небольших объёмах может работать довольно быстро:

R-tree

R-tree хорошо бы использовать, когда ваши объекты это не просто точки, а какие-то более сложные полигоны. В отличие от решений выше, листья в R-tree могут пересекаться по объектам.

На практике такая ситуация может возникнуть, когда ваш объект это не просто точка, а огромное место (аэропорт). А объекты в нескольких листьях могут возникать из-за того, что в листья попадают "близкорасположенные" объекты.

Не будем глубоко закапываться в реализацию и детали, т.к. подобные вещи легко находятся. Но вот вам визуализация со сравнением двух видов деревьев на потыкаться.

Google S2

В отличие от других решений, где карта проецируется на плоскость, Google S2 работает с планетой как сферой. Это позволяет сэкономить некоторое количество ресурсов и меньше "врать" из-за трейдофов проекции Земли на плоскость.

Тут видим, что края ячеек изогнуты, т.к. применяется как раз сферическая геометрия, которая ближе к реальной ситуации.

У каждой ячейки есть уровень (от 0 до 30), который говорит о том, как глубоко мы делили мир для получения этой ячейки. Ячейки на последнем, 30м, уровне размера примерно 1см. И их порядка 6 * 4^30.

Тут есть табличка с размерами ячеек относительно уровней.

Очевидно, что ячейки нужно как-то занумеровать. В S2 выбран подход, повышающий локальность. Если посмотреть на картинки про z-order curves, то можно заметить, что в какой-то момент для обхода вам нужно перескочить большой участок. Подход в S2 основан на другом виде space-filling curves -- hilbert curves. И на сфере он позволяет делает переходы между регионами не очень далеко:

На картиночке у нас покрытие планеты кривой на 5 уровне. С таким способом обхода нумерация ячеек обладает следующим свойством, которого у геохеша нет: если ячейки находятся рядом на карте, то и номера у них будут близкими по значению. А это повышает локальность данных для индексации.

В противовес Google S2 есть Uber H3. Тут подразумевается, что планета это не сфера, а икосаэдр (многогранник с 20 гранями), и каждая грань рекурсивно разбивается на гексагоны.

Tech stack

Кроме вышеназванных технологий, можно использовать и другие:

• индексы GiST/SP-GiST в Postgres. Это не самостоятельные решения, но вместе с конкретными подходами, которые позволяют задать отношения между объектами (в нашем случае точками на карте), можно решать нужную задачу. Например, пристраивая поверх R-tree.
• PostGIS расширение к Postgres.
• Redis умеет делать базовые операции из коробки.

Fun part

Есть такой замечательный сервис what3words, который умеет конвертировать любую точку на планете в 3 слова. Например одна из точек, находящаяся примерно на месте офиса Яндекса в Минске может быть закодирована словами ///острый.складка.империя.

Как это счастье работает, я не нашёл, но можно предположить, что имея фиксированный размер конечных точек (он порядка 1м^2) можно поделить геохеш на три части, каждая из которых мапится на некоторое слово в словаре. Правда они явно не делят просто на 3 куска, т.к. у двух точек рядом все три слова отличаются, но это можно делать более хитрыми способами.

1. ByteByteGo видео про дизайн сервиса вроде Yelp. Отсюда надёргал часть картинок.
2. Geohash online.
3. Google S2 geometry.
4. Отличный пост про разные кривые.