列存索引技术架构介绍

通过一套白名单机制来实现兼容性。 使用白名单机制是基于如下几点考量。

• 系统可用资源（主要是内存）限制。

  一般情况下，不会为数据库中全部表的所有列上都创建列索引。当一条查询语句中使用到的列没有在列存中存在时，其不能在列存上执行。

• 性能。

  重写一套面向列存的SQL执行引擎，包括所有的物理执行算子和表达式计算，其所覆盖的场景相对MySQL原生行存能够支持的范围有欠缺。当下发的SQL语句中包含一些列存索引不支持的算子片段或者列类型时，需要能够识别拦截并切换回行存执行。

目前，白名单规则校验的内容包含SQL语句中的数据类型、算子、计算表达式以及其他场景。其他场景如不支持multi statement等。

MySQL已经发展了数十年，其支持的各种列类型和SQL语法非常丰富。在IMCI中，初期重点优化在分析型查询语句中最常见的SQL性能问题。即使适用场景有所限制，IMCI能够运行的SQL语法对MySQL功能的兼容性也远超绝大部分OLAP系统。对于那些不能在列存上执行的SQL，则直接回退到MySQL原生执行引擎，因此实现了100%的MySQL兼容。

Plan转换的目的是将MySQL的原生逻辑执行计划表示方式AST转换为IMCI的Logical Plan。在生成IMCI的Logical Plan之后，会经过Optimize过程，继而生成Physical Plan。

Plan转换只需要遍历整个执行计划树，将MySQL优化后的AST转换成以relation operator为节点的树状结构即可。在这个过程中，会进行类型的隐式转换，以兼容MySQL灵活的类型系统。

Plan转换生成的是一个等价的Logical Plan，其需要被转换成Physical Plan才能被执行器执行。目前IMCI的Optimizer比较简单，除了一些基本的执行计划优化（如决策是使用HashJoin还是使用NestedLoop Join）外，Optimizer最主要的作用是将目前IMCI执行器不支持的子查询转换为一个等价的Join操作。

由于存在行存和列存两套执行引擎，优化器在选择执行计划时有了更多的选择，其可以对比行存执行计划的Cost和列存执行计划的Cost，并使用代价最低的执行计划。

在PolarDB中，除原生MySQL的行存串行执行外，还有能够发挥多核计算能力的基于行存的Parallel Query功能。因此，实际优化器会在行存串行执行、行存Parallel Query、以及IMCI三个之中选择其一。在目前的迭代阶段，优化器按如下的流程执行：

1. 执行SQL的Parse过程并生成LogicalPlan，然后调用MySQL原生优化器，并执行优化操作（join order等）。同时该阶段获得的逻辑执行计划会转给IMCI的执行计划编译模块，并尝试生成一个列存的执行计划（此处可能会被白名单拦截并回滚回行存）。

2. PolarDB的Optimizer会根据行存计划，计算得出一个面向行存的执行Cost。如果此Cost超过一定阈值，则会尝试下推到IMCI执行器使用IMCI_Plan执行。

3. 如果IMCI无法执行此SQL，则PolarDB会尝试编译出一个Parallel Query的执行计划并执行。如果无法生成PQ的执行计划，则说明IMCI和PQ均无法执行此SQL，则回滚回行存执行。

上述策略是基于这样一个判断，从执行性能上进行对比：行存串行执行 < 行存并行执行 < IMCI。 对比SQL兼容性，IMCI < 行存并行执行 < 行存串行执行。但是实际情况会更加复杂，例如：某些情况下，基于行存有序索引覆盖的并行Index Join会比基于列存的Sort Merge join有更低的Cost。按照当前策略，则会选择IMCI列存执行。

IMCI执行器引擎使用经典的火山模型，但是借助了列存存储以及向量执行来提升执行性能。

火山模型中，SQL生成的语法树所对应的关系代数中，每一种操作会抽象为一个Operator，执行引擎会将整个SQL构建成一个Operator树，查询树自顶向下调用Next()接口，数据则自底向上被拉取处理。该方法的优点是其计算模型简单直接，通过把不同物理算子抽象成一个个迭代器。每一个算子只关心自己内部的逻辑即可，使得各个算子之间的耦合性降低，从而比较容易写出一个逻辑正确的执行引擎。

