列数据库的SQL查询语句编译与优化

doi:10.3969/j.issn.1000-3428.2013.06.012

计算机工程 ›› 2013, Vol. 39 ›› Issue (6): 60-65.doi: 10.3969/j.issn.1000-3428.2013.06.012

列数据库的SQL查询语句编译与优化

甄真，陈虎，张林亚

(华南理工大学软件学院，广州 510006)

收稿日期:2012-06-18 出版日期:2013-06-15 发布日期:2013-06-14
作者简介:甄真(1987－)，男，硕士研究生，主研方向：高性能计算，并行算法；陈虎，副教授；张林亚，硕士研究生
基金项目:
广东省科技计划基金资助项目(2011A010801008, 2011A090200122, 2011A090200027)

Compilation and Optimization of SQL Query Statements on Column-oriented Database

ZHEN Zhen, CHEN Hu, ZHANG Lin-ya

(School of Software Engineering, South China University of Technology, Guangzhou 510006, China)

Received:2012-06-18 Online:2013-06-15 Published:2013-06-14

摘要/Abstract

摘要： 基于多核CPU和GPU异构平台的列数据库可用于海量数据和复杂查询，但其优化主要集中在底层，并且后端的执行序列只能通过手工硬编码生成，不能适应多样的SQL查询语句。针对该问题，设计并实现一个将SQL查询语句自动转化成执行序列的编译器，研究多个复杂表达式中的公共子表达式消除和原语依赖图合并方法。与手工编码的比较结果表明，该编译器能够提高算术表达式的计算速度，缩短执行SQL查询语句的时间。

关键词: 列数据库, 原语, 编译器, 依赖图, 公共子表达式消除, 查询优化

Abstract: A column-oriented database based on a heterogeneous platform of multi-core CPU and GPU can be used for mass data and complex queries. However, the optimization in this database is mainly on physical level and execution sequence for its back-end can only be generated manually, resulting in hard adaptation to varieties of SQL query statements. To solve this problem, this paper designs and implements a compiler that translates SQL query statements into execution sequence. It studies Common Subexpression Elimination(CSE) method in multiple complex expressions and merging method of multiple primitive dependency graphs. Comparing the results with situations where no compiler is used in GSQL, it can be found that this compiler can improve speed of computing multiple complex expressions efficiently and reduce time of processing multiple SQL query statements.

Key words: column-oriented database, primitive, compiler, dependency graph, Common Subexpression Elimination(CSE), query optimization

中图分类号:

TP314

甄真, 陈虎, 张林亚. 列数据库的SQL查询语句编译与优化[J]. 计算机工程, 2013, 39(6): 60-65.

JUAN Zhen, CHEN Hu, ZHANG Lin-E. Compilation and Optimization of SQL Query Statements on Column-oriented Database[J]. Computer Engineering, 2013, 39(6): 60-65.

参考文献

