Struggling to create an efficient index for this query I am struggling to create an index for a query and unfortunately I cannot change the query at all as it part of an ERP system. The problem is this query has over 1m reads and sometimes a duration of 10s

I Have tried using just the predicate, the seek predicate and a combination of both in different orders to no success.

Here is the query that cannot be changed:

SELECT  TOP (@0) "timestamp","Link ID","Record ID","URL1","URL2","URL3","URL4","Description","Type","Created","User ID","Company","Notify","To User ID" 
FROM "Database".dbo."Record Link" WITH(READUNCOMMITTED)  
WHERE ("Link ID"&gt;@1 AND (("Company"=@2 OR "Company"=@3) AND "Notify"=@4 AND ("To User ID" COLLATE Latin1_General_100_CI_AI LIKE @5 OR "To User ID" COLLATE Latin1_General_100_CI_AI LIKE @6))) 
ORDER BY "Link ID" ASC OPTION(OPTIMIZE for UNKNOWN, FAST 50)


Here is the script for the table if it helps:

SET ANSI_NULLS ON
GO

SET QUOTED_IDENTIFIER ON
GO

CREATE TABLE [dbo].[Record Link](
    [timestamp] [timestamp] NOT NULL,
    [Link ID] [int] IDENTITY(1,1) NOT FOR REPLICATION NOT NULL,
    [Record ID] [varbinary](448) NOT NULL,
    [URL1] [nvarchar](250) NOT NULL,
    [URL2] [nvarchar](250) NOT NULL,
    [URL3] [nvarchar](250) NOT NULL,
    [URL4] [nvarchar](250) NOT NULL,
    [Description] [nvarchar](250) NOT NULL,
    [Type] [int] NOT NULL,
    [Note] [image] NULL,
    [Created] [datetime] NOT NULL,
    [User ID] [nvarchar](132) NOT NULL,
    [Company] [nvarchar](30) NOT NULL,
    [Notify] [tinyint] NOT NULL,
    [To User ID] [nvarchar](132) NOT NULL,
 CONSTRAINT [Record Link$0] PRIMARY KEY CLUSTERED 
(
    [Link ID] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON, FILLFACTOR = 80) ON [PRIMARY]
) ON [PRIMARY] TEXTIMAGE_ON [PRIMARY]
GO


Here is the stats for the time and IO

  SQL Server Execution Times:
   CPU time = 0 ms,  elapsed time = 0 ms.
SQL Server parse and compile time: 
   CPU time = 0 ms, elapsed time = 4 ms.

(0 rows affected)
Table 'Record Link'. Scan count 1, logical reads 1018402, physical reads 3, read-ahead reads 1018391, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

(1 row affected)

 SQL Server Execution Times:
   CPU time = 8234 ms,  elapsed time = 12641 ms.


Here is the execution plan:


I would greatly appreciate it if someone could help me create an efficient index for this.

Here is a link to the execution plan:
https://www.brentozar.com/pastetheplan/?id=BkTxCbdN4
If you where to go the route of plan guides as @DenisRubashkin mentioned, you could create an 'empty' plan guide to remove the existing hints: OPTION(OPTIMIZE for UNKNOWN, FAST 50).

An example of a plan guide you could use, you might have to change some datatypes.

EXEC sp_create_plan_guide   
    @name =  N'Guide1',  
    @stmt = N'SELECT  TOP (@0) "timestamp","Link ID","Record ID","URL1","URL2","URL3","URL4","Description","Type","Created","User ID","Company","Notify","To User ID" 
FROM test.dbo."Record Link" WITH(READUNCOMMITTED)  
WHERE ("Link ID"&gt;@1 AND (("Company"=@2 OR "Company"=@3) AND "Notify"=@4 AND ("To User ID" COLLATE Latin1_General_100_CI_AI LIKE @5 OR "To User ID" COLLATE Latin1_General_100_CI_AI LIKE @6))) 
ORDER BY "Link ID" ASC OPTION(OPTIMIZE for UNKNOWN, FAST 50)',  
    @type = N'SQL',  
    @params = '@0 int, @1 int, @2  [nvarchar](30), @3  [nvarchar](30), @4 tinyint, @5 nvarchar(264),@6 nvarchar(264)',  
    @hints = NULL;


@hints will override the existing hints, by not specifying any, OPTION(OPTIMIZE for UNKNOWN, FAST 50) is removed and no other hints are used.

In my tests, while my data is different, this index was used

CREATE INDEX IX_Notify_Company_Link_ID
ON [dbo].[Record Link](Notify,Company,[Link ID])
INCLUDE([To User ID]);


