Summary

[luooofan]

base on: 6d7e170

比赛开始之前

找一些文档看，还有官方的赛前培训

• oceanbase/miniob
• 数据库管理系统实现基础讲义 | lectures-on-dbms-implementation
• miniob 源码解析文档
• 从0到1数据库内核实战教程-数据库社区活动-OceanBase社区-分布式数据库

可以做去年的题目，我们开始之前把2021年的题目做了80分

• OceanBase 训练营

初赛

准备

首先要为后续的开发、测试、版本管理构建一些基础模块，比如说编译安装以及测试的 shell 脚本、代码格式化（clang-format）、代码静态检查（clang-tidy）、Gitee 和 Github 的 Issue 和 PR 模板、Github 的 workflow 等等

涉及到的几个提交如下：

• 37ad447
• 6d96d2f
• 6ffbfee

clang-format/tidy

• e96b65c
• 94777ca

clang-format 和 clang-tidy 模块源自bustub/build_support at master · cmu-db/bustub，我们在此基础上禁用了一些 check，并且限制了被检查的目录

这两个工具除了规范编程以外，也有很实际的好处：

• clang-format 有助于合并的时候减少因为格式导致的冲突
• clang-tidy 有助于发现一些隐藏的 bug

使用 clang 编译

e35aeb5 （这个其实没啥用）

版本管理

主要就三个原则：

• 新功能新分支
• 合并新功能要提 PR，做 review
• 提 PR 之前要先 rebase 到 main 分支，并提交官网测试

rebase 主要是为了让提交历史更清晰，尽可能地线性化

这是我们 main 分支最后的一部分提交记录

赛题分析

在公布了今年的赛题后，首先有80分的题目我们已经做了：basic、select-meta、drop-table、update、date、select-tables、insert、order-by，虽然有些需要做修改，还有一个改动略大，但起码大体上没啥问题。对于这80分的题目我们基本上是把对应的提交直接 rebase 到了今年的开发分支上，然后做修改提测

然后我们发现对于 update、insert、show-index、multi-index、unique、clog 这几个赛题是一条线上的，这条线交给成林 @Zhang-X0 来做，我只了解一部分，一起调了调 bug，这几个赛题后面就不说了

剩下的由我和琨琨 @yang-jun-kun 做，这部分赛题思路我都熟，以下都会提到

具体的实现可以找对应的 PR 看

赛题思路

drop-table

先看 create table 和 create index 的流程，在 drop table 的时候要处理好各种资源

有一个要注意的地方是 disk buffer pool 的析构，会在 close file 的时候把自己释放掉，但是 buffer pool manager 中还有信息未删除，会导致问题

typecast

先把类型转换的函数单独实现，存一个函数指针的二维数组 cast_to

• 类型转换的时候会新分配内存空间存储转换后的结果，统一用 malloc 分配空间，返回 void*，这样外部调用完要释放空间的时候直接用 free 释放即可
• 对于不支持的类型转换写一个 not_support 函数，返回空指针

然后考虑要在哪里用这个模块就行

另外，在 do_predicate 的时候比较的规则是：

• date 类型不考虑
• null 类型比较结果全为false
• 涉及到浮点数，都转成浮点数比较
• 整数和字符串，都转成浮点数比较

总结来说就是不考虑 date，先处理 null，其他情况都先转成 float

like

• 用 C++ regex 库来实现
• 默认是 ignore case
• 记得要改词法文件中对字符串的正则识别规则，我们最后把单引号和双引号分开来了

select-tables && join-tables

Tuple 是算子执行阶段中非常好的一层抽象：

miniob-2022/src/observer/sql/expr/tuple.h

Lines 75 to 96 in 6d7e170

	class Tuple {
	public:
	Tuple() = default;
	virtual ~Tuple() = default;
	virtual int cell_num() const = 0;
	virtual RC cell_at(int index, TupleCell &cell) const = 0;
	virtual RC find_cell(const Field &field, TupleCell &cell) const = 0;
	virtual RC cell_spec_at(int index, const TupleCellSpec *&spec) const = 0;
	// push back records of the tuple to arg:record
	virtual void get_record(CompoundRecord &record) const = 0;
	// this func will set all records
	// invoke this func will erase begin arg:record
	virtual void set_record(CompoundRecord &record) = 0;
	// this will not set all records
	// invoke this func will erase end arg:record
	virtual void set_right_record(CompoundRecord &record) = 0;
	};

