10分钟梳理关系数据库基础知识(五):查询优化与连接算法

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

优化器

今天的内容相对来说清汤寡水一点,就梳理下优化器(optimizer)的内容。没什么复杂的。

数据库拿到我们给的SQL后,会解析成一棵语法树。而优化器做的事情,就是应用关系代数的知识,找出等价的多种计算路径(即对这棵树进行数学上等价的变换)。这个过程就是我们标题中的查询优化。

那么要衡量不同方案的好坏,就需要我们设计一个代价的评价标准,这就是代价模型。而优化的思路可以分基于代价和基于规则两种。

基于代价需要我们掌握数据库中的统计信息,比如表中的记录数,记录的大小,某个字段中不同取值的数目(即选择性的高低)等。MySQL8.0中会加入直方图。

基于规则就是变换执行计划时,有一些启发式规则。比如尽早执行选择操作,尽早执行投影操作,避免笛卡尔积等。指导思想就是尽早的缩减规模。

好,这一块基本上就这些要点了。我感觉抓住指导思想就显得很清晰,当然去细究细节的话也会很有意思,比如MySQL的代价模型是怎么算的,我以前听姜承尧说他觉得MySQL 5.7的代价模型有个bug,这个有兴趣可以一起看看源代码。

连接

顺便复习下做等值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表上也有索引且有个选择操作的话,行数会大大减少。使用索引会比块嵌套要快得多得多。

好,今天就到这里。

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

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

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专注研发

扩展欧几里得算法

    有两个数 a b,现在,我们要求 a b 的最大公约数,怎么求?枚举他们的因子?不现实,当 a b 很大的时候,枚举显得那么的naïve ,那怎么做?

843
来自专栏TensorFlow从0到N

讨厌算法的程序员 4 - 时间复杂度

增长量级 ? 函数的增长量级 上一篇算法分析基础中,我们分析了插入排序,知道了其最好情况下的运行时间为T(n) = an + b,最差情况下的运行时间为T(n...

2593
来自专栏蜉蝣禅修之道

Max-Min Fairness带宽分配算法

1576
来自专栏数据和云

如何编写更好的SQL查询:终极指南(下)

SQL是数据挖掘分析行业不可或缺的一项技能,对于SQL来说,编写查询语句只是第一步,确保查询语句高效并且适合于你的数据库操作工作,才是最重要的。在上一篇文章中,...

2746
来自专栏瓜大三哥

直方图操作(二)

直方图操作(二)之统计电路 在实际的图像中,连续的像素点灰度值为相同值的情况非常常见,如果每来一个像素都对双口RAM进行一次寻址和写操作,显然降低了统计效率而提...

1897
来自专栏人工智能LeadAI

讨厌算法的程序员 | 第四章 时间复杂度

增长量级 ? 函数的增长量级 上一篇算法分析基础中,我们分析了插入排序,知道了其最好情况下的运行时间为T(n) = an + b,最差情况下的运行时间为T(n...

2768
来自专栏灯塔大数据

每周学点大数据 | No.33最大独立集

No.33期 最大独立集 Mr. 王:好,现在我们来谈谈最大独立集的问题。首先求解最大独立集是一个NP-hard问题,接下来要介绍的这个求解方法是一个近...

3417
来自专栏marsggbo

Udacity并行计算课程笔记- Fundamental GPU Algorithms (Reduce, Scan, Histogram)

如下图示,第一种情况只有一个工人挖洞,他需要8小时才能完成,所以工作总量(Work)是8小时。第二种情况是有4个工人,它们2个小时就能完成挖洞任务,此时工作总量...

771
来自专栏机器学习算法原理与实践

FP Tree算法原理总结

    在Apriori算法原理总结中,我们对Apriori算法的原理做了总结。作为一个挖掘频繁项集的算法,Apriori算法需要多次扫描数据,I/O是很大的瓶...

723
来自专栏magicsoar

母函数及相关的算法题

母函数即生成函数,构造这么一个多项式函数g(x),使得x的n次方系数为f(n),是组合数学中尤其是计数方面的一个重要理论和工具。 (1+a1x)(1+a2x)(...

2038

扫码关注云+社区