在之前的文章中我们讨论了基于graph的DP-based算法，来解决join ordering的枚举问题。
这些DP算法通过join predicate描述的连通性，解决了枚举可能的表组合问题，但join graph本身(即使hypergraph)是无法完整的描述join语义的，因为连通边本身无法描述不同类型的join语义，例如left outer join/semi join/anti join...，因此即使找到了所谓的csg-cmp-pair，也不一定是有效的plan。
这篇paper讨论的就是这个问题，当枚举出一个csg-cmp-pair (S1 o S2)，如何判断这是有效的join组合？其中涉及关系代数等价变换，数学符号略多。。。
基本术语
-
LOP
表示逻辑的二元算子，本文的上下文中就是Inner/outer/semi/anti join，本来还有讨论group join，但由于是HyPer系统下的特定优化，因此就先不考虑它了。
- F(e)/
分别表示一个表达式e，其中引入的属性集合，以及属性所属于的表集合
- STO(o) / T(o)
分别表示以算子o为根的子树中，所有children算子的集合/子树中表的集合
-
SES(o) (syntactic eligibility sets)
从语法上，算子o可以执行，需要依赖的表集合，也就是这些表都存在时，算子o才能计算
-
Degenerate Predicates
如果在二元算子中的谓词，但没有同时引用算子两侧的表，也就是
T (left(o)) ∩ FT(p) = ∅ ∨ T (right(o)) ∩ FT(p) = ∅，注意笛卡尔积也属于这种情况
Core Search Space
做优化器的同学离不开join ordering这个最基本却又最重要的功能，但并没有一个规范化的描述，到底ordering是什么意思？
从总体来看，join ordering就是利用各种join的语义，建立可以生成等价plan的transformation，也就是变换后的join结果与变换前一致。通过不断穷尽式的应用这些transformation，来生成各种可能的有效的join顺序，就是join ordering了。
其中主要包含3种transformation：
commutativity 交换律
交换律只针对单一算子，其含义显而易见
注：上图最后一个是group join，可以先忽略它，+表示交换律可以成立，-表示不成立，满足交换律记为comm(o)
associativity 结合律
结合律针对2个算子，具体来说满足
这样的恒等式，则结合律成立，这里operator 的下标表示它只引入了e1和e2中的属性，不包含e3的，很明显如果包含e3属性，等式的左边根本无法执行，而右边则可以。
如果上述等式可以成立，则标记为assoc(◦a, ◦b)，即oa, ob满足结合律，注意这里是有顺序的，oa -> ob满足结合律，不等价于ob -> oa满足结合律，因此结合律不具有对称性！但如果oa, ob都满足交换律，则存在这种对称性，可以如下推导
下表给出了不同算子的组合之间，是否满足结合律
注：首先观察上表并不是对角线对称的，说明assoc本身不对称，同时对于有上标的+号，表示有条件的成立，即必须满足标注的条件，结合律才可以成立。
asscom 交换结合律
仅是交换律+结合律并不能完全描述所有等价变换，例如下面这种
最常见的semi-join变换方式，无法用以上两种变换描述。因此引入这种：
因为是发生在top operator ob的左子树，记为l-asscom(oa, ob)
同样有
发生在top operator ob的右子树，记为r-asscom(oa, ob)
注意asscom是具有对称性的:
同样asscom可以用交换律和结合律推导出来：
针对各种operator变换的合法性如下表所示
可以看到，这个table是沿对角线对称的。
在table 1 - 3的各个entry中，标记为 - 的，或者上标中的条件无法满足时，则代表一个conflict，表示如果做了这种变换，生成的plan是非法的。
用更加直观的operator tree来描述等价变换的要求
上图的左侧部分，每种变换的下方2个表达式，描述了允许变换的前提条件，以第一个为例，可以执行右侧的等价变换，必须要求ob中不能引用e1的属性，oa不能引用e3属性，这个是很明显的前提。
不太明显的是，如果一个算子的谓词p，不是那种degenerate谓词（即同时引用了左右子树的属性），则assoc和l/r - asscom不可能同时成立，例如前2个变换如果同时满足，则ob的谓词pb同时不引用e1和e2的列，也就是不引用左子树的列，与其不是degenerate谓词矛盾了。
core search space
基于一个初始operator tree，穷尽式的应用以上所有可行的transformation生成的有效plan集合，构成了core search space，以 这个简单算子树为起点的core search space如下：
可以通过对这4种transformation的应用做限制，来实现对于join search space的约束，例如
Left Deep Tree:
只允许对最左下方的join应用comm A⨝B → B⨝A 和 l-asscom (A⨝B)⨝C → (A⨝C)⨝B 这两种变换。
Zig-Zag Tree:
允许任意join应用comm A⨝B → B⨝A 和 l-asscom (A⨝B)⨝C → (A⨝C)⨝B 这两种变换。
Bushy Tree:
允许任意join应用任意变换。
搜索空间大小：Bushy Tree > Zig-Zag Tree > Left Deep Tree
与plan enumeration算法结合
有了以上的那些抽象概念，怎么和plan enumeration算法结合呢？由于知道什么叫做conflict，那么每找到一个csg-cmp-pair，只要能判断其是否存在conflict，就可以淘汰掉非法的plan，保证算法的正确性。如下是对之前文章提到的DPsub算法的检测：
上面第10行的APPLICABLE 函数，就是所谓的检查conflict的函数，输入是 S1 o S2这个操作。
注意在上面的算法中，显示对每个算子的交换律做了考虑(line 12)，因此APPLICABLE中主要考虑assoc + l/r-asscom这3个变换。
检测冲突
paper中采用了“3步走”的方法，依次提出了3种逐步完善的CD(conflict detector)，最终给出能够保证正确性（不会产生非法plan）且能够保证完备性（不会漏掉合法plan）的算法。
基本思路是利用上面的这些冲突表table 1 -3，在给定一个初始的join operator tree之后，对每个子树的顶层算子（用ob表示），其所拥有的子树可能会进行各种可能的变形，导致表达式e移入/移出，但由于有冲突的存在，会对能做的transform产生约束，因此对ob左/右子树中的每个算子oa，（oa ob)/(ob oa)禁止变换的冲突约束了ob的子树中，某些表达式一定要存在于子树中不能移出！！或者只能有条件的移出！！这种约束构成了对ob的一种检查，我们可以把所有存在的约束，描述成某种形式，用来对(S1 ob S2)进行检查，检查到约束不被满足，则这个join plan就是非法的。
这么说貌似比较抽象难以理解，具体看下3个步骤
Step 1: CD-A
这是最为粗暴的约束方式，针对每个operator引入了一个TES(total eligibility set)的概念，表示一个表的集合，这个集合最初只有SES(o)，但随着检查(oa, ob) ，或(ob, oa)发现冲突，为了把冲突导致的无效形式从结果上避免掉，方法就是约束某些表达式e(table)必须在ob的子树下！！
TES就是由conflict所约束的必须在ob的子树下的表的集合，记为TES(ob) 。
以上图的第一个变换assoc为例，假设结合律变换是非法的，为了保证assoc(oa, ob)无法执行，采用了反向约束的方法，即限制e1一定要在ob下面，这样就无法做从左侧树 => 右侧树的变换了。l/r-asscom也是类似的思路。
同时要考虑一种情况
即存在冲突的两个算子Op1/Op2并不直接构成父子关系，但Op1在Op2子树下，如果子树自身允许做重排序，那么也会在变换后形成右图的形态，这种跨层级的冲突也要考虑，因此对TES的收集，需要自底向上进行：
通过如上算法建立整个operator tree中各个算子的TES集合后，在执行枚举算法时，每建立一个csg-cmp-pair (S1 o S2) 时，只需做如下检查：
L-TES就是TES中左子树的部分，R-TES是右子树的部分。条件成立则认为是合法csg-cmp-pair，否则非法。
注意这种方法确实可以避免无效的plan，但因为是反向的，会产生过大的限制，导致某些valid plan也无法生成，造成误伤。
上图中，由于semi-join0,1（最左下operator）与left-join2,3（最上方operator）无法满足assoc，CD-A会约束R0必须在left-join2,3的下面，导致Plan1 / Plan2的这种合法plan也没法生成。
Step 2: CD-B
相对于CD-A的强约束（无条件约束），它的约束更灵活一些，是有条件的约束。
观察上图的变形，我们可以看到无效的形式是这样的：原来e1,e2都在Ob下，现在e2在Ob下，e1不在Ob下了，所以更精确的约束是：
不允许出现，当e2在Ob下时（前提条件），e1却不在Ob下（冲突）！
这种有前提条件的约束，用conflict rules来描述：
也就是 ： 如果T1集合有表在()下，则T2集合必须完全在S下！
这样就不用扩展TES了，使其与SES一致即可，只要额外保证这些CR(conflict rules）不被违反就行了。收集CR的算法如下，总体流程类似CD-A收集TES：
同时检查条件就变为了：
这里仍然有L-TES/R-TES，但TES已经和SES等价了，没有更广泛的含义。同时CR(o)的所有rules都要被满足，否则就认为发现冲突。
这个算法仍然只能保证正确性，而不是完备性，例如如下例子：
观察左侧的operator tree，由于r-asscom(inner-join0,1, semi-join1,3) 不能成立，会建立如下的CR:
因为在考察inner-join0,1和semi-join 1,3的r-asscom时，会把(R1 inner join R2)看做一个整体，r-asscom并不合法（冲突表），(R1 inner join R2)这个整体被有条件的限制在了O0,1的下面，导致右侧的有效plan tree无法生成。
但其实inner-join0,1和semi-join 1,3都不引用表R2，所以可以对R2不做限制，从而更精细的控制T2所涉及的表集合为ob真正引用的表！这里由原来的R3 -> (R1, R2) 变为R3 -> R1。
Step 3: CD-C
针对上面的问题，CD-C是更细粒度的控制，其他方面都和CD-B完全相同，只是对T2的处理上更细，只考虑ob真正引用到的表集合。这个算法是可以生成所有有效的plan的，但paper中没有给出完备性证明。
从line 5可以看到，在推导T2时，使用了 ，也就是只约束算子oa真正引入的表集合。
总结
经过上面复杂的算法描述后，已经给出了具有完备+正确的冲突检测机制，也就是我们所需要的APPLICABLE函数，把它与任意的graph-based DP算法结合，就能保证完整的枚举所有可能的join组合，选取最优计划。