数据库内核实验报告五：查询优化 2025.02.09 数据库

基础实现思路和难度总结

本次实验内容实现了查询重写和连接顺序优化的查询优化。

查询重写只涉及 分解复合选择谓词 下推选择运算 笛卡尔积转为连接运算

连接顺序优化以 贪心算法 为例

框架基本认识

本次实验只需修改optimizer.cpp 和 optimizer.h

对于查询优化而言，输入的为查询计划树，故先要了解查询计划树在框架中的数据结构。

查询计划操作 Operator

查询计划操作为查询计划的基本节点，一个Operator 作为基类，是构成查询计划树的主要组成部分，每个Operator作为节点，自然有 children_ 来记录孩子节点，其为空时，即为叶子节点；有左右孩子时，即连接操作。

对于以上枚举的所有操作种类，都设计了一个派生类，部分派生类有自己专属的成员，以下以几个基本的派生类作为例子介绍

enum class OperatorType {
  AGGREGATE,
  DELETE,
  FILTER,
  HASHJOIN,
  INSERT,
  LIMIT,
  LOCK_ROWS,
  MERGEJOIN,
  NESTEDLOOP,
  ORDERBY,
  PROJECTION,
  SEQSCAN,
  UPDATE,
  VALUES,
};

class Operator {
 public:
  Operator(OperatorType type, std::shared_ptr<ColumnList> column_list, std::vector<std::shared_ptr<Operator>> children)
      : type_(type), column_list_(std::move(column_list)), children_(std::move(children)) {}
  virtual ~Operator() = default;
  virtual std::string ToString(size_t indent_num = 0) const = 0;

  const ColumnList &OutputColumns() const { return *column_list_; }
  OperatorType GetType() const { return type_; }
  const std::vector<std::shared_ptr<Operator>> &GetChildren() const { return children_; }

  OperatorType type_;
  std::shared_ptr<ColumnList> column_list_;
  std::vector<std::shared_ptr<Operator>> children_;
};

筛选操作 FilterOperator

作为筛选操作，会有一个专属的predicate_即谓词，作为选择的条件，之后会介绍谓词表达式类。

class FilterOperator : public Operator {
 public:
  FilterOperator(std::shared_ptr<ColumnList> column_list, std::shared_ptr<Operator> child,
                 std::shared_ptr<OperatorExpression> predicate)
      : Operator(OperatorType::FILTER, std::move(column_list), {std::move(child)}), predicate_(std::move(predicate)) {}
  std::string ToString(size_t indent_num = 0) const override {
    return fmt::format("{}Filter: {}\\n{}", std::string(indent_num * 2, ' '), predicate_,
                       children_[0]->ToString(indent_num + 1));
  }

  std::shared_ptr<OperatorExpression> predicate_;
};

扫描读取表操作 SeqScanOperator

作为读取扫描表操作，自然需要记录扫描的表是谁，提供了GetTableNameOrAlias函数来获取扫描的表名。

class SeqScanOperator : public Operator {
 public:
  SeqScanOperator(std::shared_ptr<ColumnList> column_list, oid_t table_oid, std::string table_name,
                  std::optional<std::string> alias, bool has_lock)
      : Operator(OperatorType::SEQSCAN, std::move(column_list), {}),
        table_oid_(table_oid),
        table_name_(std::move(table_name)),
        alias_(std::move(alias)),
        has_lock_(has_lock) {}
  std::string ToString(size_t indent_num = 0) const override {
    if (alias_) {
      return fmt::format("{}SeqScan: {} {}", std::string(indent_num * 2, ' '), table_name_, *alias_);
    } else {
      return fmt::format("{}SeqScan: {}", std::string(indent_num * 2, ' '), table_name_);
    }
  }

  oid_t GetTableOid() const { return table_oid_; }
  const std::string &GetTableNameOrAlias() const {
    if (alias_) {
      return *alias_;
    } else {
      return table_name_;
    }
  }
  const std::string &GetTableName() const { return table_name_; }
  bool HasLock() const { return has_lock_; }

