Si las tablas son MyISAM, los campos no son realmente FK. Al menos no son
veraderas FK, sino que las administras por programación.
Las tablas MyISAM no poseen restricciones de foreign key, por lo que podría perfectamente haber datos sucios, si se produjo en algún momento un error de procesos (nada raro, por cierto).
La diferencia entre una y otra cosa es notable, porque las InnoDB, al definir una FK
crean un índice real sobre ambos campos, y por consecuencia en las consultas ese índice tiene incidencia en la optimización del parser.
En definitiva, el primer problema a resolver es que tienes que indexar esos campos, es decir, debes al menos contruir un índice sobre cada uno de ellos.
Cita: el phpmyadmin explota cada vez que quiero reindexarlos
Bueno, phpMyadmin
no es MySQL, sino una interfaz programada en PHP, para acceder de modo amigable a MySQL. Puede tener y tiene errores de diseño, aunque no sean errores de programación.
La mejor solución en ese caso es indexarlos por fuera del phpMyadmin, muy probablemente usando la consola propia de MySQL, o bien una herramienta realmente buena, como MySQL Workbench, por ejemplo.
Pero insisto en una cosa: No has probado el EXPLAIN.
¿Entiendes a qué me refiero cuando lo menciono?