From 29f45e299e7ffa1df0db44b8452228625479487f Mon Sep 17 00:00:00 2001 From: David Rowley Date: Wed, 7 Jul 2021 16:29:17 +1200 Subject: 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 --- src/include/catalog/catversion.h | 2 +- src/include/executor/execExpr.h | 1 + src/include/nodes/primnodes.h | 18 ++++++++++++++---- 3 files changed, 16 insertions(+), 5 deletions(-) (limited to 'src/include') 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 */ -- cgit v1.2.3