【数据库系统原理】查询处理和优化

《【数据库系统原理】查询处理和优化》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章查询处理和优化5.1引言5.2代数优化5.3依赖于存取路径的规则优化5.4代价估算优化*5.1引言概述查询是数据库系统中最基本、最常见和最复杂的操作。对数据库的查询一般都是以查询语言（如SQL）表示。从查询请求出发，直到得到查询结果，这一过程称为查询处理。关系数据库系统的查询语言一般是“非过程语言”，它减轻了用户选择存取路径的负担。用户只要提出‘干什么’，不必指出‘怎么干’。即用户不必关心查询的具体执行过程，而由DBMS确定合理的、有效的执行策略。DBMS在这方面的作用成为查询优化。对于使用非过程查询语言的RDBMS，查询优化是查询处理中非常重要的一环，对系统性能会产生很大的

2、影响。5.1引言查询优化的优点查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化”做得更好。这是因为：优化器可以从数据字典中获取许多统计信息，例如关系中的元组数、关系中每个属性值的分布情况等。优化器可以根据这些信息选择有效的执行计划，而用户程序则难以获得这些信息。如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。优化器中包括了很多复杂的优化技术，这些优化

3、技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。5.1引言查询优化的目标和途径关系数据库查询优化的总目标是：选择有效的策略，求得给定关系表达式的值。查询优化的途径包括：对查询语句进行等价变换（如改变基本操作的顺序）使查询执行起来更加有效。这种优化只涉及查询语句本身，而不涉及存取路径，故称为独立于存取路径的优化，或代数优化。根据系统提供的查询路径，选择合理的存取策略（例如是选择顺序扫描还是选择索引），这称为依赖于存取路径的优化，或称物理优化。有些查询可根据启发式规则选择执行策略，这称为规则优化。根据可供选择的执行策略进行代价估算，并从中选择代价最小

4、的执行策略，这称为代价估算优化。此外，还可以通过应用数据库的语义信息对查询进行优化，这称为语义优化。5.1引言查询处理和优化的步骤实际系统对查询优化的具体实现一般可以归纳为四个步骤：将查询转换成某种内部表示，通常是语法树。根据一定的等价变换规则把语法树转换成标准（优化）形式。选择低层的操作算法。对于语法树中的每一个操作需要根据存取路径、数据的存储分布、存储数据的聚簇等信息来选择具体的执行算法。生成查询计划。查询计划也称查询执行方案，是由一系列内部操作组成的。这些内部操作按一定的次序构成查询的一个执行方案。通常这样的执行方案有多个，需要对每个执行计划计算代价，从中选择代价最小的一个。

5、在集中式数据库中，查询的执行开销主要包括：总代价=I/O代价+CPU代价在多用户环境下：总代价=I/O代价+CPU代价+内存代价5.1引言一个简单的例子首先看一个简单的例子，说明为什么要进行查询优化。例：求选修了2号课程的学生姓名。用SQL语言表达：SELECTS.SnameFROMStudentS，SCWHERES.SNO=SC.SNOANDSC.CNO='2'；假定学生-课程数据库中有l000个学生记录,l0000个选课记录，其中选修2号课程的选课记录为50个。系统可以用多种等价的关系代数表达式来完成这一查询1.Q1=Sname(σStudent.sno=sc.sno∧sc

6、.cno='2'(Student×SC))2.Q2=Sname(σsc.cno='2'(Student

7、><

8、SC))3.Q3=Sname(Student

9、><

10、σsc.cno='2'(SC))还可以写出几种等价的关系代数表达式,但分析这三种就足以说明问题了。我们将看到由于查询执行的策略不同,查询时间相差很大。5.1引言查询执行策略Q1代价分析计算广义笛卡尔积的代价把S和SC的每个元组连接起来。一般连接的做法是：在内存中尽可能多地装人某个表(如Student表)的若干块元组，留出一块存放另一个表(如SC表)的元组。然后把SC中的每个元组和Student中每个元组连接，连接后的元

11、组装满一块后就写到中间文件上，再从SC中读入一块和内存中的S元组连接，直到SC表处理完。这时再一次读入若干块S元组，读入一块SC元组，量复上述处理过程，直到把S表处理完。设一个块能装l0个Student元组或l00个SC元组，在内存中存放5块Student元组和l块SC元组，则读取总块数为：1000/10+1000/(10X5)X(10000/100)=2100块其中读Student表l00块。读SC表20遍，每遍l00块。若每秒读写20块，则总计要花105(秒)。连