第 13 章 - 物化与排序 (Materialization and Sorting)

本章讨论关系代数操作符 materialize、sort、groupby 和 mergejoin。这些操作符会把输入记录保存到临时表中，从而将输入物化。物化允许操作符多次访问记录而不必重新计算，这能产生比仅使用管道式操作符高效得多的查询实现。

13.1 物化的价值 (The Value of Materialization)

到目前为止，你看到的每个操作符都有管道式实现。这类实现具有以下特征：

• 记录按需一次计算一条，并且不会保存。
• 访问已经看过的记录的唯一方式，是从头重新计算整个操作。

本章讨论会物化其输入的操作符。这些操作符的扫描在打开时读取输入记录，并把输出记录保存到一个或多个临时表中。这些实现称为对输入进行预处理，因为它们在请求任何输出记录之前就完成所有计算。物化的目的，是提高后续扫描的效率。

例如，考虑第 13.5 节将介绍的 groupby 操作符。该操作符根据指定分组字段对输入记录分组，并为每个组计算聚合函数。确定分组最简单的方式，是按分组字段对输入记录排序，使同一组的记录彼此相邻。因此，一种好的实现策略是先物化输入，把记录保存到一个按分组字段排序的临时表中。然后，只需对临时表做一次遍历，就可以完成聚合函数的计算。

物化是一把双刃剑。一方面，使用临时表可以显著提高扫描效率。另一方面，创建临时表会带来明显开销，因为它要写入并读取临时表。此外，创建临时表意味着必须预处理整个输入，即使客户端只关心少数输出记录也是如此。

只有当这些成本能被扫描效率的提升抵消时，物化实现才有用。本章的四个操作符都有非常高效的物化实现。

13.2 临时表 (Temporary Tables)

物化实现把输入记录存储在临时表中。临时表与普通表有三点不同：

• 临时表不是通过表管理器的 createTable 方法创建的，它的元数据也不会出现在系统目录中。在 SimpleDB 中，每个临时表管理自己的元数据，并拥有自己的 getLayout 方法。
• 当临时表不再需要时，数据库系统会自动删除它。在 SimpleDB 中，文件管理器会在系统初始化期间删除这些表。
• 恢复管理器不会记录临时表的变更。临时表不需要恢复之前的状态，因为它在所属查询完成之后就不会再使用。

SimpleDB 通过 TempTable 类实现临时表，其代码见图 13.1。构造函数创建一个空表，并给它分配一个唯一名称（形式为 tempN，其中 N 是某个整数）。该类包含三个公共方法。open 方法为该表打开一个表扫描；tableName 和 getLayout 方法返回临时表的元数据。

图 13.1 SimpleDB TempTable 类的代码 (The code for the SimpleDB class TempTable)

public class TempTable {
    private static int nextTableNum = 0;
    private Transaction tx;
    private String tblname;
    private Layout layout;

    public TempTable(Transaction tx, Schema sch) {
        this.tx = tx;
        tblname = nextTableName();
        layout = new Layout(sch);
    }

    public UpdateScan open() {
        return new TableScan(tx, tblname, layout);
    }

    public String tableName() {
        return tblname;
    }

    public Layout getLayout() {
        return layout;
    }

    private static synchronized String nextTableName() {
        nextTableNum++;
        return "temp" + nextTableNum;
    }
}

13.3 物化 (Materialization)

本节介绍一个新的关系代数操作符，称为 materialize。materialize 操作符没有可见功能。它以一张表作为唯一参数，输出记录与输入记录完全相同。也就是说：

materialize(T) = T

materialize 操作符的目的，是把子查询的输出保存在临时表中，避免这些记录被多次计算。本节考察该操作符的用途和实现。

13.3.1 物化示例 (An Example of Materialization)

考虑图 13.2a 的查询树。回忆一下，乘积操作会针对左子树的每条记录，检查右子树的每条记录。因此，左子树的记录访问一次，而右子树的记录会访问多次。

反复访问右侧记录的问题在于，它们需要被反复重新计算。在图 13.2a 中，实现需要多次读取整个 ENROLL 表，并且每次都要搜索成绩为 “A” 的记录。使用图 7.8 的统计数据，可以这样计算该乘积的成本：2005 届有 900 名学生。管道式实现会为这 900 名学生中的每一名读取整个 50,000 块的 ENROLL 表，也就是对 ENROLL 产生 45,000,000 次块访问。再加上 4500 个 STUDENT 块，总计 45,004,500 次块访问。

图 13.2b 的查询树包含两个 materialize 节点。先考虑右侧 select 节点之上的 materialize 节点。该节点创建一个临时表，其中包含成绩为 “A” 的 ENROLL 记录。每当乘积节点从右侧请求一条记录时，materialize 节点都会直接从这个临时表取得记录，而不是搜索 ENROLL。

这种物化会显著降低乘积成本。考虑如下分析。临时表比 ENROLL 小 14 倍，也就是 3572 块。右侧 materialize 节点需要 53,572 次块访问来创建表（50,000 次访问读取 ENROLL，3572 次访问写入临时表）。临时表创建之后会被读取 900 次，共 3,214,800 次访问。再加上 4500 次 STUDENT 块访问，合计 3,272,872 次块访问。换句话说，物化把原查询树的成本降低了 82%（如果每次块访问为 1 ms，就节省超过 11 小时）。创建临时表的成本与它带来的节省相比微不足道。

现在考虑图 13.2b 左侧的 materialize 节点。该节点扫描 STUDENT 表，并创建一个包含所有 2005 届学生的临时表。随后乘积节点会检查这个临时表一次。然而，原查询树中的乘积节点也会检查 STUDENT 表一次。因为两种情况下 STUDENT 记录都只检查一次，所以左侧 materialize 节点实际上增加了查询成本。一般来说，只有当节点输出会被反复计算时，materialize 节点才有用。

图 13.2 应在何处使用 materialize 操作符？(Where to use the materialize operator?)

(a) 原始查询；(b) 对乘积的左右两侧都进行物化。

13.3.2 物化成本 (The Cost of Materialization)

图 13.3 描绘了包含 materialize 节点的查询树结构。该节点的输入是记为 T2 的子查询。当用户打开查询 T1 的计划时，其根计划会打开子计划，并沿树向下依次进行。当 materialize 计划被打开时，它会预处理其输入。具体来说，该计划会打开 T2 的扫描，求值它，把输出保存到临时表中，并关闭 T2 的扫描。在查询 T1 的扫描期间，materialize 扫描会通过访问临时表中对应记录来响应请求。注意，子查询 T2 只会被访问一次，用于填充临时表；之后就不再需要它。

与 materialize 节点相关的成本可以分为两部分：预处理输入的成本，以及执行扫描的成本。预处理成本是 T2 的成本加上把记录写入临时表的成本。扫描成本是从临时表读取记录的成本。假设临时表长度为 B 块，那么成本可表示如下：

• 预处理成本 = B + 输入成本
• 扫描成本 = B

图 13.3 包含 materialize 节点的查询树 (A query tree containing a materialize node)

        T1
        |
  materialize
        |
        T2

13.3.3 实现物化操作符 (Implementing the Materialize Operator)

