如何扩展这个SQL查询以查找k个最近的邻居？

Question

我有一个数据库，里面装满了二维数据——地图上的点。每个记录都有一个几何类型的字段。我需要能够将一个点传递给存储过程，该存储过程返回最近的k个点（k也将传递给存储过程，但这很容易）。我在http://blogs.msdn.com/isaac/archive/2008/10/23/nearest-neighbors.aspx找到了一个查询，可以获得单个最近的邻居，但我不知道如何扩展它以找到k个最近的邻居。

这是当前的查询 - T是表，g是几何字段，@x是要搜索周围的点，Numbers是包含1到n的整数的表：

DECLARE @start FLOAT = 1000; 
WITH NearestPoints AS
(
     SELECT TOP(1) WITH TIES *,  T.g.STDistance(@x) AS dist
     FROM Numbers JOIN T WITH(INDEX(spatial_index)) 
     ON T.g.STDistance(@x) < @start*POWER(2,Numbers.n)
     ORDER BY n
)
SELECT TOP(1) * FROM NearestPoints
ORDER BY n, dist

内部查询选择最近的非空区域，外部查询从该区域中选择顶部结果；外部查询可以轻松更改为（例如）SELECT TOP(20)，但如果最近的区域只包含一个结果，则必须使用该结果。

我认为我可能需要递归地搜索包含k条记录的第一个区域，但是如果不使用表变量（这会导致维护问题，因为您必须创建表结构并且它容易更改 - 有很多字段），我看不到如何实现。

- Smigs

---

当查找k条记录时，将INNER查询更改为TOP（1）以上会对结果产生什么影响？（当最近的区域只包含一个结果时） - kevchadders

如果您将内部查询更改为选择更多的区域，您可以获得更多的结果，但这并不_保证_获得更多的结果：其他区域可能只包含相同的单个结果（它们的大小呈指数增长）- 例如，在一个附近只有一个点，但周围几百公里没有其他点的点周围搜索- 前_n_个区域将只包含相同的1个点。 - Smigs

有没有找到解决方案？我也在寻找同样的解决方案。 - Richard West

Answer 1

如果从内部查询中删除 TOP (1) WITH TIES 并将外部查询设置为返回前 k 行，会发生什么？

我也想知道这个修改是否有所帮助。它应该比使用 TOP 更有效率。

DECLARE @start FLOAT = 1000
        ,@k INT = 20
        ,@p FLOAT = 2;

WITH NearestPoints AS
(
     SELECT *
            ,T.g.STDistance(@x) AS dist
            ,ROW_NUMBER() OVER (ORDER BY T.g.STDistance(@x)) AS rn
     FROM Numbers 
     JOIN T WITH(INDEX(spatial_index)) 
     ON   T.g.STDistance(@x) <  @start*POWER(@p,Numbers.n)
     AND (Numbers.n - 1 = 0 
          OR T.g.STDistance(@x) >= @start*POWER(@p,Numbers.n - 1)
         )
)
SELECT * 
FROM NearestPoints
WHERE rn <= @k;

NB - 未经测试 - 我这里没有访问 SQL 2008 的权限。

- Ed Harper

---

@Smigs - 试试我所做的修改 - 或许有一个隐式的 int 转换 (虽然我看不到)。 - Ed Harper

这是源查询中的错误 - POWER 返回其第一个参数的数据类型（常量2被解释为 INT）。修改了我的查询以反映这一点。 - Ed Harper

@Ed Harper，这在某种程度上是有效的，如果将k设置为例如40，则会返回40个点。但是，如果分散在多个区域中，则返回重复项，因为区域n包含区域n-1中的所有点。当然，这些之后可以被过滤掉（记录具有ID字段），但是这样就会少于k点！不过，似乎比使用“TOP”要快！ - Smigs

@Smigs - 我认为原始查询除了k=1之外的任何值都不能按照广告所述工作 - 这是这种方法的根本问题。为了避免这种情况，内部查询需要排除已经搜索过的所有先前组的内容。这应该是可能的，但我现在没有时间去看它（基本上，连接中的ON语句需要考虑一个下限和一个上限，而不仅仅是一个上限）。 - Ed Harper

@Smigs - 我又做了一次修改以反映我的先前注释。 - Ed Harper

Answer 2

引用自《Inside Microsoft® SQL Server® 2008：T-SQL编程》，第14.8.4节。

以下查询将返回距离@input最近的10个兴趣点：

DECLARE @input GEOGRAPHY = 'POINT (-147 61)';
DECLARE @start FLOAT = 1000;
WITH NearestNeighbor AS(
  SELECT TOP 10 WITH TIES
    *, b.GEOG.STDistance(@input) AS dist
  FROM Nums n JOIN GeoNames b WITH(INDEX(geog_hhhh_16_sidx)) -- index hint
  ON b.GEOG.STDistance(@input) < @start*POWER(CAST(2 AS FLOAT),n.n)
  AND b.GEOG.STDistance(@input) >=
    CASE WHEN n = 1 THEN 0 ELSE @start*POWER(CAST(2 AS FLOAT),n.n-1) END
  WHERE n <= 20
  ORDER BY n
)
  SELECT TOP 10 geonameid, name, feature_code, admin1_code, dist
  FROM NearestNeighbor
  ORDER BY n, dist;

注意：此查询的WHERE子句只有部分被空间索引支持。然而，查询优化器正确地使用索引评估了被支持部分（"<"比较）。这限制了必须测试的">="部分的行数，使查询表现良好。如果查询速度较慢，更改@start的值有时可以加快查询速度。

清单2-1. 创建和填充数字辅助表

SET NOCOUNT ON;
USE InsideTSQL2008;

IF OBJECT_ID('dbo.Nums', 'U') IS NOT NULL DROP TABLE dbo.Nums;

CREATE TABLE dbo.Nums(n INT NOT NULL PRIMARY KEY);
DECLARE @max AS INT, @rc AS INT;
SET @max = 1000000;
SET @rc = 1;

INSERT INTO Nums VALUES(1);
WHILE @rc * 2 <= @max
BEGIN
  INSERT INTO dbo.Nums SELECT n + @rc FROM dbo.Nums;
  SET @rc = @rc * 2;
END

INSERT INTO dbo.Nums
  SELECT n + @rc FROM dbo.Nums WHERE n + @rc <= @max;

- Henry

---

我不再拥有测试这个答案所需的工具，因此我不确定是否应该将其标记为已接受的答案，对此感到抱歉！ - Smigs