第6章 关系操作符赋值

《第6章 关系操作符赋值》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2部分关系数据库系统实现第6章关系操作符赋值高级数据库系统及其应用第6章关系操作符赋值6.1外部排序6.2关系操作符赋值实现基础6.6连接操作赋值6.7集合操作的赋值实现6.8聚合操作的赋值实现6.9各类代数操作符赋值实现小结6.3RDBMS系统的目录信息6.4选择操作符赋值6.5投影与消除重复操作赋值典型的关系数据库系统体系结构RDBMS系统查询处理的基本过程当用户提出一个SQL查询后，将首先被送到解析器(parser)，进行解析和编译处理。编译后的查询接着被送到查询优化器(optimizer)优化器将利用DB系统目录中信息(

2、Systemcatalog)，产生一个高效的可执行计划。可执行计划是查询赋值的一个蓝图，它被表示为关系代数操作符树的形式――树中的每个节点通常可对应到一个具体的关系操作符。通过调用下层的计划执行器，实现最终查询赋值.关系操作符赋值是查询处理的基础，它们好比是实现整个查询赋值的一些基本积木块。本章集中讨论单个关系操作符的赋值实现问题。6.1外部排序6.1.1一种简单的两路归并排序6.1.2多路归并排序6.1.3两阶段多路归并排序6.1.4最小化外部排序时间排序是DB系统最基本的操作DB系统中有很多场合需要用到排序用户可能希望以某种指

3、定顺序返回查询结果集。排序记录集是批处理建立B+树的第一步(5.3.3)排序是消除一个记录集中重复记录的一种有效方法。广泛使用的关系连接操作，可基于排序的方法实现。6.1.1简单的两路归并排序一个含7个页文件的两路归并排序6.1.1简单的两路归并排序在每个阶段，文件中的每个页将被读入和写出1次，即在每阶段每个页有2次磁盘I/Os。如果输入文件的总页数为M，则完成排序需要的总阶段数为log2M+1，总的代价为2M(log2M+1)次I/Os。为减小排序代价，我们应设法减少归并的阶段数。如果可用的缓存页数不是3而是更多(令有B

4、个)，那么，在第1阶段:可以使用更大的子文件；在归并阶段，可以采用比两路更多路的归并，最多允许采用B-1路归并。6.1.2多路归并排序（图6.2B-1路归并图解）6.1.3两阶段多路归并排序假设可用缓存页总数B，文件总页数为M第1阶段划分子文件，可得子文件总数=M/B。第2阶段归并子文件，因只有两个阶段，要求一次完成所有子文件归并这要求排序子文件总数：M/B≤B-1即要求B>M1/2，否则，必须进行更多个阶段的排序。两阶段排序的总代价为：M*4次I/Os例6.1如果每个页的平均读写时间按15ms计算，计算两阶段排序2500

5、00个页需要的总时间。第一个阶段要读写500000个页，需要时间为500000×0.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个页）输入缓冲区和输出输出缓冲区大小：都取为一个组块大小。以组块为单位进行读写在归并阶段，一次可归

6、并的最大子文件数为(B-b)/b按组块读写进行外部排序(设每个块含b个页）输入缓冲区和输出输出缓冲区大小：都取为一个组块大小。以组块为单位进行读写在归并阶段，一次可归并的最大子文件数为(B-b)/b。选用大组块缓冲区时，归并的阶段数会增加，即算法总的I/Os数将增加。但这完全可从每页平均存取时间减少来得到补偿。在现行机器条件下，即使是使用了较大的块缓冲，除非少数特大的文件，大部分的文件排序都可以在两个阶段内完成排序。表6.1组块大小b=32时一些外部排序需要的阶段数6.2关系操作符赋值实现基础6.2.1关系操作符赋值实现的

7、三个基本操作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)通过基于一个排序键来划分元组，我们通常能够将一个关系操作分解为针对各个分区元组的、代价更小的一组操作。排序和散列是两种最常用的

8、分区划分技术。6.2.2存取路径存取路径所有关系操作符的赋值算法，通常都必须从一个或多个关系检索元组。从关系存取元组的方式也称为存取路径。两个最常用的存取路径1)关系文件扫描；2)索引加上匹配选择条件:attropvalue。如果这个attr也正好