石狮网站定制,网站模版修改,信息服务类网站建设方案,网站定位 怎么做MySQL的JOIN原理是基于索引和算法的。在执行JOIN查询时#xff0c;MySQL会根据连接字段上的索引来查找匹配的记录。 这种算法在链接查询的时候#xff0c;驱动表会根据关联字段的索引进行查找#xff0c;当在索引上找到了符合的值#xff0c;再回表进行查询#xff0c;也就…MySQL的JOIN原理是基于索引和算法的。在执行JOIN查询时MySQL会根据连接字段上的索引来查找匹配的记录。 这种算法在链接查询的时候驱动表会根据关联字段的索引进行查找当在索引上找到了符合的值再回表进行查询也就是只有当匹配到索引以后才会进行回表。
在进行JOIN查询时MySQL还采用了一些优化策略来提高查询性能例如使用嵌套循环连接算法Nested-Loop Join和索引优化技术。 嵌套循环连接算法按照指定的连接方式执行查询不会自己选择驱动表。当连接字段上有索引时MySQL会使用索引来加速查找过程 Join 算法 使用 left join 时左边的表不一定是驱动表优化器可能会将语句优化为join。如果需要 left join 的语义就不能把被驱动表的字段放在 where 条件里面做等值判断或不等值判断必须都写在 on 里面 为了便于量化分析各种Join 算法以下创建两个表 t1 和 t2 来说明
CREATE TABLE t2 (id int(11) NOT NULL,a int(11) DEFAULT NULL,b int(11) DEFAULT NULL,PRIMARY KEY (id),KEY a (a)
) ENGINEInnoDB;drop procedure idata;
delimiter ;;
create procedure idata()
begindeclare i int;set i1;while(i1000)doinsert into t2 values(i, i, i);set ii1;end while;
end;;
delimiter ;
call idata();create table t1 like t2;
insert into t1 (select * from t2 where id100)可以看到这两个表都有一个主键索引 id 和一个索引 a字段 b 上无索引。存储过程 idata() 往表 t2 里插入了 1000 行数据在表 t1 里插入的是 100 行数据
Index Nested-Loop Join
select * from t1 straight_join t2 on (t1.at2.a);为了便于分析执行过程中的性能问题我改用straight_join让 MySQL 使用固定的连接方式执行查询这样优化器只会按照我们指定的方式去 join。在这个语句里t1 是驱动表t2 是被驱动表 如果直接使用 join 语句MySQL 优化器可能会选择表 t1 或 t2 作为驱动表这样会影响我们分析 SQL 语句的执行过程 INL算法步骤为先遍历表 t1然后根据从表 t1 中取出的每行数据中的 a 值去表 t2 中查找满足条件的记录。在形式上这个过程就跟我们写程序时的嵌套查询类似并且可以用上被驱动表的索引 查询复杂度
在INL算法程中驱动表是走全表扫描而被驱动表是走树搜索
假设被驱动表的行数是 M。每次在被驱动表查一行数据要先搜索索引 a再搜索主键索引。每次搜索一棵树近似复杂度是以 2 为底的 M 的对数记为 l o g 2 M log_2M log2M所以在被驱动表上查一行的时间复杂度是 2 ∗ l o g 2 M 2 * log_2M 2∗log2M。
假设驱动表的行数是 N执行过程就要扫描驱动表 N 行然后对于每一行到被驱动表上匹配一次。
因此整个执行过程近似复杂度是 N N ∗ 2 ∗ l o g 2 M N N* 2*log_2M NN∗2∗log2M
Simple Nested-Loop Join
select * from t1 straight_join t2 on (t1.at2.b);若把SQL 语句改成这样由于表 t2 的字段 b 上没有索引因此再用上图的执行流程时每次到 t2 去匹配的时候就要做一次全表扫描。复杂度是 M * N。这个 SQL 请求就要扫描表 t2 多达 100 次总共扫描 100*100010 万行 MySQL 没有使用 Simple Nested-Loop Join 算法而是使用了另一个叫作“Block Nested-Loop Join”的算法简称 BNL Block Nested-Loop Join join_buffer是一个用于存储连接操作join中临时数据的缓冲区。当执行连接操作时MySQL将从连接的表中读取数据并临时存储在join_buffer中以便执行连接操作的计算和比较 当被驱动表上没有可用的索引算法的流程是这样的
把表 t1 的数据读入线程内存 join_buffer 中由于我们这个语句中写的是select *因此是把整个表 t1 放入了内存扫描表 t2把表 t2 中的每一行取出来跟 join_buffer 中的数据做对比满足 JOIN 条件的作为结果集的一部分返回 可以看到在这个过程中对表 t1 和 t2 都做了一次全表扫描因此总的扫描行数是 1100。由于 join_buffer 是以无序数组的方式组织的因此对表 t2 中的每一行都要做 100 次判断总共需要在内存中做的判断次数是100*100010 万次
join_buffer 的大小是由参数 join_buffer_size 设定的默认值是 256k。 如果放不下表 t1 的所有数据话策略很简单就是分块放 假设驱动表的数据行数是 N需要分 K 段才能完成算法流程被驱动表的数据行数是 M。
注意这里的 K 不是常数N 越大 K 就会越大因此把 K 表示为λ*N显然λ的取值范围是 (0,1)。
所以在这个算法的执行过程中
扫描行数是 NλNM内存判断 N*M 次
SNL与BNL对比
SNL/BNL 算法对系统的影响主要包括三个方面
可能会多次扫描被驱动表占用磁盘 IO 资源判断 join 条件需要执行 M*N 次对比M、N 分别是两张表的行数如果是大表就会占用非常多的 CPU 资源可能会导致 Buffer Pool 的热数据被淘汰影响内存命中率
大表 join 操作虽然对 IO 有影响但是在语句执行结束后对 IO 的影响也就结束了。但是对 Buffer Pool 的影响就是持续性的需要依靠后续的查询请求慢慢恢复内存命中率。
为了减少这种影响可以考虑增大join_buffer_size的值减少对被驱动表的扫描次数
BNL 算法的执行逻辑是将驱动表的数据全部读入内存 join_buffer 中然后将连接操作划分为多个块每个块包含一定数量的记录。每一行数据都跟 join_buffer 中的数据进行匹配匹配成功则作为结果集的一部分返回。 SNL 算法的执行逻辑是顺序取出驱动表中的每一行数据到被驱动表去做全表扫描匹配匹配成功则作为结果集的一部分返回 BNL算法在处理连接操作时采用了块状处理和索引优化技术(转为BKA)使得它在处理大规模数据时能够比SNL算法更快地完成查询操作 Batched Key Access
理解了 MRR 性能提升的原理我们就能理解 MySQL 在 5.6 版本后开始引入的 Batched KEY Access(BKA) 算法了。这个 BKA 算法其实就是对 NLJ 算法的优化
join_buffer 在 BNL 算法里的作用是暂存驱动表的数据。在 NLJ 算法复用 join_buffer 就优化为BKA 算法了 图中在 join_buffer 中放入的数据是 R1~R100表示的是只会取查询需要的字段。当然如果 JOIN buffer 放不下 R1~R100 的所有数据就会把这 100 行数据分成多段执行上图的流程
使用 BKA 优化算法需要在执行 SQL 语句之前先设置
set optimizer_switchmrron,mrr_cost_basedoff,batched_key_accesson;其中前两个参数的作用是要启用 MRR。这么做的原因是BKA 算法的优化要依赖于 MRR
Join 优化
Multi-Range Read 优化
Multi-Range Read优化的目的就是为了减少磁盘的随机访问并且将随机访问转化为较为顺序的数据访问这对于IO-bound类型的SQL查询语句可带来性能极大的提升。Multi-Range Read优化可适用于rangerefeq_ref类型的查询 MRR优化的优点及工作方式详见 MRR优化 如果随着 a 的值递增顺序查询的话id 的值就变成随机的那么就会出现随机访问性能相对较差。而通过MRR优化后会将满足条件的记录id值放入read_rnd_buffer中再讲id进行递增排序后依次查记录并返回结果。执行流程如下图所示 因为大多数的数据都是按照主键递增顺序插入得到的所以我们可以认为如果按照主键的递增顺序查询的话对磁盘的读比较接近顺序读能够提升读性能 BNL 转 BKA
select * from t1 join t2 on (t1.bt2.b) where t2.b1 and t2.b2000;对于表 t2 的每一行判断 JOIN 是否满足的时候都需要遍历 join_buffer 中的所有行。因此判断等值条件的次数是 1000*100 万 10 亿次这个判断的工作量很大
对于这种不适合在被驱动表上建索引的情况可以考虑使用临时表
大致思路是
把表 t2 中满足条件的数据放在临时表 tmp_t 中为了让 JOIN 使用 BKA 算法给临时表 tmp_t 的字段 b 加上索引让表 t1 和 tmp_t 做 JOIN 操作
create temporary table temp_t(id int primary key, a int, b int, index(b))engineinnodb;
insert into temp_t select * from t2 where b1 and b2000;
select * from t1 join temp_t on (t1.btemp_t.b);总体来看不论是在原表上加索引还是用有索引的临时表我们的思路都是让 JOIN 语句能够用上被驱动表上的索引来触发 BKA 算法提升查询性能
Hash join 业务多次查询再到hash结构的数据表中寻找匹配的数据 对于上面计算 10 亿次那个操作看上去有点儿傻。如果 join_buffer 里面维护的不是一个无序数组而是一个哈希表的话那么就不是 10 亿次判断而是 100 万次 HASH 查找
然而 MySQL 的优化器和执行器一直被诟病的一个原因不支持哈希 join。所以将两个表的数据分别查询在业务中组合匹配的效率其实更高
流程大致如下
select * from t1;取得表 t1 的全部 1000 行数据在业务端存入一个 HASH 结构比如 C 里的 set、PHP 的数组这样的数据结构。select * from t2 where b1 and b2000; 获取表 t2 中满足条件的 2000 行数据。把这 2000 行数据一行一行地取到业务端到 HASH 结构的数据表中寻找匹配的数据。满足匹配的条件的这行数据就作为结果集的一行。
总结
.两个表按照各自的条件过滤过滤完成之后计算参与 join 的各个字段的总数据量数据量小的那个表就是“小表”应该作为驱动表如果可以使用被驱动表的索引join 语句还是有其优势的BKA 优化是 MySQL 已经内置支持的建议默认使用BNL 算法效率低建议你都尽量转成 BKA 算法。优化的方向就是给被驱动表的关联字段加上索引基于临时表的改进方案对于能够提前过滤出小数据的 join 语句来说效果还是很好的MySQL 目前的版本还不支持 hash join但你可以配合应用端自己模拟出来理论上效果要好于临时表的方案 参考资料
MySQL 四十五讲——到底可不可以使用joinMySQL 四十五讲——join语句怎么优化MySQL 四十五讲——join的写法MRR优化
