execGrouping.c File Reference

#include "postgres.h"
#include "access/parallel.h"
#include "common/hashfn.h"
#include "executor/executor.h"
#include "miscadmin.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
#include "lib/simplehash.h"

Include dependency graph for execGrouping.c:

Go to the source code of this file.

Macros
#define	SH_PREFIX   tuplehash
#define	SH_ELEMENT_TYPE   TupleHashEntryData
#define	SH_KEY_TYPE   MinimalTuple
#define	SH_KEY   firstTuple
#define	SH_HASH_KEY(tb, key)   TupleHashTableHash_internal(tb, key)
#define	SH_EQUAL(tb, a, b)   TupleHashTableMatch(tb, a, b) == 0
#define	SH_SCOPE   extern
#define	SH_STORE_HASH
#define	SH_GET_HASH(tb, a)   a->hash
#define	SH_DEFINE

Functions
static int	TupleHashTableMatch (struct tuplehash_hash *tb, const MinimalTuple tuple1, const MinimalTuple tuple2)
static uint32	TupleHashTableHash_internal (struct tuplehash_hash *tb, const MinimalTuple tuple)
static TupleHashEntry	LookupTupleHashEntry_internal (TupleHashTable hashtable, TupleTableSlot *slot, bool *isnew, uint32 hash)
ExprState *	execTuplesMatchPrepare (TupleDesc desc, int numCols, const AttrNumber *keyColIdx, const Oid *eqOperators, const Oid *collations, PlanState *parent)
void	execTuplesHashPrepare (int numCols, const Oid *eqOperators, Oid **eqFuncOids, FmgrInfo **hashFunctions)
TupleHashTable	BuildTupleHashTableExt (PlanState *parent, TupleDesc inputDesc, int numCols, AttrNumber *keyColIdx, const Oid *eqfuncoids, FmgrInfo *hashfunctions, Oid *collations, long nbuckets, Size additionalsize, MemoryContext metacxt, MemoryContext tablecxt, MemoryContext tempcxt, bool use_variable_hash_iv)
TupleHashTable	BuildTupleHashTable (PlanState *parent, TupleDesc inputDesc, int numCols, AttrNumber *keyColIdx, const Oid *eqfuncoids, FmgrInfo *hashfunctions, Oid *collations, long nbuckets, Size additionalsize, MemoryContext tablecxt, MemoryContext tempcxt, bool use_variable_hash_iv)
void	ResetTupleHashTable (TupleHashTable hashtable)
TupleHashEntry	LookupTupleHashEntry (TupleHashTable hashtable, TupleTableSlot *slot, bool *isnew, uint32 *hash)
uint32	TupleHashTableHash (TupleHashTable hashtable, TupleTableSlot *slot)
TupleHashEntry	LookupTupleHashEntryHash (TupleHashTable hashtable, TupleTableSlot *slot, bool *isnew, uint32 hash)
TupleHashEntry	FindTupleHashEntry (TupleHashTable hashtable, TupleTableSlot *slot, ExprState *eqcomp, FmgrInfo *hashfunctions)

Macro Definition Documentation

SH_DEFINE

#define SH_DEFINE

Definition at line 45 of file execGrouping.c.

SH_ELEMENT_TYPE

#define SH_ELEMENT_TYPE   TupleHashEntryData

Definition at line 37 of file execGrouping.c.

SH_EQUAL

#define SH_EQUAL	(		tb,
			a,
			b
	)		TupleHashTableMatch(tb, a, b) == 0

Definition at line 41 of file execGrouping.c.

SH_GET_HASH

#define SH_GET_HASH	(		tb,
			a
	)		a->hash

Definition at line 44 of file execGrouping.c.

SH_HASH_KEY

#define SH_HASH_KEY	(		tb,
			key
	)		TupleHashTableHash_internal(tb, key)

Definition at line 40 of file execGrouping.c.

SH_KEY

#define SH_KEY   firstTuple

Definition at line 39 of file execGrouping.c.

SH_KEY_TYPE

#define SH_KEY_TYPE   MinimalTuple

Definition at line 38 of file execGrouping.c.

SH_PREFIX

#define SH_PREFIX   tuplehash

Definition at line 36 of file execGrouping.c.

SH_SCOPE

#define SH_SCOPE   extern

Definition at line 42 of file execGrouping.c.

SH_STORE_HASH

#define SH_STORE_HASH

Definition at line 43 of file execGrouping.c.

