数据库内核杂谈（一）：一小时实现一个基本功能的数据库

数据库内核博大精深，很多子系统的设计初看不知所云，但是细读就会发现其已经做到了极致。但是市面上很少有类似的资源或者课程把数据库内容的精髓讲解出来，因此 Facebook 现任 Tech Lead 顾仲贤撰写了《数据库内核杂谈》的系列文章。

开篇词

为啥想写这样一个系列?

最主要的原因肯定是出于兴趣吧，自从接触了数据库内核开发，觉得里面真的是博大精深，很多子系统的设计初看不知所云，细读就发现已经做到了极致。然后特别希望有大牛能够深入浅出地把这些精髓讲解出来。但可惜，一直没有发现类似的资源或者课程 (笔者虽然工作多年，但自觉还是比较注重积累，每天都关注科技新闻，技术博客甚至领域内的新的学术文章)。近期也看到有越来越多的付费培训，从算法到系统设计，到大数据，应有尽有，但唯独没有发现非常好的关于数据库内核设计的资源。自己当然没有实力可以去开那样一门课程，但我希望可以通过写 blog 来完善自己的知识储备。也希望读者能有所收获。不过想归想，自己从来没下定决心去做这样一件事，因为总是觉得自己积累还不够，还要准备准备云云。

什么契机让你真正去行动了？

这契机真的是一个非常偶然的故事。上个周末的一天晚上，小葡萄（我最爱且仅爱的老婆大人）正在给我洗脸。感觉闲着也是闲着，加之正好下午刚讨论过 SQL，我就半开玩笑地说，“老婆，你不是对数据库感兴趣吗？我给你讲讲数据库是怎么实现的，数据库是怎么去执行一个 SQL 语句的” 小葡萄：“你说呀，你能说得出来吗？”；“嘿，小看我，你听着哦 。。。” 然后我就 blahblah 地讲了大半个小时，用尽量通俗易懂的语言给老婆描述了数据库最初是怎么起源的；怎么去实现最基本的存储；有了存储，怎么去实现基本的数据读取；有了读取怎么去实现基本的数据操作，等等。听完，小葡萄真的是突然有种对我肃然起敬地感觉（极有可能是我自己的一厢情愿）。也正是小葡萄的支持，我决定，要真正去做这件想了很久却从未开始的事情。就像她说的，与其过多地去 get ready but do nothing, 还不如去实践一个不怎么 ready 的事！

啥背景呀，就敢写数据库内核

说真的，我自己也信心不足呢。说说背景吧 (偶尔咱也知乎体一下)：咳咳，谢邀。本人上海交通大学软件学院本科毕业，University of California, Davis 计算机博士毕业。现在在脸书做一个老年程序员。自己并不算一个数据库的科班出身，博士学的也不是数据库专业。一个很偶然的机会，我得到了一份数据库公司 Greenplum(Pivotal) 的实习的机会，又阴差阳错地毕业后正式加入了 Query Processing 组。在 Pivotal 的两年，非常有幸地参与了 Orca Query Optimizer (已在 Apache 开源) 的开发。在这期间也混了几篇 VLDB，SIGMOD 的 papaer。正是这份工作让我开始对内核有所了解。再后来原 Pivotal 的 director 离开开了个做数据库虚拟化的初创公司就把我一起拉去了。这个初创公司做的也非常有趣，database virtualization：旨在不用改变任何 application code 的前提下（包括不用换 JDBC, 或者 ODBC driver），就让 application code 可以直接运行在另一个数据库上（举个例子，Teradata BTEQ script 可以直接通过我们的中间件，运行在 Pivotal Greenplumn Database 上），当时我们用的最多的简介就是 VMWare in terms of databases。这份工作让我更细致地了解了不同数据库原生接口的不同以及如何 rewrite 不同的 SQL dialect 来使它们之间互相兼容，我觉得也算变相的 query optimization 吧。总的来说，自己对各个部件都有所了解，但知识点比较分散，不够系统，也希望在写 blog 的过程中去学习和完善知识储备。

这个系列会分为哪几个模块？有没有大纲

真心觉得自己还不够格去系统地讲解数据库的各个模块。所以我才把这个系列的名称定义为杂谈。咱们就暂不列什么提纲了，但我会把最核心的部件包括存储，SQL 语言，数据优化器和执行器都 cover 了。然后我们也能够自由发挥，分享一些我对 NoSQL 以及 NewSQL 的理解。在这个过程中，我也会去查最新的资料，在写的同时也能更好地去巩固和订正知识。

