SimpleDB-Lab3

0.实验介绍

在这个实验中，你将在SimpleDB之上实现一个查询优化器。主要任务包括实现一个选择性估计框架和一个基于成本的优化器。你可以自由选择具体的实现方式，但我们建议使用类似于课堂上讨论的Selinger基于成本的优化器（第9讲）。

• 实现TableStats类中的方法，使其能够使用直方图（IntHistogram类提供的骨架）或你设计的其他形式的统计数据来估计过滤器的选择性和扫描的成本。
• 实现JoinOptimizer类中的方法，使其能够估计 join 的成本和选择性。
• 编写JoinOptimizer中的orderJoins方法。这个方法必须为一系列的连接产生一个最佳的顺序（可能使用Selinger算法），给定前两个步骤中计算的统计数据。

Optimizer outline

• 基于成本的优化器的主要思想是：使用关于表的统计数据来估计不同查询计划的 “成本”。通常情况下，一个计划的成本与中间连接和选择的cardinalities（产生的 tuple 数量），以及过滤器和连接谓词的选择性有关。

• 利用这些统计数据，以最佳方式排列连接和选择，并从几个备选方案中选择连接算法的最佳实现。 在本实室中，你将实现代码以执行这两项功能。

• 优化器将从simpledb/Parser.java调用。在开始这个实验之前，你可能希望回顾一下实验2的解析器练习。简而言之，如果你有一个描述你的表的目录文件catalog.txt，你可以通过输入java -jar dist/simpledb.jar parser catalog.txt来运行解析器。

• 当解析器被调用时，它将对所有的表进行统计计算（使用你提供的统计代码）。当一个查询被发出时，解析器将把查询转换成逻辑计划表示，然后调用你的查询优化器来生成一个最佳计划。

• SimpleDB优化器的整体结构。分析器和优化器的SimpleDB模块的整体控制流程如图1所示。

• 需要实现带有双边框的组件。这些类和方法将在后面的文字中得到更详细的解释（你可能希望回过头来看看这个图），但基本操作如下：

• Parser.java在初始化时构建了一组表的统计数据（存储在statsMap容器中）。然后它等待一个查询的输入，并对该查询调用parseQuery方法。

• parseQuery首先构建一个代表解析查询的LogicalPlan，然后在它构建的LogicalPlan实例上调用physicalPlan方法。physicalPlan方法返回一个DBIterator对象，可用于实际运行查询。

• 在接下来的exercise中，你将实现帮助物理计划（physicalPlan）设计出最优计划的方法。

• 成本估计。准确地估计计划成本是相当棘手的。在这个Lab中，我们将只关注连接序列和基本表访问的成本。我们不会担心访问方法的选择（因为我们只有一种访问方法，即表扫描），也不会担心额外运算符（如聚合）的成本。在这个Lab中，你只需要考虑left-deep的计划。接下来会了解你可能实现的额外的 “奖励 “优化器特性，包括处理杂乱计划的方法。

• 我们将以p=t1 join t2 join … tn的形式来写连接计划，这表示一个左深连接，其中t1是最左边的连接（树中最深的）。给定一个像p这样的计划，其成本可以表示为：

scancost(t1) + scancost(t2) + joincost(t1 join t2) +
scancost(t3) + joincost((t1 join t2) join t3) +
... 

• 这里，scancost(t1)是扫描表t1的I/O成本，joincost(t1,t2)是连接t1和t2的CPU成本。为了使I/O和CPU成本具有可比性，通常使用一个恒定的比例系数，例如：

cost(predicate application) = 1
cost(pageScan) = SCALING_FACTOR x cost(predicate application)

• 在这个实验中，你可以忽略缓存的影响（例如，假设对表的每一次访问都会产生全部的扫描成本）–同样，这也是你可以作为一个可选的额外扩展添加到实验中的东西。因此，scancost(t1)只是t1的页数x SCALING_FACTOR。

• 当使用嵌套循环连接时，记得两个表t1和t2（其中t1是外表）之间的连接成本是简单的。

joincost(t1 join t2) = scancost(t1) + ntups(t1) x scancost(t2) //IO cost
                    + ntups(t1) x ntups(t2)  //CPU cost

• 此处，ntups(t1)是表t1中 tuples 的数量。

• ntups可以通过扫描一个基表直接计算出来。对于一个有一个或多个选择谓词的表来说，估计ntups可能比较棘手–这就是过滤器的选择性估计问题。下面是你可能使用的一种方法，基于计算表中的值的直方图。

• 计算表中每个属性的最小值和最大值（通过扫描一次）。

