Join Reorder 算法简介

因此优化器需要实现一种决定 Join 顺序的算法。目前 TiDB 中存在两种 Join Reorder 算法，贪心算法和动态规划算法。

• Join Reorder 贪心算法：在所有参与 Join 的节点中，选择行数最小的表与其他各表分别做一次 Join 的结果估算，然后选择其中结果最小的一对进行 Join，再继续这个过程进入下一轮的选择和 Join，直到所有的节点都完成 Join。

以三个表 t1、t2、t3 的 Join 为例。首先获取所有参与 Join 的节点，将所有节点按照行数多少，从少到多进行排序。

之后选定其中最小的表，将其与其他两个表分别做一次 Join，观察输出的结果集大小，选择其中结果更小的一对。

然后进入下一轮的选择，如果这时是四个表，那么就继续比较输出结果集的大小，进行选择。这里只有三个表，因此就直接得到了最终的 Join 结果。

仍然以上述例子为例。动态规划算法会枚举所有的可能性，因此相对贪心算法必须从 表开始枚举，动态规划算法可以枚举如下的 Join 顺序。

相应地，因为会枚举所有的可能性，动态规划算法会消耗更多的时间，也会更容易受统计信息影响。

目前 Join Reorder 算法由变量 控制，当参与 Join Reorder 的节点个数大于该阈值时选择贪心算法，反之选择动态规划算法。

当前的 Join Reorder 算法存在如下限制：

• 受结果集的计算算法所限并不会保证一定会选到合适的 Join order
• 是否启用 Outer Join 的 Join Reorder 功能由系统变量 控制。

目前 TiDB 中支持使用 语法来强制指定一种 Join 顺序，参见语法元素说明。