文章目录

查询处理步骤查询操作的常用算法选择操作的实现算法连接操作的实现算法查询优化查询优化的一个实例代数优化画查询树并优化计算IO读写块数

查询处理步骤

查询处理分为4个阶段：

查询分析

查询检查

查询优化

查询执行

查询操作的常用算法

选择操作的实现算法

选择操作时查询处理中最常用也是最耗时的操作之一。

索引扫描算法（index scan）

如果选择条件上有索引（例如B+树索引或hash索引），可以用索引扫描方法。

算法思想：先通过缩影找到满足条件的元组指针，再通过元组指针在基本表中找到元组。

例子：

选择条件Sdept = ‘cs’ AND Sage > 20，如果Sdept和Sage上都有索引。

则有两种算法可选：

一种是通过索引分别找到两个条件的元组指针集合，再求两个集合的交集，再到基本表中去检索。

另一中算法是通过Sdept = 'cs’找到一个元组指针集合，然后遍历这个指针集合，到基本表中将满足另一条件(Sage > 20)的元组选择输出。

简单的全表扫描算法

算法思想：按照物理次序读表的M块到内存，检查内存中的每一个元组t。如果t满足选择条件，则输出t。如果表中还有未处理的块，重复前两步。

二者的比较：

一般情况下，当选择率较低时，基于索引的选择算法要优于全表扫描算法。

但再某些情况，例如选择率较高，或者要查找的元组均匀分布再查找的表中，这时基于索引的选择算法性能不如全表扫描算法。

连接操作的实现算法

嵌套循环算法（nested loop join）

这是最简单可行的算法，可以处理包括非等值连接在内的各种连接操作。

算法思想：（连接条件：left.x = right.x）就是两个for循环，不断在比较，时间复杂度O(N*M)。

注意：现实中，数据存取时按数据块读入内存中，而不是按照元组进行I/O。

排序-合并算法（sort-merge join 或者 merge join）

这是等值连接常用的算法，尤其适合参与连接的诸表已经排好序的情况。

算法思想：（连接条件：left.x = right.x）先将两个表按连接属性排序，然后两个for循环，根据连接条件把它们连接起来。（有下标、有break）排序时间复杂度O(N*log(N)），循环时间复杂度O(N+M)。

优点：虽然时间主要花在排序上，但是相比嵌套循环算法，在表规模较大时，还是能减少很多时间。

索引连接算法（index join）

算法思想：（连接条件：left.x = right.x）

要求在right表上已经建立了属性x的索引。通过left表中的x值，通过left上的索引找到相应的right表元组，将左右表的元组连接起来。

hash join算法

处理等值连接的算法。

算法思想：

第一步，划分阶段/创建阶段。创建 hash 表。对包含较少元组的表，进行一遍处理，把它的元组通过连接属性按 hash 函数，分散到 hash 表的桶中。

第二步，试探阶段/连接阶段。对另一个表，同样进行一遍散列处理，找到合适的 hash 桶，将两个的匹配的元组连接起来。

（当发现 hash 表中已有key值时，将两个value对应的元组连接。）

算法时间复杂度O(N+M)。

缺点：需要一个前提条件，数据量较小的表，在第一阶段后，能完全放入内存中的 hash 桶中。

以下的是有关题目的

需要会做题

查询优化

关系查询优化是影响关系数据库管理系统性能的关键因素。

分为：代数优化（逻辑优化）、物理优化（非代数优化）

查询优化的一个实例

select Student.Sname from Student,SC where Student.Sno = SC.Sno and o = ‘2’

计算两个表的广义笛卡儿积

这一步产生的结果集太大，需要写入中间文件，写入块数大

从广义笛卡儿积中根据两个选择条件做选择操作

读取上一步中间文件，读取块数大

作投影操作，选出需要的列

根据Student.Sno = SC.Sno计算两个表的自然连接

由于已经用条件筛选了，中间文件减小很多，写入块数较小

从自然连接结果集中，根据SC.Sno = '2’做选择操作

同样读取中间文件，读取块数较小

投影输出

根据SC.Sno == '2’对SC表做选择操作

对单个表用等值条件筛选了，一般来讲，结果集较小，不需要中间文件，直接存在内存中

将第一步的结果集，与Student表根据Student.Sno = SC.Sno做自然连接

不需要读中间文件

投影输出

代数优化

代数优化策略是通过关系代数表达式的等价变换来提高查询效率的。

画查询树并优化

计算IO读写块数