数据库的JOIN连接查询算法

3.2 Join 算法优化

JOIN算法指的是在执行SQL查询语句中，当涉及到两个或多个表之间的数据连接（JOIN）时，查询优化器用来决定如何最有效地从这些表中检索和组合数据的方法，选择最适合的JOIN算法。

3.1.2 Nested Loop Join（NLJ）

嵌套循环连接（Nested Loop Join）是一种最基本的连接实现算法。它先从外部表（驱动表）中获取满足条件的数据，并对每个行再遍历一次另一个表（内层表）以找到匹配的行。

假设我们有两个表 employees 和 departments，并且我们要找出每个员工所在的部门名称。如果使用 NLJ，MySQL 将会遍历 employees 表中的每一行，并且针对每一行遍历 departments 表中的所有行，直到找到一个与当前员工的部门。

SQL如下：

SELECT e.name, d.name
FROM employees e
JOIN departments d ON e.department_id = d.id;

对于左表中的每一行，遍历右表的所有行寻找匹配的记录。这是一种最基本的连接方式，适用于小规模数据集或当没有合适的索引可用时。

如图所示：

伪代码如下：

-- 先遍历外部表
FOR each row e IN employees
    -- 外部表的每一条数据都会再遍历一遍内部表
    FOR each row d IN departments
        -- 最终寻找合适的数据
        IF e.department_id == d.id THEN
            OUTPUT (e.name, d.name)

3.1.3 Block Nested Loop Join（BNLJ）

Block Nested Loop 是对 NLJ 的一种改进，它利用内存中的缓存块来减少磁盘 I/O 操作。不是每次都读取整个右表（被驱动表），而是每次从右表中加载一部分数据到内存（块），然后用左表（驱动表）的一行去匹配这些块里的所有行。

BNLJ 与 NLJ 类似，但 MySQL 会尝试将尽可能多的 departments 行加载到内存中，然后用 employees 表的每一行去匹配这些已经加载到内存中的 departments 行。

同样是如下SQL：

SELECT e.name, d.name
FROM employees e
JOIN departments d ON e.department_id = d.id;

BNLJ 是 NLJ 的一种优化版本，它试图减少不必要的磁盘 I/O 操作。它的核心思想是分批加载右表的数据到内存中，然后用左表的一行去匹配这些已经加载到内存中的块。具体来说，不是每次都扫描整个右表，而是每次只加载一部分数据（一个或多个块），并且尽可能多地利用内存中的缓存。

如图所示：

伪代码如下：

// 假设有一个游标指向employees表
CURSOR cursor = OPEN CURSOR FOR SELECT * FROM employees;

WHILE cursor has more rows // 当游标还有更多行可处理
    LOAD a block of rows from departments into memory as BLOCK // 加载一部分部门记录到内存中作为BLOCK
    FETCH NEXT ROW FROM cursor INTO e // 获取下一行员工记录e
    WHILE e is not null AND there are still rows in BLOCK to process // 当有未处理的员工记录和部门块
        FOR each row d IN BLOCK // 遍历当前加载到内存的部门记录d
            IF e.department_id == d.id THEN // 如果找到匹配的部门ID
                OUTPUT (e.name, d.name) // 输出匹配的结果
        FETCH NEXT ROW FROM cursor INTO e // 获取下一行员工记录e
CLOSE cursor; // 关闭游标

BNLJ 关键点在于，当 BNLJ 从磁盘加载一批数据到内存后，它可以重复使用这批数据来与左表的多行进行比较，从而减少了频繁访问磁盘的需求。这样做的前提是内存足够大，可以容纳下右表的一个或多个块，以及左表的当前行。

3.1.4 Index Nested Loop Join（INLJ）

当右表有一个可以被有效使用的索引时，MySQL 可以直接通过索引来查找匹配的行，而不需要扫描整个表。这通常比简单的 NLJ 更快，因为它减少了需要访问的行数。

例如：如果我们为 departments 表上的 id 列创建了索引，那么 MySQL 可以直接根据 employees.department_id 查找 departments 表中的相应记录，而不是扫描整个表。

同样是如下SQL：

SELECT e.name, d.name
FROM employees e
JOIN departments d ON e.department_id = d.id;

利用右表上的索引来快速查找匹配的记录。这可以极大地提高性能，尤其是在右表很大而左表相对较小的情况下。

如图所示：

伪代码如下：

CREATE INDEX idx_department ON departments(id); // 假设已经存在这个索引

FOR each row e IN employees // 外层循环遍历左表
    LOOKUP rows FROM departments USING idx_department WHERE id = e.department_id // 使用索引查找
    FOR each matching row d // 遍历匹配的结果
        OUTPUT (e.name, d.name)

3.1.5 Sort Merge Join（SMJ）

