execGrouping.c

Go to the documentation of this file.

/*-------------------------------------------------------------------------
 *
 * execGrouping.c
 *    executor utility routines for grouping, hashing, and aggregation
 *
 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *    src/backend/executor/execGrouping.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"
 
#include <math.h>
 
#include "access/htup_details.h"
#include "access/parallel.h"
#include "common/hashfn.h"
#include "executor/executor.h"
#include "miscadmin.h"
#include "utils/lsyscache.h"
 
static int  TupleHashTableMatch(struct tuplehash_hash *tb, MinimalTuple tuple1, MinimalTuple tuple2);
static inline uint32 TupleHashTableHash_internal(struct tuplehash_hash *tb,
                                                 MinimalTuple tuple);
static inline TupleHashEntry LookupTupleHashEntry_internal(TupleHashTable hashtable,
                                                           TupleTableSlot *slot,
                                                           bool *isnew, uint32 hash);
 
/*
 * Define parameters for tuple hash table code generation. The interface is
 * *also* declared in execnodes.h (to generate the types, which are externally
 * visible).
 */
#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
#include "lib/simplehash.h"
 
 
/*****************************************************************************
 *      Utility routines for grouping tuples together
 *****************************************************************************/
 
/*
 * execTuplesMatchPrepare
 *      Build expression that can be evaluated using ExecQual(), returning
 *      whether an ExprContext's inner/outer tuples are NOT DISTINCT
 */
ExprState *
execTuplesMatchPrepare(TupleDesc desc,
                       int numCols,
                       const AttrNumber *keyColIdx,
                       const Oid *eqOperators,
                       const Oid *collations,
                       PlanState *parent)
{
    Oid        *eqFunctions;
    int         i;
    ExprState  *expr;
 
    if (numCols == 0)
        return NULL;
 
    eqFunctions = (Oid *) palloc(numCols * sizeof(Oid));
 
    /* 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;
}
 
/*
 * execTuplesHashPrepare
 *      Look up the equality and hashing functions needed for a TupleHashTable.
 *
 * This is similar to execTuplesMatchPrepare, but we also need to find the
 * hash functions associated with the equality operators.  *eqFunctions and
 * *hashFunctions receive the palloc'd result arrays.
 *
 * Note: we expect that the given operators are not cross-type comparisons.
 */
void
execTuplesHashPrepare(int numCols,
                      const Oid *eqOperators,
                      Oid **eqFuncOids,
                      FmgrInfo **hashFunctions)
{
    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]);
    }
}
 
 
/*****************************************************************************
 *      Utility routines for all-in-memory hash tables
 *
 * These routines build hash tables for grouping tuples together (eg, for
 * hash aggregation).  There is one entry for each not-distinct set of tuples
 * presented.
 *****************************************************************************/
 
/*
 * Construct an empty TupleHashTable
 *
 *  parent: PlanState node that will own this hash table
 *  inputDesc: tuple descriptor for input tuples
 *  inputOps: slot ops for input tuples, or NULL if unknown or not fixed
 *  numCols: number of columns to be compared (length of next 4 arrays)
 *  keyColIdx: indexes of tuple columns to compare
 *  eqfuncoids: OIDs of equality comparison functions to use
 *  hashfunctions: FmgrInfos of datatype-specific hashing functions to use
 *  collations: collations to use in comparisons
 *  nelements: initial estimate of hashtable size
 *  additionalsize: size of data that may be stored along with the hash entry
 *  metacxt: memory context for long-lived data and the simplehash table
 *  tuplescxt: memory context in which to store the hashed tuples themselves
 *  tempcxt: short-lived context for evaluation hash and comparison functions
 *  use_variable_hash_iv: if true, adjust hash IV per-parallel-worker
 *
 * The hashfunctions array may be made with execTuplesHashPrepare().  Note they
 * are not cross-type functions, but expect to see the table datatype(s)
 * on both sides.
 *
 * Note that the keyColIdx, hashfunctions, and collations arrays must be
 * allocated in storage that will live as long as the hashtable does.
 *
 * The metacxt and tuplescxt are separate because it's usually desirable for
 * tuplescxt to be a BumpContext to avoid memory wastage, while metacxt must
 * support pfree in case the simplehash table needs to be enlarged.  (We could
 * simplify the API of TupleHashTables by managing the tuplescxt internally.
 * But that would be disadvantageous to nodeAgg.c and nodeSubplan.c, which use
 * a single tuplescxt for multiple TupleHashTables that are reset together.)
 *
 * LookupTupleHashEntry, FindTupleHashEntry, and related functions may leak
 * memory in the tempcxt.  It is caller's responsibility to reset that context
 * reasonably often, typically once per tuple.  (We do it that way, rather
 * than managing an extra context within the hashtable, because in many cases
 * the caller can specify a tempcxt that it needs to reset per-tuple anyway.)
 *
 * We don't currently provide DestroyTupleHashTable functionality; the hash
 * table will be cleaned up at destruction of the metacxt.  (Some callers
 * bother to delete the tuplescxt explicitly, though it'd be sufficient to
 * ensure it's a child of the metacxt.)  There's not much point in working
 * harder than this so long as the expression-evaluation infrastructure
 * behaves similarly.
 */
