From 820eaa19d382f7dd005831a0a20686a7d09772ce Mon Sep 17 00:00:00 2001 From: Peter Smith Date: Thu, 12 Jun 2025 15:43:50 +1000 Subject: [PATCH v20250612] VCI module - VCI_ENABLE_HOT_HASH_TABLE code --- contrib/vci/executor/meson.build | 1 + contrib/vci/executor/vci_agg.c | 53 +++++++ contrib/vci/executor/vci_hothash.c | 299 +++++++++++++++++++++++++++++++++++++ contrib/vci/include/vci.h | 3 + contrib/vci/include/vci_executor.h | 58 +++++++ contrib/vci/include/vci_mem.h | 3 + contrib/vci/vci_read_guc.c | 14 ++ 7 files changed, 431 insertions(+) create mode 100644 contrib/vci/executor/vci_hothash.c diff --git a/contrib/vci/executor/meson.build b/contrib/vci/executor/meson.build index 7f9fcc2..179b496 100644 --- a/contrib/vci/executor/meson.build +++ b/contrib/vci/executor/meson.build @@ -7,6 +7,7 @@ vci_executor_sources = files( 'vci_executor.c', 'vci_fetch_column_store.c', 'vci_gather.c', + 'vci_hothash.c', 'vci_param.c', 'vci_plan.c', 'vci_planner.c', diff --git a/contrib/vci/executor/vci_agg.c b/contrib/vci/executor/vci_agg.c index 0bd89a6..eba30a6 100644 --- a/contrib/vci/executor/vci_agg.c +++ b/contrib/vci/executor/vci_agg.c @@ -465,6 +465,12 @@ build_hash_table(VciAggState *aggstate) aggstate->aggcontext, aggstate->aggcontext, tmpmem, false); + +#ifdef VCI_ENABLE_HOT_HASH_TABLE + if (VciCanUseHotHashTable(aggstate)) + aggstate->hottable = VciBuildTupleHotHashTable(additionalsize, + aggstate->aggcontext); +#endif /* VCI_ENABLE_HOT_HASH_TABLE */ } /** @@ -593,6 +599,26 @@ lookup_hash_entry_vector(VciAggState *aggstate, } ExecStoreVirtualTuple(hashslot); + +#ifdef VCI_ENABLE_HOT_HASH_TABLE + if (aggstate->hottable) + { + uint64 key = VciGetHotHashKey(aggstate, hashslot); + + if (key < aggstate->hottable->numEntries) + { + entry = VciLookupTupleHotHashEntry(aggstate->hottable, + key, + hashslot, + &isnew); + + pergroup = (VciAggStatePerGroup) VciTupleHotHashEntryGetAdditional(aggstate->hottable, entry); + + goto found_hot_table; + } + } +#endif + /* find or create the hashtable entry using the filtered tuple */ entry = LookupTupleHashEntry(aggstate->hashtable, hashslot, @@ -601,6 +627,10 @@ lookup_hash_entry_vector(VciAggState *aggstate, pergroup = (VciAggStatePerGroup) TupleHashEntryGetAdditional(aggstate->hashtable, entry); +#ifdef VCI_ENABLE_HOT_HASH_TABLE +found_hot_table: +#endif + if (isnew && aggstate->numaggs) { /* initialize aggregates for new tuple group */ @@ -979,6 +1009,25 @@ vci_agg_retrieve_hash_table(VciAggState *aggstate) TupleHashEntry vci_agg_find_group_from_hash_table(VciAggState *aggstate) { +#ifdef VCI_ENABLE_HOT_HASH_TABLE + VciTupleHotHashTable hottable = aggstate->hottable; + + if (aggstate->hottable) + { + while (hottable->iterator < hottable->numEntries) + { + TupleHashEntry entry; + + entry = (TupleHashEntry) hottable->entries[hottable->iterator++]; + + if (entry == NULL) + continue; + + return entry; + } + } +#endif + while (!aggstate->agg_done) { return (TupleHashEntry) ScanTupleHashTable(aggstate->hashtable, &aggstate->hashiter); @@ -1794,6 +1843,10 @@ vci_agg_ReScanCustomPlan(CustomScanState *node) if (aggstate->vci.css.ss.ps.lefttree->chgParam == NULL) { ResetTupleHashIterator(aggstate->hashtable, &aggstate->hashiter); +#ifdef VCI_ENABLE_HOT_HASH_TABLE + if (aggstate->hottable) + aggstate->hottable->iterator = 0; +#endif return; } } diff --git a/contrib/vci/executor/vci_hothash.c b/contrib/vci/executor/vci_hothash.c new file mode 100644 index 0000000..a8e4ed1 --- /dev/null +++ b/contrib/vci/executor/vci_hothash.c @@ -0,0 +1,299 @@ +/*------------------------------------------------------------------------- + * + * vci_hothash.c + * When there is no has collision in hash table and hash keys are small, + * performance can be improved by preparing direct map table before the + * original hash table. + * + * Portions Copyright (c) 2025, PostgreSQL Global Development Group + * + * IDENTIFICATION + * contrib/vci/executor/vci_hothash.c + */ +#include "postgres.h" + +#include "catalog/pg_type.h" +#include "executor/tuptable.h" +#include "fmgr.h" +#include "nodes/execnodes.h" +#include "utils/palloc.h" + +#include "vci.h" +#include "vci_mem.h" + +#include "vci_executor.h" + +#ifdef VCI_ENABLE_HOT_HASH_TABLE + +/** + * Determine if Hot Hashtable is usable + * + * @param[in] aggstate Pointer to VCI Agg State + * @return Return true if usable, false if not + * + * Usable datatypes are + * - Basic integer type + * - 1 character only char + */ +bool +VciCanUseHotHashTable(VciAggState *aggstate) +{ + VciScanState *scanstate; + TupleTableSlot *pseudo_inputslot; + TupleDesc tupleDesc; + int i; + uint64 shift = 0; + + scanstate = (VciScanState *) outerPlanState(aggstate); + pseudo_inputslot = scanstate->vci.css.ss.ps.ps_ResultTupleSlot; + tupleDesc = pseudo_inputslot->tts_tupleDescriptor; + + for (i = 0; i < aggstate->num_hash_needed; i++) + { + int varNumber; + Form_pg_attribute attr; + + varNumber = aggstate->hash_needed[i] - 1; + attr = TupleDescAttr(tupleDesc, varNumber); + + if (VciGuc.hot_hashtable_bits < shift) + return false; + + switch (attr->atttypid) + { + case BOOLOID: + shift += 1; + break; + + case CHAROID: + shift += 8; + break; + + case INT2OID: + shift += 16; + break; + + case INT4OID: + shift += 32; + break; + + case INT8OID: + shift += 64; + break; + + case BPCHAROID: + if (attr->atttypmod != VARHDRSZ + 1) + return false; + shift += 8; + break; + + default: + return false; + } + } + + return true; +} + +/** + * Create and return new Hot Hashtable + * + * @param[in] additionalsize size(byte) of additional data + * @param[in] tablecxt memory context for allocating data in Hot hashtable + * @return Pointer to Hot hashtable + */ +VciTupleHotHashTable +VciBuildTupleHotHashTable(Size additionalsize, MemoryContext tablecxt) +{ + VciTupleHotHashTable hottable; + Size entrysize; + + additionalsize = MAXALIGN(additionalsize); + entrysize = sizeof(TupleHashEntryData) + additionalsize; + + hottable = (VciTupleHotHashTable) MemoryContextAlloc(tablecxt, + sizeof(VciTupleHotHashTableData)); + + hottable->tablecxt = tablecxt; + hottable->additionalsize = additionalsize; + hottable->entrysize = entrysize; + hottable->tableslot = NULL; /* will be made on first lookup */ + hottable->inputslot = NULL; + + hottable->numEntries = 1U << (VciGuc.hot_hashtable_bits - 1); + hottable->entries = palloc0(sizeof(TupleHashEntry) * hottable->numEntries); + + hottable->iterator = 0; + + return hottable; +} + +/** + * Return entry corresponds to key from hot hashtable. + * If the entry doesn't exists, it is created and then returned. + * + * @param[in,out] hottable Pointer to Hot hastable + * @param[in] key hash key + * @param[in] slot tuple to be stored in hash + * @param[out] isnew_p Return true if key is a new entry in hot hashtable, + * false if not + * @return Pointer to hash entry + * + * The tuple table slot given in slot is converted to minimal tuple, + * then copied and stored in internal memory context of hottable. + */ +TupleHashEntry +VciLookupTupleHotHashEntry(VciTupleHotHashTable hottable, uint64 key, + TupleTableSlot *slot, + bool *isnew_p) +{ + TupleHashEntry entry; + MemoryContext oldContext; + bool isnew = false; + + Assert(key < hottable->numEntries); + + /* If first time through, clone the input slot to make table slot */ + if (hottable->tableslot == NULL) + { + TupleDesc tupdesc; + + oldContext = MemoryContextSwitchTo(hottable->tablecxt); + + /* + * We copy the input tuple descriptor just for safety --- we assume + * all input tuples will have equivalent descriptors. + */ + tupdesc = CreateTupleDescCopy(slot->tts_tupleDescriptor); + hottable->tableslot = MakeSingleTupleTableSlot(tupdesc, + &TTSOpsMinimalTuple); + MemoryContextSwitchTo(oldContext); + } + + entry = hottable->entries[key]; + + if (entry == NULL) + { + oldContext = MemoryContextSwitchTo(hottable->tablecxt); + + entry = palloc0(hottable->entrysize); + + /* + * Copy the first tuple into the table context, and request + * additionalsize extra bytes before the allocation. + * + * The caller can get a pointer to the additional data with + * TupleHashEntryGetAdditional(), and store arbitrary data there. + * Placing both the tuple and additional data in the same + * allocation avoids the need to store an extra pointer in + * TupleHashEntryData or allocate an additional chunk. + */ + entry->firstTuple = ExecCopySlotMinimalTupleExtra(slot, hottable->additionalsize); + MemoryContextSwitchTo(oldContext); + + hottable->entries[key] = entry; + + isnew = true; + } + + if (isnew_p) + *isnew_p = isnew; + + return entry; +} + +/** + * Returns hash key value for input hashslot + * + * @param[in] aggstate Pointer to VCI Agg State + * @param[in] hashslot Input tuple table slot + * @return hash key + * + * @note hashslot must be in Virtual Tuple format + */ +uint64 +VciGetHotHashKey(VciAggState *aggstate, TupleTableSlot *hashslot) +{ + TupleDesc tupleDesc; + int i; + uint64 key = 0, + shift = 0; + + tupleDesc = hashslot->tts_tupleDescriptor; + + /* Make sure the tuple is fully deconstructed */ + slot_getallattrs(hashslot); + + for (i = 0; i < aggstate->num_hash_needed; i++) + { + int varNumber = aggstate->hash_needed[i] - 1; + + Assert(varNumber < hashslot->tts_nvalid); + + if (hashslot->tts_isnull[varNumber]) + { + return UINT64_MAX; + } + else + { + Form_pg_attribute attr; + Datum value; + + attr = TupleDescAttr(tupleDesc, varNumber); + value = hashslot->tts_values[varNumber]; + + switch (attr->atttypid) + { + case BOOLOID: + key |= (DatumGetBool(value) ? 1 : 0) << shift; + shift += 1; + break; + + case CHAROID: + key |= ((unsigned char) DatumGetChar(value)) << shift; + shift += 8; + break; + + case INT2OID: + key |= ((uint16) DatumGetInt16(value)) << shift; + shift += 16; + break; + + case INT4OID: + key |= ((uint32) DatumGetInt32(value)) << shift; + shift += 32; + break; + + case INT8OID: + key |= ((uint64) DatumGetInt64(value)) << shift; + shift += 64; + break; + + case BPCHAROID: + { + BpChar *source = DatumGetBpCharPP(value); + char *s; + + if (1 < VARSIZE_ANY_EXHDR(source)) + return UINT64_MAX; + + s = VARDATA_ANY(source); + + key |= *((uint8 *) s) << shift; + shift += 8; + } + break; + + default: + /* LCOV_EXCL_START */ + elog(PANIC, "should not reach here"); + break; + /* LCOV_EXCL_STOP */ + } + } + } + + return key; +} + +#endif /* VCI_ENABLE_HOT_HASH_TABLE */ diff --git a/contrib/vci/include/vci.h b/contrib/vci/include/vci.h index 3e4426a..a0abdd5 100644 --- a/contrib/vci/include/vci.h +++ b/contrib/vci/include/vci.h @@ -37,6 +37,9 @@ #define VCI_INTERNAL_RELATION_TEMPLATE "vci_%010d_%05d_%c" +/** Enables Hot hashtable */ +#define VCI_ENABLE_HOT_HASH_TABLE + /** Use compact form to keep varlena with short header at some parts */ #define VCI_USE_COMPACT_VARLENA diff --git a/contrib/vci/include/vci_executor.h b/contrib/vci/include/vci_executor.h index eb40f74..d060e1f 100644 --- a/contrib/vci/include/vci_executor.h +++ b/contrib/vci/include/vci_executor.h @@ -321,6 +321,60 @@ typedef struct VciVPContext extern void VciExecEvalVectorProcessing(VciVPContext *vpcontext, ExprContext *econtext, int max_slots); extern VciVPContext *VciBuildVectorProcessing(Expr *node, PlanState *parent, ExprContext *econtext, uint16 *skip_list); + +#ifdef VCI_ENABLE_HOT_HASH_TABLE +/* ---------------- + * Hot hashtable + * ---------------- + */ + +/** + * Hot hash table data struct + */ +typedef struct VciTupleHotHashTableData +{ + int numEntries; /* Number of entry */ + TupleHashEntry *entries; /* Array of entry */ + + MemoryContext tablecxt; /* memory context containing table */ + Size additionalsize; /* size of additional data */ + Size entrysize; /* actual size to make each hash entry */ + TupleTableSlot *tableslot; /* slot for referencing table entries */ + /* The following fields are set transiently for each table search: */ + TupleTableSlot *inputslot; /* current input tuple's slot */ + + int iterator; /* Iterator used during Hot hast table scan */ +} VciTupleHotHashTableData; + +typedef struct VciTupleHotHashTableData *VciTupleHotHashTable; + +/* + * Get a pointer into the additional space allocated for this entry. The + * memory will be maxaligned and zeroed. + * + * The amount of space available is the additionalsize requested in the call + * to BuildTupleHashTable(). If additionalsize was specified as zero, return + * NULL. + * + * Same as TupleHashEntryGetAdditional, but for VciTuplHotHashTable. + */ +static inline void * +VciTupleHotHashEntryGetAdditional(VciTupleHotHashTable hashtable, TupleHashEntry entry) +{ + if (hashtable->additionalsize > 0) + return (char *) entry->firstTuple - hashtable->additionalsize; + else + return NULL; +} + +extern VciTupleHotHashTable VciBuildTupleHotHashTable(Size entrysize, MemoryContext tablecxt); +extern TupleHashEntry VciLookupTupleHotHashEntry(VciTupleHotHashTable hashtable, uint64 key, + TupleTableSlot *slot, bool *isnew_p); +extern bool VciCanUseHotHashTable(struct VciAggState *aggstate); +extern uint64 VciGetHotHashKey(struct VciAggState *aggstate, TupleTableSlot *hashslot); + +#endif /* VCI_ENABLE_HOT_HASH_TABLE */ + /* ---------------- * Projection information for VCI * ---------------- @@ -599,6 +653,10 @@ typedef struct VciAggState bool table_filled; /* hash table filled yet? */ TupleHashIterator hashiter; /* for iterating through hash table */ +#ifdef VCI_ENABLE_HOT_HASH_TABLE + VciTupleHotHashTable hottable; +#endif + /* * aggregation function changes its behaviour by checking AggState * Therefore, ExecEvalExpr() shows dummy AggState, not VciAggState diff --git a/contrib/vci/include/vci_mem.h b/contrib/vci/include/vci_mem.h index 93a814a..7f9d2cb 100644 --- a/contrib/vci/include/vci_mem.h +++ b/contrib/vci/include/vci_mem.h @@ -67,6 +67,9 @@ typedef struct VciGucStruct /* GUC parameters for internal use */ bool enable_ros_control_daemon; +#ifdef VCI_ENABLE_HOT_HASH_TABLE + int hot_hashtable_bits; +#endif } VciGucStruct; diff --git a/contrib/vci/vci_read_guc.c b/contrib/vci/vci_read_guc.c index 99914cb..33b4ab1 100644 --- a/contrib/vci/vci_read_guc.c +++ b/contrib/vci/vci_read_guc.c @@ -341,6 +341,20 @@ static struct config_int VciConfigureNamesInt[] = NULL, NULL, NULL, }, +#ifdef VCI_ENABLE_HOT_HASH_TABLE + { + { + "vci.hot_hashtable_bits", + PGC_USERSET, DEVELOPER_OPTIONS, + "Sets the number of bits specified by the size of hot hashtable entries.", + NULL, + }, + &VciGuc.hot_hashtable_bits, + 16, 8, 24, + NULL, NULL, NULL, + }, +#endif + }; static const struct config_enum_entry table_scan_policy_options[] = { -- 1.8.3.1