CMU15445(2023fall) Project #3 - Query Execution(上)详细分析

晚日寒鸦一片愁

柳塘新绿却温柔

若教眼底无离恨

不信人间有白头

——鹧鸪天

完整代码见：

SnowLegend-star/CMU15445-2023fall: Having Conquered the Loftiest Peak, We Stand But a Step Away from Victory in This Stage. With unwavering determination, we press onward, for destiny favors those brave enough to forge ahead, cutting through the thorns and overcoming every obstacle that dares to stand in their way.

目录

Project #3 - Query Execution

调试说明

执行计划分析

Task #1 - Access Method Executors

1. 顺序扫描（SeqScan）

2. 插入（Insert）

3. 更新（Update）

4. 删除（Delete）

 5. IndexScanExecutor（Index）

6. 优化顺序扫描为索引扫描（SeqScan → IndexScan）

Task #2 - Aggregation & Join Executors

Aggregation

NestedLoopJoin

Project #3 - Query Execution

调试说明

要准确体会executor的执行过程，进行调试是相当重要的。但是Lab 03的测试方法不同于以前，是利用sqllogictest来执行slt文件。

1. make -j$(nproc) sqllogictest2. ./bin/bustub-sqllogictest ../test/sql/p3.00-primer.slt –verbose

搞得我一直以为调试要从sqllogictest下手，但这样配置显然是有问题的

        去群里问了也没有得到想要的答案。反复看了几遍handout才发现有可能是通过bustub-shell进行调试，试了一下还真是。

        会了如何进行调试之后，我们就可以着手先分析各种sql语句的执行过程了。首先，我们可以先执行几遍sql语句来对Query Processing有个大致的了解，如下图。

执行计划分析

简略分析SELECT colA FROM __mock_table_1;的执行过程

以看到这里的expression是“#0.0”，表示左表(当前表)的第0列元素，对应colA。

显然，colA属于一个column_value_expression。

expr->Evaluate(&child_tuple, child_executor_->GetOutputSchema())

对于这句代码，意思是在表__mock_table_1中，提取当前tuple对象的第0列元素。

至于tuple的data部分要怎么看，我们可以结合每个列的类型具体分析。比如这里__mock_table_1的两个column都是int类型的，各占4个字节，加起来就是8字节。

又可以发现tuple的data部分是char *类型的数组，所以数组的前4位都是表示colA的值，数组的后4位表示colB的值。

再进一步分析char *data是怎么表示数值的。我们可以发现100对应“d”，这是因为d的ASCII码恰好是100，故可以用“d”来表示100。

而data[4]=‘，’，data[5]=‘\x01’又是怎么表示300的呢？

在小端字节序中，低位字节（较小的数字）存储在内存的低地址处，较高位字节存储在高地址处。

• data[0] = ','（0x2C，44 十进制）存储在内存低地址。
• data[1] = '\x01'（0x01，1 十进制）存储在内存高地址。

那么这两个字节拼接起来就变成了：

0x01 0x2C

即，低字节 0x2C 和高字节 0x01 组合起来形成了一个 16 位的数字。我们可以将它看作是一个十六进制数 0x012C，转化为十进制就是：

0x012C = 1 * 256 + 44 = 300

所以，data[0] = ',' 和 data[1] = '\x01' 会在小端字节序中组合成十进制的 300。如下图

再用filter举一个例子。

以此类推直至遍历结束。

然后，第二个中难点就是搞清楚各种expressions的作用了。关于Lab03的各种关键代码的分析，由于内容过多我直接放在github里面了。强烈推荐结合这张图先完全领悟这些关键代码再开始写，不然会异常折磨

上面内容后面还会用到，务必要领悟通透！

下面正式开始分析task。

Task #1 - Access Method Executors

1. 顺序扫描（SeqScan）

