Handling the Tree Path Request

Downloads
103317.zip

One of the most practical models available in SQL Server to represent trees and hierarchies, such as an Employees hierarchy, is known as the enumerated path model. In this model you add two attributes to the table. One attribute holds an enumerated path of all node IDs leading to the current node, and another attribute holds the level, or distance, from the root node. To implement this model, you can create your own custom solution in any version of SQL Server, or you can use the built-in HIERARCHYID data type introduced in SQL Server 2008. I covered both approaches in detail in previous articles. I covered the custom solution in “Maintaining Hierarchies” and the solution based on the HIERARCHYID data type in “HierarchyID” and “SQL Server 2008’s HierarchyID, Part 2.”

The queries you would write to address common requests against trees and hierarchies implemented based on the enumerated path model are quite intuitive and straightforward. The intuitive queries you would write to address some of the requests, such as returning a subtree (e.g., returning all subordinates of a given manager), run very efficiently if you create the correct indexes. However, the intuitive queries you would write to address the common path request (e.g., returning the chain of management leading to a given employee) are optimized very inefficiently. The path request is the focus of this article; I explain why the intuitive queries addressing this request are optimized inefficiently, and I provide alternative solutions that perform quite well.

The sample data that I use in my queries are two tables called Tree1 and Tree2, which you create and populate by running the code in Listing 1. Note that the code takes a few minutes to run because it populates each of the tables with more than a million rows. The code in Listing 1 first creates an auxiliary table of numbers called Nums with a column called n; the code later uses the table to populate Tree1 and Tree2.

Tree1 is implemented based on the custom enumerated path model. It has the following attributes: nodeid (integer node ID such as an employee ID), filler (character 200-byte filler representing various attributes you would normally have, such as employee name or salary), mpath (character materialized enumerated path—e.g., '.1.3.7.9.' for node 9, which is a child of 7, which is a child of 3, which is a child of 1, which is the root node), and lvl (integer level in the tree, with 0 assigned to the root node, 1 to the children of the root node, etc.). Tree2 is implemented using the HIERARCHYID data type in SQL Server 2008. It has the attributes nodeid, filler, hid (of the HIERARCHYID data type), and lvl.

The code in Listing 1 also creates indexes to support various queries against the trees. The clustered index is created on the path column. This index will potentially support requests that are handled in a depth-first manner. One nonclustered index is created on (lvl, path) to potentially support requests that are handled in a breadth-first manner. Another nonclustered index is created on the nodeid attribute to enforce the primary key and to support requests for a particular node. Note that to follow best practices you would typically want to define UNIQUE constraints instead of explicitly creating unique indexes like I did. Of course, the UNIQUE constraints will be enforced behind the scenes with unique indexes, and in terms of performance discussions, which is our focus, it makes no difference.

Querying the Trees

Next, I demonstrate queries against trees and discuss their performance. To measure I/O cost, CPU time, and elapsed time, you need to turn on STATISTICS IO and STATISTICS TIME in your session by running the following code:

SET STATISTICS IO ON;
SET STATISTICS TIME ON;

Also, to make the comparisons between the solutions fair, clear the data cache before running each solution by running the following code:

CHECKPOINT;
DBCC DROPCLEANBUFFERS;

Efficient Handling of the Subtree Request

In this section I demonstrate requests for which the intuitive queries are actually handled very efficiently. Consider the subtree request in which you are given the ID of a node, and you need to return that node and all of its descendants. An example of such a request against an Employees hierarchy would be returning all subordinates—direct and indirect—of a given manager. With our sample data, you are supposed to write queries against Tree1 and Tree2 that return the subtree of some node (e.g., the one with node ID 11111). The desired outputs of the queries against Tree1 and Tree2 are shown in abbreviated forms in Figure 1 and Figure 2, respectively.

Here’s an intuitive query to address this request against Tree1:

SELECT C.nodeid, C.lvl, C.mpath, C.filler
FROM dbo.Tree1 AS P
  JOIN dbo.Tree1 AS C
    ON P.nodeid = 11111
    AND C.mpath LIKE P.mpath + '%';

This query joins two instances of the table—one representing the parent (aliased as P), and one representing the child (aliased as C). The query filters only one row from P—the one for the root node 11111. The query returns all rows from C representing descendants of P—the rows where the path starts with the root’s path (C.mpath LIKE P.mpath + '%'). Figure 3 shows the execution plan for this query.

