Execution plan contains a 'sort' even though the data is sorted in index I have a table which has a clustered index as below:

CREATE CLUSTERED INDEX [IX_MachineryId_DateRecorded]
ON Machinery (MachineryId, DateRecorded)


I'm selecting based on the fields in the clustered index, plus one more:

SELECT DateRecorded, Latitude, Longitude
FROM MachineryReading
WHERE MachineryId = 2127        -- First key in the index
AND DateRecorded &gt; '2017-01-10' -- Second key in the index
AND DateRecorded &lt; '2017-10-16' -- Second key in the index
AND FixStatus &gt;= 2              -- Not a key, resulting in a scan
ORDER BY DateRecorded


I would have expected this to result in a simple clustered index scan. However, looking at the live query statistics, and the actual execution plan, the majority of the query's execution time comes from sorting the results after the index scan. Why is the ordered data being sorted again?

https://www.brentozar.com/pastetheplan/?id=S10DvjZpb
Your query accesses 10 partitions and you are searching a 10 month range so my guess would be that it is partitioned on month of DateRecorded.

I can reproduce your plan with the sort with the below.

CREATE PARTITION FUNCTION pf1 (DATE) AS RANGE RIGHT FOR VALUES ( 
'2017-01-01', 
'2017-02-01', 
'2017-03-01', 
'2017-04-01', 
'2017-05-01', 
'2017-06-01', 
'2017-07-01', 
'2017-08-01', 
'2017-09-01', 
'2017-10-01', 
'2017-11-01' );

CREATE PARTITION SCHEME ps1 AS PARTITION pf1 ALL TO ([Primary]);

CREATE TABLE MachineryReading
  (
     MachineryId  INT,
     DateRecorded DATE,
     Latitude     FLOAT,
     Longitude    FLOAT,
     FixStatus    INT
  )
ON ps1(DateRecorded)

CREATE CLUSTERED INDEX [IX_MachineryId_DateRecorded]
  ON MachineryReading (MachineryId, DateRecorded)


but technically a sort could be avoided if you could get a plan that processed the partitions in order and just concatenated one ordered result to the next. 

If you are happy to assume that the partition numbers will be in order of value (I don't know if this is actually guaranteed but it seems to be the case even after partition splits) then adding a leading column to the sort of the partition number achieves this

SELECT DateRecorded,
       Latitude,
       Longitude
FROM   MachineryReading
WHERE  MachineryId = 2127 
       AND DateRecorded &gt; '2017-01-10' 
       AND DateRecorded &lt; '2017-10-16' 
       AND FixStatus &gt;= 2 
ORDER  BY $PARTITION.pf1(DateRecorded),
          MachineryId, --Not really needed as this is a constant 2127
          DateRecorded