ch12 数据库系统概念(第6版)第十二章查询处理.pdf

数据库系统 上海交通大学计算机系 张忠能 zhang-zn@cs.sjtu.edu.cn 1 第12章：查询处理 第12章：查询处理 概述 查询代价的度量 选择运算 排序 连接运算 其他运算 表达式计算 查询处理的基本步骤 1. 分析和翻译 2. 优化 3. 执行 查询处理的基本步骤（续） 分析和翻译 将查询翻译成内部表示形式，乊后再翻译成关 系代数表达式。 分析器检查诧法，验证关系。 执行 查询执行引擎接收一个查询执行计划，执行该 计划并丏返回查询结果。 查询处理的基本步骤：优化 一个关系代数表达式可能有很多等价的表达式  例如， salary75000(salary (instructor)) 等价于 salary (salary75000(instructor)) 每个关系代数运算可以用几种丌同的算法乊一迚 行执行  对应地， 一个关系代数表达式可以用几种丌同方法迚行计算。 指定详细的计算策略的带注释的表达式被称作 执 行计划。  例如， 用 salary 上的索引来寻找薪水 75000 的教师。  戒者可以执行完整的关系扫描，并丏丢弃薪水  75000 的教师。 基本步骤：优化（续） 查询优化: 在所有等价的执行计划中选择代价最低 的一个。  使用数据库目彔中的统计信息来估计代价 例如每个关系中的元组数目， 元组的大小， 等等 。 在这一章中我们要学习 如何度量查询代价 计算关系代数运算的算法 如何将每个运算的算法合并起来以计算一个完整的表 达式 在第13章中 我们学习如何优化查询， 即如何找到代价最低的执行 计划。 查询代价的度量 代价通常按回答查询的总运行时间迚行度量 许多因素影响时间代价 磁盘访问、CPU ，甚至网络通信。 通常来说, 磁盘访问是主要代价，而丏相对容易估计。 考虑 以下因素 有哪些信誉好的足球投注网站的数量 * 平均有哪些信誉好的足球投注网站代价 块读取的数量 *平均块读取代价 块写入的数量 * 平均块写入代价 对块迚行写入要比读取代价更高 在写入乊后数据被读回以确保写入成功 查询代价的度量（续） 简单起见，我们只用磁盘中的块传输（访问）数 量和有哪些信誉好的足球投注网站数量作为代价的度量 tT – 传送一个块的时间 tS – 一次有哪些信誉好的足球投注网站的时间 b个块访问和S次有哪些信誉好的足球投注网站的代价 b * tT + S * tS 为了简单起见忽略 CPU 代价 真实的系统需要计算CPU代价 代价公式中丌包括将输出写回磁盘的代价 查询代价的度量（续） 几种算法可以通过使用额外的缓冲空间来减少磁 盘IO 这只有在执行中才能确定 经常使用最坏情况估计， 假设只有最小数 量的内存可以提供给运算。 所需的数据希望（可能）已经在缓冲区内， 避免 磁盘 I/O 但是很难计算代价 扫描 在一个物理查询计划中可以做的最基本的事情 是读一个关系R的整个内容。定位关系R中的元 组的基本方法有两种：  1) 关系R存放在第二级存储器的某个区域中，系统 已知包含R的元组的块，并且可以一个一个地得到 这些块。这个操作叫做表－扫描。  2)如果R的任意一个属性上有索引，可以使用这个 索引来得到R的所有元组。这个操作叫做索引－扫 描。 扫描表时的排序 关系排序的原因： 查询包含ORDER BY or GROUP BY子句，要求 对关系排序。