asp.net mvc - Is recursive query possible in LINQ to Entities

Question

this is my first question and sorry about my weak language.

I've got a table like this model;

 public class Menu
 {
      [Key]
      public int ID {get;set;}
      public int ParentID {get;set;}
      public string MenuName {get;set;}
      public int OrderNo {get;set;}
      public bool isDisplayInMenu {get;set;} // Menu or just for Access Authority
 }

and there are many rows about menu like this;

ID     ParentID      MenuName          Order
---    ---------     -------------     ------
1      0             Main.1               1     >> if ParentID==0 is Root
2      1             Sub.1.1              1
3      2             Sub.1.2              2
4      0             Main.2               2
5      4             Sub.2.1              1
6      4             Sub.2.2              2

I have got a second class to prepare menu tree;

public class MyMenu:Menu
{
    public List<MyMenu> Childs { get;set;}
}

I need a linq query to get the result like this;

var result = (...linq..).ToList<MyMenu>();

I am using a recursive function to get childs but this take too much time for to get results.

How can I write a sentence to get all menu tree in one query?

UPDATE:

I want to store main menu in a table. And this table will use on access authority control for users. Some rows will display inside the menu, some ones will use only to get access authority.

In this situation, I need many times to get the table tree. The table tree will be created as the filtered user authorities. When get the tree, stored in session. but many sessions means much RAM. If is there any fast way to get menu tree from the sql when I need then I will not store in the session.

Answer 1

If you need to walk the entire tree, you should use a stored procedure. Entity Framework is particularly ill-suited for recursive relationships. You'll either need to issue N+1 queries for each level, or eagerly load a defined set of levels. For example, .Include("Childs.Childs.Childs"), would load three levels. However, this is going to create a monstrous query, and you'll still need to issue N+1 queries for any additional level you don't include at the start.

In SQL, you can use WITH to recursively walk the table, and it will be much quicker than anything Entity Framework can do. However, your result will be flattened, rather than the object graph you would get back from Entity Framework. For example:

DECLARE @Pad INT = (
    SELECT MAX([Length])
    FROM (
        SELECT LEN([Order]) AS [Length] FROM [dbo].[Menus]
    ) x
);

WITH Tree ([Id], [ParentId], [Name], [Hierarchy]) AS
(
    SELECT
        [ID],
        [ParentID],
        [MenuName],
        REPLICATE('0', @Pad - LEN([Order])) + CAST([Order] AS NVARCHAR(MAX))
    FROM [dbo].[Menus]
    WHERE [ParentID] = 0 -- root
    UNION ALL
        SELECT
            Children.[ID],
            Children.[ParentID],
            Children.[MenuName],
            Parent.[Hierarchy] + '.' + REPLICATE('0', @Pad - LEN(Children.[Order])) + CAST(Children.[Order] AS NVARCHAR(MAX)) AS [Hierarchy]
        FROM [dbo].[Menus] Children
        INNER JOIN Tree AS Parent
            ON Parent.[ID] = Children.[ParentID]
)
SELECT
    [ID],
    [ParentID],
    [MenuName]
FROM Tree
ORDER BY [Hierarchy]

That looks much more complicated than it is. In order to ensure that the items in the menu are ordered properly by parent and their position within that parent's tree, we need to create a hierarchical representation of the order to order by. I'm doing that here by creating a string in the form of 1.1.1, where essentially each item's order is appended to the end of the parent's hierarchy string. I'm also using REPLICATE to left-pad the order for each level, so you don't have issues common with string ordering of numbers, where something like 10 comes before 2, because it starts with 1. The @Pad declaration just gets the max length I need to pad based on the highest order number in the table. For example, if the max order was something like 123, then the value of @Pad would be 3, so that orders less than 123 would still be three characters (i.e. 001).

Once you get past all that, the rest of the SQL is pretty straight-forward. You simply select all the root items and then union all with all their child by walking the tree. This and joining in each new level. Finally, you select from this tree the information you need, ordered by the hierarchy ordering string we created.

At least for my trees, this query is acceptably quick, but could be somewhat slower than you might like if the complexity scales or there's a ton of menu items to deal with. It's not a bad idea to do some sort of caching of the tree, even with using this query. Personally, for something like a site nav, I'd recommend using a child action combined with OutputCache. You call the child action in your layout where the nav should appear, and it will either run the action to get the menu or retrieve the already created HTML from cache if it exists. If the menu is specific to individual users, then just make sure you vary by custom, and factor in the user's id or something in your custom string. You could also just memory cache the result of the query itself, but you might as well reduce the cost of generating the HTML, too, while your at it. However, storing it in the session should be avoided.