An outer join algorithm based on Cuckoo filter
-
摘要: 近十几年，由于互联网的发展异常迅猛，数据规模不断增加，分布式数据库的分析效率亟待优化，其中连接操作更是分布式数据库的主要性能瓶颈.外连接在商业中运用非常广泛.分布式外连接算法涉及到大量的网络传输，严重影响系统性能，虽然有一些研究针对内连接进行了优化，但这些优化方法并不能直接应用于外连接.文章中基于Cuckoofilter（布谷鸟过滤器）的分布式外连接算法，通过构建Cuckoofilter对数据进行筛选和分配，减少数据传输量的同时，提高执行的并行度，使得查询性能得到提升.通过在Ginkgo上实现该算法，并加以充分实验，验证得出该算法提高了分布式外连接操作的效率.
-
关键词:
- Cuckoo filter /
- Ginkgo /
- 外连接
Abstract: In recent years, due to the development of the Internet, data size has been increased rapidly. At the era of big data, the analysis efficiency of distributed database system needs to be optimized urgently. Nevertheless, the join operation is the main performance bottleneck of a distributed database system. Join operations are mainly divided into inner join and outer join, and outer join is widely used in the business situations. Distributed join algorithm involves a large amount of network transmission, which affects the performance of the system severely. Although there are some studies in the literature of inner join optimized, these optimization methods cannot be directly applied to outer join. This paper proposes a distributed outer join algorithm based on Cuckoo filter. By building a Cuckoo filter with replication subdivision technology for data filtering and allocation, it reduces the amount of data transmission and improves the degree of parallelism accordingly. Finally, it improves the query performance. We implement this algorithm in Ginkgo. Based on the given extensive experimental verification, the algorithm largely improves the efficiency of the outer join.-
Key words:
- Cuckoo filter /
- Ginkgo /
- outer join
-
图 1 关系 $S(x, a)$ 和 $L(y, b)$ 在3个计算节点上的分布
Fig. 1 Two relations $S(x, a)$ and $L(y, b)$ on 3 parallel units
图 2 中文复制分片分布式连接算法的第一步和第二步:数据被复制到其他所有节点上, 并将 $S$ 和 $L$ 进行哈希内连接标题
Fig. 2 The first and second step of duplication distributed outer join, data placement after duplication $S$ to every process node and $S$ and $L $ are inner joined
图 3 复制分片分布式连接算法的第三步和第四步:重分片中间结果 $J$ , 并将 $S$ 与 $J$ 外连接
Fig. 3 The first and second step of duplication distributed outer join, repartition the inner join result $J$ (Fig. 2) and final result of outer join
图 4 基于布谷鸟过滤器的分布式外连接算法流程图
Fig. 4 The visual presentation of distributed outer join algorithm based on Cuckoo filter
图 7 基于布谷鸟过滤器复制分片外连接算法与哈希重分片外连接算法比较
Fig. 7 Compare between duplication outer join algorithm based on Cuckoo filter and Hash repartition outer join algorithm
图 8 基于布谷鸟过滤器复制分片外连接算法与哈希重分片外连接算法比较
Fig. 8 Compare between duplication outer join algorithm based on Cuckoo filter and Hash repartition outer join algorithm
图 9 基于布谷鸟过滤器复制分片外连接算法广播布谷鸟过滤器的代价
Fig. 9 The costs of broadcasting Cuckoo filter in duplication outer join algorithm based on Cuckoo filter
算法1 布谷鸟过滤器构建算法 Insert( $x$ )
1 if filter. Contain( $x$ ) then
2 return Done
3 $f=$ FingerPrint $(x)$ /*生成 $x$ 的指纹 $f$ */
4 $i_1=$ CityHash $(x)$ /*计算 $x$ 的第一个桶位置*/
5 $i_2=i_1\oplus$ CityHash $(f)$ /*计算 $x$ 的第二个桶位置*/
6 if bucket [ $i_1$ ]或bucket [ $i_2$ ]有空槽then
7 将 $x$ 加入到空槽之中
8 return Done
9 $i=$ 随机选取 $i_1$ 或 $i_2$
10 for $n=0$ ; $n＜$ MaxNumKicks; $n^{++}$ do
11 随机选取bucket[ $i$ ]一个槽, 取出期中的值 $e$
12 将 $x$ 存入槽里
13 $f=$ FingerPrint $(e)$
14 $i=i\oplus$ CityHash $(f)$
15 if bucket [ $i$ ]有空槽then
16 将 $e$ 加入到bucket [ $i$ ]
17 return Done
18 运行至此说明布谷鸟过滤器满了, 需要重新分配新的空间
19 return Failure
下载: 导出CSV
算法2 布谷鸟过滤器查找算法 Contain( $x$ )
1 $f=$ FingerPrint $(x)$ /*生成 $x$ 的指纹 $f$ */
2 $i_1=$ CityHash $(x)$ /*计算 $x$ 的第一个桶位置*/
3 $i_2=i_1\oplus$ CityHash $(f)$ /*计算 $x$ 的第二个桶位置*/
4 if bucket [ $i_1$ ]或bucket [ $i_2$ ]有空槽then
5 return True
6 return False
下载: 导出CSV
-
[1] STONEBRAKER M. The case for shared nothing[J]. Database Engineering, 1986, 9:4-9. [2] 王立. 分布式内存数据库系统的查询处理与优化[D]. 上海: 华东师范大学, 2015. http://cdmd.cnki.com.cn/Article/CDMD-10269-1015348214.htm [3] 邹先霞, 贾维嘉, 潘久辉.实化外连接视图的增量计算[J].系统工程与电子技术, 2011, 33(4):938-942. http://www.cnki.com.cn/Article/CJFDTOTAL-XTYD201104045.htm [4] 张磊, 方祝和, 周敏奇, 等.面向内存计算的连接算法[J].华东师范大学学报(自然科学版), 2014(5):180-191. http://xblk.ecnu.edu.cn/CN/abstract/abstract25018.shtml [5] BERNSTEIN P A, CHIU D-M W. Using semi-joins to solve relational queries[J] Journal of the Association for Computing Machinery, 1981, 28(1):25-40. doi: 10.1145/322234.322238 [6] 樊秋实, 周敏奇, 周傲英.基线与增量数据分离架构下的分布式连接算法[J].计算机学报, 2016, 39(10):2102-2113 doi: 10.11897/SP.J.1016.2016.02102 [7] 茅潇潇, 段惠超, 高明. OceanBase中基于布隆过滤器的连接算法[J].华东师范大学学报(自然科学版), 2016(5):67-74. http://xblk.ecnu.edu.cn/CN/abstract/abstract25336.shtml [8] BLASGEN M W, ESWARAN K P. Storage and access in relational data bases[J]. IBM Systems Journal, 1977, 16(4):363-377. doi: 10.1147/sj.164.0363 [9] 赵宇兰.分布式数据库查询优化研究[M].成都:电子科技大学出版社, 2016. [10] LI J T, XIA X L. Research on outer join optimization in parallel DBMS[C]//Proceedings of the 2011 International Conference on Computer Science and Information Technology (ICCSIT 2011). 2011:502-507. [11] XU Y, KOSTAMAA P. A new algorithm for small-large table outer joins in parallel DBMS[C]//Proceedings of the IEEE 29th International Conference on Data Engineering (ICDE) (2010). IEEE, 2010:1018-1024. [12] CHENG L, KOTOULAS S, WARD T E, et al. Robust and efficient large-large table outer joins on distributed infrastructures[C]//European Conference on Parallel Processing. Berlin:Springer International Publishing, 2014:258-269. [13] XU Y, KOSTAMAA P, ZHOU X, et al. Handling data skew in parallel joins in shared-nothing systems[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. ACM, 2008:1043-1052. [14] CHENG L, KOTOULAS S, WARD T E, et al. Efficiently handling skew in outer joins on distributed systems[C]//Proceedings of the 14th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. IEEE, 2014:295-304. [15] FAN B, ANDERSEN D G, KAMINSKY M, et al. Cuckoo Filter:Practically better than bloom[C]//Proceedings of the ACM International on Conference on Emerging Networking Experiments & Technologies. ACM, 2014:75-88. [16] PAGH R, RODLER F F. Cuckoo Hashing[J]. Journal of Algorithms, 2004, 51(2):122-144. doi: 10.1016/j.jalgor.2003.12.002 -
点击查看大图
计量
- 文章访问数: 216
- HTML全文浏览量: 104
- PDF下载量: 309
- 被引次数: 0