Respected readers, authors and reviewers, you can add comments to this page on any questions about the contribution, review, editing and publication of this journal. We will give you an answer as soon as possible. Thank you for your support!
MAO Xiao-xiao, DUAN Hui-chao, GAO Ming. A join algorithm based on bloom filter in OceanBase[J]. Journal of East China Normal University (Natural Sciences), 2016, (5): 67-74. doi: 10.3969/j.issn.1000-5641.2016.05.008
Citation:
MAO Xiao-xiao, DUAN Hui-chao, GAO Ming. A join algorithm based on bloom filter in OceanBase[J]. Journal of East China Normal University (Natural Sciences), 2016, (5): 67-74. doi: 10.3969/j.issn.1000-5641.2016.05.008
MAO Xiao-xiao, DUAN Hui-chao, GAO Ming. A join algorithm based on bloom filter in OceanBase[J]. Journal of East China Normal University (Natural Sciences), 2016, (5): 67-74. doi: 10.3969/j.issn.1000-5641.2016.05.008
Citation:
MAO Xiao-xiao, DUAN Hui-chao, GAO Ming. A join algorithm based on bloom filter in OceanBase[J]. Journal of East China Normal University (Natural Sciences), 2016, (5): 67-74. doi: 10.3969/j.issn.1000-5641.2016.05.008
In the era of big data, the movement of de-IOE campaign and the development of activities such as Double 11 have put forward higher request of the performance of distributed database. OceanBase is an open sourced distributed database implemented by Alibaba. It supports for cross-table relational query of massive data but the performance for complex queries remains to be improved. The network transmission overheads caused by join operator seriouslyinfluenced the performance of distributed database. This paper proposes a join algorithm based on bloom filter. It filters the data of the right table
by constructing a bloom filter on the join column of the left table. The key point of this algorithm is that it reduces the overhead of unnecessary data transmission and the consumption of memory resources by data processing. We implement this algorithm in OceanBase and the experiment results show that the algorithm can greatly improve the efficiency of join operator.
[ 1 ] 杨传辉.大规模分布式存储系统: 原理解析与架构实战[M]. 北京:机械工业出版社, 2013.
[ 2 ] BLASGEN M W, ESWARAN K P. Storage and access in relational data bases[J]. IBM Systems Journal, 1977, 16(4): 363-377.
[ 3 ] MERRETT T H. Why sort-merge gives the best implementation of the natural join[J]. ACM SIGMOD Record, 1983, 13(2): 39-51.
[ 4 ] BABB E. Implementing a relational database by means of specialized hardware[J]. ACM Transactions on Database Systems, 1979, 4(1): 1-29.
[ 5 ] SCHNEIDER D A, DEWITT D J. A performance evaluation of four parallel join algorithms in a shared-nothingmultiprocessor environment[C]//Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data. ACM,1989: 110-121.
[ 6 ] BERNSTEIN P A, GOODMAN N, WONG E, et al. Query processing in a system for distributed databases (SDD-1)[J]. ACMTransactions on Database Systems, 1981, 6(4): 602-625.
[ 7 ] BLOOM B H. Space/time trade-offs in hash coding with allowable errors[J]. Communications of the ACM, 1970, 13(7):422-426.
[ 8 ] CHEN M S, HSIAO H I, YU P S. On applying hash filters to improving the execution of multi-join queries[J]. The VLDB journal, 1997, 6(2): 121-131.
[ 9 ] MACKERT L F, Lohman G M. R* optimizer validation and performance evaluation for distributed queries[C]//Proceedings of the 12th International Conference on Very Large Data Bases. San Francisco: Morgan Kaufmann Publishers Inc, 1986: 149-159.
[10] BACON D F, STROM R E, TARAFDAR A. Guava: A dialect of Java without data races[C]//Proceedings of the 15th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications. 2000: 382-400.
[11] GHEMAWAT S, DEAN J. Level DB[DB/OL]. [2011-5-12]. http://code.google.com/p/leveldb/.
DownLoad: