Entity Framework query optimization

Question

A user can track a show, and mark episodes and seasons of that show as watched. To support this I have the models below:

Models

public class Show
{
    public int ID { get; set; }
    public string Name { get; set; }
    ...

    public ICollection<Season> Seasons { get; set; }
    public ICollection<UserShow> UserShows { get; set; }

    public Show()
    {
        this.Seasons = new List<Season>();
        this.UserShows = new List<UserShow>();
    }
}

public class Season
{
    public int ID { get; set; }
    public string Name { get; set; }
    ...

    public ICollection<Episode> Episodes { get; set; }
    public ICollection<WatchedSeason> UserSeasons { get; set; }

    public Season()
    {
        this.Episodes = new List<Episode>();
        this.UserSeasons = new List<WatchedSeason>();
    }
}

public class Episode
{
    public int ID { get; set; }
    public string Name { get; set; }
    ...

    public ICollection<WatchedEpisode> UserEpisodes { get; set; }
    public Season Season { get; set; }

    public Episode()
    {
        this.UserEpisodes = new List<WatchedEpisode>();
        this.Season = new Season();
    }
}

public class WatchedSeason
{
    public string UserID { get; set; }
    public int SeasonID { get; set; }
    public bool Watched { get; set; }

    public ApplicationUser User { get; set; }
    public Season Season { get; set; }
}

public class WatchedEpisode
{
    public string UserID { get; set; }
    public int EpisodeID { get; set; }
    public bool Watched { get; set; }

    public ApplicationUser User { get; set; }
    public Episode Episode { get; set; }
}  

---

The troubling query is trying to get a list of all shows the user is tracking, along with the latest episode they have watched for each tracking show.

ShowController.cs

public ActionResult UserShows()
{
    var userID = User.Identity.GetUserId();

    var shows = db.UserShows
        .Where(x => x.UserID == userID && x.Tracking)
        .Include(x => x.Show.Seasons.Select(y => y.UserSeasons))
        .Include(x => x.Show.Seasons.Select(y => y.Episodes.Select(z => z.UserEpisodes)))
        .ToList()
        .Select(x => new ShowViewModel(x.Show.ID, x.Show.Name, x.Show.Overview, true, GetLatestEpisode(x.Show, userID), x.Show.PosterPath, x.Show.FirstAirDate));

    return View(new ShowIndexViewModel() { Shows = shows });
}

private EpisodeViewModel GetLatestEpisode(Show show, string userID)
{
    var latestSeason = show.Seasons.OrderBy(x => x.SeasonNumber).FirstOrDefault(x => x.UserSeasons?.Where(y => y.UserID == userID && y.Watched == true).Count() == 0);
    if (latestSeason == null)
        return null;

    var latestEpisode = latestSeason.Episodes.OrderBy(x => x.EpisodeNumber).FirstOrDefault(x => x.UserEpisodes?.Where(y => y.UserID == userID && y.Watched == true).Count() == 0);
    if (latestEpisode == null)
        return null;

    return new EpisodeViewModel(latestEpisode.ID, latestEpisode.EpisodeNumber.Value, latestEpisode.Name, latestEpisode.Overview, latestEpisode.StillPath, false, latestEpisode.AirDate);
}

Getting the user shows with includes is the bottleneck, taking around 3 seconds on my local machine but 40 seconds on an Azure server with over 1 million rows in the episodes table.

ApplicationDbContext.cs

protected override void OnModelCreating(DbModelBuilder modelBuilder)
{
    modelBuilder.Entity<Show>().Property(x => x.ID).HasDatabaseGeneratedOption(DatabaseGeneratedOption.None);
    modelBuilder.Entity<Season>().Property(x => x.ID).HasDatabaseGeneratedOption(DatabaseGeneratedOption.None);
    modelBuilder.Entity<Episode>().Property(x => x.ID).HasDatabaseGeneratedOption(DatabaseGeneratedOption.None);

    modelBuilder.Entity<UserShow>().HasKey(x => new { x.ShowID, x.UserID });
    modelBuilder.Entity<UserShow>().HasRequired(x => x.User).WithMany(x => x.Shows).WillCascadeOnDelete(false);

    modelBuilder.Entity<WatchedSeason>().HasKey(x => new { x.SeasonID, x.UserID });
    modelBuilder.Entity<WatchedSeason>().HasRequired(x => x.User).WithMany(x => x.Seasons).WillCascadeOnDelete(false);

    modelBuilder.Entity<WatchedEpisode>().HasKey(x => new { x.EpisodeID, x.UserID });
    modelBuilder.Entity<WatchedEpisode>().HasRequired(x => x.User).WithMany(x => x.Episodes).WillCascadeOnDelete(false);

    base.OnModelCreating(modelBuilder);
}

