Share via

HierarchyID и parent-child

  • Article

Проблема, однако, состоит в том, что запрос Скрипт 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? Давайте не будем ограничиваться тупым сканом, а создадим индексы. Мы же видим в плане, как ему их хочется:

 

image001

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

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

id

hid1

fullName

parent_id

isDir

hid

63

/28/

c:\Demo\ConsoleApplication1

1

1

0xC390

64

/28/1/

c:\Demo\ConsoleApplication1\ConsoleApplication1.csproj

63

0

0xC39580

65

/28/2/

c:\Demo\ConsoleApplication1\ConsoleApplication1.sln

63

0

0xC39680

66

/28/3/

c:\Demo\ConsoleApplication1\ConsoleApplication1.suo

63

0

0xC39780

67

/28/4/

c:\Demo\ConsoleApplication1\Program.cs

63

0

0xC39840

68

/28/5/

c:\Demo\ConsoleApplication1\bin

63

1

0xC398C0

69

/28/5/1/

c:\Demo\ConsoleApplication1\bin\Debug

68

1

0xC398D6

70

/28/5/1/1/

c:\Demo\ConsoleApplication1\bin\Debug\ConsoleApplication1.exe

69

0

0xC398D6B0

71

/28/5/1/2/

c:\Demo\ConsoleApplication1\bin\Debug\ConsoleApplication1.pdb

69

0

0xC398D6D0

72

/28/5/1/3/

c:\Demo\ConsoleApplication1\bin\Debug\ConsoleApplication1.vshost.exe

69

0

0xC398D6F0

73

/28/5/1/4/

c:\Demo\ConsoleApplication1\bin\Debug\ConsoleApplication1.vshost.exe.manifest

69

0

0xC398D708

74

/28/6/

c:\Demo\ConsoleApplication1\obj

63

1

0xC39940

75

/28/6/1/

c:\Demo\ConsoleApplication1\obj\Debug

74

1

0xC39956

76

/28/6/1/1/

c:\Demo\ConsoleApplication1\obj\Debug\ConsoleApplication1.csproj.FileListAbsolute.txt

75

0

0xC39956B0

77

/28/6/1/2/

c:\Demo\ConsoleApplication1\obj\Debug\ConsoleApplication1.exe

75

0

0xC39956D0

78

/28/6/1/3/

c:\Demo\ConsoleApplication1\obj\Debug\ConsoleApplication1.pdb

75

0

0xC39956F0

79

/28/6/1/4/

c:\Demo\ConsoleApplication1\obj\Debug\TempPE

75

1

0xC3995708

80

/28/7/

c:\Demo\ConsoleApplication1\Properties

63

1

0xC399C0

81

/28/7/1/

c:\Demo\ConsoleApplication1\Properties\AssemblyInfo.cs

80

0

0xC399D6

82

/29/

c:\Demo\ConsoleApplication2

1

1

0xC3B0

Скрипт 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%'

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

id

hid1

fullName

parent_id

isDir

size

hid

63

/28/

c:\Demo\ConsoleApplication1

1

1

0

0xC390

64

/28/1/

c:\Demo\ConsoleApplication2\ConsoleApplication1.csproj

82

0

2511

0xC39580

65

/28/2/

c:\Demo\ConsoleApplication2\ConsoleApplication1.sln

82

0

927

0xC39680

66

/28/3/

c:\Demo\ConsoleApplication2\ConsoleApplication1.suo

82

0

11264

0xC39780

67

/28/4/

c:\Demo\ConsoleApplication2\Program.cs

82

0

800

0xC39840

68

/28/5/

c:\Demo\ConsoleApplication2\bin

82

1

0

0xC398C0

69

/28/5/1/

c:\Demo\ConsoleApplication2\bin\Debug

68

1

0

0xC398D6

70

/28/5/1/1/

c:\Demo\ConsoleApplication2\bin\Debug\ConsoleApplication1.exe

69

0

5632

0xC398D6B0

71

/28/5/1/2/

c:\Demo\ConsoleApplication2\bin\Debug\ConsoleApplication1.pdb

69

0

13824

0xC398D6D0

72

/28/5/1/3/

c:\Demo\ConsoleApplication2\bin\Debug\ConsoleApplication1.vshost.exe

69

0

14328

0xC398D6F0

73

/28/5/1/4/

c:\Demo\ConsoleApplication2\bin\Debug\ConsoleApplication1.vshost.exe.manifest

69

0

490

0xC398D708

74

/28/6/

c:\Demo\ConsoleApplication2\obj

82

1

0

0xC39940

75

/28/6/1/

c:\Demo\ConsoleApplication2\obj\Debug

74

1

0

0xC39956

76

/28/6/1/1/

c:\Demo\ConsoleApplication2\obj\Debug\ConsoleApplication1.csproj.FileListAbsolute.txt

75

0

322

0xC39956B0

77

/28/6/1/2/

c:\Demo\ConsoleApplication2\obj\Debug\ConsoleApplication1.exe

75

0

5632

0xC39956D0

78

/28/6/1/3/

c:\Demo\ConsoleApplication2\obj\Debug\ConsoleApplication1.pdb

75

0

13824

0xC39956F0

79

/28/6/1/4/

c:\Demo\ConsoleApplication2\obj\Debug\TempPE

75

1

0

0xC3995708

80

/28/7/

c:\Demo\ConsoleApplication2\Properties

82

1

0

0xC399C0

81

/28/7/1/

c:\Demo\ConsoleApplication2\Properties\AssemblyInfo.cs

