PostgreSQL Source Code  git master
execGrouping.c File Reference
#include "postgres.h"
#include "access/hash.h"
#include "access/parallel.h"
#include "executor/executor.h"
#include "miscadmin.h"
#include "utils/lsyscache.h"
#include "utils/hashutils.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(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 uint32 TupleHashTableHash (struct tuplehash_hash *tb, const MinimalTuple tuple)
 
static int TupleHashTableMatch (struct tuplehash_hash *tb, const MinimalTuple tuple1, const MinimalTuple tuple2)
 
ExprStateexecTuplesMatchPrepare (TupleDesc desc, int numCols, AttrNumber *keyColIdx, Oid *eqOperators, PlanState *parent)
 
void execTuplesHashPrepare (int numCols, Oid *eqOperators, Oid **eqFuncOids, FmgrInfo **hashFunctions)
 
TupleHashTable BuildTupleHashTable (PlanState *parent, TupleDesc inputDesc, int numCols, AttrNumber *keyColIdx, Oid *eqfuncoids, FmgrInfo *hashfunctions, long nbuckets, Size additionalsize, MemoryContext tablecxt, MemoryContext tempcxt, bool use_variable_hash_iv)
 
TupleHashEntry LookupTupleHashEntry (TupleHashTable hashtable, TupleTableSlot *slot, bool *isnew)
 
TupleHashEntry FindTupleHashEntry (TupleHashTable hashtable, TupleTableSlot *slot, ExprState *eqcomp, FmgrInfo *hashfunctions)
 

Macro Definition Documentation

◆ SH_DEFINE

#define SH_DEFINE

Definition at line 46 of file execGrouping.c.

◆ SH_ELEMENT_TYPE

#define SH_ELEMENT_TYPE   TupleHashEntryData

Definition at line 38 of file execGrouping.c.

◆ SH_EQUAL

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

Definition at line 42 of file execGrouping.c.

◆ SH_GET_HASH

#define SH_GET_HASH (   tb,
 
)    a->hash

Definition at line 45 of file execGrouping.c.

◆ SH_HASH_KEY

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

Definition at line 41 of file execGrouping.c.

◆ SH_KEY

#define SH_KEY   firstTuple

Definition at line 40 of file execGrouping.c.

◆ SH_KEY_TYPE

#define SH_KEY_TYPE   MinimalTuple

Definition at line 39 of file execGrouping.c.

◆ SH_PREFIX

#define SH_PREFIX   tuplehash

Definition at line 37 of file execGrouping.c.

◆ SH_SCOPE

#define SH_SCOPE   extern

Definition at line 43 of file execGrouping.c.

◆ SH_STORE_HASH

#define SH_STORE_HASH

Definition at line 44 of file execGrouping.c.

Function Documentation

◆ BuildTupleHashTable()

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

Definition at line 152 of file execGrouping.c.

References Assert, CreateExprContext(), CreateTupleDescCopy(), TupleHashTableData::cur_eq_func, TupleHashTableData::entrysize, ExecBuildGroupingEqual(), TupleHashTableData::exprcontext, TupleHashTableData::hash_iv, TupleHashTableData::hashtab, TupleHashTableData::in_hash_funcs, TupleHashTableData::inputslot, TupleHashTableData::keyColIdx, MakeSingleTupleTableSlot(), MemoryContextAlloc(), MemoryContextSwitchTo(), Min, murmurhash32(), TupleHashTableData::numCols, ParallelWorkerNumber, PlanState::state, TupleHashTableData::tab_eq_func, TupleHashTableData::tab_hash_funcs, TupleHashTableData::tablecxt, TupleHashTableData::tableslot, TupleHashTableData::tempcxt, and work_mem.

Referenced by build_hash_table(), and buildSubPlanHash().

