概要

Presto里面有個小小的模式匹配的庫: presto-matching ，這個庫很小，一共就15個文件，但是在 Presto 里面作用還蠻大的，Presto 里面很關(guān)鍵的查詢優(yōu)化(Query Optimization)就是要靠這個小小的庫來識別性能有問題的查詢計劃，替換成性能更好的計劃。

在這篇文章里，我們會詳細介紹一下 presto-matching 庫里面的幾個主要概念: Pattern, Match, Matcher、 整個庫的設(shè)計思路以及它在 Presto 查詢優(yōu)化里面的具體應(yīng)用。

源碼分析

presto-matching 里面幾個主要的類以及相互間的關(guān)系如下:

presto-matching 關(guān)鍵類圖

Pattern

Pattern 在庫里面是一個抽象類，它主要起了四方面的作用：首先它定義了模式的結(jié)構(gòu)；其次定義了模式的行為；再次它定義了常用模式構(gòu)造的方法，形成了一個小型的DSL；最后它定義了模式與匹配之間的橋梁方法: matches 。

Pattern的結(jié)構(gòu)

我們先來看看模式的結(jié)構(gòu)。模式的結(jié)構(gòu)是這樣的, 模式本身里面到底有哪些屬性是各個具體的Pattern 子類實現(xiàn)自己定義的，比如 EqualsPattern 里面有一個 expectedValue , 用來表示要判定是否相等的值是多少；FilterPattern 里面會有一個 predicate 字段，用來判定對象需要符合的條件。

而所有的 Pattern 里面都會有一個 previous 的字段，這個字段指向上一個模式，這樣我們雖然只拿到了一個 Pattern 對象，但是其實它背后可能串了一個鏈的對象，這些模式之間的關(guān)系是“并且”的關(guān)系，我們可以稱之為“復(fù)合Pattern”。

復(fù)合Pattern結(jié)構(gòu)

Pattern的行為

其次它定義了模式的行為, 主要是兩個抽象方法:

    Match<T> accept(Matcher matcher, Object object, Captures captures);

    void accept(PatternVisitor patternVisitor);

第一個 accept 方法是模式匹配的場景，它的第一個參數(shù) Matcher 是具體執(zhí)行模式識別的核心類，后面會詳細介紹，第二個參數(shù) object 是要被匹配的對象，第三個參數(shù) captures 相當于很多類庫里面的 Context 對象，它的作用是保存在模式識別的過程中我們關(guān)心的某個子節(jié)點，后續(xù)可能會對這個子節(jié)點進行進一步處理，比如說替換掉以優(yōu)化性能。

第二個 accept 方法目前主要的使用場景是對 Pattern 本身進行遍歷以實現(xiàn) toString , 現(xiàn)在唯一的 PatternVisitor: DefaultPrinter 是做這個的。

這里其實是對 Pattern 這一個對象實現(xiàn)了兩套 Visitor 的模式，一套用來進行模式匹配，一套用來進行通用的結(jié)構(gòu)遍歷。

Pattern DSL

Pattern 類的第三個作用就是定義了一些常用的模式構(gòu)造的方法，比如:

• 匹配任何對象的 any()
• 匹配指定類型對象的 typeOf()
• 匹配指定條件的 matching()
• 對象的屬性匹配某種條件的 with()
• 捕獲某個節(jié)點的 capturedAs()

從這個角度上看，Pattern 這個類其實扮演了模式匹配庫的門面角色，雖然 Pattern 有幾個具體的子類，但是這個庫的用戶不會直接去用，而都是使用 Pattern 里面的這些工廠方法，這樣的好處有兩個，一是隔離了變化，這樣 Pattern 的子類名、里面具體的實現(xiàn)邏輯可以自由變化而不用擔心影響到用戶；二是這些工廠方法用起來很簡潔，使用的時候看起來像是在手寫語法樹，有點DSL的感覺。

給大家看個例子，下面的這段代碼表示要尋找一個 Project 節(jié)點，這個 Project 節(jié)點下面(source)要有一個 Scan 節(jié)點：

project().with(
    source().matching(
        scan()
    )
)

可以看出，非常的形象，從代碼可以直接看出要尋找的模式是怎么樣的。而如果改成讓你直接用Pattern 子類來實現(xiàn)同樣邏輯的話，大概是這樣的:

new FilterPattern<>(
    new TypeOfPattern<>(ScanNode.class)
    new WithPattern<>(
        new Property<>("source", SingleSourceRelNode::getSource)
        new TypeOfPattern<>(ProjectNode.class)
    )
)

