数据密集型应用的兴起推动了混合事务分析处理（HTAP）的发展。为了支持混合工作负载，分布式HTAP数据库通常会维护两个数据副本，分别针对数据时效性和性能隔离进行专门优化。具体来说，面向行格式的数据副本适合在线事务处理（OLTP）工作负载，而面向列格式的数据副本则针对在线分析处理（OLAP）工作负载进行了优化。这种混合设计为查询优化开辟了新的设计空间：查询计划可以在不同的数据格式上进行优化，并在隔离的资源上执行，也将其称为混合计划。现阶段传统的优化器可能无法在实时更新的HTAP数据库上精确地对混合计划的执行进行建模和调度。因此，文章提出了METIS，一种支持HTAP的优化器。文章从理论和实验两方面表明，METIS系统可以在很大程度上从混合计划中受益，同时保持OLTP和OLAP的性能隔离，并且这些优化对工作负载的变化具有鲁棒性。

1. 研究背景与动机

1.1 现代HTAP系统的兴起

如今，数据密集型应用通常利用大量数据来完成各种实时业务任务，这就需要将分析和事务处理技术结合起来。为此，许多学术界和企业界的工作都致力于开发混合事务分析处理（HTAP）系统，期望这些系统能够对新鲜数据进行快速分析，并隔离交错工作负载的性能。

一个实用的HTAP数据库通常由一个支持高吞吐量事务处理的在线事务处理（OLTP）引擎和一个支持低延迟分析的在线分析处理（OLAP）引擎组成。为了高效处理混合工作负载，一类流行的分布式HTAP数据库（例如，SQL Server、TiDB、ByteHTAP等）通常采用两个带有专门数据存储的引擎，并将数据从一个副本异步复制到另一个副本，以实现上述两个目标。

现有流行的分布式HTAP系统混合物理布局的示例

如图a中，面向行的存储（简称行存储）将数据按行存储，针对一次操作单个数据元组和访问多个属性进行了优化，适合OLTP；面向列的存储（简称列存储）将不同行的相同属性连续存储在列中，针对一次访问大量行和部分元组属性进行了优化，适合OLAP。为了在新数据上提供快速的OLAP功能，更新会从行存储异步复制到列存储，同时对OLTP的影响最小。同时，利用混合物理布局，METIS在HTAP的性能、隔离性和时效性之间取得了实际的平衡。

但是，将每个工作负载限制在其专门的存储上，使得很多性能潜力未能实现。对于只读查询，根据系统实现和工作负载的特点，行存储和列存储的性能可能会有很大差异。因此，可能存在一些查询，对于它们来说，无论是列存储还是行存储都不是最优的。

为了充分发挥混合物理布局的潜力，一些HTAP系统在其查询优化器中集成了两种存储，作为可选的数据访问方法，为查询生成混合计划。具体来说，混合计划允许单个查询同时从行存储和列存储中检索数据，并基于一致的数据视图计算查询结果。

1.2 现有HTAP系统的局限性

现有方法仅基于查询的选择性选择访问路径并进行查询优化，忽略了 HTAP数据库的数据动态性。盲目追求混合计划很容易使生成的计划次优，并损害两个重要属性：数据时效性和性能隔离。

这两个属性至关重要，因为高数据时效性能以生成速度为用户提供对新鲜数据的智能洞察，这使HTAP数据库区别于传统的提取-转换-加载（ETL）方法。

HTAP中的性能隔离是指在另一个工作负载增加时，仍能保持OLTP和OLAP工作负载性能的能力，这对于提供单独的服务级别协议（SLA）非常重要。

为了保持混合计划的高效性，本文应该在查询优化器的设计中考虑数据动态性，捕捉读操作（即只读查询）和写操作（即写事务）之间的相互关系。在本文中，数据动态性定义为OLTP引擎持续执行用户的写事务，并将行存储中的新数据增量应用到列存储中的特性。基于这一见解，作者确定了三个关键挑战：

挑战1：当新的写操作不断更新用于读取的复制数据副本时，如何精确地对数据访问路径的成本进行建模？

分布式HTAP数据库通常通过单独的增量存储来支持对读优化的列存储（即用于读取的数据副本）进行及时更新。增量存储不断累积更新，并定期将其合并到列存储中。这种架构使得传统的成本模型在评估数据访问路径成本时不够精确：访问路径选择没有固定的选择性阈值；相反，选择取决于工作负载的动态性（即写操作的并发性）。

为了应对这一挑战，作者提出了一种新的增量存储的成本模型Demain，将数据动态性纳入优化器。Demain捕捉了增量存储和列存储中选择操作符的性能，从而可以有效地指导访问路径的选择。

挑战2：如何同时优化数据时效性和执行时间，特别是当新的写操作是异步传播的时候？