 private:
  oid_t table_oid_;
  std::string table_name_;
  std::optional<std::string> alias_;
  bool has_lock_;
};

连接操作 NestedLoopJoinOperator

需要一个连接的条件join_condition_，即一个条件表达式，当其为常量 true的时候，即笛卡尔积连接，所有连接情况都被允许通过。

class NestedLoopJoinOperator : public Operator {
 public:
  NestedLoopJoinOperator(std::shared_ptr<ColumnList> column_list, std::shared_ptr<Operator> left,
                         std::shared_ptr<Operator> right, std::shared_ptr<OperatorExpression> join_condition,
                         JoinType join_type = JoinType::INNER)
      : join_condition_(std::move(join_condition)),
        join_type_(join_type),
        Operator(OperatorType::NESTEDLOOP, std::move(column_list), {std::move(left), std::move(right)}) {}
  std::string ToString(size_t indent_num = 0) const override {
    return fmt::format("{}NestedLoopJoin: {}\\n{}\\n{}", std::string(indent_num * 2, ' '), join_condition_,
                       children_[0]->ToString(indent_num + 1), children_[1]->ToString(indent_num + 1));
  }
  std::shared_ptr<OperatorExpression> join_condition_;
  JoinType join_type_;
};

查询计划表达式 OperatorExpression

查询计划表达式一般属于一些操作，例如上面的选择操作。其也有多个子类。

不论是一条完整的表达式，还是一个单独的常量，都用OperatorExpression 基类可以代表。

对于一个完整表达式，即为多个OperatorExpression 嵌套，同时使用类型标识其属于常量还是表达式。

enum class OperatorExpressionType {
  AGGREGATE,
  ARITHMETIC,
  TYPE_CAST,
  COLUMN_VALUE,
  COMPARISON,
  CONST,
  FUNC_CALL,
  LIST,
  LOGIC,
  NULL_TEST
};

class OperatorExpression {
 public:
  OperatorExpression() = default;
  OperatorExpression(OperatorExpressionType expr_type, std::vector<std::shared_ptr<OperatorExpression>> children,
                     Type value_type, std::string name = "<no_name>", size_t size = 0)
      : expr_type_(expr_type),
        children_(std::move(children)),
        value_type_(value_type),
        name_(std::move(name)),
        size_(size) {}
  virtual Value Evaluate(std::shared_ptr<const Record> record) { throw DbException("Evaluate method not implemented"); }
  virtual Value EvaluateJoin(std::shared_ptr<const Record> left, std::shared_ptr<const Record> right) {
    throw DbException("EvaluateJoin method not implemented");
  }
  virtual std::string ToString() const { return "OperatorExpression"; }

  OperatorExpressionType GetExprType() const { return expr_type_; }
  Type GetValueType() const { return value_type_; }
  size_t GetSize() const { return size_; }
  void SetName(const std::string &name) { name_ = name; }

  OperatorExpressionType expr_type_;
  std::string name_;
  std::vector<std::shared_ptr<OperatorExpression>> children_;
  Type value_type_;
  size_t size_;
};

逻辑表达式 Logic

逻辑表达式会有 children_ 即用 逻辑关系AND, OR 连接的左右表达式，其中，本二元逻辑表达式的children_ 中只有两个对象，右对象可能是单个表达式也可能是再一个逻辑表达式，左对象可能是单个表达式也可能是再一个逻辑表达式，一个Logic只记录一个逻辑关系，通过不断嵌套，来做到多逻辑关系的逻辑表达式。

enum class LogicType { AND, OR, NOT };

class Logic : public OperatorExpression {
 public:
  Logic(LogicType logic_type, std::shared_ptr<OperatorExpression> arg)
      : OperatorExpression(OperatorExpressionType::LOGIC, {std::move(arg)}, Type::BOOL), logic_type_(logic_type) {
    assert(logic_type == LogicType::NOT);
  }

