清华大学数据库access课件 第09章：查询处理.ppt

§9.4实现关系运算的算法代价 嵌套循环连接 算法分析： 与文件的线性扫描算法类似，关系文件的每个数据块都必须被访问； 不要求有任何索引，任何连接条件都能适应； 对关系r的每一条记录都必须对关系s做一次完整的扫描，因此算法代价为： 最坏情况下：缓冲区只能容纳每个关系的一个数据块，因而EJ=nr*bs+br 最好情况下：两个关系都能放到内存里，因而算法代价为EJ=bs+br 第一节课的问题：谁将作为连接的内关系？ §9.4实现关系运算的算法代价 索引嵌套循环连接 将嵌套循环连接算法中的文件扫描用索引扫描来代替： 算法分析： 在给定元组tr的情况下，在关系s中查找满足连接条件的元组本质上是在s上做选择运算。因此该算法的代价为： EJ = br + nr * c 其中c是使用连接条件并利用索引对关系s进行单个选择运算的代价。 索引该建在什么地方？ §9.5表达式的求值方法 概述：关系代数表达式的代价估计 前面讨论的都是实现单个关系运算的算法与算法分析； 实际上在一个关系代数表达式里常常含有多个不同或相同的关系运算，那么如何估计整个表达式的计算代价呢？这主要与整个表达式的计算方法有关： 实体化计算方法 流水线计算方法 上述两种方法的相互结合(参见§9.6) §9.5表达式的求值方法 实体化计算方法 以适当的顺序每次执行表达式里的一个关系运算，每次计算的结果都被保存(实体化)到一个临时关系中以备后面的运算使用。如： Πcourse_name((σstudent_number”s000003”(student)) selecting) §9.5表达式的求值方法 实体化计算方法 实体化计算方法的缺点是需要构造临时关系，这些临时关系除非很小(可以放在内存里)，否则就必须写到磁盘上(tempdb)； 实体化计算方法的代价不仅仅是表达式中所涉及的关系运算的代价总和，还应该加上把中间结果写回磁盘的代价； 在估计单个关系运算的代价时，忽略了将运算结果回写到磁盘的代价。但对由多个关系运算构成的表达式，就不能简单地忽略掉回写磁盘的代价！ * 数据库系统设计与原理 第Ⅲ部分 DBMS的内核 (第９章－第11章) 第9章　查询处理 讲课内容： 查询处理是指从数据库中提取数据的一系列活动。这一系列活动包括：将用高层数据库语言表示的查询语句，如SQL，翻译成能在文件系统这一物理层上实现的表达式，如关系代数；为优化查询进行的各种转换；以及查询的实际执行。 ■查询处理的过程　　　　■表达式的求值方法 ■关系代数表达式的转换　■查询优化的方法 ■查询代价的度量　　　　■查询优化器的构造 ■实现关系运算的算法代价■本章总结 DBMS总体结构回顾：查询处理器 用户 应用界面 索引 统计数据 数据文件 数据字典 应用程序 交互查询 数据库模式 应用程序目标码 嵌入式DML预编译器 DML编译器 DDL解释器 查询计算引擎 事务管理器 缓冲区管理器 文件管理器 查询处理器 存储管理器 数据库管理系统 磁盘存储器 权限及完整性管理器 日志 §9.1查询处理的过程 查询处理 是指对最终用户提交的查询进行： 解析 优化 执行 并最终给出查询结果的处理过程。 §9.1查询处理的过程 查询优化器 问题的提出： 一个查询用SQL语言可以有多种表达方式； 而每个SQL语句又可以翻译成多个等价的关系代数表达式。例如： select student_number from student where student_number “s000003” 可以翻译成下面两个关系代数表达式： ①σstudent_number”s000003”(Πstudent_number(student)) ②Πstudent_number(σstudent_number”s000003”(student)) 表达式中的关系运算又可以用不同的算法和索引去实现。因此，查询优化器的任务就是要找出代价最小的计算给定查询的处理过程。 §9.1查询处理的过程 查询优化器 输入？输出？ 查询执行计划？带注释！ 注释用于说明： 如何具体实施每个关系操作。例如： 关系运算所采用的算法 将要使用的索引 执行原语： 加上了有关“如何执行”的注释的关系代数运算 查询执行(计算)计划： 用于计算一个查询的原语序列。 查询优化器 查询优化 为给定查询选择最有效的查询执行计划的过程： 在关系代数级进行优化，力图找出与给定表达式等价、但执行效率更高(?)的一个表达式； 查询语句处理的详细策略的选择。例如，确定算法与索引等。 本章的主要内容 什么是查询执行计划的代价？ 如何估计查询执行计划的代价？ 如何进行有效的查询优化？ §9.1查询处理的过程 §9.1查询处理的过程 执行引擎 输入是查询执行计划 输出则是具体的查询结