Cmu15445 Query Execution

huazi included in CMU

2024-12-20 6803 words 14 minutes

Contents

Query Execution

在这次项目中，将实现允许 BusTub 执行查询的组件。具体是创建执行 SQL 查询的运算符执行程序，并实施优化器规则来转换查询计划。

BusTub的架构如下：

BusTub支持EXPLAIN命令打印查询的执行计划，比如：

EXPLAIN的结果中展示了查询处理层的转换过程。该语句首先有Parser和Binder处理，后者生成表示查询的抽象语法树（AST）。在这个例子中，查询由 __mock_table_1 上的 BoundSelect 表示，该 BoundSelect 将检索两列（colA 和 colB）。注意Binder 会自动将原始 SQL 查询中的 * 字符扩展到表中的实际列。
接下来，Binder AST由Planner处理，将生成适当的查询计划。这个例子中，查询计划是一个包含两个节点的树，数据从叶子流向根。
之后，优化器（Optimizer）将会优化查询计划，他会删除冗余的投影。

接下里考虑一个更复杂的例子：这里经过优化器优化后的查询计划为：

注意

在开始之前，先对System Catalog有一个了解。数据库维护一个内部目录来跟踪关于数据库的元数据。在本项目中，你将与系统编目交互，以查询有关表、索引及其架构的信息。

对于表修改执行器（InsertExecutor、UpdateExecutor和DeleteExecutor），必须修改操作所针对的表的所有索引。你会发现Catalog：：GetTableIndexes（）函数可以查询为特定表定义的所有索引。一旦为每个表的索引创建了IndexInfo实例，就可以对基础索引结构调用索引修改操作。在这个项目中，将使用你在项目#2中实现的哈希表索引作为所有索引操作的底层数据结构。
BusTub优化器是一个基于规则的优化器。大多数优化器规则以自底向上的方式构造优化计划。由于查询计划具有此树结构，因此在将优化器规则应用于当前计划节点之前，需要首先将规则递归地应用于其子节点。在每个计划节点，你应确定源计划结构是否与你尝试优化的计划结构匹配，然后检查该计划中的属性，以查看是否可以将其优化为目标优化计划结构。（仓库中已经提供了几个优化器规则的实现，提前看一下作为参考。）

Access Method Executors

此次任务，将要实现对存储系统中的表进行读取和写入的执行程序, 下面将依次介绍每一个执行程序。

SeqScan

SeqScanPlanNode 可以使用 SELECT * FROM table 语句进行规划。 SeqScanExecutor 迭代一个表，并一次返回一个 Tuples。

Hint:

不要输出在 TableHeap 中删除的元组。检查每个元组对应 TupleMeta 的 is_deleted_ 字段。

顺序扫描的输出是每个匹配的元组及其原始记录标识符（RID）的副本。

构造函数中能赋值的赋值。**Init()**中获取table_heap（table的oid在plan_中），用table_heap的MakeIterator()创建迭代器，用迭代器遍历，记录下所有的RID。
Next(Tuple *tuple, RID *rid)。遍历记录好的RID们，对应的tuple本身和tuplemeta都可以通过table_heap获取，若meta中显示没被删除，则赋值给参数中的tuple和rid作为返回值。
循环的判断条件注意要加上filter评估的结果转换为bool类型，若是最后一个rid也过去了就return false，否则return true。

1
2
3
4
5
6
7
8


  do {
    ...
  } while (meta.is_deleted_ ||
           (plan_->filter_predicate_ != nullptr &&
            !plan_->filter_predicate_
                 ->Evaluate(tuple, GetExecutorContext()->GetCatalog()->GetTable(plan_->GetTableOid())->schema_)
                 .GetAs<bool>()));
  return true;

Insert

可以使用 INSERT 语句来规划 InsertPlanNode。请注意，你需要使用单引号来指定 VARCHAR值。

InsertExecutor将Tuples插入表中并更新受影响的索引。它只有一个子项就是生成要插入到表中的值。Planner确保这些值与表有相同的架构。Executor 将生成一个整数类型的 Tuples 作为输出，指示已插入到表中的行数。如果有与之关联的索引，请记住在插入表时更新索引。

