Test sub-tree performance in SQL Server

sub-tree performance - setup.sql

/* 
 *   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

sub-tree performance - test.sql

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.