left join 和子查询效率_Calcite 子查询处理 - II (Decorrelate)

上一篇中通过 Program#Standard 的第一个 Program 已经将表达式中的 RexSubQuery remove 掉并转换成 LogicalCorrelate 或 LogicalJoin。对于有关联变量的情况，这里虽然将子查询从表达式中提出来，但关联表达式 $core 依然存在, 所一接下来执行的下一个 program 是 DecorrelateProgram 进行去关联， program 判断了 forceDecorrelate, 他默认为 true, 所以一般所有子查询都会执行尝试进行子查询的消除处理 RelDecorrelator$decorrelateQuery

首先用 CorelMapBuilder 来收集下 correlate variable, CorelMapBuilder 自身就是一个 Shuttle(表达式 vistior)， 收集并获取 CorelMap, 如果 rel 树中完全没有 correlate 则直接结束没必要去关联(- -)， 如果有关联则会在 decorrelator 中可能尝试用 3 个 HepProgram 运用不同规则来对子查询进行 Hep 去关联。

三个快速去关联 rules

开始会在 removeCorrelationViaRule 中分别尝试用 RemoveSingleAggregateRule， RemoveCorrelationForScalarProjectRule， RemoveCorrelationForScalarAggregateRule 三个规则进行去关联，如果能去掉则会快速返回。

1) RemoveSingleAggregateRule:

这个规则用于移除 single_value (removeSubQueryRule 添加) 的 input 是 单表达式project 和 agg 时将 single_value agg 去掉,　通俗的说就是如果添加的 single_value 下面有 agg 保证不会多 value 就可以将他去掉(列信息可能非 unique 但是有 agg 对所有 input 列的 agg)

2) RemoveCorrelationForScalarProjectRule:

这个规则寻找 LogicalCorrelate 右 input 是 LogicalAgg - LogicalProject 的 pattern 类似这样:

Correlate(left correlation, condition = true)
  leftInput
  Aggregate (groupby (0) single_value())
   Project-A (may reference corVar)
    rightInput

1. correlate - agg - project -filter - any(without correlation)

首先 check 一个特列， 如果 logicalProject 下还是一个带 $cor 的 filter 且过滤的是唯一的情况，类似这样：

Correlate(left correlation, condition = true)
  leftInput
  Aggregate (groupby (0) single_value())
   Project-A (may reference corVar)
    Filter (references corVar)
      rightInput

如果 filter 的 input 没有用到关联变量， filter 的条件为中的的列在子查询表中(忽略null)是唯一的 则可以直接去掉 agg，转换 correlate 为 join, 移除 filter 中的 $cor 条件移除放入 join condition , 并将 project 提到 join 上面, 其实去关联就是将子查询中用到 $cor 的地方上提到 join condition 或 logicCorrelate 之上，让子查询没有 $cor 从而可以将 logicCorrelate 变成 logicJoin， 转换后这样:

Project-A' (replace corVar to input ref from the Join)
 Join (replace corVar to input ref from leftInput)
  leftInput
  rightInput (previously filterInput)

2. correlate - agg - project - any(without correlation)

如果不是特列情况， 如果 project 下不是 filter， 且 project 下的 input 是没有关联， 且 project 有关联(其实就是满足 pattern 且右子树只有 project 有关联, 类似这个 select * from emps e where e.deptno = (select d.deptno + e.deptno from depts d))， 则会将其转换为:

Project-A' (replace corVar to input ref from Join)
  Join (left, condition = true)
    leftInput
    Aggregate(groupby(0), single_value(0), s_v(1)....)
      Project-B (everything from input plus literal true)
        projectInput

可以看到， 这里首先添加了一个 Project-B 内容是之前 Project-A 用到的非关联列添加一列为 true 的 nullIndicator列(主动添加 true 上一篇文章中我们也看到多次，主要为了后面在 left join 后能区分出数据 null 还是 join 导致的 null); 然后还是 single_value agg; 下层已经没有关联变量将 correlate 变成 condition = true 的 join; 添加等价之前的 Project-A 的 Project-A', 过程是先将 left 推入， 对 right 用刚才添加的 nullIndicator 考虑 null 的 case when.

