数据库上课 第十三讲 查询处理、优化

1、机械自动化学院机械自动化学院20152015主讲：主讲： 顾顾 曦曦 电话：电话：1569718107915697181079EmailEmail：主要内容*2查询处理查询处理查询优化查询优化*3Profile简介Profile 是在Mysql5.1以后版本引入，来源于开源社区Jeremy Cole的贡献。当一条查询提交给服务器时，此工具会记录剖析信息到一张临时表，并且给查询赋予一个整数标识符。剖析信息包含数据库对某个查询的详细执行情况，对于分析和优化查询，提高数据库的性能很有帮助。Profile工具的使用启动数据库，登录客户端；使用数据库scoreDBmysql use scoredb；启动

2、查询刨析工具：mysql set profiling = 1;执行查询mysql select * from student;查看执行时间信息（单位：秒）mysql show profiles；*5查看详细信息*6 推荐书目高性能高性能MySQL（第（第3版）版）Baron Schwartz，Peter Zaitsev，Vadim Tkachenko 著宁海元，周振兴，彭立勋，等 译电子工业出版社 2013-5*7*81.1 概述查询处理(query processing)是指从数据库中提取数据时所涉及的一系列活动。用高层数据库语言(如SQL)表示的查询语句翻译成能在文件系统的物理层上使用的表

3、达式。为优化查询而进行的各种转换以及查询的实际执行 。查询处理的主要过程包括： 语法分析与翻译语法分析与翻译 查询优化查询优化 查询执行查询执行1） 语法分析与翻译器查询处理开始之前，系统将查询语句查询语句翻译成可使用的形式。 语法分析与翻译阶段的主要工作有：检查用户查询的语法，利用数据字典验证查询中出现的关系名、属性名等是否正确；构造该查询语句的语法分析树表示，并将其翻译成关系代数表达式关系代数表达式。 2） 查询执行计划与查询优化器一个给定的查询任务，一般都会有多种计算结果的方法 例如，考虑如下查询 select studentName from Student where classNo

