CMU15445 Database Systems: A Completion Guide

Preface

I decided to actually sit down and do these assignments, and compete for state-of-the-art performance, mainly for two reasons. First, I didn’t seriously study databases back in college. Although I’ve accumulated some experience at work over the years, I still lacked a deep understanding of the low-level details. I had been wanting to take this legendary CMU course for a long time, but it was hard to carve out a solid block of time to finish it. Second, after more than a year of career gap time, I wanted to use this chance to see what kind of assistance today’s AI can provide for programming.

About Vibe Coding

My takeaway is that AI performs astonishingly well on real industrial problems where the context is small but the required reasoning is deep. Overall, it feels like a programming genius with limited memory, which aligns with its ability to solve all problems in the ICPC finals. But once the context becomes large and token consumption spikes, the accuracy of its conclusions drops noticeably.

In the buffer pool code, I implemented fine-grained lock striping to optimize concurrency. This part is extremely hard to get right, involving complex nested locks, double-checking, and try-lock logic. With AI assistance, I was basically able to catch all concurrency bugs. In the B+ tree work, there is a lot of tedious boundary handling and offset calculation; with AI help, I could implement and verify correctness smoothly, saving a lot of debugging time.

One particularly interesting thing is: if you suspect some piece of code has a certain “bad smell” and you have a vague idea, asking AI directly almost always works. It can understand the issue and construct a suitable example that triggers a race condition, helping you quickly confirm or refute your hypothesis. This suggests AI genuinely understands multithreaded programming techniques and can apply them creatively in real scenarios. That said, current AI still hasn’t escaped the “people-pleasing” issue—if you are debugging in the completely wrong direction, AI won’t firmly tell you “this part of the code is fine”; instead it will try its best to fabricate something.

Coding Advice

Good coding style and interface design help reduce cognitive load and reduce the chance of errors.
Don’t do fancy tricks. If your code has signs of “I think this might work,” it usually means you’ve stepped into a pitfall somewhere.
For concurrency race conditions, if some part of the code feels “smelly,” you can ask AI directly instead of guessing repeatedly.
In multithreaded scenarios, think through object lifetimes to avoid strange issues in destructors.
On a MacBook Air, benchmark behavior is somewhat odd and can only be used as a reference; for serious performance data, look at the results on gradescope.

Overall Impressions

The overall project framework is very elegant, especially the design of PageGuard and TupleMeta, making it hard to run into severe deadlocks or memory-corruption bugs.
Benchmark validation seems weak. There are some obvious out-of-range hacks on the leaderboard, which makes rankings meaningless. Also, the final leaderboard task even had a bug that prevented optimizations from taking effect—for example, when implementing real-time GC in assignment 4 (this issue has been fixed).
Unit tests across assignments are not fully compatible, so you need some tricky workarounds. This is not very friendly if you later want to revisit and optimize for benchmarks.

About Debugging

First, set up a VSCode-based debugging environment. This can save a lot of time and energy later. To work with CMake Tools on macOS, launch.json looks roughly like this:

{
  "version": "0.2.0",
  "configurations": [
    {
      "name": "(lldb) Launch",
      "type": "cppdbg",
      "request": "launch",
      "preLaunchTask": "CMake: build",
      "program": "${command:cmake.launchTargetPath}",
      "cwd": "${workspaceFolder}/build",
      "args": [],
      "stopAtEntry": false,
      "environment": [],
      "externalConsole": true,
      "MIMode": "lldb",
    },
  ]
}

During the implementation, I rarely ran into deadlocks that were hard to debug. An efficient method is to run the program until it deadlocks, then pause the debugger and inspect each thread’s call stack to see whether there is lock reentrancy. Usually the bug is very obvious.

For runtime exceptions, another approach is to just run under the debugger. It will automatically pause at the throw site. Then inspect the call stack and trace variables across contexts to reconstruct what went wrong.

A Powerful Performance Tool: Flame Graphs

Flame graphs are an effective tool for performance analysis, especially when the benchmarking code is already provided. On macOS, the following script uses dtrace to collect and visualize benchmark performance for assignment 1:

sudo echo
./bin/bustub-bpm-bench --duration 1000 --latency 1 &
PID=$!
sudo dtrace -x ustackframes=100 \
  -n 'profile-2000 /pid == $target/ { @[ustack()] = count(); }' \
  -p $PID > out.stacks
stackcollapse.pl out.stacks > out.folded
flamegraph.pl out.folded > out.svg
open out.svg

Right-click and open the image below in a new tab; you can view it interactively in Chrome. From the flame graph, we can see that the main bottleneck for this test case is disk IO. So you can read the official IO simulation logic and apply targeted optimizations.

Flame

Buffer Pool Manager

Leaderboard score first:

