计算机科学 ›› 2015, Vol. 42 ›› Issue (11): 28-31.doi: 10.11896/j.issn.1002-137X.2015.11.004

• 2014年全国高性能计算机学术年会 • 上一篇    下一篇

内存列存储数据库中优化的混合自适应索引

薛忠斌,周烜,张延松,周新,王珊   

  1. 教育部数据工程与知识工程重点实验室中国人民大学 北京100872 中国人民大学信息学院 北京100872,教育部数据工程与知识工程重点实验室中国人民大学 北京100872 中国人民大学信息学院 北京100872,教育部数据工程与知识工程重点实验室中国人民大学 北京100872 中国人民大学信息学院 北京100872,教育部数据工程与知识工程重点实验室中国人民大学 北京100872 中国人民大学信息学院 北京100872,教育部数据工程与知识工程重点实验室中国人民大学 北京100872 中国人民大学信息学院 北京100872
  • 出版日期:2018-11-14 发布日期:2018-11-14

Optimized Adaptive Hybrid Indexing for In-memory Column Stores

XUE Zhong-bin, ZHOU Xuan, ZHANG Yan-song, ZHOU Xin and WANG Shan   

  • Online:2018-11-14 Published:2018-11-14

摘要: 分析型数据库在现代企业中得到广泛应用,在使用过程中对查询处理速度的要求逐渐提高。大数据环境下,分析型数据库面临一系列新的挑战:首先,数据复杂性与日俱增,使得数据库系统的初始配置任务更加繁重,例如索引创建等;其次,在分析过程中,由于查询负载模式无法预知,需要对某些属性反复构建索引,以满足查询的时间要求。显然,传统的索引构建维护技术不能完全满足新的应用环境。数据库分裂技术提出了一种不同的策略去解决这些问题。使用数据库分裂技术,DBA不需要对数据库进行细粒度的系统配置。在查询执行过程中,数据库能自动调整以适应查询负载;随着查询负载的变化,系统自动调整索引。近年来,一系列数据库分裂算法被提出,但已有的算法都各有优缺点。因此给出了一个cache conscious的数据库分裂代价模型,并基于该模型构建了一个新的自适应索引,其可以综合不同数据库分裂算法的优势。通过大量实验验证了这种新自适应索引技术的有效性。

关键词: 自适应合并,数据库分裂,自适应索引,混合算法

Abstract: Analytical database has been widely deployed in modern corporations which are posing increasing demand for the speed of data analysis.In the era of big data,analytical database is faced with a number of new challenges.Firstly,the complexity of data keeps increasing,therefore,more efforts have to be put into system configuration,such as index creation.Secondly,without prior knowledge about the patterns of workload,system administrators have to build and rebuild indexes repeatedly,in order to meet the time constraints.Apparently,traditional approaches to index construction and maintenance can not work well in the new environment.Database cracking provides an alternative to solve the problem.Using database cracking,a DBA does not need to fine-tune the system configuration.Instead,the database can automatically adjust itself to fit the workload during query execution.In recent years,a series of database cracking algorithms have been proposed,while none of them is optimal in all situations.The paper proposed a cache conscious cost model for database cracking.Based on the model,we created a new adaptive index,which can combine the advantages of several previous cracking approaches.Extensive experiments were conducted to demonstrate the effectiveness of our method.

Key words: Adaptive merging,Database cracking,Adaptive indexing,Hybrid algorithm

[1] Chaudhuri S,Weikum G.Rethinking database system architecture:Towards a self-tuning risc-style database system[C]∥Proceedings of the 26th In VLDB.2000:1-10
[2] Graefe G,Idreos S,Kuno H,et al.Benchmarking adaptive indexing[C]∥TPCTC.2010:169-184
[3] Graefe G,Kuno H.Adaptive indexing for relational keys[C]∥ICDE.2010:69-74
[4] Graefe G,Kuno H.Self-selecting,self-tuning,incrementally optimized indexex[C]∥EDBT.2010:371-381
[5] Idreos S,Kersten M L,Manegold S.Database cracking[C]∥CIDR.2007:68-78
[6] Idreos S,Kersten M L,Manegold S.Updating a cracked data-base[C]∥SIGMOD.2007:413-424
[7] Idreos S,Kersten M L,Manegold S.Self-organizing tuple reconstruction in column stores[C]∥SIGMOD.2009:297-308
[8] Idreos S,Manegold S,Kuno H,et al.Merging what’s cracked,cracking what’s merged:adaptive index in main-memory column-stores[J].PVLDB,2011,4(9):585-597
[9] Halim F,Idreos S,Karras P,et al.Stochastic database cracking:Towards robust adaptive indexing in main-memory Column-stores[J].PVLDB,2012,5(6):502-513
[10] Kersten M,Manegold S.cracking the database store[C]∥CIDR.2005:213-224
[11] Hoare C A R.Algorithm 64:Quicksort[J].Communications of the ACM,1961,4(4):319-320
[12] Schuhknecht F M,Jindal A,Dittrich J.The Uncracked Pieces in Database Cracking[C]∥VLDB.2013
[13] Pirk H,Petraki E,Idreos S,et al.Database Cracking:FancyScan,not Poor Man’s Sort![J/OL].http://oai.cwi.nl/oai/asset/22474/22474D.pdf
[14] Graefe G,Halim F,Idreos S,et al.Transactional support for adaptive indexing[J].The VLDB Journal,2014,23(2):303-328
[15] Alvarez V,Schuhknecht F M,Dittrich J,et al.Main Memory Adaptive Indexing for Multi-core Systems[J/OL].http://arxiv.org/abs/1404.2034

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[2] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[3] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[4] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[5] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[6] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[7] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[8] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[9] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .
[10] 王振朝,侯欢欢,连蕊. 抑制CMT中乱序程度的路径优化方案[J]. 计算机科学, 2018, 45(4): 122 -125 .