MapReduce架构中基于列存储的多路Theta连接查询优化

摘要

随着信息规模的日益增长，MapReduce架构成为大规模数据分析的主要平台之一。在 MapReduce中实现单个数据集上的各种操作，可以获得较高的效率。多路Theta连接在描述复杂的数据相关性方面是非常有用的，包含多路Theta连接操作的查询在大规模数据分析的过程中发挥越来越重要的作用。然而，在 MapReduce中实现多路Theta连接的效率并不高。为了避免数据集中与查询无关的属性参与查询，提高查询效率，在MapReduce架构中常常采用列式存储结构，但是这也为多路Theta连接查询高效的实现带来了许多问题和挑战。本文着眼于 MapReduce架构中基于列式存储的多路Theta连接查询，针对现存的问题，主要包括压缩、列重构以及连接策略方面存在的问题进行了分析研究。
　　在列式存储中，压缩是提高查询效率的有效手段之一。但是在现存的压缩机制中，重量级压缩很难支持压缩数据上的直接查找，其先解压再查找的特性使得数据列中不满足查找条件的值也被解压出来，增加了解压时间；轻量级压缩支持压缩数据上的直接查找，节约了解压时间，但是其压缩率（压缩后数据的空间大小和压缩前数据空间大小的比值）偏大，增加了数据读入时的I/O时间开销。针对该问题提出了一种新的基于列式存储的压缩方法。该压缩方法将数据列划分成若干子列，并且通过设计压缩率计算方法为子列选择适合的轻量级压缩机制。该方法不仅比轻量级压缩机制的压缩率要低，并且保持了轻量级压缩数据上直接查找的特性，避免对不必要的列值进行解压。因此，该方法可以通过减少数据读取时的I/O时间和数据解压的时间来提高查询效率。对应的还设计实现了压缩数据上的直接查找方法。通过实验测试了整型、实型和字符串型数据列上的压缩率、压缩时间、解压时间、等值查找时间和范围查找时间，通过和不同的压缩机制进行比较，说明该方法在提高查找效率上的优势。
　　列重构是列存储所带来的额外操作，也是影响查询效率的重要因素之一。现有的列重构策略中，早期列重构会导致不必要的记录也参与复杂的连接操作，而晚期列重构则需要对相关数据进行低效的随机读取操作。针对不同的重构策略带来不同的额外重构时间的问题，设计了一种基于选择的重构策略，通过选择从早期列重构策略和晚期列重构策略中选择适合的策略来减少列重构对查询效率的影响。该选择策略的思想是：首先对早期列重构和晚期列重构分别建立代价模型，用于计算一个MapReduce任务中，早期列重构和晚期列重构所带来的不同的时间开销；然后基于代价模型，为各种不同类型的查询创建了比较模型，通过比较早期列重构和晚期列重构这两者之间的时间开销大小来确定适合列重构的时机。相关实验测试了早期列重构和晚期列重构的开销，并将该策略的选择结果与其进行了比较，验证了该策略可以从理论上预先确定列重构的时机。
　　在多路Theta连接的连接策略，即在MapReduce架构中多路Theta连接操作的实现方法方面，使用过多的MapReduce任务，会因为多次输入输出和任务启动而导致大量的I/O时间开销和启动时间开销；而使用过少的MapReduce任务会造成任务过程中大量记录的重复读写和传输。因此，过多或过少的任务数量都会造成查询效率的降低。针对这个问题提出了一种新的基于转换的连接策略来确定多路Theta连接过程中MapReduce任务的数量以及每个MapReduce任务的内容。该连接策略首先将多路Theta连接转换为连接条件的数量和代价最少的连接，即将冗余的连接条件转换为连接结果上的过滤条件，避免因为不必要的连接操作而影响整个查询的效率；然后，将转换后的连接分解成一组2路Theta连接和等值连接，其中针对2路Theta连接组设计了相应的算法，使其能够在一个 MapReduce任务中高效地完成；最后，2路Theta连接组的结果数据集进行等值连接，并且在等值连接的结果上用冗余的连接条件进一步进行过滤，得到最终的多路Theta连接的结果。在该连接策略中，通过对2路Theta连接组和等值连接分别进行优化，从而最终达到优化多路Theta连接的目的。实验将该连接策略和其它策略的时间开销进行对比，验证了其在星型、链型和混合型这三种类型的多路Theta连接上效率的优势。
　　基于列式存储的压缩机制，列重构策略和多路Theta连接策略上的优化，设计实现了一个基于MapReduce的查询系统来对包含多路Theta连接的查询进行优化。该系统是建立在列式存储机制CFile之上，并且通过集成基于列式存储的压缩机制，基于选择的列重构策略和基于转换的连接策略来达到提高多路Theta连接查询效率的目的。通过和典型的查询系统进行对比，表明了该系统提高了多路Theta连接查询的效率。

目录

声明

1 绪论

1.1 课题背景和研究意义

1.2 研究现状

1.3 本文内容和组织结构

2 支持直接查找的列存储压缩机制

2.1 引言

2.2 压缩率的计算

2.3 数据列的划分

2.4 VParC压缩机制

2.5 VParC压缩数据上的直接查找

2.6 实验结果及分析

2.7 本章小结

3 MapReduce中基于列重构策略的查询优化

3.1 引言

3.2 列重构代价模型

3.3 CRSS选择策略

3.4 实验结果及分析

3.5 本章小节

4 MapReduce中基于多路Theta连接策略的查询优化

4.1 引言

4.2 多路Theta连接的转换

4.3 ST连接的处理

4.4 trTheta连接策略

4.5 实验结果及分析

4.6 本章小结

5 MapReduce中基于列存储的多路Theta连接查询系统

5.1 前言

5.2 存储引擎

5.3 查询引擎

5.4 实验

5.5 本章小结

6 总结和展望

6.1 全文总结

6.2 展望

致谢

参考文献

附录1 攻读学位期间发表学术论文目录

附录2 博士生期间参与的课题研究情况