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

相关文章

来自专栏Duncan's Blog

Personalized Search泛读记录

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

762
来自专栏前端侠2.0

从左关联到数据维度的思考 原

在a 的结果集,用了group by ,其实相当于将表“降维”了。假如原来1000行,现在分组后结果集变为100行了。 在b 的结果集,没用group by ...

1114
来自专栏深度学习之tensorflow实战篇

用R进行文本分析初探——包含导入词库和和导入李白语句

用R进行文本分析初探——以《红楼梦》为例 一.写在前面的话~   刚吃饭的时候同学问我,你为什么要用R做文本分析,你不是应该用R建模么,在我和她解释了一会儿...

3514
来自专栏AI科技评论

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

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

3275
来自专栏新智元

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

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

3435
来自专栏华章科技

Python爬虫新手进阶版:怎样读取非结构化网页、图像、视频、语音数据

导读:常见的数据来源和获取方式,你或许已经了解很多。本文将拓展数据来源方式和格式的获取,主要集中在非结构化的网页、图像、视频和语音。

1063
来自专栏北京马哥教育

Python自然语言处理工具小结

作者:伏草惟存 来源:http://www.cnblogs.com/baiboy/p/nltk2.html 1 Python 的几个自然语言处理工具 NLTK:...

3777
来自专栏点滴积累

geotrellis使用(二十七)栅格数据色彩渲染

目录 前言 复杂原因及思路分析 实现过程 总结 一、前言        今天我们来研究一下这个看似简单的问题,在地理信息系统中颜色渲染应当是最基本的操作和功能,...

3925
来自专栏CSDN技术头条

Apache Kylin 深入Cube和查询优化

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

4198
来自专栏用户2442861的专栏

Mysql相关

我有个同学最近在学Mysql数据库,为了测试自己的学习成果,他们老大出了6道Mysql试题让他去做,晚上回来他又分享给我,我感觉非常经典,记录了这几道试题已及...

581

扫码关注云+社区