Large variances between two similar queries when doing WHERE EXISTS on related table

Question

I'm trying to diagnose an issue where 2 very similar queries are resulting in very different execution times, even though the execution plans are extremely simple.

Broadly (and I've trimmed the selects and renamed tables), we have a primary table ([Primary]) that we are attempting to filter based on the existence of at least 1 matching row in a related table. We then return the top 20 rows (for paging)

The only difference between the queries is the related table is different (although has similar structure). The fast query ([PrimaryResult]) takes < 1s where as the slow query ([PrimaryScore]) is taking 20s or so.

I've inspected the execution plan and the major difference is the Key Lookup on the primary table. In the fast query, the Actual number of rows read is around 10k, however for the slow query, it's more than 3.6 million.

The other thing I've observed is the fast query appears to do everything in parallel (denoted by the double arrow in the execution plan, but the slow query doesn't).

The query was generated via Entity Framework 6 LINQ (hence all the aliasing).

Slow query

SELECT 
    [Project5].[Id] AS [Id]
    FROM ( SELECT 
        [Project1].[Id] AS [Id]
        FROM ( SELECT 
            [Extent1].[Id] AS [Id]
            FROM   [dbo].[Primary] AS [Extent1]
            INNER JOIN [dbo].[GuidBatch] AS [Extent2] ON ([Extent1].[DeviceRegistrationId] = [Extent2].[Ref]) AND (@p__linq__0 = [Extent2].[Id])
            INNER JOIN [dbo].[Place] AS [Extent3] ON [Extent1].[PlaceId] = [Extent3].[PlaceId]
            WHERE [Extent1].[IsValid] = 1
        )  AS [Project1]
        WHERE ( EXISTS (SELECT 
            1 AS [C1]
            FROM [dbo].[PrimaryScore] AS [Extent4]
            WHERE ([Project1].[Id] = [Extent4].[Id]) AND ([Extent4].[Key] = @p__linq__1) AND ([Extent4].[Score] IN (4,3))
        )) OR ( EXISTS (SELECT 
            1 AS [C1]
            FROM [dbo].[PrimaryScore] AS [Extent5]
            WHERE ([Project1].[Id] = [Extent5].[Id]) AND ([Extent5].[Key] = @p__linq__2)AND ([Extent5].[Score] IN (4,3))
        )) OR ( EXISTS (SELECT 
            1 AS [C1]
            FROM [dbo].[PrimaryScore] AS [Extent6]
            WHERE ([Project1].[Id] = [Extent6].[Id]) AND ([Extent6].[Key] = @p__linq__3) AND ([Extent6].[Score] IN (4,3))
        ))
    )  AS [Project5]
    ORDER BY row_number() OVER (ORDER BY [Project5].[CaptureDate] DESC)
    OFFSET 0 ROWS FETCH NEXT 20 ROWS ONLY

Fast query

