Re: NOT IN subquery optimization

Folks - I was away on vacation for the month of February, and can give this
my attention again.

I agree with Tom's comment above - when the cost of the NOT IN is dominated
by the cost of the outer scan (i.e. when the cardinality of the outer
relation is large relative to the cardinality of the subquery), and if the
inner cardinality is small enough to fit in memory, then the current
implementation does an efficient hash lookup into an in-memory structure,
and that's a very fast way to do the NOT IN. It almost achieves the
lower-bound cost of scanning the outer relation. It can also parallelizes
easily, whether or not we currently can do that. In these cases, the
current plan is the preferred plan, and we should keep it.

preferred in-memory hash lookup plan: https://explain.depesz.com/s/I1kN

This is a case that we would want to avoid the transform, because when both
the inner and outer are nullable and the outer is large and the inner is
small, the transformed plan would Scan and Materialize the inner for each
row of the outer row, which is very slow compared to the untransformed plan:

slow case for the transformation: https://explain.depesz.com/s/0CBB

However, if the inner is too large to fit into memory, then the transformed
plan is faster on all of our other test cases, although our test cases are
far from complete. If the current solution supports parallel scan of the
outer, for example, then PQ could have lower elapsed time than the non-PQ
nested loop solution.

Also, remember that the issue with the empty inner was just a bug that was
the result of trying to do an additional optimization in the case where
there is no WHERE clause in the subquery. That bug has been fixed. The
general case transformation described in the base note produces the correct
result in all cases, including the empty subquery case.

-----
Jim Finnerty, AWS, Amazon Aurora PostgreSQL
--
Sent from: http://www.postgresql-archive.org/PostgreSQL-hackers-f1928748.html