Lab3 查询优化
Exercise 1 基于直方图的选择性估计
可能刚看本章的同学有点迷惑，为什么说了一堆统计的内容，因为查询优化的本质就是希望预先知道，执行语句时怎么才能更快，统计就能帮我们更好的估计大概需要多少的时间以选择更优的执行顺序。
在做Exercise 1之前，强烈建议认真看完本章提供的学习文档中的Optimizer outline，特别是2.2的Filter Selectivity，看完你就能懂基于直方图的选择性估计是怎么一回事了（看不懂的可以往下看，我详细的描述了代码的原理），在该估计当中每个桶中的元素都是均匀分布的（这里是理想化了，事实上并不是均匀的），了解了原理过后我们就可以开始写代码了。
-
IntHistogram.java 实现的是数值类型的直方图选择性估计，那么在构造函数中就需要实例化 最大值、最小值（为了算每个桶有多宽）以及桶的个数。
public IntHistogram(int buckets, int min, int max) { // some code goes here this.buckets = new int[buckets]; this.min = min; this.max = max; this.width = (1.+max-min)/this.buckets.length; }然后就是实现一些简单的 getIndex 、addValue这样的函数，最后就是实现该类中最难的函数 estimateSelectivity，通过传入的操作符和数，进行判断应该返回的概率。拿LESS_THAN 和 8举例，要选择比8小的概率，那就是统计前面有多少个比8小的数，假如桶宽为3，那么前面最前面两个桶都是比8小的，就有了下面的for循环。
for(int i=0;i<index;++i){ cnt += buckets[i]; }cnt里是比8小的计数，然后第三个桶中还有1/3是小于8的，也就是桶内为7的数比8小。那么第三个桶内有多少个7呢，通过之前的信息我们知道7在桶内是均匀分布的，同时桶内有buckets[index]个数，所以（1/3）* buckets[index]就是7的个数，然后再加上cnt统计的数，拿cnt/ntups就是概率了。下列代码的中的buckets[index]/width* (v-index * width-min) 就是 （1/3）* buckets[index]，(v - index * width - min) 就是 看当前桶内还有多少个比给定数小的。
public double estimateSelectivity(Predicate.Op op, int v) { // some code goes here if(op.equals(Predicate.Op.LESS_THAN)){ if(v <= min) return 0.0; if(v >= max) return 1.0; final int index = getIndex(v); double cnt = 0; for(int i=0;i<index;++i){ cnt += buckets[i]; } cnt += buckets[index]/width*(v-index*width-min); return cnt/ntups; } if (op.equals(Predicate.Op.LESS_THAN_OR_EQ)) { return estimateSelectivity(Predicate.Op.LESS_THAN, v+1); } if (op.equals(Predicate.Op.GREATER_THAN)) { return 1-estimateSelectivity(Predicate.Op.LESS_THAN_OR_EQ, v); } if (op.equals(Predicate.Op.GREATER_THAN_OR_EQ)) { return estimateSelectivity(Predicate.Op.GREATER_THAN, v-1); } if (op.equals(Predicate.Op.EQUALS)) { return estimateSelectivity(Predicate.Op.LESS_THAN_OR_EQ, v) - estimateSelectivity(Predicate.Op.LESS_THAN, v); } if (op.equals(Predicate.Op.NOT_EQUALS)) { return 1 - estimateSelectivity(Predicate.Op.EQUALS, v); } return 0.0; }
Exercise 2 TableStats实现
在上一个Exercise中我们实现了基于直方图的选择性估计，本Exercise中，我们将统计Database中所有表的每个字段的直方图估计，并返回查询消耗的时间代价。
-
TableStats.java 中我们将在构造函数实例化 访问每页的消耗、需要访问的DbFile、表的Id、表中有多少个字段，表中有多少Tuple，DbFile有多少页，同时存储每个字段对应的直方图。同时在构造我们将统计每个字段的最大值和最小值，并顺便统计一个表中有多少Tuple。统计完最大值和最小值后，就开始构造每个字段对应的直方图，然后将每个Tuple中的该字段的值加入直方图。至此TableStats.java中的构造函数就完事了。
public TableStats(int tableid, int ioCostPerPage) { // For this function, you'll have to get the // DbFile for the table in question, // then scan through its tuples and calculate // the values that you need. // You should try to do this reasonably efficiently, but you don't // necessarily have to (for example) do everything // in a single scan of the table. // some code goes here numTuples = 0; this.tableid = tableid; this.ioCostPerPage = ioCostPerPage; intHistogramHashMap = new HashMap<Integer, IntHistogram>(); stringHistogramHashMap = new HashMap<Integer, StringHistogram>(); dbFile = Database.getCatalog().getDatabaseFile(tableid); numPages = ((HeapFile)dbFile).numPages(); TupleDesc td = dbFile.getTupleDesc(); numFields = td.numFields(); Type types[] = getTypes(td); int[] mins = new int[numFields]; int[] maxs = new int[numFields]; TransactionId tid = new TransactionId(); SeqScan scan = new SeqScan(tid, tableid,""); try{ scan.open(); for (int i = 0; i < numFields ; i++) { if (types[i] == Type.STRING_TYPE){ continue; } int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE; while(scan.hasNext()){ if(i == 0) numTuples++; Tuple tuple = scan.next(); IntField field = (IntField)tuple.getField(i); int val = field.getValue(); if(val > max) max = val; if(val < min) min = val; } scan.rewind(); mins[i] = min; maxs[i] = max; } scan.close(); } catch (Exception e) { e.printStackTrace(); } for(int i = 0 ; i < numFields ; i++){ Type type = types[i]; if(type == Type.INT_TYPE){ IntHistogram intHistogram = new IntHistogram(NUM_HIST_BINS,mins[i],maxs[i]); intHistogramHashMap.put(i,intHistogram); }else{ StringHistogram stringHistogram = new StringHistogram(NUM_HIST_BINS); stringHistogramHashMap.put(i,stringHistogram); } } addValueToHist(); } private Type[] getTypes(TupleDesc td){ int numFields = td.numFields(); Type[] types = new Type[numFields]; for(int i=0;i<numFields;++i){ Type t = td.getFieldType(i); types[i] = t; } return types; } private void addValueToHist(){ TransactionId tid = new TransactionId(); SeqScan scan = new SeqScan(tid,tableid,""); try{ scan.open(); while(scan.hasNext()){ Tuple tuple = scan.next(); for(int i=0;i<numFields;++i){ Field field = tuple.getField(i); if(field.getType() == Type.INT_TYPE){ int val = ((IntField)field).getValue(); intHistogramHashMap.get(i).addValue(val); }else{ String val = ((StringField)field).getValue(); stringHistogramHashMap.get(i).addValue(val); } } } scan.close(); }catch (Exception e){ e.printStackTrace(); } }然后 就是一些返回函数，返回扫描页面的花费时间，返回遍历整个表内Tuple的时间，返回未知字段类型的被选中可能性，返回已知字段类型的被选中可能性 以及 返回总的Tuple个数。
public double estimateSelectivity(int field, Predicate.Op op, Field constant) { // some code goes here double selectivity; if(constant.getType() == Type.INT_TYPE){ IntField intField = (IntField) constant; selectivity = intHistogramHashMap.get(field).estimateSelectivity(op,intField.getValue()); }else{ StringField stringField = (StringField) constant; selectivity = stringHistogramHashMap.get(field).estimateSelectivity(op,stringField.getValue()); } return selectivity; }
Exercise 3 Join Cardinality的实现
在完成了选择时间花费估计后，我们需要对连接（也就是数据库中的关键词 join）进行连接花费的估计。
-
JoinOptimizer.java类包括所有用于排序和计算连接成本的方法。在这个练习中，你将写出用于估计连接的选择性和成本的方法，特别是。
实现 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输出的图元的数量，给定左边的输入是大小为card1，右边的输入是大小为card2，以及指示左边和右边（分别）字段是否唯一（主键）的标志t1pkey和t2pkey。 -
首先是 estimateJoinCost 函数，这里有可能大家已经忘了，不知道该怎么计算连接的花费，其实官方提供的Lab 3的文档中，在2.2.2的部分已经给出了计算的公式，只需要对应着查看 estimateJoinCost 函数传入的参数就可以对应公式上的关键点了。但肯定很多小伙伴想知道这个公式怎么来的。
这里其实就是涉及到基于嵌套循环连接的知识点，其实就是两个表循环连接，伪代码如下：
For each tuple r in R do For each tuple s in S do If r and s satisfy the join condition Then output the tuple <r,s>estimateJoinCost 函数如下：
public double estimateJoinCost(LogicalJoinNode j, int card1, int card2, double cost1, double cost2) { if (j instanceof LogicalSubplanJoinNode) { // A LogicalSubplanJoinNode represents a subquery. // You do not need to implement proper support for these for Lab 3. return card1 + cost1 + cost2; } else { // Insert your code here. // HINT: You may need to use the variable "j" if you implemented // a join algorithm that's more complicated than a basic // nested-loops join. double cost = cost1 + card1 * cost2 + card1 * card2; return cost; } -
然后 estimateJoinCardinality 函数 和 estimateTableJoinCardinality函数是配套的，通过estimateJoinCardinality 判断一个连接操作会影响多少个tuple（也就是一个join cardinality 的大小），那么怎么算会影响多少个tuple呢？就通过estimateTableJoinCardinality 函数计算。
public int estimateJoinCardinality(LogicalJoinNode j, int card1, int card2, boolean t1pkey, boolean t2pkey, Map<String, TableStats> stats) { if (j instanceof LogicalSubplanJoinNode) { // A LogicalSubplanJoinNode represents a subquery. // You do not need to implement proper support for these for Lab 3. return card1; } else { return estimateTableJoinCardinality(j.p, j.t1Alias, j.t2Alias, j.f1PureName, j.f2PureName, card1, card2, t1pkey, t2pkey, stats, p.getTableAliasToIdMapping()); } -
接下来就解析一下 estimateTableJoinCardinality 函数，其实关于这个函数怎么写在官方Lab 3 的2.2.4中描述的很清楚了，但是还是打算解答一下。
首先我们要明确，这个函数要返回什么，返回的就是，如果join成功话后将形成的Tuple个数。那么这就要分几种情况。
-
当Predicate.Op 是 EQUALS时：
- 当表一是join的字段是主键，对应表二的字段也是主键的话，就返回card数大的那个值。
- 当表一是join的字段是主键，对应表二的字段不是主键的话，就返回card2。
- 当表一是join的字段不是主键，对应表二的字段是主键的话，就返回card1。
-
当Predicate.Op 不是 EQUALS时：
- 那么官方文档中给了一个公式，就是返回 0.3 * card1 *card2 这个公式估计是经过论证的吧。
-
最后一种情况，当card结果小于等于0时，直接返回1。
明白这几种情况就能将 estimateTableJoinCardinality 函数写出来了。
public static int estimateTableJoinCardinality(Predicate.Op joinOp, String table1Alias, String table2Alias, String field1PureName, String field2PureName, int card1, int card2, boolean t1pkey, boolean t2pkey, Map<String, TableStats> stats, Map<String, Integer> tableAliasToId) { int card = 1; // some code goes here if(joinOp == Predicate.Op.EQUALS){ if(t1pkey){ card = card2; }else if(t2pkey){ card = card1; }else{ card = card1>card2 ?card1:card2; } }else{ double temp = 0.3 * card1 *card2; card = (int)temp; } return card <= 0 ? 1 : card; } -
Exercise 4 orderJoins实现
虽然Exercise 4只用写一个函数，但是其中涉及到了好几个现成的函数，需要对其理解一番才能完全写出orderJoins函数。
-
orderJoins函数返回值是这个 List 实际上这是通过PlanCache类的getOrder方法进行排序后返回的List集合，PlanCache是一个辅助类，可以用来存储最好的方式来排列一组给定的连接。
然后根据joinOptimizer类中join的大小，定义循环的次数，通过enumerateSubsets函数枚举所有join的集合，然后针对每个子集中的LogicalJoinNode在computeCostAndCardOfSubplan方法中计算，然后找到花费最小的进行存储，并保存在
planCache中。
ublic List<LogicalJoinNode> orderJoins( Map<String, TableStats> stats, Map<String, Double> filterSelectivities, boolean explain) throws ParsingException { //Not necessary for labs 1--3 // See the Lab 3 writeup for some hints as to how this function // should work. // some code goes here //Replace the following int numJoinNodes = joins.size(); PlanCache pc = new PlanCache(); Set<LogicalJoinNode> wholeSet = null; for(int i = 1; i <= numJoinNodes; i++) { Set<Set<LogicalJoinNode>> setOfSubset = this.enumerateSubsets(this.joins, i); for(Set<LogicalJoinNode> s : setOfSubset) { if(s.size() == numJoinNodes) wholeSet = s; Double bestCostSofar = Double.MAX_VALUE; CostCard bestPlan = new CostCard(); // 该类用于保存plan，cost，card for (LogicalJoinNode toRemove : s) { CostCard plan = computeCostAndCardOfSubplan(stats, filterSelectivities, toRemove, s, bestCostSofar, pc); if (plan != null) { bestCostSofar = plan.cost; bestPlan = plan; } } if (bestPlan.plan != null) { pc.addPlan(s, bestPlan.cost, bestPlan.card, bestPlan.plan); } } } return pc.getOrder(wholeSet); }