第 14 章 - 高效缓冲利用 (Effective Buffer Utilization)

不同操作符实现有不同的缓冲区需求。例如，select 操作符的管道式实现只使用一个缓冲区，而且使用得非常高效，不需要额外缓冲区。另一方面，sort 操作符的物化实现会一次合并多个 run，并且每个 run 都需要一个缓冲区。

本章考察操作符实现使用额外缓冲区的各种方式，并给出 sort、product 和 join 操作符的高效多缓冲算法。

14.1 查询计划中的缓冲使用 (Buffer Usage in Query Plans)

到目前为止讨论过的关系代数实现，在缓冲区使用方面都非常节俭。例如，每个表扫描一次只 pin 一个块；当它处理完某个块中的记录后，会先 unpin 该块，再 pin 下一个块。select、project 和 product 操作符的扫描不会 pin 任何额外块。因此，给定一个包含 N 张表的查询，SimpleDB 基础查询规划器生成的扫描会同时使用 N 个被 pin 的缓冲区。

考虑第 12 章的索引实现。静态哈希索引把每个桶实现为一个文件，并顺序扫描它，一次 pin 一个块。B 树索引则从根开始一次 pin 一个目录块。它扫描该块以确定合适的子节点，unpin 该块，然后 pin 子块，如此继续，直到找到叶块。这里的分析当然适用于查询。向 B 树插入记录时，可能需要同时 pin 多个缓冲区，以处理块分裂和条目沿树向上的递归插入。练习 12.16 要求你分析插入的缓冲区需求。

现在考虑第 13 章的物化实现。materialize 操作符的实现除了输入查询所需的缓冲区之外，还需要一个缓冲区用于临时表。排序实现的 split 阶段需要一个或两个缓冲区（取决于是否使用暂存区），merge 阶段需要 k + 1 个缓冲区：正在合并的 k 个 run 各一个缓冲区，结果表一个缓冲区。groupby 和 mergejoin 的实现除了排序使用的缓冲区之外，不再需要额外缓冲区。

这个分析说明，除排序之外，一个查询计划同时使用的缓冲区数量大致等于查询中提到的表数量；这个数量通常小于 10，几乎肯定小于 100。可用缓冲区总数通常要大得多。如今的服务器机器通常至少有 16 GB 物理内存。如果其中只有很少的 400 MB 用作缓冲区，那么服务器就有 100,000 个 4 KB 缓冲区。因此，即使数据库系统支持数百个（或数千个）并发连接，只要查询计划能有效利用这些缓冲区，执行某个给定查询时仍然有大量缓冲区可用。本章考察 sort、join 和 product 操作符如何利用这种丰富的缓冲区。

14.2 多缓冲排序 (Multibuffer Sorting)

回忆一下，归并排序算法有两个阶段：第一阶段把记录拆分成 run，第二阶段合并这些 run，直到表完成排序。第 13 章讨论了在 merge 阶段使用多个缓冲区的好处。事实证明，split 阶段也可以利用额外缓冲区。

假设有 k 个缓冲区可用。split 阶段可以一次读取表中的 k 个块到这 k 个缓冲区中，使用内部排序算法把它们排序成一个 k 块 run，然后把这些块写入临时表。也就是说，它不是把记录拆分成长度为一块的 run，而是拆分成长度为 k 块的 run。如果 k 足够大（特别是当 k >= sqrt(B) 时），那么 split 阶段产生的初始 run 不超过 k 个，这意味着预处理阶段不需要做任何事情。多缓冲归并排序算法整合了这些想法，见图 14.1。

图 14.1 多缓冲归并排序算法 (The Multibuffer Mergesort Algorithm)

// split 阶段，使用 k 个缓冲区
1. 重复执行，直到没有更多输入记录：
   a. pin k 个缓冲区，并把 k 个输入记录块读入其中。
   b. 使用内部排序算法对这些记录排序。
   c. 把缓冲区内容写入临时表。
   d. unpin 这些缓冲区。
   e. 把临时表添加到 run 列表。

// merge 阶段，使用 k+1 个缓冲区
2. 重复执行，直到 run 列表只包含一个临时表：
   // 执行一次迭代
   a. 重复执行，直到 run 列表为空：
      i. 为 k 个临时表打开扫描。
      ii. 为一个新的临时表打开扫描。
      iii. 把这 k 个扫描合并到新扫描中。
      iv. 把新的临时表添加到列表 L。
   b. 把 L 中的内容添加到 run 列表。

该算法第 1 步产生 B/k 个初始 run。使用第 13.4.4 节的成本分析可知，多缓冲归并排序需要 log_k(B/k) 次 merge 迭代。这比基本归并排序（其中初始 run 大小为 1）少一次 merge 迭代。换句话说，多缓冲归并排序在预处理阶段节省 2B 次块访问，这意味着使用 k 个缓冲区对一个 B 块表执行多缓冲排序，具有以下成本：

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

如何选择最佳 k 值？k 值决定 merge 迭代次数。特别是，预处理期间执行的迭代次数等于 (log_k B) - 2。因此：

• 当 k = sqrt(B) 时，有 0 次迭代。
• 当 k = cubert(B) 时，有 1 次迭代。
• 当 k = fourthroot(B) 时，有 2 次迭代。

依此类推。

这个计算应该符合直觉。如果 k = sqrt(B)，那么 split 阶段会产生 k 个大小为 k 的 run。这些 run 可以在扫描阶段合并，也就是说预处理期间不需要 merge 迭代。如果 k = cubert(B)，那么 split 阶段会产生 k^2 个大小为 k 的 run。一次 merge 迭代会产生 k 个 run（每个大小为 k^2），随后这些 run 可以在扫描阶段合并。

