Branch data Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * execGrouping.c
4 : : * executor utility routines for grouping, hashing, and aggregation
5 : : *
6 : : * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
7 : : * Portions Copyright (c) 1994, Regents of the University of California
8 : : *
9 : : *
10 : : * IDENTIFICATION
11 : : * src/backend/executor/execGrouping.c
12 : : *
13 : : *-------------------------------------------------------------------------
14 : : */
15 : : #include "postgres.h"
16 : :
17 : : #include <math.h>
18 : :
19 : : #include "access/htup_details.h"
20 : : #include "access/parallel.h"
21 : : #include "common/hashfn.h"
22 : : #include "executor/executor.h"
23 : : #include "miscadmin.h"
24 : : #include "utils/lsyscache.h"
25 : :
26 : : static int TupleHashTableMatch(struct tuplehash_hash *tb, MinimalTuple tuple1, MinimalTuple tuple2);
27 : : static inline uint32 TupleHashTableHash_internal(struct tuplehash_hash *tb,
28 : : MinimalTuple tuple);
29 : : static inline TupleHashEntry LookupTupleHashEntry_internal(TupleHashTable hashtable,
30 : : TupleTableSlot *slot,
31 : : bool *isnew, uint32 hash);
32 : :
33 : : /*
34 : : * Define parameters for tuple hash table code generation. The interface is
35 : : * *also* declared in execnodes.h (to generate the types, which are externally
36 : : * visible).
37 : : */
38 : : #define SH_PREFIX tuplehash
39 : : #define SH_ELEMENT_TYPE TupleHashEntryData
40 : : #define SH_KEY_TYPE MinimalTuple
41 : : #define SH_KEY firstTuple
42 : : #define SH_HASH_KEY(tb, key) TupleHashTableHash_internal(tb, key)
43 : : #define SH_EQUAL(tb, a, b) TupleHashTableMatch(tb, a, b) == 0
44 : : #define SH_SCOPE extern
45 : : #define SH_STORE_HASH
46 : : #define SH_GET_HASH(tb, a) a->hash
47 : : #define SH_DEFINE
48 : : #include "lib/simplehash.h"
49 : :
50 : :
51 : : /*****************************************************************************
52 : : * Utility routines for grouping tuples together
53 : : *****************************************************************************/
54 : :
55 : : /*
56 : : * execTuplesMatchPrepare
57 : : * Build expression that can be evaluated using ExecQual(), returning
58 : : * whether an ExprContext's inner/outer tuples are NOT DISTINCT
59 : : */
60 : : ExprState *
61 : 8043 : execTuplesMatchPrepare(TupleDesc desc,
62 : : int numCols,
63 : : const AttrNumber *keyColIdx,
64 : : const Oid *eqOperators,
65 : : const Oid *collations,
66 : : PlanState *parent)
67 : : {
68 : : Oid *eqFunctions;
69 : : int i;
70 : : ExprState *expr;
71 : :
72 [ + + ]: 8043 : if (numCols == 0)
73 : 35 : return NULL;
74 : :
75 : 8008 : eqFunctions = palloc_array(Oid, numCols);
76 : :
77 : : /* lookup equality functions */
78 [ + + ]: 21789 : for (i = 0; i < numCols; i++)
79 : 13781 : eqFunctions[i] = get_opcode(eqOperators[i]);
80 : :
81 : : /* build actual expression */
82 : 8008 : expr = ExecBuildGroupingEqual(desc, desc, NULL, NULL,
83 : : numCols, keyColIdx, eqFunctions, collations,
84 : : parent);
85 : :
86 : 8008 : return expr;
87 : : }
88 : :
89 : : /*
90 : : * execTuplesHashPrepare
91 : : * Look up the equality and hashing functions needed for a TupleHashTable.
92 : : *
93 : : * This is similar to execTuplesMatchPrepare, but we also need to find the
94 : : * hash functions associated with the equality operators. *eqFunctions and
95 : : * *hashFunctions receive the palloc'd result arrays.
96 : : *
97 : : * Note: we expect that the given operators are not cross-type comparisons.
98 : : */
99 : : void
100 : 6217 : execTuplesHashPrepare(int numCols,
101 : : const Oid *eqOperators,
102 : : Oid **eqFuncOids,
103 : : FmgrInfo **hashFunctions)
104 : : {
105 : : int i;
106 : :
107 : 6217 : *eqFuncOids = palloc_array(Oid, numCols);
108 : 6217 : *hashFunctions = palloc_array(FmgrInfo, numCols);
109 : :
110 [ + + ]: 16938 : for (i = 0; i < numCols; i++)
111 : : {
112 : 10721 : Oid eq_opr = eqOperators[i];
113 : : Oid eq_function;
114 : : Oid left_hash_function;
115 : : Oid right_hash_function;
116 : :
117 : 10721 : eq_function = get_opcode(eq_opr);
118 [ - + ]: 10721 : if (!get_op_hash_functions(eq_opr,
119 : : &left_hash_function, &right_hash_function))
120 [ # # ]: 0 : elog(ERROR, "could not find hash function for hash operator %u",
121 : : eq_opr);
122 : : /* We're not supporting cross-type cases here */
123 : : Assert(left_hash_function == right_hash_function);
124 : 10721 : (*eqFuncOids)[i] = eq_function;
125 : 10721 : fmgr_info(right_hash_function, &(*hashFunctions)[i]);
126 : : }
127 : 6217 : }
128 : :
129 : :
130 : : /*****************************************************************************
131 : : * Utility routines for all-in-memory hash tables
132 : : *
133 : : * These routines build hash tables for grouping tuples together (eg, for
134 : : * hash aggregation). There is one entry for each not-distinct set of tuples
135 : : * presented.
136 : : *****************************************************************************/
137 : :
138 : : /*
139 : : * Construct an empty TupleHashTable
140 : : *
141 : : * parent: PlanState node that will own this hash table
142 : : * inputDesc: tuple descriptor for input tuples
143 : : * inputOps: slot ops for input tuples, or NULL if unknown or not fixed
144 : : * numCols: number of columns to be compared (length of next 4 arrays)
145 : : * keyColIdx: indexes of tuple columns to compare
146 : : * eqfuncoids: OIDs of equality comparison functions to use
147 : : * hashfunctions: FmgrInfos of datatype-specific hashing functions to use
148 : : * collations: collations to use in comparisons
149 : : * nelements: initial estimate of hashtable size
150 : : * additionalsize: size of data that may be stored along with the hash entry
151 : : * metacxt: memory context for long-lived data and the simplehash table
152 : : * tuplescxt: memory context in which to store the hashed tuples themselves
153 : : * tempcxt: short-lived context for evaluation hash and comparison functions
154 : : * use_variable_hash_iv: if true, adjust hash IV per-parallel-worker
155 : : *
156 : : * The hashfunctions array may be made with execTuplesHashPrepare(). Note they
157 : : * are not cross-type functions, but expect to see the table datatype(s)
158 : : * on both sides.
159 : : *
160 : : * Note that the keyColIdx, hashfunctions, and collations arrays must be
161 : : * allocated in storage that will live as long as the hashtable does.
162 : : *
163 : : * The metacxt and tuplescxt are separate because it's usually desirable for
164 : : * tuplescxt to be a BumpContext to avoid memory wastage, while metacxt must
165 : : * support pfree in case the simplehash table needs to be enlarged. (We could
166 : : * simplify the API of TupleHashTables by managing the tuplescxt internally.
167 : : * But that would be disadvantageous to nodeAgg.c and nodeSubplan.c, which use
168 : : * a single tuplescxt for multiple TupleHashTables that are reset together.)
169 : : *
170 : : * LookupTupleHashEntry, FindTupleHashEntry, and related functions may leak
171 : : * memory in the tempcxt. It is caller's responsibility to reset that context
172 : : * reasonably often, typically once per tuple. (We do it that way, rather
173 : : * than managing an extra context within the hashtable, because in many cases
174 : : * the caller can specify a tempcxt that it needs to reset per-tuple anyway.)
175 : : *
176 : : * We don't currently provide DestroyTupleHashTable functionality; the hash
177 : : * table will be cleaned up at destruction of the metacxt. (Some callers
178 : : * bother to delete the tuplescxt explicitly, though it'd be sufficient to
179 : : * ensure it's a child of the metacxt.) There's not much point in working
180 : : * harder than this so long as the expression-evaluation infrastructure
181 : : * behaves similarly.
182 : : */
183 : : TupleHashTable
184 : 5292 : BuildTupleHashTable(PlanState *parent,
185 : : TupleDesc inputDesc,
186 : : const TupleTableSlotOps *inputOps,
187 : : int numCols,
188 : : AttrNumber *keyColIdx,
189 : : const Oid *eqfuncoids,
190 : : FmgrInfo *hashfunctions,
191 : : Oid *collations,
192 : : double nelements,
193 : : Size additionalsize,
194 : : MemoryContext metacxt,
195 : : MemoryContext tuplescxt,
196 : : MemoryContext tempcxt,
197 : : bool use_variable_hash_iv)
198 : : {
199 : : TupleHashTable hashtable;
200 : : uint32 nbuckets;
201 : : MemoryContext oldcontext;
202 : 5292 : uint32 hash_iv = 0;
203 : :
204 : : /*
205 : : * tuplehash_create requires a uint32 element count, so we had better
206 : : * clamp the given nelements to fit in that. We'd also better do
207 : : * something sane when faced with a zero or NaN estimate. There are
208 : : * various reasons why the planner might not be able to provide a good
209 : : * estimate here; for example, recursive CTEs don't base their estimate on
210 : : * anything reliable and can yield some rather large estimates. Here we
211 : : * cap nbuckets to hash_mem to help prevent insane memory allocations. The
212 : : * hash table can still grow when the bucket count is insufficient. That
213 : : * will make the query a little slower, but that's better than outright
214 : : * failing due to OOM if we were to request an insane bucket count.
215 : : * Queries being slightly slower with smaller work_mem values is also
216 : : * aligned to user expectations. We purposefully don't include the tuple
217 : : * width in this calculation, as that would make the cap depend on planner
218 : : * estimates for the tuple width, which could also be unreliable.
219 : : */
220 [ + - - + ]: 5292 : if (isnan(nelements) || nelements <= 0)
221 : 0 : nbuckets = 1;
222 : : else
223 : : {
224 : : size_t entrysize;
225 : : size_t hash_mem_limit;
226 : :
227 [ - + ]: 5292 : if (nelements >= PG_UINT32_MAX)
228 : 0 : nbuckets = PG_UINT32_MAX;
229 : : else
230 : 5292 : nbuckets = (uint32) nelements;
231 : :
232 : 5292 : entrysize = sizeof(TupleHashEntryData) + additionalsize;
233 : 5292 : hash_mem_limit = get_hash_memory_limit() / entrysize;
234 [ + + ]: 5292 : if (nbuckets > hash_mem_limit)
235 : 12 : nbuckets = hash_mem_limit;
236 : : }
237 : :
238 : : /* tuplescxt must be separate, else ResetTupleHashTable breaks things */
239 : : Assert(metacxt != tuplescxt);
240 : :
241 : : /* ensure additionalsize is maxalign'ed */
242 : 5292 : additionalsize = MAXALIGN(additionalsize);
243 : :
244 : 5292 : oldcontext = MemoryContextSwitchTo(metacxt);
245 : :
246 : 5292 : hashtable = palloc_object(TupleHashTableData);
247 : :
248 : 5292 : hashtable->numCols = numCols;
249 : 5292 : hashtable->keyColIdx = keyColIdx;
250 : 5292 : hashtable->tab_collations = collations;
251 : 5292 : hashtable->tuplescxt = tuplescxt;
252 : 5292 : hashtable->tempcxt = tempcxt;
253 : 5292 : hashtable->additionalsize = additionalsize;
254 : 5292 : hashtable->inputslot = NULL;
255 : 5292 : hashtable->in_hash_expr = NULL;
256 : 5292 : hashtable->cur_eq_func = NULL;
257 : :
258 : : /*
259 : : * If parallelism is in use, even if the leader backend is performing the
260 : : * scan itself, we don't want to create the hashtable exactly the same way
261 : : * in all workers. As hashtables are iterated over in keyspace-order,
262 : : * doing so in all processes in the same way is likely to lead to
263 : : * "unbalanced" hashtables when the table size initially is
264 : : * underestimated.
265 : : */
266 [ + + ]: 5292 : if (use_variable_hash_iv)
267 : 672 : hash_iv = murmurhash32(ParallelWorkerNumber);
268 : :
269 : 5292 : hashtable->hashtab = tuplehash_create(metacxt, nbuckets, hashtable);
270 : :
271 : : /*
272 : : * We copy the input tuple descriptor just for safety --- we assume all
273 : : * input tuples will have equivalent descriptors.
274 : : */
275 : 5292 : hashtable->tableslot = MakeSingleTupleTableSlot(CreateTupleDescCopy(inputDesc),
276 : : &TTSOpsMinimalTuple);
277 : :
278 : : /* build hash ExprState for all columns */
279 : 5292 : hashtable->tab_hash_expr = ExecBuildHash32FromAttrs(inputDesc,
280 : : inputOps,
281 : : hashfunctions,
282 : : collations,
283 : : numCols,
284 : : keyColIdx,
285 : : parent,
286 : : hash_iv);
287 : :
288 : : /* build comparator for all columns */
289 : 5292 : hashtable->tab_eq_func = ExecBuildGroupingEqual(inputDesc, inputDesc,
290 : : inputOps,
291 : : &TTSOpsMinimalTuple,
292 : : numCols,
293 : : keyColIdx, eqfuncoids, collations,
294 : : parent);
295 : :
296 : : /*
297 : : * While not pretty, it's ok to not shut down this context, but instead
298 : : * rely on the containing memory context being reset, as
299 : : * ExecBuildGroupingEqual() only builds a very simple expression calling
300 : : * functions (i.e. nothing that'd employ RegisterExprContextCallback()).
301 : : */
302 : 5292 : hashtable->exprcontext = CreateStandaloneExprContext();
303 : :
304 : 5292 : MemoryContextSwitchTo(oldcontext);
305 : :
306 : 5292 : return hashtable;
307 : : }
308 : :
309 : : /*
310 : : * Reset contents of the hashtable to be empty, preserving all the non-content
311 : : * state.
312 : : *
313 : : * Note: in usages where several TupleHashTables share a tuplescxt, all must
314 : : * be reset together, as the first one's reset call will destroy all their
315 : : * data. The additional reset calls for the rest will redundantly reset the
316 : : * tuplescxt. But because of mcxt.c's isReset flag, that's cheap enough that
317 : : * we need not avoid it.
318 : : */
319 : : void
320 : 129344 : ResetTupleHashTable(TupleHashTable hashtable)
321 : : {
322 : 129344 : tuplehash_reset(hashtable->hashtab);
323 : 129344 : MemoryContextReset(hashtable->tuplescxt);
324 : 129344 : }
325 : :
326 : : /*
327 : : * Estimate the amount of space needed for a TupleHashTable with nentries
328 : : * entries, if the tuples have average data width tupleWidth and the caller
329 : : * requires additionalsize extra space per entry.
330 : : *
331 : : * Return SIZE_MAX if it'd overflow size_t.
332 : : *
333 : : * nentries is "double" because this is meant for use by the planner,
334 : : * which typically works with double rowcount estimates. So we'd need to
335 : : * clamp to integer somewhere and that might as well be here. We do expect
336 : : * the value not to be NaN or negative, else the result will be garbage.
337 : : */
338 : : Size
339 : 3962 : EstimateTupleHashTableSpace(double nentries,
340 : : Size tupleWidth,
341 : : Size additionalsize)
342 : : {
343 : : Size sh_space;
344 : : double tuples_space;
345 : :
346 : : /* First estimate the space needed for the simplehash table */
347 : 3962 : sh_space = tuplehash_estimate_space(nentries);
348 : :
349 : : /* Give up if that's already too big */
350 [ + + ]: 3962 : if (sh_space >= SIZE_MAX)
351 : 5 : return sh_space;
352 : :
353 : : /*
354 : : * Compute space needed for hashed tuples with additional data. nentries
355 : : * must be somewhat sane, so it should be safe to compute this product.
356 : : *
357 : : * We assume that the hashed tuples will be kept in a BumpContext so that
358 : : * there is not additional per-tuple overhead.
359 : : *
360 : : * (Note that this is only accurate if MEMORY_CONTEXT_CHECKING is off,
361 : : * else bump.c will add a MemoryChunk header to each tuple. However, it
362 : : * seems undesirable for debug builds to make different planning choices
363 : : * than production builds, so we assume the production behavior always.)
364 : : */
365 : 3957 : tuples_space = nentries * (MAXALIGN(SizeofMinimalTupleHeader) +
366 : 3957 : MAXALIGN(tupleWidth) +
367 : 3957 : MAXALIGN(additionalsize));
368 : :
369 : : /*
370 : : * Check for size_t overflow. This coding is trickier than it may appear,
371 : : * because on 64-bit machines SIZE_MAX cannot be represented exactly as a
372 : : * double. We must cast it explicitly to suppress compiler warnings about
373 : : * an inexact conversion, and we must trust that any double value that
374 : : * compares strictly less than "(double) SIZE_MAX" will cast to a
375 : : * representable size_t value.
376 : : */
377 [ - + ]: 3957 : if (sh_space + tuples_space >= (double) SIZE_MAX)
378 : 0 : return SIZE_MAX;
379 : :
380 : : /* We don't bother estimating size of the miscellaneous overhead data */
381 : 3957 : return (Size) (sh_space + tuples_space);
382 : : }
383 : :
384 : : /*
385 : : * Find or create a hashtable entry for the tuple group containing the
386 : : * given tuple. The tuple must be the same type as the hashtable entries.
387 : : *
388 : : * If isnew is NULL, we do not create new entries; we return NULL if no
389 : : * match is found.
390 : : *
391 : : * If hash is not NULL, we set it to the calculated hash value. This allows
392 : : * callers access to the hash value even if no entry is returned.
393 : : *
394 : : * If isnew isn't NULL, then a new entry is created if no existing entry
395 : : * matches. On return, *isnew is true if the entry is newly created,
396 : : * false if it existed already. The additional data in the new entry has
397 : : * been zeroed.
398 : : */
399 : : TupleHashEntry
400 : 5592483 : LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
401 : : bool *isnew, uint32 *hash)
402 : : {
403 : : TupleHashEntry entry;
404 : : MemoryContext oldContext;
405 : : uint32 local_hash;
406 : :
407 : : /* Need to run the hash functions in short-lived context */
408 : 5592483 : oldContext = MemoryContextSwitchTo(hashtable->tempcxt);
409 : :
410 : : /* set up data needed by hash and match functions */
411 : 5592483 : hashtable->inputslot = slot;
412 : 5592483 : hashtable->in_hash_expr = hashtable->tab_hash_expr;
413 : 5592483 : hashtable->cur_eq_func = hashtable->tab_eq_func;
414 : :
415 : 5592483 : local_hash = TupleHashTableHash_internal(hashtable->hashtab, NULL);
416 : 5592479 : entry = LookupTupleHashEntry_internal(hashtable, slot, isnew, local_hash);
417 : :
418 [ + + ]: 5592479 : if (hash != NULL)
419 : 4852504 : *hash = local_hash;
420 : :
421 : : Assert(entry == NULL || entry->hash == local_hash);
422 : :
423 : 5592479 : MemoryContextSwitchTo(oldContext);
424 : :
425 : 5592479 : return entry;
426 : : }
427 : :
428 : : /*
429 : : * Compute the hash value for a tuple
430 : : */
431 : : uint32
432 : 0 : TupleHashTableHash(TupleHashTable hashtable, TupleTableSlot *slot)
433 : : {
434 : : MemoryContext oldContext;
435 : : uint32 hash;
436 : :
437 : 0 : hashtable->inputslot = slot;
438 : 0 : hashtable->in_hash_expr = hashtable->tab_hash_expr;
439 : :
440 : : /* Need to run the hash functions in short-lived context */
441 : 0 : oldContext = MemoryContextSwitchTo(hashtable->tempcxt);
442 : :
443 : 0 : hash = TupleHashTableHash_internal(hashtable->hashtab, NULL);
444 : :
445 : 0 : MemoryContextSwitchTo(oldContext);
446 : :
447 : 0 : return hash;
448 : : }
449 : :
450 : : /*
451 : : * A variant of LookupTupleHashEntry for callers that have already computed
452 : : * the hash value.
453 : : */
454 : : TupleHashEntry
455 : 777914 : LookupTupleHashEntryHash(TupleHashTable hashtable, TupleTableSlot *slot,
456 : : bool *isnew, uint32 hash)
457 : : {
458 : : TupleHashEntry entry;
459 : : MemoryContext oldContext;
460 : :
461 : : /* Need to run the hash functions in short-lived context */
462 : 777914 : oldContext = MemoryContextSwitchTo(hashtable->tempcxt);
463 : :
464 : : /* set up data needed by hash and match functions */
465 : 777914 : hashtable->inputslot = slot;
466 : 777914 : hashtable->in_hash_expr = hashtable->tab_hash_expr;
467 : 777914 : hashtable->cur_eq_func = hashtable->tab_eq_func;
468 : :
469 : 777914 : entry = LookupTupleHashEntry_internal(hashtable, slot, isnew, hash);
470 : : Assert(entry == NULL || entry->hash == hash);
471 : :
472 : 777914 : MemoryContextSwitchTo(oldContext);
473 : :
474 : 777914 : return entry;
475 : : }
476 : :
477 : : /*
478 : : * Search for a hashtable entry matching the given tuple. No entry is
479 : : * created if there's not a match. This is similar to the non-creating
480 : : * case of LookupTupleHashEntry, except that it supports cross-type
481 : : * comparisons, in which the given tuple is not of the same type as the
482 : : * table entries. The caller must provide the hash ExprState to use for
483 : : * the input tuple, as well as the equality ExprState, since these may be
484 : : * different from the table's internal functions.
485 : : */
486 : : TupleHashEntry
487 : 606556 : FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
488 : : ExprState *eqcomp,
489 : : ExprState *hashexpr)
490 : : {
491 : : TupleHashEntry entry;
492 : : MemoryContext oldContext;
493 : : MinimalTuple key;
494 : :
495 : : /* Need to run the hash functions in short-lived context */
496 : 606556 : oldContext = MemoryContextSwitchTo(hashtable->tempcxt);
497 : :
498 : : /* Set up data needed by hash and match functions */
499 : 606556 : hashtable->inputslot = slot;
500 : 606556 : hashtable->in_hash_expr = hashexpr;
501 : 606556 : hashtable->cur_eq_func = eqcomp;
502 : :
503 : : /* Search the hash table */
504 : 606556 : key = NULL; /* flag to reference inputslot */
505 : 606556 : entry = tuplehash_lookup(hashtable->hashtab, key);
506 : 606556 : MemoryContextSwitchTo(oldContext);
507 : :
508 : 606556 : return entry;
509 : : }
510 : :
511 : : /*
512 : : * If tuple is NULL, use the input slot instead. This convention avoids the
513 : : * need to materialize virtual input tuples unless they actually need to get
514 : : * copied into the table.
515 : : *
516 : : * Also, the caller must select an appropriate memory context for running
517 : : * the hash functions.
518 : : */
519 : : static uint32
520 : 6199039 : TupleHashTableHash_internal(struct tuplehash_hash *tb,
521 : : MinimalTuple tuple)
522 : : {
523 : 6199039 : TupleHashTable hashtable = (TupleHashTable) tb->private_data;
524 : : uint32 hashkey;
525 : : TupleTableSlot *slot;
526 : : bool isnull;
527 : :
528 [ + - ]: 6199039 : if (tuple == NULL)
529 : : {
530 : : /* Process the current input tuple for the table */
531 : 6199039 : hashtable->exprcontext->ecxt_innertuple = hashtable->inputslot;
532 : 6199039 : hashkey = DatumGetUInt32(ExecEvalExpr(hashtable->in_hash_expr,
533 : : hashtable->exprcontext,
534 : : &isnull));
535 : : }
536 : : else
537 : : {
538 : : /*
539 : : * Process a tuple already stored in the table.
540 : : *
541 : : * (this case never actually occurs due to the way simplehash.h is
542 : : * used, as the hash-value is stored in the entries)
543 : : */
544 : 0 : slot = hashtable->exprcontext->ecxt_innertuple = hashtable->tableslot;
545 : 0 : ExecStoreMinimalTuple(tuple, slot, false);
546 : 0 : hashkey = DatumGetUInt32(ExecEvalExpr(hashtable->tab_hash_expr,
547 : : hashtable->exprcontext,
548 : : &isnull));
549 : : }
550 : :
551 : : /*
552 : : * The hashing done above, even with an initial value, doesn't tend to
553 : : * result in good hash perturbation. Running the value produced above
554 : : * through murmurhash32 leads to near perfect hash perturbation.
555 : : */
556 : 6199035 : return murmurhash32(hashkey);
557 : : }
558 : :
559 : : /*
560 : : * Does the work of LookupTupleHashEntry and LookupTupleHashEntryHash. Useful
561 : : * so that we can avoid switching the memory context multiple times for
562 : : * LookupTupleHashEntry.
563 : : *
564 : : * NB: This function may or may not change the memory context. Caller is
565 : : * expected to change it back.
566 : : */
567 : : static inline TupleHashEntry
568 : 6370393 : LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *slot,
569 : : bool *isnew, uint32 hash)
570 : : {
571 : : TupleHashEntryData *entry;
572 : : bool found;
573 : : MinimalTuple key;
574 : :
575 : 6370393 : key = NULL; /* flag to reference inputslot */
576 : :
577 [ + + ]: 6370393 : if (isnew)
578 : : {
579 : 5256810 : entry = tuplehash_insert_hash(hashtable->hashtab, key, hash, &found);
580 : :
581 [ + + ]: 5256810 : if (found)
582 : : {
583 : : /* found pre-existing entry */
584 : 4522746 : *isnew = false;
585 : : }
586 : : else
587 : : {
588 : : /* created new entry */
589 : 734064 : *isnew = true;
590 : :
591 : 734064 : MemoryContextSwitchTo(hashtable->tuplescxt);
592 : :
593 : : /*
594 : : * Copy the first tuple into the tuples context, and request
595 : : * additionalsize extra bytes before the allocation.
596 : : *
597 : : * The caller can get a pointer to the additional data with
598 : : * TupleHashEntryGetAdditional(), and store arbitrary data there.
599 : : * Placing both the tuple and additional data in the same
600 : : * allocation avoids the need to store an extra pointer in
601 : : * TupleHashEntryData or allocate an additional chunk.
602 : : */
603 : 734064 : entry->firstTuple = ExecCopySlotMinimalTupleExtra(slot,
604 : : hashtable->additionalsize);
605 : : }
606 : : }
607 : : else
608 : : {
609 : 1113583 : entry = tuplehash_lookup_hash(hashtable->hashtab, key, hash);
610 : : }
611 : :
612 : 6370393 : return entry;
613 : : }
614 : :
615 : : /*
616 : : * See whether two tuples (presumably of the same hash value) match
617 : : */
618 : : static int
619 : 4888051 : TupleHashTableMatch(struct tuplehash_hash *tb, MinimalTuple tuple1, MinimalTuple tuple2)
620 : : {
621 : : TupleTableSlot *slot1;
622 : : TupleTableSlot *slot2;
623 : 4888051 : TupleHashTable hashtable = (TupleHashTable) tb->private_data;
624 : 4888051 : ExprContext *econtext = hashtable->exprcontext;
625 : :
626 : : /*
627 : : * We assume that simplehash.h will only ever call us with the first
628 : : * argument being an actual table entry, and the second argument being
629 : : * LookupTupleHashEntry's dummy TupleHashEntryData. The other direction
630 : : * could be supported too, but is not currently required.
631 : : */
632 : : Assert(tuple1 != NULL);
633 : 4888051 : slot1 = hashtable->tableslot;
634 : 4888051 : ExecStoreMinimalTuple(tuple1, slot1, false);
635 : : Assert(tuple2 == NULL);
636 : 4888051 : slot2 = hashtable->inputslot;
637 : :
638 : : /* For crosstype comparisons, the inputslot must be first */
639 : 4888051 : econtext->ecxt_innertuple = slot2;
640 : 4888051 : econtext->ecxt_outertuple = slot1;
641 : 4888051 : return !ExecQualAndReset(hashtable->cur_eq_func, econtext);
642 : : }
|
