Bagaimana saya bisa mengoptimalkan kueri Point in Polygon untuk jutaan poin ketika sebagian besar poin berada di dalam poligon?

8

Saya memiliki 150 juta poin dalam tabel poin dan ingin menemukan beberapa titik di luar geometri poligon yang diberikan. Saya tahu bahwa 99,9% poin berada dalam geometri poligon. Saya tertarik menemukan beberapa poin yang ada di luar poligon.

Permintaan terbaik saya saat ini menggunakan tabel PostGIS yang diindeks membutuhkan waktu sekitar 30 menit untuk menyelesaikannya. Apakah ada cara untuk mengoptimalkan kueri berikut mengetahui bahwa sebagian besar titik berada dalam poligon (perbatasan)?

SELECT COUNT(*) 
FROM italy_points pt
JOIN borders poly
ON ST_WITHIN (pt.the_geom, poly.geom)
WHERE poly.iso3 = 'ITA';

Poligon pada dasarnya adalah admin 0 perbatasan Italia. Verteks - 405.000. Bagian - 510. Amplop ini jauh lebih besar dari poligon (Poligon mencakup 24% dari amplop)

postgis postgresql Prithvi
sumber
2
Harap Edit pertanyaan untuk memberikan indikasi kompleksitas poligon - Berapa banyak bagian? Berapa banyak simpul? Berapa persentase amplop poligon dalam poligon. Saya telah menemukan bahwa mempartisi poligon kompleks dapat meningkatkan evaluasi titik-dalam poligon , tetapi Anda perlu menangani kondisi di mana satu titik memotong lebih dari satu partisi.
Vince
Optimalisasi pertama untuk jenis operasi ini biasanya untuk memeriksa apakah titik ada dalam kotak pembatas poligon sebelum melanjutkan ke operasi titik-dalam-poligon penuh. Point-in-box adalah operasi yang sangat efisien jika dibandingkan.
WhiteboxDev
@Vince Jika duplikat dimungkinkan (satu-satunya kasus yang saya pikirkan adalah ketika jatuh tepat di perbatasan dua partisi), ini ditangani secara sepele di PostGIS. Anda hanya perlu GROUP BYkunci utama poin. (PostgreSQL memudahkan Anda untuk mereferensikan kolom apa pun dalam SELECTklausa yang berasal dari tabel di mana kunci utama termasuk dalam GROUP BYklausa.)
jpmc26
@WhiteboxDev ST_Withinsudah melakukan kotak centang batas yang memungkinkan untuk menggunakan indeks. (Hampir semua fungsi PostGIS menyertakan optimisasi ini.) Jika masih lambat, jelas masalahnya adalah dengan kompleksitas poligon.
jpmc26
@ jpmc26 Tentu saja, tetapi kueri SQL juga perlu dimodifikasi untuk digunakan ST_Intersects, karena ST_Withintidak akan cocok dengan kondisi batas internal.
Vince

Jawaban:

10

Gunakan ST_Subdivide untuk memotong poligon Anda menjadi poligon yang lebih kecil, menyimpannya ke sebuah tabel dan membuat indeks spasial. Kemudian lakukan kueri Anda pada poligon grid.

Tanpa itu, pengindeksan spasial tidak memberikan keuntungan apa pun dalam kasus Anda (hanya 1 poligon yang menarik).

Mesa
sumber
4
Lebih jauh ke komentar ST_Subdivide (), Anda mungkin menemukan bahwa menggunakan kurang dari jumlah default simpul menghasilkan keuntungan lebih lanjut dengan meningkatkan leverage indeks dan mengurangi waktu pemulihan geometri. Coba 64 atau bahkan 32.
Paul Ramsey
Permintaan sekarang selesai dalam 5 menit dibandingkan dengan 30! Terima kasih untuk sarannya.
Prithvi
Wow, ini adalah teriakan yang sangat bagus. Permintaan saya menabrak mesin dengan 62Gb RAM dalam waktu kurang dari 2 menit dan kemudian ST_Subdivide ini membuatnya tidak hanya crash tetapi juga mengeksekusi dalam hitungan detik. Baru saja menemukan sahabat baru saya!
Momchill