A Year in BusTub
Table of Contents
Introduction
It has been almost a year since I started working on BusTub, the educational database system for the CMU 15-445/645 (Database Systems) course. The system has undergone significant transformations, so this is an excellent time to revisit those changes and set its next milestone.
To return to where it started, I had not imagined working on BusTub until an email popped up in my inbox: “Do you want to be a TA for 15-445 this fall?” It was from Andy Pavlo, shortly after I accepted the MSCS offer from CMU.
I had heard rumors that CMU courses were super challenging, and I wondered whether I would have enough time to participate in the course as a TA during my first semester at CMU. After I explained my concerns, Andy hired me as a system developer so that I could focus on coding without worrying about all the other stuff, and I went ahead and landed big features in the codebase. I created pull requests very quickly, and the review queue soon grew. Wan spent so much time reviewing my PRs that Andy asked him to focus on his research. Yuchen took over the mission and got all the remaining PRs merged. Interestingly, when former TA Abi returned from TileDB in spring 2023, she complained that the codebase had changed too much since her last time as a TA. Finally, I discovered that the course load at CMU was not as heavy as I had expected, so I decided to host office hours and became more like a TA during the second half of the fall semester.
On the one hand, students told us that the benchmarks and optimizations were fun to work on, and they tried to beat each other on the leaderboard. On the other hand, students complained that the course was more challenging than senior alumni had told them. Overall, though, BusTub is becoming more like a SQL database system through which people can learn about and connect deeply with what the database industry is doing. It is a good starting point for anyone pursuing a database career or seeking to understand more about systems programming.
New Features
SQL
When I first looked at the BusTub repo in the summer of 2022, I was surprised that BusTub did not support SQL, even though the entire course was based on relational databases (and SQL)! The lack of SQL support was a big problem because students could not learn how a database system works end to end by solely staring at query plans. Therefore, I took the initiative to add a query processing layer to BusTub. After some initial investigation by Garrison, we realized that the easiest way to integrate SQL was to build the layer from scratch instead of plugging in a query processing layer from another system. There was a branch that made BusTub the query backend of PostgreSQL, but it was far from complete. Following DuckDB’s approach, I used only the PostgreSQL parser and wrote the rest of the query processing layer (i.e., binder, planner, and optimizer) myself.
The query processing layer developed alongside the course. I added many new things to the codebase while students completed homework based on it! Working on both in parallel meant that I needed to be extra careful not to touch the source files that students edited or create potential conflicts with their solutions. The plan was for students to use SQL to test their executor implementations in Project 3. I started working on the codebase in late August, and Project 3 would begin in mid-October, so I had only one and a half months to deliver the result. If it worked, students could use SQL in fall 2022. If it failed, we could introduce it only in the following semester. The schedule was tight, but we shipped SQL support in the end.
It did not take us long to make our first SQL SELECT 1 work—probably two weeks or so—with a hand-crafted binder and planner. After that, I spent another two weeks integrating joins, aggregations, insertions, sorts, and create statements into the query processing layer—all the executors we supported in BusTub. Progress went so well that we still had several weeks before rolling out the query execution project. Therefore, I brought more of the crazy ideas in my mind to life.
Query Optimizer
An optimizer was outside my original plan; I had intended to build only a planner that directly transformed SQL into plan nodes. To make the query processing project more interesting, especially for those with a strong interest in database systems, I decided to spend some time adding a rule-based optimizer so that students could optimize their systems not just by making their executors more efficient, but also by rewriting query plans.
I typically view a database system as three layers:
- The query processing layer, which takes SQL in and does transformations.
- The query execution layer, which contains many query executors.
- The storage layer, which stores data and serves read requests.
Generally, optimizing the lower part of the system (i.e., storage) is hard, but it benefits all kinds of query patterns. Optimizing the query processing layer is much easier, as people generally handle various “edge cases” that bring considerable benefits to a small set of queries. For example, at my previous company, I would usually take one TPC-H query, examine its plan, and determine how a better plan could make the query faster. If a query optimizer does not produce an optimal plan, it does not matter how quickly the query executor and storage run. Therefore, the opportunity to optimize the system from top to bottom offers students an excellent learning experience.
And that is what students see in Project 3—three hand-crafted SQL queries to optimize. Optimizing both the query plan and the executor implementation is the only way to earn a top rank on the leaderboard.
One fun fact: I did not implement any optimizations in the reference solution. I was always surprised by what our students could develop when I looked at the code that ranked at the top of the leaderboard.
Web Shell
Another crazy thing I did was bring BusTub to the browser. We made it possible using Emscripten, which compiles the C++ codebase to WASM and adds polyfills for filesystem operations. The BusTub codebase is relatively simple, and we needed to resolve only some symbol conflicts to make it work. With the BusTub web SQL shell set up, students could try the entire system before starting their projects. Besides the SQL shell, we also compiled our B+ Tree implementation to WASM. We visualized the B+ tree structure in the browser using GraphViz (thanks to Ricky Xu for the original version of the dot file generator) so that students could test their understanding and see how the B+ tree splits and merges in the browser.
SQLLogicTest
With the new query processing layer in BusTub, we introduced a new way of testing—SQLLogicTest. Originating in SQLite, this test format has been adopted by many projects, such as Apache DataFusion.
An example of this format:
query rowsort
select github_id from __mock_table_tas_2023;
----
abigalekim
arvinwu168
christopherlim98
David-Lyons
fanyuex2
Mayank-Baranwal
skyzh
yarkhinephyo
yliang412Minor Updates
Better Benchmarks
All leaderboard tests have been redesigned to ensure that students focus on architectural changes instead of design hacks. It is well known that Gradescope can be unstable for computation-heavy workloads, causing some students working on leaderboard tests to submit 50–200 times to squeeze the best result from the same piece of code. With the new benchmark suites, students are expected to implement new algorithms and make significant architectural changes to achieve better performance, rather than simply change some parameters and hope that Gradescope returns a good result. For example, in Project 1, we added latency to disk operations in the buffer pool manager benchmark. Therefore, students must find a way to issue parallel I/O requests to exploit throughput improvements.
New Project 0
Project 0 is a small project that students can finish in a few hours to become familiar with the codebase. Students use this project to gain hands-on experience with C++ and determine whether they have met the course prerequisites.
We redesigned Project 0 to help students learn C++ through an actual project. At the end of fall 2022, I suggested to some TAs that we create something called a “snapshot isolation Trie” based on copy-on-write techniques. It turned out that such copy-on-write structures are very suitable for people with a C background who are learning C++, as they involve many concepts used throughout the course:
- C++ classes and inheritance
- templates
- mutexes and concurrency-safe code
- shared pointers and RAII
- writing test cases
- copy and move constructors
Making B+ Tree Less Painful
The B+ tree project was known for its ridiculous difficulty before spring 2023. One of the main reasons students could not finish it was the misuse of buffer pool manager APIs and the incorrect concurrency control scheme.
With these challenges in mind, we redesigned the project to use PageGuard when manipulating a page from the buffer pool manager. If a user needs to access a page, they must acquire a guard from the buffer pool manager that pins the page in memory. The pin count automatically decreases when the guard goes out of scope, preventing mistakes such as forgetting to unpin a page or pinning it multiple times in one code path.
ReadPageGuard guard = bpm_->FetchPageRead(root_page->root_page_id_);
guard.As<BPlusTreePage>()->IsLeafPage(); // do some operations...
guard.Drop();For concurrency control, most students did not fully understand how to handle write operations that might create or delete the root page. Therefore, we store the pointer to the root page on a separate page called HeaderPage. This significantly simplifies concurrency control because all locks in the B+ tree index are now page locks and can be handled in the same way.
To ensure that students implement lock crabbing correctly, we added a heuristic-based detection mechanism to identify potentially incorrect implementations, and TAs manually review the code based on those heuristics. We run a purpose-built benchmark on students’ B+ tree code to see whether performance is the same in single-threaded and multi-threaded environments. If it is, something is likely wrong.
Optimizations and Optimizations
With the new query optimizer, students can make their queries more efficient by writing and applying transformation rules that generate the most efficient query plan.
Furthermore, this enables students to optimize the system as a whole. In spring 2023, there was a query with an index scan over two index columns and two filter conditions on those columns. An optimal approach would first convert the query into an index scan and then design the B+ tree iterators so that they could easily skip keys on internal nodes.
Transactions in a Correct Way
The transaction manager project has long been known for buggy and flaky test cases. From an architectural perspective, BusTub’s storage layer was not designed with concurrency control in mind, and the transaction manager was added sometime in 2018. Therefore, it needed to integrate better with the rest of the system, and some correctness bugs remained. I revisited the concurrency control implementation and fixed several bugs that might have caused correctness issues in spring 2023. I also reworked all the test cases for the storage executors. As a result, we received fewer complaints about the concurrency control implementation in storage-related query executors this semester. However, there are still improvements to make on the lock manager side.
What’s Next
The BusTub project has improved dramatically in the past year, and I still have some ideas that I want to implement. At one point, I imagined that we could have a Rust version of BusTub called RusTub, but I do not have much time to work on it, and we do not have enough TAs to support a course built on a language unfamiliar to most CMU students. Therefore, we can look into some smaller changes to the existing codebase. On the storage side, we can try an LSM index. The UCSB team adapted BusTub for their database course and asked their students to implement an LSM index, which we could adopt at CMU. On the optimizer side, we could choose different things to optimize each semester. It was join optimization in fall 2022, indexes in spring 2023, and probably sorts in fall 2023.
Besides the regular minor improvements described above, I have two big goals in mind. One is to implement a complete MVCC concurrency control scheme in BusTub. The other is to extend SQL support for correlated subqueries, window functions, and more data types. A few days ago, Runji added correlated subquery support for RisingLight (yet another educational database I maintain). I hope to understand it soon and port some optimizer work to BusTub.
Working on BusTub has been a fascinating experience for me. I had been in the database industry for almost two years as an intern before I came to CMU. I learned a great deal from those experiences by working on challenging database designs without formally taking a database course during my undergraduate studies. I started thinking, “What would I teach my past self in preparation for a database career?” I added the things I wished I had learned before starting my career to BusTub in a minimal and educational way.
Thanks for reading, and feel free to leave your comments on GitHub.