欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-17 20:48:04
...

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

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;

两个表 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> 

表关联常见有两种算法

嵌套循环连接 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> 

从执行计划中可以看出

  • 驱动表是 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. 先从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> 

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

从执行计划中可以看出

  • 驱动表是 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> 

如果放不下表 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一定要慎重,因为部分情况下人为指定的执行顺序并不一定会比优化引擎好。