Если ваш поисковый запрос начинается с символа %, то индекс не будет использоваться эффективно. В таком случае рекомендуется использовать полнотекстовый индекс и соответствующий запрос. Также можно использовать сторонние поисковые движки, например, Elasticsearch или Sphinx. Если вы не хотите использовать другие поисковые движки, то рекомендуется перенести ваш сайт с текущего хостинга на более мощный сервер, так как время выполнения запроса в 10 секунд на обработку нескольких сотен тысяч строк является очень большим.