第6课关系操作符赋值.ppt

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个缓存页。 如有排序和可匹配索引可用，还可进一步优化选择算法。 消除重复操作符(?)通常与投影结合处理。消除重复、分组聚合操作等一元操作符，以及连接、集合并/交/差等二元操作符的赋值，都必须按全关系的算法来实现。 如果可用主存可容纳一元操作的整个关系，或容纳二元操作的较小关系，则可采用一趟的算法来实现。否则，我们需要寻求两趟甚至多趟算法 6.9 各类代数操作符赋值实现小结 6.9.2 各类代数操作符赋值实现小结 全关系的两趟算法实现要点： 第1步：进行分区划分，将输入关系按排序或散列方式进行分区； 第2步：进行逐个分区或逐个分区对的处理。 还可通过合并分区划分的第二阶段与第2步，来改进算法，降低算法代价。 如果采用散列方式，还可通过采用建立主存散列表结构的方法，来进一步降低CPU代价。 6.9 各类代数操作符赋值实现小结 6.4.3 利用索引进行选择赋值 有能与选择条件相匹配的索引可用 基本代价计算式：IH(I)+?SC(A,R)/FP(R)? 有关影响因素 索引组织结构（顺序、B+树或散列） 选择条件（等值、范围或其它选择） 满足条件的元组总数（索引键是否为码属性） 关系元组是否聚簇存储、索引是否聚集 rids是否按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) 对子项中