基于列存储数据库的数据压缩研究与实现

论文摘要

本文的主要工作是对列存储技术的研究以及数据压缩在其中的应用。具体内容有:分析和研究了列存储数据库的概念及其核心实现技术;研究主流轻量级压缩算法,提出了频繁段压缩算法,其在某些条件下可能比较优越;研究压缩态数据随机访问技术,并对Int-Packing算法进行改进,提出了Pack2、Pack3和Pack4压缩算法及其相应的压缩态数据访问算法,实验证明Pack3和Pack4极大地提高了压缩态数据访问的效率;研究压缩态匹配问题,对Huffman压缩态数据扫描进行了深入研究,从理论上计算出了在不同数据规模下用超字母表扫描Huffman压缩态数据时的最佳超字母长度,实验结果表明该理论值与实际基本相符,在实践中具有很大的指导意义。

论文目录

• 提要
• 第1章 概述
• 1.1 背景与研究意义
• 1.2 国内外研究现状
• 1.2.1 列存储数据库系统
• 1.2.2 数据压缩在列存储数据库中的应用
• 1.2.3 压缩态模式匹配
• 1.3 本文主要工作及组织结构
• 第2章 列存储数据库核心技术
• 2.1 基本概念
• 2.1.1 存储粒度
• 2.1.2 高效的数据压缩
• 2.1.3 压缩态数据运算
• 2.1.4 潜在的高并行性
• 2.2 数据存储
• 2.2.1 数据表的存储
• 2.2.2 其它数据的存储
• 2.2.3 数据压缩
• 2.3 查询优化
• 2.4 物化策略
• 2.4.1 早期物化和晚期物化
• 2.4.2 平行物化和流水线物化
• 2.5 案例分析
• 2.5.1 MonetDB
• 2.5.2 CStore
• 第3章 数据列压缩
• 3.1 主流压缩算法
• 3.1.1 Huffman编码
• 3.1.2 LZ系列压缩
• 3.2 轻量级数据压缩
• 3.2.1 行程编码（Run Length Encoding，RLE）
• 3.2.2 差值压缩（Delta Compression）
• 3.2.3 粗粒度字典压缩
• 3.2.4 位图（Bitmap）
• 3.3 压缩态SQL运算
• 3.3.1 排序（ORDER BY）
• 3.3.2 分组（GROUP BY）
• 3.3.3 链接（JOIN）
• 3.4 频繁字节压缩
• 3.4.1 频繁段压缩
• 3.4.2 RLE与频繁段压缩
• 3.4.3 Delta-Value与频繁段压缩
• 3.4.4 Int-Packing与频繁段压缩
• 3.4.5 频繁段压缩算法的局限性
• 3.5 总结
• 第4章 压缩态数据访问
• 4.1 压缩态数据访问的必要性
• 4.2 Int-packing压缩态数据随机定位
• 4.2.1 原始定位算法
• 4.2.2 对压缩态数据进行双向定位
• 4.2.3 将标志位聚集到一起
• 4.2.4 对标志位定长编码
• 4.2.5 实验结果
• 4.2.6 结论
• 4.3 其它轻量级压缩态数据定位
• 4.3.1 游程编码（RLE）
• 4.4 总结
• 第5章 压缩态匹配问题
• 5.1 问题定义
• 5.2 一种错误的观点
• 5.3 常用策略
• 5.3.1 在压缩态的数据中匹配压缩态的模式
• 5.3.2 边扫描边匹配
• 5.4 超字母集
• 5.4.1 自动机与模式匹配
• 5.4.2 超字母集在自动机模式匹配中的应用
• 5.4.3 用超字母集扫描Huffman压缩态数据
• 5.4.4 最佳超字母长度
• 5.4.5 对比分析
• 5.5 总结
• 第6章 结 论
• 6.1 总结
• 6.2 下一步工作
• 参考文献
• 致谢
• 摘要
• Abstract