列存索引行列融合基础组件介绍

背景信息

事务处理（OLTP）和分析处理（OLAP）混合工作负载在当前的业务系统中变得越来越常见。由于有实时、易运维等需求，一些业务系统会采用HTAP数据库来代替原有的OLTP-ETL-OLAP架构。HTAP数据库可以在一套数据库系统中同时较为高效地处理TP请求和AP请求。然而，由于TP请求和AP请求的访问模式截然不同，高效处理这两种请求依赖于不同的存储格式和计算模式。因此，HTAP数据库需要存储两种不同格式的数据，并在处理不同的请求时选择不同的模式对相应数据进行计算。

云原生数据库PolarDB采用了上图中的方式来处理混合型的工作负载。开启列存索引（In-Memory Column Index，以下简称IMCI）功能后，只读节点（RO）会额外维护一份列式索引，并在处理AP请求时采用向量化的方式对列式数据进行计算（列式计算）。而在处理TP请求时依然采用MySQL原有的one-tuple-at-a-time的方式对行式索引的InnoDB数据进行计算（行式计算）。列式索引和行式索引都通过物理复制链路回放读写节点（RW）的写入。在这套系统中，处理两种请求的存储、执行器、优化器都彼此独立，TP请求和AP请求在执行路径上完全分离，一条SQL语句要么选择列式计算，要么选择行式计算。

长尾请求问题

从用户的工作负载中可以看到，对于混合负载中的大部分请求，“行列分离”的计算方式已经能够以最优的计划执行。然而，对于少部分请求，列式计算和行式计算都不是最优的，具体体现在以下几个方面：

1. 在查询大宽表时，若对少数列通过WHERE或JOIN条件进行过滤，或查询TOP K，最后输出筛选出来的行的所有详细信息。对于这类查询，使用列存索引进行查询的效果较好。但在使用列存索引查询筛选出的列的详细信息时，project需要获取所有的列信息，列存索引在获取所有的列信息时存在读放大问题。这种情况下，通过行式索引来查询详细信息效果较好。

2. 执行计划的一个片段是两张大表join（t1 join t2），t1表上WHERE条件的过滤比例很高，且有InnoDB索引。t2表上的join条件没有InnoDB索引且join条件只涉及少数列。在这样的查询中，通过行式计算和InnoDB索引查询t1表，再通过列式计算扫描t2表进行hash join效果较好。

3. 以2中的场景为例，t2表上的join条件有InnoDB索引，此时t1 join t2这个执行片段通过纯行式计算进行index join效果较好。执行计划的其余片段可能通过列式计算的方式执行。

为了更高效地处理混合负载中的这部分长尾请求，在IMCI的优化器和执行器中，基于两个不同的索引，设计并实现了“行列融合”执行架构。

主要挑战

在一个“行列分离”的系统中实现“行列融合”，主要的挑战来自以下几个方面：

1. 优化器代价估计：MySQL优化器和IMCI优化器的代价模型不同，如果直接以MySQL的代价模型计算行式执行片段的代价，再加上以IMCI的代价模型计算列式执行片段的代价，并不能得到整个执行计划的代价。需要设置统一的CPU和IO代价单位，再根据行列计算的不同算法复杂度和行列索引不同的统计信息计算出最终的代价。

2. 执行器访问不同索引：一套执行器需要同时访问InnoDB和列式索引。MySQL执行器是以单线程的模式执行一个SQL请求，也是使用单线程访问InnoDB相关的接口和上下文。而IMCI执行器是以单leader+多worker的模式处理一个SQL请求。那么如果在worker中访问InnoDB就需要一些额外的处理。

3. 行列索引实现强一致读：列式索引和InnoDB回放RW写入的过程是异步的，两个不同索引的回放redo log的位点可能不一致。并且InnoDB通过基于LSN的read view判断数据可见性，而列式索引通过类似LSM存储引擎的sequence判断数据可见性。在异步回放下，行列索引只能实现最终一致读，而“行列融合”的行式执行片段和列式执行片段的可见数据不一致会导致执行结果错误。

行列融合基础组件

优化器的代价模型

长尾请求问题中的三种类型在“行列分离”的执行架构下会基于代价被视为AP请求由IMCI执行。因此，选择基于IMCI的优化器并引入对行式执行片段的代价估计，从而使这些长尾请求能够选择“行列融合”执行计划。

在引入行式执行代价估计的过程中，需要遵循如下原则：

