前言
最近分析型数据库在资本市场和技术社区都非常的火热，各种创业公司的创新型产品如雨后春笋般出现。这一方面是因为当前阶段企业日益依赖从数据中寻找增长潜力带来需求的增长，另一方面云原生技术的发展带来现有技术体系的进化和变革，诸如Snowflakes这类产品的成功证明，使用云原生技术再造分析型数据库技术体系是必要的且存在很大的市场机会。
PolarDBMySQL是因云而生的一个数据库系统,除了云上OLTP场景，大量客户也对PolarDB提出了实时数据分析的性能需求。对此PolarDB技术团队提出了In-MemoryColumnIndex(IMCI）的技术方案，在复杂分析查询场景获得的数百倍的加速效果。
本文阐述了IMCI背后技术路线的思考和具体方案的取舍。PolarDBMySQL列存分析功能即将在阿里云上线，敬请期待。
一MySQL生态HTAP数据库解决方案
MySQL是一款主要面向OLTP型场景设计的开源数据库，开源社区的研发方向侧重于加强其事务处理的能力，如提升单核性能/多核扩展性/增强集群能力以提升可用性等。在处理大数据量下复杂查询所需要的能力方面，如优化器处理子查询的能力，高性能算子HashJoin,SQL并行执行等，社区一直将其放在比较低优先级上，因此MySQL的数据分析能力提升进展缓慢。
随着MySQL发展为世界上最为流行的开源数据库系统，用户在其中存储了大量的数据，并且运行着关键的业务逻辑，对这些数据进行实时分析成为一个日益增长的需求。当单机MySQL不能满足需求时，用户寻求一个更好的解决方案。
1MySQL+专用AP数据库的搭积木方案
专用分析型数据库产品选项众多，一个可选方案是使用两套系统来分别满足的OLTP和OLAP型需求，在两套系统中间通过数据同步工具等进行数据的实时同步。更进一步，用户甚至可以增加一层proxy，自动将TP型负载路由到MySQL上，而将分析型负载路由到OLAP数据库上，对应用层屏蔽底层数据库的部署拓扑。
这样的架构有其灵活之处，例如对于TP数据库和AP数据库都可以各自选择最好的方案，而且实现了TP/AP负载的完全隔离。但是其缺点也是显而易见的。首先，在技术上需要维护两套不同技术体系的数据库系统，其次由于两套系统处理机制的差异，维护上下游的数据实时一致性也非常具有挑战。而且由于同步延迟的存在，下游AP系统存储的经常是过时的数据，导致无法满足实时分析的需求。
基于多副本的DivergentDesign方法
随着互联网而兴起的新兴数据库产品很多都兼容了MySQL协议，因此成为替代MySQL的一个可选项。而这些分布式数据库产品大部分采用了分布式ShareNothing的方案，其一个核心特点是使用分布式一致性协议来保障单个partition多副本之间的数据一致性。由于一份数据在多个副本之间上完全独立，因此在不同副本上使用不同格式进行存储，来服务不同的查询负载是一个易于实施的方案。典型的如TiDB，其从TiDB.0开始，在一个RaftGroup中的其中一个副本上，使用列式存储(TiFlash)来响应AP型负载,并通过TiDB的智能路由功能来自动选取数据来源。这样实现了一套数据库系统同时服务OLTP型负载和OLAP型负载。
该方法在诸多Research及Industry领域的工作中都被借鉴并使用，并日益成为分布式数据领域一体化HTAP的事实标准方案。但是应用这个方案的前提是用户需要迁移到对应的NewSQL数据库系统，而这往往带来各种兼容性适配问题。
一体化的行列混合存储方案
比多副本DivergentDesign方法更进一步的，是在同一个数据库实例中采用行列混合存储的方案，同时响应TP型和AP型负载。这是传统商用数据库Oracle/SQLServer/DB等不约而同采用的方案。
Oracle公司在在01年发表的Oracle1C上，发布了DatabaseIn-Memory套件，其最核心的功能即为In-MemoryColumnStore，通过提供行列混合存储/高级查询优化(物化表达式，JoinGroup)等技术提升OLAP性能。
微软在SQLServerSP1上，开始提供ColumnStoreIndexs功能，用户可以根据负载特征，灵活的使用纯行存表，纯列存表，行列混合表，列存表+行存索引等多种模式。
IBM在01年发布的10.5版本(Kepler)中，增加了DBBLUAcceleration组件，通过列式数据存储配合内存计算以及DataSkipping技术，大幅提升分析场景的性能。
三家领先的商用数据库厂商，均同时采用了行列混合存储结合内存计算的技术路线，这是有其底层技术逻辑的：列式存储由于有更好的IO效率(压缩,DataSkipping,列裁剪)以及CPU计算效率(CacheFriendly),因此要达到最极致的分析性能必须使用列式存储，而列式存储中索引稀疏导致的索引精准度问题决定它不可能成为TP场景的存储格式，如此行列混合存储成为一个必选方案。但在行列混合存储架构中，行存索引和列存索引在处理随机更新时存在性能鸿沟,必须借助DRAM的低读写延时来弥补列式存储更新效率低的问题。因此在低延时在线事务处理和高性能实时数据分析两大前提下，行列混合存储结合内存计算是唯一方案。
对比上述三种方法，从组合搭积木的方法到DivergentDesign方法再到一体化的行列混合存储，其集成度越来越高，用户的使用体验也越来越好。但是其对内核工程实现上的挑战也一个比一个大。基础软件的作用就是把复杂留给自己把简单留给用户，因此一体化的方法是符合技术发展趋势的。
二PolarDBMySQLAP能力的演进
PolarDBMySQL能力栈与开源MySQL类似，长于TP但AP能力较弱。由于PolarDB提供了最大单实例TB的存储能力，同时其事务处理能力远超用户自建MySQL。因此PolarDB用户倾向于在单实例上存储更多的数据，同时会在这些数据上运行一些复杂聚合查询。借助于PolarDB一写多读的架构，用户可以增加只读的RO节点以运行复杂只读查询，从而避免分析型查询对TP负载的干扰。
1MySQL的架构在AP场景的缺陷
MySQL的实现架构在执行复杂查询时性能差有多个方面的原因，对比专用的OLAP系统，其性能瓶颈体现多个方面：
MySQL的SQL执行引擎基于流式迭代器模型(VolcanoIterator)实现,这个架构在工程实现上依赖大量深层次的函数嵌套及虚函数调用，在处理海量数据时，这种架构会影响现代CPU流水线的pipline效率，导致CPUCache效率低下。同时Iterator执行模型也无法充分发挥现代CPU提供的SIMD指令来做执行加速。执行引擎只能串行执行，无法发挥现代多核CPU的并行话能力。官方从MySQL8.0开始，在一些count(*)等基本查询上增加并行执行的能力，但是复杂SQL的并行执行能力构建依然任重道远。MySQL最常用的存储引擎都是按行存储，在按列进行海量数据分析时，按行从磁盘读取数据存在非常大的IO带宽浪费。其次行式存储格式在处理大量数据时大量拷贝不必要的列数据，对内存读写效率也存在冲击。
PolarDB并行查询突破CPU瓶颈
PolarDB团队开发的并行查询框架（ParallelQuery),可以在当查询数据量到达一定阈值时，自动启动并行执行，在存储层将数据分片到不同的线程上，多个线程并行计算，将结果流水线汇总到总线程，最后总线程做些简单归并返回给用户，提高查询效率。
并行查询的加入使得PolarDB突破了单核执行性能的限制，利用多核CPU的并行处理能力，在PolarDB上部分SQL查询耗时成指数级下降。
WhyWeNeedColumn-Store
并行执行框架突破了CPU扩展能力的限制，带来了显著的性能提升。然而受限于行式存储及行式执行器的效率限制，单核执行性能存在天花板，其峰值性能依然与专用的OLAP系统存在差距。要更进一步的提升PolarDBMySQL的分析性能，我们需要引入列式存储：
在分析场景经常需要访问某个列的大量记录，而列存按列拆分存储的方式会避免读取不需要的列。其次列存由于把相同属性的列连续保存，其压缩效率也远超行存，通常可以达到10倍以上。最后列存中大块存储的结构，结合MIN/MAX等粗糙索引信息可以实现大范围的数据过滤。所有这些行为都极大的提升了IO的效率。在现今存储计算分离的架构下，减少通过网络读取的数据量可以对查询处理的响应时间带来立竿见影的提升。列式存储同样能提高CPU在处理数据时的执行效率，首先列存的紧凑排列方式可提升CPU访问内存效率，减少L1/LCachemiss导致的执行停顿。其次在列式存储上可以使用应用SIMD技术进一步提升单核吞吐能力，而这是现代高性能分析执行引擎的通用技术路线（Oracle/SQLServer/ClickHouse).
三PolarDBIn-MemoryColumnIndex
PolarDBIn-MemoryColumnIndex功能为PolarDB带来列式存储以及内存计算能力，让用户可以在一套PolarDB数据库上同时运行TP和AP型混合负载，在保证现有PolarDB优异的OLTP性能的同时，大幅提升PolarDB在大数据量上运行复杂查询的性能。
In-MemoryColumnIndex使用行列混合存储技术，同时结合了PolarDB基于共享存储一写多读的架构特征，其包含如下几个关键的技术创新点：
在PolarDB的存储引擎（InnoDB)上新增对列式索引（ColumnarIndex）的支持，用户可以选择通过DDL将一张表的全部列或者部分列创建为列索引，列索引采用列压缩存储，其存储空间消耗会远小于行存格式。默认列索引会全部常驻内存以实现最大化分析性能，但是当内存不够时也支持将其持久化到共享存储上。在PolarDB的SQL执行器层，我们重写了一套面向列存的执行器引擎框架(Column-oriented),该执行器框架充分利用列式存储的优势，如以行的一个Batch为单位访问存储层的数据，使用SIMD指令提升CPU单核心处理数据的吞吐，所有关键算子均支持并行执行。在列式存储上，新的执行器对比MySQL原有的行存执行器性有几个数量级的性能提升。支持行列混合执行的优化器框架，该优化器框架会根据下发的SQL是否能在列索引上执行覆盖查询，并且其所依赖的的函数及算子能被列式执行器所支持来决定是否启动列式执行。优化器会同时对行存执行计划和列存执行计划做代价估算，并选中代价交代的执行计划。用户可以使用PolarDB集群中的一个RO节点作为分析型节点，在该RO节点上配置生成列存索引，复杂查询运行在列存索引上并使用所有可用CPU的计算能力，在获得最大执行性能的同时不影响该集群上的TP型负载的可用内存和CPU资源。
几个关键关键技术结合使得PolarDB成为了一个真正的HTAP数据库系统，其在大数据量上运行复杂查询的性能可以与Oracle/SQLServer等业界最顶尖的商用数据库系统处在同一水平。
四In-MemoryColumnIndex的技术架构
1行列混合的优化器
PolarDB原生有一套面向行存的优化器组件，在引擎层增加对列存功能支持之后，此部分需要进行功能增强，优化器需要能够判断一个查询应该被调度到行存执行还是列存执行。我们通过一套白名单机制和执行代价计算框架来完成此项任务。系统保证对支持的SQL进行性加速，同时兼容运行不支持的SQL.
如何实现%的MySQL兼容性
我们通过一套白名单机制来实现兼容性目标。使用白名单机制是基于如下几点考量。第一点考虑到系统可用资源（主要是内存）的限制，一般不会在所有的表的所有上都创建列索引，当一个查询语句需要使用到列不在列存中存在时，其不能在列存上执行。第二点，基于性能的的考量，我们完全重写了一套面向列存的SQL执行引擎，包括其中所有的物理执行算子和表达式计算，其所覆盖的场景相对MySQL原生行存能够支持的范围有欠缺。当下发的SQL中包含一些IMCI执行引擎不能支持的算子片段或者列类型时，需要能能够识别拦截并切换回行存执行。
查询计划转换
Plan转换的目的是将MySQL的原生逻辑执行计划表示方式AST转换为IMCI的LogicalPlan。在生成IMCI的LogicalPlan之后，会经过一轮Optimize过程，生成PhysicalPlan。Plan转换的方法简单直接，只需要遍历这个执行计划树，将mysql优化后的AST转换成IMCI以relationoperator位节点的树状结构即可，是一个比较直接的翻译过程。不过在这个过程中，也会做一部分额外的事情，如进行类型的隐式转换，以兼容MySQL灵活的类型系统。
兼顾行列混合执行的优化器
有行存和列存两套执行引擎的存在，优化器在选择执行计划时有了更多的选择，其可以对比行存执行计划的Cost和列存执行计划的Cost，并使用代价最低的那个执行计划.
在PolarDB中除了有原生MySQL的行存串行执行，还有能够发挥多核计算能力的基于行存的ParalleQuery功能。因此实际优化器会在1)行存串行执行，）行存ParalleQuery)IMCI三个选项之中选择。在目前的迭代阶段，优化器按如下的流程操作：
1.执行SQL的Parse过程并生成LogicalPlan，然后调用MySQL原生优化器按照执行一定优化操作，如joinorder调整等。同时该阶段获得的逻辑执行计划会转给IMCI的执行计划编译模块,尝试生成一个列存的执行计划(此处可能会被白名单拦截并fallback回行存）。
.PolarDB的Optimizer会根据行存的Plan,计算得出一个面向行存的执行Cost。如果此Cost超过一定阈值，则会尝试下推到IMCI执行器使用IMCI_Plan进行执行。
.如果IMCI无法执行此SQL，则PolarDB会尝试编译出一个ParallelQuery的执行计划并执行。如果无法生成PQ的执行计划，则说明IMCI和PQ均无法支持此SQL，fallback回行存执行。
上述策略是基于这样一个判断，从执行性能对比，行存串行执行行存并行执行IMCI。从SQL兼容性上看，IMCI行存并行执行行存串行执行。但是实际情况会更复杂，例如某些情况下，基于行存有序索引覆盖的并行IndexJoin会比基于列存的SortMergejoin有更低的Cost.目前的策略下可能就选择了IMCI列存执行。
面向列式存储的执行引擎
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指令实现。在AVX51指令集的加持下,单核运算性能获得会数倍的提升。
采用了与Postgres类似表达式实现方法：在SQL编译及优化阶段，IMCI的表达式以一个树形结构来存储(与现有行式迭代器模型的表现方法类似)，但是在执行之前会对该表达式树进行一个后序遍历，将其转换为一维数组来存储，在后续计算时只需要遍历该一维数组结构即可以完成运算。由于消除了树形迭代器模型中的递归过程，计算效率更高。同时该方法对计算过程提供简洁的抽象，将数据和计算过程分离，天然适合并行计算。
支持行列混合存储的存储引擎
事务型应用和分析型应用对存储引擎有着截然不同的要求，前者要求索引可以精确定位到每一行并支持高效的增删改，而后者则需要支持高效批量扫描处理，这两个场景对存储引擎的设计要求完全不同，有时甚至是矛盾的。
因此设计一个一体化的存储引擎能同时服务OLTP型和OLAP型负载非常具有挑战性。目前市场上HTAP存储引擎做的比较好的只有几家有几十年研发积累的大厂，如Oracle(In-MemoryColumnStore）/SqlServer(InMemoryColumnindex）/DB（BLU)等。如TiDB等只能通过将多副本集群中的一个副本调整为列存来支持HTAP需求。
一体化的HTAP存储引擎一般使用行列混合的存储方案，即引擎中同时存在行存和列存，行存服务于TP，列存服务于AP。相比于部署独立一套OLTP数据库加一套OLAP数据库来满足业务需求，单一HTAP引擎具有如下的优势：
行存数据和列存数据具有实时一致性，能满足很多苛刻的业务需求，所有数据写入即可见于分析型查询。
更低的成本，用户可以非常方便的指定哪些列甚至一张表哪个范围的存储为列存格式用于分析。全量数据继续以行存存储。
管理运维方便，用户无需