通常，在使用异步复制数据副本的HTAP数据库中，优化执行时间可能会以牺牲数据时效性为代价。这是因为，由于数据复制，列存储中新写操作的可见性总是存在延迟。因此，即使列存储在顺序扫描上的性能可能优于行存储（即用于写操作的数据副本），但在新写操作完全同步到列存储之前，执行必须被阻塞，从而导致响应时间变长。

在查询优化中考虑可见性延迟是一个重要的研究问题，因为尽管现有的多项工作都在努力从系统层面最小化行存储和列存储之间的可见性延迟，但根据部署情况，可见性延迟仍然很明显。

针对这一挑战，本文提出了一种新的可见性的计划选择算法。它首先根据正在进行的和预测的工作负载特征估计行存储和列存储之间的可见性延迟。在优化查询时，它通过在可用数据上预执行计划来提高查询性能，从而掩盖了明显的可见性延迟。

挑战3：当查询计划是混合计划时，如何确保读操作和写操作之间的性能隔离？

一种简单的方法是为行存储中的读操作（即用于写操作的数据副本）设置预定义的配额。然而，手动干预无法在降低查询延迟的同时有效地利用资源。一种适用于一种工作负载的配置不太可能适用于另一种工作负载。

在此问题下，作者为混合计划开发了一种新的资源的查询重新优化方法。与调度资源或限制资源使用不同，重新优化方法可以自动适应工作负载的变化。当检测到高资源争用时，它会通过机会性地将先前优化计划中的高效子计划组合成一个新的良好计划来重新优化计划，这样可以在不进行整个计划重新优化的情况下缓解资源争用。

1.3 提出METIS的动机

本文将所有这些新的优化技术（即增量存储的成本模型、可见性的计划选择和资源的查询重新优化）整合到METIS中，这是一种支持HTAP的计划优化器。METIS是基于METISDB开发的。

总体而言，METIS捕捉数据动态性以保持混合计划的高效性。METIS通过将数据时效性和性能隔离作为新的设计目标，扩展了传统优化器的设计空间。METIS可以在不牺牲时效性和性能隔离的情况下加速分析查询。

2. 背景和动机

2.1 HTAP中的混合数据格式

本文总结了流行的分布式HTAP系统（包括METISDB）的常见设计，并将它们的共同点提炼为一个抽象系统模型，该模型概述了高级优化原则（即增量存储的成本模型、可见性的计划选择和资源的计划重新优化）的适用范围。因此，METISDB是这类最先进的HTAP数据库之一，将METIS作为一个具体实例，展示如何将支持HTAP的优化原则应用于METISDB。系统模型构造如下：

1. 行存储：系统有一个行存储，它连续存储每个数据元组的所有属性。所有写事务都由行存储处理。每个写事务会在行存储中生成一个新的数据版本，每个数据版本都标记有一个单调递增的时间戳。

2. 索引：在行存储上构建索引以加速写操作和点查找。在对索引列进行查询时，索引可以按排序顺序提供结果。本文不考虑列存储上的索引，因为这会给实时更新带来额外的开销和复杂性。

3. 列存储：系统有一个采用分解存储模型的列存储。它将不同行的相同属性组合在一起并连续存储。列存储支持对未压缩数据进行快速顺序扫描。

4. 增量存储：系统有一个增量存储，可以高效地吸收带时间戳的更新。增量存储是写优化的，并定期将吸收的更新合并到列存储中。同时，增量存储支持多版本并发控制。在进行面向列的扫描时，查询首先从增量存储中检索新鲜数据，并将其与列存储的结果相结合，以生成一个新鲜的数据视图。

5. 数据同步：系统有一个数据传输管道，用于将更新从行存储异步传输到列存储，并且同步操作不在事务处理的关键路径上。列存储可能会滞后，而行存储永远不会出现回退。

其中，增量存储和异步复制对分布式HTAP数据库有以下两个好处：

1. 增量存储：由于列存储是针对按列读取进行高度读优化的，因此需要一个写优化的增量存储（用于按行写入）来使列存储与行存储保持同步。否则，由于写效率的差距，列存储可能会任意滞后，导致数据时效性差；此外，由于数据同步线程（即用于写入新数据的线程）和OLAP线程（即用于处理查询的线程）会同时读写增量存储，通常会使用多版本并发控制（MVCC）来通过维护多个快照解决读写操作之间的冲突。

2. 异步复制：HTAP数据库的另一个重要属性是性能隔离。在实际工作负载中，OLTP通常是关键任务，对性能敏感。为了最小化数据复制对事务的负面影响，广泛采用异步复制，它允许正在进行的事务在这些事务的数据同步完成之前提交。

2.2 混合计划的动机

混合计划实验效果

作者通过实验说明混合计划的动机，并展示混合计划生效的实际场景，如图在两个经过充分研究的基准测试上进行了实验：CH-benCHmark和TPC-DS。通过比较混合计划与行存储和列存储计划中较快者的执行时间，评估结果表明，对于许多给定的查询，无论是行存储计划还是列存储计划都不是最优的。在CH-benCHmark中，22 个查询里有9个从混合计划中受益，几何平均加速比达到1.68倍；在TPC-DS中，99个查询里有77个（即77.8%）从混合计划中受益，加速比达到3.06倍。