作为一个具体例子，假设需要排序一个 4 GB 表。如果块大小为 4 KB，那么该表大约包含一百万个块。图 14.2 列出了在预处理期间获得特定 merge 迭代次数所需的缓冲区数量。

图 14.2 排序 4 GB 表所需的预处理迭代次数 (The number of preprocessing iterations required to sort a 4 GB table)

缓冲区数	1000	100	32	16	10	8	6	5	4	3	2
迭代次数	0	1	2	3	4	5	6	7	8	11	18

在图 14.2 的低端，注意只增加几个缓冲区就会带来显著改进：2 个缓冲区需要 18 次迭代，但 10 个缓冲区就把它降到只有 4 次迭代。如此巨大的成本差异意味着，数据库系统用少于 10 个缓冲区排序这张表会是非常糟糕的主意。

图 14.2 的高端展示了排序可以多么高效。很可能有 1000 个缓冲区可用，或者至少有 100 个。图中显示，在有 1000 个缓冲区（等价于 4 MB 内存）的情况下，可以在预处理阶段执行 1000 次内部排序，随后在扫描阶段执行一次 1000 路合并，从而完成 4 GB 表的排序。总成本为三百万次块访问：一百万次读取未排序块，一百万次写入临时表，一百万次读取临时表。这种效率既出人意料，又相当惊人。

这个例子还说明，对于给定表大小 B，多缓冲归并排序只能有效使用某些缓冲区数量，即 sqrt(B)、cubert(B)、fourthroot(B) 等。图 14.2 为 B = 1,000,000 列出了这些值。那么其他缓冲区值如何？如果有 500 个缓冲区可用会怎样？我们知道 100 个缓冲区会产生 1 次预处理 merge 迭代。看看额外 400 个缓冲区是否能派上用场。使用 500 个缓冲区时，split 阶段会产生 2000 个 run，每个 run 有 500 块。第一次 merge 迭代会一次合并 500 个 run，产生 4 个 run（每个 250,000 块）。随后这些 run 可以在扫描阶段合并。所以额外 400 个缓冲区实际上没有帮助，因为仍然需要与 100 个缓冲区相同的迭代次数。

这个分析可以表达为如下规则：如果使用 k 个缓冲区排序长度为 B 块的表，那么 k 应该是 B 的一个根。

14.3 多缓冲笛卡尔积 (Multibuffer Product)

product 操作符的基础实现涉及大量块访问。例如，考虑查询：

product(T1, T2)

SimpleDB 的实现会针对 T1 的每条记录检查整个 T2，并使用一个缓冲区保存 T2 中的记录。也就是说，代码检查完某个 T2 块的最后一条记录后，会 unpin 该块，并 pin T2 的下一个块。这种 unpin 允许缓冲区管理器替换每个 T2 块，这意味着当检查 T1 的下一条记录时，它们可能都需要重新从磁盘读取。在最坏情况下，T2 的每个块会被读取与 T1 中记录数一样多的次数。如果假设 T1 和 T2 都是 1000 块表，并且每块包含 20 条记录，那么查询需要 20,001,000 次块访问。

假设实现不 unpin T2 中的任何块。缓冲区管理器将被迫把 T2 的每个块放入自己的缓冲区。因此，T2 的块会从磁盘读取一次，并在整个查询期间保留在内存中。这个扫描会非常高效，因为它只读取 T1 的每个块一次、T2 的每个块一次。

当然，只有当有足够缓冲区容纳整个 T2 时，这个策略才可行。如果 T2 太大该怎么办？例如，假设 T2 有 1000 块，但只有 500 个缓冲区可用。最好的做法是分两个阶段处理 T2。首先把前 500 块读入可用缓冲区，并计算 T1 与这些块的乘积；然后把 T2 剩余的 500 块读入这些缓冲区，并计算它们与 T1 的乘积。

这个策略非常高效。第一阶段需要读取 T1 一次和 T2 的前半部分一次；第二阶段需要再次读取 T1，并读取 T2 的后半部分一次。总计，T1 读取两次，T2 读取一次，总共只有 3000 次块访问。

多缓冲乘积算法推广了这些想法，见图 14.3。在这个算法中，T1 的块会针对每个 chunk 读取一次。由于有 B2/k 个 chunk，乘积操作需要 B2 + (B1 * B2 / k) 次块访问。

注意，多缓冲乘积实现对待 T1 和 T2 的方式与第 8 章的基础乘积实现相反。在第 8 章中，T2 会被扫描多次；而这里，T1 会被扫描多次。

图 14.3 多缓冲乘积算法 (The multibuffer product algorithm)

设 T1 和 T2 为两张输入表。假设 T2 是存储表（用户定义表或物化临时表），
并包含 B2 个块。

1. 令 k = B2 / i，其中 i 是某个整数。也就是说，k 是 B2 的一个分数。
2. 把 T2 视为由 i 个 chunk 组成，每个 chunk 有 k 块。对于每个 chunk C：
   a. 把 C 的所有块读入 k 个缓冲区。
   b. 计算 T1 和 C 的乘积。
   c. unpin C 的块。

再次假设 T1 和 T2 都是 1000 块表。图 14.4 列出了多缓冲乘积算法在不同缓冲区数量下所需的块访问次数。如果有 1000 个缓冲区可用，那么 T2 可以在单个 chunk 中处理，只需 2000 次块访问。另一方面，如果有 250 个缓冲区可用，那么多缓冲乘积算法会使用 4 个 chunk，每个 250 块；因此表 T1 会被扫描 4 次，T2 会被扫描一次，总共 5000 次块访问。如果只有 100 个缓冲区可用，那么算法会使用 10 个 chunk，总共 11,000 次块访问。所有这些值都远小于基础乘积实现所需的块访问。

图 14.4 对两个 1000 块表取乘积所需的块访问次数 (The block accesses required to take the product of two 1000-block tables)

