Index help for bad Query on fairly big table (2m)

Question

I am looking for some assistance please. I have a query that is running against a fairly big table (2 million records).

I have been trying to get the indexes working efficiently. There are a few other queries against this table, but this is by far the most frequent one. I am seriously struggling to get it to execute in under 1 second, and often see it running in 3 to 5 seconds using profiler.

It might be as fast as can be, but I would appreciate some input to confirm/deny that please.

Just a note: Dev wont change the query or schema at all. Optimizations can be made in the database only, and no schema changes.

The Table:

CREATE TABLE [dbo].[Notifications](
[ntID] [int] IDENTITY(1,1) NOT FOR REPLICATION NOT NULL,
[NotificationID] [int] NOT NULL,
[NotificationType] [nvarchar](50) NOT NULL,
[UserName] [nvarchar](50) NULL,
[CreatedBy] [nvarchar](50) NULL,
[CreatedOn] [datetime] NULL,
[Status] [nvarchar](50) NOT NULL,
[Result] [nvarchar](50) NULL,
[Extension] [nvarchar](50) NULL,
[ShiftRate] [nvarchar](255) NULL,
[ResponseMinutes] [int] NULL,
[ResponseWindow] [datetime] NULL,
[caNotificationID] [int] NULL,
[AwardedBy] [nvarchar](50) NULL,
[AwardedOn] [datetime] NULL,
[CancelledBy] [nvarchar](50) NULL,
[CancelledOn] [datetime] NULL,
[CancelledReasonID] [int] NULL,
[CancelledReasonText] [nvarchar](255) NULL,
[AwardingDate] [datetime] NULL,
[ScheduledLaunchDate] [datetime] NULL,
[CustomMessage] [nvarchar](160) NULL,
[SystemName] [nvarchar](4000) NULL,
[AutoClose] [bit] NOT NULL,
 CONSTRAINT [PK_ESP_Notifications_ntID] PRIMARY KEY CLUSTERED 
(
    [ntID] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]
GO

ALTER TABLE [dbo].[ESP_Notifications] ADD  DEFAULT ((0)) FOR [AutoClose]
GO

Table Data snapshot:

The Query:

Update Notifications 
  set Status = 'Awarding' OUTPUT deleted.* 
where ntID = (
    select top(1) ntID 
    from Notifications 
    where NotificationType = 'Shift' 
      and (Status = 'Done') 
      and ResponseWindow < '2019-02-04 10:40:03' 
    order by ntID)

Attempted Indexes :

CREATE INDEX [IX_Notifications_Status_NotificationType_ResponseWindow_ntID] 
ON [dbo].[Notifications](
   [Status] ASC,[NotificationType] ASC,[ResponseWindow] DESC,[ntID] DESC
)

CREATE INDEX [IX_Notifications_Status_ScheduledLaunchDate_ntID] 
ON [dbo].[Notifications](
    [ScheduledLaunchDate] DESC,[Status] ASC,[ntID] ASC
)

CREATE INDEX [IX_Notifications_NotificationType_caNotificationID_NotificationID_ntID] 
ON [dbo].[Notifications](
   [NotificationType] DESC, [caNotificationID] DESC, [NotificationID] DESC, [ntID] DESC
);

NotificationType contains 3 different types, of which 70% are type 'Shift' Status has 10 types, but the 'In Flight' records are only about 100 to 200, split over 4 Status's

Thank you for your assistance.

Answer 1

If the subquery in that update consistently uses those two predicate values, a filtered index should help a lot. Something like this (which Erik Darling kindly provided as a comment):

CREATE INDEX IX_ntID_ResponseWindow_Includes ON dbo.Notifications (ntID, ResponseWindow) 
INCLUDE (NotificationType, Status) 
WHERE (Status = 'Done' AND NotificationType = 'Shift');

This will let the subquery find the relevant group of IDs that match Status and NotificationType (as they are the only rows in the index) and avoid sorting the data (since it's already ordered by ntID as the leading column in the index).

It will still have to check the ResponseWindow value on each row. In the worst case, if there are no rows that meet the date requirement for the query (or if the first match has a very high ntID), most or all of the index will be read. Which makes the effectiveness of this approach limited depending on data distribution.