MySQL 优化器源码入门内核实现 FULL JOIN 功能

数据运维 2024-05-27 爱可生开源社区手机阅读

一、前言

埃隆·马斯克在造火箭带领人类移民火星，我在探索怎么在 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.yy
GDB 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
如下，+ 号表示新增内容，- 号表示原版内容。

MySQL 优化器源码入门内核实现 FULL JOIN 功能-每日运维

在 sql/parser_yystype.h
的 enum PT_joined_table_type
中添加 JTT_FULL、JTT_NATURAL_FULL
枚举类型

MySQL 优化器源码入门内核实现 FULL JOIN 功能-每日运维

因为 TABLE
的结构体中的数据成员 outer_join 只代表是否是 left join 或者 outer join，没有信息可以判断是否是 full join，所以需要添加新建的是数据成员 `bool full_join{false};`

MySQL 优化器源码入门内核实现 FULL JOIN 功能-每日运维

要在 `sql/http://parse_tree_nodes.cc` 的 join table 的语法树的解析函数中 `PT_joined_table::contextualize_tabs` 中添加对 FULL JOIN 语法的处理

MySQL 优化器源码入门内核实现 FULL JOIN 功能-每日运维

在调试打印中，MySQL 的对 SQL 的打印只支持 LEFT JOIN，我们把它改造成支持 FULL JOIN 的打印

MySQL 优化器源码入门内核实现 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、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.1unit1.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 | select1select2select3 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.2

可以看到最顶的 RelationalExpression
有 RelationalExpression::FULL_OUTER_JOIN
。

上面这张图我自己都看不清楚，这知乎的图像太差了，我重新个高清的图形链接，需要读者辛苦点开查看：

RelationalExpression::FULL_OUTER_JOIN

完成对 JoinHypergraph 的构建后，会执行 EnumerateAllConnectedPartitions
对超图所有可能 JOIN ORDER 进行枚举，枚举最佳路径过程中需要计算每个 JOIN 谓词的输出行数。需要在 `sql/join_optimizer/cost_model.h` 的 FindOutputRowsForJoin
中添加对 FULL JOIN 的支持。它的模型计算方式是: RelationalExpression::LEFT_JOIN + RelationalExpression::ANTIJOIN
。其实有更好的计算模型，但这个模型比较容易实现，咱们先按这个办法来实现。

MySQL 优化器源码入门内核实现 FULL JOIN 功能-每日运维

寻找到最佳 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 支持：

MySQL 优化器源码入门内核实现 FULL JOIN 功能-每日运维

我们在 CreateIteratorFromAccessPath 函数末尾断点，查看生成的迭代器结构，可以看到最顶是 HashJoinIterator，它的左右两边都是 TableScanIterator：

MySQL 优化器源码入门内核实现 FULL JOIN 功能-每日运维

知乎不支持高清大图，我发个大图形链接，辛苦读者打开查看

HashJoinIterator 全景图

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` 的地方，都有两个分支，比如：

MySQL 优化器源码入门内核实现 FULL JOIN 功能-每日运维

在 HashJoinIterator::ReadRowFromProbeIterator
函数中添加对 LEFT JOIN 的处理完成后，进行 full_to_anti 的切换，进入 ANTI JOIN 流程：

MySQL 优化器源码入门内核实现 FULL JOIN 功能-每日运维

至此，所有的代码改造工作完成。

四、测试 FULL JOIN 结果

MySQL 优化器源码入门内核实现 FULL JOIN 功能-每日运维

五、感悟

我小时候玩过一款当时很火的单机游戏叫《英雄无敌3》，里面有张超级经典的图叫《归隐田园》，当时不会上网看攻略，也没人交流怎么玩，全靠自己摸索。第一次玩这图时，全程被几十倍军力的敌人追杀着满地图逃跑，经过多次的尝试，最后不小心发现了电脑AI的弱点，以弱胜强侥幸战胜敌人，然后觉得自己在这游戏上是个绝顶高手！

直到有一天我进去百度的《英雄无敌》贴吧，发现《归隐田园》只是判断一个玩家水平是否小学毕业及格的标准，当时觉得不可能，后来查看几个攻略，发现别人都玩出了各种新花样吊打电脑，最夸张的是有人修改地图，7天完成通关。当时我都傻了眼，发现在这个圈子里自己简直是个大菜鸟。

回头看看这几年国产数据库的发展，都已经完成了各种新花样，高峰期全国大概300多个数据库创业团队，很可能每个团队都在搞内核开发，厉害的厂商在内核上玩出各种新花样，比如分布式、HTAP架构、各种不同存储引擎支持、各种打破世界TPCC记录、支持信创、上银行核心生产系统、服务海外。

这些让我感觉自己始终像个菜鸟，相对那些内核高手，可能我连入门都算不上，所以我起了个叫《MySQL 优化器源码入门》的标题。本来想在讲解过程中多增加优化器工作细节原理分享，但知乎对高清大图支持不好了。

如果继续搞这个内核研究的话，要走的路很长很长~~~

欢迎关注公众号：DBA札记，一起交流数据库技术。欢迎觉得读完本文有收获，可以转发给其他朋友，大家一起学习进步！谢谢大家。

MySQL 优化器源码入门内核实现 FULL JOIN 功能

一、前言

二、环境、知识准备

三、Server 执行流程探索

3.1 语法规则修改

3.2 探索语法层次结构

3.5 对 HashJoinIterator 改造的经历、思考、决策

四、测试 FULL JOIN 结果

怎么在服务上创建mysql服务

怎么看mysql用户密码

PostgreSQL 与 MySQL 相比，优势何在？

用批处理实现自动备份和清理mysql数据库的代码

在Oracle中使用DDL触发器来限制DDL操作