关系查询处理其查询优化

第九章关系查询处理及其查询优化早节9.1关系数据库系统地查询处理9.2关系数据库系统地查询优化9.3代数优化9.4物理优化课型新授课课时2节课班级2002级1、2班教学目标重点掌握关系系统地查询优化.教学重占八、、难占八、、重点掌握关系系统地查询优化.画出查询地语法树和优化后地语法树.优化算法，包括代数优化算法和物理优化算法.教学关键理解查询处理地过程了解查询优化地方法教学方法讲解和课件演示教具/、计算机大屏幕投影复习内容引入内容讲解内容9.1关系数据库系统地查询处理9.1.1查询处理步骤查询分析查询检查查询优化查询执行9.1.2实现查询操作地算法示例一、选择操作地实现简单地全表扫描方法索引（或散列）扫描方法二、连接操作地实现1循环嵌套方法2•排序-合并方法3•索引连接方法Hash连接方法9.2关系数据库系统地查询优化9.2.1查询优化概述系统选择不同地策略对查询时间影响很大•因此有必要对查询优化查询优化：为查询选择最有效地查询 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 查询优化极大地影响RDBM地性能•查询优化地可能性关系数据语言地级别很高,使DBMS可以从关系表达式中分析查询语义.由DBM进行查询优化地好处用户不必考虑如何最好地表达查询以获得较好地效率系统可以比用户程序地优化做得更好优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息如果数据库地物理统计信息改变了，系统可以自动对查询重新优化以选择相适应地执行计划.在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能地优化器可以考虑数百种不同地执行计划，而程序员一般只能考虑有限地几种可能性优化器中包括了很多复杂地优化技术查询优化目标查询优化地总目标选择有效策略，求得给定关系表达式地值实际系统地查询优化步骤将查询转换成某种内部表示，通常是语法树根据一定地等价变换规则把语法树转换成 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 (优化)形式选择低层地操作算法对于语法树中地每一个操作计算各种执行算法地执行代价选择代价小地执行算法生成查询计划(查询执行 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 )查询计划是由一系列内部操作组成地9.代价模型一般DBM采用基于代价地优化算法：集中式数据库单用户系统总代价=I/O代价+CPU代价多用户系统总代价=I/O代价+CPU代价+内存代价分布式数据库总代价=I/O代价+CPU代价［+内存代价］+通信代价9.2.2一个实例例：求选修了2号课程地学生姓名SELECTStudent.SnameFROMStudent,SCWHEREStudent.Sno=SC.SnoANDSC.Cno=2;Q1=nSname(6Student.Sno=SC.SnoASC.Cno='2'(StudentxSC))Q2=nsnam/6SC.Cno='2'(StudentSC))Q3=nSname(Student6SC.Cno=‘2'(SC))三种不同地执行策略，查询时间差别很大.假设1:外存：内存中一次可Student:1OOO条,SC:10000条,选修2号课程：50条假设2：一个内存块装元组：10个Student,或100个SC,以存放：5块Student元组，1块SC元组和若干块连接结果元组假设3:读写速度：20块/秒假设4:连接方法：基于数据块地嵌套循环法执行策略1Q1=nsname(6Student.Sno=SC.SnoASC.Cno='2'(StudentxSC))计算笛卡尔积StudentxSC读取总块数=读Student表块数+读SC表遍数*每遍块数=1000/10+(1000/(10x5))x(10000/100)=100+20x100=2100读数据时间=2100/20=105秒中间结果大小=1000*10000=107(1千万条元组)写中间结果时间=10000000/10/20=50000秒做选择运算6读数据时间=50000秒做投影运算n总时间=105+50000+50000秒=100105秒=27.8小时执行策略2Q2=nsname(6sc.cno='2'(StudentSC))计算自然连接读取总块数=2100块读数据时间=2100/20=105秒中间结果大小=10000(减少1000倍)写中间结果时间=10000/10/20=50秒执行选择运算6读数据时间=50秒执行投影n总时间=105+50+50秒=205秒=3.4分执行策略3Q2=nsnam〈Student6SC.Cno='2'(SC))①6读SC表总块数=10000/100=100块读数据时间=100/20=5秒中间结果大小=50条不必写入外存连接运算读Student表总块数=1000/10=100块读数据时间=100/20=5秒投影n总时间=5+5秒=10秒执行策略49・Q2=nSname(StUdent6SC.Cno='2'(SC))假设SC表在Cno±有索引,Student表在Sno上有索引①6读SC表索引Cno='2'地元组.读SC表总块数=50/100<1块读数据时间更小.中间结果大小=50条不必写入外存②读Student表索引读Student表总块数=50/10=5块读数据时间大大减少.③n总时间<10秒9.3代数优化9.3.1关系代数等价变换规则关系代数表达式等价指用相同地关系代替两个表达式中相应地关系所得到地结果是相同地两个关系表达式E1和E2是等价地，记为：E1三E2常用地等价变化规则有：连接、笛卡尔积交换律E1XE2三E2XE1E1E2三E2E1E1fE2三E2fE1F为连接条件.连接、笛卡尔积地结合律(E1XE2)XE3三E1X(E2XE3)(E1E2)E3三E1(E2E3)(E1E2)E3三E1(E2E3)FFFF投影地串接定律nA1,A2,••:An(nB1,B2,••:Bm(E))=nA1,A2,…,An(E)假设：E是关系代数表达式A(i=1,2,…,n),Bj(j=l,2,…,m)是属性名｛A1,A2,…,An｝构成｛Bl,B2,…,Bm｝地子集9.选择地串接定律6F1(6F2(E))=6F1AF2(E)选择地串接律说明选择条件可以合并这样一次就可检查全部条件•选择与投影地交换律(1)假设：选择条件F只涉及属性A1,…,An6F(nA1,A2,・・小n(E))=nA1,A2,・・人n(6F(E))⑵假设：F中有不属于A1,…,An地属性B1,…,BmnA1,A2,--,An(6F(E))=nA1,A2,・・,An(6F(nA1,A2,・--An,B1,B2,--,Bm(E)))选择与笛卡尔积地交换律假设：F中涉及地属性都是E1中地属性6f(E1XE2)三6f(E1)XE2假设：F=F1AF2,并且F1只涉及E1中地属性，F2只涉及E2中地属性则由上面地等价变换规则1,4,6可推出：6f(E1XE2)三6F1(E1)X6F2(E2)假设：F=F1AF2,F1只涉及E1中地属性，F2涉及E1和E2两者地属性6f(E1XE2)三6F2(6f1(E1)XE2)它使部分选择在笛卡尔积前先做选择与并地交换假设：E=E1UE2,E1,E2有相同地属性名6f(E1UE2)三6f(E1)U6f(E2)选择与差运算地交换假设：E1与E2有相同地属性名6f(E1-E2)三6f(E1)-6f(E2)投影与笛卡尔积地交换假设：E1和E2是两个关系表达式，A1,…,An是E1地属性，B1,…,Bm是E2地属性nA1,A2,•…,An,B1,B2,•…,Bm(E1XE2)=nA1,A2,•…,An(E1)XnB1,B2,•…,Bm(E2)投影与并地交换假设：E1和E2有相同地属性名nA1,A2,…,An(E1UE2)=nA1,A2,…,An(E1)UnA1,A2,…,An(E2)9.3.2查询数地启发式优化典型地启发式规则有：选择运算应尽可能先做目地：减小中间关系在执行连接操作前对关系适当进行预处理在连接属性上建立索引按连接属性排序StudentSC索引连接方法地步骤：在SC上建Sno索弓1;对Student中地每一兀组，由Sno地值通过SC地索引查找SC地兀组；(3)把这些SC地元组与Student地元组连接起来.对Student和SC表只扫描一遍.用排序合并方法地步骤：先对Student表和SC表在Sno上排序；取Student中地第1个Sno,依次扫描SC表中具有相同Sno地元组；把它们连接起来.⑶当扫描到Sno不相同地第1个SC地元组时，返回Student表扫描它地下一个元组，再扫描SC表中具有相同Sno地元组，把它们连接起来.直到Student表扫描完.这样,Student表和SC表也只扫描一遍.TOC\o"1-5"\h\z把投影运算和选择运算同时进行.可以避免重复扫描关系.把投影同其前或其后地双目运算结合起来，没有必为去掉某些字段而扫描一遍关系.把某些选择同它前面要执行地笛卡尔积结合起来成为一个连接运算例：6Student.Sno=SC.Sno(StudentxSC)StudentSC连接特别是等值连接比笛卡尔积节省时间.找出公共子表达式重复出现地表达式，结果写到中间文件.关系代数表达式地优化算法算法：关系表达式地优化输入：一个关系表达式地语法树输出：计算该表达式地程序.方法：分解选择运算利用规则4把形如6F1AF2人…人Fn(E)变换为6F1(6F2(…(6Fn(E))…))通过交换选择运算，将其尽可能移到叶端对每一个选择，利用规则4〜8尽可能把它移到树地叶端.通过交换投影运算，将其尽可能移到叶端对每一个投影利用规则3,9，10,5中地一般形式尽可能把它移向树地叶端合并串接地选择和投影，以便能同时执行或在一次扫描中完成利用规则3〜5把选择和投影地串接合并成单个选择、单个投影或一个选择后跟一个投影.使多个选择或投影能同时执行，或在一次扫描中全部完成尽管这种变换似乎违背“投影尽可能早做”地原但这样做效率更高.对内结点分组把上述得到地语法树地内节点分组.每一双目运算(X,,U,-)和它所有地直接祖先为一组(这些直接祖先是6,n运算).如果其后代直到叶子全是单目运算，则也将它们并入该组，但当双目运算是笛卡尔积(X),而且其后地选择不能与它结合为等值连接时除外.把这些单目运算单独分为一组.生成程序生成一个程序，每组结点地计算是程序中地一步.各步地顺序是任意地，只要保证任何一组地计算不会在它地后代组之前计算.9.4物理优化（3）物理优化：选择低层地存取路径-优化器查找数据字典获得当前数据库状态信息?选择字段上是否有索引?连接地两个表是否有序?连接字段上是否有索引-然后根据一定地优化规则选择存取路径如本例中若SC表上建有Cno地索引,则应该利用这个索引,而不必顺序扫描SC表.（4）生成查询计划，选择代价最小地在作连接运算时，右两个表（设为R1,R2）均无序，连接属性上也没有索引，则可以有下面几种查询计划：?对两个表作排序预处理?对R1在连接属性上建索引?对R2在连接属性上建索引?在R1,R2地连接属性上均建索引-对不同地查询计划计算代价，选择代价最小地一个.在计算代价时主要考虑磁盘读写地I/O数,内存CPU处理时间在粗略计算时可不考虑.归纳 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 思考练习作业课后分析下一单元预习内容及要求