联接查询处理
复杂查询
联接查询
Nested Loop Join
MySQL 中主要使用 Nested Loop Join（嵌套循环连接）算法，没有其他很多数据库锁提供的 Hash Join，也没有 Sort Merge Join。Nested Loop Join 实际上就是通过驱动表的结果集，作为循环基础数据，然后逐条通过该结果集中的数据作为过滤条件到下一个表中查询数据，然后合并结果。
驱动表就是在嵌套循环和哈希连接中，用来最先获得数据，并以此表为依据，逐步获得其他表的数据，直至最终查询到所有符合条件的数据的第一个表。驱动表不一定是表，也可以是一个数据集，即由某个表中满足条件的数据行组成的子集合。（同理被驱动表也不一定非得是表，也可以是一个数据集）。驱动表的选择，在指定了联接条件时，满足查询条件的记录行数少的表为驱动表；未指定联接条件时，行数少的表为驱动表。
在 MySQL 中，A left join B on condition 的执行过程如下：
- 以 table_A 为驱动表，检索 table_B；根据 on 条件过滤 table_B 的数据，构建 table_A 结果集，并且添加外部行。
- 对结果集执行 where 条件过滤。如果 A 中有一行匹配 where 子句但是 B 中没有一行匹配 on 条件，则生成另一个 B 行，其中所有列设置为 NULL。
- 依次执行 group by 语句分组，执行 having 语句对分组结果筛选，执行 select 出结果集，执行 distinct 对结果去重，执行 order by 语句，执行 limit 语句。
如果还有第三个参与 Join，则再通过前两个表的 Join 结果集作为循环基础数据，再一次通过循环查询条件到第三个表中查询数据，如此往复。由此可见，MySQL 会先进行连接查询，然后再使用 where 子句查询结果，再从结果执行 order by。所以如果被驱动表数据过大，会造成检索行过多。可以利用子查询先查询出一个较小的结果集，然后再用连接驱动。
一个简单的嵌套循环联接（NLJ）算法，循环从第一个表中依次读取行，取到每行再到联接的下一个表中循环匹配；这个过程会重复多次直到剩余的表都被联接了。假设表 t1、t2、t3 用下面的联接类型进行联接：
Table Join Type
t1 range
t2 ref
t3 ALL
for each row in t1 matching range {
for each row in t2 matching reference key {
for each row in t3 {
if row satisfies join conditions,
send to client
}
}
}
因为 NLJ 算法是通过外循环的行去匹配内循环的行，所以内循环的表会被扫描多次。在联接查询中，往往是将驱动表加载到内存中，而内部表要求有选择性高的索引。整体 NFJ 的代价为 cost = outer access cost + (inner access cost * outer cardinality)。
Block Nested-Loop Join Algorithm
一个块嵌套循环联接（BNL）算法，将外循环的行缓存起来，读取缓存中的行，减少内循环的表被扫描的次数。例如，如果 10 行读入缓冲区并且缓冲区传递给下一个内循环，在内循环读到的每行可以和缓冲区的 10 行做比较。这样使内循环表被扫描的次数减少了一个数量级。
MySQL 使用联接缓冲区时，会遵循下面这些原则：
- join_buffer_size 系统变量的值决定了每个联接缓冲区的大小。
- 联接类型为 ALL、index、range 时（换句话说，联接的过程会扫描索引或数据时），MySQL 会使用联接缓冲区。
- 缓冲区是分配给每一个能被缓冲的联接，所以一个查询可能会使用多个联接缓冲区。
- 联接缓冲区永远不会分配给第一个表，即使该表的查询类型为 ALL 或 index。
- 联接缓冲区联接之前分配，查询完成之后释放。
- 使用到的列才会放到联接缓冲区中，并不是所有的列。
上面的例子使用的是 NLJ 算法（没有使用缓存），使用缓存的联接方式像下面这样：
for each row in t1 matching range {
for each row in t2 matching reference key {
store used columns from t1, t2 in join buffer
if buffer is full {
for each row in t3 {
for each t1, t2 combination in join buffer {
if row satisfies join conditions,
send to client
}
}
empty buffer
}
}
}
if buffer is not empty {
for each row in t3 {
for each t1, t2 combination in join buffer {
if row satisfies join conditions,
send to client
}
}
}
首先将 t1、t2 的联接结果放到缓冲区，直到缓冲区满为止；遍历 t3，内部再循环缓冲区，并找到匹配的行，发送到客户端；清空缓冲区，重复上面步骤，直至缓冲区不满，处理缓冲区中剩余的数据，重复遍历 t3 这一步。假设 S 是每次存储 t1、t2 组合的大小，C 是组合的数量，则 t3 被扫描的次数为：
(S * C)/join_buffer_size + 1
由此可见，随着 join_buffer_size 的增大，t3 被扫描的次数会较少，如果 join_buffer_size 足够大，大到可以容纳所有 t1 和 t2 联接产生的数据，t3 只会被扫描 1 次。
结果排序
在 MySQL 中经常会带上一个 limit ,表示从排序后的结果集中取前 100 条，或者取第 n 条到第 m 条，要实现排序，我们需要先根据查询条件获取结果集，然后在内存中对这个结果集进行排序，如果结果集数量特别大，还需要将结果集写入到多个文件里，然后单独对每个文件里的数据进行排序，然后在文件之间进行归并，排序完成后在进行 limit 操作。
CREATE TABLE `person` (
`id` int(11) NOT NULL,
`city` varchar(16) NOT NULL,
`name` varchar(16) NOT NULL,
`age` int(11) NOT NULL,
`addr` varchar(128) DEFAULT NULL,
PRIMARY KEY (`id`),
KEY `city` (`city`)
) ENGINE=InnoDB;
select city,name,age from person where city='武汉' order by name limit 100 ;
使用 explain 发现该语句会使用 city 索引，并且会有 filesort，我们分析下该语句的执行流程：
- 初始化 sortbuffer，用来存放结果集；
- 找到 city 索引，定位到 city 等于武汉的第一条记录，获取主键索引 ID；
- 根据 ID 去主键索引上找到对应记录，取出 city,name,age 字段放入 sortbuffer；
- 在 city 索引取下一个 city 等于武汉的记录的主键 ID；
- 重复上面的步骤，直到所有 city 等于武汉的记录都放入 sortbuffer；
- 对 sortbuffer 里的数据根据 name 做快速排序；
- 根据排序结果取前面 1000 条返回；
这里是查询 city,name,age 3 个字段，比较少，如果查询的字段较多，则多个列如果都放入 sortbuffer 将占有大量内存空间，另一个方案是只区出待排序的字段和主键放入 sortbuffer 这里是 name 和 id ,排序完成后在根据 id 取出需要查询的字段返回，其实就是时间换取空间的做法，这里通过 max_length_for_sort_data 参数控制，是否采用后面的方案进行排序。
另外如果 sortbuffer 里的条数很多，同样会占有大量的内存空间，可以通过参数 sort_buffer_size 来控制是否需要借助文件进行排序，这里会把 sortbuffer 里的数据放入多个文件里，用归并排序的思路最终输出一个大的文件。
如果 name 字段上有索引，由于索引在构建的时候已经是有序的了，所以就不需要进行额外的排序流程只需要在查询的时候查出指定的条数就可以了，这将大大提升查询速度。我们现在加一个 city 和 name 的联合索引：
alter table person add index city_user(city, name);
这样查询过程如下：
- 根据 city,name 联合索引定位到 city 等于武汉的第一条记录，获取主键索引 ID；
- 根据 ID 去主键索引上找到对应记录，取出 city,name,age 字段作为结果集返回；
- 继续重复以上步骤直到 city 不等于武汉，或者条数大于 1000。
由于联合所以在构建索引的时候，在 city 等于武汉的索引节点中的数据已经是根据 name 进行排序了的，所以这里只需要直接查询就可，另外这里如果加上 city, name, age 的联合索引，则可以用到索引覆盖，不行到主键索引上进行回表。