160 {
161  TupleHashTable hashtable;
162  Size entrysize = sizeof(TupleHashEntryData) + additionalsize;
163  MemoryContext oldcontext;
164 
165  Assert(nbuckets > 0);
166 
167  /* Limit initial table size request to not more than work_mem */
168  nbuckets = Min(nbuckets, (long) ((work_mem * 1024L) / entrysize));
169 
170  hashtable = (TupleHashTable)
171  MemoryContextAlloc(tablecxt, sizeof(TupleHashTableData));
172 
173  hashtable->numCols = numCols;
174  hashtable->keyColIdx = keyColIdx;
175  hashtable->tab_hash_funcs = hashfunctions;
176  hashtable->tablecxt = tablecxt;
177  hashtable->tempcxt = tempcxt;
178  hashtable->entrysize = entrysize;
179  hashtable->tableslot = NULL; /* will be made on first lookup */
180  hashtable->inputslot = NULL;
181  hashtable->in_hash_funcs = NULL;
182  hashtable->cur_eq_func = NULL;
183 
184  /*
185  * If parallelism is in use, even if the master backend is performing the
186  * scan itself, we don't want to create the hashtable exactly the same way
187  * in all workers. As hashtables are iterated over in keyspace-order,
188  * doing so in all processes in the same way is likely to lead to
189  * "unbalanced" hashtables when the table size initially is
190  * underestimated.
191  */
192  if (use_variable_hash_iv)
194  else
195  hashtable->hash_iv = 0;
196 
197  hashtable->hashtab = tuplehash_create(tablecxt, nbuckets, hashtable);
198 
199  oldcontext = MemoryContextSwitchTo(hashtable->tablecxt);
200 
201  /*
202  * We copy the input tuple descriptor just for safety --- we assume all
203  * input tuples will have equivalent descriptors.
204  */
205  hashtable->tableslot = MakeSingleTupleTableSlot(CreateTupleDescCopy(inputDesc));
206 
207  /* build comparator for all columns */
208  hashtable->tab_eq_func = ExecBuildGroupingEqual(inputDesc, inputDesc,
209  numCols,
210  keyColIdx, eqfuncoids,
211  parent);
212 
213  MemoryContextSwitchTo(oldcontext);
214 
215  hashtable->exprcontext = CreateExprContext(parent->state);
216 
217  return hashtable;
218 }
ExprContext * exprcontext
Definition: execnodes.h:681
TupleDesc CreateTupleDescCopy(TupleDesc tupdesc)
Definition: tupdesc.c:112
ExprState * ExecBuildGroupingEqual(TupleDesc ldesc, TupleDesc rdesc, int numCols, AttrNumber *keyColIdx, Oid *eqfunctions, PlanState *parent)
Definition: execExpr.c:3216
TupleTableSlot * inputslot
Definition: execnodes.h:677
#define Min(x, y)
Definition: c.h:857
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
AttrNumber * keyColIdx
Definition: execnodes.h:669
ExprState * tab_eq_func
Definition: execnodes.h:671
ExprState * cur_eq_func
Definition: execnodes.h:679
EState * state
Definition: execnodes.h:914
FmgrInfo * tab_hash_funcs
Definition: execnodes.h:670
FmgrInfo * in_hash_funcs
Definition: execnodes.h:678
struct TupleHashEntryData TupleHashEntryData
MemoryContext tablecxt
Definition: execnodes.h:672
struct TupleHashTableData * TupleHashTable
Definition: execnodes.h:647
int ParallelWorkerNumber
Definition: parallel.c:103
TupleTableSlot * MakeSingleTupleTableSlot(TupleDesc tupdesc)
Definition: execTuples.c:232
int work_mem
Definition: globals.c:120
tuplehash_hash * hashtab
Definition: execnodes.h:667
#define Assert(condition)
Definition: c.h:699
TupleTableSlot * tableslot
Definition: execnodes.h:675
size_t Size
Definition: c.h:433
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:771
ExprContext * CreateExprContext(EState *estate)
Definition: execUtils.c:228
static uint32 murmurhash32(uint32 data)
Definition: hashutils.h:41
MemoryContext tempcxt
Definition: execnodes.h:673

