感谢CMU的教授们给我们分享了如此精彩的一门课程， 希望您能尊重教授们和TAs的劳动成果！

本篇文章记录本人对实验中各个板块的理解以及踩坑， 如果您发现我过多的涉及到了实验的内容， 有违学术诚信， 请告诉我！

正文

实现一系列算子以及两个优化器。其中算子有CURD、聚合链接。 优化器为：seq_scan->index_scan以及nested_loop -> hashjoin；

Task1主要实现CURD算子以及seq_scan->index_scan优化器； Task2主要实现嵌套循环链接和索引循环连接；Task3实现哈希连接，并将循环嵌套链接优化成哈希连接；Task4实现外排序以及限制执行器。

Task1

首先Task1主要实现seq_scan（查）、insert(插入）、delete(删除)、update(更新）四个执行器。 其中， 对于seq_scan来说， seq_scan是顺序扫描， 就是利用一个表堆的迭代器， 从头到尾顺序扫描表堆将数据返回。

SeqScan

顺序扫描， 利用表堆的迭代器， 从头到尾扫描整个表堆。

这里我出现了第一个问题：什么是表堆。那么就要看一下整个DBMS的架构：

• 当SQL语句进入DBMS， 首先会进入Parser器进行语法分析， 将SQL语句分析成一棵抽象语法树AST。
• 然后这颗抽象语法树被Parser传给Binder， Binder负责将抽象语法树中的每个名词映射成Expression， 并且绑定为PlanNode计划节点。
• 然后PlanNode作为输入传给Optimizer优化器， Optimizer将PlanNode优化成为真正要执行的物理计划。
• 物理计划交给执行引擎去执行。我们本节就是要实现执行引擎中的各个执行器，也叫做算子。这个算子中有着我们要执行的计划节点。

然后表堆在哪里， 首先表堆其实是表的一个范围型指针，指向了元组的起始页和结束页。表堆保存在上图中的SystemCataLog中。 SystemCatalog被传送给算子， 然后算子根据表堆中的起始页和末尾页， 就能向缓冲池发送请求读取表堆中的所有数据。下面是表堆的架构：

所以， SeqScan直接使用表堆的迭代器（Begin指向first_page_id的， end执行last_page_id）遍历整个表堆即可。

这里我要注意第二个问题， 就是关于过滤器。 过滤器原本是一个计划节点， 但是在Bustub中， 有一个过滤器下推优化器。 我现在看一下这个优化器：（我要注意， 这个优化器为官方实现， 不是本项目中的试验任务。）

• 这个优化器的第一步就是递归去优化子计划节点。 所以我们可以认为， 当前plan的子节点已经全部下推完成。只需要下推plan节点就可以了（这个是递归算法思想， 就是把函数当作一个黑盒， 相信它可以帮助我们完成任务）。
• 此时， 如果当前节点的类型是Filter，并且子树只有一个而且为SeqScan， 那么就把自己的过滤谓词下推到SeqScan身上。

其中， 过滤谓词是一个保存在Filter里面的成员，就是上图红框。这个成员被赋值给了SeqScan就算成功了。

然后， 这个谓词是如何工作的？

• 这个谓词其实本质就是一个表达式树，是在Binder阶段生成的。 它是CompareExpression或者LogicalExpression。
• 对于CompareExpression，如果表达式是age > 18这种。那么里面的CmpType 就是GreaterThan。 age作为ColumnExpression就是CompareExpression的左子树；18作为ConstantExpression就是CompareExpression的右子树。

• 对于LogicalExpression， 如果表达式是age > 18 and age < 20这种。 里面的LogType就是and。 然后左子树是一个CompareExpression， 右子树也是一个CompareExpression。同时对于两个比较表达式同上。

传入一个表后， 想要过滤， 那么就要把每一个元组丢该这个过滤谓词， 查看是否复合表达式。 判断过程就是：

• 加入一张表有五列：id， name， age， gender， tel。sql是select * from t1 where age > 18 and id < 10。
• 上面的表达式其实就是age > 18 and id < 10。 Parser和Binder转化后就成了一个过滤谓词， 树形结构如下：

• ColumnExpression内部有一个col_index， age对应表结构的第三列， 所以这个index就是3， ConstantExpression内部有一个value， value值为18；右侧的CoumnExpression内部的col_index为1， ConstantExpression的value为10.
• 如果此时经过SeqScan从表堆中拿到了一个元组， 然后要进行过滤（Evalute函数）。就要传给过滤谓词这个元组和表的schema（列结构）。然后去计算左子树和右子树。 左子树和右子树中的ColumnExpression再分别根据自己代表的列从tuple和schema拿到列的值， 左子树和右子树中的ConstantExpression直接就能从自身获取到自己代表的value。 然后比较得到结果。

Insert

SeqScan已经了解完整的DBMS框架以及表达式、PlanNode、Catalog的大概结构。Insert简洁解释：

首先我们的Insert和SeqScan不同之处在于Insert有一个子执行器， 这个子执行器是ValueExecutor， 可以获取新插入的信息。我们如何获得这个新插入的信息， 就要理解Andy上课讲解的火山模型:

火山模型就是规定每个执行器都是从下层拉取数据， 比如SeqScan的下层是表堆，所以SeqScan的Next， 就是从表堆中拉取数据。而我们的Insert，下层是ValueExecutor， 所以Insert的Next就是从ValueExecutor的Next获取数据。理解课上的图：

• 在这张图中， R是扫描执行器， S也是扫描执行器并且带有过滤谓词value > 100。 然后两者的父节点就是一个聚合操作， 最上层为投影谓词。
• 对于投影谓词的每一次Next， 就是要从下层聚合执行器拉去元组， 即调用child->Next。 然后聚合执行器就是分别从左子执行器拉取元组和右子执行器拉取元组并进行链接， 即left_child->Next和right_child->Next。两扫描执行器从表堆拉取， 如果是IndexScan则从GetValue就要先获取RID, 然后从表堆拉取。

Insert的执行流程了解了火山模型之后变得很简单。 从child->Next获取元组， 调用表堆的插入函数即可。我要注意的是要循环获取所有的可插入元组， 然后统计插入成功的个数并放在tuple中作为输出。

Delete/Update/IndexScan

删除就是更新表堆的TupleMeta， 删除index中的数据。

Update相对Delete和Insert要困难一些， 需要先将所有要更新的元组收集起来， 然后删除这些位置的元组， 再插入新的元组。

Update和Delete同样要注意一次性处理所有可处理元素， 然后统计正确处理的元素个数， 作为tuple

IndexScan先在Init中遍历索引中保存的所有键值对， 并将值RID返回保存起来。因为索引迭代器要保护页面， 如果迭代器不能一次性收集索引中所有RID， 那么就要保存迭代器， 而长久的保留迭代器相当于保留页面的PageGuard， 增加了死锁的风险。

优化SeqScan到IndexScan

优化规则如上官方文档。如果出现内部表达式为:

@1：CompareExpression{CmpType == Equal,  ChildrenExpression[0] 
    == ColumnExpression && ChildrenExpression[1] == ConstantExpression } 或者
@2：CompareExpression{CmpType == Equal, ChildrenExpression[1] 
    == ColumnExpression && ChildrenExpression[0] == ConstantExpression } 或者
@3：LogicalExpression{LogType == Or, ChildrenExpression[0] 
    == CompareExpression && ChildrenExpression[1] == CompareExpression 
    && (ChildrenExpression[0 and 1] 符合@1或者符合@2)}

则可以将SeqScan优化称为IndexScan。

接下来说一下处理过程：

• 首先要确保对处理完成过滤谓词下推。

• 先递归处理子节点，让子节点完成SeqScan优化IndexScan

• 处理当前节点。 如果当前节点是SeqScan并且过滤谓词不为空， 则进入处理流程：

  • 如果节点内是比较表达式，并且符合上面的的三个条件之一， 则记录ConstantExpression到数组tmp_pred_keys中， 然后利用tmp_pred_keys构造IndexScan节点返回。
  • 如果节点时逻辑表达式， 则递归处理左右表达式， 只要左右有任一表达是不符合要求， 则优化失败， 返回原节点； 左右表达式都符合要求， 则将所有的ConstantExpression都记录到tmp_pred_keys中用作构造IndexScan节点返回。

Task2

要求实现聚合执行器、嵌套循环连接和嵌套索引链接。

Aggregation

正如文档中所说的， 实现聚合要使用哈希表。 CMU助教们在Aggregation的头文件中已经帮我们把哈希表的框架搭出来了， 在这里我需要实现的核心就是CombineAggregateValues这个函数。

在实现之前， 我们要保证我们真正理解了分组sql。 就比如 select max(v1), count(v2), v3 from t1 group by v3, v4。对于这个sql的理解如下：

• 首先对于一个聚合函数的输出， 它的输出是由聚合列 + 分组列组成。
• 聚合列就是max(v1)，还有count(v2)列； 分组列就是v3， v4列。所以对于该sql， 聚合函数一共要输出四列。并且这四列我们要理解到，假如我们称(v3, v4)为一个组， 那么对于每一组，在输出结果中， 它是独一无二的。并且每一组都对应两个聚合值: max(v1), count(v2)。
• 聚合输出四列后， 由聚合执行器的上层投影谓词执行器投影了max(v1), count(v2), v3三列，得到最终的结果。

所以， 聚合函数如果利用哈希表结构， 那么就会利用每个独一无二的组作为Key， 聚合值的数组作为Value。所以就有了哈希映射： (v3, v4) -> (max(v1), count(v2))。 而这， 就是文档中要使用的哈希策略。具体策略如下：

• 1、逐个拉取上层的每个元组， 解析出元组中的分组列和聚合列。
• 2、对于所有分组列， 构建一个组作为哈希表的Key。 对于所有聚合列， 保存起来等待聚合。
• 3、将Key加入到哈希表中，如果这个Key不存在， 那么要对所有聚合列初始化。然后对所有聚合列逐个聚合。

其中， 1和2是我们在Init中要做的。 然后初始化过程助教们已经帮我们完成， 我们只需要补充聚合函数即可：

这里我要注意CountStar和Count的区别， CountStar要记录所有行的数量， 不管改行是否为空，而Count记录所有非空行的数量。

Combine的实现具体要使用开关， 分别处理不同的聚合类型：CountStar, Count, Sum, Min, Max。 要处理初始值为空以及行为空的情况。

NestedLoopJoin

嵌套循环比较简单， 就是在Init的时候把所有的链接后元组保存下来， 如果是内连接， 就直接Evaluate做链接， 如果是左连接， 我需要注意如果左侧元组没有与任何右侧元组进行连接， 那么要链接上一组空值。

NestedIndexJoin

先拿到外层元组， 从索引中查找与该元组索引列相同的元组， 得到该院组的RID。 然后从表堆拉取元组链接即可。如果拉取为空，并且为左连接， 那么就要链接上一个空元组。

Task3

HashJoin

我要确保我理解了聚合算子的实现方法。 就是对每个元组根据分组列和聚合列分别构造出一个数组作为哈希表的Key和Value。 然后针对相同的Key对Value做聚合。

• 那么， HashJoin我也可以先对外表每个元组根据链接列构造一个数组， 链接列作为Key， 元组本身作为Value保存下来。
• 然后在Next获取数组元组时流式拉取内表的元组。 对于每个元组，同样获取到链接列。 查找哈希表中保存下来的链接列， 如果有。那么对该链接列对应的所有外表元组， 都与该内表元组进行链接。
• 注意的是因为每次一个内表元组可能与多个外表元组构造出多个链接元组， 但是我们只返回一个。 所以我们要保存下来这些多余的连接元组，等待下一次pull返回。

优化NestedLoopJoin到HashJoin

优化方式和SeqScan优化为IndexScan一样， 首先要处理处理下推， 然后处理子节点。 然后开始处理当前节点。 当前节点的处理逻辑：

• 判断当前节点是NestedLoopJoin并且存在过滤谓词， 如果否则直接返回即可。否则判断过滤谓词的类型.

• 建议将比较表达式封装成一个函数。 处理时如果遇到：

  • 当左右子树都为列表达式，并且比较类型为Equal。
  • 当左右子树中有一个列表达式，一个常量表达式。
  • 遇到上面两种情况， 则将左子树记录进入左过滤谓词数组， 将右子树记录进右过滤谓词数组，并且记录比较类型。然后返回true即可。 然后如果饭true， 就利用左右过滤谓词数组和比较类型数组构造HashJoin节点返回。

• 如果过滤谓词是逻辑表达式， 则拿到逻辑表达式的左右子树， 如果左右子树不为逻辑表达是或者比较表达式则代表不能优化， 直接返回即可。 否则就继续去递归处理左右子树， 逻辑表达式就继续递归， 比较表达式就按照上面的比较表达式方式处理。 最后拿到所有需要处理的过滤谓词以及比较数组构造HashJoin节点返回。

Task4

Task4实际上只有一个内容， 就是实现外排序。

SortPage

根据文档的内容， 首先要实现SortPage类。

这个SortPage我们可以理解为类似于表堆内的page或者索引页。先获取BufferPool的一个帧的首地址， 然后在帧里面添加数据。官方代码只给我一个类， 没有给任何属性和方法， 说明要我全部自己设计。 下面为设计流程：

SortPage中不需要考虑RID， 我需要考虑为什么不需要将RID保存到Page中， RID是元组所在磁盘页以及槽位置。 RID的作用是用来从指定页面的槽内获取数据。 但是在外排序中， 我们的数据都拿到了SortPage中， 获取数据就是从SortPage中拿， 所以RID不再需要。

首先说元数据， 需要一个t_size来表示元组的大小、然后capacity表示SortPage一共能够储存多少元组、cur_size_表示当前储存了多少元组、cur_page_id表示当前页面的页面ID。

然后另一个data_指针指向存储区域的首地址。

函数设计

我需要先考虑要实现什么函数， 首先要有一个Init函数， 用来初始化页面内的元数据以及存储区域。因为要做修改， 所以该页面应该是WritePageGuard。 同时我需要知道schema里面保存了length， 这个length就是Tuple内所有列的大小。

然后， 文档中也要求我实现MergeSortRun， 这个MergeSortRun其实就相当于表堆， 只不过它是SortPage的表堆， 记录了在该堆内所有的页ID。 MergeSortRun里面有该表堆的迭代器指向SortPage的元组位置遍历SortPage。所以， 迭代器需要能够读取SortPage，那么就需要能够获取SortPage， 利用ReadPageGuard获取SortPage的读指针。 所以这里也要有一个GetPage函数。

然后想要获取里面的数据需要有GetTupleAt（index)。

外排序时， 获取两个不同SortPage内的元组， 然后比较两个元组， 取出其中一个插入新的SortPage。 所以向SortPage插入元组需要有InsertTuple函数。

防止SortPage移除， 同时还要能够获取最大容量， 获取当前容量。

Init函数

上面是元数据和数据的存储关系。 四个元数据的类型都是uint32_t， 所以都为四个字节。我们就可以设置四个指针分别指向偏移量为0、4、8、12的位置。 最后data_执行偏移量为16的位置。

同时要初始化， 初始化需要注意t_size的大小。

对于Tuple来说， 它的size是sizeof(uint32_t) + schema.length。这个schema.length代表了Tuple内数据的所有列的大小的总和。 但是除了数据的总大小， 还需要在Tuple的头部有一个uint32_t大小的"元数据"， "元数据“保存了当前Tuple内数据的大小。也就是说， 如果Tuple内数据的大小为32， 那么Tuple的总大小就是36， 一直要多4个字节。这样做是为了方便序列化。

Init函数对页面进行了修改， 所以要获取WritePageGuard， 同时获取表的schema。

GetPage

GetPage只是用来读取SortPage, 所以只需要获取ReadPageGuard， 同时获取表的schema。

GetTupleAt

获取元组时注意使用反序列化获取元组。

InsertTuple

插入元组时使用序列化获取元组。

GetSize

返回cur_size_, 当前容量

GetCapacity

返回capacity_， 最大容量。

MergeRun & Iterator

MergeRun其实就可以理解为一个SortPage的表堆，而Iterator就可以理解为表堆的Iterator。

这里对比表堆以及表堆的Iterator是如何设计的:

表堆中保存了frist_page_id和last_page_id。而表堆中的页面是由指针链接起来的。 同样的， MergeRun里面直接保存了堆中的所有page， 两者都保存了一组page。

然后我们看一下表堆的迭代器的GetTuple函数：

调用的就是表堆的表堆的GetTuple。而表堆去调用的table_page的GetTuple。 （写到这里， 我忽然发现， 我在SortPage中， 是否可以仿照table_page的设计， 添加一个next_page_id。这样迭代器在++的时候会更加好处理）

有了上面的认识之后， 我可以仿照表堆的Iterator设计MergeRun的迭代器。MergeRun的迭代器中可以保存一个cur_index指向迭代器遍历到当前页面的第几个元组。保存一个cur_page_id表示遍历到了哪个页面。

• 我在这里还添加了一个处理， 就是保存了当前页面的ReadPageGuard（写当这里， 我发现这样写锁粒度会很大， 这里可以优化， 仿照表堆迭代器，page_id和index， 这个ReadPageGuard只有当GetTuple的时候获取。）， 方便处理。 --- old version。

• 现在我要思考优化， 不加ReadPageGuard。

  • 那么就是说， 迭代器此时与页面保护分离， 迭代器只保证了维护的位置的正确性， 即单次读取到正确性。 不保证全局扫描的正确性， 迭代器在扫描的过程中， 页面的其他位置可能被其他事务修改， 插入， 和删除页面。
  • 把这个问题迁移给表堆迭代器。 我发现， 在整个bustub中出现的这种扫描过程中，页面突然被其他事务刷新的情况是不可能的， 因为我ReadPage后， 此时页面pin了， BufferPool我正确的设计了保证页面被pin住无法被刷新至磁盘。所以可以确保在单次读取时， 页面不会突然被刷新。
  • 第二个问题就是， 我发现， 迭代器在扫描过程种， 页面其他位置被其他事务修改的这种情况， 不就是幻读吗？ 对于幻读， p4中实现了序列化验证，所以幻读的问题也被解决了， 所以不加ReadPageGuard对表堆来说完全没问题。
  • 如果把问题迁移至IndexIterator呢？ 首先如果只保证单次读取的正确性， 那么就要允许页面被修改。索引的数据页被修改， 其实就是有新元组插入了，所以新元组的RID插入到了索引里， 本质也是其他事务对表堆进行了修改。可能导致分裂， 但是分裂不会影响， 因为新页会在旧页后面链接， 迭代器会自行迭代至新页。所以这里的本质也是发生了幻读， 可以由序列化验证管控。 但是这样真的好吗？因为索引的设计本身就是同一时间只有一个事务能够拿到索引。如果迭代器不加全局锁， 那么可能会导致频繁页面刷新的情况。会不会导致效率下降？（TODO， 迭代器中可能是不需要放PageGuard， 但是频繁的刷新页面会导致物理IO变多， 效率可能会降低。但是锁粒度会变小，更不容易死锁。 如果有PageGuard, 那么索引迭代器就不能长时间保留导致长时间占用页面， 其他其他事务或者当前事务的上下层管道会阻塞在该页面， 容易发生死锁。）
  • 如果将MergeRun的Iterator设计为只保证单次读取的正确性， 那么首先页面刷新问题可以保证（因为具有pincount）。 然后就是幻读的问题， 但是对于外排序来说， SortPage都是事务本身创建的，所以不会有其他线程看到该SortPage。 所以不会有幻读的问题。 所以MergeRun同样可以只保证单次读取的正确性。

外排序逻辑

排序逻辑就是先从管道拉取所有的元组放到SortPage中，同时记录所有SortPage的page_id， 每一个page_id独属于一个MergeRun。当一个SortPage放满了， 那么就把这个SortPage排序解钉， 重新获取一个SortPage即可。当结束时， 我们就可以得到一个MergeRun数组， 每个MergeRun内部的数组元素个数都是1。

这里要自主实现一个 SortEntry类型的operator()。 我们需要注意， 对于sort来说，默认采用less， 如果p1 < p2， 那么返回true， 并且p1被排在p2之前， 为升序。 也就是说， 升序比较p1 < p2是否为true。 当降序时， 则比较p1 > p2是否为true。

现在回归排序逻辑。 当拿到所有的元组后， 进入外排序循环， 每次处理相邻的两个MergeRun元组， 将两个MergeRun合并成一个MergeRun。注意将原MergeRun元素内页面删除。最后直至MergeRun数组中只有一个元组为止， 结束循环。

p3的全部内容已经完毕， p3个人觉得应该是4个lab里面最难的了。 东西多， 并且每个算子，每个优化器，都有新的知识要去学习。这里唯一不能把握的就是对于表堆迭代器、索引迭代器、SortPage迭代器三个迭代器如果包含PageGuard是否会增加效率，我要去验证。

以上。