Skip to content

ShireenMeher/database_engine

BranchesTags

Repository files navigation

CS645 Database Design and Implementation

System Architecture

The system implements a simplified database storage engine that manages data between memory (buffer pool) and persistent storage (disk files).

The architecture is organized into four main layers:

        +------------------------+
        |       Application      |
        |   (Dataset Loader)     |
        +-----------+------------+
                    |
                    v
        +------------------------+
        |  Index Layer (B+Tree)  |
        |(point / range searches)|
        +-----------+------------+
                    |
                    v
        +------------------------+
        |      Buffer Manager    |
        |  (Caching + eviction)  |
        +-----------+------------+
                    |
                    v
        +------------------------+
        |        Page Layer      |
        |   (DataPage / Record)  |
        +-----------+------------+
                    |
                    v
        +------------------------+
        |       Disk Manager     |
        |    (File I/O Layer)    |
        +------------------------+

Each layer abstracts the complexity of the layer below it, allowing modular development and easier debugging.

Core Components

Buffer Manager

The BufferManager manages the in-memory buffer pool and coordinates page movement between memory and disk.

Responsibilities:

  • Load pages from disk
  • Create new pages
  • Maintain page table (fileId, pageId → frame)
  • Track pinned pages
  • Evict pages when the buffer pool is full
  • Flush dirty pages to disk

Replacement Policy

The system uses LRU (Least Recently Used) eviction.

Eviction rules:

  • Only pages with pinCount == 0 can be evicted
  • Dirty pages are written to disk before eviction

Frame

A Frame represents one slot in the buffer pool.

Each frame stores:

  • Page reference
  • File ID
  • Page ID
  • Pin count
  • Dirty flag

A frame is evictable only when pinCount == 0.

Page

Pages are the unit of disk I/O. PAGE_SIZE = 4096 bytes The Page interface defines methods for:

  • retrieving page ID
  • serializing page data
  • loading page data from disk

DataPage

A DataPage stores multiple records with a fixed schema.

Structure:

  • Page metadata
  • Serialized schema
  • Record count
  • Serialized records

The maximum records per page are calculated as: (pageSize - headerSize - schemaSize) / recordSize

Records are stored sequentially.

Record

A Record represents a row of data.

Characteristics:

  • Fixed-length fields
  • Schema-driven layout
  • Stored in column order using LinkedHashMap

Serialization concatenates all field values.

Disk Manager

The DiskManager handles all file I/O operations.

Responsibilities:

  • Read pages from disk
  • Write pages to disk
  • Allocate new pages

Pages are stored using: offset = pageId * PAGE_SIZE

This allows constant-time random page access.

FileHandle

A FileHandle stores metadata for database files.

It tracks:

  • file identifier
  • file path
  • temporary vs persistent file
  • maximum allocated page ID

B+ Tree Index

A BPlusTree manages the logical tree structure for efficient O(logf​N) database lookups.

It handles:

  • point and range searches
  • leaf and internal node splitting
  • upward split propagation
  • page fetching via the Buffer Manager

Index Pages

An IndexPage represents a 4KB disk block formatted specifically to store tree nodes.

It includes:

  • MetaPage: tracks the root page ID and fixed key size
  • InternalPage: stores routing keys and child page pointers
  • LeafPage: stores actual data entries (keys mapped to Rids)
  • sibling pointers (prev/next) in leaf pages for fast range scans

Query Execution

The query executor runs a fixed director lookup query over Movies, WorkedOn, and People using iterator-style operators. Operators expose open, next, and close; parent operators pull tuples from their children. The plan uses scans or the optional title index for Movies, a selection on WorkedOn.category = director, a materialized projection of WorkedOn(movieId, personId), and two Block Nested Loop joins.

Before running a query, preprocess the CSV files into database files:

./mvnw -DskipTests compile
java -cp target/classes edu.cs645.Main pre_process \
  src/main/resources/data/title.csv \
  src/main/resources/data/workedon.csv \
  src/main/resources/data/name.csv

For faster local testing, pre_process also accepts an optional row limit:

java -cp target/classes edu.cs645.Main pre_process \
  src/main/resources/data/title.csv \
  src/main/resources/data/workedon.csv \
  src/main/resources/data/name.csv \
  26000

Run the query with:

java -cp target/classes edu.cs645.Main run_query <start_range> <end_range> <buffer_size>

Example:

java -cp target/classes edu.cs645.Main run_query a az 50

The command prints CSV rows in title,name format to stdout and prints the measured I/O count to stderr.

Testing Strategy

Unit tests verify correctness of each subsystem.

BufferManager Tests

Tests cover:

  • LRU eviction
  • pin/unpin behavior
  • dirty page flushing
  • append-only file behavior
  • page bounds validation

DiskManager Tests

Tests verify:

  • page allocation
  • correct disk offsets
  • read/write correctness

DataPage and Record Tests

Tests verify:

  • record insertion
  • page capacity handling
  • serialization and deserialization correctness

B+ Tree Index Tests

Tests verify:

  • corectness of indexing (c1-c4)
  • performance of indexed searches vs linear searches (p1-p3)

Query Execution Tests

Tests cover:

  • base table loading for Movies, WorkedOn, and People
  • end-to-end query output compared with an H2 SQL reference
  • multiple title ranges and buffer sizes
  • empty ranges, inclusive range boundaries, and duplicate title/director rows
  • optional title-index access for the Movies table
  • output CSV formatting
  • materialized temporary table lifecycle
  • range/equality selection operators
  • BNL join correctness on a small synthetic input
  • analytical vs measured I/O behavior

