# 参赛经历

2025 年 10 月底，我和去年的队友再次参加了第五届 OceanBase 数据库大赛。尽管可以提前开发，但是我们都比较忙直到初赛正式开始后才开工，耗费 2 个多星期时间，在 11 月 9 日晚上终于 AK 了今年初赛的全部题目。我们是第 26 名 AK 的队伍，也是广东省的第一。

这一次比赛，我修好了很多去年的 BUG，也成功挑战了更难的题目。截至我们 AK 为止，通过率最低的 2 道那难题 full-text-index (全文索引) 和 create-view (视图) 都由我负责完成。

对于这样复杂的项目实现复杂的功能，数据结构的设计是最重要的。数据结构设计的好，写起来就会得心应手，代码也更美观。这个过程是需要也值得多花时间的，在做后面几道难题时，我思考设计数据结构的时间基本占到总的开发时间的一半。尽管如此，依然会写着写着发现设计的有问题，然后又重新设计重写数据结构和接口，有的时候会哭笑不得的发现反复重写两三次最后又回到一开始的设计或者整个被另一个设计思路取代而删掉。

# 关于 Expression

今年我发现，之前数据结构的设计存在非常糟糕的问题，既出现在子查询也出现在 Order By，这个问题就是：

$$Expression$$

Expression 去年也是我实现的，但去年我没有意识到 Expression 的思想的重要性，毕竟当时的我没有系统学过《编译原理》。

Expression 代表的不仅仅是简单的数学计算表达式，而是一种编程语言的设计思想。在几乎所有语言设计中都一定会用它来表示全部的 右值。其实相应的，也有 “左值表达式”，那就是所有可以被赋值、被定义的东西，它当然也可以是一种表达式，只是没有那么复杂所以并不总是吸引人们的注意。这里我们讨论的 Expression 主要还是 右值表达式。

所有的编译原理课程一定会讲到 Expression 的设计，讲到他如何处理运算的优先级。而在实际写一个编译器的时候，我们总是会它用来表示：所有赋值语句的右侧、所有函数调用的传参、所有返回语句的结果...... 它无处不在。

为什么使用 Expression 后一定代码更简单、顺畅、美观？原因很简单：能很自然地复用 Expression 的逻辑和代码实现。所以 Expression 的思想归根到底还是逻辑的复用，并且同时是代码逻辑和语法解析逻辑的复用。

# Order By

去年我的 Order By 有一个愚蠢的设计失误：我把 Order By Operator 放在了 Project Operator 的上面 (根节点)。这是我当时想着 Order By 需要收集所有最终结果来完成排序时所得到的一个想当然的实现。这会导致 Order By Operator 只能拿到被投影过的 tuple，比如 SELECT A FROM t ORDER BY B 的时候就会发现 Order By Operator 根本得不到排序所需要的 B 的值。

还有一个问题就是 Expression 了，我在 ORDER BY ... 后面没有用 Expression 表示排序的 key。同样也是今年需要支持 Order By 后面允许函数才发现这个问题。这一问题比较好处理，切换成 Expression 比较简单，切换后非常顺畅就实现了新的需求。

至于 big-order-by 这道题目，是队友优化完成的，他的思路看起来投机取巧，不是外排序实现的。因为排序时所有的值都是 int 类型，所以他在检测到排序数据量很大时，把所有的 Value 都转化为 int，然后对 int 类型的数据排序，最后输出前慢慢转换回去。Value 改为 int 节省了很多内存，足以通过测评。

这看起来像是邪门歪道，但在真实的业务场景，倘若真的对海量数据排序，往往全都是对 int 类型数据比较，那么额外的抽象数据结构确实带来了大量冗余无用的内存负担，将它们优化掉是完全合理有必要的。

# 子查询

我实现的子查询没有用 Expression 表示。在今年发现 UPDATE ... SET A = B 这样的语句中 B 需要支持子查询时，我才意识到这个问题。子查询最终我也没有修正回 Expression 的设计，因为已经庞大复杂的代码迁移起来比较头疼，懒得再改了，我额外处理了一遍 UPDATE 的情况。

子查询还有一个非常需要注意的地方，那就是实际上子查询并非是只执行一次就够的，它的父级查询获取得到了多少个 tuple，它就需要执行多少次。例如如下这个 SQL 语句:

SELECT * FROM t1 WHERE t1.id IN (SELECT t2.id FROM t2 WHERE t2.id <= t1.id);

这里的子查询 (SELECT t2.id FROM t2 WHERE t2.id <= t1.id) 需要针对每一个从 t1 中获取到的 tuple 执行一次，才能得到正确的结果。所以需要注意，每一次当前查询获取到一个当前 tuple，都需要 open 一次子查询树，执行一遍子查询，完成相关操作后进行 close 。

