共计 1562 个字符，预计需要花费 4 分钟才能阅读完成。
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=R
3.i3、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