Яка СУБД для гео-даних?

Яку СУБД краще використовувати для роботи з гео-даними?
Планується наступне:
багато записів з полем гео-позиції. Поле гео-позиції змінюється з часом.
Основні вибірки — записи, що знаходяться в заданій близькості. Наприклад, вибрати записи, що знаходяться на відстані не більше 100 метрів від позиції х.
Основнии критерієм є ... парам-парам ... швидкість вибірки.
Придивляюсь до PostGIS.
Які варіанти кращі?

👍ПодобаєтьсяСподобалось0
До обраногоВ обраному0
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Кому актуально, можете спитати тут: www.facebook.com/events/149519539070010

мабуть дуже релевантно кидати рекламу в топіки 3річної давності)))

Але ж ми з вами на неї ще досі підписані і відповідаємо ;-)

делите шарик на квадраты в несколько минут (прикиньте какой угол составляют 100 метров на самых северных/южных широтах), каждому квадрату назначаете номер и по номеру строите индекс
в запросе выбираете соседние квадраты, и по результату уже проходите нормальной формулой для расстояния на сфере

каждому квадрату назначаете номер и по номеру строите индекс
и
багато записів з полем гео-позиції. Поле гео-позиції змінюється з часом.
Если точки — самолёты, то часто индексы перестраивать придётся)

Даже в Redis-е уже появились гео-данные :)

Берите ту БД, с которой более-менее знакомы. Думаю на начальном этапе разница в производительности будет небольшой, если конечно разумно подходить к проектированию БД).
Обычно по скорости относительно простых выборок NoSQL БД превосходят традиционные, но в случае с постгрес, это надо еще проверить, т.к. последний достаточно много почерпнул из NoSQL и работает довольно шустро.

Помимо упомянутых ниже вариантов, можете посмотреть в сторону Couchbase. ТОже довольно быстрая, есть спец. индексы и вьюхи для работы с геоданными. Примеры:
#1 #2.
По опыту скажу, что она довольно шустрая БД. Можно выбирать из 2-х схем «хранения информации»: 1) Все хранится в памяти с асинхронной записью на диск; 2) В памяти хранятся только ключи, а данные на диске. Что примечательно, то деградация производительности во втором случае не сильно большая.

Дякую за ще один + у бік постреса.
Подивися на Couch. Як пишуть, він менш гнучкий та менш швидкий ніж Mongo. І, як я розумію, має такі ж проблеми з map/reduce.

Как обстоят дела сейчас с монго 3, но раньше у каучбейса было неомпоримое преимущество, особенно по чтению. А что касается мапоедьюса, то у меня проблем не возникало, плюс сейчас у них появился скл-подобный язык n1ql. Если есть время можете попробовать для себя пару бд, сделать небольшие бенчмарки и выбирать.

Похоже на «кто из друзей сейчас рядом со мной» или «кто сейчас рядом с кафешкой».

Основнии критерієм є ... парам-парам ... швидкість вибірки.
Свой массив в памяти с полным перебором будет быстрее, чем вызов-ответ-выборка из базы данных. Но при условии: при проходе по массиву надо применить аналог fail-fast подхода: сначала не вычисляем реальное точное расстояние между двумя точками через тригонометрическую формулу, а тупо вычитаем пары координат и если abs(abs(x1)-abs(x2))*b + abs(y1-y2)*c > L*a, то пропускаем точку и идём к следующей в цикле. a, b и c — поправочные коэффициенты, x — долгота, y — широта.

Сколько планируется точек с координатами и сколько запросов в секунду?

якщо не самому писати алгоритм, а скористатись вже готовим? ;)

