Общие сведения о пространственных индексах
SQL Server поддерживает пространственные данные и пространственные индексы. Пространственный индекс представляет собой тип расширенного индекса, позволяющий индексировать пространственные столбцы. Пространственный столбец представляет собой столбец таблицы, в котором содержатся данные пространственного типа, например geometry или geography.
Важно! |
---|
Подробное описание и примеры использования новых функций обработки пространственных данных в этом выпуске, в том числе функции, работающие с пространственными индексами, можно получить, загрузив технический документ Новые функции обработки пространственных данных в SQL Server 2012. |
В этом разделе
О пространственных индексах
Декомпозиция индексированного пространства в сеточную иерархию
Тесселяция
Схемы тесселяции
Поддерживаемые методы для пространственных индексов
Геометрические методы, поддерживаемые пространственными индексами
Географические методы, поддерживаемые пространственными индексами
О пространственных индексах
Декомпозиция индексированного пространства в сеточную иерархию
В SQL Server пространственные индексы строятся с помощью сбалансированных деревьев, что означает, что индексы должны представлять двумерные пространственные данные в линейном порядке сбалансированных деревьев. Поэтому перед считыванием данных в пространственный индекс SQL Server проводит иерархическую декомпозицию пространства. В процессе создания индекса происходит декомпозиция пространства в четырехуровневую сеточную иерархию. Эти уровни называют Уровень 1 (верхний), Уровень 2, Уровень 3 и Уровень 4.
Каждый последующий уровень содержит дальнейшую декомпозицию уровня выше, так что каждая ячейка уровня выше содержит полную сетку следующего уровня. На заданном уровне все сетки имеют одинаковое число ячеек на обеих осях (например, 4x4 или 8x8), и все ячейки имеют одинаковый размер.
На следующем рисунке показана декомпозиция верхней правой ячейки на каждом уровне сеточной иерархии в сетку 4x4. Фактически, таким образом декомпозиция выполняется для всех ячеек. Например, декомпозиция пространства в четыре уровня сеток 4x4 фактически приводит к созданию 65 536 ячеек четвертого уровня.
Примечание |
---|
Декомпозиция пространства в пространственный индекс не зависит от единиц измерения в данных приложения. |
Ячейки в сеточной иерархии нумеруются в линейном порядке с использованием варианта заполнения пространства кривой Гильберта. Однако на данном рисунке используется простая построковая нумерация вместо нумерации, которая фактически создается кривой Гильберта. На следующем рисунке несколько многоугольников, представляющих здания, и линий, представляющих улицы, помещены в сетку 4x4 уровня 1. Ячейки первого уровня нумеруются от 1 до 16, начиная с верхней левой.
Плотность сетки
Число ячеек по осям сетки определяет ее плотность: чем больше число, тем плотнее сетка. Например, сетка 8x8 (которая порождает 64 ячейки) плотнее сетки 4x4 (которая порождает 16 ячеек). Плотность сетки определяется по уровням.
Инструкция CREATE SPATIAL INDEX Transact-SQL поддерживает использование предложения GRIDS, которое позволяет указывать различные плотности сетки на разных уровнях. Плотность сетки для данного уровня задается с помощью одного из следующих ключевых слов.
Ключевое слово |
Конфигурация сетки |
Число ячеек |
---|---|---|
LOW |
4X4 |
16 |
MEDIUM |
8X8 |
64 |
HIGH |
16X16 |
256 |
В SQL Server, если уровень совместимости базы данных имеет значение 100 или ниже, по умолчанию используется значение MEDIUM на всех уровнях. Если уровень совместимости базы данных имеет значение 110 или выше, то по умолчанию используется автоматическая схема сетки.
Управление процессом декомпозиции производится заданием плотности сетки, отличной от значения по умолчанию. Например, может оказаться полезным использование разных плотностей сеток на разных уровнях для точной настройки индекса, исходя из размера индексируемого пространства и объектов в пространственном столбце.
Примечание |
---|
Значения плотности сеток в пространственном индексе можно просмотреть в столбцах level_1_grid, level_2_grid, level_3_grid и level_4_grid представления каталога sys.spatial_index_tessellations, если уровень совместимости базы данных имеет значение 100 или ниже. Параметры схемы тесселяции GEOMETRY_AUTO_GRID/GEOGRAPHY_AUTO_GRID не заполняют эти столбцы. Представление каталога sys.spatial_index_tessellations содержит значения NULL в этих столбцах, если используются параметры автосетки. |
В начало
Тесселяция
После декомпозиции индексированного пространства в сеточную иерархию пространственный индекс построчно считывает данные из пространственного столбца. После считывания данных для пространственного объекта (или экземпляра) пространственный индекс выполняет процесс тесселяции для этого объекта. Процесс тесселяции помещает объект в cеточную иерархию, устанавливая связь между объектом и набором сеточных ячеек, с которыми он соприкасается (контактные ячейки). Начиная с уровня 1 сеточной иерархии, процесс тесселяции сначала обрабатывает уровень в ширину. В принципе процесс может продолжиться для всех четырех уровней, по одному уровню за раз.
Результатом процесса тесселяции является набор контактных ячеек, которые записываются в пространственный индекс объекта. Ссылаясь на эти записанные ячейки, пространственный индекс может найти объект в пространстве по его расположению относительно других объектов в пространственном столбце, которые также хранятся в индексе.
Правила тесселяции
Чтобы ограничить число контактных ячеек, записываемых для объекта, при проведении тесселяции применяется ряд правил тесселяции. Эти правила определяют глубину процесса тесселяции и контактные ячейки, которые записываются в индекс.
Ниже приведены эти правила.
Правило покрытия
Если объект полностью покрывает ячейку, говорят, что эта ячейка накрыта объектом. Накрытая ячейка считается и не подвергается тесселяции. Это правило применяется на всех уровнях сеточной иерархии. Это правило упрощает процесс тесселяции и сокращает объем данных, записываемых в пространственный индекс.
Правило ячеек на объект
Это правило проверяет ограничение ячеек на объект, который определяет максимальное число ячеек, которые могут быть подсчитаны для каждого объекта, за исключением первого уровня. На более низких уровнях правило ячеек на объект определяет объем данных, которые могут быть записаны об объекте.
Правило самой глубокой ячейки
Правило самой глубокой ячейки создает наилучшее приближение для объекта, записывая только самые нижние ячейки, созданные при тесселяции объекта. Родительские ячейки не включаются в счетчик ячеек на объект и не записываются в индекс.
Эти правила тесселяции применяются рекурсивно на каждом уровне сетки. В оставшейся части этого раздела правила тесселяции описываются более подробно.
Правило покрытия
Если объект полностью покрывает ячейку, говорят, что эта ячейка накрыта объектом. Например, на следующем рисунке одна из ячеек второго уровня (15.11) полностью накрыта средней частью восьмиугольника.
Накрытая ячейка считается и записывается в индекс, и дальнейшая тесселяция для ячейки не проводится.
Правило ячеек на объект
Экстент тесселяции для каждого объекта в основном зависит от ограничения ячеек на объект в пространственном индексе. Это ограничение определяет максимальное число ячеек, которые могут считаться в процессе тесселяции объекта. Однако имейте в виду, что правило ячеек на объект не действует для уровня 1, поэтому данное ограничение может быть превышено. Если счет на уровне 1 достигает или превышает ограничение ячеек на объект, на нижних уровнях дальнейшая тесселяция не проводится.
Пока счет меньше ограничения ячеек на объект, процесс тесселяции продолжается. Начиная с контактной ячейки с минимальным номером (например, ячейка 15.6 на предыдущем рисунке), процесс проверяет каждую ячейку и принимает решение, считать ее или проводить тесселяцию. Если при тесселяции ячейки будет превышено ограничение ячеек на объект, то ячейка будет посчитана, но тесселяция для нее проведена не будет. В противном случае проводится тесселяция ячейки, а ячейки нижнего уровня, соприкасающиеся с объектом, считаются. Процесс тесселяции продолжается, таким образом, в ширину по всему уровню. Этот процесс повторяется рекурсивно для сеток нижнего уровня тесселированных ячеек, пока не будет достигнуто ограничение или все ячейки не будут подсчитаны.
Например, рассмотрим предыдущий рисунок, где восьмиугольник полностью помещается в ячейку 15 сетки уровня 1. На этом рисунке для ячейки 15 была проведена тесселяция, которая разбила восьмиугольник на девять ячеек уровня 2. На рисунке предполагается, что ограничение ячеек на объект равно 9 или больше. Однако, если бы ограничение ячеек на объект равнялось 8 или меньше, то для ячейки 15 тесселяция бы не проводилась и для объекта считалась бы только ячейка 15.
По умолчанию ограничение ячеек на объект равно 16, что обеспечивает разумный компромисс между охватом и точностью для большинства пространственных индексов. Однако инструкция CREATE SPATIAL INDEX Transact-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.4.10.13-15 и 4.4.14.1-3, 4.4.14.5-7 и 4.4.14.9-11.
В начало
Схемы тесселяции
Поведение пространственного индекса частично зависит от используемой схемы тесселяции. Схема тесселяции зависит от типа данных. В SQL Server пространственные индексы поддерживают две схемы тесселяции.
Схема тесселяции сетки геометрических объектов (схема типа данных geometry).
Тесселяция сетки географических объектов, которая применяется к столбцам типа данных geography.
Примечание |
---|
Параметр tessellation_scheme пространственного индекса можно найти в представлении каталога sys.spatial_index_tessellations. |
Схема тесселяции сетки геометрических объектов
Схема тесселяции GEOMETRY_AUTO_GRID используется по умолчанию для типа данных geometry в SQL Server и более поздних версиях. Схема тесселяции GEOMETRY_GRID является единственной доступной для геометрических типов данных в SQL Server. В этом разделе рассматриваются аспекты тесселяции сетки геометрических объектов, релевантные для пространственных индексов: поддерживаемые методы и ограничивающие прямоугольники.
Примечание |
---|
Эту схему тесселяции можно задать явным образом с помощью предложения USING (GEOMETRY_AUTO_GRID/GEOMETRY_GRID) инструкции CREATE SPATIAL INDEX Transact-SQL. |
Ограничивающий прямоугольник
Геометрические данные занимают плоскость, которая может быть бесконечной. Однако в SQL Server для пространственного индекса требуется конечное пространство. Для определения конечного пространства для декомпозиции схеме тесселяции сетки геометрических объектов требуется ограничивающий прямоугольник. Ограничивающий прямоугольник определяется четырьмя координатами (x-min,y-min) и (x-max,y-max), которые хранятся в виде свойств пространственного индекса. Эти координаты представляют следующее.
x-min — это координата по оси X левого нижнего угла ограничивающего прямоугольника.
y-min — это координата по оси Y левого нижнего угла.
x-max — это координата по оси X верхнего правого угла.
y-max — это координата по оси Y верхнего правого угла.
Примечание |
---|
Эти координаты задаются предложением BOUNDING_BOX в инструкции CREATE SPATIAL INDEX Transact-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_AUTO_GRID/GEOGRAPHY_GRID) в инструкции CREATE SPATIAL INDEX Transact-SQL. |
Проекция геодезического пространства на плоскость
При вычислениях с экземплярами geography (объектами) пространство, содержащее объекты, считается геодезическим эллипсоидом. Для декомпозиции этого пространства схема тесселяции сетки географических объектов разделяет эллипсоид на верхнюю и нижнюю полушария, а затем выполняет следующие шаги.
Проецирует каждое полушарие на грани четырехсторонней пирамиды.
Делает обе пирамиды плоскими.
Соединяет плоские пирамиды для создания неевклидовой плоскости.
На следующем рисунке показано схематическое представление трехэтапного процесса декомпозиции. В пирамидах пунктирные линии представляют границы четырех граней каждой пирамиды. На шагах 1 и 2 показан геодезический эллипсоид, зеленая горизонтальная линия представляет экваториальную долготу, а ряд зеленых вертикальных линий представляют несколько широт. На шаге 1 показано проецирование двух полушарий на пирамиды. На шаге 2 показано уплощение пирамид. На шаге 3 показаны плоские пирамиды после их объединения в плоскость и число спроецированных линий долготы. Обратите внимание, что эти спроецированные линии выпрямлены и различаются по длине в зависимости от места проецирования на пирамиду.
После проецирования пространства на плоскость проводится ее декомпозиция в четырехуровневую сеточную иерархию. На разных уровнях могут использоваться разные плотности сетки. На следующем рисунке показана плоскость после ее декомпозиции в сетку 4x4 уровня 1. На данном рисунке нижние уровни сеточной иерархии опущены. На самом деле плоскость подвергается полной декомпозиции в четырехуровневую сеточную иерархию. После окончания декомпозиции географические данные из столбца geography считываются по строкам, и для каждого объекта выполняется процедура тесселяции.
В начало
Поддерживаемые методы для пространственных индексов
Геометрические методы, поддерживаемые пространственными индексами
При определенных условиях пространственные индексы поддерживают следующие геометрические методы на основе наборов: STContains(), STDistance(), STEquals(), STIntersects(), STOverlaps(), STTouches() и STWithin(). Чтобы пространственный индекс поддерживал эти методы, в запросе их необходимо использовать в пределах предложения WHERE или JOIN ON, включив в состав предиката следующего общего вида:
geometry1.method_name(geometry2) comparison_operator valid_number
Чтобы получить ненулевой результат, у geometry1 и geometry2 должны быть один и тот же идентификатор пространственной ссылки (SRID). В противном случае метод возвращает значение NULL.
Пространственные индексы поддерживают предикаты следующих форм:
geometry1.STContains(geometry2) = 1
geometry1.STDistance(geometry2) < number
geometry1.STDistance(geometry2) <= number
geometry1.STEquals(geometry2) = 1
geometry1.STIntersects(geometry2) = 1
geometry1.STOverlaps(geometry2) = 1
geometry1.STTouches(geometry2) = 1
geometry1.STWithin(geometry2) = 1
В начало
Географические методы, поддерживаемые пространственными индексами
При определенных условиях пространственные индексы поддерживают следующие географические методы для работы с наборами: STIntersects(), STEquals() и STDistance(). Чтобы пространственный индекс поддерживал эти методы, их необходимо использовать в предложении WHERE запроса, включив в состав предиката следующего общего вида:
geography1.method_name(geography2) comparison_operator valid_number
Чтобы получить ненулевой результат, аргументы geography1 и geography2 должны иметь одинаковый идентификатор пространственной ссылки (SRID). В противном случае метод возвращает значение NULL.
Пространственные индексы поддерживают предикаты следующих форм:
geography1.STIntersects(geography2) = 1
geography1.STEquals(geography2) = 1
geography1.STDistance(geography2) < number
geography1.STDistance(geography2) <= number
В начало
Запросы, использующие пространственные индексы
Пространственные индексы поддерживаются только в запросах, в предложении 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) [;]
В начало