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

Question

我有一个充满二维数据的数据库 - 地图上的点.每条记录都有一个几何类型的字段.我需要做的是将一个点传递给一个返回k个最近点的存储过程(k也会传递给sproc,但这很容易).我在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。