基于实验，本文总结了促使混合计划具有吸引力的三个因素：

1. 单个查询内部数据访问模式的多样性：当一个查询连接多个表时，每个表上数据大小和查询选择性的差异，促使对不同的表使用不同的访问路径。

2. 数据模式的划分：星型模式和雪花模式作为两种成功的数据模型，在维度表和事实表之间有明确的划分，维度表最有可能通过主键与事实表连接。在HTAP数据库中使用这些模式时，从行存储（通过主键索引）检索维度表数据，从列存储检索事实表数据，可能是最优计划的有力候选方案。

3. 查询对物理属性（如排序顺序）的要求：当查询对部分表有特定的属性要求时，无论是用户请求还是内部操作符的要求（例如排序合并连接需要有序数据），特定的存储（例如提供B+树索引）在这些表上就有机会表现得比其他存储更好，从而产生混合计划。

3. 与HTAP无关的混合计划存在的问题

3.1 数据同步的影响

在处理HTAP工作负载时，写事务会在行存储上不断生成新数据，并通过备用增量存储复制到列存储。因此，为了进行面向列的扫描，OLAP引擎总是需要结合增量存储中的新数据，以提供新鲜的数据视图。这样一来，检索数据的成本会增加，导致面向列的扫描出现读放大现象，进而影响访问路径的选择决策。

根据增量存储采用的具体策略，读放大的严重程度可能会有所不同。例如，数据库管理员可以为增量存储的大小设置严格的限制，当增量存储的大小超过限制时，立即执行增量合并操作。这样，读放大对面向列扫描的影响就可以得到限制。然而，当写工作负载较重时，这种方法必须阻塞写操作（也称为写停顿），而且增量合并的速度可能赶不上新的写操作。总而言之，从增量存储中检索数据会给列扫描带来额外开销，这对访问路径选择至关重要。

3.2 对数据时效性的影响

确保高数据时效性是实时HTAP数据库最重要的设计目标之一。一般来说，在HTAP中，行存储的数据时效性比列存储更好，因为所有数据都在行存储上生成，然后异步传播到列存储中。可见性延迟被定义为行存储上提交的更新，与使用面向列扫描的查询能够读取该更新之间的时间延迟。实验表明由于处理更多数据的开销，可见性延迟随着OLTP工作负载的并发性增加而增加（即正相关）。

从优化器的角度来看，查询可以通过直接在行存储上执行查询，或者阻塞查询执行，直到增量存储中的所有新数据都可见，来获得最佳的数据时效性。这就带来了一个两难问题：使用面向列的扫描来优化数据检索时间，可能会由于阻塞时间而导致响应延迟的负优化。即使访问路径选择的成本模型完全准确，这种情况也可能发生。

3.3 对性能隔离的影响

HTAP数据库的另一个重要属性是性能隔离。如果不使用混合计划，OLTP和OLAP工作负载中检索数据的操作由单独的存储处理。在这种情况下，数据库管理员可以使用资源管理工具（例如Cgroup）为每个存储和执行引擎分配硬件资源，或者跨机器部署存储，从而自然地提供隔离，以及OLTP和OLAP的独立可扩展性。

然而，当使用混合计划时，出现了以下两个问题：

1. OLTP的性能下降：实验表明当OLTP工作负载较轻（即少于256个OLTP线程）时，混合计划对OLTP吞吐量的影响很小。当行存储的负载接近饱和时，混合计划导致OLTP吞吐量下降。

2. 混合计划的低效率：在高竞争情况下，执行面向行扫描的混合计划必须等待调度，导致其性能低于预期。

4. METIS概述

METISDB概述

4.1 METIS概述

如图所示，METISDB采用无共享架构，计算和存储是分离的。在存储层，使用RocksDB的变体作为行存储，ClickHouse的变体作为列存储。METISDB支持使用存储内范围过滤器，不考虑其他计算下推。

行存储被划分为多个分片，并部署在多台机器上。每个分片通过逻辑日志异步复制到增量存储中。列存储与增量存储共置，并使用与行存储相同的分区策略。增量存储中的新数据将定期批量合并到列存储中。本文假设行存储和增量存储之间的网络是可靠的，每个新的更新最终都会被传递和处理。

同时，METISDB为OLTP事务和OLAP查询都提供快照隔离。为此，行存储和增量存储都支持多版本并发控制（MVCC）。新的数据元组会带着唯一的行ID和相关事务的提交时间戳，流式插入到增量存储中。

对于计算节点，有三个关键组件：

1. OLTP和OLAP引擎：是系统的入口点，它们是无状态的，包含优化器和执行器等模块。引擎负责分布式数据路由、并发控制和二级索引维护。OLTP和OLAP的缓存是独立管理的。

