ExplainDB: A Database System Built for Understandability

License: AGPL v3 Last commit Binder

ExplainDB is a didactic database management system (DBMS) implemented in Python. Rather than focusing on raw performance, it is designed specifically for educational clarity, serving as the primary teaching tool for the "Database Systems 2024/25" course taught by Prof. Jens Dittrich (Big Data Analytics Group, Saarland University).

[!IMPORTANT] The accompanying lecture series is available for public viewing on YouTube.

🚀 Quick Start: Try it in the Browser

You can explore the system without any local installation by using mybinder.org. Simply click the Binder badge to launch the notebooks in a JupyterLab environment.

Warning & Limitations:

Startup Time: Initial launches or updates to the repository may take several minutes to build the environment.
Volatility: Sessions are temporary. Inactivity or a few hours of use will result in the loss of all unsaved changes.
Privacy: Since Binder is a free public service, ~~do not~~ upload sensitive data or enter passwords.

📚 Educational Notebooks

The project is organized into notebooks that mirror the chapters of the course tutorial. Each notebook explains a theoretical concept and provides the corresponding Python implementation.

Storage & Indexing

Notebook	Topic	Description
Data-Layout	Row vs. Column	Analysis of read requirements for different query types.
RAID-Nesting-Trade-offs	RAID 0 Nesting	Impact of nested RAID 0 arrays on sequential read speeds.
B-tree	B $^+$ Trees	Step-by-step construction with visualized leaf chains and splits.
Bitmaps-and-Bloom-Filters	Fast Lookups	Bitmap indexes, WAH compression, and Bloom filters for membership checks.
Bit-Sequences-in-Pandas	Boolean Masks	Using pandas bit sequences for row filtering and `AND` operations.
Christmas-Tree	Tries	Radix and descriptor tries, including "crystal ball" and buffered variants.
Recursive-Model-Index	Learned Indexes	Implementation of an RMI for searching sorted datasets.

Query Processing & Optimization

Notebook	Topic	Description
Result-DB	Push Model	Executing queries with multiple joins as a pipeline of operators.
CodeGen	Python Generation	Generating and executing Python code specifically for Result-DB queries.
Shared-Scan	Concurrent Access	Allowing multiple queries to share a single data pass.
External-Merge-Sort	Memory Management	Sorting datasets larger than RAM via chunking and merging.
Top-k	Optimized ORDER BY	Implementing `LIMIT 10` without a full dataset sort.
Online-Aggregation	Running Estimates	Calculating aggregates before the full scan is finished.
PlanEnumeration	Join Ordering	Algorithms for join-order optimization (e.g., `DPsize`, `DPsub`, `DPccp`).
Distributed-Joins	Multi-node Execution	Performing join operations across several distributed nodes.
Z-Order-Curve	Multidimensional	Using Morton codes to map 2D data to 1D while keeping locality.

🛠️ System Architecture

The system/ package is a "read-first" DBMS. Its structure is designed to be transparent:

Component Breakdown

interfaces/: Defines the contracts that all other modules must follow.
storage/: Manages the hierarchy (DRAM $\rightarrow$ Cache $\rightarrow$ SSD $\rightarrow$ Disk) and RAID block mapping (0, 1, 4, 5) using a cost model for performance and reliability.
indexes/: Contains B $^+$ trees, Bloom filters, radix tries, and the "Christmas tree" (buffered radix trie).
bit_sequences.py: Handles plain and WAH-compressed sequences for bitmap indexing.
stores/: Implements a versioned key-value store with Multi-Version Concurrency Control (MVCC) and journaling.
query_processing/: Implements the engine operators: scan, filter, hash join, semi-join, and count.
sorting.py & queues/: Provides external merge sort logic with both memory and disk-backed queues.
query_optimization/: Handles join graphs (clique, star, cycle, chain), cardinality estimation, and the $C_{out}$ cost function: $\text{Cost} = C_{out}(\text{plan})$ It also utilizes plan tables for dynamic programming join ordering.
DBMS.py: The central hub that integrates stores, prepared queries, and the optimizer.

💻 Local Installation & Setup

This project utilizes uv for streamlined Python version and dependency management.

Setup Checklist

Install uv
Clone the repository
Sync dependencies
Launch Jupyter

Step-by-Step Guide

Install uv

macOS/Linux:

curl -LsSf https://astral.sh/uv/install.sh | sh

Windows (PowerShell):

powershell -ExecutionPolicy ByPass -c " irm https://astral.sh/uv/install.ps1 | iex "

Clone and Enter Repository

git clone https://github.com/explaindb/explaindb.git
cd explaindb

Install Dependencies
```
uv sync
```
This command automatically handles Python 3.12 installation and creates a .venv/ directory based on the uv.lock file.
Launch the Environment
```
uv run jupyter notebook
```
Navigate to the notebooks/ folder to begin.

Pro Tip: You can run any command within the project context by prefixing it with uv run. Alternatively, point your PyCharm interpreter to the .venv/ folder.

Running Tests

To verify the system installation, run the unit tests:

uv run python -m unittest discover system/tests/

For further details, refer to the API Documentation.