关系系统及查询优化

1、关系系统及查询优化 关系系统的定义、分类 全关系系统的十二条基本准则 查询优化的目标、步骤 查询优化的实例 查询优化的一般准则 关系代数表达式的优化算法一、关系系统定义 关系系统：支持关系模型的数据库管理系统称为关系关系系统：支持关系模型的数据库管理系统称为关系系统。系统。（笼统） 关系模型中并非每一部分都同等重要，并不苛求一个实际的关系数据库 管理系统必须完全支持关系模型，也不苛求完全支持关系模型的系统才能称为关系系统。 一个系统可定义为关系系统，当且仅当它一个系统可定义为关系系统，当且仅当它至少至少： 1、支持关系数据结构（表） 2、支持选择、投影和（自然）连接运算，对这些运算 不要求用户

2、定义任何物理存取路径。 对关系系统的最低要求关系系统的定义（续） 不支持关系数据结构的系统显然不能称为关系系统 仅支持关系数据结构，但没有选择、投影和连接运算功能的系统仍不能算作关系系统。 原因：不能提高用户的生产率 支持选择、投影和连接运算，但要求定义物理存取路径，这种系统也不能算作真正的关系系统 原因：就降低或丧失了数据的物理独立性 选择、投影、连接运算是最有用的运算二、关系系统的分类前面定义的关系系统是关系系统的最小要求。按照E.F.Codd的思想，可以把关系系统分类：1、表式系统 仅支持表数据结构，不支持集合级的操作，不能算关系系统。2、最小关系系统支持关系数据结构和三种关系操作。（F

3、oxBase, FoxPro等）3、关系完备的系统支持关系数据结构和所有的关系代数操作（功能上等价）。4、全关系系统支持关系模型的所有特征。即不仅是关系上完备的，而且支持数据结构中域的概念，支持实体完整性和参照完整性。（目前大多数关系系统已接近或达到了这个目标）关系系统的分类 （续） 数据结构数据结构数据操作数据操作完整性完整性表式系统表式系统表表 (最小最小)关系系统关系系统表表选择、投影、选择、投影、连接连接 关系完备的系统关系完备的系统表表 全关系系统全关系系统 全关系系统的十二条基本准则 这是关系模型的奠基人E.F.Codd从理论和实际紧密结合的高度，对关系型DBMS的评述。从实际意义

4、上看，这十二条准则可以作为评价或购买关系型产品的标准。 详细见书。三、关系系统的查询优化非关系系统中，用户使用过程化的语言表达查询要求、执行的操作以及操作序列，用户必须了解存取路径，查询效率由用户的存取策略决定，需要用户对 查询程序进行“优化”。而在关系系统中，用户只需提出“干什么”，而不必指出“怎么干”，由系统来确定存取策略，提高查询效率，即完成查询优化的工作。查询优化在关系数据库系统中有着非常重要的地位，是影响RDBMS性能的关键因素。系统的“优化器”功能与用户“优化工作”对比：1）可以从数据字典中获取许多统计信息2）如果物理统计信息改变了，前者可重新优化选择相适应的执行计划，而后者必须重

5、新写程序，而实际应用中往往不太可能。3）前者可考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。4）前者包括了很多复杂的优化技术，往往只有最好的程序员才能掌握。系统的自动优化使得所有人都拥有这些优化技术。查询优化的一般步骤1）将查询转换成某种内部表示，通常是语法树（关系代数语法树）。2）根据一定的等价变换规则把语法树转换成标准形式（优化形式）。可采用关系代数表达式的优化算法自动进行优化。3）选择低层的操作算法，即确定存取路径。对于语法树中的每一个操作需要根据存取路径（有无索引）、数据的存储分布、存储数据的聚簇等信息来选择具体的执行算法。4）生成查询计划（执行方案），选择代价最小的

6、。对每个执行计划计算代价，从中选择代价最小的一个。在集中式关系数据库中，计算代价时主要考虑磁盘读写的I/O次数，也有一些系统换考虑了CPU的处理时间。目前的商品化RDBMS答对采用基于代价的优化算法： 这种方法要求优化器充分考虑系统中的各种参数（如缓冲区大小、表的大小、数据的分布、存取路径等）。集中式数据库：总代价=I/O代价+CPU代价 （时间）多用户数据库：总代价=I/O代价+CPU代价 +内存代价 （时间）查询优化的一般准则1）选择运算应尽可能先做。因为它可使计算的中间结果大大变小。2）在执行连接（自然连接）前对关系适当地预处理。主要有两种方法，在连接属性上建立索引和对关系排序，然后执行