阅读这个系列会有啥收获?

我希望能够深入浅出地去讲解数据库是一个什么样的系统，以及为什么它最后会演化成这样一个系统，为什么我们都用 SQL 来操作数据，而不是 AQL 或 BQL. 希望读者阅读后，对数据库的理解不再单单只是知道简单的 table, row 等的基本概念或者单单会写些 join, select 的 SQL 语句。而是能从源头真正做到知其所以然。希望能从对数据库系统的认知来进一步提高对 general 系统设计的认知。

虽然没有大纲，但是这篇的题目想好了：一小时实现一个基本数据库。

一小时实现一个基本数据库

今天我们摒弃直接介绍数据库内核各个模块的思路，而是从应用开发者的角度出发，来看实现一个数据库需要哪些基本功能，然后把这些功能细分成最小的模块再手把手一起实现，帮你揭开数据库内核的神秘面纱。希望能够减轻你对学习数据库内核的压力。我们也可以从中体会到，九层之台，起于累土。所有复杂的系统，都是通过模块化的架构和设计，以及工程阶段的精益求精，一步一步累计起来。

对与应用开发者而言，一个数据库需要哪些必要的功能呢？我觉得，下面这些是必不可少的：

1）创建数据库和数据表：create database，schema, table 等

2）存储数据：insert /update 数据，或者从其他方式导入数据 (比如 csv 文件)

3）读取查询数据：通过 SQL 语句，对数据进行读取和查询，比如 sort，aggregate，filter 等

根据这三个功能，再回看标题，你可能产生疑问，一个小时就能实现上面这些功能，不会是标题党吧。我承认，有一点小小得标题党了。因为要和数据库交互，最必要的条件是有个客户端程序可以接受用户送来的指令。但要实现一个功能齐全的 Parser 可得花不少精力。既然是内核杂谈，请允许我偷个懒，假设 Parser 已经有实现，从而把精力都关注在数据库系统内部的实现。抛开 Parser，又该从哪开始呢？我的思路是跟着数据的流向，自下而上，依次从存储数据，读取数据和查询数据来看。

创建和存储数据

当用户创建一个新的数据库，并导入数据时，数据库系统就需要存储这些数据。说到存储，第一个想法就是文件系统（其实说到底数据库系统就是一个特殊的文件系统，区别与普通文件系统提供的的读写文件的接口，数据库只是提供了一个面向数据的接口：存储，读取和查询；整个系统为这些接口提供服务)。以下图 student 表作为示例，要怎么把这张表存在文件中呢？

Student 表

最显而易见的就是用 Comma-separated value(CSV) 格式存:

1,“Xiaoputao”,3,“Hiking”

2,“Zgu”,3,“Running”

3,“Xiaopang”,2,“Walking”

读取 CSV 文件的逻辑也非常简单: 一行一行读取数据，然后根据 ";" 把每个数据段取出。

除了 CSV 存储，另一种常见的方式就是 json 格式:

