оптимизировать запрос ближайшего соседа на 70 миллионов облаков пространственных точек с чрезвычайно высокой плотностью на SQL Server 2008

Question

У меня около 75 миллионов записей в базе данных SQL Server 2008 R2 Express.Каждый - это длинный лат, соответствующий некоторому значению.Таблица имеет столбец географии.Я пытаюсь найти ближайшего соседа для данной широты и долготы (точка).У меня уже есть запрос с пространственным индексом на месте.Но в зависимости от того, где запись находится в базе данных, например, в первом или последнем квартале, запрос может занять от 3 до 30 секунд, чтобы найти ближайшего соседа.Я чувствую, что это может быть оптимизировано, чтобы дать намного более быстрый результат, оптимизируя запрос или пространственный индекс.Прямо сейчас применен некоторый пространственный индекс с настройками по умолчанию.Вот как выглядит моя таблица и запрос.

CREATE TABLE lidar(
    [id] [bigint] IDENTITY(1,1) NOT NULL,
    [POINTID] [int] NOT NULL,
    [GRID_CODE] [numeric](17, 8) NULL,
    [geom] [geography] NULL,
 CONSTRAINT [PK_lidar_1] PRIMARY KEY CLUSTERED ([id] ASC)
 WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, 
 ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]

Пространственный индекс, который я использую:

CREATE SPATIAL INDEX [SPATIAL_lidar] ON [dbo].[lidar] ([geom]) USING  GEOGRAPHY_GRID 
WITH (
GRIDS =(LEVEL_1 = MEDIUM,LEVEL_2 = MEDIUM,LEVEL_3 = MEDIUM,LEVEL_4 = MEDIUM), 
CELLS_PER_OBJECT = 16, PAD_INDEX  = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF,  
ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]

Вот запрос, который я использую:

declare @ms_at geography = 'POINT (-95.66 30.04)';
select TOP(1) nearPoints.geom.STAsText()as latlon 
from
(
select r.geom
from lidar r With(Index(SPATIAL_lidar))
where r.geom.STIntersects(@ms_at.STBuffer(1000)) = 1
) nearPoints

Вот пример лонг-лонгов в моей базе данных.дать представление о точности и плотности.Все 70 миллионов записей относятся к одному городу (данные Lidar)

POINT (-95.669434934023087 30.049513838913736)

Теперь этот запрос дает мне результаты, как я описал выше, но я хочу максимально повысить производительность.Я предполагаю, что, настроив значения пространственного индекса по умолчанию, я смогу улучшить производительность.Любые подсказки это?

Я попытался изменить буфер от 10 до 1000, но с почти такими же результатами.

Также приветствуются любые другие предложения по улучшению производительности.

Вот система, которую я сейчас использую:

Windows 7 64bit Professional
Intel(R) Core(TM)2 Quad CPU    Q9650  @ 3.00GHz (4 CPUs), ~3.0GHz
Ram: 8 GB
NVIDIA GeForce 9500 GT

Answer 1

Извините, но это не ответ SQL, а способ получения предсказуемой производительности с учетом определенных ограничений ваших данных.

Как часто данные меняются? Если возможно, не могли бы вы предварительно рассчитать график каждого объекта 5 ближайших соседей и использовать его для ускорения вашего выбора .?

Если эти данные в основном только для чтения, то ...

Насколько равномерно распределены эти точки? Если распределение достаточно равномерно и хорошо известно, то вы могли бы развернуть свое собственное пространственное отображение, поместив все координаты и индексы в хеш-таблицу.

Если вам не нужно хранить данные в базе данных, переместите их в файл с отображением в памяти для быстрого поиска хеша. (70м записи должны легко помещаться в памяти).

Я использую эту архитектуру для генерации поисков менее миллисекунды для отображения рекламы и релевантности поисковой системы.

== Разработка ==