[1] Abadi D J, Madden S R, Hachem N. Column Stores vs. Row Stores: How Different Are They Really?[C]//Proc. of 2008 ACM SIGMOD International Conference on Management of Data. New York, USA: ACM Press, 2008.
[2] Transaction Processing Performance Council. TPC Bench- markTM H Standard Specification Revision 2.10.0[EB/OL]. [2012-04-18]. http://www.tpc.org.
[3] Boncz P A, Kersten M L. MIL Primitives for Querying a Fragmented World[J]. The VLDB Journal, 1999, 8(2): 101-119.
[4] Stonebraker M, Abadi D J, Batkin A, et al. C-Store: A Column- oriented DBMS[C]//Proc. of the 31st International Conference on Very Large Data Bases. New York, USA: ACM Press, 2005.
[5] Chen S, Ailamaki A, Gibbons P B, et al. Improving Hash Join Performance Through Prefetching[J]. ACM Transactions on Database Systems, 2007, 32(3).
[6] Satish N, Kim C, Chhugani J, et al. Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort[C]//Proc. of ACM SIGMOD International Conference on Management of Data. New York, USA: ACM Press, 2010.
[7] 陈虎, 欧彦麟, 陈海波. 面向多核处理器平台的Hash Join算法设计与实现[J]. 计算机研究与发展, 2010, 47(z1): 171-175.
[8] He Bingsheng, Lu Mian, Yang Ke, et al. Relational Query Co- processing on Graphics Processors[J]. ACM Transactions on Database Systems, 2009, 34(4): 1-39.
[9] 李静, 孙莉, 王梅. 列存储数据查询中的连接策略选择方法[J]. 计算机科学与探索, 2010, 4(9): 850-858.
[10] Aho A V, Lam M S, Sethi R, et al. 编译原理[M]. 2版. 赵建华, 郑滔, 戴新宇, 译. 北京: 机械工业出版社, 2009.
[11] Muchnick S S. 高级编译器设计与实现(英文版)[M]. 北京: 机械工业出版社, 2003.
[12] Breuer M A. Generation of Optimal Code for Expressions via Factorization[J]. Communications of the ACM, 1969, 12(6): 333-340.
[13] Hosangadi A, Fallah F, Kastner R. Optimizing Polynomial Expressions by Algebraic Factorization and Common Sub- expression Elimination[J]. IEEE Transactions on Computer- aided Design of Integrated Circuits and Systems, 2006, 25(10): 2012-2021.
[14] 吴文远. 列数据库的数据存储与查询向量化方法研究与实现[D]. 广州: 华南理工大学, 2011.
[15] Louden K C. 编译原理与实践(英文版)[M]. 北京: 机械工业出版社, 2002.
[16] Kersten M, Manegold S. Cracking the Database Store[C]// Proc. of the 2nd Biennial Conference on Innovative Data Systems Research. New York, USA: ACM Press, 2005.
[17] Ivanova M G, Kersten M L, Nes N J, et al. An Architecture for Recycling Intermediates in a Column-store[J]. ACM Transac- tions on Database Systems, 2010, 35(4): 1-41.
编辑金胡考

列数据库的SQL查询语句编译与优化

Compilation and Optimization of SQL Query Statements on Column-oriented Database

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10

[1]	蒋凡,范秀萍. TTCN-3语言中基于过程通信的编译器实现[J]. 计算机工程, 2016, 42(8): 9-13.
[2]	赵高义,郑启龙. BWDSP104X字节寻址模式扩展及64位数据运算模拟实现[J]. 计算机工程, 2016, 42(8): 14-18,23.
[3]	郭帆,周轩. 基于依赖的J2EE程序污点分析方法 [J]. 计算机工程, 2016, 42(6): 131-138.
[4]	张泓,曹珍富,董晓蕾. 基于承签原语与多重签名的改进虚拟交易系统方案[J]. 计算机工程, 2016, 42(2): 137-141,145.
[5]	徐东,狄效国,孟宇龙,冯晓宁. 基于依赖图等价代换的SSDG构建算法[J]. 计算机工程, 2015, 41(12): 91-95,100.
[6]	姜梦霞,江国华. 一种安全性关键软件的评估模型[J]. 计算机工程, 2015, 41(10): 130-138,143.
[7]	李重文,邓腾彬,马世龙. 基于分段极值的时间序列数据查询显示方法[J]. 计算机工程, 2014, 40(9): 27-31.
[8]	葛星,沈耀,徐常亮. 基于云计算的多重查询优化系统[J]. 计算机工程, 2014, 40(9): 46-50,58.
[9]	刘家兵，徐云. X86平台上Open64软件流水的设计与实现[J]. 计算机工程, 2013, 39(9): 15-19.
[10]	黄品丰, 赵荣彩, 韩林, 刘晓娴. OpenMP数据分布子句自动生成算法[J]. 计算机工程, 2013, 39(3): 295-299.
[11]	姚新磊, 庞建民, 岳峰, 余勇. 基于API依赖关系的代码相似度分析[J]. 计算机工程, 2013, 39(1): 80-84.
[12]	刘石柱, 尹首一, 殷崇勇, 刘雷波, 魏少军. 基于可重构处理器的并行优化算法[J]. 计算机工程, 2012, 38(21): 286-289.
[13]	张文波, 张斌, 谭小波, 付立东. 一个简化的无线传感器网络管理编码规则[J]. 计算机工程, 2012, 38(08): 64-66.
[14]	王少培, 吴健, 阮园. CoSy C语言编译器安全性研究[J]. 计算机工程, 2012, 38(06): 43-46.
[15]	魏雪菲, 吴健, 阮园. 基于错误模式和模型检验的静态代码分析方法[J]. 计算机工程, 2012, 38(06): 47-49.