HierarchyID и parent-child – 2


 


В предыдущей серии картины (http://blogs.msdn.com/alexejs/archive/2009/05/27/hierarchyid-parent-child.aspx) не удалось добиться явного преимущества подхода parent-child по сравнению с новоиспеченым HierarchyID несмотря на то, что я ретроградствовал по полной. Требовалась какая-нибудь бредовая идея. Бредовость идей напрямую обуславливается количеством пива, имевшего быть на очередном семинаре SQL Server User Group в Москве (http://sql.ineta.ru/Events/EventMultiSessionInfo.aspx?Id=41ac2e44-0ce0-49b3-9182-bb8b26dcbbaf). В этот раз с пивом все обстояло нормально. Вдохновленный примером Дмитрия Костылева (http://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


 


image001


 



Рис. 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


 


image003



Рис. 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


 


image005 



Рис. 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 можно здесь - http://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 приходится компактировать - http://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:


 


image007 



рис.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" (http://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


 


image009



рис.5


 


Кроме того, отношения порядка над HierarchyID уже зведомо построены "правильно". В данном случае использован так называемый "широкий" порядок. Индексирование в глубину и ширину на картинках разбирается здесь - http://msdn.microsoft.com/ru-ru/library/bb677173.aspx.


Skip to main content