Function Documentation

BuildTupleHashTable()

TupleHashTable BuildTupleHashTable	(	PlanState *	parent,
		TupleDesc	inputDesc,
		int	numCols,
		AttrNumber *	keyColIdx,
		const Oid *	eqfuncoids,
		FmgrInfo *	hashfunctions,
		Oid *	collations,
		long	nbuckets,
		Size	additionalsize,
		MemoryContext	tablecxt,
		MemoryContext	tempcxt,
		bool	use_variable_hash_iv
	)

Definition at line 255 of file execGrouping.c.

{
    return BuildTupleHashTableExt(parent,
                                  inputDesc,
                                  numCols, keyColIdx,
                                  eqfuncoids,
                                  hashfunctions,
                                  collations,
                                  nbuckets, additionalsize,
                                  tablecxt,
                                  tablecxt,
                                  tempcxt,
                                  use_variable_hash_iv);
}

References BuildTupleHashTableExt().

BuildTupleHashTableExt()

TupleHashTable BuildTupleHashTableExt	(	PlanState *	parent,
		TupleDesc	inputDesc,
		int	numCols,
		AttrNumber *	keyColIdx,
		const Oid *	eqfuncoids,
		FmgrInfo *	hashfunctions,
		Oid *	collations,
		long	nbuckets,
		Size	additionalsize,
		MemoryContext	metacxt,
		MemoryContext	tablecxt,
		MemoryContext	tempcxt,
		bool	use_variable_hash_iv
	)

Definition at line 154 of file execGrouping.c.

{
    TupleHashTable hashtable;
    Size        entrysize = sizeof(TupleHashEntryData) + additionalsize;
    Size        hash_mem_limit;
    MemoryContext oldcontext;
    bool        allow_jit;
 
    Assert(nbuckets > 0);
 
    /* Limit initial table size request to not more than hash_mem */
    hash_mem_limit = get_hash_memory_limit() / entrysize;
    if (nbuckets > hash_mem_limit)
        nbuckets = hash_mem_limit;
 
    oldcontext = MemoryContextSwitchTo(metacxt);
 
    hashtable = (TupleHashTable) palloc(sizeof(TupleHashTableData));
 
    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;
 
    /*
     * If parallelism is in use, even if the leader backend is performing the
     * scan itself, we don't want to create the hashtable exactly the same way
     * in all workers. As hashtables are iterated over in keyspace-order,
     * doing so in all processes in the same way is likely to lead to
     * "unbalanced" hashtables when the table size initially is
     * underestimated.
     */
    if (use_variable_hash_iv)
        hashtable->hash_iv = murmurhash32(ParallelWorkerNumber);
    else
        hashtable->hash_iv = 0;
 
    hashtable->hashtab = tuplehash_create(metacxt, nbuckets, hashtable);
 
    /*
     * We copy the input tuple descriptor just for safety --- we assume all
     * input tuples will have equivalent descriptors.
     */
    hashtable->tableslot = MakeSingleTupleTableSlot(CreateTupleDescCopy(inputDesc),
                                                    &TTSOpsMinimalTuple);
 
    /*
     * If the old reset interface is used (i.e. BuildTupleHashTable, rather
     * than BuildTupleHashTableExt), allowing JIT would lead to the generated
     * functions to a) live longer than the query b) be re-generated each time
     * the table is being reset. Therefore prevent JIT from being used in that
     * case, by not providing a parent node (which prevents accessing the
     * JitContext in the EState).
     */
    allow_jit = metacxt != tablecxt;
 
    /* build comparator for all columns */
    /* XXX: should we support non-minimal tuples for the inputslot? */
    hashtable->tab_eq_func = ExecBuildGroupingEqual(inputDesc, inputDesc,
                                                    &TTSOpsMinimalTuple, &TTSOpsMinimalTuple,
                                                    numCols,
                                                    keyColIdx, eqfuncoids, collations,
                                                    allow_jit ? parent : NULL);
 
    /*
     * While not pretty, it's ok to not shut down this context, but instead
     * rely on the containing memory context being reset, as
     * ExecBuildGroupingEqual() only builds a very simple expression calling
     * functions (i.e. nothing that'd employ RegisterExprContextCallback()).
     */
    hashtable->exprcontext = CreateStandaloneExprContext();
 
    MemoryContextSwitchTo(oldcontext);
 
    return hashtable;
}

