title: Performance of "NOT IN" in SQL query
body: <p>I'm quite new to SQL query analysis. Recently I stumbled upon a performance issue with one of the queries and I'm wondering whether my thought process is correct here and why Query Optimizer works the way it works in this case. 
  I'm om SQL Server 2012.
  I've got a SQL query that looks like</p>
  
  <pre><code>SELECT * FROM T1 
  WHERE Id NOT IN 
  (SELECT DISTINCT T1_Id from T2);
  </code></pre>
  
  <p>It takes around 30 seconds to run on my test server.
  While trying to understand what is taking so long I rewrote it using a temp table, like this:</p>
  
  <pre><code>SELECT DISTINCT T1_Id 
  INTO #temp from T2;
  SELECT * FROM T1 
  WHERE Id NOT IN  
  (SELECT T1_Id from #temp);
  </code></pre>
  
  <p>It runs a hundred times faster than the first one.</p>
  
  <p>Some info about the tables: 
  T2 has around 1 million rows, and there are around 1000 distinct values of T1_id there. T1 has around 1000+ rows. Initially I only had a clustered index on T2 on a column other than T1_Id, so T1_id wasn't indexed at all.</p>
  
  <p>Looking at the execution plans, I saw that for the first query there were as many index scans as there are distinct T1_id values, so basically SQL Server performs about 1000 index scans in this case. 
  That made me realize that adding a non-clustered index on T1_id may be a good idea (the index should've been there from the start, admittedly), and adding an index indeed made the original query run much faster since now it does nonclustered index seeks.</p>
  
  <p>What I'm looking for is to understand the Query optimizer behavior for the original query - does it look reasonable? Are there any ways to make it work in a way similar to the temporary table variant that I posted here rather than doing multiple scans? Am I just misunderstanding something here? 
  Thanks in advance for any links to the similar discussion as I haven't really found anything useful. </p>