T. Martin T. Martin - 2 years ago 100
MySQL Question

SQL: Hierarchical structure with n level

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
SELECT Path WHERE Path.GetAncestor(Path.GetLevel() - 1)
WHERE name LIKE '%motor%' AND type = 3

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.


Answer Source

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 (
   {Recursive part joining to 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

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download