10 分钟梳理关系数据库基础知识(六) : 连接的算法与代价

导语 每天10分钟,用去食堂吃饭的时间解决一个知识点。

全目录

10分钟梳理关系数据库基础知识(一)——三范式

10分钟梳理关系数据库基础知识(二)——存储结构

10分钟梳理关系数据库基础知识(三)——B+树

10分钟梳理关系数据库基础知识(四)——两阶段多路归并排序

10分钟梳理关系数据库基础知识(五)——查询优化

连接

本文复习下做等值JOIN时不同的连接方式与代价,通过粗略的估算给大家一个直观的认识。

假设我们有s和t两张表,现在要做JOIN。s表的记录数设为5000,占据的块数设为100;t表的记录数设为10000,占据的块数设为400。

嵌套循环连接

就是最简单的,以一张表的每一行记录,与另一张表的每一行记录比较。直接来两层for循环。我们来估算下代价。

若从s表的每行记录出发,那么最坏情况下,块传输次数是5000×400+100=2000100,搜索次数是5000+100=5100。

若从t表的每行记录出发,那么最坏情况下,块传输次数是10000×100+400=1000400,搜索次数是10000+400=10400。

块嵌套循环连接

一个小小的优化思路是,我每次以块的方式处理关系,这样不就可以减少块读写次数了么。

若从s表的每块出发,最坏情况下,块传输次数是100×400+100=40100,搜索次数是2×100=200。与前面相比,思路上小小的变化造就了性能上大大的提升。

索引嵌套循环连接

如果连接的字段上有B+树索引,设每个节点有20个索引项,t表记录数为10000,那么树的高度就是4,回表假设再加一次磁盘IO,此时访问次数为100+5000×5=25100,每次访问都有一次搜索和一次块传输。咦,怎么用了索引反而代价更高了?大家注意下,这里只说了t表上有索引,如果s表上也有索引且有个选择操作的话,行数会大大减少。使用索引会比块嵌套要快得多得多。

好,今天就到这里。2016年也就到这里了。祝大家新的一年里都有好运气。:)

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

算法模板——二分图匹配

实现功能为二分图匹配 原理:匈牙利算法,核心思想——匹配上了就配,没直接匹配上也要通过前面的腾出位置让这个匹配上(详见:趣写算法系列之——匈牙利算法) 本程序以...

3324
来自专栏Jed的技术阶梯

Hive窗口函数02-NTILE、ROW_NUMBER、RANK、DENSE_RANK

Hive窗口函数NTILE、ROW_NUMBER、RANK、DENSE_RANK入门

872
来自专栏斑斓

使用Python Pandas处理亿级数据

在数据分析领域,最热门的莫过于Python和R语言,此前有一篇文章《别老扯什么Hadoop了,你的数据根本不够大》指出:只有在超过5TB数据量的规模下,Hado...

6445
来自专栏数据科学与人工智能

【Python环境】使用Python Pandas处理亿级数据

在数据分析领域,最热门的莫过于Python和R语言,此前有一篇文章《别老扯什么Hadoop了,你的数据根本不够大》指出:只有在超过5TB数据量的规模下,Hado...

2775
来自专栏IT派

使用 Pandas 处理亿级数据

在数据分析领域,最热门的莫过于Python和R语言,此前有一篇文章《别老扯什么Hadoop了,你的数据根本不够大》指出:只有在超过5TB数据量的规模下,Hado...

1064
来自专栏算法channel

BAT面试题2:请简要介绍下Tensorflow的计算图

接下来,每天推送一道BAT的面试题,一般问到的这些知识点都是很重要的,所以知道的就再复习一下,不知道的希望这篇可以帮助到你。日积月累,你会在不知不觉中就步入机器...

1882
来自专栏PPV课数据科学社区

【学习】在Python中利用Pandas库处理大数据的简单介绍

在数据分析领域,最热门的莫过于Python和R语言,此前有一篇文章《别老扯什么Hadoop了,你的数据根本不够大》指出:只有在超过5TB数据量的规模下,...

3577
来自专栏美团技术团队

函数式编程在Redux/React中的应用

本文简述了软件复杂度问题及应对策略:抽象和组合;展示了抽象和组合在函数式编程中的应用;并展示了Redux/React在解决前端状态管理的复杂度方面对上述理论的实...

3449
来自专栏一名叫大蕉的程序员

大数据计数原理1+0=1这你都不会算(三)No.51

这是本坑的第三篇,之前已经说了关于 HashSet 和 BitMap 了,这次说说 Bloom Filter 布隆过滤器,要是还不知道前面讲了啥的,可以点一下下...

1829
来自专栏AI派

TensorFlow修炼之道(3)——计算图和会话(Graph&Session)

在计算图中,节点表示计算单位,边表示计算用到和产生的数据。 例如,在TensorFlow图中,tf.matmul操作将对应于具有两个输入边(要乘以的矩阵)和一个...

2954

扫码关注云+社区