CMU15445 2022fall project3
project3相对project2的b+树来说简单太多了，整体没有什么痛苦的debug，基本就看看其他算子的实现参考一下，很快就能写出来。
Task 1 - Access Method Executors
SeqScan
首先我们需要知道：init是做一些初始化工作的，next是留给上层节点调用的，SeqScanExecutor位于最下层，所以它是没有子节点的。
关于Tuple是什么，它其实就是一张表中的一列数据，其中的Value就是每个列上的具体数据。
刚一上手还是有点不知道要干啥的。构造函数的成员挨个点进去，看看都是啥。
ExecutorContext中有个Catalog，这个明显看起来很有用，点进去我们会发现果然很有用，里面有表的信息和索引的信息。
std::unordered_map<table_oid_t, std::unique_ptr<TableInfo>> tables_;
/** Map table name -> table identifiers. */
std::unordered_map<std::string, table_oid_t> table_names_;
/** The next table identifier to be used. */
std::atomic<table_oid_t> next_table_oid_{0};
/**
* Map index identifier -> index metadata.
*
* NOTE: that `indexes_` owns all index metadata.
*/
std::unordered_map<index_oid_t, std::unique_ptr<IndexInfo>> indexes_;
/** Map table name -> index names -> index identifiers. */
std::unordered_map<std::string, std::unordered_map<std::string, index_oid_t>> index_names_;
/** The next index identifier to be used. */
std::atomic<index_oid_t> next_index_oid_{0};
这个算子不需要使用索引，我们只看表，进入TableInfo，我们看到TableHeap的指针，再点进去，发现它维护了一个双链表，里面就是具体的tablepage。
到这里我们应该就能知道bustub是怎么存储这些表的了，下面这张大佬画的图很清晰的展示了目录和表的结构。
再点进SeqScanPlanNode，里面有一个tablename和tableid，那现在的任务应该很清晰明了了。
我们需要在init中保存指定tableid的table的迭代器（TableIterator，其实我感觉它是Tuple迭代器，毕竟它是一个一个Tuple遍历的，点进去你会发现它的实现是到页末尾就会找到下一个页的开头的tuple），然后在next中一个一个的把tuple推上去。
Insert
有了上面的经验，现在我们应该清楚算子是在做什么了，那这个Insert算法，任务无非就是调用它的子节点获取tuple，然后插入到对应的表中，并更新索引。
索引的key怎么获取，查看Tuple我们可以看到KeyFromTuple()函数，而Index类中刚好有GetKeySchema和 auto GetKeyAttrs两个函数，接下来就不用多说了。
Delete
基本和Insert一样，不过记得是MarkDelete标记删除，再把索引删除DeleteEntry，这里其实调用的就是我们在project2中为b+树实现的Remove。
IndexScan
Init中获取索引指针，记得转换成B+树类型，实验讲义里提到了，Next中记得把rid也赋值一下，在做project2中我们就知道RID其实就在索引的第二个模板参数中，再补充一张图片。
Task2 - Aggregation & Join Executors
Aggregation 聚集函数
首先，根据task1，我们能知道，agg的流程应该是调用子节点的next获取tuple，处理后向上传输tuple就行了。
但是由于agg的独特目的，我们需要在init中提前把值都算好，当agg的父节点需要tuple时，直接调用agg的next一个一个的把数据返回。
这里我们结合实际例子来分析一下这个过程，例子就是test中的一个sql，这个例子中没有group_by，比较容易分析。
t1 table
| v1 |
---------
|-99999 |
|99999 |
|0 |
|1 |
|2 |
|3 |
select count(*), min(v1), max(v1), count(v1), sum(v1) from t1;
- 首先我们需要搞清楚，agg的子节点每次传上来的tuple中是什么东西，以及它传输了几次。
aggregation_executor.h为我们准备了两个函数用来将tuple转换成AggregateKey和AggregateValue，而这两个类中有一个成员变量std::vector<Value>，两 个函数的作用应该就是将子节点传上来的tuple中的value，按key分组成value。
而目前我们分析的例子中没有group by，所以我们在MakeAggregateValue和MakeAggregateKey中打印出value的值，发现如下图所示
...
...
1 -99999 -99999 -99999 -99999
1 99999 99999 99999 99999
1 0 0 0 0
1 1 1 1 1
1 2 2 2 2
1 3 3 3 3
MakeAggregateKey打印了一堆换行，MakeAggregateValue打印了上面这些数字，现在我们应该能清楚的知道，agg的子节点每次传输上来的tuple中的内容其实就是table表中每一行的值，第一个就是行数（只传上来一行，自然就是1），为什么一个值传好几次，观察我们的sql应该就知道为啥了。
2.接下来我们要分析的就是将子节点传上来的tuple分成kv之后通过InsertCombine插入到哈希表中，这个过程是怎么进行的（也就是聚集函数的值是怎么迭代更新的）
观察InsertCombine函数，我们发现表为空时，会插入一个agg_types_的顺序插入计数*的聚集函数列为0，其他都为null的一条数据，在我们的例子中，插入的值就是key：空，value：{1，integer_null，integer_null，integer_null，integer_null}。
然后通过CombineAggregateValues迭代更新哈希表中key相同的那一列的数据，CombineAggregateValues需要我们自己写。
3.接下来我们保存哈希表的首迭代器，以便在next中使用，因为没有group by，在例子中其实现在只有一条数据，也就是计算好了的{6, -99999, 99999, 6, 6}
4.next中向上层返回tuple时，按照key和value来初始化tuple并返回就好了。
NestedLoopJoin 连表查询
直接再init中将所有左右子节点的元组取出来，然后比较他们，相等的保存到一个新的元组数组中，处理好左连接时应该添加上右元组相同类型的null，记得加上向上输出的模式。
在next中遍历vector<Tuple>就可以了。
NestedIndexJoin
和上面那个有一点点不一样，现在只有一个子迭代器了，右表现在需要使用plan中的KeyPredicate先找到左表中的对应索引的key，然后再去索引中查询key对应的value，这个value我们在project2中就知道是一个RID，所以现在我们需要去回表查询右表对应的Tuple，在这里我发现右表中每列的Type其实不需要找一个具体的Tuple，而是可以直接通过right_schema.GetColumn(i).GetType()来获取，方便我们设置null值。
Task 3 - Sort + Limit Executors and Top-N Optimization
Sort
在Init中获取子节点的tuple存起来，然后sort一下。
一开始我有点没太懂AbstractExpression是用来干啥的，查了一下大佬的博客才搞懂。
比较函数可以这样写
[this](const Tuple &a, const Tuple &b) {
auto order_bys = plan_->GetOrderBy();
const auto &schema = child_executor_->GetOutputSchema();
for (auto &[order_type, expr] : order_bys) {
Value va = expr->Evaluate(&a, schema);
Value vb = expr->Evaluate(&b, schema);
if (order_type == OrderByType::DESC) {
if (va.CompareEquals(vb) == CmpBool::CmpTrue) {
continue;
}
return va.CompareGreaterThan(vb);
}
if (va.CompareEquals(vb) == CmpBool::CmpTrue) {
continue;
}
return va.CompareLessThan(vb);
}
return CmpBool::CmpTrue;
}
直接返回CmpBool类型也是可以的。
Limit
这个维护一个变量就可以了。
Top-N Optimization Rule
算子实现用优先队列构造limit大小的小/大顶堆就可以了，注意优先队列中的比较函数和sort函数里的实现是反过来的。
比如对一个sort升序和堆升序的比较函数如下。
#include <iostream>
#include <vector>
#include <algorithm>
// 小顶堆比较函数
struct cmp {
bool operator()(int a, int b) const {
return a > b; // 升序的小顶堆比较函数
}
};
// std::sort比较函数
bool sortcmp(int a, int b) {
return a < b; // 升序的比较函数
}
int main() {
// 使用小顶堆比较函数创建一个小顶堆优先队列
std::priority_queue<int, std::vector<int>, cmp> minHeap;
// 向小顶堆中插入一些元素
minHeap.push(5);
minHeap.push(3);
minHeap.push(7);
minHeap.push(2);
minHeap.push(8);
// 输出小顶堆中的元素（按升序）
std::cout << "小顶堆中的元素：";
while (!minHeap.empty()) {
std::cout << minHeap.top() << " ";
minHeap.pop();
}
std::cout << std::endl;
// 使用std::sort进行排序
std::vector<int> vec = {5, 3, 7, 2, 8};
std::sort(vec.begin(), vec.end(), sortcmp);
// 输出排序后的元素
std::cout << "排序后的元素：";
for (int num : vec) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
但是为了控制数量为n，在要求降序时，我们需要升序生成小顶堆，在达到数量后，每次pop一下最小的值，最后我们就可以得到最大的n个升序的值，我们pop到数组中反转一下就行了。
SortLimitAsTopN优化器的实现，可以看一下其他的优化器实现。
我们需要后续遍历plan node，当遇到当前node为Limit且child node为Sort时，优化成TopN node并返回给自己的父节点，记得把sort节点的子节点赋值给TopN节点。
后序遍历的过程如下：
std::vector<AbstractPlanNodeRef> children;
for (const auto &child : plan->GetChildren()) {
children.emplace_back(OptimizeSortLimitAsTopN(child));
}
...
Summary
后面的选做内容由于时间问题先不做了，等后面有时间回来填坑（可能找到实习了就会回来做）。
附一张bustub架构图，感觉到了这个lab突然有种把一切都打通了的感觉。