缓冲区数	1000	500	334	250	200	167	143	125	112	100
chunk 数	1	2	3	4	5	6	7	8	9	10
块访问数	2000	3000	4000	5000	6000	7000	8000	9000	10000	11000

和排序一样，图 14.4 也说明不是所有 k 值都有用。在这个例子中，如果有 300 个缓冲区可用，那么多缓冲乘积算法只能使用其中 250 个。

14.4 确定缓冲分配 (Determining Buffer Allocation)

每个多缓冲算法都会选择 k 个缓冲区，但不会指定 k 的确切值。k 的合适值由可用缓冲区数量、输入表大小和涉及的操作符决定。对于排序，k 是输入表大小的一个根；对于乘积，k 是表大小的一个因子。

目标是选择小于可用缓冲区数量的最大根（或因子）。SimpleDB 的 BufferNeeds 类包含计算这些值的方法，其代码见图 14.5。

该类包含公共静态方法 bestRoot 和 bestFactor。这两个方法几乎相同。每个方法的输入都是可用缓冲区数量和表大小。方法会计算最优缓冲区数量，也就是小于 avail 的最大根或最大因子。bestRoot 方法把变量 k 初始化为 MAX_VALUE，以强制循环至少执行一次（从而确保 k 不会大于 sqrt(B)）。

图 14.5 SimpleDB BufferNeeds 类的代码 (The code for the SimpleDB class BufferNeeds)

public class BufferNeeds {
    public static int bestRoot(int available, int size) {
        int avail = available - 2; // 保留几个缓冲区
        if (avail <= 1)
            return 1;

        int k = Integer.MAX_VALUE;
        double i = 1.0;
        while (k > avail) {
            i++;
            k = (int)Math.ceil(Math.pow(size, 1/i));
        }
        return k;
    }

    public static int bestFactor(int available, int size) {
        int avail = available - 2; // 保留几个缓冲区
        if (avail <= 1)
            return 1;

        int k = size;
        double i = 1.0;
        while (k > avail) {
            i++;
            k = (int)Math.ceil(size / i);
        }
        return k;
    }
}

注意，BufferNeeds 中的方法并不会真的从缓冲区管理器保留缓冲区。相反，它们只是询问缓冲区管理器当前有多少缓冲区可用，并选择一个小于该数量的 k 值。当多缓冲算法尝试 pin 这 k 个块时，其中某些缓冲区可能已经不再可用。在这种情况下，算法会等待，直到缓冲区再次可用。

14.5 实现多缓冲排序 (Implementing Multibuffer Sorting)

在 SimpleDB 的 SortPlan 类中，splitIntoRuns 和 doAMergeIteration 方法决定使用多少缓冲区。目前，splitIntoRuns 以增量方式创建 run，使用一个绑定到临时表的缓冲区；doAMergeIteration 使用三个缓冲区（两个用于输入 run，一个用于输出 run）。本节考虑这些方法需要如何改变，才能实现多缓冲排序。

考虑 splitIntoRuns。该方法实际上并不知道排序表会有多大，因为表尚未创建。不过，该方法可以使用 blocksAccessed 方法做出估计。特别是，splitIntoRuns 可以执行如下代码片段：

int size = blocksAccessed();
int available = tx.availableBuffs();
int numbuffs = BufferNeeds.bestRoot(available, size);

然后，它可以 pin numbuffs 个缓冲区，用输入记录填充这些缓冲区，在内部对它们排序，并把它们写入临时表，如图 14.1 所示。

现在考虑 doAMergeIteration 方法。最佳策略是让该方法从 run 列表中移除 k 个临时表，其中 k 是初始 run 数量的一个根：

int available = tx.availableBuffs();
int numbuffs = BufferNeeds.bestRoot(available, runs.size());
List<TempTable> runsToMerge = new ArrayList<>();
for (int i=0; i<numbuffs; i++)
    runsToMerge.add(runs.remove(0));

然后，该方法可以把 runsToMerge 列表传给 mergeTwoRuns 方法（可以重命名为 mergeSeveralRuns），将它们合并成一个 run。

SimpleDB 发行代码中不包含执行多缓冲排序的 SortPlan 版本。这个任务留给练习 14.15-14.17。

最后，注意使用 SortPlan 的代码（例如 GroupByPlan 和 MergeJoinPlan）无法判断自己使用的是常规排序算法还是多缓冲算法。因此，这些类不需要改变。（不过，MergeJoinPlan 使用的缓冲区数量还有一些小问题；见练习 14.5。）

14.6 实现多缓冲笛卡尔积 (Implementing Multibuffer Product)

要实现多缓冲乘积算法，需要实现 chunk 的概念。回忆一下，chunk 是物化表中长度为 k 块的一部分，并且具有该 chunk 的所有块都能放入可用缓冲区这一性质。ChunkScan 类把 chunk 实现为记录扫描，见图 14.6。

ChunkScan 构造函数接收存储表的元数据，以及 chunk 的第一个和最后一个块号。构造函数为 chunk 中的每个块打开记录页，并把它们存储在一个列表中。扫描还会跟踪当前记录页；最初，当前页是列表中的第一页。next 方法移动到当前页中的下一条记录。如果当前页没有更多记录，那么列表中的下一页成为当前页。与表扫描不同，在 chunk 扫描中从一个块移动到另一个块时，不会关闭之前的记录页（关闭会 unpin 其缓冲区）。相反，chunk 中的记录页只有在 chunk 本身关闭时才会 unpin。

图 14.6 SimpleDB ChunkScan 类的代码 (The code for the SimpleDB class ChunkScan)

public class ChunkScan implements Scan {
    private List<RecordPage> buffs = new ArrayList<>();
    private Transaction tx;
    private String filename;
    private Layout layout;
    private int startbnum, endbnum, currentbnum;
    private RecordPage rp;
    private int currentslot;

