上几节介绍了ExecAgg函数以及相关函数的实现逻辑,其中涉及到哈希表的操作,调用了tuplehash_insert等函数,这些函数的定义和实现位于"simplehash.h"文件中,下面简单介绍"simplehash.h"文件中的内容. ### 一、数据结构 **TupleHashTable** 哈希表定义 ``` typedef struct TupleHashTableData *TupleHashTable; typedef struct TupleHashTableData { //底层Hash表 tuplehash_hash *hashtab; /* underlying hash table */ //在检索键中的列数 int numCols; /* number of columns in lookup key */ //键列中的属性格式 AttrNumber *keyColIdx; /* attr numbers of key columns */ //数据类型的哈希函数 FmgrInfo *tab_hash_funcs; /* hash functions for table datatype(s) */ //数据类型比较器 ExprState *tab_eq_func; /* comparator for table datatype(s) */ //包含数据表的内存上下文 MemoryContext tablecxt; /* memory context containing table */ //函数解析上下文 MemoryContext tempcxt; /* context for function evaluations */ //构造每个哈希条目的实际大小 Size entrysize; /* actual size to make each hash entry */ //依赖数据表条目的slot TupleTableSlot *tableslot; /* slot for referencing table entries */ /* The following fields are set transiently for each table search: */ //下面字段为每一个表检索时临时设置 //当前输入tuple slot TupleTableSlot *inputslot; /* current input tuple's slot */ //输入数据类型的哈希函数 FmgrInfo *in_hash_funcs; /* hash functions for input datatype(s) */ //input vs table的比较器 ExprState *cur_eq_func; /* comparator for input vs. table */ //哈希函数IV uint32 hash_iv; /* hash-function IV */ //表达式上下文 ExprContext *exprcontext; /* expression context */ } TupleHashTableData; typedef tuplehash_iterator TupleHashIterator; /* type definitions */ //哈希表类型定义 typedef struct SH_TYPE //tuplehash_hash { /* * Size of data / bucket array, 64 bits to handle UINT32_MAX sized hash * tables. Note that the maximum number of elements is lower * (SH_MAX_FILLFACTOR) * 数据/桶数组大小,64 bit用于处理UINT32_MAX哈希表. * 注意元素最大格式小于(SH_MAX_FILLFACTOR) */ uint64 size; /* how many elements have valid contents */ //有多少个元素具有有效内容 uint32 members; /* mask for bucket and size calculations, based on size */ //基于大小,用于计算桶和大小的掩码 uint32 sizemask; /* boundary after which to grow hashtable */ //哈希表增长的阈值 uint32 grow_threshold; /* hash buckets */ //哈希桶 SH_ELEMENT_TYPE *data; /* memory context to use for allocations */ //用于分配的内存上下文 MemoryContext ctx; /* user defined data, useful for callbacks */ //用户自定义的数据,通常用于回调函数 void *private_data; } SH_TYPE;//实际是tuplehash_hash ``` **TupleHashEntryData** 哈希表条目 ``` typedef struct TupleHashEntryData *TupleHashEntry; typedef struct TupleHashTableData *TupleHashTable; typedef struct TupleHashEntryData { //该组第一个元组的拷贝 MinimalTuple firstTuple; /* copy of first tuple in this group */ //用户数据 void *additional; /* user data */ //状态(见SH_STATUS) uint32 status; /* hash status */ //哈希值(已缓存) uint32 hash; /* hash value (cached) */ } TupleHashEntryData; typedef enum SH_STATUS { SH_STATUS_EMPTY = 0x00, SH_STATUS_IN_USE = 0x01 } SH_STATUS; ``` **MinimalTuple** 最小化的元组定义 ``` /* * MinimalTuple is an alternative representation that is used for transient * tuples inside the executor, in places where transaction status information * is not required, the tuple rowtype is known, and shaving off a few bytes * is worthwhile because we need to store many tuples. The representation * is chosen so that tuple access routines can work with either full or * minimal tuples via a HeapTupleData pointer structure. The access routines * see no difference, except that they must not access the transaction status * or t_ctid fields because those aren't there. * * For the most part, MinimalTuples should be accessed via TupleTableSlot * routines. These routines will prevent access to the "system columns" * and thereby prevent accidental use of the nonexistent fields. * * MinimalTupleData contains a length word, some padding, and fields matching * HeapTupleHeaderData beginning with t_infomask2. The padding is chosen so * that offsetof(t_infomask2) is the same modulo MAXIMUM_ALIGNOF in both * structs. This makes data alignment rules equivalent in both cases. * * When a minimal tuple is accessed via a HeapTupleData pointer, t_data is * set to point MINIMAL_TUPLE_OFFSET bytes before the actual start of the * minimal tuple --- that is, where a full tuple matching the minimal tuple's * data would start. This trick is what makes the structs seem equivalent. * * Note that t_hoff is computed the same as in a full tuple, hence it includes * the MINIMAL_TUPLE_OFFSET distance. t_len does not include that, however. * * MINIMAL_TUPLE_DATA_OFFSET is the offset to the first useful (non-pad) data * other than the length word. tuplesort.c and tuplestore.c use this to avoid * writing the padding to disk. */ #define MINIMAL_TUPLE_OFFSET \ ((offsetof(HeapTupleHeaderData, t_infomask2) - sizeof(uint32)) / MAXIMUM_ALIGNOF * MAXIMUM_ALIGNOF) #define MINIMAL_TUPLE_PADDING \ ((offsetof(HeapTupleHeaderData, t_infomask2) - sizeof(uint32)) % MAXIMUM_ALIGNOF) #define MINIMAL_TUPLE_DATA_OFFSET \ offsetof(MinimalTupleData, t_infomask2) struct MinimalTupleData { uint32 t_len; /* actual length of minimal tuple */ char mt_padding[MINIMAL_TUPLE_PADDING]; /* Fields below here must match HeapTupleHeaderData! */ uint16 t_infomask2; /* number of attributes + various flags */ uint16 t_infomask; /* various flag bits, see below */ uint8 t_hoff; /* sizeof header incl. bitmap, padding */ /* ^ - 23 bytes - ^ */ bits8 t_bits[FLEXIBLE_ARRAY_MEMBER]; /* bitmap of NULLs */ /* MORE DATA FOLLOWS AT END OF STRUCT */ }; /* typedef appears in htup.h */ #define SizeofMinimalTupleHeader offsetof(MinimalTupleData, t_bits) typedef struct MinimalTupleData MinimalTupleData; typedef MinimalTupleData *MinimalTuple; ``` ### 二、源码解读 simplehash.h定义了一系列的宏,比如SH_MAKE_PREFIX/SH_TYPE等等,在聚合函数实现(文件:src/backend/executor/execGrouping.c)中,具体定义了SH_PREFIX这些宏在聚合函数实现场景下的实际值. 如: \#define SH_PREFIX tuplehash 在聚合函数实现中,均以tuplehash打头,最终的实现函数为tuplehash_insert等. ``` //----------------------------------------------------------------------------------- //src/backend/executor/execGrouping.c /* * Define parameters for tuple hash table code generation. The interface is * *also* declared in execnodes.h (to generate the types, which are externally * visible). */ #define SH_PREFIX tuplehash //以tuplehash打头,如tuplehash_insert等 #define SH_ELEMENT_TYPE TupleHashEntryData //条目类型 #define SH_KEY_TYPE MinimalTuple //Key类型 #define SH_KEY firstTuple //KEY #define SH_HASH_KEY(tb, key) TupleHashTableHash(tb, key) //SH_HASH_KEY --> TupleHashTableHash #define SH_EQUAL(tb, a, b) TupleHashTableMatch(tb, a, b) == 0 //SH_EQUAL --> TupleHashTableMatch #define SH_SCOPE extern //外部LIB #define SH_STORE_HASH #define SH_GET_HASH(tb, a) a->hash #define SH_DEFINE #include "lib/simplehash.h" //----------------------------------------------------------------------------------- //----------------------------------------------------------------------------------- //src/include/nodes/execnodes.h /* define parameters necessary to generate the tuple hash table interface */ #define SH_PREFIX tuplehash #define SH_ELEMENT_TYPE TupleHashEntryData #define SH_KEY_TYPE MinimalTuple #define SH_SCOPE extern #define SH_DECLARE #include "lib/simplehash.h" //----------------------------------------------------------------------------------- //----------------------------------------------------------------------------------- //src/backend/nodes/tidbitmap.c /* define hashtable mapping block numbers to PagetableEntry's */ #define SH_USE_NONDEFAULT_ALLOCATOR #define SH_PREFIX pagetable #define SH_ELEMENT_TYPE PagetableEntry #define SH_KEY_TYPE BlockNumber #define SH_KEY blockno #define SH_HASH_KEY(tb, key) murmurhash32(key) #define SH_EQUAL(tb, a, b) a == b #define SH_SCOPE static inline #define SH_DEFINE #define SH_DECLARE #include "lib/simplehash.h" //----------------------------------------------------------------------------------- /* * simplehash.h * * Hash table implementation which will be specialized to user-defined * types, by including this file to generate the required code. It's * probably not worthwhile to do so for hash tables that aren't performance * or space sensitive. * 用户自定义类型Hash表实现,包含此文件用于产生相应的代码. * 对于那些空间和性能都不敏感的哈希表,可能不值得这样做. * * Usage notes: * * To generate a hash-table and associated functions for a use case several * macros have to be #define'ed before this file is included. Including * the file #undef's all those, so a new hash table can be generated * afterwards. * The relevant parameters are: * - SH_PREFIX - prefix for all symbol names generated. A prefix of 'foo' * will result in hash table type 'foo_hash' and functions like * 'foo_insert'/'foo_lookup' and so forth. * - SH_ELEMENT_TYPE - type of the contained elements * - SH_KEY_TYPE - type of the hashtable's key * - SH_DECLARE - if defined function prototypes and type declarations are * generated * - SH_DEFINE - if defined function definitions are generated * - SH_SCOPE - in which scope (e.g. extern, static inline) do function * declarations reside * - SH_USE_NONDEFAULT_ALLOCATOR - if defined no element allocator functions * are defined, so you can supply your own * The following parameters are only relevant when SH_DEFINE is defined: * - SH_KEY - name of the element in SH_ELEMENT_TYPE containing the hash key * - SH_EQUAL(table, a, b) - compare two table keys * - SH_HASH_KEY(table, key) - generate hash for the key * - SH_STORE_HASH - if defined the hash is stored in the elements * - SH_GET_HASH(tb, a) - return the field to store the hash in * * For examples of usage look at simplehash.c (file local definition) and * execnodes.h/execGrouping.c (exposed declaration, file local * implementation). * * 使用提示: * 在该文件被包含前,自行定义相应的宏,用于生成哈希表和相关的函数. * 相关的参数包括: * - SH_PREFIX - 所有标识符名称的前缀.比如前缀'foo', 产生的哈希表类型为foo_hash,函数为foo_insert/foo_lookup等. - SH_ELEMENT_TYPE - 哈希表元素类型 - SH_KEY_TYPE - 哈希表键类型 - SH_DECLARE - 如存在此宏定义,则生成函数原型和类型声明 - SH_DEFINE - 如存在此宏定义,则生成函数定义 - SH_SCOPE - 函数作用域(如extern,static inline等) - SH_USE_NONDEFAULT_ALLOCATOR - 如存在此宏定义,则不会定义元素分配器函数,自行提供 下面这些参数在定义了SH_DEFINE宏时才会生效: - SH_KEY - 包含了hash key的SH_ELEMENT_TYPE的元素名称 - SH_EQUAL(table, a, b) - 比较两个键 - SH_HASH_KEY(table, key) - 为键生成哈希值 - SH_STORE_HASH - 如存在此宏定义,哈希值存储在元素中 - SH_GET_HASH(tb, a) - 返回存储哈希值的字段 * * Hash table design: * * The hash table design chosen is a variant of linear open-addressing. The * reason for doing so is that linear addressing is CPU cache & pipeline * friendly. The biggest disadvantage of simple linear addressing schemes * are highly variable lookup times due to clustering, and deletions * leaving a lot of tombstones around. To address these issues a variant * of "robin hood" hashing is employed. Robin hood hashing optimizes * chaining lengths by moving elements close to their optimal bucket * ("rich" elements), out of the way if a to-be-inserted element is further * away from its optimal position (i.e. it's "poor"). While that can make * insertions slower, the average lookup performance is a lot better, and * higher fill factors can be used in a still performant manner. To avoid * tombstones - which normally solve the issue that a deleted node's * presence is relevant to determine whether a lookup needs to continue * looking or is done - buckets following a deleted element are shifted * backwards, unless they're empty or already at their optimal position. * * 哈希表设计: * 我们选择的哈希表设计是线性开放寻址的一种变体. * 之所以选择这种设计是因为线性寻址是CPU cache & pipeline友好的. * 简单线性寻址模式最大的缺点是由于集群导致查找时间会高度可变,而且删除操作会留下大量的无用位置. * 为了解决这些问题,使用了"robin hood"哈希变体. * "robin hood"哈希通过将元素移动到最优bucket("rich"元素)附近来优化链长度, * 如果要插入的元素离它的最优位置较远的话. * 虽然这会导致插入变慢,但平均检索的性能则会大幅提升,而且天有更高的填充因子. * 为了避免无用位置 - 用于解决删除节点的存在与否以及确定是否需要是否继续检索或执行查找相关的问题 * - 随着删除的元素的变换,buckents会向后移动,除非它们是空的或者已经处于最佳位置. */ /* helpers */ //助手宏定义,比如组装名称等等 #define SH_MAKE_PREFIX(a) CppConcat(a,_) #define SH_MAKE_NAME(name) SH_MAKE_NAME_(SH_MAKE_PREFIX(SH_PREFIX),name) #define SH_MAKE_NAME_(a,b) CppConcat(a,b) /* name macros for: */ /* type declarations */ //类型声明 #define SH_TYPE SH_MAKE_NAME(hash) #define SH_STATUS SH_MAKE_NAME(status) #define SH_STATUS_EMPTY SH_MAKE_NAME(EMPTY) #define SH_STATUS_IN_USE SH_MAKE_NAME(IN_USE) #define SH_ITERATOR SH_MAKE_NAME(iterator) /* function declarations */ //函数声明 #define SH_CREATE SH_MAKE_NAME(create) #define SH_DESTROY SH_MAKE_NAME(destroy) #define SH_RESET SH_MAKE_NAME(reset) #define SH_INSERT SH_MAKE_NAME(insert) #define SH_DELETE SH_MAKE_NAME(delete) #define SH_LOOKUP SH_MAKE_NAME(lookup) #define SH_GROW SH_MAKE_NAME(grow) #define SH_START_ITERATE SH_MAKE_NAME(start_iterate) #define SH_START_ITERATE_AT SH_MAKE_NAME(start_iterate_at) #define SH_ITERATE SH_MAKE_NAME(iterate) #define SH_ALLOCATE SH_MAKE_NAME(allocate) #define SH_FREE SH_MAKE_NAME(free) #define SH_STAT SH_MAKE_NAME(stat) /* internal helper functions (no externally visible prototypes) */ //内部助手函数(非外部可见原型) #define SH_COMPUTE_PARAMETERS SH_MAKE_NAME(compute_parameters) #define SH_NEXT SH_MAKE_NAME(next) #define SH_PREV SH_MAKE_NAME(prev) #define SH_DISTANCE_FROM_OPTIMAL SH_MAKE_NAME(distance) #define SH_INITIAL_BUCKET SH_MAKE_NAME(initial_bucket) #define SH_ENTRY_HASH SH_MAKE_NAME(entry_hash) /* generate forward declarations necessary to use the hash table */ //如定义了SH_DECLARE,则生成使用哈希表所需的声明 #ifdef SH_DECLARE /* type definitions */ typedef struct SH_TYPE { /* * Size of data / bucket array, 64 bits to handle UINT32_MAX sized hash * tables. Note that the maximum number of elements is lower * (SH_MAX_FILLFACTOR) */ uint64 size; /* how many elements have valid contents */ uint32 members; /* mask for bucket and size calculations, based on size */ uint32 sizemask; /* boundary after which to grow hashtable */ uint32 grow_threshold; /* hash buckets */ SH_ELEMENT_TYPE *data; /* memory context to use for allocations */ MemoryContext ctx; /* user defined data, useful for callbacks */ void *private_data; } SH_TYPE;//实际是tuplehash_hash typedef enum SH_STATUS { SH_STATUS_EMPTY = 0x00, SH_STATUS_IN_USE = 0x01 } SH_STATUS; typedef struct SH_ITERATOR { uint32 cur; /* current element */ uint32 end; bool done; /* iterator exhausted? */ } SH_ITERATOR; /* externally visible function prototypes */ SH_SCOPE SH_TYPE *SH_CREATE(MemoryContext ctx, uint32 nelements, void *private_data); SH_SCOPE void SH_DESTROY(SH_TYPE * tb); SH_SCOPE void SH_RESET(SH_TYPE * tb); SH_SCOPE void SH_GROW(SH_TYPE * tb, uint32 newsize); SH_SCOPE SH_ELEMENT_TYPE *SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found); SH_SCOPE SH_ELEMENT_TYPE *SH_LOOKUP(SH_TYPE * tb, SH_KEY_TYPE key); SH_SCOPE bool SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key); SH_SCOPE void SH_START_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter); SH_SCOPE void SH_START_ITERATE_AT(SH_TYPE * tb, SH_ITERATOR * iter, uint32 at); SH_SCOPE SH_ELEMENT_TYPE *SH_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter); SH_SCOPE void SH_STAT(SH_TYPE * tb); #endif /* SH_DECLARE */ /* generate implementation of the hash table */ //如定义了宏SH_DEFINE,则生成Hash表的实现 #ifdef SH_DEFINE #include "utils/memutils.h" /* max data array size,we allow up to PG_UINT32_MAX buckets, including 0 */ #define SH_MAX_SIZE (((uint64) PG_UINT32_MAX) + 1) /* normal fillfactor, unless already close to maximum */ #ifndef SH_FILLFACTOR #define SH_FILLFACTOR (0.9) #endif /* increase fillfactor if we otherwise would error out */ #define SH_MAX_FILLFACTOR (0.98) /* grow if actual and optimal location bigger than */ #ifndef SH_GROW_MAX_DIB #define SH_GROW_MAX_DIB 25 #endif /* grow if more than elements to move when inserting */ #ifndef SH_GROW_MAX_MOVE #define SH_GROW_MAX_MOVE 150 #endif #ifndef SH_GROW_MIN_FILLFACTOR /* but do not grow due to SH_GROW_MAX_* if below */ #define SH_GROW_MIN_FILLFACTOR 0.1 #endif #ifdef SH_STORE_HASH #define SH_COMPARE_KEYS(tb, ahash, akey, b) (ahash == SH_GET_HASH(tb, b) && SH_EQUAL(tb, b->SH_KEY, akey)) #else #define SH_COMPARE_KEYS(tb, ahash, akey, b) (SH_EQUAL(tb, b->SH_KEY, akey)) #endif /* FIXME: can we move these to a central location? */ /* calculate ceil(log base 2) of num */ static inline uint64 sh_log2(uint64 num) { int i; uint64 limit; for (i = 0, limit = 1; limit < num; i++, limit <<= 1) ; return i; } /* calculate first power of 2 >= num */ static inline uint64 sh_pow2(uint64 num) { return ((uint64) 1) << sh_log2(num); } /* * Compute sizing parameters for hashtable. Called when creating and growing * the hashtable. */ static inline void SH_COMPUTE_PARAMETERS(SH_TYPE * tb, uint32 newsize) { uint64 size; /* supporting zero sized hashes would complicate matters */ size = Max(newsize, 2); /* round up size to the next power of 2, that's how bucketing works */ size = sh_pow2(size); Assert(size <= SH_MAX_SIZE); /* * Verify that allocation of ->data is possible on this platform, without * overflowing Size. */ if ((((uint64) sizeof(SH_ELEMENT_TYPE)) * size) >= MaxAllocHugeSize) elog(ERROR, "hash table too large"); /* now set size */ tb->size = size; if (tb->size == SH_MAX_SIZE) tb->sizemask = 0; else tb->sizemask = tb->size - 1; /* * Compute the next threshold at which we need to grow the hash table * again. */ if (tb->size == SH_MAX_SIZE) tb->grow_threshold = ((double) tb->size) * SH_MAX_FILLFACTOR; else tb->grow_threshold = ((double) tb->size) * SH_FILLFACTOR; } /* return the optimal bucket for the hash */ static inline uint32 SH_INITIAL_BUCKET(SH_TYPE * tb, uint32 hash) { return hash & tb->sizemask; } /* return next bucket after the current, handling wraparound */ static inline uint32 SH_NEXT(SH_TYPE * tb, uint32 curelem, uint32 startelem) { curelem = (curelem + 1) & tb->sizemask; Assert(curelem != startelem); return curelem; } /* return bucket before the current, handling wraparound */ static inline uint32 SH_PREV(SH_TYPE * tb, uint32 curelem, uint32 startelem) { curelem = (curelem - 1) & tb->sizemask; Assert(curelem != startelem); return curelem; } /* return distance between bucket and its optimal position */ static inline uint32 SH_DISTANCE_FROM_OPTIMAL(SH_TYPE * tb, uint32 optimal, uint32 bucket) { if (optimal <= bucket) return bucket - optimal; else return (tb->size + bucket) - optimal; } static inline uint32 SH_ENTRY_HASH(SH_TYPE * tb, SH_ELEMENT_TYPE * entry) { #ifdef SH_STORE_HASH return SH_GET_HASH(tb, entry); #else return SH_HASH_KEY(tb, entry->SH_KEY); #endif } /* default memory allocator function */ static inline void *SH_ALLOCATE(SH_TYPE * type, Size size); static inline void SH_FREE(SH_TYPE * type, void *pointer); #ifndef SH_USE_NONDEFAULT_ALLOCATOR /* default memory allocator function */ static inline void * SH_ALLOCATE(SH_TYPE * type, Size size) { return MemoryContextAllocExtended(type->ctx, size, MCXT_ALLOC_HUGE | MCXT_ALLOC_ZERO); } /* default memory free function */ static inline void SH_FREE(SH_TYPE * type, void *pointer) { pfree(pointer); } #endif /* * Create a hash table with enough space for `nelements` distinct members. * Memory for the hash table is allocated from the passed-in context. If * desired, the array of elements can be allocated using a passed-in allocator; * this could be useful in order to place the array of elements in a shared * memory, or in a context that will outlive the rest of the hash table. * Memory other than for the array of elements will still be allocated from * the passed-in context. */ SH_SCOPE SH_TYPE * SH_CREATE(MemoryContext ctx, uint32 nelements, void *private_data) { SH_TYPE *tb; uint64 size; tb = MemoryContextAllocZero(ctx, sizeof(SH_TYPE)); tb->ctx = ctx; tb->private_data = private_data; /* increase nelements by fillfactor, want to store nelements elements */ size = Min((double) SH_MAX_SIZE, ((double) nelements) / SH_FILLFACTOR); SH_COMPUTE_PARAMETERS(tb, size); tb->data = SH_ALLOCATE(tb, sizeof(SH_ELEMENT_TYPE) * tb->size); return tb; } /* destroy a previously created hash table */ SH_SCOPE void SH_DESTROY(SH_TYPE * tb) { SH_FREE(tb, tb->data); pfree(tb); } /* reset the contents of a previously created hash table */ SH_SCOPE void SH_RESET(SH_TYPE * tb) { memset(tb->data, 0, sizeof(SH_ELEMENT_TYPE) * tb->size); tb->members = 0; } /* * Grow a hash table to at least `newsize` buckets. * * Usually this will automatically be called by insertions/deletions, when * necessary. But resizing to the exact input size can be advantageous * performance-wise, when known at some point. */ SH_SCOPE void SH_GROW(SH_TYPE * tb, uint32 newsize) { uint64 oldsize = tb->size; SH_ELEMENT_TYPE *olddata = tb->data; SH_ELEMENT_TYPE *newdata; uint32 i; uint32 startelem = 0; uint32 copyelem; Assert(oldsize == sh_pow2(oldsize)); Assert(oldsize != SH_MAX_SIZE); Assert(oldsize < newsize); /* compute parameters for new table */ SH_COMPUTE_PARAMETERS(tb, newsize); tb->data = SH_ALLOCATE(tb, sizeof(SH_ELEMENT_TYPE) * tb->size); newdata = tb->data; /* * Copy entries from the old data to newdata. We theoretically could use * SH_INSERT here, to avoid code duplication, but that's more general than * we need. We neither want tb->members increased, nor do we need to do * deal with deleted elements, nor do we need to compare keys. So a * special-cased implementation is lot faster. As resizing can be time * consuming and frequent, that's worthwhile to optimize. * * To be able to simply move entries over, we have to start not at the * first bucket (i.e olddata[0]), but find the first bucket that's either * empty, or is occupied by an entry at its optimal position. Such a * bucket has to exist in any table with a load factor under 1, as not all * buckets are occupied, i.e. there always has to be an empty bucket. By * starting at such a bucket we can move the entries to the larger table, * without having to deal with conflicts. */ /* search for the first element in the hash that's not wrapped around */ for (i = 0; i < oldsize; i++) { SH_ELEMENT_TYPE *oldentry = &olddata[i]; uint32 hash; uint32 optimal; if (oldentry->status != SH_STATUS_IN_USE) { startelem = i; break; } hash = SH_ENTRY_HASH(tb, oldentry); optimal = SH_INITIAL_BUCKET(tb, hash); if (optimal == i) { startelem = i; break; } } /* and copy all elements in the old table */ copyelem = startelem; for (i = 0; i < oldsize; i++) { SH_ELEMENT_TYPE *oldentry = &olddata[copyelem]; if (oldentry->status == SH_STATUS_IN_USE) { uint32 hash; uint32 startelem; uint32 curelem; SH_ELEMENT_TYPE *newentry; hash = SH_ENTRY_HASH(tb, oldentry); startelem = SH_INITIAL_BUCKET(tb, hash); curelem = startelem; /* find empty element to put data into */ while (true) { newentry = &newdata[curelem]; if (newentry->status == SH_STATUS_EMPTY) { break; } curelem = SH_NEXT(tb, curelem, startelem); } /* copy entry to new slot */ memcpy(newentry, oldentry, sizeof(SH_ELEMENT_TYPE)); } /* can't use SH_NEXT here, would use new size */ copyelem++; if (copyelem >= oldsize) { copyelem = 0; } } SH_FREE(tb, olddata); } /* * Insert the key key into the hash-table, set *found to true if the key * already exists, false otherwise. Returns the hash-table entry in either * case. * 插入Key到哈希表中,如Key已存在则设置*found为T,否则为F. * 返回哈希表条目. * 在聚合运算场景中: * SH_ELEMENT_TYPE --> TupleHashEntryData * SH_INSERT --> tuplehash_insert */ SH_SCOPE SH_ELEMENT_TYPE * SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found) { uint32 hash = SH_HASH_KEY(tb, key);//TupleHashTableHash,Key类型为MinimalTuple uint32 startelem; uint32 curelem; SH_ELEMENT_TYPE *data; uint32 insertdist; restart: insertdist = 0; /* * We do the grow check even if the key is actually present, to avoid * doing the check inside the loop. This also lets us avoid having to * re-find our position in the hashtable after resizing. * 就算Key实际存在但我们也会执行扩展检查以避免在循环中进行检查. * 这同时可以让我们避免不得不在调整空间后重新在哈希表中检索位置. * * Note that this also reached when resizing the table due to * SH_GROW_MAX_DIB / SH_GROW_MAX_MOVE. * 因为SH_GROW_MAX_DIB / SH_GROW_MAX_MOVE而调整空间时也会执行这些逻辑. */ if (unlikely(tb->members >= tb->grow_threshold)) { if (tb->size == SH_MAX_SIZE) { elog(ERROR, "hash table size exceeded"); } /* * When optimizing, it can be very useful to print these out. * 在优化的时候,打印这些信息会很有用. */ /* SH_STAT(tb); */ SH_GROW(tb, tb->size * 2); /* SH_STAT(tb); */ } /* perform insert, start bucket search at optimal location */ //执行插入,在优化的位置开始bucket搜索 data = tb->data; startelem = SH_INITIAL_BUCKET(tb, hash);//开始位置 curelem = startelem;//当前哈希表中的元素 while (true) { uint32 curdist; uint32 curhash; uint32 curoptimal; SH_ELEMENT_TYPE *entry = &data[curelem];//SH_ELEMENT_TYPE --> TupleHashEntryData /* any empty bucket can directly be used */ //是否有空bucket可以直接使用? if (entry->status == SH_STATUS_EMPTY) { //--------- 条目状态为空 //成员加1 tb->members++; //Key赋值 entry->SH_KEY = key; #ifdef SH_STORE_HASH //是否存在hash值? SH_GET_HASH(tb, entry) = hash; #endif //调整条目状态 entry->status = SH_STATUS_IN_USE; //设置相关变量 *found = false; //返回entry return entry; } /* * If the bucket is not empty, we either found a match (in which case * we're done), or we have to decide whether to skip over or move the * colliding entry. When the colliding element's distance to its * optimal position is smaller than the to-be-inserted entry's, we * shift the colliding entry (and its followers) forward by one. * 如果bucket非空,这时候要么会发现匹配Key,要么确定是否跳过或者移动出现冲突的etnry. * 如果出现出现冲突的元素距离优化位置小于即将插入的条目,则切换冲突条目. */ /* #ifdef SH_STORE_HASH #define SH_COMPARE_KEYS(tb, ahash, akey, b) (ahash == SH_GET_HASH(tb, b) && SH_EQUAL(tb, b->SH_KEY, akey)) #else #define SH_COMPARE_KEYS(tb, ahash, akey, b) (SH_EQUAL(tb, b->SH_KEY, akey)) #endif SH_EQUAL --> TupleHashTableMatch */ if (SH_COMPARE_KEYS(tb, hash, key, entry))//TupleHashTableMatch { //找到了相应的Key Assert(entry->status == SH_STATUS_IN_USE); *found = true; //返回条目 return entry; } //当前的哈希值 curhash = SH_ENTRY_HASH(tb, entry); //当前优化的位置 curoptimal = SH_INITIAL_BUCKET(tb, curhash); //距离 curdist = SH_DISTANCE_FROM_OPTIMAL(tb, curoptimal, curelem); if (insertdist > curdist) { SH_ELEMENT_TYPE *lastentry = entry; uint32 emptyelem = curelem; uint32 moveelem; int32 emptydist = 0; /* find next empty bucket */ while (true) { SH_ELEMENT_TYPE *emptyentry; emptyelem = SH_NEXT(tb, emptyelem, startelem); emptyentry = &data[emptyelem]; if (emptyentry->status == SH_STATUS_EMPTY) { lastentry = emptyentry; break; } /* * To avoid negative consequences from overly imbalanced * hashtables, grow the hashtable if collisions would require * us to move a lot of entries. The most likely cause of such * imbalance is filling a (currently) small table, from a * currently big one, in hash-table order. Don't grow if the * hashtable would be too empty, to prevent quick space * explosion for some weird edge cases. */ if (unlikely(++emptydist > SH_GROW_MAX_MOVE) && ((double) tb->members / tb->size) >= SH_GROW_MIN_FILLFACTOR) { tb->grow_threshold = 0; goto restart; } } /* shift forward, starting at last occupied element */ /* * TODO: This could be optimized to be one memcpy in may cases, * excepting wrapping around at the end of ->data. Hasn't shown up * in profiles so far though. */ moveelem = emptyelem; while (moveelem != curelem) { SH_ELEMENT_TYPE *moveentry; moveelem = SH_PREV(tb, moveelem, startelem); moveentry = &data[moveelem]; memcpy(lastentry, moveentry, sizeof(SH_ELEMENT_TYPE)); lastentry = moveentry; } /* and fill the now empty spot */ tb->members++; entry->SH_KEY = key; #ifdef SH_STORE_HASH SH_GET_HASH(tb, entry) = hash; #endif entry->status = SH_STATUS_IN_USE; *found = false; return entry; } curelem = SH_NEXT(tb, curelem, startelem); insertdist++; /* * To avoid negative consequences from overly imbalanced hashtables, * grow the hashtable if collisions lead to large runs. The most * likely cause of such imbalance is filling a (currently) small * table, from a currently big one, in hash-table order. Don't grow * if the hashtable would be too empty, to prevent quick space * explosion for some weird edge cases. */ if (unlikely(insertdist > SH_GROW_MAX_DIB) && ((double) tb->members / tb->size) >= SH_GROW_MIN_FILLFACTOR) { tb->grow_threshold = 0; goto restart; } } } /* * Lookup up entry in hash table. Returns NULL if key not present. */ SH_SCOPE SH_ELEMENT_TYPE * SH_LOOKUP(SH_TYPE * tb, SH_KEY_TYPE key) { uint32 hash = SH_HASH_KEY(tb, key); const uint32 startelem = SH_INITIAL_BUCKET(tb, hash); uint32 curelem = startelem; while (true) { SH_ELEMENT_TYPE *entry = &tb->data[curelem]; if (entry->status == SH_STATUS_EMPTY) { return NULL; } Assert(entry->status == SH_STATUS_IN_USE); if (SH_COMPARE_KEYS(tb, hash, key, entry)) return entry; /* * TODO: we could stop search based on distance. If the current * buckets's distance-from-optimal is smaller than what we've skipped * already, the entry doesn't exist. Probably only do so if * SH_STORE_HASH is defined, to avoid re-computing hashes? */ curelem = SH_NEXT(tb, curelem, startelem); } } /* * Delete entry from hash table. Returns whether to-be-deleted key was * present. */ SH_SCOPE bool SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key) { uint32 hash = SH_HASH_KEY(tb, key); uint32 startelem = SH_INITIAL_BUCKET(tb, hash); uint32 curelem = startelem; while (true) { SH_ELEMENT_TYPE *entry = &tb->data[curelem]; if (entry->status == SH_STATUS_EMPTY) return false; if (entry->status == SH_STATUS_IN_USE && SH_COMPARE_KEYS(tb, hash, key, entry)) { SH_ELEMENT_TYPE *lastentry = entry; tb->members--; /* * Backward shift following elements till either an empty element * or an element at its optimal position is encountered. * * While that sounds expensive, the average chain length is short, * and deletions would otherwise require tombstones. */ while (true) { SH_ELEMENT_TYPE *curentry; uint32 curhash; uint32 curoptimal; curelem = SH_NEXT(tb, curelem, startelem); curentry = &tb->data[curelem]; if (curentry->status != SH_STATUS_IN_USE) { lastentry->status = SH_STATUS_EMPTY; break; } curhash = SH_ENTRY_HASH(tb, curentry); curoptimal = SH_INITIAL_BUCKET(tb, curhash); /* current is at optimal position, done */ if (curoptimal == curelem) { lastentry->status = SH_STATUS_EMPTY; break; } /* shift */ memcpy(lastentry, curentry, sizeof(SH_ELEMENT_TYPE)); lastentry = curentry; } return true; } /* TODO: return false; if distance too big */ curelem = SH_NEXT(tb, curelem, startelem); } } /* * Initialize iterator. */ SH_SCOPE void SH_START_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter) { int i; uint64 startelem = PG_UINT64_MAX; /* * Search for the first empty element. As deletions during iterations are * supported, we want to start/end at an element that cannot be affected * by elements being shifted. */ for (i = 0; i < tb->size; i++) { SH_ELEMENT_TYPE *entry = &tb->data[i]; if (entry->status != SH_STATUS_IN_USE) { startelem = i; break; } } Assert(startelem < SH_MAX_SIZE); /* * Iterate backwards, that allows the current element to be deleted, even * if there are backward shifts */ iter->cur = startelem; iter->end = iter->cur; iter->done = false; } /* * Initialize iterator to a specific bucket. That's really only useful for * cases where callers are partially iterating over the hashspace, and that * iteration deletes and inserts elements based on visited entries. Doing that * repeatedly could lead to an unbalanced keyspace when always starting at the * same position. */ SH_SCOPE void SH_START_ITERATE_AT(SH_TYPE * tb, SH_ITERATOR * iter, uint32 at) { /* * Iterate backwards, that allows the current element to be deleted, even * if there are backward shifts. */ iter->cur = at & tb->sizemask; /* ensure at is within a valid range */ iter->end = iter->cur; iter->done = false; } /* * Iterate over all entries in the hash-table. Return the next occupied entry, * or NULL if done. * * During iteration the current entry in the hash table may be deleted, * without leading to elements being skipped or returned twice. Additionally * the rest of the table may be modified (i.e. there can be insertions or * deletions), but if so, there's neither a guarantee that all nodes are * visited at least once, nor a guarantee that a node is visited at most once. */ SH_SCOPE SH_ELEMENT_TYPE * SH_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter) { while (!iter->done) { SH_ELEMENT_TYPE *elem; elem = &tb->data[iter->cur]; /* next element in backward direction */ iter->cur = (iter->cur - 1) & tb->sizemask; if ((iter->cur & tb->sizemask) == (iter->end & tb->sizemask)) iter->done = true; if (elem->status == SH_STATUS_IN_USE) { return elem; } } return NULL; } /* * Report some statistics about the state of the hashtable. For * debugging/profiling purposes only. */ SH_SCOPE void SH_STAT(SH_TYPE * tb) { uint32 max_chain_length = 0; uint32 total_chain_length = 0; double avg_chain_length; double fillfactor; uint32 i; uint32 *collisions = palloc0(tb->size * sizeof(uint32)); uint32 total_collisions = 0; uint32 max_collisions = 0; double avg_collisions; for (i = 0; i < tb->size; i++) { uint32 hash; uint32 optimal; uint32 dist; SH_ELEMENT_TYPE *elem; elem = &tb->data[i]; if (elem->status != SH_STATUS_IN_USE) continue; hash = SH_ENTRY_HASH(tb, elem); optimal = SH_INITIAL_BUCKET(tb, hash); dist = SH_DISTANCE_FROM_OPTIMAL(tb, optimal, i); if (dist > max_chain_length) max_chain_length = dist; total_chain_length += dist; collisions[optimal]++; } for (i = 0; i < tb->size; i++) { uint32 curcoll = collisions[i]; if (curcoll == 0) continue; /* single contained element is not a collision */ curcoll--; total_collisions += curcoll; if (curcoll > max_collisions) max_collisions = curcoll; } if (tb->members > 0) { fillfactor = tb->members / ((double) tb->size); avg_chain_length = ((double) total_chain_length) / tb->members; avg_collisions = ((double) total_collisions) / tb->members; } else { fillfactor = 0; avg_chain_length = 0; avg_collisions = 0; } elog(LOG, "size: " UINT64_FORMAT ", members: %u, filled: %f, total chain: %u, max chain: %u, avg chain: %f, total_collisions: %u, max_collisions: %i, avg_collisions: %f", tb->size, tb->members, fillfactor, total_chain_length, max_chain_length, avg_chain_length, total_collisions, max_collisions, avg_collisions); } #endif /* SH_DEFINE */ /* undefine external parameters, so next hash table can be defined */ #undef SH_PREFIX #undef SH_KEY_TYPE #undef SH_KEY #undef SH_ELEMENT_TYPE #undef SH_HASH_KEY #undef SH_SCOPE #undef SH_DECLARE #undef SH_DEFINE #undef SH_GET_HASH #undef SH_STORE_HASH #undef SH_USE_NONDEFAULT_ALLOCATOR /* undefine locally declared macros */ #undef SH_MAKE_PREFIX #undef SH_MAKE_NAME #undef SH_MAKE_NAME_ #undef SH_FILLFACTOR #undef SH_MAX_FILLFACTOR #undef SH_GROW_MAX_DIB #undef SH_GROW_MAX_MOVE #undef SH_GROW_MIN_FILLFACTOR #undef SH_MAX_SIZE /* types */ #undef SH_TYPE #undef SH_STATUS #undef SH_STATUS_EMPTY #undef SH_STATUS_IN_USE #undef SH_ITERATOR /* external function names */ #undef SH_CREATE #undef SH_DESTROY #undef SH_RESET #undef SH_INSERT #undef SH_DELETE #undef SH_LOOKUP #undef SH_GROW #undef SH_START_ITERATE #undef SH_START_ITERATE_AT #undef SH_ITERATE #undef SH_ALLOCATE #undef SH_FREE #undef SH_STAT /* internal function names */ #undef SH_COMPUTE_PARAMETERS #undef SH_COMPARE_KEYS #undef SH_INITIAL_BUCKET #undef SH_NEXT #undef SH_PREV #undef SH_DISTANCE_FROM_OPTIMAL #undef SH_ENTRY_HASH ``` ### 三、跟踪分析 下面以tuplehash_insert为例,分析simplehash插入哈希表的实现. 测试脚本 ``` -- 禁用并行 set max_parallel_workers_per_gather=0; select bh,avg(c1),min(c1),max(c2) from t_agg_simple group by bh; ``` 跟踪分析 ``` (gdb) b tuplehash_insert Breakpoint 1 at 0x6d2a27: file ../../../src/include/lib/simplehash.h, line 490. (gdb) ``` 输入参数 ``` (gdb) p *tb $1 = {size = 256, members = 0, sizemask = 255, grow_threshold = 230, data = 0x1cc2a10, ctx = 0x1c9b320, private_data = 0x1cb88a0} (gdb) ``` 判断是否需要增长 ``` (gdb) n 497 insertdist = 0; (gdb) 507 if (unlikely(tb->members >= tb->grow_threshold)) (gdb) p tb->members $2 = 0 (gdb) p tb->grow_threshold $3 = 230 ``` 执行插入,在优化的位置开始bucket搜索 获取条目数组(TupleHashEntryData \*指针),初始化开始元素和当前元素 ``` (gdb) n 523 data = tb->data; (gdb) 524 startelem = SH_INITIAL_BUCKET(tb, hash); (gdb) p *data $4 = {firstTuple = 0x0, additional = 0x0, status = 0, hash = 0} (gdb) n 525 curelem = startelem; (gdb) p startelem $5 = 114 (gdb) p hash $6 = 443809650 (gdb) ``` 进入循环,寻找空闲的bucket执行插入 ``` (gdb) n 531 SH_ELEMENT_TYPE *entry = &data[curelem]; (gdb) n 534 if (entry->status == SH_STATUS_EMPTY) (gdb) p *entry $7 = {firstTuple = 0x0, additional = 0x0, status = 0, hash = 0} (gdb) p *data $8 = {firstTuple = 0x0, additional = 0x0, status = 0, hash = 0} (gdb) p data[255] $9 = {firstTuple = 0x0, additional = 0x0, status = 0, hash = 0} (gdb) n 536 tb->members++; (gdb) 537 entry->SH_KEY = key; (gdb) p *tb $10 = {size = 256, members = 1, sizemask = 255, grow_threshold = 230, data = 0x1cc2a10, ctx = 0x1c9b320, private_data = 0x1cb88a0} (gdb) n 539 SH_GET_HASH(tb, entry) = hash; (gdb) 541 entry->status = SH_STATUS_IN_USE; (gdb) p *entry $11 = {firstTuple = 0x0, additional = 0x0, status = 0, hash = 443809650} (gdb) n 542 *found = false; (gdb) 543 return entry; (gdb) p *entry $12 = {firstTuple = 0x0, additional = 0x0, status = 1, hash = 443809650} (gdb) ``` 完成函数调用,返回entry ``` (gdb) n 652 } (gdb) LookupTupleHashEntry (hashtable=0x1cb88a0, slot=0x1c9d248, isnew=0x7ffd1348e797) at execGrouping.c:303 303 if (found) (gdb) ``` 回到LookupTupleHashEntry ``` (gdb) LookupTupleHashEntry (hashtable=0x1cb88a0, slot=0x1c9d248, isnew=0x7ffd1348e797) at execGrouping.c:303 303 if (found) (gdb) n 311 *isnew = true; (gdb) 313 entry->additional = NULL; (gdb) 314 MemoryContextSwitchTo(hashtable->tablecxt); (gdb) 316 entry->firstTuple = ExecCopySlotMinimalTuple(slot); (gdb) 324 MemoryContextSwitchTo(oldContext); ``` 查看tuple数据 ``` (gdb) p *entry $13 = {firstTuple = 0x1cb2498, additional = 0x0, status = 1, hash = 443809650} (gdb) x/7x entry->firstTuple->t_bits 0x1cb24a7: 0x00 0x0b 0x47 0x5a 0x30 0x31 0x7e (gdb) x/7c entry->firstTuple->t_bits 0x1cb24a7: 0 '\000' 11 '\v' 71 'G' 90 'Z' 48 '0' 49 '1' 126 '~' ``` 下一次调用,这次出现了碰撞 ``` (gdb) c Continuing. Breakpoint 1, tuplehash_insert (tb=0x1cb8730, key=0x0, found=0x7ffd1348e757) at ../../../src/include/lib/simplehash.h:490 490 uint32 hash = SH_HASH_KEY(tb, key); (gdb) n 497 insertdist = 0; (gdb) p hash $15 = 4237773170 (gdb) n 507 if (unlikely(tb->members >= tb->grow_threshold)) (gdb) 523 data = tb->data; (gdb) 524 startelem = SH_INITIAL_BUCKET(tb, hash); (gdb) p data[0] $16 = {firstTuple = 0x0, additional = 0x0, status = 0, hash = 0} (gdb) n 525 curelem = startelem; (gdb) 531 SH_ELEMENT_TYPE *entry = &data[curelem]; (gdb) p startelem $17 = 114 (gdb) p curelem $18 = 114 (gdb) p data[curelem] $19 = {firstTuple = 0x1cb2498, additional = 0x1cb24d0, status = 1, hash = 443809650} (gdb) n 534 if (entry->status == SH_STATUS_EMPTY) (gdb) 554 if (SH_COMPARE_KEYS(tb, hash, key, entry)) (gdb) 561 curhash = SH_ENTRY_HASH(tb, entry); (gdb) 562 curoptimal = SH_INITIAL_BUCKET(tb, curhash); (gdb) p curhash $20 = 443809650 (gdb) n 563 curdist = SH_DISTANCE_FROM_OPTIMAL(tb, curoptimal, curelem); (gdb) 565 if (insertdist > curdist) (gdb) p curoptimal $21 = 114 (gdb) p curdist $22 = 0 (gdb) n 634 curelem = SH_NEXT(tb, curelem, startelem); (gdb) p insertdist $23 = 0 (gdb) n 635 insertdist++; (gdb) p curelem $24 = 115 (gdb) n 645 if (unlikely(insertdist > SH_GROW_MAX_DIB) && (gdb) 651 } (gdb) 531 SH_ELEMENT_TYPE *entry = &data[curelem]; (gdb) 534 if (entry->status == SH_STATUS_EMPTY) (gdb) 536 tb->members++; (gdb) 537 entry->SH_KEY = key; (gdb) 539 SH_GET_HASH(tb, entry) = hash; (gdb) 541 entry->status = SH_STATUS_IN_USE; (gdb) 542 *found = false; (gdb) 543 return entry; (gdb) p *entry $25 = {firstTuple = 0x0, additional = 0x0, status = 1, hash = 4237773170} (gdb) ``` 回到LookupTupleHashEntry,查看tuple ``` (gdb) LookupTupleHashEntry (hashtable=0x1cb88a0, slot=0x1c9d248, isnew=0x7ffd1348e797) at execGrouping.c:303 303 if (found) (gdb) 311 *isnew = true; (gdb) 313 entry->additional = NULL; (gdb) 314 MemoryContextSwitchTo(hashtable->tablecxt); (gdb) 316 entry->firstTuple = ExecCopySlotMinimalTuple(slot); (gdb) 324 MemoryContextSwitchTo(oldContext); (gdb) p *entry $26 = {firstTuple = 0x1cb2580, additional = 0x0, status = 1, hash = 4237773170} (gdb) p *entry->firstTuple $27 = {t_len = 21, mt_padding = "\000\000\000\000\000", t_infomask2 = 1, t_infomask = 2, t_hoff = 24 '\030', t_bits = 0x1cb258f ""} (gdb) x/7x entry->firstTuple->t_bits 0x1cb258f: 0x00 0x0b 0x47 0x5a 0x30 0x32 0x7e (gdb) x/7c entry->firstTuple->t_bits 0x1cb258f: 0 '\000' 11 '\v' 71 'G' 90 'Z' 48 '0' 50 '2' 126 '~' (gdb) ``` DONE! ### 四、参考资料 [Why Simple Hash Functions Work](https://people.seas.harvard.edu/~salil/research/streamhash-Banff08.pps)