OceanBase 4.0 解读：分布式查询性能提升，我们是如何思考的？
关于作者
王国平
OceanBase 高级技术专家
目前 OceanBase SQL 引擎的技术负责人。2016 年加入 OceanBase，负责 SQL 引擎的研发工作。2008 年毕业于哈尔滨工业大学，2014 年在新加坡国立大学获得博士学位，博士期间主要研究方向是数据库领域的(多)查询优化和处理。在加入 OceanBase 之前，曾经在华为从事数据库的研发工作。
性能是衡量数据库系统的重要指标之一，也是数据库系统领域一直备受关注的话题。在 OceanBase 3.x 版本中，OceanBase 已经实现了相对完善的优化器引擎、单机执行引擎、并行执行引擎和向量化执行引擎。在 2021 年 5 月份，OceanBase 用这个版本打榜了 TPC-H，在数据分析型基准测试榜单的 30000GB 结果一栏，OceanBase 占据性能排行首位，其中代表着数据库核心性能的每小时执行请求数综合指标达到了 1526 万 QphH@30,000GB。这次打榜充分证明了 OceanBase 的分布式查询能力性能，而且具备线性可扩展。
尽管如此，在整个 3.x 版本的大规模应用中，我们在部分业务场景中还是遭遇到了一些性能问题，比如在特定的分布式场景中生成了不优的执行计划、执行引擎对于不优的执行计划的容错能力、特定场景下没法充分利用所有的并行度来加快查询的执行等。为了解决这些问题，在 OceanBase 4.0 设计之初，我们就一直在思考，OceanBase 应该如何改进 SQL 引擎来提升分布式查询性能。分布式查询优化和分布式执行引擎从根本上决定了 SQL 引擎的分布式查询性能，下面我们从这两个方面来聊一聊我们的思考。
OceanBase 4.0 如何做分布式查询优化 ？
众所周知，查询优化是数据库内核开发的重点和难点，也是数据库查询性能的关键点。查询优化的作用是给帮助用户写的每一条 SQL，选择一个最优的执行计划。通常来说，一条 SQL 会有很多等价的执行计划，不同执行计划的性能可能会有数量级别的差异，所以查询优化很多时候从根本上就决定了查询的性能。OceanBase 是一个分布式关系数据库系统，这就意味着 OceanBase 天生就需要解决分布式查询优化的问题。在整个关系数据库系统中，查询优化一直是开发的难点，而分布式的查询优化就更加加剧了优化的难度。接下来我们来聊聊相比于单机查询优化，分布式查询优化的挑战在哪里。
▋ 分布式查询优化的挑战
分布式查询优化大大提升了计划枚举空间
在查询优化中，优化器的其中一个目标是需要给执行计划中的每个算子选择一种具体的实现方法。在单机的场景下，算子的实现方法只需要考虑单机的实现，但是在分布式的场景中，算子的实现方法除了要考虑单机实现之外，还需要考虑其分布式的实现。就拿数据库中的连接算子而言，在单机的场景中，通常的实现方法有 hash join、merge join 和 nested loop join。在分布式的场景中，通常的实现方法有 partition wise join、partitial partition wise join、hash-hash distribution join 和 broadcast distribution join。这些分布式的实现方法正交上单机的实现方法就会大大增加分布式查询优化的计划枚举空间，会让整个分布式查询优化变得更加有挑战。
分布式查询优化需要维护更多的物理属性
在单机的查询优化中，算子序是一个非常重要的物理属性，因为算子的序可能会用来加速后续的一些算子的执行。算子序本质上就是运行完这个算子之后，数据库中的元组是不是按照特定的序输出的。举个简单的例子，对于索引(a,b,c)的扫描，因为在 OceanBase 中索引扫描是保序扫描，所以这个索引扫描之后的序就是(a,b,c)。算子序跟特定的算子实现有关系，而且它可能会影响后续算子的代价，所以在每个算子执行之后，查询优化都会维护序这个物理属性，并且在做计划裁剪的时候会保留有用序的执行计划。
在分布式查询优化中，除了序这个物理属性之外，另外一个物理属性就是分区信息。分区信息主要包括数据的分区方式以及每个分区的物理位置信息。分区信息从根本上决定了一个算子的分布式算法的选择，比如一个连接能不能做 partition wise join 是取决于连接键和表的分区信息的，所以分区信息同样可能也会影响后续算子的代价，所以在分布式查询优化中，除了维护序这个物理属性之外，我们还需要维护分区信息这个物理属性。分区信息的维护最终会影响计划裁剪和计划选择，同时也增加了整个分布式查询优化的复杂性。
分布式查询优化需要更加精准的分布式代价模型
在查询优化中，代价是衡量一个执行计划好坏的标准，通常代价代表了一个执行计划的执行时间或者对数据库系统资源的占用量，包括 CPU 资源、IO 资源、网络资源等。在单机执行中，代价模型通常只需要考虑 CPU 和 IO 就可以。但是在分布式的场景中，除了考虑 CPU 和 IO 的代价之外，还需要考虑网络传输代价、查询的并行度以及一些分布式特定优化场景的代价，比如 bloom filter 的代价计算等。这些因素从根本上提升了分布式代价模型设计和拟合的复杂性，也从一定程度上增加了整个分布式查询优化的复杂性。
▋ OceanBase 3.x 的二阶段分布式查询优化方法
为了解决分布式查询优化带来的复杂性，跟业界的大部分解决方案类似，OceanBase 3.x 的版本采用二阶段的分布式查询优化方法。
第一阶段: 假设所有的表都是本地的，依赖已有的单机查询优化能力选择一个本地最优的执行计划。
第二阶段: 在固定连接顺序和本地算法的基础上，基于简单的分布式代价模型为每一个算子选择一个分布式算法。
下图展示了一个二阶段的分布式查询优化方法的例子，其中左边表代表的是第一阶段生成的本地最优的执行计划，右边代表的是第二阶段生成的分布式计划。对于 Q1，在第一阶段，单机优化器选择了一个如左边所示的本地最优的执行计划，其中 MJ、HJ 和 HGBY 分别代表了 merge join、hash join 和 hash group by 的本地算法。在第二阶段，在固定连续顺序和本地算法的基础上，基于简单的分布式代价模型，为每一个算子选择了一个分布式算法。在这个例子中，为 MJ 节点选择了一个 partition wise join 的分布式连接算法，为 HJ 节点选择了一个 hash-hash 重分区的分布式连接算法。
二阶段分布式查询优化放大大简化了整个分布式查询优化的复杂度，但是 OceanBase 3.x 在大规模商用的过程中也遇到了很多因为二阶段导致的分布式查询优化不优的情况，下面我们总结了比较突出的两大类问题。
没有考虑分区信息导致选择了不优的本地算法
二阶段的分布式查询优化通常会因为第一阶段优化时没有考虑分区信息而选择了不优的本地算法。考虑如下图所示的一个查询 Q2 和它的第一阶段的计划，在第一阶段本地优化的时候，如果谓词 R1.c = 100 的选择率比较低，那么满足这个条件的 R1 的行数会比较少，这个时候优化器会选择 nested loop join 来执行这个查询，即对于满足条件的 R1 中的每一行，通过 R2 上的索引 idx 快速的获取满足条件的 R2 数据。但是在真实的执行过程中，我们发现 nested loop join 的执行时间远远比优化器估计的要大很多，原因是因为 R2 是一个包含 100 个分区的分区表，在执行 nested loop join 的过程中，对于 R1 中的每一行，都需要在 R2 的每个分区都执行一遍，那么这个执行时间其实会扩大 100 倍。如果我们把这个扩大 100 的执行时间考虑进去，那么最优的计划可能就是 hash join 而不是 nested loop join 了。在这个场景中，因为第一阶段的优化没有考虑分区信息，所以在第一阶段会错误的估计单机算子的代价，从而导致选择了不优的本地算法。
没有考虑分区信息导致选择了不优的连接顺序
二阶段的分布式查询优化通常因为在第一阶段没有考虑分区信息而选择了不优的连接顺序。考虑如下的一个查询 Q3 和它所对应的两个本地计划和分布式计划，其中第一个计划选择了 ((R2, R3), R1) 的连接顺序，第二个计划选择了 ((R1, R2), R3) 的连接顺序。如果不考虑分区信息，在第一阶段优化器可能会选择 ((R2, R3), R1) 这样的连接顺序，但是这个连接顺序经过第二阶段之后可能会产生更多的网络传输代价，如下图所示，表 R1、R2、R3 以及 R2 和 R3 的连接结果都需要经过网络传输。一个更好的连续顺序可能是 ((R1,R2), R3)，因为这个连接顺序经过第二阶段之后只需要传输 R3 以及 R1 和 R2 的连接结果 (R1 和 R2 因为可以做 partition wise join，所以是不需要做网络传输的)。这种因为没有考虑分区信息而导致选错了错误的连接顺序的场景在我们的业务场景中也大量存在。
在如上的两个场景中，究其本质就是因为在第一阶段做优化的时候没有考虑分区信息而选择了不优的连接顺序和本地算法。通过这两个场景我们也了解到了二阶段的分布式查询优化方法的缺点是显而易见的，接下来我们来聊一聊 OceanBase 4.0 是如何做分布式查询优化来解决这个问题的。
▋ OceanBase 4.0 的分布式查询优化
我们认为分布式查询优化一定要使用一阶段的方法，即要同时枚举本地算法和分布式算法并且使用分布式代价模型来计算代价，而不是通过分阶段的方式来枚举本地算法和分布式算法。OceanBase 4.0 重构了整个分布式查询优化方法，从原先的二阶段变成了一阶段的分布式查询优化方法。
为了方便我们描述一阶段的分布式查询优化方法，这里我们简单介绍一下 System-R 的 Bottom-up 的动态规划方法。给定一个 SQL 语句，System-R 用 bottom-up 的动态规划的方法来进行连接枚举和连接算法的选择。给定一个 N 张表的连接，该方法以 size 为驱动枚举每一个子集的执行计划。对于每一个枚举的子集，该方法通过如下的方式来获取最优的计划：
枚举所有单机的连接算法，维护序这个物理属性，使用单机代价模型来计算代价。
保留代价最小的计划和存在有用序的计划，一个计划的序是有用的当且仅当该序对后续算子的分配有用。
下图展示了一个 4 张表的连接枚举例子。该算法首先会枚举大小为 1 的基表的计划，对于每一张基表，该方法会枚举所有的索引并且保留代价最小和存在有用序的计划。然后该算法为枚举每个大小为 2 的子集的计划，比如在枚举 {R1,R2} 这两张表的连接的时候，该方法会考虑所有的单机的连接算法，然后再正交上所有 R1 和 R2 保留的计划，最终达到枚举所有执行计划的目的。以此类推，该算法会继续枚举直至大小为 4 的子集的计划都已经枚举完成。
基于已有的单机的 System-R 的查询优化方法，OceanBase 4.0 的分布式查询优化按照如下的方式工作:
对于每一个枚举的子集，枚举所有算子的分布式算法，对于每一个分布式算法，OceanBase 使用分布式代价模型来计算代价，同时 OceanBase 会同时维护序和分区信息这两个物理属性。
对于每一个枚举子集，除了保留代价最小的计划，保留存在有用序的计划，同时还需要保留有存在有用分区信息的计划。一个分区信息是有用的当且仅当它对后续的算子有用。考虑下图所示的场景, 在该场景中，P1 采用了 HASH-HASH 重分区的 HASH JOIN 方法, P2 采用了对 R2 做 BROADCAST 的 HASH JOIN 方法，虽然 P2 的代价比 P1 的代价高，但是 P2 继承了 R1 的分区信息，对后续的 group by 算子是有用的，因此 P2 这个计划也会被保留。
OceanBase 4.0 使用了一阶段的分布式查询优化方法，相比于单机的查询优化，分布式查询优化的计划空间是非常大的。为了解决计划空间大的问题，OceanBase 4.0 发明了很多快速裁剪计划的方法以及新增了新的连接枚举算法来支持超大规模表的分布式计划枚举。 通过这些技术，OceanBase 4.0 大大减少了分布式计划空间，提升了分布式查询优化的性能。同时我们的实验结果也表明 OceanBase 4.0 可以在秒级内完成 50 张表的分布式计划的枚举。
OceanBase 4.0 如何提升分布式执行引擎性能 ？
相比于 OceanBase 3.x 版本，OceanBase 4.0 在执行引擎方面做了很多方面的工作，其中包括实现了新的分布式和单机算法(比如 null-aware hash anti-join、shared broadcast hash join、hash-based window function、partition bloom filter 等)，完善了整个向量化引擎的实现，开发了极致的并行下压技术，开启了自适应技术的开发。这些引擎方面的工作都大大提升了分布式查询和单机查询的性能。在这里我们主要介绍一下 OceanBase 4.0 的自适应技术和并行下压技术。
▋ OceanBase 4.0 执行引擎开始朝着自适应的方向发展
在 OceanBase 的业务场景中，我们发现 OceanBase 执行引擎对优化器产生的不优的执行计划没有任何的容错能力，即一旦优化器产生了不优的执行计划，那么执行引擎在执行的时候是没办法做一些计划上的调整从而到达提升性能的目的。虽然我们通常说优化器的目的是给数据库的查询选择一个最优的执行计划，但是从数据库发展的历程来看，优化器自身存在很多解决不了的难题，比如优化器始终解决不了估行不准确的问题，所以优化器有可能会选到一个不优的执行计划甚至是一个非常差的执行计划。
为了解决这个问题，OceanBase 4.0 执行引擎开始朝着自适应的方向发展。自适应技术是指执行引擎根据当前的执行状态来识别出来一部分计划不优的场景，通过动态调整执行计划从而达到提升执行性能的目的。我们认为一个执行引擎发展到一定阶段一定要通过自适应技术来尽量解决优化器产生的不优的执行计划的问题，当然我们也不认为自适应技术能够解决掉所有的计划不优的场景。
OceanBase 4.0 实现了自适应的 Group by/Distinct 并行下压技术，它可以解决 Group by/Distinct 并行下压场景中因为计划不优而导致的性能回退问题。在正式介绍该自适应技术之前，我们首先简单介绍一下 Group by/Distinct 并行下压技术。Group by/Distinct 并行下压技术是分布式执行中一种常见的并行下压技术，它的核心思想是提前把 Group by 算子下压下去做部分的数据预聚合，通过预聚合的方式可以减少网络传输从而达到提升性能的目的。 下图展示了一个 Group by 并行下压的执行计划的例子，其中 5 号算子就是下压的 Group by 算子，通过 5 号算子的预聚合可以减少 4 号算子网络传输从而达到性能提升的目的。但是这里需要注意的是 Group by 并行下压不一定会带来性能上的提升，有时候也会导致性能回退，主要原因是因为下压的 Group By 算子会引来额外的计算代价，所以只有当网络传输带来的性能提升超过下压的 Group By 带来的计算开销，Group by 的并行下压才会带来收益。
OceanBase 在之前的版本中都是优化器通过计算代价来决定是否要下压 Group by 算子，但是因为优化器有时会错误的估计行数，会导致出现没有正确的下压 Group by 算子或者错误的下压了 Group by 算子的场景，最终导致执行性能次优。为了解决这个问题，OceanBase 4.0 引入了自适应的 Group by/Distinct 并行下压技术，其核心思想是让优化器总是下压 Group by/Distinct 算子，然后在执行的时候通过采样下压算子的一部分数据来决定是否跳过下压的 Group by/Distinct 算子。该技术的难点在于如何判断下压的算子是否具备足够好的预聚合能力。OceanBase 采用了控制下压算子的 HASH 表在 L3 cache 之内(控制 Hash 表的性能)以及多轮采样的策略(确保数据连续非聚合性带来的误判)来判断下压算子是否具备足够好的预聚合能力。其核心思想如下:
下压算子 hash 表尽量维持在 L2 cache (1M) 内, 如果预聚合效果不好，标记该 hash 表状态为舍弃。如果预聚合效果很好, 可以将 hash 表扩张到 L3 cache(10 M)，如果执行过程中发现需要更大的内存，标记该 hash 表为舍弃状态。
如果当前 hash 表的状态是舍弃状态， 返回 hash 表内所有行并释放，重新建 hash 表，开启下一轮的采样检查。
如果连续 5 次采样检查预聚合效果都不好，就跳过当前下压的 Group by 算子。
这里需要注意的是，相比于完全不下压的场景，自适应的 Group by/Distinct 并行下压会引入一些额外的 overhead，主要是在执行时需要对下压的 Group By/Distinct 算子做一些采样和计算来判断是否需要跳过该算子，但是经过我们对各种数据分布的测试，这个额外的 overhead 基本上可以控制在 10% 之内，但是获取的性能提升是非常大的。
除了自适应的 Group by/Distinct 下压技术之外，当前 OceanBase 4.0 也在探索和实现更多新的自适应技术，包括自适应的创建和探测 bloom filter、自适应地调整 nested loop join 和 hash join，自适应地调整分布式的 broadcast 连接和分布式的 hash-hash 重分区连接等技术。我们相信这些自适应的技术会把 OceanBase 的执行引擎能力提升到一个新的级别，能够使整个执行引擎更加健壮，能够在优化器生成不优执行计划或者非常差的执行计划的时候提升整个查询的性能。
▋ OceanBase 4.0 朝着极致的并行下压技术的方向发展
分布式场景中的并行下压技术是指通过下压算子的计算从而达到提升性能的目的。并行下压技术通常通过最大限度地利用并行度或者减少数据网络传输来提升分布式查询的性能。并行下压技术对分布式的查询性能提升是非常明显的，在很多场景中都有数量级别的性能提升。 前一个章节中介绍的 Group By/Distinct 并行下压技术就是一个比较典型的并行下压的场景。相比于 OceanBase 3.x 的版本，OceanBase 4.0 实现了一套非常完善的并行下压技术，基本上覆盖了分析类场景中的所有算子，包括 Group/Rollup/Window Function/Distinct 等。
下面这个表格比较了 OceanBase 在 3.x 版本和 4.0 版本的并行下压技术上的区别。
OceanBase 4.0 中每个算子的并行下压技术的实现都是不一样的，考虑到并行执行的复杂性，每种实现都面临不一样的挑战。因为文章篇幅的原因，这里我们不一一介绍每一种并行下压技术，我们通过 OceanBase 对于处理包含 distinct 去重的聚合函数的三阶段并行下压技术来介绍一下并行下压技术的优势。考虑下图的例子，其中 Q1 包含了两个 distinct 去重的集合函数，在 OceanBase 3.x 的版本中，Q1 是没办法做任何的并行下压的，从 Q1 的执行计划中也可以看出来，所有的去重逻辑和聚合逻辑都是在 0 号算子中计算，而且 0 号算子是不具备任何并行的能力的，这会导致整体的执行性能很差。
为了解决这种包含 distinct 的聚合函数的分布式执行性能，OceanBase 在 4.0 引入了三阶段并行下压的逻辑。我们用下图中包含一个 distinct 去重的聚合函数的场景来简单介绍一下三阶段并行下压的大体逻辑。三阶段并行下压逻辑主要包括三个阶段：
第一阶段: 下压 distinct 逻辑去做数据部分去重，这里对应了下图中的 6 号算子。
第二阶段： 按照去重列做一次数据重分区，然后做完全去重和部分预聚合计算，这里对应了下图中的 3~5 号算子。
第三阶段： 把第二阶段的结果做最终的聚合，这里对应了下图中的 0-2 号算子。相比于不做任何的下压，这里三阶段并行下压有两个性能上的好处。首先三阶段并行下压可以最大限度地利用并行度去做数据去重和数据预聚合。其次通过下压 distinct 做数据部分去重可以减少网络传输。
上面我们介绍了只包括一个 distinct 去重的聚合函数的三阶段并行下压处理，这里有一个问题是如果包含多个 distinct 的聚合函数，三阶段下压技术是否还可以工作？答案是肯定的，这里的处理技巧在于对于包含 N 个 distinct 去重的聚合函数的场景，在第一阶段的时候，为每一个包含 distinct 的聚合函数，我们会冗余一份数据并且标记这一份数据属于这个聚合函数的，剩下的第二阶段和第三阶段的处理基本上都是类似的，会有一些实现上的小差别。下图展示了 OceanBase 中包含 2 个 distinct 的聚合函数的三阶段下压例子，其中 aggr_code 就是用来标记不同的 distinct 所冗余的数据。
分布式并行下压的场景是一个比较常见的客户场景，在 OceanBase 3.x 的版本中，我们也遇到了不少因为并行下压功能的不完善导致的分布式查询性能问题。我们相信在 OceanBase 4.0 可以很好地解决这类问题，提升分布式查询的性能。
写在最后
文章的最后，我们希望和大家分享，OceanBase 4.0 的分布式性能提升实际效果。相比于 OceanBase 3.x 版本，OceanBase 4.0 实现了全新的分布式代价模型和分布式查询优化框架、开发了一套非常完善的并行下压技术，开启了自适应技术的开发。这些技术的开发驱动一方面来自于我们对客户需求的理解，另一方面也来自于我们自己对分布式系统的理解。
为测试 Oceanbase 4.0 版本这些技术的工作效果，我们在 TPC-DS 100GB 上进行了测试，实验结果表明 OceanBase 4.0 的分布式性能提升效果显著，TPC-DS 100GB 的 99 个查询的执行时间总和从 918s 下降到了 270s ，在本文的最后，大家也可以看到 TPC-DS 100GB 上其中一部分查询在 OceanBase 3.x 版本和 4.0 版本的实际性能对比。
TPC-DS 100GB 性能测试对比（OceanBase 3.x vs. 4.0)
以上是我们对 OceanBase 4.0 分布式性能查询价值及技术演进的思考。数据库的本质是基础软件，站在软件「使用者」的角度来看，我们希望在未来的 4.x 版本中，通过分布式查询优化和执行引擎技术的创新能力，帮助用户带来更易用的使用体验和更快速的查询性能。
版权声明: 本文为 InfoQ 作者【OceanBase 数据库】的原创文章。
原文链接:【http://xie.infoq.cn/article/f28375fc701b0da5bf61a031f】。文章转载请联系作者。
企业级原生分布式数据库 2020-05-06 加入
github：https://github.com/oceanbase/oceanbase 欢迎大家
评论