TupleHashTable
BuildTupleHashTable(PlanState *parent,
                    TupleDesc inputDesc,
                    const TupleTableSlotOps *inputOps,
                    int numCols,
                    AttrNumber *keyColIdx,
                    const Oid *eqfuncoids,
                    FmgrInfo *hashfunctions,
                    Oid *collations,
                    double nelements,
                    Size additionalsize,
                    MemoryContext metacxt,
                    MemoryContext tuplescxt,
                    MemoryContext tempcxt,
                    bool use_variable_hash_iv)
{
    TupleHashTable hashtable;
    uint32      nbuckets;
    MemoryContext oldcontext;
    uint32      hash_iv = 0;
 
    /*
     * tuplehash_create requires a uint32 element count, so we had better
     * clamp the given nelements to fit in that.  As long as we have to do
     * that, we might as well protect against completely insane input like
     * zero or NaN.  But it is not our job here to enforce issues like staying
     * within hash_mem: the caller should have done that, and we don't have
     * enough info to second-guess.
     */
    if (isnan(nelements) || nelements <= 0)
        nbuckets = 1;
    else if (nelements >= PG_UINT32_MAX)
        nbuckets = PG_UINT32_MAX;
    else
        nbuckets = (uint32) nelements;
 
    /* tuplescxt must be separate, else ResetTupleHashTable breaks things */
    Assert(metacxt != tuplescxt);
 
    /* ensure additionalsize is maxalign'ed */
    additionalsize = MAXALIGN(additionalsize);
 
    oldcontext = MemoryContextSwitchTo(metacxt);
 
    hashtable = (TupleHashTable) palloc(sizeof(TupleHashTableData));
 
    hashtable->numCols = numCols;
    hashtable->keyColIdx = keyColIdx;
    hashtable->tab_collations = collations;
    hashtable->tuplescxt = tuplescxt;
    hashtable->tempcxt = tempcxt;
    hashtable->additionalsize = additionalsize;
    hashtable->tableslot = NULL;    /* will be made on first lookup */
    hashtable->inputslot = NULL;
    hashtable->in_hash_expr = 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)
        hash_iv = murmurhash32(ParallelWorkerNumber);
 
    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);
 
    /* build hash ExprState for all columns */
    hashtable->tab_hash_expr = ExecBuildHash32FromAttrs(inputDesc,
                                                        inputOps,
                                                        hashfunctions,
                                                        collations,
                                                        numCols,
                                                        keyColIdx,
                                                        parent,
                                                        hash_iv);
 
    /* build comparator for all columns */
    hashtable->tab_eq_func = ExecBuildGroupingEqual(inputDesc, inputDesc,
                                                    inputOps,
                                                    &TTSOpsMinimalTuple,
                                                    numCols,
                                                    keyColIdx, eqfuncoids, collations,
                                                    parent);
 
    /*
     * 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;
}
 
/*
 * Reset contents of the hashtable to be empty, preserving all the non-content
 * state.
 *
 * Note: in usages where several TupleHashTables share a tuplescxt, all must
 * be reset together, as the first one's reset call will destroy all their
 * data.  The additional reset calls for the rest will redundantly reset the
 * tuplescxt.  But because of mcxt.c's isReset flag, that's cheap enough that
 * we need not avoid it.
 */
void
ResetTupleHashTable(TupleHashTable hashtable)
{
    tuplehash_reset(hashtable->hashtab);
    MemoryContextReset(hashtable->tuplescxt);
}
 
/*
 * Estimate the amount of space needed for a TupleHashTable with nentries
 * entries, if the tuples have average data width tupleWidth and the caller
 * requires additionalsize extra space per entry.
 *
 * Return SIZE_MAX if it'd overflow size_t.
 *
 * nentries is "double" because this is meant for use by the planner,
 * which typically works with double rowcount estimates.  So we'd need to
 * clamp to integer somewhere and that might as well be here.  We do expect
 * the value not to be NaN or negative, else the result will be garbage.
 */