2. 全局元服务：它维护着系统中关于表、模式、统计信息和其他元数据的全局一致信息，还负责提供全局定时服务。因此，每个事务和查询都会通过获取一个唯一且单调递增的时间戳来启动，以获得全局一致的快照。另外的时间戳用于事务提交。

存储模型：METISDB的行存储和列存储分别以以下方式实现：

● 行存储是基于日志结构合并树（简称LSM树）实现的。具体来说，行存储中的每一行都存储为一个键值对，使用其表ID和行ID作为键，将所有属性（列）连续存储为值。在进行表扫描时，存储引擎会检索所有表ID与给定表相同的键值对。可以通过构建主键索引和二级索引，以加速在行存储上的查找性能。所有索引也都实现为键值对。

● 列存储并以数组（即向量或列块）的形式存在，通过一个柱状增量树支持及时更新，该增量树使用B+树索引组织一个只追加的增量存储，以高效定位更新。在进行列扫描时，存储引擎会从增量存储和稳定的列块中检索数据，然后合并结果输出。

4.2 METIS的工作流程和关键组件

METIS的工作流程

作者在METISDB的基础上开发了METIS，并将其整合到计算节点的优化器层。METIS的工作流程如图所示：

1. 在收到查询优化请求后，METIS首先基于成本模型和基数估计，对枚举的计划进行成本估算，特别是使用新的考虑增量存储的成本模型（Demain）来选择访问路径。

2. 然后，METIS会剔除那些远非最优的计划，并使用其可见性感知计划选择算法，形成一组种子计划。种子计划包括在仅使用行存储时成本最低的行存储计划、在仅使用列存储时成本最低的列存储计划，以及在同时考虑行存储和列存储时成本最低的支持 HTAP的混合计划。

3. 为了执行查询，METIS会从种子计划集中选择估计成本最低的计划开始执行，并持续监控查询性能。

4. 为了确保性能隔离，METIS会监控数据库的资源利用率。当计划未能达到其性能边界时，无论是由于违反性能隔离，还是由于中间子表达式的估计错误，METIS会通过重用种子计划中的子计划来拼接一个新计划。

5. 由于运行时统计信息提供了更准确的运行时测量，METIS可以纠正由资源争用或基数估计错误导致的负优化。最后，查询结果会返回给客户端。

设计原理：METIS通过考虑分布式HTAP数据库的主流架构，提高了传统成本模型的准确性，并通过考虑复制数据按顺序可见的数据同步机制，选择可见性感知计划METIS将计划优化和执行交织在一起，使优化器能够将计划选择推迟到运行时，这符合持续更新的HTAP数据库的数据动态性本质。同时，METIS可以通过重新优化生成的最优计划，确保OLTP和OLAP工作负载之间的性能隔离。

4.3 局限性和讨论

METIS有以下两个局限性：

1． 与其他基于成本模型的优化器一样，METIS依赖基数估计来预测结果集的大小，对于复杂查询，这可能并不准确。

2. METIS将列扫描建模为顺序扫描，并假设在计算之前所有数据都已解压。一些数据仓库通过直接处理压缩数据来提高OLAP性能。在考虑混合计划时，这具有挑战性。此外，在HTAP中，由于新数据不断生成，增量存储中的数据无法压缩。因此，针对增量存储的成本模型仍然是具有价值的。

5. Demain模型

5.1 模型预备知识

Demain预备知识和各参数

Demain各参数如表所示，从四个角度对HTAP中的访问路径进行建模：查询、数据集、硬件和存储。本文的成本模型以范围扫描为目标，范围扫描通常根据给定的预测条件筛选数据。比如以下一个SQL示例：

SELECT col1 FROM table WHERE col1 between ${a} and ${b}

在METISDB的行存储（即基于LSM树的键值存储）中处理范围查询时，除了请求的数据，还需要读取并丢弃“墓碑”（即记录已删除键的无效实例的元数据）和无效条目。由于失效元数据的大小对全表扫描的影响较小，因此忽略该成本。文章使用
来建模读放大，
是一个表示LSM树中插入条目的大小，相较于数据集中元组大小的放大倍数的因子。因此，
可以通过获取LSM树中条目的大小来计算，该大小由METISDB的全局元服务在运行时维护。

5.2 在HTAP中对访问路径进行建模

1. 网络 I/O 成本：通过考虑传输延迟和网络内延迟来对网络成本进行建模。

转发数据结果的总成本如下，公式的第一部分计算传输延迟，表示网络内延迟：

2. 行扫描：对于给定的表，在底层行存储中扫描数据是按顺序访问的。在存储节点上检索数据的成本包括三个部分：

● 首先，需要将数据从磁盘移动到内存。

● 其次，需要将数据从内存移动到CPU缓存以执行扫描。

● 第三，消耗CPU周期根据预测条件过滤数据。

由于所有这些步骤是以流水线方式进行的，总执行时间受这三个因素中的最大值限制。因此，行扫描的成本（以秒为单位）为：

