查询处理与优化PPT课件

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