1. 对于一个执行片段，相对高估其使用行式执行的代价，低估其使用列式执行的代价。因为长尾请求原本会选择纯列式执行，这样的代价估计可以保证当一个长尾请求选择“行列融合”的执行计划时，一定不会比原本的执行计划更差。

2. 只参考MySQL优化器的代价常量之间的比例。MySQL优化器的代价常量如上图所示，和IMCI的代价常量具有不同的数量级，因此无法直接使用它们的绝对值，但可以参考它们之间的比例关系。

基于上述原则，IMCI采用如下设计：

1. 在IMCI优化器中，InnoDB的io_block_read_cost和列式索引的pack io cost相同。虽然InnoDB一个page是16 KB，而列式索引的pack是65536行，比16 KB更大，但基于第一个原则，且考虑PolarFS并发下发请求和条带打散粒度，故设置相同的IO代价常量。

2. 基于第二个原则，memory_block_read_cost和row_evaluate_cost保持相同的比例。

根据上述的代价常量，基于MySQL和IMCI各自的算法和统计信息计算出“行列融合”执行计划的代价。

执行器的多引擎访问

IMCI优化器对长尾请求选择“行列融合”执行计划后，通过在IMCI执行器中引入新的Hybrid算子来计算行式执行片段。

新的Hybrid算子需要在IMCI执行器中访问InnoDB，参考MySQL的Server层的实现原理，通过TABLE对象中的handler来和存储引擎交互。从上图的执行流程可以看出，虽然Prepare阶段已经Open Table，但相关对象和接口都是面向MySQL单线程执行实现的，因此在IMCI执行器的worker中，需要再次Open Table，并克隆或引用相关对象。

存储引擎的日志回放和事务处理

两个不同索引异步回放的流程如上图橙色部分所示，其中InnoDB在回放完成后会更新latest read view，而列式索引在回放完成后会更新列式索引的last commit seq。回放流程在接收一定量的redo后运行一次（包含若干条redo log entry），redo内InnoDB事务和IMCI事务的提交情况一致。因此，一段redo在两个不同索引上都回放完成后，基于更新的latest read view和last commit seq，两个不同索引上的数据可见性保持一致，上述read view和commit seq称之为“对应的”。如果查询使用“对应的”read view和commit seq来判断数据可见性，就能实现强一致读。

然而，行列索引的回放流程是异步的，由于回放速度的差异，任意时刻latest read view和last commit seq可能不是“对应的”，这种情况下需要找到最近更新的“对应的”read view和commit seq。为此，在异步回放流程中引入上图中的蓝色部分，流程如下：

1. 对于一段redo，InnoDB在更新latest read view后，会在列式索引的Log Queue中添加一个包含当前latest read view的dummy日志对象。

2. 列式索引单线程顺序处理Log Queue，先推送常规日志对象到回放模块，并计算该次回放完成后更新的commit seq。接下来处理dummy日志对象，将该commit seq设置到对应的read view上。

   说明

   由于在处理dummy日志对象时，之前的常规日志对象可能还没全部完成回放，因此设置到read view上的commit seq在列式索引上可能尚未生效，回放完成后，这个“对应的”read view和commit seq才可以被使用。

引入该流程后，“行列融合”查询会在尚未被purge的read view中，寻找一个“对应的”commit seq已经生效的read view来判断数据的可见性。

HybridIndexSearch

基于行列融合基础组件，引入了HybridIndexSearch来处理第一种长尾请求问题。HybridIndexSearch通过primary key从InnoDB的主索引获取完整的行，进行相关表达式的计算后输出。除了基础组件提供的能力外，HybridIndexSearch需要执行计划中它的子算子输出primary key数据，可以通过优化器搜索执行计划时，设置primary key的property来实现。

性能测试

该测试基于ClickHouse官方提供的OnTime数据集来验证“行列融合”执行架构和HybridIndexSearch算子的性能。

OnTime数据集中的表包含110列，是一个典型的大宽表。通过如下SQL语句模拟第一种类型的长尾请求：

SELECT * FROM ontime ORDER BY ArrTime LIMIT 1000;

三种执行计划均为冷启动查询，执行时间如下，单位为秒。

由测试结果可以看出，对于混合型工作负载中的长尾请求，通过“行列融合”执行架构和Hybrid算子两种方式可以实现最优的性能，相对于纯列式执行或纯行式执行时间都有数量级的提升。