Cita: Cuando quieres sacar el nombre del usuario, el pais y la provincia...¿ Es preferible gastar recursos en hacer siempre una consulta a 3 tablas? o ¿una consulta a una tabla pero sacrificando espacio en la tabla usuario?
Si pones un varchar con el nombre te arriesgas a perder consistencia de datos. Es precisamente para condervarla y asegurarla que esos valores no se incluyen como VARCHAR sino como FK hacia otra tabla.
La pérdida de performance que puedes tener por usar tres tablas es ínfima, y sólo llega a tener algún impacto cuando estás hablando de millones de registros.
Por otro lado, las búsquedas hechas con campos numéricos, como sería el caso de las PK de Provincia y Pais, son siempre mucho más rápidas que con campos VARCHAR, porque en un caso se trata de matching binario y en el otro tienes que ver su valor como byte, más las collation, charset, longitudes de clave, etc.
Resumen: Usa tres tablas y eventualmente puedes usar tablas TEMPORARY para acelerar algunos prefiltrados.