Add ExprState hashing for GROUP BY and hashed SubPlans
adf97c156 added support to allow ExprStates to support hashing and
adjusted Hash Join to make use of that. That allowed a speedup in hash
value generation as it allowed JIT compilation of hash values. It also
allowed more efficient tuple deforming as all required attributes are
deformed in one go rather than on demand when hashing each join key.
The attached does the same for GROUP BY and hashed SubPlans. The win
for the tuple deformation does not exist here, but there does seem to
be some gains still to be had from JIT compilation.
Using a scale=1 TPC-H lineitem table, I ran the attached script.
The increase is far from impressive, but likely worth migrating these
over to use ExprState too.
master:
alter system set jit = 0;
latency average = 1509.116 ms
latency average = 1502.496 ms
latency average = 1507.560 ms
alter system set jit = 1;
latency average = 1396.015 ms
latency average = 1392.138 ms
latency average = 1396.476 ms
alter system set jit_optimize_above_cost = 0;
latency average = 1290.463 ms
latency average = 1293.364 ms
latency average = 1290.366 ms
alter system set jit_inline_above_cost = 0;
latency average = 1294.540 ms
latency average = 1300.970 ms
latency average = 1302.181 ms
patched:
alter system set jit = 0;
latency average = 1500.183 ms
latency average = 1500.911 ms
latency average = 1504.150 ms (+0.31%)
alter system set jit = 1;
latency average = 1367.427 ms
latency average = 1367.329 ms
latency average = 1366.473 ms (+2.03%)
alter system set jit_optimize_above_cost = 0;
latency average = 1273.453 ms
latency average = 1265.348 ms
latency average = 1272.598 ms (+1.65%)
alter system set jit_inline_above_cost = 0;
latency average = 1264.657 ms
latency average = 1272.661 ms
latency average = 1273.179 ms (+2.29%)
David
Attachments:
v1-0001-Use-ExprStates-for-hashing-in-GROUP-BY-and-SubPla.patchapplication/octet-stream; name=v1-0001-Use-ExprStates-for-hashing-in-GROUP-BY-and-SubPla.patchDownload
From 07b26551b82b603812de06a160263d755cd66b92 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Wed, 7 Aug 2024 16:56:48 +1200
Subject: [PATCH v1] Use ExprStates for hashing in GROUP BY and SubPlans
This speeds up obtaining hash values for GROUP BY and for hashed
SubPlan by using the ExprState support for hashing. This allows JIT
compilation for hash value.
---
src/backend/executor/execExpr.c | 115 ++++++++++++++++++++++++++++
src/backend/executor/execGrouping.c | 73 ++++++++----------
src/backend/executor/nodeSubplan.c | 11 ++-
src/include/executor/executor.h | 10 ++-
src/include/nodes/execnodes.h | 8 +-
5 files changed, 170 insertions(+), 47 deletions(-)
diff --git a/src/backend/executor/execExpr.c b/src/backend/executor/execExpr.c
index 63289ee35e..881ab6516e 100644
--- a/src/backend/executor/execExpr.c
+++ b/src/backend/executor/execExpr.c
@@ -3969,6 +3969,121 @@ ExecBuildAggTransCall(ExprState *state, AggState *aggstate,
}
}
+/*
+ * Build an ExprState that calls the given hash function(s) on the attnums
+ * given by 'keyColIdx' . When numCols > 1, the hash values returned by each
+ * hash function are combined to produce a single hash value.
+ *
+ * desc: tuple descriptor for the to-be-hashed expressions
+ * ops: TupleTableSlotOps for the TupleDesc
+ * hashfunctions: FmgrInfos for each hash function to call one per numCols
+ * collations: collation to use when calling the hash function.
+ * numCols: array length of hashfunctions, collations and keyColIdx.
+ * parent: PlanState node that the 'hash_exprs' will be evaluated at
+ * init_value: Normally 0, but can be set to other values to seed the hash
+ * with some other value. Using non-zero is slightly less efficient but can
+ * be useful.
+ */
+ExprState *
+ExecBuildHash32FromAttrs(TupleDesc desc, const TupleTableSlotOps *ops,
+ FmgrInfo *hashfunctions, Oid *collations,
+ int numCols, AttrNumber *keyColIdx,
+ PlanState *parent, uint32 init_value)
+{
+ ExprState *state = makeNode(ExprState);
+ ExprEvalStep scratch = {0};
+ intptr_t opcode;
+ AttrNumber last_attnum = 0;
+
+ state->parent = parent;
+
+ /* find the highest attnum so we deform the tuple to that point */
+ for (int i = 0; i < numCols; i++)
+ last_attnum = Max(last_attnum, keyColIdx[i]);
+
+ scratch.opcode = EEOP_INNER_FETCHSOME;
+ scratch.d.fetch.last_var = last_attnum;
+ scratch.d.fetch.fixed = false;
+ scratch.d.fetch.kind = NULL;
+ scratch.d.fetch.known_desc = NULL;
+ ExprEvalPushStep(state, &scratch);
+
+ if (init_value == 0)
+ {
+ /*
+ * No initial value, so we can assign the result of the hash function
+ * for the first hash_expr without having to concern ourselves with
+ * combining the result with any initial value.
+ */
+ opcode = EEOP_HASHDATUM_FIRST;
+ }
+ else
+ {
+ /* Set up operation to set the initial value. */
+ scratch.opcode = EEOP_HASHDATUM_SET_INITVAL;
+ scratch.d.hashdatum_initvalue.init_value = UInt32GetDatum(init_value);
+ scratch.resvalue = &state->resvalue;
+ scratch.resnull = &state->resnull;
+
+ ExprEvalPushStep(state, &scratch);
+
+ /*
+ * When using an initial value use the NEXT32 ops as the FIRST ops
+ * would overwrite the stored initial value.
+ */
+ opcode = EEOP_HASHDATUM_NEXT32;
+ }
+
+ for (int i = 0; i < numCols; i++)
+ {
+ FmgrInfo *finfo;
+ FunctionCallInfo fcinfo;
+ Oid inputcollid = collations[i];
+ AttrNumber attnum = keyColIdx[i] - 1;
+
+ finfo = &hashfunctions[i];
+ fcinfo = palloc0(SizeForFunctionCallInfo(1));
+
+ /* Initialize function call parameter structure too */
+ InitFunctionCallInfoData(*fcinfo, finfo, 1, inputcollid, NULL, NULL);
+
+ /*
+ * Fetch inner Var for this attnum and store it in the 1st arg of the
+ * hash func.
+ */
+ scratch.opcode = EEOP_INNER_VAR;
+ scratch.resvalue = &fcinfo->args[0].value;
+ scratch.resnull = &fcinfo->args[0].isnull;
+ scratch.d.var.attnum = attnum;
+ scratch.d.var.vartype = TupleDescAttr(desc, attnum)->atttypid;
+
+ ExprEvalPushStep(state, &scratch);
+
+ /* Call the hash function */
+ scratch.opcode = opcode;
+ scratch.resvalue = &state->resvalue;
+ scratch.resnull = &state->resnull;
+ scratch.d.hashdatum.finfo = finfo;
+ scratch.d.hashdatum.fcinfo_data = fcinfo;
+ scratch.d.hashdatum.fn_addr = finfo->fn_addr;
+ scratch.d.hashdatum.jumpdone = -1;
+
+ ExprEvalPushStep(state, &scratch);
+
+ /* subsequent attnums must be combined with the previous */
+ opcode = EEOP_HASHDATUM_NEXT32;
+ }
+
+ scratch.resvalue = NULL;
+ scratch.resnull = NULL;
+ scratch.opcode = EEOP_DONE;
+ ExprEvalPushStep(state, &scratch);
+
+ ExecReadyExpr(state);
+
+ return state;
+}
+
/*
* Build an ExprState that calls the given hash function(s) on the given
* 'hash_exprs'. When multiple expressions are present, the hash values
diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c
index 7233f1e3c0..b5c01e48f5 100644
--- a/src/backend/executor/execGrouping.c
+++ b/src/backend/executor/execGrouping.c
@@ -167,6 +167,7 @@ BuildTupleHashTableExt(PlanState *parent,
Size hash_mem_limit;
MemoryContext oldcontext;
bool allow_jit;
+ uint32 hash_iv = 0;
Assert(nbuckets > 0);
@@ -181,14 +182,12 @@ BuildTupleHashTableExt(PlanState *parent,
hashtable->numCols = numCols;
hashtable->keyColIdx = keyColIdx;
- hashtable->tab_hash_funcs = hashfunctions;
hashtable->tab_collations = collations;
hashtable->tablecxt = tablecxt;
hashtable->tempcxt = tempcxt;
hashtable->entrysize = entrysize;
hashtable->tableslot = NULL; /* will be made on first lookup */
hashtable->inputslot = NULL;
- hashtable->in_hash_funcs = NULL;
hashtable->cur_eq_func = NULL;
/*
@@ -200,9 +199,7 @@ BuildTupleHashTableExt(PlanState *parent,
* underestimated.
*/
if (use_variable_hash_iv)
- hashtable->hash_iv = murmurhash32(ParallelWorkerNumber);
- else
- hashtable->hash_iv = 0;
+ hash_iv = murmurhash32(ParallelWorkerNumber);
hashtable->hashtab = tuplehash_create(metacxt, nbuckets, hashtable);
@@ -223,6 +220,16 @@ BuildTupleHashTableExt(PlanState *parent,
*/
allow_jit = metacxt != tablecxt;
+ hashtable->tab_hash_expr = ExecBuildHash32FromAttrs(inputDesc,
+ &TTSOpsMinimalTuple,
+ hashfunctions,
+ collations,
+ numCols,
+ keyColIdx,
+ parent,
+ hash_iv);
+ hashtable->in_hash_expr = NULL;
+
/* build comparator for all columns */
/* XXX: should we support non-minimal tuples for the inputslot? */
hashtable->tab_eq_func = ExecBuildGroupingEqual(inputDesc, inputDesc,
@@ -314,7 +321,7 @@ LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
/* set up data needed by hash and match functions */
hashtable->inputslot = slot;
- hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
+ hashtable->in_hash_expr = hashtable->tab_hash_expr;
hashtable->cur_eq_func = hashtable->tab_eq_func;
local_hash = TupleHashTableHash_internal(hashtable->hashtab, NULL);
@@ -340,7 +347,7 @@ TupleHashTableHash(TupleHashTable hashtable, TupleTableSlot *slot)
uint32 hash;
hashtable->inputslot = slot;
- hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
+ hashtable->in_hash_expr = hashtable->tab_hash_expr;
/* Need to run the hash functions in short-lived context */
oldContext = MemoryContextSwitchTo(hashtable->tempcxt);
@@ -368,7 +375,7 @@ LookupTupleHashEntryHash(TupleHashTable hashtable, TupleTableSlot *slot,
/* set up data needed by hash and match functions */
hashtable->inputslot = slot;
- hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
+ hashtable->in_hash_expr = hashtable->tab_hash_expr;
hashtable->cur_eq_func = hashtable->tab_eq_func;
entry = LookupTupleHashEntry_internal(hashtable, slot, isnew, hash);
@@ -391,7 +398,7 @@ LookupTupleHashEntryHash(TupleHashTable hashtable, TupleTableSlot *slot,
TupleHashEntry
FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
ExprState *eqcomp,
- FmgrInfo *hashfunctions)
+ ExprState *hashexpr)
{
TupleHashEntry entry;
MemoryContext oldContext;
@@ -402,7 +409,7 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
/* Set up data needed by hash and match functions */
hashtable->inputslot = slot;
- hashtable->in_hash_funcs = hashfunctions;
+ hashtable->in_hash_expr = hashexpr;
hashtable->cur_eq_func = eqcomp;
/* Search the hash table */
@@ -419,25 +426,24 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
* copied into the table.
*
* Also, the caller must select an appropriate memory context for running
- * the hash functions. (dynahash.c doesn't change CurrentMemoryContext.)
+ * the hash functions.
*/
static uint32
TupleHashTableHash_internal(struct tuplehash_hash *tb,
const MinimalTuple tuple)
{
TupleHashTable hashtable = (TupleHashTable) tb->private_data;
- int numCols = hashtable->numCols;
- AttrNumber *keyColIdx = hashtable->keyColIdx;
- uint32 hashkey = hashtable->hash_iv;
+ uint32 hashkey;
TupleTableSlot *slot;
- FmgrInfo *hashfunctions;
- int i;
+ bool isnull;
if (tuple == NULL)
{
/* Process the current input tuple for the table */
- slot = hashtable->inputslot;
- hashfunctions = hashtable->in_hash_funcs;
+ hashtable->exprcontext->ecxt_innertuple = hashtable->inputslot;
+ hashkey = DatumGetUInt32(ExecEvalExpr(hashtable->in_hash_expr,
+ hashtable->exprcontext,
+ &isnull));
}
else
{
@@ -447,32 +453,17 @@ TupleHashTableHash_internal(struct tuplehash_hash *tb,
* (this case never actually occurs due to the way simplehash.h is
* used, as the hash-value is stored in the entries)
*/
- slot = hashtable->tableslot;
+ slot = hashtable->exprcontext->ecxt_innertuple = hashtable->tableslot;
ExecStoreMinimalTuple(tuple, slot, false);
- hashfunctions = hashtable->tab_hash_funcs;
+ hashkey = DatumGetUInt32(ExecEvalExpr(hashtable->tab_hash_expr,
+ hashtable->exprcontext,
+ &isnull));
}
- for (i = 0; i < numCols; i++)
- {
- AttrNumber att = keyColIdx[i];
- Datum attr;
- bool isNull;
-
- /* combine successive hashkeys by rotating */
- hashkey = pg_rotate_left32(hashkey, 1);
-
- attr = slot_getattr(slot, att, &isNull);
-
- if (!isNull) /* treat nulls as having hash key 0 */
- {
- uint32 hkey;
-
- hkey = DatumGetUInt32(FunctionCall1Coll(&hashfunctions[i],
- hashtable->tab_collations[i],
- attr));
- hashkey ^= hkey;
- }
- }
+#ifdef USE_ASSERT_CHECKING
+ /* XXX not for commit. */
+ elog(DEBUG1, "hashkey = %u", hashkey);
+#endif
/*
* The way hashes are combined above, among each other and with the IV,
diff --git a/src/backend/executor/nodeSubplan.c b/src/backend/executor/nodeSubplan.c
index a96cdd01e1..3d13944aef 100644
--- a/src/backend/executor/nodeSubplan.c
+++ b/src/backend/executor/nodeSubplan.c
@@ -160,7 +160,7 @@ ExecHashSubPlan(SubPlanState *node,
FindTupleHashEntry(node->hashtable,
slot,
node->cur_eq_comp,
- node->lhs_hash_funcs) != NULL)
+ node->cur_hash_expr) != NULL)
{
ExecClearTuple(slot);
return BoolGetDatum(true);
@@ -1043,6 +1043,15 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
sstate->planstate,
NULL);
+ sstate->cur_hash_expr = ExecBuildHash32FromAttrs(tupDescLeft,
+ &TTSOpsMinimalTuple,
+ sstate->lhs_hash_funcs,
+ sstate->tab_collations,
+ sstate->numCols,
+ sstate->keyColIdx,
+ parent,
+ 0);
+
/*
* Create comparator for lookups of rows in the table (potentially
* cross-type comparisons).
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index 69c3ebff00..e77377ff9b 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -160,7 +160,7 @@ extern TupleHashEntry LookupTupleHashEntryHash(TupleHashTable hashtable,
extern TupleHashEntry FindTupleHashEntry(TupleHashTable hashtable,
TupleTableSlot *slot,
ExprState *eqcomp,
- FmgrInfo *hashfunctions);
+ ExprState *hashexpr);
extern void ResetTupleHashTable(TupleHashTable hashtable);
/*
@@ -289,6 +289,14 @@ extern ExprState *ExecInitCheck(List *qual, PlanState *parent);
extern List *ExecInitExprList(List *nodes, PlanState *parent);
extern ExprState *ExecBuildAggTrans(AggState *aggstate, struct AggStatePerPhaseData *phase,
bool doSort, bool doHash, bool nullcheck);
+extern ExprState *ExecBuildHash32FromAttrs(TupleDesc desc,
+ const TupleTableSlotOps *ops,
+ FmgrInfo *hashfunctions,
+ Oid *collations,
+ int numCols,
+ AttrNumber *keyColIdx,
+ PlanState *parent,
+ uint32 init_value);
extern ExprState *ExecBuildHash32Expr(TupleDesc desc,
const TupleTableSlotOps *ops,
const Oid *hashfunc_oids,
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index af7d8fd1e7..e02508d031 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -789,7 +789,7 @@ typedef struct ExecAuxRowMark
* Normally these are the only functions used, but FindTupleHashEntry()
* supports searching a hashtable using cross-data-type hashing. For that,
* the caller must supply hash functions for the LHS datatype as well as
- * the cross-type equality operators to use. in_hash_funcs and cur_eq_func
+ * the cross-type equality operators to use. in_hash_expr and cur_eq_func
* are set to point to the caller's function arrays while doing such a search.
* During LookupTupleHashEntry(), they point to tab_hash_funcs and
* tab_eq_func respectively.
@@ -819,7 +819,7 @@ typedef struct TupleHashTableData
tuplehash_hash *hashtab; /* underlying hash table */
int numCols; /* number of columns in lookup key */
AttrNumber *keyColIdx; /* attr numbers of key columns */
- FmgrInfo *tab_hash_funcs; /* hash functions for table datatype(s) */
+ ExprState *tab_hash_expr; /* ExprState for hashing table datatype(s) */
ExprState *tab_eq_func; /* comparator for table datatype(s) */
Oid *tab_collations; /* collations for hash and comparison */
MemoryContext tablecxt; /* memory context containing table */
@@ -828,9 +828,8 @@ typedef struct TupleHashTableData
TupleTableSlot *tableslot; /* slot for referencing table entries */
/* The following fields are set transiently for each table search: */
TupleTableSlot *inputslot; /* current input tuple's slot */
- FmgrInfo *in_hash_funcs; /* hash functions for input datatype(s) */
+ ExprState *in_hash_expr; /* ExprState for hashing input datatype(s) */
ExprState *cur_eq_func; /* comparator for input vs. table */
- uint32 hash_iv; /* hash-function IV */
ExprContext *exprcontext; /* expression context */
} TupleHashTableData;
@@ -986,6 +985,7 @@ typedef struct SubPlanState
FmgrInfo *tab_eq_funcs; /* equality functions for table datatype(s) */
FmgrInfo *lhs_hash_funcs; /* hash functions for lefthand datatype(s) */
FmgrInfo *cur_eq_funcs; /* equality functions for LHS vs. table */
+ ExprState *cur_hash_expr; /* get hash value for LSH vs table */
ExprState *cur_eq_comp; /* equality comparator for LHS vs. table */
} SubPlanState;
--
2.34.1
On 9/1/24 18:49, David Rowley wrote:
adf97c156 added support to allow ExprStates to support hashing and
adjusted Hash Join to make use of that. That allowed a speedup in hash
value generation as it allowed JIT compilation of hash values. It also
allowed more efficient tuple deforming as all required attributes are
deformed in one go rather than on demand when hashing each join key.The attached does the same for GROUP BY and hashed SubPlans. The win
for the tuple deformation does not exist here, but there does seem to
be some gains still to be had from JIT compilation.Using a scale=1 TPC-H lineitem table, I ran the attached script.
The increase is far from impressive, but likely worth migrating these
over to use ExprState too.
Having remembered that SQL Server uses lightweight threads to execute
massive hash and aggregate operations in parallel, I think this patch is
promising. Unfortunately, it causes SEGFAULT on 'make check'.
--
regards, Andrei Lepikhov
On Mon, 28 Oct 2024 at 21:51, Andrei Lepikhov <lepihov@gmail.com> wrote:
Having remembered that SQL Server uses lightweight threads to execute
massive hash and aggregate operations in parallel, I think this patch is
promising. Unfortunately, it causes SEGFAULT on 'make check'.
Thanks for having a look. The crash is because I'd not quite gotten
around to adjusting this to account for the changes made in 9ca67658d
yet. Without adjustment, the ExprState evaluation code would be
looking at an uninitialised location to store the intermediate hash
value.
I've attached an updated patch with a few other fixes. Whilr checking
this tonight, noticed that master does not use
SubPlanState.tab_eq_funcs for anything. I resisted removing that in
this patch. Perhaps a follow-on patch can remove that. I suspect it's
not been used for a long time now, but I didn't do the archaeology
work to find out.
David
Attachments:
v2-0001-Use-ExprStates-for-hashing-in-GROUP-BY-and-SubPla.patchapplication/octet-stream; name=v2-0001-Use-ExprStates-for-hashing-in-GROUP-BY-and-SubPla.patchDownload
From 683507ece96034fe1cd276575fc787523f5ad9a5 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Wed, 7 Aug 2024 16:56:48 +1200
Subject: [PATCH v2] Use ExprStates for hashing in GROUP BY and SubPlans
This speeds up obtaining hash values for GROUP BY and for hashed
SubPlan by using the ExprState support for hashing. This allows JIT
compilation for hash value.
---
src/backend/executor/execExpr.c | 149 ++++++++++++++++++++++++++++
src/backend/executor/execGrouping.c | 85 +++++++---------
src/backend/executor/nodeSubplan.c | 17 +++-
src/include/executor/executor.h | 10 +-
src/include/nodes/execnodes.h | 15 ++-
5 files changed, 216 insertions(+), 60 deletions(-)
diff --git a/src/backend/executor/execExpr.c b/src/backend/executor/execExpr.c
index 45954d979f..d3f88930b0 100644
--- a/src/backend/executor/execExpr.c
+++ b/src/backend/executor/execExpr.c
@@ -3971,6 +3971,155 @@ ExecBuildAggTransCall(ExprState *state, AggState *aggstate,
}
}
+/*
+ * Build an ExprState that calls the given hash function(s) on the attnums
+ * given by 'keyColIdx' . When numCols > 1, the hash values returned by each
+ * hash function are combined to produce a single hash value.
+ *
+ * desc: tuple descriptor for the to-be-hashed columns
+ * ops: TupleTableSlotOps for the TupleDesc
+ * hashfunctions: FmgrInfos for each hash function to call, one per numCols.
+ * These are used directly in the returned ExprState so must remain allocated.
+ * collations: collation to use when calling the hash function.
+ * numCols: array length of hashfunctions, collations and keyColIdx.
+ * parent: PlanState node that the resulting ExprState will be evaluated at
+ * init_value: Normally 0, but can be set to other values to seed the hash
+ * with some other value. Using non-zero is slightly less efficient but can
+ * be useful.
+ */
+ExprState *
+ExecBuildHash32FromAttrs(TupleDesc desc, const TupleTableSlotOps *ops,
+ FmgrInfo *hashfunctions, Oid *collations,
+ int numCols, AttrNumber *keyColIdx,
+ PlanState *parent, uint32 init_value)
+{
+ ExprState *state = makeNode(ExprState);
+ ExprEvalStep scratch = {0};
+ NullableDatum *iresult = NULL;
+ intptr_t opcode;
+ AttrNumber last_attnum = 0;
+
+ state->parent = parent;
+
+ /* find the highest attnum so we deform the tuple to that point */
+ for (int i = 0; i < numCols; i++)
+ last_attnum = Max(last_attnum, keyColIdx[i]);
+
+ scratch.opcode = EEOP_INNER_FETCHSOME;
+ scratch.d.fetch.last_var = last_attnum;
+ scratch.d.fetch.fixed = false;
+ scratch.d.fetch.kind = NULL;
+ scratch.d.fetch.known_desc = NULL;
+ if (ExecComputeSlotInfo(state, &scratch))
+ ExprEvalPushStep(state, &scratch);
+
+ if (init_value == 0)
+ {
+ /*
+ * No initial value, so we can assign the result of the hash function
+ * for the first hash_expr without having to concern ourselves with
+ * combining the result with any initial value.
+ */
+ opcode = EEOP_HASHDATUM_FIRST;
+ }
+ else
+ {
+ /* Set up operation to set the initial value. */
+ scratch.opcode = EEOP_HASHDATUM_SET_INITVAL;
+ scratch.d.hashdatum_initvalue.init_value = UInt32GetDatum(init_value);
+ scratch.resvalue = &state->resvalue;
+ scratch.resnull = &state->resnull;
+
+ ExprEvalPushStep(state, &scratch);
+
+ /*
+ * When using an initial value use the NEXT32 ops as the FIRST ops
+ * would overwrite the stored initial value.
+ */
+ opcode = EEOP_HASHDATUM_NEXT32;
+ }
+
+ /*
+ * When hashing more than 1 column or if we have an init value, we need
+ * somewhere to store the intermediate hash value so that it's available
+ * to be combined with the result of subsequent hashing.
+ */
+ if (numCols > 1 || init_value != 0)
+ iresult = palloc(sizeof(NullableDatum));
+
+ for (int i = 0; i < numCols; i++)
+ {
+ FmgrInfo *finfo;
+ FunctionCallInfo fcinfo;
+ Oid inputcollid = collations[i];
+ AttrNumber attnum = keyColIdx[i] - 1;
+
+ finfo = &hashfunctions[i];
+ fcinfo = palloc0(SizeForFunctionCallInfo(1));
+
+ /* Initialize function call parameter structure too */
+ InitFunctionCallInfoData(*fcinfo, finfo, 1, inputcollid, NULL, NULL);
+
+ /*
+ * Fetch inner Var for this attnum and store it in the 1st arg of the
+ * hash func.
+ */
+ scratch.opcode = EEOP_INNER_VAR;
+ scratch.resvalue = &fcinfo->args[0].value;
+ scratch.resnull = &fcinfo->args[0].isnull;
+ scratch.d.var.attnum = attnum;
+ scratch.d.var.vartype = TupleDescAttr(desc, attnum)->atttypid;
+
+ ExprEvalPushStep(state, &scratch);
+
+ /* Call the hash function */
+ scratch.opcode = opcode;
+
+ if (i == numCols - 1)
+ {
+ /*
+ * The result for hashing the final column is stored in the
+ * ExprState.
+ */
+ scratch.resvalue = &state->resvalue;
+ scratch.resnull = &state->resnull;
+ }
+ else
+ {
+ Assert(iresult != NULL);
+
+ /* intermediate values are stored in an intermediate result */
+ scratch.resvalue = &iresult->value;
+ scratch.resnull = &iresult->isnull;
+ }
+
+ /*
+ * NEXT32 opcodes need to look at the intermediate result. We might
+ * as well just set this for all ops. FIRSTs won't look at it.
+ */
+ scratch.d.hashdatum.iresult = iresult;
+
+ scratch.d.hashdatum.finfo = finfo;
+ scratch.d.hashdatum.fcinfo_data = fcinfo;
+ scratch.d.hashdatum.fn_addr = finfo->fn_addr;
+ scratch.d.hashdatum.jumpdone = -1;
+
+ ExprEvalPushStep(state, &scratch);
+
+ /* subsequent attnums must be combined with the previous */
+ opcode = EEOP_HASHDATUM_NEXT32;
+ }
+
+ scratch.resvalue = NULL;
+ scratch.resnull = NULL;
+ scratch.opcode = EEOP_DONE;
+ ExprEvalPushStep(state, &scratch);
+
+ ExecReadyExpr(state);
+
+ return state;
+}
+
/*
* Build an ExprState that calls the given hash function(s) on the given
* 'hash_exprs'. When multiple expressions are present, the hash values
diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c
index 774e4de882..3c485a219c 100644
--- a/src/backend/executor/execGrouping.c
+++ b/src/backend/executor/execGrouping.c
@@ -169,6 +169,7 @@ BuildTupleHashTableExt(PlanState *parent,
Size hash_mem_limit;
MemoryContext oldcontext;
bool allow_jit;
+ uint32 hash_iv = 0;
Assert(nbuckets > 0);
@@ -183,14 +184,13 @@ BuildTupleHashTableExt(PlanState *parent,
hashtable->numCols = numCols;
hashtable->keyColIdx = keyColIdx;
- hashtable->tab_hash_funcs = hashfunctions;
hashtable->tab_collations = collations;
hashtable->tablecxt = tablecxt;
hashtable->tempcxt = tempcxt;
hashtable->entrysize = entrysize;
hashtable->tableslot = NULL; /* will be made on first lookup */
hashtable->inputslot = NULL;
- hashtable->in_hash_funcs = NULL;
+ hashtable->in_hash_expr = NULL;
hashtable->cur_eq_func = NULL;
/*
@@ -202,9 +202,7 @@ BuildTupleHashTableExt(PlanState *parent,
* underestimated.
*/
if (use_variable_hash_iv)
- hashtable->hash_iv = murmurhash32(ParallelWorkerNumber);
- else
- hashtable->hash_iv = 0;
+ hash_iv = murmurhash32(ParallelWorkerNumber);
hashtable->hashtab = tuplehash_create(metacxt, nbuckets, hashtable);
@@ -225,6 +223,15 @@ BuildTupleHashTableExt(PlanState *parent,
*/
allow_jit = metacxt != tablecxt;
+ hashtable->tab_hash_expr = ExecBuildHash32FromAttrs(inputDesc,
+ &TTSOpsMinimalTuple,
+ hashfunctions,
+ collations,
+ numCols,
+ keyColIdx,
+ allow_jit ? parent : NULL,
+ hash_iv);
+
/* build comparator for all columns */
/* XXX: should we support non-minimal tuples for the inputslot? */
hashtable->tab_eq_func = ExecBuildGroupingEqual(inputDesc, inputDesc,
@@ -316,7 +323,7 @@ LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
/* set up data needed by hash and match functions */
hashtable->inputslot = slot;
- hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
+ hashtable->in_hash_expr = hashtable->tab_hash_expr;
hashtable->cur_eq_func = hashtable->tab_eq_func;
local_hash = TupleHashTableHash_internal(hashtable->hashtab, NULL);
@@ -342,7 +349,7 @@ TupleHashTableHash(TupleHashTable hashtable, TupleTableSlot *slot)
uint32 hash;
hashtable->inputslot = slot;
- hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
+ hashtable->in_hash_expr = hashtable->tab_hash_expr;
/* Need to run the hash functions in short-lived context */
oldContext = MemoryContextSwitchTo(hashtable->tempcxt);
@@ -370,7 +377,7 @@ LookupTupleHashEntryHash(TupleHashTable hashtable, TupleTableSlot *slot,
/* set up data needed by hash and match functions */
hashtable->inputslot = slot;
- hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
+ hashtable->in_hash_expr = hashtable->tab_hash_expr;
hashtable->cur_eq_func = hashtable->tab_eq_func;
entry = LookupTupleHashEntry_internal(hashtable, slot, isnew, hash);
@@ -386,14 +393,14 @@ LookupTupleHashEntryHash(TupleHashTable hashtable, TupleTableSlot *slot,
* created if there's not a match. This is similar to the non-creating
* case of LookupTupleHashEntry, except that it supports cross-type
* comparisons, in which the given tuple is not of the same type as the
- * table entries. The caller must provide the hash functions to use for
- * the input tuple, as well as the equality functions, since these may be
+ * table entries. The caller must provide the hash ExprState to use for
+ * the input tuple, as well as the equality ExprState, since these may be
* different from the table's internal functions.
*/
TupleHashEntry
FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
ExprState *eqcomp,
- FmgrInfo *hashfunctions)
+ ExprState *hashexpr)
{
TupleHashEntry entry;
MemoryContext oldContext;
@@ -404,7 +411,7 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
/* Set up data needed by hash and match functions */
hashtable->inputslot = slot;
- hashtable->in_hash_funcs = hashfunctions;
+ hashtable->in_hash_expr = hashexpr;
hashtable->cur_eq_func = eqcomp;
/* Search the hash table */
@@ -421,25 +428,24 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
* copied into the table.
*
* Also, the caller must select an appropriate memory context for running
- * the hash functions. (dynahash.c doesn't change CurrentMemoryContext.)
+ * the hash functions.
*/
static uint32
TupleHashTableHash_internal(struct tuplehash_hash *tb,
const MinimalTuple tuple)
{
TupleHashTable hashtable = (TupleHashTable) tb->private_data;
- int numCols = hashtable->numCols;
- AttrNumber *keyColIdx = hashtable->keyColIdx;
- uint32 hashkey = hashtable->hash_iv;
+ uint32 hashkey;
TupleTableSlot *slot;
- FmgrInfo *hashfunctions;
- int i;
+ bool isnull;
if (tuple == NULL)
{
/* Process the current input tuple for the table */
- slot = hashtable->inputslot;
- hashfunctions = hashtable->in_hash_funcs;
+ hashtable->exprcontext->ecxt_innertuple = hashtable->inputslot;
+ hashkey = DatumGetUInt32(ExecEvalExpr(hashtable->in_hash_expr,
+ hashtable->exprcontext,
+ &isnull));
}
else
{
@@ -449,38 +455,23 @@ TupleHashTableHash_internal(struct tuplehash_hash *tb,
* (this case never actually occurs due to the way simplehash.h is
* used, as the hash-value is stored in the entries)
*/
- slot = hashtable->tableslot;
+ slot = hashtable->exprcontext->ecxt_innertuple = hashtable->tableslot;
ExecStoreMinimalTuple(tuple, slot, false);
- hashfunctions = hashtable->tab_hash_funcs;
+ hashkey = DatumGetUInt32(ExecEvalExpr(hashtable->tab_hash_expr,
+ hashtable->exprcontext,
+ &isnull));
}
- for (i = 0; i < numCols; i++)
- {
- AttrNumber att = keyColIdx[i];
- Datum attr;
- bool isNull;
-
- /* combine successive hashkeys by rotating */
- hashkey = pg_rotate_left32(hashkey, 1);
-
- attr = slot_getattr(slot, att, &isNull);
-
- if (!isNull) /* treat nulls as having hash key 0 */
- {
- uint32 hkey;
-
- hkey = DatumGetUInt32(FunctionCall1Coll(&hashfunctions[i],
- hashtable->tab_collations[i],
- attr));
- hashkey ^= hkey;
- }
- }
+#ifdef USE_ASSERT_CHECKING
+ /* XXX not for commit. */
+ elog(DEBUG1, "hashkey = %u", hashkey);
+#endif
/*
- * The way hashes are combined above, among each other and with the IV,
- * doesn't lead to good bit perturbation. As the IV's goal is to lead to
- * achieve that, perform a round of hashing of the combined hash -
- * resulting in near perfect perturbation.
+ * The way hashes are combined with the ExprState above, among each other
+ * and with the IV, doesn't lead to good bit perturbation. As the IV's
+ * goal is to lead to achieve that, perform a round of hashing of the
+ * combined hash - resulting in near perfect perturbation.
*/
return murmurhash32(hashkey);
}
diff --git a/src/backend/executor/nodeSubplan.c b/src/backend/executor/nodeSubplan.c
index a96cdd01e1..99d4d018af 100644
--- a/src/backend/executor/nodeSubplan.c
+++ b/src/backend/executor/nodeSubplan.c
@@ -160,7 +160,7 @@ ExecHashSubPlan(SubPlanState *node,
FindTupleHashEntry(node->hashtable,
slot,
node->cur_eq_comp,
- node->lhs_hash_funcs) != NULL)
+ node->lhs_hash_expr) != NULL)
{
ExecClearTuple(slot);
return BoolGetDatum(true);
@@ -858,7 +858,6 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
sstate->tab_hash_funcs = NULL;
sstate->tab_eq_funcs = NULL;
sstate->tab_collations = NULL;
- sstate->lhs_hash_funcs = NULL;
sstate->cur_eq_funcs = NULL;
/*
@@ -898,6 +897,7 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
TupleDesc tupDescRight;
Oid *cross_eq_funcoids;
TupleTableSlot *slot;
+ FmgrInfo *lhs_hash_funcs;
List *oplist,
*lefttlist,
*righttlist;
@@ -955,7 +955,7 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
sstate->tab_collations = (Oid *) palloc(ncols * sizeof(Oid));
sstate->tab_hash_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
sstate->tab_eq_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
- sstate->lhs_hash_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
+ lhs_hash_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
sstate->cur_eq_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
/* we'll need the cross-type equality fns below, but not in sstate */
cross_eq_funcoids = (Oid *) palloc(ncols * sizeof(Oid));
@@ -1007,7 +1007,7 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
&left_hashfn, &right_hashfn))
elog(ERROR, "could not find hash function for hash operator %u",
opexpr->opno);
- fmgr_info(left_hashfn, &sstate->lhs_hash_funcs[i - 1]);
+ fmgr_info(left_hashfn, &lhs_hash_funcs[i - 1]);
fmgr_info(right_hashfn, &sstate->tab_hash_funcs[i - 1]);
/* Set collation */
@@ -1043,6 +1043,15 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
sstate->planstate,
NULL);
+ sstate->lhs_hash_expr = ExecBuildHash32FromAttrs(tupDescLeft,
+ &TTSOpsVirtual,
+ lhs_hash_funcs,
+ sstate->tab_collations,
+ sstate->numCols,
+ sstate->keyColIdx,
+ parent,
+ 0);
+
/*
* Create comparator for lookups of rows in the table (potentially
* cross-type comparisons).
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index 69c3ebff00..e77377ff9b 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -160,7 +160,7 @@ extern TupleHashEntry LookupTupleHashEntryHash(TupleHashTable hashtable,
extern TupleHashEntry FindTupleHashEntry(TupleHashTable hashtable,
TupleTableSlot *slot,
ExprState *eqcomp,
- FmgrInfo *hashfunctions);
+ ExprState *hashexpr);
extern void ResetTupleHashTable(TupleHashTable hashtable);
/*
@@ -289,6 +289,14 @@ extern ExprState *ExecInitCheck(List *qual, PlanState *parent);
extern List *ExecInitExprList(List *nodes, PlanState *parent);
extern ExprState *ExecBuildAggTrans(AggState *aggstate, struct AggStatePerPhaseData *phase,
bool doSort, bool doHash, bool nullcheck);
+extern ExprState *ExecBuildHash32FromAttrs(TupleDesc desc,
+ const TupleTableSlotOps *ops,
+ FmgrInfo *hashfunctions,
+ Oid *collations,
+ int numCols,
+ AttrNumber *keyColIdx,
+ PlanState *parent,
+ uint32 init_value);
extern ExprState *ExecBuildHash32Expr(TupleDesc desc,
const TupleTableSlotOps *ops,
const Oid *hashfunc_oids,
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index b67d5186a2..1a801d183b 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -795,12 +795,12 @@ typedef struct ExecAuxRowMark
*
* All-in-memory tuple hash tables are used for a number of purposes.
*
- * Note: tab_hash_funcs are for the key datatype(s) stored in the table,
- * and tab_eq_funcs are non-cross-type equality operators for those types.
- * Normally these are the only functions used, but FindTupleHashEntry()
+ * Note: tab_hash_expr is for the key datatype(s) stored in the table,
+ * and tab_eq_func is for non-cross-type equality comparisons for those types.
+ * Normally these are the only ExprStates used, but FindTupleHashEntry()
* supports searching a hashtable using cross-data-type hashing. For that,
* the caller must supply hash functions for the LHS datatype as well as
- * the cross-type equality operators to use. in_hash_funcs and cur_eq_func
+ * the cross-type equality operators to use. in_hash_expr and cur_eq_func
* are set to point to the caller's function arrays while doing such a search.
* During LookupTupleHashEntry(), they point to tab_hash_funcs and
* tab_eq_func respectively.
@@ -830,7 +830,7 @@ typedef struct TupleHashTableData
tuplehash_hash *hashtab; /* underlying hash table */
int numCols; /* number of columns in lookup key */
AttrNumber *keyColIdx; /* attr numbers of key columns */
- FmgrInfo *tab_hash_funcs; /* hash functions for table datatype(s) */
+ ExprState *tab_hash_expr; /* ExprState for hashing table datatype(s) */
ExprState *tab_eq_func; /* comparator for table datatype(s) */
Oid *tab_collations; /* collations for hash and comparison */
MemoryContext tablecxt; /* memory context containing table */
@@ -839,9 +839,8 @@ typedef struct TupleHashTableData
TupleTableSlot *tableslot; /* slot for referencing table entries */
/* The following fields are set transiently for each table search: */
TupleTableSlot *inputslot; /* current input tuple's slot */
- FmgrInfo *in_hash_funcs; /* hash functions for input datatype(s) */
+ ExprState *in_hash_expr; /* ExprState for hashing input datatype(s) */
ExprState *cur_eq_func; /* comparator for input vs. table */
- uint32 hash_iv; /* hash-function IV */
ExprContext *exprcontext; /* expression context */
} TupleHashTableData;
@@ -995,7 +994,7 @@ typedef struct SubPlanState
Oid *tab_collations; /* collations for hash and comparison */
FmgrInfo *tab_hash_funcs; /* hash functions for table datatype(s) */
FmgrInfo *tab_eq_funcs; /* equality functions for table datatype(s) */
- FmgrInfo *lhs_hash_funcs; /* hash functions for lefthand datatype(s) */
+ ExprState *lhs_hash_expr; /* hash expr for lefthand datatype(s) */
FmgrInfo *cur_eq_funcs; /* equality functions for LHS vs. table */
ExprState *cur_eq_comp; /* equality comparator for LHS vs. table */
} SubPlanState;
--
2.34.1
On Tue, 29 Oct 2024 at 22:47, David Rowley <dgrowleyml@gmail.com> wrote:
I've attached an updated patch with a few other fixes. Whilr checking
this tonight, noticed that master does not use
SubPlanState.tab_eq_funcs for anything. I resisted removing that in
this patch. Perhaps a follow-on patch can remove that. I suspect it's
not been used for a long time now, but I didn't do the archaeology
work to find out.
3974bc319 removed the SubPlanState.tab_eq_funcs field, so here's a
rebased patch.
David
Attachments:
v3-0001-Use-ExprStates-for-hashing-in-GROUP-BY-and-SubPla.patchapplication/octet-stream; name=v3-0001-Use-ExprStates-for-hashing-in-GROUP-BY-and-SubPla.patchDownload
From 0e6be0b377c6653f5df84cc00097cd856b62277d Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Wed, 7 Aug 2024 16:56:48 +1200
Subject: [PATCH v3] Use ExprStates for hashing in GROUP BY and SubPlans
This speeds up obtaining hash values for GROUP BY and for hashed
SubPlan by using the ExprState support for hashing. This allows JIT
compilation for hash value.
---
src/backend/executor/execExpr.c | 149 ++++++++++++++++++++++++++++
src/backend/executor/execGrouping.c | 82 +++++++--------
src/backend/executor/nodeSubplan.c | 17 +++-
src/include/executor/executor.h | 10 +-
src/include/nodes/execnodes.h | 15 ++-
5 files changed, 212 insertions(+), 61 deletions(-)
diff --git a/src/backend/executor/execExpr.c b/src/backend/executor/execExpr.c
index 45954d979f..d3f88930b0 100644
--- a/src/backend/executor/execExpr.c
+++ b/src/backend/executor/execExpr.c
@@ -3971,6 +3971,155 @@ ExecBuildAggTransCall(ExprState *state, AggState *aggstate,
}
}
+/*
+ * Build an ExprState that calls the given hash function(s) on the attnums
+ * given by 'keyColIdx' . When numCols > 1, the hash values returned by each
+ * hash function are combined to produce a single hash value.
+ *
+ * desc: tuple descriptor for the to-be-hashed columns
+ * ops: TupleTableSlotOps for the TupleDesc
+ * hashfunctions: FmgrInfos for each hash function to call, one per numCols.
+ * These are used directly in the returned ExprState so must remain allocated.
+ * collations: collation to use when calling the hash function.
+ * numCols: array length of hashfunctions, collations and keyColIdx.
+ * parent: PlanState node that the resulting ExprState will be evaluated at
+ * init_value: Normally 0, but can be set to other values to seed the hash
+ * with some other value. Using non-zero is slightly less efficient but can
+ * be useful.
+ */
+ExprState *
+ExecBuildHash32FromAttrs(TupleDesc desc, const TupleTableSlotOps *ops,
+ FmgrInfo *hashfunctions, Oid *collations,
+ int numCols, AttrNumber *keyColIdx,
+ PlanState *parent, uint32 init_value)
+{
+ ExprState *state = makeNode(ExprState);
+ ExprEvalStep scratch = {0};
+ NullableDatum *iresult = NULL;
+ intptr_t opcode;
+ AttrNumber last_attnum = 0;
+
+ state->parent = parent;
+
+ /* find the highest attnum so we deform the tuple to that point */
+ for (int i = 0; i < numCols; i++)
+ last_attnum = Max(last_attnum, keyColIdx[i]);
+
+ scratch.opcode = EEOP_INNER_FETCHSOME;
+ scratch.d.fetch.last_var = last_attnum;
+ scratch.d.fetch.fixed = false;
+ scratch.d.fetch.kind = NULL;
+ scratch.d.fetch.known_desc = NULL;
+ if (ExecComputeSlotInfo(state, &scratch))
+ ExprEvalPushStep(state, &scratch);
+
+ if (init_value == 0)
+ {
+ /*
+ * No initial value, so we can assign the result of the hash function
+ * for the first hash_expr without having to concern ourselves with
+ * combining the result with any initial value.
+ */
+ opcode = EEOP_HASHDATUM_FIRST;
+ }
+ else
+ {
+ /* Set up operation to set the initial value. */
+ scratch.opcode = EEOP_HASHDATUM_SET_INITVAL;
+ scratch.d.hashdatum_initvalue.init_value = UInt32GetDatum(init_value);
+ scratch.resvalue = &state->resvalue;
+ scratch.resnull = &state->resnull;
+
+ ExprEvalPushStep(state, &scratch);
+
+ /*
+ * When using an initial value use the NEXT32 ops as the FIRST ops
+ * would overwrite the stored initial value.
+ */
+ opcode = EEOP_HASHDATUM_NEXT32;
+ }
+
+ /*
+ * When hashing more than 1 column or if we have an init value, we need
+ * somewhere to store the intermediate hash value so that it's available
+ * to be combined with the result of subsequent hashing.
+ */
+ if (numCols > 1 || init_value != 0)
+ iresult = palloc(sizeof(NullableDatum));
+
+ for (int i = 0; i < numCols; i++)
+ {
+ FmgrInfo *finfo;
+ FunctionCallInfo fcinfo;
+ Oid inputcollid = collations[i];
+ AttrNumber attnum = keyColIdx[i] - 1;
+
+ finfo = &hashfunctions[i];
+ fcinfo = palloc0(SizeForFunctionCallInfo(1));
+
+ /* Initialize function call parameter structure too */
+ InitFunctionCallInfoData(*fcinfo, finfo, 1, inputcollid, NULL, NULL);
+
+ /*
+ * Fetch inner Var for this attnum and store it in the 1st arg of the
+ * hash func.
+ */
+ scratch.opcode = EEOP_INNER_VAR;
+ scratch.resvalue = &fcinfo->args[0].value;
+ scratch.resnull = &fcinfo->args[0].isnull;
+ scratch.d.var.attnum = attnum;
+ scratch.d.var.vartype = TupleDescAttr(desc, attnum)->atttypid;
+
+ ExprEvalPushStep(state, &scratch);
+
+ /* Call the hash function */
+ scratch.opcode = opcode;
+
+ if (i == numCols - 1)
+ {
+ /*
+ * The result for hashing the final column is stored in the
+ * ExprState.
+ */
+ scratch.resvalue = &state->resvalue;
+ scratch.resnull = &state->resnull;
+ }
+ else
+ {
+ Assert(iresult != NULL);
+
+ /* intermediate values are stored in an intermediate result */
+ scratch.resvalue = &iresult->value;
+ scratch.resnull = &iresult->isnull;
+ }
+
+ /*
+ * NEXT32 opcodes need to look at the intermediate result. We might
+ * as well just set this for all ops. FIRSTs won't look at it.
+ */
+ scratch.d.hashdatum.iresult = iresult;
+
+ scratch.d.hashdatum.finfo = finfo;
+ scratch.d.hashdatum.fcinfo_data = fcinfo;
+ scratch.d.hashdatum.fn_addr = finfo->fn_addr;
+ scratch.d.hashdatum.jumpdone = -1;
+
+ ExprEvalPushStep(state, &scratch);
+
+ /* subsequent attnums must be combined with the previous */
+ opcode = EEOP_HASHDATUM_NEXT32;
+ }
+
+ scratch.resvalue = NULL;
+ scratch.resnull = NULL;
+ scratch.opcode = EEOP_DONE;
+ ExprEvalPushStep(state, &scratch);
+
+ ExecReadyExpr(state);
+
+ return state;
+}
+
/*
* Build an ExprState that calls the given hash function(s) on the given
* 'hash_exprs'. When multiple expressions are present, the hash values
diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c
index 774e4de882..73743847d6 100644
--- a/src/backend/executor/execGrouping.c
+++ b/src/backend/executor/execGrouping.c
@@ -169,6 +169,7 @@ BuildTupleHashTableExt(PlanState *parent,
Size hash_mem_limit;
MemoryContext oldcontext;
bool allow_jit;
+ uint32 hash_iv = 0;
Assert(nbuckets > 0);
@@ -183,14 +184,13 @@ BuildTupleHashTableExt(PlanState *parent,
hashtable->numCols = numCols;
hashtable->keyColIdx = keyColIdx;
- hashtable->tab_hash_funcs = hashfunctions;
hashtable->tab_collations = collations;
hashtable->tablecxt = tablecxt;
hashtable->tempcxt = tempcxt;
hashtable->entrysize = entrysize;
hashtable->tableslot = NULL; /* will be made on first lookup */
hashtable->inputslot = NULL;
- hashtable->in_hash_funcs = NULL;
+ hashtable->in_hash_expr = NULL;
hashtable->cur_eq_func = NULL;
/*
@@ -202,9 +202,7 @@ BuildTupleHashTableExt(PlanState *parent,
* underestimated.
*/
if (use_variable_hash_iv)
- hashtable->hash_iv = murmurhash32(ParallelWorkerNumber);
- else
- hashtable->hash_iv = 0;
+ hash_iv = murmurhash32(ParallelWorkerNumber);
hashtable->hashtab = tuplehash_create(metacxt, nbuckets, hashtable);
@@ -225,6 +223,15 @@ BuildTupleHashTableExt(PlanState *parent,
*/
allow_jit = metacxt != tablecxt;
+ hashtable->tab_hash_expr = ExecBuildHash32FromAttrs(inputDesc,
+ &TTSOpsMinimalTuple,
+ hashfunctions,
+ collations,
+ numCols,
+ keyColIdx,
+ allow_jit ? parent : NULL,
+ hash_iv);
+
/* build comparator for all columns */
/* XXX: should we support non-minimal tuples for the inputslot? */
hashtable->tab_eq_func = ExecBuildGroupingEqual(inputDesc, inputDesc,
@@ -316,7 +323,7 @@ LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
/* set up data needed by hash and match functions */
hashtable->inputslot = slot;
- hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
+ hashtable->in_hash_expr = hashtable->tab_hash_expr;
hashtable->cur_eq_func = hashtable->tab_eq_func;
local_hash = TupleHashTableHash_internal(hashtable->hashtab, NULL);
@@ -342,7 +349,7 @@ TupleHashTableHash(TupleHashTable hashtable, TupleTableSlot *slot)
uint32 hash;
hashtable->inputslot = slot;
- hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
+ hashtable->in_hash_expr = hashtable->tab_hash_expr;
/* Need to run the hash functions in short-lived context */
oldContext = MemoryContextSwitchTo(hashtable->tempcxt);
@@ -370,7 +377,7 @@ LookupTupleHashEntryHash(TupleHashTable hashtable, TupleTableSlot *slot,
/* set up data needed by hash and match functions */
hashtable->inputslot = slot;
- hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
+ hashtable->in_hash_expr = hashtable->tab_hash_expr;
hashtable->cur_eq_func = hashtable->tab_eq_func;
entry = LookupTupleHashEntry_internal(hashtable, slot, isnew, hash);
@@ -386,14 +393,14 @@ LookupTupleHashEntryHash(TupleHashTable hashtable, TupleTableSlot *slot,
* created if there's not a match. This is similar to the non-creating
* case of LookupTupleHashEntry, except that it supports cross-type
* comparisons, in which the given tuple is not of the same type as the
- * table entries. The caller must provide the hash functions to use for
- * the input tuple, as well as the equality functions, since these may be
+ * table entries. The caller must provide the hash ExprState to use for
+ * the input tuple, as well as the equality ExprState, since these may be
* different from the table's internal functions.
*/
TupleHashEntry
FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
ExprState *eqcomp,
- FmgrInfo *hashfunctions)
+ ExprState *hashexpr)
{
TupleHashEntry entry;
MemoryContext oldContext;
@@ -404,7 +411,7 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
/* Set up data needed by hash and match functions */
hashtable->inputslot = slot;
- hashtable->in_hash_funcs = hashfunctions;
+ hashtable->in_hash_expr = hashexpr;
hashtable->cur_eq_func = eqcomp;
/* Search the hash table */
@@ -421,25 +428,24 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
* copied into the table.
*
* Also, the caller must select an appropriate memory context for running
- * the hash functions. (dynahash.c doesn't change CurrentMemoryContext.)
+ * the hash functions.
*/
static uint32
TupleHashTableHash_internal(struct tuplehash_hash *tb,
const MinimalTuple tuple)
{
TupleHashTable hashtable = (TupleHashTable) tb->private_data;
- int numCols = hashtable->numCols;
- AttrNumber *keyColIdx = hashtable->keyColIdx;
- uint32 hashkey = hashtable->hash_iv;
+ uint32 hashkey;
TupleTableSlot *slot;
- FmgrInfo *hashfunctions;
- int i;
+ bool isnull;
if (tuple == NULL)
{
/* Process the current input tuple for the table */
- slot = hashtable->inputslot;
- hashfunctions = hashtable->in_hash_funcs;
+ hashtable->exprcontext->ecxt_innertuple = hashtable->inputslot;
+ hashkey = DatumGetUInt32(ExecEvalExpr(hashtable->in_hash_expr,
+ hashtable->exprcontext,
+ &isnull));
}
else
{
@@ -449,38 +455,18 @@ TupleHashTableHash_internal(struct tuplehash_hash *tb,
* (this case never actually occurs due to the way simplehash.h is
* used, as the hash-value is stored in the entries)
*/
- slot = hashtable->tableslot;
+ slot = hashtable->exprcontext->ecxt_innertuple = hashtable->tableslot;
ExecStoreMinimalTuple(tuple, slot, false);
- hashfunctions = hashtable->tab_hash_funcs;
- }
-
- for (i = 0; i < numCols; i++)
- {
- AttrNumber att = keyColIdx[i];
- Datum attr;
- bool isNull;
-
- /* combine successive hashkeys by rotating */
- hashkey = pg_rotate_left32(hashkey, 1);
-
- attr = slot_getattr(slot, att, &isNull);
-
- if (!isNull) /* treat nulls as having hash key 0 */
- {
- uint32 hkey;
-
- hkey = DatumGetUInt32(FunctionCall1Coll(&hashfunctions[i],
- hashtable->tab_collations[i],
- attr));
- hashkey ^= hkey;
- }
+ hashkey = DatumGetUInt32(ExecEvalExpr(hashtable->tab_hash_expr,
+ hashtable->exprcontext,
+ &isnull));
}
/*
- * The way hashes are combined above, among each other and with the IV,
- * doesn't lead to good bit perturbation. As the IV's goal is to lead to
- * achieve that, perform a round of hashing of the combined hash -
- * resulting in near perfect perturbation.
+ * The way hashes are combined with the ExprState above, among each other
+ * and with the IV, doesn't lead to good bit perturbation. As the IV's
+ * goal is to lead to achieve that, perform a round of hashing of the
+ * combined hash - resulting in near perfect perturbation.
*/
return murmurhash32(hashkey);
}
diff --git a/src/backend/executor/nodeSubplan.c b/src/backend/executor/nodeSubplan.c
index 236222d72a..40bae49267 100644
--- a/src/backend/executor/nodeSubplan.c
+++ b/src/backend/executor/nodeSubplan.c
@@ -160,7 +160,7 @@ ExecHashSubPlan(SubPlanState *node,
FindTupleHashEntry(node->hashtable,
slot,
node->cur_eq_comp,
- node->lhs_hash_funcs) != NULL)
+ node->lhs_hash_expr) != NULL)
{
ExecClearTuple(slot);
return BoolGetDatum(true);
@@ -857,7 +857,6 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
sstate->tab_eq_funcoids = NULL;
sstate->tab_hash_funcs = NULL;
sstate->tab_collations = NULL;
- sstate->lhs_hash_funcs = NULL;
sstate->cur_eq_funcs = NULL;
/*
@@ -897,6 +896,7 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
TupleDesc tupDescRight;
Oid *cross_eq_funcoids;
TupleTableSlot *slot;
+ FmgrInfo *lhs_hash_funcs;
List *oplist,
*lefttlist,
*righttlist;
@@ -953,7 +953,7 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
sstate->tab_eq_funcoids = (Oid *) palloc(ncols * sizeof(Oid));
sstate->tab_collations = (Oid *) palloc(ncols * sizeof(Oid));
sstate->tab_hash_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
- sstate->lhs_hash_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
+ lhs_hash_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
sstate->cur_eq_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
/* we'll need the cross-type equality fns below, but not in sstate */
cross_eq_funcoids = (Oid *) palloc(ncols * sizeof(Oid));
@@ -1003,7 +1003,7 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
&left_hashfn, &right_hashfn))
elog(ERROR, "could not find hash function for hash operator %u",
opexpr->opno);
- fmgr_info(left_hashfn, &sstate->lhs_hash_funcs[i - 1]);
+ fmgr_info(left_hashfn, &lhs_hash_funcs[i - 1]);
fmgr_info(right_hashfn, &sstate->tab_hash_funcs[i - 1]);
/* Set collation */
@@ -1039,6 +1039,15 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
sstate->planstate,
NULL);
+ sstate->lhs_hash_expr = ExecBuildHash32FromAttrs(tupDescLeft,
+ &TTSOpsVirtual,
+ lhs_hash_funcs,
+ sstate->tab_collations,
+ sstate->numCols,
+ sstate->keyColIdx,
+ parent,
+ 0);
+
/*
* Create comparator for lookups of rows in the table (potentially
* cross-type comparisons).
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index 69c3ebff00..e77377ff9b 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -160,7 +160,7 @@ extern TupleHashEntry LookupTupleHashEntryHash(TupleHashTable hashtable,
extern TupleHashEntry FindTupleHashEntry(TupleHashTable hashtable,
TupleTableSlot *slot,
ExprState *eqcomp,
- FmgrInfo *hashfunctions);
+ ExprState *hashexpr);
extern void ResetTupleHashTable(TupleHashTable hashtable);
/*
@@ -289,6 +289,14 @@ extern ExprState *ExecInitCheck(List *qual, PlanState *parent);
extern List *ExecInitExprList(List *nodes, PlanState *parent);
extern ExprState *ExecBuildAggTrans(AggState *aggstate, struct AggStatePerPhaseData *phase,
bool doSort, bool doHash, bool nullcheck);
+extern ExprState *ExecBuildHash32FromAttrs(TupleDesc desc,
+ const TupleTableSlotOps *ops,
+ FmgrInfo *hashfunctions,
+ Oid *collations,
+ int numCols,
+ AttrNumber *keyColIdx,
+ PlanState *parent,
+ uint32 init_value);
extern ExprState *ExecBuildHash32Expr(TupleDesc desc,
const TupleTableSlotOps *ops,
const Oid *hashfunc_oids,
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 182a6956bb..616f7bf270 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -795,14 +795,14 @@ typedef struct ExecAuxRowMark
*
* All-in-memory tuple hash tables are used for a number of purposes.
*
- * Note: tab_hash_funcs are for the key datatype(s) stored in the table,
+ * Note: tab_hash_expr are for the key datatype(s) stored in the table,
* and tab_eq_func are non-cross-type equality operators for those types.
- * Normally these are the only functions used, but FindTupleHashEntry()
+ * Normally these are the only ExprStates used, but FindTupleHashEntry()
* supports searching a hashtable using cross-data-type hashing. For that,
* the caller must supply hash functions for the LHS datatype as well as
- * the cross-type equality operators to use. in_hash_funcs and cur_eq_func
+ * the cross-type equality operators to use. in_hash_expr and cur_eq_func
* are set to point to the caller's function arrays while doing such a search.
- * During LookupTupleHashEntry(), they point to tab_hash_funcs and
+ * During LookupTupleHashEntry(), they point to tab_hash_expr and
* tab_eq_func respectively.
* ----------------------------------------------------------------
*/
@@ -830,7 +830,7 @@ typedef struct TupleHashTableData
tuplehash_hash *hashtab; /* underlying hash table */
int numCols; /* number of columns in lookup key */
AttrNumber *keyColIdx; /* attr numbers of key columns */
- FmgrInfo *tab_hash_funcs; /* hash functions for table datatype(s) */
+ ExprState *tab_hash_expr; /* ExprState for hashing table datatype(s) */
ExprState *tab_eq_func; /* comparator for table datatype(s) */
Oid *tab_collations; /* collations for hash and comparison */
MemoryContext tablecxt; /* memory context containing table */
@@ -839,9 +839,8 @@ typedef struct TupleHashTableData
TupleTableSlot *tableslot; /* slot for referencing table entries */
/* The following fields are set transiently for each table search: */
TupleTableSlot *inputslot; /* current input tuple's slot */
- FmgrInfo *in_hash_funcs; /* hash functions for input datatype(s) */
+ ExprState *in_hash_expr; /* ExprState for hashing input datatype(s) */
ExprState *cur_eq_func; /* comparator for input vs. table */
- uint32 hash_iv; /* hash-function IV */
ExprContext *exprcontext; /* expression context */
} TupleHashTableData;
@@ -994,7 +993,7 @@ typedef struct SubPlanState
* datatype(s) */
Oid *tab_collations; /* collations for hash and comparison */
FmgrInfo *tab_hash_funcs; /* hash functions for table datatype(s) */
- FmgrInfo *lhs_hash_funcs; /* hash functions for lefthand datatype(s) */
+ ExprState *lhs_hash_expr; /* hash expr for lefthand datatype(s) */
FmgrInfo *cur_eq_funcs; /* equality functions for LHS vs. table */
ExprState *cur_eq_comp; /* equality comparator for LHS vs. table */
} SubPlanState;
--
2.34.1
On 10/31/24 08:16, David Rowley wrote:
On Tue, 29 Oct 2024 at 22:47, David Rowley <dgrowleyml@gmail.com> wrote:
I've attached an updated patch with a few other fixes. Whilr checking
this tonight, noticed that master does not use
SubPlanState.tab_eq_funcs for anything. I resisted removing that in
this patch. Perhaps a follow-on patch can remove that. I suspect it's
not been used for a long time now, but I didn't do the archaeology
work to find out.3974bc319 removed the SubPlanState.tab_eq_funcs field, so here's a
rebased patch.
Thanks for sharing this.
I still need to dive deeply into the code. But I have one annoying user
case where the user complained about a 4x SQL server speedup in
comparison to Postgres, and I guess it is a good benchmark for your code.
This query is remarkable because of high grouping computation load. Of
course, I can't provide the user's data, but I have prepared a synthetic
test to reproduce the case (see attachment).
Comparing the master with and without your patch, the first, I see is
more extensive usage of memory (see complete explains in the attachment):
Current master:
---------------
Partial HashAggregate (cost=54492.60..55588.03 rows=19917 width=889)
(actual time=20621.028..20642.664 rows=10176 loops=9)
Group Key: t1.x1, t1.x2, t1.x3, t1.x4, t1.x5
Batches: 1 Memory Usage: 74513kB
Patched:
--------
Partial HashAggregate (cost=54699.91..55799.69 rows=19996 width=889)
(actual time=57213.280..186216.604 rows=10302738 loops=9)
Group Key: t1.x1, t1.x2, t1.x3, t1.x4, t1.x5
Batches: 261 Memory Usage: 527905kB Disk Usage: 4832656kB
I wonder what causes memory consumption, but it is hard to decide on the
patch's positive outcome for now.
--
regards, Andrei Lepikhov
On Thu, 31 Oct 2024 at 15:30, Andrei Lepikhov <lepihov@gmail.com> wrote:
Comparing the master with and without your patch, the first, I see is
more extensive usage of memory (see complete explains in the attachment):Current master:
Batches: 1 Memory Usage: 74513kB
Patched:
Batches: 261 Memory Usage: 527905kB Disk Usage: 4832656kB
Thanks for testing that. I had forgotten to adjust the storage
location for the hash initial value when I rebased the patch against
the changes made in 9ca67658d. I've fixed that in the attached patch.
The patched version comes out faster for me now:
master: Execution Time: 15515.401 ms
v4 patch: Execution Time: 15024.395 ms
David
Attachments:
v4-0001-Use-ExprStates-for-hashing-in-GROUP-BY-and-SubPla.patchapplication/octet-stream; name=v4-0001-Use-ExprStates-for-hashing-in-GROUP-BY-and-SubPla.patchDownload
From 066320bc566140122bc8e9b0aca1bd7b08236515 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Wed, 7 Aug 2024 16:56:48 +1200
Subject: [PATCH v4] Use ExprStates for hashing in GROUP BY and SubPlans
This speeds up obtaining hash values for GROUP BY and for hashed
SubPlan by using the ExprState support for hashing. This allows JIT
compilation for hash value.
---
src/backend/executor/execExpr.c | 149 ++++++++++++++++++++++++++++
src/backend/executor/execGrouping.c | 82 +++++++--------
src/backend/executor/nodeSubplan.c | 17 +++-
src/include/executor/executor.h | 10 +-
src/include/nodes/execnodes.h | 15 ++-
5 files changed, 212 insertions(+), 61 deletions(-)
diff --git a/src/backend/executor/execExpr.c b/src/backend/executor/execExpr.c
index 45954d979f..e9cc9935fc 100644
--- a/src/backend/executor/execExpr.c
+++ b/src/backend/executor/execExpr.c
@@ -3971,6 +3971,155 @@ ExecBuildAggTransCall(ExprState *state, AggState *aggstate,
}
}
+/*
+ * Build an ExprState that calls the given hash function(s) on the attnums
+ * given by 'keyColIdx' . When numCols > 1, the hash values returned by each
+ * hash function are combined to produce a single hash value.
+ *
+ * desc: tuple descriptor for the to-be-hashed columns
+ * ops: TupleTableSlotOps for the TupleDesc
+ * hashfunctions: FmgrInfos for each hash function to call, one per numCols.
+ * These are used directly in the returned ExprState so must remain allocated.
+ * collations: collation to use when calling the hash function.
+ * numCols: array length of hashfunctions, collations and keyColIdx.
+ * parent: PlanState node that the resulting ExprState will be evaluated at
+ * init_value: Normally 0, but can be set to other values to seed the hash
+ * with some other value. Using non-zero is slightly less efficient but can
+ * be useful.
+ */
+ExprState *
+ExecBuildHash32FromAttrs(TupleDesc desc, const TupleTableSlotOps *ops,
+ FmgrInfo *hashfunctions, Oid *collations,
+ int numCols, AttrNumber *keyColIdx,
+ PlanState *parent, uint32 init_value)
+{
+ ExprState *state = makeNode(ExprState);
+ ExprEvalStep scratch = {0};
+ NullableDatum *iresult = NULL;
+ intptr_t opcode;
+ AttrNumber last_attnum = 0;
+
+ state->parent = parent;
+
+ /*
+ * When hashing more than 1 column or if we have an init value, we need
+ * somewhere to store the intermediate hash value so that it's available
+ * to be combined with the result of subsequent hashing.
+ */
+ if (numCols > 1 || init_value != 0)
+ iresult = palloc(sizeof(NullableDatum));
+
+ /* find the highest attnum so we deform the tuple to that point */
+ for (int i = 0; i < numCols; i++)
+ last_attnum = Max(last_attnum, keyColIdx[i]);
+
+ scratch.opcode = EEOP_INNER_FETCHSOME;
+ scratch.d.fetch.last_var = last_attnum;
+ scratch.d.fetch.fixed = false;
+ scratch.d.fetch.kind = NULL;
+ scratch.d.fetch.known_desc = NULL;
+ if (ExecComputeSlotInfo(state, &scratch))
+ ExprEvalPushStep(state, &scratch);
+
+ if (init_value == 0)
+ {
+ /*
+ * No initial value, so we can assign the result of the hash function
+ * for the first hash_expr without having to concern ourselves with
+ * combining the result with any initial value.
+ */
+ opcode = EEOP_HASHDATUM_FIRST;
+ }
+ else
+ {
+ /* Set up operation to set the initial value. */
+ scratch.opcode = EEOP_HASHDATUM_SET_INITVAL;
+ scratch.d.hashdatum_initvalue.init_value = UInt32GetDatum(init_value);
+ scratch.resvalue = &iresult->value;
+ scratch.resnull = &iresult->isnull;
+
+ ExprEvalPushStep(state, &scratch);
+
+ /*
+ * When using an initial value use the NEXT32 ops as the FIRST ops
+ * would overwrite the stored initial value.
+ */
+ opcode = EEOP_HASHDATUM_NEXT32;
+ }
+
+ for (int i = 0; i < numCols; i++)
+ {
+ FmgrInfo *finfo;
+ FunctionCallInfo fcinfo;
+ Oid inputcollid = collations[i];
+ AttrNumber attnum = keyColIdx[i] - 1;
+
+ finfo = &hashfunctions[i];
+ fcinfo = palloc0(SizeForFunctionCallInfo(1));
+
+ /* Initialize function call parameter structure too */
+ InitFunctionCallInfoData(*fcinfo, finfo, 1, inputcollid, NULL, NULL);
+
+ /*
+ * Fetch inner Var for this attnum and store it in the 1st arg of the
+ * hash func.
+ */
+ scratch.opcode = EEOP_INNER_VAR;
+ scratch.resvalue = &fcinfo->args[0].value;
+ scratch.resnull = &fcinfo->args[0].isnull;
+ scratch.d.var.attnum = attnum;
+ scratch.d.var.vartype = TupleDescAttr(desc, attnum)->atttypid;
+
+ ExprEvalPushStep(state, &scratch);
+
+ /* Call the hash function */
+ scratch.opcode = opcode;
+
+ if (i == numCols - 1)
+ {
+ /*
+ * The result for hashing the final column is stored in the
+ * ExprState.
+ */
+ scratch.resvalue = &state->resvalue;
+ scratch.resnull = &state->resnull;
+ }
+ else
+ {
+ Assert(iresult != NULL);
+
+ /* intermediate values are stored in an intermediate result */
+ scratch.resvalue = &iresult->value;
+ scratch.resnull = &iresult->isnull;
+ }
+
+ /*
+ * NEXT32 opcodes need to look at the intermediate result. We might
+ * as well just set this for all ops. FIRSTs won't look at it.
+ */
+ scratch.d.hashdatum.iresult = iresult;
+
+ scratch.d.hashdatum.finfo = finfo;
+ scratch.d.hashdatum.fcinfo_data = fcinfo;
+ scratch.d.hashdatum.fn_addr = finfo->fn_addr;
+ scratch.d.hashdatum.jumpdone = -1;
+
+ ExprEvalPushStep(state, &scratch);
+
+ /* subsequent attnums must be combined with the previous */
+ opcode = EEOP_HASHDATUM_NEXT32;
+ }
+
+ scratch.resvalue = NULL;
+ scratch.resnull = NULL;
+ scratch.opcode = EEOP_DONE;
+ ExprEvalPushStep(state, &scratch);
+
+ ExecReadyExpr(state);
+
+ return state;
+}
+
/*
* Build an ExprState that calls the given hash function(s) on the given
* 'hash_exprs'. When multiple expressions are present, the hash values
diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c
index 774e4de882..73743847d6 100644
--- a/src/backend/executor/execGrouping.c
+++ b/src/backend/executor/execGrouping.c
@@ -169,6 +169,7 @@ BuildTupleHashTableExt(PlanState *parent,
Size hash_mem_limit;
MemoryContext oldcontext;
bool allow_jit;
+ uint32 hash_iv = 0;
Assert(nbuckets > 0);
@@ -183,14 +184,13 @@ BuildTupleHashTableExt(PlanState *parent,
hashtable->numCols = numCols;
hashtable->keyColIdx = keyColIdx;
- hashtable->tab_hash_funcs = hashfunctions;
hashtable->tab_collations = collations;
hashtable->tablecxt = tablecxt;
hashtable->tempcxt = tempcxt;
hashtable->entrysize = entrysize;
hashtable->tableslot = NULL; /* will be made on first lookup */
hashtable->inputslot = NULL;
- hashtable->in_hash_funcs = NULL;
+ hashtable->in_hash_expr = NULL;
hashtable->cur_eq_func = NULL;
/*
@@ -202,9 +202,7 @@ BuildTupleHashTableExt(PlanState *parent,
* underestimated.
*/
if (use_variable_hash_iv)
- hashtable->hash_iv = murmurhash32(ParallelWorkerNumber);
- else
- hashtable->hash_iv = 0;
+ hash_iv = murmurhash32(ParallelWorkerNumber);
hashtable->hashtab = tuplehash_create(metacxt, nbuckets, hashtable);
@@ -225,6 +223,15 @@ BuildTupleHashTableExt(PlanState *parent,
*/
allow_jit = metacxt != tablecxt;
+ hashtable->tab_hash_expr = ExecBuildHash32FromAttrs(inputDesc,
+ &TTSOpsMinimalTuple,
+ hashfunctions,
+ collations,
+ numCols,
+ keyColIdx,
+ allow_jit ? parent : NULL,
+ hash_iv);
+
/* build comparator for all columns */
/* XXX: should we support non-minimal tuples for the inputslot? */
hashtable->tab_eq_func = ExecBuildGroupingEqual(inputDesc, inputDesc,
@@ -316,7 +323,7 @@ LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
/* set up data needed by hash and match functions */
hashtable->inputslot = slot;
- hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
+ hashtable->in_hash_expr = hashtable->tab_hash_expr;
hashtable->cur_eq_func = hashtable->tab_eq_func;
local_hash = TupleHashTableHash_internal(hashtable->hashtab, NULL);
@@ -342,7 +349,7 @@ TupleHashTableHash(TupleHashTable hashtable, TupleTableSlot *slot)
uint32 hash;
hashtable->inputslot = slot;
- hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
+ hashtable->in_hash_expr = hashtable->tab_hash_expr;
/* Need to run the hash functions in short-lived context */
oldContext = MemoryContextSwitchTo(hashtable->tempcxt);
@@ -370,7 +377,7 @@ LookupTupleHashEntryHash(TupleHashTable hashtable, TupleTableSlot *slot,
/* set up data needed by hash and match functions */
hashtable->inputslot = slot;
- hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
+ hashtable->in_hash_expr = hashtable->tab_hash_expr;
hashtable->cur_eq_func = hashtable->tab_eq_func;
entry = LookupTupleHashEntry_internal(hashtable, slot, isnew, hash);
@@ -386,14 +393,14 @@ LookupTupleHashEntryHash(TupleHashTable hashtable, TupleTableSlot *slot,
* created if there's not a match. This is similar to the non-creating
* case of LookupTupleHashEntry, except that it supports cross-type
* comparisons, in which the given tuple is not of the same type as the
- * table entries. The caller must provide the hash functions to use for
- * the input tuple, as well as the equality functions, since these may be
+ * table entries. The caller must provide the hash ExprState to use for
+ * the input tuple, as well as the equality ExprState, since these may be
* different from the table's internal functions.
*/
TupleHashEntry
FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
ExprState *eqcomp,
- FmgrInfo *hashfunctions)
+ ExprState *hashexpr)
{
TupleHashEntry entry;
MemoryContext oldContext;
@@ -404,7 +411,7 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
/* Set up data needed by hash and match functions */
hashtable->inputslot = slot;
- hashtable->in_hash_funcs = hashfunctions;
+ hashtable->in_hash_expr = hashexpr;
hashtable->cur_eq_func = eqcomp;
/* Search the hash table */
@@ -421,25 +428,24 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
* copied into the table.
*
* Also, the caller must select an appropriate memory context for running
- * the hash functions. (dynahash.c doesn't change CurrentMemoryContext.)
+ * the hash functions.
*/
static uint32
TupleHashTableHash_internal(struct tuplehash_hash *tb,
const MinimalTuple tuple)
{
TupleHashTable hashtable = (TupleHashTable) tb->private_data;
- int numCols = hashtable->numCols;
- AttrNumber *keyColIdx = hashtable->keyColIdx;
- uint32 hashkey = hashtable->hash_iv;
+ uint32 hashkey;
TupleTableSlot *slot;
- FmgrInfo *hashfunctions;
- int i;
+ bool isnull;
if (tuple == NULL)
{
/* Process the current input tuple for the table */
- slot = hashtable->inputslot;
- hashfunctions = hashtable->in_hash_funcs;
+ hashtable->exprcontext->ecxt_innertuple = hashtable->inputslot;
+ hashkey = DatumGetUInt32(ExecEvalExpr(hashtable->in_hash_expr,
+ hashtable->exprcontext,
+ &isnull));
}
else
{
@@ -449,38 +455,18 @@ TupleHashTableHash_internal(struct tuplehash_hash *tb,
* (this case never actually occurs due to the way simplehash.h is
* used, as the hash-value is stored in the entries)
*/
- slot = hashtable->tableslot;
+ slot = hashtable->exprcontext->ecxt_innertuple = hashtable->tableslot;
ExecStoreMinimalTuple(tuple, slot, false);
- hashfunctions = hashtable->tab_hash_funcs;
- }
-
- for (i = 0; i < numCols; i++)
- {
- AttrNumber att = keyColIdx[i];
- Datum attr;
- bool isNull;
-
- /* combine successive hashkeys by rotating */
- hashkey = pg_rotate_left32(hashkey, 1);
-
- attr = slot_getattr(slot, att, &isNull);
-
- if (!isNull) /* treat nulls as having hash key 0 */
- {
- uint32 hkey;
-
- hkey = DatumGetUInt32(FunctionCall1Coll(&hashfunctions[i],
- hashtable->tab_collations[i],
- attr));
- hashkey ^= hkey;
- }
+ hashkey = DatumGetUInt32(ExecEvalExpr(hashtable->tab_hash_expr,
+ hashtable->exprcontext,
+ &isnull));
}
/*
- * The way hashes are combined above, among each other and with the IV,
- * doesn't lead to good bit perturbation. As the IV's goal is to lead to
- * achieve that, perform a round of hashing of the combined hash -
- * resulting in near perfect perturbation.
+ * The way hashes are combined with the ExprState above, among each other
+ * and with the IV, doesn't lead to good bit perturbation. As the IV's
+ * goal is to lead to achieve that, perform a round of hashing of the
+ * combined hash - resulting in near perfect perturbation.
*/
return murmurhash32(hashkey);
}
diff --git a/src/backend/executor/nodeSubplan.c b/src/backend/executor/nodeSubplan.c
index 236222d72a..40bae49267 100644
--- a/src/backend/executor/nodeSubplan.c
+++ b/src/backend/executor/nodeSubplan.c
@@ -160,7 +160,7 @@ ExecHashSubPlan(SubPlanState *node,
FindTupleHashEntry(node->hashtable,
slot,
node->cur_eq_comp,
- node->lhs_hash_funcs) != NULL)
+ node->lhs_hash_expr) != NULL)
{
ExecClearTuple(slot);
return BoolGetDatum(true);
@@ -857,7 +857,6 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
sstate->tab_eq_funcoids = NULL;
sstate->tab_hash_funcs = NULL;
sstate->tab_collations = NULL;
- sstate->lhs_hash_funcs = NULL;
sstate->cur_eq_funcs = NULL;
/*
@@ -897,6 +896,7 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
TupleDesc tupDescRight;
Oid *cross_eq_funcoids;
TupleTableSlot *slot;
+ FmgrInfo *lhs_hash_funcs;
List *oplist,
*lefttlist,
*righttlist;
@@ -953,7 +953,7 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
sstate->tab_eq_funcoids = (Oid *) palloc(ncols * sizeof(Oid));
sstate->tab_collations = (Oid *) palloc(ncols * sizeof(Oid));
sstate->tab_hash_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
- sstate->lhs_hash_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
+ lhs_hash_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
sstate->cur_eq_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
/* we'll need the cross-type equality fns below, but not in sstate */
cross_eq_funcoids = (Oid *) palloc(ncols * sizeof(Oid));
@@ -1003,7 +1003,7 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
&left_hashfn, &right_hashfn))
elog(ERROR, "could not find hash function for hash operator %u",
opexpr->opno);
- fmgr_info(left_hashfn, &sstate->lhs_hash_funcs[i - 1]);
+ fmgr_info(left_hashfn, &lhs_hash_funcs[i - 1]);
fmgr_info(right_hashfn, &sstate->tab_hash_funcs[i - 1]);
/* Set collation */
@@ -1039,6 +1039,15 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
sstate->planstate,
NULL);
+ sstate->lhs_hash_expr = ExecBuildHash32FromAttrs(tupDescLeft,
+ &TTSOpsVirtual,
+ lhs_hash_funcs,
+ sstate->tab_collations,
+ sstate->numCols,
+ sstate->keyColIdx,
+ parent,
+ 0);
+
/*
* Create comparator for lookups of rows in the table (potentially
* cross-type comparisons).
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index 69c3ebff00..e77377ff9b 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -160,7 +160,7 @@ extern TupleHashEntry LookupTupleHashEntryHash(TupleHashTable hashtable,
extern TupleHashEntry FindTupleHashEntry(TupleHashTable hashtable,
TupleTableSlot *slot,
ExprState *eqcomp,
- FmgrInfo *hashfunctions);
+ ExprState *hashexpr);
extern void ResetTupleHashTable(TupleHashTable hashtable);
/*
@@ -289,6 +289,14 @@ extern ExprState *ExecInitCheck(List *qual, PlanState *parent);
extern List *ExecInitExprList(List *nodes, PlanState *parent);
extern ExprState *ExecBuildAggTrans(AggState *aggstate, struct AggStatePerPhaseData *phase,
bool doSort, bool doHash, bool nullcheck);
+extern ExprState *ExecBuildHash32FromAttrs(TupleDesc desc,
+ const TupleTableSlotOps *ops,
+ FmgrInfo *hashfunctions,
+ Oid *collations,
+ int numCols,
+ AttrNumber *keyColIdx,
+ PlanState *parent,
+ uint32 init_value);
extern ExprState *ExecBuildHash32Expr(TupleDesc desc,
const TupleTableSlotOps *ops,
const Oid *hashfunc_oids,
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 182a6956bb..616f7bf270 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -795,14 +795,14 @@ typedef struct ExecAuxRowMark
*
* All-in-memory tuple hash tables are used for a number of purposes.
*
- * Note: tab_hash_funcs are for the key datatype(s) stored in the table,
+ * Note: tab_hash_expr are for the key datatype(s) stored in the table,
* and tab_eq_func are non-cross-type equality operators for those types.
- * Normally these are the only functions used, but FindTupleHashEntry()
+ * Normally these are the only ExprStates used, but FindTupleHashEntry()
* supports searching a hashtable using cross-data-type hashing. For that,
* the caller must supply hash functions for the LHS datatype as well as
- * the cross-type equality operators to use. in_hash_funcs and cur_eq_func
+ * the cross-type equality operators to use. in_hash_expr and cur_eq_func
* are set to point to the caller's function arrays while doing such a search.
- * During LookupTupleHashEntry(), they point to tab_hash_funcs and
+ * During LookupTupleHashEntry(), they point to tab_hash_expr and
* tab_eq_func respectively.
* ----------------------------------------------------------------
*/
@@ -830,7 +830,7 @@ typedef struct TupleHashTableData
tuplehash_hash *hashtab; /* underlying hash table */
int numCols; /* number of columns in lookup key */
AttrNumber *keyColIdx; /* attr numbers of key columns */
- FmgrInfo *tab_hash_funcs; /* hash functions for table datatype(s) */
+ ExprState *tab_hash_expr; /* ExprState for hashing table datatype(s) */
ExprState *tab_eq_func; /* comparator for table datatype(s) */
Oid *tab_collations; /* collations for hash and comparison */
MemoryContext tablecxt; /* memory context containing table */
@@ -839,9 +839,8 @@ typedef struct TupleHashTableData
TupleTableSlot *tableslot; /* slot for referencing table entries */
/* The following fields are set transiently for each table search: */
TupleTableSlot *inputslot; /* current input tuple's slot */
- FmgrInfo *in_hash_funcs; /* hash functions for input datatype(s) */
+ ExprState *in_hash_expr; /* ExprState for hashing input datatype(s) */
ExprState *cur_eq_func; /* comparator for input vs. table */
- uint32 hash_iv; /* hash-function IV */
ExprContext *exprcontext; /* expression context */
} TupleHashTableData;
@@ -994,7 +993,7 @@ typedef struct SubPlanState
* datatype(s) */
Oid *tab_collations; /* collations for hash and comparison */
FmgrInfo *tab_hash_funcs; /* hash functions for table datatype(s) */
- FmgrInfo *lhs_hash_funcs; /* hash functions for lefthand datatype(s) */
+ ExprState *lhs_hash_expr; /* hash expr for lefthand datatype(s) */
FmgrInfo *cur_eq_funcs; /* equality functions for LHS vs. table */
ExprState *cur_eq_comp; /* equality comparator for LHS vs. table */
} SubPlanState;
--
2.34.1
On 11/1/24 06:17, David Rowley wrote:
On Thu, 31 Oct 2024 at 15:30, Andrei Lepikhov <lepihov@gmail.com> wrote:
Comparing the master with and without your patch, the first, I see is
more extensive usage of memory (see complete explains in the attachment):Current master:
Batches: 1 Memory Usage: 74513kBPatched:
Batches: 261 Memory Usage: 527905kB Disk Usage: 4832656kBThanks for testing that. I had forgotten to adjust the storage
location for the hash initial value when I rebased the patch against
the changes made in 9ca67658d. I've fixed that in the attached patch.
Okay, I passed through the code. It looks good. Hashing expressions are
too simple to give notably impressive results, but it is a step in the
right direction.
I found only one minor issue: an outdated comment (see attachment).
Also, to make a hash calculation as fast as possible, should we add the
call of murmurhash32 as an optional step of ExprState in the
ExecBuildHash32FromAttrs?
--
regards, Andrei Lepikhov
Attachments:
comment_fix.difftext/x-patch; charset=UTF-8; name=comment_fix.diffDownload
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 616f7bf270..6b535b0592 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -801,8 +801,8 @@ typedef struct ExecAuxRowMark
* supports searching a hashtable using cross-data-type hashing. For that,
* the caller must supply hash functions for the LHS datatype as well as
* the cross-type equality operators to use. in_hash_expr and cur_eq_func
- * are set to point to the caller's function arrays while doing such a search.
- * During LookupTupleHashEntry(), they point to tab_hash_expr and
+ * are set to point to the caller's hash and equality ExprStates while doing
+ * such a search. During LookupTupleHashEntry(), they point to tab_hash_expr and
* tab_eq_func respectively.
* ----------------------------------------------------------------
*/
On Sat, 2 Nov 2024 at 22:13, Andrei Lepikhov <lepihov@gmail.com> wrote:
Okay, I passed through the code. It looks good. Hashing expressions are
too simple to give notably impressive results, but it is a step in the
right direction.
I found only one minor issue: an outdated comment (see attachment).
Thanks for looking. I ended up doing a bit more work on that comment.
See attached.
I was performing some final benchmarks on this and found that there's
a small performance regression for hashed subplans.
The test case is:
create table t1 (a int);
insert into t1 select a from generate_series(1,100000)a;
select * from t1 where a not in(select a from t1);
With my Zen4 laptop I get:
gcc:
master tps = 58.0375255
v5-0001 tps = 56.11840762
clang:
master tps = 58.72993378
v5-0001 tps = 53.39965968
Zen2 3990x
gcc:
master tps = 34.30392818
v5-0001 tps = 33.22067202
clang:
master tps = 34.0497471
v5-0001 tps = 33.34801254
That's the average over 50 runs starting and stopping the server on
each 10 second run.
I'm still thinking about what to do about this. In the meantime, I'm
not going to commit it.
Also, to make a hash calculation as fast as possible, should we add the
call of murmurhash32 as an optional step of ExprState in the
ExecBuildHash32FromAttrs?
I wrote enough of this patch to test the performance. It does not
help. See attached 0002.
David
Attachments:
v5-0001-Use-ExprStates-for-hashing-in-GROUP-BY-and-SubPla.patchtext/plain; charset=US-ASCII; name=v5-0001-Use-ExprStates-for-hashing-in-GROUP-BY-and-SubPla.patchDownload
From 31cffc52c302e63da6c6f0c20cf8cc7c8162c191 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Wed, 7 Aug 2024 16:56:48 +1200
Subject: [PATCH v5 1/2] Use ExprStates for hashing in GROUP BY and SubPlans
This speeds up obtaining hash values for GROUP BY and for hashed
SubPlan by using the ExprState support for hashing. This allows JIT
compilation for hash value. This hash shown to improve Hash Aggregate
performance in some cases by about 3%.
In passing, fix a hypothetical bug in ExecBuildHash32Expr() so that the
initial value is stored directly in the ExprState's result field if
there are no expressions to hash. None of the current users of this
function uses an initial value, so the bug is only hypothetical.
Reviewed-by: Andrei Lepikhov <lepihov@gmail.com>
Discussion: https://postgr.es/m/CAApHDvpYSO3kc9UryMevWqthTBrxgfd9djiAjKHMPUSQeX9vdQ@mail.gmail.com
---
src/backend/executor/execExpr.c | 155 ++++++++++++++++++++++++++++
src/backend/executor/execGrouping.c | 82 ++++++---------
src/backend/executor/nodeSubplan.c | 17 ++-
src/include/executor/executor.h | 10 +-
src/include/nodes/execnodes.h | 25 +++--
5 files changed, 223 insertions(+), 66 deletions(-)
diff --git a/src/backend/executor/execExpr.c b/src/backend/executor/execExpr.c
index 8f7a534005..c7bb13e270 100644
--- a/src/backend/executor/execExpr.c
+++ b/src/backend/executor/execExpr.c
@@ -3971,6 +3971,161 @@ ExecBuildAggTransCall(ExprState *state, AggState *aggstate,
}
}
+/*
+ * Build an ExprState that calls the given hash function(s) on the attnums
+ * given by 'keyColIdx' . When numCols > 1, the hash values returned by each
+ * hash function are combined to produce a single hash value.
+ *
+ * desc: tuple descriptor for the to-be-hashed columns
+ * ops: TupleTableSlotOps to use for the give TupleDesc
+ * hashfunctions: FmgrInfos for each hash function to call, one per numCols.
+ * These are used directly in the returned ExprState so must remain allocated.
+ * collations: collation to use when calling the hash function.
+ * numCols: array length of hashfunctions, collations and keyColIdx.
+ * parent: PlanState node that the resulting ExprState will be evaluated at
+ * init_value: Normally 0, but can be set to other values to seed the hash
+ * with. Non-zero is marginally slower, so best to only use if it's provably
+ * worthwhile.
+ */
+ExprState *
+ExecBuildHash32FromAttrs(TupleDesc desc, const TupleTableSlotOps *ops,
+ FmgrInfo *hashfunctions, Oid *collations,
+ int numCols, AttrNumber *keyColIdx,
+ PlanState *parent, uint32 init_value)
+{
+ ExprState *state = makeNode(ExprState);
+ ExprEvalStep scratch = {0};
+ NullableDatum *iresult = NULL;
+ intptr_t opcode;
+ AttrNumber last_attnum = 0;
+
+ Assert(numCols >= 0);
+
+ state->parent = parent;
+
+ /*
+ * Make a place to store intermediate hash values between subsequent
+ * hashing of individual columns. We only need this if there is more than
+ * one column to hash or an initial value plus one column.
+ */
+ if ((int64) numCols + (init_value != 0) > 1)
+ iresult = palloc(sizeof(NullableDatum));
+
+ /* find the highest attnum so we deform the tuple to that point */
+ for (int i = 0; i < numCols; i++)
+ last_attnum = Max(last_attnum, keyColIdx[i]);
+
+ scratch.opcode = EEOP_INNER_FETCHSOME;
+ scratch.d.fetch.last_var = last_attnum;
+ scratch.d.fetch.fixed = false;
+ scratch.d.fetch.kind = NULL;
+ scratch.d.fetch.known_desc = NULL;
+ if (ExecComputeSlotInfo(state, &scratch))
+ ExprEvalPushStep(state, &scratch);
+
+ if (init_value == 0)
+ {
+ /*
+ * No initial value, so we can assign the result of the hash function
+ * for the first hash_expr without having to concern ourselves with
+ * combining the result with any initial value.
+ */
+ opcode = EEOP_HASHDATUM_FIRST;
+ }
+ else
+ {
+ /*
+ * Set up operation to set the initial value. Normally we store this
+ * in the intermediate hash value location, but if there are no
+ * columns to hash, store it in the ExprState's result field.
+ */
+ scratch.opcode = EEOP_HASHDATUM_SET_INITVAL;
+ scratch.d.hashdatum_initvalue.init_value = UInt32GetDatum(init_value);
+ scratch.resvalue = numCols > 0 ? &iresult->value : &state->resvalue;
+ scratch.resnull = numCols > 0 ? &iresult->isnull : &state->resnull;
+
+ ExprEvalPushStep(state, &scratch);
+
+ /*
+ * When using an initial value use the NEXT32 ops as the FIRST ops
+ * would overwrite the stored initial value.
+ */
+ opcode = EEOP_HASHDATUM_NEXT32;
+ }
+
+ for (int i = 0; i < numCols; i++)
+ {
+ FmgrInfo *finfo;
+ FunctionCallInfo fcinfo;
+ Oid inputcollid = collations[i];
+ AttrNumber attnum = keyColIdx[i] - 1;
+
+ finfo = &hashfunctions[i];
+ fcinfo = palloc0(SizeForFunctionCallInfo(1));
+
+ /* Initialize function call parameter structure too */
+ InitFunctionCallInfoData(*fcinfo, finfo, 1, inputcollid, NULL, NULL);
+
+ /*
+ * Fetch inner Var for this attnum and store it in the 1st arg of the
+ * hash func.
+ */
+ scratch.opcode = EEOP_INNER_VAR;
+ scratch.resvalue = &fcinfo->args[0].value;
+ scratch.resnull = &fcinfo->args[0].isnull;
+ scratch.d.var.attnum = attnum;
+ scratch.d.var.vartype = TupleDescAttr(desc, attnum)->atttypid;
+
+ ExprEvalPushStep(state, &scratch);
+
+ /* Call the hash function */
+ scratch.opcode = opcode;
+
+ if (i == numCols - 1)
+ {
+ /*
+ * The result for hashing the final column is stored in the
+ * ExprState.
+ */
+ scratch.resvalue = &state->resvalue;
+ scratch.resnull = &state->resnull;
+ }
+ else
+ {
+ Assert(iresult != NULL);
+
+ /* intermediate values are stored in an intermediate result */
+ scratch.resvalue = &iresult->value;
+ scratch.resnull = &iresult->isnull;
+ }
+
+ /*
+ * NEXT32 opcodes need to look at the intermediate result. We might
+ * as well just set this for all ops. FIRSTs won't look at it.
+ */
+ scratch.d.hashdatum.iresult = iresult;
+
+ scratch.d.hashdatum.finfo = finfo;
+ scratch.d.hashdatum.fcinfo_data = fcinfo;
+ scratch.d.hashdatum.fn_addr = finfo->fn_addr;
+ scratch.d.hashdatum.jumpdone = -1;
+
+ ExprEvalPushStep(state, &scratch);
+
+ /* subsequent attnums must be combined with the previous */
+ opcode = EEOP_HASHDATUM_NEXT32;
+ }
+
+ scratch.resvalue = NULL;
+ scratch.resnull = NULL;
+ scratch.opcode = EEOP_DONE;
+ ExprEvalPushStep(state, &scratch);
+
+ ExecReadyExpr(state);
+
+ return state;
+}
+
/*
* Build an ExprState that calls the given hash function(s) on the given
* 'hash_exprs'. When multiple expressions are present, the hash values
diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c
index 774e4de882..9a88fc6524 100644
--- a/src/backend/executor/execGrouping.c
+++ b/src/backend/executor/execGrouping.c
@@ -169,6 +169,7 @@ BuildTupleHashTableExt(PlanState *parent,
Size hash_mem_limit;
MemoryContext oldcontext;
bool allow_jit;
+ uint32 hash_iv = 0;
Assert(nbuckets > 0);
@@ -183,14 +184,13 @@ BuildTupleHashTableExt(PlanState *parent,
hashtable->numCols = numCols;
hashtable->keyColIdx = keyColIdx;
- hashtable->tab_hash_funcs = hashfunctions;
hashtable->tab_collations = collations;
hashtable->tablecxt = tablecxt;
hashtable->tempcxt = tempcxt;
hashtable->entrysize = entrysize;
hashtable->tableslot = NULL; /* will be made on first lookup */
hashtable->inputslot = NULL;
- hashtable->in_hash_funcs = NULL;
+ hashtable->in_hash_expr = NULL;
hashtable->cur_eq_func = NULL;
/*
@@ -202,9 +202,7 @@ BuildTupleHashTableExt(PlanState *parent,
* underestimated.
*/
if (use_variable_hash_iv)
- hashtable->hash_iv = murmurhash32(ParallelWorkerNumber);
- else
- hashtable->hash_iv = 0;
+ hash_iv = murmurhash32(ParallelWorkerNumber);
hashtable->hashtab = tuplehash_create(metacxt, nbuckets, hashtable);
@@ -225,6 +223,16 @@ BuildTupleHashTableExt(PlanState *parent,
*/
allow_jit = metacxt != tablecxt;
+ /* build hash ExprState for all columns */
+ hashtable->tab_hash_expr = ExecBuildHash32FromAttrs(inputDesc,
+ &TTSOpsMinimalTuple,
+ hashfunctions,
+ collations,
+ numCols,
+ keyColIdx,
+ allow_jit ? parent : NULL,
+ hash_iv);
+
/* build comparator for all columns */
/* XXX: should we support non-minimal tuples for the inputslot? */
hashtable->tab_eq_func = ExecBuildGroupingEqual(inputDesc, inputDesc,
@@ -316,7 +324,7 @@ LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
/* set up data needed by hash and match functions */
hashtable->inputslot = slot;
- hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
+ hashtable->in_hash_expr = hashtable->tab_hash_expr;
hashtable->cur_eq_func = hashtable->tab_eq_func;
local_hash = TupleHashTableHash_internal(hashtable->hashtab, NULL);
@@ -342,7 +350,7 @@ TupleHashTableHash(TupleHashTable hashtable, TupleTableSlot *slot)
uint32 hash;
hashtable->inputslot = slot;
- hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
+ hashtable->in_hash_expr = hashtable->tab_hash_expr;
/* Need to run the hash functions in short-lived context */
oldContext = MemoryContextSwitchTo(hashtable->tempcxt);
@@ -370,7 +378,7 @@ LookupTupleHashEntryHash(TupleHashTable hashtable, TupleTableSlot *slot,
/* set up data needed by hash and match functions */
hashtable->inputslot = slot;
- hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
+ hashtable->in_hash_expr = hashtable->tab_hash_expr;
hashtable->cur_eq_func = hashtable->tab_eq_func;
entry = LookupTupleHashEntry_internal(hashtable, slot, isnew, hash);
@@ -386,14 +394,14 @@ LookupTupleHashEntryHash(TupleHashTable hashtable, TupleTableSlot *slot,
* created if there's not a match. This is similar to the non-creating
* case of LookupTupleHashEntry, except that it supports cross-type
* comparisons, in which the given tuple is not of the same type as the
- * table entries. The caller must provide the hash functions to use for
- * the input tuple, as well as the equality functions, since these may be
+ * table entries. The caller must provide the hash ExprState to use for
+ * the input tuple, as well as the equality ExprState, since these may be
* different from the table's internal functions.
*/
TupleHashEntry
FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
ExprState *eqcomp,
- FmgrInfo *hashfunctions)
+ ExprState *hashexpr)
{
TupleHashEntry entry;
MemoryContext oldContext;
@@ -404,7 +412,7 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
/* Set up data needed by hash and match functions */
hashtable->inputslot = slot;
- hashtable->in_hash_funcs = hashfunctions;
+ hashtable->in_hash_expr = hashexpr;
hashtable->cur_eq_func = eqcomp;
/* Search the hash table */
@@ -421,25 +429,24 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
* copied into the table.
*
* Also, the caller must select an appropriate memory context for running
- * the hash functions. (dynahash.c doesn't change CurrentMemoryContext.)
+ * the hash functions.
*/
static uint32
TupleHashTableHash_internal(struct tuplehash_hash *tb,
const MinimalTuple tuple)
{
TupleHashTable hashtable = (TupleHashTable) tb->private_data;
- int numCols = hashtable->numCols;
- AttrNumber *keyColIdx = hashtable->keyColIdx;
- uint32 hashkey = hashtable->hash_iv;
+ uint32 hashkey;
TupleTableSlot *slot;
- FmgrInfo *hashfunctions;
- int i;
+ bool isnull;
if (tuple == NULL)
{
/* Process the current input tuple for the table */
- slot = hashtable->inputslot;
- hashfunctions = hashtable->in_hash_funcs;
+ hashtable->exprcontext->ecxt_innertuple = hashtable->inputslot;
+ hashkey = DatumGetUInt32(ExecEvalExpr(hashtable->in_hash_expr,
+ hashtable->exprcontext,
+ &isnull));
}
else
{
@@ -449,38 +456,17 @@ TupleHashTableHash_internal(struct tuplehash_hash *tb,
* (this case never actually occurs due to the way simplehash.h is
* used, as the hash-value is stored in the entries)
*/
- slot = hashtable->tableslot;
+ slot = hashtable->exprcontext->ecxt_innertuple = hashtable->tableslot;
ExecStoreMinimalTuple(tuple, slot, false);
- hashfunctions = hashtable->tab_hash_funcs;
- }
-
- for (i = 0; i < numCols; i++)
- {
- AttrNumber att = keyColIdx[i];
- Datum attr;
- bool isNull;
-
- /* combine successive hashkeys by rotating */
- hashkey = pg_rotate_left32(hashkey, 1);
-
- attr = slot_getattr(slot, att, &isNull);
-
- if (!isNull) /* treat nulls as having hash key 0 */
- {
- uint32 hkey;
-
- hkey = DatumGetUInt32(FunctionCall1Coll(&hashfunctions[i],
- hashtable->tab_collations[i],
- attr));
- hashkey ^= hkey;
- }
+ hashkey = DatumGetUInt32(ExecEvalExpr(hashtable->tab_hash_expr,
+ hashtable->exprcontext,
+ &isnull));
}
/*
- * The way hashes are combined above, among each other and with the IV,
- * doesn't lead to good bit perturbation. As the IV's goal is to lead to
- * achieve that, perform a round of hashing of the combined hash -
- * resulting in near perfect perturbation.
+ * The hashing done above, even with an initial value, doesn't tend to
+ * result in good hash perturbation. Running the value produced above
+ * through murmurhash32 leads to near perfect hash perturbation.
*/
return murmurhash32(hashkey);
}
diff --git a/src/backend/executor/nodeSubplan.c b/src/backend/executor/nodeSubplan.c
index 236222d72a..40bae49267 100644
--- a/src/backend/executor/nodeSubplan.c
+++ b/src/backend/executor/nodeSubplan.c
@@ -160,7 +160,7 @@ ExecHashSubPlan(SubPlanState *node,
FindTupleHashEntry(node->hashtable,
slot,
node->cur_eq_comp,
- node->lhs_hash_funcs) != NULL)
+ node->lhs_hash_expr) != NULL)
{
ExecClearTuple(slot);
return BoolGetDatum(true);
@@ -857,7 +857,6 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
sstate->tab_eq_funcoids = NULL;
sstate->tab_hash_funcs = NULL;
sstate->tab_collations = NULL;
- sstate->lhs_hash_funcs = NULL;
sstate->cur_eq_funcs = NULL;
/*
@@ -897,6 +896,7 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
TupleDesc tupDescRight;
Oid *cross_eq_funcoids;
TupleTableSlot *slot;
+ FmgrInfo *lhs_hash_funcs;
List *oplist,
*lefttlist,
*righttlist;
@@ -953,7 +953,7 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
sstate->tab_eq_funcoids = (Oid *) palloc(ncols * sizeof(Oid));
sstate->tab_collations = (Oid *) palloc(ncols * sizeof(Oid));
sstate->tab_hash_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
- sstate->lhs_hash_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
+ lhs_hash_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
sstate->cur_eq_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
/* we'll need the cross-type equality fns below, but not in sstate */
cross_eq_funcoids = (Oid *) palloc(ncols * sizeof(Oid));
@@ -1003,7 +1003,7 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
&left_hashfn, &right_hashfn))
elog(ERROR, "could not find hash function for hash operator %u",
opexpr->opno);
- fmgr_info(left_hashfn, &sstate->lhs_hash_funcs[i - 1]);
+ fmgr_info(left_hashfn, &lhs_hash_funcs[i - 1]);
fmgr_info(right_hashfn, &sstate->tab_hash_funcs[i - 1]);
/* Set collation */
@@ -1039,6 +1039,15 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
sstate->planstate,
NULL);
+ sstate->lhs_hash_expr = ExecBuildHash32FromAttrs(tupDescLeft,
+ &TTSOpsVirtual,
+ lhs_hash_funcs,
+ sstate->tab_collations,
+ sstate->numCols,
+ sstate->keyColIdx,
+ parent,
+ 0);
+
/*
* Create comparator for lookups of rows in the table (potentially
* cross-type comparisons).
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index 69c3ebff00..e77377ff9b 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -160,7 +160,7 @@ extern TupleHashEntry LookupTupleHashEntryHash(TupleHashTable hashtable,
extern TupleHashEntry FindTupleHashEntry(TupleHashTable hashtable,
TupleTableSlot *slot,
ExprState *eqcomp,
- FmgrInfo *hashfunctions);
+ ExprState *hashexpr);
extern void ResetTupleHashTable(TupleHashTable hashtable);
/*
@@ -289,6 +289,14 @@ extern ExprState *ExecInitCheck(List *qual, PlanState *parent);
extern List *ExecInitExprList(List *nodes, PlanState *parent);
extern ExprState *ExecBuildAggTrans(AggState *aggstate, struct AggStatePerPhaseData *phase,
bool doSort, bool doHash, bool nullcheck);
+extern ExprState *ExecBuildHash32FromAttrs(TupleDesc desc,
+ const TupleTableSlotOps *ops,
+ FmgrInfo *hashfunctions,
+ Oid *collations,
+ int numCols,
+ AttrNumber *keyColIdx,
+ PlanState *parent,
+ uint32 init_value);
extern ExprState *ExecBuildHash32Expr(TupleDesc desc,
const TupleTableSlotOps *ops,
const Oid *hashfunc_oids,
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 182a6956bb..7f71b7625d 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -795,15 +795,15 @@ typedef struct ExecAuxRowMark
*
* All-in-memory tuple hash tables are used for a number of purposes.
*
- * Note: tab_hash_funcs are for the key datatype(s) stored in the table,
- * and tab_eq_func are non-cross-type equality operators for those types.
- * Normally these are the only functions used, but FindTupleHashEntry()
- * supports searching a hashtable using cross-data-type hashing. For that,
- * the caller must supply hash functions for the LHS datatype as well as
- * the cross-type equality operators to use. in_hash_funcs and cur_eq_func
- * are set to point to the caller's function arrays while doing such a search.
- * During LookupTupleHashEntry(), they point to tab_hash_funcs and
- * tab_eq_func respectively.
+ * Note: tab_hash_expr is for hashing the key datatype(s) stored in the table,
+ * and tab_eq_func is a non-cross-type ExprState for equality checks on those
+ * types. Normally these are the only ExprStates used, but
+ * FindTupleHashEntry() supports searching a hashtable using cross-data-type
+ * hashing. For that, the caller must supply an ExprState to hash the LHS
+ * datatype as well as the cross-type equality ExprState to use. in_hash_expr
+ * and cur_eq_func are set to point to the caller's hash and equality
+ * ExprStates while doing such a search. During LookupTupleHashEntry(), they
+ * point to tab_hash_expr and tab_eq_func respectively.
* ----------------------------------------------------------------
*/
typedef struct TupleHashEntryData *TupleHashEntry;
@@ -830,7 +830,7 @@ typedef struct TupleHashTableData
tuplehash_hash *hashtab; /* underlying hash table */
int numCols; /* number of columns in lookup key */
AttrNumber *keyColIdx; /* attr numbers of key columns */
- FmgrInfo *tab_hash_funcs; /* hash functions for table datatype(s) */
+ ExprState *tab_hash_expr; /* ExprState for hashing table datatype(s) */
ExprState *tab_eq_func; /* comparator for table datatype(s) */
Oid *tab_collations; /* collations for hash and comparison */
MemoryContext tablecxt; /* memory context containing table */
@@ -839,9 +839,8 @@ typedef struct TupleHashTableData
TupleTableSlot *tableslot; /* slot for referencing table entries */
/* The following fields are set transiently for each table search: */
TupleTableSlot *inputslot; /* current input tuple's slot */
- FmgrInfo *in_hash_funcs; /* hash functions for input datatype(s) */
+ ExprState *in_hash_expr; /* ExprState for hashing input datatype(s) */
ExprState *cur_eq_func; /* comparator for input vs. table */
- uint32 hash_iv; /* hash-function IV */
ExprContext *exprcontext; /* expression context */
} TupleHashTableData;
@@ -994,7 +993,7 @@ typedef struct SubPlanState
* datatype(s) */
Oid *tab_collations; /* collations for hash and comparison */
FmgrInfo *tab_hash_funcs; /* hash functions for table datatype(s) */
- FmgrInfo *lhs_hash_funcs; /* hash functions for lefthand datatype(s) */
+ ExprState *lhs_hash_expr; /* hash expr for lefthand datatype(s) */
FmgrInfo *cur_eq_funcs; /* equality functions for LHS vs. table */
ExprState *cur_eq_comp; /* equality comparator for LHS vs. table */
} SubPlanState;
--
2.34.1
v5-0002-Support-murmur32-hashing-of-the-final-ExprState-h.patch.txttext/plain; charset=US-ASCII; name=v5-0002-Support-murmur32-hashing-of-the-final-ExprState-h.patch.txtDownload
From ed798392e2fc0e0df167b80d468faaf74fd4bc33 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Mon, 4 Nov 2024 23:45:07 +1300
Subject: [PATCH v5 2/2] Support murmur32 hashing of the final ExprState hash
value
*** No JIT support yet ***
---
src/backend/executor/execExpr.c | 18 +++++++++++++++---
src/backend/executor/execExprInterp.c | 11 +++++++++++
src/backend/executor/execGrouping.c | 23 ++++++++---------------
src/backend/executor/nodeSubplan.c | 3 ++-
src/include/executor/execExpr.h | 1 +
src/include/executor/executor.h | 3 ++-
6 files changed, 39 insertions(+), 20 deletions(-)
diff --git a/src/backend/executor/execExpr.c b/src/backend/executor/execExpr.c
index c7bb13e270..b55431229d 100644
--- a/src/backend/executor/execExpr.c
+++ b/src/backend/executor/execExpr.c
@@ -3986,12 +3986,15 @@ ExecBuildAggTransCall(ExprState *state, AggState *aggstate,
* init_value: Normally 0, but can be set to other values to seed the hash
* with. Non-zero is marginally slower, so best to only use if it's provably
* worthwhile.
+ * murmurfinal: Can be set to true to have the final result hashed through
+ * murmur32. This can improve the hash perturbation of the result.
*/
ExprState *
ExecBuildHash32FromAttrs(TupleDesc desc, const TupleTableSlotOps *ops,
FmgrInfo *hashfunctions, Oid *collations,
int numCols, AttrNumber *keyColIdx,
- PlanState *parent, uint32 init_value)
+ PlanState *parent, uint32 init_value,
+ bool murmurfinal)
{
ExprState *state = makeNode(ExprState);
ExprEvalStep scratch = {0};
@@ -4008,7 +4011,7 @@ ExecBuildHash32FromAttrs(TupleDesc desc, const TupleTableSlotOps *ops,
* hashing of individual columns. We only need this if there is more than
* one column to hash or an initial value plus one column.
*/
- if ((int64) numCols + (init_value != 0) > 1)
+ if ((int64) numCols + (init_value != 0) > 1 || murmurfinal)
iresult = palloc(sizeof(NullableDatum));
/* find the highest attnum so we deform the tuple to that point */
@@ -4081,7 +4084,7 @@ ExecBuildHash32FromAttrs(TupleDesc desc, const TupleTableSlotOps *ops,
/* Call the hash function */
scratch.opcode = opcode;
- if (i == numCols - 1)
+ if (i == numCols - 1 && !murmurfinal)
{
/*
* The result for hashing the final column is stored in the
@@ -4116,6 +4119,15 @@ ExecBuildHash32FromAttrs(TupleDesc desc, const TupleTableSlotOps *ops,
opcode = EEOP_HASHDATUM_NEXT32;
}
+ if (murmurfinal)
+ {
+ scratch.opcode = EEOP_HASHDATUM_MURMUR32_FINAL;
+ scratch.resvalue = &state->resvalue;
+ scratch.resnull = &state->resnull;
+ scratch.d.hashdatum.iresult = iresult;
+ ExprEvalPushStep(state, &scratch);
+ }
+
scratch.resvalue = NULL;
scratch.resnull = NULL;
scratch.opcode = EEOP_DONE;
diff --git a/src/backend/executor/execExprInterp.c b/src/backend/executor/execExprInterp.c
index 30c5a19aad..391835a3e5 100644
--- a/src/backend/executor/execExprInterp.c
+++ b/src/backend/executor/execExprInterp.c
@@ -59,6 +59,7 @@
#include "access/heaptoast.h"
#include "catalog/pg_type.h"
#include "commands/sequence.h"
+#include "common/hashfn.h"
#include "executor/execExpr.h"
#include "executor/nodeSubplan.h"
#include "funcapi.h"
@@ -482,6 +483,7 @@ ExecInterpExpr(ExprState *state, ExprContext *econtext, bool *isnull)
&&CASE_EEOP_HASHDATUM_FIRST_STRICT,
&&CASE_EEOP_HASHDATUM_NEXT32,
&&CASE_EEOP_HASHDATUM_NEXT32_STRICT,
+ &&CASE_EEOP_HASHDATUM_MURMUR32_FINAL,
&&CASE_EEOP_CONVERT_ROWTYPE,
&&CASE_EEOP_SCALARARRAYOP,
&&CASE_EEOP_HASHED_SCALARARRAYOP,
@@ -1655,6 +1657,15 @@ ExecInterpExpr(ExprState *state, ExprContext *econtext, bool *isnull)
EEO_NEXT();
}
+ EEO_CASE(EEOP_HASHDATUM_MURMUR32_FINAL)
+ {
+ uint32 hashkey = DatumGetUInt32(op->d.hashdatum.iresult->value);
+
+ *op->resvalue = murmurhash32(hashkey);
+ *op->resnull = false;
+ EEO_NEXT();
+ }
+
EEO_CASE(EEOP_XMLEXPR)
{
/* too complex for an inline implementation */
diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c
index 9a88fc6524..5d88f517d5 100644
--- a/src/backend/executor/execGrouping.c
+++ b/src/backend/executor/execGrouping.c
@@ -231,7 +231,8 @@ BuildTupleHashTableExt(PlanState *parent,
numCols,
keyColIdx,
allow_jit ? parent : NULL,
- hash_iv);
+ hash_iv,
+ true);
/* build comparator for all columns */
/* XXX: should we support non-minimal tuples for the inputslot? */
@@ -436,7 +437,6 @@ TupleHashTableHash_internal(struct tuplehash_hash *tb,
const MinimalTuple tuple)
{
TupleHashTable hashtable = (TupleHashTable) tb->private_data;
- uint32 hashkey;
TupleTableSlot *slot;
bool isnull;
@@ -444,9 +444,9 @@ TupleHashTableHash_internal(struct tuplehash_hash *tb,
{
/* Process the current input tuple for the table */
hashtable->exprcontext->ecxt_innertuple = hashtable->inputslot;
- hashkey = DatumGetUInt32(ExecEvalExpr(hashtable->in_hash_expr,
- hashtable->exprcontext,
- &isnull));
+ return DatumGetUInt32(ExecEvalExpr(hashtable->in_hash_expr,
+ hashtable->exprcontext,
+ &isnull));
}
else
{
@@ -458,17 +458,10 @@ TupleHashTableHash_internal(struct tuplehash_hash *tb,
*/
slot = hashtable->exprcontext->ecxt_innertuple = hashtable->tableslot;
ExecStoreMinimalTuple(tuple, slot, false);
- hashkey = DatumGetUInt32(ExecEvalExpr(hashtable->tab_hash_expr,
- hashtable->exprcontext,
- &isnull));
+ return DatumGetUInt32(ExecEvalExpr(hashtable->tab_hash_expr,
+ hashtable->exprcontext,
+ &isnull));
}
-
- /*
- * The hashing done above, even with an initial value, doesn't tend to
- * result in good hash perturbation. Running the value produced above
- * through murmurhash32 leads to near perfect hash perturbation.
- */
- return murmurhash32(hashkey);
}
/*
diff --git a/src/backend/executor/nodeSubplan.c b/src/backend/executor/nodeSubplan.c
index 40bae49267..0e3d97f4f0 100644
--- a/src/backend/executor/nodeSubplan.c
+++ b/src/backend/executor/nodeSubplan.c
@@ -1046,7 +1046,8 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
sstate->numCols,
sstate->keyColIdx,
parent,
- 0);
+ 0,
+ true);
/*
* Create comparator for lookups of rows in the table (potentially
diff --git a/src/include/executor/execExpr.h b/src/include/executor/execExpr.h
index cd97dfa062..081d91cf6a 100644
--- a/src/include/executor/execExpr.h
+++ b/src/include/executor/execExpr.h
@@ -241,6 +241,7 @@ typedef enum ExprEvalOp
EEOP_HASHDATUM_FIRST_STRICT,
EEOP_HASHDATUM_NEXT32,
EEOP_HASHDATUM_NEXT32_STRICT,
+ EEOP_HASHDATUM_MURMUR32_FINAL,
/* evaluate assorted special-purpose expression types */
EEOP_CONVERT_ROWTYPE,
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index e77377ff9b..210217f406 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -296,7 +296,8 @@ extern ExprState *ExecBuildHash32FromAttrs(TupleDesc desc,
int numCols,
AttrNumber *keyColIdx,
PlanState *parent,
- uint32 init_value);
+ uint32 init_value,
+ bool murmurfinal);
extern ExprState *ExecBuildHash32Expr(TupleDesc desc,
const TupleTableSlotOps *ops,
const Oid *hashfunc_oids,
--
2.34.1
On Wed, 6 Nov 2024 at 09:38, David Rowley <dgrowleyml@gmail.com> wrote:
I was performing some final benchmarks on this and found that there's
a small performance regression for hashed subplans.
I'm still thinking about what to do about this. In the meantime, I'm
not going to commit it.
I spent quite a bit more time on this both benchmarking and adjusting
the patch. I've now added some dedicated ExecJust* evaluation
functions for hashing a single Var. This should give something similar
to the JITted performance with optimisation and no inlining for single
columns. The v6-0002 patch does contain some additional ExecJust*
functions to improve the performance of Hash Joins. I'll remove those
and test them independently.
The benchmark results are often very close and often the numbers are
different on both patched and unpatched if I stop and start the server
and prewarm the tables again. For this reason, I ended up running the
benchmarks 50 times each stopping and starting the server between each
run. I added a 10-second sleep as it's quite warm weather here
currently and I did start to get thermal throttling on the Zen4 laptop
without this.
Setup:
create table t1 (a int);
insert into t1 values(1);
create table t2 (a int);
insert into t2 select 1 from generate_series(1,1000000);
vacuum freeze analyze t1,t2;
notin.sql: select a from t2 where a not in (select a from t1);
I made it so the hash table contains only a single record and I probe
that record each time. I did that to ensure the hash table item was
always in L1.
groupby.sql: select a from t2 group by a;
This produces a single group. That was done to eliminate CPU cache
related variations and to try and exaggerate any difference with the
ExprState hashing performance as much as possible.
for i in {1..50}; do pg_ctl stop -D pgdata > /dev/null && pg_ctl start
-D pgdata -l pg.log > /dev/null && psql -c "select
pg_prewarm('t1'),pg_prewarm('t2');" postgres > /dev/null && sleep 10
&& pgbench -n -f notin.sql -T 10 -M prepared postgres | grep tps; done
Please see the attached 6 graphs for the results. Note the left axis
is not scaled to zero. I adjusted the lower end of that axis to be
just below the lowest results value as without that, the lines were
often too close to notice the difference. I also included a dotted
line with the percentage of performance increase the patched version
gave. These are on the righthand vertical axis. For both AMD
machines, I compiled with gcc and clang.
The only slowdown I saw was the NOT IN test on the AMD3990x machine.
It's about 3.6% slower with gcc and 1% slower with clang. All the
other tests show a performance gain. The AMD3990x's GROUP BY test saw
a 13% improvement and the NOT IN test on the Zen4 with gcc averages
almost 33% faster.
I'm pretty happy with this now. The only part I'm not so sure about is
what to pass as the "parent" parameter for ExecBuildHash32FromAttrs()
in nodeSubplan.c. I think the existing call to
ExecBuildGroupingEqual() is passing the wrong PlanState. I believe
this should be passing the PlanState for the SubPlanState.
David
Attachments:
v6-0001-Use-ExprStates-for-hashing-in-GROUP-BY-and-SubPla.patchapplication/octet-stream; name=v6-0001-Use-ExprStates-for-hashing-in-GROUP-BY-and-SubPla.patchDownload
From 069fe633aceb5960ff077a21c2bfd3136c4a385a Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Wed, 7 Aug 2024 16:56:48 +1200
Subject: [PATCH v6 1/2] Use ExprStates for hashing in GROUP BY and SubPlans
This speeds up obtaining hash values for GROUP BY and for hashed
SubPlan by using the ExprState support for hashing. This allows JIT
compilation for hash value. This hash shown to improve Hash Aggregate
performance in some cases by about 3%.
In passing, fix a hypothetical bug in ExecBuildHash32Expr() so that the
initial value is stored directly in the ExprState's result field if
there are no expressions to hash. None of the current users of this
function uses an initial value, so the bug is only hypothetical.
Reviewed-by: Andrei Lepikhov <lepihov@gmail.com>
Discussion: https://postgr.es/m/CAApHDvpYSO3kc9UryMevWqthTBrxgfd9djiAjKHMPUSQeX9vdQ@mail.gmail.com
---
src/backend/executor/execExpr.c | 155 ++++++++++++++++++++++++++++
src/backend/executor/execGrouping.c | 82 ++++++---------
src/backend/executor/nodeSubplan.c | 17 ++-
src/include/executor/executor.h | 10 +-
src/include/nodes/execnodes.h | 25 +++--
5 files changed, 223 insertions(+), 66 deletions(-)
diff --git a/src/backend/executor/execExpr.c b/src/backend/executor/execExpr.c
index 69d36f70b3..fdc71ee216 100644
--- a/src/backend/executor/execExpr.c
+++ b/src/backend/executor/execExpr.c
@@ -3979,6 +3979,161 @@ ExecBuildAggTransCall(ExprState *state, AggState *aggstate,
}
}
+/*
+ * Build an ExprState that calls the given hash function(s) on the attnums
+ * given by 'keyColIdx' . When numCols > 1, the hash values returned by each
+ * hash function are combined to produce a single hash value.
+ *
+ * desc: tuple descriptor for the to-be-hashed columns
+ * ops: TupleTableSlotOps to use for the give TupleDesc
+ * hashfunctions: FmgrInfos for each hash function to call, one per numCols.
+ * These are used directly in the returned ExprState so must remain allocated.
+ * collations: collation to use when calling the hash function.
+ * numCols: array length of hashfunctions, collations and keyColIdx.
+ * parent: PlanState node that the resulting ExprState will be evaluated at
+ * init_value: Normally 0, but can be set to other values to seed the hash
+ * with. Non-zero is marginally slower, so best to only use if it's provably
+ * worthwhile.
+ */
+ExprState *
+ExecBuildHash32FromAttrs(TupleDesc desc, const TupleTableSlotOps *ops,
+ FmgrInfo *hashfunctions, Oid *collations,
+ int numCols, AttrNumber *keyColIdx,
+ PlanState *parent, uint32 init_value)
+{
+ ExprState *state = makeNode(ExprState);
+ ExprEvalStep scratch = {0};
+ NullableDatum *iresult = NULL;
+ intptr_t opcode;
+ AttrNumber last_attnum = 0;
+
+ Assert(numCols >= 0);
+
+ state->parent = parent;
+
+ /*
+ * Make a place to store intermediate hash values between subsequent
+ * hashing of individual columns. We only need this if there is more than
+ * one column to hash or an initial value plus one column.
+ */
+ if ((int64) numCols + (init_value != 0) > 1)
+ iresult = palloc(sizeof(NullableDatum));
+
+ /* find the highest attnum so we deform the tuple to that point */
+ for (int i = 0; i < numCols; i++)
+ last_attnum = Max(last_attnum, keyColIdx[i]);
+
+ scratch.opcode = EEOP_INNER_FETCHSOME;
+ scratch.d.fetch.last_var = last_attnum;
+ scratch.d.fetch.fixed = false;
+ scratch.d.fetch.kind = ops;
+ scratch.d.fetch.known_desc = desc;
+ if (ExecComputeSlotInfo(state, &scratch))
+ ExprEvalPushStep(state, &scratch);
+
+ if (init_value == 0)
+ {
+ /*
+ * No initial value, so we can assign the result of the hash function
+ * for the first hash_expr without having to concern ourselves with
+ * combining the result with any initial value.
+ */
+ opcode = EEOP_HASHDATUM_FIRST;
+ }
+ else
+ {
+ /*
+ * Set up operation to set the initial value. Normally we store this
+ * in the intermediate hash value location, but if there are no
+ * columns to hash, store it in the ExprState's result field.
+ */
+ scratch.opcode = EEOP_HASHDATUM_SET_INITVAL;
+ scratch.d.hashdatum_initvalue.init_value = UInt32GetDatum(init_value);
+ scratch.resvalue = numCols > 0 ? &iresult->value : &state->resvalue;
+ scratch.resnull = numCols > 0 ? &iresult->isnull : &state->resnull;
+
+ ExprEvalPushStep(state, &scratch);
+
+ /*
+ * When using an initial value use the NEXT32 ops as the FIRST ops
+ * would overwrite the stored initial value.
+ */
+ opcode = EEOP_HASHDATUM_NEXT32;
+ }
+
+ for (int i = 0; i < numCols; i++)
+ {
+ FmgrInfo *finfo;
+ FunctionCallInfo fcinfo;
+ Oid inputcollid = collations[i];
+ AttrNumber attnum = keyColIdx[i] - 1;
+
+ finfo = &hashfunctions[i];
+ fcinfo = palloc0(SizeForFunctionCallInfo(1));
+
+ /* Initialize function call parameter structure too */
+ InitFunctionCallInfoData(*fcinfo, finfo, 1, inputcollid, NULL, NULL);
+
+ /*
+ * Fetch inner Var for this attnum and store it in the 1st arg of the
+ * hash func.
+ */
+ scratch.opcode = EEOP_INNER_VAR;
+ scratch.resvalue = &fcinfo->args[0].value;
+ scratch.resnull = &fcinfo->args[0].isnull;
+ scratch.d.var.attnum = attnum;
+ scratch.d.var.vartype = TupleDescAttr(desc, attnum)->atttypid;
+
+ ExprEvalPushStep(state, &scratch);
+
+ /* Call the hash function */
+ scratch.opcode = opcode;
+
+ if (i == numCols - 1)
+ {
+ /*
+ * The result for hashing the final column is stored in the
+ * ExprState.
+ */
+ scratch.resvalue = &state->resvalue;
+ scratch.resnull = &state->resnull;
+ }
+ else
+ {
+ Assert(iresult != NULL);
+
+ /* intermediate values are stored in an intermediate result */
+ scratch.resvalue = &iresult->value;
+ scratch.resnull = &iresult->isnull;
+ }
+
+ /*
+ * NEXT32 opcodes need to look at the intermediate result. We might
+ * as well just set this for all ops. FIRSTs won't look at it.
+ */
+ scratch.d.hashdatum.iresult = iresult;
+
+ scratch.d.hashdatum.finfo = finfo;
+ scratch.d.hashdatum.fcinfo_data = fcinfo;
+ scratch.d.hashdatum.fn_addr = finfo->fn_addr;
+ scratch.d.hashdatum.jumpdone = -1;
+
+ ExprEvalPushStep(state, &scratch);
+
+ /* subsequent attnums must be combined with the previous */
+ opcode = EEOP_HASHDATUM_NEXT32;
+ }
+
+ scratch.resvalue = NULL;
+ scratch.resnull = NULL;
+ scratch.opcode = EEOP_DONE;
+ ExprEvalPushStep(state, &scratch);
+
+ ExecReadyExpr(state);
+
+ return state;
+}
+
/*
* Build an ExprState that calls the given hash function(s) on the given
* 'hash_exprs'. When multiple expressions are present, the hash values
diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c
index 774e4de882..9a88fc6524 100644
--- a/src/backend/executor/execGrouping.c
+++ b/src/backend/executor/execGrouping.c
@@ -169,6 +169,7 @@ BuildTupleHashTableExt(PlanState *parent,
Size hash_mem_limit;
MemoryContext oldcontext;
bool allow_jit;
+ uint32 hash_iv = 0;
Assert(nbuckets > 0);
@@ -183,14 +184,13 @@ BuildTupleHashTableExt(PlanState *parent,
hashtable->numCols = numCols;
hashtable->keyColIdx = keyColIdx;
- hashtable->tab_hash_funcs = hashfunctions;
hashtable->tab_collations = collations;
hashtable->tablecxt = tablecxt;
hashtable->tempcxt = tempcxt;
hashtable->entrysize = entrysize;
hashtable->tableslot = NULL; /* will be made on first lookup */
hashtable->inputslot = NULL;
- hashtable->in_hash_funcs = NULL;
+ hashtable->in_hash_expr = NULL;
hashtable->cur_eq_func = NULL;
/*
@@ -202,9 +202,7 @@ BuildTupleHashTableExt(PlanState *parent,
* underestimated.
*/
if (use_variable_hash_iv)
- hashtable->hash_iv = murmurhash32(ParallelWorkerNumber);
- else
- hashtable->hash_iv = 0;
+ hash_iv = murmurhash32(ParallelWorkerNumber);
hashtable->hashtab = tuplehash_create(metacxt, nbuckets, hashtable);
@@ -225,6 +223,16 @@ BuildTupleHashTableExt(PlanState *parent,
*/
allow_jit = metacxt != tablecxt;
+ /* build hash ExprState for all columns */
+ hashtable->tab_hash_expr = ExecBuildHash32FromAttrs(inputDesc,
+ &TTSOpsMinimalTuple,
+ hashfunctions,
+ collations,
+ numCols,
+ keyColIdx,
+ allow_jit ? parent : NULL,
+ hash_iv);
+
/* build comparator for all columns */
/* XXX: should we support non-minimal tuples for the inputslot? */
hashtable->tab_eq_func = ExecBuildGroupingEqual(inputDesc, inputDesc,
@@ -316,7 +324,7 @@ LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
/* set up data needed by hash and match functions */
hashtable->inputslot = slot;
- hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
+ hashtable->in_hash_expr = hashtable->tab_hash_expr;
hashtable->cur_eq_func = hashtable->tab_eq_func;
local_hash = TupleHashTableHash_internal(hashtable->hashtab, NULL);
@@ -342,7 +350,7 @@ TupleHashTableHash(TupleHashTable hashtable, TupleTableSlot *slot)
uint32 hash;
hashtable->inputslot = slot;
- hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
+ hashtable->in_hash_expr = hashtable->tab_hash_expr;
/* Need to run the hash functions in short-lived context */
oldContext = MemoryContextSwitchTo(hashtable->tempcxt);
@@ -370,7 +378,7 @@ LookupTupleHashEntryHash(TupleHashTable hashtable, TupleTableSlot *slot,
/* set up data needed by hash and match functions */
hashtable->inputslot = slot;
- hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
+ hashtable->in_hash_expr = hashtable->tab_hash_expr;
hashtable->cur_eq_func = hashtable->tab_eq_func;
entry = LookupTupleHashEntry_internal(hashtable, slot, isnew, hash);
@@ -386,14 +394,14 @@ LookupTupleHashEntryHash(TupleHashTable hashtable, TupleTableSlot *slot,
* created if there's not a match. This is similar to the non-creating
* case of LookupTupleHashEntry, except that it supports cross-type
* comparisons, in which the given tuple is not of the same type as the
- * table entries. The caller must provide the hash functions to use for
- * the input tuple, as well as the equality functions, since these may be
+ * table entries. The caller must provide the hash ExprState to use for
+ * the input tuple, as well as the equality ExprState, since these may be
* different from the table's internal functions.
*/
TupleHashEntry
FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
ExprState *eqcomp,
- FmgrInfo *hashfunctions)
+ ExprState *hashexpr)
{
TupleHashEntry entry;
MemoryContext oldContext;
@@ -404,7 +412,7 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
/* Set up data needed by hash and match functions */
hashtable->inputslot = slot;
- hashtable->in_hash_funcs = hashfunctions;
+ hashtable->in_hash_expr = hashexpr;
hashtable->cur_eq_func = eqcomp;
/* Search the hash table */
@@ -421,25 +429,24 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
* copied into the table.
*
* Also, the caller must select an appropriate memory context for running
- * the hash functions. (dynahash.c doesn't change CurrentMemoryContext.)
+ * the hash functions.
*/
static uint32
TupleHashTableHash_internal(struct tuplehash_hash *tb,
const MinimalTuple tuple)
{
TupleHashTable hashtable = (TupleHashTable) tb->private_data;
- int numCols = hashtable->numCols;
- AttrNumber *keyColIdx = hashtable->keyColIdx;
- uint32 hashkey = hashtable->hash_iv;
+ uint32 hashkey;
TupleTableSlot *slot;
- FmgrInfo *hashfunctions;
- int i;
+ bool isnull;
if (tuple == NULL)
{
/* Process the current input tuple for the table */
- slot = hashtable->inputslot;
- hashfunctions = hashtable->in_hash_funcs;
+ hashtable->exprcontext->ecxt_innertuple = hashtable->inputslot;
+ hashkey = DatumGetUInt32(ExecEvalExpr(hashtable->in_hash_expr,
+ hashtable->exprcontext,
+ &isnull));
}
else
{
@@ -449,38 +456,17 @@ TupleHashTableHash_internal(struct tuplehash_hash *tb,
* (this case never actually occurs due to the way simplehash.h is
* used, as the hash-value is stored in the entries)
*/
- slot = hashtable->tableslot;
+ slot = hashtable->exprcontext->ecxt_innertuple = hashtable->tableslot;
ExecStoreMinimalTuple(tuple, slot, false);
- hashfunctions = hashtable->tab_hash_funcs;
- }
-
- for (i = 0; i < numCols; i++)
- {
- AttrNumber att = keyColIdx[i];
- Datum attr;
- bool isNull;
-
- /* combine successive hashkeys by rotating */
- hashkey = pg_rotate_left32(hashkey, 1);
-
- attr = slot_getattr(slot, att, &isNull);
-
- if (!isNull) /* treat nulls as having hash key 0 */
- {
- uint32 hkey;
-
- hkey = DatumGetUInt32(FunctionCall1Coll(&hashfunctions[i],
- hashtable->tab_collations[i],
- attr));
- hashkey ^= hkey;
- }
+ hashkey = DatumGetUInt32(ExecEvalExpr(hashtable->tab_hash_expr,
+ hashtable->exprcontext,
+ &isnull));
}
/*
- * The way hashes are combined above, among each other and with the IV,
- * doesn't lead to good bit perturbation. As the IV's goal is to lead to
- * achieve that, perform a round of hashing of the combined hash -
- * resulting in near perfect perturbation.
+ * The hashing done above, even with an initial value, doesn't tend to
+ * result in good hash perturbation. Running the value produced above
+ * through murmurhash32 leads to near perfect hash perturbation.
*/
return murmurhash32(hashkey);
}
diff --git a/src/backend/executor/nodeSubplan.c b/src/backend/executor/nodeSubplan.c
index 236222d72a..40bae49267 100644
--- a/src/backend/executor/nodeSubplan.c
+++ b/src/backend/executor/nodeSubplan.c
@@ -160,7 +160,7 @@ ExecHashSubPlan(SubPlanState *node,
FindTupleHashEntry(node->hashtable,
slot,
node->cur_eq_comp,
- node->lhs_hash_funcs) != NULL)
+ node->lhs_hash_expr) != NULL)
{
ExecClearTuple(slot);
return BoolGetDatum(true);
@@ -857,7 +857,6 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
sstate->tab_eq_funcoids = NULL;
sstate->tab_hash_funcs = NULL;
sstate->tab_collations = NULL;
- sstate->lhs_hash_funcs = NULL;
sstate->cur_eq_funcs = NULL;
/*
@@ -897,6 +896,7 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
TupleDesc tupDescRight;
Oid *cross_eq_funcoids;
TupleTableSlot *slot;
+ FmgrInfo *lhs_hash_funcs;
List *oplist,
*lefttlist,
*righttlist;
@@ -953,7 +953,7 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
sstate->tab_eq_funcoids = (Oid *) palloc(ncols * sizeof(Oid));
sstate->tab_collations = (Oid *) palloc(ncols * sizeof(Oid));
sstate->tab_hash_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
- sstate->lhs_hash_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
+ lhs_hash_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
sstate->cur_eq_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
/* we'll need the cross-type equality fns below, but not in sstate */
cross_eq_funcoids = (Oid *) palloc(ncols * sizeof(Oid));
@@ -1003,7 +1003,7 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
&left_hashfn, &right_hashfn))
elog(ERROR, "could not find hash function for hash operator %u",
opexpr->opno);
- fmgr_info(left_hashfn, &sstate->lhs_hash_funcs[i - 1]);
+ fmgr_info(left_hashfn, &lhs_hash_funcs[i - 1]);
fmgr_info(right_hashfn, &sstate->tab_hash_funcs[i - 1]);
/* Set collation */
@@ -1039,6 +1039,15 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
sstate->planstate,
NULL);
+ sstate->lhs_hash_expr = ExecBuildHash32FromAttrs(tupDescLeft,
+ &TTSOpsVirtual,
+ lhs_hash_funcs,
+ sstate->tab_collations,
+ sstate->numCols,
+ sstate->keyColIdx,
+ parent,
+ 0);
+
/*
* Create comparator for lookups of rows in the table (potentially
* cross-type comparisons).
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index 69c3ebff00..e77377ff9b 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -160,7 +160,7 @@ extern TupleHashEntry LookupTupleHashEntryHash(TupleHashTable hashtable,
extern TupleHashEntry FindTupleHashEntry(TupleHashTable hashtable,
TupleTableSlot *slot,
ExprState *eqcomp,
- FmgrInfo *hashfunctions);
+ ExprState *hashexpr);
extern void ResetTupleHashTable(TupleHashTable hashtable);
/*
@@ -289,6 +289,14 @@ extern ExprState *ExecInitCheck(List *qual, PlanState *parent);
extern List *ExecInitExprList(List *nodes, PlanState *parent);
extern ExprState *ExecBuildAggTrans(AggState *aggstate, struct AggStatePerPhaseData *phase,
bool doSort, bool doHash, bool nullcheck);
+extern ExprState *ExecBuildHash32FromAttrs(TupleDesc desc,
+ const TupleTableSlotOps *ops,
+ FmgrInfo *hashfunctions,
+ Oid *collations,
+ int numCols,
+ AttrNumber *keyColIdx,
+ PlanState *parent,
+ uint32 init_value);
extern ExprState *ExecBuildHash32Expr(TupleDesc desc,
const TupleTableSlotOps *ops,
const Oid *hashfunc_oids,
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 182a6956bb..7f71b7625d 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -795,15 +795,15 @@ typedef struct ExecAuxRowMark
*
* All-in-memory tuple hash tables are used for a number of purposes.
*
- * Note: tab_hash_funcs are for the key datatype(s) stored in the table,
- * and tab_eq_func are non-cross-type equality operators for those types.
- * Normally these are the only functions used, but FindTupleHashEntry()
- * supports searching a hashtable using cross-data-type hashing. For that,
- * the caller must supply hash functions for the LHS datatype as well as
- * the cross-type equality operators to use. in_hash_funcs and cur_eq_func
- * are set to point to the caller's function arrays while doing such a search.
- * During LookupTupleHashEntry(), they point to tab_hash_funcs and
- * tab_eq_func respectively.
+ * Note: tab_hash_expr is for hashing the key datatype(s) stored in the table,
+ * and tab_eq_func is a non-cross-type ExprState for equality checks on those
+ * types. Normally these are the only ExprStates used, but
+ * FindTupleHashEntry() supports searching a hashtable using cross-data-type
+ * hashing. For that, the caller must supply an ExprState to hash the LHS
+ * datatype as well as the cross-type equality ExprState to use. in_hash_expr
+ * and cur_eq_func are set to point to the caller's hash and equality
+ * ExprStates while doing such a search. During LookupTupleHashEntry(), they
+ * point to tab_hash_expr and tab_eq_func respectively.
* ----------------------------------------------------------------
*/
typedef struct TupleHashEntryData *TupleHashEntry;
@@ -830,7 +830,7 @@ typedef struct TupleHashTableData
tuplehash_hash *hashtab; /* underlying hash table */
int numCols; /* number of columns in lookup key */
AttrNumber *keyColIdx; /* attr numbers of key columns */
- FmgrInfo *tab_hash_funcs; /* hash functions for table datatype(s) */
+ ExprState *tab_hash_expr; /* ExprState for hashing table datatype(s) */
ExprState *tab_eq_func; /* comparator for table datatype(s) */
Oid *tab_collations; /* collations for hash and comparison */
MemoryContext tablecxt; /* memory context containing table */
@@ -839,9 +839,8 @@ typedef struct TupleHashTableData
TupleTableSlot *tableslot; /* slot for referencing table entries */
/* The following fields are set transiently for each table search: */
TupleTableSlot *inputslot; /* current input tuple's slot */
- FmgrInfo *in_hash_funcs; /* hash functions for input datatype(s) */
+ ExprState *in_hash_expr; /* ExprState for hashing input datatype(s) */
ExprState *cur_eq_func; /* comparator for input vs. table */
- uint32 hash_iv; /* hash-function IV */
ExprContext *exprcontext; /* expression context */
} TupleHashTableData;
@@ -994,7 +993,7 @@ typedef struct SubPlanState
* datatype(s) */
Oid *tab_collations; /* collations for hash and comparison */
FmgrInfo *tab_hash_funcs; /* hash functions for table datatype(s) */
- FmgrInfo *lhs_hash_funcs; /* hash functions for lefthand datatype(s) */
+ ExprState *lhs_hash_expr; /* hash expr for lefthand datatype(s) */
FmgrInfo *cur_eq_funcs; /* equality functions for LHS vs. table */
ExprState *cur_eq_comp; /* equality comparator for LHS vs. table */
} SubPlanState;
--
2.34.1
v6-0002-Add-dedicated-evaluation-functions-for-hashing-Ex.patchapplication/octet-stream; name=v6-0002-Add-dedicated-evaluation-functions-for-hashing-Ex.patchDownload
From 5c21d47bbafe944ebc0a8d6ea292368ffc2b1f5b Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Mon, 25 Nov 2024 15:19:16 +1300
Subject: [PATCH v6 2/2] Add dedicated evaluation functions for hashing
ExprStates
It's common to be hashing a single Var and also cheap enough for the
step evaluation overhead of evaluation of the ExprState to matter. Here
we add dedicated functions to remove that overhead and thus speedup the
hashing of single Vars.
---
src/backend/executor/execExprInterp.c | 238 +++++++++++++++++++++++++-
1 file changed, 237 insertions(+), 1 deletion(-)
diff --git a/src/backend/executor/execExprInterp.c b/src/backend/executor/execExprInterp.c
index 42da962178..c3eb58a443 100644
--- a/src/backend/executor/execExprInterp.c
+++ b/src/backend/executor/execExprInterp.c
@@ -154,6 +154,12 @@ static void ExecEvalRowNullInt(ExprState *state, ExprEvalStep *op,
ExprContext *econtext, bool checkisnull);
/* fast-path evaluation functions */
+static Datum ExecJustFetchAndHashInnerVarWithIV(ExprState *state, ExprContext *econtext, bool *isnull);
+static Datum ExecJustFetchAndHashOuterVar(ExprState *state, ExprContext *econtext, bool *isnull);
+static Datum ExecJustFetchAndHashInnerVar(ExprState *state, ExprContext *econtext, bool *isnull);
+static Datum ExecJustHashInnerVar(ExprState *state, ExprContext *econtext, bool *isnull);
+static Datum ExecJustFetchAndHashOuterVarStrict(ExprState *state, ExprContext *econtext, bool *isnull);
+static Datum ExecJustFetchAndHashInnerVarStrict(ExprState *state, ExprContext *econtext, bool *isnull);
static Datum ExecJustInnerVar(ExprState *state, ExprContext *econtext, bool *isnull);
static Datum ExecJustOuterVar(ExprState *state, ExprContext *econtext, bool *isnull);
static Datum ExecJustScanVar(ExprState *state, ExprContext *econtext, bool *isnull);
@@ -273,7 +279,58 @@ ExecReadyInterpretedExpr(ExprState *state)
* the full interpreter is a measurable overhead for these, and these
* patterns occur often enough to be worth optimizing.
*/
- if (state->steps_len == 3)
+ if (state->steps_len == 5)
+ {
+ ExprEvalOp step0 = state->steps[0].opcode;
+ ExprEvalOp step1 = state->steps[1].opcode;
+ ExprEvalOp step2 = state->steps[2].opcode;
+ ExprEvalOp step3 = state->steps[3].opcode;
+
+ if (step0 == EEOP_INNER_FETCHSOME &&
+ step1 == EEOP_HASHDATUM_SET_INITVAL &&
+ step2 == EEOP_INNER_VAR &&
+ step3 == EEOP_HASHDATUM_NEXT32)
+ {
+ state->evalfunc_private = (void *) ExecJustFetchAndHashInnerVarWithIV;
+ return;
+ }
+ }
+ else if (state->steps_len == 4)
+ {
+ ExprEvalOp step0 = state->steps[0].opcode;
+ ExprEvalOp step1 = state->steps[1].opcode;
+ ExprEvalOp step2 = state->steps[2].opcode;
+
+ if (step0 == EEOP_OUTER_FETCHSOME &&
+ step1 == EEOP_OUTER_VAR &&
+ step2 == EEOP_HASHDATUM_FIRST)
+ {
+ state->evalfunc_private = (void *) ExecJustFetchAndHashOuterVar;
+ return;
+ }
+ else if (step0 == EEOP_INNER_FETCHSOME &&
+ step1 == EEOP_INNER_VAR &&
+ step2 == EEOP_HASHDATUM_FIRST)
+ {
+ state->evalfunc_private = (void *) ExecJustFetchAndHashInnerVar;
+ return;
+ }
+ else if (step0 == EEOP_OUTER_FETCHSOME &&
+ step1 == EEOP_OUTER_VAR &&
+ step2 == EEOP_HASHDATUM_FIRST_STRICT)
+ {
+ state->evalfunc_private = (void *) ExecJustFetchAndHashOuterVarStrict;
+ return;
+ }
+ else if (step0 == EEOP_INNER_FETCHSOME &&
+ step1 == EEOP_INNER_VAR &&
+ step2 == EEOP_HASHDATUM_FIRST_STRICT)
+ {
+ state->evalfunc_private = (void *) ExecJustFetchAndHashInnerVarStrict;
+ return;
+ }
+ }
+ else if (state->steps_len == 3)
{
ExprEvalOp step0 = state->steps[0].opcode;
ExprEvalOp step1 = state->steps[1].opcode;
@@ -321,6 +378,12 @@ ExecReadyInterpretedExpr(ExprState *state)
state->evalfunc_private = (void *) ExecJustApplyFuncToCase;
return;
}
+ else if (step0 == EEOP_INNER_VAR &&
+ step1 == EEOP_HASHDATUM_FIRST)
+ {
+ state->evalfunc_private = (void *) ExecJustHashInnerVar;
+ return;
+ }
}
else if (state->steps_len == 2)
{
@@ -2282,6 +2345,179 @@ ExecJustVarImpl(ExprState *state, TupleTableSlot *slot, bool *isnull)
return slot_getattr(slot, attnum, isnull);
}
+/*
+ * implementation for deforming and hashing an inner Var, seeding with an
+ * initial value.
+ */
+static Datum
+ExecJustFetchAndHashInnerVarWithIV(ExprState *state, ExprContext *econtext,
+ bool *isnull)
+{
+ ExprEvalStep *fetchop = &state->steps[0];
+ ExprEvalStep *setivop = &state->steps[1];
+ ExprEvalStep *innervar = &state->steps[2];
+ ExprEvalStep *hashop = &state->steps[3];
+ FunctionCallInfo fcinfo = hashop->d.hashdatum.fcinfo_data;
+ int attnum = innervar->d.var.attnum;
+ uint32 hashkey;
+
+ CheckOpSlotCompatibility(fetchop, econtext->ecxt_innertuple);
+ slot_getsomeattrs(econtext->ecxt_innertuple, fetchop->d.fetch.last_var);
+
+ fcinfo->args[0].value = econtext->ecxt_innertuple->tts_values[attnum];
+ fcinfo->args[0].isnull = econtext->ecxt_innertuple->tts_isnull[attnum];
+
+ hashkey = DatumGetUInt32(setivop->d.hashdatum_initvalue.init_value);
+ hashkey = pg_rotate_left32(hashkey, 1);
+
+ if (!fcinfo->args[0].isnull)
+ {
+ uint32 hashvalue;
+
+ hashvalue = DatumGetUInt32(hashop->d.hashdatum.fn_addr(fcinfo));
+ hashkey = hashkey ^ hashvalue;
+ }
+
+ *isnull = false;
+ return UInt32GetDatum(hashkey);
+}
+
+/* implementation for deforming and hashing an outer Var */
+static Datum
+ExecJustFetchAndHashOuterVar(ExprState *state, ExprContext *econtext,
+ bool *isnull)
+{
+ ExprEvalStep *fetchop = &state->steps[0];
+ ExprEvalStep *innervar = &state->steps[1];
+ ExprEvalStep *hashop = &state->steps[2];
+ FunctionCallInfo fcinfo = hashop->d.hashdatum.fcinfo_data;
+ int attnum = innervar->d.var.attnum;
+
+ CheckOpSlotCompatibility(fetchop, econtext->ecxt_outertuple);
+ slot_getsomeattrs(econtext->ecxt_outertuple, fetchop->d.fetch.last_var);
+
+ fcinfo->args[0].value = econtext->ecxt_outertuple->tts_values[attnum];
+ fcinfo->args[0].isnull = econtext->ecxt_outertuple->tts_isnull[attnum];
+
+ *isnull = false;
+
+ if (!fcinfo->args[0].isnull)
+ return DatumGetUInt32(hashop->d.hashdatum.fn_addr(fcinfo));
+ else
+ return (Datum) 0;
+}
+
+/* implementation for deforming and hashing an inner Var */
+static Datum
+ExecJustFetchAndHashInnerVar(ExprState *state, ExprContext *econtext,
+ bool *isnull)
+{
+ ExprEvalStep *fetchop = &state->steps[0];
+ ExprEvalStep *innervar = &state->steps[1];
+ ExprEvalStep *hashop = &state->steps[2];
+ FunctionCallInfo fcinfo = hashop->d.hashdatum.fcinfo_data;
+ int attnum = innervar->d.var.attnum;
+
+ CheckOpSlotCompatibility(fetchop, econtext->ecxt_innertuple);
+ slot_getsomeattrs(econtext->ecxt_innertuple, fetchop->d.fetch.last_var);
+
+ fcinfo->args[0].value = econtext->ecxt_innertuple->tts_values[attnum];
+ fcinfo->args[0].isnull = econtext->ecxt_innertuple->tts_isnull[attnum];
+
+ *isnull = false;
+
+ if (!fcinfo->args[0].isnull)
+ return DatumGetUInt32(hashop->d.hashdatum.fn_addr(fcinfo));
+ else
+ return (Datum) 0;
+}
+
+/* implementation for hashing an inner Var */
+static Datum
+ExecJustHashInnerVar(ExprState *state, ExprContext *econtext, bool *isnull)
+{
+ ExprEvalStep *innervar = &state->steps[0];
+ ExprEvalStep *hashop = &state->steps[1];
+ FunctionCallInfo fcinfo = hashop->d.hashdatum.fcinfo_data;
+ int attnum = innervar->d.var.attnum;
+
+ fcinfo->args[0].value = econtext->ecxt_innertuple->tts_values[attnum];
+ fcinfo->args[0].isnull = econtext->ecxt_innertuple->tts_isnull[attnum];
+
+ *isnull = false;
+
+ if (!fcinfo->args[0].isnull)
+ return DatumGetUInt32(hashop->d.hashdatum.fn_addr(fcinfo));
+ else
+ return (Datum) 0;
+}
+
+/*
+ * implementation for deforming and hashing an outer Var. Returns NULL on
+ * NULL input.
+ */
+static Datum
+ExecJustFetchAndHashOuterVarStrict(ExprState *state, ExprContext *econtext,
+ bool *isnull)
+{
+ ExprEvalStep *fetchop = &state->steps[0];
+ ExprEvalStep *innervar = &state->steps[1];
+ ExprEvalStep *hashop = &state->steps[2];
+ FunctionCallInfo fcinfo = hashop->d.hashdatum.fcinfo_data;
+ int attnum = innervar->d.var.attnum;
+
+ CheckOpSlotCompatibility(fetchop, econtext->ecxt_outertuple);
+ slot_getsomeattrs(econtext->ecxt_outertuple, fetchop->d.fetch.last_var);
+
+ fcinfo->args[0].value = econtext->ecxt_outertuple->tts_values[attnum];
+ fcinfo->args[0].isnull = econtext->ecxt_outertuple->tts_isnull[attnum];
+
+ if (!fcinfo->args[0].isnull)
+ {
+ *isnull = false;
+ return DatumGetUInt32(hashop->d.hashdatum.fn_addr(fcinfo));
+ }
+ else
+ {
+ /* return NULL on NULL input */
+ *isnull = true;
+ return (Datum) 0;
+ }
+}
+
+/*
+ * implementation for deforming and hashing an inner Var. Returns NULL on
+ * NULL input.
+ */
+static Datum
+ExecJustFetchAndHashInnerVarStrict(ExprState *state, ExprContext *econtext,
+ bool *isnull)
+{
+ ExprEvalStep *fetchop = &state->steps[0];
+ ExprEvalStep *innervar = &state->steps[1];
+ ExprEvalStep *hashop = &state->steps[2];
+ FunctionCallInfo fcinfo = hashop->d.hashdatum.fcinfo_data;
+ int attnum = innervar->d.var.attnum;
+
+ CheckOpSlotCompatibility(fetchop, econtext->ecxt_innertuple);
+ slot_getsomeattrs(econtext->ecxt_innertuple, fetchop->d.fetch.last_var);
+
+ fcinfo->args[0].value = econtext->ecxt_innertuple->tts_values[attnum];
+ fcinfo->args[0].isnull = econtext->ecxt_innertuple->tts_isnull[attnum];
+
+ if (!fcinfo->args[0].isnull)
+ {
+ *isnull = false;
+ return DatumGetUInt32(hashop->d.hashdatum.fn_addr(fcinfo));
+ }
+ else
+ {
+ /* return NULL on NULL input */
+ *isnull = true;
+ return (Datum) 0;
+ }
+}
+
/* Simple reference to inner Var */
static Datum
ExecJustInnerVar(ExprState *state, ExprContext *econtext, bool *isnull)
--
2.34.1
AMD7945HX NOT IN 1 million lookups, 1 hashed value.pngimage/png; name="AMD7945HX NOT IN 1 million lookups, 1 hashed value.png"Download
�PNG
IHDR ( � ��oQ � IDATx^���������`���p:l�m80L���s6�`�L�@�� !�B( �r�9�U��js�o���������3�=���>��tuUWwu��_�? B�� �^@� B
4@� B
4@� B
4@� B
4@� B
4@� B
4@� B
4@� B
4@� B
4@� B
4@� B
4@� B
4@� B
=MMM��{wz��G��v�w�����W_}E;w��w���s8������G�������_RMM�����466��1c�O�>��G���/�\�2%���-����������������>�/��2E"%$Q,�W_}U�2dH�>;�������2��W)++����^���O�k��F_�5UVV��-y��k
�p�/�5���$^[����v6�V��J�= ���g�d;�l�'i�th/ P@�Y�d��qf�t�R=��n���n���t�}v�������R_q����q��D�n��)�Q�TTTP��=EX�]�vY��:;?=Lmm-���K���S�:u�����5��9<+;��%s����{�r}����gFE��k
�p�/�5��a������xmE?W���$[ig+��"�����������������@��[:�������N����g�yF��h4������[.�>��<-[�n�7�xC���z�o
)�,X`�M�6�<FQQ�8'nx��w�q�g��I8=���d��U�����*va�/_.��<w��!�X��.��ylv�G��w���|�����m������*((0�vnB��;�W���&7��['�W��2�~�v{��s�V:�A[�� q�E���vz��J�����gc������:����j��G|��a�?�*[�l��|�����������~Z�_�f��;6������R�Y�p����������N���3�s�;��3g
�Q�F��,8C�)������b���"����/��YXX����]�Xq�;7�1{�l�[����I����.n�kr��/�����o���)�s����l�K���6m}���I�N;��I�+] �j���#>�,8��C��m��C~�eM���S��6���7�����/����~��J�[2���
U���w�V����S�ni������+��'����i
�c�8�a���'��>��3�������<6�4���;��A,�O�4Il�g�
���E����`7�5����knn�O"��� �����'�n����y��wXt�;6el����m��}�� �����ny�=��'��a�q���+ZL���r|Nz+�mI�OX�t�e�����������m���?�\�n��J
�?:���V\�����7�|�-Z��
�C:�5���3������+(?*<��[��Z9�����]vc�\���9��;�������~�}��3����
��>��Z����b��+*���y??�����������\7 a�.��c����k�����zKi ?��za���_"���q����<@� ���a��i9~��9��
.DX�p<;N�7h� ����?F�#G��O*N�Pq#�� ����������az�����7nTB���[��8��vq�\��7o6��'�q�EM���[���r�TA���w��"iz���M5����R�o����D[��VO����X62�;�����r��Q=m���-+F����B��5�Wu����vNo��z�����YH����Vn��.��,+T7p�@���+�^9��b���5�O~����N�~��0�B����(�����6��~����w���5���6���aU��%����9!7��b�f������1$|�*\�����O�N�'g���\U�G�����9'��}����E=6�In��JU�����N��T���DX>����`7�5y%H<�g��g���,q-3l���B�������6��\��-,�����z\~Ny����E�k}[�-i� ��������m�v����/�������i�3�q� ����g�����5��B?G/�8�L�7�������� >����1n�c?�f���5���?,�����J0u� �;�qW6�y��Y�k�#������O>S~�COW�v��s� � Z&O�,>�\���]!�����gY�)���Zu9VB��K��%\���u!!��}��o���7n����W,����k0��n���?o��dM���q��Zpn���,//7�s��D���C�����t�b�c����Z��ad���m�69,�'����.������$���F������W[�����8�%z�~�e��>���^�-8W���"S=''�����2~gem:WF����_n��*2mn�����6(�s����i�&�O>S����%�S�{������+'�VIdk����a.\��L���
����������x�&��{U��COW�v��s� � Z���?�����6��u�R?�����X�����Y�,aU��%\���Y���K�~���\xr?c��t���4���p�
Ik�����qx���r�0��X�����c��'o�2���-(v}�u���^-(��k�J�x2�����$�����/i����������_}d\����� ��N�����'�L�+�o��NG���zk�L[��2#F�0����'