Estou usando o pgrouting em um banco de dados postgis criado por meio do osm2pgrouting. Ele executa muito bem em um conjunto de dados limitado (3,5 mil maneiras, todo o caminho mais curto A * pesquisa <20 ms).
No entanto, desde que importei uma caixa delimitadora maior (122k maneiras) da europe.osm, o desempenho caiu muito (um caminho mais curto custa cerca de 900ms).
Eu acho que usando A * a maioria dessas bordas nunca será visitada, pois estão fora do caminho.
O que fiz até agora na tentativa de melhorar a velocidade:
- Coloque um índice na coluna de geometria (sem efeito perceptível)
- Aumentei minha memória de 8GB para 16GB
- Altere as configurações de memória do postgresql (shared_buffers, effective_cache_size) de (128MB, 128MB) para (1GB, 2GB) (sem efeito perceptível)
Tenho a sensação de que a maior parte do trabalho está sendo feita na biblioteca C Boost, onde o gráfico está sendo feito, para otimizar o postgresql não me dará resultados muito melhores. Como faço pequenas alterações no conjunto de linhas que seleciono para A * em todas as pesquisas, tenho um pouco de medo de que a biblioteca de impulso não consiga armazenar em cache meu gráfico e precise reconstruir todas as arestas de 122k todas as vezes (mesmo que use apenas uma subconjunto limitado a cada consulta). E não tenho ideia de quanto é gasto fazendo isso em comparação com a pesquisa de caminho mais curta real.
Algum de vocês usa pgrouting em um conjunto de dados OSM 122k ou superior? Que desempenho devo esperar? Quais configurações afetam mais o desempenho?
Respostas:
Quando confrontado com tarefas como essa, seu objetivo principal é ser racional. Não mude os parâmetros com base no "pressentimento". Embora o intestino pareça funcionar para Hollywood, não para nós que moramos no mundo real. Bem, pelo menos não meu instinto ;-).
Você deve:
estabeleça uma métrica utilizável e repetível (como o tempo necessário para uma consulta de pgrouting)
salve os resultados das métricas em uma planilha e faça a média deles (descarte o melhor e o pior). Isso informará se as alterações que você está fazendo estão indo na direção certa
monitore seu servidor usando top e vmstat (supondo que você esteja no * nix) enquanto as consultas estão em execução e procure por padrões significativos: lotes de io, alta cpu, troca, etc. Se a cpu estiver esperando por E / S, tente melhorar desempenho do disco (isso deve ser fácil, veja abaixo). Se a CPU estiver 100% sem nenhuma atividade significativa do disco, você precisará encontrar uma maneira de melhorar a consulta (isso provavelmente será mais difícil).
Por uma questão de simplicidade, presumo que a rede não esteja desempenhando nenhum papel significativo aqui.
Melhorando o desempenho do banco de dados
Atualize para a versão mais recente do Postgres. A versão 9 é muito melhor que as versões anteriores. É grátis, então você não tem motivos para não.
Leia o livro que eu já recomendei aqui .
Você realmente deveria ler. Eu acredito que os capítulos relevantes para este caso são 5,6,10,11
Melhorando o desempenho do disco
Obtenha uma unidade SSD e coloque todo o banco de dados nela. O desempenho de leitura provavelmente quadruplicará e o desempenho de gravação também deve melhorar radicalmente
atribua mais memória ao postgres. Idealmente, você deve poder atribuir memória suficiente para que todo (ou a parte mais quente) possa ser armazenado em cache na memória, mas não muito para que ocorra a troca. Trocar é muito ruim. Isso é coberto no livro citado no parágrafo anterior
desativar atime em todos os discos (adicione as opções de noatime ao fstab)
Melhorando o desempenho da consulta
Use as ferramentas descritas no livro citado acima para rastrear suas consultas e encontrar paradas que valem a pena otimizar.
Atualizar
Após os comentários, observei o código-fonte do procedimento armazenado
https://github.com/pgRouting/pgrouting/blob/master/core/src/astar.c
e parece que depois que a consulta foi ajustada, não há muito mais espaço para melhorias, pois o algoritmo é executado completamente na memória (e, infelizmente, em apenas um processador). Receio que sua única solução seja encontrar um algoritmo melhor / mais rápido ou um que possa executar multithread e depois integrá-lo ao postgres, criando uma biblioteca como pgrouting ou usando algum middleware para recuperar os dados (e armazená-los em cache, talvez) e alimente-o com o algoritmo.
HTH
fonte
Eu tenho o mesmo problema e estava prestes a perguntar em listas de discussão, então obrigado a todos!
Estou usando o Shooting Star com um milhão e meio de linhas na tabela de roteamento. Demora quase dez segundos para calcular. Com 20k linhas, leva quase três segundos. Preciso de Shooting Star porque preciso das restrições de turno.
Aqui estão algumas idéias que estou tentando implementar:
No SQL em que o pgRouting obtém os caminhos, use um st_buffer para que não obtenha todos os caminhos, mas apenas os caminhos "próximos":
selecione * de shortest_path_shooting_star ('SELECT rout. * FROM roteamento de roteamento, (selecione st_buffer (st_envelope (st_collect (geometry)), 4) como geometria do roteamento onde id =' || source_ || 'ou id =' || target | | ') e ONDE rout.geometry && e.geometry', origem, destino, verdadeiro, verdadeiro);
Melhorou o desempenho, mas se o caminho precisar sair do buffer, ele pode retornar um erro "nenhum caminho encontrado", então ... buffer grande? várias chamadas aumentando o buffer até encontrar um caminho?
Como sugerido por dassouki, armazenarei em cache algumas rotas "úteis"; portanto, se a distância for muito longa, ela poderá percorrer essas rotas rápidas e apenas precisar encontrar a maneira de entrar e sair delas.
Mas suponho que, se for para a memória, realmente não importa ... Deveria testá-lo, de qualquer maneira.
Por favor, continue postando se você encontrar outra idéia.
Além disso, você sabe se existe algum pgRouting compilado para o Postgres9?
fonte
Acabamos de criar uma ramificação no git para um caminho mais curto restrito por vez @ https://github.com/pgRouting/pgrouting/tree/trsp
Desculpe, ainda não há documentação, mas, se você fizer perguntas na lista pgRouting, eu saio lá e responderei. Esse código é executado muito mais rápido que uma estrela cadente e é baseado no algoritmo Dijkstra.
-Steve
fonte
Eu tenho uma tabela de rota de origem que contém ~ 1200000 bordas. No meu i7 com SSD, são necessários 12 segundos para criar uma rota. Minha ideia para aumentar o desempenho é dividir a tabela de borda em várias tabelas de nível de zoom. Quero dizer, o nível idêntico ao google tiles. No 8º nível de zoom, por exemplo, tenho 88 tabelas. Cada tabela contém um subconjunto de estradas e suas áreas se sobrepõem, de modo a calcular uma rota entre dois pontos que ficam a menos de 290 km de distância e leva 2 segundos. No 9º nível, o tempo de cálculo cai para 0,25 s e temos 352 tabelas. A recriação de todos os gráficos, caso editemos estradas, não leva mais de uma hora. A maneira radical de aumentar a velocidade do roteamento é usar o algoritmo de Floyd-Warshall. Mas ninguém sabe quanto é necessário para calcular a matriz predecessora em tantas arestas.
fonte