一、前言
埃隆·马斯克在造火箭带领人类移民火星，我在探索怎么在 MySQL 内核中实现 FULL JOIN 功能。
做为一名 DBA，敢给自己定这样的目标，要么我是脑子是烧坏了，要么我有很大的勇气。因为 MySQL 做为世界上最流行的开源数据库，已经在世界顶级内核开发者手中打磨了30多年，居然还没实现 SQL 标准中的 FULL JOIN 功能。阅读、调试过 MySQL 源码的人，我相信大部分人的感受是：对整体流程、细节的理解，就像一片孤舟漂泊在浩瀚的海洋中。
未知的工作量如此庞大，我又不甘心退缩，我该怎么安慰、激励自己继续前行？
埃隆·马斯克信奉第一性原理：要解决复杂问题，如造火箭，就必须深入到问题的核心，拆解成基本元素和原理，然后从这些最根本的事实出发，重新构建解决方案。他说过：制造经济、可靠、可重复利用火箭的关键步骤就27个，其它工程上的难度远比这个简单。于是我想，理清 MySQL Server 层源码内容的关键步骤应该不超过3个，努力一把还是很有希望的。
网上很多 MySQL 源码分析的文章，但很多都比较零散，看完的感受是：除了知道作者很厉害、牛逼之外，发现自己没有知识上的长进，因为自己做不出成绩！以色列为什么称霸中东、敢惹事，因为他知道周边国家不团结，再多的零串在一起，没有团结的1，结果还是零。于是我决定给自己定个目标：以实现新功能为目的去阅读这 MySQL 源码。于是选了这个 FULL JOIN 新功能。
二、环境、知识准备
MySQL版本选择：直接拉取最新的版本 8.3.0，个人 fork 地址：https://github.com/decilin/mysql-server.git
开发环境：Linux
IDE：Visual Studio Code （插件很丰富，个人很喜欢）
《C++ Primary》个人阅读完70%，看完不实践忘得很快，掌握效果远比不上直接阅读精品工程源码
我明明是学过 C++，为什么刚阅读 MySQL 源码时感觉连语法都看不懂了呢，因为它基本把系统的很多数据类型、STL 重新封装或造了一遍，所以这基本等价于还要在 C++ 的基础上重新学习 MYSQL 的源码编程新语言，入门的工作量一下就上来了。它里面的
mem_root_deque、List、Mem_root_array、QL_I_List、mem_root_unordered_map、Prealloced_array无处不在，这些都要当作基本的编程语法来学习了解。SQL 语法，能多了解就多了解，当DBA多年发现自己很多 SQL 语法居然没见过或者根本不知道它还能这么玩，导致阅读源码时不知道它在干嘛，需要重新复习、学习 SQL 语法。极力推荐认真学习这 SQL 语法：SELECT Statement、JOIN Clause
《flex与bison(中文版)》，要想掌握 MySQL 的语法规则配置 yacc 文件，至少要了解 bison。这本书大概 200 页，个人进眼不进脑地翻了一遍，感觉掌握的不到50%，但足够应付理解 MySQL 的
sql/sql_yacc.yyGDB Python API，只掌握 GDB 是不够我们很好地理解 MySQL 源码的，因为里面的数据结构很复杂，上百个数据成员的类至少有几十个，它们盘根错节地融合在一起完美地配合工作，只靠 GDB 是很难理清它们之间的复杂关系。GDB Python API 可以把我们想要的信息一起打印出来。
阅读量！这很重要，阅读这么庞大工程量的软件源码，如果没有足够的阅读量是很难理解它的整体工作流程、细节的。回顾下自己调通 FULL JOIN 功能的两周里，平均每天的代码阅读量大概在 2000，要了解的东西好多，好多东西是看完过了很久，随着量的积累才开始理解得过来。我有个搞游戏引擎内核开发的同学，他说一天要阅读2万行代码，我被吓得怀疑了人生，但我相信他是完全做到了的，因为他太成功和爱阅读了。去年的人工智能为什么获得了空前突破，OPENAI 的首席科学家 Ilya Sutskever解释：我们的算法还是跟以前一样没变化，但随着大语言模型参数开始达到 6 亿的时候，模型开始出现了涌现能力（类似智商从20直接跳跃到200）。所以说阅读量很重要，说不定随着个人阅读量的增加，我们也会出现涌现能力。
下面开始进入第一性原理的工作方式。
三、Server 执行流程探索
3.1 语法规则修改
修改 SQL 语法配置规则支持 FULL JOIN 语法。运用从 BISON 学到知识，修改 sql/sql_yacc.yy 如下，+ 号表示新增内容，- 号表示原版内容。
在 sql/parser_yystype.h 的 enum PT_joined_table_type 中添加 JTT_FULL、JTT_NATURAL_FULL 枚举类型
因为 TABLE 的结构体中的数据成员 outer_join 只代表是否是 left join 或者 outer join，没有信息可以判断是否是 full join，所以需要添加新建的是数据成员 `bool full_join{false};`
要在 `sql/http://parse_tree_nodes.cc` 的 join table 的语法树的解析函数中 `PT_joined_table::contextualize_tabs` 中添加对 FULL JOIN 语法的处理
在调试打印中，MySQL 的对 SQL 的打印只支持 LEFT JOIN，我们把它改造成支持 FULL JOIN 的打印
3.2 探索语法层次结构
MySQL 对一条 SQL 进行词法、语法解析后，会先按照语法层次结构生成 Query_expression、Query_block、Query_term 组成的结构。
我们先查看一条简单关联查询的语法解析结果：
# 构造表、数据
drop table if exists t1;
drop table if exists t2;
drop table if exists t3;
drop table if exists t4;
drop table if exists t5;
drop table if exists t6;
create table t1 (id int primary key, a int, b int default 0, c int default 0, d int default 0);
create table t2 (id int primary key, a int, b int default 0, c int default 0, d int default 0);
create table t3 (id int primary key, a int, b int default 0, c int default 0, d int default 0);
create table t4 (id int primary key, a int, b int default 0, c int default 0, d int default 0);
create table t5 (id int primary key, a int, b int default 0, c int default 0, d int default 0);
create table t6 (id int primary key, a int, b int default 0, c int default 0, d int default 0);
insert into t1 (id,a) values (0,0),(1,1),(8,8);
insert into t2 (id,a) values (0,0),(1,1),(2,2);
insert into t3 (id,a) values (1,1),(2,2),(3,3),(8,8);
insert into t4 (id,a) values (2,2),(3,3),(4,4);
insert into t5 (id,a) values (2,2),(3,3),(4,4),(5,5);
insert into t6 (id,a) values (2,2),(3,3),(4,4),(5,5),(6,6);
# 执行一条简单关联查询
select
t1.id as t1_id, t1.a as t1_a, t1.b as t1_b,
t2.id, t2.a, t2.b
from t1 full join t2 on t1.a=t2.a ;在函数 Query_expression::prepare开始的地方下断点，查看此时的对象结构、关系
Query_expression、Query_block 这两者的关系，在官方源码注释中有详细解释（这代码不能设置为不展开，太占用篇幅了，发现知乎对 MARKDOWN 的支持太弱了，对读者阅读造成很大的不方便）：
Class Query_expression represents a query expression.
Class Query_block represents a query block.
In addition to what is explained below, the query block(s) of a query
expression is contained in a tree expressing the nesting of set operations,
cf. query_term.h
A query expression contains one or more query blocks (more than one means
that the query expression contains one or more set operations - UNION,
INTERSECT or EXCEPT - unless the query blocks are used to describe
subqueries). These classes are connected as follows: both classes have a
master, a slave, a next and a prev field. For class Query_block, master and
slave connect to objects of type Query_expression, whereas for class
Query_expression, they connect to Query_block. master is pointer to outer
node. slave is pointer to the first inner node.
neighbors are two Query_block or Query_expression objects on
the same level.
The structures are linked with the following pointers:
- list of neighbors (next/prev) (prev of first element point to slave
pointer of outer structure)
- For Query_block, this is a list of query blocks.
- For Query_expression, this is a list of subqueries.
- pointer to outer node (master), which is
If this is Query_expression
- pointer to outer query_block.
If this is Query_block
- pointer to outer Query_expression.
- pointer to inner objects (slave), which is either:
If this is an Query_expression:
- first query block that belong to this query expression.
If this is an Query_block
- first query expression that belong to this query block (subqueries).
- list of all Query_block objects (link_next/link_prev)
This is to be used for things like derived tables creation, where we
go through this list and create the derived tables.
In addition to the above mentioned link, the query's tree structure is
represented by the member m_query_term, see query_term.h
For example for following query:
select *
from table1
where table1.field IN (select * from table1_1_1 union
select * from table1_1_2)
union
select *
from table2
where table2.field=(select (select f1 from table2_1_1_1_1
where table2_1_1_1_1.f2=table2_1_1.f3)
from table2_1_1
where table2_1_1.f1=table2.f2)
union
select * from table3;
we will have following structure:
select1: (select * from table1 ...)
select2: (select * from table2 ...)
select3: (select * from table3)
select1.1.1: (select * from table1_1_1)
...
main unit
select1 select2 select3
|^^ |^
s||| ||master
l||| |+---------------------------------+
a||| +---------------------------------+|
v|||master slave ||
e||+-------------------------+ ||
V| neighbor | V|
unit1.1<+==================>unit1.2 unit2.1
select1.1.1 select 1.1.2 select1.2.1 select2.1.1
|^
||
V|
unit2.1.1.1
select2.1.1.1.1
relation in main unit will be following:
(bigger picture for:
main unit
select1 select2 select3
in the above picture)
main unit
|^^^
||||
||||
|||+------------------------------+
||+--------------+ |
slave||master | |
V| neighbor | neighbor |
select1<========>select2<========>select3
list of all query_block will be following (as it will be constructed by
parser):
select1->select2->select3->select2.1.1->select 2.1.2->select2.1.1.1.1-+
|
+---------------------------------------------------------------------+
|
+->select1.1.1->select1.1.2Query_term，在官方源码注释中有详细解释：
Query term tree structure. There are five node types, cf. Query_term_type.
Leaf nodes are Query_block objects. We have three kinds of n-ary set operation
nodes corresponding to INTERSECT, UNION and EXCEPT. Finally, we have a "unary"
node which essentially adds a ORDER BY/LIMIT over another node.
Query blocks serve a dual purpose: they represent the query specification and
table constructors of the query. As such they are the leaf nodes of the query
tree. But they also serve as a way to realize ORDER BY and LIMIT for non-leaf
nodes, accessed via the function Query_term::query_block(). Therefore, every
non-leaf node in the tree has a companion Query_block to hold ORDER BY and
LIMIT information. For the leaf nodes, which are themselves query blocks, the
query_block() function just returns a pointer to self, i.e. the leaf nodes
handle ORDER BY and LIMIT themselves.
\verbatim
Example: ((SELECT * FROM t1 UNION SELECT * FROM t2 UNION ALL SELECT * FROM t3
ORDER BY a LIMIT 5) INTERSECT
(((SELECT * FROM t3 ORDER BY a LIMIT 4) ) EXCEPT SELECT * FROM t4)
ORDER BY a LIMIT 4) ORDER BY -a LIMIT 3;
->
m_query_term +------------------+ slave(s)
+--------------|-Query_expression |------------------+
| +------------------+ |
V post_ |
+-------------------+processing_ +----------------------+ |
| Query_term_unary |block() |Query_block | |
| |----------->|order by -(`a) limit 3| |
+-------------------+ +----------------------+ |
|m_children |
| +-----------------------+ +----------------------+ |
| |Query_term_intersect | |Query_block | |
+>|last distinct index: 1 |-->|order by `a` limit 4 | |
+-----------------------+ +----------------------+ |
|m_children |
| +-----------------------+ +----------------------+ |
| |Query_term_union | |Query_block | |
+->|last distinct index: 1 |-->|order by `a` limit 5 | |
| +-----------------------+ +----------------------+ |
| |m_children |
| | +------------+ SELECT * FROM t1 /
| +-->|Query_block | <---------------------------------+
| | +------------+ ----------------------------------+ next
| | \
| | +------------+ SELECT * FROM t2 /
| +-->|Query_block | <---------------------------------+
| | +------------+ ----------------------------------+ next
| | \
| | +------------+ SELECT * FROM t3 /
| +-->|Query_block | <---------------------------------+
| +------------+ ----------------------------------+ next
| \
| +-----------------------+ +------------+ |
| |Query_term_except |->|Query_block | |
+->|last distinct index: 1 | +------------+ |
+-----------------------+ |
|m_children |
| +----------------------+ |
| |Query_block | SELECT * FROM t3 /
+-->|order by `a` limit 4 | <------------------------+
| +----------------------+ -------------------------+ next
| \
| +------------+ SELECT * FROM t4 |
+-->|Query_block | <------------------------------------+
+------------+
\endverbatim
Note that all leaf query blocks representing the query specifications are
linked under Query_expression via their next pointers. The nesting is achieved
by the arrows on the left side of the figure, via the nodes' m_children
members. The four classes Query_term_unary and Query_term_{union, intersect,
except} are modelled via the base class Query_term_set_op which contains a
m_children member. Each of these also contain a Query_block which will handle
its order by and/or limit clauses. These are similar to the old so-called
"fake_query_block" (which is now gone), and are not linked in with "next"
pointers.
The is also a back pointer from the children nodes to the parent Query_term
object (not shown).
In the simple case of a single query specification (or table value constructor
or explicit table), there is no super-structure over the Query_block linked
from the Query_expression, i.e. Query_expression's m_query_term member is just
a Query_block.
The query blocks (QT_QUERY_BLOCK nodes) corresponding to the query
specification (or table value constructors) are prepared and optimized by
running over them from the Query_expression via the slave/next pointers as
before. There are separate methods which handle prepare and optimization for
non-leaves, i.e. nodes of types QT_UNARY, QT_INTERSECT, QT_EXCEPT and
QT_UNION.
We also define an iterator class (Query_terms) for iterating over all
the nodes in the tree, see also Query_expression::query_terms() for its use.
When possible, we access all nodes using iterators.
The built structure can be traced with the debug trace keyword "ast", e.g.
as SET SESSION debug = 'd,ast:O,/tmp/mysqld.trace';
拿 Query_term 类的源码注释中的 SQL 例子解释它们三者的关系。
# 源码 Query_term 类注释中的 SQL 例子
(
(SELECT * FROM t1
UNION
SELECT * FROM t2
UNION ALL
SELECT * FROM t3
ORDER BY a LIMIT 5
)
INTERSECT
(
(
( SELECT * FROM t3 ORDER BY a LIMIT 4 )
)
EXCEPT
SELECT * FROM t4
)
ORDER BY a LIMIT 4
) ORDER BY - a LIMIT 3;在函数 Query_expression::optimize 开始的地方下断点，查看此时的对象结构（图形太大了，知乎不支持高清图片，只能展示 SVG 图形的链接，需要读者麻烦打开查看，顿时觉得知乎这方面太不友好了，对读者阅读造成很大的不方便）：
到此、词法分析、语法的分析工作完成（发现这块没有对FULL JOIN 进一步处理）。接下来是语义分析、SQL 优化工作。
3.3 探索 Query_expression、Query_block 的 prepare、optimzie 工作流程
详细阅读完这两个类的代码，发现都没有对 FULL JOIN 进一步处理，所以跳过。
（我手头对这两个类的每一个重要优化步骤，都画出对应的图，对我的理解帮助很大。但知乎不支持高清图，所以这里就不展开介绍了，如果大家有兴趣的话，我再另外开新篇幅详细图文讲解）。
3.4 探索 JOIN 的 optimzie 工作流程
MySQL 8.0 版本开始对 hypergraph_optimizer 支持，但默认是关闭的。在开源界中，我认为它目前是 join order 算法中最领先的，它是其它开源数据库优化器的未来。所以在这里，我选择了在 hypergraph_optimizer 中打造 FULL JOIN 新功能，需要执行 SQL 之前设置 set optimizer_switch="hypergraph_optimizer=on";。
JOIN 的 optimzie 工作过程中，它会生成对应 Query_block 的整个 JoinHypergraph，它是寻找最低成本模型之前的最后一步。
SQL 中的每个关系连接谓词都会对应一个 RelationalExpression，它里面的数据成员 type 会记录连接类型，这里我们需要添加它对 FULL JOIN 的支持：
修改 `sql/join_optimizer/http://make_join_hypergraph.cc` 中的函数 MakeRelationalExpressionFromJoinList
生成 RelationalExpression 之前的整个函数调用堆栈是：
(anonymous namespace)::MakeRelationalExpressionFromJoinList(THD * thd, const mem_root_deque<Table_ref*> & join_list)
MakeJoinHypergraph(THD * thd, std::string * trace, JoinHypergraph * graph, bool * where_is_always_false)
FindBestQueryPlanInner(THD * thd, Query_block * query_block, bool * retry, int * subgraph_pair_limit, std::string * trace)
FindBestQueryPlan(THD * thd, Query_block * query_block, std::string * trace)
JOIN::optimize(JOIN * const this, bool finalize_access_paths)
Query_block::optimize(Query_block * const this, THD * thd, bool finalize_access_paths)
Query_expression::optimize(Query_expression * const this, THD * thd, TABLE * materialize_destination, bool create_iterators, bool finalize_access_paths)我们可以看到整个 SQL 的语义优化流程是：Query_expression::optimize --> Query_block::optimize --> JOIN::optimize。
我们来确认下我们的改造是否符合预期，在函数 MakeRelationalExpressionFromJoinList末尾下断点，然后查看生成的 `RelationalExpression` 是否有 RelationalExpression::FULL_OUTER_JOIN 。
可以看到最顶的 RelationalExpression 有 RelationalExpression::FULL_OUTER_JOIN 。
上面这张图我自己都看不清楚，这知乎的图像太差了，我重新个高清的图形链接，需要读者辛苦点开查看：
完成对 JoinHypergraph 的构建后，会执行 EnumerateAllConnectedPartitions 对超图所有可能 JOIN ORDER 进行枚举，枚举最佳路径过程中需要计算每个 JOIN 谓词的输出行数。需要在 `sql/join_optimizer/cost_model.h` 的 FindOutputRowsForJoin中添加对 FULL JOIN 的支持。它的模型计算方式是: RelationalExpression::LEFT_JOIN + RelationalExpression::ANTIJOIN 。其实有更好的计算模型，但这个模型比较容易实现，咱们先按这个办法来实现。
寻找到最佳 JOIN ORDER 路径后，会生成对应的 AccessPath。需要改造 AccessPath 生成火山迭代器时对 FULL JOIN 的支持。这次只做对 HASH JOIN 迭代器的改造，NEST LOOP JOIN 迭代器的改在以后有空再打造。
修改 `sql/join_optimizer/http://access_path.cc` 中的函数 CreateIteratorFromAccessPath，在 case AccessPath::HASH_JOIN: {部分添加对 FULL JOIN 支持：
我们在 CreateIteratorFromAccessPath 函数末尾断点，查看生成的迭代器结构，可以看到最顶是 HashJoinIterator，它的左右两边都是 TableScanIterator：
知乎不支持高清大图，我发个大图形链接，辛苦读者打开查看
3.5 对 HashJoinIterator 改造的经历、思考、决策
看完 HashJoinIterator 的源码，我感觉挑战好大，虽然核心只有1000多行代码，但涉及其它的类、方法很多，如果要遵循最佳算法来改造，工作量是非常巨大的。回顾 MySQL 的 HASH JOIN 历史，它在顶级程序员手中大约经历了25年，一直到8.0版本才开始支持，如果容易实现的话，也不会拖了这么长的时间。
对这个 HashJoinIterator 的改造，我大约尝试了3天才成功。第一次的改动大约花了半天时间，想通过一次扫描完成这个 FULL JOIN，但发现自己对细节理解不够，导致一直没返回期望的结果。然后花了两天的时间重新把整体流程、细节确认清楚，再花半天时间开始动手改造，居然返回了预期的结果，完成了人生第一次对内核的改动，很开心。
HashJoinIterator::m_row_buffer::m_hash_map 这个数据成员初始化一次后，不好清空，因为以后还有可能重复利用。所以你很难在不添加新数据成员的情况下能让它支持 FULL JOIN。在有限的时间内，我们最好的做法可能是继续站在巨人的肩膀上，做出最少的改动来实现功能。
对 sql/iterators/hash_join_iterator.h 和 sql/iterators/hash_join_iterator.cc改动的地方挺多，思路是再添加一个新的 m_hash_map 存放另外一张表的 hash key，然后添加个新状态标记 full_to_anti 判断是否进入 anti join 阶段。在完成一个 LEFT JOIN 后，再增加一次 ANTI JOIN 流程。
可能有人会说其实 FULL JOIN 是可以把两张表的 HASH JOIN KEY 放到同个 hash key 中，对 hash map 的 second 进行打标签表示哪些表有该记录，最后对 hash map 执行一次全扫描就能完成 FULL JOIN 功能，少了一次 ANTI JOIN。
从算法上感觉上面的做法最佳，但实践上可能不是，因为 MySQL 的 has map 使用了 std::String_view，因为它不能修改，所以 has map 的插入、查询性能比使用 std::String 会高很多。因为如果使用上面的算法，必须使用 std::String 才能实现 hash map 的 second 进行打标签。
我这边决定继续选择坚持在巨人的肩膀上，最少的改动量来完成任务。所以在 sql/iterators/hash_join_iterator.cc 的每个有 `m_probe_input_tables、m_build_input_tables、m_row_buffer` 的地方，都有两个分支，比如：
在 HashJoinIterator::ReadRowFromProbeIterator 函数中添加对 LEFT JOIN 的处理完成后，进行 full_to_anti 的切换，进入 ANTI JOIN 流程：
至此，所有的代码改造工作完成。
四、测试 FULL JOIN 结果
五、感悟
我小时候玩过一款当时很火的单机游戏叫《英雄无敌3》，里面有张超级经典的图叫 《归隐田园》，当时不会上网看攻略，也没人交流怎么玩，全靠自己摸索。第一次玩这图时，全程被几十倍军力的敌人追杀着满地图逃跑，经过多次的尝试，最后不小心发现了电脑AI的弱点，以弱胜强侥幸战胜敌人，然后觉得自己在这游戏上是个绝顶高手！
直到有一天我进去百度的《英雄无敌》贴吧，发现《归隐田园》只是判断一个玩家水平是否小学毕业及格的标准，当时觉得不可能，后来查看几个攻略，发现别人都玩出了各种新花样吊打电脑，最夸张的是有人修改地图，7天完成通关。当时我都傻了眼，发现在这个圈子里自己简直是个大菜鸟。
回头看看这几年国产数据库的发展，都已经完成了各种新花样，高峰期全国大概300多个数据库创业团队，很可能每个团队都在搞内核开发，厉害的厂商在内核上玩出各种新花样，比如分布式、HTAP架构、各种不同存储引擎支持、各种打破世界TPCC记录、支持信创、上银行核心生产系统、服务海外。
这些让我感觉自己始终像个菜鸟，相对那些内核高手，可能我连入门都算不上，所以我起了个叫《MySQL 优化器源码入门》的标题。本来想在讲解过程中多增加优化器工作细节原理分享，但知乎对高清大图支持不好了。
如果继续搞这个内核研究的话，要走的路很长很长~~~
欢迎关注公众号：DBA札记，一起交流数据库技术。欢迎觉得读完本文有收获，可以转发给其他朋友，大家一起学习进步！谢谢大家。
