谈谈关系数据库的设计与实现(4)——执行器

pedrogao大约 8 分钟

执行器

前面的两个小节中，分别介绍了缓存池组件以及支持存储引擎的 B+树，本节的主角是执行器。

数据库系统从客户端接收到 SQL 语句后，对语句解析、优化并得到该语句的「查询计划」，而执行器的作用就是按照查询计划来执行查询操作。

这里的查询操作，并不单单指数据查询，它包括如下几类操作：

访问、查询，如表遍历，记录查询等；
更改，如数据更新、插入、删除等；
其它，如 Limit、Offset、聚合函数，Join 等；

注意：bustub 中不会实现 SQL 解析器、优化器，这里也不做介绍。

处理模型

「处理模型」规定了执行器如何去执行查询计划。常见的处理模型有：

Iterator Model(迭代器模型)
Materialization Model
Vectorized / Batch Model(批处理模型) bustub 实现了迭代器模型，其核心思想是：每一个执行器都实现 Next 方法。
每次调用 Next 方法，执行器都会返回一条数据记录(Tuple)，如果没有则返回空；
执行器可以拥有子执行器，父执行器在 Next 被调用时可以调用子执行器的 Next 方法，获取子执行器数据记录后，进一步处理返回。 bustub 通过 ExecutionEngine 类实例来执行查询计划，并获取查询结果，其定义如下：

class ExecutionEngine {
 public:
  // ...
  bool Execute(const AbstractPlanNode *plan, std::vector<Tuple> *result_set, Transaction *txn,
               ExecutorContext *exec_ctx) {
    // construct executor
    auto executor = ExecutorFactory::CreateExecutor(exec_ctx, plan);
    // prepare
    executor->Init();
    // execute
    try {
      Tuple tuple;
      RID rid;
      while (executor->Next(&tuple, &rid)) {
        if (result_set != nullptr) {
          result_set->push_back(tuple);
        }
      }
    } catch (Exception &e) {
    }
    return true;
  }
  // ...
}

ExecutionEngine 对外只暴露一个 Execute 方法，该方法接收四个参数：

plan：查询计划；
result：数据记录容器；
txn：当前查询事务；
exec_ctx：执行上下文。 AbstractPlanNode 是所有执行计划的父类，可用来表示所有类型的执行计划，通过调用 ExecutorFactory::CreateExecutor 方法可根据 plan 类型来生成对应的执行器，然后初始化该执行器，并不断调用 Next 方法来获取所有符合条件的数据记录(Tuple)。

执行计划

为了支持各类查询计划(比如 select 查询计划)，bustub 定义了 AbstractPlanNode 作为所有查询计划的父类，其定义如下：

class AbstractPlanNode {
 public:
  // ...
  AbstractPlanNode(const Schema *output_schema, std::vector<const AbstractPlanNode *> &&children)
      : output_schema_(output_schema), children_(std::move(children)) {}
  virtual ~AbstractPlanNode() = default;
  // ...
/ 
 private:
  // 数据表范式
  const Schema *output_schema_;
  // 子查询计划
  std::vector<const AbstractPlanNode *> children_;
};

AbstractPlanNode 类有两个重要字段：

output_schema_：数据表范式(定义)，查询数据组织方式，如：a int, b bool；
children_：子查询计划列表；每一类查询(如全表扫描)计划都有一个对应的查询计划类，以全表扫描的 SeqScanPlanNode 为例：

class SeqScanPlanNode : public AbstractPlanNode {
 public:
  SeqScanPlanNode(const Schema *output, const AbstractExpression *predicate, table_oid_t table_oid)
      : AbstractPlanNode(output, {}), predicate_{predicate}, table_oid_(table_oid) {}
  
  PlanType GetType() const override { return PlanType::SeqScan; }
   
  const AbstractExpression *GetPredicate() const { return predicate_; }
   
  table_oid_t GetTableOid() const { return table_oid_; }
 private:
  // 谓词
  const AbstractExpression *predicate_;
  // 数据表 id
  table_oid_t table_oid_;
};

SeqScanPlanNode 表示全表扫描查询计划，即 SQL 中的 select 语句，其核心字段有两个：

predicate_：断言，也可理解为查询条件，如 where id > 1；
table_oid_：数据表 id，用来唯一标识一张表，即对哪张表进行全表扫描。全表扫描查询计划保存了当前查询的表 id、查询条件等，那么该查询计划又是如何被执行器执行的呢？

无独有偶，与查询计划一样，所有执行器也有一个公共父类 AbstractExecutor：