References Assert(), CreateStandaloneExprContext(), CreateTupleDescCopy(), TupleHashTableData::cur_eq_func, TupleHashTableData::entrysize, ExecBuildGroupingEqual(), TupleHashTableData::exprcontext, get_hash_memory_limit(), TupleHashTableData::hash_iv, TupleHashTableData::hashtab, TupleHashTableData::in_hash_funcs, TupleHashTableData::inputslot, TupleHashTableData::keyColIdx, MakeSingleTupleTableSlot(), MemoryContextSwitchTo(), murmurhash32(), TupleHashTableData::numCols, palloc(), ParallelWorkerNumber, TupleHashTableData::tab_collations, TupleHashTableData::tab_eq_func, TupleHashTableData::tab_hash_funcs, TupleHashTableData::tablecxt, TupleHashTableData::tableslot, TupleHashTableData::tempcxt, and TTSOpsMinimalTuple.

Referenced by build_hash_table(), buildSubPlanHash(), and BuildTupleHashTable().

execTuplesHashPrepare()

void execTuplesHashPrepare	(	int	numCols,
		const Oid *	eqOperators,
		Oid **	eqFuncOids,
		FmgrInfo **	hashFunctions
	)

Definition at line 96 of file execGrouping.c.

{
    int         i;
 
    *eqFuncOids = (Oid *) palloc(numCols * sizeof(Oid));
    *hashFunctions = (FmgrInfo *) palloc(numCols * sizeof(FmgrInfo));
 
    for (i = 0; i < numCols; i++)
    {
        Oid         eq_opr = eqOperators[i];
        Oid         eq_function;
        Oid         left_hash_function;
        Oid         right_hash_function;
 
        eq_function = get_opcode(eq_opr);
        if (!get_op_hash_functions(eq_opr,
                                   &left_hash_function, &right_hash_function))
            elog(ERROR, "could not find hash function for hash operator %u",
                 eq_opr);
        /* We're not supporting cross-type cases here */
        Assert(left_hash_function == right_hash_function);
        (*eqFuncOids)[i] = eq_function;
        fmgr_info(right_hash_function, &(*hashFunctions)[i]);
    }
}

References Assert(), elog(), ERROR, fmgr_info(), get_op_hash_functions(), get_opcode(), i, and palloc().

Referenced by ExecInitRecursiveUnion(), ExecInitSetOp(), and find_hash_columns().

execTuplesMatchPrepare()

ExprState* execTuplesMatchPrepare	(	TupleDesc	desc,
		int	numCols,
		const AttrNumber *	keyColIdx,
		const Oid *	eqOperators,
		const Oid *	collations,
		PlanState *	parent
	)

Definition at line 59 of file execGrouping.c.

{
    Oid        *eqFunctions = (Oid *) palloc(numCols * sizeof(Oid));
    int         i;
    ExprState  *expr;
 
    if (numCols == 0)
        return NULL;
 
    /* lookup equality functions */
    for (i = 0; i < numCols; i++)
        eqFunctions[i] = get_opcode(eqOperators[i]);
 
    /* build actual expression */
    expr = ExecBuildGroupingEqual(desc, desc, NULL, NULL,
                                  numCols, keyColIdx, eqFunctions, collations,
                                  parent);
 
    return expr;
}

References ExecBuildGroupingEqual(), get_opcode(), i, and palloc().

Referenced by build_pertrans_for_aggref(), ExecInitAgg(), ExecInitGroup(), ExecInitLimit(), ExecInitSetOp(), ExecInitUnique(), ExecInitWindowAgg(), and hypothetical_dense_rank_final().

FindTupleHashEntry()

TupleHashEntry FindTupleHashEntry	(	TupleHashTable	hashtable,
		TupleTableSlot *	slot,
		ExprState *	eqcomp,
		FmgrInfo *	hashfunctions
	)

Definition at line 393 of file execGrouping.c.

{
    TupleHashEntry entry;
    MemoryContext oldContext;
    MinimalTuple key;
 
    /* Need to run the hash functions in short-lived context */
    oldContext = MemoryContextSwitchTo(hashtable->tempcxt);
 
    /* Set up data needed by hash and match functions */
    hashtable->inputslot = slot;
    hashtable->in_hash_funcs = hashfunctions;
    hashtable->cur_eq_func = eqcomp;
 
    /* Search the hash table */
    key = NULL;                 /* flag to reference inputslot */
    entry = tuplehash_lookup(hashtable->hashtab, key);
    MemoryContextSwitchTo(oldContext);
 
    return entry;
}

