一 背景
在MySQL中我们为了实现业务逻辑会进行多表关联查询.也就是我们常说的各种join.那么我们怎么使用join才会获得好的执行效果呢?
二 Nested-Loop Join 又称SNL
什么是SNL呢?借用官网上的一段伪代码:
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
}
}
}比如:
select a.* from test a join test1 b on a.c=b.c;
其中test表没有索引所以会全表扫描,test1表的c列有索引.所以test1表将会使用索引.那么SNL的执行逻辑是什么样的呢?
对test表的c列进行全表扫描然一个一个的去test1表(test1使用索引)获取对应的值.然后再回表test获取所有记录.然后返回给客户端.
执行计划查看:
"nested_loop": [
{
"table": {
"table_name": "a", --test表
"access_type": "ALL", --可以看到test表进行了全表扫描
"rows_examined_per_scan": 986400,
"rows_produced_per_join": 986400,
"filtered": "100.00",
"cost_info": {
"read_cost": "13741.00",
"eval_cost": "197280.00",
"prefix_cost": "211021.00",
"data_read_per_join": "180M"
},
"used_columns": [
"id",
"k",
"c",
"pad"
]
}
},
{
"table": {
"table_name": "b", --test1表
"access_type": "ref", --使用了非唯一索引的等值查询
"possible_keys": [
"idx_c"
],
"key": "idx_c",
"used_key_parts": [
"c"
],
"key_length": "120",
"ref": [
"increment.a.c"
],
"rows_examined_per_scan": 1,
"rows_produced_per_join": 986400,
"filtered": "100.00",
"using_index": true,
"cost_info": {
"read_cost": "986400.00",
"eval_cost": "197280.00",
"prefix_cost": "1394701.00",
"data_read_per_join": "180M"
},
"used_columns": [
"c"
通过对SNL的实现逻辑及执行计划分析发现:
驱动表test越小.那么执行效率就越高
三 Block Nested-Loop Join 又称BNL
伪代码如下:
for block row in a matching range {
?for each row in b {
??a.x = b.y ，send to client
?}
}语句还是:
select a.* from test a join test1 b on a.c=b.c;
现在不同的是,test表和test1表的相关列都没有索引BNL的实现逻辑:
批量的从test表取数据放入join buffer如果一次性能放到join buffer则全部放入,然后一次性匹配test1中满足条件的c列,然后返回客户端.如果一次性不能把test中的数据全部放入join buffer则循环上边的流程.直到全部全完为止.
执行计划分析
"nested_loop": [
{
"table": {
"table_name": "b", --test1表
"access_type": "ALL", --可以看到是全表扫描
"rows_examined_per_scan": 9680,
"rows_produced_per_join": 9680,
"filtered": "100.00",
"cost_info": {
"read_cost": "161.00",
"eval_cost": "1936.00",
"prefix_cost": "2097.00",
"data_read_per_join": "1M"
},
"used_columns": [
"c" --可以看到只使用了c列和join buffer中的test进行对比
]
}
},
{
"table": {
"table_name": "a", --test表
"access_type": "ALL", --也是全表扫描
"rows_examined_per_scan": 986400,
"rows_produced_per_join": 954835214,
"filtered": "10.00",
"using_join_buffer": "Block Nested Loop", --可以看到使用了BNL
"cost_info": {
"read_cost": "21352.06",
"eval_cost": "190967042.85",
"prefix_cost": "1909693849.06",
"data_read_per_join": "170G"
},
"used_columns": [
"id",
"k",
"c",
"pad"
],
"attached_condition": "(`increment`.`a`.`c` = `increment`.`b`.`c`)"
同样.可以看到驱动表test越小的话.效率就会越高.
注意:从MySQL的8020版本开始.将废弃BNL.因为从MySQL8018版本开始就加入了hash join默认都会使用hash join
同样.我们在此看一下mysql8020版本的hash join的执行计划
"nested_loop": [
{
"table": {
"table_name": "b",
"access_type": "ALL",
"rows_examined_per_scan": 1000,
"rows_produced_per_join": 1000,
"filtered": "100.00",
"cost_info": {
"read_cost": "0.25",
"eval_cost": "100.00",
"prefix_cost": "100.25",
"data_read_per_join": "718K"
},
"used_columns": [
"c"
]
}
},
{
"table": {
"table_name": "a",
"access_type": "ALL",
"rows_examined_per_scan": 9936,
"rows_produced_per_join": 993600,
"filtered": "10.00",
"using_join_buffer": "hash join", --可以看到这里使用了hash join
"cost_info": {
"read_cost": "113.95",
"eval_cost": "99360.00",
"prefix_cost": "993814.20",
"data_read_per_join": "697M"
},
"used_columns": [
"id",
"k",
"c",
"pad"
],
"attached_condition": "(`world`.`a`.`c` = `world`.`b`.`c`)"
同时在上边的BNL和hash join我展示的两个例子中.不知道大家注意到没有.优化器默认选择了表数据量小的表作为了驱动表.上边的BNL展示中的test表是100万的数据,test1是1万的数据.hash join展示使用的test表是1万数据.test1是1千的数据量.
最后.不管哪种算法.都最好使用驱动表结果集小的作为驱动表.优化器也会自己去选择.
三 优化算法MRR(Multi-Range Read Optimization)
在此提到MRR算法是为了下边的BKA算法提供铺垫.大家看看MRR的实现原理就好了.不要单独开启MRR.因为实际压测显示单独开启MRR的效果不理想.
MRR是为了实现什么呢?
实验环境准备:
mysql> desc test1;
+-------+-----------+------+-----+---------+----------------+
| Field | Type | Null | Key | Default | Extra |
+-------+-----------+------+-----+---------+----------------+
| id | int | NO | PRI | NULL | auto_increment |
| k | int | NO | MUL | 0 | |
| c | char(120) | NO | | | |
| pad | char(60) | NO | | | |
+-------+-----------+------+-----+---------+----------------+
4 rows in set (0.00 sec)
mysql> show index from test1;
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| test1 | 0 | PRIMARY | 1 | id | A | 1000 | NULL | NULL | | BTREE | | | YES | NULL |
| test1 | 1 | idx_k | 1 | k | A | 311 | NULL | NULL | | BTREE | | | YES | NULL |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
2 rows in set (0.01 sec)
执行查询
在没有开启MRR的情况下.这条语句的执行逻辑是这样的
也就是说会范围扫描索引之后.会回表进行随机的磁盘读.
接下来我们开启MRR
mysql> set optimizer_switch="mrr_cost_based=off";接下来再执行上边的查询查看执行计划:
在这里我们看到使用到了MRR.那么我们看看使用了MRR之后的执行逻辑是什么样的
在这里我们看到开启MRR之后.索引范围扫描获取到的数据先存储到buffer中进行排序.然后使用主键顺序的回表取数据.减少了随机读的时间浪费.
四 Batched Key Access Joins(BKA)算法
BKA算法可以被inner join和outer join及semi join使用.BKA场景和SNL算法的应用条件差不多.就是test1表对应列有索引.不同的是BKA会使用到MRR算法.同时还会使用到join buffer
开启BKA
mysql> SET optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';环境准备:
执行查询并查看执行计划:
"nested_loop": [
{
"table": {
"table_name": "test",
"access_type": "ALL",
"rows_examined_per_scan": 986400,
"rows_produced_per_join": 986400,
"filtered": "100.00",
"cost_info": {
"read_cost": "13741.00",
"eval_cost": "197280.00",
"prefix_cost": "211021.00",
"data_read_per_join": "180M"
},
"used_columns": [
"id",
"k",
"c",
"pad"
]
}
},
{
"table": {
"table_name": "test1",
"access_type": "ref",
"possible_keys": [
"idx_c"
],
"key": "idx_c",
"used_key_parts": [
"c"
],
"key_length": "120",
"ref": [
"increment.test.c"
],
"rows_examined_per_scan": 1,
"rows_produced_per_join": 986400,
"filtered": "100.00",
"using_join_buffer": "Batched Key Access", --在这里可以看到.使用到了BKA和join buffer
"cost_info": {
"read_cost": "986400.00",
"eval_cost": "197280.00",
"prefix_cost": "1394701.00",
"data_read_per_join": "180M"
},
"used_columns": [
"id",
"k",
"c",
"pad"
那么BKA的执行逻辑是什么样的呢?
在这里我们可以和前边的SNL的图对比发现.BKA先从test表取出数据和test1中的的c列对比取出并集.然后在join buffer中排序.再一次性去test中顺序取出数据.这里使用到了MRR的排序算法.
五 总结
本篇文章主要介绍了MySQL中的join算法.