class AbstractExecutor {
 public:
  explicit AbstractExecutor(ExecutorContext *exec_ctx) : exec_ctx_{exec_ctx} {}

  virtual ~AbstractExecutor() = default;

  virtual void Init() = 0;

  virtual bool Next(Tuple *tuple, RID *rid) = 0;

  virtual const Schema *GetOutputSchema() = 0;

  ExecutorContext *GetExecutorContext() { return exec_ctx_; }
 protected:
  ExecutorContext *exec_ctx_;
};

AbstractExecutor 有且只有一个核心字段 exec_ctx_，即执行器上下文。执行器上下文上保存了执行器所需的环境、数据等信息，如：

缓冲池管理器(BufferPoolManager)：执行器需访问数据页；
目录(Catalog)：存储表、索引元数据；
等等。 AbstractExecutor 还定义了执行器的基本方法 Init、Next 等，ExecutionEngine 就是通过 Next 方法来获取数据记录的。

因此任何一个执行器，其核心其实都是 Next 方法，仍以全表扫描为例，其核心实现如下：

SeqScanExecutor::SeqScanExecutor(ExecutorContext *exec_ctx, const SeqScanPlanNode *plan)
    : AbstractExecutor(exec_ctx), plan_(plan) {
  table_metadata_ = exec_ctx->GetCatalog()->GetTable(plan->GetTableOid());
}

void SeqScanExecutor::Init() {
  table_iterator_ = std::make_unique<TableIterator>(table_metadata_->table_->Begin(exec_ctx_->GetTransaction()));
}

bool SeqScanExecutor::Next(Tuple *tuple, RID *rid) {
  Tuple tup;
  do {
    // 到末尾了，直接返回
    if (*table_iterator_ == table_metadata_->table_->End()) {
      return false;
    }
    tup = *(*table_iterator_);  // 得到当前 tuple
    ++(*table_iterator_);       // 下一个
  } while (plan_->GetPredicate() != nullptr &&
           // 执行
           !plan_->GetPredicate()->Evaluate(&tup, &(table_metadata_->schema_)).GetAs<bool>());
  // 一个 Tuple 是一条记录，values 是字段值，schema 是字段名称
  std::vector<Value> values;
  std::transform(plan_->OutputSchema()->GetColumns().begin(), plan_->OutputSchema()->GetColumns().end(),
                 std::back_inserter(values), [&tup, &table_metadata_ = table_metadata_](const Column &col) {
                   // Column 是数据列，即字段的定义，调用 Evaluate 获取列数据
                   return col.GetExpr()->Evaluate(&tup, &(table_metadata_->schema_));
                 });
  // 赋值
  *tuple = Tuple{values, plan_->OutputSchema()};
  *rid = tup.GetRid();
  return true;
}

SeqScanExecutor 构造函数、Init 方法分别用来初始化表元数据、表迭代器。其核心 Next 方法主要流程如下：

判断迭代器是否结束，若结束，返回 false；
迭代器++，若查询谓词为空，或者当前表记录(Tuple)满足查询条件(Predicate)，那么结束 while 循环，否则迭代器继续 ++；
将表字段数据(Value)按照执行计划上的表范式(output_schema)包装为表记录(Tuple)返回。不同的查询计划对应不同的执行器，bustub 通过 ExecutionEngine、AbstractExecutor 和 AbstractPlanNode 巧妙将其解耦；执行器执行时从上下文中获取查询所需的环境、数据等信息，然后通过谓词判断记录是否符合查询条件，若符合则取出值，并包装为表记录返回给执行引擎。

执行器运行流程图如图 20 所示：

图 20

当然，bustub 有多种查询计划、执行器，如下：

./src/execution
├── aggregation_executor.cpp
├── delete_executor.cpp
├── executor_factory.cpp
├── index_scan_executor.cpp
├── insert_executor.cpp
├── limit_executor.cpp
├── nested_index_join_executor.cpp
├── nested_loop_join_executor.cpp
├── seq_scan_executor.cpp
└── update_executor.cpp

全表扫描仅仅只是其中最简单的一种，得益于 bustub 精妙的抽象，我们只需实现一个简单的执行器就能领略到数据库执行器的风采，篇幅有限，其它执行器的实现这里就不再赘述了，感兴趣的可以点开参考资料查阅。

参考资料

Database System Concepts 12
PROJECT #3 - QUERY EXECUTIONopen in new window
Query Execution Iopen in new window
Query Execution IIopen in new window

谈谈关系数据库的设计与实现(4)——执行器

# 执行器

# 处理模型

# 执行计划

# 参考资料

执行器

处理模型

执行计划

参考资料