miniob 初赛参赛总结

写在前面

参加这个比赛其实主要目的是赚钱（感谢周师姐的校友基金，最后含泪收下 7000￥ ），所以以下很多内容可能并不专业。

最终的结果是全国第 40 名，进决赛一共有 50 个队伍，不过由于加权压力（目前估计加权相较于大二上要掉 6 分左右），决赛不一定会付出太多心血去打了。

感谢我的队友 Sazikk 和我一起熬夜肝代码，并且忍耐我的屎山代码长达 21 天之久。由于屎山太多了，所以出现屎的部分会标注。

Sazikk 个人博客：https://sazikk.github.io 目前已有数十万的观看量（狗头
我们的项目：https://github.com/SaZiKK/miniob-2024
806 官方链接：https://ustb-806.github.io/blogs/2024/11/oceanbase/

个人心得

参加这个比赛需要什么能力：

  1. 较强的 C++ 开发能力
  2. 一定的 SQL 语言理解能力
  3. 对 miniob 内核有较好的理解

miniob 框架解析

我负责的题目

drop table

题目要求删除某个表格，一个表格的信息包括三种：数据信息 + 索引信息 + 表格元数据

  1. 数据信息：真实存放到表格当中的数据
  2. 索引信息：一个索引对应一棵 B+ 树
  3. 表格元数据：各种表格的描述信息

drop table 不需要算子，需要执行器

前端 lex yacc 完善

lex 加入关键字 DROP

1
DROP                                    RETURN_TOKEN(DROP);

yacc 加入语句

1
2
3
4
5
6
drop_table_stmt:
    DROP TABLE ID {
      $$ = new ParsedSqlNode(SCF_DROP_TABLE);
      $$->drop_table.relation_name = $3;
      free($3);
    };

STMT 设计

删除表格只需要表格的表名，当然正常来说在 STMT 级就应该通过表格名称获取到实际的 Table 了，但是当时写的时候放到了 Db 的删除表格函数中。

EXECUTE 设计

在执行器中通过调用 db 的删除表格函数或者 table 的自毁函数。表格的自毁函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
RC Table::drop() {

  // 删除数据文件 data_file
  string data_file = table_data_file(base_dir_.c_str(), table_meta_.name());
  unlink(data_file.c_str());

  // 删除索引文件 index_file
  int indexNum = table_meta_.index_num();
  for (int i = 0; i < indexNum; i++) {
    auto *index_meta = table_meta_.index(i);
    string index_file = table_index_file(base_dir_.c_str(), table_meta_.name(), index_meta->name());
    unlink(index_file.c_str());
  }

  // 删除元文件 meta_file
  string meta_file = table_meta_file(base_dir_.c_str(), table_meta_.name());
  unlink(meta_file.c_str());

  return RC::SUCCESS;
}

update

虽然题目只要求单字段的更新，但是由于后面很快就要扩充，所以下面直接放完整版。

需要注意的有两点，如何将 在某些字段修改为某值 推得 在内存某些位置修改二进制数据；以及对于多个字段的更新，必须同时成功或失败，也即先判断后修改（或回滚），不仅有单个字段间的回滚，还有单个元组间的回滚。

update 语句不需要执行器，需要算子

前端 lex yacc 完善

lex 加入关键字 UPDATE

1
UPDATE                                  RETURN_TOKEN(UPDATE);

yacc 加入语句
其中 update_target 为一个字段的更新，update_target_list 为若干字段的更新，where 为谓词表达式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
update_stmt:      /*  update 语句的语法解析树*/
    UPDATE ID SET update_target update_target_list where 
    {
      $$ = new ParsedSqlNode(SCF_UPDATE);
      $$->update.relation_name = $2;

      if ($6 != nullptr) {
        $$->update.conditions.swap(*$6);
        delete $6;
      }

      if($5 != nullptr)
        $$->update.update_targets.swap(*$5);
      $$->update.update_targets.emplace_back(*$4);
      std::reverse($$->update.update_targets.begin(), $$->update.update_targets.end());
    }
    ;

对于 ParseSqlNode，新增 update 语句对应的 node。

1
2
3
4
5
6
7
8
9
10
11
12
struct UpdateSqlNode {
  std::string relation_name;                // 更新表格名称
  std::vector<UpdateTarget> update_targets; // 更新字段集合
  std::vector<ConditionSqlNode> conditions; // 谓词条件
};

struct UpdateTarget {
  bool is_value;                            // 是否为简单值，本题视作 true
  Value value;                              // 更新的值
  std::string attribute_name;               // 更新的属性名
  SubSelectSqlNode *sub_select;             // 子查询，后面习题涉及
};

STMT 设计

update 语句对应的 STMT 中包含：所有修改域信息(FieldMeta)，目标表格，筛选对应的 STMT(FilterStmt)，以及处理好的 UpdateTarget 数组。

第一步，拿到表格

第二步，通过所有修改域的名称，拿到全部修改域，注意顺序是不重要的，因为它们都是同时成功或同时失败的。

第三步，如果有子查询需要将子查询转化为一个 Value，后面对应的题再解释。

逻辑算子和物理算子设计

逻辑算子中需要包含表格以及一个数组，数组表示需要更新的域和值。

1
2
Table *table_ = nullptr;
std::vector<std::pair<Value, FieldMeta>> update_map_;

物理算子直接继承逻辑算子中的表格和<域, 值>数组，除此之外还需要包含一个 Record 数组，因为我们要处理单个元组的回滚。在存在 unique index 的情境下，一条 update 语句可能对多个元组进行修改，
如果修改时发现某一条元组的修改是非法的，则之前所有的修改都要撤回。此处存放修改前的 Record 数组方便回滚。而对于单个字段的回滚，我们采取先判断合法再修改的策略，也即只有全部字段的修改都是有效的
才会开始实际的修改。

例如：

id num col
id1 num1 col1
id2 num2 col2
id3 num3 col3

update 语句需要修改第一个元组和第三个元组的 id, col 字段。

元组级别的回滚：更新第一个元组没问题，但是更新第三个元组是非法的。

字段级别的回滚：更新某个元组时，更新 id 域没问题，但是更新 col 域是非法的。

1
2
3
4
Table *table_ = nullptr;
Trx *trx_ = nullptr;
std::vector<std::pair<Value, FieldMeta>> update_map_;
std::vector<Record> records_;

