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

相关文章

来自专栏小小挖掘机

数据城堡参赛代码实战篇(二)---使用pandas进行数据去重

小编们最近参加了数据城堡举办的“大学生助学金精准资助预测”比赛,分组第19名的成绩进入了复赛,很激动有木有!在上一篇文章中,小编带你使用pandas并结合官方给...

3368
来自专栏PingCAP的专栏

Succinct Data Structure

最近看了一篇论文 SuRF: Practical Range Query Filtering with Fast Succinct Tries,里面提到使用一种...

2636
来自专栏章鱼的慢慢技术路

笔试常考题型之时间复杂度

1223
来自专栏青玉伏案

关于Simple_html_dom的小应用

  今天一同学给我推荐了本书,说是刚出不久,内容还不错,是心灵鸡汤类的书,于是按捺不住就像在网上下一本,可是木有资源肿么办。只有在线看的,作为一个准码农,所以甭...

1927
来自专栏猿人谷

为什么使用抽象类?有什么好处?

最简单的说法也是最重要的理由:接口和实现分离 老是在想为什么要引用抽象类,一般类不就够用了吗。一般类里定义的方法,子类也可以覆盖,没必要定义成抽象的啊。 看了下...

1699
来自专栏拭心的安卓进阶之路

RxJava 1.x 笔记:过滤型操作符

我真的是奇怪,上下班的路上看书、看文章学习的劲头特别大,到了周末有大把的学习时间,反而不珍惜,总想打游戏,睡前才踏踏实实地写了篇文章,真是服了自己! 本文内容...

2729
来自专栏CDA数据分析师

用SPSS做数据分析?先弄懂SPSS的基础知识吧

1、SPSS数据分析的流程 ? 2、SPSS特性: ? 3、数据的编辑: 1 常量 数值型常量:除了普通写法外还可以用科学计数法,如:1.3E18; 字符型常量...

21310
来自专栏一个会写诗的程序员的博客

《Kotin 极简教程》第8章 函数式编程(FP)(1)第8章 函数式编程(FP)《Kotlin极简教程》正式上架:

"函数式编程", 又称泛函编程, 是一种"编程范式"(programming paradigm),也就是如何编写程序的方法论。它的基础是 λ 演算(lambda...

782
来自专栏IT技术精选文摘

搜索引擎架构概述

架构 对软件系统来讲,从一个层面对系统的各个组件进行抽象.描述它们各自的功能、提供的接口以及它们之间的关系. 需求 架构为应付需求而产生,对搜索引擎来讲,它主要...

21910
来自专栏章鱼的慢慢技术路

笔试常考题型之时间复杂度

2616

扫码关注云+社区