Generated SQL

SELECT 
    [Project3].[ShowID] AS [ShowID], 
    [Project3].[UserID] AS [UserID], 
    [Project3].[Tracking] AS [Tracking], 
    [Project3].[ID] AS [ID], 
    [Project3].[Name] AS [Name], 
    [Project3].[Overview] AS [Overview], 
    [Project3].[BackdropPath] AS [BackdropPath], 
    [Project3].[PosterPath] AS [PosterPath], 
    [Project3].[FirstAirDate] AS [FirstAirDate], 
    [Project3].[Popularity] AS [Popularity], 
    [Project3].[VoteAverage] AS [VoteAverage], 
    [Project3].[VoteCount] AS [VoteCount], 
    [Project3].[C32] AS [C1], 
    [Project3].[C2] AS [C2], 
    [Project3].[C3] AS [C3], 
    [Project3].[C4] AS [C4], 
    [Project3].[C5] AS [C5], 
    [Project3].[C6] AS [C6], 
    [Project3].[C7] AS [C7], 
    [Project3].[C8] AS [C8], 
    [Project3].[C9] AS [C9], 
    [Project3].[C10] AS [C10], 
    [Project3].[C11] AS [C11], 
    [Project3].[C1] AS [C12], 
    [Project3].[C12] AS [C13], 
    [Project3].[C13] AS [C14], 
    [Project3].[C14] AS [C15], 
    [Project3].[C15] AS [C16], 
    [Project3].[C16] AS [C17], 
    [Project3].[C17] AS [C18], 
    [Project3].[C18] AS [C19], 
    [Project3].[C19] AS [C20], 
    [Project3].[C20] AS [C21], 
    [Project3].[C21] AS [C22], 
    [Project3].[C22] AS [C23], 
    [Project3].[C23] AS [C24], 
    [Project3].[C24] AS [C25], 
    [Project3].[C25] AS [C26], 
    [Project3].[C26] AS [C27], 
    [Project3].[C27] AS [C28], 
    [Project3].[C28] AS [C29], 
    [Project3].[C29] AS [C30], 
    [Project3].[C30] AS [C31], 
    [Project3].[C31] AS [C32]
    FROM ( SELECT 
        [Filter1].[ShowID] AS [ShowID], 
        [Filter1].[UserID] AS [UserID], 
        [Filter1].[Tracking] AS [Tracking], 
        [Filter1].[ID] AS [ID], 
        [Filter1].[Name] AS [Name], 
        [Filter1].[Overview] AS [Overview], 
        [Filter1].[BackdropPath] AS [BackdropPath], 
        [Filter1].[PosterPath] AS [PosterPath], 
        [Filter1].[FirstAirDate] AS [FirstAirDate], 
        [Filter1].[Popularity] AS [Popularity], 
        [Filter1].[VoteAverage] AS [VoteAverage], 
        [Filter1].[VoteCount] AS [VoteCount], 
        [UnionAll1].[C1] AS [C1], 
        [UnionAll1].[Show_ID] AS [C2], 
        [UnionAll1].[ID] AS [C3], 
        [UnionAll1].[ID1] AS [C4], 
        [UnionAll1].[Name] AS [C5], 
        [UnionAll1].[Overview] AS [C6], 
        [UnionAll1].[AirDate] AS [C7], 
        [UnionAll1].[EpisodeCount] AS [C8], 
        [UnionAll1].[PosterPath] AS [C9], 
        [UnionAll1].[SeasonNumber] AS [C10], 
        [UnionAll1].[Show_ID1] AS [C11], 
        [UnionAll1].[SeasonID] AS [C12], 
        [UnionAll1].[UserID] AS [C13], 
        [UnionAll1].[Watched] AS [C14], 
        [UnionAll1].[SeasonID1] AS [C15], 
        [UnionAll1].[C2] AS [C16], 
        [UnionAll1].[C3] AS [C17], 
        [UnionAll1].[C4] AS [C18], 
        [UnionAll1].[C5] AS [C19], 
        [UnionAll1].[C6] AS [C20], 
        [UnionAll1].[C7] AS [C21], 
        [UnionAll1].[C8] AS [C22], 
        [UnionAll1].[C9] AS [C23], 
        [UnionAll1].[C10] AS [C24], 
        [UnionAll1].[C11] AS [C25], 
        [UnionAll1].[C12] AS [C26], 
        [UnionAll1].[C13] AS [C27], 
        [UnionAll1].[C14] AS [C28], 
        [UnionAll1].[C15] AS [C29], 
        [UnionAll1].[C16] AS [C30], 
        [UnionAll1].[C17] AS [C31], 
        CASE WHEN ([UnionAll1].[ID] IS NULL) THEN CAST(NULL AS int) ELSE 1 END AS [C32]
        FROM   (SELECT [Extent1].[ShowID] AS [ShowID], [Extent1].[UserID] AS [UserID], [Extent1].[Tracking] AS [Tracking], [Extent2].[ID] AS [ID], [Extent2].[Name] AS [Name], [Extent2].[Overview] AS [Overview], [Extent2].[BackdropPath] AS [BackdropPath], [Extent2].[PosterPath] AS [PosterPath], [Extent2].[FirstAirDate] AS [FirstAirDate], [Extent2].[Popularity] AS [Popularity], [Extent2].[VoteAverage] AS [VoteAverage], [Extent2].[VoteCount] AS [VoteCount]
            FROM  [dbo].[UserShows] AS [Extent1]
            INNER JOIN [dbo].[Shows] AS [Extent2] ON [Extent1].[ShowID] = [Extent2].[ID]
            WHERE (N'9ff7c0d8-7a11-4084-a6b8-1cf4cf678d23' = [Extent1].[UserID]) AND ([Extent1].[Tracking] = 1) ) AS [Filter1]
        OUTER APPLY  (SELECT 
            CASE WHEN ([Extent4].[SeasonID] IS NULL) THEN CAST(NULL AS int) ELSE 1 END AS [C1], 
            [Extent3].[Show_ID] AS [Show_ID], 
            [Extent3].[ID] AS [ID], 
            [Extent3].[ID] AS [ID1], 
            [Extent3].[Name] AS [Name], 
            [Extent3].[Overview] AS [Overview], 
            [Extent3].[AirDate] AS [AirDate], 
            [Extent3].[EpisodeCount] AS [EpisodeCount], 
            [Extent3].[PosterPath] AS [PosterPath], 
            [Extent3].[SeasonNumber] AS [SeasonNumber], 
            [Extent3].[Show_ID] AS [Show_ID1], 
            [Extent4].[SeasonID] AS [SeasonID], 
            [Extent4].[UserID] AS [UserID], 
            [Extent4].[Watched] AS [Watched], 
            [Extent4].[SeasonID] AS [SeasonID1], 
            CAST(NULL AS int) AS [C2], 
            CAST(NULL AS int) AS [C3], 
            CAST(NULL AS datetime2) AS [C4], 
            CAST(NULL AS int) AS [C5], 
            CAST(NULL AS varchar(1)) AS [C6], 
            CAST(NULL AS varchar(1)) AS [C7], 
            CAST(NULL AS int) AS [C8], 
            CAST(NULL AS varchar(1)) AS [C9], 
            CAST(NULL AS float) AS [C10], 
            CAST(NULL AS float) AS [C11], 
            CAST(NULL AS int) AS [C12], 
            CAST(NULL AS int) AS [C13], 
            CAST(NULL AS int) AS [C14], 
            CAST(NULL AS varchar(1)) AS [C15], 
            CAST(NULL AS bit) AS [C16], 
            CAST(NULL AS int) AS [C17]
            FROM  [dbo].[Seasons] AS [Extent3]
            LEFT OUTER JOIN [dbo].[WatchedSeasons] AS [Extent4] ON [Extent3].[ID] = [Extent4].[SeasonID]
            WHERE ([Extent3].[Show_ID] IS NOT NULL) AND ([Filter1].[ShowID] = [Extent3].[Show_ID])
        UNION ALL
            SELECT 
            2 AS [C1], 
            [Extent5].[Show_ID] AS [Show_ID], 
            [Extent5].[ID] AS [ID], 
            [Extent5].[ID] AS [ID1], 
            [Extent5].[Name] AS [Name], 
            [Extent5].[Overview] AS [Overview], 
            [Extent5].[AirDate] AS [AirDate], 
            [Extent5].[EpisodeCount] AS [EpisodeCount], 
            [Extent5].[PosterPath] AS [PosterPath], 
            [Extent5].[SeasonNumber] AS [SeasonNumber], 
            [Extent5].[Show_ID] AS [Show_ID1], 
            CAST(NULL AS int) AS [C2], 
            CAST(NULL AS varchar(1)) AS [C3], 
            CAST(NULL AS bit) AS [C4], 
            CAST(NULL AS int) AS [C5], 
            [Join3].[ID] AS [ID2], 
            [Join3].[ID] AS [ID3], 
            [Join3].[AirDate] AS [AirDate1], 
            [Join3].[EpisodeNumber] AS [EpisodeNumber], 
            [Join3].[Name] AS [Name1], 
            [Join3].[Overview] AS [Overview1], 
            [Join3].[SeasonNumber] AS [SeasonNumber1], 
            [Join3].[StillPath] AS [StillPath], 
            [Join3].[VoteAverage] AS [VoteAverage], 
            [Join3].[VoteCount] AS [VoteCount], 
            [Join3].[Season_ID] AS [Season_ID], 
            CASE WHEN ([Join3].[EpisodeID] IS NULL) THEN CAST(NULL AS int) ELSE 1 END AS [C6], 
            [Join3].[EpisodeID] AS [EpisodeID], 
            [Join3].[UserID] AS [UserID], 
            [Join3].[Watched] AS [Watched], 
            [Join3].[EpisodeID] AS [EpisodeID1]
            FROM  [dbo].[Seasons] AS [Extent5]
            INNER JOIN  (SELECT [Extent6].[ID] AS [ID], [Extent6].[AirDate] AS [AirDate], [Extent6].[EpisodeNumber] AS [EpisodeNumber], [Extent6].[Name] AS [Name], [Extent6].[Overview] AS [Overview], [Extent6].[SeasonNumber] AS [SeasonNumber], [Extent6].[StillPath] AS [StillPath], [Extent6].[VoteAverage] AS [VoteAverage], [Extent6].[VoteCount] AS [VoteCount], [Extent6].[Season_ID] AS [Season_ID], [Extent7].[EpisodeID] AS [EpisodeID], [Extent7].[UserID] AS [UserID], [Extent7].[Watched] AS [Watched]
                FROM  [dbo].[Episodes] AS [Extent6]
                LEFT OUTER JOIN [dbo].[WatchedEpisodes] AS [Extent7] ON [Extent6].[ID] = [Extent7].[EpisodeID] ) AS [Join3] ON [Extent5].[ID] = [Join3].[Season_ID]
            WHERE ([Extent5].[Show_ID] IS NOT NULL) AND ([Filter1].[ShowID] = [Extent5].[Show_ID])) AS [UnionAll1]
    )  AS [Project3]
    ORDER BY [Project3].[ShowID] ASC, [Project3].[UserID] ASC, [Project3].[ID] ASC, [Project3].[C32] ASC, [Project3].[C2] ASC, [Project3].[C4] ASC, [Project3].[C1] ASC, [Project3].[C17] ASC, [Project3].[C27] ASC

