Mycat2 JoinClustering

1.17版本的实现

Mycat2在1.17开始正式支持JoinClustering,该名字来自于PolarDB-X的JoinClustering.它对分库分表类数据库的join下推至关重要.Mycat2对其理解后进行开源实现.

它是SQL重写技术,优化目标是生成更优的存储节点执行的SQL,使更多Join运算在存储节点运算,大大减少Mycat2的运算.它是基于Join Reorder技术进行构建的.Mycat2的SQL重写器在遇到不能应用两表下推规则(任意表+全局表),再判断是否是inner join,则启动代价优化器,使用

JOIN ASSOCIATE: (a JOIN b) JOIN c) → (a JOIN (b JOIN c)) JOIN COMMUTE:``(a JOIN b)→(b JOIN a) JOIN PUSH THROUGH JOIN: (A join B) join C ``→`` (A join C) join B

作为Join Reorder规则 然后在上述规则作用下对新的join关系表达式进行ER表规则应用

比如

t2(分片表),t1(单表),t3(分片表),t2和t3属于父子表关系,具有相同的数据分布

select t2.id from t2 join t1 on t2.id = t1.id join t3 on t1.id = t3.id;

此处的id实际上它们的值是相同的,输出值实际上可以来自三个表t2,t1,t3

在没有JoinClustering的情况

t2 join t1 join t3,因为t2和t3没有相邻(因为t1的阻隔),导致无法应用ER表下推规则

在有JoinClustering的情况

代价优化器会交换 表的顺序,生成t2 join t3 join t1并成功使用ER表下推规则

1.18版本(2021-5-11以后)实现

1.17版本基于COMMUTE规则实现,存在优化十分耗时的问题,因为它的搜索空间大(混合了逻辑优化与物理优化),虽然使用了执行计划管理可以手动持久化已有的执行计划,省去优化阶段,这样可以暂时解决问题,所以在1.18对Join的优化进一步探索,实现了基于MultiJoin的reorder,它在规则优化器就可以使用,基于一定规则,把多个join转换成MutilJoin来表达,然后在MutilJoin的形式下进行逻辑优化

1.17的JoinClustering阶段
Logical RBO →View RBO→ JoinClustering CBO→Physical CBO

JoinClustering实际上就是一个独立的CBO阶段

1.18的JoinClustering阶段
Logical RBO →JoinClustering RBO→Logical RBO →View RBO→Physical CBO

优化流程

JOIN_TO_MULTI_JOIN

多个join转换成多个Multi join.因为join不同的树形,我们暂时只关注inner join的这一种

A JOIN B → MJ(A, B)A JOIN B JOIN C → MJ(A, B, C)

MYCAT_HEP_JOIN_CLUSTERING

进行JoinClustering的规则.与一般的Join Reorder不同,Join Reorder关注执行器层面跑得更快更好,它们关注统计信息的行数,选择性的信息.而在分库分表数据库中,JoinClustering关注把相同存储节点相同的表靠近在一起,这样可以把更多join运算在存储节点中进行,所以它关注输入的关系表达式的顺序.

input reorder

对输入的关系表达式进行排序,排序的依据是View的数据分布,局部来说,把可以下推的表相邻排列.整体来说,把可以下推的表往左排,不可以下推的表往右排.如果发现排序后,输入的顺序没有改变,则优化结束.

field reorder 因为输入的关系表达式顺序改变了,所以条件表达式对输入字段的引用需要重新计算,调整正确即可.然后我们对条件进行的字段一些简化.目的是调整字段的值的依赖.

应用传递性(前提是等价关系,不满足等价关系的条件表达式不进行优化)

(a.id = b.id) and (b.id = c.id)→(a.id = b.id) and (a.id = c.id) 根据输入的关系表达式的顺序对字段进行排序

顺序:a,c,b

(a.id = b.id) and (b.id = c.id)→(a.id = c.id) and (a.id = b.id) 最终得到

a join c : (a.id = c.id) a join b: (a.id = b.id) → (a join c join b):(a.id = c.id) and (a.id = b.id)

field adjust

因为对输入顺序改变了,所以join的字段类型顺序也改变了,所以添加一个Project表达式把新生成的MutilJoin的字段信息投影至与原表达式相同的类型.

MULTI_JOIN_TO_JOIN

最后,使用该规则把MULTI_JOIN还原成JOIN.

总结

使用Multi join可以仅仅关注逻辑优化中的join节点部分进行转换,使用几个逻辑优化规则就可以进行优化,把优化范围限制在Multi join节点的范围之内,大大减少了优化耗时.

例子

逻辑SQL:

select * from db1.sharding s join db1.global g  on s.id = g.id join  db1.er e  on  e.id = g.id

生成执行SQL模板

MycatView(distribution=[shardingTables=db1.sharding,db1.er,globalTables=db1.global]
`SELECT *  FROM db1.sharding INNER JOIN db1.global ON (`sharding`.`id` = `global`.`id`)      INNER JOIN db1.er ON (`global`.`id` = `er`.`id`)`

逻辑SQL:

select t2.id from db1.sharding t2 join db1.normal t1 on t2.id = t1.id join db1.er l2 on t1.id = l2.id

生成执行SQL模板

MycatProject(id=[$0])    
    MycatHashJoin(condition=[=($0, $1)], joinType=[inner])      
  MycatView(distribution=[shardingTables=db1.sharding,db1.er])      
  MycatView(distribution=[normalTables=db1.normal])  
`
SELECT `sharding`.`id`  FROM db1.sharding      INNER JOIN db1.er ON (`sharding`.`id` = `er`.`id`)`


...
`(SELECT `sharding_0`.`id`     FROM db1_0.sharding_0         INNER JOIN db1_0.er_0 ON (`sharding_0`.`id` = `er_0`.`id`)     UNION ALL     SELECT `sharding_1`.`id`     FROM db1_0.sharding_1         INNER JOIN db1_0.er_1 ON (`sharding_1`.`id` = `er_1`.`id`)))`