The query is optimized very efficiently mainly because of the depth-first clustered index created on the mpath attribute. The plan first performs a seek operation in the nonclustered index created on nodeid to retrieve the path of the root node. Then, the plan performs a seek and partial range scan in the clustered index to retrieve all qualifying members of the subtree. The beauty of this plan is that all members of the subtree are organized in a consecutive range of rows in the leaf level of the clustered index; therefore, only the qualifying rows are scanned. The first Compute Scalar operator computes based on the LIKE predicate the applicable LikeRangeStart and LikeRangeEnd values. Then, the range scan at the leaf of the clustered index is based on the following predicates: Start: \\[tempdb\\].\\[dbo\\].\\[Tree1\\].mpath > Scalar Operator(\\[Expr1008\\]), End: \\[tempdb\\].\\[dbo\\].\\[Tree1\\].mpath < Scalar Operator(\\[Expr1009\\]), where Expr1008 represents the start of the range, and Expr1009 represents the end of the range. The performance measures that I got for this query are:

logical reads: 15, CPU: 16, elapsed time: 304

Of course, your mileage may vary depending on your hardware environment.

The query against Tree2 is very similar, but instead of using the LIKE predicate to identify descendants, you use the IsDescendantOf method of the HIERARCHYID data type:

SELECT C.nodeid, C.lvl, C.hid.ToString() AS cpath, C.filler
FROM dbo.Tree2 AS P
  JOIN dbo.Tree2 AS C
    ON P.nodeid = 11111
    AND C.hid.IsDescendantOf(P.hid) = 1;

Figure 4 shows the execution plan for this query.

As you can see, this plan is very similar to the one in Figure 3. Also here, the depth-first clustered index created on the hid attribute ensures that all members of the same subtree reside in a consecutive range of the clustered index leaf level. The Compute Scalar operator computes the maximum possible value in the subtree of the given root: \\[Expr1005\\] = Scalar Operator(\\[tempdb\\].\\[dbo\\].\\[Tree2\\].\\[hid\\] as \\[P\\].\\[hid\\].DescendantLimit()), and then the predicates used for the range scan in the clustered index are: Start: \\[tempdb\\].\\[dbo\\].\\[Tree2\\].hid >= Scalar Operator(\\[tempdb\\].\\[dbo\\].\\[Tree2\\].\\[hid\\] as \\[P\\].\\[hid\\]), End: \\[tempdb\\].\\[dbo\\].\\[Tree2\\].hid <= Scalar Operator(\\[Expr1005\\]). The performance measures that I got for this query are:

logical reads: 10, CPU: 16, elapsed time: 242

As you can see, in both cases the queries run in less than a second, and they cost very little in terms of I/O and CPU time.

Inefficient Handling of the Path Request

Consider the request to return all members of the path leading to a given node (e.g., node 1111111). Figure 5 and Figure 6 show the desired outputs of the queries against Tree1 and Tree2, respectively. An example of such a request is returning the managers in the management chain leading to a given employee. The intuitive queries you would write to handle the path request are very similar to the queries handling the subtree request. You use the same predicates to identify the relationship between ancestors and descendants (members of P and members of C, respectively). The difference is that in the subtree request you filter only one ancestor row from P and return all matching descendants from C, whereas in the path request you filter only one descendant row from C, and return all matching ancestors from P.

Here’s the query against Tree1 that returns information about members of the path leading to node 1111111:

SELECT P.nodeid, P.lvl, P.mpath, P.filler
FROM dbo.Tree1 AS P
  JOIN dbo.Tree1 AS C
    ON C.nodeid = 1111111
    AND C.mpath LIKE P.mpath + '%';

Although the logic of this path query is very similar to the logic of the subtree query, the performance is quite different. In the subtree case, the rows of all members of the same subtree are stored in a consecutive range in the leaf level of the depth-first index. In the path case, the qualifying rows are spread all over the place across the leaf. Figure 7 shows the execution plan for the path query.

The plan performs an index seek operation against the index on nodeid to retrieve the path for the input node. But then the plan performs a full scan of the clustered index, filtering the qualifying rows during the scan. Because the table is quite large, this full scan is very slow. Here are the performance measures that I got for this query:

logical reads: 65551, CPU: 1248, elapsed time: 31527

Here’s the query handling the path request against Tree2:

SELECT P.nodeid, P.lvl, P.hid.ToString() AS cpath, P.filler
FROM dbo.Tree2 AS P
  JOIN dbo.Tree2 AS C
    ON C.nodeid = 1111111
    AND C.hid.IsDescendantOf(P.hid) = 1;

Again, the logic is very similar to that of the subtree query, but not the performance. Figure 8 shows the execution plan for this query.

Similar to the query against Tree1, the qualifying rows are spread across the leaf of the depth-first clustered index created on hid. There is a bit of improvement here compared with the execution plan in Figure 7. Here, the optimizer scans all ancestor rows where the hid value is smaller than that of the input descendant node’s hid value (End: \\[tempdb\\].\\[dbo\\].\\[Tree2\\].hid <= Scalar Operator(\\[tempdb\\].\\[dbo\\].\\[Tree2\\].\\[hid\\] as \\[C\\].\\[hid\\])). If you think about it, a node with a greater hid value of the input node cannot be its ancestor. This means that on average, half the rows in the table would need to be scanned—not all rows. Still, this plan is very inefficient. Here are the performance measures I got for this query:

logical reads: 48727, CPU: 6661, elapsed time: 24458

As you can see, both queries handling the path request are very slow. The one against Tree1 ran for about half a minute, and the one against Tree2 for 24 seconds. Again, your mileage may vary depending on your hardware, but regardless, the aforementioned solutions for the path request are optimized inefficiently.

Efficient Handling of the Path Request

The key to writing an efficient solution to handle the path request is to realize that in the enumerated path model, you have one attribute that already contains information about all the nodes in the path leading to the current node. In Tree1 the mpath value of the input node contains the actual node IDs of all members of the path leading to the current node. In Tree2, the hid value of the input node contains the HIERARCHYID values of all members of the path leading to the current node.

So, to handle the path request against Tree1 efficiently, you can develop a function that accepts a separated list of values and a separator as inputs and returns a table result with the individual elements (call the function dbo.Split). You can then provide the mpath value of the input node and '.' as the inputs to the function, and join the result of the function with Tree1 to return information about the members of the path. The function can be implemented either with T-SQL or with the CLR. The latter implementation is more efficient; therefore I provide the definition of the Split function using C# in Listing 2. For details about the Split function, see “More Options for Handling Arrays as Inputs.”

After the function deploys, you can use the following query to address the path request against Tree1:

SELECT T.nodeid, T.lvl, T.mpath, T.filler
FROM dbo.Split((SELECT SUBSTRING(mpath, 2, LEN(mpath) - 2)
                FROM dbo.Tree1
                WHERE nodeid = 1111111), '.') AS K
  JOIN dbo.Tree1 AS T
    ON T.nodeid = K.element;

Figure 9 shows the execution plan for this query.

The plan uses an index seek operation against the index on nodeid to retrieve the mpath value of the input node. The plan then invokes the Split function to split the path into its individual elements. Then, the plan performs an index seek operation in the index on nodeid for each member of the path. Finally, the plan performs a key look for each qualifying member to retrieve the requested member’s attributes from the data row. Here are the performance measures I got for this query:

logical reads: 92, CPU: 0, elapsed time: 388

As you can see, the improvement is dramatic.

You don’t need the Split function for the path request against Tree2. You do need to invoke the GetAncestor method of the HIERARCHYID data type for each level in the input node’s path, providing the level as input (0 for root, 1 for child of root, 2 for grandchild, etc.). To obtain a row with the level number for each level in the input node’s path, you can query the Nums auxiliary table you created earlier by running the code in Listing 1. Note that the Nums table has values starting with 1, whereas the level of a node is expressed in 0-based offset. So you need to filter the numbers where n - 1 is smaller than or equal to the input node’s level, and provide n - 1 as the input to the GetAncestor method. Finally, once you obtain the hid values of all members of the input node’s path, you can query the Tree2 table to retrieve other attributes of those members. Here’s the complete solution query:

SELECT P.nodeid, P.lvl, P.hid.ToString() AS cpath, P.filler
FROM dbo.Tree2 AS C
  JOIN dbo.Nums
    ON C.nodeid = 1111111
   AND n <= C.lvl + 1
  JOIN dbo.Tree2 AS P
    ON P.hid = C.hid.GetAncestor(n - 1);