  Logic(LogicType logic_type, std::shared_ptr<OperatorExpression> left, std::shared_ptr<OperatorExpression> right)
      : OperatorExpression(OperatorExpressionType::LOGIC, {std::move(left), std::move(right)}, Type::BOOL),
        logic_type_(logic_type) {}

  Value Evaluate(std::shared_ptr<const Record> record) override {
    if (logic_type_ == LogicType::NOT) {
      return children_[0]->Evaluate(record).Not();
    } else {
      Value lhs = children_[0]->Evaluate(record);
      Value rhs = children_[1]->Evaluate(record);
      return Compute(lhs, rhs);
    }
  }

  Value EvaluateJoin(std::shared_ptr<const Record> left, std::shared_ptr<const Record> right) override {
    if (logic_type_ == LogicType::NOT) {
      return children_[0]->Evaluate(left).Not();
    } else {
      Value lhs = children_[0]->EvaluateJoin(left, right);
      Value rhs = children_[1]->EvaluateJoin(left, right);
      return Compute(lhs, rhs);
    }
  }

  std::string ToString() const override {
    if (logic_type_ == LogicType::NOT) {
      return fmt::format("{} {}", logic_type_, children_[0]);
    }
    return fmt::format("{} {} {}", children_[0], logic_type_, children_[1]);
  }
  LogicType GetLogicType() const { return logic_type_; }

 private:
  LogicType logic_type_;
  Value Compute(const Value &lhs, const Value &rhs) {
    if (lhs.IsNull() || rhs.IsNull()) {
      return Value();
    }
    switch (lhs.GetType()) {
      case Type::BOOL:
        return Value(DoOperation(lhs.GetValue<bool>(), rhs.GetValue<bool>()));
      default:
        throw DbException("Type unsupported for logic operation");
    }
  }

  bool DoOperation(bool lhs, bool rhs) {
    switch (logic_type_) {
      case LogicType::AND:
        return lhs && rhs;
      case LogicType::OR:
        return lhs || rhs;
      default:
        throw DbException("Unknown logic type");
    }
  }
};

查询重写

lab5/10-filter-pushdown.test

lab5/20-join-pushdown.test

分解复合的选择谓词

分解复合的选择谓词即将单个节点的长表达式 A and B 变成两个节点连接代替原节点，在原本查询树的基础上多了一个选择节点。

分解复合谓词有前提条件，即当前节点是选择节点，并且这个节点的表达式为AND逻辑，我们即可将表达式分割为两个，然后再分别用这两个表达式来创建出两个选择节点，让左的指向右的。再让右指向原来的孩子，再将原本指针指向左选择表达式节点。

需要注意的是，作为表达式，一次的分割可能不够，需要多次不断修改，故将得到的表达式递归即可。

为了遍历这一整个计划查询树，故在后面再遍历所有的子节点。使用的方式类似于DFS的递归。

std::shared_ptr<Operator> Optimizer::SplitPredicates(std::shared_ptr<Operator> plan) {
  if(plan->GetType() == OperatorType::FILTER){
    ptrFilter curFilter = std::dynamic_pointer_cast<FilterOperator>(plan);
    ptrExpr curExpr = curFilter->predicate_;
    if(curExpr->GetExprType() == OperatorExpressionType::LOGIC){
      ptrLogic curLogic = std::dynamic_pointer_cast<Logic>(curExpr);
      if(curLogic->GetLogicType() == LogicType::AND){
        ptrExpr leftExpr = curExpr->children_[0];
        ptrExpr rightExpr = curExpr->children_[1];
        
        std::shared_ptr<ColumnList> columns = std::make_shared<ColumnList>(plan->OutputColumns());

        ptrFilter rightFilter = std::make_shared<FilterOperator>(columns, plan->GetChildren()[0], rightExpr);
        ptrOP rightNode = SplitPredicates(rightFilter);
        ptrFilter leftFilter = std::make_shared<FilterOperator>(plan->column_list_, rightNode, leftExpr);
        ptrOP leftNode = SplitPredicates(leftFilter);
        plan = leftNode;
      }
    }
  }
  for(ptrOP &son: plan->children_){
    son = SplitPredicates(son);
  }

  return plan;
}

