InfoQ Geekathon 大模型技术应用创新大赛 了解详情
写点什么

数据库内核杂谈(八):数据库优化器(下)

  • 2019-12-25
  • 本文字数:0 字

    阅读完需:约 1 分钟

数据库内核杂谈(八):数据库优化器(下)

本篇文章选自数据库内核杂谈系列文章。


在上一篇文章中,我们介绍了优化器的大概并且讲解了一系列通过语句重写来对查询进行优化的方法。文末也留了一个坑:当语句中涉及到多个表的 join 时,优化器该如何决定 join 的顺序(join ordering)来找到最优解呢?这期,我们接着这个话题往下说。


答案就是,优化器也只能尽力而为。上一篇文章中我们提到过 n 个表的 join 搜索空间高达 4^n,理论上只有穷尽搜索空间,才能保证找到最优解。但即便有时间和能力穷尽搜索空间,也未必能找到最优解(此为后话,暂且不表)。因此优化器的主要职责是,在资源限制内,这里资源可以是计算资源或者优化时间,找到尽可能足够好的执行计划。

启发式算法(Heuristic approach)

4^n 的搜索空间实在太大了,首先要做的就是,减小搜索空间。数据库的先贤们,想到了应用启发式算法(heuristic approach)来降低搜素空间。比如,最早的 Volcano Optimizer 里,就提出了对于 Join-order,只考虑 left-deep-tree,即所有的右子树必须是一个实体表。可能解释起来不太直观,对应下面三张不同的 join-order 的树形结构,就一目了然了。



left-deep-tree



bushy-tree 1



bushy-tree 2


其中图 1 就是 left-deep-tree,图 2 和图 3 称为 bushy-tree。那为什么只选择 left-deep-tree?要知道,即使是 left-deep-tree,搜素空间也有 n!。我自己的理解是结构比较简单,执行计划也很直观:左边的表不断和右边的表 join 生成新的 intermediate 表(中间表),然后不断递归。在讲 join 实现的那章时,我们提到过,大部分情况下都会使用 HashJoin。如果能够使得左边的 result set 一直很小,从而建立的 Hash 表能一直存放在内存中的话,对于全部右子树的表,只要进行一次全表扫描,即可得到最终结果。因此,右子树的 table order 就不是特别影响运行时间了(因为总是得至少进行一次全表扫描的)。这种情况下,已经算是很优的执行计划了。


说完了优点,再来看看 left-deep-tree 有什么不好的地方? 那就是不能同时执行多个 join。如果按图 3 中的 bushy-tree 2,那 A 和 B, C 和 D 可以同时进行 join。对于现在服务器配备多个 CPU 和大内存作为计算资源,考虑 bushy tree,肯定是会有更多的优化可能的。反之,也可能因为早期的服务器并没有那么多计算资源,本来也并不考虑对一个 SQL 查询进行并行执行,因此采用 left-deep-tree 的 heuristic,也就说得通了。


因此,left-deep-tree 的 join ordering 优化关键在于能够让左边的结果集, 从一开始的叶节点以及后续的所有 intermediate result 越来越小,最好能一直 fit in memory,这样就能保证所有的右子树表只需要进行一次全表扫描。要如何选择哪个表放在哪个位置呢?我们需要一些概率统计的知识。

Cardinality Estimation

Cardinality estimation,就是用来预测单个表的 selection cardinality 和 2 个表的 join cardinality 的技术。首先,简单介绍一些术语。


Selection cardinality: SC(P, R)
复制代码


表示当 predicate 是 P 的时候,对于表 R,最后大约会有多少条 row 输出。


举个例子,对于表 student, 假设 P 为 major = ‘CS’, 相当于我们要计算下面这个 SQL 有多少 row 输出。


SELECT * FROM student WHERE major = 'CS';
复制代码


要对输出进行预测,我们先要对表收集一些基本的元信息。有哪些信息呢?1)对于表 student,首先需要知道总共有多少 row;2)对于 student 表中的每个 column,总共有多少个 distinct value。你可能会想, 数据库是什么收集这些数据的呢? 有些数据库会不定期地自动更新每个表以及每个 column 的统计信息,一般都还提供相关的语句来让数据库对某个表做元数据的统计:analyze TABLE 语句。有了这两个信息,那我们怎么计算 selection cardinality,再来看下面这个公式。


SC(P, R) = N_R * SEL(P, R) 
复制代码


