hash join时间复杂度为o(m+n)，因其build阶段单次扫描小表建哈希表、probe阶段单次扫描大表哈希匹配，避免nlj的o(m×n)双重遍历与随机io，且不依赖索引、不受隐式转换影响。
Hash Join的时间复杂度是O(M+N)，不是O(M×N)
嵌套循环（Nested Loop Join）本质是双层遍历：对驱动表每行，都完整扫描一次被驱动表。若驱动表有10万行、被驱动表500万行，最坏要执行5×10¹⁰次比较或索引查找——哪怕有索引，也是10万次独立点查，受磁盘寻道和缓存命中率拖累严重。
Hash Join只做两件事：Build阶段读一遍小表建哈希表，Probe阶段读一遍大表做哈希匹配。总I/O接近顺序扫描两次，平均每次匹配耗时O(1)。只要哈希表能装进内存，实际开销就是M+N量级，和数据分布无关。
- 哈希表大小取决于小表的**内存占用体积**（行宽×行数），不单看行数；比如10万行但带
TEXT字段，可能比100万行纯INT还占内存 - MySQL 8.0默认用
join_buffer_size控制哈希内存上限；PostgreSQL靠work_mem；SQL Server看max server memory - 一旦溢出内存，Hash Join会分片写临时文件，变成多轮磁盘I/O，性能断崖下跌——这时NLJ反而更稳
Hash Join不依赖索引，NLJ高度依赖内表索引
当连接字段没有索引，或者存在隐式类型转换（如INT列 vs VARCHAR值）、函数包裹（如UPPER(t1.a) = t2.b）时，Nested Loop Join会退化为全表扫描，每轮循环都扫一遍内表，成本爆炸。
而Hash Join对连接字段只要求等值条件（=），不关心是否有索引，也不怕字段类型不一致（只要能比较相等）。它直接计算哈希值，查表匹配，完全绕过B+树遍历路径。
- 常见错误：给内表加了索引，但NLJ仍慢——大概率是连接字段发生隐式转换，索引失效
- Hash Join在OLAP场景下优势明显：宽表、无序、无索引的大数据集连接，比如日志表关联维表
- 注意：Hash Join不支持
!=、LIKE、范围条件；这些只能走NLJ或Merge Join
执行计划里怎么确认真用了Hash Join？
不能只看语法写了JOIN就以为生效。必须查执行计划输出里的物理算子名：
- MySQL 8.0+：
EXPLAIN ANALYZE中出现Inner hash join和Hash子节点才是实锤；仅写JOIN或USING不保证触发 - PostgreSQL：
EXPLAIN (ANALYZE, BUFFERS)中看到Hash Cond且节点类型为Hash Join，同时Buffers: shared read值不大（说明没大量落盘） - SQL Server：
SET STATISTICS XML ON后看<relop physicalop="Hash Match"></relop>，并悬停算子确认Estimated Row Count≈Actual Row Count - Oracle：
EXPLAIN PLAN中出现HASH JOIN，且Bytes列显示build侧远小于probe侧
如果执行计划里出现Warning: hash join cannot fit in memory或No join predicate，说明哈希失败或ON条件漏写，实际已退化为笛卡尔积。
别盲目调大内存参数，Hash Join的瓶颈常在数据本身
join_buffer_size或work_mem设太大，不仅不会加速，反而可能挤占InnoDB buffer pool或触发OS内存分配失败；设太小则频繁落盘，延迟陡增。真正卡住性能的，往往是小表侧的数据特征：
- 小表含大量NULL值：哈希表仍为其分配槽位，空间浪费，探测效率下降
- 连接字段高重复率（如状态码只有'Y'/'N'）：哈希冲突激增，链表拉长，O(1)退化为O(K)，K为桶内平均行数
- 小表实际体积超预期：比如估算10MB，但因
JSON或BLOB字段膨胀到200MB，直接溢出内存
比起调参，先用SELECT COUNT(*), AVG(LENGTH(col)), COUNT(DISTINCT col) FROM small_table摸清小表真实体积和选择性，比盲目加大join_buffer_size管用得多。
