基于排序的两趟算法详解.ppt

基于排序的两趟算法 两趟算法介绍 当在关系上执行关系代数操作时，若关系大于一趟算法能够处理的范围，则使用两趟（多趟）算法：来自于操作对象关系中的数据被读到内存，以某种方式处理，再写回磁盘，然后重新读取磁盘以完成操作。 两趟算法介绍 基于排序操作来实现两趟算法的一般过程：对于B（R）X的关系R，将它分为大小为X（X为单个内存缓冲区的大小）的块并排序，然后对于某种任意子表在任意时刻只占用一个内存块（内存缓冲区）的方式，对排好序的子表进行排序。 两阶段多路归并排序（TPMMS） 阶段1：不断将R中的元组放入M个缓冲区，利用内部排序算法对他们排序，将得到的子表放入外存。 阶段2：对排好序的子表进行归并（M-1个输入缓冲区，1个输出缓冲区）。 两阶段多路归并排序（TPMMS） TPMMS代价分析 在第2阶段，由于输出缓冲区的存在，子表数目不能超过M-1.设B(R)为关系R占用的块数，每个子表包含M个块，则要求B≦M(M-1)或近似为B≦M2. 算法在第一趟时读入B个块，并在排序后将子表写回磁盘，故磁盘I/O次数为2B；再第二阶段，子表被读入内存，进行归并后再次被写回，则了两趟总的I/O为4B（若归并后的结果用于其他操作而非写回磁盘则为3B）。 利用排序去重复 阶段1：与原始TPMMS算法相同。 阶段2：选中输入缓冲区的第一个未被选过的元组t，将其拷贝至输出缓冲区，同时删除输入缓冲区中所有此元组，而不是进行排序。 空间代价：B≦M2 I/O代价：3B 注意：每一个输入缓冲区中元组都是内部有序的。 利用排序进行分组和聚集 阶段1：将R中的元组每次读取M个块到内存，并对其分组属性进行排序，将排好序的子表写回外存。 阶段2：选取足够的内存缓冲区存放子表块，对于每个缓冲区的第一个元组，反复查找具有分组属性v最小值的元组，并使其成为下一分组。 阶段3：在此分组上检查符合分组属性v的元组，并计算聚集。 空间代价：B≦M2 I/O代价：3B 基于排序的并、交和差算法 阶段1：对关系R和S分别创建排序子表，并为他们的每个子表使用一块内存缓冲区。 阶段2：对于并，重复地在缓冲区查找一个未被考虑的元组t，将其复制到输出缓冲区，然后删除输入缓冲区中的所有t；对于交，如果t同时在R与S中出现，则复制到输出；对于差R-S，当且仅当t出现在R但不出现在S时输出。 空间代价：B(R)+B(S)≦M2 I/O代价：3(B(R)+B(S)) 基于排序的一个简单连接算法 阶段1：对关系R（X，Y）和S（Y，Z）以连接属性Y为关键字分别创建排序子表并进行归并，但之后只为R与S分别分配一个缓冲区。 阶段2：同时在R和S内存块的前端查找连接属性Y的最小值y。如果y在另一个关系中没有出现，则删除具有关键字y的所有元组；如果出现，则对当前关系中每一个拥有关键字y的元组，输出通过连接另一个关系中具有共同y值的所有元组而组成的新元组。 基于排序的一个简单连接算法 当某一关系的缓冲区中不再有关键字y的元组时，删除另一关系中所有具有y的元组。 算法要求用于连接的属性具有公共值的所有元组必须能够完全装入M个缓冲区。 空间代价：B(R)≦M2且B(S)≦M2 I/O代价：5(B(R)+B(S))