下推选择运算收集阶段

作为下推选择，实际上分为三步：

• 记录所有的选择谓词
• 再遍历下面子树中判断能将之前的选择谓词下推
• 遍历后判断这个选择谓词是否下推成功，若成功，删除本节点，若不成功不删除。

三步操作实际上就是再 递归前 递归中 递归后 的三部分编写即可。

不过要考虑到的是，这个步骤在分解复合的选择谓词之后，所以所有的选择节点的表达式都是单独的表达式，而不是逻辑表达式。

先判断谓词是否Comparison 类型：

选择谓词分为普通谓词和连接谓词，其区别在于表达式的类型。如果表达式左右两边都是COLUMN_VALUE类型，即例如 a.id = b.id，这就属于连接谓词。否则属于普通谓词。

作为下推选择运算，本函数只要考虑记录和判断是否删除节点即可。

使用 join_predicates 和 selection_predicates 来记录有哪些谓词，使用一个映射predicate_pushdown_status 来记录谓词是否下移成功。故第三部分就可以借助predicate_pushdown_status 来判断是否要删除

std::shared_ptr<Operator> Optimizer::PushDownFilter(std::shared_ptr<Operator> plan) {
  ptrFilter curFilter = std::dynamic_pointer_cast<FilterOperator>(plan);
  ptrExpr curExpr = curFilter->predicate_;

  if(curExpr->GetExprType() == OperatorExpressionType::COMPARISON){
    ptrExpr left = curExpr->children_[0];
    ptrExpr right = curExpr->children_[1];
    if (left->GetExprType() == OperatorExpressionType::COLUMN_VALUE 
    and right->GetExprType() == OperatorExpressionType::COLUMN_VALUE){
      join_predicates.push_back(curExpr);
    }else{
      selection_predicates.push_back(curExpr);
    }
    predicate_pushdown_status[curExpr] = false;
  }

  plan->children_[0] = PushDown(plan->children_[0]);

  if(predicate_pushdown_status[curExpr]){
    return plan->children_[0];
  }else{
    return plan;
  }
}

下推选择运算（普通谓词下推）

遇到扫描操作的时候就会执行这个函数，也就是我们实际下推谓词的时候，此时，如果记录的谓词符合当前扫描的标准，就用该谓词创建一个选择操作节点，再将这个节点插入这个扫描操作的上方即可。

ColumnValue 的 name_ 字段为 “table_name.column_name” 的形式，再借助扫描操作可以获取表的名字，通过比较table_name来判断能否下推该谓词到这个扫描，同时记录当前谓词已成功下移。

std::shared_ptr<Operator> Optimizer::PushDownSeqScan(std::shared_ptr<Operator> plan) {
  ptrScan curScan = std::dynamic_pointer_cast<SeqScanOperator>(plan);

  for(ptrExpr expr: selection_predicates){
    ptrExpr columnValue = expr->children_[0];

    std::string columnName = columnValue->name_;
    size_t pos = columnName.find('.');
    std::string tableName = columnName.substr(0, pos);

    std::string scanName = curScan->GetTableNameOrAlias();

    if(tableName == scanName){
      std::shared_ptr<ColumnList> column = plan->column_list_;
      ptrFilter newFilter = std::make_shared<FilterOperator>(column, plan, expr);
      plan = newFilter;
      predicate_pushdown_status[expr] = true;
    }
  }

  return plan;
}

至此10-filter-pushdown.test已通过。

下推选择运算（笛卡尔积转连接）（连接谓词下推）

和下推普通谓词类似，对于笛卡尔积转连接，只需要同样判断是否符合条件，一旦符合条件，就将该连接置于操作的join_condition_ ，即连接的条件。同时标记该连接谓词已使用。

