CMU15-445数据库实验全满分通过笔记2021Fallbustub-cmudblab Contents
PROJECT #0 - C++ PRIMER
如果本地测试能通过，gradescope报错Test Failed: Test was not run. Plea check the autograder!，说明build失败，可能的原因是没有进
⾏make format格式检查，还可能是上传课程的年份搞错了（注意仓库是最新的版本，所以提交到最新的课程）。
如果内存安全测试报错Conditional jump or move depends on uninitialid value(s)，可能是因为矩阵乘法中没有将矩阵初始化为全0。
1. const对象只能访问const成员函数。const成员函数例⼦：
virtual int GetRowCount()const{
return rows_;
}
2. C++智能指针unique_ptr独享被管理对象指针所有权，要创建⾮空的 unique_ptr 对象，需要在创建对象时在其构造函数中传递原始指
针，即：
std::unique_ptr<RowMatrix<T>>ret(new RowMatrix<T>(r1, c2));
std::unique_ptr<RowMatrix<T>> ret =new RowMatrix<T>(r1, c2);//错误，不能以赋值⽅式定义！
将其转换为普通指针：
RowMatrix<T>*p = ();
3. 抛出异常：
throw Exception(ExceptionType::OUT_OF_RANGE,"out of range!");
PROJECT #1 - BUFFER POOL
TASK #1 - LRU REPLACEMENT POLICY
原理⽐较简单，可见。
1. 加锁和解锁：
std::mutex mtx_;
mtx_.lock();
···
红烧鸦片鱼mtx_.unlock();
注意mutex不是可重⼊锁（递归锁），所以两个函数之间有调⽤关系时，不能上同⼀把锁。
TASK #2 - BUFFER POOL MANAGER INSTANCE
这个⽐较难理解的是frame和page、buffer pool和replacer之间的关系。
实际上，buffer pool像⼀个page的容器，⽽page在容器的哪⾥由frame标记，page table就是记录page和frame的映射关系的。也就是说，frame是⼀个物理的概念。⽽frame中，哪些被page占⽤，哪些是空的，由free_list标记。哪些包含page的frame可以被victim，需要借助replacer来选择。replacer
仅仅记录frame的编号。最后，page中的page_id说明它来⾃于哪个物理页⾯，但实际上虚拟页⾯和物理页⾯的转换已经写好了，我们不需要关⼼。
操作的具体步骤基本上在注释中说的很明⽩了，再补充⼀些：
1. 新建页⾯是要pin的，⽽fetch页⾯时如果已存在则引⽤计数加⼀，否则相当于新建⼀个页⾯，引⽤计数设为1。
2. ⼀个本地测试样例没测出来但在gradescope中测试出来的地⽅：UnpinPgImp中只有is_dirty_为真时设置页⾯为脏，如果is_dirty_
为假，页⾯不能设置成不脏，因为其他进程可能写过该页⾯！
TASK #3 - PARALLEL BUFFER POOL MANAGER
貌似是今年新加的⼀项。实现起来很简单，搞清楚继承关系。
1. 为存储多个BufferPoolManagerInstance，⼀开始想创建⼀个对象数组，但是数组需要⽤花括号的形式构造，⽽且需要写出实际的
构造参数。因此，最后采⽤vector，并且循环构造压⼊。vector的类型为BufferPoolManagerInstance。
2. BufferPoolManagerInstance和ParallelBufferPoolManager是平级的关系，它们都继承于BufferPoolManager类。在进⾏
FlushPgImp、UnpinPgImp等时，可以直接取vector中的元素操作某⼀个缓冲池；也可以使⽤GetBufferPoolManager来取，不过它的返回值是⽗类指针类型的，需要进⾏类型转换：
return dynamic_cast<BufferPoolManagerInstance *>(GetBufferPoolManager(page_id))->FlushPgImp(page_id);
PROJECT #2 - EXTENDIBLE HASH INDEX
做的⾮常艰难，只能借助gradescope的输出来debug，前前后后提交了近200次······好多坑我只能说。
TASK #1 - PAGE LAYOUTS
零长度数组与reinterpret_cast
草字头一个今
HashTableBucketPage类中，复杂保存键值对的成员数组的定义：
MappingType array_[0];
这是⼀个Zero-length array（零长度数组）。它位于结构体/类的最后，本⾝不占⽤空间。在声明结构体的时候分配内存，去除掉其他元素的部分就是零长度数组可以访问的部分。
⽽类的实例化是不能定义⼤⼩的。但是，我们的类⽐较特殊，它的实际意义是⼀个页⾯，⽽页⾯的⼤⼩是固定的。从测试代码可以看到该类实例化是这样的：
auto bucket_page =reinterpret_cast<HashTableBucketPage<int,int, IntComparator>*>(
bpm->NewPage(&bucket_page_id,nullptr)->GetData());
定义了⼀个页⾯，页⾯的data部分是全零的字节。使⽤reinterpret_cast，将这块空⽩解释为我们的对象。由于类中的成员函数是在代码段的，这块空⽩实际上被解释为类中的成员函数，内存分配与结构体类似。本题中已经根据页⾯⼤⼩为我们算好了BUCKET_ARRAY_SIZE，所以可以放⼼地取⽤这个零成员数组了。
待月西厢下桶的⼤⼩
源代码中，桶的⼤⼩是这样确定的：
#define BUCKET_ARRAY_SIZE (4 * PAGE_SIZE / (4 * sizeof(MappingType) + 1))
char occupied_[(BUCKET_ARRAY_SIZE -1)/8+1];
妙就妙在这⾥occupied数组的⼤⼩，是对BUCKET_ARRAY_SIZE/8向上取整，但是却不会发⽣内存泄漏。题中PAGE_SIZE已经定义为4096。取sizeof(MappingType)为1，BUCKET_ARRAY_SIZE计算得3276，occupied_差长度计算得410，实际占⽤空间为
410*2+3276*1=4096，正好填满。测试了⼏个例⼦，都满⾜不会内存泄漏，直觉上来说，是因为char的size⽐较⼩，所以在较⼤的PAGE_SIZE下，多那么⼀个两个char不会抵消计算BUCKET_ARRAY_SIZE向下取整的富余空间。
桶内删除条⽬
为什么在HashTableBucketPage类中定义了两个⼯具类数组occupied和readable？在occupied的注释中找到原因：// 0 if tombstone/brand new (never occupied), 1 otherwi.
原来删除⼀个条⽬之后，occupied仍然显⽰占据状态，所以应该修改readable来表⽰删除。不过，个
家能⼈认为设计两个⼯具类数组是没有什么必要的，因为tombstone的设计主要是为了在开放寻址法中防⽌探测中断 ，⽽我们的EXTENDIBLE HASH TABLE显然不需要，如果让我设计，删除直接把占⽤标志去掉就可以了。
重点来了！墓碑仅仅辅助探测，因此在插⼊节点时，仍然将其视为可以插⼊（因为插⼊后不会影响探测）。所以，桶空桶满只需要看readable。
桶中的元素是否连续
1992年属什么这个问题及occupied数组中的1是否是从数组头到数组尾连续增长的。进⾏普通的插⼊和删除条⽬时，我们可以保持occupied数组中1的连续状态，这让对桶的操作不必对整个数组遍历，在occupied数组找到0时停⽌即可。但是，实际上这⾥有个坑，因为有⼀种操作可以改变这种连续状态，那就是桶分裂。由于桶内数组被设置成了私有类型，在进⾏桶分裂的时候，只能通过修改occupied的每⼀位来代表数组是否还保留在当前桶内。因此，在插⼊、删除元素到桶内时，不能把元素看成连续的，还是需要遍历整个数组。
以上是我还没意识到墓碑值可以插⼊的时候写的，意识到了之后显然不⽤考虑了，当然不连续啦！
TASK #2 - HASH TABLE IMPLEMENTATION
总体实现
这张图画的很清楚了：
注意本次project建议根据后⾯的位来进⾏区分，即⽬录页中数组的下标，和图上相反。大悲咒解释
对页的操作
这是⼀个重点，因为我在这上⾯栽了100多次。。因为没有及时unpin导致bufferpool满，进⽽⽆法运⾏，⽽在gradescope上根本没法看出来，直到bufferpool满时LOG_DEBUG才找到。
buffer_pool_manager->NewPage(&bucket_page_id,nullptr);//新建页
reinterpret_cast<HashTableDirectoryPage *>(buffer_pool_manager_->FetchPage(directory_page_id_,nullptr)->GetData());//获取页内容
buffer_pool_manager_->UnpinPage(bpg_page_id,true,nullptr);//⽆论新建页，还是获取页，都不要忘记unpin
普通的查找、插⼊和删除都不难，重点是分裂和合并的逻辑。
桶页分裂
注意，接下来提到的“桶”指⽬录页数组的⼀个元素，⽽不是具体的存储元素的“桶页”，前者指向后者，是多对⼀的关系。
插⼊时如果桶页已满则进⾏分裂。步骤如下：
1. 获取⽬录页、需要分裂的桶页。记住桶页所在页（Page）的ID，最后unpin要⽤。
2. 判断是否需要IncrGlobalDepth。如果需要分裂的桶的深度和全局深度相等了，则增加全局深度，即将桶数扩张⼀倍，扩张的部分桶
对应的bucket_page_id和local_depth都要和前⾯的桶对应。
3. 新建⼀个桶页，并修改⽬录页中的bucket_page_ids，让桶中该指向新桶页的指向它。遍历指向旧桶页的桶，根据桶的局部深度对应
的位之前的那⼀位来判断应该指向新桶页还是旧桶页。边遍历边增加local_depth：
size_t common_bits = kti %(1<< dpg->GetLocalDepth(kti));//kti为分裂桶下标
size_t ld = dpg->GetLocalDepth(kti);
for(size_t i = common_bits; i < dpg->Size(); i +=(1<< ld)){
if(((i >> ld)&1)!=((kti >> ld)&1)){
dpg->SetBucketPageId(i, new_bucket_page_id);
}
dpg->IncrLocalDepth(i);
}
4. 移动元素到新桶页。在桶页类中⾃定义删除和设置键值对的public函数，对桶页中每个元素重新将key映射到页来判断是否需要移动。
5. unpin⽬录页、旧桶页和新桶页，重新插⼊元素。
桶页合并
如果删除后变成空桶页则尝试合并。步骤如下：
1. 获取⽬录页，需要合并的空桶在⽬录中的下标，以及镜像（image）桶的下标。image即合并的对象，如⽬录页容量是8的话，下标
0/4，1/5，2/6，3/7互为镜像。
2. 判断是否满⾜合并条件，即该空桶深度不为0，且桶和镜像桶深度相等。还有⼀个条件，就是桶和镜像对应的不是同⼀个桶页（否则没
必要合并了）。若不满⾜，直接返回。
3. 转移那些指向空桶的指针到镜像桶页，这⼀步和桶分裂的第三步实现类似。
4. 删除旧桶页。注意删除之前如果有fetch过，⼀定要对应进⾏unpin，否则pin_count不为1，没法删除。
5. 对⽬录进⾏Shrink，判断条件是所有桶局部深度都⼩于全局深度。此时，每⼀个桶和它的镜像桶都指向同⼀个桶页，所以直接
DecrGlobalDepth。
之后还有⼀步，那就是遍历Shrink后的⽬录，对每个空桶尝试合并。这是因为，Shrink之后，每个桶的镜像发⽣了变化。例如，假设⽬录页容量本来是8，其中0/4/5/7（下标）是空桶，接下来，6变成空桶，2与6合并，并发⽣Shrink，此时2的镜像为0，0是空桶应该合并。⽽之前0刚变为空桶时，它的镜像是4，所以还不能与2合并。
PROJECT #3 - QUERY EXECUTION
helper class
为了了解这些类是怎么配合实现语句的完成的，需要好好读下⼯具类和测试类代码，然后厘清类之间的关系。知道每个类及其成员变量、成员函数的功能，就能顺理成章完成各项操作的实现。
Value走向远方汪国真
从最⼩的类开始。Value可以理解为单元格，并且提供了⼀些⽐较和运算的函数。
Tuple
可以理解为⼀⾏。其中的data_字段存储了Value，使⽤GetValue()即可获得。虽然tuple中有rid_字段，但是在插⼊tuple操作中没有对其进⾏修改，⽽且也备注了该字段只在指向TableHeap时有⽤，所以不能把它当成tuple所在的RID。
TablePage
林丹广告继承于Page类，是表的存储单元。提供了对页中Tuple的操作。
TableHeap
可以理解为⼀个表的物理表⽰，对应TablePage的双向链表。提供了对表中Tuple增删改查的操作。
TableIterator
TableHeap的迭代器，由于其运算符已经重载，所以可以当成Tuple的指针来使⽤。
RID
RID对应物理表页ID及在页中槽的位置，⼀般记录⼀个tuple的物理位置。
Column
表格⼀列的列头信息，包含类型、名称等。
Schema
表格的所有列头，主要包含⼀个Column的数组。
Index
表格的索引信息，每个索引提供tuple到RID的对应关系，依靠之前的ExtendibleHashTable实现。
Catalog
⼀个数据库的全部表格信息的索引，提供了对表格的操作。成员变量主要包括：TableInfo的表，每个TableInfo包括⼀个表格的ID、Schema、TableHeap；IndexInfo的表，即每个表格的索引信息。
AbstractExpression
对where语句（其实不⽌where语句中⽤到）进⾏拆分，形成⼀个树，其中的每⼀个节点就对应⼀个AbstractExpression类，该抽象类包括其⼦节点以及返回类型，还有其他有⽤的⽅法。其中：
