2022秋MIT6.830lab3实验报告
本实验主要实现查询优化器，针对连接优化
连接优化：对于r1 join r2 join r3这样的查询存在很多种不同连接顺序的查询计划，本实验主要针对该连接计划，选择出成本最小的连接计划
EXERCISE 1
实现IntHistogram
IntHistogram是针对int字段的直方图，通过直方图我们可以得到一个谓词在一个字段上的选择性，即经过这个谓词过滤出多少比例元组, 该类没有什么难点，根据hint编写计算逻辑即可，核心逻辑展示：
EXERCISE 2
实现TableStats
这里TableStats是记录表的数据，主要是包括各个Field的直方图，同样比较简单，这里给出具体的实现逻辑
需要两次遍历，第一次维护int的max和min数组，第二次进行addValue操作
EXERCISE 3
实现两个估算成本的方法
该方法根据hint中的公式填写即可
根据公式计算即可:
- 如果有key，则不超过key的tuple数
- 如果是笛卡尔积，乘0.3的经验系数，同时必须大于两个表的任意一个card
EXERCISE 4
实现orderJoins
这里采用塞林格优化的方法，其实本质上是动态规划，从小集合推导到大集合的最优方法
- planCache，类似记忆化，记录之前的最优方法
- costcard，将plan cost card聚合成一个类
- computeCostAndCardOfSubPlan, 本质是上计算+与当前最优值比较，如果目前方法更优则返回plan否则是null
这里仔细研究一下computeCostAndCardOfSubPlan的源码
核心代码：
news是去掉joinToRemove的集合，如果空代表着是基础连接，即 r1 join r2, 这里只需要分别计算cost 和 card即可，否则则是子连接 和 一个表的连接，具体来看doesJoin函数检查哪个是已join的连接计划中的，如果是已join的连接计划的表，可以通过，planCache得到对应的cost和card，这样最终得到了两个表的cost和card，通过上述实现的estimateJoinCost函数计算连接成本与bestCost比较从而得到最后的costcard