查询处理与查询代价估计课件.pptxVIP

查询处理与查询代价估计

目录n查询处理1、查询分析2、查询优化3、查询执行n查询代价估计

n查询处理

查询处理n查询处理是指从数据库中提取数据的一系列活动。包括：1、将用高层数据库语言表示的查询语句翻译成文件系统这一物理层次上实现的表达式；2、为优化查询进行各种转换；3、查询的实际执行。

查询处理过程DBMS语法分析器和翻译器关系代数表达式查询优化器查询结果执行引擎执行计划数据基于数据的统计分析

查询分析在数据库执行查询处理之前，系统先将查询语句翻译成可使用的形式。翻译过程：1、语法分析器将查询翻译成系统内部表示形式；2、翻译的同时进行语法检查；3、构造查询语句的语法分析树；4、翻译成关系代数表达式。对于给出的一个查询，一般经过翻译器翻译后都会有多种关系代数表达式与之对应。

查询分析实例查询实例:求选修2号课程的学生姓名SQL表示:selectSnamefromStudents,SCwhereStudents.Sno=SC.SnoandCno=‘2’；翻译结果：Q=π(σ(Student×SC))1SnameStudent.Sno=SC.Sno∧Sc.Cno=2Q=π(σ(StudentSC))2SnameSc.Cno=2Q=π(StudentσSc.Cno=2(SC))3Sname

优化器功能功能：负责产生最有效的查询执行计划（QEP）n逻辑转换部分：对于一个语法树，根据关系代数等价变换规则，得到所有的等价的关系代数表达式；n物理转换部分：对于每一个关系代数表达式，根据查询引擎提供的物理操作，找出所有可能的查询执行计划。n比较和查找：根据代价估计函数，估计每一个查询执行计划的代价，并从中找出代价最小的查询执行计划。

优化器处理过程代价估计函数查找物理操作集等价变换规则集代价最小QEP查询请求物理转换逻辑转换等价的语法树集合等价的QEP

查询执行引擎功能：n查询执行引擎为每一个关系操作的实现提供多种物理实现方法。n选择操作有两种可能的物理操作：顺序扫描和索引扫描n连接操作有三种可能的物理操作：嵌套循环连接、合并连接和散列连接。n查询执行引擎还可以提供更多的物理实现方法。每一种物理实现方法利用不同的存取路径（如索引、数据的存储分布、元组的排序等）n负责产生执行查询的代码

n查询代价的估计

查询的代价n查询执行开销主要包括集中式数据库总代价=I/O代价+CPU代价+内存代价分布式数据库总代价=I/O代价+CPU代价+内存代价+通信代价n查询代价主要取决于磁盘访问的次数。一个给定的查询，对应多种可能的处理策略。策略不同，访问磁盘的次数相差很大，甚至相差几个数量级。

查询代价的度量n对于大型数据库系统而言，在磁盘上存取数据的代价通常是最重要的代价，可以通过传输磁盘块数以及搜索磁盘次数来度量。n使用t表示传输一块数据的平均耗时，t表示搜索一次磁TS盘的平均定位时间(包括搜索时间加旋转时间)。则一个传输b块并作s次磁盘搜索的操作将耗时b*t+s*t毫秒(ms)TSn写磁盘块的代价通常是读磁盘块的2倍n执行计划所需挂钟时间

用于代价估算的统计信息n相关的统计信息主要包括：?n：关系r中的元组数目。r?b：用于存储关系r所有元组的块数目。r?s：关系r中一个元组的大小。r?f：关系r的块因子，即一个物理块中能存放的关系r的元组数目。r?V(A,r)：关系r中属性A所具有的不同值的数目，该数目与∏(r)的A大小相同。若A为关系r的码，则V(A,r)=n。r?SC(A,r)：关系r关于属性A的选择度，表示在属性A上满足某个等值条件（假设至少有一条记录满足该等值条件）的平均记录数。

用于代价估算的统计信息?f:索引i的内节点的平均扇出,适用于树结构索引,如B+树i?HT:索引i的层数—即高度i对于关系r上A属性的平衡树索引(如B+-树),HT=?log(V(A,r))?ifi对于散列索引,HT为1i?LB:索引i的底层索引块数—即索引叶子层的块数i

查询代价估计举例n查询实例:求选修2号课程的学生姓名SQL表示:selectSnamefromStudents,SCwhereStudents.Sno=SC.SnoandCno=‘2’;n数据库模式的样例Students(Sno,Sname,Ssex,Sage,Sdept)SC(Sno,Cno,Grade)假定学生-课程数据库中有1000个学生记录，10000个选课记录其中选修2号课程的选课记录为50个

可能的语句翻译结果Q=πSname(σStudent