如何递归地找到两个表之间的相交地理位置

Question

我正在运行Postgres 9.6.1和PostGIS 2.3.0 r15146并且有两个表.
geographies可能有150,000,000行,paths可能有10,000,000行:

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))

给定一个数组/套ids的表geographies,什么是查找所有交叉路径与几何的"最佳"的方式？

换句话说,如果一个初始geography有一个相应的交叉,path我们还需要找到这个相交的所有其他 .从那里,我们需要找到这些新发现的所有其他相交,依此类推,直到我们找到所有可能的交叉点.geographiespathpathsgeographies

初始地理标识(我们的输入)可以是0到700之间的任何位置.平均值大约为40.
最小交叉点将为0,最大值将为大约1000.平均值可能大约为20,通常小于100连接.

我创建了一个这样做的功能,但我是PostGIS中的GIS和Postgres的新手.我发布了我的解决方案作为这个问题的答案.

我觉得应该有比我想出的更有说服力和更快速的方式.

Answer 1

您的功能可以从根本上简化.

建立

我建议你将列转换paths.path为数据类型geography(或至少geometry).path是一种本地Postgres类型,与PostGIS函数和空间索引不兼容.您必须强制转换path::geometry或path::geometry::geography(在LINESTRING内部生成)使其适用于PostGIS等功能ST_Intersects().

我的答案基于这些改编的表格:

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
);

一切都适用geometry于两列的数据类型.geography通常更准确但也更昂贵.哪个用？阅读PostGIS常见问题解答.

解决方案1:优化您的功能

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;

呼叫:

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

很多比你有什么更快.

主要观点

• 您基于整个集合查询,而不是仅对集合的最新添加.每次循环都会变得越来越慢而不需要.我添加了一个循环计数器(loop_ct)以避免冗余工作.

• 确保在和上具有空间GiST 索引:geographies.geographypaths.path

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

  由于Postgres 9.5 仅索引扫描将是GiST索引的一个选项.您可以添加id为第二个索引列.好处取决于很多因素,你必须要测试.但是,该uuid类型没有适合的运算符GiST类.它可以bigint在安装扩展名btree_gist后使用:

  • Postgres多列索引(整数,布尔值和数组)
  • 具有异构数据类型的3个字段的多列索引

• 也有适合的指数g.fk_id.同样,(fk_id, id, geography)如果您可以从中获取仅索引扫描,那么多列索引可能会付费.默认的btree索引,fk_id必须是第一个索引列.特别是如果您经常运行查询并且很少更新表,并且表行比索引宽得多.

• 您可以在声明时初始化变量.重写后只需要一次.

• ON COMMIT DROP自动删除事务结束时的临时表.所以我明确地删除了丢弃表.但是,如果在同一事务中调用该函数两次,则会出现异常.在函数中,我将检查是否存在临时表,并TRUNCATE在这种情况下使用.有关:

  • 如何检查给定模式中是否存在表

• 使用GET DIAGNOSTICS获得的行数,而不是运行计数另一个查询.

  • 计算受DELETE影响的行

  重写后你根本不需要计算.便宜的检查FOUND就足够了.
  实际上,你需要GET DIAGNOSTICS.CREATE TABLE未设置FOUND(如手册中所列).我有你INSERT在我原来的(测试)函数不设置FOUND,因此监督.现在修复了.

• 填充表后,添加索引或PK/UNIQUE约束会更快.而不是在我们真正需要之前.

• ON CONFLICT ... DO ... 自Postgres 9.5以来,UPSERT是更简单,更便宜的方式.

  • 如何在PostgreSQL中UPSERT(MERGE,INSERT ...在DUPLICATE UPDATE上)？

  对于命令的简单形式,您只需列出索引列或表达式(如ON CONFLICT (id) DO ...),并让Postgres执行唯一索引推断以确定仲裁约束或索引.我后来通过直接提供约束进行了优化.但为此我们需要一个实际的约束 - 一个独特的索引是不够的.相应修正.手册中的详细信息在这里.

• 它可以帮助ANALYZE临时表人工帮助的Postgres找到最好的查询计划.(但我不认为你的情况需要它.)

  • 是否仍在9.1推荐常规VACUUM ANALYZE？

• _geo_ct - _geographyLength > 0是一种尴尬而且更昂贵的说法_geo_ct > _geographyLength.但现在已经完全消失了.

• 不要引用语言名称.只是LANGUAGE plpgsql.

• 您的函数参数是varchar[]针对数组的fk_id,但您稍后评论过:

  它是一个bigint代表地理区域的字段(它实际上是s2cell15级的预先计算的id).

  我不知道s2cell15级的id,但理想情况下你传递一个匹配数据类型的数组,或者如果那不是默认的选项text[].

  你也评论过:

  总共有13个fk_id传入.

  这似乎是VARIADIC函数参数的完美用例.所以你的函数定义是:

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

  细节:

  • 在单个参数中传递多个值

解决方案2:具有递归CTE的纯SQL

围绕两个交替循环包装rCTE很困难,但可能有一些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;

就这样.您需要与上面相同的索引.您可以将其包装到SQL或PL/pgSQL函数中以供重复使用.

主要补充点

• 演员text是必要的,因为geography类型不是"可散列的"(相同geometry).(有关详细信息,请参阅此打开的PostGIS问题.)通过转换来解决此问题text.行是独一无二的(id, type),我们可以忽略这一geography列.回到geography加入.不应该花费太多额外费用.

• 我们需要两个,LEFT JOIN所以不要排除行,因为在每次迭代时,只有两个表中的一个可以贡献更多的行.
  最后的条件确保我们没有完成,但是:

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

  这是有效的,因为从临时中间表中排除了重复的结果.手册:

  对于UNION(但不是UNION ALL),丢弃重复任何先前结果行的重复行和行.在递归查询的结果中包括所有剩余行,并将它们放在临时中间表中.

哪个更快？

rCTE可能比小结果集的功能更快.函数中的临时表和索引意味着更多的开销.但是,对于大型结果集,函数可能更快.只有使用您的实际设置进行测试才能给出明确的答案.*
*请参阅评论中的OP反馈.