""5月28日，“全球開源技術(shù)峰會 GOTC 2023 ”圓滿落幕。在本次會上，Databend 數(shù)據(jù)庫的優(yōu)化器研發(fā)工程師 駱迪安作為嘉賓中的一員，在 rust 專題專區(qū)分會場進行了一次主題為《 Rust 實現(xiàn)的先進 SQL ?Parser 與高效表達式執(zhí)行框架 — Databend 數(shù)據(jù)庫表達式框架設(shè)計與實現(xiàn)》的演講。

演講嘉賓： 駱迪安 ? https://github.com/andylokandy

嘉賓介紹： 現(xiàn)任 Databend 數(shù)據(jù)庫的優(yōu)化器研發(fā)工程師，主要負責(zé) Databend 計算引擎的 SQL Parser、優(yōu)化器、類型系統(tǒng)以及向量化執(zhí)行框架的開發(fā)；之前在一家使用 Rust 開發(fā)的分布式數(shù)據(jù)庫公司擔(dān)任分布式事務(wù)的研發(fā)工程師。從 2015 年開始接觸 Rust 這門語言。曾積極參與社區(qū)討論并貢獻了幾個庫，現(xiàn)如今這些庫的下載量已經(jīng)超過了百萬。

以下為本次演講的精彩內(nèi)容：

Intro

編程語言一直是我非常感興趣的領(lǐng)域。在業(yè)余時間，我會為一門名為 Idris 的語言編譯器貢獻代碼。Idris 的語法與 Haskell 相似，但增加了依賴類型和線性類型等特性。它是一門非常有趣的實驗性編程語言。這些年來，我看到 Rust 逐漸將 Idris 的實驗特性引入 Rust 生態(tài)，例如 effect（也稱作關(guān)鍵字泛型）以及最近剛剛穩(wěn)定的 const generic 特性。在編譯器和數(shù)據(jù)庫開發(fā)的過程中，我發(fā)現(xiàn)它們之間存在許多共通之處，如文本解析成語法樹、語法樹的語義分析和類型檢查等。因此，Databend 中包含了許多借鑒現(xiàn)代編譯器實踐的精髓。

首先，簡要介紹一下 Databend。Databend 是一個全新的云原生數(shù)倉，具有即時擴縮容能力，能在數(shù)分鐘內(nèi)增加數(shù)百倍的算力。得益于 Databend 的存算分離架構(gòu)以及無狀態(tài)計算節(jié)點設(shè)計，擴縮容速度得到了極大的提升。而數(shù)據(jù)完全托管在對象存儲中，確保了云服務(wù)在高性價比的同時，實現(xiàn)高可用性。

從架構(gòu)圖中可以看到，Databend 由兩個獨立的組件組成。頂部是元數(shù)據(jù)存儲，相當(dāng)于集群的目錄；第二部分是計算節(jié)點，負責(zé)從 SQL 解析和優(yōu)化到數(shù)據(jù)處理的整個過程。所消耗大量 CPU 的部分主要集中在計算節(jié)點。它們通過彈性的存儲接口從底部的對象存儲中拉取數(shù)據(jù)。今天的分享重點在計算節(jié)點，我將帶領(lǐng)大家深入了解 Databend 內(nèi)部如何將一個 SQL 字符串轉(zhuǎn)化為可執(zhí)行的中間計劃，并計算出結(jié)果。

[String] -- [Tokoenize] -- [Parse] -- [Name Resoluation] -- [Type Check] -- [Optimize] -- [Execution]

SQL Parser

在我們詳細探討 Databend 中的 SQL 語法解析器之前，讓我們先了解一下語法解析器的基本概念。用戶請求的 SQL 字符串會輸入語法解析器，語法解析器檢查 SQL 中是否包含語法錯誤，如果語法正確就輸出抽象語法樹（AST）便于機器理解和處理：

解析器過程可以分成兩個階段：Tokenize（分詞） 階段和 Parsing（解析）階段。

首先是 Tokenize 階段。在這個階段，我們將 SQL 語句作為輸入字符串，任務(wù)是將這段字符串切分成具有獨立語義的單元，稱為 Token。這一步的關(guān)鍵在于利用正則表達式從字符串中識別相鄰的有意義的部分，例如關(guān)鍵字、變量名、常量和操作符。

