HashMap优化及其在列存储数据库查询中的应用_母红芬1
需积分: 0 15 浏览量
2022-08-04
15:09:12
上传
评论
收藏 3.26MB PDF 举报
HashMap 优化及其在列存储数据库查询中的应用
*
母红芬
1
，李 征
1+
，霍卫平
2
，金正皓
2
1. 北京化工大学 计算机系，北京 100029
2. 北京东方国信科技股份有限公司，北京 100102
HashMap Optimization and Its Application in Column-Oriented Database Query
MU Hongfen
1
, LI Zheng
1+
, HUO Weiping
2
, JIN Zhenghao
2
1. Department of Computer Science, Beijing University of Chemical Technology, Beijing 100029, China
2. Business-Intelligence of Oriental Nations Corporation, Beijing 100102, China
MU Hongfen, LI Zheng, HUO Weiping, et al. HashMap optimization and its application in column-oriented
database query. Journal of Frontiers of Computer Science and Technology, 2016, 10(9)：1250-1261.
Abstract: HashMap has been widely used to retrieve big data because of its constant level in average performance of
dictionary operations. Block_HashMap (BHMap) is based on C++ HashMap, in which three optimizations are intro-
duced: Hash function selection, conflict resolution and keyword matching. Conflict resolution is the core of optimiza-
tion, where Block_list, a storage structure based on the chain address method, is proposed to use cache efficiently and
save matching time by store hashcode. In the situation of limited bucket number and low data repetition rate, experi-
ments show that although it consumes a small amount of memory, BHMap has a 3.5 times of C++ unordered_map and
10 times of Map in terms of query speed. In column- oriented database, group by and join are the most commonly
used, in which bucket keywords, resolving conflict and matching keywords are all Hash based. Finally the application
of BHMap in the query of column-oriented database is provided.
Key words: HashMap; group by; join; cache-conscious; cache-oblivious; column-oriented database; BHMap
* The National Natural Science Foundation of China under Grant Nos. 61170082, 61472025 (国家自然科学基金); the New Century
Excellent Talents Foundation from MOE of China under Grant No. NCET-12-0757 (教育部新世纪优秀人才支持计划); the Scientific
Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry of China under Grant No. LXJJ201303
(教育部留学回国人员科研启动基金).
Received 2015-07, Accepted 2015-10.
CNKI 网络优先出版: 2015-10-29, http://www.cnki.net/kcms/detail/11.5602.TP.20151029.1704.002.html
ISSN 1673-9418 CODEN JKYTA8
Journal of Frontiers of Computer Science and Technology
1673-9418/2016/10(09)-1250-12
doi: 10.3778/j.issn.1673-9418.1507065
E-mail: [email protected]
http://www.ceaj.org
Tel: +86-10-89056056
剩余11页未读，继续阅读
评论0