关系查询处理和查询优化小结

1、关系查询处理和查询优化小结一. 关系查询优化的概述1. 查询优化在关系数据库中的重要性及必要性关系系统的查询优化既是 RDBMS 实现的关键技术又是关系系统 的 优点所在。它减轻了用户选择存取路径的负担。查询优化极大地影 响 RDBMS 的性能。用户只要提出“干什么 ，不必指出“怎么干 。 查询 优化的优点不仅在于用户不必考虑如何最好地表达查询以获得 较好的效 率，而且在于系统可以比用户程序的“优化 夕做得更好。2. 查询优化的可能性和优点1) 优化器可以从数据字典中获取许多统计信息， 而用户程序那么 难以获得这些信息2) 如果数据库的物理统计信息改变了， 系统可以自动对查询重 新优化以选择相

2、适应的执行方案。在非关系系统中必须重写程序 , 而 重写程序在实际应用中往往是不太可能的。3) 优化器可以考虑数百种不同的执行方案， 程序员一般只能考 虑有限的几种可能性。4) 优化器中包括了很多复杂的优化技术， 这些优化技术往往只 有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有 这 些优化技术；3. 查询优化的一般准那么(1 )选择运算应尽可能先做；(2) 把投影运算和选择运算同时进行；(3) 把投影同其前或其后的双目运算结合起来执行；(4) 把某些选择同在它前面要执行的笛卡儿积结合起来成为一个 连接运算； (5 ) 找出公共子表达式；(6) 选取适宜的连接算法。4. 查询优化

3、的一般步骤(1) 把查询转换成某种内部表示，通常用的内部表示是语法树。始的(2) 把语法树转换成标准 (优化) 形式。即利用优化算法，把原 语法树转换成优化的形式。(3) 选择低层的存取路径。(4) 生成查询方案，选择代价最小的。5. 代价模型一般 DBMS 采用基于代价的优化算法：集中式数据库单用户系统总代价二 I/O 代价+ CPU 代价多用户系统总代价=1/0代价+ CPU代价+内存代价分布式数据库总代价=1/0代价+ CPU代价+内存代价+通信代价二. 关系数据库查询优化方法1?代数优化关系代数表达式等价指用相同的关系代替两个表达式中相应的 关系所得到的结果是相同的1查询树启发式优化，

4、一般规那么有选择运算应尽可能先做最重要，最根本目的：减小中间关系投影运算和选择运算同时做目的：防止重复扫描关系将投影运算与其前面或后面的双目运算结合 目的：减少扫描关系的遍数在执行连接操作前对关系适当进行预处理按连接属性排序在连接属性上建立索引某些选择运算 +在其前面执行的笛卡尔积= 连接运算2查询树的启发式优化一算法1分解选择运算2通过交换选择运算，将其尽可能移到叶端3通过交换投影运算，将其尽可能移到叶端4合并串接的选择和投影， 以便能同时执行或在一次扫描中完(5) 对内结点分组(6) 生成程序例：6 Student. Sno=SC. Sno (Student XSC)1X1Stude nW

5、 SC提取公共子表达式； 例如：查询小王选修的所有课程。可以用关系代数来表达多种 同的查询方法。Sl= n eno ( o S. sno二 SC. sno A S. sname=小王(SXSC)S2= n eno ( o S. sn ame二“小王(sX SC)S3= n eno ( o S. sn ame=小 _5?八(S) SC)三种查询的结果是完全相同的，但三种查询的具体操作、所占 用的内存、所消耗的时间是不相同的。显然：S3 优于 S2 优于 S1查询优化对减少系统开销、提髙运行速度是很重要的。2. 物理优化物理优化就是要选择高效合理的操作算法或存取路径，球的优化的查询方案，到达查询优

6、化的目标1物理优化可以选择的方法1 基于规那么的启发式优化；大多数情况下都适用。2基于代价估算的优化；优化器估算不同执行策略的代价，并 出具有最小代价的执行方案。3两者结合的优化方法。2选择操作的启发式规那么对于小关系，使用全表顺序扫描，即使选择列上有索引； 对于大关系，启发式规那么有：对于选择条件是主码 =值的查询； 查询结果最多是一个元组，可以选择主码索引； 一般的 RDBMS 会自动建立主码索引；对于选择条件是非主属性 =值的查询，并且选择列上有索 要估算查询结果的元组数目 如果比例较小 ?10% 可以使用索引扫描方法 否那么还是使用全表顺序扫描3全表扫描算法的代价估算公式如果根本表大小为 B 块，全表扫描算法的代价 cost=B如果选择条件是码 =值，那么平均代价 cost = B/24) 排序- 合并连接算法的代价估算公式如果连接表已经按照连接属性排好序，那么 cost =Br+Bs+(Frs*Nr*Ns)/Mrs 。如果必须对文件排序 需要在代价函数中加上排序的代价 对于包含 B 个块的文件排序的代价大约是 (2*B)+(2*B*log2B)三 . 总结 对于数据库的设计，数据库的查询优化是必不可少的；查询处理时 RDBMS 的核心，而查询优化技术是查询处理的关键。 一个好的查询优 化 处理能使的执行效