查询处理与优化课件

查询处理与查询 优化,目 录,查询处理,查询优化,查询处理,查询处理(query processing)是指从数据库中提取数据时所涉及的一系列活动。 语法分析与翻译 查询优化 查询执行,查询处理过程,语法分析与翻译器 查询处理开始之前，系统必须将查询语句翻译成可使用的形式。 语法分析与翻译阶段的主要工作有： 检查用户查询的语法，利用数据字典验证查询中出现的关系名、属性名等是否正确； 构造该查询语句的语法分析树表示，并将其翻译成关系代数表达式。,查询处理过程,查询执行计划与查询优化器 一个给定的查询任务，一般都会有多种计算结果的方法 例如，考虑如下查询 select studentName from Student where classNo=CS0701 and sex=女 该查询语句可翻译成如下关系表达式中的任意一个 classNo=CS0701(sex=女(studentName(Student) sex=女(classNo=CS0701(studentName(Student) classNo=CS0701(studentName(sex=女(Student) studentName(sex=女(classNo=CS0701(Student),查询处理过程,查询执行计划与查询优化器 执行一个查询，不仅需要提供关系代数表达式，还要对该表达式加上注释说明如何执行每个操作 加了“如何执行”注释的关系代数运算称为执行原语 用于执行一个查询的原语操作序列称为查询执行计划 不同的查询执行计划会有不同的代价 构造具有最小查询执行代价的查询执行计划是DBMS的责任 这项工作称为查询优化，由查询优化器来完成,查询处理过程,关系数据库系统和非过程化的SQL语言能够取得巨大成功关键是得益于查询优化技术的发展 查询优化是影响RDBMS性能的关键因素 查询执行引擎 根据输入的查询执行计划，调用相关算法实现查询计算，并将计算结果返回给用户 有效地对内存缓冲区进行管理是影响查询执行性能的非常重要的方面,目 录,查询处理,查询优化,查询优化,处理一个给定的查询，尤其是复杂的查询，通常会有许多种策略。 查询优化(query optimization)就是从这许多策略中找出最有效的查询执行计划的处理过程。 RDBMS能够构造并选择出一个具有最小查询执行代价的查询执行计划,查询优化的必要性,不同查询执行计划的执行时间分析 Q1 =SN(s.s# = sc.s# sc.c# = c2(SSC) Q2 =SN(sc.c# = c2(S SC) Q3 =SN(S sc.c# = c2(SC),（1）第一种情况 计算广义笛卡尔积 作选择操作 作投影操作 执行总时间为105s,（2）第二种情况 计算自然连接 作选择操作 作投影操作 执行总时间为205s,（3）第三种情况 先对SC作选择运算 作连接运算 作投影操作 执行总时间为10s,查询优化概述, 例：找出2008级修读“数据库系统概论”课程的学生姓名。初始关系表达式为： studentName(grade=2008courseName=DB(Class Student) (Score Course), 转换后的关系代数表达式为： studentName(grade=2008(Class) Student) (Score courseName=DB(Course),查询优化概述, 查询优化分3步进行 逻辑优化，产生逻辑上与给定关系代数表达式等价的表达式； 代价估计，估计每个执行计划的代价； 物理优化，对所产生的表达式以不同方式作注释，产生不同的查询执行计划。 查询优化器中第步和第步是交叉进行的 先产生一些等价的表达式并加以注释 再进一步产生一些等价表达式并加以注释，依此类推 第步是基于系统收集的一些统计信息，如关系的大小、属性值的分布、B+树索引的深度等，对一个执行计划的代价进行事先估计,关系表达式转换, 等价规则 合取选择运算的级联分解 选择运算满足交换律 系列投影的最后有效性 选择操作与连接相结合 =E1 E2 ,等价规则,连接运算的结合律 自然连接运算的结合律： (E1 E2) E3 = E1 (E2 E3) 连接运算的结合律：(E1 E2) E3 = E1 (E2 E3) 选择运算对连接运算的分配律 选择条件0的所有属性只涉及连接的表达式之一时，满足分配律 E2) = E2 当选择条件1只涉及E1的属性，且选择条件2只涉及E2的属性时满足分配律 E2) = ,等价规则,投影运算对连接运算的分配律 令A1、A2分别代表E1、E2的属性，假设连接条件只涉及A1A2中的属性，则 E2) = 令A1、A2分别代表E1、E2的属性；令A3是E1中出现在连接条件中但不在A1A2中的属性；令A4是E2中出现在连接条件中但不在A1A2中的属性 E2 ) = ,关系表达式转换, 转换实例 studentName(grade=2008courseName=DB(Class Student) (Score Course) studentName(grade=2008(Class) Student) Score) courseName=DB(Course) 步骤： 应用等价规划(1) ，表达式可以转换为 studentName(grade=2008(courseName=DB(Class Student) (Score Course) 两次应用等价规划(7)的第条 ，表达式可以转换为 studentName(grade=2008(Class Student) courseName=DB(Score Course),转换实例,studentName(grade=2008courseName=DB(Class Student) (Score Course) studentName(grade=2008(Class) Student) Score) courseName=DB(Course) 步骤： 再应用两次等价规划(7)的第条，表达式可以转换为 studentName(grade=2008(Class) Student) (courseName=DB(Score) Course) 第四，应用等价规划(5)，表达式可以转换为 studentName(grade=2008(Class) Student) (Course courseName=DB(Score) 应用等价规划(6)的第条， 得到