关系操作符赋值优秀PPT.ppt

《关系操作符赋值优秀PPT.ppt》由会员分享，可在线阅读，更多相关《关系操作符赋值优秀PPT.ppt（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关系操作符赋值关系操作符赋值第1页，本讲稿共71页典型的关系数据库系统体系结构典型的关系数据库系统体系结构 第2页，本讲稿共71页RDBMS系统查询处理的基本过程系统查询处理的基本过程 v当用户提出一个当用户提出一个SQL查询后，将首先被送到解析查询后，将首先被送到解析器器(parser)，进行解析和编译处理。，进行解析和编译处理。v编译后的查询接着被送到查询优化器编译后的查询接着被送到查询优化器(optimizer)优化器将利用DB系统目录中信息(System catalog)，产生一个高效的可执行计划。可执行计划是查询赋值的一个蓝图，它被表示为关系代数操作符树的形式树中的每个节点通常可对应

2、到一个具体的关系操作符。v通过调用下层的计划执行器，实现最终查询赋值通过调用下层的计划执行器，实现最终查询赋值.v关系操作符赋值是查询处理的基础，它们好比是实现整个查询赋关系操作符赋值是查询处理的基础，它们好比是实现整个查询赋值的一些基本积木块。值的一些基本积木块。v本章集中讨论单个关系操作符的赋值实现问题。本章集中讨论单个关系操作符的赋值实现问题。第3页，本讲稿共71页查询赋值计划查询赋值计划考虑下面考虑下面SQL查询例句：查询例句：SELECT S.sname FROM Reserves R,Sailors S WHERE R.sid=S.sid AND R.bid=100 AND S.r

