算法|为什么不让用join？《死磕MySQL系列十六》( 二 ) 飞利浦·斯塔克|死磕mysql系列

CREATE PROCEDURE idata () BEGIN DECLARE i INT; SET i=1; WHILE (i<=1000) DO INSERT INTO article VALUES (ii); SET i=i+1; END WHILE; END;

call idata();

CREATE TABLE `article_comment` (`id` INT (11) NOT NULL AUTO_INCREMENT COMMENT 'ID'`article_id` INT (11) NOT NULL COMMENT '文章ID'`user_id` INT (11) NOT NULL COMMENT '用户ID'PRIMARY KEY (`id`)INDEX `idx_article_id` (`article_id`)) ENGINE=INNODB CHARSET=utf8mb4 COLLATE utf8mb4_german2_ci COMMENT='用户评论表';

DROP PROCEDURE idata;

CREATE PROCEDURE idata () BEGIN DECLARE i INT;
SET i=1; WHILE (i<=1000)
DO
INSERT INTO article_comment VALUES (iii);
SET i=i+1; END WHILE; END;

CALL idata ();

可以看到，此时article表和article_comment ，数据都是1000行
需求是查看文章的所有评论信息，执行SQL如下
SELECT*FROM article STRAIGHT_JOIN article_comment ON article.id=article_comment.article_id;
现在，我们来看一下这条语句的explain结果。

死磕MySQL系列

可以看到，在这条语句中，被驱动表article_comment的字段article_id使用了索引，因此这个语句的执行流程是这样的

从article表读取一行数据R
从R中去除id字段到表article_comment去查找
取出article_comment中满足条件的行，跟R组成一行
重复前三个步骤，直到表article满足条件的数据扫描结束

在这个流程中我们简单的梳理一下扫描行数

对article表需要做全表扫描，扫描行数为1000
没行R数据，根据article表的id去表article_comment查找，走的是树搜索，因此每次的搜索的结果都是一一对应的，也就是说每次只会扫描到一行数据，共需要扫描1000
所以，这个执行流程，总扫描行数为2000行

若在代码中如何实现

全表扫描article数据，这里是1000行
循环这1000行数据
使用article的id作为条件，在循环中进行查询

执行过程扫描行数也是2000行，先不涉及这样写性能如何，光与MySQL进交互就进行了1001次。
结论
显然这么做还不如直接使用join好
三、Simple Nested-Loop Join简单嵌套循环连接查询是表连接使用不上索引，然后就粗暴的使用嵌套循环， article、article_comment表都有1000行数据，那么扫描数据的行数就是1000*1000=1千万，这种查询效率可想而知是怎么样的。
执行SQL如下

SELECT * FROM article STRAIGHT_JOIN article_comment ON article.author_id=author_id.user_id;

在这个流程里：

对驱动表article做了全表扫描，这个过程需要扫描1000行
从驱动表每读取一行数据都需要在article_comment表中进行全表扫描，没有使用索引就需要全表扫描
因此，每次都需要全表扫描被驱动表的数据

这还是两个非常小的表，在生产环境的表动辄就是上千万，如果使用这种算法估计MySQL就没有现在的盛况
当然了， MySQL也没有使用这种算法，而是用了分块嵌套查询的算法，这种思想在MySQL中很多地方都在使用
扩展
例如，索引是存储在磁盘中的，每次使用索引进行检索数据时会把数据从磁盘读入内存中，读取的方式也是分块读取，并不是一次读取完。
假设现在操作系统需在磁盘中读取1kb的数据，实际上会操作系统读取到4kb的数据，在操作系统中一页的数据是4kb ，在innodb存储引擎中默认一页的数据是16kb 。
为什么MySQL会采用分块来读取数据，是因为数据的局部性原理，数据和程序都有聚集成群的倾向，在访问到一行数据后，在之后有极大的可能性会再次访问这条数据和这条数据相邻的数据。
四、Block Nested-Loop Join使用简单嵌套查询的方式经过上文的分析肯定是不可取的，而是选择了分块的思想进行处理。

算法|为什么不让用join？《死磕MySQL系列 十六》( 二 )

算法|为什么不让用join？《死磕MySQL系列十六》( 二 )