Сначала попробуйте использовать двоичное сопоставление, что будет означать, что сложные правила Unicode заменяются простым сравнением байтов.
SELECT COUNT(*)
FROM MyTable
WHERE MyColumn COLLATE Latin1_General_BIN2 LIKE '%some string%'
Также посмотрите главу под названием «Построить свой собственный индекс» в SQL Server MVP Deep Dives , написанный Эрландом Соммарскогом
Основная идея заключается в том, что вы вводите ограничение для пользователя и требует, чтобы строка была длиной не менее трех смежных символов.Затем вы извлекаете все три последовательности букв из поля MyColumn и сохраняете эти фрагменты в таблице вместе с MyTable.id, к которому они принадлежат.При поиске строки вы также разбиваете ее на три буквенных фрагмента и смотрите, к какому идентификатору записи они принадлежат.Таким образом, вы найдете подходящие строки намного быстрее.Это стратегия в двух словах.
В книге описываются детали реализации и способы дальнейшей оптимизации.