CMU 15-445 Fall 2021 Course Projects

When a bucket becomes full, it must be split. The splitting logic depends on the relationship between the bucket's local depth ($j$) and the table's global depth ($i$):

Case 1: Local Depth equals Global Depth ($j = i$)

In this case, only one directory entry points to the bucket. A table expansion is required:

1. Increment the global depth ($i o i+1$).
2. Double the directory size.
3. Update the directory entries to point to the original bucket and a new bucket (the 'split image').
4. Re-insert records from the original bucket into the appropriate new/old buckets.

Case 2: Local Depth is less than Global Depth ($j < i$)

Multiple directory entries point to the bucket. Only a bucket split is required (no table expansion):

1. Create a new bucket.
2. Redistribute the directory entries: half will point to the original bucket and half to the new bucket, based on the $(j+1)$-th bit.
3. Increment the local depth of both buckets ($j o j+1$).

Finding 'Sibling' Directory Entries: To find all directory entries that point to the same bucket as a given entry (with global depth $i$ and local depth $j$):

• The first entry in the group has the lower $j$ bits as 0 and all other bits as 0.
• Adjacent entries in the group differ by exactly 1 << j.
• There are exactly 1 << (i - j) entries in the group.

The BufferPoolManagerInstance is responsible for managing database pages by retrieving them from a DiskManager and writing dirty pages back to disk when required or during eviction.

Key components include:

• pages_: An array of Page slots acting as the actual container for pages read from disk.
• disk_manager_: Provides interfaces to read and write pages to disk.
• page_table_: An std::unordered_map mapping page_id_t (disk page ID) to frame_id_t (buffer pool slot ID).
• replacer_: Used to identify unpinned pages suitable for replacement.
• free_list_: A list of available frame_id_t slots.
• latch_: A std::mutex to ensure thread safety across shared data structures.

Crucial distinction: Always distinguish between page_id (the identifier on disk) and frame_id_t (the index/slot in the buffer pool memory).

class BufferPoolManagerInstance : public BufferPoolManager {
  // ...
  Page *pages_;                                     // Actual page slots
  DiskManager *disk_manager_;                       // Disk interface
  LogManager *log_manager_;                         // Log interface
  std::unordered_map<page_id_t, frame_id_t> page_table_; // Disk ID -> Frame ID mapping
  Replacer *replacer_;                               // Eviction logic
  std::list<frame_id_t> free_list_;                 // Available slots
  std::mutex latch_;                                // Thread safety
};

When a bucket becomes empty, it may be merged with its target directory entry.

Bucket Merging

A bucket can merge with its target bucket if:

1. Both the current bucket and the target bucket are empty.
2. The local depth of the current bucket and the target bucket are identical and greater than 0.

Finding the Target Entry: The target entry is found by flipping the $j$-th bit of the current entry's index. Note that because local depths can vary, the relationship is not always perfectly reversible.

After a successful merge:

• The directory entries that previously pointed to the two separate buckets are updated to point to the single merged bucket.
• The local depth of the merged bucket is decremented ($j o j-1$).

Table Shrinking

If a merge results in all directory entries having a local depth strictly less than the global depth, the table can be shrunk. In low-bit extendible hashing, shrinking is efficient: simply decrement the global depth ($i o i-1$) without needing to modify other metadata.

The Page class represents a single container in the buffer pool. It holds the actual data and metadata required for buffer management.

Key Fields:

• data_: A char array of size PAGE_SIZE containing the actual page content.
• page_id_: The ID of the page as stored in the DiskManager.
• pin_count_: The number of users (DBMS components) currently using this page. A page can only be evicted if its pin_count_ is 0.
• is_dirty_: A boolean indicating if the page has been modified since it was last read from or written to disk.
• rwlatch_: A ReaderWriterLatch for protecting the page content itself.

class Page {
 public:
  inline auto GetData() -> char * { return data_; }
  inline auto GetPageId() -> page_id_t { return page_id_; }
  inline auto GetPinCount() -> int { return pin_count_; }
  inline auto IsDirty() -> bool { return is_dirty_; }

 private:
  char data_[PAGE_SIZE]{};
  page_id_t page_id_ = INVALID_PAGE_ID;
  int pin_count_ = 0;
  bool is_dirty_ = false;
  ReaderWriterLatch rwlatch_;
};

In bustub, physical query plans are organized as a tree of nodes executed using the Iterator Model.

Each node in the query plan is represented by an AbstractExecutor class. The execution follows these rules:

1. Control Flow: The execution starts by calling Init() on the root node, and the control flow propagates down to the leaf nodes.
2. Data Retrieval: Each executor provides a Next() method. When called, it attempts to retrieve the next available tuple. If no more tuples are available, Next() returns false.
3. Context: Executors have access to an ExecutorContext, which provides global information such as the current Transaction, TransactionManager, and LockManager.
4. Plan Nodes: While the AbstractExecutor handles the logic, the AbstractPlanNode stores the specific parameters for the operation (e.g., a SeqScanPlanNode stores the table OID, while a join node stores its children and predicates).

// Conceptual flow:
executor->Init();
while (executor->Next(&tuple, &rid)) {
    // Process tuple
}

When a bucket is full, SplitInsert is called to perform a structural change. This method requires a global write lock (table_latch_.WLock()).

Key Steps:

1. Re-validation: Because there is a gap between releasing locks in Insert and acquiring the write lock in SplitInsert, you must re-fetch the directory page and re-verify if the bucket is still full.
2. Expansion Strategy:
   • If global_depth == local_depth: The directory must expand. Double the directory size, copy existing entries, increment global_depth, and then split the bucket.
   • If global_depth > local_depth: Only the bucket splits. Update the directory entries to point to a new bucket and increment the local_depth of the affected indices.
3. Rehashing: Iterate through all records in the original bucket. Re-insert them into either the original bucket or the new bucket based on their new KeyToPageId.
4. Cleanup: Unpin the original and new bucket pages and return the result of the insertion.

The LRUReplacer is a component of the Buffer Pool responsible for tracking page usage within the pool. When the buffer pool reaches capacity, the LRUReplacer identifies and evicts the Least Recently Used (LRU) pages to make room for new ones.

To achieve $O(1)$ complexity for all operations, the recommended implementation pattern is using a hash table combined with a doubly linked list:

• A doubly linked list (e.g., std::list) maintains the order of page access.
• A hash table (e.g., std::unordered_map) stores mappings from frame_id_t to the corresponding iterator in the linked list, allowing for $O(1)$ removal of elements.
• All operations must be protected by a std::mutex (e.g., data_latch_) to ensure thread safety.

class LRUReplacer : public Replacer {
 public:
  explicit LRUReplacer(size_t num_pages);
  ~LRUReplacer() override;

  bool Victim(frame_id_t *frame_id) override;
  void Pin(frame_id_t frame_id) override;
  void Unpin(frame_id_t frame_id) override;
  size_t Size() override;

 private:
  std::unordered_map<frame_id_t, std::list<frame_id_t>::iterator> data_idx_;
  std::list<frame_id_t> data_;
  std::mutex data_latch_;
};