Mais

Como posso otimizar o pgrouting para aumentar a velocidade?

Como posso otimizar o pgrouting para aumentar a velocidade?


Estou usando o pgrouting em um banco de dados Postgis criado por meio do osm2pgrouting. Ele tem um desempenho muito bom em um conjunto de dados limitado (3,5 mil maneiras, todas as pesquisas de caminho A * mais curtas <20 ms).

No entanto, como importei uma caixa delimitadora maior (122 mil maneiras) da europa.osm, o desempenho caiu muito (um caminho mais curto custa cerca de 900 ms).

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 (nenhum efeito perceptível)
  • Aumentei minha memória de 8 GB para 16 GB
  • Altere as configurações de memória postgresql (shared_buffers, effective_cache_size) de (128 MB, 128 MB) para (1 GB, 2 GB) (nenhum efeito perceptível)

Tenho a sensação de que a maior parte do trabalho está sendo feito na biblioteca C Boost, onde o gráfico está sendo feito, portanto, otimizar o postgresql não me dará resultados muito melhores. Como faço pequenas alterações no conjunto de linhas que seleciono para A * para cada pesquisa, estou com um pouco de medo que a biblioteca boost não possa armazenar em cache meu gráfico e tenha que reconstruir todas as bordas de 122k todas as vezes (embora ela use apenas subconjunto limitado a cada consulta). E não tenho ideia de quanto é gasto para fazer isso em comparação com a pesquisa do caminho mais curto real.

Algum de vocês usa pgrouting em um conjunto de dados OSM de 122k ou superior? Que desempenho devo esperar? Quais configurações afetam mais o desempenho?


Quando confrontado com tarefas como essa, seu objetivo principal é ser racional. Não altere os parâmetros com base no 'pressentimento'. Embora o instinto pareça funcionar para Hollywood, não funciona para nós que vivemos no mundo real. Bem, pelo menos não meu instinto ;-).

Você deve:

  1. estabelecer uma métrica utilizável e repetível (como o tempo necessário para uma consulta de pgrouting)

  2. salve os resultados das métricas em uma planilha e calcule a média deles (descarte os melhores e os piores). Isso vai dizer se as mudanças que você está fazendo estão indo na direção certa

  3. 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: muito io, alta cpu, troca, etc. Se a cpu está esperando por i / o, tente melhorar desempenho do disco (isso deve ser fácil, veja abaixo). Se a CPU estiver em 100% sem nenhuma atividade de disco significativa, você terá que encontrar uma maneira de melhorar a consulta (provavelmente será mais difícil).

Para simplificar, suponho 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. É gratuito, então você não tem razão para não o fazer.

Leia o livro que 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

  1. Pegue 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

  2. atribuir mais memória ao postgres. Idealmente, você deve ser capaz de atribuir memória suficiente para que o todo (ou a parte mais quente) possa ser armazenado em cache na memória, mas não muito para que ocorra a troca. A troca é muito ruim. Isso é abordado no livro citado no parágrafo anterior

  3. desabilite o atime em todos os discos (adicione as opções noatime ao fstab)

Melhorar o desempenho da consulta

Use as ferramentas descritas no livro citado acima para rastrear suas dúvidas e encontrar paradas que valham a pena otimizar.

Atualizar

Após os comentários, olhei para o código-fonte do procedimento armazenado

https://github.com/pgRouting/pgrouting/blob/master/core/src/astar.c

e parece que, uma vez 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 uma cpu). Temo que sua única solução seja encontrar um algoritmo melhor / mais rápido ou que possa rodar multithreaded e então 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 ao algoritmo.

HTH


Eu tenho exatamente o mesmo problema e estava prestes a perguntar nas listas de discussão, então, obrigado a todos!

estou usando Estrela cadente com um milhão e meio de linhas na tabela de roteamento. Demora quase dez segundos para calculá-lo. Com 20 mil linhas, leva quase três segundos. Eu preciso do Shooting Star porque preciso das restrições de direção.

Aqui estão algumas idéias que estou tentando implementar:

  • No SQL, onde pgRouting obtém os caminhos, use um st_buffer por isso não é possível de todas as formas, mas apenas das formas "próximas":

    select * from shortest_path_shooting_star ('SELECT rout. * FROM routing rout, (select st_buffer (st_envelope (st_collect (geometry))), 4) como geometry from routing where id =' || source_ || 'or id =' || target | | ') e WHERE rot.geometria && e.geometria', origem, destino, verdadeiro, verdadeiro);

Isso melhorou o desempenho, mas se o caminho precisar sair do buffer, pode retornar um erro "nenhum caminho encontrado", então ... buffer grande? várias chamadas aumentando o buffer até encontrar uma maneira?

  • Rotas rápidas em cache

Como dassouki sugeriu, vou armazenar em cache algumas rotas "úteis" para que, se a distância for muito longa, ele possa passar por essas rotas rápidas e só tenha que encontrar o caminho de entrada e saída delas.

  • Tabela de partição por índice gis

Mas suponho que, se for para a memória, realmente não importa ... Deveria testar, de qualquer maneira.

Por favor, continue postando se você encontrar outra ideia.

Além disso, você sabe se existe algum pgRouting compilado para Postgres9?


Acabamos de criar um branch no git para um caminho mais curto com restrição de virada @ https://github.com/pgRouting/pgrouting/tree/trsp

Desculpe, não há documentação ainda, mas se você fizer perguntas na lista pgRouting, eu saio por aí e responderei. Este código é executado muito mais rápido do que a estrela cadente e é baseado no algoritmo Dijkstra.

-Steve


Eu tenho uma tabela de rota de origem que contém ~ 1200000 arestas. No meu i7 com SSD, leva 12 segundos para criar uma rota. Minha ideia para aumentar o desempenho é dividir a mesa de borda em várias tabelas de nível de zoom. Quero dizer, o nível idêntico ao do 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 não muito longe de 290 km um do outro, leva 2 segundos. No 9º nível, o tempo de cálculo cai para 0,25 seg e temos 352 tabelas. A recriação de todos os gráficos no caso de editarmos estradas não leva mais de uma hora. A maneira radical de aumentar a velocidade de roteamento é usar o algoritmo Floyd-Warshall. Mas ninguém sabe quanto é necessário para calcular a matriz predecessora em tantas arestas.


Assista o vídeo: Video Tutorial Install mapserver