Общие сведения о пространственных индексах

Область применения: SQL Server База данных SQL Azure Управляемый экземпляр SQL Azure

SQL Server поддерживает пространственные данные и пространственные индексы. Пространственный индекс представляет собой тип расширенного индекса, позволяющий индексировать пространственные столбцы. Пространственный столбец представляет собой столбец таблицы, в котором содержатся данные пространственного типа, например geometry или geography.

О пространственных индексах

Декомпозиция индексированного пространства в сеточную иерархию

В SQL Server пространственные индексы создаются с помощью деревьев B, что означает, что индексы должны представлять 2-мерные пространственные данные в линейном порядке деревьев B.. Таким образом, перед чтением данных в пространственный индекс SQL Server реализует иерархическую однородную декомпозицию пространства. В процессе создания индекса происходит декомпозиция пространства в четырехуровневую сеточную иерархию. Эти уровни называют Уровень 1 (верхний), Уровень 2, Уровень 3и Уровень 4.

Каждый последующий уровень содержит дальнейшую декомпозицию уровня выше, так что каждая ячейка уровня выше содержит полную сетку следующего уровня. На заданном уровне все сетки имеют одинаковое число ячеек на обеих осях (например, 4x4 или 8x8), и все ячейки имеют одинаковый размер.

На следующем рисунке показана декомпозиция верхней правой ячейки на каждом уровне сеточной иерархии в сетку 4x4. Фактически, таким образом декомпозиция выполняется для всех ячеек. Например, декомпозиция пространства в четыре уровня сеток 4x4 фактически приводит к созданию 65 536 ячеек четвертого уровня.

Ячейки в сеточной иерархии нумеруются в линейном порядке с использованием варианта заполнения пространства кривой Гильберта. Однако на данном рисунке используется простая построковая нумерация вместо нумерации, которая фактически создается кривой Гильберта. На следующем рисунке несколько многоугольников, представляющих здания, и линий, представляющих улицы, помещены в сетку 4x4 уровня 1. Ячейки первого уровня нумеруются от 1 до 16, начиная с верхней левой.

Плотность сетки

Число ячеек по осям сетки определяет ее плотность: чем больше число, тем плотнее сетка. Например, сетка 8x8 (которая порождает 64 ячейки) плотнее сетки 4x4 (которая порождает 16 ячеек). Плотность сетки определяется по уровням.

Инструкция CREATE SPATIAL INDEXTransact-SQL поддерживает предложение GRIDS, позволяющее указать различные плотности сетки на разных уровнях. Плотность сетки для данного уровня задается с помощью одного из следующих ключевых слов.

В SQL Server, если для уровня совместимости базы данных задано значение 100 или ниже, значение по умолчанию — MEDIUM на всех уровнях. Если уровень совместимости базы данных имеет значение 110 или выше, то по умолчанию используется автоматическая схема сетки. (Автоматическая сетка указывает 8 уровень конфигурации HLLLLLLL.) Вместо изменения плотности сетки индекса можно изменять число ячеек на объект и число ячеек окна запроса на объект посредством указания.

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

Тесселяция

После декомпозиции индексированного пространства в сеточную иерархию пространственный индекс построчно считывает данные из пространственного столбца. После считывания данных для пространственного объекта (или экземпляра) пространственный индекс выполняет процесс тесселяции для этого объекта. Процесс тесселяции помещает объект в cеточную иерархию, устанавливая связь между объектом и набором сеточных ячеек, с которыми он соприкасается (контактные ячейки). Начиная с уровня 1 сеточной иерархии, процесс тесселяции сначала обрабатывает уровень в ширину . В принципе процесс может продолжиться для всех четырех уровней, по одному уровню за раз.

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

Правила тесселяции

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

Ниже приведены эти правила.

• Правило покрытия

  Если объект полностью покрывает ячейку, говорят, что эта ячейка накрыта объектом. Накрытая ячейка считается и не подвергается тесселяции. Это правило применяется на всех уровнях сеточной иерархии. Это правило упрощает процесс тесселяции и сокращает объем данных, записываемых в пространственный индекс.

• Правило ячеек на объект

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

