mysqljoin算法_【MySQL】之join算法详解

在阿里巴巴的java开发手册有这么一条强制规定&＃xff1a;超过三个表禁止join&＃xff0c;须要join的字段&＃xff0c;数据类型保持绝对一致&＃xff0c;多表关联查询时&＃xff0c;要保证被关联的字段须要有索引。

为何尽可能避免使用join&＃xff1f;若是使用join&＃xff0c;咱们应该怎么用呢&＃xff1f;接下来咱们就一块儿聊一聊关于join的几种算法。

Simple Nested-Loop Joinjava

Simple Nested-Loop Join算法是指读取驱动表t1中的每行数据&＃xff0c;将每行数据传递到被驱动表t2上&＃xff0c;取出被驱动表t2中知足条件的行,和t1组成结果集。算法

在这个算法中&＃xff0c;须要对t1进行全表扫描&＃xff0c;假设t1表1000行数据&＃xff0c;那么须要对t2表进行1000次全表扫描&＃xff0c;假设t2表也是1000行数据&＃xff0c;那么就须要扫描1000 X 1000&＃61;1000000行。sql

示例图以下&＃xff1a;当t1表5行数据&＃xff0c;t2表5行数据时&＃xff0c;须要扫描25行数据。数据库

Index Nested-Loop Joinapache

index nested-loop join算法的优化思路是经过驱动表的匹配条件&＃xff0c;直接与被驱动表的索引进行匹配&＃xff0c;减小了被驱动表的扫描次数。缓存

该算法一样要对驱动表t1进行全表扫描&＃xff0c;可是咱们在拿着t1表的数据去被驱动表t2进行匹配时能够利用t2表的索引&＃xff0c;若是t1表中1000行数据&＃xff0c;t2表中1000行数据&＃xff0c;那么一共就须要扫描1000&＃43;1000&＃61;2000行数据。这个过程就跟咱们写程序时的嵌套查询相似&＃xff0c;而且能够用上被驱动表的索引&＃xff0c;因此称之为“Index Nested-Loop Join”&＃xff0c;简称 NLJ。微信

示例以下&＃xff1a;当t1表有5行数据&＃xff0c;t2表有5行数据时&＃xff0c;一共须要扫描5&＃43;5&＃61;10行数据。数据结构

Block Nested-Loop Joinoop

Block Nested-Loop join&＃xff0c;基于块的嵌套循环&＃xff0c;简称BNL算法&＃xff0c;其优化思路主要是减小被驱动表的循坏次数&＃xff0c;它会将驱动表的数据缓存起来&＃xff0c;把参与查询的列缓存到join buffer里&＃xff0c;而后拿join buffer里的数据批量与内层表的数据在join buffer中进行匹配&＃xff0c;知足join条件的&＃xff0c;做为结果集的一部分返回。

能够看到该算法对两个表都进行了全表扫描&＃xff0c;所以扫描的行数是两个表的行数之和。这种场景下&＃xff0c;虽然在扫描行数上和NLJ算法同样&＃xff0c;可是因为BNL算法是在内存中进行判断&＃xff0c;速度上会快不少。

join buffer的大小是由参数join_buffer_size设定&＃xff0c;默认256k。若是一次放不下驱动表的全部数据&＃xff0c;会分段放&＃xff0c;这种状况下会致使被驱动表扫描屡次。若是被驱动表是冷数据表&＃xff0c;而且屡次扫描读取被驱动表间隔超过1S的话&＃xff0c;就会将他放入LRU链表的young区域&＃xff0c;致使业务数据没法进入热数据区&＃xff0c;减小了bufferpool的命中率&＃xff0c;这又是另一个课题了&＃xff0c;暂不过多展开。咱们能够经过调大join_buffer_size来提升缓存的数据量&＃xff0c;减小对被驱动表的扫描次数。

启用BNL算法须要在optimizer_switch参数中设置block_nested_loop&＃61;on。

Batched Key Access性能

BNL算法提高了join的性能&＃xff0c;可是它在经过辅助索引链接后须要回表&＃xff0c;就会消耗大量的随机I/O&＃xff0c;咱们知道随机IO对MySQL的影响是很是大的。所以MySQL5.6引入了Batched Key Access(BKA&＃xff0c;批量键访问联接)算法。

再说BKA算法时不得不提的就是MySQL的Multi-Range Read 优化&＃xff0c;MRR的目的主要是减小磁盘的随机访问。咱们都知道&＃xff0c;Innodb索引采用的是B&＃43;tree的数据结构&＃xff0c;数据保存在主键索引中&＃xff0c;而且是按照主键递增的顺序插入的&＃xff0c;可是二级索引的排列顺序和主键的排列顺序通常是不同的&＃xff0c;它保存的主键值也并不是按照主键顺序排列&＃xff0c;在回表时就会出现随机访问主键索引的状况。因此若是能够按照主键递增顺序查询的话&＃xff0c;对磁盘的读比较接近顺序读&＃xff0c;这样就可以提高读性能。

MRR优化的思路就是在进行范围查询时&＃xff0c;在获得主键值以后&＃xff0c;先按照主键的顺序进行排序&＃xff0c;而后拿着排好序的主键ID再去主键索引进行查询&＃xff0c;这样就能体现出顺序性的优点了。由于是多值查询&＃xff0c;因此通常用于range、ref类型的查询。

再说会BKA算法&＃xff0c;当被驱动表上有索引能够利用时&＃xff0c;那么就在行提交给被 join 的表以前&＃xff0c;先对两个表的对应列的索引字段进行join&＃xff0c;获得主键值后&＃xff0c;按照主键排好序后&＃xff0c;利用 MRR 技术&＃xff0c;批量访问表取数据&＃xff0c;减小了随机 IO。可是若是被 join 的表没用索引的话&＃xff0c;那就只能使用BNL算法了。

具体算法以下图&＃xff1a;

开启BKA和MRR的方式&＃xff1a;

set optimizer_switch&＃61;&＃39;mrr&＃61;on,mrr_cost_based&＃61;off,batched_key_access&＃61;on&＃39;;

MySQL在8.0版本已经实现了hash join&＃xff0c;这里暂不作介绍。

小结

如何优化join的速度呢&＃xff0c;这里给出以下几点建议&＃xff1a;

尽可能避免使用join。

用小表做为驱动表&＃xff0c;减小外层循环的次数。

多表关联查询时&＃xff0c;要保证被关联的字段要有索引。

适当增大join_buffer_size的值&＃xff0c;缓存的数据越多&＃xff0c;就越能减小被驱动表扫描的次数。

减小没必要要的字段查询。

须要join的字段&＃xff0c;数据类型保持绝对一致。