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