Heuristic mechanism for query optimization in column-store data warehouse

被引：0

作者：

Yan Q.-L. ^{[1
]}

Sun L. ^{[1
]}

Wang M. ^{[1
]}

Le J.-J. ^{[1
]}

Liu G.-H. ^{[1
,2
]}

机构：

[1] School of Computer Science and Technology, Donghua University

[2] State Key Laboratory for Novel Software Technology, Nanjing University

来源：

Jisuanji Xuebao/Chinese Journal of Computers | 2011年 / 34卷 / 10期

关键词：

Column-store; Left-deep join tree; Optimization strategy; Query optimization; Rewrite rule;

D O I：

10.3724/SP.J.1016.2011.02018

中图分类号：

学科分类号：

摘要：

It is well known that column-store architecture is more suitable for "read optimization" application in large scale dataset. However, due to the fact that data is organized in columns in column-store, the traditional rule-based query optimization methods are not fully applicable for such application. In this paper, we first compare the difference of the query optimization between the column-sotre and row-store, and then propose a heuristic mechanism for query optimization in column-store, including heuristic optimization strategy, relational algebra expression rewriting rules, left-deep join tree and relating algorithms. The experimental results show that the proposed heuristic optimization mechanism can effectively reduce the size of the candidate plan, and exclude a large number of plans which can not generate the optimal plan, so as to make the cost and implementation time of query processing greatly reduced.

引用

页码：2018 / 2026

页数：8

共 19 条

[1] Abadi Daniel J., Query execution in column-oriented database systems, (2008)
[2] Mike S., Abadi Daniel J., Et al., C-Store: A column-oriented DBMS, Proceedings of the 31st VLDB Conference, pp. 553-564, (2005)
[3] MacNicol R., French B., Sybase IQ multiplex-designed for analytics, Proceedings of the 30th VLDB Conference, pp. 1227-1230, (2004)
[4] Boncz P.A., Monet: A next-generation DBMS kernel for query-intensive applications, (2002)
[5] Abadi D.J., Integrating compression and execution in column oriented database systems, Proceedings of the SIGMOD, pp. 671-682, (2006)
[6] Gupta A., Davis K.C., Performance comparison of property map and bitmap indexing, Proceedings of the 5th ACM International Workshop, pp. 65-71, (2002)
[7] Neil P.O., Quass D., Improved query performance with variant indexes, Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 38-49, (1997)
[8] Abadi Daniel J., Madden Samuel R., Nabil H., Column-stores vs. row-stores: How different are they really?, Proceedings of the 2008 ACM SIGMOD International Conference, pp. 967-980, (2008)
[9] Stratos I., Kersten Martin L., Stefan M., Self-organizing tuple reconstruction in column stores, Proceedings of the 35th SIGMOD International Conference, pp. 297-308, (2009)
[10] Pirahesh H., Hellerstein J.M., Hasan W., Extensible/rule based query rewrite optimization in starbust, Proceedings of ACM SIGMOD, pp. 39-48, (1992)

← 1 2 →