Join查询深度优化 – 不为人知的新方法-一一网

导读

一个用户交友平台，随着用户量的快速增长，会有一些用户提出这样的需求：想知道自己的主页有多少用户访问，男生有多少，女生有多少？进而针对性地在平台上展示自己的特点。这是一个简单的数据统计展示，通常我们可以使用MySQL的联表查询得到相应的结果。

已知我们现在数据库中有两张表：用户主表user和t_user_view用户访客表，这两张表的表结构如下：

user表

CREATE TABLE `user` (
  `id` int(11) NOT NULL,
  `user_id` int(8) DEFAULT NULL COMMENT '用户id',
  `user_name` varchar(29) DEFAULT NULL COMMENT '用户名',
  `user_introduction` varchar(498) DEFAULT NULL COMMENT '用户介绍',
  `sex` tinyint(1) DEFAULT NULL COMMENT '性别',
  `age` int(3) DEFAULT NULL COMMENT '年龄',
  `birthday` date DEFAULT NULL COMMENT '生日',
  PRIMARY KEY (`id`),
  UNIQUE KEY `index_user_id` (`user_id`),
  KEY `index_un_age_sex` (`user_name`,`age`,`sex`),
  KEY `index_age_sex` (`age`,`sex`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
复制代码

t_user_view表

CREATE TABLE `t_user_view` (
  `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT COMMENT '自增id',
  `user_id` bigint(20) DEFAULT NULL COMMENT '用户id',
  `viewed_user_id` bigint(20) DEFAULT NULL COMMENT '被查看用户id',
  `create_time` datetime(3) DEFAULT CURRENT_TIMESTAMP(3),
  `update_time` datetime(3) DEFAULT CURRENT_TIMESTAMP(3) ON UPDATE CURRENT_TIMESTAMP(3),
  PRIMARY KEY (`id`),
  KEY `index_viewed_user_user` (`viewed_user_id`,`user_id`)
) ENGINE=InnoDB AUTO_INCREMENT=7 DEFAULT CHARSET=utf8;
复制代码

其中，user表的数据如下：

t_user_view表的数9据如下：

已知我的用户id为10008，那么，结合上面的表结构和数据，我们就可以通过下面这条SQL得到访问我的女性用户(sex = 0)和男性(sex = 1)用户数：

SELECT u.sex, COUNT(*) FROM user u LEFT JOIN t_user_view tuv ON u.user_id = tuv.user_id WHERE tuv.viewed_user_id = 10008 GROUP BY u.sex
复制代码

执行SQL后，得到访问我的用户性别分布如下：

性别	用户数
女(0)	3
男(1)	2

在上面这条SQL中，我们使用了left join，这时，你可能担心，当我们的user表的数据规模达到千万级时，这样的联表查询是否会很慢，如果很慢，我们有什么办法去优化它呢？

为了回答这个问题，我们就以上面这条SQL为例，先来详细看看MySQL处理left join的过程。

Explain

我们先通过explain命令初步看一下这条SQL的执行过程：

EXPLAIN SELECT u.sex, COUNT(*) FROM user u LEFT JOIN t_user_view tuv ON u.user_id = tuv.user_id WHERE tuv.viewed_user_id = 10008 GROUP BY u.sex
复制代码

得到结果如下：

通过上图，我们发现这条SQL中的驱动表是t_user_view(图中的tuv)，被驱动表是user(图中的u)，其中，t_user_view表使用了索引index_viewed_user_user，user表使用了索引index_user_id，因此，MySQL会使用Index Nested-Loop Join方式执行该SQL。什么是Index Nested-Loop Join？

Index Nested-Loop Join

Index Nested-Loop Join，指的就是MySQL在联表查询时，对关联表使用了索引查询。

那么，以上面这条SQL为例，结合我在《为什么MySQL能够支撑千万数据规模的快速查询？
》中讲解的索引查找过程，我们看下Index Nested-Loop Join执行过程：

根据tuv.viewed_user_id = 10008这个条件，查找t_user_view表的索引树index_viewed_user_user，得到满足条件的第一个叶子节点记录<10008, 10001, 1>
提取记录<10008, 10001, 1>中的10001，组装条件u.user_id = 10001
根据条件u.user_id = 10001，查找user表索引树index_user_id，得到满足条件的记录<10001, 1>
根据记录<10001, 1>中的主键1，查找user表聚簇索引(回表)，得到主键id =1 的记录<1, 10001, ..., 1998-01-02>
从第1步得到的记录<10008, 10001, 1>开始顺序扫描其后继记录，重复2 ~ 4步，最终得到4条记录<4, 10003, Bruce, ..., 2006-03-03, 10008, 10003, 2>、<2, 10002, Nancy, ..., 2008-02-03, 10008, 10002, 3>、…、<5, 10005, Amy, ..., 2008-02-06, 10008, 10005, 5>，加上第4步得到的一条记录，至此，我们就得到了所有满足SQL查询条件的5条记录
依次遍历上面得到的5条记录，取出记录中的sex字段值，将该字段值依次写入内存临时表

(1) 遍历第一条记录<1, 10001, ..., 1998-01-02>，取出记录中的sex字段值

(2) 如果临时表中没有sex 字段值，用sex字段值初始化临时表记录<1, 1>，里面包含两个元素，其中前面的1代表性别，后面的1代表该性别出现的次数

(3) 否则，相应的sex字段值所在临时表记录的第二个元素+1

(4) 重复步骤(1)~(3)
最后，得到内存临时表的记录分别为<1, 2>和<0, 3>
对临时表中的两条记录按sex字段排序，得到最终的结果为<0, 3>和<1, 2>

其中，步骤7 ~ 9，我在《告诉面试官，我能优化groupBy，而且知道得很深！》一文中详细讲解过，其实就是groupBy的执行过程。

但有时候，我们并不能保证表联接语句都可以命中索引，所以，这时候，MySQL不得不采用新的方式执行表联接语句：Block Nested-Loop Join。那么，什么又是Block Nested-Loop Join？

Block Nested-Loop Join

Block Nested-Loop Join，指的是使用一个内存块做表联接查询。我还是以上面这条SQL为例：

SELECT u.sex, COUNT(*) FROM user u LEFT JOIN t_user_view tuv ON u.user_id = tuv.user_id WHERE tuv.viewed_user_id = 10008 GROUP BY u.sex
复制代码

现在，我把user表的索引index_user_id删掉，来说明一下Block Nested-Loop Join的执行过程。

我们先explain一下，得到如下结果：

可以看到user表的extra中显示Using join buffer(Block Nested Loop)，说明这条联表SQL使用了Block Nested-Loop Join方式执行。详细过程如下：

根据tuv.viewed_user_id = 10008这个条件，查找t_user_view表的索引树index_viewed_user_user，得到满足条件的第一个叶子节点记录<10008, 10001, 1>
提取记录<10008, 10001, 1>中的10001，组装条件u.user_id = 10001
根据条件u.user_id = 10001，扫描user表（聚簇索引叶子节点），依次遍历表中所有记录，把满足条件的记录写入join buffer：

(1) 发现第一条记录<1, 10001, Jack, ..., 1998-01-02>满足条件，将记录<1, 10001, Jack, ..., 1998-01-02>写入join buffer，重复步骤3，直到找出所有满足条件u.user_id = 10001的记录，并将它们写入join buffer
从第1步得到的记录<10008, 10001, 1>开始顺序扫描其后继记录，重复2 ~ 3步，最终，join buffer中写入5条记录：<1, 10001, Jack, ..., 1998-01-02>、…、<5, 10005, Amy, ..., 2008-02-06>
依次遍历join buffer中的5条记录，取出记录中的sex字段值，将该字段值依次写入内存临时表

(1) 遍历第一条记录<1, 10001, ..., 1998-01-02>，取出记录中的sex字段值

(2) 如果临时表中没有sex 字段值，用sex字段值初始化临时表记录<1, 1>，里面包含两个元素，其中前面的1代表性别，后面的1代表该性别出现的次数

(3) 否则，相应的sex字段值所在临时表记录的第二个元素+1

(4) 重复步骤(1)~(3)
最后，得到内存临时表的记录分别为<1, 2>和<0, 3>
对临时表中的两条记录按sex字段排序，得到最终的结果为<0, 3>和<1, 2>

讲完Block Nested-Loop Join算法后，我突然在想，上面的过程中，我把user表中满足查询条件的记录全部放进了一个join buffer，那如果一个join buffer放不下这些记录，会发什么情况呢？

还是以上面的SQL为例，我们来看一下语句执行的过程：

根据tuv.viewed_user_id = 10008这个条件，查找t_user_view表的索引树index_viewed_user_user，得到满足条件的第一个叶子节点记录<10008, 10001, 1>
提取记录<10008, 10001, 1>中的10001，组装条件u.user_id = 10001
根据条件u.user_id = 10001，扫描user表（聚簇索引叶子节点），依次遍历表中所有记录，把满足条件的记录写入join buffer：

(1) 发现第一条记录<1, 10001, Jack, ..., 1998-01-02>满足条件，将记录<1, 10001, Jack, ..., 1998-01-02>写入join buffer，重复步骤3，直到找出所有满足条件u.user_id = 10001的记录，并将它们写入join buffer
从第1步得到的记录<10008, 10001, 1>开始顺序扫描其后继记录，重复2 ~ 3步，在写入第3条记录<2, 10002, Nancy, ..., 2008-02-03>后，join buffer满了，此时，MySQL终止后续记录的扫描，进入步骤5
依次遍历join buffer中的3条记录，取出记录中的sex字段值，将该字段值依次写入内存临时表

(1) 遍历第一条记录<1, 10001, ..., 1998-01-02>，取出记录中的sex字段值

(2) 如果临时表中没有sex 字段值，用sex 字段值初始化临时表记录<1, 1>，里面包含两个元素，其中前面的1代表性别，后面的1代表该性别出现的次数

(3) 否则，相应的sex字段值所在临时表记录的第二个元素+1

(4) 重复步骤(1)~(3)
最后，得到内存临时表的记录分别为<1, 2>和<0, 1>
清空join buffer
从记录索引树index_viewed_user_user叶子节点记录<10008, 10002, 3>开始顺序扫描其后继记录，重复步骤4 ~ 6，最终，得到内存临时表中的记录为<1, 2>和<0, 3>
对临时表中的两条记录按sex字段排序，得到最终的结果为<0, 3>和<1, 2>

通过使用一次join buffer和使用两次join buffer的执行过程来看，后者会两次全表扫描user表，前者只会扫描一次，所以，多次扫表的性能更差，我们应该尽量保证join buffer足够大，可以容纳被驱动表的记录，减少扫表的次数。在MySQL中可以通过参数join_buffer_size调整！

参数调整

我们可以在MySQL的配置文件my.cnf中设置join_buffer_size的大小：

join_buffer_size = 2M
复制代码

很多同学看到这里，可能没有更多优化的办法了。现在我们来看一个场景：

假设我们的系统内存总共4G，join_buffer我们配置了2G，此时，我们的联表语句已经写满了2G的join_buffer，而此刻整个内存也写满了，有优先级更高的进程需要分配内存（比如，系统级的进程），这时，为了给优先级更高的进程分配内存，Linux会交换join_buffer的内存到硬盘上，产生IO操作，这势必影响联表查询的性能。

那我们该怎么解决这个问题呢？

缺页异常

还记得我在《MySQL分表时机：100w？300w？500w？都对也都不对！》一文中讲到了Linux系统缺页异常的处理机制吗？我们一起回顾一下这个过程：

处理器生成一个虚拟地址，并把它传送给 MMU
MMU 根据虚拟地址生成 VPN(虚拟页号，因为CPU与内存交互以页为单位)，然后请求内存，获取 PTE 的数据。
内存向 MMU 返回 PTE 的数据
由于判断出 PTE 的有效位是 0，即内存中没有虚拟页号对应的物理页，所以 CPU 将出发一次异常中断，将控制权转移给内核中的缺页异常处理程序。
缺页异常处理程序确定出物理内存中的牺牲页，如果这个页面被修改过了（D 标志位为 1），那么将牺牲页换出到磁盘。
缺页处理程序从磁盘中调入新的页面到内存中，并且更新 PTE
缺页处理程序将控制权返回给原来的进程，再次执行导致缺页的指令。再次执行后，就会产生页命中时的情况了。

在上面的过程中，我们重点关注一下5和6两步，在第5步中我讲到将牺牲页换出到磁盘，这里的换出，在Linux内核中就叫做swap out，在第6步中我讲到从磁盘中调入新的页面到内存中，这里的调入，在Linux内核中就叫做swap in。

因此，结合上面的缺页异常处理过程，我们发现，上面联表查询产生的IO操作其实就是swap out。所以，在这种情况下，我们有必要想办法减少Linux系统进行swap，那么，该如何减少呢？我们就从swap的原理出发，找一找减少的办法。

Linux内核swap的对象是什么？是内存。也就是上面的图中的memory，即物理内存。所以，我们先来看看物理内存在Linux系统中长什么样？

Linux内核将物理内存从逻辑上划分为一个一个page，每个page叫做page frame(页框)。这个页框又被分为两类：page cache和anonymous page(匿名页)。

所以，要看物理内存在Linux系统中的样子，其实就是看看这两类内存。

Page Cache

我们先来看看Page Cache。

page cache：如上图，它是一个tree结构，tree中的每个节点就是一个页框，比如，P1、P2分别表示Page Cache中的两个页框，它们通过mmap方式创建。

分配条件：我在《MySQL分表时机：100w？300w？500w？都对也都不对！》中提到过：申请内存大小大于MMAP_THRESHOLD这个内核参数配置的大小(默认128K)时，Linux使用mmap分配内存。

特点：内存不足时系统立刻回收。

匿名页

我们再来看看匿名页。

匿名页：如上图中的A和B两个页框，它们是离散在物理内存中的，通过brk()方式创建。

分配条件：我在《MySQL分表时机：100w？300w？500w？都对也都不对！》中提到过：申请内存大小小于MMAP_THRESHOLD这个内核参数配置的大小(默认128K)时，Linux使用brk分配内存。

特点：内存不足时，系统先标记待回收，待下次访问时，回收页框。

知道了Linux系统将物理内存分为Page Cache和匿名页，那么，我们开始进入正题：Page Cache和匿名页，两者swap的机制到底是什么样的呢？了解了这个机制，我们就能找到减少swap的办法！

Swap

Page Cache

Swap Out

以MySQL查询使用了join_buffer为例，我们结合上面的缺页异常中的第5步，先来看下Page Cache页swap out的机制。见下图，我们关注红线：

根据MySQL进程对应的task_struct中mm属性，找到进程使用的内存结构mm_struct
假设MySQL进程的join_buffer使用了物理内存页P1，那么，图中的page指的就是P1。缺页异常处理程序根据P1对应的page中的mapping找到address_space
根据address_space中的i_mmap属性，找到vm_area_struct优先级红黑树的根节点vm_area_struct。ps：在Page Cache中vm_area_struct结构组成一个优先级红黑树。
缺页异常处理程序根据第1步得到的mm_struct，到vm_area_struct优先级红黑树寻找vm_mm等于前面mm_struct的vm_area_struct节点，如上图，找到左边的那个vm_area_struct节点
缺页异常处理程序取到第2步中page中的index属性，即得到P1的物理地址index。如上图，page->index为P1对应page中的index
缺页异常处理程序根据第4步得到的vm_area_struct中的vm_file，得到P1对应的映射文件File
缺页异常处理程序根据第4步得到的vm_area_struct中的vm_pgoff，通过page->index - vm_pgoff，得到P1在映射文件File中对应的虚拟地址偏移量
缺页异常处理程序根据第4步得到的vm_area_struct中的vm_start，通过vm_start + 第6步得到的偏移量，得到P1在内存中的虚拟地址
缺页异常处理程序根据第1步中的mm_struct中的pgd，即页全局目录，通过P1的虚拟地址到pgd找对应的pte，即页表项，更新页表项的标记为1，表示需要将该页swap out到磁盘
缺页异常处理程序根据第7步得到的P1虚拟地址偏移量，和第6步得到的映射文件，将P1换出到磁盘的映射文件中

Swap In

同样，以MySQL查询使用了join_buffer为例，结合上面的缺页异常中的第6步，我们再来看下Page Cache页swap in的过程，见下图绿线部分：

根据MySQL进程对应的task_struct中mm属性，找到进程使用的内存结构mm_struct
假设MySQL进程的join_buffer使用了物理内存页P1，那么，图中的page指的就是P1。缺页异常处理程序根据P1对应的page中的mapping找到address_space
根据address_space中的i_mmap属性，找到vm_area_struct优先级红黑树的根节点vm_area_struct。ps：在Page Cache中vm_area_struct结构组成一个优先级红黑树。
缺页异常处理程序根据第1步得到的mm_struct，到vm_area_struct优先级红黑树寻找vm_mm等于前面mm_struct的vm_area_struct节点，如上图，找到左边的那个vm_area_struct节点
缺页异常处理程序取到第2步中page中的index属性，即得到P1的物理地址index。如上图，page->index为P1对应page中的index
缺页异常处理程序根据第4步得到的vm_area_struct中的vm_file，得到P1对应的映射文件File
缺页异常处理程序根据第4步得到的vm_area_struct中的vm_pgoff，通过page->index - vm_pgoff，得到P1在映射文件File中对应的虚拟地址偏移量
缺页异常处理程序根据第4步得到的vm_area_struct中的vm_start，通过vm_start + 第6步得到的偏移量，得到P1在内存中的虚拟地址
缺页异常处理程序根据第1步中的mm_struct中的pgd，即页全局目录，通过P1的虚拟地址到pgd找对应的pte，即页表项，更新页表项的标记为0
缺页异常处理程序根据第7步得到的P1虚拟地址偏移量，和第6步得到的映射文件，将P1从磁盘的映射文件换入到内存中

匿名页

关于匿名页的swap机制，限于篇幅，我在后续的文章中详细分享给大家~

参数优化

在Linux内核中有个参数swappiness，这个参数用来控制内核优先回收(swap out)的页框类型，数字越小，优先回收Page Cache中的页框，反之，优先回收(swap out)匿名区的页框。

因此，针对频繁使用join_buffer和sort_buffer的场景，建议优化方案：

考虑通过brk()分配的内存，在内存不足时不会立即回收，方便后续进程可以直接利用未回收的内存，减少IO，提升性能。所以，参考上面匿名页的介绍：申请内存大小小于MMAP_THRESHOLD这个内核参数配置的大小(默认128K)，Linux使用brk分配内存。建议调大MMAP_THRESHOLD参数，保证联表查询可以更多地使用匿名页。

设置swappiness=0，减少回收匿名页的频率。ps：swappiness=0不是不回收匿名页，只是在内存中只有匿名页占满内存时，触发回收匿名页，只要内存中有page cache页，优先回收page cache页。