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

Question

我有一个巨大的 table（大约 4000 万行），称为 nearest_spot，代表线（以线串格式）和它们最接近的点（大约有 1500 个不同的点，存储在另一个table)。 nearest_spot table 是这样的：

 data_id || spot_id || spot_name || link_geom

其中data_id是主键，spot_id是主键的外键spot table, spot_name 是 spot 名称（我知道冗余不好但我不允许修改数据库）和 link_geom是直线坐标。

数据库在 PostgreSQL 10.6、PostGIS 2.5 中，link_geom 列有一个要点索引，并且已经对 nearest_spot table.

我的目标是尽可能快地找到数据记录中某个点的最近邻居（在此 table）。

我已经知道如何找到最近的邻居，我的问题是找到它所花费的时间。我是 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 ORDER BY 的原因是，根据来自 PostGIS 的 documentation，<-> 更快但精度较低（对于边界框）而 ST_Distance 更精确但更慢。

关于 <-> 运算符，我也使用了这个 documentation about Spatial Indexing, and this one，它们也来自 PostGIS。

编辑： 我意识到我所有的坐标都存储为几何（SRID 4326），所以 ST_DWithin 调用虽然具有良好的语法，但返回的所有行不是20 米以内，但所有行都在 20 度（地球）以内，所以实际上我的 ST_DWithin 并没有使结果集变小，这可能是它的最大原因之一花了这么长时间，ST_Buffer 也是如此。在将它们与米一起使用之前，我会尝试将所有坐标转换为地理坐标（::geography），希望我会看到改进

Answer 1

需要数据库做吗？我认为最快的方法可能是加载将 1500 个点放入一个空间索引中，例如 KD-Tree、四叉树或 R-Tree。然后遍历 40M 个点并在索引中搜索最近的邻居。

不费吹灰之力，您应该能够每秒进行 100,000 到 500,000 次 NN 搜索，因此 40M NN 搜索大约需要 2 到 5 分钟。

Answer 2

看来 table 有大量重复项（每行重复了大约 1800 次），给我的人根本不知道。删除重复项后，查询时间不再有问题

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

What's the most optimal query in PgSql to find the nearest neighbor in a huge dataset?

postgresql

optimization

postgis

nearest-neighbor

knn