本文具体讨论了Join基础算法的一种优化方案 – Runtime Filter，在本文最后还引申地聊了聊谓词 下推技术。同时，在本文文章开头，笔者引出了两个问题，SQL执行引擎如何知晓参与Join的两波数据集大小？衡量两波数据集 大小的是物理大小还是纪录多少抑或两者都有？这关系到SQL解析器如何正确选择Join算法的问题。好了，这些就是这篇文章要为 大家带来的议题－基于代价优化（Cost-Based Optimization，简称CBO）。
CBO基本原理
提到CBO，就不得不提起一位’老熟人’ – 基于规则优化（Rule-Based Optimization，简称RBO）。RBO是一种经验式、启发式 的优化思路，优化规则都已经预先定义好，只需要将SQL往这些规则上套就可以。说白了，RBO就像是一个经验丰富的老司机，基 本套路全都知道。
然而世界上有一种东西叫做 – 不按套路来，与其说它不按套路来，倒不如说它本身并没有什么套路。最典型的莫过于复杂Join算子 优化，对于这些Join来说，通常有两个选择题要做：
1. Join应该选择哪种算法策略来执行？BroadcastJoin or ShuffleHashJoin or SortMergeJoin？不同的执行策略对系统的资源要求 不同，执行效率也有天壤之别，同一个SQL，选择到合适的策略执行可能只需要几秒钟，而如果没有选择到合适的执行策略就可能 会导致系统OOM。
2. 对于雪花模型或者星型模型来讲，多表Join应该选择什么样的顺序执行？不同的Join顺序意味着不同的执行效率，比如A join B join C，A、B表都很大，C表很小，那A join B很显然需要大量的系统资源来运算，执行时间必然不会短。而如果使用A join C join B的执行顺序，因为C表很小，所以A join C会很快得到结果，而且结果集会很小，再使用小的结果集 join B，性能显而易见会好于 前一种方案。
大家想想，这有什么固定的优化规则么？并没有。说白了，你需要知道更多关于表的基础信息（表大小、表记录总条数等），再通 过一定规则代价评估才能从中选择一条最优的执行计划。CBO意为基于代价优化策略，就是从多个可能的语法树中选择一条代价最 小的语法树来执行，换个说法，CBO的核心在于评估出一条给定语法树的实际代价。比如下面这颗SQL语法树：
要评估给定整棵树的代价，分而治之只需要评估每个节点执行的代价，最后将所有节点代价累加即可。而要评估单个节点执行实际 代价，又需要知道两点，其一是这种算子的代价规则，每种算子的代价计算规则必然都不同，比如Merge-Sort Join、Shuffle Hash Join、GroupBy都有自己的一套代价计算算法。其二是参与操作的数据集基本信息（大小、总记录条数），比如实际参与 Merge-Sort Join的两表大小，作为节点实际执行代价的一个重要因素，当然非常重要。试想，同样是Table Scan操作，大表和小 表的执行代价必然不同。
为给定算子的代价进行评估说到底也是一种算法，算法都是死的，暂且不表，下文详述。而参与的数据集基本信息却是活的，为什 么如此说，因为这些数据集都是原始表经过过滤、聚合之后的中间结果，没有规则直接告诉你这个中间结果有多少数据！那中间结 果的基本信息如何评估呢？推导！对，原始表基本信息我们是可以知道的，如果能够一层一层向上推导，是不是就有可能知道所求 中间结果信息！
这里又将任意节点中间结果信息评估拆分为两个子问题：首先评估叶子节点（原始表）的基本信息，其次一层一层往上推导。评估 原始表基本信息想想总是有办法的，粗暴点就全表扫描，获取记录条数、最大值、最小值，总之是可以做到的。那基本信息如何一 层一层往上推导呢？规则！比如原始表经过 id = 12这个Filter过滤之后的数据集信息（数据集大小等）就可以经过一定的规则推导 出来，不同算子有不同的规则，下文详述！
1. 基于代价优化（CBO）原理是计算所有执行路径的代价，并挑选代价最小的执行路径。问题转化为：如何计算一条给定执行路径 的代价；
2. 计算给定路径的执行代价，只需要计算这条路径上每个节点的执行代价，最后相加即可。问题转化为：如何计算其中任意一个节 点的执行代价；
3. 计算任意节点的执行代价，只需要知道当前节点算子的代价计算规则以及参与计算的数据集（中间结果）基本信息（数据量大 小、数据条数等）。问题转化为：如何计算中间结果的基本信息以及定义算子代价计算规则；