No, una búsqueda de expresión regular no puede usar un índice. Si lo que está aplicando la expresión regular es un índice, podría ir un poco más rápido, pero básicamente está escaneando una tabla.
La única solución que conozco es usar LIKE 'foo%' en lugar de RLIKE 'foo.*' si esa es tu expresión regular. Un índice en dicha columna puede usar LIKE pero no RLIKE
