Mycat2 JoinClustering

1.17版本的實(shí)現(xiàn)

Mycat2在1.17開始正式支持JoinClustering,該名字來自于PolarDB-X的JoinClustering.它對分庫分表類數(shù)據(jù)庫的join下推至關(guān)重要.Mycat2對其理解后進(jìn)行開源實(shí)現(xiàn).

它是SQL重寫技術(shù),優(yōu)化目標(biāo)是生成更優(yōu)的存儲節(jié)點(diǎn)執(zhí)行的SQL,使更多Join運(yùn)算在存儲節(jié)點(diǎn)運(yùn)算,大大減少M(fèi)ycat2的運(yùn)算.它是基于Join Reorder技術(shù)進(jìn)行構(gòu)建的.Mycat2的SQL重寫器在遇到不能應(yīng)用兩表下推規(guī)則(任意表+全局表),再判斷是否是inner join,則啟動代價(jià)優(yōu)化器,使用

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規(guī)則 然后在上述規(guī)則作用下對新的join關(guān)系表達(dá)式進(jìn)行ER表規(guī)則應(yīng)用

比如

t2(分片表),t1(單表),t3(分片表),t2和t3屬于父子表關(guān)系,具有相同的數(shù)據(jù)分布

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

此處的id實(shí)際上它們的值是相同的,輸出值實(shí)際上可以來自三個表t2,t1,t3

在沒有JoinClustering的情況

t2 join t1 join t3,因?yàn)閠2和t3沒有相鄰(因?yàn)閠1的阻隔),導(dǎo)致無法應(yīng)用ER表下推規(guī)則

在有JoinClustering的情況

代價(jià)優(yōu)化器會交換 表的順序,生成t2 join t3 join t1并成功使用ER表下推規(guī)則

1.18版本(2021-5-11以后)實(shí)現(xiàn)

1.17版本基于COMMUTE規(guī)則實(shí)現(xiàn),存在優(yōu)化十分耗時(shí)的問題,因?yàn)樗乃阉骺臻g大(混合了邏輯優(yōu)化與物理優(yōu)化),雖然使用了執(zhí)行計(jì)劃管理可以手動持久化已有的執(zhí)行計(jì)劃,省去優(yōu)化階段,這樣可以暫時(shí)解決問題,所以在1.18對Join的優(yōu)化進(jìn)一步探索,實(shí)現(xiàn)了基于MultiJoin的reorder,它在規(guī)則優(yōu)化器就可以使用,基于一定規(guī)則,把多個join轉(zhuǎn)換成MutilJoin來表達(dá),然后在MutilJoin的形式下進(jìn)行邏輯優(yōu)化

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

JoinClustering實(shí)際上就是一個獨(dú)立的CBO階段

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

優(yōu)化流程

JOIN_TO_MULTI_JOIN

多個join轉(zhuǎn)換成多個Multi join.因?yàn)閖oin不同的樹形,我們暫時(shí)只關(guān)注inner join的這一種

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

MYCAT_HEP_JOIN_CLUSTERING

進(jìn)行JoinClustering的規(guī)則.與一般的Join Reorder不同,Join Reorder關(guān)注執(zhí)行器層面跑得更快更好,它們關(guān)注統(tǒng)計(jì)信息的行數(shù),選擇性的信息.而在分庫分表數(shù)據(jù)庫中,JoinClustering關(guān)注把相同存儲節(jié)點(diǎn)相同的表靠近在一起,這樣可以把更多join運(yùn)算在存儲節(jié)點(diǎn)中進(jìn)行,所以它關(guān)注輸入的關(guān)系表達(dá)式的順序.

input reorder

對輸入的關(guān)系表達(dá)式進(jìn)行排序,排序的依據(jù)是View的數(shù)據(jù)分布,局部來說,把可以下推的表相鄰排列.整體來說,把可以下推的表往左排,不可以下推的表往右排.如果發(fā)現(xiàn)排序后,輸入的順序沒有改變,則優(yōu)化結(jié)束.

field reorder 因?yàn)檩斎氲年P(guān)系表達(dá)式順序改變了,所以條件表達(dá)式對輸入字段的引用需要重新計(jì)算,調(diào)整正確即可.然后我們對條件進(jìn)行的字段一些簡化.目的是調(diào)整字段的值的依賴.

應(yīng)用傳遞性(前提是等價(jià)關(guān)系,不滿足等價(jià)關(guān)系的條件表達(dá)式不進(jìn)行優(yōu)化)

(a.id = b.id) and (b.id = c.id)→(a.id = b.id) and (a.id = c.id) 根據(jù)輸入的關(guān)系表達(dá)式的順序?qū)ψ侄芜M(jìn)行排序

順序: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

因?yàn)閷斎腠樞蚋淖兞?所以join的字段類型順序也改變了,所以添加一個Project表達(dá)式把新生成的MutilJoin的字段信息投影至與原表達(dá)式相同的類型.

MULTI_JOIN_TO_JOIN

最后,使用該規(guī)則把MULTI_JOIN還原成JOIN.

總結(jié)

使用Multi join可以僅僅關(guān)注邏輯優(yōu)化中的join節(jié)點(diǎn)部分進(jìn)行轉(zhuǎn)換,使用幾個邏輯優(yōu)化規(guī)則就可以進(jìn)行優(yōu)化,把優(yōu)化范圍限制在Multi join節(jié)點(diǎn)的范圍之內(nèi),大大減少了優(yōu)化耗時(shí).

例子

邏輯SQL:

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

生成執(zhí)行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

生成執(zhí)行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`)))`