第6章 关系操作符赋值

,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,*,第,2,部分 关系数据库系统实现,第,6,章 关系操作符赋值,高级数据库系统及其应用,第,6,章 关系操作符赋值,6.1,外部排序,6.2,关系操作符赋值实现基础,6.6,连接操作赋值,6.7,集合操作的赋值实现,6.8,聚合操作的赋值实现,6.9,各类代数操作符赋值实现小结,6.3 RDBMS,系统的目录信息,6.4,选择操作符赋值,6.5,投影与消除重复操作赋值,典型的关系数据库系统体系结构,RDBMS,系统查询处理的基本过程,当用户提出一个,SQL,查询后，将首先被送到解析器,(parser),，进行解析和编译处理。,编译后的查询接着被送到查询优化器,(,optimizer,),优化器将利用,DB,系统目录中信息,(System catalog),，产生一个高效的可执行计划。,可执行计划是查询赋值的一个蓝图，它被表示为关系代数操作符树的形式,树中的每个节点通常可对应到一个具体的关系操作符。,通过调用下层的计划执行器，实现最终查询赋值,.,关系操作符赋值是查询处理的基础，它们好比是实现整个查询赋值的一些基本积木块。,本章集中讨论单个关系操作符的赋值实现问题。,6.1,外部排序,6.1.1,一种简单的两路归并排序,6.1.2,多路归并排序,6.1.3,两阶段多路归并排序,6.1.4,最小化外部排序时间,排序是,DB,系统,最基本,的操作,DB,系统中有很多场合需要用到排序,用户可能希望以某种指定顺序返回查询结果集。,排序记录集是批处理建立B+树的第一步(5.3.3),排序是消除一个记录集中重复记录的一种有效方法。,广泛使用的关系连接操作，可基于排序的方法实现。,6.1.1,简单 的两路归并排序,一个含,7,个页文件的两路归并排序,6.1.1,简单的两路归并排序,在每个阶段，文件中的每个页将被读入和写出,1,次，即在每阶段每个页有,2,次磁盘,I/Os,。,如果输入文件的总页数为,M,，则完成排序需要的总阶段数为,log,2,M,+1,，总的代价为,2,M,(,log,2,M,+1),次,I/Os,。,为减小排序代价，我们应设法减少归并的阶段数。,如果可用的缓存页数不是,3,而是更多,(,令有,B,个,),，那么，,在第,1,阶段,:,可以使用更大的子文件；,在归并阶段，可以采用比两路更多路的归并，最多允许采用,B-1,路归并。,6.1.2,多路归并排序,（,图,6.2,B-1,路归并图解,）,6.1.3,两阶段多路归并排序,假设可用缓存页总数,B,，文件总页数为,M,第,1,阶段,划分子文件，可得子文件总数,=,M/B,。,第,2,阶段,归并子文件，因只有两个阶段，要求一次完成所有子文件归并,这要求排序子文件总数：,M/B, B-1,即要求,B M,1/2,，否则，必须进行更多个阶段的排序。,两阶段排序的总代价为：,M*4,次,I/Os,例,6.1,如果每个页的平均读写时间按,15ms,计算，计算两阶段排序,250000,个页需要的总时间。,第一个阶段要读写,500000,个页，需要时间为,5000000.015=7500s,，约,125,分钟。,第二个阶段也需要,125,分钟！,利用组块,I/O,优化外部排序时间,1,次请求读写几个连续页的时间，可能远小于分别独立读写每个页的时间之和。,1,次读写同一柱面,/,磁道上的,32,个连续页的时间,=6.5+7.5+32*0.5=30ms,；,分别读写,32,个页的时间,32*(6.5+7.5+0.5)=464ms,。,按组块读写进行外部排序,(,设每个块含,b,个页）,输入缓冲区和输出输出缓冲区大小：都取为一个组块大小。,以组块为单位进行读写,在归并阶段，一次可归并的最大子文件数为,(B-b)/b,按组块读写进行外部排序,(,设每个块含,b,个页）,输入缓冲区和输出输出缓冲区大小：都取为一个组块大小。,以组块为单位进行读写,在归并阶段，一次可归并的最大子文件数为,(B-b)/b,。,选用大组块缓冲区时，归并的阶段数会增加，即算法总的,I/Os,数将增加。,但这完全可从每页平均存取时间减少来得到补偿,。,在现行机器条件下，即使是使用了较大的块缓冲，除非少数特大的文件，大部分的文件排序都可以在两个阶段内完成排序。,表,6.1,组块大小,b=32,时一些外部排序需要的阶段数,6.2,关系操作符赋值实现基础,6.2.1,关系操作符赋值实现的三个基本操作,6.2.2,存取路径,6.2.3,代价计算模型,6.2.4,关系操作符赋值的实现算法分类,6.2.5,迭代器技术,6.2.6,主存散列表技术,6.2.7,本章查询用例说明,6.2,关系操作符赋值实现基础,6.2.1,关系操作符赋值实现的三个基本操作,循环,(Iteration),循环检查输入关系中的每个元组。,索引,(Indexing),如果选择或连接的条件已指定，通常可使用一个索引来检查满足条件的元组。,分区,(Partitioning),通过基于一个排序键来划分元组，我们通常能够将一个关系操作分解为针对各个分区元组的、代价更小的一组操作。,排序和散列是两种最常用的分区划分技术。,6.2.2,存取路径,存取路径,所有关系操作符的赋值算法，通常都必须从一个或多个关系检索元组。,从关系存取元组的方式也称为存取路径。,两个最常用的存取路径,1),关系文件扫描；,2),索引加上匹配选择条件,:,att,r,op,value,。,如果这个,attr,也正好是某索引,I,的搜索键，则称索引,I,匹配选择条件。,当存在多种存取路径时，称具有最小存取代价的存取路径为具有最好选择性的存取路径。,6.2.3,代价计算模型,关系操作符的输入对象，即关系，位于辅存,(,磁盘,),中,只考虑,I/O,代价，不考虑,CPU,代价。而衡量,I/O,代价的标准是需要读取或写出的页数。,对每个关系操作符，我们将讨论几种可选的存取路径。在比较不同赋值计划代价时，我们统一都不计算写出结果的代价。,几个可能会影响关系操作符赋值代价的重要参数,位于主存缓冲池中的可用缓存页数,B,；,关系,R,实际数据的存储页数,M,；,关系,R,的元组数,T(R),；,关系,R,不同的元组数,V,(,R, ,a,1,a,2,a,n),聚簇关系及其定义,如果,R,的所有元组存储在,M,个页或近似,M,个页中。如果,R,的元组分布在其它关系的元组之间，则称关系,R,是非聚簇的。,扫描聚簇关系,R,的代价为,M,次,I/Os,；最坏情况下，扫描非聚簇,R,的代价为,T (R),次,I/Os,。,本书约定在没有特别声明时，都默认关系是聚簇存储的。,6.2.4,关系操作符赋值的实现算法分类,按算法实现所采用的主存数据结构分类：,基于排序；,基于散列；,基于索引。,按算法实现的难度代价：,一趟算法,算法实现时，相应的关系只需扫描1次；,一趟半算法,一个关系只需扫描1次，但另一个关系需扫描多次；,二趟算法(算法实现时，相应的关系需扫描2次)；,多趟算法(算法实现时，相应的关系需扫描多次)。,6.2.4,关系操作符赋值的实现算法分类,按操作符的操作对象数分类：,一元操作实现算法,如选择(,c,(R)、投影(,L,(R)、消除重复(R)、分组 ,L,(R)等。,二元操作实现算法,如连接()、并()、交()、差()、叉积(,)等,按是否可以分割并独立处理关系的各页来分类：,一次多元组算法。,允许独立地处理关系的每个页，前后页处理结果没有相互影响，如选择(,c,(R)、投影(,L,(R)等操作。,全关系算法。,6.2.5,迭代器技术,代数操作符的迭代器接口,包括：,open,getnext,和,close,三个函数,它们隐藏了操作符如何实现的细节，允许我们以一致的方式看待所有的操作符节点。,多个迭代器连接，可构成具有流水化工作方式的,迭代器网络。,例,6.3 TableScan(R),迭代器实现,算法,6.2,包并运算的迭代器实现算法,6.2.6,主存散列表技术,本章查询用例说明,仍用第,2,章,“,水手值勤管理,DB,模式,”,的三个关系表：,Sailors (,sid,:integer,sname,:string,rating,:integer,age,:real),Boats (,bid,:integer,bname,:string,color,:string),Reserves (,sid,:integer,bid,:integer,day,:dates,rname,:string),关系,Reserves,的元组大小为,40,字节，每个页可存储,100,个元组，总共有,1000,个页。,关系,Sailors,的元组大小为,50,字节，每个页可存储,80,个元组，总共有,500,个页。,6.3 RDBMS,系统的目录信息,6.3.1,存储在,DB,系统目录中的信息,6.3.2 DB,系统目录组织结构,6.3 RDBMS,系统的目录信息,在,DB,系统目录中，一般至少都会有一些系统范围的信息，如缓冲池大小、用户帐户或认证信息 ，以及一些关于个体关系、索引或视图的信息：,对每个关系模式结构，有关信息包括：,关系名、文件名、文件结构,(,如堆结构,),；,属性名、类型、长度；,关系上的每个索引名；,关系上的约束定义。,对每个索引,索引名、索引结构,(,如,B+,树,),；,搜索键的属性。,对每个视图,视图名字与定义。,可供查询优化器应用的目录信息（,1,）,关系R的元组数,T,(,R,)。,关系R元组大小,ST,(,R,)。,含关系R元组的文件总页数,M,(,R,)。,关系R的页因子，即一个页中能存放关系R元组的数目,FP,(R)。,若关系R聚簇存储在一个文件中，则有,M,(,R,)=,T,(,R,)/,FP,(R)。,关系R在属性A上所具有的不同值数V(A,R)。,关系,R,在属性,A,上的等值选择基数,SC(A,R),。,当,A,为码属性时,SC(A,R),1,；,当,A,为非码属性时，如假定,V(R,A),个不同值在,R,的元组中均匀分布，则,SC(A,R)=,T,(,R,)/V(R,A),。,可供查询优化器应用的目录信息（,2,）,索引基数值,(Index Cardinality),：对每个索引,I,，存储索引所含的不同键数,Nkeys,(,I,)。,索引大小,(Index size),：每个索引,I,，存储索引文件的总页数,(,INPages,(,I,),。,对B+树，,INPages,(,I,)存储叶子节点的总数。,索引深度,(Index height),：,IH,(,I,)，,对于散列索引，它是桶的深度（页数）；,对B+树形索引，它是非叶子的总层数。,索引范围,(Index Range),：每个索引,I,，可表示的最小键值,(,ILow,(,I,),和最大键值,(,IHigh,(,I,),。,6.4,选择操作符赋值,6.4.1,简单扫描方法,6.4.2,利用排序特性进行选择赋值,6.4.3,利用索引进行选择赋值,6.4.4,一般的选择条件处理,6.4,选择操作符赋值,例,6.5,SELECT * FROM Reserves R,WHERE R.rnames,=,Joe,令,M,是关系,R,的总页数，本例中,M=1000,。,6.4.1,简单扫描方法,6.4.2,利用排序特性进行选择赋值,用二分法，定位第,1,个满足条件的记录。这一步的代价为,O(,log,2,M,),。,从上,1,步定位的位置开始扫描关系,R,，直到找到一条不满足条件的记录时才停止继续扫描。,该步代价取决于满足条件的元组数,代价为,O(0,M),对属性,A,上的等值选择,该步代价约,SC(A,R)/,FP,(R),6.4.3,利用索引进行选择赋值,有能与选择条件相匹配的索引可用,基本代价计算式：,IH,(,I,)+,SC(A,R)/FP,(R),有关影响因素,索引组织结构（顺序、,B+,树或散列）,选择条件（等值、范围或其它选择）,满足条件的元组总数（索引键是否为码属性）,关系元组是否聚簇存储、索引是否聚集,rids,是否按,page-id,排序。,6.4.3,利用索引进行选择赋值,用散列索引实现等值选择赋值,如果在,R.attr,上有散列索引可用，且,op,是等值运算符，则利用这个散列索引进行赋值可能是最好的存取路径。,例,6.6,考虑例,6.5,查询，假定在,Reserves:,rname,上有散列索引，一个名为,Joe,的人做了,100,个值派。分析检索这,100,个,Reserves,元组需要的代价。,基于,B+,树索引的选择赋值,例,6.7,考虑,Reserves,上,rname,%C,形式选择。假设名字按第,1,个字母均匀分布，选择结果集约含有,10%,的元组，即有大约,10000,个元组或,100,个页。若有,rname,上的一个聚集,B+,树索引，分析检索满足条件元组的代价。,6.4.4,一般的选择条件处理（,1,）,任何复杂条件，总可改写为,CNF,形式,conjunctive normal form, CNF,例如, (day8/9/94,rname=Joe),bid=5,sid=3,，,等价于,(day8/9/94,bid=5,sid=3),(rname=Joe,bid=5,sid=3),对子项中不含析取运算的,CNF,形式条件，存在两条规则：,对散列索引搜索键中的每个属性，如果选择条件中都有一个形式为attr=,v,的选择项与它对应，则该散列索引匹配对应选择条件。,对树形索引搜索键前缀中的每个属性，如果选择条件中都有一个形式为,attr op v,的选择项与它对应，则该散列索引匹配对应选择条件。,相应有两种赋值选项：,使用文件扫描；,先使用一个单索引去匹配选择条件中部分合取项，然后应用非主合取项到每个被检索的元组。,6.4.4,一般的选择条件处理（,2,）,对子项中含析取运算的,CNF,形式条件，存在两条规则：,对,(,day8/9/94,rname=Joe,),，当只有,rname,上的散列索引和,sid,上的散列索引可用时，文件扫描是具有最好选择性的方法,。,对,(,day (T),1/2,时，两种方法总代价都是,M+2T,次,I/Os,。,两种算法的主存要求比较,基于排序算法要求可用缓存页数,B (T),1/2,以保证可按两阶段完成排序。,基于散列算法要求可用缓存页数,B,足够容纳最大的子桶，在划分均匀情况下，要求,BT/(B-1),，即,B (T),1/2,。但若散列划分不均匀，则可能需要比,(T),1/2,更大一些的,B,。,结论,综合考虑到排序方法的投影结果集是排序的、散列可能存在偏斜和,CPU,的代价，选用排序方法似乎更好些 。,6.5.4,利用索引来执行消除重复投影,排序,/,散列方法消除重复都未用到索引。如果索引的搜索键中包含了投影需要的所有属性，则索引也是有用的。,只基于索引的扫描,(index-only scan),如果我们有一个排序索引,(,如,B+,树,),，投影所需属性是索引搜索键的前缀时，我们还可以做得更好：,只需要检查相关索引项，丢弃不需的字段，比较相邻的数索引项以删除重复。,6.6,连接操作赋值,6.6.1,嵌套循环连接,6.6.2,基于索引的嵌套循环连接,6.6.3,排序,-,归并连接,6.6.4,散列连接,6.6.5,一般连接条件处理,6.6,连接操作赋值,例,6.10,SELECT * FROM Reserves R, Sailors S,WHERE R.sid=S.sid,S,为较小关系。,连接条件为,R,i,= S,j,(,用位置标记字段,),，表示关系,R,的第,i,个字段,(,sid,),与关系,S,的第,j,个字段,(,sid,),等值连接。,假定关系,R,的大小为,M,个页，每页,p,R,个元组；关系,S,的大小为,N,个页，每页,p,S,个元组,6.6.1,嵌套循环连接,嵌套循环连接算法，实质上是先枚举了叉积的所有结果，再丢弃不满足连接条件元组的一种简单连接实现方法,.,简单嵌套循环连接（算法,6.3),for each tuple,r,R,do,for each tuple,s,S,do,if,r,i,= s,i,then add to resultset,算法首先扫描外层关系,R,，并对外层关系的每个元组,r R,，扫描整个内层关系。,算法总代价为,M,+,p,R,*M*N,。,简单改进算法,：采用一次一个页的嵌套循环赋值,算法总代价可降低为,M+ M*N,对例,6.10,，对应,R,为,Reserves,、,S,为,Sailors,代价为,1000,100*1000*500,若按每次,I/O,10ms,计算，则近乎需要,140,个小时,!,采用一次一个页的嵌套循环赋值,(,简单改进）,连接代价变为,1000,1000*500,。,按每次,I/O,10ms,计算，所需时间可降为,1.4,个小时。,块嵌套循环连接,算法,6.4,基于块的嵌套循环连接算法,for each 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,算法,6.4,的总代价为,N+ M*N/(B-2),读入外层关系,S,(,只需,1,次,),的,N,次,I/Os,，,内层关系扫描,N/(B-2),次，每次,M,次,I/Os,。,6.6.2,基于索引的嵌套循环连接,算法,6.5,基于索引的循环连接算法,for each tuple,r,i, R,do,用索引检索,S,的匹配元组,s,j,添加,到结果集;,它不需要枚举,R,与,S,叉积结果。,扫描外层关系,R,的代价仍是,M,，但检索匹配的,S,元组代价，则依赖于索引种类和可匹配元组数。,检索索引文件代价,若对,B+,树索引，定位到相应叶子节点，约,24,次,I/Os,；,对散列索引，发现相应桶的典型代价为,12,次,I/Os,。,检索相应元组的代价依赖于索引是否聚集,如果是聚集的，则这个代价典型地为,1,或,2,次,I/Os,，,非聚集情况下，可能是每个匹配元组一次,I/O,。,6.6.3,排序,-,归并连接,排序,-,归并连接算法的基本思想：,先基于连接属性分别排序两个关系（排序步）,相当于将两连接关系按连接属性分组,(,分区,),，同一分组中的所有元组在连接属性上取同一值。,通过类似归并两个排序关系方法，来寻找两关系中满足连接条件的元组（归并步）,探索两个连接关系对应的等值分组，产生连接元组。,该方法也能避免枚举叉积，但这种基于分区的方法只适合等值连接的情况，不适用非等值连接。,算法,6.6,排序,-,归并连接算法,排序,-,归并连接实例,排序,-,归并的代价分析,一般排序,-,归并算法代价：,排序总页数分别为,M,和,N,的关系,R,与,S,代价为：,O(M log M),和,O(N log N),。,归并阶段的代价为,M+N,。,如果我们有,B (N),1/2,个缓存页，这里,N,是较大关系的总页数，则可采用两阶段排序,-,归并连接，总代价为,5(M+N),。,若采用合并排序第,2,阶段与归并阶段的改进算法，总代价可降为,3(M+N),。,若之前至少有一个关系已排序，或在连接属性上有聚集索引时，这个方法将更有吸引力。,6.6.4,散列连接,散列连接算法的基本思想,开始时也是一个划分阶段：利用一个散列函数,h,作用到连接属性来散列两个关系，将,R,与,S,以同样方式划分为一系列的子桶,(,分区,),。（使用散列技术进行分区划分）,随后是匹配阶段：检查比较,R,与,S,对应子桶中的元组，测试等值连接条件。,散列连接的主存需求分析,在划分阶段，为划分,R,为,k,个子桶，我们至少需要,k,个输出缓存页和,1,个输入缓存页。,给定,B,个可用缓存页，最大的子桶数为,B-1,。,假定每个子桶等大小，均为,M/(B-1),，则,匹配阶段处理关系,R,子桶的主存散列表需用缓存大小约为,f*M/(B-1),，,f,为一个稍大于,1,的模糊因子。,还需要一扫描输入,S,对应子桶的缓冲页和一输出缓存页,要求,B f*M/(B-1) + 2,成立，故有效执行散列连接，至少要求可用缓冲页数,B,大小超过,(f*M),1/2,。,当,B(f*M),1/2,时，散列连接算法的总代价只有,3(M+N),次。,混合散列连接,(hybrid hash join),散列连接的最小主存需求为,B(f*M),1/2,。,如还有更多的可用主存,.,将,R,（或,S,）划分为,k,个子桶，需要,1,个输入缓存和,k,个输出缓存，共,k+1,个缓存页。,还剩余的缓存页为,B-(k+1),。,每个子桶大小约,M/k,如果,B-(k+1) f* (M/k),，则剩余的缓存还可容纳一个子桶的主存散列表。这样在划分阶段，即可利用这部分多余缓冲完成第,1,个子桶的匹配。,当总子桶数不多,(,k(M),1/2,个缓存页,(,这里,M,是较小关系的总页数,),，且我们假设散列函数能实现均匀划分，则散列连接的代价是,3(M+N),次,I/Os,。,如果有,B (N),1/2,个缓存页，这里,N,是较大关系的总页数，则排序,-,归并连接的代价也是,3(M+N),。,在实际系统中，如何选用这两种技术，还需考虑的其它因素（参见书本,P P215),6.6.5,一般连接条件处理,（一）处理多属性等值连接,利用组合键索引，或利用组合键进行排序,-,归并来解决。,（二）处理非等值连接,对基于索引的嵌套循环连接，仍可用B+树索引(散列索引则没有作用)。,基于分区的散列连接和排序-归并连接算法不可用。,其它我们讨论的连接算法不受影响。,（三）结论,没有一种连接算法能在所有情况下优越于其它算法。,如何正确选用算法，应综合考虑被连接关系的大小、可用的连接方法和可用缓冲池大小等因素。,这个决策可能对系统的性能有重要的影响，因为不同算法的性能差异可能是巨大的。,6.7,集合操作的赋值实现,6.7.1,集合操作的一趟实现算法,6.7.2,包运算的一套实现算法,6.7.3,实现集合并与集合差的两趟算法,6.7,集合操作的赋值实现,集合操作包括集合并,(RS),、集合交,(RS),、集合差,(R-S),和叉积,(R,S),。它们都是二元的，且集合并,/,交,/,差还要求两个操作对象是相容的（模式结构）相同。,集合操作基本上都可用我们前面已介绍的操作符赋值技术来实现。,用散列,/,排序实现集合并的两趟算法,基于散列实现,RS,算法,：,基于排序实现,RS,算法,：,用所有字段组合作为排序键，分别排序R与S；,同时扫描已排序的R与S，归并两关系元组并删除重复元组。,集合操作一趟实现算法,对于两关系,R,与,S,的集合操作，如果,可用主存足够大,可容纳整个较小关系,，则我们可采用简单的一趟算法来完成。,代价：,M+N,次,I/Os,令,R,是较小关系，一趟算法可描述如下：,算法,6.7,集合交,R,S,运算的一趟实现算法,先将较小关系,R,全部扫描读入主存，并建立存储,R,所有元组的主存散列表,;,逐页扫描处理较大关系,S,中的每个元组；,for 对S已读入缓存页中每个元组t do,用t探索匹配R的主存散列表；,if 未找到匹配项 then,丢弃当前元组t；,else if 找到匹配项 then,输出t;,endif;,end for;,算法,6.8,两个包交运算,R,B,S,的一趟实现算法,算法,6.9,两个包差运算,R-,B,S,的一趟实现算法,6.8,聚合操作符的赋值实现,例,6.16,SELECT AVG(,S.age,) FROM Sailors S,SQL-92,支持的其它聚合操作还包括,MIN,、,MAX,、,SUM,和,COUNT,。,实现聚合操作赋值的基本算法包括：,扫描整个关系,;,保留已扫描元组的一些聚合运算信息。,聚合操作通常与,GROUP BY,子句联合使用。如果我们增加,GROUP BY,rating,子句到例,6.16,，就可计算每个职级组水手的平均工资。,没有,GROUP BY,的,SQL,语句可视为只有一个分组的特殊情况，这时被查询选择的所有元组同属于一个匿名分组。,分组查询赋值实现,类似于消除重复运算，分组计算也必须采用全关系算法实现。有两种不依赖于索引的很好赋值算法：,排序方法,先按分组属性排序关系;,扫描已排序关系，为每个分组计算聚合运算值。这一步类似于我们实现未分组时的聚合操作，只是在扫描时必须额外注意分组边界。,散列方法,将基于分组属性建立一个主存散列表，散列项中含有,；,当扫描关系时，对每个元组：我们探求散列表发现该元组所属的相应散列项，并更新聚合运算信息。,当散列表完成后，各散列项可被用来计算相应分组的回答元组。,6.9,各类代数操作符赋值实现小结,6.9.1,缓冲区的影响分析,6.9.2,各类代数操作符赋值实现小结,6.9,各类代数操作符赋值实现小结,6.9.1,缓冲区的影响,在关系操作符的各种实现方案中，有效利用缓冲池非常重要。在已讨论的各种算法中，我们都显式考虑了缓冲池大小对算法选择的重要性。,还有三点值得我们特别注意：,如果有几个操作并发执行，它们需要共享缓冲池。这将减少每个操作实际可用的缓存页数量。,如果利用索引存取元组，特别是存取非聚集元组时，一个页可能先后被请求多次，能否在缓冲池中找到之前已被请求过的页，取决于缓冲池的大小和置换策略。,如果特定操作符有某种重复存取页的模式，我们就能增加在主存中发现页的可能性,通过选择一个好得置换策略或为操作保留有效的缓存页。,6.9,各类代数操作符赋值实现小结,6.9.2,各类代数操作符赋值实现小结,选择,(,c,(R),),和不消除重复的简单投影,(,L(R),),都可按一次多元组算法实现，可以逐页依次独立处理。,只需扫描关系一次，总代价为,M,；,主存需求也只有,2,个缓存页。,如有排序和可匹配索引可用，还可进一步优化选择算法。,消除重复操作符,(,),通常与投影结合处理。消除重复、分组聚合操作等一元操作符，以及连接、集合并,/,交,/,差等二元操作符的赋值，都必须按全关系的算法来实现。,如果可用主存可容纳一元操作的整个关系，或容纳二元操作的较小关系，则可采用一趟的算法来实现。否则，我们需要寻求两趟甚至多趟算法,