Mycat2 優(yōu)化器

前言

本文描述的設(shè)計(jì)細(xì)節(jié)，大部分已經(jīng)實(shí)現(xiàn)，有小部分沒(méi)有完全實(shí)現(xiàn)。

Mycat2減少使用人類理解編寫(xiě)的SQL解析路由和基于經(jīng)驗(yàn)制作的查詢引擎的思路來(lái)實(shí)現(xiàn)查詢引擎,取而代之,使用基于關(guān)系表達(dá)式轉(zhuǎn)換SQL的思路以支持更多甚至是標(biāo)準(zhǔn)SQL，MySQL語(yǔ)法的SQL。使用Java生態(tài)Apache Calcite項(xiàng)目,改造成以接收MySQL方言的SQL,翻譯該SQL變成Mycat算子和查詢物理庫(kù)的SQL。該引擎在設(shè)計(jì)上可以脫離網(wǎng)絡(luò)層獨(dú)立運(yùn)行。

Mycat2使用calcite作為優(yōu)化器實(shí)現(xiàn),優(yōu)化有四個(gè)階段。

第一階段Mycat把MySQL語(yǔ)法的SQL編譯成語(yǔ)法抽象樹(shù),并進(jìn)一步把它編譯成邏輯關(guān)系表達(dá)式，值得注意的是，輯MySQL方言元素以Hint或者特征的形態(tài)保存在表達(dá)式內(nèi)，而不會(huì)以表達(dá)式表示。

第二階段是基于規(guī)則改寫(xiě)邏輯關(guān)系表達(dá)式,把可以下推到Mysql關(guān)系表達(dá)式轉(zhuǎn)換以特殊的節(jié)點(diǎn)保存,該節(jié)點(diǎn)最終執(zhí)行的時(shí)候以SQL表示運(yùn)算。

第三階段是使用基于代價(jià)的優(yōu)化方法把未能下推的,需要在Mycat里運(yùn)算的算子選擇物理算子。

第四階段則進(jìn)一步把物理算子翻譯成對(duì)應(yīng)的執(zhí)行計(jì)劃,執(zhí)行計(jì)劃是以樹(shù)節(jié)點(diǎn)表示的執(zhí)行樹(shù),與執(zhí)行流程是對(duì)應(yīng)的,而且是有狀態(tài)的.而上述的關(guān)系表達(dá)式是不可變對(duì)象,無(wú)狀態(tài)的。上述有微妙的關(guān)系，算子與執(zhí)行器沒(méi)有嚴(yán)格的對(duì)應(yīng)關(guān)系，它們的樹(shù)形狀并不是對(duì)應(yīng)的，但是有轉(zhuǎn)換程序把算子生成執(zhí)行器。

在Mycat2開(kāi)發(fā)的歷史中,使用calcite實(shí)現(xiàn)的查詢引擎有兩個(gè)版本,其技術(shù)特征如下。

第一代查詢引擎

1. 基于邏輯表結(jié)合分片條件翻譯為類似union all語(yǔ)義和多個(gè)物理表
2. 在合適的條件下,上拉Union All算子,相對(duì)地,其它在Union All算子之上的算子會(huì)下推
3. 從葉子節(jié)點(diǎn)開(kāi)始往上遍歷(后序遍歷),計(jì)算每個(gè)節(jié)點(diǎn)的分片屬性,把相同分片屬性的節(jié)點(diǎn)的根節(jié)點(diǎn)記錄,然后把它向下遍歷部變成SQL。

該設(shè)計(jì)最大程度依賴calcite現(xiàn)有功能,而且下推的方法比較直觀，但是僅僅在邏輯關(guān)系表達(dá)式層面做處理,未能深入更深入的優(yōu)化，需要編寫(xiě)更多規(guī)則實(shí)現(xiàn)，而且對(duì)于一些情況難以控制關(guān)系表達(dá)式的改寫(xiě)，另外由于開(kāi)發(fā)時(shí)候?qū)儆谠缙陔A段，未能實(shí)現(xiàn)Mycat自研的執(zhí)行器所以未能使用執(zhí)行成本優(yōu)化,使用calcite的內(nèi)置執(zhí)行器實(shí)現(xiàn)執(zhí)行。它在用戶測(cè)試以及使用中發(fā)現(xiàn)使用Calcite的解釋器執(zhí)行器執(zhí)行效率較低，而代碼生成器的執(zhí)行器難以理解調(diào)試。所以開(kāi)始制作第二代執(zhí)行引擎。

第二代查詢引擎

開(kāi)發(fā)第二代查詢引擎的過(guò)程中，嘗試了很多方案，包括移植1.6的查詢引擎，自研SQL編譯成不支持關(guān)聯(lián)子查詢的表達(dá)式樹(shù)并自研執(zhí)行器，經(jīng)過(guò)多次方案和測(cè)試，保留自研執(zhí)行器。因?yàn)殡y以界定簡(jiǎn)單sql與復(fù)雜sql,可能導(dǎo)致多次編譯,所以拋棄自研的SQL編譯器。為了實(shí)現(xiàn)執(zhí)行器，深入使用Calcite，實(shí)現(xiàn)MycatRel，把關(guān)系表達(dá)式轉(zhuǎn)換為Mycat自研的關(guān)系表達(dá)式類，在此之上再轉(zhuǎn)換成執(zhí)行器。執(zhí)行器保留Caclite的表達(dá)式編譯器,使用代碼生成技術(shù),對(duì)標(biāo)量表達(dá)式生成java代碼，然后動(dòng)態(tài)編譯成類，然后加載為對(duì)象，執(zhí)行。對(duì)于關(guān)系表達(dá)式，則是自己實(shí)現(xiàn)執(zhí)行器，而不使用代碼生成方案，雖然效率有所降低，但是便于調(diào)試，因?yàn)榭紤]到之后可能有替換執(zhí)行器的可能，所以暫時(shí)無(wú)需優(yōu)化至極致。

