MastiDB

Where the idea came from

The idea didn’t start with “I should write a database.”

At Udaan, I owned the Apache Druid layer behind Percept Insight, an in-house product-analytics platform that later became a SaaS product. I worked on the cluster, ingestion, segments, and query performance. The practical question was usually simple: why is this slice, funnel, or cohort slow, and what can I change to make it return in time?

Trying to answer that meant going quite deep into Druid. I spent a lot of time understanding how its configs and knobs affected storage and query execution. Sometimes I ended up reading the Druid source to understand what a setting actually did.

Around the same time, I was watching Prof. Andy Pavlo’s database courses at CMU — the Intro to Database Systems lectures on YouTube, and the advanced course on OLAP indexes, compression, and execution models. The lectures gave names and structure to things I had encountered while operating Druid: columnar storage, dictionary encoding, indexes, and partial aggregation.

I wanted to connect those ideas properly. So I decided to build a small analytical database myself, one where I could understand every major choice from the bytes on disk to the final result.

That became MastiDB. The name comes from masti, meaning fun or mischief. It is a playful name for a fairly serious learning project.

What I built

MastiDB is a single-node, disk-based columnar OLAP engine written in Python. Most of the hot modules are compiled using MyPyC. You can install it with pip install mastidb.

It can ingest CSV, TSV, JSON, or ndJSON and query the resulting data using a small SQL interface. It currently supports SELECT, equality-based WHERE, GROUP BY, ORDER BY, LIMIT, and COUNT / SUM / AVG / COUNT(DISTINCT).

I did not want to build an in-memory dataframe and put a SQL parser in front of it. The data had to stay on disk. Filters had to use indexes. The engine had to avoid creating rows that a query did not need. A table also had to work across multiple independent segments.

It is not meant to replace Druid or ClickHouse, and it is not production-ready. The useful thing about MastiDB is that it uses many of the same basic ideas while staying small enough to follow end to end.

How the data is stored

Every column in a segment is stored as two files: a 40-byte metadata file and a memory-mapped payload file.

The payload contains five sections:

1. offsets into the dictionary;
2. a sorted dictionary of distinct values;
3. one dictionary id per row;
4. offsets into the bitmap index; and
5. one roaring bitmap per distinct value.

The metadata file contains ten integers describing where each section starts and ends. Once that is read, the engine can jump directly to a dictionary value, an encoded row value, or a bitmap. It does not need to scan the file to discover where something is stored.

The payload is accessed through mmap. The engine asks for byte ranges instead of loading an entire column into a Python list. The operating system’s page cache decides which parts are actually resident in memory. This means a 100 MB column can be queried without first allocating a 100 MB Python object.

There are clear costs to this layout. The encoded list always uses four bytes per row per column. Bitmap indexes added roughly 13 to 40 percent in the sample columns I measured. Low-cardinality columns work well with this format. Near-unique columns make the dictionary and per-value indexes much less attractive.

How filtering works

For a filter such as:

WHERE countryName = 'India'

MastiDB binary-searches the sorted dictionary, finds the dictionary id for India, and reads the matching bitmap. AND and OR become bitmap intersection and union.

So an equality filter does not scan the encoded column. If the value is not in the dictionary, the engine can stop after the dictionary search without reading any row values.

Every distinct value is indexed during ingest. That costs extra space and makes ingestion heavier, but it keeps repeated equality filters cheap. It makes sense for an append-only analytical store. It would make much less sense for a write-heavy database.

How aggregation works

Once filtering produces a bitmap of matching row ids, the engine processes those ids in batches. It fetches the required dictionary ids into a small value matrix, then runs aggregation over integers rather than building a Python object for every row.

Grouping also happens on dictionary ids, not decoded strings. If a million rows collapse into a few hundred groups, the engine only needs to decode the group keys when producing the partial result.

The distinction between partial and final state became important when I added segments. Each segment processes a query independently and returns unfinished state:

• COUNT returns an integer;
• SUM returns a running total;
• AVG returns (sum, count), not an average;
• COUNT(DISTINCT) returns a set.

The executor merges these states and only then finalises the answer. For example, averaging the averages from two segments can be wrong, while merging their sums and counts is correct.

Segment dictionaries are independent, so the same dictionary id can mean different values in different segments. Group keys therefore have to be decoded before partial results are merged. This adds some work, but it keeps multi-segment results correct.

How ORDER BY and LIMIT work

For a query like this:

SELECT cityName, added
WHERE countryName = 'India'
ORDER BY added DESC
LIMIT 5

