SQL 的三維側寫

SQL 起源于上世紀七十年代的 IBM R 系統，是一個針對關系型數據庫的聲明式查詢語言。一句話引出三個點：

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

關系表的變換

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

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

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

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

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

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

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

SQL 執行過程

CMU 15445 課程圖

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

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

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

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

優化（Optimization）：邏輯計劃由多個數據變換操作構成，我們可以基于關系代數中算子的一些性質（比如交換性、結合性），調整變換順序和組合，使得查詢所耗費資源（包括計算、存儲和網絡帶寬等）最小，最后生成物理執行計劃，常包括基于規則和基于代價的兩種方式。

執行（Execution）：將優化過后的執行計劃（一般仍是樹形）進行執行。包括從外存撈數據到內存和在內存中對數據做各種變換。不管數據在外存表現為什么形式，撈到內存后可以理解為一張前面提到的二維表，然后按樹結構施加各種算子，進行計算。

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

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

參考

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