前言
最近分析型数据库在资本市场和技术社区都非常的火热，各种创业公司的创新型产品如雨后春笋般出现。这一方面是因为当前阶段企业日益依赖从数据中寻找增长潜力带来需求的增长，另一方面云原生技术的发展带来现有技术体系的进化和变革，诸如Snowflakes这类产品的成功证明，使用云原生技术再造分析型数据库技术体系是必要的且存在很大的市场机会。
PolarDB MySQL是因云而生的一个数据库系统, 除了云上OLTP场景，大量客户也对PolarDB提出了实时数据分析的性能需求。对此PolarDB技术团队提出了In-Memory Column Index(IMCI）的技术方案，在复杂分析查询场景获得的数百倍的加速效果。
本文阐述了IMCI背后技术路线的思考和具体方案的取舍。PolarDB MySQL 列存分析功能即将在阿里云上线，敬请期待。
一、 MySQL生态HTAP数据库解决方案
MySQL是一款主要面向OLTP型场景设计的开源数据库，开源社区的研发方向侧重于加强其事务处理的能力，如提升单核性能/多核扩展性/增强集群能力以提升可用性等。在处理大数据量下复杂查询所需要的能力方面，如优化器处理子查询的能力，高性能算子HashJoin, SQL并行执行等，社区一直将其放在比较低优先级上，因此MySQL的数据分析能力提升进展缓慢。
随着MySQL发展为世界上最为流行的开源数据库系统，用户在其中存储了大量的数据，并且运行着关键的业务逻辑，对这些数据进行实时分析成为一个日益增长的需求。当单机MySQL不能满足需求时，用户寻求一个更好的解决方案。
1、MySQL + 专用AP数据库的搭积木方案
专用分析型数据库产品选项众多，一个可选方案是使用两套系统来分别满足的OLTP和OLAP型需求，在两套系统中间通过数据同步工具等进行数据的实时同步。更进一步，用户甚至可以增加一层proxy，自动将TP型负载路由到MySQL上，而将分析型负载路由到OLAP数据库上，对应用层屏蔽底层数据库的部署拓扑。
这样的架构有其灵活之处，例如对于TP数据库和AP数据库都可以各自选择最好的方案，而且实现了TP/AP负载的完全隔离。但是其缺点也是显而易见的。首先，在技术上需要维护两套不同技术体系的数据库系统，其次由于两套系统处理机制的差异，维护上下游的数据实时一致性也非常具有挑战。而且由于同步延迟的存在，下游AP系统存储的经常是过时的数据，导致无法满足实时分析的需求。
2、基于多副本的Divergent Design方法
随着互联网而兴起的新兴数据库产品很多都兼容了MySQL协议，因此成为替代MySQL的一个可选项。而这些分布式数据库产品大部分采用了分布式Share Nothing的方案，其一个核心特点是使用分布式一致性协议来保障单个partition多副本之间的数据一致性。由于一份数据在多个副本之间上完全独立，因此在不同副本上使用不同格式进行存储，来服务不同的查询负载是一个易于实施的方案。典型的如TiDB，其从TiDB4.0开始，在一个Raft Group中的其中一个副本上，使用列式存储(TiFlash)来响应AP型负载, 并通过TiDB的智能路由功能来自动选取数据来源。这样实现了一套数据库系统同时服务OLTP型负载和OLAP型负载。
该方法在诸多Research及Industry领域的工作中都被借鉴并使用，并日益成为分布式数据领域一体化HTAP的事实标准方案。但是应用这个方案的前提是用户需要迁移到对应的NewSQL数据库系统，而这往往带来各种兼容性适配问题。
3、一体化的行列混合存储方案
比多副本Divergent Design方法更进一步的，是在同一个数据库实例中采用行列混合存储的方案，同时响应TP型和AP型负载。这是传统商用数据库Oracle/SQL Server/DB2等不约而同采用的方案。
- Oracle公司在在2013年发表的Oracle 12C上，发布了Database In-Memory套件，其最核心的功能即为In-Memory Column Store，通过提供行列混合存储/高级查询优化(物化表达式，JoinGroup)等技术提升OLAP性能。
- 微软在SQL Server 2016 SP1上，开始提供Column Store Indexs功能，用户可以根据负载特征，灵活的使用纯行存表，纯列存表，行列混合表，列存表+行存索引等多种模式。
- IBM在2013年发布的10.5版本(Kepler)中，增加了DB2 BLU Acceleration组件，通过列式数据存储配合内存计算以及DataSkipping技术，大幅提升分析场景的性能。
三家领先的商用数据库厂商，均同时采用了行列混合存储结合内存计算的技术路线，这是有其底层技术逻辑的：列式存储由于有更好的IO效率(压缩,DataSkipping,列裁剪)以及CPU计算效率(Cache Friendly), 因此要达到最极致的分析性能必须使用列式存储，而列式存储中索引稀疏导致的索引精准度问题决定它不可能成为TP场景的存储格式，如此行列混合存储成为一个必选方案。但在行列混合存储架构中，行存索引和列存索引在处理随机更新时存在性能鸿沟, 必须借助DRAM的低读写延时来弥补列式存储更新效率低的问题。因此在低延时在线事务处理和高性能实时数据分析两大前提下，行列混合存储结合内存计算是唯一方案。
对比上述三种方法，从组合搭积木的方法到Divergent Design方法再到一体化的行列混合存储，其集成度越来越高，用户的使用体验也越来越好。但是其对内核工程实现上的挑战也一个比一个大。基础软件的作用就是把复杂留给自己把简单留给用户，因此一体化的方法是符合技术发展趋势的。
二、PolarDB MySQL AP能力的演进
PolarDB MySQL能力栈与开源MySQL类似，长于TP但AP能力较弱。由于PolarDB提供了最大单实例100TB的存储能力，同时其事务处理能力远超用户自建MySQL。因此PolarDB用户倾向于在单实例上存储更多的数据，同时会在这些数据上运行一些复杂聚合查询。借助于PolarDB一写多读的架构，用户可以增加只读的RO节点以运行复杂只读查询，从而避免分析型查询对TP负载的干扰。
1、MySQL的架构在AP场景的缺陷
MySQL的实现架构在执行复杂查询时性能差有多个方面的原因，对比专用的OLAP系统，其性能瓶颈体现多个方面：
1. MySQL的SQL执行引擎基于流式迭代器模型(Volcano Iterator)实现, 这个架构在工程实现上依赖大量深层次的函数嵌套及虚函数调用，在处理海量数据时，这种架构会影响现代CPU流水线的pipline效率，导致CPU Cache效率低下。同时Iterator执行模型也无法充分发挥现代CPU提供的SIMD指令来做执行加速。
2. 执行引擎只能串行执行，无法发挥现代多核CPU的并行话能力。官方从MySQL 8.0开始，在一些count(*)等基本查询上增加并行执行的能力，但是复杂SQL的并行执行能力构建依然任重道远。
3. MySQL最常用的存储引擎都是按行存储，在按列进行海量数据分析时，按行从磁盘读取数据存在非常大的IO带宽浪费。其次行式存储格式在处理大量数据时大量拷贝不必要的列数据，对内存读写效率也存在冲击。
2、PolarDB 并行查询突破CPU瓶颈
PolarDB团队开发的并行查询框架（Parallel Query), 可以在当查询数据量到达一定阈值时，自动启动并行执行，在存储层将数据分片到不同的线程上，多个线程并行计算，将结果流水线汇总到总线程，最后总线程做些简单归并返回给用户，提高查询效率。
并行查询的加入使得PolarDB突破了单核执行性能的限制，利用多核CPU的并行处理能力，在PolarDB上部分SQL查询耗时成指数级下降。
3、Why We Need Column-Store
并行执行框架突破了CPU扩展能力的限制，带来了显著的性能提升。然而受限于行式存储及行式执行器的效率限制，单核执行性能存在天花板，其峰值性能依然与专用的OLAP系统存在差距。要更进一步的提升PolarDB MySQL的分析性能，我们需要引入列式存储：
1. 在分析场景经常需要访问某个列的大量记录，而列存按列拆分存储的方式会避免读取不需要的列。其次列存由于把相同属性的列连续保存，其压缩效率也远超行存，通常可以达到10倍以上。最后列存中大块存储的结构，结合MIN/MAX等粗糙索引信息可以实现大范围的数据过滤。所有这些行为都极大的提升了IO的效率。在现今存储计算分离的架构下，减少通过网络读取的数据量可以对查询处理的响应时间带来立竿见影的提升。
2. 列式存储同样能提高CPU在处理数据时的执行效率，首先列存的紧凑排列方式可提升CPU访问内存效率，减少L1/L2 Cache miss导致的执行停顿。其次在列式存储上可以使用应用SIMD技术进一步提升单核吞吐能力，而这是现代高性能分析执行引擎的通用技术路线（Oracle/SQL Server/ClickHouse).
三、PolarDB In-Memory Column Index
PolarDB In-Memory Column Index功能为PolarDB带来列式存储以及内存计算能力，让用户可以在一套PolarDB数据库上同时运行TP和AP型混合负载，在保证现有PolarDB优异的OLTP性能的同时，大幅提升PolarDB在大数据量上运行复杂查询的性能。
In-Memory Column Index使用行列混合存储技术，同时结合了PolarDB基于共享存储一写多读的架构特征，其包含如下几个关键的技术创新点：
1. 在PolarDB的存储引擎（InnoDB)上新增对列式索引（Columnar Index）的支持，用户可以选择通过DDL将一张表的全部列或者部分列创建为列索引，列索引采用列压缩存储，其存储空间消耗会远小于行存格式。默认列索引会全部常驻内存以实现最大化分析性能，但是当内存不够时也支持将其持久化到共享存储上。
2. 在PolarDB的SQL执行器层，我们重写了一套面向列存的执行器引擎框架(Column-oriented), 该执行器框架充分利用列式存储的优势，如以4096行的一个Batch为单位访问存储层的数据，使用SIMD指令提升CPU单核心处理数据的吞吐，所有关键算子均支持并行执行。在列式存储上，新的执行器对比MySQL原有的行存执行器性有几个数量级的性能提升。
3. 支持行列混合执行的优化器框架，该优化器框架会根据下发的SQL是否能在列索引上执行覆盖查询，并且其所依赖的的函数及算子能被列式执行器所支持来决定是否启动列式执行。优化器会同时对行存执行计划和列存执行计划做代价估算，并选中代价交代的执行计划。
4. 用户可以使用PolarDB集群中的一个RO节点作为分析型节点，在该RO节点上配置生成列存索引，复杂查询运行在列存索引上并使用所有可用CPU的计算能力，在获得最大执行性能的同时不影响该集群上的TP型负载的可用内存和CPU资源。
几个关键关键技术结合使得PolarDB成为了一个真正的HTAP数据库系统，其在大数据量上运行复杂查询的性能可以与Oracle/SQL Server等业界最顶尖的商用数据库系统处在同一水平。
四、In-Memory Column Index的技术架构
1、行列混合的优化器
PolarDB原生有一套面向行存的优化器组件，在引擎层增加对列存功能支持之后，此部分需要进行功能增强，优化器需要能够判断一个查询应该被调度到行存执行还是列存执行。我们通过一套白名单机制和执行代价计算框架来完成此项任务。系统保证对支持的SQL进行性加速，同时兼容运行不支持的SQL.
如何实现100%的MySQL兼容性
我们通过一套白名单机制来实现兼容性目标。使用白名单机制是基于如下几点考量。第一点考虑到系统可用资源（主要是内存）的限制，一般不会在所有的表的所有上都创建列索引，当一个查询语句需要使用到列不在列存中存在时，其不能在列存上执行。第二点，基于性能的的考量，我们完全重写了一套面向列存的SQL执行引擎，包括其中所有的物理执行算子和表达式计算，其所覆盖的场景相对MySQL原生行存能够支持的范围有欠缺。当下发的SQL中包含一些IMCI执行引擎不能支持的算子片段或者列类型时，需要能能够识别拦截并切换回行存执行。
查询计划转换
Plan转换的目的是将MySQL的原生逻辑执行计划表示方式AST转换为IMCI的Logical Plan。在生成IMCI的Logical Plan之后，会经过一轮Optimize过程，生成Physical Plan。Plan转换的方法简单直接，只需要遍历这个执行计划树，将 mysql 优化后的 AST 转换成IMCI 以 relation operator 位节点的树状结构即可，是一个比较直接的翻译过程。不过在这个过程中，也会做一部分额外的事情，如进行类型的隐式转换，以兼容MySQL灵活的类型系统。
兼顾行列混合执行的优化器
有行存和列存两套执行引擎的存在，优化器在选择执行计划时有了更多的选择，其可以对比行存执行计划的Cost和列存执行计划的Cost，并使用代价最低的那个执行计划.
在PolarDB中除了有原生MySQL的行存串行执行，还有能够发挥多核计算能力的基于行存的Paralle Query功能。因此实际优化器会在1)行存串行执行，2）行存Paralle Query 3)IMCI 三个选项之中选择。在目前的迭代阶段，优化器按如下的流程操作：
1.执行SQL的Parse过程并生成LogicalPlan，然后调用MySQL原生优化器按照执行一定优化操作，如join order调整等。同时该阶段获得的逻辑执行计划会转给IMCI的执行计划编译模块,尝试生成一个列存的执行计划(此处可能会被白名单拦截并fallback回行存）。
2.PolarDB的Optimizer会根据行存的Plan,计算得出一个面向行存的执行Cost。如果此Cost超过一定阈值，则会尝试下推到IMCI执行器使用IMCI_Plan进行执行。
3.如果IMCI无法执行此SQL，则PolarDB会尝试编译出一个Parallel Query的执行计划并执行。如果无法生成PQ的执行计划，则说明IMCI和PQ均无法支持此SQL，fallback回行存执行。
上述策略是基于这样一个判断，从执行性能对比，行存串行执行 < 行存并行执行 < IMCI。从SQL兼容性上看，IMCI < 行存并行执行 < 行存串行执行。但是实际情况会更复杂，例如某些情况下，基于行存有序索引覆盖的并行Index Join会比基于列存的Sort Merge join有更低的Cost. 目前的策略下可能就选择了IMCI 列存执行。
2、面向列式存储的执行引擎
IMCI执行引擎是一套面向列存优化,并完全独立于现有MySQL行式执行器的一个实现，重写执行器的目的是为了消除现有行存执行引擎在执行分析型SQL时效率低两个关键瓶颈点：按行访问导致的虚函数访问开销以及无法并行执行。
支持BATCH并行的算子
IMCI执行器引擎使用经典的火山模型，但是借助了列存存储以及向量执行来提升执行性能。
火山模型里，SQL生成的语法树所对应的关系代数中，每一种操作会抽象为一个 Operator，执行引擎会将整个 SQL 构建成一个 Operator 树，查询树自顶向下的调用Next()接口，数据则自底向上的被拉取处理。该方法的优点是其计算模型简单直接，通过把不同物理算子抽象成一个个迭代器。每一个算子只关心自己内部的逻辑即可，让各个算子之间的耦合性降低，从而比较容易写出一个逻辑正确的执行引擎。
- 在IMCI的执行引擎中，每个Operator也使用迭代器函数来访问数据，但不同的是每次调用迭代器会返回一批的数据，而不是一行，可以认为这是一个支持batch处理的火山模型。
- 串行执行受制于单核计算效率，访存延时，IO延迟等限制，执行能力有限。而IMCI执行器在几个关键物理算子（Scan/Join/Agg等)上均支持并行执行。除物理算子需要支持并行外，IMCI的优化器需要支持生成并行执行计划，优化器在确定一个表的访问方式时，会根据需要访问的数据量来决定是否启用并行执行，如果确定启用并行执行，则会参考一系列状态数据决定并行度：包括当前系统可用的CPU/Memory/IO资源, 目前已经调度和在排队的任务信息, 统计信息, query 的复杂程度, 用户可配置的参数等。根据这些数据计算出一个推荐的DOP值给算子, 而一个算子内部会使用相同的DOP。同时DOP也支持用户使用Hint的方式进行设定。
向量化执行解决了单核执行效率的问题，而并行执行突破了单核的计算瓶颈。二者结合使得IMCI执行速度相比传统MySQL行式执行有了数量级的速度提升。
SIMD向量化计算加速
AP型场景，SQL中经常会包含很多涉及到一个或者多个值/运算符/函数组成的计算过程，这都是属于表达式计算的范畴。表达式的求值是一个计算密集型的任务，因此表达式的计算效率是影响整体性能的一个关键的因素。
传统MySQL的表达式计算体系以一行为一个单位的逐行运算，一般称其为迭代器模型实现。由于迭代器对整张表进行了抽象，整个表达式实现为一个树形结构，其实现代码易于理解，整个处理的过程非常清晰。
但这种抽象会同时带来性能上的损耗，因为在迭代器进行迭代的过程中，每一行数据的获取都会引发多层的函数调用，同时逐行地获取数据会带来过多的 I/O，对缓存也不友好。MySQL采用树形迭代器模型，是受到存储引擎访问方法的限制，这导致其很难对复杂的逻辑计算进行优化。
在列存格式下，由于每一列的数据都单独顺序存储，涉及到某一个特定列上的表达式计算过程都可以批量进行。对每一个计算表达式，其输入和输出都以Batch为单位，在Batch的处理模式下，计算过程可以使用SIMD指令进行加速。新表达式系统有两项关键优化：
- 充分利用列式存储的优势，使用分批处理的模型代替迭代器模型，我们使用SIMD指令重写了大部分常用数据类型的表达式内核实现，例如所有数字类型(int, decimal, double)的基本数学运算(+, -, *, /, abs)，全部都有对应的SIMD指令实现。在AVX512指令集的加持下, 单核运算性能获得会数倍的提升。
- 采用了与Postgres类似表达式实现方法：在SQL编译及优化阶段，IMCI的表达式以一个树形结构来存储(与现有行式迭代器模型的表现方法类似)，但是在执行之前会对该表达式树进行一个后序遍历，将其转换为一维数组来存储，在后续计算时只需要遍历该一维数组结构即可以完成运算。由于消除了树形迭代器模型中的递归过程，计算效率更高。同时该方法对计算过程提供简洁的抽象，将数据和计算过程分离，天然适合并行计算。
3、支持行列混合存储的存储引擎
事务型应用和分析型应用对存储引擎有着截然不同的要求，前者要求索引可以精确定位到每一行并支持高效的增删改，而后者则需要支持高效批量扫描处理，这两个场景对存储引擎的设计要求完全不同，有时甚至是矛盾的。
因此设计一个一体化的存储引擎能同时服务OLTP型和OLAP型负载非常具有挑战性。目前市场上HTAP存储引擎做的比较好的只有几家有几十年研发积累的大厂，如Oracle (In-Memory Column Store）/Sql Server(In Memory Column index）/DB2（BLU)等。如TiDB等只能通过将多副本集群中的一个副本调整为列存来支持HTAP需求。
一体化的HTAP存储引擎一般使用行列混合的存储方案，即引擎中同时存在行存和列存，行存服务于TP，列存服务于AP。相比于部署独立一套OLTP数据库 加一套OLAP数据库来满足业务需求，单一HTAP引擎具有如下的优势：
- 行存数据和列存数据具有实时一致性，能满足很多苛刻的业务需求，所有数据写入即可见于分析型查询。
- 更低的成本，用户可以非常方便的指定哪些列甚至一张表哪个范围的存储为列存格式用于分析。全量数据继续以行存存储。
- 管理运维方便，用户无需关注数据在两套系统之间同步及数据一致性问题。
PolarDB 采用了和Oracle/Sql Server等商用数据库类似的行列混合存储技术，我们称之为In-Memory Column Index：
- 建表时可以指定部分表或者列为列存格式，或者对已有的表可以使用Alter table语句为其增加列存属性，分析型查询会自动使用列存格式来进行查询加速。
- 列存数据默认压缩格式存储在磁盘上，并可以使用In-Memory Columbia Store Area来做缓存加速并加速查询，传统的行格式依然保存在BufferPool中供OLTP性负载使用。
- 所有事务的增删改操作都会实时反应到列存存储上，保证事务级别的数据一致性。
实现一个行列混合的存储引擎技术上非常困难，但是在InnoDB这样一个成熟的面向OLTP负载优化的存储引擎中增加列存支持，又面临不同的情况：
- 满足OLTP业务的需求是第一优先的，因此增加列存支持不能对TP性能太大影响。这要求我们维护列存必须足够轻量，必要时需要牺牲AP性能保TP性能。
- 列存的设计无需考虑事务并发对数据的修改, 数据的unique check等问题，这些问题在行存系统中已经被解决，而这些问题对ClickHouse等单独的列存引擎是非常难以处理的。
- 由于有一个久经考验的行存系统的存在，列存系统出现任何问题，都可以切换回行存系统响应查询请求。
上述条件可谓有利有弊，这也影响了对PolarDB整个行列混合存储的方案设计。
表现为Index的列存
在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和Seconary Index都实现为一个B+Tree。而列索引在定义上是一个Index，但其实是一个虚拟的索引，用于捕获对该索引覆盖列的增删改操作。
对于上面的表其主表(Primary Index）包含（C1,C2,C3,C4,C5) 5列数据, Seconary Index索引包含(C2,C1) 两列数据, 在普通二级索引中，C2与C1编码成一行保存在B+tree中。而其中的列存索引包含(C2,C3,C4)三列数据. 在实际物理存储时，会对三列进行拆分独立存储，每一列都会按写入顺序转成列存格式。
列存实现为二级索引的另一个好处是执行器的工程实现非常简单，在MySQL中已经存在覆盖索引的概念，即一个查询所需要的列都在一个二级索引中存储，则可以直接利用这个二级索引中的数据满足查询需求，使用二级索引相对于使用Primary Index可以极大减少读取的数据量进而提升查询性能。当一个查询所需要的列都被列索引覆盖时，借助列存的加速作用，可以数十倍甚至数百倍的提升查询性能。
列存数据组织
对ColumnIndex中每一列，其存储都使用了无序且追加写的格式，结合标记删除及后台异步compaction实现空间回收。其具体实现上有如下几个关键点：
- 列索引中记录按RowGroup进行组织，每个RowGroup中不同的列会各自打包形成DataPack。
- 每个RowGroup都采用追加写，分属每个列的DataPack也是采用追加写模式。对于一个列索引，只有个Active RowGroup负责接受新的写入。当该RowGroup写满之后即冻结，其包含的所有Datapack会转为压缩格保存到磁盘上，同时记录每个数据块的统计信息便于过滤。
- 列存RowGroup中每新写入一行都会分配一个RowID用作定位，属于一行的所有列都可以用该RowID计算定位，同时系统维护PK到RowID的映射索引，以支持后续的删除和修改操作。
- 更新操作采用标记删除的方式来支持，对于更新操作，首先根据RowID计算出其原始位置并设置删除标记，然后在ActiveRowGroup中写入新的数据版本。
- 当一个RowGroup中的无效记录超过一定阈值，则会触发后台异步compaction操作，其作用一方面是回收空间，另一方面可以让有效数据存储更加紧凑，提升分析型查询单的效率。
采用这种数据组织方式一方面满足了分析型查询按列进行批量扫描过滤的要求。另一方面对于TP型事务操作影响非常小，写入操作只需要按列追加写到内存即可，删除操作只需要设置一个删除标记位。而更新操作则是一个标记删除附加一个追加写。列存可以做到支持事务级别的更新同时，做到几乎不影响OLTP的性能。
全量及增量行转列
行转列操作在两种情况下会发生，第一种情况是使用DDL语句对部分列创建列索引(一般是业务对一个已有的表有新增分析型需求)，此时需要扫描全表数据以创建列索引。另一种情况是在事务操作过程中对于涉及到的列实时行专列。
对于全表行转列的情形，我们使用并行扫描的方式对InnoDB的Primary Key进行扫描，并依次将所有涉及到的列转换为列存形式，这一操作的速度非常快，其基本只受限于服务器可用的IO吞吐速度和可用CPU资源。该操作是一个online-DDL过程，不会阻塞在线业务的运行。
在一个表上建立列索引之后，所有的更新事务将会同步更新行存和列存数据，以保证二者的事务一致性。下图演示了在IMCI功能关闭和开启之间的差异性。在未开启IMCI功能时，事务对所有行的更新都会先加锁，然后再对数据页进行修改，在事务提交之前会对所有加锁的记录一次性方所。在开启IMCI功能之后，事务系统会创建一个列存更新缓存，在所有数据页被修改的同时，会记录所涉及到的列存的修改操作，在事务提交结束前，该更新缓存会应用到列存系统。
在此实现下，列存存储提供了与行存一样的事务隔离级别。对于每个写操作, RowGroup中的每一行都会记录修改该行的事务编号，而对于每个标记删除操作也会记录该设置动作的事务编号。借助写入事务号和删除事务号，AP型查询可以用非常轻量级的方式获得一个全局一致性的快照。
列索引粗糙索引
由前述列的存储格式可以看出, IMCI中所有的Datapack都采用无序且追加写的方式, 因此无法像InnoDB的普通有序索引那样的可以精准的过滤掉不符合要求的数据。在IMCI中，我们借助统计信息来进行数据块过滤，以此来达到降低数据访问单价的目的。
- 在每个Active Datapack终结写入的时候，会预先进行计算，并生成Datapack所包含数据的最小值/最大值/数值的总和/空值的个数/记录总条数等信息。所有这些信息会维护在DataPacks Meta元信息区域并常驻内存。由于冻结的Datapack中还会存在数据的删除操作，因此统计信息的更新维护会放到后台完成。
- 对于查询请求，会根据查询条件将Datapacks分为相关、不相关、可能相关三大类，从而减少实际的数据块访问。而对于一些聚合查询操作，如count/sum等，可以通过预先计算好的统计值进行简单的运算得出，这些数据块甚至都不需要进行解压。
采用基于统计信息的粗糙索引方案对于一些需要精准定位部分数据的查询并不是很友好。但是在一个行列混合存储引擎中，列索引只需要辅助加速那些会涉及到大量数据扫描的查询，在这个场景下使用列会具有显著的优势。而对于那些只会访问到少量数据的SQL，优化器通常会基于代价模型计算得出基于行存会得到一个成本更低的方案。
行列混合存储下的TP和AP资源隔离
PolarDB行列混合存储可以支持在一个实例中同时支持AP型查询和TP型查询。但很多业务有很高的OLTP型负载，而突发性的OLAP性负载可能干扰到TP型业务的响应时延。因此支持负载隔离在HTAP数据库中是一个必须支持的功能。借助PolarDB一写多读的架构，我们可以非常方便对AP型负载和TP型负载进行隔离。在PolarDB的技术架构下，我们有如下几个部署方式：
- 第一种方式，RW上开启行列混合存储，此种模式部署可以支持轻量级的AP查询，在主要为TP负载，且AP型请求比较少时可以采用。或者使用PolarDB进行报表查询，但是数据来自批量数据导入的场景。
- 第二种方式，RW支持OLTP型负载，并启动一个AP型RO开启行列混合存储以支持查询，此种部署模式下CPU资源可以实现100%隔离，同时该AP型RO节点上的内存可以100%分配给列存存储和执行器。但是由于使用的相同的共享存储，因此在IO上会相互产生一定影响，对于这个问题我们在未来会支持将列存数据写入到外部存储如OSS等，实现IO的资源隔离，同时提升AP型RO上的IO吞吐速率。
- 第三种方式，RW/RO支持OLTP型负载，在单独的Standby节点开启行列混合存储以支持AP型查询，由于standby是使用独立的共享存储集群，这种方案在第二种方案支持CPU和内存资源隔离的基础上，还可以实现IO资源的隔离。
除了上述部署架构上不同可以支持的资源局隔离之外。在PolarDB内部对于一些需要使用并行执行的大查询支持动态并行度调整(Auto DOP)，这个机制会综合考虑当前系统的负载以及可用的CPU和内存资源，对单个查询所用的资源进行限制，以避免单个查询消耗的资源太多，影响其他请求的处理。
五、PolarDB IMCI的OLAP性能
为了验证IMCI技术的效果， 我们对PolarDB MySQL IMCI的进行了TPC-H场景的测试。同时在相同的场景下将其与原生MySQL的行存执行引擎以及当前OLAP引擎单机性能最强的ClickHouse进行了对比。测试参数简要介绍如下:
- 数据量TPC-H 100GB, 22条Query
- CPU Intel(R) Xeon(R) CPU E5-2682 2 socket
- 内存 512G, 启动后数据都灌进内存。
1、PolarDB IMCI VS MySQL串行
在TPC-H场景下，所有22条Query ，IMCI处理延时相对比原生MySQL都有数十倍到数百倍不等的加速效果。其中Q6的的效果将近400倍。体现出了IMCI的巨大优势。
2、PolarDB IMCI VS ClickHouse
而在对比当前社区最火热的分析型数据库ClickHouse时, IMCI在TPC-H场景下的性能也与其基本在同一水平。部分SQL的处理延时各有优劣。用户完全可以使用IMCI替代ClickHouse使用，同时其数据管理也更加方便。
FutureWork
IMCI是PolarDB迈向数据分析市场的第一步，它迭代脚步不会停止，接下里我们会在如下几个方向进一步研究和探索，给客户带来更好的使用体验：
- 自动化的索引推荐系统，目前列存的创建和删除需要用户手动指定，这增加了DBA的工作量，目前我们正在研究引入自动化推荐技术，根据用户的SQL请求特征，自动创建列存索引，降低维护负担。
- 单独的列存表以及OSS存储，目前IMCI只是一个索引，对纯分析型场景，去除行存可以更进一步的降低存储大小，而IMCI执行器支持读写OSS对象存储能将存储成本降到最低。
- 行列混合执行，即一个SQl的执行计划部分片段在行存执行，部分片段在列存执行。以获得最大化的执行加速效果。
中国计算机学会 × 高德地图 发布“POI名称生成”赛题，诚邀全球英才组队参加
高德地图携手中国计算机学会发布“POI名称生成”赛题，内容新颖，与计算机视觉、NLP、多模融合等前沿技术相关，具有很大的技术价值和实际的社会应用价值。欢迎感兴趣的同学参加或推荐给朋友，让我们一起用技术让亿万用户的出行体验更美好。点击【中国计算机学会 × 高德地图 “POI名称生成”赛题】，查看详情！
