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

Question

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

这是当前的查询 - T是表，g是几何字段，@x是指向搜索周围，Numbers是整数的表1至Ñ：

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)，但是如果最近的区域只包含一个结果，那么您就会被困住。

我想我可能需要递归搜索第一个包含记录的区域，但是不使用表变量很多领域），我看不出如何。

Answer 1

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

我也很想知道这个修正是否有帮助。这应该是比使用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这里访问。

Answer 2

从Inside Microsoft® SQL Server® 2008: T-SQL Programming引用。第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;