数据库学习笔记（第十五章）

第十五章 查询处理

1.查询处理的基本步骤
语法分析与翻译（语法检查、语义检查）+优化+执行

① 解析与翻译
语法分析器检查语法，验证关系
把查询语句翻译成系统的内部表示形式，也就是翻译成关系代数
②执行
查询执行引擎接收一个查询执行计划，执行该计划并把结果返回给查询

2.查询处理的重要步骤: 优化
一个关系代数表达式可能有许多等价的表达式
可以用多种不同的算法来执行每个关系代数运算，相应地，一个关系代数表达式可以用多种方法计算

用于执行一个查询的原语操作序列称为查询执行计划

查询优化：在所有等效执行计划中选择具有最小查询执行代价的计划

3.查询代价的度量
查询处理的代价可以通过该查询对各种资源的使用情况进行度量，这些资源包括磁盘存取，执行一个查询所用 CPU 时间，甚至是网络通信代价

在磁盘上存取数据的代价通常是主要代价。通过以下指标来对其进行度量：
只用传输磁盘块数以及搜索磁盘次数来度量查询计算计划的代价

忽略 CPU 时间，实际应用中 CPU 时间应被考虑
代价估算没有包括将操作的最终结果写回磁盘的代价

4.选择运算——文件扫描（看的不是很懂）

4.1算法 A1 (线性搜索)

4.2索引扫描 – 使用索引的搜索算法
选择条件必须是索引的搜索码

5.嵌套循环连接

块嵌套循环连接

它是嵌套循环连接的一个变种，其中内层关系的每一块与外层关系的每一块对应，形成块对，在每一个块对中，一个块的每一个元组与另一个块的每一个元组形成组对，从而得到全体组对
适应于内存不能完全容纳任何一个关系时，如果我们以块的方式而不是以元组的方式处理关系，可以减少块读写次数。

6.索引循环嵌套连接

7.归并连接

在连接属性上对全部关系进行排序(如果之前并非有序的)

为了连接它们，归并有序关系：

连接步骤类似于归并排序算法中的归并阶段
主要不同在于处理连接属性上的重复值 — 每对具有相同值的连接属性的元组必须被匹配

8.散列连接

9.表达式计算

物化: 输入一个关系或者已完成的计算，产生一个表达式的结果，在磁盘中物化它，重复该过程
流水线: 一个正在执行的操作的部分结果传送到流水线的下一个操作，使得两操作可同时进行

9.1 物化
物化计算: 从最底层开始，执行树中的运算，对运算的每个中间结果创建(物化，即创建临时关系)，然后用于上一层运算

9.2流水线

感觉本章难度偏大，没咋看懂
END