Size
EstimateTupleHashTableSpace(double nentries,
                            Size tupleWidth,
                            Size additionalsize)
{
    Size        sh_space;
    double      tuples_space;
 
    /* First estimate the space needed for the simplehash table */
    sh_space = tuplehash_estimate_space(nentries);
 
    /* Give up if that's already too big */
    if (sh_space >= SIZE_MAX)
        return sh_space;
 
    /*
     * Compute space needed for hashed tuples with additional data.  nentries
     * must be somewhat sane, so it should be safe to compute this product.
     *
     * We assume that the hashed tuples will be kept in a BumpContext so that
     * there is not additional per-tuple overhead.
     *
     * (Note that this is only accurate if MEMORY_CONTEXT_CHECKING is off,
     * else bump.c will add a MemoryChunk header to each tuple.  However, it
     * seems undesirable for debug builds to make different planning choices
     * than production builds, so we assume the production behavior always.)
     */
    tuples_space = nentries * (MAXALIGN(SizeofMinimalTupleHeader) +
                               MAXALIGN(tupleWidth) +
                               MAXALIGN(additionalsize));
 
    /*
     * Check for size_t overflow.  This coding is trickier than it may appear,
     * because on 64-bit machines SIZE_MAX cannot be represented exactly as a
     * double.  We must cast it explicitly to suppress compiler warnings about
     * an inexact conversion, and we must trust that any double value that
     * compares strictly less than "(double) SIZE_MAX" will cast to a
     * representable size_t value.
     */
    if (sh_space + tuples_space >= (double) SIZE_MAX)
        return SIZE_MAX;
 
    /* We don't bother estimating size of the miscellaneous overhead data */
    return (Size) (sh_space + tuples_space);
}
 
/*
 * Find or create a hashtable entry for the tuple group containing the
 * given tuple.  The tuple must be the same type as the hashtable entries.
 *
 * If isnew is NULL, we do not create new entries; we return NULL if no
 * match is found.
 *
 * If hash is not NULL, we set it to the calculated hash value. This allows
 * callers access to the hash value even if no entry is returned.
 *
 * If isnew isn't NULL, then a new entry is created if no existing entry
 * matches.  On return, *isnew is true if the entry is newly created,
 * false if it existed already.  The additional data in the new entry has
 * been zeroed.
 */
TupleHashEntry
LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
                     bool *isnew, uint32 *hash)
{
    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_expr = hashtable->tab_hash_expr;
    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;
}
 
/*
 * Compute the hash value for a tuple
 */
uint32
TupleHashTableHash(TupleHashTable hashtable, TupleTableSlot *slot)
{
    MemoryContext oldContext;
    uint32      hash;
 
    hashtable->inputslot = slot;
    hashtable->in_hash_expr = hashtable->tab_hash_expr;
 
    /* Need to run the hash functions in short-lived context */
    oldContext = MemoryContextSwitchTo(hashtable->tempcxt);
 
    hash = TupleHashTableHash_internal(hashtable->hashtab, NULL);
 
    MemoryContextSwitchTo(oldContext);
 
    return hash;
}
 
/*
 * A variant of LookupTupleHashEntry for callers that have already computed
 * the hash value.
 */
TupleHashEntry
LookupTupleHashEntryHash(TupleHashTable hashtable, TupleTableSlot *slot,
                         bool *isnew, uint32 hash)
{
    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_expr = hashtable->tab_hash_expr;
    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;
}
 
/*
 * Search for a hashtable entry matching the given tuple.  No entry is
 * 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 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,
                   ExprState *hashexpr)
{
    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_expr = hashexpr;
    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;
}
 
/*
 * If tuple is NULL, use the input slot instead. This convention avoids the
 * need to materialize virtual input tuples unless they actually need to get
 * copied into the table.
 *
 * Also, the caller must select an appropriate memory context for running
 * the hash functions.
 */
static uint32
TupleHashTableHash_internal(struct tuplehash_hash *tb,
                            MinimalTuple tuple)
{
    TupleHashTable hashtable = (TupleHashTable) tb->private_data;
    uint32      hashkey;
    TupleTableSlot *slot;
    bool        isnull;
 
    if (tuple == NULL)
    {
        /* Process the current input tuple for the table */
        hashtable->exprcontext->ecxt_innertuple = hashtable->inputslot;
        hashkey = DatumGetUInt32(ExecEvalExpr(hashtable->in_hash_expr,
                                              hashtable->exprcontext,
                                              &isnull));
    }
    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->exprcontext->ecxt_innertuple = hashtable->tableslot;
        ExecStoreMinimalTuple(tuple, slot, false);
        hashkey = 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);
}
 
/*
 * Does the work of LookupTupleHashEntry and LookupTupleHashEntryHash. Useful
 * so that we can avoid switching the memory context multiple times for
 * LookupTupleHashEntry.
 *
 * NB: This function may or may not change the memory context. Caller is
 * expected to change it back.
 */
static inline TupleHashEntry
LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *slot,
                              bool *isnew, uint32 hash)
{
    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;
 
            MemoryContextSwitchTo(hashtable->tuplescxt);
 
            /*
             * Copy the first tuple into the tuples 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,
                                                              hashtable->additionalsize);
        }
    }
    else
    {
        entry = tuplehash_lookup_hash(hashtable->hashtab, key, hash);
    }
 
    return entry;
}
 
/*
 * See whether two tuples (presumably of the same hash value) match
 */
static int
TupleHashTableMatch(struct tuplehash_hash *tb, MinimalTuple tuple1, MinimalTuple tuple2)
{
    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);
}