Modificând puţin semnificaţia query-ului, ai putea să scrii:

Select b.ExternalCode, a.*, c.CodStare

from tbl1 a,

(select ExternalCode, MessageCode from tbl2 union select ExternalCode, MessageCode from tbl2_hist) b,

tbl3 c

where DataExecutiei = @Data

and a.CodMesajOut = b.MessageCode

and c.CodMesajOut = a.CodMesajOut

and c.CodStare = 32

and a.CodMesaj = 8

Order by a.CodMesaj

Sau chiar:

Select b.ExternalCode, a.*, c.CodStare

from tbl1 a,

(select ExternalCode, MessageCode from tbl2 union all select ExternalCode, MessageCode from tbl2_hist) b,

tbl3 c

where DataExecutiei = @Data

and a.CodMesajOut = b.MessageCode

and c.CodMesajOut = a.CodMesajOut

and c.CodStare = 32

and a.CodMesaj = 8

Order by a.CodMesaj

Apoi poţi să elimini ORDER BY-ul, dacă ai o singură valoare pentru a.CodMesaj.

Poţi să încerci să mai creezi nişte indecşi (dacă nu există):

CREATE INDEX ix1 ON tbl1 (CodMesaj, CodMesajOut)
CREATE INDEX ix2 ON tbl3 (CodStare, CodMesajOut)

Totuşi, nu mi-e clar din care tabelă vine coloana DataExecutiei.

Răzvan