Вы просто создаете сетку квадратов фиксированного размера (например, шахматную доску), и вы отображаете каждую точку в сетке, и вы создаете список объектов, которые принадлежат каждому из полей сетки - если вы настраиваете размер каждой ячейки должен составлять в среднем 5–50 точек на каждом квадрате. В принципе, это четырехугольное дерево, но без дерева для простоты.

Для каждого сегмента, который пуст после того, как вы разбросали все данные в сегментах, вы добавляете информацию о ближайших сегментах, содержащих данные.

Теперь вы можете нумеровать каждую группу слева-направо-строку-строку, чтобы каждый сегмент имел уникальный номер, который можно вычислить по координатам, и вы вставляете каждую группу в хеш-таблицу или, если пробел, разрешив так же, как прямую таблицу поиска.

Теперь, когда у вас есть запрос, вы просто вычисляете, к какому контейнеру он будет привязан, и вы получите либо список объектов в этом сегменте, либо вы получите «пустой» блок, содержащий указатели на ближайший блок. которые имеют содержание.

Это даст вам первый список кандидатов объектов, которые вы ищете, и теперь вам просто нужно просто запустить и посмотреть, какой из них ближе всего.

В 99% случаев это так и есть - но если вас это беспокоит, то (а) либо есть несколько единомышленников в соседних корзинах, которые на самом деле ближе, то просто проверьте 8 окружающих корзин и посмотрите, если найдешь там поближе.

Если теперь вы также хотите получить список всех ближайших объектов, то также рассчитайте простую сеть из 5 ближайших соседей для каждого объекта, так что вы получите структуру данных, подобную A -> {B, C, D, E, F}, B -> {A, D, G, H, I}, C -> {A, J, K, G, M} ....

Это сформирует простую сеть, которую вы теперь можете проходить с вариацией Dijkstra здесь, чтобы получить все точки, смежные с вашей ближайшей точкой.

Построение структур данных потребует времени, но после того, как все сделано, и правильный поиск и возврат набора данных может быть выполнен за миллисекунды (не включая http или автономную связь по причине)

Надеюсь, это поможет.

Answer 2

Прочтите эту статью о пространственной индексации.

Я предполагаю, что ваш основной фильтр очень неэффективен. Вероятно, вам нужно, чтобы плотность сетки была ВЫСОКОЙ для первого уровня, поскольку ваши точки очень плотные. Одна проблема, с которой я боролся, это как сделать так, чтобы LEVEL1 имел плотность больше 256 (HIGH). Я поражен, что Microsoft заставила нас использовать только 3 варианта плотности сетки.

Answer 3

Вы пробовали поиграть с настройками индекса?Я обычно использую более высокие объекты на ячейку и «высокий» для всех уровней сетки.Смотрите ниже:

CREATE SPATIAL INDEX [SPATIAL_lidar] ON [dbo].[lidar] ([geom]) USING  GEOGRAPHY_GRID  WITH ( GRIDS =(LEVEL_1 =   HIGH,LEVEL_2 = HIGH,LEVEL_3 = HIGH,LEVEL_4 = HIGH),  CELLS_PER_OBJECT = 64, PAD_INDEX  = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF,   ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY] 

Answer 4

Для обычного запроса ближайшего соседа в SQL Server 2008 попробуйте подход, который Исаак задокументировал в своем блоге , который использует таблицу чисел для увеличения границ поиска, пока не будет найдено достаточное количество кандидатов.Другая рекомендация - попытаться изменить плотность вашей сетки - HHHH или HHMM, вероятно, будут работать лучше для плотных точек.

В Sql Server Denali эта функция для оптимизированных запросов ближайших соседей также будет поддерживаться с помощью обычного SELECT TOP... Синтаксис ORDER BY.

В качестве sidenote, в вашем примере, похоже, что в вашем запросе отсутствует условие расстояния ORDER BY, чтобы идти вместе с вершиной?Ваш текущий запрос вернет точку, находящуюся в пределах 1000 метров от цели, но не обязательно ближайшую.