Полнотекстовая индексация / поиск, если у вас есть символы подстановки.
Никакая нормальная индексация не поможет вам сделать это быстро, извините, с несколькими или отдельными столбцами с подстановочными знаками.
Ваш лучший наименьший наихудший шанс - иметь составной индекс по 3 столбцам и надеяться, что оптимизатор отсканирует это, скорее, сканирование таблицы, но, честно говоря, я сам не пробовал. И, вероятно, вы не можете, потому что общая ширина столбца индекса ключа должна быть менее 900 байт