[ {"id":1, "name":"Xiaoputao", "class":3, "hobby":"running}, ... ]

聊聊 CSV 和 JSON 存储的优缺点。两者都属于文本存储，优点一在于易于人类理解。另一个优点就是直接兼容其他支持 CSV 和 JSON 的数据库。缺点也很明显，存储效率不高，读取效率也会随之降低。另一个问题在于，上述例子中存储的内容只有值，没有 type 和 size(metadata)，这些信息在后续操作如校验中是很重要的。当然，我们可以把 metadata 加入到存储中，比如，把 json 的每个 val 变成一个 obj:{“colName”:“id”,“colType”:“int”,“colSize”:4,“colVal”:1}。专业数据库肯定不会选择用 CSV 或 JSON 作为默认存储，但几乎都支持 CSV 和 JSON 数据作为 external table。如果要追求更高的性能，我们可以选择更高效的编码方式把数据以字节流的形式存储在文件中；只要数据库系统自身能够读取这些数据即可。咱们既然时间有限，当然是一切从简，就选择 CSV 或者 JSON 的文件格式来存储我们的数据。

只要有一个文本编辑器，能够创建和编辑 CSV 或者 JSON 文件。这其实这已经完成了创建数据表，输入，修改以及存储数据的功能。

读取数据

基于上述用 CSV 或 JSON 的存储，读取数据非常简单 (允许我们调用第三方支持 CSV 或者 JSON 的 API)。重点在于读取完存放在怎样一个数据结构中方便后续对数据进一步的查询操作。根据数据的特性，结果集 (RowSet) 是由一序列的行数据 (Row) 组成，每一行又由多个单元 (Cell) 组成。我们试着根据这个概念设计下面这些类：

Cell, Row, RowSet Class

简单梳理下，每个 Cell 存 type，size，和 value；Row 存一整行 cell；RowSet 存一序列的 Row。具体在实现中还有很多细节需要注意，如 typecheck, 确保每行列数相同，等等，这里也一并从简略过。定义了存储方式和数据结构，具体数据读取代码如下:

读取

csvToRowSet 和 jsonToRowSet 的实现只需要借助第三方 CSV 和 JSON 的类库就能实现，就不赘述代码了。

这一节里，我们定义了 Cell, Row, RowSet 的数据结构来存放从文件 (CSV 或 JSON) 中读取的数据，并给出了示例代码。

执行查询

有了存储和读取，已经可以把数据从文件中读取到内存，接下来就要支持用户的查询语句了。实现查询就是去实现 SQL 语句中的各个功能模块，比如排序 (order by), 聚合 (group by)，多表联合 (join) 等等。执行器会对每个功能模块进行实现，甚至针对不同的数据分布，会有多种方式的实现来提高读取速度。现在，我们一起来讨论一些常用的语言功能。

全表读取 (SELECT *)

其实，定义了 RowSet 的数据结构和实现了读取文件的接口，我们的数据库就已经支持全表读取的 SQL 语句，示例如下：

SELECT * FROM student;

‍分页语句 (LIMIT)

一下子就能想到的分页语句，用来限制输出的数据行数：

Limit Operator

一行代码，不解释了。抬走！

关系映射语句 (PROJECTION)

关系映射的本质是对于输入的 RowSet 的每一行 (row), 通过各种标量计算，输出一个新的数据行，再由这些行组成新的 RowSet。见下图示例：

SELECT id + 5, LEN(name) FROM student;

‍对从 student 表读取的每一行数据，输出一个新的数据行包含 id + 5 和 LEN(name) 的 cells。

Projection 可以非常复杂，但有一条准则就是它不改变原有 RowSet 的基数 (cardinality), 即新 RowSet 的行数和原来的相同。因此，无论映射逻辑多复杂，输入一个 Row，输出一个 Row。再复杂的计算，也是一比一步迭代产生。比如上述示例可以分解成下面这些操作来完成：对于每一行 input row, id 值加 5，对 name 取 length，最后去掉 class 和 hobby 两列。归根结底就是将复杂的运算拆分成原子操作然后一步一步地顺序执行。我们可以定义如下两个基本 operator：RowComputeOperator 根据定义的 computeCellVal 对 input row 计算一个新 cell，并把这个 cell 加到原 row 的末尾。SelectionOperator 根据给定的 indexes，生成一个仅包含指定 index 的新 row。Pseudo code 如下：

RowComputeOperator and SelectionOperator

RowComputeOperator 里面有需要定义 computeCellVal，输入是一个 row, 输出一个新的 cell。具体实现则根据具体语义来定。定义一个 computeCellVal 需要 2 个参数：1）运算作用在哪些 cell 上，假设限制只能作用在 1 个或 2 个 cell 上 (2 个以上可以用多个 Operator 嵌套)；2）提供具体计算的操作，比如常见单元操作如 len(), ceiling(), abs() 或者常见的二元操作如±*/ 等等。

有了这两个基本 operator, 实现示例中的 projection，我们定义 3 个 operator 即可：1）compute a new cell using “(id + 5)” 2) compute a new cell using “len(name)” 3) 用 SelectionOperator 选择最后两个新生成的 cell。

实现整个 projection 的 operator 的 pseudo code 如下：

Projection Operator

条件选择语句 (WHERE)

有了 Projection，我们就可以实现下面的条件选择语句 (WHERE) 了：

SELECT class_room, COUNT(*) FROM student;

实现想法很简单，首先用 Projection operator 计算出 filter condition 的值 (bool)，然后 filter by 这个 cell 即可。

