1 /*------------------------------------------------------------------------- 2 * 3 * hashjoin.h 4 * internal structures for hash joins 5 * 6 * 7 * Portions Copyright (c) 1996-2016, 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 */ 69 } HashJoinTupleData; 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 */ 98 } HashSkewBucket; 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 */ 119 } HashMemoryChunkData; 120 121 typedef struct HashMemoryChunkData *HashMemoryChunk; 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 */ 137 struct HashJoinTupleData **buckets; 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 */ 189 } HashJoinTableData; 190 191 #endif /* HASHJOIN_H */ 192