MIT 6.830是研究生级别的数据库课程。其课程主页见http://db.lcs.mit.edu/6.830/sched.php。
我的代码见https://github.com/PeriodicLaw/simple-db-hw。
Lec2
关系数据库并非一开始就有的。在关系模式出现之前，最早的是IMS模型，即层次数据模型。数据用记录（元组）表示，记录有用于唯一标识的key，且记录类型之间用树状关系连接起来。 IMS实质上是只有父-子关系的关系模型，存在很多限制并且会造成冗余。IMS的操作语言是即时记录（record-in-time）的，直接操作数据库细节，被执行器直接执行，因而需要程序员手动优化。
CODASYL是用于改进IMS而出现的，用网状结构取代了树状结构，导致模型更加复杂了。然而它在操作语言上并无改进，仍然是即时记录的。
1970年，Codd提出了关系模型，并证明了关系演算和关系代数之间的等价性。Codd提出的操作语言与IMS和CODASYL不同，是set-at-a-time的。
在此基础上则有进一步的ER模型、范式等等。
Lab1
文档对整个数据库的设计的描述还是不太详细，很多靠自己摸索。
数据库设计
整个数据库的全局信息，通过DataBase类（单例）访问，底下有三个组件：
Catalog用来索引，根据表名得到表ID，根据表ID得到表（实质是文件）；BufferPool用来缓存页；LogFile处理日志，这里用不到。
将数据库与磁盘中文件对应起来的，则是三层结构：
DbFile既对应数据库里的一个表，又对应硬盘上具体的文件，使用tableid（实质可能是用文件路径生成的hash）索引；Page是缓存，一个表可以有多个页用作缓存，当需要访问时将其调入缓存池，使用PageId（实质是tableid+pgno）索引；Tuple是元组，对应一行，使用RecordId（实质是PageId+tupleno）索引；TupleDesc对应表头。
针对DbFile的实现，有两种：
HeapFile是顺序存储所有元组在一起的简单结构；BTreeFile使用B+树，这里用不到。
两种实现都有各自对应的Page等。
HeapFile的实现
HeapFile对应磁盘上一个具体的文件，由若干连续的页（HeapPage）组成，一个页一般4096字节。
HeapPage的结构包括一个头和若干元组，头是一个bitmap，用来表示每个元组是使用中还是未使用。 在内存中，每个元组都是一个Tuple对象；在磁盘上，每个Tuple占据一段字节，由里面的每个Field连续使用（整数是一个4字节的int，字符串是先一个int表示长度，再每个字符）。
实验里会要求我们实现iterator。HeapFile的iterator遍历每个页的iterator；HeapPage的iterator遍历每个被使用的tuple。
Lec5
数据库大概包括几个组成部分：
- 进程管理器，负责进程&线程的调度，从而实现并发
- 客户端通信管理器，负责和客户端通过一定的协议（JDBC等）通信
- 关系查询处理器，负责解析、优化、执行SQL查询等
- 事务与存储管理器，负责与硬盘交互的访问方法（Access Method）、事务管理等
- 共享组件和工具
进程管理涉及到OS提供的进程&线程工具。一般来说有这么几种模型（一个worker对应一个客户端，负责执行SQL查询等操作）：
- 每个worker对应一个进程
- 每个worker对应一个线程（OS级线程/DBMS自己实现的轻量级线程）
- 使用进程池/线程池
进程管理还要负责准入控制——当资源不足时，worker必须等待直到资源可用。
关系查询处理器将SQL语句（通常是DML，DDL一般直接解释执行不需要走优化等流程）解析、优化、执行，具体过程包括：
- SQL解析，以及解析时的权限检查，得到SQL语句的内部表示。
- 重写（改变内部表示的同时不改变语义），比如视图扩展（把视图替换成下面的表）、常量计算、布尔逻辑重写、冗余连接（join）消去、子查询展开等等。
- 优化（将内部表示转换成一个高效的执行计划）。执行计划是将表中数据通过各种管道、流经若干算子，组成的一张图。
- 执行。
Lab2
本次实验主要实现的内容包括：
Filter和Join数据库操作（Join用最简单的嵌套循环即可）- 底层
HeapFile和BufferPool的写功能 Insert和Delete数据库操作
此外，给的代码已经实现了一个SQL Parser和优化器，可以按照指导，体验直接的SQL操作。
实现BufferPool写功能的时候要特别注意“cache一致性”：BufferPool的insertTuple操作会调用底层DbFile的insertTuple操作，这个操作会返回一个被修改了的页的列表；这些页并不一定已经在池子里面，而有可能是新建的页。因此，BufferPool需要将这些不在池中的页加到池里，否则在后续操作时会重新从磁盘读取这些页——其内容是过时的。
另外，随着实验的深入，可以明显感受到很多代码的冗余以及设计的不合理之处。
Lec10
SQL优化，也就是从声明式的SQL语句得到尽量优的具体执行过程。具体而言，SQL会得到逻辑上的计划（logical plan）；一个逻辑计划可能有若干物理实现（physical plan），优化器需要选择（大概）最优的一个。
在Selinger的论文中，数据通过RSS（Research Storage System）进行存储管理。 数据会分布在若干页上，每个页包含若干元组。一个页的元组不一定都是同一个关系中的，但几个关系会组成一个segment，每个页只会属于一个segment。
访问元组则有两种方式：
- 直接扫描所有页，此时每个元组、每个页都会被读取，但每个页至多读取一次。
- 索引扫描（Index Scan）。索引往往是类似B+树的结构，其叶节点代表具体的元组，并且会指向某个页。由于我们可以设定起始和结束的键值，所以不需要读取所有的元组；但是一个页可能会被读取多次（因为索引相近的元组不一定在相近的页上）。如果元组按照索引的顺序来插入页当中的话，这种索引就叫成簇索引（Clustered Index）。
单个关系的查询
首先考虑只有单个关系的查询（也就是不存在join）。我们可以将SQL的WHERE子句改写成若干布尔因子（boolean factor）的合取范式，每个factor都是类似column op value column IN ...之类的形式。 factor如果谓词是sargable的、并且引用的column是索引的key，那么就说这个factor匹配这个index（比较绕口，意思是这个factor可以用索引扫描来优化）。
然后，基于一些统计数据（比如一个关系或索引里有多少元组、对应多少页等等），我们对每个factor算一个估计的选择因子（selectivity factor）F，它是这个factor取真的概率的估计值；factor组合起来的时候，假设factor之间互相独立，从而计算组合的F；论文里有具体的计算方法，大概就是可以被索引的按照索引均匀分布来估计，否则直接给一个经验值。 有了WHERE子句整个的F以后，我们就可以估计一个select语句会选出多少元组了。
我们对于一个计划的代价估计，是它所要访问的页数量和会取出的元组数量的加权平均。前者衡量IO代价，后者（也叫做RSI调用数）衡量CPU代价。 有了统计数据和估计的因子F，我们可以估计一个具体计划的代价，论文里也有具体的计算方法。 值得注意的是非clustered的索引，会假设元组是完全打乱的——访问的页数量=元组数量。
考虑到ORDER BY和GROUP BY子句的情况会更复杂一点，我们还要加上排序带来的代价。（这里作者讲的有点模糊）
有join的情况
两个关系之间的join，作者列举了两种方法：
- 嵌套循环，也就是两层循环进行比对；
- 合并连接（merge join），往往是比较两列相等的时候，如果两列有序，则可以用类似归并的方法一遍得到结果。
当关系数量变多的时候，join顺序就变得重要了。为了限制考虑的join顺序的种类数，我们可以要求笛卡尔积（也就是没有join谓词限制的连接）尽可能迟地出现。
然后，作者给出了关于join的代价估计；这里两种方法的估计公式是一样的，但子项的估计值可能不一样。
最后作者以一个3关系join的例子说明具体是如何生成搜索树并估计代价的。
- 首先考虑只有1个关系的情况，分析可能的索引操作，是否有序，以及各自带来的代价。
- 然后考虑2个关系的情况，先考虑join顺序；对于nested loop，分别考虑两个关系的索引方式即可；对于merge join，则要考虑第一个关系的索引方式，第一个关系是否需要再排序，以及合并带来的代价。如果结果相同（表和有序性相同），进行剪枝，只保留最优的那个。可以看出这是动态规划的思想。
- 最后考虑3个关系的情况，先考虑前2个关系的选择，然后根据nested loop或是merge join再进行第三个选择。
嵌套查询
嵌套子查询又包括无关和相关子查询两种。前者只需要预先执行一次子查询即可，得到一个内部的列表即可；后者则需要随元组的改变而重新计算，但在某些条件下，不是每次都要重新计算。
Lab 3
接下来就实现SQL优化器。具体又分为两部分：代价估计和join选择。
代价估计
首先，我们需要收集统计数据。 与Selinger论文中不同的是，我们会使用直方图估计，扫描一遍整个表，并将数据放入若干个桶中。估计的时候，桶内假设均匀分布。这可以看作是对Selinger中简单均匀分布的一种改进。 具体而言，我们实现IntHistogram类即可，而StringHistogram已经帮我们实现好了。
其次，我们对不涉及join的情况进行估计，具体而言是估计谓词的selectivity（即F因子）、扫描代价、表的大小。扫描代价通过页数乘以一个用于加权的因子即可（平衡磁盘与IO）。 具体而言，实现TableStats类即可。（我真的很想吐槽这里的接口设计……）
最后，考虑join的代价估计。这里我们只需要考虑nested loop的join即可，并且已经给出了一个简单的估计公式。 为了估计多个表join的代价，我们还需要估计两个表join以后的基数——指导里也给出了一个非常粗略的估计方法。
join选择
接下来，我们对任意一组join谓词，选择最优的join方法。我们用动态规划的算法完成估计，对每个谓词集合，考虑最后一个join使用哪个谓词，将其他谓词join的最优策略与最后一个谓词组合得到新的最优策略。具体而言，按照给的伪代码实现orderJoins函数即可。
Lab 4
这个实验实现基于锁的并发。锁这里是对于BufferPool里的页缓存加锁，有共享锁（读）和独占锁（写）两种，在获取页之前需要先获取相应的锁。这里还要利用java里的synchronized同步机制。
这里有个很重要的问题，就是死锁的检测和处理。简单起见，死锁的检测可以用定时器实现，如果一段时间内都无法获取到锁，就说明发生死锁；发生死锁时，直接中止事务，释放自己持有的所有锁。
但这样会导致一个新问题，就是两个对称的线程同时申请锁，同时发生死锁，同时中止并放弃锁，结果就是同时重来一遍。参考了一下网上的做法，我们可以将定时时长设为一个随机值，从而破坏对称。 但是在高并发的情况下，出现恰好解决死锁的概率较低，可能跑很长时间也解决不了死锁。在测试的时候，5个线程跑3s就能通过，10个线程跑1分钟也没有通过。