What order should my index's columns be for a SELECT a, b, MAX( c ) FROM d WHERE e = 1 GROUP BY a, b?

Question

Supposing I have this table (in a multi-tenant SaaS database:

CREATE TABLE dbo.Messages (

    TenantId    int          NOT NULL,
    RecipientId int          NOT NULL,
    MessageId   int          NOT NULL IDENTITY,
    SentUtc     datetime2(7) NOT NULL,
    IsDeleted   bit          NOT NULL, /* Less than 5% of rows have IsDeleted = 1 */
    -- Body, Subject, etc
    
    CONSTRAINT PK_Messages PRIMARY KEY ( MessageId, TenantId ),

    CONSTRAINT UK_Messages UNIQUE ( MessageId ),

    CONSTRAINT FK_Messages_Tenants FOREIGN KEY ( TenantId ) REFERENCES dbo.Tenants ( TenantId ),
    CONSTRAINT FK_Messages_Recipients FOREIGN KEY ( RecipientId, TenantId ) REFERENCES dbo.Recipients ( RecipientId, TenantId )
);

I have a VIEW that is meant to get the latest MessageId for each RecipientId:

CREATE VIEW dbo.LatestMessages
    WITH SCHEMABINDING
AS

WITH latestMessageUtcPerRecipient AS (

    SELECT
        m.TenantId,
        m.RecipientId,
        MAX( m.SentUtc ) AS MaxSentUtc
    FROM
        dbo.Messages AS m
    WHERE
        m.IsDeleted = 0
    GROUP BY
        m.TenantId,
        m.RecipientId
)
SELECT
    lm.TenantId,
    lm.RecipientId,
    m .MessageId,
    m .SentUtc

FROM
    dbo.Messages AS m

    INNER JOIN latestMessageUtcPerRecipient AS lm ON
        m.TenantId = lm.TenantId
        AND
        m.RecipientId = lm.RecipientId
        AND
        m.SentUtc = lm.MaxSentUtc

• I currently have foreign-key-covering (non-clustered) indexes over FX_Tenants ( TenantId ) and FX_Recipients ( RecipientId, TenantId ).

• Without any other extra INDEX objects on dbo.Messages, this VIEW's execution-plan currently performs an Index Scan on the FX_Recipients index where it reads 14,000% of the final query rows (erk!)

• So I need to create a good index for this VIEW's query that covers the TenantId, RecipientId, and SentUtc - and I understand I should exclude IsDeleted from the index as is a low-selectivity column) - the problem is I'm unsure what order the columns should go in because I don't know if SentUtc should go first (to aid the MAX( m.SentUtc ) aggregate) - or if RecipientId should go first (as it's the most selective column for the GROUP BY clause).

• So I first tried this index:

  CREATE INDEX IX_for_LatestMessages_VIEW ( LatestUtc, RecipientId, TenantId )
  

  ...but after creating that, and running SELECT TOP 1000 * FROM dbo.LatestMessages, the execution-plan is actually worse than when I didn't have this index (and the FX_Recipients index now has a 28,700% over-read index-scan which is far worse than the ~14,000% from earlier).

• Then I tried:

  CREATE INDEX IX_for_LatestMessages_VIEW ( RecipientId, TenantId, LatestUtc )
  

  ...and to my surprise this resulted in a much better plan, with zero reads from FX_Recipients. Though SSMS's "Missing index details" area appears and it really wants me to create another index as ON dbo.Messages ( IsDeleted ) INCLUDE ( RecipientId, LatestUtc ) - but I'm wary of doing what it suggests because IsDeleted is not a very selective column (I'm fairly confident the STATISTICS are up-to-date too).

Is there a good, single INDEX definition for this VIEW that avoids the index-scans of my first attempt while also not setting-off SQL Server's missing-index alarms?

---

Also, because the VIEW only gets MessageId from dbo.Messages I was hoping that adding INCLUDE ( MessageId ) would eliminate a Key Lookup step in the execution-plan, but it didn't seem to have any effect (presumably because MessageId is already in the table's composite PK?) - in which case why is the plan doing a Key Lookup (with a 7,700% over-read) in addition to the Index Scan over IX_for_LatestMessages_VIEW?

Answer 1

Index and View

I would probably replace the FX indexes with:

CREATE NONCLUSTERED INDEX 
    [dbo.Messages TenantID, RecipientId, SentUtc, (MessageId, IsDeleted)]
ON dbo.[Messages]
    (TenantID ASC, RecipientId ASC, SentUtc ASC)
INCLUDE 
    (MessageId, IsDeleted);

There's not too much benefit to MessageId being an INCLUDE rather than at the end of the key. It will only be non-key at the leaf of the index because the index is not specified as unique. MessageId is part of the clustering key so it will be part of the nonclustered index key above the leaf level. It doesn't make a huge amount of difference either way.

You could make this index filtered on IsDeleted = 0 but whether this is worthwhile depends on how many deleted records you have and how your foreign keys are set up for deleted rows.

You would also need to be careful that your queries don't ever supply a parameterized value for IsDeleted (or that a supplied literal isn't simple/forced parameterized on the server) because then the filtered index can't be matched. There are also other issues. Initially, I probably wouldn't bother with it.

Add the missing IsDeleted = 0 predicate to your view:

CREATE OR ALTER VIEW dbo.LatestMessages
    WITH SCHEMABINDING
