Again - Count(*) is overkill for a scenario like that. You don't care how many there are, you just want to know there are some matching records.
So instead of
select * from table1
where (select count(*) from table2 where table1.field1=table2.val1 and table1.field2=table2.val2) >0
Try using this (which usually runs faster)
select * from table1
where EXISTS (select top1 *from table2 where table1.field1=table2.val1 and table1.field2=table2.val2)
But still - this would run a LOT faster if you simply asked the owner of said DB to add in the index you need. Is this a vendor DB or something that prevents you from even asking?
----------------------------------------------------------------------------------
Your lack of planning does not constitute an emergency on my part...unless you're my manager...or a director and above...or a really loud-spoken end-user..All right - what was my emergency again?