是不是覺得很不直觀，很累贅，一點都不想用了吧？沒錯，這就是DSL的力量。沒有對比就沒有傷害啊。

把模式與匹配邏輯連接起來

Pattern 的最后一個主要作用是定義了把模式與匹配的邏輯連接起來的橋梁方法: matches():

public boolean matches(Object object)
{
    return DEFAULT_MATCHER.match(this, object).isPresent();
}

從代碼實現(xiàn)就可以看出, matches 方法的作用對于給定的一個對象，判斷它是否能匹配當前的Pattern。

Pattern的子類

目前Pattern的子類主要有5個:

• TypeOfPattern: 檢測某個節(jié)點是不是指定類型的節(jié)點，比如是不是一個 TableScan 節(jié)點，是不是一個 Join 節(jié)點。這個在 Presto 的查詢優(yōu)化里面是最常用的了。Pattern.typeOf() 底層調(diào)用的就是這個實現(xiàn)。
• FilterPattern: 檢測節(jié)點是否符合某個 predicate。Pattern.matching() 底層調(diào)用的就是這個實現(xiàn)。
• EqualsPattern: 這其實是 FilterPattern 的一種特殊形式。
• WithPattern: 它的作用是檢測對象的某個屬性是否符合某種模式，比如上面例子里面的 project().with(source().xxxx) , 這里的 source() 就是表示 ProjectNode 的下游節(jié)點。這個Pattern也非常的重要，沒有這個模式的話，我們只能對一個對象本身進行檢測，有了這個Pattern之后，我們就可以對一個節(jié)點的樹形結(jié)構(gòu)進行模式匹配。
• CapturePattern: 這個模式是為了捕獲當前的節(jié)點，并且把當前節(jié)點跟用戶給定的 Capture 綁定上，后面用戶可以通過這個 Capture 獲取到對應(yīng)的節(jié)點。

匹配(Match)

前面我們講完了模式匹配的前半部分: 模式，下面我們來講講后半部分： 匹配。匹配的關(guān)鍵類是 Match , Match 跟 Pattern 一樣，也是一個抽象類。它主要定義了:

• isPresent(): 是否匹配上了。
• value(): 如果匹配上了，匹配到的值是什么?
• capture(capture), 如果匹配上了，那么你可以調(diào)用這個方法去獲取這個匹配到的結(jié)構(gòu)里面的某個子節(jié)點。

比如在下面的例子里面:

project().with(
    source().matching(
        scan().capturedAs(SCAN_NODE);
    )
)

我們可以用下面的代碼獲取到這個 ScanNode:

    ScanNode scan = match.capture(SCAN_NODE);

這個類另外一個比較有意思的點是, Pattern.matches() 返回的永遠不會為 null (其實不只是這一個類，整個 Presto 都是這個風(fēng)格，不會返回 null，因此你可以看到代碼里面大量的使用了 Optional 類，然后判斷 optional.isPresent() 來看是否真的有結(jié)果)。Match 有兩個私有實現(xiàn)，一個是 Present , 一個是 Empty 。

如果匹配到了，那么返回的是 Present , 這個 Present 里面會有兩個東西:

• value: 匹配到的節(jié)點(值)
• captures: 匹配的過程中捕獲的所有子節(jié)點。

而如果沒有匹配到，那么返回的是 Empty, 看起來很優(yōu)雅。

值得注意的是這兩個實現(xiàn)類 Present, Empty 都是私有的，用戶是無法直接用的，對用戶來說只有一個抽象類 Match, Match 本身提供工廠方法來根據(jù)使用場景構(gòu)造具體的實現(xiàn)類給你使用:

• Match<T> of(S value, Captures captures) , 模式匹配成功的話使用這個工廠方法，返回的是 Present.
• Match<S> empty() , 沒有匹配到的話使用這個工廠方法，返回的是 Empty 。

Matcher

模式(Pattern)跟匹配(Match)都講完了， 最后我們來講講聯(lián)系這兩端的橋梁: 匹配器(Matcher):

如前面所說，匹配器使用的是 Visitor 的模式，它定義了匹配各種不同模式的方法:

public interface Matcher {
    default <T> Match<T> match(Pattern<T> pattern, Object object) {
        return match(pattern, object, Captures.empty());
    }
    <T> Match<T> match(Pattern<T> pattern, Object object, Captures captures);
    <T> Match<T> matchTypeOf(TypeOfPattern<T> typeOfPattern, Object object, Captures captures);
    <T> Match<T> matchWith(WithPattern<T> withPattern, Object object, Captures captures);
    <T> Match<T> matchCapture(CapturePattern<T> capturePattern, Object object, Captures captures);
    <T> Match<T> matchEquals(EqualsPattern<T> equalsPattern, Object object, Captures captures);
    <T> Match<T> matchFilter(FilterPattern<T> filterPattern, Object object, Captures captures);
}