    public ChunkScan(Transaction tx, String filename,
                     Layout layout, int startbnum, int endbnum) {
        this.tx = tx;
        this.filename = filename;
        this.layout = layout;
        this.startbnum = startbnum;
        this.endbnum = endbnum;
        for (int i=startbnum; i<=endbnum; i++) {
            BlockId blk = new BlockId(filename, i);
            buffs.add(new RecordPage(tx, blk, layout));
        }
        moveToBlock(startbnum);
    }

    public void close() {
        for (int i=0; i<buffs.size(); i++) {
            BlockId blk = new BlockId(filename, startbnum+i);
            tx.unpin(blk);
        }
    }

    public void beforeFirst() {
        moveToBlock(startbnum);
    }

    public boolean next() {
        currentslot = rp.nextAfter(currentslot);
        while (currentslot < 0) {
            if (currentbnum == endbnum)
                return false;
            moveToBlock(rp.block().number()+1);
            currentslot = rp.nextAfter(currentslot);
        }
        return true;
    }

    public int getInt(String fldname) {
        return rp.getInt(currentslot, fldname);
    }

    public String getString(String fldname) {
        return rp.getString(currentslot, fldname);
    }

    public Constant getVal(String fldname) {
        if (layout.schema().type(fldname) == INTEGER)
            return new Constant(getInt(fldname));
        else
            return new Constant(getString(fldname));
    }

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

    private void moveToBlock(int blknum) {
        currentbnum = blknum;
        rp = buffs.get(currentbnum - startbnum);
        currentslot = -1;
    }
}

MultibufferProductPlan 类实现多缓冲乘积算法；其代码见图 14.7。open 方法物化左侧和右侧记录：左侧作为 MaterializeScan，右侧作为临时表。blocksAccessed 方法需要知道物化右侧表的大小，以便计算 chunk 数量。由于该表要到计划打开时才存在，该方法使用 MaterializePlan 提供的估计值来估计大小。recordsOutput 和 distinctValues 方法的代码与 ProductPlan 相同，也很直接。

图 14.7 SimpleDB MultibufferProductPlan 类的代码 (The code for the SimpleDB class MultibufferProductPlan)

public class MultibufferProductPlan implements Plan {
    private Transaction tx;
    private Plan lhs, rhs;
    private Schema schema = new Schema();

    public MultibufferProductPlan(Transaction tx, Plan lhs, Plan rhs) {
        this.tx = tx;
        this.lhs = new MaterializePlan(tx, lhs);
        this.rhs = rhs;
        schema.addAll(lhs.schema());
        schema.addAll(rhs.schema());
    }

    public Scan open() {
        Scan leftscan = lhs.open();
        TempTable t = copyRecordsFrom(rhs);
        return new MultibufferProductScan(tx, leftscan, t.tableName(),
                                          t.getLayout());
    }

    public int blocksAccessed() {
        // 这里猜测 chunk 数量
        int avail = tx.availableBuffs();
        int size = new MaterializePlan(tx, rhs).blocksAccessed();
        int numchunks = size / avail;
        return rhs.blocksAccessed() +
               (lhs.blocksAccessed() * numchunks);
    }

    public int recordsOutput() {
        return lhs.recordsOutput() * rhs.recordsOutput();
    }

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

    public Schema schema() {
        return schema;
    }

    private TempTable copyRecordsFrom(Plan p) {
        Scan src = p.open();
        Schema sch = p.schema();
        TempTable tt = new TempTable(tx, sch);
        UpdateScan dest = (UpdateScan) tt.open();
        while (src.next()) {
            dest.insert();
            for (String fldname : sch.fields())
                dest.setVal(fldname, src.getVal(fldname));
        }
        src.close();
        dest.close();
        return tt;
    }
}

MultibufferProductScan 的代码见图 14.8。其构造函数通过在右侧文件大小上调用 BufferNeeds.bestFactor 来确定 chunk 大小。然后，它把左侧扫描定位到第一条记录，为右侧第一个 chunk 打开一个 ChunkScan，并从这两个扫描创建一个 ProductScan。也就是说，变量 prodscan 包含左侧扫描与当前 chunk 之间的基础乘积扫描。大多数扫描方法都使用这个乘积扫描。例外是 next 方法。

next 方法移动到当前乘积扫描中的下一条记录。如果该扫描没有更多记录，那么该方法关闭该扫描，为下一个 chunk 创建新的乘积扫描，并移动到其第一条记录。当没有更多 chunk 要处理时，该方法返回 false。

图 14.8 SimpleDB MultibufferProductScan 类的代码 (The code for the SimpleDB class MultibufferProductScan)

public class MultibufferProductScan implements Scan {
    private Transaction tx;
    private Scan lhsscan, rhsscan = null, prodscan;
    private String filename;
    private Layout layout;
    private int chunksize, nextblknum, filesize;

    public MultibufferProductScan(Transaction tx, Scan lhsscan,
                                  String filename, Layout layout) {
        this.tx = tx;
        this.lhsscan = lhsscan;
        this.filename = filename;
        this.layout = layout;
        filesize = tx.size(filename);
        int available = tx.availableBuffs();
        chunksize = BufferNeeds.bestFactor(available, filesize);
        beforeFirst();
    }

    public void beforeFirst() {
        nextblknum = 0;
        useNextChunk();
    }

    public boolean next() {
        while (!prodscan.next())
            if (!useNextChunk())
                return false;
        return true;
    }

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

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

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

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

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

