Извините, я отвечаю на это сам. Спасибо Артуру за ссылки, они были полезны (поэтому я проголосовал за твой ответ). Мы обновили статистику, но это не помогло. Мы проверили дефрагментацию с помощью DBCC SHOWCONTIG, но она не сильно отличалась от других баз данных.
Прошу прощения, что не опубликовал запрос AdaTheDev, но мне пришлось бы изменить все столбцы и прочее (потому что это довольно критично для бизнеса), и мы нашли решение сейчас.
Мы заметили, что в таблице было гораздо больше записей, чем в других базах данных. Мы добавили индексы на правильные столбцы. Мы сделали соединение как:
inner join table2 t2 on t1.t1Id = t2.t1Id and t2.someOtherId = @parameter
where t2.aThirdId = @otherParameter
Таким образом, мы добавили три отдельных индекса для каждого столбца Id, что ускорило его от 30 до 3-5 секунд (хотя у нас был индекс для t1Id и someOtherId вместе).
В конце мы также выполнили очистку таблицы, потому что многие записи были логически удалены и больше не нужны. Но индексы сделали свое дело.