Saludos.
Puedes probar creando indices sobre los campos que mas consultas.
Cita: Los índices -como los índices de los libros- sirven para agilizar las consultas a las tablas, evitando que mysql tenga que revisar todos los datos disponibles para devolver el resultado.
Hasta Pronto!!!