然后為了實(shí)現(xiàn)對(duì)物理節(jié)點(diǎn)的SQL可控，研究關(guān)系表達(dá)式與SQL的生成規(guī)則，實(shí)現(xiàn)了有效的關(guān)系表達(dá)式下推判斷器。然后為了對(duì)已排序的節(jié)點(diǎn)進(jìn)行規(guī)則優(yōu)化，引入排序特征傳播（相比之下，手動(dòng)的HBT就比較難表達(dá)這些信息了，Hint可能是一個(gè)方向）。后來(lái)再參考阿里DRDS的參數(shù)化思路,實(shí)現(xiàn)參數(shù)化功能原型.最后為了結(jié)合第一代查詢引擎的任意分配配置,基于名字而不是基于下標(biāo)的分表映射方案(第二代原始設(shè)計(jì)是基于下標(biāo)指向拆分的物理表),重新引入第一代查詢引擎的思路,基于規(guī)則判斷,對(duì)于復(fù)雜的SQL,邏輯表編譯成物理表再優(yōu)化。這樣就完成了第二代查詢引擎。

引入?yún)?shù)化

理想的參數(shù)化就是把sql中的直接量提取出來(lái),用參數(shù)化標(biāo)記?替代,sql就變成參數(shù)化模板，把SQL中部分常量以?替換,形成參數(shù)化模板與參數(shù)值,以該參數(shù)化模板為key,查詢緩存是否已經(jīng)有物理算子或者已經(jīng)解析好的SQL抽象語(yǔ)法樹(shù),也就說(shuō)緩存的對(duì)象有兩種.對(duì)于物理算子,一個(gè)參數(shù)化模板可能對(duì)應(yīng)多種物理算子,這是因?yàn)槭褂玫膬?yōu)化方法不同導(dǎo)致的結(jié)果.Mycat會(huì)使用執(zhí)行代價(jià)的物理算子來(lái)執(zhí)行。上面說(shuō)得很理想，但是還是有限制的，在Mycat2里面，暫時(shí)不會(huì)對(duì)offset，limit，以及select item的值進(jìn)行參數(shù)化。前者會(huì)影響生成物理算子，因?yàn)樾袛?shù)對(duì)算子選擇有影響。后者會(huì)影響結(jié)果集類型的生成。

參數(shù)化的MycatView

MycatView這個(gè)名字參考阿里DRDS的View算子，在Mycat2第一代引擎有類似的東西，叫做MycatTransientSQLTableScan,一種臨時(shí)的TableScan,它以sql字符串和數(shù)據(jù)源信息來(lái)構(gòu)造。而MycatView使用關(guān)系表達(dá)式與數(shù)據(jù)分布來(lái)表示，數(shù)據(jù)分布包含兩類，一種是具體的，他們就是已經(jīng)包含具體物理表的信息。一種是需要賦以參數(shù)值才可以得到具體信息，如果不，只能得到全表掃描信息，也就是說(shuō)，MycatView計(jì)算物理表可以是惰性計(jì)算的。理想情況下，一個(gè)參數(shù)化的關(guān)系表達(dá)式，不同的參數(shù)值能影響它掃描分表數(shù)量。

一對(duì)多的MycatView

一般來(lái)說(shuō)，MycatView保存的關(guān)系表達(dá)式是關(guān)于邏輯表的，而物理表信息以數(shù)據(jù)分布來(lái)表示。在分表情況下，一般來(lái)說(shuō)，一個(gè)邏輯表對(duì)應(yīng)多個(gè)物理表。在實(shí)現(xiàn)了參數(shù)化后,關(guān)于邏輯表的關(guān)系表達(dá)式成為了模板的存在，（它也包含參數(shù)標(biāo)記？）在生成執(zhí)行計(jì)劃的時(shí)候,應(yīng)用參數(shù)值,使邏輯表的MycatView擴(kuò)展成多個(gè)分片物理表的關(guān)系表達(dá)式。換句話說(shuō)，使用MycatView‘概括’多個(gè)分片節(jié)點(diǎn)的關(guān)系表達(dá)式,即使用一個(gè)分片表達(dá)式與多個(gè)分片節(jié)點(diǎn)信息,減少規(guī)則重寫(xiě)表達(dá)式存在多個(gè)重復(fù)的改寫(xiě)消耗,設(shè)想,如果有100個(gè)物理表,使用邏輯表編譯成物理表的方法,如果涉及對(duì)這些物理表的關(guān)系表達(dá)式改寫(xiě)則要進(jìn)行100次,而使用MycatView‘概括’只需1次。

具體的MycatView

而對(duì)于復(fù)雜的sql,Mycat可能會(huì)選擇使用物理表擴(kuò)展的方法來(lái)優(yōu)化,這是因?yàn)榉制瑮l件對(duì)算子的形狀影響很大,對(duì)于這個(gè)情況,mycat僅僅緩存sql抽象語(yǔ)法樹(shù),并在規(guī)則優(yōu)化階段就應(yīng)用參數(shù)值,把邏輯表擴(kuò)展成物理表。

過(guò)早優(yōu)化的MycatView

對(duì)于簡(jiǎn)單sql,如果在規(guī)則優(yōu)化階段已經(jīng)得到MycatView,則無(wú)需進(jìn)行物理算子優(yōu)化,直接生成執(zhí)行計(jì)劃,因?yàn)镸ycatView本身就是物理算子。與第一代查詢引擎相比,Mycat2自研了執(zhí)行器,執(zhí)行器與物理算子存在多對(duì)一的關(guān)系,例如就算Sort節(jié)點(diǎn)被代價(jià)優(yōu)化器選擇為MemSort,Mycat在生成執(zhí)行器的時(shí)候發(fā)現(xiàn)帶有l(wèi)imit和排序字段會(huì)編譯成TopN執(zhí)行器,而發(fā)現(xiàn)只有l(wèi)imit時(shí)候則會(huì)僅限制行數(shù)量。

參數(shù)化與預(yù)處理語(yǔ)句

在一般的預(yù)處理語(yǔ)句,用戶提供預(yù)處理語(yǔ)句,預(yù)處理語(yǔ)句通過(guò)特殊的語(yǔ)法或者客戶端使用特殊通訊協(xié)議把預(yù)處理語(yǔ)句發(fā)送到數(shù)據(jù)庫(kù),然后數(shù)據(jù)庫(kù)返回指向該預(yù)處理語(yǔ)句的句柄.當(dāng)客戶端要執(zhí)行這個(gè)預(yù)處理語(yǔ)句的時(shí)候,通過(guò)對(duì)?賦值,然后交給數(shù)據(jù)庫(kù)執(zhí)行.預(yù)處理語(yǔ)句中的?是一種參數(shù)標(biāo)記,一般來(lái)說(shuō),參數(shù)是直接量,它們的參數(shù)類型可以根據(jù)SQL的語(yǔ)法,語(yǔ)義推導(dǎo)出來(lái)出來(lái),但是不一定完全是確定的,因?yàn)閷?shí)際參數(shù)類型取決于實(shí)際值.對(duì)于整個(gè)SQL的結(jié)果集類型,是根據(jù)Select Item表達(dá)式的類型推導(dǎo)出來(lái)的.如此來(lái)說(shuō),整個(gè)結(jié)果集的類型實(shí)際上也是不確定的.

外部參數(shù)化

對(duì)于客戶端相關(guān)的預(yù)處理語(yǔ)句參數(shù),在Mycat的查詢引擎中稱為外部參數(shù),它們就是直接量.對(duì)于把沒(méi)有?參數(shù)化標(biāo)記的SQL轉(zhuǎn)換成帶有?和參數(shù)值的SQL對(duì)象,這個(gè)過(guò)程稱為參數(shù)化.在這里我們把外部參數(shù)相關(guān)的參數(shù)化叫做外部參數(shù)化。

內(nèi)部參數(shù)化

在SQL層面上,不同的SQL產(chǎn)生的邏輯關(guān)系表達(dá)式可能是相似的.把TableScan,Values的算子去掉,它們是相同的。如果把關(guān)系表達(dá)式也用？來(lái)表示，則稱為內(nèi)部參數(shù)化，如果以SQL模板來(lái)表示內(nèi)部化參數(shù)則表名也是？。這樣的SQL模板更為通用。Mycat暫時(shí)沒(méi)有顯式實(shí)現(xiàn)這種方式但有使用這種思路。

不參數(shù)化的直接量

1. 對(duì)物理算子的形態(tài)有很大影響的,比如limit的參數(shù),而且limit的參數(shù)可以計(jì)算結(jié)果集的行數(shù),會(huì)影響物理算子的選擇,所以此類的參數(shù)化止步于物理算子生成之前。
2. 表名（實(shí)際上不能當(dāng)做直接量）,Mycat2沒(méi)有進(jìn)一步把表名用參數(shù)化標(biāo)記表示,而保留邏輯表來(lái)表示表信息,當(dāng)生成執(zhí)行器的時(shí)候,邏輯表信息會(huì)被替換成物理表
3. and/or/in表達(dá)式,Mycat2也沒(méi)有把a(bǔ)nd/or的條件中的直接量以數(shù)組的形式排列,而選擇保持原樣。
4. select item中的直接量

關(guān)聯(lián)子查詢

Calcite在編譯SQL的時(shí)候會(huì)解子查詢，使用join，SemiJoin，Agg替代關(guān)聯(lián)子查詢，最后還有小部分子查詢不能消去，以Correlate的形式存在，對(duì)于這個(gè)算子，Mycat2的執(zhí)行器暫時(shí)不支持（如果以后這種sql確實(shí)有很多需求就考慮支持）。涉及到Correlate的關(guān)系表達(dá)式，要求它的執(zhí)行器的輸入直接具備引用外部上下文變量的功能，具體就是表達(dá)式編譯的時(shí)候，生成的表達(dá)式要求支持變量來(lái)自其所在的關(guān)系表達(dá)式之上的Correlate節(jié)點(diǎn)。

內(nèi)置表

Mycat2支持自定義表數(shù)據(jù)的來(lái)源，具體要自定義開(kāi)發(fā)。暫時(shí)能確定的下推的接口是Filter，Project，Limit，Sort。而對(duì)于元表相關(guān)的，暫時(shí)沒(méi)有實(shí)現(xiàn)下推接口的計(jì)劃。

RBO(基于規(guī)則的優(yōu)化)

