BusTub Database Internals

Implemented the core internals of a disk-based relational DBMS in C++, from buffer management and a concurrent B+Tree index to optimizer rewrite rules, the execution engine, and optimistic multi-version concurrency control, then tuned the query and index paths, placing 17th and 18th on the course performance leaderboards.

Tech stack: C++17 · Concurrent systems programming · Query optimization · Performance engineering
Operating context: Single-node disk-based relational DBMS · Four core components from storage to transactions · Performance work on the index and query paths

Architecture

Disk-based DBMS internals

Query pathAsync background I/OImplemented component

Neutral components are the course-provided scaffold. Highlighted components are the parts I implemented, and each links to its record below. Per the course academic integrity policy, solution code is not public.

Implemented components

Query execution and plan optimization

Implemented the executor suite for the batch pull-based engine, then wrote the optimizer rewrite rules and hash-join fast path that finished 17th on the course query-execution leaderboard.

Course leaderboard optimization · final rank 17

Plan rewrite

Column pruning
Projection merge (post-pruning)
Predicate pushdown
Aggregate deduplication
Always-false elimination

Join planning

Nested-loop to hash join
Build on the left child, probe with the right

Join execution

Integer key fast path, no per-probe key vector
Flat build vector with index references

Rewrite rules did most of the work. Pruning columns and collapsing projection layers ahead of the aggregation was worth roughly an order of magnitude on the heaviest query in local runs, while the execution-level changes contributed the final fraction. The graded run finished the three benchmark queries in 1000, 471, and 245 milliseconds, ranking 17th in the course.

Concurrent B+Tree index and access-path tuning

Built a concurrent B+Tree index with latch crabbing, then tuned the read and write paths by removing per-traversal buffer-pool reads, comparison cost, and global-latch contention, finishing 18th on the course throughput leaderboard.

Course leaderboard optimization · final rank 18

Root lookupheader page read on every traversalatomic root page-id cache

Search inside a pagelinear scan over up to 681 childrenbinary search

Page table lookuphash map on every page fetcharrays indexed by page and frame

Replacement bookkeepingrecorded under the one global latchshared mutex · lock-free unpin

Binary search and moving the cache-hit path off the global latch were the two largest gains, worth roughly 2x and 1.6x in local runs. The graded run reached 668,382 read and 159,371 write queries per second on the concurrent 100K-key benchmark, ranking 18th in the course.

Multi-version concurrency control

Added optimistic multi-version concurrency control to the engine, with tuple version chains and undo logs, snapshot visibility, atomic write-write conflict detection, serializable commit validation, and garbage collection.

Buffer pool and page infrastructure

Implemented the buffer pool manager, an ARC page-replacement policy, an asynchronous disk scheduler, and RAII page guards that give every upper layer safe concurrent page access.

BusTub is Carnegie Mellon's teaching database system. The SQL front end, catalog, table heap, disk manager, optimizer framework, executor interfaces, and test harness are provided by the course, and the records above are the components I implemented on that scaffold. Solution code stays private under the course academic integrity policy, so this page describes the work at the level of the public project specifications.