Querying hierarchies at any depth: recursive SQL functions meet an in-memory TreeList

"Give me all products under category X — including every subcategory, at any depth."

Every developer who has modeled a self-referencing entity has met this requirement, and it's where the comfortable world of LINQ-to-Entities gets awkward. EF Core is excellent at joins it knows about at compile time; it has no built-in answer for walk this edge table until you run out of children. SQL does — recursive common table expressions have been standard since SQL Server 2005 — but combining raw recursive SQL with a typed, composable EF Core query pipeline takes a few deliberate steps.

This article walks through three escalating strategies for hierarchical data, ending with the one we use in the Regira Entities framework for large trees: recursive CTEs wrapped in table-valued functions, mapped into the DbContext, and composed inside ordinary IQueryable filters — then materialized into an in-memory tree structure for the client.

The running example is a webshop's Category, and deliberately not a simple one: a category can hang under several parents through a RelatedCategories join table. That makes it a graph rather than a strict tree, which is exactly why the pattern needs to be robust — "recursive" here means self-referencing, whatever the arity.

public class Category
{
    public int Id { get; set; }
    public string Title { get; set; } = null!;
    public bool IsArchived { get; set; }

    public ICollection<RelatedCategory>? ParentCategories { get; set; }
    public ICollection<RelatedCategory>? ChildCategories { get; set; }
}

public class RelatedCategory
{
    public int Id { get; set; }
    public int ParentId { get; set; }
    public int ChildId { get; set; }

    public Category? Parent { get; set; }
    public Category? Child { get; set; }
}

Layer 1 — Direct relations: as far as a plain query takes you

Before reaching for recursion, be honest about how much of the requirement a non-recursive query covers. Filtering on direct parents or children is ordinary LINQ, and in a typed filter pipeline it looks like this (the shape Regira Entities uses — a SearchObject record bound from the query string, applied by a query builder):

public record CategorySearchObject : SearchObject
{
    public ICollection<int>? ParentId { get; set; }  // direct children of these
    public ICollection<int>? ChildId { get; set; }   // direct parents of these
    public bool? IsRoot { get; set; }
}

// inside the filter query builder
if (so?.ParentId?.Any() == true)
    query = query.Where(x => x.ParentCategories!.Any(r => so.ParentId.Contains(r.ParentId)));
if (so?.IsRoot == true)
    query = query.Where(x => !x.ParentCategories!.Any());

GET /categories?parentId=5 now returns the direct children of category 5. For a navigation menu that unfolds level by level, this is all you need — each unfold is one indexed query, and no recursion ever runs.

One modeling note while you're here: on a single-parent tree (a plain ParentId column), think about delete behavior early. A required self-referencing FK with Restrict gets fixed up client-side by EF when the children happen to be loaded, which produces confusing failures; ClientNoAction lets the database be the referee and surfaces a clean constraint violation instead. A nullable ParentId is the other defensible choice: deleting a node promotes its children to roots.

Where layer 1 stops: "everything under X, any depth." You could loop — query children, then their children — but that's one round-trip per level, and it composes with nothing.

Layer 2 — Load flat, build the tree in memory

If the whole table is modest (navigation trees, org charts, folder structures — thousands of rows, not millions), the pragmatic answer is: fetch the flat list once and assemble the hierarchy in memory. The assembly is the part worth not hand-rolling; it's the job of Regira.TreeList:

var categories = await dbContext.Categories
    .Include(x => x.ParentCategories)
    .ToListAsync();

var roots = categories.Where(c => !(c.ParentCategories?.Any() ?? false));
var tree = categories.ToTreeList(roots,
    node => categories.Where(c =>
        c.ParentCategories?.Any(r => r.ParentId == node.Value.Id) == true));

// any-depth questions are now in-memory navigation:
var electronics = tree.First(n => n.Value.Id == 5);
var subtreeIds  = electronics.GetOffspring().Select(n => n.Value.Id).ToHashSet();

var products = await dbContext.Products
    .Where(p => subtreeIds.Contains(p.CategoryId))
    .ToListAsync();

