SQL 的三維側(cè)寫(xiě)

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

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

關(guān)系表的變換

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

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

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

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

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

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

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

SQL 執(zhí)行過(guò)程

CMU 15445 課程圖

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

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

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

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

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

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

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

之后對(duì)于每個(gè)階段，會(huì)分別出一篇小文。

參考

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