This could not be the most optimal index for your dataset! Used solely as a way to show that the plan guide works. YMMV

A seek predicate on both Notify and Company where used. 
They are not very selective in my dataset, resulting in many rows read.

Part of the new plan



PasteThePlan

Comment by @PaulWhite


  You might find an addition benefit in parameter embedding using OPTION
  (RECOMPILE) in the plan guide.


You would have to change the @hints parameter in the plan guide to

    @hints = 'OPTION(RECOMPILE)';


Keep in mind that your query plan will be recompiled each time, but if it is not executed that frequently it should not be a problem.

Plan with option recompile



A better plan was used, with seek predicates on all 3 key colums.

PasteThePlan

Test Query used

SET STATISTICS IO, TIME ON;
EXEC SP_EXECUTESQL N'SELECT  TOP (@0) "timestamp","Link ID","Record ID","URL1","URL2","URL3","URL4","Description","Type","Created","User ID","Company","Notify","To User ID" 
FROM test.dbo."Record Link" WITH(READUNCOMMITTED)  
WHERE ("Link ID"&gt;@1 AND (("Company"=@2 OR "Company"=@3) AND "Notify"=@4 AND ("To User ID" COLLATE Latin1_General_100_CI_AI LIKE @5 OR "To User ID" COLLATE Latin1_General_100_CI_AI LIKE @6))) 
ORDER BY "Link ID" ASC OPTION(OPTIMIZE for UNKNOWN, FAST 50)',N'@0 int, @1 int, @2  [nvarchar](30), @3  [nvarchar](30), @4 tinyint, @5 nvarchar(264),@6 nvarchar(264)',@0=100,@1 = 99 ,@2  = 'NNNNNNNV',@3 = 'NNNNNNN',@4=1,@5='NNNNNNN1',@6='NNNNNNN2'


Test Data used

CREATE TABLE [dbo].[Record Link](
    [timestamp] [timestamp] NOT NULL,
    [Link ID] [int] IDENTITY(1,1) NOT FOR REPLICATION NOT NULL,
    [Record ID] [varbinary](448) NOT NULL,
    [URL1] [nvarchar](250) NOT NULL,
    [URL2] [nvarchar](250) NOT NULL,
    [URL3] [nvarchar](250) NOT NULL,
    [URL4] [nvarchar](250) NOT NULL,
    [Description] [nvarchar](250) NOT NULL,
    [Type] [int] NOT NULL,
    [Note] [image] NULL,
    [Created] [datetime] NOT NULL,
    [User ID] [nvarchar](132) NOT NULL,
    [Company] [nvarchar](30) NOT NULL,
    [Notify] [tinyint] NOT NULL,
    [To User ID] [nvarchar](132) NOT NULL,
 CONSTRAINT [Record Link$0] PRIMARY KEY CLUSTERED 
(
    [Link ID] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON, FILLFACTOR = 80) ON [PRIMARY]
) ON [PRIMARY] TEXTIMAGE_ON [PRIMARY]
GO
SET NOCOUNT ON;
DECLARE @I INT = 0;
WHILE @I &lt;= 10000
BEGIN
INSERT INTO [dbo].[Record Link]
(       

    [Record ID]   ,
    [URL1]    ,
    [URL2]    ,
    [URL3]    ,
    [URL4]    ,
    [Description]    ,
    [Type]  ,
    [Note]  ,
    [Created]   ,
    [User ID]   ,
    [Company]   ,
    [Notify]   ,
    [To User ID]   )
    VALUES(convert(varbinary(448),'NNNNNNN'),'NNNNNNN','NNNNNNN','NNNNNNN','NNNNNNN','NNNNNNN',@I,'NNNNNNN',GETDATE(),'NNNNNNN'+CAST(@i as nvarchar(10)),'NNNNNNN',1,'NNNNNNN'+CAST(@i as nvarchar(10)))
    SET @I += 1
    END
    SET NOCOUNT OFF
INSERT INTO [dbo].[Record Link]
(       

    [Record ID]   ,
    [URL1]    ,
    [URL2]    ,
    [URL3]    ,
    [URL4]    ,
    [Description]    ,
    [Type]  ,
    [Note]  ,
    [Created]   ,
    [User ID]   ,
    [Company]   ,
    [Notify]   ,
    [To User ID]   )

    SELECT
     [Record ID]   ,
     [URL1] ,
     [URL2]    ,
     [URL3]    ,
     [URL4]    ,
     [Description] , 
     [Type]  ,
     [Note]  ,
     [Created]   ,
     [User ID]   ,
     [Company]   ,
     [Notify]   ,
     [To User ID]   
     FROM   [dbo].[Record Link]
     GO 7