Ответ кроется в том, как именно происходит поиск в строках? сравнение, подстрока like, полнотекстовый индекс. Что ищется… случайная строка или ключевое слово (подстроки, заранее определенные и редко изменяемые, максимум дополняемые). Так же очень важно каких запросов больше и на сколько (изменения, добавления, удаления, чтение или поиск).
А дальше, в зависимости от ответов, можно заменить тестовые поля на группу строго типизированных полей (в т.ч. и сложную структуру таблиц), можно поверх имеющейся базы настроить 'индекс из своих полей' (кстати это может позволить убрать индекс БД, что может в некоторых случаях ускорить запись) и т.п.