本文已收录至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 customersINNER JOIN ordersON 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算法。对于不好在索引的状况，能够基于长期表的改良计划，提前过滤出小数据增加索引。

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