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

相关文章

来自专栏机器之心

专栏 | 百度PaddlePaddle的新特性与大规模稀疏数据分布式模型训练

百度深度学习框架 PaddlePaddle 自 2016 年开源以来,受到了业界的广泛关注,PaddlePaddle 社区更是汇集了一大批 AI 技术开发者。开...

13930
来自专栏顶级程序员

不多掏钱 让数据库快200倍,Really?!

这年头几乎每个人都在这样那样抱怨性能。数据库管理员和程序员不断发现自己处于这种情形:服务器遇到了瓶颈,或者查询起来没完没了,这种情况并不少见。这种郁闷对我们所...

398110
来自专栏新智元

【自动编译代码】陈天奇团队TVM重磅更新:直接在浏览器使用GPU

【新智元导读】华盛顿大学陈天奇团队的深度学习自动优化代码生成器TVM发布更新,不需要写一行Javascprit代码,直接就能将深度学习模型编译到WebGL,然后...

47250
来自专栏喔家ArchiSelf

嵌入式中的人工神经网络

人工神经网络在AI中具有举足轻重的地位,除了找到最好的神经网络模型和训练数据集之外,人工神经网络的另一个挑战是如何在嵌入式设备上实现它,同时优化性能和功率效率。...

23920
来自专栏Duncan's Blog

Personalized Search泛读记录

搜索在20年前就已出现在互联网,而如今搜索已经无处不在。传统的搜索像这样,用户给出Query,Query中包含1个或多个关键词,搜索引擎通过关键词去检索返回查询...

10920
来自专栏AI科技评论

学界 | 大规模分布式存储如何优化?Facebook说自己的方法能把CPU负载降一半

AI 科技评论按:Facebook今天在研究blog上发布了一篇文章,介绍了自己的超大规模图分区优化算法SHP。这是 Facebook 为了处理自己的规模过大的...

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

用R进行文本分析初探——以《红楼梦》为例

一.写在前面的话~   刚吃饭的时候同学问我,你为什么要用R做文本分析,你不是应该用R建模么,在我和她解释了一会儿后,她嘱咐我好好写这篇博文,嗯为了娟儿同学,细...

49650
来自专栏我是攻城师

如何合理的控制solr查询的命中的数量和质量?

44150
来自专栏CSDN技术头条

Apache Kylin 深入Cube和查询优化

近几年,Apache Kylin作为一个高速的开源分布式大数据查询引擎正在迅速崛起。它充分发挥Hadoop、Spark、HBase等技术的优势,通过对超大规模数...

55480
来自专栏灯塔大数据

分析 | Python抓取婚恋网用户数据,原来这才是年轻人的择偶观

刚好在看决策树这一章,书里面的理论和例子让我觉得这个理论和选择对象简直不能再贴切。看完长相看学历,看完学历看收入。

26430

扫码关注云+社区

领取腾讯云代金券