explaindb/explaindb
A Database System built for Understandability. Contribute to explaindb/explaindb development by creating an account on GitHub.
10 stars · 1 forks
README
ExplainDB - a Database System built for Understandability
Teaching materials for a database systems course: a collection of Jupyter notebooks and a didactic DBMS implemented in Python (the system/ package). The lecture that uses this code is available on YouTube: Database Systems 2024/25 (Prof. Dr. Jens Dittrich, Big Data Analytics Group, Saarland University). Try It in the Browser
Click the badge to open the notebooks in JupyterLab on mybinder.org, with no installation needed. The start can take a few minutes the first time, after a change to the repository, or after a longer pause, while Binder builds the environment. Sessions are temporary: they end after a period of inactivity, or after a few hours at most, and all your changes are lost. Download any notebook you want to keep (File → Download). mybinder.org is a free public service: do not upload private or confidential data, and do not enter passwords in a Binder session. Notebooks The notebooks are grouped by the chapters of the tutorial, which explains each topic and points to the code that implements it. The launch badge opens a notebook directly on Binder. Storage & Data Layout
Notebook Topic Launch
Data-Layout Row vs. column layout: how much each layout has to read for different queries
RAID-Nesting-Trade-offs Nesting RAID 0 arrays and its effect on sequential read performance
Indexing
Notebook Topic Launch
B-tree Building a B⁺-tree step by step, with visualized splits and leaf chain
Bitmaps-and-Bloom-Filters Bitmap indexes, their compression (WAH), and Bloom filters for fast "is this value present?" checks
Bit-Sequences-in-Pandas Boolean masks in pandas as bit sequences: filtering rows and combining masks with AND
Christmas-Tree Radix and descriptor tries, with buffered and "crystal ball" variants
Recursive-Model-Index A learned index (RMI) for searching sorted data
Query Processing
Notebook Topic Launch
Result-DB Running a query with two joins as a pipeline of operators (push model)
CodeGen Generating Python code for the Result-DB query and running it
Shared-Scan Several concurrent queries sharing one pass over the data
External-Merge-Sort Sorting data larger than main memory: sort chunks, then merge them
Top-k ORDER BY title LIMIT 10 without sorting all rows
Online-Aggregation A running estimate of an aggregate before the scan completes
Query Optimization
Notebook Topic Launch
PlanEnumeration Join-order enumeration algorithms (DPsize, DPsub, DPccp)
Distributed-Joins Executing a join across several nodes
Multidimensional
Notebook Topic Launch
Z-Order-Curve Z-codes (Morton codes): mapping 2-D data to 1-D while preserving locality
What's Inside the system/ Package A small DBMS written for reading, not for speed. Interfaces in system/interfaces/ carry the contracts; the other folders implement them:
Storage (storage/): the storage hierarchy (DRAM, caches, SSD, disk) and RAID block assignment (RAID 0/1/4/5) with a reliability and performance cost model. Indexes (indexes/): B⁺-tree, bitmap indexes (equality- and range-encoded), Bloom filters, radix tries and the "Christmas tree" (a radix trie with node buffers). Bit sequences (bit_sequences.py): plain and WAH-compressed bit sequences used by the bitmap indexes. Transactional stores (stores/): a versioned key-value store and MVCC (multi-version concurrency control) with journaling, also with an index. Query processing (query_processing/): operators such as scan, filter, hash join, semi-join and count, plus WHERE-clause predicates. Sorting and queues (sorting.py, queues/): external merge sort with in-memory and disk-backed queues. Query optimization (query_optimization/): join graphs (chain, star, cycle, clique), cardinality estimation, the C_out cost function and plan tables for dynamic-programming join ordering.
DBMS.py ties these parts together: it manages stores, prepared queries and query optimization. Unit tests for all of this live in system/tests/. Setting Up the Environment with uv This repository uses uv to manage its Python version and dependencies. uv installs the correct Python interpreter for you, so no separate Python installation is required. 1. 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"
See the uv installation docs for alternatives (Homebrew, pipx, etc.). 2. Clone the Repository git clone https://github.com/explaindb/explaindb.git cd explaindb 3. Install Dependencies uv sync This creates a virtual environment in .venv/, installs Python 3.12 if needed, and installs all required packages from uv.lock. 4. Run Jupyter Notebook uv run jupyter notebook This opens a browser window listing the files in the current directory. The notebooks live in the notebooks/ directory; open them from there. Any command can be run inside the project environment by prefixing it with uv run — no manual environment activation needed. Alternatively, you may run the notebooks in an IDE like PyCharm; point its interpreter at the .venv/ created by uv. Running the Tests uv run python -m unittest discover system/tests/ API Documentation The API documentation, generated from the source docstrings, is available online at https://bigdata.uni-saarland.de/software/explaindb/index.html. How to build it locally is described in CONTRIBUTING.md. Contributing See CONTRIBUTING.md for the code formatting, the docstring conventions, and how dependencies, notebooks and the API documentation are maintained. License ExplainDB is licensed under the GNU Affero General Public License v3.0 (AGPL-3.0). Copyright (C) 2026 Prof. Dr. Jens Dittrich, Saarland University. Contributors People, in order of number of commits:
Jens Dittrich Marcel Maltry Simon Rink Luca Gretscher Joris Nix
With help from Claude, an AI coding assistant by Anthropic, credited as co-author on commits.