一文走進(jìn)SQL編譯-語義解析

一、概述

SQL 引擎主要由三大部分構(gòu)成：解析器、優(yōu)化器和執(zhí)行器。

解析器的主要作用是將客戶端傳來的命令解析編譯成數(shù)據(jù)庫能識(shí)別運(yùn)行的命令，其主要由詞法解析、語法解析和語義解析三部分構(gòu)成，如下圖所示。

?

本文將重點(diǎn)介紹 KaiwuDB 語義解析部分，其輸入為 AST 語法樹，輸出為可供優(yōu)化器使用的 Expr 表達(dá)式。

KaiwuDB 中的語義解析主要包括：

檢查數(shù)據(jù)庫或表是否存在

檢查語句所需的特定權(quán)限

對語句中的表達(dá)式進(jìn)行語義解析

檢查 DDL 語句所請求的 schema change 的有效性

二、語義解析

?

KaiwuDB 中的語義解析主要包括以下流程：

檢查查詢是否為 SQL 語言中的有效語句

解析名稱，例如表名或變量名的值

消除不必要的中間計(jì)算，例如用 1.0 替換 0.6 + 0.4，這也被稱為常數(shù)折疊

確定用于中間結(jié)果的數(shù)據(jù)類型

其代碼流程介于 parser 和 memo 構(gòu)建之間，將 parser 輸出的 AST 中的對象進(jìn)行語義解析，語義解析的輸出作為 memo 構(gòu)建的輸入。

接下來，將重點(diǎn)介紹查詢語句的語義解析流程：

Source and target analysis （目標(biāo)解析）

Permission check （權(quán)限校驗(yàn)）

Semanticdecomposition & validation （表達(dá)式拆分及其語義解析）

?

1. 目標(biāo)解析及權(quán)限校驗(yàn)

1）接口路徑：

buildStmt() -> buildSelectStmtWithoutParent() -> buildSelectClause() -> builtFrom() -> buildDataSource()

2）核心接口為：

?

ResolveDataSource 通過 object name 解析出對象描述符（元數(shù)據(jù)），Privilege check 使用 current username 來校驗(yàn)當(dāng)前用戶對該對象是否有相應(yīng)權(quán)限。

在完成目標(biāo)解析和權(quán)限校驗(yàn)后，會(huì)為 select stmt 中的 from clause 構(gòu)建 memo 表達(dá)式。這個(gè)行為看似不是語義解析應(yīng)該做的，出現(xiàn)在這里的原因是 KaiwuDB 的語義解析和部分邏輯計(jì)劃優(yōu)化是相互融合的。

2. 表達(dá)式拆分及其語義解析

1）接口路徑：

buildStmt() -> buildSelectStmtWithoutParent() -> buildSelectClause()

KaiwuDB 將 select stmt 中的各個(gè)部分拆分為表達(dá)式，并對其進(jìn)行標(biāo)量表達(dá)式的語義解析，從而完成 scalarExpr 的構(gòu)建。例如：

?

2）標(biāo)量表達(dá)式語義解析：

ROLE：檢查表達(dá)式是否合法，為其做一些初步的優(yōu)化，為其賦予類型。

INTERFACE：

in : Expr

out : TypedExpr

實(shí)質(zhì)上是檢查并賦予類型 + 簡化表達(dá)式

AnalyzeExpr()

HOW：

i. Name Resolution

ii. TypeCheck

iii. Normalize Expr

這些子任務(wù)實(shí)現(xiàn)幾乎是純粹的函數(shù)，唯一的缺陷是， TypeCheck 將 SQL 占位符（$1、$2 等）的類型以一種對順序敏感的方式，輸出到通過遞歸傳遞的語義環(huán)境對象上。

注意：可以使用 EXPLAIN(EXPRS, TYPES) 來檢查表達(dá)式，而不進(jìn)行解構(gòu)和簡化。

i. Name Resolution

? ?

參數(shù) sources 和 IndexedVars，如果都不是 nil，則表示 resolveNames 應(yīng)該被執(zhí)行。IndexedVars map 將被填充并且作為結(jié)果返回。

用 parser.IndexedVar 實(shí)例替換列名

用 parser.FuncDef 引用替換函數(shù)名

ii. TypeCheck

parser.TypeCheck() / parser.TypeCheckAndRequire()：

常數(shù)折疊

類型推斷

類型檢查

在 ComparisonExpr 節(jié)點(diǎn)上記憶比較器函數(shù)

用其類型來注釋表達(dá)式和占位符

實(shí)現(xiàn) Expr 接口的表達(dá)式有很多：AndExpr, OrExpr, CastExpr, CaseExpr 等。

每個(gè)表達(dá)式都實(shí)現(xiàn)了 TypeCheck 接口，在被調(diào)用時(shí)返回結(jié)果表達(dá)式的類型，包括bool, string, int 等。

iii. Normalize parser.NormalizeExpr()：

注意：此處的 normalize 有點(diǎn)不太準(zhǔn)確，因?yàn)樗]有進(jìn)行標(biāo)準(zhǔn)的 normalize，這里只是將除變量名以外的東西都放到比較符號(hào)的右側(cè)，從而達(dá)到簡化的目的。

Normalize Example：

(a+1) < 3 is transformed to a < 2

-(a - b) is transformed to (b - a)

a between c and d is transformed to a >= c and a <= d

?

Normalize 的實(shí)現(xiàn)主要依靠 WalkExpr 函數(shù)。WalkExpr 會(huì)橫穿 Expr，其通過傳入對應(yīng)的 visitor 來定義 WalkExpr 的具體行為，前面講到的 name resolution 也是通過傳入 name resolution visitor 實(shí)現(xiàn)的。

審核編輯：劉清