Bagaimana saya bisa mengoptimalkan pgrouting untuk kecepatan?

22

Saya menggunakan pgrouting pada database postgis yang dibuat melalui osm2pgrouting. Ia bekerja sangat baik pada dataset terbatas (3.5k cara, semua jalur terpendek A * pencarian <20 ms).

Namun karena saya telah mengimpor kotak pembatas yang lebih besar (cara 122k) dari europe.osm kinerjanya turun banyak (biaya jalur terpendek sekitar 900 ms).

Saya akan berpikir bahwa menggunakan A * sebagian besar tepi tidak akan pernah dikunjungi karena mereka keluar dari jalan.

Apa yang telah saya lakukan sejauh ini dalam upaya meningkatkan kecepatan:

  • Letakkan indeks pada kolom geometri (tidak ada efek yang terlihat)
  • Meningkatkan memori saya dari 8GB menjadi 16GB
  • Ubah pengaturan memori postgresql (shared_buffers, efektif_cache_size) dari (128MB, 128MB) menjadi (1GB, 2GB) (tidak ada efek yang terlihat)

Saya merasa bahwa sebagian besar pekerjaan sedang dilakukan di perpustakaan C Boost di mana grafik sedang dibuat sehingga mengoptimalkan postgresql tidak akan memberi saya hasil yang lebih baik. Saat saya melakukan perubahan kecil pada set baris, saya memilih A * untuk setiap pencarian. Saya agak takut bahwa boost library tidak dapat men-cache grafik saya dan harus membangun kembali semua tepi 122k setiap kali (walaupun itu hanya akan menggunakan yang sangat subset terbatas setiap kueri). Dan saya tidak tahu berapa banyak yang dihabiskan untuk melakukan itu dibandingkan dengan pencarian jalur terpendek yang sebenarnya.

Apakah ada di antara Anda yang menggunakan pgrouting pada 122k atau lebih banyak set data OSM? Kinerja apa yang harus saya harapkan? Pengaturan apa yang paling memengaruhi kinerja?

mrg
sumber
2
Saya bukan ahli pgrouting, tetapi dapatkah Anda menyimpan hasil, misalnya, jika Anda tahu sub rute umum selalu digunakan, dapatkah Anda melakukannya sebelumnya? karena itu, Anda harus melakukan lebih sedikit pencarian? Juga, apakah Anda membatasi pencarian untuk Arteri dan kolektor?
dassouki
1
Saya mengizinkan atm pencarian gratis, jadi saya tidak berpikir saya bisa berasumsi banyak untuk sub rute. Saya juga sedang menyimpan hasil pencarian dari x menit terakhir, tetapi itu tidak membantu saya untuk pencarian baru. Saya merasa bahwa A * pada ukuran ini harus tetap sangat cepat selama saya dapat menjaga seluruh grafik statis dalam memori. Pasti ada orang yang merutekan cara ini di seluruh negara yang tahu cara meningkatkan kinerja.
mrg
1
Pilihan lain adalah membangun matriks O / D (matriks asal / tujuan). Ini adalah teknik yang kami gunakan dalam rekayasa lalu lintas. membagi jaringan menjadi zona, jadi katakanlah sebuah kota besar dapat memiliki 100 zona. Setiap zona akan memiliki droid centroid. Hubungkan centroid ke jaringan Anda melalui tautan dummy. Kemudian Anda dapat mengubah seluruh jaringan Anda menjadi 100 x 100 perjalanan (total 10.000 perjalanan). Saat pengguna melakukan pencarian, pgrouting harus menemukan rute yang ditutup ke tautan centroid atau dummy di sisi asal dan tujuan.
dassouki
2
Apakah Anda tidak mendapatkan hasil yang aneh jika seseorang ingin pergi dari 1 zona ke yang lain tetapi mereka bisa dialihkan melalui centroid mereka? Atau apakah Anda hanya menggunakan ini ketika zona terpisah lebih jauh? Solusi Anda paling masuk akal jika pelanggan ingin mendapatkan yang tercepat dari A ke B, tetapi dalam kasus saya, saya harus berurusan dengan pelanggan yang ingin berjalan, bersepeda, dll untuk bersantai dan ingin memilih rute yang unik dan tidak dipaksa untuk pergi melalui rute standar.
mrg
3
Jika Anda mencari solusi multimoda (sepeda, jalan kaki, angkutan umum, mengemudi), Anda harus benar-benar melihat Portland, situs perutean multimodal TriMet Oregon, yang menggunakan OpenTripPlanner: trimet.org/news/releases/oct15-rtp. htm
RyanDalton

