关系查询优化讨论与小结

1、数据库管理与应用开发专题讨论与小结讨论题目：关系查询优化学 号： 1013011050 姓 名： 李明 专 业： 10信管 成 绩： 一、 关系查询优化的概述 1. 查询优化在关系数据库中的重要性：关系系统的查询优化既是 RDBMS 实现的关键技术又是关系系统的优点所在。它减轻了用户选择存取路径的负担。用户只要提出“干什么”，不必指出“怎么干”。查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化夕做得更好。2.查询优化的可能性和优点：用户不必考虑如何最好地表达查询以获得较好的效率；系统可以比用户做得更好(更“优化” 1优化器可以从数据字典中

2、获取许多统计信息，而用户程序则难以获得这些信息2如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。3优化器可以考虑数百种不同的执行计划，程序员一般只能考虑有限的几种可能性。4优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术；3.查询优化的总目标：选择有效的策略；求得给定关系表达式的值；使得查询代价最小；4.查询优化的一般准则。下面的优化策略一般能提高查询效率：( l ）选择运算应尽可能先做；( 2 ）把投影运算和选择运算

3、同时进行；( 3 ）把投影同其前或其后的双目运算结合起来执行；( 4 ）把某些选择同在它前面要执行的笛卡儿积结合起来成为一个连接运算； ( 5 ）找出公共子表达式； ( 6 ）选取合适的连接算法。5. 查询优化的一般步骤：各个关系系统的优化方法不尽相同，大致的步骤可以归纳如下：( l）把查询转换成某种内部表示，通常用的内部表示是语法树。( 2）把语法树转换成标准（优化）形式。即利用优化算法，把原始的语法树转换成优化的形式。 ( 3）选择低层的存取路径。 ( 4）生成查询计划，选择代价最小的。6.代价模型：一般DBMS采用基于代价的优化算法：集中式数据库单用户系统总代价 = I/O代价 + CP

4、U代价多用户系统总代价 = I/O代价 + CPU代价 + 内存代价分布式数据库总代价 = I/O代价 + CPU代价+ 内存代价 + 通信代价 二、 关系数据库查询优化方法一、 代数优化：1、代数表达式等价变换规则：（1）代数优化包括：（2）连接、笛卡尔积交换律；（3）连接、笛卡尔积结合律；（4）投影的串接定律；（5）选择的串接定律；（6）选择与投影操作的交换律；（7）选择与笛卡尔积操作的交换律；（8）选择与并的分配率；（9）选择与差运算的分配率；（10）选择对自然链的分配率；（11）投影与笛卡尔积的分配率；（12）投影与并的分配率；2.查询树启发式优化，一般规则有：选择运算应尽可能先做(最

5、重要，最根本 目的：减小中间关系投影运算和选择运算同时做目的：避免重复扫描关系将投影运算与其前面或后面的双目运算结合目的：减少扫描关系的遍数在执行连接操作前对关系适当进行预处理按连接属性排序在连接属性上建立索引某些选择运算在其前面执行的笛卡尔积 = 连接运算 例：Student.Sno=SC.Sno (StudentSC Student SC提取公共子表达式;例如：查询小王选修的所有课程。可以用关系代数来表达多种不同的查询方法。S1=cno（S.sno=SC.sno S.sname=“小王”( SSCS2=cno（ S.sname=“小王” ( S SCS3=cno（S.sname=“小王”

6、( S） SC三种查询的结果是完全相同的，但三种查询的具体操作、所占用的内存、所消耗的时间是不相同的。显然：S3 优于 S2 优于 S1查询优化对减少系统开销、提高运行速度是很重要的。3商数据库中有供应商、零件、项目、供应 4个关系（基本表）S(Sno,Sname,Status,City P(Pno,Pname,Color,WeightJ(Jno,Jname,CitySPJ(Sno,Pno,Jno,Qty用户的查询语句是：检索使用上海供应商生产的红色零件的工程号 1）该查询的关系代数表达式为：2）查询优化的关系代数表达式为：二、物理优化物理优化就是要选择高效合理的操作算法或存取路径，球的优化的

7、查询计划，达到查询优化的目标。1. 物理优化可以选择的方法：（1） 基于规则的启发式优化；大多数情况下都适用。（2） 基于代价估算的优化；优化器估算不同执行策略的代价，并选出具有最小代价的执行计划。（3） 两者结合的优化方法。2. 选择操作的启发式规则:对于小关系，使用全表顺序扫描，即使选择列上有索引；对于大关系，启发式规则有：对于选择条件是主码值的查询；查询结果最多是一个元组，可以选择主码索引；一般的RDBMS会自动建立主码索引；对于选择条件是非主属性值的查询，并且选择列上有索引要估算查询结果的元组数目如果比例较小(10%可以使用索引扫描方法否则还是使用全表顺序扫描3、全表扫描算法的代价估算

8、公式如果基本表大小为Bspan块，全表扫描算法的代价 costBp 如果选择条件是码值，则平均代价 cost B/2 4、排序-合并连接算法的代价估算公式如果连接表已经按照连接属性排好序，则costBr+Bs+(Frs*Nr*Ns/Mrs。如果必须对文件排序需要在代价函数中加上排序的代价对于包含B个块的文件排序的代价大约是(2*B+(2*B*log2B三、总结：对于数据库的设计，数据库的查询优化是必不可少的；查询处理时RDBMS的核心，而查询优化技术是查询处理的关键。一个好的查询优化处理能使的执行效率更高，减小程序的设计代价；查询优化能避免不必要的复杂性，对于有些查询构建方法，优化器无法总能给出最优执行计划；给优化器提供约束和统计信息，询优化器生成的执行计划的性能和健壮性很大程度上依赖于可获得