Wie kann ich das Verfugen auf Geschwindigkeit optimieren?

22

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?

mrg
quelle
2
Ich bin kein Experte für Verfugung, aber können Sie die Ergebnisse zwischenspeichern, wenn Sie beispielsweise wissen, dass immer eine gemeinsame Unterroute verwendet wird, können Sie sie vorab zwischenspeichern? Müssen Sie daher weniger suchen? Außerdem können Sie die Suche auf Arterien und Sammler beschränken.
Dassouki
1
Ich erlaube freie Suche atm, also denke ich nicht, dass ich viel für Nebenwege annehmen kann. Ich speichere auch die Suchergebnisse der letzten x Minuten, aber das hilft mir nicht bei neuen Suchen. Ich habe das Gefühl, dass A * auf dieser Größe immer noch sehr schnell sein sollte, solange ich den gesamten Graphen statisch im Gedächtnis behalten kann. Es muss Menschen geben, die auf diese Weise ein ganzes Land bereisen und wissen, wie man die Leistung verbessert.
15.
1
Eine andere Möglichkeit wäre, eine O / D-Matrix (Ursprungs- / Zielmatrix) zu erstellen. Dies ist eine Technik, die wir in der Verkehrstechnik anwenden. Teilen Sie das Netzwerk in Zonen auf. Nehmen wir also an, eine große Stadt könnte 100 Zonen haben. Jede Zone hätte einen Dummy-Schwerpunkt. Verbinden Sie den Schwerpunkt über einen Dummy-Link mit Ihrem Netzwerk. Dann können Sie Ihr gesamtes Netzwerk in 100 x 100 Fahrten (insgesamt 10.000 Fahrten) umgestalten. Wenn ein Benutzer eine Suche durchführt, muss pgrouting eine Route finden, die sich auf der Ursprungs- und Zielseite in der Nähe des Schwerpunkts oder des Dummy-Links befindet.
Dassouki
2
Erhalten Sie keine seltsamen Ergebnisse, wenn jemand von einer Zone zur nächsten will, aber durch seine Zentroide geleitet wird? Oder verwenden Sie dies nur, wenn die Zonen weiter voneinander entfernt sind? Ihre Lösung ist am sinnvollsten, wenn Kunden am schnellsten von A nach B gelangen möchten, aber in meinem Fall muss ich mich mit Kunden befassen, die in der Freizeit laufen, radeln usw. möchten und eindeutige Routen auswählen möchten, ohne gezwungen zu sein, zu gehen über die Standardroute.
15.
3
Wenn Sie nach einer multimodalen Lösung suchen (Fahrrad, Fußweg, öffentlicher Verkehr, Autofahrt), sollten Sie unbedingt Portland, die multimodale Routing-Site von Oregon, besuchen, die OpenTripPlanner verwendet: trimet.org/news/releases/oct15-rtp. htm
RyanDalton

Antworten:

10

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:

  1. Erstellen Sie eine verwendbare und wiederholbare Metrik (wie die Zeit, die eine Pgrouting-Abfrage benötigt).

  2. 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

  3. Ü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

  1. 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

  2. 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

  3. 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

unicoletti
quelle
Ich habe Teile des von Ihnen empfohlenen Buches gelesen. Mein Dataset ist immer noch klein genug, um vollständig in den Arbeitsspeicher zu passen, sodass ich der Meinung bin, dass die Festplattenleistung kein Engpass sein sollte (ich überprüfe meine Ressourcen beim Testen, um dies zu bestätigen). Ich denke, dass Postgresql nur dann im Pgrouting-Prozess zum Tragen kommt, wenn es eine einfache Auswahl * aus der Tabelle vornimmt, um die C-Boost-Bibliothek mit Zeilen / Tupeln zu füttern, um die eigentliche Suche durchzuführen (kann jemand bestätigen), also fürchte ich, dass es keine gibt viel zu gewinnen in Postgresql selbst. Ihre Antwort scheint sehr gut für Postgresql-Leistung, aber vielleicht nicht so für das Verfassen bestimmter Leistung.
Mrg
@mrg Daran hatte ich eigentlich gedacht, aber ich wollte sichergehen, dass du die tief hängenden Früchte nicht ausgelassen hast. Wenn Sie daran denken, sind Sie von 20ms für 3.5k auf 900ms für 122k gegangen, was imho nicht ganz schlecht ist. Viel Glück
unicoletti
Solid-State-Laufwerke steigern die Leistung (ähnlich wie Caching)
Mapperz
Meiner Erfahrung nach bietet die Postgres-Engine keinen großen Vorteil, wenn die Pgrouting-Funktion für alle Datensätze (Tabellen) verwendet wird. Der Index wird nicht einmal verwendet, daher ist er nutzlos. Bei jeder Abfrage wird die gesamte Tabelle in den Speicher geladen. Freigegebene Puffer und Caches haben ebenfalls keinen Leistungsvorteil gebracht, da bei jeder Abfrage die gesamte Tabelle in den Arbeitsspeicher geladen wird. Wenn es jemandem gelungen ist, geladene Daten im Speicher für spätere Abfragen wiederzuverwenden, teilen Sie uns dies bitte mit. Nur eine mögliche Leistungssteigerung sehe ich bei SDD-Laufwerken, die ich aber noch nie getestet habe. Mehr Speicher ermöglicht nur mehr gleichzeitige Abfragen, nicht die Leistung.
Mario Miler
8

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?

  • Schnelle Routen zwischengespeichert

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.

  • Partitionstabelle nach gis-Index

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?

Délawen
quelle
+1 Hier scheint es einige nützliche und konstruktive Ideen zu geben. Bitte beachten Sie: Wenn Sie Ihre Fragen beantworten möchten, formulieren Sie sie am besten als neue Frage. In unseren FAQ erfahren Sie, wie Sie vorgehen müssen.
whuber
Délawen, ich habe auch über Ihre erste Idee (ST_Buffer) nachgedacht und das gleiche Problem vorhergesehen. Der Vorteil könnte jedoch in zwei Richtungen liegen: Der Datensatz ist kleiner und damit schneller, und da ein Großteil der Verarbeitung in Postgresql ausgeführt wird, haben Sie erneut Möglichkeiten, ihn zu optimieren. Atm Ich benutze Ubuntu 11, wobei Postgresql 8.4 die neueste Version ist.
16.
mrg, ich habe pgRouting auf einem Ubuntu Maverick für PostgreSQL 9.0 ohne viel problem kompiliert. Postgis für PostgreSQL 9.0 finden Sie hier: ppa.launchpad.net/pi-deb/gis/ubuntu maverick / main amd64 Packages
Délawen
Ich hatte 2 Ideen. 1) Eine Kombination aus zwischengespeicherten 'schnellen Routen' und 'st_buffer'. Auf diese Weise finden Sie garantiert eine Route und es werden nicht alle Personen auf die gleiche Route gezwungen. 2) Füllen Sie ein statisches Diagramm nur mit postgis (entweder mit Boost (C), nx_spatial (Python), neo4j (Java) usw.) und verwenden Sie dieses Diagramm für jede Suchabfrage erneut.
16.
Was ist mit der Senkung der Kosten (dh Erhöhung der Präferenz) für "schnelle" Kanten wie Autobahnen, wenn der Abstand zwischen Start und Ende größer als ein Schwellenwert ist? Der Boost-Faktor könnte auch mit der Entfernung zusammenhängen: Größer für längere Entfernungen, kleiner für kürzere.
unicoletti
5

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

Stephen Woodbridge
quelle
0

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.

Vadym
quelle