这是MaxComputeSQL优化器原理系列文章之一。SQL优化器的优化规则和框架，我们会陆续发布其他文章。本文主要介绍MaxCompute优化器实现的AutoHashJoin功能。简介在MaxCompute中，Join算子的一种实现算法叫做“HashJoin”。该阶段直接扫描大表数据匹配内存中的小表数据。Hashjoin的执行方式效率很高，但是要求小表中的数据足够小，才能存放在内存中。如果小表数据过大，任务执行过程中会报OutOfMemory错误。在MapCompute中，可以使用MapJoin关键字来实现Hashjoin，如下所示：但是，这种使用hint的方式不够智能。此外，对于复杂的查询，用户可能会因为无法确定某条join路径的数据量而放弃使用mapjoin。在最新的MaxComputeSQL2.0中，CostBasedOptimizer(CBO)包含了一个优化规则，可以自动将join优化为hashjoin。实施原则在CBO中，所有运营商的成本都会被估算。这个成本包括行数、cpu、内存等。有了每个算子的成本，就可以估算出相应输出数据的大小。该公式可以简单地认为：data_size=rowcount*averageRowSize。有了dataSize，就很容易知道任务是否适合使用HashJoin。判断方法是计算每个父算子的数据大小之和是否小于某个阈值。如果估计的数据大小在阈值范围内，将生成包含HashJoin的计划。同时，对于Join，CBO也会生成一个包含MergeJoin的公共计划，***在两个计划中选择成本最小的作为最佳计划。简单来说，在CBO中选择HashJoin作为最优计划有两个步骤：Step1：估计join的输入数据大小，判断是否生成包含HashJoin的计划Step2：比较HashJoin和MergeJoin相关计划的成本，选择成本最小的计划作为***计划的例子，优化如下SQL：上面的SQL会在CBO中进行翻译，生成如下算子树：从上面可以看出，有两个join的parentoperators：id为1的project输出记录数为4行，其输出列只有1列（bad_tpch_customer表中有5列）。预估输出数据量，认为适合使用HashJoin，所以生成的plan包含两种：Plan1:HashJoinPlan2:MergeJoin比较了以上两种plan的成本。显然，方案1的成本较小，所以选择包含HashJoin的方案1作为最佳方案。综上所述，AutoHashJoin的一大好处是它允许用户在没有参与的情况下执行此优化。同时，对于一些复杂的查询，更倾向于使用HashJoin。但由于CBO无法准确预估数据量，可能会出现误判，导致任务OOM。针对这种情况，MaxCompute也做出了相应的调整。对于CBO误判导致HashJoinOOM的任务，将禁用HashJoin规则进行重试。目前CBO中使用HashJoin的门槛比较保守，默认是25MB。主要原因是CBO对数据量的预估存在偏差，无法准确预估数据量。估计不准确的原因有两个：数据被压缩存储，CBO得到的统计数据不准确。CBO的估计算法是有偏差的。CBO正在努力解决两个问题。
