20 | 关联查询：如何提升多表Join能力？
王磊
该思维导图由 AI 生成，仅供参考
你好，我是王磊，你也可以叫我 Ivan。
今天，我们会继续学习查询场景中的处理技术。这一讲的关键词是“多表关联”，也就是数据库中常见的 Join 操作。无论是单体数据库还是分布式数据库，关联操作的语义始终没有变，一些经典算法也保持了很好的延续性。
关联算法作为一个稍微细节点的设计，在不同数据库中是有差异的，我们还是秉承课程的整体思路，不陷入具体的设置参数、指令等内容。这样安排的依据是，只要你掌握关联算法的基本原理，就能快速掌握具体数据库的实现了。同时，有了这些原理作为基础，你也能更容易地掌握分布式数据库的优化思路。
那么，我们先来看看这些经典的关联算法吧。
三类关联算法
常见的关联算法有三大类，分别是嵌套循环（Nested Loop Join）、排序归并（Sort-Merge Join）和哈希（Hash Join）。
嵌套循环连接算法
所有的嵌套循环算法都由内外两个循环构成，分别从两张表中顺序取数据。其中，外层循环表称为外表（Outer 表），内层循环表则称为内表（Inner 表）。因为这个算法的过程是由遍历 Outer 表开始，所以 Outer 表也称为驱动表。在最终得到的结果集中，记录的排列顺序与 Outer 表的记录顺序是一致的。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文介绍了数据库中常见的多表关联查询操作及其优化算法。文章首先介绍了三种经典的关联算法：嵌套循环连接算法、排序归并连接算法和哈希连接算法，分别包括不同的子算法和性能优化空间。随后，文章探讨了分布式数据库中关联算法的优化与并行框架的密切关系，以及在大表和小表关联中的复制表和重分布等解决方案。最后，文章总结了关联计算的复杂性以及分布式数据库对关联算法的支持程度与OLAP场景的关联。整体而言，本文深入浅出地介绍了数据库关联查询的相关技术，为读者提供了全面的概览。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《分布式数据库 30 讲》，新⼈⾸单¥59
《分布式数据库 30 讲》，新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(13)
- 最新
- 精选
Jxin
重分布这个有疑惑: 如果我有多个关联查询呢?每次关联查询都重分布？这样重分布就可能是个死循环了。因为A关联查询和B关联查询的重分布,可能会相互影响。作者回复: 多表关联会被拆解成多个阶段执行，21讲正好有个例子，可以关注下。
2020-09-2321- 有铭Grace这个最早使用GHJ算法数据库没有查到啊？ 很久以前就困惑传统数据库在分表分库后如何解决joint的问题。今天看到这篇文章后豁然开朗
作者回复: Grace出处这个说法是从论文中来的，我也没有考证，应该是某个学术界的数据库吧。
2020-09-23 
Jowin分布式数据库的并行查询，底层依赖的是和大数据计算平台相同的并行计算技术。可以想见，在Spark上支持SQL查询，其实是一样的原理。这一讲非常棒，把分布式数据库和大数据技术串起来了！2021-03-082- Geek_64affe思考题最主要的问题我觉得应该是如何确定 大/小 表2022-05-10
wy老师有个问题不理解 假设两个表数据量一样大都是n,那么嵌套循环的复杂度是n*n ,而排序归并的复杂度应该是nlogn+nlogn+2*n约等于nlogn。这样看的话排序归并的效率更高一点，但是文中你说成本更高一些，体现在什么地方呢2021-01-261- black_mirrorHI，Ivan老师好 1、GHJ算法，是不是每次只把inner表bucket加入内存，而outer表的bucket一直在磁盘中，进行2者的比较？ 2、observer node4 节点第2个工作线程是不是应该叫4-2 ？2020-12-28
幼儿编程教学大表join，查询过来的时候，再做重分布？在节点间移动数据？这样不会很慢？是不是我的理解哪里有问题？这种指的是olap吧？2020-11-22
星之柱h如果选择的inner表ash不均衡的时候，就退化成了嵌套循环2020-11-18
游弋云端“在计算逻辑允许的情况下，建立阶段选择数据量较小的表作为 Inner 表”，我的问题就是在什么情况下，系统无法根据数据量决定 Inner 表呢？ 答复：如果连接属性本身内容重复较多，但是表格很大，这样反而选择较大的表格作为 Inner 表，可以根据内容相同，从而节省Hash的计算资源。想到这种场景。2020-09-24- 赵见跃哈希算法，“在计算逻辑允许的情况下，建立阶段选择数据量较小的表作为 Inner 表”，我的问题就是在什么情况下，系统无法根据数据量决定 Inner 表呢？这个问题，也很困惑，大家给指点一下呀，谢谢。2020-09-24
收起评论
