第九章 关系查询处理和查询优化.ppt

AnIntroductiontoDatabaseSystem 上海第二工业大学计算机与信息学院 数据库系统概论AnIntroductiontoDatabaseSystem第九章关系查询处理和查询优化 AnIntroductiontoDatabaseSystem 第九章关系查询处理和查询优化 9 1关系数据库的查询处理9 2关系数据库系统的查询优化9 3代数优化9 4物理优化 AnIntroductiontoDatabaseSystem 9 1关系数据库的查询处理 9 1 1查询处理的步骤查询分析 对查询语句进行语法和词法分析查询检查 检查语义 语句中使用的对象的存在性和有效性用户权限和和完整性检查检查通过后 把查询语句转换成等价的关系代数表达式 查询树即语法分析树 AnIntroductiontoDatabaseSystem 语法分析树 AnIntroductiontoDatabaseSystem 查询优化 选择一个高效的查询处理策略 方法有代数优化 物理优化 选择的依据有基于规则 基于代价或基于语义执行查询 依据优化器得到的策略生成查询计划 由代码生成器生成可执行代码 AnIntroductiontoDatabaseSystem 9 1 2实现查询操作的算法示例 1 选择操作的常用算法全表扫描 选出符合条件的元组使用索引可快速获取符合选择条件的元组指针 如sage 20或sage 20 组合条件如 sage 20andsdept CS 方法1 分别选出符合sage 20条件的元组指针和符合sdept CS 条件的元组指针 然后求它们的交集方法2 先选出符合sage 20条件的元组指针 然后对选出的元组判断是否符合sdept CS 条件 第一种方法在sage和sdept上均有索引的情况下比较有效 第二种方法应该优先选出选择条件中有索引的元组 AnIntroductiontoDatabaseSystem 2 连接操作的常用算法 假定为等值连接 Selecta sno a sname o b gradefromstudenta scbwherea sno b sno连接的总体思路 扫描student 对每一元组的sno 扫描grade的sno 把相同值的元组和student对应元组进行连接后输出 AnIntroductiontoDatabaseSystem 循环嵌套方法 嵌套扫描两个表 总循环次数为两个元组个数的乘积 排序 合并方法 根据两个表的sno进行排序 两个循环均不必进行全表扫描 效率大大提高 索引连接方法 对sc关于sno建立索引 内层循环中由于sc建立的索引 所以不必全表扫描 AnIntroductiontoDatabaseSystem Hashjoin方法 适用大表和小表的连接1依据Hash函数把小表数据放入内存 可保留少量数据在临时表空间中 小表数据的一次扫描 2每读取大表的一条记录 大表数据的一次扫描 就和小表中内存中的数据进行比较 有了hash函数 比较就不需要扫描小表 如果符合 则立即输出数据 而如果大表的数据与小表中临时表空间的数据相符合 先不输出 而等大表的所有数据都读取完毕 才一起输出 减少读取硬盘的次数 3 HashJoin方法只需要对两个表进行一次扫描 并且极大地降低了读取硬盘的次数 AnIntroductiontoDatabaseSystem 9 2 1查询优化概述 查询效率是衡量RDBMS重要性能指标 RDBMS通过查询优化提升查询效率 关系的结构化查询语言SQL高级别的语义 只需指出做什么而不必给出怎么做 使RDBMS进行查询优化成为可能 RDBMS的查询优化 使用户不必考虑如何最好地表达查询以获得较好的效率 AnIntroductiontoDatabaseSystem 系统进行优化较用户优化的优势 优化器可以从数据字典中获取许多统计信息 而用户程序则难以获得这些信息 如果数据库的物理统计信息改变了 系统可以自动对查询重新优化以选择相适应的执行计划而不必重写程序 优化器可以考虑数百种不同的执行计划 而程序员一般只能考虑有限的几种可能性 优化器中包括了很多复杂的优化技术 AnIntroductiontoDatabaseSystem 查询优化目标 查询优化的总目标选择有效策略 求得给定关系代数表达式的值 关系 使得查询代价最小 查询执行策略的代价构成 总代价 I O代价 CPU代价 内存代价 通信代价 AnIntroductiontoDatabaseSystem 9 2 2查询优化的必要性 例 求选修了课程 2的学生姓名SELECTStudent SnameFROMStudent SCWHEREStudent Sno SC SnoANDSC Cno 2 以下考察不同的执行策略对数据读写上需要的时间 AnIntroductiontoDatabaseSystem 查询优化的必要性 续 假设 1 Student 1000条 SC 10000条 选修2号课程 50条2 一个内存块可存放元组 10个Student 或100个SC 内存容量可以存放 5块Student元组 1块SC元组和若干块连接结果元组3 读写速度 20块 秒4 连接方法 基于数据块的嵌套循环法 AnIntroductiontoDatabaseSystem 执行策略1 笛卡尔积 选择 投影 Q1 sname Student Sno SC Sno SC Cno 2 Student SC Student SC 读取总块数 读Student表块数 读SC表遍数 每遍块数 1000 10 1000 10 5 10000 100 100 20 100 2100读数据时间 2100 20 105秒 每次可读student的10X5个元组 然后以块为单位读入全部SC 产生笛卡尔积 AnIntroductiontoDatabaseSystem 中间结果大小 1000 10000 107写中间结果时间 10000000 10 20 50000秒 假设每个内存块可存放10个元组的中间结果 读数据时间 50000秒 总时间 105 50000 50000秒 100105秒 27 8小时 AnIntroductiontoDatabaseSystem 执行策略2 自然连接 选择 投影 2 2 name SC Cno 2 StudentSC 读取总块数 2100块读数据时间 2100 20 105秒中间结果大小 10000 减少1000倍 写中间结果时间 10000 10 20 50秒 读数据时间 50秒 时间 105 50 50秒 205秒 3 4分 AnIntroductiontoDatabaseSystem 执行策略3 选择 自然连接 投影 3 3 Sname Student SC Cno 2 SC 读SC表总块数 10000 100 100块读数据时间 100 20 5秒中间结果大小 50条不必写入外存 读Student表总块数 1000 10 100块读数据时间 100 20 5秒 总时间 5 5秒 10秒 AnIntroductiontoDatabaseSystem 9 3代数优化 关系代数表达式 关系代数运算符经过有限次复合后得到的式子 其值仍为关系 P60 关系代数表达式等价 即关系代数表达式E1和E2中代入相同的关系 其结果相同 记为 E1 E2 AnIntroductiontoDatabaseSystem 9 3 1关系代数表达式等价变换规则 设E1 E2等是关系代数表达式 F是条件表达式l 连接 笛卡尔积交换律E1 E2 E2 E1E1E2 E2E1E1FE2 E2FE1 AnIntroductiontoDatabaseSystem 关系代数等价变换规则 续 2 连接 笛卡尔积的结合律 E1 E2 E3 E1 E2 E3 E1E2 E3 E1 E2E3 E1E2 E3 E1 E2E3 F1F2F1F2 AnIntroductiontoDatabaseSystem 关系代数等价变换规则 续 3 投影的串接定律 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 的子集 AnIntroductiontoDatabaseSystem 关系代数等价变换规则 续 4 选择的串接定律 F1 F2 E F1 F2 E 选择的串接律说明选择条件可以合并这样一次就可检查全部条件 AnIntroductiontoDatabaseSystem 关系代数等价变换规则 续 5 选择与投影的交换律 1 假设 选择条件F只涉及属性A1 An F A1 A2 An E A1 A2 An F E 2 假设 F中有不属于A1 An的属性B1 Bm A1 A2 An F E A1 A2 An F A1 A2 An B1 B2 Bm E AnIntroductiontoDatabaseSystem 关系代数等价变换规则 续 6 选择与笛卡尔积的交换律 1 假设 F中涉及的属性都是E1中的属性 F E1 E2 F E1 E2 2 假设 F F1 F2 并且F1只涉及E1中的属性 F2只涉及E2中的属性 则由上面的等价变换规则1 4 6可推出 F E1 E2 F1 E1 F2 E2 AnIntroductiontoDatabaseSystem 关系代数等价变换规则 续 3 假设 F F1 F2 F1只涉及E1中的属性 F2涉及E1和E2两者的属性 则 F E1 E2 F2 F1 E1 E2 7 选择与并的交换假设 E E1 E2 E1 E2有相同的属性名 F E1 E2 F E1 F E2 8 选择与差运算的交换假设 E1与E2有相同的属性名 F E1 E2 F E1 F E2 AnIntroductiontoDatabaseSystem 关系代数等价变换规则 续 9 投影与笛卡尔积的交换假设 E1和E2是两个关系表达式 A1 An是E1的属性 B1 Bm是E2的属性 A1 A2 An B1 B2 Bm E1 E2 A1 A2 An E1 B1 B2 Bm E2 AnIntroductiontoDatabaseSystem 关系代数等价变换规则 续 l0 投影与并的交换假设 E1和E2有相同的属性名 A1 A2 An E1 E2 A1 A2 An E1 A1 A2 An E2 AnIntroductiontoDatabaseSystem 小结 1 2 连接 笛卡尔积的交换律 结合律3 合并或分解投影运算4 合并或分解选择运算5 8 选择运算与其他运算交换5 9 10 投影运算与其他运算交换 AnIntroductiontoDatabaseSystem 9 3 2关系代数的启发式的优化算法 选择运算应尽可能先做 选择运算减小了中间关系中元组数量在执行连接操作前对关系适当进行预处理按连接属性排序在连接属性上建立索引投影运算和选择运算同时做 在扫描关系时同时进行投影运算和选择运算 避免重复扫描关系将投影运算与其前面或后面的双目运算 关系代数的运算符除投影和选择外均为双目运算符 一起做 AnIntroductiontoDatabaseSystem 某些选择运算同它前面要执行的笛卡尔积结合起来成为连接运算 连接运算比产生笛卡尔后进行选择运算要快的多提取公共子表达式 可把满足公共子表达式的关系 不太大的情况下 读入内存以提高查询效率 AnIntroductiontoDatabaseSystem 遵循启发式规则 运用等价变换规则优化关系表达式的算法 算法 关系代数表达式的优化算法输入 依据一个关系表达式的查询树 算法输出 优化的查询树方法 1 分解选择运算利用规则4把形如 F1 F2 Fn E 变换为 F1 F2 Fn E 为 2 做准备 AnIntroductiontoDatabaseSystem 关系代数表达式的优化算法 续 2 对每一个选择运算 利用规则4 8尽可能把它移到树的叶端 选择优先 3 对每一个投影运算 利用规则3 5 l0 11中的一般形式尽可能把它移向树的叶端 投影优先 选择和投影运算均能减少中间结果 具体哪个更优先 取决于具体关系中行和列哪个数据量更大 AnIntroductiontoDatabaseSystem 4 利用等价变化3 5 合并串接的选择运算成一个选择运算和合并串接的投影运算成一个投影运算 以便能在一次扫描中完成运算 如 A 3 A 5 E A 3 E A1 A1 A2 E A1 E AnIntroductiontoDatabaseSystem 关系代数表达式的优化算法 续 5 对内结点 除叶结点外的所有结点 分组 每一双目运算 和它所有的直接祖先为一组 这些直接祖先是 运算 如下例第1 3组 如果其后代直到叶子全是单目运算 则也将它们并入该组 如下例第1组 当双目运算是笛卡尔积 而且其后的选择不能与它结合为等值连接时 可把这些单目运算单独分为一组 如下例中注释部分 每组结点对应计算程序中的一步 各步程序的顺序可任意 但任何一组的计算必须在它的父代组之前计算 如下例中第1和第2组结果必须在第3组计算之间产生 AnIntroductiontoDatabaseSystem 分组实例 查询男同学选课学分大于4分的姓名和课程名 AnIntroductiontoDatabaseSystem 9 4物理优化 物理优化指存取路径和底层操作算法的选择 主要研究根据查询的不同特点 选择操作和连接操作中对9 1 2中各种算法的选择 有基于启发式 基于代价估算和两者结合的优化方法 AnIntroductiontoDatabaseSystem 基于启发式的优化 一 选择操作的优化规则对于小关系 不论是否有索引 均使用全表扫描 下面规则则对大关系而言 包含主码等值的查询 一定使用主码索引 包含非主属性等值查询 若有关于该非主属性的索引 则估算查询结果的元组数量 与整个元组数量比例大的话 使用全表扫描 否则使用索引扫描 AnIntroductiontoDatabaseSystem 对and连接的条件 若有相应的组合索引 则使用索引扫描 若部分有索引 则先使用索引扫描 选出符合部分条件的元组 在其中再选出符合其他条件的元组 对or连接的条件 一般使用全表扫描 例如关于A B有索引 notA or notB 可优化为not AandB 事实上一些DBMS也会作此优化 前者若使用索引 必须两次全表扫描 而后者一次全表 一次在前一次结果上再扫描 AnIntroductiontoDatabaseSystem 二 连接操作的优化规则 连接属性均排序 使用排序 合并方法仅一个表的连接属性有索引 使用索引连接方法 上述条件均不满足 若一个表较小 则可以选用Hashjoin方法嵌套循环方法不需要任何前提条件 但较小的表的扫描应作为外循环 可减少读块的次数 极端情况下 小表只要读一次 AnIntroductiontoDatabaseSystem 基于代价估算的优化 根据数据库的状态计算各种操作算法的执行代价 选择代价最小的算法 执行代价的计算方法 在数据字典中存放优化器所需要的统计信息 如表的元组数 元组长度 列值个数 最大 最小值 列上是否有索引等 根据以上的统计信息 计算各种算法的代价估值 AnIntroductiontoDatabaseSystem 优化的一般步骤 续 1 把查询转换成某种内部表示例 求选修了课程 2的学生姓名SELECTStudent SnameFROMStudent SCWHEREStudent Sno SC SnoANDSC Cno 2 AnIntroductiontoDatabaseSystem 1 把查询转换成某种内部表示 语法树 AnIntroductiontoDatabas