The top few are clearly using some kind of hack; everyone else is pretty similar. This score is decent.

The LRU-K Algorithm

The official guide starts by digging a pit for you: the real complexity of LRU-K is O(logN), which is very costly later when running the B+ tree benchmark, so you will eventually need to rewrite it into an O(1) implementation. A simple approach is to split into two LRU queues based on whether the page has reached K accesses. Then you can add a variable like LRUKReplacer::enable_fast_mode_ to switch between the two algorithms, which also helps keep logic consistent.

Page IO Optimizations

Clearly we shouldn’t do IO while holding the global lock. Instead, we should hand IO requests to a thread pool asynchronously; otherwise performance will be poor. This requires thinking through some details:

When flushing a dirty frame, do we need to keep occupying that frame the whole time?
- Not necessarily. We can copy its data into a buffer, and the frame is immediately available again. Then use a thread pool to write the buffer asynchronously to the corresponding page_id on disk.
Then the question becomes: when we try to load a page_id and find it is currently being asynchronously written to disk, what should we do?
- Use a condition variable to suspend the calling thread until the IO operation for that page_id completes; only then can we legally read that page.

Thus we can abstract the following interface to manage IO state per page_id:

// class BufferPoolManager....
std::unordered_set<page_id_t> io_pages_;
std::condition_variable io_cv_;

void BufferPoolManager::WaitForPageReady(std::unique_lock<std::mutex> &lck, page_id_t page_id) {
  io_cv_.wait(lck, [page_id, this]() { return io_pages_.count(page_id) == 0; });
}

void BufferPoolManager::MarkPageBusy(page_id_t page_id) { io_pages_.insert(page_id); }

void BufferPoolManager::MarkPageReady(page_id_t page_id) {
  BUSTUB_ENSURE(io_pages_.count(page_id), "page_id not in IO status");
  io_pages_.erase(page_id);
  io_cv_.notify_all();
}

A new problem: if we attempt ReadPage and the system has neither a free frame nor any evictable frame, what should we do?

The answer is to also wait on a condition variable until a new frame is returned to the system—but note: if you implement it directly like that, the EvictableTest will fail, because it expects the scenario where Evict() fails and must return nullopt. One solution that satisfies both is to slightly adjust the interface, for example:

// class BufferPoolManager....
CheckedReadPage(page_id_t page_id, AccessType access_type, bool wait_for_page=false)

auto BasicBufferPoolManager::ReadPage(page_id_t page_id, AccessType access_type) -> ReadPageGuard {
  auto guard_opt = CheckedReadPage(page_id, access_type, true);
  if (!guard_opt.has_value()) {
    fmt::println(stderr, "\n`CheckedReadPage` failed to bring in page {}\n", page_id);
    std::abort();
  }
  return std::move(guard_opt).value();
}

// when allocating a new frame...
if (wait_for_page) {
  frames_cv_->wait_for(lock, std::chrono::seconds(3),
                       [this]() { return !free_frames_.empty() || replacer_->Size() > 0; });
}

This distinguishes the semantics of CheckedReadPage and ReadPage: when calling the former, you can choose whether to wait for an available frame and it is allowed to return empty, satisfying unit tests; while the latter expects to always obtain a frame and allows the calling thread to block until some frame becomes available.

The last optimization idea is about disk IO. In DiskManagerUnlimitedMemory, you can see the simulated IO latency: consecutive disk IO, or IO within the same block, has lower latency. We can add some manual statistics to compute what fraction of IO operations got “penalized” with high latency. One approach is: for each thread in the thread pool, have it listen to a consecutive range of page_id values (e.g., 16 per group), batching requests so that IO is as contiguous as possible before calling the actual disk operation. This can improve the contiguous-hit rate from ~50% under purely random access to ~75%.

Lock Striping

This part is not in the official guide; it is my own attempt at performance optimization. I strongly do not recommend doing this optimization. Debugging is hell, and it does not provide much benefit for the leaderboard workload. Here is why lock striping is so hard.

1. Why Lock Striping Is Needed

Lock striping essentially splits the single big lock bpm_latch_ that used to protect all resources into finer-grained locks, reducing lock contention under high load. If all buffer pool operations use one global lock, threads calling ReadPage/WritePage will frequently block on it, leading to low throughput. By partitioning all pages by page_id % NUM_PARTITIONS, each partition is locked independently, so operations on different partitions can proceed concurrently. This greatly reduces contention and better utilizes multiple cores.

// class BufferPoolManager...
constexpr static size_t NUM_PARTITIONS = 32;
std::array<std::unordered_map<page_id_t, frame_id_t>, NUM_PARTITIONS> page_table_;
std::array<std::mutex, NUM_PARTITIONS> latches_;
// data structure for pages that pending IO
std::array<std::unordered_set<page_id_t>, NUM_PARTITIONS> io_pages_;
std::array<std::condition_variable, NUM_PARTITIONS> io_cv_;