    private boolean useNextChunk() {
        if (rhsscan != null)
            rhsscan.close();
        if (nextblknum >= filesize)
            return false;

        int end = nextblknum + chunksize - 1;
        if (end >= filesize)
            end = filesize - 1;
        rhsscan = new ChunkScan(tx, filename, layout, nextblknum, end);
        lhsscan.beforeFirst();
        prodscan = new ProductScan(lhsscan, rhsscan);
        nextblknum = end + 1;
        return true;
    }
}

14.7 哈希连接 (Hash Joins)

第 13.6 节考察了 mergejoin 算法。因为该算法对两张输入表都排序，所以其成本由较大的输入表大小决定。本节考虑另一种连接算法，称为 hashjoin。该算法的特性是，其成本由较小的输入表大小决定。因此，当输入表大小差异很大时，该算法优于 mergejoin。

14.7.1 hashjoin 算法 (The Hashjoin Algorithm)

多缓冲乘积算法背后的想法可以扩展到计算两张表的连接。这个算法称为 hashjoin，见图 14.9。

hashjoin 算法是递归的，递归取决于 T2 的大小。如果 T2 足够小，可以放入可用缓冲区，那么算法使用多缓冲乘积连接 T1 和 T2。如果 T2 太大，无法放入内存，那么算法使用哈希来缩小 T2 的规模。它创建两组临时表：一组 {V0,...,Vk-1} 用于 T1，一组 {W0,...,Wk-1} 用于 T2。这些临时表作为哈希函数的桶。每条 T1 记录按其连接字段哈希，并放入与哈希值相关联的桶中。每条 T2 记录也以类似方式哈希。然后，对应表 (Vi, Wi) 递归连接。

显然，所有具有相同连接值的记录都会哈希到同一个桶。因此，可以通过对每个 i 独立连接 Vi 和 Wi 来执行 T1 与 T2 的连接。由于每个 Wi 都小于 T2，递归最终会停止。

注意，每次递归调用 hashjoin 算法都必须使用不同的哈希函数。原因是，临时表中的所有记录之所以在那里，是因为它们都哈希到了相同的值。不同的哈希函数可以确保这些记录在新的临时表之间均匀分布。

图 14.9 的代码还说，每次递归调用都要重新选择 k 值。也可以只选择一次 k，并在所有调用中使用它。练习 14.11 要求你考虑这两个选项的权衡。

还可以通过谨慎搜索块中的匹配记录，稍微提高多缓冲乘积的效率。给定 T1 中的一条记录，算法需要找到 T2 中的匹配记录。多缓冲乘积采用的策略是简单搜索整个 T2。虽然这种搜索不会产生额外磁盘访问，但它当然可以通过合适的内部数据结构变得更高效。例如，可以把对 T2 记录的引用存储在哈希表或二叉搜索树中。（事实上，Java Map 接口的任意实现都可以工作。）给定一条 T1 记录，算法会在数据结构中查找其连接值，并找到具有该连接值的 T2 记录引用，从而避免搜索 T2。

图 14.9 hashjoin 算法 (The hashjoin algorithm)

设 T1 和 T2 为要连接的表。

1. 选择一个小于可用缓冲区数量的 k 值。
2. 如果 T2 的大小不超过 k 块，则：
   a. 使用多缓冲乘积后接连接谓词上的选择，连接 T1 和 T2。
   b. 返回。

// 否则：
3. 选择一个哈希函数，其返回值位于 0 到 k-1 之间。
4. 对表 T1：
   a. 为 k 个临时表打开扫描。
   b. 对 T1 中的每条记录：
      i. 对记录的连接字段哈希，得到哈希值 h。
      ii. 把记录复制到第 h 个临时表。
   c. 关闭临时表扫描。
5. 对表 T2 重复第 4 步。
6. 对 0 到 k-1 之间的每个 i：
   a. 令 Vi 为 T1 的第 i 个临时表。
   b. 令 Wi 为 T2 的第 i 个临时表。
   c. 递归执行 Vi 和 Wi 的 hashjoin。

14.7.2 hashjoin 示例 (An Example of Hashjoin)

作为具体例子，使用 hashjoin 实现 ENROLL 和 STUDENT 表的连接，使用图 1.1 中的记录。做如下假设：

• STUDENT 表位于连接右侧。
• 两条 STUDENT 记录可放入一个块，两条 ENROLL 记录可放入一个块。
• 使用三个桶；也就是说，k = 3。
• 哈希函数为 h(n) = n % 3。

九条 STUDENT 记录装入五个块。由于 k = 3，STUDENT 记录无法一次全部装入内存，因此需要哈希。得到的桶见图 14.10。

图 14.10 使用 hashjoin 连接 ENROLL 和 STUDENT (Using hashjoin to join ENROLL with STUDENT)

桶	ENROLL 临时表	STUDENT 临时表
V0 / W0	(64, 6, 53, A)	(3, max, 2022, 10), (6, kim, 2020, 20), (9, lee, 2021, 10)
V1 / W1	(14, 1, 13, A), (24, 1, 43, C), (44, 4, 33, B), (54, 4, 53, A)	(1, joe, 2021, 10), (4, sue, 2022, 20), (7, art, 2021, 30)
V2 / W2	(34, 2, 43, B+)	(2, amy, 2020, 20), (5, bob, 2020, 30), (8, pat, 2019, 20)

学生 ID 值 3、6 和 9 的哈希值为 0。因此，这些学生的 ENROLL 记录被放入 V0，这些学生的 STUDENT 记录被放入 W0。类似地，学生 1、4 和 7 的记录被放入 V1 和 W1，学生 2、5 和 8 的记录被放入 V2 和 W2。现在可以递归连接每个 Vi 表及其对应的 Wi 表。

由于每个 Wi 表都有两个块，它们各自都能放入内存；因此，这三个递归连接都可以作为多缓冲乘积执行。特别是，通过把所有 Wi 读入内存来连接 Vi 和 Wi。然后扫描 Vi；对于每条记录，在 Wi 中搜索任何匹配记录。

