OB大赛

2021-09-29

往年OB赛题

OB大赛

参考从0到1打造你的数据库

参考OceanBase大赛miniob代码架构框架设计和说明

官方论坛

参赛宝典

看看参赛宝典

第4章查询处理

参考查询处理

选择运算

一般情况下，当选择率较低时，基于索引的选择算法要优于全表扫描。但在某些情况下，如选择率较高、或者要查找的元组均匀分散在表中，这时索引扫描法的性能可能还不如全表扫描法，因为还需要考虑扫描索引带来的额外开销。

参赛题目

参考参赛题目

其中，其中必做题的多表查询这道题，我们可以思考一下怎么和后面的查询优化关联。weihan学长说这部分不要用笛卡儿积，要考虑各种join，比如hash join和merge join。

在 1b9d1be 这里，做了基础题加上join, insert, null和unique
dev中commit 7aa5bada5df5bbcd68f3fa63904e4b28021dd753 的已经有140分了

basic

优化buffer pool

在storage/default/disk_buffer_pool.cpp/DiskBufferPool::get_this_page(int file_id, PageNum page_num, BPPageHandle *page_handle)中，是得到一个缓存页面用于判断适不适合插入输入，所以对应的页面被访问过了，因此要更改LRU链表。

Frame *f = bp_manager_.get(file_handle->file_desc,page_num);
if(f!=nullptr){
  page_handle->frame = f;
  page_handle->frame->pin_count++;
  //page_handle->frame->acc_time = current_time();
  page_handle->open = true;
  return RC::SUCCESS;
}

在storage/default/disk_buffer_pool.h/BPManager/get(int file_desc, PageNum page_num)，实现了LRU：

Frame *get(int file_desc, PageNum page_num) {
    Node *node = getNode(file_desc,page_num);
    if(node!=nullptr){
      remove(node);
      setHead(node);
      return node ->frame;
    }
    else return nullptr;
}

update

测试用例

增加date字段

语法和词法部分

在sql/parser/lex_sql.l文件中增加词法规则：

[Ii][Nn][Tt]					                   { position=strdup(yytext);RETURN_TOKEN(INT_T);}
[Cc][Hh][Aa][Rr]				                 { position=strdup(yytext);RETURN_TOKEN(STRING_T);}
[Ff][Ll][Oo][Aa][Tt]			               { position=strdup(yytext);RETURN_TOKEN(FLOAT_T);}
[Dd][Aa][Tt][Ee]				                 { position=strdup(yytext);RETURN_TOKEN(DATE_T);}

1	{QUOTE}[0-9]{4}-((0?[1-9])\|(1[0-2]))-((0?[1-9])\|([12][0-9])\|(3[0-1])){QUOTE} {yylval->string=strdup(yytext);position = strdup(yytext);RETURN_TOKEN(DATE);}

如上述，在int, char, float的基础上增加了数据库列的date属性。也增加了对日期值的判断（比如在insert语句中，可以识别"2010-10-9"是一个单独的TOKEN，为DATE）。

在sql/parser/yacc_sql.y中增加标识TOKEN：

1 2	%token DATE_T

1	%token <string> DATE

语法规则部分：

type:
	INT_T { $$=INTS; }
       | STRING_T { $$=CHARS; }
       | FLOAT_T { $$=FLOATS; }
	   | DATE_T { $$=DATES; }
       ;

attr_def:
    ID_get type null_value
		{
			AttrInfo attribute;
			attr_info_init(&attribute, CONTEXT->id, $2, 4, CONTEXT->permit_null);
			create_table_append_attribute(&CONTEXT->ssql->sstr.create_table, &attribute);
			// CONTEXT->ssql->sstr.create_table.attributes[CONTEXT->value_length].name=(char*)malloc(sizeof(char));
			// strcpy(CONTEXT->ssql->sstr.create_table.attributes[CONTEXT->value_length].name, CONTEXT->id); 
			// CONTEXT->ssql->sstr.create_table.attributes[CONTEXT->value_length].type=$2;  
			// CONTEXT->ssql->sstr.create_table.attributes[CONTEXT->value_length].length=4; // default attribute length
			CONTEXT->value_length++;
			CONTEXT->permit_null=0;	//清空
		}

insert语句的推导式是: insert: INSERT INTO ID VALUES row row_list SEMICOLON，row的推导式是：row: LBRACE value value_list RBRACE，因此要在value的推导式中加入对DATE的支持。

value:
	NULLL{
		value_init_null(&CONTEXT->values[CONTEXT->value_length++]);	
	}
    |NUMBER{	
  		value_init_integer(&CONTEXT->values[CONTEXT->value_length++], $1);
		}
    |FLOAT{
  		value_init_float(&CONTEXT->values[CONTEXT->value_length++], $1);
		}
	|DATE {
			$1 = substr($1,1,strlen($1)-2);
  		value_init_date(&CONTEXT->values[CONTEXT->value_length++], $1);
		}		
    |SSS {
			$1 = substr($1,1,strlen($1)-2);
  		value_init_string(&CONTEXT->values[CONTEXT->value_length++], $1);
		}
    ;

在sql/parser/parse_defs.h中定义date字段的标识（因为create语句在内存中是以Query数据结构的形式保存的，Query中要记录每个列属性的类型，这个列属性的类型就由enum类型的AttrType表示）。

//属性值类型
//最高位为1表示允许null
typedef enum { 
  UNDEFINED,
  CHARS, 
  INTS, 
  FLOATS,
  DATES,
  TEXTS
} AttrType;

还有要加入value_init_date()函数，具体怎么定义和实现，可以参考value_init_string()的定义和实现。

接下来思考：在各种SQL语句中，它们是怎么支持date字段的。

create table t1(birthday date);

update t1 set birthday="2000-10-9";

select birthday from t1;

insert into t1 values("2000-10-12");

根据本片文章中源码/调试跟踪/创建表的记录情况，我认为create语句是不会更改的。

select语句部分

我怀疑select语句相关代码可能要更改，在查询到page中的tuple后，要把这个tuple转换为一行字符串的形式输出，而且要按照特定格式输出，此时肯定要判断出date属性类型，然后进行相应操作。

在sql/executor/tuple.cpp/add_record(const char *record)中，是要将page中的一个record转换为Tuple类型（Tuple包含很多TupleValue的指针，依次表示一个元组的很多属性值，TupleValue是属性值的表示），所以在这里要考虑很多属性值类型，然后将record中对应位置的bytes转换为TupleValue

void TupleRecordConverter::add_record(const char *record) {
  const TupleSchema &schema = tuple_set_.schema();
  Tuple tuple;
  const TableMeta &table_meta = table_->table_meta();
  for (const TupleField &field : schema.fields()) {
    const FieldMeta *field_meta = table_meta.field(field.field_name());
    assert(field_meta != nullptr);
    switch (field_meta->type()) {
      case INTS: {
        int value = *(int*)(record + field_meta->offset());
        tuple.add(value);
      }
      break;
      case FLOATS: {
        float value = *(float *)(record + field_meta->offset());
        tuple.add(value);
      }
        break;
      case CHARS: {
        const char *s = record + field_meta->offset();  // 现在当做Cstring来处理
        tuple.add(s, strlen(s));
      }
      break;
      default: {
        LOG_PANIC("Unsupported field type. type=%d", field_meta->type());
      }
    }
  }

  tuple_set_.add(std::move(tuple));
}

但是上述代码没有考虑date属性值类型的情况。

在sql/executor/value.h中定义了不同的TupleValue，比如：

class StringValue : public TupleValue {
public:
  explicit StringValue(const char *value, int len) : value_(value, len), type_(CHARS){
  }
  explicit StringValue() : value_("NULL", 4), type_(CHARS), is_null_(true) {
  }
  void to_string(std::ostream &os) const override;

  void set_value(std::string &value);

  const void *get_value() const override;

  int get_type() const override;

  int compare(const TupleValue &other) const override;
  
  bool is_null() const override;
private:
  std::string value_;
  int type_;
  bool is_null_ = false;
};

这个是string字符串类型的TupleValue，叫做StringValue。我们需要自己定义一个DateValue的TupleValue。

我觉得insert语句相关代码也要更改，因为要把Query类型的数据结构转换为实际在page中存储的元组，要判断date属性类型，然后进行相应的格式转换。

最后顺藤摸瓜，找到了这个函数的一行语句: storage/common/table.cpp/insert_record(Trx *trx, int value_num, const Value *values)。

1	RC rc = make_record(value_num, values, record_data);

bug

类似于where s="1998-12-9"，可能错弄成字符串和date了

一次插入多条数据

我发现在storage/default/default_handler.cpp/DefaultHandler::insert_record(Trx *trx, const char *dbname, const char *relation_name, int value_num, const Value *values, int row_num, const int *row_end)，这个函数里，实现了一次插入多条数据，所以我主要的工作可能还是在语法分析上，主要是改yaac_sql.y文件。

查询元数据校验

在sql/executor/execute_stage.cpp/check_select_meta_data(const Selects &selects, const char *db, SessionEvent *session_event)中，对selects中的表，属性和条件进行校验，主要判断表和涉及的属性是否存在（所以需要db参数）；如果是多表连接，那么属性一定要带表明前缀，如：school.salary。

多表连接

在sql/executor/execute_stage.cpp/ExecuteStage::do_select(const char *db, Query *sql, SessionEvent *session_event)中，初始化了很多SelectExeNode，但是这些node中的TupleSchema只包含查询属性，并不包含表的所有属性，这就会导致多表连接的一个问题：

假设，t1有col1和col2属性，t2有col1和col2属性，然后执行SQL：select t1.col, t2.col2 from t1,t2 where t1.col2==t2.col2。这些node执行查询后，产生的结果TupleSet中也只包含查询属性，在这个例子中，对t1初始化了执行结点node1，产生tupleset1，对t2初始化了执行结点node2，产生tupleset2，但是tupleset1只包含col1属性，tupleset2只包含col2属性，这样的话，如何基于tupleset1和tupleset2进行多表连接？我觉得以一种解决方法是，node1中不仅要包含查询属性，还要包含必要的在多表连接中需要用到的属性。A

聚合运算

在sql/parser/lex_sql.l文件中，添加了词法规则：

[Cc][Oo][Uu][Nn][Tt]  position=strdup(yytext); RETURN_TOKEN(COUNT);
[Mm][Aa][Xx]          position=strdup(yytext); RETURN_TOKEN(MAX);
[Mm][Ii][Nn]          position=strdup(yytext); RETURN_TOKEN(MIN);
[Aa][Vv][Gg]          position=strdup(yytext); RETURN_TOKEN(AVG);

在sql/parser/yacc_sql.y文件中，添加标识TOKEN：

%token 
        COUNT
        MAX
        MIN
        AVG

添加语法规则：

select_attr:
    COUNT LBRACE ID DOT ID RBRACE attr_list {
			RelAttr attr;
			relation_attr_with_agg_init(&attr, "COUNT", $3, $5);
			selects_append_attribute(&CONTEXT->ssql->sstr.selection, &attr);
    }

以上只是一个例子，其实关于COUNT的语法规则还有别的，以及AVG等其他的规则，而且写的都和上面的差不多。relation_attr_with_agg_init()是在sql/parser/parse_defs.h定义的，实现在sql/parser/parse.cpp中，构造一个RelAttr对象。

在sql/executor/execution_node.cpp中实现AggregationExeNode的很多函数。

在sql/executor/execute_stage.cpp/ExecuteStage::do_select(const char *db, Query *sql, SessionEvent *session_event)，添加对聚合的支持：比如，在条件过滤后建立AggregationExeNode来进行聚合运算

1
2
3

