Le portail francophone de la géomatique

Bonjour,

IL y a hélas beaucoup de paramètres qui entrent en jeu pour optimiser pg/pgrouting.
Quelle est la configuration du serveur Postgresql ? os, versions de PG + Postgis, disques durs, ram.

Par défaut, la configuration de postgresql est assez minimaliste en terme de ressource mémoire affectée a PG.
Il faut la modifier pour utiliser au mieux les ressources du serveur.
Les données du routing peuvent être mises sur un disque dur très rapide également (style SSD et/ou montage RAID).

La table contenant les données est bien indexée sur les champs utilisés par le routing ?
Un vacuum analyse a été lancé sur cette table apres les insertions/mises a jour ?

Nicolas

Dernière modification par Nicolas Ribot (Tue 14 February 2012 12:40)

Bonjour,

je voudrais rebondir sur ce sujet car je rencontre actuellement un probleme similaire sur des temps de reponses de la fonction shortest_path().

J'ai compilé l'ensemble des dernieres sources pour le routing sur une debian squeeze 64bits virtualisée avec openVZ à 4Go de RAM sur un serveur dédié Intel i5 à 3.1GHz (4 coeurs)

postgresql 9.1
postgis 1.5.3 (avec geos 3.3.2 et proj 4.8)
pgrouting 1.05 (avec libboost en paquet, cgal 3.9, gaul-devel 0.1849)


j'ai intégré les données OSM de la france à l'aide de l'outils osm2po.
et j'ai indexé les champs pris en compte lors de la requete shortest_path() (source, target, cost, reverse_cost et la clé primaire) + vacuum full analyze
je me retrouve avec une table comportant un graphe de 3 800 000 enregistrements

lors de l'execution de mes requetes , je me retrouve  avec un temps de reponses avoisinant les 4 secondes.
le temps est le meme que se soit entre deux rues voisines ou entre deux rues dans des villes totalement opposées en france.

J'ai tenté des modifications dans postgres :

shared_memory
maintenance_work_mem
checkpoint_segments
stopper autovacuum

j'ai aussi tenté d'augmenter de modifier le kernel.shmmax dans les parametres du systeme
mais rien de ces changements ne changent mes temps de reponses.

