6、两趟扫描算法.md

### 两趟扫描算法

#### 基本思路

整个关系操作存在的问题（ $\delta$(R）, $\gamma$(R） , $\tau$(R））

* 理论上，任何一个元组需要与所有元组进行比较，才能确定是否重复，才能知道是否是一个新的组，才能确定位于何序位置，但这些需要内存
* 如果需保存的待处理数据块数远远大于内存可用块数时，怎么办？



思路

* 第一趟：划分子集，并使子集具有某种特性，如有序或相同散列值等
* 第二趟：处理全局性内容的操作，形成结果关系。如多子集间的归并排序，相同散列值子集的操作等


	<img src="https://img-blog.csdnimg.cn/20201127134452149.png" width="50%" height="50%" />




#### 多路归并排序

内排序和外排序

* 内排序问题: 待排序的数据可一次性地装入内存中，即排序者可以完整地看到和操纵所有数据。内存中数据的排序算法：插入排序算法、选择排序算法、冒泡排序算法。
* 外排序问题: 待排序的数据不能一次性装入内存，即排序者不能一次完整地看到和操纵所有数据，需要将数据分批装入内存分批处理的排序问题；
* 示例：内存--2GB；待排序数据--7GB, 10GB, 100GB，或者更大数据集合。这种需要使用硬盘等外部存储设备进行大数据集合排序的过程/算法称为外排序(External sorting) 。



问题分析

* 情景

  * 读写磁盘块函数: ReadBlock, WriteBlock
  * 内存大小: 共Bmemory=6块, 每块可装载Rblock=5个元素
  * 待排序数据:共占用Bproblem=12块，加起来一共 Rproblem=60个元素,

* 第一趟：划分子集合与分别排序，并重新写入磁盘

  * Bproblem块数据可划分为N个子集合,  使每个子集合的块数小于内存可用块数，即：Bproblem/N<Bmemory。每个子集合都可装入内存并采用内排序算法排好序并重新写回磁盘。

    
	<img src="https://img-blog.csdnimg.cn/20201127134605826.png" width="50%" height="50%" />
  * 划分为 4 组，即每组 3 块。下面是第一趟结束重新写入磁盘的，排好序后的四个子集合

    ![在这里插入图片描述](https://img-blog.csdnimg.cn/20201127134953568.png#pic_center)


* 第二趟：归并子集合

  * 占用内存页数：子集合个数 + 排序缓冲（1个） + 输出缓冲（1个）

  
	<img src="https://img-blog.csdnimg.cn/2020112713501446.png" width="50%" height="50%" />

  * 过程模拟

  
	<img src="https://img-blog.csdnimg.cn/2020112713504634.png" width="50%" height="50%" />



  * 算法的复杂性：

    * 3 B(R）---不考虑最终结果的写回；
    * 4 B(R）—考虑最终结果的写回

  * 算法的应用条件

    * 子集合的块数 < Bmemory（因为第一趟扫描要把一个子集合完整加载到内存排好序）
    * 子集合数< Bmemory（因为第二趟扫描归并要加载每个子集合的一个数据块）

  * 即大数据集块数<$Bmemory^2$

* 算法描述

  ![在这里插入图片描述](https://img-blog.csdnimg.cn/20201127135119482.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70#pic_center)




更大规模数据集的排序问题—多趟/多阶段

* 情景
  * 内存大小:共Bmemory=3块
  * 待排序数据: 共占用Bproblem=30块
* 基本策略
  * 1、30块的数据集->10个子集合，每个子集合3块，排序并存储。
  * 2、10个已排序子集合分成5个组：每个组2个子集合,分别进行二路归并，则可得到5个排好序的集合；
  * 3、5个集合再分成3个组：每个组2个子集，剩余一个单独1组，分别进行二路归并，可得3个排好序的集合；再分组，再归并得到2个排好序的集合；再归并便可完成最终的排序。



#### 基于排序实现

 $\delta$(R）---DISTINCT

* 第一趟：划分子表，并进行子表排序

* 第二趟：归并阶段，在排序的基础上，直接将重复的记录剔出掉-不输出

* 算法的复杂性，同TPMMS:  3B(R）---不考虑输出；4B(R）---考虑输出。

 
	<img src="https://img-blog.csdnimg.cn/20201127135134201.png" width="50%" height="50%" />



$\gamma$(R） ---GROUP BY

* 第一趟：划分子表，并进行子表排序

* 第二趟：归并阶段，在排序基础上，将不重复的记录，作为新分组输出；将重复的记录进行分组聚集计算。

* 算法的复杂性，同TPMMS: 3B(R）---不考虑输出；4B(R）---考虑输出。

  

	<img src="https://img-blog.csdnimg.cn/20201127135200758.png" width="50%" height="50%" />
 

$\tau$(R） ---SORTING

* 第一趟：划分子表，并进行子表排序

* 第二趟：归并阶段，直接归并排序即可。

* 算法的复杂性，同TPMMS: 3B(R）---不考虑输出；4B(R）---考虑输出。



$\bigcup_S$, $\bigcap_S$，$-_S$ 和 $\bigcup_B$, $\bigcap_B$，$-_B$

* $\bigcup_B$无需两趟，直接两个关系合并即可，$\bigcup_S$需两趟, 需要去重复。

  第一趟：划分R和S的子表并子表排序；第二趟：归并时**注意是R的输入还是S的输入**。R和S两路输入之间去重复性合并输出。

 
	<img src="https://img-blog.csdnimg.cn/20201127135244688.png" width="50%" height="50%" />

* $\bigcap_S$和$\bigcap_B$都需要两趟, 需要处理出现次数或者去重复。

  第一趟：划分R和S的子表并子表排序；第二趟：归并时**注意是R的输入还是S的输入**。R和S的两路输入之间按要求进行输出

* $-_S$和$-_B$都需要两趟, 需要处理出现次数或者去重复。

  第一趟：划分R和S的子表并子表排序；第二趟：归并时**注意是R的输入还是S的输入**。R和S的两路输入之间按要求进行输出

  



R JOIN S

* 第一趟：划分R和S的子表并进行子表排序，排序均基于Y属性排序。

* 第二趟：归并时**注意是R的输入还是S的输入**。R和S的两路输入之间进行连接检查并连接后输出。

  

#### 多路散列合并

基本思想

* 核心：hash值相近（即类似的元素），最后都会聚集到一起

* 第一趟：散列子表。用散列函数hp，将原始关系划分成M-1个子表，并存储

* 第二趟：单独处理每个**子表用另一散列函数**hr，将子表读入内存并建立内存结构，进行不同操作的处理

	<img src="https://img-blog.csdnimg.cn/20201127135317716.png" width="30%" height="50%" />


注意：不能做排序操作。



#### 基于散列实现

 $\delta$(R）---DISTINCT

* 核心思想：元组在子表上不重复，则在大关系中亦不重复
  * Hp将可能重复的元组散列到同一子表，hr将可能重复的元组散列到同一内存块中。

* 第一趟：将原始关系通过hp散列成M-1个子表，并进行存储；
* 第二趟：处理每个子表。将每个子表读入内存，并用另一函数hr形成散列数据结构，进行去重复操作。
* 应选择不同的hp和hr，例如：如下是一种方案
  * Hp= 计算元组部分属性的值 MOD M。
  * Hr= 计算整个元组的值 MOD M。
* 算法的复杂性，3B(R）---不考虑输出；4B(R）---考虑输出。



$(R） ---GROUP BY

* 核心思想：同一分组的所有记录应在同一个子表中：Hp。同一子表中同一分组的所有记录应在同一内存块中：Hr。
  * Hp和Hr不能相同，但都以分组属性为基础。

* 第一趟：将原始关系通过hp散列成M-1个子表，并进行存储；
* 第二趟：处理每个子表。将每个子表读入内存，并用另一函数hr形成散列数据结构，进行分组聚集操作。
* 应选择不同的hp和hr，例如：如下是一种方案
  * Hp= 计算“分组属性”的值 MOD M。
  * Hr= 以“分组属性”的二进制位串重新计算值，然后 MOD M。

* 算法的复杂性，3B(R）---不考虑输出；4B(R）)---考虑输出



$\bigcup_S$, $\bigcap_S$，$-_S$ 和 $\bigcup_B$, $\bigcap_B$，$-_B$

* 使用相同散列函数散列两个操作对象R和S，形成R1,...,RM和S1,...,SM，R operator S = $\bigcup_{i=1,...,M}$(Ri operator Si)

  * $\bigcup_B$ 无需两趟，直接两个关系合并即可；

  * $\bigcup_S$ 需两趟，需要去重复。

    第一趟：以相同散列函数散列R和S形成M-2个子表Ri,Si；

    第二趟：将Si再整体散列读入到内存中，再依次处理Ri的每一块。如判断在Ri,Si都出现元组t,则仅输出t的一个副本，否则输出Si和Ri。

* $\bigcap_S$和$\bigcap_B$：可采取相似方法处理(略)。

* $-_S$和$-_B$：可采取相似方法处理(略)。

	<img src="https://img-blog.csdnimg.cn/20201127135355521.png?" width="30%" height="50%" />



R join S

* 以连接属性Y作散列关键字，设计散列函数。
* 第一趟：使用相同散列函数散列两个操作对象R和S，形成R1,...,RM和S1,...,SM，R $\Join_{R.Y=S.Y}$S = $\bigcup_{i=1,...,M}$(Ri $\Join_{Ri.Y=Si.Y}$ Si)
* 第二趟：将Si再整体散列读入到内存中，再依次处理Ri的每一块。进行连接。