NOT IN vs. NOT EXISTS performance

[Lincoln Swaine-Moore <lswainemoore@xxxxxxxxx>]

Hi all,

I've figured out how to solve the performance issues I've been encountering with a particular query, but I'm interested in better understanding the intuition behind why the better query is so much more performant.

The query in question involves a NOT IN filter from a CTE:

WITH temp as (
  SELECT temp_id
  FROM other_table
  WHERE ...
)
SELECT COUNT(*)

FROM main_table m

WHERE m.main_id NOT IN (SELECT temp_id from temp);

The query plan for (the non-masked version of) this query includes:

Filter: (NOT (SubPlan 1))

   Rows Removed by Filter: 1

   SubPlan 1

     ->  CTE Scan on temp  (cost=0.00..1950.60 rows=97530 width=418) (actual time=0.018..4.170 rows=15697 loops=100731)

My understanding is that PostgreSQL is not able to make this into a hashed Subplan because the expected number of rows * width of rows is too large for the work_mem setting, and so instead it has to do many repeated linear passes to find whether the various values of main_id are in the list of temp_ids.

The resolution to this problem was discovered via https://explainextended.com/2009/09/16/not-in-vs-not-exists-vs-left-join-is-null-postgresql/, and involves rewriting as so:

WITH temp as (
  SELECT temp_id
  FROM other_table
  WHERE ...
)
SELECT COUNT(*)

FROM main_table m 

WHERE NOT EXISTS (SELECT temp_id from temp where temp_id = m.main_id);

The query plan for this query (which I believe is equivalent to what it would be if I instead explicitly LEFT JOINed main_table to temp and used a WHERE to filter out NULL values of temp_id) does not involve a high number of loops like above:

->  Merge Anti Join  (cost=147305.45..149523.68 rows=192712 width=4) (actual time=5050.773..5622.266 rows=158850 loops=1)

   Merge Cond: (m.main_id = temp.temp_id)

   ->  Sort  (cost=115086.98..115637.10 rows=220050 width=19) (actual time=1290.829..1655.066 rows=199226 loops=1)

         Sort Key: m.main_id

         Sort Method: external merge  Disk: 5632kB

   ->  Materialize  (cost=32218.47..32764.37 rows=109180 width=418) (actual time=3759.936..3787.724 rows=38268 loops=1)

         ->  Sort  (cost=32218.47..32491.42 rows=109180 width=418) (actual time=3759.933..3771.117 rows=38268 loops=1)

               Sort Key: temp.temp_id

               Sort Method: quicksort  Memory: 3160kB

               ->  CTE Scan on temp  (cost=0.00..2183.60 rows=109180 width=418) (actual time=2316.745..3735.486 rows=38268 loops=1)

Instead it sorts using disk, and uses a MERGE ANTI JOIN, which I understand to eliminate the need for multiple passes through the table temp.

My primary question is: why is this approach only possible (for data too large for memory) when using NOT EXISTS, and not when using NOT IN? 

I understand that there is a slight difference in the meaning of the two expressions, in that NOT IN will produce NULL if there are any NULL values in the right hand side (in this case there are none, and the queries should return the same COUNT). But if anything, I would expect that to improve performance of the NOT IN operation, since a single pass through that data should reveal if there are any NULL values, at which point that information could be used to short-circuit. So I am a bit baffled.

Thanks very much for your help!

Best,
Lincoln

--
Lincoln Swaine-Moore