V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
mynamewang0
V2EX  ›  数据库

hash join 构建 hash 表的意义是什么?

  •  
  •   mynamewang0 · 2019-10-30 08:10:41 +08:00 · 2217 次点击
    这是一个创建于 1870 天前的主题,其中的信息可能已经有所发展或是发生改变。

    已知 hash join 会取其中的值少的表的联结键做 hash 表存放在内存中,再用另一张表调用 hash 函数探测匹配 hash 表,匹配成功返回数据。那其中构建 hash 表的意义是什么?

    如果不构建 hash 表,直接把所有联结键存放在内存中,再取另一张表的联结键探测匹配,这样做有什么不合理的地方?

    8 条回复    2019-11-15 13:33:40 +08:00
    miaoever
        1
    miaoever  
       2019-10-30 08:26:14 +08:00
    ”再取另一张表的联结键探测匹配“ -> 怎么做探测匹配呢? hash table - O(1)
    des
        2
    des  
       2019-10-30 08:35:16 +08:00 via Android
    怎么看着像是考试题目一样的?
    现在主流的有三种实现,一个是 hash join,另一个就是最广泛的嵌套循环,还有一个忘了。
    嵌套循环得扫描 m+n 次,hash join 只用扫描 m+n 次再加上建 hash 的时间
    你可以先看看索引的相关知识
    agagega
        3
    agagega  
       2019-10-30 08:50:39 +08:00 via iPhone
    @des 还有一个是两边排序
    mynamewang0
        4
    mynamewang0  
    OP
       2019-10-30 08:53:00 +08:00
    @miaoever 所以 hash table 的意义之一是探测匹配?
    mynamewang0
        5
    mynamewang0  
    OP
       2019-10-30 08:54:06 +08:00
    @des 只有嵌套循环能用到索引,hash join 用不到索引吧
    restlessdream
        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 得到最终的结果。
    liprais
        7
    liprais  
       2019-10-30 13:08:24 +08:00
    "如果不构建 hash 表,直接把所有联结键存放在内存中,再取另一张表的联结键探测匹配,这样做有什么不合理的地方?"
    放不下啊.......
    lolizeppelin
        8
    lolizeppelin  
       2019-11-15 13:33:40 +08:00
    不看代码的话 知道 HashJoin 是 O1, 不是 m*n 性能屌爆就是了,缺点是 hashtable 空间不能太大

    MergeJoin 也是常见的 join

    各种 join 算法都不是很难实现的东西,mysql 这玩意只有一种算法是因为它没有统计数据去支持选哪种方式

    没有银弹..有银弹大家还选个啥
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   920 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 19:55 · PVG 03:55 · LAX 11:55 · JFK 14:55
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.