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

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

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

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

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

创建和存储数据

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

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, 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即可：

  • compute a new cell using “(id + 5)”
  • compute a new cell using “len(name)”
  • 用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像搭乐高一样搭建起来。

最近更新于0001-01-01