sql - teoria - Cómo encontrar intersecciones geográficas entre dos tablas recursivamente

unir dos consultas sql misma tabla

Question

Estoy ejecutando Postgres 9.6.1 y PostGIS 2.3.0 r15146 y tengo dos tablas.
geographies pueden tener 150,000,000 filas, las paths pueden tener 10,000,000 filas:

CREATE TABLE paths (id uuid NOT NULL, path path NOT NULL, PRIMARY KEY (id))
CREATE TABLE geographies (id uuid NOT NULL, geography geography NOT NULL, PRIMARY KEY (id))

Dada una matriz / conjunto de ids para geographies tablas, ¿cuál es la "mejor" manera de encontrar todos los caminos y geometrías que se cruzan?

En otras palabras, si una geography inicial tiene una path intersección correspondiente, también debemos encontrar todas las otras geographies que esta path interseca. A partir de ahí, debemos encontrar todos los demás paths que intersectan estas geographies recién encontradas, y así sucesivamente hasta que hayamos encontrado todas las intersecciones posibles.

Los identificadores de geografía iniciales (nuestra entrada) pueden estar entre 0 y 700. Con un promedio de alrededor de 40.
Las intersecciones mínimas serán 0, la máxima será aproximadamente 1000. Promedio probable de alrededor de 20, generalmente menos de 100 conectadas.

He creado una función que hace esto, pero soy nuevo en SIG en PostGIS y en Postgres en general. He publicado mi solución como respuesta a esta pregunta .

Siento que debería haber una forma más elocuente y más rápida de hacer esto que la que he creado.

Answer 1

Pensé que sería bueno publicar mi propia solución aquí, incluso si no es óptima.

Aquí está lo que se me ocurrió (siguiendo el consejo de Steve Chambers):

CREATE OR REPLACE FUNCTION public.function_name(
    _fk_ids character varying[])
    RETURNS TABLE(id uuid, type character varying)
    LANGUAGE ''plpgsql''
    COST 100.0
    VOLATILE
    ROWS 1000.0
AS $function$

    DECLARE
        _pathLength bigint;
        _geographyLength bigint;

        _currentPathLength bigint;
        _currentGeographyLength bigint;
    BEGIN
        DROP TABLE IF EXISTS _pathIds;
        DROP TABLE IF EXISTS _geographyIds;
        CREATE TEMPORARY TABLE _pathIds (id UUID PRIMARY KEY);
        CREATE TEMPORARY TABLE _geographyIds (id UUID PRIMARY KEY);

        -- get all geographies in the specified _fk_ids
        INSERT INTO _geographyIds
            SELECT g.id
            FROM geographies g
            WHERE g.fk_id= ANY(_fk_ids);

        _pathLength := 0;
        _geographyLength := 0;
        _currentPathLength := 0;
        _currentGeographyLength := (SELECT COUNT(_geographyIds.id) FROM _geographyIds);
        -- _pathIds := ARRAY[]::uuid[];

        WHILE (_currentPathLength - _pathLength > 0) OR (_currentGeographyLength - _geographyLength > 0) LOOP
            _pathLength := (SELECT COUNT(_pathIds.id) FROM _pathIds);
            _geographyLength := (SELECT COUNT(_geographyIds.id) FROM _geographyIds);

            -- gets all paths that have paths that intersect the geographies that aren''t in the current list of path ids

            INSERT INTO _pathIds 
                SELECT DISTINCT p.id
                    FROM paths p
                    JOIN geographies g ON ST_Intersects(g.geography, p.path)
                    WHERE
                        g.id IN (SELECT _geographyIds.id FROM _geographyIds) AND
                        p.id NOT IN (SELECT _pathIds.id from _pathIds);

            -- gets all geographies that have paths that intersect the paths that aren''t in the current list of geography ids
            INSERT INTO _geographyIds 
                SELECT DISTINCT g.id
                    FROM geographies g
                    JOIN paths p ON ST_Intersects(g.geography, p.path)
                    WHERE
                        p.id IN (SELECT _pathIds.id FROM _pathIds) AND
                        g.id NOT IN (SELECT _geographyIds.id FROM _geographyIds);

            _currentPathLength := (SELECT COUNT(_pathIds.id) FROM _pathIds);
            _currentGeographyLength := (SELECT COUNT(_geographyIds.id) FROM _geographyIds);
        END LOOP;

        RETURN QUERY
            SELECT _geographyIds.id, ''geography'' AS type FROM _geographyIds
            UNION ALL
            SELECT _pathIds.id, ''path'' AS type FROM _pathIds;
    END;

$function$;

Answer 2

Ejemplo de gráfico y datos de este script

Puede ser puro relacional con una función agregada. Esta implementación utiliza una tabla de path y una tabla de point . Ambas son geometrías. El punto es más fácil para crear datos de prueba con y para probar que una geografía genérica, pero debería ser fácil de adaptar.

create table path (
    path_text text primary key,
    path geometry(linestring) not null
);
create table point (
   point_text text primary key,
   point geometry(point) not null
);

Un tipo para mantener el estado de la función agregada:

create type mpath_mpoint as (
    mpath geometry(multilinestring),
    mpoint geometry(multipoint)
);

La función de construcción del estado:

create or replace function path_point_intersect (
    _i mpath_mpoint[], _e mpath_mpoint
) returns mpath_mpoint[] as $$

    with e as (select (e).mpath, (e).mpoint from (values (_e)) e (e)),
    i as (select mpath, mpoint from unnest(_i) i (mpath, mpoint))
    select array_agg((mpath, mpoint)::mpath_mpoint)
    from (
        select
            st_multi(st_union(i.mpoint, e.mpoint)) as mpoint,
            (
                select st_collect(gd)
                from (
                    select gd from st_dump(i.mpath) a (a, gd)
                    union all
                    select gd from st_dump(e.mpath) b (a, gd)
                ) s
            ) as mpath
        from i inner join e on st_intersects(i.mpoint, e.mpoint)

        union all
        select i.mpoint, i.mpath
        from i inner join e on not st_intersects(i.mpoint, e.mpoint)

        union all
        select e.mpoint, e.mpath
        from e
        where not exists (
            select 1 from i
            where st_intersects(i.mpoint, e.mpoint)
        )
    ) s;
$$ language sql;

El agregado:

create aggregate path_point_agg (mpath_mpoint) (
    sfunc = path_point_intersect,
    stype = mpath_mpoint[]
);

Esta consulta devolverá un conjunto de cadenas multilinestring, multipoint contienen las rutas / puntos coincidentes:

select st_astext(mpath), st_astext(mpoint)
from unnest((
    select path_point_agg((st_multi(path), st_multi(mpoint))::mpath_mpoint)
    from (
        select path, st_union(point) as mpoint
        from
            path 
            inner join
            point on st_intersects(path, point)
        group by path
    ) s
)) m (mpath, mpoint)
;
                         st_astext                         |          st_astext          
-----------------------------------------------------------+-----------------------------
 MULTILINESTRING((-10 0,10 0,8 3),(0 -10,0 10),(2 1,4 -1)) | MULTIPOINT(0 0,0 5,3 0,5 0)
 MULTILINESTRING((-9 -8,4 -8),(-8 -9,-8 6))                | MULTIPOINT(-8 -8,2 -8)
 MULTILINESTRING((-7 -4,-3 4,-5 6))                        | MULTIPOINT(-6 -2)

Answer 3

Su función puede ser radicalmente simplificada.

Preparar

Le sugiero que convierta la paths.path la columna. paths.path a la geography tipo de datos (o al menos la geometry ). path es un tipo de Postgres nativo y no funciona bien con las funciones de PostGIS y los índices espaciales. Tendría que convertir path::geometry o path::geometry::geography (que resulta en un LINESTRING internamente ) para que funcione con las funciones de PostGIS como ST_Intersects() .

Mi respuesta se basa en estas tablas adaptadas:

CREATE TABLE paths (
   id uuid PRIMARY KEY
 , path geography NOT NULL
);

CREATE TABLE geographies (
   id uuid PRIMARY KEY
 , geography geography NOT NULL
 , fk_id text NOT NULL
);

Todo funciona con la geometry tipo de datos para ambas columnas también. geography es generalmente más exacta pero también más cara. ¿Cuál usar? Lea las preguntas frecuentes de PostGIS aquí.

Solución 1: Su función optimizada

CREATE OR REPLACE FUNCTION public.function_name(_fk_ids text[])
  RETURNS TABLE(id uuid, type text) AS
$func$
DECLARE
   _row_ct int;
   _loop_ct int := 0;

