当前位置：首页 > news >正文

cmu 445 poject 3笔记

news 2025/7/4 21:12:56

2022年的任务 https://15445.courses.cs.cmu.edu/fall2022/project3/
task1, 从磁盘读取数据的算子
task2, 聚合和join算子
task3, sort,limit,topn算子，以及sort+limit->TopN优化
leaderboard没做
本文不写代码，只记录遇到的一些思维盲点

Task1

scan

比较简单，参考filter算子的实现即可。

insert和delete

需要根据index对象的keyAttr来将原始的tuple转换为index的entry。
类似下面这样

    for (auto it : indexs) {auto key_attrs = (it)->index_->GetKeyAttrs();std::vector<Value> index_cols(key_attrs.size());size_t i = 0;for (auto col_idx : key_attrs) {index_cols[i++] = (child_tuple.GetValue(&child_executor_->GetOutputSchema(), col_idx));}(it)->index_->DeleteEntry(Tuple(index_cols, (it)->index_->GetKeySchema()), child_rid,exec_ctx_->GetTransaction());}

Task 2

Aggregate聚合算子

补充hash表的计算函数CombineAggregateValues，这个比较简单，就是根据不同的算子做对应处理即可。
1. 需要判断下input的结果是为空，对于count（*）算子，会累加一行，其他的算子都不处理
对于计算，需要先执行构建操作，后续调用聚合算子的next时结果都是从构建的结果里取
需要特别注意的是，如果是个空表，并且没有group by操作，也是需要返回结果的

第二步大概代码如下

while (true) {auto status = child_->Next(&child_tuple, &child_rid);if (!status) {first_next_ = true;break;}keys.group_bys_.clear();for (const auto &expr : key_exprs) {keys.group_bys_.emplace_back(expr->Evaluate(&child_tuple, child_->GetOutputSchema()));}vals.aggregates_.clear();for (const auto &expr : val_exprs) {vals.aggregates_.emplace_back(expr->Evaluate(&child_tuple, child_->GetOutputSchema()));}aht_.InsertCombine(keys, vals);}

第三步大概代码如下

 aht_iterator_ = aht_.Begin();if (aht_iterator_ == aht_.End()) {// empty tableif (key_exprs.empty()) {vals.aggregates_.clear();for (uint32_t i = 0; i < plan_->agg_types_.size(); i++) {vals.aggregates_.emplace_back(ValueFactory::GetNullValueByType(TypeId::BIGINT));}aht_.InsertCombine(keys, vals);aht_iterator_ = aht_.Begin();std::vector<Value> cols;cols.insert(cols.end(), aht_iterator_.Val().aggregates_.begin(), aht_iterator_.Val().aggregates_.end());++aht_iterator_;*tuple = {cols, &GetOutputSchema()};return true;}}

Join算子

也是分为构建阶段和取数据阶段。
构建阶段，主要是把右表（内表）的数据读到一个数组里，用于后续跟左表（外表）的元素进行匹配。
取数据阶段就是读取左表的数据，然后去上面的数组里一行一行匹配。

需要注意的是，一行左表的数据，可能会对应多行右表的数据，因此需要遍历整个数组才行。

我的做法是记录一个右表的游标和一个左表的当前记录
每次取出左表的数据后，这个游标清零，从头开始匹配右表数据。匹配成功就返回
下次取数据时，判断这个游标是否到右表的尾部了，如果不是，那就继续匹配。
直到尾部后，再拉取一个左表的数据，从头开始匹配。

Task3

sort 算子

主要是排序算法的实现，需要判断下null的位置。
对于升序，null是最小的。对于降序，null是最大的。

auto comp = [&](Tuple &a, Tuple &b) -> bool {for (const auto &order : orders) {auto left = order.second->Evaluate(&a, GetOutputSchema());auto right = order.second->Evaluate(&b, GetOutputSchema());bool ret = true;if (left.IsNull()) {if (order.first == OrderByType::DESC) {ret = false;}} else if (right.IsNull()) {if (order.first != OrderByType::DESC) {ret = false;}} else {auto val = left.CompareEquals(right);if (val == CmpBool::CmpTrue) {continue;}val = left.CompareLessThan(right);if (val == CmpBool::CmpTrue) {if (order.first == OrderByType::DESC) {ret = false;}} else {if (order.first != OrderByType::DESC) {ret = false;}}}return ret;}return true;};

TopN算子

对于topN算子，使用堆来存limit个元素。
如果是降序的，就构建最小堆。这样，每次淘汰都是淘汰最小的值，最后堆里保存的是最大的limit个元素。
同理，如果是升序的，就构建最大堆。这样，每次淘汰的都是淘汰最大的值，最后堆里保存的是最小的limit个元素。

std的priority_queue默认是最大堆，因此比较函数就按正常的排序规则就行（同sort的比较方式），它自动的反转构建堆。对于升序，就会构建最大堆；对于降序，就会构建最小堆
因为堆里的数据实际上跟最终的结果是相反的，因此在构建阶段，需要把堆里的数据取出来放到一个vector中，取的时候，从尾部到头部取出就行

sort+limit->TopN

需要递归处理，先处理子算子，然后再处理本节点。

std::vector<AbstractPlanNodeRef> new_child;for (size_t i = 0; i < plan->GetChildren().size(); ++i) {new_child.emplace_back(OptimizeSortLimitAsTopN(plan->children_[i]));}if (plan->GetType() == PlanType::Limit) {if (plan->GetChildren().size() == 1 && new_child[0]->GetType() == PlanType::Sort) {auto sort = std::dynamic_pointer_cast<const SortPlanNode>(new_child[0]);auto limit = dynamic_cast<const LimitPlanNode *>(plan.get());SchemaRef schema = std::make_shared<const Schema>(plan->OutputSchema().GetColumns());auto ret = std::make_shared<TopNPlanNode>(schema, (new_child[0]->GetChildAt(0)), (sort)->GetOrderBy(),limit->GetLimit());return ret;}}return plan->CloneWithChildren(new_child);