SQL 的三維側(cè)寫

SQL 起源于上世紀(jì)七十年代的 IBM R 系統(tǒng)，是一個針對關(guān)系型數(shù)據(jù)庫的聲明式查詢語言。一句話引出三個點：

1. 關(guān)系型（relational）：基于關(guān)系代數(shù)理論的一種數(shù)據(jù)建模方式，其他的建模方式如文檔數(shù)據(jù)庫、圖數(shù)據(jù)庫等。以 SQL 表的方式來理解，可以將任何數(shù)據(jù)集抽象為一張二維表，每行一個元組（tuple），每個元組有多個屬性列；將對數(shù)據(jù)集的查詢抽象為一組運算符的組合，也即二維表的一組變換。常見的運算符：

關(guān)系表的變換

選擇 (σ)：針對單張二維表，選擇其中一些行；對應(yīng) SQL 中 where 子句

投影 (π)：針對單張二維表，選擇其中某幾列；對應(yīng) SQL 中 select xx 子句

自然連接 (?)：針對兩張二維表，按某一列上等值進行合并；對應(yīng) SQL 中 join 子句

2. 聲明式（declarative）：與命令式（imperative）相對，可類比編程中的接口。側(cè)重于描述而非實現(xiàn)。舉個例子感受一下：

聲明式：“找出教三今天的空閑教室”

命令式：“1. 找出教三所有教室 2. 對于每間教室查詢課表看其是否空閑 3. 如果空閑則加入結(jié)果集”

3. 查詢語言（Query）：顧名思義，這是一門專門用來做諸如“找教室”一類的對滿足條件的數(shù)據(jù)進行查詢的語言。雖然他是圖靈完備的，但一般不用于像通用編程語言 C++ 等來編寫復(fù)雜軟件。

SQL 執(zhí)行過程

CMU 15445 課程圖

SQL 也是一門語言，因此其執(zhí)行過程和編譯器前端類似，參考上圖（來自 cmu 15-445）可粗分為數(shù)個步驟：

解析（Parsing）：將適合人閱讀的 SQL 語句進行分詞（token），并進行基本語法檢查。然后基于關(guān)系代數(shù)，構(gòu)建成抽象語法樹（AST，Abstract Syntax Tree）。其中葉子節(jié)點為表，中間節(jié)點為運算符。

校驗（Validating）：檢查所插入數(shù)據(jù)格式是否滿足之前所定義的模式。舉個例子，學(xué)生表定義了學(xué)號、姓名、課程三列，則插入的數(shù)據(jù)每一行不能多于三個屬性。

計劃（Planning）：使用模式信息，將語法樹中元素（各種有意義的名稱）轉(zhuǎn)成內(nèi)部表示（各種 無意義且不重復(fù) id），生成邏輯計劃。

優(yōu)化（Optimization）：邏輯計劃由多個數(shù)據(jù)變換操作構(gòu)成，我們可以基于關(guān)系代數(shù)中算子的一些性質(zhì)（比如交換性、結(jié)合性），調(diào)整變換順序和組合，使得查詢所耗費資源（包括計算、存儲和網(wǎng)絡(luò)帶寬等）最小，最后生成物理執(zhí)行計劃，常包括基于規(guī)則和基于代價的兩種方式。

執(zhí)行（Execution）：將優(yōu)化過后的執(zhí)行計劃（一般仍是樹形）進行執(zhí)行。包括從外存撈數(shù)據(jù)到內(nèi)存和在內(nèi)存中對數(shù)據(jù)做各種變換。不管數(shù)據(jù)在外存表現(xiàn)為什么形式，撈到內(nèi)存后可以理解為一張前面提到的二維表，然后按樹結(jié)構(gòu)施加各種算子，進行計算。

有時候校驗階段也被歸入解析范疇，有時候執(zhí)行階段中的表達式求值會單拎出來說，但總的職責(zé)就這幾個，排列順序基本確定，只是劃分可能有出入。

之后對于每個階段，會分別出一篇小文。

參考

https://15445.courses.cs.cmu.edu/fall2022/notes/02-modernsql.pdf

https://15445.courses.cs.cmu.edu/fall2022/notes/14-optimization.pdf

Database System Concepts, Chapter 15 Query Processing and Chapter 16 Query Optimization