JOIN

能不能使用 JOIN

驱动表：左表
被驱动表：右表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
CREATE TABLE `t1`
(
    `id` INT(11) NOT NULL,
    `a`  INT(11) DEFAULT NULL,
    `b`  INT(11) DEFAULT NULL,
    PRIMARY KEY (`id`)
) ENGINE=InnoDB;

CREATE TABLE `t2`
(
    `id` INT(11) NOT NULL,
    `a`  INT(11) DEFAULT NULL,
    `b`  INT(11) DEFAULT NULL,
    PRIMARY KEY (`id`),
    KEY `a` (`a`)
) ENGINE=InnoDB;

Index Nested-Loop Join NLJ

1
2
3
SELECT *
FROM t1 straight_join t2  -- straight_join 指定驱动表，从左到右
ON (t1.a=t2.a);
  1. 从表 t1 中读入一行数据 R
  2. 从数据行 R 中，取出 a 字段到表 t2 里去查找；
  3. 取出表 t2 中满足条件的行，跟 R 组成一行，作为结果集的一部分；
  4. 重复执行步骤 1 到 3，直到表 t1 的末尾循环结束。

这个过程是先遍历表 t1，然后根据从表 t1 中取出的每行数据中的 a 值，去表 t2 中查找满足条件的记录。在形式上，这个过程就跟我们写程序时的嵌套查询类似，并且可以用上被驱动表的索引，所以我们称之为“Index Nested-Loop Join”，简称 NLJ。

怎样选择驱动表

在这个 join 语句执行过程中，驱动表是走全表扫描，而被驱动表是走树搜索。
假设被驱动表的行数是 M。每次在被驱动表查一行数据，要先搜索索引 a，再搜索主键索引。每次搜索一棵树近似复杂度是以 2 为底的 M 的对数，记为 log2M，所以在被驱动表上查一行的时间复杂度是 2log2M。
假设驱动表的行数是 N，执行过程就要扫描驱动表 N 行，然后对于每一行，到被驱动表上匹配一次。
因此整个执行过程，近似复杂度是 N + N2*log2M。
显然，N 对扫描行数的影响更大，因此应该让小表来做驱动表。

  1. 使用 join 语句，性能比强行拆成多个单表执行 SQL 语句的性能要好；
  2. 如果使用 join 语句的话，需要让小表做驱动表。

Block Nested-Loop Join BNL

1
2
3
SELECT *
FROM t2 straight_join t1  -- straight_join 指定驱动表，从左到右
ON (t2.a=t1.a);

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

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

因为受到 join_buffer 限制，如果驱动表数据过大，执行过程就变成了：

  1. 扫描表 t1，顺序读取数据行放入 join_buffer 中，放完第 88 行 join_buffer 满了，继续第 2 步；
  2. 扫描表 t2，把 t2 中的每一行取出来，跟 join_buffer 中的数据做对比，满足 join 条件的，作为结果集的一部分返回；
  3. 清空 join_buffer；
  4. 继续扫描表 t1，顺序读取最后的 12 行数据放入 join_buffer 中，继续执行第 2 步。

得出结论：应该让小表当驱动表。

小表是什么？

过滤条件后，数量少的表为小表
举例：
假设 A 表千万条，B 表百万行
在不设置过滤条件直接 JOIN 时，此时 B 表为小表

1
SELECT * FROM B INNER JOIN A ON B.name = A.name;

在设置过滤条件后
1
SELECT * FROM A INNER JOIN B ON A.name = B.name WHERE A.age <= 10;

此时 A 表仅剩 10W 数据，这里的 A 表为小表

小结

通过对 Index Nested-Loop Join 和 Block Nested-Loop Join 两个算法执行过程的分析，我们也得到了文章开头两个问题的答案：

  1. 如果可以使用被驱动表的索引，join 语句还是有其优势的；
  2. 不能使用被驱动表的索引，只能使用 Block Nested-Loop Join 算法，这样的语句就尽量不要使用；
  3. 在使用 join 的时候，应该让小表做驱动表。

对之前的错误反省

在之前没有正确的理解 JOIN 的原理，错误的认为：如果右表数据非常少时，使用 IN 的方法会更快，其实不然，这样会生成临时表，导致占用更多的性能，大家引以为戒