SQL經(jīng)過(guò)解析轉(zhuǎn)換成抽象語(yǔ)法樹(shù),然后進(jìn)行語(yǔ)法級(jí)別的規(guī)范化(基于SQL改寫(xiě),化簡(jiǎn)一些稍復(fù)雜表達(dá)式到統(tǒng)一語(yǔ)法),然后基于語(yǔ)法節(jié)點(diǎn)推導(dǎo)對(duì)應(yīng)的值類型.并驗(yàn)證類型轉(zhuǎn)換,最后轉(zhuǎn)換成關(guān)系表達(dá)式。然后關(guān)系表達(dá)式進(jìn)行優(yōu)化階段。Mycat2首先進(jìn)行RBO，使用自定義的規(guī)則，對(duì)關(guān)系表達(dá)式進(jìn)行優(yōu)化。RBO的實(shí)現(xiàn)各式各樣，在Mycat2的RBO實(shí)現(xiàn)中，使用基于Calcite的Hep優(yōu)化器，它對(duì)規(guī)則依次應(yīng)用，直到關(guān)系表達(dá)式不再變化，即優(yōu)化結(jié)束。另一方面，Mycat2也有直接使用前序遍歷結(jié)合后序遍歷關(guān)系表達(dá)式樹(shù)直接進(jìn)行改寫(xiě)的實(shí)現(xiàn)方式，但是最后還是把這種實(shí)現(xiàn)方式直接‘嵌入’到Hep優(yōu)化器之內(nèi)進(jìn)行。這樣實(shí)現(xiàn)的好處是,1.可以利用Hep優(yōu)化器的驗(yàn)證校驗(yàn)節(jié)點(diǎn)類型的功能，檢查錯(cuò)誤。2.統(tǒng)一優(yōu)化規(guī)則的實(shí)現(xiàn)方式，即統(tǒng)一使用Calcite的框架實(shí)現(xiàn)，因此規(guī)則使用上不區(qū)分Hep優(yōu)化器還是volcano優(yōu)化器。但是也會(huì)導(dǎo)致一些問(wèn)題，RBO在優(yōu)化器遇上矛盾的規(guī)則的時(shí)候,可能會(huì)導(dǎo)致規(guī)則之間相互優(yōu)化,導(dǎo)致不能停機(jī)(到達(dá)優(yōu)化限制次數(shù))。最后，Mycat不把RBO的規(guī)則完全放在CBO中，是為了減少CBO中搜索的優(yōu)化空間過(guò)大，Mycat2主要使用場(chǎng)景是TP場(chǎng)景，對(duì)響應(yīng)及時(shí)性要求很高，而優(yōu)化關(guān)系表達(dá)式是需要耗費(fèi)不確定的時(shí)間，為了減少優(yōu)化時(shí)間，所以存在RBO優(yōu)化階段。

總體來(lái)說(shuō)，通過(guò)RBO應(yīng)用一部分邏輯關(guān)系表達(dá)式優(yōu)化的規(guī)則，然后CBO再應(yīng)用物理算子規(guī)則。

CBO(基于成本的優(yōu)化)

Mycat2的CBO主要是完成邏輯關(guān)系表達(dá)式，選擇物理算子，轉(zhuǎn)換到物理算子的任務(wù)。Mycat2在TP場(chǎng)景的設(shè)計(jì)上，CBO并沒(méi)有改寫(xiě)關(guān)系表達(dá)式樹(shù)的形態(tài)，僅僅是邏輯關(guān)系表達(dá)式到物理關(guān)系表達(dá)式的一對(duì)一映射。CBO通過(guò)獲得葉子節(jié)點(diǎn)（數(shù)據(jù)源）的信息，一般是指行數(shù)，然后根據(jù)窮舉使用物理算子的計(jì)算代價(jià)規(guī)則，生成每個(gè)算子的執(zhí)行代價(jià)（一般是行數(shù)，cpu代價(jià)，內(nèi)存代價(jià)），以及物理算子之間的要求，比如一些算子對(duì)后置節(jié)點(diǎn)具有排序要求。綜合這些信息，使用動(dòng)態(tài)規(guī)劃算法，最后組裝出使用物理算子表達(dá)的關(guān)系表達(dá)式。CBO需要統(tǒng)計(jì)組件支持。

生成執(zhí)行器

在生成執(zhí)行器的階段，要求關(guān)系表達(dá)式具有完全的信息，例如，參數(shù)化之后關(guān)系表達(dá)式，不提供其參數(shù)值，這肯定是不能執(zhí)行的。生成器根據(jù)參數(shù)值以及必要的上下文，把還沒(méi)有確定具體分片的View轉(zhuǎn)換成具體的View，并收集涉及參與使用數(shù)據(jù)源。最后還適配不同的執(zhí)行工具，比如proxy的，只支持獲取單一數(shù)據(jù)源的實(shí)現(xiàn)。jdbc的，涉及多個(gè)分片的。

第二代查詢引擎執(zhí)行流程

1. SQL解析成語(yǔ)法抽象樹(shù)->轉(zhuǎn)換成邏輯關(guān)系表達(dá)式
2. 檢查SQL特征,選擇優(yōu)化方式
   1. 優(yōu)化方式1 下推Filter 結(jié)合Filter與邏輯表擴(kuò)展成物理表 上拉Union All語(yǔ)義
   2. 優(yōu)化方式2 下推Filter條件同時(shí)生成MycatView
3. 選擇物理算子
4. 生成執(zhí)行器并執(zhí)行

由于Mysql本身對(duì)于一些語(yǔ)法執(zhí)行效率不高,Mycat在第一代查詢引擎與第二代查詢引擎都有選擇性地(不下推)下推集合操作來(lái)減少M(fèi)ysql執(zhí)行這些sql的效率低下。在第一代查詢引擎中,從葉子節(jié)點(diǎn)開(kāi)始后序遍歷,記錄相同分片目標(biāo)的節(jié)點(diǎn),然后再次后序遍歷,直到遇上不滿足下推條件的節(jié)點(diǎn),然后把它的子節(jié)點(diǎn)翻譯成SQL。

相似地,在第二代查詢引擎中也有類似邏輯,但是不像第一代引擎是有獨(dú)立的翻譯階段,而是與其他RBO規(guī)則一起在相同的優(yōu)化器里進(jìn)行規(guī)則轉(zhuǎn)換,,同時(shí)轉(zhuǎn)換時(shí)候可以傳播排序信息,如果遇上能轉(zhuǎn)換為MegreSort的條件,就會(huì)馬上轉(zhuǎn)換,而無(wú)需在CBO階段中完成.若果MycatView階段在RBO階段已經(jīng)被提升到根節(jié)點(diǎn),那也無(wú)需進(jìn)行CBO了.當(dāng)RBO完成的時(shí)候,根節(jié)點(diǎn)不是物理算子,會(huì)進(jìn)行CRO進(jìn)一步轉(zhuǎn)換成物理算子(第一代查詢引擎沒(méi)有這個(gè)階段),通過(guò)計(jì)算節(jié)點(diǎn)特征和行數(shù)等統(tǒng)計(jì)信息來(lái)選擇物理計(jì)劃。