这边 SEL§ 就是统计意义上每个 row 满足 P 的概率。那怎么计算 SEL§呢。假设 P 很简单,只是单个 column 的 equality,比如上述示例 major = ‘CS’。基于 distinct value 的信息,我们假设 V(major, student)总共有 10 个专业,在此基础上,我们进一步假设数据均匀分布,那 major = 'CS’的概率就是 10%, 即 SEL(major = ‘CS’, student) = 10% 。如果 N_R = 100。那我们就可以推算出 SC(major = ‘CS’, student)约等于 10 条输出。是不是挺简单的,下面来看一些复杂的 predicate 的预测。


如果 P 并不是简单的 equality join,比如 age != 30。假设 SEL(age = 30, student) = 90%, 可以通过 negation 推算出 SEL(age != 30, student) = 10%


如果 P 是 age > 30 呢?这时候就需要用到大于 30 的 age 还有多少个 distinct value,我们假设 age 总共有 10 个 distinct value,且大于 30 的还有 4 个值,再次基于数据均匀分布假设,就可以推算出 SEL(age > 30, student) = 40%。


再来看更复杂一些的 predicate,如牵涉多个 column 的。如果是 P 是 age = 30 and major = ‘CS’。这里,我们需要一个新的假设,朴素贝叶斯定理假设条件互相独立。则 SEL(age = 30 ^ major = ‘CS’, student) = SEL(age = 30, student) * SEL(major = ‘CS’, student)。


如果 predicate 的 condition 是 disjunction,如 SEL(age = 30 V major = ‘CS’, student) = SEL(age = 30, student) + SEL(major = ‘CS’, student) - SEL(age = 30, student) * SEL(major = ‘CS’, student)。可以根据下图来推出这个公式:



disjunction


讲完了单个表的selection cardinality。那join cardinality呢?比如下面这句语句:


SEL * FROM R1, R2 WHERE R1.a = R2.a;
复制代码


由于本人数学实在不好,就直接给出公式了:


JC(R1, R2, R1.a = R2.a) = N_R * N_S / max(V(a, R), V(a, S))
复制代码


其中 V(a, R)就是指对于表 R 中 column a,一共有多少个 distinct value。


刚刚我们通过示例讲解了许多计算 selection cardinality 和 join cardinality 的方法。但刚才所有的计算假设都是数据是均匀分布(uniformly distributed)。现实情况肯定不会这么容易,比如我们计算 major = 'CS’的 student,CS 专业的学生肯定比其他专业学生要多一些。 那有什么办法可以改进吗?另一种常见的对 column 的值分布进行统计的方法就是使用 Histogram。Histogram 呢,除了统计有哪些 distinct value,还记录了这些 value 分别出现了几次,下图给出了一个 Histogram 统计的示例。



Histogram example


由于牵涉过多数学,我们就不展开了,有兴趣的同学可以参考


这里



Histogram 通过存储更多的信息来统计更精确的数值分布。但很多情况下,统计并不需要那么精确。工程方面要在使用资源和准确性里找平衡。后来,又有大牛提出了HyperLogLog,是一种占用资源少,但能给出较为准确的近似结果的 cardinality estimator。


总结一下,有了 cardinality estimation,我们终于能预测哪两个表 join 后的 cardinality 比较小,可以用来决定 join ordering 了。但同时也发现,cardinality estimation 给出的只是预测结果,这也是为什么文章开头的时候谈到,即使能够穷尽搜索空间,依然不一定能找到最优解的原因。因为预测的结果是有出入的,并且随着 join 变得更复杂, 层级越多,越往上的误差就越大。


Cardinality estimation 仅仅是帮助决定了 join ordering,相当于 logical operator tree 上,不同的表分别应该放在哪个位置。但对于每个 logical operator,最后还需要变换成 physical operator (物理算子)才算完成最终的优化。如,对与 TableScan 这个逻辑算子,它对应的 physical operator 有 SequentialScan 和 IndexScan,应该用哪个? 对于 JoinOperator,到底是用 NestedLoopJoin, SortMergeJoin,还是 HashJoin 呢?下面,我们介绍第二个关键技术。

Cost Model

Cost Model 的主要思想是,对于每一个 Physical operator,根据输入输出的 cardinality,会被赋值一个 cost(代价)。这个 cost,通常情况下可以认为是执行这个 operator 需要的时间,当然也可以是计算资源。那如何计算这个 cost 呢?对于每个 operator,都有一个 cost formula(公式),这个公式根据输入输出的信息,最后能计算出这个 operator 的 cost 值。


还是配合示例来讲解:对于 SequentialScan(全表扫描),它的 cost formula 我们定义成如下:


