title: NOT IN implementation of Presto v.s Spark SQL
body: <p>I got a very simple query which shows significant performance difference when running on Spark SQL and Presto (3 hrs v.s 3 mins) in the same hardware. </p>
  
  <pre class="lang-sql prettyprint-override"><code>SELECT field 
  FROM test1 
  WHERE field NOT IN (SELECT field FROM test2)
  </code></pre>
  
  <p>After some research of the query plan, I found out the reason is how Spark SQL deals with <code>NOT IN</code> predicate subquery.
  To correctly handle the NULL of NOT IN, Spark SQL translate the <code>NOT IN</code> predicate as <code>Left AntiJoin( (test1=test2) OR isNULL(test1=test2))</code>.</p>
  
  <p>Spark SQL introduces <code>OR isNULL(test1=test2)</code> to ensure the correct semantics of <code>NOT IN</code>.</p>
  
  <p>However, the <code>OR</code> of Left AntiJoin join predicate causes the only feasible physical join strategy for <code>Left AntiJoin</code> is <code>BroadcastNestedLoopJoin</code>. For current stage, I could rewrite NOT IN to NOT EXISTS to workaround this issue. In the query plan of NOT EXISTS, I could see the the join predicate is <code>Left AntiJoin(test1=test2)</code> which causes a better physical join operator for NOT EXISTS (5 mins to finish).</p>
  
  <p>So far I am lucky since my dataset currently does not have any <code>NULL</code> attributes, but it may have in the future and the semantics of NOT IN is what I really want.</p>
  
  <p>So I check query plan of Presto, It does not really provides <code>Left AntiJoin</code> but it uses <code>SemiJoin</code> with a <code>FilterPredicate = not (expr)</code>. The query plan of Presto does not provide too much info like Spark.</p>
  
  <p>So my question is more like:</p>
  
  <p>Could I assume Presto has a better physical join operator to handle <code>NOT IN</code> operation? Not like Spark SQL, it does not rely on the rewrite of  join predicates <code>isnull(op1 = op2)</code> to ensure the correct semantics of NOT IN in the logical plan level.</p>