Qué campo debería indexar?

[jurena]

Una pregunta: ¿por qué usas regexp? Al parecer las expresiones regulares no hacen uso de los índices. Yo te diría que antes que nada, si puedes hacer esas búsquedas con LIKE o =, la hagas así y, como te ha dicho Genetix, indexes esos campos que busques con el where...
Y por otra parte tal vez la búsqueda la tendrás que hacer tras el group by y usando having...
Mira a ver si es algo de eso.