Join 的实现原理

在MySQL 中，只有一种Join 算法，也就是Nested Loop Join，没有其他很多数据库所提供的Hash Join，也没有Sort Merge Join。顾名思义，Nested Loop Join 实际上就是通过驱动表的结果集作为循环基础数据，然后一条一条的通过该结果集中的数据作为过滤条件到下一个表中查询数据，然后合并结果。如果还有第三个参与Join，则再通过前两个表的Join 结果集作为循环基础数据，再一次通过循环查询条件到第三个表中查询数据，如此往复。

下面我们将通过一个三表Join 语句示例来说明MySQL 的Nested Loop Join 实现方式。

Query 如下：
select m.subject msg_subject, c.content msg_content
from user_group g,group_message m,group_message_content c
where g.user_id = 1
and m.group_id = g.group_id
and c.group_msg_id = m.id

索引情况：

user_group表：user_id

group_message表：group_id

group_message_content表：group_msg_id

然后看看我们的Query 的执行计划：
root@localhost> explain select m.subject msg_subject, c.content
msg_content
-> from user_group g,group_message m,group_message_content c
-> where g.user_id = 1
-> and m.group_id = g.group_id
-> and c.group_msg_id = m.id\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: g
type: ref
possible_keys: user_group_gid_ind,user_group_uid_ind,user_group_gid_uid_ind
key: user_group_uid_ind
key_len: 4
ref: const

rows: 2
Extra:
*************************** 2. row ***************************
id: 1
select_type: SIMPLE
table: m
type: ref
possible_keys: PRIMARY,idx_group_message_gid_uid
key: idx_group_message_gid_uid
key_len: 4
ref: example.g.group_id
rows: 3
Extra:
*************************** 3. row ***************************
id: 1
select_type: SIMPLE
table: c
type: ref
possible_keys: idx_group_message_content_msg_id
key: idx_group_message_content_msg_id
key_len: 4
ref: example.m.id
rows: 2
Extra:

我们可以看出，MySQL Query Optimizer 选择了user_group 作为驱动表，首先利用我们传入的条件user_id 通过该表上面的索引user_group_uid_ind 来进行const 条件的索引ref 查找，然后以user_group 表中过滤出来的结果集的group_id 字段作为查询条件，对group_message 循环查询，然后再通过user_group 和group_message 两个表的结果集中的group_message 的id 作为条件与group_message_content 的group_msg_id 比较进行循环查询，才得到最终的结果。

假设我们去掉group_message_content 表上面的group_msg_id 字段的索引，然后再看看执行计划会变成怎样：
root@localhost> drop index idx_group_message_content_msg_id on
group_message_content;
Query OK, 96 rows affected (0.11 sec)

root@localhost> explain
-> select m.subject msg_subject, c.content msg_content
-> from user_group g,group_message m,group_message_content c
-> where g.user_id = 1
-> and m.group_id = g.group_id
-> and c.group_msg_id = m.id\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: g
type: ref
possible_keys: idx_user_group_uid
key: idx_user_group_uid
key_len: 4
ref: const
rows: 2
Extra:

*************************** 2. row ***************************
id: 1
select_type: SIMPLE
table: m
type: ref
possible_keys: PRIMARY,idx_group_message_gid_uid
key: idx_group_message_gid_uid
key_len: 4
ref: example.g.group_id
rows: 3
Extra:
*************************** 3. row ***************************
id: 1
select_type: SIMPLE
table: c
type: ALL
possible_keys: NULL
key: NULL
key_len: NULL
ref: NULL
rows: 96
Extra: Using where; Using join buffer

我们看到不仅仅user_group 表的访问从ref 变成了ALL，此外，在最后一行的Extra 信息从没有任何内容变成为Using where; Using join buffer，也就是说，对于从ref 变成ALL 很容易理解，没有可以使用的索引的索引了嘛，当然得进行全表扫描了，Using where 也是因为变成全表扫描之后，我们需要取得的content 字段只能通过对表中的数据进行where 过滤才能取得，但是后面出现的Using join buffer 是一个啥呢？
实际上，这里的Join 正是利用到了我们在之前“MySQL Server 性能优化”一章中所提到的一个Cache 参数相关的内容，也就是我们通过join_buffer_size 参数所设置的Join Buffer。
实际上，Join Buffer 只有当我们的Join 类型为ALL（如示例中），index，rang 或者是index_merge 的时候才能够使用，所以，在我们去掉group_message_content 表的group_msg_id 字段的索引之前，由于Join 是ref 类型的，所以我们的执行计划中并没有看到有使用Join Buffer。

Join 语句的优化
在明白了MySQL 中Join 的实现原理之后，我们就比较清楚的知道该如何去优化一个一个Join 语句了。
1. 尽可能减少Join 语句中的Nested Loop 的循环总次数；
如何减少Nested Loop 的循环总次数？最有效的办法只有一个，那就是让驱动表的结果集尽可能的小。
为什么？因为驱动结果集越大，意味着需要循环的次数越多，也就是说在被驱动结果集上面所需要执行的查询检索次数会越多。比如，当两个表（表A 和表B） Join 的时候，如果表A 通过WHERE 条件过滤后有10 条记录，而表B 有20 条记录。如果我们选择表A 作为驱动表，也就是被驱动表的结果集为20，那么我们通过Join 条件对被驱动表（表B）的比较过滤就会有10 次。反之，如果我们选择表B 作为驱动表，则需要有20 次对表A 的比较过滤。当然，此优化的前提条件是通过Join 条件对各个表的每次访问的资源消耗差别不是太大。如果访问存在较大的差别的时候（一般都是因为索引的区别），我们就不能简单的通过结果集的大小来判断需要Join 语句的驱动顺序，而是要通过比较循环次数和每次循环所需要的消耗的乘积的大小来得到如何驱动更优化。

2. 优先优化Nested Loop 的内层循环；
不仅仅是在数据库的Join 中应该做的，实际上在我们优化程序语言的时候也有类似的优化原则。内层循环是循环中执行次数最多的，每次循环节约很小的资源，在整个循环中就能节约很大的资源。
3. 保证Join 语句中被驱动表上Join 条件字段已经被索引；
保证被驱动表上Join 条件字段已经被索引的目的，正是针对上面两点的考虑，只有让被驱动表的Join 条件字段被索引了，才能保证循环中每次查询都能够消耗较少的资源，这也正是优化内层循环的实际优化方法。
4. 当无法保证被驱动表的Join 条件字段被索引且内存资源充足的前提下，不要太吝惜Join
Buffer 的设置：
当在某些特殊的环境中，我们的Join 必须是All，Index，range 或者是index_merge 类型的时候，Join Buffer 就会派上用场了。在这种情况下，Join Buffer 的大小将对整个Join 语句的消耗起到非常关键的作用。