至于父级 tuple 的信息如何向下传递给子查询呢？我的实现是基于火山模型的 next 方法创建了一个特殊的 next_with_tuple 方法，根级首次查询调用这个方法的时候放入当前自己获取到的 tuple，在经过每一级子查询语句的时候，都会把传下来的这个 tuple 上附加到子查询当前获取到的 tuple 上，这样 PredicatePhysicalOperator 等算子就能看到所有父级查询 tuple 信息了。

当然这一套本质上是编译原理的作用域，更加经典的实现是给每一级查询定义一个作用域，当前作用域找不到的继续到上一级作用域找。

# alias

在 alias 的实现中也需要开始实现类似作用域的处理，因为子查询需要可以创建遮蔽父级查询的 alias。

但是在实现子查询的时候，我在语义分析阶段并没有给每一级查询创建一个 ExpressionBinder 也就是 Field 的绑定上下文 (也就是编译原理中的变量绑定上下文)，而是把父级的上下文直接传给了子查询。所以我只好修改 ExpressionBinder 内部实现，让它区分哪些 alias 和表是父级查询的、哪些又是当前查询的。

我给表和 alias 查询表分别划分了 2 个集合来进行区分，在每次准备对子查询进行语义分析处理之前，把当前查询集合里的全部放到父级查询里就行了。而在进行绑定操作的时候，优先在当前查询的集合里找，找不到再到父级查询的集合里继续找，从而实现 “变量遮蔽” 的功能。

# union

原本的投影算子 Project 只有一个子节点，可能是 OrderBy、GroupBy、Predicate。既然 union 的几个查询列一定是相同的，那么 Project 也一定是相同的。所以我把 UNION 的所有其他查询一个接一个放到这个共同的 Project 下面，让 Project 按顺序对所有子树获取 tuple 就行了。

# 视图

在着手开始视图的开发前，我阅读参考了 2024 年同样二战 AK 入围决赛的 soulter 的博客。soulter 写的非常详细，整体思路描述的非常清晰，讲到了很多坑，他们甚至开源了自己的代码。不过我并没有看他们的代码，毕竟我都好不容易自己写了这么多题目了，为什么不全部自己写下去呢？

视图的实现思路主要是把视图的定义存储下来，然后在查询时把视图展开成对应的查询语句再执行。看上去非常简单，然而真正复杂的地方在视图的更新。今年这道题目官方给视图的更新写了详细的说明，以前还是没有的，所以去年 soulter 他自己测试了 MySQL 的视图更新逻辑和规则。

MySQL 会将视图的定义存到一个名为 INFORMATION_SCHEMA 的特殊的 DB/Schema 的一个特殊的表 VIEWS 之中，同时每一个视图本身所定义的 DB/Schema 和它所实际查询的表所在的 DB/Schema 可以是不同的，也就是视图的定义包含自己所在的 DB/Schema 这一属性。在 MiniOB，始终只有一个 DB/Schema sys ，所有的表也都放在这里面。所以简单起见我直接将视图的定义存到这个 sys 里的一个特殊的表 __VIEWS__ ，并且认为所有视图都属于这个 sys 。我将我的表 __VIEWS__ 设计如下：

/**

  @brief 存储所有视图的特殊表

  @ +------------+------------+------+

  @ | Field      | Type       | NULL |

  @ +------------+------------+------+

  @ | SCHEMA     | char (64)  |  NO  |

  @ | NAME       | char (64)  |  NO  |

  @ | ATTR_NAMES | char (255) |  YES |

  @ | DEFINITION | char (255) |  NO  |

  @ | ID         | int        |  NO  |

  @ +------------+------------+------+

 */

const char VIEWS_TABLE_NAME[10] = "__VIEWS__";

const int VIEWS_TABLE_FIELD_NUM = 5;

const AttrInfoSqlNode VIEWS_TABLE_ATTRS[5] = {

  AttrInfoSqlNode{AttrType::CHARS, "SCHEMA", 64, false},

  AttrInfoSqlNode{AttrType::CHARS, "NAME", 64, false},

  AttrInfoSqlNode{AttrType::CHARS, "ATTR_NAMES", 255, true},

  AttrInfoSqlNode{AttrType::CHARS, "DEFINITION", 255, false},

  AttrInfoSqlNode{AttrType::INTS, "ID", 4, false}

};

由于创建视图时可以 CREATE VIEW(A, B, C, ...) AS ... 的形式重新定义查询出来的列名，所以这些 A,B,C 信息也要存到 __VIEWS__ 之中，也就是上面的 ATTR_NAMES ，我存成逗号分隔的字符串。

当然 MySQL 实际上是用 text 类型存视图的定义 SQL 语句的，然而此时我的队友 Luv 负责实现 text 还没做完，我就先用 CHARS 类型了。

