Add folder-aware filter extensions and descendant query provider

- Add FolderAwareFilterExtensions for LinkedChildren-based filtering
- Add IDescendantQueryProvider interface for database-specific queries
- Add MatchCriteria classes for folder filtering
- Add SqliteDescendantQueryProvider implementation

7 files changed, 256 insertions, 0 deletions

diff --git a/Jellyfin.Server.Implementations/Item/FolderAwareFilterExtensions.cs b/Jellyfin.Server.Implementations/Item/FolderAwareFilterExtensions.cs
new file mode 100644
index 0000000000..c63d99d54d
--- /dev/null
+++ b/Jellyfin.Server.Implementations/Item/FolderAwareFilterExtensions.cs
@@ -0,0 +1,65 @@
+using System;
+using System.Linq;
+using System.Linq.Expressions;
+using Jellyfin.Database.Implementations;
+using Jellyfin.Database.Implementations.Entities;
+
+namespace Jellyfin.Server.Implementations.Item;
+
+/// <summary>
+/// Extension methods for applying folder-aware filters that check items and their descendants.
+/// </summary>
+internal static class FolderAwareFilterExtensions
+{
+    /// <summary>
+    /// Filters items where either the item matches the condition (for non-folders)
+    /// or any descendant matches (for folders). Uses reverse traversal through AncestorIds.
+    /// </summary>
+    /// <param name="query">The query to filter.</param>
+    /// <param name="context">The database context.</param>
+    /// <param name="condition">The condition to check on BaseItemEntity.</param>
+    /// <returns>Filtered query.</returns>
+    public static IQueryable<BaseItemEntity> WhereItemOrDescendantMatches(
+        this IQueryable<BaseItemEntity> query,
+        JellyfinDbContext context,
+        Expression<Func<BaseItemEntity, bool>> condition)
+    {
+        var matchingIds = context.BaseItems.Where(condition).Select(b => b.Id);
+        var foldersWithMatchingDescendants = context.AncestorIds
+            .Where(a => matchingIds.Contains(a.ItemId))
+            .Select(a => a.ParentItemId)
+            .Union(context.LinkedChildren
+                .Where(lc => matchingIds.Contains(lc.ChildId))
+                .Select(lc => lc.ParentId));
+
+        return query.Where(e =>
+            matchingIds.Contains(e.Id)
+            || foldersWithMatchingDescendants.Contains(e.Id));
+    }
+
+    /// <summary>
+    /// Filters items where neither the item matches the condition (for non-folders)
+    /// nor any descendant matches (for folders). Uses reverse traversal for infinite depth.
+    /// </summary>
+    /// <param name="query">The query to filter.</param>
+    /// <param name="context">The database context.</param>
+    /// <param name="condition">The condition that should NOT match.</param>
+    /// <returns>Filtered query.</returns>
+    public static IQueryable<BaseItemEntity> WhereNeitherItemNorDescendantMatches(
+        this IQueryable<BaseItemEntity> query,
+        JellyfinDbContext context,
+        Expression<Func<BaseItemEntity, bool>> condition)
+    {
+        var matchingIds = context.BaseItems.Where(condition).Select(b => b.Id);
+        var foldersWithMatchingDescendants = context.AncestorIds
+            .Where(a => matchingIds.Contains(a.ItemId))
+            .Select(a => a.ParentItemId)
+            .Union(context.LinkedChildren
+                .Where(lc => matchingIds.Contains(lc.ChildId))
+                .Select(lc => lc.ParentId));
+
+        return query.Where(e =>
+            !matchingIds.Contains(e.Id)
+            && !foldersWithMatchingDescendants.Contains(e.Id));
+    }
+}
diff --git a/src/Jellyfin.Database/Jellyfin.Database.Implementations/IDescendantQueryProvider.cs b/src/Jellyfin.Database/Jellyfin.Database.Implementations/IDescendantQueryProvider.cs
new file mode 100644
index 0000000000..9e3d510b9c
--- /dev/null
+++ b/src/Jellyfin.Database/Jellyfin.Database.Implementations/IDescendantQueryProvider.cs
@@ -0,0 +1,30 @@
+using System;
+using System.Linq;
+using Jellyfin.Database.Implementations.MatchCriteria;
+
+namespace Jellyfin.Database.Implementations;
+
+/// <summary>
+/// Provider interface for descendant queries using recursive CTEs.
+/// Each database provider implements this with provider-specific SQL.
+/// </summary>
+public interface IDescendantQueryProvider
+{
+    /// <summary>
+    /// Gets a queryable of all descendant IDs for a parent item.
+    /// Uses recursive CTE to traverse AncestorIds and LinkedChildren infinitely.
+    /// </summary>
+    /// <param name="context">Database context.</param>
+    /// <param name="parentId">Parent item ID.</param>
+    /// <returns>Queryable of descendant item IDs.</returns>
+    IQueryable<Guid> GetAllDescendantIds(JellyfinDbContext context, Guid parentId);
+
+    /// <summary>
+    /// Gets a queryable of all folder IDs that have any descendant matching the specified criteria.
+    /// Uses recursive CTE for infinite depth traversal. Can be used in LINQ .Contains() expressions.
+    /// </summary>
+    /// <param name="context">Database context.</param>
+    /// <param name="criteria">The matching criteria to apply.</param>
+    /// <returns>Queryable of folder IDs.</returns>
+    IQueryable<Guid> GetFolderIdsMatching(JellyfinDbContext context, FolderMatchCriteria criteria);
+}
diff --git a/src/Jellyfin.Database/Jellyfin.Database.Implementations/MatchCriteria/FolderMatchCriteria.cs b/src/Jellyfin.Database/Jellyfin.Database.Implementations/MatchCriteria/FolderMatchCriteria.cs
new file mode 100644
index 0000000000..d9f2d91806
--- /dev/null
+++ b/src/Jellyfin.Database/Jellyfin.Database.Implementations/MatchCriteria/FolderMatchCriteria.cs
@@ -0,0 +1,6 @@
+namespace Jellyfin.Database.Implementations.MatchCriteria;
+
+/// <summary>
+/// Base type for folder matching criteria using discriminated union pattern.
+/// </summary>
+public abstract record FolderMatchCriteria;
diff --git a/src/Jellyfin.Database/Jellyfin.Database.Implementations/MatchCriteria/HasChapterImages.cs b/src/Jellyfin.Database/Jellyfin.Database.Implementations/MatchCriteria/HasChapterImages.cs
new file mode 100644
index 0000000000..3dd84bbd27
--- /dev/null
+++ b/src/Jellyfin.Database/Jellyfin.Database.Implementations/MatchCriteria/HasChapterImages.cs
@@ -0,0 +1,6 @@
+namespace Jellyfin.Database.Implementations.MatchCriteria;
+
+/// <summary>
+/// Matches folders containing descendants with chapter images.
+/// </summary>
+public sealed record HasChapterImages : FolderMatchCriteria;
diff --git a/src/Jellyfin.Database/Jellyfin.Database.Implementations/MatchCriteria/HasMediaStreamType.cs b/src/Jellyfin.Database/Jellyfin.Database.Implementations/MatchCriteria/HasMediaStreamType.cs
new file mode 100644
index 0000000000..68f2ca2786
--- /dev/null
+++ b/src/Jellyfin.Database/Jellyfin.Database.Implementations/MatchCriteria/HasMediaStreamType.cs
@@ -0,0 +1,14 @@
+using Jellyfin.Database.Implementations.Entities;
+
+namespace Jellyfin.Database.Implementations.MatchCriteria;
+
+/// <summary>
+/// Matches folders containing descendants with a specific media stream type and language.
+/// </summary>
+/// <param name="StreamType">The type of media stream to match (Audio, Subtitle, etc.).</param>
+/// <param name="Language">The language to match.</param>
+/// <param name="IsExternal">If not null, filters by internal (false) or external (true) streams. Only applicable to subtitles.</param>
+public sealed record HasMediaStreamType(
+    MediaStreamTypeEntity StreamType,
+    string Language,
+    bool? IsExternal = null) : FolderMatchCriteria;
diff --git a/src/Jellyfin.Database/Jellyfin.Database.Implementations/MatchCriteria/HasSubtitles.cs b/src/Jellyfin.Database/Jellyfin.Database.Implementations/MatchCriteria/HasSubtitles.cs
new file mode 100644
index 0000000000..e50b9f3e12
--- /dev/null
+++ b/src/Jellyfin.Database/Jellyfin.Database.Implementations/MatchCriteria/HasSubtitles.cs
@@ -0,0 +1,6 @@
+namespace Jellyfin.Database.Implementations.MatchCriteria;
+
+/// <summary>
+/// Matches folders containing descendants with subtitles.
+/// </summary>
+public sealed record HasSubtitles : FolderMatchCriteria;
diff --git a/src/Jellyfin.Database/Jellyfin.Database.Providers.Sqlite/SqliteDescendantQueryProvider.cs b/src/Jellyfin.Database/Jellyfin.Database.Providers.Sqlite/SqliteDescendantQueryProvider.cs
new file mode 100644
index 0000000000..756f750bf9
--- /dev/null
+++ b/src/Jellyfin.Database/Jellyfin.Database.Providers.Sqlite/SqliteDescendantQueryProvider.cs
@@ -0,0 +1,129 @@
+using System;
+using System.Linq;
+using Jellyfin.Database.Implementations;
+using Jellyfin.Database.Implementations.Entities;
+using Jellyfin.Database.Implementations.MatchCriteria;
+using Microsoft.EntityFrameworkCore;
+
+namespace Jellyfin.Database.Providers.Sqlite;
+
+/// <summary>
+/// SQLite implementation of descendant queries using optimized ancestor lookups.
+/// Uses AncestorIds and LinkedChildren tables for efficient parent-child traversal.
+/// </summary>
+public class SqliteDescendantQueryProvider : IDescendantQueryProvider
+{
+    /// <summary>
+    /// Recursive CTE fragment that traverses UP the tree from matching items to find all ancestor folders.
+    /// Expects a preceding CTE named "MatchingItems" with an ItemId column.
+    /// </summary>
+    private const string AllAncestorsCte = """
+        AllAncestors AS (
+            SELECT a.ParentItemId AS AncestorId
+            FROM AncestorIds a
+            WHERE a.ItemId IN (SELECT ItemId FROM MatchingItems)
+            UNION
+            SELECT lc.ParentId AS AncestorId
+            FROM LinkedChildren lc
+            WHERE lc.ChildId IN (SELECT ItemId FROM MatchingItems)
+            UNION
+            SELECT a.ParentItemId AS AncestorId
+            FROM AllAncestors aa
+            INNER JOIN AncestorIds a ON a.ItemId = aa.AncestorId
+            UNION
+            SELECT lc.ParentId AS AncestorId
+            FROM AllAncestors aa
+            INNER JOIN LinkedChildren lc ON lc.ChildId = aa.AncestorId
+        )
+        SELECT DISTINCT AncestorId AS Value FROM AllAncestors
+        """;
+
+    /// <inheritdoc />
+    public IQueryable<Guid> GetAllDescendantIds(JellyfinDbContext context, Guid parentId)
+    {
+        ArgumentNullException.ThrowIfNull(context);
+
+        var sql = """
+            WITH RECURSIVE AllDescendants AS (
+                SELECT ItemId FROM AncestorIds WHERE ParentItemId = {0}
+                UNION
+                SELECT ChildId AS ItemId FROM LinkedChildren WHERE ParentId = {0}
+                UNION ALL
+                SELECT a.ItemId
+                FROM AllDescendants d
+                INNER JOIN BaseItems b ON b.Id = d.ItemId AND b.IsFolder = 1
+                INNER JOIN AncestorIds a ON a.ParentItemId = d.ItemId
+                UNION ALL
+                SELECT lc.ChildId AS ItemId
+                FROM AllDescendants d
+                INNER JOIN BaseItems b ON b.Id = d.ItemId AND b.IsFolder = 1
+                INNER JOIN LinkedChildren lc ON lc.ParentId = d.ItemId
+            )
+            SELECT DISTINCT ItemId AS Value FROM AllDescendants
+            """;
+
+        return context.Database.SqlQueryRaw<Guid>(sql, parentId);
+    }
+
+    /// <inheritdoc />
+    public IQueryable<Guid> GetFolderIdsMatching(JellyfinDbContext context, FolderMatchCriteria criteria)
+    {
+        ArgumentNullException.ThrowIfNull(context);
+        ArgumentNullException.ThrowIfNull(criteria);
+
+        return criteria switch
+        {
+            HasSubtitles => GetFolderIdsWithSubtitles(context),
+            HasChapterImages => GetFolderIdsWithChapterImages(context),
+            HasMediaStreamType m => GetFolderIdsWithMediaStream(context, m.StreamType, m.Language, m.IsExternal),
+            _ => throw new ArgumentOutOfRangeException(nameof(criteria), $"Unknown criteria type: {criteria.GetType().Name}")
+        };
+    }
+
+    private IQueryable<Guid> GetFolderIdsWithSubtitles(JellyfinDbContext context)
+    {
+        var sql = $"""
+            WITH RECURSIVE MatchingItems AS (
+                SELECT DISTINCT ms.ItemId FROM MediaStreamInfos ms WHERE ms.StreamType = 2
+            ),
+            {AllAncestorsCte}
+            """;
+
+        return context.Database.SqlQueryRaw<Guid>(sql);
+    }
+
+    private IQueryable<Guid> GetFolderIdsWithChapterImages(JellyfinDbContext context)
+    {
+        var sql = $"""
+            WITH RECURSIVE MatchingItems AS (
+                SELECT DISTINCT c.ItemId FROM Chapters c WHERE c.ImagePath IS NOT NULL
+            ),
+            {AllAncestorsCte}
+            """;
+
+        return context.Database.SqlQueryRaw<Guid>(sql);
+    }
+
+    private IQueryable<Guid> GetFolderIdsWithMediaStream(JellyfinDbContext context, MediaStreamTypeEntity streamType, string language, bool? isExternal)
+    {
+        ArgumentNullException.ThrowIfNull(language);
+
+        var streamTypeInt = (int)streamType;
+        var externalCondition = isExternal switch
+        {
+            true => " AND ms.IsExternal = 1",
+            false => " AND ms.IsExternal = 0",
+            null => string.Empty
+        };
+
+        var sql = $$"""
+            WITH RECURSIVE MatchingItems AS (
+                SELECT DISTINCT ms.ItemId FROM MediaStreamInfos ms
+                WHERE ms.StreamType = {0} AND ms.Language = {1}{{externalCondition}}
+            ),
+            {{AllAncestorsCte}}
+            """;
+
+        return context.Database.SqlQueryRaw<Guid>(sql, streamTypeInt, language);
+    }
+}