Init()，先对child_executor_执行初始化，然后将has_isnerted_设置为false，来避免halloween problem。（包括后面的执行器也都需要这一步）
Next(Tuple *tuple, RID *rid)，先判断has_inserted如果为true，说明已经插入过了，直接返回false。否则置为true然后开始插入。获取需要用到的table_info、schema、indexes，并初始化一个count来记录插入行数。
从子执行器child_executor_ 中逐个取出元组并插入到表中，同时更新所有的索引。利用InsertTuple返回得到的new_rid，遍历indexes中的每个索引类型，先用tuple->KeyFromTuple拿到key，然后用index_->InsertEntry更新索引。
根据要求，用count构造一个tuple返回。

1
2
3


  std::vector<Value> result = {{TypeId::INTEGER, count}};
  *tuple = Tuple(result, &GetOutputSchema());
  return true;

Update

UpdatePlanNode 可以使用 UPDATE 语句进行规划。它只有一个子项，其中包含表中要更新的记录。

UpdateExecutor修改指定表中的现有元组。执行器将生成一个整数类型的元组作为输出，指示有多少行被更新。请记住更新受更新影响的任何索引。要实现更新，首先删除受影响的元组，然后插入一个新的元组。

前两步与insert相同。每次从子执行器得到的元组，先删除再插入。
删除的操作是UpdateTupleMeta(TupleMeta{0, true}, *rid)把meta更新一下就可以了，然后还要删除对应的索引，用DeleteEntry。
再插入之前，先要计算表达式，得到更新后的值，然后再执行插入，与insert相同。

1
2
3
4
5


    // update: compute expressions
    std::vector<Value> new_values{};
    for (auto &expr : plan_->target_expressions_) {
      new_values.push_back(expr->Evaluate(tuple, child_executor_->GetOutputSchema()));
    }

Delete

DeletePlanNode可以用一个SQL语句来规划。它正好有一个子节点，该子节点具有要从表中删除的记录。

DeleteExcutor应该生成一个整数输出，表示从表中删除的行数。它还需要更新任何受影响的索引。要删除一个元组，你需要从子执行器获取一个RID，并更新该元组对应的TupleMeta的is_deleted_field。

同理update的删除部分的逻辑。

IndexScan

IndexScanExecutor使用散列索引进行点查找，以检索元组的RID。然后操作员使用这些RID在相应的表中检索它们的元组。然后它每次发出一个元组。计划中索引对象的类型在此项目中将始终为 HashTableIndexForTwoIntegerColumn 。你可以安全地将其转换并存储在executor对象中：

1

htable_ = dynamic_cast<HashTableIndexForTwoIntegerColumn *>(index_info_->index_.get())

你可以使用散列索引进行点查找，从表堆中查找元组，并根据谓词输出正确的元组。BusTub仅支持具有单个唯一整数列的索引。我们的测试用例不会包含重复的键。因此，点查找只返回一个元组，如果它存在。不要发出已删除的元组。

**Init()**的时候，用上面说的，获取htable_存储在executor中。
Next()：利用htable_的ScanKey方法搜索，若返回结果为空，说明没有这个索引，直接返回false，否则从table_heap中拿到这个元组查看meta中的is_deleted_，若没被删除就正常返回。

Optimizing SeqScan to IndexScan

当我们查询索引列时，使用IndexScan将显著提高查找性能。为此，我们需要将过滤器下推到扫描器中，以便我们知道在索引中查找的键。然后我们可以直接通过索引检索值，而不是进行全表扫描或索引扫描。

这里需要修改优化器，以便在可能的情况下将SeqScanPlanNode转换为IndexScanPlanNode。如执行bustub> EXPLAIN (o) SELECT * FROM t1 WHERE v1 = 1;，不应用MergeFilterScan和SeqScan as IndexScan优化器规则，计划可能如下所示：

在应用MergeFilterScan和SeqScan as IndexScan优化器规则之后，我们可以只做一个快速的索引查找，而不是迭代整个表。生成的计划如下所示：

执行之前，递归的优化子节点。

1
2
3
4


  for (const auto &child : plan->GetChildren()) {
    optimized_children.emplace_back(OptimizeSeqScanAsIndexScan(child));
  }
  auto optimized_plan = plan->CloneWithChildren(std::move(optimized_children));

如果optimized_plan->GetType()等于PlanType::SeqScan，开始执行优化。获取计划的谓词，如果谓词为空仍然执行顺序扫描。
判断其是否为条件谓词中的等值条件ComparisonType::Equal，只有等值条件这里才转化为索引扫描。
根据谓词的列，获取索引信息col_index。遍历indexes，如果index_->GetKeyAttrs()取出的列与col_index相同，表示存在相关索引，构建IndexScanPlanNode并用智能共享指针来管理，返回。

