¿Cómo puedo optimizar el rendimiento de la velocidad?

22

Estoy utilizando pgrouting en una base de datos postgis creada a través de osm2pgrouting. Se desempeña muy bien en un conjunto de datos limitado (3.5k maneras, todas las rutas de acceso más cortas que A * busca < 20 ms).

Sin embargo, ya que he importado un cuadro delimitador más grande (122k formas) desde europe.osm, el rendimiento bajó mucho (la ruta más corta cuesta alrededor de 900 ms).

Pienso que utilizando A *, la mayoría de esos bordes nunca serán visitados ya que están fuera del camino.

Lo que he hecho hasta ahora para intentar mejorar la velocidad:

  • Coloque un índice en la columna de geometría (sin efecto notable)
  • Aumenté mi memoria de 8GB a 16GB
  • Cambie la configuración de la memoria postgresql (shared_buffers, effect_cache_size) de (128MB, 128MB) a (1GB, 2GB) (sin efecto notable)

Tengo la sensación de que la mayor parte del trabajo se está realizando en la biblioteca de C Boost, en la que se está realizando el gráfico, por lo que la optimización de postgresql no me dará mejores resultados. A medida que hago cambios menores en el conjunto de filas, selecciono A * para cada búsqueda, me temo que la biblioteca de refuerzo no puede almacenar en la memoria caché mi gráfico y tiene que reconstruir todos los bordes de 122k cada vez subconjunto limitado a cada consulta). Y no tengo idea de cuánto se gasta haciendo eso en comparación con la búsqueda de ruta más corta real.

¿Alguno de ustedes usa pgrouting en un conjunto de datos de OSM de 122k o más? ¿Qué rendimiento debo esperar? ¿Qué configuraciones afectan más el rendimiento?

    
pregunta mrg 15.11.2011 - 10:01

4 respuestas

10

Cuando te enfrentas a tareas como esta, tu objetivo principal es ser racional. No cambie los parámetros basados en el 'sentimiento intestinal'. Si bien el instinto parece funcionar para Hollywood, no lo es para nosotros que vivimos en el mundo real. Bueno, al menos no mi instinto ;-).

Deberías:

  1. establezca una métrica utilizable y repetible (como el tiempo requerido por una consulta de desarrollo)

  2. guarda los resultados de la métrica en una hoja de cálculo y los promedia (descartar los mejores y los peores). Esto le indicará si los cambios que está realizando van en la dirección correcta

  3. supervise su servidor usando top y vmstat (asumiendo que está en * nix) mientras se ejecutan las consultas y busque patrones significativos: gran cantidad de io, cpu alto, intercambio, etc. Si la cpu está esperando por i A continuación, intente mejorar el rendimiento del disco (esto debería ser fácil, consulte a continuación). Si, por el contrario, la CPU está al 100% sin ninguna actividad de disco significativa, tiene que encontrar una manera de mejorar la consulta (probablemente será más difícil).

En aras de la simplicidad, asumo que la red no está jugando ningún papel importante aquí.

Mejora del rendimiento de la base de datos

Actualiza a la última versión de Postgres. La versión 9 es mucho mejor que las versiones anteriores. Es gratis, así que no tienes ninguna razón, no.

Lea el libro que ya recomendé aquí .

Realmente deberías leerlo. Creo que los capítulos relevantes para este caso son 5,6,10,11

Mejora del rendimiento del disco

  1. Obtenga una unidad SSD y ponga toda la base de datos en ella. Lo más probable es que el rendimiento de lectura sea cuádruple y el rendimiento de escritura también debería mejorar radicalmente

  2. asigna más memoria a postgres. Idealmente, debería poder asignar suficiente memoria para que la totalidad (o la parte más caliente) se pueda almacenar en la memoria caché, pero no demasiado para que se produzca el intercambio. El intercambio es muy malo. Esto se trata en el libro citado en el párrafo anterior

  3. deshabilite el atime en todos los discos (agregue noatime opciones para fstab)

Mejora del rendimiento de las consultas

