Py学习  »  DATABASE

MySQL - Join关联查询优化 --- NLJ及BNL 算法初探

小小工匠 • 3 年前 • 183 次点击  

在这里插入图片描述

Demo Table

CREATE TABLE `t1` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `a` int(11) DEFAULT NULL,
  `b` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `idx_a` (`a`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

create table t2 like t1;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

两个表 t1 和 t2 , 一样的,包括索引信息 a 字段有索引 b字段没有索引。

数据量 t1 ,t2 如下

mysql> select count(1) from t1;
+----------+
| count(1) |
+----------+
|    10000 |
+----------+
1 row in set

mysql> select count(1) from t2;
+----------+
| count(1) |
+----------+
|      100 |
+----------+
1 row in set

mysql> 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

表关联常见有两种算法

嵌套循环连接 Nested-Loop Join(NLJ) 算法 (NLP)

定义

一次一行循环地从第一张表(称为 驱动表 )中读取行,在这行数据中取到关联字段,根据关联字段在另一张表( 被驱动表 )里取出满足条件的行,然后取出两张表的结果合集。


示例

举个例子来说明一下

【关联字段a有索引】

mysql> EXPLAIN select * from t1 inner join t2 on t1.a= t2.a;
+----+-------------+-------+------------+------+---------------+-------+---------+--------------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key   | key_len | ref          | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+-------+---------+--------------+------+----------+-------------+
|  1 | SIMPLE      | t2    | NULL       | ALL  | idx_a         | NULL  | NULL    | NULL         |  100 |      100 | Using where |
|  1 | SIMPLE      | t1    | NULL       | ref  | idx_a         | idx_a | 5       | artisan.t2.a |    1 |      100 | NULL        |
+----+-------------+-------+------------+------+---------------+-------+---------+--------------+------+----------+-------------+
2 rows in set

mysql> 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

从执行计划中可以看出

  • 驱动表是 t2,被驱动表是 t1 。 从执行顺序上来看,先执行的就是驱动表,所以id=1 的是t2 ,如果id相同,从上到下顺序执行。 (id越大,优先级越高越先执行)

  • 使用了 NLJ算法 . 一般 join 语句中,如果执行计划 Extra 中未出现 Using join buffer 则表示使用的 join 算法是 NLJ。


执行过程

mysql> EXPLAIN select * from t1 inner join t2 on t1.a= t2.a;
+----+-------------+-------+------------+------+---------------+-------+---------+--------------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key   | key_len | ref          | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+-------+---------+--------------+------+----------+-------------+
|  1 | SIMPLE      | t2    | NULL       | ALL  | idx_a         | NULL  | NULL    | NULL         |  100 |      100 | Using where |
|  1 | SIMPLE      | t1    | NULL       | ref  | idx_a         | idx_a | 5       | artisan.t2.a |    1 |      100 | NULL        |
+----+-------------+-------+------------+------+---------------+-------+---------+--------------+------+----------+-------------+
2 rows in set

mysql> 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

执行过程如下

  1. 先从t2 驱动表里 取出一条记录(如果有where条件,则按where条件过滤后的结果集中取出一行 )
  2. 拿到t2 结果集中的一条记录中的关联字段 a , 去t1表中查找
  3. 取出 t1 中满足条件的行,跟 t2 中获取到的结果合并,作为结果返回给客户端
  4. 重复上述步骤

我们来算一下这个操作MySQL要读取多少行数据

首先读取 t2 表的所有数据 100条记录 ,然后遍历这每行数据中字段 a 的值,根据 t2 表中 a 的值索引扫描 t1 表中的对应行(扫描100次 t1 表的索引(idx_a ),1次扫描可以认为最终只扫描 t1 表一行完整数据,也就是总共 t1 表也扫描了100行), 因此整个过程扫描了 200 行。 (估算的)

如果被驱动表的关联字段没索引,使用NLJ算法性能会比较低 ,mysql会选择Block Nested-Loop Join算法。


规律

  • 优化器一般会优先选择小表做驱动表。所以使用 inner join 时,排在前面的表并不一定就是驱动表。

  • 当使用left join时,左表是驱动表,右表是被驱动表

  • 当使用right join时,右表时驱动表,左表是被驱动表

  • 当使用join时,mysql会选择数据量比较小的表作为驱动表,大表作为被驱动表。


基于块的嵌套循环连接 Block Nested-Loop Join(BNL)算法

定义

把驱动表的数据读入到 join_buffer 中,然后扫描被驱动表,把被驱动表每一行取出来跟 join_buffer 中的数据做对比。


示例

【关联字段b无索引】

mysql> EXPLAIN select * from t1 inner join t2 on t1.b= t2.b;
+----+-------------+-------+------------+------+---------------+------+---------+------+-------+----------+----------------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows  | filtered | Extra                                              |
+----+-------------+-------+------------+------+---------------+------+---------+------+-------+----------+----------------------------------------------------+
|  1 | SIMPLE      | t2    | NULL       | ALL  | NULL          | NULL | NULL    | NULL |   100 |      100 | NULL                                               |
|  1 | SIMPLE      | t1    | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 10337 |       10 | Using where; Using join buffer (Block Nested Loop) |
+----+-------------+-------+------------+------+---------------+------+---------+------+-------+----------+----------------------------------------------------+
2 rows in set

mysql> 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

在这里插入图片描述

从执行计划中可以看出

  • 驱动表是 t2,被驱动表是 t1 。 从执行顺序上来看,先执行的就是驱动表,所以id=1 的是t2 ,如果id相同,从上到下顺序执行。

  • 使用了 BNL 算法 . Extra 中 的Using join buffer (Block Nested Loop)说明该关联查询


执行过程

  1. 把 t2 的所有数据放入到 join_buffer 中
  2. 把表 t1 中每一行取出来,跟 join_buffer 中的数据做对比
  3. 返回满足 join 条件的数据

我们来算一下这个操作MySQL要读取多少行数据

整个过程对表 t1 和 t2 都做了一次全表扫描,因此扫描的总行数为10000(表 t1 的数据总量) + 100(表 t2 的数据总量) = 10100。

join_buffer 里的数据是无序的,极端情况下对表 t1 中的每一行,都要做 100 次判断,所以内存中的判断次数是 100 * 10000= 100 万次。


join_buffer 放不下怎么办?

我们这个例子里表 t2 才 100 行,要是表 t2 是一个大表,join_buffer 放不下怎么办呢

join_buffer 的大小是由参数 join_buffer_size 设定的,默认值是 256k。

mysql> show variables like '%join_buffer_size%';
+------------------+--------+
| Variable_name    | Value  |
+------------------+--------+
| join_buffer_size | 262144 |
+------------------+--------+
1 row in set

mysql> 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

如果放不下表 t2 的所有数据话,策略很简单,就是 分段放

举个例子

比如 t2 表有1000行记录, join_buffer 一次只能放800行数据,那么执行过程就是先往 join_buffer 里放800行记录,然后从 t1 表里取数据跟 join_buffer 中数据对比得到部分结果,然后清空 join_buffer ,再放入 t2 表剩余200行记录,再次从 t1 表里取数据跟 join_buffer 中数据对比。所以就多扫了一次 t1 表。


被驱动表的关联字段没索引为什么要选择使用 BNL 算法而不使用 Nested-Loop Join 呢?

如果上面第二条sql使用 Nested-Loop Join,那么扫描行数为 100 * 10000 = 100万次,因为没有索引,所以这个100万磁盘扫描。

虽然BNL也是100万,但是是内存中计算 ,肯定要快

所以,用BNL磁盘扫描次数少很多,相比于磁盘扫描,BNL的内存计算会快得多。

因此MySQL对于被驱动表的关联字段没索引的关联查询,一般都会使用 BNL 算法。如果有索引一般选择 NLJ 算法,有索引的情况下 NLJ 算法比 BNL算法性能更高


如何界定大表 小表

不是按照表中的数量来决定大表小表,而是根据参与计算的表的数量来决定大表还是小表。

在决定哪个表做驱动表的时候,应该是两个表按照各自的条件过滤,过滤完成之后,计算参与 join 的各个字段的总数据量,数据量小的那个表,就是“小表”,应该作为驱动表。


关联sql的优化的两个核心点

  • 关联字段加索引,让mysql做join操作时尽量选择NLJ算法
  • 小表驱动大表 ,写多表连接sql时如果明确知道哪张表是小表可以用straight_join写法固定连接驱动方式,省去mysql优化器自己判断的时间.

举个例子

比如 :select * from t2 straight_join t1 on t2.a = t1.a; 代表指定mysql选着 t2 表作为驱动表。

  • straight_join只适用于inner join,并不适用于left join,right join 。 因为left join,right join已经代表指定了表的执行顺序
  • 尽可能让优化器去判断,因为大部分情况下mysql优化器是比人要聪明的。使用straight_join一定要慎重,因为部分情况下人为指定的执行顺序并不一定会比优化引擎好。
Python社区是高质量的Python/Django开发社区
本文地址:http://www.python88.com/topic/72314
 
183 次点击