niwid-db

niwid-db is a toy database management system built from scratch, designed to explore fundamental database concepts, including memory and disk management, ACID properties, basic transaction handling, indexing, and query execution.

Table of Contents

1. Features
2. Getting Started
3. Examples
4. Some Implementation Details
5. Contributing

Features

• ACID Compliance via Shadow Paging: Ensures Atomicity, Consistency, Isolation (read-committed), and Durability by implementing shadow paging, maintaining a stable, crash-resistant state. Shadow paging allows a table to have only a single writer for simplified concurrency control.

• Transaction Management: Supports commits and rollbacks to execute or discard changes within a transaction block to ensure transactional atomicity and isolation.

• Custom Execution Engine: A simple query engine that processes SQL statements, validates the query and datatypes, and performs basic DDL, TCL, and DML operations. Also supports EXPLAIN and EXPLAIN ANALYZE. Unoptimized logical plans are executed directly, without physical plan generation or optimizations yet.

• SQL Parsing: The only part not written from scratch. Leverages the sqlparser-rs crate for SQL syntax parsing.

• B+ Tree Indexing: Implements a B+ Tree index to ensure uniqueness, enabling efficient lookups and range queries for unique columns. Since there is no optimizer yet, you can force an index lookup using the PREWHERE clause. Check out index.slt for more examples.

• Constraints: Supports NOT NULL and UNIQUE constraints to enforce data integrity, although primary keys and foreign keys (referential integrity) are not supported.

• Joins: Performs basic nested loop join operations between tables, allowing for relational queries.

Getting Started

Prerequisites

• Rust: niwid-db is written in Rust.

Installation

1. Clone the repository:

   git clone https://github.com/MohamedAbdeen21/niwid-db.git
   cd niwid-db
   

2. Run the server:

   cargo run --release --bin idk-server
   

3. Connect to the server from a different terminal:

   nc localhost 8080
   

Usage

niwid-db can execute SQL queries for managing tables, running transactions, and executing basic SQL commands.

Example:

CREATE TABLE users (
    id INT PRIMARY KEY,
    name TEXT NOT NULL,
    email TEXT
);

INSERT INTO users VALUES (1, 'Alice', '[email protected]');

You can also use transactions to batch operations:

BEGIN;
UPDATE users SET email = '[email protected]' WHERE id = 1;
ROLLBACK; -- Discards the update

Examples

For more examples, check out:

• the sqllogictests. If you're not familiar with slt files, check out how to read sqllogictests
• Examples panel in the demo website

Some implementation details

• Slotted pages, with string indirection and a B+ Tree Index.
• LRU page eviction policy
• Shadow-Paging for ACID. No MVCC, OCC, 2PL, or WAL.
• Simple query engine, directly executes the raw logical plan. No optimizer, or physical plan builder. The project focused on exploring the internals of the database, not the query engine.
• Catalog as a read-only Table, check it out using SELECT * FROM __CATALOG__; Using sqlparser.rs is the only part not written from scratch. I wrote my fair share of parsers (and contributed some to sqlparser-rs), but again, this was not the main focus of the project.
• Demo website made with HTMX and Askama.

Contributing

Contributions are always welcome! Feel free to submit issues or pull requests.