Обзор пространственного индексирования

SQL Server 2008 и более поздние версии поддерживают пространственные данные. Сюда входит поддержка планарного пространственного типа данных, geometry, который описывает геометрические объекты — точки, линии и многоугольники в евклидовой системе координат. Тип данных geography представляет географические объекты на поверхности Земли, например участки суши. Пространственный индекс для столбца geography позволяет соотносит географические данные с двумерным не-евклидовым пространством.

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

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

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

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

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

Примечание
Декомпозиция пространства в пространственный индекс не зависит от единиц измерения в данных приложения.

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

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

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

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

Ключевое слово	Конфигурация cетки	Число ячеек
LOW	4X4	16
MEDIUM	8X8	64
HIGH	16X16	256

По умолчанию для всех уровней используется MEDIUM.

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

Примечание
Плотности cеток в пространственном индексе можно просмотреть в столбцах level_1_grid, level_2_grid, level_3_grid и level_4_grid представления каталога sys.spatial_index_tessellations.

Тесселяция

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

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

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

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

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

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

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

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

  Это правило вводит ограничение ячеек на объект, которое определяет максимальное число ячеек, которые можно посчитать для каждого объекта (за исключением уровня 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 включительно.

Примечание
Параметр cells_per_object пространственного индекса можно найти в представлении каталога sys.spatial_index_tessellations.

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

Правило самой глубокой ячейки учитывает тот факт, что каждая ячейка нижнего уровня принадлежит ячейке над ней. Ячейка уровня 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.10.13-15 и 4.4.14.1-3, 4.4.14.5-7 и 4.4.14.9-11.

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

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

• Схема тесселяции сетки геометрических объектов (схема типа данных geometry).

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

Примечание
Параметр tessellation_scheme пространственного индекса можно найти в представлении каталога sys.spatial_index_tessellations.

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

Тесселяция сетки геометрических объектов является схемой тесселяции по умолчанию для типа данных geometry и в SQL Server 2008 является единственной такой схемой. В этом разделе рассматриваются аспекты тесселяции сетки геометрических объектов, релевантные для пространственных индексов: поддерживаемые методы и ограничивающие прямоугольники.

Примечание
Эту схему тесселяции можно задать явно с помощью предложения USING GEOMETRY_GRID в инструкции CREATE SPATIAL INDEXTransact-SQL.

Поддерживаемые географические методы

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

Дополнительные сведения о поддержке геометрических методов в пространственных индексах см. в разделе Геометрические методы, поддерживаемые пространственными индексами.

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

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

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

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

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

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

Примечание
Эти координаты задаются предложением BOUNDING_BOX в инструкции CREATE SPATIAL INDEXTransact-SQL.

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

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

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

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

Примечание
Плотности сеток в пространственном индексе можно просмотреть в столбцах bounding_box_xmin, bounding_box_ymin, bounding_box_xmax и bounding_box_ymax представления каталога sys.spatial_index_tessellations.

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

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

Примечание
Эту схему тесселяции можно задать явно с помощью предложения USING GEOGRAPHY_GRID в инструкции CREATE SPATIAL INDEXTransact-SQL.

Поддерживаемые географические методы

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

Дополнительные сведения о поддержке географических методов в пространственных индексах см. в разделе Географические методы, поддерживаемые пространственными индексами.

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

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

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

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

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

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

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

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

Пространственный индекс может быть создан только для пространственного столбца. Можно создавать пространственные индексы для любого пространственного столбца в таблице, поддерживающей пространственные индексы, и для данного пространственного столбца можно создавать несколько пространственных индексов. Дополнительные сведения об ограничениях на пространственные индексы см. в разделе Ограничения пространственных индексов.

См. также

Основные понятия

Создание, изменение и удаление пространственных индексов

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

Другие ресурсы

Работа с пространственными индексами (компонент Database Engine)