目前 Matcher 接口只有一個默認實現(xiàn): DefaultMatcher, 估計在可以預(yù)見的將來也就只有一個實現(xiàn)了，因為實現(xiàn)本身很簡單，沒有太多花頭。 這里最核心的方法是:

    @Override
    public <T> Match<T> match(Pattern<T> pattern, Object object, Captures captures)
    {
        if (pattern.previous() != null) {
            Match<?> match = match(pattern.previous(), object, captures);
            return match.flatMap((value) -> pattern.accept(this, value, match.captures()));
        }
        else {
            return pattern.accept(this, object, captures);
        }
    }

它遞歸地在整個 Pattern 鏈上調(diào)用 match 方法，看看是否這個入?yún)?object 能夠滿足這個鏈上的所有 Pattern，同時把過程當中把用戶想捕獲的子節(jié)點通過 Captures 保存下來。

模式匹配在Presto里面的應(yīng)用

前面也介紹過，模式匹配在 Presto 里面主要用來尋找執(zhí)行計劃里面有待優(yōu)化的部分，執(zhí)行計劃優(yōu)化在 Presto 里面有兩類： 一類基于規(guī)則的優(yōu)化器(Rule Based Optimization)，一類是基于代價的優(yōu)化器(Cost Based Optimization)，而模式識別主要是在基于規(guī)則的場景下使用的，比如其中有一個優(yōu)化規(guī)則 PushLimitThroughProject 是這樣的:

如果在Limit節(jié)點下面有一個Project節(jié)點，那么把這個Limit節(jié)點下推到Project節(jié)點下面。

這里的Limit, Project都是關(guān)系代數(shù)里面的概念, 不熟悉的同學(xué)可以這么簡單理解: Limit就對應(yīng)到SQL語句里面的LIMIT語句，Project對應(yīng)到SQL語句里面的SELECT語句。這樣上面那條優(yōu)化規(guī)則的意思就很好理解了：你如果知道后面進行 limit 操作，那么不如在前面 select 時候時候就少 select 一些數(shù)據(jù)出來，這樣整個查詢總的處理的數(shù)據(jù)量就少了。那么我們看看這么一個規(guī)則是怎么通過模式識別來實現(xiàn)的:

// 為了整個代碼的簡潔性，不影響理解的情況下，這里刪除了一些不大相關(guān)的方法。
// PushLimitThroughProject的完整實現(xiàn)請參見Presto的源碼
public class PushLimitThroughProject
         implements Rule<LimitNode> {
    // 我們給要捕獲的ProjectNode節(jié)點分配一個Key
    private static final Capture<ProjectNode> CHILD = newCapture();
    private static final Pattern<LimitNode> PATTERN = limit()
            .with(source().matching(
                    project().capturedAs(CHILD) // 通過capturedAs捕獲ProjectNode
                    ));

    @Override
    public Result apply(LimitNode parent, Captures captures, Context context) {
        // 把LimitNode和ProjectNode的位置進行互換從而把Limit換到Project下面去
        // 達到的效果就是先做Limit再進行Project
        return Result.ofPlanNode(transpose(parent, captures.get(CHILD)));
    }
}

這里的代碼很簡單，配合我的注釋應(yīng)該很好理解。這樣一個優(yōu)雅的小模式識別的庫在這個 Presto 查詢優(yōu)化的大場景中就起到了很大的作用。

感想

好的代碼就像一首散文，一首詩，雖然里面的每個字都會寫，但是自己卻寫不出這么美妙的代碼。至于它為什么好，我覺得這里融入了作者對于技術(shù)、業(yè)務(wù)的充分理解和抽象，以及作者本身作為這個庫的用戶不斷打磨推敲出來的。

Presto 的代碼雖然總體來說不是很好：注釋很少、接口太多、定義很隨便、構(gòu)造函數(shù)動輒十幾個參數(shù)等等，問題數(shù)不勝數(shù)，但是看到這個模式識別的小庫還是有點驚艷的感覺的。

這個庫設(shè)計得比較干凈，雖然它在 Presto 里面的主要場景就是做查詢優(yōu)化的模式識別，但是它的實現(xiàn)沒有跟查詢優(yōu)化綁定死，以后如果有類似模式識別的場景只要把這個庫稍加改造應(yīng)該就可以使用。