“从 0 到 1，打造你的数据库”， 作为国内首个分布式数据库内核开发大赛， OceanBase 数据库大赛于 5 月 10 日公布 10 强名单，2021 年大赛正式落下帷幕。

决赛的结束，也是大赛分享的开始。为帮助更多朋友了解参赛队伍背后的故事，这次我们请来了本期的特邀队伍 —— 中国人民大学 NoPassCET4 团队的队长黄人煌、队员涂荐泓、王元桢，我们一起来看看他们对数据库大赛的看法。

NoPassCET4 团队有话说
本次大赛的冠军团队由三位同学组成，分别是来自中国人民大学云计算与大数据系统实验室，研究方向为 NVM 数据库的黄人煌（队长）和王元桢同学，以及来自中国人民大学数据库与智能信息检索实验室，研究方向为数据挖掘与关系数据预训练的涂荐泓同学。在参赛的众多团队里，被亲切地称为极客世界的“神雕侠侣”！（戳下方视频了解他们

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

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

A:

我们三位队友的研究方向都是数据库相关，得知 OceanBase 数据库大赛，觉得这是一个难得的接触开源数据库和项目实战的机会，并且有丰厚奖金作为激励，就果断报名参加了。

Q:

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

A:

在这次比赛中，最深的感触就是数据库学习必须理论实践结合，有一些我们在课堂上学到的场景，在实际应用中需要考虑更多方面，只有去动手实现，才能深入理解与掌握。另外，数据库系统还处于发展阶段，一些较为成熟的技术，例如复赛环节的 NLJ 算法，在实际应用中和缓存等技术结合还有很多可优化的地方，而这些需要在动手尝试中探索出来。

Q:

作为本次数据库大赛的冠军团队，对明年大赛的哪些建议和期望？

A:

可以鼓励更多本科生参加，让本科生更早地接触真实数据库场景，尽早明白数据库发展情况，有利于数据库学子们更早地找到感兴趣的方向。

Nested Loop Join 探索更快的性能方案

赛题说明

本次赛题在 OceanBase 社区版基础上，针对单机版做小规格性能优化，使用 sysbench 做基准测试工具，针对 Nested Loop Join（NLJ) 场景做性能优化。JOIN 是数据库中查询多张表时的一个非常基础的操作，而 Nested Loop Join 是 JOIN 中经常出现，对数据库性能产生至关重要的关键影响作用。

决赛预赛的赛题和复赛一致，都是针对 NLJ 场景做优化，区别是增加了更严格的 mysql_test。

最朴素的 JOIN 算法

Nested Loop Join

JOIN 的基本操作是关联两张表，简单理解可以是左表的每条数据与右表的每条数据连接起来，不过需要满足一定的约束条件。Nested Loop Join 是最“朴素”的 JOIN 算法，原理是扫描(遍历)一个表（外表），每读到该表中的一条记录，就去“扫描”另一张表（内表）找到满足条件的数据。

可参考 OceanBase 社区版——联接算法测试的 SQL 样例。

select /*+ordered use_nl(A,B)*/ * from t1 A, t2 B where A.c1 >= 100 and A.c1 < 200 and A.c2 = B.c2 and A.c3 = B.c3，A 是外表，B 是内表

在 c2 列上会建立索引。原始版本在测试服务器上 TPS 为 1650 附近。

基于 OceanBase 社区版

NLJ 执行路径（新引擎）设计

为了对 OceanBase 的性能做深入分析，我们投入很大的精力深入分析了OceanBase 代码，下面是 NLJ 的主要执行路径。

1. ObNestedLoopJoinOp：OceanBase 采用了火山模型，NLJ 算法的入口是NLJ 算子。NLJ 算子，在这里进行 NLJ 的最上层调用，读左表一行去右表匹配，校验结果是否满足 Join 条件，并添加到结果集。

2. ObTableScanOp：TableScan 算子，这里发起 rescan 复用上次生成的查询计划。

3. ObTableScanIterator：通用迭代器，调度 ObIndexMerge 和 ObMultipleScanMerge。

4. ObMultipleScanMerge：外表的遍历。

5. ObIndexMerge：索引查询，样例 sql 的 c2 列是建立了索引的，所以在查询时会先用 c2 列的索引找到对应行的 key。

