行/列存储分析以及压缩算法简要介绍。
Database Workloads
On-Line Transaction Processing(OLTP)：侧重于插入/更新的写入操作，查询一般不会一次性处理大量数据。
On-Line Analytical Processing(OLAP)：从既有数据中读取大量数据进行计算分析。
Hybrid Transaction + Analytical Processing：综合考虑上述两种工作负载，并兼容上述两种特性。
Storage Models
存储模型指定 tuple 在页面（page）内的物理布局方式，并影响磁盘与内存中的组织形式。
N-ary Storage Model（NSM）/ 行存储
将一个元组的所有属性连续存储在同一页面，对少量数据能做到快速插入、更新、删除，利于OLTP工作。
物理布局如图所示，每个元组拥有自己的header（其中包含例如空值bitmap之类的元数据），随后跟随元组所有属性值，因此一次读取可以获取整行数据，无需跳转其他页面。
容易理解行存的问题在于，假设查询中仅仅涉及特定字段的值，但我们必须读取整个元组所在页面。最坏的情况下，我们指定查询的数据行均不在统一页面，则将加载大量冗余数据；同时行存模型中多个不同类型字段存储于同一页面，往往难于压缩。
Decomposition Storage Model （DSM）/ 列存储
将所有元组的同一属性连续存储在同一页面。
页内物理布局如图所示，header中依然是一些元数据。随后是所有元组的同一字段值连续存储在一起。
如何区分不同元组：
- 固定长度偏移量：适用于定长字段；
- 为列中每一个值存储一个元组ID，使用额外数据结构来表示；
如何处理变长字段：
- 使用偏移量数组（offset array）记录每个值的位置；
- 或采用长度前缀 + 数据区分离的布局；
- 在此基础上可以进一步叠加字典编码等压缩技术。
使用列存的优点在于我们避免了上述行存面对针对特定字段而导致的冗余数据读取问题，降低磁盘IO次数；同时允许较好的数据压缩。
但也存在缺点，点查、插入、更新、删除场景下都会较慢，因为需要从多个列块中重构整行 tuple。
Hybrid Storage Model （PAX）/ 混合
PAX（Partition Attributes Across）是在“页内”进行列式分组的混合布局模型，即在同一page内部按列分块存储，但page之间仍按行组织。PAX的目标是在利用列存优势的同时，保留空间局部性，即统一元组数据应当彼此接近。
Parquet、ORC、Arrow属于文件级或内存级列式格式，在“分块列存”思想上与PAX有相似之处。
如图所示，在PAX File中，表中所有数据行被划分为多个行组，行组内部使用列存储，并维护一些元数据。
注意：行组大小与之前所说的页面并不相同，一般认为PAX file是用于分析的不可变文件，因此行组大小设置的较大，Parquet中默认行组大小为128M；ORC固定为100w个元组。
Data Compression
Naive Compression：MySQL InnoDB Compression
使用通用算法进行数据压缩，压缩范围取决于提供的输入，例如ZStandard。
对于MySQL，其数据库文件结构如图所示：
- mod log：用于记录页内增量修改，从而避免每次修改都解压整页；
- compressed page：压缩后数据页。
值得注意的是，mysql规定一个压缩页（包含其mod log）可选四种大小：1、2、4、8KB。如果当前页大小小于下一个可选大小，则进行padding，目的是能够使用固定长度偏移量跳转页。
那么对于盲写或者读取被mod log吸收后的修改数据：
- 无需解压原始数据页；
- 直接写入mod log/返回mod log中的最新值。
如果涉及读取mod log中没有的数据，那么必须进行解压缩，扩展成MySQL标准的16KB页面。
Columnar Compression
针对列存的压缩方式，因为相同属性存在可控值域，可以做到行存无法实现的一些压缩。
Run-Length Encoding
思路：同列中出现连续重复值，则只存储（值，频次）。
当然，排序后压缩效果更好：
Bit Packing
思路：如果列中所有值都远小于其最大可能值，则无需存储未使用的位。
Patching / Mostly Encoding
思路：对bit packing过程中出现异常值的一种补丁，即摘出异常值构成辅助表，对其余数据进行bit packing。
Bitmap Encoding
思想：为属性列中所有的可能值维护一个独立bitmap，标记对应位是否为1来确认真实值，但要求当前属性最大值确定。
若基数很高，则必须维护较多bitmap，可能影响整体压缩性能表现；插入操作必须更新所有 bitmap 向量长度。
Delta Encoding
思想：记录基数与各个值相对基数的差值，可以借助RLE进一步压缩。
Dictionary Compression
思想：维护字符串-整数映射表，存储时替换为相应整数。
进一步地，排序后可与RLE等编码方式叠加获得更高压缩比，并加速范围查询。