Jawaban:

10

Ketika dihadapkan dengan tugas-tugas seperti ini, tujuan utama Anda adalah bersikap rasional. Jangan mengubah params berdasarkan 'firasat'. Sementara usus tampaknya bekerja untuk Hollywood, itu tidak untuk kita yang hidup di dunia nyata. Yah, setidaknya bukan nyali saya ;-).

Anda harus:

  1. menetapkan metrik yang dapat digunakan dan berulang (seperti waktu yang dibutuhkan oleh kueri pgrouting)

  2. menyimpan hasil metrik dalam spreadsheet dan rata-rata hasilnya (buang yang terbaik dan terburuk). Ini akan memberi tahu Anda jika perubahan yang Anda lakukan mengarah ke arah yang benar

  3. monitor server Anda menggunakan top dan vmstat (dengan asumsi Anda berada di * nix) ketika kueri sedang berjalan dan mencari pola yang signifikan: banyak io, cpu tinggi, swapping, dll. Jika cpu sedang menunggu i / o maka cobalah untuk meningkatkan kinerja disk (ini seharusnya mudah, lihat di bawah). Jika CPU 100% tanpa aktivitas disk yang signifikan, Anda harus menemukan cara untuk meningkatkan kueri (ini mungkin akan lebih sulit).

Demi kesederhanaan saya menganggap jaringan tidak memainkan peran penting di sini.

Meningkatkan kinerja basis data

Tingkatkan ke versi Postgres terbaru. Versi 9 jauh lebih baik daripada versi sebelumnya. Ini gratis sehingga Anda tidak punya alasan untuk tidak melakukannya.

Baca buku yang saya rekomendasikan di sini .

Anda benar-benar harus membacanya. Saya percaya bab-bab yang relevan untuk kasus ini adalah 5,6,10,11

Meningkatkan kinerja disk

  1. Dapatkan drive SSD dan letakkan seluruh database di atasnya. Kinerja membaca kemungkinan besar akan empat kali lipat dan kinerja menulis juga harus meningkat secara radikal

  2. tetapkan lebih banyak memori untuk postgres. Idealnya Anda harus dapat menetapkan memori yang cukup sehingga keseluruhan (atau bagian terpanas) dapat di-cache ke memori, tetapi tidak terlalu banyak sehingga terjadi pertukaran. Bertukar sangat buruk. Ini tercakup dalam buku yang dikutip pada paragraf sebelumnya

  3. nonaktifkan atime pada semua disk (tambahkan opsi noatime ke fstab)

Meningkatkan kinerja permintaan

Gunakan alat yang dijelaskan dalam buku yang dikutip di atas untuk melacak permintaan Anda dan menemukan penghentian yang layak untuk dioptimalkan.

Memperbarui

Setelah komentar saya melihat kode sumber untuk prosedur tersimpan

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

dan tampaknya begitu permintaan telah disetel tidak ada banyak ruang untuk perbaikan karena algoritma berjalan sepenuhnya dalam memori (dan, sayangnya hanya pada satu cpu). Saya khawatir satu-satunya solusi Anda adalah menemukan algoritma yang lebih baik / lebih cepat atau yang dapat menjalankan multithreaded dan kemudian mengintegrasikannya dengan postgres baik dengan membuat perpustakaan seperti pgrouting atau menggunakan beberapa middleware untuk mengambil data (dan menyimpannya, mungkin) dan beri makan ke algoritma.

