查看原文
其他

黑客松环节No.1,疫情隔离“顺手”拿了个奖| “OceanBase数据库大赛”华东师大队伍专访

乐于分享的 OceanBase 2022-08-27

从 0 到 1,打造你的数据库”。这是首届“OceanBase数据库大赛”的主题,参赛者需要从0到1系统地打造一个完整的数据库。


来自国内外的1179 支团队历经 9 个月的激烈角逐,5月10日,首届“OceanBase数据库大赛”正式落下帷幕,并公布 10 强名单(👉回顾10强名单)。


在这场没有硝烟的“大战”中,华东师范大学5支团队进入决赛10强,成为本届大赛总决赛入围团队数量最多的高校。“东亚男儿”团队最终荣获首届 OceanBase 数据库大赛亚军。


他们在参赛过程中做出了怎样的技术创新?又是如何取得优异成绩的?今天,我们请来了这支队伍 —— 华东师范大学“东亚男儿” 团队的队长连薛超、队员翁思扬、胡梓锐,请他们分享自己的参赛感受。














“东亚男儿” 团队

做好中国特色的数据库
















本次大赛的亚军团队由三位同学组成,均来自华东师范大学。分别是研究方向为存储与分布式事务、事务型数据库评测及 HTAP 系统评测与优化的队长连薛超,和来自数据科学与工程学院的翁思扬以及来自软件学院的胡梓锐。

“代表中国的青年人,做好中国特色的数据库”从这支队伍的口号里,我们也能感受到他们的自信。

