第7章-查询处理与查询优化.ppt

第7章 查询处理与查询优化 7.1 引言 7.2 代数优化 7.3 物理优化 7.4 代价估算优化* 7.1 引言 查询处理 查询处理的步骤 实际系统对查询优化的具体实现一般可以归纳为四个步骤： 将查询转换成某种内部表示，通常是语法树 根据一定的等价变换规则把语法树转换成标准（优化）形式 选择低层的操作算法。对于语法树中的每一个操作需要根据存取路径、数据的存储分布、存储数据的聚簇等信息来选择具体的执行算法 生成查询计划。查询计划也称查询执行方案，由一系列内部操作组成。这些内部操作按一定的次序构成查询的一个执行方案。通常这样的执行方案有多个，需要对每个执行计划计算代价，从中选择代价最小的一个 查询处理的步骤 查询处理的实现方式 解释：DBMS接到查询语句，创建相应的事务，解释执行查询语句，且在事务完成后返回查询结果，一般不保留可执行代码 查询处理的实现方式 编译：应用程序经预编译处理，将嵌入的查询语句分出，进行语法、词法分析和查询优化，生成一个可执行的访问模块（AM），存于磁盘中。 查询优化 关系数据库系统的查询语言一般是“非过程语言”，它减轻了用户选择存取路径的负担。 即用户只要提出“做什么?”(What)，不必指出“怎么做”(How)。用户不必关心查询的具体执行过程 由DBMS确定合理的、有效的执行策略这方面的功能称为查询优化 对于使用非过程查询语言的RDBMS，查询优化是查询处理中非常重要的一环 查询优化的必要性 查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化”做得更好, 这是因为： 优化器可以从数据字典中获取许多统计信息 如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的 优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。 优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术 查询优化的途径 对查询语句进行等价变换（如改变基本操作的顺序）使查询执行起来更加有效。这种优化只涉及查询语句本身，而不涉及存取路径，故称为独立于存取路径的优化，或代数优化 根据系统提供的查询路径，选择合理的存取策略（例如是选择顺序扫描还是选择索引），这称为依赖于存取路径的优化，或称物理优化 有些查询可根据启发式规则选择执行策略，这称为规则优化 根据可供选择的执行策略进行代价估算，并从中选择代价最小的执行策略，这称为代价估算优化 此外，还可以通过应用数据库的语义信息对查询进行优化，这称为语义优化 查询处理的代价 在集中式数据库中，查询的执行代价主要包括 总代价 = I/O代价 + CPU代价 在多用户环境下: 总代价 = I/O代价 + CPU代价 + 内存代价 在网络分布环境下: 总代价 = I/O代价 + CPU代价+网络传输代价 实例分析 例：求选修了2号课程的学生姓名。用SQL语言表达：  SELECT S.Sname  FROM Student S，SC  WHERE S.SNO=SC.SNO AND SC.CNO=2； 假定学生-课程数据库中有l000个学生记录,l0000个选课记录，其中选修2号课程的选课记录为50个。 系统可以用多种等价的关系代数表达式来完成这一查询  Q1= πSname(σStudent.sno=sc.sno∧sc.cno=2(Student×SC))  Q2= πSname (σ sc.cno=2 (Student ||SC))  Q3= πSname (Student || σ sc.cno=2‘ (SC)) 实例分析 查询执行策略Q1代价分析 计算广义笛卡尔积的代价 把S和SC的每个元组连接起来。一般连接的做法是：在内存中尽可能多地装人某个表(如Student表)的若干块元组，留出一块存放另一个表(如SC表)的元组。然后把SC中的每个元组和Student中每个元组连接，连接后的元组装满一块后就写到中间文件上，再从SC中读入一块和内存中的S元组连接，直到SC表处理完。这时再一次读入若干块S元组，读入一块SC元组，量复上述处理过程，直到把S表处理完 设一个块能装l0个Student元组或l00个SC元组，在内存中存放5块Student元组 和1块SC元组，则读取总块数为： 1000/10+1000/(10 X 5) X (10000/100)=2100块 其中读Student表l00块。读SC表20遍，每遍l00块。若每秒读写20块，则总计要花105(秒) 连接后的元组数为1000X10000,