AggregationExeNode node;
node.init(trx, &res_table, std::move(agg_infos));
node.execute(agg_res, columns);

多表join操作

一次插入多条数据
更改词法语法规则
更改parser_defs.h中的Inserts结构体

支持NULL类型

添加词法语法规则
在parser_defs.h中加入对insert, create中null的支持
更改table_mate.h可以在表的元数据中加入对null的支持；还要看数据库启动时如何加载表的元数据的
查看select, insert, create, update的流程，看看有没有需要加入null支持的；在输出的时候，有的空字段可能要输出NULL
聚合也要改一下，比如t表中有5个行，但是这5行的col2属性有2个是非空的，那么select count(col2) from t的结果是2；如果某个属性col2全是空的，那么select max(col2) from t的结果就是NULL；
底层的表结构该如何支持null

insert对null的支持

在storage/common/table.cpp/Table::insert_record(Trx *trx, int value_num, const Value *values)

1	RC rc = make_record(value_num, values, record_data);

要改下形成的record结构, 使得它能够标识哪些属性是null的。然后在Value结构体中加入对null的标识。然后改下make_record()函数进行相关校验，以及标识哪些属性是null的。

TupleField也要支持null，用于表示这个属性是否是nullable的，这样在insert的元数据判断时，要检查属性是否是nullable的。

Value也要支持null，当在insert的时候，就可以表示这个插入的值是不是null。

在初始化page页面的时候，需要用到record_size来初始化page的头部，比如根据record_size来计算页面能够容纳多少个record。在table.cpp/Table::insert_record(Trx *trx, Record *record)中有个代码：

1	rc = record_handler_->insert_record(record->data, table_meta_.record_size(), &record->rid);

但是幸运的是，不用改这部分，因为代码写的扩展性比较好。

select对null的支持

在sql/executor/tuple.cpp/TupleRecordConverter::add_record(const char *record) 中从record字节数组中读取想要的列，这里估计要改下。

TupleValue要支持null，当add_record()函数读取到schema中的某个属性是null的话，就用支持null的TupleValue来存储。

where条件部分：在condition进行filter的时候，要知道null和谁比较都是false。如果条件中有一个是null值，则可以不做类型兼容性判断。

create对null的支持

table_meta要能够保存哪些属性是nullable的。

在/storage/common/table.cpp/Table::create(const char *path, const char *name, const char *base_dir, int attribute_count, const AttrInfo attributes[])中，改变对table_meta的初始化，table_meta中要保存哪些属性是nullable的，每个属性的null标识指针（指向record中哪个bit，这个bit表示对应属性是否是null）。field_meta中增加了nullable, nulltagoffset, nulltaglen属性，然后它的init(), to_json(), from_json()都要改。

AttrInfo结构体也要支持null，表示这个属性是不是nullable的。attr_info_init()函数要默认AttrInfo的nullable是false。

update对null的支持

修改了执行阶段的对于update的校验。

索引

普通索引的话就插入数据的时候key是null不给它建索引，按照索引查找的时候本身也用不到null数据， is null单独处理，not null正好遍历存在索引的数据就行了。如果是condition中含有null，则也不用索引。

update要更新索引，如果update某个null的属性为非null，那么就要添加索引项；如果update某个非null属性为null，就要删除索引项。

在table.cpp中，要更新插入索引和删除索引项的代码，当对应属性为null时，直接返回。

在table.cpp中，创建IndexScanner时，如果发现是针对is null创建的，就直接返回nullptr，意思说不对is null的用索引查找。

但是，is null用不到索引，可能要全表扫描，效率不好。还有一个问题是，我没有判断当is null时不从索引查找，这就意味着，当在nullable的属性上建立索引时，并查找这个属性is null的所有行，可能完全查找不到，因为是从索引中查找的。
支持is not null吗

多表对null的支持

索引

如果没有where语句就不用索引来查找
如果是is null的where语句，也不用索引来查找。

子查询

condition要改，支持大于tupleset之类的，因为子查询要用。

查询支持表达式

expression: result file difference(`-` is yours and `+` is base)
 SELECT ID,-(COL2*(-1)+1)+(COL4+2)*(COL1+COL3*2),(4+COL2)*COL3/2 FROM EXP_TABLE WHERE -(COL2*(-1)+1)+(COL4+2)*(COL1+COL3*2) > (4+COL2)*COL3/2;
-FAILURE
+1 | 10.5 | 2.5
+2 | 36 | 5.5
+3 | 81 | 20
+ID | -(COL2*(-1)+1)+(COL4+2)*(COL1+COL3*2) | (4+COL2)*COL3/2
 SELECT ID,COL1,COL2,COL3,COL4,6-(COL2*(1+COL1))+(COL4+2)/(1+COL1*4+COL3*2) FROM EXP_TABLE WHERE 6-(COL2*(1+COL1))+(COL4+2)/(1+COL1*4+COL3*2) > 5;
-2 | 2 | -2 | 5.5 | 1 | 12.1
+2 | 2 | -2 | 5.5 | 1 | 12.15
 ID | COL1 | COL2 | COL3 | COL4 | 6-(COL2*(1+COL1))+(COL4+2)/(1+COL1*4+COL3*2)
 SELECT ID,COL1,COL2,COL3,COL4,3*COL1/(COL2+2) FROM EXP_TABLE WHERE 3*COL1/(COL2+2) > 1;
 3 | 3 | 4 | 5 | 4 | 1.5
 ID | COL1 | COL2 | COL3 | COL4 | 3*COL1/(COL2+2)
 SELECT ID,3*COL1/(COL2+2) FROM EXP_TABLE WHERE 3*COL1/(COL2+2)+1/0 > 1;
 ID | 3*COL1/(COL2+2)
 SELECT * FROM EXP_TABLE WHERE 1/0 = 1/0;
 ID | COL1 | COL2 | COL3 | COL4

我们要重新设计一整套架构，要对原来的代码进行一番重构，从语法分析阶段到查询执行阶段，很多都要重构，下面具体分析该如何做。总的来说，以前的select clause中只有属性，聚合，但是现在要有表达式（基于属性和非null值）和聚合，以前的condition clause中有属性或值比较属性或值，但是现在要有表达式（基于属性和值）比较表达式，这些变化对后面的架构有重要影响。

测试样例

create table texp1(i int, f float, c char, d date);
insert into texp1 values (1, 4.221, "abc", "1998-12-9");
insert into texp1 values (2, 2.986, "arf", "1990-7-23");
insert into texp1 values (6, 4.523, "ghi", "2009-3-21");
insert into texp1 values (12, 4.523, "gss", "2005-5-13");
# 基本测试 ---------------------------------------------------------------
select * from texp1;
select f, d, c, i from texp1;
select texp1.f, texp1.d, texp1.c, texp1.i from texp1;
select * from texp1 where c="abc";
select * from texp1 where d="2009-3-21";
select * from texp1 where f=2.986 and i>=1;
# 单表单条件的加减乘除 -----------------------------------------------------
select i*5 from texp1;
select i*4.3 from texp1 where i*2>3;
select i*5.353682 from texp1 where i*2.1>3.2;
select i/3 from texp1 where i*f=4.221;
select * from texp1 where i*f<20;
select * from texp1 where i=f-3.221;
select * from texp1 where i/2>f;
select * from texp1 where i*f>i+f;
select * from texp1 where (i+f)*(i-f)>(i+f)/(i-f);
select 2 from texp1 where i>0;        # 这个不做要求
select * from texp1 where 3>0;
select -i, -f from texp1;
select i+f, c, d from texp1;    
select * from texp1 where (i+f)*(i-f)>(i+f)/(i-f) and c="arf";
select * from texp1 where -0 < -i+f;
select * from texp1 where (4+f)*i/2 > (5-1)*1.5; // test wrong
select i/0 from texp1 where i>3;      # select clause中异常运算：除0错误，直接返回NULL
select d/0 from texp1 where i>3;      # select clause中异常运算：参与运算的属性不是int或float中的一种，直接返回NULL
select "1998-12-9"/0 from texp1 where i>3;  # selece clause中异常运算：参与运算的属性不是int或float中的一种，
select count(i), i*f from texp1 where i>3;  # select clause中聚合属性不能和表达式同时存在
select count(i), d, 4 from texp1;              # select clause中聚合属性不能和单个属性或值同时存在
select * from texp1 where i/0=f/0;    # where clause中异常运算：除0错误
select * from texp1 where d*2>3.0;    # where clause中异常运算：参与运算的属性不是int或float中的一种
select * from texp1 where -d>"1998-12-9" # where clause中异常运算：参与运算的属性不是int或float中的一种
select * from texp1 where i*2>d       # where clause中异常运算：非int, float得类型不能和表达式进行比较，因为表达式肯定是int或float结果。where clause中存在非int, float类型，当且仅当condition两端的表达式都只有一个项而且类型相同
select * from nonexist_table;           # from clause中不存在的表
select non_exist_table.i from texp1;    # select clause中不存在的表
select non_exist_col from texp1;        # select clause中不存在的属性
select i-non_exist_col from texp1;      # select clause中不存在的属性
select * from texp1 where (i+f)*(i-nonexist_col)>0; # where clause中不存在的属性
select * from texp1 where (i+f)>0 and (i-nonexist_table.f)>0; # where clause中不存在的表
# 多表单条件的加减乘除 -----------------------------------------------------
create table texp2(i int, f float, c char, d date);
insert into texp2 values (1, 4.221, "abc", "1998-12-9");
insert into texp2 values (2, 2.986, "arf", "1990-7-23");
insert into texp2 values (6, 4.523, "ghi", "2009-3-21");
insert into texp2 values (12, 4.523, "gss", "2005-5-13");

create table texp4(i int, f float, c char, d date);

select * from texp1, texp2 where texp1.i*texp1.f>texp2.i+texp2.f;  # 
select texp1.i, texp1.c, (texp1.i + texp2.i)*(texp1.f + texp2.f), texp2.d from texp1, texp2 where texp1.i*texp1.f>texp2.i+texp2.f and texp1.c>"arf";
select texp1.i, texp1.c, (texp1.i + texp2.i)*(texp1.f + texp2.f), texp2.d from texp1, texp2 where texp1.i*texp1.f>texp2.i+texp2.f and texp1.c = null;

select * from texp1, texp2 where i>f;   # where clause中表名不存在

create table texp3(i1 int, i2 float, i3 int, i4 float);
insert into texp3 values(1, 5.45, 3, 4.25);
select -(i2*(-1)+1)+(i4+2)*(i1+i3*2) from texp3;

Selects结构

原来的Selects结构：

// struct of select
typedef struct {
  size_t    attr_num;               // Length of attrs in Select clause
  RelAttr   attributes[MAX_NUM];    // attrs in Select clause
  size_t    relation_num;           // Length of relations in Fro clause
  char *    relations[MAX_NUM];     // relations in From clause
  size_t    condition_num;          // Length of conditions in Where clause
  Condition conditions[MAX_NUM];    // conditions in Where clause
} Selects;

但是这个结构已经不适用了，因为RelAttr和Condition不可能支持表达式了。

新的架构可以是：

typedef struct {
  size_t       attr_num;
  RelAttrExp   attr_exps[MAX_NUM];  // 删掉RelAttr，增加RelAttrExp
  size_t       relation_num;
  char *       relations[MAX_NUM];
  size_t       condition_num;
  ConditionExp condition_exps[MAX_NUM]; // 删掉Condition，增加ConditionExp
}AdvSelects; // advanced selects: 支持条件表达式

RelAttrExp结构

typedef enum {
  STARTCALOP,
  PLUS_OP,
  MINUS_OP,
  TIME_OP,
  DIVIDE_OP,
  ENDCALOP
} CalOp;

