James Routley

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).

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.

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.

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

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

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

Notebook	Topic	Launch
PlanEnumeration	Join-order enumeration algorithms (DPsize, DPsub, DPccp)
Distributed-Joins	Executing a join across several nodes

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.

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.).

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

This creates a virtual environment in .venv/, installs Python 3.12 if needed, and installs all required packages from uv.lock.

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.

uv run python -m unittest discover system/tests/

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.

See CONTRIBUTING.md for the code formatting, the docstring conventions, and how dependencies, notebooks and the API documentation are maintained.

People, in order of number of commits:

With help from Claude, an AI coding assistant by Anthropic, credited as co-author on commits.

ExplainDB: A Database System Built for Understandability

What's Inside the system/ Package

Setting Up the Environment with uv

What's Inside the `system/` Package