数据库原理及应用-孙浩军 第7章查询优化

《数据库原理及应用-孙浩军 第7章查询优化》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据库原理及应用ThePrincipleofDatabaseandapplications第七章查询优化第七章查询优化7.1查询优化概述7.2查询优化的一般策略7.3基于关系代数表达式的优化算法7.4分解查询的优化方法7.5连接运算的优化7.6代价估算优化7.1查询优化概述查询优化的必要性查询优化极大地影响RDBMS的性能。查询优化的可能性关系数据语言的级别很高，使DBMS可以从关系表达式中分析查询语义。查性优化必要性例：找出学生张明所选修的课程和成绩T1=πCNO,GR（бS.SNO=SC.SNOS.SN=‘张明’（SSC）)T2=πCNO,GR（бSN=‘张明’（SSC）)T3=πC

2、NO,GR（（бSN=‘张明’（S）SC）查询优化的必要性假设1：外存：S:n1条,SC:n2条假设2：一个内存块装元组:B1个Student,或B2个SC,内存共有K块，存放:K-1块S元组,1块SC元组假设3：连接方法：基于数据块的嵌套循环法查询优化的必要性对于表达式T1，总共要存取的块数是：设n1=n2=10000，B1=B2=10，K=100，则共存取11000块。若每秒存取10块，则需要18分钟查询优化的必要性对于表达式T3，由于先做选择运算，则所存取的块数是：假设各项参数同上，则共存取2000块，这时则大约需要3分钟查询优化查询优化的思想要完成同样的查询任务可能有若干条查询路径，

3、从这些查询路径中选择最佳路径查询优化代数优化物理优化规则优化代价估算优化由DBMS进行查询优化的好处系统可以比用户程序的优化做得更好优化器从数据字典中获取更多的信息如属性值的分布情况，优化器根据这些信息选择有效的执行计划如果物理统计信息丢失，系统可以自动优化查询以选择相适应的执行计划优化器可以考虑数百种不同的执行计划优化器包含了许多复杂的优化技术，这些技术只有最好的程序员才能掌握7.2查询优化的一般策略限制运算尽早进行合并笛卡儿乘积与其后的限制运算为连接运算把投影运算和限制运算同时进行投影运算与其后的其他运算同时进行，以避免重复多次扫描文件事先处理文件存储公用的子表达式7.3基于关系代数表达式

4、的优化算法7.3.1关系代数表达式的等价变换规则关系代数表达式等价指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的上面的优化策略大部分都涉及到代数表达式的变换常用的等价变换规则设E1、E2等是关系代数表达式，F是条件表达式l.连接、笛卡尔积交换律E1×E2≡E2×E1E1E2≡E2E1E1FE2≡E2FE1关系代数等价变换规则2.连接、笛卡尔积的结合律(E1×E2)×E3≡E1×(E2×E3)(E1E2)E3≡E1(E2E3)(E1E2)E3≡E1(E2E3)FFFF关系代数等价变换规则3.投影的串接定律πA1,A2,,An(πB1,B2,,Bm(E))≡πA1,A2,,An

5、(E)假设：1)E是关系代数表达式2)Ai(i=1，2，…，n),Bj(j=l，2，…，m)是属性名3){A1,A2,…,An}构成{Bl，B2，…，Bm}的子集关系代数等价变换规则4.选择的串接定律бF1（бF2（E））≡бF1∧F2(E)5.选择与投影的交换律бF(πA1,A2,,An(E))≡πA1,A2,,An(бF(E))关系代数等价变换规则6.选择与笛卡尔积的交换律(1)假设：F中涉及的属性都是E1中的属性бF(E1×E2)≡бF(E1)×E2(2)假设：F=F1∧F2，并且F1只涉及E1中的属性，F2只涉及E2中的属性则由上面的等价变换规则1，4，6可推出：бF(E1×E2)

6、≡бF1(E1)×бF2(E2)关系代数等价变换规则7.选择与并的交换假设：E=E1∪E2，E1，E2有相同的属性名бF(E1∪E2)≡бF(E1)∪бF(E2)8.选择与差运算的交换假设：E1与E2有相同的属性名бF(E1-E2)≡бF(E1)-бF(E2)关系代数等价变换规则9.投影与笛卡尔积的交换假设：E1和E2是两个关系表达式，A1，…，An是E1的属性，B1，…，Bm是E2的属性πA1,A2,…,An,B1,B2,…,Bm（E1×E2)≡πA1,A2,…,An（E1)×πB1,B2,…,Bm(E2)关系代数等价变换规则l0.投影与并的交换假设：E1和E2有相同的属性名πA1,A2,…

7、,An(E1∪E2)≡πA1,A2,…,An(E1)∪πA1,A2,…,An(E2)7.3.2关系代数表达式的优化步骤【例7.1】设有S(供应商)，P(零件)，SP(供应关系)S(SNUM，SNAME，CITY)P(PNUM，PNAME，WEIGHT，SIZE)SP(SNUM，PNUM，EDEPT，QUAN)设有查询Q:SELECTSNAMEFROMS，P，SPWHERES.SUNM=SP.SNU