¿Cuál es una buena manera de agregar una CLAVE PRIMARIA a una tabla InnoDB grande?

Tengo una tabla con alrededor de 30 millones de filas en MySQL 5.5 usando el motor de almacenamiento InnoDB. Esta tabla tiene una clave externa que se vincula a otra tabla con alrededor de 3 millones de filas. Quiero agregar una clave principal a la tabla más grande, pero no estoy seguro de cuál...