Database

该系列博客只是为了记录自己在写Lab时的思路，按照课程要求不会在Github和博客中公开源代码。欢迎与我一起讨论交流！ 这个project和之前就不一样了，开始深入数据库内核的实现了。需要理清楚一条sql语句是如何被执行的，方才能写出代码。 前置奶酪 一条SQL语句的执行 这里需要去看看一条sql语句传入bustub内部之后的代码：src/common/bustub_instance.cpp:ExecuteSqlTxn： auto BustubInstance::ExecuteSqlTxn(const std::string &sql, ResultWriter &writer, Transaction *txn, std::shared_ptr<CheckOptions> check_options) -> bool { if (!sql.empty() && sql[0] == '\\') { // 处理元命令 ... } // binder，但是在其中会使用libpg_query来解析sql语句 bustub::Binder binder(*catalog_); binder.ParseAndSave(sql); // 经过上一步后，binder中的statement_nodes_存储着所有的语句解析节点 for (auto *stmt : binder.statement_nodes_) { // 将stmt转换成BoundStatement对象，方便后面处理数据 auto statement = binder.BindStatement(stmt); // 只有不需要构建plan树、不需要进行优化的sql语句才会在switch之后继续执行 switch (statement->type_) { ... } // 生成初步的执行计划 bustub::Planner planner(*catalog_); planner.PlanQuery(*statement); // 优化刚刚的执行计划 bustub::Optimizer optimizer(*catalog_, IsForceStarterRule()); auto optimized_plan = optimizer.Optimize(planner.plan_); ....

该系列博客只是为了记录自己在写Lab时的思路，按照课程要求不会在Github和博客中公开源代码。欢迎与我一起讨论交流！ 太菜了，从没打过这么艰难的仗QAQ。由于课程的要求不能公开源代码，所以网上的资源会少很多，平台上的测试案例比较全面，有的还比较刁钻，需要考虑到可拓展哈希的实现细节。在自认为写完了后，提交了近40来次总有几个测试集过不了，还好没有崩溃，在看了几篇博客的方法后，加上自己画图理解，最后终于过了😭。不过回头写博客的时候再去看代码，也没有特别的复杂，还是得明白其中的算法逻辑是如何实现的。 Task1 - Read/Write Page Guards 简单来说，就是为Page实现一个RAII来自动管理资源。因为在BufferPoolManager::Unpin中，每次调用这个函数，都会让对应的page的pin_count_ - 1，当这个值为0时，这个page就可以被回收，或者说被替换了。但如果我们忘记去手动调用，该页面将永远不会被逐出缓冲池。由于缓冲池以更少的帧数运行，磁盘内外的页面交换将更多。不仅性能受到影响，而且很难检测到错误。 主要需要考虑如何编写移动构造、移动赋值的逻辑。移动了一个对象后，原来的对象的资源应该转移到了新对象上，那么原来的对象无法再访问资源（将原来对象的资源重置nullptr或清空）。 还有一个Drop()的接口，这是提供给使用者的释放资源的api，在实现虚构函数时可以直接调用它。Drop的实现就是调用Unpin，然后置空资源。需要注意的是，在进行移动赋值时，一开始也要Drop一下，考虑这样一种情况： auto p = std::move(basic_page_guard); p = std::move(basic_page_guard2); 这个时候同一个变量p接管了两个page，那么应该在第二个移动赋值时先drop掉第一个，因为第一个page不再使用了，自然要Unpin。 还有就是在三个page guard类重载移动赋值时，如果需要移动的对象和自身是同一个，那么直接返回自己就好： auto BasicPageGuard::operator=(BasicPageGuard &&that) noexcept -> BasicPageGuard & { if (&that == this) { return *this; } // ... 其他操作 } 在ReadPageGuard和WritePageGuard的Drop()中，还需要考虑释放管理的page的锁。对应的，锁的获取发生在FetchPageWrite()和FetchPageWrite()中。 Task2 - Extendible Hash Table Pages 为什么我们需要可扩展哈希？ 下图来源：https://www.bilibili.com/video/BV1Qt421w7JT 在bustub的设计中，Header Page，Directory Page和Bucket Page都是无法直接构造出来的，即不能通过构造函数创建，只能通过各自的PageGuard中的As()或者AsMut()函数来转换。 Header header page中有一个max_depth_的成员变量，1 << max_depth_即为header page中能存放的目录的索引的数量。当我们有值需要放入哈希表时，获取hash(key)的二进制最高max_depth_位作为索引，再从header中对应位置去找到directory。对应的ExtendibleHTableHeaderPage中的功能实现并不难。 Directory directory中有两个depth： Global Depth：若global depth为n，那么这个Directory就有2^n个entry（相当于指向2^n个bucket） Local Depth：若local depth为n，则在这个对应的bucket下，每个元素的key的最后n位都相同 类似header中获取下一级页的索引，directory获取hash(key)的二进制最低global_depth_位作为索引。那local depth的作用是什么呢？...

该系列博客只是为了记录自己在写Lab时的思路，按照课程要求不会在Github和博客中公开源代码。欢迎与我一起讨论交流！ 这个Project需要我们实现一个缓存池，减少对于磁盘的频繁IO。开始慢慢上强度了，细节拉满！ ...

该系列博客只是为了记录自己在写Lab时的思路，按照课程要求不会在Github和博客中公开源代码。欢迎与我一起讨论交流！ project0只在task4中浅浅涉及了一点BusTub的内容，其他都是检测我们对于C++的一个掌握，主要涉及智能指针和C++的常用特性（dynamic_cast、std::move、并发与锁等）。 ...