C# & Entity Framework - optimizing DB query for self-referencing entity with indefinite family tree

Viewed 91

I want to improve an existing query I made. Technically it works right now, but it doesn't seem very efficient when I look at it, but I can't come up with anything better at the moment that works.

To start with, I have the following setup:

public class Folder
{
    public int FolderID { get; set; }
    public string Name { get; set; }
    public int? ParentFolderID { get; set; }
    public Folder? ParentFolder { get; set; }

    //Folders belonging to folder
    public ICollection<Folder>? ChildFolders { get; set; }

    //Users belonging to folder
    public ICollection<User>? Users { get; set; }

    //Groups belonging to folder
    public ICollection<Group>? Groups { get; set; }

    // Determines which users and groups can see this folder
    public ICollection<UserFolder>? UserFolders { get; set; } //Composite Entity between users and folders
    public ICollection<GroupFolder>? GroupFolders { get; set; } //Composite Entity between groups and folders
}

As shown: a folder can have a parent folder and a list of children folders.

I use the following DTO for the entity:

public class FolderAdminSidebarRightDTO : IFolderGetCollectionDTO
{
    public int FolderId { get; set; }
    public string Name { get; set; }
    public int? ParentFolderId { get; set; }

    // Id and username of users
    public List<Tuple<int, string>> Users { get; set; }

    // List of itself
    public List<FolderAdminSidebarRightDTO> SubFolders { get; set; }
}

The idea is to show a navigation bar to the right with a list of folders they have access to, which can individually be expanded on with a click to show a list of users and subfolders inside that folder. This can repeat indefinitely.

Example:

-folder 1
  -user 1
  -user 2
  -folder 2
    -user 3
    -user 4
    -folder 3
      -unknown steps down...
-folder 4
  -user 5
  -user 6
  -folder 5

I've made the following code to satisfy these needs:

/// <inheritdoc/>
public IEnumerable<IFolderGetCollectionDTO> GetFolders(NetworkManagementContext context, int userId, IFolderDTOOptions options)
{
    //query to get all folders the current user has access to
    List<FolderAdminSidebarRightDTO> query = context.UserFolders
        .AsNoTracking()
        .Where(uf => uf.UserID == userId)
        .Select(uf => new FolderAdminSidebarRightDTO
        {
            FolderId = uf.Folder.FolderID,
            Name = uf.Folder.Name,
            ParentFolderId = uf.Folder.ParentFolderID,
            Users = uf.Folder.Users.Select(u => new Tuple<int, string>(u.UserID, u.Name)).ToList()
        }).ToList();

    //List of all subfolder Ids 
    List<int> subfolderIds = new List<int>();

    //iterates through all folders found in inital query to get subfolders
    foreach (FolderAdminSidebarRightDTO item in query)
    {
        GetSubFolders(item, subfolderIds, context);
    }

    //removes all duplicates of folder ids
    subfolderIds = subfolderIds.Distinct().ToList();

    //removes folders from initial query that the user has access to, but already exists 
    //somewhere within another folder from initial query or it's subfolders to avoid duplicate UI elements
    query.RemoveAll(f => subfolderIds.Contains(f.FolderId));

    return query;
}

/// <summary>
/// Projects a list of folders from DB related to id of <see cref="FolderAdminSidebarRightDTO"/> object argument and binds the list of projected folders to the object
/// </summary>
/// <param name="folder">DTO of folder entity</param>
/// <param name="folderIds">List of folder ids used for filtering out duplicate folders found in DB</param>
/// <param name="context">Context for entity framework</param>
private void GetSubFolders(FolderAdminSidebarRightDTO folder, List<int> folderIds, NetworkManagementContext context)
{
    //query to get all subfolders inside folder argument
    folder.SubFolders = context.Folders
        .AsNoTracking()
        .Where(f => f.ParentFolderID == folder.FolderId)
        .Select(f => new FolderAdminSidebarRightDTO
        {
            FolderId = f.FolderID,
            Name = f.Name,
            ParentFolderId = f.ParentFolderID,
            Users = f.Users.Select(u => new Tuple<int, string>(u.UserID, u.Name)).ToList()
        }).ToList();

    //adds id of all found subfolders in current query to list of subfolder ids
    folder.SubFolders.ForEach(f => folderIds.Add(f.FolderId)); 

    //iterates through all subfolders found in current query to get subfolders for the next level
    foreach (FolderAdminSidebarRightDTO item in folder.SubFolders)
    {
        //calls itself
        GetSubFolders(item, folderIds, context);
    }
}

My main concern is the amount of times I call the context through this process, but I personally can't figure out how to dynamically get an unknown amount of levels of folders without first retrieving the level above since I need to know the ids of the folders to get their children.

If there's something else that could be made more efficiently within my code, i'd be more than happy to hear it.

Thanks in advance

1 Answers

AFAIK, there is no support for doing such a recursive call through LINQ.

Therefore, you are left with the following options:

  1. Write the query using Pure SQL, which would enable you to write a Common Table Expression that calls itself recursively. Then, the recursion logic to build up the result will be done in the database server at once, instead of having multiple roundtrips from the client application as you have now.
  2. If you don't wanna have the raw SQL in your code for some reason, you could always create a database view from the same query you would build in option 1, and then query the view directly from your application.
  3. Finally, there is an alternative without using Recursive CTEs at all: you could maintain your tree structure in the database in what's called a Nested Set Model. When doing that, you have to add two new properties to each node called something like Left and Right (or TreeMin and TreeMax), which represent the "position" when first/last visiting each node during a tree transversal. The idea of labeling each node with a Left and Right is that then you would be able to easily query all the children of one node checking if child.Left > parent.Left && child.Right < parent.Right. Maintaining such data structure in the DB might be a little bit more complex than the previous solution, and it's only advisable if your tree doesn't change that often.
Related