Если речь о том, как решить это в рамках SQL, то смотри JOIN. Ну и, в принципе, если у тебя только две эти сущности, то, я предполагаю, что тебе и не нужна нормальная форма (смотри денормализация)
InnoDB создано для реляционных связей между таблицами (primary / foreign keys), работает намного медленнее, чем MyISAM именно по этой причине. Конечно, ощутимо с таким количеством данных.
