PostGIS / OSM: consulta más rápida para encontrar más cercano de la línea de puntos

Question

Situación siguiente: tengo una tabla roads, que contiene básicamente la red de carreteras de un país entero extraído de la OSM line de mesa y una mesa de points que contiene millones de GPS de seguimiento de puntos que son parte de las pistas. Ambos tienen un id columna, una geometría PostGIS geom columna con los tipos LineString (carreteras) y Point (puntos), así como un índice espacial en las columnas. El sistema de referencia se ha SRID 4326. La geometría de índice agrupado.

Versiones: Postgres 9.5, PostGIS 2.2.2

Quiero averiguar qué camino es el más cercano para cada punto. Se me ocurrió la siguiente propuesta: ¿Cómo encontrar el punto más cercano mediante el uso de PostGIS función?

SELECT point.id, road.id, ST_Distance(road.geom, point.geom) AS Distance 
FROM roads AS road, points AS point
WHERE road.id = ( 
   SELECT r.id
   FROM roads as r, points as p
   WHERE point.id = p.id
   ORDER BY ST_Distance(r.geom, p.geom) ASC LIMIT 1
);

El resultado de EXPLAIN ANALYZE donde el resultado es limitada a 1 punto:

"Limit  (cost=2171519.51..4343038.72 rows=1 width=186) (actual time=7944.471..7944.471 rows=1 loops=1)"
"  ->  Nested Loop  (cost=2171519.51..4578064121748.85 rows=2108230 width=186) (actual time=7944.470..7944.470 rows=1 loops=1)"
"        ->  Seq Scan on points point  (cost=0.00..78098.30 rows=2108230 width=36) (actual time=0.006..0.006 rows=1 loops=1)"
"        ->  Index Scan using roads_id_index on roads road  (cost=2171519.51..2171519.95 rows=1 width=150) (actual time=0.010..0.010 rows=1 loops=1)"
"              Index Cond: (id = (SubPlan 1))"
"              SubPlan 1"
"                ->  Limit  (cost=2171519.07..2171519.07 rows=1 width=182) (actual time=7944.438..7944.438 rows=1 loops=1)"
"                      ->  Sort  (cost=2171519.07..2189421.96 rows=7161155 width=182) (actual time=7944.437..7944.437 rows=1 loops=1)"
"                            Sort Key: (st_distance(r.geom, p.geom))"
"                            Sort Method: top-N heapsort  Memory: 25kB"
"                            ->  Nested Loop  (cost=0.43..2135713.30 rows=7161155 width=182) (actual time=0.034..7046.628 rows=7161026 loops=1)"
"                                  ->  Index Scan using points_pkey on points p  (cost=0.43..8.45 rows=1 width=32) (actual time=0.013..0.015 rows=1 loops=1)"
"                                        Index Cond: (point.id = id)"
"                                  ->  Seq Scan on roads r  (cost=0.00..273804.55 rows=7161155 width=150) (actual time=0.003..1455.615 rows=7161026 loops=1)"
"              SubPlan 1"
"                ->  Limit  (cost=2171519.07..2171519.07 rows=1 width=182) (actual time=7944.438..7944.438 rows=1 loops=1)"
"                      ->  Sort  (cost=2171519.07..2189421.96 rows=7161155 width=182) (actual time=7944.437..7944.437 rows=1 loops=1)"
"                            Sort Key: (st_distance(r.geom, p.geom))"
"                            Sort Method: top-N heapsort  Memory: 25kB"
"                            ->  Nested Loop  (cost=0.43..2135713.30 rows=7161155 width=182) (actual time=0.034..7046.628 rows=7161026 loops=1)"
"                                  ->  Index Scan using points_pkey on points p  (cost=0.43..8.45 rows=1 width=32) (actual time=0.013..0.015 rows=1 loops=1)"
"                                        Index Cond: (point.id = id)"
"                                  ->  Seq Scan on de_road_network r  (cost=0.00..273804.55 rows=7161155 width=150) (actual time=0.003..1455.615 rows=7161026 loops=1)"
"Planning time: 0.426 ms"
"Execution time: 7944.560 ms"

