- 論壇徽章:
- 0
|
|
昨天晚上看了一下Hive HQL的優(yōu)化器。這個(gè)優(yōu)化器相比于GCC4、LLVM的優(yōu)化器而言極其簡(jiǎn)單，但<br>結(jié)構(gòu)也非常地清晰。<br><br>Hive優(yōu)化器結(jié)構(gòu)<br><br>* 總體結(jié)構(gòu)<br> 總體上講，Hive的優(yōu)化器是一種基于Pass的優(yōu)化器，Pass在Hive中稱為Transform。與此同時(shí)，<br>為了便于每個(gè)Transform的編寫，Hive還提供了一個(gè)框架，用于遍歷一遍當(dāng)前DAG圖，并在每個(gè)節(jié)<br>點(diǎn)上執(zhí)行規(guī)則指定的操作。<br> Hive優(yōu)化器在ql/optimizer目錄中，優(yōu)化器的入口是Optimizer類和PhysicalOptimizer。前者<br>主要是在中間語(yǔ)言上進(jìn)行優(yōu)化，后者則是在生成的MapReducer執(zhí)行計(jì)劃上進(jìn)行優(yōu)化。這兩個(gè)優(yōu)化<br>器使用的遍歷框架一樣，之所以區(qū)分兩個(gè)不同的情況，是因?yàn)�，Optimizer處理的DAG圖是HQL語(yǔ)言<br>編譯得到的DAG圖，而PhysicalOptimizer處理的DAG圖是MapReduce任務(wù)構(gòu)成的執(zhí)行計(jì)劃。除此以<br>外，兩者的結(jié)構(gòu)類似，這里僅僅分析Optimizer。<br> 用于遍歷DAG圖的框架在ql/lib目錄下，核心的接口包括Node、GraphWalker、NodeProcessor<br>與NodeProcessorCtx、Rule、Dispatcher幾個(gè)。<br> 在Hive編譯器內(nèi)部，有一個(gè)概念十分重要：ParseContext。這個(gè)類包含了當(dāng)前的IL和相關(guān)的<br>一些信息。每個(gè)Transform都是以一個(gè)ParseContext作為參數(shù)，返回一個(gè)ParseContext作為結(jié)果。<br>可以說(shuō)，ParseContext就是Hive處理HQL的信息的中心。<br><br>* Optimizer<br> 這是Hive優(yōu)化器的驅(qū)動(dòng)類。其實(shí)，更合適的叫法是PassManager或者TransformationManager，<br>因?yàn)樗芾淼膖ransform不一定是“優(yōu)化”，這些transform也可以完成規(guī)格化、階段劃分、代碼<br>生成等其它任務(wù)。<br> Optimizer主要維護(hù)兩個(gè)信息：<br> 1. 當(dāng)前的ParseContext：pctx；<br> 2. 一個(gè)序列的Transform：transformations；<br> Optimizer在初始化時(shí)，向transformations序列中依次加入各個(gè)Transform，在執(zhí)行時(shí)(<br>optimize()方法中)按照順序依次調(diào)用每個(gè)Transform，每個(gè)Transform的輸入都是當(dāng)前Optimizer的<br>pctx，輸出都重新賦值給該pctx。第一個(gè)Transform的pctx是被語(yǔ)法分析器顯式設(shè)置的<br>(setPctx()方法)。<br> Optimizer可能根據(jù)配置信息/選項(xiàng)跳過(guò)（不執(zhí)行）某些Transform。<br><br>* Transform<br> 這是一個(gè)接口，用于表示一個(gè)變換遍。它的定義非常簡(jiǎn)單，僅僅包含一個(gè)方法：<br> ParseContext transform(ParseContext pctx) throws SemanticException;<br> 它的用法從Optimizer中可以看出。<br><br>* 遍歷框架<br> 其實(shí)，有了Optimizer和Transform的定義，已經(jīng)可以寫變換遍了。由于很多變換遍的邏輯都是<br>很相似的：<br> 1. 按照某種順序(如前序、后序等)遍歷整個(gè)IL；<br> 2. 在遍歷過(guò)程中，每到一個(gè)節(jié)點(diǎn)，對(duì)其進(jìn)行處理：<br> 對(duì)一個(gè)節(jié)點(diǎn)的處理可能分為不同的情況，針對(duì)不同的情況進(jìn)行不同的處理。一個(gè)簡(jiǎn)單的<br> 例子就是，針對(duì)不同的節(jié)點(diǎn)（load、map join、filter）做不同的處理。所以，在這里<br> 我們有一個(gè)（規(guī)則 --> 處理函數(shù)）的映射集合，根據(jù)節(jié)點(diǎn)滿足的規(guī)則選擇處理函數(shù)。<br> 有了這些觀察，Hive的遍歷框架就很容易理解了：<br> 1. Node：該接口表示IL中的每個(gè)節(jié)點(diǎn)，被框架使用；<br> 2. GraphWalker：該接口表示一個(gè)遍歷器，它只有一個(gè)接口：<br> void startWalking(Collection<Node> startNodes, HashMap<Node, Object> nodeOutput)<br> throws SemanticException;<br> 其中，startNodes表示從這些節(jié)點(diǎn)開(kāi)始遍歷，遍歷包括這些節(jié)點(diǎn)和它們直接/間接的后繼<br> 節(jié)點(diǎn)；nodeOutput如果不為null，它表示節(jié)點(diǎn)到對(duì)象的一個(gè)映射，這個(gè)對(duì)象就是遍歷中<br> NodeProcessor處理這個(gè)節(jié)點(diǎn)時(shí)的返回值。<br> 在框架中默認(rèn)實(shí)現(xiàn)了DefaultGraphWalker，這是一個(gè)后序遍歷；PreOrderWalker，這是一個(gè)<br> 前序遍歷。<br> 3. NodeProcessor與NodeProcessorCtx：NodeProcessorCtx接口只是一個(gè)標(biāo)記接口，用于表示<br> 某個(gè)節(jié)點(diǎn)處理器的上下文信息。<br> NodeProcessor接口表示一個(gè)節(jié)點(diǎn)處理函數(shù)，它定義了一個(gè)方法：<br> Object process(Node nd, Stack<Node> stack, NodeProcessorCtx, procCtx, <br> Object... nodeOutputs) throws SemanticException;<br> 在遍歷過(guò)程中，如果某個(gè)節(jié)點(diǎn)滿足了該P(yáng)rocessor的規(guī)則，則會(huì)針對(duì)這個(gè)Node調(diào)用這個(gè)函數(shù)。<br> 其中，nd表示滿足規(guī)則的節(jié)點(diǎn)；stack表示當(dāng)前的節(jié)點(diǎn)棧，這個(gè)棧遞歸地包含nd節(jié)點(diǎn)的前驅(qū)<br> 節(jié)點(diǎn)，直到某些startNodes為止；procCtx表示這個(gè)processor的上下文，用于保存這個(gè)<br> 處理函數(shù)特定的、跨節(jié)點(diǎn)的信息；nodeOutput是這個(gè)節(jié)點(diǎn)的所有直接后繼節(jié)點(diǎn)被處理時(shí)<br> process()函數(shù)的返回值。<br> 4. Rule：該接口表示一個(gè)規(guī)則，它最重要的一個(gè)方法是：<br> int cost(Stack<Node> stack) throws SemanticException;<br> 其中，stack是當(dāng)前的節(jié)點(diǎn)棧，stack頂部的節(jié)點(diǎn)就是正在遍歷的節(jié)點(diǎn)。每個(gè)規(guī)則對(duì)應(yīng)一個(gè)<br> 處理函數(shù)。在當(dāng)前所有可用規(guī)則中，cost()返回值最小的規(guī)則是“匹配規(guī)則”。<br> 5. Dispatcher：該接口表示一個(gè)分發(fā)器。如前文所述，每個(gè)Transform都有一組<br> (規(guī)則 --> 處理函數(shù)）的集合，這組集合注冊(cè)給一個(gè)Dispatcher，Dispatcher注冊(cè)給<br> GraphWalker。當(dāng)調(diào)用GraphWalker的startWalking后，GraphWalker會(huì)按定義的順序遍歷<br> 每個(gè)節(jié)點(diǎn)，每遍歷到一個(gè)節(jié)點(diǎn)，就會(huì)針對(duì)它調(diào)用Dispatcher的dispatch()函數(shù)，在這個(gè)函<br> 數(shù)內(nèi)部，Dispatcher會(huì)依次嘗試匹配每個(gè)Rule，最終針對(duì)當(dāng)前節(jié)點(diǎn)調(diào)用匹配到的Rule對(duì)應(yīng)<br> 的NodeProcessor。<br> dispatch()方法和NodeProcessor的process()方法參數(shù)類似，只是沒(méi)有NodeProcessorCtx<br> 參數(shù)。<br> 有了這個(gè)遍歷框架，實(shí)現(xiàn)一個(gè)Transform時(shí)就會(huì)避免很多重復(fù)的代碼。<br><br>* 一個(gè)改進(jìn)點(diǎn)<br> 將Transform組織成樹(shù)的形式，即，一個(gè)Transform可以包含若干個(gè)子Transform。當(dāng)執(zhí)行這種<br>Transform時(shí)，該Transform本身不做什么操作，而是按序執(zhí)行各個(gè)子Transform。同時(shí)，存在一個(gè)<br>TransformCtx，在幾個(gè)子Transform中共享。這是因?yàn)�，一個(gè)頂層的Transform應(yīng)該代表一個(gè)邏輯<br>上語(yǔ)義等價(jià)的變換，這樣就可以方便地啟用/禁用某個(gè)Transform；而一個(gè)變換不一定通過(guò)一個(gè)遍歷<br>就可以完成，它可能包含若干個(gè)（可能被復(fù)用的）遍歷。這種情況用子Transform可以很好的表達(dá)。<br><br> |
|
免費(fèi)注冊(cè)
發(fā)表于 2011-12-21 08:42