Run all tests:

./mvnw test

(Running all tests also generates the query execution I/O CSV/SVG plot artifacts.)

Run only the query execution tests:

./mvnw -Dtest=Lab3Tests test

Generate query execution I/O plot data and graph for progressively wider title ranges:

./mvnw -Dtest=Lab3Tests#testIOPlotAcrossSelectivities test

This writes the following files in the project root:

  • io_plot.csv
  • io_plot.svg

Generate the analytical-vs-measured I/O plot data and graph:

./mvnw -Dtest=Lab3Tests#testAnalyticalVsMeasuredIOs test

This writes the following files in the project root:

  • analytical_io_plot.csv
  • analytical_io_plot.svg

The B+ tree performance tests also attempt to generate plots. If Python plotting dependencies are unavailable, plot generation is skipped without failing the test suite.

Design Assumptions

  • Page size is 4096 bytes
  • Records are fixed-length
  • Schema is stored within each page
  • Buffer replacement uses LRU
  • Disk files grow append-only

Serialized Object Formats

Schema

Length (bytes) Data Description
2 Length of Column1's Name The length of Column1's name in bytes
column1.length() Column1's Name Column1's name encoded in US-ASCII
2 column1's Size The number of bytes required to store Column1's data
... ... ...
2 Length of ColumnN's Name The length of ColumnN's name in bytes
columnN.length() ColumnN's Name ColumnN's name encoded in US-ASCII
2 columnN's Size The number of bytes required to store ColumnN's data

Record

  • The byte array is not self-describing. Deserialization requires the schema (column names and sizes) to interpret the bytes correctly.
  • All values are stored in the order defined by schema.keySet().
Length (bytes) Data Description
schema.get("column1") column1 value Serialized value for column1
schema.get("column2") column2 value Serialized value for column2
... ... ...
schema.get("columnN") columnN value Serialized value for columnN

Page

  • The byte array is self-describing. All that is required for deserialization is to know that the bytes represent a Page.
Length (bytes) Data Description
1 Page Type ID Identifies the type of the page (e.g., DataPage, IndexPage). Used during deserialization to determine which subclass format to use.
4 Page ID A unique identifier for this page. Assigned by the BufferManager to track and reference pages.
2 Page Size Total size of the page in bytes. Determines the amount of space allocated for the page, including header, data, and any padding
Remaining bytes Payload The payload of the page. For a DataPage, this contains serialized records; for other page types, it contains their specific content. Fills the remaining space in the page.

DataPage

Length (bytes) Data Description
1 Page Type ID Identifies the type of the page (e.g., DataPage, IndexPage). Used during deserialization to determine which subclass format to use.
4 Page ID A unique identifier for this page. Assigned by the BufferManager to track and reference pages.
2 Page Size Total size of the page in bytes. Determines the amount of space allocated for the page, including header, data, and any padding
2 Schema Size Size of the serialized schema in bytes. Used to determine how many bytes to read to fully reconstruct the schema during deserialization.
? Schema Serialized representation of the page schema. Required to correctly interpret record data stored in this page.
2 Record Count Then number of records contained in this page. Required to read the appropriate amount of records, and not fill the page will empty records.
Remaining bytes Records Contiguous sequence of serialized records. Each record is encoded according to the schema and has a fixed size of Record Size bytes.

MetaPage

Length (bytes) Data Description
1 Page Type ID Identifies the page as a MetaPage.
4 Page ID Always 0 for the main meta page.
4 Root Page ID The Page ID of the current root of the B+ Tree.
4 Key Size The fixed length (in bytes) of the search key used in this index.

InternalPage

Length (bytes) Data Description
1 Page Type ID Identifies the page as an InternalPage.
4 Page ID Unique identifier for this page.
4 Key Size The fixed length of the keys.
4 Key Count The number of keys currently stored in this node.
4 First Child Ptr The Page ID of the left-most child node (P0).
Remaining bytes Entries Contiguous sequence of entries.

LeafPage

Length (bytes) Data Description
1 Page Type ID Identifies the page as a LeafPage.
4 Page ID Unique identifier for this page.
4 Key Size The fixed length of the keys.
4 Key Count The number of entries currently stored in this node.
4 Prev Leaf ID Page ID of the previous leaf node (for reverse range scans).
4 Next Leaf ID Page ID of the next leaf node (for forward range scans).
Remaining bytes Entries Contiguous sequence of entries.

Limitations

Current implementation does not include:

  • concurrency control
  • transaction logging
  • record deletion or updates
  • B+ Tree deletions

Future Improvements

Potential extensions:

  • write-ahead logging
  • concurrent buffer manager
  • slot-directory page layout
  • B+ Tree deletions and bulk loading

Dependencies

Dependencies:

  • Java JDK 17
  • Maven

How to run

.\run_tests.bat OR ./run_tests.sh

About

Relational database storage engine built from scratch in Java — disk-backed buffer pool with LRU eviction, B+ Tree index with leaf sibling pointers for range scans, volcano-model query executor with Block Nested Loop joins, and I/O cost analysis across buffer sizes

Topics

java serialization database storage-engine dbms indexing lru-cache database-engine range-query systems-programming page-cache file-io buffer-pool b-plus-tree bplustree query-executor buffer-manager disk-manager iterator-model block-nested-loop-join

Resources

Readme
Activity

Stars

0 stars

Watchers

0 watching

Forks

0 forks
Report repository

Releases

No releases published

Packages

 
 
 

Contributors

Languages