Utilice las herramientas descritas en el libro citado anteriormente para rastrear sus consultas y encontrar paradas que valgan la pena optimizar.

Actualizar

Después de los comentarios, he mirado el código fuente del procedimiento almacenado

enlace

y parece que una vez que se ha ajustado la consulta, no hay mucho más espacio para mejorar ya que el algoritmo se ejecuta completamente en la memoria (y, desafortunadamente, solo en una CPU). Me temo que su única solución es encontrar un algoritmo mejor / más rápido o uno que pueda ejecutarse con múltiples subprocesos y luego integrarlo con postgres, ya sea creando una biblioteca como pgrouting o usando algún middleware para recuperar los datos (y guardarlos en caché, tal vez) y aliméntalo al algoritmo.

HTH

    
respondido por el unicoletti 15.11.2011 - 14:39
8

Tengo el mismo problema y estaba a punto de preguntar en las listas de correo, ¡así que gracias a todos!

Estoy usando Shooting Star con un millón y medio de filas en la tabla de enrutamiento. Se tarda casi diez segundos en calcularlo. Con 20k filas lleva casi tres segundos. Necesito Shooting Star porque necesito las restricciones de giro.

Aquí hay algunas ideas que estoy tratando de implementar:

  • En el SQL donde pgRouting obtiene las formas, usa un st_buffer para que no se obtenga todas las formas, solo las formas "cercanas":

    selecciona * de shortest_path_shooting_star ( 'SELECCIONAR ruta. * DESDE ruta enrutamiento,             (seleccione st_buffer (st_envelope (st_collect (geometría)), 4) como geometría             de enrutamiento donde id = '|| fuente_ || 'o id =' || objetivo || ') e DONDE rout.geometry & & e.geometría ', fuente, destino, verdadero, verdadero);

Mejoró el rendimiento, pero si el camino necesita salir del búfer, puede devolver un error de "no se encontró la ruta", así que ... ¿búfer grande? varias llamadas aumentando el búfer hasta que encuentre una manera?

  • Rutas rápidas en caché

Como sugirió dassouki, guardaré algunas rutas "útiles" por lo que si la distancia es demasiado larga, puede recorrer estas rutas rápidas y solo tiene que encontrar la forma de entrar y salir de ellas.

  • Tabla de particiones por el índice de gis

Pero supongo que, si va a la memoria, realmente no importa ... Debería probarlo, de todos modos.

Por favor, sigue publicando si encuentras otra idea.

Además, ¿sabe si hay algún pgRouting compilado para Postgres9?

    
respondido por el Délawen 16.11.2011 - 14:08
5

Acabamos de crear una rama en git para una ruta más corta restringida por turnos @ enlace

Lo siento, no hay documentación todavía, pero si haces preguntas en la lista de pgRouting, me quedo y respondo. Este código se ejecuta mucho más rápido que la estrella fugaz y se basa en el algoritmo Dijkstra.

-Steve

    
respondido por el Stephen Woodbridge 10.01.2012 - 01:19
0

Tengo una tabla de ruta de origen que contiene ~ 1200000 bordes. En mi i7 con SSD, se tarda 12 segundos en crear una ruta. Mi idea para aumentar el rendimiento es dividir la tabla de borde en varias tablas de nivel de zoom. Me refiero al nivel que es idéntico a google tiles. En el octavo nivel de zoom, por ejemplo, tengo 88 tablas. Cada tabla contiene un subconjunto de carreteras y sus áreas se superponen entre sí para calcular una ruta entre dos puntos que se encuentran a no más de 290 km de distancia entre sí y toma 2 segundos. En el noveno nivel, el tiempo de cálculo se reduce a 0.25 segundos y tenemos 352 tablas. La recreación de todos los gráficos en caso de que editemos carreteras no toma más de una hora. La forma radical de aumentar la velocidad de enrutamiento es usar el algoritmo Floyd-Warshall. Pero nadie sabe cuánto se necesita para calcular la matriz predecesora en tantos bordes.

    
respondido por el Vadym 05.12.2018 - 16:58

Lea otras preguntas en las etiquetas