06-第六章关系系统及其优化-new.ppt
《06-第六章关系系统及其优化-new.ppt》由会员分享,可在线阅读,更多相关《06-第六章关系系统及其优化-new.ppt(51页珍藏版)》请在三一文库上搜索。
1、第六章: 关系系统及其查询优化,关系系统的定义和分类 查询处理 关系系统中的查询优化,关系系统的定义,关系系统: 支持关系数据模型的数据库管理系统(粗略) 关系系统(确切定义): 一个系统可以定义为一个关系系统, 当且仅当它: 支持关系数据库 支持选择、投影和连接运算(自然连接), 对这些运算不要求定义任何物理存取路径,关系系统的分类,许多关系系统的产品 按E.F.Codd的思想将关系系统分为: 表式系统(a) 最小关系系统(b) 关系完备的系统(c) 全关系系统(d),S,M,I,S,M,I,S,M,I,S,M,I,a,b,c,d,S: Structure I: Integrity M: M
2、anipulation,关系数据模型,集合级,关系系统的查询处理,查询处理的步骤:,查询,关系代数 表达式,执行计划,查询结果输出,数据,基于数据的统计分析,优 化 器,分析器 & 翻译器,评 价 引 擎,DBMS,为什么需要查询优化?,一个查询实例: 求选修2号课程的学生姓名 SQL表示: select Sname from Students, SC where Students.Sno=SC.Sno and Cno=2; 关系代数表示: Q1= sname(Students.Sno=SC.Sno and Cno=2(StudentsSC) Q2= sname(Cno=2(Students
3、SC) Q3= sname( Students Cno=2(SC),代价计算 Q1代价计算(仅考虑I/O代价) 计算广义笛卡尔积代价 假定: 在内存中, 存放5块Students元组和一块SC元组, 一块可以装10个Students元组或100个SC元组. 假定: Students有1000个元组,SC有10000个元组, 其中选2号课程的有50个元组 数据只有读到内存才能进行连接,Q1 = sname(Students.Sno=SC.Sno and Cno=2(StudentsSC),10,100,SC,Students,5块,通过读取块数计算I/O代价 读取块数计算方法: Students
4、 1000个元组 SC 10000个元组 读取总块数: 若每秒读写20块, 则花费:,Q1 = sname(Students.Sno=SC.Sno and Cno=2(StudentsSC),Student 块数,SC 读入内存的次数,SC块数,10,100,SC,Students,5块,条件:Students 1000个元组, SC 10000个元组 迪卡尔集后的元组个数为: 103 104=107 连接后的中间结果内存放不下, 需暂时写到外存 若每块可装10个完成迪卡尔集后的元组, 则写这些元组需: (107 /10)/20=5 104s 选择操作: 读回需5 104s, 假设选择后剩50
5、个元组,均可放在内存 投影操作: 只需CPU时间 查询共花费: 105+2 5 104 105 s 28小时,Q1 = sname(Students.Sno=SC.Sno and Cno=2(StudentsSC),每秒读20块,Q2= sname(Cno=2(Students SC),Q2代价计算(仅考虑I/O代价) 计算自然连接代价 也要把数据读到内存进行连接, 但连接结果比笛卡尔积要小得多 读取块数依然为: 花费为2100/20105s 假设连接结果大小为104个元组, 写到外存需: (104 /10)/20=50s,每秒读20块,Q2= sname(Cno=2(Students SC)
6、 Q3= sname( Students Cno=2(SC),读取自然连接结果, 执行选择运算, 需50s, 选择结果均可放在内存 投影运算:只需CPU时间 总花费为: 105+50+50=205s 3.4分钟 Q3代价计算(仅考虑I/O代价) 计算对SC做选择运算的代价 需读SC到内存进行选择运算 读SC块数为: 10000/100=100 花费为: 100/20=5s 选择结果为50个SC元组, 均可放在内存,Q3= sname( Students Cno=2(SC),计算和Students自然连接的 代价 需读Students到内存进行连 接运算 读Students块数为: 1000/1
7、0=100 花费为: 100/20=5s 连接结果为50个元组, 均可放在内存 投影运算:只需CPU时间 总花费: 5+5=10s,10,50,SC,Students,5块,关系系统的查询优化,关系系统的查询优化由系统完成, 而不是由用户完成 优化器可以从数据字典获取许多统计信息 如果数据库的物理统计信息改变了,优化器可以对查询进行重新优化以选择适应的执行计划 优化器可以考虑数百种不同的执行计划 优化器包括了许多复杂的技术 优化目标: 寻求最优的执行计划, 使查询执行开销尽量小,查询执行开销主要包括: 总代价 = I/O代价 + CPU代价 多用户数据库执行开销: 总代价 = I/O代价 +
8、CPU代价 + 内存代价 查询优化的途径 代数优化 物理优化,关系系统的查询优化,代数优化,查询优化的一般步骤 将查询转化成内部表示-语法树 根据等价变化规则, 将语法树转化成优化形式 选择底层操作算法 生成查询计划,代数优化,查询优化的一般准则(启发式规则): 下面的优化策略一般能提高查询效率, 但不一定是最优的 选择和投影运算尽可能先做, 降低中间结果大小 把投影运算和选择运算同时进行 sno (cno=2(SC) 把投影和其前或后的双目运算结合起来 Cname(Course SC) 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算 Students.Sno=SC.Sno an
9、d Cno=2(StudentsSC) 找出公共子表达式,代数优化,关系代数等价变换规则: 给定 sname(Students.Sno=SC.Sno and Cno=2(StudentsSC) 如何将上述提到的运算先做, 即得到: sname( Students Cno=2(SC) 规则1: 连接、笛卡尔积的交换律 E1 E2 E2 E1 E1 E2= E2 E1 E1 E2= E2 E1 E: 关系代数表达式 F: 连接条件,代数优化,规则2: 连接、笛卡尔积的结合律 (E1 E2) E3 = E1 (E2 E3) (E1 E2) E3 E1 (E2 E3) (E1 E2) E3 E1 (E
10、2 E3) 规则3: 投影的串接定律 A1,A2,.,An( B1,B2,.,Bn (E) A1,A2,.,An(E),F1,F2,F1,F2,代数优化,规则4: 选择的串接定律 F1(F2(E) F1F2(E) 规则5: 选择和投影的交换律 F(A1,A2,.,An(E) = A1,A2,.,An(F(E) 特殊情况 A1,A2,.,An(F(E) A1,A2,.,An(F(A1,A2,.,An, B1,B2,.,Bm (E),代数优化,规则6: 选择与笛卡尔积的交换律 F(E1 E2) F(E1) E2 F仅和E1有关 F(E1 E2) F1(E1) F2( E2 ) F= F1F2 F(
11、E1 E2) F2(F1(E1)E2 ) F1-E1 F2-E1E2 规则7: 选择与并的分配律 F(E1 E2) F(E1) F(E2),代数优化,规则8: 选择与差的分配律 F(E1- E2) F(E1)- F(E2) 规则9: 选择对自然连接的分配律 F(E1 E2) F(E1) F(E2),代数优化,规则10: 投影与笛卡尔积的分配律 A1,A2,.,An, B1,B2,.,Bm(E1 E2) A1,A2,.,An(E1) B1,B2,.,Bm(E2) 规则11: 投影与并的分配律 A1,A2,.,An (E1 E2) A1,A2,.,An(E1) A1,A2,.,An(E2),代数优
12、化,关系代数表达式的优化算法: 应用关系代数等价变换规则来优化关系代数表达式, 使优化后的表达式能遵循查询优化的一般准则, 在语法树上进行优化,代数优化,关系代数表达式的优化算法 输入: 语法树 输出: 计算关系代数表达式的程序 1 利用规则4把形如F1F2Fn(E) 变换成 F1(F2( (Fn(E).) 2 对每一个选择, 利用规则49尽可能移到树的叶端 3 对于每个投影, 利用规则3, 5, 10, 11尽可能移到树的叶端 4 利用规则35把选择和投影的串接合并成单个选择, 单个投影, 或一个选择后跟一个投影,代数优化,5 把处理后的语法树内节点分组: 每一双目运算(, ,)和它的所有直
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 06 第六 关系 系统 及其 优化 new
链接地址:https://www.31doc.com/p-3401096.html