3. 索引扫描：在访问列上有索引时，从索引中检索数据的成本有两部分：

●  首先，需要顺序遍历索引，以找到与请求值范围对应的一组行ID。

●  其次，存储引擎应根据提议的行ID集过滤行，而无需支付读取整个键值对的开销。

与行扫描类似，忽略内存和CPU的成本：

4. 列存储上的列扫描：为了在列存储上执行列扫描，METISDB直接从指定的单个列中检索数据，而不是读取整个元组。

5. 增量扫描：METISDB将B+树作为只追加增量存储的一部分，B+树的成本分为两部分：

● 第一部分用于遍历B+树的内部结构，以找到与请求值范围对应的第一个叶节点的起始点。

 ● 第二部分用于遍历叶节点以读取索引行ID，并根据行ID找到元组。

6. HTAP中的列扫描：HTAP中列扫描的总成本为： 

检索数据的总成本还应结合从存储节点传输数据到计算节点的网络 I/O成本，这对于估计执行延迟至关重要。然而，该成本对于访问路径选择并不关键，因为存储节点会根据预测条件在本地过滤数据，因此不同访问路径传输结果的大小应该是相同的。

5.3 访问路径选择

通过上述公式详细比较行扫描、列存储上的列扫描和索引扫描。可以发现：对于基于磁盘的数据库，列存储的主要优势在于帮助降低I/O成本（即每个元组的成本从降低到）。当表有大量列且请求的列数较少时，这种优势尤为明显。行存储的读取性能可以得到提升，因为索引可以帮助跳过不必要的元组访问，只读取与请求值范围对应的整个元组。当查询选择性较低时，索引扫描的总成本应该更低。但是，当查询选择度特别大时，索引扫描的性能可能比行扫描更差，因为它们在顺序索引遍历上需要额外的开销，并且数据遍历是随机的。

于是，对于METIS中的访问路径选择如下：根据本文的模型，当查询的选择度特别大，METIS更倾向于行扫描。当特别小时，METIS更倾向于索引扫描。否则，METIS选择列扫描。

6. 运行时优化

6.1 可见性的计划选择

给定上述的成本模型，在进行计划枚举时，METIS将每个物理计划表示为一个有向无环图（DAG），该图为计划执行构建了一个偏序。METIS利用DAG来预测计划的性能。图中的每个顶点对应一个物理操作符，每条边表示由于数据依赖而在两个操作符之间存在的依赖关系。具体来说，存在两种类型的边：如果一个操作符必须在另一个操作符的整个数据输出完成后才能执行，则将这种依赖关系称为硬依赖；否则，如果可以以流水线方式执行，则将其称为软依赖。

对可见性的计划选择的想法为：提前在可用数据上调度预执行，而不是阻塞查询直到所有数据都可见，这有助于掩盖HTAP数据库的可见性延迟。在混合计划中，METIS可以先从行存储中检索数据，并在从列存储中检索数据之前执行哈希连接的第一阶段（即构建哈希表），从而减少整体响应延迟。与另一个从列存储中检索所有数据，然后执行哈希连接的物理计划相比，即使索引扫描的执行时间比列扫描略长，混合计划在查询延迟方面也可能优于物理计划。

可见性的计划选择

上述算法展示了可见性的计划选择的伪代码：

1. 基于DAG抽象，算法首先通过从图中删除不可用的待处理任务，计算每个计划的预执行任务（第13-14行）。通过这样做，得到一组预执行任务（即）。

2. 该集合中的每个任务都是一个强连通分量，包含多个物理操作符。由于中的任务之间没有数据依赖，它们可以并行执行。算法在第18行将可见性延迟的知识整合到计划成本中，这捕获了用户观察到的端到端查询延迟。

3. 最后，算法使用修订后的成本来指导选择函数（第4-10行），并生成在查询延迟方面成本最低的考虑可见性的物理计划。

6.1.1 可见性延迟估计

可见性计划选择示例

在METISDB中，可见性延迟来自四个方面：

1. 新的写操作提交到数据传输管道，然后从行存储传输到列存储。

2. 传输的逻辑日志由增量存储解析。

3. 新的更新追加到增量存储并由B+树索引。

4. 更新提交到增量存储并最终对查询可见。

因此，除了受物理限制（即网络内延迟）约束的数据传输时间外，影响可见性延迟的最重要参数是写操作的负载：写操作越多，意味着需要处理的数据越多，导致排队时间越长。此外，由于METISDB的增量存储是只追加的，来自行存储的分散更新也会追加到增量存储中。因此不需要考虑更新的分布情况。因此，METIS使用历史数据来估计可见性延迟，这些历史数据将OLTP工作负载的并发性映射到可见性延迟。

6.1.2 未来扩展

为了保证数据一致性，METISDB保证快照隔离，并且METIS总是使用最新的时间戳来执行查询，以实现最佳的数据时效性。在实践中，METISDB以数据块为粒度跟踪时间戳，对数据块的更新是单独排序的。因此，在METIS中，一部分数据在一开始就可以在增量存储中使用，并且增量存储的可见性会逐渐增加。因此，可以将增量计算技术结合到对列的预执行中，以进一步提高性能。

