Comment puis-je optimiser le pgrouting pour la vitesse?

22

J'utilise pgrouting sur une base de données postgis créée via osm2pgrouting. Il fonctionne très bien sur un ensemble de données limité (voies de 3,5 km, toutes les recherches A * du chemin le plus court <20 ms).

Cependant, depuis que j'ai importé une boîte englobante plus grande (122k voies) d'europe.osm, les performances ont beaucoup baissé (le chemin le plus court coûte environ 900 ms).

Je pense que l'utilisation de A * la plupart de ces bords ne seront jamais visités car ils sont à l'écart.

Ce que j'ai fait jusqu'à présent pour essayer d'améliorer la vitesse:

  • Mettre un index sur la colonne de géométrie (pas d'effet notable)
  • Augmentation de ma mémoire de 8 Go à 16 Go
  • Modifiez les paramètres de mémoire postgresql (shared_buffers, effective_cache_size) de (128 Mo, 128 Mo) à (1 Go, 2 Go) (pas d'effet notable)

J'ai le sentiment que la plupart du travail se fait dans la bibliothèque C Boost où le graphique est fait, donc l'optimisation de postgresql ne me donnera pas de bien meilleurs résultats. Comme je fais des changements mineurs à l'ensemble de lignes que je sélectionne pour A * pour chaque recherche, j'ai un peu peur que la bibliothèque de boost ne puisse pas mettre en cache mon graphique et doive reconstruire tous les 122k bords à chaque fois (même si elle n'utilisera qu'une très sous-ensemble limité à chaque requête). Et je n'ai aucune idée du montant dépensé pour cela par rapport à la recherche du chemin le plus court.

L'un de vous utilise-t-il le pgroutage sur un ensemble de données OSM de 122k ou plus? À quelle performance dois-je m'attendre? Quels paramètres affectent le plus les performances?

mrg
la source
2
Je ne suis pas un expert en infiltration, mais pouvez-vous mettre en cache les résultats, par exemple, si vous savez qu'un sous-itinéraire commun est toujours utilisé, pouvez-vous le mettre en cache? par conséquent, vous devez faire moins de recherches? De plus, vous limitez les recherches aux artères et aux collectionneurs?
dassouki
1
J'autorise la recherche gratuite d'atm, donc je ne pense pas pouvoir assumer beaucoup pour les sous-routes. Je mets également en cache le résultat des recherches des dernières x minutes, mais cela ne m'aide pas pour les nouvelles recherches. J'ai le sentiment que A * sur cette taille devrait toujours être très rapide tant que je peux garder le graphique entier statique en mémoire. Il doit y avoir des gens qui empruntent cette voie sur tout un pays et qui savent comment améliorer les performances.
mrg
1
Une autre option serait de construire une matrice O / D (matrice origine / destination). Il s'agit d'une technique que nous utilisons dans l'ingénierie du trafic. diviser le réseau en zones, alors disons qu'une grande ville pourrait avoir 100 zones. Chaque zone aurait un centroïde factice. Connectez le centroïde à votre réseau via un lien factice. Ensuite, vous pouvez remodeler l'ensemble de votre réseau en 100 x 100 voyages (10 000 voyages au total). Lorsqu'un utilisateur effectue une recherche, le pgroutage doit trouver un itinéraire fermé au lien centroïde ou factice du côté origine et destination.
dassouki
2
N'obtenez-vous pas des résultats étranges si quelqu'un veut passer d'une zone à l'autre mais qu'il est acheminé à travers ses centroïdes? Ou l'utilisez-vous uniquement lorsque les zones sont plus éloignées? Votre solution a le plus de sens si les clients veulent passer le plus rapidement de A à B, mais dans mon cas, je dois traiter avec des clients qui veulent marcher, faire du vélo, etc. pour les loisirs et aimeraient choisir des itinéraires uniques et ne pas être obligés d'aller via l'itinéraire standard.
mrg
3
Si vous recherchez une solution multimodale (vélo, marche, transport public, voiture), vous devriez vraiment jeter un œil au site de routage multimodal TriMet de Portland, en Oregon, qui utilise OpenTripPlanner: trimet.org/news/releases/oct15-rtp. htm
RyanDalton

Réponses:

10

Face à de telles tâches, votre objectif principal est d'être rationnel. Ne changez pas les paramètres en fonction du «sentiment d'intestin». Alors que l'intestin semble fonctionner pour Hollywood, il ne l'est pas pour nous qui vivons dans le monde réel. Eh bien, du moins pas mon instinct ;-).

Vous devriez:

  1. établir une métrique utilisable et répétable (comme le temps requis par une requête de pgrouting)

  2. enregistrez les résultats des mesures dans une feuille de calcul et faites-en la moyenne (jetez le meilleur et le pire). Cela vous dira si les changements que vous apportez vont dans la bonne direction

  3. surveillez votre serveur en utilisant top et vmstat (en supposant que vous êtes sur * nix) pendant l'exécution des requêtes et recherchez des modèles significatifs: beaucoup d'io, CPU élevé, échange, etc. Si le CPU attend les E / S, essayez d'améliorer les performances du disque (cela devrait être facile, voir ci-dessous). Si le CPU est à 100% sans aucune acticité de disque significative, vous devez trouver un moyen d'améliorer la requête (cela va probablement être plus difficile).

Par souci de simplicité, je suppose que le réseau ne joue aucun rôle important ici.

Amélioration des performances de la base de données

Passez à la dernière version de Postgres. La version 9 est tellement meilleure que les versions précédentes. C'est gratuit donc vous n'avez aucune raison de ne pas le faire.

Lisez le livre que j'ai déjà recommandé ici .

Vous devriez vraiment le lire. Je crois que les chapitres pertinents pour cette affaire sont 5,6,10,11

Amélioration des performances du disque

  1. Obtenez un disque SSD et mettez toute la base de données dessus. Les performances de lecture quadrupleront très probablement et les performances d'écriture devraient également s'améliorer radicalement

  2. affecter plus de mémoire aux postgres. Idéalement, vous devriez être en mesure d'affecter suffisamment de mémoire pour que l'ensemble (ou la partie la plus chaude) puisse être mis en cache en mémoire, mais pas trop pour que l'échange se produise. L'échange est très mauvais. Ceci est couvert dans le livre cité au paragraphe précédent

  3. désactiver atime sur tous les disques (ajouter les options noatime à fstab)

Amélioration de la performance des requêtes

Utilisez les outils décrits dans le livre cité ci-dessus pour tracer vos requêtes et trouver des arrêts qui méritent d'être optimisés.

Mise à jour

Après les commentaires, j'ai regardé le code source de la procédure stockée

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

et il semble qu'une fois la requête réglée, il n'y a pas beaucoup plus de place à l'amélioration car l'algorithme s'exécute complètement en mémoire (et, malheureusement, sur un seul processeur). Je crains que votre seule solution soit de trouver un algorithme meilleur / plus rapide ou capable de fonctionner en multithread puis de l'intégrer à postgres soit en créant une bibliothèque comme pgrouting ou en utilisant un middleware pour récupérer les données (et les mettre en cache, peut-être) et alimentez-le à l'algorithme.

HTH

unicoletti
la source
J'ai lu des parties du livre que vous recommandez. Mon ensemble de données est encore assez petit pour tenir entièrement en mémoire, donc je pense que les performances du disque ne devraient pas être un goulot d'étranglement (je vérifierai mieux mes ressources lors des tests pour le confirmer). Je pense que Postgresql n'entre en jeu dans le processus de pgroutage que lorsqu'il effectue une simple sélection * dans le tableau pour alimenter la bibliothèque C Boost avec des lignes / tuples pour effectuer la recherche réelle ((quelqu'un peut-il le confirmer), donc je crains qu'il n'y en ait pas beaucoup à gagner dans Postgresql lui-même. Votre réponse semble très bonne pour les performances de Postgresql mais peut-être pas pour les performances spécifiques de pgrouting.
mrg
@mrg J'y avais pensé, mais je voulais être sûr que vous n'aviez pas laissé de côté les fruits à suspendre. En y pensant, vous êtes passé de 20ms pour 3,5k à 900ms pour 122k, ce qui, à mon humble avis, n'est pas entièrement mauvais. Bonne chance
unicoletti
Les disques SSD augmentent les performances (vitesses similaires à celles de la mise en cache)
Mapperz
D'après mon expérience, si vous utilisez pgrouting sur tous les ensembles de données (tableau), le moteur Postgres ne présente aucun grand avantage. L'index n'est même pas utilisé donc son inutile. Sur chaque requête, toute la table est chargée en mémoire. les tampons et les caches partagés n'apportaient aucun avantage en termes de performances car chaque requête charge toute la table en mémoire. Si quelqu'un a réussi à réutiliser les données chargées en mémoire pour des requêtes ultérieures, veuillez nous en informer. Seule augmentation des performances possible que je vois dans les lecteurs SDD, mais je ne l'ai jamais testée. Plus de mémoire ne permet que plus de requêtes simultanées, pas de performances.
Mario Miler
8

J'ai juste le même problème et j'allais demander sur les listes de diffusion, donc merci à tous!

J'utilise Shooting Star avec un million et demi de lignes sur la table de routage. Il faut près de dix secondes pour le calculer. Avec 20 000 lignes, cela prend près de trois secondes. J'ai besoin de Shooting Star parce que j'ai besoin des restrictions de virage.

Voici quelques idées que j'essaie de mettre en œuvre:

  • Sur le SQL où pgRouting obtient les chemins, utilisez un st_buffer pour qu'il n'obtienne pas tous les chemins, mais juste les chemins "voisins":

    sélectionnez * dans shortest_path_shooting_star ('SELECT rout. * FROM rout rout, (sélectionnez st_buffer (st_envelope (st_collect (geometry)), 4) comme géométrie dans le routage où id =' || source_ || 'ou id =' || target | | ') e WHERE rout.geometry && e.geometry', source, cible, vrai, vrai);

Il a amélioré les performances, mais si le chemin doit aller en dehors du tampon, il peut renvoyer une erreur "aucun chemin trouvé", alors ... gros tampon? plusieurs appels augmentant le tampon jusqu'à ce qu'il trouve un moyen?

  • Itinéraires rapides mis en cache

Comme l'a suggéré Dassouki, je vais mettre en cache certains itinéraires "utiles", donc si la distance est trop longue, il peut passer par ces itinéraires rapides et avoir juste à trouver le chemin pour entrer et sortir d'eux.

  • Table de partition par index gis

Mais je suppose que, si ça se remémore, ça n'a pas vraiment d'importance ... Faut le tester quand même.

Veuillez continuer à publier si vous trouvez une autre idée.

De plus, savez-vous s'il existe un pgRouting compilé pour Postgres9?

Délawen
la source
+1 Il semble y avoir ici des idées utiles et constructives. Veuillez noter que si vous souhaitez obtenir des réponses à vos questions, il est préférable de les formuler comme une nouvelle question. Notre FAQ vous indiquera comment procéder.
whuber
Délawen, j'ai aussi pensé à votre première idée (ST_Buffer) et je prévois le même problème. L'avantage pourrait toutefois être à 2 sens: le jeu de données est plus petit et donc plus rapide et, comme le traitement se fait davantage dans Postgresql, vous avez à nouveau des moyens de l'optimiser. ATM J'utilise Ubuntu 11 où postgresql 8.4 est la dernière version.
mrg
mrg, j'ai compilé pgRouting sur un Ubuntu Maverick pour PostgreSQL 9.0 sans trop de problème. Postgis pour PostgreSQL 9.0 peut être trouvé ici: ppa.launchpad.net/pi-deb/gis/ubuntu maverick / main amd64 Packages
Délawen
Je suis venu avec 2 idées. 1) Une combinaison de «routes rapides mises en cache» et «st_buffer». De cette façon, vous garantissez de trouver un itinéraire et les gens ne seront pas tous obligés de suivre le même itinéraire. 2) Utilisez uniquement postgis pour remplir un graphique statique (avec Boost (C), nx_spatial (Python), neo4j (Java), etc.) et réutilisez ce graphique pour chaque requête de recherche.
mrg
Qu'en est-il de réduire le coût (c'est-à-dire d'augmenter la préférence) pour les bords «rapides» comme les autoroutes lorsque la distance entre le début et la fin est supérieure à un seuil? Le facteur de boost pourrait également être lié à la distance: plus grand pour de plus longues distances, plus petit pour plus court.
unicoletti
5

Nous venons de créer une branche dans git pour un chemin le plus court limité en virage @ https://github.com/pgRouting/pgrouting/tree/trsp

Désolé, pas encore de documentation, mais si vous posez des questions sur la liste pgRouting, je traîne et je vous répondrai. Ce code fonctionne beaucoup plus rapidement que l'étoile filante et est basé sur l'algorithme de Dijkstra.

-Steve

Stephen Woodbridge
la source
0

J'ai une table de routage source qui contient ~ 1200000 bords. Sur mon i7 avec SSD, il faut 12 secondes pour créer un itinéraire. Mon idée pour augmenter les performances est de diviser la table de bord en plusieurs tables de niveau de zoom. Je veux dire le niveau identique aux tuiles Google. Au 8e niveau de zoom, par exemple, j'ai 88 tableaux. Chaque table contient un sous-ensemble de routes et leurs zones se chevauchent afin de calculer un itinéraire entre deux points qui ne se trouvent pas à une distance de 290 km l'un de l'autre prend 2 secondes. Au 9ème niveau, le temps de calcul tombe à 0,25 s et nous avons 352 tables. La recréation de tous les graphiques dans le cas où nous éditons des routes ne prend pas plus d'une heure. La manière radicale d'augmenter la vitesse de routage est d'utiliser l'algorithme Floyd-Warshall. Mais personne ne sait combien il faut pour calculer la matrice précédente sur autant d'arêtes.

Vadym
la source