物理算子 open 函数设计：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// main_tuple 涉及到复杂子查询
RC UpdatePhysicalOperator::open(Trx *trx, const Tuple *main_tuple) {
  if (children_.empty()) {
    return RC::SUCCESS;
  }

  std::unique_ptr<PhysicalOperator> &child = children_[0];

  // 调用子算子的 open 函数
  RC rc = child->open(trx, main_tuple);
  if (rc != RC::SUCCESS) {
    LOG_WARN("failed to open child operator: %s", strrc(rc));
    return rc;
  }

  trx_ = trx;

  // 收集全部元组
  while (OB_SUCC(rc = child->next(main_tuple))) {
    Tuple *tuple = child->current_tuple();
    if (nullptr == tuple) {
      return rc;
    }

    RowTuple *row_tuple = static_cast<RowTuple *>(tuple);
    Record &record = row_tuple->record();
    records_.emplace_back(std::move(record));
  }

  child->close();

  if (records_.empty()) {
    LOG_WARN("no records to update");
  }

  // 将这些元组数据拷贝到一个新数组中，用于回滚
  std::vector<char *> backup_datas;
  for (Record &record : records_) {
    Record backup_record;
    char *old_data = record.data();
    char *backup_data = (char *)malloc(record.len());
    memcpy(backup_data, old_data, record.len());

    backup_datas.push_back(backup_data);
  }

  size_t update_num = 0;

  // 先收集记录再更新
  for (Record &record : records_) {
    rc = trx_->update_records(table_, record, update_map_);
    ++update_num;
    if (rc != RC::SUCCESS) {
      // 如果更新失败，需要回滚，重新将修改过的元组复原
      for (int i = 0; i < (int)update_num; ++i) {
        char *backup_data = backup_datas[i];
        Record &record = records_[i];

        record.set_data(backup_data);
        table_->record_handler()->update_record(&record);
      }
      return rc;
    }
  }

  return RC::SUCCESS;
}

update 算子一般没有上层算子，所以不需要 next 函数，open 函数中调用了子算子的 close 函数，所以也不需要 close 函数。但理论上子算子的 close 函数放到 update 算子的 close 函数中会更好。
不过 delete 算子中也是这么写的，所以此处不修改了。

expression

将万物都改成 expression 的过程

1.将谓词语句的 value/field op value/field 结构改成 expression op expression
2.初始的 FilterObj 中的 expression 只能是 value/field，扩展使得 expression 可以是任何类型

之前提到过，在 select 语句中，会将查询的表达式进行绑定，例如将 UnboundField 绑定为 Field。在 Filter 部分，如果想要支持任何类型的 expression，也需要绑定的环节。miniob 初始的框架只包含了对 UnboundField 的绑定，
也即只完成了通过名字寻找特定域的功能。

理论上，应该模仿 select 语句的绑定，使用 ExpressionBinder 类来完成绑定的行为，但当时写的过于潦草，采用了纯粹的 switch 来完成。例如在下面的代码中完成了对表达式 expr 的绑定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
// use_flag 是弃用的(时间关系未删除)，alias_map 为别名部分，table_map 为复杂子查询中的传递情况
// expr 是需要绑定的表达式，也是一条谓词语句的一端
RC FilterStmt::bind_filter_expr(Db *db, Table *default_table, std::unordered_map<std::string, Table *> *tables, unique_ptr<Expression> &expr,
                                bool &use_flag, std::unordered_map<string, string> alias_map, std::unordered_map<string, Table *> table_map) {
  if (expr == nullptr) return RC::INVALID_ARGUMENT;

  // TODO 直接使用 expression_binder 中的函数进行

  // 根据表达式的不同类型需要进行不同的操作
  switch (expr->type()) {
    case ExprType::VALUE: {
      Value value;
      RC rc = expr->try_get_value(value);
      if (rc != RC::SUCCESS) return rc;
      if (value.attr_type() == AttrType::DATE && !DateType::check_date(&value)) return RC::INVALID_ARGUMENT;
    } break;
    case ExprType::VALUELIST: {
      std::vector<Value> value_list;
      RC rc = expr->get_value_list(value_list);
      if (rc != RC::SUCCESS) return rc;
      for (auto it : value_list)
        if (it.attr_type() == AttrType::DATE && !DateType::check_date(&it)) return RC::INVALID_ARGUMENT;
    } break;
    case ExprType::SUBQUERY: {
      return RC::SUCCESS;
    } break;
    case ExprType::UNBOUND_FIELD: {
      Table *table = nullptr;
      const FieldMeta *field = nullptr;
      RC rc = get_table_and_field(db, default_table, tables, expr.get(), table, field, use_flag, alias_map, table_map);
      if (rc != RC::SUCCESS) return rc;
      expr = std::make_unique<FieldExpr>(table, field);
    } break;
    case ExprType::ARITHMETIC: {
      RC rc = RC::SUCCESS;
      ArithmeticExpr *arith_expr = static_cast<ArithmeticExpr *>(expr.get());
      if (arith_expr->left() != nullptr) {
        rc = bind_filter_expr(db, default_table, tables, arith_expr->left(), use_flag, alias_map, table_map);
      }
      if (rc != RC::SUCCESS) return rc;
      if (arith_expr->right() != nullptr) {
        rc = bind_filter_expr(db, default_table, tables, arith_expr->right(), use_flag, alias_map, table_map);
      }
      if (rc != RC::SUCCESS) return rc;
    } break;
    case ExprType::VECFUNC: {
      RC rc = RC::SUCCESS;
      VecFuncExpr *vec_func_expr = static_cast<VecFuncExpr *>(expr.get());
      if (vec_func_expr->child_left() != nullptr) {
        rc = bind_filter_expr(db, default_table, tables, vec_func_expr->child_left(), use_flag, alias_map, table_map);
      }
      if (rc != RC::SUCCESS) return rc;
      if (vec_func_expr->child_right() != nullptr) {
        rc = bind_filter_expr(db, default_table, tables, vec_func_expr->child_right(), use_flag, alias_map, table_map);
      }
      if (rc != RC::SUCCESS) return rc;
    } break;
    case ExprType::UNBOUND_AGGREGATION: {
      RC rc = RC::SUCCESS;
      auto unbound_aggregate_expr = static_cast<UnboundAggregateExpr *>(expr.get());
      string name = unbound_aggregate_expr->name();
      const char *aggregate_name = unbound_aggregate_expr->aggregate_name();

      AggregateExpr::Type aggregate_type;
      rc = AggregateExpr::type_from_string(aggregate_name, aggregate_type);
      if (rc != RC::SUCCESS) return rc;

      unique_ptr<Expression> &child_expr = unbound_aggregate_expr->child();

      if (child_expr == nullptr) return RC::INVALID_ARGUMENT;

      if (child_expr->type() == ExprType::STAR && aggregate_type == AggregateExpr::Type::COUNT) {
        ValueExpr *value_expr = new ValueExpr(Value(1));
        child_expr.reset(value_expr);
      } else {
        rc = bind_filter_expr(db, default_table, tables, child_expr, use_flag, alias_map, table_map);
        if (rc != RC::SUCCESS) return rc;
      }

      // TODO 校验聚合表达式
      expr = make_unique<AggregateExpr>(aggregate_type, std::move(child_expr));
      expr->set_name(name);
    } break;
    default:
      return RC::INVALID_ARGUMENT;
      break;
  }
  return RC::SUCCESS;
}

当然，FilterObj 也需要改成 expression，而不是之前的 field/value 模式。

1
2
3
4
5
struct FilterObj {
  std::unique_ptr<Expression> expr;
  void operator=(FilterObj &obj) { this->expr = std::move(obj.expr); }
  void init(std::unique_ptr<Expression> expr) { this->expr = std::move(expr); }
};