Note that even though I mentioned earlier that you need to return all rows from Nums where n - 1 <= C.lvl, I used the expression n <= C.lvl + 1. The two expressions are logically equivalent; however, the former is not a search argument (SARG) because it applies manipulation to the filtered column, whereas the latter is a SARG. So only the latter expression can efficiently use the index on column n. Figure 10 shows the execution plan for this query.

As you can see, the plan is very efficient. The plan starts by performing an index seek operation against the clustered index on hid to retrieve the input node’s path and lvl values. The plan then performs a partial scan in the index on Nums.n to retrieve the numbers representing the levels of the members of the path. Finally, for each level, the plan performs an index seek operation against the clustered index on hid to retrieve the attributes requested for the members. Here are the performance measures I got for this query:

logical reads: 44, CPU: 0, elapsed time: 330

Again, as you can see, this query performs dramatically better than the original version.

Creative Query Tuning

Query tuning involves much more than just arranging the correct physical environment (e.g., good indexes). The intuitive query that handles a given task is not necessarily the most efficient query. Sometimes without any changes in the physical environment, you can get better performance by using a different query. It boils down to understanding why a given query doesn’t perform well, how the optimizer works, and which querying elements lend themselves to better optimization. In this article I focus on handling requests against trees. For some requests (e.g., the subtree request) the intuitive query performs quite well, but for the path request the intuitive solution is extremely inefficient. With some creativity, you can come up with solutions to the path request that are handled very efficiently.

Listing 1: Code to Create and Populate Tree1 and Tree2

SET NOCOUNT ON;

USE tempdb;

GO

 

-- Creating and Populating Auxiliary Table of Numbers

IF OBJECT_ID('dbo.Nums', 'U') IS NOT NULL DROP TABLE dbo.Nums;

 

CREATE TABLE dbo.Nums(n INT NOT NULL PRIMARY KEY);

DECLARE @max AS INT, @rc AS INT;

SET @max = 1000000;

SET @rc = 1;

 

INSERT INTO Nums VALUES(1);

WHILE @rc * 2 <= @max

BEGIN

  INSERT INTO dbo.Nums SELECT n + @rc FROM dbo.Nums;

  SET @rc = @rc * 2;

END

 

INSERT INTO dbo.Nums

  SELECT n + @rc FROM dbo.Nums WHERE n + @rc <= @max;

GO

 

-- Code to create Tree1 using custom materialized path

IF OBJECT_ID('dbo.Tree1', 'U') IS NOT NULL

  DROP TABLE dbo.Tree1;

GO

CREATE TABLE dbo.Tree1

(

  nodeid INT          NOT NULL,

  filler CHAR(200)    NOT NULL DEFAULT('a'),

  mpath  VARCHAR(896) NOT NULL,

  lvl    INT          NOT NULL,

  CONSTRAINT PK_Tree1 PRIMARY KEY NONCLUSTERED(nodeid)

);

 

CREATE UNIQUE CLUSTERED INDEX idx_ucl_mpath        -- depth first

  ON dbo.Tree1(mpath);

 

CREATE UNIQUE NONCLUSTERED INDEX idx_unc_lvl_mpath -- breadth first

  ON dbo.Tree1(lvl, mpath);

GO

 

-- Code to populate Tree1

-- Total number of rows: SELECT (POWER(@num_children, @num_levels) - 1) / (@num_children - 1);

DECLARE

  @num_levels   AS INT = 7,

  @num_children AS INT = 10; -- number of direct children per single parent

 

WITH MyTree AS

(

  SELECT

    1 AS nodeid,

    1 AS pos_in_level,

    CAST('.1.'AS VARCHAR(896)) AS mpath,

    0 AS lvl,

    1 AS cnt

 

  UNION ALL

 

  SELECT

    CAST(P.cnt + (P.pos_in_level - 1) * @num_children + n AS INT) AS nodeid,

    CAST((P.pos_in_level - 1) * @num_children + n AS INT) AS pos_in_level,

    CAST(P.mpath

           + CAST(P.cnt + (P.pos_in_level - 1) * @num_children + n AS VARCHAR(10))

           + '.'

         AS VARCHAR(896)) AS mpath,

    P.lvl + 1 AS lvl,

    P.cnt + POWER(@num_children, P.lvl + 1) AS cnt

  FROM MyTree AS P

    CROSS JOIN dbo.Nums

  WHERE P.lvl < @num_levels - 1

    AND n <= @num_children

)

