Debian Codegraph @

src/backend/executor/nodeHash.c

raw
1 /*-------------------------------------------------------------------------
2 *
3 * nodeHash.c
4 * Routines to hash relations for hashjoin
5 *
6 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
8 *
9 *
10 * IDENTIFICATION
11 * src/backend/executor/nodeHash.c
12 *
13 * See note on parallelism in nodeHashjoin.c.
14 *
15 *-------------------------------------------------------------------------
16 */
17 /*
18 * INTERFACE ROUTINES
19 * MultiExecHash - generate an in-memory hash table of the relation
20 * ExecInitHash - initialize node and subnodes
21 * ExecEndHash - shutdown node and subnodes
22 */
23
24 #include "postgres.h"
25
26 #include <math.h>
27 #include <limits.h>
28
29 #include "access/htup_details.h"
30 #include "access/parallel.h"
31 #include "catalog/pg_statistic.h"
32 #include "commands/tablespace.h"
33 #include "executor/executor.h"
34 #include "executor/hashjoin.h"
35 #include "executor/nodeHash.h"
36 #include "executor/nodeHashjoin.h"
37 #include "miscadmin.h"
38 #include "port/pg_bitutils.h"
39 #include "utils/dynahash.h"
40 #include "utils/lsyscache.h"
41 #include "utils/memutils.h"
42 #include "utils/syscache.h"
43 #include "utils/wait_event.h"
44
45 static void ExecHashIncreaseNumBatches(HashJoinTable hashtable);
46 static void ExecHashIncreaseNumBuckets(HashJoinTable hashtable);
47 static void ExecParallelHashIncreaseNumBatches(HashJoinTable hashtable);
48 static void ExecParallelHashIncreaseNumBuckets(HashJoinTable hashtable);
49 static void ExecHashBuildSkewHash(HashState *hashstate,
50 HashJoinTable hashtable, Hash *node,
51 int mcvsToUse);
52 static void ExecHashSkewTableInsert(HashJoinTable hashtable,
53 TupleTableSlot *slot,
54 uint32 hashvalue,
55 int bucketNumber);
56 static void ExecHashRemoveNextSkewBucket(HashJoinTable hashtable);
57
58 static void *dense_alloc(HashJoinTable hashtable, Size size);
59 static HashJoinTuple ExecParallelHashTupleAlloc(HashJoinTable hashtable,
60 size_t size,
61 dsa_pointer *shared);
62 static void MultiExecPrivateHash(HashState *node);
63 static void MultiExecParallelHash(HashState *node);
64 static inline HashJoinTuple ExecParallelHashFirstTuple(HashJoinTable hashtable,
65 int bucketno);
66 static inline HashJoinTuple ExecParallelHashNextTuple(HashJoinTable hashtable,
67 HashJoinTuple tuple);
68 static inline void ExecParallelHashPushTuple(dsa_pointer_atomic *head,
69 HashJoinTuple tuple,
70 dsa_pointer tuple_shared);
71 static void ExecParallelHashJoinSetUpBatches(HashJoinTable hashtable, int nbatch);
72 static void ExecParallelHashEnsureBatchAccessors(HashJoinTable hashtable);
73 static void ExecParallelHashRepartitionFirst(HashJoinTable hashtable);
74 static void ExecParallelHashRepartitionRest(HashJoinTable hashtable);
75 static HashMemoryChunk ExecParallelHashPopChunkQueue(HashJoinTable hashtable,
76 dsa_pointer *shared);
77 static bool ExecParallelHashTuplePrealloc(HashJoinTable hashtable,
78 int batchno,
79 size_t size);
80 static void ExecParallelHashMergeCounters(HashJoinTable hashtable);
81 static void ExecParallelHashCloseBatchAccessors(HashJoinTable hashtable);
82
83
84 /* ----------------------------------------------------------------
85 * ExecHash
86 *
87 * stub for pro forma compliance
88 * ----------------------------------------------------------------
89 */
90 static TupleTableSlot *
91 ExecHash(PlanState *pstate)
92 {
93 elog(ERROR, "Hash node does not support ExecProcNode call convention");
94 return NULL;
95 }
96
97 /* ----------------------------------------------------------------
98 * MultiExecHash
99 *
100 * build hash table for hashjoin, doing partitioning if more
101 * than one batch is required.
102 * ----------------------------------------------------------------
103 */
104 Node *
105 MultiExecHash(HashState *node)
106 {
107 /* must provide our own instrumentation support */
108 if (node->ps.instrument)
109 InstrStartNode(node->ps.instrument);
110
111 if (node->parallel_state != NULL)
112 MultiExecParallelHash(node);
113 else
114 MultiExecPrivateHash(node);
115
116 /* must provide our own instrumentation support */
117 if (node->ps.instrument)
118 InstrStopNode(node->ps.instrument, node->hashtable->partialTuples);
119
120 /*
121 * We do not return the hash table directly because it's not a subtype of
122 * Node, and so would violate the MultiExecProcNode API. Instead, our
123 * parent Hashjoin node is expected to know how to fish it out of our node
124 * state. Ugly but not really worth cleaning up, since Hashjoin knows
125 * quite a bit more about Hash besides that.
126 */
127 return NULL;
128 }
129
130 /* ----------------------------------------------------------------
131 * MultiExecPrivateHash
132 *
133 * parallel-oblivious version, building a backend-private
134 * hash table and (if necessary) batch files.
135 * ----------------------------------------------------------------
136 */
137 static void
138 MultiExecPrivateHash(HashState *node)
139 {
140 PlanState *outerNode;
141 HashJoinTable hashtable;
142 TupleTableSlot *slot;
143 ExprContext *econtext;
144
145 /*
146 * get state info from node
147 */
148 outerNode = outerPlanState(node);
149 hashtable = node->hashtable;
150
151 /*
152 * set expression context
153 */
154 econtext = node->ps.ps_ExprContext;
155
156 /*
157 * Get all tuples from the node below the Hash node and insert into the
158 * hash table (or temp files).
159 */
160 for (;;)
161 {
162 bool isnull;
163 Datum hashdatum;
164
165 slot = ExecProcNode(outerNode);
166 if (TupIsNull(slot))
167 break;
168 /* We have to compute the hash value */
169 econtext->ecxt_outertuple = slot;
170
171 ResetExprContext(econtext);
172
173 hashdatum = ExecEvalExprSwitchContext(node->hash_expr, econtext,
174 &isnull);
175
176 if (!isnull)
177 {
178 uint32 hashvalue = DatumGetUInt32(hashdatum);
179 int bucketNumber;
180
181 bucketNumber = ExecHashGetSkewBucket(hashtable, hashvalue);
182 if (bucketNumber != INVALID_SKEW_BUCKET_NO)
183 {
184 /* It's a skew tuple, so put it into that hash table */
185 ExecHashSkewTableInsert(hashtable, slot, hashvalue,
186 bucketNumber);
187 hashtable->skewTuples += 1;
188 }
189 else
190 {
191 /* Not subject to skew optimization, so insert normally */
192 ExecHashTableInsert(hashtable, slot, hashvalue);
193 }
194 hashtable->totalTuples += 1;
195 }
196 }
197
198 /* resize the hash table if needed (NTUP_PER_BUCKET exceeded) */
199 if (hashtable->nbuckets != hashtable->nbuckets_optimal)
200 ExecHashIncreaseNumBuckets(hashtable);
201
202 /* Account for the buckets in spaceUsed (reported in EXPLAIN ANALYZE) */
203 hashtable->spaceUsed += hashtable->nbuckets * sizeof(HashJoinTuple);
204 if (hashtable->spaceUsed > hashtable->spacePeak)
205 hashtable->spacePeak = hashtable->spaceUsed;
206
207 hashtable->partialTuples = hashtable->totalTuples;
208 }
209
210 /* ----------------------------------------------------------------
211 * MultiExecParallelHash
212 *
213 * parallel-aware version, building a shared hash table and
214 * (if necessary) batch files using the combined effort of
215 * a set of co-operating backends.
216 * ----------------------------------------------------------------
217 */
218 static void
219 MultiExecParallelHash(HashState *node)
220 {
221 ParallelHashJoinState *pstate;
222 PlanState *outerNode;
223 HashJoinTable hashtable;
224 TupleTableSlot *slot;
225 ExprContext *econtext;
226 uint32 hashvalue;
227 Barrier *build_barrier;
228 int i;
229
230 /*
231 * get state info from node
232 */
233 outerNode = outerPlanState(node);
234 hashtable = node->hashtable;
235
236 /*
237 * set expression context
238 */
239 econtext = node->ps.ps_ExprContext;
240
241 /*
242 * Synchronize the parallel hash table build. At this stage we know that
243 * the shared hash table has been or is being set up by
244 * ExecHashTableCreate(), but we don't know if our peers have returned
245 * from there or are here in MultiExecParallelHash(), and if so how far
246 * through they are. To find out, we check the build_barrier phase then
247 * and jump to the right step in the build algorithm.
248 */
249 pstate = hashtable->parallel_state;
250 build_barrier = &pstate->build_barrier;
251 Assert(BarrierPhase(build_barrier) >= PHJ_BUILD_ALLOCATE);
252 switch (BarrierPhase(build_barrier))
253 {
254 case PHJ_BUILD_ALLOCATE:
255
256 /*
257 * Either I just allocated the initial hash table in
258 * ExecHashTableCreate(), or someone else is doing that. Either
259 * way, wait for everyone to arrive here so we can proceed.
260 */
261 BarrierArriveAndWait(build_barrier, WAIT_EVENT_HASH_BUILD_ALLOCATE);
262 /* Fall through. */
263
264 case PHJ_BUILD_HASH_INNER:
265
266 /*
267 * It's time to begin hashing, or if we just arrived here then
268 * hashing is already underway, so join in that effort. While
269 * hashing we have to be prepared to help increase the number of
270 * batches or buckets at any time, and if we arrived here when
271 * that was already underway we'll have to help complete that work
272 * immediately so that it's safe to access batches and buckets
273 * below.
274 */
275 if (PHJ_GROW_BATCHES_PHASE(BarrierAttach(&pstate->grow_batches_barrier)) !=
276 PHJ_GROW_BATCHES_ELECT)
277 ExecParallelHashIncreaseNumBatches(hashtable);
278 if (PHJ_GROW_BUCKETS_PHASE(BarrierAttach(&pstate->grow_buckets_barrier)) !=
279 PHJ_GROW_BUCKETS_ELECT)
280 ExecParallelHashIncreaseNumBuckets(hashtable);
281 ExecParallelHashEnsureBatchAccessors(hashtable);
282 ExecParallelHashTableSetCurrentBatch(hashtable, 0);
283 for (;;)
284 {
285 bool isnull;
286
287 slot = ExecProcNode(outerNode);
288 if (TupIsNull(slot))
289 break;
290 econtext->ecxt_outertuple = slot;
291
292 ResetExprContext(econtext);
293
294 hashvalue = DatumGetUInt32(ExecEvalExprSwitchContext(node->hash_expr,
295 econtext,
296 &isnull));
297
298 if (!isnull)
299 ExecParallelHashTableInsert(hashtable, slot, hashvalue);
300 hashtable->partialTuples++;
301 }
302
303 /*
304 * Make sure that any tuples we wrote to disk are visible to
305 * others before anyone tries to load them.
306 */
307 for (i = 0; i < hashtable->nbatch; ++i)
308 sts_end_write(hashtable->batches[i].inner_tuples);
309
310 /*
311 * Update shared counters. We need an accurate total tuple count
312 * to control the empty table optimization.
313 */
314 ExecParallelHashMergeCounters(hashtable);
315
316 BarrierDetach(&pstate->grow_buckets_barrier);
317 BarrierDetach(&pstate->grow_batches_barrier);
318
319 /*
320 * Wait for everyone to finish building and flushing files and
321 * counters.
322 */
323 if (BarrierArriveAndWait(build_barrier,
324 WAIT_EVENT_HASH_BUILD_HASH_INNER))
325 {
326 /*
327 * Elect one backend to disable any further growth. Batches
328 * are now fixed. While building them we made sure they'd fit
329 * in our memory budget when we load them back in later (or we
330 * tried to do that and gave up because we detected extreme
331 * skew).
332 */
333 pstate->growth = PHJ_GROWTH_DISABLED;
334 }
335 }
336
337 /*
338 * We're not yet attached to a batch. We all agree on the dimensions and
339 * number of inner tuples (for the empty table optimization).
340 */
341 hashtable->curbatch = -1;
342 hashtable->nbuckets = pstate->nbuckets;
343 hashtable->log2_nbuckets = my_log2(hashtable->nbuckets);
344 hashtable->totalTuples = pstate->total_tuples;
345
346 /*
347 * Unless we're completely done and the batch state has been freed, make
348 * sure we have accessors.
349 */
350 if (BarrierPhase(build_barrier) < PHJ_BUILD_FREE)
351 ExecParallelHashEnsureBatchAccessors(hashtable);
352
353 /*
354 * The next synchronization point is in ExecHashJoin's HJ_BUILD_HASHTABLE
355 * case, which will bring the build phase to PHJ_BUILD_RUN (if it isn't
356 * there already).
357 */
358 Assert(BarrierPhase(build_barrier) == PHJ_BUILD_HASH_OUTER ||
359 BarrierPhase(build_barrier) == PHJ_BUILD_RUN ||
360 BarrierPhase(build_barrier) == PHJ_BUILD_FREE);
361 }
362
363 /* ----------------------------------------------------------------
364 * ExecInitHash
365 *
366 * Init routine for Hash node
367 * ----------------------------------------------------------------
368 */
369 HashState *
370 ExecInitHash(Hash *node, EState *estate, int eflags)
371 {
372 HashState *hashstate;
373
374 /* check for unsupported flags */
375 Assert(!(eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)));
376
377 /*
378 * create state structure
379 */
380 hashstate = makeNode(HashState);
381 hashstate->ps.plan = (Plan *) node;
382 hashstate->ps.state = estate;
383 hashstate->ps.ExecProcNode = ExecHash;
384 /* delay building hashtable until ExecHashTableCreate() in executor run */
385 hashstate->hashtable = NULL;
386
387 /*
388 * Miscellaneous initialization
389 *
390 * create expression context for node
391 */
392 ExecAssignExprContext(estate, &hashstate->ps);
393
394 /*
395 * initialize child nodes
396 */
397 outerPlanState(hashstate) = ExecInitNode(outerPlan(node), estate, eflags);
398
399 /*
400 * initialize our result slot and type. No need to build projection
401 * because this node doesn't do projections.
402 */
403 ExecInitResultTupleSlotTL(&hashstate->ps, &TTSOpsMinimalTuple);
404 hashstate->ps.ps_ProjInfo = NULL;
405
406 Assert(node->plan.qual == NIL);
407
408 /*
409 * Delay initialization of hash_expr until ExecInitHashJoin(). We cannot
410 * build the ExprState here as we don't yet know the join type we're going
411 * to be hashing values for and we need to know that before calling
412 * ExecBuildHash32Expr as the keep_nulls parameter depends on the join
413 * type.
414 */
415 hashstate->hash_expr = NULL;
416
417 return hashstate;
418 }
419
420 /* ---------------------------------------------------------------
421 * ExecEndHash
422 *
423 * clean up routine for Hash node
424 * ----------------------------------------------------------------
425 */
426 void
427 ExecEndHash(HashState *node)
428 {
429 PlanState *outerPlan;
430
431 /*
432 * shut down the subplan
433 */
434 outerPlan = outerPlanState(node);
435 ExecEndNode(outerPlan);
436 }
437
438
439 /* ----------------------------------------------------------------
440 * ExecHashTableCreate
441 *
442 * create an empty hashtable data structure for hashjoin.
443 * ----------------------------------------------------------------
444 */
445 HashJoinTable
446 ExecHashTableCreate(HashState *state)
447 {
448 Hash *node;
449 HashJoinTable hashtable;
450 Plan *outerNode;
451 size_t space_allowed;
452 int nbuckets;
453 int nbatch;
454 double rows;
455 int num_skew_mcvs;
456 int log2_nbuckets;
457 MemoryContext oldcxt;
458
459 /*
460 * Get information about the size of the relation to be hashed (it's the
461 * "outer" subtree of this node, but the inner relation of the hashjoin).
462 * Compute the appropriate size of the hash table.
463 */
464 node = (Hash *) state->ps.plan;
465 outerNode = outerPlan(node);
466
467 /*
468 * If this is shared hash table with a partial plan, then we can't use
469 * outerNode->plan_rows to estimate its size. We need an estimate of the
470 * total number of rows across all copies of the partial plan.
471 */
472 rows = node->plan.parallel_aware ? node->rows_total : outerNode->plan_rows;
473
474 ExecChooseHashTableSize(rows, outerNode->plan_width,
475 OidIsValid(node->skewTable),
476 state->parallel_state != NULL,
477 state->parallel_state != NULL ?
478 state->parallel_state->nparticipants - 1 : 0,
479 &space_allowed,
480 &nbuckets, &nbatch, &num_skew_mcvs);
481
482 /* nbuckets must be a power of 2 */
483 log2_nbuckets = my_log2(nbuckets);
484 Assert(nbuckets == (1 << log2_nbuckets));
485
486 /*
487 * Initialize the hash table control block.
488 *
489 * The hashtable control block is just palloc'd from the executor's
490 * per-query memory context. Everything else should be kept inside the
491 * subsidiary hashCxt, batchCxt or spillCxt.
492 */
493 hashtable = palloc_object(HashJoinTableData);
494 hashtable->nbuckets = nbuckets;
495 hashtable->nbuckets_original = nbuckets;
496 hashtable->nbuckets_optimal = nbuckets;
497 hashtable->log2_nbuckets = log2_nbuckets;
498 hashtable->log2_nbuckets_optimal = log2_nbuckets;
499 hashtable->buckets.unshared = NULL;
500 hashtable->skewEnabled = false;
501 hashtable->skewBucket = NULL;
502 hashtable->skewBucketLen = 0;
503 hashtable->nSkewBuckets = 0;
504 hashtable->skewBucketNums = NULL;
505 hashtable->nbatch = nbatch;
506 hashtable->curbatch = 0;
507 hashtable->nbatch_original = nbatch;
508 hashtable->nbatch_outstart = nbatch;
509 hashtable->growEnabled = true;
510 hashtable->totalTuples = 0;
511 hashtable->partialTuples = 0;
512 hashtable->skewTuples = 0;
513 hashtable->innerBatchFile = NULL;
514 hashtable->outerBatchFile = NULL;
515 hashtable->spaceUsed = 0;
516 hashtable->spacePeak = 0;
517 hashtable->spaceAllowed = space_allowed;
518 hashtable->spaceUsedSkew = 0;
519 hashtable->spaceAllowedSkew =
520 hashtable->spaceAllowed * SKEW_HASH_MEM_PERCENT / 100;
521 hashtable->chunks = NULL;
522 hashtable->current_chunk = NULL;
523 hashtable->parallel_state = state->parallel_state;
524 hashtable->area = state->ps.state->es_query_dsa;
525 hashtable->batches = NULL;
526
527 #ifdef HJDEBUG
528 printf("Hashjoin %p: initial nbatch = %d, nbuckets = %d\n",
529 hashtable, nbatch, nbuckets);
530 #endif
531
532 /*
533 * Create temporary memory contexts in which to keep the hashtable working
534 * storage. See notes in executor/hashjoin.h.
535 */
536 hashtable->hashCxt = AllocSetContextCreate(CurrentMemoryContext,
537 "HashTableContext",
538 ALLOCSET_DEFAULT_SIZES);
539
540 hashtable->batchCxt = AllocSetContextCreate(hashtable->hashCxt,
541 "HashBatchContext",
542 ALLOCSET_DEFAULT_SIZES);
543
544 hashtable->spillCxt = AllocSetContextCreate(hashtable->hashCxt,
545 "HashSpillContext",
546 ALLOCSET_DEFAULT_SIZES);
547
548 /* Allocate data that will live for the life of the hashjoin */
549
550 oldcxt = MemoryContextSwitchTo(hashtable->hashCxt);
551
552 if (nbatch > 1 && hashtable->parallel_state == NULL)
553 {
554 MemoryContext oldctx;
555
556 /*
557 * allocate and initialize the file arrays in hashCxt (not needed for
558 * parallel case which uses shared tuplestores instead of raw files)
559 */
560 oldctx = MemoryContextSwitchTo(hashtable->spillCxt);
561
562 hashtable->innerBatchFile = palloc0_array(BufFile *, nbatch);
563 hashtable->outerBatchFile = palloc0_array(BufFile *, nbatch);
564
565 MemoryContextSwitchTo(oldctx);
566
567 /* The files will not be opened until needed... */
568 /* ... but make sure we have temp tablespaces established for them */
569 PrepareTempTablespaces();
570 }
571
572 MemoryContextSwitchTo(oldcxt);
573
574 if (hashtable->parallel_state)
575 {
576 ParallelHashJoinState *pstate = hashtable->parallel_state;
577 Barrier *build_barrier;
578
579 /*
580 * Attach to the build barrier. The corresponding detach operation is
581 * in ExecHashTableDetach. Note that we won't attach to the
582 * batch_barrier for batch 0 yet. We'll attach later and start it out
583 * in PHJ_BATCH_PROBE phase, because batch 0 is allocated up front and
584 * then loaded while hashing (the standard hybrid hash join
585 * algorithm), and we'll coordinate that using build_barrier.
586 */
587 build_barrier = &pstate->build_barrier;
588 BarrierAttach(build_barrier);
589
590 /*
591 * So far we have no idea whether there are any other participants,
592 * and if so, what phase they are working on. The only thing we care
593 * about at this point is whether someone has already created the
594 * SharedHashJoinBatch objects and the hash table for batch 0. One
595 * backend will be elected to do that now if necessary.
596 */
597 if (BarrierPhase(build_barrier) == PHJ_BUILD_ELECT &&
598 BarrierArriveAndWait(build_barrier, WAIT_EVENT_HASH_BUILD_ELECT))
599 {
600 pstate->nbatch = nbatch;
601 pstate->space_allowed = space_allowed;
602 pstate->growth = PHJ_GROWTH_OK;
603
604 /* Set up the shared state for coordinating batches. */
605 ExecParallelHashJoinSetUpBatches(hashtable, nbatch);
606
607 /*
608 * Allocate batch 0's hash table up front so we can load it
609 * directly while hashing.
610 */
611 pstate->nbuckets = nbuckets;
612 ExecParallelHashTableAlloc(hashtable, 0);
613 }
614
615 /*
616 * The next Parallel Hash synchronization point is in
617 * MultiExecParallelHash(), which will progress it all the way to
618 * PHJ_BUILD_RUN. The caller must not return control from this
619 * executor node between now and then.
620 */
621 }
622 else
623 {
624 /*
625 * Prepare context for the first-scan space allocations; allocate the
626 * hashbucket array therein, and set each bucket "empty".
627 */
628 MemoryContextSwitchTo(hashtable->batchCxt);
629
630 hashtable->buckets.unshared = palloc0_array(HashJoinTuple, nbuckets);
631
632 /*
633 * Set up for skew optimization, if possible and there's a need for
634 * more than one batch. (In a one-batch join, there's no point in
635 * it.)
636 */
637 if (nbatch > 1)
638 ExecHashBuildSkewHash(state, hashtable, node, num_skew_mcvs);
639
640 MemoryContextSwitchTo(oldcxt);
641 }
642
643 return hashtable;
644 }
645
646
647 /*
648 * Compute appropriate size for hashtable given the estimated size of the
649 * relation to be hashed (number of rows and average row width).
650 *
651 * This is exported so that the planner's costsize.c can use it.
652 */
653
654 /* Target bucket loading (tuples per bucket) */
655 #define NTUP_PER_BUCKET 1
656
657 void
658 ExecChooseHashTableSize(double ntuples, int tupwidth, bool useskew,
659 bool try_combined_hash_mem,
660 int parallel_workers,
661 size_t *space_allowed,
662 int *numbuckets,
663 int *numbatches,
664 int *num_skew_mcvs)
665 {
666 int tupsize;
667 double inner_rel_bytes;
668 size_t hash_table_bytes;
669 size_t bucket_bytes;
670 size_t max_pointers;
671 int nbatch = 1;
672 int nbuckets;
673 double dbuckets;
674
675 /* Force a plausible relation size if no info */
676 if (ntuples <= 0.0)
677 ntuples = 1000.0;
678
679 /*
680 * Estimate tupsize based on footprint of tuple in hashtable... note this
681 * does not allow for any palloc overhead. The manipulations of spaceUsed
682 * don't count palloc overhead either.
683 */
684 tupsize = HJTUPLE_OVERHEAD +
685 MAXALIGN(SizeofMinimalTupleHeader) +
686 MAXALIGN(tupwidth);
687 inner_rel_bytes = ntuples * tupsize;
688
689 /*
690 * Compute in-memory hashtable size limit from GUCs.
691 */
692 hash_table_bytes = get_hash_memory_limit();
693
694 /*
695 * Parallel Hash tries to use the combined hash_mem of all workers to
696 * avoid the need to batch. If that won't work, it falls back to hash_mem
697 * per worker and tries to process batches in parallel.
698 */
699 if (try_combined_hash_mem)
700 {
701 /* Careful, this could overflow size_t */
702 double newlimit;
703
704 newlimit = (double) hash_table_bytes * (double) (parallel_workers + 1);
705 newlimit = Min(newlimit, (double) SIZE_MAX);
706 hash_table_bytes = (size_t) newlimit;
707 }
708
709 *space_allowed = hash_table_bytes;
710
711 /*
712 * If skew optimization is possible, estimate the number of skew buckets
713 * that will fit in the memory allowed, and decrement the assumed space
714 * available for the main hash table accordingly.
715 *
716 * We make the optimistic assumption that each skew bucket will contain
717 * one inner-relation tuple. If that turns out to be low, we will recover
718 * at runtime by reducing the number of skew buckets.
719 *
720 * hashtable->skewBucket will have up to 8 times as many HashSkewBucket
721 * pointers as the number of MCVs we allow, since ExecHashBuildSkewHash
722 * will round up to the next power of 2 and then multiply by 4 to reduce
723 * collisions.
724 */
725 if (useskew)
726 {
727 size_t bytes_per_mcv;
728 size_t skew_mcvs;
729
730 /*----------
731 * Compute number of MCVs we could hold in hash_table_bytes
732 *
733 * Divisor is:
734 * size of a hash tuple +
735 * worst-case size of skewBucket[] per MCV +
736 * size of skewBucketNums[] entry +
737 * size of skew bucket struct itself
738 *----------
739 */
740 bytes_per_mcv = tupsize +
741 (8 * sizeof(HashSkewBucket *)) +
742 sizeof(int) +
743 SKEW_BUCKET_OVERHEAD;
744 skew_mcvs = hash_table_bytes / bytes_per_mcv;
745
746 /*
747 * Now scale by SKEW_HASH_MEM_PERCENT (we do it in this order so as
748 * not to worry about size_t overflow in the multiplication)
749 */
750 skew_mcvs = (skew_mcvs * SKEW_HASH_MEM_PERCENT) / 100;
751
752 /* Now clamp to integer range */
753 skew_mcvs = Min(skew_mcvs, INT_MAX);
754
755 *num_skew_mcvs = (int) skew_mcvs;
756
757 /* Reduce hash_table_bytes by the amount needed for the skew table */
758 if (skew_mcvs > 0)
759 hash_table_bytes -= skew_mcvs * bytes_per_mcv;
760 }
761 else
762 *num_skew_mcvs = 0;
763
764 /*
765 * Set nbuckets to achieve an average bucket load of NTUP_PER_BUCKET when
766 * memory is filled, assuming a single batch; but limit the value so that
767 * the pointer arrays we'll try to allocate do not exceed hash_table_bytes
768 * nor MaxAllocSize.
769 *
770 * Note that both nbuckets and nbatch must be powers of 2 to make
771 * ExecHashGetBucketAndBatch fast.
772 */
773 max_pointers = hash_table_bytes / sizeof(HashJoinTuple);
774 max_pointers = Min(max_pointers, MaxAllocSize / sizeof(HashJoinTuple));
775 /* If max_pointers isn't a power of 2, must round it down to one */
776 max_pointers = pg_prevpower2_size_t(max_pointers);
777
778 /* Also ensure we avoid integer overflow in nbatch and nbuckets */
779 /* (this step is redundant given the current value of MaxAllocSize) */
780 max_pointers = Min(max_pointers, INT_MAX / 2 + 1);
781
782 dbuckets = ceil(ntuples / NTUP_PER_BUCKET);
783 dbuckets = Min(dbuckets, max_pointers);
784 nbuckets = (int) dbuckets;
785 /* don't let nbuckets be really small, though ... */
786 nbuckets = Max(nbuckets, 1024);
787 /* ... and force it to be a power of 2. */
788 nbuckets = pg_nextpower2_32(nbuckets);
789
790 /*
791 * If there's not enough space to store the projected number of tuples and
792 * the required bucket headers, we will need multiple batches.
793 */
794 bucket_bytes = sizeof(HashJoinTuple) * nbuckets;
795 if (inner_rel_bytes + bucket_bytes > hash_table_bytes)
796 {
797 /* We'll need multiple batches */
798 size_t sbuckets;
799 double dbatch;
800 int minbatch;
801 size_t bucket_size;
802
803 /*
804 * If Parallel Hash with combined hash_mem would still need multiple
805 * batches, we'll have to fall back to regular hash_mem budget.
806 */
807 if (try_combined_hash_mem)
808 {
809 ExecChooseHashTableSize(ntuples, tupwidth, useskew,
810 false, parallel_workers,
811 space_allowed,
812 numbuckets,
813 numbatches,
814 num_skew_mcvs);
815 return;
816 }
817
818 /*
819 * Estimate the number of buckets we'll want to have when hash_mem is
820 * entirely full. Each bucket will contain a bucket pointer plus
821 * NTUP_PER_BUCKET tuples, whose projected size already includes
822 * overhead for the hash code, pointer to the next tuple, etc.
823 */
824 bucket_size = (tupsize * NTUP_PER_BUCKET + sizeof(HashJoinTuple));
825 if (hash_table_bytes <= bucket_size)
826 sbuckets = 1; /* avoid pg_nextpower2_size_t(0) */
827 else
828 sbuckets = pg_nextpower2_size_t(hash_table_bytes / bucket_size);
829 sbuckets = Min(sbuckets, max_pointers);
830 nbuckets = (int) sbuckets;
831 nbuckets = pg_nextpower2_32(nbuckets);
832 bucket_bytes = nbuckets * sizeof(HashJoinTuple);
833
834 /*
835 * Buckets are simple pointers to hashjoin tuples, while tupsize
836 * includes the pointer, hash code, and MinimalTupleData. So buckets
837 * should never really exceed 25% of hash_mem (even for
838 * NTUP_PER_BUCKET=1); except maybe for hash_mem values that are not
839 * 2^N bytes, where we might get more because of doubling. So let's
840 * look for 50% here.
841 */
842 Assert(bucket_bytes <= hash_table_bytes / 2);
843
844 /* Calculate required number of batches. */
845 dbatch = ceil(inner_rel_bytes / (hash_table_bytes - bucket_bytes));
846 dbatch = Min(dbatch, max_pointers);
847 minbatch = (int) dbatch;
848 nbatch = pg_nextpower2_32(Max(2, minbatch));
849 }
850
851 /*
852 * Optimize the total amount of memory consumed by the hash node.
853 *
854 * The nbatch calculation above focuses on the in-memory hash table,
855 * assuming no per-batch overhead. But each batch may have two files, each
856 * with a BLCKSZ buffer. For large nbatch values these buffers may use
857 * significantly more memory than the hash table.
858 *
859 * The total memory usage may be expressed by this formula:
860 *
861 * (inner_rel_bytes / nbatch) + (2 * nbatch * BLCKSZ)
862 *
863 * where (inner_rel_bytes / nbatch) is the size of the in-memory hash
864 * table and (2 * nbatch * BLCKSZ) is the amount of memory used by file
865 * buffers.
866 *
867 * The nbatch calculation however ignores the second part. And for very
868 * large inner_rel_bytes, there may be no nbatch that keeps total memory
869 * usage under the budget (work_mem * hash_mem_multiplier). To deal with
870 * that, we will adjust nbatch to minimize total memory consumption across
871 * both the hashtable and file buffers.
872 *
873 * As we increase the size of the hashtable, the number of batches
874 * decreases, and the total memory usage follows a U-shaped curve. We find
875 * the minimum nbatch by "walking back" -- checking if halving nbatch
876 * would lower the total memory usage. We stop when it no longer helps.
877 *
878 * We only reduce the number of batches. Adding batches reduces memory
879 * usage only when most of the memory is used by the hash table, with
880 * total memory usage within the limit or not far from it. We don't want
881 * to start batching when not needed, even if that would reduce memory
882 * usage.
883 *
884 * While growing the hashtable, we also adjust the number of buckets to
885 * maintain a load factor of NTUP_PER_BUCKET while squeezing tuples back
886 * from batches into the hashtable.
887 *
888 * Note that we can only change nbuckets during initial hashtable sizing.
889 * Once we start building the hash, nbuckets is fixed (we may still grow
890 * the hash table).
891 *
892 * We double several parameters (space_allowed, nbuckets, num_skew_mcvs),
893 * which introduces a risk of overflow. We avoid this by exiting the loop.
894 * We could do something smarter (e.g. capping nbuckets and continue), but
895 * the complexity is not worth it. Such cases are extremely rare, and this
896 * is a best-effort attempt to reduce memory usage.
897 */
898 while (nbatch > 1)
899 {
900 /* Check that buckets won't overflow MaxAllocSize */
901 if (nbuckets > (MaxAllocSize / sizeof(HashJoinTuple) / 2))
902 break;
903
904 /* num_skew_mcvs should be less than nbuckets */
905 Assert((*num_skew_mcvs) < (INT_MAX / 2));
906
907 /*
908 * Check that space_allowed won't overflow SIZE_MAX.
909 *
910 * We don't use hash_table_bytes here, because it does not include the
911 * skew buckets. And we want to limit the overall memory limit.
912 */
913 if ((*space_allowed) > (SIZE_MAX / 2))
914 break;
915
916 /*
917 * Will halving the number of batches and doubling the size of the
918 * hashtable reduce overall memory usage?
919 *
920 * This is the same as (S = space_allowed):
921 *
922 * (S + 2 * nbatch * BLCKSZ) < (S * 2 + nbatch * BLCKSZ)
923 *
924 * but avoiding intermediate overflow.
925 */
926 if (nbatch < (*space_allowed) / BLCKSZ)
927 break;
928
929 /*
930 * MaxAllocSize is sufficiently small that we are not worried about
931 * overflowing nbuckets.
932 */
933 nbuckets *= 2;
934
935 *num_skew_mcvs = (*num_skew_mcvs) * 2;
936 *space_allowed = (*space_allowed) * 2;
937
938 nbatch /= 2;
939 }
940
941 Assert(nbuckets > 0);
942 Assert(nbatch > 0);
943
944 *numbuckets = nbuckets;
945 *numbatches = nbatch;
946 }
947
948
949 /* ----------------------------------------------------------------
950 * ExecHashTableDestroy
951 *
952 * destroy a hash table
953 * ----------------------------------------------------------------
954 */
955 void
956 ExecHashTableDestroy(HashJoinTable hashtable)
957 {
958 int i;
959
960 /*
961 * Make sure all the temp files are closed. We skip batch 0, since it
962 * can't have any temp files (and the arrays might not even exist if
963 * nbatch is only 1). Parallel hash joins don't use these files.
964 */
965 if (hashtable->innerBatchFile != NULL)
966 {
967 for (i = 1; i < hashtable->nbatch; i++)
968 {
969 if (hashtable->innerBatchFile[i])
970 BufFileClose(hashtable->innerBatchFile[i]);
971 if (hashtable->outerBatchFile[i])
972 BufFileClose(hashtable->outerBatchFile[i]);
973 }
974 }
975
976 /* Release working memory (batchCxt is a child, so it goes away too) */
977 MemoryContextDelete(hashtable->hashCxt);
978
979 /* And drop the control block */
980 pfree(hashtable);
981 }
982
983 /*
984 * Consider adjusting the allowed hash table size, depending on the number
985 * of batches, to minimize the overall memory usage (for both the hashtable
986 * and batch files).
987 *
988 * We're adjusting the size of the hash table, not the (optimal) number of
989 * buckets. We can't change that once we start building the hash, due to how
990 * ExecHashGetBucketAndBatch calculates batchno/bucketno from the hash. This
991 * means the load factor may not be optimal, but we're in damage control so
992 * we accept slower lookups. It's still much better than batch explosion.
993 *
994 * Returns true if we chose to increase the batch size (and thus we don't
995 * need to add batches), and false if we should increase nbatch.
996 */
997 static bool
998 ExecHashIncreaseBatchSize(HashJoinTable hashtable)
999 {
1000 /*
1001 * How much additional memory would doubling nbatch use? Each batch may
1002 * require two buffered files (inner/outer), with a BLCKSZ buffer.
1003 */
1004 size_t batchSpace = (hashtable->nbatch * 2 * (size_t) BLCKSZ);
1005
1006 /*
1007 * Compare the new space needed for doubling nbatch and for enlarging the
1008 * in-memory hash table. If doubling the hash table needs less memory,
1009 * just do that. Otherwise, continue with doubling the nbatch.
1010 *
1011 * We're either doubling spaceAllowed or batchSpace, so which of those
1012 * increases the memory usage the least is the same as comparing the
1013 * values directly.
1014 */
1015 if (hashtable->spaceAllowed <= batchSpace)
1016 {
1017 hashtable->spaceAllowed *= 2;
1018 return true;
1019 }
1020
1021 return false;
1022 }
1023
1024 /*
1025 * ExecHashIncreaseNumBatches
1026 * increase the original number of batches in order to reduce
1027 * current memory consumption
1028 */
1029 static void
1030 ExecHashIncreaseNumBatches(HashJoinTable hashtable)
1031 {
1032 int oldnbatch = hashtable->nbatch;
1033 int curbatch = hashtable->curbatch;
1034 int nbatch;
1035 long ninmemory;
1036 long nfreed;
1037 HashMemoryChunk oldchunks;
1038
1039 /* do nothing if we've decided to shut off growth */
1040 if (!hashtable->growEnabled)
1041 return;
1042
1043 /* safety check to avoid overflow */
1044 if (oldnbatch > Min(INT_MAX / 2, MaxAllocSize / (sizeof(void *) * 2)))
1045 return;
1046
1047 /* consider increasing size of the in-memory hash table instead */
1048 if (ExecHashIncreaseBatchSize(hashtable))
1049 return;
1050
1051 nbatch = oldnbatch * 2;
1052 Assert(nbatch > 1);
1053
1054 #ifdef HJDEBUG
1055 printf("Hashjoin %p: increasing nbatch to %d because space = %zu\n",
1056 hashtable, nbatch, hashtable->spaceUsed);
1057 #endif
1058
1059 if (hashtable->innerBatchFile == NULL)
1060 {
1061 MemoryContext oldcxt = MemoryContextSwitchTo(hashtable->spillCxt);
1062
1063 /* we had no file arrays before */
1064 hashtable->innerBatchFile = palloc0_array(BufFile *, nbatch);
1065 hashtable->outerBatchFile = palloc0_array(BufFile *, nbatch);
1066
1067 MemoryContextSwitchTo(oldcxt);
1068
1069 /* time to establish the temp tablespaces, too */
1070 PrepareTempTablespaces();
1071 }
1072 else
1073 {
1074 /* enlarge arrays and zero out added entries */
1075 hashtable->innerBatchFile = repalloc0_array(hashtable->innerBatchFile, BufFile *, oldnbatch, nbatch);
1076 hashtable->outerBatchFile = repalloc0_array(hashtable->outerBatchFile, BufFile *, oldnbatch, nbatch);
1077 }
1078
1079 hashtable->nbatch = nbatch;
1080
1081 /*
1082 * Scan through the existing hash table entries and dump out any that are
1083 * no longer of the current batch.
1084 */
1085 ninmemory = nfreed = 0;
1086
1087 /* If know we need to resize nbuckets, we can do it while rebatching. */
1088 if (hashtable->nbuckets_optimal != hashtable->nbuckets)
1089 {
1090 /* we never decrease the number of buckets */
1091 Assert(hashtable->nbuckets_optimal > hashtable->nbuckets);
1092
1093 hashtable->nbuckets = hashtable->nbuckets_optimal;
1094 hashtable->log2_nbuckets = hashtable->log2_nbuckets_optimal;
1095
1096 hashtable->buckets.unshared =
1097 repalloc_array(hashtable->buckets.unshared,
1098 HashJoinTuple, hashtable->nbuckets);
1099 }
1100
1101 /*
1102 * We will scan through the chunks directly, so that we can reset the
1103 * buckets now and not have to keep track which tuples in the buckets have
1104 * already been processed. We will free the old chunks as we go.
1105 */
1106 memset(hashtable->buckets.unshared, 0,
1107 sizeof(HashJoinTuple) * hashtable->nbuckets);
1108 oldchunks = hashtable->chunks;
1109 hashtable->chunks = NULL;
1110
1111 /* so, let's scan through the old chunks, and all tuples in each chunk */
1112 while (oldchunks != NULL)
1113 {
1114 HashMemoryChunk nextchunk = oldchunks->next.unshared;
1115
1116 /* position within the buffer (up to oldchunks->used) */
1117 size_t idx = 0;
1118
1119 /* process all tuples stored in this chunk (and then free it) */
1120 while (idx < oldchunks->used)
1121 {
1122 HashJoinTuple hashTuple = (HashJoinTuple) (HASH_CHUNK_DATA(oldchunks) + idx);
1123 MinimalTuple tuple = HJTUPLE_MINTUPLE(hashTuple);
1124 int hashTupleSize = (HJTUPLE_OVERHEAD + tuple->t_len);
1125 int bucketno;
1126 int batchno;
1127
1128 ninmemory++;
1129 ExecHashGetBucketAndBatch(hashtable, hashTuple->hashvalue,
1130 &bucketno, &batchno);
1131
1132 if (batchno == curbatch)
1133 {
1134 /* keep tuple in memory - copy it into the new chunk */
1135 HashJoinTuple copyTuple;
1136
1137 copyTuple = (HashJoinTuple) dense_alloc(hashtable, hashTupleSize);
1138 memcpy(copyTuple, hashTuple, hashTupleSize);
1139
1140 /* and add it back to the appropriate bucket */
1141 copyTuple->next.unshared = hashtable->buckets.unshared[bucketno];
1142 hashtable->buckets.unshared[bucketno] = copyTuple;
1143 }
1144 else
1145 {
1146 /* dump it out */
1147 Assert(batchno > curbatch);
1148 ExecHashJoinSaveTuple(HJTUPLE_MINTUPLE(hashTuple),
1149 hashTuple->hashvalue,
1150 &hashtable->innerBatchFile[batchno],
1151 hashtable);
1152
1153 hashtable->spaceUsed -= hashTupleSize;
1154 nfreed++;
1155 }
1156
1157 /* next tuple in this chunk */
1158 idx += MAXALIGN(hashTupleSize);
1159
1160 /* allow this loop to be cancellable */
1161 CHECK_FOR_INTERRUPTS();
1162 }
1163
1164 /* we're done with this chunk - free it and proceed to the next one */
1165 pfree(oldchunks);
1166 oldchunks = nextchunk;
1167 }
1168
1169 #ifdef HJDEBUG
1170 printf("Hashjoin %p: freed %ld of %ld tuples, space now %zu\n",
1171 hashtable, nfreed, ninmemory, hashtable->spaceUsed);
1172 #endif
1173
1174 /*
1175 * If we dumped out either all or none of the tuples in the table, disable
1176 * further expansion of nbatch. This situation implies that we have
1177 * enough tuples of identical hashvalues to overflow spaceAllowed.
1178 * Increasing nbatch will not fix it since there's no way to subdivide the
1179 * group any more finely. We have to just gut it out and hope the server
1180 * has enough RAM.
1181 */
1182 if (nfreed == 0 || nfreed == ninmemory)
1183 {
1184 hashtable->growEnabled = false;
1185 #ifdef HJDEBUG
1186 printf("Hashjoin %p: disabling further increase of nbatch\n",
1187 hashtable);
1188 #endif
1189 }
1190 }
1191
1192 /*
1193 * ExecParallelHashIncreaseNumBatches
1194 * Every participant attached to grow_batches_barrier must run this
1195 * function when it observes growth == PHJ_GROWTH_NEED_MORE_BATCHES.
1196 */
1197 static void
1198 ExecParallelHashIncreaseNumBatches(HashJoinTable hashtable)
1199 {
1200 ParallelHashJoinState *pstate = hashtable->parallel_state;
1201
1202 Assert(BarrierPhase(&pstate->build_barrier) == PHJ_BUILD_HASH_INNER);
1203
1204 /*
1205 * It's unlikely, but we need to be prepared for new participants to show
1206 * up while we're in the middle of this operation so we need to switch on
1207 * barrier phase here.
1208 */
1209 switch (PHJ_GROW_BATCHES_PHASE(BarrierPhase(&pstate->grow_batches_barrier)))
1210 {
1211 case PHJ_GROW_BATCHES_ELECT:
1212
1213 /*
1214 * Elect one participant to prepare to grow the number of batches.
1215 * This involves reallocating or resetting the buckets of batch 0
1216 * in preparation for all participants to begin repartitioning the
1217 * tuples.
1218 */
1219 if (BarrierArriveAndWait(&pstate->grow_batches_barrier,
1220 WAIT_EVENT_HASH_GROW_BATCHES_ELECT))
1221 {
1222 dsa_pointer_atomic *buckets;
1223 ParallelHashJoinBatch *old_batch0;
1224 int new_nbatch;
1225 int i;
1226
1227 /* Move the old batch out of the way. */
1228 old_batch0 = hashtable->batches[0].shared;
1229 pstate->old_batches = pstate->batches;
1230 pstate->old_nbatch = hashtable->nbatch;
1231 pstate->batches = InvalidDsaPointer;
1232
1233 /* Free this backend's old accessors. */
1234 ExecParallelHashCloseBatchAccessors(hashtable);
1235
1236 /* Figure out how many batches to use. */
1237 if (hashtable->nbatch == 1)
1238 {
1239 /*
1240 * We are going from single-batch to multi-batch. We need
1241 * to switch from one large combined memory budget to the
1242 * regular hash_mem budget.
1243 */
1244 pstate->space_allowed = get_hash_memory_limit();
1245
1246 /*
1247 * The combined hash_mem of all participants wasn't
1248 * enough. Therefore one batch per participant would be
1249 * approximately equivalent and would probably also be
1250 * insufficient. So try two batches per participant,
1251 * rounded up to a power of two.
1252 */
1253 new_nbatch = pg_nextpower2_32(pstate->nparticipants * 2);
1254 }
1255 else
1256 {
1257 /*
1258 * We were already multi-batched. Try doubling the number
1259 * of batches.
1260 */
1261 new_nbatch = hashtable->nbatch * 2;
1262 }
1263
1264 /* Allocate new larger generation of batches. */
1265 Assert(hashtable->nbatch == pstate->nbatch);
1266 ExecParallelHashJoinSetUpBatches(hashtable, new_nbatch);
1267 Assert(hashtable->nbatch == pstate->nbatch);
1268
1269 /* Replace or recycle batch 0's bucket array. */
1270 if (pstate->old_nbatch == 1)
1271 {
1272 double dtuples;
1273 double dbuckets;
1274 int new_nbuckets;
1275 uint32 max_buckets;
1276
1277 /*
1278 * We probably also need a smaller bucket array. How many
1279 * tuples do we expect per batch, assuming we have only
1280 * half of them so far? Normally we don't need to change
1281 * the bucket array's size, because the size of each batch
1282 * stays the same as we add more batches, but in this
1283 * special case we move from a large batch to many smaller
1284 * batches and it would be wasteful to keep the large
1285 * array.
1286 */
1287 dtuples = (old_batch0->ntuples * 2.0) / new_nbatch;
1288
1289 /*
1290 * We need to calculate the maximum number of buckets to
1291 * stay within the MaxAllocSize boundary. Round the
1292 * maximum number to the previous power of 2 given that
1293 * later we round the number to the next power of 2.
1294 */
1295 max_buckets = pg_prevpower2_32((uint32)
1296 (MaxAllocSize / sizeof(dsa_pointer_atomic)));
1297 dbuckets = ceil(dtuples / NTUP_PER_BUCKET);
1298 dbuckets = Min(dbuckets, max_buckets);
1299 new_nbuckets = (int) dbuckets;
1300 new_nbuckets = Max(new_nbuckets, 1024);
1301 new_nbuckets = pg_nextpower2_32(new_nbuckets);
1302 dsa_free(hashtable->area, old_batch0->buckets);
1303 hashtable->batches[0].shared->buckets =
1304 dsa_allocate(hashtable->area,
1305 sizeof(dsa_pointer_atomic) * new_nbuckets);
1306 buckets = (dsa_pointer_atomic *)
1307 dsa_get_address(hashtable->area,
1308 hashtable->batches[0].shared->buckets);
1309 for (i = 0; i < new_nbuckets; ++i)
1310 dsa_pointer_atomic_init(&buckets[i], InvalidDsaPointer);
1311 pstate->nbuckets = new_nbuckets;
1312 }
1313 else
1314 {
1315 /* Recycle the existing bucket array. */
1316 hashtable->batches[0].shared->buckets = old_batch0->buckets;
1317 buckets = (dsa_pointer_atomic *)
1318 dsa_get_address(hashtable->area, old_batch0->buckets);
1319 for (i = 0; i < hashtable->nbuckets; ++i)
1320 dsa_pointer_atomic_write(&buckets[i], InvalidDsaPointer);
1321 }
1322
1323 /* Move all chunks to the work queue for parallel processing. */
1324 pstate->chunk_work_queue = old_batch0->chunks;
1325
1326 /* Disable further growth temporarily while we're growing. */
1327 pstate->growth = PHJ_GROWTH_DISABLED;
1328 }
1329 else
1330 {
1331 /* All other participants just flush their tuples to disk. */
1332 ExecParallelHashCloseBatchAccessors(hashtable);
1333 }
1334 /* Fall through. */
1335
1336 case PHJ_GROW_BATCHES_REALLOCATE:
1337 /* Wait for the above to be finished. */
1338 BarrierArriveAndWait(&pstate->grow_batches_barrier,
1339 WAIT_EVENT_HASH_GROW_BATCHES_REALLOCATE);
1340 /* Fall through. */
1341
1342 case PHJ_GROW_BATCHES_REPARTITION:
1343 /* Make sure that we have the current dimensions and buckets. */
1344 ExecParallelHashEnsureBatchAccessors(hashtable);
1345 ExecParallelHashTableSetCurrentBatch(hashtable, 0);
1346 /* Then partition, flush counters. */
1347 ExecParallelHashRepartitionFirst(hashtable);
1348 ExecParallelHashRepartitionRest(hashtable);
1349 ExecParallelHashMergeCounters(hashtable);
1350 /* Wait for the above to be finished. */
1351 BarrierArriveAndWait(&pstate->grow_batches_barrier,
1352 WAIT_EVENT_HASH_GROW_BATCHES_REPARTITION);
1353 /* Fall through. */
1354
1355 case PHJ_GROW_BATCHES_DECIDE:
1356
1357 /*
1358 * Elect one participant to clean up and decide whether further
1359 * repartitioning is needed, or should be disabled because it's
1360 * not helping.
1361 */
1362 if (BarrierArriveAndWait(&pstate->grow_batches_barrier,
1363 WAIT_EVENT_HASH_GROW_BATCHES_DECIDE))
1364 {
1365 ParallelHashJoinBatch *old_batches;
1366 bool space_exhausted = false;
1367 bool extreme_skew_detected = false;
1368
1369 /* Make sure that we have the current dimensions and buckets. */
1370 ExecParallelHashEnsureBatchAccessors(hashtable);
1371 ExecParallelHashTableSetCurrentBatch(hashtable, 0);
1372
1373 old_batches = dsa_get_address(hashtable->area, pstate->old_batches);
1374
1375 /* Are any of the new generation of batches exhausted? */
1376 for (int i = 0; i < hashtable->nbatch; ++i)
1377 {
1378 ParallelHashJoinBatch *batch;
1379 ParallelHashJoinBatch *old_batch;
1380 int parent;
1381
1382 batch = hashtable->batches[i].shared;
1383 if (batch->space_exhausted ||
1384 batch->estimated_size > pstate->space_allowed)
1385 space_exhausted = true;
1386
1387 parent = i % pstate->old_nbatch;
1388 old_batch = NthParallelHashJoinBatch(old_batches, parent);
1389 if (old_batch->space_exhausted ||
1390 batch->estimated_size > pstate->space_allowed)
1391 {
1392 /*
1393 * Did this batch receive ALL of the tuples from its
1394 * parent batch? That would indicate that further
1395 * repartitioning isn't going to help (the hash values
1396 * are probably all the same).
1397 */
1398 if (batch->ntuples == hashtable->batches[parent].shared->old_ntuples)
1399 extreme_skew_detected = true;
1400 }
1401 }
1402
1403 /* Don't keep growing if it's not helping or we'd overflow. */
1404 if (extreme_skew_detected || hashtable->nbatch >= INT_MAX / 2)
1405 pstate->growth = PHJ_GROWTH_DISABLED;
1406 else if (space_exhausted)
1407 pstate->growth = PHJ_GROWTH_NEED_MORE_BATCHES;
1408 else
1409 pstate->growth = PHJ_GROWTH_OK;
1410
1411 /* Free the old batches in shared memory. */
1412 dsa_free(hashtable->area, pstate->old_batches);
1413 pstate->old_batches = InvalidDsaPointer;
1414 }
1415 /* Fall through. */
1416
1417 case PHJ_GROW_BATCHES_FINISH:
1418 /* Wait for the above to complete. */
1419 BarrierArriveAndWait(&pstate->grow_batches_barrier,
1420 WAIT_EVENT_HASH_GROW_BATCHES_FINISH);
1421 }
1422 }
1423
1424 /*
1425 * Repartition the tuples currently loaded into memory for inner batch 0
1426 * because the number of batches has been increased. Some tuples are retained
1427 * in memory and some are written out to a later batch.
1428 */
1429 static void
1430 ExecParallelHashRepartitionFirst(HashJoinTable hashtable)
1431 {
1432 dsa_pointer chunk_shared;
1433 HashMemoryChunk chunk;
1434
1435 Assert(hashtable->nbatch == hashtable->parallel_state->nbatch);
1436
1437 while ((chunk = ExecParallelHashPopChunkQueue(hashtable, &chunk_shared)))
1438 {
1439 size_t idx = 0;
1440
1441 /* Repartition all tuples in this chunk. */
1442 while (idx < chunk->used)
1443 {
1444 HashJoinTuple hashTuple = (HashJoinTuple) (HASH_CHUNK_DATA(chunk) + idx);
1445 MinimalTuple tuple = HJTUPLE_MINTUPLE(hashTuple);
1446 HashJoinTuple copyTuple;
1447 dsa_pointer shared;
1448 int bucketno;
1449 int batchno;
1450
1451 ExecHashGetBucketAndBatch(hashtable, hashTuple->hashvalue,
1452 &bucketno, &batchno);
1453
1454 Assert(batchno < hashtable->nbatch);
1455 if (batchno == 0)
1456 {
1457 /* It still belongs in batch 0. Copy to a new chunk. */
1458 copyTuple =
1459 ExecParallelHashTupleAlloc(hashtable,
1460 HJTUPLE_OVERHEAD + tuple->t_len,
1461 &shared);
1462 copyTuple->hashvalue = hashTuple->hashvalue;
1463 memcpy(HJTUPLE_MINTUPLE(copyTuple), tuple, tuple->t_len);
1464 ExecParallelHashPushTuple(&hashtable->buckets.shared[bucketno],
1465 copyTuple, shared);
1466 }
1467 else
1468 {
1469 size_t tuple_size =
1470 MAXALIGN(HJTUPLE_OVERHEAD + tuple->t_len);
1471
1472 /* It belongs in a later batch. */
1473 hashtable->batches[batchno].estimated_size += tuple_size;
1474 sts_puttuple(hashtable->batches[batchno].inner_tuples,
1475 &hashTuple->hashvalue, tuple);
1476 }
1477
1478 /* Count this tuple. */
1479 ++hashtable->batches[0].old_ntuples;
1480 ++hashtable->batches[batchno].ntuples;
1481
1482 idx += MAXALIGN(HJTUPLE_OVERHEAD +
1483 HJTUPLE_MINTUPLE(hashTuple)->t_len);
1484 }
1485
1486 /* Free this chunk. */
1487 dsa_free(hashtable->area, chunk_shared);
1488
1489 CHECK_FOR_INTERRUPTS();
1490 }
1491 }
1492
1493 /*
1494 * Help repartition inner batches 1..n.
1495 */
1496 static void
1497 ExecParallelHashRepartitionRest(HashJoinTable hashtable)
1498 {
1499 ParallelHashJoinState *pstate = hashtable->parallel_state;
1500 int old_nbatch = pstate->old_nbatch;
1501 SharedTuplestoreAccessor **old_inner_tuples;
1502 ParallelHashJoinBatch *old_batches;
1503 int i;
1504
1505 /* Get our hands on the previous generation of batches. */
1506 old_batches = (ParallelHashJoinBatch *)
1507 dsa_get_address(hashtable->area, pstate->old_batches);
1508 old_inner_tuples = palloc0_array(SharedTuplestoreAccessor *, old_nbatch);
1509 for (i = 1; i < old_nbatch; ++i)
1510 {
1511 ParallelHashJoinBatch *shared =
1512 NthParallelHashJoinBatch(old_batches, i);
1513
1514 old_inner_tuples[i] = sts_attach(ParallelHashJoinBatchInner(shared),
1515 ParallelWorkerNumber + 1,
1516 &pstate->fileset);
1517 }
1518
1519 /* Join in the effort to repartition them. */
1520 for (i = 1; i < old_nbatch; ++i)
1521 {
1522 MinimalTuple tuple;
1523 uint32 hashvalue;
1524
1525 /* Scan one partition from the previous generation. */
1526 sts_begin_parallel_scan(old_inner_tuples[i]);
1527 while ((tuple = sts_parallel_scan_next(old_inner_tuples[i], &hashvalue)))
1528 {
1529 size_t tuple_size = MAXALIGN(HJTUPLE_OVERHEAD + tuple->t_len);
1530 int bucketno;
1531 int batchno;
1532
1533 /* Decide which partition it goes to in the new generation. */
1534 ExecHashGetBucketAndBatch(hashtable, hashvalue, &bucketno,
1535 &batchno);
1536
1537 hashtable->batches[batchno].estimated_size += tuple_size;
1538 ++hashtable->batches[batchno].ntuples;
1539 ++hashtable->batches[i].old_ntuples;
1540
1541 /* Store the tuple its new batch. */
1542 sts_puttuple(hashtable->batches[batchno].inner_tuples,
1543 &hashvalue, tuple);
1544
1545 CHECK_FOR_INTERRUPTS();
1546 }
1547 sts_end_parallel_scan(old_inner_tuples[i]);
1548 }
1549
1550 pfree(old_inner_tuples);
1551 }
1552
1553 /*
1554 * Transfer the backend-local per-batch counters to the shared totals.
1555 */
1556 static void
1557 ExecParallelHashMergeCounters(HashJoinTable hashtable)
1558 {
1559 ParallelHashJoinState *pstate = hashtable->parallel_state;
1560 int i;
1561
1562 LWLockAcquire(&pstate->lock, LW_EXCLUSIVE);
1563 pstate->total_tuples = 0;
1564 for (i = 0; i < hashtable->nbatch; ++i)
1565 {
1566 ParallelHashJoinBatchAccessor *batch = &hashtable->batches[i];
1567
1568 batch->shared->size += batch->size;
1569 batch->shared->estimated_size += batch->estimated_size;
1570 batch->shared->ntuples += batch->ntuples;
1571 batch->shared->old_ntuples += batch->old_ntuples;
1572 batch->size = 0;
1573 batch->estimated_size = 0;
1574 batch->ntuples = 0;
1575 batch->old_ntuples = 0;
1576 pstate->total_tuples += batch->shared->ntuples;
1577 }
1578 LWLockRelease(&pstate->lock);
1579 }
1580
1581 /*
1582 * ExecHashIncreaseNumBuckets
1583 * increase the original number of buckets in order to reduce
1584 * number of tuples per bucket
1585 */
1586 static void
1587 ExecHashIncreaseNumBuckets(HashJoinTable hashtable)
1588 {
1589 HashMemoryChunk chunk;
1590
1591 /* do nothing if not an increase (it's called increase for a reason) */
1592 if (hashtable->nbuckets >= hashtable->nbuckets_optimal)
1593 return;
1594
1595 #ifdef HJDEBUG
1596 printf("Hashjoin %p: increasing nbuckets %d => %d\n",
1597 hashtable, hashtable->nbuckets, hashtable->nbuckets_optimal);
1598 #endif
1599
1600 hashtable->nbuckets = hashtable->nbuckets_optimal;
1601 hashtable->log2_nbuckets = hashtable->log2_nbuckets_optimal;
1602
1603 Assert(hashtable->nbuckets > 1);
1604 Assert(hashtable->nbuckets <= (INT_MAX / 2));
1605 Assert(hashtable->nbuckets == (1 << hashtable->log2_nbuckets));
1606
1607 /*
1608 * Just reallocate the proper number of buckets - we don't need to walk
1609 * through them - we can walk the dense-allocated chunks (just like in
1610 * ExecHashIncreaseNumBatches, but without all the copying into new
1611 * chunks)
1612 */
1613 hashtable->buckets.unshared =
1614 repalloc_array(hashtable->buckets.unshared,
1615 HashJoinTuple, hashtable->nbuckets);
1616
1617 memset(hashtable->buckets.unshared, 0,
1618 hashtable->nbuckets * sizeof(HashJoinTuple));
1619
1620 /* scan through all tuples in all chunks to rebuild the hash table */
1621 for (chunk = hashtable->chunks; chunk != NULL; chunk = chunk->next.unshared)
1622 {
1623 /* process all tuples stored in this chunk */
1624 size_t idx = 0;
1625
1626 while (idx < chunk->used)
1627 {
1628 HashJoinTuple hashTuple = (HashJoinTuple) (HASH_CHUNK_DATA(chunk) + idx);
1629 int bucketno;
1630 int batchno;
1631
1632 ExecHashGetBucketAndBatch(hashtable, hashTuple->hashvalue,
1633 &bucketno, &batchno);
1634
1635 /* add the tuple to the proper bucket */
1636 hashTuple->next.unshared = hashtable->buckets.unshared[bucketno];
1637 hashtable->buckets.unshared[bucketno] = hashTuple;
1638
1639 /* advance index past the tuple */
1640 idx += MAXALIGN(HJTUPLE_OVERHEAD +
1641 HJTUPLE_MINTUPLE(hashTuple)->t_len);
1642 }
1643
1644 /* allow this loop to be cancellable */
1645 CHECK_FOR_INTERRUPTS();
1646 }
1647 }
1648
1649 static void
1650 ExecParallelHashIncreaseNumBuckets(HashJoinTable hashtable)
1651 {
1652 ParallelHashJoinState *pstate = hashtable->parallel_state;
1653 int i;
1654 HashMemoryChunk chunk;
1655 dsa_pointer chunk_s;
1656
1657 Assert(BarrierPhase(&pstate->build_barrier) == PHJ_BUILD_HASH_INNER);
1658
1659 /*
1660 * It's unlikely, but we need to be prepared for new participants to show
1661 * up while we're in the middle of this operation so we need to switch on
1662 * barrier phase here.
1663 */
1664 switch (PHJ_GROW_BUCKETS_PHASE(BarrierPhase(&pstate->grow_buckets_barrier)))
1665 {
1666 case PHJ_GROW_BUCKETS_ELECT:
1667 /* Elect one participant to prepare to increase nbuckets. */
1668 if (BarrierArriveAndWait(&pstate->grow_buckets_barrier,
1669 WAIT_EVENT_HASH_GROW_BUCKETS_ELECT))
1670 {
1671 size_t size;
1672 dsa_pointer_atomic *buckets;
1673
1674 /* Double the size of the bucket array. */
1675 pstate->nbuckets *= 2;
1676 size = pstate->nbuckets * sizeof(dsa_pointer_atomic);
1677 hashtable->batches[0].shared->size += size / 2;
1678 dsa_free(hashtable->area, hashtable->batches[0].shared->buckets);
1679 hashtable->batches[0].shared->buckets =
1680 dsa_allocate(hashtable->area, size);
1681 buckets = (dsa_pointer_atomic *)
1682 dsa_get_address(hashtable->area,
1683 hashtable->batches[0].shared->buckets);
1684 for (i = 0; i < pstate->nbuckets; ++i)
1685 dsa_pointer_atomic_init(&buckets[i], InvalidDsaPointer);
1686
1687 /* Put the chunk list onto the work queue. */
1688 pstate->chunk_work_queue = hashtable->batches[0].shared->chunks;
1689
1690 /* Clear the flag. */
1691 pstate->growth = PHJ_GROWTH_OK;
1692 }
1693 /* Fall through. */
1694
1695 case PHJ_GROW_BUCKETS_REALLOCATE:
1696 /* Wait for the above to complete. */
1697 BarrierArriveAndWait(&pstate->grow_buckets_barrier,
1698 WAIT_EVENT_HASH_GROW_BUCKETS_REALLOCATE);
1699 /* Fall through. */
1700
1701 case PHJ_GROW_BUCKETS_REINSERT:
1702 /* Reinsert all tuples into the hash table. */
1703 ExecParallelHashEnsureBatchAccessors(hashtable);
1704 ExecParallelHashTableSetCurrentBatch(hashtable, 0);
1705 while ((chunk = ExecParallelHashPopChunkQueue(hashtable, &chunk_s)))
1706 {
1707 size_t idx = 0;
1708
1709 while (idx < chunk->used)
1710 {
1711 HashJoinTuple hashTuple = (HashJoinTuple) (HASH_CHUNK_DATA(chunk) + idx);
1712 dsa_pointer shared = chunk_s + HASH_CHUNK_HEADER_SIZE + idx;
1713 int bucketno;
1714 int batchno;
1715
1716 ExecHashGetBucketAndBatch(hashtable, hashTuple->hashvalue,
1717 &bucketno, &batchno);
1718 Assert(batchno == 0);
1719
1720 /* add the tuple to the proper bucket */
1721 ExecParallelHashPushTuple(&hashtable->buckets.shared[bucketno],
1722 hashTuple, shared);
1723
1724 /* advance index past the tuple */
1725 idx += MAXALIGN(HJTUPLE_OVERHEAD +
1726 HJTUPLE_MINTUPLE(hashTuple)->t_len);
1727 }
1728
1729 /* allow this loop to be cancellable */
1730 CHECK_FOR_INTERRUPTS();
1731 }
1732 BarrierArriveAndWait(&pstate->grow_buckets_barrier,
1733 WAIT_EVENT_HASH_GROW_BUCKETS_REINSERT);
1734 }
1735 }
1736
1737 /*
1738 * ExecHashTableInsert
1739 * insert a tuple into the hash table depending on the hash value
1740 * it may just go to a temp file for later batches
1741 *
1742 * Note: the passed TupleTableSlot may contain a regular, minimal, or virtual
1743 * tuple; the minimal case in particular is certain to happen while reloading
1744 * tuples from batch files. We could save some cycles in the regular-tuple
1745 * case by not forcing the slot contents into minimal form; not clear if it's
1746 * worth the messiness required.
1747 */
1748 void
1749 ExecHashTableInsert(HashJoinTable hashtable,
1750 TupleTableSlot *slot,
1751 uint32 hashvalue)
1752 {
1753 bool shouldFree;
1754 MinimalTuple tuple = ExecFetchSlotMinimalTuple(slot, &shouldFree);
1755 int bucketno;
1756 int batchno;
1757
1758 ExecHashGetBucketAndBatch(hashtable, hashvalue,
1759 &bucketno, &batchno);
1760
1761 /*
1762 * decide whether to put the tuple in the hash table or a temp file
1763 */
1764 if (batchno == hashtable->curbatch)
1765 {
1766 /*
1767 * put the tuple in hash table
1768 */
1769 HashJoinTuple hashTuple;
1770 int hashTupleSize;
1771 double ntuples = (hashtable->totalTuples - hashtable->skewTuples);
1772
1773 /* Create the HashJoinTuple */
1774 hashTupleSize = HJTUPLE_OVERHEAD + tuple->t_len;
1775 hashTuple = (HashJoinTuple) dense_alloc(hashtable, hashTupleSize);
1776
1777 hashTuple->hashvalue = hashvalue;
1778 memcpy(HJTUPLE_MINTUPLE(hashTuple), tuple, tuple->t_len);
1779
1780 /*
1781 * We always reset the tuple-matched flag on insertion. This is okay
1782 * even when reloading a tuple from a batch file, since the tuple
1783 * could not possibly have been matched to an outer tuple before it
1784 * went into the batch file.
1785 */
1786 HeapTupleHeaderClearMatch(HJTUPLE_MINTUPLE(hashTuple));
1787
1788 /* Push it onto the front of the bucket's list */
1789 hashTuple->next.unshared = hashtable->buckets.unshared[bucketno];
1790 hashtable->buckets.unshared[bucketno] = hashTuple;
1791
1792 /*
1793 * Increase the (optimal) number of buckets if we just exceeded the
1794 * NTUP_PER_BUCKET threshold, but only when there's still a single
1795 * batch.
1796 */
1797 if (hashtable->nbatch == 1 &&
1798 ntuples > (hashtable->nbuckets_optimal * NTUP_PER_BUCKET))
1799 {
1800 /* Guard against integer overflow and alloc size overflow */
1801 if (hashtable->nbuckets_optimal <= INT_MAX / 2 &&
1802 hashtable->nbuckets_optimal * 2 <= MaxAllocSize / sizeof(HashJoinTuple))
1803 {
1804 hashtable->nbuckets_optimal *= 2;
1805 hashtable->log2_nbuckets_optimal += 1;
1806 }
1807 }
1808
1809 /* Account for space used, and back off if we've used too much */
1810 hashtable->spaceUsed += hashTupleSize;
1811 if (hashtable->spaceUsed > hashtable->spacePeak)
1812 hashtable->spacePeak = hashtable->spaceUsed;
1813 if (hashtable->spaceUsed +
1814 hashtable->nbuckets_optimal * sizeof(HashJoinTuple)
1815 > hashtable->spaceAllowed)
1816 ExecHashIncreaseNumBatches(hashtable);
1817 }
1818 else
1819 {
1820 /*
1821 * put the tuple into a temp file for later batches
1822 */
1823 Assert(batchno > hashtable->curbatch);
1824 ExecHashJoinSaveTuple(tuple,
1825 hashvalue,
1826 &hashtable->innerBatchFile[batchno],
1827 hashtable);
1828 }
1829
1830 if (shouldFree)
1831 heap_free_minimal_tuple(tuple);
1832 }
1833
1834 /*
1835 * ExecParallelHashTableInsert
1836 * insert a tuple into a shared hash table or shared batch tuplestore
1837 */
1838 void
1839 ExecParallelHashTableInsert(HashJoinTable hashtable,
1840 TupleTableSlot *slot,
1841 uint32 hashvalue)
1842 {
1843 bool shouldFree;
1844 MinimalTuple tuple = ExecFetchSlotMinimalTuple(slot, &shouldFree);
1845 dsa_pointer shared;
1846 int bucketno;
1847 int batchno;
1848
1849 retry:
1850 ExecHashGetBucketAndBatch(hashtable, hashvalue, &bucketno, &batchno);
1851
1852 if (batchno == 0)
1853 {
1854 HashJoinTuple hashTuple;
1855
1856 /* Try to load it into memory. */
1857 Assert(BarrierPhase(&hashtable->parallel_state->build_barrier) ==
1858 PHJ_BUILD_HASH_INNER);
1859 hashTuple = ExecParallelHashTupleAlloc(hashtable,
1860 HJTUPLE_OVERHEAD + tuple->t_len,
1861 &shared);
1862 if (hashTuple == NULL)
1863 goto retry;
1864
1865 /* Store the hash value in the HashJoinTuple header. */
1866 hashTuple->hashvalue = hashvalue;
1867 memcpy(HJTUPLE_MINTUPLE(hashTuple), tuple, tuple->t_len);
1868 HeapTupleHeaderClearMatch(HJTUPLE_MINTUPLE(hashTuple));
1869
1870 /* Push it onto the front of the bucket's list */
1871 ExecParallelHashPushTuple(&hashtable->buckets.shared[bucketno],
1872 hashTuple, shared);
1873 }
1874 else
1875 {
1876 size_t tuple_size = MAXALIGN(HJTUPLE_OVERHEAD + tuple->t_len);
1877
1878 Assert(batchno > 0);
1879
1880 /* Try to preallocate space in the batch if necessary. */
1881 if (hashtable->batches[batchno].preallocated < tuple_size)
1882 {
1883 if (!ExecParallelHashTuplePrealloc(hashtable, batchno, tuple_size))
1884 goto retry;
1885 }
1886
1887 Assert(hashtable->batches[batchno].preallocated >= tuple_size);
1888 hashtable->batches[batchno].preallocated -= tuple_size;
1889 sts_puttuple(hashtable->batches[batchno].inner_tuples, &hashvalue,
1890 tuple);
1891 }
1892 ++hashtable->batches[batchno].ntuples;
1893
1894 if (shouldFree)
1895 heap_free_minimal_tuple(tuple);
1896 }
1897
1898 /*
1899 * Insert a tuple into the current hash table. Unlike
1900 * ExecParallelHashTableInsert, this version is not prepared to send the tuple
1901 * to other batches or to run out of memory, and should only be called with
1902 * tuples that belong in the current batch once growth has been disabled.
1903 */
1904 void
1905 ExecParallelHashTableInsertCurrentBatch(HashJoinTable hashtable,
1906 TupleTableSlot *slot,
1907 uint32 hashvalue)
1908 {
1909 bool shouldFree;
1910 MinimalTuple tuple = ExecFetchSlotMinimalTuple(slot, &shouldFree);
1911 HashJoinTuple hashTuple;
1912 dsa_pointer shared;
1913 int batchno;
1914 int bucketno;
1915
1916 ExecHashGetBucketAndBatch(hashtable, hashvalue, &bucketno, &batchno);
1917 Assert(batchno == hashtable->curbatch);
1918 hashTuple = ExecParallelHashTupleAlloc(hashtable,
1919 HJTUPLE_OVERHEAD + tuple->t_len,
1920 &shared);
1921 hashTuple->hashvalue = hashvalue;
1922 memcpy(HJTUPLE_MINTUPLE(hashTuple), tuple, tuple->t_len);
1923 HeapTupleHeaderClearMatch(HJTUPLE_MINTUPLE(hashTuple));
1924 ExecParallelHashPushTuple(&hashtable->buckets.shared[bucketno],
1925 hashTuple, shared);
1926
1927 if (shouldFree)
1928 heap_free_minimal_tuple(tuple);
1929 }
1930
1931
1932 /*
1933 * ExecHashGetBucketAndBatch
1934 * Determine the bucket number and batch number for a hash value
1935 *
1936 * Note: on-the-fly increases of nbatch must not change the bucket number
1937 * for a given hash code (since we don't move tuples to different hash
1938 * chains), and must only cause the batch number to remain the same or
1939 * increase. Our algorithm is
1940 * bucketno = hashvalue MOD nbuckets
1941 * batchno = ROR(hashvalue, log2_nbuckets) MOD nbatch
1942 * where nbuckets and nbatch are both expected to be powers of 2, so we can
1943 * do the computations by shifting and masking. (This assumes that all hash
1944 * functions are good about randomizing all their output bits, else we are
1945 * likely to have very skewed bucket or batch occupancy.)
1946 *
1947 * nbuckets and log2_nbuckets may change while nbatch == 1 because of dynamic
1948 * bucket count growth. Once we start batching, the value is fixed and does
1949 * not change over the course of the join (making it possible to compute batch
1950 * number the way we do here).
1951 *
1952 * nbatch is always a power of 2; we increase it only by doubling it. This
1953 * effectively adds one more bit to the top of the batchno. In very large
1954 * joins, we might run out of bits to add, so we do this by rotating the hash
1955 * value. This causes batchno to steal bits from bucketno when the number of
1956 * virtual buckets exceeds 2^32. It's better to have longer bucket chains
1957 * than to lose the ability to divide batches.
1958 */
1959 void
1960 ExecHashGetBucketAndBatch(HashJoinTable hashtable,
1961 uint32 hashvalue,
1962 int *bucketno,
1963 int *batchno)
1964 {
1965 uint32 nbuckets = (uint32) hashtable->nbuckets;
1966 uint32 nbatch = (uint32) hashtable->nbatch;
1967
1968 if (nbatch > 1)
1969 {
1970 *bucketno = hashvalue & (nbuckets - 1);
1971 *batchno = pg_rotate_right32(hashvalue,
1972 hashtable->log2_nbuckets) & (nbatch - 1);
1973 }
1974 else
1975 {
1976 *bucketno = hashvalue & (nbuckets - 1);
1977 *batchno = 0;
1978 }
1979 }
1980
1981 /*
1982 * ExecScanHashBucket
1983 * scan a hash bucket for matches to the current outer tuple
1984 *
1985 * The current outer tuple must be stored in econtext->ecxt_outertuple.
1986 *
1987 * On success, the inner tuple is stored into hjstate->hj_CurTuple and
1988 * econtext->ecxt_innertuple, using hjstate->hj_HashTupleSlot as the slot
1989 * for the latter.
1990 */
1991 bool
1992 ExecScanHashBucket(HashJoinState *hjstate,
1993 ExprContext *econtext)
1994 {
1995 ExprState *hjclauses = hjstate->hashclauses;
1996 HashJoinTable hashtable = hjstate->hj_HashTable;
1997 HashJoinTuple hashTuple = hjstate->hj_CurTuple;
1998 uint32 hashvalue = hjstate->hj_CurHashValue;
1999
2000 /*
2001 * hj_CurTuple is the address of the tuple last returned from the current
2002 * bucket, or NULL if it's time to start scanning a new bucket.
2003 *
2004 * If the tuple hashed to a skew bucket then scan the skew bucket
2005 * otherwise scan the standard hashtable bucket.
2006 */
2007 if (hashTuple != NULL)
2008 hashTuple = hashTuple->next.unshared;
2009 else if (hjstate->hj_CurSkewBucketNo != INVALID_SKEW_BUCKET_NO)
2010 hashTuple = hashtable->skewBucket[hjstate->hj_CurSkewBucketNo]->tuples;
2011 else
2012 hashTuple = hashtable->buckets.unshared[hjstate->hj_CurBucketNo];
2013
2014 while (hashTuple != NULL)
2015 {
2016 if (hashTuple->hashvalue == hashvalue)
2017 {
2018 TupleTableSlot *inntuple;
2019
2020 /* insert hashtable's tuple into exec slot so ExecQual sees it */
2021 inntuple = ExecStoreMinimalTuple(HJTUPLE_MINTUPLE(hashTuple),
2022 hjstate->hj_HashTupleSlot,
2023 false); /* do not pfree */
2024 econtext->ecxt_innertuple = inntuple;
2025
2026 if (ExecQualAndReset(hjclauses, econtext))
2027 {
2028 hjstate->hj_CurTuple = hashTuple;
2029 return true;
2030 }
2031 }
2032
2033 hashTuple = hashTuple->next.unshared;
2034 }
2035
2036 /*
2037 * no match
2038 */
2039 return false;
2040 }
2041
2042 /*
2043 * ExecParallelScanHashBucket
2044 * scan a hash bucket for matches to the current outer tuple
2045 *
2046 * The current outer tuple must be stored in econtext->ecxt_outertuple.
2047 *
2048 * On success, the inner tuple is stored into hjstate->hj_CurTuple and
2049 * econtext->ecxt_innertuple, using hjstate->hj_HashTupleSlot as the slot
2050 * for the latter.
2051 */
2052 bool
2053 ExecParallelScanHashBucket(HashJoinState *hjstate,
2054 ExprContext *econtext)
2055 {
2056 ExprState *hjclauses = hjstate->hashclauses;
2057 HashJoinTable hashtable = hjstate->hj_HashTable;
2058 HashJoinTuple hashTuple = hjstate->hj_CurTuple;
2059 uint32 hashvalue = hjstate->hj_CurHashValue;
2060
2061 /*
2062 * hj_CurTuple is the address of the tuple last returned from the current
2063 * bucket, or NULL if it's time to start scanning a new bucket.
2064 */
2065 if (hashTuple != NULL)
2066 hashTuple = ExecParallelHashNextTuple(hashtable, hashTuple);
2067 else
2068 hashTuple = ExecParallelHashFirstTuple(hashtable,
2069 hjstate->hj_CurBucketNo);
2070
2071 while (hashTuple != NULL)
2072 {
2073 if (hashTuple->hashvalue == hashvalue)
2074 {
2075 TupleTableSlot *inntuple;
2076
2077 /* insert hashtable's tuple into exec slot so ExecQual sees it */
2078 inntuple = ExecStoreMinimalTuple(HJTUPLE_MINTUPLE(hashTuple),
2079 hjstate->hj_HashTupleSlot,
2080 false); /* do not pfree */
2081 econtext->ecxt_innertuple = inntuple;
2082
2083 if (ExecQualAndReset(hjclauses, econtext))
2084 {
2085 hjstate->hj_CurTuple = hashTuple;
2086 return true;
2087 }
2088 }
2089
2090 hashTuple = ExecParallelHashNextTuple(hashtable, hashTuple);
2091 }
2092
2093 /*
2094 * no match
2095 */
2096 return false;
2097 }
2098
2099 /*
2100 * ExecPrepHashTableForUnmatched
2101 * set up for a series of ExecScanHashTableForUnmatched calls
2102 */
2103 void
2104 ExecPrepHashTableForUnmatched(HashJoinState *hjstate)
2105 {
2106 /*----------
2107 * During this scan we use the HashJoinState fields as follows:
2108 *
2109 * hj_CurBucketNo: next regular bucket to scan
2110 * hj_CurSkewBucketNo: next skew bucket (an index into skewBucketNums)
2111 * hj_CurTuple: last tuple returned, or NULL to start next bucket
2112 *----------
2113 */
2114 hjstate->hj_CurBucketNo = 0;
2115 hjstate->hj_CurSkewBucketNo = 0;
2116 hjstate->hj_CurTuple = NULL;
2117 }
2118
2119 /*
2120 * Decide if this process is allowed to run the unmatched scan. If so, the
2121 * batch barrier is advanced to PHJ_BATCH_SCAN and true is returned.
2122 * Otherwise the batch is detached and false is returned.
2123 */
2124 bool
2125 ExecParallelPrepHashTableForUnmatched(HashJoinState *hjstate)
2126 {
2127 HashJoinTable hashtable = hjstate->hj_HashTable;
2128 int curbatch = hashtable->curbatch;
2129 ParallelHashJoinBatch *batch = hashtable->batches[curbatch].shared;
2130
2131 Assert(BarrierPhase(&batch->batch_barrier) == PHJ_BATCH_PROBE);
2132
2133 /*
2134 * It would not be deadlock-free to wait on the batch barrier, because it
2135 * is in PHJ_BATCH_PROBE phase, and thus processes attached to it have
2136 * already emitted tuples. Therefore, we'll hold a wait-free election:
2137 * only one process can continue to the next phase, and all others detach
2138 * from this batch. They can still go any work on other batches, if there
2139 * are any.
2140 */
2141 if (!BarrierArriveAndDetachExceptLast(&batch->batch_barrier))
2142 {
2143 /* This process considers the batch to be done. */
2144 hashtable->batches[hashtable->curbatch].done = true;
2145
2146 /* Make sure any temporary files are closed. */
2147 sts_end_parallel_scan(hashtable->batches[curbatch].inner_tuples);
2148 sts_end_parallel_scan(hashtable->batches[curbatch].outer_tuples);
2149
2150 /*
2151 * Track largest batch we've seen, which would normally happen in
2152 * ExecHashTableDetachBatch().
2153 */
2154 hashtable->spacePeak =
2155 Max(hashtable->spacePeak,
2156 batch->size + sizeof(dsa_pointer_atomic) * hashtable->nbuckets);
2157 hashtable->curbatch = -1;
2158 return false;
2159 }
2160
2161 /* Now we are alone with this batch. */
2162 Assert(BarrierPhase(&batch->batch_barrier) == PHJ_BATCH_SCAN);
2163
2164 /*
2165 * Has another process decided to give up early and command all processes
2166 * to skip the unmatched scan?
2167 */
2168 if (batch->skip_unmatched)
2169 {
2170 hashtable->batches[hashtable->curbatch].done = true;
2171 ExecHashTableDetachBatch(hashtable);
2172 return false;
2173 }
2174
2175 /* Now prepare the process local state, just as for non-parallel join. */
2176 ExecPrepHashTableForUnmatched(hjstate);
2177
2178 return true;
2179 }
2180
2181 /*
2182 * ExecScanHashTableForUnmatched
2183 * scan the hash table for unmatched inner tuples
2184 *
2185 * On success, the inner tuple is stored into hjstate->hj_CurTuple and
2186 * econtext->ecxt_innertuple, using hjstate->hj_HashTupleSlot as the slot
2187 * for the latter.
2188 */
2189 bool
2190 ExecScanHashTableForUnmatched(HashJoinState *hjstate, ExprContext *econtext)
2191 {
2192 HashJoinTable hashtable = hjstate->hj_HashTable;
2193 HashJoinTuple hashTuple = hjstate->hj_CurTuple;
2194
2195 for (;;)
2196 {
2197 /*
2198 * hj_CurTuple is the address of the tuple last returned from the
2199 * current bucket, or NULL if it's time to start scanning a new
2200 * bucket.
2201 */
2202 if (hashTuple != NULL)
2203 hashTuple = hashTuple->next.unshared;
2204 else if (hjstate->hj_CurBucketNo < hashtable->nbuckets)
2205 {
2206 hashTuple = hashtable->buckets.unshared[hjstate->hj_CurBucketNo];
2207 hjstate->hj_CurBucketNo++;
2208 }
2209 else if (hjstate->hj_CurSkewBucketNo < hashtable->nSkewBuckets)
2210 {
2211 int j = hashtable->skewBucketNums[hjstate->hj_CurSkewBucketNo];
2212
2213 hashTuple = hashtable->skewBucket[j]->tuples;
2214 hjstate->hj_CurSkewBucketNo++;
2215 }
2216 else
2217 break; /* finished all buckets */
2218
2219 while (hashTuple != NULL)
2220 {
2221 if (!HeapTupleHeaderHasMatch(HJTUPLE_MINTUPLE(hashTuple)))
2222 {
2223 TupleTableSlot *inntuple;
2224
2225 /* insert hashtable's tuple into exec slot */
2226 inntuple = ExecStoreMinimalTuple(HJTUPLE_MINTUPLE(hashTuple),
2227 hjstate->hj_HashTupleSlot,
2228 false); /* do not pfree */
2229 econtext->ecxt_innertuple = inntuple;
2230
2231 /*
2232 * Reset temp memory each time; although this function doesn't
2233 * do any qual eval, the caller will, so let's keep it
2234 * parallel to ExecScanHashBucket.
2235 */
2236 ResetExprContext(econtext);
2237
2238 hjstate->hj_CurTuple = hashTuple;
2239 return true;
2240 }
2241
2242 hashTuple = hashTuple->next.unshared;
2243 }
2244
2245 /* allow this loop to be cancellable */
2246 CHECK_FOR_INTERRUPTS();
2247 }
2248
2249 /*
2250 * no more unmatched tuples
2251 */
2252 return false;
2253 }
2254
2255 /*
2256 * ExecParallelScanHashTableForUnmatched
2257 * scan the hash table for unmatched inner tuples, in parallel join
2258 *
2259 * On success, the inner tuple is stored into hjstate->hj_CurTuple and
2260 * econtext->ecxt_innertuple, using hjstate->hj_HashTupleSlot as the slot
2261 * for the latter.
2262 */
2263 bool
2264 ExecParallelScanHashTableForUnmatched(HashJoinState *hjstate,
2265 ExprContext *econtext)
2266 {
2267 HashJoinTable hashtable = hjstate->hj_HashTable;
2268 HashJoinTuple hashTuple = hjstate->hj_CurTuple;
2269
2270 for (;;)
2271 {
2272 /*
2273 * hj_CurTuple is the address of the tuple last returned from the
2274 * current bucket, or NULL if it's time to start scanning a new
2275 * bucket.
2276 */
2277 if (hashTuple != NULL)
2278 hashTuple = ExecParallelHashNextTuple(hashtable, hashTuple);
2279 else if (hjstate->hj_CurBucketNo < hashtable->nbuckets)
2280 hashTuple = ExecParallelHashFirstTuple(hashtable,
2281 hjstate->hj_CurBucketNo++);
2282 else
2283 break; /* finished all buckets */
2284
2285 while (hashTuple != NULL)
2286 {
2287 if (!HeapTupleHeaderHasMatch(HJTUPLE_MINTUPLE(hashTuple)))
2288 {
2289 TupleTableSlot *inntuple;
2290
2291 /* insert hashtable's tuple into exec slot */
2292 inntuple = ExecStoreMinimalTuple(HJTUPLE_MINTUPLE(hashTuple),
2293 hjstate->hj_HashTupleSlot,
2294 false); /* do not pfree */
2295 econtext->ecxt_innertuple = inntuple;
2296
2297 /*
2298 * Reset temp memory each time; although this function doesn't
2299 * do any qual eval, the caller will, so let's keep it
2300 * parallel to ExecScanHashBucket.
2301 */
2302 ResetExprContext(econtext);
2303
2304 hjstate->hj_CurTuple = hashTuple;
2305 return true;
2306 }
2307
2308 hashTuple = ExecParallelHashNextTuple(hashtable, hashTuple);
2309 }
2310
2311 /* allow this loop to be cancellable */
2312 CHECK_FOR_INTERRUPTS();
2313 }
2314
2315 /*
2316 * no more unmatched tuples
2317 */
2318 return false;
2319 }
2320
2321 /*
2322 * ExecHashTableReset
2323 *
2324 * reset hash table header for new batch
2325 */
2326 void
2327 ExecHashTableReset(HashJoinTable hashtable)
2328 {
2329 MemoryContext oldcxt;
2330 int nbuckets = hashtable->nbuckets;
2331
2332 /*
2333 * Release all the hash buckets and tuples acquired in the prior pass, and
2334 * reinitialize the context for a new pass.
2335 */
2336 MemoryContextReset(hashtable->batchCxt);
2337 oldcxt = MemoryContextSwitchTo(hashtable->batchCxt);
2338
2339 /* Reallocate and reinitialize the hash bucket headers. */
2340 hashtable->buckets.unshared = palloc0_array(HashJoinTuple, nbuckets);
2341
2342 hashtable->spaceUsed = 0;
2343
2344 MemoryContextSwitchTo(oldcxt);
2345
2346 /* Forget the chunks (the memory was freed by the context reset above). */
2347 hashtable->chunks = NULL;
2348 }
2349
2350 /*
2351 * ExecHashTableResetMatchFlags
2352 * Clear all the HeapTupleHeaderHasMatch flags in the table
2353 */
2354 void
2355 ExecHashTableResetMatchFlags(HashJoinTable hashtable)
2356 {
2357 HashJoinTuple tuple;
2358 int i;
2359
2360 /* Reset all flags in the main table ... */
2361 for (i = 0; i < hashtable->nbuckets; i++)
2362 {
2363 for (tuple = hashtable->buckets.unshared[i]; tuple != NULL;
2364 tuple = tuple->next.unshared)
2365 HeapTupleHeaderClearMatch(HJTUPLE_MINTUPLE(tuple));
2366 }
2367
2368 /* ... and the same for the skew buckets, if any */
2369 for (i = 0; i < hashtable->nSkewBuckets; i++)
2370 {
2371 int j = hashtable->skewBucketNums[i];
2372 HashSkewBucket *skewBucket = hashtable->skewBucket[j];
2373
2374 for (tuple = skewBucket->tuples; tuple != NULL; tuple = tuple->next.unshared)
2375 HeapTupleHeaderClearMatch(HJTUPLE_MINTUPLE(tuple));
2376 }
2377 }
2378
2379
2380 void
2381 ExecReScanHash(HashState *node)
2382 {
2383 PlanState *outerPlan = outerPlanState(node);
2384
2385 /*
2386 * if chgParam of subnode is not null then plan will be re-scanned by
2387 * first ExecProcNode.
2388 */
2389 if (outerPlan->chgParam == NULL)
2390 ExecReScan(outerPlan);
2391 }
2392
2393
2394 /*
2395 * ExecHashBuildSkewHash
2396 *
2397 * Set up for skew optimization if we can identify the most common values
2398 * (MCVs) of the outer relation's join key. We make a skew hash bucket
2399 * for the hash value of each MCV, up to the number of slots allowed
2400 * based on available memory.
2401 */
2402 static void
2403 ExecHashBuildSkewHash(HashState *hashstate, HashJoinTable hashtable,
2404 Hash *node, int mcvsToUse)
2405 {
2406 HeapTupleData *statsTuple;
2407 AttStatsSlot sslot;
2408
2409 /* Do nothing if planner didn't identify the outer relation's join key */
2410 if (!OidIsValid(node->skewTable))
2411 return;
2412 /* Also, do nothing if we don't have room for at least one skew bucket */
2413 if (mcvsToUse <= 0)
2414 return;
2415
2416 /*
2417 * Try to find the MCV statistics for the outer relation's join key.
2418 */
2419 statsTuple = SearchSysCache3(STATRELATTINH,
2420 ObjectIdGetDatum(node->skewTable),
2421 Int16GetDatum(node->skewColumn),
2422 BoolGetDatum(node->skewInherit));
2423 if (!HeapTupleIsValid(statsTuple))
2424 return;
2425
2426 if (get_attstatsslot(&sslot, statsTuple,
2427 STATISTIC_KIND_MCV, InvalidOid,
2428 ATTSTATSSLOT_VALUES | ATTSTATSSLOT_NUMBERS))
2429 {
2430 double frac;
2431 int nbuckets;
2432 int i;
2433
2434 if (mcvsToUse > sslot.nvalues)
2435 mcvsToUse = sslot.nvalues;
2436
2437 /*
2438 * Calculate the expected fraction of outer relation that will
2439 * participate in the skew optimization. If this isn't at least
2440 * SKEW_MIN_OUTER_FRACTION, don't use skew optimization.
2441 */
2442 frac = 0;
2443 for (i = 0; i < mcvsToUse; i++)
2444 frac += sslot.numbers[i];
2445 if (frac < SKEW_MIN_OUTER_FRACTION)
2446 {
2447 free_attstatsslot(&sslot);
2448 ReleaseSysCache(statsTuple);
2449 return;
2450 }
2451
2452 /*
2453 * Okay, set up the skew hashtable.
2454 *
2455 * skewBucket[] is an open addressing hashtable with a power of 2 size
2456 * that is greater than the number of MCV values. (This ensures there
2457 * will be at least one null entry, so searches will always
2458 * terminate.)
2459 *
2460 * Note: this code could fail if mcvsToUse exceeds INT_MAX/8 or
2461 * MaxAllocSize/sizeof(void *)/8, but that is not currently possible
2462 * since we limit pg_statistic entries to much less than that.
2463 */
2464 nbuckets = pg_nextpower2_32(mcvsToUse + 1);
2465 /* use two more bits just to help avoid collisions */
2466 nbuckets <<= 2;
2467
2468 hashtable->skewEnabled = true;
2469 hashtable->skewBucketLen = nbuckets;
2470
2471 /*
2472 * We allocate the bucket memory in the hashtable's batch context. It
2473 * is only needed during the first batch, and this ensures it will be
2474 * automatically removed once the first batch is done.
2475 */
2476 hashtable->skewBucket = (HashSkewBucket **)
2477 MemoryContextAllocZero(hashtable->batchCxt,
2478 nbuckets * sizeof(HashSkewBucket *));
2479 hashtable->skewBucketNums = (int *)
2480 MemoryContextAllocZero(hashtable->batchCxt,
2481 mcvsToUse * sizeof(int));
2482
2483 hashtable->spaceUsed += nbuckets * sizeof(HashSkewBucket *)
2484 + mcvsToUse * sizeof(int);
2485 hashtable->spaceUsedSkew += nbuckets * sizeof(HashSkewBucket *)
2486 + mcvsToUse * sizeof(int);
2487 if (hashtable->spaceUsed > hashtable->spacePeak)
2488 hashtable->spacePeak = hashtable->spaceUsed;
2489
2490 /*
2491 * Create a skew bucket for each MCV hash value.
2492 *
2493 * Note: it is very important that we create the buckets in order of
2494 * decreasing MCV frequency. If we have to remove some buckets, they
2495 * must be removed in reverse order of creation (see notes in
2496 * ExecHashRemoveNextSkewBucket) and we want the least common MCVs to
2497 * be removed first.
2498 */
2499
2500 for (i = 0; i < mcvsToUse; i++)
2501 {
2502 uint32 hashvalue;
2503 int bucket;
2504
2505 hashvalue = DatumGetUInt32(FunctionCall1Coll(hashstate->skew_hashfunction,
2506 hashstate->skew_collation,
2507 sslot.values[i]));
2508
2509 /*
2510 * While we have not hit a hole in the hashtable and have not hit
2511 * the desired bucket, we have collided with some previous hash
2512 * value, so try the next bucket location. NB: this code must
2513 * match ExecHashGetSkewBucket.
2514 */
2515 bucket = hashvalue & (nbuckets - 1);
2516 while (hashtable->skewBucket[bucket] != NULL &&
2517 hashtable->skewBucket[bucket]->hashvalue != hashvalue)
2518 bucket = (bucket + 1) & (nbuckets - 1);
2519
2520 /*
2521 * If we found an existing bucket with the same hashvalue, leave
2522 * it alone. It's okay for two MCVs to share a hashvalue.
2523 */
2524 if (hashtable->skewBucket[bucket] != NULL)
2525 continue;
2526
2527 /* Okay, create a new skew bucket for this hashvalue. */
2528 hashtable->skewBucket[bucket] = (HashSkewBucket *)
2529 MemoryContextAlloc(hashtable->batchCxt,
2530 sizeof(HashSkewBucket));
2531 hashtable->skewBucket[bucket]->hashvalue = hashvalue;
2532 hashtable->skewBucket[bucket]->tuples = NULL;
2533 hashtable->skewBucketNums[hashtable->nSkewBuckets] = bucket;
2534 hashtable->nSkewBuckets++;
2535 hashtable->spaceUsed += SKEW_BUCKET_OVERHEAD;
2536 hashtable->spaceUsedSkew += SKEW_BUCKET_OVERHEAD;
2537 if (hashtable->spaceUsed > hashtable->spacePeak)
2538 hashtable->spacePeak = hashtable->spaceUsed;
2539 }
2540
2541 free_attstatsslot(&sslot);
2542 }
2543
2544 ReleaseSysCache(statsTuple);
2545 }
2546
2547 /*
2548 * ExecHashGetSkewBucket
2549 *
2550 * Returns the index of the skew bucket for this hashvalue,
2551 * or INVALID_SKEW_BUCKET_NO if the hashvalue is not
2552 * associated with any active skew bucket.
2553 */
2554 int
2555 ExecHashGetSkewBucket(HashJoinTable hashtable, uint32 hashvalue)
2556 {
2557 int bucket;
2558
2559 /*
2560 * Always return INVALID_SKEW_BUCKET_NO if not doing skew optimization (in
2561 * particular, this happens after the initial batch is done).
2562 */
2563 if (!hashtable->skewEnabled)
2564 return INVALID_SKEW_BUCKET_NO;
2565
2566 /*
2567 * Since skewBucketLen is a power of 2, we can do a modulo by ANDing.
2568 */
2569 bucket = hashvalue & (hashtable->skewBucketLen - 1);
2570
2571 /*
2572 * While we have not hit a hole in the hashtable and have not hit the
2573 * desired bucket, we have collided with some other hash value, so try the
2574 * next bucket location.
2575 */
2576 while (hashtable->skewBucket[bucket] != NULL &&
2577 hashtable->skewBucket[bucket]->hashvalue != hashvalue)
2578 bucket = (bucket + 1) & (hashtable->skewBucketLen - 1);
2579
2580 /*
2581 * Found the desired bucket?
2582 */
2583 if (hashtable->skewBucket[bucket] != NULL)
2584 return bucket;
2585
2586 /*
2587 * There must not be any hashtable entry for this hash value.
2588 */
2589 return INVALID_SKEW_BUCKET_NO;
2590 }
2591
2592 /*
2593 * ExecHashSkewTableInsert
2594 *
2595 * Insert a tuple into the skew hashtable.
2596 *
2597 * This should generally match up with the current-batch case in
2598 * ExecHashTableInsert.
2599 */
2600 static void
2601 ExecHashSkewTableInsert(HashJoinTable hashtable,
2602 TupleTableSlot *slot,
2603 uint32 hashvalue,
2604 int bucketNumber)
2605 {
2606 bool shouldFree;
2607 MinimalTuple tuple = ExecFetchSlotMinimalTuple(slot, &shouldFree);
2608 HashJoinTuple hashTuple;
2609 int hashTupleSize;
2610
2611 /* Create the HashJoinTuple */
2612 hashTupleSize = HJTUPLE_OVERHEAD + tuple->t_len;
2613 hashTuple = (HashJoinTuple) MemoryContextAlloc(hashtable->batchCxt,
2614 hashTupleSize);
2615 hashTuple->hashvalue = hashvalue;
2616 memcpy(HJTUPLE_MINTUPLE(hashTuple), tuple, tuple->t_len);
2617 HeapTupleHeaderClearMatch(HJTUPLE_MINTUPLE(hashTuple));
2618
2619 /* Push it onto the front of the skew bucket's list */
2620 hashTuple->next.unshared = hashtable->skewBucket[bucketNumber]->tuples;
2621 hashtable->skewBucket[bucketNumber]->tuples = hashTuple;
2622 Assert(hashTuple != hashTuple->next.unshared);
2623
2624 /* Account for space used, and back off if we've used too much */
2625 hashtable->spaceUsed += hashTupleSize;
2626 hashtable->spaceUsedSkew += hashTupleSize;
2627 if (hashtable->spaceUsed > hashtable->spacePeak)
2628 hashtable->spacePeak = hashtable->spaceUsed;
2629 while (hashtable->spaceUsedSkew > hashtable->spaceAllowedSkew)
2630 ExecHashRemoveNextSkewBucket(hashtable);
2631
2632 /* Check we are not over the total spaceAllowed, either */
2633 if (hashtable->spaceUsed > hashtable->spaceAllowed)
2634 ExecHashIncreaseNumBatches(hashtable);
2635
2636 if (shouldFree)
2637 heap_free_minimal_tuple(tuple);
2638 }
2639
2640 /*
2641 * ExecHashRemoveNextSkewBucket
2642 *
2643 * Remove the least valuable skew bucket by pushing its tuples into
2644 * the main hash table.
2645 */
2646 static void
2647 ExecHashRemoveNextSkewBucket(HashJoinTable hashtable)
2648 {
2649 int bucketToRemove;
2650 HashSkewBucket *bucket;
2651 uint32 hashvalue;
2652 int bucketno;
2653 int batchno;
2654 HashJoinTuple hashTuple;
2655
2656 /* Locate the bucket to remove */
2657 bucketToRemove = hashtable->skewBucketNums[hashtable->nSkewBuckets - 1];
2658 bucket = hashtable->skewBucket[bucketToRemove];
2659
2660 /*
2661 * Calculate which bucket and batch the tuples belong to in the main
2662 * hashtable. They all have the same hash value, so it's the same for all
2663 * of them. Also note that it's not possible for nbatch to increase while
2664 * we are processing the tuples.
2665 */
2666 hashvalue = bucket->hashvalue;
2667 ExecHashGetBucketAndBatch(hashtable, hashvalue, &bucketno, &batchno);
2668
2669 /* Process all tuples in the bucket */
2670 hashTuple = bucket->tuples;
2671 while (hashTuple != NULL)
2672 {
2673 HashJoinTuple nextHashTuple = hashTuple->next.unshared;
2674 MinimalTuple tuple;
2675 Size tupleSize;
2676
2677 /*
2678 * This code must agree with ExecHashTableInsert. We do not use
2679 * ExecHashTableInsert directly as ExecHashTableInsert expects a
2680 * TupleTableSlot while we already have HashJoinTuples.
2681 */
2682 tuple = HJTUPLE_MINTUPLE(hashTuple);
2683 tupleSize = HJTUPLE_OVERHEAD + tuple->t_len;
2684
2685 /* Decide whether to put the tuple in the hash table or a temp file */
2686 if (batchno == hashtable->curbatch)
2687 {
2688 /* Move the tuple to the main hash table */
2689 HashJoinTuple copyTuple;
2690
2691 /*
2692 * We must copy the tuple into the dense storage, else it will not
2693 * be found by, eg, ExecHashIncreaseNumBatches.
2694 */
2695 copyTuple = (HashJoinTuple) dense_alloc(hashtable, tupleSize);
2696 memcpy(copyTuple, hashTuple, tupleSize);
2697 pfree(hashTuple);
2698
2699 copyTuple->next.unshared = hashtable->buckets.unshared[bucketno];
2700 hashtable->buckets.unshared[bucketno] = copyTuple;
2701
2702 /* We have reduced skew space, but overall space doesn't change */
2703 hashtable->spaceUsedSkew -= tupleSize;
2704 }
2705 else
2706 {
2707 /* Put the tuple into a temp file for later batches */
2708 Assert(batchno > hashtable->curbatch);
2709 ExecHashJoinSaveTuple(tuple, hashvalue,
2710 &hashtable->innerBatchFile[batchno],
2711 hashtable);
2712 pfree(hashTuple);
2713 hashtable->spaceUsed -= tupleSize;
2714 hashtable->spaceUsedSkew -= tupleSize;
2715 }
2716
2717 hashTuple = nextHashTuple;
2718
2719 /* allow this loop to be cancellable */
2720 CHECK_FOR_INTERRUPTS();
2721 }
2722
2723 /*
2724 * Free the bucket struct itself and reset the hashtable entry to NULL.
2725 *
2726 * NOTE: this is not nearly as simple as it looks on the surface, because
2727 * of the possibility of collisions in the hashtable. Suppose that hash
2728 * values A and B collide at a particular hashtable entry, and that A was
2729 * entered first so B gets shifted to a different table entry. If we were
2730 * to remove A first then ExecHashGetSkewBucket would mistakenly start
2731 * reporting that B is not in the hashtable, because it would hit the NULL
2732 * before finding B. However, we always remove entries in the reverse
2733 * order of creation, so this failure cannot happen.
2734 */
2735 hashtable->skewBucket[bucketToRemove] = NULL;
2736 hashtable->nSkewBuckets--;
2737 pfree(bucket);
2738 hashtable->spaceUsed -= SKEW_BUCKET_OVERHEAD;
2739 hashtable->spaceUsedSkew -= SKEW_BUCKET_OVERHEAD;
2740
2741 /*
2742 * If we have removed all skew buckets then give up on skew optimization.
2743 * Release the arrays since they aren't useful any more.
2744 */
2745 if (hashtable->nSkewBuckets == 0)
2746 {
2747 hashtable->skewEnabled = false;
2748 pfree(hashtable->skewBucket);
2749 pfree(hashtable->skewBucketNums);
2750 hashtable->skewBucket = NULL;
2751 hashtable->skewBucketNums = NULL;
2752 hashtable->spaceUsed -= hashtable->spaceUsedSkew;
2753 hashtable->spaceUsedSkew = 0;
2754 }
2755 }
2756
2757 /*
2758 * Reserve space in the DSM segment for instrumentation data.
2759 */
2760 void
2761 ExecHashEstimate(HashState *node, ParallelContext *pcxt)
2762 {
2763 size_t size;
2764
2765 /* don't need this if not instrumenting or no workers */
2766 if (!node->ps.instrument || pcxt->nworkers == 0)
2767 return;
2768
2769 size = mul_size(pcxt->nworkers, sizeof(HashInstrumentation));
2770 size = add_size(size, offsetof(SharedHashInfo, hinstrument));
2771 shm_toc_estimate_chunk(&pcxt->estimator, size);
2772 shm_toc_estimate_keys(&pcxt->estimator, 1);
2773 }
2774
2775 /*
2776 * Set up a space in the DSM for all workers to record instrumentation data
2777 * about their hash table.
2778 */
2779 void
2780 ExecHashInitializeDSM(HashState *node, ParallelContext *pcxt)
2781 {
2782 size_t size;
2783
2784 /* don't need this if not instrumenting or no workers */
2785 if (!node->ps.instrument || pcxt->nworkers == 0)
2786 return;
2787
2788 size = offsetof(SharedHashInfo, hinstrument) +
2789 pcxt->nworkers * sizeof(HashInstrumentation);
2790 node->shared_info = (SharedHashInfo *) shm_toc_allocate(pcxt->toc, size);
2791
2792 /* Each per-worker area must start out as zeroes. */
2793 memset(node->shared_info, 0, size);
2794
2795 node->shared_info->num_workers = pcxt->nworkers;
2796 shm_toc_insert(pcxt->toc, node->ps.plan->plan_node_id,
2797 node->shared_info);
2798 }
2799
2800 /*
2801 * Locate the DSM space for hash table instrumentation data that we'll write
2802 * to at shutdown time.
2803 */
2804 void
2805 ExecHashInitializeWorker(HashState *node, ParallelWorkerContext *pwcxt)
2806 {
2807 SharedHashInfo *shared_info;
2808
2809 /* don't need this if not instrumenting */
2810 if (!node->ps.instrument)
2811 return;
2812
2813 /*
2814 * Find our entry in the shared area, and set up a pointer to it so that
2815 * we'll accumulate stats there when shutting down or rebuilding the hash
2816 * table.
2817 */
2818 shared_info = (SharedHashInfo *)
2819 shm_toc_lookup(pwcxt->toc, node->ps.plan->plan_node_id, false);
2820 node->hinstrument = &shared_info->hinstrument[ParallelWorkerNumber];
2821 }
2822
2823 /*
2824 * Collect EXPLAIN stats if needed, saving them into DSM memory if
2825 * ExecHashInitializeWorker was called, or local storage if not. In the
2826 * parallel case, this must be done in ExecShutdownHash() rather than
2827 * ExecEndHash() because the latter runs after we've detached from the DSM
2828 * segment.
2829 */
2830 void
2831 ExecShutdownHash(HashState *node)
2832 {
2833 /* Allocate save space if EXPLAIN'ing and we didn't do so already */
2834 if (node->ps.instrument && !node->hinstrument)
2835 node->hinstrument = palloc0_object(HashInstrumentation);
2836 /* Now accumulate data for the current (final) hash table */
2837 if (node->hinstrument && node->hashtable)
2838 ExecHashAccumInstrumentation(node->hinstrument, node->hashtable);
2839 }
2840
2841 /*
2842 * Retrieve instrumentation data from workers before the DSM segment is
2843 * detached, so that EXPLAIN can access it.
2844 */
2845 void
2846 ExecHashRetrieveInstrumentation(HashState *node)
2847 {
2848 SharedHashInfo *shared_info = node->shared_info;
2849 size_t size;
2850
2851 if (shared_info == NULL)
2852 return;
2853
2854 /* Replace node->shared_info with a copy in backend-local memory. */
2855 size = offsetof(SharedHashInfo, hinstrument) +
2856 shared_info->num_workers * sizeof(HashInstrumentation);
2857 node->shared_info = palloc(size);
2858 memcpy(node->shared_info, shared_info, size);
2859 }
2860
2861 /*
2862 * Accumulate instrumentation data from 'hashtable' into an
2863 * initially-zeroed HashInstrumentation struct.
2864 *
2865 * This is used to merge information across successive hash table instances
2866 * within a single plan node. We take the maximum values of each interesting
2867 * number. The largest nbuckets and largest nbatch values might have occurred
2868 * in different instances, so there's some risk of confusion from reporting
2869 * unrelated numbers; but there's a bigger risk of misdiagnosing a performance
2870 * issue if we don't report the largest values. Similarly, we want to report
2871 * the largest spacePeak regardless of whether it happened in the same
2872 * instance as the largest nbuckets or nbatch. All the instances should have
2873 * the same nbuckets_original and nbatch_original; but there's little value
2874 * in depending on that here, so handle them the same way.
2875 */
2876 void
2877 ExecHashAccumInstrumentation(HashInstrumentation *instrument,
2878 HashJoinTable hashtable)
2879 {
2880 instrument->nbuckets = Max(instrument->nbuckets,
2881 hashtable->nbuckets);
2882 instrument->nbuckets_original = Max(instrument->nbuckets_original,
2883 hashtable->nbuckets_original);
2884 instrument->nbatch = Max(instrument->nbatch,
2885 hashtable->nbatch);
2886 instrument->nbatch_original = Max(instrument->nbatch_original,
2887 hashtable->nbatch_original);
2888 instrument->space_peak = Max(instrument->space_peak,
2889 hashtable->spacePeak);
2890 }
2891
2892 /*
2893 * Allocate 'size' bytes from the currently active HashMemoryChunk
2894 */
2895 static void *
2896 dense_alloc(HashJoinTable hashtable, Size size)
2897 {
2898 HashMemoryChunk newChunk;
2899 char *ptr;
2900
2901 /* just in case the size is not already aligned properly */
2902 size = MAXALIGN(size);
2903
2904 /*
2905 * If tuple size is larger than threshold, allocate a separate chunk.
2906 */
2907 if (size > HASH_CHUNK_THRESHOLD)
2908 {
2909 /* allocate new chunk and put it at the beginning of the list */
2910 newChunk = (HashMemoryChunk) MemoryContextAlloc(hashtable->batchCxt,
2911 HASH_CHUNK_HEADER_SIZE + size);
2912 newChunk->maxlen = size;
2913 newChunk->used = size;
2914 newChunk->ntuples = 1;
2915
2916 /*
2917 * Add this chunk to the list after the first existing chunk, so that
2918 * we don't lose the remaining space in the "current" chunk.
2919 */
2920 if (hashtable->chunks != NULL)
2921 {
2922 newChunk->next = hashtable->chunks->next;
2923 hashtable->chunks->next.unshared = newChunk;
2924 }
2925 else
2926 {
2927 newChunk->next.unshared = hashtable->chunks;
2928 hashtable->chunks = newChunk;
2929 }
2930
2931 return HASH_CHUNK_DATA(newChunk);
2932 }
2933
2934 /*
2935 * See if we have enough space for it in the current chunk (if any). If
2936 * not, allocate a fresh chunk.
2937 */
2938 if ((hashtable->chunks == NULL) ||
2939 (hashtable->chunks->maxlen - hashtable->chunks->used) < size)
2940 {
2941 /* allocate new chunk and put it at the beginning of the list */
2942 newChunk = (HashMemoryChunk) MemoryContextAlloc(hashtable->batchCxt,
2943 HASH_CHUNK_HEADER_SIZE + HASH_CHUNK_SIZE);
2944
2945 newChunk->maxlen = HASH_CHUNK_SIZE;
2946 newChunk->used = size;
2947 newChunk->ntuples = 1;
2948
2949 newChunk->next.unshared = hashtable->chunks;
2950 hashtable->chunks = newChunk;
2951
2952 return HASH_CHUNK_DATA(newChunk);
2953 }
2954
2955 /* There is enough space in the current chunk, let's add the tuple */
2956 ptr = HASH_CHUNK_DATA(hashtable->chunks) + hashtable->chunks->used;
2957 hashtable->chunks->used += size;
2958 hashtable->chunks->ntuples += 1;
2959
2960 /* return pointer to the start of the tuple memory */
2961 return ptr;
2962 }
2963
2964 /*
2965 * Allocate space for a tuple in shared dense storage. This is equivalent to
2966 * dense_alloc but for Parallel Hash using shared memory.
2967 *
2968 * While loading a tuple into shared memory, we might run out of memory and
2969 * decide to repartition, or determine that the load factor is too high and
2970 * decide to expand the bucket array, or discover that another participant has
2971 * commanded us to help do that. Return NULL if number of buckets or batches
2972 * has changed, indicating that the caller must retry (considering the
2973 * possibility that the tuple no longer belongs in the same batch).
2974 */
2975 static HashJoinTuple
2976 ExecParallelHashTupleAlloc(HashJoinTable hashtable, size_t size,
2977 dsa_pointer *shared)
2978 {
2979 ParallelHashJoinState *pstate = hashtable->parallel_state;
2980 dsa_pointer chunk_shared;
2981 HashMemoryChunk chunk;
2982 Size chunk_size;
2983 HashJoinTuple result;
2984 int curbatch = hashtable->curbatch;
2985
2986 size = MAXALIGN(size);
2987
2988 /*
2989 * Fast path: if there is enough space in this backend's current chunk,
2990 * then we can allocate without any locking.
2991 */
2992 chunk = hashtable->current_chunk;
2993 if (chunk != NULL &&
2994 size <= HASH_CHUNK_THRESHOLD &&
2995 chunk->maxlen - chunk->used >= size)
2996 {
2997
2998 chunk_shared = hashtable->current_chunk_shared;
2999 Assert(chunk == dsa_get_address(hashtable->area, chunk_shared));
3000 *shared = chunk_shared + HASH_CHUNK_HEADER_SIZE + chunk->used;
3001 result = (HashJoinTuple) (HASH_CHUNK_DATA(chunk) + chunk->used);
3002 chunk->used += size;
3003
3004 Assert(chunk->used <= chunk->maxlen);
3005 Assert(result == dsa_get_address(hashtable->area, *shared));
3006
3007 return result;
3008 }
3009
3010 /* Slow path: try to allocate a new chunk. */
3011 LWLockAcquire(&pstate->lock, LW_EXCLUSIVE);
3012
3013 /*
3014 * Check if we need to help increase the number of buckets or batches.
3015 */
3016 if (pstate->growth == PHJ_GROWTH_NEED_MORE_BATCHES ||
3017 pstate->growth == PHJ_GROWTH_NEED_MORE_BUCKETS)
3018 {
3019 ParallelHashGrowth growth = pstate->growth;
3020
3021 hashtable->current_chunk = NULL;
3022 LWLockRelease(&pstate->lock);
3023
3024 /* Another participant has commanded us to help grow. */
3025 if (growth == PHJ_GROWTH_NEED_MORE_BATCHES)
3026 ExecParallelHashIncreaseNumBatches(hashtable);
3027 else if (growth == PHJ_GROWTH_NEED_MORE_BUCKETS)
3028 ExecParallelHashIncreaseNumBuckets(hashtable);
3029
3030 /* The caller must retry. */
3031 return NULL;
3032 }
3033
3034 /* Oversized tuples get their own chunk. */
3035 if (size > HASH_CHUNK_THRESHOLD)
3036 chunk_size = size + HASH_CHUNK_HEADER_SIZE;
3037 else
3038 chunk_size = HASH_CHUNK_SIZE;
3039
3040 /* Check if it's time to grow batches or buckets. */
3041 if (pstate->growth != PHJ_GROWTH_DISABLED)
3042 {
3043 Assert(curbatch == 0);
3044 Assert(BarrierPhase(&pstate->build_barrier) == PHJ_BUILD_HASH_INNER);
3045
3046 /*
3047 * Check if our space limit would be exceeded. To avoid choking on
3048 * very large tuples or very low hash_mem setting, we'll always allow
3049 * each backend to allocate at least one chunk.
3050 */
3051 if (hashtable->batches[0].at_least_one_chunk &&
3052 hashtable->batches[0].shared->size +
3053 chunk_size > pstate->space_allowed)
3054 {
3055 pstate->growth = PHJ_GROWTH_NEED_MORE_BATCHES;
3056 hashtable->batches[0].shared->space_exhausted = true;
3057 LWLockRelease(&pstate->lock);
3058
3059 return NULL;
3060 }
3061
3062 /* Check if our load factor limit would be exceeded. */
3063 if (hashtable->nbatch == 1)
3064 {
3065 hashtable->batches[0].shared->ntuples += hashtable->batches[0].ntuples;
3066 hashtable->batches[0].ntuples = 0;
3067 /* Guard against integer overflow and alloc size overflow */
3068 if (hashtable->batches[0].shared->ntuples + 1 >
3069 hashtable->nbuckets * NTUP_PER_BUCKET &&
3070 hashtable->nbuckets < (INT_MAX / 2) &&
3071 hashtable->nbuckets * 2 <=
3072 MaxAllocSize / sizeof(dsa_pointer_atomic))
3073 {
3074 pstate->growth = PHJ_GROWTH_NEED_MORE_BUCKETS;
3075 LWLockRelease(&pstate->lock);
3076
3077 return NULL;
3078 }
3079 }
3080 }
3081
3082 /* We are cleared to allocate a new chunk. */
3083 chunk_shared = dsa_allocate(hashtable->area, chunk_size);
3084 hashtable->batches[curbatch].shared->size += chunk_size;
3085 hashtable->batches[curbatch].at_least_one_chunk = true;
3086
3087 /* Set up the chunk. */
3088 chunk = (HashMemoryChunk) dsa_get_address(hashtable->area, chunk_shared);
3089 *shared = chunk_shared + HASH_CHUNK_HEADER_SIZE;
3090 chunk->maxlen = chunk_size - HASH_CHUNK_HEADER_SIZE;
3091 chunk->used = size;
3092
3093 /*
3094 * Push it onto the list of chunks, so that it can be found if we need to
3095 * increase the number of buckets or batches (batch 0 only) and later for
3096 * freeing the memory (all batches).
3097 */
3098 chunk->next.shared = hashtable->batches[curbatch].shared->chunks;
3099 hashtable->batches[curbatch].shared->chunks = chunk_shared;
3100
3101 if (size <= HASH_CHUNK_THRESHOLD)
3102 {
3103 /*
3104 * Make this the current chunk so that we can use the fast path to
3105 * fill the rest of it up in future calls.
3106 */
3107 hashtable->current_chunk = chunk;
3108 hashtable->current_chunk_shared = chunk_shared;
3109 }
3110 LWLockRelease(&pstate->lock);
3111
3112 Assert(HASH_CHUNK_DATA(chunk) == dsa_get_address(hashtable->area, *shared));
3113 result = (HashJoinTuple) HASH_CHUNK_DATA(chunk);
3114
3115 return result;
3116 }
3117
3118 /*
3119 * One backend needs to set up the shared batch state including tuplestores.
3120 * Other backends will ensure they have correctly configured accessors by
3121 * called ExecParallelHashEnsureBatchAccessors().
3122 */
3123 static void
3124 ExecParallelHashJoinSetUpBatches(HashJoinTable hashtable, int nbatch)
3125 {
3126 ParallelHashJoinState *pstate = hashtable->parallel_state;
3127 ParallelHashJoinBatch *batches;
3128 MemoryContext oldcxt;
3129 int i;
3130
3131 Assert(hashtable->batches == NULL);
3132
3133 /* Allocate space. */
3134 pstate->batches =
3135 dsa_allocate0(hashtable->area,
3136 EstimateParallelHashJoinBatch(hashtable) * nbatch);
3137 pstate->nbatch = nbatch;
3138 batches = dsa_get_address(hashtable->area, pstate->batches);
3139
3140 /*
3141 * Use hash join spill memory context to allocate accessors, including
3142 * buffers for the temporary files.
3143 */
3144 oldcxt = MemoryContextSwitchTo(hashtable->spillCxt);
3145
3146 /* Allocate this backend's accessor array. */
3147 hashtable->nbatch = nbatch;
3148 hashtable->batches =
3149 palloc0_array(ParallelHashJoinBatchAccessor, hashtable->nbatch);
3150
3151 /* Set up the shared state, tuplestores and backend-local accessors. */
3152 for (i = 0; i < hashtable->nbatch; ++i)
3153 {
3154 ParallelHashJoinBatchAccessor *accessor = &hashtable->batches[i];
3155 ParallelHashJoinBatch *shared = NthParallelHashJoinBatch(batches, i);
3156 char name[MAXPGPATH];
3157
3158 /*
3159 * All members of shared were zero-initialized. We just need to set
3160 * up the Barrier.
3161 */
3162 BarrierInit(&shared->batch_barrier, 0);
3163 if (i == 0)
3164 {
3165 /* Batch 0 doesn't need to be loaded. */
3166 BarrierAttach(&shared->batch_barrier);
3167 while (BarrierPhase(&shared->batch_barrier) < PHJ_BATCH_PROBE)
3168 BarrierArriveAndWait(&shared->batch_barrier, 0);
3169 BarrierDetach(&shared->batch_barrier);
3170 }
3171
3172 /* Initialize accessor state. All members were zero-initialized. */
3173 accessor->shared = shared;
3174
3175 /* Initialize the shared tuplestores. */
3176 snprintf(name, sizeof(name), "i%dof%d", i, hashtable->nbatch);
3177 accessor->inner_tuples =
3178 sts_initialize(ParallelHashJoinBatchInner(shared),
3179 pstate->nparticipants,
3180 ParallelWorkerNumber + 1,
3181 sizeof(uint32),
3182 SHARED_TUPLESTORE_SINGLE_PASS,
3183 &pstate->fileset,
3184 name);
3185 snprintf(name, sizeof(name), "o%dof%d", i, hashtable->nbatch);
3186 accessor->outer_tuples =
3187 sts_initialize(ParallelHashJoinBatchOuter(shared,
3188 pstate->nparticipants),
3189 pstate->nparticipants,
3190 ParallelWorkerNumber + 1,
3191 sizeof(uint32),
3192 SHARED_TUPLESTORE_SINGLE_PASS,
3193 &pstate->fileset,
3194 name);
3195 }
3196
3197 MemoryContextSwitchTo(oldcxt);
3198 }
3199
3200 /*
3201 * Free the current set of ParallelHashJoinBatchAccessor objects.
3202 */
3203 static void
3204 ExecParallelHashCloseBatchAccessors(HashJoinTable hashtable)
3205 {
3206 int i;
3207
3208 for (i = 0; i < hashtable->nbatch; ++i)
3209 {
3210 /* Make sure no files are left open. */
3211 sts_end_write(hashtable->batches[i].inner_tuples);
3212 sts_end_write(hashtable->batches[i].outer_tuples);
3213 sts_end_parallel_scan(hashtable->batches[i].inner_tuples);
3214 sts_end_parallel_scan(hashtable->batches[i].outer_tuples);
3215 }
3216 pfree(hashtable->batches);
3217 hashtable->batches = NULL;
3218 }
3219
3220 /*
3221 * Make sure this backend has up-to-date accessors for the current set of
3222 * batches.
3223 */
3224 static void
3225 ExecParallelHashEnsureBatchAccessors(HashJoinTable hashtable)
3226 {
3227 ParallelHashJoinState *pstate = hashtable->parallel_state;
3228 ParallelHashJoinBatch *batches;
3229 MemoryContext oldcxt;
3230 int i;
3231
3232 if (hashtable->batches != NULL)
3233 {
3234 if (hashtable->nbatch == pstate->nbatch)
3235 return;
3236 ExecParallelHashCloseBatchAccessors(hashtable);
3237 }
3238
3239 /*
3240 * We should never see a state where the batch-tracking array is freed,
3241 * because we should have given up sooner if we join when the build
3242 * barrier has reached the PHJ_BUILD_FREE phase.
3243 */
3244 Assert(DsaPointerIsValid(pstate->batches));
3245
3246 /*
3247 * Use hash join spill memory context to allocate accessors, including
3248 * buffers for the temporary files.
3249 */
3250 oldcxt = MemoryContextSwitchTo(hashtable->spillCxt);
3251
3252 /* Allocate this backend's accessor array. */
3253 hashtable->nbatch = pstate->nbatch;
3254 hashtable->batches =
3255 palloc0_array(ParallelHashJoinBatchAccessor, hashtable->nbatch);
3256
3257 /* Find the base of the pseudo-array of ParallelHashJoinBatch objects. */
3258 batches = (ParallelHashJoinBatch *)
3259 dsa_get_address(hashtable->area, pstate->batches);
3260
3261 /* Set up the accessor array and attach to the tuplestores. */
3262 for (i = 0; i < hashtable->nbatch; ++i)
3263 {
3264 ParallelHashJoinBatchAccessor *accessor = &hashtable->batches[i];
3265 ParallelHashJoinBatch *shared = NthParallelHashJoinBatch(batches, i);
3266
3267 accessor->shared = shared;
3268 accessor->preallocated = 0;
3269 accessor->done = false;
3270 accessor->outer_eof = false;
3271 accessor->inner_tuples =
3272 sts_attach(ParallelHashJoinBatchInner(shared),
3273 ParallelWorkerNumber + 1,
3274 &pstate->fileset);
3275 accessor->outer_tuples =
3276 sts_attach(ParallelHashJoinBatchOuter(shared,
3277 pstate->nparticipants),
3278 ParallelWorkerNumber + 1,
3279 &pstate->fileset);
3280 }
3281
3282 MemoryContextSwitchTo(oldcxt);
3283 }
3284
3285 /*
3286 * Allocate an empty shared memory hash table for a given batch.
3287 */
3288 void
3289 ExecParallelHashTableAlloc(HashJoinTable hashtable, int batchno)
3290 {
3291 ParallelHashJoinBatch *batch = hashtable->batches[batchno].shared;
3292 dsa_pointer_atomic *buckets;
3293 int nbuckets = hashtable->parallel_state->nbuckets;
3294 int i;
3295
3296 batch->buckets =
3297 dsa_allocate(hashtable->area, sizeof(dsa_pointer_atomic) * nbuckets);
3298 buckets = (dsa_pointer_atomic *)
3299 dsa_get_address(hashtable->area, batch->buckets);
3300 for (i = 0; i < nbuckets; ++i)
3301 dsa_pointer_atomic_init(&buckets[i], InvalidDsaPointer);
3302 }
3303
3304 /*
3305 * If we are currently attached to a shared hash join batch, detach. If we
3306 * are last to detach, clean up.
3307 */
3308 void
3309 ExecHashTableDetachBatch(HashJoinTable hashtable)
3310 {
3311 if (hashtable->parallel_state != NULL &&
3312 hashtable->curbatch >= 0)
3313 {
3314 int curbatch = hashtable->curbatch;
3315 ParallelHashJoinBatch *batch = hashtable->batches[curbatch].shared;
3316 bool attached = true;
3317
3318 /* Make sure any temporary files are closed. */
3319 sts_end_parallel_scan(hashtable->batches[curbatch].inner_tuples);
3320 sts_end_parallel_scan(hashtable->batches[curbatch].outer_tuples);
3321
3322 /* After attaching we always get at least to PHJ_BATCH_PROBE. */
3323 Assert(BarrierPhase(&batch->batch_barrier) == PHJ_BATCH_PROBE ||
3324 BarrierPhase(&batch->batch_barrier) == PHJ_BATCH_SCAN);
3325
3326 /*
3327 * If we're abandoning the PHJ_BATCH_PROBE phase early without having
3328 * reached the end of it, it means the plan doesn't want any more
3329 * tuples, and it is happy to abandon any tuples buffered in this
3330 * process's subplans. For correctness, we can't allow any process to
3331 * execute the PHJ_BATCH_SCAN phase, because we will never have the
3332 * complete set of match bits. Therefore we skip emitting unmatched
3333 * tuples in all backends (if this is a full/right join), as if those
3334 * tuples were all due to be emitted by this process and it has
3335 * abandoned them too.
3336 */
3337 if (BarrierPhase(&batch->batch_barrier) == PHJ_BATCH_PROBE &&
3338 !hashtable->batches[curbatch].outer_eof)
3339 {
3340 /*
3341 * This flag may be written to by multiple backends during
3342 * PHJ_BATCH_PROBE phase, but will only be read in PHJ_BATCH_SCAN
3343 * phase so requires no extra locking.
3344 */
3345 batch->skip_unmatched = true;
3346 }
3347
3348 /*
3349 * Even if we aren't doing a full/right outer join, we'll step through
3350 * the PHJ_BATCH_SCAN phase just to maintain the invariant that
3351 * freeing happens in PHJ_BATCH_FREE, but that'll be wait-free.
3352 */
3353 if (BarrierPhase(&batch->batch_barrier) == PHJ_BATCH_PROBE)
3354 attached = BarrierArriveAndDetachExceptLast(&batch->batch_barrier);
3355 if (attached && BarrierArriveAndDetach(&batch->batch_barrier))
3356 {
3357 /*
3358 * We are not longer attached to the batch barrier, but we're the
3359 * process that was chosen to free resources and it's safe to
3360 * assert the current phase. The ParallelHashJoinBatch can't go
3361 * away underneath us while we are attached to the build barrier,
3362 * making this access safe.
3363 */
3364 Assert(BarrierPhase(&batch->batch_barrier) == PHJ_BATCH_FREE);
3365
3366 /* Free shared chunks and buckets. */
3367 while (DsaPointerIsValid(batch->chunks))
3368 {
3369 HashMemoryChunk chunk =
3370 dsa_get_address(hashtable->area, batch->chunks);
3371 dsa_pointer next = chunk->next.shared;
3372
3373 dsa_free(hashtable->area, batch->chunks);
3374 batch->chunks = next;
3375 }
3376 if (DsaPointerIsValid(batch->buckets))
3377 {
3378 dsa_free(hashtable->area, batch->buckets);
3379 batch->buckets = InvalidDsaPointer;
3380 }
3381 }
3382
3383 /*
3384 * Track the largest batch we've been attached to. Though each
3385 * backend might see a different subset of batches, explain.c will
3386 * scan the results from all backends to find the largest value.
3387 */
3388 hashtable->spacePeak =
3389 Max(hashtable->spacePeak,
3390 batch->size + sizeof(dsa_pointer_atomic) * hashtable->nbuckets);
3391
3392 /* Remember that we are not attached to a batch. */
3393 hashtable->curbatch = -1;
3394 }
3395 }
3396
3397 /*
3398 * Detach from all shared resources. If we are last to detach, clean up.
3399 */
3400 void
3401 ExecHashTableDetach(HashJoinTable hashtable)
3402 {
3403 ParallelHashJoinState *pstate = hashtable->parallel_state;
3404
3405 /*
3406 * If we're involved in a parallel query, we must either have gotten all
3407 * the way to PHJ_BUILD_RUN, or joined too late and be in PHJ_BUILD_FREE.
3408 */
3409 Assert(!pstate ||
3410 BarrierPhase(&pstate->build_barrier) >= PHJ_BUILD_RUN);
3411
3412 if (pstate && BarrierPhase(&pstate->build_barrier) == PHJ_BUILD_RUN)
3413 {
3414 int i;
3415
3416 /* Make sure any temporary files are closed. */
3417 if (hashtable->batches)
3418 {
3419 for (i = 0; i < hashtable->nbatch; ++i)
3420 {
3421 sts_end_write(hashtable->batches[i].inner_tuples);
3422 sts_end_write(hashtable->batches[i].outer_tuples);
3423 sts_end_parallel_scan(hashtable->batches[i].inner_tuples);
3424 sts_end_parallel_scan(hashtable->batches[i].outer_tuples);
3425 }
3426 }
3427
3428 /* If we're last to detach, clean up shared memory. */
3429 if (BarrierArriveAndDetach(&pstate->build_barrier))
3430 {
3431 /*
3432 * Late joining processes will see this state and give up
3433 * immediately.
3434 */
3435 Assert(BarrierPhase(&pstate->build_barrier) == PHJ_BUILD_FREE);
3436
3437 if (DsaPointerIsValid(pstate->batches))
3438 {
3439 dsa_free(hashtable->area, pstate->batches);
3440 pstate->batches = InvalidDsaPointer;
3441 }
3442 }
3443 }
3444 hashtable->parallel_state = NULL;
3445 }
3446
3447 /*
3448 * Get the first tuple in a given bucket identified by number.
3449 */
3450 static inline HashJoinTuple
3451 ExecParallelHashFirstTuple(HashJoinTable hashtable, int bucketno)
3452 {
3453 HashJoinTuple tuple;
3454 dsa_pointer p;
3455
3456 Assert(hashtable->parallel_state);
3457 p = dsa_pointer_atomic_read(&hashtable->buckets.shared[bucketno]);
3458 tuple = (HashJoinTuple) dsa_get_address(hashtable->area, p);
3459
3460 return tuple;
3461 }
3462
3463 /*
3464 * Get the next tuple in the same bucket as 'tuple'.
3465 */
3466 static inline HashJoinTuple
3467 ExecParallelHashNextTuple(HashJoinTable hashtable, HashJoinTuple tuple)
3468 {
3469 HashJoinTuple next;
3470
3471 Assert(hashtable->parallel_state);
3472 next = (HashJoinTuple) dsa_get_address(hashtable->area, tuple->next.shared);
3473
3474 return next;
3475 }
3476
3477 /*
3478 * Insert a tuple at the front of a chain of tuples in DSA memory atomically.
3479 */
3480 static inline void
3481 ExecParallelHashPushTuple(dsa_pointer_atomic *head,
3482 HashJoinTuple tuple,
3483 dsa_pointer tuple_shared)
3484 {
3485 for (;;)
3486 {
3487 tuple->next.shared = dsa_pointer_atomic_read(head);
3488 if (dsa_pointer_atomic_compare_exchange(head,
3489 &tuple->next.shared,
3490 tuple_shared))
3491 break;
3492 }
3493 }
3494
3495 /*
3496 * Prepare to work on a given batch.
3497 */
3498 void
3499 ExecParallelHashTableSetCurrentBatch(HashJoinTable hashtable, int batchno)
3500 {
3501 Assert(hashtable->batches[batchno].shared->buckets != InvalidDsaPointer);
3502
3503 hashtable->curbatch = batchno;
3504 hashtable->buckets.shared = (dsa_pointer_atomic *)
3505 dsa_get_address(hashtable->area,
3506 hashtable->batches[batchno].shared->buckets);
3507 hashtable->nbuckets = hashtable->parallel_state->nbuckets;
3508 hashtable->log2_nbuckets = my_log2(hashtable->nbuckets);
3509 hashtable->current_chunk = NULL;
3510 hashtable->current_chunk_shared = InvalidDsaPointer;
3511 hashtable->batches[batchno].at_least_one_chunk = false;
3512 }
3513
3514 /*
3515 * Take the next available chunk from the queue of chunks being worked on in
3516 * parallel. Return NULL if there are none left. Otherwise return a pointer
3517 * to the chunk, and set *shared to the DSA pointer to the chunk.
3518 */
3519 static HashMemoryChunk
3520 ExecParallelHashPopChunkQueue(HashJoinTable hashtable, dsa_pointer *shared)
3521 {
3522 ParallelHashJoinState *pstate = hashtable->parallel_state;
3523 HashMemoryChunk chunk;
3524
3525 LWLockAcquire(&pstate->lock, LW_EXCLUSIVE);
3526 if (DsaPointerIsValid(pstate->chunk_work_queue))
3527 {
3528 *shared = pstate->chunk_work_queue;
3529 chunk = (HashMemoryChunk)
3530 dsa_get_address(hashtable->area, *shared);
3531 pstate->chunk_work_queue = chunk->next.shared;
3532 }
3533 else
3534 chunk = NULL;
3535 LWLockRelease(&pstate->lock);
3536
3537 return chunk;
3538 }
3539
3540 /*
3541 * Increase the space preallocated in this backend for a given inner batch by
3542 * at least a given amount. This allows us to track whether a given batch
3543 * would fit in memory when loaded back in. Also increase the number of
3544 * batches or buckets if required.
3545 *
3546 * This maintains a running estimation of how much space will be taken when we
3547 * load the batch back into memory by simulating the way chunks will be handed
3548 * out to workers. It's not perfectly accurate because the tuples will be
3549 * packed into memory chunks differently by ExecParallelHashTupleAlloc(), but
3550 * it should be pretty close. It tends to overestimate by a fraction of a
3551 * chunk per worker since all workers gang up to preallocate during hashing,
3552 * but workers tend to reload batches alone if there are enough to go around,
3553 * leaving fewer partially filled chunks. This effect is bounded by
3554 * nparticipants.
3555 *
3556 * Return false if the number of batches or buckets has changed, and the
3557 * caller should reconsider which batch a given tuple now belongs in and call
3558 * again.
3559 */
3560 static bool
3561 ExecParallelHashTuplePrealloc(HashJoinTable hashtable, int batchno, size_t size)
3562 {
3563 ParallelHashJoinState *pstate = hashtable->parallel_state;
3564 ParallelHashJoinBatchAccessor *batch = &hashtable->batches[batchno];
3565 size_t want = Max(size, HASH_CHUNK_SIZE - HASH_CHUNK_HEADER_SIZE);
3566
3567 Assert(batchno > 0);
3568 Assert(batchno < hashtable->nbatch);
3569 Assert(size == MAXALIGN(size));
3570
3571 LWLockAcquire(&pstate->lock, LW_EXCLUSIVE);
3572
3573 /* Has another participant commanded us to help grow? */
3574 if (pstate->growth == PHJ_GROWTH_NEED_MORE_BATCHES ||
3575 pstate->growth == PHJ_GROWTH_NEED_MORE_BUCKETS)
3576 {
3577 ParallelHashGrowth growth = pstate->growth;
3578
3579 LWLockRelease(&pstate->lock);
3580 if (growth == PHJ_GROWTH_NEED_MORE_BATCHES)
3581 ExecParallelHashIncreaseNumBatches(hashtable);
3582 else if (growth == PHJ_GROWTH_NEED_MORE_BUCKETS)
3583 ExecParallelHashIncreaseNumBuckets(hashtable);
3584
3585 return false;
3586 }
3587
3588 if (pstate->growth != PHJ_GROWTH_DISABLED &&
3589 batch->at_least_one_chunk &&
3590 (batch->shared->estimated_size + want + HASH_CHUNK_HEADER_SIZE
3591 > pstate->space_allowed))
3592 {
3593 /*
3594 * We have determined that this batch would exceed the space budget if
3595 * loaded into memory. Command all participants to help repartition.
3596 */
3597 batch->shared->space_exhausted = true;
3598 pstate->growth = PHJ_GROWTH_NEED_MORE_BATCHES;
3599 LWLockRelease(&pstate->lock);
3600
3601 return false;
3602 }
3603
3604 batch->at_least_one_chunk = true;
3605 batch->shared->estimated_size += want + HASH_CHUNK_HEADER_SIZE;
3606 batch->preallocated = want;
3607 LWLockRelease(&pstate->lock);
3608
3609 return true;
3610 }
3611
3612 /*
3613 * Calculate the limit on how much memory can be used by Hash and similar
3614 * plan types. This is work_mem times hash_mem_multiplier, and is
3615 * expressed in bytes.
3616 *
3617 * Exported for use by the planner, as well as other hash-like executor
3618 * nodes. This is a rather random place for this, but there is no better
3619 * place.
3620 */
3621 size_t
3622 get_hash_memory_limit(void)
3623 {
3624 double mem_limit;
3625
3626 /* Do initial calculation in double arithmetic */
3627 mem_limit = (double) work_mem * hash_mem_multiplier * 1024.0;
3628
3629 /* Clamp in case it doesn't fit in size_t */
3630 mem_limit = Min(mem_limit, (double) SIZE_MAX);
3631
3632 return (size_t) mem_limit;
3633 }