J'ai récemment rencontré un problème similaire avec MySQL dans l'un de mes systèmes de production.
Comme un commentateur l'a noté ci-dessus, le problème est la recherche de caractères génériques sur le champ de texte, et en particulier le premier % dans la recherche.
Nous avons baissé le premier % et réduit le temps nécessaire pour une requête de recherche de plusieurs ordres de grandeur (d'un serveur broyant plus de 60 secondes à "pas de temps du tout").
Les alternatives seraient d'utiliser un index de texte intégral ou un système comme Lucene pour la recherche.