在参加比赛的时候,队长连薛超专门设计了 Logo,通过三只小黄鸭代表参赛队伍对数据库领域的展望,以及对自己的鼓励和期许:“以马克思主义为引领,将人工智能算法用于数据库中,为数据库领域带来中国智慧”。(戳下方视频了解他们 




听听他们的参赛感受:
Q:

为什么要参加这次 OceanBase 数据库大赛?有哪些吸引你们的地方?


A:

数据库作为计算机领域的基础软件,在整个体系中占据着重要的地位。因此,在OceanBase 提出了独立自研的国产数据库、不断突破的消息传来之后,我们很快对其产生了兴趣。在学院组织的相关培训中,我们对 OceanBase 有了一个初步的了解,这更进一步激发了我们对其内部的独特机制和技术的好奇。正因如此,我们在得知这一比赛时,就决定不能错过深入了解 OceanBase 数据库内核的机会,果断报名参加了比赛。




Q:

参加本次数据库大赛的感触最深的是什么?有哪些事情让你们印象深刻?


A:

数据库本身是一个极具挑战性的研究领域,其对于多个学科的整合以及计算机学科各个子领域知识的汇聚都使得实现一款高性能的数据库从理论和实践上都非常困难。本科的课程我们相对来说还是停留在基础的理论学习上,对于数据库一些内部模块的细节把握以及工程实现上的设计思路仍然是有很大欠缺的。所以此次 OceanBase 的数据库大赛无疑给了我们一次将理论付诸实践的机会。


我们从初赛思考如何将功能需求落实到具体的工程实现上,实现诸如子查询,多表 Join 等基础功能,再到复赛决赛去更深入地思考系统性能优化,查询存储之间在时间与空间上的权衡,这一方面加深了我们对数据库内部模块的理解,另一方面期间很多有益的探索也让我们对数据库更加充满热情和希望,所以非常感谢 OceanBase 能提供这样一次难得的学习机会。




Q:

作为本次数据库大赛的亚军团队,对明年大赛的哪些建议和期望?


A:

我们觉得 OceanBase 大赛组织的非常好,希望大家都能积极参与,积极地在一个交流社区里相互补充学习,希望大家能在数据库领域做出更有意义的工作。


同时也给明有三点建议,首先在考核性能的同时,建议在指标里体现内存的消耗。其次,疫情对大赛尤其是决赛会安排产生影响,最好可以针对突发情况做好备份方案。然后,赛题方面建议更仔细地控制变量,避免一些 hack 的情况出现。最后,希望比赛可以在出题时考虑一些更具开放性的题目。
















东亚男儿的技术分享

从查询树的生成到查询执行

















本文主体面向对 OceanBase 数据库源码以及系统性能优化感兴趣的初学者供以技术交流,笔者来自华东师范大学数据科学与工程学院 DBHammer 项目组(东亚男儿团队)。


Nested Loop Join(NLJ)是数据库中最常用的关联算法之一,它的性能会直接影响数据库的性能。在这里我们以 OceanBase 社区版 3.1 中 NLJ 为例,简要介绍我们对 OceanBase 从查询树的生成到查询执行的一些认识。文章主要从 OceanBase 的代码风格、查询树的生成和查询执行三个方面进行介绍。



OceanBase的代码风格


在刚开始研读 OceanBase 的代码时,简洁的代码风格让人印象深刻。一般而言,OceanBase 的函数返回值不是函数的处理结果,而是函数的执行状态。与之相对的,函数的处理结果会通过修改引用参数的方式向上传递。因此,通过分析每个函数的返回值,可以简单得知这个函数的执行流程。所以,在 OceanBase 的代码中经常能看到类似的代码:


if (OB_FAIL(func_1)){ logging} else (OB_FAIL(func_2)){ logging} else (OB_SUCC(func_3)){ logging}


这样的代码实际上相当于顺序执行 func_1、func_2、func_3,并在函数执行失败/成功的时候输出日志信息,不继续执行剩下的函数。为了后续叙述的简洁,对于类似的代码,我们将省略函数执行失败的异常处理。



查询树的生成

Index Nested Loop Join为例


对于一般的 SQL 执行过程,首先生成逻辑查询树,在此基础上按照一定规则进行优化,然后生成物理查询树,最终真正的执行。NLJ 中最重要的就是 join 算子的生成,所以我们以 join 算子的生成为例介绍这一部分。算子是构造查询树的基本元素,每个算子根据下层算子的结果,加工生成数据,然后供上层算子加工生成新的数据,最终由跟节点算子输出最终结果。join 算子是关联两张表的基本操作,它有两个下层算子,按照一定规则对下层算子的数据进行关联处理。


join 算子的生成主要依赖于ObStaticEngineCG::generate_join_spec(ObLogJoin& op, ObJoinSpec& spec) 函数。这一函数接收两个引用参数 op 和 spec,op 是 join 对应的逻辑计划,当有多个 join 条件(可以理解为查询条件)时,op 详细记录第一个 join 条件,并将其他的 join 条件存储在 other_join_conditions 里;spec 是生成的物理执行计划。generate_join_spec() 分为两个部分。在第一部分,它会处理首要的 join 条件,判断逻辑计划中首要的 join 条件的 join 类型,根据这个类型选择生成对应的物理计划。在第二部分,它遍历 other_join_conditions,逐个调用接口函数生成物理执行计划。通过这种方式,OceanBase 能够自然地实现对逻辑计划的递归展开,从而构建出对应的物理执行树。我们对这一函数进行了整理和提取,抽象出其中的逻辑如下:


int ObStaticEngineCG::generate_join_spec(ObLogJoin& op, ObJoinSpec& spec){ int ret = OB_SUCCESS; bool is_late_mat = (phy_plan_->get_is_late_materialized() || op.is_late_mat()); phy_plan_->set_is_late_materialized(is_late_mat);
spec.join_type_ = op.get_join_type(); if (MERGE_JOIN == op.get_join_algo()) { // 查询计划是merge join时的处理,暂略 } else if (NESTED_LOOP_JOIN == op.get_join_algo()) { // nested loop join if (0 != op.get_equal_join_conditions().count()) { } else { ObBasicNestedLoopJoinSpec& nlj_spec = static_cast<ObBasicNestedLoopJoinSpec&>(spec); nlj_spec.enable_gi_partition_pruning_ = op.is_enable_gi_partition_pruning(); const ObIArray<std::pair<int64_t, ObRawExpr*>>& nl_params = op.get_nl_params(); if (nlj_spec.enable_gi_partition_pruning_ && OB_FAIL(do_gi_partition_pruning(op, nlj_spec))) { // 如果可以的话,进行分区裁剪 } else if (OB_FAIL(nlj_spec.init_param_count(nl_params.count()))) { // 初始化join的参数数量 } else { ObIArray<ObRawExpr*>& exec_param_exprs = op.get_stmt()->get_exec_param_ref_exprs(); ARRAY_FOREACH(nl_params, i)// 遍历每个参数 { // 根据参数生成物理执行算子,具体内容略 } if (OB_SUCC(ret) && PHY_NESTED_LOOP_JOIN == spec.type_) { // 判断能否使用batch nlj,如果可以就更新flag bool use_batch_nlj = false; ObNestedLoopJoinSpec& nlj = static_cast<ObNestedLoopJoinSpec&>(spec); if (OB_FAIL(op.can_use_batch_nlj(use_batch_nlj))) {// 判断能不能用,当join条件有复数字段组成时不使用batch } else if (use_batch_nlj) { nlj.use_group_ = use_batch_nlj; if (OB_ISNULL(nlj.get_right()) || PHY_TABLE_SCAN != nlj.get_right()->type_) { // 只有table scan的时候才会选择batch nlj } else { const ObTableScanSpec* right_tsc = static_cast<const ObTableScanSpec*>(nlj.get_right()); const_cast<ObTableScanSpec*>(right_tsc)->batch_scan_flag_ = true; } } } } } } else if (HASH_JOIN == op.get_join_algo()) { // 查询计划是hash join时的处理,暂略 } const common::ObIArray<std::pair<int64_t, ObRawExpr*>>& exec_params = op.get_exec_params();
// 2. add other join conditions const ObIArray<ObRawExpr*>& other_join_conds = op.get_other_join_conditions(); // 初始化other condition OZ(spec.other_join_conds_.init(other_join_conds.count()));
ARRAY_FOREACH(other_join_conds, i) // 遍历剩下的条件 { // 逐个生成剩下条件的物理算子 } // end for
return ret;}


generate_join_spec() 对于 NLJ 最为特别的处理就是判断能否使用 batch NLJ,这也是我们所关注的第一个优化点。因此,我们通过扩展 OceanBase 对 batch NLJ 的支持和修改判定条件,使得 generate_join_spec() 能将比赛中的查询转化为 batch NLJ 的物理执行计划。



查询执行

Index Nested Loop Join为例


当逻辑执行计划里的 NLJ 经过 generate_join_spec 转换为物理的执行算子之后,OceanBase 就会通过火山模型逐层执行物理算子,并一次向上层算子呈递一行数据。对于 NLJ 而言,这部分功能主要由 ObNestedLoopJoinOp::inner_get_next_row() 实现。这一函数并不需要返回值,是因为它会直接通过修改上下文信息的方式保存一次调用所获取的数据。


作为一个 join 算子,ObNestedLoopJoinOp 很自然地含有两个子节点。对于比赛中的查询语句,我们可以很容易知道这两个子节点都是 table scan 算子。且不论左右节点的区别,每次调用 join 算子时需要从左右节点分别获取一行数据并连接。但在执行过程中可能出现很多种情况,比如右节点获取的数据与左节点获取的数据不匹配,遍历完右节点都无法与左节点当前的数据匹配等等。因此,为了更好地实现这部分逻辑,OceanBase 在函数中实现了一个小型的状态机,根据当前状态选择后续需要执行的函数。示意图如下:



其代码抽象如下:


int ObNestedLoopJoinOp::inner_get_next_row(){ int ret = OB_SUCCESS; if (OB_UNLIKELY(LEFT_SEMI_JOIN == MY_SPEC.join_type_ || LEFT_ANTI_JOIN == MY_SPEC.join_type_)) { // 处理半连接,具体内容略} else { ..... while (OB_SUCC(ret) && !output_row_produced_) { state_operation = this->ObNestedLoopJoinOp::state_operation_func_[state_];// state_取值为left right,表示当前执行左节点还是右节点的任务 if (OB_ITER_END == (ret = (this->*state_operation)())) { func = FT_ITER_END;// func的取值为end、going,对应取流程图中end或是going后缀的函数 ret = OB_SUCCESS; } else if (OB_FAIL(ret)) { } else { func = FT_ITER_GOING; } ..... } // while end} return ret;}


其中一共包含 6 个函数,分别是左右节点的 operate()、func_going()、func_end() 函数。其中,operate() 函数负责从对应子节点获取一行数据;func_going() 函数负责判断是否需要切换为另一个节点的函数,并做预处理,如 left_func_going() 会根据左节点获取的数据,准备扫描右节点所需要的参数(值得一提的是,因为实际上这个函数会深入底层更新右节点的迭代器,所以开销是很大的),right_func_going() 负责判断是否连接成功;func_end() 判断是否得到了需要的结果,并修改 inner_get_next_row() 的返回值。


在这 6 个函数中,func_going() 和 func_end() 的函数逻辑都比较简单,我们不再在这里赘述。以下主要介绍左右节点的 operate() 函数,这也是我们优化 batch_nlj 所主要关心的函数。



Join的左子节点实现

batch, or not batch


根据在构建物理执行树时的判断,left_operate() 存在两种执行逻辑,分别对应不使用 batch NLJ 和使用 batch NLJ。当不使用 batch nlj 时,函数直接调用对应算子的 next_row() 方法。这一方法会不断向下获取一行数据,具体的调用栈如下:


oceanbase::storage::ObmultipleScanMergeImpI::supply_consume()oceanbase::storage::ObmultipleScanMergeImpI::inner_get_next_row()oceanbase::storage::ObmultipleScanMerge::inner_get_next_row()oceanbase::storage::ObmultipleMerge::get_next_row()oceanbase::storage::ObTableScanStoreRowIterator::get_next_row()oceanbase::storage::ObTableScanRangeArrayRowIterator::get_next_row()oceanbase::storage::ObTableScanIterator::get_next_row()oceanbase::sql::ObTableScanOp::get_next_row_with_mode()oceanbase::sql::ObTableScanOp::inner_get_next_row()oceanbase::sql::ObOperator::get_next_row()oceanbase::sql::ObJoinOp::get_next_left_row()oceanbase::sql::ObBasicNestedLoopJoin::get_next_left_row()


通过检查代码,我们发现每层调用的逻辑都非常清晰,主要是调用下层接口以及异常处理,因此不再赘述。我们主要讨论使用 batch NLJ 时的执行逻辑。


当使用 batch NLJ 时,join 算子会先取出左节点中的一批数据,然后再逐个与右节点进行匹配。这种方式可以更好地利用数据的局部性,提高对磁盘数据的访问效率。为了实现批量获取数据,同时又不改变程序其他部分的逻辑,使用 batch NLJ 时需要在第一次调用时连续调用多次算子的 next_row() 方法并存储对应的数据,在后续调用时直接从存储的数据中导出对应数据。其代码抽象如下:


int ObNestedLoopJoinOp::group_read_left_operate(){ int ret = OB_SUCCESS; ObTableScanOp* right_tsc = reinterpret_cast<ObTableScanOp*>(right_); if (left_store_iter_.is_valid() && left_store_iter_.has_next()) { // 当前还有存储数据时,直接获取存储数据,具体内容略 } else { // 没有存储数据时,批量获取数据 if (OB_FAIL(right_tsc->group_rescan_init(MY_SPEC.batch_size_))) { } else if (is_left_end_) { // 判断左节点是否已经取完 } else { // 初始化存储数据的结构,具体内容略
bool ignore_end = false; //初始化或重置访问数据和它的迭代器left_store_和left_store_iter_,具体内容略
save_last_row_ = false; while (OB_SUCC(ret) && !is_full()) { // 批量获取数据 if (OB_FAIL(get_next_left_row())) { // 获取下一行 if (OB_ITER_END == ret) { is_left_end_ = true;
} } else if (OB_FAIL(left_store_.add_row(left_->get_spec().output_, &eval_ctx_))) {// 存储到存储到对应的结构left_store_中 } else if (OB_FAIL(prepare_rescan_params(true /*is_group*/))) { } else if (OB_FAIL(deep_copy_dynamic_obj())) { } else if (OB_FAIL(right_tsc->group_add_query_range())) { // 存储对应的右节点访问参数 } else { ignore_end = true; } } }
if (OB_SUCC(ret) || (ignore_end && OB_ITER_END == ret)) { // 更新迭代器left_store_iter_,并更新右节点的访问参数,具体内容略 } } }
if (OB_SUCC(ret)) { // 从存储结构left_store_里拿一行数据,作为本次调用的返回结果 if (OB_FAIL(left_store_iter_.get_next_row(left_->get_spec().output_, eval_ctx_))) { } else { left_row_joined_ = false; } } return ret;}


可以注意到,在执行过程中,group_read_left_operate() 会存储每一行数据对应的右节点访问参数。更具体来说,是这一行数据对应第一个 join 条件字段的值。因此,如果存在多于一个 join 字段,剩余的字段值不会被存储,这导致使用 batch NLJ 时无法正确根据join条件过滤结果,这也是 OceanBase 原本只限制在 join 条件唯一时使用 batch NLJ 的原因。为了使用 batch NLJ,我们对存储结构进行扩展,使它能存储剩余条件字段的值,从而保证对于比赛的查询语句也能有效且正确使用 batch NLJ。



Join的右节点实现

index merge


与左节点稍有不同,右节点并非是一个普通的 table scan,而是一个带有 index 的 scan。因此,在这个算子扫描结果的时候,会首先在索引表中进行搜索和定位,然后基于定位的结果直接构造数据表中的迭代器,从而加速数据的获取。这一流程在代码上的体现便是这个算子同时维护了两张表的迭代器,分别是数据表的 main_iter_ 和索引表的 index_iter_。其代码抽象如下:


int ObIndexMerge::get_next_row(ObStoreRow*& row){ ..... } else if (access_ctx_->is_end()) { // 已经扫描完了 } else { while (OB_SUCC(ret)) { if (NULL != main_iter_ && OB_SUCC(main_iter_->get_next_row(row))) { // 数据表获取到一行数据,直接结束 break; } else { ..... if (OB_SUCC(ret)) { // batch get main table rowkeys from index table // 初始化键值参数等结构,具体内容略 for (int64_t i = 0; OB_SUCC(ret) && i < MAX_NUM_PER_BATCH; ++i) { if (OB_FAIL(index_iter_->get_next_row(index_row))) { // 索引表获取数据 if (OB_ARRAY_BINDING_SWITCH_ITERATOR == ret) { ++index_range_array_cursor_; if (OB_FAIL(index_iter_->switch_iterator(index_range_array_cursor_))) { } } else if (OB_ITER_END != ret) { } } else { // 存储获取的数据 ..... } if (OB_SUCC(ret)) { if (OB_FAIL(table_iter_.open(rowkeys_))) { // 根据索引表的数据初始化数据表的迭代器 } else { main_iter_ = &table_iter_; } } } } } } return ret;}



总结:如何从代码结构上

对源码进行分析?


或许很多人会像我们一样,在一开始看到源码的时候不知所措。毕竟,OceanBase 作为一个非常庞大的项目,很难快速找到入手的部分。


根据我们的经验,在这种情况下,一般可以先使用 perf 来快速找到最耗时的执行部分,这部分代码往往与核心逻辑紧密相关,如我们上述展示的部分代码。在此基础上,结合 gdb debug,可以获取到执行过程中的主要调用栈。往往我们会发现调用栈很深,但是其中大部分的代码都不会涉及到核心逻辑,不需要逐个深入地研究。再通过 OceanBase 的代码自注释和基本的数据库知识可以有效地定位到所想要修改的部分。


当定位到要修改的部分之后,如何具体地分析源码的逻辑呢?首先需要熟悉 OceanBase 的代码风格,能将连续的条件嵌套重新翻译为顺序执行。然后通过代码的自注释去感受实现的功能,由于 OceanBase 中大部分的类都带有很多层的嵌套,在一开始不断深挖某个细节很容易晕头转向,采用“不求甚解”的态度,先宏观上把握整个执行流程,对于代码的分析会更有利。在了解了整体的流程之后,再结合逐步调试去深入理解其中的执行流程。


希望上述的方法分享,能够帮助大家分析 OceanBase 代码,为大家在开源社区中的贡献添砖加瓦。














关于 OceanBase 数据库大赛














「2021 OceanBase 数据库大赛」面向高校青年人才,自2021年8月开始报名,从初赛、复赛到最终总决赛历时 9 个月,吸引了国内外包括清华大学、北京大学、中国人民大学、南洋理工大学、美国哥伦比亚大学等 246 所知名高校在内的共 1179 支团队,近 2000 名数据库爱好者参赛,开创了国内分布式数据库领域产教融合的人才培养新模式。


经过总决赛激烈角逐及现场答辩,来自中国人民大学的 NoPassCET4 团队获得冠军,华东师范大学的东亚男儿、电子科技大学的 push_d_ 团队获得亚军,华东师范大学的 lying_flat、华东师范大学和青岛科技大学的 Honiitro19 团队、以及华中科技大学的两只老虎吃萝卜获得季军。



更多大赛详情回顾可以点击《产教融合加速数据库人才培养 | OceanBase数据库大赛10强诞生》进行回顾


大赛往期推荐:




首届OceanBase数据库大赛冠军!被北京青年报点赞的人大队伍谈参赛体验


钱卫宁:开源是培养数据库人才的关键|OceanBase 数据库大赛访谈


柴云鹏:创新能力的培养至关重要|OceanBase 数据库大赛访谈


范举:从0到1打造一个完整的数据库|OceanBase 数据库大赛访谈

这里,加入知乎话题探讨

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存