miniob 2023 初赛记录
miniob 2023 初赛记录
写在前面
第一次参加miniob，记录一下初赛。总体来说没有什么技术难度，大部分是体力活，但也让我复习了不少数据库细节上的东西，比如MVCC、SQL解析与查询计划构建等等。记录是为了以后再参加时可以给自己或者其他同学做参考。
各题思路
Drop table
这个sql解析语法已经写好了，需要做的是添加一个drop_table_executor，然后为Db类（管理数据库的元数据的类）添加一个drop_table函数，函数内需要删除一个table的元数据文件、index文件、data文件，然后还需要回收bufferpool中该文件对应的页，成功的话再将该table的tableMeta从Db类中删除即可，此时就完成了一个table的完全清理。
update
这个虽然分值不高，但是涵盖了从sql层解析到底层table分页存储的内容。具体来说，包括：
- 增加update语句的sql解析
- 增加updateStatement\updateLogicalOperator\updatePhyicalOperator，并在各个stage中添加构建这些对象的链路，至于这些对象需要哪些字段以及如何构建，可以参考select和delete的链路。
- 增加tablehandler->update_record()、pagehandler->update_record函数，为updatePhyicalOperator提供存储上的支持。tablehandler->update_record()除了修改data文件，还需要修改对应的索引（现在只支持b+tree索引，需要先delete再insert)。
Null
- 增加建表的时候的语法，为table增加元信息nullable；
- 增加Value的null字段，标识该字段是否为null。在insert value时，如果是NULL，则将 null 赋值为true；
- 为where增加 is null 和 is not null 语法；
- 在insert和update时，在executor或者resolver阶段检查插入的数据是否允许null，如果允许，则插入为一个特殊的值，对于INT来说，插入INT_MIN, FLOAT:FLOAT_MIN, CHAR(N): ‘/0’，这里在从record中存储数据以及读取数据为value时，提供一下判NULL支持。
- 新增compareType IS和IS_NOT，在表达式进行比较时，如果两边value有任意一个为null，则判断比较运算符是否为IS或者IS_NOT，如果不是，直接判false；如果是，则返回 (left.is_null() == left.is_null()) == (cmptype==IS)
- 可能需要在别的地方加上对NULL特判的支持，比如聚合函数。
- 以下是mysql的做法，每个coloumn一个bit表示是否是null(https://cloud.tencent.com/developer/article/1469056) 这是关于mysql 与null有关的index上走没走索引的讨论
aggregation-func
-
除了sql层添加的语法，主要增加了一个aggregation的逻辑和物理算子，在select查询计划中，放在查询计划的顶端（和projection 平级），即predicate以上的位置。agg算子的逻辑可以认为是bustub中group by算子的子集，功能还很弱，只能输出一行数据。
-
另外，这里还涉及到schema的问题，miniob中的schema表示的是数据的输出字段显示格式，具体在RC ExecuteStage::handle_request_with_physical_operator(SQLStageEvent *sql_event)。在agg这个题目中，由于需要为聚合字段添加名字，所以需要在这个函数中添加命名方式。比如“MIN(字段名)”等。
所有权的设计挺有意思的，可以详细写一下, 包括swap和move（生成phyical operator时从sqlnode move过来而不是采用指针引用，可以使之后的执行减少一次访存的开销）
过测例的时候发现，恶心的是强制要求把很多能在parse阶段解决的错误延后到resolve阶段，使得需要重新设计sql部分。
sub-query
-
采用物化的方法，优先进行子查询，然后将子查询的结果作为Value(或者vector)放在predicate_operator中。具体来说，这是通过给predicate_operator加child做到的。predicate_operator在open时，会检查自己有几个children，如果有两个children，说明第二个children是一个子查询，则优先进行子查询，利用得到的结果构造出最终的predicate expression。本质上是将expression的构造时间延后了。
-
为了支持IN/NOT算子，设计了一个新的ExprType，称为ExistExpr，继承自Expresion，其内部维护一个Value集合。get_value时根据查询值是否在这个Value集合返回一个bool值。
-
过测例时发现update的set value字段也可以是一个subquery, 我采用的还是加child的方式，不过这次是加到update_operator后面，逻辑也是一样的，open时发现有两个children则优先进行子查询。本质上是将value的构造时间延后了。
multi-index
- 修改存储在index文件中第一页的元数据
- 实现最左匹配：在生成物理执行计划时判断table get能不能走索引，用最左匹配原则。如果有，则需要构造出left key和right key，剩下的无法走索引的字段左右分别设置为最小值和最大值即可。注意，由于这里我的NULL值是比MIN（MIN设计的是NULL+1)还小的值，所以左边界是NULL。
- 另：logical_operator重写阶段实现了谓词下推（predicate pushdown)，所以在table_get_logical operator构建物理执行计划时，如果有谓词，再尝试使用索引即可，如果有索引，构建index_scan的物理执行计划。
**text **
- 弄个新的TextPage, header存char_num, char_num表示这个page中存的实际数据有多少， next_page指示下一个TextPage的page_num。读取时，当char_num == FULL_CHAR_NUM && next_page != NULL 时，说明这不是最后一页，那就继续往下读，最后一页读char_num个字符就行了，最后再拼接起来，记得读一个unpin一个。
- delete_record时，如果这个record字段中有Text类型的，那还需要回收这个Text字段对应的所有TextPage，还给buffer_pool。
- update_record时，如果改的是Text类型的字段，那就就先回收之前所有的TextPage，在重新申请新的。
**alias **
-
在构建select/ update/ delete statement时，先将别名替换为真实名。
-
需要修改输出时的表头，具体位置在以下函数中:
RC ExecuteStage::handle_request_with_physical_operator(SQLStageEvent *sql_event) -
这个题建议多提交，因为本地没给测例
**update-select **
- 需要维护一个映射，用来表示每个set子句是不是一个子查询，这个用一个bool vector来存就行了,true表示是子查询，false表示是value。
- 只要违反了一个unqiue constraint或者null constraint就整体放弃；
unique
- 为index元信息添加字段，为B+tree添加check_unique_constraint函数；并在Table的insert_record、update_record函数中添加对应的逻辑；
- update_record其实需要改成update_records。
group-by
group-by可以参照bustub的做法，核心思想就是构建一个哈希表，记录从<aggregation_key>到<aggregation_value>的映射，aggregation_key就是一个vector，而aggregation_value就是要进行的聚合函数的结果，也是个vector（如果有多个聚合值的话）。
big-group-by
这个没有涉及到topk类似的优化，要过这个需要做一些纯内存上的C++优化。队友用profiling找了一晚上，发现是std::sort里Value的构造函数花了大部分时间（当然WSL可能不准）。最后他把TupleSpec这个对象的移动构造函数显式地写了一下，居然就过了，如下：
const TupleSpec(TupleSpec &&spec) = default;
我搜了下std::swap的实现：
template<typename T>
void swap(T &a,T &b) noexcept
{
T temp = std::move(a);
a = std::move(b);
b = std::move(temp);
}
c++11 在无自定义的(析构，拷贝，赋值，移动赋值)时存在编译器提供的默认移动构造函数。move语义：如果对象有移动构造，就优先调用移动构造，如果没有移动构造，就调用拷贝构造。奇怪，为什么不会生成自定义移动构造函数呢？
https://www.zhihu.com/question/467102319 c++中构造函数default有什么用？
complex subquery
- 嵌套子查询和关联子查询的区别，关联子查询质上是由外表驱动内表进行子查询，即对外表的每一行数据，都进行一次子查询，效率比较低 https://zhuanlan.zhihu.com/p/149862836 这篇文章写得很好。
- 做法有两种，一种是在一开始就将所有表join起来，物化为joInTuple，然后将Not IN/IN 分别转化为NOT_EQUAL和EQUAL，将EQUL / Greater/ Less 等比较算符转化为 Group By+Having，达到关联子查询去关联的效果。这个实现方法的难点在于查询计划的构建不是递归的，实现起来难度较大；
- 另外一种做法是将subquery作为一个Expression, 通过get_value方法传入上层的tuple，如果是关联子查询，则可以在这个tuple中获得需要的关联字段值，这个tuple是在filter_predicator的next方法里一层层join起来的，本质上就是将join的过程延后了。这个做法的优点在于构建执行计划的方法是递归的。具体实现时发现了循环依赖的问题，具体原因是：Expression.h中使用构建了新的exp称为SubqueryExpr，为了保证该类能自己取到数据，需要有一个类型unique_ptr的成员变量，但PhysicalOperator是依赖于下层的Expression的，这就产生了依赖倒转。解决方法记录一下：
- 使用回调函数，消除循环依赖：成员变量改为std::function tuple_getter，表示一个上层给予的一个回调函数，这个回调函数由构建SubQueryExpr时设置好。实现时遇到了点问题，其实就是C++的这个std::function在捕捉了non-copyable的变量，比如unqiue_ptr后，自己会变得non-movable，导致无法将回调函数交付给SubQueryExpr；这个其实可以使用template来避免使用std::function来避免这个问题。
- 前向声明：很简单，在expression.h头文件里不include “physical_operator.h"即可，但前向声明一下class PhysicalOperator；这种方法work的理由可以回想一下CSAPP里说的编译链接的过程。
发现了一个巨大bug, 从table_get中返回的record居然不是owner,也就是说实际数据在buffer_pool上，太危险了。
expression
队友写的
- 与实际执行的Expression区分一下，语法分析yacc里构建出 SQLExpression，记录表达式里引用的表名字段名，形成表达式树。在解析时再结合metadata构建出具体的fieldExpr和ValueExpr，递归构建出执行时的表达式树。
- 修改project_operator，支持表达式。predicate_operator不用改就能用。
mvcc-update
-
这个框架内判断版本可见性使用的是visit_record函数，可见的版本为 begin_id<x_id<end_id或者-begin_id = x_id的版本。
-
mvcc中的多版本时通过调用delete_record再调用insert_record来完成的，不能用update_record(不能动原来的数据，得形成新版本）。
-
而由于要支持unique_index，unique_index和多版本时天然冲突的，所以用原先的Table::insert_record会有问题，即会与旧版本发生unique冲突，这显然是不合理的。正确的做法是为field再添加一个字段next_rid，来形成一个版本链，只在BPlusTree中维护头RID即可。这还需要修改index_scanner的访问逻辑，seq_scanner的逻辑不需要变（mvcc旧版本存储在同一个表内会造成seq_scan的性能很差，innodb相当于存储在redolog里，避免了这个）。
-
他这个mvcc设计得非常糟糕，本质原因还是因为没有维护版本链，需要记录begin和end两个时间戳，另外，通过负数来做是否正在修改的记号也是非常粗暴且不直观。所以与之关系较密切的Clog日志恢复部分我就没有细看了。
其余值得注意的
- observer使用的是SEDA架构，介于多线程与事件驱动模型之间。以后有时间可以学着实现一个SEDA服务器。