MycatView的生成規(guī)則

設(shè)計(jì)目標(biāo)是盡量生成簡(jiǎn)單的SQL,同時(shí)讓后端數(shù)據(jù)庫(kù)(Mysql)執(zhí)行一定量的運(yùn)算,總體來(lái)說(shuō),算子應(yīng)該區(qū)分二階段

以MycatView為邊界,MycatView之上的算子為Mycat2執(zhí)行的算子,MycatView之下為MySQL要執(zhí)行的運(yùn)算.MycatView之上的算子能否下推到MycatView之下,一般來(lái)說(shuō)有兩個(gè)規(guī)則

1. 如果MycatView之上的節(jié)點(diǎn)放在MycatView之下的節(jié)點(diǎn)的根節(jié)點(diǎn)之上,是否會(huì)導(dǎo)致整體算子運(yùn)算執(zhí)行效率降低,尤其是MySQL上的執(zhí)行.
2. MycatView之下的算子的類型集合是否已經(jīng)包含MycatView之上的算子類型,如果不存在,則一般可以下推,否則參考下一條規(guī)則
3. MycatView之下的算子從葉子節(jié)點(diǎn)向根節(jié)點(diǎn)遍歷所得的關(guān)系表達(dá)式的順序是否是自然的,這條規(guī)則的另一種表達(dá)是,MycatView之下的關(guān)系表達(dá)式對(duì)應(yīng)的SQL無(wú)需以子查詢來(lái)表達(dá),特殊情況如下
4. 對(duì)于部分能通過(guò)SQL表達(dá)的簡(jiǎn)化關(guān)聯(lián)子查詢?cè)贛ycat中執(zhí)行的下推,直接下推到MycatView
5. 對(duì)于join 全局表,直接下推到MycatView

RBO規(guī)則化轉(zhuǎn)換

基于兩個(gè)節(jié)點(diǎn)的下推判斷,?指任意關(guān)系表達(dá)式

TableScan

TableScan=>MycatView(TableScan)

Filter

