歡迎閱讀數(shù)據(jù)庫內(nèi)核雜談的第一篇。今天我們摒棄直接介紹數(shù)據(jù)庫內(nèi)核各個(gè)模塊的思路杨幼，而是從應(yīng)用開發(fā)者的角度出發(fā)撇簿，來看實(shí)現(xiàn)一個(gè)數(shù)據(jù)庫需要哪些基本功能聂渊，然后把這些功能細(xì)分成最小的模塊再手把手一起實(shí)現(xiàn)，幫你揭開數(shù)據(jù)庫內(nèi)核的神秘面紗四瘫。希望能夠減輕你對學(xué)習(xí)數(shù)據(jù)庫內(nèi)核的壓力汉嗽。我們也可以從中體會(huì)到，九層之臺(tái)找蜜，起于累土饼暑。所有復(fù)雜的系統(tǒng)，都是通過模塊化的架構(gòu)和設(shè)計(jì)洗做，以及工程階段的精益求精撵孤，一步一步累計(jì)起來。
對與應(yīng)用開發(fā)者而言竭望，一個(gè)數(shù)據(jù)庫需要哪些必要的功能呢邪码？我覺得，下面這些是必不可少的：
1）創(chuàng)建數(shù)據(jù)庫和數(shù)據(jù)表：create database咬清，schema, table等
2）存儲(chǔ)數(shù)據(jù)：insert /update數(shù)據(jù)闭专，或者從其他方式導(dǎo)入數(shù)據(jù)(比如csv文件)
3）讀取查詢數(shù)據(jù)：通過SQL語句，對數(shù)據(jù)進(jìn)行讀取和查詢旧烧，比如sort影钉，aggregate，filter等
根據(jù)這三個(gè)功能掘剪，再回看標(biāo)題平委，你可能產(chǎn)生疑問，一個(gè)小時(shí)就能實(shí)現(xiàn)上面這些功能夺谁，不會(huì)是標(biāo)題黨吧廉赔。我承認(rèn)，有一點(diǎn)小小得標(biāo)題黨了匾鸥。因?yàn)橐蛿?shù)據(jù)庫交互蜡塌，最必要的條件是有個(gè)客戶端程序可以接受用戶送來的指令。但要實(shí)現(xiàn)一個(gè)功能齊全的Parser可得花不少精力勿负。既然是內(nèi)核雜談馏艾，請?jiān)试S我偷個(gè)懶，假設(shè)Parser已經(jīng)有實(shí)現(xiàn)奴愉，從而把精力都關(guān)注在數(shù)據(jù)庫系統(tǒng)內(nèi)部的實(shí)現(xiàn)琅摩。拋開Parser，又該從哪開始呢锭硼？我的思路是跟著數(shù)據(jù)的流向房资，自下而上，依次從存儲(chǔ)數(shù)據(jù)账忘，讀取數(shù)據(jù)和查詢數(shù)據(jù)來看志膀。
創(chuàng)建和存儲(chǔ)數(shù)據(jù)
當(dāng)用戶創(chuàng)建一個(gè)新的數(shù)據(jù)庫熙宇，并導(dǎo)入數(shù)據(jù)時(shí)，數(shù)據(jù)庫系統(tǒng)就需要存儲(chǔ)這些數(shù)據(jù)溉浙。說到存儲(chǔ)烫止，第一個(gè)想法就是文件系統(tǒng)（其實(shí)說到底數(shù)據(jù)庫系統(tǒng)就是一個(gè)特殊的文件系統(tǒng)，區(qū)別與普通文件系統(tǒng)提供的的讀寫文件的接口戳稽，數(shù)據(jù)庫只是提供了一個(gè)面向數(shù)據(jù)的接口：存儲(chǔ)馆蠕，讀取和查詢；整個(gè)系統(tǒng)為這些接口提供服務(wù))惊奇。以下圖student表作為示例互躬，要怎么把這張表存在文件中呢？
最顯而易見的就是用Comma-separated value(CSV)格式存:
1,"Xiaoputao",3,"Hiking"
2,"Zgu",3,"Running"
3,"Xiaopang",2,"Walking"
讀取CSV文件的邏輯也非常簡單: 一行一行讀取數(shù)據(jù)颂郎，然后根據(jù)";"把每個(gè)數(shù)據(jù)段取出吼渡。
除了CSV存儲(chǔ)，另一種常見的方式就是json格式:
[ {"id":1, "name":"Xiaoputao", "class":3, "hobby":"running}, ... ]
聊聊CSV和JSON存儲(chǔ)的優(yōu)缺點(diǎn)乓序。兩者都屬于文本存儲(chǔ)寺酪，優(yōu)點(diǎn)一在于易于人類理解。另一個(gè)優(yōu)點(diǎn)就是直接兼容其他支持CSV和JSON的數(shù)據(jù)庫替劈。缺點(diǎn)也很明顯寄雀，存儲(chǔ)效率不高，讀取效率也會(huì)隨之降低陨献。另一個(gè)問題在于盒犹，上述例子中存儲(chǔ)的內(nèi)容只有值，沒有type和size(metadata)眨业，這些信息在后續(xù)操作如校驗(yàn)中是很重要的急膀。當(dāng)然，我們可以把metadata加入到存儲(chǔ)中坛猪，比如脖阵，把json的每個(gè)val變成一個(gè)obj:{"colName":"id","colType":"int","colSize":4,"colVal":1}。專業(yè)數(shù)據(jù)庫肯定不會(huì)選擇用CSV或JSON作為默認(rèn)存儲(chǔ)墅茉，但幾乎都支持CSV和JSON數(shù)據(jù)作為external table。如果要追求更高的性能呜呐，我們可以選擇更高效的編碼方式把數(shù)據(jù)以字節(jié)流的形式存儲(chǔ)在文件中就斤；只要數(shù)據(jù)庫系統(tǒng)自身能夠讀取這些數(shù)據(jù)即可。咱們既然時(shí)間有限蘑辑，當(dāng)然是一切從簡洋机，就選擇CSV或者JSON的文件格式來存儲(chǔ)我們的數(shù)據(jù)。
只要有一個(gè)文本編輯器洋魂，能夠創(chuàng)建和編輯CSV或者JSON文件绷旗。這其實(shí)這已經(jīng)完成了創(chuàng)建數(shù)據(jù)表喜鼓，輸入，修改以及存儲(chǔ)數(shù)據(jù)的功能衔肢。
讀取數(shù)據(jù)
基于上述用CSV或JSON的存儲(chǔ)庄岖，讀取數(shù)據(jù)非常簡單(允許我們調(diào)用第三方支持CSV或者JSON的API)。重點(diǎn)在于讀取完存放在怎樣一個(gè)數(shù)據(jù)結(jié)構(gòu)中方便后續(xù)對數(shù)據(jù)進(jìn)一步的查詢操作角骤。根據(jù)數(shù)據(jù)的特性隅忿，結(jié)果集(RowSet)是由一序列的行數(shù)據(jù)(Row)組成，每一行又由多個(gè)單元(Cell)組成邦尊。我們試著根據(jù)這個(gè)概念設(shè)計(jì)下面這些類：
簡單梳理下背桐，每個(gè)Cell存type，size蝉揍，和value链峭；Row存一整行cell；RowSet存一序列的Row又沾。具體在實(shí)現(xiàn)中還有很多細(xì)節(jié)需要注意弊仪，如typecheck, 確保每行列數(shù)相同，等等捍掺，這里也一并從簡略過撼短。定義了存儲(chǔ)方式和數(shù)據(jù)結(jié)構(gòu)，具體數(shù)據(jù)讀取代碼如下
csvToRowSet和jsonToRowSet的實(shí)現(xiàn)只需要借助第三方CSV和JSON的類庫就能實(shí)現(xiàn)挺勿，就不贅述代碼了曲横。
這一節(jié)里，我們定義了Cell, Row, RowSet的數(shù)據(jù)結(jié)構(gòu)來存放從文件(CSV或JSON)中讀取的數(shù)據(jù)不瓶，并給出了示例代碼禾嫉。
執(zhí)行查詢
有了存儲(chǔ)和讀取，已經(jīng)可以把數(shù)據(jù)從文件中讀取到內(nèi)存蚊丐，接下來就要支持用戶的查詢語句了熙参。實(shí)現(xiàn)查詢就是去實(shí)現(xiàn)SQL語句中的各個(gè)功能模塊，比如排序(order by), 聚合(group by)麦备，多表聯(lián)合(join)等等孽椰。執(zhí)行器會(huì)對每個(gè)功能模塊進(jìn)行實(shí)現(xiàn)，甚至針對不同的數(shù)據(jù)分布黍匾，會(huì)有多種方式的實(shí)現(xiàn)來提高讀取速度。現(xiàn)在呛梆，我們一起來討論一些常用的語言功能锐涯。
全表讀取(SELECT *)
其實(shí)纹腌，定義了RowSet的數(shù)據(jù)結(jié)構(gòu)和實(shí)現(xiàn)了讀取文件的接口莱褒，我們的數(shù)據(jù)庫就已經(jīng)支持全表讀取的SQL語句保礼，示例如下：
SELECT * FROM student;
分頁語句(LIMIT)
一下子就能想到的分頁語句，用來限制輸出的數(shù)據(jù)行數(shù)：
一行代碼白筹，不解釋了系馆。抬走由蘑！
關(guān)系映射語句(PROJECTION)
關(guān)系映射的本質(zhì)是對于輸入的RowSet的每一行(row), 通過各種標(biāo)量計(jì)算尼酿，輸出一個(gè)新的數(shù)據(jù)行，再由這些行組成新的RowSet思币。見下圖示例：
SELECT id + 5, LEN(name) FROM student;
對從student表讀取的每一行數(shù)據(jù)抢野，輸出一個(gè)新的數(shù)據(jù)行包含 id + 5 和 LEN(name)的cells贬堵。
Projection可以非常復(fù)雜，但有一條準(zhǔn)則就是它不改變原有RowSet的基數(shù)(cardinality), 即新RowSet的行數(shù)和原來的相同蒸殿。因此酥艳，無論映射邏輯多復(fù)雜充石，輸入一個(gè)Row坷剧，輸出一個(gè)Row惫企。再復(fù)雜的計(jì)算，也是一比一步迭代產(chǎn)生禽车。比如上述示例可以分解成下面這些操作來完成：對于每一行input row, id值加5瓢颅，對name取length挽懦，最后去掉class和hobby兩列信柿。歸根結(jié)底就是將復(fù)雜的運(yùn)算拆分成原子操作然后一步一步地順序執(zhí)行蝗岖。我們可以定義如下兩個(gè)基本operator：RowComputeOperator根據(jù)定義的computeCellVal對input row計(jì)算一個(gè)新cell，并把這個(gè)cell加到原row的末尾邢享。SelectionOperator根據(jù)給定的indexes鹏往，生成一個(gè)僅包含指定index的新row。Pseudo code如下：
RowComputeOperator里面有需要定義computeCellVal骇塘，輸入是一個(gè)row,輸出一個(gè)新的cell伊履。具體實(shí)現(xiàn)則根據(jù)具體語義來定。定義一個(gè)computeCellVal需要2個(gè)參數(shù)：1）運(yùn)算作用在哪些cell上款违，假設(shè)限制只能作用在1個(gè)或2個(gè)cell上(2個(gè)以上可以用多個(gè)Operator嵌套)唐瀑；2）提供具體計(jì)算的操作，比如常見單元操作如len(), ceiling(), abs()或者常見的二元操作如+-*/等等插爹。
有了這兩個(gè)基本operator, 實(shí)現(xiàn)示例中的projection哄辣，我們定義3個(gè)operator即可：1）compute a new cell using "(id + 5)" 2) compute a new cell using "len(name)" 3) 用SelectionOperator選擇最后兩個(gè)新生成的cell。
實(shí)現(xiàn)整個(gè)projection的operator的pseudo code如下：
條件選擇語句(WHERE)
有了Projection，我們就可以實(shí)現(xiàn)下面的條件選擇語句(WHERE)了：
SELECT * FROM student WHERE?class = 3;
實(shí)現(xiàn)想法很簡單柔滔，首先用Projection operator計(jì)算出filter condition的值(bool)溢陪，然后filter by 這個(gè)cell即可。
排序語句(ORDER BY)
這里睛廊，我給一個(gè)非常低效但很容易理解的實(shí)現(xiàn)：創(chuàng)建一個(gè)hashmap來存<cell, id>，然后對要sort的cell排序杉编，根據(jù)cell順序取出原row組成新的rowSet輸出：
有讀者會(huì)問超全，如果排序語句是一個(gè)expression而不是單個(gè)column怎么辦？比如下面的示例:
SELECT * FROM student ORDER BY id + 5 ASEC;
還記得我們前面實(shí)現(xiàn)的projection嗎邓馒？這里把(id + 5)作為一個(gè)新的projection加入到Row中即可嘶朱。
一起實(shí)現(xiàn)了4個(gè)Operator，看看有沒有什么規(guī)律可循光酣？所有定義的操作都是基于一個(gè)原則：輸入一個(gè)RowSet疏遏，然后輸出一個(gè)RowSet。并且救军，是一層一層循序漸進(jìn)的迭代财异。對于數(shù)據(jù)的查詢操作，是從最初讀取表中的原始數(shù)據(jù)開始唱遭，根據(jù)給定的Operator序列對數(shù)據(jù)逐一進(jìn)行操作戳寸；這一個(gè)Operator的輸出就是下一個(gè)operator的輸入。也就是說拷泽，給定一個(gè)SQL查詢語句疫鹊，我們生成一序列Operator的tree，再依次執(zhí)行司致，就能得到最終結(jié)果〔疬海現(xiàn)在來一起優(yōu)化下代碼，把Operator的接口抽象出來脂矫，然后把剛才實(shí)現(xiàn)的operator全當(dāng)成子類來實(shí)現(xiàn)枣耀。代碼如下：
有讀者會(huì)有疑問，基類為什么叫UnaryOperator呢羹唠？先賣個(gè)關(guān)子奕枢。有了基類，我們可以根據(jù)SQL的語法功能實(shí)現(xiàn)相應(yīng)的Operator佩微。
聚合操作(AGGREGATION)
接著一起來實(shí)現(xiàn)聚合操作缝彬。Aggregation分為兩大類，scalar-agg和multi-agg哺眯。scalar-agg就是簡單的sum, avg, min, max等的數(shù)據(jù)聚合操作谷浅，最終返回一個(gè)數(shù)據(jù)行的結(jié)果集，實(shí)現(xiàn)代碼如下：
每個(gè)AggOp接受一序列的cells，然后輸出聚合結(jié)果的cell一疯。常見的AggOp如sum, max撼玄，min實(shí)現(xiàn)都很簡單，這邊就不贅述了墩邀。
multi-agg對應(yīng)SQL中的GROUP By掌猛，如下圖示例：
SELECT class_room, COUNT(*) FROM student;
比scalar-agg復(fù)雜的地方就是先要把有相同值的group by columns(示例中為class_rom)的row合并起來，然后對合并后的rows做Scala-agg即可眉睹。代碼我就不貼啦荔茬，當(dāng)留個(gè)小作業(yè)給大家。
SQL Operator Tree
有了實(shí)現(xiàn)基本語義的Operator竹海，要實(shí)現(xiàn)一個(gè)完整的查詢語句慕蔚，我們要做的就是把operator一層一層的累加起來，形成一個(gè)Operator tree斋配，然后根據(jù)這個(gè)operator tree, 依次執(zhí)行每一個(gè)operator即可孔飒。比如下面這個(gè)查詢語句：
select class, sum(id + len(name)) as c
from (
? ? select * from student where hobby = 'hiking' limit 10
)
group by class;
我們只要建立如下的Operator tree：
有沒有覺得挺神奇的！即使再復(fù)雜的查詢SQL都能這樣用基本的operator像搭樂高一樣搭建起來艰争。
小結(jié)
至此坏瞄，我們簡單的數(shù)據(jù)庫也實(shí)現(xiàn)得差不多啦。我看了下自己寫的pseudo code僅僅200多行园细，一個(gè)小時(shí)寫完也不算條件太苛刻惦积。雖然數(shù)據(jù)結(jié)構(gòu)冗余，算法低效猛频，但是麻雀雖小狮崩，五臟俱全！
來解釋前面賣的關(guān)子鹿寻，為什么基類定義為UnaryOperator睦柴？因?yàn)槲覀冞€有BinaryOperator。二元的操作是做什么的呢毡熏？答案就是為了表與表的聯(lián)合(join)坦敌。有了Binary Operator，Operator的疊加就真正變成了一顆樹(二叉樹)痢法，這也是為什么前文我們稱之為operator tree狱窘。本文就先不詳述如何實(shí)現(xiàn)Join Operator了，以后會(huì)有專門的章節(jié)來覆蓋财搁。再講下去蘸炸，肯定超過一個(gè)小時(shí)，讀者就更覺得我標(biāo)題黨了尖奔。
最后給大家總結(jié)一下：
1）一個(gè)SQL的查詢語句搭儒，即便邏輯再復(fù)雜穷当，也可以拆分成一個(gè)一個(gè)原子operator的疊加
2）把這些operator組建成一個(gè)operator tree，然后自底向上地依次執(zhí)行淹禾，就能得到最終的查詢結(jié)果
3) 你可能覺得真正的數(shù)據(jù)庫和我們在這搗鼓的很不一樣馁菜。如果有條件，可以在Mysql或者Postgres中運(yùn)行"EXPLAIN SQL_STMT"來打印它們生成的operator tree铃岔，你會(huì)發(fā)現(xiàn)和我們生成的樹挺相似的
4) 相信大家都非常熟悉用SQL做各種數(shù)據(jù)查詢汪疮，但可能從沒去想過底層是怎樣實(shí)現(xiàn)的。希望這篇博客對你有所幫助德撬。正所謂铲咨，知其然，知其所以然蜓洪！
下一篇，咱們深入聊聊存儲(chǔ)!
