How Can I Extend This Sql Query To Find The K Nearest Neighbors?

I have a database full of two-dimensional data - points on a map. Each record has a field of the geometry type. What I need to be able to do is pass a point to a stored procedure w

Solution 1:

What happens if you remove TOP (1) WITH TIES from the inner query, and set the outer query to return the top k rows?

I'd also be interested to know whether this amendment helps at all. It ought to be more efficient than using TOP:

DECLARE@startFLOAT=1000
        ,@kINT=20
        ,@pFLOAT=2;

WITH NearestPoints AS
(
     SELECT*
            ,T.g.STDistance(@x) AS dist
            ,ROW_NUMBER() OVER (ORDERBY 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=0OR T.g.STDistance(@x) >=@start*POWER(@p,Numbers.n -1)
         )
)
SELECT*FROM NearestPoints
WHERE rn <=@k;

NB - untested - I don't have access to SQL 2008 here.

Solution 2:

Quoted from Inside Microsoft® SQL Server® 2008: T-SQL Programming. Section 14.8.4.

The following query will return the 10 points of interest nearest to @input:

DECLARE@input GEOGRAPHY ='POINT (-147 61)';
DECLARE@startFLOAT=1000;
WITH NearestNeighbor AS(
  SELECT TOP 10WITH TIES
    *, b.GEOG.STDistance(@input) AS dist
  FROM Nums n JOIN GeoNames b WITH(INDEX(geog_hhhh_16_sidx)) -- index hintON b.GEOG.STDistance(@input) <@start*POWER(CAST(2ASFLOAT),n.n)
  AND b.GEOG.STDistance(@input) >=CASEWHEN n =1THEN0ELSE@start*POWER(CAST(2ASFLOAT),n.n-1) ENDWHERE n <=20ORDERBY n
)
  SELECT TOP 10 geonameid, name, feature_code, admin1_code, dist
  FROM NearestNeighbor
  ORDERBY n, dist;

Note: Only part of this query’s WHERE clause is supported by the spatial index. However, the query optimizer correctly evaluates the supported part (the "<" comparison) using the index. This restricts the number of rows for which the ">=" part must be tested, and the query performs well. Changing the value of @start can sometimes speed up the query if it is slower than desired.

Listing 2-1. Creating and Populating Auxiliary Table of Numbers

SET NOCOUNT ON;
USE InsideTSQL2008;

IF OBJECT_ID('dbo.Nums', 'U') ISNOTNULLDROPTABLE dbo.Nums;

CREATETABLE dbo.Nums(n INTNOTNULLPRIMARY KEY);
DECLARE@maxASINT, @rcASINT;
SET@max=1000000;
SET@rc=1;

INSERTINTO Nums VALUES(1);
WHILE @rc*2<=@maxBEGININSERTINTO dbo.Nums SELECT n +@rcFROM dbo.Nums;
  SET@rc=@rc*2;
ENDINSERTINTO dbo.Nums
  SELECT n +@rcFROM dbo.Nums WHERE n +@rc<=@max;