如何做好厦门大学计算机科学系

《如何做好厦门大学计算机科学系》由会员分享，可在线阅读，更多相关《如何做好厦门大学计算机科学系（44页珍藏版）》请在金锄头文库上搜索。

1、,厦门大学计算机科学系 2017版,林子雨 厦门大学计算机科学系 E-mail: 主页：http:/ 数据库查询优化 （2017版）,厦门大学计算机科学系本科生课程 数据库系统原理,扫一扫访问班级网站 支持手机浏览,第9章 数据库查询优化,9.1 关系数据库系统的查询处理 9.2 关系数据库系统的查询优化 9.3 基于半联接的查询优化 9.4 基于枚举法的查询优化,9.1 关系数据库系统的查询处理,9.2 关系数据库系统的查询优化,查询优化的必要性 查询优化极大地影响RDBMS的性能。 查询优化的可能性 关系数据语言的级别很高，使DBMS可以从关系表达式中分析查询语义。,9.2 关系数据库系

2、统的查询优化,用户不必考虑如何最好地表达查询以获得较好的效率 系统可以比用户程序的优化做得更好 (1) 优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息,9.2 关系数据库系统的查询优化,(2)如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。 在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。 (3)优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。 (4)优化器中包括了很多复杂的优化技术,9.2 关系数据库系统的查询优化,查询优化的总目标 选择有效策略，求得给定关系表达式的值 实际系统的查询优化步

3、骤 1. 将查询转换成某种内部表示，通常是语法树 2. 根据一定的等价变换规则把语法树转换成标准 （优化）形式,例：有查询Q1：查询北部地区（AREA=North）所属部门发出订单的供应商号。这里涉及两个全局关系Dept(D#,DNAME,MGTRSSN,AREA)和Sp(S#,P#,D#,QUAN)，SQL表达式为： Select S From Dept, Sp Where SpD=Dept.D And AREA=North; 其相应的代数表达式为： S#AREA=North（Sp Dept） D=D 其相应的查询树如下： s# AREA=Nouth D=D Sp Dept,查询树,显然，边

4、为 E1（ ，Sp ） D=D 时，则Sp是非叶节点 的分量。,查询表达式的等价性,例：对关系 Emp,有如下SQL查询表达式 Select ENAME,DNO From Emp Where DNO=15; （4-1） 其相应的代数操作表达式为： ENAME，DNO（DNO=15 Emp） （4-2） 或 DNO=15（ENAME，DNO Emp） （4-3） 本例表示了不同的操作顺序仍可获得相同的结果。这就是等价的概念。 定义4.2：两个查询表达式 E1 和 E2 是等价的，如果其 查询的结果是相同的，记为 E1 E2。,9.2 关系数据库系统的查询优化,3. 选择低层的操作算法 对于语法树

5、中的每一个操作 计算各种执行算法的执行代价 选择代价小的执行算法 4. 生成查询计划(查询执行方案) 查询计划是由一系列内部操作组成的,查询树可以理解为全局查询树 根据等价定义，可用三种方式描述查询： SQL表达式（查询语句） 代数表达式 查询树,代价模型,集中式数据库 单用户系统 总代价 = I/O代价 + CPU代价 多用户系统 总代价 = I/O代价 + CPU代价 + 内存代价 分布式数据库 总代价 = I/O代价 + CPU代价+ 内存代价 + 通信代价,9.3 基于半联接的查询优化,4.5.1 联接操作重要性 4.5.2 联接操作 4.5.3 半联接操作原理和不对称性 4.5.4

6、半联接操作的缩减作用 4.5.5 半联接程序的作用 4.5.6 半联接程序的具体过程 4.5.7 半联接技术的不足,9.3.1 联接操作重要性,关系数据库由许多关系组成，关系与关系之间的联系主要通过联接操作表现出来，因而在二元操作中，联接操作远比其它操作用得多。 讨论联接，其实包括了“选择投影联接”的综合问题，即二元操作和一元操作的综合优化问题。 分布式查询处理的联接操作，更是影响分布式查询效率的最关键因素。 在DDB中，联接操作的大量数据会引起场地间的传输，它直接影响整个系统性能。 当前对联接操作的优化有两种趋向： 一种是采用半联接技术来减少联接操作的操作数，以降低通讯费用； 另一种是直接进

7、行联接操作的代价计算,9.3.2 联接操作,联接操作是从两个关系的笛卡尔积中选取属性间满足一定条件的元组。记作：,其中A和B分别为R和S上可比的属性组。,自然联接（Natural join）是一种特殊的等值联接，它要求两个关系中进行比较的分量必须是相同的属性组，并且要在结果中把重复的属性去掉。即若R和S具有相同的属性组B，则自然连接可记作：,等值连接（equi-join），为“”的连接运算称为等值连接。它是从关系R与S的笛卡尔积中选取A、B属性值相等的那些元组。即等值连接为：,（回顾）自然联接,图 自然联接实例,自然联接的结果是在 R 和 S 中的在它们的公共属性名字上相等的所有元组的组合。例

8、如下面是表格“雇员”和“部门”和它们的自然联接:,（回顾）等值联接,图 -联接实例,-联接和等值联接 如果我们要组合来自两个关系的元组，而组合条件不是简单的共享属性上的相等，则有一种更一般形式的连接算子才方便，这就是 -联接(或 theta-联接)。 是在集合 , 中的二元关系。的结果由在 R 和 S 中满足关系 的元素的所有组合构成。只有 S 和 R 的表头是不相交的，即不包含公共属性的情况下，-连接的结果才是有定义的。 实例：考虑分别列出车模和船模的价格的表“车”和“船”。假设一个顾客要购买一个车模和一个船模，但不想为船花费比车更多的钱。在关系上的-联接 CarPrice BoatPric

9、e 生成所有可能选项的一个表。,9.3.3 半联接操作原理和不对称性,半联接操作是关系代数操作中联接（JOIN）操作的一种缩减，关系R和S的半联接记为RS。其结果关系是R和S的自然联接（Natural JOIN）后，在R的属性上的投影，可用下述表达式表示： RS=R（RS）,等价方法：将S中与R有相同属性名的属性集投影出来，然后与R完成自然联接，其等价公式为： RS=R （BS）,具不对称操作性：RSSR。,（回顾）半联接,图 半联接实例,半联接的结果只是在 S 中有在公共属性名字上相等的元组所有的 R 中的元组。 实例：“雇员”和“部门”和它们的半联接的表:,9.3.4 半联接操作的缩减作用

10、,例4.17 有R（A,B）和 S（B,C），根据半联接计算公式有： 和 。如果有图 4.21（a）的实例，则 R S的结果如 4.21（b）所示，S R的结果如图4.21（C）所示。,图4.12 半联接操作的不对称性与缩减作用,从图4.21（b）、（c）可得出结论：半联接操作对操作数R或S有缩减作用，且由于其不对称性则各自缩减的程度不一样。半联接操作的缩减性与在联接操作前先对操作数关系做选择和投影有相似的效果。特别在分布式环境中，可用半联接操作减少网上数据的传送量。,9.3.5 半联接程序的作用,半联接程序是用半联接技术实现联接操作的程序，即用一组具有半联接与联接的操作，映射出具有与等值联接

11、相同结果的过程。,(4-11a),(4-11b),（411a）、（411b）式说明半联接程序与两个关系的直接等值联接等价。,同样，在分布式数据库中，当R，S两个关系不在相同场地上时，用（411a）公式或（411b）公式处理，可以减少联接操作的数据传送量，并且半联接程序的技术可以缩减它的操作数。,9.3.6 半联接程序的具体过程,以式（4-11a）为例，且假定 R和S不在同一场地： 在s场地对S关系做投影操作，使S关系缩减为S：, 将S送往r场地；, 在r场地上完成R与S的半联接操作，使R关系缩减为R：, 将R关系送回S场地；, 在S场地完成R与S的联接操作。,图4.22 半联接程序操作,图4.

12、22的核心技术思想是只将联接操作有关的操作分量在网上进行传输。R与S关系在A=B条件下联接，R、S关系只有公共属性值相等的那些元组才有意义。,半联接技术是通过局部缩减操作关系的数据量，发送缩减的关系到执行场地，在执行场地对缩减后的关系进行查询处理。 采用该技术大大降低了场地间传递的信息量，从而减少了整个系统的传输代价。 但是，半联接技术使传输代价降低的同时，也增加了系统的局部处理代价。因此，半联接技术有如下不足： （1）没有考虑局部代价。 （2）当选择度较低时，半联接技术才能够达到减少传输代价的效果。,9.3.7 半联接技术的不足,9.4.1 概述 9.4.2 嵌套循环联接算法 9.4.3 基

13、于排序的联接算法 9.4.4 散列连接算法,9.4 基于枚举法的查询优化,半联接优化方法能够减少查询执行的通信代价，但是同时会导致通信次数的增加和局部执行代价的增加。 当系统环境为高速局域网时，查询执行代价主要考虑的是局部处理代价，半联接优化方法则不再适用。 在这种情况下，分布式数据库系统通常使用基于直接联接技术的枚举法优化技术。 所谓枚举法优化，就是枚举联接操作所有可行的直接联接算法，通过对每种方法的查询执行代价估计，从中选择一种代价最小的算法作为联接操作的执行算法。 直接联接算法广泛应用于集中式数据库系统中，包括：嵌套循环连接算法、归并排序连接算法、散列连接算法和基于索引的连接算法。,9.

14、4.1 概述,9.4.2.1 基于元组的嵌套循环联接 9.4.2.2 基于块的嵌套循环联接 9.4.2.3 嵌套循环联接方法的代价估计,9.4.2 嵌套循环联接算法,嵌套循环连接算法是一种最简单的联接算法，其原理是对联接操作的两个关系对象中的一个仅读取其元组一次，而对另一个关系对象中元组将重复读取。 嵌套循环联接算法的特点是可以用于任何大小的关系间的连接操作，不必受连接操作所分配的内存空间大小的限制。 对于嵌套循环连接算法，可根据每次操作的对象大小分为基于元组的嵌套循环连接和基于块的嵌套循环连接。,9.4.2.1 基于元组的嵌套循环联接,图4.13 两个联接关系,假设有关系R(A,B)和关系S

15、(B,C)，分别有Card(R)=n和Card(S)=m，现在要执行两个关系在属性B上的连接操作，如图4.13所示。,基于元组的嵌套循环连接 Result = ;/*初始化结果集合*/ For each tuple s in S For each tuple r in R If r.B=s.B then /*元组r和元组s满足连接条件*/ Join r and s as tuple t; Output t into Result;/*输出连接结果元组*/ Endif Endfor Endfor Return Result,9.4.2.1 基于元组的嵌套循环联接,上面基于元组的嵌套循环连接算法中，对于循环外层的关系，通常称为外关系，而对循环内层的关系称为内关系。 在执行嵌套循环连接时，仅对外关系进行1次读取操作，而对内关系则需要进行反复读取操作。 如果不进行优化的话，这种基于元组的执行代价很大，以磁盘IO计算最多可能达到Card(R)*Card(S)。 因此，通常对这种算法进行修改，以减少嵌套循环连接的磁盘IO代价。一种方法是使用连接属