std::shared_ptr<Operator> Optimizer::PushDownJoin(std::shared_ptr<Operator> plan) {
  for (auto &child : plan->children_) {
    child = PushDown(child);
  }

  ptrJoin curJoin = std::dynamic_pointer_cast<NestedLoopJoinOperator>(plan);
  if(curJoin->join_condition_->ToString() == "true"){
    for(ptrExpr expr: join_predicates){
      if(predicate_pushdown_status[expr]){
        continue;
      }
      std::string columnA = expr->children_[0]->name_;
      std::string columnB = expr->children_[1]->name_;

      if (curJoin->column_list_->TryGetColumnIndex(columnA) != std::nullopt
      and curJoin->column_list_->TryGetColumnIndex(columnB) != std::nullopt){
        curJoin->join_condition_ = expr;
        predicate_pushdown_status[expr] = true;
      }
    }
  }
  return plan;
}

至此，通过 20-join-pushdown.test 测试样例

连接顺序选择（贪心算法）

30-join-order.test

代价估计

贪心算法的实现基于代价估计，对于表的代价估计，基于表的统计，需要用到的有：

• T®：关系R的元组数目
• V(R,A)：关系R在属性A上不同值个数。当A扩展为属性集合a时，V(R,a)表示关系R在属性集a上投影后不同的元组数，即 Πa® 元组数

复习一遍需要知道的前提条件，基于贪心算法的连接顺序选择，连接的代价估计为连接之后T的大小，例如要连接Ra和Rb代价即T(Ra⋈Rb)

对于Ra和Rb在col上进行连接即 Ra.col = Rb.col，有以下：

T(Ra⋈Rb) = T(Ra) * T(Rb) / max(V(Ra, col), V(Rb, col))

同时更新其V，有以下：

V(Ra⋈Rb, col) = min(V(Ra, col), V(Rb, col))

贪心算法

步骤：

• 选择一个大小T最小的关系作为当前Rcur
• 从余下没有被选择过的关系中选择与Rcur连接后结果最小的Rnext，将Rcur更新为Rcur ⋈Rnext
• 不断重复步骤2，直到所有关系都被选择过。

其中，如果T相等，我们优先选择能连接选择最多的表。

实现

类似于图的性质，因此我们将表看做节点，通过tables映射来记录，通过递归的DFS来记录所有的表，同时记录所有的连接，连接即看做一条边，我们此时将一个连接计划变成了一个图，图中记录了边的情况，使用了邻接表的结构。

这段代码没有进行很深的优化，以展现算法思路为主。

使用collect DFS进行信息收集，收集所有的边，将原来的题目转化为一个图。

遍历一遍所有的table，通过T和边的数目来选择初始的表。

使用一个near来记录所有当前联通情况下的边，例如我已经连接了AB，那就把A的所有边和B的所有边记录下来。

使用一个visited来记录所有的表是否已经被连接。

使用curV和curT来记录当前连接情况下的T和V的情况，通过连接不断更新，同时更新指针结构，构建新的计划树。

• 选择起点
• 不断遍历能连接到的所有的表
• 找到连接代价最小的表
• 更新当前连接情况下的统计数据
• 更新当前连接计划树结构
• 回到第二步，直到所有表连接完

