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

Olya Kapinos Head of Marketing в Skyworker 14.03.2018 17:59

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

Відповісти

Підтримати

Віталій Мартиник Senior Software Engineer в United Software 14.03.2018 18:46

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

Відповісти

Підтримати

Olya Kapinos

Volodymyr Spodaryk Software Engineer 14.03.2018 23:17

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

Відповісти

Підтримати

Віталій Мартиник

Xuz Ypol 08.08.2015 14:36

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

Відповісти

Підтримати

Егор 08.08.2015 16:36

каждому квадрату назначаете номер и по номеру строите индекс

и

багато записів з полем гео-позиції. Поле гео-позиції змінюється з часом.

Если точки — самолёты, то часто индексы перестраивать придётся)

Відповісти

Підтримати

Xuz Ypol

Александр Лозовюк CTO/Co-founder в CoinIndex 07.08.2015 18:25

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

Відповісти

Підтримати

Alexander 07.08.2015 16:15

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

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

Відповісти

Підтримати

Юрій Чугаєнко Node.js se 08.08.2015 00:39

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

Відповісти

Підтримати

Alexander

Alexander 08.08.2015 22:16

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

Відповісти

Підтримати

Юрій Чугаєнко

Егор 07.08.2015 14:52

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

Відповісти

Підтримати

Егор 07.08.2015 15:27

Основнии критерієм є ... парам-парам ... швидкість вибірки.

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

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

Відповісти

Підтримати

Егор

Volodymyr Spodaryk Software Engineer 07.08.2015 17:17

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

Відповісти

Підтримати

Егор

Егор 07.08.2015 17:30

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

Відповісти

Підтримати

Volodymyr Spodaryk

Volodymyr Spodaryk Software Engineer 07.08.2015 18:58

а де взяти

my_dist

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

Відповісти

Підтримати

Егор

Егор 08.08.2015 17:28

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

Відповісти

Підтримати

Volodymyr Spodaryk

Volodymyr Spodaryk Software Engineer 09.08.2015 11:30

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

Відповісти

Підтримати

Егор

Егор 09.08.2015 12:07

з якого довідника?

В мене був довідник до калькулятора Casio FX-603P, але можна пошукати довідник штурмана — теж там бачив. Або географа — чому б ні.

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

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

Відповісти

Підтримати

Volodymyr Spodaryk

Volodymyr Spodaryk Software Engineer 09.08.2015 13:11

надійшла задача № 1001

щось в цьому однозначно є...
хоча мені здається, що у ТС ще нема

стара база на Oracle

а все тільки починається)

Відповісти

Підтримати

Егор

Юрій Чугаєнко Node.js se 08.08.2015 00:25

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

Відповісти

Підтримати

Егор

Егор 08.08.2015 17:38

Може краще мати індекси на x та y

Ви ж казали, що

Поле гео-позиції змінюється з часом.

Позиції завжди змінються у об’єктів

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

Відповісти

Підтримати

Юрій Чугаєнко

Егор 08.08.2015 21:25

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

Відповісти

Підтримати

Юрій Чугаєнко

Александр Колосов 05.08.2015 23:22

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

Відповісти

Підтримати

Sergiy Matusevych вечный чайник 05.08.2015 21:09

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

Відповісти

Підтримати

Grez 05.08.2015 16:55

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

Відповісти

Підтримати

Vlad Skachkov не мэнт в НГУ 05.08.2015 16:25

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

Відповісти

Підтримати

Ruslan K 05.08.2015 15:10

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

Відповісти

Підтримати

Юрій Чугаєнко Node.js se 05.08.2015 23:07

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

Відповісти

Підтримати

Ruslan K

Volodymyr Spodaryk Software Engineer 05.08.2015 14:45

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

Відповісти

Підтримати

Юрій Чугаєнко Node.js se 05.08.2015 23:01

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

Відповісти

Підтримати

Volodymyr Spodaryk

Igor Melnick Mastermind в Bid-Robot 05.08.2015 13:48

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

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

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

Відповісти

Підтримати

Alexander Skakunov Founder в Місія на Марс 05.08.2015 12:41

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

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

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

Відповісти

Підтримати

Юрій Чугаєнко Node.js se 05.08.2015 12:49

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

Відповісти

Підтримати

Alexander Skakunov

Alexander Skakunov Founder в Місія на Марс 05.08.2015 14:04

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

Відповісти

Підтримати

Юрій Чугаєнко

Oleg Kuprovskiy Web developer в Kindgeek 05.08.2015 12:24

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

Відповісти

Підтримати

Юрій Чугаєнко Node.js se 05.08.2015 22:58

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

Відповісти

Підтримати

Oleg Kuprovskiy

Дмитро Думанський Co-Founder в Blynk 05.08.2015 23:04

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

Відповісти

Підтримати

Юрій Чугаєнко

Сергей 10.08.2015 15:31

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

Відповісти

Підтримати

Юрій Чугаєнко

Oleksandr Zakrevskyi Developer 05.08.2015 12:18

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

Відповісти

Підтримати

Дмитро Думанський Co-Founder в Blynk 05.08.2015 12:16

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

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

Відповісти

Підтримати

Юрій Чугаєнко Node.js se 05.08.2015 12:44

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

Відповісти

Підтримати

Дмитро Думанський

Дмитро Думанський Co-Founder в Blynk 05.08.2015 12:46

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

Великий це який?

Відповісти

Підтримати

Юрій Чугаєнко

Юрій Чугаєнко Node.js se 05.08.2015 12:56

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

Відповісти

Підтримати

Дмитро Думанський

Дмитро Думанський Co-Founder в Blynk 05.08.2015 12:59

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

Відповісти

Підтримати

Юрій Чугаєнко

Юрій Чугаєнко Node.js se 05.08.2015 13:19

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

Відповісти

Підтримати

Дмитро Думанський

Дмитро Думанський Co-Founder в Blynk 05.08.2015 13:26

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

Відповісти

Підтримати

Юрій Чугаєнко

Олексій Пєніє 05.08.2015 08:28

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

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

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

Відповісти

Підтримати

Lyova Zi 05.08.2015 05:27

Гео данные легко укладываются в обычные типы данных + геометрические типы данных.
Т.е. вам нужна база поддерживающая 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

Відповісти

Підтримати