【作者】 李静；

【导师】 孙莉；

【作者基本信息】 东华大学 ， 计算机软件与理论， 2011， 硕士

【摘要】 数据仓库查询一直是数据库领域的研究重点。近年的研究发现列存储体系仅从磁盘或内存中读取与查询相关的列,相对于行存储来说,更适合OLAP、数据仓库等查询密集型应用。作为一个较少更新的读优先系统,基于列存储的数据仓库系统能提高查询性能的思想已经占据了主导地位。论文研究了数据仓库技术、列存储技术、以及现有的查询优化技术。设计实现了列存储数据仓库查询模块,包括词法语法分析器、预处理器、查询优化器以及计划产生器。尤其是在查询优化方面,结合基于规则的优化方法(RBO)和基于代价的优化方法(CBO)设计了查询优化器,提出了列的连接策略优化方法。首先,论文分析了数据仓库查询特点以及现有的列存储查询优化技术,详细讨论了列存储系统PAX、InfoBright、C-Store以及MonetDB的存储方式和查询方式,并总结了列存储和行存储的查询特点差异。然后,论文对列存储的查询模块进行了深入探究,设计实现了查询编译器的各个功能模块。首先利用开源工具Flex和Bison,结合本系统语法树结构实现了词法语法分析器；根据SQL语句的标准和本系统查询树结构设计实现了预处理器,包括它的三大功能模块：语义分析、对象特征绑定以及部分逻辑计划的生成；在剖析现有的列存储连接策略的基础上,设计实现了一种新的列存储查询优化方法。该方法利用基于规则的优化方法为列存储数据查询制定优化规则,过滤掉不可能产生最优计划的候选计划。然后设计实现了基于代价的优化方法：根据动态Huffman树原理和左深连接树原理对查询执行顺序进行改进,进一步减少候选计划的规模；根据列存储数据的特点将候选计划中每个连接结点的执行策略归纳为串行连接和并行连接两类,并在此基础上提出代价估计模型,集中针对这两种连接策略进行代价估计和策略选择。实验证明该方法以较小的时空复杂度获得了优化的查询计划。最后,论文介绍了逻辑计划产生器和物理计划产生器的原则和方法,并对列存储数据仓库的查询优化进行了总结和展望。更多还原

【Abstract】 Data warehouse query is always the hot point in the area of database research. Recent studies show that column-store, a storage system only reads query-related attributes into memory from disk, is more suitable for OLAP, data warehouse and other query-intensive applications. As a read-optimized system with less update, the idea of column-oriented data warehouse can improve the query performance has already held a dominant position.The paper researched the techniques of data warehouse, column-stores and current query optimization. It designed and realized the query module of column-oriented data warehouse, including the parser, the preprocessor, the query optimizer and the plan generator. In the aspect of query optimizer, it is designed by merging the rule-based optimization (RBO) method and the cost-based optimization (CBO) method. And then it proposed the join strategy optimization in column-oriented queries.Firstly, paper analyzed the query features of data warehouse and current column-oriented query techniques. It discussed the storage mode and query method of several column-oriented systems in detail such as PAX, InfoBright, C-Store and MonetDB. After that, it summarized the query differences between column-stores and row-stores.Secondly, paper did some deep research on query module of column-stores. It designed and realized function modules of query compiler. It realized the parser by combing the parser tree structure with two open source tools, Flex and Bison. It designed and realized the preprocessor according to the SQL standard and the query tree structure, including three function modules which are semantic analysis, object characteristic binding and half-plan generation. On the basis of modern join strategies, this paper proposed a new column-oriented query optimization method. The method used RBO method to set rules for column-oriented queries to filter those candidate plans with large costs. Then it designed the CBO algorithm. It changed the execution order by Huffman tree and left-deep tree principle. It summarized the execution strategies of each join node in the column-oriented query plan into two:pipeline strategy and parallel strategy. Based on that, a cost model is then proposed focusing on estimating the cost of the pipeline and parallel strategies. The experimental results showed that with small time and space complexity, the efficiency of the query execution in column-oriented systems is improved.Finally, the paper introduced the principle of plan generator, including logical plan and physical plan. It summarized the query optimization of column-oriented data warehouse and previewed its research future.更多还原