k 인접 노드를 찾기 위해이 SQL 쿼리를 어떻게 확장 할 수 있습니까?

Question

지도상의 2 차원 데이터 포인트로 가득 찬 데이터베이스가 있습니다. 각 레코드에는 기하학 유형 필드가 있습니다. 내가 할 수 있어야 할 점은 k 가장 가까운 점을 반환하는 저장 프로 시저에 포인트를 전달하는 것입니다 (k는 sproc에도 전달되지만 쉽습니다). http://blogs.msdn.com/isaac/archive/2008/10/23/nearest-neighbors.aspx에서 하나의 가장 가까운 이웃을 얻었습니다.하지만 이웃을 가장 가까운 이웃 k으로 확장하는 방법을 알 수 없습니다.

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 

내측에게 -

이 현재 쿼리이다 T 테이블이다 g 지오메트리 필드이다 @x는 점 Numbers 1 N에 정수를 표이다 주변 검색 할 쿼리는 가장 가까운 비어 있지 않은 영역을 선택하고 외부 쿼리는 그 영역에서 가장 높은 결과를 선택합니다. 외부 쿼리는 (예 : 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; 

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; 

참고 :이 쿼리의 조항의 일부만 공간 인덱스에 의해 지원됩니다 . 그러나 쿼리 최적화 프로그램 은 인덱스를 사용하여 지원되는 부분 ("<"비교)을 올바르게 평가합니다. 이렇게하면 "> ="부분을 테스트해야하는 의 행 수가 제한되고 이고 쿼리가 제대로 수행됩니다. 을 @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;