• Правило самой глубокой ячейки

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

Эти правила тесселяции применяются рекурсивно на каждом уровне сетки. В оставшейся части этого раздела правила тесселяции описываются более подробно.

Правило покрытия

Если объект полностью покрывает ячейку, говорят, что эта ячейка накрыта объектом. Например, на следующем рисунке одна из ячеек второго уровня (15.11) полностью накрыта средней частью восьмиугольника.

Накрытая ячейка считается и записывается в индекс, и дальнейшая тесселяция для ячейки не проводится.

Правило ячеек на объект

Экстент тесселяции для каждого объекта в основном зависит от ограничения ячеек на объект в пространственном индексе. Это ограничение определяет максимальное число ячеек, которые могут считаться в процессе тесселяции объекта. Однако имейте в виду, что правило ячеек на объект не действует для уровня 1, поэтому данное ограничение может быть превышено. Если счет на уровне 1 достигает или превышает ограничение ячеек на объект, на нижних уровнях дальнейшая тесселяция не проводится.

Пока счет меньше ограничения ячеек на объект, процесс тесселяции продолжается. Начиная с контактной ячейки с минимальным номером (например, ячейка 15.6 на предыдущем рисунке), процесс проверяет каждую ячейку и принимает решение, считать ее или проводить тесселяцию. Если при тесселяции ячейки будет превышено ограничение ячеек на объект, то ячейка будет посчитана, но тесселяция для нее проведена не будет. В противном случае проводится тесселяция ячейки, а ячейки нижнего уровня, соприкасающиеся с объектом, считаются. Процесс тесселяции продолжается, таким образом, в ширину по всему уровню. Этот процесс повторяется рекурсивно для сеток нижнего уровня тесселированных ячеек, пока не будет достигнуто ограничение или все ячейки не будут подсчитаны.

Например, рассмотрим предыдущий рисунок, где восьмиугольник полностью помещается в ячейку 15 сетки уровня 1. На этом рисунке для ячейки 15 была проведена тесселяция, которая разбила восьмиугольник на девять ячеек уровня 2. На рисунке предполагается, что ограничение ячеек на объект равно 9 или больше. Однако, если бы ограничение ячеек на объект равнялось 8 или меньше, то для ячейки 15 тесселяция бы не проводилась и для объекта считалась бы только ячейка 15.

По умолчанию ограничение ячеек на объект равно 16, что обеспечивает разумный компромисс между охватом и точностью для большинства пространственных индексов. Однако инструкция CREATE SPATIAL INDEXTransact-SQL поддерживает предложение CELLS_PER_OBJECT = n, позволяющее указать ограничение ячеек на объект в диапазоне от 1 до 8192 включительно.

Правило самой глубокой ячейки

Правило самой глубокой ячейки учитывает тот факт, что каждая ячейка нижнего уровня принадлежит ячейке над ней. Ячейка уровня 4 принадлежит ячейке уровня 3, ячейка уровня 3 принадлежит ячейке уровня 2, а ячейка уровня 2 принадлежит ячейке уровня 1. Например, объект, который относится к ячейке 1.1.1.1, также принадлежит ячейке 1.1.1, ячейке 1.1 и ячейке 1. Сведения о таких иерархических связях ячеек встроены в обработчик запросов. Поэтому в индекс необходимо записывать только ячейки самого нижнего уровня, минимизируя объем данных, хранящихся в индексе.

На следующем рисунке проводится тесселяция относительно небольшого ромбовидного многоугольника. В индексе используется ограничение ячеек на объект, по умолчанию равное 16, которое для этого небольшого объекта не достигается. Таким образом, тесселяция продолжается до уровня 4. Многоугольник располагается в следующих ячейках на уровнях с 1 по 3: 4, 4.4, 4.4.10 и 4.4.14. Однако, согласно правилу самой глубокой ячейки, тесселяция учитывает только двенадцать ячеек на уровне 4: 4.4.10.13-15 и 4.4.14.1-3, 4.4.14.5-7 и 4.4.14.9-11.

Схемы тесселяции

