通过一条SQL 理解 Doris 优化器（RBO/CBO）原理

下面从 SQL 的本质来讲解一下优化器的地位。

首先，SQL 的核心是一种描述性语言，使用者只需定义所需的数据及数据的获取方式由优化器来决定。可以说，执行引擎相当于汽车的发动机，而查询优化器则是方向盘。若没有合适的优化器指引，再强大的引擎也可能导致我们在高速行驶中撞上内存溢出的障碍。因此，优化器是 SQL 中极为关键的组件。

在一条 SQL 查询的处理流程中，优化器扮演着什么样的角色呢？如图中标示的红框区域所示，当一条 SQL 查询被提交后，它首先经历的是语法解析阶段，生成相应的抽象语法树，随后进行语义分析。在这一系列步骤之后，进入逻辑计划的重写阶段，在此过程中会应用多种规则。完成重写后，系统会生成若干个备选的执行计划，并通过成本模型评估这些计划，最终挑选出最佳的执行方案交付给查询引擎执行。Nereids 优化器主要负责的就是查询计划的改写与优化这两大部分的工作。

具体而言，改写部分被称为基于规则的优化（RBO），而代价估算则被称为基于代价的优化（CBO）。为了确保与现有的优化器和执行引擎的兼容性，还需要一个“计划翻译”的步骤，将新优化器产生的执行计划转换为后端（BE）能够理解和执行的查询计划。

在 RBO 的规则集合中，包含了诸如谓词下推、表达式重写、常量折叠以及消除无用算子等操作。这些规则通常能够提升查询的效率，因此由它们生成的执行计划将会取代初始的计划。有时候，某些规则会被多次应用，直到执行计划不再发生变化。

当 RBO 的改写过程结束后，所产生的执行计划会被作为输入传递给 CBO 阶段。在 CBO 阶段，最重要的任务之一就是确定连接操作的执行顺序，因为这对接口计划的性能有重大影响。此外，CBO 还需处理其他多项任务，例如决定是否将公共表表达式（CTE）即带有 WITH 子句生成的视图，作为独立计算的一部分还是嵌入到整个查询中；同时还要选择聚合操作的策略，例如采用单阶段、两阶段、三阶段或是更多阶段的方式来执行。所有这些都是在 CBO 阶段完成的。

上述内容讨论了众多的优化规则，其核心目标都是为了让 SQL 查询执行得更快。然而，正如科学研究中所强调的那样，明确地定义问题往往比直接解决问题更为关键。那么，如何才算恰当地定义了一个问题呢？这就需要我们找到一个恰当的度量标准来评估问题。如果我们仅仅以查询的执行时间作为衡量标准，虽然直观但却缺乏指导意义。根据我的理解，问题应当被定义为：尽可能早地减少涉及的数据量。接下来，我们将从这一视角出发，重新审视那些优化规则。

通过一个简化的 TPC-H 示例来说明这一点。在这个例子中，我们进行了查询改写。场景描述了一个包含大量订单的情况，其中订单的买卖双方都有各自的国籍信息。我们的目标是从中筛选出中国和美国之间交易的订单，并据此生成下表。

理解了这条 SQL 的处理方式，我们就能明白优化器在此过程中扮演的角色。根据条件：（卖方的国籍为中国且买方的国籍为美国）或（卖方的国籍为美国且买方的国籍为中国）来筛选中美之间的贸易订单。由于这个条件不可分割，一个直观的方法是首先将 orders 表与 customer 表进行连接，然后再与 supplier 表连接，接着与 nation 表连接，最后执行过滤操作。这是第一种处理方法，但其效率相对较低。

更优的做法是，鉴于我们要筛选的是中美之间的贸易记录，可以预先设定一个条件：仅选择国籍为中国或美国的 customer 和 supplier。这是优化器实施的一项重要优化措施——尽管这些额外的条件看起来可能有些多余，但实际上它们对于提前缩减 customer 和 supplier 的数据规模至关重要。这意味着，在与 orders 表进行连接时，右侧的表不再是全部的 customer 数据，而仅仅是其中的一部分；同样地，在与 supplier 表连接时，右侧表的数据也仅限于部分 supplier。同时，左侧的 orders 表也会被筛选，只保留那些 customer 国籍为中国或美国的订单。这样一来，在执行 join 操作时，无论是左侧还是右侧的数据量都得到了有效减少。这种优化在 TPC-H 查询中的效果尤为明显，性能提升了约 2 到 3 倍。这里的关键理念在于尽早减少数据规模。希望这个例子能够帮助大家更好地理解优化器努力追求的目标。