6.2 主动的查询重新优化

METIS主动查询重新优化机制

为保持查询计划高效且工作负载相互隔离，METIS会主动对计划进行重优化。如图所示，在进行查询优化时，METIS会生成一组种子计划（即一个行存储计划、一个列存储计划和一个 HTAP感知计划），以此降低重优化成本。执行查询时，METIS从成本最低的计划开始，并依据运行时统计信息持续对计划进行重优化。

6.2.1 种子计划

为生成种子计划，METIS运用了改进后的成本模型和上述的可见性感知计划选择算法。

METIS首先生成成本最低的混合计划，然后基于该混合计划的逻辑结构，通过考虑不同的物理操作符，生成优化后的行存储计划和列存储计划。因此，所有种子计划逻辑结构相同，但可能采用不同的物理操作符（如行扫描与列扫描、嵌套循环连接与哈希连接、流聚合与哈希聚合）。通常情况下，如果存在比行存储计划和列存储计划更优的混合计划，种子计划就由三个物理计划组成；否则，种子计划包含两个计划。

6.2.2 运行时统计信息

为判断是否应重优化查询计划，METIS会依据运行时统计信息定量评估决策效果。为实现高效执行，当估计基数与实际统计信息偏差较大（如超过20%）时，METIS会重优化物理操作符。

为保障性能隔离，METIS会拼接子计划以缓解资源竞争，通过设置观察到的物理资源利用率阈值（如80%的CPU利用率）来控制物理资源的使用，并通过竞争足迹阈值（即冲突事务的数量），来控制每个表上的逻辑竞争。

6.2.3 计划拼接

在重优化计划时，METIS会从种子计划中拼接子计划，避免在查询执行流水线中丢失部分已完成的工作。由于METIS中的种子计划逻辑结构相同，拼接新计划本质上是对剩余未执行计划的物理操作符选择进行重优化。因此，先前计划中已完成的工作可部分应用于新拼接的计划。

7. 实验

在本节中，实验首先研究METIS的整体性能，接着依次评估其三项关键技术（即增量存储的成本模型、可见性计划选择、资源的计划重优化），评估主要围绕以下问题展开：

● METIS的整体性能如何？

● 在METIS中使用Demain有哪些优势？

● 可见性计划选择算法有何帮助？

● 重优化的效果如何？

● 哪些技术对HTAP数据库更有益？

7.1 实验设置

实验在一个由七台机器组成的集群上进行所有实验。每台机器配备2.60GHz的Intel (R) Xeon (R) E5 - 2690 v3 CPU（即24核，单NUMA节点）、带宽为544Gbps的64GB内存、带宽为6Gbps的960GB Dell DD4G0 SSD，以及40Gbps的NetXtreme NIC。

实验使用三个行存储对数据库进行水平分区，三个列存储采用与行存储相同的分区策略。每个存储都与执行引擎一同部署在独立的机器上。作者在一台备用机器上设置客户端程序和全局元服务，用于发送客户端请求并维护全局一致的元数据，并使用Linux tc模拟机器间3ms的网络延迟，这与数据中心内部的延迟相符。

实验还采用了三种工作负载：

●  CH-benCHmark：简称CH，这是HTAP场景中一种知名的工作负载，用于评估METIS在混合工作负载下的性能。

●  TPC-DS：规模因子设为100，用于分析2.2节中的混合计划。由于TPC-DS是纯OLAP工作负载，不含任何写事务，因此未用于评估METIS。

●  YCSB：为微调工作负载，利用YCSB的API开发了一个微基准测试。该微基准测试包含两个表（A和B），每个表有1亿行，包含一个64位的主键属性和十个数据属性，并在每个表上构建了主键索引。

8.1.4 基线

在实验中，基线使用METIS的相同代码库模拟与HTAP无关的方法，同时禁用所有HTAP感知优化（即不使用增量存储的成本模型（视为①）、可见性计划选择（视为②）、资源的计划重优化（视为③））。

此外，实验还研究了仅使用行存储和列存储计划处理OLAP查询的性能，这种情况下优化空间局限于行存储或列存储。需要注意的是，仅使用行存储和列存储计划的基线在实际部署中可能不太现实，因为它们依赖用户提示来区分OLTP和OLAP查询，限制了HTAP的功能。相比之下，METIS或与HTAP无关的方法可以根据成本模型自动区分。

7.2 METIS整体性能

为研究METIS在HTAP工作负载下的性能，实验为CH和YCSB创建了三种不同的场景，其中OLTP负载分别为轻量级（约为峰值吞吐量的20%）、中等（约为峰值吞吐量的50%）和高强度（约为峰值吞吐量的80%）。

分析查询完成时间