Какой такой алгоритм :-) Тогда любая база с хранимками и простым запросом типа
select t.id from my_table t where my_dist(t.lat, t.lon, p_lat, p_lon) < p_dist
И дело с концом. Кстати, та оптимизация с «abs(abs(...» запросто в подзапросе сработает с хинтом для базы «не разворачивать подзапросы».

а де взяти

my_dist
?
чи не легше використати щось готове типу:
db.collection.find({ location : { $near : [ 50.4020355, 30.5326905 ] } })
??

my_dist() - функция из справочника, на прошлой работе такую у нас в базе Oracle товарищ Тимофей написал, а я на поза-прошлой работе на PHP накодил:
$rn1=deg2rad($n1); $re1=deg2rad($e1); $rn2=deg2rad($n2); $re2=deg2rad($e2); $rd=60*acos(sin($rn1)*sin($rn2)+cos($rn1)*cos($rn2)*cos($re2-$re1)); $dist=1.852*rad2deg($rd);
pastebin.com/QKnG5Xkx

з якого довідника?
нащо її кожного разу вигадувати на кожній роботі, якщо є готові рішення?

з якого довідника?
В мене був довідник до калькулятора Casio FX-603P, але можна пошукати довідник штурмана — теж там бачив. Або географа — чому б ні.
нащо її кожного разу вигадувати на кожній роботі, якщо є готові рішення?
Якщо є вже давно стара база на Oracle і надійшла задача № 1001, яку потрібно вирішити за кілька днів, то нашо туди ще пхати нові фреймворки та інші бази? Там потрібно було складати списки найближчих точок до кожної. Вирішував адмін.
А мені потрібно було лише на сайт формочку збацати — тим паче.
надійшла задача № 1001
щось в цьому однозначно є...
хоча мені здається, що у ТС ще нема
стара база на Oracle
а все тільки починається)

Об’єктів з позиціями буде декілька мільйонів. Запитів до 1000.
Як я розумію, ваша реалізація потребує проходу по всім об’єктам для вибірки декількох?
Може краще мати індекси на x та y і першим колом відібрати ті x та y, що ± декілька одиниць від потрібного значення, а потім з них відібрати необхідіні?
Варіант з масивом даних у пам’яті не хотілося б розглядати через важкість горизонтального масштабування та неузгодженості даних. Позиції завжди змінються у об’єктів

Може краще мати індекси на x та y
Ви ж казали, що
Поле гео-позиції змінюється з часом.
Позиції завжди змінються у об’єктів
Звичайно ж індекси прискорюють пошук, але ж вони одночасно гальмують вставку/зміну, якщо при цьому змінюється індекс. Якщо у вас декілька мільйонів точок рухаються, то індекс буде цікавий.

Написал однопоточный тест на древнеэльфийском языке — получил на ноуте 1000 поисков по 2 млн. записям за 4.5 секунды. Не вложился :-) Код тут: pastebin.com/f5iyLbFT

Я собирал несколько раз под debian 7 и один раз под Ubuntu 12 тайловый геодезический сервер,
switch2osm.org/...ding-a-tile-server-12-04
Он как раз использует postgresql gis, и кучу вспомогательных скриптов на python,
Очень хорошая система, я знаком как минимум с тремя другими технологиями
отображения карт местности, они хуже

у меня есть небольшой положительный опыт с PostgreSQL + PostGIS. имно, если основные данные и так хранятся в постгресе, то это вполне приемлемый вариант. правда, в нашем случае мы поняли, что данных у нас не так много, и можно тупо держать в памяти trie + geohash. у нас, правда, координаты не менялись. впрочем, если координаты меняются незначительно (например, мы отслеживаем движущийся объект), то префикс geohash тоже будет меняться не так сильно, а следовательно, апдейтить (и, соответственно, лочить) нужно будет только часть trie. в общем, поэкспериментируйте с geohash, и поделитесь впечатлениями потом.

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

Postgresql неплох, как по мне

обязательно бд? в одном из проектов для аналогичных целей активно пользовали солр с его гео-фичами. фича описана здесь cwiki.apache.org/...splay/solr/Spatial Search

Цікаво. Раніше не чув про нього. Треба глянути

використовую MongoDB: запустити просто, працює швидко...
але було б цікаво побачити порівняльну характеристику по роботі з геоданими...

А які в вас навантаження? Якого типу запити по гео? Яка версія монго? 3-я суттєво покращила швидкість. Після переходу на 3 — відчули.

Із того з чим доводилось працювати, функціонал з коробки є у:
MongoDB
ElasticSearch
MySQL
PostgreSQL
Aerospike (гео-функціонал є в бетах, скоро реліз версії яка його включатиме)

Вікі-сторінка присвячена таким базам: en.wikipedia.org/wiki/Spatial_database

«Швидкість» обробки — не достатньо конкретний критерій. Чи є ви вимоги до latency, кількість паралельних запитів, вимоги до кількості оброблених за одиницю часу запитів, і т.д.

Делал это в MySQL — но не советую: шаг вправо-влево, и их встроенные функции начинают оперировать наименьшими прямоугольниками, а кастомные очень медленные.

Поэтому только PostGIS — они работают шустро и при любом количестве измерений.

А вы какую гео-базу используете? Мы использовали GeoNames, и с ней есть проблемы качества данных: например, многие города принадлежат сразу стране, минуя уровни остальных административных делений.

