Correct SQL index for Partition + Order to remove SORT

I have a SQL Statement which i am trying to optimise to remove the sort operator

SELECT *,ROW_NUMBER() OVER (
        PARTITION BY RuleInstanceId 
        ORDER BY [Timestamp] DESC
   ) AS rn
FROM RuleInstanceHistoricalMembership

Everything I have read (eg. Optimizing SQL queries by removing Sort operator in Execution plan) suggests this is the correct index to add however it appears to have no effect at all.

CREATE NONCLUSTERED INDEX IX_MyIndex ON dbo.[RuleInstanceHistoricalMembership](RuleInstanceId, [Timestamp] DESC)

I must be missing something as I have read heaps of articles which all seem to sugguest an index spanning both columns should solve this issue

Technically the index you have added does allow you to avoid a sort.

However the index you have created is non covering so SQL Server would then also need to perform 60 million key lookups back to the base table.

Simply scanning the clustered index and sorting it on the fly is costed as being considerably cheaper than that option.

In order to get the index to be used automatically you would need to either.

• Remove columns from the query SELECT list so the index covers it.
• Add INCLUDE-d columns to the index.

BTW: For a table with 60 million rows you may well find that even if you were to try and force the issue with an index hint on the non covering index you still don't get the desired results of avoiding a sort.

CREATE TABLE RuleInstanceHistoricalMembership
  (
     ID             INT PRIMARY KEY,
     Col2           INT,
     Col3           INT,
     RuleInstanceId INT,
     [Timestamp]    INT
  )

CREATE NONCLUSTERED INDEX IX_MyIndex
  ON dbo.[RuleInstanceHistoricalMembership](RuleInstanceId, [Timestamp] DESC)

/*Fake small table*/
UPDATE STATISTICS RuleInstanceHistoricalMembership 
                  WITH ROWCOUNT = 600, 
                       PAGECOUNT = 10 

SELECT *,
       ROW_NUMBER() OVER ( PARTITION BY RuleInstanceId 
                               ORDER BY [Timestamp] DESC ) AS rn
FROM   RuleInstanceHistoricalMembership WITH (INDEX = IX_MyIndex) 

Gives the plan

With no sort but up the row and page count

/*Fake large table*/
UPDATE STATISTICS RuleInstanceHistoricalMembership 
                  WITH ROWCOUNT = 60000000, 
                       PAGECOUNT = 10000000 

And try again and you get

Now it has two sorts!

The scan on the NCI is in RuleInstanceId, Timestamp DESC order but then SQL Server reorders it into clustered index key order (Id ASC) per Optimizing I/O Performance by Sorting.

This step is to try and reduce the expected massive cost of 60 million random lookups into the clustered index. Then it gets sorted back into the original RuleInstanceId, Timestamp DESC order that the index delivered it in.