Я использую pgrouting в базе данных postgis, созданной с помощью osm2pgrouting. Он работает очень хорошо на ограниченном наборе данных (3,5 тыс. Путей, поиск по кратчайшему пути A * <20 мс).
Однако, так как я импортировал большую ограничительную рамку (122 тыс. Путей) из europe.osm, производительность сильно упала (самый короткий путь стоит около 900 мс).
Я думаю, что при использовании A * большинство этих ребер никогда не будут посещаться, поскольку они находятся вне пути.
Что я сделал до сих пор в попытке улучшить скорость:
- Поместить индекс в столбец геометрии (без заметного эффекта)
- Увеличил мою память с 8 ГБ до 16 ГБ
- Измените параметры памяти postgresql (shared_buffers ,ffective_cache_size) с (128 МБ, 128 МБ) на (1 ГБ, 2 ГБ) (без заметного эффекта)
У меня такое ощущение, что большая часть работы выполняется в библиотеке C Boost, где создается график, поэтому оптимизация postgresql не даст мне намного лучших результатов. Поскольку я делаю небольшие изменения в наборе строк, которые я выбираю для A * для каждого поиска, я немного боюсь, что библиотека boost не сможет кэшировать мой график и должна каждый раз перестраивать все ребра 122k (хотя она будет использовать только очень ограниченное подмножество каждого запроса). И я понятия не имею, сколько потрачено на это по сравнению с реальным поиском по кратчайшему пути.
Кто-нибудь из вас использует pgrouting в наборе данных OSM 122k или выше? Какую производительность мне ожидать? Какие настройки влияют на производительность больше всего?
Ответы:
Когда вы сталкиваетесь с такими задачами, ваша основная цель - быть рациональным. Не меняйте параметры, основываясь на «внутреннем чувстве». Хотя кажется, что кишка работает для Голливуда, это не для нас, живущих в реальном мире. Ну, по крайней мере, не моя интуиция ;-).
Вам следует:
установить пригодную для повторения метрику (например, время, необходимое для запроса pgrouting)
сохранить результаты метрик в электронной таблице и усреднить их (отбросить лучшие и худшие). Это скажет вам, если изменения, которые вы делаете, идут в правильном направлении
Контролируйте ваш сервер, используя top и vmstat (при условии, что вы используете * nix) во время выполнения запросов и ищите существенные шаблоны: много операций ввода-вывода, высокая загрузка процессора, свопинг и т. д. Если процессор ожидает ввода-вывода, попробуйте улучшить производительность диска (это должно быть легко, см. ниже). Если вместо этого процессор на 100% без какой-либо значительной активности диска, вам нужно найти способ улучшить запрос (это, вероятно, будет сложнее).
Для простоты я предполагаю, что сеть здесь не играет существенной роли.
Улучшение производительности базы данных
Обновите до последней версии Postgres. Версия 9 намного лучше, чем предыдущие версии. Это бесплатно, поэтому у вас нет причин, нет.
Прочитайте книгу, которую я рекомендовал уже здесь .
Вы действительно должны прочитать это. Я считаю, что соответствующие главы для этого дела 5,6,10,11
Улучшение производительности диска
Получите SSD-накопитель и поместите на него всю базу данных. Производительность чтения, скорее всего, увеличится в четыре раза, а производительность записи также должна значительно улучшиться
назначьте больше памяти для postgres. В идеале вы должны быть в состоянии выделить достаточно памяти, чтобы вся (или самая горячая часть) могла быть кэширована в памяти, но не слишком много, чтобы произошла перестановка. Обмен очень плох. Это описано в книге, процитированной в предыдущем абзаце
отключите atime на всех дисках (добавьте параметры noatime в fstab)
Улучшение производительности запроса
Используйте инструменты, описанные в приведенной выше книге, чтобы проследить ваши запросы и найти остановки, которые стоит оптимизировать.
Обновить
После комментариев я посмотрел исходный код хранимой процедуры
https://github.com/pgRouting/pgrouting/blob/master/core/src/astar.c
и кажется, что после того, как запрос был настроен, улучшений не остается, так как алгоритм работает полностью в памяти (и, к сожалению, только на одном процессоре). Боюсь, что ваше единственное решение - найти лучший / более быстрый алгоритм или алгоритм, который может работать в многопоточном режиме, а затем интегрировать его с postgres, либо создав библиотеку типа pgrouting, либо используя некоторое промежуточное программное обеспечение для извлечения данных (и, возможно, кеширования) и скормить это алгоритму.
НТН
источник
У меня точно такая же проблема, и я собирался спросить в списках рассылки, так что спасибо всем!
Я использую Shooting Star с миллионом с половиной строк в таблице маршрутизации. На его вычисление уходит почти десять секунд. С 20 тысячами строк это занимает почти три секунды. Мне нужна Падающая звезда, потому что мне нужны ограничения на поворот.
Вот несколько идей, которые я пытаюсь реализовать:
На SQL, где pgRouting получает пути, используйте st_buffer, чтобы не все, а только «соседние» пути:
выберите * из shorttest_path_shooting_star ('ВЫБРАТЬ маршрут. * ИЗ маршрутизации маршрутизации, (выберите st_buffer (st_envelope (st_collect (geometry))), 4) в качестве геометрии из маршрутизации, где id =' || source_ || 'или id =' || target | | ') e ГДЕ rout.geometry && e.geometry', источник, цель, правда, правда);
Это улучшило производительность, но если путь должен выходить за пределы буфера, он может вернуть ошибку «путь не найден», так что ... большой буфер? несколько вызовов, увеличивающих буфер, пока он не найдет способ?
Как предложил Дассуки, я буду кешировать некоторые «полезные» маршруты, поэтому, если расстояние слишком велико, он может пройти по этим быстрым маршрутам и просто должен найти выход в них и из них.
Но я полагаю, что, если речь идет о памяти, это на самом деле не имеет значения ... Все равно стоит это проверить.
Пожалуйста, продолжайте писать, если найдете другую идею.
Кроме того, вы знаете, есть ли какой-нибудь скомпилированный pgRouting для Postgres9?
источник
Мы только что создали ветку в git для кратчайшего пути с ограниченным ходом @ https://github.com/pgRouting/pgrouting/tree/trsp
Извините, но документации пока нет, но если вы зададите вопросы в списке pgRouting, я вывешу там и отвечу. Этот код работает намного быстрее падающей звезды и основан на алгоритме Дейкстры.
-Стив
источник
У меня есть исходная таблица маршрутов, которая содержит ~ 1200000 ребер. На моем i7 с SSD создание маршрута занимает 12 секунд. Моя идея повысить производительность - разделить таблицу границ на несколько таблиц уровней масштабирования. Я имею в виду уровень, который идентичен плитке Google. Например, на 8-м уровне масштабирования у меня 88 таблиц. Каждая таблица содержит подмножество дорог, и их области перекрывают друг друга, поэтому для расчета маршрута между двумя точками, расположенными на расстоянии 290 км друг от друга, требуется 2 секунды. На 9-м уровне время расчета падает до 0,25 сек и у нас 352 таблицы. Воссоздание всех графиков в случае редактирования дорог занимает не более часа. Радикальный способ увеличить скорость маршрутизации - использовать алгоритм Флойда-Варшалла. Но никто не знает, сколько нужно, чтобы вычислить матрицу предшественника на таком количестве ребер.
источник