Jag stötte nyligen på ett liknande problem med MySQL i ett av mina produktionssystem.
Som en kommentator noterat ovan är problemet jokerteckensökningen i textfältet, och i synnerhet den inledande % i sökningen.
Vi sänkte den ledande procenten och minskade tidsåtgången för en sökfråga med flera storleksordningar (från en server som malde över 60 sekunder till "ingen tid alls").
Alternativ skulle vara att använda ett Full-Text-index eller ett system som Lucene för att söka.