Я бы рекомендовал использовать SQL Management Studio для проверки наилучшего использования индекса. Это очень помогает. Во-первых, я бы поставил дату в первую позицию, так как она наиболее часто используется (даже если она ничего не меняет в этом случае).
Во-вторых, если бы вы могли выполнить порядок в коде позади, я бы рекомендовал это. В любой момент закажите результат в коде (Java, C# ...). Я буду намного быстрее, и вы сможете лучше использовать свои индексы, поскольку вам не понадобится индекс на Date.
В-третьих, если вы не можете сделать заказ в коде Java или C# иногда лучше создать свой выбор без порядка, поместить результат во временную таблицу с индексом по дате, а затем выбрать из этой временной таблицы с порядком. Вы должны посмотреть на план выполнения, чтобы увидеть, какой из них лучше.
Затем вы также можете попробовать использовать включенные индексы вместо индексов с несколькими столбцами. Что-то вроде:
CREATE NONCLUSTERED INDEX IX_MYINDEX
ON T(Date)
INCLUDED (FieldA, FieldB)
Надеюсь, это поможет. Если возможно, опубликуйте свой план выполнения, чтобы мы могли увидеть, что не так.