title: Postgres NOT IN performance
body: <p>Any ideas how to speed up this query?</p>
  
  <p>Input </p>
  
  <pre><code>EXPLAIN SELECT entityid FROM entity e
  
  LEFT JOIN level1entity l1 ON l1.level1id = e.level1_level1id
  LEFT JOIN level2entity l2 ON l2.level2id = l1.level2_level2id
  WHERE 
  
  l2.userid = 'a987c246-65e5-48f6-9d2d-a7bcb6284c8f' 
  AND 
  (entityid NOT IN 
  (1377776,1377792,1377793,1377794,1377795,1377796... 50000 ids)
  )
  </code></pre>
  
  <p>Output</p>
  
  <pre><code>Nested Loop  (cost=0.00..1452373.79 rows=3865 width=8)
    -&gt;  Nested Loop  (cost=0.00..8.58 rows=1 width=8)
          Join Filter: (l1.level2_level2id = l2.level2id)
          -&gt;  Seq Scan on level2entity l2  (cost=0.00..3.17 rows=1 width=8)
                Filter: ((userid)::text = 'a987c246-65e5-48f6-9d2d-a7bcb6284c8f'::text)
          -&gt;  Seq Scan on level1entity l1  (cost=0.00..4.07 rows=107 width=16)
    -&gt;  Index Scan using fk_fk18edb1cfb2a41235_idx on entity e  (cost=0.00..1452086.09 rows=22329 width=16)
          Index Cond: (level1_level1id = l1.level1id)
  </code></pre>
  
  <p>OK here a simplified version, the joins aren't the bottleneck</p>
  
  <pre><code>SELECT enitityid FROM 
  (SELECT enitityid FROM enitity e LIMIT 5000) a
  
  WHERE
  (enitityid NOT IN 
  (1377776,1377792,1377793,1377794,1377795, ... 50000 ids)
  )
  </code></pre>
  
  <p>the problem is to find the enties which don't have any of these ids</p>
  
  <p>EXPLAIN</p>
  
  <pre><code>Subquery Scan on a  (cost=0.00..312667.76 rows=1 width=8)
    Filter: (e.entityid &lt;&gt; ALL ('{1377776,1377792,1377793,1377794, ... 50000 ids}'::bigint[]))
    -&gt;  Limit  (cost=0.00..111.51 rows=5000 width=8)
          -&gt;  Seq Scan on entity e  (cost=0.00..29015.26 rows=1301026 width=8)
  </code></pre>