Cost = NumRowsInTable * RowWidth * SEQ_SCAN_UNIT_COST
复制代码


解释一下这个公式,因为对于全表扫描,需要读取所有的 row,因此读取时间大致正比于表的 total row * 表的 width。而最后的 coeffficient SEQ_SCAN_UNIT_COST,可以想象成是一个虚拟的时间单位。


对于 IndexScan 呢?它的 cost formula 又长成什么样呢?区别于 Sequential Scan,它不需要全表扫描,但对于从 Index 中读取满足条件的 Row,需要回到原表中读取,相当于执行了 random IO。因此,我们可以根据操作的实现,定义它 cost formula 如下:


Cost = SelectionCardinality * RowWidth * INDEX_SCAN_UNIT_COST
复制代码


而这边,INDEX_SCAN_UNIT_COST 可以认为是 random IO 的 cost,所以它的值应该要比 SEQ_SCAN_UNIT_COST 要大很多。比如,我们假定 SEQ_SCAN_UNIT_COST 值为 1,那 INDEX_SCAN_UNIT_COST 就可以设为 100。先不管这样设是否准确。但有了 cost formula 的定义,我们就能计算每个 physical operator 在当前环境下的 cost 了。再来参考下面这个示例:


SELECT * FROM student WHERE major = 'CS';
复制代码


现在假设,student 表对 major 建有 index,然后 student 表总共有 10000 个 row,然后假定 cardinality estimation 给出的 selection cardinality 是 500,即有 500 个 CS 学生。我们再假设 width 是 10。分别把这些信息带入 SequentialScan 和 IndexScan 的公式可得:


SequentialScan Cost = 10000 * 10 * 1 = 100000
IndexScan Cost = 500 * 10 * 100 = 500000
复制代码


在这种情况下,Optimizer 就会选择 SequentialScan。但如果查询语句变了,变为 major = ‘archaeology’ (考古学),作为一个冷门专业,cardinality estimation 预测只有 10。再分别计算 cost:


SequentialScan Cost = 10000 * 10 * 1 = 100000
IndexScan Cost = 10 * 10 * 100 = 10000
复制代码


在上述情况下,optimizer 就应该选择 IndexScan。


那如何定义 cost formula 和 coefficient 的值呢?这确实是一个很难的问题。笔者曾经做过相关的 research,cost formula 是需要根据 operator 的实现来定义的。甚至一个 operator,根据不同的执行环境,都会有不同的 cost formula。cost formula 意在去 simulate 真实执行下所花掉的时间。而对于 coefficient,笔者当时提出的方法就是通过执行 mini-benchmark 来 calibrate coefficient 的值,因为不同的部署环境,网络条件和硬件资源,都会影响 coefficient。当时对一些 operator 进行了测试,calibrate 后,效果立竿见影,只可惜后来离开公司了,没能把这个 research 做完。


讲完了单个 operator,我们再来看全局。对于一个 logical operator tree,Optimizer 要做的就是,当它变换成 Physical operator tree 后,所有的 operator 的 cost 相加(也可以是有权重的相加,假定多个 operator 可以并行执行,这边我们暂且不考虑这种复杂情况)后,使得 total cost 最小,这便是 optimizer 给出的最优 physical execution plan。


你可能会觉得,似乎对于每一个 logical operator, 选择哪一个 physical operator 是一个 local optimization 的问题。至少 Scan operator 看上去是这样的。其实并没那么简单。还记得我们说过 index Scan 带来的一个好处是什么吗? 就是读取后的数据是有序的。有序是一个很好的属性,如果上层的 operator 对有序有需求,比如 SortMergeJoin,或者 SortGroupByAggregate,那原本需要排序的 cost 就被省去了。因此对于同一个 operator,它的 cost 不仅仅和自己的 cost formula 相关,还和它的子节点的 operator 也相关。比如对于 SortMergeJoin operator 来说,它的两个子节点都是 IndexScan, 或者是 Sequential Scan 会对它本身的 cost 产生影响,如果是 sequential scan 的话,排序的 cost 是需要计算在它的 cost formula 里的,但如果是 index scan,那排序的 cost 就为 0 了。因此,计算每个 operator 的 cost 是一个 global optimization 的问题。假定,对每个 operator,我们定义一个 aggregated cost 等于它本身的 cost 加上所有子节点的 cost。那 Optimizer 要求解的就是使得 root operator 的 aggregated cost 最小的 physical operator tree。是否有联想到什么算法了吗? global optimization? Bingo!就是 dynamic programming。我觉得这可能是我工作中遇到的第一个真正使用 DP 解决的问题了吧:多阶段决策最优解模型;求解过程中需要多个决策阶段,每个决策阶段都会取决于最优子结构;并且,最优子结构属于重复子问题,因为会被多次使用到。上层无论是 HashJoin 或者是 SortMergeJoin 都会需要知道下层表的 SequentialScan 的 cost 是多少。因此我们需要 memorize 这个 SequentialScan 的 cost。整个计算过程自顶向下递归,对于子问题 memorize 结果,最终我们就能计算出最小的 root operator 的 aggregated cost, 以及它所对应的 physical operator tree。这就是最后 optimizer 输出的 physical execution plan。