Aggregation & Join Executors

Aggregation

AggregationPlanNode用于支持以下查询: 聚合执行器为每组输入计算聚合函数。它只有一个孩子。输出架构由group-by列和聚合列组成。实现聚合的一个常见策略是使用哈希表，并将group-by列作为键。

在本项目中，你可以假设聚合哈希表适合内存。这意味着你不需要实现基于分区的多级策略，并且哈希表不需要由缓冲池页支持。我们提供了一个SimpleAggregationHashTable数据结构，它公开了一个内存中的哈希表（std：：unordered_map），但带有一个为计算聚合而设计的接口。这个类还公开了一个 Iterator类型，可用于遍历哈希表。你需要完成此类的CombineAggregateValues函数。

Hint中提到，聚合是pipeline breakers，意味着在流水线中，聚合会中断数据流处理的过程。你会希望Init()中尽可能多地做准备工作，因为聚合往往需要看到所有相关的输入行才能正确地生成最终的结果。

在实现aggregation之前需要先把哈希表完善一下。主要是CombineAggregateValues，将输入的聚合值与结果聚合值进行合并：遍历所有聚合表达式。根据不同的聚合类型（如计数、求和、最小值、最大值等），对每个聚合值进行相应的操作。
Init()：子执行器初始化，根据plan_的信息创建SimpleAggregationHashTable。遍历子执行器，将子执行器中的获取的数据插入到聚合哈希表中，不能在聚合执行器中完成，因为聚合执行器需要先从子执行器中获取所有数据，然后对这些数据进行分组和聚合操作，最后才能产生输出结果。具体来说，对每一个元组，执行MakeAggregateKey和MakeAggregateValue获取key和value，再InsertCombine到AHT里。
Next()：利用Iterator遍历AHT，如果有groupby的话就创建一个vector<Value>，先把groupby都依次添加进去，然后把聚合值依次添加进去，用这个vector构造tuple返回。groupbys为空，则生成一个初始的聚合值元组返回。

NestedLoopJoin

默认情况下，DBMS将对所有连接操作使用NestedLoopJoinPlanNode。考虑以下示例查询：

你需要使用类中的简单嵌套循环连接算法为NestedLoopJoinExecutor实现内部连接和左连接。该操作符的输出模式是左表中的所有列，后面跟着右表中的所有列。对于外部表中的每个元组，考虑内部表中的每个元组，如果满足连接谓词，则发出输出元组。

左连接：返回左表中的所有记录，如果右表中没有匹配的记录，就用NULL表示。

内部连接：仅返回两个表中有匹配的结果行。

Init()：初始化左右两个子执行器。
Next()：（这里解释左连接，内部连接类似）对于每个左表中的元组，遍历右表，用谓词的EvaluateJoin来判断是否匹配，若匹配成功，创建一个values，把左元组每一列的值添加进去，再把右元组每一列的值添加进去，用这个values构造一个tuple，返回。
若是遍历完右表没找到，则用NULL代替右元组的值。

1

ValueFactory::GetNullValueByType(right_executor_->GetOutputSchema().GetColumn(i).GetType());

HashJoin Executor and Optimization

在开始此任务之前，你需要在任务#2中实现NestedLoopJoinExecutor。

HashJoin

如果一个查询包含一个两列之间有多个等价条件的连接（等价条件由AND分隔），DBMS可以使用HashJoinPlanNode。考虑以下示例查询：

你需要使用类中的散列连接算法为HashJoinExecutor实现内部连接和左连接。与聚合一样，哈希连接的构建端是pipeline breaker。你需要一种方法来散列一个具有多个属性的元组，以构造一个唯一的键，参考SimpleAggregationHashTable。

Init()：初始化左右两个子执行器，遍历右表执行器，把每个元组插入到自己的哈希表里。
Next()：遍历左表执行器，对每个元组，通过左表的key，在哈希表GetValue到所有右表中匹配的元组，然后用和NestedLoopJoin中相同的操作构造tuple并返回。

Optimizing NestedLoopJoin to HashJoin

哈希连接通常比嵌套循环连接产生更好的性能。当连接谓词是两列之间的几个等价条件的合取时，可以使用哈希连接算法。对于这个项目，你应该能够处理不同数量的由AND连接的等价条件。