除了上述方法外，另一个至关重要的减少数据规模的策略是调整 join 操作的顺序。当事实表与维度表进行 join 时，通常维度表上会施加一些过滤条件，这些条件对事实表具有显著的过滤效果。然而，这引出了一个新的挑战：join 顺序的优化（join reorder）是一个 NP 完全问题，随着表数量的增加，候选执行计划的数量将以指数形式增长。长期以来，针对这一难题并未出现特别创新的解决方案，NP 完全问题通常只能通过动态规划的方法寻求次优解。目前我们所见的各种方法，本质上都是动态规划的不同应用形式，例如 DPSize、DPSub、DPhyper、Cascading 等。在我们的新型优化器 Nereids 中，同时采用了两种动态规划技术：基本的 Cascading 方法，以及 DPhyper 方法，二者相辅相成，共同发挥作用。

这或许是一个对你有用的开源项目，data-warehouse-learning 项目是一套基于 MySQL + Kafka + Hadoop + Hive + Dolphinscheduler + Doris + Seatunnel + Paimon + Hudi + Iceberg + Flink + Dinky + DataRT + SuperSet 实现的实时离线数仓（数据湖）系统，以大家最熟悉的电商业务为切入点，详细讲述并实现了数据产生、同步、数据建模、数仓（数据湖）建设、数据服务、BI报表展示等数据全链路处理流程。

https://gitee.com/wzylzjtn/data-warehouse-learning

https://github.com/Mrkuhuo/data-warehouse-learning

https://bigdatacircle.top/

项目演示：

首个重要的性能提升源自于 RBO 阶段的一次关键重构。在 Cascading 框架中，存在一个名为 Memo 的结构，类似于一个小账本，用于记录所有由规则生成的执行计划。这是因为 CBO 阶段在执行动态规划算法时需要依赖这些信息。众所周知，所有动态规划方法都会使用某种形式的“小账本”，而在 Cascading 中，这个“小账本”就被称作 Memo。最初，我们按照文献中的流程，将执行计划存储在 Memo 中，当对执行计划进行修改时，需要从 Memo 中取出相应的计划片段，这个过程分别称为 copyIn 和 copyOut。在 RBO 阶段，通常是用一个全新的执行计划来替换旧的执行计划，我们依旧沿用了这种方式，即每次生成新的执行计划时，将其存入 Memo，待下一次规则替换时再从 Memo 中取出。然而，反复进行 copyIn 和 copyOut 的操作实际上是不必要的。为此，美团的华建老师花费了几周时间闭关开发，最终提交了一个大型的 PR，极大地提高了 RBO 的效率。尽管这要求我们重新审查一遍 RBO 的所有代码，带来了一定的挑战，但我们非常欢迎这样的改进带来的“痛苦”。

在 RBO 阶段实现了性能的大幅提升之后，CBO 阶段的性能瓶颈便显得尤为突出。这时，我们团队中的 ACM 冠军莫琛辉同学挺身而出。在接下来的几周内，他仔细研究了上百个火焰图，经历了多轮代码的改写与优化，最终成功将原本需要数秒的分析时间缩短至大约 20 毫秒。如果你未来也有构建一个类似 Cascading 框架的需求，那么对 CostAndEnforce 部分的性能优化绝对是一个值得深入探索的重点领域。

下面再介绍下开发过程中所面临的各种各样的挑战。这部分可能是介绍中最有意义的部分。

这里提供了一个基于表数量与 Left Deep Tree、ZigZag Tree、Bushy Tree 搜索空间增长情况的估算。在实际应用中，当表的数量较少时，倾向于使用 Cascading 方法，其优点在于能够将除 join 顺序优化之外的多种规则与 join 顺序优化相结合使用。不过，这种方法的效率相对较低，因此当表的数量较多时，通常会转而采用 DPhyper 方法。

第二个挑战在于我们不得不与误差共存，但这并不意味着我们放弃努力去减少这些误差。首先，让我们探讨一下误差是如何产生的。在进行 join 顺序优化时，这一步骤高度依赖于各种统计信息，包括每次 join 操作后预计的结果行数以及过滤后的行数等。因此，第一类误差来源于统计信息本身，其产生原因主要是抽样。例如，在计算某个字段中不同值的数量（即 NDV，number of distinct values）时，由于无法对全部数据进行精确计算，通常会采用抽样的方法，而这正是误差的一个重要来源。