总结

今天我们先从 join ordering 问题讲起,介绍了 cardinality estimation 技术,它通过预测 selection cardinality 和 join cardinality 来帮助决定 join ordering。然后介绍了 cost model 来对每个对应的 physical operator 计算 cost。最后通过 dynamic programming 来求解最小 cost 的 physical operator tree,以此得到最终的 physical execution plan。


终于,理论部分讲完了。这两期比较枯燥和深奥,但为了完整性,我觉得还是有必要的。最后,推荐大家一篇paper,介绍一个开源的数据库优化器 ORCA 的设计和实现(本人也是作者之一)。这是我当时第一份工作时参与的项目。


说了那么多枯燥的理论,咱们以一个小趣事结尾吧。当时我问组里的人为什么叫 ORCA(虎鲸),是不是因为虎鲸很聪明?然后组里的头说"let me show you something"。然后打开 Youtube,放的是一段几头虎鲸围猎一群海豚的视频,场面略带血腥。头边放边说,“look at these babies, they are so smart!” 当时我也是虎躯一震。后来我仔细去查了一下,虎鲸生性残暴,喜欢虐杀。还有相关 research 说,从已经解析的虎鲸叫声中发现,大约 70%的叫声都是抱怨和咒骂。。可见脾气之暴躁。但谁让它长得萌,和大熊猫一样黑白配。所以说,这是一个看脸的世界。相对的,大白鲨,一副凶神恶煞的样子,被拉了不少仇恨。但你不知道,大白鲨,特别怕虎鲸,特别怕。


相关阅读:


数据库内核杂谈(一):一小时实现一个基本功能的数据库


数据库内核杂谈(二):存储“演化论”


数据库内核杂谈(三):索引优化


数据库内核杂谈(四):执行模式


数据库内核杂谈(五):如何实现排序和聚合


数据库内核杂谈(六):表的 JOIN(连接)


数据库内核杂谈(七):数据库优化器(上)


活动推荐:

2023年9月3-5日,「QCon全球软件开发大会·北京站」 将在北京•富力万丽酒店举办。此次大会以「启航·AIGC软件工程变革」为主题,策划了大前端融合提效、大模型应用落地、面向 AI 的存储、AIGC 浪潮下的研发效能提升、LLMOps、异构算力、微服务架构治理、业务安全技术、构建未来软件的编程语言、FinOps 等近30个精彩专题。咨询购票可联系票务经理 18514549229(微信同手机号)。

2019-12-25 08:006065

评论 16 条评论