TreeList<T> wraps each item in a TreeNode<T> with Parent, Children and Level, gives you GetOffspring() / GetAncestors() / GetRoots() in every direction, guards against cycles with a typed exception, and — because it inherits List<TreeNode<T>> — stays fully LINQ-composable. (A short intro is in From flat list to tree in one line of C#.)

Note the shape of the product query: resolve the subtree to a set of ids in memory, then let the database do what it's good at. Two queries, both simple. For most applications, layers 1 and 2 are genuinely enough — and they work on every database provider, including the SQLite you prototype on.

Where layer 2 stops: when the table no longer fits comfortably in memory, or when the subtree condition must compose inside a larger server-side query (paging, sorting, counting) rather than as a pre-resolved id set.

Layer 3 — Teach the database to walk the tree

The endgame is to make "the whole subtree of X" a first-class queryable — something you can Any() against inside a Where, that EF Core translates to a single SQL statement. That takes three pieces:

1. a recursive CTE doing the actual walking, packaged as a table-valued function (TVF);
2. a keyless entity type describing the rows it returns;
3. a mapped DbContext method so LINQ can compose it.

The keyless projection

The functions return edges, not entities: each row says "starting from seed RootId, at depth Level, there is an edge ParentId → ChildId". Model that as a keyless type — no table, never tracked:

public class CategoryTreeItem
{
    public int ParentId { get; set; }
    public int ChildId { get; set; }
    public int Level { get; set; }     // 0-based depth from the seed
    public int RootId { get; set; }    // which seed id reached this row
    public Category? Parent { get; set; }
    public Category? Child { get; set; }
}

The two optional navigations are a nice trick: because they point at a real entity, you can Include actual Category rows through the projection when you want titles along with the edges.

The SQL — a recursive CTE in a TVF

The function itself is classic recursive-CTE material, with two production details baked in: a JSON-array parameter for the seed ids (parsed by OPENJSON — SQL Server 2016+ with database compatibility level 130 or higher — so one function handles one seed or many), and a level cap as the cycle guard — remember, multi-parent means cycles are possible in principle:

CREATE OR ALTER FUNCTION [dbo].[GetCategoryOffspring]
    (@ids NVARCHAR(MAX) = NULL, @max_level INT = 9)
RETURNS TABLE AS RETURN
    WITH offspring (ParentId, ChildId, Level, RootId) AS (
        -- anchor: edges starting at the seed ids
        SELECT     r.ParentId, r.ChildId, 0, r.ParentId
        FROM       RelatedCategories r
        WHERE      (@ids IS NULL OR @ids = ''
                    OR r.ParentId IN (SELECT CAST(value AS INT) FROM OPENJSON(@ids)))
               AND NOT EXISTS (SELECT 1 FROM Categories s
                               WHERE (s.Id = r.ChildId OR s.Id = r.ParentId) AND s.IsArchived = 1)
        UNION ALL
        -- recursive step: follow edges downward
        SELECT     sc.ParentId, sc.ChildId, offspring.Level + 1, offspring.RootId
        FROM       RelatedCategories sc
        INNER JOIN offspring ON offspring.ChildId = sc.ParentId
        WHERE      (@max_level IS NULL OR offspring.Level < @max_level)
               AND NOT EXISTS (SELECT 1 FROM Categories s
                               WHERE (s.Id = sc.ChildId OR s.Id = sc.ParentId) AND s.IsArchived = 1)
    )
    SELECT * FROM offspring;

GetCategoryAncestors is the mirror image — seed on ChildId, join the other way. A third function, GetCategoryFamily, unions both with signed levels (negative = ancestor side), which is handy for "show me where this node sits" views. Each of the three gets the same treatment in the next section: its own stub, convenience overload and HasDbFunction registration — shown once for GetCategoryOffspring, copied verbatim for the other two.

Notice the IsArchived checks inside the SQL. If your application soft-deletes rows with a global query filter (Regira Entities does this for any IArchivable entity), be aware that global filters do not reach inside a TVF — the function bypasses EF's query pipeline by definition. Whatever row-level rules you rely on (archived, tenant) must be re-applied in the function itself; a tenant-scoped tree needs TenantId as a function parameter.

Keep the DDL as string constants next to the DbContext — CREATE OR ALTER makes it idempotent, so you can run it from a migration (migrationBuilder.Sql(...)) or, on an EnsureCreated()-style setup, right after schema creation, gated on the provider:

await db.Database.EnsureCreatedAsync();
if (db.Database.ProviderName == "Microsoft.EntityFrameworkCore.SqlServer")
    foreach (var sql in CategoryDbFunctions.CREATE_ALL)
        await db.Database.ExecuteSqlRawAsync(sql);

The functions must exist before the first query composes them; EnsureCreated() alone will not create them, and the failure mode is a runtime SQL error, not a startup one.

Mapping the function into EF Core

ModelBuilder.HasDbFunction is the bridge. The stub method's body calls FromExpression, which tells EF "never execute this in .NET — translate calls to it into SQL":

public partial class WebshopDbContext
{
    // DB-mapped stub: EF translates calls into SELECT * FROM dbo.GetCategoryOffspring(@ids, @max_level)
    protected IQueryable<CategoryTreeItem> GetCategoryOffspring(string? ids, int maxLevel)
        => FromExpression(() => GetCategoryOffspring(ids, maxLevel));

    // convenience overload: IEnumerable<int> -> JSON array string ("[1,2,3]")
    public IQueryable<CategoryTreeItem> GetCategoryOffspring(IEnumerable<int>? ids = null, int maxLevel = 9)
        => GetCategoryOffspring(ToJsonArray(ids), maxLevel);

    // declared `partial void ConfigureFunctions(ModelBuilder modelBuilder);` in the other half
    // of the partial class, and called from its OnModelCreating
    partial void ConfigureFunctions(ModelBuilder modelBuilder)
    {
        var flags = BindingFlags.Instance | BindingFlags.Public | BindingFlags.NonPublic;
        modelBuilder.Entity<CategoryTreeItem>(entity =>
        {
            entity.HasNoKey().ToTable((string?)null);   // query-only projection
            entity.HasOne(x => x.Parent).WithMany();
            entity.HasOne(x => x.Child).WithMany();
        });
        modelBuilder.HasDbFunction(typeof(WebshopDbContext)
            .GetMethod(nameof(GetCategoryOffspring), flags, [typeof(string), typeof(int)])!)
            .HasSchema("dbo");
    }

    private static string? ToJsonArray(IEnumerable<int>? ids)
    {
        var list = ids as IList<int> ?? ids?.ToList();
        return list == null || list.Count == 0 ? null : $"[{string.Join(",", list)}]";
    }
}

The two-overload split matters: the string-typed stub is what EF maps (SQL sees an NVARCHAR parameter), while the public IEnumerable<int> overload keeps call sites type-safe and does the JSON encoding in one place.

Composing the function inside your filters

This is the payoff. The TVF returns an IQueryable, so it slots into any predicate and the whole thing runs as one SQL statement — no round-trip to resolve ids first:

public record CategorySearchObject : SearchObject
{
    // layer 1 — direct relations
    public ICollection<int>? ParentId { get; set; }
    public ICollection<int>? ChildId { get; set; }
    public bool? IsRoot { get; set; }
    // layer 3 — recursive, any depth
    public ICollection<int>? AncestorId { get; set; }   // below these ids
    public ICollection<int>? OffspringId { get; set; }  // above these ids
    public ICollection<int>? RootId { get; set; }       // reachable from these seeds
}

public override IQueryable<Category> Build(IQueryable<Category> query, CategorySearchObject? so)
{
    // ... direct-relation filters ...
    if (so?.AncestorId?.Any() == true)
        query = query.Where(x => dbContext.GetCategoryOffspring(so.AncestorId, 9)
                                          .Any(o => o.ChildId == x.Id));
    if (so?.OffspringId?.Any() == true)
        query = query.Where(x => dbContext.GetCategoryAncestors(so.OffspringId, 9)
                                          .Any(o => o.ParentId == x.Id));
    if (so?.RootId?.Any() == true)
        query = query.Where(x => dbContext.GetCategoryOffspring(so.RootId, 9)
                                          .Any(o => o.RootId == x.Id));
    return query;
}

From the outside, nothing changed: GET /categories?ancestorId=5 is just another query-string filter, and it pages, sorts and counts like every other one, because the recursion happens inside the same statement.

The same composition powers indirect filters on other entities — the requirement this article opened with:

// "products in category X or any of its subcategories"
if (so?.CategoryId?.Any() == true)
{
    var subtree = dbContext.GetCategoryOffspring(so.CategoryId, 9).Select(o => o.ChildId);
    query = query.Where(p => so.CategoryId.Contains(p.CategoryId)
                          || subtree.Contains(p.CategoryId));
}

A practical rule for when to materialize: if the resolved ids feed a single predicate, leave the function composed inside the Where and let SQL Server run it as one statement. If they feed several later predicates, ToListAsync()/ToHashSet() once and reuse the set — recomputing the recursive walk per predicate is the one way to make this pattern slow.

Closing the loop: TVF → TreeList → API response

The database now answers subtree filters efficiently, but a client rendering a tree widget wants the structure back, not just matching rows. This is where layers 2 and 3 meet: the TVF produces the flat edge list — cheaply, at any depth — and TreeList reassembles it in memory:

public class CategoryRepository(WebshopDbContext dbContext,
    IEntityReadService<Category, int, CategorySearchObject> readService,
    IEntityWriteService<Category, int> writeService)
    : EntityRepository<Category, int, CategorySearchObject>(readService, writeService), ICategoryService
{
    public async Task<TreeList<CategoryTreeItem>> GetOffspring(IList<int> ids, int maxLevel = 9)
    {
        var items = await dbContext.GetCategoryOffspring(ids, maxLevel).ToListAsync();
        // an edge-row's parent is the row that ends where it starts:
        return items.ToTreeList(x => items.FindAll(p => p.ChildId == x.ParentId));
    }
}

// on the controller:
[HttpGet("offspring")]
public async Task<IActionResult> GetOffspring([FromQuery] IList<int> ids, [FromQuery] int level = 9)
    => Ok(new ListResult<CategoryTreeItem>
    {
        Items = (await service.GetOffspring(ids, level)).ToTreeView()
    });

ToTreeView() flattens the assembled tree depth-first — parents always precede their children — so the JSON the SPA receives can be rebuilt into a client-side tree in a single pass, with no sorting or lookahead. (How the front end does that, with the @regira/modules TreeList and a drag-and-drop composable, is the follow-up article.)

Choosing your layer — and the honest caveats

Match the layer to the data size and the provider. Layer 1 (direct filters) works everywhere and covers unfold-as-you-go UIs. Layer 2 (TreeList over a flat fetch) works everywhere too, and for tables that fit in memory it is simpler and usually faster end-to-end than being clever in SQL. Layer 3 earns its complexity only for trees too large to load, or when subtree conditions must compose inside larger server-side queries.

Layer 3 is provider-specific. The SQL above is SQL Server (OPENJSON, CREATE OR ALTER FUNCTION). PostgreSQL and MySQL both have recursive CTEs (WITH RECURSIVE) and JSON table functions, but the dialect differs and the functions need porting; SQLite has no stored functions at all. The C# mapping side is provider-neutral — gate the function creation and the recursive filter availability on Database.ProviderName.

The level cap is your cycle insurance. A multi-parent join table can, in principle, encode a cycle; @max_level guarantees the CTE terminates anyway. Defense in depth: keep a unique index on (ParentId, ChildId), and validate "a node may not become its own ancestor" at write time — an in-memory TreeList makes that check trivial (tree.IsValidChild(parentNode, candidate)) before the bad edge ever reaches the database.

Re-apply row-level rules inside the function. Worth repeating, because it's the one genuine trap: archived-row filters, tenant filters, and any other global query filter stop at the TVF boundary. The SQL must enforce them itself.

The pattern above ships as a documented blueprint (with the ancestors/family functions, registration wiring and gotchas) in the Regira Entities docs — and the whole SearchObject/query-builder pipeline it plugs into is an article of its own.

A note on what you're using here: SearchObject, the query-builder base, IEntityReadService/IEntityWriteService, EntityRepository and ListResult come from the Regira.Entities packages (Regira.Entities for the abstractions, Regira.Entities.EFcore + Regira.Entities.DependencyInjection + Regira.Entities.Web for the pipeline, repositories and controllers — commercially licensed with a free tier); Regira.TreeList is Apache-2.0. Layer 1 and layer 2 need nothing but EF Core and Regira.TreeList — the framework types only enter at layer 3's filter composition, and the mapping section above is plain EF Core either way.

Package docs: Regira.Entities · Regira.TreeList