您好,欢迎访问三七文档
当前位置:首页 > 电子/通信 > 数据通信与网络 > 信息科学与技术学院计算机系
AnIntroductiontoDatabaseSystem信息科学与技术学院计算机系数据库系统概论AnIntroductiontoDatabaseSystem第九章关系查询处理和查询优化AnIntroductiontoDatabaseSystem第九章关系系统及其查询优化9.1关系数据库系统的查询处理9.2关系数据库系统的查询优化9.3代数优化9.4物理优化9.3小结AnIntroductiontoDatabaseSystem9.1关系数据库系统的查询处理9.1.1查询处理步骤9.1.2实现查询操作的算法示例AnIntroductiontoDatabaseSystem9.1.1查询处理步骤查询分析词法/语法/语义分析符号名转换查询检查语义检查安全性检查完整性检查查询优化代数优化物理优化查询执行查询计划生成代码生成AnIntroductiontoDatabaseSystem9.1关系数据库系统的查询处理9.1.1查询处理步骤9.1.2实现查询操作的算法示例AnIntroductiontoDatabaseSystem9.1.2实现查询操作的算法示例一选择操作的实现二连接操作的实现AnIntroductiontoDatabaseSystem9.1.2实现查询操作的算法示例一选择操作的实现1、简单的全表扫描方法2、索引(或散列)扫描方法[例1]Select*fromstudentwhere条件表达式表达式情况:C1:无条件;C2:Sno=‘200215121’;C3:Sage20;C4:Sdept=‘CS’ANDSage20;AnIntroductiontoDatabaseSystem9.1.2实现查询操作的算法示例1、简单的全表扫描方法AnIntroductiontoDatabaseSystem9.1.2实现查询操作的算法示例2、索引(或散列)扫描方法[例1-C2]Sno上有索引[例1-C3]Sage上有B+树索引[例1-C4]Sdept和Sage上都有索引AnIntroductiontoDatabaseSystem9.1.2实现查询操作的算法示例二连接操作的实现1、嵌套循环方法(nestedloop)2、排序-合并方法(sort-mergejoin)3、索引连接(IndexJoin)方法4、HashJoin方法[例2]Select*fromstudent,scwherestudent.sno=sc.sno;AnIntroductiontoDatabaseSystem9.1.2实现查询操作的算法示例1、嵌套循环方法AnIntroductiontoDatabaseSystem9.1.2实现查询操作的算法示例2、排序合并方法20021512120021512220021512320021512420021512122002151213200215121120021512222002151223200215123520021512332002151231SNOSNOCNOAnIntroductiontoDatabaseSystem9.1.2实现查询操作的算法示例3、索引连接方法20021512320021512220021512120021512420021512122002151233200215123120021512122002151223200215121520021512232002151231SNOSNOCNO索引表AnIntroductiontoDatabaseSystem9.1.2实现查询操作的算法示例3、HashJoin方法20021512320021512220021512120021512412002151233200215122520021512132002151222200215121120021512332002151232200215121SNOSNOCNOAnIntroductiontoDatabaseSystem第四章关系系统及其查询优化9.1关系数据库系统的查询处理9.2关系数据库系统的查询优化9.3代数优化9.4物理优化9.3小结AnIntroductiontoDatabaseSystem9.2关系数据库系统的查询优化查询优化的必要性查询优化极大地影响RDBMS的性能。查询优化的可能性关系数据语言的级别很高,使DBMS可以从关系表达式中分析查询语义。AnIntroductiontoDatabaseSystem9.2.1查询优化概述关系系统的查询优化既是RDBMS的关键技术又是关系系统的优点所在;大大减轻了用户的负担。AnIntroductiontoDatabaseSystem9.2.1查询优化概述由DBMS进行查询优化的好处用户不必考虑如何最好地表达查询以获得较好的效率系统可以比用户程序的优化做得更好(1)优化器可以从数据字典中获取许多统计信息,而用户程序则难以获得这些信息AnIntroductiontoDatabaseSystem由DBMS进行查询优化的好处(2)如果数据库的物理统计信息改变了,系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序,而重写程序在实际应用中往往是不太可能的。(3)优化器可以考虑数百种不同的执行计划,而程序员一般只能考虑有限的几种可能性。(4)优化器中包括了很多复杂的优化技术AnIntroductiontoDatabaseSystem9.2.1查询优化概述集中式数据库查询开销:I/O+CPU+内存分布式数据库查询开销:I/O+CPU+内存+通信代价查询优化的总目标选择有效策略,求得给定关系表达式的值,使得查询代价较小AnIntroductiontoDatabaseSystem9.2.2一个实例例3:求选修了课程C2的学生姓名SELECTStudent.SnameFROMStudent,SCWHEREStudent.Sno=SC.SnoANDSC.Cno='2';AnIntroductiontoDatabaseSystem9.2.2一个实例(续)假设1:外存:Student:1000条,SC:10000条,选修2号课程:50条假设2:一个内存块装元组:10个Student,或100个SC,内存中一次可以存放:5块Student元组,1块SC元组和若干块连接结果元组假设3:读写速度:20块/秒假设4:连接方法:基于数据块的嵌套循环法AnIntroductiontoDatabaseSystem9.2.2一个实例(续)三种策略:Q1=ПSname(бStudent.Sno=SC.Sno∧SC.Cno='2'(Student×SC))Q2=ПSname(бSC.Cno='2'(StudentSC))Q2=ПSname(StudentбSC.Cno='2'(SC))AnIntroductiontoDatabaseSystem执行策略1Q1=П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秒AnIntroductiontoDatabaseSystem不同的执行策略,考虑I/O时间中间结果大小=1000*10000=107(1千万条元组)写中间结果时间=10000000/10/20=50000秒②б读数据时间=50000秒③П总时间=105+50000+50000秒=100105秒=27.8小时AnIntroductiontoDatabaseSystem9.2.2一个实例(续)策略2.Q2=ПSname(бSC.Cno='2'(StudentSC))①读取总块数=2100块读数据时间=2100/20=105秒中间结果大小=10000(减少1000倍)写中间结果时间=10000/10/20=50秒②б读数据时间=50秒③П总时间=105+50+50秒=205秒=3.4分AnIntroductiontoDatabaseSystem9.2.2一个实例(续)策略3.Q3=ПSname(StudentбSC.Cno='2'(SC))①б读SC表总块数=10000/100=100块读数据时间=100/20=5秒中间结果大小=50条不必写入外存②读Student表总块数=1000/10=100块读数据时间=100/20=5秒③П总时间=5+5秒=10秒AnIntroductiontoDatabaseSystem9.2.2一个实例(续)策略4.Q2=ПSname(StudentбSC.Cno='2'(SC))假设SC表在Cno上有索引,Student表在Sno上有索引①б读SC表索引=读SC表总块数=50/1001块读数据时间中间结果大小=50条不必写入外存AnIntroductiontoDatabaseSystem9.2.2一个实例(续)②读Student表索引=读Student表总块数=50/10=5块读数据时间③П总时间10秒AnIntroductiontoDatabaseSystem第九章关系系统及其查询优化9.1关系数据库系统的查询处理9.2关系数据库系统的查询优化9.3代数优化9.4物理优化9.3小结AnIntroductiontoDatabaseSystem9.3代数优化9.3.1关系代数表达式等价变换规则9.3.2查询树的启发式优化AnIntroductiontoDatabaseSystem9.3.1关系代数等价变换规则关系代数表达式等价指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的上面的优化策略大部分都涉及到代数表达式的变换AnIntroductiontoDatabaseSystem9.3.1关系代数等价变换规则设E1、E2等是关系代数表达式,F是条件表达式l.连接、笛卡尔积交换律E1×E2≡E2×E1E1E2≡E2E1E1FE2≡E2FE1AnIntroductiontoDatabaseSystem9.3.1关系代数等价变换规则2.连接、笛卡尔积的结合律(E1×E2)×E3≡E1×(E2×E3)(E1E2)E3≡E1(E2E3)(E1E2)E3≡E1(E2E3)FFFFAnIntroductiontoDatabaseSystem9.3.1关系代数等价变换规则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}的子集AnIntroductiontoDatabaseSystem9.3.1关系代数等价变换规则4.选择的串接定律бF1(бF2(E))≡бF1∧F2(E)选择的串接律说明选择条件可以合并这样一次就可检查全部条件。AnIntroductiontoDatabaseSystem9.3.1关系代数等价变换规则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)))AnIntroductiontoDatabaseSystem9.3.1关系代数等价变换规则6.选择与笛卡尔积的交换律(1)假设:F中涉及的属性都是E1中的属性бF(E1×E2)≡бF(E1)×E2(2)假设:F=F1∧F2,并且F1只涉及E1中的属性,F2只涉及E2中的属性则由上面的等价变换规则1,4,6可推出:
本文标题:信息科学与技术学院计算机系
链接地址:https://www.777doc.com/doc-3612400 .html