Execution Plan

I don't know of an easy way to paste the execution plan but from right to left the most important values appear to be:

Clustered Index Scan PK_dbo.Episodes 12%
Sort 31%
Hash Match 17%
Sort 37%

I have a feeling I need to keep track of the latest episode ID in the database but I'd rather not do that if possible, any help is greatly appreciated.

EDIT:

Still looking into this but I've made a pretty significant boost in performance from ~40secs to ~2secs.

The first sort was part of a Merge-sort join for Episodes on the foreign key Season_ID, so I made the following changes to ApplicationDbContext.cs

modelBuilder.Entity<Show>().HasMany(x => x.Seasons).WithRequired(x => x.Show);
modelBuilder.Entity<Season>().HasMany(x => x.Episodes).WithRequired(x => x.Season);

Which in turn created the following migration

public override void Up()
{
    DropForeignKey("dbo.Episodes", "Season_ID", "dbo.Seasons");
    DropForeignKey("dbo.Seasons", "Show_ID", "dbo.Shows");
    DropIndex("dbo.Episodes", new[] { "Season_ID" });
    DropIndex("dbo.Seasons", new[] { "Show_ID" });
    AlterColumn("dbo.Episodes", "Season_ID", c => c.Int(nullable: false));
    AlterColumn("dbo.Seasons", "Show_ID", c => c.Int(nullable: false));
    CreateIndex("dbo.Episodes", "Season_ID");
    CreateIndex("dbo.Seasons", "Show_ID");
    AddForeignKey("dbo.Episodes", "Season_ID", "dbo.Seasons", "ID", cascadeDelete: true);
    AddForeignKey("dbo.Seasons", "Show_ID", "dbo.Shows", "ID", cascadeDelete: true);
}

