# Faster alternative to scalar UDF with recursion?

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).

-
Did you try recursive CTE ? –  a1ex07 May 12 '12 at 0:58
If you redesign your table to use materialized path instead, your queries will be much faster. –  A-K May 12 '12 at 1:19
Alex, can you explain why? There's no getting around SQL Server having to check the bit value for every ancestor. I don't see how materialized path would speed up walking up the chain. –  influent May 14 '12 at 19:32
Did you check if the indexes are being used? –  MarlonRibunal May 15 '12 at 17:48
Is the IsBilltoCustomer bit likely to change? –  JNK May 15 '12 at 17:50

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.

-
In your example CustomerID 3 is the parent of CustomerID 6. Let's also say that CustomerID 15 is the child of CustomerID 6. I'm looking for the fastest way to get the Billing Master for CustomerID 15, which is 6 in this case because it's the highest member of the hierarchy that's a parent of 15 (or 15 itself) with IsBillToCustomer = 1. –  influent May 14 '12 at 19:01
CustomerID 15 is a sub-child of CustomerID 6? So, First Level (Main parent) is CustomerID 3 > Second Level is CustomerID 6 > Third Level is CustomerID 15. How many levels (max) do you have on the hierarchy? –  MarlonRibunal May 15 '12 at 17:45
Please check this fiddle if it's close enough: sqlfiddle.com/#!3/b27bc/4 Please try indexes as the query is doing multiple table scans. –  MarlonRibunal May 15 '12 at 17:55
Your schema script looks correct. There could be an infinite number of levels but in reality there will never be more than 10. I'll play around with your scripts as soon as I get a chance, thanks. –  influent May 15 '12 at 23:54

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.

-
+1 for an answer that might be useful to others and thanks for your help. My situation is a lot more complex but it's my bad for oversimplifying it. –  influent May 16 '12 at 21:14

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.

-
I'm glad you found your solution :-) –  MarlonRibunal May 16 '12 at 22:07