struct ExpList;
// 5; a; a*5; a/5; a/b; 5/b; *等只含有乘除法，不含加减法的表达式
typedef struct Exp {
  // 若have_brace==true，则Exp里面只有explist有效
  // is_attr为真，relation_name和attribute_name有效
  // is_attr为假，value有效
  // left_exp默认为nullptr, 若为nullptr，则calop属性失效
  int have_brace;                 // 表达式外面是否有括号包围
  ExpList *explist;               // 若have_brace==true，则Exp里面只有explist有效
    
  int is_attr;           // 标识是否是属性
  char *relation_name;   // relation name (may be NULL) 表名
  char *attribute_name;  // attribute name              属性名
  Value value;           // 表达式中的常量值
  Exp *left_exp;        // 为nullptr,表示这个结点是表达式树的叶子结点，而且后面的CalOp属性失效
  CalOp calop;           // 只能是乘除号
    
  int num;                  // 表达式中item的个数，这个item可以是*, id或value
} Exp;

// 可以包含一个Exp，也可以用加减号将多个ExpList连接在一起
typedef struct ExpList {
  // left_explist为假时, calop失效
  Exp *exp;
  ExpList *left_explist;
  CalOp calop;                    // 只能是加减号
    
  int num;                  // 表达式中item的个数，这个item可以是*, id或value
} ExpList;

typedef struct {
  AggType agg_type;   // 标识是否是聚合查询以及是什么聚合查询，NOTAGG表示不是
  ExpList *explist;    // 表达式
  int is_attr;        // 如果是聚合属性，则这个is_attr判断是属性还是数值
  char *agg_relation_name;  // 聚合属性的表名
  char *agg_attribute_name; // 聚合属性的属性名
  AggValType agg_val_type;  // 聚合属性的数值类型
  AggVal agg_val;           // 聚合属性的数值
    
  int num;                  // 当agg_type==NOTAGG时有效, 表达式中item的个数，这个item可以是*, id或value
}RelAttrExp;

ConditionExp结构

原来的Condition结构是：

typedef struct _Condition {
  int left_is_attr;    // TRUE if left-hand side is an attribute
                       // 1时，操作符左边是属性名，0时，是属性值
  Value left_value;    // left-hand side value if left_is_attr = FALSE
  RelAttr left_attr;   // left-hand side attribute
  CompOp comp;         // comparison operator
  int right_is_attr;   // TRUE if right-hand side is an attribute
                       // 1时，操作符右边是属性名，0时，是属性值
  RelAttr right_attr;  // right-hand side attribute if right_is_attr = TRUE 右边的属性
  Value right_value;   // right-hand side value if right_is_attr = FALSE
} Condition;

可以改为：

typedef struct {
  ExpList *left;
  ExpList *right;
  CompOp comp; 
} ConditionExp;

改变value_init_float()函数，使得value可以存储float的字符串完整字符串形式。

在do_select()函数中判断AdvSelects结构是否是简单select形式（select clause只包含简单的属性, where clause中只包含属性或值之间的比较，不包含表达式之间的比较），如果是，就将AdvSelects重构为老版本的Selects，然后走老路线；否则，就直接走新路线。

filter要支持左右两边可以是表达式或者tuplset，支持表达式是为了select语句中where语句可以有表达式，支持tupleset是为了支持嵌套子查询。

当我有了要选择的很多表以及很多condition，我该如何得到最终的tupleset？我需要一个SelectionExeNode，来执行支持表达式比较的单表查询；我需要一个JoinExeNode来执行支持表达式比较的多表连接；我需要一个CartExeNode来执行多个表的笛卡儿积；我需要一个projection来执行投影操作。

selects的destroy函数要改，可能还要涉及到一些属性的destroy函数。

lex文件中加入加减乘除的token

yacc文件中的递推式设计的有问题

修改lex和yacc文件

 /* @author: huahui  @what for: expression <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/   
"+"       RETURN_TOKEN(PLUS_OP);
"-"       RETURN_TOKEN(MINUS_OP);
"/"       RETURN_TOKEN(DIVIDE_OP);
 /* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>*/

/* @author: huahui  @what for: expression <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/
%token
        PLUS_OP
        MINUS_OP
        DIVIDE_OP
        STAR
/* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>*/



/* @author: huahui &what for: 聚合
 * 由于max(1.999)需要完整保留1.999，因此lex_sql.l文件中解析到FLOATS时需要保存float值和字符串
 * -----------------------------------------------------------------------------------------------------
 */
%union {
  struct _Attr *attr;
  struct _Condition *condition1;
  struct _Value *value1;
  char *string;
  int number;
  float floats;
  char *position;
  struct {
    float floats;
    char *str;
  } floatsAndStr;
  void *exp;       /* @author: huahui  @what for: expression */
  void *exp_list;  /* @author: huahui  @what for: expression */
}
/* ----------------------------------------------------------------------------------------------*/

//非终结符

%type <number> type;
%type <condition1> condition;
%type <value1> value;
%type <number> number;
/* @author: huahui  @what for: expression <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/
%type <exp> exp;
%type <exp> exps;
%type <exp> exps2;
%type <exp_list> exp_list;
%type <exp_list> exp_list2;
/* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>*/
%%


select:
  SELECT relattrexp FROM ID rel_list where SEMICOLON {
    selects_append_relation(&CONTEXT->ssql->sstr.selection, $4);
    CONTEXT->ssql->flag=SCF_SELECT;
    //临时变量清零
    CONTEXT->condition_length=0;
    CONTEXT->from_length=0;
    CONTEXT->select_length=0;
    CONTEXT->value_length = 0;
  }
  | SELECT relattrexp FROM ID join where SEMICOLON
  {
     selects_append_relation(&CONTEXT->ssql->sstr.selection, $4);
     CONTEXT->ssql->flag=SCF_SELECT;
     //临时变量清零
     CONTEXT->condition_length=0;
     CONTEXT->from_length=0;
     CONTEXT->select_length=0;
     CONTEXT->value_length = 0;
  }
  ;
  
relattrexp:
  exp_list relattrexp2 {
    RelAttrExp exp;
    exp.agg_type = NOTAGG;
    exp.explist = (ExpList *)($1);
    exp.num = exp.explist->num;
    advselects_append_relattrexp(&CONTEXT->ssql->sstr.adv_selection, &exp);
  }
    /* @author: huahui 
     * @what for: 必做题，聚合查询 
     * -----------------------------------------------------------------------------------------------------------------
     */
    | COUNT LBRACE ID RBRACE relattrexp2 {
            RelAttrExp exp;
            relation_agg_relattrexp_init(&exp, AGGCOUNT, NULL, $3);
            advselects_append_relattrexp(&CONTEXT->ssql->sstr.adv_selection, &exp);
        }
        | COUNT LBRACE STAR RBRACE relattrexp2 {
            RelAttrExp exp;
            relation_agg_relattrexp_init(&exp, AGGCOUNT, NULL, "*");
            advselects_append_relattrexp(&CONTEXT->ssql->sstr.adv_selection, &exp);
        }
        | COUNT LBRACE ID DOT ID RBRACE relattrexp2 {
            RelAttrExp exp;
            relation_agg_relattrexp_init(&exp, AGGCOUNT, $3, $5);
            advselects_append_relattrexp(&CONTEXT->ssql->sstr.adv_selection, &exp);
        }
        | COUNT LBRACE ID DOT STAR RBRACE relattrexp2 {
            RelAttrExp exp;
            relation_agg_relattrexp_init(&exp, AGGCOUNT, $3, "*");
            advselects_append_relattrexp(&CONTEXT->ssql->sstr.adv_selection, &exp);
        }
        | COUNT LBRACE NUMBER RBRACE relattrexp2 {
            RelAttrExp exp;
            relation_agg_relattrexp_init(&exp, AGGCOUNT, NULL, "*");
            exp.is_attr = 0;
            exp.agg_val_type = AGGNUMBER;
            exp.agg_val.intv = $3;
            advselects_append_relattrexp(&CONTEXT->ssql->sstr.adv_selection, &exp);
        }
        | COUNT LBRACE FLOAT RBRACE relattrexp2 {
            RelAttrExp exp;
            relation_agg_relattrexp_init(&exp, AGGCOUNT, NULL, "*");
            exp.is_attr = 0;
            exp.agg_val_type = AGGFLOAT;
            exp.agg_val.floatv = ($3).floats;
            exp.agg_val.str = strdup(($3).str);
            advselects_append_relattrexp(&CONTEXT->ssql->sstr.adv_selection, &exp);
        }
    | MAX LBRACE ID RBRACE relattrexp2 {
            RelAttrExp exp;
            relation_agg_relattrexp_init(&exp, AGGMAX, NULL, $3);
            advselects_append_relattrexp(&CONTEXT->ssql->sstr.adv_selection, &exp);
        }
        | MAX LBRACE STAR RBRACE relattrexp2 {
            RelAttrExp exp;
            relation_agg_relattrexp_init(&exp, AGGMAX, NULL, "*");
            advselects_append_relattrexp(&CONTEXT->ssql->sstr.adv_selection, &exp);
        }
        | MAX LBRACE ID DOT ID RBRACE relattrexp2 {
            RelAttrExp exp;
            relation_agg_relattrexp_init(&exp, AGGMAX, $3, $5);
            advselects_append_relattrexp(&CONTEXT->ssql->sstr.adv_selection, &exp);
        }
        | MAX LBRACE NUMBER RBRACE relattrexp2 {
            RelAttrExp exp;
            relation_agg_relattrexp_init(&exp, AGGMAX, NULL, "*");
            exp.is_attr = 0;
            exp.agg_val_type = AGGNUMBER;
            exp.agg_val.intv = $3;
            advselects_append_relattrexp(&CONTEXT->ssql->sstr.adv_selection, &exp);
        }
        | MAX LBRACE FLOAT RBRACE relattrexp2 {
            RelAttrExp exp;
            relation_agg_relattrexp_init(&exp, AGGMAX, NULL, "*");
            exp.is_attr = 0;
            exp.agg_val_type = AGGFLOAT;
            exp.agg_val.floatv = ($3).floats;
            exp.agg_val.str = strdup(($3).str);
            advselects_append_relattrexp(&CONTEXT->ssql->sstr.adv_selection, &exp);
        }
    | MIN LBRACE ID RBRACE relattrexp2 {  
            RelAttrExp exp;
            relation_agg_relattrexp_init(&exp, AGGMIN, NULL, $3);
            advselects_append_relattrexp(&CONTEXT->ssql->sstr.adv_selection, &exp);
        }
        | MIN LBRACE STAR RBRACE relattrexp2 {
            RelAttrExp exp;
            relation_agg_relattrexp_init(&exp, AGGMIN, NULL, "*");
            advselects_append_relattrexp(&CONTEXT->ssql->sstr.adv_selection, &exp);
        }
        | MIN LBRACE ID DOT ID RBRACE relattrexp2 {
            RelAttrExp exp;
            relation_agg_relattrexp_init(&exp, AGGMIN, $3, $5);
            advselects_append_relattrexp(&CONTEXT->ssql->sstr.adv_selection, &exp);
        }
        | MIN LBRACE NUMBER RBRACE relattrexp2 { 
            RelAttrExp exp;
            relation_agg_relattrexp_init(&exp, AGGMIN, NULL, "*");
            exp.is_attr = 0;
            exp.agg_val_type = AGGNUMBER;
            exp.agg_val.intv = $3;
            advselects_append_relattrexp(&CONTEXT->ssql->sstr.adv_selection, &exp);
        }
        | MIN LBRACE FLOAT RBRACE relattrexp2 {
            RelAttrExp exp;
            relation_agg_relattrexp_init(&exp, AGGMIN, NULL, "*");
            exp.is_attr = 0;
            exp.agg_val_type = AGGFLOAT;
            exp.agg_val.floatv = ($3).floats;
            exp.agg_val.str = strdup(($3).str);
            advselects_append_relattrexp(&CONTEXT->ssql->sstr.adv_selection, &exp);
        }
    | AVG LBRACE ID RBRACE relattrexp2 {
            RelAttrExp exp;
            relation_agg_relattrexp_init(&exp, AGGAVG, NULL, $3);
            advselects_append_relattrexp(&CONTEXT->ssql->sstr.adv_selection, &exp);
        }
        | AVG LBRACE STAR RBRACE relattrexp2 {
            RelAttrExp exp;
            relation_agg_relattrexp_init(&exp, AGGAVG, NULL, "*");
            advselects_append_relattrexp(&CONTEXT->ssql->sstr.adv_selection, &exp);
        }
        | AVG LBRACE ID DOT ID RBRACE relattrexp2 {
            RelAttrExp exp;
            relation_agg_relattrexp_init(&exp, AGGAVG, $3, $5);
            advselects_append_relattrexp(&CONTEXT->ssql->sstr.adv_selection, &exp);
        }
        | AVG LBRACE NUMBER RBRACE relattrexp2 {
            RelAttrExp exp;
            relation_agg_relattrexp_init(&exp, AGGAVG, NULL, "*");
            exp.is_attr = 0;
            exp.agg_val_type = AGGNUMBER;
            exp.agg_val.intv = $3;
            advselects_append_relattrexp(&CONTEXT->ssql->sstr.adv_selection, &exp);
        }
        | AVG LBRACE FLOAT RBRACE relattrexp2 {
            RelAttrExp exp;
            relation_agg_relattrexp_init(&exp, AGGAVG, NULL, "*");
            exp.is_attr = 0;
            exp.agg_val_type = AGGFLOAT;
            exp.agg_val.floatv = ($3).floats;
            exp.agg_val.str = strdup(($3).str);
            advselects_append_relattrexp(&CONTEXT->ssql->sstr.adv_selection, &exp);
        }
    /* ------------------------------------------------------------------------------------------------------------
     */
    ;
    
