《数据结构域算法设计ch.12 查询处理和优化》由会员分享，可在线阅读，更多相关《数据结构域算法设计ch.12 查询处理和优化（34页珍藏版）》请在金锄头文库上搜索。
1、第12章 查询处理和优化,12.1 概述 12.2 代数优化 12.3 依赖于存取路径的规则优化 12.4 代价估算优化*,12.1 概述,重要性 查询是数据库系统中最基本、最常见和最复杂的操作。对数据库的查询一般都是以查询语言（如SQL）表示。从查询请求出发，直到得到查询结果，这一过程称为查询处理。 关系数据库系统的查询语言一般是“非过程语言”，它减轻了用户选择存取路径的负担。用户只要提出干什么，不必指出怎么干。即用户不必关心查询的具体执行过程，而由DBMS确定合理的、有效的执行策略。DBMS在这方面的作用成为查询优化 。 对于使用非过程查询语言的RDBMS，查询优化是查询处理中非常重要的一
2、环，对系统性能会产生很大的影响。,12.1 引言,查询优化的优点 查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化”做得更好。这是因为： 优化器可以从数据字典中获取许多统计信息，例如关系中的元组数、关系中每个属性值的分布情况等。优化器可以根据这些信息选择有效的执行计划，而用户程序则难以获得这些信息。 如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。 优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。 优化器中包
3、括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。,12.1 引言,查询优化的目标和途径 关系数据库查询优化的总目标是：选择有效的策略，求得给定关系表达式的值。 查询优化的途径包括： 对查询语句进行等价变换（如改变基本操作的顺序）使查询执行起来更加有效。这种优化只涉及查询语句本身，而不涉及存取路径，故称为独立于存取路径的优化，或代数优化。 根据系统提供的查询路径，选择合理的存取策略（例如是选择顺序扫描还是选择索引），这称为依赖于存取路径的优化，或称物理优化。 有些查询可根据启发式规则选择执行策略，这称为规则优化。 根据可供选择的
4、执行策略进行代价估算，并从中选择代价最小的执行策略，这称为代价估算优化。 此外，还可以通过应用数据库的语义信息对查询进行优化，这称为语义优化。,12.1 引言,查询处理和优化的步骤 实际系统对查询优化的具体实现一般可以归纳为四个步骤： 将查询转换成某种内部表示，通常是语法树。 根据一定的等价变换规则把语法树转换成标准（优化）形式。 选择低层的操作算法。对于语法树中的每一个操作需要根据存取路径、数据的存储分布、存储数据的聚簇等信息来选择具体的执行算法。 生成查询计划。查询计划也称查询执行方案，是由一系列内部操作组成的。这些内部操作按一定的次序构成查询的一个执行方案。通常这样的执行方案有多个，需要
5、对每个执行计划计算代价，从中选择代价最小的一个。 在集中式数据库中，查询的执行开销主要包括： 总代价 = I/O代价 + CPU代价 在多用户环境下： 总代价 = I/O代价 + CPU代价 + 内存代价,12.1 引言,一个简单的例子 首先看一个简单的例子，说明为什么要进行查询优化。 例：求选修了2号课程的学生姓名。用SQL语言表达： SELECT S.Sname FROM Student S，SC WHERE S.SNO=SC.SNO AND SC.CNO=2； 假定学生-课程数据库中有l000个学生记录,l0000个选课记录，其中选修2号课程的选课记录为50个。 系统可以用多种等价的关系代数表达式来完成这一查询 1.Q1= Sname( Student.sno=o=2(StudentSC) 2.Q2= Sname( o=2 (Student |10000;,
