Module 3: nanoDB

This PSET covers Module 3: BigSort, HashPartition, JOIN algorithms (BNLJ, SMJ, HPJ), IO cost equations, B+ tree indexing, LSM trees, and query plans. Before starting, you should have read the Module 3 content, attended the lectures, and completed the NanoDB and Query Plans Colab walkthroughs in your CA section.

Conventions: Page size = 64 MB. C_r = C_w = 1 IO unless stated otherwise. IO costs are measured in number of page reads/writes. Ignore the cost of writing output (+OUT) in all calculations — we only count the cost of the algorithm itself.