Поиск строки, какую СУБД выбрать для решения задачи?

Доброй ночи!

Есть входной параметр в виде строки, допустим: "Привет, есть ли у тебя ручка?"
Для этой строки нужно найти "шаблон", который бы максимально "подходил" к ней. Пример найденой записи: "При*есть*ручка".

Сейчас это реализовывается с помощью Redis, но генерируется очень много запросов к нему, хотелось бы как-то этот вопрос решить малой кровью.. (строк "шаблонов" не так мало, в данный момент их кололо 5 тысяч, дальше - больше)

RDMS не подходят т.к. посылается очень много запросов и кэширование тут не поможет т.к. большинство входных строк уникальны. Вероятно с redis это как-то можно решить. Спасибо!

Обновление:
нужно, что бы алгоритм работал обратным образом от redis.keys.

Supported glob-style patterns:
h?llo matches hello, hallo and hxllo
h*llo matches hllo and heeeello
h[ae]llo matches hello and hallo, but not hillo
h[^e]llo matches hallo, hbllo, ... but not hello
h[a-b]llo matches hallo and hbllo

Т.е. нужно, что бы по параметру в виде строки - "hello", нашлись записи: "h?llo", "h*llo"