• 为表中的每个属性构建一个直方图。一个简单的方法是使用一个固定数量的桶NumB，每个桶代表直方图属性领域的固定范围内的记录数。例如，如果一个字段f的范围是1到100，有10个桶，那么桶1可能包含1到10之间的记录数，桶2包含11到20之间的记录数，以此类推。

• 再次扫描该表，选择出所有 tuples 的所有字段，用它们来填充每个直方图中的桶的计数。

• 为了估计一个平等表达式f=const的选择性，计算包含值const的桶。假设桶的宽度（值的范围）是w，高度（ tuples 的数量）是h，而表中 tuples 的数量是ntups。那么，假设值在整个桶中是均匀分布的，表达式的选择性大致为(h/w)/ntups，因为(h/w)代表的是桶中含有值常数的 tuples 的预期数量。

• 为了估计一个范围表达式f>const的选择性，计算const所在的桶b，其宽度为w_b，高度为h_b。那么，b包含了全部 tuples 中的一部分b_f = h_b / ntups。假设 tuples 均匀地分布在整个b中，b中大于const的部分b_part是（b_right - const）/ w_b，其中b_right是b的桶的右端点。因此，b桶对谓词贡献了（b_f x b_part）的选择性。此外，b+1…NumB-1桶贡献了它们所有的选择性（可以用类似于上面b_f的公式来计算）。将所有桶的选择性贡献相加，将产生表达式的整体选择性。图2说明了这个过程。

• 涉及小于的表达式的选择性可以类似于大于的情况下进行，看下到0的桶。

• 在接下来的两个练习中，你将用代码来执行连接和过滤器的选择性估计。

1. IntHistogram.java

a. 要修改的文件

• src/java/simpledb/optimizer/IntHistogram.java

b. 实现说明

• 你将需要实现一些方法来记录表的统计数据，以便进行选择性估计。我们提供了一个骨架类，IntHistogram，它可以做到这一点。我们的目的是让你使用上面描述的基于桶的方法来计算直方图，但你也可以自由地使用其他方法，只要它能提供合理的选择性估计。
• 我们提供了一个StringHistogram类，它使用IntHistogram来计算字符串谓词的选取。如果你想实现一个更好的估计器，你可以修改StringHistogram，尽管你不需要为了完成这个实验而修改。

c. 实现目标

• 通过单元测试 IntHistogramTest（如果你选择不实现基于直方图的选择性估计，你不需要通过这个测试）

d. 实现说明

• 基本按照讲解实现。除了用List保存直方图外，还保存了min_value， max_value、bucket_width和num_tuples，用于计算。

• 当加入或估计的值在min_value和max_value范围之外时，单独进行判断。

2. TableStats.java

a. 要修改的文件

• src/java/simpledb/optimizer/TableStats.java

b. 实现说明

• TableStats类包含了计算一个表中 tuples 和页数的方法，以及估计该表字段上的谓词的选择性的方法。我们创建的查询分析器为每个表创建一个TableStats的实例，并将这些结构传递给你的查询优化器（在后面的练习中你会需要它）。

• 你应该在TableStats中填写以下方法和类：

• 实现TableStats构造函数。一旦你实现了跟踪统计的方法，如直方图，你应该实现TableStats构造函数，添加代码来扫描表（可能是多次）以建立你需要的统计。

• 实现 estimateSelectivity(int field, Predicate.Op op, Field constant)。使用你的统计数据（例如，根据字段的类型，使用IntHistogram或StringHistogram），估计predicate字段op常量对表的选择性。

• 实现 estimateScanCost()。这个方法估计顺序扫描文件的成本，考虑到读取一个页面的成本是costPerPageIO。你可以假设没有寻道，也没有页面在缓冲池中。这个方法可以使用你在构造函数中计算的成本或大小。

• 实现 estimateTableCardinality(double selectivityFactor)。该方法返回关系中 tuples 的数量，考虑到应用了具有选择性的selectivityFactor的谓词。这个方法可以使用你在构造函数中计算的成本或大小。

c. 实现目标

• 通过单元测试 TableStatsTest

d. 实现说明

• 基本参照说明实现。

• （from chatgpt）setStatsMap()使用反射机制的原因可能是为了绕过 statsMap 字段的访问权限，以便在类的内部方法中直接替换整个 statsMap 对象。通过反射，可以将私有字段的访问权限设置为可访问，然后使用 set() 方法来替换 statsMap 对象，而不是通过普通的字段访问操作符来逐个修改字段的值。

• TableStats构造函数：先扫描一遍所有tuple得到Field的最大最小值，根据最值创建直方图Histogram。再扫描第二遍，往Histogram中加入value，用于相应的估计。

• estimateScanCost()：page数量乘上每页的cost。