SELECT 
    [Project5].[Id] AS [Id]
    FROM ( SELECT 
        [Project1].[Id] AS [Id]
        FROM ( SELECT 
            [Extent1].[Id] AS [Id]
            FROM   [dbo].[Primary] AS [Extent1]
            INNER JOIN [dbo].[GuidBatch] AS [Extent2] ON ([Extent1].[DeviceRegistrationId] = [Extent2].[Ref]) AND (@p__linq__0 = [Extent2].[Id])
            INNER JOIN [dbo].[Place] AS [Extent3] ON [Extent1].[PlaceId] = [Extent3].[PlaceId]
            WHERE [Extent1].[IsValid] = 1
        )  AS [Project1]
        WHERE ( EXISTS (SELECT 
            1 AS [C1]
            FROM [dbo].[PrimaryResult] AS [Extent4]
            WHERE ([Project1].[Id] = [Extent4].[Id]) AND ([Extent4].[ActivityId] = @p__linq__1) AND ([Extent4].[SelectedOptionId] IN (cast('8c93216d-53a4-40b3-a905-caaa84c0a09c' as uniqueidentifier), cast('b1f406ab-b009-4851-9200-1a2828bc61e6' as uniqueidentifier), cast('aa8d425d-5f0b-4142-b43b-29fa697f82a6' as uniqueidentifier), cast('8945430c-9ef8-4c53-a228-24b58aa7cf7e' as uniqueidentifier)))
        )) 
        OR ( EXISTS (SELECT 
            1 AS [C1]
            FROM [dbo].[PrimaryResult] AS [Extent5]
            WHERE ([Project1].[Id] = [Extent5].[Id]) AND ([Extent5].[ActivityId] = @p__linq__2) AND ([Extent5].[SelectedOptionId] IN (cast('215e02d9-a96a-43ec-8940-d7561534f352' as uniqueidentifier), cast('cee9415e-0ba9-4b43-ad7b-01c28ed4a9ff' as uniqueidentifier), cast('65655400-865c-4456-82a1-dc8addd705fa' as uniqueidentifier), cast('50d406d0-15f2-45ee-8a9b-3503f8e638b1' as uniqueidentifier)))
        )) OR ( EXISTS (SELECT 
            1 AS [C1]
            FROM [dbo].[PrimaryResult] AS [Extent6]
            WHERE ([Project1].[Id] = [Extent6].[Id]) AND ([Extent6].[ActivityId] = @p__linq__3) AND ([Extent6].[SelectedOptionId] IN (cast('1d1b5f0f-3335-4ad9-96c9-d363bca2f7ae' as uniqueidentifier), cast('d04e21f3-0106-47c5-b79f-b74e6309adb0' as uniqueidentifier), cast('c768ed36-fea2-4e8e-8074-b8a0f5aa6f92' as uniqueidentifier), cast('cc32fa39-fa0f-4545-b01e-d7254b5e6a85' as uniqueidentifier), cast('af768460-5d59-4107-8642-2b22ea2cf73e' as uniqueidentifier)))
        ))
    )  AS [Project5]
    ORDER BY row_number() OVER (ORDER BY [Project5].[CaptureDate] DESC)
    OFFSET 0 ROWS FETCH NEXT 20 ROWS ONLY 

Here is the execution plans. I've just obfuscated specific table names

EDIT: I've uploaded an anonymized query plans.

Slow Query https://www.brentozar.com/pastetheplan/?id=ryXq6AF1H

Fast Query: https://www.brentozar.com/pastetheplan/?id=H1JSpCKkr

My question is obviously why is this occurring? I believe I've got the correct indexes set up on all tables.

The other thing to note is the GuidBatch filtering returns a maximum of 1.6m Primary rows, so I'm quite confused why the slow query is reading more than that, but then fast query is only reading 10k rows.

Answer 1

I understand the need to anonymize, but it makes analysis really difficult. There's also not a reasonable way to guess at why when you query two different tables, you get different performance without seeing the table and index definitions (aside from the fact that they're, well, two different tables).

Avoiding speculation, let's focus on the slow plan:

The issue you're likely facing is from a (potentially parameterized) TOP expression. Using TOP introduces a row goal, which changes the optimizer's strategy for finding data.

It may also be related to the initial set of parameters the plan is compiled with, but you've anonymized away any helpful information about compile and runtime parameters.

Depending on data distribution, you can run into really unfortunate plans trying to locate data.

Note the amount of rows that need to come out of the longest running parts of the plan to satisfy the 20 row goal later in the plan:

Even with "perfect" indexes, you can run into issues like this. You could try fixing the Key Lookup portion, but that would require quite a wide index.

You'd need to account for the predicate and output lists from both the nonclustered index scan and the key lookup operators. Doing so may only shave ~5 seconds off the plan, though. You're still left with 12 seconds of other stuff.

You could experiment with different hints on the query, like OPTION(MERGE JOIN, HASH JOIN); to get away from the nested loops hell you've wound up in. Unfortunately, unless you're willing to take these queries out of Entity Framework's hands, your options are pretty limited for tuning. If one of the hinted plans is better, you could try creating a plan guide or using Query Store to force the better plan.

One option might be to eliminate the key lookup by only selecting columns you need for the query, but that's impossible to tell without seeing the query or knowing its requirements.