Filter Operator

排序语句 (ORDER BY)

这里，我给一个非常低效但很容易理解的实现：创建一个 hashmap 来存 <cell, id>，然后对要 sort 的 cell 排序，根据 cell 顺序取出原 row 组成新的 rowSet 输出：

Sort Operator

有读者会问，如果排序语句是一个 expression 而不是单个 column 怎么办？比如下面的示例:

SELECT * FROM student ORDER BY id + 5 ASEC;

还记得我们前面实现的 projection 吗？这里把 (id + 5) 作为一个新的 projection 加入到 Row 中即可。

一起实现了 4 个 Operator，看看有没有什么规律可循？所有定义的操作都是基于一个原则：输入一个 RowSet，然后输出一个 RowSet。并且，是一层一层循序渐进的迭代。对于数据的查询操作，是从最初读取表中的原始数据开始，根据给定的 Operator 序列对数据逐一进行操作；这一个 Operator 的输出就是下一个 operator 的输入。也就是说，给定一个 SQL 查询语句，我们生成一序列 Operator 的 tree，再依次执行，就能得到最终结果。现在来一起优化下代码，把 Operator 的接口抽象出来，然后把刚才实现的 operator 全当成子类来实现。代码如下：

Unary Operator

有读者会有疑问，基类为什么叫 UnaryOperator 呢？先卖个关子。有了基类，我们可以根据 SQL 的语法功能实现相应的 Operator。

聚合操作 (AGGREGATION)

接着一起来实现聚合操作。Aggregation 分为两大类，scalar-agg 和 multi-agg。scalar-agg 就是简单的 sum, avg, min, max 等的数据聚合操作，最终返回一个数据行的结果集，实现代码如下：

Scalar-agg

每个 AggOp 接受一序列的 cells，然后输出聚合结果的 cell。常见的 AggOp 如 sum, max，min 实现都很简单，这边就不赘述了。

multi-agg 对应 SQL 中的 GROUP By，如下图示例：

SELECT class_room, COUNT(*) FROM student

比 scalar-agg 复杂的地方就是先要把有相同值的 group by columns(示例中为 class_rom) 的 row 合并起来，然后对合并后的 rows 做 Scala-agg 即可。代码我就不贴啦，当留个小作业给大家。

SQL Operator Tree

有了实现基本语义的 Operator，要实现一个完整的查询语句，我们要做的就是把 operator 一层一层的累加起来，形成一个 Operator tree，然后根据这个 operator tree, 依次执行每一个 operator 即可。比如下面这个查询语句：

select class, sum(id + len(name)) as c
from (
    select * from student where hobby = 'hiking' limit 10
)
group by class;

我们只要建立如下的 Operator tree：

sql operator tree

有没有觉得挺神奇的！即使再复杂的查询 SQL 都能这样用基本的 operator 像搭乐高一样搭建起来。

小结

至此，我们简单的数据库也实现得差不多啦。我看了下自己写的 pseudo code 仅仅 200 多行，一个小时写完也不算条件太苛刻。虽然数据结构冗余，算法低效，但是麻雀虽小，五脏俱全！

来解释前面卖的关子，为什么基类定义为 UnaryOperator？因为我们还有 BinaryOperator。二元的操作是做什么的呢？答案就是为了表与表的联合 (join)。有了 Binary Operator，Operator 的叠加就真正变成了一颗树 (二叉树)，这也是为什么前文我们称之为 operator tree。本文就先不详述如何实现 Join Operator 了，以后会有专门的章节来覆盖。再讲下去，肯定超过一个小时，读者就更觉得我标题党了。

最后给大家总结一下：

1）一个 SQL 的查询语句，即便逻辑再复杂，也可以拆分成一个一个原子 operator 的叠加

2）把这些 operator 组建成一个 operator tree，然后自底向上地依次执行，就能得到最终的查询结果

3）你可能觉得真正的数据库和我们在这捣鼓的很不一样。如果有条件，可以在 Mysql 或者 Postgres 中运行 "EXPLAIN SQL_STMT" 来打印它们生成的 operator tree，你会发现和我们生成的树挺相似的

4）相信大家都非常熟悉用 SQL 做各种数据查询，但可能从没去想过底层是怎样实现的。希望这篇博客对你有所帮助。正所谓，知其然，知其所以然！

下一篇，咱们深入聊聊存储!