9_查询处理.ppt

查询处理过程 语法分析与翻译器 查询处理开始之前，系统必须将查询语句翻译成可使用的形式。 语法分析与翻译阶段的主要工作有： 检查用户查询的语法，利用数据字典验证查询中出现的关系名、属性名等是否正确； 构造该查询语句的语法分析树表示，并将其翻译成关系代数表达式。 查询处理过程 查询执行计划与查询优化器 一个给定的查询任务，一般都会有多种计算结果的方法 例如，考虑如下查询 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’(S×SC)) Q2 =πSN(σsc.c# = ‘c2’(S ? SC)) Q3 =πSN(S ? σsc.c# = ‘c2’(SC)) 查询优化概述 ■ 例：找出2008级修读“数据库系统概论”课程的学生姓名。初始关系表达式为： ∏studentName(σgrade=2008∧courseName=DB((Class ? Student) ? (Score ? 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的属性，假设连接条件θ只涉及A1∪A2中的属性，则