• estimateTableCardinality()：tuple数量乘上选择因子。

• avgSelectivity()：均值没有测试，因此不确定实现的正确性。

• estimateSelectivity()：根据构造函数创建的直方图，返回估计结果。

• 通过单元测试 TableStatsTest。

3. Join Cost Estimation

a. 要修改的文件

• src/java/simpledb/optimizer/JoinOptimizer.java

b. 实现说明

• 观察一下，上面的连接计划p的成本包括形式为joincost((t1 join t2) join t3)的表达。为了评估这个表达式，你需要一些方法来估计t1 join t2的大小（ntups）。这个连接cardinality估计问题比过滤器的选择性估计问题更难。在这个实验中，你不需要为此做任何花哨的事情，尽管第2.4节中的一个可选的练习包括一个基于直方图的连接选择性估计的方法。

• 在实施你的简单解决方案时，你应该牢记以下几点：

• 对于等价连接，当其中一个属性是主键时，由连接产生的 tuples 的数量不能大于非主键属性的cardinality。

• 对于没有主键的等价连接，很难说输出的大小是什么–它可能是表的cardinalities的乘积的大小（如果两个表的所有 tuples 都有相同的值）–或者它可能是0。

• 对于范围扫描，同样也很难对尺寸说得准确。输出的大小应该与输入的大小成正比。假设交叉产物的一个固定部分是由范围扫描发出的（比如，30%），是可以的。一般来说，范围连接的成本应该大于相同大小的两个表的非主键平等连接的成本。

• JoinOptimizer.java类包括所有用于排序和计算连接成本的方法。在这个练习中，你将写出用于估计 join 的 selectivity 和 cost 的方法，特别是：

• 实现 estimateJoinCost(LogicalJoinNode j, int card1, int card2, double cost1, double cost2) 。这个方法估计了连接j的成本，考虑到左边的输入是cardinality card1，右边的输入是cardinality card2，扫描左边输入的成本是cost1，访问右边输入的成本是card2。你可以假设这个连接是一个NL连接，并应用前面提到的公式。

• 实现 estimateJoinCardinality(LogicalJoinNode j, int card1, int card2, boolean t1pkey, boolean t2pkey) 。这个方法估计了j连接输出的 tuples 数，给定左边的输入是大小为card1，右边的输入是大小为card2，以及指示左边和右边（分别）字段是否唯一（主键）的标志t1pkey和t2pkey。

c. 实现目标

• 通过单元测试JoinOptimizerTest中的 estimateJoinCostTest 和 estimateJoinCardinality

d. 实现说明

• estimateJoinCost()通过公式计算连接的成本。其中，cost1为scancost(t1)，ntups(t1)为card1（表1中tuple与影响因子的乘积）

joincost(t1 join t2) = scancost(t1) + ntups(t1) x scancost(t2) //IO cost
                    + ntups(t1) x ntups(t2)  //CPU cost

• estimateJoinCardinality()看文档有点没明白具体实现的算法，参考MIT 6.830 数据库系统实现。
• 通过测试。

4. Join Cost Estimation

a. 要修改的文件

• src/java/simpledb/optimizer/JoinOptimizer.java

b. 实现说明

• 现在你已经实现了估计成本的方法，你将实现Selinger优化器。对于这些方法，连接被表达为一个连接节点的列表（例如，对两个表的谓词），而不是课堂上描述的连接关系的列表。将讲座中给出的算法转化为上述的连接节点列表形式，伪代码的概要是：