3、ating 5 v对应的关系代数表达式：对应的关系代数表达式：sname(bid=100 AND rating5(Reserves sid=sid Sailors)第4页，本讲稿共71页一个典型的查询赋值计划树一个典型的查询赋值计划树第5页，本讲稿共71页第第6章章 关系操作符赋值关系操作符赋值6.1 外部排序外部排序 6.2 关系操作符赋值实现基础关系操作符赋值实现基础6.6 连接操作赋值连接操作赋值6.7 集合操作的赋值实现集合操作的赋值实现6.8 聚合操作的赋值实现聚合操作的赋值实现6.9 各类代数操作符赋值实现小结各类代数操作符赋值实现小结6.3 RDBMS系统的目录信息系统的目录信息

4、6.4 选择操作符赋值选择操作符赋值6.5 投影与消除重复操作赋值投影与消除重复操作赋值第6页，本讲稿共71页6.1 外部排序外部排序6.1.1 一种简单的两路归并排序6.1.2 多路归并排序6.1.3 两阶段多路归并排序6.1.4 最小化外部排序时间排序是排序是排序是DBDBDB系统系统系统最基本最基本最基本的操作的操作的操作DB系统中有很多场合需要用到排序系统中有很多场合需要用到排序u 用户可能希望以某种指定顺序返回查询结果集。用户可能希望以某种指定顺序返回查询结果集。u 排序记录集是批处理建立排序记录集是批处理建立B+树的第一步树的第一步(5.3.3)u 排序是消除一个记录集中重复记录的

5、一种有效方法。排序是消除一个记录集中重复记录的一种有效方法。u 广泛使用的关系连接操作，可基于排序的方法实现。广泛使用的关系连接操作，可基于排序的方法实现。第7页，本讲稿共71页6.1.1 简单的两路归并排序简单的两路归并排序第8页，本讲稿共71页一个含一个含7个页文件的两路归并排序个页文件的两路归并排序第9页，本讲稿共71页6.1.1 简单的两路归并排序简单的两路归并排序v在每个阶段，文件中的每个页将被读入和写出在每个阶段，文件中的每个页将被读入和写出1次，即在每阶段每个页有次，即在每阶段每个页有2次磁盘次磁盘I/Os。v如果输入文件的总页数为如果输入文件的总页数为M，则完成排序需要的，则完

6、成排序需要的总阶段数为总阶段数为 log2M+1，总的代价为，总的代价为2M(log2M+1)次次I/Os。为减小排序代价，我们应设法减少归并的阶段数。v如果可用的缓存页数不是如果可用的缓存页数不是3而是更多而是更多(令有令有B个个)，那么，那么，在第1阶段:可以使用更大的子文件；在归并阶段，可以采用比两路更多路的归并，最多允许采用B-1路归并。第10页，本讲稿共71页6.1.2 多路归并排序多路归并排序（图图6.2 B-1路归并图解路归并图解）第11页，本讲稿共71页6.1.3 两阶段多路归并排序两阶段多路归并排序 假设可用缓存页总数假设可用缓存页总数B，文件总页数为，文件总页数为Mv第第1

7、阶段阶段 划分子文件，可得子文件总数=M/B。v第第2阶段阶段 归并子文件，因只有两个阶段，要求一次完成所有子文件归并这要求排序子文件总数：M/B B-1 即要求B M1/2，否则，必须进行更多个阶段的排序。v两阶段排序的总代价为：两阶段排序的总代价为：M*4次次 I/Os 例例6.1 如果每个页的平均读写时间按如果每个页的平均读写时间按15ms计算，计算两阶段排计算，计算两阶段排序序250000个页需要的总时间。个页需要的总时间。第一个阶段要读写500000个页，需要时间为5000000.015=7500s，约125分钟。第二个阶段也需要125分钟！第12页，本讲稿共71页利用组块利用组块I

8、/O优化外部排序时间优化外部排序时间 v1次请求读写几个连续页的时间，可能远小于分别独立读写每次请求读写几个连续页的时间，可能远小于分别独立读写每个页的时间之和。个页的时间之和。1次读写同一柱面/磁道上的32个连续页的时间=6.5+7.5+32*0.5=30ms；分别读写32个页的时间32*(6.5+7.5+0.5)=464ms。v按组块读写进行外部排序按组块读写进行外部排序(设每个块含设每个块含b个页）个页）输入缓冲区和输出输出缓冲区大小：都取为一个组块大小。以组块为单位进行读写在归并阶段，一次可归并的最大子文件数为(B-b)/bv按组块读写进行外部排序按组块读写进行外部排序(设每个块含设每

9、个块含b个页）个页）输入缓冲区和输出输出缓冲区大小：都取为一个组块大小。以组块为单位进行读写在归并阶段，一次可归并的最大子文件数为(B-b)/b。v选用大组块缓冲区时，归并的阶段数会增加，即算法总的选用大组块缓冲区时，归并的阶段数会增加，即算法总的I/Os数将增加。数将增加。但这完全可从每页平均存取时间减少来得到补偿。v在现行机器条件下，即使是使用了较大的块缓冲，除非少数特在现行机器条件下，即使是使用了较大的块缓冲，除非少数特大的文件，大部分的文件排序都可以在两个阶段内完成排序。大的文件，大部分的文件排序都可以在两个阶段内完成排序。第13页，本讲稿共71页表表6.1 组块大小组块大小b=32时

10、一些外部排序需要的阶段数时一些外部排序需要的阶段数 第14页，本讲稿共71页6.2 关系操作符赋值实现基础关系操作符赋值实现基础6.2.1 关系操作符赋值实现的三个基本操作 6.2.2 存取路径6.2.3 代价计算模型 6.2.4 关系操作符赋值的实现算法分类6.2.5 迭代器技术6.2.6 主存散列表技术6.2.7 本章查询用例说明 第15页，本讲稿共71页6.2 关系操作符赋值实现基础关系操作符赋值实现基础 6.2.1 关系操作符赋值实现的三个基本操作关系操作符赋值实现的三个基本操作v循环循环(Iteration)循环检查输入关系中的每个元组。v索引索引(Indexing)如果选择或连接的

11、条件已指定，通常可使用一个索引来检查满足条件的元组。v分区分区(Partitioning)通过基于一个排序键来划分元组，我们通常能够将一个关系操作分解为针对各个分区元组的、代价更小的一组操作。排序和散列是两种最常用的分区划分技术。第16页，本讲稿共71页6.2.2 存取路径存取路径v存取路径存取路径 所有关系操作符的赋值算法，通常都必须从一个或多个关系检索元组。从关系存取元组的方式也称为存取路径。v两个最常用的存取路径两个最常用的存取路径1)关系文件扫描；2)索引加上匹配选择条件:attr op value。v如果这个如果这个attr也正好是某索引也正好是某索引I的搜索键，则称索引的搜索键，则

12、称索引I匹配选择匹配选择条件。条件。当存在多种存取路径时，称具有最小存取代价的存取路径为具有最好选择性的存取路径。第17页，本讲稿共71页6.2.3 代价计算模型代价计算模型 v关系操作符的输入对象，即关系，位于辅存关系操作符的输入对象，即关系，位于辅存(磁盘磁盘)中中v只考虑只考虑I/O代价，不考虑代价，不考虑CPU代价。而衡量代价。而衡量I/O代价的标准是需要读取或写出的页数。代价的标准是需要读取或写出的页数。v对每个关系操作符，我们将讨论几种可选的存取对每个关系操作符，我们将讨论几种可选的存取路径。在比较不同赋值计划代价时，我们统一都路径。在比较不同赋值计划代价时，我们统一都不计算写出结

13、果的代价。不计算写出结果的代价。第18页，本讲稿共71页几个可能会影响关系操作符赋值代价的重要参数几个可能会影响关系操作符赋值代价的重要参数 v位于主存缓冲池中的可用缓存页数位于主存缓冲池中的可用缓存页数B；v关系关系R实际数据的存储页数实际数据的存储页数M；v关系关系R的元组数的元组数T(R)；v关系关系R不同的元组数不同的元组数V(R,a1,a2,an)v聚簇关系及其定义聚簇关系及其定义如果R的所有元组存储在M个页或近似M个页中。如果R的元组分布在其它关系的元组之间，则称关系R是非聚簇的。扫描聚簇关系R的代价为M次I/Os；最坏情况下，扫描非聚簇R的代价为T(R)次I/Os。本书约定在没有

14、特别声明时，都默认关系是聚簇存储的。第19页，本讲稿共71页6.2.4 关系操作符赋值的实现算法分类关系操作符赋值的实现算法分类v按算法实现时，所采用的主存数据结构分类：按算法实现时，所采用的主存数据结构分类：基于排序；基于散列；基于索引。v按算法实现的难度代价：按算法实现的难度代价：一趟算法算法实现时，相应的关系表只需扫描1次；一趟半算法一个关系表只需扫描1次,但另一个关系表需扫描多次；二趟算法(算法实现时,相应的关系表需扫描2次)；多趟算法(算法实现时,相应的关系表需扫描多次)。第20页，本讲稿共71页6.2.4 关系操作符赋值的实现算法分类关系操作符赋值的实现算法分类v按操作符的操作对象

15、数分类：按操作符的操作对象数分类：一元操作实现算法如选择(c(R)、投影(L(R)、消除重复(R)、分组 L(R)等。二元操作实现算法 如连接()、并()、交()、差()、叉积()等v按是否可以分割并独立处理关系的各页来分类：按是否可以分割并独立处理关系的各页来分类：一次多元组算法。允许独立地处理关系的每个页，前后页处理结果没有相互影响，如选择(c(R)、投影(L(R)等操作。全关系算法。第21页，本讲稿共71页6.2.5 迭代器技术迭代器技术v代数操作符的迭代器接口代数操作符的迭代器接口包括：open,getnext和close三个函数它们隐藏了操作符如何实现的细节，允许我们以一致的方式看待

16、所有的操作符节点。v通过多个迭代器连接，可构成具有流水化工作方通过多个迭代器连接，可构成具有流水化工作方式的式的迭代器网络迭代器网络。第22页，本讲稿共71页例例6.3 TableScan(R)迭代器实现迭代器实现第23页，本讲稿共71页算法算法6.2 包并运算的迭代器实现算法包并运算的迭代器实现算法 第24页，本讲稿共71页6.2.6 主存散列表技术主存散列表技术 第25页，本讲稿共71页本章查询用例说明本章查询用例说明v仍用第仍用第2章章“水手值勤管理水手值勤管理DB模式模式”的三个关系的三个关系表：表：vSailors(sid:integer,sname:string,rating:in

17、teger,age:real)vBoats(bid:integer,bname:string,color:string)vReserves(sid:integer,bid:integer,day:dates,rname:string)关系关系Reserves的元组大小为的元组大小为40字节，每个字节，每个页可存储页可存储100个元组，总共有个元组，总共有1000个页。个页。关系关系Sailors的元组大小为的元组大小为50字节，每个页可字节，每个页可存储存储80个元组，总共有个元组，总共有500个页。个页。第26页，本讲稿共71页6.3 RDBMS系统的目录信息系统的目录信息6.3.1 存储在

18、DB系统目录中的信息6.3.2 DB系统目录组织结构第27页，本讲稿共71页6.3 RDBMS系统的目录信息系统的目录信息v在在DB系统目录中，一般至少都会有一些系统范围系统目录中，一般至少都会有一些系统范围的信息，如缓冲池大小、用户帐户或认证信息的信息，如缓冲池大小、用户帐户或认证信息，以及一些关于个体关系、索引或视图的信息：以及一些关于个体关系、索引或视图的信息：v对每个关系模式结构，有关信息包括：对每个关系模式结构，有关信息包括：关系名、文件名、文件结构(如堆结构)；属性名、类型、长度；关系上的每个索引名；关系上的约束定义。v对每个索引对每个索引索引名、索引结构(如B+树)；搜索键的属性

19、。v对每个视图对每个视图视图名字与定义。第28页，本讲稿共71页可供查询优化器应用的目录信息（可供查询优化器应用的目录信息（1）v关系关系R的元组数的元组数T(R)。v关系关系R元组大小元组大小ST(R)。v含关系含关系R元组的文件总页数元组的文件总页数M(R)。v关系关系R的页因子，即一个页中能存放关系的页因子，即一个页中能存放关系R元组的元组的数目数目FP(R)。若关系R聚簇存储在一个文件中，则有M(R)=T(R)/FP(R)。v关系关系R在属性在属性A上所具有的不同值数上所具有的不同值数V(A,R)。v关系关系R在属性在属性A上的等值选择基数上的等值选择基数SC(A,R)。当A为码属性时

20、SC(A,R)1；当A为非码属性时，如假定V(R,A)个不同值在R的元组中均匀分布，则SC(A,R)=T(R)/V(R,A)。第29页，本讲稿共71页可供查询优化器应用的目录信息（可供查询优化器应用的目录信息（2）v索引基数值索引基数值(Index Cardinality)：对每个索引：对每个索引I，存，存储索引所含的不同键数储索引所含的不同键数Nkeys(I)。v索引大小索引大小(Index size)：每个索引：每个索引I，存储索引文件，存储索引文件的总页数的总页数(INPages(I)。对B+树，INPages(I)存储叶子节点的总数。v索引深度索引深度(Index height)：IH

21、(I)，对于散列索引，它是桶的深度（页数）；对B+树形索引，它是非叶子的总层数。v索引范围索引范围(Index Range)：每个索引：每个索引I，可表示的最，可表示的最小键值小键值(ILow(I)和最大键值和最大键值(IHigh(I)。第30页，本讲稿共71页6.4 选择操作符赋值选择操作符赋值6.4.1 简单扫描方法 6.4.2 利用排序特性进行选择赋值6.4.3 利用索引进行选择赋值 6.4.4 一般的选择条件处理第31页，本讲稿共71页6.4 选择操作符赋值选择操作符赋值 v例例6.5 SELECT*FROM Reserves R WHERE R.rnames=Joe 令令M是关系是关

22、系R的总页数，本例中的总页数，本例中M=1000。6.4.1 简单扫描方法简单扫描方法6.4.2 利用排序特性进行选择赋值利用排序特性进行选择赋值 用二分法，定位第1个满足条件的记录。这一步的代价为O(log 2 M)。从上1步定位的位置开始扫描关系R，直到找到一条不满足条件的记录时才停止继续扫描。该步代价取决于满足条件的元组数,代价为 O(0M)对属性A上的等值选择,该步代价约SC(A,R)/FP(R)第32页，本讲稿共71页6.4.3 利用索引进行选择赋值利用索引进行选择赋值 v有能与选择条件相匹配的索引可用有能与选择条件相匹配的索引可用 v基本代价计算式：基本代价计算式：IH(I)+SC

23、(A,R)/FP(R)v有关影响因素有关影响因素索引组织结构（顺序、B+树或散列）选择条件（等值、范围或其它选择）满足条件的元组总数（索引键是否为码属性）关系元组是否聚簇存储、索引是否聚集rids是否按page-id排序。第33页，本讲稿共71页6.4.3 利用索引进行选择赋值利用索引进行选择赋值v用散列索引实现等值选择赋值用散列索引实现等值选择赋值如果在R.attr上有散列索引可用，且op是等值运算符，则利用这个散列索引进行赋值可能是最好的存取路径。例6.6 考虑例6.5查询，假定在Reserves:rname上有散列索引，一个名为Joe的人做了100个值派。分析检索这100个Reserve

24、s元组需要的代价。v基于基于B+树索引的选择赋值树索引的选择赋值例6.7 考虑Reserves上rname%C形式选择。假设名字按第1个字母均匀分布，选择结果集约含有10%的元组，即有大约10000个元组或100个页。若有rname上的一个聚集B+树索引，分析检索满足条件元组的代价。第34页，本讲稿共71页6.4.4 一般的选择条件处理（一般的选择条件处理（1）v任何复杂条件，总可改写为任何复杂条件，总可改写为CNF形式形式 conjunctive normal form,CNF 例如,(day8/9/94rname=Joe)bid=5sid=3，等价于 (day8/9/94bid=5sid=

25、3)(rname=Joe bid=5sid=3)v对子项中不含析取运算的对子项中不含析取运算的CNF形式条件，存在两形式条件，存在两条规则：条规则：对散列索引搜索键中的每个属性，如果选择条件中都有一个形式为attr=v的选择项与它对应，则该散列索引匹配对应选择条件。对树形索引搜索键前缀中的每个属性，如果选择条件中都有一个形式为attr op v的选择项与它对应，则该索引匹配对应选择条件。v相应有两种赋值选项：相应有两种赋值选项：使用文件扫描；先使用一个单索引去匹配选择条件中部分合取项，然后应用非主合取项到每个被检索的元组。第35页，本讲稿共71页6.4.4 一般的选择条件处理（一般的选择条件处

26、理（2）v对子项中含析取运算的对子项中含析取运算的CNF形式条件，存在两条形式条件，存在两条规则：规则：对(day8/9/94 rname=Joe)，当只有rname上的散列索引和sid上的散列索引可用时，文件扫描是具有最好选择性的方法。对(day(T)1/2时，两种方法总代价都是M+2T次I/Os。v两种算法的主存要求比较两种算法的主存要求比较基于排序算法要求可用缓存页数B(T)1/2以保证可按两阶段完成排序。基于散列算法要求可用缓存页数B足够容纳最大的子桶，在划分均匀情况下，要求BT/(B-1)，即B(T)1/2。但若散列划分不均匀，则可能需要比(T)1/2更大一些的B。v结论结论综合考虑

27、到排序方法的投影结果集是排序的、散列可能存在偏斜和CPU的代价，选用排序方法似乎更好些。第42页，本讲稿共71页6.5.4 利用索引来执行消除重复投影利用索引来执行消除重复投影 v排序排序/散列方法消除重复都未用到索引。如果索散列方法消除重复都未用到索引。如果索引的搜索键中包含了投影需要的所有属性，则索引的搜索键中包含了投影需要的所有属性，则索引也是有用的。引也是有用的。v只基于索引的扫描只基于索引的扫描(index-only scan)v如果我们有一个排序索引如果我们有一个排序索引(如如B+树树)，投影所需，投影所需属性是索引搜索键的前缀时，我们还可以做得更属性是索引搜索键的前缀时，我们还可

28、以做得更好：好：只需要检查相关索引项，丢弃不需的字段，比较相邻的数索引项以删除重复。第43页，本讲稿共71页6.6 连接操作赋值连接操作赋值6.6.1 嵌套循环连接6.6.2 基于索引的嵌套循环连接6.6.3 排序-归并连接 6.6.4 散列连接6.6.5 一般连接条件处理第44页，本讲稿共71页6.6 连接操作赋值连接操作赋值 v例例6.10 SELECT*FROM Reserves R,Sailors S WHERE R.sid=S.sidS为较小关系。连接条件为Ri=Sj(用位置标记字段)，表示关系R的第i个字段(sid)与关系S的第j个字段(sid)等值连接。假定关系R的大小为M个页，

29、每页pR个元组；关系S的大小为N个页，每页pS个元组 第45页，本讲稿共71页6.6.1 嵌套循环连接嵌套循环连接v嵌套循环连接算法，实质上是先枚举了叉积的所有嵌套循环连接算法，实质上是先枚举了叉积的所有结果，再丢弃不满足连接条件元组的一种简单连接结果，再丢弃不满足连接条件元组的一种简单连接实现方法实现方法.v简单嵌套循环连接（算法简单嵌套循环连接（算法6.3)for each tuple r R do for each tuple s S do if ri=si then add to resultset算法首先扫描外层关系R，并对外层关系的每个元组r R，扫描整个内层关系。算法总代价为M+

30、pR*M*N。v简单改进算法简单改进算法：采用一次一个页的嵌套循环赋值：采用一次一个页的嵌套循环赋值算法总代价可降低为M+M*N v对例对例6.10，对应，对应R为为Reserves、S为为Sailors代价为1000100*1000*500若按每次I/O 10ms计算，则近乎需要140个小时!v采用一次一个页的嵌套循环赋值采用一次一个页的嵌套循环赋值(简单改进）简单改进）连接代价变为10001000*500。按每次I/O10ms计算，所需时间可降为1.4个小时。第46页，本讲稿共71页块嵌套循环连接块嵌套循环连接 v算法算法6.4 基于块的嵌套循环连接算法基于块的嵌套循环连接算法 for e

31、ach block of B-2 pages of S for each page of R do for all matching in-memory tuples s S-block and r R-page add to resultset v算法算法6.4的总代价为的总代价为N+M*N/(B-2)读入外层关系S(只需1次)的N次I/Os，内层关系扫描N/(B-2)次，每次M次I/Os。第47页，本讲稿共71页6.6.2 基于索引的嵌套循环连接基于索引的嵌套循环连接 v算法算法6.5 基于索引的循环连接算法基于索引的循环连接算法 for each tuple ri R do 用索引检索用

32、索引检索S的匹配元组的匹配元组sj 添加添加 到结果集到结果集;它不需要枚举R与S叉积结果。扫描外层关系R的代价仍是M，但检索匹配的S元组代价，则依赖于索引种类和可匹配元组数。检索索引文件代价若对B+树索引，定位到相应叶子节点，约24次I/Os；对散列索引，发现相应桶的典型代价为12次I/Os。检索相应元组的代价依赖于索引是否聚集如果是聚集的，则这个代价典型地为1或2次I/Os，非聚集情况下，可能是每个匹配元组一次I/O。第48页，本讲稿共71页6.6.3 排序排序-归并连接归并连接 排序排序-归并连接算法的基本思想：归并连接算法的基本思想：v先基于连接属性分别排序两个关系（排序步）先基于连接

33、属性分别排序两个关系（排序步）相当于将两连接关系按连接属性分组(分区)，同一分组中的所有元组在连接属性上取同一值。v通过类似归并两个排序关系方法，来寻找两关系通过类似归并两个排序关系方法，来寻找两关系中满足连接条件的元组（归并步）中满足连接条件的元组（归并步）探索两个连接关系对应的等值分组，产生连接元组。v该方法也能避免枚举叉积，但这种基于分区的方该方法也能避免枚举叉积，但这种基于分区的方法只适合等值连接的情况，不适用非等值连接。法只适合等值连接的情况，不适用非等值连接。第49页，本讲稿共71页算法算法6.6 排序排序-归并连接算法归并连接算法 第50页，本讲稿共71页排序排序-归并连接实例归

34、并连接实例第51页，本讲稿共71页排序排序-归并的代价分析归并的代价分析 v一般排序一般排序-归并算法代价：归并算法代价：排序总页数分别为M和N的关系R与S代价为：O(M log M)和和O(N log N)。归并阶段的代价为M+N。v如果我们有如果我们有B(N)1/2个缓存页，这里个缓存页，这里N是较大是较大关系的总页数，则可采用两阶段排序关系的总页数，则可采用两阶段排序-归并连接，归并连接，总代价为总代价为5(M+N)。v若采用合并排序第若采用合并排序第2阶段与归并阶段的改进算法，阶段与归并阶段的改进算法，总代价可降为总代价可降为3(M+N)。v若之前至少有一个关系已排序，或在连接属性上若

35、之前至少有一个关系已排序，或在连接属性上有聚集索引时，这个方法将更有吸引力。有聚集索引时，这个方法将更有吸引力。第52页，本讲稿共71页6.6.4 散列连接散列连接 v散列连接算法的基本思想散列连接算法的基本思想开始时也是一个划分阶段：利用一个散列函数h作用到连接属性来散列两个关系，将R与S以同样方式划分为一系列的子桶(分区)。（使用散列技术进行分区划分）随后是匹配阶段：检查比较R与S对应子桶中的元组，测试等值连接条件。第53页，本讲稿共71页散列连接的主存需求分析散列连接的主存需求分析v在划分阶段，为划分在划分阶段，为划分R为为k个子桶，我们至少需要个子桶，我们至少需要k个输出缓存页和个输出

36、缓存页和1个输入缓存页。个输入缓存页。给定B个可用缓存页，最大的子桶数为B-1。v假定每个子桶等大小，均为假定每个子桶等大小，均为M/(B-1)，则，则匹配阶段处理关系R子桶的主存散列表需用缓存大小约为f*M/(B-1)，f为一个稍大于1的模糊因子。还需要一扫描输入S对应子桶的缓冲页和一输出缓存页要求B f*M/(B-1)+2成立，故有效执行散列连接，至少要求可用缓冲页数B大小超过(f*M)1/2。v当当B(f*M)1/2时，散列连接算法的总代价只有时，散列连接算法的总代价只有3(M+N)次。次。第54页，本讲稿共71页混合散列连接混合散列连接(hybrid hash join)v散列连接的最

37、小主存需求为散列连接的最小主存需求为B(f*M)1/2。v如还有更多的可用主存如还有更多的可用主存.将将R（或（或S）划分为）划分为k个子桶，个子桶，需要需要1个输入缓存和个输入缓存和k个输出缓存，共个输出缓存，共k+1个缓存页。个缓存页。还剩余的缓存页为B-(k+1)。每个子桶大小约M/kv如果如果B-(k+1)f*(M/k)，则剩余的缓存还可容，则剩余的缓存还可容纳一个子桶的主存散列表。这样在划分阶段，即可纳一个子桶的主存散列表。这样在划分阶段，即可利用这部分多余缓冲完成第利用这部分多余缓冲完成第1个子桶的匹配。个子桶的匹配。当总子桶数不多(k(M)1/2个缓存页个缓存页(这里这里M是较小

38、关系的是较小关系的总页数总页数)，且我们假设散列函数能实现均匀划分，且我们假设散列函数能实现均匀划分，则散列连接的代价是则散列连接的代价是3(M+N)次次I/Os。v如果有如果有B(N)1/2个缓存页，这里个缓存页，这里N是较大关系是较大关系的总页数，则排序的总页数，则排序-归并连接的代价也是归并连接的代价也是3(M+N)。v在实际系统中，如何选用这两种技术，还需考虑在实际系统中，如何选用这两种技术，还需考虑的其它因素（参见书本的其它因素（参见书本P P215)第56页，本讲稿共71页6.6.5 一般连接条件处理一般连接条件处理（一）处理多属性等值连接（一）处理多属性等值连接利用组合键索引，或

39、利用组合键进行排序-归并来解决。（二）处理非等值连接（二）处理非等值连接对基于索引的嵌套循环连接，仍可用B+树索引(散列索引则没有作用)。基于分区的散列连接和排序-归并连接算法不可用。其它我们讨论的连接算法不受影响。（三）结论（三）结论没有一种连接算法能在所有情况下优越于其它算法。如何正确选用算法，应综合考虑被连接关系的大小、可用的连接方法和可用缓冲池大小等因素。这个决策可能对系统的性能有重要的影响，因为不同算法的性能差异可能是巨大的。第57页，本讲稿共71页6.7 集合操作的赋值实现集合操作的赋值实现6.7.1 集合操作的一趟实现算法6.7.2 包运算的一套实现算法6.7.3 实现集合并与集

40、合差的两趟算法 第58页，本讲稿共71页6.7 集合操作的赋值实现集合操作的赋值实现 v集合操作包括集合并集合操作包括集合并(R S)、集合交、集合交(RS)、集、集合差合差(R-S)和叉积和叉积(R S)。它们都是二元的，。它们都是二元的，且集合并且集合并/交交/差还要求两个操作对象是相容的差还要求两个操作对象是相容的（模式结构）相同。（模式结构）相同。v集合操作基本上都可用我们前面已介绍的操作符集合操作基本上都可用我们前面已介绍的操作符赋值技术来实现。赋值技术来实现。第59页，本讲稿共71页用散列用散列/排序实现集合并的两趟算法排序实现集合并的两趟算法 基于散列实现基于散列实现RS算法算法

41、：基于排序实现基于排序实现RS算法算法：用所有字段组合作为排序键，分别排序R与S；同时扫描已排序的R与S，归并两关系元组并删除重复元组。第60页，本讲稿共71页集合操作一趟实现算法集合操作一趟实现算法v对于两关系对于两关系R与与S的集合操作，如果的集合操作，如果可用主存足够可用主存足够大大,可容纳整个较小关系可容纳整个较小关系，则我们可采用简单的一，则我们可采用简单的一趟算法来完成。趟算法来完成。代价：M+N 次I/Osv令令R是较小关系，一趟算法可描述如下：是较小关系，一趟算法可描述如下：第61页，本讲稿共71页算法算法6.7 集合交集合交RS运算的一趟实现算法运算的一趟实现算法v先将较小关

42、系先将较小关系R全部扫描读入主存，并建立存储全部扫描读入主存，并建立存储R所有元组的主存散列表所有元组的主存散列表;v逐页扫描处理较大关系逐页扫描处理较大关系S中的每个元组；中的每个元组；for 对对S已读入缓存页中每个元组已读入缓存页中每个元组t do 用用t探索匹配探索匹配R的主存散列表；的主存散列表；if 未找到匹配项未找到匹配项 then 丢弃当前元组丢弃当前元组t；else if 找到匹配项找到匹配项 then 输出输出t;endif;end for;第62页，本讲稿共71页算法算法6.8 两个包交运算两个包交运算RBS的一趟实现算法的一趟实现算法 第63页，本讲稿共71页算法算法6

43、.9 两个包差运算两个包差运算R-BS的一趟实现算法的一趟实现算法 第64页，本讲稿共71页 6.8 聚合操作符的赋值实现聚合操作符的赋值实现 例例6.16 SELECT AVG(S.age)FROM Sailors SvSQL-92支持的其它聚合操作还包括支持的其它聚合操作还包括MIN、MAX、SUM和和COUNT。v实现聚合操作赋值的基本算法包括：实现聚合操作赋值的基本算法包括：扫描整个关系;保留已扫描元组的一些聚合运算信息。v聚合操作通常与聚合操作通常与GROUP BY 子句联合使用。如子句联合使用。如果我们增加果我们增加GROUP BY rating 子句到例子句到例6.16，就可计算

44、每个职级组水手的平均工资。，就可计算每个职级组水手的平均工资。v没有没有GROUP BY 的的SQL语句可视为只有一个分语句可视为只有一个分组的特殊情况，这时被查询选择的所有元组同属组的特殊情况，这时被查询选择的所有元组同属于一个匿名分组。于一个匿名分组。第65页，本讲稿共71页分组查询赋值实现分组查询赋值实现 类似于消除重复运算，分组计算也必须采用全关系类似于消除重复运算，分组计算也必须采用全关系算法实现。有两种不依赖于索引的很好赋值算法：算法实现。有两种不依赖于索引的很好赋值算法：v排序方法排序方法先按分组属性排序关系;扫描已排序关系，为每个分组计算聚合运算值。这一步类似于我们实现未分组时

45、的聚合操作，只是在扫描时必须额外注意分组边界。v散列方法散列方法将基于分组属性建立一个主存散列表，散列项中含有；当扫描关系时，对每个元组：我们探求散列表发现该元组所属的相应散列项，并更新聚合运算信息。当散列表完成后，各散列项可被用来计算相应分组的回答元组。第66页，本讲稿共71页6.9 各类代数操作符赋值实现小结各类代数操作符赋值实现小结6.9.1 缓冲区的影响分析6.9.2 各类代数操作符赋值实现小结第67页，本讲稿共71页6.9 各类代数操作符赋值实现小结各类代数操作符赋值实现小结 6.9.1 缓冲区的影响缓冲区的影响 v在关系操作符的各种实现方案中，有效利用缓冲池在关系操作符的各种实现方

46、案中，有效利用缓冲池非常重要。在已讨论的各种算法中，我们都显式考非常重要。在已讨论的各种算法中，我们都显式考虑了缓冲池大小对算法选择的重要性。虑了缓冲池大小对算法选择的重要性。v还有三点值得我们特别注意：还有三点值得我们特别注意：如果有几个操作并发执行，它们需要共享缓冲池。这将减少每个操作实际可用的缓存页数量。如果利用索引存取元组，特别是存取非聚集元组时，一个页可能先后被请求多次，能否在缓冲池中找到之前已被请求过的页，取决于缓冲池的大小和置换策略。如果特定操作符有某种重复存取页的模式，我们就能增加在主存中发现页的可能性通过选择一个好得置换策略或为操作保留有效的缓存页。第68页，本讲稿共71页6

47、.9 各类代数操作符赋值实现小结各类代数操作符赋值实现小结 6.9.2 各类代数操作符赋值实现小结各类代数操作符赋值实现小结 v选择选择(c(R)和不消除重复的简单投影和不消除重复的简单投影(L(R)都可按一次多元组都可按一次多元组算法实现，可以逐页依次独立处理。算法实现，可以逐页依次独立处理。只需扫描关系一次，总代价为M；主存需求也只有2个缓存页。如有排序和可匹配索引可用，还可进一步优化选择算法。v消除重复操作符消除重复操作符()通常与投影结合处理。消除重复、分组聚合操作通常与投影结合处理。消除重复、分组聚合操作等一元操作符，以及连接、集合并等一元操作符，以及连接、集合并/交交/差等二元操作

48、符的赋值，都差等二元操作符的赋值，都必须按全关系的算法来实现。必须按全关系的算法来实现。如果可用主存可容纳一元操作的整个关系，或容纳二元操作的较小关系，则可采用一趟的算法来实现。否则，我们需要寻求两趟甚至多趟算法 第69页，本讲稿共71页6.9 各类代数操作符赋值实现小结各类代数操作符赋值实现小结 6.9.2 各类代数操作符赋值实现小结各类代数操作符赋值实现小结v全关系的两趟算法实现要点：全关系的两趟算法实现要点：第1步：进行分区划分，将输入关系按排序或散列方式进行分区；第2步：进行逐个分区或逐个分区对的处理。还可通过合并分区划分的第二阶段与第2步，来改进算法，降低算法代价。如果采用散列方式，还可通过采用建立主存散列表结构的方法，来进一步降低CPU代价。第70页，本讲稿共71页6.9 各类代数操作符赋值实现小结各类代数操作符赋值实现小结第71页，本讲稿共71页