¿Cómo puedo optimizar pgrouting para velocidad?

Question

Estoy usando pgrouting en una base de datos postgis creado a través de osm2pgrouting. Se comporta muy bien en un conjunto de datos limitado (3.5 k maneras, todo el camino más corto A* búsquedas < 20 ms).

Sin embargo, ya me han importado un mayor cuadro delimitador (122k formas) de europa.osm el rendimiento bajó mucho (un camino más corto, cuesta alrededor de 900ms).

Yo creo que el uso de Un* la mayoría de los bordes nunca va a ser visitado, ya que están fuera del camino.

Lo que he hecho hasta ahora, en un intento de mejorar la velocidad:

• Poner un índice en la geometría de la columna (ningún efecto apreciable)
• El aumento de mi memoria de 8GB a 16GB
• Cambiar el postgresql configuración de la memoria (shared_buffers, effective_cache_size) de 128 MB, 128 MB) a (1, 2) (ningún efecto apreciable)

Tengo la sensación de que la mayoría del trabajo que se está haciendo en la C Impulsar la biblioteca, donde el gráfico que se está realizando para la optimización de postgresql no me dará resultados mucho mejores. Como hago cambios de menor importancia para el conjunto de filas que seleccionar Un* por cada búsqueda que me da un poco de miedo que el impulso de la biblioteca no puede caché de mi gráfica y tiene que reconstruir todos los 122k bordes cada vez que (a pesar de usar un subconjunto limitado de cada consulta). Y no tengo idea de cuánto se gasta haciendo que en comparación con el camino más corto de búsqueda.

¿Alguno de ustedes uso de pgrouting en un 122k o más conjunto de datos de OSM? Lo que el rendimiento que debo esperar? Cuáles son los ajustes que afectan el rendimiento de la mayoría?

Answer 1

Cuando se enfrentan con tareas como esta su principal objetivo es ser racional. No cambie los parámetros basados en la "sensación de la tripa'. Mientras que el intestino parece que funciona para Hollywood no para nosotros que vivimos en el mundo real. Bueno, al menos no en mi instinto ;-).

Usted debe:

1. establecer un utilizable y repetible métrica (como el tiempo requerido por un pgrouting consulta)

2. guardar métrica de resultados en una hoja de cálculo y un promedio de ellos (desechar las mejores y peores). Esto le dirá si los cambios que están haciendo va en la dirección correcta

3. el monitor de su servidor a través de la parte superior y vmstat (asumiendo que estás en *nix) mientras se ejecutan las consultas y buscar patrones significativos: un montón de io, alto de la cpu, la memoria de intercambio, etc. Si la cpu está a la espera de i/o, a continuación, tratar de mejorar el rendimiento del disco (esto debería ser fácil, ver más abajo). Si la CPU en lugar de al 100% sin ningún disco significativo acticity usted tiene que encontrar una manera de mejorar la consulta (esto es, probablemente, va a ser más difícil).

Por el bien de la simplicidad que asumir que la red no está jugando ningún papel importante aquí.

La mejora de rendimiento de base de datos

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

Leer el libro me recomienda ya aquí.

Usted realmente debe leer. Creo que los capítulos pertinentes para este caso son 5,6,10,11

Mejorar el rendimiento del disco

1. Obtener un disco SSD y poner a toda la base de datos. El rendimiento de la lectura será más probable cuádruple y el rendimiento de escritura también debe mejorar radicalmente

2. asignar más memoria a postgres. Idealmente, usted debe ser capaz de asignar memoria suficiente para que la totalidad (o la parte más caliente) puede ser almacenado en caché en la memoria, pero no demasiado para que el intercambio se produce. El intercambio es muy malo. Esto se trata en el libro citado en el párrafo anterior

3. deshabilitar atime en todos los discos (agregar el noatime opciones para fstab)

La mejora de rendimiento de la consulta

El uso de las herramientas descritas en el libro citado anteriormente para el seguimiento de sus consultas/erótico y encontrar paradas de que vale la pena optimizar.

Actualización

Después de los comentarios que he mirado el código fuente para el procedimiento almacenado

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

y parece que una vez que la consulta ha sido afinado no hay mucho más margen de mejora, ya que el algoritmo se ejecuta por completo en la memoria (y, por desgracia, en sólo una cpu). Me temo que su única solución es encontrar una mejor/más rápido o algoritmo que puede ejecutar multiproceso y luego integrarlo con postgres, ya sea por la creación de una biblioteca como la de pgrouting o el uso de algunos de middleware para recuperar los datos (y la memoria caché, tal vez) y alimentar el algoritmo.

HTH

Answer 2

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

Estoy usando Estrella fugaz con un millón y medio de filas en la tabla de enrutamiento. Se tarda casi diez segundos para calcularlo. Con 20k filas que lleva casi tres segundos. Necesito Estrella fugaz porque tengo la necesidad de restricciones de giro.

Aquí están algunas ideas que estoy tratando de implementar:

• En el SQL donde pgRouting obtener las formas, el uso de un st_buffer por lo que no recibe todas maneras, pero sólo los "cercanos" maneras:

  select * from shortest_path_shooting_star( 'SELECCIONE derrota.* DE enrutamiento de derrota, (seleccione st_buffer(st_envelope(st_collect(geometría)), 4) como la geometría de enrutamiento where id = '|| source_ | | "id =' || blanco || ') e DONDE derrota.la geometría && e.geometría', el origen, destino, true, true);

Se ha mejorado el rendimiento, pero si la forma en que debe ir fuera del búfer, puede devolver una "ruta de acceso no encontrada", así que... buffer grande? varias llamadas aumentar el buffer hasta que encuentra un camino?

• Vías rápidas en caché

Como dassouki sugerido, voy caché de algunos "útil" rutas por lo que si la distancia es demasiado largo, se puede ir a través de estas vías rápidas y sólo tenemos que encontrar la manera de entrar y salir de ellos.

• La tabla de la partición por el sig índice

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

Por favor, seguir posteando si te encuentras con otra idea.

También, ¿sabes si hay algún compilado de pgRouting para Postgres9?

Answer 3

Acabamos de crear un branch en git para una ruta más corta restringidos de vuelta a https://github.com/pgRouting/pgrouting/tree/trsp

Lo siento no hay documentación, pero pero si preguntas en la lista de pgRouting cuelgue por ahí y va a responder. Este código funciona mucho más rápido que la estrella fugaz y se basa en el algoritmo de Dijkstra.

-Steve