在 yacc 中，也需要进行修改，condition 部分需要改成左右都为 expression。其中虽然我们将子查询也设计成了表达式，但是在解析的时候，子查询并不算为 expression，否则会出现冲突。
所以此处我们先通过 sub_select_stmt 来识别，在后面将其转化为 expression，从而和其他 expression 一起处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
expression comp_op
    {
      $$ = new ConditionSqlNode;
      $$->left_is_sub_query = false;
      $$->right_is_sub_query = false;
      $$->comp = $2;
      $$->left_expression = $1;
      $$->right_expression = new ValueExpr(Value(114514));
    }
    | expression comp_op sub_select_stmt
    {
      $$ = new ConditionSqlNode;
      $$->left_is_sub_query = false;
      $$->right_is_sub_query = true;
      $$->comp = $2;
      $$->left_expression = $1;
      $$->right_sub_query = $3;
      $$->right_expression = nullptr;
    }
    | sub_select_stmt comp_op sub_select_stmt
    {
      $$ = new ConditionSqlNode;
      $$->left_is_sub_query = true;
      $$->right_is_sub_query = true;
      $$->comp = $2;
      $$->left_sub_query = $1;
      $$->left_expression = nullptr;
      $$->right_sub_query = $3;
      $$->right_expression = nullptr;
    }
    | sub_select_stmt comp_op expression
    {
      $$ = new ConditionSqlNode;
      $$->left_is_sub_query = true;
      $$->right_is_sub_query = false;
      $$->comp = $2;
      $$->left_sub_query = $1;
      $$->left_expression = nullptr;
      $$->right_expression = $3;
    }
    | expression comp_op expression
    {
      $$ = new ConditionSqlNode;
      $$->left_is_sub_query = false;
      $$->right_is_sub_query = false;
      $$->comp = $2;
      $$->left_expression = $1;
      $$->right_expression = $3;
    }
    | comp_op sub_select_stmt
    {
      $$ = new ConditionSqlNode;
      $$->left_is_sub_query = false;
      $$->right_is_sub_query = true;
      $$->right_sub_query = $2;
      $$->comp = $1;
      $$->left_expression = new ValueExpr(Value(114514));
    }
    | expression comp_op LBRACE value value_list RBRACE %prec HIGHER_THAN_EXPRESSION
    {
      $$ = new ConditionSqlNode;
      $$->left_is_sub_query = false;
      $$->right_is_sub_query = false;
      $$->comp = $2;
      $$->left_expression = $1;
      $5->push_back(*$4);
      $$->right_expression = new ValueListExpr(*$5);
    }
    ;

在后面的日子中，我们将能改的都改成了 expression，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @brief 表达式类型
 * @ingroup Expression
 */
enum class ExprType {
  NONE,
  STAR,                 ///< 星号，表示所有字段
  UNBOUND_FIELD,        ///< 未绑定的字段，需要在resolver阶段解析为FieldExpr
  UNBOUND_TABLE,        ///< 未绑定的表明，需要在resolver阶段提取别名和原名
  UNBOUND_AGGREGATION,  ///< 未绑定的聚合函数，需要在resolver阶段解析为AggregateExpr

  ALIAS,        ///< 别名
  FIELD,        ///< 字段。在实际执行时，根据行数据内容提取对应字段的值
  JOINTABLE,    ///< join 字段
  ORDERBY,      ///< order 字段
  VALUE,        ///< 常量值
  VALUELIST,    ///< 常量值列表
  CAST,         ///< 需要做类型转换的表达式
  COMPARISON,   ///< 需要做比较的表达式
  CONJUNCTION,  ///< 多个表达式使用同一种关系(AND或OR)来联结
  ARITHMETIC,   ///< 算术运算
  AGGREGATION,  ///< 聚合运算
  SUBQUERY,     ///< 子查询
  FUNC,         ///< 函数运算
  VECFUNC,      ///< 向量函数运算
};

修改逻辑算子生成器

在逻辑算子的生成过程中，原始的 miniob 会将 Filter 中的 field/value 变成表达式，很明显现在这是多此一举，对此进行修改。

需要注意的是，当一个 STMT 创建算子之后，原来的全部 unique_ptr 都会被移动走，在子查询里，应该还会看到这句话。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
RC LogicalPlanGenerator::create_plan(FilterStmt *filter_stmt, unique_ptr<LogicalOperator> &logical_operator) {
  RC rc = RC::SUCCESS;
  std::vector<unique_ptr<Expression>> cmp_exprs;
  ConjunctionExpr::Type conjunction_types = ConjunctionExpr::Type::AND;
  const std::vector<FilterUnit *> &filter_units = filter_stmt->filter_units();
  for (FilterUnit *filter_unit : filter_units) {
    FilterObj &filter_obj_left = filter_unit->left();
    FilterObj &filter_obj_right = filter_unit->right();

    unique_ptr<Expression> left = std::move(filter_obj_left.expr);
    unique_ptr<Expression> right = std::move(filter_obj_right.expr);

    if (filter_unit->conjunction_type() == 1)
      conjunction_types = ConjunctionExpr::Type::AND;
    else if (filter_unit->conjunction_type() == 2)
      conjunction_types = ConjunctionExpr::Type::OR;

    bool need_value_cast = left->value_type() != AttrType::TUPLES && right->value_type() != AttrType::TUPLES && left->type() != ExprType::VALUELIST &&
                           right->type() != ExprType::VALUELIST && filter_unit->comp() != CompOp::XXX_IS_NULL &&
                           filter_unit->comp() != CompOp::XXX_IS_NOT_NULL;

    // 如果左右两边的类型不一致，需要先计算转换开销，再进行隐式类型转换，同时要排除有子查询的情况
    if (need_value_cast) {
      Value left_value, right_value;
      left->try_get_value(left_value);
      right->try_get_value(right_value);
      if (!left_value.get_null() && !right_value.get_null() && left->value_type() != right->value_type()) {
        auto left_to_right_cost = implicit_cast_cost(left->value_type(), right->value_type());
        auto right_to_left_cost = implicit_cast_cost(right->value_type(), left->value_type());
        if (left_to_right_cost <= right_to_left_cost && left_to_right_cost != INT32_MAX) {
          ExprType left_type = left->type();

          // 特殊判断，如果为 INTS 和 CHARS 比较大小，均转换成 FLOATS 类型
          unique_ptr<CastExpr> cast_expr;
          if (left->value_type() == AttrType::CHARS && right->value_type() == AttrType::INTS)
            cast_expr = make_unique<CastExpr>(std::move(left), AttrType::FLOATS);
          else
            cast_expr = make_unique<CastExpr>(std::move(left), right->value_type());
          if (left_type == ExprType::VALUE) {
            Value left_val;
            if (OB_FAIL(rc = cast_expr->try_get_value(left_val))) {
              LOG_WARN("failed to get value from left child", strrc(rc));
              return rc;
            }
            left = make_unique<ValueExpr>(left_val);
          } else {
            left = std::move(cast_expr);
          }
        } else if (right_to_left_cost < left_to_right_cost && right_to_left_cost != INT32_MAX) {
          ExprType right_type = right->type();

          // 特殊判断，如果为 INTS 和 CHARS 比较大小，均转换成 FLOATS 类型
          unique_ptr<CastExpr> cast_expr;
          if (left->value_type() == AttrType::INTS && right->value_type() == AttrType::CHARS)
            cast_expr = make_unique<CastExpr>(std::move(right), AttrType::FLOATS);
          else
            cast_expr = make_unique<CastExpr>(std::move(right), left->value_type());

          if (right_type == ExprType::VALUE) {
            Value right_val;
            if (OB_FAIL(rc = cast_expr->try_get_value(right_val))) {
              LOG_WARN("failed to get value from right child", strrc(rc));
              return rc;
            }
            right = make_unique<ValueExpr>(right_val);
          } else {
            right = std::move(cast_expr);
          }
        } else if (filter_unit->comp() == CompOp::LIKE_XXX || filter_unit->comp() == CompOp::NOT_LIKE_XXX) {
          ExprType right_type = right->type();

          // 如果执行LIKE运算符，把右边转化成CHARS类型
          unique_ptr<CastExpr> cast_expr;
          cast_expr = make_unique<CastExpr>(std::move(right), AttrType::CHARS);

          if (right_type == ExprType::VALUE) {
            Value right_val;
            if (OB_FAIL(rc = cast_expr->try_get_value(right_val))) {
              LOG_WARN("failed to get value from right child", strrc(rc));
              return rc;
            }
            right = make_unique<ValueExpr>(right_val);
          } else {
            right = std::move(cast_expr);
          }
        } else {
          rc = RC::UNSUPPORTED;
          LOG_WARN("unsupported cast from %s to %s", attr_type_to_string(left->value_type()), attr_type_to_string(right->value_type()));
          return rc;
        }
      }
    }

    ComparisonExpr *cmp_expr = new ComparisonExpr(filter_unit->comp(), std::move(left), std::move(right));

    cmp_exprs.emplace_back(cmp_expr);
  }

  unique_ptr<PredicateLogicalOperator> predicate_oper;
  if (!cmp_exprs.empty()) {
    unique_ptr<ConjunctionExpr> conjunction_expr(new ConjunctionExpr(conjunction_types, cmp_exprs));
    predicate_oper = unique_ptr<PredicateLogicalOperator>(new PredicateLogicalOperator(std::move(conjunction_expr)));
  }

  logical_operator = std::move(predicate_oper);
  return rc;
}

