Join优化

物理算子支持

SelectDB支持如下两种物理Join算子，用于实现单机引擎中数据进行Join的处理过程。

• Hash Join：在右表上根据等值Join列建立哈希表，左表流式的利用哈希表进行Join计算，这个算子只适用于等值Join。

• Nest Loop Join：通过两个for循环进行Join过程处理。它适用的场景是不等值的Join，例如大于小于或者是需要求笛卡尔积的场景。它是一个通用的Join算子，但是性能表现差。

Shuffle方式概述

作为分布式的MPP数据库，SelectDB在Join的过程中需要先进行数据的Shuffle，然后才调用物理算子进行处理。SelectDB现阶段支持4种Shuffle方式，以下举例说明。

下述示例将对表S和表R进行Join，其中N表示参与Join计算的节点的数量，T则表示表的记录数。

• Broadcast Join

  它要求把R表的全量的数据都发送到S表上，即每一个参与Join的节点，它都拥有R表全量的数据，也就是T(R)。这个Shuffle方式较为通用，同时能够支持Hash Join和Nest loop Join。它的网络开销是N*T(R)。

  

  S表数据不移动，R表数据发送到S表数据的扫描节点。

• Shuffle Join

  当进行Hash Join时，可以通过Join列计算S表和R表相应数据的哈希值，把相同哈希值的数据被分发到分布式系统中的同一个节点，利用分布式系统加速Join查询。它的网络开销是T(S)+T(R)，但它只能支持Hash Join，因为它根据Join的条件计算分桶。

  

  S表和R表数据根据分区计算，计算的结果发送到不同的分区节点上。

• Bucket Shuffle Join

  SelectDB的表数据本身是通过哈希计算分桶的，所以就可以利用表本身的分桶列的性质来进行Join数据的Shuffle。例如两张表；表S和表R需要做Join，并且Join列是表S的分桶列，那么表S的数据其实可以不需要移动，通过移动分发表R的数据就可以完成Join的计算。

  它的网络开销是T(R)，相当于只Shuffle表R的数据就可以完成Join。有关Bucket Shuffle Join使用的更多细节，详见Bucket Shuffle Join。

  

  表S数据不移动，表R数据根据分区计算的结果发送到S表扫表的节点

• Colocation Join

  对于多个相关联的表，在建表时确保表的数据分片数量一致，相同Hash分桶在分布式系统中的分布一致，那么实际查询时就可以跳过数据的Shuffle过程，直接进行Join计算，提升查询性能。Colocation Join详情，请参见Colocation Join。

  

  数据已经预先分区，不需要考虑网络开销，直接在本地进行Join计算。

四种Shuffle方式对比如下。

上述这4种Shuffle方式的灵活度按照从高到低排列，对数据分布的要求越来越严格，但Join计算的性能也逐级提高。

Runtime Filter优化

Runtime Filter在查询规划时动态生成，由HashJoin算子（对应查询Explain/Profile中的HashJoinNode）中将Join过程中的右表转换为过滤条件，下推给数据扫描算子（对应查询Explain/Profile中的ScanNode），然后在左表扫描过程中进行裁剪过滤。这种方式大幅降低查询过程中的数据读取和计算，提升了查询性能。Runtime Filter详情，请参见Runtime Filter。

Join Reorder

在多表Join的场景下，Join的顺序对整个Join查询的性能影响很大。

例如有三张表Join，如下图所示。其中ScanA，ScanB，ScanC代表表A，B，C根据查询条件进行完初步的Scan后得到的数据。

在上图的左侧，表A和表B的Scan先进行Join，产生2000行中间结果，然后与表C的Scan再进行Join计算。

在右侧，Join的顺序经过了调整。把表A的Scan先与表C的Scan Join，生成的中间结果只有100，然后再与表B的Scan Join计算。最终的Join结果是一样的，但是它生成的中间结果有20倍的差距，因此会产生一个很大的性能差距。

SelectDB目前支持基于规则的Join Reorder算法。它的逻辑如下。

• 建议优先选择将大表与小表进行Join操作，以便生成尽可能小的中间结果。

• 将有条件的Join表写在查询语句中的靠前位置，尽量让有条件的Join表进行过滤。

• Hash Join的优先级高于Nest Loop Join，因为Hash Join的执行速度明显快于Nest Loop Join。

Join调优方法

Join调优的方法大致按照如下步骤进行。

1. 利用SelectDB本身提供的Profile来定位查询的瓶颈。Profile会记录SelectDB整个查询中的各种信息，这对进行性能调优非常重要。

2. 深入了解SelectDB的Join机制，了解其原理，才能深刻分析其性能较慢的原因。

3. 利用会话变量来修改Join操作的一些行为，以实现Join操作的优化。

4. 查看Query Plan去分析这个调优是否生效。

上述4个步骤描述了标准的Join调优流程。如果在完成了上述流程后仍未见效果，可能需要重新编写Join语句，或者调整数据分布并重新检查整个数据分布是否合理，包括手动调整查询所用的Join语句。然而，这种方式的所花费的成本相对较高，因此在上述方法无效的情况下才需要进一步分析。

Join调优建议

SelectDB Join优化调优的一些建议如下。

• 进行Join的时候，尽量选择同类型或者简单类型的列，同类型列可以减少数据Cast，简单类型本身Join计算就很快。

• 尽量选择Key列进行Join，原因参见Runtime Filter。Key列在延迟物化上有较好的效果。

• 尽量让大表之间的Join以Colocation的方式进行。因为大表之间进行Join会带来很大的网络开销，会使得Shuffle的代价急剧升高。

• 合理使用Runtime Filter。它在Join过滤率高的场景下效果非常显著，但它同时具有一定副作用，需要根据具体的SQL的粒度做开关。

• 涉及到多表Join时，需要去判断Join的合理性。尽量保证左表为大表，右表为小表。这种场景下，Hash Join会优于Nest Loop Join。必要的时可以通过SQL Rewrite，利用Hint去调整Join的顺序。