利用好 Tuple 这个抽象，构造一个 CompoundTuple（一开始叫 JoinedTuple）

最初的实现：

• 存一个 RowTuple 的数组（一开始考虑的是 JoinOperator 的孩子只能是 JoinOperator 或者是 TableScanOperator）
• 不考虑缓存右表数据

后来因为在实现 OrderBy 的时候必须缓存表数据，所以把这里也改成了缓存右表数据：

• 用 CompoundRecord 表示一个 Record 的数组
• 做深拷贝

并且考虑到 JoinOperator 的孩子可能是其他类型的算子（尤其是考虑到 ProjectOperator 这种特殊类型，必须用 ProjectTuple 才能得到正确的信息，虽然今年的赛题里没有这种情况）：

• 把 RowTuple 的数组改成了二叉树的结构，左右各一个 Tuple*

实现 InnerJoinOn 的时候，一开始偷懒做的方案是把 on filter 作为 where filter，等所有的表笛卡尔连接后再统一做 filter，结果超时了

最后的方案是在构造 JoinOperator 的时候尽可能地把 filter 推下去，给 JoinOperator 集成了过滤功能

最终，JoinOperator 的 next 流程为：

• 如果是第一次调用 next，则预取整张右表并缓存（这里对 Record 做了拷贝）
• 如果当前已过滤的右表还没遍历完，则设置 record，返回 SUCCESS
• 如果遍历完了，左表取下一行，对缓存的整张右表做过滤，得到已过滤的右表，然后递归调用 next
• 如果左表已经取完了，返回 RECORD_EOF

text

发现了官方的彩蛋（或者说卡了一个 bug）
直接看 commit msg: 8abfe5a

分隔

到这里为止，第一页的基本都做完了，分析后面的赛题的时候发现存在一个 null 测例，其前后的一些测例都要把 null 考虑进去

另外还发现 aggr-func 赛题排在很前面，group-by 赛题排在很后面，但是我觉得这两个应该一起做，仔细考虑之后，重排了一下做题顺序，具体安排见 #14

order-by

• 需要缓存整张表的数据，用一个 CompoundRecord 的数组来存
• 获得表的数据后要排序，写一个 lambda compactor，用 std::sort 排序得到一个排好序的索引数组，next 的时候用这个索引数组来找数据返回

expression

在语法分析阶段根据优先级构造成树的形式，resolve 阶段保留树的结构，执行阶段后序遍历执行

在语法阶段增加了 UnaryExpr、BinaryExpr、Expr，在 resolve 阶段给 Expression 扩充了 BinaryExpression，具体的运算则是对 TupleCell 做扩展

function

对表达式的扩充，语法阶段增加了 FuncExpr，对应到 resolve 后的 FuncExpression

group-by && aggrfunc

重排做题顺序主要是为了把这两一起实现 #14

这块新增了 GroupByUnit GroupByStmt GroupByOperator GroupByTuple，以及 AggrFuncExpr(esssion)

实现的关键在于 GroupByTuple，也是利用了 Tuple 这个抽象

• 存储 GroupBy 算子的子算子的 tuple，每次从这里取数据然后运算
• 存储字段表达式和聚集函数表达式，实际上相当于是把投影列全存起来了（但并没有用 GroupByOper 取代 ProjectOper，只要把 GroupByTuple 的 find_cell 函数实现好就行）
• 存储字段结果，这个与字段表达式是一一对应的
• 存储聚集函数结果、组内计数（count 和 avg 用）、组内 all null 标志，这些与聚集函数表达式是一一对应的
• 提供 do aggregate first 函数，用于每个 group 内的第一行数据，初始化聚集函数的运算结果，以及填充该 group 内的字段结果
• 提供 do aggregate 函数，用于每个 group 内的非第一行数据进行聚集运算
• 提供 do aggregate done 函数，用于读到了新 group 的数据时，处理当前 group 的结果（考虑 null 类型，count、avg 函数的运算的结果）
• 实现基类的 find cell 函数，如果要找的字段有聚集函数信息，则从聚集函数结果里找，否则从字段结果里面找

其他的几个点：

• 有 GroupBy 子句时对投影列是有限制的，要么是 GroupBy 字段，要么带聚集函数
• 构造算子树的时候要把 select 子句中的投影列信息、having 子句中的字段、聚集函数信息传递给 GroupByOper