SimpleDB 的 MaterializePlan 类实现了 materialize 操作符；代码见图 13.4。open 方法预处理输入：它创建新的临时表，为该表和输入打开扫描，把输入记录复制到表扫描中，关闭输入扫描，并返回表扫描。blocksAccessed 方法返回物化表的估计大小。该大小通过计算新记录的每块记录数（RPB），再用输出记录数除以 RPB 得到。recordsOutput 和 distinctValues 方法的值与底层计划相同。

注意，blocksAccessed 不包含预处理成本。原因是临时表只构建一次，却可能被扫描多次。

图 13.4 SimpleDB MaterializePlan 类的代码 (The code for the SimpleDB class MaterializePlan)

public class MaterializePlan implements Plan {
    private Plan srcplan;
    private Transaction tx;

    public MaterializePlan(Transaction tx, Plan srcplan) {
        this.srcplan = srcplan;
        this.tx = tx;
    }

    public Scan open() {
        Schema sch = srcplan.schema();
        TempTable temp = new TempTable(tx, sch);
        Scan src = srcplan.open();
        UpdateScan dest = temp.open();

        while (src.next()) {
            dest.insert();
            for (String fldname : sch.fields())
                dest.setVal(fldname, src.getVal(fldname));
        }
        src.close();
        dest.beforeFirst();
        return dest;
    }

    public int blocksAccessed() {
        // 创建一个虚拟 Layout 对象来计算槽大小
        Layout y = new Layout(srcplan.schema());
        double rpb = (double) (tx.blockSize() / y.slotSize());
        return (int) Math.ceil(srcplan.recordsOutput() / rpb);
    }

    public int recordsOutput() {
        return srcplan.recordsOutput();
    }

    public int distinctValues(String fldname) {
        return srcplan.distinctValues(fldname);
    }

    public Schema schema() {
        return srcplan.schema();
    }
}

如果希望在成本公式中包含建表成本，就需要向 Plan 接口新增一个方法（例如 preprocessingCost），并重写各种计划估算公式以包含它。这个任务留给练习 13.9。另一种做法是，假定预处理成本足够小，并在估算中忽略它。

还要注意，没有 MaterializeScan 类。open 方法直接返回临时表的表扫描。

13.4 排序 (Sorting)

另一个有用的关系代数操作符是 sort。sort 操作符接受两个参数：一张输入表和一个字段名列表。输出表与输入表拥有相同记录，但会按字段排序。例如，下面的查询按 GradYear 对 STUDENT 表排序，毕业年份相同的学生再按姓名排序。如果两个学生姓名和毕业年份都相同，那么它们的记录可以以任意顺序出现。

sort(STUDENT, [GradYear, SName])

规划器使用 sort 来实现 SQL 查询的 order by 子句。本章稍后还会使用排序来实现 groupby 和 mergejoin 操作符。数据库引擎需要能够高效地对记录排序。本节讨论这个问题及其 SimpleDB 解决方案。

13.4.1 为什么排序需要物化输入 (Why Sort Needs to Materialize Its Input)

不使用物化也可以实现排序。例如，考虑图 13.5 查询树中的 sort 节点。该节点的输入是学生及其专业的集合，输出按学生姓名排序。为简单起见，假设没有两个学生同名，因此输入记录有不同的排序值。

图 13.5 包含 sort 节点的查询树 (A query tree containing a sort node)

在 sort 操作符的非物化实现中，next 方法需要把扫描定位到具有下一个最大 SName 值的输入记录。为此，该方法必须遍历输入记录两次：第一次找到下一个最大值，第二次移动到具有该值的记录。虽然这种实现可行，但对于大表来说会极其低效，完全不实用。

在排序的物化实现中，open 方法会预处理输入记录，把它们按排序顺序保存到临时表中。每次调用 next 都只是从临时表中检索下一条记录。这个实现用一些初始预处理成本换取非常高效的扫描。假设创建并排序临时表可以相对高效地完成（确实可以），那么这种物化实现将比非物化实现便宜得多。

13.4.2 基本归并排序算法 (The Basic Mergesort Algorithm)

入门编程课程中教授的标准排序算法（如插入排序和快速排序）称为内部排序算法，因为它们要求所有记录同时位于内存中。然而，数据库引擎不能假设一张表能完整装入内存；因此它必须使用外部排序算法。最简单、最常见的外部排序算法称为归并排序 (mergesort)。

归并排序算法基于 run 的概念。一个 run 是表中已经排好序的一段。未排序表有多个 run；已排序表恰好有一个 run。例如，假设你想按学生 ID 排序，而 STUDENT 记录的 SId 值当前顺序如下：

2  6  20  4  1  16  19  3  18

这张表包含四个 run。第一个 run 包含 [2, 6, 20]，第二个包含 [4]，第三个包含 [1, 16, 19]，第四个包含 [3, 18]。

归并排序分两阶段工作。第一阶段称为 split，扫描输入记录，并把每个 run 放入自己的临时表中。第二阶段称为 merge，反复合并这些 run，直到只剩一个 run；最终 run 就是排序后的表。

merge 阶段以一系列迭代方式工作。在每次迭代中，当前 run 集合被分成若干对；每一对 run 被合并成一个 run。这些结果 run 形成新的当前 run 集合。新集合中的 run 数量是之前的一半。迭代持续进行，直到当前集合只包含一个 run。

作为归并排序的例子，来排序上面的 STUDENT 记录。split 阶段识别四个 run，并将每个 run 存入临时表：

Run 1: 2  6  20
Run 2: 4
Run 3: 1  16  19
Run 4: 3  18

merge 阶段的第一次迭代合并 run 1 和 run 2，产生 run 5；合并 run 3 和 run 4，产生 run 6：

Run 5: 2  4  6  20
Run 6: 1  3  16  18  19

第二次迭代合并 run 5 和 run 6，产生 run 7：

Run 7: 1  2  3  4  6  16  18  19  20

现在只有一个 run，因此算法停止。它只用两次 merge 迭代就完成了排序。

假设一张表有 2^N 个初始 run。每次 merge 迭代把成对 run 转换成单个 run，也就是把 run 数量减少为原来的 1/2。因此，排序该文件需要 N 次迭代：第一次迭代将其减少为 2^(N-1) 个 run，第二次减少为 2^(N-2) 个 run，第 N 次减少为 2^0 = 1 个 run。一般来说，具有 R 个初始 run 的表会在 log2 R 次 merge 迭代后完成排序。

13.4.3 改进归并排序算法 (Improving the Mergesort Algorithm)

有三种方式可以提高基本归并排序算法的效率：

• 增加一次合并的 run 数量。
• 减少初始 run 数量。
• 避免写入最终排序表。

本节考察这些改进。

增加一次合并中的 run 数量 (Increasing the Number of Runs in a Merge)

算法可以不合并成对 run，而是一次合并三个 run，甚至更多 run。假设算法一次合并 k 个 run。那么它会在 k 个临时表上各打开一个扫描。每一步，它查看每个扫描的当前记录，把值最小的记录复制到输出表，并移动该扫描到下一条记录。这个步骤重复执行，直到所有 k 个 run 的记录都复制到输出表。

一次合并多个 run 会减少排序表所需的迭代次数。如果表从 R 个初始 run 开始，并且一次合并 k 个 run，那么排序该文件只需要 logk R 次迭代。如何知道应该使用哪个 k 值？为什么不在一次迭代中合并所有 run？答案取决于可用缓冲区数量。为了合并 k 个 run，需要 k+1 个缓冲区：k 个输入扫描各一个缓冲区，输出扫描一个缓冲区。

