ITPub博客

首页 > 数据库 > PostgreSQL > PostgreSQL 源码解读(185)- 查询#101(聚合函数#6-simplehash)

PostgreSQL 源码解读(185)- 查询#101(聚合函数#6-simplehash)

原创 PostgreSQL 作者:husthxd 时间:2019-05-08 15:14:47 0 删除 编辑

上几节介绍了哈希表的相关实现,主要是”simplehash.h”文件以及”simplehash.h”中的SH_INSERT实现,本节继续介绍聚合函数实现中使用的”simplehash”,包括TupleHashTableHash和TupleHashTableMatch.这两个函数会替换simplehash的SH_HASH_KEY/SH_EQUAL


//src/backend/executor/execGrouping.c
#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

一、数据结构

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;

二、源码解读

TupleHashTableHash
TupleHashTableHash用于计算tuple的哈希值(分组列值)


/*
 * Compute the hash value for a tuple
 * 计算tuple的哈希值
 *
 * The passed-in key is a pointer to TupleHashEntryData.  In an actual hash
 * table entry, the firstTuple field points to a tuple (in MinimalTuple
 * format).  LookupTupleHashEntry sets up a dummy TupleHashEntryData with a
 * NULL firstTuple field --- that cues us to look at the inputslot instead.
 * This convention avoids the need to materialize virtual input tuples unless
 * they actually need to get copied into the table.
 * 传入的key是指向TupleHashEntryData结构体的指针.
 * 在实际的哈希表条目中,firstTuple字段指向一个元组(以MinimalTuple格式保存).
 * LookupTupleHashEntry会使用NULL firstTuple字段设置一个虚拟的TupleHashEntryData.
 *   --- 这可以提示我们转而查看inputslot.
 * 这个转换避免了物化虚拟输入元组,除非它们需要实际拷贝到数据表中.
 *
 * Also, the caller must select an appropriate memory context for running
 * the hash functions. (dynahash.c doesn't change CurrentMemoryContext.)
 * 同时,调用者必须选择合适的内存上下文用于运行哈希函数.
 * (dynahash.c不会改变CurrentMemoryContext)
 */
static uint32
TupleHashTableHash(struct tuplehash_hash *tb, const MinimalTuple tuple)
{
    //Tuple 哈希表
    TupleHashTable hashtable = (TupleHashTable) tb->private_data;
    //列数
    int            numCols = hashtable->numCols;
    //属性编号
    AttrNumber *keyColIdx = hashtable->keyColIdx;
    //哈希key
    uint32        hashkey = hashtable->hash_iv;
    //元组slot
    TupleTableSlot *slot;
    //哈希函数指针
    FmgrInfo   *hashfunctions;
    int            i;
    if (tuple == NULL)//元组为NULL
    {
        /* Process the current input tuple for the table */
        //处理当前输入元组
        slot = hashtable->inputslot;
        hashfunctions = hashtable->in_hash_funcs;
    }
    else
    {
        /*
         * Process a tuple already stored in the table.
         * 处理已存储在数据表中的元组.
         *
         * (this case never actually occurs due to the way simplehash.h is
         * used, as the hash-value is stored in the entries)
         * (这种情况因为simplehash.h的使用,实际上不会发生,因为哈希值存储在条目中)
         */
        slot = hashtable->tableslot;
        //存储MinimalTuple
        ExecStoreMinimalTuple(tuple, slot, false);
        hashfunctions = hashtable->tab_hash_funcs;
    }
    for (i = 0; i < numCols; i++)
    {
        //------- 循环遍历列数
        //获取属性编号
        AttrNumber    att = keyColIdx[i];
        Datum        attr;//属性
        bool        isNull;//是否为NULL?
        /* rotate hashkey left 1 bit at each step */
        //每一步向左移动一位
        hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0);
        //获取属性值
        attr = slot_getattr(slot, att, &isNull);
        //如为null,则哈希key设置为0
        if (!isNull)            /* treat nulls as having hash key 0 */
        {
            //不为NULL
            uint32        hkey;
            //调用哈希函数
            hkey = DatumGetUInt32(FunctionCall1(&hashfunctions[i],
                                                attr));
            hashkey ^= hkey;
        }
    }
    /*
     * The way hashes are combined above, among each other and with the IV,
     * doesn't lead to good bit perturbation. As the IV's goal is to lead to
     * achieve that, perform a round of hashing of the combined hash -
     * resulting in near perfect perturbation.
     * 上面哈希的的组合方式,彼此之间以及与IV的组合方式,都不会导致位扰动.
     * 因为IV存在的目的是实现该目标,执行组合哈希的hashing取整 -- 结果是完美的扰动.
     */
    return murmurhash32(hashkey);
}

