Problema de vecino más cercano en Postgis 2.0 usando el índice GIST (función <->)

25

Estoy tratando de usar Postgis 2.0 nueva función <-> (Geometry Distance Centroid) para calcular, para cada fila de mi tabla (cosn1), la distancia al polígono más cercano de la misma clase.

Estaba tratando de usar el siguiente código:

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;

Pero luego me doy cuenta de la advertencia:

Nota: El índice solo se activa si una de las geometrías es una constante (no en una subconsulta / cte). por ejemplo, 'SRID = 3005; POINT (1011102 450541)' :: geometría en lugar de a.geom

Lo que significa que el índice no se usará en absoluto, y la consulta tomará casi el mismo tiempo que antes de usar:

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)

¿Alguien puede señalarme una solución alternativa que me permita mejorar el rendimiento de mi consulta?

Muchas gracias.

nearest-neighbor postgis-2.0 Alexandre Neto
fuente
Dado que aún no hay respuestas, puede preguntar esto en la lista de correo de PostGIS.
GIS-Jonathan
Ya lo hice, pero también sin ninguna respuesta.
Alexandre Neto
3
Puede usar g1.gid> g2.gid en la cláusula where, que reducirá la cantidad de cálculos de distancia que tiene que hacer. Desafortunadamente, hasta que el operador <-> funcione sin constantes, no veremos mucha mejora en la velocidad en este tipo de consulta.
John Powell
John, necesito mantener todos los gids, incluso los que se repiten, ya que necesito actualizar el EEN para cada uno de los polígonos en mi tabla "cosn1". Pero lo que dijiste me dio una idea. Podría hacer lo que usted dice usando g1.gid> g2.gis para reducir los cálculos de distancia, pero manteniendo g1.gid y g2.gid en el resultado. Después de eso, podría unir dos subconsultas (una con g1.gis como gid y otra con g2.gid). Gracias
Alexandre Neto
Descubrí que una posible solución para solucionar el problema constante sería usar <-> dentro de una función SQL, usando the_geom como parámetro. He realizado algunas pruebas, y en algunos casos es mucho más rápido (). Pero en mi caso, dado que las distancias están dentro de la misma tabla, muchos cálculos de distancia se repiten durante el proceso, por lo que es más lento que usar la consulta directa.
Alexandre Neto

Respuestas:

2

Hum haciendo algunas pruebas en mi máquina sonaba como si este operador <-> no funcionara correctamente. No estoy seguro de que sea un error, pero informó una distancia cero en geometrías no superpuestas. ¿No intrigante?

¿Y qué hay de las justas optimizaciones de consultas SQL tradicionales? Desde esos resultados inesperados con el operador <->, lo reemplazo con st_centroid. Obtuve resultados mucho mejores en velocidad.

La semántica de la esperanza con st_overlaps se mantiene igual. Al menos esto fue entendido por la documentación sobre <->

De documentos en Postigs <->

Para otros tipos de geometría, se devuelve la distancia entre los centroides del cuadro delimitador de coma flotante.

En mis datos de prueba con ~ 5.5k polígonos se aceleró de ~ 1000 segundos a ~ 5 segundos sin indexación espacial.

De todos modos, ¿por qué usar DISTINCT ON para agrupar? ¿Veo a algunas personas usándolo pero no existe el grupo by para eliminar duplicados?

Su consulta con optimizaciones SQL estándar sin el error st_centroid introducido

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

Felices vacaciones de navidad!

cavila
fuente
Lo sentimos, pero tu respuesta no resuelve el problema. De hecho, es mucho más rápido, pero los resultados no son precisos, ya que el resultado final se calcula utilizando los centroides de los polígonos, en lugar de su geometría real. El <-> tiene como objetivo optimizar la búsqueda de candidatos al vecino más cercano, pero al final debe usar las geometrías reales para calcular la distancia a los mejores candidatos. También intenté usar MIN \ GROUP BY en lugar de DISTINCT ON \ ORDER BY, y parece ser más lento.
Alexandre Neto
Pero el manual postgis para el operador <-> establece que usa el centroide para geometrías sin puntos. Entonces mi solución te daría resultados similares. Debería darte los mismos resultados que tu consulta principal. Compruebe que los resultados con el operador <-> también sean correctos. Me informó geometrías de longitud cero en mis datos de prueba, por lo que los resultados podrían romperse y esta solución proporcionaría datos más precisos. Si puede publicar algunos registros de muestra que muestran errores en algún sitio pastoso, podríamos descubrir fallas en la solución.
cavila
Si marca mi consulta, el operador <-> se usaría solo para ordenar a los candidatos, el resultado final se calcula utilizando las geometrías reales. De todos modos, como dije antes, el aumento de rendimiento <-> solo funciona con puntos fijos. Esa fue mi pregunta original.
Alexandre Neto
Entonces, ¿está de acuerdo en que la consulta superior no es equivalente a la consulta inferior? Dado que el orden cambiará porque el operador <-> ORDER BY st_centroid y st_distance le dará un valor diferente? ¿Un orden diferente puede traer una consulta diferente como la primera fila para pasar la cláusula DISTINCT ON? ¿La consulta válida sería la inferior que necesita mejorar la velocidad?
cavila
Sí, la primera consulta es una intención de mejorar la velocidad en la inferior. Y sí, podría dar un resultado un poco diferente, ya que g1.geom <-> g2.geom usa los centroides, y eso significa que la primera fila podría no estar más cerca. Para que funcione, creo que tendría que poner un límite al orden mediante la cláusula say limit 10 y luego extraer los valores reales de la distancia. Incluso podría usar el <#> en su lugar, que usa los cuadros delimitadores en lugar de los centroides.
Alexandre Neto