relattrexp2:
  /* empty*/
  | COMA relattrexp
  ;

/* exp_list是一个完整的支持加减乘除的表达式，它用加减将至少一个的exps连接起来
 */
exp_list:
  exps exp_list2 {
    ExpList *explist_left = (ExpList *)malloc(sizeof(ExpList));
    explist_left->exp = (Exp *)($1);
    explist_left->left_explist = NULL;
    explist_left->calop = STARTCALOP;
    explist_left->num = explist_left->exp->num;
    if($2){
      ExpList *explist_right = (ExpList *)($2);
      while(explist_right->left_explist) {
        explist_right->num += explist_left->num;
        explist_right = explist_right->left_explist;
      }
      explist_right->num += explist_left->num;
      explist_right->left_explist = explist_left;
      $$ = $2;
    }
    else {
      $$ = (void *)explist_left;
    }
  }
  ;
  
exp_list2:
  /* empty*/ {
    $$ = NULL;
  }
  | PLUS_OP exp_list {
    ExpList *explist_right = (ExpList *)($2);
    while(explist_right->left_explist) {
      explist_right = explist_right->left_explist;
    }
    explist_right->calop = PLUS_OP;
    $$ = $2;
  }
  | MINUS_OP exp_list {
    ExpList *explist_right = (ExpList *)($2);
    while(explist_right->left_explist) {
      explist_right = explist_right->left_explist;
    }
    explist_right->calop = MINUS_OP;
    $$ = $2;
  }
  ;


/* exps是一个完整的支持乘除的表达式，它用乘除将很多exp连接起来，exp可以是属性，值或者括号括进来的东西exp_list
 */
exps:
  exp exps2 {
    if($2){
      Exp *exp_left = (Exp *)($1);
      Exp *exp_right = (Exp *)($2);
      while(exp_right->left_exp) {
        exp_right->num += exp_left->num;
        exp_right = exp_right->left_exp;
      }
      exp_right->num += exp_left->num;
      exp_right->left_exp = exp_left;
      $$ = $2;
    } else {
      $$ = $1;
    }
  }
  ;

exps2:
  /* empty*/ {
    $$ = NULL;
  }
  | STAR exps {
    Exp *exp_right = (Exp *)($2);
    while(exp_right->left_exp) {
      exp_right = exp_right->left_exp;
    }
    exp_right->calop = TIME_OP;
    $$ = $2;
  }
  | DIVIDE_OP exps {
    Exp *exp_right = (Exp *)($2);
    while(exp_right->left_exp) {
      exp_right = exp_right->left_exp;
    }
    exp_right->calop = DIVIDE_OP;
    $$ = $2;
  }
  ;

/* exp可以是属性，值或者括号括进来的东西exp_list
 */
exp:
  STAR {
    Exp *exp = (Exp *)malloc(sizeof(Exp));
    exp->have_brace = 0;
    exp->explist = NULL;
    exp->is_attr = 1;
    exp->relation_name = NULL;
    exp->attribute_name = strdup("*");
    exp->left_exp = NULL;
    exp->calop = STARTCALOP;
    exp->num = 1;
    $$ = (void *)exp;
  }
  | ID {
    Exp *exp = (Exp *)malloc(sizeof(Exp));
    exp->have_brace = 0;
    exp->explist = NULL;
    exp->is_attr = 1;
    exp->relation_name = NULL;
    exp->attribute_name = strdup($1);
    exp->left_exp = NULL;
    exp->calop = STARTCALOP;
    exp->num = 1;
    $$ = (void *)exp;
  }
  | ID DOT ID {
    Exp *exp = (Exp *)malloc(sizeof(Exp));
    exp->have_brace = 0;
    exp->explist = NULL;
    exp->is_attr = 1;
    exp->relation_name = strdup($1);
    exp->attribute_name = strdup($3);
    exp->left_exp = NULL;
    exp->calop = STARTCALOP;
    exp->num = 1;
    $$ = (void *)exp;
  }
  | ID DOT STAR {
    Exp *exp = (Exp *)malloc(sizeof(Exp));
    exp->have_brace = 0;
    exp->explist = NULL;
    exp->is_attr = 1;
    exp->relation_name = strdup($1);
    exp->attribute_name = strdup("*");
    exp->left_exp = NULL;
    exp->calop = STARTCALOP;
    exp->num = 1;
    $$ = (void *)exp;
  }
  | value {
    Exp *exp = (Exp *)malloc(sizeof(Exp));
    exp->have_brace = 0;
    exp->is_attr = 0;
    exp->explist = NULL;
    exp->relation_name = NULL;
    exp->attribute_name = NULL;
    exp->value = CONTEXT->values[CONTEXT->value_length - 1];
    exp->left_exp = NULL;
    exp->calop = STARTCALOP;
    exp->num = 1;
    $$ = (void *)exp;
  }
  | LBRACE exp_list RBRACE {
    Exp *exp = (Exp *)malloc(sizeof(Exp));
    exp->have_brace = 1;
    exp->explist = (ExpList *)($2);
    exp->num = exp->explist->num;
    $$ = (void *)exp;
  }
  ;

rel_list:
    /* empty */
    | COMMA ID rel_list {	
				selects_append_relation(&CONTEXT->ssql->sstr.selection, $2);
		  }
    ;

where:
  /* empty*/
  | WHERE condition_exps {
  
  }
  ;
  
condition_exps:
  | condition_exp {
  
  }
  | condition_exp AND condition_exps {
  
  }
  ;
  
condition_exp: 
  exp_list comOp exp_list {
    ExpList *explist_left = (ExpList *)($1);
    ExpList *explist_right = (ExpList *)($3);
    ConditionExp cond_exp;
    cond_exp.left = explist_left;
    cond_exp.right = explist_right;
    cond_exp.comp = CONTEXT->comp;
    advselects_append_conditionexp(&CONTEXT->ssql->sstr.adv_selection, &cond_exp);
  }
  /* @author: huahui  @what for: null ------------------------------------------------------------------------*/
	| exp_list IS_A NULL_A {
		ExpList *explist_left = (ExpList *)($1);
		ExpList *explist_right = (ExpList *)malloc(sizeof(ExpList));
		
		explist_init_for_null(explist_right);
		
		ConditionExp cond_exp;
		cond_exp.left = explist_left;
		cond_exp.right = explist_right;
		cond_exp.comp = IS;
		advselects_append_conditionexp(&CONTEXT->ssql->sstr.adv_selection, &cond_exp);
	}
	| exp_list IS_A NOT NULL_A {
		ExpList *explist_left = (ExpList *)($1);
		ExpList *explist_right = (ExpList *)malloc(sizeof(ExpList));
		
		explist_init_for_null(explist_right);
		
		ConditionExp cond_exp;
		cond_exp.left = explist_left;
		cond_exp.right = explist_right;
		cond_exp.comp = ISNOT;
		advselects_append_conditionexp(&CONTEXT->ssql->sstr.adv_selection, &cond_exp);
	}
	/* ------------------------------------------------------------------------------------------------------------*/
    ;

join:
    INNER JOIN ID onwhere {
        selects_append_relation(&CONTEXT->ssql->sstr.selection, $3);
    }
    |INNER JOIN ID onwhere join {
        selects_append_relation(&CONTEXT->ssql->sstr.selection, $3);
    }
    ;
onwhere:
    /* empty */
    | ON condition_exps {

    }
    ;

约束

排序

todo:

在创建单表schema的时候，要把order_attrs中的属性考虑进来
多表的输出是一个未projection的tupleset
在多表之后，聚合之前，做好排序和projection的工作。

测试用例：

create table torder(i int, f float, c char, d date);
insert into torder values(1, 5.23, "c", "1998-12-9");
insert into torder values(2, 8.45, "a", "1992-1-9");
insert into torder values(3, 1.63, "e", "1986-8-10");
insert into torder values(4, 0.368, "e", "1985-12-1");

select * from torder order by c;
select i from torder order by c;

create table torder2(i int, f float, c char, d date);
insert into torder2 values(1, 5.23, "c", "1998-12-9");
insert into torder2 values(2, 8.45, "a", "1992-1-9");
insert into torder2 values(3, 1.63, "e", "1986-8-10");
insert into torder2 values(4, 0.368, "e", "1985-12-1");

select * from torder, torder2 order by torder.f;
select * from torder, torder2 order by torder.f asc, torder2.f desc;
select torder.c, torder2.d from torder, torder2 order by torder2.d desc;
select torder.c from torder, torder2 order by torder2.d desc;

分组

把分组的属性放在schema中

在convert_to_selects()中将groupby的属性添加到selects中

groupby的select中不能有星

测试样例：

create table tgroup(i int, f float, c char, d date);
insert into tgroup values(1, 2.123, "a", "1998-12-9");
insert into tgroup values(1, 2.123, "b", "1997-7-3");
select i, f from tgroup group by i, f;
select i, f, avg(f) from tgroup group by i, f;
select i, count(i), f from tgroup group by i, f;

insert into tgroup values(2, 2.123, "b", "1993-7-23");
select f, c from tgroup group by f, c;
select avg(i), f, c from tgroup group by f,c;

代码框架介绍

这个是一个视频，在OceanBase社区版这个页面有。

网络模块

主要与客户端交互。在miniob/src/observer/net/server.h中定义。

SQL解析

将用户输入的SQL语句解析成语法树。

在miniob/src/observer/sql/parser/lex_sql.l文件中，负责词法解析，yacc_sql.y负责语法解析

计划执行

