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

Question

我有一个巨大的表（约40万行），名为nearest_spot，表示行（以线串格式）和最接近的点（有大约1500个不同的点，存储在另一个表中）。 nearest_spot表是这样的：

 data_id || spot_id || spot_name || link_geom 

其中data_id是主键，spot_id是spot表主键的外键，spot_name是spot名称（我知道冗余不好但我不允许修改数据库）而link_geom就是这一行坐标。

---

该数据库位于PostgreSQL 10.6，PostGIS 2.5中，link_geom列有一个gist索引，并且最近的表已经完成了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进行ORDER BY的原因是根据PostGIS中的documentation，<->更快但不太精确（对于边界框），而ST_Distance更精确但更慢。

我也使用这个关于空间索引的documentation，以及关于one算子的<->，两者都来自PostGIS。

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

Answer 1

是否需要由数据库完成？我认为最快的方法可能是将1500个点加载到空间索引中，例如KD-Tree，quadtree或R-Tree。然后迭代40M点并搜索索引中最近的邻居。

没有太多努力，你应该能够每秒进行100,000到500,000次NN搜索，因此40M NN搜索大约需要2到5分钟。

Answer 2

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