INSERT INTO dbo.Tree1 WITH (TABLOCK) (nodeid, mpath, lvl)

  SELECT nodeid, mpath, lvl

  FROM MyTree

  ORDER BY nodeid;

GO

 

-- Code to create Tree2 using HIERARCHYID datatype

IF OBJECT_ID('dbo.Tree2', 'U') IS NOT NULL

  DROP TABLE dbo.Tree2;

GO

CREATE TABLE dbo.Tree2

(

  nodeid INT         NOT NULL,

  filler CHAR(200)   NOT NULL DEFAULT('a'),

  hid    HIERARCHYID NOT NULL,

  lvl AS hid.GetLevel() PERSISTED,

  CONSTRAINT PK_Tree2 PRIMARY KEY NONCLUSTERED(nodeid)

);

 

CREATE UNIQUE CLUSTERED INDEX idx_ucl_hid        -- depth first

  ON dbo.Tree2(hid);

 

CREATE UNIQUE NONCLUSTERED INDEX idx_unc_lvl_hid -- breadth first

  ON dbo.Tree2(lvl, hid);

GO

 

-- Code to populate Tree2

DECLARE

  @num_levels   AS INT = 7,

  @num_children AS INT = 10;

 

WITH MyTree AS

(

  SELECT

    1 AS nodeid,

    1 AS pos_in_level,

    CAST('/' AS VARCHAR(MAX)) AS cpath,

    0 AS lvl,

    1 AS cnt

 

  UNION ALL

 

  SELECT

    CAST(P.cnt + (P.pos_in_level - 1) * @num_children + n AS INT) AS nodeid,

    CAST((P.pos_in_level - 1) * @num_children + n AS INT) AS pos_in_level,

    CAST(P.cpath + CAST(n AS VARCHAR(10)) + '/' AS VARCHAR(MAX)) AS cpath,

    P.lvl + 1 AS lvl,

    P.cnt + POWER(@num_children, P.lvl + 1) AS cnt

  FROM MyTree AS P

    CROSS JOIN dbo.Nums

  WHERE P.lvl < @num_levels - 1

    AND n <= @num_children

)

INSERT INTO dbo.Tree2 WITH (TABLOCK) (nodeid, hid)

  SELECT nodeid, CAST(cpath AS HIERARCHYID) AS hid

  FROM MyTree

  ORDER BY nodeid;

GO

Listing 2: Definition of Split Function in C#

using System;

using System.Data.SqlTypes;

using Microsoft.SqlServer.Server;

using System.Collections;

using System.Collections.Generic;

 

public partial class SplitClass

\\{

  // Struct used in string split functions

  struct row_item

  \\{

    public string item;

    public int pos;

  \\}

 

  // Split array of strings and return a table

  // FillRowMethodName = "ArrSplitFillRow"

  \\[SqlFunction(FillRowMethodName = "ArrSplitFillRow",

   DataAccess = DataAccessKind.None,

   TableDefinition = "pos INT, element NVARCHAR(MAX)")\\]

  public static IEnumerable Split(SqlString inpStr,

      SqlString charSeparator)

  \\{

    string locStr;

    string\\[\\] splitStr;

    char\\[\\] locSeparator = new char\\[1\\];

    locSeparator\\[0\\] = (char)charSeparator.Value\\[0\\];

    if (inpStr.IsNull)

      locStr = "";

    else

      locStr = inpStr.Value;

    splitStr = locStr.Split(locSeparator,

          StringSplitOptions.RemoveEmptyEntries);

    //locStr.Split(charSeparator.ToString()\\[0\\]);

    List SplitString = new List();

    int i = 1;

    foreach (string s in splitStr)

    \\{

      row_item r = new row_item();

      r.item = s;

      r.pos = i;

      SplitString.Add(r);

      ++i;

    \\}

    return SplitString;

  \\}

 

  public static void ArrSplitFillRow(

    Object obj, out int pos, out string item)

  \\{

    pos = ((row_item)obj).pos;

    item = ((row_item)obj).item;

  \\}

\\}