SQL Server 2008 new data type HierarchyID

תאריך: 15 ינואר, 2012 | מאת: אסף אביב

One of the coolest and fantastic new features of SQL Server 2008 is the new data type HierarchyID. You’ve probably been confronted with a scenario in which you needed to data tree of some sort, and you’ve probably struggled with joins, recursive operations, and other strategies in the past. With this new type you can implement tree structures with ease, making use of the best indexing strategy.

The HierarchyID data type allows you to construct relationships among data elements within a table, specifically to represent a position in a hierarchy.

Some Facts:

-New system CLR type supporting trees.

-Extremely compact – Internally stored as varbinary <= 900 bytes.

-Easy to understand – Holds a path that provides a topological sort of a tree.

-Has a set of methods that provide tree functionality: GetAncestor, GetDescendant,  GetLevel, GetRoot, IsDescendant, Parse, Read, Reparent, ToString, Write.

-Efficient querying that can utilize depth-first and breadth-first indexes.

The hierarchyid data type has the following limitations:

-A column of type hierarchyid does not automatically represent a  tree. It is up to the application to generate and assign hierarchyid values in such a way that the desired relationship between rows is reflected in the values. Some applications might not even want to have a column of type hierarchyid represent a tree. Perhaps the values are references to location in a hierarchy defined in another table.

-It is up to the application to manage concurrency in generating and assigning hierarchyid values. There is no guarantee that hierarchyid values in a column are unique unless the application uses a unique key constraint or enforces uniqueness itself through its own logic.

-Hierarchical relationships represented by hierarchyid values are not enforced like a foreign key relationship. It is possible and sometimes appropriate to have a hierarchical relationship where A has a child B, and then A is deleted leaving B with a relationship to a nonexistent record. If this behavior is unacceptable, the application must query for descendants before deleting parents.

Methods provided are as follows:

GetAncestor: Returns a HierarchyID that represents the n^th ancestor of this HierarchyID node.

GetDescendant: Returns a child node of this HierarchyID node.

GetLevel: Returns an integer that represents the depth of this HierarchyID node in the overall hierarchy.

GetRoot: Returns the root HierarchyID node of this hierarchy tree. Static.

IsDescendant: Returns true if the passed-in child node is a descendant of this HierarchyID node.

Parse: Converts a string representation of a hierarchy to a HierarchyID value. Static.

Reparent: Moves a node of a hierarchy to a new location within the hierarchy.

ToString: Returns a string that contains the logical representation of this HierarchyID.

Indexing Strategies :

There are two strategies for indexing hierarchical data:

-Depth-first

A depth-first index, rows in a subtree are stored near each other. For example, all employees that report through a manager are stored near their managers' record- Useful for querying subtrees.

-Breadth-first

A breadth-first stores the rows each level of the hierarchy together. For example, the records of employees who directly report to the same manager are stored near each other – Useful for querying immediate children.

Everyone found that genius but a lot broke their teeth using it in real life so let's 

Try it:

Let's assume we already have the following products 

The Idea is to represent a product tree:

First, we need to create a table to store the product hierarchy:

   1: CREATE TABLE dbo.ProductTree

   2: (

   3: [hierarchyid] [hierarchyid] NOT NULL,

   4: [Node] [nvarchar](4000) NOT NULL, --String representation of the HierarchyID.

   5: [ProductID] [int] NOT NULL

   6: )ON [PRIMARY]

   7: GO

   8: CREATE UNIQUE CLUSTERED INDEX [IX_ProductTree] ON dbo.ProductTree

   9: (

  10:  [hierarchyid],

  11:  [ProductID]

  12: )

  13: GO

Let's start building the tree! First, the root: 

   1: --Insert The Root -> Product

   2: INSERT INTO dbo.ProductTree

   3: (hierarchyid, Node, ProductID)

   4: VALUES

   5: (hierarchyid::GetRoot(), hierarchyid::GetRoot().ToString(), 1)

   6: GO

Notice the call GetRoot() to get the root node reference.

So now we have the root node, now we need to add the first child:

   1: --Insert First Child(IPhone)

   2: DECLARE @ProductID INT = 2 -- The First Child  = iPhone

   3: DECLARE @hierarchyid HIERARCHYID

   4: DECLARE @Parenthierarchyid HIERARCHYID

   5:

   6: --Get Parent hierarchyid

   7: SELECT @Parenthierarchyid = hierarchyid

   8: FROM dbo.ProductTree

   9: WHERE ProductID = 1

  10:

  11: --Get the hierarchyid

  12: SELECT @hierarchyid = @Parenthierarchyid.GetDescendant(NULL,NULL)

  13: FROM dbo.ProductTree

  14:

  15: --Insert First Child(IPhone)

  16: INSERT INTO dbo.ProductTree

  17: (hierarchyid, Node, ProductID)

  18: VALUES

  19: (@hierarchyid, @hierarchyid.ToString(), @ProductID)

  20:  Go

