21/12/6 Database 查询优化

查询优化

游标

目的-解决集合性操作语言与过程性操作语言的不匹配

原因:sql一条语句一般能产生或处理多条记录,而主语言一次只能存放一条记录

是什么:是系统为用户开设的一个数据缓冲区,存放sql语句的执行结果

用户可以用SQL语句逐一地从游标中获取记录,并赋给主变量

定义游标: 使用Declare语句

EXEC SQL DECLARE <> CURSOR……

打开游标–执行相应的select语句,吧所有满足查询条件的记录从指定表取到缓冲区中

EXEC SQL OPEN <游标名>

此时游标指针指向查询结果集中第一条记录之前

推动游标

使用FETCH语句

EXEC SQL FETCH [[NEXT]]….

指定方向推动游标指针,然后将缓冲区中的当前记录取出来送至主变量供主语言进一步处理

要求:主变量与select语句中的目标列表达式具有一一对应关系

关闭游标

CLOSE语句

EXEC SQL CLOSE <游标名>

7.1查询处理过程

7.1.1 查询分析

对查询语句进行扫描,词法分析和语法分析

7.1.2查询检查

根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查

检查通过后将SQL查询语句转换成等价的<u>关系代数表达式</u>

7.1.4查询优化

选择一个高效执行的查询处理策略

代数优化-关系代数表达式优化

物理优化-存取物理介质及…的优化

7.1.5查询执行

不用多言

7.2执行查询操作的基本算法

1. 选择操作

顺序扫描/二分查找/索引[散列]/复合选择

索引–提供元组指针,间接检索

B+树索引:同样是提供元组指针,同时支持顺序集中依次查找

如是 sdept=’cs’ and sae>20:则

算法一:分别查询,求交集

算法而:先找到第一个查询的指针,然后在第一个查询的指针基础上进行第二个查询

2.连接操作

连接操作是查询处理中最耗时的操作之一

[例2]

SELECT *

FROM Student,SC

WHERE Student.Sno=SC.Sno

[例2end]

1. 嵌套循环法
   对外层循环的每一个元组,检测内层循环中的每一个元组,检查两个元组在连接属性上是否相等
   满足,即串接后作为结果输出
2. 索引链接法
   在输出表上建立属性Sno的索引(如果原来没有)
   对student中每个元组,有Sno值通过Sc……..
3. 排序合并法
   适合连接的诸表已经排好序的情况
   没排序则排序
   取Student表中第一个sno,然后依次找sc表中具有相同sno的元组
   扫到sno不相同的第一个sc元组时,返回Student扫描它的下一个元组
   之后循环
4. 散列连接法
   把连接属性作为散列码,
   然后划分

3.投影操作

选取关系的某些列,从垂直的方向减小关系的大小

如果投影属性列包括了关系R的主键,则操作可言直接执行,操作结果将于R中元组个数相同

否则则需要消除重复元组

4.集合运算操作

并,查,交,笛卡尔积

并查缴类似排序合并法

笛卡尔积一般嵌套循环合并

7.3关系数据库系统的查询优化

分布式数据库:总代接=I/O代价+*****

7.3.2查询优化实例

假定学生-课程数据库中有1000个学生记录,10000个选课记录

其中选修二号课程的选课记录为50个

查询选修了2号课程的学生姓名

第一种情况

1.计算广义笛卡尔积

-把student和sc的每个元组连接起来的做法

2.做选择操作

依次读入连接后的元组,按照选择条件选取满足要求的记录

3.做投影操作

把第二步操作的结果在Sname上作投影输出,得到最终输出

第二种情况

1.计算自然连接

2.读取中间文件块,进行选择操作

3.投影输出

第三种情况

1.先对sc表进行选择运算

2.读取Student表,把读入的student元组和内存中收到sc元组做连接

3.把连接结果投影输出

假如SC表的Cno字段/Student表上的Sno有索引,可加快读取

有选择和连接操作时,先做选择操作–代数优化

选择操作算法有权标扫描和索引扫描两种,在第三种情况下,索引扫描效果好–物理优化

7.3.3 代数优化

关系代数表达式的等价变换规则

指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的

常用的等价变换规则

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

启发式规则

1. 选择运算尽可能先做,最重要最基本的一条
2. 把投影运算和选择运算同时进行
3. 把投影同其前后的双目运算结合起来
4. 把某些选择同在它前面要执行的笛卡尔积结合起来形成一个连接运算’
5. 找出公共子表达式

代数优化算法

输入:一个查询树

输出:优化的查询树

物理优化

代数优化改变查询语句中操作的次序和组合,不涉及底层的存取路径

定义:选择高效合理的操作算法/存取路径

基于存取路径的优化

选择操作的启发式规则–

1. 对于小关系,使用全表顺序扫描,即使有索引

2. 对于大关系–

   1. 对于选择条件是主键=值的查询
      选择主键索引
   2. 对于选择条件是非主属性=值的查询,且选择列上有索引
      估算查询结果的元组书目–比例小(10%),索引,比例大-全表
   3. 选择条件是属性上的非等值查询或范围查询,且存在索引
      估算查询结果的元组书目–比例小(10%),索引,比例大-全表
   4. 对于用and连接的合取选择条件
      优先采用组合索引扫描….
   5. or连接
      一般全表

连接操作的启发式规则

1. 两个比哦啊都已经按照连接属性排序
   排序合并法
2. 一个表在连接属性上有索引
   索引连接法
3. 都不是1,2,而其中一个表比较小
   散列连接法
4. 可以选用嵌套循环阀,并选择较小的表作为外表

基于代价估算的优化

二者结合的优化