2. Why Local Locks Must Cooperate With a Global Lock

Some data structures (like page_table_, io_pages_) only affect a single partition, so local locks are sufficient. But resources like free_frames_ and replacer_ are global—frames are shared by the whole system—so they must be protected by a global lock. When an operation involves both local and global resources, you need to acquire the local lock first and then the global lock to ensure consistency and avoid deadlocks. This maintains high concurrency while safely managing global state, but makes implementation very challenging.

For example, when we check page_table_ and see that page_id is already mapped to some frame, we need to pin that frame—this is actually very complex. With only the local lock held, we cannot prevent other threads from concurrently evicting (Evict()) and reallocating that frame, because the frame lifecycle is governed by global logic. We must upgrade to the global lock and double-check the frame’s page_id_ and pin_count_ to ensure the frame is still mapped to the current page and pin_count_ is still 0; only then is it safe to pin the frame. Without global protection, bugs like the following can occur:

Threads A and B both see pin_count_==0. A is about to pin, while B holds the global lock, Evicts the frame and assigns it to a new page. Then A increments pin_count_++, incorrectly pinning the frame for the new page, corrupting data.
Or before A pins, B already recycles the frame and puts it into the free list, leading to two pages sharing one frame later.

3. Why CAS Is Needed

For incrementing the pin count, beyond lock upgrading, there is an extremely subtle race condition. If we observe pin_count_>0, meaning the frame is already pinned, can we just do pin_count_++ and return the FrameHeader? No. Although atomic increment itself is safe and won’t produce a wrong count, the condition check and the increment are not atomic together. A race can happen: in the gap, another thread may have turned pin_count_ back to 0, so the previous condition no longer holds and the correct action would differ. Therefore we must use CAS to make the condition check and count increment atomic; otherwise we retry:

while (true) {
  auto frame_hdr = GetMappedFrameLocked(page_id);
  if (frame_hdr) {
    auto old_pin_count = frame_hdr->pin_count_.load();
    if (old_pin_count > 0) {
      if (frame_hdr->pin_count_.compare_exchange_strong(old_pin_count, old_pin_count + 1)) {
        // ...
        return frame_hdr;
      }
    } else {
      std::scoped_lock global(*bpm_latch_);
      if (frame_hdr->page_id_ == page_id && frame_hdr->pin_count_ == 0) {
        replacer_->SetEvictable(frame_hdr->frame_id_, false);
        frame_hdr->pin_count_++;
        // ...
        return frame_hdr;
      }
    }
  } else {
    break;
  }
}

A question worth thinking about: why does doing CAS here not lead to incorrectness due to the ABA problem?

4. Why try-lock Is Needed

Normally, lock acquisition must follow a consistent local-then-global order, otherwise deadlocks occur. But in special cases, such as page eviction, we must first hold the global lock and use Evict() to obtain a FrameHeader, then acquire the local lock for that frame’s corresponding page_id to clear the existing mapping. In this case we must use try-lock rather than blocking locks, because if we can’t acquire the local lock, we cannot block; instead we must immediately return the frame and try to get a new one. Similarly, if the page_id of that frame is currently in an IO state, we must also return it.

5. Why Double-Checks Are Needed Everywhere

Double-checks prevent races between checking a condition and acquiring a lock: after you check but before you acquire the lock, other threads may have updated state. Only double-checking ensures your operation is based on the latest correct state and avoids concurrency holes.

For example, when allocating a new frame for a page_id, we don’t need the partition lock. We acquire the lock only when updating the mapping in page_table_. At that point, we might discover another thread has already mapped the page, so we must return the newly obtained frame and restart; otherwise we would overwrite the existing page<=>frame mapping and corrupt data.

Similarly, when destructing PageGuard, we first check whether pin_count_ becomes 0, but after upgrading to the global lock we still need to check again to ensure no other thread pinned the page again:

if (--frame_->pin_count_ == 0) {
  std::scoped_lock global(*bpm_latch_);
  if (frame_->pin_count_ == 0) {
    replacer_->SetEvictable(frame_->frame_id_, true);
    // ...
  }
}

In DeletePage, we must acquire the partition lock first. If we find page_id is mapped to a frame and pin_count_==0, then any subsequent operations on the frame must be protected by the global lock, and after upgrading we also need a double-check:

auto BufferPoolManager::DeletePage(page_id_t page_id) -> bool {
  auto frame_hdr = ...;
  if (frame_hdr->pin_count_ > 0) return false;
  std::scoped_lock global(*bpm_latch_);
  BUSTUB_ENSURE(frame_hdr->page_id_ == page_id, "Unexpected: frame mapped to different page_id");
  if (frame_hdr->pin_count_ > 0) return false;
  if (frame_hdr->is_dirty_) {
    // async flush data to disk...
  }
  // ...
}

