GroupJoin算法设计

IMCI里的GroupJoin实现，是HashJoin与HashGroupby两个算子的融合：

1. 先使用左表（小表）建立哈希表，涉及左表的aggr函数会在建哈希表的时候直接运算掉。这个过程与对左表聚合（i.e., HashGroupby left_table）的操作是相同的。
2. 使用右表（大表）查哈希表，查询命中则在hash table entry上运算涉及右表的aggr函数，否则丢弃或者直接输出。

以上介绍了IMCI GroupJoin算法的基本思路，下文会对算法进行详细的描述以及介绍简化的方法。

限制条件

出于实现的复杂度考虑，相对于理论上最完备的GroupJoin实现，PolarDB MySQL版做了如下几点限制：

1. group by key要完全匹配某一边，且只能是某一边的join key，虽然某些情况下join key的一部分，也能唯一定义这个key（i.e., functional dependency）；
2. RIGHT JOIN、GROUP BY RIGHT的场景，要求right keys是unique keys。否则可能会转成LEFT JOIN、GROUP BY LEFT的方式，或者不使用GroupJoin；
3. 任意一个aggr函数只能单独引用左表，或者单独引用右表；如果原GROUP BY算子中的aggr函数同时引用了左右两个表（e.g., SUN(t1.a+t2.a)），则不适用GroupJoin。

相关算法

INNER JOIN/GROUP BY LEFT

此场景如下SQL所示：

l_table INNER JOIN r_table
ON l_table.key1 = r_table.key1
GROUP BY l_table.key1

假设实际执行顺序与SQL描述一样，则Join过程中不会动态换边。

1. 使用左表建哈希表，并且创建哈希表的过程中直接运算涉及左表的aggr函数；涉及右表的aggr函数，对应设一个“repeat count”，这等同于一个hash table entry对应的payload的数量；
2. 在join过程中，使用右表查哈希表，如果不匹配，则右表的行直接被丢弃；如果匹配，左表的aggr context的“repeat count”会增加1，右表的aggr函数直接进行运算；
3. join完成后，只输出曾经被匹配上的hash table entry的aggr结果，没有被匹配上的hash table entry全部忽略；
4. 输出aggr结果时，要考虑“repeat count”，例如如果一个SUM(expr)的结果是200，“repeat count”是5，则最终结果是1000。

INNER JOIN/GROUP BY RIGHT

此场景如下SQL所示：

l_table INNER JOIN r_table
ON l_table.key1 = r_table.key1
GROUP BY r_table.key1

考虑到l_table.key1=r_table.key1，这种情况被归到“INNER JOIN, GROUP BY LEFT”中。

LEFT OUTER JOIN/GROUP BY LEFT

此场景如下SQL所示：

l_table LEFT OUTER JOIN r_table
ON l_table.key1 = r_table.key1
GROUP BY l_table.key1

1. 使用左表建哈希表，建哈希表的过程中运算左表的aggr函数；涉及右表的aggr函数，对应设一个“repeat count”；
2. 在join过程中，使用右表查哈希表，如果不匹配，则右表的行直接被丢弃；如果匹配，左表的aggr context的“repeat count”会增加1，右表的aggr函数直接进行运算；
3. 与INNER JOIN不同，此场景中join完成后，被匹配上的hash table entry的aggr结果直接输出，没有被匹配上的每个hash table entry单独成为一个GROUP，对应的右表的aggr函数的输入都是NULL。

LEFT OUTER JOIN/GROUP BY RIGHT

此场景如下SQL所示：

l_table LEFT OUTER JOIN r_table
ON l_table.key1 = r_table.key1
GROUP BY r_table.key1

1. 使用左表建哈希表，建哈希表的过程中运算左表的aggr函数；涉及右表的aggr函数，对应设一个 “repeat count”；
2. 在join过程中，使用右表查哈希表，如果不匹配，则右表的行直接被丢弃；如果匹配，左表的aggr context的“repeat count”会增加1，右表的aggr函数直接进行运算；
3. 与其他场景不同，此场景中join完成后，被匹配上的hash table entry的aggr结果直接输出，没有被匹配上的所有hash table entry成为一个GROUP，对应的右表的aggr函数的输入都是NULL。

RIGHT OUTER JOIN/GROUP BY LEFT

此场景如下SQL所示：

l_table RIGHT OUTER JOIN r_table
ON l_table.key1 = r_table.key1
GROUP BY l_table.key1

1. 使用左表建哈希表，创建哈希表的过程中运算左表的aggr函数；涉及右表的aggr函数，对应设一个“repeat count”；
2. 与其他场景不同，此场景在join过程中，使用右表查哈希表，如果匹配，左表的aggr context的“repeat count”会增加1，右表的aggr函数直接进行运算；如果不匹配，则右表的所有不匹配的行成为一个GROUP，对应的左表的aggr函数结果都是NULL；
3. 与其他场景不同，此场景在join完成后，被匹配上的hash table entry的aggr结果直接输出，没有被匹配上的所有hash table entry全都忽略。

RIGHT OUTER JOIN/GROUP BY RIGHT

此场景如下SQL所示：

l_table RIGHT OUTER JOIN r_table
ON l_table.key1 = r_table.key1
GROUP BY r_table.key1

限制条件

要求r_table.key1必须是distinct的，否则这种join是不合法的；如果不能确定r_table.key1是distinct的，则需要在优化器里将这种join+groupby转成LEFT OUTER JOIN、GROUP BY LEFT。

执行步骤

1. 使用左表建哈希表，建哈希表的过程中运算左表的aggr函数；涉及右表的aggr函数，对应设一个“repeat count”；
2. 与其他场景不同，此场景在join过程中，使用右表查哈希表，如果匹配，直接输出左右表的aggr结果；如果不匹配，也输出aggr结果，此时左表的aggr结果都是NULL；
3. 与其他场景不同，此场景在join完成后，GroupJoin即完成，不需要处理任何hash table entry。