这是一个创建于 1860 天前的主题，其中的信息可能已经有所发展或是发生改变。
已知 hash join 会取其中的值少的表的联结键做 hash 表存放在内存中，再用另一张表调用 hash 函数探测匹配 hash 表，匹配成功返回数据。那其中构建 hash 表的意义是什么？
如果不构建 hash 表，直接把所有联结键存放在内存中，再取另一张表的联结键探测匹配，这样做有什么不合理的地方？
 |
1
miaoever 2019-10-30 08:26:14 +08:00
”再取另一张表的联结键探测匹配“ -> 怎么做探测匹配呢？ hash table - O(1)
|
 |
2
des 2019-10-30 08:35:16 +08:00 via Android
怎么看着像是考试题目一样的？
现在主流的有三种实现，一个是 hash join，另一个就是最广泛的嵌套循环，还有一个忘了。 嵌套循环得扫描 m+n 次，hash join 只用扫描 m+n 次再加上建 hash 的时间 你可以先看看索引的相关知识 |
 |
4
mynamewang0 OP @miaoever 所以 hash table 的意义之一是探测匹配？
|
|
5
mynamewang0 OP @des 只有嵌套循环能用到索引，hash join 用不到索引吧
|
 |
6
restlessdream 2019-10-30 11:42:33 +08:00
HashJoin 中的 hashmap 的 key->value 是 join key->所在行，用 hashmap 的目的是降低时间复杂度，因为 map 这种结构（一般实现是红黑树或者其变种）的时间复杂度为 O(logN)，比一行一行扫的 O(n)要快多了。
第二种是 NestedLoopJoin，目前 Mysql 只支持这种，如果内表有索引的话，时间复杂度可以大大降低到 O(MlogN ），M 为外表的行数，没有索引的话时间复杂度就很恐怖了，就是 O(MN ），而且，Mysql 内部对传统的 NestedLoop 进行了一定的优化，叫做 BlockedNestedLoopJoin，实际上可以简单的理解为和 HashJoin 一种结合。 第三种是 SortMergeJoin，这种用到的不多，据说是 Oracle 好像实现了？（不太确定），就是两张表根据 join 的 key 排序，然后在 Merge 得到最终的结果。 |
 |
7
liprais 2019-10-30 13:08:24 +08:00
"如果不构建 hash 表，直接把所有联结键存放在内存中，再取另一张表的联结键探测匹配，这样做有什么不合理的地方？"
放不下啊....... |
 |
8
lolizeppelin 2019-11-15 13:33:40 +08:00
不看代码的话 知道 HashJoin 是 O1, 不是 m*n 性能屌爆就是了,缺点是 hashtable 空间不能太大
MergeJoin 也是常见的 join 各种 join 算法都不是很难实现的东西,mysql 这玩意只有一种算法是因为它没有统计数据去支持选哪种方式 没有银弹..有银弹大家还选个啥 |
Select Language