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
132  * hash */
133  int nbuckets_optimal; /* optimal # buckets (per batch) */
134  int log2_nbuckets_optimal; /* log2(nbuckets_optimal) */
135 
136  /* buckets[i] is head of list of tuples in i'th in-memory bucket */
138  /* buckets array is per-batch storage, as are all the tuples */
139 
140  bool keepNulls; /* true to store unmatchable NULL tuples */
141 
142  bool skewEnabled; /* are we using skew optimization? */
143  HashSkewBucket **skewBucket; /* hashtable of skew buckets */
144  int skewBucketLen; /* size of skewBucket array (a power of 2!) */
145  int nSkewBuckets; /* number of active skew buckets */
146  int *skewBucketNums; /* array indexes of active skew buckets */
147 
148  int nbatch; /* number of batches */
149  int curbatch; /* current batch #; 0 during 1st pass */
150 
151  int nbatch_original; /* nbatch when we started inner scan */
152  int nbatch_outstart; /* nbatch when we started outer scan */
153 
154  bool growEnabled; /* flag to shut off nbatch increases */
155 
156  double totalTuples; /* # tuples obtained from inner plan */
157  double skewTuples; /* # tuples inserted into skew tuples */
158 
159  /*
160  * These arrays are allocated for the life of the hash join, but only if
161  * nbatch > 1. A file is opened only when we first write a tuple into it
162  * (otherwise its pointer remains NULL). Note that the zero'th array
163  * elements never get used, since we will process rather than dump out any
164  * tuples of batch zero.
165  */
166  BufFile **innerBatchFile; /* buffered virtual temp file per batch */
167  BufFile **outerBatchFile; /* buffered virtual temp file per batch */
168 
169  /*
170  * Info about the datatype-specific hash functions for the datatypes being
171  * hashed. These are arrays of the same length as the number of hash join
172  * clauses (hash keys).
173  */
174  FmgrInfo *outer_hashfunctions; /* lookup data for hash functions */
175  FmgrInfo *inner_hashfunctions; /* lookup data for hash functions */
176  bool *hashStrict; /* is each hash join operator strict? */
177 
178  Size spaceUsed; /* memory space currently used by tuples */
179  Size spaceAllowed; /* upper limit for space used */
180  Size spacePeak; /* peak space used */
181  Size spaceUsedSkew; /* skew hash table's current space usage */
182  Size spaceAllowedSkew; /* upper limit for skew hashtable */
183 
184  MemoryContext hashCxt; /* context for whole-hash-join storage */
185  MemoryContext batchCxt; /* context for this-batch-only storage */
186 
187  /* used for dense allocation of tuples (into linked chunks) */
188  HashMemoryChunk chunks; /* one list for the whole batch */
190 
191 #endif /* HASHJOIN_H */
int log2_nbuckets_optimal
Definition: hashjoin.h:134
double skewTuples
Definition: hashjoin.h:157
Definition: fmgr.h:53
struct HashJoinTupleData ** buckets
Definition: hashjoin.h:137
FmgrInfo * inner_hashfunctions
Definition: hashjoin.h:175
int * skewBucketNums
Definition: hashjoin.h:146
BufFile ** outerBatchFile
Definition: hashjoin.h:167
Size spaceAllowedSkew
Definition: hashjoin.h:182
HashJoinTuple tuples
Definition: hashjoin.h:97
unsigned int uint32
Definition: c.h:265
struct HashMemoryChunkData * next
Definition: hashjoin.h:115
MemoryContext batchCxt
Definition: hashjoin.h:185
struct HashSkewBucket HashSkewBucket
FmgrInfo * outer_hashfunctions
Definition: hashjoin.h:174
HashSkewBucket ** skewBucket
Definition: hashjoin.h:143
struct HashMemoryChunkData * HashMemoryChunk
Definition: hashjoin.h:121
double totalTuples
Definition: hashjoin.h:156
uint32 hashvalue
Definition: hashjoin.h:96
struct HashJoinTupleData HashJoinTupleData
char data[FLEXIBLE_ARRAY_MEMBER]
Definition: hashjoin.h:118
struct HashJoinTableData HashJoinTableData
size_t Size
Definition: c.h:353
BufFile ** innerBatchFile
Definition: hashjoin.h:166
struct HashJoinTupleData * next
Definition: hashjoin.h:66
struct HashMemoryChunkData HashMemoryChunkData
HashMemoryChunk chunks
Definition: hashjoin.h:188
bool * hashStrict
Definition: hashjoin.h:176
MemoryContext hashCxt
Definition: hashjoin.h:184
uint32 hashvalue
Definition: hashjoin.h:67