¿Por qué alguna función de enrutamiento pgr_ * tarda para siempre según los datos de OSM en un DB habilitado para pgrouting

9

Cargué el conjunto de datos OSM alemán en la base de datos pgrouting utilizando osm2po 4.7.7. Todo funciona bien, tengo osm2po configurado a través de su configuración y funciona de maravilla a través de su parte de Java.

Tenía la tabla * _2po_4pgr importada sin ningún problema. Incluso la tabla * 2po_v se importa, aunque no entiendo completamente la relación de esta tabla.

Ejecuté la función pgr_createTopology que se ejecutó durante bastante tiempo (12000 segundos) mientras calculaba los 6m de bordes. Pensé que esto haría el trato, pero aún así es insoportablemente lento.

Me gustaría saber si olvidé algo. Estaba pensando en usar pgRouting en lugar de la biblioteca de Java, pero en este momento su rendimiento solo es incomparable.

Johnny Cusack
fuente
1
¿ha creado índices, ha ajustado las variables de memoria postgis? createTopology solo se ejecuta una vez para todo el conjunto de datos, por lo que su rendimiento no importa tanto. Nota al margen. Tenía toda Finlandia desde el conjunto de datos digiroad (como 2G de red de carreteras) y devolví resultados en un máximo de 250 ms, generalmente 125 ms sin ninguna optimización. Así que debería ser mejor ahora días
simplexio
Hay índices en la columna de origen y destino creados automáticamente por el generador de script osm2po. ¿Se necesita más? Cambié las variables work_mem / maintenance_work_mem a un valor GigaByte, reinicié, todavía no hay cambio. ¿Hay alguna plantilla de script de inicio que pueda necesitar?
Johnny Cusack
1
Hmmm ... ¿Qué hace createTopology ()? Quiero decir, osm2po ya crea la topología basada en OSM-Node-ID. Entonces no hay necesidad de ejecutar algo. similar de nuevo. Para pgRouting (shortest_path & shortest_path_astar) solo necesita la tabla 4pgr creada. Eso es todo.
Carsten
Ahora tengo el conjunto de datos de Finlandia, postgis 2.0.3, pgrouting 2.0.0-dev. Y tengo que decir que esto es lento. siempre durante 1 segundo para obtener resultados cuando se usa pgr_astar (). Compruebo si me pongo un poco más rápido
simplexio

Respuestas:

5

El problema con el rendimiento de pgRouting parece ser que los nuevos pgr_astar y pgr_dijkstra usan un gráfico completo (que garantiza la solución si hay uno). Una solución simple para obtener un mejor rendimiento es limitar el gráfico usado a un área más pequeña. Tiene sus propios problemas, ya que a veces puede crear gráficos que no se pueden resolver.

 (SELECT ST_Expand(ST_Extent(geom_way),0.1) as box  FROM hh_2po_4pgr as l1 WHERE l1.source =7 OR l1.target = 12) 

Crea BBOX sobre la colección de origen y destino y lo expande 0.1 grados, luego se usa la misma consulta para limitar el tamaño del gráfico en pgr_ query

Dijkstra de 1.2s a ~ 65ms

SELECT  seq, id1 AS node, id2 AS edge, g.geom_way as the_geom
    FROM pgr_dijkstra(
            'SELECT id, source, target, cost FROM hh_2po_4pgr as r, 
            (SELECT ST_Expand(ST_Extent(geom_way),0.1) as box  FROM hh_2po_4pgr as l1    WHERE l1.source =7 OR l1.target = 12) as box
            WHERE r.geom_way && box.box',
            7, 12, false, false
    ) as r INNER JOIN hh_2po_4pgr as g ON r.id2 = g.id ;

A * de 2s a ~ 50ms

SELECT seq, id1 AS node, id2 AS edge, cost
    FROM pgr_astar(
           'SELECT id, source, target, cost, x1,y1,x2,y2 FROM hh_2po_4pgr as r, 
             (SELECT ST_Expand(ST_Extent(geom_way),0.1) as box  FROM hh_2po_4pgr as l1    WHERE l1.source =7 OR l1.target = 12) as box
            WHERE r.geom_way && box.box',
            7, 12, false, false
    );

osm2po se utilizó para importar datos (finlandia-último) en la tabla postgis. índice Gist agregado a la columna geom_way y análisis de vacío completo para la base de datos. memoria compartida 1G. workmem 512M

simplexio
fuente
Tuve la misma idea con el cuadro delimitador, todavía más de 90 segundos incluso con los vars de memoria configurados, etc.
Johnny Cusack
tengo 380k lineas? ¿Probablemente tenga algo como 3M + líneas en la tabla de enrutamiento?
simplexio
1
Este es uno de los principales problemas en Postgres para no almacenar en caché todo el gráfico. Funciona bastante rápido. Pero necesito conectarlo con otras tablas de base de datos que crean en la situación actual (prueba) un enorme cuello de botella con solo 5qps (consultas por segundo)
Johnny Cusack
1
Acabo de cargar un subconjunto de filas de 1M en un disco RAM para comparar. pgr_dijkstra tarda 3 segundos en una carrera en frío. pgr_astra con el ejemplo de bbox proporcionado por @simplexio, toma alrededor de 900 ms para una ejecución en frío. Así que parece que tengo que poner todo en un disco RAM para un rendimiento adecuado.
Johnny Cusack
1
¡Excelente! con los índices de @ kttii, ¡ahora estoy corriendo rápido!
Magno C
5

Finalmente llegué a la conclusión de que es mejor colocar todo el gráfico (incluidos los índices) en un espacio de tabla separado que reside permanentemente en la memoria utilizando un disco RAM.

Para configurar el ramdisk en Ubuntu 13.04, utilicé las siguientes instrucciones y debo decir que funciona bastante bien (incluye instrucciones para volver a cargar los datos en la memoria después de reiniciar / reiniciar).

La próxima semana echaré un vistazo a los nuevos SSD (1 GB / s de lectura) e intentaré comparar el rendimiento.

Por lo que veo, es la única solución para mantener un gráfico de filas de 1M + permanentemente accesible, ya que ocurren lecturas aleatorias continuas.

Johnny Cusack
fuente
¿Cómo creaste el gráfico completo (incluidos los índices)? No vi nada en la documentación de pgrouting.
Dennis Bauszus
¡Usé osm2po, una increíble pieza de código java! osm2po.de
Johnny Cusack
5

Use esta guía para configurar índices para una base de datos espacial. Aquí está la esencia de esto:

 1. create indexes on ID, source and target columns.
 2. create index using GIST on geom column.
 3. vacuum
 4. cluster on geom column
 5. analyze

para mis tablas _4pgr y _vertex, solo las columnas de origen y destino tenían índices después de la importación (osm2po-core-5.1.0).

kttii
fuente
¡Fantástico! de ~ 45 segundos a ~ 15 segundos con OSM completo de América del Sur con autounión.
Magno C
Perdón mi error. de ~ 45 segundos a ~ 5 ms !!!!!!
Magno C