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 条评论
登录 后参与评论

相关文章

来自专栏Kevin Chen

大数据计算中复杂存储过程的替代方案

以往的数据结构和业务逻辑比较简单,所以单条SQL语句就可以实现业务的需要。但随着技术的进步,用户计算的复杂程度也越来越高。要实现复杂的计算,单条SQL语句就显得...

7157
来自专栏智能大石头

大数据分析中使用关系型数据库的关键点

相当一部分大数据分析处理的原始数据来自关系型数据库,处理结果也存放在关系型数据库中。原因在于超过99%的软件系统采用传统的关系型数据库,大家对它们很熟悉,用起来...

934
来自专栏大数据和云计算技术

技术专栏丨2018 存储技术热点与趋势总结

类型:技术专栏 作者介绍 张凯(Kyle Zhang),SmartX 联合创始人 & CTO。毕业于清华大学计算机系,研究方向为分布式系统和体系结构。2013...

4218
来自专栏存储

列式存储的另一面

列式存储的另一面 列存是常见的数据存储技术,在许多场景下也确实很有效,因而也被不少数据仓库类产品采用,在业内列存也常常就意味着高性能。 可是,列存真有这么好吗?...

28010
来自专栏FreeBuf

看我如何基于Python;Facepp打造智能监控系统

由于种种原因,最近想亲自做一个基于python&facepp打造的智能监控系统。 0x00:萌芽 1:暑假在家很无聊 想出去玩,找不到人。玩个lol(已卸载),...

4595
来自专栏月色的自留地

大恒工业相机多实例使用

1845
来自专栏飞总聊IT

大数据那些事(15):Cosmos的技术

Cosmos是微软大数据的应用平台,内部使用不开源,最开始支撑Bing的后端,到后来扩展到整个微软。作为一个完整的系统,基本上Hadoop系统里面有的它也多多少...

3046
来自专栏大数据和云计算技术

SQL on Hadoop 技术分析(二)

森哥大作,接上一篇:SQL on Hadoop技术分析(一) SQL on Hadoop 技术分析(二) 本篇继续分析SQL on Hadoop的相关技术,本次...

4068
来自专栏Sorrower的专栏

GPU编程(二): GPU架构了解一下!

http://html.rhhz.net/tis/html/20150101.htm# http://hustcat.github.io/gpu-archit...

2742
来自专栏跟着阿笨一起玩NET

浅谈数据库设计技巧(上)(转)

转一篇他人写的数据库设计技巧,感觉也不一定都正确,开拓一下思路吧。 说到数据库,我认为不能不先谈数据结构。1996年,在我初入大学学习计算机...

1691

扫码关注云+社区