Выполнение поиска близости местоположения в базе данных с помощью библиотеки геометрии S2
Я работаю над проектом, который требует быстрого выполнения запросов близости к базе данных с данными о местоположении.
В моей базе данных я хочу хранить местоположения с дополнительной информацией. Идея состоит в том, что пользователь открывает карту в определенном месте, а моя программа выбирает только маркеры, видимые пользователю. Если я планирую иметь миллионы значений, получение маркеров из Нью-Йорка при увеличении масштаба Лондона приведет к очень медленной работе карты, а данные, которые я отправляю обратно из базы данных, будут ОГРОМНЫМИ.
Вот почему, когда пользователь открывает карту, я хочу получить все маркеры, которые, например, находятся на расстоянии 10 км от центра карты. (Я могу брать маркеры за пределами видимой области. Я просто не хочу получать маркеры, которые находятся на расстоянии 100 км)
После тщательного исследования я выбрал подход S2 Geometry Library с кривой заполнения пространства Гильберта.
Идея сопоставления двухмерного значения с одним целочисленным значением, где чем длиннее общий префикс между двумя индексами, тем пространственно ближе они друг к другу, была большим аргументом в пользу продажи.
Мне нужна моя база данных, чтобы иметь возможность молниеносно выполнять этот запрос SELECT, и я ожидаю, что в будущем у меня будет МНОГО данных, поэтому работа только с одним столбцом - большой плюс.
Кроме того, что меня больше всего заинтриговало, так это возможность выполнять быстрый поиск по близости из-за того, что два числа, которые расположены близко друг к другу на карте, будут иметь 1D-индексы, также близкие друг к другу.
Идея выглядит очень простой (если ничего не упущу).
У меня проблемы с тем, как (если это даже возможно) выбрать минимальное значение и максимальное значение на плоскости 1D, чтобы быть уверенным, что я сканирую всю видимую область.
Большинство ответов и руководств, которые я нахожу в Интернете, предлагают решение, в котором вы берете ограничивающую область, полную меньших «ящиков» индекса S2, а затем просматриваете каждый индекс в базе данных, чтобы увидеть, содержится ли он в одном из «ящиков» из множество. Это легко сделать, но когда у вас есть 50 миллионов записей, невозможно просмотреть каждую из них, чтобы увидеть, находится ли она в одной из «коробок».
Я имею в виду решение, в котором вы берете минимальное значение области и максимальное значение области, в которой вы ищете, и выполняете что-то в строках
SELECT (...) WHERE s2cellid BETWEEN min AND max
Например, я нахожусь в местоположении 47194c и хочу получить все маркеры на расстоянии 10 км, поэтому я беру значение x слева от индексов и значение x справа от индекса и выполняю
BETWEEN 47194c-x AND 47194c+x query
Возможно ли что-то подобное с библиотекой S2? Если нет, то какой подход я должен предпринять, чтобы делать запросы как можно быстрее?
Заранее спасибо :)
[Я планирую использовать PostgreSQL]