Problem Najbliższego sąsiada w Postgis 2.0 przy użyciu indeksu GIST (funkcja <->)

25

Próbuję użyć nowej funkcji Postgis 2.0 <-> (Centroid Distance Geometry), aby obliczyć dla każdego wiersza mojej tabeli (cosn1) odległość do najbliższego wielokąta tej samej klasy.

Próbowałem użyć następującego kodu:

WITH index_query AS (
  SELECT g1.gid As ref_gid, ST_Distance(g1.the_geom,g2.the_geom) As ENN    
    FROM "cosn1" As g1, "cosn1" As g2   
    WHERE g1.gid <> g2.gid AND g1.class = g2.class
    ORDER BY g1.gid, g1.the_geom <-> g2.the_geom) 
SELECT DISTINCT ON (ref_gid) ref_gid, ENN 
    FROM index_query
ORDER BY ref_gid, ENN;

Ale wtedy zdaję sobie sprawę z ostrzeżeniem:

Uwaga: Indeks jest uruchamiany tylko wtedy, gdy jedna z geometrii jest stała (nie w podzapytaniu / cte). np. „SRID = 3005; POINT (1011102 450541)” :: geometria zamiast a.geom

Oznacza to, że Indeks w ogóle nie będzie używany, a zapytanie zajmie prawie taki sam czas, jak przed użyciem:

SELECT DISTINCT ON(g1.gid)  g1.gid As ref_gid, ST_Distance(g1.the_geom,g2.the_geom) As ENN    
    FROM "cosn1" As g1, "cosn1" As g2   
    WHERE g1.gid <> g2.gid AND g1.class = g2.class
    ORDER BY g1.gid, ST_Distance(g1.the_geom,g2.the_geom)

Czy ktoś może wskazać mi obejście, które pozwala mi poprawić wydajność mojego zapytania?

Dziękuję Ci bardzo.

Alexandre Neto
źródło
Wobec braku odpowiedzi możesz zadać to pytanie na liście mailingowej PostGIS.
GIS-Jonathan
Już to zrobiłem, ale także bez odpowiedzi.
Alexandre Neto
3
Możesz użyć g1.gid> g2.gid w klauzuli where, co zmniejszy liczbę obliczeń odległości, które musisz wykonać. Niestety, dopóki operator <-> nie będzie działał bez stałych, nie zobaczymy znacznej poprawy prędkości w tego rodzaju zapytaniach.
John Powell,
John, muszę zachować wszystkie klasy, nawet te powtarzane, gdy muszę zaktualizować EEN dla każdego z wielokątów w mojej tabeli „cosn1”. Ale to, co powiedziałeś, dało mi pomysł. Mógłbym zrobić, jak mówisz, używając g1.gid> g2.gis, aby zmniejszyć obliczenia odległości, ale utrzymując w wyniku g1.gid i g2.gid. Następnie mogłem połączyć dwa jego podkwerendy (jeden z g1.gis jako gid, a drugi z g2.gid). Dzięki
Alexandre Neto,
Odkryłem, że możliwym rozwiązaniem tego stałego problemu byłoby użycie <-> wewnątrz funkcji SQL, używając parametru the_geom jako parametru. Zrobiłem kilka testów, a w niektórych przypadkach jest to znacznie szybsze (). Ale w moim przypadku, ponieważ odległości znajdują się w tej samej tabeli, wiele obliczeń odległości jest powtarzanych podczas procesu, co powoduje, że jest wolniejszy niż przy użyciu bezpośredniego zapytania.
Alexandre Neto

Odpowiedzi:

2

Hum podczas niektórych testów na moim komputerze brzmiał tak, jakby ten operator <-> nie działał poprawnie. Nie jestem pewien, czy to błąd, ale zgłosił zerową odległość dla nie nachodzących na siebie geometrii. Intrygujące nie?

A co z uczciwymi tradycyjnymi optymalizacjami zapytań SQL? Ponieważ te nieoczekiwane wyniki z operatorem <-> zastępuję go st_centroid. Osiągnął znacznie lepsze wyniki w zakresie prędkości.

