列存储数据仓库中的查询优化研究

摘要

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