Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Test sub-tree performance in SQL Server
/*
* File illustrating blog post
* Copyright 2012 Michał Poręba
*/
create table Nodes (
nodeId int identity primary key
,nodeParent int
,nodeValue varchar(32)
);
go
create procedure CreateAbcTree @depth int
as
begin
declare @abc table (letter varchar(24))
declare @counter int
set @counter = 0
while @counter < @depth
begin
insert into @abc
select char(ascii(isnull(max(letter),Char(ASCII('A')-1)))+1) from @abc
set @counter = @counter +1
end
insert into Nodes (nodeParent, nodeValue) values (0,'');
with newnode as
(
select convert(varchar(24),letter) letter, 1 as Level from @abc
union all
select convert(varchar(24),nt.letter + abc.letter), Level+1
from newnode nt
inner join @abc abc on nt.Level<@depth
and abc.letter<=char(ascii(right(nt.letter,1)))
--and char(ascii(right(nt.letter,1)))<>'A'
and nt.level<=ascii(right(nt.letter,1))-ascii('A')
)
insert into Nodes (nodeParent, nodeValue)
select 0, letter
from newnode
update T1 set nodeParent = T2.nodeId
from nodes T1
inner join nodes T2
on len(T1.nodevalue)>0 and LEFT(T1.nodeValue, len(T1.nodevalue)-1) = T2.nodeValue
end
go
exec CreateAbcTree 14
create nonclustered index TreeParentIndex on Nodes(nodeParent)
go
--method 1
create function GetTreeWithLoop (
@node int
,@maxDepth int
)
returns @output table (nodeId int, nodeParent int, nodeValue varchar(32), nodeDistance int)
as
begin
declare @tmp table (nodeId int primary key, nodeDistance int)
insert into @tmp (nodeId, nodeDistance)
select nodeId, 0
from nodes where nodeId = @node
declare @level tinyint;
set @level = 0
while
exists(select null from @tmp where nodeDistance = @level)
and (@maxDepth<0 or @level<@maxDepth)
begin
insert into @tmp (nodeId, nodeDistance)
select N.nodeId, @level + 1
from Nodes N
inner join @tmp T on T.nodeDistance = @level and N.nodeParent = T.nodeId
set @level = @level+1
end
insert into @output
select N.nodeId, N.nodeParent, N.nodeValue, T.nodeDistance
from nodes N
inner join @tmp T on N.nodeId = T.nodeId
return
end
--method 2
create function GetTreeWithCte (@node int, @maxDepth int)
returns table
as
return (
with SubTree as
(
select nodeId, nodeParent, nodeValue, 0 as nodeDistance
from nodes
where nodeId = @node
union all
select R.nodeId, R.nodeParent, R.nodeValue, T.nodeDistance+1
from nodes R
inner join SubTree T
on (@maxDepth<0 or T.nodeDistance<@maxDepth)
and R.nodeParent = T.nodeId
)
select * from SubTree
);
go
--method 3
create function GetXmlTree (@node int, @maxLevel int, @level int)
returns xml
with returns null on null input
begin
return (
select
nodeId as [@nodeId]
,@level as [@nodeDistance]
,dbo.GetXmlTree(nodeId, @maxLevel, 1+@level)
from nodes
where (@maxLevel<0 or @level<=@maxLevel)
and (
(@level=0 and nodeId=@node)
or (@level>0 and nodeParent=@node)
)
for xml path('node'), type
)
end
go
create function GetTreeWithXml (@node int, @maxDepth int)
returns @output table (nodeId int, nodeParent int, nodeValue varchar(32), nodeDistance int)
as
begin
declare @xml xml
set @xml = dbo.GetXmlTree(@node,@maxDepth,0)
insert into @output
select N.nodeId, N.nodeParent, N.nodeValue
,xmlNode.value('@nodeDistance', 'int')
from Nodes N
cross apply @xml.nodes('//*[@nodeId]') XmlNodes(xmlNode)
where xmlNode.value('@nodeId','int') = nodeId
return
end
go
--method 4
alter table Nodes add nodeHid HierarchyId
go
update Nodes set nodeHid = hierarchyid::GetRoot()
where nodeParent = 0
declare @tmp table (id int, parentHid HierarchyId)
insert into @tmp
select nodeId, nodeHid from (
select T1.nodeId, T2.nodeHid, ROW_NUMBER() over(partition by t1.nodeParent order by t1.nodeParent, t1.nodeId) as rownum
from Nodes T1
inner join Nodes T2 on T2.nodeHid is not null and T1.nodeParent = T2.nodeId
where T1.nodeHid is null
) numbered where rownum=1
while exists(select null from @tmp)
begin
update N set nodeHid = parentHid.GetDescendant((select max(nodeHid) from nodes I where I.nodeHid.GetAncestor(1) = parentHid), null)
from Nodes N
inner join @tmp T on N.nodeId = T.id
delete from @tmp
insert into @tmp
select nodeId, nodeHid from (
select T1.nodeId, T2.nodeHid, ROW_NUMBER() over(partition by t1.nodeParent order by t1.nodeParent, t1.nodeId) as rownum
from Nodes T1
inner join Nodes T2 on T2.nodeHid is not null and T1.nodeParent = T2.nodeId
where T1.nodeHid is null
) numbered where rownum=1
end
go
create unique nonclustered index TreeHierarchicalIndex on Nodes(nodeHid)
create function GetTreeWithHierarchyId (@node int, @maxDepth int)
returns @output table (nodeId int, nodeParent int, nodeValue varchar(32), nodeDistance int)
as
begin
declare @parent HierarchyId
set @parent = (
select nodeHid
from Nodes
where nodeId = @node
)
insert into @output
select N.nodeId, N.nodeParent, N.nodeValue
, N.nodeHid.GetLevel()-@parent.GetLevel() nodeDistance
from Nodes N
Where N.nodeHid.IsDescendantOf(@parent)=1
and (@maxDepth<0 or N.nodeHid.GetLevel()-@parent.GetLevel()<=@maxDepth)
return
end
DBCC FREEPROCCACHE
DBCC DROPCLEANBUFFERS
declare @testNode int
set @testNode = 14
select COUNT(*) from GetTreeWithLoop(@testNode,-1)
-- DBCC FREEPROCCACHE can impact performance on your Production Servers.
-- It is used here on a Test Machine to generate the results so we can compare fairly.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.