本文分享《DB2 with BLU Acceleration: So Much More than Just a Column Store》文章压缩的设计和存储层数据格式。
背景
DB2 with BLU Acclearation，简称DB2 BLU，是深度集成在DB2，用于加速AP查询需求的列存DBMS。对比DB2行存，它在 read-mostly的BI query上做到1050倍的加速比，同时压缩比提高310倍。DB2 BLU提供了在行存和列存无缝衔接的体验，并且支持行列混存的查询。
文章介绍的是DB2 BLU 2nd generation，1代的BLU定位是集成在IBM其他产品的内存列存DBMS，和PolarDB IMCI类似，需要copy一份行存的数据。DB2 BLU 2nd generation和1st generation的最大区别在于列数据独立存在，不需要从行存copy，通过内部工具实现两者间高效数据迁移(待调研)。
DB2 BLU的一个亮点是压缩设计，它深刻影响了存储层和执行层的设计和优化，我们将在下文对该压缩设计和存储层数据布局设计对压缩的支持进行分析。
基于频数聚类的列级别字典压缩
我们首先介绍DB2 BLU的压缩设计，它深刻影响了整体的data layout，包括page format的设计等，并在存储上为优化查询性能提供了基本条件。DB2 BLU的数据压缩是列级别的字典压缩，论文称之为基于频数聚类的字典压缩(frequency-based dictionary compression)。简单来说就是用频率聚类后再类内压缩。可以不严格地用哈夫曼编码类比，基于频数聚类相当于在哈夫曼树中把相同高度的数据构成一类，它们的编码长度相同。BLU称每个类为一个Frequency Partition。
不严格地用哈夫曼编码类比基于频数聚类的字典压缩，聚类方法是把相同高度的数据构成一类，
因为它们的编码长度相同。例如图中A单独构成一类，B和C构成一类。
基于频数聚类的列级别字典压缩具体细节包括:
- Prepare, sample and build histogram。采样发生在基于行存建立列存数据(建立基线数据)时，或者初次建立列存并逐渐插入数据达到一个阈值时。通过采样获取histogram并由compression optimizer对数据进行frequency-based划分以达到最优压缩比。
- Build dictionary in one of three dictionary entries’ types. BLU对字典中的dictionary entry进行排序，因此编码具有保序性。BLU字典中的dictionary entry有三类，(1) Full data values (2) base values for offset coding (3)common bit prefixes，这三类使得BLU字典可以编码大部分数据类型。(1)类型通常用于种类有限的字符串，(2)类型通常编码integer类型的数据，而(3)类型基于二进制数据编码，通用性最高，但涉及不定长度的位数计算，效率最低。
- Data augmentation with page level dictionary。BLU字典使用采样，面向列级别构建，因此存在无法编码新数据的情况，新数据只能以raw data存储在page中，其细节见存储层设计。BLU会在page中构建页内字典，尝试压缩这部分raw data数据和尝试更少的bit表示非raw data的部分。由于页数据有局部性，其分布通常为列数据分布的子集。例如某partition存在8个类，使用3个bit编码，而页中该partition数据只有2种，因此仅需要1个bit即可。**页级别字典的dictionary entry是列级别字典的value，相当于字典增加了一层成为树状结构。**使用页级别字典，BLU进一步压缩了数据。
- Global coding. 由于列进行了frequency-based划分partition，数据的编码是partition相关的。为利用列级别字典优化join和group，DB2 BLU设计了global coding，对value产生进行partition无关的编码。Global coding的设计是partition相关的编码上增加一个值，该值为编码所属的partition前的所有partition的大小总和，其结果其实就是Partition Start Seqence + Partition offset。在求和不会溢出的前提下，编码后的结果仍是唯一的。Global coding的设计应该是使编码成为fixed length，便于后续在压缩的join和group by算子的比较。
下面的图示，以字符串“Frank”的编码流程说明上述的列级别字典压缩细节。
DB2 BLU的字典结构, 以Frank为例，它在Partition 1中，因此被Partition字典映射为1，
而在Page N中使用Page 字典映射为0，为存储时的实际编码值。查找字符串所在的partition。DB2 BLU论文未说明如何找到数据在哪个partition中，可能需要利用保存histogram结合compression optimizer来查找。
数据布局设计
接下来我们关注存储层的数据布局设计，正如@原峰(dongsheng.zds)在空间管理设计中提到的，定长存储单位需要做精细化的数据格式前期设计，DB2作为成熟的商业数据库产品，使用fixed size page实现逻辑统一的，精细化的空间管理。为了支持列级别的字典压缩方法，数据布局与基于频数聚类的字典压缩设计对应。
以下我们介绍DB2 BLU存储涉及的术语，概念等。BLU存储层数据的布局设计，具体见page的数据布局图。
- **Column group. **DB2 BLU可以将列按group存储，最常见的是null indicator和列组成column group。
- **Tuplet. **组成Column group的列，其中同一行的数据所组成的一个元组称为Tuplet。
- **TSN. **表示列数据按某种顺序存储，通常与主键序对应，在Page Header中以StartTSN, TSN Count 二元组表示。作为索引值不实际存储。
- **Page Map.**根据Page的StartTSN构建的B+Tree索引。
- **Cell. **页内的partition和column group，确定了cell的类型，即cell由该column group所对应的一种partition组成。
- **Region. **页内相同的partition的cell构成region。
- **Bank. **每个bank数据都是同一列构成。cell对应的列在bank的位置相同。Bank数量与cell列数量一致。
- **Tuple map. **根据数据在页内偏移标识数据所在的Region。
特殊处理
- New fixed length’s raw data, 数据仍按bank组织，放在对应位置。
- New variable length’s raw data，使用extra variable-width data bank存储数据，例如新的varchar将被compact到一起。在region中的bank存储数据在extra variable-width data bank的(offset, length)，由于partition的存在，难以在extra variable-width data bank找到相邻的offset，因此必须在bank中存储length.
TODO: 添加展示terminology之间包含关系的框图
下面是查询列的一行非特殊数据的流程:
- 使用TSN在Page Map中寻找page和page中的offset。
- 使用Tuple Map以及page中的offset，确认数据所在的Region及region中的offset。
- 在Region中确定所在的Bank，使用offset获取page specific dictionary编码。
- 使用page specific dictionary编码获取原始值。
小结
此节主要总结DB2 BLU基于频数聚类的字典压缩设计的部分优点和缺点。
优点:
- 列级别的压缩设计，使得字典压缩支持包括predicate(range, in), joins, grouping操作的压缩数据计算。
- Frequency partition和页内二级字典，全局+局部信息，使得数据压缩比更高。
- …
缺点:
- 影响数据布局设计，查询逻辑复杂，工程实现复杂度高。
- 数据在页中按partition划分，按TSN顺序访问数据的效率低(需要在tuple map/多个region间跳转，影响cache命中)。
- 未提到如何处理字符串的collation问题。
- …
TO BE CONTINUED
后续补充DB2 BLU的执行层介绍，重点在基于压缩数据计算的优化部分