HTH

unicoletti
sumber
Saya telah membaca bagian-bagian buku yang Anda rekomendasikan. Dataset saya masih cukup kecil untuk sepenuhnya masuk ke dalam memori jadi saya pikir kinerja disk seharusnya tidak menjadi hambatan (saya akan lebih baik memeriksa sumber daya saya saat pengujian untuk mengonfirmasi ini). Saya pikir Postgresql hanya berperan dalam proses pgrouting ketika ia melakukan pemilihan * dari tabel sederhana untuk memberi makan perpustakaan C Boost dengan baris / tuple untuk melakukan pencarian yang sebenarnya ((dapat seseorang mengonfirmasi ini) jadi saya khawatir tidak ada banyak keuntungan di Postgresql sendiri. Jawaban Anda tampaknya sangat baik untuk kinerja Postgresql tetapi mungkin tidak demikian untuk pgrouting kinerja tertentu.
mrg
@ mrg Sebenarnya saya sudah memikirkan hal itu, tetapi saya ingin memastikan bahwa Anda tidak meninggalkan buah yang menggantung rendah. Kalau dipikir-pikir, Anda pergi dari 20 ms untuk 3.5k ke 900 ms untuk 122k yang, imho, tidak sepenuhnya buruk. Semoga berhasil
unicoletti
Solid State Drives meningkatkan kinerja (kecepatan yang sama dengan caching apa)
Mapperz
Dalam pengalaman saya, jika menggunakan pgrouting pada semua dataset (tabel) maka tidak ada manfaat besar dari mesin Postgres. Indeks bahkan tidak digunakan jadi tidak berguna. Pada setiap kueri, seluruh tabel dimuat ke dalam memori. buffer dan cache yang dibagikan juga tidak memberikan manfaat kinerja apa pun karena setiap kueri memuat semua tabel ke dalam memori. Jika ada yang berhasil menggunakan kembali data yang dimuat dalam memori untuk pertanyaan selanjutnya, beri tahu kami. Hanya kemungkinan peningkatan kinerja yang saya lihat di drive SDD, tetapi saya belum pernah mengujinya. Lebih banyak memori hanya memungkinkan lebih banyak permintaan bersamaan, bukan kinerja.
Mario Miler
8

Saya hanya memiliki masalah yang sama dan akan bertanya di milis, jadi terima kasih untuk semua orang!

Saya menggunakan Shooting Star dengan sejuta setengah baris di tabel perutean. Diperlukan hampir sepuluh detik untuk menghitungnya. Dengan baris 20k dibutuhkan hampir tiga detik. Saya perlu Shooting Star karena saya perlu batasan belokan.

Berikut adalah beberapa ide yang saya coba terapkan:

  • Pada SQL di mana pgRouting mendapatkan cara, gunakan st_buffer sehingga tidak mendapatkan semua cara, tetapi hanya cara "terdekat":

    pilih * dari shortest_path_shooting_star ('SELECT rout. * FROM routing rout, (pilih st_buffer (st_envelope (st_collect (geometry)), 4) sebagai geometri dari perutean di mana id =' || source_ || 'atau id =' || target | | ') e WHERE rout.geometry && e.geometry', sumber, target, benar, benar);

Ini meningkatkan kinerja, tetapi jika cara harus keluar buffer, itu dapat mengembalikan kesalahan "tidak ada jalan yang ditemukan", jadi ... buffer besar? beberapa panggilan meningkatkan buffer sampai menemukan jalan?

  • Rute cepat di-cache

Seperti yang disarankan oleh dassouki, saya akan membuat cache beberapa rute "berguna" jadi jika jaraknya terlalu panjang, ia bisa melalui rute cepat ini dan hanya perlu menemukan jalan keluar-masuknya.

  • Tabel partisi berdasarkan indeks gis

Tapi saya kira itu, jika masuk ke memori, itu tidak terlalu penting ... Bagaimanapun, harus mengujinya.

Tolong, terus posting jika Anda menemukan ide lain.

Juga, tahukah Anda jika ada beberapa pgRouting yang dikompilasi untuk Postgres9?

Délawen
sumber
+1 Tampaknya ada beberapa ide yang berguna dan konstruktif di sini. Harap perhatikan bahwa jika Anda ingin agar pertanyaan Anda dijawab, maka yang terbaik adalah merumuskannya sebagai pertanyaan baru. FAQ kami akan memberi tahu Anda bagaimana melanjutkan.
whuber
Délawen, saya juga telah memikirkan ide pertama Anda (ST_Buffer) dan meramalkan masalah yang sama. Keuntungannya bisa 2 cara: dataset lebih kecil dan dengan demikian lebih cepat dan karena lebih banyak pemrosesan sedang dilakukan di Postgresql Anda memiliki cara lagi untuk mengoptimalkannya. Saya menggunakan Ubuntu 11 di mana postgresql 8.4 adalah versi terbaru.
mrg
mrg, saya mengkompilasi pgRouting pada Ubuntu Maverick untuk PostgreSQL 9.0 tanpa banyak masalah. Postgis untuk PostgreSQL 9.0 dapat ditemukan di sini: ppa.launchpad.net/pi-deb/gis/ubuntu maverick / main amd64 Packages
Délawen
Saya datang dengan 2 ide. 1) Kombinasi 'rute cepat di-cache' dan 'st_buffer'. Dengan begitu Anda menjamin menemukan rute dan orang-orang tidak semua akan dipaksa pada rute yang sama. 2) Hanya gunakan postgis untuk mengisi grafik statis (dengan Boost (C), nx_spatial (Python), neo4j (Java), dll.) Dan gunakan kembali grafik itu untuk setiap permintaan pencarian.
mrg
Bagaimana dengan menurunkan biaya (yaitu meningkatkan preferensi) untuk tepi 'cepat' seperti jalan raya ketika jarak antara awal dan akhir lebih besar dari ambang batas? Faktor pendorong juga bisa terkait dengan jarak: lebih besar untuk jarak yang lebih jauh, lebih kecil untuk yang lebih pendek.
unicoletti
5