int LogicalPlanGenerator::implicit_cast_cost(AttrType from, AttrType to) {
  if (from == to) {
    return 0;
  }
  return DataType::type_instance(from)->cast_cost(to);
}

vector_basic

相对简单的一道题目，需要添加一种数据类型：VECTOR

我们采取的方式为，对于 ‘[1, 2, 3, 4]’ 这样的向量，先以字符串的形式输入进来，在 Value 的构造函数中进行格式检验，如果符合向量的格式，那么将其转化为向量存储，否则以字符串的方式存储。

有些边角的东西没有体现在下面的描述中，包括：插入向量时的长度不匹配问题 + 创建表格时的 VECTOR 长度检验等

Value 类的完善

首先，由于向量一定是 float 类型，所以实际的存储形式为 vector。Value 中有个字段 len，表示 Value 的长度，注意这个长度是占用空间的长度，对于 vector 来说，这个长度是 vector.size() * 4。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// vector part
 public:
  // 判断一个字符串是否为向量形式
  static bool isValidFormat(const char *input);
  // 判断一个字符串是否为数字，避免 [1, a, 2] 这样的例子
  static bool isValidNumber(const std::string &s);
  // 将字符串转化为 vector，如果字符串不合法，返回 FAILURE
  static RC string_to_vector(string str, vector<float> &result);

  // set and get
  void set_vector(std::vector<float> value_vector);
  vector<float> get_vector() const;
  float get_vector_item(int idx) const;
  int get_vector_size() const;

 private:
  std::vector<float> value_vector_;

isValidFormat, isValidNumber, string_to_vector 的设计如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// vector part

// 用于检查输入字符串是否符合 vector 的格式
bool Value::isValidFormat(const char *input) {
  // 检查是否为空或长度小于2（必须至少包含 "[]")
  if (input == nullptr || strlen(input) < 2) {
    return false;
  }

  // 检查首尾是否分别为 '[' 和 ']'
  if (input[0] != '[' || input[strlen(input) - 1] != ']') {
    return false;
  }

  // 剔除 '[' 和 ']'，从第二个字符开始检查
  std::string content(input + 1, strlen(input) - 2);

  // 删除多余的空格
  content.erase(std::remove(content.begin(), content.end(), ' '), content.end());

  // 使用逗号分割内容
  std::istringstream ss(content);
  std::string token;
  std::vector<std::string> tokens;

  // 分割内容并检查每个部分
  while (std::getline(ss, token, ',')) {
    if (!isValidNumber(token)) {
      return false;  // 如果某个部分不是有效的数字，返回 false
    }
  }

  return true;  // 所有部分都是有效的数字
}

// 用于检查一个字符串是否是整数或浮点数
bool Value::isValidNumber(const std::string &s) {
  std::istringstream stream(s);
  float number;
  stream >> number;
  // 检查是否成功解析为数字，并且没有多余字符
  return stream.eof() && !stream.fail();
}

RC Value::string_to_vector(string str, vector<float> &result) {
  if (!Value::isValidFormat(str.c_str())) return RC::INVALID_ARGUMENT;

  // 剔除 '[' 和 ']'，从第二个字符开始检查
  str = str.substr(1, (int)str.size() - 2);

  // 去除多余空格
  str.erase(std::remove(str.begin(), str.end(), ' '), str.end());

  // 使用逗号分割内容
  std::istringstream ss(str);
  std::string token;
  std::vector<std::string> tokens;

  // 分割内容并检查每个部分
  while (std::getline(ss, token, ',')) {
    result.push_back(FloatType::formatFloat(std::stof(token), 2));
  }
  return RC::SUCCESS;
}

接下来是 Value 输入为字符串的构造函数，如果发现字符串的格式为数组形式，那么转化为 VECTOR。

1
2
3
4
5
6
7
8
Value::Value(const char *s, int len /*= 0*/) {
  vector<float> value_vector;
  RC rc = Value::string_to_vector(s, value_vector);
  if (rc == RC::SUCCESS)
    set_vector(value_vector);
  else
    set_string(s, len);
}

接下来是 Value 和 data 的转换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
void Value::set_data(char *data, int length) {
  switch (attr_type_) {
    case AttrType::CHARS: {
      set_string(data, length);
    } break;
    case AttrType::INTS: {
      value_.int_value_ = *(int *)data;
      length_ = length;
    } break;
    case AttrType::FLOATS: {
      value_.float_value_ = *(float *)data;
      length_ = length;
    } break;
    case AttrType::BOOLEANS: {
      value_.bool_value_ = *(int *)data != 0;
      length_ = length;
    } break;
    case AttrType::DATE: {
      value_.int_value_ = *(int *)data;
      length_ = length;
    } break;
    case AttrType::VECTORS: {
      size_t element_size = sizeof(int);
      size_t num_elements = length / element_size;

      // 使用 memcpy 将数据复制回 vector
      value_vector_.resize(num_elements);
      memcpy(value_vector_.data(), data, length);
      length_ = length;
    } break;
    case AttrType::TEXT: {
      set_text(data);
    } break;
    default: {
      LOG_WARN("unknown data type: %d", attr_type_);
    } break;
  }
}

const char *Value::data() const {
  switch (attr_type_) {
    case AttrType::TEXT: {
      return value_.pointer_value_;
    } break;
    case AttrType::CHARS: {
      return value_.pointer_value_;
    } break;
    case AttrType::VECTORS: {
      return (const char *)(value_vector_.data());
    }
    default: {
      return (const char *)&value_;
    } break;
  }
}