◆ execTuplesHashPrepare()

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

Definition at line 95 of file execGrouping.c.

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

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

99 {
100  int i;
101 
102  *eqFuncOids = (Oid *) palloc(numCols * sizeof(Oid));
103  *hashFunctions = (FmgrInfo *) palloc(numCols * sizeof(FmgrInfo));
104 
105  for (i = 0; i < numCols; i++)
106  {
107  Oid eq_opr = eqOperators[i];
108  Oid eq_function;
109  Oid left_hash_function;
110  Oid right_hash_function;
111 
112  eq_function = get_opcode(eq_opr);
113  if (!get_op_hash_functions(eq_opr,
114  &left_hash_function, &right_hash_function))
115  elog(ERROR, "could not find hash function for hash operator %u",
116  eq_opr);
117  /* We're not supporting cross-type cases here */
118  Assert(left_hash_function == right_hash_function);
119  (*eqFuncOids)[i] = eq_function;
120  fmgr_info(right_hash_function, &(*hashFunctions)[i]);
121  }
122 }
Definition: fmgr.h:56
bool get_op_hash_functions(Oid opno, RegProcedure *lhs_procno, RegProcedure *rhs_procno)
Definition: lsyscache.c:507
unsigned int Oid
Definition: postgres_ext.h:31
#define ERROR
Definition: elog.h:43
void fmgr_info(Oid functionId, FmgrInfo *finfo)
Definition: fmgr.c:124
RegProcedure get_opcode(Oid opno)
Definition: lsyscache.c:1079
#define Assert(condition)
Definition: c.h:699
void * palloc(Size size)
Definition: mcxt.c:924
int i
#define elog
Definition: elog.h:219

◆ execTuplesMatchPrepare()

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

Definition at line 60 of file execGrouping.c.

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

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

65 {
66  Oid *eqFunctions = (Oid *) palloc(numCols * sizeof(Oid));
67  int i;
68  ExprState *expr;
69 
70  if (numCols == 0)
71  return NULL;
72 
73  /* lookup equality functions */
74  for (i = 0; i < numCols; i++)
75  eqFunctions[i] = get_opcode(eqOperators[i]);
76 
77  /* build actual expression */
78  expr = ExecBuildGroupingEqual(desc, desc, numCols, keyColIdx, eqFunctions,
79  parent);
80 
81  return expr;
82 }
ExprState * ExecBuildGroupingEqual(TupleDesc ldesc, TupleDesc rdesc, int numCols, AttrNumber *keyColIdx, Oid *eqfunctions, PlanState *parent)
Definition: execExpr.c:3216
unsigned int Oid
Definition: postgres_ext.h:31
RegProcedure get_opcode(Oid opno)
Definition: lsyscache.c:1079
void * palloc(Size size)
Definition: mcxt.c:924
int i

◆ FindTupleHashEntry()

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

Definition at line 291 of file execGrouping.c.

References TupleHashTableData::cur_eq_func, TupleHashTableData::hashtab, TupleHashTableData::in_hash_funcs, TupleHashTableData::inputslot, MemoryContextSwitchTo(), and TupleHashTableData::tempcxt.

Referenced by ExecHashSubPlan().

294 {
295  TupleHashEntry entry;
296  MemoryContext oldContext;
297  MinimalTuple key;
298 
299  /* Need to run the hash functions in short-lived context */
300  oldContext = MemoryContextSwitchTo(hashtable->tempcxt);
301 
302  /* Set up data needed by hash and match functions */
303  hashtable->inputslot = slot;
304  hashtable->in_hash_funcs = hashfunctions;
305  hashtable->cur_eq_func = eqcomp;
306 
307  /* Search the hash table */
308  key = NULL; /* flag to reference inputslot */
309  entry = tuplehash_lookup(hashtable->hashtab, key);
310  MemoryContextSwitchTo(oldContext);
311 
312  return entry;
313 }
TupleTableSlot * inputslot
Definition: execnodes.h:677
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
ExprState * cur_eq_func
Definition: execnodes.h:679
FmgrInfo * in_hash_funcs
Definition: execnodes.h:678
tuplehash_hash * hashtab
Definition: execnodes.h:667
MemoryContext tempcxt
Definition: execnodes.h:673

