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

相关文章

来自专栏Jed的技术阶梯

Spark性能调优04-数据倾斜调优

数据倾斜的原理很简单:在进行shuffle的时候,必须将各个节点上相同的key拉取到某个节点上的一个task来进行处理,比如按照key进行聚合或join等操作。...

1205
来自专栏别先生

一脸懵逼学习Storm---(一个开源的分布式实时计算系统)

Storm的官方网址:http://storm.apache.org/index.html 1:什么是Storm?  Storm是一个开源的分布式实时计算系统,...

3027
来自专栏架构师之路

一分钟掌握数据库垂直拆分

一、缘起 当数据库的数据量非常大时,水平切分和垂直拆分是两种常见的降低数据库大小,提升性能的方法。假设有用户表: user( uid bigint, name ...

3585
来自专栏java一日一条

Java初学者必知:Java语言的11大特点

Java是一种简单的,面向对象的,分布式的,解释型的,健壮安全的,结构中立的,可移植的,性能优异、多线程的静态语言。那么java语言的特点是什么呢?

312
来自专栏Duncan's Blog

红黑树学习

1.红黑树是每个节点都带有颜色属性的二叉查找树,颜色或红色或黑色.并且有如下性质:

651
来自专栏Hongten

让你一看就明白什么是单列模式(和静态静态工厂模式)--java版本_源码下载

=================================================

361
来自专栏蘑菇先生的技术笔记

浅谈分布式计算的开发与实现(二)

24410
来自专栏吉浦迅科技

CUDA&OpenCL编程7个技巧及ArrayFire如何帮助您

· 向量化代码Vectorized Code: 加速器执行向量化代码性能会很好因为计算自然地映射到硬件的运算内核上。ArrayFire函数本质上是量化的,因此...

3966
来自专栏强仔仔

MySQL数据库系列之数据库设计原则

MySQL中数据库设计原则: 1.一般情况下,应该尽量使用可以正确存储数据的最小数据类型。数据类型不一样,存储的执行效率也不一样。最好使用适度的整型数据类型,...

21410
来自专栏蓝天

改进型MapReduce

本文通过对MapReduce的分析,列出MapReduce存在的问题,然后提出一种解决这些问题的改进型MapReduce,这种改进型的MapReduce暂且取名...

752

扫码关注云+社区