Holas derkenuke, creo que se olvidaron mencionar un concepto importante y es el uso de indices, aqui les dejo algo extractado del manual de mysql:
Cita: The larger the table, the more this costs. If the table has an index for the columns in question, MySQL can quickly determine the position to seek to in the middle of the data file without having to look at all the data. If a table has 1,000 rows, then this is at least 100 times faster than reading sequentially
el crear una llave primaria o foranea no es la solución adecuada desde mi punto de vista, para eso se crearon los indices que se encargan de mejorar los tiempos de respuesta de los SELECTS, lo que tendrias que hacer es ver si necesitas crear un indice combinado para ambas columnas o un indice para cada una de ellas, puedes consultar mas la documentacion de mysql para conocer mas sobre el uso de indices, saludos, cya
http://dev.mysql.com/doc/refman/5.0/es/indexes.html