那么怎么查询一个视图呢？只要能将视图视为一种特殊的表，或者说抽象的表，就能支持可能对它执行的复杂查询。soulter 的实现稍微暴力，他将需要解析的视图定义、视图名字、视图 Stmt 都放在了 SQLStageEvent 中，在处理一条 SQL 语句的每一个阶段 (语法解析 -> 语义分析 -> 优化 -> 执行)，检查有没有视图，有的话就同时也处理视图 SQL 语句，在最后的执行阶段把视图的物理执行算子拼接到对应表的扫描算子下。

我觉得这样设计有点奇怪也不够优雅，首先有一个问题就是完全没有必要每次都解析一次查询语句，在初始化视图到内存的时候解析一次就够了，后面每次复用这个解析得到的物理执行算子树，这也是我的实现思路。

在数据库初始化的时候会将磁盘上表元数据读入内存名为 Table 的数据结构，MiniOB 比较暴力直接读取所有表元数据文件将全部表读入内存，由于我们不是生产级数据库暂时不考虑内存装不下所有表、视图元数据的情况。我给 Table 加了一个成员 unique_ptr<PhysicalOperator> 类型的 query_tree_ 代表视图查询的物理执行树，以及一个简单的方法 is_view() 在这个树存在 (指针非空) 的时候返回 true 。数据库初始化的时候，也读取我的 __VIEW__ 表，解析查询语句存入 query_tree_ ，创建 Table 。

事实上还有一种思路是视图应该在语义分析阶段完成，也就是 Optimizer 里完成。将视图的展开视为一种查询语句的重写 (rewrite)，而查询语句的重写本来就是优化器需要做的事情之一，通过新增一种 Rewriter 来实现。

至于上面 soulter 的那个拼接过程是怎样的呢？如下是他的博客原文:

原本扫描表的物理算子有且只有两种： TableScanPhysicalOperator 和 IndexScanPhysicalOperator ，他的实现仅处理了前者的情况，但也并没有问题，因为视图无法被创建索引，永远不会扫描视图的时候使用 IndexScanPhysicalOperator 。

我决定直接为表的扫描创建一个新的算子 ViewScanPhysicalOperator ，在生成物理执行计划的时候检查表的 is_view() 来决定使用该算子。这个算子和原来的 TableScanPhysicalOperator 没有太大差别，只需要将 open 、 next 、 close 、 current_tuple 从原本调用 RecordFileScanner 改为调用视图的 query_tree_ 作为子节点。不过注意 既然选择了复用 PhysicalOperator ， query_tree_ 的所有权始终是属于其所属视图 Table 的，所以新算子存这个查询子树要存成普通指针而不是物理执行树默认的独享指针。

现在来看最复杂的视图更新，但是复杂的更新规则实际上过滤下来会发现总是只允许视图同时更新一个基表，只需要更新的时候确定是哪一个基表，然后从那个基表的 TableScanPhysicalOperator 获取 RID 就行了。

soulter 的方案如下：

他给 tuple 的每一个 cell 也就是 Value 加上了 RID rid_ 和 string table_name_ 两个成员。这非常冗余，但是他也因此得到了另一个好处：

诶 🤓，你猜 MySQL 为什么不支持这个功能？因为 MySQL 没有给 tuple 的每一个 cell 加上 RID 信息。

最后我的做法则是给 PhysicalOperator 增加了一个方法 view_update_rid() ，虚类上默认实现为递归调用全部子节点的方法，在 TableScanPhysicalOperator 结束递归返回所需的 RID。当然只需要一个 RID，因为正如先前所述，更新的时候永远只会更新一个基表，只需要知道那一个表的当前 tuple 的 RID 即可。

上面的处理实际上仅在 UPDATE 的时候是需要的，其他更新操作并不需要 RID 信息。而 INSERT 的时候刚加简单，只需要在语义分析阶段也就是创建 Stmt 的时候，检查 INSERT 的字段是否来自同一个基表，否则不允许插入，是的话就记录下这个基表等到执行的时候对该表插入即可。需要注意初始化一个全为 NULL 的更新需要的 Value 列表，然后按照指定的插入字段和值填充，保证其他字段默认为 NULL。对于 DELETE，完全不允许对多基表视图操作，无需考虑。

# 全文索引

全文索引 (full-text-index) 是一道今年的新题目，实现思路主要是建立倒排索引 (Inverted Index)，将每个词语映射到包含该词语的文档列表。这样，在查询时，可以快速定位包含特定词语的文档，从而提高查询效率。

全文索引需要分词器 (tokenizer)，题目指定使用 cppjieba，应该是默认分词模式因为最后也是这样过的测评。实现分词语句比较简单，只需要创建一个二元操作 Expression 表示分词操作即可，所以我创建了 TokenizeExpr 。然后还需要输出一个疑似 CHARS VECTOR 的东西，为此我创建了一个只存在于内存中的 Value 数据类型，专门显示 vector<string> 分词结果。创建全文索引的上层实现也比较简单。

