Why is my SQL Server ORDER BY slow despite the ordered column being indexed?

Indexing a column doesn't help make the sort faster.

If you want to make your query a lot faster, then reverse the order of your tables. Specifically, list table country first in your joined tables.

The reason why this helps is that the where clause can filter rows from the first table instead of having to make all those joins, then filtering the rows.

If your query does not contain an order by then it will return the data in whatever oreder it was found. There is no guarantee that the data will even be returned in the same order when you run the query again.

When you include an order by clause, the dabatase has to build a list of the rows in the correct order and then return the data in that order. This can take a lot of extra processing which translates into extra time.

It probably takes longer to sort a large number of columns, which your query might be returning. At some point you will run out of buffer space and the database will have to start swapping and perfromance will go downhill.

Try returning less columns (specify the columns you need instead of Select *) and see if the query runs faster.

Because your query projects all the columns (*), it needs 5 columns for the join conditions and has an unselective WHERE clause on what is likely a joined table column, it causes it to hit the Index Tipping Point: the optimizer decides that it is less costly to scan the entire table, filter it and sort it that it would be to range scan the index and then lookup each key in the table to retrieve the needed extra columns (the 5 for the joins and the rest for the *).

A better index to partially cover this query could be:

CREATE INDEX ... ON .. (countryId, startDatetime);

Jeffrey's suggestion to make the clustered index would cover the query 100% and would definitely improve performance, but changing the clustered index has many side effects. I would start with a non-clustered index as above. Unless they are needed by other queries, you can drop all the other non-clustered indexes you created, they won't help this query.

You should try below code also

Insert the records into temporary table Without using the Order by clause

SELECT * into #temp FROM [mydb].[dbo].[employees]
JOIN [mydb].[dbo].[industry]
  ON jobs.industryId = industry.id
JOIN [mydb].[dbo].[state]
  ON jobs.stateId = state.id
JOIN [mydb].[dbo].[positionType]
  ON jobs.positionTypeId = positionType.id
JOIN [mydb].[dbo].[payPer]
  ON jobs.salaryPerId = payPer.id
JOIN [mydb].[dbo].[country]
  ON jobs.countryId = country.id
WHERE countryName = 'US'

Now run the statement using Order By Clause

Select * from #temp ORDER BY startDatetime