MySQL-t sajnos hál' Istennek sosem kellett élesben használnom, de amik dialektustól függetlenül eszembe jutnak (csak a helyes eredményt mutató query-t megnézve):
1) Én megpróbálnám, hogy nem az egész táblával JOIN-olok, hanem egy subquery-vel, ami eleve csak azokat tölti be a két segédtáblából, amire szükség van
2) Ha van ráhatásod a DB struktúrára, akkor megfontolhatod a DB-t denormalizálva a current_title és current_salary mezőket letárolni az employee táblában. (Ofc erről az adatbázis kliensnek is tudnia kell, vagy DB oldalon csinálod meg, hogy ott legyen a cache)
3) from_date ha nincs indexelve, az is megér egy próbát
Imho itt a bottleneck az egyes pont: a hárommillió soros tábla minden soránál kétszer nyálazod végig mindkét segédtáblát ahelyett, hogy egyszer csinálnád meg a segédtáblás lekérdezést (emp_no, title, MAX(from_date)), és onnan szednéd ki, ami kell.
szerk: aztán persze ki tudja, nálam eddig kb. 70% T-SQL, 29% PL/SQL, 1% egyéb :)