Jak mogę zoptymalizować trening dla prędkości?

22

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ść?

— mrg
źródło

2

Nie jestem ekspertem od planowania, ale czy możesz buforować wyniki, na przykład, jeśli wiesz, że zawsze używana jest wspólna trasa podrzędna, czy możesz ją wstępnie buforować? dlatego musisz wykonać mniej wyszukiwań? Ponadto, czy ograniczysz wyszukiwanie do artykułów i kolektorów?

— dassouki

1

Pozwalam na darmowe wyszukiwanie bankomatu, więc nie sądzę, że mogę dużo założyć na trasy podrzędne. Również buforuję wyniki wyszukiwania z ostatnich x minut, ale to nie pomaga mi w przypadku nowych wyszukiwań. Mam wrażenie, że A * w tym rozmiarze powinien być naprawdę szybki, o ile mogę zachować cały wykres w pamięci. Muszą być ludzie, którzy prowadzą tę trasę po całym kraju, którzy wiedzą, jak poprawić wydajność.

— mrg

1

Inną opcją byłoby zbudowanie macierzy O / D (macierzy źródłowej / docelowej). Jest to technika, której używamy w inżynierii ruchu. podziel sieć na strefy, więc powiedzmy, że duże miasto może mieć 100 stref. Każda strefa miałaby atrapę centroida. Połącz centroid z siecią za pomocą fikcyjnego łącza. Następnie możesz przebudować całą sieć na 100 x 100 podróży (łącznie 10 000 podróży). Gdy użytkownik przeprowadza wyszukiwanie, planowanie musi znaleźć trasę zamkniętą do linku środkowego lub zastępczego po stronie początkowej i docelowej.

— dassouki

2

Czy nie dostajesz dziwnych rezultatów, jeśli ktoś chce przejść z jednej strefy do następnej, ale zostaje poprowadzony przez swoje centroidy? A może używasz tego tylko wtedy, gdy strefy są dalej od siebie? Twoje rozwiązanie jest najbardziej sensowne, jeśli klienci chcą jak najszybciej dostać się z punktu A do punktu B, ale w moim przypadku mam do czynienia z klientami, którzy chcą chodzić, jeździć rowerem itp. W celach rekreacyjnych i chcą wybrać unikalne trasy i nie muszą iść standardową trasą.

— mrg

3

Jeśli szukasz rozwiązania multimodalnego (rower, spacer, transport publiczny, jazda), naprawdę powinieneś rzucić okiem na multimodalną stronę routingu TriMet w Portland w Oregonie, która korzysta z OpenTripPlanner: trimet.org/news/releases/oct15-rtp. htm

— RyanDalton

10

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

— unicoletti
źródło

Przeczytałem części książki, które polecasz. Mój zestaw danych jest wciąż wystarczająco mały, aby zmieścić się całkowicie w pamięci, więc myślę, że wydajność dysku nie powinna być wąskim gardłem (lepiej sprawdzę zasoby podczas testowania, aby to potwierdzić). Myślę, że Postgresql wchodzi w grę tylko wtedy, gdy wykonuje proste wybranie * z tabeli, aby zasilić bibliotekę C Boost wierszem / krotkami w celu przeprowadzenia prawdziwego wyszukiwania ((czy ktoś może to potwierdzić), więc obawiam się, że nie ma wiele do zdobycia w samym Postgresql. Twoja odpowiedź wydaje się bardzo dobra w odniesieniu do wydajności Postgresql, ale być może nie w przypadku planowania konkretnej wydajności

— mrg

@mrg Właściwie to myślałem, ale chciałem mieć pewność, że nie pominąłeś nisko wiszących owoców. Myśląc o tym, poszedłeś z 20ms dla 3,5k do 900ms dla 122k, co nie jest całkiem złe. Powodzenia

— unicoletti

Dyski SSD zwiększają wydajność (podobne prędkości do buforowania)

— Mapperz

Z mojego doświadczenia wynika, że korzystanie z pgroutinga we wszystkich zestawach danych (tabelach) nie daje wielkich korzyści z silnika Postgres. Indeks nie jest nawet używany, więc jest bezużyteczny. Przy każdym zapytaniu cała tabela jest ładowana do pamięci. współużytkowane bufory i pamięci podręczne również nie przyniosły żadnej poprawy wydajności, ponieważ każde zapytanie ładuje całą tabelę do pamięci. Jeśli komuś uda się ponownie wykorzystać załadowane dane w pamięci do kolejnych zapytań, powiedz nam. Tylko możliwy wzrost wydajności widzę w dyskach SDD, ale nigdy go nie testowałem. Więcej pamięci pozwala tylko na więcej równoczesnych zapytań, a nie na wydajność.

— Mario Miler,

8

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?

Szybkie trasy buforowane

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.

Tabela podziału według indeksu gis

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?

— Délawen
źródło

+1 Wygląda na to, że są tu przydatne i konstruktywne pomysły. Pamiętaj, że jeśli chcesz uzyskać odpowiedź na swoje pytania, najlepiej sformułować je jako nowe pytanie. Nasze FAQ powie Ci, jak postępować.

— whuber

Délawen, myślałem również o twoim pierwszym pomyśle (ST_Buffer) i przewiduję ten sam problem. Zaleta może być jednak dwukierunkowa: zestaw danych jest mniejszy, a przez to szybszy, a ponieważ w Postgresql odbywa się więcej przetwarzania, można ponownie zoptymalizować go. Korzystam z Ubuntu 11, gdzie postgresql 8.4 to najnowsza wersja.

— mrg

mrg, skompilowałem pgRouting na Ubuntu Maverick dla PostgreSQL 9.0 bez większego problemu. Postgis dla PostgreSQL 9.0 można znaleźć tutaj: ppa.launchpad.net/pi-deb/gis/ubuntu maverick / main amd64 Pakiety

— Délawen 16.11.11

Wymyśliłem 2 pomysły. 1) Kombinacja „szybkich buforowanych tras” i „st_buffer”. W ten sposób gwarantujesz znalezienie trasy, a ludzie nie zostaną zmuszeni do przejścia tą samą trasą. 2) Używaj postgis tylko do wypełniania statycznego wykresu (z Boost (C), nx_spatial (Python), neo4j (Java) itp.) I ponownie używaj tego wykresu dla każdego zapytania.

— mrg

Co powiesz na obniżenie kosztów (tj. Zwiększenie preferencji) dla „szybkich” krawędzi, takich jak autostrady, gdy odległość między początkiem a końcem jest większa niż próg? Współczynnik doładowania można również powiązać z odległością: większy dla dłuższych odległości, mniejszy dla krótszych.

— unicoletti

5

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

— Stephen Woodbridge
źródło

0

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.

— Vadym
źródło