3) RemoveCorrelationForScalarAggregateRule:

这个规则匹配的 pattern 是这样:

CorrelateRel(left correlation, condition = true)
  leftInput
  Project-A (a RexNode)
   Aggregate (groupby (0), agg0(), agg1()...)
    Project-B (references coVar)
     rightInput

和上个规则相比在 agg 之上多了一次 project ， 且 agg 要求只能是 SIMPLE 的

1. filter + unique

很上一个流程类似 如果 right input 是 filter 且下层不再有其他 correlation 且子表比较列为 unique, 可以将开始的 pattern

Correlate(left correlation, condition = true)
 leftInput
 Project-A (a RexNode)
  Aggregate (groupby(0), agg0(),agg1()...)
   Project-B (may reference corVar)
    Filter (references corVar)
      rightInput (no correlated reference)

转换为:

Project-A' (all gby keys + rewritten nullable ProjExpr)
   Aggregate (groupby(all left input refs) agg0(rewritten expression),agg1()...)
    Project-B' (rewritten original projected exprs)
     Join(replace corVar w/ input ref from leftInput)
      leftInput
      rightInput

如果 agg 函数是 count, 需要用 nullIndicator 做 count

Project-A' (all gby keys + rewritten nullable ProjExpr)
 Aggregate (groupby(all left input refs), count(nullIndicator), other aggs...)
  Project-B' (all left input refs plus the rewritten original projected exprs)
   Join(replace corVar to input ref from leftInput)
    leftInput
    Project (everything from rightInput plus the nullIndicator "true")
     rightInput

2. other but no correlate

如果 right input 不是 filter 且下层算子没有用到 correlation 变量, 则单纯将 agg 上提, 然后替换为 join, 将查询改写为:

Aggregate (groupby(all left input refs) agg0(rewritten expression),agg1()...)
 Project-B' (rewritten original projected exprs)
  Join (LOJ cond = true)
   leftInput
   rightInput

如果 agg 是 count 同样需要特殊处理下:

Project-A' (all gby keys + rewritten nullable ProjExpr)
 Aggregate (groupby(all left input refs),count(nullIndicator), other aggs...)
  Project-B' (all left input refs plus the rewritten original projected exprs)
   Join (replace corVar to input ref from leftInput)
    leftInput
    Project (everything from rightInput plus the nullIndicator "true")
     rightInput

小结: 这 3 个规则对比较常见的简答情况，将 correlate 下马上接的 project/filter/agg 进行上提进而去关联, 如果经过这三个规则之后已经没有关联则可以快速结束去关联过程，如果还是有关联则尝试其他复杂的去关联规则。

RelDecorrelator#decorrelate

如果在这三个规则处理后 仍然有 correlate, 则进入 decorrelate 这个相对复杂的去关联方法。

这个方法的整体处理逻辑是:

• 进入方法后先 hep 执行一组前置规则
• 之后用反射递归调用 decorrelateRel 重载,
• 最后在完成后再 hep 执行一组后置规则。

decorrelate 前置 rules

在开始反射递归执行 decorrelateRel 之前会用 hep 执行 4 个规则:

1) AdjustProjectForCountAggregateRule:

用于将在 agg 有 count 时将 project 上提到 correlate 上, 即将

CorrelateRel(left correlation, condition = true)
 leftInput
 Project-A (a RexNode)
  Aggregate (groupby (0), agg0(), agg1()...)

如果有没有 Project-A 则自己添加而一个, 然后应用规则, 最后转换为:

Project-A' (all LHS plus transformed original projections, 
            replacing references to count() with case statement)
 Correlate(left correlation, condition = true)
  leftInput
  Aggregate(groupby (0), agg0(), agg1()...)

2) FilterIntoJoinRule:

这个规则会在多个地方被多次用到(包括后面的 volcano planner)， 是 FilterJoinRule 的自类， 主要尝试将 Join 上的 Filter 推到 Join 里作为条件， 主要逻辑位于 perform 方法。

3) FilterProjectTransposeRule:

将没有 correlation 的 Filter 推下过下层的 Project, 这个也是一个被多个地方用到的通用规则, 通过这个规则之后可以在后续处理中假设 filter(没有 cor) 在 project 下。

4) FilterCorrelateRule:

在上面两个规则之后尝试将 correlate 之上的 filter 尝试推到 correlate 的两个 input 上。

经过这 4 个规则对 rel 树的调整后， 开始进行 decorrelate.

反射递归处理 decorrelateRel

getInvoke 方法会通过反射的方式从 root 开始递归调用 RelDecorrelator 中的各种类型的 decorrelateRel 重载方法， 从叶子节点的算子开始处理， 根据算子的不同类型进行 rewrite

Filter:

因为进过上面 FilterProjectTransposeRule 处理后 filter 一定在 project 之下, 在递归处理过程中会有优先看到 filter， 所以我们从这里开始, 首先会看下 input 是否已经包含该全需要的 $cor (因为可能底层已经 decorrelate 好了上面的算子直接用) , 如果 miss 则进入 decorrelateInputWithValueGenerator 这个方法， 对于 Filter Rel 使用之前 CorelMapBuilder 收集的 Rel -> $cor 找到当前 Rel 所有需要的 $cor 并检查这些 $cor

• 如果没有不是当前 filter condition 的 equal 和 and 之外用到 $cor(也就是都在当前filter中且都是 equal 和 and), 则将 $cor 通过 frrame 传递， 并直接将 filter 中使用 $cor 的地方替换为下层提供的列并放到原来 input 上。
• 反之为了去关联则需要对当前 rel 用到的所有 $cor 尝试生成 ValueGenerator, 即通过 $cor -> rel 关系获取对应 $cor 产生的 LogicalCorrelate 的 input rel, 并做在当前位置重复做一遍， 并做 disticnt 作为 ValueGenerator(如果有多个变量则 join 起来作为 valueGenerator)，然后和当前 filter 的 input 做 cross join 并，之后同样将 filter 中的 $cor 替换为 join 输出列，并将 filter 放到 join 之上

总体上对应注释中这段描述的逻辑

1. If a Filter references a correlated field in its filter
condition, rewrite the Filter to be
   Filter
     Join(cross product)
       originalFilterInput
       ValueGenerator(produces distinct sets of correlated variables)
and rewrite the correlated fieldAccess in the filter condition to
reference the Join output.
 
2. If Filter does not reference correlated variables, simply
rewrite the filter condition using new input.

filter 处理之后会没有关联表达式, 只是如上面所述会自己 join 更多的 rel(及其子 rel)

Project:

看过上面的 filter 看 Project 就很类似， 如果 project 中有用到关联变量同样通过 decorrelateInputWithValueGenerator 去进一步 join ValueGenerator， 并对 Project 根据下游 input(或 join 了 valueGenerator 的 input)， 对用到的 $cor 转换为列引用；

最后将 input 提供的 $cor 通过 frame 传递下去到输出给上游算子。

Agg:

Agg 首先处理 input 算子并返回其 frame, 之后

• 因为 calcite 中的 agg 会将 group key 放到 input 靠前的部分，所以首先将 input 的前 cardinality 个非 const 列放到新 project 的前面的部分(如果 group 的 key 是 const 则先保存到 omittedConstants)
• 如果 input 有产生 $cor, 紧接着上一步的 group key 将 $cor 引用的列追加到新 project 中
• 之后将剩下的 input 列也都放到新 project 中, 并在 input 之上生成新的 project
• 根据新 project， 修正 groupSet 和 aggCall 的参数， 并创建新的 agg
• 最后根据第一步是否发现 omittedConstants, 如果则添加一个后置的 project 后追加 const