VECTOR 的各种运算

在 common/type 中，还需要完成有关 VECTOR 的各种计算、比较等。由于比较简单这里直接放上来了，不过需要注意的是，比赛要求向量的乘法是逐位相乘，也即两个向量的乘积仍为向量：[1, 2, 3] * [4, 5, 6] = [4, 10, 18]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
int VectorType::compare(const Value &left, const Value &right) const {
  if (left.attr_type() != AttrType::VECTORS || right.attr_type() != AttrType::VECTORS || left.get_vector_size() != right.get_vector_size())
    return INT32_MAX;
  int size = (int)left.get_vector_size();
  int result = 0;
  for (int i = 0; i < size; i++) {
    if (left.get_vector()[i] > right.get_vector()[i]) {
      result = 1;
      break;
    } else if (left.get_vector()[i] < right.get_vector()[i]) {
      result = -1;
      break;
    }
  }
  return result;
}

RC VectorType::add(const Value &left, const Value &right, Value &result) const {
  if (left.attr_type() != AttrType::VECTORS || right.attr_type() != AttrType::VECTORS || left.get_vector_size() != right.get_vector_size())
    return RC::INVALID_ARGUMENT;
  int size = (int)left.get_vector_size();
  vector<float> answer(size, 0);
  for (int i = 0; i < size; i++) answer[i] = left.get_vector()[i] + right.get_vector()[i];
  result.set_vector(answer);
  return RC::SUCCESS;
}
RC VectorType::subtract(const Value &left, const Value &right, Value &result) const {
  if (left.attr_type() != AttrType::VECTORS || right.attr_type() != AttrType::VECTORS || left.get_vector_size() != right.get_vector_size())
    return RC::INVALID_ARGUMENT;
  int size = (int)left.get_vector_size();
  vector<float> answer(size, 0);
  for (int i = 0; i < size; i++) answer[i] = left.get_vector()[i] - right.get_vector()[i];
  result.set_vector(answer);
  return RC::SUCCESS;
}
RC VectorType::multiply(const Value &left, const Value &right, Value &result) const {
  if (left.attr_type() != AttrType::VECTORS || right.attr_type() != AttrType::VECTORS || left.get_vector_size() != right.get_vector_size())
    return RC::INVALID_ARGUMENT;
  int size = (int)left.get_vector_size();
  vector<float> answer(size, 0);
  for (int i = 0; i < size; i++) answer[i] = left.get_vector()[i] * right.get_vector()[i];
  result.set_vector(answer);
  return RC::SUCCESS;
}

RC VectorType::to_string(const Value &val, string &result) const {
  if (val.attr_type() != AttrType::VECTORS) return RC::INVALID_ARGUMENT;

  result = "[";
  for (auto it : val.get_vector()) {
    it = FloatType::formatFloat(it, 2);
    string str = std::to_string(it);
    str = FloatType::formatFloat_s(it, 2);

    // 去除后导零
    str.erase(str.find_last_not_of('0') + 1, std::string::npos);
    if (str.back() == '.') {
      str.pop_back();
    }
    result += str;
    result += ',';
  }
  if ((int)result.length() > 1) result.pop_back();
  result += "]";

  return RC::SUCCESS;
}

vector_format

题目要求不仅要识别字符串类型的向量数据，还需要识别不带引号的向量数据。我在写的时候偷懒了，直接采取 [ + value + value_list + ]，所以只需要在 yacc 中添加这一条规则即可。

lex 和 yacc 完善

lex 需要添加左右中括号的词语：

1
2
"["                                     RETURN_TOKEN(LBRACKET);
"]"                                     RETURN_TOKEN(RBRACKET);

yacc 需要添加对向量变量的识别：

1
2
3
4
5
6
7
8
9
10
11
12
value:
    LBRACKET value value_list RBRACKET {
      std::vector<float> nums;
      nums.emplace_back($2->get_float());
      if($3 != nullptr) {
        std::reverse($3->begin(), $3->end());
        for (Value value : *$3) {
          nums.emplace_back(value.get_float());
        }
      }
      $$ = new Value(nums);
    }

join-tables

join-tables 所涉及的算子在初始工程已经很完善了。简单来说，对于一条 select 语句可能有多个目标表格，其中第一个目标表格为主表格，后面的表格会跟主表格一并做笛卡尔积。创建算子的时候，第一个表格会创建 TableGet 相关算子，后面的表格会创建 JoinTable 相关算子。

对于 INNERJOIN，ON 中定义的谓词逻辑和 WHERE 中定义的谓词逻辑是完全平等的，所以，对于 ON 中的全部谓词逻辑，我们只需要将其视作 WHERE 中通过 AND 连结词连在一起的即可。

对于 join 部分，将其视作一个表达式，原因见 expression。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// *********************************************************
// * 表格连接表达式
// *
class JoinTableExpr : public Expression {
 public:
  JoinTableExpr(std::vector<ConditionSqlNode> conditions, unique_ptr<Expression> child) : conditions_(conditions), child_(std::move(child)) {}
  JoinTableExpr(std::vector<ConditionSqlNode> conditions, Expression *child) : conditions_(conditions), child_(child) {}

  virtual ~JoinTableExpr() = default;

  ExprType type() const override { return ExprType::JOINTABLE; }
  AttrType value_type() const override { return AttrType::UNDEFINED; }

  RC get_value(const Tuple &tuple, Value &value) const override { return RC::INTERNAL; }

  const std::vector<ConditionSqlNode> conditions() const { return conditions_; }
  const std::unique_ptr<Expression> &child() const { return child_; }

 private:
  std::vector<ConditionSqlNode> conditions_;
  std::unique_ptr<Expression> child_;
};

lex 和 yacc 的完善

lex 需要完善对 JOIN/INNER JOIN/ON 的识别。

1
2
JOIN|INNER[ \t]+JOIN                    RETURN_TOKEN(INNER_JOIN);
ON                                      RETURN_TOKEN(ON);

对于 join 子句的部分，创建一个 expression 数组，数组的 expression 类型为 JoinTableExpr，每一个 JoinTableExpr 包含 join 的表格以及谓词逻辑语句。

select_stmt 也需要加入 join_list 部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
join_list:
    /* empty */
    {
      $$ = nullptr;
    }
    | INNER_JOIN relation ON condition_list join_list {
      if ($5 != nullptr) {
        $$ = $5;
      } else {
        $$ = new std::vector<std::unique_ptr<Expression>>;
      }
      $$->emplace_back(new JoinTableExpr(*$4, $2));
    }
    ;

select_stmt 的完善

在创建 SelectStmt 时，需要将 join 的表格和谓词语句添加到 select 语句中的表格列表和谓词语句列表中。谓词语句顺序无所谓，但是表格的顺序会影响输出表头的顺序，所以需要严格按照 JOIN 出现的顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
// *****************************************************************************
  // * 将节点中的 join 添加到 conditions 以及 relations 当中
  // *    在之后的处理中，如果查询的表格有多个，就会计算全部表格的笛卡尔积
  // *    join 等价于先求笛卡尔积，然后进行选择运算
  // *    所以需要将选择条件也加进 conditions 中(目前全是 AND 运算，所以可以这么处理)

  for (size_t i = 0; i < select_sql.join.size(); i++) {
    JoinTableExpr *join_table_expr = static_cast<JoinTableExpr *>(select_sql.join[i].get());
    UnboundTableExpr *table_expr = static_cast<UnboundTableExpr *>(join_table_expr->child().get());
    unique_ptr<Expression> temp = make_unique<UnboundTableExpr>(table_expr->table_name(), table_expr->table_alias());
    select_sql.relations.emplace_back(move(temp));
    for (auto condition : join_table_expr->conditions()) select_sql.conditions.emplace_back(condition);
  }

