.NET and SQL Recursion

Home / .NET and SQL Recursion

A while back, I wrote an application that processes sales information. These sales actually represent a hierarchy of data because there can be refunds, charge backs, charge backs of charge backs, refunds of refunds, adjustments, and so on and so forth. The way the data processing is handled, though, treating the entire hierarchy as a single transaction is important. This requires a bit of recursion.


I won’t go into much detail in terms of how the data is processed, but with C#/LINQ (EF) it’s relatively straight forward to create a recursive method to populate a hierarchy. Effectively, you have to navigate to the root and then back down the tree to ensure that the entire hierarchy is represented. The Invoices themselves are linked by a single “parent” sales id. This makes the sales look like a tree structure.

Here’s a pretty simple method that will retrieve the tree.

private InvoiceNode GetTree(int invoiceId)
{
    var rootInvoiceId = GetRootParentId(invoiceId);
    var root = _invoiceRepo.Get(x => x.InvoiceId = rootInvoiceId);

    var rootNode = new SaleNode()
    {
        Parent = null,
        InvoiceId = rootInvoiceId,
        Invoice = root
    };

    rootNode.Nodes = GetChildren(rootInvoiceId, rootNode, 1);
    return rootNode;
}

private int GetRootParentId(int invoiceId)
{
    var returnValue = invoiceId;
    var hasNext = true;
    do
    {
        var nextId = _invoiceRepo.Get(x => x.Id == returnValue).Select(x => x.OriginalInvoiceId).FirstOrDefault();
        returnValue = nextId.HasValue ? nextId.Value : returnValue;
        hasNext = nextId.HasValue;
    }
    while (hasNext);
    return returnValue;
}

private List<InvoiceNode> GetChildren(int invoiceId, InvoiceNode parent, int depth)
{
    // Updated method so excluding removed is optional
    var exp = excludeRemoved ? (Expression<Func<Invoice, bool>>)(x => x.ParentInvoiceId.HasValue && x.ParentInvoiceId== invoiceId);
    var query = _invoiceRepo.GetUntracked(exp);
    var list = query.ToList();

    var nodes = new List<InvoiceNode>();
    
    foreach (var invoice in list) {
        var newNode = new InvoiceNode()
        {
            Parent = parent,
            InvoiceId = invoice.InvoiceId,
            Invoice = invoice,
            Depth = depth
        };

        nodes.Add(newNode);
    }

    foreach (var node in nodes)
    {
        node.Nodes = GetChildren(node.InvoiceId, node, node.Depth++);
    }

    return nodes;
}

The interesting thing, though, for me was attempting to replicate this sort of functionality entirely in T-SQL. Recursive functions in SQL are simply not my thing. However, it’s not too terribly difficult to achieve this functionality with a recursive CTE.

Here’s a SQL query that will do pretty much the same thing. It will carry through the root Id as a column and provide a “path” string indicating the relationship between the bracnhes and leafs in the tree. One significant difference with the code-based approach and the SQL CTE approach is that it’s possible to retrieve the tree for many invoices.

DECLARE @invoiceIds TABLE (InvoiceId INT, InvoiceNumber VARCHAR(16));

--INSERT INTO @invoiceIds the top 100 Sales Invoices with children
INSERT INTO @invoiceIds
SELECT TOP 100 [i].[InvoiceId], [i].[InvoiceNumber]
FROM [dbo].[Invoice] i WITH (NOLOCK)
OUTER APPLY (SELECT TOP 1 InvoiceId FROM [dbo].[Invoice] c1 WITH (NOLOCK) WHERE [c1].[ParentInvoiceId] = [i].[InvoiceId]) c1
WHERE [i].InvoiceType = 1 AND c1.InvoiceId IS NOT NULL

-- If only a single, known Invoice is desired..
--INSERT INTO @invoiceIds SELECT 11111, 'ABCDFEG'

--DECLARE @invoiceId int = 11363;

;WITH invoices AS (
    SELECT [i].InvoiceID, [i].InvoiceNumber, [i].TenderDateAtStore AS 'TenderDate', [tt].InvoiceTypeDescription AS 'InvoiceType', 0 AS Level
    , CAST([i].[InvoiceID] AS VARCHAR(255)) AS Path, CAST([i].[InvoiceID] AS VARCHAR(255)) AS Root
    FROM [dbo].[Invoice] i WITH (NOLOCK)
	INNER JOIN [dbo].[lkInvoiceType] tt  WITH (NOLOCK) ON tt.InvoiceTypeID = i.InvoiceType
	INNER JOIN @invoiceIds [ids] ON [i].[InvoiceId] = [ids].[InvoiceId]
    --WHERE ParentInvoiceId IS NULL AND InvoiceId = @invoiceId
	WHERE ParentInvoiceId IS NULL

    UNION ALL

    SELECT [i].InvoiceID, [i].InvoiceNumber, [i].TenderDateAtStore AS 'TenderDate', [tt].InvoiceTypeDescription AS 'InvoiceType', Level + 1
    , CAST(Path + '.' + CAST(i.InvoiceID AS VARCHAR(255)) AS VARCHAR(255)), Root
    FROM [dbo].[Invoice] i WITH (NOLOCK)
	INNER JOIN [dbo].[lkInvoiceType] tt WITH (NOLOCK) ON tt.InvoiceTypeID = i.InvoiceType 
    INNER JOIN invoices inv ON inv.InvoiceId = i.ParentInvoiceId
)

SELECT * FROM invoices

Also note that I am joining to a link table that contains Invoice types and displaying that as appropriate.

Leave a Reply