测试全文索引的语句疑似只有一种，形式如下：

SELECT id, content, MATCH(content) AGAINST('某个Query') AS score \

  FROM texts WHERE MATCH(content) AGAINST('某个Query') > 0 \

  ORDER BY MATCH(content) AGAINST('某个Query') DESC, id ASC;

首先还是需要加一个 Expression，我叫它 MatchExpr，用来识别 MATCH(content) AGAINST('某个Query') 。

一开始，我新加了一个 OrderByPushdownRewriter 在 Order By 里出现 MatchExpr 时下沉到在 IndexScanner 那里完成排序，然后发现这样有很大问题，我完全忘记了排序后面还有一个 id ASC ，而 IndexScanner 本身设计就不应该扫描表访问 Record，所以我也不能在这里获取 tuple 计算排序的其他键值。

那要不要改到 IndexTableScanPhysicalOperator 呢？这时我就发现完全没必要下沉了，B + 树索引下沉是因为完全可以去掉排序逻辑，但倒排索引只是计算 BM25 评分，还要排序的话没必要复制一份排序逻辑到底层，我只让 IndexScanner 提供 RID 以及相应的 BM25 评分即可。

那么，我要不要像先前实现视图时候一样搞一个火山模型上递归调用的方法获取 BM25 的值呢？这样写会发现还是有个麻烦，那就是所有会对 MatchExpr 取值的地方都要我去修改逻辑。这就很不好了，这个获取 BM25 评分的操作最好能被封装到 MatchExpr 类自己的方法里，也就是 get_value(const Tuple tuple, &Value value) 。那么我只能将 BM25 信息放在每一次向上传递的 tuple 里，这样 MatchExpr 执行 get_value 的时候才能得到 BM25 信息。那么我应该像 soulter 一样在 Tuple 这个类里加一个成员吗？还有一个巧妙一点的办法是在 IndexTableScanPhysicalOperator 返回 tuple 给上层的时候加那么一个 cell 表示当前这个 RID BM25 评分。而 MatchExpr 的 get_value 方法中怎么找到这个 cell 呢？可以通过 TupleCellSpec 匹配，但这道题目不考虑 Join 操作，所以只有一个表，我就简单地把这个 BM25 加到原始 tuple 的最后面，MatchExpr 的 get_value 方法也直接从这个位置取即可。

最后我把原本的 OrderByPushdownRewriter 简单修改，不再 pushdown 而只是找到 ORDER BY 后面的 MatchExpr，存到 TableGetLogicalOperator 让其在生成物理执行计划的时候选择使用倒排索引 Index。当然，这一切都建立在整条 SQL 语句出现的 MatchExpr 始终是同一个的条件下，万一出现多种 MatchExpr，他们的 Field 和 Query 不同，那么就得对所有 Expression 做一个处理，找到所有 MatchExpr 并把他们的 Field 和 Query 往下传递，并且出现多个 Field 时，已经是 Multi Index 的情况了，太复杂我就没有再考虑。

所幸，这道题确实测试语句其实没有那么复杂，一条 SQL 语句始终只有一个 MatchExpr。我还发现系统测评实际上不会重启 observer 测试持久化，因为创建全文索引的 create 代码漏了父类 Index 的初始化，而读取表元数据文件 open 的代码没有问题，我本地脚本测试经常重启 observer 所以没发现 create 的问题，反而在官方测评里出现了...... 总之，过测评甚至不需要考虑持久化倒排索引信息，“内存数据库” 都能搞定。

不过我的实现当然还是老老实实持久化了的，由于倒排索引是 token 为键、所有包含该文档的相关信息为值的键值结构，我很自然地用一个简单的 Json 文件存储。我设计的 Json 结构如下：

{

  "total_doc_num": 114514,

  "total_doc_len": 1919180,

  "inverted_index": {

    "我是一个token": [

      [0, 0, 350, 234],

      [0, 1, 350, 234],

      [0, 2, 350, 234]

    ],

    "我是另一个token": [

      [1, 0, 123, 456],

      [1, 2, 123, 456]

    ],

  }

}

除倒排索引本身之外还有 2 个整个表统计下来的数据 total_doc_num 和 total_doc_len ，在计算 BM25 的时候需要用到。倒排索引本身以 token 为键，值为一个列表，列表包含多个四元组。每一个四元组代表一个文档，内容为 [PageNum, SlotNum, TermFreq, DocLen] ，前面 2 个共同组成一个 RID，后面 2 个则同样是是计算 BM25 的时候需要用到。

# null

最后放一个赛博案底，Value 是 4 字节的，我存成 4 个 0xEE 特殊值来表示 NULL。

什么，你问我 bitmap 是啥？我不知道。