实现一个基本功能的数据库

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

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

1）创建数据库和数据表：create database，schema, table 等 2）存储数据：insert /update 数据，或者从其他方式导入数据(比如 csv 文件) 3）读取查询数据：通过 SQL 语句，对数据进行读取和查询，比如 sort，aggregate，filter 等

创建和存储数据

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

读取 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 的 API)。重点在于读取完存放在怎样一个数据结构中方便后续对数据进一步的查询操作。根据数据的特性，结果集(RowSet)是由一序列的行数据(Row)组成，每一行又由多个单元(Cell)组成。我们试着根据这个概念设计下面这些类：

简单梳理下，每个 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)

关系映射语句(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 里面有需要定义 computeCellVal，输入是一个 row,输出一个新的 cell。具体实现则根据具体语义来定。定义一个 computeCellVal 需要 2 个参数：

1）运算作用在哪些 cell 上，假设限制只能作用在 1 个或 2 个 cell 上(2 个以上可以用多个 Operator 嵌套)； 2）提供具体计算的操作，比如常见单元操作如 len(), ceiling(), abs()或者常见的二元操作如 ±*/等等。

有了这两个基本 operator, 实现示例中的 projection，我们定义 3 个 operator 即可：

• compute a new cell using “(id + 5)”
• compute a new cell using “len(name)”
• 用 SelectionOperator 选择最后两个新生成的 cell。

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

条件选择语句(WHERE)

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

SELECT * FROM student WHERE class = 3;

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

排序语句(ORDER BY)

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

有读者会问，如果排序语句是一个 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 全当成子类来实现。代码如下：

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

聚合操作(AGGREGATION)

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

每个 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 像搭乐高一样搭建起来。