Introduction

Most database servers have limited RAM to process data. When datasets grow or resources are limited, data systems rely on disk storage (of course for other reasons too). However, disk I/O is far slower than RAM. This makes smart utilization and minimal disk access critical for implementing efficient and effective data management systems.

In this assignment you will design a query execution engine that operates under a strict memory budget, optimizing it for minimal disk I/O and efficient in-memory computations.

System Architecture

 ┌─────────────────────────────────────────────────────┐
 │                      Monitor                        │
 │  (spawns processes, sends queries, validates output)│
 └──────────────┬──────────────────────┬───────────────┘
                │ FD 5 (query in)      │ FD 6 (results / commands out)
                ▼                      ▲
 ┌──────────────────────────────────────────────────────┐
 │                    Database (YOU)                    │
 │  reads query → accesses disk → outputs result rows   │
 └──────────────┬──────────────────────┬────────────────┘
                │ FD 4 (commands out)  │ FD 3 (block data in)
                ▼                      ▲
 ┌──────────────────────────────────────────────────────┐
 │                  Disk Simulator                      │
 │  (block storage, tracks I/O for scoring)             │
 └──────────────────────────────────────────────────────┘

To give you a hands-on experience with building data systems, we’ve designed an in-house system in Rust comprising three components:

1. Disk Simulator — simulates a block-addressable storage. It stores raw table files and provides a read/write anonymous space for your database to use as scratch. It tracks I/O (reads and writes) access patterns and estimates simulated disk time, which contributes to your score (more on this later).
2. Monitor — This is the orchestrator. It spawns the disk and database processes, sends the query, and validates your output against expected results.
3. Database — this is what you will implement. It receives a query from the monitor, reads table data from the disk, executes the query, and streams the result rows back to the monitor.

You typically need to touch only the database/ directory.

File Descriptors

The monitor maps the following file descriptors for your database process at startup:

These are already wired up in database/src/io_setup.rs — you do not need to open any files or sockets yourself.

Constraints

The monitor enforces the following hard limits on your database process:

1. Memory: At least 64 MB virtual address space (RLIMIT_AS), including the stack (RLIMIT_STACK). Note, you will not be able to load entire tables into memory as they typically will be of several gigabytes.
2. Single-threaded: No spawning subprocesses (RLIMIT_NPROC = 1).
3. No file I/O: Writing files on disk is forbidden (RLIMIT_FSIZE = 0). Use the disk simulator’s anonymous space for any scratch storage.