Nadzieja, że ​​semantyka z st_overlaps pozostają takie same. Przynajmniej zrozumiałem to z dokumentacji dotyczącej <->

Z dokumentów na Postigs <->

Dla innych typów geometrii zwracana jest odległość między centroidami obwiedni zmiennoprzecinkowych.

Na moich testach dane z ~ 5,5k wielokątów przyspieszyły z ~ 1000 sekund do ~ 5 sekund bez indeksowania przestrzennego.

W każdym razie, dlaczego używasz DISTINCT ON do grupowania? Widzę, że niektórzy ludzie go używają, ale grupa nie istnieje, aby wyeliminować duplikaty?

Twoje zapytanie ze standardowymi optymalizacjami SQL bez wprowadzonego błędu st_centroid

select g1.gid, min( st_distance( g1.the_geom, g2.the_geom ) ) AS enn
FROM 
  "cosn1" AS g1, "cosn1" AS g2
WHERE
  g1.gid <> g2.gid
  AND g1.class = g2.class
  AND g1.the_geom && g2.the_geom
GROUP BY
  g1.gid

Wesołych Świąt Bożego Narodzenia!

Cavila
źródło
Przepraszamy, ale twoja odpowiedź nie rozwiązuje problemu. W rzeczywistości jest znacznie szybszy, ale wyniki nie są dokładne, ponieważ wynik końcowy jest obliczany za pomocą centroidów wielokątów, zamiast ich rzeczywistej geometrii. <-> ma na celu optymalizację wyszukiwania kandydatów do najbliższego sąsiada, ale ostatecznie należy użyć rzeczywistych geometrii, aby obliczyć odległość do najlepszych kandydatów. Próbowałem także użyć MIN \ GROUP BY zamiast DISTINCT ON \ ORDER BY i wydaje się być wolniejszy.
Alexandre Neto,
Jednak instrukcja postgis dla operatora <-> stwierdza, że ​​używa on środka ciężkości dla geometrii niepunktowych. Więc moje rozwiązanie dałoby podobne wyniki. Powinno dać ci takie same wyniki jak twoje najpopularniejsze zapytanie. Sprawdź, czy wyniki operatora <-> są również poprawne. Zgłoszono mi geometrie zerowej długości na moich danych testowych, więc wyniki mogły zostać złamane, a to rozwiązanie dało dokładniejsze dane. Jeśli możesz opublikować przykładowe rekordy pokazujące błędy w jakiejś witrynie z ciastkami, moglibyśmy odkryć wady rozwiązania.
cavila
Jeśli sprawdzisz moje zapytanie, operator <-> zostanie użyty tylko do zamówienia kandydatów, wynik końcowy zostanie obliczony na podstawie rzeczywistych geometrii. W każdym razie, jak powiedziałem wcześniej, zwiększenie wydajności <-> działa tylko z ustalonymi punktami. To było moje pierwotne pytanie.
Alexandre Neto,
Czy zgadzasz się, że górne zapytanie nie jest równoważne z dolnym zapytaniem? Ponieważ kolejność ulegnie zmianie, ponieważ operator <-> ORDER BY st_centroid, a odległość st_ da ci inną wartość? Inna kolejność może przynieść inne zapytanie jako pierwszy wiersz do przekazania klauzuli DISTINCT ON? Prawidłowe zapytanie byłoby dolne, które wymaga poprawy prędkości?
cavila 27.12.12
Tak, pierwsze zapytanie ma na celu zwiększenie prędkości na dole. I tak, może dać nieco inny wynik, ponieważ g1.geom <-> g2.geom używa centroidów, a to oznacza, że ​​pierwszy rząd może nie być bliżej. Aby to zadziałało, uważam, że musiałbym ograniczyć zamówienie według klauzuli powiedz limit 10, a następnie wyodrębnić rzeczywiste wartości odległości. Można nawet użyć zamiast tego <#>, który używa obwiedni zamiast centroidów.
Alexandre Neto,