查询处理

1 概述

一个查询，一般都会有多种计算结果的方法。

例如，select salary from instructor where salary<75000;

可以被翻译为以下任意一个关系代数表达式

要全面说明如何执行一个查询，有以下概念：

计算原语（evaluation primitive）：加了“如何执行”注释的关系代数运算
查询执行计划（query-execution plan）：用于执行一个查询的原语操作序列，也成为查询计算计划（query-evaluation plan）
查询执行引擎（query-execution engine）：接受一个查询执行计划，执行该计划并把结果返回给查询

给定查询的不同执行计划会有不同的代价，选择最高效率的查询计划就是查询优化，是系统的责任

主要度量：

假设传输一个磁盘块的数据平均t_r秒，磁盘访问时间（磁盘搜索加旋转延迟）t_s秒，一次传输b个块以及执行S次磁盘搜索的时间为：

我们假定开始时的数据必须从磁盘中读出，但实际上可能已经被缓存过了。为了简化，忽略这种情况，所以实际代价可能小于估算代价

因此，很难估算计划的响应时间，原因如下：

优化器通常努力去降低查询计划的资源消耗，而不是降低响应时间。因为总有一些方法可以以资源换时间，这对于单个查询是降低了响应时间，但如果多个查询同时执行，往往会提高响应时间。

文件扫描（file scan）是存取数据最低级的操作

有以下更复杂的选择谓词

分别有以下算法

A7（利用一个索引的合取选择）

判断是否有某个属性上存在索引，若存在选择A2-A6中的一个来搜索满足条件的记录，然后在内存缓冲区中，通过测试检索到的记录是否满足其他条件，最终完成这个操作。由选择的θi组合决定。
A8（通过使用组合索引和合取选择）

可能使用组合索引，索引的类型决定使用A2、A3、A4中的哪一个
A9（通过标识符的交实现合取选择）

要求各个条件涉及的字段上带有记录指针的索引。对每个索引进行扫描，获取那些指向单个条件记录的指针，然后取交集。需要注意的是：
1. 应该把指向一个磁盘块的指针放在一起，这样只需要一次磁盘IO就可以获取该磁盘块上的全部记录
2. 要按存储次序执行，这样磁盘臂的移动最少
A10（通过标识符的并实现析取选择）

如果析取条件中均有带有记录指针的索引，可以类似A9。

否则直接线性扫描。（不然的话为了取一个条件也要线性扫描一次，不如直接扫描好了）
取反

线性扫描A1

针对内存中能够完全容纳的情况

标准的排序算法，比如快排

针对不能被内存完全容纳的情况

本节介绍

对于不能完全放在内存中的关系进行排序，称为外排序（external sorting）。

其中最常用的技术是归并排序。