◆ LookupTupleHashEntry()

TupleHashEntry LookupTupleHashEntry ( TupleHashTable  hashtable,
TupleTableSlot slot,
bool isnew 
)

Definition at line 233 of file execGrouping.c.

References TupleHashEntryData::additional, TupleHashTableData::cur_eq_func, ExecCopySlotMinimalTuple(), TupleHashEntryData::firstTuple, TupleHashTableData::hashtab, TupleHashTableData::in_hash_funcs, TupleHashTableData::inputslot, MemoryContextSwitchTo(), TupleHashTableData::tab_eq_func, TupleHashTableData::tab_hash_funcs, TupleHashTableData::tablecxt, and TupleHashTableData::tempcxt.

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

235 {
236  TupleHashEntryData *entry;
237  MemoryContext oldContext;
238  bool found;
239  MinimalTuple key;
240 
241  /* Need to run the hash functions in short-lived context */
242  oldContext = MemoryContextSwitchTo(hashtable->tempcxt);
243 
244  /* set up data needed by hash and match functions */
245  hashtable->inputslot = slot;
246  hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
247  hashtable->cur_eq_func = hashtable->tab_eq_func;
248 
249  key = NULL; /* flag to reference inputslot */
250 
251  if (isnew)
252  {
253  entry = tuplehash_insert(hashtable->hashtab, key, &found);
254 
255  if (found)
256  {
257  /* found pre-existing entry */
258  *isnew = false;
259  }
260  else
261  {
262  /* created new entry */
263  *isnew = true;
264  /* zero caller data */
265  entry->additional = NULL;
266  MemoryContextSwitchTo(hashtable->tablecxt);
267  /* Copy the first tuple into the table context */
268  entry->firstTuple = ExecCopySlotMinimalTuple(slot);
269  }
270  }
271  else
272  {
273  entry = tuplehash_lookup(hashtable->hashtab, key);
274  }
275 
276  MemoryContextSwitchTo(oldContext);
277 
278  return entry;
279 }
TupleTableSlot * inputslot
Definition: execnodes.h:677
MinimalTuple firstTuple
Definition: execnodes.h:651
MinimalTuple ExecCopySlotMinimalTuple(TupleTableSlot *slot)
Definition: execTuples.c:613
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
ExprState * tab_eq_func
Definition: execnodes.h:671
ExprState * cur_eq_func
Definition: execnodes.h:679
FmgrInfo * tab_hash_funcs
Definition: execnodes.h:670
FmgrInfo * in_hash_funcs
Definition: execnodes.h:678
MemoryContext tablecxt
Definition: execnodes.h:672
tuplehash_hash * hashtab
Definition: execnodes.h:667
MemoryContext tempcxt
Definition: execnodes.h:673

◆ TupleHashTableHash()

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

Definition at line 329 of file execGrouping.c.

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