• 在IMCI执行引擎中，每个Operator也使用迭代器函数来访问数据，但不同的是每次调用迭代器会返回一批数据，而不是一行，可以认为这是一个使用了向量化模式的火山模型。

  

• 串行执行受制于单核计算效率、访存延时、IO延迟等限制，执行能力有限。而IMCI执行器在几个关键物理算子（Scan/Join/Agg等）上均并行执行。除物理算子需要支持并行外，IMCI的优化器也支持生成并行执行计划，优化器在确定一个表的访问方式时，会根据需要访问的数据量来决定是否启用并行执行，如果确定启用并行执行，则会参考一系列状态数据（包括当前系统可用的CPU/Memory/IO资源、目前已经调度和在排队的任务信息、统计信息、query的复杂程度、用户可配置的参数等）。 根据这些数据会计算出一个推荐的DOP值给一个算子，而一个算子内部会使用相同的DOP。同时，DOP也支持用户使用Hint进行设定。

  

基于以上两点优化思路，重新实现了所有物理执行算子，包括TableScan、HashJoin、NestedLoopJoin、Groupby等。下面以HashJoin为例展示执行器的并行化及向量化加速效果。在IMCI中，HashJoin按如下流程执行：

向量化执行解决了单核执行效率低的问题，而并行执行突破了单核的计算瓶颈。二者结合使得IMCI执行速度相比传统MySQL行式执行有了数量级的提升。

AP型场景，SQL中经常会包含很多涉及到一个或者多个值、运算符和函数组成的计算过程，这都是属于表达式计算的范畴。表达式的求值是一个计算密集型的任务，因此，表达式的计算效率是影响整体性能的一个关键的因素。

传统MySQL的表达式计算体系以一行为一个单位的逐行运算，一般称其为迭代器模型实现。由于迭代器对整张表进行了抽象，整个表达式实现为一个树形结构。但是，这种抽象会同时带来性能上的损耗，因为在迭代器进行迭代的过程中，每一行数据的获取都会引发多层的函数调用。同时，逐行地获取数据会带来过多的 I/O，对缓存也不友好。MySQL采用树形迭代器模型，是受到存储引擎访问方法的限制，导致其很难对这些计算复杂的逻辑进行优化。

而在列存格式下，由于每一列的数据都单独顺序存储，涉及到某一个特定列上的表达式计算过程都可以批量进行。对每一个计算表达式，其输入和输出都以Batch为单位，在Batch的处理模式下，计算过程可以使用SIMD指令进行加速。

向量化表达式的关键优化点：

• 充分利用列式存储的优势，使用分批处理的模型代替迭代器模型，使用SIMD指令重写了大部分常用数据类型的表达式内核实现。例如，所有数字类型（int、decimal、double）的基本数学运算（+、 -、*、/、abs），全部都使用对应的SIMD指令实现。在AVX512指令集的加持下，单核运算性能数倍提升。

  

• 采用了与PostgreSQL类似表达式实现方法：在SQL编译及优化阶段，IMCI的表达式以一个树形结构来存储（与现有行式迭代器模型的表现方法类似）。但是，在执行之前会对该表达式树进行一个后序遍历，将其转换为一维数组来存储，在后续计算时只需要遍历该一维数组结构即可以完成运算。由于消除了树形迭代器模型中的递归过程，计算效率更高。同时该方法对计算过程提供简洁的抽象，将数据和计算过程分离，适合并行计算。

在MySQL插件式的存储引擎框架下，增加列存支持最简单的方案是实现一个单独的存储引擎，如Inforbright以及MarinaDB的ColumnStore都采用了这种方案。而PolarDB采用了将列存实现为InnoDB的二级索引方案，主要基于如下几点考量：

• InnoDB原生支持多索引，Insert、Update和Delete操作都会以行粒度apply到Primary Index和所有的Secondary Index上，并且保证事务。将列存实现为一个二级索引可以复用这套事务处理框架。

• 在数据编码格式上，二级索引的列存可以和其他行存索引使用完全一样的格式，直接内存拷贝即可，不需要考虑charset和collation等信息。

