PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
nodeHash.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * nodeHash.c
4  * Routines to hash relations for hashjoin
5  *
6  * Portions Copyright (c) 1996-2017, 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  *-------------------------------------------------------------------------
14  */
15 /*
16  * INTERFACE ROUTINES
17  * MultiExecHash - generate an in-memory hash table of the relation
18  * ExecInitHash - initialize node and subnodes
19  * ExecEndHash - shutdown node and subnodes
20  */
21 
22 #include "postgres.h"
23 
24 #include <math.h>
25 #include <limits.h>
26 
27 #include "access/htup_details.h"
28 #include "catalog/pg_statistic.h"
29 #include "commands/tablespace.h"
30 #include "executor/execdebug.h"
31 #include "executor/hashjoin.h"
32 #include "executor/nodeHash.h"
33 #include "executor/nodeHashjoin.h"
34 #include "miscadmin.h"
35 #include "utils/dynahash.h"
36 #include "utils/memutils.h"
37 #include "utils/lsyscache.h"
38 #include "utils/syscache.h"
39 
40 
41 static void ExecHashIncreaseNumBatches(HashJoinTable hashtable);
42 static void ExecHashIncreaseNumBuckets(HashJoinTable hashtable);
43 static void ExecHashBuildSkewHash(HashJoinTable hashtable, Hash *node,
44  int mcvsToUse);
45 static void ExecHashSkewTableInsert(HashJoinTable hashtable,
46  TupleTableSlot *slot,
47  uint32 hashvalue,
48  int bucketNumber);
49 static void ExecHashRemoveNextSkewBucket(HashJoinTable hashtable);
50 
51 static void *dense_alloc(HashJoinTable hashtable, Size size);
52 
53 /* ----------------------------------------------------------------
54  * ExecHash
55  *
56  * stub for pro forma compliance
57  * ----------------------------------------------------------------
58  */
61 {
62  elog(ERROR, "Hash node does not support ExecProcNode call convention");
63  return NULL;
64 }
65 
66 /* ----------------------------------------------------------------
67  * MultiExecHash
68  *
69  * build hash table for hashjoin, doing partitioning if more
70  * than one batch is required.
71  * ----------------------------------------------------------------
72  */
73 Node *
75 {
76  PlanState *outerNode;
77  List *hashkeys;
78  HashJoinTable hashtable;
79  TupleTableSlot *slot;
80  ExprContext *econtext;
81  uint32 hashvalue;
82 
83  /* must provide our own instrumentation support */
84  if (node->ps.instrument)
86 
87  /*
88  * get state info from node
89  */
90  outerNode = outerPlanState(node);
91  hashtable = node->hashtable;
92 
93  /*
94  * set expression context
95  */
96  hashkeys = node->hashkeys;
97  econtext = node->ps.ps_ExprContext;
98 
99  /*
100  * get all inner tuples and insert into the hash table (or temp files)
101  */
102  for (;;)
103  {
104  slot = ExecProcNode(outerNode);
105  if (TupIsNull(slot))
106  break;
107  /* We have to compute the hash value */
108  econtext->ecxt_innertuple = slot;
109  if (ExecHashGetHashValue(hashtable, econtext, hashkeys,
110  false, hashtable->keepNulls,
111  &hashvalue))
112  {
113  int bucketNumber;
114 
115  bucketNumber = ExecHashGetSkewBucket(hashtable, hashvalue);
116  if (bucketNumber != INVALID_SKEW_BUCKET_NO)
117  {
118  /* It's a skew tuple, so put it into that hash table */
119  ExecHashSkewTableInsert(hashtable, slot, hashvalue,
120  bucketNumber);
121  hashtable->skewTuples += 1;
122  }
123  else
124  {
125  /* Not subject to skew optimization, so insert normally */
126  ExecHashTableInsert(hashtable, slot, hashvalue);
127  }
128  hashtable->totalTuples += 1;
129  }
130  }
131 
132  /* resize the hash table if needed (NTUP_PER_BUCKET exceeded) */
133  if (hashtable->nbuckets != hashtable->nbuckets_optimal)
134  ExecHashIncreaseNumBuckets(hashtable);
135 
136  /* Account for the buckets in spaceUsed (reported in EXPLAIN ANALYZE) */
137  hashtable->spaceUsed += hashtable->nbuckets * sizeof(HashJoinTuple);
138  if (hashtable->spaceUsed > hashtable->spacePeak)
139  hashtable->spacePeak = hashtable->spaceUsed;
140 
141  /* must provide our own instrumentation support */
142  if (node->ps.instrument)
143  InstrStopNode(node->ps.instrument, hashtable->totalTuples);
144 
145  /*
146  * We do not return the hash table directly because it's not a subtype of
147  * Node, and so would violate the MultiExecProcNode API. Instead, our
148  * parent Hashjoin node is expected to know how to fish it out of our node
149  * state. Ugly but not really worth cleaning up, since Hashjoin knows
150  * quite a bit more about Hash besides that.
151  */
152  return NULL;
153 }
154 
155 /* ----------------------------------------------------------------
156  * ExecInitHash
157  *
158  * Init routine for Hash node
159  * ----------------------------------------------------------------
160  */
161 HashState *
162 ExecInitHash(Hash *node, EState *estate, int eflags)
163 {
164  HashState *hashstate;
165 
166  /* check for unsupported flags */
167  Assert(!(eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)));
168 
169  /*
170  * create state structure
171  */
172  hashstate = makeNode(HashState);
173  hashstate->ps.plan = (Plan *) node;
174  hashstate->ps.state = estate;
175  hashstate->hashtable = NULL;
176  hashstate->hashkeys = NIL; /* will be set by parent HashJoin */
177 
178  /*
179  * Miscellaneous initialization
180  *
181  * create expression context for node
182  */
183  ExecAssignExprContext(estate, &hashstate->ps);
184 
185  /*
186  * initialize our result slot
187  */
188  ExecInitResultTupleSlot(estate, &hashstate->ps);
189 
190  /*
191  * initialize child expressions
192  */
193  hashstate->ps.targetlist = (List *)
194  ExecInitExpr((Expr *) node->plan.targetlist,
195  (PlanState *) hashstate);
196  hashstate->ps.qual = (List *)
197  ExecInitExpr((Expr *) node->plan.qual,
198  (PlanState *) hashstate);
199 
200  /*
201  * initialize child nodes
202  */
203  outerPlanState(hashstate) = ExecInitNode(outerPlan(node), estate, eflags);
204 
205  /*
206  * initialize tuple type. no need to initialize projection info because
207  * this node doesn't do projections
208  */
209  ExecAssignResultTypeFromTL(&hashstate->ps);
210  hashstate->ps.ps_ProjInfo = NULL;
211 
212  return hashstate;
213 }
214 
215 /* ---------------------------------------------------------------
216  * ExecEndHash
217  *
218  * clean up routine for Hash node
219  * ----------------------------------------------------------------
220  */
221 void
223 {
225 
226  /*
227  * free exprcontext
228  */
229  ExecFreeExprContext(&node->ps);
230 
231  /*
232  * shut down the subplan
233  */
234  outerPlan = outerPlanState(node);
235  ExecEndNode(outerPlan);
236 }
237 
238 
239 /* ----------------------------------------------------------------
240  * ExecHashTableCreate
241  *
242  * create an empty hashtable data structure for hashjoin.
243  * ----------------------------------------------------------------
244  */
246 ExecHashTableCreate(Hash *node, List *hashOperators, bool keepNulls)
247 {
248  HashJoinTable hashtable;
249  Plan *outerNode;
250  int nbuckets;
251  int nbatch;
252  int num_skew_mcvs;
253  int log2_nbuckets;
254  int nkeys;
255  int i;
256  ListCell *ho;
257  MemoryContext oldcxt;
258 
259  /*
260  * Get information about the size of the relation to be hashed (it's the
261  * "outer" subtree of this node, but the inner relation of the hashjoin).
262  * Compute the appropriate size of the hash table.
263  */
264  outerNode = outerPlan(node);
265 
266  ExecChooseHashTableSize(outerNode->plan_rows, outerNode->plan_width,
267  OidIsValid(node->skewTable),
268  &nbuckets, &nbatch, &num_skew_mcvs);
269 
270  /* nbuckets must be a power of 2 */
271  log2_nbuckets = my_log2(nbuckets);
272  Assert(nbuckets == (1 << log2_nbuckets));
273 
274  /*
275  * Initialize the hash table control block.
276  *
277  * The hashtable control block is just palloc'd from the executor's
278  * per-query memory context.
279  */
280  hashtable = (HashJoinTable) palloc(sizeof(HashJoinTableData));
281  hashtable->nbuckets = nbuckets;
282  hashtable->nbuckets_original = nbuckets;
283  hashtable->nbuckets_optimal = nbuckets;
284  hashtable->log2_nbuckets = log2_nbuckets;
285  hashtable->log2_nbuckets_optimal = log2_nbuckets;
286  hashtable->buckets = NULL;
287  hashtable->keepNulls = keepNulls;
288  hashtable->skewEnabled = false;
289  hashtable->skewBucket = NULL;
290  hashtable->skewBucketLen = 0;
291  hashtable->nSkewBuckets = 0;
292  hashtable->skewBucketNums = NULL;
293  hashtable->nbatch = nbatch;
294  hashtable->curbatch = 0;
295  hashtable->nbatch_original = nbatch;
296  hashtable->nbatch_outstart = nbatch;
297  hashtable->growEnabled = true;
298  hashtable->totalTuples = 0;
299  hashtable->skewTuples = 0;
300  hashtable->innerBatchFile = NULL;
301  hashtable->outerBatchFile = NULL;
302  hashtable->spaceUsed = 0;
303  hashtable->spacePeak = 0;
304  hashtable->spaceAllowed = work_mem * 1024L;
305  hashtable->spaceUsedSkew = 0;
306  hashtable->spaceAllowedSkew =
307  hashtable->spaceAllowed * SKEW_WORK_MEM_PERCENT / 100;
308  hashtable->chunks = NULL;
309 
310 #ifdef HJDEBUG
311  printf("Hashjoin %p: initial nbatch = %d, nbuckets = %d\n",
312  hashtable, nbatch, nbuckets);
313 #endif
314 
315  /*
316  * Get info about the hash functions to be used for each hash key. Also
317  * remember whether the join operators are strict.
318  */
319  nkeys = list_length(hashOperators);
320  hashtable->outer_hashfunctions =
321  (FmgrInfo *) palloc(nkeys * sizeof(FmgrInfo));
322  hashtable->inner_hashfunctions =
323  (FmgrInfo *) palloc(nkeys * sizeof(FmgrInfo));
324  hashtable->hashStrict = (bool *) palloc(nkeys * sizeof(bool));
325  i = 0;
326  foreach(ho, hashOperators)
327  {
328  Oid hashop = lfirst_oid(ho);
329  Oid left_hashfn;
330  Oid right_hashfn;
331 
332  if (!get_op_hash_functions(hashop, &left_hashfn, &right_hashfn))
333  elog(ERROR, "could not find hash function for hash operator %u",
334  hashop);
335  fmgr_info(left_hashfn, &hashtable->outer_hashfunctions[i]);
336  fmgr_info(right_hashfn, &hashtable->inner_hashfunctions[i]);
337  hashtable->hashStrict[i] = op_strict(hashop);
338  i++;
339  }
340 
341  /*
342  * Create temporary memory contexts in which to keep the hashtable working
343  * storage. See notes in executor/hashjoin.h.
344  */
346  "HashTableContext",
348 
349  hashtable->batchCxt = AllocSetContextCreate(hashtable->hashCxt,
350  "HashBatchContext",
352 
353  /* Allocate data that will live for the life of the hashjoin */
354 
355  oldcxt = MemoryContextSwitchTo(hashtable->hashCxt);
356 
357  if (nbatch > 1)
358  {
359  /*
360  * allocate and initialize the file arrays in hashCxt
361  */
362  hashtable->innerBatchFile = (BufFile **)
363  palloc0(nbatch * sizeof(BufFile *));
364  hashtable->outerBatchFile = (BufFile **)
365  palloc0(nbatch * sizeof(BufFile *));
366  /* The files will not be opened until needed... */
367  /* ... but make sure we have temp tablespaces established for them */
369  }
370 
371  /*
372  * Prepare context for the first-scan space allocations; allocate the
373  * hashbucket array therein, and set each bucket "empty".
374  */
375  MemoryContextSwitchTo(hashtable->batchCxt);
376 
377  hashtable->buckets = (HashJoinTuple *)
378  palloc0(nbuckets * sizeof(HashJoinTuple));
379 
380  /*
381  * Set up for skew optimization, if possible and there's a need for more
382  * than one batch. (In a one-batch join, there's no point in it.)
383  */
384  if (nbatch > 1)
385  ExecHashBuildSkewHash(hashtable, node, num_skew_mcvs);
386 
387  MemoryContextSwitchTo(oldcxt);
388 
389  return hashtable;
390 }
391 
392 
393 /*
394  * Compute appropriate size for hashtable given the estimated size of the
395  * relation to be hashed (number of rows and average row width).
396  *
397  * This is exported so that the planner's costsize.c can use it.
398  */
399 
400 /* Target bucket loading (tuples per bucket) */
401 #define NTUP_PER_BUCKET 1
402 
403 void
404 ExecChooseHashTableSize(double ntuples, int tupwidth, bool useskew,
405  int *numbuckets,
406  int *numbatches,
407  int *num_skew_mcvs)
408 {
409  int tupsize;
410  double inner_rel_bytes;
411  long bucket_bytes;
412  long hash_table_bytes;
413  long skew_table_bytes;
414  long max_pointers;
415  long mppow2;
416  int nbatch = 1;
417  int nbuckets;
418  double dbuckets;
419 
420  /* Force a plausible relation size if no info */
421  if (ntuples <= 0.0)
422  ntuples = 1000.0;
423 
424  /*
425  * Estimate tupsize based on footprint of tuple in hashtable... note this
426  * does not allow for any palloc overhead. The manipulations of spaceUsed
427  * don't count palloc overhead either.
428  */
429  tupsize = HJTUPLE_OVERHEAD +
431  MAXALIGN(tupwidth);
432  inner_rel_bytes = ntuples * tupsize;
433 
434  /*
435  * Target in-memory hashtable size is work_mem kilobytes.
436  */
437  hash_table_bytes = work_mem * 1024L;
438 
439  /*
440  * If skew optimization is possible, estimate the number of skew buckets
441  * that will fit in the memory allowed, and decrement the assumed space
442  * available for the main hash table accordingly.
443  *
444  * We make the optimistic assumption that each skew bucket will contain
445  * one inner-relation tuple. If that turns out to be low, we will recover
446  * at runtime by reducing the number of skew buckets.
447  *
448  * hashtable->skewBucket will have up to 8 times as many HashSkewBucket
449  * pointers as the number of MCVs we allow, since ExecHashBuildSkewHash
450  * will round up to the next power of 2 and then multiply by 4 to reduce
451  * collisions.
452  */
453  if (useskew)
454  {
455  skew_table_bytes = hash_table_bytes * SKEW_WORK_MEM_PERCENT / 100;
456 
457  /*----------
458  * Divisor is:
459  * size of a hash tuple +
460  * worst-case size of skewBucket[] per MCV +
461  * size of skewBucketNums[] entry +
462  * size of skew bucket struct itself
463  *----------
464  */
465  *num_skew_mcvs = skew_table_bytes / (tupsize +
466  (8 * sizeof(HashSkewBucket *)) +
467  sizeof(int) +
469  if (*num_skew_mcvs > 0)
470  hash_table_bytes -= skew_table_bytes;
471  }
472  else
473  *num_skew_mcvs = 0;
474 
475  /*
476  * Set nbuckets to achieve an average bucket load of NTUP_PER_BUCKET when
477  * memory is filled, assuming a single batch; but limit the value so that
478  * the pointer arrays we'll try to allocate do not exceed work_mem nor
479  * MaxAllocSize.
480  *
481  * Note that both nbuckets and nbatch must be powers of 2 to make
482  * ExecHashGetBucketAndBatch fast.
483  */
484  max_pointers = (work_mem * 1024L) / sizeof(HashJoinTuple);
485  max_pointers = Min(max_pointers, MaxAllocSize / sizeof(HashJoinTuple));
486  /* If max_pointers isn't a power of 2, must round it down to one */
487  mppow2 = 1L << my_log2(max_pointers);
488  if (max_pointers != mppow2)
489  max_pointers = mppow2 / 2;
490 
491  /* Also ensure we avoid integer overflow in nbatch and nbuckets */
492  /* (this step is redundant given the current value of MaxAllocSize) */
493  max_pointers = Min(max_pointers, INT_MAX / 2);
494 
495  dbuckets = ceil(ntuples / NTUP_PER_BUCKET);
496  dbuckets = Min(dbuckets, max_pointers);
497  nbuckets = (int) dbuckets;
498  /* don't let nbuckets be really small, though ... */
499  nbuckets = Max(nbuckets, 1024);
500  /* ... and force it to be a power of 2. */
501  nbuckets = 1 << my_log2(nbuckets);
502 
503  /*
504  * If there's not enough space to store the projected number of tuples and
505  * the required bucket headers, we will need multiple batches.
506  */
507  bucket_bytes = sizeof(HashJoinTuple) * nbuckets;
508  if (inner_rel_bytes + bucket_bytes > hash_table_bytes)
509  {
510  /* We'll need multiple batches */
511  long lbuckets;
512  double dbatch;
513  int minbatch;
514  long bucket_size;
515 
516  /*
517  * Estimate the number of buckets we'll want to have when work_mem is
518  * entirely full. Each bucket will contain a bucket pointer plus
519  * NTUP_PER_BUCKET tuples, whose projected size already includes
520  * overhead for the hash code, pointer to the next tuple, etc.
521  */
522  bucket_size = (tupsize * NTUP_PER_BUCKET + sizeof(HashJoinTuple));
523  lbuckets = 1L << my_log2(hash_table_bytes / bucket_size);
524  lbuckets = Min(lbuckets, max_pointers);
525  nbuckets = (int) lbuckets;
526  nbuckets = 1 << my_log2(nbuckets);
527  bucket_bytes = nbuckets * sizeof(HashJoinTuple);
528 
529  /*
530  * Buckets are simple pointers to hashjoin tuples, while tupsize
531  * includes the pointer, hash code, and MinimalTupleData. So buckets
532  * should never really exceed 25% of work_mem (even for
533  * NTUP_PER_BUCKET=1); except maybe for work_mem values that are not
534  * 2^N bytes, where we might get more because of doubling. So let's
535  * look for 50% here.
536  */
537  Assert(bucket_bytes <= hash_table_bytes / 2);
538 
539  /* Calculate required number of batches. */
540  dbatch = ceil(inner_rel_bytes / (hash_table_bytes - bucket_bytes));
541  dbatch = Min(dbatch, max_pointers);
542  minbatch = (int) dbatch;
543  nbatch = 2;
544  while (nbatch < minbatch)
545  nbatch <<= 1;
546  }
547 
548  Assert(nbuckets > 0);
549  Assert(nbatch > 0);
550 
551  *numbuckets = nbuckets;
552  *numbatches = nbatch;
553 }
554 
555 
556 /* ----------------------------------------------------------------
557  * ExecHashTableDestroy
558  *
559  * destroy a hash table
560  * ----------------------------------------------------------------
561  */
562 void
564 {
565  int i;
566 
567  /*
568  * Make sure all the temp files are closed. We skip batch 0, since it
569  * can't have any temp files (and the arrays might not even exist if
570  * nbatch is only 1).
571  */
572  for (i = 1; i < hashtable->nbatch; i++)
573  {
574  if (hashtable->innerBatchFile[i])
575  BufFileClose(hashtable->innerBatchFile[i]);
576  if (hashtable->outerBatchFile[i])
577  BufFileClose(hashtable->outerBatchFile[i]);
578  }
579 
580  /* Release working memory (batchCxt is a child, so it goes away too) */
581  MemoryContextDelete(hashtable->hashCxt);
582 
583  /* And drop the control block */
584  pfree(hashtable);
585 }
586 
587 /*
588  * ExecHashIncreaseNumBatches
589  * increase the original number of batches in order to reduce
590  * current memory consumption
591  */
592 static void
594 {
595  int oldnbatch = hashtable->nbatch;
596  int curbatch = hashtable->curbatch;
597  int nbatch;
598  MemoryContext oldcxt;
599  long ninmemory;
600  long nfreed;
601  HashMemoryChunk oldchunks;
602 
603  /* do nothing if we've decided to shut off growth */
604  if (!hashtable->growEnabled)
605  return;
606 
607  /* safety check to avoid overflow */
608  if (oldnbatch > Min(INT_MAX / 2, MaxAllocSize / (sizeof(void *) * 2)))
609  return;
610 
611  nbatch = oldnbatch * 2;
612  Assert(nbatch > 1);
613 
614 #ifdef HJDEBUG
615  printf("Hashjoin %p: increasing nbatch to %d because space = %zu\n",
616  hashtable, nbatch, hashtable->spaceUsed);
617 #endif
618 
619  oldcxt = MemoryContextSwitchTo(hashtable->hashCxt);
620 
621  if (hashtable->innerBatchFile == NULL)
622  {
623  /* we had no file arrays before */
624  hashtable->innerBatchFile = (BufFile **)
625  palloc0(nbatch * sizeof(BufFile *));
626  hashtable->outerBatchFile = (BufFile **)
627  palloc0(nbatch * sizeof(BufFile *));
628  /* time to establish the temp tablespaces, too */
630  }
631  else
632  {
633  /* enlarge arrays and zero out added entries */
634  hashtable->innerBatchFile = (BufFile **)
635  repalloc(hashtable->innerBatchFile, nbatch * sizeof(BufFile *));
636  hashtable->outerBatchFile = (BufFile **)
637  repalloc(hashtable->outerBatchFile, nbatch * sizeof(BufFile *));
638  MemSet(hashtable->innerBatchFile + oldnbatch, 0,
639  (nbatch - oldnbatch) * sizeof(BufFile *));
640  MemSet(hashtable->outerBatchFile + oldnbatch, 0,
641  (nbatch - oldnbatch) * sizeof(BufFile *));
642  }
643 
644  MemoryContextSwitchTo(oldcxt);
645 
646  hashtable->nbatch = nbatch;
647 
648  /*
649  * Scan through the existing hash table entries and dump out any that are
650  * no longer of the current batch.
651  */
652  ninmemory = nfreed = 0;
653 
654  /* If know we need to resize nbuckets, we can do it while rebatching. */
655  if (hashtable->nbuckets_optimal != hashtable->nbuckets)
656  {
657  /* we never decrease the number of buckets */
658  Assert(hashtable->nbuckets_optimal > hashtable->nbuckets);
659 
660  hashtable->nbuckets = hashtable->nbuckets_optimal;
661  hashtable->log2_nbuckets = hashtable->log2_nbuckets_optimal;
662 
663  hashtable->buckets = repalloc(hashtable->buckets,
664  sizeof(HashJoinTuple) * hashtable->nbuckets);
665  }
666 
667  /*
668  * We will scan through the chunks directly, so that we can reset the
669  * buckets now and not have to keep track which tuples in the buckets have
670  * already been processed. We will free the old chunks as we go.
671  */
672  memset(hashtable->buckets, 0, sizeof(HashJoinTuple) * hashtable->nbuckets);
673  oldchunks = hashtable->chunks;
674  hashtable->chunks = NULL;
675 
676  /* so, let's scan through the old chunks, and all tuples in each chunk */
677  while (oldchunks != NULL)
678  {
679  HashMemoryChunk nextchunk = oldchunks->next;
680 
681  /* position within the buffer (up to oldchunks->used) */
682  size_t idx = 0;
683 
684  /* process all tuples stored in this chunk (and then free it) */
685  while (idx < oldchunks->used)
686  {
687  HashJoinTuple hashTuple = (HashJoinTuple) (oldchunks->data + idx);
688  MinimalTuple tuple = HJTUPLE_MINTUPLE(hashTuple);
689  int hashTupleSize = (HJTUPLE_OVERHEAD + tuple->t_len);
690  int bucketno;
691  int batchno;
692 
693  ninmemory++;
694  ExecHashGetBucketAndBatch(hashtable, hashTuple->hashvalue,
695  &bucketno, &batchno);
696 
697  if (batchno == curbatch)
698  {
699  /* keep tuple in memory - copy it into the new chunk */
700  HashJoinTuple copyTuple;
701 
702  copyTuple = (HashJoinTuple) dense_alloc(hashtable, hashTupleSize);
703  memcpy(copyTuple, hashTuple, hashTupleSize);
704 
705  /* and add it back to the appropriate bucket */
706  copyTuple->next = hashtable->buckets[bucketno];
707  hashtable->buckets[bucketno] = copyTuple;
708  }
709  else
710  {
711  /* dump it out */
712  Assert(batchno > curbatch);
714  hashTuple->hashvalue,
715  &hashtable->innerBatchFile[batchno]);
716 
717  hashtable->spaceUsed -= hashTupleSize;
718  nfreed++;
719  }
720 
721  /* next tuple in this chunk */
722  idx += MAXALIGN(hashTupleSize);
723 
724  /* allow this loop to be cancellable */
726  }
727 
728  /* we're done with this chunk - free it and proceed to the next one */
729  pfree(oldchunks);
730  oldchunks = nextchunk;
731  }
732 
733 #ifdef HJDEBUG
734  printf("Hashjoin %p: freed %ld of %ld tuples, space now %zu\n",
735  hashtable, nfreed, ninmemory, hashtable->spaceUsed);
736 #endif
737 
738  /*
739  * If we dumped out either all or none of the tuples in the table, disable
740  * further expansion of nbatch. This situation implies that we have
741  * enough tuples of identical hashvalues to overflow spaceAllowed.
742  * Increasing nbatch will not fix it since there's no way to subdivide the
743  * group any more finely. We have to just gut it out and hope the server
744  * has enough RAM.
745  */
746  if (nfreed == 0 || nfreed == ninmemory)
747  {
748  hashtable->growEnabled = false;
749 #ifdef HJDEBUG
750  printf("Hashjoin %p: disabling further increase of nbatch\n",
751  hashtable);
752 #endif
753  }
754 }
755 
756 /*
757  * ExecHashIncreaseNumBuckets
758  * increase the original number of buckets in order to reduce
759  * number of tuples per bucket
760  */
761 static void
763 {
764  HashMemoryChunk chunk;
765 
766  /* do nothing if not an increase (it's called increase for a reason) */
767  if (hashtable->nbuckets >= hashtable->nbuckets_optimal)
768  return;
769 
770 #ifdef HJDEBUG
771  printf("Hashjoin %p: increasing nbuckets %d => %d\n",
772  hashtable, hashtable->nbuckets, hashtable->nbuckets_optimal);
773 #endif
774 
775  hashtable->nbuckets = hashtable->nbuckets_optimal;
776  hashtable->log2_nbuckets = hashtable->log2_nbuckets_optimal;
777 
778  Assert(hashtable->nbuckets > 1);
779  Assert(hashtable->nbuckets <= (INT_MAX / 2));
780  Assert(hashtable->nbuckets == (1 << hashtable->log2_nbuckets));
781 
782  /*
783  * Just reallocate the proper number of buckets - we don't need to walk
784  * through them - we can walk the dense-allocated chunks (just like in
785  * ExecHashIncreaseNumBatches, but without all the copying into new
786  * chunks)
787  */
788  hashtable->buckets =
789  (HashJoinTuple *) repalloc(hashtable->buckets,
790  hashtable->nbuckets * sizeof(HashJoinTuple));
791 
792  memset(hashtable->buckets, 0, hashtable->nbuckets * sizeof(HashJoinTuple));
793 
794  /* scan through all tuples in all chunks to rebuild the hash table */
795  for (chunk = hashtable->chunks; chunk != NULL; chunk = chunk->next)
796  {
797  /* process all tuples stored in this chunk */
798  size_t idx = 0;
799 
800  while (idx < chunk->used)
801  {
802  HashJoinTuple hashTuple = (HashJoinTuple) (chunk->data + idx);
803  int bucketno;
804  int batchno;
805 
806  ExecHashGetBucketAndBatch(hashtable, hashTuple->hashvalue,
807  &bucketno, &batchno);
808 
809  /* add the tuple to the proper bucket */
810  hashTuple->next = hashtable->buckets[bucketno];
811  hashtable->buckets[bucketno] = hashTuple;
812 
813  /* advance index past the tuple */
814  idx += MAXALIGN(HJTUPLE_OVERHEAD +
815  HJTUPLE_MINTUPLE(hashTuple)->t_len);
816  }
817  }
818 }
819 
820 
821 /*
822  * ExecHashTableInsert
823  * insert a tuple into the hash table depending on the hash value
824  * it may just go to a temp file for later batches
825  *
826  * Note: the passed TupleTableSlot may contain a regular, minimal, or virtual
827  * tuple; the minimal case in particular is certain to happen while reloading
828  * tuples from batch files. We could save some cycles in the regular-tuple
829  * case by not forcing the slot contents into minimal form; not clear if it's
830  * worth the messiness required.
831  */
832 void
834  TupleTableSlot *slot,
835  uint32 hashvalue)
836 {
838  int bucketno;
839  int batchno;
840 
841  ExecHashGetBucketAndBatch(hashtable, hashvalue,
842  &bucketno, &batchno);
843 
844  /*
845  * decide whether to put the tuple in the hash table or a temp file
846  */
847  if (batchno == hashtable->curbatch)
848  {
849  /*
850  * put the tuple in hash table
851  */
852  HashJoinTuple hashTuple;
853  int hashTupleSize;
854  double ntuples = (hashtable->totalTuples - hashtable->skewTuples);
855 
856  /* Create the HashJoinTuple */
857  hashTupleSize = HJTUPLE_OVERHEAD + tuple->t_len;
858  hashTuple = (HashJoinTuple) dense_alloc(hashtable, hashTupleSize);
859 
860  hashTuple->hashvalue = hashvalue;
861  memcpy(HJTUPLE_MINTUPLE(hashTuple), tuple, tuple->t_len);
862 
863  /*
864  * We always reset the tuple-matched flag on insertion. This is okay
865  * even when reloading a tuple from a batch file, since the tuple
866  * could not possibly have been matched to an outer tuple before it
867  * went into the batch file.
868  */
870 
871  /* Push it onto the front of the bucket's list */
872  hashTuple->next = hashtable->buckets[bucketno];
873  hashtable->buckets[bucketno] = hashTuple;
874 
875  /*
876  * Increase the (optimal) number of buckets if we just exceeded the
877  * NTUP_PER_BUCKET threshold, but only when there's still a single
878  * batch.
879  */
880  if (hashtable->nbatch == 1 &&
881  ntuples > (hashtable->nbuckets_optimal * NTUP_PER_BUCKET))
882  {
883  /* Guard against integer overflow and alloc size overflow */
884  if (hashtable->nbuckets_optimal <= INT_MAX / 2 &&
885  hashtable->nbuckets_optimal * 2 <= MaxAllocSize / sizeof(HashJoinTuple))
886  {
887  hashtable->nbuckets_optimal *= 2;
888  hashtable->log2_nbuckets_optimal += 1;
889  }
890  }
891 
892  /* Account for space used, and back off if we've used too much */
893  hashtable->spaceUsed += hashTupleSize;
894  if (hashtable->spaceUsed > hashtable->spacePeak)
895  hashtable->spacePeak = hashtable->spaceUsed;
896  if (hashtable->spaceUsed +
897  hashtable->nbuckets_optimal * sizeof(HashJoinTuple)
898  > hashtable->spaceAllowed)
899  ExecHashIncreaseNumBatches(hashtable);
900  }
901  else
902  {
903  /*
904  * put the tuple into a temp file for later batches
905  */
906  Assert(batchno > hashtable->curbatch);
907  ExecHashJoinSaveTuple(tuple,
908  hashvalue,
909  &hashtable->innerBatchFile[batchno]);
910  }
911 }
912 
913 /*
914  * ExecHashGetHashValue
915  * Compute the hash value for a tuple
916  *
917  * The tuple to be tested must be in either econtext->ecxt_outertuple or
918  * econtext->ecxt_innertuple. Vars in the hashkeys expressions should have
919  * varno either OUTER_VAR or INNER_VAR.
920  *
921  * A TRUE result means the tuple's hash value has been successfully computed
922  * and stored at *hashvalue. A FALSE result means the tuple cannot match
923  * because it contains a null attribute, and hence it should be discarded
924  * immediately. (If keep_nulls is true then FALSE is never returned.)
925  */
926 bool
928  ExprContext *econtext,
929  List *hashkeys,
930  bool outer_tuple,
931  bool keep_nulls,
932  uint32 *hashvalue)
933 {
934  uint32 hashkey = 0;
935  FmgrInfo *hashfunctions;
936  ListCell *hk;
937  int i = 0;
938  MemoryContext oldContext;
939 
940  /*
941  * We reset the eval context each time to reclaim any memory leaked in the
942  * hashkey expressions.
943  */
944  ResetExprContext(econtext);
945 
946  oldContext = MemoryContextSwitchTo(econtext->ecxt_per_tuple_memory);
947 
948  if (outer_tuple)
949  hashfunctions = hashtable->outer_hashfunctions;
950  else
951  hashfunctions = hashtable->inner_hashfunctions;
952 
953  foreach(hk, hashkeys)
954  {
955  ExprState *keyexpr = (ExprState *) lfirst(hk);
956  Datum keyval;
957  bool isNull;
958 
959  /* rotate hashkey left 1 bit at each step */
960  hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0);
961 
962  /*
963  * Get the join attribute value of the tuple
964  */
965  keyval = ExecEvalExpr(keyexpr, econtext, &isNull);
966 
967  /*
968  * If the attribute is NULL, and the join operator is strict, then
969  * this tuple cannot pass the join qual so we can reject it
970  * immediately (unless we're scanning the outside of an outer join, in
971  * which case we must not reject it). Otherwise we act like the
972  * hashcode of NULL is zero (this will support operators that act like
973  * IS NOT DISTINCT, though not any more-random behavior). We treat
974  * the hash support function as strict even if the operator is not.
975  *
976  * Note: currently, all hashjoinable operators must be strict since
977  * the hash index AM assumes that. However, it takes so little extra
978  * code here to allow non-strict that we may as well do it.
979  */
980  if (isNull)
981  {
982  if (hashtable->hashStrict[i] && !keep_nulls)
983  {
984  MemoryContextSwitchTo(oldContext);
985  return false; /* cannot match */
986  }
987  /* else, leave hashkey unmodified, equivalent to hashcode 0 */
988  }
989  else
990  {
991  /* Compute the hash function */
992  uint32 hkey;
993 
994  hkey = DatumGetUInt32(FunctionCall1(&hashfunctions[i], keyval));
995  hashkey ^= hkey;
996  }
997 
998  i++;
999  }
1000 
1001  MemoryContextSwitchTo(oldContext);
1002 
1003  *hashvalue = hashkey;
1004  return true;
1005 }
1006 
1007 /*
1008  * ExecHashGetBucketAndBatch
1009  * Determine the bucket number and batch number for a hash value
1010  *
1011  * Note: on-the-fly increases of nbatch must not change the bucket number
1012  * for a given hash code (since we don't move tuples to different hash
1013  * chains), and must only cause the batch number to remain the same or
1014  * increase. Our algorithm is
1015  * bucketno = hashvalue MOD nbuckets
1016  * batchno = (hashvalue DIV nbuckets) MOD nbatch
1017  * where nbuckets and nbatch are both expected to be powers of 2, so we can
1018  * do the computations by shifting and masking. (This assumes that all hash
1019  * functions are good about randomizing all their output bits, else we are
1020  * likely to have very skewed bucket or batch occupancy.)
1021  *
1022  * nbuckets and log2_nbuckets may change while nbatch == 1 because of dynamic
1023  * bucket count growth. Once we start batching, the value is fixed and does
1024  * not change over the course of the join (making it possible to compute batch
1025  * number the way we do here).
1026  *
1027  * nbatch is always a power of 2; we increase it only by doubling it. This
1028  * effectively adds one more bit to the top of the batchno.
1029  */
1030 void
1032  uint32 hashvalue,
1033  int *bucketno,
1034  int *batchno)
1035 {
1036  uint32 nbuckets = (uint32) hashtable->nbuckets;
1037  uint32 nbatch = (uint32) hashtable->nbatch;
1038 
1039  if (nbatch > 1)
1040  {
1041  /* we can do MOD by masking, DIV by shifting */
1042  *bucketno = hashvalue & (nbuckets - 1);
1043  *batchno = (hashvalue >> hashtable->log2_nbuckets) & (nbatch - 1);
1044  }
1045  else
1046  {
1047  *bucketno = hashvalue & (nbuckets - 1);
1048  *batchno = 0;
1049  }
1050 }
1051 
1052 /*
1053  * ExecScanHashBucket
1054  * scan a hash bucket for matches to the current outer tuple
1055  *
1056  * The current outer tuple must be stored in econtext->ecxt_outertuple.
1057  *
1058  * On success, the inner tuple is stored into hjstate->hj_CurTuple and
1059  * econtext->ecxt_innertuple, using hjstate->hj_HashTupleSlot as the slot
1060  * for the latter.
1061  */
1062 bool
1064  ExprContext *econtext)
1065 {
1066  List *hjclauses = hjstate->hashclauses;
1067  HashJoinTable hashtable = hjstate->hj_HashTable;
1068  HashJoinTuple hashTuple = hjstate->hj_CurTuple;
1069  uint32 hashvalue = hjstate->hj_CurHashValue;
1070 
1071  /*
1072  * hj_CurTuple is the address of the tuple last returned from the current
1073  * bucket, or NULL if it's time to start scanning a new bucket.
1074  *
1075  * If the tuple hashed to a skew bucket then scan the skew bucket
1076  * otherwise scan the standard hashtable bucket.
1077  */
1078  if (hashTuple != NULL)
1079  hashTuple = hashTuple->next;
1080  else if (hjstate->hj_CurSkewBucketNo != INVALID_SKEW_BUCKET_NO)
1081  hashTuple = hashtable->skewBucket[hjstate->hj_CurSkewBucketNo]->tuples;
1082  else
1083  hashTuple = hashtable->buckets[hjstate->hj_CurBucketNo];
1084 
1085  while (hashTuple != NULL)
1086  {
1087  if (hashTuple->hashvalue == hashvalue)
1088  {
1089  TupleTableSlot *inntuple;
1090 
1091  /* insert hashtable's tuple into exec slot so ExecQual sees it */
1092  inntuple = ExecStoreMinimalTuple(HJTUPLE_MINTUPLE(hashTuple),
1093  hjstate->hj_HashTupleSlot,
1094  false); /* do not pfree */
1095  econtext->ecxt_innertuple = inntuple;
1096 
1097  /* reset temp memory each time to avoid leaks from qual expr */
1098  ResetExprContext(econtext);
1099 
1100  if (ExecQual(hjclauses, econtext, false))
1101  {
1102  hjstate->hj_CurTuple = hashTuple;
1103  return true;
1104  }
1105  }
1106 
1107  hashTuple = hashTuple->next;
1108  }
1109 
1110  /*
1111  * no match
1112  */
1113  return false;
1114 }
1115 
1116 /*
1117  * ExecPrepHashTableForUnmatched
1118  * set up for a series of ExecScanHashTableForUnmatched calls
1119  */
1120 void
1122 {
1123  /*----------
1124  * During this scan we use the HashJoinState fields as follows:
1125  *
1126  * hj_CurBucketNo: next regular bucket to scan
1127  * hj_CurSkewBucketNo: next skew bucket (an index into skewBucketNums)
1128  * hj_CurTuple: last tuple returned, or NULL to start next bucket
1129  *----------
1130  */
1131  hjstate->hj_CurBucketNo = 0;
1132  hjstate->hj_CurSkewBucketNo = 0;
1133  hjstate->hj_CurTuple = NULL;
1134 }
1135 
1136 /*
1137  * ExecScanHashTableForUnmatched
1138  * scan the hash table for unmatched inner tuples
1139  *
1140  * On success, the inner tuple is stored into hjstate->hj_CurTuple and
1141  * econtext->ecxt_innertuple, using hjstate->hj_HashTupleSlot as the slot
1142  * for the latter.
1143  */
1144 bool
1146 {
1147  HashJoinTable hashtable = hjstate->hj_HashTable;
1148  HashJoinTuple hashTuple = hjstate->hj_CurTuple;
1149 
1150  for (;;)
1151  {
1152  /*
1153  * hj_CurTuple is the address of the tuple last returned from the
1154  * current bucket, or NULL if it's time to start scanning a new
1155  * bucket.
1156  */
1157  if (hashTuple != NULL)
1158  hashTuple = hashTuple->next;
1159  else if (hjstate->hj_CurBucketNo < hashtable->nbuckets)
1160  {
1161  hashTuple = hashtable->buckets[hjstate->hj_CurBucketNo];
1162  hjstate->hj_CurBucketNo++;
1163  }
1164  else if (hjstate->hj_CurSkewBucketNo < hashtable->nSkewBuckets)
1165  {
1166  int j = hashtable->skewBucketNums[hjstate->hj_CurSkewBucketNo];
1167 
1168  hashTuple = hashtable->skewBucket[j]->tuples;
1169  hjstate->hj_CurSkewBucketNo++;
1170  }
1171  else
1172  break; /* finished all buckets */
1173 
1174  while (hashTuple != NULL)
1175  {
1176  if (!HeapTupleHeaderHasMatch(HJTUPLE_MINTUPLE(hashTuple)))
1177  {
1178  TupleTableSlot *inntuple;
1179 
1180  /* insert hashtable's tuple into exec slot */
1181  inntuple = ExecStoreMinimalTuple(HJTUPLE_MINTUPLE(hashTuple),
1182  hjstate->hj_HashTupleSlot,
1183  false); /* do not pfree */
1184  econtext->ecxt_innertuple = inntuple;
1185 
1186  /*
1187  * Reset temp memory each time; although this function doesn't
1188  * do any qual eval, the caller will, so let's keep it
1189  * parallel to ExecScanHashBucket.
1190  */
1191  ResetExprContext(econtext);
1192 
1193  hjstate->hj_CurTuple = hashTuple;
1194  return true;
1195  }
1196 
1197  hashTuple = hashTuple->next;
1198  }
1199  }
1200 
1201  /*
1202  * no more unmatched tuples
1203  */
1204  return false;
1205 }
1206 
1207 /*
1208  * ExecHashTableReset
1209  *
1210  * reset hash table header for new batch
1211  */
1212 void
1214 {
1215  MemoryContext oldcxt;
1216  int nbuckets = hashtable->nbuckets;
1217 
1218  /*
1219  * Release all the hash buckets and tuples acquired in the prior pass, and
1220  * reinitialize the context for a new pass.
1221  */
1222  MemoryContextReset(hashtable->batchCxt);
1223  oldcxt = MemoryContextSwitchTo(hashtable->batchCxt);
1224 
1225  /* Reallocate and reinitialize the hash bucket headers. */
1226  hashtable->buckets = (HashJoinTuple *)
1227  palloc0(nbuckets * sizeof(HashJoinTuple));
1228 
1229  hashtable->spaceUsed = 0;
1230 
1231  MemoryContextSwitchTo(oldcxt);
1232 
1233  /* Forget the chunks (the memory was freed by the context reset above). */
1234  hashtable->chunks = NULL;
1235 }
1236 
1237 /*
1238  * ExecHashTableResetMatchFlags
1239  * Clear all the HeapTupleHeaderHasMatch flags in the table
1240  */
1241 void
1243 {
1244  HashJoinTuple tuple;
1245  int i;
1246 
1247  /* Reset all flags in the main table ... */
1248  for (i = 0; i < hashtable->nbuckets; i++)
1249  {
1250  for (tuple = hashtable->buckets[i]; tuple != NULL; tuple = tuple->next)
1252  }
1253 
1254  /* ... and the same for the skew buckets, if any */
1255  for (i = 0; i < hashtable->nSkewBuckets; i++)
1256  {
1257  int j = hashtable->skewBucketNums[i];
1258  HashSkewBucket *skewBucket = hashtable->skewBucket[j];
1259 
1260  for (tuple = skewBucket->tuples; tuple != NULL; tuple = tuple->next)
1262  }
1263 }
1264 
1265 
1266 void
1268 {
1269  /*
1270  * if chgParam of subnode is not null then plan will be re-scanned by
1271  * first ExecProcNode.
1272  */
1273  if (node->ps.lefttree->chgParam == NULL)
1274  ExecReScan(node->ps.lefttree);
1275 }
1276 
1277 
1278 /*
1279  * ExecHashBuildSkewHash
1280  *
1281  * Set up for skew optimization if we can identify the most common values
1282  * (MCVs) of the outer relation's join key. We make a skew hash bucket
1283  * for the hash value of each MCV, up to the number of slots allowed
1284  * based on available memory.
1285  */
1286 static void
1287 ExecHashBuildSkewHash(HashJoinTable hashtable, Hash *node, int mcvsToUse)
1288 {
1289  HeapTupleData *statsTuple;
1290  Datum *values;
1291  int nvalues;
1292  float4 *numbers;
1293  int nnumbers;
1294 
1295  /* Do nothing if planner didn't identify the outer relation's join key */
1296  if (!OidIsValid(node->skewTable))
1297  return;
1298  /* Also, do nothing if we don't have room for at least one skew bucket */
1299  if (mcvsToUse <= 0)
1300  return;
1301 
1302  /*
1303  * Try to find the MCV statistics for the outer relation's join key.
1304  */
1305  statsTuple = SearchSysCache3(STATRELATTINH,
1306  ObjectIdGetDatum(node->skewTable),
1307  Int16GetDatum(node->skewColumn),
1308  BoolGetDatum(node->skewInherit));
1309  if (!HeapTupleIsValid(statsTuple))
1310  return;
1311 
1312  if (get_attstatsslot(statsTuple, node->skewColType, node->skewColTypmod,
1314  NULL,
1315  &values, &nvalues,
1316  &numbers, &nnumbers))
1317  {
1318  double frac;
1319  int nbuckets;
1320  FmgrInfo *hashfunctions;
1321  int i;
1322 
1323  if (mcvsToUse > nvalues)
1324  mcvsToUse = nvalues;
1325 
1326  /*
1327  * Calculate the expected fraction of outer relation that will
1328  * participate in the skew optimization. If this isn't at least
1329  * SKEW_MIN_OUTER_FRACTION, don't use skew optimization.
1330  */
1331  frac = 0;
1332  for (i = 0; i < mcvsToUse; i++)
1333  frac += numbers[i];
1334  if (frac < SKEW_MIN_OUTER_FRACTION)
1335  {
1337  values, nvalues, numbers, nnumbers);
1338  ReleaseSysCache(statsTuple);
1339  return;
1340  }
1341 
1342  /*
1343  * Okay, set up the skew hashtable.
1344  *
1345  * skewBucket[] is an open addressing hashtable with a power of 2 size
1346  * that is greater than the number of MCV values. (This ensures there
1347  * will be at least one null entry, so searches will always
1348  * terminate.)
1349  *
1350  * Note: this code could fail if mcvsToUse exceeds INT_MAX/8 or
1351  * MaxAllocSize/sizeof(void *)/8, but that is not currently possible
1352  * since we limit pg_statistic entries to much less than that.
1353  */
1354  nbuckets = 2;
1355  while (nbuckets <= mcvsToUse)
1356  nbuckets <<= 1;
1357  /* use two more bits just to help avoid collisions */
1358  nbuckets <<= 2;
1359 
1360  hashtable->skewEnabled = true;
1361  hashtable->skewBucketLen = nbuckets;
1362 
1363  /*
1364  * We allocate the bucket memory in the hashtable's batch context. It
1365  * is only needed during the first batch, and this ensures it will be
1366  * automatically removed once the first batch is done.
1367  */
1368  hashtable->skewBucket = (HashSkewBucket **)
1369  MemoryContextAllocZero(hashtable->batchCxt,
1370  nbuckets * sizeof(HashSkewBucket *));
1371  hashtable->skewBucketNums = (int *)
1372  MemoryContextAllocZero(hashtable->batchCxt,
1373  mcvsToUse * sizeof(int));
1374 
1375  hashtable->spaceUsed += nbuckets * sizeof(HashSkewBucket *)
1376  + mcvsToUse * sizeof(int);
1377  hashtable->spaceUsedSkew += nbuckets * sizeof(HashSkewBucket *)
1378  + mcvsToUse * sizeof(int);
1379  if (hashtable->spaceUsed > hashtable->spacePeak)
1380  hashtable->spacePeak = hashtable->spaceUsed;
1381 
1382  /*
1383  * Create a skew bucket for each MCV hash value.
1384  *
1385  * Note: it is very important that we create the buckets in order of
1386  * decreasing MCV frequency. If we have to remove some buckets, they
1387  * must be removed in reverse order of creation (see notes in
1388  * ExecHashRemoveNextSkewBucket) and we want the least common MCVs to
1389  * be removed first.
1390  */
1391  hashfunctions = hashtable->outer_hashfunctions;
1392 
1393  for (i = 0; i < mcvsToUse; i++)
1394  {
1395  uint32 hashvalue;
1396  int bucket;
1397 
1398  hashvalue = DatumGetUInt32(FunctionCall1(&hashfunctions[0],
1399  values[i]));
1400 
1401  /*
1402  * While we have not hit a hole in the hashtable and have not hit
1403  * the desired bucket, we have collided with some previous hash
1404  * value, so try the next bucket location. NB: this code must
1405  * match ExecHashGetSkewBucket.
1406  */
1407  bucket = hashvalue & (nbuckets - 1);
1408  while (hashtable->skewBucket[bucket] != NULL &&
1409  hashtable->skewBucket[bucket]->hashvalue != hashvalue)
1410  bucket = (bucket + 1) & (nbuckets - 1);
1411 
1412  /*
1413  * If we found an existing bucket with the same hashvalue, leave
1414  * it alone. It's okay for two MCVs to share a hashvalue.
1415  */
1416  if (hashtable->skewBucket[bucket] != NULL)
1417  continue;
1418 
1419  /* Okay, create a new skew bucket for this hashvalue. */
1420  hashtable->skewBucket[bucket] = (HashSkewBucket *)
1421  MemoryContextAlloc(hashtable->batchCxt,
1422  sizeof(HashSkewBucket));
1423  hashtable->skewBucket[bucket]->hashvalue = hashvalue;
1424  hashtable->skewBucket[bucket]->tuples = NULL;
1425  hashtable->skewBucketNums[hashtable->nSkewBuckets] = bucket;
1426  hashtable->nSkewBuckets++;
1427  hashtable->spaceUsed += SKEW_BUCKET_OVERHEAD;
1428  hashtable->spaceUsedSkew += SKEW_BUCKET_OVERHEAD;
1429  if (hashtable->spaceUsed > hashtable->spacePeak)
1430  hashtable->spacePeak = hashtable->spaceUsed;
1431  }
1432 
1434  values, nvalues, numbers, nnumbers);
1435  }
1436 
1437  ReleaseSysCache(statsTuple);
1438 }
1439 
1440 /*
1441  * ExecHashGetSkewBucket
1442  *
1443  * Returns the index of the skew bucket for this hashvalue,
1444  * or INVALID_SKEW_BUCKET_NO if the hashvalue is not
1445  * associated with any active skew bucket.
1446  */
1447 int
1449 {
1450  int bucket;
1451 
1452  /*
1453  * Always return INVALID_SKEW_BUCKET_NO if not doing skew optimization (in
1454  * particular, this happens after the initial batch is done).
1455  */
1456  if (!hashtable->skewEnabled)
1457  return INVALID_SKEW_BUCKET_NO;
1458 
1459  /*
1460  * Since skewBucketLen is a power of 2, we can do a modulo by ANDing.
1461  */
1462  bucket = hashvalue & (hashtable->skewBucketLen - 1);
1463 
1464  /*
1465  * While we have not hit a hole in the hashtable and have not hit the
1466  * desired bucket, we have collided with some other hash value, so try the
1467  * next bucket location.
1468  */
1469  while (hashtable->skewBucket[bucket] != NULL &&
1470  hashtable->skewBucket[bucket]->hashvalue != hashvalue)
1471  bucket = (bucket + 1) & (hashtable->skewBucketLen - 1);
1472 
1473  /*
1474  * Found the desired bucket?
1475  */
1476  if (hashtable->skewBucket[bucket] != NULL)
1477  return bucket;
1478 
1479  /*
1480  * There must not be any hashtable entry for this hash value.
1481  */
1482  return INVALID_SKEW_BUCKET_NO;
1483 }
1484 
1485 /*
1486  * ExecHashSkewTableInsert
1487  *
1488  * Insert a tuple into the skew hashtable.
1489  *
1490  * This should generally match up with the current-batch case in
1491  * ExecHashTableInsert.
1492  */
1493 static void
1495  TupleTableSlot *slot,
1496  uint32 hashvalue,
1497  int bucketNumber)
1498 {
1500  HashJoinTuple hashTuple;
1501  int hashTupleSize;
1502 
1503  /* Create the HashJoinTuple */
1504  hashTupleSize = HJTUPLE_OVERHEAD + tuple->t_len;
1505  hashTuple = (HashJoinTuple) MemoryContextAlloc(hashtable->batchCxt,
1506  hashTupleSize);
1507  hashTuple->hashvalue = hashvalue;
1508  memcpy(HJTUPLE_MINTUPLE(hashTuple), tuple, tuple->t_len);
1510 
1511  /* Push it onto the front of the skew bucket's list */
1512  hashTuple->next = hashtable->skewBucket[bucketNumber]->tuples;
1513  hashtable->skewBucket[bucketNumber]->tuples = hashTuple;
1514 
1515  /* Account for space used, and back off if we've used too much */
1516  hashtable->spaceUsed += hashTupleSize;
1517  hashtable->spaceUsedSkew += hashTupleSize;
1518  if (hashtable->spaceUsed > hashtable->spacePeak)
1519  hashtable->spacePeak = hashtable->spaceUsed;
1520  while (hashtable->spaceUsedSkew > hashtable->spaceAllowedSkew)
1521  ExecHashRemoveNextSkewBucket(hashtable);
1522 
1523  /* Check we are not over the total spaceAllowed, either */
1524  if (hashtable->spaceUsed > hashtable->spaceAllowed)
1525  ExecHashIncreaseNumBatches(hashtable);
1526 }
1527 
1528 /*
1529  * ExecHashRemoveNextSkewBucket
1530  *
1531  * Remove the least valuable skew bucket by pushing its tuples into
1532  * the main hash table.
1533  */
1534 static void
1536 {
1537  int bucketToRemove;
1538  HashSkewBucket *bucket;
1539  uint32 hashvalue;
1540  int bucketno;
1541  int batchno;
1542  HashJoinTuple hashTuple;
1543 
1544  /* Locate the bucket to remove */
1545  bucketToRemove = hashtable->skewBucketNums[hashtable->nSkewBuckets - 1];
1546  bucket = hashtable->skewBucket[bucketToRemove];
1547 
1548  /*
1549  * Calculate which bucket and batch the tuples belong to in the main
1550  * hashtable. They all have the same hash value, so it's the same for all
1551  * of them. Also note that it's not possible for nbatch to increase while
1552  * we are processing the tuples.
1553  */
1554  hashvalue = bucket->hashvalue;
1555  ExecHashGetBucketAndBatch(hashtable, hashvalue, &bucketno, &batchno);
1556 
1557  /* Process all tuples in the bucket */
1558  hashTuple = bucket->tuples;
1559  while (hashTuple != NULL)
1560  {
1561  HashJoinTuple nextHashTuple = hashTuple->next;
1562  MinimalTuple tuple;
1563  Size tupleSize;
1564 
1565  /*
1566  * This code must agree with ExecHashTableInsert. We do not use
1567  * ExecHashTableInsert directly as ExecHashTableInsert expects a
1568  * TupleTableSlot while we already have HashJoinTuples.
1569  */
1570  tuple = HJTUPLE_MINTUPLE(hashTuple);
1571  tupleSize = HJTUPLE_OVERHEAD + tuple->t_len;
1572 
1573  /* Decide whether to put the tuple in the hash table or a temp file */
1574  if (batchno == hashtable->curbatch)
1575  {
1576  /* Move the tuple to the main hash table */
1577  HashJoinTuple copyTuple;
1578 
1579  /*
1580  * We must copy the tuple into the dense storage, else it will not
1581  * be found by, eg, ExecHashIncreaseNumBatches.
1582  */
1583  copyTuple = (HashJoinTuple) dense_alloc(hashtable, tupleSize);
1584  memcpy(copyTuple, hashTuple, tupleSize);
1585  pfree(hashTuple);
1586 
1587  copyTuple->next = hashtable->buckets[bucketno];
1588  hashtable->buckets[bucketno] = copyTuple;
1589 
1590  /* We have reduced skew space, but overall space doesn't change */
1591  hashtable->spaceUsedSkew -= tupleSize;
1592  }
1593  else
1594  {
1595  /* Put the tuple into a temp file for later batches */
1596  Assert(batchno > hashtable->curbatch);
1597  ExecHashJoinSaveTuple(tuple, hashvalue,
1598  &hashtable->innerBatchFile[batchno]);
1599  pfree(hashTuple);
1600  hashtable->spaceUsed -= tupleSize;
1601  hashtable->spaceUsedSkew -= tupleSize;
1602  }
1603 
1604  hashTuple = nextHashTuple;
1605 
1606  /* allow this loop to be cancellable */
1608  }
1609 
1610  /*
1611  * Free the bucket struct itself and reset the hashtable entry to NULL.
1612  *
1613  * NOTE: this is not nearly as simple as it looks on the surface, because
1614  * of the possibility of collisions in the hashtable. Suppose that hash
1615  * values A and B collide at a particular hashtable entry, and that A was
1616  * entered first so B gets shifted to a different table entry. If we were
1617  * to remove A first then ExecHashGetSkewBucket would mistakenly start
1618  * reporting that B is not in the hashtable, because it would hit the NULL
1619  * before finding B. However, we always remove entries in the reverse
1620  * order of creation, so this failure cannot happen.
1621  */
1622  hashtable->skewBucket[bucketToRemove] = NULL;
1623  hashtable->nSkewBuckets--;
1624  pfree(bucket);
1625  hashtable->spaceUsed -= SKEW_BUCKET_OVERHEAD;
1626  hashtable->spaceUsedSkew -= SKEW_BUCKET_OVERHEAD;
1627 
1628  /*
1629  * If we have removed all skew buckets then give up on skew optimization.
1630  * Release the arrays since they aren't useful any more.
1631  */
1632  if (hashtable->nSkewBuckets == 0)
1633  {
1634  hashtable->skewEnabled = false;
1635  pfree(hashtable->skewBucket);
1636  pfree(hashtable->skewBucketNums);
1637  hashtable->skewBucket = NULL;
1638  hashtable->skewBucketNums = NULL;
1639  hashtable->spaceUsed -= hashtable->spaceUsedSkew;
1640  hashtable->spaceUsedSkew = 0;
1641  }
1642 }
1643 
1644 /*
1645  * Allocate 'size' bytes from the currently active HashMemoryChunk
1646  */
1647 static void *
1649 {
1650  HashMemoryChunk newChunk;
1651  char *ptr;
1652 
1653  /* just in case the size is not already aligned properly */
1654  size = MAXALIGN(size);
1655 
1656  /*
1657  * If tuple size is larger than of 1/4 of chunk size, allocate a separate
1658  * chunk.
1659  */
1660  if (size > HASH_CHUNK_THRESHOLD)
1661  {
1662  /* allocate new chunk and put it at the beginning of the list */
1663  newChunk = (HashMemoryChunk) MemoryContextAlloc(hashtable->batchCxt,
1664  offsetof(HashMemoryChunkData, data) + size);
1665  newChunk->maxlen = size;
1666  newChunk->used = 0;
1667  newChunk->ntuples = 0;
1668 
1669  /*
1670  * Add this chunk to the list after the first existing chunk, so that
1671  * we don't lose the remaining space in the "current" chunk.
1672  */
1673  if (hashtable->chunks != NULL)
1674  {
1675  newChunk->next = hashtable->chunks->next;
1676  hashtable->chunks->next = newChunk;
1677  }
1678  else
1679  {
1680  newChunk->next = hashtable->chunks;
1681  hashtable->chunks = newChunk;
1682  }
1683 
1684  newChunk->used += size;
1685  newChunk->ntuples += 1;
1686 
1687  return newChunk->data;
1688  }
1689 
1690  /*
1691  * See if we have enough space for it in the current chunk (if any). If
1692  * not, allocate a fresh chunk.
1693  */
1694  if ((hashtable->chunks == NULL) ||
1695  (hashtable->chunks->maxlen - hashtable->chunks->used) < size)
1696  {
1697  /* allocate new chunk and put it at the beginning of the list */
1698  newChunk = (HashMemoryChunk) MemoryContextAlloc(hashtable->batchCxt,
1700 
1701  newChunk->maxlen = HASH_CHUNK_SIZE;
1702  newChunk->used = size;
1703  newChunk->ntuples = 1;
1704 
1705  newChunk->next = hashtable->chunks;
1706  hashtable->chunks = newChunk;
1707 
1708  return newChunk->data;
1709  }
1710 
1711  /* There is enough space in the current chunk, let's add the tuple */
1712  ptr = hashtable->chunks->data + hashtable->chunks->used;
1713  hashtable->chunks->used += size;
1714  hashtable->chunks->ntuples += 1;
1715 
1716  /* return pointer to the start of the tuple memory */
1717  return ptr;
1718 }
int log2_nbuckets_optimal
Definition: hashjoin.h:134
Oid skewTable
Definition: plannodes.h:837
#define DatumGetUInt32(X)
Definition: postgres.h:492
double skewTuples
Definition: hashjoin.h:157
#define NIL
Definition: pg_list.h:69
void InstrStopNode(Instrumentation *instr, double nTuples)
Definition: instrument.c:80
Definition: fmgr.h:53
List * qual
Definition: plannodes.h:133
#define SKEW_BUCKET_OVERHEAD
Definition: hashjoin.h:100
double plan_rows
Definition: plannodes.h:120
#define INVALID_SKEW_BUCKET_NO
Definition: hashjoin.h:101
bool op_strict(Oid opno)
Definition: lsyscache.c:1249
TupleTableSlot * ExecProcNode(PlanState *node)
Definition: execProcnode.c:392
bool skewInherit
Definition: plannodes.h:839
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:200
bool get_op_hash_functions(Oid opno, RegProcedure *lhs_procno, RegProcedure *rhs_procno)
Definition: lsyscache.c:507
HashJoinTable ExecHashTableCreate(Hash *node, List *hashOperators, bool keepNulls)
Definition: nodeHash.c:246
TupleTableSlot * ExecStoreMinimalTuple(MinimalTuple mtup, TupleTableSlot *slot, bool shouldFree)
Definition: execTuples.c:384
static void ExecHashRemoveNextSkewBucket(HashJoinTable hashtable)
Definition: nodeHash.c:1535
#define SKEW_MIN_OUTER_FRACTION
Definition: hashjoin.h:103
struct HashJoinTupleData ** buckets
Definition: hashjoin.h:137
ProjectionInfo * ps_ProjInfo
Definition: execnodes.h:1081
Instrumentation * instrument
Definition: execnodes.h:1055
void ExecEndNode(PlanState *node)
Definition: execProcnode.c:644
bool ExecScanHashTableForUnmatched(HashJoinState *hjstate, ExprContext *econtext)
Definition: nodeHash.c:1145
MinimalTuple ExecFetchSlotMinimalTuple(TupleTableSlot *slot)
Definition: execTuples.c:652
#define HASH_CHUNK_SIZE
Definition: hashjoin.h:123
void ExecPrepHashTableForUnmatched(HashJoinState *hjstate)
Definition: nodeHash.c:1121
ExprContext * ps_ExprContext
Definition: execnodes.h:1080
HashState * ExecInitHash(Hash *node, EState *estate, int eflags)
Definition: nodeHash.c:162
void ExecHashTableReset(HashJoinTable hashtable)
Definition: nodeHash.c:1213
MemoryContext ecxt_per_tuple_memory
Definition: execnodes.h:136
HashJoinTable hashtable
Definition: execnodes.h:2133
#define Min(x, y)
Definition: c.h:806
void ExecReScan(PlanState *node)
Definition: execAmi.c:74
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
#define Int16GetDatum(X)
Definition: postgres.h:457
List * qual
Definition: execnodes.h:1064
Definition: nodes.h:518
Oid skewColType
Definition: plannodes.h:840
#define MemSet(start, val, len)
Definition: c.h:857
Node * MultiExecHash(HashState *node)
Definition: nodeHash.c:74
List * targetlist
Definition: execnodes.h:1063
Datum idx(PG_FUNCTION_ARGS)
Definition: _int_op.c:264
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:135
FmgrInfo * inner_hashfunctions
Definition: hashjoin.h:175
bool get_attstatsslot(HeapTuple statstuple, Oid atttype, int32 atttypmod, int reqkind, Oid reqop, Oid *actualop, Datum **values, int *nvalues, float4 **numbers, int *nnumbers)
Definition: lsyscache.c:2854
static void ExecHashIncreaseNumBatches(HashJoinTable hashtable)
Definition: nodeHash.c:593
EState * state
Definition: execnodes.h:1051
void ExecChooseHashTableSize(double ntuples, int tupwidth, bool useskew, int *numbuckets, int *numbatches, int *num_skew_mcvs)
Definition: nodeHash.c:404
unsigned int Oid
Definition: postgres_ext.h:31
#define OidIsValid(objectId)
Definition: c.h:538
void ExecFreeExprContext(PlanState *planstate)
Definition: execUtils.c:686
void BufFileClose(BufFile *file)
Definition: buffile.c:203
int ExecHashGetSkewBucket(HashJoinTable hashtable, uint32 hashvalue)
Definition: nodeHash.c:1448
void ExecAssignResultTypeFromTL(PlanState *planstate)
Definition: execUtils.c:431
static void ExecHashBuildSkewHash(HashJoinTable hashtable, Hash *node, int mcvsToUse)
Definition: nodeHash.c:1287
struct PlanState * lefttree
Definition: execnodes.h:1065
int * skewBucketNums
Definition: hashjoin.h:146
void ExecHashTableInsert(HashJoinTable hashtable, TupleTableSlot *slot, uint32 hashvalue)
Definition: nodeHash.c:833
void ExecHashGetBucketAndBatch(HashJoinTable hashtable, uint32 hashvalue, int *bucketno, int *batchno)
Definition: nodeHash.c:1031
uint32 hj_CurHashValue
Definition: execnodes.h:1865
int hj_CurSkewBucketNo
Definition: execnodes.h:1867
ExprState * ExecInitExpr(Expr *node, PlanState *parent)
Definition: execQual.c:4267
void ExecReScanHash(HashState *node)
Definition: nodeHash.c:1267
void pfree(void *pointer)
Definition: mcxt.c:950
#define ExecEvalExpr(expr, econtext, isNull)
Definition: executor.h:73
#define ObjectIdGetDatum(X)
Definition: postgres.h:513
#define ERROR
Definition: elog.h:43
void PrepareTempTablespaces(void)
Definition: tablespace.c:1287
void ExecInitResultTupleSlot(EState *estate, PlanState *planstate)
Definition: execTuples.c:832
static void ExecHashIncreaseNumBuckets(HashJoinTable hashtable)
Definition: nodeHash.c:762
void InstrStartNode(Instrumentation *instr)
Definition: instrument.c:63
void fmgr_info(Oid functionId, FmgrInfo *finfo)
Definition: fmgr.c:159
#define HASH_CHUNK_THRESHOLD
Definition: hashjoin.h:124
struct HashJoinTupleData * HashJoinTuple
Definition: execnodes.h:1854
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:165
#define EXEC_FLAG_BACKWARD
Definition: executor.h:60
BufFile ** outerBatchFile
Definition: hashjoin.h:167
#define outerPlanState(node)
Definition: execnodes.h:1092
HashJoinTuple hj_CurTuple
Definition: execnodes.h:1868
AttrNumber skewColumn
Definition: plannodes.h:838
bool ExecScanHashBucket(HashJoinState *hjstate, ExprContext *econtext)
Definition: nodeHash.c:1063
Size spaceAllowedSkew
Definition: hashjoin.h:182
HashJoinTuple tuples
Definition: hashjoin.h:97
TupleTableSlot * ecxt_innertuple
Definition: execnodes.h:131
bool ExecQual(List *qual, ExprContext *econtext, bool resultForNull)
Definition: execQual.c:5056
List * hashkeys
Definition: execnodes.h:2134
#define TupIsNull(slot)
Definition: tuptable.h:138
unsigned int uint32
Definition: c.h:268
PlanState ps
Definition: execnodes.h:2132
struct HashMemoryChunkData * next
Definition: hashjoin.h:115
MemoryContext CurrentMemoryContext
Definition: mcxt.c:37
#define STATISTIC_KIND_MCV
Definition: pg_statistic.h:204
MemoryContext batchCxt
Definition: hashjoin.h:185
struct HashJoinTableData * HashJoinTable
Definition: execnodes.h:1855
Bitmapset * chgParam
Definition: execnodes.h:1074
int my_log2(long num)
Definition: dynahash.c:1682
#define outerPlan(node)
Definition: plannodes.h:162
FmgrInfo * outer_hashfunctions
Definition: hashjoin.h:174
#define MaxAllocSize
Definition: memutils.h:40
int hj_CurBucketNo
Definition: execnodes.h:1866
float float4
Definition: c.h:380
#define SizeofMinimalTupleHeader
Definition: htup_details.h:650
HashSkewBucket ** skewBucket
Definition: hashjoin.h:143
MemoryContext AllocSetContextCreate(MemoryContext parent, const char *name, Size minContextSize, Size initBlockSize, Size maxBlockSize)
Definition: aset.c:322
void * palloc0(Size size)
Definition: mcxt.c:878
uintptr_t Datum
Definition: postgres.h:372
static void * dense_alloc(HashJoinTable hashtable, Size size)
Definition: nodeHash.c:1648
void ReleaseSysCache(HeapTuple tuple)
Definition: syscache.c:1081
struct HashMemoryChunkData * HashMemoryChunk
Definition: hashjoin.h:121
#define NTUP_PER_BUCKET
Definition: nodeHash.c:401
int work_mem
Definition: globals.c:112
void * MemoryContextAllocZero(MemoryContext context, Size size)
Definition: mcxt.c:742
#define HJTUPLE_OVERHEAD
Definition: hashjoin.h:71
#define BoolGetDatum(X)
Definition: postgres.h:408
Plan * plan
Definition: execnodes.h:1049
int32 skewColTypmod
Definition: plannodes.h:841
#define InvalidOid
Definition: postgres_ext.h:36
double totalTuples
Definition: hashjoin.h:156
uint32 hashvalue
Definition: hashjoin.h:96
#define HJTUPLE_MINTUPLE(hjtup)
Definition: hashjoin.h:72
#define HeapTupleHeaderHasMatch(tup)
Definition: htup_details.h:517
#define Max(x, y)
Definition: c.h:800
#define makeNode(_type_)
Definition: nodes.h:566
int plan_width
Definition: plannodes.h:121
#define HeapTupleIsValid(tuple)
Definition: htup.h:77
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
static void ExecHashSkewTableInsert(HashJoinTable hashtable, TupleTableSlot *slot, uint32 hashvalue, int bucketNumber)
Definition: nodeHash.c:1494
#define lfirst(lc)
Definition: pg_list.h:106
#define EXEC_FLAG_MARK
Definition: executor.h:61
char data[FLEXIBLE_ARRAY_MEMBER]
Definition: hashjoin.h:118
size_t Size
Definition: c.h:356
void ExecAssignExprContext(EState *estate, PlanState *planstate)
Definition: execUtils.c:409
BufFile ** innerBatchFile
Definition: hashjoin.h:166
struct HashJoinTupleData * next
Definition: hashjoin.h:66
static int list_length(const List *l)
Definition: pg_list.h:89
#define HeapTupleHeaderClearMatch(tup)
Definition: htup_details.h:527
#define MAXALIGN(LEN)
Definition: c.h:588
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:963
List * targetlist
Definition: plannodes.h:132
HashMemoryChunk chunks
Definition: hashjoin.h:188
List * hashclauses
Definition: execnodes.h:1860
static Datum values[MAXATTR]
Definition: bootstrap.c:162
TupleTableSlot * hj_HashTupleSlot
Definition: execnodes.h:1870
Plan plan
Definition: plannodes.h:836
void * palloc(Size size)
Definition: mcxt.c:849
HashJoinTable hj_HashTable
Definition: execnodes.h:1864
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:707
#define SearchSysCache3(cacheId, key1, key2, key3)
Definition: syscache.h:153
int i
void ExecEndHash(HashState *node)
Definition: nodeHash.c:222
#define FunctionCall1(flinfo, arg1)
Definition: fmgr.h:594
void ExecHashTableResetMatchFlags(HashJoinTable hashtable)
Definition: nodeHash.c:1242
bool ExecHashGetHashValue(HashJoinTable hashtable, ExprContext *econtext, List *hashkeys, bool outer_tuple, bool keep_nulls, uint32 *hashvalue)
Definition: nodeHash.c:927
bool * hashStrict
Definition: hashjoin.h:176
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:97
MemoryContext hashCxt
Definition: hashjoin.h:184
#define elog
Definition: elog.h:219
#define SKEW_WORK_MEM_PERCENT
Definition: hashjoin.h:102
PlanState * ExecInitNode(Plan *node, EState *estate, int eflags)
Definition: execProcnode.c:139
Definition: pg_list.h:45
void free_attstatsslot(Oid atttype, Datum *values, int nvalues, float4 *numbers, int nnumbers)
Definition: lsyscache.c:2978
TupleTableSlot * ExecHash(HashState *node)
Definition: nodeHash.c:60
void ExecHashJoinSaveTuple(MinimalTuple tuple, uint32 hashvalue, BufFile **fileptr)
Definition: nodeHashjoin.c:816
void ExecHashTableDestroy(HashJoinTable hashtable)
Definition: nodeHash.c:563
uint32 hashvalue
Definition: hashjoin.h:67
#define offsetof(type, field)
Definition: c.h:555
#define ResetExprContext(econtext)
Definition: executor.h:332
#define lfirst_oid(lc)
Definition: pg_list.h:108