Поведение пространственного индекса частично зависит от используемой схемы тесселяции. Схема тесселяции зависит от типа данных. В SQL Server пространственные индексы поддерживают две схемы тесселяции:

• Тесселяция геометрической сетки— эта схема предназначена для типа данных geometry ).

• Тесселяция сетки географических объектов, которая применяется к столбцам типа данных geography .

Схема тесселяции сетки геометрических объектов

GEOMETRY_AUTO_GRID тесселяции — это схема тесселяции по умолчанию для типа данных геометрии для SQL Server 2012 (11.x) и более поздних версий. GEOMETRY_GRID тесселяции — это единственная схема тесселяции, доступная для типов данных геометрии в SQL Server 2008 (10.0.x). В этом разделе рассматриваются аспекты тесселяции сетки геометрических объектов, релевантные для пространственных индексов: поддерживаемые методы и ограничивающие прямоугольники.

Ограничивающий прямоугольник

Геометрические данные занимают плоскость, которая может быть бесконечной. Однако в SQL Server пространственный индекс требует ограниченного пространства. Для определения конечного пространства для декомпозиции схеме тесселяции сетки геометрических объектов требуется ограничивающий прямоугольник. Ограничивающий прямоугольник определяется четырьмя координатами (x-min,y-min) и (x-max,y-max), которые хранятся в виде свойств пространственного индекса. Эти координаты представляют следующее.

• x-min — это координата левого нижнего угла ограничивающего прямоугольника по оси X.

• y-min — это координата левого нижнего угла по оси Y.

• x-max — это координата верхнего правого угла по оси X.

• y-max — это координата верхнего правого угла по оси Y.

Координаты (x-min,y-min) и (x-max,y-max) определяют расположение и размеры ограничивающего прямоугольника. Пространство за пределами ограничивающего прямоугольника считается одной ячейкой с номером 0.

В пространственном индексе проводится декомпозиция пространства внутри ограничивающего прямоугольника. Сетка уровня 1 сеточной иерархии заполняет ограничивающий прямоугольник. Чтобы поместить геометрический объект в сеточную иерархию, пространственный индекс сравнивает координаты объекта с координатами ограничивающего прямоугольника.

На приведенном ниже рисунке показаны точки, определенные координатами (x-min,y-min) и (x-max,y-max) ограничивающего прямоугольника. Верхний уровень сеточной иерархии показан как решетка 4x4. На данном рисунке нижние уровни опущены. Пространство за пределами ограничивающего прямоугольника обозначается нулем (0). Обратите внимание, что объект A частично выходит за пределы ограничивающего прямоугольника, а объект B находится полностью вне прямоугольника в ячейке 0.

Ограничивающий прямоугольник относится к некоторой части пространственных данных приложения. Приложение само определяет, будет ли ограничивающий прямоугольник индекса полностью включать данные из пространственного столбца или только их часть. Пространственный индекс имеет смысл использовать только для операций с объектами, полностью находящимися внутри ограничивающего прямоугольника. Поэтому для максимально эффективного использования пространственного индекса по столбцу geometry необходимо указать ограничивающий прямоугольник, содержащий все объекты или большинство из них.

Схема тесселяции сетки географических объектов

Эта схема тесселяции применяется только к столбцу geography . В этом разделе рассматриваются методы, поддерживаемые тесселяцией географических объектов, и описывается, как геодезическое пространство проецируется на плоскость, которая затем подвергается декомпозиции в сеточную иерархию.

Проекция геодезического пространства на плоскость

При вычислениях с экземплярами geography (объектами) пространство, содержащее объекты, считается геодезическим эллипсоидом. Для декомпозиции этого пространства схема тесселяции сетки географических объектов разделяет эллипсоид на верхнюю и нижнюю полушария, а затем выполняет следующие шаги.

1. Проецирует каждое полушарие на грани четырехсторонней пирамиды.

2. Делает обе пирамиды плоскими.

3. Соединяет плоские пирамиды для создания неевклидовой плоскости.

