找到相同的键,并不意味着工作结束
两个已排序文件可以同时扫描:当前键不同时,较小的键不可能与另一文件中后续记录匹配。但是当前键相同时,两个游标各前进一步是不够的。一侧的键出现三次,另一侧出现两次,就有六对记录。分组还可能大于内存,所以仅能在内存中做笛卡尔(Cartesian)积的方案并不是完整的外部算法。
下面研究一个明确而简单的算法,其输出由以下定义确定。
定义 20.2.1
(已排序文件的多重集等值连接)
设 、 是有限文件,记录的键取自一个全序集,且该顺序与相等关系一致;两个文件均按键升序排列。文件中某一位置上的记录称为一次出现;即使记录内容相同,不同位置仍是不同的出现。不考虑空值键,并假设比较精确。 与 的多重集等值连接,是由 的一次出现 与 的一次出现 组成、且两者键相等的全部有序对 ,每对计一次,此外不含其他记录对;不保证输出顺序。
因此,若键 在 中出现 次、在 中出现 次,它恰好贡献 对;只在一个文件中出现的键不贡献任何记录对。
存储模型与算法
设 、 分别占 、 个输入块。一个 块可放 条记录,一个 块可放 条;最后一个输入块可以未满。顺序扫描将每个已占用块恰好读取一次。每次读或写一个块算一次传输。暂存 分组与 分组的块容量分别为 、,输出块可放 对。暂存分组和最终输出都紧密存储,非空但未满的最后一块写入一次;空文件无需块传输。读取未满的输入块或暂存块时,用有效记录数识别其内容。
同时预留足够内存,容纳两个输入当前块、两个暂存分组写入缓冲区、 个暂存 分组块、一个暂存 分组读取块和一个输出缓冲区。各类缓冲区大小可以不同;少量描述信息和比较工作空间另计。处理匹配分组时保留输入块,包括下一个键的首条预读记录;输出缓冲区跨分组保留。暂存文件是新建的,重读时没有缓存;此模型不计删除、定位、比较、分配、故障或延迟的成本。
两个游标始终指向下一条未消费记录:
- 如果任一输入结束,读完另一输入但不输出,然后转到步骤 4。否则比较当前键;若不同,消费较小键的整个分组,再进行比较。
- 若两键同为 ,将两侧完整的 分组分别复制到紧密存储的暂存文件 、,保留每次出现;将各侧下一条记录保留为预读记录。每个分组最后非空的部分块也要写出。
- 依次读取每批至多 个 块。对每批完整扫描一次 的所有块,输出该批每条 记录与每条 记录的配对。写出已满的输出块,但把未满缓冲区留给下一分组。处理完毕后删除两个暂存文件,再回到步骤 1。
- 两个输入都读完后,如果输出缓冲区非空则写出。
即使一侧提前结束,读完另一侧的规则仍使下述成本恰好成立。实现也可以提前停止,但这时基础扫描成本取决于另一游标已经走到哪里。
定理 20.2.2
(正确性与精确传输次数)
对每个共同键 ,设两侧出现次数为 ,并令 、,以及 。算法恰好输出多重集等值连接,并进行
次传输。没有共同键时求和为零; 时输出项为零。
证明
(先按键划分,再按批划分,每次传输只计一次)
如果当前 键较小, 剩余的键都不小于其当前键,因此不可能匹配这个较小分组;它也不会匹配已消费的 分组,因为两个游标从不跳过可能的匹配,该共同键在当时已经处理。交换两侧同理,所以跳过较小分组不会遗漏记录对。键相等时,排序保证每个完整分组连续,复制将每次出现恰好保留一次。每条 记录恰属一批,该批的完整 扫描恰好访问每条右侧记录一次,因此每对恰好输出一次;不同键不会配对。内容重复但位置不同的记录同样如此。
两个完整输入扫描需要 次读取。对键 ,写入暂存分组需要 次;读取全部左侧批次需要 次, 批各需读取 个右侧块。输出缓冲区不会在分组之间提前写出,因此 对恰需 次写入。相加得到公式。这是指定实现的成本,并非所有连接的下界;其他合并连接也不一定需要暂存两个分组。
证明透视
两层划分与三项计数约定
正确性部分依靠两层划分。排序把所有匹配记录对按共同键划分,而且只在一处用到:当前键不同时,另一文件后续的键都不小于其当前键,所以可以丢弃较小的分组;没有排序,这一步就没有依据,会遗漏记录对。对固定的键,分批划分左侧的出现,每批都与右侧分组的一次完整扫描相遇;因此每对恰好在一批、一个右侧块中产生。成本部分之所以是精确计数,全靠模型中的三项约定。读完另一侧的规则使基础扫描恰为 ,无论哪个文件先结束。预读记录保留在内存中,所以分组边界落在块内部时,没有输入块被读两次。未满的输出块跨分组保留,使各分组上取整之和变为单一的 。去掉任何一项约定,正确性仍然成立,但公式会变成不等式。
第一个例子在一个小文件上逐项核对公式,其中有一个分组需要两批。
例题 20.2.3
(分组超出一批的容量)
设 、,输入块为
因此 、。键 1 的 ,;键 2 对应 和 。键 4 没有匹配。记录对总数 。键 1 的暂存写入需 次,重读需 次;键 2 则分别需 次和 次。七对输出占四个块。加上五次输入读取,总计 次传输。键 1 虽跨越输入和暂存块边界,六对仍全部输出。
概念视角几何
把每个配对分组看成块对的网格
对一个配对的键 ,设想一个 网格,其格子 装着 第 个暂存块与 第 个块之间的配对; 的每一对恰好落在一格中。第 3 步用至多 行的横条覆盖网格:每条只读一次,共 次读取,而 条中的每一条都扫过全部 列。因此在一个分组内,这个过程就是块嵌套循环连接,而 正是这种铺排的代价。上例中键 1 给出 网格,被切成两条。
例题 20.2.4
(边界情形:没有共同键)
设 ,输入块为
因此 、。游标依次比较 (消费键 的分组)、(消费 )、(消费 )、(消费 )以及 (消费 )。此时 已结束,步骤 1 读完 余下的记录 ,完成 的读取而不输出任何记录对。没有共同键,所以匹配分组的求和为空,;步骤 4 发现输出缓冲区为空,不写任何块。公式给出 ,正是两次顺序扫描的五次块读取。如果没有读完另一侧的规则,实现可以在读了 的两个块后停止,计数便取决于数据,而不是 。
例题 20.2.5
(大量小分组:暂存的代价)
设 、、,并且
则 ,键 都有 ,故 、。每个键需要 次暂存写入和 次暂存读取,三个分组共 次传输。输出共 对,放得进一个输出块。总计 次。若在内存中直接连接这些单条记录的分组,只需 次输入读取和 次输出写入。暂存使算法对任何大小的分组都正确,但遇到大量微小分组时,成本会成倍增加。
下面的反例说明,为什么步骤 2 要复制完整分组,而不是逐对推进游标。
反例模式
两个游标同时前进会遗漏配对
令 、。每次匹配后两个游标同时前进,可能只输出 和 。多重集连接却有六对,包括 和 。只保留同一键的一条记录也会丢失重复次数。
如何理解和比较成本
上述公式以已排序并存盘的文件为起点。如果需要排序,应加上所采用的外部排序实际传输量,包括最后写入,并避免重复计算同一次读取。如果排序器将最后合并结果以流式方式直接送入连接,模型和计数都须修改。同样,若输出以流式方式送往下游而非写盘,只有在另计下游成本时才可移除上述输出写入项。
暂存每个匹配分组使方法容易描述,但对小分组可能浪费传输。其他实现可以将分组留在内存、交换分批方向,或利用可回读的排序输入;这些选择会改变内存假设和传输次数。尤其是重复键分组可能需要多次扫描,所以排序不保证连接成本为线性;存盘结果本身也可能随两侧频数的乘积增长。块计数不能直接证明实际耗时或普遍最优性。
常见错误
常见错误
(输出成本按分组逐一上取整再相加)
把输出成本写成 ,等于假设每个分组后都写出输出缓冲区。上述算法把未满的输出块留给下一分组,所以成本是单一项 。两个共同键各产生一对而 时,逐组相加得 ,算法实际只写一个块。
常见错误
(用分组跨越的输入块数代替紧密存储的大小)
与 计的是紧密存储的暂存文件块数,而不是分组恰好跨越的输入块数。在 的 中,键 的两次出现跨越两个输入块,却只填满 个暂存块。用跨越数计算,会高估暂存写入以及每次重读。
练习与解答
练习 20.2.6
(设 、、、、,唯一共同键满足 、。求精确传输次数。)
核心
解答(3)
- 1
计算紧密存储的分组大小与批数
、、,左侧有 批。
- 2
计算暂存传输
暂存写入需要 次;重读需要 次。
- 3
加上基础扫描与输出
输出需要 次,输入扫描需要 次,总计 次传输。
快速检查
(两个共同键各产生一对,。为什么必须跨分组保留输出缓冲区,定理才精确?)
比较每组后写出与不写出时所写的输出块数。
解答 · 答案
两对可共用一个输出块,定理把它计为 次写入。如果每组后都写出,就会写两个未满块,一次输出写入的计数不再精确。
快速检查
(已排序输入的键频数为 、。求 并指出跳过的分组。)
只有两个文件都有的键才有贡献。
解答 · 答案
共同键是 和 ,所以 。 的键 2 和 的键 3 没有匹配而被跳过。不同位置的相同值仍贡献不同记录对。
快速检查
(某匹配分组的 、、。指定方向需要多少次暂存读取?若交换两侧,且新外层仍可每批放两个块,又是多少?)
把 中 、 的角色交换。
解答 · 答案
指定方向需要 次;交换后需要 次。暂存写入和输出写入次数不变。比较依赖内存足以支持两个方向,不能证明交换后总是更好。