Simulating CTE recursion in C#

Question

Say that have the following CTE that returns the level of some tree data (adjacency model) that I have (taken from Hierarchical data in Linq - options and performance):

WITH hierarchy_cte(id, parent_id, data, lvl) AS
(
    SELECT id, parent_id, data, 0 AS lvl
    FROM dbo.hierarchical_table
    WHERE (parent_id IS NULL)

    UNION ALL

    SELECT t1.id, t1.parent_id, t1.data, h.lvl + 1 AS lvl
    FROM dbo.hierarchical_table AS t1 
    INNER JOIN hierarchy_cte AS h ON t1.parent_id = h.id
)
SELECT id, parent_id, data, lvl
FROM hierarchy_cte AS result

I was wondering if there would be any performance increase by doing the recursion in C# instead of SQL. Can anyone show me how to perform the same work that the CTE does with a recursive C# function assuming I have a IQueryable where Tree is an entity representing an entry in the hierarchical table? Something along the lines of:

public void RecurseTree(IQueryable<Tree> tree, Guid userId, Guid parentId, int level)
{
    ...
    currentNode.level = x
    ...
    Recurse(tree... ,level + 1)
}

Would be cool to see this is easy to do using a lambda expression.

Answer 1

Recursion in SQL Server is horrendously slow by comparsion but it does work.

I'd have to say that T-SQL is somewhat limited but it was never meant to do all those operations in the first place. I don't believe there is any way you can make this happen with an IQueryable if you inted to run this against you SQL Server instance but you can do it in memory on the machine running the code using LINQ-to-Objects in a relatively compact manner.

Here's one way to do that:

class TreeNode
{
    public int Id;
    public int? ParentId;
}

static void Main(string[] args)
{
    var list = new List<TreeNode>{
        new TreeNode{ Id = 1 },
            new TreeNode{ Id = 4, ParentId = 1 },
            new TreeNode{ Id = 5, ParentId = 1 },
            new TreeNode{ Id = 6, ParentId = 1 },
        new TreeNode{ Id = 2 },
            new TreeNode{ Id = 7, ParentId= 2 },
                new TreeNode{ Id = 8, ParentId= 7 },
        new TreeNode{ Id = 3 },
    };

    foreach (var item in Level(list, null, 0))
    {
        Console.WriteLine("Id={0}, Level={1}", item.Key, item.Value);
    }
}

private static IEnumerable<KeyValuePair<int,int>> Level(List<TreeNode> list, int? parentId, int lvl)
{
    return list
        .Where(x => x.ParentId == parentId)
        .SelectMany(x => 
            new[] { new KeyValuePair<int, int>(x.Id, lvl) }.Concat(Level(list, x.Id, lvl + 1))
        );
}

Answer 2

Genuinely recursive lambdas (and by inference, Expressions) are technically possible but pretty much insane. I would also expect any parser (L2S, EF, etc) except maybe LINQ-to-Objects to just go crazy trying to unpick that.

In short: you would do well to consider this an unsupported mechanism for Expression.

Finally, note that just because you are writing an Expression doesn't mean you are executing it in C# - in fact, quite probably the opposite: if you are actively writing an Expression (rather than a delegate or procedural code) I assume that it is going to a parser (unless you used .AsQueryable() to push it to LINQ-to-Objects).