多表 Join 处理在现实业务中很常见，通常其执行效率和 Join 的顺序息息相关。

简介 #

Join 操作满足交换律和结合率，那么对于两个表 A Join B 来说，那么可以是 $A \Join B$ 或者 $B \Join A$，而对于三个表 A Join B Join C 可以是 $(A \Join B) \Join C$、$A \Join (B \Join C)$ 等，无论如何转换，始终希望可以尽早、尽快减少结果集。

正式介绍实现之前，先整理下常见的基本概念。

Join Tree #

这是一棵二叉树，叶子节点代表需要被连接的表，非叶子节点代表 Join 算子，根据 Join Tree 的形状，可归类为：

• Left Deep Tree 左深树，Join 节点的右侧是叶子节点，很多数据库会默认将左深树作为 Join Reorder 的搜索空间。
• ZigZag Tree 可以理解为左深树的基础上可以进行左右节点的交换。
• Bushy Tree 结构最为自由，表可以按照任意顺序。

Join Cardinality #

表示 Join 算子输出中间结果集的大小，是所有 Join Reorder 算法进行顺序选择的重要依据，输出的结果越小，那么越利于提升后续 Join 的性能。

相对来说，单表大小比较好估计，可以通过表的行数和每行的平均长度估算出，对于表上有过滤条件可以通过直方图或 Sketch 等方法估算出过滤后的行数。

对于 Join 的中间结果集行数估算一般采用以下公式：

LeftRowCount * RightRowCount / MAX(LeftCardinality, RightCardinality)

其中 RowCount 代表 Join 左右输入行数，而 Cardinality 代表左右 Join 列的 NDV 值，比较特殊的 CrossJoin 就是左右行数相乘。

Join Cost #

不同的 Join 算法实现对应了不同的计算规则，常见的有 NestedLoop Join(Block/Index)、Hash Join、Sort Merge Join，如下以 CPU 代价估算为例。

----- Hash Join
CPU = Probe权重 * Probe端数据量 + Build权重 * Build端数据量
----- Nested Loop Join
CPU = Join权重 * 左端数据量 * 右端数据量
----- Sort Merge Join
CPU = 左端输入数据排序代价 + 右端输入排序代价 + Merge代价

注意，不同的数据库其驱动表可能在左或者右。

整体流程 #

因为 Join 满足交换律和结合律，如下是三个表的可能 Join 顺序。

理论上可以枚举出所有可能的 Join 顺序，然后通过计算每个 Plan 的成本，从而选出代价最小的执行计划。但是，随着 Join 节点数增加，优化器的搜索空间会成指数级放大，尤其是再考虑不同的 Join 实现，如下是 Columbia 中的介绍。

所以，很多系统实现时会根据 Join 节点树选择不同的策略，如下是常用的规则：

• 默认采用左深树，因为 Join Order 的调整依赖统计信息，如果关闭了那么就无法处理。
• 小于某个数值 (例如4) 则枚举所有可能的顺序。
• 如果还小于某个值 (例如10) 则采用动态规划和贪心算法。
• 依然超过上述的值时，则直接采用贪心算法。

上述的阈值通常可以通过变量动态配置。