Adding an INNER JOIN ruins query performance due to different execution plan despite updated STATISTICS and RECOMPILE, why?

Question

In the home-page of my multi-tenant web application, Linq-to-Entities (EF6) is used to get a paged list of Calendar Events. This data is JOINed with some other tables to produce this query, below.

The tables all have composite primary keys that combine their TenantId with their own IDENTITY. I put the IDENTITY column first in clustered index because STATISTICS only looks at the first column in an index, and I understand having the most-specific column first improves performance of get-single-row queries. (If I'm wrong about this then please let me know!).

The schema is this:

CREATE TABLE dbo.Events (
    EventId     int NOT NULL IDENTITY(1,1),
    TenantId    int NOT NULL,
    CustomerId  int     NULL,
    EventTypeId int NOT NULL,
    LocationId  int NOT NULL,
    Etc...

    CONSTRAINT PRIMARY KEY ( EventId, TenantId ),
    
    CONSTRAINT FOREIGN KEY FK_Events_Tenants ( TenantId ) REFERENCES dbo.Tenants ( TenantId ),
    
    CONSTRAINT FOREIGN KEY FK_Events_Customers ( CustomerId, TenantId ) REFERENCES dbo.Customers ( CustomerId, TenantId ),
    
    CONSTRAINT FOREIGN KEY FK_Events_EventTypes ( EventTypeId, TenantId ) REFERENCES dbo.EventTypes ( EventTypeId, TenantId ),
    
    CONSTRAINT FOREIGN KEY FK_Events_Locations ( LocationId, TenantId ) REFERENCES dbo.Locations ( LocationId, TenantId ),
)

The query that Linq generates is this:

_{(reformatted for readability, e.g. indentation, renaming Linq's Extent1 alias to shorter aliases based on the table's name, removing redundant column aliases, and removing Linq's idiosyncratic Project1, these changes did not affect the execution plan)}

SELECT
    e.(etc),
    c.(etc),
    l.(etc),
    t.(etc)
FROM
    dbo.Events AS e
    LEFT OUTER JOIN dbo.Customers AS c ON
        c.TenantId = e.TenantId
        AND
        c.CustomerId = e.CustomerId
    INNER JOIN dbo.Locations AS l ON
        l.TenantId = e.TenantId
        AND
        l.LocationId = e.LocationId
    INNER JOIN dbo.EventTypes AS t ON
        t.TenantId = e.TenantId
        AND
        t.TypeId = e.TypeId
WHERE
    e.TenantId = @tenantId

ORDER BY
    ROW_NUMBER() OVER ( ORDER BY e.EventId DESC, e.TenantId DESC )
OFFSET
    @offset ROWS FETCH NEXT @pageSize ROWS ONLY

• The @tenantId parameter is 123.
• The @offset parameter is 0.
• The @pageSize parameter is 50.
• I ran the query before and after a rebuild of all indexes, as well as updating all STATISTICS with sp_updatestats @resample = 'resample'. This had no effect on the execution plan.
• I also ran them with OPTION(RECOMPILE). This also had no effect on the execution plan.
• This query is being run on Azure SQL, btw.

---

Recently (ever since a few weeks ago) this query was running very slowly, so I got the Execution Plan for that query from SSMS:

• I have circled all execution plan nodes that pass 41,109 rows around.
• 41,109 is the number of rows in my dbo.Events table that correspond to the TenantId account I was looking at.
  • So every time I saw 41,109 in the plan I know that it was reading all dbo.Events rows - or index nodes - for that Tenant.
  • But the query has paging via OFFSET ROWS FETCH ROWS with an ORDER BY that uses the Clustered Index key columns - so it should not be reading more than 50 rows from the dbo.Events table!
• I've uploaded the Execution Plan to Brent Ozar's PasteThePlan website: https://www.brentozar.com/pastetheplan/?id=Hyc1bdkEO

I saw that the plan was reading from the dbo.EventTypes table first, and using the output of that read to filter rows from dbo.Events - but that's not my intention. My intention is for dbo.Events to be the "primary" table, and for it to get rows from the other tables (dbo.Customers, dbo.EventTypes, and dbo.Locations) based on the rows it read from dbo.Events.

When I removed the INNER JOIN dbo.EventTypes AS t ON... part of the query (and the concordant columns) and re-ran the query, the execution plan was now what I intended it to be and the query ran very fast (except without the dbo.EventTypes data that I still need...):

SELECT
    e.(etc),
    c.(etc),
    l.(etc)
FROM
    dbo.Events AS e
    LEFT OUTER JOIN dbo.Customers AS c ON
        c.TenantId = e.TenantId
        AND
        c.CustomerId = e.CustomerId
    INNER JOIN dbo.Locations AS l ON
        l.TenantId = e.TenantId
        AND
        l.LocationId = e.LocationId
WHERE
    e.TenantId = @tenantId

ORDER BY
    ROW_NUMBER() OVER ( ORDER BY e.EventId DESC, e.TenantId DESC )
OFFSET
    @offset ROWS FETCH NEXT @pageSize ROWS ONLY

The execution plan now shows it reading exactly 50 rows from the dbo.Events table. (Curiously, it also shows it reading from the dbo.Locations table and indexes twice - I don't understand why).

The Execution Plan window does not indicate that any indexes are missing for either query. When dbo.EventTypes is used in the query then the execution-plan shows the Index Seek node on dbo.Events is using the TenantId as the only seek predicate and ignoring the EventId predicate that would be used because of the ORDER BY clause.

Unfortunately none of the online resources I've found that advise improving execution plans by judicious use of indexes helped me in this cause because, as far as I know, the dbo.Events table has plenty of coverage by indexes (there's more than 15 indexes on the table) and none of them talked about how indexes are used by ORDER BY, TOP, and OFFSET. Additionally they all advised that incorrect estimated row counts (like how I see 2616 estimated but 41109 actual, or 77192 estimated but 41109 actual) would be rectified by updating STATISTICS, but I did update all statistics and that didn't help at all.

Answer 1

Multi-tenant systems are very prone to having problems with skewed statistics. Both the Events and Locations table have over a million rows in them, and are using the automatic sampling rate chosen by the database engine. You can see that in the execution plan XML, here are a couple of examples:

<StatisticsInfo 
    Database="[D0849AEA-A31D-4639-9F71-2651302E4887]" Schema="[dbo]" Table="[Locations]" 
    Statistics="[nci_wi_Locations_C8E94572A7BDF437552DACBCD45FE7BF]" 
    ModificationCount="981" SamplingPercent="5.79953" LastUpdate="2021-03-14T01:55:32.9" />

<StatisticsInfo 
    Database="[D0849AEA-A31D-4639-9F71-2651302E4887]" Schema="[dbo]" Table="[Events]" 
    Statistics="[nci_wi_Events_9AD45C8598F09E7FDFDFA2AD8792424C]" 
    ModificationCount="2113" SamplingPercent="4.56518" LastUpdate="2021-03-14T01:55:42.45" />

Notice that these statistics are based on sampling only ~4-5% of the rows in the table.

This is normally okay, but could be impacting your situation significantly. I would update statistics for the indexes on both tables using the FULLSCAN option:

UPDATE STATISTICS dbo.Locations
WITH FULLSCAN;
GO

UPDATE STATISTICS dbo.Events
WITH FULLSCAN;
GO

Then try re-running the query. Hopefully the optimizer will have a better chance of estimating the join cardinality between these two tables then, and choosing the more efficient plan.

If that works, you can back down the sample rate to a lower value that still produces the good plan, and potentially "pin it" in place with the PERSIST_SAMPLE_PERCENT.

---

As a potential workaround: since the query works well when the join to EventTypes isn't present, you could remove that from your LINQ query (don't .Include(...) that entity, don't reference any of its properties in a Select(...) projection).

Then you could retrieve the 25 EventTypes rows needed separately, either via lazy loading (which would result in 25 additional queries, but they'd be point lookups) or by running a separate query to get them all by ID.

Getting them all by ID would be something like this:

// "events" here is the result of your first query
var eventTypeIds = events
    .Select(e => e.EventType.Id)
    .ToList();

var eventTypes = _context.EventTypes
    .Where(et => eventTypeIds.Contains(et.Id))
    .ToList();

Answer 2

Try building it with the clustered index keys in the reverse order - so tenantid first. for the inner joins add the

  l.TenantId = @tenantId 

to the join criteria

change your order by from

ORDER BY
    ROW_NUMBER() OVER ( ORDER BY e.EventId DESC, e.TenantId DESC )

to

ORDER BY e.EventId DESC, e.TenantId DESC

although with the reversed order you would be better served with

ORDER BY e.TenantId DESC, e.EventId DESC

if that is still acceptable If you still get a sort consider building the PK with DESC order as well

Answer 3

Unfortunately LINQ is notorious for generating sub-par (and even terrible) queries in regards to performance for even some of the simplest code (such as a join between two entities, or a contains search on a single entity, etc). This is evident even in your query by the fact it added a meaningless ROW_NUMBER() function call in your ORDER BY clause, when it can just ORDER BY the fields it's calling out inside the ROW_NUMBER() function directly themselves.

That being said, I don't necessarily know if LINQ is your actual issue here yet though. If you take the first generated query (inclusive of your join to EventTypes), and run it directly in SSMS with hard-coded values instead of parameters, how is the performance? If it's good then you could be experiencing a parameter sniffing issue with the parameterized query sent to the server from LINQ. This in turn could be causing a cardinality estimate issue, which may be what your first execution plan screenshot is even showing, but it's hard to confirm without the actual execution plan in front of us. Could you please upload it to Paste The Plan? There's a lot of information in the actual execution plan that's not shown in a screenshot.

Also sidenote, clauses like TOP and OFFSET generally don't reduce your dataset early on, rather they're applied later on in the order of operations. This is because predicate filtering (JOIN, WHERE, and HAVING clauses) are typically used to filter the data down first since they're specific to how to filter the data (as opposed to TOP and OFFSET being generic) and call out fields that potentially are indexed, so this influences the order of operations in a query. The SQL Engine is able to make use of indexes early on in the set of operations it performs (because indexes store the data in logical data structure of a B-Tree which is very efficient for searching), after that then it can then apply generic reduction to the dataset vis TOP, OFFSET, etc. So it's generally most optimal to reduce your data via predicates, or at least ensure your predicates are optimally indexed and used for efficient index usage by the SQL Engine when it goes to pull the data.

Answer 4

Make sure you have these indexes or equivalents:

CREATE INDEX IX1 ON EventTypes ( TenantId, EventypeId)
CREATE INDEX IX2 ON Locations (Tenantid, LocationId)

You say you have clustered indexes, where the columns are the other way around. Yet from the execution plan it seems SQL Server favors indexes where TenantId is the first key column.

I would also try changing all the inner joins to left joins. At least as experiment. It doesn't seem any of the tables affect the number of rows returned except Events.

From my perspective SQL Server is very confused here. The join between Events and Locations produces 41k rows where SQL Server expects 41. Three orders of magnitude diference. And this error propagates thorough the whole plan.