Korzystam z pgroutinga w bazie danych Postgis utworzonej przez osm2pgrouting. Działa bardzo dobrze na ograniczonym zbiorze danych (3,5 tys. Sposobów, wszystkie najkrótsze ścieżki wyszukiwania A * <20 ms).
Ponieważ jednak zaimportowałem z europy większą ramkę ograniczającą (122 tys. Sposobów), wydajność znacznie spadła (najkrótsza ścieżka kosztuje około 900 ms).
Myślę, że przy użyciu A * większość tych krawędzi nigdy nie będzie odwiedzana, ponieważ są one na uboczu.
Co zrobiłem do tej pory, próbując poprawić prędkość:
- Umieść indeks na kolumnie geometrii (brak zauważalnego efektu)
- Zwiększono moją pamięć z 8 GB do 16 GB
- Zmień ustawienia pamięci postgresql (Shared_buffers, Efektywny_cache_size) z (128 MB, 128 MB) na (1 GB, 2 GB) (brak zauważalnego efektu)
Mam wrażenie, że większość pracy jest wykonywana w bibliotece C Boost, gdzie tworzony jest wykres, więc optymalizacja postgresql nie da mi dużo lepszych wyników. Ponieważ dokonuję drobnych zmian w zestawie wierszy, wybieram A * przy każdym wyszukiwaniu, trochę boję się, że biblioteka doładowań nie może buforować mojego wykresu i za każdym razem musi odbudować wszystkie 122k krawędzie (mimo że użyje tylko bardzo ograniczony podzbiór każdego zapytania). I nie mam pojęcia, ile wydaje się na robienie tego w porównaniu z faktycznym najkrótszą ścieżką.
Czy ktoś z was korzysta z pgroutinga w zestawie danych OSM 122k lub większym? Jakiej wydajności powinienem się spodziewać? Jakie ustawienia najbardziej wpływają na wydajność?
Odpowiedzi:
W obliczu takich zadań twoim głównym celem jest racjonalność. Nie zmieniaj parametrów opartych na „przeczuciu”. Chociaż wydaje się, że jelito działa w Hollywood, nie żyje w prawdziwym świecie. Cóż, przynajmniej nie moje jelita ;-).
Powinieneś:
ustanowić użyteczną i powtarzalną metrykę (np. czas wymagany przez zapytanie dotyczące planowania)
zapisz wyniki danych w arkuszu kalkulacyjnym i uśrednij je (odrzuć najlepsze i najgorsze). Dzięki temu dowiesz się, czy wprowadzane zmiany idą w dobrym kierunku
monitoruj swój serwer za pomocą top i vmstat (zakładając, że jesteś na * nix) podczas działania zapytań i szukaj znaczących wzorców: dużo io, wysokie cpu, zamiana itp. Jeśli procesor czeka na operacje we / wy, spróbuj poprawić wydajność dysku (powinno to być łatwe, patrz poniżej). Jeśli zamiast tego procesor jest w 100% pozbawiony znaczącej aktywności dysku, musisz znaleźć sposób na poprawienie zapytania (prawdopodobnie będzie to trudniejsze).
Dla uproszczenia zakładam, że sieć nie odgrywa tutaj znaczącej roli.
Poprawa wydajności bazy danych
Uaktualnij do najnowszej wersji Postgres. Wersja 9 jest o wiele lepsza niż poprzednie wersje. Jest bezpłatny, więc nie masz powodu, żeby nie nie.
Przeczytaj książkę polecaną już tutaj .
Naprawdę powinieneś to przeczytać. Uważam, że odpowiednie rozdziały dla tej sprawy to 5,6,10,11
Poprawa wydajności dysku
Pobierz dysk SSD i umieść na nim całą bazę danych. Wydajność odczytu najprawdopodobniej czterokrotnie, a wydajność zapisu powinna się radykalnie poprawić
przypisz więcej pamięci postgresowi. Idealnie powinieneś być w stanie przypisać wystarczającą ilość pamięci, aby cała (lub najgorętsza część) mogła być buforowana w pamięci, ale nie za bardzo, aby nastąpiła zamiana. Zamiana jest bardzo zła. Jest to omówione w książce cytowanej w poprzednim akapicie
wyłącz atime na wszystkich dyskach (dodaj opcje noatime do fstab)
Poprawa wydajności zapytania
Skorzystaj z narzędzi opisanych w cytowanej wyżej książce, aby prześledzić swoje zapytanie / zapytania i znaleźć przystanki, które warto zoptymalizować.
Aktualizacja
Po komentarzach spojrzałem na kod źródłowy procedury składowanej
https://github.com/pgRouting/pgrouting/blob/master/core/src/astar.c
i wydaje się, że po dostrojeniu zapytania nie ma już dużo miejsca na ulepszenia, ponieważ algorytm działa całkowicie w pamięci (i, niestety, tylko na jednej jednostce centralnej). Obawiam się, że twoim jedynym rozwiązaniem jest znalezienie lepszego / szybszego algorytmu lub takiego, który może uruchamiać wielowątkowość, a następnie zintegrować go z postgres, tworząc bibliotekę taką jak pgrouting lub używając oprogramowania pośredniego do pobierania danych (i buforowania, być może) i podaj go do algorytmu.
HTH
źródło
Mam dokładnie ten sam problem i chciałem zapytać na listach mailowych, więc dziękuję wszystkim!
Używam Shooting Star z półtora miliona rzędów na stole do wyznaczania tras. Obliczenie zajmuje prawie dziesięć sekund. Z 20k rzędami zajmuje prawie trzy sekundy. Potrzebuję Shooting Star, ponieważ potrzebuję ograniczeń skrętu.
Oto kilka pomysłów, które próbuję wdrożyć:
Na SQL, gdzie pgRouting zdobywa sposoby, użyj st_buffer, aby nie uzyskać wszystkich sposobów, ale tylko „pobliskie” sposoby:
wybierz * z shortest_path_shooting_star ('SELECT rout. * FROM routing rout, (wybierz st_buffer (st_envelope (st_collect (geometria)), 4) jako geometrię z trasy gdzie id =' || source_ || 'lub id =' || target | | ') e GDZIE rout.geometry && e.geometry', źródło, cel, prawda, prawda);
Poprawiło to wydajność, ale jeśli droga musi wyjść poza bufor, może zwrócić błąd „nie znaleziono ścieżki”, więc ... duży bufor? kilka połączeń zwiększających bufor, aż znajdzie sposób?
Jak zasugerował dassouki, zbuforuję niektóre „przydatne” trasy, więc jeśli odległość jest zbyt długa, może przejść przez te szybkie trasy i po prostu znaleźć drogę do nich.
Ale przypuszczam, że jeśli chodzi o pamięć, to tak naprawdę nie ma znaczenia ... W każdym razie powinien to przetestować.
Proszę pisać dalej, jeśli znajdziesz inny pomysł.
Czy wiesz też, czy istnieje jakiś skompilowany pgRouting dla Postgres9?
źródło
Właśnie utworzyliśmy oddział w git dla najkrótszej ścieżki o ograniczonym zakręcie @ https://github.com/pgRouting/pgrouting/tree/trsp
Niestety nie ma jeszcze dokumentacji, ale jeśli zadajesz pytania na liście pgRouting, spotykam się tam i odpowiadam. Ten kod działa znacznie szybciej niż spadająca gwiazda i jest oparty na algorytmie Dijkstry.
-Steve
źródło
Mam źródłową tabelę tras, która zawiera ~ 1200000 krawędzi. Na moim i7 z dyskiem SSD utworzenie trasy zajmuje 12 sekund. Moim pomysłem na zwiększenie wydajności jest podzielenie tabeli krawędzi na kilka tabel poziomu powiększenia. Mam na myśli poziom identyczny z kafelkami Google. Na przykład na 8. poziomie powiększenia mam 88 tabel. Każda tabela zawiera podzbiór dróg, a ich obszary nakładają się na siebie, aby obliczyć trasę między dwoma punktami, które leżą nie dalej niż 290 km od siebie, zajmuje 2 sekundy. Na 9 poziomie czas obliczeń spada do 0,25 sekundy i mamy 352 tabele. Odtwarzanie wszystkich wykresów na wypadek, gdybyśmy edytowali drogi, zajmuje nie więcej niż godzinę. Radykalnym sposobem na zwiększenie prędkości routingu jest użycie algorytmu Floyd-Warshall. Ale nikt nie wie, ile kosztuje obliczenie macierzy poprzednika na tak wielu krawędziach.
źródło