这是ODPS有关SQL优化器原理的系列文章之一。我们会陆续推出SQL优化器有关优化规则和框架的其他文章。添加钉钉群“关系代数优化技术”（群号11719083）可以获取最新文章发布动态。
本文的目标是解释Join重排这个特性的基础概念和算法，如果想快速了解并在ODPS上使用这个特性，请直接跳到“总结”。
简介
Join重排是经典的SQL优化问题。考虑3个表的自然连接 A ⋈ B ⋈ C ，在不影响最终结果集的前提下，可以改变连接的顺序为下列：
A ⋈ C ⋈ BB ⋈ A ⋈ CB ⋈ C ⋈ AC ⋈ A ⋈ BC ⋈ B ⋈ A
熟悉SQL开发的读者会明白，这个顺序可能极大影响SQL执行的效率。打个比方，A，B，C的数据量各自是100条记录，如果A ⋈ C的数据量是1条记录，A ⋈ B是100条记录，显然A ⋈ B ⋈ C的效率低于A ⋈ C ⋈ B，因为前者的中间结果是100条记录，而后者是1条，并且最终结果的数据量是相同的。因此我们得到结论1。
结论1：Join的顺序影响中间结果的数据量，决定了Join的执行效率另外一种影响Join效率的原因是Join算法。考虑Hash Join算法（对ODPS熟悉的读者可以理解为MapJoin），它提前把右边表的数据建立一张哈希表，循环获取左边表的记录查表做Join。假设建立哈希表的代价很大，且随数据量线性递增，那么我们总希望更小的数据集在右边。假设A表是100条记录，B表是10条记录，那么A ⋈ B优于B ⋈ A。因此我们得到结论2。
结论2：Join的顺序影响具体Join算法的效率，决定了Join的执行效率综上所述，Join的顺序很大程度决定了Join的执行效率。这么看来，在开发SQL程序的时候，我们一定要仔细安排Join的顺序，让它达到最优的执行效率？不尽然。事实上，Join重排的难度如此之大，以至于手工调整是不现实的。主要的难度体现在两部分：
- 穷举和验证最优方案的算法复杂度是指数级的（NP hard问题）
- 获取某个Join的中间结果数据量的代价很大。我们不得不实际执行一遍Join才能获知中间结果数据量，每个Join都可能花费数小时甚至数天。
因此必须借助机器自动优化。在最新的ODPS SQL 2.0中，基于代价的优化器（Cost Based Optimizer，CBO）已经包含了Join重排的优化规则。在本文中，我们尝试从算法、代价计算、数据量估计等方方面面解释Join重排，也会包含一部分CBO的基本概念。
问题分类
Join树
在SQL优化器程序中表达的Join大部分时候是一棵二叉树。把Join节点作为二叉树的节点，可以构建一棵Join树。
例如，上述的A ⋈ B ⋈ C生成的逻辑执行计划（Algebrized Tree）如下：
生成的Join树如下：
至此一切都很完美，每个查询都是树，直到有一种奇怪的查询闯进了这个森林。考虑以下Join：
SELECT * FROM A JOIN B ON A.id = B.id JOIN C ON B.id = C.id显然，通过A.id = B.id and B.id = C.id可以推出另一个Join，即C.id = A.id，这时的Join"树"是这样的：
这种形态称为__有环__的Join树。有环在Join重排算法里会非常复杂，大部分的算法不支持环。当然我们可以考虑随机删除某个Join操作，保证整个Join树__无环__，但是这么做会损失一些优化的可能性。
Join树形态
上文提到的Join树在SQL的逻辑表达中通常是一个__偏树__。考虑A ⋈ B ⋈ C ⋈ D，这棵偏树的形态如下：
我们称这种Join树为__左深（Left-deep）树__，对应的也有__右深树__。在单机／单任务数据库上，我们只考虑这种形态的Join树就可以做Join重排，但是在分布式环境，我们还要考虑__稠密（Bushy）树__，如下图所示：
显然，如果有更多计算节点，AB和CD可以并行执行，从而降低整体响应时间。大部分的Join重排算法只能支持左深树，我们会在后续提到稠密树的增强算法。ODPS SQL 2.0支持了稠密树的重排算法。
笛卡尔积
区别于自然连接，笛卡尔积将两边的输入做两层循环的完全展开。部分Join重排算法不支持笛卡尔积。
综上，我们有“有／无环”，“左深／稠密树”，“支持／不支持笛卡尔积”这三类8种问题分类。
动态规划算法
终于到了Join重排算法了！希望之前的概念解释没有吓跑你。首先看__动态规划算法__，这是一个非常自然的Join重排算法，它最早是由P. Griffiths Selinger etl在1979年提出 [Selinger79]，并使用在数据库鼻祖级的系统System R上。
动态规划保留所有可能的Join顺序，加入到CBO的执行计划选项（被称为Memo的一个数据结构）中，最后由代价模型选择最优的Join顺序。为了避免代价被反复计算，使用动态规划的算法记录局部最优的代价。
这是一种穷举（exhaustive）算法，但是我们通常提到的Join重排都不是穷举算法，因为它的复杂度实在是太高了！考虑n个输入自由组建一棵左深树或稠密树的所有可能性，它的复杂度是卡特兰数序列，下表是一个直观的例子：
输入数 n |
左深树 2^(n−1) |
稠密树 2^(n−1) * C(n − 1) |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 2 |
| 3 | 4 | 8 |
| 4 | 8 | 40 |
| 5 | 16 | 224 |
| 6 | 32 | 1344 |
| 7 | 64 | 8448 |
| 8 | 128 | 54912 |
| 9 | 256 | 366080 |
| 10 | 512 | 2489344 |
在ODPS中，我们最初利用了这个算法，因为它在理论上总能找到最优解（区别于后续我们提到的算法，理论上只能找到次优解），并且支持稠密树和笛卡尔积。为了降低它的复杂度，我们用了一些限制：
- 不区分
A ⋈ B和B ⋈ A（交换） - 仅处理n<=5的情况，当n>5时，分裂为多个n<=5的组分别做Join重排
截止本文，ODPS线上仍然使用以上限制的动态规划算法。你可以通过set odps.optimizer.cbo.rule.filter.white=pojr打开Join重排。但是，正如我们看到的，这个算法复杂度非常大，限制也非常多。我们在最新未发布的版本使用了启发式算法替换它。
启发式算法
为了降低动态规划算法的复杂度，我们必须在Join重排算法上就开始做剪枝，而不是把所有可能性都留下来。需要解释的是，启发式算法同样是建立在动态规划算法上的一种优化，而不是独立的自成一套。
既然要“启发”，就需要一个定义什么是__好__的Join。我们需要引入一个评估体系，被称为cost function（如果读者对CBO熟悉，这里的cost不是指CBO框架的代价，而仅仅是用于评估Join顺序好坏的一个公式，因为此时Join并没有build，我们无法获取准确的cost）。为了简化问题，接下来我们使用的cost function都等于Join的输出数据量（cardinality。有关cardinality的估计算法是另一个大话题，留到下一篇文章解释，此处请读者先假定我们有能力获取一个精确的cardinality）。选择执行计划的准则就是选择cost最小的那个。
最重要的启发式算法有贪婪算法和GOO算法两种。ODPS采用了增强的GOO算法。
贪婪算法
贪婪算法考虑逻辑执行计划，以输入为节点，每次选取cost最小的节点直到所有节点都被选取，从而组建一个左深树作为最后的Join重排顺序。贪婪算法只支持左深树。
最基础的贪婪算法的伪代码如下：
ø = {所有输入}
orders = {}
while ø != {}
n = ni of min(cost(orders ⋈ ni)) for ni in ø
orders = orders + n
ø = ø - n
return orders实践中，这个算法很容易受到第一个输入选择的影响，因为首次选择节点，cost({} ⋈ ni)，还没有任何Join，这个cost被定义为ni的cardinality，小表会优先选择，这并不一定是最好的。因此一个改进的算法是在首次选择时，所有表都有机会，伪代码如下：
ø = {所有输入}
options = {}
for n in ø
orders = {n}
rest = ø - n
while rest != {}
n = ni of min(cost(orders ⋈ ni)) for ni in ø
orders = orders + n
ø = ø - n
options = options + orders
return i of min(cost(i)) for i in options贪婪算法的好处是，它每次选择的一个Join都是可以实际执行的（区别于下文的GOO算法，选择的可能是一个中间Join），因此我们很容易计算cost。和所有的启发式算法一样，它只能获得次优解。考虑到它不支持稠密树，我们没有选择这个算法。
GOO算法
区别于贪婪算法以输入为节点，GOO（Greedy Operator Ordering）考虑Join树，以Join为节点。它循环选择一个节点，和已选择的所有节点尝试Join并选择代价最小的那个，生成一个新的节点，直到所有的节点都被选择了。
考虑A ⋈ B ⋈ C ⋈ D的例子，如果cost的估计结果是 A ⋈ B < C ⋈ D < B ⋈ C，GOO算法的执行过程如下图所示：
这个算法的复杂度比贪婪算法高，cost估计从实体的输入改为抽象的Join，难度更大，但是它的优势在于支持稠密树。ODPS最新的版本使用了这种算法。
KBZ算法
KBZ或IIKBZ是在cost function满足ASI（adjacent sequence interchange）条件下理论最优的启发式算法。因为ODPS无法满足ASI，且KBZ仅支持左深树，我们没有考虑KBZ算法。感兴趣的读者可以参考 [Ibaraki84]。
随机算法简介
我们之前讨论了动态规划算法，也讨论了启发式算法。这两种算法是两个极端，前者保留所有的Join形态，后者只保留唯一的Join形态，这是算法复杂度和最优解之间的tradeoff。实际操作中，这两个极端通常不是好的策略，我们希望有更折中的办法，这就是__随机算法__。
Random Walk算法 是最基础的随机算法。在次优解的基础上随机改变一些排序，尝试查找更优的方案。__Iterative Random Walk算法__ 做了改进，避免Random Walk生成的环。
折中的考量最后回到了基本的最优化问题上。数学上的一些算法也被应用于Join重排，讨论比较多的包括 模拟退火算法 和 基因算法 [Steinbrunn]。
扩展问题
稠密树偏好
像ODPS这样的分布式系统下，我们更偏好生成稠密树，因为分布式系统可以并行执行那些在树中同深度的Join。怎样表达这样的偏好是一个难题。
在我们的实现中，我们对cost function施加一个深度的惩罚（例如，每一级深度施加30%的cost惩罚），我们通过“深度厌恶”这个想法来表达“稠密树偏好”。
Join 分组
在现实中，某些Join可以被合并在一个分组里实现。如果读者熟悉ODPS，容易理解有两类分组：
- 对于Sorted Merge Join，当参与Join的每一路输入，Join key都是相同的，可以在一个task完成。
- 对于Map Join，当大表是相同的，可以在一个map里完成。
显然，Join分组很大程度影响了代价，从而影响了最优顺序。我们在Join重排的实现会保留两种optional plan：合并的方案和不合并的方案，留给CBO框架去选择最优方案。
总结
这篇文档中，我们解释了Join重排这一优化的意义、概念和经典的几种算法。
- 动态规划的算法总能找到最优方案，但是复杂度是最高的。
- 启发式算法的复杂度最低，只能找到次优解。
- 随机算法的效果是上面两种算法的折中。
ODPS最新的算法使用了启发式的GOO算法。在线上运行的ODPS还在使用受限的动态规划算法。从经典的数据仓库测试集TPC-H的测试发现，使用受限的动态规划算法可以帮助我们获得额外的8%以上的性能提升。
Join重排是一个较激进的优化规则，考虑到CBO无法完美估计数据量（这在我们的后续文章中解释），打开这个规则可能会产生worst plan。这个worst plan的比例经过我们线上实测是非常低的，但是我们仍然不得不默认关闭Join重排规则，你可以尝试设置odps.optimizer.cbo.rule.filter.white=pojr来打开某个query或project的Join重排特性。
索引
[Selinger79] Selinger, P. G., Astrahan, M. M., Chamberlin, D. D., Lorie, I. A., Price, T. G., Lorie, R. a., … Price, T. G. (1979). Access path selection in a relational database management system. ACM SIGMOD International Conference on Management of Data., 23–34. https://doi.org/10.1145/582095.582099
[Ibaraki84] Ibaraki, T., & Kameda, T. (1984). On the optimal nesting order for computing N-relational joins. ACM Transactions on Database Systems, 9(3), 482–502. https://doi.org/10.1145/1270.1498
[Steinbrunn] Steinbrunn, M., Moerkotte, G., & Kemper, A. (n.d.). Optimizing Join Orders, 1–55.
