Faster alternative to scalar UDF with recursion to walk tree hierarchy?

Question

I have a scalar function that traverses a simple parent-child hierarchy of customers to find the ancestor that's in charge of billing. Here's a simplified version of the schema.

CREATE TABLE Customer (CustomerID int, ParentCustomerID int, IsBillToCustomer bit)

The UDF walks up the chain until it hits the top parent, recording the IsBillToCustomer setting for each customer in the chain, then returns the CustomerID for the highest customer in the chain with IsBillToCustomer = 1. The UDF is fast for each customer, but I need to run reports that return thousands of customers with data associated to their billing master and it takes tens of minutes for so many customers. Is my only alternative to implement SQL Server's hierarchyID data type? Will that even help?

Creating a SQL job that stores the data I need is not a viable solution because the data needs to be as up-to-date as possible and I can't be running a 40-minute CPU-intensive job over and over.

UPDATE: I created a temporary table using HierarchyID and set up some indexes, then used IsDescendantOf in my query, and it still took over 13 minutes (and hammered my CPU's).

Answer 1

Let's start with this. Let us know if it looks something like this. Please edit as necessary. I am adding data into the table:

INSERT INTO Customer (CustomerID, ParentCustomerID, IsBillToCustomer)
select  1   ,   0   ,   0   union all
select  2   ,   0   ,   0   union all
select  3   ,   0   ,   0       union all
select  4   ,   1   ,   0   union all
select  5   ,   2   ,   0   union all
select  6   ,   3   ,   1   union all
select  7   ,   1   ,   1   union all
select  8   ,   2   ,   1   union all
select  9   ,   3   ,   1   union all
select  10  ,   1   ,   0   union all
select  11  ,   2   ,   0   union all
select  12  ,   3   ,   0   union all
select  13  ,   1   ,   0   union all
select  14  ,   2   ,   0   union all
select  15  ,   3   ,   1   union all
select  16  ,   1   ,   1   union all
select  17  ,   2   ,   1   union all
select  18  ,   3   ,   1   union all
select  19  ,   1   ,   0   union all
select  20  ,   2   ,   1   union all
select  21  ,   3   ,   1   union all
select  22  ,   1   ,   1   union all
select  23  ,   2   ,   0   union all
select  24  ,   3   ,   0   union all
select  25  ,   1   ,   1   union all
select  26  ,   2   ,   1   union all
select  27  ,   3   ,   1   union all
select  28  ,   1   ,   1   union all
select  29  ,   2   ,   0   union all
select  30  ,   3   ,   0   union all
select  31  ,   1   ,   0   union all
select  32  ,   2   ,   0   union all
select  33  ,   3   ,   0   union all
select  34  ,   1   ,   1   union all
select  35  ,   2   ,   1   union all
select  36  ,   3   ,   1   union all
select  37  ,   1   ,   1   union all
select  38  ,   2   ,   0   union all
select  39  ,   3   ,   1   union all
select  40  ,   1   ,   1   union all
select  41  ,   2   ,   1   union all
select  42  ,   3   ,   0   union all
select  43  ,   1   ,   0   union all
select  44  ,   2   ,   1   union all
select  45  ,   3   ,   1   union all
select  46  ,   1   ,   1   union all
select  47  ,   2   ,   1   union all
select  48  ,   3   ,   0   union all
select  49  ,   1   ,   0   union all
select  50  ,   2   ,   0   union all
select  51  ,   3   ,   0   union all
select  52  ,   1   ,   0   union all
select  53  ,   2   ,   1   union all
select  54  ,   3   ,   1   union all
select  55  ,   1   ,   1   union all
select  56  ,   2   ,   1   union all
select  57  ,   3   ,   0   union all
select  58  ,   1   ,   1   union all
select  59  ,   2   ,   1   union all
select  60  ,   3   ,   1   union all
select  61  ,   1   ,   0   union all
select  62  ,   2   ,   0   union all
select  63  ,   3   ,   1   union all
select  64  ,   1   ,   1   union all
select  65  ,   2   ,   1   union all
select  66  ,   3   ,   1   union all
select  67  ,   1   ,   0   union all
select  68  ,   2   ,   0   union all
select  69  ,   3   ,   0   union all
select  70  ,   1   ,   0   union all
select  71  ,   2   ,   0   union all
select  72  ,   3   ,   1   union all
select  73  ,   1   ,   1   union all
select  74  ,   2   ,   1   union all
select  75  ,   3   ,   1   union all
select  76  ,   1   ,   0   union all
select  77  ,   2   ,   1   union all
select  78  ,   3   ,   1   union all
select  79  ,   1   ,   1   union all
select  80  ,   2   ,   0   union all
select  81  ,   3   ,   0   union all
select  82  ,   1   ,   1   union all
select  83  ,   2   ,   1   union all
select  84  ,   3   ,   1   union all
select  85  ,   1   ,   1   union all
select  86  ,   2   ,   0   union all
select  87  ,   3   ,   0   union all
select  88  ,   1   ,   0   union all
select  89  ,   2   ,   0   union all
select  90  ,   3   ,   0   union all
select  91  ,   1   ,   1   union all
select  92  ,   2   ,   1   union all
select  93  ,   3   ,   1   union all
select  94  ,   1   ,   1   union all
select  95  ,   2   ,   0   union all
select  96  ,   3   ,   1   union all
select  97  ,   1   ,   1   union all
select  98  ,   2   ,   1   union all
select  99  ,   3   ,   0   union all
select  100 ,   1   ,   0   union all
select  101 ,   2   ,   1   union all
select  102 ,   3   ,   1   union all
select  103 ,   1   ,   1

So, let's run a simple CTE with the data we have. Then from here show us where we are and what we're trying to achieve:

;With Parent(CustomerID, ParentCustomerID, IsBillToCustomer)
As
(
   Select c.CustomerID, c.ParentCustomerID, c.IsBillToCustomer
    from Customer c
    WHERE c.ParentCustomerID = 0
    UNION ALL
  Select c.CustomerID, c.ParentCustomerID, c.IsBillToCustomer
    from Customer c
    inner join Customer p on p.CustomerID=c.ParentCustomerID
)

Select *
  from Parent p

Help us understand the problem. Thanks.

Answer 2

I am not sure if "the highest customer in the chain" for a leaf node means closest to the leaf or closest to the root. If you meant "closest to the leaf", you may want to denormalize and have a FK make sure your denormalized data is always correct:

CREATE TABLE Customer (CustomerID int, ParentCustomerID int, IsBillToCustomer bit,
BillToCustomerID INT NOT NULL, 
FOREIGN KEY(ParentCustomerID, BillToCustomerID) 
REFERENCES Customer(CustomerId, BillToCustomerID),
CHECK((IsBillToCustomer = 1 and BillToCustomerID = CustomerId)
OR (IsBillToCustomer = 0 AND BillToCustomerID <> CustomerID ))

If you denormalize like this, you do not need to traverse up your tree at all. Note that I added two constraints, a foreign key and a check, to ensure that BillToCustomerID is always correct Another way is to use materialized path. I can post it tomorrow if you are interested.

Answer 3

I determined that SQL Server's IsDescendantOf function is way too slow (at least in my environment) and a CPU hog so it wasn't an option for me.

I used this to create a CustomerHierarchy table: http://msdn.microsoft.com/en-us/library/bb677268.aspx

Once I had the hierarchy level of each customer I was able to determine, using subqueries and group-by's, the billing master for each customer in less than 2 seconds total for all 60,000 customers.

Answer 4

It is possible to remove the need to "walk" the tree by creating a "Closure Table". This table does not require any special data type like HierarchyId however it takes time to rebuild such a table (recursively) since it represents the entire tree. Incremental rebuilds should be possible if incremental changes to parent/child can be sensed (TimeStamp field etc).

Google: hierarchy closure tree

A closure table stores the parent/child relationships as Ancestor/Descendant relationships. Querying a single node's ancestors (e.g. parent/grandparent/greatgrandparent/etc) is a single query (indexed by node).

For your case the closure table fields might be named:

DescendantCustomerId, AncestorCustomerId, Level

If there are loops in the tree than you may need

DescendantCustomerId, AncestorCustomerId, MinLevel, MaxLevel

For loops there is some detail in getting the min/max populated correctly (we used a separate recursive CTE).

Example Closure Table Creation

This depth level calculation shown below may not what you need. For example it could be adjusted to show min/max distance up from each descendant's point of view.

-- Create a temp table just to calculate the levels (depth) for each parent.
--
-- Recursively walk the many to many Oav.ObjectHierarchy table and calculate a min and 
-- max since nodes may appear multiple times in different positions under a given parent.
--      
with q as
(
    select 0 as level, r.ParentObjectId, r.ChildObjectId
      from Oav.ObjectHierarchy r            
    where r.ParentObjectId in 
          (   --
              -- Level 0 Root node(s) (nodes without a parent).
              --
              select distinct ParentObjectId
                from Oav.ObjectHierarchy
              where ParentObjectId not in (select ChildObjectId
                                             from Oav.ObjectHierarchy)
          )
    union all
    select Level + 1 as Level, c.ParentObjectId, c.ChildObjectId    -- add children
      from q
      join Oav.ObjectHierarchy c 
        on c.ParentObjectId = q.ChildObjectId           
)    
select ParentObjectId, min(Level) MinLevel, max(level) MaxLevel
  into #tempParentLevels
  from q
 group by ParentObjectId
 order by MinLevel, MaxLevel, ParentObjectId;


-- Create Closure Table
--         
with q as
(
    select 1 as Distance, r.ParentObjectId as Ancestor, r.ChildObjectId as Descendant
      from Oav.ObjectHierarchy r
     where r.ParentObjectId in 
          (   
              select distinct ParentObjectId
                from Oav.ObjectHierarchy
          )
     union all
    --
    -- Add new descendant using _original_ ancestor for a closure tree
    -- 
    select Distance + 1 as Distance, q.Ancestor, c.ChildObjectId as Descendant
      from q
      join Oav.ObjectHierarchy c
        on c.ParentObjectId = q.Descendant -- pull in new descendent
)    
select Ancestor as AncestorObjectId,       
       Descendant as DescendantObjectId,
       count(*) DescendantCount, 
       --
       --  Combine Min/Max Distances in addition to Min/Max Levels
       --
       min(Distance + tpl.MinLevel) as DescendantMinLevel, 
       max(Distance + tpl.MaxLevel) as DescendantMaxLevel,
       sysutcdatetime() as ModifiedUtc
  into #NewObjectHierarchyClosure
  from q      
  join #tempParentLevels tpl
    on Ancestor = tpl.ParentObjectId
 group by Ancestor, Descendant
     ;