Recentemente, encontrei um problema semelhante com o MySQL em um dos meus sistemas de produção.

Como um comentarista observou acima, o problema é a pesquisa de curinga no campo de texto e, em particular, o % inicial na pesquisa.

Reduzimos a % principal e reduzimos o tempo gasto para uma consulta de pesquisa em várias ordens de magnitude (de um servidor processando mais de 60 segundos para "nenhum tempo").

Alternativas seriam usar um índice de texto completo ou um sistema como o Lucene para pesquisa.