Come posso estendere questa query SQL per trovare i k vicini più vicini?

Question

Ho un database pieno di dati bidimensionali - punti su una mappa. Ogni record ha un campo del tipo di geometria. Quello che devo essere in grado di fare è passare un punto a una stored procedure che restituisce i punti più vicini a k (k verrebbe passato anche a sproc, ma è facile). Ho trovato una query al http://blogs.msdn.com/isaac/archive/2008/10/23/nearest-neighbors.aspx che ottiene il singolo vicino più vicino, ma non riesco a capire come estenderlo per trovare i vicini più vicini k.

Questa è la query corrente - T è la tabella, g è il campo della geometria, @x è il punto a cercare in giro, Numbers è una tabella con i numeri interi 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 

L'interno query seleziona la regione non vuota più vicina e la query esterna seleziona quindi il risultato migliore da quella regione; la query esterna può essere facilmente modificata in (ad esempio) SELECT TOP(20), ma se la regione più vicina contiene solo un risultato, sei bloccato con quello. c'e' -

ho dato probabilmente ho bisogno di cercare in modo ricorsivo per la prima regione contenente k dischi, ma senza l'utilizzo di una variabile di tabella (che causerebbe problemi di manutenzione, come è necessario creare la struttura della tabella ed è suscettibile di cambiare molti campi), non riesco a vedere come.

Answer 1

Cosa succede se si rimuove TOP (1) WITH TIES dalla query interna e si imposta la query esterna per restituire le prime righe k?

Sarei anche interessato a sapere se questo emendamento aiuta affatto. Dovrebbe essere più efficiente rispetto all'utilizzo di 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 - non provato - non ho accesso a SQL 2008 qui.

Answer 2

Citato da Inside Microsoft® SQL Server® 2008: T-SQL Programming. Sezione 14.8.4.

la seguente query restituirà i 10 punti di interesse più vicino a @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; 

Nota: Solo una parte della clausola WHERE di questa domanda è sostenuta dalla spaziale dell'indice . Tuttavia, query optimizer valuta correttamente la parte supportata (il confronto "<") utilizzando l'indice. Questo limita il numero di righe per che la parte "> =" deve essere testata, e la query ha buone prestazioni. Modificando , il valore di @start può a volte aumentare la query se è più lento di .

Listing 2-1. Creazione e popolamento di una tabella ausiliaria di numeri

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;