6. ObMultipleGetMerge：在第 5 步得到了 key 去 memtable 或者 sstable 得到具体行。

7. ObStoreRowIterator：存储层通用迭代器。

基于大赛的通用优化思路

基于大赛提供的基本思路及核心思想，在适当的地方使用 stmt_allocator 替换 allocator，以内存优化为主。stmt_allocator 和 allocator 都是内存分配器，他们析构时都会自动释放经过他们申请的内存。他们的区别是 stmt_allocator 的声明周期是语句级别，而 allocator 的生命周期是在 rescan 每次操作内。那么使用 stmt_allocator 替换 allocator 可以明显地减少内存申请释放频率，进而提升系统性能。

考虑到 allocator 分配的内存在每次 rescan 之后都会被释放，stmt_allocator 分配的内存在每次 sql 执行完之后才会被释放。所以，我们要尽量找能复用的对象，使用 stmt_allocator 分配，在每次 rescan 时不需要重新分配内存，创建对象。

• reuse_row_iters：每次 rescan 都会析构所有创建的 iter，并把 iters 数组清空。这里可以调用 iter 的 reuse 函数，复用这些 iter。相对应的，要把 iter 内部的对象用 stmt_allocator 分配内存。
  

• ObSSTableRowIterator：可以看到 ObSSTableRowIterator 的 reuse 内部析构了很多对象，这部分我们发现可以复用的包含：
  

 read_handles_
 micro_handles_
 sstable_micro_infos_
 micro_exister_
 micro_getter_
 micro_scanner_
 micro_lock_checker_
 block_index_handle_mgr_
 block_handle_mgr_
 block_cache_

• ObSingleMerge：对右表回表，通过 ObIndexMerge 的实现代码可以看出从索引表会一次拿 batch rowkeys，然后根据 rowkeys 数组通过 ObMultipleGetMerge 查询主表，如果每次只能从索引表拿到 1 个 rowkey，更适合的方式是使用 ObSingleMerge 查询主表。在这里加个判断，rowkeys 大小为 1 的时候使用 ObSingleMerge。
  
  
• report_stat：OceanBase 源码中有一些代码是用来记录状态信息的，去掉可以提升性能。
  

以上是官方提供的思路，所有做完 TPS 能达到 2300-2400。

核心优化方向

• free_large_pages ：这里我们针对比赛的特定场景，尽量提升缓存利用率，减少内存申请释放，做了一些调整。OceanBase 会调用释放一些大的页，在比赛场景下可以注释以提高 page 命中率。
  
  
• const int64_t OB_USER_MAX_ROWKEY
  _COLUMN_NUMBER = 64：OceanBase 设置的一行最多可以有 64 列，在此基础上创建的很多 buf 都是以 64 列为基础的，会占用不少时间。但是这是一个普适性的做法，在当前场景下非常不适用，我们可以针对性的做一些优化，把创建 buf 的大小修改。
  
  