Notice the call GetDescendant() to get the descendant of a given node. 

It has a great significance in terms of finding the new descendant position 

Get the descendants etc.

We'll be inserting the "Mac", in the same level, below "Product" 

And next to "iPhone".

   1: --Insert Second Child(Mac)

   2: DECLARE @ProductID INT = 3 -- The Second Child = Mac

   3: DECLARE @FirstChildhierarchyid HIERARCHYID

   4: DECLARE @hierarchyid HIERARCHYID

   5: DECLARE @Parenthierarchyid HIERARCHYID

   6: --Get First Child hierarchyid and Parent hierarchyid

   7: SELECT @FirstChildhierarchyid = hierarchyid,

   8:        @Parenthierarchyid = hierarchyid.GetAncestor(hierarchyid.GetLevel())

   9: FROM dbo.ProductTree

  10: WHERE ProductID = 2 -- iPhone

  11: --Get the hierarchyid

  12: SELECT @hierarchyid = @Parenthierarchyid.GetDescendant(@FirstChildhierarchyid,NULL)

  13: FROM dbo.ProductTree

  14: --Insert Second Child(Mac)

  15: INSERT INTO dbo.ProductTree

  16: (hierarchyid, Node, ProductID)

  17: VALUES

  18: (@hierarchyid, @hierarchyid.ToString(), @ProductID)

  19:

  20: Go

Notice the call GetAncestor() to get the ancestor 

Of a given child node by the level (int).

Since we needed to add a new product,

At the same level of the "iPhone" product,

we had to get a node reference next to it, hence the @Parenthierarchyid.GetDescendant(@FirstChildhierarchyid,NULL).

Now let's add a second level child to "iPhone":

   1: --Insert Second Level Child(iPhone 4S)

   2: DECLARE @ProductID INT = 4 -- The Second Level Child = iPhone 4S

   3: DECLARE @hierarchyid HIERARCHYID

   4: DECLARE @Parenthierarchyid HIERARCHYID

   5: --Get the Parent hierarchyid

   6: SELECT @Parenthierarchyid = hierarchyid

   7: FROM dbo.ProductTree

   8: WHERE ProductID = 2 -- iPhone

   9: --Get the hierarchyid

  10: SELECT @hierarchyid = @Parenthierarchyid.GetDescendant(NULL,NULL)

  11: FROM dbo.ProductTree

  12: --Insert Second Level Child(iPhone 4S)

  13: INSERT INTO dbo.ProductTree

  14: (hierarchyid, Node, ProductID)

  15: VALUES

  16: (@hierarchyid, @hierarchyid.ToString(), @ProductID)

  17: Go

Here is the result:

?Notice the path representation and how it all fits in. Pretty neat huh
Conclusion

According performances, you can use the HierarchyID type without hesitation when modeling tree structures in a relational database. That new type fulfills its goal although it's not simple to implement…

...Hope you like this article I will write more about HierarchyID very soon

תגובות אחרונות

• Shay Attiya: הנחתי שמיותר לציין, אבל כנראה שלא. תודה על... (בתגובה ל: Foreign keys and how they help the optimizer)
• יניב אתרוגי: ובאותו הקשר כדאי להזכיר את הנקודה שרצוי שהמפתח... (בתגובה ל: Foreign keys and how they help the optimizer)
• דניאל: יש ממשק פשוט יותר להעביר פקודות לשרת על בסיס... (בתגובה ל: Using Reporting Services as your Software Frontend)
• יוסי חקיקת: תודה רבה תומר!! (בתגובה ל: * Select)
• יוסי חקיקת: תודה רבה אסף!! (בתגובה ל: * Select)
• Tomer Shtrum: נהניתי מאוד, אחלה פוסט. (בתגובה ל: * Select)
• אסף אביב: פשוט תענוג לקרוא את הפוסטים שלך (בתגובה ל: * Select)
• גרי רשף: מסכים עם קודמִי: הנושא מעניין מאוד, אבל קשה לעקוב אחר הדוגמה, לא ברור מה הקוד... (בתגובה ל: Help The Optimizer)
• Lawanda: A little rtaioainlty lifts the quality of the debate here.... (בתגובה ל: SAN Basics and Actual Execution Plans)
• צ'יקו דרורי: Nice one! Tnx (בתגובה ל: CASE Study)