BEGIN
   CREATE TEMP TABLE _geo ON COMMIT DROP AS  -- dropped at end of transaction
   SELECT DISTINCT ON (g.id) g.id, g.geography, _loop_ct AS loop_ct -- dupes possible?
   FROM   geographies g
   WHERE  g.fk_id = ANY(_fk_ids);

   GET DIAGNOSTICS _row_ct = ROW_COUNT;

   IF _row_ct = 0 THEN  -- no rows found, return empty result immediately
      RETURN;           -- exit function
   END IF;

   CREATE TEMP TABLE _path ON COMMIT DROP AS
   SELECT DISTINCT ON (p.id) p.id, p.path, _loop_ct AS loop_ct
   FROM   _geo  g
   JOIN   paths p ON ST_Intersects(g.geography, p.path);  -- no dupes yet

   GET DIAGNOSTICS _row_ct = ROW_COUNT;

   IF _row_ct = 0 THEN  -- no rows found, return _geo immediately
      RETURN QUERY SELECT g.id, text ''geo'' FROM _geo g;
      RETURN;   
   END IF;

   ALTER TABLE _geo  ADD CONSTRAINT g_uni UNIQUE (id);  -- required for UPSERT
   ALTER TABLE _path ADD CONSTRAINT p_uni UNIQUE (id);

   LOOP
      _loop_ct := _loop_ct + 1;

      INSERT INTO _geo(id, geography, loop_ct)
      SELECT DISTINCT ON (g.id) g.id, g.geography, _loop_ct
      FROM   _paths      p
      JOIN   geographies g ON ST_Intersects(g.geography, p.path)
      WHERE  p.loop_ct = _loop_ct - 1   -- only use last round!
      ON     CONFLICT ON CONSTRAINT g_uni DO NOTHING;  -- eliminate new dupes

      EXIT WHEN NOT FOUND;

      INSERT INTO _path(id, path, loop_ct)
      SELECT DISTINCT ON (p.id) p.id, p.path, _loop_ct
      FROM   _geo  g
      JOIN   paths p ON ST_Intersects(g.geography, p.path)
      WHERE  g.loop_ct = _loop_ct - 1
      ON     CONFLICT ON CONSTRAINT p_uni DO NOTHING;

      EXIT WHEN NOT FOUND;
   END LOOP;

   RETURN QUERY
   SELECT g.id, text ''geo''  FROM _geo g
   UNION ALL
   SELECT p.id, text ''path'' FROM _path p;

END
$func$  LANGUAGE plpgsql;

Llamada:

SELECT * FROM public.function_name(''{foo,bar}'');

Mucho más rápido de lo que tienes.

Puntos principales

• Basó las consultas en todo el conjunto, en lugar de las últimas adiciones al conjunto solamente. Esto se vuelve cada vez más lento con cada bucle sin necesidad. loop_ct un contador de bucle ( loop_ct ) para evitar el trabajo redundante .

• Asegúrese de tener índices GiST espaciales en geographies.geography y paths.path :

  CREATE INDEX geo_geo_gix ON geographies USING GIST (geography);
  CREATE INDEX paths_path_gix ON paths USING GIST (path);

  Dado que las exploraciones de índice solo de Postgres 9.5 serían una opción para los índices GiST. Puede agregar id como segunda columna de índice. El beneficio depende de muchos factores, tendrías que probar. Sin embargo , no hay una clase GiST de operador de ajuste para el tipo uuid . Funcionaría con bigint después de instalar la extensión btree_gist :

  • Índice de columnas múltiples de Postgres (entero, booleano y matriz)
  • Índice de columnas múltiples en 3 campos con tipos de datos heterogéneos

• g.fk_id tiene un índice de ajuste en g.fk_id . De nuevo, un índice de (fk_id, id, geography) en (fk_id, id, geography) podría pagar si puede obtener escaneos de solo índice. El índice de btree predeterminado, fk_id debe ser la primera columna de índice. Especialmente si ejecuta la consulta con frecuencia y rara vez actualiza la tabla y las filas de la tabla son mucho más anchas que el índice.

• Puede inicializar variables en el momento de la declaración. Solo es necesario una vez después de la reescritura.

• ON COMMIT DROP elimina automáticamente las tablas temporales al final de la transacción. Así que quité las tablas que caen explícitamente. Pero obtienes una excepción si llamas a la función en la misma transacción dos veces. En la función, verificaría la existencia de la tabla temporal y utilizaré TRUNCATE en este caso. Relacionado:

  • Cómo verificar si una tabla existe en un esquema dado

• Use GET DIAGNOSTICS para obtener el recuento de filas en lugar de ejecutar otra consulta para el recuento.

  • Contar filas afectadas por BORRAR

  No es necesario contar en absoluto después de la reescritura. Cheaply check FOUND es suficiente.
  En realidad, necesitas GET DIAGNOSTICS . CREATE TABLE no establece FOUND (como se indica en el manual). Tuve tu INSERT en mi función original (probada) que establece FOUND , por lo tanto, la supervisión. Arreglado ahora.