null

题目要求支持一种特殊的数据类型：null，它不属于任何普通类型，却又能匹配任何普通类型。

整体来说，需要完成以下内容：

  1. 支持识别关键字 NULL IS NOT 等
  2. 支持创建表格时对特定域声明 NULL or NOT NULL = default
  3. Value 类中添加对 NULL 的管理
  4. 支持插入数据时插入 NULL，并判断合法性
  5. 支持更新数据时更新 NULL，并判断合法性
  6. 支持谓词逻辑普通运算符对 NULL 计算，以及谓词逻辑新增运算 IS NULL and IS NOT NULL

额外需要考虑的一点为，Value 会被转换成 Record 写入内存，也即实际写入内存的是 01 串，而通过 01 串并不能知道这是什么类型。假设某个域类型为 INT，它可以通过表头信息知道：从该列拿出来的数据一定是 INT 类型，所以可以将 01 串按照 INT 的存储规则还原，但是对于 NULL 类型，由于其可以匹配任意类型，所以并不能通过某处记录的信息来得知拿出来的数据为 NULL 类型。

我们的处理是 bitmap 或者 写入特殊字符，使用 bitmap 会导致后面的并发 update 报错，至比赛结束仍不知道原因。不过 bitmap 无疑是最优美的解决方案。

—- WARING 下文有狗屎 —-

所以我们的处理方法是，对于一个 x 字节的数据，如果它的类型为 NULL，则向内存写入数据时，写入 x 字节的 ÿ，就是如此抽象。拿出数据时，首先检验 01 串是否为 x 字节的 ÿ 的 ASCII 码，
如果是则还原成 NULL，不是则根据表头信息等还原。

支持识别关键字 NULL IS NOT 等

lex 中需要添加新的词语解析

1
2
3
4
NULL                                    RETURN_TOKEN(NULLABLE);
NOT[ \t]+NULL                           RETURN_TOKEN(UNNULLABLE);
IS[ \t]+NULL                            RETURN_TOKEN(IS_NULL);
IS[ \t]+NOT+[ \t]+NULL                  RETURN_TOKEN(IS_NOT_NULL);

支持创建表格时对特定域声明 NULL or NOT NULL = default

yacc 中需要添加新的语法解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 运算符
comp_op:
    ...
    | IS_NULL { $$ = XXX_IS_NULL; }
    | IS_NOT_NULL { $$ = XXX_IS_NOT_NULL; }
    | NOT_LIKE { $$ = NOT_LIKE_XXX; }
    ...
    ;
// 创建表格时的声明
attr_def:
    ID type LBRACE number RBRACE null_def 
    {
      $$ = new AttrInfoSqlNode;
      $$->type = (AttrType)$2;
      $$->name = $1;
      $$->length = $4;
      $$->can_be_null = $6;

      ...

      free($1);
    }
// null
null_def:
    {
      $$ = false;
    }
    | NULLABLE {
      $$ = true;
    }
    | UNNULLABLE {
      $$ = false;
    }

Value 类中添加对 NULL 的管理

Value 中添加标志位 is_null_，用于判断 Value 是否为 NULL。同时还需要维护各种构造函数，拷贝函数，运算符重载有关 NULL 的问题。同时 NULL 数据转化为 char * 写入内存的
时候要转换成若干个 ÿ。

支持插入数据时插入 NULL，并判断合法性

在将 Value 转化为 Record 时，需要额外做一步判断。如果插入的数据为 NULL 且该域不允许为 NULL，返回 FAILURE。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
RC Table::make_record(int value_num, const Value *values, Record &record) {
  RC rc = RC::SUCCESS;
  // 检查属性数量是否一致
  if (value_num + table_meta_.sys_field_num() != table_meta_.field_num()) {
    LOG_WARN("Input values don't match the table's schema, table name:%s", table_meta_.name());
    return RC::SCHEMA_FIELD_MISSING;
  }

  const int normal_field_start_index = table_meta_.sys_field_num();
  // 复制所有字段的值
  int record_size = table_meta_.record_size();
  char *record_data = (char *)malloc(record_size);
  memset(record_data, 0, record_size);

  for (int i = 0; i < value_num && OB_SUCC(rc); i++) {
    const FieldMeta *field = table_meta_.field(i + normal_field_start_index);
    Value value = values[i];

    // 当插入数据 NULL 时，做一次检验
    if (value.get_null()) {
      if (field->can_be_null() == false) {
        LOG_WARN("failed to insert NULL to NOT_NULL field");
        return RC::INVALID_ARGUMENT;
      }
      rc = set_value_to_record(record_data, value, field, i);
    } else if (field->type() != value.attr_type()) {
      Value real_value;
      rc = Value::cast_to(value, field->type(), real_value);
      if (OB_FAIL(rc)) {
        LOG_WARN("failed to cast value. table name:%s,field name:%s,value:%s ", table_meta_.name(), field->name(), value.to_string().c_str());
        break;
      }
      rc = set_value_to_record(record_data, real_value, field, i);
    } else {
      rc = set_value_to_record(record_data, value, field, i);
    }
  }
  if (OB_FAIL(rc)) {
    LOG_WARN("failed to make record. table name:%s", table_meta_.name());
    free(record_data);
    return rc;
  }

  record.set_data_owner(record_data, record_size);
  return RC::SUCCESS;
}

同时转换为 Record 时，也需要考虑 NULL 的情况。

1
2
3
4
if (value.get_null()) {
  const char *flag = "ÿÿÿÿ";
  memcpy(record_data + field->offset(), flag, std::min(field->len(), 4));
}

支持更新数据时更新 NULL，并判断合法性