发布
用户头像
作者留言:2022年1月1日,祝大家新年快乐。不知不觉,数据库内核杂谈又陪伴大家一年(虽然。。还是不可避免地拖更了)。今年的new year resolution,希望创建一个群,和大家一起交流。加我微信 81211430(请备注数据库内核杂谈,谢谢),我会建群。期待和大家交流。
2022-01-01 12:29
回复
用户头像
顾老师好,作为一个数据库初学者,读了您的文章后收获颇多,非常想继续深入读下去。因为没有看到查询优化这里关于子查询提升等部分,所以想问一下您数据库系列是否只有这十几期?最后再次感谢您,文章非常精彩!
2021-10-11 16:32
回复
用户头像
希望作者继续写下去,有深度的文章,付费也可以啊
2021-09-05 15:06
回复
感谢感谢,不用付费。持续催更就行。。我更新比较慢,尽量做到1个月1更。
2021-09-05 21:33
回复
用户头像
作者来留个言,一言难尽的2020终于过去了,新年快乐,希望2021对所有人,都充满惊喜。数据库内核杂谈也已经更新到第十四期了,再次感谢各位的关注。如果你是内核杂谈的真粉丝,觉得内核杂谈对你有收获,愿意听我多扯扯,欢迎加入我的知识星球:Dr.ZZZ 聊技术和管理:https://t.zsxq.com/VrZbeAE(由于不知道能输出多少,也不知道有多少粉丝,所以还是先免费吧)
2021-01-01 02:43
回复
用户头像
真的写的很好,深入浅出!支持作者!
2020-09-03 11:39
回复
用户头像
JC(R1, R2, R1.a = R2.a) = N_R * N_S / max(V(a, R), V(a, S))
请教一下我觉得上面这个公式的除数是不是应该是计算出的max的值的平房呢。
2020-02-29 16:50
回复
我的理解是:N_R * N_S 是笛卡尔积的总数,1 / max(V(a, R), V(a, S))是笛卡尔积中每个结果被选中的可能性。因为值等值join,所以选择大表的维度。
2020-05-04 22:36
回复
用户头像
建议分享一些论文什么的
2020-02-29 15:51
回复
用户头像
要干掉mysql,有野心的项目~
2020-02-16 16:37
回复
用户头像
收益良多,应该写极客时间专栏
2020-01-20 10:05
回复
用户头像
请问这个专栏还继续更新么?写的真好,收益良多
2020-01-13 12:43
回复
还会更新的,作者在龟速写稿中,哈哈哈哈
2020-01-16 10:46
回复
作者来回复啦!会继续更新,保证不能断更。。但是,前阵子休假了。。偷懒了。感谢阅读。一定再接再厉。
2020-01-16 13:26
回复
用户头像
膜拜大佬。从前面看过来,到这篇是真的懵逼了...
2019-12-26 18:21
回复
感谢关注和阅读!
2020-01-16 10:47
回复
没有更多了
发现更多内容

甲方日常 33

句子

工作 随笔杂谈 日常

京东智联云MySQL数据库如何保障数据的可靠性?

京东科技开发者

MySQL 数据库

5G时代音视频开发王器:WebRTC

华章IT

flutter 音视频 WebRTC React Native

分布式系统设计理念这么难学?

架构师修行之路

分布式 微服务

架构师的成长之路

华章IT

CTO 架构师 架构师之道

关注你自己,如同篮球巨星一样,让身体最佳化,持续投入最爱的事情。

叶小鍵

健康 科普 王立铭 肥胖

帆软授权失效处理

Flychen

Servlet-技术专题-Servlet3异步原理与实践

洛神灬殇

CloudQuery v1.1.1 修复版本发布

BinTools图尔兹

数据库 sql 安全 工具软件

第19届亚运会门票采用区块链技术防伪

CECBC

区块链技术 防伪 溯源

第12周学习总结

Vincent

极客时间 极客大学

NET-Core中的配置文件操作

为体验更多

C# .net .net core ASP.NET Core

LAXCUS大数据集群操作系统:一个分布式分时共享E级系统软件(四)

陈泽云

人工智能 大数据 数据结构 操作系统 数据存储

微服务架构:基于微服务和Docker容器技术的PaaS云平台架构设计(微服务架构实施原理)

AI乔治

Java 架构 微服务 ,docker

计算机网络基础知识总结

cxuan

计算机网络 计算机

手把手带你玩转 openEuler | openEuler 的使用

openEuler

操作系统 openEuler

让AI人才在产业界闪闪发光:百度之星的“神奇滤镜”是怎样炼成的?

脑极体

“区块链技术创新要植根市场”

CECBC

金融科技 信息安全

Java Reference核心原理分析

AI乔治

Java 架构 JVM 性能调优

架构训练营 - 第4周课后作业 - 学习总结

Pudding

黄金圈法则:成功者必备的深度思考方法

程序员陆通

黄金圈法则 厉害 牛逼

有了容器为什么kubernetes还需要Pod?

架构师修行之路

分布式 微服务 pod kubernete

据说99.99%的人都会答错的类加载的问题

AI乔治

Java 架构 JVM 类加载 性能调优

第12周作业

Vincent

极客时间 极客大学

最新版MySQL在MacOS上的安装与使用

王磊

MySQL

诸多老牌数据仓库厂商当前,Snowflake如何创近12年最大IPO金额

华为云开发者联盟

数据仓库 数据 存储

十七、深入Python异常处理

刘润森

Python

“区块链×多方计算”解决众多难题 将成区块链应用新场景

CECBC

区块链 数据融合

云计算简史(上)- 15分钟读完15年

明道云

架构师训练营 - 第 4周课后作业(1 期)

Pudding

考研须知

时间是一个人最好的证明

考研

  • 扫码添加小助手
    领取最新资料包
数据库内核杂谈(八):数据库优化器(下)_语言 & 开发_顾仲贤_InfoQ精选文章