SQL优化器原理 - Join重排-阿里云开发者社区

开发者社区> 阿里巴巴大数据计算> 正文
登录阅读全文

SQL优化器原理 - Join重排

简介: 这是MaxCompute有关SQL优化器原理的系列文章之一。我们会陆续推出SQL优化器有关优化规则和框架的其他文章。添加钉钉群“关系代数优化技术”(群号11719083)可以获取最新文章发布动态。 本文的目标是解释Join重排这个特性的基础概念和算法,如果想快速了解并在MaxCompute上使用这个特性,请直接跳到“总结”。

这是ODPS有关SQL优化器原理的系列文章之一。我们会陆续推出SQL优化器有关优化规则和框架的其他文章。添加钉钉群“关系代数优化技术”(群号11719083)可以获取最新文章发布动态。

ding_jpeg

本文的目标是解释Join重排这个特性的基础概念和算法,如果想快速了解并在MaxCompute上使用这个特性,请直接跳到“总结”。

简介

Join重排是经典的SQL优化问题。考虑3个表的自然连接 A ⋈ B ⋈ C ,在不影响最终结果集的前提下,可以改变连接的顺序为下列:

  1. A ⋈ C ⋈ B
  2. B ⋈ A ⋈ C
  3. B ⋈ C ⋈ A
  4. C ⋈ A ⋈ B
  5. C ⋈ B ⋈ A

熟悉SQL开发的读者会明白,这个顺序可能极大影响SQL执行的效率。打个比方,A,B,C的数据量各自是100条记录,如果A ⋈ C的数据量是1条记录,A ⋈ B是100条记录,显然A ⋈ B ⋈ C的效率低于A ⋈ C ⋈ B,因为前者的中间结果是100条记录,而后者是1条,并且最终结果的数据量是相同的。因此我们得到结论1。

结论1:Join的顺序影响中间结果的数据量,决定了Join的执行效率

另外一种影响Join效率的原因是Join算法。考虑Hash Join算法(对MaxCompute熟悉的读者可以理解为MapJoin),它提前把右边表的数据建立一张哈希表,循环获取左边表的记录查表做Join。假设建立哈希表的代价很大,且随数据量线性递增,那么我们总希望更小的数据集在右边。假设A表是100条记录,B表是10条记录,那么A ⋈ B优于B ⋈ A。因此我们得到结论2。

结论2:Join的顺序影响具体Join算法的效率,决定了Join的执行效率

综上所述,Join的顺序很大程度决定了Join的执行效率。这么看来,在开发SQL程序的时候,我们一定要仔细安排Join的顺序,让它达到最优的执行效率?不尽然。事实上,Join重排的难度如此之大,以至于手工调整是不现实的。主要的难度体现在两部分:

  1. 穷举和验证最优方案的算法复杂度是指数级的(NP hard问题)
  2. 获取某个Join的中间结果数据量的代价很大。我们不得不实际执行一遍Join才能获知中间结果数据量,每个Join都可能花费数小时甚至数天。

因此必须借助机器自动优化。在最新的MaxCompute SQL 2.0中,基于代价的优化器(Cost Based Optimizer,CBO)已经包含了Join重排的优化规则。在本文中,我们尝试从算法、代价计算、数据量估计等方方面面解释Join重排,也会包含一部分CBO的基本概念。

问题分类

Join树

在SQL优化器程序中表达的Join大部分时候是一棵二叉树。把Join节点作为二叉树的节点,可以构建一棵Join树。

例如,上述的A ⋈ B ⋈ C生成的逻辑执行计划(Algebrized Tree)如下:

alge_tree

生成的Join树如下:

Join Tree

至此一切都很完美,每个查询都是树,直到有一种奇怪的查询闯进了这个森林。考虑以下Join:

SELECT * FROM A JOIN B ON A.id = B.id JOIN C ON B.id = C.id

显然,通过A.id = B.id and B.id = C.id可以推出另一个Join,即C.id = A.id,这时的Join"树"是这样的:

circle

这种形态称为 有环 的Join树。有环在Join重排算法里会非常复杂,大部分的算法不支持环。当然我们可以考虑随机删除某个Join操作,保证整个Join树 无环 ,但是这么做会损失一些优化的可能性。

Join树形态

上文提到的Join树在SQL的逻辑表达中通常是一个 偏树 。考虑A ⋈ B ⋈ C ⋈ D,这棵偏树的形态如下:

linear

我们称这种Join树为 左深(Left-deep)树 ,对应的也有 右深树 。在单机/单任务数据库上,我们只考虑这种形态的Join树就可以做Join重排,但是在分布式环境,我们还要考虑 稠密(Bushy)树 ,如下图所示:

bushy

显然,如果有更多计算节点,AB和CD可以并行执行,从而降低整体响应时间。大部分的Join重排算法只能支持左深树,我们会在后续提到稠密树的增强算法。MaxCompute SQL 2.0支持了稠密树的重排算法。

笛卡尔积

区别于自然连接,笛卡尔积将两边的输入做两层循环的完全展开。部分Join重排算法不支持笛卡尔积。

综上,我们有“有/无环”,“左深/稠密树”,“支持/不支持笛卡尔积”这三类8种问题分类。

动态规划算法

终于到了Join重排算法了!希望之前的概念解释没有吓跑你。首先看 动态规划算法 ,这是一个非常自然的Join重排算法,它最早是由P. Griffiths Selinger etl在1979年提出 [Selinger79],并使用在数据库鼻祖级的系统System R上。

动态规划保留所有可能的Join顺序,加入到CBO的执行计划选项(被称为Memo的一个数据结构)中,最后由代价模型选择最优的Join顺序。为了避免代价被反复计算,使用动态规划的算法记录局部最优的代价。

这是一种穷举(exhaustive)算法,但是我们通常提到的Join重排都不是穷举算法,因为它的复杂度实在是太高了!考虑n个输入自由组建一棵左深树或稠密树的所有可能性,它的复杂度是卡特兰数序列,下表是一个直观的例子:

输入数 n 左深树 2^(n−1) 稠密树 2^(n−1) * C(n − 1)
1 1 1
2 2 2
3 4 8
4 8 40
5 16 224
6 32 1344
7 64 8448
8 128 54912
9 256 366080
10 512 2489344

在MaxCompute中,我们最初利用了这个算法,因为它在理论上总能找到最优解(区别于后续我们提到的算法,理论上只能找到次优解),并且支持稠密树和笛卡尔积。为了降低它的复杂度,我们用了一些限制:

  1. 不区分A ⋈ BB ⋈ A(交换)
  2. 仅处理n<=5的情况,当n>5时,分裂为多个n<=5的组分别做Join重排

截止本文,MaxCompute线上仍然使用以上限制的动态规划算法。你可以通过set odps.optimizer.cbo.rule.filter.white=pojr打开Join重排。但是,正如我们看到的,这个算法复杂度非常大,限制也非常多。我们在最新未发布的版本使用了启发式算法替换它。

启发式算法

为了降低动态规划算法的复杂度,我们必须在Join重排算法上就开始做剪枝,而不是把所有可能性都留下来。需要解释的是,启发式算法同样是建立在动态规划算法上的一种优化,而不是独立的自成一套。

既然要“启发”,就需要一个定义什么是 的Join。我们需要引入一个评估体系,被称为cost function(如果读者对CBO熟悉,这里的cost不是指CBO框架的代价,而仅仅是用于评估Join顺序好坏的一个公式,因为此时Join并没有build,我们无法获取准确的cost)。为了简化问题,接下来我们使用的cost function都等于Join的输出数据量(cardinality。有关cardinality的估计算法是另一个大话题,留到下一篇文章解释,此处请读者先假定我们有能力获取一个精确的cardinality)。选择执行计划的准则就是选择cost最小的那个。

最重要的启发式算法有贪婪算法和GOO算法两种。MaxCompute采用了增强的GOO算法。

贪婪算法

贪婪算法考虑逻辑执行计划,以输入为节点,每次选取cost最小的节点直到所有节点都被选取,从而组建一个左深树作为最后的Join重排顺序。贪婪算法只支持左深树。

最基础的贪婪算法的伪代码如下:

ø = {所有输入}
orders = {}
while ø != {}
  n = ni of min(cost(orders ⋈ ni)) for ni in ø
  orders = orders + n
  ø = ø - n  
return orders

实践中,这个算法很容易受到第一个输入选择的影响,因为首次选择节点,cost({} ⋈ ni),还没有任何Join,这个cost被定义为ni的cardinality,小表会优先选择,这并不一定是最好的。因此一个改进的算法是在首次选择时,所有表都有机会,伪代码如下:

ø = {所有输入}
options = {}
for n in ø
  orders = {n}
  rest = ø - n
  while rest != {}
    n = ni of min(cost(orders ⋈ ni)) for ni in ø
    orders = orders + n
    ø = ø - n  
  options = options + orders  
return i of min(cost(i)) for i in options

贪婪算法的好处是,它每次选择的一个Join都是可以实际执行的(区别于下文的GOO算法,选择的可能是一个中间Join),因此我们很容易计算cost。和所有的启发式算法一样,它只能获得次优解。考虑到它不支持稠密树,我们没有选择这个算法。