根据语法树描述执行并生成结果，miniob/src/observer/sql/executor/execute_stage.h会根据用户输入的SQL命令执行相应的语句，然后将生成的结果返回给客户端。

元数据管理

记录了当前数据库的表，字段和索引的元数据，在miniob/src/observer/storage/common/field_meta.h中。

执行计划缓存

这个和以下两个在决赛时用作查询优化题目的实现。在miniob/src/observer/sql/plan_cache中，将该SQL第一次生成的执行计划缓存在内存中，后续的执行可以反复执行这个计划，避免重复查询优化的过程。

语义解析

将生成的语法树转换成数据库内部的数据结构，在miniob/src/observer/sql/parser中。

查询缓存

将执行的查询结果缓存在内存中，下次查询时可以直接返回query_cache。在miniob/src/observer/sql/query_cache中。

查询优化

查询优化在miniob/src/observer/sql/optimizer中，根据一定的规则和统计数据，调整或重写语法树。

SEDA事件处理框架

结合事件驱动和多线程模式的优点，做到易扩展，解耦合和高并发，代码在miniob/deps/common/seda，代码量很大，使用方法可以参考miniob/src/observer/session/session_stage.h。

源码

weihan学长已经发给我们MiniOB往年源码，但是这是private的。在这个private里面有三个分支：main, feature_org和feature_ob。main分支是原始的文件，没有实现任何题目，但是可以编译成功；feature_org分支实现了一半的update分支，可以从这个分支开始做；feature_ob分支里面实现了必做题的3，4，5题和选做题2，3，4，6，7题。

在ob大赛微信群里，weihan学长发了miniob比赛.doc的文件，记录了他跟踪整个insert操作的过程，非常有参考价值。

编译

WSL下编译

代码的编译是个小问题，因为要在linux系统下编译。我平时写代码都是在windows上的，因为有合适的IDE，但是编译却要在linux下，就很不方便，因此我安装了WSL，写完代码之后拷贝到WSL的文件夹下C:\Users\zhou2\AppData\Local\Packages\CanonicalGroupLimited.Ubuntu20.04onWindows_79rhkp1fndgsc\LocalState\rootfs，然后在WSL下安装cmake来安装。

我的WSL是ubuntu系统的，所以安装cmake是这样的：

1 2	sudo apt-get update # 更新软件源 sudo apt install cmake

还有个问题时，如果你直接将文件夹拷贝到WSL的对应位置，会出现权限问题，你可以这样:

sudo su -
chmod a+w -R MiniOB
chmod a+r -R MiniOB
chmod a+x -R MiniOB

就是给所有人加上所有权限，就没什么事了。

但是，需要安装支持c14的gcc版本，但是我在WSL下遇到了很多莫名其妙的问题，所以转战centos7虚拟机了。

centos7虚拟机下编译

关于如何在centos7下安装支持c14的gcc, g++, gdb以及高于3.6版本的cmake，可以看linux环境。

然后直接按照docs/how_to_build.md中的做法来做就可以了，只是在最终build miniob阶段，需要按照weihan学长的做法来编译。

1
2
3

cd build
cmake .. -DDEBUG=1 # 因为我们要用gdb调试
make && sudo make install

坑

注意最好不用weihan学长的make -j all并行编译，可能会导致编译卡死问题，用make就好了。
make过后会出现找不到libjsoncpp.so.24的问题，去miniob/jsoncpp/build/lib/下面，拷贝所有文件到miniob/build/lib/下main。

词法与语法文件的编译

build文件夹中的Makefile貌似没有编译.l和.y文件的代码，要我们自己生成。参考OceanBase大赛miniob代码架构框架设计和说明

使用flex编译lex_sql.l文件，产生lex.yy.h和lex.yy.c文件：

1	flex --header-file=lex.yy.h lex_sql.l

架构

索引

我们可以从table.cpp中的Table::scan_record(Trx *trx, ConditionFilter *filter, int limit, void *context, RC (*record_reader)(Record *record, void *context)) 函数出发跟踪，了解索引是怎么工作的。

存储系统

研究了DiskBufferPool这个类的数据结构，以及它和RecordPageHandler之间的关系。

代码结构

rc.cpp里面有一句代码：

1 2	#define RC_CASE_STRING(rc) case rc : return #rc // rc应该用枚举值填充，但是#rc是什么意思

deps/common/seda/callback.h

// deps/common/seda/callback.h
//! A generic CompletionCallback
/**
 * A completion callback object provides a function that should be
 * invoked when an event has made it successfully through the stage
 * pipeline.  Usually, each event will reference a completion callback,
 * and before an event is deleted, the stage doing the deletion should
 * invoke the "done()" event method.  This method eventually invokes the
 * "callbackEvent()" method in the stage which set the callback, providing
 * a reference to the event as a parameter.
 * <p>
 * The purpose of the callback is to allow a stage to register some
 * processing for an event that is delayed until after the event has
 * progressed all the way through the stage pipeline.  Callbacks can be
 * chained.  Typically, each stage in the pipeline might add a callback
 * to an event's callback chain before passing the event to the next stage.
 * When the "done()" method is finally invoked, the callback on top of the
 * callback stack is invoked.  It becomes the responsibility of this callback
 * to either forward the event to another stage for more processing, or
 * to eventually call done() again of the event.  In this way, with each
 * callback on the stack eventually invoking the next callback on the stack,
 * all the callbacks are eventually executed. Each callback
 * can have an optional context associated with it.  This context is
 * provided to the stage callback function when it is invoked.  It is
 * opaque to the callback object.
 * <p>
 * By default, the callback will run on the thread of the stage that created
 * the callback.  If the stage that is calling done() on the event wants
 * to execute the callback stack in place, it can call the doneImmediate()
 * interface.  Note that this will execute the *entire* callback stack on
 * the current thread.
 */

class CompletionCallback {

  // public interface operations

 public:
  //! Constructor
  CompletionCallback(Stage *trgt, CallbackContext *ctx = NULL);

  //! Destructor
  virtual ~CompletionCallback();

  //! Push onto a callback stack
  void pushCallback(CompletionCallback *stack);

  //! Pop off of a callback stack
  /**
   * @returns  remainder of callback stack
   */
  CompletionCallback *popCallback();

  //! One event is complete
  void eventDone(StageEvent *ev);

  //! Reschedule this event as a callback on the target stage
  void eventReschedule(StageEvent *ev);

  //! Complete this event if it has timed out
  void eventTimeout(StageEvent *ev);

 protected:
  // implementation state

  Stage *targetStage;         //!< stage which is setting this callback
  CallbackContext *context;   //!< argument to pass when invoking cb
  CompletionCallback *nextCb; //!< next event in the chain
  bool evHistFlag;            //!< true if event histories are enabled
};

当StageEvent::done()函数调用之后，会调用CompletionCallback::event_done()函数，它的代码是：

// One event is complete
void CompletionCallback::event_done(StageEvent *ev) {

  if (ev_hist_flag_) {
    ev->save_stage(target_stage_, StageEvent::CALLBACK_EV);
  }
  target_stage_->callback_event(ev, context_);
}
// 这里target_stage_就是设置了这个callback的Stage动态对象
// ev就是调用了done()函数的那个StageEvent动态对象
// context_是在绑定Stage和CompletionCallback时，设置的参数
// Stage::callback_event()是虚函数，需要子类来定义这个函数, 比如：ParseStage就定义了callback_event()函数

(过期)observer/handler/handler_defs.h

typedef struct _Condition {
  int bLhsIsAttr;  // TRUE if left-hand side is an attribute
                   // 1时，操作符左边是属性名，0时，是属性值
  Value lhsValue;  // left-hand side value if bLhsIsAttr = FALSE
  RelAttr lhsAttr; // left-hand side attribute
  CompOp op;       // comparison operator
  int bRhsIsAttr;  // TRUE if right-hand side is an attribute
                   // 1时，操作符右边是属性名，0时，是属性值
  //   and not a value
  RelAttr rhsAttr; // right-hand side attribute if bRhsIsAttr = TRUE 右边的属性
  Value rhsValue; // right-hand side value if bRhsIsAttr = FALSE
} Condition;

这个Condition结构体用于表示一个简单表达式，比如：

1 2	2>1 name="xiaoming"

// struct of select
typedef struct {
  int nSelAttrs;                 // Length of attrs in Select clause
  RelAttr selAttrs[MAX_NUM];     // attrs in Select clause
  int nRelations;                // Length of relations in Fro clause
  char *relations[MAX_NUM];      // relations in From clause
  int nConditions;               // Length of conditions in Where clause
  Condition conditions[MAX_NUM]; // conditions in Where clause
} Selects;

例如，如果有一个sql语句：

1 2	select name,loc from person join department on person.dep=department.dep where person.age>40 and department.dep!="bio";

那么最终的Selects结构可能包含下述信息：

nSelAttrs: 2
RelAttr: {person,name},{department,loc}
nRelations: 2
relations: person,department
nConditions:2
conditions: {person.age,>,40},{department.dep,!=,"bio"}

我们可以发现Selects中少了join这个表连接信息，and这个条件逻辑关系信息。

// struct of insert
typedef struct {
  char *relName;         // Relation to insert into
  int nValues;           // Length of values
  Value values[MAX_NUM]; // values to insert
}Inserts;

这个Inserts结构表示向哪个表插入数据，以及插入哪些value，这里面的Value结构体实际上表示属性类型和属性值。从这里我们可以看到，miniob只支持指定全部属性值的元组插入操作，values中必须按顺序保存要插入元组的所有属性信息。

用一个union联合体表示所有可能的sql:

// union of sql_structs
union sqls {
  Selects sel;
  Inserts ins;
  Deletes del;
  Updates upd;
  CreateTable cret;
  DropTable drt;
  CreateIndex crei;
  DropIndex dri;
  DescTable desc_table;
  char *errors;
};

最后的sqlstr就表示这个sql是哪种类型的sql query以及sql query的内容。

// struct of flag and sql_struct
typedef struct _sqlstr {
  enum SqlCommandFlag flag;
  union sqls sstr;
}sqlstr;

observer/net/server.cpp

Server.accept()

更新ConnectionContext* client_context结构。

Server.start()

启动服务器，socket(), bind(), listen()函数都是在这里完成的。

storage/common/record_manager.h

这里定义了一个很重要的数据结构RID，表示一个元组在这个表文件中的位置，也称为元组的标识符。

struct RID 
{
  PageNum page_num; // record's page number
  SlotNum slot_num; // record's slot number
  // bool    valid;    // true means a valid record

  bool operator== (const RID &other) const {
    return page_num == other.page_num && slot_num == other.slot_num;
  }
};

调试跟踪

创建表

在obclient下，执行sql: create table t(c1 int)

使用gdb调试，设置断点：b ParseStage::handle_request，然后一步一步看程序怎么执行的，里面的变量怎么变化的。

位置1：observer/sql/parser/parse_stage.cpp/ParseStage::handle_request(StageEvent *event)

event的动态类型是SQLStageEvent *，向上类型转换为sql_event。sql_event指向的内容是：

{<common::StageEvent> = {
    _vptr.StageEvent = 0x498120 <vtable for SQLStageEvent+16>, comp_cb_ = 0x0, 
    ud_	= 0x0, cb_flag_ = false, history_ = 0x0, stage_hops_ = 0, 
    tm_info_ = 0x0}, 
 session_event_ = 0x4dc650,	
 sql_ = "create table t(c1 int);\n"
}

sql_event->session_event_指向的内容是：

{<common::StageEvent> = {
    _vptr.StageEvent = 0x4980b8 <vtable for SessionEvent+16>, 
    comp_cb_ = 0x7fffd00008e0, ud_ = 0x0, cb_flag_ = false, history_ = 0x0, 
    stage_hops_	= 0, tm_info_ = 0x0
 }, 
 client_ = 0x4e70c0, response_ = ""
}

