>Well, what does execution plan show? You have indexes in the Table2 and TableStatus on the foreign key, right?

The execution plan recognizes I have an index on the temporary table. That, however, did not improve performance. The rest of the execution is as before. So, it shows an Index seek instead of a scan. The image of the execution plan is attached. In my example, I had to change the real table names to preserve the confidentiality. So, I had to adjust the execution plan as well.

Yes, I have an index on all keys.

>You can re-write the last query as

The T and Tmp aliases did not change anything, except the fact that the query now takes 3 minutes and 18 seconds instead of 2.

>Also, how often do you re-build statistics and with full scan in your tables?

Never

>You may also try adding OPTION (RECOMPILE) to your last query and see if the performance improves.

If I could know in advance if the number of WHERE IN keys would be too much, I could alternate between two methods. That one worked pretty well except that it has limitations. The use of a temporary table resolves that limitation but brings another factor as SQL Server has to perform a join and this brings down several queries.