• 二级索引操作非常灵活，可以在建表时指定索引所包含的列，也可以后续通过DDL语句对一个二级索引中包含的列进行增加或者删除操作。例如，用户可以将需要分析的int、float和double列加入列索引，而对于一般只需要点查但是又占用大量空间的text和blob字段，则可以保留在行存中。

• 崩溃恢复过程可以复用InnoDB的Redo事务日志模块，与现有实现无缝兼容。同时也方便PolarDB的物理复制过程，支持在独立RO节点或者Standby节点上生成列存索引提供分析服务。

• 二级索引与主表有一样的生命周期，方便管理。

  

如上图所示，在PolarDB中，所有Primary Index和Secondary Index都实现为一个B+Tree。而列索引在定义上是一个Index，但其实是一个虚拟的索引，用于捕获对该索引覆盖列的增删改操作。

对于上面的表，其主表（Primary Index）包含（C1、C2、C3、C4、C5） 5列数据， Secondary Index索引包含（C2、C1）两列数据，在普通二级索引中，C2与C1编码成一行保存在B+tree中。而其中的列存索引包含（C2、C3、C4）三列数据。在实际物理存储时，会对三列进行拆分独立存储，每一列都会按写入顺序转成列存格式。

列存实现为二级索引的另一个好处是执行器的工程实现非常简单，在MySQL中已经存在覆盖索引的概念，即一个查询所需要的列都在一个二级索引中存储，则这个二级索引中的数据满足查询需求，使用二级索引相对于使用Primary Index可以极大减少读取的数据量进而提升查询性能。当一个查询所需要的列都被列索引覆盖时，借助列存的加速作用，可以数十倍甚至数百倍的提升查询性能。

对Column Index中的每一列，其存储都使用了无序且追加写的格式。结合标记删除及后台异步compaction实现空间回收。其具体实现上有如下几个关键点：

• 列索引中记录按RowGroup进行组织（目前每个RowGroup包含64K行），每个RowGroup中不同的列会各自打包形成DataPack。

• 每个RowGroup都采用追加写，分属每个列的DataPack也是采用追加写模式。对于一个列索引，只有Active RowGroup负责接受新的写入。当该RowGroup写满之后即冻结，其包含的所有Datapack会转为压缩格保存到磁盘上，同时记录每个数据块的统计信息便于过滤。

• 列存RowGroup中每新写入一行都会分配一个RowID用于定位，属于一行的所有列都可以用该RowID计算定位，同时系统维护PK到RowID的映射索引，以支持后续的删除和修改操作。

• 更新操作采用标记删除的方式，对于删除操作直接设置BitMap即可。对于更新操作，首先根据RowID计算出其原始位置并设置删除标记，然后在ActiveRowGroup中写入新的数据版本。

• 当一个RowGroup中的无效记录超过一定阈值，则会触发后台异步compaction操作，其作用一方面是回收空间，另一方面可以让有效数据存储更加紧凑，提升分析型查询单的效率。

  

采用这种数据组织方式，一方面满足了分析型查询按列进行批量扫描过滤的要求。另一方面对于TP型事务操作影响非常小，写入操作只需要按列追加写到内存即可，删除操作只需要设置一个删除标记位。而更新操作则是一个标记删除附加一个追加写。列存在支持事务级别更新的同时，几乎不影响OLTP的性能。

以下两种情况会执行行转列操作：

• 第一种情况：使用DDL语句对部分列创建列索引（对一张已存在的表有分析型需求），此时需要扫描全表数据以创建列索引。

• 第二种情况：在事务操作过程中对涉及到的列执行行转列。

对于全表行转列的情形，使用并行扫描的方式对InnoDB中的Primary Key进行扫描，并依次将所有涉及到的列转换为列存形式，该操作的速度非常快，其基本仅受限于服务器可用的IO吞吐速度和CPU资源。该操作是一个online-DDL过程，不会阻塞在线业务的运行。

在一张表上建立列索引之后，所有的更新事务将会同步更新行存和列存数据，以保证二者的事务一致性。下图演示了开启和关闭IMCI功能的差异性。