References TupleHashTableData::cur_eq_func, TupleHashTableData::hashtab, TupleHashTableData::in_hash_funcs, TupleHashTableData::inputslot, sort-test::key, MemoryContextSwitchTo(), and TupleHashTableData::tempcxt.

Referenced by ExecHashSubPlan().

LookupTupleHashEntry()

TupleHashEntry LookupTupleHashEntry	(	TupleHashTable	hashtable,
		TupleTableSlot *	slot,
		bool *	isnew,
		uint32 *	hash
	)

Definition at line 306 of file execGrouping.c.

{
    TupleHashEntry entry;
    MemoryContext oldContext;
    uint32      local_hash;
 
    /* Need to run the hash functions in short-lived context */
    oldContext = MemoryContextSwitchTo(hashtable->tempcxt);
 
    /* set up data needed by hash and match functions */
    hashtable->inputslot = slot;
    hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
    hashtable->cur_eq_func = hashtable->tab_eq_func;
 
    local_hash = TupleHashTableHash_internal(hashtable->hashtab, NULL);
    entry = LookupTupleHashEntry_internal(hashtable, slot, isnew, local_hash);
 
    if (hash != NULL)
        *hash = local_hash;
 
    Assert(entry == NULL || entry->hash == local_hash);
 
    MemoryContextSwitchTo(oldContext);
 
    return entry;
}

References Assert(), TupleHashTableData::cur_eq_func, hash(), TupleHashEntryData::hash, TupleHashTableData::hashtab, TupleHashTableData::in_hash_funcs, TupleHashTableData::inputslot, LookupTupleHashEntry_internal(), MemoryContextSwitchTo(), TupleHashTableData::tab_eq_func, TupleHashTableData::tab_hash_funcs, TupleHashTableData::tempcxt, and TupleHashTableHash_internal().

Referenced by buildSubPlanHash(), ExecRecursiveUnion(), lookup_hash_entries(), and setop_fill_hash_table().

LookupTupleHashEntry_internal()

static TupleHashEntry LookupTupleHashEntry_internal ( TupleHashTable  hashtable, TupleTableSlot *  slot, bool *  isnew, uint32  hash  )

inlinestatic

Definition at line 496 of file execGrouping.c.

{
    TupleHashEntryData *entry;
    bool        found;
    MinimalTuple key;
 
    key = NULL;                 /* flag to reference inputslot */
 
    if (isnew)
    {
        entry = tuplehash_insert_hash(hashtable->hashtab, key, hash, &found);
 
        if (found)
        {
            /* found pre-existing entry */
            *isnew = false;
        }
        else
        {
            /* created new entry */
            *isnew = true;
            /* zero caller data */
            entry->additional = NULL;
            MemoryContextSwitchTo(hashtable->tablecxt);
            /* Copy the first tuple into the table context */
            entry->firstTuple = ExecCopySlotMinimalTuple(slot);
        }
    }
    else
    {
        entry = tuplehash_lookup_hash(hashtable->hashtab, key, hash);
    }
 
    return entry;
}

References TupleHashEntryData::additional, ExecCopySlotMinimalTuple(), TupleHashEntryData::firstTuple, hash(), TupleHashTableData::hashtab, sort-test::key, MemoryContextSwitchTo(), and TupleHashTableData::tablecxt.

Referenced by LookupTupleHashEntry(), and LookupTupleHashEntryHash().

LookupTupleHashEntryHash()

TupleHashEntry LookupTupleHashEntryHash	(	TupleHashTable	hashtable,
		TupleTableSlot *	slot,
		bool *	isnew,
		uint32	hash
	)

Definition at line 361 of file execGrouping.c.

{
    TupleHashEntry entry;
    MemoryContext oldContext;
 
    /* Need to run the hash functions in short-lived context */
    oldContext = MemoryContextSwitchTo(hashtable->tempcxt);
 
    /* set up data needed by hash and match functions */
    hashtable->inputslot = slot;
    hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
    hashtable->cur_eq_func = hashtable->tab_eq_func;
 
    entry = LookupTupleHashEntry_internal(hashtable, slot, isnew, hash);
    Assert(entry == NULL || entry->hash == hash);
 
    MemoryContextSwitchTo(oldContext);
 
    return entry;
}