其中的client_是observer/net/connection_context.h/ConnectionContext类型。

Query是observer/sql/parser/parser_defs.h/Query类型，这是语法分析的最终结果，用字符串来存储这个SQL查询的各方面信息，比如查哪些表，哪些属性，修改哪些属性之类的。

1	RC ret = parse(sql.c_str(), result);

parse()是observer/sql/parser/parse.h/parse(const char*, Query*)函数。

1	return new ExecutionPlanEvent(sql_event, result);

最后，返回ExecutionPlanEvent对象，这个也是StageEvent的子类，它与SQLStageEvent的关系是:

位置2: observer/sql/executor/execute_stage.cpp/ExecuteStage::handle_request(common::StageEvent *event)

我研究了一下这些StageEvent子类的关系：

1
2
3

StorageEvent *storage_event = new (std::nothrow) StorageEvent(exe_event);
// ...
default_storage_stage_->handle_event(storage_event);

又进入了下一个Stage:

位置3：observer/storage/default/default_storage_stage.cpp/DefaultStorageStage::handle_event(Stage *event)

把这个DefaultStorageStage和CompletionCallback绑定起来，这步操作在ParseStage, ExecutionStage和DefaultStorageStage都会存在。

StorageEvent *storage_event = static_cast<StorageEvent *>(event);
  CompletionCallback *cb = new (std::nothrow) CompletionCallback(this, nullptr);
  if (cb == nullptr) {
    LOG_ERROR("Failed to new callback for SessionEvent");
    storage_event->done_immediate();
    return;
  }
  storage_event->push_callback(cb);

然后，从event（动态类型是StorageEvent）中可以解析出很多关于这个SQL的信息：

Query *sql = storage_event->exe_event()->sqls();

SessionEvent *session_event = storage_event->exe_event()->sql_event()->session_event();

Session *session = session_event->get_client()->session;
const char *current_db = session->get_current_db().c_str();

Trx *current_trx = session->current_trx();

如果执行：print sql->sstr.create_table，会得到

$4 = {relation_name = 0x7fffd00016b0 "t", attribute_count = 1, 
      attributes = {{
      name = 0x7fffd0001690 "c1", type = 2, length = 4}, {name = 0x0, 
      type = 0,	length = 0} <repeats 19 times>}}

因为我正在创建名字为t的表。

接着，到达代码：

1
2
3

const CreateTable &create_table = sql->sstr.create_table;
rc = handler_->create_table(current_db, create_table.relation_name, 
        create_table.attribute_count, create_table.attributes);

位置4：observer/storage/default/default_handler.cpp/DefaultHandler::create_table(const char *dbname, const char *relation_name, int attribute_count, const AttrInfo *attributes)

我们根据字符串类型的dbname找到Db*类型对象，Db的定义是：

// observer/storage/common/db.h/Db
class Db {
public:
  Db() = default;
  ~Db();

  RC init(const char *name, const char *dbpath);

  RC create_table(const char *table_name, int attribute_count, const AttrInfo *attributes);

  Table *find_table(const char *table_name) const;

  RC drop_table(const char *table_name);

  const char *name() const;

  void all_tables(std::vector<std::string> &table_names) const;

  RC sync();


private:
  RC open_all_tables();

private:
  std::string   name_;
  std::string   path_;
  std::unordered_map<std::string, Table *>  opened_tables_;
};

如果执行gdb: print *db，输出

