1 概述

对于数据库来说，其中俩个核心的模块是：优化器和执行引擎。优化器负责给执行引擎提供输入，它接收来自 SQL Parser 解析好的 AST 树，然后需要从所有可能的计划中选择代价最优的计划提供给执行引擎。基于代价的优化器本质上是一个复杂的搜索问题，想要解决好这个问题，需要从四个方向入手：

1）搜索框架： 既然是搜索问题，那么就需要一个搜索框架来承载这个问题。从数据库的发展历程来看，基于 Cascades 的搜索框架已经成为了业界标准，包括商业数据库 SQL Server 以及开源数据库 GP/ORCA 都采用 Cascades 实现。AnalyticDB CBO 也是基于 Cascades 论文实现的。

2）分布式并行计划： 相对于传统的单机版数据库，AnalyticDB 是一个分布式 MPP 数据库，优化器生成的计划是一个分布式并行计划。因此需要把分布式并行计划的生成和搜索框架结合起来，基于代价选择最佳的分布式并行计划。

3）代价估算： 代价估算是优化器能否寻找到最优计划的关键因素，代价估算做不好，优化器不可能做好。代价估算涉及到统计信息的推导和代价模型。统计信息的推导依赖于：原始表的统计信息、中间算子的推导算法、对数据的各种假设（均匀性假设、独立性假设、包括性假设、包含性假设）以及在一些极端情况下的猜测。因此统计信息的推导存在大量的不确定性，也正是因为这些不确定性，极大的加剧了优化器寻找最优解的难度。

4）统计信息收集： 收集必要的统计信息是 CBO 工作的前提，CBO 和统计信息之间的关系犹如一把枪和弹药之间的关系，枪再好如果没有充足的弹药的话，那么无异于巧妇难为无米之炊。统计信息需要做到：基本信息能够自动化收集，自动化更新，高级统计信息可以手动收集，为 CBO 提供可靠的、多维度的统计信息。

2 架构

搜索框架 搜索框架在整个 CBO 中处于非常中心的一个位置，它会调用 Property Enforcement 框架，生成分布式执行计划，然后调用代价估算模块，给每一种候选分布式执行计划评估代价，最终基于代价选择最优的分布式执行计划。搜索框架包括以下几个部分：

Memo 表示搜索空间：对于一个查询计划来说，首先需要把它初始化，形成初始化的搜索空间。随着搜索的进行，搜索空间会不断扩充。由于搜索空间会非常庞大，因此 Memo 需要做到高效存储。

Search 表示搜索算法：搜索算法由三部分组成，第一部分用于递归遍历搜索空间，第二部分用于调用展开规则产生新的等价候选计划，扩充搜索空间，第三分部用于用于推导分布式计划的属性要求并计算代价值，进而寻求最优的分布式执行计划。

Scheduler 表示调度搜索算法的调度器：在当前的 AnalyticDB CBO 版本中，基于单线程和栈实现：把搜索任务压入到一个栈中，然后循环取栈中的任务去执行，直到任务结束。

考虑到其他开源优化器产品，例如 ORCA 提到了多线程并行搜索的理念，我们预留了多线程调度器的接口，相对于优化器众多棘手的问题来说，它的优先级并不是那么高，实现并行搜索的好处是非常明显的，它可以显著降低任务调度的执行时间，充分发挥多核并行的能力，从整个查询的角度来看，可以缩短查询优化的耗时，从而降低整体查询的耗时。但是并行搜索带来的线程同步问题，以及线程间依赖处理问题，挑战还是很大的。

Rule 表示展开规则：展开规则用于生成等价候选计划，等价候选计划会被放入到 Memo 中，形成完整的搜索空间。展开规则决定了优化器可以展开多少种候选计划，因此展开规则的种类，以及每种展开规则的算法效率对 CBO 来说也是至关重要的。展开规则种类越多，搜索空间就越完善，也就更有可能寻求到最优解，同时每种展开规则的算法越高效，生成完整的搜索空间就越高效，查询优化就越快。

分布式并行计划 相对于传统的单机版数据库来说，分布式 MPP 数据库给优化器带来了新的挑战。在分布式 MPP 数据库中，数据的分布属性变得十分的重要，它会直接影响到数据的正确性。为了满足不同算子对数据分布的要求，我们往往需要做数据重分布。

