数据库系统实现第六章查询执行

第六章 查询执行

查询执行也就是操作数据库的算法

一次查询的过程：

查询-->查询编译（第七章）-->查询执行(第六章）-->数据

查询编译预览

查询编译可以分为三个步骤：

a）分析：构造分析树，用来表达查询和它的结构

b）查询重写，分析树被转化为初始查询计划，通常是代数表达式，之后初始的查询计划会被优化为一个时间更小的计划

c）物理计划生成，将查询计划转化成物理的计划，

为了选择更好的查询计划，需要判断

1）查询哪一个代数的等价形式是最有效的

2）对选中形式的每一个操作，所使用的算法选择

3）数据如何从一个操作转向另一个操作，比如流水线的方式还是，主存缓冲区还是通过磁盘。这些选择依赖于关系的大小，统计数据，某些索引的存在以及数据在磁盘上的分步。

关系代数的操作符包括

1）并，交，和差

2）选择

3）投影

4）乘积

5）连接

6）消除重复

7）分组

8）排序

表达式树

对于任何操作，我们可以将几个操作符的应用画成一个表达式树，这些树的叶节点是关系的名字，内部节点为操作符，每个操作符操作的是他的儿子节点。

物理查询计划操作符

物理查询计划由操作符构造，每一个操作符实现计划的一步，物理操作符常是一个关系代数操作符的时间。当然物理操作符有时完成的与关系代数无关，例如，扫描一个表。

扫描表

无力查询计划中最基本的事是读一个关系R的整个内容，例如将R与另一个关系做并连接的时候，这一步是必须的，扫描的方式有两种

1）很多时候，关系R存放在二级存储器中的某些区域，元组排放在块中，一个接一个的扫描块，叫做表-扫描

2）如果关系R种某一属性有索引，可以使用索引来得到R的元组，这种叫索引-扫描

扫描表时的排序

实现排序-扫描的方法有三种

a）如果我们想要按照属性a来排序关系R，并且a上有一个B数索引，或者R是按a排序的，那么对索引扫描即可得到顺序的R

b）如果R可以装进内存，那么可以采用内存排序算法

c）如果R很大不能完全装进内存，那么可以采用外存排序的方式，如两阶段多路归并

数据库系统实现 第六章 查询执行