1 2	$5 = {name_ = "sys", path_ = "./miniob/db/sys", opened_tables_ = std::unordered_map with 1 elements

接着，到达代码:

1	return db->create_table(relation_name, attribute_count, attributes);

位置5：storage/common/db.cpp/Db::create_table(const char *table_name, int attribute_count, const AttrInfo *attributes)

1	std::string table_file_path = table_meta_file(path_.c_str(), table_name);

执行gdb: print table_file_path，输出：

1	$6 = "./miniob/db/sys/t.table"

使用t.table记录名字为t的表的元数据。

执行gdb: print *attributes，输出:

1	$7 = {name = 0x7fffd0001690 "c1", type = 2, length = 4}

接着，到达代码

1	rc = table->create(table_file_path.c_str(), table_name, path_.c_str(), attribute_count, attributes);

位置6：/storage/common/table.cpp/Table::create(const char *path, const char *name, const char *base_dir, int attribute_count, const AttrInfo attributes[])

我们看下Table这个类关联了哪些数据：

class Table {
// pass
private:
  std::string             base_dir_;
  TableMeta               table_meta_;
  DiskBufferPool *        data_buffer_pool_; /// 数据文件关联的buffer pool
  int                     file_id_;
  RecordFileHandler *     record_handler_;   /// 记录操作
  std::vector<Index *>    indexes_;
};
// 重点要理解TableMeta, DiskBufferPool, RecordFileHandler, std::vector<Index*>类型的数据有什么用

接下来，就要初始化.table文件，先在内存中初始化Table::table_meta_属性，然后将Table::table_meta_serialize到.table文件中。

1
2
3

if ((rc = table_meta_.init(name, attribute_count, attributes)) != RC::SUCCESS) {
    // pass
}

table_meta_.init()函数意图初始化表的元数据，它创建这样一个数组，来表示一个表的所有属性（不仅包括用户定义的属性，比如c1，还包括系统需要的属性）：

sys_fields_[0]	sys_fields1	attributes[0]	attributes1	……

在table_meta_.init()函数下，执行gdb调试print fields_，查看fields信息，输出：

$8 = std::vector of length 3, capacity 3 = {{name_ = "__trx", attr_type_ = 2, 
    attr_offset_ = 0, attr_len_ = 4, visible_ = false},	{name_ = "__null", 
    attr_type_ = 2, attr_offset_ = 4, attr_len_ = 4, visible_ = false},	{
    name_ = "c1", attr_type_ = 2, attr_offset_ = 8, attr_len_ = 4, 
    visible_ = true}}

1
2
3

fs.open(path, std::ios_base::out | std::ios_base::binary);
// pass
table_meta_.serialize(fs);

将元数据持久化到文件中。

总结

Stage类和StageEvent类的关系已经大致看懂了，可能与SEDA事件处理框架有关：

删除表

// storage/common/db.cpp/Db::drop_table(const char *table_name)
RC Db::drop_table(const char *table_name)
{
  RC rc = RC::SUCCESS;
  std::unordered_map<std::string, Table *>::const_iterator iter = opened_tables_.find(table_name);
  if (iter != opened_tables_.end())
  {
    Table *td = opened_tables_[table_name]; //
    opened_tables_[table_name] = nullptr;
    delete td;
    opened_tables_.erase(iter);
    std::string table_file_path = table_meta_file(path_.c_str(), table_name);
    std::string data_file_path = path_ + "/" + table_name + TABLE_DATA_SUFFIX;
    if (remove(table_file_path.c_str()) != 0)
    {
      return RC::IOERR_DELETE;
    }
    if (remove(data_file_path.c_str()) != 0)
    {
      return RC::IOERR_DELETE;
    }
  }
  else
  {
    return RC::SCHEMA_TABLE_NOT_EXIST;
  }
  LOG_INFO("Drop table success.");
  return rc;
}
/*
 * drop_table就做了两件事：
 *   1. 把Db::opened_tables_映射表中的$table_name删掉并delete
 *   2. 把磁盘中的$table_name.table和$table_name.data删掉
 */

元组插入操作

下面是插入操作的整个过程以及用到的相关主要数据结构:

1. sql/parser/parser_stage.cpp/ParserStage::handle_event()
   1. sql/parser/parser_stage.cpp/ParserStage::handle_request()
      1. 得到sql字符串: const std::string &sql = sql_event->get_sql();
         例如: sql="select * from t1"
      2. 对sql进行词法分析和语法分析: RC ret = parse(sql.c_str(), result);
         result是handler/handler_defs.h/sqlstr*类型
      3. return new ExecutionPlanEvent(sql_event, result);
   2. sql/optimizer/optimizer_stage.cpp/OptimizerStage::handle_event()
      1. 没有写任何优化代码
      2. sql/executor/executor_stage.cpp/ExecuteStage::handle_request()
         1. ExecutionPlanEvent*类型的exe_event包含了SessionEvent, sqlstr, current_db等信息; 
            storage_event和exe_event一样;
         2. CompletionCallback *cb = new (std::nothrow) CompletionCallback(this, nullptr);
            storage_event->pushCallback(cb);
            不懂这个CompletionCallback是什么意思;
         3. storage/default/default_storage_stage.cpp/DefaultStorageStage::handle_event()
            1. Query sql;, SessionEvent sesson_event, current_db, Trx current_trx等信息都从StorageEvent storage_event中解析出来了
               其中,sql已经指明了SQL查询的各部分信息，比如从哪些表查，满足什么条件，查什么属性之类的
            2. storage/default/default_handler.cpp/DefaultHandler::insert_record()
               1. storage/common/table.cpp/Table::insert_record(Trx* trx, Record* record)
                  在执行这个函数之前，先使用Table:make_record(value_num, values, record_data)来将values中的属性值串接到record_data中，也进行了一些鲁棒性判断；
                  Table关联了storage/default/DiskBufferPool, storage/common/record_manager/RecordFileHandler, storage/common/RecordPageHandler
                  这三个数据结构，可能包含了一些关于表的磁盘页的信息。
                  1. trx->init_trx_info(this, *record); 初始化事务信息，将事务ID记录在该record上  
                     /storage/trx/trx.cpp/Trx::init_trx_info(Table *table, Record *record) 
                     1. 在Table::table_mata_::fields_属性中保存了有关事务的FieldMeta，
                        这个FieldMeta记录了保存在Record中的事务信息的offset
                     2. 将Record中对应于事务信息的部分: ptrx_id，更新为当前的事务id
                  1. storage/common/record_manager.cpp/RecordFileHandler::insert_record(const char *data, int record_size, RID *rid)
                     通过DiskBufferPool::get_page_count()计算page_count，这个表的总的页面数量;
                     通过RecordPageHandler::get_page_num()计算current_page_num，当前打开的页面;
                     从current_page_num开始找一个合适的磁盘页，用于插入数据，每次找到一个页后，就访问disk_buffer_pool_初始化record_page_handle_,记录关于这个页的信息（这个过程稍微底层点，后面会具体分析）;
                     如果找不到一个合适的页，就分配一个新的页面;
                     调用RecordPageHandler::insert_record()函数将元组数据插入到这个页中;
                     1. storage/common/record_manager.cpp/RecordPageHandler::insert_record(const char *data, RID *rid)
                  2. rc = trx->insert_record(this, record);
                     /storage/trx/trx.cpp/Trx::insert_record(Table *table, Record *record)

位置1：在storage/common/table.cpp/Table::insert_record(Trx* trx, Record* record)

1	rc = record_handler_->insert_record(record->data, table_meta_.record_size(), &record->rid);

使用gdb命令：print *record_handler_，输出:

$10 = {disk_buffer_pool_ = 0x4db810, file_id_ = 1, 
       record_page_handler_ = {
           disk_buffer_pool_ =	0x4db810, file_id_ = 1,	
           page_handle_ = {open = true, frame = 0x7fffd8002340}, 
           page_header_ = 0x7fffd8002350, 
           bitmap_ = 0x7fffd8002364 "\001"
       }
}

这里bitmap_就是位图，指示这个page种哪些slot有元组，哪些slot没有。

我们可以发现，RecordFileHandler, RecordPageHandler, DiskBufferPool有如下特点：

使用gdb命令：print *(record_handler_->record_page_handler_.page_handle_.frame)，输出：

$11 = {dirty = true, pin_count = 1, file_desc = 10, 
       page = {page_num = 1, 
               data = "\001\000\000\000\374\000\000\000\f\000\000\000\020\000\000\000\070\0
                        00\000\000\001", '\000'	<repeats 43 times>, "\001", '\000' <repeats 4026 times>
       }
}

在RecordPageHandler中保存了完整的一个frame，它是一个Page数据以及状态数据（如，是否脏）的集合。

使用gdb命令：print *(record_handler_->record_page_handler_.page_header_)，输出

1
2
3

$13 = {record_num = 1, record_capacity = 252, record_real_size = 12, 
       record_size =	16, first_record_offset = 56
}

从这里可以看出，这个RecordPageHandler::page_header_保存的是page_num为1的这个Page的一些元信息，比如这个Page已经有1个元组了，总共可以保存252个元组，每个元组的实际大小是12字节，填充后是16字节，第一个元组的offset是56字节。所以，每个元组的大小比较固定，这个是12字节的原因是，我设置的这个表t只有一个int类型属性，再加上两个系统属性，总共3个属性，然后每个属性恰好是4字节，所以是12字节。

位置2：storage/record_manager.cpp/RecordFileHandler::insert_record(const char *data, int record_size, RID *rid)

执行到：

1	if ((ret = disk_buffer_pool_->get_page_count(file_id_, &page_count)) != RC::SUCCESS) {

于是step进get_page_count()这个函数：

1	*page_count = open_list_[file_id]->file_sub_header->page_count;

执行gdb命令：print *(open_list_[file_id])，输出：

$19 = {bopen = true, file_name = 0x4e6190 "./miniob/db/sys/t.data", 
       file_desc = 10, hdr_frame = 0x4e70e0,	hdr_page = 0x4e70ec, 
       bitmap = 0x4e70f8 "\003", file_sub_header = 0x4e70f0
}

可以发现，保存在RecordFileHandler和RecordPageHandler的file_id_属性并不是真正的文件描述符，而是记录在DiskBufferPool中的open_list_属性中的下标，它指向的元素是BPFileHandle，表示一个文件的元信息。比如，上面的输出，有文件是否打开，文件名，文件描述符等。这些信息应该在创建表时就初始化好的。

执行gdb命令：print *(open_list_[file_id]->hdr_frame)，输出：

$20 = {dirty = true, pin_count = 1, file_desc = 10, 
       page = {page_num = 0, 
               data = "\002\000\000\000\002\000\000\000\003", '\000' <repeats 4082	times>
       }
}

执行gdb命令：print *(open_list_[file_id]->file_sub_header)，输出：

1	$22 = {page_count = 2, allocated_pages = 2}

我们可以看到，表文件的第一个Page是0号的，貌似不保存元组数据，因为我创建这个表后插入了两个元组，但是这里的page_count是2（一个0号，一个1号），而且上面的数据显示，这个两个元组保存在1号Page中。

然后，再返回到RecordFileHandler::insert_record(const char *data, int record_size, RID *rid)。

1	ret = record_page_handler_.init(*disk_buffer_pool_, file_id_, current_page_num);

上述代码从disk_buffer_pool中找到一个对应的page的视图，包括page的数据和头部都是视图，而不是拷贝。具体的讲解在get_this_page()函数中。

1	return record_page_handler_.insert_record(data, rid);

在这个RecordPageHandler::insert_record()函数里，只将元组插入到缓存区中，但是并没有存储到磁盘文件中。这个是因为，当buffer不够用的时候，才会把脏页给刷到磁盘中，这个miniOB没有后台刷进程。

位置3：storage/default/disk_buffer_pool.cpp/DiskBufferPool::get_this_page(int file_id, PageNum page_num, BPPageHandle *page_handle)

在RecordFileHandler::insert_record()里面需要根据文件描述符和页号找到对应的BPPageHandle，而要找到这个，最重要的是要找到frame，所以要分析这个函数。

首先得到BPFileHandle *file_handle：

1	BPFileHandle *file_handle= open_list_[file_id];

然后根据文件描述符和页号得到frame：

1	Frame *f = bp_manager_.get(file_handle->file_desc,page_num);

step进storage/default/disk_buffer_pool.h/BPManager::get(int file_desc, PageNum page_num)，看看里面是什么：

Node *node = getNode(file_desc,page_num);
if(node!=nullptr){
    remove(node);
    setHead(node);
    return node ->frame;
}
else return nullptr;

这个BPManager::getNode()函数是在搜索BPManager::mp映射，找到(file_desc, page_num)对应的Node。系统中的所有frame是连接成一个链表的，因此Node包含frame，以及一些链表指针，这样设计是为了实现LRU；然后，将这个Node放到链表的头部，实现了LRU。

为了更好地理解BPManager是干什么的，看下它的源码：

// storage/default/disk_buffer_pool.h
#define BP_BUFFER_SIZE 50
#define MAX_OPEN_FILE 50

class BPManager {
    // pass
    int size;
    Node *head = nullptr,*tail = nullptr;
    map<pair<int,int>,Node*> mp;
};

BPManager就是管理disk buffer的，将很多frame连接成一个链表，然后设置buffer的最大size是50，最大文件打开数是50。

然后回到DiskBufferPool::get_this_page()函数，从上面可以知道，BPManager::get只能在buffer中找页。如果通过BPManager::get能够得到frame，就直接返回成功；否则，就从磁盘中读取页并设置一个新的frame，函数是BPManager::load_page(PageNum page_num, BPFileHandle *file_handle, Frame *frame)，然后将这个frame加入到BPManager管理的链表的头部，但是若链表没有空闲空间了，需要考虑evict一个页。

位置4：storage/trx/trx.cpp/Trx::insert_record(Table *table, Record *record)

在插入元组后，向Trx中也插入元组。

执行gdb命令：print record->rid，输出：

1	$15 = {page_num = 1, slot_num = 1}

1	insert_operation(table, Operation::Type::INSERT, record->rid);

在Trx类中有一个属性：operations_，它记录了每个Table的所有Operation，这个是type和rid的组合，type表示这个Operaion是增删改的哪个，rid表示这个Operation操作的是哪个元组，因为rid是元组标识符嘛。

感觉这个Operations_就像一个轻量级的日志。

位置5：storage/common/table.cpp/Table::insert_entry_of_indexes(const char *record, const RID &rid)

插入元组后，理所当然地要更新索引。

但是我发现Table::indexes_中并没有任何Index对象，说明索引没有自动创建。

// event/sql_event.h
class SQLStageEvent : public common::StageEvent {
public:
  SQLStageEvent(SessionEvent *event, std::string &sql);
  virtual ~SQLStageEvent() noexcept;

  const std::string &get_sql() const {
    return sql_;
  }

  SessionEvent * session_event() const {
    return session_event_;
  }
private:
  SessionEvent *session_event_;
  std::string & sql_;
  // void *context_;
};
// SessionEvent* session_event_是做什么用的?
// sql_就是一个sql字符串

// event/execution_plan_event.h
class ExecutionPlanEvent : public common::StageEvent {
public:
  ExecutionPlanEvent(SQLStageEvent *sql_event, sqlstr *sqls);
  virtual ~ExecutionPlanEvent();

  sqlstr * sqls() const {
    return sqls_;
  }

  SQLStageEvent * sql_event() const {
    return sql_event_;
  }
private:
  SQLStageEvent *      sql_event_;
  sqlstr *             sqls_;
};
// sqls_保存了parse过的sql结构

// storage/common/record_manager.h
struct RID 
{
  PageNum page_num; // record's page number
  SlotNum slot_num; // record's slot number
  // bool    valid;    // true means a valid record

  bool operator== (const RID &other) const {
    return page_num == other.page_num && slot_num == other.slot_num;
  }
};
// RID是一个元组（记录）的标识符

struct Record 
{
  // bool valid; // false means the record hasn't been load
  RID  rid;   // record's rid
  char *data; // record's data
};
// data来源于sql/parser/parser_defs.h/Inserts结构体的信息

class RecordFileHandler {
public:
    // pass
    
    /**
     * 插入一个新的记录到指定文件中，pData为指向新纪录内容的指针，返回该记录的标识符rid
     * @pram data
     * @param rid
     * @return
     */
    RC insert_record(const char *data, int record_size, RID *rid);
    
    // pass
    
private:
   DiskBufferPool  *   disk_buffer_pool_;
   int                 file_id_;                    // 参考DiskBufferPool中的fileId
    
   RecordPageHandler   record_page_handler_;        // 目前只有insert record使用
}
// DiskBufferPool和RecordPageHandler是做什么用的

class RecordPageHandler {
    // pass
    
private:
    DiskBufferPool * disk_buffer_pool_;
    int              file_id_;
    BPPageHandle     page_handle_;
    PageHeader    *  page_header_;
    char *           bitmap_;
}
// file_id_, BPPageHandle page_handle_, PageHeader* page_header_, bitmap_都是做什么用的

总结

研究了DiskBufferPool这个类的数据结构，以及它和RecordPageHandler之间的关系。

RecordPageHandler是DiskBufferPool的切片（视图）。

元组查找

1. sql/executor/execute_stage.cpp/ExecuteStage::do_select(const char *db, Query *sql, SessionEvent *session_event) 
   根据sql进行查询
   node是一个SelectExeNode执行结点，包含DefaultConditionFilter数组，DefaultConditonFilter包含每个属性在元组中的偏移和长度或者它的值
   1. rc = node->execute(tuple_set);
      sql/executor/execution_node.cpp/SelectExeNode::execute(TupleSet &tuple_set)  
      1. node是一个SelectExeNode执行结点，查询一个表的过滤了条件之后的元组。当然，这个语句是在一个循环内的，可能很多个表都要放在一个执行结点中查询，
      然后方便它们的结果进行连接.
      2. condition_filter是CompositeConditionFilter类型, 从SelectExeNode::condition_filters_初始化来的, 它本质上还是DefaultConditonFilter的数组，只是加了一些函数，
         比如说CompositeConditionFilter::filter()函数，可能是用于过滤
      3. TupleRecordConverter converter(table_, tuple_set);
         return table_->scan_record(trx_, &condition_filter, -1, (void *)&converter, record_reader);  
         storage/common/table.cpp/Table::scan_record(Trx *trx, ConditionFilter *filter, int limit, void *context, void (*record_reader)(const char *data, void *context)) 
         1. converter是一个context，可以调用它的add_record()函数，将保存在磁盘中的数据转换为很多列，然后形成一个tuple，加入到tuple_set中。 
         record_reader()是一个方法，用于向converter传入char *data
         2. RecordReaderScanAdapter adapter(record_reader, context);
            return scan_record(trx, filter, limit, (void *)&adapter, scan_record_reader_adapter);
            storage/common/table.cpp/Table::scan_record(Trx *trx, ConditionFilter *filter, int limit, void *context, RC (*record_reader)(Record *record, void *context))
            adapter是对record_reader和context的一个简单封装
            1. RecordFileScanner scanner;
               rc = scanner.open_scan(*data_buffer_pool_, file_id_, filter);
               storage/common/record_manager.cpp/RecordFileScanner::open_scan(DiskBufferPool & buffer_pool, int file_id, ConditionFilter *condition_filter)
               scanner知道了file_id, DiskBufferPool, CompositeConditionFilter,它可以亲自和RecordPageHandler交互，来一个一个读取Record
            2. for ( ; RC::SUCCESS == rc && record_count < limit; rc = scanner.get_next_record(&record)) 
               storage/common/record_manager.cpp/RecordFileScanner::get_next_record(Record *rec)  
               1.

最重要的是：

位置1：sql/executor/execute_stage.cpp/ExecuteStage::do_select(const char *db, Query *sql, SessionEvent *session_event)。

这个代码优点难理解。在db和Query信息已知的情况下执行查找。

比较重要的数据结构：

// sql/executor/tuple.h
class Tuple {
    // pass
private:
  std::vector<std::shared_ptr<TupleValue>>  values_;
};

class TupleField {
    // pass
private:
  int  type_;
  std::string table_name_;
  std::string field_name_;
};

class TupleSchema {
    // pass
public:
  static void from_table(Table *table, TupleSchema &schema);
private:
  std::vector<TupleField> fields_;
};

class TupleSet {
    // pass
public:
  const TupleSchema &schema() const {
    return schema_;
  }
private:
  std::vector<Tuple> tuples_;
  TupleSchema schema_;
};

从上面可以知道：TupleSet就是保存同一个表的很多元组。而Tuple就是保存了很多TupleValue的指针。画图表示：

// sql/executor/execution_node.h

class SelectExeNode : public ExecutionNode {
public:
  SelectExeNode();
  virtual ~SelectExeNode();

  RC init(Trx *trx, Table *table, TupleSchema && tuple_schema, std::vector<DefaultConditionFilter *> &&condition_filters);

  RC execute(TupleSet &tuple_set) override;
private:
  Trx *trx_ = nullptr;
  Table  * table_;
  TupleSchema  tuple_schema_;
  std::vector<DefaultConditionFilter *> condition_filters_;
};


class JoinExeNode : public ExecutionNode{
public:
  JoinExeNode();
  virtual ~JoinExeNode();

  RC init(Trx *trx, const TupleSet *left_table, const TupleSet *right_table, 
          TupleSchema && tuple_schema, 
          std::vector<JoinConditionFilter *> &&condition_filters);
  void set_left_table(TupleSet *left_table);
  void set_right_table(TupleSet *right_table);
  void set_tuple_schema(TupleSchema &tuple_schema);
  // 暂时只支持基于的内存join，且不支持索引
  RC execute(TupleSet &tuple_set);

private:
  Trx *trx_ = nullptr;
  const TupleSet *left_table_;
  const TupleSet *right_table_;
  TupleSchema tuple_schema_;
  std::vector<JoinConditionFilter *> condition_filters_;
};

SelectExeNode只能够处理与某一个表相关的condition以及查询函数，不支持涉及到多表的查询。比如说，SelectExeNode可以表示一个表t，以及查询条件t.c1<10，但是不能表示t.c1 < t2.c1，因为conditon只能涉及一个表。

// storage/common/condition_filter.h
struct ConDesc {
  bool   is_attr;     // 是否属性，false 表示是值
  int    attr_length; // 如果是属性，表示属性值长度
  int    attr_offset; // 如果是属性，表示在记录中的偏移量
  void * value;       // 如果是值类型，这里记录值的数据
  int attr_type;
  int index;//属性的下标
};

class ConditionFilter {
//默认只支持一个条件过滤
private:
  ConDesc  left_;
  ConDesc  right_;
  int left_attr_type_;
  int right_attr_type_;
  CompOp   comp_op_;
};

SelectExeNode初始化时需要ConditionFilter，它比Conditon更精确地描述了条件，以及涉及的每个属性。

位置2：storage/common/table.cpp/Table::scan_record(Trx *trx, ConditionFilter *filter, int limit, void *context, RC (*record_reader)(Record *record, void *context))。

重要的结构是：RecordFileScanner

RecordFileScanner scanner;
rc = scanner.open_scan(*data_buffer_pool_, file_id_, filter);
// pass
int record_count = 0;
Record record;
rc = scanner.get_first_record(&record);
for ( ; RC::SUCCESS == rc && record_count < limit; rc = scanner.get_next_record(&record)) {
  if (trx == nullptr || trx->is_visible(this, &record)) {
    rc = record_reader(&record, context);
    if (rc != RC::SUCCESS) {
      break;
    }
    record_count++;
  }
}

RecordFileScanner的结构是：

// storage/common/record_manager.h
class RecordFileScanner 
{
public:
  RecordFileScanner();

  /**
   * 打开一个文件扫描。
   * 本函数利用从第二个参数开始的所有输入参数初始化一个由参数rmFileScan指向的文件扫描结构，
   * 在使用中，用户应先调用此函数初始化文件扫描结构，
   * 然后再调用GetNextRec函数来逐个返回文件中满足条件的记录。
   * 如果条件数量conNum为0，则意味着检索文件中的所有记录。
   * 如果条件不为空，则要对每条记录进行条件比较，只有满足所有条件的记录才被返回
   * @param buffer_pool 
   * @param file_id 
   * @param condition_num 
   * @param conditions
   * @return
   */
  RC open_scan(DiskBufferPool & buffer_pool, int file_id, ConditionFilter *condition_filter);

  /**
   * 关闭一个文件扫描，释放相应的资源
   * @return
   */
  RC close_scan();

  RC get_first_record(Record *rec);

  /**
   * 获取下一个符合扫描条件的记录。
   * 如果该方法成功，返回值rec应包含记录副本及记录标识符。
   * 如果没有发现满足扫描条件的记录，则返回RM_EOF
   * @param rec 上一条记录。如果为NULL，就返回第一条记录
   * @return
   */
  RC get_next_record(Record *rec);

private:
  DiskBufferPool  *   disk_buffer_pool_;
  int                 file_id_;                    // 参考DiskBufferPool中的fileId

  ConditionFilter *   condition_filter_;
  RecordPageHandler   record_page_handler_;
};

使用索引查找

1. table.cpp/Table::scan_record(Trx *trx, ConditionFilter *filter, int limit, void *context, RC (*record_reader)(Record *record, void *context))
   1. IndexScanner *index_scanner = find_index_for_scan(filter);
      找到对应的IndexScanner
      table.cpp/Table::find_index_for_scan(const ConditionFilter *filter)
      1. 如果filter是DefaultConditionFilter（只有一个条件），则直接调用find_index_for_scan
      2. 如果filter是CompositeConditionFilter，则根据filter中的第一个DefaultConditionFilter调用find_index_for_scan
         table.cpp/Table::find_index_for_scan(const DefaultConditionFilter &filter)
         1. 从table_meta_中找到找到IndexMeta
            const IndexMeta *index_meta = table_meta_.find_index_by_field(field_meta->name());
         2. 根据index_meta->name()找到Index index
         3. index根据操作符和操作数创建IndexScanner（比如>5, ="1999-12-9"）
            bplus_tree_index.cpp/BplusTreeIndex::create_scanner(CompOp comp_op, const char *value)
            1. 创建BplusTreeScanner *bplus_tree_scanner = new BplusTreeScanner(index_handler_);
               将BplusTreeScanner中的BplusTreeHandler &index_handler_设置为index_handler_
               BplusTreeHandler index_handler是BplusTreeIndex里面的一个属性，维护了一个BplusTree
            2. 打开bplus_tree_scanner.  bplus_tree_scanner->open(comp_op, value);
               初始化bplus_tree_scanner中的一些成员属性     
            3. 创建BplusTreeIndexScanner *index_scanner = new BplusTreeIndexScanner(bplus_tree_scanner); 
               将BplusTreeIndexScanner的tree_scanner_属性设置为bplus_tree_scanner
               返回           
   2. scan_record_by_index(trx, index_scanner, filter, limit, context, record_reader);
      table.cpp/Table::scan_record_by_index(Trx *trx, IndexScanner *scanner, ConditionFilter *filter, int limit, void *context,
                                            RC (*record_reader)(Record *, void *)
      1. 得到下一个记录的RID
         bplus_tree.cpp/BplusTreeScanner::next_entry(RID *rid)
         1. 从磁盘中加载一些索引文件的页到内存中
            bplus_tree.cpp/BplusTreeScanner::find_idx_pages()
         2. 得到下一个索引，BplusTreeScanner应该会记录目前扫描到了哪个位置，然后继续扫描下一个合法的索引记录
            bplus_tree.cpp/BplusTreeScanner::get_next_idx_in_memory(RID *rid)
      2. 从RecordFileHandler中根据rid找到对应的元组记录
         record_manager.cpp/RecordFileHandler::get_record(const RID *rid, Record *rec)
      3. record_reader(&record, context); 调用record_reader从原始的元组记录中读取数据到规定的格式中，比如MiniOB中的tuple结构

聚合查找max

执行下述SQL语句：

1	select max(salary) from school;

位置1：sql/executor/execute_stage.cpp/ExecuteStage::do_select(const char *db, Query *sql, SessionEvent *session_event)。

1	const Selects &selects = sql->sstr.selection;

这行代码会解析出Query中的Selects结构，得到SELECT查询的信息。

1
2
3

(gdb) print selects.attributes[0]
$2 = {agg_func_name = 0x7fffcc0058e0 "MAX", relation_name = 0x0, 
  attribute_name = 0x7fffcc0058c0 "salary"}

Tuple agg_res;
std::vector<const char*> columns;

AggregationExeNode node;
node.init(trx, &res_table, std::move(agg_infos));
node.execute(agg_res, columns);

难点

seda事件处理框架

代码阅读

代码阅读感觉很难，以后我们可以几天交流一次，毕竟如果有大佬已经看懂了，那么我就可以偷懒了，省点时间。

性能优化

这部分应该是要提前考虑的点，我们可以：

系统学习查询执行，查询优化相关的知识，比如数据库系统概念, 数据库系统实现, 以及参赛宝典
和weihan学长交流

可以有哪些优化：

当where条件必为false时，可以直接返回空集，比如where id=null。
当count(1)时，可以直接返回tupleset大小。

错误

自豪的drop table还没有实现好。没有删掉table.data文件
退出miniob后，select创建的表发现no data。
元数据校验支持多表校验。主要查询t.col中t有没有col属性。
聚合查询做更多的校验，比如字符串不能算平均值

做

把check_insert_stat拆分
基于tuple set做聚合
update没有做完整的校验，只对set的date字段做了校验
要在TupleSchema中重写print()函数。还要添加一个agg属性，表示是不是聚合属性。还要判断聚合与属性是否匹配，比如AVG(string)。

我把代码大改了，元数据校验又加了些东西，TupleSchema也改了很多，这部分和多表以及聚合都相关，目的是，通过调用TupleSchema的print()函数就可以精确无误地输出多表，单表，聚合属性以及group by的属性头。比如id | max(birthday)。

对聚合属性进行合法性校验

update也要做合法性校验;

聚合属性的浮点数的输出规范

date最早限制是1970-01-01

drop table, update table, date都要考虑索引

往年OB赛题

OB大赛

参赛宝典

第4章 查询处理

选择运算

参赛题目

basic

优化buffer pool

update

测试用例

增加date字段

语法和词法部分

select语句部分

bug

一次插入多条数据

查询元数据校验

多表连接

聚合运算

多表join操作

一次插入多条数据

支持NULL类型

索引

子查询

查询支持表达式

测试样例

Selects结构

RelAttrExp结构

ConditionExp结构

修改lex和yacc文件

约束

排序

分组

代码框架介绍

网络模块

SQL解析

计划执行

元数据管理

执行计划缓存

语义解析

查询缓存

查询优化

SEDA事件处理框架

源码

编译

WSL下编译

centos7虚拟机下编译

坑

词法与语法文件的编译

架构

索引

存储系统

代码结构

deps/common/seda/callback.h

(过期)observer/handler/handler_defs.h

observer/net/server.cpp

Server.accept()

Server.start()

storage/common/record_manager.h

调试跟踪

创建表

总结

删除表

元组插入操作

总结

元组查找

使用索引查找

聚合查找max

难点

seda事件处理框架

代码阅读

性能优化

错误

做

引用

第4章查询处理