然而数据的重分布，也就是数据 shuffle 的代价非常昂贵，因此，在保证数据正确性的前提下，尽可能的减少数据 shuffle，可以大幅度提升分布式计划的执行性能。作为分布式 MPP 数据库优化器来说，需要把数据的 Partitioning 属性，以及 Sorting、Grouping 属性，也纳入到搜索空间来综合考虑，基于代价选择最优的分布式并行执行计划。

因此我们设计实现了一套完整的 Property Enforcement 框架，用于描述在分布式场景下，分布式计划对数据分布的要求。同时我们把 Property Enforcement 的过程和搜索框架无缝的结合在一起，实现了面向分布式 MPP 数据库的 CBO。

代价估算 代价估算是整个 CBO 质量好坏的关键因素，代价估算做的好，CBO 才有可能选择出最优的计划，它包括三个部分。

Statistics 用于描述原始表的统计信息。包括表级别的统计信息 Row Count，单个字段的统计信息：每个字段的 NDV 值（distinct 值），Max 值，Min 值，NULL 值，Histogram 值（分布信息，用于区间查询）, Count-Min Sketch 值(用于等值查询)，DataSize 值。这些统计信息我们把它归纳为基础统计信息，需要做到自动收集，自动更新。

同时考虑到多个字段之间的关联度、Functional dependency、数据的倾斜等这些因素对统计信息估算的影响，还会提供命令行工具，手动收集这些信息，对于这些需要手动收集的信息，我们把它归纳为高级统计信息，只有在必要的时候，才需要显示的手动收集。另外，对于一些复杂的 predicate，例如 like，那么即使收集了 Histogram 也无法支持这种场景，因此我们也会在运行时基于动态采样来获取对应的统计信息。

Stats Derivation 用于推导经过各个算子之后的统计信息。统计信息的推导依赖于原始表的统计信息，数学公式，对数据属性的假设（例如，数据的分布是均匀的，多列之间的选择率是没有相关性的），以及极端情况下，启发式的假设（例如对于一个用户自定义的 UDF，它的选择率只能给一个默认值）。

统计信息的推导的好坏对优化器来说至关重要，这也一直是学术界的研究热点。本质上来说，只有打破对数据属性的假设，才有可能使得统计信息的估算做到知其然知其所以然，然而打破这些假设，依赖于对原始数据的分析，生成更多维度的统计信息，必然也要付出更多的代价。

Cost Model 表示代价模型。代价模型的工作必须要建立在合理的统计信息推导的基础之上，否则它的意义不会很大。代价模型需要对实际的计算模型进行评估，把统计信息转换为可以量化的代价值，从而为优化器提供决策依据。

统计信息收集 Analyze 用于收集统计信息。对于商业数据库来说，为了提升用户体验，做到开箱即用，都致力于 Auto analyze，即统计信息收集的自动化，以及自动更新。但是收集本身也是有代价的，因此我们把统计信息分为俩类：基础统计信息和高级统计信息。

基础统计信息就是前面提到的：表级别的统计信息 row count，单个字段的统计信息：每个字段的 NDV 值（distinct 值），Max 值，Min 值，NULL 值，Histogram 值（分布信息，用于区间查询），Count-Min Sketch 值(用于等值查询)，DataSize 值。基础统计信息必须要做到自动化收集、自动化更新，否则很可能由于这些统计信息的缺失，导致优化器产生灾难性的计划。

同时为了提升优化器在复杂情况下的决策质量，还提供了一些高级的命令用于收集更加复杂的统计信息，例如可以收集 column group 的统计信息，来获取多个字段之间的关联度信息。高级统计信息需要手工触发收集，只有在必要的时候才会收集。

基于 Analyze 命令收集统计信息，无论是自动化收集，还是手工收集，本质上来说所，它都是一个独立的进程：Analyze 会调用 Data Profiling 任务，对原始数据进行分析，生成统计信息，并存储在 Metadata 库中。

考虑到实际情况下，可能存在一些非常复杂的查询条件，不管是基础的统计信息还是高级统计信息，都无法很好的对它做合理的估算，这个时候，dynamic sampling 动态采样就可以发挥它的价值，动态采样会实时下发采样，获取必要的统计信息，提升优化器的决策质量。

其次，动态采样也可以作为统计信息收集的一种兜底策略，当基础统计信息由于某些原因导致未收集的情况下，动态采样的存在可以避免优化器由于缺失统计信息而产生灾难性的计划。但是动态采样是在查询优化阶段同步阻塞执行的，因此它必然会增加查询优化的整体耗时，同时也会增加整个数据库系统的负载，因此我们严格限制动态采样的使用场景。

