概要

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

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

源碼分析

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

presto-matching 關鍵類圖

Pattern

Pattern 在庫里面是一個抽象類达舒，它主要起了四方面的作用：首先它定義了模式的結構值朋；其次定義了模式的行為；再次它定義了常用模式構造的方法巩搏，形成了一個小型的DSL昨登；最后它定義了模式與匹配之間的橋梁方法: matches 。

Pattern的結構

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

而所有的 Pattern 里面都會有一個 previous 的字段胚想，這個字段指向上一個模式琐凭，這樣我們雖然只拿到了一個 Pattern 對象，但是其實它背后可能串了一個鏈的對象浊服，這些模式之間的關系是“并且”的關系统屈，我們可以稱之為“復合Pattern”。

復合Pattern結構

Pattern的行為

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

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

    void accept(PatternVisitor patternVisitor);

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

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

這里其實是對 Pattern 這一個對象實現了兩套 Visitor 的模式进肯，一套用來進行模式匹配激蹲，一套用來進行通用的結構遍歷棉磨。

Pattern DSL

Pattern 類的第三個作用就是定義了一些常用的模式構造的方法江掩，比如:

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

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

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

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

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

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();
}

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

Pattern的子類

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

• TypeOfPattern: 檢測某個節(jié)點是不是指定類型的節(jié)點蔓肯，比如是不是一個 TableScan 節(jié)點遂鹊，是不是一個 Join 節(jié)點。這個在 Presto 的查詢優(yōu)化里面是最常用的了蔗包。Pattern.typeOf() 底層調用的就是這個實現秉扑。
• FilterPattern: 檢測節(jié)點是否符合某個 predicate。Pattern.matching() 底層調用的就是這個實現调限。
• EqualsPattern: 這其實是 FilterPattern 的一種特殊形式舟陆。
• WithPattern: 它的作用是檢測對象的某個屬性是否符合某種模式，比如上面例子里面的 project().with(source().xxxx) , 這里的 source() 就是表示 ProjectNode 的下游節(jié)點耻矮。這個Pattern也非常的重要秦躯，沒有這個模式的話，我們只能對一個對象本身進行檢測裆装，有了這個Pattern之后踱承，我們就可以對一個節(jié)點的樹形結構進行模式匹配。
• CapturePattern: 這個模式是為了捕獲當前的節(jié)點哨免，并且把當前節(jié)點跟用戶給定的 Capture 綁定上茎活，后面用戶可以通過這個 Capture 獲取到對應的節(jié)點。

匹配(Match)

前面我們講完了模式匹配的前半部分: 模式琢唾，下面我們來講講后半部分： 匹配载荔。匹配的關鍵類是 Match , Match 跟 Pattern 一樣，也是一個抽象類采桃。它主要定義了:

• isPresent(): 是否匹配上了懒熙。
• value(): 如果匹配上了丘损，匹配到的值是什么?
• capture(capture), 如果匹配上了，那么你可以調用這個方法去獲取這個匹配到的結構里面的某個子節(jié)點工扎。

比如在下面的例子里面:

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

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

    ScanNode scan = match.capture(SCAN_NODE);

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

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

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

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

值得注意的是這兩個實現類 Present, Empty 都是私有的俱病，用戶是無法直接用的官疲，對用戶來說只有一個抽象類 Match, Match 本身提供工廠方法來根據使用場景構造具體的實現類給你使用:

• 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 接口只有一個默認實現: DefaultMatcher, 估計在可以預見的將來也就只有一個實現了，因為實現本身很簡單促王，沒有太多花頭犀盟。 這里最核心的方法是:

    @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 鏈上調用 match 方法，看看是否這個入參 object 能夠滿足這個鏈上的所有 Pattern蝇狼，同時把過程當中把用戶想捕獲的子節(jié)點通過 Captures 保存下來阅畴。

模式匹配在Presto里面的應用

前面也介紹過，模式匹配在 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都是關系代數里面的概念, 不熟悉的同學可以這么簡單理解: Limit就對應到SQL語句里面的LIMIT語句血公，Project對應到SQL語句里面的SELECT語句。這樣上面那條優(yōu)化規(guī)則的意思就很好理解了：你如果知道后面進行 limit 操作缓熟，那么不如在前面 select 時候時候就少 select 一些數據出來累魔，這樣整個查詢總的處理的數據量就少了摔笤。那么我們看看這么一個規(guī)則是怎么通過模式識別來實現的:

// 為了整個代碼的簡潔性，不影響理解的情況下垦写，這里刪除了一些不大相關的方法吕世。
// PushLimitThroughProject的完整實現請參見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ōu)雅的小模式識別的庫在這個 Presto 查詢優(yōu)化的大場景中就起到了很大的作用命辖。

感想

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

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

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