基于超图和浓密树的大数据实时查询优化研究与实现

摘要

Impala是Cloudera公司推出的大数据实时查询系统，其利用分布式技术，使用Hadoop作为存储，通过Hive的元数据表获取统计信息，实现大数据的高效查询。Impala的最新版本提供了一些查询优化技术，但目前只支持左深树形式的查询计划，同时由于目前基于McCHyp(MinCutConservative Hypergraph)算法的查询优化存在搜索空间大、优化时间较长的问题，本文提出了基于浓密树和改进的McCHyp算法的Impala查询优化方法。首先分析Impala系统生成查询计划的方法，修改构建流程使其支持浓密树形式的查询计划;接着分析McCHyp算法并使用剪枝策略对其进行改进，减少优化算法执行的时间，同时对剪枝策略的完整性和正确性进行了说明;然后通过分析多种经典的代价模型，提出一种综合考虑了磁盘I/O、网络传输和右表大小的代价模型，并将改进的McCHyp算法集成到Impala2.0系统中，根据用户的SQL语句生成最优查询计划。最后从优化算法、代价模型、查询性能和可扩展性四个方面在TPC-DS数据集上进行了对比实验，实验结果表明本文提出的方法有效提高了查询的效率，同时通过增加集群节点可以进一步减少查询响应时间。

目录

声明

摘要

图目录

表目录

第1章 绪论

1．1 研究背景及意义

1．2．1 搜索空间

1．2．2 搜索策略

1．2．3 代价模型

1．2．4 目前研究存在的问题

1．3 研究目标及内容

1．4 本文结构组织

1．5 本章小结

第2章 Impala大数据实时查询系统

2．1 Impala介绍

2．1．1 Impala 1．0系统

2．1．2 Impala 2．0系统

2．2 Impala 1．0系统查询过程

2．2．1 语法解析

2．2．2 查询计划生成

2．2．3 执行计划生成

2．2．4 查询和汇总

2．3 Impala 2．0系统对查询过程的改进

2．4 本章小结

第3章 代价估计

3．1 概述

3．2 统计信息收集

3．3 代价模型

3．4 代价估计方法

3．4．1 基于表的代价估计方法

3．4．2 基于列的代价估计方法

3．5 本章小结

第4章 基于超图和浓密树的大数据实时查询优化

4．1 概述

4．2 基本定义

4．3 查询超图建模

4．4 改进的McCHyp算法

4．4．1 集成剪枝策略的改进的McCHyp算法

4．4．2 改进的MeCItyp算法优化过程举例

4．5 剪枝策略的完整性和正确性

4．6 本章小结

第5章 系统实现

5．1 系统总体框架

5．2 查询计划形式的修改方法

5．2．1 JoinTree结构

5．2．2 JoinNode结构

5．2．3 HashJoinRef结构

5．2．4 构造查询计划的方法

5．3 改进的McCHyp算法在Impala中的集成

5．4 本章小结

第6章 实验评估

6．1 实验环境

6．2 实验设置

6．3 实验数据

6．4 实验结果与分析

6．4．1 优化算法对比

6．4．2 代价模型对比

6．4．3 查询性能对比

6．4．4 可扩展性对比

6．5 本章小结

第7章 总结与展望

7．1 总结

7．2 展望

参考文献

攻读硕士学位期间主要的研究成果

致谢