Manejar con php una base de datos grandisima

[mafima]

Gracias jurena,
El problema es que antes tenia tambien la tablas paises como dices ( eso si no le habia puesdo Clave foranea) y cuando lo tenia asi entonces andaba mas lento.
Me toco pasar la tabla de los paises a un archivo y meter todo dentro de un array poniendo como INDICE del array el ID del pais.

Es sumamente extraño, y ya que mensionas que el problema puede estar tambien en la programación, quizas tengas experiencia en como optimizar a travez del codigo.

Espero más comentarios que me ayuden con este problema, muchas gracias a todos.
PD: uso PHP para programar.