public override void Down()
{
    DropForeignKey("dbo.Seasons", "Show_ID", "dbo.Shows");
    DropForeignKey("dbo.Episodes", "Season_ID", "dbo.Seasons");
    DropIndex("dbo.Seasons", new[] { "Show_ID" });
    DropIndex("dbo.Episodes", new[] { "Season_ID" });
    AlterColumn("dbo.Seasons", "Show_ID", c => c.Int());
    AlterColumn("dbo.Episodes", "Season_ID", c => c.Int());
    CreateIndex("dbo.Seasons", "Show_ID");
    CreateIndex("dbo.Episodes", "Season_ID");
    AddForeignKey("dbo.Seasons", "Show_ID", "dbo.Shows", "ID");
    AddForeignKey("dbo.Episodes", "Season_ID", "dbo.Seasons", "ID");
}

Forcing the foreign keys to be not-nullable, SQL then switched to a nested loop join instead of a merge-sort join from what I can see. I would still really love any theory on this as I still don't know why this increased the performance so much.

Answer 1

The Problem

The performance killers are the Includes this query:

var shows = db.UserShows
    .Where(x => x.UserID == userID && x.Tracking)
    .Include(x => x.Show.Seasons.Select(y => y.UserSeasons))
    .Include(x => x.Show.Seasons.Select(y => y.Episodes.Select(z => z.UserEpisodes)))
    .ToList()