我們從上到下按順序嘗試匹配正則表達式，并重復(fù)這個步驟就得到了 Token 序列，這就是 Tokenizer 的基本工作原理。

接下來是 Parsing 階段。通常我們會使用 BNF 來定義 SQL 的語法規(guī)則，它描述了有意義的 Token 應(yīng)該如何組合。

在這個階段，我們將 Token 序列作為輸入，然后生成 AST。

Choosing an SQL Parser

剛開始，Databend 嘗試 fork 了 sqlparser-rs，但后來我們決定放棄這個選擇。盡管 sqlparser-rs 已經(jīng)被諸如 materialize 和 risingwave 這樣的 Rust 編寫的數(shù)據(jù)庫廣泛使用，但其主要問題在于它主要采用手寫狀態(tài)機的方式實現(xiàn)，這使得它在擴展性和容錯性上都存在問題。所以，我們意識到需要尋找一種綜合性更強、可擴展性更高的解析器方案。

這時，我們選擇 nom 作為解析器庫，并實現(xiàn)了遞歸下降 SQL 解析器。nom 是一個受到廣泛好評的解析器組合庫，它具有高性能和高擴展性，與此同時，它還能為開發(fā)者提供更貼近原生的開發(fā)體驗。與 ANTLR4 和 LALRPOP 等語法生成器相比，nom 作為原生 Rust 開發(fā)，能夠與其他 Rust 編寫的組件完美融合，橋接起來毫不費力。這意味著我們可以充分享受 Rust IDE 的強大支持以及靜態(tài)類型檢查的優(yōu)勢。

當(dāng)然，nom 也有自己的一些缺點，比如它構(gòu)建語法規(guī)則的過程相對繁瑣。為了解決這個問題，我們使用了"?nom-rule!()"?過程宏。這使得我們可以使用 BNF 來定義語法規(guī)則，并能自動生成 nom 解析器，簡潔明了。這樣一來，我們既保留了 nom 的高性能和高擴展性，又解決了它在語法描述上的問題，提高了可維護性。

Tokenizer

在選擇 Tokenizer 方案時，我們選擇了社區(qū)的 Logos 庫。

為了有效地表達 Token 的類型，我們定義一個名為?"TokenKind"?的 enum 枚舉類型。每個?"TokenKind"?對應(yīng)一種特定的 Token，例如：關(guān)鍵字、變量名、常量和操作符。每個?"TokenKind"?都會有一個單獨的正則表達式進行匹配，以確保準確地從輸入字符串中提取 Token。

然后我們引入了社區(qū)的 Logos 庫，它會將所有?"TokenKind"?的正則表達式聚合，并將它們編譯成一個高效的狀態(tài)機和跳表來達到超過任何手寫 Tokenizer 的極快的分詞性能。

除了?"TokenKind"?的定義，Token 本身還包括了一個重要的屬性——span。span 記錄了 Token 在原始字符串中的起始和結(jié)束位置。這在后續(xù)階段很有用，比如當(dāng)我們需要針對 SQL 語句中的特定部分向用戶報告錯誤時，可以利用 span 屬性精確定位到具體的位置。

Parser

接下來, 讓我們介紹一下如何在 Databend 中使用 nom 來實現(xiàn)遞歸下降 SQL 解析器。

遞歸下降解析器主要由兩種 parser 組成：

1. Terminal parser：這是最基本的解析器，用于匹配特定 TokenKind 的 Token。在 Databend 的 SQL parser 中，我們定義了"?match_token()"?和?"match_text()"?兩個 Terminal parser。

2. Combinator parser：允許將多個小的解析器組合成較大的解析器。這是我們構(gòu)建復(fù)雜邏輯的基礎(chǔ)。以下是一些常見的組合器：

• tuple(a, b, c)：會讓多個 parser 按順序排列（例如先是 a，然后是 b，接著是 c）。它們需要按照預(yù)期的順序逐個成功才算作最后的成功。?

• ?alt(a, b, c)：嘗試多個 parser 分支（例如 a，b 或 c），直到滿足第一個成功條件。如果全部失敗，解析器將報告錯誤。?

• ?many0(a)：貪婪地循環(huán)調(diào)用相同的 parser。如果無法繼續(xù)，這個解析器將成功返回已匹配的 Token 序列?？赡転榭铡?