• 针对新引擎一些未进行的深拷贝：这个思路来自于比赛时，我发现用最新的分支走进行测试会比比赛分支高 50，然后去查了一下原因。
  

  } else if (OB_FAIL(
                ObRawExprUtils::copy_exprs(expr_factory, other.user_var_exprs_, user_var_exprs_, COPY_REF_DEFAULT))) {
   LOG_WARN("deep copy user var exprs failed", K(ret));

在 src/sql/resolver/dml/ob_dml_stmt.cpp ，下增加了一些代码。顺着这个思路，修改了一些代码。

• query_range 复用：可以看到每次 rescan 都会 reset_query_range，通过复用，性能可以提高至 300 tps。原理跟减少内存申请释放频率的原理类似，对象复用也可以很好的提升系统性能，也是常用的性能优化手段。
  

以上这些做完，TPS 可以达到 3000。

创新的多线程优化

上面优化完成，思路基本上就终止了。我们团队尝试从其它数据库的思想借鉴一些过来，最先想到的就是 Oracle 的并行 JOIN 优化。Oracle 数据库利用 Bloom Filter 减少并行 JOIN 中从进程之间的数据通信量，实现连接过滤器修剪并支持结果缓存。

并行 JOIN 可以把一个任务拆分成多个子任务，然后并行执行，在有些场景下可以很好地加快速度。当两个表采用并行执行哈希(hash)或合并联接(merge join)时，需要在有多个从属进程之间交换数据集。例如，在以下查询的执行计划中，使用三组从属进程(每组从属进程拥有列 TQ 中的不同标识值)。

SELECT * FROM t1, t2 WHERE t1.id = t2.id AND t1.mod = 42

简单说明这条 SQL的执行计划：

Step 1：从属进程(Q1，00)应用过滤器“ filter("T1"."MOD"=42)”扫描表 t1 ，然后将过滤后的数据发送到从属进程(Q1，02)。

Step 2：从属进程(Q1，01)扫描表 t2 ，将数据发送到从属进程(Q1，02)。

Step 3：从属进程(Q1，02)接收从属进程(Q1，00)，(Q1，01)的数据。

Step 4：从属进程(Q1，02)把接收的数据生成哈希表。

Step 5：从属进程(Q1，02)把哈希表联接的行发送到主进程。

主进程接收数据并返回结果集。

核心优化点：

联接由从属进程(Q1，02)执行，因此从属进程(Q1，00) 和 从属进程(Q1，01) 发送的部分数据可能会因为不满足联接条件而被丢弃。换句话说，可能有不必要数据被发送到从属进程(Q1，02)而造成通信开销特别明显。这种情况下，如果使用 Bloom filter 在传递给从属进程(Q1，02)之前过滤掉不满足联接条件的大多数数据，就能避免不必要的通信，从而提高效率。

具体实现可以是从线程(Q1， 02)创建一个 Bloom Filter，在第 1 步扫描完 t1 之后，把符合条件的行的主键插入到(Q1，02)的 Bloom Filter 中。在接收（Q1，01）的数据时，可以直接过滤掉行号不在 Bloom Filter 的行。

再说 OceanBase 执行测试的 SQL ：

select /*+ordered use_nl(A,B)*/ * from t1 A, t2 B where A.c1 >= 100 and A.c1 < 200 and A.c2 = B.c2 and A.c3 = B.c3

通过阅读 ObNestedLoopJoinOp 源码，NLJ 的查询就是一个 while 循环，从左表读一行，然后从右表读结果，是一个单线程的过程。

我们参考 Oracle 的思路，A.c1 >= 100 and A.c1 < 200 是一个结果集。A.c2 = B.c2 and A.c3 = B.c3 也是一个结果集。我们进行并行 Join。这样就能进行拆分，在整个 benchmark，我们只需要一个线程去执行 A.c2 = B.c2 and A.c3 = B.c3 得到一个结果集。然后对所有的 SQL，只需执行 A.c1 >= 100 and A.c1 < 200，完全跳过右表，最后对两个结果集进行联接。

具体实现把连续的查询同样的表，和同样的列的 SQL 划成一个线程组。用一个主线程返回数据，再使用这些 SQL 的公共查询集构建一个 Bloom Filter（目前我的实现版本是把对右表的所有等值查询组成一个临时的结果集，会得到一个满足 A.c2 = B.c2 and A.c3 = B.c3 的 A 表主键 Bloom filter）。然后对每个从线程都循环访问左表，对满足 A.c1 >= 100 and A.c1 < 200 的行，看主键是否在 Bloom Filter 中。实现 Bloom Filter 以后，TPS 可以达到 12000。

• 跳过 prepare_rescan_param ：阅读 OceanBase 代码可以看到，每次 rescan 都会经历 prepare_rescan_params。按我们的做法，一个线程组只需要扫一遍右表。所以可以对这个函数标记，让扫完一次右表以后不再需要 prepare_rescan_params。能把 TPS 提升到 14000 。
  
  
• 跳过 drain_exch：观察 get_next_row 函数，在 OB_ITER_END == ret 时。回调用 drain_exch 。因为不确定这个函数具体作用，只是看到在火焰图中占比很高，于是设置在执行 NLJ 时的 get_next_row 不调用这个函数。
  

这些就是我们团队做的所有优化点，最后 TPS 达到 15888。

关于 OceanBase 数据库大赛

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

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