结果展示了十轮分析查询的完成时间。结果表明，OLTP并发会影响所有候选查询计划的性能。这是因为随着OLTP并发增加，更多事务在行存储中消耗资源，进而影响行扫描和索引扫描的性能。同时，数据同步也会导致读放大，影响列扫描的性能。不过，与行扫描和索引扫描相比，列扫描的性能下降幅度要小得多，因为它避免了与OLTP的直接资源冲突。和与HTAP无关的计划相比，METIS的性能下降相对较小，这是因为METIS能更准确地为子查询选择访问路径。

对于YCSB工作负载，实验结果表明，在轻量级和中等OLTP并发下，使用与HTAP无关的计划的方法和METIS都能生成最优计划。METIS的性能略好，因为METIS的可见性计划选择算法可以提前安排在行存储上的执行（即所有数据在增量存储中均可用）。在高OLTP并发下，METIS切换到列存储计划，以缓解行存储上的资源竞争。而与HTAP无关的方法仍使用混合计划，导致性能欠佳（。

性能隔离：维持OLTP和OLAP之间的强性能隔离，是METIS的一个重要设计目标。

OLAP对OLTP性能的影响结果

实验结果所示，对于METIS，OLAP吞吐量随着OLAP线程数量的增加而增加，最终趋于平稳；在整个实验过程中，OLTP吞吐量基本保持不变。相反，与HTAP无关的方法导致OLTP吞吐量下降更为严重，。这是因为METIS在面对资源竞争时，会主动重优化低效计划。重优化后，METIS对分析查询使用列存储计划或子计划。因此，METIS能够实现与不使用混合计划的方法相同的性能隔离特性。

总而言之，METIS能够在不同的HTAP工作负载中，有效利用混合计划加速分析查询，同时维持OLTP和OLAP之间的强性能隔离。

7.3 使用Demain的优势

在本实验中禁用优化②和③，在CH-benCHmark工作负载的默认设置下，研究Demain①的性能优势。

各种查询延迟结果

表格展示了分析查询的延迟。对于与HTAP无关的方法和仅使用Demain的METIS，用R标记生成的行存储计划，用C标记列存储计划，用H标记混合计划。总体而言，METIS的表现优于其他三个竞争对手。和与HTAP无关的方法相比，METIS的几何平均加速比达到1.72倍。

对于特定查询，使用与HTAP无关的方法和METIS都能从混合计划中受益（如Q4）。这是因为对于这些查询，行存储和列存储在检索数据时都不占优势。然而，由于成本估计容易出错，使用与HTAP无关的方法可能导致性能不佳。此外，实验观察到在特定查询（如Q10、Q12和Q22）上，由与HTAP无关的方法生成的混合计划的性能，可能比行存储计划和列存储计划都差。

Demain的准确性分析：实验通过比较预测的交叉选择性和测量的交叉选择性，单独分析Demain的准确性。交叉点是指行扫描和列扫描执行时间相同时的选择性。实验显示Demain误差率在12.28%左右，且在测量的交叉选择性标准差范围内。

Demain准确性结果

总体来说，Demain作为METIS的关键组件，能够准确预测索引扫描和列扫描之间的交叉选择性，从而指导METISDB中的访问路径选择。使用Demain，METIS纠正了与 HTAP无关的方法生成的次优计划，在竞争对手中实现了最佳性能。

7.4 可见性计划选择的优势

接下来，实验启用可见性感知计划选择算法②时METIS的性能。在这五个查询中，与不考虑可见性的方法相比，METIS的几何平均加速比达到1.13倍。

可见性计划选择查询延迟结果

实验还研究了Q21的物理计划以及每个操作符的累计执行时间。如图展示了通过禁用②（即仅使用Demain）生成的“最优”成本计划，图b展示了可见性计划。

可见性计划的成本分析

结果显示，尽管可见性计划在检索数据时可能花费更多成本，但其延迟比“最优”成本计划更短（即8.97s对9.42s）。

可见性延迟估计的准确性：实验研究了估计的准确性。对于每个并发情况，测量的可见性延迟是在5分钟内每秒延迟的平均值。估计曲线通过对样本（不包括异常值）的平均值进行三次多项式拟合得到。总体而言，可见性计划的估计大致准确，误差率在观察样本的24.8%。

估计的准确性结果

敏感性研究：实验进行了敏感性分析，以确定估计误差对分析查询性能的影响。总体而言，低估计会使查询更倾向于列扫描，查询性能可能退回到不考虑可见性方法的性能水平。高估计会使查询更倾向于行扫描，当估计值趋于无穷大时，查询性能可能退回到仅使用行存储计划的性能水平。

可见性选择的估计误差对分析查询性能影响结果

总而言之，对于特定查询，METIS可以通过预执行非阻塞子计划进一步提升查询性能。可见性延迟的估计误差可能会影响查询计划的质量，但在实际中可以得到缓解。

7.5 重优化的效果