在Sort Merge Join中，首先两个表按连接键排序，之后同时遍历这两个有序列表，如果两个元素的连接键相当，则匹配成功。如果不相等则指向较小的连接键值，找到匹配的记录。

例如：如果 employees 和 departments 都是根据 department_id 和 id 排序的，那么 MySQL 可以简单地同时遍历两个表，只比较相等的键值，从而高效地完成 JOIN。

如图所示：

伪代码如下：

SORT employees BY department_id;		// 根据 department_id 字段将 employees 表排序
SORT departments BY id;					// 根据 id 字段将 departments 表排序

// 开始合并两个已排序的列表，基于 e.department_id 和 d.id 的匹配
MERGE SORTED employees AND sorted departments ON e.department_id = d.id
    // 在处理两个排序后的列表时
    WHILE processing both sorted lists
        // 如果当前员工的部门ID等于当前部门的ID
        IF e.department_id == d.id THEN
            // 输出员工的名字和对应部门的名字
            OUTPUT (e.name, d.name)
        // 如果当前员工的部门ID小于当前部门的ID
        ELSE IF e.department_id < d.id THEN
            // 移动到下一个员工记录，因为当前员工所属的部门已经处理完毕或不存在于部门列表中
            ADVANCE TO NEXT e
        // 如果当前员工的部门ID大于当前部门的ID
        ELSE
            // 移动到下一个部门记录，因为当前部门没有对应的员工或者所有相关员工已经被处理
            ADVANCE TO NEXT d

3.1.6 Hash Join

Hash Join 在MySQL 8.0.18版本引入，且不需要索引的支持。Hash Join在查询时首先会在内存中构建一个哈希表，然后用另一个表的数据去探测这个哈希表，检查该表中的每一行是否存在于哈希表中。这种 JOIN 方式非常适合大规模数据集，对于等值连接特别有效，尤其是在内存足够大的情况下。

Hash Join的工作流程：

• 1）**Build Phase (构建阶段)： **
  • 选择较小的表作为构建表（Build Table），并在内存中为该表构建一个哈希表。
  • 对构建表中的每一行计算哈希函数，并将结果插入到这个哈希表中。这个哈希表的键是连接列上的哈希值，而值是指向该行的指针或行本身。
• 2）**Probe Phase (探测阶段)： **
  • 遍历较大的表（Probe Table）中的每一行。
  • 对于每行，使用相同的哈希函数计算连接列的哈希值。
  • 使用这个哈希值在哈希表中查找匹配项。如果找到匹配，则输出这两行组成的连接结果。

Hash Join工作示意图如下：

伪代码如下：

// 构建阶段: 为较小的表创建哈希表(假设部门表较小)
HASH_TABLE ht;
FOR each row d IN departments // 构建表为 departments
    HASH_VALUE hv = HASH(d.id); // 计算哈希值
    INSERT INTO ht WITH key = hv AND value = d; // 将部门记录插入哈希表

// 探测阶段: 扫码较大的表并在哈希表中查询
FOR each row e IN employees // 探测表为 employees
    HASH_VALUE hv = HASH(e.department_id); // 使用相同的哈希函数计算哈希值
    IF ht CONTAINS key = hv THEN // 查找哈希表
        FOR each matching row d IN ht[hv] // 如果有多个匹配（如哈希冲突）
            IF e.department_id == d.id THEN // 确认实际值是否相等
                OUTPUT (e.name, d.name) // 输出匹配的结果

Hash Join 通过构建一个哈希表包含来自一个表的连接列的值，然后扫描另一个表，检查该表中的每一行是否存在于哈希表中。这种 JOIN 方式非常适合大规模数据集和等值连接条件。

默认配置时，MySQL 所有可能的情况下都会使用 hash join。同时提供了两种控制是否使用 hash join 的方法：

• 1）在全局或者会话级别设置服务器系统变量 optimizer_switch 中的 hash_join=on 或者 hash_join=off 选项。默认为 hash_join=on。

-- 查询优化器相关参数
show variables like 'optimizer_switch';

-- 查看hash_join参数,默认为no(开启Hash Join)
hash_join=on

• 2）MySQL 8.0.18 支持使用hint，在语句级别为特定的连接指定优化器提示 HASH_JOIN 或者 NO_HASH_JOIN（在 8.0.19 和之后的版本中，这些参数不再起作）。

explain select SQL_NO_CACHE * from emp e inner join dept d on e.dept_id=d.id

Tips：可以通过系统变量 join_buffer_size 控制 hash join 允许使用的内存数量；hash join 不会使用超过该变量设置的内存数量。如果 hash join 所需的内存超过该阈值，MySQL 将会在磁盘中执行操作。需要注意的是，如果 hash join 无法在内存中完成，并且打开的文件数量超过系统变量 open_files_limit 的值，连接操作可能会失败。