Быстрый(er)метод поиска по шаблону в более чем 250 тыс. строк

У меня есть английский словарь в базе данных MySQL с немногим более 250 тысячами записей, и я использую простой ruby ​​front-end для поиска по нему, используя подстановочные знаки в начале струны. До сих пор я делал это так:

SELECT * FROM words WHERE word LIKE '_e__o'

или даже

SELECT * FROM words WHERE word LIKE '____s'

. Я всегда знаю точную длину слова, но все символы, кроме одного, потенциально неизвестны.

Это медленнее, чем меласса, примерно в пятнадцать раз медленнее, чем аналогичный запрос без начального подстановочного знака, потому что нельзя использовать индекс для столбца.

Я попробовал несколько методов, чтобы сузить область поиска. Например, я добавил 26 дополнительных столбцов, содержащих индивидуальное количество букв в каждом слове, и сузил поиск, используя их в первую очередь. Я также пробовал сужать по длине слова. Эти методы почти ничего не изменили из-за присущей им неэффективности ведущего-поиска с подстановочными знаками. Я экспериментировал с оператором REGEXP, который еще медленнее.

SQLite и PostgreSQL столь же ограничены, как и MySQL, и хотя у меня ограниченный опыт работы с системами NoSQL, мои исследования создают впечатление, что они превосходят в масштабируемости, а не в производительности, которая мне нужна.

Тогда мой вопрос: где мне искать решение? Должен ли я продолжать поиск способа оптимизации моих запросов или добавления дополнительных столбцов, которые могут сузить мой потенциальный набор записей? Существуют ли системы, разработанные специально для быстрого поиска по подстановочным знакам в этом ключе?