数据库系统概论.ppt

第九章关系系统及其查询优化苟仕蓉教学内容关系数据库系统的查询处理关系数据库系统的查询优化代数优化物理优化教学目标通过本章的学习，要求学生了解查询优化的必要性掌握查询优化的一般规则9.1关系数据库系统的查询处理查询处理的任务查询处理的步骤查询分析查询检查查询优化代数优化物理优化查询执行9.2关系数据库系统的查询优化例：求选修了2号课程的学生姓名SelectStudent.SnameFromStudent,SCWhereStudent.Sno=SC.SnoandSC.Cno=‘2’;假设有学生记录1000个；选课记录10000个；其中选修2号课程的选课记录50个计算广义笛卡尔积的代价假设：一个内存块可容纳10个student元组或100个SC表元组，5个内存块提供给student使用，1个内存块提供给SC使用需读取的总块数为： 1000/10+1000÷(10×5)×（10000÷100）=2100每秒读写20个内存块，总时间为： 2100÷20=105秒中间结果(10个/内存块)写入外存时间： (1000×10000)÷10÷20=5×104秒作选择操作中间结果(10个/内存块)读入内存时间： (1000×10000)÷10÷20=5×104秒选择结果为50个元组，全部存放在内存中，无写出代价投影运算全部在内存中进行，无I/O代价总代价105秒+5×104+5×104≈105秒假设有学生记录1000个；选课记录10000个；其中选修2号课程的选课记录50个自然连接假设：一个内存快可容纳10个student元组或100个SC表元组，5个内存块提供给student使用，1个内存块提供给SC使用需读取的总块数为： 1000/10+1000÷(10×5)×10000÷100=2100每秒读写20个内存块，总时间为： 2100÷20=105秒中间结果(10个/内存块)写入外存时间： (10000)÷10÷20=50秒作选择操作中间结果(10个/内存块)读入内存时间： (10000)÷10÷20=50秒选择结果为50个元组，全部存放在内存中，无写出代价投影运算全部在内存中进行，无I/O代价总代价105秒+50+50=205秒假设有学生记录1000个；选课记录10000个；其中选修2号课程的选课记录50个作选择操作假设：一个内存快可容纳10个student元组或100个SC表元组，5个内存块提供给student使用，1个内存块提供给SC使用需读取的总块数为： 10000÷100=100个每秒读写20个内存块，总时间为： 100÷20=5秒选择结果为50个元组，全部存放在内存中，无写出代价进行自然连接Student表(10个/内存块)读入内存时间： 1000÷10÷20=5秒自然连接结果为50个元组，全部存放在内存中，无写出代价投影运算全部在内存中进行，无I/O代价总代价5秒+5秒=10秒再如果： SC表在Cno字段上有索引 Student表在Sno字段上有索引9.3代数优化代数优化概述关系代数表达式等价变换规则查询树的启发式优化9.3.1关系代数等价变换规则连接、笛卡尔积交换律连接、笛卡尔积结合律9.3.1关系代数等价变换规则投影的串接定律选择的串接定律9.3.1关系代数等价变换规则选择与笛卡尔积的交换律9.3.2查询优化的一般准则选择运算尽可能先做在执行连接前对关系作适当的预处理(建立适当的索引或排序)索引连接如Student∞SC若SC表在Sno上有索引排序合并连接如Student∞SC若Student和SC表都按Sno属性排序9.3.2代数优化示例把查询转化成某种内部表示(关系代数语法树)Select子句对应投影From子句对应笛卡尔积Where子句对应选择操作9.3.2代数优化示例利用优化算法，把原始语法树转换成优化的形式9.3.2代数优化示例选择低层的存取路径生成查询计划，选择代价最小的9.4物理优化物理优化概述可使用的方法基于规则的启发式优化基于代价估算的优化两者结合的优化方法*教学重难点关系数据库系统的查询处理关系数据库系统的查询优化代数优化物理优化①②③执行代价=I/O代价+CPU代价+内存代价计算广义笛卡尔积作选择操作作投影①②③执行代价=I/O代价+CPU代价+内存代价自然连接作选择操作作投影①②③执行代价=I/