Est-ce une limite CPU qui m'empeche de gagner en performance ?
Y a t'il un parametrage particulier que je n'aurai pas activé ?
Existe t-il une possibilité d'optimiser l'algorythme dans les sources de la librairie de routing ?
Le processus declenché par le routing ne semble pas être multithread (malgré une version 64bits de l'OS). le probleme de lenteur pourrait-il venir de là ?


bref, si vous pouvez m'eclairer à ce sujet.

cordialement,

Jérôme,

C'est une interprétation qui n'est que la tienne ! Peux tu, au moins, me citer le message du lien que tu données qui te permet d'affirmer que "pgRouting découvre depuis peu les problèmes de performances et qu'il n'est pas fait pour être utilisé malgré blablabal"

Merci,

Y.

La recherche d'itinéraire n'est pas «un problème classique». Au mieux ce sont «des problèmes classiques». Il s'agit par nature d'un problème NP-complet, c'est à dire qui possède une explosion combinatoire (exponentielle) des résultats selon la taille du réseau. Tant qu'on ne saura pas si P=NP on aura des soucis pour résoudre ce genre de problème.

La recherche d'itinéraire peut avoir de très nombreuses variantes. Quelques paramètres parmi d'autres :
  - taille du réseau
  - couts fixes ou dynamiques ?
  - réseau orienté ou non ?
  - restrictions de circulation ?
  - géographie disponible ou non ?
  - multimodal ou réseau simple ?
  - feuille de route ?
  - solution exacte ou approchée ?
  - une seule solution ou plusieurs ?
  - optimisation suivant un seul ou des critères ?
  - ....

On peut aussi chercher le problème du voyageur de commerce, des isochrones, de l'optimisation de flotte, etc etc. Il y a plusieurs algorithmes dans PgRouting, non pas pour créer intentionnellement de la confusion, mais pour répondre à différents sous-types de problèmes avec des caractéristiques différentes.

Donc non on ne réinvente certainement pas la roue à chaque fois. Ce domaine est en recherche permanente (voir les travaux du fraunhofer, de bing, osmr, de l'iffstar, etc), et il n'y a pas un seul problème ni une seule solution générique pour chaque problème.

PgRouting a l'avantage d'être directement connecté à la base de donnée. Il est «fait pour être utilisé» (sic !), et fonctionne sur des bases conséquentes, avec les bonnes optimisations.

Ceci étant dit, PgRouting souffre d'erreurs de conceptions. Pour pouvoir améliorer ses performances il faut connaitre son fonctionnement. C'est globalement le suivant à chaque appel :

  - appel d'une fonction de haut niveau de PgRouting (shortest_path par exemple)
  - On lui passe en paramètre une requête SQL, qui renvoie un réseau topologique
  - PgRouting exécute cette requête, récupère le réseau (et les coûts)
  - Il convertit les résultats de la requête en un format utilisable dans les algorithmes de graphe de Boost
  - Il lance l'algo de boost correspondant
  - Il récupère les résultats de boost
  - Il crée une sortie au format PostgreSQL
  - Il renvoie cette sortie

Ce qu'on peut voir là dedans, c'est qu'il y a à chaque appel un chargement du graphe résultant de la requête SQL paramétre, en mémoire dans Boost, à partir de la base de donnée. C'est là que doit se faire l'optimisation, sinon on va charger systématiquement la base entière.
Pour optimiser, il faut passer le graphe le plus petit possible. C'est à dire restreindre le graphe par une préestimation du trajet. Cela peut se faire de diverses manières :
  - par une bounding box (peu efficace dans le cas de trajets longs et en «diagonale»)
  - par une ellipse autour du trajet en ligne droite (ce qui est fait en général, assez efficace)
  - par un calcul préalable sur un sous-réseau

Comme on fait des requêtes géographiques ici, l'indexation est nécessaire et performante.

La dernière possibilité est en général celle qui amène à des bonnes performances : on ne fait pas un seul appel de routing, mais plusieurs, sur des réseaux à différentes échelles. On fait un premier itinéraire plus global sur des nationales par exemple, et on fait les itinéraires du point de départ vers les accès aux nationales dans un second temps. Pareil pour les autoroutes. On peut faire la même chose sur N niveaux.

La vraie solution consisterait à avoir un réseau complet en mémoire sur lequel toutes les requêtes s'exécutent. C'est ce que fait graphserver par exemple. Mais dans ce cas c'est découplé de la base de données, ce qui a des inconvénients aussi.

A noter au passage que PostgreSQL est multi-processus, mais pour une requête on n'a qu'un seul processus de lancé. On sera donc plus efficace sur beaucoup de petites requêtes simultanées que sur peu de grosses requêtes de routing.

En résumé, c'est pas simple !

Le premier travail à faire est d'identifier le goulot d'étranglement. Est ce que le problème vient dans la taille du réseau passé à PgRouting, ou bien de la performance des algorithmes ?

En général c'est la première solution, et dans ce cas la stratégie est d'abord dépendante des contraintes fonctionnelles, ensuite on teste les différentes stratégies ci-dessus qui correspondent, et enfin c'est de l'optimisation de base de données, mais pas de façon aléatoire.

On touche aux paramètres de configuration une fois qu'on sait à peu près comment on doit les changer, et ça passe par l'analyse des requêtes : EXPLAIN sur le SQL, vérification des indexes, optimisation des requêtes (jointures, filtres, filtres spatiaux, etc). Puis optimisations matérielles : SSD, RAM, Partitionnement, etc.

J'espère que ça rétablit un peu de clarté dans vos démarches. Bon courage !

Merci vincent pour cette précision, tu me rassures dans mon constat. Et encore merci, cette fois pour ces pistes sérieuses sur l'optimisation du serveur d'itinéraire.

A priori une ellipse englobante doit être assez difficile à configurer :
  - Le meilleur itinéraire de banlieue à banlieue va souvent passer par le périphérique de l'agglomération, et donc l'itinéraire sera très fortement élargie (et même dans des cas où le rectangle englobant est très étroit (départ / destination dans axe nord / sud ou est / ouest) ça risque d'être tendu).
  - À proximité d'une extrémité, on peut s'éloigner de la destination afin de rejoindre la voie la plus rapide.
  - Le réseau d'autoroute s'approche des agglomérations du pays, quitte à faire quelques zigzags.

Ça risque d'être triste si pour des raisons d'optimisations le trajet nous invite à rallonger notre voyage

Précautions à prendre !!!

Heu l'idée c'était plutôt de dire que c'était une bonne solution qui fonctionnait, faut juste savoir de quoi on parle. Dans ce domaine il n'y a pas de solution boite dès qu'on dépasse certains volumes et un cadre fonctionnel très contraint.

L'ellipse peut être aussi modifiée, en fonction de la densité de voirie par exemple aussi. Mais c'est pour ces cas là notamment que l'approche multi-échelle est plus efficace.

Exactement ce que je dis, car là nous sommes moins dans une situation RTFM (va voir la doc), que dans une situation RTFSC (va voir comment c'est fait).

Malheureusement même si PgRouting est le sujet ici, ce n'est pas le seul à offrir un fonctionnement idéal dans des cadres de démonstration, avec de petites quantités de données, et à se dégrader dès qu'on essaye de généraliser peu à peu son utilisation. Même si avoir une solution prêt à l'emploi n'est pas aisée, connaitre les limites d'un logiciel pourrait être sympathique.

Mais on dépasse un peu le cadre du sujet...

Une petite precision concernant le fonctionnement de pgRouting en mode demo ou prod.
Du temps de sa sortie, Orkney, la boite japonaise qui a travaillé avec C2C sur pgRouting, faisait ses tests sur la voirie de Tokyo, une des plus denses du monde (13 millions d'arcs).
Le temps acceptable pour eux, et atteint si je me souviens bien, etait un routing en moins de 1s.

Nicolas

En fait, Orkney a repris le code de C2C initié par Sylvain Pasche et a continué les dev.

Oui bien sur: avec toutes les optimisations qui vont bien, sur une machine serveur "moyenne" (me rappelle plus les specs de l'epoque, style assez de ram pour que le graphe tienne en memoire), les temps etaient < 1s.

On est d'accord que dans le monde des BD, et particulierement dans le monde postgresql, qui arrive avec une conf ultra minimaliste, la performance d'une requete ou d'un module s'entend APRES avoir configuré le systeme comme il faut, ce qui est difficile et au coeur du métier de DBA.

Nico

En fait, Orkney a repris le code de C2C initié par Sylvain Pasche et a continué les dev.

Oui bien sur: avec toutes les optimisations qui vont bien, sur une machine serveur "moyenne" (me rappelle plus les specs de l'epoque, style assez de ram pour que le graphe tienne en memoire), les temps etaient < 1s.

On est d'accord que dans le monde des BD, et particulierement dans le monde postgresql, qui arrive avec une conf ultra minimaliste, la performance d'une requete ou d'un module s'entend APRES avoir configuré le systeme comme il faut, ce qui est difficile et au coeur du métier de DBA.

Donc, non: pas utilisation bete et mechante de l'API, mais la chaine:
• que sont mes données
• quel est mon matériel
• que veux-je faire
=> je tune tout comme il faut.


Nico

Dernière modification par Nicolas Ribot (Tue 20 March 2012 14:41)

+1 !

(435€ un stage, scandaleux)

Oui Christophe, j'ai fait un petit raccourci. Ce qui n'est vraiment pas terrible, et helas une pratique courante dans les boites privées, c'est de sortir une demande de stage, ou vu les prerequis techniques demandés, on subodore un travail demandé qui sera de la production, vendue a des clients a des taux horaires d'ingénieurs.

Bref, je me concentre sur postgis

Nico

Bonjour,

Je suis (également du verbe suivre) ces échanges depuis hier. Je suis (du verbe être cette fois-ci) à l'origine de cette offre de stage.

En ce qui concerne la rémunération, je suis parfaitement d'accord avec le fait que ce soit scandaleux mais c'est effectivement le minimum légal.  Le bureau d'études où je travaille est une petite structure (12 personnes) et nous sommes assez éloignés des grosses structures qui ont recours à des stagiaires dans le cadre de productions commerciales. Il s'agît là du 2e stage en 6 ans.

Concernant les mots en gras, je suis au fait que le stagiaire qui intégrera notre entreprise ne disposera pas de toutes ces compétences. Ces termes volontairement forts ont été employés afin d'exercer un filtre à la fois en termes de compétences et de motivation du candidat.

Il ne s'agît en aucun cas de développer de A à Z une solution sans aucun accompagnement, mais d'améliorer une application webmapping existante sur une thématique précise par le biais d'un environnement déjà en place (Postgis, Mapserver). En tant que géomaticien dans une PME, je me ferai d'ailleurs un plaisir d'accompagner le stagiaire dans sa réflexion et le développement entrepris. Et contrairement à ce que j'ai lu précédemment, ce n'est pas destiné à la commercialisation, mais fait partie d'un programme de développement interne à l'entreprise.

Concernant la date de début de stage, formulation maladroite. Je dois avouer que ce travail n'était pas destiné à l'origine à un stagiaire, nous ne sommes pas habitués à recourir à des stagiaires (peut-être devrions le faire plus souvent), mais étant particulièrement chargé en ce moment, il nous est apparu comme étant une solution envisageable.

Toutes mes excuses si cette annonce a choqué certains d'entre vous.

Bref, je me concentre également sur postgis

Pas de problème, je ne me sens pas stigmatisé et encore moins scrupuleux

On est d'accord.

Encore une fois, on est d'accord.