SQL: Hierarchical structure with n level

Question

I have a hierarchical structure stored in a relational database that is represented in a treeview. Each node has various fields for its properties and knows its parent by ID. This is a parent-child relationship model.

If a node has a child it is represented with a [+] in front of the node's name. By clicking at the [+] you can expand the node and see the nodes children. The children itself have a [+] if they have childnodes as so forth to the lowest level.

A simplified example treeview looks like:

            [+] A Land 
                       [+] A.1 Car
                                   A.1.A Motor 
                                   A.1.B Wheels
            [+] B Sea
                           B.1 Sailing ship
                       [+] B.2 Motorboat
                                   B.2.A Motor
            [+] C Air
                       [+] C.1 Plane
                                   C.1.A Turbine
                                   C.2.B Wheels                                                    

It's possible to set one or multiple filters on various node properties, e.g. show all nodes which have descendants whose name is 'Motor'. The treeview would look like:

            [+] A Land 
                           [+] A.1 Car
                                      A.1.A Motor                                           
            [+] B Sea                                   
                           [+] B.2 Motorboat
                                      B.2.A Motor

As I have a limited count of levels and a little amount of nodes this structure satisfies my needs (with mediocre performance).

Now we want to extend the treeview to n-level depth.

There is the nested sets model, and the performance is great as long as you don't filter things out. This is because the nested sets don't support filtering as far as we know. We also tried the path model (SQL-Servers hierarchyid-datatype), but filtering is slow, if you have a lot of levels.

---

Our path model approach: Imagine you have 20 Levels with a lot of nodes in each level in tbale PMTable, that has a column Path of hierarchyid-datatype. Then you wan't to query (to initalize the TreeView) all the top level nodes that have at least one descendant (must be not a direct descendant, descandant can have every posible level), which apply to a filter (for example: name LIKE '%motor%' AND type = 3, where name and type are columns in the same path-model table). We also stored the zero-based level of the node for simplifying the queries.

The query could be:

SELECT id, name
FROM PMTable WHERE level = 0
AND Path IN
(
  SELECT Path WHERE Path.GetAncestor(Path.GetLevel() - 1)
  FROM PMTable
  WHERE name LIKE '%motor%' AND type = 3
)
ORDER BY name

This query is maybe mediocre performance, but as you can see, also in the top level query you have an expensive subquery, which has to query all nodes from the table that matches the criteria.

But is the user clicks on the small [+] to expand one top level node, you have to query all second level nodes, that has the clicked node as ancestor and also match that filter criteria (contains any level descandants, that matches). If a node itself match that filter criteria (is of type 3 and name includes 'motor'), then you have to display all of its descendants.

These querys are of poor performance in our example.

---

Are there any other models you can prefer or some ideas of getting better performance for this.

Thanks!

Answer 1

many thanks for your efforts. You've been truly helpful. We came up with a combination of the Path-Model and recursive CTEs with additional inserting the parents id in the table to get a little extra performance boost.

Answer 2

Using the Nested Sets model, finding all trees that have a descendant with the name "Motor" should be pretty simple:

SELECT
    P.name    -- Or whatever other columns you need
FROM
    My_Tree D
INNER JOIN My_Tree P ON P.lft <= D.lft AND P.rgt >= D.rgt
WHERE
    D.name = 'Motor'

If you want to include the descendants of that node as well (i.e., the full tree where any member has that name), then you can easily add an OR statement to grab children as well.

Answer 3

I've been using ranges keys for my hierarchies for over 2 decades. We've had massive and numerous alternate hierarchies which have been used for reporting, processing, and/or selection criteria. I've also created a library of functions for quick navigation and utilities.

The following is a quick sample. Keep in mind I manually created the range keys, they are normally created/updated programmatically. Also, I usually have a Presentation Sequence number to control the actual sequence by level during the attribution.

The real beauty is that you can easily aggregate variable depth data without using recursive queries.

The query below lacks all of my helpers because I wanted to illustrate the technique.

Declare @OH table (OH_R1 int,OH_R2 int,OH_Lvl int,OH_Nr int,OH_Pt int,OH_Title varchar(100))
Insert into @OH Select 0,12,1,9,0,'Total'
Insert into @OH Select 1,4,2,100,9,'Land'
Insert into @OH Select 2,4,3,200,100,'Car'
Insert into @OH Select 3,3,4,300,200,'Motor'
Insert into @OH Select 4,4,4,400,200,'Wheels'
Insert into @OH Select 5,8,2,500,9,'Sea'
Insert into @OH Select 6,6,3,600,500,'Sailing Ship'
Insert into @OH Select 7,8,3,625,500,'Motor Boat'
Insert into @OH Select 8,8,4,650,625,'Motor'
Insert into @OH Select 9,12,2,800,9,'Air'
Insert into @OH Select 10,12,3,825,800,'Plane'
Insert into @OH Select 11,11,4,550,825,'Turbine'
Insert into @OH Select 12,12,4,550,825,'Wheele'

-- Show Nested/Filtered Hierarchy
Select A.*
      ,Nested=Replicate('  ',OH_Lvl-1)+OH_Title 
      ,Hits=sum(hits)
 From @OH A 
 Join (Select OH_R1,Hits=1 from @OH where OH_Title like '%motor%' and OH_Lvl=4) B on (B.OH_R1 between A.OH_R1 and A.OH_R2)
 Group by A.OH_R1,A.OH_R2,A.OH_Lvl,A.OH_Nr,A.OH_Pt,A.OH_Title
 Order by OH_R1


 -- Show Actual Hierarchy
Select * from @OH Order by OH_R1

Returns

OH_R1   OH_R2   OH_Lvl  OH_Nr   OH_Pt   OH_Title    Nested             Hits
0       12      1       9       0       Total       Total               2
1       4       2       100     9       Land          Land              1
2       4       3       200     100     Car             Car             1
3       3       4       300     200     Motor             Motor         1
5       8       2       500     9       Sea            Sea              1
7       8       3       625     500     Motor Boat        Motor Boat    1
8       8       4       650     625     Motor                Motor      1

Answer 4

Since SQL Server 2005, T-SQL developers are able to execute recursive queries with CTE structures for hierarchy data

If you check the referred SQL tutorial, you will find sample data and sample CTE queries and level of hierarchy in the last screenshot

A recursive CTE is formed as follows in SQL Server

WITH cte AS (
   {Anchor_Query}
   UNION ALL
   {Recursive part joining to cte}
 )
 SELECT * FROM cte

By adding initial level of hierarch as 1 in the anchor Select statement in CTE, and increasing this by 1 in the recursive part, you will finally end up with all hierarchy levels in your resultant dataset

Please check the sample SQL tutorial