Storage Engine

The storage engine persists relational data, covering heap files, indexes, page formats, and the handles exposed to execution. Understanding this layer is key to reasoning about performance, MVCC, and recovery.

Responsibilities

Manage TableHeap insert/delete/update paths and their MVCC metadata.
Maintain indexes (see the Index module for details).
Expose the StorageEngine trait so execution can fetch TableHandle / IndexHandle instances per table.
Provide TupleStream so sequential and index scans share a unified interface.

Directory Layout

Path	Purpose	Key Types
`engine.rs`	Default engine plus handle definitions.	`StorageEngine`, `TableHandle`, `TupleStream`
`table_heap/`	Heap storage + MVCC logic.	`TableHeap`, `MvccHeap`
`index/`	B+Tree implementation.	`BPlusTreeIndex`
`page/`	Page, RID, tuple metadata.	`Page`, `RecordId`, `TupleMeta`
`tuple/`	Row encoding and projection helpers.	`Tuple`
`disk_manager.rs`	File layout and page I/O.	`DiskManager`
`disk_scheduler.rs`	`io_uring`-backed async scheduler.	`DiskScheduler`

Core Abstractions

StorageEngine Trait

#![allow(unused)]
fn main() {
pub trait StorageEngine {
    fn table(&self, catalog: &Catalog, table: &TableReference)
        -> QuillSQLResult<Arc<dyn TableHandle>>;
    fn indexes(&self, catalog: &Catalog, table: &TableReference)
        -> QuillSQLResult<Vec<Arc<dyn IndexHandle>>>;
}
}

The default implementation wraps the row-oriented heap + B+Tree combo, but the trait is ready for column stores, remote storage, or async engines.

TableHandle

Offers full_scan(), insert, delete, update, and prepare_row_for_write. MVCC, undo, and locking concerns live here so execution operators only describe intent. Every delete/update now receives the table’s index handles so HeapTableHandle can delete or re-insert keys in tandem with heap tuples—exactly the behaviour CMU 15-445’s buffer/heap projects walk you through.

TupleStream

Minimal iterator that returns (RecordId, TupleMeta, Tuple) triples. Index scans use IndexScanRequest to describe ranges.

Interactions

Execution – ExecutionContext::table_stream / index_stream delegate to handles.
Transaction – Handle methods call into TxnContext to acquire locks, record undo, and emit WAL.
Buffer Manager – TableHeap/BPlusTreeIndex access pages through the shared buffer pool.
Recovery – Heap/index mutations generate WAL records (HeapInsert, HeapDelete, IndexInsert, …) that ARIES replays.
Background – MVCC vacuum and index cleanup obtain handles and iterate tuples via the same abstractions as foreground scans.

Teaching Ideas

Implement a toy columnar handle to show how the execution engine can stay agnostic to storage layout.
Extend the TableHandle::full_scan / TableIterator plumbing to accept projection hints so students can experiment with column pruning.
Enable RUST_LOG=storage::table_heap=trace and trace MVCC version chains as updates occur.
Follow the CMU 15-445 Lab 2 flow: instrument TableBinding::delete to print every RID
- key pair, run an UPDATE with multiple indexes, and confirm the WAL stream contains the matching HeapInsert/HeapDelete + IndexLeafInsert/IndexLeafDelete entries.

Further reading: Disk I/O, Page & Tuple Layout, Table Heap & MVCC

Keyboard shortcuts

QuillSQL Internals