References Assert(), TupleHashTableData::cur_eq_func, hash(), TupleHashEntryData::hash, TupleHashTableData::in_hash_funcs, TupleHashTableData::inputslot, LookupTupleHashEntry_internal(), MemoryContextSwitchTo(), TupleHashTableData::tab_eq_func, TupleHashTableData::tab_hash_funcs, and TupleHashTableData::tempcxt.

Referenced by agg_refill_hash_table().

ResetTupleHashTable()

void ResetTupleHashTable

(

TupleHashTable

hashtable

)

Definition at line 285 of file execGrouping.c.

{
    tuplehash_reset(hashtable->hashtab);
}

References TupleHashTableData::hashtab.

Referenced by agg_refill_hash_table(), build_hash_tables(), buildSubPlanHash(), ExecReScanRecursiveUnion(), and ExecReScanSetOp().

TupleHashTableHash()

uint32 TupleHashTableHash	(	TupleHashTable	hashtable,
		TupleTableSlot *	slot
	)

Definition at line 338 of file execGrouping.c.

{
    MemoryContext oldContext;
    uint32      hash;
 
    hashtable->inputslot = slot;
    hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
 
    /* Need to run the hash functions in short-lived context */
    oldContext = MemoryContextSwitchTo(hashtable->tempcxt);
 
    hash = TupleHashTableHash_internal(hashtable->hashtab, NULL);
 
    MemoryContextSwitchTo(oldContext);
 
    return hash;
}

References hash(), TupleHashTableData::hashtab, TupleHashTableData::in_hash_funcs, TupleHashTableData::inputslot, MemoryContextSwitchTo(), TupleHashTableData::tab_hash_funcs, TupleHashTableData::tempcxt, and TupleHashTableHash_internal().

TupleHashTableHash_internal()

static uint32 TupleHashTableHash_internal ( struct tuplehash_hash *  tb, const MinimalTuple  tuple  )

inlinestatic

Definition at line 426 of file execGrouping.c.

{
    TupleHashTable hashtable = (TupleHashTable) tb->private_data;
    int         numCols = hashtable->numCols;
    AttrNumber *keyColIdx = hashtable->keyColIdx;
    uint32      hashkey = hashtable->hash_iv;
    TupleTableSlot *slot;
    FmgrInfo   *hashfunctions;
    int         i;
 
    if (tuple == NULL)
    {
        /* Process the current input tuple for the table */
        slot = hashtable->inputslot;
        hashfunctions = hashtable->in_hash_funcs;
    }
    else
    {
        /*
         * Process a tuple already stored in the table.
         *
         * (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;
        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;
        }
    }
 
    /*
     * 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.
     */
    return murmurhash32(hashkey);
}

References DatumGetUInt32(), ExecStoreMinimalTuple(), FunctionCall1Coll(), TupleHashTableData::hash_iv, i, if(), TupleHashTableData::in_hash_funcs, TupleHashTableData::inputslot, TupleHashTableData::keyColIdx, murmurhash32(), TupleHashTableData::numCols, pg_rotate_left32(), slot_getattr(), TupleHashTableData::tab_collations, TupleHashTableData::tab_hash_funcs, and TupleHashTableData::tableslot.

Referenced by LookupTupleHashEntry(), and TupleHashTableHash().

TupleHashTableMatch()

static int TupleHashTableMatch ( struct tuplehash_hash *  tb, const MinimalTuple  tuple1, const MinimalTuple  tuple2  )

static

Definition at line 537 of file execGrouping.c.

{
    TupleTableSlot *slot1;
    TupleTableSlot *slot2;
    TupleHashTable hashtable = (TupleHashTable) tb->private_data;
    ExprContext *econtext = hashtable->exprcontext;
 
    /*
     * We assume that simplehash.h 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 required.
     */
    Assert(tuple1 != NULL);
    slot1 = hashtable->tableslot;
    ExecStoreMinimalTuple(tuple1, slot1, false);
    Assert(tuple2 == NULL);
    slot2 = hashtable->inputslot;
 
    /* For crosstype comparisons, the inputslot must be first */
    econtext->ecxt_innertuple = slot2;
    econtext->ecxt_outertuple = slot1;
    return !ExecQualAndReset(hashtable->cur_eq_func, econtext);
}

References Assert(), TupleHashTableData::cur_eq_func, ExecQualAndReset(), ExecStoreMinimalTuple(), TupleHashTableData::exprcontext, TupleHashTableData::inputslot, and TupleHashTableData::tableslot.