• Es más rápido agregar un índice o una restricción PK / UNIQUE después de llenar la tabla. Y no antes de que realmente lo necesitamos.

• ON CONFLICT ... DO ... es la forma más sencilla y económica de UPSERT desde Postgres 9.5.

  • ¿Cómo PONER EN MARCHA (MERGE, INSERTAR ... ACTUALIZAR DUPLICADO) en PostgreSQL?

  Para la forma simple del comando, simplemente se enumeran columnas o expresiones de índice (como ON CONFLICT (id) DO ... ) y se permite que Postgres realice una inferencia de índice única para determinar una restricción o índice de árbitro. Más tarde optimicé proporcionando la restricción directamente. Pero para esto necesitamos una restricción real: un índice único no es suficiente. Se corrige en consecuencia. Detalles en el manual aquí.

• Puede ayudar a ANALYZE las tablas temporales manualmente para ayudar a Postgres a encontrar el mejor plan de consulta. (Pero no creo que lo necesites en tu caso).

  • ¿Se siguen recomendando ANÁLISIS DE VACÍO con regularidad según 9.1?

• _geo_ct - _geographyLength > 0 es una manera torpe y costosa de decir _geo_ct > _geographyLength . Pero eso se ha ido completamente ahora.

• No cites el nombre del idioma. Sólo el LANGUAGE plpgsql .

• Su parámetro de función es varchar[] para una matriz de fk_id , pero luego comentó:

  Es un campo bigint que representa un área geográfica (en realidad es una identificación de s2cell precomputada en el nivel 15).

  No sé el ID de s2cell en el nivel 15 , pero lo ideal es que pase una matriz de tipo de datos coincidentes, o si esa no es una opción predeterminada para el text[] .

  También desde que comentaste:

  Siempre hay exactamente 13 fk_id s pasados.

  Esto parece ser un caso de uso perfecto para un parámetro de función VARIADIC . Entonces tu definición de función sería:

  CREATE OR REPLACE FUNCTION public.function_name(_fk_ids VARIADIC text[]) ...

  Detalles:

  • Pase múltiples valores en un solo parámetro

Solución 2: SQL simple con CTE recursivo

Es difícil envolver un rCTE alrededor de dos bucles alternos, pero es posible con algo de delicadeza de SQL:

WITH RECURSIVE cte AS (
   SELECT g.id, g.geography::text, NULL::text AS path, text ''geo'' AS type
   FROM   geographies g
   WHERE  g.fk_id = ANY($kf_ids)  -- your input array here

   UNION
   SELECT p.id, g.geography::text, p.path::text
        , CASE WHEN p.path IS NULL THEN ''geo'' ELSE ''path'' END AS type
   FROM   cte              c
   LEFT   JOIN paths       p ON c.type = ''geo''
                            AND ST_Intersects(c.geography::geography, p.path)
   LEFT   JOIN geographies g ON c.type = ''path''
                            AND ST_Intersects(g.geography, c.path::geography)
   WHERE (p.path IS NOT NULL OR g.geography IS NOT NULL)
   )
SELECT id, type FROM cte;

Eso es todo. Necesitas los mismos índices que arriba. Puede envolverlo en una función SQL o PL / pgSQL para uso repetido.

Principales puntos adicionales

• La text a text es necesaria porque el tipo de geography no es "hashable" (igual para la geometry ). ( Consulte este tema abierto de PostGIS para obtener más información ) . Resuelva el problema convirtiéndolo en text . Las filas son únicas en virtud de (id, type) solo, podemos ignorar las columnas de geography para esto. Reparto a la geography para la unión. No debería costar demasiado extra.

• Necesitamos dos LEFT JOIN para no excluir filas, porque en cada iteración solo una de las dos tablas puede contribuir con más filas.
  La condición final asegura que no hayamos terminado, sin embargo:

  WHERE (p.path IS NOT NULL OR g.geography IS NOT NULL)

  Esto funciona porque los resultados duplicados se excluyen de la tabla intermedia temporal. El manual:

  Para UNION (pero no UNION ALL ), descarte filas y filas duplicadas que dupliquen cualquier fila de resultados anterior. Incluya todas las filas restantes en el resultado de la consulta recursiva, y también colóquelas en una tabla intermedia temporal.

Entonces, ¿cuál es más rápido?

El rCTE es probablemente más rápido que la función para pequeños conjuntos de resultados. Las tablas temporales y los índices en la función significan una sobrecarga considerablemente mayor. Sin embargo, para conjuntos de resultados grandes, la función puede ser más rápida. Solo las pruebas con su configuración real pueden darle una respuesta definitiva. *
* Ver los comentarios del OP en el comentario .