Однозначно, надо создать индексы по вторичным ключам во всех таблицах (на всякий случай напомню, что вторичный ключ — это поле, которое используется в JOIN), а также индекс по last_vacation_time в таблице employee — без этих индексов оптимизировать попросту нечего. Также поможет индекс по тем полям, по которым происходит выборка.
Для начала стоит попробовать убрать AND из условия на JOIN и перенести его в блок WHERE — смысл один, но оптимизатор MySQL никогда не отличался умом и сообразительностью.
Еще стоит попробовать использовать одну ENGINE для всех таблиц.
В качестве последнего средства лично я бы стал играться с порядком JOINов. Я НЕ знаю, влияет ли этот порядок на план запроса в MySQL, но что-то нехорошее слышал. Возможно, в последней версии эту особенность починили.
— Кстати, по поводу схемы данных. Я бы сделал словарь типов (имен) меток, чтобы не дублировать строковую информацию. И отпуски хранил бы все в отдельной таблице, а не только последний. Но сначала, конечно же, надо научиться строить быстрые запросы.