Hola
Tienes que optimizar tus consultas.
- Evita usar (*) (a no ser que desees recuperar todos los registros), trata de colocar los nombres de los campos que desees recuperar
- Todos los campos que están dentro de Where son candidatas a ser indices
- Usa la sentencia Explain, te ayudará a optimizar mejor tus consultas
Aquí puedes encontrar mayores referencias
http://dev.mysql.com/doc/refman/5.0/es/query-speed.html
saludos!