Esta consulta funciona bien, pero tengo una eficiencia problema.

La consulta anterior tiene más de 7 segundos para que un punto. Creo que no hay manera de acelerar este proceso con el índice, ya que el ST_Distance función no se puede utilizar el índice. De todos modos, desde que me gustaría hacer esto para (~ 3) en millones de puntos que me gustaría para acelerar la consulta o para desarrollar más rápido.

¿Tiene alguna sugerencia sobre que ?

Algunas ideas:

• El uso de la && oeprator, que utiliza el índice. El cambio de la WHERE cláusula de la sub-consulta a: WHERE point.id = p.id AND p.geom && r.geom de resultados en un gran aumento en la velocidad. Ver: Vecino más Cercano problema en Postgis 2.0 el uso de GIST Índice (<-> función) .

Es esta la solución exacta ? ¿Qué sucede si un punto de p tiene una carretera más cercana r1 pero p no está en el recuadro de delimitación r1 , pero en el recuadro de delimitación r2 ? Es este escenario factible ?

• El uso de la <-> operador: he intentado reemplazar el ST_Distance con la <-> operador pero sin éxito. El índice espacial no está involucrado. Supongo que es porque

Índice sólo se activa si una de las geometrías es una constante (no en una subconsulta/cte). por ejemplo, 'SRID=3005;PUNTO(1011102 450541)'::geometría en lugar de una.geom

• Incluyendo un pre-filtrado de paso el uso de otras funciones de postgis ? E. g. con la ST_DWithin función. (Ver: Encontrar la más cercana a los vecinos más rápido en PostGIS). ¿Cómo sería una consulta, si quiero especificar la distancia en metros ?

• Sería, probablemente, dar sentido a la vuelta a este problema en un punto en el polígono problema mediante la transformación de cada ruta en un polígono con un ancho fijo, seguido por un punto en el polígono de prueba ? Supongo que muchos de los puntos sólo coincidirá con un polígono. Y para los que no, que podía hacer que la distancia de la prueba.

• Obtener una aproximados de la solución (por ejemplo, Utilizando una radial de barrido de la línea como la que aquí se propone: Encontrar el más Cercano de los Segmentos de Línea a Punto)

La solución Final de la Consulta: el Uso de CROSS JOIN LATERAL (Créditos a Tyler)

SELECT p.id AS point_id, b.id AS road_id, ST_DISTANCE(b.geom, p.geom) AS distance
FROM points p
CROSS JOIN LATERAL (
    SELECT r.id AS id, r.geom AS geom
    FROM roads r
    ORDER BY r.geom <-> p.geom 
    LIMIT 1
) b;

Answer 1

Te gustaría ser capaz de agregar el resultado de poner "EXPLICAR ANALIZAR" antes de la consulta en tu pregunta? Entonces puedo actualizar mi respuesta con sugerencias.

Por supuesto, usted necesitará GIST índices en la tabla de la geometría de los campos y de vacío analizar primero.

CREATE INDEX ON road USING gist (geom);
CREATE INDEX ON point USING gist (geom);
VACUUM ANALYZE road;
VACUUM ANALYZE point;

Usted podría intentar algo como esto, al menos podría darle algunas ideas que pueden resultar en la búsqueda de su respuesta.

SELECT p.id, cjl.id
FROM point p
CROSS JOIN LATERAL (
    SELECT r.id 
    FROM road r
    ORDER BY r.geom <-> p.geom 
    LIMIT 1
) cjl
WHERE p.id = 1

Explicación:

Yo personalmente disfruto el uso de combinación CRUZADA LATERAL porque me puede pasar en la tabla principal de la columna para filtrar y limitar los resultados. El <-> operador se utiliza para aumentar el rendimiento de hacer del vecino más cercano aproximado de la distancia de pedidos - las mejoras de rendimiento que superan con creces el "aproximado" de la distancia en términos de precisión.

Recursos:

http://postgis.net/docs/geometry_distance_knn.html http://postgis.net/docs/geometry_distance_centroid.html https://www.postgresql.org/docs/9.3/static/queries-table-expressions.html#QUERIES-LATERAL