数据库系统原理第九章.ppt

第9章 关系查询处理和查询优化 9.1 问题的提出 非过程化，无需显示指明存取路经。 查询操作的多解性：同一个查询操作可能存在多种实现途径（算法不同、存取方法不同）。 代数优化——优化关系代数表达式 物理优化——优化存取路径和底层操作算法，可进一步分为基于规则的（rule based）、基于代价的（cost based）和基于语义的（semantic based）。 基本概念1 查询分析（词法、语法、语义、符号名） 查询树（query tree或者syntax tree） 执行树 执行计划 查询处理步骤（课本264页图9.1） 假定有1000条学生记录，10000条成绩记录，选修了2号课程的记录为50条。设一个物理块能装10条学生记录或100条成绩记录，内存仅提供了7块存储空间，其中5块存放学生记录，1块存放成绩记录，1块用来存放中间结果，磁盘每秒钟读/写20块数据记录。采用嵌套循环实现方式。 第一种情况： Q1＝π姓名（σ学生.学号=成绩.学号∧课号=’2’（学生×成绩）） 1．计算：学生×成绩 读取的总块数为： 1000/10+1000/(10×5)×10000/100=2100(块) 所需时T1=2100/20=105(秒) 笛卡儿集的元组个数为103×104＝107，设每块能装10个元组，则写出这些块所需的时间T2=106/20=5×104(秒) 2．作选择σ 依次读入连接后的结果，选择满足条件的记录，假定内存处理时间忽略不计，则读取中间结果的时间T3与T2相等，即T3=5×104 (秒)，满足条件的记录仅有50条，直接驻留内存。 3．作投影π 将内存中的结果在“姓名”上作投影，得最终结果，因此第一种情况下执行查询的总时间为：T=T1+T2+T3≈105(秒) （约28小时） 第二种情况 Q2＝π姓名（σ课号=’2’ (学生 成绩）） 1．计算自然连接 读取学生表和成绩表的策略不变，总的读取时间仍105秒，但自然连接的结果比第一种情况大大减少，为104条，因此，写出这些元组所需时间为104/10/20＝50（秒）。 2．作选择 读取中间结果所需的时间仍为50（秒），符合条件的记录为50条。 3．作投影 将中间结果投影输出。 第二种情况总的执行时间为：105＋50＋50＝205（秒） 第三种情况 Q3＝π姓名（学生 σ课号=’2’（成绩）） 1．先对成绩表作选择运算，只读取一遍成绩表，存取花费时间为5秒，因满足条件的记录为50条，不必使用中间文件。 2．读取学生表并与内存中的成绩记录作连接，花费时间5秒。 3．输出投影结果。 第三种情况总的执行时间为10秒。 上例充分说明查询优化的必要性，同时给出一些查询优化方法的初步概念（尽量让选择运算在连接运算之前执行）。 基本概念2 全表扫描 索引扫描 嵌套循环连接（nested loop） 排序—合并连接（sort-merge join） Hash连接（hash join） 索引连接（index join） 9.2 查询优化的任务：提高速度（DBMS） 9.3 查询优化的目标 1、减少中间关系规模 2、减少I/O 关系代数表达式的等价变换规则（课本269～271页） SQL查询的代数处理过程（课本272页，图9.3~9.5） 9.4 一般策略（查询树的启发式优化） 1、“选择”尽可能提前执行； 最基本一条，因为“选择”使中间结果变小。 2、索引和排序 特别是对连接运算，连接前先排序或建立索引，提高速度。 例如：对Borrower 与Loans进行自然联接计算时： ① 对loans 按card-no建立索引； ② 对Borrower 每一元组的card-no值： ·通过loans 索引查元组 ·Borrower 元组与相应元组连接起来 ③ 无需反复扫描loans 3、“投影”和“选择”同时进行，（避免多重扫描关系，否则投影选择各扫描一次）。 前提是两种运算对同一关系运算才成立。 4、 （某些）选择与选择前的笛卡尔积结合 扫描得到的元组立即与参与计算的另一元组做匹配条件过滤，将这种笛卡尔积转变为连接运算。 连接运算（特别是等值连接运算）比笛卡尔积快。 5、投影其前后的其它双目运算同时进行，避免重复扫描关系。 6、提取公共子表达式。 ① 公共子表达式计算结果 ② 结果存入外存 ③ 需要时从外存调入内存使用（无需重计算） ④ 前提：外存调入内存的时间大大少于计算公共表达式时间 教材第271页：运用上述代数优化启发式规则的