TupleHashTableMatch
TupleHashTableMatch用于判断两个tuples是否匹配(有相同的hash值)


/*
 * See whether two tuples (presumably of the same hash value) match
 * 检查两个tuples是否匹配(有相同的hash值)
 *
 * As above, the passed pointers are pointers to TupleHashEntryData.
 * 如上所述,传入的指针指向TupleHashEntryData
 */
static int
TupleHashTableMatch(struct tuplehash_hash *tb, const MinimalTuple tuple1, const MinimalTuple tuple2)
{
    TupleTableSlot *slot1;
    TupleTableSlot *slot2;
    TupleHashTable hashtable = (TupleHashTable) tb->private_data;
    ExprContext *econtext = hashtable->exprcontext;
    /*
     * We assume that simplehash.h will only ever call us with the first
     * argument being an actual table entry, and the second argument being
     * LookupTupleHashEntry's dummy TupleHashEntryData.  The other direction
     * could be supported too, but is not currently required.
     */
    Assert(tuple1 != NULL);
    slot1 = hashtable->tableslot;
    ExecStoreMinimalTuple(tuple1, slot1, false);
    Assert(tuple2 == NULL);
    slot2 = hashtable->inputslot;
    /* For crosstype comparisons, the inputslot must be first */
    econtext->ecxt_innertuple = slot2;
    econtext->ecxt_outertuple = slot1;
    return !ExecQualAndReset(hashtable->cur_eq_func, econtext);
}

三、跟踪分析

测试脚本


-- 禁用并行
set max_parallel_workers_per_gather=0;
select bh,avg(c1),min(c1),max(c2) from t_agg_simple group by bh;

跟踪分析


(gdb) b TupleHashTableHash
Breakpoint 1 at 0x6d3b2b: file execGrouping.c, line 379.
(gdb) b TupleHashTableMatch
Breakpoint 2 at 0x6d3c79: file execGrouping.c, line 446.
(gdb)  
(gdb) c
Continuing.
Breakpoint 1, TupleHashTableHash (tb=0x2dd2720, tuple=0x0) at execGrouping.c:379
379        TupleHashTable hashtable = (TupleHashTable) tb->private_data;
(gdb)

输入参数


(gdb) p *tb
$1 = {size = 256, members = 0, sizemask = 255, grow_threshold = 230, data = 0x2ddca00, ctx = 0x2db5310, 
  private_data = 0x2dd2890}
(gdb) p *tb->data
$2 = {firstTuple = 0x0, additional = 0x0, status = 0, hash = 0}

获取分组列数


(gdb) n
380        int            numCols = hashtable->numCols;
(gdb) p *hashtable
$3 = {hashtab = 0x2dd2720, numCols = 1, keyColIdx = 0x2dd2680, tab_hash_funcs = 0x2db72d0, tab_eq_func = 0x2ddea18, 
  tablecxt = 0x2dcc370, tempcxt = 0x2db7320, entrysize = 24, tableslot = 0x2dd2928, inputslot = 0x2db7238, 
  in_hash_funcs = 0x2db72d0, cur_eq_func = 0x2ddea18, hash_iv = 0, exprcontext = 0x2ddf338}
(gdb) p tb->private_data
$4 = (void *) 0x2dd2890

获取分组列属性编号


(gdb) n
381        AttrNumber *keyColIdx = hashtable->keyColIdx;
(gdb) 
382        uint32        hashkey = hashtable->hash_iv;
(gdb) p *keyColIdx
$5 = 1

如输入tuple为NULL,设置slot和哈希函数


(gdb) n
387        if (tuple == NULL)
(gdb) p hashkey
$6 = 0
(gdb) n
390            slot = hashtable->inputslot;
(gdb) 
391            hashfunctions = hashtable->in_hash_funcs;

开始遍历分组列
获取hashkey


(gdb) n
406        for (i = 0; i < numCols; i++)
(gdb) p numCols
$8 = 1
(gdb) n
408            AttrNumber    att = keyColIdx[i];
(gdb) 
413            hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0);
(gdb) p att
$9 = 1
(gdb) p hashkey
$10 = 0

获取属性值