4、=CS0701 and sex=女 该查询语句可翻译成如下关系表达式中的任意一个classNo=CS0701(sex=女(studentName(Student)sex=女(classNo=CS0701(studentName(Student)classNo=CS0701(studentName(sex=女(Student)studentName(sex=女(classNo=CS0701(Student)执行一个查询，不仅需要提供关系代数表达式，还要对该表达式加上注释来说明如何执行每个操作。加了“如何执行”注释的关系代数运算称为执行原语。用于执行一个查询的原语操作序列操作序列称为查询执行计划。

5、不同的查询执行计划会有不同的代价。DBMS通过查询优化器构造具有最小查询执行代价的查询执行计划，称为查询优化查询优化。 查询优化是影响RDBMS性能的关键因素。关系数据库系统和非过程化的SQL语言能够取得巨大成功关键是得益于查询优化技术的发展。3） 查询执行引擎查询执行引擎查询执行引擎根据输入的查询执行计划，调用相关算法实现查询计算，并将计算结果返回给用户。 有效地对内存缓冲区内存缓冲区进行管理是影响查询执行性能的非常重要的方面。 *142.1 概述查询处理的代价可以通过该查询对各种资源的使用情况进行度量。主要包括磁盘存取时间磁盘存取时间执行一个查询所用的执行一个查询所用的CPU时间、时间、在

6、并行在并行/分布式数据库系统中的通信开销等分布式数据库系统中的通信开销等对于大型数据库系统而言，在磁盘上存取数据的代价在磁盘上存取数据的代价通常是最重要的代价 ，可以通过传输磁盘块数以及搜索磁盘次数来度量。 在代价估算时，通常假定是最坏的情形。 大型数据库系统最重要的代价通常是在磁盘上存取数据的代价，通过传输磁盘块数以及搜索磁盘次数来度量。 例如：一个传输b块并作s次磁盘搜索的操作将耗时btT+stS （毫秒（毫秒(ms)）其中：tT：传输一块数据的平均耗时 tS：搜索一次磁盘的平均定位时间(包括搜索时间加旋转时间)*16查询优化器利用存储在DBMS的数据字典中的统计信息统计信息来估算查询执行

7、计划的代价，相关的统计信息主要包括： nr：关系r中的元组数目。 br：用于存储关系r所有元组的块数目。 lr：关系r中一个元组的大小。 fr：关系r的块因子，即一个物理块中能存放的关系r的元组数目。 V(A, r)：关系r中属性A所具有的不同值的数目，该数目与A(r)的大小相同。若A为关系r的码，则V(A, r)=nr。 SC(A, r)：关系r关于属性A的选择度，表示在属性A上满足某个等值条件（假设至少有一条记录满足该等值条件）的平均记录数平均记录数。若A为关系r的码，则SC(A, r)=1；若A为非码属性，并假定V(A, r)上不同的值在所有元组中平均分配，则SC(A, r)=nr/V(

8、A, r)。 HTi：索引i的层数，即高度。2.2 选择运算用于选择运算的搜索算法： 1) 文件扫描：不用索引的搜索算法线性搜索算法 A1二分搜索算法 A2 2) 索引扫描：使用索引的搜索算法在主索引的码属性上的等值比较算法 A3在主索引的非码属性上的等值比较算法 A4在辅助索引上的等值比较算法 A5在主索引上的范围比较算法 A6在辅助索引上的范围比较算法 A71)选择运算文件扫描文件扫描：用于定位、检索满足选择条件的记录线性搜索算法A1 线性搜索中，系统扫描每一个文件块，对所有记录进行测试，看它们是否满足选择条件。开始时需作一次磁盘搜索来定位文件的第一个块。 线性搜索的代价为EA1=br*t

9、T+tS，其中br代表文件中的磁盘块数。 *19线性搜索算法A1 的优缺点*20二分搜索算法A2关于搜索码物理有序存储，搜索过程是针对文件的磁盘块进行，而不是针对记录进行最坏情况下，找到包含所需记录的磁盘块所需访问和检查的磁盘块数目为log2(br) ，而且每一个这样的磁盘块都需要一次磁盘搜索定位，因此算法A2的时间代价为 EA2= log2(br) *(tT+tS)如果是在非码属性上的选择操作，那么可能会有多个块包含所需记录，这样还需顺序读取包含选择结果的额外块，估计有 SC(A, r)/fr -1个额外块 。*212）选择运算索引扫描主索引码属性上的等值比较算法主索引码属性上的等值比较算法

10、 A3 具有主索引的码属性上的等值比较算法，可以通过主索引检索到指向满足相应等值条件的唯一唯一记录的指针，再根据该指针到数据文件中访问磁盘块。若使用B+树索引，则访问索引块的数量等于树高度HTi，访问文件块的数量为1；而且每一次I/O操作都需要一次磁盘搜索定位和一次磁盘块传输。因此，算法A3的时间代价为： EA3= HTi+1 *(tT+tS)*22主索引非码属性上的等值比较算法 A4 通过主索引检索到指向满足相应等值条件的第一条记录（可能有多条记录，但它们在物理上顺序存放）的指针，再根据该指针到数据文件中访问磁盘块。 需要访问的文件块的数目可估计为： b= SC(A, r)/fr 算法A4的

11、时间代价为 EA4= HTi+1 *(tT+tS)+( SC(A, r)/fr -1)*tT*23辅助索引的等值比较算法A5 如果是码属性上的等值条件，算法A5的时间代价与算法A3相同。 如果是非码属性上的等值条件，则通过辅助索引可以检索到存放满足相应等值条件的多条记录的指针桶的指针，再根据该指针桶中的每一个指针分别到数据文件中访问包含相应记录的文件块。 最坏情况下，算法A5的时间代价为： EA5= HTi+1+SC(A, r) *(tT+tS) 其中的加1是表示访问指针桶的代价。 *24主索引上的范围比较算法A6 对于形如Av或Av的比较条件，首先通过主索引（如B+树索引）搜索，定位在满足A

12、v或Av条件的第一个索引项第一个索引项，该索引项中的指针指向满足查询条件的所有记录中的第一条。然后通过该指针到文件中搜索磁盘块，并从该磁盘块开始顺序访问所有的磁盘块，直到文件结束。其时间代价可估算为（SC(P(A), r)表示满足谓词P(A)的选择度） EA6= HTi+1 *(tT+tS)+ ( SC(P(A), r)/fr -1)*tT 对于形如Av或Av的比较条件A=90(Score) classNo=CS0701(Student)*442.5 其他运算排序外部排序归并(external sort-merge，ESM)算法 去除重复元组 投影集合运算聚集运算 *45*463.1 概述查询

13、优化(query optimization):处理一个给定的查询，尤其是复杂的查询，通常会有许多种策略。从这许多策略中找出最有效的查询执行计划的处理过程。 由于关系表达式的语义级别很高，使关系系统可以从关系表达式中分析查询语义，提供了执行查询优化的可能性 关系查询优化是影响RDBMS性能的关键因素;查询优化的特点优化器可以从数据字典中获取许多统计信息，可以考虑数百种不同的执行计划优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可

14、能的。3.1.2 查询优化器作用：通过某种代价模型计算出各种查询执行策略的执行代价，然后选取代价最小的执行方案。代价包括集中式数据库磁盘存取块数磁盘存取块数(I/O代价代价)（主要）（主要）处理机时间处理机时间(CPU代价代价)查询的内存开销查询的内存开销 分布式数据库总代价总代价=I/O代价代价+CPU代价代价+内存代价内存代价通信代价通信代价 3.1.3查询优化的总目标：选择有效的策略求得给定关系表达式的值使得查询代价最小(实际上是较小) 3.2 查询优化的类型逻辑优化逻辑优化：产生逻辑上与给定关系代数表达式等价的表达式；代价估计代价估计：基于系统收集的一些统计信息，如关系的大小、属性值的

15、分布、B+树索引的深度等，对一个执行计划的代价进行事先估计。物理优化物理优化：对所产生的表达式以不同方式作注释注释，产生不同的查询执行计划。 在查询优化器中第1步和第3步是交叉进行的*513.2.1 代数优化定义：基于关系代数等价变换规则的优化方法。方法：关系表达式转换(参看课本本章和关系代数一章)查询树的启发式优化 优化重点：连接运算的次序 一个好的连接运算次序对于减少中间结果的大小非常重要，也会影响到连接算法的选择。大部分查询优化器在连接运算的次序上花了很多功夫。*52例找出2008级修读“数据库系统概论”课程的学生姓名。初始关系表达式为：studentName(grade=2008cou

16、rseName=DB(Class Student) (Score Course)转换后的关系代数表达式为：转换后的关系代数表达式为： studentName(grade=2008(Class) Student) (Score courseName=DB(Course)3.2.2 代价估计一个运算的代价依赖于它的输入的大小和其他统计信息。因此，给定一棵查询树，要估计上一层某个运算的代价，首先需要估计其下层运算的中间结果集的大小。结果集大小的估计需要用到存储在数据库的数据字典中的有关统计信息，现实数据库系统中需要维护更详细的统计信息，以提高代价估计的精确度。大多数数据库系统中将每个属性的取值分布存

17、储成一张直方图。 选择和连接运算的估计选择运算结果大小的估计选择运算结果大小的估计依赖于选择谓词。等值谓词选择运算A=a比较谓词选择运算Av连接运算结果大小的估计*553.2.3 物理优化物理优化就是要选择高效合理的操作算法操作算法或存取路径存取路径，求得优化的执行计划。主要方法：主要方法： 基于代价估算的优化基于规则的启发式优化两者结合的优化方法例：*571）基于代价的优化 基于代价的优化器(cost-based optimizer，CBO)通过使用等价规划从给定的查询语句产生一系列查询执行计划，并选择代价最小的一个。对于一个复杂的查询，等价于给定查询的不同执行计划可能很多。基于代价的优化器

18、在实际应用中，不可能也没必要对所有可能的执行计划进行穷举搜索(这样将会导致不可接受的优化代价，即为了寻找最佳执行计划而花费的代价过高)通常都是采用各种剪枝的技术进行局部搜索，以寻找接近接近最优最优的执行计划。 *582）基于规则的启发式优化目标：减少中间结果的大小减少不相关的数据运算 减少扫描表的次数减少不相关元组的读取 *59一般准则选择操作尽可能先做目的：大大减少中间结果的大小执行连接前对关系适当地预处理两种预处理方法：在连接属性上建立索引和对关系排序目的：减少扫描表的次数减少不相关元组的读取投影运算和选择运算同时进行目的：避免重复扫描表投影同其前或其后的双目运算结合起来目的：避免重复扫描

19、表*60把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算目的：减少内外存交换的信息量找出公共子表达式目的：减少计算量*61常用的关系代数表达式的启发式方法常用的关系代数表达式的启发式方法针对一棵语法树，有下列常用的启发式：选择操作下移投影操作下移选择和投影的串接合并*623.3 多连接查询优化*63查询请求代价最小等价的JOIN树集合等价的QEPR1R3查询图ABR2joinjoinR3R2R1join树Sort-mergeNested-loopR3R2R1操作树3.4 一个实例求选修了2号课程的学生姓名。用SQL表达： SELECT Student.Sname FROM Stud

20、ent，SC WHERE Student.Sno=SC.Sno AND SC.Cno=2； 假定学生-课程数据库中有n1000个学生记录n10000个选课记录n其中选修2号课程的选课记录为50个 可以用多种等价的关系代数表达式1）Q1=sname(student.Sno=sc.Snosc.Cno=2 (studentsc)2）Q2=sname(sc.Cno=2 (student SC)3）Q3=sname(student sc.Cno=2(sc)1) 第一种情况第一种情况Q1=Sname(Student.Sno=SC.SnoSc.Cno=2 (StudentSC)1. 计算广义笛卡尔积计算广义

21、笛卡尔积 把Student和SC的每个元组连接起来的做法：在内存中尽可能多地装入某个表(如Student表)的若干块，留出一块存放另一个表(如SC表)的元组。把SC中的每个元组和Student中每个元组连接，连接后的元组装满一块后就写到中间文件上从SC中读入一块和内存中的Student元组连接，直到SC表处理完。再读入若干块Student元组，读入一块SC元组重复上述处理过程，直到把Student表处理完设一个块能装10个Student元组或100个SC元组，在内存中存放5块Student元组和1块SC元组，则读取总块数为 =100+20100=2100块其中，读Student表100块。读S

22、C表20遍，每遍100块。若每秒读写20块，则总计要花105s 连接后的元组数为103104=107。设每块能装10个元组，则写出这些块要用106/20=5104s 1010005101000100100002. 作选择操作作选择操作 依次读入连接后的元组，按照选择条件选取满足要求的记录 假定内存处理时间忽略。读取中间文件花费的时间(同写中间文件一样)需5104s 满足条件的元组假设仅50个，均可放在内存 3. 作投影操作作投影操作 把第2步的结果在Sname上作投影输出，得到最终结果 第一种情况下执行查询的总时间105+25104105s所有内存处理时间均忽略不计 2) 第二种情况第二种情况 Q2=Sname(Sc.Cno=2 (Student SC)1. 计算自然连接 执行自然连接，读取Student和SC表的策略不变，总的读取块数仍为2100块花费105 s 自然连接的结果比第一种情况大大减少，为104个 写出这些元组时间为104/10/20=50s，为第一种情况的千分之一 2. 读取中间文件块，执行选择运算，花费时间也为50s。3. 把第2步结果投影输出。 第二种情况总的执行时间105+50+50205s 3) 第三种情况第三种情况Q3=Sname(Student Sc.Cno=2(SC)1. 先对SC表作选