在本实验中通过研究OLTP吞吐量和OLAP延迟随时间的变化，展示重优化方法如何帮助METIS实现这两个好处。由于重优化是对改进成本模型以实现这两个好处的方法的补充，实验也研究了仅使用Demain①作为基线的性能。为清晰起见，实验禁用了②。

OLTP吞吐量和OLAP延迟结果

在实验开始时（即0-300秒），使用128个OLTP线程以达到中等OLTP吞吐量。使用Demain的两个METIS都能生成最优混合计划。

当实验在300秒时将OLTP线程数从128增加到256时，OLTP吞吐量相应增加，这使得行存储上的CPU周期消耗达到约92%。在这种情况下，为了提高查询效率和工作负载之间的性能隔离，METIS（①+③）避免从行存储检索数据。它使用种子计划对混合计划进行重优化，延迟时间更短。相比之下，仅使用Demain的METIS仍使用与第一阶段相同的混合计划，因为Demain没有捕捉到CPU上的资源冲突，而是将磁盘I/O视为主要参数。在900秒时，METIS的两种变体都生成了行存储计划，效果类似。

实验表明，重优化可以帮助METIS平稳适应工作负载的变化，同时保持工作负载之间的性能隔离，并提供合理的OLAP性能。

7.6 经验总结

通过实验，本文可以得到以下总结：

● 型，这是实现混合计划潜力的关键。

● 其次，可见性计划选择可以通过预执行进一步提升混合计划的性能。然而，其潜力受到行存储和列存储之间可见性延迟的物理限制。特定查询的性能提升取决于成本模型和延迟估计的准确性。

● 第三，重优化可以减轻成本模型的不准确性，并处理模型未考虑到的资源冲突。通过这种方式，重优化是实现性能隔离的关键，即使成本模型的输入（例如基数估计）完全准确，重优化也不可或缺。

8. 相关工作

8.1 HTAP数据库中的查询优化

1. 独立成本模型：一些HTAP数据库独立地处理OLTP和OLAP的查询优化，采用基于路由的方法，并非为混合数据访问而设计。在收到SQL请求后，它们依靠嵌入式用户级提示或中间件层来区分OLTP和OLAP查询，然后在理想的引擎和存储上执行查询。这种方法易于实现，但以性能和功能不佳，因为获取查询的先验知识具有挑战性，而且可能不准确。

2. 统一成本模型：另一种方法是将列存储作为额外的数据访问路径进行补充。

● F1 Lightning：使用其F1优化器（即专为OLTP设计的优化器）生成逻辑计划，并在物理规划时考虑仅适用于Lightning的索引和视图。

● SQL Server：通过其数据库引擎优化顾问（DTA）分析并推荐在适合给定工作负载时使用列存储。

● TiDB：扩展查询优化器以探索同时访问行存储和列存储的物理计划。

● Oracle Dual：将列索引补充到其优化器中，作为高速表扫描的替代执行方法。

8.2 现代数据库中的访问路径选择

访问路径选择是数据库中从表中检索数据最基本的优化之一。近期研究主要集中在大规模列数据库、内存行数据库以及 HTAP数据库中的混合物理设计的分析上：

● Kester等人通过比较B+树探测和列存储共享扫描，分析了内存分析数据库的访问路径选择问题。

● Dziedzic等人对商业级数据库的访问路径选择进行了分析，考虑了列存储索引之上的二级B+树。

● Abadi等人进行了一项实验研究，量化了列存储和面向行的B+树之间的显著差异。

8.3 使用预执行进行优化

推测执行允许处理器在被提示之前执行一系列任务，在操作系统领域有深入研究。如果最终发现这些工作并不需要，结果将被忽略。不同的是，METIS从不丢弃预执行结果。流处理（例如Kafka、Flink）对查询进行增量处理。当某些输入数据流被阻塞时，它们会在可用数据上预执行查询。不同之处在于，METIS在执行前选择一致的数据视图，并在查询优化时考虑不同的数据格式。

8.4 主动查询重优化

有几项有影响力的工作聚焦于资源感知重优化方法：

● Babu等人估计以边界框计算的统计信息，并生成用于运行时重优化的可切换种子计划。

● Ding等人利用从其他先前执行计划中收集的高效子计划的有价值信息，并在运行时拼接这些子计划。

● Viswanathan等人在Hive和Spark中使用基于成本的模型，将资源规划集成到查询规划器中。

● Li等人提出一种资源感知深度学习模型，该模型可以预测计划的执行时间，从而将可用资源的知识整合到查询规划中。

不同的是，METIS还旨在保持工作负载之间的性能隔离，这是HTAP特有的需求。

9. 结论

本文系统地分析了分布式HTAP数据库中混合计划的潜力和挑战，提出了METIS，一种支持HTAP的混合优化器。METIS使用修订后的成本模型进行访问路径选择，通过可见性感知算法选择计划，并主动重优化查询。实验展示了METIS的效率和适应性。

论文解读联系人：

刘思源

13691032906（微信同号）

liusiyuan@caict.ac.cn