MySQL - Query tarda demasiado

TEngo una query que hasta ahora venía tardando 3-5 minutos. Desde hace unos meses ha habido un incremento del numero de registros extraidos por la query de un 15%, pero el tiempo que tarda ha pasado a ser de 40 minutos o mas. Entiendo que el problema no es de la query, no se si puede ser por algún parametro de mysql o del servidor Unix en el que está alojada la BBDD.

¿Alguien me puede ayudar o dar alguna idea sobre esta hipótesis?