AS
WITH latestMessageUtcPerRecipient AS (
    SELECT
        m.TenantId,
        m.RecipientId,
        MAX( m.SentUtc ) AS MaxSentUtc
    FROM
        dbo.Messages AS m
    WHERE
        m.IsDeleted = 0
    GROUP BY
        m.TenantId,
        m.RecipientId
)
SELECT
    lm.TenantId,
    lm.RecipientId,
    m .MessageId,
    m .SentUtc

FROM
    dbo.Messages AS m
    INNER JOIN latestMessageUtcPerRecipient AS lm ON
        m.TenantId = lm.TenantId
        AND
        m.RecipientId = lm.RecipientId
        AND
        m.SentUtc = lm.MaxSentUtc
WHERE
    m.IsDeleted = 0; -- This was missing

Now, a query on the view uses a very efficient Segment Top plan:

SELECT LM.*
FROM dbo.LatestMessages AS LM; 

Alternate Views

If it were my code, I might express the view equivalently as:

CREATE OR ALTER VIEW dbo.LatestMessages
WITH SCHEMABINDING
AS
SELECT
    M.TenantId,
    M.RecipientId,
    M.MessageId,
    M.SentUtc
FROM dbo.[Messages] AS M
WHERE
    M.IsDeleted = 0
    AND M.SentUtc =
    (
        SELECT
            MAX(M2.SentUtc)
        FROM dbo.[Messages] AS M2
        WHERE
            -- Correlations
            M2.TenantId = M.TenantId
            AND M2.RecipientId = M.RecipientId
            AND M2.IsDeleted = M.IsDeleted
    );

But this is mostly a question of style.

You might also prefer:

CREATE OR ALTER VIEW dbo.LatestMessages
    WITH SCHEMABINDING
AS
SELECT
    TR.TenantId, 
    TR.RecipientId, 
    T1.MessageId, 
    T1.SentUtc
FROM 
(
    SELECT 
        R.TenantId, 
        R.RecipientId
    FROM dbo.Recipients AS R
) AS TR
CROSS APPLY 
(
    SELECT TOP (1)
        M.MessageId, 
        M.SentUtc
    FROM dbo.[Messages] AS M
    WHERE 
        M.TenantId = TR.TenantId
        AND M.RecipientId = TR.RecipientId
        AND M.IsDeleted = 0
    ORDER BY
        M.SentUtc DESC
) AS T1;

This definition can also work well with the suggested index:

Window Functions

I would probably avoid writing the view with a DENSE_RANK windowing function because SQL Server has had some problems pushing parameterized or variable predicates down into such views. As I mention in the linked article, you can work around this by replacing the view with a parameterized inline TVF, though that is not always convenient.

For example:

DECLARE @TenantId integer = 1;

SELECT
    LM.*
FROM dbo.LatestMessages AS LM 
WHERE 
    LM.TenantId = @TenantId;

With the windowing function approach, the predicate on TenantId will not be pushed past the function, resulting in an index scan where you would expect a seek. It can be hard to spot because the stuck filter ends up combined with the existing filter for DENSE_RANK = 1.

This aspect is not a concern if you are running SQL Server 2017 CU30 or later with query optimizer hotfixes enabled, or SQL Server 2022 (where the hotfix setting is not required). In those configurations, the optimizer will push the predicate down to obtain a seek.

Answer 2

Putting TenantID, RecipientId first makes sense, because in one branch of the join they are grouping columns, and are used in the join clause.

I would say put TenantID before RecipientId because it is more likely to have an equality predicate on it in other queries, although it makes no difference to this query.

But you need to add INCLUDE columns to your index.

CREATE INDEX IX_for_LatestMessages_VIEW ON Messages 
  (TenantID, RecipientId, SentUtc DESC)
  INCLUDE (IsDeleted)
;

Now you get this query plan:

Note that this index is essentially a replacement for either FX_Recipients or FX_Tenants (depending on order), which you can now remove.

---

Having said that, you are probably far better off using window functions (with the same index):

CREATE OR ALTER VIEW dbo.LatestMessages
    WITH SCHEMABINDING
AS

WITH latestMessageUtcPerRecipient AS (

    SELECT
        m.TenantId,
        m.RecipientId,
        m.MessageId,
        m.SentUtc,
        DENSE_RANK() OVER (PARTITION BY m.TenantID, m.RecipientId ORDER BY m.SentUtc DESC) AS dr
    FROM
        dbo.Messages AS m
    WHERE
        m.IsDeleted = 0
)
SELECT
    m.TenantId,
    m.RecipientId,
    m .MessageId,
    m .SentUtc
FROM
    latestMessageUtcPerRecipient AS m
WHERE m.dr = 1;

db<>fiddle

Note that the semantics are slightly different: you don't get any results which are IsDeleted = 0, even if the max SentUtc value is the same for IsDeleted = 0 rows. Whereas in your current design (probably unintentionally) you are getting rows where IsDeleted = 1 as long as there is at least one row on the same SentUtc which has IsDeleted = 0.

For non-tied results, use ROW_NUMBER() instead of DENSE_RANK().

You can even add a filter to the index with this view, which would make it even more efficient.

CREATE INDEX IX ON Messages 
  (TenantID, RecipientId, SentUtc DESC)
  INCLUDE (IsDeleted)
  WHERE (IsDeleted = 0)
;