为什么需要压缩
在面向磁盘的数据库，从磁盘中取数据是最大的性能瓶颈。
而在内存数据库中，在速度与压缩率的取舍中总是会选速度，其压缩的主要目的是为了减少内存的需求和处理。（Compressing the database reduces DRAM requirements and processing 减少requirements显而易见，reduce processing如何体现呢）
数据库压缩的目标
压缩后产生固定长度的值；查询时解压尽可能放到后面；无损解压缩
压缩技术
数据特征，什么样的数据是适合压缩的
数据集在某些属性值上有很高的偏斜分布（如Zipfian）；数据集在同一个元组中的属性间有很强的相关性（Zip Code to City）。
有损/无损 压缩
数据库的压缩必须是无损的；有损压缩只能用在应用级；读比原来应读的数据少某种意义上说和压缩一样（比如利用聚合信息）。
Data Skipping
近似查询（有损） 在原来的整表的抽样子集进行查询产生近似结果（适合有没有的查询）
Zone Map（无损）预先计算每个block的列的聚合信息，在DBMS进行查询的时候会检查聚合信息判断是否需要访问这个块
压缩的粒度
Block-level 压缩同一个表中同一块中的元组
Tuple-level 压缩整个元组（行存储NSM）
Attribute-level 压缩一个元组中的一个属性；压缩一个元组中的多个属性
Column-level 压缩多个元组的同一个属性（列存储CSM）
Naive Compression
用通用压缩算法，不考虑语义；只需要考虑计算开销和压缩和解压的速度。
数据在读或者可能修改时需要先解压；如果要连接的数据是以同样的方式压缩的，可能可以直接用压缩数据进行连接
OLAP 列压缩
Null Suppression 对于连续的0或者连续的空（稀疏数据），描述有多少0或者数据在什么位置
run-length 游程编码 压缩一列中相同的数据到一个三元组<value, offset, length>
位图编码
这个和位图索引很像了，用01表示是否，适合像性别之类可选项不多的属性
压缩的实现上有 通用压缩（用标准压缩算法，查询时需要解压缩，不适用于内存数据库）和Byte-aligned Bitmap Codes（用结构化游程编码压缩），下面介绍一种BBC, Oracle BBC，但是已经过时了。
Word-Aligned Hybrid encoding性能更好
BBC都不支持随机访问
Delta Encoding
记录的是同一列中彼此之间值的不同；在本表中或单独的查找表中存一个基础值，其他值存的都是和这个基础值的差值（可以与RLE结合）
Incremental Encoding
记录下一行和上一行的公共前缀，找出最长的那个，然后进行压缩，记录前缀长度和自己独占的。
Mostly Encoding
比如一个属性是long型64位，但是这个属性中存的绝大多数都是32位以下，那么就可以把这个属性用int代替，然后单独记录那些32位以上的数字。
Dictionary Compression
字典压缩，把出现频率高的部分用更小的code代替，在DBSM中应用最普遍；需要支持快速解压缩；需要支持范围查询。
字典压缩有几个问题，字典何时构建；字典的规模（要覆盖多大的范围）；字典用什么数据结构；字典用什么编码模式？
构建 通常有一次构建和增量构建。一次构建就是在一个给定时间点上根据全部的元组来计算字典，对于新加入的元组用单独的字典否则字典要用全部的元组重新计算；增量构建就是把新元组和已经存在的字典合并，可能需要对已经存在的元组进行重新编码
字典规模 块级-只包含一个表中子集；压缩率低但是添加新元组简单；表级-为一整个表构建一个字典，更高的压缩率，更新贵；多表级-可以是覆盖多个表或子表，可能对连接和集合操作有帮助。
跳过val1和val2的连接，直接从压缩数据中读取
编码/解码 编码上采取保序编码编码后的值和原来的值的顺序保持一致。
字典的数据结构 数组-一个变长String数组，一个指针数组-更新贵，因为是有序的，所以涉及到数组的后移问题； 哈希表-快速且紧凑，但不支持范围查询和前缀(%)查询；B+树-比哈希表慢，更少的内存，支持范围查询和前缀查询。
OLTP的索引压缩
OLTP不能用OLAP压缩技术，因为OLTP需要快速的随机访问，动态的解压/压缩热元组对于一个事务的更新太慢了，然而索引会消耗大量的内存。
Hybrid Indexes
一个逻辑索引分成两个物理索引，数据会从一个stage迁移到另一个stage。
Dynamic Stage-存新数据，快速更新
Static Stage - 旧数据，可以压缩，用来只读
(讲的并不很清楚，有机会会看论文Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes
)
