PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
hashjoin.h
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * hashjoin.h
4  * internal structures for hash joins
5  *
6  *
7  * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
8  * Portions Copyright (c) 1994, Regents of the University of California
9  *
10  * src/include/executor/hashjoin.h
11  *
12  *-------------------------------------------------------------------------
13  */
14 #ifndef HASHJOIN_H
15 #define HASHJOIN_H
16 
17 #include "nodes/execnodes.h"
18 #include "storage/buffile.h"
19 
20 /* ----------------------------------------------------------------
21  * hash-join hash table structures
22  *
23  * Each active hashjoin has a HashJoinTable control block, which is
24  * palloc'd in the executor's per-query context. All other storage needed
25  * for the hashjoin is kept in private memory contexts, two for each hashjoin.
26  * This makes it easy and fast to release the storage when we don't need it
27  * anymore. (Exception: data associated with the temp files lives in the
28  * per-query context too, since we always call buffile.c in that context.)
29  *
30  * The hashtable contexts are made children of the per-query context, ensuring
31  * that they will be discarded at end of statement even if the join is
32  * aborted early by an error. (Likewise, any temporary files we make will
33  * be cleaned up by the virtual file manager in event of an error.)
34  *
35  * Storage that should live through the entire join is allocated from the
36  * "hashCxt", while storage that is only wanted for the current batch is
37  * allocated in the "batchCxt". By resetting the batchCxt at the end of
38  * each batch, we free all the per-batch storage reliably and without tedium.
39  *
40  * During first scan of inner relation, we get its tuples from executor.
41  * If nbatch > 1 then tuples that don't belong in first batch get saved
42  * into inner-batch temp files. The same statements apply for the
43  * first scan of the outer relation, except we write tuples to outer-batch
44  * temp files. After finishing the first scan, we do the following for
45  * each remaining batch:
46  * 1. Read tuples from inner batch file, load into hash buckets.
47  * 2. Read tuples from outer batch file, match to hash buckets and output.
48  *
49  * It is possible to increase nbatch on the fly if the in-memory hash table
50  * gets too big. The hash-value-to-batch computation is arranged so that this
51  * can only cause a tuple to go into a later batch than previously thought,
52  * never into an earlier batch. When we increase nbatch, we rescan the hash
53  * table and dump out any tuples that are now of a later batch to the correct
54  * inner batch file. Subsequently, while reading either inner or outer batch
55  * files, we might find tuples that no longer belong to the current batch;
56  * if so, we just dump them out to the correct batch file.
57  * ----------------------------------------------------------------
58  */
59 
60 /* these are in nodes/execnodes.h: */
61 /* typedef struct HashJoinTupleData *HashJoinTuple; */
62 /* typedef struct HashJoinTableData *HashJoinTable; */
63 
64 typedef struct HashJoinTupleData
65 {
66  struct HashJoinTupleData *next; /* link to next tuple in same bucket */
67  uint32 hashvalue; /* tuple's hash code */
68  /* Tuple data, in MinimalTuple format, follows on a MAXALIGN boundary */
70 
71 #define HJTUPLE_OVERHEAD MAXALIGN(sizeof(HashJoinTupleData))
72 #define HJTUPLE_MINTUPLE(hjtup) \
73  ((MinimalTuple) ((char *) (hjtup) + HJTUPLE_OVERHEAD))
74 
75 /*
76  * If the outer relation's distribution is sufficiently nonuniform, we attempt
77  * to optimize the join by treating the hash values corresponding to the outer
78  * relation's MCVs specially. Inner relation tuples matching these hash
79  * values go into the "skew" hashtable instead of the main hashtable, and
80  * outer relation tuples with these hash values are matched against that
81  * table instead of the main one. Thus, tuples with these hash values are
82  * effectively handled as part of the first batch and will never go to disk.
83  * The skew hashtable is limited to SKEW_WORK_MEM_PERCENT of the total memory
84  * allowed for the join; while building the hashtables, we decrease the number
85  * of MCVs being specially treated if needed to stay under this limit.
86  *
87  * Note: you might wonder why we look at the outer relation stats for this,
88  * rather than the inner. One reason is that the outer relation is typically
89  * bigger, so we get more I/O savings by optimizing for its most common values.
90  * Also, for similarly-sized relations, the planner prefers to put the more
91  * uniformly distributed relation on the inside, so we're more likely to find
92  * interesting skew in the outer relation.
93  */
94 typedef struct HashSkewBucket
95 {
96  uint32 hashvalue; /* common hash value */
97  HashJoinTuple tuples; /* linked list of inner-relation tuples */
99 
100 #define SKEW_BUCKET_OVERHEAD MAXALIGN(sizeof(HashSkewBucket))
101 #define INVALID_SKEW_BUCKET_NO (-1)
102 #define SKEW_WORK_MEM_PERCENT 2
103 #define SKEW_MIN_OUTER_FRACTION 0.01
104 
105 /*
106  * To reduce palloc overhead, the HashJoinTuples for the current batch are
107  * packed in 32kB buffers instead of pallocing each tuple individually.
108  */
109 typedef struct HashMemoryChunkData
110 {
111  int ntuples; /* number of tuples stored in this chunk */
112  size_t maxlen; /* size of the buffer holding the tuples */
113  size_t used; /* number of buffer bytes already used */
114 
115  struct HashMemoryChunkData *next; /* pointer to the next chunk (linked
116  * list) */
117 
118  char data[FLEXIBLE_ARRAY_MEMBER]; /* buffer allocated at the end */
120 
122 
123 #define HASH_CHUNK_SIZE (32 * 1024L)
124 #define HASH_CHUNK_THRESHOLD (HASH_CHUNK_SIZE / 4)
125 
126 typedef struct HashJoinTableData
127 {
128  int nbuckets; /* # buckets in the in-memory hash table */
129  int log2_nbuckets; /* its log2 (nbuckets must be a power of 2) */
130 
131  int nbuckets_original; /* # buckets when starting the first hash */
132  int nbuckets_optimal; /* optimal # buckets (per batch) */
133  int log2_nbuckets_optimal; /* log2(nbuckets_optimal) */
134 
135  /* buckets[i] is head of list of tuples in i'th in-memory bucket */
137  /* buckets array is per-batch storage, as are all the tuples */
138 
139  bool keepNulls; /* true to store unmatchable NULL tuples */
140 
141  bool skewEnabled; /* are we using skew optimization? */
142  HashSkewBucket **skewBucket; /* hashtable of skew buckets */
143  int skewBucketLen; /* size of skewBucket array (a power of 2!) */
144  int nSkewBuckets; /* number of active skew buckets */
145  int *skewBucketNums; /* array indexes of active skew buckets */
146 
147  int nbatch; /* number of batches */
148  int curbatch; /* current batch #; 0 during 1st pass */
149 
150  int nbatch_original; /* nbatch when we started inner scan */
151  int nbatch_outstart; /* nbatch when we started outer scan */
152 
153  bool growEnabled; /* flag to shut off nbatch increases */
154 
155  double totalTuples; /* # tuples obtained from inner plan */
156  double skewTuples; /* # tuples inserted into skew tuples */
157 
158  /*
159  * These arrays are allocated for the life of the hash join, but only if
160  * nbatch > 1. A file is opened only when we first write a tuple into it
161  * (otherwise its pointer remains NULL). Note that the zero'th array
162  * elements never get used, since we will process rather than dump out any
163  * tuples of batch zero.
164  */
165  BufFile **innerBatchFile; /* buffered virtual temp file per batch */
166  BufFile **outerBatchFile; /* buffered virtual temp file per batch */
167 
168  /*
169  * Info about the datatype-specific hash functions for the datatypes being
170  * hashed. These are arrays of the same length as the number of hash join
171  * clauses (hash keys).
172  */
173  FmgrInfo *outer_hashfunctions; /* lookup data for hash functions */
174  FmgrInfo *inner_hashfunctions; /* lookup data for hash functions */
175  bool *hashStrict; /* is each hash join operator strict? */
176 
177  Size spaceUsed; /* memory space currently used by tuples */
178  Size spaceAllowed; /* upper limit for space used */
179  Size spacePeak; /* peak space used */
180  Size spaceUsedSkew; /* skew hash table's current space usage */
181  Size spaceAllowedSkew; /* upper limit for skew hashtable */
182 
183  MemoryContext hashCxt; /* context for whole-hash-join storage */
184  MemoryContext batchCxt; /* context for this-batch-only storage */
185 
186  /* used for dense allocation of tuples (into linked chunks) */
187  HashMemoryChunk chunks; /* one list for the whole batch */
189 
190 #endif /* HASHJOIN_H */
int log2_nbuckets_optimal
Definition: hashjoin.h:133
double skewTuples
Definition: hashjoin.h:156
Definition: fmgr.h:56
struct HashJoinTupleData ** buckets
Definition: hashjoin.h:136
struct HashMemoryChunkData HashMemoryChunkData
FmgrInfo * inner_hashfunctions
Definition: hashjoin.h:174
struct HashJoinTableData HashJoinTableData
int * skewBucketNums
Definition: hashjoin.h:145
BufFile ** outerBatchFile
Definition: hashjoin.h:166
Size spaceAllowedSkew
Definition: hashjoin.h:181
HashJoinTuple tuples
Definition: hashjoin.h:97
unsigned int uint32
Definition: c.h:268
struct HashMemoryChunkData * next
Definition: hashjoin.h:115
MemoryContext batchCxt
Definition: hashjoin.h:184
struct HashSkewBucket HashSkewBucket
FmgrInfo * outer_hashfunctions
Definition: hashjoin.h:173
HashSkewBucket ** skewBucket
Definition: hashjoin.h:142
struct HashMemoryChunkData * HashMemoryChunk
Definition: hashjoin.h:121
double totalTuples
Definition: hashjoin.h:155
uint32 hashvalue
Definition: hashjoin.h:96
char data[FLEXIBLE_ARRAY_MEMBER]
Definition: hashjoin.h:118
size_t Size
Definition: c.h:356
BufFile ** innerBatchFile
Definition: hashjoin.h:165
struct HashJoinTupleData * next
Definition: hashjoin.h:66
HashMemoryChunk chunks
Definition: hashjoin.h:187
struct HashJoinTupleData HashJoinTupleData
bool * hashStrict
Definition: hashjoin.h:175
MemoryContext hashCxt
Definition: hashjoin.h:183
uint32 hashvalue
Definition: hashjoin.h:67