std::shared_ptr<Operator> Optimizer::ReorderJoin(std::shared_ptr<Operator> plan) {
  // 通过 catalog_.GetCardinality 和 catalog_.GetDistinct 从系统表中读取表和列的元信息
  // 可根据 join_order_algorithm_ 变量的值选择不同的连接顺序选择算法，默认为 None，表示不进行连接顺序优化
  using namespace std;

  map<string, ptrOP> tables;
  map<string, set<string>> colOfTable;
  map<pair<string, string>, ptrJoin> joins;
  map<string, vector<pair<string, string>>> edges;
  map<string, ptrJoin> col2Join;

  function<string(ptrOP)> getName = [&](ptrOP cur){
    if(cur->GetType() == OperatorType::SEQSCAN){
      ptrScan curScan = dynamic_pointer_cast<SeqScanOperator>(cur);
      return curScan->GetTableNameOrAlias();
    }else{
      return getName(cur->children_[0]);
    }
  };

  ptrOP PreOP = nullptr;

  function<void(ptrOP, ptrOP)> collect = [&](ptrOP cur, ptrOP par){

    if(cur->GetType() == OperatorType::NESTEDLOOP){
      if(PreOP == nullptr){
        PreOP = par;
      }
      ptrJoin curJoin = dynamic_pointer_cast<NestedLoopJoinOperator>(cur);
      ptrExpr curExpr = curJoin->join_condition_;

      string table1 = curExpr->children_[0]->name_;
      string table2 = curExpr->children_[1]->name_;
      size_t pos = table1.find('.');
      table1 = table1.substr(0, pos);
      pos = table2.find('.');
      string column = table2.substr(pos + 1);
      table2 = table2.substr(0, pos);

      tables[getName(curJoin->children_[1])] = curJoin->children_[1];
      joins[{table1, table2}] = curJoin;
      joins[{table2, table1}] = curJoin;
      edges[table1].push_back({table2, column});
      edges[table2].push_back({table1, column});
      colOfTable[table1].insert(column);
      colOfTable[table2].insert(column);
      col2Join[column] = curJoin;

      if(cur->children_[0]->GetType() == OperatorType::NESTEDLOOP){
        collect(cur->children_[0], cur);
      }else{
        tables[getName(curJoin->children_[0])] = curJoin->children_[0];
      }
    }
    if(cur->children_.size() > 0){
      collect(cur->children_[0], cur);
    }
  };

  if(join_order_algorithm_ == JoinOrderAlgorithm::GREEDY){
    collect(plan, nullptr);
    if(tables.empty()){
      return plan;
    }
    set<pair<string, string>> nears;
    ptrOP ptrCur = nullptr;
    int curT = 1e9;
    string minTable;

    map<string, int> curV;
    map<string, bool> visited;

    for(auto[table, op]: tables){
      visited[table] = false;
      if(catalog_.GetCardinality(table) < curT){
        curT = catalog_.GetCardinality(table);
        ptrCur = op;
        minTable = table;
      }
      if(catalog_.GetCardinality(table) == curT and edges[table].size() > edges[minTable].size()){
        curT = catalog_.GetCardinality(table);
        ptrCur = op;
        minTable = table;
      }
    }

    visited[minTable] = true;
    for(auto col: colOfTable[minTable]){
      curV[col] = catalog_.GetDistinct(minTable, col);
    }

    for(auto edge: edges[minTable]){
      nears.insert(edge);
    }
    
    while(true){

      bool all_connected = true;
      for(auto[table, _]:tables){
        if(not visited[table]){
          all_connected = false;
        }
      }
      if(all_connected){
        break;
      }

      int minCost = 1e9;
      string nextTableName;
      string nextCol;

      for(auto[table, col]: nears){
        if(visited[table]) continue;
        int T2 = catalog_.GetCardinality(table);
        int V2 = catalog_.GetDistinct(table, col);

        int cost = curT * T2 / max(V2, curV[col]);
        if(cost < minCost){
          minCost = cost;
          nextTableName = table;
          nextCol = col;
        }
      }
      curT = minCost;
      for(auto col:colOfTable[nextTableName]){
        if(curV.count(col)){
          curV[col] = min(curV[col], (int)catalog_.GetDistinct(nextTableName, col));
        }else{
          curV[col] = catalog_.GetDistinct(nextTableName, col);
        }
      }
      for(auto edge:edges[nextTableName]){
        nears.insert(edge);
      }
      ptrOP tmp = col2Join[nextCol];
      tmp->children_ = {ptrCur, tables[nextTableName]};
      ptrCur = tmp;
      visited[nextTableName] = true;
    }
    PreOP->children_ = {ptrCur};
  }

  
  return plan;
}

至此，通过样例30-join-order.test

本次实验完成

难度和坑的总结

对于连接优化，许多统计数据都需要自己重新部分暴力的实现，属于一个比较少资源的情况下完成的测试样例。