Дякую за досвід.
Наразі не використовує ніяку. І поки не плануємо, бо нам не потрібна конвертація точки у щось інше типу назв. Тільки пошук за відстанями

Ещё хинт (не знаю, насколько это актуально в новых версиях MySQL): сначала выловить самые близкие точки очень быстрым поиском — квадратом вокруг точки (±1 радиан от её координат или как-то так), а потом уже делать поиск стандартный proximity search (по радиусу) по тем, кто только в этом квадрате.

ElasticSearch має можливість фільтрувати по дистанції.

Але ж він наче позиціонується як для суцільнотекстового пошуку? Яке слово цікаве)

Якщо хочете прострелити собі ногу, то еластік серч підійде. Взагалі за такі поради треба карати =).

они там пытаются охватить как можно больше «направлений» развития, не только поиск текста.

В Монге есть неплохие гео-индексы ( docs.mongodb.org/...tions/geospatial-indexes ), особенно если расстояния большие и прямоугольника для вычисления явно не достаточно, хотя гео-индексы есть не только в монге но и во многих sql СУБД. (для радиуса в 100 метров хватит и прямоугольника — для 100 км уже может не хватить в зависимости от широты).

Делал такую задачу — поиск ближайшего города к lat, ln юзера. При старте загружал пару миллионов координат городов в kd-tree. При заходе координаты юзера tree.getClosestCity(lat, lon). Выборка за микросекнду. Никакой БД для этого не надо. Все в памяти. Дерево пару сотен метров.

Изменения данных не проблема. Дерево можно баласнировать периодически.

Теж робили подібний «хак», коли великий обсяг даних запхати при ініціаліцзації у якусь структуру. І періодично синхронізувати зміни (дані змінються). Проте для нас це не виявилось найкращим, бо швидкість доступу не настільки зростає, як падає гнучкість та може з’явитись неузгодженність даних.

коли великий обсяг даних
Великий це який?

Сумарно біля 50 тисяч об’єктів. Кожен з них міг мати від 20 до 50 полів даних

Тю. Так це взагалі фігня. Так в чому проблема? У Вас на 50к обєктів повільно працює пошук? Повільно це скільки? Можливо ви перебором користуєтесь =)?

Вся проблема була в тому, що в пікові години було до 200 користувачів на секунду. Кожен користувач генерува декілька запитів на вибірку і вставку.

Будуєте kd-дерево. Вибірка з дерева це декілька мікросекунд. При 200 рек-сек це буде пару мілісекунд. З кожною вставкою дерево трохи деградує. Раз в хвилину перебалансовуєте. Все.

IMHO здесь вопрос не в выборе базы данных, а в том как построишь индекс. Другими словами, здесь важнее выбор суррогата: по заданным координатам определить страну, город, квадрат, на что ты там ещё ориентируешься. И уже по этому параметру строить индекс, и по нему искать.

Расстояние ты тоже будешь считать не кругом, а квадратом. Почему так: пользователю мало интересно реальное расстояние с высоты птичьего полёта. Город — это сеть препятствий. А потому расстояние — весьма условная величина, нужен маршрут. Следовательно, сначала делаешь грубую прикидку (поиск по индексу), потом строишь маршрут и определяешь расстояние. Притом последние 2 фичи отложи на более поздние этапы реализации, когда будет время. Возможно даже научишься одним запросом кидать.

Далее — расстояние 100м слишком маленькое. Это длина обычной пятиэтажки. Человек передвигается со скоростью 6 км/час, а значит всё что в пределах 500м — это на расстоянии 5 минут. Вот и не задалбывай пользователя избыточными данными и запросами, просто очерти круг кто/что находится в 5 мин, кто в 10 мин. Если у человека менее 10 минут — ему твоя программа точно не интересна, он спешит и точно знает куда.

Гео данные легко укладываются в обычные типы данных + геометрические типы данных.
Т.е. вам нужна база поддерживающая spatial data types.
Как уже писали ранее- postgresql поддерживает данные типы данных «из коробки»
Можно добавить

PostGIS
как фреймворк для организвции индексов и прочего.
1. Postgresql -www.postgresql.org/...c/datatype-geometric.html
Есть еще Oracle Spatial — www.oracle.com/...atial/overview/index.html
MySQL тоже поддерживает spatial data types -dev.mysql.com/...en/spatial-datatypes.html

есть модуль в db2 и вроде postgresql поддерживает гео данные

Підписатись на коментарі