PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
execGrouping.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * execGrouping.c
4  * executor utility routines for grouping, hashing, and aggregation
5  *
6  * Note: we currently assume that equality and hashing functions are not
7  * collation-sensitive, so the code in this file has no support for passing
8  * collation settings through from callers. That may have to change someday.
9  *
10  * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
11  * Portions Copyright (c) 1994, Regents of the University of California
12  *
13  *
14  * IDENTIFICATION
15  * src/backend/executor/execGrouping.c
16  *
17  *-------------------------------------------------------------------------
18  */
19 #include "postgres.h"
20 
21 #include "access/hash.h"
22 #include "access/parallel.h"
23 #include "executor/executor.h"
24 #include "miscadmin.h"
25 #include "utils/lsyscache.h"
26 #include "utils/memutils.h"
27 
28 static uint32 TupleHashTableHash(struct tuplehash_hash *tb, const MinimalTuple tuple);
29 static int TupleHashTableMatch(struct tuplehash_hash *tb, const MinimalTuple tuple1, const MinimalTuple tuple2);
30 
31 /*
32  * Define parameters for tuple hash table code generation. The interface is
33  * *also* declared in execnodes.h (to generate the types, which are externally
34  * visible).
35  */
36 #define SH_PREFIX tuplehash
37 #define SH_ELEMENT_TYPE TupleHashEntryData
38 #define SH_KEY_TYPE MinimalTuple
39 #define SH_KEY firstTuple
40 #define SH_HASH_KEY(tb, key) TupleHashTableHash(tb, key)
41 #define SH_EQUAL(tb, a, b) TupleHashTableMatch(tb, a, b) == 0
42 #define SH_SCOPE extern
43 #define SH_STORE_HASH
44 #define SH_GET_HASH(tb, a) a->hash
45 #define SH_DEFINE
46 #include "lib/simplehash.h"
47 
48 
49 /*****************************************************************************
50  * Utility routines for grouping tuples together
51  *****************************************************************************/
52 
53 /*
54  * execTuplesMatch
55  * Return true if two tuples match in all the indicated fields.
56  *
57  * This actually implements SQL's notion of "not distinct". Two nulls
58  * match, a null and a not-null don't match.
59  *
60  * slot1, slot2: the tuples to compare (must have same columns!)
61  * numCols: the number of attributes to be examined
62  * matchColIdx: array of attribute column numbers
63  * eqFunctions: array of fmgr lookup info for the equality functions to use
64  * evalContext: short-term memory context for executing the functions
65  *
66  * NB: evalContext is reset each time!
67  */
68 bool
70  TupleTableSlot *slot2,
71  int numCols,
72  AttrNumber *matchColIdx,
73  FmgrInfo *eqfunctions,
74  MemoryContext evalContext)
75 {
76  MemoryContext oldContext;
77  bool result;
78  int i;
79 
80  /* Reset and switch into the temp context. */
81  MemoryContextReset(evalContext);
82  oldContext = MemoryContextSwitchTo(evalContext);
83 
84  /*
85  * We cannot report a match without checking all the fields, but we can
86  * report a non-match as soon as we find unequal fields. So, start
87  * comparing at the last field (least significant sort key). That's the
88  * most likely to be different if we are dealing with sorted input.
89  */
90  result = true;
91 
92  for (i = numCols; --i >= 0;)
93  {
94  AttrNumber att = matchColIdx[i];
95  Datum attr1,
96  attr2;
97  bool isNull1,
98  isNull2;
99 
100  attr1 = slot_getattr(slot1, att, &isNull1);
101 
102  attr2 = slot_getattr(slot2, att, &isNull2);
103 
104  if (isNull1 != isNull2)
105  {
106  result = false; /* one null and one not; they aren't equal */
107  break;
108  }
109 
110  if (isNull1)
111  continue; /* both are null, treat as equal */
112 
113  /* Apply the type-specific equality function */
114 
115  if (!DatumGetBool(FunctionCall2(&eqfunctions[i],
116  attr1, attr2)))
117  {
118  result = false; /* they aren't equal */
119  break;
120  }
121  }
122 
123  MemoryContextSwitchTo(oldContext);
124 
125  return result;
126 }
127 
128 /*
129  * execTuplesUnequal
130  * Return true if two tuples are definitely unequal in the indicated
131  * fields.
132  *
133  * Nulls are neither equal nor unequal to anything else. A true result
134  * is obtained only if there are non-null fields that compare not-equal.
135  *
136  * Parameters are identical to execTuplesMatch.
137  */
138 bool
140  TupleTableSlot *slot2,
141  int numCols,
142  AttrNumber *matchColIdx,
143  FmgrInfo *eqfunctions,
144  MemoryContext evalContext)
145 {
146  MemoryContext oldContext;
147  bool result;
148  int i;
149 
150  /* Reset and switch into the temp context. */
151  MemoryContextReset(evalContext);
152  oldContext = MemoryContextSwitchTo(evalContext);
153 
154  /*
155  * We cannot report a match without checking all the fields, but we can
156  * report a non-match as soon as we find unequal fields. So, start
157  * comparing at the last field (least significant sort key). That's the
158  * most likely to be different if we are dealing with sorted input.
159  */
160  result = false;
161 
162  for (i = numCols; --i >= 0;)
163  {
164  AttrNumber att = matchColIdx[i];
165  Datum attr1,
166  attr2;
167  bool isNull1,
168  isNull2;
169 
170  attr1 = slot_getattr(slot1, att, &isNull1);
171 
172  if (isNull1)
173  continue; /* can't prove anything here */
174 
175  attr2 = slot_getattr(slot2, att, &isNull2);
176 
177  if (isNull2)
178  continue; /* can't prove anything here */
179 
180  /* Apply the type-specific equality function */
181 
182  if (!DatumGetBool(FunctionCall2(&eqfunctions[i],
183  attr1, attr2)))
184  {
185  result = true; /* they are unequal */
186  break;
187  }
188  }
189 
190  MemoryContextSwitchTo(oldContext);
191 
192  return result;
193 }
194 
195 
196 /*
197  * execTuplesMatchPrepare
198  * Look up the equality functions needed for execTuplesMatch or
199  * execTuplesUnequal, given an array of equality operator OIDs.
200  *
201  * The result is a palloc'd array.
202  */
203 FmgrInfo *
205  Oid *eqOperators)
206 {
207  FmgrInfo *eqFunctions = (FmgrInfo *) palloc(numCols * sizeof(FmgrInfo));
208  int i;
209 
210  for (i = 0; i < numCols; i++)
211  {
212  Oid eq_opr = eqOperators[i];
213  Oid eq_function;
214 
215  eq_function = get_opcode(eq_opr);
216  fmgr_info(eq_function, &eqFunctions[i]);
217  }
218 
219  return eqFunctions;
220 }
221 
222 /*
223  * execTuplesHashPrepare
224  * Look up the equality and hashing functions needed for a TupleHashTable.
225  *
226  * This is similar to execTuplesMatchPrepare, but we also need to find the
227  * hash functions associated with the equality operators. *eqFunctions and
228  * *hashFunctions receive the palloc'd result arrays.
229  *
230  * Note: we expect that the given operators are not cross-type comparisons.
231  */
232 void
234  Oid *eqOperators,
235  FmgrInfo **eqFunctions,
236  FmgrInfo **hashFunctions)
237 {
238  int i;
239 
240  *eqFunctions = (FmgrInfo *) palloc(numCols * sizeof(FmgrInfo));
241  *hashFunctions = (FmgrInfo *) palloc(numCols * sizeof(FmgrInfo));
242 
243  for (i = 0; i < numCols; i++)
244  {
245  Oid eq_opr = eqOperators[i];
246  Oid eq_function;
247  Oid left_hash_function;
248  Oid right_hash_function;
249 
250  eq_function = get_opcode(eq_opr);
251  if (!get_op_hash_functions(eq_opr,
252  &left_hash_function, &right_hash_function))
253  elog(ERROR, "could not find hash function for hash operator %u",
254  eq_opr);
255  /* We're not supporting cross-type cases here */
256  Assert(left_hash_function == right_hash_function);
257  fmgr_info(eq_function, &(*eqFunctions)[i]);
258  fmgr_info(right_hash_function, &(*hashFunctions)[i]);
259  }
260 }
261 
262 
263 /*****************************************************************************
264  * Utility routines for all-in-memory hash tables
265  *
266  * These routines build hash tables for grouping tuples together (eg, for
267  * hash aggregation). There is one entry for each not-distinct set of tuples
268  * presented.
269  *****************************************************************************/
270 
271 /*
272  * Construct an empty TupleHashTable
273  *
274  * numCols, keyColIdx: identify the tuple fields to use as lookup key
275  * eqfunctions: equality comparison functions to use
276  * hashfunctions: datatype-specific hashing functions to use
277  * nbuckets: initial estimate of hashtable size
278  * additionalsize: size of data stored in ->additional
279  * tablecxt: memory context in which to store table and table entries
280  * tempcxt: short-lived context for evaluation hash and comparison functions
281  *
282  * The function arrays may be made with execTuplesHashPrepare(). Note they
283  * are not cross-type functions, but expect to see the table datatype(s)
284  * on both sides.
285  *
286  * Note that keyColIdx, eqfunctions, and hashfunctions must be allocated in
287  * storage that will live as long as the hashtable does.
288  */
290 BuildTupleHashTable(int numCols, AttrNumber *keyColIdx,
291  FmgrInfo *eqfunctions,
292  FmgrInfo *hashfunctions,
293  long nbuckets, Size additionalsize,
294  MemoryContext tablecxt, MemoryContext tempcxt,
295  bool use_variable_hash_iv)
296 {
297  TupleHashTable hashtable;
298  Size entrysize = sizeof(TupleHashEntryData) + additionalsize;
299 
300  Assert(nbuckets > 0);
301 
302  /* Limit initial table size request to not more than work_mem */
303  nbuckets = Min(nbuckets, (long) ((work_mem * 1024L) / entrysize));
304 
305  hashtable = (TupleHashTable)
306  MemoryContextAlloc(tablecxt, sizeof(TupleHashTableData));
307 
308  hashtable->numCols = numCols;
309  hashtable->keyColIdx = keyColIdx;
310  hashtable->tab_hash_funcs = hashfunctions;
311  hashtable->tab_eq_funcs = eqfunctions;
312  hashtable->tablecxt = tablecxt;
313  hashtable->tempcxt = tempcxt;
314  hashtable->entrysize = entrysize;
315  hashtable->tableslot = NULL; /* will be made on first lookup */
316  hashtable->inputslot = NULL;
317  hashtable->in_hash_funcs = NULL;
318  hashtable->cur_eq_funcs = NULL;
319 
320  /*
321  * If parallelism is in use, even if the master backend is performing the
322  * scan itself, we don't want to create the hashtable exactly the same way
323  * in all workers. As hashtables are iterated over in keyspace-order,
324  * doing so in all processes in the same way is likely to lead to
325  * "unbalanced" hashtables when the table size initially is
326  * underestimated.
327  */
328  if (use_variable_hash_iv)
330  else
331  hashtable->hash_iv = 0;
332 
333  hashtable->hashtab = tuplehash_create(tablecxt, nbuckets, hashtable);
334 
335  return hashtable;
336 }
337 
338 /*
339  * Find or create a hashtable entry for the tuple group containing the
340  * given tuple. The tuple must be the same type as the hashtable entries.
341  *
342  * If isnew is NULL, we do not create new entries; we return NULL if no
343  * match is found.
344  *
345  * If isnew isn't NULL, then a new entry is created if no existing entry
346  * matches. On return, *isnew is true if the entry is newly created,
347  * false if it existed already. ->additional_data in the new entry has
348  * been zeroed.
349  */
352  bool *isnew)
353 {
354  TupleHashEntryData *entry;
355  MemoryContext oldContext;
356  bool found;
357  MinimalTuple key;
358 
359  /* If first time through, clone the input slot to make table slot */
360  if (hashtable->tableslot == NULL)
361  {
362  TupleDesc tupdesc;
363 
364  oldContext = MemoryContextSwitchTo(hashtable->tablecxt);
365 
366  /*
367  * We copy the input tuple descriptor just for safety --- we assume
368  * all input tuples will have equivalent descriptors.
369  */
370  tupdesc = CreateTupleDescCopy(slot->tts_tupleDescriptor);
371  hashtable->tableslot = MakeSingleTupleTableSlot(tupdesc);
372  MemoryContextSwitchTo(oldContext);
373  }
374 
375  /* Need to run the hash functions in short-lived context */
376  oldContext = MemoryContextSwitchTo(hashtable->tempcxt);
377 
378  /* set up data needed by hash and match functions */
379  hashtable->inputslot = slot;
380  hashtable->in_hash_funcs = hashtable->tab_hash_funcs;
381  hashtable->cur_eq_funcs = hashtable->tab_eq_funcs;
382 
383  key = NULL; /* flag to reference inputslot */
384 
385  if (isnew)
386  {
387  entry = tuplehash_insert(hashtable->hashtab, key, &found);
388 
389  if (found)
390  {
391  /* found pre-existing entry */
392  *isnew = false;
393  }
394  else
395  {
396  /* created new entry */
397  *isnew = true;
398  /* zero caller data */
399  entry->additional = NULL;
400  MemoryContextSwitchTo(hashtable->tablecxt);
401  /* Copy the first tuple into the table context */
402  entry->firstTuple = ExecCopySlotMinimalTuple(slot);
403  }
404  }
405  else
406  {
407  entry = tuplehash_lookup(hashtable->hashtab, key);
408  }
409 
410  MemoryContextSwitchTo(oldContext);
411 
412  return entry;
413 }
414 
415 /*
416  * Search for a hashtable entry matching the given tuple. No entry is
417  * created if there's not a match. This is similar to the non-creating
418  * case of LookupTupleHashEntry, except that it supports cross-type
419  * comparisons, in which the given tuple is not of the same type as the
420  * table entries. The caller must provide the hash functions to use for
421  * the input tuple, as well as the equality functions, since these may be
422  * different from the table's internal functions.
423  */
426  FmgrInfo *eqfunctions,
427  FmgrInfo *hashfunctions)
428 {
429  TupleHashEntry entry;
430  MemoryContext oldContext;
431  MinimalTuple key;
432 
433  /* Need to run the hash functions in short-lived context */
434  oldContext = MemoryContextSwitchTo(hashtable->tempcxt);
435 
436  /* Set up data needed by hash and match functions */
437  hashtable->inputslot = slot;
438  hashtable->in_hash_funcs = hashfunctions;
439  hashtable->cur_eq_funcs = eqfunctions;
440 
441  /* Search the hash table */
442  key = NULL; /* flag to reference inputslot */
443  entry = tuplehash_lookup(hashtable->hashtab, key);
444  MemoryContextSwitchTo(oldContext);
445 
446  return entry;
447 }
448 
449 /*
450  * Compute the hash value for a tuple
451  *
452  * The passed-in key is a pointer to TupleHashEntryData. In an actual hash
453  * table entry, the firstTuple field points to a tuple (in MinimalTuple
454  * format). LookupTupleHashEntry sets up a dummy TupleHashEntryData with a
455  * NULL firstTuple field --- that cues us to look at the inputslot instead.
456  * This convention avoids the need to materialize virtual input tuples unless
457  * they actually need to get copied into the table.
458  *
459  * Also, the caller must select an appropriate memory context for running
460  * the hash functions. (dynahash.c doesn't change CurrentMemoryContext.)
461  */
462 static uint32
463 TupleHashTableHash(struct tuplehash_hash *tb, const MinimalTuple tuple)
464 {
465  TupleHashTable hashtable = (TupleHashTable) tb->private_data;
466  int numCols = hashtable->numCols;
467  AttrNumber *keyColIdx = hashtable->keyColIdx;
468  uint32 hashkey = hashtable->hash_iv;
469  TupleTableSlot *slot;
470  FmgrInfo *hashfunctions;
471  int i;
472 
473  if (tuple == NULL)
474  {
475  /* Process the current input tuple for the table */
476  slot = hashtable->inputslot;
477  hashfunctions = hashtable->in_hash_funcs;
478  }
479  else
480  {
481  /*
482  * Process a tuple already stored in the table.
483  *
484  * (this case never actually occurs due to the way simplehash.h is
485  * used, as the hash-value is stored in the entries)
486  */
487  slot = hashtable->tableslot;
488  ExecStoreMinimalTuple(tuple, slot, false);
489  hashfunctions = hashtable->tab_hash_funcs;
490  }
491 
492  for (i = 0; i < numCols; i++)
493  {
494  AttrNumber att = keyColIdx[i];
495  Datum attr;
496  bool isNull;
497 
498  /* rotate hashkey left 1 bit at each step */
499  hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0);
500 
501  attr = slot_getattr(slot, att, &isNull);
502 
503  if (!isNull) /* treat nulls as having hash key 0 */
504  {
505  uint32 hkey;
506 
507  hkey = DatumGetUInt32(FunctionCall1(&hashfunctions[i],
508  attr));
509  hashkey ^= hkey;
510  }
511  }
512 
513  return hashkey;
514 }
515 
516 /*
517  * See whether two tuples (presumably of the same hash value) match
518  *
519  * As above, the passed pointers are pointers to TupleHashEntryData.
520  *
521  * Also, the caller must select an appropriate memory context for running
522  * the compare functions. (dynahash.c doesn't change CurrentMemoryContext.)
523  */
524 static int
525 TupleHashTableMatch(struct tuplehash_hash *tb, const MinimalTuple tuple1, const MinimalTuple tuple2)
526 {
527  TupleTableSlot *slot1;
528  TupleTableSlot *slot2;
529  TupleHashTable hashtable = (TupleHashTable) tb->private_data;
530 
531  /*
532  * We assume that simplehash.h will only ever call us with the first
533  * argument being an actual table entry, and the second argument being
534  * LookupTupleHashEntry's dummy TupleHashEntryData. The other direction
535  * could be supported too, but is not currently required.
536  */
537  Assert(tuple1 != NULL);
538  slot1 = hashtable->tableslot;
539  ExecStoreMinimalTuple(tuple1, slot1, false);
540  Assert(tuple2 == NULL);
541  slot2 = hashtable->inputslot;
542 
543  /* For crosstype comparisons, the inputslot must be first */
544  if (execTuplesMatch(slot2,
545  slot1,
546  hashtable->numCols,
547  hashtable->keyColIdx,
548  hashtable->cur_eq_funcs,
549  hashtable->tempcxt))
550  return 0;
551  else
552  return 1;
553 }
#define DatumGetUInt32(X)
Definition: postgres.h:492
Definition: fmgr.h:56
TupleDesc CreateTupleDescCopy(TupleDesc tupdesc)
Definition: tupdesc.c:141
bool get_op_hash_functions(Oid opno, RegProcedure *lhs_procno, RegProcedure *rhs_procno)
Definition: lsyscache.c:507
TupleTableSlot * ExecStoreMinimalTuple(MinimalTuple mtup, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:384
TupleTableSlot * inputslot
Definition: execnodes.h:582
MinimalTuple firstTuple
Definition: execnodes.h:556
#define Min(x, y)
Definition: c.h:806
MinimalTuple ExecCopySlotMinimalTuple(TupleTableSlot *slot)
Definition: execTuples.c:577
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
AttrNumber * keyColIdx
Definition: execnodes.h:574
#define FunctionCall2(flinfo, arg1, arg2)
Definition: fmgr.h:604
bool execTuplesMatch(TupleTableSlot *slot1, TupleTableSlot *slot2, int numCols, AttrNumber *matchColIdx, FmgrInfo *eqfunctions, MemoryContext evalContext)
Definition: execGrouping.c:69
return result
Definition: formatting.c:1618
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:135
unsigned int Oid
Definition: postgres_ext.h:31
void execTuplesHashPrepare(int numCols, Oid *eqOperators, FmgrInfo **eqFunctions, FmgrInfo **hashFunctions)
Definition: execGrouping.c:233
FmgrInfo * tab_hash_funcs
Definition: execnodes.h:575
static int TupleHashTableMatch(struct tuplehash_hash *tb, const MinimalTuple tuple1, const MinimalTuple tuple2)
Definition: execGrouping.c:525
FmgrInfo * in_hash_funcs
Definition: execnodes.h:583
#define ERROR
Definition: elog.h:43
void fmgr_info(Oid functionId, FmgrInfo *finfo)
Definition: fmgr.c:127
struct TupleHashEntryData TupleHashEntryData
MemoryContext tablecxt
Definition: execnodes.h:577
struct TupleHashTableData * TupleHashTable
Definition: execnodes.h:552
#define DatumGetBool(X)
Definition: postgres.h:399
int ParallelWorkerNumber
Definition: parallel.c:94
bool execTuplesUnequal(TupleTableSlot *slot1, TupleTableSlot *slot2, int numCols, AttrNumber *matchColIdx, FmgrInfo *eqfunctions, MemoryContext evalContext)
Definition: execGrouping.c:139
unsigned int uint32
Definition: c.h:268
TupleHashEntry LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot, bool *isnew)
Definition: execGrouping.c:351
TupleTableSlot * MakeSingleTupleTableSlot(TupleDesc tupdesc)
Definition: execTuples.c:199
TupleDesc tts_tupleDescriptor
Definition: tuptable.h:121
Datum hash_uint32(uint32 k)
Definition: hashfunc.c:512
uintptr_t Datum
Definition: postgres.h:372
int work_mem
Definition: globals.c:112
RegProcedure get_opcode(Oid opno)
Definition: lsyscache.c:1094
tuplehash_hash * hashtab
Definition: execnodes.h:572
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
TupleTableSlot * tableslot
Definition: execnodes.h:580
size_t Size
Definition: c.h:356
TupleHashTable BuildTupleHashTable(int numCols, AttrNumber *keyColIdx, FmgrInfo *eqfunctions, FmgrInfo *hashfunctions, long nbuckets, Size additionalsize, MemoryContext tablecxt, MemoryContext tempcxt, bool use_variable_hash_iv)
Definition: execGrouping.c:290
static uint32 TupleHashTableHash(struct tuplehash_hash *tb, const MinimalTuple tuple)
Definition: execGrouping.c:463
void * palloc(Size size)
Definition: mcxt.c:849
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:707
int i
#define FunctionCall1(flinfo, arg1)
Definition: fmgr.h:602
Datum slot_getattr(TupleTableSlot *slot, int attnum, bool *isnull)
Definition: heaptuple.c:1143
FmgrInfo * cur_eq_funcs
Definition: execnodes.h:584
MemoryContext tempcxt
Definition: execnodes.h:578
#define elog
Definition: elog.h:219
FmgrInfo * execTuplesMatchPrepare(int numCols, Oid *eqOperators)
Definition: execGrouping.c:204
int16 AttrNumber
Definition: attnum.h:21
TupleHashEntry FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot, FmgrInfo *eqfunctions, FmgrInfo *hashfunctions)
Definition: execGrouping.c:425
FmgrInfo * tab_eq_funcs
Definition: execnodes.h:576