From 50e17ad281b8d1c1b410c9833955bc80fbad4078 Mon Sep 17 00:00:00 2001 From: David Rowley Date: Thu, 8 Apr 2021 23:51:22 +1200 Subject: Speedup ScalarArrayOpExpr evaluation ScalarArrayOpExprs with "useOr=true" and a set of Consts on the righthand side have traditionally been evaluated by using a linear search over the array. When these arrays contain large numbers of elements then this linear search could become a significant part of execution time. Here we add a new method of evaluating ScalarArrayOpExpr expressions to allow them to be evaluated by first building a hash table containing each element, then on subsequent evaluations, we just probe that hash table to determine if there is a match. The planner is in charge of determining when this optimization is possible and it enables it by setting hashfuncid in the ScalarArrayOpExpr. The executor will only perform the hash table evaluation when the hashfuncid is set. This means that not all cases are optimized. For example CHECK constraints containing an IN clause won't go through the planner, so won't get the hashfuncid set. We could maybe do something about that at some later date. The reason we're not doing it now is from fear that we may slow down cases where the expression is evaluated only once. Those cases can be common, for example, a single row INSERT to a table with a CHECK constraint containing an IN clause. In the planner, we enable this when there are suitable hash functions for the ScalarArrayOpExpr's operator and only when there is at least MIN_ARRAY_SIZE_FOR_HASHED_SAOP elements in the array. The threshold is currently set to 9. Author: James Coleman, David Rowley Reviewed-by: David Rowley, Tomas Vondra, Heikki Linnakangas Discussion: https://postgr.es/m/CAAaqYe8x62+=wn0zvNKCj55tPpg-JBHzhZFFc6ANovdqFw7-dA@mail.gmail.com --- src/backend/executor/execExpr.c | 99 ++++++++++--- src/backend/executor/execExprInterp.c | 262 ++++++++++++++++++++++++++++++++++ 2 files changed, 343 insertions(+), 18 deletions(-) (limited to 'src/backend/executor') diff --git a/src/backend/executor/execExpr.c b/src/backend/executor/execExpr.c index 23c0fb9379b..74fcfbea566 100644 --- a/src/backend/executor/execExpr.c +++ b/src/backend/executor/execExpr.c @@ -1149,6 +1149,8 @@ ExecInitExprRec(Expr *node, ExprState *state, FmgrInfo *finfo; FunctionCallInfo fcinfo; AclResult aclresult; + FmgrInfo *hash_finfo; + FunctionCallInfo hash_fcinfo; Assert(list_length(opexpr->args) == 2); scalararg = (Expr *) linitial(opexpr->args); @@ -1163,6 +1165,17 @@ ExecInitExprRec(Expr *node, ExprState *state, get_func_name(opexpr->opfuncid)); InvokeFunctionExecuteHook(opexpr->opfuncid); + if (OidIsValid(opexpr->hashfuncid)) + { + aclresult = pg_proc_aclcheck(opexpr->hashfuncid, + GetUserId(), + ACL_EXECUTE); + if (aclresult != ACLCHECK_OK) + aclcheck_error(aclresult, OBJECT_FUNCTION, + get_func_name(opexpr->hashfuncid)); + InvokeFunctionExecuteHook(opexpr->hashfuncid); + } + /* Set up the primary fmgr lookup information */ finfo = palloc0(sizeof(FmgrInfo)); fcinfo = palloc0(SizeForFunctionCallInfo(2)); @@ -1171,26 +1184,76 @@ ExecInitExprRec(Expr *node, ExprState *state, InitFunctionCallInfoData(*fcinfo, finfo, 2, opexpr->inputcollid, NULL, NULL); - /* Evaluate scalar directly into left function argument */ - ExecInitExprRec(scalararg, state, - &fcinfo->args[0].value, &fcinfo->args[0].isnull); - /* - * Evaluate array argument into our return value. There's no - * danger in that, because the return value is guaranteed to - * be overwritten by EEOP_SCALARARRAYOP, and will not be - * passed to any other expression. + * If hashfuncid is set, we create a EEOP_HASHED_SCALARARRAYOP + * step instead of a EEOP_SCALARARRAYOP. This provides much + * faster lookup performance than the normal linear search + * when the number of items in the array is anything but very + * small. */ - ExecInitExprRec(arrayarg, state, resv, resnull); - - /* And perform the operation */ - scratch.opcode = EEOP_SCALARARRAYOP; - scratch.d.scalararrayop.element_type = InvalidOid; - scratch.d.scalararrayop.useOr = opexpr->useOr; - scratch.d.scalararrayop.finfo = finfo; - scratch.d.scalararrayop.fcinfo_data = fcinfo; - scratch.d.scalararrayop.fn_addr = finfo->fn_addr; - ExprEvalPushStep(state, &scratch); + if (OidIsValid(opexpr->hashfuncid)) + { + hash_finfo = palloc0(sizeof(FmgrInfo)); + hash_fcinfo = palloc0(SizeForFunctionCallInfo(1)); + fmgr_info(opexpr->hashfuncid, hash_finfo); + fmgr_info_set_expr((Node *) node, hash_finfo); + InitFunctionCallInfoData(*hash_fcinfo, hash_finfo, + 1, opexpr->inputcollid, NULL, + NULL); + + scratch.d.hashedscalararrayop.hash_finfo = hash_finfo; + scratch.d.hashedscalararrayop.hash_fcinfo_data = hash_fcinfo; + scratch.d.hashedscalararrayop.hash_fn_addr = hash_finfo->fn_addr; + + /* Evaluate scalar directly into left function argument */ + ExecInitExprRec(scalararg, state, + &fcinfo->args[0].value, &fcinfo->args[0].isnull); + + /* + * Evaluate array argument into our return value. There's + * no danger in that, because the return value is + * guaranteed to be overwritten by + * EEOP_HASHED_SCALARARRAYOP, and will not be passed to + * any other expression. + */ + ExecInitExprRec(arrayarg, state, resv, resnull); + + /* And perform the operation */ + scratch.opcode = EEOP_HASHED_SCALARARRAYOP; + scratch.d.hashedscalararrayop.finfo = finfo; + scratch.d.hashedscalararrayop.fcinfo_data = fcinfo; + scratch.d.hashedscalararrayop.fn_addr = finfo->fn_addr; + + scratch.d.hashedscalararrayop.hash_finfo = hash_finfo; + scratch.d.hashedscalararrayop.hash_fcinfo_data = hash_fcinfo; + scratch.d.hashedscalararrayop.hash_fn_addr = hash_finfo->fn_addr; + + ExprEvalPushStep(state, &scratch); + } + else + { + /* Evaluate scalar directly into left function argument */ + ExecInitExprRec(scalararg, state, + &fcinfo->args[0].value, + &fcinfo->args[0].isnull); + + /* + * Evaluate array argument into our return value. There's + * no danger in that, because the return value is + * guaranteed to be overwritten by EEOP_SCALARARRAYOP, and + * will not be passed to any other expression. + */ + ExecInitExprRec(arrayarg, state, resv, resnull); + + /* And perform the operation */ + scratch.opcode = EEOP_SCALARARRAYOP; + scratch.d.scalararrayop.element_type = InvalidOid; + scratch.d.scalararrayop.useOr = opexpr->useOr; + scratch.d.scalararrayop.finfo = finfo; + scratch.d.scalararrayop.fcinfo_data = fcinfo; + scratch.d.scalararrayop.fn_addr = finfo->fn_addr; + ExprEvalPushStep(state, &scratch); + } break; } diff --git a/src/backend/executor/execExprInterp.c b/src/backend/executor/execExprInterp.c index 6308286d8c3..07948c1b131 100644 --- a/src/backend/executor/execExprInterp.c +++ b/src/backend/executor/execExprInterp.c @@ -178,6 +178,51 @@ static pg_attribute_always_inline void ExecAggPlainTransByRef(AggState *aggstate ExprContext *aggcontext, int setno); +/* + * ScalarArrayOpExprHashEntry + * Hash table entry type used during EEOP_HASHED_SCALARARRAYOP + */ +typedef struct ScalarArrayOpExprHashEntry +{ + Datum key; + uint32 status; /* hash status */ + uint32 hash; /* hash value (cached) */ +} ScalarArrayOpExprHashEntry; + +#define SH_PREFIX saophash +#define SH_ELEMENT_TYPE ScalarArrayOpExprHashEntry +#define SH_KEY_TYPE Datum +#define SH_SCOPE static inline +#define SH_DECLARE +#include "lib/simplehash.h" + +static bool saop_hash_element_match(struct saophash_hash *tb, Datum key1, + Datum key2); +static uint32 saop_element_hash(struct saophash_hash *tb, Datum key); + +/* + * ScalarArrayOpExprHashTable + * Hash table for EEOP_HASHED_SCALARARRAYOP + */ +typedef struct ScalarArrayOpExprHashTable +{ + saophash_hash *hashtab; /* underlying hash table */ + struct ExprEvalStep *op; +} ScalarArrayOpExprHashTable; + +/* Define parameters for ScalarArrayOpExpr hash table code generation. */ +#define SH_PREFIX saophash +#define SH_ELEMENT_TYPE ScalarArrayOpExprHashEntry +#define SH_KEY_TYPE Datum +#define SH_KEY key +#define SH_HASH_KEY(tb, key) saop_element_hash(tb, key) +#define SH_EQUAL(tb, a, b) saop_hash_element_match(tb, a, b) +#define SH_SCOPE static inline +#define SH_STORE_HASH +#define SH_GET_HASH(tb, a) a->hash +#define SH_DEFINE +#include "lib/simplehash.h" + /* * Prepare ExprState for interpreted execution. */ @@ -426,6 +471,7 @@ ExecInterpExpr(ExprState *state, ExprContext *econtext, bool *isnull) &&CASE_EEOP_DOMAIN_CHECK, &&CASE_EEOP_CONVERT_ROWTYPE, &&CASE_EEOP_SCALARARRAYOP, + &&CASE_EEOP_HASHED_SCALARARRAYOP, &&CASE_EEOP_XMLEXPR, &&CASE_EEOP_AGGREF, &&CASE_EEOP_GROUPING_FUNC, @@ -1436,6 +1482,14 @@ ExecInterpExpr(ExprState *state, ExprContext *econtext, bool *isnull) EEO_NEXT(); } + EEO_CASE(EEOP_HASHED_SCALARARRAYOP) + { + /* too complex for an inline implementation */ + ExecEvalHashedScalarArrayOp(state, op, econtext); + + EEO_NEXT(); + } + EEO_CASE(EEOP_DOMAIN_NOTNULL) { /* too complex for an inline implementation */ @@ -3345,6 +3399,214 @@ ExecEvalScalarArrayOp(ExprState *state, ExprEvalStep *op) *op->resnull = resultnull; } +/* + * Hash function for scalar array hash op elements. + * + * We use the element type's default hash opclass, and the column collation + * if the type is collation-sensitive. + */ +static uint32 +saop_element_hash(struct saophash_hash *tb, Datum key) +{ + ScalarArrayOpExprHashTable *elements_tab = (ScalarArrayOpExprHashTable *) tb->private_data; + FunctionCallInfo fcinfo = elements_tab->op->d.hashedscalararrayop.hash_fcinfo_data; + Datum hash; + + fcinfo->args[0].value = key; + fcinfo->args[0].isnull = false; + + hash = elements_tab->op->d.hashedscalararrayop.hash_fn_addr(fcinfo); + + return DatumGetUInt32(hash); +} + +/* + * Matching function for scalar array hash op elements, to be used in hashtable + * lookups. + */ +static bool +saop_hash_element_match(struct saophash_hash *tb, Datum key1, Datum key2) +{ + Datum result; + + ScalarArrayOpExprHashTable *elements_tab = (ScalarArrayOpExprHashTable *) tb->private_data; + FunctionCallInfo fcinfo = elements_tab->op->d.hashedscalararrayop.fcinfo_data; + + fcinfo->args[0].value = key1; + fcinfo->args[0].isnull = false; + fcinfo->args[1].value = key2; + fcinfo->args[1].isnull = false; + + result = elements_tab->op->d.hashedscalararrayop.fn_addr(fcinfo); + + return DatumGetBool(result); +} + +/* + * Evaluate "scalar op ANY (const array)". + * + * Similar to ExecEvalScalarArrayOp, but optimized for faster repeat lookups + * by building a hashtable on the first lookup. This hashtable will be reused + * by subsequent lookups. Unlike ExecEvalScalarArrayOp, this version only + * supports OR semantics. + * + * Source array is in our result area, scalar arg is already evaluated into + * fcinfo->args[0]. + * + * The operator always yields boolean. + */ +void +ExecEvalHashedScalarArrayOp(ExprState *state, ExprEvalStep *op, ExprContext *econtext) +{ + ScalarArrayOpExprHashTable *elements_tab = op->d.hashedscalararrayop.elements_tab; + FunctionCallInfo fcinfo = op->d.hashedscalararrayop.fcinfo_data; + bool strictfunc = op->d.hashedscalararrayop.finfo->fn_strict; + Datum scalar = fcinfo->args[0].value; + bool scalar_isnull = fcinfo->args[0].isnull; + Datum result; + bool resultnull; + bool hashfound; + + /* We don't setup a hashed scalar array op if the array const is null. */ + Assert(!*op->resnull); + + /* + * If the scalar is NULL, and the function is strict, return NULL; no + * point in executing the search. + */ + if (fcinfo->args[0].isnull && strictfunc) + { + *op->resnull = true; + return; + } + + /* Build the hash table on first evaluation */ + if (elements_tab == NULL) + { + int16 typlen; + bool typbyval; + char typalign; + int nitems; + bool has_nulls = false; + char *s; + bits8 *bitmap; + int bitmask; + MemoryContext oldcontext; + ArrayType *arr; + + arr = DatumGetArrayTypeP(*op->resvalue); + nitems = ArrayGetNItems(ARR_NDIM(arr), ARR_DIMS(arr)); + + get_typlenbyvalalign(ARR_ELEMTYPE(arr), + &typlen, + &typbyval, + &typalign); + + oldcontext = MemoryContextSwitchTo(econtext->ecxt_per_query_memory); + + elements_tab = (ScalarArrayOpExprHashTable *) + palloc(sizeof(ScalarArrayOpExprHashTable)); + op->d.hashedscalararrayop.elements_tab = elements_tab; + elements_tab->op = op; + + /* + * Create the hash table sizing it according to the number of elements + * in the array. This does assume that the array has no duplicates. + * If the array happens to contain many duplicate values then it'll + * just mean that we sized the table a bit on the large side. + */ + elements_tab->hashtab = saophash_create(CurrentMemoryContext, nitems, + elements_tab); + + MemoryContextSwitchTo(oldcontext); + + s = (char *) ARR_DATA_PTR(arr); + bitmap = ARR_NULLBITMAP(arr); + bitmask = 1; + for (int i = 0; i < nitems; i++) + { + /* Get array element, checking for NULL. */ + if (bitmap && (*bitmap & bitmask) == 0) + { + has_nulls = true; + } + else + { + Datum element; + + element = fetch_att(s, typbyval, typlen); + s = att_addlength_pointer(s, typlen, s); + s = (char *) att_align_nominal(s, typalign); + + saophash_insert(elements_tab->hashtab, element, &hashfound); + } + + /* Advance bitmap pointer if any. */ + if (bitmap) + { + bitmask <<= 1; + if (bitmask == 0x100) + { + bitmap++; + bitmask = 1; + } + } + } + + /* + * Remember if we had any nulls so that we know if we need to execute + * non-strict functions with a null lhs value if no match is found. + */ + op->d.hashedscalararrayop.has_nulls = has_nulls; + } + + /* Check the hash to see if we have a match. */ + hashfound = NULL != saophash_lookup(elements_tab->hashtab, scalar); + + result = BoolGetDatum(hashfound); + resultnull = false; + + /* + * If we didn't find a match in the array, we still might need to handle + * the possibility of null values. We didn't put any NULLs into the + * hashtable, but instead marked if we found any when building the table + * in has_nulls. + */ + if (!DatumGetBool(result) && op->d.hashedscalararrayop.has_nulls) + { + if (strictfunc) + { + + /* + * We have nulls in the array so a non-null lhs and no match must + * yield NULL. + */ + result = (Datum) 0; + resultnull = true; + } + else + { + /* + * Execute function will null rhs just once. + * + * The hash lookup path will have scribbled on the lhs argument so + * we need to set it up also (even though we entered this function + * with it already set). + */ + fcinfo->args[0].value = scalar; + fcinfo->args[0].isnull = scalar_isnull; + fcinfo->args[1].value = (Datum) 0; + fcinfo->args[1].isnull = true; + + result = op->d.hashedscalararrayop.fn_addr(fcinfo); + resultnull = fcinfo->isnull; + } + } + + *op->resvalue = result; + *op->resnull = resultnull; +} + /* * Evaluate a NOT NULL domain constraint. */ -- cgit v1.2.3