(gdb) n
415            attr = slot_getattr(slot, att, &isNull);
(gdb) p hashkey
$11 = 0
(gdb) n
417            if (!isNull)            /* treat nulls as having hash key 0 */
(gdb) p attr
$12 = 140535426168416
(gdb) x\16c attr
Invalid character '\' in expression.
(gdb) x/16c attr
0x7fd0f427b660:    11 '\v'    71 'G'    90 'Z'    48 '0'    49 '1'    0 '\000'    0 '\000'    0 '\000'
0x7fd0f427b668:    1 '\001'    0 '\000'    0 '\000'    0 '\000'    1 '\001'    0 '\000'    0 '\000'    0 '\000'

计算哈希值


(gdb) n
421                hkey = DatumGetUInt32(FunctionCall1(&hashfunctions[i],
(gdb) p hashfunctions[i]
$13 = {fn_addr = 0x4c8a31 <hashtext>, fn_oid = 400, fn_nargs = 1, fn_strict = true, fn_retset = false, fn_stats = 2 '\002', 
  fn_extra = 0x0, fn_mcxt = 0x2db5310, fn_expr = 0x0}
(gdb) p i
$14 = 0
(gdb) n
423                hashkey ^= hkey;
(gdb) p hkey
$15 = 3431319292
(gdb) n
406        for (i = 0; i < numCols; i++)
(gdb) p hashkey
$16 = 3431319292

返回结果


(gdb) n
433        return murmurhash32(hashkey);
(gdb) p murmurhash32(hashkey)
$17 = 443809650
(gdb) n
434    }
(gdb) 
tuplehash_insert (tb=0x2dd2720, key=0x0, found=0x7fff585be487) at ../../../src/include/lib/simplehash.h:497
497        insertdist = 0;
(gdb)

TupleHashTableMatch
进入TupleHashTableMatch


(gdb) c
Continuing.
Breakpoint 2, TupleHashTableMatch (tb=0x2dd2720, tuple1=0x2dcc488, tuple2=0x0) at execGrouping.c:446
446        TupleHashTable hashtable = (TupleHashTable) tb->private_data;
(gdb)

输入参数


(gdb) p *tb
$18 = {size = 256, members = 1, sizemask = 255, grow_threshold = 230, data = 0x2ddca00, ctx = 0x2db5310, 
  private_data = 0x2dd2890}
(gdb) p *tuple1
$19 = {t_len = 21, mt_padding = "\000\000\000\000\000", t_infomask2 = 1, t_infomask = 2, t_hoff = 24 '\030', 
  t_bits = 0x2dcc497 ""}

对比是否匹配


(gdb) n
447        ExprContext *econtext = hashtable->exprcontext;
(gdb) 
455        Assert(tuple1 != NULL);
(gdb) 
456        slot1 = hashtable->tableslot;
(gdb) 
457        ExecStoreMinimalTuple(tuple1, slot1, false);
(gdb) 
458        Assert(tuple2 == NULL);
(gdb) 
459        slot2 = hashtable->inputslot;
(gdb) 
462        econtext->ecxt_innertuple = slot2;
(gdb) 
463        econtext->ecxt_outertuple = slot1;
(gdb) 
464        return !ExecQualAndReset(hashtable->cur_eq_func, econtext);
(gdb) p hashtable->cur_eq_func
$20 = (ExprState *) 0x2ddea18
(gdb) p *hashtable->cur_eq_func
$21 = {tag = {type = T_ExprState}, flags = 7 '\a', resnull = false, resvalue = 0, resultslot = 0x0, steps = 0x2ddeab0, 
  evalfunc = 0x6cd882 <ExecInterpExprStillValid>, expr = 0x0, evalfunc_private = 0x6cb43e <ExecInterpExpr>, steps_len = 7, 
  steps_alloc = 16, parent = 0x0, ext_params = 0x0, innermost_caseval = 0x0, innermost_casenull = 0x0, 
  innermost_domainval = 0x0, innermost_domainnull = 0x0}

返回值


$22 = true
(gdb) n
465    }
(gdb) 
tuplehash_insert (tb=0x2dd2720, key=0x0, found=0x7fff585be487) at ../../../src/include/lib/simplehash.h:556
556                Assert(entry->status == SH_STATUS_IN_USE);
(gdb)

DONE!

四、参考资料

N/A

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/6906/viewspace-2643703/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
长期从事政务、金融等行业产品研发和架构设计工作,ITPUB数据库版块资深版主,对Oracle、PostgreSQL有深入研究。现就职于广州云图数据技术有限公司,系统架构师。

注册时间:2007-12-28

  • 博文量
    1268
  • 访问量
    3745784