29. 最近邻搜索

29.1. 什么是最近邻搜索？

一个常见的空间查询是：“<查询要素> 附近最近的 <候选要素> 是什么？”

与距离搜索不同，“最近邻”搜索不包含任何限制候选几何体距离的度量，任何距离的要素都将被接受，只要它们是最近的。

PostgreSQL 通过引入一个“按距离排序”（<->）运算符来解决最近邻问题，该运算符促使数据库使用索引来加速排序后的返回集。有了“按距离排序”运算符，最近邻查询只需添加排序并限制结果集到 N 个条目，即可返回“N 个最近的要素”。

“按距离排序”运算符适用于几何和地理类型。它们在两种类型之间工作方式的唯一区别是返回的距离值。对于几何 <-> 返回与 ST_Distance 相同的答案，该答案取决于所用空间参考系统的单位。对于地理，返回的距离值是球面距离，而不是 ST_Distance(geography,geography) 返回的更准确的椭球距离。

以下是距离“Broad St”地铁站最近的 3 条街道

-- Get the geometry of Broad St
SELECT ST_AsEWKT(geom, 1)
FROM nyc_subway_stations
WHERE name = 'Broad St';

SRID=26918;POINT(583571.9 4506714.3)

-- Plug the geometry into a nearest-neighbor query
SELECT streets.gid, streets.name,
  ST_Transform(streets.geom, 4326),
  streets.geom <-> 'SRID=26918;POINT(583571.9 4506714.3)'::geometry AS dist
FROM
  nyc_streets streets
ORDER BY
  dist
LIMIT 3;

  gid  |   name    |        dist
-------+-----------+--------------------
 17385 | Wall St   |  0.749987508809928
 17390 | Broad St  | 0.8836306235191059
 17436 | Nassau St | 1.3368280241070414

我们如何确保我们正在获得索引辅助的查询？检查最近邻查询的 EXPLAIN 输出是一个好主意，因为有可能从非索引的 SQL 中获得正确答案，并且在表大小扩展之前，索引的缺乏可能并不明显。

这是 EXPLAIN 的输出，请注意按顺序扫描索引

                              QUERY PLAN
---------------------------------------------------------------------------------
Limit  (cost=0.28..79.58 rows=3 width=31)
   ->  Index Scan using nyc_streets_geom_idx on nyc_streets streets
       (cost=0.28..504685.12 rows=19091 width=31)
         Order By:
         (geom <-> '0101000020266900000EEBD4CF27CF2141BC17D69516315141'::geometry)

29.2. 最近邻连接

索引辅助的按顺序排序运算符有一个主要缺点：它只适用于运算符一侧的单个几何文字。这对于查找与一个查询对象最近的对象来说很好，但对于空间连接没有帮助，空间连接的目标是为一组完整的候选对象中的每一个找到最近的邻居。

幸运的是，SQL 语言有一个功能允许我们重复运行一个由循环驱动的查询：LATERAL 连接。

在这里，我们将找到距离每个地铁站最近的街道

SELECT subways.gid AS subway_gid,
       subways.name AS subway,
       streets.name AS street,
       streets.gid AS street_gid,
       streets.geom::geometry(MultiLinestring, 26918) AS street_geom,
       streets.dist
FROM nyc_subway_stations subways
CROSS JOIN LATERAL (
  SELECT streets.name, streets.geom, streets.gid, streets.geom <-> subways.geom AS dist
  FROM nyc_streets AS streets
  ORDER BY dist
  LIMIT 1
) streets;

请注意 CROSS JOIN LATERAL 充当由地铁表驱动的循环的内部部分。地铁表中的每个记录都会被逐一馈送到横向子查询中，因此您会为每个地铁记录获得一个最近的结果。

此解释展示了地铁站的循环，以及循环内部的索引辅助排序，我们希望它在那里。

                           QUERY PLAN
-------------------------------------------------------------------------
 Nested Loop  (cost=0.28..13140.71 rows=491 width=37)
   ->  Seq Scan on nyc_subway_stations subways
       (cost=0.00..15.91 rows=491 width=46)
   ->  Limit
       (cost=0.28..1.71 rows=1 width=170)
         ->  Index Scan using nyc_streets_geom_idx on nyc_streets streets
             (cost=0.28..27410.12 rows=19091 width=170)
                Order By: (geom <-> subways.geom)