一、重塑
过去一年是 Doris 商业化的元年，遇到了很多新的场景和挑战。在这些挑战中，我们发现老优化器有很多问题。首先是缺少优化规则的抽象。有些规则并不适用于所有的场景，对某些场景，有些规则有帮助，有些规则没有帮助。因为缺少规则的抽象，不方便细粒度控制规则的使用，给 query 的调优带来很大麻烦。同时，为了适应更多的数据场景，需要增加新的规则。添加规则的成本，除了实现规则本身，还要让规则融入优化器，这就带来很多额外的成本。最后，老优化器不方便我们观察一个规则究竟给 plan 带来了怎样的变化。
除了优化规则的抽象，还有一个更重要的问题是我们缺少 CBO 的框架。老优化器缺少统计信息收集的能力。代价模型代码也零散的分布在整个优化器中。所以只能做一些很简单很有限的 CBO 的规则。如果拿到复杂的 query，基本只会生成一个左深树。
最后优化器本身的架构，基本只是做树的两轮遍历。这对优化规则的有很大限制。
于是在去年，Doris 决定做一个新的优化器。从此拉开了新优化器的序幕。
经过来自美团、百度、小米、腾讯、京东、SelectDB 等公司的工程师们 400 多天的努力工作后，我们的优化器终于与大家见面了，我们会在 Doris2.0 的时候正式推出。在前面的研发过程当中，我们也在不断做测试。比如在 SSB、TPCH 500G/1T 这些测试中，我们都超过了由专家人工改写的 SQL。也就是说，即使是经验丰富的 DBA 用老优化器改写的 SQL 仍然比新优化器自动生成的 plan 要差一些。图中是我们测试的对比，大多达到了 50% 以上的提升。同时为了检验泛化能力，在用户 POC 测试中，超过 10 个测试使用了新优化器，在这些测试中，新优化器为用户减轻了很多负担，SQL的调优的工作几乎都是自动完成。
二、优化的本质
下面从 SQL 的本质来讲解一下优化器的地位。
首先，SQL 的本质是一个描述性的语言，用户只需要描述需要的数据是什么，数据怎么拿到是由优化器决定的。可以说执行引擎是车的发动机，优化器是车的方向盘，如果没有一个正确的优化器，越强劲的引擎只会让我们以越快的速度撞到内存溢出的南墙上面。所以优化器是 SQL 中最有特色的部分。
优化器在一条 SQL 的旅程中处于什么位置呢？如上图中所示，它处于红框范围内。一条 SQL 首先经过语法解析，生成抽象语法树，然后进行语义分析后，第一阶段对逻辑计划进行改写，改写中会引入很多规则。改写完成后，会生成多个候选的 plan，通过代价模型估计，从中挑出一个最优的执行计划，交给查询引擎执行。Nereids 优化器主要是指改写查询计划、优化查询计划两部分。
具体来说，改写的部分称之为 RBO，代价估算称之为 CBO，为了和之前的优化器、执行引擎兼容，还需要“plan 翻译”才可以把新优化器生成的 plan 转换成 BE端可理解的查询计划。
在 RBO 规则中，包括了：谓词下推、表达式改写、常量折叠、消除空算子等等。这些规则一般来说会提高查询的效率。所以这些规则生成的 plan 会替代输入的 plan。有时一组规则会反复使用，知道 plan 不再变化为止。
当 RBO 改写完成后，生成的 plan 作为 CBO 阶段的输入。CBO 阶段最主要的任务是决定 join 的顺序。因为 join 的顺序对 plan 的影响是非常大的。除了 join 顺序的选择，还有许多需要代价估算的点：包括 CTE，即一些 with 语句生成的 view，是单独算出来还是嵌入到 SQL 中；还有聚合选用哪一种策略，是一阶段还是两阶段、三阶段做甚至四阶段做。这些都是 CBO 阶段做的事情。
上面讲了很多优化规则，其核心思想就是让 SQL 执行更快。但是就像做科学研究，定义好一个问题比解决问题更有价值。怎么叫定义好一个问题？就是需要找到一个好的指标来衡量这个问题。如果我们用查询的时间来衡量，这是一个正确但是无用的指标。所以根据我的理解，应该将这个问题定义为：尽早降低数据规模。下面我们从这个角度来审视优化的规则。
用一个简单的例子来看。上面是一个 TPC-H 的例子，我们做了改写。描述的是有很多订单，订单的买方和卖方都有国籍，我们需要选出中国和美国之间贸易往来的订单，生成下面的表格。
理解了这个 SQL 的做法，我们就能够理解优化器在其中做了什么事情。根据条件：（卖方的国籍=中国，并且买方的国籍=美国）或者（卖方的国籍=美国，并且买方的国籍=中国）表示中美之间往来的订单，这个条件无法拆开，一个最自然的做法是把 orders 表和 customer表先 join，然后和 supplier 表 join，再和 nation join，最后做过滤。这是第一种做法，效率比较低。
好一些的做法是，既然挑出的是中美之间的贸易，那么可以推导出一个条件：customer 只选出中国或美国的 customer，supplier 只选出中国或美国的s upplier，这就是我们优化器所做的一个优化，我们会推导出一些看似冗余的条件，但这些条件作用非常大，可以帮助我们尽早将 customer 和 supplier 的数据规模降低。数据规模降低再来与 orders 表做 join 时，右表的数量就不再是全体 customer，而只是 customer 的一部分。再和 supplier 做 join 时，右表的数量也只是一部分的 supplier，左表的数量也不是全体的 order，而只是 customer 是中国或美国的 order，所以对这个 join 来说，也降低了数据量。这两个 join 在 TPC-H 查询中的性能提高是非常显著的，有 2-3 倍的提升。这里的核心思想就是尽早把数据规模降低。希望这个例子能帮大家理解我们的优化器殚精竭虑想要达到的目的。
除了上面的方法，还有一个更重要的降低数据规模的途径是：调整 join 的顺序。在事实表和维度表做 join 的时候，往往维度表会有一些过滤条件，会对事实表有很强的过滤效果。但是这时候又面临一个问题：我们知道 join reorder 是一个 NP的问题，当表的数量增加时，候选 plan 会呈几何级数增长。这么多年来，这个问题没有特别创新的突破，NP 问题一般只能通过动态规划的方法，找一些次优的解。我们现在看到的所有方法，都是动态规划不同的应用，比如有：DPSize、DPSub、DPhyper、Cascading......我们的新优化器 Nereids 上面，同时采用了两种动态规划的方法，基础的有 Cascading 方法，同时也加上了 DPhyper 的方法，两者相互补充。
三、优化瓶颈
艰苦奋战了大半年后，系统基本成型。接着就开始关注性能。
第一个很重要的性能提升来源于 RBO 阶段的一次重要重构。Cascading 框架有一个 Memo 结构，相当于一个小账本，所有规则产生的 plan 都用 Memo 记下来。这是CBO阶段执行动态规划算法所需要的。我们知道所有动态规划方法都有小账本，在 Cascading 中的小账本就叫做 Memo。我们一开始就像论文中的流程一样，将 plan 放在 Memo 中，对plan进行改造时再从 Memo 中把 plan 片段取出来，这个过程叫 copyIn，copyOut。RBO 阶段，总是用一个新的 plan 来替代老的 plan，我们仍然遵循老的套路，每次生成新的plan，就放入 Memo 中，进行下一个规则替换时，再将这个 plan 从 Memo 中拿出来。反复 copyIn，copyOut 的动作其实是多余的。于是美团的华建老师闭关好几周，给大家提交了一个巨大的pr，RBO 的效率得到了飞速的提升。当然我们也很痛苦，因为需要重新看一遍RBO 的所有代码。但我们非常欢迎有越来越多这样的痛苦。
RBO 阶段有了一个性能的飞跃之后，CBO 阶段的性能问题就凸显出来了。于是我们团队里的 ACM 冠军，莫琛辉同学出场了。在那几个星期里，他分析了上百个火焰图，改写了好几轮代码，最终将很多秒级的分析时间压缩到 20 毫秒左右。如果将来你也需要实现一个 cascade 矿建，那么 CostAndEnforce 部分的性能调优一定值得深入挖掘。
四、挑战
下面再介绍下开发过程中所面临的各种各样的挑战。这部分可能是介绍中最有意义的部分。
第一个问题就是公平与效率的平衡。这个问题的本质是，做 join reorder 时候，希望找出做好的 plan，但是这是个 NP 问题，这就意味着我们一定要做裁剪，不可能公平地给每个可能的 plan 检验的机会，有一些plan未经检验就直接被淘汰掉了。最简单的树结构是 Left Deep Tree。这种树，一般大表放在最左边，隐含了一个假设：我们现在做的都是 hash join，用右表 build hash table, 左表做probe。因为一行数据构建hash table的成本远远高于探测 hash table 的成本，所以要把成本高的计算放在行数少的表上做，单行成本低的计算放在行数大的表上做。这就是最基本的思想。所以构造出一个左深树，把最大的表（事实表）放在最左边，依次把小表（维度表）放在右边，和大表 join。这个方法的优点是搜索空间小（比后面两种小很多），因此优化器的执行就会快。但是这样往往会错过很多优秀的执行计划，让引擎端的负担太大。一个更好的平衡是 ZigZag Tree。它背后的思想是：当大表和小表 join 后，得到的结果可能数据量比较小，再和另外的表join 时，可能就需要放在右边，于是生成了中间所示的执行计划，每一步都去需要判断左表和右表谁大谁小，就得到了 ZigZag Tree。如果将搜索空间再扩大一点，称之为 Bushy Tree，就是把所有的二叉树都放进来考虑，Bushy Tree 的搜索空间因此会暴涨上去。当表的数量太多时，就会导致优化器执行时间超过了执行引擎的执行时间。所以很多情况下，不能搜索整个空间的 Bushy Tree。
这里有一个基于表数量和 Left Deep Tree、ZigZag Tree、Bushy Tree 增长幅度的估算。在实际实践当中，当表的数量较少时，会采用 Cascading，优势是可以把除了 join reorder 外的各种 rule 和 join reorder 混合使用。但是效率不是太高，所以当表的数量较多时，会切换到 DPhyper 上去。
第二个挑战是我们始终与误差共存。与误差共存不代表我们不去努力消除误差。先来看看误差是怎么产生的。刚才说要做 join reorder，这步需要很多的统计信息，需要估算每次 join 的结果有多少行，经过过滤有多少行等。所以第一个误差是统计信息，误差来源是抽样。比如计算某个字段不同值的个数（distinct），称之为NDV(number of distinct values)，不可能全量做真实计算，一般会使用抽样的方式，就会带来误差。
对表里数据统计后开始计算，比如一张表里有学生信息，有过滤条件：选出其中男同学数量。假设表有 100 行，优化器估计选中男同学数量为 50%，但如果表来自国防科大，可能选出男同学数量占 98%，就会导致统计信息的推导出现误差。在这些例子中，误差产生的主要原因一是统计信息有误差，二是加入了一些假设，比如假设数据均匀分布，假设字段之间没有相关性等。所以统计信息推导时候，在统计信息误差基础上，又加入了一些误差。这些误差中，有一些是需要努力消除的，有一些是特殊应用场景引入的。
如何检验统计信息的推导是否准确呢？我们开发了一个工具叫 qError，它会把每个算子推导的行数和实际执行的行数做比较计算，来检验推导是否准确。当我们把推导信息也做出来后，就开始计算各个 plan 真实的代价，这一步称为代价模型。这部分需要考虑引擎的特点，环境的差异等，要看更需要减少数据在网络的传输？还是更看重机器内存的代价，或是 CPU 的代价等。不同情况要做不同的权衡。所以代价模型在统计信息推导误差的基础上，又会有新的误差。如何衡量代价模型呢？我们推出了 Plan Ranker 工具。不管是 Cascading 还是 DPhyper，都是动态规划方法，我们都加入了 Memo 记录不同的 plan。我们可以取出认为排名前十的 plan，实际执行中，他们的效率是否和我们预期的排序是一致的呢，可以通过实际执行来检验。将检验后的 plan 序列与推断的 plan 序列进行距离计算，来衡量代价模型的好坏。
最后，还有一个“颠覆者”。它的出现颠覆了我们对 join reorder 以及做优化时的很多认识。先用一个简单的例子来理解下 Runtime Filter，它对我们做 join 时有非常大的影响。假设有一个订单表，有订单号、商品id和其他字段。还有一个商品表，有商品 id、品牌，一个品牌下有多个商品。现在要找出“华为”这个品牌下的订单。首先对商品表做过滤，找出品牌“华为”的商品，然后和订单表做 join。刚才我们说过，优化的目的是要尽早降低数据规模，那么这时候会有个想法。
假设商品表过滤出“华为”品牌的商品 id 是 p001、p003，作为集合 A，是否可以把A发送给订单表，先用商品 id 对订单集合做一次过滤，过滤后 6 亿条数据只剩2400 万条做j oin。这个是来自 TPC-H 里的典型场景，数据比例也是这样。这样就可以大大降低最后一步 join 的负担，提高整个查询的效率。本来 Runtime Filter 一开始的出现被认为是额外的 bonus，如果优化器里的规则是一等公民的话，它就是二等公民，可是这个二等公民颠覆了我们的想法。
换一个稍微复杂的例子。假设需要找出亚洲的 supplier，supplier 有 nation id，nation id 有 region id（这里只选出亚洲）。supplier 先和 nation join，再和 region join。在 TPCH 里，region 有 5 大洲，nation 表有 25 个国家，每个洲5 个国家。每个国家有一些供应商，supplier 表有 1 千万条数据，并且每个国家的 supplier 是均匀分布的。左册的破烂相对右侧 plan，就不够高效。右边首先选出亚洲，和 nation 做 join，这样只选出亚洲的 5 个国家，再和 supplier 做 join，就直接选出了亚洲国家的 2 百万 supplier。可以看到，左表和右边都有两个 join，但是处理的数据量级是不一样的。显然右边处理的数据量级小了很多。因为 1 千万的数据 join，右边只做了一次，而左边做了两次。传统观点下，右边plan 是远远优于左边 plan 的。下面就会看到为什么将 Runtime Filter 称为颠覆者。
颠覆效果是这样的。左边是我们刚才认为优秀的 plan，右边是认为不优秀的plan。但是加上 Runtime Filter 后，右边因为 region 只选择亚洲，所以会把亚洲的 region id 发送给 nation，于是 nation 表在扫描时候只会取出 5 条数据，因为 nation 表通过 Runtime Filter 做了过滤。Nation 表过滤后，会生成下一个Runtime Filter，把5个国家的 id 发送给 supplier，于是 supplier 表直接过滤出2 百万数据出来。如果采用右边的 plan，参与 join 的数据规模就没有出现过1千万。这样，右边执行反而更占优势。而且可以看到，除了 join 以外，它对延迟物化也非常有帮助。在 Doris 存储层里，除了要取 key 字段外，还要取很多其他字段。Doris是 列存数据，当把 nation 表过滤出的 5 个 id 发送给 supplier 以后，supplier 上其他字段的访问数据量也会减少，我们把这称为延迟物化。像左边这样，supplier 其他字段都需要读取出来。而在右边情况下，可以通过 index，只需要点查取出相关的行。所以，有了 Runtime Filter 加持后，右边的 plan 反而比左边更有效了。但是 Runtime Filter 又有不确定性，因为无法确定 Runtime Filter 有多高的过滤率，这个依赖统计推导。同时，可能因为 Runtime Filter 等待时间过长，导致整个查询时间变长。如果要实现刚才那种理想的运行效果，supplier 扫描必须要等到 region 扫描完成，nation 扫描完成，才能得到有效的Runtime Filter。假设 region 扫描变慢了，nation 没有等到 region 的扫描结果，直接生成 Runtime Filter 交给 supplier，其实没有任何过滤效果。所以Runtime Filter 的过滤效果比较动态，这给查询优化带来非常大的挑战。这也是我们下一步要去解决的重要问题。
五、问答
1、CostAndEnforce 在优化器优化的思路是什么？
打出火焰图，找出热点，分析热点部分有没有做重复计算，比如有没有做重复的统计信息推导，有没有重复计算 cost。通过火焰图，可以得到一些线索，更快找到从哪里分析出现的重复计算。
2、当过滤条件很多，或者非等值的条件下，Runtime Filter 效率是否会下降很多？
不会。如果对右表有越多的过滤条件，Runtime Filter 效率会越高，因为对左表的过滤性会更强。如果没有等值条件，不会生成 runtimeFilter
3、Runtime Filter 对 left join 是否有优化效果？
对 left outer join 没有优化效果。因为不能在左表的扫描端把数据过滤掉，因为左表不管能否跟右表匹配，都需要把数据输出。所以 left outer join 不能运用Runtime Filter。
4、Doris 支持分页查询么？
分页查询支持。
5、左表等 Runtime Filter 要等多久？
这是经验参数，我们默认等 1 秒。
6、优化器以后可以交给 AI 吗？
DB for AI 是一个新的研究方向。几十年来，优化器我觉得没有本质的进展，都是拿着同一件武器——动态规划，只是打的不同的拳法。可能 AI 是一个新的武器，但是目前还没有看到特别的效果，特别是 ad-hoc 查询中。