具体实现看 #15 过了两周才写这里，忘了不少，但最关键的部分已经写了

null

关键思路：在 Record 中给每个 nullable 的字段加一个 null 标志

实现上，为了简单，给所有字段都加这个标记，具体来说有两种方案：

• 每个字段旁边加一个 bit，或者一个 byte
• 每个 record 加一个 __null 字段，是一个标识对应位置是否为 null 的 bitmap

我们选择了第二种做法，这样也方便了索引对 null 的支持，把 bitmap 作为 key 的一部分，然后扩展 key compactor 就行

simple-sub-query && complex-sub-query

子查询首先要考虑如何区分父子查询的 where 谓词条件、join 谓词条件、投影列、order-by 表达式、group-by 表达式、having 谓词条件等，我们的方案是用涉及到的这些归约节点存一个 length 信息

像这样

miniob-2022/src/observer/sql/parser/yacc_sql.y

Lines 921 to 936 in 54b4154

	opt_having:
	/* empty */ {
	$$ = 0;
	}
	| HAVING having_condition having_condition_list {
	$$ = $3 + 1;
	}
	;
	having_condition_list:
	/* empty */ {
	$$ = 0;
	}
	| AND having_condition having_condition_list {
	$$ = $3 + 1;
	}
	;

对于 In 和 Exists 子查询其实也是给表达式做扩充，增加了 ListExpr(ession) 和 SubQueryExpr(ession)

do predicate 的时候：

• 先处理 Exists，右表达式一定是一个 SubQueryExpression
• 再处理 In，右表达式可能是 ListExpression 也可能是 SubQueryExpression
• 再处理其他操作符

对于父子查询表关联，我们给每个 Operator 增加了一个 parent tuple，do predicate 的时候把 parent tuple 和子算子的 tuple 拼成一个 CompoundTuple 传下去

最后对于复杂子查询留了一个 and 和 or 条件支持：

• 要想支持 and 和 or 嵌套出现，需要像表达式那样处理成树的结构
• 直接把原来语法模块中的 condition_list 改掉代价太大，所以保留了 condition_list 以及相关的地方，非 select 语句以及 select 语句的 inner join on 用的还是 condition_list
• 把 AND 和 OR 归属于比较操作符，也就是说 where 子句最后会把所有的 filter 归约为一个树结构的 Condition，而不是原来的 Condition 的数组
• 针对 select 的 where 子句单独使用了一个 opt_where，本身作为一个 expr（把 Condition 也归属于 expr 的一种）
• 后面的处理细节看提交 82e9981

alias

给每个表达式存一个别名就行

update-select

有了前面子查询的基础，这里语法阶段只需要把 updates 中原来的 values 拓展成 exprs 即可，在 resolve 阶段生成对应的 Expression，执行阶段（UpdateOperator Open）先 get_value 拿到 TupleCell，根据 TupleCell 构造 Value，以适配 table update_record 的接口

非功能性 fail

basic 挂了：钉钉群里问的镜水老师，说是重启失败了，我们在本地也复现了

本地能过测例，提交后因为段错误 core 了：

• 可能是变量未初始化的问题：成林那边有一次看了一下午发现是一个 bool 变量没初始化的原因；琨琨这边也有一次语法分析的时候没把指针初始化为 null 导致 Release 编译开 ASAN 后本地测例就 core 了
• 内存越界：比如访问野指针、数组越界等，可以用 ASAN 检查，可以开 clang-tidy 检查

此外还可以利用评测系统二分找 bug：
可以看看 alias-debug 和 unique-debug 这两个分支的最后几次提交

TODO

编码上主要是内存管理没太做好，第一周还注意着，第二周就不太行了

项目管理上还有不少问题：

• review：pr 都创建好了，但是因为赶时间基本没有 review，而且确实出现了因此导致的问题 pass simple sub query #19
• kanban issue 和 doc：没时间做，大部分赛题只做了一些零零散散的记录，经常是有了可行的方案后直接开始写代码，发现 bug 就调，没有把这些都记录下来

Last

在满分之前没好好做文档和问题记录，想着之后补起来，但由于时间原因又隔了一个礼拜，等初赛结束的时候才勉强把这篇总结写完。当时的一些细节好多已经忘了，初赛过程中一些零散的记录也不愿再整理了，之后会和这个总结一起放到 wiki 里保存。就先这样吧