在MySQL中，多表关联一直是其处理不太好的地方。MySQL本身只支持一种表间关联方式，就是嵌套循环（Nested Loop）。如果关联表的规模较大，则执行时间会非常长。在5.5以后的版本中，MySQL通过引入多种算法来优化嵌套执行。下面就介绍其中的一种，BlockNested-Loop。
1.准备工作
(1).创建结构
CREATE TABLE `big_emp` (
`empno` int(4) NOT NULL,
`ename` varchar(30) DEFAULT NULL,
`job` varchar(9) DEFAULT NULL,
`mgr` int(4) DEFAULT NULL,
`hiredate` date DEFAULT NULL,
`sal` int(7) DEFAULT NULL,
`comm` int(7) DEFAULT NULL,
`dname` varchar(13) DEFAULT NULL,
PRIMARY KEY (`empno`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;
CREATE TABLE `big_dept` (
`deptno` int(2) NOT NULL,
`dname` varchar(14) DEFAULT NULL,
`loc` varchar(13) DEFAULT NULL,
PRIMARY KEY (`deptno`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;
(2).构造数据
seq 1000|awk '{print$1",dept"$1",loc"$1}'>big_dept.txt
seq -f%.0f 100000|awk '{print$1",user"$1",job,1,2000-01-01,1,1,dept"int(1000*rand())+1}'>big_emp.txt
LOAD DATA INFILE 'big_dept.txt' INTO TABLE big_dept FIELDS TERMINATED BY',' (deptno,dname,loc);
LOAD DATA INFILE 'big_emp.txt' INTO TABLE big_emp FIELDS TERMINATED BY ','(empno,ename,job,mgr,hiredate,sal,comm,dname);
2.默认情况 - Simple Nested-Loops Join
下面先来看看默认情况，观察一下MySQL是如何处理的。
(1).执行计划
explain select e.empno,e.ename,e.job,e.sal,d.dname from big_emp e,big_deptd where e.dname=d.dname\G;
********** 1. row **********
id: 1
select_type: SIMPLE
table: d
type: ALL
possible_keys: NULL
key: NULL
key_len: NULL
ref: NULL
rows: 1000
Extra: NULL
********** 2. row **********
id: 1
select_type: SIMPLE
table: e
type: ALL
possible_keys: NULL
key: NULL
key_len: NULL
ref: NULL
rows: 99865
Extra: Using where
这就是个简单的嵌套循环。外部表为big_dept，内部表为big_emp。外部表循环的每一条记录，在内部表进行匹配遍历。
(2).执行时长
mysql> select e.empno,e.ename,e.job,e.sal,d.dname from big_empe,big_dept d where e.dname=d.dname\G;
100000 rows in set (41.58 sec)
3. 优化算法 — Block Nested-Loop(块嵌套循环连接算法)
在5.5的环境里，可以使用优化的BNL算法来提高嵌套循环效率。下面看看MySQL是如何执行的。
(1).执行计划
mysql> set optimizer_switch='block_nested_loop=on';
Query OK, 0 rows affected (0.00 sec)
需要先打开一个开关，启用BNL算法。
mysql> explain select e.empno,e.ename,e.job,e.sal,d.dname from big_empe,big_dept d where e.dname=d.dname\G;
********** 1. row **********
id: 1
select_type: SIMPLE
table: d
type: ALL
possible_keys: NULL
key: NULL
key_len: NULL
ref: NULL
rows: 1000
Extra: NULL
********** 2. row **********
id: 1
select_type: SIMPLE
table: e
type: ALL
possible_keys: NULL
key: NULL
key_len: NULL
ref: NULL
rows: 99865
Extra: Using where; Usingjoin buffer (Block Nested Loop)
*在执行的Extra里中提示"Using join buffer"，这就代表了使用了Block Nested LoopedJoin算法。
(2).执行时长
mysql> select e.empno,e.ename,e.job,e.sal,d.dname from big_empe,big_dept d where e.dname=d.dname\G;
100000 rows in set (7.93 sec)
对比上面的41秒，有4倍多的提升。
(3).算法说明
BNL是嵌套循环连接算法的改进算法。在代码中通过JOIN_CACHE_BNL类支持算法的实现。MySQL用此算法支持内连接、外连接、半连接的连接语义，其中外连接和半连接是在V5.6版本中被BNL算法支持的。
Simple Nested-LoopsJoin算法在内层循环时，外部表的每条记录都需要读取内部表一次。在内部表的连接上有索引的情况下，其扫描成本为O(Rn)；若没有索引，则扫描成本为O(Rn*Sn)。如果内部表S有很多记录，则SimpleNested-Loops Join会扫描内部表很多次，执行效率非常差。而Block Nested-Loops Join算法就是针对没有索引的连接情况设置的，其使用JoinBuffer(连接缓冲)来减少内部循环读取表的次数。
举例来说，BlockNested-Loops Join算法先把对Outer Loop表(外部表)每次读取的10行记录(准确的说是10行需要进行连接的列)放入Join Buffer中，然后在InnerLoop表(内部表)中直接匹配这10行数据。因此，对内部表的扫描减少了9/10。对于没有索引的表来说，Block Nested-Loops Join算法可以极大地提高连接的速度。