着手开始实现时，首先还是要先看看这个语句的执行计划。

        可以看到，SeqScan就是最底层的executor，它没有child_executor的存在。至于为什么“Planner”部分的执行计划可以优化为“Optimizer”部分的呢？这里就是课上提到的“投影下移”——直接在顺序扫描table的时候就提取所需的column(这里是column1、2)，而不用扫描完所有tuple后再做一次Project。

        而init()和next()两个函数到底该如何实现，我们可以先从next()的注释入手：next()返回一个生成的tuple。注意到，这里next()一次只能返回一个tuple，所以如果我们想要在next()内直接用for循环的方式遍历table是不可取的，这样难以记录当前访问的tuple的下标。再根据实验说明提到的“iter自增问题”，用迭代器遍历table的想法就应运而生了。每次next()内部获得新的tuple后，迭代器只需要自增1就可以满足记录到底访问到table的什么位置了。至于在哪里初始化这个迭代器，自然而然就可以想到init()了。显然，SeqScan只需要调用一次init()，调用sizeof(table)次next()。

更具体地说，完成SeqScan可以分为两步走：

1. Init 方法首先获取要扫描的表的堆（table_heap_），然后创建一个迭代器 iter来遍历这个堆。它遍历堆中的所有记录，并将它们的记录标识符（RID）存储在rids_列表中。最后，它将rid_iter_设置为rids_列表的起始位置。
2. Next方法用于从表中检索下一个满足条件的元组。它使用一个do-while循环来遍历rids_ 列表中的 RID。对于每个 RID，它首先获取该 RID 对应的元组的元数据（TupleMeta）。如果该元组没有被删除（!meta.is_deleted_），则将该元组复制到传入的 tuple参数中，并将 RID 复制到rid参数中。

        然后，它检查是否有过滤条件（plan_->filter_predicate_）。如果有，它会评估这个过滤条件，并检查结果是否为 true。只有当元组没有被删除且满足过滤条件时，do-while 循环才会结束。

2. 插入（Insert）

老样子我们先看看insert_executor的具体查询计划

可以看到insert_executor是拥有一个child_exector的，这个child类型是“Value_executor”。没错，就是实验说明三个实例之一的那个Value。其次，从insert_executor的实验说明可以看到它的next()函数输出并不和SeqScan一样，它会输出“一个整数元组，表示成功插入的行数”。那就是说我们直接在next()内部执行这个插入就可以了，insert_executor的next()只需要执行一次，将child_executor包含的几个value插入完毕后就可以返回了。

但是，还要注意插入values成功后，还要及时更新索引。有一说一，这里索引出现得有点突兀。举个例子，我们刚才创建的表t1在第一列(v1)有一个可扩展哈希索引，就是Project 2实现的可扩展哈希表。显然，我们需要把表t1所有的tuple都放进可扩展哈希表索引中， v1这列的值进行hash()后就作为索引的key，整个tuple作为索引的value。

所以在插入了新的tuple后，我们很自然地就需要为可扩展哈希表也添加这个新的元素，想办法怎么联系到可扩展哈希表的Insert(const K &key, const V &value, Transaction *transaction)。具体可以看那张总体函数调用流程图。

分享几个我在实现insert时想到的几个问题

Q：如果在进行插入的时候，发现当前table page已经满了，哪里会处理table page++这个操作呢？

A：table_heap内的InsertTuple()会处理。

Q：感觉insert会调用seq_scan知道找到一个空的slot，那应该如何实现这点呢？

A：同样InsertTuple()会处理。

Q：索引的类型是什么呢？

A：稠密索引，即为每个tuple都生成一个索引。其实我们在Project 2实现的可扩展哈希表也是稠密索引，因为我们把每个tuple都插入到哈希表中了。

3. 更新（Update）

        老样子先看update_executor的执行计划，我们发现它和insert_executor的执行计划差不多。它也有一个child_executor，child的类型也是SeqScan。这里如果还是对update这个操作感到疑惑，可以直接去看看测试点15445/test/sql里面的测试语句。自己将这些语句复制到官方提供的shell中跑一遍，通过explain看看执行计划到底是怎么样的。

        Update的next()也是只执行一次——“返回一个整数，表示更新的行数”。在更新tuple的时候，我们要注意更新的方式是“先删除旧的tuple，再插入新的tuple”。至于删除tuple的方式很简单，修改改tuple的TupleMeta即可。对索引的更新同样如此“先在哈希表中删除这个tuple，再向哈希表中插入新的tuple”。