• ?many1(a)：貪婪地循環(huán)調(diào)用相同的 parser，但至少需要匹配成功一次。如果至少匹配成功一次，解析器會返回 Token 序列。?

• opt(a)：允許 parser 失敗。當(dāng) parser 失敗時，將返回?"None"。成功時將返回成功匹配的結(jié)果。

我們來看一個實際的例子，我們知道?"select_statment"?的 BNF 是：

我們使用 nom 提供的組合子來組裝相應(yīng)的語法樹：

在這里關(guān)鍵字使用?"match_token"?識別；循環(huán)多個的?"<expr>+"?用?"many1"?來實現(xiàn)。nom 的語法樹會幫助我們把一維的 Token 序列識別成立體的 Parse Tree。

到這里 nom 僅僅幫助我們構(gòu)建了一課符合語法結(jié)構(gòu)的 Parse Tree，它的節(jié)點都是由 Token 組成的，所以這個還不是我們需要的 AST，所以進一步地，我們用?"map"?把 Token 樹，于是最終我們得到了 AST:

nom-rule

nom 使用原生 Rust 函數(shù)構(gòu)造語法樹，顯得過于冗余和不清晰。我們希望可以使用類似 BNF 的形式來描述 SQL 這種復(fù)雜的語法結(jié)構(gòu)，所以我們使用了?"nom-rule"?過程宏來做到這一點。它輸入類似 BNF 的語法定義，然后轉(zhuǎn)換成 nom 的組合子函數(shù)。因為?"nom-rule"?生成的是合法的 Rust 代碼，所以我們可以把?"nom-rule"?直接嵌入到 nom 代碼的任何位置。

Left Recursion

現(xiàn)在我們來探討一個實際中實現(xiàn)解析器會遇到的問題 - 左遞歸問題。

假設(shè)我們打算定義算術(shù)表達式的語法規(guī)則，比如說 解析一個簡單的算術(shù)表達式："1 + 2"，理想情況下，我們期望將這個表達式解析成一個樹狀結(jié)構(gòu)，其中操作符 "+" 作為樹的根節(jié)點，"1" 和 "2" 分別作為左子節(jié)點和右子節(jié)點。根據(jù)直覺我們會定義成：

然而，實際上這樣的解析器會報告錯誤，這是因為?"1 + 2"?中的?"1"?會首先被識別為 ，剩下的?"+ 2"?并不能匹配任何一條規(guī)則。

所以我們必須把更整體的分支放到前面，然后定義會變成：

然而，實際上這樣做會讓解析器陷入死循環(huán)。因為調(diào)用 解析器之后它做的第一件事情是再次調(diào)用自己，沒有任何退出遞歸的機會。

我們使用 Pratt 算法來解決這個問題。Pratt 算法是在 1973 年提出的一種簡易算法。它專門用于處理一元和二元操作符。輸入表達式元素的一維序列，即?"[1, +, 2]"，以及定義"?+",?"-","?*",?"/"?為二元中置操作符，然后采用 Pratt 算法處理這些表達式元素，組裝成樹狀結(jié)構(gòu)。具體算法由于時間關(guān)系在這里不作展開了。

Type Check

SQL 字符串經(jīng)過 Parser 變成了 AST，Parser 輸出的 AST 一定符合語法規(guī)則，但不一定有意義，例如?"1 + 'foo'"?這個表達式，它遵守語法規(guī)則，但仍然是無意義的。因此，在解析得到 AST 后，我們會緊接著對表達式的類型進行檢查。一旦類型檢查通過，我們就可以保證表達式具有明確的運行時語義。

在 Databend 中，類型信息主要依賴于函數(shù)簽名。我們來看一個表達式的例子：

首先，Typechecker 對其進行簡化，將其轉(zhuǎn)換為函數(shù)調(diào)用：

然后，類型檢查器可以輕松推斷出：

此外，由于?"plus"?函數(shù)提供了一些重載方法：

我們可以輕松地發(fā)現(xiàn)，"plus(Int8, String)"?并不符合任何重載方法。因此，類型檢查器可以報錯，指出：

Type Judgement

Type Checking 的概念源于類型理論。在類型理論中，我們使用專門的記號來定義類型推導(dǎo)規(guī)則。例如，我們在以下示例中運用了這些推導(dǎo)規(guī)則：

