乐趣区

关于mysql:MySQL中的Join-的算法NLJBNLBKA

jiezi

本文已收录至 Github，举荐浏览 👉 Java 随想录
微信公众号：Java 随想录

摘要

Join 是 MySQL 中最常见的查问操作之一，用于从多个表中获取数据并将它们组合在一起。Join 算法通常应用两种根本办法：Index Nested-Loop Join（NLJ）和 Block Nested-Loop Join（BNL）。本文将探讨这两种算法的工作原理，以及如何在 MySQL 中应用它们。

什么是 Join

在 MySQL 中，Join 是一种用于组合两个或多个表中数据的查问操作。Join 操作通常基于两个表中的某些独特的列进行，这些列在两个表中都存在。MySQL 反对多种类型的 Join 操作，如 Inner Join、Left Join、Right Join、Full Join 等。

Inner Join 是最常见的 Join 类型之一。在 Inner Join 操作中，只有在两个表中都存在的行才会被返回。例如，如果咱们有一个“customers”表和一个“orders”表，咱们能够通过在这两个表中共享“customer_id”列来组合它们的数据。

SELECT *
FROM customers
INNER JOIN orders
ON customers.customer_id = orders.customer_id;

下面的查问将返回所有存在于“customers”和“orders”表中的“customer_id”列雷同的行。

Index Nested-Loop Join

Index Nested-Loop Join（NLJ）算法是 Join 算法中最根本的算法之一。在 NLJ 算法中，MySQL 首先抉择一个表（通常是小型表）作为驱动表，并迭代该表中的每一行。而后，MySQL 在第二个表中搜寻匹配条件的行，这个搜寻过程通常应用索引来实现。一旦找到匹配的行，MySQL 将这些行组合在一起，并将它们作为后果集返回。

工作流程如图：

例如，上面这个语句：

select * from t1 straight_join t2 on (t1.a=t2.a);

在这个语句里，假如 t1 是驱动表，t2 是被驱动表。咱们来看一下这条语句的 explain 后果。

能够看到，在这条语句里，被驱动表 t2 的字段 a 上有索引，join 过程用上了这个索引，因而这个语句的执行流程是这样的：

  1. 从表 t1 中读入一行数据 R；
  2. 从数据行 R 中，取出 a 字段到表 t2 里去查找；
  3. 取出表 t2 中满足条件的行，跟 R 组成一行，作为后果集的一部分；
  4. 反复执行步骤 1 到 3，直到表 t1 的开端循环完结。

这个过程就跟咱们写程序时的嵌套查问相似，并且能够用上被驱动表的索引，所以咱们称之为“Index Nested-Loop Join”，简称 NLJ。

NLJ 是应用上了索引的状况，如果查问条件没有应用到索引呢？

MySQL 会抉择应用另一个叫作“Block Nested-Loop Join”的算法，简称 BNL。

Block Nested-Loop Join

Block Nested Loop Join（BNL）算法与 NLJ 算法不同的是，BNL 算法应用一个相似于缓存的机制，将表数据分成多个块，而后一一解决这些块，以缩小内存和 CPU 的耗费。

例如，上面这个语句：

select * from t1 straight_join t2 on (t1.a=t2.b);

字段 b 上是没有建设索引的。

这时候，被驱动表上没有可用的索引，算法的流程是这样的：

  1. 把表 t1 的数据读入线程内存 join_buffer 中，因为咱们这个语句中写的是 select *，因而是把整个表 t1 放入了内存；
  2. 扫描表 t2，把表 t2 中的每一行取出来，跟 join_buffer 中的数据做比照，满足 join 条件的，作为后果集的一部分返回。

这条 SQL 语句的 explain 后果如下所示：

能够看到，在这个过程中，对表 t1 和 t2 都做了一次全表扫描，因而总的扫描行数是 1100。因为 join_buffer 是以无序数组的形式组织的，因而对表 t2 中的每一行，都要做 100 次判断，总共须要在内存中做的判断次数是：100*1000=10 万次。

尽管 Block Nested-Loop Join 算法是全表扫描。然而是在内存中进行的判断操作，速度上会快很多。然而性能依然不如 NLJ。

join_buffer 的大小是由参数 join_buffer_size 设定的，默认值是 256k。如果放不下表 t1 的所有数据话，策略很简略，就是分段放。

  1. 程序读取数据行放入 join_buffer 中，直到 join_buffer 满了。
  2. 扫描被驱动表跟 join_buffer 中的数据做比照，满足 join 条件的，作为后果集的一部分返回。
  3. 清空 join_buffer，反复上述步骤。

尽管分成屡次放入 join_buffer，然而判断等值条件的次数还是不变的，仍然是 10 万次。

MRR & BKA

上篇文章里咱们讲到了 MRR（Multi-Range Read）。MySQL 在 5.6 版本后引入了 Batched Key Acess(BKA)算法了。这个 BKA 算法，其实就是对 NLJ 算法的优化，BKA 算法正是基于 MRR。

NLJ 算法执行的逻辑是：从驱动表 t1，一行行地取出 a 的值，再到被驱动表 t2 去做 join。也就是说，对于表 t2 来说，每次都是匹配一个值。这时，MRR 的劣势就用不上了。

咱们能够从表 t1 里一次性地多拿些行进去，，先放到一个长期内存，一起传给表 t2。这个长期内存不是他人，就是 join_buffer。

通过上一篇文章，咱们晓得 join_buffer 在 BNL 算法里的作用，是暂存驱动表的数据。然而在 NLJ 算法里并没有用。那么，咱们刚好就能够复用 join_buffer 到 BKA 算法中。

NLJ 算法优化后的 BKA 算法的流程，如图所示：

图中，我在 join_buffer 中放入的数据是 P1~P100，示意的是只会取查问须要的字段。当然，如果 join buffer 放不下 P1~P100 的所有数据，就会把这 100 行数据分成多段执行上图的流程。

如果要应用 BKA 优化算法的话，你须要在执行 SQL 语句之前，先设置

set optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';

其中，前两个参数的作用是要启用 MRR。这么做的起因是，BKA 算法的优化要依赖于 MRR。

对于 BNL，咱们能够通过建设索引转为 BKA。对于一些列建设索引代价太大，不好建设索引的状况，咱们能够应用长期表去优化。

例如，对于这个语句：

select * from t1 join t2 on (t1.b=t2.b) where t2.b>=1 and t2.b<=2000;

应用长期表的大抵思路是：

  1. 把表 t2 中满足条件的数据放在长期表 tmp_t 中；
  2. 为了让 join 应用 BKA 算法，给长期表 tmp_t 的字段 b 加上索引；
  3. 让表 t1 和 tmp_t 做 join 操作。

这样能够大大减少扫描的行数，晋升性能。

总结

在 MySQL 中，不论 Join 应用的是 NLJ 还是 BNL 总是应该应用小表做驱动表。更精确地说，在决定哪个表做驱动表的时候，应该是两个表依照各自的条件过滤，过滤实现之后，计算参加 join 的各个字段的总数据量，数据量小的那个表，就是“小表”，应该作为驱动表。该当尽量避免应用 BNL 算法，如果确认优化器会应用 BNL 算法，就须要做优化。优化的常见做法是，给被驱动表的 join 字段加上索引，把 BNL 算法转成 BKA 算法。对于不好在索引的状况，能够基于长期表的改良计划，提前过滤出小数据增加索引。

本篇文章就到这里，感激浏览，如果本篇博客有任何谬误和倡议，欢送给我留言斧正。文章继续更新，能够关注公众号第一工夫浏览。

退出移动版