4. 删除（Delete）

        通过观察这个Delete_executor的执行计划，我们还可以发现一点——可以将filter下移与SeqScan结合，直接在顺序扫描table的同时提取符合predicate的元素就可以了。

        Delete_executor的实现和insert、update类似，就是它要更为简洁一些。找到符合predicate的tuple后，将其TupleMeta的is_deleted置为true即可。同时记得删除这个tuple在哈希表中的内容。

 5. IndexScanExecutor（Index）

它来了它来了，期待已久的index终于来了。乍一看还是两眼一黑的状态，这时不妨先结合测试点进行一番debug看看执行过程。

        我们可以发现IndexScan也是没有child_executor的，因为它本质是SeqScan的变体。利用索引来快速查找符合filter的tuple，参考利用Project 2的可扩展哈希表进行快速查找。值得一提的是，由于官方提供的shell版本是最新的，所以在官方shell中显示的索引类型是BplusTree。

        要完成这次的task，得多看几遍实验说明了，我大致总结了下：

• 先用htable_ = dynamic_cast<HashTableIndexForTwoIntegerColumn *>(index_info_->index_.get());来生成索引
• 然后，你可以使用哈希索引进行点查找，查找满足谓词的元组，并将这些元组逐个发出。BusTub 只支持具有单一整数列的索引。我们的测试用例不会插入重复的键值。因此，点查找只会返回一个元组（如果存在）。
• 提示：在查询时，我们不会插入具有重复键的行。
• 你还需要确保不会发出已删除的元组。

        在完成索引扫描后，我们会发现执行计划依然没有从SeqScan更正为IndexScan，原因是我们还没有完成优化规则。

6. 优化顺序扫描为索引扫描（SeqScan → IndexScan）

这部分也没什么好讲解的，主要是读懂实验说明部分。

1. 启用谓词下推到 SeqScan：
   • 我们可以在 SeqScanExecutor 中实现谓词过滤，以便稍后索引扫描节点可以得到该谓词。优化器规则 MergeFilterScan 已经在启动时提供，你只需要确保该规则正常工作。
2. 使用索引：
   • 你可以检查谓词中的过滤列。如果该列上存在索引，那么创建 IndexScanPlanNode。要获得满分，你只需要支持针对索引列上的单一相等谓词的优化（例如：WHERE v1 = 1）。查询 SELECT * FROM t1 WHERE v1 = 1 AND v2 = 2 应该仍然使用 SeqScan，因此你不需要拆分谓词。

        而且光分析起来就显得罗里吧嗦，直接上代码。

auto Optimizer::OptimizeSeqScanAsIndexScan(const bustub::AbstractPlanNodeRef &plan) -> AbstractPlanNodeRef {// TODO(student): implement seq scan with predicate -> index scan optimizer rule// The Filter Predicate Pushdown has been enabled for you in optimizer.cpp when forcing starter rulestd::vector<AbstractPlanNodeRef> children;for (const auto &child : plan->GetChildren()) {children.emplace_back(OptimizeSeqScanAsIndexScan(child));}auto optimized_plan = plan->CloneWithChildren(std::move(children));// 尝试将seqScan转化为indexScanif (optimized_plan->GetType() == PlanType::SeqScan) {// 将当前plan转化为seq_planconst auto &seq_plan = dynamic_cast<const SeqScanPlanNode &>(*optimized_plan);//如果seq没有filter_predicate, 那就是将整个table传上去, 也没必要用到索引if (seq_plan.filter_predicate_ != nullptr) {auto table_info = catalog_.GetTable(seq_plan.table_oid_);auto table_indexes = catalog_.GetTableIndexes(seq_plan.table_name_);// 如果filter_pre是一个逻辑谓词 例如v1 = 1 AND v2 = 2, 则直接返回, 因为bustub的索引都是单列的, 两者不可能匹配if (auto tmp = dynamic_cast<LogicExpression *>(seq_plan.filter_predicate_.get());tmp != nullptr && table_indexes.empty()) {return optimized_plan;}// 这个filter_pri实际上是一个compExpr 例如where v1=1auto filter_comp_expr = dynamic_cast<ComparisonExpression *>(seq_plan.filter_predicate_.get());if (filter_comp_expr != nullptr && filter_comp_expr->comp_type_ == ComparisonType::Equal) {// 提取filter_pre中的列名auto filter_colval_expr = dynamic_cast<ColumnValueExpression *>(filter_comp_expr->children_[0].get());if (filter_colval_expr == nullptr) {  // 其实到这一步基本不可能出问题了return optimized_plan;}std::vector<uint32_t> filter_colval_expr_ids{filter_colval_expr->GetColIdx()};  // 装模作样把一个元素塞进vector里// 开始判断filter_pre和索引的关系for (const auto &index : table_indexes) {auto index_columns = index->index_->GetKeyAttrs();if (index_columns == filter_colval_expr_ids) {auto pred_key = dynamic_cast<ConstantValueExpression *>(filter_comp_expr->children_[1].get());return std::make_shared<IndexScanPlanNode>(optimized_plan->output_schema_, table_info->oid_,index->index_oid_, seq_plan.filter_predicate_, pred_key);}}}}}return optimized_plan;
}

        需要注意的一点是，这次需要设置next(tuple,rid)中的tuple和rid，不能向前几个一样只是设置了tuple而没有管rid，不然就会报错。

        有一说一这花花绿绿的配色还挺好看，嘻嘻~

