diff options
Diffstat (limited to 'src/Jellyfin.Database/Jellyfin.Database.Implementations/DescendantQueryHelper.cs')
| -rw-r--r-- | src/Jellyfin.Database/Jellyfin.Database.Implementations/DescendantQueryHelper.cs | 315 |
1 files changed, 198 insertions, 117 deletions
diff --git a/src/Jellyfin.Database/Jellyfin.Database.Implementations/DescendantQueryHelper.cs b/src/Jellyfin.Database/Jellyfin.Database.Implementations/DescendantQueryHelper.cs index bfd0fac34a..6b08f8dd7e 100644 --- a/src/Jellyfin.Database/Jellyfin.Database.Implementations/DescendantQueryHelper.cs +++ b/src/Jellyfin.Database/Jellyfin.Database.Implementations/DescendantQueryHelper.cs @@ -8,7 +8,7 @@ using Jellyfin.Database.Implementations.MatchCriteria; namespace Jellyfin.Database.Implementations; /// <summary> -/// Provides methods for querying item hierarchies using iterative traversal. +/// Provides methods for querying item hierarchies. /// Uses AncestorIds and LinkedChildren tables for parent-child traversal. /// </summary> public static class DescendantQueryHelper @@ -32,11 +32,18 @@ public static class DescendantQueryHelper { ArgumentNullException.ThrowIfNull(context); - var descendants = TraverseHierarchyDown(context, [parentId]); + var (closureRoots, linkRoots) = ResolveLinkedRoots(context, parentId); - descendants.Remove(parentId); + var hierarchyDescendants = ClosureDescendants(context, closureRoots); - return descendants.AsQueryable(); + var linkedDescendants = context.LinkedChildren + .WhereOneOrMany(linkRoots, e => e.ParentId) + .Select(e => e.ChildId); + + return hierarchyDescendants + .Concat(linkedDescendants) + .Where(e => !e.Equals(parentId)) + .Distinct(); } /// <summary> @@ -51,11 +58,9 @@ public static class DescendantQueryHelper { ArgumentNullException.ThrowIfNull(context); - var descendants = TraverseHierarchyDownOwned(context, [parentId]); - - descendants.Remove(parentId); - - return descendants.AsQueryable(); + return ClosureDescendants(context, [parentId]) + .Where(e => !e.Equals(parentId)) + .Distinct(); } /// <summary> @@ -76,11 +81,11 @@ public static class DescendantQueryHelper return []; } - var seedSet = new HashSet<Guid>(parentIds); - var descendants = TraverseHierarchyDownOwned(context, seedSet); + var descendants = ClosureDescendants(context, parentIds) + .Distinct() + .ToHashSet(); - // Remove the seed IDs — callers want only descendants - descendants.ExceptWith(seedSet); + descendants.ExceptWith(parentIds); return descendants; } @@ -96,28 +101,106 @@ public static class DescendantQueryHelper { ArgumentNullException.ThrowIfNull(context); ArgumentNullException.ThrowIfNull(criteria); - var matchingItemIds = criteria switch + + // Both sides of a version group can hold a folder a caller would see as matching: the + // alternate carries its own AncestorIds rows and may sit in a different library than the + // primary it is reported against, and the primary is the item that becomes visible. + var reportedItemIds = MatchingMediaOwnerIds(context, criteria) + .Concat(GetPrimaryVersionIdsMatching(context, criteria)) + .Distinct(); + + // One hop up the closure covers every ancestor level. + var hierarchyAncestors = context.AncestorIds + .Where(e => reportedItemIds.Contains(e.ItemId)) + .Select(e => e.ParentItemId); + + var linkParents = ResolveLinkParents(context, reportedItemIds, hierarchyAncestors); + + // Read back as a sub-select so the result stays composable. Off the primary key, which is one + // row per id: LinkedChildren would yield one row per link and lean on the outer Distinct. + var linkedParents = context.BaseItems + .WhereOneOrMany(linkParents, e => e.Id) + .Select(e => e.Id); + + var linkedParentAncestors = context.AncestorIds + .WhereOneOrMany(linkParents, e => e.ItemId) + .Select(e => e.ParentItemId); + + // The chain an item carries stops at its collection folders, so this hop crosses that seam to + // the UserRootFolder above them. One statement for both sides beats a sub-select per side. + var seamAncestors = context.AncestorIds + .Where(e => hierarchyAncestors.Contains(e.ItemId) || linkedParentAncestors.Contains(e.ItemId)) + .Select(e => e.ParentItemId); + + return hierarchyAncestors + .Concat(linkedParents) + .Concat(linkedParentAncestors) + .Concat(seamAncestors) + .Distinct(); + } + + /// <summary> + /// Gets a queryable of the IDs of the primary versions whose alternate version's media matches the + /// criteria. + /// </summary> + /// <param name="context">Database context.</param> + /// <param name="criteria">The matching criteria to apply.</param> + /// <returns>Queryable of primary version item IDs.</returns> + /// <remarks> + /// For callers that already test an item's own media with their own indexed predicate: this covers + /// exactly what such a predicate misses, and the filtered PrimaryVersionId index keeps it to the few + /// items that have versions at all. + /// </remarks> + public static IQueryable<Guid> GetPrimaryVersionIdsMatching(JellyfinDbContext context, FolderMatchCriteria criteria) + { + ArgumentNullException.ThrowIfNull(context); + ArgumentNullException.ThrowIfNull(criteria); + + // Anchored on the alternates rather than on the matches: "has a primary version" is served by + // the partial PrimaryVersionId index, which holds only the few items that are second files, so + // this costs a seek each into the stream index instead of a second pass over every stream row. + var alternates = context.BaseItems.Where(v => v.PrimaryVersionId.HasValue); + + if (criteria is HasChapterImages) { - HasSubtitles => context.MediaStreamInfos - .Where(ms => ms.StreamType == MediaStreamTypeEntity.Subtitle) - .Select(ms => ms.ItemId) - .Distinct() - .ToHashSet(), - HasChapterImages => context.Chapters + return alternates + .Where(v => context.Chapters.Any(c => c.ItemId.Equals(v.Id) && c.ImagePath != null)) + .Select(v => v.PrimaryVersionId!.Value); + } + + var matchingStreams = MatchingMediaStreams(context, criteria); + + return alternates + .Where(v => matchingStreams.Any(ms => ms.ItemId.Equals(v.Id))) + .Select(v => v.PrimaryVersionId!.Value); + } + + // The ids of the items whose own media matches. Kept to the stream and chapter tables so their + // covering indexes answer this outright: projecting the BaseItems navigation instead would add a + // primary-key lookup per stream row rather than one per matching item, and the leading key of both + // indexes leaves the ids already grouped, so the Distinct costs no sort. + private static IQueryable<Guid> MatchingMediaOwnerIds(JellyfinDbContext context, FolderMatchCriteria criteria) + => criteria is HasChapterImages + ? context.Chapters .Where(c => c.ImagePath != null) .Select(c => c.ItemId) .Distinct() - .ToHashSet(), - HasMediaStreamType m => GetMatchingMediaStreamItemIds(context, m), + : MatchingMediaStreams(context, criteria) + .Select(ms => ms.ItemId) + .Distinct(); + + // The stream rows a criteria matches. One definition, so the owner projection and the alternate + // projection cannot drift apart despite reading it from opposite ends. + private static IQueryable<MediaStreamInfo> MatchingMediaStreams(JellyfinDbContext context, FolderMatchCriteria criteria) + => criteria switch + { + HasSubtitles => context.MediaStreamInfos + .Where(ms => ms.StreamType == MediaStreamTypeEntity.Subtitle), + HasMediaStreamType m => GetMatchingMediaStreams(context, m), _ => throw new ArgumentOutOfRangeException(nameof(criteria), $"Unknown criteria type: {criteria.GetType().Name}") }; - var ancestors = TraverseHierarchyUp(context, matchingItemIds); - - return ancestors.AsQueryable(); - } - - private static HashSet<Guid> GetMatchingMediaStreamItemIds(JellyfinDbContext context, HasMediaStreamType criteria) + private static IQueryable<MediaStreamInfo> GetMatchingMediaStreams(JellyfinDbContext context, HasMediaStreamType criteria) { var query = context.MediaStreamInfos .Where(ms => ms.StreamType == criteria.StreamType @@ -130,130 +213,128 @@ public static class DescendantQueryHelper query = query.Where(ms => ms.IsExternal == isExternal); } - return query.Select(ms => ms.ItemId).Distinct().ToHashSet(); + return query; } - /// <summary> - /// Traverses DOWN the hierarchy from parent folders to find all descendants. - /// </summary> - private static HashSet<Guid> TraverseHierarchyDown(JellyfinDbContext context, ICollection<Guid> startIds) + private static IQueryable<Guid> ClosureDescendants(JellyfinDbContext context, IReadOnlyList<Guid> roots) { - var visited = new HashSet<Guid>(startIds); - var folderStack = new HashSet<Guid>(startIds); + var direct = context.AncestorIds + .WhereOneOrMany(roots, e => e.ParentItemId) + .Select(e => e.ItemId); - while (folderStack.Count != 0) - { - var currentFolders = folderStack.ToArray(); - folderStack.Clear(); + // An item carries its own chain plus its collection folders, never the UserRootFolder. + var indirect = context.AncestorIds + .Where(e => direct.Contains(e.ParentItemId)) + .Select(e => e.ItemId); - var directChildren = context.AncestorIds - .WhereOneOrMany(currentFolders, e => e.ParentItemId) - .Select(e => e.ItemId) - .ToArray(); + return direct.Concat(indirect); + } - var linkedChildren = context.LinkedChildren - .WhereOneOrMany(currentFolders, e => e.ParentId) - .Select(e => e.ChildId) - .ToArray(); + // Resolves the folders whose linked children lead, at any depth, to a matching item. + private static List<Guid> ResolveLinkParents(JellyfinDbContext context, IQueryable<Guid> matchingItemIds, IQueryable<Guid> ancestorsOfMatches) + { + // An alternate version is a second file for the item that links it, not a child of it, so that + // edge is not walked. It is also the one link a non-folder owns, and there is one per remuxed + // movie: walking it would swell this list from the BoxSet and Playlist count to the item count, + // and the list is bound into every statement the returned queryable is embedded in. + var containerLinks = context.LinkedChildren + .Where(e => e.ChildType != LinkedChildType.LocalAlternateVersion + && e.ChildType != LinkedChildType.LinkedAlternateVersion); + + // A link sits above the closure and above another link alike, so the hop repeats until nothing + // new turns up. + var resolved = containerLinks + .Where(e => matchingItemIds.Contains(e.ChildId) || ancestorsOfMatches.Contains(e.ChildId)) + .Select(e => e.ParentId) + .Distinct() + .ToHashSet(); + + var frontier = resolved.ToList(); + + while (frontier.Count != 0) + { + var containingFolders = context.AncestorIds + .WhereOneOrMany(frontier, e => e.ItemId) + .Select(e => e.ParentItemId); - var allChildren = directChildren.Concat(linkedChildren).Distinct().ToArray(); + var directLinkParents = containerLinks + .WhereOneOrMany(frontier, e => e.ChildId) + .Select(e => e.ParentId); - if (allChildren.Length == 0) - { - break; - } + var indirectLinkParents = containerLinks + .Where(e => containingFolders.Contains(e.ChildId)) + .Select(e => e.ParentId); - var childFolders = context.BaseItems - .WhereOneOrMany(allChildren, e => e.Id) - .Where(e => e.IsFolder) - .Select(e => e.Id) - .ToHashSet(); + var next = directLinkParents + .Concat(indirectLinkParents) + .Distinct() + .ToArray(); - foreach (var childId in allChildren) + frontier = []; + foreach (var id in next) { - if (visited.Add(childId) && childFolders.Contains(childId)) + // Cyclic links terminate on the resolved set. + if (resolved.Add(id)) { - folderStack.Add(childId); + frontier.Add(id); } } } - return visited; + return [.. resolved]; } - /// <summary> - /// Traverses DOWN the hierarchy using only AncestorIds (ownership), not LinkedChildren. - /// </summary> - private static HashSet<Guid> TraverseHierarchyDownOwned(JellyfinDbContext context, ICollection<Guid> startIds) + // Resolves the roots the descendant sub-selects are anchored on: those contributing their closure, + // and those contributing their linked children. + private static (List<Guid> ClosureRoots, List<Guid> LinkRoots) ResolveLinkedRoots(JellyfinDbContext context, Guid parentId) { - var visited = new HashSet<Guid>(startIds); - var folderStack = new HashSet<Guid>(startIds); + var closureRoots = new List<Guid> { parentId }; + var linkRoots = new List<Guid> { parentId }; + var visited = new HashSet<Guid> { parentId }; + var frontier = new List<Guid> { parentId }; - while (folderStack.Count != 0) + while (frontier.Count != 0) { - var currentFolders = folderStack.ToArray(); - folderStack.Clear(); - - var directChildren = context.AncestorIds - .WhereOneOrMany(currentFolders, e => e.ParentItemId) - .Select(e => e.ItemId) - .ToArray(); + var closureIds = ClosureDescendants(context, frontier); - if (directChildren.Length == 0) - { - break; - } + var linkedIds = context.LinkedChildren + .WhereOneOrMany(frontier, e => e.ParentId) + .Select(e => e.ChildId); - var childFolders = context.BaseItems - .WhereOneOrMany(directChildren, e => e.Id) - .Where(e => e.IsFolder) + var linkedFolders = context.BaseItems + .Where(e => e.IsFolder && linkedIds.Contains(e.Id)) .Select(e => e.Id) .ToHashSet(); - foreach (var childId in directChildren) + // Folders whose own links have to be followed. Driven off LinkedChildren because owning a + // link is the rare property, so the folder check only reaches rows that can qualify. That + // check stays: a non-folder owns links too (a movie and its alternate versions). + var linkOwners = context.LinkedChildren + .Where(e => (closureIds.Contains(e.ParentId) || linkedIds.Contains(e.ParentId)) + && e.Parent!.IsFolder) + .Select(e => e.ParentId) + .Distinct() + .ToArray(); + + frontier = []; + foreach (var id in linkOwners.Concat(linkedFolders)) { - if (visited.Add(childId) && childFolders.Contains(childId)) + if (!visited.Add(id)) { - folderStack.Add(childId); + continue; } - } - } - return visited; - } - - /// <summary> - /// Traverses UP the hierarchy from items to find all ancestor folders. - /// </summary> - private static HashSet<Guid> TraverseHierarchyUp(JellyfinDbContext context, ICollection<Guid> startIds) - { - var ancestors = new HashSet<Guid>(); - var itemStack = new HashSet<Guid>(startIds); + frontier.Add(id); + linkRoots.Add(id); - while (itemStack.Count != 0) - { - var currentItems = itemStack.ToArray(); - itemStack.Clear(); - - var ancestorParents = context.AncestorIds - .WhereOneOrMany(currentItems, e => e.ItemId) - .Select(e => e.ParentItemId) - .ToArray(); - - var linkedParents = context.LinkedChildren - .WhereOneOrMany(currentItems, e => e.ChildId) - .Select(e => e.ParentId) - .ToArray(); - - foreach (var parentId in ancestorParents.Concat(linkedParents)) - { - if (ancestors.Add(parentId)) + // Only a folder reached through a link adds a closure the roots so far do not cover. + if (linkedFolders.Contains(id)) { - itemStack.Add(parentId); + closureRoots.Add(id); } } } - return ancestors; + return (closureRoots, linkRoots); } } |