ORDER BY performance impact I am using SQL Server 2012. We have a table that specifies the incoming requests to be processed. Some of the columns are (total columns are 10),

requestId
requestStatus (Enum - Processed, NotProcessed, Failed, etc)
requestedTime
requestCompletionTime


The query to pick the new requests is

select top 10000 
from RequestProcessingTable 
where requestStatus = 'NotProcessed' 
order by requestId


The total number of rows in this table is 300 million.

We have 2 indexes, one clustered (requestId - primary key of this table) and one non-clustered (requestStatus).

Since we want to process the requests based on the requestId we need to do the order by. When we introduce the order by it is taking 3 times more time to select. Is there a best way to create indexes or do it in a different approach so that the performance of the SQL query can be improved.

Thanks a lot for your help in advance.
Create a filtered index on requestId with the predicate where requestStatus = 'NotProcessed'. The optimiser is likely to favour this as long as the query conditions exactly match the index definition.

It may help to use a small tinyint for the status instead of a longer character string. There will be more rows per data page and less IO.