OK, eu testei isso em mais de 30.000 registros por tabela e ele é executado muito rápido.
Atualmente, você está realizando uma junção em duas tabelas enormes, mas se você procurar por correspondências em 'val' em cada tabela primeiro, isso reduzirá substancialmente o tamanho de seus conjuntos de junção.
Originalmente postei esta resposta como um conjunto de subconsultas, mas não percebi que o MySQL é dolorosamente lento em subconsultas aninhadas, pois executa de fora para dentro. No entanto, se você definir as subconsultas como visualizações, ele as executa de dentro para fora.
Então, primeiro crie as visualizações.
CREATE VIEW tbl1_iii AS (
SELECT * FROM tbl1 WHERE val='iii'
);
CREATE VIEW tbl2_iii AS (
SELECT * FROM tbl2 WHERE val='iii'
);
Em seguida, execute a consulta.
SELECT tbl1_iii.id from tbl1_iii,tbl2_iii
WHERE tbl1_iii.id = tbl2_iii.id;
Relâmpago.
