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

《数据库上课第十三讲查询处理、优化》由会员分享，可在线阅读，更多相关《数据库上课第十三讲查询处理、优化（77页珍藏版）》请在金锄头文库上搜索。

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

2、l 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 studentNamefrom Student where classNo=CS0701 and sex=女该查询语句可翻译成如下关系表达式中的任意一个classN

4、o=CS0701(sex=女(studentName(Student)sex=女(classNo=CS0701(studentName(Student)classNo=CS0701(studentName(sex=女(Student)studentName(sex=女(classNo=CS0701(Student)执行一个查询，不仅需要提供关系代数表达式，还要 对该表达式加上注释来说明如何执行每个操作。加了“如何执行”注释的关系代数运算称为执行原语。用于执行一个查询的原语操作序列称为查询执行计划。不同的查询执行计划会有不同的代价。DBMS通过查询优化器构造具有最小查询执行代价的查询执行计划，称

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

6、算时，通常假定是最坏的情形。 大型数据库系统最重要的代价通常是在磁盘上存取数据的 代价，通过传输磁盘块数以及搜索磁盘次数来度量。 例如：一个传输b块并作s次磁盘搜索的操作将耗时btT+stS （毫秒(ms)）其中：tT：传输一块数据的平均耗时tS：搜索一次磁盘的平均定位时间(包括搜索时间加旋转时间)*16查询优化器利用存储在DBMS的数据字典中的统计信息来估算 查询执行计划的代价，相关的统计信息主要包括： nr：关系r中的元组数目。 br：用于存储关系r所有元组的块数目。 lr：关系r中一个元组的大小。 fr：关系r的块因子，即一个物理块中能存放的关系r的元组数目。 V(A, r)：关系r中属

7、性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(A, r)。 HTi：索引i的层数，即高度。2.2 选择运算用于选择运算的搜索算法： 1) 文件扫描：不用索引的搜索算法线性搜索算法 A1二分搜索算法 A2 2) 索引扫描：使用索引的搜索算法在主索引的码属性上的等值比较算法 A3

8、在主索引的非码属性上的等值比较算法 A4在辅助索引上的等值比较算法 A5在主索引上的范围比较算法 A6在辅助索引上的范围比较算法 A71)选择运算文件扫描文件扫描：用于定位、检索满足选择条件的记录线性搜索算法A1 线性搜索中，系统扫描每一个文件块，对所有记录进行 测试，看它们是否满足选择条件。开始时需作一次磁盘 搜索来定位文件的第一个块。 线性搜索的代价为EA1=br*tT+tS，其中br代表文件中的磁盘块数。 *19线性搜索算法A1 的优缺点*20 二分搜索算法A2关于搜索码物理有序存储，搜索过程是针对文件的磁盘块进行，而不是针对记录进行最坏情况下，找到包含所需记录的磁盘块所需访问和检查 的

9、磁盘块数目为log2(br) ，而且每一个这样的磁盘块都需要一次磁盘搜索定位，因此算法A2的时间代价为EA2=log2(br)*(tT+tS)如果是在非码属性上的选择操作，那么可能会有多个块包含所需记录，这样还需顺序读取包含选择结果的额外块，估计有SC(A, r)/fr-1个额外块 。*212）选择运算索引扫描主索引码属性上的等值比较算法 A3 具有主索引的码属性上的等值比较算法，可以通过主索引检索到指向满足相应等值条件的唯一记录的指针，再根据该指针到数据文件中访问磁盘块。若使用B+树索引，则访问索引块的数量等于树高度HTi，访问文件块的数量为1；而且每一次I/O操作都需要一次磁盘搜索定位和一

10、次磁盘块传输。因此，算法A3的时间代价为：EA3=HTi+1*(tT+tS)*22主索引非码属性上的等值比较 算法 A4 通过主索引检索到指向满足相应等值条件的第一条记录（可能有多条记录，但它们在物理上顺序存放）的指针，再根据该指针到数据文件中访问磁盘块。 需要访问的文件块的数目可估计为：b=SC(A, r)/fr 算法A4的时间代价为EA4=HTi+1*(tT+tS)+(SC(A, r)/fr-1)*tT*23辅助索引的等值比较算法A5 如果是码属性上的等值条件，算法A5的时间代价与算法A3相同。 如果是非码属性上的等值条件，则通过辅助索引可以检索到存放满足相应等值条件的多条记录的指针桶的指

11、针，再根据该指针桶中的每一个指针分别到数据文件中访问包含相应记录的文件块。 最坏情况下，算法A5的时间代价为：EA5=HTi+1+SC(A, r)*(tT+tS)其中的加1是表示访问指针桶的代价。 *24主索引上的范围比较算法A6 对于形如Av或Av的比较条件，首先通过主索引（如B+树索引） 搜索，定位在满足Av或Av条件的第一个索引项，该索引项中的指针指向满足查询条件的所有记录中的第一条。然后通过该指针到文件中搜索磁盘块，并从该磁盘块开始顺序访问 所有的磁盘块，直到文件结束。其时间代价可估算为（SC(P(A), r)表示满足谓词P(A)的选择度）EA6=HTi+1*(tT+tS)+ (SC(

12、P(A), r)/fr-1)*tT 对于形如Av或Av的比较条件A=90(Score) classNo=CS0701(Student)*442.5 其他运算排序外部排序归并(external sort-merge， ESM)算法 去除重复元组 投影集合运算聚集运算*45*463.1 概述查询优化(query optimization):处理一个给定的查询，尤其是复杂的查询，通常会有许多种策略。从这许多策略中找出最有效的查询执行计划的处理过程。 由于关系表达式的语义级别很高，使关系系统可以从关系表达式中分析查询语义，提供了执行查询优化的可能性 关系查询优化是影响RDBMS性能的关键因素;查询优化

13、的特点优化器可以从数据字典中获取许多统计信息，可以考虑数百种不同的执行计划优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。3.1.2 查询优化器作用：通过某种代价模型计算出各种查询执行策略的执行 代价，然后选取代价最小的执行方案。代价包括集中式数据库磁盘存取块数(I/O代价)（主要）处理机时间(CPU代价)查询的内存开销 分布式数据库 总代价=I/O代价+CPU代价+内存代价通信代价 3.1.3查询优化的总目标：选择有效

14、的策略求得给定关系表达式的值使得查询代价最小(实际上是较小) 3.2 查询优化的类型1.逻辑优化：产生逻辑上与给定关系代数表达式等价 的表达式；2.代价估计：基于系统收集的一些统计信息，如关系的大小 、属性值的分布、B+树索引的深度等，对一个执行计划的代价进行事先估计。3.物理优化：对所产生的表达式以不同方式作注释， 产生不同的查询执行计划。 在查询优化器中第1步和第3步是交叉进行的*513.2.1 代数优化定义：基于关系代数等价变换规则的优化方法。方法：关系表达式转换(参看课本本章和关系代数一章)查询树的启发式优化 优化重点：连接运算的次序 一个好的连接运算次序对于减少中间结果的大小非常重要

15、，也会影响到连接算法的选择。大部分查询优化器在连接运算的次序上花了很多功夫。*52例找出2008级修读“数据库系统概论”课程的学生姓名。初始关系表 达式为： studentName(grade=2008courseName=DB(Class Student) (Score Course)转换后的关系代数表达式为：studentName(grade=2008(Class) Student) (Score courseName=DB(Course)3.2.2 代价估计一个运算的代价依赖于它的输入的大小和其他统计信息。因此，给定一棵查询树，要估计上一层某个运算的代价，首先需要估计其下层运算的中间结果集的大小。结果集大小的估计需要用到存储在数据库的数据字典中的有关统计信息，现实数据库系统中需要维护更详细的统计信息，以提高代价估计的精确度。大多数数据库系统中将每个属性的取值分布存储成一张直方图。 选择和连接运算的估计选择运算结果大小的估计选择运算结果大小的估计依赖于选择谓词。等值谓词选择运算A=a比较谓词选择运算Av连接运算结果大小的估计*553.2.3 物理优化物理优化就是要选择高效合理的操作算法或存取路径，求