Efficiently selecting a tree in Linq-To-Sql

Question

Hello!

I have a linq-to-sql data layer, with 2 tables in it. "Parent" and "Child". There's a relationship between Child and Parent (so parent has many children, etc etc), a parent can also have many parents (when children grow up and themselves become parents).

I want to display this hierarchy out to the user, but I'm not sure how to do this efficiently.

The inefficient approach is to do:

foreach(Parent in db.Parents)
{
    output(Parent.Parents)
    output(Parent.Children)
}

But, this generates a db round trip twice for every iteration in the loop (eek!!), if it's a big family, this is going to be REALLY expensive.

Is there a better way? (god I hope so!)

Answer 1

I would suggest eager loading the whole collection you wish to pass to the UI. If the method for generating the parent -> parent collection is recursive (which it seems it might be) then use L2S code to select the items in a recursive manner. This way iterating the final collection of results in the UI is not going to trigger the SQL commands in an inefficient way.

Example:
I dont know if this is the best/shortest/cleanest way to do this, but hopefully you will get the idea. static functions coz its a console app.

class Program
{
    static void Main(string[] args)
    {
        foreach (ParentDTO p in GetParents().ToList())
        {
            if (p.Parent == null)
                Console.WriteLine(String.Format("{0} ({1})",
                    p.Name, p.ID.ToString()));
            else
                Console.WriteLine(String.Format("{0} ({1}){2}",
                    p.Name, p.ID.ToString(), "\r\n\t-" + p.Parent.Name));
        }

        Console.ReadKey();
    }

    private static IQueryable<ParentDTO> GetParents()
    {
        var db = new DataClasses1DataContext();
        db.Log = new DebuggerWriter();

        return from p in db.Parents
               let parentParent = GetParentOfParent(p.ParentID)
               select new ParentDTO
               {
                   ID = p.ID,
                   Name = p.Name,
                   Parent = parentParent
               };
    }

    private static ParentDTO GetParentOfParent(int? childParentID)
    {
        if (childParentID.HasValue)
            return GetParents().Single(p => p.ID == childParentID);
        else
            return null;
    }
}

Table data:

ID ParentID Name
1 NULL Bill
2 8 Mary
3 1 Gary
4 1 Milla
5 NULL Sue
6 NULL Fred
7 NULL Marg
8 7 Hillary

Output:

Bill (1)
Mary (2)
-Hillary
Gary (3)
-Bill
Milla (4)
-Bill
Sue (5)
Fred (6)
Marg (7)
Hillary (8)
-Marg

(the indented/hyphenated names are the respective parents)

This is the debugger output from the L2S dc Log:

SELECT [t0].[ID], [t0].[ParentID], [t0].[Name]
FROM [dbo].[Parent] AS [t0]
WHERE ([t0].[ID]) = @p0
-- @p0: Input Int (Size = 0; Prec = 0; Scale = 0) [8]
-- Context: SqlProvider(Sql2005) Model: AttributedMetaModel Build: 3.5.30729.1

SELECT [t0].[ID], [t0].[ParentID], [t0].[Name]
FROM [dbo].[Parent] AS [t0]
WHERE ([t0].[ID]) = @p0
-- @p0: Input Int (Size = 0; Prec = 0; Scale = 0) [7]
-- Context: SqlProvider(Sql2005) Model: AttributedMetaModel Build: 3.5.30729.1

SELECT [t0].[ID], [t0].[ParentID], [t0].[Name]
FROM [dbo].[Parent] AS [t0]
WHERE ([t0].[ID]) = @p0
-- @p0: Input Int (Size = 0; Prec = 0; Scale = 0) [1]
-- Context: SqlProvider(Sql2005) Model: AttributedMetaModel Build: 3.5.30729.1

SELECT [t0].[ID], [t0].[ParentID], [t0].[Name]
FROM [dbo].[Parent] AS [t0]
WHERE ([t0].[ID]) = @p0
-- @p0: Input Int (Size = 0; Prec = 0; Scale = 0) [1]
-- Context: SqlProvider(Sql2005) Model: AttributedMetaModel Build: 3.5.30729.1

SELECT [t0].[ID], [t0].[ParentID], [t0].[Name]
FROM [dbo].[Parent] AS [t0]
WHERE ([t0].[ID]) = @p0
-- @p0: Input Int (Size = 0; Prec = 0; Scale = 0) [7]
-- Context: SqlProvider(Sql2005) Model: AttributedMetaModel Build: 3.5.30729.1

..all of which fired in one go at the .ToList(); line (as expected).

I hope this is useful.