查询处理与优化

查询处理的一个目标是快速高效地得到查询结果，实现这一目标的方式是查询优化
优化就是寻找执行代价（费用和时间）最小的查询执行策略，使系统执行效率降到最低。
优化的目标就是指局部执行代价和网络传输代价的和最小。
局部执行代价：主要指输入/输出次数（I/O代价）及CPU处理代价。
网络传输代价：主要指传输启动代价和数据传输代价

查询优化的意义

我们以一个例子来说明选择何种执行策略。
比如求选修2号课程的学生姓名
SQL表示:

select Sname
from Students, SC
where Students.Sno=SC.Snoand Cno='2';

面对这样的查询语句，将其转化为关系代数，有3种不同的表示方法



代价计算(均只考虑I/O代价)
假定: 在内存中, 存放5块Students元组和一块SC元组,一块可以装10个Students元组或100个SC元组.
假定: Students有1000个元组,SC有10000个元组,其中选2号课程的有50个元组
数据只有读到内存才能进行连接
1.代价计算

读取方式为以其中一块为主，依次读取另外一块，读完之后再更新主块
此处为以Students作为主块，遍历SC块
内存中一次可以存放5个Students块，1个SC块，一次读取块数如下
读取总块数:

若每秒读写20块, 则花费105s
笛卡尔集计算后的元组个数为:
连接后的中间结果内存放不下, 需暂时写到外存
若每块可装10个完成笛卡尔积后的元组, 则写这些元组需:

选择操作时，将数据读回内存，选择后剩下50个元组，均可放在内存中
则查询共花费

1. 代价计算

自然连接时，读取总块数同,花费时间105s
自然连接结果为个元组，写入外存，
读自然连接结果50s，执行选择余下50个元组放入内存
总时间为

1. 代价计算

对SC进行选择，读入内存块数为，消耗时间5s
选择结果为50个SC元组，均可放在内存中
与Students进行自然连接，读入Students，读入内存块数为
花费时间为5s
连接结果为50个元组，均可放入内存，总花费为
从上述三种策略看，虽然都能实现所要完成的功能，但三种实现方法所须的代价却相差很大。
在分布式系统中，对于多用户、多应用需求的复杂任务，采用不同的实现策略会相差更大，将直接影响整个系统整体性能。
因此，需要确定出一种执行代价最小的查询执行策略。
优化内容体现如下几点：

• 执行运算的次序。
• 执行每种运算的方法。如上例，不同方法代价不同。
• 所访问的副本场地。如：选择就近的场地，节约传输代价。
• 执行运算的场地的选择。使总的传输代价或总代价最低。

综合考虑，确定出一种执行代价最小的查询执行策略。

查询树与关系代数

从以上例子可以看出，用户所使用的是数据库顶层的全局查询，对于具体的执行细节没有过多的关注，系统需要将全局查询语句转化为等价的关系表达式，描述如何执行该语句，并确定最优的执行策略。
内部表示的一种方式就是查询树，而查询树则是根据关系代数语法分析得到的。