MySQL indicizza automaticamente le colonne della chiave esterna?

Sì, ma solo su innodb . Innodb è attualmente l'unico formato di tabella distribuito con chiavi esterne implementate.