现在可以假设算法任意选择一个 k 值。第 14 章将考察如何选择最佳 k 值。

减少初始 run 数量 (Reducing the Number of Initial Runs)

如果要减少初始 run 数量，就需要增加每个 run 中的记录数。可以使用两种算法。

第一种算法见图 13.6。该算法忽略输入记录天然形成的 run，而是创建长度总是一块的 run。它的工作方式是反复把一块大小的输入记录存入临时表。由于这一块记录会位于内存中的缓冲页内，算法可以使用内存排序算法（如快速排序）对这些记录排序，而不产生任何磁盘访问。把这一块记录排序成一个 run 之后，再把该块保存到磁盘。

图 13.6 创建恰好一块长的初始 run 的算法 (An algorithm to create initial runs that are exactly one block long)

重复执行，直到没有更多输入记录：
1. 把一块大小的输入记录读入新的临时表。
2. 使用内存排序算法对这些记录排序。
3. 把这一块临时表保存到磁盘。

第二种算法类似，但它使用额外一块内存作为输入记录的“暂存区”。它先用记录填满暂存区。只要可能，它就反复从暂存区删除一条记录，把它写入当前 run，并向暂存区添加另一条输入记录。当暂存区中所有记录都小于 run 中最后一条记录时，这个过程会停止。此时，当前 run 被关闭，并开始一个新的 run。该算法的代码见图 13.7。

使用暂存区的好处是，你会不断向暂存区加入记录，这意味着总能从一个块大小的候选池中选择 run 的下一条记录。因此，每个 run 很可能包含超过一块的记录。

图 13.7 创建较大初始 run 的算法 (An algorithm to create large initial runs)

1. 用输入记录填满一块大小的暂存区。
2. 开始一个新的 run。
3. 重复执行，直到暂存区为空：
   a. 如果暂存区中没有任何记录适合当前 run，则：
      关闭当前 run，并开始一个新 run。
   b. 从暂存区中选择大于当前 run 最后一条记录、且值最低的记录。
   c. 将该记录复制到当前 run。
   d. 从暂存区删除该记录。
   e. 如果还有输入记录，则把下一条输入记录加入暂存区。
4. 关闭当前 run。

下面的例子比较这两种创建初始 run 的方式。再次考虑前面按 SId 值排序 STUDENT 记录的例子。假设一个块能容纳三条记录，并且记录初始顺序为：

2  6  20  4  1  16  19  3  18

这些记录恰好形成四个 run，如前所述。假设使用图 13.6 的算法减少初始 run 数量。那么记录会按三条一组读取，每组单独排序。因此最终得到三个初始 run：

Run 1: 2  6  20
Run 2: 1  4  16
Run 3: 3  18  19

再假设使用图 13.7 的算法减少 run 数量。首先读取前三条记录到暂存区：

暂存区: 2  6  20
Run 1:

接下来选择最小值 2，把它加入 run，从暂存区移除，并读取下一条记录到暂存区：

暂存区: 6  20  4
Run 1: 2

下一个最小值是 4，因此把它加入 run，从暂存区移除，并读入下一条输入值：

暂存区: 6  20  1
Run 1: 2  4

此时，最小值是 1，但该值太小，不能成为当前 run 的一部分。于是，下一个可行值是 6，把它加入 run，并读取下一条输入值到暂存区：

暂存区: 20  1  16
Run 1: 2  4  6

继续执行，会把 16、19 和 20 加入 run。此时，暂存区全部由不能加入该 run 的记录组成：

暂存区: 1  3  18
Run 1: 2  4  6  16  19  20

因此开始一个新的 run。因为已经没有更多输入记录，这个 run 将包含暂存区中的三条记录：

Run 1: 2  4  6  16  19  20
Run 2: 1  3  18

该算法只产生两个初始 run。第一个 run 长度为两块。

