CREATE TABLE [dbo].[Notifications](
[Id] [bigint] IDENTITY(1,1) NOT NULL,
[AlertId] [int] NOT NULL,
[CreatedAt] [datetimeoffset](7) NOT NULL,
...
CONSTRAINT [PK_Notifications] PRIMARY KEY CLUSTERED 
(
   [Id] ASC
) WITH (STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, 
 OPTIMIZE_FOR_SEQUENTIAL_KEY = OFF) ON [PRIMARY]
) ON [PRIMARY] TEXTIMAGE_ON [PRIMARY]

CREATE NONCLUSTERED INDEX [IX_Notifications_CreatedAt] ON [dbo].[Notifications]
(
   [CreatedAt] ASC
)

CREATE TABLE [dbo].[Notifications](
  [Id] [bigint] IDENTITY(1,1) NOT NULL,
  [AlertId] [int] NOT NULL,
  [ChannelId] [int] NOT NULL,
  [Status] [int] NOT NULL,
  [Identifier] [nvarchar](1024) NOT NULL,
  [CreatedAt] [datetimeoffset](7) NOT NULL,
  [CanBeRetried] [bit] NULL,
  [RetryCount] [int] NOT NULL,
  ...
CONSTRAINT [PK_Notifications] PRIMARY KEY CLUSTERED 
(
   [Id] ASC
) WITH (STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, 
 OPTIMIZE_FOR_SEQUENTIAL_KEY = OFF) ON [PRIMARY]
) ON [PRIMARY] TEXTIMAGE_ON [PRIMARY]

CREATE NONCLUSTERED INDEX [IX_Notifications_CreatedAt] ON [dbo].[Notifications]
(
   [CreatedAt] ASC
)

CREATE NONCLUSTERED INDEX [IX_Notifications_AlertId_ChannelId_CreatedAt_Include_Identifier_Status_CanBeRetried_RetryCount] ON [dbo].[Notifications]
(
   [AlertId] ASC,
   [ChannelId] ASC,
   [CreatedAt] ASC
)
INCLUDE([Identifier],[Status],[CanBeRetried],[RetryCount]) 

CREATE NONCLUSTERED INDEX [IX_Notifications_AlertId_ChannelId_Identifier] ON [dbo].[Notifications]
(
   [AlertId] ASC,
   [ChannelId] ASC,
   [Identifier] ASC
)

CREATE NONCLUSTERED INDEX [IX_Notifications_CreatedAt_Status_Include_AlertId] ON [dbo].[Notifications]
(
   [CreatedAt] ASC,
   [Status] ASC
)
INCLUDE([AlertId]) 

UPDATE 1

So I have come back with more details.

The table:

CREATE TABLE [dbo].[Notifications](
[Id] [bigint] IDENTITY(1,1) NOT NULL,
[AlertId] [int] NOT NULL,
[CreatedAt] [datetimeoffset](7) NOT NULL,
...
CONSTRAINT [PK_Notifications] PRIMARY KEY CLUSTERED 
(
   [Id] ASC
) WITH (STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, 
 OPTIMIZE_FOR_SEQUENTIAL_KEY = OFF) ON [PRIMARY]
) ON [PRIMARY] TEXTIMAGE_ON [PRIMARY]

CREATE NONCLUSTERED INDEX [IX_Notifications_CreatedAt] ON [dbo].[Notifications]
(
   [CreatedAt] ASC
)

Now, the scenarios + execution plans. For more context, I am selecting notifications which I want to archive, notifications are produced by an Alert and I want to exclude from the archivation process notifications that are produced by certain Alerts.

1. CreatedAt < '2024-04-14 09:00:00' AND [n].[AlertId] NOT IN ( '76', '126', '127', '128', '129')

https://www.brentozar.com/pastetheplan/?id=ByV4zrlaA

This one takes around 11 minutes to process. There are no notifications present other than the ones excluded, older than that date. So this will produce and emtpty result set. The optimiser chose an Clustered Index Scan.

2. CreatedAt < '2024-04-15 09:00:00' AND [n].[AlertId] NOT IN ( '76', '126', '127', '128', '129')

https://www.brentozar.com/pastetheplan/?id=SJldhHxa0

This one takes around 2 seconds to process. There are notifications present other than the ones excluded, older than that date. The optimiser chose, again, the same Clustered Index Scan.

3. CreatedAt < '2023-09-13 11:00:00' AND [n].[AlertId] NOT IN ( '76', '126', '127', '128', '129')

https://www.brentozar.com/pastetheplan/?id=SJkp2Hl6R

This one takes 1 second. There are no notifications whatsoever, older than that date. This one uses an Index Seek on the IX_Notifications_CreatedAt index.

I've also found this in a post: https://stackoverflow.com/questions/12846283/why-is-sql-server-not-using-index-for-very-similar-datetime-query

As the range grows (and hence number of lookups required) it estimates that it will be quicker just to scan the whole (covering) clustered index avoiding the lookups. Possibly incorrectly in your case. The point at which it switches from one plan to the other is known as the tipping point.

This would answer would have satisfied me if it was performing poorly in both scenario 1 and 2, but it only runs slow in scenario 1.