On the Correct and Complete Enumeration of the Core Search Space
在之前的文章中我们讨论了基于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