Kami baru saja membuat cabang di git untuk lintasan terpendek belokan terbatas @ https://github.com/pgRouting/pgrouting/tree/trsp

Maaf belum ada dokumentasi, tetapi jika Anda mengajukan pertanyaan pada daftar pgRouting, saya nongkrong di sana dan akan merespons. Kode ini berjalan jauh lebih cepat daripada bintang jatuh dan didasarkan pada algoritma Dijkstra.

-Steve

Stephen Woodbridge
sumber
0

Saya memiliki tabel rute sumber yang berisi ~ 1200000 tepi. Pada i7 saya dengan SSD, dibutuhkan 12 detik untuk membuat rute. Ide saya untuk meningkatkan kinerja adalah membagi tabel tepi menjadi beberapa tabel level zoom. Maksud saya level yang identik dengan ubin google. Pada tingkat zoom 8, misalnya, saya memiliki 88 tabel. Setiap tabel berisi subset jalan dan area mereka saling tumpang tindih sehingga untuk menghitung rute antara dua titik yang terletak tidak jauh dari 290 km satu sama lain membutuhkan waktu 2 detik. Pada level 9 waktu perhitungan turun menjadi 0,25 detik dan kami memiliki 352 tabel. Rekreasi semua grafik jika kami mengedit jalan tidak lebih dari satu jam. Cara radikal untuk meningkatkan kecepatan perutean adalah dengan menggunakan algoritma Floyd-Warshall. Tapi tidak ada yang tahu berapa yang dibutuhkan untuk menghitung matriks pendahulu di banyak sisi.

Vadym
sumber