pgsql: Use a hash table to speed up NOT IN(values)

Use a hash table to speed up NOT IN(values)

Similar to 50e17ad28, which allowed hash tables to be used for IN clauses
with a set of constants, here we add the same feature for NOT IN clauses.

NOT IN evaluates the same as: WHERE a <> v1 AND a <> v2 AND a <> v3.
Obviously, if we're using a hash table we must be exactly equivalent to
that and return the same result taking into account that either side of
the condition could contain a NULL. This requires a little bit of
special handling to make work with the hash table version.

When processing NOT IN, the ScalarArrayOpExpr's operator will be the <>
operator. To be able to build and lookup a hash table we must use the
<>'s negator operator. The planner checks if that exists and is hashable
and sets the relevant fields in ScalarArrayOpExpr to instruct the executor
to use hashing.

Author: David Rowley, James Coleman
Reviewed-by: James Coleman, Zhihong Yu
Discussion: https://postgr.es/m/CAApHDvoF1mum_FRk6D621edcB6KSHBi2+GAgWmioj5AhOu2vwQ@mail.gmail.com

Branch
------
master

Details
-------
https://git.postgresql.org/pg/commitdiff/29f45e299e7ffa1df0db44b8452228625479487f

Modified Files
--------------
src/backend/executor/execExpr.c | 24 +++++++--
src/backend/executor/execExprInterp.c | 17 ++++++-
src/backend/nodes/copyfuncs.c | 1 +
src/backend/nodes/equalfuncs.c | 6 +++
src/backend/nodes/outfuncs.c | 1 +
src/backend/nodes/readfuncs.c | 1 +
src/backend/optimizer/plan/setrefs.c | 3 ++
src/backend/optimizer/prep/prepqual.c | 1 +
src/backend/optimizer/util/clauses.c | 76 ++++++++++++++++++++++------
src/backend/parser/parse_oper.c | 1 +
src/backend/partitioning/partbounds.c | 1 +
src/include/catalog/catversion.h | 2 +-
src/include/executor/execExpr.h | 1 +
src/include/nodes/primnodes.h | 18 +++++--
src/test/regress/expected/expressions.out | 84 +++++++++++++++++++++++++++++++
src/test/regress/sql/expressions.sql | 30 +++++++++++
16 files changed, 240 insertions(+), 27 deletions(-)