С возвращением в серию о внутреннем устройстве структур хранения. Я начал с обзора стандартных типов хранения в выпусках о дисковом rowstore, колоночных индексах, оптимизированном для памяти хранилище и оптимизированных для памяти колоночных хранилищах, а затем перешёл к специализированным структурам хранения в частях об XML-индексах и JSON-индексах. Теперь пришло время рассмотреть пространственные индексы.
Тесселяция
Чтобы понять пространственные индексы, сначала нужно разобраться в процессе, известном как «тесселяция». Это процесс, при котором фигура делится на более мелкие элементы, которые затем могут рекурсивно делиться ещё дальше, в результате чего получается список ячеек, для каждой из которых указан атрибут, показывающий, покрывает ли объект эту ячейку частично или полностью.
Я покажу пример, чтобы проиллюстрировать процесс. Допустим, у вас есть таблица с геометрическими объектами, и в одной из её строк хранится объект, изображённый ниже:
Когда вы создаёте пространственный индекс по этой таблице, SQL Server применит процесс тесселяции для каждой строки. Первым шагом в этом процессе будет наложение сетки ячеек поверх объекта, как показано ниже (обратите внимание, что количество ячеек можно настроить в параметре GEOMETRY_GRID или GEOGRAPHY_GRID инструкции CREATE SPATIAL INDEX).
На рисунке выше я пронумеровал ячейки для удобства. SQL Server также нумерует их, но иначе (используя вариацию кривой Гильберта, заполняющей пространство).
На этом этапе мы уже можем выделить три типа ячеек. Ячейки 4 и 12 полностью не пересекаются с объектом, ни одна часть стрелки не попадает в эти ячейки, что делает их несущественными для пространственного индекса. Ячейка 6 полностью покрыта объектом. А все остальные ячейки покрыты частично (хотя ячейка 7 очень близка к полному покрытию).
Здесь начинается рекурсия. Каждая частично покрытая ячейка теперь делится на множество более мелких ячеек. На рисунке ниже это показано для ячейки 5, но то же самое делается и для всех остальных частично покрытых ячеек. Как видно на рисунке, эти меньшие ячейки снова могут быть несущественными, полностью покрытыми или частично покрытыми.
Процесс рекурсии продолжается до тех пор, пока не будет достигнут максимальный уровень рекурсии или максимальное количество ячеек. Их можно задать в инструкции CREATE SPATIAL INDEX или оставить по умолчанию. Так что в реалистичном случае ячейки 5.1, 5.2, 5.6, 5.7, 5.10, 5.11 и 5.14 могли бы делиться дальше. Но давайте для этой статьи предположим, что максимальная рекурсия (или максимальное количество ячеек) уже достигнута. Это означает, что эти частично покрытые ячейки больше не делятся, а просто помечаются как частично покрытые.
Структура индекса
Вооружившись знанием о процессе тесселяции, мы можем теперь рассмотреть детали того, как SQL Server хранит пространственный индекс. Для этого, конечно, нужно его иметь. Ни одна из стандартных демонстрационных баз данных Microsoft его не содержит. Но во многих есть столбцы с типом данных geometry или geography, что позволяет легко создать пространственный индекс.
Я выбрал для этого образец базы данных ContosoRetailDW, потому что в ней есть одна таблица, содержащая как столбец geometry, так и столбец geography. Это позволяет нам увидеть различия и сходства между ними. Итак, начнём с создания двух пространственных индексов в этой базе данных, используя по возможности параметры по умолчанию:
CREATE SPATIAL INDEX spix_DimStore_Geometry
ON dbo.DimStore (Geometry) -- Data type: geometry
USING GEOMETRY_AUTO_GRID
WITH (BOUNDING_BOX = (XMIN = -500, YMIN = -500, XMAX = 500, YMAX = 500));
CREATE SPATIAL INDEX spix_DimStore_GeoLocation
ON dbo.DimStore (GeoLocation) -- Data type: geography
USING GEOGRAPHY_AUTO_GRID;
Теперь мы можем использовать приведённый ниже запрос, который вы, возможно, помните из предыдущих выпусков этой серии, чтобы выяснить, какие объекты создал для нас SQL Server:
SELECT o.object_id AS [Object ID],
SCHEMA_NAME (o.schema_id) AS [Schema name],
o.name AS [Object name],
o.parent_object_id AS [Parent object ID],
o.type_desc AS [Object type],
i.name AS [Index name],
i.index_id AS [Index ID],
i.type_desc AS [Index type]
FROM sys.indexes AS i
INNER JOIN sys.objects AS o
ON o.object_id = i.object_id
WHERE o.parent_object_id = OBJECT_ID ('dbo.DimStore')
OR o.object_id = OBJECT_ID ('dbo.DimStore');
Полученный мной вывод приведён ниже. Как всегда, вы, вероятно, увидите другие значения Object ID и другие имена объектов.
Шаблон, который вы здесь видите, — тот же, что мы наблюдали при рассмотрении XML-индексов и JSON-индексов: «официальный» индекс с соответствующим типом индекса по самой таблице, но затем ещё и кластерный индекс по внутренней таблице, которая в данном случае названа по object_id таблицы плюс index_id индекса. Эта внутренняя таблица, которую я буду называть «таблицей тесселяции», — там, где происходит вся магия.
Таблица тесселяции
Давайте ещё раз вернёмся к запросу из некоторых предыдущих выпусков, чтобы проверить, какие столбцы существуют в таблице тесселяции.
SELECT i.name AS IndexName,
c.name AS ColumnName,
t.name AS Datatype,
CASE
WHEN c.max_length = -1 THEN
'MAX'
ELSE
CAST (c.max_length AS varchar(30))
END AS MaxLength,
ic.key_ordinal AS [Clustered index column]
FROM sys.indexes AS i
INNER JOIN sys.columns AS c
ON c.object_id = i.object_id
INNER JOIN sys.types AS t
ON t.user_type_id = c.user_type_id
LEFT JOIN sys.index_columns AS ic
ON ic.object_id = i.object_id
AND ic.index_id = i.index_id
AND ic.column_id = c.column_id
WHERE i.name IN (N'spix_DimStore_Geometry', N'spix_DimStore_GeoLocation')
AND i.type_desc = 'CLUSTERED'
ORDER BY i.name,
c.column_id;
Вот результаты:
Как видите, обе таблицы имеют одинаковую структуру. Три столбца. Первичный ключ состоит из двух столбцов Id (который представляет номер ячейки, хранимый в иерархическом формате) и pk0 (первичный ключ строки в таблице dbo.DimStore — если бы это был составной ключ, то внутренняя таблица добавила бы столбцы pk1, pk2 и т.д. по мере необходимости). Последний столбец, не входящий в первичный ключ, называется Attr. Этот столбец хранит тип ячейки: 2 для полного покрытия или 1 для частичного покрытия, которое не было дополнительно разделено.
Интересно посмотреть, как всё меняется, когда вместо автоматического параметра сетки я использую ручное задание сетки тесселяции. Чтобы проверить это самостоятельно, вы можете удалить два только что созданных индекса, а затем создать их снова, но теперь с этим кодом:
DROP INDEX spix_DimStore_Geometry ON dbo.DimStore;
DROP INDEX spix_DimStore_GeoLocation ON dbo.DimStore;
CREATE SPATIAL INDEX spix_DimStore_Geometry
ON dbo.DimStore (Geometry) -- Data type: geometry
USING GEOMETRY_GRID
WITH (BOUNDING_BOX = ( XMIN = -500, YMIN = -500, XMAX = 500, YMAX = 500),
GRIDS = (LEVEL_4 = HIGH, LEVEL_3 = HIGH, LEVEL_2 = HIGH, LEVEL_1 = HIGH),
CELLS_PER_OBJECT = 64);
CREATE SPATIAL INDEX spix_DimStore_GeoLocation
ON dbo.DimStore (GeoLocation) -- Data type: geography
USING GEOGRAPHY_GRID
WITH (GRIDS = (LEVEL_4 = HIGH, LEVEL_3 = MEDIUM, LEVEL_2 = LOW, LEVEL_1 = MEDIUM),
CELLS_PER_OBJECT = 64);
Если вы теперь повторите DMV-запросы выше, вы увидите, что создаются те же индексы и внутренние таблицы. Но столбцы в этих внутренних таблицах отличаются:
Различия кажутся больше, чем есть на самом деле. Столбцы, которые сначала назывались «Id» и «Attr», по-прежнему на месте, но теперь называются «Cell_Id» и «Cell_Attributes». Столбец «pk0» не изменился. Единственное реальное изменение — добавление столбца «SRID», который используется для хранения идентификатора пространственных ссылок (Spatial Reference Identifier, SRID).
Для остальной части этой статьи я буду предполагать, что пространственные индексы созданы с параметром автоматической сетки. Поэтому, если вы выполнили вышеуказанные шаги, вам придётся снова удалить и пересоздать эти индексы:
DROP INDEX spix_DimStore_Geometry ON dbo.DimStore;
DROP INDEX spix_DimStore_GeoLocation ON dbo.DimStore;
CREATE SPATIAL INDEX spix_DimStore_Geometry
ON dbo.DimStore (Geometry) -- Data type: geometry
USING GEOMETRY_AUTO_GRID
WITH (BOUNDING_BOX = (XMIN = -500, YMIN = -500, XMAX = 500, YMAX = 500));
CREATE SPATIAL INDEX spix_DimStore_GeoLocation
ON dbo.DimStore (GeoLocation) -- Data type: geography
USING GEOGRAPHY_AUTO_GRID;
Давайте также взглянем на содержимое этой таблицы тесселяции. Как всегда, вам нужно будет использовать выделенное административное подключение (DAC) для запроса этой внутренней таблицы, и я категорически не рекомендую делать это в производственной системе!
На скриншоте ниже показана часть содержимого одной из внутренних таблиц (в данном случае для столбца geometry):
Столбец Id (или Cell_Id) — это иерархическое представление номера ячейки. Обратите внимание, что ячейки, которые рекурсивно разделены, не хранятся. Так, для образца геометрического объекта, который я использовал выше для иллюстрации процесса тесселяции, пространственный индекс включал бы строки для ячеек 5.3 и 6 (полностью покрытых), а также для ячеек 5.1 и 5.2 (частично покрытых), но не для ячеек 5 и 7 (также частично покрытых, но рекурсивно разделённых на более мелкие ячейки), и не для ячеек 4 и 5.5 (несущественных). Конечно, эти номера ячеек затем были бы представлены в двоичном формате, который вы видите на скриншоте.
Для индексов, созданных на таблице DimStore, столбец Attr (или Cell_Attribute) всегда равен 1 для всех строк. Это потому, что эти столбцы представляют собой просто местоположение, одну точку. Только более крупные области могут когда-либо полностью покрыть ячейку. Я посмотрел на столбцы geometry в других таблицах, что дало следующий список возможных значений для столбца Attr (или Cell_Attribute):
2: ячейка полностью покрыта.
1: ячейка покрыта частично (но не разделена дальше).
0: ячейка не покрыта и, следовательно, несущественна.
Значение 0 используется только в случаях, когда строка в основной таблице имеет NULL в столбце geometry (или geography). В этом случае в таблицу тесселяции добавляется одна строка с Id (или Cell_Id), равным 0x0000000000, и Attr (или Cell_Attribute), равным 0. Я предполагаю, что это необходимо для того, чтобы определённые планы выполнения возвращали эти строки при необходимости, когда выбор строк основан на таблице тесселяции.
Запросы к таблице тесселяции
И это подводит нас к теме того, как используются эти пространственные индексы. Для протокола: все пространственные запросы возможны и без пространственного индекса. Пространственный индекс лишь ускоряет процесс. Итак, давайте рассмотрим пример.
Приведённый ниже запрос сначала извлекает объект geometry, представляющий Францию, из таблицы DimGeography, а затем использует его, чтобы найти все магазины, расположенные где-либо на территории Франции.
DECLARE @France geometry;
SELECT @France = dg.Geometry
FROM dbo.DimGeography AS dg
WHERE dg.ContinentName = N'Europe'
AND dg.GeographyType = N'Country/Region'
AND dg.RegionCountryName = 'France';
SELECT ds.StoreKey,
ds.StoreManager,
ds.StoreType,
ds.StoreName,
ds.ZipCode
FROM dbo.DimStore AS ds
WHERE ds.Geometry.STIntersects (@France) = 1;
Для протокола: выбор STIntersects немного необычен. Более очевидный запрос использовал бы WHERE @France.STContains (ds.Geometry). Но оба возвращают одинаковые правильные результаты, и план выполнения для версии со STIntersects немного интереснее. Отсюда и мой выбор.
Итак, давайте посмотрим на этот план выполнения!
Это довольно сложный план выполнения. Но я не хочу превращать это в статью о plansplaining, поэтому пробегусь по нему гигантскими шагами и сосредоточусь только на специфической обработке, связанной с пространственным индексом.
Оператор Table Valued Function в правом верхнем углу использует внутреннюю табличную функцию PlanarTessellation. Я не показывал её, но эта же внутренняя табличная функция использовалась и при создании пространственного индекса (обратите внимание, что используются разные табличные функции, когда есть определяемая пользователем сетка или когда пространственный индекс построен по объекту geography. Однако все они выполняют одну и ту же функцию: создают тесселяцию для объекта geometry или geography). В данном случае первый входной параметр — @France, а остальные параметры совпадают с теми, что использовались при создании индекса. Эффект — создание тесселяции для @France на основе той же сетки, что использовалась для столбца Geometry в таблице DimStore, но с гораздо более высоким максимальным количеством ячеек на объект (параметр 6, который здесь равен 512, но был всего 8 в плане выполнения создания индекса).
Как видно из чисел в плане выполнения, это даёт 840 возвращённых строк. В списке вывода видно, что у них три столбца: Id, Attr и LimitId. Первые два по имени совпадают с двумя столбцами в таблице тесселяции и выполняют ту же функцию: иерархический номер ячейки и её атрибут, который может быть либо 1 для частичного покрытия, либо 2 для полного покрытия. Третий — LimitId, и это показывает (вместе с его использованием в плане выполнения, как мы вскоре увидим), что внутренняя табличная функция возвращает не отдельные ячейки и их атрибут, а то, что каждая строка представляет диапазон последовательных ячеек с одинаковым атрибутом.
Затем Nested Loops передаёт Id и LimitId в Clustered Index Seek, который читает из внутренней таблицы тесселяции. Какие строки читаются, определяется свойством Seek Predicates, которое упрощённо читается так: Start: extended_index.Id >= Id ; End: extended_index.Id <= LimitId. Таким образом, это возвращает все строки из таблицы тесселяции, у которых номер ячейки находится где-то в диапазоне между наименьшим и наибольшим номером ячейки из диапазона, полученного от табличной функции, только что переданного в seek. Обратите внимание, что благодаря иерархическому представлению номера ячейки это может совпадать даже тогда, когда они используют разный уровень рекурсии.
Для каждого диапазона это может вернуть несколько строк для одного значения pk0, если между двумя тесселяциями есть несколько перекрывающихся ячеек. И если Франция перекрывается более чем с одной строкой в таблице, это тоже приводит к большему числу строк. Однако если все ячейки, частично или полностью покрытые Францией, несущественны для тесселяции магазина (как, например, в случае с магазинами в США или Китае), то Clustered Index Seek не найдёт ни одной строки. Поскольку в образце данных всего несколько магазинов во Франции, это возвращает только 11 строк. Однако некоторые из них могут быть магазинами чуть за границами Франции, но в ячейке, которая всё ещё частично покрывалась Францией!
Значения Id ячеек больше не важны для остальной части плана выполнения. Для каждой строки, возвращённой Clustered Index Seek, Nested Loops теперь возвращает значение pk0 (первичный ключ магазина во Франции или рядом с ней) и два значения Attr: одно из тесселяции Франции, другое из тесселяции магазина. Для этих двух значений Attr есть три варианта (теоретически — поскольку Geometry в DimStore представляет точку, а не область, один из них в нашем случае невозможен). Один из вариантов — оба значения Attr равны 2. В этом случае одна полностью покрытая ячейка совпадает с другой полностью покрытой ячейкой. Даже если они находятся на разных уровнях рекурсии, этого достаточно, чтобы заключить, что два объекта пересекаются — в конце концов, единственное требование для пересечения — чтобы фигуры не были полностью разъединены. По той же причине случай, когда одно из значений Attr равно 1, а другое 2, также достаточен для вывода о перекрытии. Поскольку одна из ячеек полностью покрыта, частичное покрытие другой ячейки обязательно перекрывается с этим полным покрытием. Единственный «сложный» сценарий — когда оба значения Attr равны 1. В этом случае две ячейки, возможно, на разных уровнях рекурсии, обе частично покрыты своими объектами. Эти фигуры внутри ячеек могут фактически перекрываться, но это не гарантировано.
Способ, которым SQL Server обрабатывает эти три возможных случая, прост. Compute Scalar просто складывает два значения Attr. Для трёх возможных случаев это может дать 3 или 4, если одна или обе ячейки были полностью покрыты (что означает, что они точно перекрываются), или 2, если обе покрыты частично (что означает, что они могут перекрываться, а могут и нет). Затем Hash Match агрегирует значения по pk0, оставляя только наибольший из этих результатов сложения. В нашем случае количество строк остаётся 11 — помните, столбец Geometry в DimStore представляет точки, поэтому для каждого магазина никогда не будет больше одной ячейки. Но если бы я использовал столбец geometry, хранящий более крупные объекты, мы увидели бы здесь сокращение числа строк. Причина, по которой сохраняется максимум результатов сложения, проста: если две фигуры имеют несколько совпадающих ячеек и хотя бы одна из них даёт 3 или 4, мы уже знаем, что фигуры перекрываются; только если все совпадающие ячейки имеют оценку 2 (частичное покрытие в обеих, так что могут или не могут перекрываться), нам нужно выполнить дополнительную работу.
Прежде чем мы перейдём к этой дополнительной работе, мы сначала передаём pk0 в Clustered Index Seek по фактической таблице DimStore, где извлекаем все столбцы из списка SELECT, плюс столбец Geometry. Этот последний столбец, а также Expr1002, MAX результатов сложения, затем передаются вниз финальным Nested Loops.
Оператор Filter использует Startup Expression Predicate. Это означает, что, как только он вызывается, он вычисляет условие. Это условие использует выражение CASE. Если Expr1002, наибольший результат сложения, больше 2, то мы уже знаем, что фигуры пересекаются хотя бы в одной из ячеек. Но мы ещё не проверили, основаны ли обе фигуры на одном и том же SRID (Spatial Reference Identifier). Внутренняя скалярная функция SridMatch возвращает true, если это так, и false в противном случае.
Если наибольший результат сложения не больше 2 (то есть равен ровно 2, как мы уже видели, он может быть только 2, 3 или 4), то мы знаем, что у нас есть магазин, чья тесселяция имеет одну или несколько общих ячеек с тесселяцией Франции, но все они являются частичным покрытием для обеих. Это может быть совпадением, а может быть магазином, близким к Франции, но не внутри неё. В этом случае у нас нет другого выбора, кроме как вызвать (довольно дорогую) функцию STIntersects для двух значений, чтобы выполнить полное и точное определение, пересекаются они или нет.
По-видимому, четыре из магазинов с перекрывающейся тесселяцией действительно находились за пределами Франции. Для них проверка Startup Expression Predicate в Filter даёт false, что означает, что ни одна строка не возвращается в Nested Loops, и (поскольку это Inner Join) магазин теперь не попадает в результаты. Для оставшихся семи магазинов, которые все находятся во Франции, вызывается Constant Scan. Он просто возвращает пустую (с нулём столбцов) строку, которая возвращается в Nested Loops. Поскольку строка возвращена, Inner Join выполняется, и магазин теперь возвращается в SELECT, который возвращает строку клиенту.
Преимущество индекса
Если вы удалите пространственный индекс и затем снова выполните запрос для поиска всех магазинов во Франции, вы увидите очень простой план выполнения. Clustered Index Scan возвращает все 306 магазинов, и для каждой из этих 306 строк оператор Filter затем вызывает функцию STIntersects. Как упоминалось выше, это дорогая функция. Оценочная стоимость поддерева (Estimated Subtree Cost) этого простого (но дорогого) плана выполнения составляет 0,325 единиц стоимости.
Пространственный индекс отсеивает много лишнего. После сравнения тесселяций, которое выполняется быстро, поскольку мы можем использовать seek, нам нужно выполнить дальнейшую проверку только для 11 магазинов. Эта проверка может быть всё ещё дешёвой SridMatch или же дорогой STIntersects. Даже в худшем случае, когда всем 11 нужна последняя, мы избежали 295 вызовов этой функции. Даже по слегка более пессимистичным оценкам, где нам пришлось бы проверить 17 магазинов, оценочная стоимость поддерева теперь снижается до 0,246 единиц стоимости для полного плана выполнения. Это экономия 25% стоимости!
Другие функции geometry и geography
SQL Server поддерживает длинный список функций geometry и geography. Не все они выиграют от пространственного индекса. Для тех, которые выиграют, план выполнения будет сильно различаться в зависимости от функции. Однако, вероятно, все они будут использовать одну и ту же базовую идею: находить ячейки, общие для тесселяций двух объектов, а затем смотреть на атрибуты, чтобы различать возможные комбинации полного и частичного покрытия. Это должно привести к значительному сокращению числа случаев, когда всё ещё нужно вызывать фактическую функцию geometry или geography.
Заключение
Пространственный индекс хранит тесселяцию пространственного объекта. Эта тесселяция фактически является результатом деления (а затем рекурсивного подразделения) области на ячейки с различением ячеек, полностью покрытых, частично покрытых или полностью не пересекающихся с пространственным объектом. Полностью и частично покрытые ячейки затем сохраняются в пространственном индексе вместе с первичным ключом исходной таблицы как ссылкой обратно на соответствующую строку.
Для запросов, которые фильтруют по пространственным функциям, таким как STIntersects, STContains, STOverlaps и т.д., SQL Server затем сравнивает тесселяцию эталонного пространственного объекта с результатами тесселяции в этом пространственном индексе, чтобы быстро удалить все строки, которые не могут совпасть, и дополнительно различить строки, которые точно совпадают на основе тесселяции, и те, которые нуждаются в дальнейшей проверке. Фактическая функция затем вызывается только для строк из последней группы.
Комментариев нет:
Отправить комментарий