哈希连接

定义

哈希连接(Hash Join)是针对等值连接的高效算法,分两阶段:构建阶段扫描较小的一侧(build side),按连接键建立内存哈希表;探测阶段扫描另一侧(probe side),对每行计算哈希并在表中查找匹配。

复杂度与落盘

理想情况下两侧各扫描一遍,复杂度近似线性,远优于无索引的嵌套循环。当构建侧超出内存时采用 Grace Hash Join:先按哈希把两侧数据分区落盘,再逐分区在内存中完成连接;混合哈希(Hybrid Hash)则尽量保留部分分区在内存中。

适用与限制

哈希连接适合等值连接、无可用索引、数据量大的场景,是数据仓库与分析引擎的主力连接算法;它不保序,且原生形态只支持等值条件。构建侧基数估计错误会导致内存溢出落盘,性能骤降。

支持情况

Oracle、SQL Server、PostgreSQL 长期支持;MySQL 直到 8.0.18 才引入哈希连接并逐步取代块嵌套循环。分布式引擎中还衍生出广播哈希连接与 shuffle 哈希连接等分布式变体。