基于支持列存储的数据压缩算法研究

摘要

由于日益庞大的业务处理，许多决策系统和OLAP系统的数据正在朝着TB数量级发展。面对各种存储了海量数据的巨型表，如何充分利用存储空间，节省系统维护成本，在查询海量数据时取得更好的性能，引起了数据库研究者们越来越多的关注。而将数据压缩技术引进数据库系统，成为了解决大数据量环境下数据库性能问题的有效手段之一。
　　 在传统的关系型数据库中，数据均是按行存储的(行存数据库)，即关系表中同一条记录的不同属性值被依次顺序存放在物理磁盘上。遗憾的是，由于记录中不同的属性值通常取值于不同的值域，彼此间的相关性很小，导致按行存储的数据存储方式并不利于数据压缩的实现。
　　 列存数据库消除了行存数据库在数据压缩领域的不利条件。在列存数据库中，连续存储的数据均来源于同一个值域，而对同一个值域内的数据进行压缩正是各种经典数据压缩算法实现的前提和关键。为此，本文对如何将各种经典的数据压缩算法融入列存数据库进行了研究。
　　 首先，本文阐述了列存环境下数据压缩的重要意义，并对数据压缩技术的发展历程和国外主流列存商业数据库的现状进行了分析；其次，综述了数据压缩的相关概念以及列存数据库在数据压缩领域的巨大优势，并详细讨论了各种经典的数据压缩算法，具体包括了赫夫曼编码、算术编码、LZ77算法、LZW算法、RLE算法和空值压缩算法等。
　　 随后，本文深入研究了列存压缩运算库的结构设计。列存压缩运算库由压缩数据物理存储机制、压缩模块和数据源模块三个部分构成。其中，物理存储机制描述了不同压缩数据在列存数据库中同时存储的合理方案，是列存环境下各种压缩算法实现的必要保证；压缩模块则封装了具体压缩算法的细节，并负责对外提供统一的解压接口；而数据源模块扮演着通信媒介的角色，为压缩模块与数据库存储层之间的消息和数据传递提供服务。此外，通过归纳各种压缩数据的属性，本文对传统的数据库执行器算子进行了相应的改进，从而实现了压缩数据在压缩态下的直接查询。
　　 最后，本文以国产数据库神舟OSCAR为平台，具体实现了上述各项关键技术。通过对相关的性能测试结果进行对比分析，验证了本文所述内容的正确性和有效性，在减少列存数据库存储规模的同时，进一步自动优化了数据库系统的性能。

目录

文摘

英文文摘

声明

1绪论

1.1课题来源

1.2课题研究意义

1.3国内外研究动态

1.4课题研究方法和论文组织

2列存数据库中数据压缩算法的研究

2.1数据压缩综述

2.2支持列存储的数据压缩算法

2.2.1列存环境下的数据压缩优势

2.2.2列存环境下基于统计的数据压缩算法

2.2.3列存环境下基于字典的数据压缩算法

2.2.4 RLE算法

2.2.5空值压缩算法

2.3各种数据压缩算法的比较与分析

2.4本章小结

3列存压缩运算库结构设计

3.1列存压缩运算库模型

3.2压缩数据的物理存储机制

3.2.1压缩元组的数据结构

3.2.2压缩值长度编码

3.2.3压缩值长度解码

3.3列存数据库执行器功能模块扩展

3.3.1压缩模块

3.3.2数据源模块

3.4列存数据压缩态下的查询优化

3.5本章小结

4神舟OSCAR列存压缩数据库管理系统

4.1 OSCAR列存压缩数据库管理系统体系结构

4.2 OSCAR列存压缩数据库存储模式设计

4.2.1基本概念

4.2.2总体结构设计

4.2.3块头属性功能描述

4.3 OSCAR列存压缩数据库执行器模块设计

4.3.1功能结构图

4.3.2信息流图

4.4实验和验证

4.4.1解压后的数据查询

4.4.2压缩态下数据查询

4.5本章小结

5总结和展望

5.1研究总结

5.2研究展望

致谢

参考文献