Hierarchical data in Linq - options and performanc

Question

I have some hierarchical data - each entry has an id and a (nullable) parent entry id. I want to retrieve all entries in the tree under a given entry. This is in a SQL Server 2005 database. I am querying it with LINQ to SQL in C# 3.5.

LINQ to SQL does not support Common Table Expressions directly. My choices are to assemble the data in code with several LINQ queries, or to make a view on the database that surfaces a CTE.

Which option (or another option) do you think will perform better when data volumes get large? Is SQL Server 2008's HierarchyId type supported in Linq to SQL?

Answer 1

The trouble with fetching the data from the client side is that you can never be sure how deep you need to go. This method will do one roundtrip per depth and it could be union'd to do from 0 to a specified depth in one roundtrip.

public IQueryable<Node> GetChildrenAtDepth(int NodeID, int depth)
{
  IQueryable<Node> query = db.Nodes.Where(n => n.NodeID == NodeID);
  for(int i = 0; i < depth; i++)
    query = query.SelectMany(n => n.Children);
       //use this if the Children association has not been defined
    //query = query.SelectMany(n => db.Nodes.Where(c => c.ParentID == n.NodeID));
  return query;
}

It can't, however, do arbitrary depth. If you really do require arbitrary depth, you need to do that in the database - so you can make the correct decision to stop.

Answer 2

I got this approach from Rob Conery's blog (check around Pt. 6 for this code, also on codeplex) and I love using it. This could be refashioned to support multiple "sub" levels.

var categories = from c in db.Categories
                 select new Category
                 {
                     CategoryID = c.CategoryID,
                     ParentCategoryID = c.ParentCategoryID,
                     SubCategories = new List<Category>(
                                      from sc in db.Categories
                                      where sc.ParentCategoryID == c.CategoryID
                                      select new Category {
                                        CategoryID = sc.CategoryID, 
                                        ParentProductID = sc.ParentProductID
                                        }
                                      )
                             };

Answer 3

This extension method could potentially be modified to use IQueryable. I've used it succesfully in the past on a collection of objects. It may work for your scenario.

public static IEnumerable<T> ByHierarchy<T>(
 this IEnumerable<T> source, Func<T, bool> startWith, Func<T, T, bool> connectBy)
{
  if (source == null)
   throw new ArgumentNullException("source");

  if (startWith == null)
   throw new ArgumentNullException("startWith");

  if (connectBy == null)
   throw new ArgumentNullException("connectBy");

  foreach (T root in source.Where(startWith))
  {
   yield return root;
   foreach (T child in source.ByHierarchy(c => connectBy(root, c), connectBy))
   {
    yield return child;
   }
 }
}

Here is how I called it:

comments.ByHierarchy(comment => comment.ParentNum == parentNum, 
 (parent, child) => child.ParentNum == parent.CommentNum && includeChildren)

This code is an improved, bug-fixed version of the code found here.