在对表中的数据进行统计并开始计算时，例如一张包含学生信息的表，若有一个过滤条件为“选出其中的男生数量”。假设该表共有 100 行，优化器预估男生的比例为 50%。然而，如果这张表的数据来源于国防科技大学，实际选出的男生比例可能高达 98%，这就导致了统计信息推断上的误差。这类误差产生的主要原因有两个方面：一是统计信息本身的不准确，如前所述的抽样误差；二是引入了一些假设，比如假设数据是均匀分布的，或者假设不同字段之间不存在相关性等。因此，在统计信息的推导过程中，不仅原有的统计信息误差被保留，还额外引入了因假设不准确而导致的新误差。这些误差中，有的需要我们积极努力去消除，而有的则是特定应用场景下不可避免的。

要如何验证统计信息的推导是否准确呢？我们开发了一个名为 qError 的工具，它通过对比每个操作符预测的行数与实际执行时的行数，来检查推导的准确性。一旦我们生成了这些推导信息，下一步就是计算各个执行计划的真实代价，这一过程称为代价模型。在这一步中，必须考虑到查询引擎的特性、运行环境的差异等因素，比如是否更注重减少数据在网络中的传输，还是更关注机器内存的消耗，或者是 CPU 的利用效率等。不同的情况需要做出不同的权衡。因此，即便是在统计信息推导误差的基础上，代价模型还会引入新的误差。为了衡量代价模型的质量，我们推出了一款名为 Plan Ranker 的工具。无论是采用 Cascading 还是 DPhyper 动态规划方法，我们都会使用 Memo 来记录不同的执行计划。通过 Plan Ranker，我们可以提取出预计排名前十的执行计划，并通过实际执行来检验这些计划的效率是否与我们的预期相符。通过将实际执行后的计划序列与理论推断的计划序列进行比较，计算它们之间的距离，以此来评估代价模型的有效性。

最后，还有一个“游戏规则改变者”——Runtime Filter，它的出现彻底改变了我们对 join 顺序优化及整体优化策略的传统认知。让我们通过一个简单的例子来理解 Runtime Filter 的作用及其对 join 操作的重大影响。假设存在一个订单表，包含订单号、商品ID及其他字段；同时还有一个商品表，记录了商品ID和品牌信息，其中每个品牌下有多个商品。现在，我们的任务是找出所有属于“华为”品牌的订单。首先，我们会对商品表进行过滤，筛选出品牌为“华为”的商品，然后将这些商品与订单表进行 join 操作。之前提到过，优化的核心目标在于尽早减少数据规模，因此在这种情况下，我们可能会产生一个想法。

假设从商品表中过滤出“华为”品牌对应的商品ID为 p001、p003，形成集合 A。是否可以将集合 A 发送给订单表，先依据商品ID对订单集合进行一次预过滤，这样原本6亿条的订单数据可能只剩下2400万条来进行 join 操作。这正是 TPC-H 中的一个典型场景，其数据比例也与此相似。通过这种方式，可以显著减轻最后一步 join 操作的负担，进而大幅提升整个查询的效率。起初，Runtime Filter 被视为优化器中规则的一种附加奖励，如果说优化器内的规则是“一等公民”，那么 Runtime Filter 就像是“二等公民”。然而，这位“二等公民”却以其独特的方式颠覆了我们对优化策略的传统看法。

让我们来看一个稍显复杂的例子。假设任务是找出位于亚洲的供应商（supplier），已知 supplier 表中包含 nation id，而 nation 表中又包含 region id（这里只考虑亚洲）。传统的处理方式是先将 supplier 表与 nation 表进行 join，然后再与 region 表 join。在 TPC-H 测试中，region 表涵盖了5大洲，nation 表则列出了25个国家，每个大洲恰好有5个国家。每个国家拥有一部分供应商，总计 supplier 表有1千万条记录，并且这些供应商在各个国家间均匀分布。相比之下，左侧的执行计划不如右侧的高效。右侧的方案首先从 region 表中筛选出亚洲，然后与 nation 表 join，这样就只选出了亚洲的5个国家。接着，再与 supplier 表进行 join，直接锁定了这5个亚洲国家下的2百万供应商。尽管左右两侧的执行计划都涉及两次 join 操作，但处理的数据量级却大相径庭。右侧的方案仅对1千万条数据进行了一次 join 操作，而左侧的方案却进行了两次。根据传统观点，右侧的执行计划显然远胜于左侧。接下来，我们将探讨为何 Runtime Filter 被誉为“颠覆者”。

推荐阅读系列文章

• 建议收藏 | Dinky系列总结篇 
• 建议收藏 | Flink系列总结篇 
• 建议收藏 | Flink CDC 系列总结篇 
• 建议收藏 | Doris实战文章汇总