Нормализация и борьба с «using temporary; using filesort»
Однозначно, надо создать индексы по вторичным ключам во всех таблицах (на всякий случай напомню, что вторичный ключ — это поле, которое используется в JOIN), а также индекс по last_vacation_time в таблице employee — без этих индексов оптимизировать попросту нечего. Также поможет индекс по тем полям, по которым происходит выборка.

Для начала стоит попробовать убрать AND из условия на JOIN и перенести его в блок WHERE — смысл один, но оптимизатор MySQL никогда не отличался умом и сообразительностью.

Еще стоит попробовать использовать одну ENGINE для всех таблиц.

В качестве последнего средства лично я бы стал играться с порядком JOINов. Я НЕ знаю, влияет ли этот порядок на план запроса в MySQL, но что-то нехорошее слышал. Возможно, в последней версии эту особенность починили.

 — Кстати, по поводу схемы данных. Я бы сделал словарь типов (имен) меток, чтобы не дублировать строковую информацию. И отпуски хранил бы все в отдельной таблице, а не только последний. Но сначала, конечно же, надо научиться строить быстрые запросы.
filesort у вас потому что вы есть «ORDER BY e.last_vacation_time» и нет ключа по этому полю. Тот ключ, что есть («deleted») не подошел оптимизатору видимо по той причине что last_vacation_time не на первом месте.

Попробуйте сделать ключ с «last_vacation_time» и убедитесь что он используется. При разных наборах данных оптимизатор mysql вполне может выбирать разные ключи. На таком количестве записей как у вас вы не получите реальной картины по производительности.