Filter(MycatView(Project(?)))≠>
Filter(MycatView(Set(?)))≠>
Filter(MycatView(Agg(?)))=>MycatView(Filter(Agg(?)):group by having語(yǔ)法
Filter(MycatView(Sort(?)))≠>
Filter(MycatView(Filter(?)))≠>MycatView(Filter(?)):需要MycatView之上合拼Filter
Filter(MycatView(Join(?)))=>MycatView(Filter(Join(?)))
Filter(MycatView(TableScan(?)))=>MycatView(Filter(TableScan(?)))

Project

Project(MycatView(Project(?)))=>MycatView(Project(Project(?)):盡量合拼Project
Project(MycatView(Set(?)))≠>
Project(MycatView(Agg(?)))=>MycatView(Project(Agg(?))
Project(MycatView(Sort(?)))≠>
Project(MycatView(Filter(?)))=>MycatView(Project(Filter(?)))
Project(MycatView(Join(?)))=>MycatView(Project(Join(?)))
Project(MycatView(TableScan(?)))=>MycatView(Project(TableScan(?)))

Join

Join(MycatView(Project(?)))≠>
Join(MycatView(Set(?)))≠>
Join(MycatView(Agg(?)))≠>
Join(MycatView(Sort(?)))≠>
Join(MycatView(Filter(?)))≠>
Join(MycatView(Join(?)))=>MycatView(Join(Join(?)))
Join(MycatView(TableScan(?)))=>MycatView(Join(TableScan(?)))

Agg

Agg(MycatView(Project(?)))=>MycatView(Agg(Project(?)))
Agg(MycatView(Set(?)))≠>
Agg(MycatView(Agg(?)))≠>
Agg(MycatView(Sort(?)))≠>
Agg(MycatView(Filter(?)))=>MycatView(Agg(Filter(?)))
Agg(MycatView(Join(?)))=>MycatView(Agg(Join(?)))
Agg(MycatView(TableScan(?)))=>MycatView(Agg(TableScan(?)))

Sort

Sort(MycatView(Project(?)))=>MycatView(Sort(Project(?)))
Sort(MycatView(Set(?)))≠>
Sort(MycatView(Agg(?)))=>MycatView(Sort(Agg(?)))
Sort(MycatView(Sort(?)))≠>
Sort(MycatView(Filter(?)))=>MycatView(Sort(Filter(?)))
Sort(MycatView(Join(?)))=>MycatView(Sort(Join(?)))
Sort(MycatView(TableScan(?)))=>MycatView(Sort(TableScan))

Set

Set(MycatView(Project(?)))≠>
Set(MycatView(Set(?)))≠>
Set(MycatView(Agg(?)))≠>
Set(MycatView(Sort(?)))≠>
Set(MycatView(Filter(?)))≠>
Set(MycatView(Join(?)))≠>
Set(MycatView(TableScan(?)))=>MycatView(Set(TableScan))

Correlate

Correlate(MycatView(Project(?)))≠>
Correlate(MycatView(Set(?)))≠>
Correlate(MycatView(Agg(?)))≠>
Correlate(MycatView(Sort(?)))≠>
Correlate(MycatView(Filter(?)))≠>
Correlate(MycatView(Join(?)))≠>
Correlate(MycatView(TableScan(?)))=>MycatView(Correlate(TableScan))

Mycat物理算子

HBT執(zhí)行也是使用這套物理算子

MycatProject

1. 執(zhí)行投影操作
2. 執(zhí)行表達(dá)式計(jì)算
3. 流式

MycatFilter

1. 執(zhí)行過(guò)濾操作
2. 流式

MycatNestedLoopJoin

1. 當(dāng)其他join實(shí)現(xiàn)無(wú)法被選擇的時(shí)候使用
2. 左側(cè)源流式,右側(cè)數(shù)據(jù)源支持可重復(fù)計(jì)算或者使用臨時(shí)表緩存計(jì)算結(jié)果
3. 兩重循環(huán)計(jì)算

MycatNestedLoopSemipJoin

SemiJoin版本的NestedLoopSemipJoin

MycatHashJoin

1. 用于等值連接的Join
2. 左側(cè)源流式,右側(cè)拉取所有數(shù)據(jù)

MycatSemiHashJoin

SemiJoin版本的MycatHashJoin

MycatBatchNestedLoopJoin(一般關(guān)閉,因?yàn)閮?yōu)化器暫時(shí)沒(méi)有根據(jù)左側(cè)數(shù)據(jù)源得到行統(tǒng)計(jì))

1. 用于左側(cè)數(shù)據(jù)源的結(jié)果數(shù)量較少的情況,右側(cè)是MycatView關(guān)系表達(dá)式,Join有顯式的關(guān)聯(lián)鍵
2. 左側(cè)源流式,右側(cè)源需要是MycatView(轉(zhuǎn)換成LookupExecutor),此MycatView在JDBC數(shù)據(jù)源可以重復(fù)從左側(cè)源得到參數(shù)值應(yīng)用并生成SQL執(zhí)行,支持涉及多個(gè)分片。

MycatSortMergeJoin

1. Join有顯式的等價(jià)關(guān)聯(lián)鍵,并且是inner join.此時(shí)Join的兩個(gè)源的已經(jīng)按照J(rèn)oin key排序,則應(yīng)用MycatSortMergeJoin規(guī)則
2. 兩側(cè)源流式處理
3. 輸出結(jié)果已排序

MycatMergeSemiJoin

SemiJoin版本的MycatHashJoin

MycatHashAgg

1. 當(dāng)其他Agg實(shí)現(xiàn)無(wú)法被選擇的時(shí)候使用

MycatSortAgg

1. 當(dāng)源已對(duì)需要聚合的字段排序,則使用MycatSortAgg替代MycatHashAgg

MycatMemSort

1. 在當(dāng)無(wú)法使用其他排序算子的時(shí)候使用
2. 當(dāng)只有排序字段的時(shí)候,而沒(méi)有offset,limit的時(shí)候,在生成執(zhí)行器時(shí)候會(huì)把數(shù)據(jù)保存到內(nèi)存然后再排序
3. 當(dāng)只有offset,limit的時(shí)候,會(huì)進(jìn)行流式計(jì)算偏移與行數(shù)等價(jià)于MycatLimit算子
4. 當(dāng)同時(shí)有排序字段,offset,limit的時(shí)候,等價(jià)于MycatTopN算子,在生成執(zhí)行器的時(shí)候使用TopN執(zhí)行器

MycatTopN

1. 當(dāng)邏輯關(guān)系表達(dá)式具有排序字段,offset,limit的時(shí)候,應(yīng)用MycatTopN算子
2. 固定內(nèi)存占用空間

MycatMegreSort

1. 當(dāng)MycatView是已經(jīng)排序的時(shí)候,而且MycatView內(nèi)的算子是設(shè)計(jì)多個(gè)分片的,則使用MycatMegreSort合拼這些分片的數(shù)據(jù)
2. 強(qiáng)制使用MycatSortMergeJoin或者M(jìn)ycatSortAgg需要添加Sort算子,則該sort算子會(huì)被轉(zhuǎn)換為MycatMegreSort
3. 當(dāng)出現(xiàn)Sort(UnionAll(Sort(...),Sort(...)))都對(duì)相同的字段排序的時(shí)候,會(huì)轉(zhuǎn)換成MycatMegreSort(UnionAll(Sort(...),Sort(...)))

MycatUnion

1. union all的時(shí)候,使用流式合拼,對(duì)數(shù)據(jù)源依次求值 2, union distinct的時(shí)候使用集合語(yǔ)義,把數(shù)據(jù)拉取到內(nèi)存里運(yùn)算

MycatMinus

1. 求差,使用集合語(yǔ)義,把數(shù)據(jù)拉取到內(nèi)存里面運(yùn)算,mysql語(yǔ)法不支持這個(gè)算子,HBT使用

MycatIntersect

1. 求交集,使用集合語(yǔ)義,把數(shù)據(jù)拉取到內(nèi)存里面運(yùn)算,mysql語(yǔ)法不支持這個(gè)算子,HBT使用

MycatValues

1. 針對(duì)邏輯關(guān)系表達(dá)式中產(chǎn)生的小型臨時(shí)表,or/in表達(dá)式產(chǎn)生的臨時(shí)表,集合運(yùn)算產(chǎn)生的臨時(shí)表使用MycatValues表示,其中HBT也用到了該算子
2. MycatValues等價(jià)與沒(méi)有表信息的表,具有字段信息和在內(nèi)存存放的行數(shù)據(jù)(字面量)

MycatInsert

1. 分表表專用插入算子,把sql參數(shù)化之后得出sql模板,與相應(yīng)的表信息
2. MycatInsert在生成執(zhí)行器的時(shí)候應(yīng)用參數(shù)值,并計(jì)算分片節(jié)點(diǎn)信息,改寫(xiě)sql模板,替換邏輯表為物理表,對(duì)同一個(gè)分片,同一個(gè)分片表的sql分組,得到對(duì)應(yīng)的參數(shù)值組,然后就是使用jdbc api進(jìn)行預(yù)處理的批量插入.批量插入的sql一般會(huì)生成兩種 對(duì)于values(xxx,xxx,xxx),(xxx,xxx,xxx)語(yǔ)法中都是字面量的時(shí)候,Mycat2會(huì)把它們參數(shù)化,得到values(?,?,?)和兩組參數(shù)值. 而對(duì)于values中使用表達(dá)式的情況,比如values(1+1,1),(2,2)這個(gè)情況,參數(shù)化結(jié)果是values(?+?,?),(?,?)和一組參數(shù)值, 當(dāng)生成執(zhí)行器,參數(shù)應(yīng)用的時(shí)候,會(huì)先應(yīng)用參數(shù)值然后把values(?+?,?),(?,?)拆分成兩組values(?+?,?)與(?,?),計(jì)算分片節(jié)點(diǎn),然后再使用jdbc插入
3. 如果MycatInsert僅僅涉及一個(gè)分片的時(shí)候,同時(shí)Mycat2當(dāng)前的事務(wù)模式是proxy的,就會(huì)把sql模板與參數(shù)值結(jié)合生成最終的sql,然后使用proxy api執(zhí)行.
4. 對(duì)于涉及到全局序列號(hào)的生成,mycat會(huì)修改sql模板,如果插入的字段沒(méi)有自增序列,則sql模板補(bǔ)充自增字段.序列號(hào)的值作為預(yù)處理語(yǔ)句的參數(shù)值.

MycatUpdate

1. 對(duì)于普通表,全局表的update,delete,insert,使用該算子表達(dá)
2. 對(duì)于分片表的update,delete也是使用該算子表達(dá)
3. 該算子把sql參數(shù)化,得到sql模板,和待求值的分片信息,當(dāng)生成執(zhí)行器的時(shí)候,應(yīng)用參數(shù)值,得到對(duì)應(yīng)的分片范圍,然后使用物理表替換sql模板中的邏輯表,然后使用jdbc預(yù)處理語(yǔ)句進(jìn)行執(zhí)行
4. 與MycatInsert相同,如果處于proxy模式,則嘗試使用proxy模式執(zhí)行
5. 該算子與MycatInsert的不同點(diǎn)是MycatUpdate的生成的變化點(diǎn)在于分片信息,具體是根據(jù)分片信息修改sql的表名,而其他部分無(wú)需多加處理,而MycatInsert則復(fù)雜得多.
6. 與MycatInsert都是針對(duì)分庫(kù)分表設(shè)計(jì)的算子,最終執(zhí)行的形態(tài)都是sql

MycatTableModify

1. 該算子暫未啟用,用于表示對(duì)查詢結(jié)果的行數(shù)據(jù)修改應(yīng)用到涉及的物理表上的運(yùn)算
2. 涉及的物理表要求配置主鍵信息
3. 該算子也準(zhǔn)備用于表達(dá)內(nèi)置表的修改

MycatView

1. MycatView劃分Mycat運(yùn)算的算子與數(shù)據(jù)庫(kù)運(yùn)算的算子(物理節(jié)點(diǎn)算子)
2. MycatView使用邏輯表的邏輯關(guān)系表達(dá)式與分片具體值無(wú)關(guān)的數(shù)據(jù)分布信息表示,要么是全表信息,要么是參數(shù)化的分布信息,要么是具體的分布信息.對(duì)于參數(shù)化的分布信息,在真正求值的時(shí)候,也就是應(yīng)用參數(shù)值的時(shí)候才產(chǎn)生具體的分布信息.如果無(wú)法找不到有效的分片條件的時(shí)候,就會(huì)使用全表信息,全表信息也是具體的分布信息.特殊地對(duì)于物理表, 分布信息肯定是具體的,分片信息就是一個(gè)分片的,而且關(guān)系表達(dá)式就是物理表相關(guān)的,不包含邏輯表.
3. 與之相對(duì)的是MycatTransientSQLTableScan
4. 當(dāng)MycatView之下涉及多個(gè)分片的時(shí)候,生成執(zhí)行器可能就帶有并行拉取這些分片數(shù)據(jù)的特性,而無(wú)需顯示的Gather算子指定并行

MycatTransientSQLTableScan

1. 使用sql與分片目標(biāo)表達(dá)的數(shù)據(jù)源算子,與MycatView不同的是,MycatTransientSQLTableScan就是具體的sql字符串
2. 沒(méi)有關(guān)系表達(dá)式,而且就是一對(duì)一的,一個(gè)分片目標(biāo)與一個(gè)sql.而MycatView之下可能還涉及多個(gè)分片目標(biāo),但是只有一個(gè)關(guān)系表達(dá)式

建立臨時(shí)表

有一些要求輸入的數(shù)據(jù)源支持重復(fù)計(jì)算（迭代，rewind）的執(zhí)行器，Mycat2在不支持重復(fù)迭代的輸入源的執(zhí)行器會(huì)加上一個(gè)保存行數(shù)據(jù)的包裝器，這個(gè)包裝器會(huì)保存輸入的執(zhí)行器的數(shù)據(jù)，這樣就可以得到支持重復(fù)迭代的執(zhí)行器。

一代與二代的配置不同

在第一代查詢引擎中,全局表配置是任意的,而沒(méi)有關(guān)于普通表的配置.這種設(shè)計(jì)的原因是配置一個(gè)單分片信息的全局表就具備普通表的功能.當(dāng)分片表join全局表的時(shí)候,union的上推和分片sql的計(jì)算能把全局表與join的物理表join,然后合拼,并把相同分片節(jié)點(diǎn)的關(guān)系表達(dá)式變成sql.

而在第二代查詢引擎中,使用自定義的sql生成規(guī)則,對(duì)于全局表的語(yǔ)義,在join總是兩個(gè)子關(guān)系表達(dá)式式,多個(gè)join的時(shí)候總是以二叉樹(shù)的形態(tài)存在的時(shí)候,涉及全局表的join總是能下推的,如果全局表的schema與table名字不一樣,那么還需要計(jì)算對(duì)應(yīng)的物理表是哪個(gè).這樣略顯復(fù)雜,冗余,所以規(guī)定在第二代查詢引擎,全局表總是要存在所有分片,而且?guī)烀砻家恢?包括邏輯表.而對(duì)于普通表,如果采用MycatView的方法,即使是同一個(gè)分片的下推也是要計(jì)算對(duì)應(yīng)的物理表。

