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

数据库内核博大精深，很多子系统的设计初看不知所云，但是细读就会发现其已经做到了极致。但是市面上很少有类似的资源或者课程把数据库内容的精髓讲解出来，因此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 * FROM student WHERE class = 3;

实现想法很简单，首先用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做各种数据查询，但可能从没去想过底层是怎样实现的。希望这篇博客对你有所帮助。正所谓，知其然，知其所以然！

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

作者介绍：

顾仲贤，现任Facebook Tech Lead，专注于数据库，分布式系统，数据密集型应用后端架构与开发。拥有多年分布式数据库内核开发经验，发表数十篇数据库顶级期刊并申请获得多项专利，对搜索，即时通讯系统有深刻理解，爱设计爱架构，持续跟进互联网前沿技术。

2008年毕业于上海交大软件学院，2012年，获得美国加州大学戴维斯计算机硕士，博士学位；2013-2014年任Pivotal数据库核心研发团队资深工程师，开发开源数据库优化器Orca；2016年作为初创员工加入Datometry，任首席工程师，负责全球首家数据库虚拟化平台开发；2017年至今就职于Facebook任Tech Lead，领导重构搜索相关后端服务及数据管道， 管理即时通讯软件WhatsApp数据平台负责数据收集，整理，并提供后续应用。