На следующем рисунке показано схематическое представление трехэтапного процесса декомпозиции. В пирамидах пунктирные линии представляют границы четырех граней каждой пирамиды. На шагах 1 и 2 показан геодезический эллипсоид: зеленая горизонтальная линия представляет экваториальную широту, а ряд зеленых вертикальных линий представляют несколько долгот. На шаге 1 показано проецирование двух полушарий на пирамиды. На шаге 2 показано уплощение пирамид. На шаге 3 показаны плоские пирамиды после их объединения в плоскость и число спроецированных линий долготы. Обратите внимание, что эти спроецированные линии выпрямлены и различаются по длине в зависимости от места проецирования на пирамиду.

После проецирования пространства на плоскость проводится ее декомпозиция в четырехуровневую сеточную иерархию. На разных уровнях могут использоваться разные плотности сетки. На следующем рисунке показана плоскость после ее декомпозиции в сетку 4x4 уровня 1. На данном рисунке нижние уровни сеточной иерархии опущены. На самом деле плоскость подвергается полной декомпозиции в четырехуровневую сеточную иерархию. После окончания декомпозиции географические данные из столбца geography считываются по строкам, и для каждого объекта выполняется процедура тесселяции.

Поддерживаемые методы для пространственных индексов

Геометрические методы, поддерживаемые пространственными индексами

При определенных условиях пространственные индексы поддерживают следующие геометрические методы на основе наборов: STContains(), STDistance(), STEquals(), STIntersects(), STOverlaps(), STTouches() и STWithin(). Чтобы пространственный индекс поддерживал эти методы, в запросе их необходимо использовать в пределах предложения WHERE или JOIN ON, включив в состав предиката следующего общего вида:

geometry1.имя_метода(geometry2)оператор_сравнения**допустимое_число

Чтобы получить ненулевой результат, аргументы geometry1 и geometry2 должны иметь одинаковый идентификатор пространственной ссылки (SRID). В противном случае метод возвращает значение NULL.

Пространственные индексы поддерживают предикаты следующих форм:

• geometry1.STContains(geometry2) = 1

• geometry1.Номер STDistance(geometry2) <

• geometry1.STDistance(geometry2) <= число

• geometry1.STEquals(geometry2)= 1

• geometry1.STIntersects(geometry2)= 1

• geometry1. STOverlaps (geometry2) = 1

• geometry1.STTouches(geometry2) = 1

• geometry1.STWithin(geometry2)= 1

Географические методы, поддерживаемые пространственными индексами

При определенных условиях пространственные индексы поддерживают следующие географические методы для работы с наборами: STIntersects(),STEquals(), and STDistance(). Чтобы пространственный индекс поддерживал эти методы, их необходимо использовать в предложении WHERE запроса, включив в состав предиката следующего общего вида:

geography1.имя_метода(geography2)оператор_сравнения**допустимое_число

Чтобы получить ненулевой результат, аргументы geography1 и geography2 должны иметь одинаковый идентификатор пространственной ссылки (SRID). В противном случае метод возвращает значение NULL.

Пространственные индексы поддерживают предикаты следующих форм:

• geography1.STIntersects(geography2)= 1

• geography1.STEquals(geography2)= 1

• geography1.Номер STDistance(geography2) <

• geography1.STDistance(geography2) <= число

Запросы, использующие пространственные индексы

Пространственные индексы поддерживаются только в запросах, в предложении WHERE которых есть индексированный пространственный оператор. Пример синтаксиса.

[spatial object].SpatialMethod([reference spatial object]) [ = | < ] [const literal or variable]  

Оптимизатор запросов учитывает коммутативность пространственных операций (что @a.STIntersects(@b) = @b.STInterestcs(@a) ). Однако пространственный индекс не будет использоваться, если в начале сравнения нет пространственного оператора (например, WHERE 1 = spatial op не будет использовать пространственный индекс). Для использования пространственного индекса перепишите сравнение (например, WHERE spatial op = 1).

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

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

SELECT TOP(K) [WITH TIES] *   
FROM <Table> AS T [WITH(INDEX(<SpatialIndex>))]  
WHERE <SpatialColumn>.STDistance(@reference_object) IS NOT NULL  
ORDER BY <SpatialColumn>.STDistance(@reference_object) [;]  

См. также

Пространственные данные (SQL Server)