OK, l'ho testato su oltre 30.000 record per tabella e funziona molto velocemente.
Allo stato attuale, al momento stai eseguendo un join su due enormi tavoli, ma se esegui prima la scansione delle corrispondenze su "val" su ogni tavolo, ciò ridurrà sostanzialmente le dimensioni dei tuoi set di join.
Inizialmente ho pubblicato questa risposta come un insieme di sottoquery, ma non mi rendevo conto che MySQL è dolorosamente lento nelle sottoquery nidificate poiché viene eseguito dall'esterno verso l'interno. Tuttavia, se definisci le sottoquery come viste, le esegue dall'interno verso l'esterno.
Quindi, prima crea le viste.
CREATE VIEW tbl1_iii AS (
SELECT * FROM tbl1 WHERE val='iii'
);
CREATE VIEW tbl2_iii AS (
SELECT * FROM tbl2 WHERE val='iii'
);
Quindi esegui la query.
SELECT tbl1_iii.id from tbl1_iii,tbl2_iii
WHERE tbl1_iii.id = tbl2_iii.id;
Fulmine.
