# 参赛经历

感谢 Luv 拉我过来参加这个比赛。我和他以及一位他的学弟组队参赛，我们的队伍名字叫做 神雕侠侣 (Luv 起的名，不知道是不是因为拉我来之前它们队伍只有两个人的原因)。拉我来的时候距离初赛结束还有 2 周时间，几位队友都花了不少时间，我中途掉线了 4 天去完成密码学实验的手搓大数库去了，感觉非常可惜，如果我多在线这 4 天，虽然还是进不了决赛，或许还能摸一个省奖走。

当然这个比赛为什么我们那么难进决赛，一个根本原因还是赛题都是承接往年的题，平时也可以通过 “训练营” 做题，最终进入决赛的队伍大部分都 AK 了，想必都是有以前的基础，而我们则没法在这么短时间内，又要应付课程和作业又要做出这么多题。我相信我们第二年再参赛应该能拿捏并弥补遗憾的。

有几道题我还是基本做出来的，比如 null、子查询、复杂子查询的实现，虽然 null 我的实现并不正确，但这些都还遇到了各种问题没来得及 debug 完。实际上我的排序实现也不正确，我还是用了内排序做的，在真正的大数据排序下估计是要爆内存的，我们就遇到过忘了删掉 LOG_DEBUG 提交然后爆内存。（但是测评用的数据似乎并不是特别多）

分工协作做不同题目，虽然个人完成的题目提交评测没有问题，但是 merge 之后经常遇到不兼容的问题，需要不断的排查。我印象最深的是，我实现的子查询和 Luv 实现的 update-mvcc 不兼容，折磨了好久。

尽管如此，我非常享受这一次比赛，我对数据库的实现、运行有了深刻的理解。我在专业课程上所学的《数据库系统原理》是偏理论的，而且说实话讲的并没有多好 ~~(考试和给分还一坨真的是烂中烂)~~ 。真正上手去做一个数据库，才是我眼中更加理想的学习过程。Mini Oceanbase 在这一点上非常适合学习使用，它是为数据库初学者设计的，让学习者体验从底层开始的完整实现，麻雀虽小五脏俱全，没有工业生产级别数据库那么庞大复杂以及高性能，但是有一个真实数据库完整且规范的实现。

# MiniOB 架构

MiniOB 用 C++ 实现，采用面向对象风格。下图中，左侧为不同阶段处理器对象，右侧为该阶段下所处理的结果对象。

	┌──────────────────┐ ┌──────────────────┐
	│ SQL │ ---> │ String │
	└────────┬─────────┘ └──────────────────┘
	│
	┌────────▼─────────┐ ┌──────────────────┐
	│ Parser │ ---> │ ParsedSqlNode │
	└────────┬─────────┘ └──────────────────┘
	│
	┌────────▼─────────┐ ┌──────────────────┐
	│ Resolver │ ---> │ Statement │
	└────────┬─────────┘ └──────────────────┘
	│
	┌────────▼─────────┐ ┌──────────────────┐
	│ Transformer │ ---> │ LogicalOperator │
	└────────┬─────────┘ │ PhysicalOperator │
	│ │ or │
	┌────────▼─────────┐ │ CommandExecutor │
	│ Optimizer │ ---> │ │
	└────────┬─────────┘ └──────────────────┘
	│
	┌────────▼─────────┐ ┌──────────────────┐
	│ Executor │ ---> │ SqlResult │
	└──────────────────┘ └──────────────────┘

# SQL 解析

任何输入的 SQL 语句都是一条字符串，解析的任务是将这样一条机器无法理解的字符串最终转化为机器可理解的数据结构形式的节点 ParsedNode 。解析的过程分为词法解析和语法解析：

词法解析：负责匹配不同的关键词，例如 SELECT , WHERE ...... 这样的词，以及剩余其他的字符串、数值或日期字面量。这些都被匹配为对应的 token 供语法解析使用
语法解析：有了匹配出来的各种 token，就可以定义这些 token 如何排列组合能够得到一条 SQL 语句，并构造出一个 ParsedNode 作为返回结果，这个 ParsedNode 数据结构应当包含这个查询所需的所有数据和条件

特别注意的是，语法解析涉及大量经典的递归语法，需要准确定义递归和递归边界。例如子查询、 JOIN 连接、 WHERE 后的条件等等。

# 词法分析

MiniOB 使用词法分析工具 flex

# 语法分析

MiniOB 使用语法分析工具 bison

语法解析时，会定义一些不同类型的字面量，包括数值、日期、字符串，可以说字符串以外的字面量都是正则表达式定义的特殊的字符串。

同时还有一种类型 Attribute 也就是表的属性，表的属性定义为两种：带表名的和不带表名的。

