Hash JOIN时间复杂度为O(N+M)，通过build阶段建哈希表、probe阶段单次扫描实现，避免嵌套循环的O(N×M)重复I/O，适用于大表等值连接且无可用索引场景。

Hash JOIN 的时间复杂度是 O(N + M)，不是 O(N × M)

嵌套循环连接（Nested Loop Join）本质是双重遍历：驱动表每行都要完整扫描一遍被驱动表。如果驱动表有 10 万行、被驱动表有 50 万行，比较次数就是 500 亿次——哪怕每次只是内存比对，CPU 也扛不住。

Hash JOIN 把这个过程拆成两步：build 阶段只扫一次驱动表建哈希表，probe 阶段只扫一次被驱动表做哈希查找。总扫描行数是 N + M，哈希计算和查表平均是 O(1) 操作。

• 前提是连接条件是等值（=），且字段无索引或索引不可用时，优化器才倾向选 Hash JOIN
• 如果被驱动表连接列已有高效索引，MySQL 通常仍会选 Index Nested-Loop Join，因为 B+ 树查找稳定、内存开销小
• 哈希表全在内存里时最快；超限时会写磁盘分桶，性能回落，但依然比反复读磁盘的嵌套循环强

Hash JOIN 减少了重复 I/O，尤其适合大表无索引场景

嵌套循环在无索引时，被驱动表要被反复读取 M 次——每次驱动表换一行，就要把整张表从磁盘（或 buffer pool）再加载一遍。即使有预读，页缓存命中率也极低。

Hash JOIN 只需把驱动表数据一次性读入内存建哈希表，被驱动表只需顺序扫描一次。顺序 I/O + 单次加载，对 SSD 或大 buffer pool 更友好。

• join_buffer_size 默认 256KB，太小会导致哈希表频繁落盘；建议根据驱动表连接字段大小估算后调大
• 若驱动表本身很大（比如千万级），MySQL 可能自动降级为 Hybrid Hash Join，分批 build + probe，避免 OOM
• 注意：EXPLAIN 的 Extra 列出现 Using join buffer (hash join) 才表示真正在用

MySQL 8.0.20+ 已移除 Block Nested-Loop，Hash JOIN 是默认兜底方案

在 8.0.20 之前，MySQL 对无索引 JOIN 会尝试 Block Nested-Loop Join（BNL），靠 join_buffer 缓存一批驱动表行，减少被驱动表扫描次数。但它仍是 O(N × M) 复杂度，只是系数变小。

MySQL8 CRM Schema Design Expert

面向 CRM 系统的 MySQL 8 数据库模式设计。当用户需要为客户关系管理（CRM）系统设计、评审、优化或生成数据库模式时，应使用此项技能。

下载

8.0.20 起，BNL 被彻底移除，所有满足条件的等值 JOIN 都走 Hash JOIN —— 不是“可选”，而是“唯一路径”。这意味着你不再需要手动干预算法选择，但必须清楚它的触发边界。

• 触发条件包括：t1.a = t2.b 这类纯等值条件；连接列上没有可用索引；驱动表估算行数不太离谱（否则可能 fallback）
• 如果加了 STRAIGHT_JOIN 强制表顺序，且驱动表过大，Hash JOIN 可能失败并报错 hash join memory exhausted
• optimizer_switch='hash_join=off' 可临时禁用，但不推荐用于生产——除非你明确知道 INLJ 更优

容易忽略的细节：Hash JOIN 不加速非等值条件，也不绕过统计信息偏差

很多人以为“只要升级到 8.0 就自动变快”，结果发现 WHERE a > b 或 JOIN ... ON t1.id LIKE CONCAT(t2.prefix, '%') 场景下 Hash JOIN 根本不生效——它只认 =、 这类严格等值。

更隐蔽的问题是统计信息不准：如果 ANALYZE TABLE 没更新，优化器可能误判驱动表大小，选错哪张表 build 哈希表。小表被当大表，哈希表塞不下；大表被当小表，probe 阶段缓存失效严重。

• 执行 EXPLAIN FORMAT=JSON 后重点看 hash_join 节点是否出现，以及 table_name 字段确认哪张表是 build 表
• 用 SHOW INDEX FROM tbl 确认连接列是否有索引；有索引却没走，先查 key_len 和 possible_keys 是否为空
• 哈希内存不够时，错误日志里会出现 hash join: insufficient memory，不是 SQL 写错了，是配置或数据量问题