优化器核心技术—Join Reorder

Join Reorder 的简介

Join Reorder 是开务数据库 SQL 优化器中的核心优化算法，开务数据库优化器包括 RBO 和 CBO 两部分，负责计划优化，提升 SQL 执行性能。Join Reorder 能够保证在复杂查询执行的场景下，枚举合法的执行路径，保证 SQL 执行性能的稳定性。

开务数据库中的 Join Reorder 主要采用了基于规则变换的 Top-down 枚举算法，通过各种 Join 之间满足的 Reorder 规则，构建出完备的搜索空间，枚举所有能够正确执行的 Join 顺序，利用 Dpsube、CD-C 冲突检测、代价计算选出最优的执行顺序。

Join Reorder 的规则

1、Commutativity：example:R1⋈R2=R2⋈R1

首先是 Join 中的交换律，Table 1 展示了 7 种 Join 满足的情况，其中 + 号表示对于的 Join 类型满足交换律，- 号表示不满足。

2、Associativity：example:(R1⋈R2)⋈R3=R1⋈(R2⋈R3)

其次是 Join 中的结合律，Table 2 中展示了任意两种 Join 的满足情况，上标 1 和上标 2 表示当 Join 满足对 R2 的 null rejecting 时可应用该规则。

3、l-assocom: example:(R1⋈R2)⋈R3=(R1⋈R3)⋈R2

4、R-assocom: example:R1⋈(R2⋈R3)=R2⋈(R1⋈R3)

上述第 3 和第 4 条，是左（右）交换结合律，也是结合律和交换律的一种综合应用。Table 3 展示了任意两种 Join 满足该规律的情况，上标 1、2、3、4 表示对应的 Join 条件满足对 R1 或 R3 的 null rejecting 时可应用该规则。

Dpsube 算法

递归地从关系集合 R 中选出子集对 {S1,S2}，求解 BestPlan{R} = BestPlan(S1) join BestPlan(S2) 。其中 Dpsube 算法中核心的问题在于 applicable 的实现。

CD-C 冲突检测算法

递归遍历 Join graph 中当前 Edge 的左右边集，根据规则变换表 Comm、Assoc、l-assocom、R-assocom 记录下当前 Edge 的冲突规则（算法流程中的 CR），在 Dpsube 流程中根据是否满足 CR 枚举 Valid Join，对应 Dpsube 的 applicable 判断。

Join Reorder 的实现

1、populateGraph

该流程中会递归遍历初始生成的 left-deep-tree，构建用于 Join order 枚举的 Join hyper-graph，区别于普通的 graph 结构，Join hyper-graph 中的边表示谓词条件，该条边可以连接多个顶点（一个顶点看作一个关系）。

在该流程中，会有一个 Join-order-limit 限制，默认为 4，超过 4 个 Table 部分的 Join 关系不会进行 Join order 的调整，被当作一个整体的关系表达式参与 Join Reorder。

2、ensureClosure

该步骤确定谓词的传递性闭包，可以推出隐藏的谓词条件，以便于发掘更多的 Join ordering。例如：R1.i= R2.i AND R2.i=R3.i => R1.i=R3.i

3、DpSube

采用文中的 Dpsube 算法，如果存在子集对 {S1,S2} 对于某个 Join Edge，能够满足该 Edge 下的冲突规则，生成的 Join 为合法 Join，Dpsube 按照这种方式枚举所有的 Join 顺序，在后续的 CBO 流程中，选出 cost 最低的一个。

4、makeInnerEdge

采用 CD-C 冲突检测算法，记录每个 Join Edge 的冲突规则集，用于之后 Dpsube 枚举 Join 流程的合法性判断，在开务数据库中，增加了一个特殊处理：如果 STO(left(edge)) ⊂ TES(edge)，则不进行该边的冲突规则添加。

END