Làm cách nào để mở rộng truy vấn SQL này để tìm k hàng xóm gần nhất?

Question

Tôi có một cơ sở dữ liệu đầy đủ các dữ liệu hai chiều - các điểm trên bản đồ. Mỗi bản ghi có một trường của loại hình. Những gì tôi cần để có thể làm là vượt qua một điểm đến một thủ tục lưu trữ mà trả về k điểm gần nhất (k cũng sẽ được thông qua để các sproc, nhưng đó là dễ dàng). Tôi đã tìm thấy truy vấn tại số http://blogs.msdn.com/isaac/archive/2008/10/23/nearest-neighbors.aspx để nhận được người hàng xóm gần nhất, nhưng tôi không thể tìm cách mở rộng nó để tìm các số hàng xóm gần nhất là k.

Đây là truy vấn hiện tại - T là bàn, g là lĩnh vực hình học, @x là điểm để tìm kiếm xung quanh, Numbers là một bảng với số nguyên 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 

Các nội truy vấn chọn vùng không trống gần nhất và truy vấn bên ngoài sau đó chọn kết quả trên cùng từ vùng đó; truy vấn bên ngoài có thể dễ dàng được thay đổi thành (ví dụ) SELECT TOP(20), nhưng nếu khu vực gần nhất chỉ chứa một kết quả, bạn sẽ bị mắc kẹt với điều đó.

Tôi có thể cần phải đệ quy tìm kiếm vùng đầu tiên có chứa k bản ghi, nhưng không sử dụng biến bảng (điều này sẽ gây ra sự cố bảo trì khi bạn phải tạo cấu trúc bảng và có thể thay đổi) lại rất nhiều lĩnh vực), tôi không thể thấy như thế nào.

Answer 1

Điều gì sẽ xảy ra nếu bạn xóa TOP (1) WITH TIES khỏi truy vấn bên trong và đặt truy vấn bên ngoài để trả về hàng đầu k hàng?

Tôi cũng muốn biết liệu sửa đổi này có giúp ích gì không. Nó phải hiệu quả hơn việc sử dụng 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 - chưa được kiểm tra - Tôi không có quyền truy cập SQL 2008 tại đây.

Answer 2

Trích dẫn từ Inside Microsoft® SQL Server® 2008: T-SQL Programming. Mục 14.8.4.

Các truy vấn sau đây sẽ trả lại 10 điểm đáng chú ý gần @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; 

Lưu ý: Chỉ có một phần của mệnh đề WHERE của truy vấn này được hỗ trợ bởi chỉ số không gian . Tuy nhiên, trình tối ưu hóa truy vấn đánh giá chính xác phần được hỗ trợ (so sánh "<") bằng cách sử dụng chỉ mục. Điều này hạn chế số hàng cho mà phần "> =" phải được kiểm tra, và truy vấn hoạt động tốt. Thay đổi giá trị của @start đôi khi có thể tăng tốc truy vấn nếu nó chậm hơn so với mong muốn.

Liệt kê 2-1. Tạo và điền bảng phụ số

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;