在语法解析的时候，我们还定义一种特殊的结构： Expression 或者说表达式。它就是 SELECT 后以及 WHERE 后会出现的，字面量以及 Attribute 参与的的运算表达式。

# Statement

缩写为 stmt ，接下来都这么简称它。

在得到 ParsedNode 之后，还需要进一步将其转化为 Stmt ，这个过程被称为 Resolve 阶段。通常在 Resolve 阶段会校验 SQL 语法树的合法性，比如查询的表是否存在，运算类型是否正确。

实际上， ParsedNode 已经是树的结构了，但不一定是合法的树，Resolve 阶段得到的 Stmt 则一定是合法的树结构。

同时，这一步还会进行绑定操作，从 FROM 后面得到一系列表，将每一个语句中出现的 Attribute 尝试在这些表中绑定，当然如果绑定失败，那就是查询语句不合法，包括：

FROM 后有多个表有相同名字的属性，这个名字的属性 Attribute 出现了但没有指定表名，无法确定该绑定哪一个
属性 Attribute 不在任何一个 FROM 后的表中

绑定的 Attribute 不仅出现在 SELECT 后面，还会出现在任何 Expression 中，也就是出现在任何 SELECT 后以及 WHERE 后会出现的 Expression 中。

# 执行模型

在理解 Logical Operator 和 Physical Operator 的工作过程之前，必须先了解数据库实现的经典模型：火山模型以及它的并行向量化版本。

# 火山模型

构建一颗树的结构，每一个节点被称为 Operator ，采用面向对象的设计，这些 Operator 都实现如下几个方法：

open() ，相当于初始化，只在刚开始执行一次
next() ，由上层反复调用，直到执行失败，表示不再有更多 tuple
tuple() ，每次 next() 执行成功，则也执行这个方法，将得到一个 tuple
close() ，最后结束，从上到下依次关闭，保证所有叶子结点关闭对相应数据的访问

注意这些方法都是迭代执行的，上一层调用下一层的方法，下一层将继续调用在下一层同样的方法。

这里说的当然无论是逻辑还是物理的 Operator 都是抽象类，在底下将实现不同的继承类，作为执行计划树上的不同节点。

	┌──Volcano iteration model─┐
	│ ┌───────────┐ │
	│ │ │ │
	│ │ operator1 │ │
	│ │ │ │
	│ └──┬────▲───┘ │
	│ next()│ │ │
	│ tuple()│ │ tuple │
	│ ┌──▼────┴───┐ │
	│ │ │ │
	│ │ operator2 │ │
	│ │ │ │
	│ └──┬────▲───┘ │
	│ next()│ │ │
	│ tuple()│ │ tuple │
	│ ┌──▼────┴───┐ │
	│ │ │ │
	│ │ operator3 │ │
	│ │ │ │
	│ └───────────┘ │
	└──────────────────────────┘

# 向量化执行模型

和火山模型执行过程完全一致，但是每一次是以 chunk 或者说 batch 为单位向量化执行，有点像现代处理器的向量指令，可以并行化加速。由于我在比赛中没有实现这个模型，并没有特别了解。

	┌─────── Vectorization model ──────┐
	│ ┌───────────┐ │
	│ │ │ │
	│ │ operator1 │ │
	│ │ │ │
	│ └─┬─────▲───┘ │
	│ next()│ │ │
	│next_chunk()│ │ chunk/batch │
	│ ┌─▼─────┴───┐ │
	│ │ │ │
	│ │ operator2 │ │
	│ │ │ │
	│ └─┬─────▲───┘ │
	│ next()│ │ │
	│next_chunk()│ │ chunk/batch │
	│ ┌─▼─────┴───┐ │
	│ │ │ │
	│ │ operator3 │ │
	│ │ │ │
	│ └───────────┘ │
	└──────────────────────────────────┘

# Logical Operator

这个过程也就是生成逻辑执行计划，就是将 Stmt 的树组装为 LogicalOperator 的树。在面向对象的设计中，这一步由 Logical Plan Generator 完成。

LogicalOperator 的树已经和 PhysicalOperator 在结构上基本一致了，只是它并没有真的实现 open() ， next() ， tuple() 和 close() 。

一颗 SQL 的 Operator 树具有如下通用泛化结构：

	Project/Insert/Delete/Update
	\|
	[OrderBy]
	\|
	[GroupBy]
	\|
	Predict
	\|
	Join
	/ \
	TableScan Join
	/ \
	TableScan ......

其中有一些是可选的，例如 GroupBy。另外，Join 的执行可以看出其实是迭代进行的，每一次都是两个表之间进行。而 TableScan 的实现也有向量化版本，而且这个 Operator 在逻辑计划和物理计划中名字不太一样，实际上它在逻辑计划中还可以叫做 TableGet Operator，这样的叶子节点是整个执行过程中真正从数据库的 record 获取 tuple 的地方。