符號???讀作 "推導(dǎo)出"。這條規(guī)則表示字面量?"TRUE"?的類型為布爾類型。

同樣地，我們也為整數(shù)和字符串字面量定義了類型：

接下來，我們?yōu)?"plus()"?函數(shù)定義推導(dǎo)規(guī)則：

分號上方部分是推導(dǎo)的前提條件，若分號上的所有條件都滿足，分號下的規(guī)則便成立。這表明如果在當(dāng)前類型環(huán)境（Type Environment）中，表達式?"e1"?與?"e2"?的類型皆為?"Int8"，那么我們可推導(dǎo)出?"plus(e1, e2)"?的類型為?"Int8"。

表達式可以包含自由變量（free variables），在 SQL 中，數(shù)據(jù)列就是自由變量。例如，在查詢?"SELECT 1 + a"?中的?"a"?就是一個自由變量。當(dāng)檢查表達式?"1 + a"?時，我們無法確定變量?"a"?的類型；若?"a"?是表的數(shù)據(jù)列，我們需要從表元數(shù)據(jù)中查詢?"a"?的類型。

若?"a"?是子查詢的結(jié)果列，則需要先檢查子查詢以得到?"a"?的類型：

在上下文中，變量名稱與類型具有映射關(guān)系。這種信息稱為類型環(huán)境（Type Environment），用?"Γ"?符號表示。類型環(huán)境可以有多種來源，但在 Typechecker 中，我們將其抽象為一個外部界面。我們只需了解，每個變量都可以從類型環(huán)境中查詢到一個確定的類型。

Subtype

Databend 引入了子類型概念，數(shù)據(jù)類型可以根據(jù)需要適當(dāng)自動回退到一個更小約束的類型。比如?"1 + 256"?的入?yún)㈩愋褪?"plus(Int8, Int16)"，根據(jù)?"plus()"?函數(shù)重載列表

我們發(fā)現(xiàn)沒有一個重載可完全符合入?yún)㈩愋?。但我們知?"Int8"?可以無損地由?"Int16"?類型表示，也就是說?"Int8"?是?"Int16"?的 subtype

為此我們稍微修改一下函數(shù)類型規(guī)則：

這樣可以推導(dǎo)出?"1 + 256"?的類型是?"Int16"。

在實際實踐中，我們會在必要進行子類型轉(zhuǎn)換的地方插入?"CAST"，所以?"1 + 256"?會變成?"CAST(1 AS INT16) + 256"。

Generic

在 Databend 中，我們支持數(shù)組類型，例如：

當(dāng)我們嘗試為數(shù)組定義函數(shù)時，會發(fā)現(xiàn)無法列舉出所有重載。以?"get()"?函數(shù)為例，該函數(shù)用于根據(jù)下標從數(shù)組中提取一個元素，因此函數(shù)的返回類型取決于數(shù)組的元素類型。如下所示：

為了解決這個問題，我們在 Typechecker 中引入了泛型。借助泛型，可以用一個簡單的重載定義?"get()"?函數(shù)：

當(dāng)嘗試檢查表達式?"get(Array<Int8>, Int64)"?時，Typechecker 會通過比較簽名類型?"Array<T>"?和實際參數(shù)類型?"Array<Int8>"?來解析替換關(guān)系?"T=Int8"。因此，將簽名中返回值類型的?"T"?替換為?"Int8"，就可以得到函數(shù)類型?"Int8"。這個解析替換關(guān)系的算法被稱為 Unification 算法，它非常有趣，但由于時間原因在此不展開講解。如果您感興趣，強烈推薦去了解這個算法。

Vectorized Evaluation

為了在內(nèi)存中存儲數(shù)據(jù)，我們定義了一些數(shù)據(jù)結(jié)構(gòu)：

表達式?"1 + a"?通過類型檢查后得到?"Expr"?結(jié)構(gòu)：

"FunctionCall"?包含一個名為?"eval"?的閉包。這個閉包在類型檢查階段被確定，并負責(zé)實際的數(shù)據(jù)計算。由于 Databend 實現(xiàn)了向量化計算，"eval"?會一次接收一批數(shù)據(jù)作為參數(shù)，并批量計算并輸出相同行數(shù)的結(jié)果。特殊情況下，如果輸入的每一行都相同，我們使用?"Value::Scalar"?進行存儲。

