如何扩展这个 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 记录的第一个区域，但不使用表变量（这会导致维护问题，因为您必须创建表结构并且它很容易发生变化 - 那里有很多字段），我不明白如何。

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;

注意 - 未经测试 - 我无法在这里访问 SQL 2008。

Answer 2

引自 Microsoft® SQL Server® 2008 内部：T-SQL 编程。第 14.8.4 节。

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

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;