全局表,普通表,分片表

在第二代查詢引擎中,要求全局表,普通表的物理庫(kù)名字,物理表名字分別與邏輯庫(kù)名字,邏輯表名字一致.

這樣的設(shè)計(jì)的好處是,mycat對(duì)于非用戶關(guān)心的sql,比如show語(yǔ)句,無(wú)需進(jìn)行sql改寫(xiě)表名,直接發(fā)到對(duì)應(yīng)的物數(shù)據(jù)源上就可以了.更進(jìn)一步的設(shè)計(jì)是指定一個(gè)物理數(shù)據(jù)源專門(mén)處理這些sql.而第一代查詢引擎涉及到了sql改寫(xiě),稍微復(fù)雜.

另外一個(gè)方面,全局表要求每個(gè)數(shù)據(jù)源上都有對(duì)應(yīng)的物理表,而不像1代中,可以任意配置.這是為了與ER表下推全局表做簡(jiǎn)化處理,如果簡(jiǎn)化下推全局表的檢查過(guò)程.對(duì)于普通表,只需檢查sql的涉及的表信息,只有普通表的時(shí)候,直接把原sql發(fā)到數(shù)據(jù)源上即可,更一步的設(shè)計(jì)是固定一個(gè)數(shù)據(jù)源,對(duì)于普通表,或者沒(méi)有配置的表的sql,直接發(fā)到此節(jié)點(diǎn).普通表與沒(méi)有配置的表的區(qū)別是前者顯式制定了他們會(huì)參與分片路由,而后者,一般來(lái)說(shuō),只是進(jìn)行讀寫(xiě)分離處理.對(duì)于分片表,分析出是sql中只有一個(gè)表,而且分析得出的分片算法。

對(duì)于分片表,物理庫(kù)與物理表的名字一般具有規(guī)律,有規(guī)律的名字容易與分片規(guī)則結(jié)合,生成物理表信息.無(wú)論在第一代查詢引擎與第二代查詢引擎中,都有明確指定配置分片信息設(shè)計(jì)傾向.主要原因是有些用戶分庫(kù)分表,有些是先分庫(kù),此時(shí)他們的物理表,名字是相同的,有些用戶是先分表,他們的名字并不相同,還有一些用戶一開(kāi)始就是分庫(kù)分表,然后選擇分庫(kù)來(lái)擴(kuò)展性能.加上有些用戶的系統(tǒng)是已經(jīng)有分片的設(shè)計(jì),后來(lái)再使用Mycat做分庫(kù)分表,有自己的表名規(guī)則.情況比較復(fù)雜,所以mycat在配置分片表,一般要求配置所有的存儲(chǔ)節(jié)點(diǎn)。

關(guān)于分片算法

1. 分片算法是根據(jù)分片條件計(jì)算出分片信息的對(duì)象,而分片信息一般就是指向數(shù)據(jù)源,物理庫(kù),物理表信息的對(duì)象,Mycat會(huì)使用此信息對(duì)sql進(jìn)行改寫(xiě),一般來(lái)說(shuō)一個(gè)分片信息只涉及一個(gè)表信息,結(jié)合上述的ER表下推,就可以理解這個(gè)涉及多表下推的復(fù)雜。
2. 配置文件中dataNodes是供分片算法提供全表掃描的信息,而分片算法可以根據(jù)實(shí)際情況,比如根據(jù)分片值得出物理庫(kù),物理表名.當(dāng)在條件中找不到分片值的時(shí)候,使用全表掃描.Mycat2的分片算法的接口接收完整的條件表達(dá)式,用戶可以根據(jù)實(shí)際情況寫(xiě)分片算法實(shí)現(xiàn)計(jì)算分片。

關(guān)于DataNode

Mycat2總體設(shè)計(jì)上模糊了在1.6中dataNode的概念,并不明確.在1.6中,dataNode數(shù)據(jù)源和物理庫(kù)名為固定信息,而要求表名在路由中改寫(xiě)(Mycat先去掉sql中的庫(kù)名.分庫(kù)不改寫(xiě)表名,分表改寫(xiě)表名),往大一點(diǎn)的方向來(lái)說(shuō),這個(gè)dataNode強(qiáng)調(diào)了節(jié)點(diǎn)這個(gè)概念,而固定物理庫(kù)名實(shí)際上是路由的改寫(xiě)要求,.而在2.0中一個(gè)dataNode在配置中體現(xiàn)就是表分片(以后考慮配置中把dataNode更名，減少混亂).即其中一個(gè)分表,無(wú)論他是在一個(gè)數(shù)據(jù)源上還是在不同的物理庫(kù).在Mycat2的早期sql生成機(jī)制中,如果只涉及一個(gè)數(shù)據(jù)源的sql,就使用union all合拼sql,也就是說(shuō),無(wú)論跨庫(kù)還是跨表,總能把查詢邏輯表的sql翻譯成查詢多個(gè)物理表的一條sql.但是由于mysql的執(zhí)行機(jī)制問(wèn)題,性能并沒(méi)有顯著提高.所以Mycat2顯著的設(shè)計(jì)是默認(rèn)對(duì)于涉及多個(gè)物理表的查詢,優(yōu)先并行拉取多個(gè)數(shù)據(jù)源的數(shù)據(jù),而使用union all合拼同一個(gè)數(shù)據(jù)源的結(jié)果集則是次要考慮。