j = set of join nodes
for (i in 1...|j|):
    for s in {all length i subsets of j}
      bestPlan = {}
      for s' in {all length d-1 subsets of s}
           subplan = optjoin(s')
           plan = best way to join (s-s') to subplan
           if (cost(plan) < cost(bestPlan))
              bestPlan = plan
      optjoin(s) = bestPlan
 return optjoin(j)

• 为了帮助你实现这个算法，我们提供了几个类和方法来帮助你。

• 首先，JoinOptimizer.java中的enumerateSubsets(List v, int size)方法将返回一个大小为v的所有子集的集合。这个方法对于大型集合来说效率非常低；你可以通过实现一个更有效的枚举器来获得额外的分数（提示：考虑使用原地生成算法和懒惰迭代器（或流）接口来避免物化整个幂集）。

• 第二，我们提供了方法computeCostAndCardOfSubplan。

private CostCard computeCostAndCardOfSubplan(Map<String, TableStats> stats, 
                                                Map<String, Double> filterSelectivities, 
                                                LogicalJoinNode joinToRemove,  
                                                Set<LogicalJoinNode> joinSet,
                                                double bestCostSoFar,
                                                PlanCache pc)

• 给出一个连接的子集（joinSet），以及一个要从这个子集中移除的连接（joinToRemove），这个方法计算出将joinToRemove连接到joinSet-{joinToRemove}的最佳方法。它在一个CostCard对象中返回这个最佳方法，其中包括成本、cardinality和最佳连接顺序（作为一个列表）。如果找不到计划（因为，例如，没有可能的左深连接），或者如果所有计划的成本都大于bestCostSoFar参数，computeCostAndCardOfSubplan可能返回null。该方法使用了一个叫做pc（上面的psuedocode中的optjoin）的先前连接的缓存来快速查找joinSet的最快方式–{joinToRemove}。其他参数（stats和filterSelectivities）被传递到你必须实现的orderJoins方法中，作为练习4的一部分，下面会有解释。这个方法基本上是执行前面描述的假代码的第6-8行。

• 第三，我们提供了方法printJoins。

private void printJoins(List<LogicalJoinNode> js, 
                           PlanCache pc,
                           Map<String, TableStats> stats,
                           Map<String, Double> selectivities)

• 这种方法可以用来显示连接计划的图形表示（例如，当通过优化器的”-explain “选项设置 “explain “标志时）。

• 第四，我们提供了一个PlanCache类，可以用来缓存到目前为止在你的Selinger实现中所考虑的连接子集的最佳方式（使用computeCostAndCardOfSubplan需要这个类的一个实例）。

• 在JoinOptimizer.java中，实现方法orderJoins。

List<LogicalJoinNode> orderJoins(Map<String, TableStats> stats, 
                   Map<String, Double> filterSelectivities,  
                   boolean explain)

• 这个方法应该在joins类成员上操作，返回一个新的List，这个List指定了应该进行的连接的顺序。这个列表中的第0项表示左深计划中最左、最底的连接。返回的列表中相邻的连接应该至少共享一个字段，以确保计划是左深的。这里stats是一个对象，让你找到出现在查询的FROM列表中的给定表名的TableStats。 filterSelectivities让你找到表的任何谓词的选择性；它保证在FROM列表中的每个表名有一个条目。最后，explain指定了你应该输出一个连接顺序的表示，以供参考。
• 你可能希望使用上面描述的辅助方法和类来帮助你实现。大致上，你的实现应该遵循上面的假设代码，通过子集大小、子集和子集的子计划进行循环，调用computeCostAndCardOfSubplan并建立一个PlanCache对象来存储执行每个子集连接的最小成本方式。

c. 实现目标

• 通过单元测试 JoinOptimizerTest
• 通过系统测试 QueryTest

5. *Bonus Exercises

a. 添加代码以执行更高级的连接心率估计

• 与其使用简单的启发式方法来估计连接的cardinality，不如设计一个更复杂的算法。
• 一种选择是在每对表t1和t2中的每对属性a和b之间使用联合直方图。这个想法是创建a的桶，对于a的每个桶A，创建一个与A中a值共同出现的b值的直方图。
• 另一种估计连接的cardinality的方法是假设小表中的每个值在大表中都有一个匹配的值。那么连接选择性的公式将是。1/(Max(num-distinct(t1, column1), num-distinct(t2, column2))）。这里，列1和列2是连接属性。连接的cardinality是t1和t2的cardinality乘以选择性的产物。

b. 改进子集迭代器

• 我们对enumerateSubsets的实现是相当低效的，因为它在每次调用时都会创建大量的Java对象。
• 在这个奖励练习中，你将提高enumerateSubsets的性能，这样你的系统就可以对有20个或更多连接的计划进行查询优化（目前这样的计划需要几分钟或几小时来计算）。

c. 一个考虑到缓存的成本模型

• 估计扫描和连接成本的方法没有考虑到缓冲池中的缓存。你应该扩展成本模型以考虑到缓存效应。这很棘手，因为由于迭代器模型，多个连接是同时运行的，所以可能很难预测使用我们在以前的实验中实现的简单缓冲池，每个人可以获得多少内存。

d. 改进的连接算法和算法选择

• 我们目前的成本估算和连接运算符选择算法（见JoinOptimizer.java中的instantiateJoin()）只考虑嵌套循环的连接。扩展这些方法以使用一个或多个额外的连接算法（例如，使用HashMap的某种形式的内存散列）。

e. Bushy plans

• 改进所提供的orderJoins()和其他辅助方法，以生成bushy joins。我们的查询计划生成和可视化算法完全能够处理繁忙的计划；例如，如果orderJoins()返回列表(t1 join t2; t3 join t4; t2 join t3)，这将对应于一个繁忙的计划，(t2 join t3)节点在顶部。