LIKE осуществляет лишь простейший поиск с использованием двух символов замены: % - для любого количества символов и _ для замены одного симовола, REGEXP или RLIKE поддерживает поиск по регулярному выражению.
Можно следовать двумя путями,
1) либо воспользоваться полнотекстовым поиском по полям типа TEXT проиндексированных индексом FULLTEXT
2) либо отталкиваться от операторов LIKE и REGEXP
Вот как мне кажется наиболее интересные темы по поиску: