概要

查詢(xún)優(yōu)化是數(shù)據(jù)庫(kù)系統(tǒng)里面特別關(guān)鍵的一個(gè)組件, 曾經(jīng)有一個(gè)老外，我也不知道是誰(shuí)說(shuō)過(guò):

Query optimizer is where the power of a database lies. （查詢(xún)優(yōu)化器是數(shù)據(jù)庫(kù)的強(qiáng)大之處。）

可見(jiàn)查詢(xún)優(yōu)化的重要性，查詢(xún)優(yōu)化在 Presto 里面主要是由 IterativeOptimizer 完成的，今天我們來(lái)分析下 IterativeOptimizer。

PlanOptimizer

在介紹 IterativeOptimizer 之前我們先來(lái)介紹一下 PlanOptimizer。在 PlanOptimizer 里面只有一個(gè)接口，給你一個(gè)輸入 PlanNode 以及一些輔助的參數(shù)，你給出一個(gè)優(yōu)化后的 PlanNode:

public interface PlanOptimizer {
   PlanNode optimize(PlanNode plan,
           Session session,
           TypeProvider types,
           SymbolAllocator symbolAllocator,
           PlanNodeIdAllocator idAllocator);
}

這個(gè)接口實(shí)現(xiàn)一般都要實(shí)現(xiàn)一個(gè) SimplePlanRewriter 這個(gè)使用了 Visitor 設(shè)計(jì)模式的類(lèi), 找到你要處理的節(jié)點(diǎn)進(jìn)行 visit 。用起來(lái)其實(shí)蠻復(fù)雜的，關(guān)鍵是它把多個(gè)優(yōu)化策略揉到一個(gè)類(lèi)里面去做了，比如 LimitPushDown 這個(gè)實(shí)現(xiàn)，它是要找 LimitNode 進(jìn)行優(yōu)化，它里面實(shí)現(xiàn)了很多規(guī)則:

• 如果 LimitNode 的上游還有一個(gè) LimitNode 那么把這兩個(gè) LimitNode 進(jìn)行合并。如果合并之后要 LimitNode 的 count 是 0，那么直接把這個(gè) LimitNode 節(jié)點(diǎn)換成一個(gè)空的 Values 節(jié)點(diǎn)。
• 如果 LimitNode 的上游有一個(gè) TopN 節(jié)點(diǎn)，那么把 Limit 和 TopN 節(jié)點(diǎn)進(jìn)行合并。
• 如果碰到 Union 節(jié)點(diǎn)，那么把 Limit 節(jié)點(diǎn)推到 Union 下面去。
• 等等。

可以看出來(lái)一個(gè)優(yōu)化實(shí)現(xiàn)里面糅雜了很多條規(guī)則。

不管出于什么理由，把很多不那么相關(guān)的邏輯揉在一起都是不好的。

IterativeOptimizer

PlanOptimizer 的缺點(diǎn)正是 IterativeOptimizer 改進(jìn)的地方，IterativeOptimizer 在 PlanOptimizer 上面又包裝了一層，IterativeOptimizer 把每條優(yōu)化規(guī)則抽象出單獨(dú)的類(lèi): Rule。讓我們做查詢(xún)優(yōu)化的時(shí)候只需要去編寫(xiě) Rule 而不需要去 Optimizer， 不需要去實(shí)現(xiàn) Visitor 模式，真的是太棒了。

Rule 的主要的接口是這樣的:

public interface Rule<T>{
   /**
    * 你要優(yōu)化的Plan的模式是怎么樣的?
    */
   Pattern<T> getPattern();

   /**
    * 匹配你模式的PlanNode找到你，你去優(yōu)化吧。
    */
   Result apply(T node, Captures captures, Context context);
}

首先它讓你指定你要優(yōu)化的 Plan 的結(jié)構(gòu)是怎么樣的。比如:

 找到兩個(gè)相鄰 LimitNode 節(jié)點(diǎn)的結(jié)構(gòu)。

這個(gè)在 presto-matching 庫(kù)的幫助下很好實(shí)現(xiàn)(presto-matching庫(kù)我們?cè)谏弦黄恼隆?a href="http://www.itdecent.cn/p/45d5040f8ff1" target="_blank">Presto源碼分析之模式匹配》專(zhuān)門(mén)分析過(guò)。):

   private static final Capture<LimitNode> CHILD = newCapture();
   private static final Pattern<LimitNode> PATTERN =
       limit().with(source().matching(limit().capturedAs(CHILD)));
   @Override
   public Pattern<LimitNode> getPattern() {
       return PATTERN;
   }

找到之后我們?cè)?apply 方法里面來(lái)實(shí)現(xiàn) LimitNode 合并的操作，也非常的簡(jiǎn)單。

   @Override
   public Result apply(LimitNode parent, Captures captures, Context context) {
       // 這個(gè) child 是那個(gè)上游的 LimitNode
       LimitNode child = captures.get(CHILD);
       return Result.ofPlanNode(
               new LimitNode(
                       parent.getId(),
                       child.getSource(),
                       // 合并成一個(gè) LimitNode 取比較小的那個(gè) count
                       Math.min(parent.getCount(), child.getCount()),
                       parent.isPartial()));
   }

不知道大家是什么感覺(jué)，反正我在閱讀 Presto Optimizer 代碼之前沒(méi)有想到進(jìn)行查詢(xún)優(yōu)化的邏輯可以寫(xiě)得這么簡(jiǎn)單。這就是優(yōu)秀框架的力量啊。

可變的執(zhí)行計(jì)劃: Memo

在 IterativeOptimizer 對(duì) PlanNode 進(jìn)行改寫(xiě)的過(guò)程中還有一個(gè)很重要的類(lèi): Memo。我們知道 Presto 源代碼里面有一點(diǎn)做得很好，就是對(duì)象都是能不可變(immutable)就不可變，這讓程序更可預(yù)期，潛在的 bug 也會(huì)少很多，同時(shí)也有一些缺點(diǎn): 不可變導(dǎo)致要改變一個(gè)Plan結(jié)構(gòu)的一部分變得很復(fù)雜，你必須重新構(gòu)造整個(gè) Plan ，因此為了執(zhí)行計(jì)劃優(yōu)化的方便性以及性能的考慮，在對(duì)PlanNode進(jìn)行優(yōu)化前會(huì)把 PlanNode 轉(zhuǎn)化成一個(gè)可變的對(duì)象: Memo, 下面我們來(lái)詳細(xì)分析下Memo這個(gè)類(lèi)。

說(shuō)實(shí)話(huà) Memo 這個(gè)類(lèi)名我覺(jué)得起的特別不好，光看類(lèi)名完全跟可變的PlanNode聯(lián)系不上，如果讓我起名字的話(huà)，我覺(jué)得還不如叫 MuttablePlanNode 來(lái)的直觀。

在 Memo 里面，所有的 PlanNode 被一個(gè)新的類(lèi) GroupReference 包裝一層，一個(gè)原始的計(jì)劃:

原始的PlanNode結(jié)構(gòu)

會(huì)被包成下面的結(jié)構(gòu):

包裝過(guò)后的PlanNode結(jié)構(gòu)

這里 GroupReference 仍然是不可變的，但是 Group 是可變的，PlanNode 優(yōu)化的過(guò)程其實(shí)就是通過(guò)遍歷 GroupReference 樹(shù)，不斷修改對(duì)應(yīng)的 Group 里面的 PlanNode 的過(guò)程。值得注意的是，這個(gè)樹(shù)的結(jié)構(gòu)也可能會(huì)被修改，比如上面我們提到過(guò)的那個(gè)優(yōu)化策略：

如果有兩個(gè)相鄰的 LimitNode 節(jié)點(diǎn)，那么把他們合并成一個(gè) LimitNode 節(jié)點(diǎn)，取比較小的那個(gè)LimitNode的值作為最終的 LimitNode。