330 {
331  TupleHashTable hashtable = (TupleHashTable) tb->private_data;
332  int numCols = hashtable->numCols;
333  AttrNumber *keyColIdx = hashtable->keyColIdx;
334  uint32 hashkey = hashtable->hash_iv;
335  TupleTableSlot *slot;
336  FmgrInfo *hashfunctions;
337  int i;
338 
339  if (tuple == NULL)
340  {
341  /* Process the current input tuple for the table */
342  slot = hashtable->inputslot;
343  hashfunctions = hashtable->in_hash_funcs;
344  }
345  else
346  {
347  /*
348  * Process a tuple already stored in the table.
349  *
350  * (this case never actually occurs due to the way simplehash.h is
351  * used, as the hash-value is stored in the entries)
352  */
353  slot = hashtable->tableslot;
354  ExecStoreMinimalTuple(tuple, slot, false);
355  hashfunctions = hashtable->tab_hash_funcs;
356  }
357 
358  for (i = 0; i < numCols; i++)
359  {
360  AttrNumber att = keyColIdx[i];
361  Datum attr;
362  bool isNull;
363 
364  /* rotate hashkey left 1 bit at each step */
365  hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0);
366 
367  attr = slot_getattr(slot, att, &isNull);
368 
369  if (!isNull) /* treat nulls as having hash key 0 */
370  {
371  uint32 hkey;
372 
373  hkey = DatumGetUInt32(FunctionCall1(&hashfunctions[i],
374  attr));
375  hashkey ^= hkey;
376  }
377  }
378 
379  /*
380  * The way hashes are combined above, among each other and with the IV,
381  * doesn't lead to good bit perturbation. As the IV's goal is to lead to
382  * achieve that, perform a round of hashing of the combined hash -
383  * resulting in near perfect perturbation.
384  */
385  return murmurhash32(hashkey);
386 }
#define DatumGetUInt32(X)
Definition: postgres.h:471
Definition: fmgr.h:56
TupleTableSlot * ExecStoreMinimalTuple(MinimalTuple mtup, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:420
TupleTableSlot * inputslot
Definition: execnodes.h:677
AttrNumber * keyColIdx
Definition: execnodes.h:669
FmgrInfo * tab_hash_funcs
Definition: execnodes.h:670
FmgrInfo * in_hash_funcs
Definition: execnodes.h:678
struct TupleHashTableData * TupleHashTable
Definition: execnodes.h:647
unsigned int uint32
Definition: c.h:325
uintptr_t Datum
Definition: postgres.h:367
TupleTableSlot * tableslot
Definition: execnodes.h:675
int i
#define FunctionCall1(flinfo, arg1)
Definition: fmgr.h:608
Datum slot_getattr(TupleTableSlot *slot, int attnum, bool *isnull)
Definition: heaptuple.c:1518
static uint32 murmurhash32(uint32 data)
Definition: hashutils.h:41
int16 AttrNumber
Definition: attnum.h:21

◆ TupleHashTableMatch()

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

Definition at line 394 of file execGrouping.c.

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

395 {
396  TupleTableSlot *slot1;
397  TupleTableSlot *slot2;
398  TupleHashTable hashtable = (TupleHashTable) tb->private_data;
399  ExprContext *econtext = hashtable->exprcontext;
400 
401  /*
402  * We assume that simplehash.h will only ever call us with the first
403  * argument being an actual table entry, and the second argument being
404  * LookupTupleHashEntry's dummy TupleHashEntryData. The other direction
405  * could be supported too, but is not currently required.
406  */
407  Assert(tuple1 != NULL);
408  slot1 = hashtable->tableslot;
409  ExecStoreMinimalTuple(tuple1, slot1, false);
410  Assert(tuple2 == NULL);
411  slot2 = hashtable->inputslot;
412 
413  /* For crosstype comparisons, the inputslot must be first */
414  econtext->ecxt_innertuple = slot2;
415  econtext->ecxt_outertuple = slot1;
416  return !ExecQualAndReset(hashtable->cur_eq_func, econtext);
417 }
ExprContext * exprcontext
Definition: execnodes.h:681
TupleTableSlot * ExecStoreMinimalTuple(MinimalTuple mtup, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:420
TupleTableSlot * inputslot
Definition: execnodes.h:677
ExprState * cur_eq_func
Definition: execnodes.h:679
struct TupleHashTableData * TupleHashTable
Definition: execnodes.h:647
static bool ExecQualAndReset(ExprState *state, ExprContext *econtext)
Definition: executor.h:388
#define Assert(condition)
Definition: c.h:699
TupleTableSlot * tableslot
Definition: execnodes.h:675