HierarchyID и parent-child

Проблема, однако, состоит в том, что запрос Скрипт 4 (см. тему "Dir() и HierarchyID" - https://blogs.msdn.com/alexejs/archive/2009/05/24/dir-hierarchyid.aspx), вычисляющий полные имена файлов по текущему имени и цепочке родителей выполняется неприлично долго. В случае банальной Program Files (56 тыс.файлов и поддиректорий) я безуспешно прождал его полчаса, после чего заканселил, не говоря уже про c:\ целиком.

Возникает здоровое любопытство – тормоза проистекают по жизни из-за рекурсивного СТЕ или это метод GetAncestor() такой тормознутый? Для эксперимента достаточно навесить на таблицу с HierarchyID отношение parent-child на обычных int-колонках и построить рекурсивный СТЕ на основе этого отношения. Это можно сделать в самой TVF по аналогии с полем HierarchyID (Скрипт 3 в "Dir() и HierarchyID"), но я не стал ее усложнять, а добавил колонки id и parent_id уже на стороне SQL:

drop table #t

select identity(int, 1, 1) id, id hid, Name, dateModified, size, isDir, null parent_id into #t from dbo.Dir('c:\Program Files', 0)

--(56441 row(s) affected) 00:00:27

Скрипт 1

Значение id родителя в parent_id кладем на основе значения HierarchyID:

update t1 set parent_id = t2.id from #t t1 join #t t2 on t1.hid.GetAncestor(1) = t2.hid

--Меньше 1 сек.

Скрипт 2

Скрипт 2 выполняется меньше 1 секунды, что наводит на мысль, что, по-видимому, метод GetAncestor() отрабатывает достаточно быстро. Повторяем Скрипт 4 (постинг "Dir() и HierarchyID"), но уже для случая связки по id – parent_id:

if object_id('tempdb..#t1', 'U') is not null drop table #t1

;with cte as (

select #t.*, case when Name like '%\' then left(Name, len(Name) - 1) else Name end as fullName from #t where parent_id is null

union all

select #t.*, cast(cte.fullName + '\' + #t.Name as nvarchar(1000)) from #t join cte on #t.parent_id = cte.id)

select hid.ToString() hid1, * into #t1 from cte order by ID

--00:10:07

Скрипт 3

Время выполнения составляет порядка 10 мин. Повторюсь, что при связке по #t.hid.GetAncestor(1) = cte.hid аналогичный запрос выполнялся заведомо более получаса. Так что, parent-child оказывается выгоднее HierarchyID? Давайте не будем ограничиваться тупым сканом, а создадим индексы. Мы же видим в плане, как ему их хочется:

Рис.1

create clustered index id on #t(id)

create index parent_id on #t(parent_id)

Скрипт 4

И повторим Скрипт 3. На этот раз он выполняется порядка 10-15 секунд, т.е. в 40-60 раз быстрее. Для сравнения построим индекс по HierarchyID и СТЕ со связью на основе HierarchyID

create index hid on #t(hid)

if object_id('tempdb..#t1', 'U') is not null drop table #t1

;with cte as (

select #t.*, case when Name like '%\' then left(Name, len(Name) - 1) else Name end as fullName from #t where parent_id is null

union all

select #t.*, cast(cte.fullName + '\' + #t.Name as nvarchar(1000)) from #t join cte on #t.hid.GetAncestor(1) = cte.hid)

select hid.ToString() hid1, * into #t1 from cte order by ID

Скрипт 5

Время выполнения данного запроса также не превышает 15 сек., т.е. практически эквивалентно времени выполнения parent-child Скрипта 3 при наличии индексов Скрипт 4.

Для целиком диска с:\ (147001 записей) сбор, т.е. Скрипт 1 с dbo.Dir('c:\', 0) занимает в среднем полторы минуты; вычисление parent_id, т.е. Скрипт 2 – 4 - 8 секунд. Время выполнения parent-child вычислений полного пути (Скрипт 3) составляет заведомо больше часа (дальше терпения не хватило); с предварительным построением индексов (Скрипт 4 + Скрипт 3) – менее 1 минуты (45-55 секунд). Индекс и связь по HierarchyID (Скрипт 5) – аналогично, на самом деле получилось даже чуть меньше (35 – 45 сек.)

Вывод, который отсюда можно сделать. В рассмотренной задаче вычисления полного пути parent-child отношение не показывает преимуществ по сравнению HierarchyID с в производительности при условии наличия соответствующих (см. Скрипт 4, Скрипт 5) индексов. Данное соотношение сохраняет справедливость при возрастании числа записей (с 50 тыс. до 150).

Я могу с ходу придумать ситуацию, в которой parent-child заведомо окажется выгоднее HierarchyID. Это пернос куска дерева из-под одного родителя под другого. Пусть в директории c:\Demo находятся поддиректории ConsoleApplication1 и ConsoleApplication2 и требуется все файлы и поддиректории из-под первой переместить во вторую. Сначала, как обычно, вызываем функцию Dir()

use tempdb

if object_id('tempdb..#t', 'U') is not null drop table #t

select identity(int, 1, 1) id, id hid, Name, dateModified, size, isDir, null parent_id into #t from dbo.Dir('c:\Demo', 0)

Скрипт 6

и повторяем Скрипты 2 + 3 построения полного пути по parent-child.

Можно видеть

select id, hid1, fullName, parent_id, isDir, hid from #t1 where fullname like 'c:\demo\Console%'

-----------------------

Скрипт 7

что все, что для этого требуется сделать в случае parent-child таблицы, это сменить родителя ConsoleApplication1 на ConsoleApplication2 у непосредственных детей.

update #t set parent_id = 82 where parent_id = 63

Скрипт 8

В более глубоких уровнях (, ...\bin\Debug и т.д) ничего не меняется, поскольку непосредственные родители (...\bin) там сохраняются. Повторяем запрос Скрипт 7 и видим, что все из-под ConsoleApplication1 переместилось под ConsoleApplication2. При этом адекватно отобразились извенения id/parent_id.

select id, hid1, fullName, parent_id, isDir, size, hid from #t1 where fullname like 'c:\demo\Console%'

-----------------------

Скрипт 9

В случае HierarchyID придется обойти весь переносимый кусок дерева вглубь до упора и поменять внутри всех записей в этом куске поле HierarchyID. Хорошо, что у типа HierarchyID есть метод node.GetReparentedValue ( oldRoot, newRoot ) – см. https://msdn.microsoft.com/ru-ru/library/bb677207.aspx. Здесь node - это текущий узел внутри переносимого куска дерева, oldRoot – это hid узла ConsoleApplication1, newRoot – ConsoleApplication2. Осталось еще вспомнить замечательный метод IsDescendantOf(), прочитать про который можно в BOL (https://msdn.microsoft.com/ru-ru/library/bb677203.aspx), но лучше не надо, потому что там parent и child перепутаны местами. child.IsDescendantOf(parent) возвращает true, если узел child является потомком узла parent независимо от глубины родства, что сообразно, собственно, названию метода. Например, получить все содержимое ConsoleApplication1 вглубь до упора можно так:

select id, hid1, fullName, parent_id, isDir, hid from #t1 where hid.IsDescendantOf('/28/') = 1

----------------------------------------------------

Скрипт 10

У нас больше нет препятствий, чтобы написать эквивалент запроса Скрипт 8 для HierarchyID:

update #t set hid = hid.GetReparentedValue('/28/', '/29/') where hid.IsDescendantOf('/28/') = 1 and hid <> '/28/'

Скрипт 11

Здесь /28/ - это hid узла ConsoleApplication1, а /29/ - ConsoleApplication2 (см. Скрипт 9). Условие hid <> '/28/' добавлено в where потому, что метод IsDescendantOf рефлексивен и считает hid потомком самого себя. Без этого условия будет

select HierarchyID::Parse('/28/').GetReparentedValue('/28/', '/29/').ToString()

---

29

то есть он сделает ConsoleApplication1 ConsoleApplication2, а нам надо, чтобы она осталась собой. По выполнении Скрипт 11 запускаем Скрипт 5, который формирует полные имена файлов на основе hidов (а не parent-child отношений, как Скрипты 2 + 3), пускаем Скрипт 10 и видим, что снова все получилось, но в этот раз благодаря изменению hidов.

Скрипт 12

Несмотря на очевидную экономию в случае parent-child (апдейтим только уровень непосредственных детей поддерева), тогда как в случае HierarchyID – все поддерево, при отсутствии индексов это все одинаково выливается в тупой скан.

рис.2

При создании индексов Скрипт 4, 5 parent-child оказывается получше, но все равно несильно 46:54.

рис.3

Но мы-то с вами знаем, что первый запрос должен быть существенно выигрышней. Для самоутешения я создал кластерный индекс по hidу, а id и parent_id сделал обычными. Соотношение сразу изменилось в 33:67 J Опишите самый дорогой способ определения постоянной Планка (с) "Физики шутят". Это еще не предел, запрос с hidом можно измордовать так, что он вообще не поднимется. Ибо главное – это душевное равновесие, когда теория согласуется с экспериментом. Если же этого не происходит, тем хуже для эксперимента JJ

Comments

• Anonymous
  May 27, 2009
  PingBack from http://microsoft-sharepoint.simplynetdev.com/hierarchyid-%d0%b8-parent-child/

• Anonymous
  June 02, 2009
  В предыдущей серии картины (http://blogs.msdn.com/alexejs/archive/2009/05/27/hierarchyid-parent-child.aspx)