From 0716ad3e017196faa2746b169f7add9f92b02adf Mon Sep 17 00:00:00 2001 From: Andres Freund Date: Thu, 21 Jul 2016 12:51:14 -0700 Subject: [PATCH 4/4] WIP: execGrouping.c simplehash --- src/backend/executor/execGrouping.c | 146 +++++++++++++++--------------------- src/backend/executor/nodeAgg.c | 33 ++++---- src/backend/executor/nodeSetOp.c | 24 +++--- src/backend/executor/nodeSubplan.c | 6 +- src/include/executor/executor.h | 12 +++ src/include/nodes/execnodes.h | 38 ++++++---- 6 files changed, 124 insertions(+), 135 deletions(-) diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c index 808275a..21089c8 100644 --- a/src/backend/executor/execGrouping.c +++ b/src/backend/executor/execGrouping.c @@ -22,13 +22,26 @@ #include "miscadmin.h" #include "utils/lsyscache.h" #include "utils/memutils.h" +#include "access/htup_details.h" +static uint32 TupleHashTableHash(struct tuplehash_hash *tb, const MinimalTuple tuple); +static int TupleHashTableMatch(struct tuplehash_hash *tb, const MinimalTuple tuple1, const MinimalTuple tuple2); -static TupleHashTable CurTupleHashTable = NULL; - -static uint32 TupleHashTableHash(const void *key, Size keysize); -static int TupleHashTableMatch(const void *key1, const void *key2, - Size keysize); +/* + * Define parameters for tuple hash table code generation. The interface is + * *also* defined in executor.h. + */ +#define SH_PREFIX tuplehash +#define SH_KEYTYPE TupleHashEntryKey +#define SH_KEY key +#define SH_CONTAINS TupleHashEntryData +#define SH_HASH_KEY(tb, key) TupleHashTableHash(tb, key.firstTuple) +#define SH_EQUAL(tb, a, b) TupleHashTableMatch(tb, a.firstTuple, b.firstTuple) == 0 +#define SH_SCOPE extern +#define SH_STORE_HASH +#define SH_GET_HASH(tb, a) a->hash +#define SH_DEFINE +#include "lib/simplehash.h" /***************************************************************************** @@ -279,10 +292,8 @@ BuildTupleHashTable(int numCols, AttrNumber *keyColIdx, MemoryContext tablecxt, MemoryContext tempcxt) { TupleHashTable hashtable; - HASHCTL hash_ctl; Assert(nbuckets > 0); - Assert(entrysize >= sizeof(TupleHashEntryData)); /* Limit initial table size request to not more than work_mem */ nbuckets = Min(nbuckets, (long) ((work_mem * 1024L) / entrysize)); @@ -297,20 +308,14 @@ BuildTupleHashTable(int numCols, AttrNumber *keyColIdx, hashtable->tablecxt = tablecxt; hashtable->tempcxt = tempcxt; hashtable->entrysize = entrysize; - hashtable->tableslot = NULL; /* will be made on first lookup */ + hashtable->tableslot1 = NULL; /* will be made on first lookup */ + hashtable->tableslot2 = NULL; /* will be made on first lookup */ hashtable->inputslot = NULL; hashtable->in_hash_funcs = NULL; hashtable->cur_eq_funcs = NULL; - MemSet(&hash_ctl, 0, sizeof(hash_ctl)); - hash_ctl.keysize = sizeof(TupleHashEntryData); - hash_ctl.entrysize = entrysize; - hash_ctl.hash = TupleHashTableHash; - hash_ctl.match = TupleHashTableMatch; - hash_ctl.hcxt = tablecxt; - hashtable->hashtab = hash_create("TupleHashTable", nbuckets, - &hash_ctl, - HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT); + hashtable->hashtab = tuplehash_create(tablecxt, nbuckets); + hashtable->hashtab->private = hashtable; return hashtable; } @@ -331,14 +336,13 @@ TupleHashEntry LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot, bool *isnew) { - TupleHashEntry entry; + TupleHashEntryData *entry; MemoryContext oldContext; - TupleHashTable saveCurHT; - TupleHashEntryData dummy; bool found; + TupleHashEntryKey key; /* If first time through, clone the input slot to make table slot */ - if (hashtable->tableslot == NULL) + if (hashtable->tableslot1 == NULL) { TupleDesc tupdesc; @@ -349,7 +353,8 @@ LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot, * all input tuples will have equivalent descriptors. */ tupdesc = CreateTupleDescCopy(slot->tts_tupleDescriptor); - hashtable->tableslot = MakeSingleTupleTableSlot(tupdesc); + hashtable->tableslot1 = MakeSingleTupleTableSlot(tupdesc); + hashtable->tableslot2 = MakeSingleTupleTableSlot(tupdesc); MemoryContextSwitchTo(oldContext); } @@ -358,26 +363,17 @@ LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot, /* * Set up data needed by hash and match functions - * - * We save and restore CurTupleHashTable just in case someone manages to - * invoke this code re-entrantly. */ hashtable->inputslot = slot; hashtable->in_hash_funcs = hashtable->tab_hash_funcs; hashtable->cur_eq_funcs = hashtable->tab_eq_funcs; - saveCurHT = CurTupleHashTable; - CurTupleHashTable = hashtable; - - /* Search the hash table */ - dummy.firstTuple = NULL; /* flag to reference inputslot */ - entry = (TupleHashEntry) hash_search(hashtable->hashtab, - &dummy, - isnew ? HASH_ENTER : HASH_FIND, - &found); + key.firstTuple = NULL; if (isnew) { + entry = tuplehash_insert(hashtable->hashtab, key, &found); + if (found) { /* found pre-existing entry */ @@ -385,24 +381,19 @@ LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot, } else { - /* - * created new entry - * - * Zero any caller-requested space in the entry. (This zaps the - * "key data" dynahash.c copied into the new entry, but we don't - * care since we're about to overwrite it anyway.) - */ - MemSet(entry, 0, hashtable->entrysize); - - /* Copy the first tuple into the table context */ - MemoryContextSwitchTo(hashtable->tablecxt); - entry->firstTuple = ExecCopySlotMinimalTuple(slot); - + /* FIXME: fill */ *isnew = true; + entry->additional = NULL; + MemoryContextSwitchTo(hashtable->tablecxt); + /* Copy the first tuple into the table context */ + entry->key.firstTuple = ExecCopySlotMinimalTuple(slot); } } + else + { + entry = tuplehash_lookup(hashtable->hashtab, key); + } - CurTupleHashTable = saveCurHT; MemoryContextSwitchTo(oldContext); @@ -425,8 +416,7 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot, { TupleHashEntry entry; MemoryContext oldContext; - TupleHashTable saveCurHT; - TupleHashEntryData dummy; + TupleHashEntryKey key; /* Need to run the hash functions in short-lived context */ oldContext = MemoryContextSwitchTo(hashtable->tempcxt); @@ -441,20 +431,10 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot, hashtable->in_hash_funcs = hashfunctions; hashtable->cur_eq_funcs = eqfunctions; - saveCurHT = CurTupleHashTable; - CurTupleHashTable = hashtable; - /* Search the hash table */ - dummy.firstTuple = NULL; /* flag to reference inputslot */ - entry = (TupleHashEntry) hash_search(hashtable->hashtab, - &dummy, - HASH_FIND, - NULL); - - CurTupleHashTable = saveCurHT; - + key.firstTuple = NULL; /* flag to reference inputslot */ + entry = tuplehash_lookup(hashtable->hashtab, key); MemoryContextSwitchTo(oldContext); - return entry; } @@ -474,16 +454,14 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot, * Also, the caller must select an appropriate memory context for running * the hash functions. (dynahash.c doesn't change CurrentMemoryContext.) */ -static uint32 -TupleHashTableHash(const void *key, Size keysize) +static uint32 TupleHashTableHash(struct tuplehash_hash *tb, const MinimalTuple tuple) { - MinimalTuple tuple = ((const TupleHashEntryData *) key)->firstTuple; - TupleTableSlot *slot; - TupleHashTable hashtable = CurTupleHashTable; + TupleHashTable hashtable = tb->private; int numCols = hashtable->numCols; AttrNumber *keyColIdx = hashtable->keyColIdx; - FmgrInfo *hashfunctions; uint32 hashkey = 0; + TupleTableSlot *slot; + FmgrInfo *hashfunctions; int i; if (tuple == NULL) @@ -495,8 +473,7 @@ TupleHashTableHash(const void *key, Size keysize) else { /* Process a tuple already stored in the table */ - /* (this case never actually occurs in current dynahash.c code) */ - slot = hashtable->tableslot; + slot = hashtable->tableslot1; ExecStoreMinimalTuple(tuple, slot, false); hashfunctions = hashtable->tab_hash_funcs; } @@ -537,28 +514,25 @@ TupleHashTableHash(const void *key, Size keysize) * the compare functions. (dynahash.c doesn't change CurrentMemoryContext.) */ static int -TupleHashTableMatch(const void *key1, const void *key2, Size keysize) +TupleHashTableMatch(struct tuplehash_hash *tb, const MinimalTuple tuple1, const MinimalTuple tuple2) { - MinimalTuple tuple1 = ((const TupleHashEntryData *) key1)->firstTuple; - -#ifdef USE_ASSERT_CHECKING - MinimalTuple tuple2 = ((const TupleHashEntryData *) key2)->firstTuple; -#endif TupleTableSlot *slot1; TupleTableSlot *slot2; - TupleHashTable hashtable = CurTupleHashTable; + TupleHashTable hashtable = tb->private; - /* - * We assume that dynahash.c will only ever call us with the first - * argument being an actual table entry, and the second argument being - * LookupTupleHashEntry's dummy TupleHashEntryData. The other direction - * could be supported too, but is not currently used by dynahash.c. - */ Assert(tuple1 != NULL); - slot1 = hashtable->tableslot; + slot1 = hashtable->tableslot1; ExecStoreMinimalTuple(tuple1, slot1, false); - Assert(tuple2 == NULL); - slot2 = hashtable->inputslot; + + if (tuple2 != NULL) + { + slot2 = hashtable->tableslot2; + ExecStoreMinimalTuple(tuple2, slot2, false); + } + else + { + slot2 = hashtable->inputslot; + } /* For crosstype comparisons, the inputslot must be first */ if (execTuplesMatch(slot2, diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c index b3187e6..31f25ae 100644 --- a/src/backend/executor/nodeAgg.c +++ b/src/backend/executor/nodeAgg.c @@ -440,14 +440,7 @@ typedef struct AggStatePerPhaseData * distinct set of GROUP BY column values. We compute the hash key from * the GROUP BY columns. */ -typedef struct AggHashEntryData *AggHashEntry; - -typedef struct AggHashEntryData -{ - TupleHashEntryData shared; /* common header for hash table entries */ - /* per-aggregate transition status array */ - AggStatePerGroupData pergroup[FLEXIBLE_ARRAY_MEMBER]; -} AggHashEntryData; +typedef TupleHashEntryData *AggHashEntry; static void initialize_phase(AggState *aggstate, int newphase); static TupleTableSlot *fetch_input_tuple(AggState *aggstate); @@ -1658,8 +1651,7 @@ build_hash_table(AggState *aggstate) Assert(node->aggstrategy == AGG_HASHED); Assert(node->numGroups > 0); - entrysize = offsetof(AggHashEntryData, pergroup) + - aggstate->numaggs * sizeof(AggStatePerGroupData); + entrysize = sizeof(AggHashEntry); aggstate->hashtable = BuildTupleHashTable(node->numCols, node->grpColIdx, @@ -1730,7 +1722,7 @@ hash_agg_entry_size(int numAggs) Size entrysize; /* This must match build_hash_table */ - entrysize = offsetof(AggHashEntryData, pergroup) + + entrysize = sizeof(TupleHashEntryData) + numAggs * sizeof(AggStatePerGroupData); entrysize = MAXALIGN(entrysize); /* Account for hashtable overhead (assuming fill factor = 1) */ @@ -1755,7 +1747,10 @@ lookup_hash_entry(AggState *aggstate, TupleTableSlot *inputslot) /* if first time through, initialize hashslot by cloning input slot */ if (hashslot->tts_tupleDescriptor == NULL) { - ExecSetSlotDescriptor(hashslot, inputslot->tts_tupleDescriptor); + MemoryContext oldContext = MemoryContextSwitchTo(hashslot->tts_mcxt); + /* get rid of constraints */ + ExecSetSlotDescriptor(hashslot, CreateTupleDescCopy(inputslot->tts_tupleDescriptor)); + MemoryContextSwitchTo(oldContext); /* Make sure all unused columns are NULLs */ ExecStoreAllNullTuple(hashslot); } @@ -1777,8 +1772,10 @@ lookup_hash_entry(AggState *aggstate, TupleTableSlot *inputslot) if (isnew) { + entry->additional = MemoryContextAlloc(aggstate->hashtable->tablecxt, + sizeof(AggStatePerGroupData) * aggstate->numtrans); /* initialize aggregates for new tuple group */ - initialize_aggregates(aggstate, entry->pergroup, 0); + initialize_aggregates(aggstate, entry->additional, 0); } return entry; @@ -2203,9 +2200,9 @@ agg_fill_hash_table(AggState *aggstate) /* Advance the aggregates */ if (DO_AGGSPLIT_COMBINE(aggstate->aggsplit)) - combine_aggregates(aggstate, entry->pergroup); + combine_aggregates(aggstate, entry->additional); else - advance_aggregates(aggstate, entry->pergroup); + advance_aggregates(aggstate, entry->additional); /* Reset per-input-tuple context after each tuple */ ResetExprContext(tmpcontext); @@ -2246,7 +2243,7 @@ agg_retrieve_hash_table(AggState *aggstate) /* * Find the next entry in the hash table */ - entry = (AggHashEntry) ScanTupleHashTable(&aggstate->hashiter); + entry = (AggHashEntry) ScanTupleHashTable(aggstate->hashtable, &aggstate->hashiter); if (entry == NULL) { /* No more entries in hashtable, so done */ @@ -2267,11 +2264,11 @@ agg_retrieve_hash_table(AggState *aggstate) * Store the copied first input tuple in the tuple table slot reserved * for it, so that it can be used in ExecProject. */ - ExecStoreMinimalTuple(entry->shared.firstTuple, + ExecStoreMinimalTuple(entry->key.firstTuple, firstSlot, false); - pergroup = entry->pergroup; + pergroup = entry->additional; finalize_aggregates(aggstate, peragg, pergroup, 0); diff --git a/src/backend/executor/nodeSetOp.c b/src/backend/executor/nodeSetOp.c index 2d81d46..ce393e1 100644 --- a/src/backend/executor/nodeSetOp.c +++ b/src/backend/executor/nodeSetOp.c @@ -71,13 +71,9 @@ typedef struct SetOpStatePerGroupData * representative tuple and the duplicate counts for each distinct set * of grouping columns. We compute the hash key from the grouping columns. */ -typedef struct SetOpHashEntryData *SetOpHashEntry; +typedef TupleHashEntryData SetOpHashEntryData; -typedef struct SetOpHashEntryData -{ - TupleHashEntryData shared; /* common header for hash table entries */ - SetOpStatePerGroupData pergroup; -} SetOpHashEntryData; +typedef SetOpHashEntryData *SetOpHashEntry; static TupleTableSlot *setop_retrieve_direct(SetOpState *setopstate); @@ -388,10 +384,14 @@ setop_fill_hash_table(SetOpState *setopstate) /* If new tuple group, initialize counts */ if (isnew) - initialize_counts(&entry->pergroup); + { + entry->additional = MemoryContextAlloc(setopstate->hashtable->tablecxt, + sizeof(SetOpStatePerGroupData)); + initialize_counts(entry->additional); + } /* Advance the counts */ - advance_counts(&entry->pergroup, flag); + advance_counts(entry->additional, flag); } else { @@ -404,7 +404,7 @@ setop_fill_hash_table(SetOpState *setopstate) /* Advance the counts if entry is already present */ if (entry) - advance_counts(&entry->pergroup, flag); + advance_counts(entry->additional, flag); } /* Must reset temp context after each hashtable lookup */ @@ -438,7 +438,7 @@ setop_retrieve_hash_table(SetOpState *setopstate) /* * Find the next entry in the hash table */ - entry = (SetOpHashEntry) ScanTupleHashTable(&setopstate->hashiter); + entry = (SetOpHashEntry) ScanTupleHashTable(setopstate->hashtable, &setopstate->hashiter); if (entry == NULL) { /* No more entries in hashtable, so done */ @@ -450,12 +450,12 @@ setop_retrieve_hash_table(SetOpState *setopstate) * See if we should emit any copies of this tuple, and if so return * the first copy. */ - set_output_count(setopstate, &entry->pergroup); + set_output_count(setopstate, entry->additional); if (setopstate->numOutput > 0) { setopstate->numOutput--; - return ExecStoreMinimalTuple(entry->shared.firstTuple, + return ExecStoreMinimalTuple(entry->key.firstTuple, resultTupleSlot, false); } diff --git a/src/backend/executor/nodeSubplan.c b/src/backend/executor/nodeSubplan.c index e503494..df9f04f 100644 --- a/src/backend/executor/nodeSubplan.c +++ b/src/backend/executor/nodeSubplan.c @@ -626,10 +626,10 @@ findPartialMatch(TupleHashTable hashtable, TupleTableSlot *slot, TupleHashEntry entry; InitTupleHashIterator(hashtable, &hashiter); - while ((entry = ScanTupleHashTable(&hashiter)) != NULL) + while ((entry = ScanTupleHashTable(hashtable, &hashiter)) != NULL) { - ExecStoreMinimalTuple(entry->firstTuple, hashtable->tableslot, false); - if (!execTuplesUnequal(slot, hashtable->tableslot, + ExecStoreMinimalTuple(entry->key.firstTuple, hashtable->tableslot1, false); + if (!execTuplesUnequal(slot, hashtable->tableslot1, numCols, keyColIdx, eqfunctions, hashtable->tempcxt)) diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h index 39521ed..0addcbf 100644 --- a/src/include/executor/executor.h +++ b/src/include/executor/executor.h @@ -95,6 +95,18 @@ extern PGDLLIMPORT ExecutorEnd_hook_type ExecutorEnd_hook; typedef bool (*ExecutorCheckPerms_hook_type) (List *, bool); extern PGDLLIMPORT ExecutorCheckPerms_hook_type ExecutorCheckPerms_hook; +/* + * Define paramters necessary to generate the tuple hash table interface + * functions. It seems better to do this in executor.h, rather than + * execnodes.h, which is more widely included. + */ +#define SH_PREFIX tuplehash +#define SH_KEYTYPE TupleHashEntryKey +#define SH_KEY key +#define SH_CONTAINS TupleHashEntryData +#define SH_SCOPE extern +#define SH_DECLARE +#include "lib/simplehash.h" /* * prototypes from functions in execAmi.c diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index e7fd7bd..6fd9ff9 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -496,16 +496,26 @@ typedef struct ExecAuxRowMark typedef struct TupleHashEntryData *TupleHashEntry; typedef struct TupleHashTableData *TupleHashTable; +typedef struct TupleHashEntryKey +{ + MinimalTuple firstTuple; /* copy of first tuple in this group */ +} TupleHashEntryKey; + typedef struct TupleHashEntryData { - /* firstTuple must be the first field in this struct! */ - MinimalTuple firstTuple; /* copy of first tuple in this group */ - /* there may be additional data beyond the end of this struct */ -} TupleHashEntryData; /* VARIABLE LENGTH STRUCT */ + TupleHashEntryKey key; + void *additional; + uint32 status; + uint32 hash; +} TupleHashEntryData; + +/* forward declare, to avoid including hash related code here */ +struct tuplehash_hash; +typedef uint32 TupleHashIterator; typedef struct TupleHashTableData { - HTAB *hashtab; /* underlying dynahash table */ + struct 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) */ @@ -513,31 +523,27 @@ typedef struct TupleHashTableData MemoryContext tablecxt; /* memory context containing table */ MemoryContext tempcxt; /* context for function evaluations */ Size entrysize; /* actual size to make each hash entry */ - TupleTableSlot *tableslot; /* slot for referencing table entries */ + TupleTableSlot *tableslot1; /* slot for referencing table entries */ + TupleTableSlot *tableslot2; /* 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) */ FmgrInfo *cur_eq_funcs; /* equality functions for input vs. table */ } TupleHashTableData; -typedef HASH_SEQ_STATUS TupleHashIterator; - /* * Use InitTupleHashIterator/TermTupleHashIterator for a read/write scan. * Use ResetTupleHashIterator if the table can be frozen (in this case no * explicit scan termination is needed). */ #define InitTupleHashIterator(htable, iter) \ - hash_seq_init(iter, (htable)->hashtab) + tuplehash_start_iterate(htable->hashtab, iter) #define TermTupleHashIterator(iter) \ - hash_seq_term(iter) + (void)0 #define ResetTupleHashIterator(htable, iter) \ - do { \ - hash_freeze((htable)->hashtab); \ - hash_seq_init(iter, (htable)->hashtab); \ - } while (0) -#define ScanTupleHashTable(iter) \ - ((TupleHashEntry) hash_seq_search(iter)) + InitTupleHashIterator(htable, iter) +#define ScanTupleHashTable(htable, iter) \ + tuplehash_iterate(htable->hashtab, iter) /* ---------------------------------------------------------------- -- 2.8.1