資料庫核心雜談 - 一小時實現一個基本資料庫
作者：來自簡書的 Dr_GU
本文轉載自 Dr_GU 的簡書文章，技術瑣話授權轉載。
提到資料庫，對於一個 end user 來說，有哪些必要的基本功能？我覺得，至少得支援下面這些：
建立資料庫：create database，schema， table 等；
儲存資料：insert /update 資料，或者 load from external file （比如 csv 檔案）；
讀取查詢資料：透過 SQL 語句，對資料進行讀取和查詢，比如 sort，aggregate，filter 等。
根據這三個功能，再回看標題，你可能產生疑問，一個小時就能實現上面這些功能，不會是標題黨吧。恭喜你，答對了！我小小地標題黨了。講道理嘛，寫個簡單的 SQL parser 都要很久的，好嘛！既然是核心雜談，我們就假設已有 parser 的實現（透過自己寫 lexer，具體實現參考 Yacc 或 JavaCC），我們則更多地關注在資料庫系統本身的實現。好，拋開 Parser，又該從哪開始呢？我自己的理解是，由下而上，從儲存，到讀取，再到執行查詢。
儲存
最底層就是儲存。說到儲存，第一想到的就是檔案系統（其實說到底資料庫就是是一個特殊的檔案系統，區別與普通的檔案系統，資料庫這個 “系統” 的一切都是在為儲存，讀取和處理資料做最佳化）。怎麼把資料存在檔案裡，我們用這張 student 表作為示例來看。
student 表
最顯而易見的就是用 Comma-separated value （CSV） 格式存：
1，“Xiaoputao”，3，“Hiking”2，“Zgu”，3，“Running”3，“Xiaopang”，2，“Walking”
讀取 CSV 也非常簡單： delimited by ‘\n’ then separated by ‘，’。
除了 CSV 儲存，另一種非常流行的方式就是 json
［ {“id”：1， “name”：“Xiaoputao”， “class”：3， “hobby”：“running}， 。。。 ］
聊聊 CSV 和 JSON 儲存的優缺點。兩者都屬於文字儲存，優點一在於易於人類理解（方便我們 debug），另一個我個人覺得的優點就是直接相容其他支援 CSV 和 JSON 的資料庫。缺點也很明顯，儲存效率不高，讀取效率也會隨之降低。另一個問題在於，上述例子中儲存的內容只有值，沒有 type 和 size （metadata），這些資訊在後續操作如校驗中是很重要的。當然，我們可以把 metadata 加入到儲存中，比如，把 json 的每個 val 變成一個 obj：{”colName“：”id“，”colType“：”int“，”colSize“：4，”colVal“：1}。專業資料庫肯定不會選擇用 CSV 或 JSON 作為預設儲存，但幾乎都支援 CSV 和 JSON 資料作為 external table。咱們既然是一個小時實現一個基本資料庫，當然是能簡則簡。
思考得深一些，如果要追求效能，應該怎麼存呢？Raw bytes 肯定把文字模式高效很多。就像生活大爆炸裡說的，世界本來就只有 0 和 1。如果以 Raw bytes 來存資料，應該怎麼設計，優點在哪，留個思考題給大家。
讀取
基於上述的儲存，讀取資料非常簡單 （允許我們呼叫一下 parsing 的 API），重點在於讀取完存放在怎樣一個數據結構中方便後續對資料進一步的查詢操作。根據資料的特性，結果集 （RowSet） 是由一序列的行資料 （Row） 組成，每一行又由多個單元 （Cell） 組成。我們試著根據這個概念設計下面這些類：
Cell， Row， RowSet Class
簡單梳理下，每個 Cell 存 type，size，和 value，Row 存一整行 cell，RowSet 存一序列 Row。具體在使用，生成的時候還有很多細節，如 typecheck， 確保每行列數相同，等等，暫且略過。定義了儲存方式和資料結構，具體資料讀取程式碼如下：
讀取
csvToRowSet 和 jsonToRowSet 的具體實現沒啥特色，在此省略。
執行查詢
實現了讀取，下面就是執行 SQL 查詢語句了。執行的複雜度主要取決於 SQL 語句的複雜度。比如，上面的讀取方法就已經實現了
select * from student；
語句。下面，我們一起來實現一些基本的查詢語句。
第一個想到非常簡單的
Limit：
Limit Operator
一行程式碼，不解釋了。抬走！
下一個，
Projection
：對於現有 row 的 cells，進行各種 scalar compute expression，如下示例：
select id + 5， len（name） from student；
Projection 可以非常複雜，但有一條不會變，projection 不改變原有 RowSet 的 cardinality。無論計算邏輯多複雜，輸入一個 Row，輸出一個 Row。再複雜的計算，也是一比一步迭代產生。比如上邊這示例就需要執行這些操作來完成：對於每一行 input row， id 值加 5，對 name 取 length，最後去掉 class 和 hobby 兩列。歸根到底就是將複雜地運算拆分成 atomic operators 然後一步一步地順序執行。我們可以定義如下兩個基本 operator：RowComputeOperator 根據定義的 computeCellVal 對 input row 計算一個新 cell，並把這個 cell 加到原 row 的末尾。SelectionOperator 根據給定的 indexes， 產生一個僅包含指定 index 的新 row。Pseudo code 如下：
RowComputeOperator 裡面有需要定義 computeCellVal，輸入是一個 row， 輸出一個新的 cell。怎麼去實現呢？一個簡單的想法是，定義一個 computeCellVal 需要 2 個引數，1）作用在哪些 cell 上，假設限制只能作用在 1 個或 2 個 cell 上 （2 個以上可以用多個 Operator 巢狀）；2）提供計算的 operator，比如常見的 unaryOperator 如 len （）， ceiling （）， abs （） 等等，常見的 binaryOperator 如 +-*/ 等等。
有了這兩個基本 operator， 實現示例的 projection，我們定義 3 個 operator 即可：1）compute a new cell using （id + 5）； 2） compute a new cell using len （name） ；3） select 最後兩個新生成的 cell。
實現整個 projection 的 operator 的 pseudo code 如下：
Projection Operator
有了 Projection，我們就可以實現
Filter Operator (Where)
：
select * from student where
class = 3
；
演算法很簡單，用 Projection operator 計算出 filter condition 的值 （bool），然後 filter by 這個 column 即可。
Filter Operator
下一個是
Sort(Order By)
：
我給一個非常低效但很容易理解地實現，存 hashmap
Sort Operator
有人問，如果 order by 是 composite expression 比如 id + 10 呢？ Projection operator is your friend！
一起實現了 4 個 Operator，有沒有發現什麼規律？Bingo！ 所有的 Operator 都是 take a RowSet then output a RowSet， 並且，是一層一層 hierarchical 的。也就是說，對於資料的查詢操作，可以想象成，從最初讀取表中的原始資料開始，一層一層地對於資料 apply 各種 operator；這一個 Operator 的輸出就是下一個 operator 的輸入。也就是說，給定一個 SQL 查詢語句，我們生成一序列 Operator 的 tree，再依次執行，就能得到最終結果。我們做就能最佳化一下程式碼，把 Operator 的介面抽象出來，然後把剛才實現的 operator 全當成子類來實現。程式碼如下：
Unary Operator
這邊為啥定義基類叫 UnaryOperator 呢？先賣個關子。有了基類，我們可以為 SQL 不同的語法實現各種 Operator。再來看看還有哪些常見的 operator 呢？Aggregation。Aggregation 分為兩大類，scalar-agg 和 multi-agg。scalar-agg 就是簡單的 sum， avg， min， max 等 agg 操作，最終返回為 one dimension 結果，實現程式碼如下：
Scalar-agg
每個 AggOp 接受一個 list 的 cells，然後 output aggregated value cell。AggOp 如 sum， max，min 實現都很簡單，略過。
multi-agg 對應 SQL 中的 GROUP By，需要先把有相同值的 group by columns 的 row 合併起來（可以用 hashMap），再對 agg column 求 aggregation。演算法不難，留做回家作業！
萬事俱備，只欠東風，看看怎麼用 Operator tree 來實現查詢 SQL！比如下面這個 sql （雖然，沒啥具體意義）：
select class， sum（id + len（name）） as cfrom （select * from student where hobby = ‘hiking’ limit 10）group by class；
我們只要建立如下的 Operator tree （請別仔細地驗證）：
Operator Tree
有沒有覺得挺神奇的！即使再複雜得 SQL 都能這樣用基本的 operator 像搭樂高那樣搭建起來，只是最後搭建起來的樂高也很複雜罷了。
好啦，差不多快一個小時了，我們簡單的資料庫也實現得差不多啦。雖然資料結構冗餘，演算法低效，但是麻雀雖小，五臟俱全！更重要的是，從中我們理解了，任何複雜的 SQL 語句 to the end 都能分解成最基本的 operator，然後一步一步生成 operator tree 來實現。要支援新的 SQL 語法，只需要實現新的 Operator 即可。好！來說最後一個關子，為什前面定義 UnaryOperator？因為我們還有 BinaryOperator ！For what？For Joy~~ （諧音 Join）。真心的，並不是故意不想講，主要一講感覺輕鬆就超過一個小時，顯得我更標題黨了。退一步講，好多 NoSQL 還不支援 join 呢。咱們劃拉劃拉把 join 劃到非 basic operator 啦 （以後單開一節講）。簡單說一說，JoinOperator takes two RowSet， join the two based on given join conditions。具體實現起來，這個坑就深了。以 hashJoin 為例，對於要 join 的 columns，對 inner table （cardinality 小的 table） 建 hashmap，然後遍歷另一個 table 的 rowSet， 如果有 hit hashMap，就表示 hit 了一次 join condition，output rows from both side。Join Operator 生成的 Operator Tree 如下圖：
Join Operator Tree
小結
不容易呢！一個小時實現一個基本資料庫不難，一天寫一篇 blog 才是真難！對於那些能堅持寫技術部落格的，簡直是佩服再佩服！希望自己也能繼續堅持！復讀的時候發現自己總是中英文互相切換，有些時候真是詞窮，各位看官多擔待。並不是刻意要走 tvb 風格的。
寫這樣一篇其實是覆盤和小葡萄的討論。當時覺得自己說了大半個小時，就把這些最基本的全講了。所以覺得，寫下來應該也不會太長吧。結果，寫了一整天！但是，我要強調的是，看了自己寫的 pseudo code 也就 200 多行 （雖然做了多處省略，但都不是關鍵點），1 個小時內肯定能寫完的，所以不算標題黨！
真正的第一篇就到這啦！給大家總結一下：
一個 SQL 語句再複雜，也能拆分成一個個 atomic 的 operator。沒有哪個語法是一個 operator 不能解決的 （如果不能，就兩個 ：））。
把這些 operator 組建成一個 tree （術語裡叫 execution plan tree），然後自底向上地執行，就能得到最終結果。
你可能覺得真正的資料庫和咱們在這自己搗鼓的很不一樣，try ”EXPLAIN SQL_STMT“ in Postgres or Mysql。
很多人都非常熟悉用 SQL 做各種查詢，可能從沒去想過底層是怎樣實現的。希望這篇部落格對你有所幫助，作為一個 solid enginner，應該知其然，知其所以然！
下一篇，咱們深入聊聊儲存！