和插入数据区别不大，也是需要额外添加一层判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
// 检查所有更新字段是否全部有效
RC Table::update_records(Record &record, std::vector<std::pair<Value, FieldMeta>> update_map_) {
  // 遍历表格的全部域，找到目标域
  const int sys_field_num = table_meta_.sys_field_num();
  const int user_field_num = table_meta_.field_num() - sys_field_num;
  FieldMeta *targetFiled = nullptr;

  for (auto it : update_map_) {
    for (int i = 0; i < user_field_num; i++) {
      const FieldMeta *field_meta = table_meta_.field(sys_field_num + i);
      const char *field_name = field_meta->name();

      // 找到目标域
      if (strcmp(field_name, it.second.name()) == 0) {
        // 判断 NULL 值
        if (it.first.get_null()) {
          if (field_meta->can_be_null() == false) return RC::INVALID_ARGUMENT;
        }
        // 类型匹配检查
        else if (field_meta->type() != it.first.attr_type()) {
          Value real_value;
          RC rc = Value::cast_to(it.first, field_meta->type(), real_value);
          if (OB_FAIL(rc)) return rc;
        }

        // 拿到目标域
        targetFiled = (FieldMeta *)field_meta;
        break;
      }
    }

    // 域存在检查
    if (nullptr == targetFiled) {
      return RC::SCHEMA_FIELD_NOT_EXIST;
    }
  }

  // 暂时备份旧数据
  char *old_data = record.data();
  char *backup_data = (char *)malloc(record.len());
  memcpy(backup_data, old_data, record.len());

  // 所有字段均可更新，开始更新
  for (auto it : update_map_) {
    RC rc = update_record(record, it.second.name(), &it.first);
    if (rc != RC::SUCCESS) return rc;
  }

  // 如果有索引，更新索引，顺便检查如果是唯一索引，那么是否有重复
  std::vector<const char *> update_fields;
  for (auto &it : update_map_) {
    update_fields.push_back(it.second.name());
  }
  Index *index = this->find_index_by_fields(update_fields);
  // 只检查多索引，单列索引交给 update_record 处理
  if (index != nullptr && update_fields.size() > 1) {
    RC rc = index->insert_entry(record.data(), &record.rid());
    if (rc != RC::SUCCESS && strcmp(old_data, backup_data) != 0) {
      LOG_ERROR("Failed to update data, recovering. table=%s, rc=%d:%s", name(), rc, strrc(rc));
      return rc;
    }
  }

  return RC::SUCCESS;
}

// 更新一个字段
RC Table::update_record(Record &record, const char *attr_name, Value *value) {
  // 遍历表格的全部域，找到目标域
  const int sys_field_num = table_meta_.sys_field_num();
  const int user_field_num = table_meta_.field_num() - sys_field_num;
  FieldMeta *targetFiled = nullptr;

  int i = 0;
  for (; i < user_field_num; i++) {
    const FieldMeta *field_meta = table_meta_.field(sys_field_num + i);
    const char *field_name = field_meta->name();

    // 找到目标域
    if (strcmp(field_name, attr_name) == 0) {
      // 判断 NULL 值
      if (value->get_null()) {
        if (field_meta->can_be_null() == false) return RC::INVALID_ARGUMENT;
      }
      // 类型匹配检查
      else if (field_meta->type() != value->attr_type()) {
        Value real_value;
        RC rc = Value::cast_to(*value, field_meta->type(), real_value);
        if (OB_FAIL(rc)) return rc;
        *value = std::move(real_value);
      }

      // 拿到目标域
      targetFiled = (FieldMeta *)field_meta;
      break;
    }
  }

  // 域存在检查
  if (nullptr == targetFiled) {
    return RC::SCHEMA_FIELD_NOT_EXIST;
  }

  int field_offset = targetFiled->offset();
  int field_length = targetFiled->len();

  // 修改旧数据
  char *old_data = record.data();

  // 暂时备份旧数据
  char *backup_data = (char *)malloc(record.len());
  memcpy(backup_data, old_data, record.len());

  if (value->length() > field_length && targetFiled->type() != AttrType::VECTORS) {
    memcpy(old_data + field_offset, value->data(), field_length);
  }
  ...
  // 对于 CHARS
  // 这种不定长的记录，如果更新的元素小于原来的长度，需要额外抹去原有元素
  else {
    memcpy(old_data + field_offset, value->data(), value->length());
    memset(old_data + field_offset + value->length(), 0, field_length - value->length());
  }

  if (value->get_null()) {
    const char *flag = "ÿÿÿÿ";
    memcpy(old_data + field_offset, flag, std::min(4, field_length));
  }

  record.set_data(old_data);

  Index *index = this->find_index_by_field(targetFiled->name());

  // 单字段索引更新和检查
  if (index != nullptr) {
    RC rc = index->insert_entry(record.data(), &record.rid());
    if (rc != RC::SUCCESS && strcmp(old_data, backup_data) != 0) {
      LOG_ERROR("Failed to update data, recovering. table=%s, rc=%d:%s", name(), rc, strrc(rc));
      return rc;
    }
  }

  record_handler_->update_record(&record);
  // delete old_data;
  return RC::SUCCESS;
}

支持谓词逻辑普通运算符对 NULL 计算，以及谓词逻辑新增运算 IS NULL and IS NOT NULL

由于 Compare 部分我们写的比较复杂，这边只展示有关 IS NULL and IS NOT NULL 的函数，对于普通运算符，只需要在最上方判断：如果为 NULL，直接返回 false。不过需要注意，后面涉及到排序题目的时候，不能无脑返回 false，需要特殊考虑 NULL 和 NULL 的比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
bool IS_NULL_Compare(CompType type_, const Value &left, const Value &right, const std::vector<Value> left_list, const std::vector<Value> right_list,
                     const std::vector<std::vector<Value>> left_tuple_list, const std::vector<std::vector<Value>> right_tuple_list) {
  if (type_ == CompType::VAL_LIST || type_ == CompType::VAL_VAL || type_ == CompType::VAL_TUPLES) {
    return left.get_null();
  }
  if (!left_list.empty() && type_ == CompType::LIST_VAL) {
    return left_list[0].get_null();
  }
  if (!left_tuple_list.empty() && type_ == CompType::TUPLES_VAL) {
    return left_tuple_list[0][0].get_null();
  }
  return false;
}

update-select

本题要求 update 的更新目标值可以通过子查询得出，子查询第一版本是我的队友完成的，但是在写复杂子查询的时候将整个框架重构了一下。因为在看代码框架的时候发现，用于生成算子的部分是完全独立的，所以完全可以将生成算子的部分改成静态的，从而可以 : “随时随地，STNT -> 算子 -> 结果”。这样设计完之后，想要获取子查询的结果只需要一个 STMT，极大的简化了代码，甚至 update-select 并没有新增什么内容，只是在收集更新的 Value 时，多增一步，如果 Value 是子查询需要转化一下。

需要注意的是，准确说当时因为这个 debug 了好久，where 子句筛选出来的元组集合为空集时，即便子查询搜出来的结果不合法，也算 SUCCESS。
对于子查询，能当作 update 的 Value 的充分必要条件是搜出来的元组数组，或者二维数组，只能是一个元素。如果搜出来是空集，等同于插入 NULL。

STMT -> vector< vector< Value>>

更近一步，设计一个函数，输入 STMT，输出为二维 Value 数组，省去中间的部分。函数设计如下：输入 STMT，输出 数据 + 表头信息。其中 main_tuple 为复杂子查询的内容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
RC OptimizeStage::handle_sub_stmt(Stmt *stmt, std::vector<std::vector<Value>> &tuple_list, TupleSchema &tuple_schema, const Tuple *main_tuple) {
  SelectStmt *select_stmt = static_cast<SelectStmt *>(stmt);
  vector<Table *> tables = select_stmt->tables();
  string table_names;
  for (auto it : tables) table_names += it->name();

  RC rc = RC::SUCCESS;

  // ? 不存在创建好的逻辑算子
  if (!sub_expr_and_logical_oper.contains(table_names)) {
    unique_ptr<LogicalOperator> logical_oper;
    rc = create_logical_plan(stmt, logical_oper);

    if (rc != RC::SUCCESS && rc != RC::UNIMPLEMENTED) return rc;
    ASSERT(logical_oper, "logical operator is null");

    sub_expr_and_logical_oper.insert(make_pair(table_names, std::move(logical_oper)));
  }

  // ? 不存在创建好的物理算子
  if (!sub_expr_and_physical_oper.contains(table_names)) {
    unique_ptr<PhysicalOperator> physical_oper;
    rc = generate_physical_plan(sub_expr_and_logical_oper[table_names], physical_oper);

    if (rc != RC::SUCCESS) return rc;

    sub_expr_and_physical_oper.insert(make_pair(table_names, std::move(physical_oper)));
  }

  PhysicalOperator *physical_oper = sub_expr_and_physical_oper[table_names].get();
  rc = get_tuple_schema(physical_oper, tuple_schema);
  if (rc != RC::SUCCESS) return rc;

  rc = get_tuple_list(physical_oper, tuple_list, main_tuple);
  return rc;
}