7、连接。（详细见书 P.161）3）把投影运算和选择运算同时进行。当他们对同一个关系操作，则可以在扫描关系的同时完成所有的这些运算来避免重复扫描关系。4）把投影和其前或其后的双目运算结合起来，没有必要为了去掉某些字段而扫描一遍关系。5）把某些选择同在它前面要执行的笛卡儿积结合起来成为一个连接运算，连接特别是等值连接运算要比同样关系上的笛卡儿积省很多时间。6）找出公共子表达式，如果这种重复出现的子表达式结果不是很大，从外存读入结果比计算该子表达式的时间少得多，可先计算一次该子表达式并把结果写入中间文件是合算的。如查询的是视图，定义视图的表达式就是公共子表达式的情况。关系代数等价变换规则 各种查询语

8、言都可以转换成关系代数表达式，因此查询优化可以转换为对关系代数表达式的优化。而其优化的基础是关系代数表达式的等价变换规则。 等价：等价：如果用相同的关系来代替两个表达式中相应的关系所得到的结果是相同的，则说这两个关系代数表达式E1、E2是等价的，记为E1E2。 常用的等价变换规则：常用的等价变换规则：10条（见书P.162-164）。 关系代数表达式的优化原则：关系代数表达式的优化原则：应用等价变换规则来优化关系表达式，使得优化后的表达式能遵循查询优化的一般准则，如把选择和投影尽可能地早做（即把它们移到表达式语法树的下部，叶端）。关系代数表达式的优化算法算法：关系表达式的优化。输入：一个关系表

9、达式的语法树。输出：计算该表达式的程序。1）利用规则4把形如F1F2 Fn(E)变换为 F1( F2( Fn(E)。2）对每个选择，利用规则4-8尽可能把它移到树的叶端。3）对每个投影，利用规则3，9，10，5中的一般形式尽可能把它移向树的叶端。4）利用规则3-5把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。使得多个选择或投影能同时执行，或在一次扫描中全部完成。5）将得到的语法树的内结点进行分组。每一双目运算和它所有的直接祖先（ ， ）为一组；如果其后代直到叶子全是单目运算，则也将它们并入该组；但当双目运算是笛卡儿积，而且其后的选择不能与它结合为等值连接时,则一直到叶子的一

10、目运算结点须单独立一组。6）自动生成一个程序。每组结点的计算是程序中的一步。各步的顺序是任意的，只要保证任何一组的计算不会在它的后代组之前计算。7）执行时从叶端依次向上进行，每组运算只对关系进行一次扫描。优化的一般步骤（1）把查询转换成某种内部表示 通常是（关系代数）语法树，以4.2.2节中的实例为例。（2）把语法树转换成标准（优化）形式。 语法树最终的优化形式语法树最终的优化形式（运用了哪些变换规则？） Sname Student.Sno=SC.Sno Sname,Sno Sno Student Cno=2 SC StudentCno=2SCSnameStudent.Sno=SC.SnoSn

11、ame, Student.Sno, SC.Sno（3）选择低层的存取路径 根据第（2）步得到的优化了的语法树计算关系表达式值的时候要充分考虑索引、数据的存储分布等存取路径，利用它们进一步改善查询效率。 优化器查找数据字典获得当前数据库状态信息选择字段上是否有索引连接的两个表是否有序连接字段上是否有索引 然后根据一定的优化规则选择存取路径（4）生成查询计划，选择代价最小的）生成查询计划，选择代价最小的 查询计划是由一组内部过程组成的，这组内部过程实现按某条存取路径计算关系表达式的值。 在作连接运算时，若两个表(设为R1，R2)均无序，连接属性上也没有索引，则可以有下面几种查询计划： 对两个表作排

12、序预处理 对R1在连接属性上建索引 对R2在连接属性上建索引 在R1，R2的连接属性上均建索引 对不同的查询计划计算代价，选择代价最小的一个。 在计算代价时主要考虑磁盘读写的I/O数，内存CPU处理时间在粗略计算时可不考虑。实例_查询优化的实例 SELECT Student.Sname FROM Student,SC WHER Student.Sno=SC.Sno AND SC.Cno=2;系统可以用多种等价的关系代数表达式来完成这一查询： 如 q1= sname( student.sno=o=2(studentsc) q2= sname( o=2(student sc) q3= sname(

13、student o=2(sc)这三种不同的查询执行策略，其查询时间相差很大。可通过某种代价模型(如只计算I/O时间代价)，粗略计算出各种查询执行方案的代价，选择代价最小的来实现查询。实例_查询优化的实例 读取Student和SC表的策略Student表SC表100个SC元组内存缓冲区中间文件10个Student元组10个连接后的元组第一个五块第二个五块 共一千个学生记录 共一万个选课记录 第1100个元组第101200个元组 第110个元组第1120个元组第一块第二块第 n 块 Student表第1个五块的元组 SC表第1块的元组 SC表第2块的元组 SC表第n块的元组 Student表第2个五块的元组 SC表第1块的元组 SC表第2块的元组 SC表第n块的元组 Student表最后五块的元组 SC表第1块的元组 SC表第2块的元组 SC表第n块的元组 假设1：1000个学生记录，10000个选课记录，在内存中存放5块Student元组和一块SC元组，一块能装10个学生记录或100个选课记录。 则读取总块数为： 1000 1000 10000 10 105 10