Наскоро се сблъсках с подобен проблем с MySQL в една от моите производствени системи.
Както коментира по-горе, проблемът е търсенето на заместващи знаци в текстовото поле и по-специално водещия % в търсенето.
Премахнахме водещия % и намалихме времето, необходимо за заявка за търсене с няколко порядъка (от сървър, който шлайфаше 60 секунди+ до „без време“).
Алтернативи биха били използването на пълнотекстов индекс или система като Lucene за търсене.