RC OptimizeStage::create_logical_plan(Stmt *stmt, unique_ptr<LogicalOperator> &logical_operator) {
  if (nullptr == stmt) {
    return RC::UNIMPLEMENTED;
  }

  return LogicalPlanGenerator::create(stmt, logical_operator);
}

RC OptimizeStage::generate_physical_plan(unique_ptr<LogicalOperator> &logical_operator, unique_ptr<PhysicalOperator> &physical_operator) {
  RC rc = PhysicalPlanGenerator::create(*logical_operator, physical_operator);

  if (rc != RC::SUCCESS) {
    LOG_WARN("failed to create physical operator. rc=%s", strrc(rc));
  }
  return rc;
}

RC OptimizeStage::get_tuple_schema(PhysicalOperator *physical_operator, TupleSchema &tuple_schema) {
  return physical_operator->tuple_schema(tuple_schema);
}

RC OptimizeStage::get_tuple_list(PhysicalOperator *physical_operator, std::vector<std::vector<Value>> &tuple_list, const Tuple *main_tuple) {
  RC rc = physical_operator->open(nullptr, main_tuple);
  if (rc != RC::SUCCESS) {
    LOG_WARN("failed to open sub physical operator. rc=%s", strrc(rc));
    return rc;
  }

  // 将查表结果放入value_list
  while (RC::SUCCESS == (rc = physical_operator->next(main_tuple))) {
    Tuple *tuple = physical_operator->current_tuple();
    std::vector<Value> single_tuple;
    for (int i = 0; i < tuple->cell_num(); i++) {
      Value value;
      tuple->cell_at(i, value);
      single_tuple.push_back(value);
    }
    tuple_list.push_back(single_tuple);
  }

  if (rc != RC::RECORD_EOF) return rc;

  rc = physical_operator->close();
  if (rc != RC::SUCCESS) return rc;

  return RC::SUCCESS;
}

update 中添加有关子查询的部分

如果发现有子查询，通过函数将其转化为二维 Value 数组，如果数组只有一个元素则合法，拿出来；如果数组为空，则等同于 NULL；如果数组不为空，等同一个非法的 Value，注意这里并没有直接返回 FAILURE，因为如果 where 子句筛选集为空集，即便子查询有误也返回 SUCCESS，所以这里通过特意构造非法 Value，如果 where 子句筛选集不为空集，则会识别非法 Value 并返回 FAILURE；如果 where 子句筛选集为空集，则不会有识别环节。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
RC UpdateStmt::create(Db *db, UpdateSqlNode &update, Stmt *&stmt) {
  // 拿到目标表格以及名称以及修改域
  const char *table_name = update.relation_name.c_str();
  Table *table = db->find_table(table_name);

  // 目标表格不存在检查
  if (table == nullptr) {
    LOG_WARN("no such table. db=%s, table_name=%s", db->name(), table_name);
    return RC::SCHEMA_TABLE_NOT_EXIST;
  }
  // 参数非法检查
  if (nullptr == db || nullptr == table_name) {
    LOG_WARN("invalid argument. db=%p, table_name=%p", db, table_name);
    return RC::INVALID_ARGUMENT;
  }

  // 拿到全部修改域
  std::vector<FieldMeta> field_metas;
  for (auto it : update.update_targets) {
    FieldMeta *field_meta = (FieldMeta *)table->table_meta().field(it.attribute_name.c_str());
    // 修改域检查
    if (nullptr == field_meta) {
      return RC::SCHEMA_FIELD_NOT_EXIST;
    }
    field_metas.push_back(*field_meta);
  }

  // 创建筛选 STMT 对象
  std::unordered_map<std::string, Table *> table_map;
  table_map.insert(std::pair<std::string, Table *>(std::string(table_name), table));
  FilterStmt *filter_stmt = nullptr;
  bool flag;
  RC rc = FilterStmt::create(db, table, &table_map, update.conditions.data(), static_cast<int>(update.conditions.size()), filter_stmt, flag);

  // 谓词语句合法检查
  if (rc != RC::SUCCESS) {
    LOG_WARN("failed to create filter statement. rc=%d:%s", rc, strrc(rc));
    return rc;
  }

  // 创建子查询的 STMT 对象
  for (int i = 0; i < (int)update.update_targets.size(); i++) {
    if (update.update_targets[i].is_value == false) {
      Stmt *temp;
      rc = SelectStmt::create(db, update.update_targets[i].sub_select->selection, temp, flag);
      if (rc != RC::SUCCESS) return rc;
      vector<vector<Value>> tuple_list;
      TupleSchema tuple_schema;
      OptimizeStage::reset();
      RC rc = OptimizeStage::handle_sub_stmt(temp, tuple_list, tuple_schema);
      if (rc != RC::SUCCESS) return RC::INVALID_ARGUMENT;
      // 子查询为空值，等同于插入 NULL
      if (tuple_list.empty()) {
        update.update_targets[i].value.set_null(true);
      }
      // 子查询非法，等同于插入非法 Value，如果筛选出来没有更新目标，则无视，否则报错
      else if (tuple_list.size() != 1 || tuple_list[0].size() != 1) {
        update.update_targets[i].value.set_type(AttrType::UNDEFINED);
      } else {
        update.update_targets[i].value = tuple_list[0][0];
      }
      update.update_targets[i].is_value = true;
    }
  }

  // check date validity
  for (auto it : update.update_targets) {
    Value value = it.value;
    if (value.attr_type() == AttrType::DATE) {
      if (!DateType::check_date(value.get_date())) {
        return RC::INVALID_ARGUMENT;
      }
    } else if (value.attr_type() == AttrType::CHARS) {
      if (value.get_string().size() > BP_MAX_TEXT_SIZE) {
        return RC::INVALID_ARGUMENT;
      }
    } else if (value.attr_type() == AttrType::VECTORS) {
      if (value.get_vector_size() > BP_MAX_VECTOR_SIZE) {
        return RC::INVALID_ARGUMENT;
      }
    }
  }

  // 创建 update 的 STMT 对象
  stmt = new UpdateStmt(table, filter_stmt, field_metas, update.update_targets);
  return RC::SUCCESS;
}

alias

order-by

aggregation_and_groupby

create-table-select

vector_rewrite

complex-sub-query

#Competition
miniob 初赛参赛总结
https://dmx20070206.github.io/2024/11/11/miniob/
Author
DM-X~X~X
Posted on
November 11, 2024
Licensed under