80

0

1450

0xC399D6

82

/29/

c:\Demo\ConsoleApplication2

1

1

0

0xC3B0

Скрипт 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

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

id

hid1

fullName

parent_id

isDir

hid

63

/28/

c:\Demo\ConsoleApplication1

1

1

0xC390

64

/28/1/

c:\Demo\ConsoleApplication1\ConsoleApplication1.csproj

63

0

0xC39580

65

/28/2/

c:\Demo\ConsoleApplication1\ConsoleApplication1.sln

63

0

0xC39680

66

/28/3/

c:\Demo\ConsoleApplication1\ConsoleApplication1.suo

63

0

0xC39780

67

/28/4/

c:\Demo\ConsoleApplication1\Program.cs

63

0

0xC39840

68

/28/5/

c:\Demo\ConsoleApplication1\bin

63

1

0xC398C0

69

/28/5/1/

c:\Demo\ConsoleApplication1\bin\Debug

68

1

0xC398D6

70

/28/5/1/1/

c:\Demo\ConsoleApplication1\bin\Debug\ConsoleApplication1.exe

69

0

0xC398D6B0

71

/28/5/1/2/

c:\Demo\ConsoleApplication1\bin\Debug\ConsoleApplication1.pdb

69

0

0xC398D6D0

72

/28/5/1/3/

c:\Demo\ConsoleApplication1\bin\Debug\ConsoleApplication1.vshost.exe

69

0

0xC398D6F0

73

/28/5/1/4/

c:\Demo\ConsoleApplication1\bin\Debug\ConsoleApplication1.vshost.exe.manifest

69

0

0xC398D708

74

/28/6/

c:\Demo\ConsoleApplication1\obj

63

1

0xC39940

75

/28/6/1/

c:\Demo\ConsoleApplication1\obj\Debug

74

1

0xC39956

76

/28/6/1/1/

c:\Demo\ConsoleApplication1\obj\Debug\ConsoleApplication1.csproj.FileListAbsolute.txt

75

0

0xC39956B0

77

/28/6/1/2/

c:\Demo\ConsoleApplication1\obj\Debug\ConsoleApplication1.exe

75

0

0xC39956D0

78

/28/6/1/3/

c:\Demo\ConsoleApplication1\obj\Debug\ConsoleApplication1.pdb

75

0

0xC39956F0

79

/28/6/1/4/

c:\Demo\ConsoleApplication1\obj\Debug\TempPE

75

1

0xC3995708

80

/28/7/

c:\Demo\ConsoleApplication1\Properties

63

1

0xC399C0

81

/28/7/1/

c:\Demo\ConsoleApplication1\Properties\AssemblyInfo.cs

80

0

0xC399D6

Скрипт 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ов.

id

hid1

fullName

parent_id

isDir

hid

63

/28/

c:\Demo\ConsoleApplication1

1

1

0xC390

64

/29/1/

c:\Demo\ConsoleApplication2\ConsoleApplication1.csproj

63

0

0xC3B580

65

/29/2/

c:\Demo\ConsoleApplication2\ConsoleApplication1.sln

63

0

0xC3B680

66

/29/3/

c:\Demo\ConsoleApplication2\ConsoleApplication1.suo

63

0

0xC3B780

67

/29/4/

c:\Demo\ConsoleApplication2\Program.cs

63

0

0xC3B840

68

/29/5/

c:\Demo\ConsoleApplication2\bin

63

1

0xC3B8C0

69

/29/5/1/

c:\Demo\ConsoleApplication2\bin\Debug

68

1

0xC3B8D6

70

/29/5/1/1/

c:\Demo\ConsoleApplication2\bin\Debug\ConsoleApplication1.exe

69

0

0xC3B8D6B0

71

/29/5/1/2/

c:\Demo\ConsoleApplication2\bin\Debug\ConsoleApplication1.pdb

69

0

0xC3B8D6D0

72

/29/5/1/3/

c:\Demo\ConsoleApplication2\bin\Debug\ConsoleApplication1.vshost.exe

69

0

0xC3B8D6F0

73

/29/5/1/4/

c:\Demo\ConsoleApplication2\bin\Debug\ConsoleApplication1.vshost.exe.manifest

69

0

0xC3B8D708

74

/29/6/

c:\Demo\ConsoleApplication2\obj

63

1

0xC3B940

75

/29/6/1/

c:\Demo\ConsoleApplication2\obj\Debug

74

1

0xC3B956

76

/29/6/1/1/

c:\Demo\ConsoleApplication2\obj\Debug\ConsoleApplication1.csproj.FileListAbsolute.txt

75

0

0xC3B956B0

77

/29/6/1/2/

c:\Demo\ConsoleApplication2\obj\Debug\ConsoleApplication1.exe

75

0

0xC3B956D0

78

/29/6/1/3/

c:\Demo\ConsoleApplication2\obj\Debug\ConsoleApplication1.pdb

75

0

0xC3B956F0

79

/29/6/1/4/

c:\Demo\ConsoleApplication2\obj\Debug\TempPE

75

1

0xC3B95708

80

/29/7/

c:\Demo\ConsoleApplication2\Properties

63

1

0xC3B9C0

81

/29/7/1/

c:\Demo\ConsoleApplication2\Properties\AssemblyInfo.cs

80

0

0xC3B9D6

82

/29/

c:\Demo\ConsoleApplication2

1

1

0xC3B0

Скрипт 12

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

image002

рис.2

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

image003

рис.3

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

Comments