Task #2 - Aggregation & Join Executors

Aggregation

        我个人感觉要完成这个task，重中之重是理解那几个expression类。在充分理解了expression后，就可以着手对aggregation_executor进行分析了。

        先看aggregation_executor的执行计划，我们需要重点关注的就是types(聚合操作的类型)、aggregates(聚合操作针对的列)和group by(基于哪一列进行分组)。显然，这次我们还是需要用到column_expr.evaluate()来提取某个tuple中对应的列值。

        正如实验说明里提到的，aggregations操作是pipeline breakers，即我们不能一边从child_executor中获得tuple，一边对这些tuple进行聚合操作。相反，聚合函数需要先从其子节点获取所有相关的数据，完成整个聚合计算过程（例如计算总和、平均值、最小/最大值等），然后才能产生输出结果。综上，我们可以将遍历child_executor和聚合操作都放在init()中实现。在next()进行对聚合哈希表的遍历即可。

        对于哈希表的使用，可以归纳为以下几个步骤:

1. 在child_executor中提取一个tuple
2. 在tuple中，提取group by(col_expr类型)对应的列组成values1，用values1构造一个AggregateKey，即哈希表的key，这也正是MakeAggregateKey()的作用。注意，group by可能由不止一个attribute组成。
3. 在tuple中，提取aggregates(col_expr类型)对应的列组成values2，用values2构造一个AggregateValue，即哈希表的value，这是正是MakeAggregateValue()的作用。Aggregates的个数和聚合函数的个数是一一对应的。
4. 将{AggregateKey，AggregateValue}插入到哈希表中进行聚合运算，并将结果存储起来。

        这个task的重难点就是完成哈希表的操作，理解了上面那个过程就可以较为轻松完成了。最后，还会遇到一个比较奇怪的测试。如果这个table是空的，但是聚合函数只有count(*)，最终结果还是要输出0，而不是什么都不输出。但是，在table为空的情况下，如果聚合函数有count(*)和max(cloA)等其他聚合函数，那就是输出空值。

NestedLoopJoin

        像这里的predicate本质是一个comparison_expression，它有两个child。Child[0]是一个col_expr(col0)，child[1]也是个col_expr(col2)。

        这个task感觉没啥好说的，就是对各种expression的运用，一开始已经分析过了，就不再赘述。实验说明里面的一句话说的就是这个意思。

        我们需要注意的一点是，存在这样一种情况：左表的某个tuple，在右表有多个匹配的tuple，就像下面这种错误。

        这里讲讲什么时候用自身的OutputSchema()、什么时候用child-> OutputSchema()吧。

        一般来说，在next()中用values来构造输出的tuple时需要用到自身的output_schema；当我们用相关的expr提取tuple的某一列值时，用到的就是child的output_schema。因为像predicate、group by等等列col_Expr集合，他们都是作用于从child_executor中提取出来的tuple，所以这个tuple的初始类型就是child的output_schema。