14.7.3 成本分析 (Cost Analysis)

为了分析使用 hashjoin 连接 T1 和 T2 的成本，假设 T1 中物化记录需要 B1 块，T2 中记录需要 B2 块。选择 k 为 B2 的 n 次根；也就是说，B2 = k^n。然后假设记录均匀哈希，可以如下计算成本。

第一轮哈希会产生 k 个临时表；T2 的每个表会有 k^(n-1) 块。当递归哈希这些临时表时，会剩下 k^2 个临时表，其中每个有 k^(n-2) 块。继续下去，T2 最终会得到 k^(n-1) 个临时表，每个有 k 块。这些表随后可以使用多缓冲乘积与来自 T1 的对应表连接。

因此，会有 n-1 轮哈希。第一轮成本为 B1 + B2，再加上读取输入的成本。在后续轮次中，每个临时表的每个块都会读一次、写一次；因此这些轮次的成本为 2(B1 + B2)。多缓冲乘积发生在扫描阶段。临时表中的每个块都会读一次，成本为 B1 + B2。

把这些值组合起来可知，使用 k 个缓冲区对大小为 B1 和 B2 的表执行 hashjoin，具有以下成本：

• 预处理成本 = (2B1 log_k B2 - 3B1) + (2B2 log_k B2 - 3B2) + 输入成本
• 扫描成本 = B1 + B2

令人惊讶的是，这个成本几乎与多缓冲 mergejoin 的成本相同！有一个差异：在这个公式中，两个对数的参数都是 B2；而在 mergejoin 的公式中，第一个对数的参数是 B1。这个差异的原因是，在 hashjoin 中，哈希轮数只由 T2 决定；而在 mergejoin 中，排序阶段的 merge 迭代次数由 T1 和 T2 共同决定。

这个差异解释了两个连接算法性能的不同。mergejoin 算法必须先排序两张输入表，然后才能合并。另一方面，hashjoin 算法不关心 T1 有多大；它只需要一直哈希到 T2 的桶足够小。mergejoin 的成本不受哪张表位于左侧或右侧影响。然而，当较小表位于右侧时，hashjoin 更高效。

如果 T1 和 T2 大小接近，那么使用 mergejoin 可能更好，尽管 hashjoin 具有相同的成本公式。原因是 hashjoin 公式依赖于记录会均匀哈希这一假设。但如果哈希结果不均匀，算法可能需要比公式所说更多的缓冲区和更多迭代。相反，mergejoin 的行为更可预测。

14.8 连接算法比较 (Comparing the Join Algorithms)

本章考察了两种实现两张表连接的方式：mergejoin 和 hashjoin，第 12 章考察了 indexjoin。本节使用如下连接查询来研究这三种实现的相对收益：

select SName, Grade from STUDENT, ENROLL where SId=StudentId

假设各表大小如图 7.8 所示，有 200 个缓冲区可用，并且 ENROLL 在 StudentId 上有索引。

先考虑 mergejoin 算法。该算法需要先排序 ENROLL 和 STUDENT，再合并它们。ENROLL 表有 50,000 块。50,000 的平方根是 244，大于可用缓冲区数量。因此必须分配立方根，也就是 37 个缓冲区。split 阶段会创建 1352 个 run，每个 run 有 37 块。一次 merge 迭代会产生 37 个大小为 1352 块的 run。因此，预处理 ENROLL 表需要对记录读两次、写两次，总共 200,000 次块访问。STUDENT 表有 4500 块。4500 的平方根是 68，且有 68 个缓冲区可用。因此可以使用 68 个缓冲区，把 4500 个 STUDENT 块拆分成 68 个大小为 68 的 run。这个拆分需要 9000 次块访问，并且已经完成所需的全部预处理。合并两张排序表还需要 54,500 次块访问，总成本为 263,500 次块访问。

现在考虑 hashjoin 算法。当最小表位于右侧时，该算法最高效；因此 ENROLL 是左侧表，STUDENT 是右侧表。可以使用 68 个缓冲区把 STUDENT 哈希成 68 个桶，每个桶约 68 块。类似地，可以使用同样的 68 个缓冲区把 ENROLL 哈希成 68 个桶，每个桶约 736 块。然后递归连接对应桶。这些子连接中的每一个都可以使用多缓冲乘积执行。也就是说，分配 68 个缓冲区容纳整个 STUDENT 桶，并为 ENROLL 桶的顺序扫描再分配一个缓冲区。每个桶扫描一次。把成本相加，ENROLL 和 STUDENT 记录被读取一次，桶被写入一次并读取一次，总共 163,500 次块访问。

indexjoin 实现会扫描 STUDENT 表；对于每条 STUDENT 记录，它使用记录的 SId 值搜索索引，并查找匹配的 ENROLL 记录。因此，STUDENT 表会访问一次（4500 次块访问），ENROLL 表会针对每条匹配记录访问一次。然而，由于每条 ENROLL 记录都匹配某条 STUDENT 记录，ENROLL 表可能需要 1,500,000 次块访问。因此该查询需要 1,504,500 次块访问。

这个分析表明，在这些假设下，hashjoin 最快，其次是 mergejoin，最后是 indexjoin。hashjoin 如此高效的原因是，其中一张表（即 STUDENT）相对于可用缓冲区数量来说足够小，而另一张表（即 ENROLL）大得多。假设有 1000 个缓冲区可用。那么 mergejoin 将能够在没有任何 merge 迭代的情况下排序 ENROLL，总成本为 163,500 次块访问，与 hashjoin 相同。对于这个查询，indexjoin 算法远远是最低效的实现。原因是，当有许多匹配数据记录时，索引没有用；而在这个查询中，每条 ENROLL 记录都有匹配。