• 未开启IMCI功能时，事务对所有行的更新都会先加锁，然后在对数据页进行修改，在事务提交之前会对所有加锁的记录一次性释放锁。

• 开启IMCI功能之后，事务系统会创建一个列存更新缓存，在所有数据页被修改的同时，会记录所涉及到的列存的修改操作，在事务结束并释放锁之前，该缓存会应用到列存系统。

对于一般的OLTP型请求，最后的内存数据页更新只占事务操作过程的很少一部分时间，因此此方法对TP型事务时延的影响非常小。对于操作了非常多的行的大事务，则会直接将其对列索引的更新实时应用到列存存储，但是在事务提交之前不对外可见，也保证了大事务的提交延时增加在一个非常小的时间范围。同时为了更进一步的降低对TP性能的影响，当AP型查询对数据的实时性要求不高时, 列索引支持异步应用对列存的更新操作。

列存存储提供了与行存一样的事务隔离级别。对于每个写操作，RowGroup中的每一行都会记录修改该行的事务编号，而对于DeleteBitMap，每个标记删除操作也会记录该标志位的事务编号。借助写入事务号和删除事务号，AP型查询可以用非常轻量级的方式获得一个全局一致性的快照。

由前述列举的存储格式可以看出，IMCI中所有的Datapack都采用无序且追加写的方式，因此无法像InnoDB的普通有序索引那样，可以精准的过滤掉不符合要求的数据。在IMCI中，借助统计信息来进行数据块过滤，以此来达到降低数据访问单价的目的。

• 在每个Active Datapack终结写入的时候，会预先进行计算，并生成Datapack所包含数据的最小值、最大值、数值的总和、空值的个数和记录总条数等信息。所有这些信息会维护在DataPacks Meta元信息区域并常驻内存。由于冻结的Datapack中还会存在数据的删除操作，因此统计信息的更新维护会放到后台完成。

• 对于查询请求，会根据查询条件将Datapacks分为相关、不相关、可能相关三大类，从而减少实际的数据块访问。而对于一些聚合查询操作，如count和sum等，可以通过预先计算好的统计值进行简单的运算得出，这些数据块甚至都不需要进行解压。

采用基于统计信息的粗糙索引方案，对于一些需要精准定位部分数据的查询并不是很友好。但是在一个行列混合存储引擎中，列索引只需要辅助加速那些会涉及到大量数据扫描的查询，在这个场景下使用列存索引会具有显著的优势。而对于那些只会访问到少量数据的SQL，优化器通常会基于代价模型计算得出基于行存而得到的一个成本更低的方案。

行列混合存储可以在一个集群中同时支持AP型查询和TP型查询。但很多业务有很高的OLTP型负载，而突发性的OLAP型负载可能干扰到TP型业务的响应时延。因此负载隔离在HTAP数据库中是一个必须支持的功能。借助一写多读架构，可以非常方便地对AP型负载和TP型负载进行隔离。在PolarDB技术架构下，有如下几个部署方式：

• 第一种方式：在RW上开启行列混合存储，此种部署模式可以支持轻量级的AP查询，以TP负载为主，且AP型请求比较少时可以采用。或者使用PolarDB进行报表查询，且数据来自批量数据导入的场景。

• 第二种方式：RW支持OLTP型负载，并启动一个AP型RO开启行列混合存储以支持查询，此种部署模式下CPU资源可以实现100%隔离，同时该AP型RO节点上的内存可以100%分配给列存存储和执行器。但是，由于使用相同的共享存储，因此在IO上会相互产生一定影响。

• 第三种方式：RW和RO均支持OLTP型负载，在单独的Standby节点开启行列混合存储以支持AP型查询，由于Standby是使用独立的共享存储集群，这种方案在第二种方案支持CPU和内存资源隔离的基础上，还可以实现IO资源的隔离。

除上述部署架构上的不同，和可以支持的资源隔离不同之外。在PolarDB内部对于一些需要使用并行执行的大查询，支持动态并行度调整（Auto DOP），这个机制会综合考虑当前系统的负载以及可用的CPU和内存资源，对单个查询所用的资源进行限制，以避免单个查询消耗的资源太多，影响其他请求的处理。