Pourquoi une fonction de routage pgr_ * prend-elle une éternité en fonction des données OSM dans une base de données activée pour le pgrouting

9

J'ai chargé l'ensemble de données OSM allemand dans la base de données de pgrouting en utilisant osm2po 4.7.7. Tout fonctionne bien j'ai osm2po mis en place via sa configuration et ça fonctionne comme un charme à travers sa partie Java.

J'ai eu la table * _2po_4pgr importée sans aucun problème. Même la table * 2po_v est importée, bien que je ne comprenne pas complètement la relation de cette table.

J'ai exécuté la fonction pgr_createTopology qui a fonctionné pendant un certain temps (12000 secondes) tout en calculant tous les bords de 6 m. Je pensais que cela ferait l'affaire, mais c'est quand même insupportablement lent.

Je voudrais savoir si j'ai oublié quelque chose. Je pensais à utiliser pgRouting au lieu de la bibliothèque java mais pour le moment, ses performances sont tout simplement hors de comparaison.

Johnny Cusack
la source
1
avez-vous créé des index, avez-vous réglé les variables de mémoire postgis? createTopology n'est exécuté qu'une seule fois pour l'ensemble de données, ses performances n'ont donc pas beaucoup d'importance. Note de côté. J'ai eu toute la Finlande à partir du jeu de données digiroad (comme 2G du réseau routier) et j'ai retourné des résultats en max 250 ms, généralement 125 ms sans aucune optimisation. Donc ça devrait être mieux maintenant
simplexio
Il existe des index sur les colonnes source et cible créés automatiquement par le générateur de script osm2po. Plus besoin? J'ai changé les variables work_mem / maintenance_work_mem en valeur GigaByte, redémarré, toujours pas de changement. Existe-t-il un modèle de script de démarrage dont je pourrais avoir besoin?
Johnny Cusack
1
Hmmm ... Que fait createTopology ()? Je veux dire, osm2po crée déjà la topologie basée sur OSM-Node-IDs. Il n'est donc pas nécessaire d'exécuter qc. similaire à nouveau. Pour pgRouting (shortest_path & shortest_path_astar), vous n'avez besoin que de la table 4pgr créée. C'est tout.
Carsten
J'ai maintenant un ensemble de données finlandaises, postgis 2.0.3, pgrouting 2.0.0-dev. Et je dois dire que c'est lent. toujours sur 1 sec pour le résultat lors de l'utilisation de pgr_astar (). Je vérifie si j'obtiens un peu plus vite
simplexio

Réponses:

5

Le problème avec les performances de pgRouting semble être que les nouveaux pgr_astar et pgr_dijkstra utilisent un graphe entier (ce qui garantit la solution s'il y en a un). Une solution simple pour obtenir de meilleures performances est de limiter le graphique utilisé à une zone plus petite. Il a ses propres problèmes comme parfois il peut créer des graphiques qui ne peuvent pas être résolus

 (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) 

Crée BBOX sur la collection source et cible et l'étend de 0,1 degré, puis la même requête est utilisée pour limiter la taille du graphique dans la requête pgr_

Dijkstra de 1,2 s à ~ 65 ms

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 à ~ 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 a été utilisé pour importer des données (finland-latest) dans le tableau postgis. index gist ajouté à la colonne geom_way et analyse complète du vide pour la base de données. mémoire partagée 1G. workmem 512M

simplexio
la source
J'ai eu la même idée avec la boîte englobante, toujours bien au-delà de 90 secondes, même avec les variables de mémoire définies, etc.
Johnny Cusack
j'ai 380k lignes? vous avez probablement quelque chose comme des lignes 3M + dans la table de routage?
simplexio
1
C'est l'un des principaux problèmes de Postgres pour ne pas mettre en cache l'ensemble du graphique. Cela fonctionne assez rapidement. Mais je dois le connecter à d'autres tables de base de données, ce qui crée dans la situation actuelle (test) un énorme goulot d'étranglement avec seulement 5 qps (requêtes par seconde)
Johnny Cusack
1
Je viens de charger un sous-ensemble de 1 M de lignes dans un disque virtuel pour comparer. pgr_dijkstra prend 3 secondes dans une course à froid. pgr_astra avec l'exemple bbox fourni par @simplexio, cela prend environ 900 ms pour un run à froid. Il semble donc que je doive tout mettre dans un ramdisk pour de bonnes performances.
Johnny Cusack
1
Génial! avec les index de @ kttii, je cours vite maintenant!
Magno C
5

Je suis finalement arrivé à la conclusion qu'il est préférable de placer le graphique entier (y compris les indices) sur un espace de table séparé qui réside en permanence en mémoire à l'aide d'un disque virtuel.

Pour configurer le ramdisk sur Ubuntu 13.04, j'ai utilisé les instructions suivantes et je dois dire que cela fonctionne assez bien (il comprend des instructions pour recharger les données en mémoire après un redémarrage / redémarrage).

La semaine prochaine, je vais mettre la main sur de nouveaux SSD (1 Go / s en lecture) et essayer de comparer les performances.

Pour autant que je vois, c'est la seule solution pour garder un graphique de 1M + lignes accessible en permanence, car il se produit une lecture aléatoire continue.

Johnny Cusack
la source
Comment avez-vous créé l'ensemble du graphique (y compris les indices)? Je n'ai rien vu dans la documentation de pgrouting.
Dennis Bauszus
J'ai utilisé osm2po, un incroyable morceau de code java! osm2po.de
Johnny Cusack
5

Utilisez ce guide pour configurer des index pour une base de données spatiale. En voici l'essentiel:

 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

pour mes tables _4pgr et _vertex, seules les colonnes source et cible avaient des index après l'importation (osm2po-core-5.1.0).

kttii
la source
Fantastique! de ~ 45 sec à ~ 15 sec en utilisant OSM Amérique du Sud complet avec auto-jointure.
Magno C
Désolé ... mon erreur. de ~ 45 sec à ~ 5 ms !!!!!!
Magno C