不写入最终排序表 (Don't Write the Final Sorted Table)

回忆一下，每个物化实现都有两个阶段：预处理阶段，把输入记录物化到一个或多个临时表中；扫描阶段，使用这些临时表决定下一条输出记录。

在基本归并排序算法中，预处理阶段创建一个排序后的临时表，扫描则读取该表。这个策略简单，但不是最优。

假设预处理阶段不创建排序后的临时表，而是在最终 merge 迭代之前停止，也就是在临时表数量不超过 k 时停止。扫描阶段会把这 k 张表作为输入，并由自己执行最终合并。具体来说，该阶段会为这 k 张表各打开一个扫描。每次调用 next 时，它会检查这些扫描的当前记录，并选择排序值最小的记录。

在任一时刻，扫描阶段都需要跟踪 k 个扫描中哪一个包含当前记录。这个扫描称为当前扫描。当客户端请求下一条记录时，实现会把当前扫描移动到下一条记录，确定包含最低记录的扫描，并把该扫描指定为新的当前扫描。

总结来说，扫描阶段的工作是按排序顺序返回记录，就好像这些记录存储在一张排序表中。但它并不需要实际创建那张表。相反，它使用预处理阶段交给它的 k 张表。因此，可以避免写入（以及读取）最终排序表所需的块访问。

13.4.4 归并排序成本 (The Cost of Mergesort)

现在使用与 materialize 操作符类似的分析来计算排序成本。图 13.8 描绘了包含 sort 节点的查询树结构。

图 13.8 包含 sort 节点的查询树 (A query tree containing a sort node)

与 sort 节点相关的成本可以分为两部分：预处理成本和扫描成本。

• 预处理成本是 T2 的成本，加上把记录拆分成 run 的成本，再加上除最后一次 merge 迭代之外的所有 merge 迭代成本。
• 扫描成本是从临时表记录执行最终 merge 的成本。

为了更具体，假设如下：

• 算法一次合并 k 个 run。
• 有 R 个初始 run。
• 物化后的输入记录需要 B 块。

split 阶段会写每个块一次，因此拆分需要 B 次块访问，加上输入成本。记录可在 logk R 次迭代中排序完成。其中一次迭代由扫描阶段执行，其余迭代由预处理阶段执行。在每次预处理迭代中，每个 run 的记录都会读一次、写一次；因此该迭代需要 2B 次块访问。在扫描阶段，每个 run 中的记录会读一次，成本为 B 次块访问。把这些值合并并化简，得到以下成本公式：

预处理成本 = 2B log_k R - B + 输入成本
扫描成本 = B

作为一个具体例子，假设你想排序一张 1000 块的存储表，其初始 run 长度为一块（即 B = R = 1000）。这张表是存储表，所以输入成本为 1000 块。如果一次合并 2 个 run，那么需要 10 次 merge 迭代才能完全排序记录（因为 log2 1000 ≈ 10）。上述公式说明，预处理记录需要 20,000 次块访问，最终扫描还需要 1000 次。如果一次合并 10 个 run（即 k = 10），那么只需要 3 次迭代，预处理只需要 6000 次块访问。

继续这个例子，假设一次合并 1000 个 run（即 k = 1000）。那么 logk R = 1，所以预处理成本是 B 加输入成本，也就是 2000 次块访问。注意，这种情况下排序成本与物化成本相同。特别是，预处理阶段不需要执行任何合并，因为 split 阶段已经得到 k 个 run。因此，预处理成本就是读取表和拆分记录的成本，也就是 2B 次块访问。

13.4.5 实现归并排序 (Implementing Mergesort)

SimpleDB 的 SortPlan 和 SortScan 类实现了 sort 操作符。

SortPlan 类 (The Class SortPlan)

SortPlan 的代码见图 13.9。

open 方法执行归并排序算法。具体来说，它一次合并两个 run（即 k = 2），并且不会尝试减少初始 run 数量。（练习 13.10 到 13.13 会要求你实现这些改进。）

私有方法 splitIntoRuns 执行归并排序算法的 split 阶段，方法 doAMergeIteration 执行 merge 阶段的一次迭代；该方法会反复调用，直到返回不超过两个 run。此时，open 把 run 列表传给 SortScan 构造函数，由它处理最终 merge 迭代。

splitIntoRuns 方法先创建一个临时表并在其上打开扫描（“目标扫描”）。然后该方法遍历输入扫描。每条输入记录都会插入目标扫描。每当一个新的 run 开始时，目标扫描会关闭，另一个临时表被创建并打开。该方法结束时，会创建若干临时表，每个临时表包含一个 run。

doAMergeIteration 方法接收当前临时表列表。它对列表中的每一对临时表反复调用 mergeTwoRuns，并返回一个包含合并后临时表的列表。

mergeTwoRuns 方法为两个表各打开一个扫描，并创建一个临时表保存结果。该方法反复从输入扫描中选择值最小的记录，把该记录复制到结果中。当其中一个扫描完成时，另一个扫描的剩余记录会被添加到结果中。

成本估算方法很直接。recordsOutput 和 distinctValues 方法返回与输入表相同的值，因为排序表包含相同记录和相同的值分布。blocksAccessed 方法估计遍历排序扫描所需的块访问次数，该次数等于排序表中的块数。由于排序表和物化表大小完全相同，这个计算与 MaterializePlan 完全相同。因此，该方法创建一个“虚拟”物化计划，仅用于调用其 blocksAccessed 方法。与 MaterializePlan 一样，预处理成本不包含在 blocksAccessed 方法中，原因相同。

比较记录的工作由 RecordComparator 类完成，其代码见图 13.10。该类比较两个扫描的当前记录。它的 compare 方法遍历排序字段，并使用 compareTo 比较每个扫描当前记录中的值。如果所有值都相等，则 compareTo 返回 0。

图 13.9 SimpleDB SortPlan 类的代码 (The code for the SimpleDB class SortPlan)

public class SortPlan implements Plan {
    private Plan p;
    private Transaction tx;
    private Schema sch;
    private RecordComparator comp;

    public SortPlan(Plan p, List<String> sortfields, Transaction tx) {
        this.p = p;
        this.tx = tx;
        sch = p.schema();
        comp = new RecordComparator(sortfields);
    }

    public Scan open() {
        Scan src = p.open();
        List<TempTable> runs = splitIntoRuns(src);
        src.close();
        while (runs.size() > 2)
            runs = doAMergeIteration(runs);
        return new SortScan(runs, comp);
    }

    public int blocksAccessed() {
        // 不包含排序的一次性成本
        Plan mp = new MaterializePlan(tx, p);
        return mp.blocksAccessed();
    }

    public int recordsOutput() {
        return p.recordsOutput();
    }

    public int distinctValues(String fldname) {
        return p.distinctValues(fldname);
    }

    public Schema schema() {
        return sch;
    }

    private List<TempTable> splitIntoRuns(Scan src) {
        List<TempTable> temps = new ArrayList<>();
        src.beforeFirst();
        if (!src.next())
            return temps;

        TempTable currenttemp = new TempTable(tx, sch);
        temps.add(currenttemp);
        UpdateScan currentscan = currenttemp.open();
        while (copy(src, currentscan))
            if (comp.compare(src, currentscan) < 0) {
                // 开始一个新的 run
                currentscan.close();
                currenttemp = new TempTable(tx, sch);
                temps.add(currenttemp);
                currentscan = (UpdateScan) currenttemp.open();
            }
        currentscan.close();
        return temps;
    }

    private List<TempTable> doAMergeIteration(List<TempTable> runs) {
        List<TempTable> result = new ArrayList<>();
        while (runs.size() > 1) {
            TempTable p1 = runs.remove(0);
            TempTable p2 = runs.remove(0);
            result.add(mergeTwoRuns(p1, p2));
        }
        if (runs.size() == 1)
            result.add(runs.get(0));
        return result;
    }

    private TempTable mergeTwoRuns(TempTable p1, TempTable p2) {
        Scan src1 = p1.open();
        Scan src2 = p2.open();
        TempTable result = new TempTable(tx, sch);
        UpdateScan dest = result.open();

        boolean hasmore1 = src1.next();
        boolean hasmore2 = src2.next();
        while (hasmore1 && hasmore2)
            if (comp.compare(src1, src2) < 0)
                hasmore1 = copy(src1, dest);
            else
                hasmore2 = copy(src2, dest);

        if (hasmore1)
            while (hasmore1)
                hasmore1 = copy(src1, dest);
        else
            while (hasmore2)
                hasmore2 = copy(src2, dest);

        src1.close();
        src2.close();
        dest.close();
        return result;
    }

    private boolean copy(Scan src, UpdateScan dest) {
        dest.insert();
        for (String fldname : sch.fields())
            dest.setVal(fldname, src.getVal(fldname));
        return src.next();
    }
}

图 13.10 SimpleDB RecordComparator 类的代码 (The code for the SimpleDB class RecordComparator)

public class RecordComparator implements Comparator<Scan> {
    private Collection<String> fields;

    public RecordComparator(Collection<String> fields) {
        this.fields = fields;
    }

    public int compare(Scan s1, Scan s2) {
        for (String fldname : fields) {
            Constant val1 = s1.getVal(fldname);
            Constant val2 = s2.getVal(fldname);
            int result = val1.compareTo(val2);
            if (result != 0)
                return result;
        }
        return 0;
    }
}

SortScan 类 (The Class SortScan)

SortScan 类实现扫描；其代码见图 13.11。构造函数期望一个包含一个或两个 run 的列表。它通过打开这些表并移动到第一条记录来初始化 run。（如果只有一个 run，则变量 hasmore2 被设为 false，第二个 run 永远不会被考虑。）

变量 currentscan 指向 merge 中包含最近记录的扫描。get 方法从该扫描获取值。next 方法移动当前扫描到下一条记录，然后从两个扫描中选择值最低的记录。变量 currentscan 随后指向该扫描。

该类还拥有两个公共方法：savePosition 和 restorePosition。这些方法允许客户端（特别是第 13.6 节的 mergejoin 扫描）回到先前见过的记录，并从那里继续扫描。

图 13.11 SimpleDB SortScan 类的代码 (The code for the SimpleDB class SortScan)

public class SortScan implements Scan {
    private UpdateScan s1, s2 = null, currentscan = null;
    private RecordComparator comp;
    private boolean hasmore1, hasmore2 = false;
    private List<RID> savedposition;

    public SortScan(List<TempTable> runs, RecordComparator comp) {
        this.comp = comp;
        s1 = (UpdateScan) runs.get(0).open();
        hasmore1 = s1.next();
        if (runs.size() > 1) {
            s2 = (UpdateScan) runs.get(1).open();
            hasmore2 = s2.next();
        }
    }

    public void beforeFirst() {
        s1.beforeFirst();
        hasmore1 = s1.next();
        if (s2 != null) {
            s2.beforeFirst();
            hasmore2 = s2.next();
        }
    }

    public boolean next() {
        if (currentscan == s1)
            hasmore1 = s1.next();
        else if (currentscan == s2)
            hasmore2 = s2.next();

        if (!hasmore1 && !hasmore2)
            return false;
        else if (hasmore1 && hasmore2) {
            if (comp.compare(s1, s2) < 0)
                currentscan = s1;
            else
                currentscan = s2;
        }
        else if (hasmore1)
            currentscan = s1;
        else if (hasmore2)
            currentscan = s2;
        return true;
    }

    public void close() {
        s1.close();
        if (s2 != null)
            s2.close();
    }

    public Constant getVal(String fldname) {
        return currentscan.getVal(fldname);
    }

    public int getInt(String fldname) {
        return currentscan.getInt(fldname);
    }

    public String getString(String fldname) {
        return currentscan.getString(fldname);
    }

    public boolean hasField(String fldname) {
        return currentscan.hasField(fldname);
    }

    public void savePosition() {
        RID rid1 = s1.getRid();
        RID rid2 = s2.getRid();
        savedposition = Arrays.asList(rid1, rid2);
    }

    public void restorePosition() {
        RID rid1 = savedposition.get(0);
        RID rid2 = savedposition.get(1);
        s1.moveToRid(rid1);
        s2.moveToRid(rid2);
    }
}

13.5 分组与聚合 (Grouping and Aggregation)

groupby 关系代数操作符接受三个参数：一张输入表、一组分组字段、一组聚合表达式。它把输入记录组织成组，具有相同分组字段值的记录属于同一组。其输出表对每个组包含一行；该行对每个分组字段和聚合表达式各有一列。

例如，下面的查询为每个学生专业返回该专业学生的最小和最大毕业年份。给定图 1.1 的 STUDENT 表，图 13.12 展示该查询的输出。

groupby(STUDENT, {MajorID}, {Min(GradYear), Max(GradYear)})

一般来说，聚合表达式指定一个聚合函数和一个字段。在上面的查询中，聚合表达式 Min(GradYear) 返回组中记录的最小 GradYear 值。SQL 中可用的聚合函数包括 Min、Max、Count、Sum 和 Avg。

图 13.12 示例 groupby 查询的输出 (The output of the example groupby query)

MajorId	MinOfGradYear	MaxOfGradYear
10	2021	2022
20	2019	2022
30	2020	2021

实现 groupby 操作符的主要问题是如何创建记录组。最好的解决方案是创建一个临时表，其中记录按分组字段排序。这样每个组中的记录会彼此相邻，因此实现只需对排序表做一次遍历，就可以计算每个组的信息。图 13.13 给出了算法。

图 13.13 执行聚合的算法 (An algorithm to perform aggregation)

1. 创建一个包含输入记录的临时表，并按分组字段排序。
2. 移动到表中的第一条记录。
3. 重复执行，直到临时表耗尽：
   a. 令“组值”为当前记录的分组字段值。
   b. 对每条分组字段值等于该组值的记录：
      把记录读入组列表。
   c. 为组列表中的记录计算指定聚合函数。

聚合算法的成本可以分为预处理成本和扫描成本。这些成本很直接。预处理成本是排序成本，扫描成本是对排序记录的一次遍历。换句话说，groupby 操作符与 sort 具有相同成本。

SimpleDB 使用 GroupByPlan 和 GroupByScan 类实现 groupby 算法，见图 13.14 和图 13.15。

GroupByPlan 中的 open 方法为输入记录创建并打开一个排序计划。得到的排序扫描被传入 GroupByScan 构造函数。

groupby 扫描按需读取排序扫描中的记录。具体来说，每次调用 next 时，该方法读取下一个组中的记录。当读到另一个组的记录时（或检测到排序扫描没有更多记录时），该方法识别出一个组结束；因此，每次调用 next 时，底层扫描中的当前记录总是下一组的第一条记录。

GroupValue 类保存当前组的信息，其代码见图 13.16。构造函数接收一个扫描和分组字段。当前记录的字段值定义该组。getVal 方法返回指定字段的值。equals 方法在两个 GroupValue 对象具有相同分组字段值时返回 true，hashCode 方法为每个 GroupValue 对象分配哈希值。

SimpleDB 把每个聚合函数（例如 MIN、COUNT 等）都实现为一个类。该类的对象负责跟踪一个组中记录的相关信息，计算该组的聚合值，并确定计算字段的名称。这些方法属于 AggregationFn 接口，其代码见图 13.17。processFirst 方法用当前记录作为组的第一条记录来开始一个新组。processNext 方法向已有组添加另一条记录。

聚合函数类的一个例子是 MaxFn，它实现 MAX，见图 13.18。客户端把聚合字段名传给构造函数。对象使用这个字段名检查组中每条记录的字段值，并把最大值保存在变量 val 中。

图 13.14 SimpleDB GroupByPlan 类的代码 (The code for the SimpleDB class GroupByPlan)

public class GroupByPlan implements Plan {
    private Plan p;
    private List<String> groupfields;
    private List<AggregationFn> aggfns;
    private Schema sch = new Schema();

    public GroupByPlan(Transaction tx, Plan p,
                       List<String> groupfields,
                       List<AggregationFn> aggfns) {
        this.p = new SortPlan(tx, p, groupfields);
        this.groupfields = groupfields;
        this.aggfns = aggfns;
        for (String fldname : groupfields)
            sch.add(fldname, p.schema());
        for (AggregationFn fn : aggfns)
            sch.addIntField(fn.fieldName());
    }

    public Scan open() {
        Scan s = p.open();
        return new GroupByScan(s, groupfields, aggfns);
    }

    public int blocksAccessed() {
        return p.blocksAccessed();
    }

    public int recordsOutput() {
        int numgroups = 1;
        for (String fldname : groupfields)
            numgroups *= p.distinctValues(fldname);
        return numgroups;
    }

    public int distinctValues(String fldname) {
        if (p.schema().hasField(fldname))
            return p.distinctValues(fldname);
        else
            return recordsOutput();
    }

    public Schema schema() {
        return sch;
    }
}

图 13.15 SimpleDB GroupByScan 类的代码 (The code for the SimpleDB class GroupByScan)

public class GroupByScan implements Scan {
    private Scan s;
    private List<String> groupfields;
    private List<AggregationFn> aggfns;
    private GroupValue groupval;
    private boolean moregroups;

    public GroupByScan(Scan s, List<String> groupfields,
                       List<AggregationFn> aggfns) {
        this.s = s;
        this.groupfields = groupfields;
        this.aggfns = aggfns;
        beforeFirst();
    }

    public void beforeFirst() {
        s.beforeFirst();
        moregroups = s.next();
    }

    public boolean next() {
        if (!moregroups)
            return false;
        for (AggregationFn fn : aggfns)
            fn.processFirst(s);
        groupval = new GroupValue(s, groupfields);
        while (moregroups = s.next()) {
            GroupValue gv = new GroupValue(s, groupfields);
            if (!groupval.equals(gv))
                break;
            for (AggregationFn fn : aggfns)
                fn.processNext(s);
        }
        return true;
    }

    public void close() {
        s.close();
    }

    public Constant getVal(String fldname) {
        if (groupfields.contains(fldname))
            return groupval.getVal(fldname);
        for (AggregationFn fn : aggfns)
            if (fn.fieldName().equals(fldname))
                return fn.value();
        throw new RuntimeException("no field " + fldname);
    }

    public int getInt(String fldname) {
        return getVal(fldname).asInt();
    }

    public String getString(String fldname) {
        return getVal(fldname).asString();
    }

    public boolean hasField(String fldname) {
        if (groupfields.contains(fldname))
            return true;
        for (AggregationFn fn : aggfns)
            if (fn.fieldName().equals(fldname))
                return true;
        return false;
    }
}

图 13.16 SimpleDB GroupValue 类的代码 (The code for the SimpleDB class GroupValue)

public class GroupValue {
    private Map<String, Constant> vals = new HashMap<>();

    public GroupValue(Scan s, List<String> fields) {
        for (String fldname : fields)
            vals.put(fldname, s.getVal(fldname));
    }

    public Constant getVal(String fldname) {
        return vals.get(fldname);
    }

    public boolean equals(Object obj) {
        GroupValue gv = (GroupValue) obj;
        for (String fldname : vals.keySet()) {
            Constant v1 = vals.get(fldname);
            Constant v2 = gv.getVal(fldname);
            if (!v1.equals(v2))
                return false;
        }
        return true;
    }

    public int hashCode() {
        int hashval = 0;
        for (Constant c : vals.values())
            hashval += c.hashCode();
        return hashval;
    }
}

图 13.17 SimpleDB AggregationFn 接口的代码 (The code for the SimpleDB AggregationFn interface)

public interface AggregationFn {
    void processFirst(Scan s);
    void processNext(Scan s);
    String fieldName();
    Constant value();
}

图 13.18 SimpleDB MaxFn 类的代码 (The code for the SimpleDB class MaxFn)

public class MaxFn implements AggregationFn {
    private String fldname;
    private Constant val;

    public MaxFn(String fldname) {
        this.fldname = fldname;
    }

    public void processFirst(Scan s) {
        val = s.getVal(fldname);
    }

    public void processNext(Scan s) {
        Constant newval = s.getVal(fldname);
        if (newval.compareTo(val) > 0)
            val = newval;
    }

    public String fieldName() {
        return "maxof" + fldname;
    }

    public Constant value() {
        return val;
    }
}

13.6 归并连接 (Merge Joins)

第 12 章开发了高效的 indexjoin 操作符，用于在连接谓词形式为 A = B 时连接两张表，其中 A 位于左侧表，B 位于右侧表。这些字段称为连接字段 (join fields)。当右侧表是存储表，并且在其连接字段上有索引时，indexjoin 操作符适用。本节考察一个高效的连接操作符，称为 mergejoin，它总是适用。其算法见图 13.19。

图 13.19 mergejoin 算法 (The mergejoin algorithm)

1. 对每张输入表：
   使用其连接字段作为排序字段，对表排序。
2. 并行扫描排序后的表，寻找连接字段之间的匹配。

考虑算法第 2 步。暂时假设连接左侧的表在其连接字段上没有重复值，那么该算法类似于乘积扫描。也就是说，它扫描左侧表一次。对于每条左侧记录，它搜索右侧表，寻找匹配记录。然而，记录已排序这一事实会大幅简化搜索。特别注意：

• 匹配的右侧记录必须出现在前一条左侧记录的匹配记录之后。
• 匹配记录在表中彼此相邻。

因此，每次考虑新的左侧记录时，只需从右侧表上次停止的位置继续扫描，并在遇到大于左侧连接值的连接值时停止。也就是说，右侧表只需扫描一次。

13.6.1 mergejoin 示例 (An Example of Mergejoin)

下面的查询使用 mergejoin 连接 DEPT 和 STUDENT 表。

mergejoin(DEPT, STUDENT, DId=MajorId)

归并连接算法的第一步创建临时表，分别保存按 DId 和 MajorId 排序的 DEPT 和 STUDENT 内容。图 13.20 展示这些排序表，使用图 1.1 中的示例记录，并增加了一个新系（篮筐编织系，DId = 18）。

图 13.20 排序后的 DEPT 和 STUDENT 表 (The sorted DEPT and STUDENT tables)

DId	DName
10	compsci
18	basketry
20	math
30	drama

SId	SName	MajorId	GradYear
1	joe	10	2021
3	max	10	2022
9	lee	10	2021
2	amy	20	2020
4	sue	20	2022
6	kim	20	2020
8	pat	20	2019
5	bob	30	2020
7	art	30	2021

算法第二步扫描排序后的表。当前 DEPT 记录是 10 号系。它扫描 STUDENT，在前三条记录找到匹配。当它移动到第四条记录（Amy）时，发现 MajorId 值不同，因此知道 10 号系已经处理完。它移动到下一条 DEPT 记录（篮筐编织系），并把该记录的 DId 值与当前 STUDENT 记录（即 Amy）的 MajorId 值比较。由于 Amy 的 MajorId 值更大，算法知道该系没有匹配记录，因此移动到下一条 DEPT 记录（数学系）。该记录与 Amy 的记录匹配，也与接下来三条 STUDENT 记录匹配。随着算法继续遍历 STUDENT，它最终到达 Bob 的记录，该记录不再匹配当前系。因此它移动到下一条 DEPT 记录（戏剧系），并继续在 STUDENT 中搜索，其中 Bob 和 Art 的记录匹配。只要其中一张表没有更多记录，连接就可以结束。

如果归并连接左侧存在重复连接值，会发生什么？回忆一下，当算法读到不再匹配的右侧记录时，会移动到下一条左侧记录。如果下一条左侧记录具有相同的连接值，那么算法需要回到第一条匹配的右侧记录。也就是说，包含匹配记录的所有右侧块都必须重新读取，这可能增加连接成本。

幸运的是，左侧重复值很少出现。查询中的大多数连接往往基于键-外键关系。例如，在上面的连接中，DId 是 DEPT 的键，MajorId 是它的外键。由于键和外键在创建表时声明，查询规划器可以使用这些信息，确保具有键的表位于归并连接左侧。

为了计算 mergejoin 算法成本，注意预处理阶段会对每张输入表排序，扫描阶段会遍历排序后的表。如果没有左侧重复值，那么每张排序表都会扫描一次，连接成本就是两次排序操作成本之和。如果存在左侧重复值，那么右侧扫描中对应记录会被读取多次。

例如，可以使用图 7.8 的统计数据计算 STUDENT 和 DEPT 归并连接的成本。假设算法合并成对 run，并且每个初始 run 长度为 1 块。预处理成本包括排序 4500 块的 STUDENT 表（9000 * log2(4500) - 4500 = 112,500 次块访问，再加 4500 的输入成本），以及排序 2 块的 DEPT 表（4 * log2(2) - 2 = 2 次块访问，再加 2 的输入成本）。因此总预处理成本为 117,004 次块访问。扫描成本是排序后两张表大小之和，即 4502 次块访问。因此连接总成本为 121,506 次块访问。

把这个成本与第 8 章中把连接作为乘积后接选择来执行的成本比较。那个成本公式为 B1 + R1 * B2，即 184,500 次块访问。

13.6.2 实现 mergejoin (Implementing Mergejoin)

SimpleDB 的 MergeJoinPlan 和 MergeJoinScan 类实现归并连接算法。

MergeJoinPlan 类 (The Class MergeJoinPlan)

MergeJoinPlan 的代码见图 13.21。open 方法使用指定连接字段，为两张输入表各打开一个排序扫描。然后它把这些扫描传给 MergeJoinScan 构造函数。

blocksAccessed 方法假定每个扫描都会遍历一次。其想法是，即使存在左侧重复值，匹配的右侧记录也会位于同一块或最近访问过的块中。因此，很可能只需要很少（甚至零次）额外块访问。

recordsOutput 方法计算连接的记录数。该值等于乘积中的记录数除以连接谓词过滤掉的记录数量。distinctValues 方法的代码很直接。由于连接不会增加或减少字段值，因此估计值与适当的底层查询相同。

图 13.21 SimpleDB MergeJoinPlan 类的代码 (The code for the SimpleDB class MergeJoinPlan)

public class MergeJoinPlan implements Plan {
    private Plan p1, p2;
    private String fldname1, fldname2;
    private Schema sch = new Schema();

    public MergeJoinPlan(Transaction tx, Plan p1, Plan p2,
                         String fldname1, String fldname2) {
        this.fldname1 = fldname1;
        List<String> sortlist1 = Arrays.asList(fldname1);
        this.p1 = new SortPlan(tx, p1, sortlist1);
        this.fldname2 = fldname2;
        List<String> sortlist2 = Arrays.asList(fldname2);
        this.p2 = new SortPlan(tx, p2, sortlist2);
        sch.addAll(p1.schema());
        sch.addAll(p2.schema());
    }

    public Scan open() {
        Scan s1 = p1.open();
        SortScan s2 = (SortScan) p2.open();
        return new MergeJoinScan(s1, s2, fldname1, fldname2);
    }

    public int blocksAccessed() {
        return p1.blocksAccessed() + p2.blocksAccessed();
    }

    public int recordsOutput() {
        int maxvals = Math.max(p1.distinctValues(fldname1),
                               p2.distinctValues(fldname2));
        return (p1.recordsOutput() * p2.recordsOutput()) / maxvals;
    }

    public int distinctValues(String fldname) {
        if (p1.schema().hasField(fldname))
            return p1.distinctValues(fldname);
        else
            return p2.distinctValues(fldname);
    }

    public Schema schema() {
        return sch;
    }
}

MergeJoinScan 类 (The Class MergeJoinScan)

MergeJoinScan 的代码见图 13.22。next 方法执行寻找匹配的困难工作。扫描使用变量 joinval 跟踪最近的连接值。当调用 next 时，它读取下一条右侧记录。如果该记录的连接值等于 joinval，就找到了匹配，该方法返回。如果不是，方法移动到下一条左侧记录。如果该记录的连接值等于 joinval，说明有重复的左侧值。该方法把右侧扫描重新定位到具有该连接值的第一条记录并返回。否则，方法反复从连接值较小的扫描读取，直到找到匹配或某个扫描耗尽。如果找到匹配，则设置变量 joinval，并保存当前右侧位置。如果某个扫描耗尽，则该方法返回 false。

图 13.22 SimpleDB MergeJoinScan 类的代码 (The code for the SimpleDB class MergeJoinScan)

public class MergeJoinScan implements Scan {
    private Scan s1;
    private SortScan s2;
    private String fldname1, fldname2;
    private Constant joinval = null;

    public MergeJoinScan(Scan s1, SortScan s2,
                         String fldname1, String fldname2) {
        this.s1 = s1;
        this.s2 = s2;
        this.fldname1 = fldname1;
        this.fldname2 = fldname2;
        beforeFirst();
    }

    public void close() {
        s1.close();
        s2.close();
    }

    public void beforeFirst() {
        s1.beforeFirst();
        s2.beforeFirst();
    }

    public boolean next() {
        boolean hasmore2 = s2.next();
        if (hasmore2 && s2.getVal(fldname2).equals(joinval))
            return true;

        boolean hasmore1 = s1.next();
        if (hasmore1 && s1.getVal(fldname1).equals(joinval)) {
            s2.restorePosition();
            return true;
        }

        while (hasmore1 && hasmore2) {
            Constant v1 = s1.getVal(fldname1);
            Constant v2 = s2.getVal(fldname2);
            if (v1.compareTo(v2) < 0)
                hasmore1 = s1.next();
            else if (v1.compareTo(v2) > 0)
                hasmore2 = s2.next();
            else {
                s2.savePosition();
                joinval = s2.getVal(fldname2);
                return true;
            }
        }
        return false;
    }

    public int getInt(String fldname) {
        if (s1.hasField(fldname))
            return s1.getInt(fldname);
        else
            return s2.getInt(fldname);
    }

    public String getString(String fldname) {
        if (s1.hasField(fldname))
            return s1.getString(fldname);
        else
            return s2.getString(fldname);
    }

    public Constant getVal(String fldname) {
        if (s1.hasField(fldname))
            return s1.getVal(fldname);
        else
            return s2.getVal(fldname);
    }

    public boolean hasField(String fldname) {
        return s1.hasField(fldname) || s2.hasField(fldname);
    }
}

13.7 本章小结 (Chapter Summary)

• 操作符的物化实现会预处理其底层记录，并把它们存储到一个或多个临时表中。因此，它的扫描方法更高效，因为只需要检查临时表。
• 物化实现只计算输入一次，并且可以利用排序。然而，即使用户只关心少数记录，它也必须计算整张输入表。虽然可以为任何关系操作符编写物化实现，但只有当其预处理成本能被后续扫描节省抵消时，物化实现才有用。
• materialize 操作符创建一个包含所有输入记录的临时表。当其输入会被反复执行时，例如位于乘积节点右侧时，它很有用。
• 数据库系统使用外部排序算法把记录排序到临时表中。最简单、最常见的外部排序算法称为归并排序。归并排序算法把输入记录拆分成 run，然后反复合并这些 run，直到记录完成排序。
• 当初始 run 数量较少时，归并排序更高效。一种直接方法是通过把输入记录读入一块并使用内部排序算法排序，创建长度为一块的初始 run。另一种方法是把输入记录读入一块大小的暂存区，并通过反复选择暂存区中值最低的记录来构造 run。
• 当一次合并更多 run 时，归并排序也更高效。合并的 run 越多，所需迭代越少。每个被合并的 run 都需要一个缓冲区来管理，因此最大 run 数量受可用缓冲区数量限制。
• 归并排序需要 2B log_k(R) - B 次块访问（加上输入成本）来预处理输入，其中 B 是保存排序表所需块数，R 是初始 run 数量，k 是一次合并的 run 数量。
• groupby 操作符的实现按分组字段对记录排序，使每个组中的记录彼此相邻。然后它通过对排序记录做一次遍历，计算每个组的信息。
• mergejoin 算法实现两张表的连接。它首先按连接字段排序每张表。然后并行扫描两张排序表。每次调用 next 方法都会推进值较低的那个扫描。

13.8 建议阅读 (Suggested Reading)

文件排序在整个计算历史中一直是重要（甚至关键）的操作，比数据库系统早许多年。该主题有大量文献，也有许多本章未讨论的归并排序变体。Knuth (1998) 对各种算法给出了全面概述。

SimpleDB 的 SortPlan 代码是归并排序算法的直接实现。Graefe (2006) 一文描述了若干有趣且有用的技术，可以改进这个实现。

Graefe (2003) 一文探讨了排序算法与 B 树算法之间的对偶性。它展示了如何使用 B 树有用地存储归并排序的中间 run，以及如何使用 merge 迭代为已有表创建 B 树索引。

Graefe (1993) 讨论了物化算法，并将其与非物化算法进行了比较。

• Graefe, G. (1993) Query evaluation techniques for large databases. ACM Computing Surveys, 25(2), 73-170.
• Graefe, G. (2003) Sorting and indexing with partitioned B-trees. Proceedings of the CIDR Conference.
• Graefe, G. (2006) Implementing sorting in database systems. ACM Computing Surveys, 38(3), 1-37.
• Knuth, D. (1998) The art of computer programming, Vol. 3: Sorting and searching. Addison-Wesley.

13.9 习题 (Exercises)

概念性练习 (Conceptual Exercises)

13.1. 考虑图 13.2b 的查询树。

(a) 假设 2005 届只有一名学生。右侧 materialize 节点值得使用吗？

(b) 假设 2005 届只有两名学生。右侧 materialize 节点值得使用吗？

(c) 假设乘积节点的左右子树互换。计算物化新的右侧 select 节点所节省的成本。

13.2. 第 13.4 节的基本归并排序算法以迭代方式合并 run。使用该节的例子，它合并 run 1 和 run 2 产生 run 5，合并 run 3 和 run 4 产生 run 6；然后合并 run 5 和 run 6 产生最终 run。假设算法改为顺序合并 run。也就是说，它合并 run 1 和 run 2 产生 run 5，然后合并 run 3 和 run 5 产生 run 6，最后合并 run 4 和 run 6 产生最终 run。

(a) 解释为什么这种“顺序合并”产生最终 run 所需的合并次数总是与迭代合并相同。

(b) 解释为什么顺序合并比迭代合并需要更多（通常多得多）的块访问。

13.3. 考虑图 13.6 和图 13.7 的 run 生成算法。

(a) 假设输入记录已经排序。哪个算法会产生最少的初始 run？请解释。

(b) 假设输入记录按逆序排序。解释为什么两个算法会产生相同数量的初始 run。

13.4. 考虑大学数据库和图 7.8 的统计数据。

(a) 对每张表，估计使用 2、10 或 100 张辅助表对其排序的成本。假设每个初始 run 长度为一块。

(b) 对每一对可以有意义地连接的表，估计执行 mergejoin 的成本（同样使用 2、10 或 100 张辅助表）。

13.5. SortPlan 类中的 splitIntoRuns 方法返回一个 TempTable 对象列表。如果数据库非常大，那么这个列表可能非常长。

(a) 解释这个列表可能如何成为意外低效的来源。

(b) 提出一个更好的解决方案。

编程练习 (Programming Exercises)

13.6. 第 13.4 节描述了一种非物化排序实现。

(a) 设计并实现 NMSortPlan 和 NMSortScan 类，它们在不创建临时表的情况下提供对记录的排序访问。

(b) 完整遍历这种扫描需要多少次块访问？

(c) 假设 JDBC 客户端想找到某个字段具有最小值的记录；客户端通过执行一个按该字段排序的查询，然后选择第一条记录来做到这一点。比较使用物化实现和非物化实现完成此操作所需的块访问次数。

13.7. 服务器重启时，临时表名称会再次从 0 开始。SimpleDB 文件管理器构造函数会删除所有临时文件。

(a) 解释如果允许临时表文件在系统重启后保留下来，SimpleDB 中会发生什么问题。

(b) 系统可以不在重启时删除所有临时文件，而是在创建临时表的事务完成后立即删除该临时表文件。修改 SimpleDB 代码来实现这一点。

13.8. 当 SortPlan 和 SortScan 被要求排序一张空表时会出现什么问题？修改代码修复该问题。

13.9. 修改 SimpleDB 的 Plan 接口（以及所有实现类），使其具有 preprocessingCost 方法，用来估计物化表的一次性成本。相应修改其他估算公式。

13.10. 修改 SortPlan 代码，使其使用图 13.6 的算法构造长度为一块的初始 run。

13.11. 修改 SortPlan 代码，使其使用图 13.7 的算法通过暂存区构造初始 run。

13.12. 修改 SortPlan 代码，使其一次合并三个 run。

13.13. 修改 SortPlan 代码，使其一次合并 k 个 run，其中整数 k 由构造函数提供。

13.14. 修改 SimpleDB 的 Plan 类，使它们跟踪自己的记录是否已排序，如果已排序则跟踪排序字段。然后修改 SortPlan 代码，使其仅在必要时排序记录。

13.15. SQL 查询中的 order by 子句是可选的。如果存在，它由两个关键字 order 和 by 组成，后接一个逗号分隔的字段名列表。

(a) 修改图 9.7 的 SQL 文法，使其包含 order by 子句。

(b) 修改 SimpleDB 词法分析器和查询解析器，以实现语法变更。

(c) 修改 SimpleDB 查询规划器，使其为包含 order by 子句的查询生成适当的排序操作。SortPlan 对象应该是查询树最顶层节点。

13.16. SimpleDB 只实现聚合函数 COUNT 和 MAX。添加实现 MIN、AVG 和 SUM 的类。

13.17. 查找 SQL 聚合语句的语法。

(a) 修改图 9.7 的 SQL 文法，使其包含该语法。

(b) 修改 SimpleDB 词法分析器和查询解析器，以实现语法变更。

(c) 修改 SimpleDB 查询规划器，使其为包含 group by 子句的查询生成适当的 groupby 操作。GroupBy 对象应该位于 select 和 semijoin 节点之上，但位于查询计划中的 extend 和 project 节点之下。

13.18. 定义关系操作符 nodups，其输出表由输入表中的记录组成，但会移除重复项。

(a) 编写 NoDupsPlan 和 NoDupsScan 的代码，类似于 GroupByPlan 和 GroupByScan 的写法。

(b) 去重也可以由没有聚合函数的 groupby 操作符执行。编写 GBNoDupsPlan 的代码，通过创建适当的 GroupByPlan 对象来实现 nodups 操作符。

13.19. 关键字 distinct 可以可选地出现在 SQL 查询的 select 子句中。如果存在，查询处理器应该从输出表中移除重复项。

(a) 修改图 9.7 的 SQL 文法，使其包含 distinct 关键字。

(b) 修改 SimpleDB 词法分析器和查询解析器，以实现语法变更。

(c) 修改基础查询规划器，使其为 select distinct 查询生成适当的 nodups 操作。

13.20. 对单个字段排序表的另一种方式是使用 B 树索引。SortPlan 构造函数会先在排序字段上为物化表创建索引。然后它会为每条数据记录向 B 树添加一条索引记录。随后，通过从头遍历 B 树的叶节点，可以按排序顺序读取记录。

(a) 实现这个版本的 SortPlan。（你需要修改 B 树代码，使所有索引块链接在一起。）

(b) 它需要多少次块访问？它比使用归并排序更高效还是更低效？