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

3 files changed, 16 insertions, 5 deletions

diff --git a/src/include/catalog/catversion.h b/src/include/catalog/catversion.h
index 1b23c7c253b..e92ecaf3448 100644
--- a/src/include/catalog/catversion.h
+++ b/src/include/catalog/catversion.h
@@ -53,6 +53,6 @@
  */
 
 /*							yyyymmddN */
-#define CATALOG_VERSION_NO	202106151
+#define CATALOG_VERSION_NO	202107071
 
 #endif
diff --git a/src/include/executor/execExpr.h b/src/include/executor/execExpr.h
index 785600d04d0..6a24341faa7 100644
--- a/src/include/executor/execExpr.h
+++ b/src/include/executor/execExpr.h
@@ -574,6 +574,7 @@ typedef struct ExprEvalStep
 		struct
 		{
 			bool		has_nulls;
+			bool		inclause;	/* true for IN and false for NOT IN */
 			struct ScalarArrayOpExprHashTable *elements_tab;
 			FmgrInfo   *finfo;	/* function's lookup data */
 			FunctionCallInfo fcinfo_data;	/* arguments etc */
diff --git a/src/include/nodes/primnodes.h b/src/include/nodes/primnodes.h
index 9ae851d8477..996c3e40160 100644
--- a/src/include/nodes/primnodes.h
+++ b/src/include/nodes/primnodes.h
@@ -580,10 +580,18 @@ typedef OpExpr NullIfExpr;
  * the result type (or the collation) because it must be boolean.
  *
  * A ScalarArrayOpExpr with a valid hashfuncid is evaluated during execution
- * by building a hash table containing the Const values from the rhs arg.
- * This table is probed during expression evaluation.  Only useOr=true
- * ScalarArrayOpExpr with Const arrays on the rhs can have the hashfuncid
- * field set. See convert_saop_to_hashed_saop().
+ * by building a hash table containing the Const values from the RHS arg.
+ * This table is probed during expression evaluation.  The planner will set
+ * hashfuncid to the hash function which must be used to build and probe the
+ * hash table.  The executor determines if it should use hash-based checks or
+ * the more traditional means based on if the hashfuncid is set or not.
+ *
+ * When performing hashed NOT IN, the negfuncid will also be set to the
+ * equality function which the hash table must use to build and probe the hash
+ * table.  opno and opfuncid will remain set to the <> operator and its
+ * corresponding function and won't be used during execution.  For
+ * non-hashtable based NOT INs, negfuncid will be set to InvalidOid.  See
+ * convert_saop_to_hashed_saop().
  */
 typedef struct ScalarArrayOpExpr
 {
@@ -591,6 +599,8 @@ typedef struct ScalarArrayOpExpr
 	Oid			opno;			/* PG_OPERATOR OID of the operator */
 	Oid			opfuncid;		/* PG_PROC OID of comparison function */
 	Oid			hashfuncid;		/* PG_PROC OID of hash func or InvalidOid */
+	Oid			negfuncid;		/* PG_PROC OID of negator of opfuncid function
+								 * or InvalidOid.  See above */
 	bool		useOr;			/* true for ANY, false for ALL */
 	Oid			inputcollid;	/* OID of collation that operator should use */
 	List	   *args;			/* the scalar and array operands */