第一章绪论数据库系统基础ppt课件.ppt

第九章关系查询处理和查询优化 授课内容 9 1关系数据库系统的查询处理9 2关系数据库系统的查询优化9 3代数优化9 4物理优化 9 1关系数据库系统的查询处理 查询处理步骤 RDBMS查询处理过程 1 查询分析2 查询检查3 查询优化4 查询执行 查询处理步骤 1 查询分析对查询语句进行扫描 从查询语句中识别出语言符号 如SQL关键字 数据库对象名 进行语法检查和语法分析 判断查询语句是否符合SQL语法规则 查询处理步骤 查询检查根据数据字典对合法的查询语句进行语义检查根据数据字典中的用户权限和完整性约束定义对用户的查询请求进行检查检查通过后把SQL查询语句转换成等价的关系代数表达式RDBMS一般都用查询树 语法分析树 来表示扩展的关系代数表达式 查询处理步骤 查询优化每个查询都会有多个可供选择的执行策略 查询优化就是选择一个高效率的执行策略查询优化分类 代数优化 指关系代数表达式的优化物理优化 指存取路径和底层操作算法的选择 查询处理步骤 查询执行依据优化器得到的执行策略生成查询计划代码生成器 codegenerator 生成执行查询计划的代码 实现查询操作的算法示例 1 选择操作的实现SELECT FROMStudentwheresno 95006 选择操作的实现 1 简单的全表扫描方法对查询的基本表顺序扫描 逐一检查每个元组是否满足选择条件 把满足条件的元组作为结果输出适合小表 不适合大表2 索引 或散列 扫描方法选择条件中的属性上有索引 例如B 树索引或Hash索引 通过索引先找到满足条件的元组指针 再通过元组指针直接在查询的基本表中找到元组 选择操作的实现 索引表 连接操作的实现 连接操作是查询处理中最耗时的操作之一SELECT FROMStudentinnerjoinSConStudent Sno SC Sno 连接操作的实现 嵌套循环方法 nestedloop 对外层循环 Student 的每一个元组 检索内层循环 SC 中的每一个元组检查这两个元组在连接属性 sno 上是否相等如果满足连接条件 则串接后作为结果输出 直到外层循环表中的元组处理完为止 连接操作的实现 2 排序 合并方法 sort mergejoin或mergejoin 常用算法 尤其适合连接的诸表已经排好序的情况 95001王三95002王四95003王五95004王六 9500119295001285950013889500329095003380 连接操作的实现 3 索引连接 indexjoin 方法步骤 如果SC表的属性Sno上原来没有索引 在SC表的属性Sno上建立索引 对Student中每一个元组 由Sno值通过SC的索引查找相应的SC元组 把这些SC元组和Student元组连接起来循环执行 直到Student表中的元组处理完为止 连接操作的实现 4 HashJoin方法把连接属性作为hash码 选用同一个hash函数 950011929500128595001388950022909500238095003175 95001 950011929500128595001388 95002 9500229095002380 95003 95003175 9 2关系数据库系统的查询优化 关系数据库系统的查询优化 关系语言 关系代数 关系演算语言和SQL语言 是一个非过程化的语言 用户只要提出 干什么 不必指出 怎么干 SELECTsnameFROMStudentinnerjoinSConStudent SNO SC SNOwhereSC CNO 2 关系数据库系统的查询优化 1 优化器可以从数据字典中获取许多统计信息 而用户则难以获得这些信息 2 如果数据库的物理统计信息改变了 系统可以自动对查询重新优化以选择相适应的执行计划 3 优化器可以考虑数百种不同的执行计划 程序员一般只能考虑有限的几种可能性 4 优化器中包括了很多复杂的优化技术 这些优化技术往往只有最好的程序员才能掌握 系统的自动优化相当于使得所有人都拥有这些优化技术 关系数据库系统的查询优化 RDBMS通过某种代价模型计算出各种查询执行策略的执行代价 然后选取代价最小的执行方案查询执行方案的代价集中式数据库总代价 I O代价 CPU代价 内存代价分布式数据库总代价 I O代价 CPU代价 内存代价 通信代价 9 3代数优化 代数优化 代数优化策略 通过对关系代数表达式的等价变换来提高查询效率关系代数表达式的等价 指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的两个关系表达式E1和E2是等价的 可记为E1 E2 连接 笛卡儿积的交换律E1 E2 E2 E1E1 E2 E2 E1E1 E2 E2 E1其中F为连接运算条件 的结合律 E1 E2 E3 E1 E2 E3 E1 E2 E3 E1 E2 E3 E1 E2 E3 E1 E2 E3 关系代数的等价变换规则 F F F1 F2 F1 F2 关系代数的等价变换规则 投影串接定律 A1 A2 An B1 B2 Bm E A1 A2 An E 其中 1 E是关系代数表达式2 Ai i 1 2 n Bj j l 2 m 是属性名3 A1 A2 An 构成 Bl B2 Bm 的子集 Sname sage Sname sno sage Student Sname sage Student 关系代数的等价变换规则 选择 串接定律 F1 F2 E F1 F2 E SC Grade 60 SC Cno 2 SC SC Grade 60 SC Cno 2 SC 关系代数的等价变换规则 选择与投影的交换律 F A1 A2 An E A1 A2 An F E 其中F涉及 A1 A2 An 中的部分属性 SC Grade 60 SC Sno SC Grade SC SC Sno SC Grade SC Grade 60 SC 关系代数的等价变换规则 与笛卡尔积的交换律1 若F中只涉及E1中的属性 则 F E1 E2 F E1 E2 SC Cno 2 SC Student SC Cno 2 SC Student2 若F F1 F2 并且F1只涉及E1中的属性 F2只涉及E2中的属性 则 F E1 E2 F1 F2 E1 E2 F1 E1 F2 E2 SC Cno 2 sdept IS Student SC sdept IS Student SC Cno 2 SC 关系代数的等价变换规则 与笛卡尔积的交换律3 若F F1 F2 并且F1只涉及E1中的属性 F2涉及E1和E2中的属性 则 F E1 E2 F1 F2 E1 E2 F2 F1 E1 E2 使部分选择在笛卡儿积前先做 关系代数的等价变换规则 与 的分配律设E E1 E2 且E1与E2有相同的属性名 则 F E1 E2 F E1 F E2 A 2 E1 E2 A 2 E1 A 2 E2 关系代数的等价变换规则 与差的分配律若E1与E2有相同的属性名 则 F E1 E2 F E1 F E2 与 的分配律 F E1 E2 F E1 F E2 关系代数的等价变换规则 与 的分配律设E1和E2是两个关系表达式 A1 An是E1的属性 B1 Bm是E2的属性 则 A1 An B1 Bm E1 E2 A1 An E1 B1 Bm E2 与 的分配律设E1与E2有相同的属性名 则 A1 An E1 E2 A1 An E1 A1 An E2 查询树的启发式优化 驾驶汽车到达某人的家 写成算法是这样的 沿167号高速公路往南行至阳谷 从阳谷高速出口出来后往山上开4 5英里 在一个杂物店旁边的红绿灯路口右转 接着在第一个路口左转 从左边褐色大房子的车道进去 就是某人的家 启发式方法来描述则可能是这样 找出上一次我们寄给你的信 照着信上面的寄出地址开车到这个镇 到了之后你问一下我们的房子在哪里 这里每个人都认识我们 肯定有人会很愿意帮助你的 如果你找不到人 那就找个公共电话亭给我们打电话 我们会出来接你 查询树的启发式优化 简而言之 启发式是一种经验性的指导原则 依靠好的启发式 我们可以大得到进行高效 快速的问题求解 查询树的启发式优化 典型的启发式规则 1 选择运算应尽可能先做 在优化策略中这是最重要 最基本的一条2 把投影运算和选择运算同时进行如有若干投影和选择运算 并且它们都对同一个关系操作 则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系 查询树的启发式优化 典型的启发式规则 3 把投影同其前或其后的双目运算结合起来4 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算 Studnet Sno SC Sno Studnet SC Studnet SC 查询树的启发式优化 典型的启发式规则 5 找出公共子表达式如果这种重复出现的子表达式的结果不是很大的关系并且从外存中读入这个关系比计算该子表达式的时间少得多 则先计算一次公共子表达式并把结果写入中间文件是合算的 查询树的启发式优化 算法 关系表达式的优化输入 一个关系表达式的查询树输出 优化的查询树 查询树的启发式优化 算法步骤 查询选修了2号课的学生学号 姓名以及该门课的成绩 sno sname grade SC Cno 2 Studnet Sno SC Sno Student SC 查询树的启发式优化 算法步骤 1 利用规则 把形如 F1 F2 Fn E 变换为 F1 F2 Fn E sno sname grade Studnet Sno SC Sno SC Cno 2 Student SC sno Sname grade SC Cno 2 Studnet Sno SC Sno Student SC 查询树的启发式优化 算法步骤 2 对每一个选择 利用规则 尽可能把它移到树的叶端 查询树的启发式优化 算法步骤 3 对于每一个投影 利用规则 尽可能把它移到树的叶端 查询树的启发式优化 算法步骤 4 利用规则 把选择和投影的串接合并成单个选择 单个投影或一个选择后跟一个投影 sage 18 sdept IS Student sage 18 sdept IS Student 关系代数的等价变换规则 算法步骤 5 把笛卡尔积和其后的选择合并成某种连接运算 练习 SELECTsname sdeptFROMs c scWHEREs sno sc snoANDo oANDcname 数据结构 练习 图书管理数据库关系模型如下 图书B 书号BN 书名T 作者A 学生S 借书证号LN 姓名N 班级C 借书L 借书证号LN 书号BN 日期D 查询 2007 5 1 即D 20070501 以前借过数据库原理这本书的学生姓名 要求 1 以笛卡尔积为基础表达查询 2 写出关系代数语法树并转换为标准形式 连接操作的实现 2 排序 合并方法 sort mergejoin或mergejoin 如果连接的表没有排好序 先对Student表和SC表按连接属性Sno排序取Student表中第一个Sno 依次扫描SC表中具有相同Sno的元组当扫描到Sno不相同的第一个SC元组时 返回Student表扫描它的下一个元组 再扫描SC表中具有相同Sno的元组 把它们连接起来重复上述步骤直到Student表扫描完 连接操作的实现 4 HashJoin方法把连接属性作为hash码 选用同一个hash函数步骤 划分阶段对包含较少元组的表 SC 进行一遍处理把它的元组按hash函数分散到hash表的桶中试探阶段 也称为连接阶段 joinphase 对另一个表 Student 进行一遍处理把Student的元组散列到适当的hash桶中把元组与桶中所有来自SC并与之相匹配的元组连接起来 关系数据库系统的查询优化 求选修2号课程的学生姓名SELECTsnameFROMStudentinnerjoinSConStudent SNO SC SNOwhereSC CNO 2 关系数据库系统的查询优化 假设1 数据量Student 1000条 SC 10000条选修2号课程 50条 关系数据库系统的查询优化 假设2 连接方法 基于数据块的嵌套循环法在内存中尽可能多地装入Student表的若干块元组 留出一块 A块 存放SC表的元组 然后从SC表读一块元组装入A块然后把A块中的SC元组与内存中的Student元组连接 连接完后写入到中间文件 再从SC表读一块元组装入A块 与内存中的Student元组连接 连接完后写入到中间文件 重复读SC表 直到SC表处理完 再一次读入Student表的其他若干块元组 重复上述过程 直到Student表处理完 关系数据库系统的查询优化 假设3 内存中一次可以同时存放 5块Student元组 1块SC元组和若干块连接结果元组一个内存块装元组 10个Student元组 或100个SC元组 或10个连接后的元组假设4 读写速度 20块 秒 Sname Studnet Sno SC Sno SC Cno 2 Studnet SC Student SC第一遍 读5块Student 按块读SC读100块 读取块数 5 100要处理20遍读取总块数 20 5 100 2100读数据时间 2100 20 105秒中间结果大小 1000 10000 107写中间结果时间107 10 20 50000秒 读数据时间 50000秒 结果50个元组 时间忽略 总时间 105 50000 50000秒 100105秒 27 8小时 Sname SC Cno 2