Nearest Neighbour Problem in Postgis 2.0 mit GIST Index (<-> Funktion)

25

Ich versuche, die neue Postgis 2.0-Funktion <-> (Geometry Distance Centroid) zu verwenden, um für jede Zeile meiner Tabelle (cosn1) die Entfernung zum nächsten Polygon derselben Klasse zu berechnen.

Ich habe versucht, den folgenden Code zu verwenden:

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;

Aber dann merke ich die Warnung:

Hinweis: Der Index wird nur aktiviert, wenn eine der Geometrien eine Konstante ist (nicht in einer Unterabfrage / einem Byte). zB 'SRID = 3005; POINT (1011102 450541)' :: Geometrie anstelle von a.geom

Dies bedeutet, dass der Index überhaupt nicht verwendet wird und die Abfrage fast genauso lange dauert wie vor der Verwendung von:

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)

Kann mir jemand eine Problemumgehung empfehlen, mit der ich die Leistung meiner Abfrage verbessern kann?

Vielen Dank.

nearest-neighbor postgis-2.0 Alexandre Neto
quelle
Wenn Sie noch keine Antworten erhalten haben, können Sie dies in der PostGIS-Mailingliste nachfragen.
GIS-Jonathan
Das habe ich schon getan, aber auch ohne Antworten.
Alexandre Neto
3
In der where-Klausel können Sie g1.gid> g2.gid verwenden, wodurch sich die Anzahl der Entfernungsberechnungen verringert, die Sie durchführen müssen. Bis der Operator <-> ohne Konstanten arbeitet, werden wir bei dieser Art von Abfrage leider keine wesentliche Geschwindigkeitsverbesserung feststellen.
John Powell
John, ich muss alle Gids behalten, auch die, die wiederholt werden, wenn ich die EEN für jedes der Polygone in meiner "cosn1" -Tabelle aktualisieren muss. Aber was du gesagt hast, hat mich auf eine Idee gebracht. Ich könnte tun, was Sie sagen, indem Sie g1.gid> g2.gis verwenden, um Entfernungsberechnungen zu reduzieren, aber g1.gid und g2.gid im Ergebnis behalten. Danach konnte ich zwei Unterabfragen davon verbinden (eine mit g1.gis als gid und eine mit g2.gid). Danke
Alexandre Neto
Ich stellte fest, dass eine mögliche Lösung zur Umgehung des ständigen Problems darin besteht, das <-> in einer SQL-Funktion zu verwenden und the_geom als Parameter zu verwenden. Ich habe einige Tests gemacht, und in einigen Fällen ist es viel schneller (). In meinem Fall werden jedoch viele Entfernungsberechnungen während des Vorgangs wiederholt, da sich die Entfernungen in derselben Tabelle befinden. Dies ist langsamer als die direkte Abfrage.
Alexandre Neto

Antworten:

2

Das Summen bei einigen Tests auf meinem Computer hat sich so angehört, als ob der Operator <-> nicht richtig funktioniert. Ich bin mir nicht sicher, ob das ein Fehler ist, aber es wurde ein Abstand von Null für nicht überlappende Geometrien gemeldet. Interessant nein?

Was ist mit den fairen traditionellen SQL-Abfrageoptimierungen? Da diese unerwarteten Ergebnisse mit dem Operator <-> auftreten, ersetze ich ihn durch st_centroid. Bekam viel bessere Ergebnisse in der Geschwindigkeit.

Hoffe, die Semantik mit st_overlaps bleibt gleich. Zumindest habe ich das aus der Dokumentation über <-> verstanden

Aus Dokumenten zu Postigs <->

Bei anderen Geometrietypen wird der Abstand zwischen den Mittelpunkten des Gleitkomma-Begrenzungsrahmens zurückgegeben.

Bei meinen Testdaten mit ~ 5.5k Polygonen wurde die Geschwindigkeit von ~ 1000 Sekunden auf ~ 5 Sekunden ohne räumliche Indizierung erhöht.

Warum sollte DISTINCT ON zum Gruppieren verwendet werden? Ich sehe einige Leute, die es benutzen, aber die Gruppe existiert nicht, um Duplikate zu beseitigen.

Ihre Abfrage mit Standard-SQL-Optimierungen ohne den eingeführten st_centroid-Fehler

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

Frohe Weihnachten!

cavila
quelle
Entschuldigung, aber Ihre Antwort löst das Problem nicht. Es ist zwar viel schneller, aber die Ergebnisse sind nicht genau, da das Endergebnis unter Verwendung der Zentroide der Polygone anstelle ihrer tatsächlichen Geometrie berechnet wird. Das <-> zielt darauf ab, die Suche nach Kandidaten für den nächsten Nachbarn zu optimieren, sollte jedoch letztendlich die realen Geometrien verwenden, um den Abstand zu den besten Kandidaten zu berechnen. Ich habe auch versucht, MIN \ GROUP BY anstelle von DISTINCT ON \ ORDER BY zu verwenden, und es scheint langsamer zu sein.
Alexandre Neto
Das Postgis-Handbuch für den Operator <-> gibt jedoch an, dass der Schwerpunkt für Nicht-Punkt-Geometrien verwendet wird. Meine Lösung würde also zu ähnlichen Ergebnissen führen. Es sollte die gleichen Ergebnisse liefern wie Ihre Top-Abfrage. Bitte überprüfen Sie auch, ob die Ergebnisse mit dem Operator <-> korrekt sind. Es wurden Geometrien mit der Länge Null für meine Testdaten gemeldet, damit die Ergebnisse gebrochen werden konnten und diese Lösung genauere Daten lieferte. Wenn Sie in der Lage sind, einige Beispieldatensätze mit Fehlern auf einer Pastiesite zu veröffentlichen, können wir Fehler bei der Lösung entdecken.
Cavila
Wenn Sie meine Abfrage überprüfen, wird der Operator <-> nur zum Bestellen der Kandidaten verwendet. Das Endergebnis wird anhand der tatsächlichen Geometrien berechnet. Wie ich bereits sagte, funktioniert der <-> Leistungsschub nur mit Fixpunkten. Das war meine ursprüngliche Frage.
Alexandre Neto
Stimmen Sie also zu, dass die obere Abfrage nicht der unteren Abfrage entspricht? Da sich die Reihenfolge ändert, weil der Operator <-> ORDER BY st_centroid und die st_distance einen anderen Wert ergeben? Eine andere Reihenfolge kann zu einer anderen Abfrage führen als die erste Zeile, die die DISTINCT ON-Klausel weitergibt. Die gültige Abfrage wäre die unterste, die eine Geschwindigkeitsverbesserung benötigt?
Cavila
Ja, die erste Abfrage soll die Geschwindigkeit der untersten verbessern. Und ja, es könnte ein etwas anderes Ergebnis geben, da g1.geom <-> g2.geom die Zentroide verwendet, und das bedeutet, dass die erste Reihe möglicherweise nicht näher ist. Damit es funktioniert, müsste ich meiner Meinung nach der Reihenfolge eine Grenze setzen, indem ich Limit 10 sage und dann die tatsächlichen Entfernungswerte extrahiere. Könnte stattdessen auch das <#> verwenden, das die Begrenzungsrahmen anstelle der Zentroide verwendet.
Alexandre Neto