数据库系统概念 第十二章 查询处理
查询处理是指从数据库中提取数据时涉及的一系列活动，包括：
将用高层数据库语言表示的查询语句翻译为能在文件系统的物理层上使用的表达式
为优化查询而进行各种转换
查询的实际执行
概述：
查询处理基本步骤：
1 语法分析与翻译
2 优化
3 执行
用于执行一个查询的原语操作序列称为查询执行计划
查询执行引擎接收一个查询执行计划，执行该计划并把结果返回
构造具有最小查询执行代价的查询执行计划应当是系统的责任，这项工作叫做查询优化。
查询代价的度量：
查询处理的代价可以通过该查询对各种资源的使用情况进行度量，这些资源包括磁盘存取、执行一个查询所用CPU时间、还有在并行/分布式数据库系统中的通信代价
在大型数据库系统中，在磁盘上存取数据的代价通常是最主要的代价
我们用传送磁盘块数(一般传送一个块平均消耗为0.1ms)以及搜索磁盘次数(磁盘块平均访问时间为4ms)来度量查询计算计划的代价
优化器通常努力去尽可能降低查询计划总的资源消耗，而不是尽可能缩低响应时间
选择运算：
在查询处理中，文件扫描是存取数据最低级的操作。
文件扫描是用于定位、检索满足选择条件的记录的搜索算法
使用文件扫描和索引的选择：
1 线性搜索：系统扫描每一个文件块，对所有记录都进行测试。
2 主索引，码属性等值比较
3 主索引，非码属性等值比较
4 辅助索引，等值比较
涉及比较的选择：
1 主索引，比较：
最好的选择
2 辅助索引，比较
有可能比线性搜索还要大
排序：
内存中能够完全容纳的关系的，用标准的排序技术
不能完全被内存容纳的关系的：
外部排序归并算法：
不能全部放在内存中的关系的排序称为外排序，外排序最常用的技术是外部排序归并算法
1 建立多个排好序的归并段，每个归并段都是排序过的，但仅包含关系中的部分记录
2 对归并段进行归并
连接运算：
嵌套循环连接：
由两个嵌套的for循环构成，因此称为嵌套循环连接，外面的称为外层关系，里面的称为内层关系
块嵌套循环连接：
以块的方式而不是以元组的方式处理关系，仍然可以减少不少块读写次数
索引嵌套循环连接
在嵌套循环连接中，若在内层循环的连接属性上有索引，则可以用索引查找替代文件扫描
如果内外都有索引时，一般把元组较少的关系作外层关系时效果较好
索引嵌套循环连接可以比块嵌套循环连接快得多
归并连接
归并连接算法(又称排序-归并-连接算法)可用于计算自然连接和等值连接
散列连接：
可以实现自然连接和等值连接
在散列连接算法中，用散列函数h来划分两个关系的元组
此算法的基本思想是把这两个关系的元组划分成在连接属性值上具有相同散列值的元组集合
基本思想：
如果关系r的一个元组与关系s的一个元组满足连接条件，那么它们在连接属性上就会有相同的值
其他运算：
去除重复：
排序、归并、散列算法很容易地实现去除重复。
由于去除重复的代价相对较大，因此SQL查询语言要求用户显式指明需要去除重复，若不指明则保留重复
投影：
首先对每个元组作投影，所得结果关系可能有重复记录，然后去除重复记录
集合运算：
要实现集合运算并、交、差，我们首先对两个关系进行排序，然后对每个已排序的关系扫描一次，产生所需结果
散列提供了实现集合运算的另一种方法
外连接：
两种策略实现：
1 先计算内连接，如果是左外连接，把左表中未连接的加入结果集，右外连接，相反
2 将嵌套循环连接算法扩展为计算左外连接的算法，把与内层关系的任何元组都不匹配的外层关系元组在填充空值后写到结果中
聚集：
表达式计算：
如何计算包含多个运算的表达式：
1 以适当的顺序每次执行一个操作，每次计算的结果被物化到一个临时关系中以备后用。
缺点：需要构造临时关系，这些临时关系必须写到磁盘上(除非很小)
2 在流水线上同时计算多个运算，一个运算结果传递给下一个，而不必保存临时关系
两种方法代价相差很大，并且有的情况下只能用物化方法
物化：
要直观地理解如何计算一个表达式，最容易地方法是看一看以运算符树对表达式所做的图形化表示
物化计算：运算的每个中间结果被创建(物化)，然后用于下一层的运算
物化计算的代价不仅仅是那些所涉及的运算代价的总和，而且包括了将计算结果写到磁盘上的代价
双缓冲(使用两个缓冲区，一个用于连续执行算法，一个用于写出结果)允许CPU活动与I/O活动并行，提高算法执行速度
流水线：
通过减少查询执行中产生的临时文件数，可以提高查询执行的效率。
减少临时文件数是通过将多个关系操作组合成一个操作的流水线来实现的，一个操作的结果将传送到下一个操作，叫做流水线计算
好处：
1 它能消除读和写临时关系的代价，减少查询计算代价
2 如果一个查询计算计划的根操作符及其输入合并到流水线中，那么可以迅速开始生产查询结果
实现：
通过将所有操作组合起来构成流水线，构造一个单独的复合操作，可以实现流水线。
流水线可按以下两种方式之一来执行：
1 在一条需求驱动的流水线中，系统不停地向位于流水线顶端的操作发出需要元组的请求
每当一个操作收到需要元组的请求，它就计算下一个(若干个)元组并返回
2 在一条生产者驱动的流水线中，各操作并不等待元组请求，而是积极地产生元组。
生产者驱动的流水线中的每一个操作作为系统中一个单独的进程或线程模型，
以处理流水线输入的元组流，并产生相应的输出元组流
生产者驱动的流水线中，元组的生产是积极的。
需求驱动的流水线中，元组消极地按需求产生
需求驱动的流水线比生产者驱动的流水线应用得更为普遍，因为它更容易实现
生产者驱动的流水线在并行处理系统中非常有用
流水线的执行算法：