3 设计与实现

接下来我们会通过一个例子来展开搜索框架、Property Enforcement 框架、以及代价估算的设计与实现。

查询语句

这一个简化版的 TPCH q3，非常典型的三表 Join。其中 customer 表按照 c_custkey 进行分区，orders 表按照 o_orderkey 进行分区，lineitem 表按照 l_orderkey 进行分区。

SELECT
    l_orderkey,
    o_orderdate,
    o_shippriority
FROM
    customer,
    orders,
    lineitem
WHERE
    c_custkey = o_custkey
    AND l_orderkey = o_orderkey

查询优化

在进入到 CBO 之前，原始的执行计划如下图所示，customer 表和 orders 表先 Join，Join 的结果再和 lineitem 表 Join，然后输出结果。

进入到 CBO 后，首先需要把查询计划转换为 Group 和 GroupExpression，并初始化 Memo 搜索空间。可以看到共有 6 个 Group，每个 Group 都有一个 GroupExpression。Group 和 GroupExpression 都是搜索空间里面的重要概念，关于它的详细介绍可以参考：AnalyticDB Cost based Optimizer 搜索框架，这里不展开。

简单来说：对于逻辑等价的，可以产生相同结果的 Logical Expression 和 Physical Expression 的集合称为 Group，GroupExpression 则包括 Logical GroupExpression 和 Physical GroupExpression，每一种 GroupExpression 表示一种等价候选计划。

在这里，我们为了简化描述，只考虑 Join 的 Order，以及分布式 Join 情况下，Repartition Join 和 Replicate Join 这两种属性要求，对于 Join 的算法默认只考虑 Hash-join 物理实现。

其他算子：TableScan 和 Output 也默认只有一种物理实现。调度器调度搜索任务，执行搜索流程，扩展搜索空间。可以看到随着搜索算法的不断迭代，Memo 里面的 Group 和 GroupExpression 会新增：白色表示 Logical GroupExpression，灰色表示 Physical GroupExpression。

可以看到，在应用了 Join 的结合律之后，新产生了 Group7 和 Group8 这俩个 Group；同时应用了 Join 的交换律之后，Group5 和 Group3 里面新增了很多等价的 Logical GroupExpression；同样 Group7 和 Group8 里面也有等价的 Logical GroupExpression。

最终考虑俩种分布式 Join 实现：Repartition Join 和 Replicate Join，这样就生成了完整的搜索空间。

当整个搜索空间被完整的扩充出来之后，接下来需要调用 Property Enforcement 框架，对每一种物理执行计划，去 Enforce 必要的属性，从而满足分布式执行计划的要求，然后再调用代价估算模块，去计算每一种分布式计划的代价，并把代价最小的计划标记为最优解，也就是 Winner。当每一个 Group 的 Winner 都被计算出来之后，将每个 Winner 串接起来，就是最优的分布式执行计划。

关于 Property Enforcement 和代价估算的详情，可以参考下面这三篇文章，这里不展开。

• AnalyticDB Cost based Optimizer 分布式并行计划

• AnalyticDB Cost based Optimizer 代价估算

• AnalyticDB Cost based Optimizer 统计信息收集

下图中黑色意味着 Winner，表示的是在满足某种属性要求的情况下，代价最低最低的物理执行计划。

我们遍历每个 Group 的 Winner，将 Winner 串接起来，就形成了最优的分布式执行计划。

每一个 Winner 经过 Property Enforcement 之后，都会在必要的时候插入必要的 Exchange 节点，来满足分布式计划的属性要求，所以生成的分布式执行计划如下图所示。可以看到：首先 customer 表做了一个全表广播到所有节点，进而满足和 orders 表 Join 的要求，Join 之后的结果按照 order 表分布，orders 表和 lineitem 表数据分布本身就满足 Join 的要求，因此不需要插入 Exchange 节点，最终 Join 的结果要输出到 Output 节点，因此插入 Gather 节点，汇总到单节点。

• An Overview of Query Optimization in Relational Systems

• The Cascades Framework for Query Optimization

• Efficiency in the columbia database query optimizer

• Orca: A Modular Query Optimizer Architecture for Big Data

• Incorporating Partitioning and Parallel Plans into the SCOPE Optimizer

• Profiling Relational Data – A Survey