总结下就是首先添加一个 project 将 group key 放到新 project 的前面并紧跟 $cor 相关的引用列，最后是剩下的列， 并修改 groupSet 和 aggCall 来生成新的 agg; 有个特殊情况是如果 input 有 const，则在 agg 和 新添加的 project 中忽略并在 agg 之上添加一个后置的 project 补回

Correlate:

首先递归处理左右 input 算子并且获得 frame，只有右边 input 会产生 $cor(所以右边 input 没有 $cor 可以直接跳过该算子的处理)， 如果右 input 有 $cor 将 LogicalCorrelate 转为 Join.

decorrelateRel 是递归处理的，所以当我们看到 correlate 的时候其 input 算子已经完成 decorrelate 且 $cor 信息已经自底向上传递并放到 frame 中，所以对 correlate 的处理就是看下 input 通过 frame 传上来的 $cor， 如果是自己定义的的产生 condition 将对应 $cor 改称为 equal 对应下层列， 并生成 join(前面提到过 correlate 是没有 condition 的但他能定义 $cor 給右边算子树用), 如果不是自己定义的 $cor 则继续向上传递等遇到定义 $cor 的 correlate 会用同样的过程消除。

对于 left input 不需要处理继续向上传递 $cor , join 的生成需要处理 right 列的 offset， 并使用根据 $cor 生成的 condition 作为 join 条件。

Join：

对 join 的 left 和 right input 递归处理获取 frame； 并如果左右都被重写过， 则生成新的 join， 主要对 join 的 condition 表达式进行 decorrelateExpr; 最后对 mapOldToNew 和 corDefOutput 调整为 join 后的 offset。

Sort:

sort 算子自身不会进行 $cor 引用，但可能会引用下游 $cor, 所以需要根据 input frame 调整 RelCollation 的引用列 index。

小结下: decorrelateRel 反射递归自底向上，消除表达式中 $cor 的引用，并向上传递 $cor 直到遇到定义 $cor 的 correlate 时转换 correlate 为 join; 对于 filter 和 project 中的 $cor 可为了消除多 join 被引用 rel。

decorrelate 后置 rules

如果 decorrelateRel 有进行 decorrelate 修改(返回的 frame 不为 null)， 则对返回的新 rel 用 hep 运用两个后置规则。

前面的规则我们是设法将 $cor 向上提并最终消除 correlate 生成 condtion 转 cor 为 join，在完成消除这两个规则则尝试将 condition 向下 push。

1) FilterIntoJoinRule

同前置规则中的 FilterIntoJoinRule, 再次尝试将 Join 上的 Filter 推入 Join 中作为 join condition。

2) JoinConditionPushRule

也是 FilterJoinRule, 只是尝试将 Join condition 中的条件下推到 Join 的 input 去， 这个规则的实现后面介绍 join 相关优化时再来介绍

反向操作

通过这上一遍和本篇可以看到 calcite 会优先将 correlate 转换为 join 并且去关联，并且从 calcite 自有用法看到这个过程是在 CBO VolcanoPlanner 之前只要规则能匹配应用就进行转换，看上去多数时候这样是 ok 的(感觉这样做也可以防止 cost 不准带来的选错风险?), 但是存在一些场景， 比如 correlate 右表的数据量少或者可以命中 index 的时候对外查询每条记录处理一遍内表有可能比添加 agg 转 join 的效果好，其实选择是 join + agg 还是 correlate 更应该根据代价来决定，不过 calcite 提供了一个条和子查询消除的反向规则 ---- JoinToCorrelateRule, 这个规则除了反向外原本就是 join 的情况也存在转换更好的可能...

这个规则作用于 LogicalJoin 且要求 joinType 是 inner 或 left, 转换过程就将 join condition 引用 left 的所有 filedAccess 转换为引用 $cor, 并修正引用 right, 生成 filter 放到 right input 之上来生成 LogicCorrelate。

不过这个规则在 calcite 自己代码除测试外没有用到的地方用到 drill 里也没有 - -

总结

本文我们主要看了下如何将 SubQueryRemove 之后的 LogicalCorrelate 进行去关联的实现。