GOO算法

区别于贪婪算法以输入为节点,GOO(Greedy Operator Ordering)考虑Join树,以Join为节点。它循环选择一个节点,和已选择的所有节点尝试Join并选择代价最小的那个,生成一个新的节点,直到所有的节点都被选择了。

考虑A ⋈ B ⋈ C ⋈ D的例子,如果cost的估计结果是 A ⋈ B < C ⋈ D < B ⋈ C,GOO算法的执行过程如下图所示:

GOOgoo

这个算法的复杂度比贪婪算法高,cost估计从实体的输入改为抽象的Join,难度更大,但是它的优势在于支持稠密树。MaxCompute最新的版本使用了这种算法。

KBZ算法

KBZ或IIKBZ是在cost function满足ASI(adjacent sequence interchange)条件下理论最优的启发式算法。因为MaxCompute无法满足ASI,且KBZ仅支持左深树,我们没有考虑KBZ算法。感兴趣的读者可以参考 [Ibaraki84]。

随机算法简介

我们之前讨论了动态规划算法,也讨论了启发式算法。这两种算法是两个极端,前者保留所有的Join形态,后者只保留唯一的Join形态,这是算法复杂度和最优解之间的tradeoff。实际操作中,这两个极端通常不是好的策略,我们希望有更折中的办法,这就是 随机算法

Random Walk算法 是最基础的随机算法。在次优解的基础上随机改变一些排序,尝试查找更优的方案。__Iterative Random Walk算法__ 做了改进,避免Random Walk生成的环。

折中的考量最后回到了基本的最优化问题上。数学上的一些算法也被应用于Join重排,讨论比较多的包括 模拟退火算法基因算法 [Steinbrunn]。

扩展问题

稠密树偏好

像MaxCompute这样的分布式系统下,我们更偏好生成稠密树,因为分布式系统可以并行执行那些在树中同深度的Join。怎样表达这样的偏好是一个难题。

在我们的实现中,我们对cost function施加一个深度的惩罚(例如,每一级深度施加30%的cost惩罚),我们通过“深度厌恶”这个想法来表达“稠密树偏好”。

Join 分组

在现实中,某些Join可以被合并在一个分组里实现。如果读者熟悉MaxCompute,容易理解有两类分组:

  1. 对于Sorted Merge Join,当参与Join的每一路输入,Join key都是相同的,可以在一个task完成。
  2. 对于Map Join,当大表是相同的,可以在一个map里完成。

显然,Join分组很大程度影响了代价,从而影响了最优顺序。我们在Join重排的实现会保留两种optional plan:合并的方案和不合并的方案,留给CBO框架去选择最优方案。

总结

这篇文档中,我们解释了Join重排这一优化的意义、概念和经典的几种算法。

  1. 动态规划的算法总能找到最优方案,但是复杂度是最高的。
  2. 启发式算法的复杂度最低,只能找到次优解。
  3. 随机算法的效果是上面两种算法的折中。

MaxCompute最新的算法使用了启发式的GOO算法。在线上运行的MaxCompute还在使用受限的动态规划算法。从经典的数据仓库测试集TPC-H的测试发现,使用受限的动态规划算法可以帮助我们获得额外的8%以上的性能提升。

Join重排是一个较激进的优化规则,考虑到CBO无法完美估计数据量(这在我们的后续文章中解释),打开这个规则可能会产生worst plan。这个worst plan的比例经过我们线上实测是非常低的,但是我们仍然不得不默认关闭Join重排规则,你可以尝试设置odps.optimizer.cbo.rule.filter.white=pojr来打开某个query或project的Join重排特性。

索引

[Selinger79] Selinger, P. G., Astrahan, M. M., Chamberlin, D. D., Lorie, I. A., Price, T. G., Lorie, R. a., … Price, T. G. (1979). Access path selection in a relational database management system. ACM SIGMOD International Conference on Management of Data., 23–34. https://doi.org/10.1145/582095.582099

[Ibaraki84] Ibaraki, T., & Kameda, T. (1984). On the optimal nesting order for computing N-relational joins. ACM Transactions on Database Systems, 9(3), 482–502. https://doi.org/10.1145/1270.1498

[Steinbrunn] Steinbrunn, M., Moerkotte, G., & Kemper, A. (n.d.). Optimizing Join Orders, 1–55.

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
阿里巴巴大数据计算
使用钉钉扫一扫加入圈子
+ 订阅

阿里大数据官方技术圈

官方博客
链接