大数据时代，单一的数据库系统已经不能满足用户的所有业务需求，OLAP 场景往往数据量大，查询复杂，需使用专门的数据分析类产品，如 GreenPlum；OLTP 场景往往操作较简单，要求响应及时，这也是多数关系数据库系统擅长的场景。AP 系统的数据通常需要定期从 TP 系统同步以进行分析，这也就造成 AP 系统的实时性较差，如只能查询 T+1 的数据。为实现实时分析，很多数据库系统在混合负载方面做了很多工作，逐步支持大数据量下的复杂查询，自己先消化一部分分析场景，对于依然无法满足的场景，再使用其他产品实现。
在数据分析场景下，列存比行存更有优势。Oracle 从 12c 开始引入 in-memory 组件，使其在数据实时分析和混合负载情况下的性能大幅提升，其主要特性是 In-Memory Column Store (IM column store) ，在存储中持久化的数据依然是行存，在内存中维护行存和列存两种模式的数据，行存用于 OLTP 场景，列存用于 OLAP 场景。SQL Server 同样支持 Columnstore indexes，其性能较行存有高达10倍的提升。
PostgreSQL 在列存方面也做了一些尝试，本文介绍[1]中提出的一种 PostgreSQL 列存索引（Column Store Index）实现方法，该索引以列存形式组织数据，数据表的 INSERT/UPDATE/DELETE 操作均被同步到列存索引中，以下将从列存索引结构，并发控制，查询执行等方面介绍其如何增强 PostgreSQL 的 OLAP 处理能力。
创建列存索引
PostgreSQL 中的数据是以堆表组织的，所有索引都可以认为是二级索引（secondary index），索引与数据完全隔离，存储在单独的文件中，并且为扩展新的索引提供了接口，只需实现这些接口即可自定义一个新的索引。
本文引入一种新的索引类型 Column Store Index（CSI），以列存形式组织数据，加速 OLAP 场景下的查询性能。当执行 INSERT/UPDATE 命令将数据插入/更新至数据表时，会调用以上接口中实现的回调函数 aminsert 在对应索引中插入数据。然而，PostgreSQL 中并没有 DELETE 命令对应的回调函数，为迅速将删除操作应用到 CSI 中，为 PostgreSQL 扩展一个新的回调函数 amdelete。
创建 CSI 的语法如下：
CREATE INDEX indexname ON tablename USING csi (a, b, c);以上 SQL 创建一个 CSI 索引，索引中每个列对应的数据存储在一个文件中，本例中的索引对应三个文件。
列存索引结构
为保证 CSI 的时效性，行存数据的变更需及时反映到 CSI 中，但又要尽量减小因此带来的性能损耗，尤其不能影响 OLTP 场景的性能，因此，文中引入了三种结构：Insert/Delete Lists, ROS 和 Local ROS。
从下图可知，数据表的变更先缓存在 Insert/Delete 列表中，后台进程异步地将列表中对应的数据转换为列存索引数据（ROS），如果有查询请求，则将 Insert/Delete 列表中尚未转换为列存的数据临时转换为列存，即 Local ROS，再与 ROS 中的列存数据一起供查询使用。
Insert/Delete Lists（InsL/DelL）
CSI 中，每个索引列对应一个文件，如果每次数据变更都同步等待索引列更新完成，将会是非常耗时的，为此，文中引入了两个结构，Insert Lists（InsL） 和 Delete Lists（DelL），数据的增删都同步记录在这里两个列表中，列表中仅记录数据的唯一标识符 TID（Tuple-ID）。
数据从行存转换为列存是通过后天转换进程异步完成的，其定期将 InsL 中记录的 TID 对应的行数据转换为列数据，保存在 ROS（Read-Optimized-Storage）中。
ROS
为高效管理 CSI 中的数据，ROS 中的数据被划分为称为 extent 的单元，每个 extent 默认保存 262,144 行数据，数据转换、写文件以及与查询执行引擎访问数据均以 extent 为单位。如 InsL 中的 TID 数量足够填充一个 extent 时，会将其引用的数据转换至 ROS 中；对于 InsL 和 DelL 中都有的 TID，说明其已经被删除，无需转换，对于仅在 DelL 中有的 TID 则将其记录在 DeleteVector 中，每个 extent 都会有一个 DeleteVector。
Local ROS
由于从 InsL/DelL 转换行数据至 ROS 的列数据是异步的，当有查询请求时，并非所有数据都在 ROS 中，还有一部分在 InsL/DelL 中，因此，将 InsL/DelL 中尚未转换至 ROS 的数据临时转换为列存格式，称其为 Local ROS。
并发控制
PostgreSQL 中使用 MVCC 作为其并发控制策略，每个数据行（tuple）中都记录了插入该行的事务 ID（xmin）和删除该行的事务 ID（xmax），每个查询或者事务都会有一个快照（snapshot）记录查询/事务开始时的最大事务 ID，最小事务 ID，以及活跃事务列表，根据该快照和数据行上的 xmin，xmax 信息即可判断当前行对当前查询/事务是否可见。
CSI 索引不能破坏以上的数据可见性判断规则，在 InsL/DelL 中同样记录了 tuple 的 xmin 和 xmax 信息，其转换为 ROS 的规则如下：
- 对于 InsL 中的数据，只有产生该数据的事务已经提交且对所有现存事务均可见才能将其转换至 ROS；
- 同理，DelL 中，只有删除该数据的事务已经提交且对其他事务均可见时才能将其记录在 DeleteVector 中。
这样做可以确保 ROS 中存储的总是在某一时刻对所有事务均可见的数据。
对于 ROS 中的数据，如果每行数据均记录其 xmin 和 xmax，据此做可见性判断，其处理代价是很高的。为此，在每个 extent 中记录产生和删除该 extent 的事务 ID，分别为 Xgen 和 Xdel，只有满足 Xgen <=? XID < Xdel 的 extent 对事务 XID 是可见的。
以下图为例，最初有 5 个 extent，其 Xgen 分别为 X100，X120，X130，X140，X150。假设 query#1 执行前，最后一个转换的 extent 其 Xgen 是 X150，则该查询对所有 extent 均可见；对于 InsL 中尚未转换为 ROS 的数据，通过记录的 xmin 和 xmax 进行可见性判断，对于可见的数据将其转换为 Local ROS。
不妨假设在 query#2 之前，有一个 XID 是 200 的事务，做了一次 ROS 转换，T100 和 T101 满足转换条件（产生该数据的事务均已提交，且对其他事务可见），同时 extent 1 中已经删除的数据超过了某个阈值，因此，该 ROS 转换将 extent 1 中尚未被删除的数据拷贝至新的 extent 5，并转换 InsL 中的 T100 和 T101，转换完成后将 Xgen 设置为 X200。对于随后而来的 query#2，其可见的 extent 有 0，2，3，4，5，extent 1 由于 X120 <= ?X200 < X200 不成立，对该查询不可见，其中的数据已经被拷贝至 extent 5。
查询执行
查询重写
引入 CSI 之后，需要在生成查询计划时，考虑使用 CSI 的代价是否更低，从而将原生的计划节点替换为对应的 CSI 计划节点。CSI 可以看做是一个覆盖索引（Cover Index），对于仅访问 CSI 就可以获取所有数据且代价较访问行存小的查询均可以考虑使用。
目前支持重写的计划节点有 SeqScan，Aggregation 和 Sort，其对应的 CSI 计划节点为 CSI Scan，CSI Aggregation，CSI Sort，其重写的实现基于 PostgreSQL 9.5 以后提供的 Custom Scan API。
计划执行
重写后的计划从 ROS 和 Local ROS 访问数据，读数据时会过滤 DeleteVector 和 DelL 中已经被删除的数据，如下图所示：
向量化处理
为充分利用列存的优势，处理表达式计算时采用一次一批的方式，其处理单位为 vector，默认每个 vector 包含 128 行数据，进而使用 SIMD，实现高效数据处理。
并行处理
使用 CSI 时，会尽量以并行模式执行，每个后台工作进程（Dynamic Background Worker，DBW）处理不同的 extent，具体并行度依赖于优化器的具体实现。以下图为例，SMC（Shared Memory Context）表示动态创建的多进程间共享的内存，每个 DBW 处理一部分数据，并将局部结果放置在对应的 SMC 中，用户的处理进程（backend process）将局部结果汇总并计算出最终结果。
PostgreSQL 的并行处理实现可以参考这篇文章。
总结
本文介绍了一种新的 PostgreSQL 索引结构，列存索引（CSI），其将行存数据以索引的形式按列存储，同时配合其他组件的改造，如实现列存算子，优化器通过代价估算生成访问列存索引的计划，向量化处理以及并行处理等，充分发挥列存优势，从而在大数据量复杂查询的 OLAP 场景获得更高的性能。
个人认为，列存索引是一种很好的将行存与列存整合的方式，PostgreSQL 本身对于索引的接口式实现，以及 Custom Scan API 机制，使得列存索引的实现非常灵活且侵入性不强。本文仅做原理性介绍，并没有太多的实现细节，感兴趣的读者可以参考 [3] 中作者提交的 patch，该 patch 目前尚未合入社区。
参考文献
[1] Nakamura, Minoru , et al. "Extending postgreSQL to handle OLXP workloads." Fifth International Conference on Innovative Computing Technology IEEE, 2015.
[2] https://wiki.postgresql.org/wiki/Future_of_storage
[3] https://www.postgresql.org/message-id/flat/CAJrrPGfaC7WC9NK6PTTy6YN-NN+hCy8xOLAh2doYhVg5d6HsAA@mail.gmail.com
