Jeg stødte for nylig på et lignende problem med MySQL i et af mine produktionssystemer.
Som en kommentator nævnt ovenfor, er problemet jokertegnssøgningen i tekstfeltet, og især den førende % i søgningen.
Vi sænkede den førende % og reducerede tidsforbruget for en søgeforespørgsel med flere størrelsesordener (fra en server, der kværner 60 sekunder+ til "ingen tid overhovedet").
Alternativer ville være at bruge et fuldtekstindeks eller et system som Lucene til søgning.