MIT 6.830 数据库实验 Lab 3 实验报告

发表于 更新于 分类于 ， 阅读次数： 本文字数： 3.2k 阅读时长 ≈ 6 分钟

摘要

Lab 3 要实现的是查询优化模块。在数据库中，查询优化主要在查询被解析为抽象语法树后被调用，用于为指定的查询找到 “最优的” 执行计划。在 SimpleDb 中，这部分定义在 Optimizer 模块中，主要对联合操作进行优化。

理论知识

查询优化模块的作用是为指定的查询找到高效的执行方案。由于 SQL 是声明式语言，查询只声明了想要的结果，并没有规定执行的具体方案。这些结果等价的方案存在于一个计划空间中，包含物理上等价或者关系代数等价的方案。

  • 物理等价是指操作的不同物理实现，比如 Join 是使用嵌套循环、Sort-Merge 还是其他，Scan 是使用 Heap Scan 还是 Index Scan，等等。
  • 关系代数等价是指，关系代数上等价的关系。例如一些操作的顺序是可交换的（例如 projection），多种同种操作是可串联的（例如 filter），等等。

查询优化的终极目的，是在这个庞大的空间中找到实际上 “最优的” 方案，它使用以下子模块来完成：

  • 计划生成器：生成新的、结果等价的计划
  • 成本估计器：估计一个计划的成本，包含 IO 和 CPU，其中 IO 占主要部分
  • 搜索策略：如何在计划空间中行走，常使用动态规划策略

为了对搜索空间进行剪枝，查询优化的开山之作，System R 提出只考虑左深树，即执行树只有左侧是深的。这种树可以较好地流水线化。值得注意的是，由于各种原因，查询优化实际上经常找不到最优的实际执行方案，例如，成本估计器的误差，成本估计器基于选择度去计算操作前后的表规模，进而估算 IO 和 CPU cost，每一步都会有误差。因此，实际上，查询优化器是去除一些看起来特别差的执行计划，与理想最优还有差距。

查询优化经常遵循一些启发式的策略，例如：

  • 尽早完成列和行的筛选，减小数据规模
  • 避免表间的笛卡尔积
  • ... 等等

Exercise

IntHistogram

Histogram，即直方图，用于记录字段的统计信息，即字段值的分布，进而用于估计不同操作的选择度。这在成本估计器中会用到。这类直方图在构建时常用若干个等宽的桶，对应值区间，然后在这些桶间构建分布。IntHistogram 是对整型字段进行统计的类，它的构造函数如下：

1
2
3
public IntHistogram(int buckets, int min, int max) {
    // some code goes here
}

即根据桶的数量、最小值、最大值初始化一个直方图，然后通过 addValue 方法逐个将值加入，最后通过 estimateSelectivity 等方法，估计操作符的选择度。实现逻辑就是将值域等距地划分为指定数量的桶，在添加值时对应桶计数 + 1,。在估计选择度时，要按照两步走的方法，例如 <=，先估计 < 的比率，在桶内再根据均匀分布，估计 = 的比率，求和即可。

值得注意的是，StringHistogram 是通过将字符串映射到整型，再通过 IntHistogram 实现的。但是这两个类并没有实现同样的接口，这给后面带来了麻烦。

TableStats

TableStats 记录了整张表的统计信息，包含每个字段的直方图，以及表的基数。正常应该是保存一个 List<Histogram>，用于保存每个字段的直方图。但并没有 Histogram 这样的接口，而重构代码还需要去修改测试代码，也并不是一种好的做法。我这里使用了一个 List<Object> 加强制类型转换完成，也不是一种值得提倡的做法。不过可以先达到效果。

在确定了如何保存直方图，还有一个问题是如何获得字段的最大最小值。因为直方图的构建需要指定最大最小值，之后才能一个个地添加值。这个过程不是一次遍历能够完成的。因此，需要先遍历一次，记录每个字段的最大最小值，构建直方图，再遍历一次逐个添加值。

Join Cardinality

这个 exercise 要求去根据公式估计 join 操作结果的基数和操作成本。操作成本非常简单，根据在 Lab 2 中实现的 Join 策略计算即可。我 Lab 2 是使用的粗暴的嵌套循环的方法，将 IO 成本与 CPU 计算成本相加即可。join 操作的基数则相对难以估计。如果是 equijoin 且某侧字段为主键，那么基数一定不会超过另一张表的基数。这很容易理解，因为左侧主键是不重复的，右侧表中与主键相同的记录可以保留，其他则不会。如果不存在这样的条件，就需要一些策略去估计了：

  • 简单启发估计：如果是 equijoin，可以使用较大表的基数作为估计。如果是 range-join，可以按照一定的比例 * 笛卡尔积的基数，作为估计。
  • 基于直方图：要获得准确一点的结果，需要根据两侧的直方图进行估计。例如 equijoin，对于每一个值，去估计在另一个直方图中的数量，然后两个数量相乘最后求和即可。range-join 则要在前一步的基础上，考虑两侧的比率。

Join Ordering

最后一个 Exercise 要求实现找出多个 join 的最优执行方案。Join 操作的被封装在了 LogicalJoinNode 这个类中，包含 Join 的信息，例如两侧表、别名、Join 条件等。目标就是接收一个 List<LogicalJoinNode> 作为输入，找到最优的左深树联合顺序 List<LogicalJoinNode>。伪代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
1. j = set of join nodes
2. for (i in 1...|j|):
3.     for s in {all length i subsets of j}
4.       bestPlan = {}
5.       for s' in {all length d-1 subsets of s}
6.            subplan = optjoin(s')
7.            plan = best way to join (s-s') to subplan
8.            if (cost(plan) < cost(bestPlan))
9.               bestPlan = plan
10.      optjoin(s) = bestPlan
11. return optjoin(j)

遵循动态规划的思想，按照规模从小到大的顺序建动态规划表。对于给定的规模 i，需要枚举所有该规模的子集，根据小规模的最优结果计算该子集的最优结果。这个伪代码看起来很简单，但是有以下几个难点：

  • 如何枚举指定规模的所有子集
  • 如何计算指定 join 顺序的成本，如果子集的最优 join 顺序不支持新元素插入在最后面怎么办

实验中给定了一些辅助方法，帮助我们解决了这些问题，虽然并不优雅：

  • enumerateSubsets 方法从规模为 1 开始，构建规模为 iS 支持，则直接跳过

其中，enumerateSubsets 是一种非常低效的枚举策略，一次性地创建规模为 i 的 Set，会有较大的内存开销。正常的策略是遵循迭代器的模式，每次返回一个新的子集。join 顺序不支持直接跳过也是一种妥协，在动态规划的设定下。

这个 Exercise 就是在上面辅助函数的帮助下，实现上述伪代码。这里我写了一个迭代器类，替代一次返回所有结果的枚举函数。这个枚举函数实际上是在计算组合方案，相对容易改造成迭代器，维护多个指针，然后每次获取新元素时更新指针位置即可。如果是要计算排列方案的话，就要用那个基于左右箭头的算法了。

总结

查询优化这个 Lab 本身难度不大，属于麻雀虽小五脏俱全。对于成本估计、方案生成、动态规划每部分都涉及到了，但都不深。查询优化的理论知识要更为复杂，只是获得一个搜索空间就要考虑各种关系代数的等价性、Join 交换时的条件问题等等。对于非左深树，这个空间会更大，剪枝和搜索也会更难。动态规划搜索理论上还要考虑每种方案的物理执行类型，是否有可用的排序结果等等。真正完成这些实践就属于重复造轮子了，过于复杂且没有必要。