El consejo de Quimfv sigue siendo la mejor opción considerando que los índices FULLTEXT operan en base a relevancia:
Cita: La función MATCH() realiza una búsqueda de lenguaje natural para cadenas contra una colección de textos. Una colección es un conjunto de una o más columnas incluídas en un índice FULLTEXT . La cadena de búsqueda se da como argumento para AGAINST(). Para cada registro en la tabla MATCH() retorna un valor de relevancia, esto es, una medida de similaridad entre la cadena de búsqueda y el texto en el registro en las columnas mencionadas en la lista MATCH().
[...]
Cuando se usa MATCH() en una cláusula WHERE , como en el ejemplo precedente, los registros retornados se ordenan automáticamente con la relevancia mayor primero. Los valores relevantes son números en coma flotante no negativos. Relevancia cero significa que no tiene similaridad. La relevancia se computa basada en el número de palabras en el registro, el número de palabras únicas en este registro, el número total de palabras en la colección, y el número de documentos (registros) que contienen una palabra particulas.
El único inconveniente es que MATCH()... AGAINST no opera con cadenas parciales. Sólo con palabras completas, por lo cual no se pueden usar expresiones regulares o comodines. Pero resulta mucho mejor que otras soluciones posibles, para tu caso.