《第6章关系操作符赋值.ppt》由会员分享，可在线阅读，更多相关《第6章关系操作符赋值.ppt（68页珍藏版）》请在三一文库上搜索。
1、第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
2、 catalog)，产生一个高效的可执行计划。可执行计划是查询赋值的一个蓝图，它被表示为关系代数操作符树的形式树中的每个节点通常可对应到一个具体的关系操作符。通过调用下层的计划执行器，实现最终查询赋值.,关系操作符赋值是查询处理的基础，它们好比是实现整个查询赋值的一些基本积木块。本章集中讨论单个关系操作符的赋值实现问题。,6.1 外部排序,6.1.1 一种简单的两路归并排序,6.1.2 多路归并排序,6.1.3 两阶段多路归并排序,6.1.4 最小化外部排序时间,6.1.1 简单 的两路归并排序,一个含7个页文件的两路归并排序,6.1.1 简单的两路归并排序,在每个阶段，文件中的每个页将被读入
3、和写出1次，即在每阶段每个页有2次磁盘I/Os。如果输入文件的总页数为M，则完成排序需要的总阶段数为log2M+1，总的代价为2M(log2M+1)次I/Os。为减小排序代价，我们应设法减少归并的阶段数。如果可用的缓存页数不是3而是更多(令有B个)，那么，在第1阶段:可以使用更大的子文件；在归并阶段，可以采用比两路更多路的归并，最多允许采用B-1路归并。,6.1.2 多路归并排序（图6.2 B-1路归并图解 ）,6.1.3 两阶段多路归并排序,假设可用缓存页总数B，文件总页数为M第1阶段 划分子文件，可得子文件总数= M/B 。第2阶段 归并子文件，因只有两个阶段，要求一次完成所有子文件归并这
4、要求排序子文件总数： M/B B-1 即要求B M1/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)=4
5、64ms。 按组块读写进行外部排序(设每个块含b个页）输入缓冲区和输出输出缓冲区大小：都取为一个组块大小。以组块为单位进行读写在归并阶段，一次可归并的最大子文件数为(B-b)/b,按组块读写进行外部排序(设每个块含b个页）输入缓冲区和输出输出缓冲区大小：都取为一个组块大小。以组块为单位进行读写在归并阶段，一次可归并的最大子文件数为(B-b)/b。选用大组块缓冲区时，归并的阶段数会增加，即算法总的I/Os数将增加。但这完全可从每页平均存取时间减少来得到补偿。 在现行机器条件下，即使是使用了较大的块缓冲，除非少数特大的文件，大部分的文件排序都可以在两个阶段内完成排序。,表6.1 组块大小b=32时
6、一些外部排序需要的阶段数,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) 通过基于一个排序键来划分元组，我们通常能够将一个关系操作分解为
7、针对各个分区元组的、代价更小的一组操作。排序和散列是两种最常用的分区划分技术。,6.2.2 存取路径,存取路径 所有关系操作符的赋值算法，通常都必须从一个或多个关系检索元组。从关系存取元组的方式也称为存取路径。两个最常用的存取路径1) 关系文件扫描；2) 索引加上匹配选择条件: attr op value 。如果这个attr也正好是某索引I的搜索键，则称索引I匹配选择条件。当存在多种存取路径时，称具有最小存取代价的存取路径为具有最好选择性的存取路径。,6.2.3 代价计算模型,关系操作符的输入对象，即关系，位于辅存(磁盘)中只考虑I/O代价，不考虑CPU代价。而衡量I/O代价的标准是需要读取或
8、写出的页数。对每个关系操作符，我们将讨论几种可选的存取路径。在比较不同赋值计划代价时，我们统一都不计算写出结果的代价。,几个可能会影响关系操作符赋值代价的重要参数,位于主存缓冲池中的可用缓存页数B；关系R实际数据的存储页数M；关系R的元组数T(R)；关系R不同的元组数V( R, a1,a2,an)聚簇关系及其定义如果R的所有元组存储在M个页或近似M个页中。如果R的元组分布在其它关系的元组之间，则称关系R是非聚簇的。扫描聚簇关系R的代价为M次I/Os；最坏情况下，扫描非聚簇R的代价为T (R)次I/Os。本书约定在没有特别声明时，都默认关系是聚簇存储的。,6.2.4 关系操作符赋值的实现算法分类
9、,按算法实现所采用的主存数据结构分类：基于排序；基于散列；基于索引。按算法实现的难度代价：一趟算法算法实现时，相应的关系只需扫描1次；一趟半算法一个关系只需扫描1次，但另一个关系需扫描多次；二趟算法(算法实现时，相应的关系需扫描2次)；多趟算法(算法实现时，相应的关系需扫描多次)。,6.2.4 关系操作符赋值的实现算法分类,按操作符的操作对象数分类：一元操作实现算法如选择(c(R)、投影(L(R)、消除重复(R)、分组 L(R)等。二元操作实现算法 如连接()、并()、交()、差()、叉积()等按是否可以分割并独立处理关系的各页来分类：一次多元组算法。允许独立地处理关系的每个页，前后页处理结果
10、没有相互影响，如选择(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 :re
11、al)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系统目录中，一般至少都会有一些系统范围
12、的信息，如缓冲池大小、用户帐户或认证信息 ，以及一些关于个体关系、索引或视图的信息：对每个关系模式结构，有关信息包括：关系名、文件名、文件结构(如堆结构)；属性名、类型、长度；关系上的每个索引名；关系上的约束定义。对每个索引索引名、索引结构(如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)。关
13、系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+树形索引，它是非叶子的总层数。索引范围
14、(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，直到找到一
15、条不满足条件的记录时才停止继续扫描。该步代价取决于满足条件的元组数,代价为 O(0M)对属性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是等值运算符，则利用这个散列索引进行赋值
16、可能是最好的存取路径。例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/94rna
17、me=Joe) bid=5sid=3， 等价于 (day8/9/94bid=5sid=3) (rname=Joe bid=5sid=3) 对子项中不含析取运算的CNF形式条件，存在两条规则：对散列索引搜索键中的每个属性，如果选择条件中都有一个形式为attr=v的选择项与它对应，则该散列索引匹配对应选择条件。对树形索引搜索键前缀中的每个属性，如果选择条件中都有一个形式为attr op v的选择项与它对应，则该散列索引匹配对应选择条件。,相应有两种赋值选项：使用文件扫描；先使用一个单索引去匹配选择条件中部分合取项，然后应用非主合取项到每个被检索的元组。,6.4.4 一般的选择条件处理（2）,对子项
18、中含析取运算的CNF形式条件，存在两条规则：对(day8/9/94 rname=Joe)，当只有rname上的散列索引和sid上的散列索引可用时，文件扫描是具有最好选择性的方法 。对(day 8/9/94 rname=Joe) sid=3，sid上有索引如果一个含析取合取项中的每个析取分项都有可用索引，且每个索引项都含记录指针rid。可分别利用每个索引获取一组rids，再对各组rids按page-id排序和求并集，最后利用并集中的每个rid检索满足条件元组。,6.5 投影与消除重复操作赋值,6.5.1 基于排序实现消除重复操作符,6.5.2 基于散列实现消除重复操作符,6.5.3 排序与散列算
19、法比较,6.5.4 利用索引执行消除重复投影,6.5 投影与消除重复操作赋值,投影操作符的关系代数表达式为a1,a2,am(R) 可用一次多元组扫描算法，总代价为O(M)；投影与消除重复操作通常可放在一起来实现例6.8 SELECT DISTINCT R.sid, R.bid FROM Reserves R对应关系代数表达式(sid,bid)为实现这个投影，必须完成：1) 移除不需要的属性；2) 删除结果集中重复的元组；消除重复步通常较困难。有两个基本算法：一是基于排序，二是基于散列。它们都是划分方法的实例。,6.5.1 基于排序实现消除重复投影,概念上，该算法至少需有以下步骤：扫描关系R以产
20、生只包括需要属性的元组集（即剔除不需要属性）；代价为扫描R的M次I/Os写出结果的T次I/Os, T是临时结果的页数,准确值依赖于投影保留的属性数。 代价量级：O(M).用保留的所有属性组合作为排序键，对这组元组集进行排序； 代价量级：O(T logT) 扫描排序结果，比较邻近元组，丢弃重复元组。 代价量级：O(T) 。总代价量级：O(M logM)。,前后两步都较直接，代价较小；但中间步(排序)的代价则较大,6.5.1 基于排序实现消除重复投影,例6.9 续例6.8。若假定仅含sid、bid字段的临时关系元组为10字节（约原关系元组大小的四分之一），且我们有20个缓存页可用。分析这时该查询赋
21、值的代价。分析与解法，参见书本P206总代价：2500次I/Os 若采用改进算法总代价可降为：(1000250)+250=1500次I/Os,6.5.2 基于散列实现消除重复投影,算法包括两个基本阶段：划分和对每个子桶执行删除重复元组；,两个阶段总代价为M+2T对例6.8，代价为：1000+250*2=1500次I/O,6.5.3 用排序与散列算法比较,排序算法较有优势的一些场合两种算法代价比较当有B(T)1/2时，两种方法总代价都是M+2T次I/Os。 两种算法的主存要求比较基于排序算法要求可用缓存页数B (T)1/2以保证可按两阶段完成排序。基于散列算法要求可用缓存页数B足够容纳最大的子桶
22、，在划分均匀情况下，要求BT/(B-1)，即B (T)1/2。但若散列划分不均匀，则可能需要比(T)1/2更大一些的B。结论综合考虑到排序方法的投影结果集是排序的、散列可能存在偏斜和CPU的代价，选用排序方法似乎更好些 。,6.5.4 利用索引来执行消除重复投影,排序/散列方法消除重复都未用到索引。如果索引的搜索键中包含了投影需要的所有属性，则索引也是有用的。只基于索引的扫描(index-only scan)如果我们有一个排序索引(如B+树)，投影所需属性是索引搜索键的前缀时，我们还可以做得更好：只需要检查相关索引项，丢弃不需的字段，比较相邻的数索引项以删除重复。,6.6 连接操作赋值,6.6
23、.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.sidS为较小关系。连接条件为Ri= Sj (用位置标记字段)，表示关系R的第i个字段(sid)与关系S的第j个字段(sid)等值连接。假定关系R的大小为M个页，每页pR个元组；关系S的大小为N个页，每页pS个元组,6.6.1 嵌套循环连接,嵌套循环连接算法，实质上是先枚举了叉积的所有结果，再丢弃不满足连接条件元组的一种简单连接
24、实现方法.简单嵌套循环连接（算法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+pR*M*N。 简单改进算法：采用一次一个页的嵌套循环赋值算法总代价可降低为M+ M*N,对例6.10，对应R为Reserves、S为Sailors代价为1000100*1000*500若按每次I/O 10ms计算，则近乎需要140个小时!采用一次一个页的嵌套循环赋值(简单改进） 连接代价变为10001000*500
25、。按每次I/O10ms计算，所需时间可降为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 tu
26、ple ri R do 用索引检索S的匹配元组sj 添加 到结果集;它不需要枚举R与S叉积结果。扫描外层关系R的代价仍是M，但检索匹配的S元组代价，则依赖于索引种类和可匹配元组数。 检索索引文件代价若对B+树索引，定位到相应叶子节点，约24次I/Os；对散列索引，发现相应桶的典型代价为12次I/Os。检索相应元组的代价依赖于索引是否聚集如果是聚集的，则这个代价典型地为1或2次I/Os，非聚集情况下，可能是每个匹配元组一次I/O。,6.6.3 排序-归并连接,排序-归并连接算法的基本思想：先基于连接属性分别排序两个关系（排序步）相当于将两连接关系按连接属性分组(分区)，同一分组中的所有元组在连接
27、属性上取同一值。通过类似归并两个排序关系方法，来寻找两关系中满足连接条件的元组（归并步）探索两个连接关系对应的等值分组，产生连接元组。该方法也能避免枚举叉积，但这种基于分区的方法只适合等值连接的情况，不适用非等值连接。,算法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阶段与归并阶段的改进算法，总代价可降为
28、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
29、-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)，则剩余的缓存还可容纳一个子桶的主存散列表。这样在划分阶
30、段，即可利用这部分多余缓冲完成第1个子桶的匹配。当总子桶数不多(k5)的情况下，这个改进可显著提高算法性能。,散列连接与排序-归并连接对比,如果有B(M)1/2个缓存页(这里M是较小关系的总页数)，且我们假设散列函数能实现均匀划分，则散列连接的代价是3(M+N)次I/Os。如果有B (N)1/2个缓存页，这里N是较大关系的总页数，则排序-归并连接的代价也是3(M+N)。在实际系统中，如何选用这两种技术，还需考虑的其它因素（参见书本P P215),6.6.5 一般连接条件处理,（一）处理多属性等值连接利用组合键索引，或利用组合键进行排序-归并来解决。（二）处理非等值连接对基于索引的嵌套循环连接，
31、仍可用B+树索引(散列索引则没有作用)。基于分区的散列连接和排序-归并连接算法不可用。其它我们讨论的连接算法不受影响。 （三）结论没有一种连接算法能在所有情况下优越于其它算法。如何正确选用算法，应综合考虑被连接关系的大小、可用的连接方法和可用缓冲池大小等因素。这个决策可能对系统的性能有重要的影响，因为不同算法的性能差异可能是巨大的。,6.7 集合操作的赋值实现,6.7.1 集合操作的一趟实现算法,6.7.2 包运算的一套实现算法,6.7.3 实现集合并与集合差的两趟算法,6.7 集合操作的赋值实现,集合操作包括集合并(RS)、集合交(RS)、集合差(R-S)和叉积(RS)。它们都是二元的，且集
32、合并/交/差还要求两个操作对象是相容的（模式结构）相同。集合操作基本上都可用我们前面已介绍的操作符赋值技术来实现。,用散列/排序实现集合并的两趟算法,基于散列实现RS算法： 基于排序实现RS算法：用所有字段组合作为排序键，分别排序R与S；同时扫描已排序的R与S，归并两关系元组并删除重复元组。,集合操作一趟实现算法,对于两关系R与S的集合操作，如果可用主存足够大,可容纳整个较小关系，则我们可采用简单的一趟算法来完成。代价：M+N 次I/Os令R是较小关系，一趟算法可描述如下：,算法6.7 集合交RS运算的一趟实现算法,先将较小关系R全部扫描读入主存，并建立存储R所有元组的主存散列表;逐页扫描处理
33、较大关系S中的每个元组； for 对S已读入缓存页中每个元组t do 用t探索匹配R的主存散列表； if 未找到匹配项 then 丢弃当前元组t； else if 找到匹配项 then 输出t; endif; end for;,算法6.8 两个包交运算RBS的一趟实现算法,算法6.9 两个包差运算R-BS的一趟实现算法,6.8 聚合操作符的赋值实现,例6.16 SELECT AVG(S.age) FROM Sailors SSQL-92支持的其它聚合操作还包括MIN、MAX、SUM和COUNT。实现聚合操作赋值的基本算法包括：扫描整个关系;保留已扫描元组的一些聚合运算信息。聚合操作通常与GRO
34、UP BY 子句联合使用。如果我们增加GROUP BY rating 子句到例6.16，就可计算每个职级组水手的平均工资。没有GROUP BY 的SQL语句可视为只有一个分组的特殊情况，这时被查询选择的所有元组同属于一个匿名分组。,分组查询赋值实现,类似于消除重复运算，分组计算也必须采用全关系算法实现。有两种不依赖于索引的很好赋值算法：排序方法先按分组属性排序关系;扫描已排序关系，为每个分组计算聚合运算值。这一步类似于我们实现未分组时的聚合操作，只是在扫描时必须额外注意分组边界。散列方法将基于分组属性建立一个主存散列表，散列项中含有；当扫描关系时，对每个元组：我们探求散列表发现该元组所属的相应
35、散列项，并更新聚合运算信息。当散列表完成后，各散列项可被用来计算相应分组的回答元组。,6.9 各类代数操作符赋值实现小结,6.9.1 缓冲区的影响分析,6.9.2 各类代数操作符赋值实现小结,6.9 各类代数操作符赋值实现小结,6.9.1 缓冲区的影响 在关系操作符的各种实现方案中，有效利用缓冲池非常重要。在已讨论的各种算法中，我们都显式考虑了缓冲池大小对算法选择的重要性。还有三点值得我们特别注意：如果有几个操作并发执行，它们需要共享缓冲池。这将减少每个操作实际可用的缓存页数量。如果利用索引存取元组，特别是存取非聚集元组时，一个页可能先后被请求多次，能否在缓冲池中找到之前已被请求过的页，取决于
36、缓冲池的大小和置换策略。如果特定操作符有某种重复存取页的模式，我们就能增加在主存中发现页的可能性通过选择一个好得置换策略或为操作保留有效的缓存页。,6.9 各类代数操作符赋值实现小结,6.9.2 各类代数操作符赋值实现小结 选择(c(R)和不消除重复的简单投影(L(R)都可按一次多元组算法实现，可以逐页依次独立处理。只需扫描关系一次，总代价为M；主存需求也只有2个缓存页。如有排序和可匹配索引可用，还可进一步优化选择算法。 消除重复操作符()通常与投影结合处理。消除重复、分组聚合操作等一元操作符，以及连接、集合并/交/差等二元操作符的赋值，都必须按全关系的算法来实现。 如果可用主存可容纳一元操作的整个关系，或容纳二元操作的较小关系，则可采用一趟的算法来实现。否则，我们需要寻求两趟甚至多趟算法,6.9 各类代数操作符赋值实现小结,6.9.2 各类代数操作符赋值实现小结全关系的两趟算法实现要点：第1步：进行分区划分，将输入关系按排序或散列方式进行分区；第2步：进行逐个分区或逐个分区对的处理。还可通过合并分区划分的第二阶段与第2步，来改进算法，降低算法代价。如果采用散列方式，还可通过采用建立主存散列表结构的方法，来进一步降低CPU代价。,