These Includes generate a very wide query (as you show), because all fields of as many as six tables are queried. Often, when tackling performance troubles, people focus on reducing the number of rows that are fetched by a query, but reducing the number of queried fields can be at least as beneficial. This is especially true for ORMs, where materializing entity objects can take a significant amount of time.

So it would make a lot of difference if you'd project to the view models, ShowViewModel and EpisodeViewModel in the LINQ query as IQueryable, i.e. not after ToList(). This would narrow down the query to only the fields required to populate these models.

However, you don't do this, obviously because this function call GetLatestEpisode is not supported in a LINQ-to-Enties query.

Then, of course, you also query too many records. In the end, you only need data from one Show and one Episode, but because of the Includes you fetch all seasons and all episodes of a show from the database.

The Solution

I think you can both reduce the number of queried rows and fields if you start the query at the bottom.

If a user watched an episode, they obviously also watched its season and its show. So if you get the latest episode directly, you don't have to worry about getting watched seasons and shows any more. You don't need this GetLatestEpisode function, because you start by getting the latest episode. Further, you can get required Show data by accessing parent navigation properties. Like this (only showing the essentials):

var shows = context.WatchedEpisodes
                   .Where(we => we.UserID == userId
                             && we.Watched)
                   .GroupBy(we => we.Episode.Season.Show)
                   .Select(grp => grp.OrderBy(we => we.Episode.Season.SeasonNumber)
                                     .ThenBy(we => we.Episode.EpisodeNumber)
                                     .Select(we => new ShowViewModel
                                     {
                                         ShowID = grp.Key.ID,
                                         Name = grp.Key.Name,
                                         // etc.
                                         LatestEpisode = new EpisodeViewModel
                                         {
                                             EpisodeID = we.EpisodeID,
                                             // etc.
                                         }
                                     }).FirstOrDefault());

Now you get only one record per show in the result set and only the required fields are included in the SELECT. You'll still see a number of joins, but they don't cause any widening of the query, as Includes do.