Because at the moment of checking, the frame is completely unpinned, two scenarios are possible:

In the gap before acquiring the global lock, the frame may already have been Evict()ed, but it won’t be reassigned to another page because the partition for the current page_id is still locked, so this is safe.
Or at the same instant, a concurrent thread calls WritePage and pins the frame again. When we acquire the global lock and double-check and find pin_count_>0, we should immediately return false; otherwise a race occurs: the frame’s data is being flushed to disk while being concurrently updated, corrupting data.

Database Index

Leaderboard score first:

The key point for the B+ tree is interface design. A good design greatly reduces coding cognitive load and helps manage loop invariants, making correctness more apparent. It’s best to write the interfaces first, sort out the algorithm, and then fill in details. This part is quite suitable for vibe coding, because many sections are strongly symmetric and AI completion accuracy is fairly high.

Interface Design

Here are the helper function interfaces I used for my B+ tree:

class BPlusTree {
private:
  auto AcquireSiblingPage(Context &ctx, int choose) -> std::optional<WritePageGuard>;
  auto DeleteNodeFromParent(Context &ctx, WritePageGuard sibling_guard_to_del, int choose) -> void;
  auto FindLeafPageOptimistic(const KeyType &key, bool) -> WritePageGuard;
  auto FindLeafPage(const std::optional<KeyType> &key) -> ReadPageGuard;
  auto FindLeafPage(Context &ctx, const KeyType &key, std::function<bool(const InternalPage *)>, bool)
      -> WritePageGuard;
  auto BorrowFromRight(InternalPage *f, InternalPage *i, InternalPage *right, int offset) -> void;
  auto BorrowFromLeft(InternalPage *f, InternalPage *i, InternalPage *left, int offset) -> void;
  auto MergeIntoLeft(InternalPage *f, InternalPage *i, InternalPage *left, int offset) -> void;
  auto MergeFromRight(InternalPage *f, InternalPage *i, InternalPage *right, int offset) -> void;
  // ...
};

class BPlusTreeInternalPage : public BPlusTreePage {
public:
  std::pair<page_id_t, int> FindChildPage(const KeyType &key, const KeyComparator &less) const;
  void Insert(const KeyType &key, page_id_t page_id, const KeyComparator &comp);
  void InsertAt(int offset, const KeyType &key, page_id_t page_id);
  KeyType SplitInto(BPlusTreeInternalPage *other);
  page_id_t EraseAt(int offset);
  // ...
};
class BPlusTreeLeafPage : public BPlusTreePage {
public:
  auto KeyAt(int index) const -> const KeyType &;
  auto ValueAt(int index) const -> const ValueType &;
  auto Find(const KeyType &key, const KeyComparator &comp, int *offset_result) const -> std::optional<ValueType>;
  void Insert(const KeyType &key, const ValueType &value, const KeyComparator &comp);
  void InsertAt(int offset, const KeyType &key, const ValueType &value);
  void Erase(const KeyType &key, const KeyComparator &comp);
  void EraseAt(int offset);
  void SplitInto(BPlusTreeLeafPage *other);
  void AppendInto(BPlusTreeLeafPage *other);
  // ...
};

For BorrowFromRight, BorrowFromLeft, MergeIntoLeft, MergeFromRight, you need to think through details. It helps to construct a concrete example and write it into comments, then implement against it. For example:

INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::MergeIntoLeft(InternalPage *f, InternalPage *i, InternalPage *left, int offset) -> void {
  // Consider the following B+ tree structure:
  // Father:
  //
  //     FK1 [FK2] FK3 FK4
  // FP0 FP1 (FP2) FP3 FP4
  //      |   |
  //      L   I
  //
  // Left:
  //
  //     LK1 LK2 LK3 [FK2] IK1 IK2 IK3
  // LP0 LP1 LP2 LP3 [IP0] IP1 IP2 IP3
  //
  // Intermediate:
  //
  //       IK1 IK2 IK3
  // [IP0] IP1 IP2 IP3
  // This is to make sure: FK2 <= Key < IK1 should be routed to IP0
  left->InsertAt(left->GetSize(), f->KeyAt(offset), i->ValueAt(0));
  for (int j = 1; j < i->GetSize(); j++) {
    left->InsertAt(left->GetSize(), i->KeyAt(j), i->ValueAt(j));
  }
};

Leaderboard Optimization

For performance, implementing optimistic locking (FindLeafPageOptimistic) per the official guide is fairly straightforward, but tombstone deletion is a tricky strategy. After suffering through lock striping above, I decided not to step into that pit.