在构建完这样一颗树之后，将会开始优化。分为两种优化：

先对 Expression 优化，将不依赖于 Attribute 的表达式直接计算出来
然后是 Operator 树的优化，但是 MiniOB 中并没有实现这一方面的优化，本文不再考虑。实际上这种优化就是尽可能将 Predict 拆开、放在 Join 的子孙节点，节省 Join 开销。

第一种优化也叫做 Rewrite，在面向对象的设计中由 Rewriter 完成。我们对每一种 Expression 事先定义好一些列优化规则，叫做 Simplification Rule。于是优化过程就是如下伪代码：

	auto rewrite = [] (oper, &dirty) {
	for (oper : 当前 Operator 的子节点) {
	for (expr : oper 的所有表达式) {
	if (expr 是可优化表达式) {
	for (rule : 这个表达式类型的所有 Simplification Rule) {
	尝试应用规则
	if (应用规则成功简化表达式) {
	dirty = true;
	}
	}
	}
	}
	rewrite(oper, dirty);
	}
	}

	bool dirty = false;
	do {
	rewrite(根节点, dirty);
	} while ( dirty );

# Physical Operator

最后，优化完的逻辑执行计划被转化为物理执行计划，在面向对象的设计中，这一步由 Physical Plan Generator 完成。优化完的 Logical Operator 树直接每个节点对应转化就可以。

这里着重的关注点就是不同 Operator 的 open() ， next() ， tuple() 和 close() 四个方法了，它们决定了每个 Operator 节点扮演什么角色以及如何工作。

# Predicate

起到条件判断或者说过滤作用的 Predict Operator，它的 next() 和 tuple() 就会是如下的逻辑：

	void next () {
	do {
	子节点.next();
	当前 tuple = 子节点.tuple();
	} while (当前 tuple 不满足条件);
	}

	Tuple tuple () {
	return 子节点.tuple();
	}

# Groupby

GroupBy 有两种情况的实现被划分为了物理执行计划中的两种节点：

ScalarGroupByPhysicalOperator ，聚合目标只有一个，或者说 SELECT 后面只有一个表达式。它的实现方式相对简单，逐条处理数据进行分组和聚合操作。
HashGroupByPhysicalOperator ，聚合目标有多个，或者说 SELECT 后面有多个表达式。基于哈希表来实现不同分组的聚合。

执行聚合操作就和上面 Predict Operator 的原理很像，只不过他是在 open() 的时候就迭代完了所有子孙节点的 tuple，在迭代过程不断更新每一个 group 的聚合结果 (当然对于 Scalar 只有一个 group)。在面向对象的程序实现过程，聚合的过程由这样一个类来实现：

	class Aggregator
	{
	public:
	virtual ~Aggregator() = default;

	virtual RC accumulate(const Value &value) = 0;
	virtual RC evaluate(Value &result) = 0;

	protected:
	Value value_;
	};

open() 中每次迭代都执行一次 accumulate() ，当在 next() 和 tuple() 迭代阶段则每次 next() 成功后，执行一次 evaluate 返回聚合结果。

和 Operator 一样，这里的 Aggregator 也是抽象类，依据五种聚合函数得到五种继承类：

AvgAggregator
CountAggregator
MinAggregator
MaxAggregator
SumAggregator

# Orderby

Orderby 的情况和先前两种都不一样，因为 Predicate 和 Groupby 实际上都仅需一个一个扫描 tuple，不需要一次性全读入内存。但是排序是需要考虑读多少进入内存的，也就是所谓的 外排序 的情况。

如果还是内排序那一套来实现，就和聚合类似，在 open() 阶段就完成排序即可，排序结果一个一个返回给上一层 Operator。但是正如我在本文开头讲的那样，终究是有爆内存的问题的。

那么该如何实现外排序呢？这个问题我当时没考虑到，而且当时存储模块主要由队友 Luv 负责，我也尚不清楚如何利用内存、存储实现外排序。

# 子查询

子查询的实现，需要在 语法解析 阶段就建立 ParsedNode 的迭代的树结构。然后在此后的 Stmt ， LogicalOperator ， PhysicalOperator 阶段都传递并保持这样的树结构。只有这样才能实现递归执行的效果。

这个过程还牵扯到了一些比较复杂的语法判断问题，尤其是 Attribute 的绑定，给 Resolve 阶段带来了不小的麻烦。

而在物理执行计划，和上面两种情况仍然一样，注意子查询作为 WHERE 后的一种条件判断，需要将子查询的 Operator 子树放在 Predicate 节点的子节点。在 open() 阶段完成整个子查询，上层的 Predicate 每次通过 next() 和 tuple() 拿到一个 tuple。

# Reference

Documentation of MiniOB

数据库