HierarchyID и parent-child - 2
В предыдущей серии картины (https://blogs.msdn.com/alexejs/archive/2009/05/27/hierarchyid-parent-child.aspx) не удалось добиться явного преимущества подхода parent-child по сравнению с новоиспеченым HierarchyID несмотря на то, что я ретроградствовал по полной. Требовалась какая-нибудь бредовая идея. Бредовость идей напрямую обуславливается количеством пива, имевшего быть на очередном семинаре SQL Server User Group в Москве (https://sql.ineta.ru/Events/EventMultiSessionInfo.aspx?Id=41ac2e44-0ce0-49b3-9182-bb8b26dcbbaf). В этот раз с пивом все обстояло нормально. Вдохновленный примером Дмитрия Костылева (https://blogs.gotdotnet.ru/personal/decolores/), который на собственном опыте удостоверился, что длина унификатора, нет, уникифакера, блин, короче, uniqueifier, который добавляет SQL Server к одинаковым значениям кластерного ключа, чтобы их разнообразить, составляет 4 байта, я тоже решил насовать в SQL Server чего-нибудь такого, чтобы ему поплохело вплоть до ошибки 666 или еще какой-нибудь зловещей величины. На 4 294 967 296 одинаковых значений терпения бы однозначно не хватило, поэтому я взял себе за магическое число 100 000 уровней и решил проверить, насколько потянут дерево такой глубины parent-child таблица и HierarchyID. В случае parent-child таблицы единственное, во что теоретически можно было бы упереться, - ограничение на глубину рекурсии в рекурсивном СТЕ. Но его нет. По умолчанию рекурсивный СТЕ-запрос имеет ограничение на глубину рекурсии в 100 уровней, которое легко обходится запросной опцией option (maxrecursion 100000). Или вообще option (maxrecursion 0), что означает, что рекурсивный СТЕ будет крутиться, покамест у него хватит памяти. Глубина рекурсии в СТЕ не имеет отношения к рекурсии в хранимых процедурах и триггерах, которая по-прежнему остается максимум 32 уровня. Пример:
if object_id('tempdb..#t', 'U') is not null drop table #t
create table #t (i int default 0)
insert #t default values
go
if object_id('p', 'P') is not null drop proc p
go
create proc p as begin
update #t set i += 1 output inserted.i
exec p
end
exec p
Скрипт 1
Рис. 1
То же самое для триггеров, только для них еще предварительно требуется
sp_configure 'nested triggers', 1
В отличие от хранимых процедур, функций, триггеров и вьюшек глубина рекурсии в СТЕ ограничена свободной памятью и фантазией. Пример:
declare @n0 int = 0, @n1 int = 100000
;with cte as (select n = @n0 union all select n = n + 1 from cte where n < @n1)
select * from cte option (maxrecursion 0)
Скрипт 2
Таким образом, если мы создадим parent-child таблицу для представления иерархии, она легко потянет 100 000 уровней иерархии.
--Набиваем данными
if object_id('tempdb..#t', 'U') is not null drop table #t
create table #t (i int, parent int)
declare @i int = 1
set nocount on
while 1 = 1 begin
insert #t values (@i, @i - 1)
if @i >= 100000 break
if @i % 1000 = 0 print @i
set @i += 1
end
--00:00:07
--Индексы, чтобы быстрее отображалось.
create clustered index i on #t(i)
create index parent on #t(parent)
--00:00:17
--Отображаем иерархию.
;with cte as (
select *, 0 as level from #t where parent = 0
union all
select #t.*, level + 1 from #t join cte on #t.parent = cte.i)
select space(level) + cast(i as varchar(6)) ii into #tt from cte option (maxrecursion 0)
--00:02:08
Скрипт 3
Рис. 2
Это яркое и наглядное преимущество parent-child таблицы как средства представления иерархии по сравнению с типом HierarchyID, поскольку средствами HierarchyID более-менее глубокая иерархия не может быть представлена из-за ограничений на размер типа, длина которого составляет 892 байта. Пример:
if object_id('tempdb..#t', 'U') is not null drop table #t
create table #t (hi hierarchyid)
declare @hid hierarchyid = hierarchyid::GetRoot()
declare @i int = 1
set nocount on
while 1 = 1 begin
insert #t values (@hid)
if @i >= 100000 break
select @i, datalength(@hid), @hid.ToString()
select @i += 1, @hid = @hid.GetDescendant(null, null)
end
Скрипт 4
Рис. 3
Глубина в 1427 уровней оказывается максимальной, больше этого HierarchyID вместить не может:
Msg 6522, Level 16, State 2, Line 10
A .NET Framework error occurred during execution of user-defined routine or aggregate "hierarchyid":
Microsoft.SqlServer.Types.HierarchyIdException: 24006: SqlHierarchyId.GetDescendant failed because its result is too big.
В реальной жизни глубина будет еще меньше, потому что в данном случае на каждом уровне находился один элемент. Чем больше элементов будет на уровне, тем больше бит потребуется на кодирование порядковых номеров элементов, расположенных справа. Прочитать про бинарное представление HierarchyID можно здесь - https://blogs.gotdotnet.ru/personal/yliberman/PermaLink.aspx?guid=5ed219fc-1624-4961-8eb1-e83a73cb4d11. Далее, когда узлы вставляются посередине уровня, например, 2.1 – между 2 и 3, после 2 будет добавлен флаг перехода на новый уровень (0 – нет перехода), затем код диапазона (01 – от 0 до 3) и смещение от начала диапазона (1). Короче, каждая промежуточная вставка дополнительно отъедает место от этих 892 байт, так что со временем HierarchyID приходится компактировать - https://www.sqlmag.com/Article/ArticleID/100646/sql_server_100646.html.
Обратно, можно немедленно привести ситуацию в которой HierarchyID, в свою очередь, одержит верх над parent-child. Скажем, требуется определить номер уровня, на котором находится некоторый элемент. Возьмем, к примеру, таблицу #t, полученную в результате Скриптов 1 и 2 предыдущего поста (HierarchyID и parent-child). В ней лежит результат ф-ции Dir() для директории c:\Program Files. При этом, кроме поля hid (HierarchyID), добавлены int поля id и parent, по которым организовано parent-child отношение для сравнения. Предположим, необходимо определить уровень залегания записи id = 26856, Name = netfx35_x86.exe по отношению к корневой директории c:\Program Files, для которой вызывалась функция Dir(). В случае HierarchyID для этого достаточно просто позвать метод GetLevel():
select hid.GetLevel(), * from #t where name = 'netfx35_x86.exe'
---------------------------------------------------------------
9 26856 0xAEB5B5AF8DAB netfx35_x86.exe 2007-11-08 03:09:54.9738211 6657032 0 26855
Скрипт 5
В случае parent-child отношения, как обычно, придется написать рекурсивный СТЕ:
with cte as (
select 0 as level, * from #t where name = 'netfx35_x86.exe'
union all
select level + 1, #t.* from #t join cte on #t.id = cte.parent_id)
select max(level) from cte
--------------------------
(No column name)
9
Скрипт 6
коий невзирая на сермяжную незатейливость довольно проиграет в пефомансе HierarchyID:
рис.4
Еще одним ощутимым бенефитом HierarchyID, которое славословится скоро два года, со времен июльского СТР Катмая, является его самоописательность. Например, по hid = /13/6/1/4/146/ для C:\Program Files\Microsoft SQL Server\MSSQL10.MSSQLSERVER\MSSQL\Binn\sqlservr.exe
select hid.ToString() from #t where fullName = 'C:\Program Files\Microsoft SQL Server\MSSQL10.MSSQLSERVER\MSSQL\Binn\sqlservr.exe'
можно сказать, что этот узел находится на 5-м (кол-во слэшей) уровне иерархии (по отношению к C:\Program Files), а, например, C:\Program Files\Microsoft SQL Server\MSSQL10.MSSQLSERVER\MSSQL\Binn\sqlagent.exe = /13/6/1/4/122/ является его братом (имеет того же непосредственного родителя /13/6/1/4/), стоящим перед ним (122 < 146) в пределах уровня. В отличие от parent-child, где, глядя на пару значений id/parent_id, ничего на эту тему сказать нельзя. Выше отмечалось, что для перемещения куска дерева из-под одного родителя под другого достаточно переделать parent_id у непосредственных детей, а в случае HierarchyID как раз из-за его самоописательности его придется переписывать для всех дочерних узлов, вызывая метод GetReparentedValue(). Но слабая сторона HierarchyID обращается сильной, а parent-child наоборот в рваных иерархиях. Как только в parent-child пропадет промежуточный узел между родителем и потомком, родственные отношения между ними утратятся навсегда. Ничто больше не наводит на мысль, что этот узел был потомком этого. Тогда как, глядя на значение HierarchyID, можно сразу представить себе структуру дерева вплоть до данного узла и его положение в общей иерархии дерева. Поясню, что имеется в виду, на примере поста "Синхронизация файловых каталогов средствами SQL Server" (https://blogs.msdn.com/alexejs/archive/2009/05/15/p20090515.aspx). После работы процедуры FindLeftDifferences в таблице ##merge образовались результаты несовпадений двух папок. Предположим, это файлы C:\Demo\MergeFolders\SqlServerProject1\PublicPrivateKeyFile.snk, C:\Demo\MergeFolders\SqlServerProject1\Test Scripts\Test.sql, C:\Demo\MergeFolders\SqlServerProject1\bin\Debug\SqlClassLibrary.dll. Хотелось бы вывести их согласно их местонахождению в фолдере C:\Demo\MergeFolders, поставив второй файл под первым, а третий под вторым, и сместив название файла на столько пробелов вправо, на каком уровне он находится. В данном примере эту информацию для наглядности можно почерпнуть из полного имени файла. Однако вместо полного пути может храниться только имя (sqlservr.exe или sqlagent.exe) или это вообще могут быть не файлы, а какие-то произвольные данные. HierarchyID есть аналог полного пути файла для узлов произвольной природы. В случае рваной иерархии бестолку делать рекурсивный СТЕ по типу Скрипт 6. Он не зацепит узлы без непосредственных родителей. В такой ситуации можно порекомендовать материализовать рекурсивный СТЕ, пока все непосредственные родители еще живы, проставив уровень против каждого узла, а потом, когда в дереве появятся дырки, джойнить узлы с материализованным СТЕ, вытаскивая уровни оставшихся узлов. Это муторно и некрасиво. Проще сделать ID типа HierarchyID, который позволяет построить красивое иерархическое представление независимо от дыр в иерархии:
SELECT replicate(' ', (ID.GetLevel() - 1) * 2) + source, dateModified, isDir, size, reason, CopyStatus
FROM [##merge]
ORDER BY ID.GetLevel(), ID
Скрипт 7
рис.5
Кроме того, отношения порядка над HierarchyID уже зведомо построены "правильно". В данном случае использован так называемый "широкий" порядок. Индексирование в глубину и ширину на картинках разбирается здесь - https://msdn.microsoft.com/ru-ru/library/bb677173.aspx.