The benchmark workload is relatively single-purpose: it’s basically a slightly modified linear insert. So you only need a simple optimization on leaf splits: keep the new node as empty as possible, so sequential inserts trigger fewer splits:

INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_LEAF_PAGE_TYPE::SplitInto(BPlusTreeLeafPage *other) {
  other->Init();
  auto remain = GetSize() / 2 + GetSize() % 2;
  // note: this is an allowed dedicated optimization for B+ tree sequential insert performance
  if (this->GetMaxSize() > 100) {
    remain = GetSize() * 0.9;
  }
  for (int i = remain; i < GetSize(); i++) {
    other->key_array_[i - remain] = key_array_[i];
    other->rid_array_[i - remain] = rid_array_[i];
  }
  other->SetSize(GetSize() - remain);
  this->SetSize(remain);
}

Finally, use flame graphs again to find hot spots. I found locking inside LRU-K is also a small bottleneck. Replacing std::mutex with a handwritten spinlock can yield another ~10% improvement.

class Spinlock {
 private:
  std::atomic_flag flag = ATOMIC_FLAG_INIT;
 public:
  void lock() noexcept {
    while (flag.test_and_set(std::memory_order_acquire)) {
      // do not yield here for better performance
      // std::this_thread::yield();
    }
  }
  void unlock() noexcept { flag.clear(std::memory_order_release); }
  bool try_lock() noexcept { return !flag.test_and_set(std::memory_order_acquire); }
  Spinlock() = default;
  Spinlock(const Spinlock &) = delete;
  Spinlock &operator=(const Spinlock &) = delete;
};

Query Execution

Same routine: leaderboard score first:

In this assignment, implementing query executors is not very exciting. You basically need to understand the abstraction of a database “row”: Schema, Column, Tuple, Value, and how the AbstractExecutor framework works, then implement the algorithms taught in class. The most complex part is External Merge Sort, but there are no big pitfalls.

However, the two optimization passes in the leaderboard task are the real highlight. It’s not hard if you only handle benchmark-specific special cases, but writing a rigorous and general solution takes a lot of effort.

Semantics of `Init()` and `Next()`

The executor constructor and Init() are easy to confuse. The former initializes the object and is called only once; but Init() may be called multiple times by its parent. For example, NestedLoopJoinExecutor must traverse the right table for each left tuple, so it must call right_executor_->Init() each time to reset internal state and restart reading.

Optimizing SeqScan to IndexScan

First understand the overall Optimizer workflow: it does not modify the original expression tree. If an optimization condition is met, it directly creates and returns a new AbstractPlanNodeRef, while the old subtree is cleaned up automatically by RAII.

For this pass, the logic is simple: recursively traverse the expression tree, ensure all comparisons are “equality lookups,” i.e., in the form Column=ConstantValue, and extract the columns and constants from all comparison expressions to build an IndexScanPlanNode. Note that because our B+ tree only supports point lookups, it cannot support composite indexes; in this pass we can only simplify by assuming the query is on a single column.

Optimizing NestedLoopJoin to HashJoin

Very similar to the previous pass: traverse the expression tree, check that it is entirely connected by AND, and ensure the ColumnValue on one side of each equality must all come from the same table. For example, the following SQL cannot be optimized into HashJoin:

bustub> EXPLAIN (o) SELECT * FROM test_1 t1, test_2 t2 WHERE t1.colB + t2.colA = t2.colC;
=== OPTIMIZER ===
NestedLoopJoin { type=Inner, predicate=((#0.1+#1.0)=#1.2) }
  SeqScan { table=test_1 }
  SeqScan { table=test_2 }

External Merge Sort

This is another design-pattern-focused task. The key is to put all temporary pages into MergeSortRun for management: call MergeSortRun::Add(const Tuple& tuple) on writes, and use Iterator to handle traversal and reads (think carefully when implementing operator++()). This avoids managing messy boundary computations and page lifetimes inside the merge sort algorithm.

Although the official guide only requires a simple 2-way merge, implementing a general K-way merge is not hard; it’s worth doing it properly in one go.

Also, think through where WritePageGuard and ReadPageGuard should be managed. Given merge sort’s read/write patterns, there is a small optimization: try to reuse Read/WritePageGuard to reduce unnecessary BufferPoolManager overhead (since it involves locking). Specifically:

The Iterator’s ReadPageGuard locks only the currently accessed page; when moving to the next page, lazily switch the guard.
Each MergeSortRun::Add lazily calls bpm_->WritePage only when creating a new page or switching pages, avoiding acquiring/releasing page locks for every inserted Tuple.

Query Optimization 1: Predicate Extraction and Pushdown

Consider the following SQL:

SELECT * FROM t4, t5, t6
  WHERE (t4.x = t5.x) AND (t5.y = t6.y) AND (t4.y >= 1000000)
    AND (t4.y < 1500000) AND (t6.x >= 100000) AND (t6.x < 150000);

The idea looks intuitive: push equality joins in WHERE down into HashJoin children, and put range filters into the corresponding SeqScan. But writing a general recursive implementation that can handle joins of an arbitrary number of tables is much more complicated; when I look back at my own code, it’s hard to understand. There are too many boundary details and no great design pattern to simplify it.

In fact, this “manual recursive traversal + type branching” style in bustub is more about teaching and demonstrating principles. In real engineering, you would introduce higher-level abstractions. Industrial optimizers use “rule engines + pattern matching + unified abstractions + auxiliary tools,” allowing developers to describe “pattern-rewrite” rules declaratively, making optimization pass development more declarative, modular, composable, and maintainable—far more efficient and robust than handwritten recursion and type checks.

For this pass, the specific approach is:

Predicate classification and separation: traverse the incoming predicate list and decide which predicates can be used as equality join conditions for Hash Join (e.g., t1.a = t2.b), then store them separately.
Push predicates down to scan nodes first: for each child plan of the NLJ, if it is SeqScan or MockScan, push down applicable predicates into the scan node to improve filtering efficiency. In this process, note that you must recursively fix column indexes inside predicate expressions—setting them directly to 0 is sufficient.
Then recursively process nested NLJs: for nodes in the child plan list that are still NestedLoopJoin, first recursively adjust column indexes in predicate expressions so they match the left/right table structures of the child NLJ, then recursively call yourself.
Optimization termination condition: if there are remaining predicates that cannot be pushed down, it means the optimization cannot be fully applied; return nullptr directly to indicate rewrite failure.
After finishing children, create and return a new NLJ node:
- If there are available Hash Join predicates, extract join keys from left and right and rewrite into HashJoinPlanNode to improve join performance.
- If there are no available Hash Join predicates, build a new NLJ node with predicate set to constant true (i.e., unconditional join).

With this, the optimizer can handle more complex cases:

bustub> EXPLAIN (o) SELECT * FROM t4, t5, t6, t7, t8
...   WHERE (t4.x + t4.y = t5.x + 1) AND (t5.y = t6.y) AND (t5.x = t7.y) AND (t4.x = t7.x) AND (t8.y = 1)
...   AND (t4.y >= 1000000) AND (t4.y < 1500000) AND (t6.x >= 100000) AND (t6.x < 150000) AND (t7.y < 100);
=== OPTIMIZER ===
NestedLoopJoin { type=Inner, predicate=true }
  HashJoin { type=Inner, left_key=["#0.2", "#0.0"], right_key=["#1.1", "#1.0"] }
    HashJoin { type=Inner, left_key=["#0.3"], right_key=["#1.1"] }
      HashJoin { type=Inner, left_key=["(#0.0+#0.1)"], right_key=["(#1.0+1)"] }
        SeqScan { table=t4, filter=((#0.1>=1000000)and(#0.1<1500000)) }
        SeqScan { table=t5 }
      SeqScan { table=t6, filter=((#0.0>=100000)and(#0.0<150000)) }
    SeqScan { table=t7, filter=(#0.1<100) }
  SeqScan { table=t8, filter=(#0.1=1) }

Query Optimization 2: Column Pruning + Common Expression Elimination

Consider the following SQL:

SELECT v, d1, d2 FROM (
  SELECT v,
         MAX(v1) AS d1, MIN(v1), MAX(v2), MIN(v2),
         MAX(v1) + MIN(v1), MAX(v2) + MIN(v2),
         MAX(v1) + MAX(v1) + MAX(v2) AS d2
    FROM t7 LEFT JOIN (SELECT v4 FROM t8 WHERE 1 == 2) ON v < v4
    GROUP BY v
);

We can target a specific recursive optimization for the pattern where the current node is a Projection, its child is also a Projection, and the child Projection’s child is an Aggregation. The approach is:

1st Pass: Prune the Projection to Keep Only Necessary Columns

Collect the column indexes needed by the top Projection: which output columns of the child Projection are used by the parent.
Use those indexes to prune the child Projection expressions, keeping only necessary columns.
Remember to prune the child Projection output Schema as well.

2nd Pass: Prune the Aggregation to Keep Only Necessary Aggregates

Similar to the previous pass: determine which output columns from the child Aggregation are still needed by the child Projection.
Keep only those Aggregation expressions and types, record their indexes, and prune the unused parts.
Note that the first columns of AggregationPlanNode’s output Schema are the GroupBy results, so handle that offset specially.

3rd Pass: Eliminate Duplicate Aggregation Expressions

Check whether the Aggregation expression list contains duplicates (e.g., SUM(x), SUM(x)), and keep only one to avoid redundant computation.
Maintain a mapping from original expression index to new index.
Use the mapping to fix column index references inside the parent Projection expressions.
Rebuild the Aggregation node output Schema, keeping only columns corresponding to the used aggregate expressions.

Finally, rebuild the Projection → Projection → Aggregation structure using the pruned Aggregation expression list and new Schema, and return the final ProjectionPlanNode.

A Complex Example

After implementing the above logic, you can cleanly simplify a very complex and redundant query like this:

bustub> explain (o) select v, d1 + d2, d3 + d4 - d5 from (
...     select
...         v, max(v1) as d1, min(v2) as d2,
...         max(v1) + min(v2) as d3,
...         max(v1) + max(v2) + min(v2) as d4,
...         max(v1 + v2 + v4) as d5,
...         min(v1), max(v2), min(v2), max(v1) + min(v1), max(v2) + min(v2), min(v1), max(v2), min(v2), max(v1) + min(v1), max(v2) + min(v2), min(v1), max(v2), min(v2), max(v1) + min(v1), max(v2) + min(v2), min(v1), max(v2), min(v2), max(v1) + min(v1), max(v2) + min(v2), min(v1), max(v2), min(v2), max(v1) + min(v1), max(v2) + min(v2), min(v1), max(v2), min(v2), max(v1) + min(v1), max(v2) + min(v2), min(v1), max(v2), min(v2), max(v1) + min(v1), max(v2) + min(v2), min(v1), max(v2), min(v2), max(v1) + min(v1), max(v2) + min(v2), min(v1), max(v2), min(v2), max(v1) + min(v1), max(v2) + min(v2)
...     from __mock_t7 left join (select v4 from __mock_t8 where 1 == 2) on v < v4 group by v
... );
=== OPTIMIZER ===
Projection { exprs=["#0.0", "(#0.1+#0.2)", "((#0.3+#0.4)-#0.5)"] }
  Projection { exprs=["#0.0", "#0.1", "#0.2", "(#0.1+#0.2)", "((#0.1+#0.3)+#0.2)", "#0.4"] }
    Agg { types=["max", "min", "max", "max"], aggregates=["#0.1", "#0.2", "#0.2", "((#0.1+#0.2)+#0.3)"], group_by=["#0.0"] }
      NestedLoopJoin { type=Left, predicate=(#0.0<#1.0) }
        MockScan { table=__mock_t7 }
        Values { rows=0 }

You can see that at the Aggregation layer, only a few necessary aggregate results are computed, and then the upper Projection recombines them.

Concurrency Control

Final leaderboard score:

Notes before starting:

When coding, try to encapsulate and reuse similar logic as much as possible to reduce later workload. Specifically, Tuple Update and Delete are referenced in many places, so it’s best to put them into common utilities early.
Always remember to correctly maintain the write set; this avoids having to come back and fix bugs when implementing serializable isolation later.

Watermark

Ignore the O(1) algorithm mentioned in the official guide; it refers to average complexity and isn’t very meaningful. Implementing it with std::set with worst-case O(logN) is sufficient.

MVCC and the Version Chain

First, deeply understand the semantics of UndoLog: if you apply this log, you can revert the state to log.ts_, i.e., read the Tuple at that historical timestamp. In CollectUndoLogs(), for a given read_ts, you only need to find the first log satisfying log.ts_<=read_ts. If none of the UndoLogs on the version chain satisfy this condition, then at read_ts the Tuple did not exist. Also make sure you understand other conditions that indicate a Tuple does not exist.

If you read a temporary timestamp from TupleMeta (ts >= TXN_START_ID), this special value effectively blocks all concurrent updates to the same Tuple, ensuring thread safety. This is also why an UndoLog cannot contain a temporary timestamp: other threads/transactions abort automatically upon seeing it, so they never get a chance to modify the Tuple and append a new UndoLog into the version chain.

Understand why you need to implement GenerateNewUndoLog() and GenerateUpdatedUndoLog() separately. If within the same transaction you modify the same Tuple multiple times, you should not write a new UndoLog into the version chain. The invariant is: each transaction produces only one new UndoLog per Tuple. This saves space and helps correctness of other features.

Concurrency Safety Under CAS Semantics

When updating/deleting a Tuple, we need to call UpdateTupleAndUndoLink() to atomically update TupleMeta, Tuple, and UndoLink. But this “atomicity” is based on CAS semantics, so we must pass in a check function. Essentially it is a conflict detector under “optimistic concurrency control” to ensure the Tuple you want to modify has not been changed by another transaction between your read and write. Only if the check passes can you safely perform the physical update; otherwise you must abort the current transaction.

The check function is very simple:

auto check_func = [&meta](const TupleMeta &cur_meta, const Tuple &tuple, RID rid, std::optional<UndoLink>) {
  return meta == cur_meta;
};

This is based on two considerations:

Obviously ts_ cannot change between reading and writing back; otherwise another transaction definitely modified the Tuple.
For INSERT, it may insert into a Tuple that was soft-deleted, so you must ensure is_deleted_ also hasn’t changed.

Updating the Primary Key

First, understand that once a RID is inserted into the B+ tree, it cannot be updated; this is the source of concurrency safety. Because UndoLink is uniquely associated with a RID, even if we look up a key that is currently deleted, as long as it once existed in the tree, we must be able to access its full history to satisfy MVCC semantics. In industrial implementations, if all historical versions for a RID are “expired” (invisible to all active transactions and no longer reachable by any snapshot or rollback), then it can be safely physically removed from the B+ tree index. Bustub simplifies this and does not care about that space waste.

For primary key updates, we have to implement it as: soft-delete the old key via TupleMeta, then insert the new key. If the B+ tree cannot find a RID for the new key, simply insert a new Tuple into TableHeap, then insert the new RID into the B+ tree. A pitfall here is that we must correctly abort SQL like UPDATE key SET key = 1: it is a write-write conflict, so think through how to detect it.

There is a small optimization: if we detect the primary key does not change before/after the Tuple update, then directly write the new Tuple into the same RID without the delete-and-reinsert logic.

Special Handling for Delete Executor

When implementing DELETE, the official guide mentions that if a Tuple goes through the special sequence INSERT => UPDATE => DELETE, you need to set its meta.ts_ to zero, making it invisible outside the transaction. This is because when implementing Serializable Verification later, you need to traverse the transaction’s write_set and check for read-write conflicts, and you must ignore this “externally invisible” Tuple.

However, here you can ignore this tip initially, to avoid implementing it in the wrong place and then refactoring repeatedly later. In the end, you can put it into the common tuple-delete logic.

Real-Time GC and ABORT Logic

When implementing Abort, the official guide provides two approaches. The second seems more GC-friendly, but if you want real-time GC, both have the same subtle concurrency issue, and you end up having to degrade to: GC can only run when there are no running transactions in the entire system.

First, without GC, Index Scan and Abort logic are concurrency-safe: CollectUndoLogs() will never access a dangling UndoLink. But once GC is introduced, if Abort removes the undo log from the version chain, there is a race condition:

In Index Scan, you may read a temporary timestamp (ts >= TXN_START_ID) and an undo link pointing into the transaction being aborted, so it needs to traverse the version chain to find a visible Tuple.
The GC thread may read the updated tuple meta after Abort has finished updating it. When traversing the version chain, it does not see any reference to the current transaction, and will think it can GC.
As a result, the aborted transaction’s undo logs are cleaned up, while Index Scan still holds an invalid undo link, causing errors.

What if we take the other (uglier) implementation and keep the aborted transaction’s undo logs in the version chain—would that prevent GC from reclaiming them incorrectly? Unfortunately, it still fails in another case: when GC checks, if it reads watermark >= meta.ts_, it triggers cleanup directly without traversing the version chain. But Index Scan is still reading a temporary timestamp and must access the undo log, leading to a dangling pointer.

Fundamentally, this is caused by reading tuple meta and subsequent operations not being atomic, leading to inconsistency across threads. The correct solution is to add atomic reference counting to undo logs to prevent dangling pointers, but bustub’s code framework does not support such changes.

Serializable Verification

Since MVCC already provides snapshot-level isolation, this part is just implementing an Optimistic Concurrency Control (OCC) transaction validation to avoid “write skew abnormalities.” You can translate the algorithm description from the official guide into code. Try to reuse ReconstructTuple() logic, and watch out for a small pitfall: what does it mean if you cannot find an UndoLog for a Tuple? How should you handle it?

Pessimistic Concurrency Control

In essence, PCC performs a check before writing/modifying/deleting a Tuple: whether the Tuple you want to operate on matches the read predicate of any running transaction. If yes, abort early to avoid wasting time continuing execution.

A crude and fast implementation is to store these predicates directly in TransactionManager, and evaluate them by iterating through all predicates on each query. This is obviously inefficient; industrial systems use more complex data structures to optimize the lookup.

PCC is actually simpler than OCC in the official guide, but after adding it you may fail unit tests, because some cases require abort only at Commit. So how do we automatically switch between pessimistic and optimistic control? We can track abort rate in real time: at the entry of the PCC check function, if the conflict rate is low, skip the check and let OCC catch issues at the end; if the conflict rate is high, enable the pessimistic strategy—for example when running leaderboard benchmark 2.

(End)

PS: If you have the patience to read up to here and are interested in my implementation, you can contact me via email to request the code. For reference and learning only; please do not publish it publicly.