a simple implementation would materialise every matching row, sort them all, and keep five.

MastiDB uses two passes. In the first pass, it reads only what is needed to identify the five winning row ids and keeps them in a bounded heap. In the second pass, it fetches and decodes the projected values for those five rows.

The sorted dictionary helps here too. Dictionary ids preserve the lexicographic order of their values, so ordering by a plain string column can often compare integer ids without decoding the strings first.

This was one of the more useful lessons from the project. Many of the biggest performance improvements came from avoiding work altogether: not decoding values too early, not fetching the same column once per aggregate, and not materialising rows that LIMIT would discard.

Segments

A table can contain one segment or several. Each segment is an immutable horizontal slice with its own column files, dictionaries, and indexes.

The query path is always:

SQL → process each segment → merge partial states → finalise → result

Even a single-segment query follows this path. There is no separate implementation that skips the merge model. It costs a little performance, but it means single-segment and multi-segment queries use the same correctness rules.

Segments are processed sequentially today. Since the processors already return independent mergeable states, parallel fan-out should mostly be a change inside the executor rather than a redesign of the query engine.

Performance

I tracked a few queries on the NYPL menu-item dataset, which has about 1.3 million rows. These numbers are from my laptop with a warm cache and a MyPyC build. They are useful for comparing versions of MastiDB, not for comparing it with production databases.

Query	First working version	Current mergeable-partials version
COUNT(id)	8.77s	1.45s
GROUP BY … COUNT	10.57s	1.98s
COUNT … WHERE price = '0.25'	0.59s	0.15s
COUNT, SUM, AVG … GROUP BY	27.29s	3.01s

Adding types and compiling with MyPyC was the first large improvement. It cut most query times by around 60 percent without changing the design.

After that, the useful gains came from the query path itself. A value matrix stopped the engine from fetching the same column separately for COUNT, SUM, and AVG. Batching reduced repeated reads. Late materialisation removed a lot of string decoding. The two-pass projection path reduced the number of rows that had to be built.

Not every good change made a benchmark faster. Adding mergeable partials made GROUP BY slightly slower than the fastest earlier version because group keys now have to be decoded and rehashed at the segment boundary. I kept that cost because correct multi-segment behaviour mattered more than a faster single-segment number.

The largest remaining performance issue is the type system. MastiDB currently stores every value as a string. COUNT does not need to look at the value, but SUM and AVG have to decode and parse numeric strings for every row. Typed metric columns should remove much of that work.

Current limitations

MastiDB is still an experiment, and some limitations are fundamental rather than cosmetic:

• all values are stored as strings, so numeric ordering is lexicographic and numeric aggregates parse values on the fly;
• WHERE supports equality, but not ranges, IN, or inequalities;
• ingest rewrites a segment instead of appending a new one;
• segments are processed sequentially and there is no segment pruning;
• there are no joins, subqueries, HAVING, updates, deletes, or concurrency;
• aggregate ordering on string group keys has a known bug;
• COUNT(DISTINCT) is not yet correct across segments because its state currently holds segment-local dictionary ids.

The last two are correctness issues, not just missing features. I have kept them explicit in the roadmap rather than presenting the engine as more complete than it is.

What I learned

Before building MastiDB, I understood ideas like dictionary encoding, bitmap indexes, late materialisation, and partial aggregation in theory and from using Druid. Implementing them showed me where the actual decisions are.

For example, a sorted dictionary makes string sorting cheaper, but dictionary ids cannot safely move across segment boundaries. AVG has to remain a sum and count until merging is finished. Columnar storage is naturally good at aggregation but awkward when it has to reconstruct many rows. Fixed-width integers make addressing simple, but also create space overhead and hard file-size limits.

More than anything, it changed the way I look at performance work. The biggest improvements often did not come from making a loop faster. They came from looking at why the loop existed and whether the query needed it at all.

Using it

pip install mastidb
mastidb ingest -d /path/to/data -s /path/to/source.csv
mastidb console -d /path/to/data

from mastidb import QueryExecutor, Table

table = Table.from_ingest_source(
    "/tmp/menuitem",
    "MenuItem.csv",
    num_segments=4,
)

result = QueryExecutor(table).execute(
    "SELECT menu_page_id, COUNT(id) "
    "GROUP BY menu_page_id "
    "ORDER BY COUNT(id) DESC "
    "LIMIT 10"
)

print(result.get_results())

The GitHub repository contains the code and tests. The architecture guide goes into the file layout and follows both query paths in detail.