考虑这个例子：bustub> EXPLAIN (o) SELECT * FROM test_1 t1, test_2 t2 WHERE t1.colA = t2.colA AND t1.colB = t2.colC; 如果不应用NLJAsHashJoin优化器规则，计划可能如下所示：应用NLJAsHashJoin优化器规则后，将从NestedLoopJoinPlanNode中的单个连接谓词中提取左连接键表达式和右连接键表达式。生成的计划如下所示：

先写一个单独的函数用来解析and表达式，并提取出左右连接键表达式：如果逻辑表达式是and则递归解析两边的表达式。接下来判断是否是=表达式，用GetTupleIdx()区分哪个列属于哪个表后，将其添加到对应的键表达式中。
开始实现OptimizeNLJAsHashJoin，与之前优化器一样先对子执行器进行优化。然后检查当前plan_的类型是不是PlanType::NestedLoopJoin，是的话开始优化：获取谓词，用刚才的函数提取左右两侧键表达式，用得到的结果创建一个新的HashJoinPlanNode返回。

Sort + Limit Executors + Window Functions + Top-N Optimization

在开始此任务之前，您需要在任务#1中实现IndexScanExecutor。如果表上有索引，查询处理层将自动选择它进行排序。在其他情况下，您需要一个特殊的排序执行器来完成此操作。

Sort

除了ORDERBY属性与索引键匹配的情况外，BusTub将对所有ORDERBY运算符使用SortPlanNode。

此计划节点不会更改schema（即输出与输入schema相同）。您可以从order_bys中提取排序键，然后使用std::sort和自定义比较器对子对象中的所有元组进行排序。您可以假设表中的所有条目都可以容纳在内存中。

Init()：初始化子执行器，并创建一个Vector来子执行器输出的元组，使用std::sort排序。

1

  std::sort(tuples_.begin(), tuples_.end(), Comparator(&GetOutputSchema(), plan_->GetOrderBy()));

Next()：依次输出排序后的元组。

Limit

LimitExecutor约束其子执行器的输出元组的数量。如果其子执行器生成的元组数量小于计划节点中指定的限制，则此执行器无效，并生成它接收的所有元组。

Next()：每次输出的时候计数，到达plan_->GetLimit()后返回false。

Top-N Optimization Rule

修改BusTub的优化器以支持转换前N个查询。考虑以下查询：

EXPLAIN SELECT * FROM __mock_table_1 ORDER BY colA LIMIT 10;

默认情况下，BusTub将通过以下方式执行此查询：（1）对表中的所有数据进行排序（2）获取前10个元素。这显然是低效的，因为查询只需要最小的值。一个更聪明的方法是动态地跟踪到目前为止最小的10个元素。这就是BusTub的TopNExecutor所做的。想想什么数据结构可以用来跟踪前n个元素，小顶堆和大顶堆！。

所以需要修改优化器，以支持将带有ORDER BY + LIMIT子句的查询转换为使用TopNEutor。

Init()：用优先队列创建一个堆。遍历子执行器的元组，插入堆，如果当前堆的大小超过N，则弹出一个，最后保留的即为前N个，O(n*logN)

1
2
3


// 使用优先队列存储topN，升序用大顶堆（每次pop出来大的），降序用小顶堆
// 元素为Tuple，底层用vector存储，比较器为Comparator
std::priority_queue<Tuple, std::vector<Tuple>, Comparator> heap(Comparator(&GetOutputSchema(), plan_->GetOrderBy()));

对于优化器OptimizeSortLimitAsTopN，先判断如果plan_的类型是Limit，将其转换为LimitPlanNode来获取limit_的值，并获取plan_的第0个孩子，如果孩子的类型是Sort，就创建一个TopNPlanNode返回。

Window Functions

一般来说，窗口函数有三个部分：partition by、order by和window frames。这三个功能都是可选的，因此这些功能的多种组合使窗口功能一开始令人生畏。然而，窗口函数的概念模型有助于使其更容易理解。概念模型如下：* 根据partition by子句中的条件分割数据。* 然后，在每个分区中，按order by子句排序。* 然后，在每个分区（现在已排序）中，遍历每个元组。对于每个元组，我们计算该元组的框架的边界条件。每个帧都有一个开始和结束（由窗口帧的子句指定）。窗口函数是在每个帧中的元组上计算的，我们输出在每个帧中计算的结果。