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

1 数据库系统概论AnIntroductiontoDatabaseSystem第九章关系查询处理和查询优化 2 第九章关系查询处理和查询优化 9 1关系数据库系统的查询处理9 2关系数据库系统的查询优化9 3代数优化9 4物理优化9 5小结 3 9 1关系数据库系统的查询处理 9 1 1查询处理的步骤查询分析查询检查查询优化查询执行 4 9 1 2实现查询操作的算法举例 一 选择操作的实现例1 Select fromstudentwhere的几种情况 C1 无条件 C2 Sno 200215121 C3 Sage 20 C4 Sdept CS ANDSage 20 5 选择操作的实现方法 1简单的全表扫描方法对查询的基本表顺序扫描 逐一检查每个元组是否满足条件 把满足条件的元组作为结果输出 小表有效 大表顺序扫描效率低 6 索引扫描方法若选择条件中的属性上有索引 B 树索引或Hash索引 可以用索引扫描方法 通过索引先找到满足条件的元组主码或元组指针 再通过元组指针直接在查询的基本表中找到元组 选择操作的实现方法 7 B 树索引 25 351 516879 31530 798493 68697176 515465 3041 152025 37 25 8 索引扫描方法的实现 C2 若Sno上有索引 则通过索引查找到该Sno元组的指针 从而检索到该学生 C3 若Sage上有B 树索引 则可以B 树索引找到该索引项 从而根据B 树的顺序集得到该元组的指针 检索到目标元组 C4 若两个条件都有索引 先分别找到满足两个条件的指针 再求交集 从而检索到目标元组 找到某一项的指针 找到满足条件的元组集 在根据另一条件 找到满足条件的元组 9 二 连接操作的实现 例2 SELECT FROMStudent SCWHEREStudent Sno SC Sno 1 嵌套循环方法 nestedloop 对外层循环 Student 的每一个元组 s 检索内层循环 SC 中的每一个元组 sc 并检查这两个元组在连接属性 sno 上是否相等 满足条件则串接后输出 否则知道外层循环表中的元组处理完为止 最耗时的操作 10 用排序 合并连接方法步骤 若连接的表没有排好序 首先对Student表和SC表按连接属性Sno排序 取Student表中第一个Sno 依次扫描SC表中具有相同Sno的元组 把它们连接起来 当扫描到Sno不相同的第一个SC元组时 返回Student表扫描它的下一个元组 再扫描SC表中具有相同Sno的元组 把它们连接起来 重复上述步骤直到Student表扫描完 2 排序 合并方法 sort mergejoin或mergejoin 11 用索引连接方法的步骤 如果原来没有的话 在SC表上建立属性Sno的索引 对Student中每一个元组 由Sno值通过SC的索引查找相应的SC元组 把这些SC元组和Student元组连接起来 循环执行2 3 直到Student表中的元组处理完为止 4 HashJoin方法 3 索引连接 indexjoin 方法 12 9 2关系数据库系统的查询优化 9 2 1查询优化概述9 2 2实例 13 9 2 1查询优化概述 关系系统的查询优化是RDBMS实现的关键技术 是关系系统的优点所在 查询优化的可能性关系数据语言的级别很高 使DBMS可以从关系表达式中分析查询语义 从而提供了执行查询优化的可能性 14 DBMS进行查询优化的便利条件 用户不必考虑如何最好地表达查询以获得较好的效率系统可以比用户程序的优化做得更好 1 优化器可以从数据字典中获取许多统计信息 而用户程序则难以获得这些信息 15 由DBMS进行查询优化的好处 2 如果数据库的物理统计信息改变了 系统可以自动对查询重新优化以选择相适应的执行计划 在非关系系统中必须重写程序 而重写程序在实际应用中往往是不太可能的 3 优化器可以考虑数百种不同的执行计划 而程序员一般只能考虑有限的几种可能性 4 优化器中包括了很多复杂的优化技术 16 查询优化目标 查询优化的总目标选择有效策略 求得给定关系表达式的值 使得查询代价最小 实际系统的查询优化步骤1 将查询转换成某种内部表示 通常是语法树2 根据一定的等价变换规则把语法树转换成标准 优化 形式 17 实际系统的查询优化步骤 3 选择低层的操作算法对于语法树中的每一个操作计算各种执行算法的执行代价选择代价小的执行算法4 生成查询计划 查询执行方案 查询计划是由一系列内部操作组成的 18 代价模型 集中式数据库单用户系统总代价 I O代价 CPU代价多用户系统总代价 I O代价 CPU代价 内存代价 开销 分布式数据库总代价 I O代价 CPU代价 内存代价 通信代价 19 9 2 2查询优化的必要性 举例 例 求选修了2号课程的学生姓名SELECTStudent SnameFROMStudent SCWHEREStudent Sno SC SnoANDSC Cno 2 1 sname Student Sno SC Sno SC Cno 2 Student SC 2 Sname SC Cno 2 StudentSC 3 name Student SC Cno 2 SC 20 查询优化的必要性 续 假设1 外存 Student 1000条 SC 10000条 其中选修2号课程 50条假设2 一个内存块装元组 10个Student元组 或100个SC元组 内存中一次可以存放 5块Student元组 1块SC元组和若干块连接结果元组假设3 读写速度 20块 秒假设4 连接方法 基于数据块的嵌套循环法 21 Student SC读取总块数 读Student表块数 读SC表遍数 每遍块数 1000 10 1000 10 5 10000 100 100 20 100 2100读数据时间 2100 20 105秒 查询优化的必要性 续 1 1 sname Student Sno SC Sno SC Cno 2 Student SC 22 中间结果大小 1000 10000 107 1千万条元组 写中间结果时间 10000000 10 20 50000秒 读数据时间 50000秒 总时间 105 50000 50000秒 100105秒 27 8小时 23 查询优化的必要性 续 2 2 name SC Cno 2 StudentSC 读取总块数 2100块读数据时间 2100 20 105秒中间结果大小 10000 减少1000倍 写中间结果时间 10000 10 20 50秒 读数据时间 50秒 总时间 105 50 50秒 205秒 3 4分 24 查询优化的必要性 续 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秒 25 查询优化的必要性 续 4 3 name Student SC Cno 2 SC 假设SC表在Cno上有索引 Student表在Sno上有索引 读SC表索引 读SC表总块数 50 100 1块读数据时间中间结果大小 50条不必写入外存 26 查询优化的必要性 续 读Student表索引 读Student表总块数 50 10 5块读数据时间 总时间 10秒 27 9 3代数优化 9 3 1关系代数表达式等价变换规则9 3 2查询树的启发式优化 28 9 3 1关系代数表达式等价变换规则 关系代数表达式等价指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的上面的优化策略大部分都涉及到代数表达式的变换 29 常用的等价变换规则 设E1 E2等是关系代数表达式 F是条件表达式l 连接 笛卡尔积交换律E1 E2 E2 E1E1E2 E2E1E1FE2 E2FE1 30 关系代数等价变换规则 续 2 连接 笛卡尔积的结合律 E1 E2 E3 E1 E2 E3 E1E2 E3 E1 E2E3 E1E2 E3 E1 E2E3 F1F2F1F2 31 关系代数等价变换规则 续 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 的子集 32 关系代数等价变换规则 续 4 选择的串接定律 F1 F2 E F1 F2 E 选择的串接律说明选择条件可以合并这样一次就可检查全部条件 33 关系代数等价变换规则 续 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 34 关系代数等价变换规则 续 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 35 关系代数等价变换规则 续 3 假设 F F1 F2 F1只涉及E1中的属性 F2涉及E1和E2两者的属性 F E1 E2 F2 F1 E1 E2 它使部分选择在笛卡尔积前先做 36 关系代数等价变换规则 续 7 选择与并的分配率假设 E E1 E2 E1 E2有相同的属性名 F E1 E2 F E1 F E2 8 选择与差运算的分配率假设 E1与E2有相同的属性名 F E1 E2 F E1 F E2 37 关系代数等价变换规则 续 9选择对自然连接的分配率 F E1E2 F E1 F E2 F只涉及E1与E2的公共属性 38 关系代数等价变换规则 续 10 投影与笛卡尔积的分配率假设 E1和E2是两个关系表达式 A1 An是E1的属性 B1 Bm是E2的属性 A1 A2 An B1 B2 Bm E1 E2 A1 A2 An E1 B1 B2 Bm E2 39 关系代数等价变换规则 续 11 投影与并的分配率假设 E1和E2有相同的属性名 A1 A2 An E1 E2 A1 A2 An E1 A1 A2 An E2 40 9 3 2查询树的启发式优化 启发式规则 heuristicrules 的代数优化典型的启发式规则 1选择运算应尽可能先做在优化策略中这是最重要 最基本的一条 它常常可使执行时节约几个数量级 因为选择运算一般使计算的中间结果大大变小 41 典型的启发式规则 2把投影运算和选择运算同时进行如有若干投影和选择运算 并且它们都对同一个关系操作 则可以在扫描此关系的同时完戌所有的这些运算以避免重复扫描关系 42 典型的启发式规则 3投影同双目运算结合把投影同其前或其后的双目运算结合起来 没有必要为了去掉某些字段而扫描一遍关系 43 典型的启发式规则 4选择同某些笛卡尔积结合起来构成一个连接运算把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算 连接特别是等值连接运算要比同样关系上的笛卡尔积省很多时间 44 5找出公共子表达式如果重复出现的子表达式的查询结果不是很大的关系 并且从外存中读入这个关系比计算该子表达式的时间少得多 则先计算一次公共子表达式并把结果写入中间文件是合算的 当查询的是视图时 定义视图的表达式就是公共子表达式的情况 典型的启发式规则 45 关系代数表达式的优化算法 输入 一个关系表达式的查询树输出 优化的查询树方法 1 利用规则4将形如变换为 2 对每一选择 利用等价变换规则4 9尽可能将它移到树的叶端 46 优化算法 3 对每一个投影 利用规则3 5 10 11中的一般形式尽可能将它移到树的叶端 4 利用规则3 5将选择和投影的串接合并成单个选择 单个投影或一个选择后跟一个投影 使多个选择或投影能同时进行 或在一次扫描中全部完成 47 优化算法 5 将上述得到的语法树的内节点分组 每一双目运算 和它所有的直接祖先为一组 这些直接祖先是 运算 如果其后代直到叶子全部是单目运算 则将它并入该组 48 举例 例 供应商数据库中有 供应商 零件 项目 供应四个基本表 关系 S Sno Sname Status City P Pno Pname Color Weight J Jno Jname City SPJ Sno Pno Jno Qty 49 举例 用户有一查询语句 检索使用上海供应商生产的红色零件的工程号 1 试写出该查询的关系代数表达式 2 试写出查询优化的关系代数表达式 3 画出该查询初始的关系代数表达式的语法树 4 使用优化算法 对语法树进行优化 并画出优化后的语法树 50 举例 解 1 该查询的关系代数表达式如下 2 查询优化的关系代数表达式如下 3 该查询初始的关系代数表达式的语法树如下图1所示 4 优化后的语法树如图2所示 51 优化前的查询树 关系代数语法树 图1 52 优化后的查询树 图2 53 9 4物理优化 代数优化改变查询语句中操作的次序和组合 不涉及底层的存取路径 物理优化是要选择高效合理的操作算法或存取路径 求得优化的查询计划 达到查询优化的目的 54 物理优化选择的方法 基于规则的启发式优化 大多数情况下都适用基于代价估算的优化 优化器估算不同执行策略的代价 并选出具有最小代价的执行计划两者结合的优化方法 先使用启发式规则 选取若干较优的候选方案 减少代价估算的工作量 然后分别计算这些候选方案的执行代价 较快地选出最终的优化方案 55 9 4 1基于启发式规则的存取路径选择优化 选择操作的启发式规则 使用全表顺序扫描 即使选择列上有索引 小关系 对于选择条件是主码 值的查询 查询结果最多是一个元组 可以选择主码索引 一般情况RDBMS会自动建立主码索引 对于选择条件是非主属性 值的查询 并且选择列上有索引 则要估算查询结果的元组数目 若比例较小 10 则使用索引扫描方法 否则使用全表顺序扫描 56 选择操作的启发式规则 对于选择条件是属性上的非等值查询或者范围查询 并且选择列上有索引 同样要估算查询结果的元组数目 若比例较小 10 可以使用索引扫描方法 否则使用全表顺序扫描 对于用AND连接的合取选择条件 若有涉及这些属性的组合索引 则优先采用组合索引扫描方法 若某些属性上有一般的索引 则可以用 例1 C4 中介绍的索引扫描方法 否则使用全表顺序扫描 对于用OR连接的析取选择条件 一般使用全表顺序扫描 57 连接操作的启发式规则 若两个表都已经按照连接属性排序 则选用排序 合并方法 若一个表在连接属性上有索引 则可以选用索引连接方法 若上面两条规则都不适用 其中一个表较小 则可以选用HASHJoin方法 最后可以选用嵌套循环方法 并选择其中较小的表 即占用块数较小的表 作为外表 58 9 4 2基于代价的优化 启发式规则优化是定性的选择 较粗糙 但实现简单而且优化本身代价较小 适用于解释执行的系统 在编译系统中 一次编译优化 多次执行 查询优化和查询执行分开进行 因此适合用精细复杂的基于代价的优化方法 59 一 统计信息 基于代价的优化方法要计算各种操作算法的执行代