以?"plus(Int8, Int8)"?為例，其定義類似于：

在這里我們看到相同的加法邏輯出現(xiàn)了 4 次，這是因為我們需要分別處理?"Value::Scalar"?或?"Value::Column"?的左右輸入?yún)?shù)情況。因此，我們可以將這個模式抽象出來：

這樣我們可以更方便地注冊?"Int8"?類型的算術(shù)函數(shù)：

這個模式中我們抽象出了處理?"Value"?的分類討論，但仍需要針對每種輸入?yún)?shù)類型進行一次實現(xiàn)。因此，我們繼續(xù)將輸入?yún)?shù)類型抽象出來。從這一步開始，抽象變得更加復(fù)雜。因為閉包的輸入?yún)?shù)類型在 Rust 編譯期已經(jīng)確定下來，這就意味著無法使用單個?"|lhs, rhs| lhs + rhs"?來同時定義?"plus(Int8, Int8) -> Int8"?和?"plus(Int16, Int16) -> Int16"兩種重載。因此，在這里我們需要求助于一些 Rust 的高級技巧：

首先，為?"Int8"?數(shù)據(jù)類型定義一個空結(jié)構(gòu)體：

然后，將處理?"Int8"?類型數(shù)據(jù)的操作放入?"Int8Type"?中：

在定義了必要操作之后，我們可以對?"register_2_arg_int8"?進行修改。我們將輸入?yún)?shù)類型從固定的?"i8"?更改為靈活的三個泛型?"I1"，"I2"?和?"Output"，分別表示第一個參數(shù)類型、第二個參數(shù)類型和輸出類型：

現(xiàn)在，我們已經(jīng)借助 Rust 泛型系統(tǒng)將類型信息抽象化：

有了這個改進，我們可以非常方便地注冊其他類型的重載函數(shù)，例如：

Golang

說來也巧，之前我也參與過一個使用 golang 編寫的數(shù)據(jù)庫項目。一般為了避免引戰(zhàn)，我不會在公開場合討論 Rust 和 Golang 的優(yōu)劣。但是今天是rust專場，所以我就可以說一說了。這是我從 golang 項目中摘取的定義 abs() 函數(shù)的片段，它有 135 行，定義了 5 個結(jié)構(gòu)體和 5 個函數(shù)，分別是一個函數(shù)級專微型類型檢查器，4個 struct 用來分別代表不同的函數(shù)從在，以及對每個類型重載分別定義一次計算過程，由于 golang 沒有能夠把向量化循環(huán)抽象出來的機制，那么只好在每一個重載內(nèi)部都手動重寫一次for循環(huán)。

這里 135 行只定義了一個 abs 函數(shù)，定義其他上百個函數(shù)的時候都要把重復(fù)一遍相同過程。

這樣對比下來，rust 在運行效率和可維護性上都是明顯更好一些。其實不是想討論 rust 和 golang 誰更好這種問題。只是說每一種語言都有適合的場景，而在數(shù)據(jù)庫領(lǐng)域，rust 在應(yīng)對功能復(fù)雜性上比 golang 更適合一些。

Conclusion

在本次分享中，我向大家介紹了 Databend 中獨特的 SQL 解析器和表達式框架。我們使用了諸如 Rust、nom、Logos、Pratt 算法、類型檢查等工具和技術(shù)來實現(xiàn)一個高效的、可擴展的解析器和計算框架。這使得我們能夠快速迭代 Databend，不斷優(yōu)化我們的數(shù)據(jù)庫系統(tǒng)，同時保持高性能和高可擴展性。

在演講的最后，我還想向各位觀眾推薦一本書——《Types and Programing Language》。這本書由 Benjamin C. Pierce 編寫，系統(tǒng)地介紹了類型理論、程序語言和編譯器相關(guān)的知識。通過閱讀這本書，您將深入了解類型系統(tǒng)、類型檢查、類型推導(dǎo)等概念，這對于研究和開發(fā)編譯器以及數(shù)據(jù)庫都有很大幫助。

最后，我要感謝這次機會，讓我能和大家一起分享 Databend 中的這些技術(shù)與實踐。謝謝大家！