Так устроен индекс. Он строится в первую очередь по первым символам и в последнюю по последним.
Если вы подменяете % начало, то индекс просто не будет работать.
Разделите ФИО на отдельные компоненты и сделайте отдельный индекс для имени, тогжа ваш кейс будет быстрее работать.
У вас же фактически происходит полный перебор базы без индекса.
Для примера. Вот у вас есть больой алфавитный список людей. Найти в нем любого человека по тому, по чему список отсортирован - это тривиальная задача. Вы делите весь спислк пополам и мгновенно определяете в какой половине искомая строка. Потом делите оставшуюс половину и так далее. А теперь представьте, что ваш список осортирован по фамилии, а вам надо найти в нем Сигизмунда. Всех Сигизмундов. Сортировка по фамилии вам не поможет быстро искать. Нужна сортировка по имени. Для этого и делают отдельные индексы.
