HashJoin功能设计文档
修订历史
版本 修订日期 修订描述 作者 备注
0.3 20170929 HashJoin功能设计文档 茅潇潇 无
1需求分析
Cedar是可扩展的关系数据库,实现了巨大数据量上的跨行跨表事务。在线业务中存在大量
的多表连接查询,在处理多表连接时,Cedar支持MergeJoin、BloomFilterJoin、SemiJoin
运算,特点是MergeServer(MS)分发请求给相应的ChunkServer(CS),CS把过滤后
的数据返回给MS,MS排序后做Merge操作。但是,如果对两张或两张以上的大表进行连
接,MS需要对大量的数据进行排序和比较,并且由于上述算子的连接操作都基于排序归并
导致需要缓存每张表的数据和中间结果表的数据,对CPU计算资源和内存资源消耗较大。
为解决上述问题,Cedar0.3版本增加了HashJoin的支持。HashJoin首先对前表构建Hash
Table,然后流水线处理后表每行数据做连接,一方面对于选择率较高的查询减少了大量的
数据对比次数,明显降低了连接计算的时间,另一方面不再需要对后表进行内存中的缓存和
排序,减少了时间和空间资源的消耗。生产环境中检验证明HashJoin的应用显著提高了多
表连接查询的性能。
2原理介绍
HashJoin使用关系S利用公共属性B上在内存中建立哈希表,然后扫描R表并探测哈希表,
找出相匹配的行。假设,节点1上的关系R和节点2上的关系S,在属性R.A=S.B上做连接操
作,它的工作流程如下:首先,节点2对关系S的每个元组在属性B上的值使用特定的哈希函
数进行计算,并在内存里产生一张哈希表;然后,节点1把关系R中的记录传送给节点2,在
节点2上对关系R的每个元组在属性A上的值使用相同的哈希函数进行计算,将计算的结果在
哈希表中进行探测;如果探测成功,则一条新的纪录将被创建。
3功能简述
评论0