Query with a UNION sub-query takes a very long time

Question

I've been having an odd problem with some queries that depend on a sub query. They run lightning fast, until I use a UNION statement in the sub query. Then they run endlessly, I've given after 10 minutes. The scenario I'm describing now isn't the original one I started with, but I think it cuts out a lot of possible problems yet yields the same problem. So even though it's a pointless query, bear with me!

I have a table:

tblUser - 100,000 rows
tblFavourites - 200,000 rows

If I execute:

SELECT COUNT(*) 
FROM tblFavourites 
WHERE userID NOT IN (SELECT uid FROM tblUser);  

… then it runs in under a second. However, if I modify it so that the sub query has a UNION, it will run for at least 10 minutes (before I give up!)

SELECT COUNT(*) 
FROM tblFavourites 
WHERE userID NOT IN (SELECT uid FROM tblUser UNION SELECT uid FROM tblUser);  

A pointless change, but it should yield the same result and I don't see why it should take any longer?

Putting the sub-query into a view and calling that instead has the same effect.

Any ideas why this would be? I'm using SQL Azure.

---

Problem solved. See my answer below.

---

Answer 1

UNION generate unique values, so the DBMS engine makes sorts. You can use safely UNION ALL in this case.