A serious OLAP
database engine.
Written in Python.
MastiDB is a minimal, on-disk columnar database engine. It implements the same core ideas that make mature analytical engines fast, at a size you can read in an afternoon.
"SELECT cityName, COUNT(id)
WHERE countryName = 'India'
GROUP BY cityName"
I thought I understood databases. There was one way to find out.
The confidence
After years of operating, tuning, and optimising analytical engines, I thought I understood the machinery pretty well.
The itch
But I still wanted to follow one query all the way down: which bytes moved, which values were decoded, and where the time actually went.
The questionable decision
So I built a columnar database in Python.
It seemed reasonable at the time.
Follow a query through the engine
Step through what MastiDB does with one analytical query, from SQL text to result. Bitmaps and integer dictionaries let it skip both the row scan and the string building.
How Stage 1 Works
The SQL string is parsed into an abstract syntax tree. ParsedQuery computes the dependent columns needed: countryName and cityName. Every other column on disk is left untouched.
The SQL string is parsed into an abstract syntax tree. ParsedQuery computes the dependent columns needed: countryName and cityName. Every other column on disk is left untouched.
Look inside a segment file (.mastidb)
Every column is stored on disk as two files: a 40-byte binary header and a memory-mapped payload. Hover any region below to trace a value from the logical table down to the bytes that hold it.
- A 40-byte header (
.meta) defines ten 32-bit byte boundaries, and an unpadded payload file (.mastidb) stores the data. - Inside that payload, dictionary offsets, sorted UTF-8 values, encoded row IDs, and Roaring Bitmaps sit back-to-back, with no padding between them.
- Because every row ID is exactly 4 bytes, row i is found by arithmetic (
offset + i × 4) instead of by walking an index or following pointers.
Logical Table Editor
EditableMemory-Mapped Address Space (.mastidb file)
Continuous binary layoutCore engine techniques
Every design choice here trades speed, space, and complexity against each other. For each one: the problem it solves, what MastiDB does about it, and what that costs.
Columnar segments and fixed addressing
Row storage reads every column off disk, even the ones the query never asks for.
Each column lives in its own immutable file, and every row ID is a fixed 4-byte integer, so row i is found by arithmetic (offset + i * 4) rather than by walking an index.
Costs 4 bytes per row even for columns with only a handful of distinct values, and it is a poor fit for single-row OLTP work.
Sorted dictionary encoding
Storing the same strings again on every row wastes space, and comparing them in Python is slow.
Each distinct string is stored once in a sorted dictionary. Queries find a value by binary search in O(log N), and ORDER BY on a string column sorts integers instead of strings.
Columns with many distinct values make the dictionary large, and numbers are still stored as strings today, so SUM and AVG parse a float per row.
Roaring Bitmap indexing
Checking a WHERE clause row by row means reading every row in the table.
Ingestion builds a compressed Roaring Bitmap for every distinct value. An equality filter is then one bitmap lookup, and AND and OR are bitwise intersection and union.
The bitmaps add roughly 15 to 40% to segment size. Filtering is equality-only today; ranges and inequalities are not indexed yet.
Late materialization
Turning IDs back into strings for rows that never reach the output is work thrown away.
Columns stay as integer IDs through filtering, grouping, and sorting. Only the rows that survive LIMIT, or the distinct output groups, are decoded back into strings.
A non-aggregate query with a large LIMIT ends up doing many random seeks into the dictionary files to materialize its columns.
Mergeable partial aggregation
Every segment has its own dictionary, so partial results from two segments cannot simply be concatenated.
Each segment returns an AggregatePartial whose merge() is associative and commutative. AVG, for instance, carries (sum, count) until the very end, so partials from any number of segments combine safely.
Group keys have to be decoded to strings before they cross a segment boundary, since two segments map the same string to different IDs.
MyPyC ahead-of-time compilation
Interpreter overhead and dynamic dispatch dominate the cost of a tight inner loop in Python.
The hot inner loops are type-annotated and compiled to native C extensions with MyPyC, which cut runtime by about 60% without changing a single algorithm.
Needs a C compiler at install time (it falls back to pure Python without one) and holds the compiled modules to strict static types.
Where it stands today
MastiDB is an experimental project built for learning. It is not meant for production, and it is not trying to compete with mature columnar systems.
What works today
- ✓ Supported SQL:
SELECT,WHERE(equality, AND, OR),GROUP BY,ORDER BY,LIMIT, and aggregations (COUNT,SUM,AVG). - ✓ Two-pass execution: string decoding waits until a bounded min-heap has settled which top-K row IDs actually survive.
- ✓ Independent segments: each segment answers a query on its own and returns a partial result that merges with the others.
Measured on my laptop with a warm cache. MyPyC compilation cut runtime by about 60%, taking COUNT(id) from 8.77s to 3.41s. The value matrix then halved multi-aggregate queries by fetching each column once per chunk, and batched integer reads brought single-segment scans to ~1.45s and equality queries to ~0.15s.
Known rough edges
- ✕ Everything is a string: every column uses
DIMENSIONencoding today, soSUMandAVGparse a string on every row. Real numeric types are on the roadmap. - ✕ WHERE is equality-only: Bitmap lookups resolve exact equality only (
col = val). Ranges, inequalities, andINlists are not yet supported. - ✕ Sequential segment scan: Segments are queried in a sequential Python loop, not fanned out across threads or worker processes.
- ✕ Cross-segment COUNT(DISTINCT): Partial distinct states are merged on raw per-segment dictionary IDs instead of decoded values, which is a known correctness bug.
- ✕ Batch-only ingest: Ingestion rewrites the whole target directory rather than appending a segment. Joins and subqueries are out of scope.
Experimental Playground
Expect rough edges, missing features, and an API that still moves. Ideas, bug reports, and patches are all welcome.
