查询优化技术(1)

1、整理ppt第七章第七章 查询优化技术查询优化技术 查询处理器是数据库管理系统DBMS的一个部件，它把用户的查询命令转换成对数据库的一连串操作。鉴于用查询语言SQL表达查询是在较高的层次上，查询处理器必须提供如何进行查询的诸多细节。整理ppt 设S是一个存储有关学生信息的关系，包括学号S#和姓名SN等属性。SC是存储学生选课情况的关系，包括学号S#和课程号C#等属性。下边的SQL语句表示查询“列出所有选修课程C2的学生姓名”：SELECT DISTINCT S.SNFROM S, SCWHERE S.S#SC.S# AND SC.C#“C2”。查询优化例查询优化例整理ppt 假定S中包含1000

2、个学生记录，SC中包含10000个选课记录，其中选修C2课程的选课记录为50个。我们用三个等价的关系代数表达式来表示这个查询的三种处理策略： Q1=SN(s.s#sc.s#) (sc.c#=”c2”)(ssc)； Q2SN(sc.c#”c2”) (s s.s#=sc.s# sc)； Q3SN(sc.c#”c2”sc s.s#=sc.s# s)三种查询处理策略整理ppt Q1=SN(s.s#sc.s#) (sc.c#=”c2”)(ssc) 执行过程和时间开销分析(1)计算S和SC的笛卡尔积。步骤1，使用一个内存缓冲区BS读入某个关系(如S)的未处理元组；步骤2，使用另一个内存缓冲区BSC读入另一

3、个关系(如SC)的未处理元组；步骤3，把BS中的每个元组和BSC中每个元组相连接，并送人输出缓冲区BO；步骤4，如果BO已满则写到一个临时文件； 步骤5，重复步骤，直至SC中元组全部处理完； 步骤6，重复步骤，直至S中元组全部处理完。整理ppt 设BS能装50个S的元组，BSC能装100个SC的元组，每个磁盘块能装10个S的元组或100个SC的元组。上述算法需要读关系S的100个磁盘块数据，需要20遍读SC关系，每遍读100个磁盘块，读取总块数为：2100。 若每秒可读20个磁盘块，则总计要花105秒。 S和SC的笛卡尔积的结果元组数为10000000。设每个磁盘块能装5个结果元组，则结果元组

4、的写出要花费100000秒(设每秒写20块)。 整理ppt (2)从临时文件读入S和SC的笛卡尔积，按照选择条件选取满足要求的记录。这一步读取中间文件花费的时间为100000秒(同写中间文件一样)。 (3)把第2步的结果在SN上作投影输出，得到最终结果。设满足条件的元组数为50，可存放在内存中。忽略CPU时间，Q1需要的处理时间大于200105秒。整理ppt Q2的处理过程和时间开销分析 (1)计算自然连接。为了执行自然连接，读取S和SC表的策略不变，总的读取块数仍为2100块，需要105秒的时间。但自然连接的结果大大减少，为l000个元组。因此写出这些元组花费的时间为l0秒。 (2)读取中间

5、文件块，执行选择运算，花费时间也为10秒。 (3)把第2步结果投影输出。如果忽略CPU时间，Q2的处理时间约为125秒。整理ppt Q3的处理过程和时间开销分析 (1)先对SC作选择运算，只需读一遍SC表，存取100块花费时间为5秒。因为满足条件的元组仅50个，不必使用中间文件。 (2)读取S表，把读入的S元组和内存中的SC元组作连接。这一步只需读一遍S，共100块，需要5秒钟的时间。 (3)把连接结果投影输出。 忽略CPU时间，Q3的处理时间约为10秒。整理ppt 本章的开始部分，将考察用于改善逻辑查询方案的各种代数法则。并考察每一种关系代数算符的可能算法。将一个逻辑查询方案转换为一个物理查

6、询方案，不仅要定义出所用的算子，还要给出如何实现算子及如何将数据传给另一算子的方法。本章主要内容整理ppt 关系代数关系代数 传统的关系代数假设关系是在集合的基础上设计出来的，而SQL中的关系实际上是包(bag)，或称多重集。也就是说， SQL关系中可以存在任意个重复元组。因此，我们将引入一种包上的关系代数。整理ppt 并，交，差并，交，差在RS中，元组t 在运算结果中出现的次数，等于在R中出现的次数与S中出现的次数之和。在RS中，元组t 在运算结果中出现次数，是R中出现次数与S中出现次数的较小者。在R-S中，元组t 在运算结果中出现次数，等于R中出现次数减去S中出现次数之差，但不少于零它们对

7、应着SQL中的UNION, INTERSECT和EXCEPT运算。整理ppt 选择运算选择运算 假设R是一个关系，C是条件, 则C(R)表示对关系R进行选择运算。 它是R中符合条件C的元组的包。运算结果的域与R的域相同。 运算被称为关系代数的选择运算。整理ppt 投影运算投影运算若R是一个关系，则L（R）为R在投影属性表L上的投影。将扩充这一运算，使之模拟SQL的SELECT子句。 允许属性的重命名，用来指示重命名。例如， L中的成员xy表示取R的x属性列并重新命名为y。 允许表L中包括属性的算术或条件运算。 若L的成员不是单个的属性，则必须由箭号和属性来命名表达式的结果。整理ppt例例 7.

8、3 7.3 令 R 为如下的关系：abc012012345则a,b+cx（R）的运算结果为：ax030339整理ppt笛卡尔乘积运算笛卡尔乘积运算 若R和S是关系，则RS也是关系，其结果关系的域来自于R的域加上S的域。 若某一个属性，如a，在两个关系中都有，则在结果域中用R.a和S.a作为这两个属性的名字。 结果关系的元组都是由从R中取一个元组且在这一元组的分量后接S的任一元组的分量而形成的。 若一元组r在R中出现n次，另一元组s在S中出现m次，则元组rs在结果中出现nm次。整理ppt 假设 R(a,b)为关系: ab012323 关系 S(b,c)为: bc141425整理ppt图图 7 7

9、. .2 2 关系 R 和 S 的积aR.bS.bc011401140125231423142325231423142325整理ppt 连接运算连接运算 最简单的连接是自然连接；我们用RS来表示R和S的自然连接。 自然连接可分解为 L（C(RS)），其中：.C是使R和S中所有同名的属性对相等的条件。.L是R和S的所有属性的列表，只是每一对相等的属性中去掉一个。若R.x和S.x是相等的属性，则因为在投影的结果中只有一个属性x， 任取R.x和S.x之一, 并重新命名为x。整理ppt 用于改善查询方案的代数定律用于改善查询方案的代数定律 关系代数表达式可以用树结构来表示。在不改变查询结果的前提下，将

10、这棵树进行变换，以达到降低查询的时间和空间复杂性的目的。这一工作称为关系代数优化。 这一工作是在较高的抽象层次上即逻辑数据结构层上进行的。整理ppt查询的符号表示形式：查询树 查询树是一种表示关系代数表达式的树形结构。在一个查询树中，叶子节点表示关系，内部节点表示关系代数操作。查询树以自底向上的方式执行： 当一个内部节点的操作分量有值时，这个内部节点所表示的操作开始启动执行，执行结束后用结果关系代替这个内部节点。整理ppt给定一个用SQL语言定义的查询：SELECT listFROM R1，R2，RnWHERE C其中，C是条件表达式，list是输出属性表。可以按照如下方法把这个查询转换为关系

11、代数表达式：1）使用FROM从句中的关系R1、R2、Rn构造笛卡尔乘积R1R2Rn；2）在第1步的基础上构造一个选择操作：C（R1R2Rn）；在第2步的基础上构造一个投影操作：list(C（R1R2Rn）)。整理ppt 假设有关系MovieStar(name,addr,gender,birthdate)StarsIn(title,year,starName)从中我们要查找出那些在1996年的影片中出现的女演员的出生日期和影片名：SELECT title, birthdateFROM MovieStar, StarsInWHERE year=1996 AND gender=F AND starN

12、ame=name;整理ppt整理ppt等价的表达方式下图中所用的方案与上图明显不同。第一，应用于两个关系的乘积上的WHERE子句中的条件starName=name是一个等值连接。一般地，连接运算产生的元组比乘积运算产生的结果元组要少，因此，如有可能，尽量使用连接运算。第二，WHERE子句的其他两个条件被分成了两个运算，并且两个运算都被顺着树往下移。其中，因为选择运算year=1996只涉及到StarsIn的一个属性year，所以，它可直接应用到关系StarsIn之上。整理ppt有几个关系代数的运算符是既可结合又可交换的。例如：1 RSSR； （RS）TR（ST） 。2 RSSR； （RS）TR

13、（ST） 。3 RSSR； （RS）TR（ST） 。4 RSSR； （RS）TR（ST） 。注意不管关系是集合还是包，以上所述的并和交的规则总是适用的。整理ppt的两个分离规则：lC1 AND C2(R)C1 (C2(R)。lC1 OR C2(R) (C1 (R) (C2(R)。注意和的次序是灵活的。例如，我们也可以把上面的第一个规则写成在之后进行操作，即C2(C1(R)。实际上，运算符的次序可任意交换。lC1 (C2(R) C2(C1(R)。 优化查询过程的一个最重要的思想，是不改变表达式的作用而尽量将选择操作顺着查询树往下移整理ppt例例 给出关系R（a，b）、S（b，c）和表达式(a=1

14、 OR a=3) AND bc (RS)。条件bc可单独应用于S，条件a1 OR a3可单独应用于R，因此，从分解这两个条件的AND开始，得 a=1 OR a=3 (bc(R S)。接着，可以将选择bc下移至S，得到表达式： a=1 OR a=3 (R bc(S)最后，将第一个条件移至R， 生成a=1 OR a=3 (R) bc(S)整理ppt设有关系MovieStar(name,addr,gender,birthdate)StarsIn(title,year,starName)并且想知道对每一年出现在该年影片中的最年轻演员的生日。我们可以把这一查询表达为：SELECT year,MAX(birthdate)FROM MovieStar,StarsInWHERE nam