因此存在著一開(kāi)始存在的 Group 隨著優(yōu)化過(guò)程對(duì)整個(gè) PlanNode 結(jié)構(gòu)的修改，最后不再被任何其它 Group 引用，因而需要?jiǎng)h除掉的情況，因此 Memo 里面有個(gè)小小的垃圾回收的策略: 每個(gè) Group對(duì)象上除了記錄它的原始的 PlanNode 之外，還會(huì)有一個(gè)引用它的 Group 的記錄:

   private Multiset<Integer> incomingReferences = HashMultiset.create();

它每次操作一個(gè)節(jié)點(diǎn)的時(shí)候會(huì)對(duì)相關(guān)的節(jié)點(diǎn)做個(gè)引用計(jì)數(shù) + 垃圾回收的維護(hù):

     // 增加新節(jié)點(diǎn)(node)的引用計(jì)數(shù)
   incrementReferenceCounts(node, group);
   // 更新節(jié)點(diǎn)
   getGroup(group).membership = node;
   // 減少舊節(jié)點(diǎn)(old)相關(guān)節(jié)點(diǎn)的引用計(jì)數(shù)，如果引用計(jì)數(shù)為0，則把對(duì)應(yīng)的Group刪掉
   decrementReferenceCounts(old, group);

感想

剛學(xué)習(xí)設(shè)計(jì)模式的時(shí)候動(dòng)不動(dòng)就想把設(shè)計(jì)模式用到代碼里面去，這樣代碼會(huì)顯得高大上一點(diǎn)。當(dāng)然，在代碼里面用設(shè)計(jì)模式?jīng)]錯(cuò)，它可以有效地隔離變化，讓代碼更具有可維護(hù)性、可擴(kuò)展性。但是就像寫(xiě)文章一樣，堆滿(mǎn)華麗辭藻的文章絕不是什么好文章，堆滿(mǎn)設(shè)計(jì)模式的代碼也絕不是什么好的代碼。

寫(xiě)代碼又像武俠小說(shuō)里面的俠客學(xué)習(xí)武功一樣，一開(kāi)始你什么招式也不會(huì)，誰(shuí)也打不過(guò)，后來(lái)你學(xué)了很多招式，能打過(guò)很多人了，但是仍然不是絕頂高手，所謂的絕頂高手是要在把所有招式都學(xué)過(guò)之后，再把所有的招式都忘記掉，真正要用的時(shí)候隨心所至信手拈來(lái)。

設(shè)計(jì)模式就相當(dāng)于武功里面的招式，真正的高手應(yīng)該是學(xué)過(guò)之后忘掉它，在真正需要的的時(shí)候信手拈來(lái)用到合適的地方去，這個(gè)合適的地方就是框架，讓普通開(kāi)發(fā)看不到，這樣普通開(kāi)發(fā)同學(xué)就可以集中精力寫(xiě)真正的業(yè)務(wù)代碼了, 我們每天要花大量時(shí)間去寫(xiě)的應(yīng)該是業(yè)務(wù)代碼。

在 Presto 查詢(xún)優(yōu)化的模塊里面，框架代碼指的是 PlanOptimizer、IterativeOptimizer, 這里面該用 Visitor 模式就用 Visitor 模式，一旦有了這個(gè)框架之后，我們真正業(yè)務(wù)是調(diào)優(yōu)查詢(xún)性能，這時(shí)候只需要去寫(xiě) Rule 就好了，而 Rule 的實(shí)現(xiàn)都是平鋪直敘的邏輯，沒(méi)有什么復(fù)雜的模式，用戶(hù)用起來(lái)會(huì)覺(jué)得很方便好用。

再引申一點(diǎn)，一個(gè)好的 API 一定是平鋪直敘的，不需要讓用戶(hù)使用什么設(shè)計(jì)模式的。