Как я могу расширить этот SQL-запрос для нахождения k ближайших соседей?
У меня есть база данных, полная двумерных данных - указывает на карте. Каждая запись имеет поле типа геометрии. То, что я должен смочь сделать, передать точку хранимой процедуре, которая возвращается, k ближайшие точки (k был бы также передан sproc, но это легко). Я нашел запрос по http://blogs.msdn.com/isaac/archive/2008/10/23/nearest-neighbors.aspx, который получает единственного ближайшего соседа, но я не могу изобразить, как расширить его для нахождения k ближайших соседей.
Это - текущий запрос - T таблица, g поле геометрии, @x точка должна искать вокруг, Numbers таблица с целыми числами 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
Внутренний запрос выбирает ближайший непустой регион, и внешний запрос затем выбирает главный результат того региона; внешний запрос может легко быть изменен на (например). SELECT TOP(20), но если ближайший регион только содержит один результат, Вы застреваете с этим.
Я полагаю, что, вероятно, должен рекурсивно искать первый регион, содержащий k записи, но не используя табличную переменную (который вызвал бы проблемы обслуживания, поскольку необходимо создать структуру таблицы, и склонно измениться - существует много полей), я не вижу как.
2 ответа
Что произойдет, если вы удалите 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.
Цитируется из Inside Microsoft® SQL Server® 2008: Программирование T-SQL. Раздел 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;