Ich verwende pgrouting für eine Postgis-Datenbank, die mit osm2pgrouting erstellt wurde. Die Leistung ist bei einem begrenzten Datensatz sehr gut (3,5 k-Wege, alle A * -Suche mit kürzestem Pfad <20 ms).
Da ich jedoch eine größere Bounding Box (122k-Wege) aus europe.osm importiert habe, ging die Leistung stark zurück (ein kürzester Pfad kostet etwa 900 ms).
Ich würde denken, dass mit A * die meisten dieser Kanten nie besucht werden, da sie aus dem Weg sind.
Was ich bisher getan habe, um die Geschwindigkeit zu verbessern:
- Fügen Sie der Geometriespalte einen Index hinzu (kein erkennbarer Effekt)
- Mein Speicher wurde von 8 GB auf 16 GB erhöht
- Ändern Sie die Postgresql-Speichereinstellungen (shared_buffers, effective_cache_size) von (128 MB, 128 MB) auf (1 GB, 2 GB) (kein erkennbarer Effekt).
Ich habe das Gefühl, dass die meiste Arbeit in der C-Boost-Bibliothek ausgeführt wird, in der das Diagramm erstellt wird, sodass die Optimierung von postgresql keine besseren Ergebnisse liefert. Da ich geringfügige Änderungen an der Reihe von Zeilen vornehme, die ich für A * bei jeder Suche auswähle, habe ich ein wenig Angst, dass die Boost-Bibliothek mein Diagramm nicht zwischenspeichern kann und jedes Mal alle 122k-Kanten neu erstellen muss (auch wenn es nur sehr viele verwendet begrenzte Teilmenge jeder Abfrage). Und ich habe keine Ahnung, wie viel dafür ausgegeben wird, verglichen mit der tatsächlichen Suche nach kürzesten Wegen.
Verwendet einer von Ihnen Pgrouting für ein OSM-Dataset mit 122 KB oder mehr? Mit welcher Leistung sollte ich rechnen? Welche Einstellungen wirken sich am meisten auf die Leistung aus?
Antworten:
Wenn Sie mit solchen Aufgaben konfrontiert werden, ist es Ihr Hauptziel, rational zu sein. Ändern Sie die Parameter nicht nach dem Bauchgefühl. Während der Darm für Hollywood zu funktionieren scheint, gilt dies nicht für uns, die wir in der realen Welt leben. Na jedenfalls nicht mein Bauch ;-).
Du solltest:
Erstellen Sie eine verwendbare und wiederholbare Metrik (wie die Zeit, die eine Pgrouting-Abfrage benötigt).
Speichern Sie metrische Ergebnisse in einer Tabelle und mitteln Sie sie (am besten und am schlechtesten verwerfen). Hier erfahren Sie, ob die von Ihnen vorgenommenen Änderungen in die richtige Richtung gehen
Überwachen Sie Ihren Server mit top und vmstat (vorausgesetzt, Sie sind auf * nix), während Abfragen ausgeführt werden, und suchen Sie nach signifikanten Mustern: viele io, hohe CPU, Swap usw. Wenn die CPU auf i / o wartet, versuchen Sie, sich zu verbessern Festplattenleistung (dies sollte einfach sein, siehe unten). Wenn die CPU stattdessen zu 100% ohne nennenswerte Festplattenaktivität ist, müssen Sie einen Weg finden, um die Abfrage zu verbessern (dies wird wahrscheinlich schwieriger sein).
Der Einfachheit halber gehe ich davon aus, dass das Netzwerk hier keine wesentliche Rolle spielt.
Verbesserung der Datenbankleistung
Aktualisieren Sie auf die neueste Postgres-Version. Version 9 ist so viel besser als frühere Versionen. Es ist kostenlos, also hast du keinen Grund, es nicht zu tun.
Lesen Sie das Buch, das ich bereits hier empfohlen habe .
Du solltest es wirklich lesen. Ich glaube, die relevanten Kapitel für diesen Fall sind 5, 6, 10, 11
Verbesserung der Festplattenleistung
Holen Sie sich ein SSD-Laufwerk und legen Sie die gesamte Datenbank darauf. Die Leseleistung wird sich höchstwahrscheinlich vervierfachen, und auch die Schreibleistung dürfte sich radikal verbessern
Weisen Sie postgres mehr Speicher zu. Im Idealfall sollten Sie in der Lage sein, genügend Arbeitsspeicher zuzuweisen, damit das Ganze (oder der heißeste Teil) im Arbeitsspeicher zwischengespeichert werden kann, jedoch nicht zu viel, damit ein Austausch stattfindet. Tauschen ist sehr schlecht. Dies wird in dem im vorherigen Absatz zitierten Buch behandelt
deaktiviere atime auf allen Festplatten (füge die noatime Optionen zu fstab hinzu)
Verbesserung der Abfrageleistung
Verwenden Sie die in dem oben genannten Buch beschriebenen Tools, um Ihre Abfragen zu verfolgen und Stopps zu finden, die es wert sind, optimiert zu werden.
Aktualisieren
Nach den Kommentaren habe ich mir den Quellcode für die gespeicherte Prozedur angesehen
https://github.com/pgRouting/pgrouting/blob/master/core/src/astar.c
und es scheint, dass nach der Optimierung der Abfrage nicht mehr viel Raum für Verbesserungen besteht, da der Algorithmus vollständig im Speicher ausgeführt wird (und leider nur auf einer CPU). Ich fürchte, Ihre einzige Lösung besteht darin, einen besseren / schnelleren Algorithmus zu finden oder einen, der Multithreading-fähig ist, und ihn dann in Postgres zu integrieren, indem Sie entweder eine Bibliothek wie pgrouting erstellen oder Middleware zum Abrufen der Daten verwenden (und sie möglicherweise zwischenspeichern) und füttere es dem Algorithmus.
HTH
quelle
Ich habe genau das gleiche Problem und wollte gerade auf Mailinglisten fragen, also danke an alle!
ich benutze Shooting Star mit eineinhalb Millionen Zeilen auf dem Routing-Tisch. Die Berechnung dauert fast zehn Sekunden. Bei 20.000 Zeilen dauert es fast drei Sekunden. Ich brauche Shooting Star, weil ich die Abbiegebeschränkungen brauche.
Hier sind einige Ideen, die ich umsetzen möchte:
In der SQL, in der pgRouting die Möglichkeiten hat, Verwenden einen st_buffer, damit nicht alle Wege ermittelt werden, sondern nur die "nahe" gelegenen Wege:
Wählen Sie * aus dem kürzesten_Pfad_Schießstern ('SELECT rout. * FROM routing rout.' | ') e WHERE rout.geometry && e.geometry', Quelle, Ziel, wahr, wahr);
Es hat die Leistung verbessert, aber wenn der Weg außerhalb des Puffers gehen muss, kann es einen Fehler "Kein Pfad gefunden" zurückgeben, also ... großer Puffer? mehrere Aufrufe den Puffer vergrößern, bis es einen Weg findet?
Wie Dassouki vorgeschlagen hat, werde ich einige "nützliche" Routen zwischenspeichern. Wenn die Entfernung also zu lang ist, kann es diese schnellen Routen durchlaufen und muss nur den Weg hinein und heraus finden.
Aber ich nehme an, wenn es in Erinnerung bleibt, spielt es keine Rolle ... Sollte es trotzdem testen.
Bitte posten Sie weiter, wenn Sie eine andere Idee finden.
Weißt du auch, ob es ein kompiliertes pgRouting für Postgres9 gibt?
quelle
Wir haben soeben eine Verzweigung in Git für einen kurvenbeschränkten kürzesten Pfad erstellt: https://github.com/pgRouting/pgrouting/tree/trsp
Entschuldigung, noch keine Dokumentation, aber wenn du Fragen zur pgRouting-Liste stellst, hänge ich da rum und werde antworten. Dieser Code läuft viel schneller als Shooting Star und basiert auf dem Dijkstra-Algorithmus.
-Steve
quelle
Ich habe eine Quellroutentabelle, die ~ 1200000 Kanten enthält. Auf meinem i7 mit SSD dauert es 12 Sekunden, bis eine Route erstellt wurde. Meine Idee, die Leistung zu steigern, ist die Aufteilung der Kantentabelle in mehrere Zoomebenentabellen. Ich meine den Level, der mit Google Tiles identisch ist. Bei der achten Zoomstufe habe ich zum Beispiel 88 Tabellen. Jede Tabelle enthält eine Untergruppe von Straßen und deren Flächen, die sich überlappen, um eine Route zwischen zwei Punkten zu berechnen, die nicht weiter als 290 km voneinander entfernt liegen. Dies dauert 2 Sekunden. Bei der 9. Stufe sinkt die Berechnungszeit auf 0,25 Sekunden und wir haben 352 Tabellen. Die Neuerstellung aller Diagramme für den Fall, dass wir Straßen bearbeiten, dauert nicht länger als eine Stunde. Der radikale Weg, die Routing-Geschwindigkeit zu erhöhen, ist die Verwendung des Floyd-Warshall-Algorithmus. Aber niemand weiß, wie viel es kostet, die Vorgängermatrix an so vielen Kanten zu berechnen.
quelle