现在考虑该查询的一个变体，它在 GradYear 上有额外选择：

select SName, Grade from STUDENT, ENROLL
where SId=StudentId and GradYear=2020

先考虑 mergejoin 实现。相关的 STUDENT 记录只有 900 条，能装入 90 个块。因此，可以把 STUDENT 记录读入 90 个缓冲区，并使用内部排序算法对其排序。于是只需要 4500 次块访问。但处理 ENROLL 的成本不变，因此该查询总共需要 204,500 次块访问，只比原查询上的 mergejoin 略有改进。

hashjoin 实现会认识到 90 块 STUDENT 记录可以直接放入 90 个缓冲区，而不需要哈希。因此，该连接可以通过对两张表各扫描一次来执行，即 54,500 次块访问。

indexjoin 实现会读取全部 4500 个 STUDENT 记录，以找到 2020 届的 900 名学生。这些记录会匹配 ENROLL 记录的 1/50（即 50,000 条），导致对 ENROLL 大约 50,000 次块访问，总共 54,500 次块访问。

因此，hashjoin 和 indexjoin 相当，而 mergejoin 明显更差。原因是 mergejoin 被迫预处理两张表，即使其中一张表小得多。

作为最后一个例子，修改上面的查询，使其在 STUDENT 上有更严格的选择：

select SName, Grade from STUDENT, ENROLL
where SId=StudentId and SId=3

现在输出表由这名学生的 34 条选课记录组成。在这种情况下，indexjoin 最高效。它扫描整个 4500 块的 STUDENT，遍历索引，并查找 34 条 ENROLL 记录，总共约 4534 次块访问（不计算索引遍历成本）。

hashjoin 实现与之前成本相同。它需要扫描 STUDENT 一次（物化单条记录），并扫描 ENROLL 一次（找到所有匹配记录），总共 54,500 次块访问。mergejoin 必须像之前一样预处理 ENROLL 和 STUDENT，总共 204,500 次块访问。

这个分析说明，当两张输入表大小相对接近时，mergejoin 最高效。当输入表大小差异很大时，hashjoin 往往更好。当输出记录数较少时，indexjoin 更好。

14.9 本章小结 (Chapter Summary)

• 非物化扫描在缓冲区使用方面非常节俭。特别是：
  • 表扫描恰好使用一个缓冲区。
  • select、project 和 product 的扫描不使用额外缓冲区。
  • 静态哈希索引或 B 树索引需要一个额外缓冲区（用于查询）。
• 归并排序算法在创建初始 run 和合并 run 时都可以利用多个缓冲区。它选择 k = nroot(B)，其中 B 是输入表大小，n 是使 k 小于可用缓冲区数量的最小整数。所得算法称为多缓冲归并排序，过程如下：
  • 从缓冲区管理器分配 k 个缓冲区。
  • 一次把表中的 k 块读入 k 个缓冲区，并使用内部排序算法把它们排序成一个 k 块 run。
  • 使用 k 个临时表对所得 run 执行 merge 迭代，直到剩余 run 数不超过 k。由于 split 阶段产生 B/k 个 run，因此会有 n-2 次 merge 迭代。
  • 在扫描阶段合并最终的 k 个 run。
• 多缓冲乘积算法是 product 操作符的高效实现，工作方式如下：
  1. 把 RHS 表物化为临时表 T2。令 B2 为 T2 中的块数。
  2. 令 i 为最小的数，使 B2/i 小于可用缓冲区数量。
  3. 把 T2 视为 i 个 chunk，每个 chunk 有 k 块。对于每个 chunk C： (a) 把 C 的所有块读入 k 个缓冲区。 (b) 计算 T1 与 C 的乘积。 (c) unpin C 的块。 也就是说，T1 的块会针对每个 chunk 读取一次。因此，乘积中的块访问数量为 B2 + B1 * B2 / k。
• 不是所有缓冲区分配都有用。多缓冲归并排序只能使用表大小的某个根作为缓冲区分配。多缓冲乘积只能使用右侧表大小的某个因子作为分配。
• hashjoin 算法是多缓冲乘积的扩展，工作方式如下：
  1. 选择一个小于可用缓冲区数量的 k 值。
  2. 如果 T2 能放入 k 个缓冲区，则使用多缓冲乘积连接 T1 和 T2。
  3. 否则，哈希 T1 和 T2，各使用 k 个临时表。
  4. 对对应的哈希桶递归执行 hashjoin。

14.10 建议阅读 (Suggested Reading)

Shapiro (1986) 一文描述并分析了多种连接算法及其缓冲区需求。Yu 和 Cornell (1993) 一文考虑缓冲区使用的成本效益。它认为缓冲区是一种有价值的全局资源，查询不应尽可能多地分配缓冲区（SimpleDB 正是如此），而应分配对整个系统最具成本效益的缓冲区数量。该文给出了一个可用于确定最优缓冲区分配的算法。

• Shapiro, L. (1986) Join processing in database systems with large main memories. ACM Transactions on Database Systems, 11(3), 239-264.
• Yu, P., & Cornell, D. (1993) Buffer management based on return on consumption in a multi-query environment. VLDB Journal, 2(1), 1-37.

14.11 习题 (Exercises)

概念性练习 (Conceptual Exercises)

14.1. 假设数据库系统包含如此多的缓冲区，以至于它们永远不会同时全部被 pin。这只是浪费物理内存，还是拥有过量缓冲区也有优势？

14.2. 大量 RAM 正变得越来越便宜。假设数据库系统拥有的缓冲区数量多于数据库中的块数。所有缓冲区都能被有效使用吗？

14.3. 假设数据库系统包含足够多的缓冲区，可以容纳数据库中的每个块。这样的系统称为主存数据库系统，因为它可以把整个数据库一次读入缓冲区，然后执行查询时不再产生任何额外块访问。

