在PgSql中，查找大型数据集中最近的相邻项的最佳查询是什么？

Question

我有一张巨大的表 (约 4000 万行)，名为 nearest_spot，表示线条 (以 linestring 格式表示) 和它们最近的地点 (存储在另一个表中有大约 1500 个不同的地点)。nearest_spot 表如下所示：

 data_id || spot_id || spot_name || link_geom 

其中 data_id 是主键，spot_id 是指向 spot 表主键的外键，spot_name 是地点名称 (我知道冗余不好，但我不能修改数据库)，link_geom 是线的坐标。

---

数据库是 PostgreSQL 10.6、PostGIS 2.5，link_geom 列有一项 gist 索引，并且已对 nearest_spot 表进行了 VACUUM ANALYZE。

我的目标是尽可能快地找到数据记录中最近的邻居 (在此表中)。

我已经知道如何找到最近的邻居，我的问题是找到它所需的时间。我对 PostgreSQL 和 PostGIS 还比较新，一直在阅读它们的文档，浏览很多关于 KNN 优化的话题，我一直在寻找最有效的答案，但即使只搜索一行，也无法在 5 分钟内得出结果 (有时甚至高达 30 分钟)。我尝试了以下不同的查询：

SELECT *
FROM( SELECT A.position, B.spot_id
      FROM data A, nearest_spot B
      WHERE A.id = 1
      AND ST_DWithin(A.position,B.link_geom,20)
      ORDER BY A.position <-> B.link_geom
      LIMIT 10;)
ORDER BY ST_Distance(A.position,B.link_geom)
LIMIT 1;

SELECT *
FROM( SELECT A.position, B.spot_id
      FROM data A, nearest_spot B
      WHERE A.id = 1
      AND ST_Buffer(A.position,20) && B.link_geom
      ORDER BY A.position <-> B.link_geom
      LIMIT 10;)
ORDER BY ST_Distance(A.position,B.link_geom)
LIMIT 1;

SELECT *
FROM( SELECT A.position, B.spot_id
      FROM data A, nearest_spot B
      WHERE A.id = 1
      AND ST_Intersects(ST_Buffer(A.position,20), B.link_geom)
      ORDER BY A.position <-> B.link_geom
      LIMIT 10;)
ORDER BY ST_Distance(A.position,B.link_geom)
LIMIT 1;

我之所以首先使用 <-> 运算符，然后再使用 ST_Distance，是因为根据PostGIS的文档，<->运算符速度更快但精度较低（对于边界框），而ST_Distance更准确但速度较慢。

我还参考了PostGIS的这篇有关空间索引的文档，以及这篇有关<->运算符的文档。 编辑:我意识到所有的坐标都是作为几何图形（SRID 4326）存储的，因此ST_DWithin调用虽然语法正确，但返回的所有行都不在20米范围内，而是在地球的20度范围内，所以实际上我的ST_DWithin没有缩小结果集的大小，这可能是导致耗时如此之长的最大原因之一，ST_Buffer也是如此。我将尝试在使用米之前将所有坐标转换为地理坐标（使用:: geography），希望能看到改进。

- Adrien

Answer 1

看起来这个表格有大量的重复数据（每行数据重复了大约1800次），给我这个表格的人完全不知道。删除重复数据后，查询时间问题解决了。

- Adrien

Answer 2

需要由数据库完成吗？我认为最快的方法可能是将这1500个点加载到空间索引中，例如KD-Tree、四叉树或R-Tree。然后迭代遍历这4000万个点，并在索引中搜索最近的邻居。

不需要太多的努力，您应该能够每秒执行100,000到500,000个最近邻搜索，因此40M个最近邻搜索大约需要2到5分钟。

- TilmannZ

---

PostGIS 提供了空间索引。 - inc42

@inc42 是的，OP甚至写道他们使用了PostGIS空间索引，但显然速度太慢了。我不确定你的观点是什么？ - TilmannZ

我不确定您使用与PostGIS提供的不同空间索引和数据结构所想象的性能优势是什么。为什么这比经过充分测试和证明的空间数据库更快呢？ - inc42

请纠正我，但是PostGIS是PostgreSQL的插件/扩展/...，它是一个关系型数据库。这意味着它带有大量的开销来管理ACID行为、查询处理、表到内存对象映射，以及最可能的磁盘I/O。因此，我建议使用一些经过充分测试和证明的内存空间索引，而不是一个经过充分测试和证明的DBMS（带有所有不必要的DBMS开销）。为什么那样不会更快呢？ - TilmannZ

你会感到惊讶的，我想。 - inc42

请纠正我如果我错了，但是PostGIS内部使用了空间索引。您能否解释一下为什么直接使用空间索引（如我所提出的）不应该比使用包含大量逻辑的包装器（如PostGIS）通过空间索引更快？ 如果您知道我不知道的东西，如果您可以分享一些事实或见解，那将非常有帮助。只是在这里给出没有解释的意见并不是很有帮助，所以您能否请解释一下这应该如何和为什么可能成立？ - TilmannZ