TacoDB — Relational Database from Scratch
Context
TacoDB was the term project for CSE 562 / 462: Database Systems at the University at Buffalo. The course provides a skeleton framework — include/storage, include/index, include/expr, include/dbmain — and asks you to implement the missing pieces of a working RDBMS. I built mine in C++17 over four lab milestones, tested against the GoogleTest harness shipped with the framework.
What I built
1. Storage layer
Variable-length page records with slotted page layout. The buffer pool uses a clock-replacement policy — a circular sweep with a reference bit, cheap to implement and good enough for the workload sizes the course tests against. Pinning and unpinning are explicit; the buffer manager refuses to evict a pinned frame, which forced me to track ownership carefully across nested operator calls.
2. B+ tree index
A persistent B+ tree built on top of the storage layer. The tricky parts were:
- Splits: when an internal node fills, splitting it correctly so the median key promotes up the tree. Edge cases at the root mean the tree depth grows.
- Merges and borrowing: on delete, when a node falls below the half-full threshold, I either borrow a key from a sibling or merge with a sibling and propagate the change up.
- Latching discipline: even though TacoDB is single-threaded, I had to be careful about stale page pointers across operations that re-traverse the tree.
3. Query processor
The execution engine is built around the iterator (Volcano) model — every operator implements open / next / close. I implemented:
- Hash join — build the smaller side into an in-memory hash table, probe with the other.
- Sort-merge join — sort both inputs, walk them in lockstep.
- Index-nested-loop join — useful when one side has a B+ tree index on the join key and the other is small.
The query planner is rule-based: it picks among the three join strategies based on table sizes, predicate selectivity, and whether a usable index exists.
4. SQL execution
End-to-end SQL execution: SELECT … FROM … WHERE … JOIN … GROUP BY … ORDER BY. The expression evaluator handles arithmetic and comparisons over the same set of types the storage layer encodes natively — integers, doubles, varchars.
What I learned
The thing that stuck with me most: the gap between an algorithm in a paper and the same algorithm in production code is enormous, and most of the gap is failure handling. The B+ tree is a famously elegant data structure. Implementing it so that a partial write doesn't leave the tree in a corrupted state — that's where most of the real engineering went.
I also got a much sharper intuition for why DBAs care so much about index choice. Watching a query that takes 800ms with a sequential scan drop to 4ms when you add the right B+ tree index — and watching it stay slow when you add the wrong index — makes the cost-based optimizer's job feel less like magic.
Stack
C++17, GoogleTest, CMake, GDB, jemalloc.
What's next
If I picked it up again, I'd add:
- Concurrency control (2PL or MVCC) — the framework is single-threaded by design, but a real database needs to do this.
- Crash recovery — write-ahead logging and ARIES-style recovery would be the obvious next step.
- A cost-based planner — the rule-based planner I wrote is fine for the test workloads, but cost-based estimation with histograms is what real engines do.