一文走進SQL編譯-語義解析

一、概述

SQL 引擎主要由三大部分構成：解析器、優化器和執行器。

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

?

本文將重點介紹 KaiwuDB 語義解析部分，其輸入為 AST 語法樹，輸出為可供優化器使用的 Expr 表達式。

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

檢查數據庫或表是否存在

檢查語句所需的特定權限

對語句中的表達式進行語義解析

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

二、語義解析

?

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

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

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

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

確定用于中間結果的數據類型

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

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

Source and target analysis （目標解析）

Permission check （權限校驗）

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

?

1. 目標解析及權限校驗

1）接口路徑：

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

2）核心接口為：

?

ResolveDataSource 通過 object name 解析出對象描述符（元數據），Privilege check 使用 current username 來校驗當前用戶對該對象是否有相應權限。

在完成目標解析和權限校驗后，會為 select stmt 中的 from clause 構建 memo 表達式。這個行為看似不是語義解析應該做的，出現在這里的原因是 KaiwuDB 的語義解析和部分邏輯計劃優化是相互融合的。

2. 表達式拆分及其語義解析

1）接口路徑：

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

KaiwuDB 將 select stmt 中的各個部分拆分為表達式，并對其進行標量表達式的語義解析，從而完成 scalarExpr 的構建。例如：

?

2）標量表達式語義解析：

ROLE：檢查表達式是否合法，為其做一些初步的優化，為其賦予類型。

INTERFACE：

in : Expr

out : TypedExpr

實質上是檢查并賦予類型 + 簡化表達式

AnalyzeExpr()

HOW：

i. Name Resolution

ii. TypeCheck

iii. Normalize Expr

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

注意：可以使用 EXPLAIN(EXPRS, TYPES) 來檢查表達式，而不進行解構和簡化。

i. Name Resolution

? ?

參數 sources 和 IndexedVars，如果都不是 nil，則表示 resolveNames 應該被執行。IndexedVars map 將被填充并且作為結果返回。

用 parser.IndexedVar 實例替換列名

用 parser.FuncDef 引用替換函數名

ii. TypeCheck

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

常數折疊

類型推斷

類型檢查

在 ComparisonExpr 節點上記憶比較器函數

用其類型來注釋表達式和占位符

實現 Expr 接口的表達式有很多：AndExpr, OrExpr, CastExpr, CaseExpr 等。

每個表達式都實現了 TypeCheck 接口，在被調用時返回結果表達式的類型，包括bool, string, int 等。

iii. Normalize parser.NormalizeExpr()：

注意：此處的 normalize 有點不太準確，因為他并沒有進行標準的 normalize，這里只是將除變量名以外的東西都放到比較符號的右側，從而達到簡化的目的。

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 的實現主要依靠 WalkExpr 函數。WalkExpr 會橫穿 Expr，其通過傳入對應的 visitor 來定義 WalkExpr 的具體行為，前面講到的 name resolution 也是通過傳入 name resolution visitor 實現的。

審核編輯：劉清