(a) 在这种情况下，数据库系统的某些组件是否变得不必要？

(b) 某些组件的功能是否应显著不同？

(c) 查询计划估算函数当然需要改变，因为再用块访问次数评估查询已经没有意义。提出一个更好的函数，更准确地建模查询求值成本。

14.4. 考虑第 14.5 节中对多缓冲排序的描述，其中建议 splitIntoRuns 和 doAMergeIteration 方法各自确定要分配多少缓冲区。

(a) 另一种选项是让 open 方法确定 numbuffs 的值，并将其传给两个方法。解释为什么这是较不理想的选项。

(b) 还有一种选项是在 SortPlan 构造函数中分配缓冲区。解释为什么这是更糟糕的选项。

14.5. 假设 SortPlan 类已经修改为实现图 14.2 的多缓冲排序算法，并考虑第 14.6 节中的第一个 mergejoin 示例。

(a) 该 mergejoin 扫描的扫描阶段使用多少缓冲区？

(b) 假设只有 100 个缓冲区可用（而不是 200 个）。假设先为 ENROLL 分配缓冲区，再为 STUDENT 分配。它们将如何分配？

(c) 假设只有 100 个缓冲区可用（而不是 200 个）。假设先为 STUDENT 分配缓冲区，再为 ENROLL 分配。它们将如何分配？

(d) 另一个选项是在连接之前完全物化其中一张排序表。计算这个选项的成本。

14.6. 考虑以下实现 groupby 操作符的算法：

1. 创建并打开 k 个临时表。
2. 对每条输入记录：
   (a) 按分组字段对记录哈希。
   (b) 把记录复制到对应临时表。
3. 关闭临时表。
4. 对每个临时表：
   在该表上执行基于排序的 groupby 算法。

(a) 解释为什么该算法有效。

(b) 计算该算法的预处理成本和扫描成本。

(c) 解释为什么该算法通常不如图 13.14 中基于排序的 groupby 算法。

(d) 解释为什么该算法在并行处理环境中可能有用。

14.7. 考虑第 14.3 节中的多缓冲乘积示例，它对两个 1000 块表取乘积。假设表 T2 只有一个缓冲区可用，也就是说 k = 1。

(a) 计算取乘积所需的块访问次数。

(b) 尽管它使用了与第 8 章基础乘积算法相同数量的缓冲区，这个数量仍显著少于基础乘积算法所需块访问。解释原因。

14.8. 多缓冲乘积算法要求 RHS 表被物化（这样才能 chunk）。然而，MultibufferProductPlan 代码也会物化 LHS 扫描。不物化左侧可能导致缓冲区使用和效率方面的问题。解释原因，并分别给出一个示例。

14.9. 重写图 14.9 的 hashjoin 算法，使其成为非递归算法。确保所有哈希都在预处理阶段执行，合并在扫描阶段执行。

14.10. 图 14.9 的 hashjoin 算法使用相同的 k 值对 T1 和 T2 的记录进行哈希。解释为什么使用不同的 k 值不可行。

14.11. 图 14.9 的 hashjoin 算法每次调用时都会重新选择 k 值。

(a) 解释为什么也可以只选择一次 k 值，并把它传入每个递归调用。

(b) 分析这两种可能性的权衡。你更喜欢哪一种？

14.12. 假设你修改图 14.9 的 hashjoin 算法，使第 6 步使用 mergejoin 连接各个桶，而不是递归调用 hashjoin。给出该算法的成本分析，并将块访问次数与原始 hashjoin 算法比较。

14.13. 假设 STUDENT 表在 SId 和 MajorId 上有索引。对于以下每个 SQL 查询，使用图 7.8 的统计数据计算使用 mergejoin、hashjoin 或 indexjoin 的实现成本。

(a)

select SName, DName from STUDENT, DEPT
where MajorId=DId

(b)

select SName, DName from STUDENT, DEPT
where MajorId=DId and GradYear=2020

(c)

select DName from STUDENT, DEPT
where MajorId=DId and SId=1

(d)

select SName from STUDENT, ENROLL
where SId=StudentId and Grade='F'

编程练习 (Programming Exercises)

14.14. SimpleDB 的 BufferNeeds 类不会从缓冲区管理器保留缓冲区。

(a) 列出一些 SimpleDB 中可能发生、且如果缓冲区真的被保留就能缓解的问题。不保留缓冲区是否也有优势？

(b) 重新设计 SimpleDB 缓冲区管理器，使其允许事务保留缓冲区。（务必考虑这种情况：事务 T1 把块 b pin 到一个保留缓冲区，然后事务 T2 想 pin b。你应该怎么办？）

(c) 实现你的设计，并相应修改 BufferNeeds。

14.15. 在练习 13.10 中，你修改了 SortPlan 类，使其构造长度为一块的初始 run。修改代码，使其构造长度为 k 块的初始 run，如第 14.5 节所述。

14.16. 在练习 13.11 中，你修改了 SortPlan 类，使其使用一块长的暂存区来计算初始 run。修改代码，使其使用 k 块长的暂存区。

14.17. 在练习 13.13 中，你修改了 SortPlan 类，使其一次合并 k 个 run，其中 k 的值传给构造函数。修改代码，使 k 值由初始 run 数量决定，如第 14.5 节所述。

14.18. 当最小输入表位于右侧时，多缓冲乘积算法通常最高效。

(a) 解释原因。

(b) 修改 MultiBufferProductPlan 代码，使其总是选择较小的输入表位于扫描右侧。

14.19. 修改 MultiBufferProductPlan 代码，使其只在必要时物化左侧和右侧表。

14.20. 编写 SimpleDB 代码来实现 hashjoin 算法。