5月28日，“全球開源技術(shù)峰會 GOTC 2023 ”圓滿落幕挽懦。在本次會上傻丝，Databend 數(shù)據(jù)庫的 優(yōu)化器 研發(fā)工程師 駱迪安作為嘉賓中的一員赖晶，在 rust 專題專區(qū)分會場進行了一次主題為《 Rust 實現(xiàn)的先進 SQL Parser 與高效表達(dá)式執(zhí)行框架 — Databend 數(shù)據(jù)庫表達(dá)式框架設(shè)計與實現(xiàn)》的演講。
演講嘉賓： 駱迪安 https://github.com/andylokandy
嘉賓介紹： 現(xiàn)任 Databend 數(shù)據(jù)庫的優(yōu)化器研發(fā)工程師腔长，主要負(fù)責(zé) Databend 計算引擎的 SQL Parser袭祟、優(yōu)化器、類型系統(tǒng)以及向量化執(zhí)行框架的開發(fā)捞附；之前在一家使用 Rust 開發(fā)的分布式數(shù)據(jù)庫公司擔(dān)任分布式事務(wù)的研發(fā)工程師巾乳。從 2015 年開始接觸 Rust 這門語言。曾積極參與社區(qū)討論并貢獻(xiàn)了幾個庫鸟召，現(xiàn)如今這些庫的下載量已經(jīng)超過了百萬胆绊。
以下為本次演講的精彩內(nèi)容：
Intro
編程語言一直是我非常感興趣的領(lǐng)域。在業(yè)余時間欧募，我會為一門名為 Idris 的語言編譯器貢獻(xiàn)代碼压状。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é)點莉兰，負(fù)責(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]
[圖片上傳失敗...(image-580e7e-1685602586110)]
SQL Parser
在我們詳細(xì)探討 Databend 中的 SQL 語法解析器之前蜘矢，讓我們先了解一下語法解析器的基本概念。用戶請求的 SQL 字符串會輸入語法解析器综看，語法解析器檢查 SQL 中是否包含語法錯誤品腹，如果語法正確就輸出抽象語法樹（AST）便于機器理解和處理：
select a + 1 from t
SelectStatement {
projection: Expr::BinaryOp {
op: Op::Plus,
args: [
Expr::ColumnRef("a"),
Expr::Constant(Scalar::Int(1))
]
}
from: "t",
}
解析器過程可以分成兩個階段：Tokenize（分詞） 階段和 Parsing（解析）階段。
首先是 Tokenize 階段红碑。在這個階段舞吭，我們將 SQL 語句作為輸入字符串，任務(wù)是將這段字符串切分成具有獨立語義的單元析珊，稱為 Token羡鸥。這一步的關(guān)鍵在于利用正則表達(dá)式從字符串中識別相鄰的有意義的部分，例如關(guān)鍵字唾琼、變量名兄春、常量和操作符澎剥。
Ident = [_a-zA-Z][_$a-zA-Z0-9]*
Number = [0-9]+
Plus = +
SELECT = SELECT
FROM = FROM
我們從上到下按順序嘗試匹配正則表達(dá)式锡溯，并重復(fù)這個步驟就得到了 Token 序列赶舆，這就是 Tokenizer 的基本工作原理。
select a + 1 from t
[
Keyword(SELECT),
Ident(a),
BinOp(+),
Number(1),
Keyword(FROM),
Ident(t),
]
接下來是 Parsing 階段祭饭。通常我們會使用 BNF 來定義 SQL 的語法規(guī)則芜茵，它描述了有意義的 Token 應(yīng)該如何組合。
<select_statement> ::= SELECT <expr> FROM <ident>
<expr> ::= <number>
| <ident>
| <expr> <op> <expr>
<op> ::= + | - | * | /
在這個階段倡蝙，我們將 Token 序列作為輸入九串，然后生成 AST。
SelectStatement {
projection: Expr::BinaryOp {
op: Op::Plus,
args: [
Expr::ColumnRef("a"),
Expr::Constant(Scalar::Int(1))
]
}
from: "t",
}
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 庫贮庞。
為了有效地表達(dá) Token 的類型峦筒，我們定義一個名為 TokenKind 的 enum 枚舉類型。每個 TokenKind 對應(yīng)一種特定的 Token窗慎，例如：關(guān)鍵字物喷、變量名、常量和操作符遮斥。每個 TokenKind 都會有一個單獨的正則表達(dá)式進行匹配峦失，以確保準(zhǔn)確地從輸入字符串中提取 Token。
然后我們引入了社區(qū)的 Logos 庫术吗，它會將所有 TokenKind 的正則表達(dá)式聚合宠进，并將它們編譯成一個高效的狀態(tài)機和跳表來達(dá)到超過任何手寫 Tokenizer 的極快的分詞性能。
#[allow(non_camel_case_types)]
#[derive(Logos)]
pub enum TokenKind {
#[regex(r"[ \t\r\n\f]+", logos::skip)]
Whitespace,
#[regex(r#"[_a-zA-Z][_$a-zA-Z0-9]*"#)]
Ident,
#[regex(r"[0-9]+")]
Number,
#[token("+")]
Plus,
#[token("SELECT", ignore(ascii_case))]
SELECT,
#[token("FROM", ignore(ascii_case))]
FROM,
}
[
Token { kind: TokenKind::Select, text: "SELECT", span: 0..6 },
Token { kind: TokenKind::Ident, text: "a", span: 7..8 },
Token { kind: TokenKind::Plus, text: "+", span: 9..10 },
Token { kind: TokenKind::Number, text: "1", span: 11..12 },
Token { kind: TokenKind::From, text: "from", span: 13..17 },
Token { kind: TokenKind::Ident, text: "t", span: 18..19 },
]
除了 TokenKind 的定義藐翎，Token 本身還包括了一個重要的屬性——span材蹬。span 記錄了 Token 在原始字符串中的起始和結(jié)束位置。這在后續(xù)階段很有用吝镣，比如當(dāng)我們需要針對 SQL 語句中的特定部分向用戶報告錯誤時堤器，可以利用 span 屬性精確定位到具體的位置。
error:
--> SQL:1:19
|
1 | create table a (c varch)
| ------ - ^^^^^ expected `BOOLEAN`, `BOOL`, `UINT8`, `TINYINT`, `UINT16`, `SMALLINT`, or 33 more ...
| | |
| | while parsing `<column name> <type> [DEFAULT <default value>] [COMMENT '<comment>']`
| while parsing `CREATE TABLE [IF NOT EXISTS] [<database>.]<table> [<source>] [<table_options>]`
Parser
接下來, 讓我們介紹一下如何在 Databend 中使用 nom 來實現(xiàn)遞歸下降 SQL 解析器末贾。
遞歸下降解析器主要由兩種 parser 組成：
- Terminal parser：這是最基本的解析器闸溃，用于匹配特定 TokenKind 的 Token。在 Databend 的 SQL parser 中拱撵，我們定義了
match_token()和match_text()兩個 Terminal parser辉川。
fn match_text(text: &str) -> impl FnMut(&[Token]) -> IResult<&[Token], Token> {
satisfy(|token: &Token| token.text == text)(i)
}
fn match_token(kind: TokenKind) -> impl FnMut(&[Token]) -> IResult<&[Token], Token> {
satisfy(|token: &Token| token.kind == kind)(i)
}
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 是：
<select_statement> ::= SELECT <expr>+ FROM <ident>
我們使用 nom 提供的組合子來組裝相應(yīng)的語法樹：
tuple((
match_token(SELECT),
many1(expr),
match_token(FROM),
match_token(Ident),
))
在這里關(guān)鍵字使用 match_token 識別毅糟；循環(huán)多個的 <expr>+ 用 many1 來實現(xiàn)红选。nom 的語法樹會幫助我們把一維的 Token 序列識別成立體的 Parse Tree。
SELECT a + 1 FROM t
("SELECT", (+ a 1), FROM, t)
到這里 nom 僅僅幫助我們構(gòu)建了一課符合語法結(jié)構(gòu)的 Parse Tree姆另，它的節(jié)點都是由 Token 組成的喇肋，所以這個還不是我們需要的 AST，所以進一步地迹辐，我們用 map 把 Token 樹蝶防，于是最終我們得到了 AST:
use nom::combinator::*;
use nom::multi::*;
fn select_statement(input: &[Token]) -> IResult<&[Token], SelectStatement> {
map(
tuple((
match_token(SELECT),
many1(expr),
match_token(FROM),
match_token(Ident),
)),
|(_, projections, _, from)| SelectStatement {
projections,
from,
}
)(input)
}
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 代碼的任何位置仍律。
fn select_statement(input: &[Token]) -> IResult<&[Token], SelectStatement> {
map(
nom_rule! {
SELECT ~ #expr+ ~ FROM ~ #ident
},
|(_, projections, _, from)| SelectStatement {
projections,
from,
}
)(input)
}
常用的幾個語法結(jié)構(gòu)有這些嘿悬，它們分別和 nom 的組合子一一對應(yīng)：
| Rule | Translated | ||
|---|---|---|---|
| TOKEN | match_token(TOKEN) | ||
| "+" | match_text("+") | ||
| a ~ b ~ c | tuple((a, b, c)) | ||
| (...)* | many0(...) | ||
| (...)+ | many1(...) | ||
| (...)? | opt(...) | ||
| a | b | c | alt((a, b, c)) |
Left Recursion
現(xiàn)在我們來探討一個實際中實現(xiàn)解析器會遇到的問題 - 左遞歸問題。
假設(shè)我們打算定義算術(shù)表達(dá)式的語法規(guī)則水泉，比如說 解析一個簡單的算術(shù)表達(dá)式：1 + 2鹊漠，理想情況下，我們期望將這個表達(dá)式解析成一個樹狀結(jié)構(gòu)茶行，其中操作符 "+" 作為樹的根節(jié)點躯概，"1" 和 "2" 分別作為左子節(jié)點和右子節(jié)點。根據(jù)直覺我們會定義成：
<expr> ::= <number>
| <expr> + <expr>
然而畔师，實際上這樣的解析器會報告錯誤娶靡，這是因為 1 + 2 中的 1 會首先被識別為 ，剩下的 + 2 并不能匹配任何一條規(guī)則看锉。
所以我們必須把更整體的分支放到前面姿锭，然后定義會變成：
<expr> ::= <expr> + <expr>
| <number>
然而塔鳍，實際上這樣做會讓解析器陷入死循環(huán)。因為調(diào)用 解析器之后它做的第一件事情是再次調(diào)用自己呻此，沒有任何退出遞歸的機會轮纫。
我們使用 Pratt 算法來解決這個問題。Pratt 算法是在 1973 年提出的一種簡易算法焚鲜。它專門用于處理一元和二元操作符掌唾。輸入表達(dá)式元素的一維序列，即 [1, +, 2]忿磅，以及定義 +, -, *, / 為二元中置操作符糯彬，然后采用 Pratt 算法處理這些表達(dá)式元素，組裝成樹狀結(jié)構(gòu)葱她。具體算法由于時間關(guān)系在這里不作展開了撩扒。
Type Check
SQL 字符串經(jīng)過 Parser 變成了 AST，Parser 輸出的 AST 一定符合語法規(guī)則吨些，但不一定有意義搓谆，例如 1 + 'foo' 這個表達(dá)式，它遵守語法規(guī)則豪墅，但仍然是無意義的泉手。因此，在解析得到 AST 后但校，我們會緊接著對表達(dá)式的類型進行檢查螃诅。一旦類型檢查通過，我們就可以保證表達(dá)式具有明確的運行時語義状囱。
在 Databend 中术裸，類型信息主要依賴于函數(shù)簽名。我們來看一個表達(dá)式的例子：
1 + 'foo'
首先亭枷，Typechecker 對其進行簡化袭艺，將其轉(zhuǎn)換為函數(shù)調(diào)用：
plus(1, 'foo')
然后，類型檢查器可以輕松推斷出：
1 :: Int8
'foo' :: String
此外叨粘，由于 plus 函數(shù)提供了一些重載方法：
plus(Int8, Int8) -> Int8
plus(Int16, Int16) -> Int16
plus(Timestamp, Timestamp) -> Timestamp
plus(Date, Date) -> Date
我們可以輕松地發(fā)現(xiàn)猾编，plus(Int8, String) 并不符合任何重載方法。因此升敲，類型檢查器可以報錯答倡，指出：
1 + 'foo'
^ function `plus` has no overload for parameters `(Int8, String)`
available overloads:
plus(Int8, Int8) -> Int8
plus(Int16, Int16) -> Int16
plus(Timestamp, Timestamp) -> Timestamp
plus(Date, Date) -> Date
Type Judgement
Type Checking 的概念源于類型理論。在類型理論中驴党，我們使用專門的記號來定義類型推導(dǎo)規(guī)則瘪撇。例如，我們在以下示例中運用了這些推導(dǎo)規(guī)則：
? TRUE : Boolean
符號 ? 讀作 "推導(dǎo)出"。這條規(guī)則表示字面量 TRUE 的類型為布爾類型倔既。
同樣地恕曲，我們也為整數(shù)和字符串字面量定義了類型：
? 1 : Int8
? "foo" : String
接下來，我們?yōu)?plus() 函數(shù)定義推導(dǎo)規(guī)則：
Γ? e1 : Int8 Γ? e2 : Int8
----------------------
Γ? plus(e1, e2) : Int8
分號上方部分是推導(dǎo)的前提條件渤涌，若分號上的所有條件都滿足佩谣，分號下的規(guī)則便成立挑宠。這表明如果在當(dāng)前類型環(huán)境（Type Environment）中虏劲，表達(dá)式 e1 與 e2 的類型皆為 Int8，那么我們可推導(dǎo)出 plus(e1, e2) 的類型為 Int8著瓶。
表達(dá)式可以包含自由變量（free variables）瞳秽，在 SQL 中瓣履，數(shù)據(jù)列就是自由變量率翅。例如练俐，在查詢 SELECT 1 + a 中的 a 就是一個自由變量。當(dāng)檢查表達(dá)式 1 + a 時冕臭，我們無法確定變量 a 的類型腺晾；若 a 是表的數(shù)據(jù)列，我們需要從表元數(shù)據(jù)中查詢 a 的類型辜贵。
若 a 是子查詢的結(jié)果列悯蝉，則需要先檢查子查詢以得到 a 的類型：
SELECT 1 + a from (SELECT number as a from numbers(100))
在上下文中，變量名稱與類型具有映射關(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ù)重載列表
plus(Int8, Int8) -> Int8
plus(Int16, Int16) -> Int16
...
我們發(fā)現(xiàn)沒有一個重載可完全符合入?yún)㈩愋汀５覀冎?Int8 可以無損地由 Int16 類型表示谐区，也就是說 Int8 是 Int16 的 subtype
Int8 <: Int16
為此我們稍微修改一下函數(shù)類型規(guī)則：
Γ? e1 : T1 Γ? e2 : T2 T1 <: Int16 T2 <: Int16
---------------------------------------------------
Γ? plus(e1, e2) : Int16
這樣可以推導(dǎo)出 1 + 256 的類型是 Int16湖蜕。
在實際實踐中，我們會在必要進行子類型轉(zhuǎn)換的地方插入 CAST宋列，所以 1 + 256 會變成 CAST(1 AS INT16) + 256昭抒。
Generic
在 Databend 中，我們支持?jǐn)?shù)組類型，例如：
? [1, 2, 3] : Array<Int8>
當(dāng)我們嘗試為數(shù)組定義函數(shù)時戈鲁，會發(fā)現(xiàn)無法列舉出所有重載仇参。以 get() 函數(shù)為例，該函數(shù)用于根據(jù)下標(biāo)從數(shù)組中提取一個元素婆殿，因此函數(shù)的返回類型取決于數(shù)組的元素類型诈乒。如下所示：
get(Array<Int8>, Int64) -> Int8
get(Array<Array<Int8>>, Int64) -> Array<Int8>
get(Array<Array<Array<Int8>>>, Int64) -> Array<Array<Int8>>
...
為了解決這個問題，我們在 Typechecker 中引入了泛型婆芦。借助泛型怕磨，可以用一個簡單的重載定義 get() 函數(shù)：
get<T>(Array<T>, Int64) -> T
當(dāng)嘗試檢查表達(dá)式 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)：
enum Value {
Scalar(Scalar),
Column(Column),
}
enum Scalar {
Int8(i8),
Int16(i16),
Boolean(bool),
...
}
enum Column {
Int8(Vec<i8>),
Int16(Vec<i16>),
Boolean(Vec<bool>),
...
}
表達(dá)式 1 + a 通過類型檢查后得到 Expr 結(jié)構(gòu)：
Expr::FunctionCall {
name: "plus",
args: [
Expr::Constant(Scalar::Int8(1)),
Expr::ColumnRef("a"),
],
eval: Box<Fn([Value]) -> Value>,
}
FunctionCall 包含一個名為 eval 的閉包袋毙。這個閉包在類型檢查階段被確定，并負(fù)責(zé)實際的數(shù)據(jù)計算冗尤。由于 Databend 實現(xiàn)了向量化計算听盖，eval 會一次接收一批數(shù)據(jù)作為參數(shù)，并批量計算并輸出相同行數(shù)的結(jié)果裂七。特殊情況下皆看，如果輸入的每一行都相同，我們使用 Value::Scalar 進行存儲碍讯。
以 plus(Int8, Int8) 為例悬蔽，其定義類似于：
registry.register_function(Function {
signature: FunctionSignature {
name: "plus",
arg: [DataType::Int8, DataType::Int8],
return_type: DataType::Int8,
},
eval: |lhs: Value, rhs: Value| -> Value {
match (lhs, rhs) {
(Value::Scalar(Scalar::Int8(lhs)), Value::Scalar(Scalar::Int8(rhs))) => {
Value::Scalar(Scalar::Int8(lhs + rhs))
},
(Value::Column(Column::Int8(lhs)), Value::Scalar(Scalar::Int8(rhs))) => {
let result: Vec<i8> = lhs.iter().map(|lhs| *lhs + rhs).collect();
Value::Column(Column::Int8(result))
},
(Value::Scalar(Scalar::Int8(lhs)), Value::Column(Column::Int8(rhs))) => {
let result: Vec<i8> = rhs.iter().map(|rhs| lhs + *rhs).collect();
Value::Column(Column::Int8(result))
},
(Value::Column(Column::Int8(lhs)), Value::Column(Column::Int8(rhs))) => {
let result: Vec<i8> = lhs.iter().zip(rhs.iter()).map(|(lhs, rhs)| *lhs + *rhs).collect();
Value::Column(Column::Int8(result))
},
_ => unreachable!()
}
}
})
在這里我們看到相同的加法邏輯出現(xiàn)了 4 次，這是因為我們需要分別處理 Value::Scalar 或 Value::Column 的左右輸入?yún)?shù)情況捉兴。因此蝎困，我們可以將這個模式抽象出來：
impl FunctionRegistry {
fn register_2_arg_int8(&mut self, name: String, eval: impl Fn(i8, i8) -> i8) {
self.register_function(Function {
signature: FunctionSignature {
name: "plus",
arg: [DataType::Int8, DataType::Int8],
return_type: DataType::Int8,
},
eval: |lhs: Value, rhs: Value| -> Value {
match (lhs, rhs) {
(Value::Scalar(Scalar::Int8(lhs)), Value::Scalar(Scalar::Int8(rhs))) => {
Value::Scalar(Scalar::Int8(eval(lhs, rhs)))
},
(Value::Column(Column::Int8(lhs)), Value::Scalar(Scalar::Int8(rhs))) => {
let result: Vec<i8> = lhs.iter().map(eval(*lhs, rhs)).collect();
Value::Column(Column::Int8(result))
},
(Value::Scalar(Scalar::Int8(lhs)), Value::Column(Column::Int8(rhs))) => {
let result: Vec<i8> = rhs.iter().map(eval(lhs, *rhs)).collect();
Value::Column(Column::Int8(result))
},
(Value::Column(Column::Int8(lhs)), Value::Column(Column::Int8(rhs))) => {
let result: Vec<i8> = lhs.iter().zip(rhs.iter()).map(|(lhs, rhs)| eval(*lhs, *rhs)).collect();
Value::Column(Column::Int8(result))
},
_ => unreachable!()
}
}
});
}
}
這樣我們可以更方便地注冊 Int8 類型的算術(shù)函數(shù)：
registry.register_2_arg_int8("plus", |lhs: i8, rhs: i8| lhs + rhs);
registry.register_2_arg_int8("minus", |lhs: i8, rhs: i8| lhs - rhs);
這個模式中我們抽象出了處理 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)體：
struct Int8Type;
然后，將處理 Int8 類型數(shù)據(jù)的操作放入 Int8Type 中：
trait ValueType {
type Scalar;
fn data_type() -> DataType;
fn downcast_scalar(Scalar) -> Self::Scalar;
fn upcast_scalar(Self::Scalar) -> Scalar;
fn iter_column(Column) -> impl Iterator<Item = Self::Scalar>;
fn collect_iter(impl Iterator<Item = Self::Scalar>) -> Column;
}
impl ValueType for Int8Type {
type Scalar = i8;
fn data_type() -> DataType {
DataType::Int8
}
fn downcast_scalar(scalar: Scalar) -> Self::Scalar {
match scalar {
Scalar::Int8(val) => val,
_ => unreachable!(),
}
}
fn upcast_scalar(scalar: Self::Scalar) -> Scalar {
Scalar::Int8(scalar)
}
fn iter_column(col: Column) -> impl Iterator<Item = Self::Scalar> {
match col {
Column::Int8(col) => col.iter().cloned(),
_ => unreachable!(),
}
}
fn collect_iter(iter: impl Iterator<Item = Self::Scalar>) -> Column {
let col = iter.collect();
Column::Int8(col)
}
}
在定義了必要操作之后诉植，我們可以對 register_2_arg_int8 進行修改祥国。我們將輸入?yún)?shù)類型從固定的 i8 更改為靈活的三個泛型 I1，I2 和 Output晾腔，分別表示第一個參數(shù)類型舌稀、第二個參數(shù)類型和輸出類型：
impl FunctionRegistry {
fn register_2_arg<I1: ValueType, I2: ValueType, Output: ValueType>(&mut self, name: String, eval: impl Fn(I1::Scalar, I2::Scalar) -> Output::Scalar) {
self.register_function(Function {
signature: FunctionSignature {
name: "plus",
arg: [I1::data_type(), I2::data_type()],
return_type: Output::data_type(),
},
eval: |lhs: Value, rhs: Value| -> Value {
match (lhs, rhs) {
(Value::Scalar(lhs), Value::Scalar(rhs)) => {
let lhs: I1::Scalar = I1::downcast_scalar(lhs);
let rhs: I2::Scalar = I2::downcast_scalar(rhs);
let res: Output::Scalar = eval(lhs, rhs);
Output::upcast_scalar(O::upcast_scalar(res))
},
...
}
}
});
}
}
現(xiàn)在，我們已經(jīng)借助 Rust 泛型系統(tǒng)將類型信息抽象化：
registry.register_2_arg::<Int8Type, Int8Type, Int8Type>("plus", |lhs: i8, rhs: i8| lhs + rhs);
registry.register_2_arg::<Int8Type, Int8Type, Int8Type>("minus", |lhs: i8, rhs: i8| lhs - rhs);
有了這個改進灼擂，我們可以非常方便地注冊其他類型的重載函數(shù)壁查，例如：
registry.register_2_arg::<Int16Type, Int16Type, Int16Type>("plus", |lhs: i16, rhs: i16| lhs + rhs);
registry.register_2_arg::<Int16Type, Int16Type, Int16Type>("minus", |lhs: i16, rhs: i16| lhs - rhs);
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 解析器和表達(dá)式框架。我們使用了諸如 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ù)與實踐。謝謝大家荞胡！
