第9章 9.3 代数优化.ppt

1、第九章 关系查询处理及其查询优化,9.1 关系数据库系统的查询处理 9.2 关系数据库系统的查询优化 9.3 代数优化 9.4 物理优化 9.5 小 结,RDBMS查询处理步骤,9.3 代 数 优 化,要解决两个问题： 如何构造查询树（语法分析树）？ 如何进行代数优化？依据（规则）是什么？ 代数优化： 是指关系代数表达式的优化。各种关系查询语言都可以等价地 转换为关系代数表达式，因此关系代数表达式的优化是查询优 化的基本课题 代数优化策略：通过对关系代数表达式的等价变换来提高查询效率,9.3.1 查询优化的一般准则,选择运算应尽可能先做 在优化策略中这是最重要、最基本的一条。 在执行连接前对关

2、系适当地预处理（建立索引，排序） 预处理方法主要有两种： 第一种称为索引连接方法。在连接属性上建立索引，然后执行连接。 第二种称为排序合并连接方法。将关系中元组按某个值排序，然后执行连接 将投影运算和选择运算同时进行 如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系,9.3.1 查询优化的一般准则,将投影同其前或其后的双目运算结合起来，减少扫描关系的次数 将某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算，连接运算比笛卡尔积省很多时间 找出公共子表达式： 如果这种重复出现的子表达式的结果不是很大的关系并且从外存中读入这个

3、关系比计算该子表达式的时间少得多，则先计算一次公共子表达式并把结果写入中间文件是合算的 定义视图的表达式就是公共子表达式的情况,9.3.2 关系代数表达式的等价变换规则,关系代数表达式的等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的 两个关系表达式E1和E2是等价的，可记为E1E2 常用的等价变换规则： 1）连接、笛卡尔积的交换律 设E1和E2是关系代数表达式 F是连接运算的条件 2）连接、笛卡尔积的结合,9.3.2 关系代数表达式的等价变换规则,3）投影的串接 4）选择的串接 5）选择与投影的交换 6）选择与笛卡尔积的交换,9.3.2 关系代数表达式的等价变换规则,7)选

4、择与并的交换 8）选择与差的交换 9）投影与笛卡尔积的交换 10）投影与并的交换,9.3.3 关系代数表达式的优化步骤,1、构造查询树 第一步：把用高级语言定义的查询转换为关系代数表达式。 以SELECT子句对应投影操作，以FROM字句对应笛卡尔积，以WHERE子句对应选择操作，生成原始查询树。 SQL语句转化为原始查询树,9.3.3 关系代数表达式的优化步骤,第二步：把关系代数表达式转换为查询树。 查询树是一种表示关系代数表达式的树形结构。在一个查询树中，叶子结点表示关系，内结点表示关系代数操作。查询树以自底向上的方式执行：当一个内结点的操作分量可用时，这个内结点所表示的操作启动执行，执行结

5、束后用结果关系代替这个内结点。 例 给定一个用SQL语言定义的查询： SELECT A FROM R1,R2,R3 WHERE P=15 AND N=“User”,A(P=15 AND N=User(R1R2R3),9.3.3 关系代数表达式的优化步骤,2、利用等价转换规则反复地对查询表达式进行尝试性转换，将原始的语法树转换成“优化”的形式 利用等价变换规则4把形如F1F2Fn(E)变换为 F1(F2(Fn(E)。目的是使选择操作可以灵活方便地沿查询树下移 对每一个选择，利用等价变换规则49尽可能把它移到树的叶端。目的是使选择操作尽早执行 对每一个投影利用等价变换规则3，9等的一般形式尽可能把

6、它移向树的叶端。目的是使投影操作尽早执行 对每个叶节点加必要的投影操作，以消除对查询无用的属性。 如果笛卡尔乘积后还须按连接条件进行选择操作可将两者组 合成连接操作。,9.3.3 关系代数表达式的优化步骤,把上述得到的“优化”后的语法树的内节点分组。 每一双目运算（，-）和它所有的直接祖先为一组（这些直接祖先是，运算）。 如果其后代直到叶子全是单目运算，则也将它们并入该组。 生成一个查询代码，每组结点的计算是程序中的一步(即每一步计算一个子树)。各步的顺序是任意的，只要保证任何一组的计算不会在它的后代组之前计算。,9.3.4 查询优化实例,设有S(供应商)，P(零件)，SP(供应关系)三个关系

7、，关系模式如下： S(SNUM,SNAME,CITY) P(PNUM,PNAME,WEIGHT,SIZE) SP(SNUM,PNUM,DEPT,QUAN),有如下语义查询：查询来自南京的供应数量大于10000的bolt零件的供应商的名称。 1、SQL语句： Q : SELECT SNAME FROM S,P,SP WHERE S.SNUM = SP.SNUM AND SP.PNUM = P.PNUM AND S.CITY = NANJING AND P.PNAME = BOLT AND SP.QUAN 10000,9.3.4 查询优化实例,2、构造查询树,Q : SELECT SNAME FROM S,P,SP WHERE S.SNUM = SP.SNUM AND SP.PNUM = P.PNUM AND S.CITY = NANJING AND P.PNAME = BOLT AND SP.QUAN 10000,9.3.4 查询优化实例,选择操作尽量下移,原始查询树,9.3.4 查询优化实例,消除对查询无用的属性,优化算法练习,学生-课程关系数据库中包括以下关系模式： S（S#，Sname，Age，Sex） SC（S#，C#，